进程同步、互斥
进程异步
各并发执行的进程以各自独立的、不可预知的速度向前推进
进程同步
协调多个并发执行进程的工作先后次序
例如：进程通信中的管道通信
- 读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。
- 如何解决这种异步问题，就是“进程同步”所讨论的内容。
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
进程互斥
- 我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
- 对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系
- 进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
访问临界资源
- 临界区是进程中访问临界资源的代码
- 进入区和退出区是负责实现互斥的代码段
- 临界区也可称为”临界段“
访问临界资源（进程互斥）需要遵循的原则
空闲让进
临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待
当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待
对请求访问的进程，应保证能在有限时间内进入临界区 (保证不会饥饿)
让权等待
当进程不能进入临界区，应当立即释放处理机，防止进程忙等待 (不应该让他占用处理机 一直执行循环无法前进，应当得知无法进入临界区时不执行循环，直接切换进程)
小结
进程互斥的软件实现方法
单标志法
思想
一个进程访问完临界区后会把使用临界区的权限交给另一个进程，即每个进程进入临界区的权限只能被另一个进程赋予
实现
- turn的初值为0，即刚开始只允许0号进程进入临界区。
- 若P1先上处理机运行，则会一直卡在⑤。直到P1的时间片用完，发生调度，切换P0上处理机运行。代码①不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即使切换回p1，P1依然会卡在⑤，只有P0在退出区将turn改为1后，P1才能进入临界区。
- 因此，该算法
可以实现”同一时刻最多只允许一个进程访问临界区“ - 如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么此时虽然临界区空闲，但一直不允许P1访问，因此，单标志法存在的问题是：违背空闲让进原则
双标志先检查
思想
设置一个布尔数组flag[]，数组中各元素标记各进程是否想进入临界区，true表示想进入， false表示不想进入；每个进程在进入临界区之前先检查当前有没有别的进程想进入临界 区，如果没有，把自身对应的标志flag[i]改为true，之后开始访问临界区
实现
存在的问题：P0进程进入之后，在修改P0为true之前，切换到P1，P1检查无别的进程想进入临界区，故会将P1改为true，导致两个进程都为true，会同时访问临界区，违反了”忙则等待“原则
原因：进入区的检查和上锁两个处理不是一气呵成的。检查后，上锁前可能发生进程切换
双标志后检查
思想
双标志先检查法的改版，先上锁后检查，谁想进谁直接将自身改为true，不关心其他进 程，改为true之后，再检查有没有其他进程想访问
实现
存在的问题：P0想进入，P0改为true，在检查之前切换到P1，P1想进入，改为true，导致两个进程都为true，违背了“空闲让进”和有限等待”，谁都无法访问临界区，产生饥饿现象
原因：进入区的检查和上锁不是一气呵成的
Peterson算法
思想
双标志后检查法的改版，若两个进程都想进入临界区，可以主动让对方优先访问临界区
实现
进入区做了三件事：1. 主动争取 2. 主动谦让 3. 检查对方
Peterson算法解决了空闲让进，忙则等待，有限等待三个原则，但未遵循让权等待原则
进程互斥的硬件实现方法
中断屏蔽方法
原理
利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）
优缺点
优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）
TestAndSet指令(TS指令)
原理
TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。
若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
优缺点
相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
Swap指令
原理
Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
优缺点
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
小结
信号量机制
出现原因
进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）
进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）
在双标志先检查法中，进入区的“检查”、“上锁” 操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；
所有的解决方案都无法实现“让权等待”
1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制
基本介绍
- 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
- 信号量其实就是一个变量 ，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。
- 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
- 一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。
- wait、signal 原语常简称为 P、V操作（来自荷兰语 proberen 和 verhogen）。
整型信号量
- 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
- 与普通整数变量的区别： 对信号量的操作只有三种， 即 初始化、P操作、V操作
记录型信号量
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。
- 中 wait(S)、signal(S) 也可以记为 P(S)、V(S)，这对原语可用于实现系统资源的“申请”和“释放”。
- S.value 的初值表示系统中某种资源的数目。
- 对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value–，表示资源数减1，当 S.value < 0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态—>阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
- 对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态—>就绪态）。
小结
用信号量实现进程互斥、同步、前驱关系
- 一个信号量对应一种资源
- 信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）
- P( S ) —— 申请一个资源S，如果资源不够就阻塞等待
- V( S ) —— 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程
进程互斥实现
进程同步实现
进程同步：要让各并发进程按要求有序地推进。
前驱关系实现
小结
管程
为什么要引入管程
- 信号量机制存在的问题：编写程序困难、易出错
- 能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢？
- 1973年，Brinch Hansen 首次在程序设计语言 (Pascal)中引入了“管程”成分——一种高级同步机制
管程的定义和基本特征
管程是一种特殊的软件模块，有这些部分组成：
局部于管程的共享数据结构说明；
对该数据结构进行操作的一组过程；“过程”其实就是“函数”
对局部于管程的共享数据设置初始值的语句；
管程有一个名字。
管程的基本特征：
局部于管程的数据只能被局部于管程的过程所访问；
一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
每次仅允许一个进程在管程内执行某个内部过程。
由编译器负责实现各进程互斥地进入管程中的过程
管程中设置条件变量和等待/唤醒操作， 以解决同步问题
每次仅允许一个进程在管程内执行某个内部过程。
例1：两个生产者进程并发执行，依次调用了insert 过程…
例2：两个消费者进程先执行，生产者进程后执行…
引入管程的目的无非就是要更方便地实现进程互斥和同步。
需要在管程中定义共享数据（如生产者消费者问题的缓冲区）
需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）
只有通过这些特定的“入口”才能访问共享数据
管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心）
可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
程序员可以用某种特殊的语法定义一个管程（比如: monitor ProducerConsumer …… end monitor;），之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。（封装思想）
Java 中类似于管程的机制
Java 中，如果用关键字 synchronized 来᧿ 述一个函数，那么这个函数同一时间段内只能被一个线程调用
- 每次只能有一个线程进入insert 函数，如果多个线程 同时调用 insert 函数，则后来者需要排队等待
小结
