myhomework

课程名称：操作系统 年级：2020级 上机实践成绩：
指导教师：翁楚良 姓名：陈柏延 学号：10205501441
上机实践名称：Minix3-进程管理 上机实践日期：2022.3.25
上机实践编号：02 组号： 上机实践时间：2022.3.25

OS-Project2

一、实验目的

  1. 巩固操作系统的进程调度机制和策略

  2. 熟悉 MINIX 系统调用和 MINIX 调度器的实现

  3. 熟悉安装和调试MINIX3.3.0操作系统

  4. 巩固操作系统通过串口输出信息

二、实验环境

  • 物理机：MacOS 11.6
  • 虚拟机：Minix 3
  • 虚拟机软件：Vmware
  • 物理机通过ssh远程连接虚拟机
  • 代码搜索与编辑：vscode
  • 物理机与虚拟机间文件传输：FileZilla

三、实验要求

在MINIX3中实现Earliest-Deadline-First近似实时调度功能

  1. 提供设置进程执行期限的系统调==chrt(long deadline)==，用于将调用该系统调用的进程设为实时进程，其执行的期限为:从调用处开始deadline秒。

​ 实现时示例：

1
2
3
4
#include <unistd.h>
......
chrt(10);/* 该程序将可以运行的最长时间为10秒，若没有运行结束，则 强制结束*/
......

​ chrt的定义: int chrt(long deadline);

​ /*deadline 是最后期限值(秒)，返回值1表示成功，返回值0表示该调用出错 */

  1. 在内核进程表中需要增加一个条目，用于表示进程的实时属性; 修改相关代码，新增一个系统调用chrt，用于设置其进程表中的 实时属性。
  2. 修改proc.c和proc.h中相关的调度代码，实现最早deadline的用户进程相对于其它用户进程具有更高的优先级，从而被优先调度运行。
  3. 在用户程序中，可以在不同位置调用多次chrt系统调用，在未到 deadline之前，调用chrt将会改变该程序的deadline。
  4. 未调用chrt的程序将以普通的用户进程(非实时进程)在系统中运行。

四、实现过程

实现过程可分为==增加系统调用chrt部分==与==更改与deadline相关的进程调度部分。==

准备过程：先在虚拟机中下载minix3.3.0源码，编译生成新的kernel后重启虚拟机。为了便于修改代码及观察代码各层之间的关系，将关键文件通过FileZilla上传至物理机，通过vscode观察调用关系、全局搜索。

如图：截屏2022-04-16 上午10.10.30接下来按照应用层、服务层、内核层、进程调度的顺序依次更改源代码。

增加系统调用chrt

MINIX3中的系统调用结构分成三个层次:应用层、服务层、内核层。在这三层中分别进行代码修改，实现系统调用chrt的信息传递。从应用层用_syscall将信息传递到服务层，在服务层用 _kernel_call将信息传递到内核层，在内核层对进程结构体增加 deadline成员。

应用层

从应用层用_syscall将信息传递到服务层，用户调用 chrt 系统调用，将 deadline 传入到服务层。需要添加的系统调用chrt可以定义在unistd头文件中， 并在libc中添加chrt函数体实现 。

  1. 在/usr/src/include/unistd.h 中添加chrt函数定义(直接添加函数定义即可)。
1
int chrt(long );
  1. 在/usr/src/minix/lib/libc/sys/chrt.c中添加chrt函数实现，用alarm函数实现超时强制终止。参照该文件夹下fork.c文件，在实现中通过_syscall(调用号)传递到服务层。

**_syscall(PM_PROC_NR,PM_CHRT,&m)**中调用的服务为将 deadline 放入消息结构体，由于deadline存的数据类型为long，所以在message消息结构体中寻找long型，利用vscode寻找得到message结构体定义在/usr/src/minix/include/minix/ipc.h中，m2l1为结构体中的long类型，且查找到#define m2_l1 m_m2.m2l1宏定义，因此将deadline存入m2_l1。

​ 截屏2022-04-16 上午10.46.37

注：加上当前时间是要记录进程终止时间赋值给 deadline，保证每次调用的进程是当前剩余运行时间最少的。

chrt函数实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <sys/cdefs.h>
#include "namespace.h"
#include <lib.h>

#include <string.h>
#include <unistd.h>
#include <stdio.h>
#include <time.h>

int chrt(long deadline){
    struct timeval tv;//使用来获得时间
    struct timezone tz;//是用来获得时区
    message m;
    memset(&m,0,sizeof(m));
    //设置alarm
    alarm((unsigned int)deadline);
    if(deadline>0){
    gettimeofday(&tv,&tz);//用来获取当前的时间的函数
    deadline = tv.tv_sec + deadline; 
    }
    //存deadline
    m.m2_l1=deadline;
  	//把m传到服务层当中去
    return(_syscall(PM_PROC_NR,PM_CHRT,&m));
}
  1. 在/usr/src/minix/lib/libc/sys中 Makefile.inc文件添加chrt.c条目
