操作系统专业课程设计方案报告优先级捐赠PrioritySchedulingTask.docx

西安电子科技大学
操作系统课程设计
()

实
验
报
告

试验名称： Priority-Scheduling-Task2
班 级： 1403018
姓 名： 张可心
学 号：

一、试验内容
操作系统中存在优先级反转问题——当一个高优先级线程经过信号量机制访问共享资源时，该信号量已被一低优先级任务占有，而这个低优先级任务在访问共享资源时，可能又被其它部分中等优先级任务抢先，所以造成高优先级任务被很多低优先级任务阻塞，实时性难以确保。我们任务是：处理由锁（Lock）造成优先级反转问题，处理策略是优先级捐赠。
二、分析及设计
优先级继承 (Priority inheritance)
（1） 简单捐赠

图所表示：简单捐赠三个线程实施次序是：H—>M—>L。实施过程以下：首先H，M等候时间发生，处于挂起状态，L运行，持有锁A，M等候时间发生，就绪，抢占CPU；H等候时间发生，就绪，抢占CPU，并等候锁A；因为A已被L取得，H挂起，并将优先级捐赠给L，L优先级提升，开始运行，并释放所A，同时恢复原始优先级，H被唤醒，运行，然后M运行，L运行。
（2） 递归捐赠

图所表示：递归捐赠发生时各优先级实施次序是：H—>M—>L。实施过程以下：H、M等候时间发生，处于挂起状态，L运行，持有锁A，M等候事件抵达，就绪，抢占CPU，请求锁B成功，并继续请求锁A，因为A已被L持有，M挂起，并捐赠自己优先级32给L，L优先级取得提升，开始实施，H等候事件抵达，就绪，抢占CPU，并请求锁B，因为B被M持有，H挂起，并捐赠给自己优先级33给M，因为M因L而被阻塞，故优先级33也捐赠给L，L优先级再次得到提升，开始运行，L释放锁A，M被唤醒，L优先级恢复到31，M开始实施，释放锁B，H被唤醒，M优先级恢复到32，H运行，M运行，L运行。
（3）多重捐赠

图所表示，当多重捐赠发生时，三个优先级实施次序是：H—>M—>L。实施过程以下：H、M等候事件发生，处于挂起状态，L运行，并前后持有锁A和B，M等候事件发生，就绪，抢占CPU，并请求锁A，因为A被L占有，故M挂起，并将优先级32捐赠给L，L运行，H等候时间发生，就绪，抢占CPU，并请求锁B，因为B已被L占有，H挂起，并捐献优先级33给L，L优先级得到提升，运行，前后释放A、B，L优先级恢复到31，H被唤醒，运行，M运行，L运行。
具体分析：
要实现优先级捐赠问题，首先需要考虑保留原优先级问题，所以需要定义一个包含原先优先级和被捐赠时捐赠者需要什么锁两个组员结构pri_stack，并在 thread 结构体中加入类型为 struct pri_stack 组员，考虑到多重捐赠情况，该组员是栈结构。以后，再在 thread 结构体中加入 block_sema、block_lock 两个组员，分别统计被哪个信号量阻塞、在等候哪个 lock。在这以后，还需修改 init_thread()函数，使其在初始化时同时初始化这些新加入组员。在调用 thread_set_priority()时，为了确保线程在捐赠完成时其优先级回到新优先级，在该函数中加入对线程是否被捐赠过判定，若是，只修改栈底存放优先级；不然，修改线程目前优先级，并实施第二次试验中加入目前优先级确定。在 PV 操作中，当调用 P 操作时，若此时该信号量为 0，应在线程 block_sema组员中统计目前被哪个信号量阻塞；当调用 V 操作时，需在调用 thread_unblock()后置空线程 block_sema。在锁 acquire 和 release 操作中，当线程提议对锁索取时，需先判定该锁对应信号量是否为 0，若是，则说明已被占用，这时应在线程 block_lock 组员中保留阻塞该线程锁，并调用优先级捐赠函数。而在释放锁时候，假如该线程被捐赠过，会出现三种情况：该锁在线程被捐赠栈栈顶，则还原优先级，删除统计；该锁既不在栈顶也不在栈底，直接删除统计；该锁在栈底，将栈底优先级赋值给其上一层后，删除统计。而在实现优先级捐赠函数时，我们还需要考虑被捐赠者是否在 ready_list 中，若是，需调整其在 ready_list 中位置。同时，我们还需考虑被捐赠者是否在block_list 中，若是，且被捐赠者也被某个锁阻塞，此时调整其在信号量等候队列中位置，并触发递归捐赠。
三、具体实现

1、 首先在文件thread.h中struct thread结构体中添加三个变量

2、 在文件thread.h中添加结构体struct dthread

3、 然后在文件thread.cinit_thread()函数中添加初始化代码

4、在thread_set_priority()函数中添加代码

5、 在synch.c文件lock_acquire()函数中添加代码
6、 然后在lock_release()函数中添加代码
7、 添加中有一个thread_prisort()函数，定义在thread.c文件中

四、试验结果

在修改完成后，调用 make check 命令对../threads 子目录进行任务检验，结果满足题目要求。
五、心得体会
此次试验内容为优先级反转问题，我采取了课设指导中要求优先级继承算法（即优先级捐赠算法）。在试验过程中，碰到了很多课堂上没有提到过问题，处理后感到获益匪浅。
参考文件
[1]黄伯虎，Priority-Scheduling-Task2.pdf。
[2]网上相关代码资料等。