操作系统——进程同步与信号量

女爷i 2024-04-01 18:53 96阅读 0赞

**一、CPU调度策略（进程调度）**

**调度最终的目标是合理的使用CPU！！！**

**1.调度种类：**

*  **高级调度：****(High-Level Scheduling)又称为****作业调度****，它决定把****后备作业调入内存运行**
 *  **中级调度：****(Intermediate-Level Scheduling)又称为****在虚拟存储器中引入，在内、外存对换区进行进程对换**
 *  **低级调度****：(Low-Level Scheduling)又称为****进程调度****，它决定把****就绪队列的某进程获得CPU**

**2. 非抢占式调度与抢占式调度**

**非抢占式**

*  **分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生进程 调度进程 调度某事件 而阻塞时，才把处理机分配给另一个进程**

**抢占式**

*  **操作系统将正在运行的进程强行暂停，由调度程序将CPU分配给其他就绪进程的调度方式**

**3.调度策略的设计**

*  **周转时间 = 作业完成时间 - 作业提交时间**
 *  **响应时间：从操作发生到响应**
 *  **内耗时间：吞吐量（完成的任务量**）

**吞吐量与响应时间的矛盾：**

*  **响应时间小 ---> 切换次数多 ---> 系统内耗大 ---> 吞吐量小**

**I/O约束型任务：CPU使用短区间多**

**CPU约束型任务：I/O使用短区间多**

![6f9b4df4fbfc4a3f8940ffaa58b7f686.png][]

**二、CPU调度算法**

**1. 先来先服务（FCFS） ：公平、简单、非抢占、不适合交互式**

<table style="width:500px;"> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">任务</td> 
 <td style="text-align:center;">到达时间</td> 
 <td style="text-align:center;">CPU区间（ms）</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">P1</td> 
 <td style="text-align:center;">0.0001</td> 
 <td style="text-align:center;">10</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">P2</td> 
 <td style="text-align:center;">0.0002</td> 
 <td style="text-align:center;">29</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">P3</td> 
 <td style="text-align:center;">0.0003</td> 
 <td style="text-align:center;">3</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">P4</td> 
 <td style="text-align:center;">0.0004</td> 
 <td style="text-align:center;">7</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">P5</td> 
 <td style="text-align:center;">0.0005</td> 
 <td style="text-align:center;">12</td> 
 </tr> 
 </tbody> 
</table>

平均周转时间：（10+39+42+49+61）/5 = 40.2

**2.短作业优先（SJF）：保证最小的平均等待时间；不适合交互式**

*  **SJF的可抢占版本，比SJF更有优势**

> 如果调度结果为P1P2...PN，则平均周转时间为：
> 
>  *  P1+P1+P2+P1+P2+P3+...= ∑ ( n +1 - i ) Pi = nP1 + (n-1)P2+...
>  *  前面作业越短，平均周转时间越短

**3. 优先权调度**

*  **每个任务关联一个优先权，调度优先权最高的任务**
 *  **优先权太低的任务一直就绪，得不到运行，出现“饥饿”现象**
 *  **FCFS是RR的特例，SJF是优先权调度的特例。这些调度算法都不适合于交互式系统**

**4. 时间片轮转调度（RR）**

*  **时间片大：响应时间太长**
 *  **时间片小：吞吐量小** 
 *  **折中：时间片 10 - 100ms ；切换时间为 0.1-1ms（1%）**

![c7edd8ad09404db49f3afe3c9bf402eb.png][]

*  **优先级调度：前台任务>后台任务 ---> 后台任务产生饥饿**

**5. 多级队列调度：（没法区分I/O bound和CPU bound、存在一定程度的“饥饿”现象）**

*  **按照一定的规则建立多个进程队列**
 *  **不同的队列有固定的优先级（高优先级有抢占权）**
 *  **不同的队列可以给不同的时间片和采用不同的调度方法**

**6. 多级反馈队列**

*  **在多级队列的基础上，****任务可以在队列之间移动****，更细致的区分任务**
 *  **可以****根据“享用”CPU时间多少来移动队列，阻止“饥饿”**
 *  **最通用的调度算法****，多数OS都使用该方法或其变形，如UNIX、Windows等**

**三、Linux0.11中schedule():**

![aedcc214a4de4cc6b5e6c484f9759599.png][]

![2b66c65a80314a578d1c9fb08ea912ee.png][]

![8b09452fbbda488797fb690e1966d249.png][]

**阻塞的进程再就绪以后优先级高于非阻塞进程**

> counter作用整理：
> 
> * counter保证了响应时间的界：每个进程时间片最常为2P
> 
> c(0) = P
> 
> c(t) = c(t-1)/2 + P
> 
> c(∞) = P+P/2+P/4+...<=2P
> 
> 经过I/O以后，counter就会变大，I/O时间越长，counter越大（优先级提高），照顾了I/O进程，变相照顾了前台进程
> 
> 后台进程一直按照 counter 轮转，近似SJF调度
> 
> 每一个进程只用维护一个counter变脸，简单、高效
> 
> * 固定优先级调度：后台任务产生饥饿
> * 动态优先级调度：后台任务优先级提高，前台任务响应时间长

