[键入文字] “操作系统原理”课程设计 BX090709吴沛儒
《操作系统原理》 课程设计报告
姓 名： 吴沛儒 班 级： BX0907 学 号： 9 指导老师： 胡静
二〇一一年十二月十六日
[键入文字] “操作系统原理”课程设计 BX090709吴沛儒
目录
一、 《操作系统原理》课程设计的目的与要求 ..................................... 3 1、 目的 ................................................................................................ 3 2、 要求 ................................................................................................ 3 二、 简述课程设计内容、主要功能和实现环境 .................................. 3 1. 课程设计内容 ................................................................................... 3 2. 主要功能 ........................................................................................... 3 3. 实现环境 ........................................................................................... 3 三、 任务的分析、设计、实现和讨论 ................................................... 3 1、 任务的分析 .................................................................................... 3 2、 任务的设计与实现 ........................................................................ 4 3、 操作过程和结果分析 .................................................................... 5 4、 思考题的解答和讨论 .................................................................... 6 四、 《操作系统》课程设计小结（收获、不足与建议） ..................... 6 五、 附录 ................................................................................................... 7
[键入文字] “操作系统原理”课程设计 BX090709吴沛儒
设计课题：操作系统的死锁实验（车辆死锁问题）
一、 《操作系统原理》课程设计的目的与要求
1、 目的 （1） 理解死锁的产生原因，掌握预防和避免死锁的方法，以及死锁的检测方法。 （2） 通过车辆行驶死锁问题的设计与实现掌握解决死锁的方法。 2、 要求
编写车辆行驶死锁问题的程序： （1） 在Linux下用C语言编程，利用信号量操作实现进程同步； （2） 假设3个方向的车辆数目相等，数值由用户输入，并动态显示车辆的行驶状态，每个车辆行驶所用的时间可以预先设定。
二、 简述课程设计内容、主要功能和实现环境
1. 课程设计内容
车辆行驶死锁问题，在Linux下用C语言完成下面模型：设有一个T字型路口，其中A、B、C、D处各可容纳一辆车，车行方向如图1所示。试找出死锁并用有序分配法消除之，要求资源编号合理。
图1 T型路口模型图
2. 主要功能
本程序可选用优先数法或简单轮转法对五个进程进行调度。每个进程处于运行R(run)、就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。为了便于处理，程序进程的运行时间以时间片为单位计算。各进程的优先数或轮转时间片数、以及进程需要运行的时间片数，均由伪随机数发生器产生。
3. 实现环境
本次课程设计结合算法的特点，采用Linux Ubantu操作系统平台。开发工具为Microsoft Visual C++6.0。
三、 任务的分析、设计、实现和讨论
1、 任务的分析
死锁是指在一组进程中的各个进程均占有不会释放的资源，但因互相申请被其他进程所占用不会释放的资源而处于一种永久等待状态。
死锁的四个必要条件：
? 互斥条件（mutual exclusion）：资源不能被共享，只能由一个进程使用。
[键入文字] “操作系统原理”课程设计 BX090709吴沛儒
? 请求与保持条件（hold and wait）：已经得到资源的进程可以在此申请新的资源。 ? 非剥夺条件（no pre-emption）：已分配的资源不能从相应的进程中被强制地剥夺。 ? 循环等待条件（circular wait）：系统中若干进程组成环路，该环路中每个进程都
在等待相邻进程已占用的资源。
死锁预防的基本思想是对进程在申请有关资源的时候规定某种策略，如果所有进程都遵守这一策略，则系统就不会进入死锁状态。
预防死锁的策略有两种：资源预先分配策略和资源有序分配策略。本实验主要使用资源有序分配策略来预防死锁。下面开始重点介绍资源有序分配策略的申请过程及其缺点。
资源有序分配策略在于打破死锁条件中的循环等待条件。事先将所有的资源类进行全排序，并对其进行编号，赋予每个资源类一个唯一的整数（该资源类的数量）。
资源的有序分配策略规定进程必须按照资源编号由小到大的次序申请资源。就是说，当进程不占有任何资源时，该进程可以先去申请某一个资源类中的任意多个资源实例，但当它申请另一资源类时，必须满足申请的该资源类中的若干个资源实例，则他必须在一个申请命令中同时发出请求。
一个进程必须按从小到大的次序进行资源的申请。可以申请某一资源类中的资源实例充要条件是它必须已经释放了前一个申请的资源类中的所有资源实例，其中申请的该资源类中的资源实例的数量要大于等于前面所申请的资源实例的数量。
如果所有的进程在申请资源是都遵循上述的策略，系统就不会发生死锁。在使用资源有序分配策略时，资源类的编号应当仔细考虑，通常应当按使用资源的次序来给资源类编号。
资源有序分配策略也有缺点，它限制了进程对资源的请求，而且资源的编号较困难；同时暂时不用的小编号的资源需先申请，加长了它的占用时间。
2、 任务的设计与实现 死锁的可能性有两种：
（1）E方向两辆车分别位于A和B，S方向一辆车位于C，W方向一辆车位于D。 （2）S方向两辆车分别位于B和C，E方向一辆车位于A，W方向一辆车位于D。 位置资源编号：f(C)=1，f(B)=2，f(A)=3，f(D)=4。
管理C，B，A，D四个位置的信号量分别为s1，s2，s3，s4，初始值均为1。控制的PV原语，如表1所示。
表1 利用PV原语解决死锁算法
Semaphore s1=1,s2=1,s3=1,s4=1; Void S（）{ P（s1）; 驶入C； P（s2）; 驶入B； V（s1）; P（s3）; 驶入A； V（s2）; 驶出A; V（s3）; }
Void E（）{ P（s2）; 驶入B； P（s3）; 驶入A； V（s2）; P（s4）; 驶入D; V(S3); 驶出D； V（S4）； ｝ Void W（）｛ P（S1）；//按序申请 P（S4）； 驶入D； 驶入C； V（S4）； 驶出C； V（S1）； ｝ [键入文字] “操作系统原理”课程设计 BX090709吴沛儒
本实验的程序流程图，如图2所示。
图2 车辆死锁问题流程图
3、 操作过程和结果分析
1. 在Linux系统中运行程序deadlock2。 2. 输入每条路上的车辆数并按确定。
图3 程序运行结果截图