《自己动手写操作系统》第六章:进程调度

时间:2021-11-13 14:36:26

    摘要:进程和任务都有轻重缓急之分,如何让高优先级别的进程能够获得很好的CPU权限?进程调度方面有很多算法——时间片轮转算法、绝对优先级算法、动态有限级算法、短作业优先算法等。本文,我们将结合实践篇轮转算法实现一种绝对优先级算法。


1.固定非等比例下的延迟

    我们来修改A、B、C三个进程的延迟:
 
75  *======================================================================*/
 76 void TestA()
 77 {
 78     while(1){
 79         disp_str("A.");
 80         milli_delay(300);B、C对应改成900和1500
 81     }
 82 }
        这样以后,打印出来A、B、C的个数是181:65:39.我们来分析一下这个比例:很显然,这里面的延迟指令实际上是靠CPU执行一系列指令来实现的,milli_delay(300)我们可以理解成300条nop指令。也就是说,循环体的长度与时间成正比。假设每隔30条指令,触发依次时钟中断,那么A、B、C程序执行一个循环被中断的次数是10、30、50,而每次中断,程序控制权就会转交到下一个进程。可以估算,循环内中断越多,被打印的次数越少,但为什么不是1:3:5的比例呢?我们可以这样理解,每次中断,打印的字符个数分别为:1/10;1/30/;1/50也就是15:5:3,这样看来倒是比较符合我们的比例。

2.利用延迟,实现优先级别

    想一想,优先级的调度本来应该在调度函数中实现,如果我们在调度函数中能够设计成这样:以每次中断为一个时间片,给A、B、C分别分配150、50、30个时间片,先运行A,150个时间片之后,运行B.....等到C也运行完毕的时候,重新运行A,150个时间片之后....
    为了实现我们的设想,需要做哪些改动呢?
首先,进程结构体中我们要增加两个int 类型的变量,remained_tricks,表示剩下的时间片;priority 表示优先级对应的时间片个数。需要做对应的初始化工作。
    对于进程调度,我们单独写一个函数schedule(),放在proc.c之中:
 20 PUBLIC void schedule()
 21 {
 22     p_proc_ready->ticks--;//注意,我们将cloc.c中的这句,移动到了schedule函数之中,从而防止中断重入问题;要删掉对应clock.c中的这句
 23     PROCESS*    p;
 24     int     greatest_priority = 0;
 25     if(p_proc_ready->ticks>0)
 26     {   
 27         return ;//ticks not used out
 28     }   
 29     
 30     while (1==1) {//current tickes used out
 31         for (p=proc_table; p<proc_table+NR_TASKS; p++) {//find the max priority which ticks !=0
 32             if(p->ticks<=0)
 33                 continue;
 34             if (p->priority > greatest_priority) {
 35                 greatest_priority = p->priority; 
 36                 p_proc_ready = p; 
 37                 return ;
 38             }   
 39         }   
 40         //ticks=0 for all,not found sth for proc_ready
 41         if (p_proc_ready->ticks<=0) {
 42             for (p=proc_table; p<proc_table+NR_TASKS; p++) {
 43                 p->ticks = p->priority;
 44             }   
 45         }   
 46         else//find the p which ticks not = 0
 47             return ;
 48     }       
 49 }   
    对于时钟中断:每次时钟中断,对应进程的时间片-1.
    对于进程体:我们将延迟改为10ms

统计一下最后的输出结果

[huangyk@huangyk i]$ cat snapshot.txt | sed -e 's/\([ABC]\)\./\1\n/g'|sort | grep C | wc -l

94
[huangyk@huangyk i]$ cat snapshot.txt | sed -e 's/\([ABC]\)\./\1\n/g'|sort | grep B | wc -l
152
[huangyk@huangyk i]$ cat snapshot.txt | sed -e 's/\([ABC]\)\./\1\n/g'|sort | grep A | wc -l
754

注意:orange上的这一节实际上有严重的bug,因为考虑到中断重入问题,我们不能用tick==0来判断时间片是否用完!由于中断重入,加上tick--放在了clock函数之中,这样会导致tick编程0xFFFF****等数值,最终出错。如果将延迟从10ms改动到100ms或者1000ms,你将能很明显观测到这个错误。