计算机操作系统实验_线程调度的优化与控制

西北工业大学 操作系统实验 实验报告

一、实验目的

掌握GeekOS系统的线程调度算法以及线程同步与互斥方法，实现线程调度的优化与控制。

二、实验要求

1. 按照实验讲义P146页中的设计要求，增加线程调度算法的选择策略，使系统可以在时间片轮转调度和四级反馈队列调度之间切换，并且实现四级反馈队列调度算法，给出关键函数的代码以及实验结果。

2. 在GeekOS中实现信号量，使用信号量保证用户程序运行时的线程同步，给出关键函数的代码以及实验结果。

三、实验过程及结果

答：

1、进程间的调度实现：

Get_Next_Runnable代码如下：

struct Kernel_Thread* Get_Next_Runnable(void) { struct Kernel_Thread* best = 0; int i, best_index_queue = -1; if (g_schedulingPolicy == ROUND_ROBIN) { struct Kernel_Thread* best_in_queue = NULL; for (i = 0; i < MAX_QUEUE_LEVEL; i++){ best_in_queue = Find_Best(&s_runQueue[i]); if (best == NULL) { best = best_in_queue; best_index_queue = i; } else if (best_in_queue != NULL){ if (best_in_queue->priority > best->priority) { best = best_in_queue; best_index_queue = i; } }

－1－

}

}

} else if (g_schedulingPolicy == MULTILEVEL_FEEDBACK) { if ( g_currentThread->priority != PRIORITY_IDLE ){ if ( g_currentThread->blocked && g_currentThread->currentReadyQueue > 0 ) g_currentThread->currentReadyQueue--; } for (i = 0; i < MAX_QUEUE_LEVEL; i++){ best = Find_Best(&s_runQueue[i]); best_index_queue = i; if (best != NULL) break; } if ( best->currentReadyQueue < MAX_QUEUE_LEVEL-1 ) best->currentReadyQueue++; }

KASSERT(best != NULL);

Remove_Thread(&s_runQueue[best_index_queue], best); return best;

结果如图：

－2－

2、信号量操作

P、V操作代码如下：

int P(int sid)

{ if(!validateSID(sid)){ return EINVALID; } bool atomic = Begin_Int_Atomic(); if(g_Semaphores[sid].resources == 0){ Wait(&g_Semaphores[sid].waitingThreads); KASSERT(g_Semaphores[sid].resources == 1); } KASSERT(0 < g_Semaphores[sid].resources); g_Semaphores[sid].resources--; End_Int_Atomic(atomic); return 0; }

int V(sid) { if(!validateSID(sid)){ return EINVALID; } bool atomic = Begin_Int_Atomic(); g_Semaphores[sid].resources++; if(g_Semaphores[sid].resources == 1){ Wake_Up_One(&g_Semaphores[sid].waitingThreads);

－3－

} End_Int_Atomic(atomic); return 0; }

修改后的Ping.c代码如下： #include #include #include #include #include

