OS-2.3 同步和互斥
同步和互斥
进程同步，进程互斥
①进程同步：解决进程的异步问题，协调工作顺序。
②进程互斥：对于临界资源 / 共享资源，必须互斥地进行访问。（or结果就像两个文档打印混一起了）
- 不同线程 对 同一个进程 的共享变量 的访问才可能需要互斥，不同进程的不同线程不存在互斥访问。
临界资源：互斥，共享 – 资源。
临界区：访问临界资源的那一个 代码段。
- 临界区是为了保护临界资源而存在的。（所以5个并发进程就有5个共享操作变量X的代码段）
实现互斥的四个代码段：
进入区。临界区。退出区。剩余区。
==实现同步遵循的四个原则：==
空闲让进。忙则等待。有限等待。让权等待。
note：
可重入代码：不允许被修改的代码，又叫纯代码。
- 所以这种代码能在多个时刻被任意进程共享，无需互斥。（EG：进程映像中的程序（段））
回顾
进程互斥的软件实现方法
①单标志法
一个进程在访问完临界区后，会把使用临界区的权限 交给 另一个进程。
标志位turn，表示当前允许进入临界区的进程号。
- turn=x，轮到x进入临界区，而不是x先发出请求的意思。
缺点：当允许进入临界区的进程A不访问临界区（或者是并发时时间片到期了），造成临界区空闲，而别的进程如B使用不了临界区。
违背原则：“空闲让进”。
②双标志先检查法
先“检查”后“上锁”
先检查对方想不想使用（检查）
自己要用（表达意愿，上锁）。 flag[0]，flag[1]标记各进程的意愿，T/F。
缺点：如果两个进程是，并发的运行时，时间片切换，【1[false]（time out）-5[false]-6-7（time out）,2-3】会造成两个进程P1 P2同时使用临界区。
违反原则：“忙则等待”
原因在于：“检查”后，“上锁”前，可能发生进程切换。【即进入区的“检查”和“上锁”两个处理不是一气呵成的。】
③双标志后检查法
先“上锁”后“检查”。
自己想用临界资源（表达意愿，上锁）
自己不想再问对方。（检查）
缺点：并发运行，两个进程都访问不了临界区。【1(time out)-5(time out)-2-6-…】。造成“饥饿”。
违背原则：“空闲让进”，“有限等待”。
④peterson 算法
1.主动争取【flag[自己id]=true】
2.主动谦让【turn=对方id】
3.如果对方也想使用。且最后一次是自己谦让，则让对方进入临界区。【while（flag[对方id] && turn==对方id】
初始的 flag[]=false。
是 单标志法+先上锁后检查法的综合。
优点：遵循了空闲让进，忙则等待，有限等待三个原则。
缺点：没有遵循让权等待的原则。造成“忙等”
回顾
进程互斥的硬件实现方法
①中断屏蔽方法
实现机制：开/关中断指令
优点：简单，高效
缺点：
①不适合多处理机。（一个cpu关中断不能阻止其他cpu的进程访问同一共享资源）
②限制了CPU的并发执行能力。（屏蔽期间”冻结”当前CPU，无法响应中断、无法进程调度、无法处理I/O。）
③只适用于OS内核进程。（开/关中断指令只能运行在内核态，因为如果用户上锁忘记解锁了，很危险）
②TestAndSet指令
“检查”与“上锁是一体的。
一体的原因是：TSL（TS）指令是一条硬件指令，CPU执行这条指令时不会被打断。
优点：
①实现简单。
②相比于关中断方法，lock是共享变量，适合多处理器系统。
违背原则：“让权等待”
③swap指令
类似于TSL指令。
回顾
进程互斥的高级方法
互斥锁
【还有信号量，管程，条件变量等】
上锁：acquire（）
解锁：release（）
阻塞型互斥锁：放弃CPU，把自己挂起（阻塞），让CPU去执行其他进程，等锁可用时再被唤醒。
- 适用于：临界区较长或单处理器的场景。
自旋型互斥锁：进程在等待锁期间没有上下文切换（即不进入等待队列），CPU空转，忙等。
- 忙等： 即B也会使用CPU进程（时间片到期），但是B做不了事情，造成CPU空转，A又少了些许的CPU执行时间。
- 违背原则：“让权等待”。
- 适用于：临界区极短且多处理器的场景。
- 自旋锁的底层实现：可以是TSL指令，swap指令，单标志法。
- 优点：若持有锁的时间较短，则等待代价较低。
信号量机制
用户进程提供一对 原语（P,V） 来对信号量进行操作。
信号量不同于普通的变量，对信号量的操作只有：初始化，P，V三种。
P操作判断
if (S.value < 0)→ 阻塞（等于0时不阻塞是因为刚才拿了一个资源来用，现在才变成0的）V操作判断
if (S.value <= 0)→ 唤醒（等于0时唤醒是因为刚才释放了一个资源，正好给等待队列里的第一个线程用）（说明刚刚起码是-1，有进程需要资源）
整型信号量
原理：和双标志先检查后上锁相同。但是实现了 检查和上锁 一气呵成。（避免进程同时在临界区的问题）
缺点：不满足“让权等待”，会发生忙等。
原语wait–检查+上锁，signal–释放
记录型信号量⭐
原理：S. value表示剩余资源数，S.L指向等待资源的队列。
优点：遵循了“让权等待”原则（解决“忙等”问题）
⭐左右两边都重要
EG
回顾
用信号量机制实现进程互斥、同步、前驱关系
P（s） – 申请一个进程S，如果资源不够就阻塞等待
V（s） – 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。
实现进程互斥
互斥信号量初始值为1。
临界区之前对信号量执行P操作。
临界区之后对信号量执行V操作。
实现进程同步
同步：保证顺序执行。
同步信号量初始值为0。
临界区之前对信号量执行V操作。
临界区之后对信号量执行P操作。
实现前驱关系
为每一对的前驱关系设置信号量，初始值为0。
在每一个“前操作”之后执行V操作
在每一个“后操作”之前执行P操作
回顾
管程
信号量机制的缺点：编写程序困难，易出错，大量同步操作分散。
管程：不易出错，易编写。
管程 VS 进程
进程拥有私有数据结构。管程管理的是公共数据结构。
进程是主动调用的实体。管程是被动调用的模块。
进程具有动态的生命周期，管程是os中的静态资源管理模块，仅供进程调用。
条件变量
将不同的阻塞原因分别抽象为独立的条件变量。
每个条件变量维护一个等待队列。
对条件变量仅支持两种操作：wait和signal。
条件变量 VS 信号量
相似：wait和signal操作和PV操作都可以实现进程的阻塞与唤醒。
不同：
信号量具有整数值，反映可用资源数量。条件变量不维护数值，仅用于线程排队和通知。
资源数量由共享变量如S显示记录（PV操作一定会改变信号量的值）。条件变量只负责同步。（条件是否满足应该由共享数据判断 ，而不是依赖信号次数。）
相当于封装，自己调函数就行
回顾
进程同步互斥问题
生产者消费问题
名词解释：
没有空缓冲区 = 缓冲区全满
没有满缓冲区 = 缓冲区全空
①不能改变相邻P操作的顺序：会造成死锁。
（死锁：如果已经没有空闲区了，生产者会被阻塞，切换成消费者进程，消费者在等待对方释放资源锁，也被阻塞了，进入阻塞队列。互相等待被对方唤醒 ）
- 因此得，先执行同步P操作，再执行互斥P操作。（避免进程在持有互斥锁的同时等待资源）
②可以改变相邻V操作的顺序，不会造成进程阻塞。
不建议把处理内容都放入临界区，会造成临界区上锁时间长。
回顾
发现题目之间的同步，互斥关系。
确定PV顺序。
互斥信号量初值一般是1，同步信号量初值看资源初值是多少。
多（类）生产者-多（类）消费者
缓冲区为1，有可能，不用设置互斥信号量。
回顾
看成 事件 的先后关系（而不是进程的前后关系，这样子复杂）
读者-写者问题
设置一个信号量mutex，保证读进程检查和上锁一体，保证不会在执行完检查（count==0）后被切换进程导致之后进不去进程。
又有潜在的问题…写进程可能被“饿死”。
再设置一个信号量w，用于实现 “读写公平”（谁先来谁优先，而不是一直是读先）
（读者1完成，释放rw信号量，唤醒因为rw而阻塞的写进程）
回顾
哲学家进餐问题
死锁的出现：
如何防止死锁的发生？
方案②：保证了不会死锁，但会引起饥饿。此时只有4个人能拿起第一根筷子。
回顾
notes
系统有n个进程：
就绪队列中进程的个数最多有n-1个。（不会出现cpu空闲的）
阻塞队列中进程的个数最多有n个（死锁）
原语的实现：
- ①屏蔽中断方法（单CPU）
- ②硬件实现