Linux操作系统课程设计—车辆死锁

[键入文字] “操作系统原理”课程设计 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 程序运行结果截图

[键入文字] “操作系统原理”课程设计 BX090709吴沛儒

4、 思考题的解答和讨论

? 在程序中为什么要创建三个线程？

为了进一步提高系统的并行处理能力，在程序中加入线程，使处理机并行处理多线程。

? 在ubuntu系统运行程序时为什么要输入-lpthread？

Lpthread是一个库，在linux操作系统编程时要用到这个库。就像使用pow等数学计算函数需要用到math.h。

? Semaphore这个库是做什么用的？

在这个程序中这个库是十分重要的，semaphore是信号量库。用以执行PV操作。

四、

《操作系统》课程设计小结（收获、不足与建议）

当我在回首这一个星期的时候，不因虚度光阴而悔恨，也不因碌碌无为而羞耻。我想，

这可能是我一学期中最丰富而有意义的一个星期了。

从大一开始我的理论知识就比实践知识好的多，每门课都如此，实训是我最头疼的一

件事。课本上记得很牢的东西到了实际操作的时候感觉都用不上，做个实验就手忙脚乱的。所以我感觉，这个星期的课设不仅学到了在理论课上学不到的知识，更是让我对自己的实践操作有了信心。

本次课程设计的题目之一是用“死锁”来处理车辆行驶的问题，其中用到了理论课中

学过的死锁和资源分配的东西。操作系统的基本特征是并发和共享，系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。死锁是指系统中若干个进程相互“无知地”等待对方所占有的资源而无限地处于等待状态的一种僵持局面，其现象是若干个进程均停顿不前，且无法自行恢复。死锁是并发进程因相互制约不当而造成的最严重的后果，是并发系统的潜在的隐患。一旦发生死锁，通常采取的措施是强制地撤销一个或几个进程，释放它们占用的资源。这些进程将前功尽弃，因而死锁是对系统资源极大的浪费。

预防死锁的策略有两种：资源预先分配策略和资源有序分配策略。本实验主要使用资

源有序分配策略来预防死锁。但这种策略也是有缺点的，它限制了进程对资源的请求，而且资源的编号较困难；同时暂时不用的小编号的资源需先申请，加长了它的占用时间。

因为这个课题的源代码在实验书上都有的，所以在程序的调试和运行上我没有发现什

么大问题。而是更加巩固了理论知识中的死锁问题，尤其是其中的银行家算法。

银行家算法作为一个避免死锁发生的重要算法为我们所熟知，当新进程进入系统时，

它必须说明对各类资源类型的实例的最大需求量。仅当申请者可以在一定时间内无条件地归还它所申请的全部资源时，才能把资源分配给它。人无完人，程序也如此，即使是这样周密的算法也有一定的缺陷，银行家算法的主要问题是，每个进程必须事先知道资源的最大需求量，而且在系统运行时，考查每个进程对各类资源的申请需花费较多的时间。而且这种算法过于谨慎，花销较大。

路漫漫其修远兮，吾将上下而求索。我们对操作系统的学习还有很长的路要走，死锁

[键入文字] “操作系统原理”课程设计 BX090709吴沛儒

只是其中的一小部分。重要的是，我在实训的这种里学到了这样的一种精神，一种知难而上，相信努力和付出能够带来好的结果的精神。这种精神比刻板的知识点更加重要，能够指引我走向更宽阔的明天。

五、 附录

程序源代码：

#include #include #include #include //死锁

#define Max 5

pthread_t E[Max]; pthread_t W[Max]; pthread_t S[Max];

pthread_mutex_t s1; pthread_mutex_t s2; pthread_mutex_t s3; pthread_mutex_t s4; int i;

void *s(void *a1)

{

pthread_mutex_lock(&s1); printf(\ sleep(2);

pthread_mutex_lock(&s2); printf(\ sleep(2);

pthread_mutex_unlock(&s1); pthread_mutex_lock(&s3); printf(\ sleep(2);

pthread_mutex_unlock(&s2); printf(\ printf(\ sleep(2);

pthread_mutex_unlock(&s3); }

//车辆最大数目 //E方向的线程 //W方向的线程 //S方向的线程 //C处的互斥信号 //B处的互斥信号 //A处的互斥信号 //D处的互斥信号

//用于方便动态显示行驶信息的

//S方向

//相当于PV原语中的P操作

//方便观察

//相当于PV原语中的V操作

//一辆S方向上的车已经通过

[键入文字]

void *e(void *a2) {

pthread_mutex_lock(&s2); printf(\ sleep(2);

pthread_mutex_lock(&s3); printf(\ sleep(2);

pthread_mutex_unlock(&s2); pthread_mutex_lock(&s4); printf(\ sleep(2);

pthread_mutex_unlock(&s3); printf(\ printf(\ sleep(2);

pthread_mutex_unlock(&s4); }

void *w(void *a3) {

pthread_mutex_lock(&s1); pthread_mutex_lock(&s4); printf(\ sleep(2);

printf(\ sleep(2);

pthread_mutex_unlock(&s4); printf(\ printf(\ sleep(2);

pthread_mutex_unlock(&s1); }

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

int c;

“操作系统原理”课程设计

//E方向

BX090709吴沛儒

//W方向

//记录输入的数值

printf(\ printf(\ printf(\ scanf(\ if( c > Max ) {

//c不能大过MAX

[键入文字] “操作系统原理”课程设计 BX090709吴沛儒

printf(\ exit(1); }

int i1 = pthread_mutex_init(&s1,NULL); if(i1 != 0) {

printf(\ exit(1); }

int i2 = pthread_mutex_init(&s2,NULL); if(i2 != 0) {

printf(\ exit(1); }

int i3 = pthread_mutex_init(&s3,NULL); if(i3 != 0) {

printf(\ exit(1); }

int i4 = pthread_mutex_init(&s4,NULL); if(i4 != 0) {

printf(\ exit(1); }

for(i = 0;i < c; i++) {

pthread_create(&W[i],NULL,(void *)w,(void *)(i + 1)); pthread_create(&E[i],NULL,(void *)e,(void *)(i + 1)); pthread_create(&S[i],NULL,(void *)s,(void *)(i + 1)); sleep(5); } //销毁线程

for(i = 0; i < c; i++) {

pthread_join(W[i],NULL); pthread_join(E[i],NULL); pthread_join(S[i],NULL); } exit(0); }

//分别创建c个W方向、E方向、S方向上的线程

//初始化互斥信号量

[键入文字] “操作系统原理”课程设计 BX090709吴沛儒

运行结果:

Wpr@ubuntu:~$ ./deadlock2

This program will help you let cars cross this T crossing. Suppose that there are same quantity of cars in three derections. Please input the integer number,less than 5:2 W 1 enter D E 1 enter B E 1 enter A W 1 enter C W 1 leave C !!!W finished one E 1 enter D E 2 enter B E 2 leave D !!!E finished one S 2 enter C E 2 enter A E 2 enter D S 2 enter B E 1 leave D !!!E finishes one S 1 enter A S 1 leave A !!!S finished one W 1 enter D W 1 enter C W 2 leave C !!!W finished one S 2 enter C S 2 enter B S 2 enter A S 2 leave A !!!S finished one Wpr@ubuntu:~$

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