int main(int argc , char ** argv) {

int i,j ; /* loop index */ int scr_sem; /* id of screen semaphore */ int time; /* current and start time */

int ping,pong; /* id of semaphores to sync processes b & c */ time = Get_Time_Of_Day();

scr_sem = Create_Semaphore (\ /* register for screen use */ ping = Create_Semaphore (\ pong = Create_Semaphore (\ for (i=0; i < 5; i++) { P(pong);

for (j=0; j < 35; j++); time = Get_Time_Of_Day() - time; P(src_sem); Print(\ V(src_sem); V(ping); }

time = Get_Time_Of_Day() - time; P (scr_sem) ;

Print (\ V(scr_sem);

Destroy_Semaphore(pong); Destroy_Semaphore(ping); Destroy_Semaphore(scr_sem); return (0); }

修改后的Pong.c代码如下： #include #include

－4－

#include #include #include

int main(int argc , char ** argv) { int i,j ; /* loop index */ int scr_sem; /* id of screen semaphore */ int time; /* current and start time */ int ping,pong; /* id of semaphores to sync processes b & c */ time = Get_Time_Of_Day(); scr_sem = Create_Semaphore (\ /* register for screen use */ ping = Create_Semaphore (\ pong = Create_Semaphore (\ for (i=0; i < 5; i++) { P(ping); for (j=0; j < 35; j++); time = Get_Time_Of_Day() - time; P(src_sem); Print(\ V(src_sem); V(pong); } time = Get_Time_Of_Day() - time; P (scr_sem) ; Print (\ V(scr_sem); return (0); }

结果如图：

－5－

四、实验分析

1.调度：

MLF调度算法的主要思想是系统有多个就绪队列，每个队列对应相应优先级，第一队列的优先级最高，然后优先级逐渐降低。同时给高优先级的任务分配较短的时间片，给低优先级的任务分配较长的时间片。对于同一优先级的任务，采用FCFS调度算法。如果把优先级队列数量降低到一，则MLF算法退化为Round Robin调度算法。

MLF调度算法最大的问题是会导致饥饿问题，因为低优先级的任务有可能会长时间得不到执行，所以在实际的操作系统中，调度器会给长时间未执行的任务动态的提高优先级，避免饥饿现象。

由实验分析可知，在短作业情况下，mlf调度相较于rr缩短了三分之一的执行时间，优越性明显。

2.信号量

信号量的目的是保障进程的同步或互斥，若信号量为1，则确保互斥。因为当争抢一个临界资源时，首先获取到信号量的进程会把信号量减少为0，其余进程请求该资源时候必须要等待该进程释放才能获取。如果信号量为0时，则是保障进程的同步。因为当某一个信号量执行到某一步时，该信号量为0，进程阻塞掉，必须要等待其他的进程增加该信号量才能继续执行，从而实现了进程间的同步。

五、所遇问题及解决方法

经过这次试验，我对操作系统中进程的调度算法和调度过程、尤其是对基于时间片轮转的进程多级反馈算法有了更深的理解，对使用P、V操作来进行进程间的同步与互斥过程也有了更深的体会。

实验中，首先就是要求我们实现调度算法的选择策略，使系统可以在时间片轮转调度和四级反馈队列调度之间切换。由于大部分代码老师都已经给出，所以只需实现一个取得下一个运行线程的函数，实现高优先队列为空时继续在低优先级中查找就可以了。代码编写不是很难，只要能基本了解了思想和结构就可以编写。对于实现进程间的同步和互斥，只需要利用P、V操作实现对临界资源的保护即可。虽然在过程中遇到很多困难，但所幸在老师同学们的帮助下，以及自己

－6－

查资料，还是完成了实验项目。

其次，也是同过这几次操作系统实验让我对计算机操作系统学习有了一个新的认识，通过这次实验又一次让理论运用于实践，而实践是需要系统的知识，去分析设计一个完整的东西，因此不仅是某个具体的细节自己要知道，还要了解好全局，一个小问题都有可能使得实验失败。

总之，这次实验让我学习了很多，通过这次实验设计，让我对整个系统有了更深的了解，虽然还有很多地方还没有完全明白，比如说，如何进行进程调度,如何处理中断，如何管理内存，因为后面几个Project都没有完全做出来，是个遗憾。但也是通过这次实验让我认识到自己还有很多不足的地方，在以后的学习中得以加强。对这次验的启示自己总结以下觉得首先是做一件事情要百分百的投入，然后是做事要细心不要总是急噪，最后是要多与同学交流，一个问题自己想半天可能还是不能解决，这个时候同学可能已经知道了很快就能帮你解决，这会给你节省很多时间思考其他的问题。这里要感谢老师的指导，也感谢同学在我不知道怎么往下做的时候给我的鼓励与帮助。感谢学校老师提供这么一次软件课程设计,让我受益匪浅。

－7－

本文来源：https://www.bwwdw.com/article/0k57.html