截屏2022-04-16 上午10.30.01

每一次添加C文件后，要在同目录下Makefile.inc中添加条目。

服务层

需要向MINIX系统的进程管理服务中注册chrt，使得 chrt服务可以向应用层提供deadline 。

  1. 在/usr/src/minix/servers/pm/proto.h中添加do_chrt函数定义。
1
int do_chrt(void);
  1. 在/usr/src/minix/servers/pm/chrt.c中添加do_chrt函数，do_chrt 的功能是调用 sys_chrt()函数，属于内核调用，who_p 是传递进程号，消息结构体传递 deadline 内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include"pm.h"
#include<minix/syslib.h>
#include<minix/callnr.h>
#include<sys/wait.h>
#include<minix/com.h>
#include <minix/vm.h>
#include "mproc.h"
#include <sys/ptrace.h>
#include <sys/resource.h>
#include <signal.h>
#include <stdio.h>
#include<minix/sched.h>
#include <assert.h>
int do_chrt()
{
  // who_p 是用来获取进程信息的，类型是endpoint_t;m_in.m2_l1就是deadline
    sys_chrt(who_p, m_in.m2_l1); 
    return (OK);    //OK宏定义为0
}
  1. 在/usr/src/minix/include/minix/callnr.h中定义PM_CHRT编号，用来帮助应用层的系统调用能找到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* Message type 0 is traditionally reserved. */
#define PM_EXIT			(PM_BASE + 1)
#define PM_FORK			(PM_BASE + 2)
#define PM_WAITPID		(PM_BASE + 3)
#define PM_GETPID		(PM_BASE + 4)
#define PM_SETUID		(PM_BASE + 5)
#define PM_GETUID		(PM_BASE + 6)
#define PM_STIME		(PM_BASE + 7)
#define PM_PTRACE		(PM_BASE + 8)
#define PM_SETGROUPS		(PM_BASE + 9)
#define PM_GETGROUPS		(PM_BASE + 10)
#define PM_KILL			(PM_BASE + 11)
#define PM_SETGID		(PM_BASE + 12)
#define PM_GETGID		(PM_BASE + 13)
#define PM_EXEC			(PM_BASE + 14)
#define PM_SETSID		(PM_BASE + 15)
#define PM_GETPGRP		(PM_BASE + 16)
#define PM_ITIMER		(PM_BASE + 17)
#define PM_GETMCONTEXT		(PM_BASE + 18)
#define PM_SETMCONTEXT		(PM_BASE + 19)
#define PM_SIGACTION		(PM_BASE + 20)
#define PM_SIGSUSPEND		(PM_BASE + 21)
#define PM_SIGPENDING		(PM_BASE + 22)
#define PM_SIGPROCMASK		(PM_BASE + 23)
#define PM_SIGRETURN		(PM_BASE + 24)
#define PM_SYSUNAME		(PM_BASE + 25)
#define PM_GETPRIORITY		(PM_BASE + 26)
#define PM_SETPRIORITY		(PM_BASE + 27)
#define PM_GETTIMEOFDAY		(PM_BASE + 28)
#define PM_SETEUID		(PM_BASE + 29)
#define PM_SETEGID		(PM_BASE + 30)
#define PM_ISSETUGID		(PM_BASE + 31)
#define PM_GETSID		(PM_BASE + 32)
#define PM_CLOCK_GETRES		(PM_BASE + 33)
#define PM_CLOCK_GETTIME	(PM_BASE + 34)
#define PM_CLOCK_SETTIME	(PM_BASE + 35)
#define PM_GETRUSAGE		(PM_BASE + 36)
#define PM_REBOOT		(PM_BASE + 37)
#define PM_SVRCTL		(PM_BASE + 38)
#define PM_SPROF		(PM_BASE + 39)
#define PM_CPROF		(PM_BASE + 40)
#define PM_SRV_FORK		(PM_BASE + 41)
#define PM_SRV_KILL		(PM_BASE + 42)
#define PM_EXEC_NEW		(PM_BASE + 43)
#define PM_EXEC_RESTART		(PM_BASE + 44)
#define PM_GETEPINFO		(PM_BASE + 45)
#define PM_GETPROCNR		(PM_BASE + 46)
#define PM_GETSYSINFO		(PM_BASE + 47)
#define PM_CHRT             (PM_BASE + 48)
#define NR_PM_CALLS		49	/* highest number from base plus one */
  1. 在/usr/src/minix/servers/pm/Makefile中添加chrt.c条目。
截屏2022-04-16 上午11.11.04
  1. 在/usr/src/minix/servers/pm/table.c 中调用映射表。
