操作系统lab2-chrt

Author Avatar
MorphLing 5月 30, 2021

内容与设计思想

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

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

实验过程

应用层

  • 在/usr/src/include/unistd.h 中添加chrt函数定义

img

  • 在/usr/src/minix/lib/libc/sys/chrt.c中添加chrt函数实现。

此处修改deadline值，将当前时间戳+deadline，即进程结束的绝对时间作为新的deadline值向下传递，作为进程调度决策的参数。

img

  • 在/usr/src/minix/lib/libc/sys中Makefile.inc文件添加chrt.c条目

img

服务层

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

img

  • 在/usr/src/minix/servers/pm/chrt.c中添加chrt函数实现，调用sys_chrt()。

img

  • 在/usr/src/minix/include/minix/callnr.h中定义PM_CHRT编号。

img

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

img

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

img

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

img

  • 在/usr/src/minix/lib/libsys/sys_chrt.c 中添加sys_chrt () 实现。可参照该文件夹下的sys_fork文件，在实现中通过_kernel_call (调用号)向内核传递。

img

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

img

内核层

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

img

  • 在/usr/src/minix/kernel/system/do_chrt.c中添加do_chrt函数实现。

img

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

img

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

img

  • 在/usr/src/minix/include/minix/com.h中定义SYS_CHRT编号。

img

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

img

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

img

进程调度

  • 修改/usr/src/minix/kernel/proc.h在struct proc中添加p_deadline成员。

img

  • 修改/usr/src/minix/kernel/proc.c中enqueue_head()和enqueue()函数，在实时进程入队时设置优先级为5。

img

img

  • 修改/usr/src/minix/kernel/proc.c中pick_proc()函数，选择进程时遍历队列，优先选择最先中止运行的进程

img

测试

测试程序：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <signal.h>

void proc(int id);
int main(void) {
  for (int i = 0; i < 3; i++) {
​    if (fork() == 0) {
​      proc(i + 1);
​    }
  }
  return 0;
}
void proc(int id) {
  int loop;
  switch(id) {
​    case 1:
​      chrt(20);
​      printf("proc1 set success\n");
​      sleep(1);
​      break;
​    case 2:
​      chrt(15);
​      printf("proc2 set success\n");
​      sleep(1);
​      break;
​    case 3:
​      chrt(0);
​      printf("proc3 set success\n");
​      sleep(1);
​      break;
  }
  for (loop = 1; loop < 30; loop++) {
​    if (id == 1 && loop == 5) {
​      chrt(5);
​      printf("Change proc1 deadline to 5s\n");
​    }
​    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);
}

运行结果：

img

第一阶段P1、P2为实时进程，P3为用户进程，优先级P2>P1>P3

第二阶段P1、P2、P3都为实时进程，优先级P1>P2>P3

第三阶段P1进程结束，P2、P3为实时进程，优先级P3>P2，符合预期

总结

MINIX系统调用机制包含三层：应用层、服务层和内核层，层与层之间通过message传递消息。该实验本质上是将进程的deadline通过message逐层传递至内核层，并用deadline值进行进程调度决策。

在修改MINIX3内核过程中遇到了一些问题并分别尝试解决如下：

  • git clone在不同操作系统下不同的换行符（CRLF或LF）

    我采用的编写方式是先将原来的MINIX3源码clone到windows10系统下，在本地修改后再将修改后的文件通过ssh传输到虚拟机。

    但是git clone在windows系统和MINIX系统下文件的换行符有区别，windows下为CRLF，MINIX下为LF，这导致两边的文件不一致，编译时会报错。

    参考解决方案：https://stackoverflow.com/questions/5834014/lf-will-be-replaced-by-crlf-in-git-what-is-that-and-is-it-important

    在windows系统git中设置后使得windows系统下换行符也为LF。

    设置命令：

     git config --global core.autocrlf false

  • 编译过程中遇到permission denied问题

    通过chmod修改文件权限后解决

  • 进程调度时，实时进程的优先级设置范围问题

    实时进程的优先级设置不能过高，也不能过低。小于等于3时，可能会被视作系统进程和内核进程；大于等于7时，优先级可能会小于非实时进程。这些情况都会导致调度不能正确实现。经过了解和测试后选择实时进程优先级为5时可以正确实现。