**四、进程同步与信号量（多进程合作）**

**1.生产者 - 消费者实例（用户态程序）：**

![6d1e300f208f499ab915bd54410c4006.png][]

![4136de87c8d4446eb0860797544a2f5c.png][]

**进程同步核心：等待**

**进程****走走停停****就是****进程同步****，****保证多进程合作的合理有序**

![6e87f95464e34539a8e2df52f0021344.png][]

![7fc4d7a662b8449fbb5286ee3b5c455b.png][]

*   **单纯的counter不能知道有多少个生产者被沉睡**
 *  **导致后面进来的生产可能永远被sleep**
 *  **所以需要信号量来决定是否发信息，即根据被sleep的生产者数量来决定发多少次唤醒**
 *  **信号量：发信号 + 记录等待的进程（对应睡眠和唤醒）**

**2.信号量开始工作：**

**信号量：**

*  **一个确定的二元组（s，q），其中s是一个具有非负初值的整形变量，q是一个初始状态为空的队列，整形变量s表示系统中某类资源的数目：**
    
     *  **当其值 ≥ 0 时，表示系统中当前可用资源的数目**
     *  **当其值 ＜ 0 时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目**
 *  **除信号量的初值外，信号量的值仅能由P操作和V操作更改，操作系统利用它的状态对进程和资源进行管理**

<table style="width:500px;"> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">缓冲区满，P1执行</td> 
 <td style="text-align:center;">P1 sleep&nbsp; &nbsp; &nbsp;</td> 
 <td style="text-align:center;">sem = -1</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">P2执行</td> 
 <td style="text-align:center;">P2 sleep</td> 
 <td style="text-align:center;">sem = -2</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">消费者C执行1次循环</td> 
 <td style="text-align:center;">wakeup P1</td> 
 <td style="text-align:center;">sem = -1</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">C再执行1次</td> 
 <td style="text-align:center;">wakeup P2</td> 
 <td style="text-align:center;">sem = 0</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">C再执行1次</td> 
 <td style="text-align:center;"></td> 
 <td style="text-align:center;">sem = 1</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">P3执行</td> 
 <td style="text-align:center;"></td> 
 <td style="text-align:center;">sem = 0</td> 
 </tr> 
 </tbody> 
</table>

* **信号量 <=0 ，等待；信号量 > 0 ，执行**
 * **根据信号量的值，决定进程何时走何时停**

![dca3b284d5d545df9d0ba6e02f7723d6.png][]

**3.信号量定义：**

**信号量：特殊整型变量，量用来记录，信号用来sleep和wakeup**

![7093c0ff32824baca727f7dd4bac4a89.png][]

V(semaphore s)
 
 {
 
         s.value ++
 
         if(s.value <= 0){
 
                 wakeup(s.queue);}
 
 }

![5027a3f4d43b498cbd99f5edc601c045.png][]

**4.信号量临界区保护**

*  **信号量保护：上锁**
 *  **竞争条件：和调度有关的共享数据语义错误（语义错误和调度顺序有关）**
 *  **临界区：一次只允许一个进程进入该进程的那一段代码**

> **为什么要进行信号量保护：**
> 
>  *  **信号量表达同步必须是语义正确**
>  *  **保证语义正确必须是临界区**
>  *  **故读写信号量的代码一定是临界区**

![da771210bf77406c8bd65c7b77c51b30.png][]

*  **进入区:查看临界区是否可访问，如果可以访问，则转到步骤二，否则进程会被阻塞**
 *  **临界区:在临界区做操作**
 *  **退出区:清除临界区被占用的标志**
 *  **剩余区：进程与临界区不相关部分的代码**

**临界区代码的保护原则：**

*  **基本原则：互斥进入**
 *  **好的临界区保护原则：有空让进、有限等待**

**（1）上锁**

*  **轮转法（互斥进入）：**

![6d91b800990d4c6099ca08af42caf0dc.png][]

*  **标记法（空等，都进入不了临界区）：**

![316f07f572794f31b59c854380c95a79.png][]

*  **非对称标记（Peterson算法）：轮转法+标记法（两个进程）**

![2d2ebe37e9e4462097bdcadd063751d8.png][]

![39409986d24c40ce98437cfe58c91cf6.png][]

**&&：第一个表达式为false时，结果为false（具有短路功能）**

**第一个表达式为false时，后面才会继续计算**

*  **面包店算法（软件方法、多个进程）：轮转+标记：**
    
     *  **如何轮转：每个进程都获得一个序号**
     *  **如何标记：进程离开时序号为0，不为0的序号即为标记**
     *  **面包店：每个进入商店的客户都获得一个号码；号码最小的先得到服务；****号码相同时，名字靠前的先服务**