截屏2022-04-16 上午11.14.54
  1. 在/usr/src/minix/include/minix/syslib.h 中添加sys_ chrt () 定义。
1
int sys_chrt(endpoint_t proc_ep,long deadline);

  1. 在/usr/src/minix/lib/libsys/sys_chrt.c 中添加sys_chrt () 实现。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include "syslib.h"

    int sys_chrt(proc_ep,deadline)
    endpoint_t proc_ep;		/* process doing the chrt */
    long deadline;      /*set the deadline*/
    {
    /* A process got the deadline. Tell the kernel. */
        message m;
      int r;
      m.m2_i1 = proc_ep;//int
      m.m2_l1 = deadline;//long

      r = _kernel_call(SYS_CHRT, &m);
      //和syscall一样，通过SYS_CHRT和do_chrt的映射，把message传入内核层并调用do_chrt修改进程信息
      return r;
    }

  2. 在/usr/src/minix/lib/libsys 中的Makefile中添加sys_chrt.c条目。

截屏2022-04-16 上午11.19.42

内核层

在MINIX内核中实现进程调度功能，此处可以直接修改内核信息，例如进程的截至时间。

  1. 在/usr/src/minix/kernel/system.h中添加do_chrt函数定义。
1
2
3
4
int do_chrt(struct proc * caller, message *m_ptr);
#if ! USE_CHRT
#define do_chrt NULL
#endif
  1. 在/usr/src/minix/kernel/system/do_chrt.c中添加do_chrt函数实现。参考该文件下的do_fork文件，修改调用者进程信息。
1
2
pid_t fork(void) {
	return(_syscall(PM_PROC_NR, PM_FORK, &m)); }

用消息结构体中的进程号，通过 proc_addr 定位内核中进程地址，然后 将消息结构体中的 deadline 赋值给该进程的deadline(这里已经在 proc 头文件中添加了该成员变量)。

  1. 在/usr/src/minix/kernel/system/ 中Makefile.inc文件添加do_chrt.c条目。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "kernel/system.h"
#include "kernel/vm.h"
#include <signal.h>
#include <string.h>
#include <assert.h>

#include <minix/endpoint.h>
#include <minix/u64.h>
int do_chrt(struct proc *caller, message *m_ptr)
{
    struct proc *rp;
    long exp_time;
    exp_time = m_ptr->m2_l1;
    //通过 proc_addr 定位内核中进程地址
    rp = proc_addr(m_ptr->m2_i1);
    //将消息结构体中的deadline 赋值给该进程的deadline(结构体中的)
    rp->deadline = exp_time;
    return (OK);
}
  1. 在/usr/src/minix/include/minix/com.h中定义SYS_CHRT编号。
截屏2022-04-16 下午5.01.51
  1. 在/usr/src/minix/kernel/system.c 中添加SYS_CHRT编号到do_chrt的映射。
截屏2022-04-10 上午9.40.00
  1. 在/usr/src/minix/commands/service/parse.c的system_tab中添加名称编号对。
截屏2022-04-16 下午5.05.49
  1. 在 /usr/src/minix/kernel/config.h中添加 USE_CHRT
1
2
3
4
#define USE_CHRT 	 1
/* It allows to set sizes of some
 * kernel buffers and to enable or disable debugging code, timing features, 
 * and individual kernel calls.*/

进程调度

MINIX3使用一种多级调度算法。进程优先级数字越小，优先级越高， 根据优先级不同分成了16个可运行进程队列。每个队列内部采用时间片轮转调度，找到最高非空优先级队列，选取队列首部可运行的进程， 当用完了时间片，则移到当前队列的队尾(详见教材P124)。

将EDF添加到多级调度算法中，可控制入队实现实时调度。入队是将当前剩余时间(终止时间-运行 时间)大于0的进程添加到某个优先级队列，即设置进程优先级(需要选择合适的优先级，否则执行效果不理想)。

在该队列内部将时间片轮转调度改成==剩余时间最少优先调度==，即将剩余时间最小的进程移到队列首部。

进程调度模块位于/usr/src/minix/kernel/下的proc.h和proc.c，修改影响进程调度顺序的部分。

  1. structproc维护每个进程的信息，用于调度决策。添加deadline成员。（ 其实按照minix3的代码风格，这里应该将ddl定义为p_deadline，实验更改的时候疏忽了，就直接定义为deadline了。）截屏2022-04-16 下午5.14.32
  2. enqueue_head()按优先级将进程加入列队首。实验中需要将实时进程的优先级设置成合适的优先级。enqueue()按优先级将进程加入列队尾，同上。

​ 经过尝试，将设置过deadline的进程优先级设置为5、6均可获得理想的执行结果。其中原因为：minix3中默认优先级为0-4的进程大多为系统进程，非用户进程。故设置优先级为5、6时已经可以得到理想的执行结果。

