os-Project2

Posted on
Words count in article: 3.5k | Reading time ≈ 14

Project2 进程调度

实验要求

在MINIX3中实现 Earlist-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

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

应用层

需要添加的系统调用chrt可以定义在unistd头文件中，并在libc中添加chrt函数体实现。

  • 在/usr/src/include/unistd.h中添加chrt函数定义
1
2
3
//...
int chrt(long);
//...

这里我犯了一个很愚蠢的错误，一开始我写的是 int char(long deadline)，虽然kernel编译成功但是在编译test.c 的时候却始终找不到chrt 函数，经过修改后排除错误

  • 在/usr/src/minix/lib/libc/sys/chrt.c中添加chrt函数实现。可用alarm函数实现超时强制终止。参照该文件夹下fork.c文件，在实现中通过_syscall(调用号)向系统服务传递。例如：
1
2
3
pid_t fork(void){
	return(_syscall(PM_PROC_NR, PM_FORK, &m));
}

chrt.c如下图所示：

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 <stdio.h>
#include <string.h>
#include <unistd.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);
    //将当前时间记录下来 算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));
}

timeval 使用来获得时间的

timezone 是用来获得时区的

gettimeofday 用来获取当前的时间的函数，包含在头文件 #include <sys/time.h> 中

_syscall函数可以用来查找系统调用。PM_PROC_NR 将会用来存放PM_CHRT的系统调用号，

  • 在/usr/src/minix/lib/libc/sys中 Makefile.inc文件添加chrt.c条目（添加C文件后，需在同目录下的Makefile/Makefile.inc中添加条目）

服务层：

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

  • 在/usr/src/minix/servers/pm/proto.h中添加do_chrt函数定义。

因为 do_chrt 的功能是调用 sys_chrt()函数，并不需要传入参数，所以这里写void

  • 在/usr/src/minix/servers/pm/chrt.c中添加chrt函数实现，调用sys_chrt()
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;
}
  • 在/usr/src/minix/include/minix/callnr.h中定义PM_CHRT编号。用来帮助应用层的系统调用能找到

我一开始没有定义 PM_CHRT 的编号，导致 make build 的时候总是报告称error: use of undeclared identifier 'PM_CHRT'

  • 在/usr/src/minix/servers/pm/Makefile中添加chrt.c条目。

  • 在/usr/src/minix/servers/pm/table.c中调用映射表。

  • 在/usr/src/minix/include/minix/syslib.h中添加sys_chrt()定义。

  • 在/usr/src/minix/lib/libsys/sys_chrt.c中添加sys_chrt ()实现。可参照该文件夹下的sys_fork文件，在实现中通过_kernel_call (调用号)向内核传递。例如：
1
2
3
int sys_fork(parent, child, child_endpoint, flags, msgaddr){
	_kernel_call(SYS_FORK, &m);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "syslib.h"
// 目的就是把进程和deadline提取出来，然后调用 kernel_call() 传入内核
int sys_chrt(proc_ep, deadline)
endpoint_t proc_ep;
long deadline;
{
    message m;
    int r;
    m.m2_i1 = proc_ep; //m2_i1 支持传送一个 int 类型的数据
    m.m2_l1 = deadline; // m2_l1 支持传送一个long 类型的数据
  //和syscall一样，这里通过SYS_CHRT和do_chrt的映射，把message传入内核层并调用do_chrt修改进程信息
    r=_kernel_call(SYS_CHRT, &m);
    return r;
}、
  • 在/usr/src/minix/lib/libsys中的Makefile中添加sys_chrt.c条目。

内核层

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

  • 在/usr/src/minix/kernel/system.h中添加do_chrt函数定义。

  • 在 /usr/src/minix/kernel/config.h中添加 USE_CHRT

踩坑：这一步虽然在实验说明中没有写，但是我们要加上去。否则在编译 测试文件的时候会报错

  • 在/usr/src/minix/kernel/system/do_chrt.c中添加do_chrt函数实现。参考该文件下的do_fork文件，修改调用者进程信息。例如：
1
2
3
pid_t fork(void){
	return(_syscall(PM_PROC_NR, PM_FORK, &m));
}
do_chrt.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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>

#if USE_CHRT

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 赋值给该进程的 p_deadline
    rp->deadline = exp_time;
    return (OK);
}

#endif /* USE_CHRT */
  • 在/usr/src/minix/kernel/system/中Makefile.inc文件添加do_chrt.c条目。

  • 在/usr/src/minix/include/minix/com.h中定义SYS_CHRT编号。方便Kernel_Call找到SYS_CHRT函数。

  • 在/usr/src/minix/kernel/system.c中添加SYS_CHRT编号到do_chrt的映射。

  • 在/usr/src/minix/commands/service/parse.c的system_tab中添加名称编号对。