![62be33cad49b45f8a9abc793e6ae442c.png][]

**（2）临界区保护：组织调度**

*  **关中断：多CPU（多核）不好使**
    
     *  **因为关中断时，只是对执行该条件语句的CPU进行关中断，当中断来临时，执行P1语句的CPU继续执行（关中断），执行其他语句的CPU中断想回那个，执行P2语句，最后P1和P2只会导致信号量歧义**

![2022250ef8b54babb962c8f419b7b066.png][]

*  **硬件原子指令法：**

![c7ed3e0d97dd4a8b980aac522bf06204.png][]

**五、死锁处理**

![f4b7ad536341454d877b615686803421.png][]

**死锁：互相等待对方持有的资源**

> **死锁的4个必要条件：**
> 
>  *  **互斥使用**
>  *  **不可抢占**
>  *  **请求和保持**
>  *  **循环等待（环路等待）**

> **死锁处理方法：**
> 
>  *  **死锁预防：破坏死锁出现的条件**
>     
>      *  **不占有资源：一次性申请所有需要的资源，资源申请必须按序进行（资源浪费、编程困难）**
>  *  **死锁避免：检测每个资源请求，如果造成死锁就拒绝**
>     
>      *  **判断此次请求是否引起死锁，即是否为安全状态**
>      *  **安全状态：所有进程存在一个可完成的执行序列P1P2P3...Pn**
>      *  **银行家算法：找出安全序列(T(n)= O(mn^2)；m：资源个数，n：进程个数)：找出安全序列**
>      *  **请求出现时：首先将假装分配，其次调用银行家算法，若无安全序列，则拒绝资源申请**
>  *  **死锁检测+恢复：检测到死锁出现，让进程 roll back（回滚），让出资源**
>     
>      *  **发现问题再处理：roll back难实现**
>  *  **死锁忽略：就像没有死锁一样：**
>     
>      *  **代价最小，可重启解决**

**六、进程间通信：**

**本地进程间通信的方式有很多，可以总结为下面四类：**

*  **消息传递（管道、FIFO、消息队列）**
 *  **同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）**
 *  **共享内存（匿名的和具名的）**
 *  **远程过程调用（Solaris门和Sun RPC）**

[6f9b4df4fbfc4a3f8940ffaa58b7f686.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/57d24efd97ac4ad98b1cd5851767055a.png
[c7edd8ad09404db49f3afe3c9bf402eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/afb72c985cb24711b77af961e14db824.png
[aedcc214a4de4cc6b5e6c484f9759599.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/287a041bd5cd48df82cb7e6b89c70479.png
[2b66c65a80314a578d1c9fb08ea912ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ef9ac85dc3df4ae2825e1d0f39839bd6.png
[8b09452fbbda488797fb690e1966d249.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ae24e4eacc644cfa92b2bf9f9fbfca4a.png
[6d1e300f208f499ab915bd54410c4006.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/73dcd40698d448ca8bbc9aa362c86601.png
[4136de87c8d4446eb0860797544a2f5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6db03287e0e94aaf907486934c79d820.png
[6e87f95464e34539a8e2df52f0021344.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fa6baef51c9a441b839247a7b10edc45.png
[7fc4d7a662b8449fbb5286ee3b5c455b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/27cf407ed1f6420ab79bdac902cda5d6.png
[dca3b284d5d545df9d0ba6e02f7723d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d1c668b284a54e64a00c504220ddeb01.png
[7093c0ff32824baca727f7dd4bac4a89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f7f2de8e3a8740e9b97b48d73cbc4bf0.png
[5027a3f4d43b498cbd99f5edc601c045.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/af990ce41aa54a6abcda8ec03462bd8d.png
[da771210bf77406c8bd65c7b77c51b30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c7a115bc77da42ab98937b7d7f182097.png
[6d91b800990d4c6099ca08af42caf0dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b4353e08fd6c4d1e84dd479377b1c2ac.png
[316f07f572794f31b59c854380c95a79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/2d08f9211a1640cd99f47dc7b6bf31ab.png
[2d2ebe37e9e4462097bdcadd063751d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/734018c149e24a9ca5bf7d127a19f5ce.png
[39409986d24c40ce98437cfe58c91cf6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3453e459e6254ebca88b60abe1b17bfe.png
[62be33cad49b45f8a9abc793e6ae442c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/23d03e8fe7b149cc83e9ad8b09fd1762.png
[2022250ef8b54babb962c8f419b7b066.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/25b58ac77cf648678510752871f10a5c.png
[c7ed3e0d97dd4a8b980aac522bf06204.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/67d25f8ab41d40dfbf7095102ea66f99.png
[f4b7ad536341454d877b615686803421.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/aaf24399f87249e192d84eed81fb0af7.png