截屏2022-04-16 下午5.20.32 截屏2022-04-16 下午5.21.01

注：由于在这个地方踩坑，编译可成功，可执行文件却无法运行，我debug了两天才找到真正的错误。由于deadline大于0时要指定rp的优先级为5，而初始代码将p_priority定义为了const常量，将优先级设置放在其后会出现错误，一定要在其之前设置优先级。

  1. pick_proc()从队列中返回一个可调度的进程。遍历设置的优先级队列，返回剩余时间最小并可运行的进程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*===========================================================================
 *				pick_proc				     * 
 *=========================================================================*/
static struct proc * pick_proc(void)
{
/* Decide who to run now.  A new process is selected an returned.
 * When a billable process is selected, record it in 'bill_ptr', so that the 
 * clock task can tell who to bill for system time.
 *
 * This function always uses the run queues of the local cpu!
 */
  register struct proc *rp;			/* process to run */
  struct proc **rdy_head;
  int q;				/* iterate over queues */
	register struct proc *next; // 中间变量,用来指代下一个进程
  /* Check each of the scheduling queues for ready processes. The number of
   * queues is defined in proc.h, and priorities are set in the task table.
   * If there are no processes ready to run, return NULL.
   */
  rdy_head = get_cpulocal_var(run_q_head);
  for (q=0; q < NR_SCHED_QUEUES; q++) {	
	if(!(rp = rdy_head[q])) {
		TRACE(VF_PICKPROC, printf("cpu %d queue %d empty\n", cpuid, q););
		continue;
	}
	rp = rdy_head[q];
    next = rp->p_nextready;/* pointer to next ready process */
	if (q == 5) 
	{ /* 如果优先级等于5，说明可能是设置deadline的进程，找剩余时间最小的进程*/
        while (next != NULL) 
				{//遍历进程
            if (next->deadline > 0) 
						{ 
				/* 交换这两个进程，得到剩余时间最短的进程。*/
                if (rp->deadline == 0 || (rp->deadline > next->deadline))
								{
                    if (proc_is_runnable(next)) //判断是否在运行
											rp = next;
                }
            }
          /* 比下一个 */
          next = next->p_nextready;
        }
    }
	assert(proc_is_runnable(rp));
	if (priv(rp)->s_flags & BILLABLE)	 	
		get_cpulocal_var(bill_ptr) = rp; /* bill for system time */
	return rp;
  }
  return NULL;
}

实验结果

测试用例如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <signal.h>
#include <sys/wait.h>
#include <sys/types.h>
#include <lib.h>
#include <time.h>

void proc(int id);
int main(void)
{
  //创建三个子进程，并赋予子进程id
  for (int i = 1; i < 4; i++)
  {
    if (fork() == 0)
    {
      proc(i);
    }
  }
  return 0;
}
void proc(int id)
{
  int loop;
  switch (id)
  {
  case 1: //子进程1，设置deadline=25
    chrt(25);
    printf("proc1 set success\n");
    sleep(1);
    break;
  case 2: //子进程2，设置deadline=15
    chrt(15);
    printf("proc2 set success\n");
    sleep(1);
    break;
  case 3: //子进程3，普通进程
    chrt(0);
    printf("proc3 set success\n");
    break;
  }
  for (loop = 1; loop < 40; loop++)
  {
    //子进程1在5s后设置deadline=5
    if (id == 1 && loop == 5)
    {
      chrt(5);
      printf("Change proc1 deadline to 5s\n");
    }
    //子进程3在10s后设置deadline=3
    if (id == 3 && loop == 10)
    {
      chrt(3);
      printf("Change proc3 deadline to 3s\n");
    }
    sleep(1); //睡眠，否则会打印很多信息
    printf("prc%d heart beat %d\n", id, loop);
  }
  exit(0);
}

运行结果:P1和P2为实时进程，deadline分别设为25s和15s。第0秒，优先级P2>P1>P3；第5秒，P1剩5s，P2剩10s，优先级P1>P2>P3；第10s，P2剩5s，P3剩3s,优先级P1>P2>P3。

截屏2022-04-16 下午6.54.44

总结

由于minix 的不同服务模块和内核运行在不同进程中，我在这个实验中熟悉了基于消息的进程间系统调用，在实践中对minix操作系统内部的调度算法理解得更为深入，也看到了操作系统各层之间、文件之间定义等关系。整个实验的实现过程还是需要很多耐心和理解的，稍微不慎就会使耗时很久的编译失败，我也用了很长时间在查找错误、修改错误。所以，在这个过程中更体会到了及时备份保存，利用好git diff工具检查代码修改等的重要性，学习到了很多。感谢助教们的解答和同学们的帮助。