同步互斥和 Linux 内核模块之C语言【100012226】

# 同步互斥和 Linux 内核模块 课程名称：操作系统 实验类型：综合型 实验项目名称：同步互斥和 Linux 内核模块 ## 一、实验环境 1、**PC 端配置**： 处理器：Intel(R)Core(TM)i7-8550U CPU @ 1.80GHz 内存：8G 显卡：NVIDIA GeForce MX150 虚拟机配置（VMware workstation 15.5 pro）： 处理器内核数量：4 内存：4GB 2、**操作系统环境**： Windows 操作系统； 3、**Linux 版本**： Ubuntu 20.04 ## 二、实验内容和结果以及分析 ### 实验一: #### 1、实验内容 有两条道路双向两个车道，即每条路每个方向只有一个车道，两条道路十字交叉。假设车辆只能向前直行，而不允许转弯和后退。如果有 4 辆车几乎同时到达这个十字路口，如图（a）所示；相互交叉地停下来，如图（b），此时 4 辆车都将不能继续向前，这是一个典型的死锁问题。从操作系统原理的资源分配观点，如果 4 辆车都想驶过十字路口，那么对资源的要求如下： + 向北行驶的车 1 需要象限 a 和 b； + 向西行驶的车 2 需要象限 b 和 c； + 向南行驶的车 3 需要象限 c 和 d； + 向东行驶的车 4 需要象限 d 和 a。  我们要实现十字路口交通的车辆同步问题，防止汽车在经过十字路口时产生死锁和饥饿。在我们的系统中，东西南北各个方向不断地有车辆经过十字路口（注意：不只有 4 辆），同一个方向的车辆依次排队通过十字路口。按照交通规则是右边车辆优先通行，如图(a)中，若只有 car1、car2、car3，那么车辆通过十字路口的顺序是 car3->car2->car1。车辆通行总的规则： 1. 来自同一个方向多个车辆到达十字路口时，车辆靠右行驶，依次顺序通过； 2. 有多个方向的车辆同时到达十字路口时，按照右边车辆优先通行规则，除非该车在十字路口等待时收到一个立即通行的信号； 3. 避免产生死锁； 4. 避免产生饥饿； 5. 任何一个线程（车辆）不得采用单点调度策略； 6. 由于使用 AND 型信号量机制会使线程（车辆）并发度降低且引起不公平（部分线程饥饿），本题不得使用 AND 型信号量机制，即在上图中车辆不能要求同时满足两个象限才能顺利通过，如南方车辆不能同时判断 a 和 b 是否有空。 #### 2、设计思路 分析题目要求，将每一辆骑车视作一个单独的线程，则一个线程所执行的任务如下： 1. 按照汽车方向加入个方向的等待队列； 2. 等待同方向的前方车辆离开等待队列； 3. 等待正在道路上行驶的同方向，以及左右方向的车辆离开道路（不需要等待对面方向的车辆离开道路，因为对面方向的车辆和本方向车辆并不占用相同的资源）； 4. 该车辆准备发车； 5. 检测死锁，如果四个方向都要同时发车，则触发死锁检测线程； 6. 遵循右侧车辆先行原则，让右侧车辆先行并等待； 7. 车辆发车，进入路口第一段，并从等待队列中弹出； 8. 车辆进入路口第二段； 9. 车辆彻底通过路口； 为了更加充分地体现整个程序进行时的并发过程，我对实验报告中的输出做了一些调整，车辆同行过程中，在不同阶段下会产生如下输出： `"Car %d from %s arrives at crossing.\n",ID,dirS` 表示车辆已经到达了等待队列的首部，也就是在路口等待的阶段； `"Car %d from %s is going to get into the crossing.\n"` 表示车辆已经从路口出发，离开等待队列； `"Car %d from %s has gone through part X.\n",ID,dirS` 表示车辆已经通过路口中的 X 部分，例如对于北方出发的车辆，首先会通过上方图中的 part C 的部分，则在通过 part C 后产生输出 `Car 1 from south has gone through part c`,其次会通过 part d，通过 part d 后产生输出 `Car 1 from south has gone through part d`，产生这一输出后也就代表着车辆已经通过了路口； #### 3、实现过程 上述线程所执行的 9 个任务中，涉及诸多互斥与同步的问题，均通过互斥锁，条件变量以及线程间的全局变量来实现，这里将对如何实现 9 个任务的同步与互斥进行说明： 在任务 1 和 7 中，涉及对于等待队列的修改，`mutex_wait[]` 是四个方向的等待队列的互斥锁，在每次新的车辆入队或出队时，需要对相应的队列加锁来避免同时读写，以下是入队时的代码： ```c pthread_mutex_lock(&mutex_wait[dir]); //访问等待队列的互斥锁 enqueue(ID,Queue_wait[dir]); //将本车辆加入等待队列中 pthread_mutex_unlock(&mutex_wait[dir]); ``` 任务 2 中需要等待同方向上前方的车辆离开队列，通过队列数据结构队头的 ID 即可判断前方是否还有车辆，如果不是自己则继续等待： ```c while(front(Queue_wait[dir])!=ID); ``` 任务 3 需要等待正在道路上行驶的三个方向的车辆（无需等待对面方向的车辆）通过进程间的全局变量 `flag[]` 来判断，`flag[]` 代表每个方向上是否有车辆正在路口通行，当一辆车发动后（在任务 7 中），相应方向 flag 置 1，一辆车行驶过路口时，相应方向 flag 置 0（在任务 9 中），通过判断对应的 flag 是否为 1 即可知道该放下是否有车在通行； ```c while(flag[dir]); while(flag[(dir+1)%4]); while(flag[(dir+3)%4]); ``` 无需担心 `flag[]` 的互斥问题，因为会修改 flag 的只有同一方向的线程（车辆），通过路口的车辆会在任务 9 中修改 flag，而此时另一辆同方向的车辆还在任务 3 中等待，而另一次修改 flag 的机会在任务 7 中，因此不存在互斥访问问题。 任务 4、5 所做的均是为了避免死锁，进入任务 4 后，变量 `crossSource` 减少 1，并同过相应的互斥锁避免 `crossSource` 的同时修改，`crossSource` 是一个初值为 4 的变量，代表路口资源，每一辆车即将发车时 `crossSource` 减少 1，通过路口后 `crossSource` 增加 1，当 `crossSource` 为 0 时，代表 4 个方向同时要通车，意味着死锁发生，因此需要触发死锁进程： ```c pthread_mutex_lock(&mutex_cross); crossSource--; //道路资源统计量减一 pthread_mutex_unlock(&mutex_cross); if(!crossSource) //四个方向都要占用资源，发生死锁 { printf("DEADLOCK: car jam detected, signalling North to go.\n"); pthread_mutex_lock(&mutext_deadLock); pthread_cond_signal(&cond_deadLcok); //触发死锁进程 pthread_mutex_unlock(&mutext_deadLock); } ``` 死锁进程的内容是如下一段代码： ```c while(1) { pthread_mutex_lock(&mutex_cross); //等待唤醒 pthread_cond_wait(&cond_deadLcok,&mutex_cross); //唤醒后，首先让北方车辆通信，利用条件变量激活北方的车辆 pthread_mutex_lock(&mutex_dir[NORTH]); pthread_cond_signal(&cond_first[NORTH]); pthread_mutex_unlock(&mutex_dir[NORTH]); pthread_mutex_unlock(&mutex_cross); } ``` 死锁进程创立后一直通过信号量等待车辆线程去唤醒，一旦检测到死锁后唤醒，死锁进程将优先令北方车辆通过，从而解决死锁问题。 任务 6 通过条件变量完成：如果右方有车辆通行则令右侧车辆先行，同时为了避免饥饿问题，通过条件变量等待右侧车辆行驶过后，右侧车辆唤醒左侧车辆通行 ```c if(Queue_wait[(dir+1)%4]->size!=0) { pthread_cond_wait(&cond_first[dir],&mutex_dir[dir]); } ``` 发车后，每一个方向的车辆根据自己所需的资源不同，执行不同的代码，通过互斥锁去访问 abcd 四种资源，并在通过相应位置后发送对应的信息，任务 7-9 就执行这一段内容，以北方车辆为