踩坑：这个文件中有两个struct，一个都是 VM_****,一个都是 SYS_**** ,不要放错，我因为这个调试了很久

Minix3中的进程调度

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

  • 将EDF添加到多级调度算法中，可控制入队实现实时调度（也可有其他新颖方式，得分更高）。入队是将当前剩余时间（终止时间-运行时间）大于0的进程添加到某个优先级队列，即设置进程优先级（需要选择合适的优先级否则执行效果不理想）。

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

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

    proc.h

  • struct proc 维护每个进程的信息，用于调度决策。添加deadline成员。

    利用xcode 可以很清楚得看见 proc 这个结构的内部成员：

    1
    2
    3
    4
    5
    6
    static struct proc * pick_proc(void)
    {	
    	//...	
    	long deadline;
    	//...
    }

    proc.c

  • switch_to_user() 选择进程进行切换。

  • enqueue_head() 按优先级将进程加入列队首。实验中需要将实时进程的优先级设置成合适的优先级。这里我设置成了5。也就是说，当我给进程设置了 deadline 之后，这个实时进程的优先级就会变成5。然后多级调度算法就会发现这个较高的优先级并执行入队操作：

    1
    2
    3
    if(rp->deadline > 0) {
          rp->p_priority = 5;
    }

  • enqueue() 按优先级将进程加入列队尾。同上。

  • 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
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;
      }
    	//这里是新加入的部分
    
 	if (q == 5) { /* 如果优先级等于5，说明可能是设置deadline的进程，下面要找剩余时间最小的进程*/
        rp = rdy_head[q];
        next = rp->p_nextready;
        /* 拿到当前和下一个进程 */
        while (next != NULL) {//遍历进程
            if (next->deadline > 0) { /* 再次判断，防止原本优先级就是7的进程，留下用了chrt的 */
            /* 如果当前的进程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=20
    chrt(20);
    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);
}

输出

编译完成之后，我们把测试用的 test.c文件放到 文件夹下，然后 clang test.c -o test 编译文件 ./test 运行可执行文件，结果如下图所示：

显然这个答案并不是正确的，但是起码在kernel中添加了chrt 函数。第二天我调试了四五个小时(主要时间花在编译上面)，将内核层多次删改后再次尝试，这次成功了：

在测试中，在main函数中fork三个子进程(P1, P2, P3)，并为每个子进程设置id。

P1和P2为实时进程，deadline分别设为20s和15s。

三个子进程会打印出子进程id和循环次数。

第0s时：优先级P2 > P1 > P3;

第5s 时：P1设置deadline为5s，P1调用chrt(5);

第5s后：优先级P1 > P2 > P3;

第10s时：P3设置deadline为3s，P3调用chrt(3);

第10s后：优先级P3 > P2;

n 打印输出信息，观察子进程执行顺序是否正确.

注意事项

  • MINIX的不同服务模块和内核都是运行在不同进程中，只能使用基于消息的进程间系统调用/内核调用，不能使用直接调用普通C函数。
  • 添加调用编号，需要修改取值范围限制。
  • 以源码为准（博客等资料版本落后）。
  • 善用source insight高级功能（调用关系，全局搜索）。
  • 善用git diff 检查代码修改。修改涉及文件较多，git diff可直观看到修改内容，避免引入无意的错误。
  • 善用FileZilla功能。连接虚拟机，拉取需修改的文件，修改后上传到虚拟机。

编译方法

  • cd /usr/src
  • make build #首次编译，或者修改了头文件，Makefile时使用，时间较长。
  • Make build MKUPDATE=yes #增量式编译，适用于少量C源代码修改时使用。
  • reboot #重启，默认情况下自动选择latest kernel（新生成的kernel），需要原始版本时手工选择。

总结

  • 这次实验要求我们修改的东西很多，我的解决步骤是：

    应用层$\longrightarrow$服务层$\longrightarrow$内核层$\longrightarrow$修改进程调度算法

    在每一part做完之后，都会编译一下kernal，如果没有报错，说明修改的代码没有问题

  • 找到效率高的工作流很重要。我的工作软件如下：

    Typora 负责步骤查看和报告撰写

    Terminus 负责用ssh连接虚拟机与命令操作

    Transmit3 负责用ftp连接虚拟机的文件系统，配合xcode 修改代码

    Chrome、Acrobat 用于博客查看与资料查阅

-------------本文结束，感谢您的阅读-------------