操作系统Project2:Chrt系统调用和EDF算法


阅读数: 次   

操作系统Project2:Chrt系统调用和EDF算法

实验任务

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

1.增加系统调用chrt

2.修改MINIX3.3的调度算法

排版好累!!!!!

实验过程

整体思路:

类比于其它系统调用(fork)增加一个名为chrt的系统调用,这个系统调用同时为调用chrt的进程设置一个闹钟,同时这个系统调用通过_sys_call和_kernel_call向内核传递deadline信息;

同时修改MINIX的调度算法,将调用chrt的进程的优先级设置为一个较高的合适的优先级,但不能是0优先级等,因为这样会和系统进程产生调度冲突;当这些调用chrt进程的优先级被设置较高时,与其余未调用chrt的进程或deadline=0的普通进程比,因为享有较高优先级,所以被优先调度;

在设置了较高优先级队列的实时进程队列中,遍历整个队列,将原先的时间片轮转调度修改为离deadline最近的进程被置于队首被优先调度;

同时需要注意的是对离“deadline最近”这一概念的表达

设置deadtime=nowtime(调用chrt的时刻)+deadline(实际秒数);

将deadtime作为参数,实际参与从应用层的传递;

deadtime的理解是:deadtime反映了从调用chrt的时刻起,进程的结束调用时刻,所以只需要比较各个进程间的进程结束调用时刻,当调用时刻越早,即从数值上来看越小时,说明该进程越需要被优先调度;同时,即使是在后续deadtime时间内同一进程再次调用chrt修改了进程的deadtime时间,也是实时修改了进程的结束调用时刻;

1. 增加系统调用chrt

int chrt(long deadline);*

该系统调用实现的功能:

a. \Deadline=0,为普通进程,priority比实时进程的优先级低;**

b. \Deadline>0,为实时进程,即该进程需要在******在deadline秒内结束.如果到达进程结束时间点时该进程仍然没有结束,则超过时间强制停止该进程;****

\支持在进程的deadline时间内进行多次调用chrt修改deadline;**

c. \Deadline<0;直接返回不成功;**

img

在MINIX3中,用户进程发出的系统调用将被转换为发往服务器进程的消息;由服务器进程给系统任务进程发消息,由系统任务进程完成剩下的工作;

由系统任务接受的消息类型:

这里sys_chrt对应POSIX系统调用,属于进程管理类;

系统函数库:在系统任务主程序system.c中每一个名字为do_xyz 形式的函数的源码在kernel/system/do_xyz.c文件中;在system.c中也添加响应编号的映射;

MINIX3操作系统本身是由许多进程组成,这些系统进程之间通过消息传送机制相互通信,用户进程也可以通过消息传送机制与操作系统进程之间通信,从而请求操作系统的服务;

2. \在MINIX操作系统下增加系统调用的流程:**

img

如上述流程图所示,分别从应用层,服务层,内核层进行系统调用;

A. \内核层:**

\usr/src/minix/kernel/system.h,system.c:系统任务的总框架;**

\usr/src/minix/kernel/system/:包含了每个响应函数的源文件;**

\内核层需要实现的内容如下:**

\改内核信息，例如进程的截至时间。**

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

q 在/usr/src/minix/kernel/system/do_ chrt.c中添加do_chrt函数实现。参

考该文件下的do_fork文件，修改调用者进程信息。例如：

pid_t fork(void)

{

return(_syscall(PM_PROC_NR, PM_FORK, &m));

}

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

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

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

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

内核层do_chrt.c的具体实现:

int do_chrt(struct proc *caller, message *m_ptr)

{

struct proc *rp;

long deadline;

deadline = m_ptr->m2_l1;

rp = proc_addr(m_ptr->m2_i1);/获得调用chrt的进程的proc结构/

rp->p_deadline = deadline;

return (OK);

}

注意这里的消息结构体:m2_l1表示进程的deadline,m2_i1表示进程是哪个进程;

消息结构体在各层逻辑相同;

B. \服务层:**

\PM服务实现进程的创建,启动与终止等系统调用;**

. 服务层：需要向MINIX系统的进程管理服务中注册chrt，使得

chrt服务可以向应用层提供 。

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

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

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

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

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

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

q 在/usr/src/minix/lib/libsys/sys_chrt.c 中添加\sys_chrt ()** 实现。可参照

该文件夹下的sys_fork文件，在实现中通过_kernel_call (调用号)向

内核传递。例如：

int sys_fork(parent, child, child_endpoint, flags, msgaddr)

{

\_kernel_call(SYS_FORK, &m);**

}

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

这里chrt.c调用sys_chrt.c,

Sys_chrt.c在服务层需要像内核传递信息,信息是m2_i1和m2_l1;

//声明风格模仿sys_fork.c

int sys_chrt(who, deadline)

long deadline;

endpoint_t who;

{

message m;

m.m2_l1=deadline;

m.m2_i1=who;

return _kernel_call(SYS_CHRT,&m);

}

C. \应用层:**

应用层：需要添加的系统调用chrt可以定义在unistd头文件中，

并在libc中添加chrt函数体实现 。

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

