操作系统课程设计报告优先级捐赠Priority-Scheduling-Task-2

西安电子科技大学操作系统课程设计(2016年度)实验报告实验名称：Priority-Scheduling-Task2班级：1403018姓名：张可心学号：14030188030一、实验内容操作系统中存在优先级反转问题——当一个高优先级线程通过信号量机制访问共享资源时，该信号量已被一低优先级任务占有，而这个低优先级任务在访问共享资源时，可能又被其他一些中等优先级任务抢先，因此造成高优先级任务被许多低优先级任务阻塞，实时性难以保证。我们的任务是：解决由锁（Lock）造成的优先级反转问题，解决策略是优先级捐赠。二、分析及设计优先级继承(Priorityinheritance)（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结构体中加入类型为structpri_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中的structthread的结构体中添加三个变量2、在文件thread.h中添加结构体structdthread3、然后在文件thread.c的init_thread()函数中添加初始化代码4、在thread_set_priority()函数中添加代码5、在synch.c文件的lock_acquire()函数中添加代码6、然后在lock_release()函数中添加代码7、添加中有一个thread_prisort()函数，定义在thread.c文件中四、实验结果在修改完成后，调用makecheck命令对../threads子目录进行任务检查，结果满足题目要求。五、心得体会本次实验内容为优先级反转问题，我采用了课设指导中要求的优先级继承算法（即优先级捐赠算法）。在实验过程中，遇到了很多课堂上没有提到过的问题，解决后感到获益匪浅。参考文献[1]黄伯虎，Priority-Scheduling-Task2.pdf。[2]网上相关代码资料等。