【操作系统】第九课

谁践踏了优雅 2022-03-20 04:28 212阅读 0赞

来源：操作系统\_清华大学(向勇、陈渝)

**1.背景知识**

同步互斥、临界区、死锁、互斥概念等等

多道程序设计（multi-programming）：现代操作系统的重要特征

并行很有用：多个并发实体（CPU、I/O、用户、…）

进程/线程：操作系统抽象出来用于支持多道程序设计

CPU调度：实现多道程序设计的机制

调度算法：不同的策略

我们主要讨论协同多道程序设计和并发问题。

独立的线程：  
1.不和其他线程共享资源或状态，不和其他线程共享资源或状态，不交互  
2.具有确定性（输入状态决定结果）  
3.可重现（能重现起始条件），I/O  
4.调度顺序不重要

合作的线程：在多个线程中共享状态，不确定性，不可重现

不确定性和不可重现意味着BUG可能是间歇性发生的。

为什么要合作？  
1.共享资源（嵌入式系统）；  
2.加速，效率高（I/O操作和计算可以重叠，拆分小任务，流水，并行，多处理器将程序分成多个部分并行执行）；  
3.模块化：大程序分解成小程序，使系统易于扩展

存在的问题——>举例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]  
因为进程切换时，就要保存现场包括寄存器值，所以两边都是100作为新的PID，next\_pid为101，和我们期望有差别.

希望是：  
无论多个线程的指令序列怎么交替，程序都必须正常工作，调试难度很高；  
不确定性要求并行程序的正确性，一定更要预先思考。

**2.一些概念**

因为上节课的问题，所以引出了同步互斥的概念。

上面的问题，术语叫作：Race condition （竞态条件）  
导致系统缺陷：结果依赖于并发执行的时间点 顺序/时间，导致不确定性和不可重现。

怎么避免竞态？如何不让指令被打断？  
方法：atomic operation原子操作  
原子操作：指一次不存在任何中断或者失败的执行，要么成功done要么没执行 ，并且不应该发现任何部分执行的状态。

实际上操作往往不是原子的，甚至单个机器指令都不一定是原子的。  
对内存的load store是原子的，但++ 、–-都不是

**临界区critical section：（访问共享资源的代码区域）**  
进程中访问共享资源的代码区域，且当另一个进程处于相应代码区域时便不会执行。

互斥mutual exclusion：  
任一时刻只能有一个进程进入临界区访问。当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区，并访问任何相同的共享资源。

死锁Dead lock：  
多个进程相互等待完成特定任务，而最终没法继续自身任务

饥饿starvation：  
一个可执行的进程长期等待执行，被调度器持续忽略。

死锁（Deadlock）举例：A拿到锁1，B拿到锁2，A想继续拿到锁2再继续执行，B想继续拿到锁1再继续执行。导致A和B谁也无法继续执行。

A贴了标签，A访问了临界资源，此时其他人想访问临界区，因为有A标签，便不会去访问。

**3.临界值**

临界区的特点：  
1.互斥，同一时间临界值最多存在一个线程  
2.progress前进，如果一个线程想要进入临界区，不会一直死等，总能成功  
3.优先等待，如果一个线程i处于入口区，那么i的请求被接受之前，其他线程进入临界区的时间是有限制的。否则，是一种饥饿状态了。是对progress的补充  
4.无忙等待：尽量不要忙等，如果进程一直等待进入临界区，那么在它可以进入之前会被挂起。（可以不满足）

**临界区代码保护三种方法：禁用硬件中断，基于软件，更高级的抽象**

我们还会比较三种方法在性能、时间复杂性、并发级别的特点

**4.禁用硬件中断**

三种方法：禁用硬件中断，基于软件，更高级的抽象

如果进入临界区的代码没有中断，那么就没有上下文切换，因此就没有并发，此时的代码会一直执行到结束。  
关中断，就没有调度。  
硬件将中断处理延迟到中断被启用之后。  
大多数现代计算机体系结构都提供指令来完成。

问题：  
一旦禁用中断，线程无法停止  
整个系统都会停下来，I/O啥的都没用了，其他线程可能会饥饿 影响效率  
临界区要是太长咋整？无法限制响应中断所需的时间，可能有硬件影响。一般都用于短的临界区时间。  
如果两个CPU并行的话，一个CPU只能屏蔽自身，另一个仍可能产生中断，也就是只能控制自己的CPU中断，控制不了多个CPU中断。

进入临界区：禁用中断  
离开临界区：开启中断

**5.基于软件的解决方法**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]

**6.更高级的抽象**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220320/d806d2bbf71f4059833bc2279a809908.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220320/1c09c428cb124a80b3749fb93a9d9a00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]: /images/20220320/fcf1a7bcc1f94ab0be9b5aab16dc06b8.png