q 在/usr/src/minix/lib/libc/sys/chrt.c中添加chrt函数实现。可用alarm函

数实现超时强制终止。参照该文件夹下fork.c文件，在实现中通过

_syscall (调用号)向系统服务传递。例如：

pid_t fork(void)

{

return(_syscall(PM_PROC_NR, PM_FORK, &m));

}

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

C文件后，需在同目录下的Makefile/Makefile.inc中添加条目）。

int chrt(long deadline)

{

struct timespec time;

message m;

memset(&m, 0, sizeof(m));

alarm((unsigned int)deadline);

if(deadline<0)

return 0;

if(deadline>0){

clock_gettime(CLOCK_REALTIME,&time);

deadline =time.tv_sec+deadline;//nowtime+deadline;

}

m.m2_l1=deadline;

return(_syscall(PM_PROC_NR, PM_CHRT, &m));//在消息结构体中将deadline放入

}

3. \修改系统调度算法,模拟EDF:early-deadline-first的近似实时调度:**

A. \MINIX系统的进程调度方式:**

n MINIX3使用一种多级调度算法。进程优先级数字越小，优先级越高，

根据优先级不同分成了16个可运行进程队列。每个队列内部采用时间片轮转调度，找到最高非空优先级队列,选取队列首部可运行的进程,当用完了时间,则移到当前队列的队尾.

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

n 在该队列内部将时间片轮转调度改成剩余时间最少优先调度，即将剩

余时间最小的进程移到队列首部。

具体代码修改思路:

1.修改proc.h为进程结构体增加deadline(deadtime)信息;

2.修改enqueue()将进程加入至队尾函数,对于deadtime>0(即实时进程,设置优先级为5);

3.修改enqueue_head()将进程加入至队首函数,对于deadtime>0(即实时进程,设置优先级为5);

4.修改pick_proc()函数,对于之前设置的优先级5的队列,在该队列中进行进程调度时,从队列中返回一个可调度的进程,遍历设置的优先级队列，返回\剩余时间最小******(deadtime)*并*可运行****的进程.

Proc.c中代码如下

if(q==5){//对于特殊的优先级队列

rp=rdy_head[q];//rp是当前队首的第一个

tmp=rp->p_nextready;//待调队列队首的下一个,实质承载遍历

while(tmp!=NULL){//tmp非空才有遍历的价值

if(tmp->p_deadline>0){//当下一个不为0的时候:

if(rp->p_deadline==0)&&proc_is_runnable(tmp))//如果队首进程是普通进程,注意这里不意味着优先级为5一定是实时进程;

rp=tmp;

else if(rp->deadline>tmp->deadline)&&proc_is_runnable(tmp))

rp=tmp;//deadtime早的享有优先调度的权利;

}

}

tmp=tmp->p_nextready;

}

}

4. \测试**

在测试中，在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;

测试代码如下:

void proc(int id);

int main(void)

{

//创建三个子进程，并赋予子进程id

for (int i = 0; i < 3; i++)

{

if (fork() == 0)

{

proc(i);

}

}

return 0;

}

void proc(int id)

{

int loop;

switch (id)

{

case 0: //子进程1，设置deadline=20

chrt(20);

printf(“proc1 set success\n”);

sleep(1);

break;

case 1: //子进程2，设置deadline=15

chrt(15);

printf(“proc2 set success\n”);

sleep(1);

break;

case 2: //子进程3，普通进程

chrt(0);

printf(“proc3 set success\n”);

break;

}

for (loop = 1; loop < 40; loop++)

{

sleep(1); //睡眠，否则会打印很多信息

printf(“prc%d heart beat %d\n”, id+1, loop);

}

exit(0);

}

img

\利用测试样例测试结果如上图所示;**

\通过git diff 工具可得,最终修改的minix系统src文件如下,被修改的文件在上述思维导图结构中已经给出:**

1.****内核层:****

Src/minix/kernel/proc.h

Src/minix/kernel/proc.c

Src/minix/kernel/system/system.h

Src/minix/kernel/system/do_chrt.c

Src/minix/kernel/system/Makefile.inc

Src/minix/kernel/commands/service/parse.c

2.****服务层****

Src/minix/servers/pm/proto.h

Src/minix/servers/pm/table.c

Src/minix/servers/pm/chrt.c

Src/minix/servers/pm/Makefile.inc

Src/minix/lib/libsys/sys_chrt.c

Src/minix/lib/libsys/Makefile.inc

Src/minix/include/minix/callnr.h

Src/minix/include/minix/syslib.h

Src/minix/include/minix/com.h

3.****应用层****

Src/include/unistd.h

Src/minix/lib/libc/sys/chrt.c

Src/minix/lib/libc/sys/Makefile.inc

五、 \总结**

赏

谢谢你请我吃糖果❤️

支付宝

扫一扫，分享到微信

微信分享二维码
本站总访问量次

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br><br>个人随笔笔记为主<br>有很多不足<br>谢谢大家～<br><br>可以搜索我的微信号联系我：Habseligkeit030<br><br><br>也可以给我发邮件xinning_chi@163.com