OS-2.3 同步和互斥
同步和互斥
进程同步，进程互斥
①进程同步：解决进程的异步问题，协调工作顺序。
②进程互斥：对于临界资源 / 共享资源，必须互斥地进行访问。（or结果就像两个文档打印混一起了）
- *不同线程 对 同一个进程 的共享变量 的访问==才可能需要互斥==*。不同进程的不同线程不存在互斥访问。
临界资源是：互斥+共享 的资源。
- （打印机属于。公用队列属于。非共享数据不属于。可重入代码不属于。）
临界区：访问临界资源的那一个 ==代码段==。
- 临界区是为了保护临界资源而存在的。（所以5个并发进程就有5个共享操作变量X的代码段）
==实现互斥，的四个代码段：==
进入区。临界区。退出区。剩余区。
- 临界区：访问临界资源的代码段
- 进入区和退出区：==负责实现互斥==的代码段
==实现同步遵循的四个原则：==
⭐空闲让进。忙则等待。有限等待。让权等待。
note：
可重入代码：不允许被修改的代码，又叫纯代码。
- 所以这种代码能在多个时刻被任意进程共享，无需互斥。（EG：进程映像中的程序（段））
回顾
进程互斥的软件实现方法
①单标志法
==一个进程在访问完临界区后，会把使用临界区的权限 交给另一个进程。==
标志位turn，表示当前允许进入临界区的进程号。
- ==turn=x，轮到x进入临界区==，而不是x先发出请求的意思。
==缺点：==当允许进入临界区的进程A不访问临界区（或者是并发时时间片到期了），==而自身还没将turn置B==，别的进程如B使用不了临界区。
违背原则：==“空闲让进”==。
②双标志先检查法
==先“检查”后“上锁”==
- ① 先检查对方想不想使用（检查）【while(flag(对方进程编号)】
- ② （无论自己想不想用），都表示自己要用（表达意愿，==上锁==）。【flag(自己进程编号)=true】
- flag[0] = T，表示进程0想进入临界区。
- ==while（true）→原地打转；while（false）→执行执行下一条代码。==
==缺点：==
- ==IF：“检查”后，“上锁”前，发生了进程切换。==⭐
- 【1[false]（time out）-5[false]-6-7（time out）,2-3】，
- 造成==两个进程P1 P2都能够进入临界区==，同时使用临界区。
违反原则：“忙则等待”
核心原因：==进入区的“检查”和“上锁”两个处理不是一气呵成的。==
③双标志后检查法
==先“上锁”后“检查”。==
- 自己想用临界资源（表达意愿，上锁）
- 自己不想再问对方。（检查）
缺点：并发运行，==两个进程都访问不了临界区==。【1(time out)-5(time out)-2-6-…】。==造成“饥饿”。==
违背原则：**==“空闲让进”，“有限等待”。==**
④peterson 算法
是单标志法+先上锁后检查法的综合。
==先上锁后谦让turn==
1.主动争取【flag[自己id]=true】
2.主动谦让【turn=对方id】
3.==如果对方也想使用。且最后一次是自己谦让turn，则让对方进入临界区，自己原地转圈等待。==【while（flag[对方id] && turn==对方id】
初始的 flag[]=false。
优点：遵循了空闲让进，忙则等待，有限等待三个原则。
违背原则：：==让权等待==（造成==“忙等”==）
回顾
进程互斥的硬件实现方法
①中断屏蔽方法
==实现机制：开/关中断指令==
优点：简单，高效
缺点：
- ①只适合单CPU系统，不适合多CPU系统。（一个cpu关中断不能阻止其他cpu的进程访问同一共享资源）
- ②限制了CPU的并发执行能力。（屏蔽期间”冻结”当前CPU，无法响应中断、无法进程调度、无法处理I/O。）
- ③只适用于OS内核进程。（开/关中断指令只能运行在内核态，因为如果用户上锁忘记解锁了，很危险）
②TestAndSet指令
==“检查”与“上锁是一体的。==
一体的原因是：TSL（TS）指令是一条硬件指令，CPU执行这条指令时不会被打断。
优点：
- ①实现简单。
- ②相比于关中断方法，lock是共享变量，适合多CPU系统。
违背原则：“让权等待”。
③swap指令
类似于TSL指令。
回顾
进程互斥的高级方法
互斥锁，信号量，管程，条件变量等等
1.互斥锁
因为上锁和解锁是原子操作，所以一般互斥锁的实现通过硬件完成。
上锁：acquire（）
解锁：release（）
阻塞型互斥锁：放弃CPU，把自己挂起（阻塞），让CPU去执行其他进程，等锁可用时再被唤醒。
- 适用于：临界区较长或单处理器的场景。
自旋型互斥锁：进程在等待锁期间没有上下文切换（即不进入等待队列），CPU空转，忙等。
- 忙等： 即B也会使用CPU进程（时间片到期），但是B做不了事情，造成CPU空转，A又少了些许的CPU执行时间。
- 违背原则：“让权等待”。
- 适用于：**==临界区极短且多处理器的场景。==**
- 自旋锁的底层实现：可以是TSL指令，swap指令，单标志法。
2.信号量机制
前面的所有方案都无法实现“让权等待”。
==信号量本质是变量S。==
==用户进程提供一对 原语（P,V） 来对信号量进行操作。==
信号量不同于普通的变量，对信号量的操作只有：初始化，P，V三种。
整数型信号量
用==一个整数型的变量S==作为信号量，==用来表示系统中某种资源的数量==。
原理：和双标志先检查后上锁相同。但是实现了 检查和上锁 一气呵成。（避免进程同时在临界区的问题）
缺点：不满足“让权等待”，会发生忙等。
原语：
==wait–→ 检查+上锁==，相当于进入区
- 如果资源数不够，就一直循环等待 while (S<=0)；
- 不然，如果资源数够，就占用一个资源 S=S-1；
==signal–→ 释放==，相当于退出区
- 使用完资源后，在退出区释放资源 S=S+1；
记录型信号量⭐
==用 记录型数据结构 表示 信号量资源S。==
原理：==S. value表示剩余资源数==，==S.L指向等待资源的队列==。
优点：遵循了“让权等待”原则（解决“忙等”问题）
记录型信号量定义：
tpyedef struct{ int value; //剩余资源数。 struct process *L; //等待队列。 }semaphore;1
2
3
4
5
6
7
8
9
10
申请资源：==wait原语，P(S)==
+ ```c
void wait (semaphore S){
S.value--;
if (S.value<0){
block(S.L); // 如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂其到信号量S的等待(阻塞)队列中。
}
}
释放资源：==signal原语，V(S)==
void signal (semaphore S){ s.value++; if(S.value<=0){ wakeup(S.L); //释放完资源后，如果还有别的进程在等待这种资源(S.value<=0)，就使用wakeup原语唤醒等待队列中的一个进程。该进程从阻塞态变成就绪态。 } }生产者： P(empty); // 同步：看是否有空闲缓冲区（申请资源） P(mutex); // 互斥：进入临界区（申请锁） 放产品 V(mutex); // 互斥：退出临界区（释放资源） V(full); // 同步：增加产品数（释放锁）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
==P操作判断== `if (S.value < 0)` → ==阻塞==（等于0时不阻塞是因为刚才拿了一个资源来用，现在才变成0的）
==V操作判断== `if (S.value <= 0)` → ==唤醒==（等于0时唤醒是因为刚才释放了一个资源，正好给等待队列里的第一个线程用）
（说明刚刚起码是-1，有进程需要资源）
⭐
EG
回顾
#### 用信号量机制实现进程互斥、同步、前驱关系
P（s） -- 申请一个进程S，如果资源不够就阻塞等待
V（s） -- 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。
##### ==实现进程互斥==
> 互斥信号量初始值为1。
**临界区之前对信号量执行P操作。**
**临界区之后对信号量执行V操作。**
注：对不同的临界资源S1，S2，需要设置不同的互斥信号量。
##### ==实现进程同步==
> 同步信号量初始值为0。
同步：==保证一前一后的顺序执行。==
（前一个事情）在临界区之前对信号量执行V操作。（通知别人）
（后一个事情）在临界区之后对信号量执行P操作。（等待别人）
##### 实现前驱关系
> 本质上就是多级同步问题
为每一对的前驱关系设置信号量，初始值为0。
在每一个 “前操作” 之后执行V操作。
在每一个 “后操作” 之前执行P操作。
回顾
#### 3.管程
==信号量机制的缺点：==编写程序困难，易出错，大量同步操作分散。
==管程：不易出错，易编写。==
+ 一个进程，只有被特定的入口调用，s才能进入管程，来访问共享数据。
+ 每次仅允许**一个**进程在管程内执行。
+ **能同步，能互斥。**
==管程 VS 进程==
进程拥有私有数据结构。管程管理的是公共数据结构。
进程是主动调用的实体。管程是被动调用的模块。
进程具有动态的生命周期，管程是os中的静态资源管理模块，仅供进程调用。
==条件变量==
**将不同的阻塞原因分别抽象为独立的条件变量。**
每个条件变量维护一个等待队列。
对条件变量仅支持两种操作：wait和signal。
条件变量 VS 信号量
相似：PV操作都可以实现进程的阻塞与唤醒。
不同：
+ 信号量： 信号量具有整数值，==PV操作一定会改变信号量S的值==，反映可用资源数量。
+ 条件变量：==条件变量不维护数值==，只负责同步，仅用于线程排队和通知。
相当于封装，自己调函数就行
回顾
### 进程同步互斥问题
#### 1.生产者消费问题
名词解释：
没有空缓冲区 = 缓冲区全满
没有满缓冲区 = 缓冲区全空
消费者：
P(full); // 同步：看是否有产品（申请资源）
P(mutex); // 互斥：进入临界区（申请锁）
取产品
V(mutex); // 互斥：退出临界区（释放资源）
V(empty); // 同步：增加空闲缓冲区（释放锁）
①不能改变相邻**P**操作的顺序：会造成**死锁**。
（死锁：如果已经没有空闲区了，生产者会被阻塞，切换成消费者进程，消费者在等待对方释放资源锁，也被阻塞了，进入阻塞队列。*互相等待被对方唤醒* ）
+ **因此得，先执行同步P操作，再执行互斥P操作。**（避免进程在持有互斥锁的同时等待资源）
②可以**改变相邻V操作的顺序**，不会造成进程阻塞。
+ 
note：不建议把处理内容都放入临界区，会造成临界区上锁时间长。
回顾
① 发现题目之间的同步，互斥关系。
② 确定PV顺序。
③ ==互斥信号量初值都是1==，同步信号量初值看资源初值是多少。
#### 2.多（类）生产者-多（类）消费者
缓冲区大小为1。
+ 所以是可以不用设置互斥信号量的（因为盘子容量只有1，任何时候最多只有1个进程能操作盘子（放或取）)
回顾
==看成 事件 的先后关系（而不是进程的前后关系==，这样子复杂）
#### 3.读者-写者问题
设置一个信号量mutex，保证读进程检查和上锁一体，保证不会在执行完检查（count==0）后被切换进程导致之后进不去进程。
又有潜在的问题...写进程可能被“饿死”。
（最后一个完成释放信号量rw的事情，唤醒因为rw而阻塞的写进程）
再设置一个信号量w，用于实现 “读写公平”（谁先来谁优先，而不是一直是读先）
回顾
+ 核心在于用一个==计数器count==记录当前正在访问共享文件的读进程数目.
+ 我们可以用count的值判断当前进入的进程是否是第一个/最后一个读进程,从而做出不同的处理.
+ 此外我们还解决了可能产生的写饥饿的问题.
#### 4.哲学家进餐问题
+ 只有互斥的问题要处理.
死锁 : ==所有人==,是所有人都被卡住了.
死锁的出现：
如何防止死锁的发生？
① 方案一:最多允许四个哲学家同时进餐(而不是五个)
+ 这样子可以保证至少有一个哲学家拿到左右两只筷子,不再是死锁了.
方案②：
+ 要求奇数号哲学家先拿左边的筷子,然后再拿右边的筷子.
+ 而偶数号的哲学家相反.
+ 这样子可以保证了如果有相邻的两位都想吃饭,那么就只有其中一个哲学家能拿起第一只筷子,另一个哲学家会被阻塞,避免了死锁.
方案三：同时检查两个筷子是否可用
+ 这个方法不会导致饥饿，因为有的哲学家没吃饭，等别人吃完再吃。
回顾
### notes
系统有n个进程：
+ 就绪队列中进程的个数最多有n-1个。（不会出现cpu空闲的）
+ 阻塞队列中进程的个数最多有n个（死锁）
原语的实现：
+ ①屏蔽中断方法（单CPU）
+ ②硬件实现
评论