王道操作系统第2章-进程管理-进程的同步与互斥
第2章-进程管理-进程的同步与互斥
进程同步、进程互斥
进程互斥的软件实现方法
单标志法
双标志先检查法
双标志后检查法
Peterson算法
进程互斥的硬件实现方法
中断屏蔽方法
TestAndSet指令
Swap指令
互斥锁
信号量机制
整型信号量
记录型信号量
用信号量机制实现进程互斥、同步、前驱关系
信号量机制实现进程互斥
信号量机制实现进程同步
信号量机制实现前驱关系
生产者、消费者问题
多生产者-多消费者问题
吸烟者问题
读者写者问题
哲学家进餐问题
管程
用管程解决生产者消费者问题
Java中类似于管程的机制
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要再某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作
在之前的学习中我们知道：进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免地需要共享一些系统资源（比如内存、打印机、摄像头）
两种资源共享方式：
互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（如摄像头、打印机）都是临界资源。此外还有许多变量、数据、内存缓冲区都属于临界资源。
对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源
do {
entry section;//进入区，负责检查是否可以进入临界区，若可进入，则应设置“正在访问临界资源的标志”（可理解为上锁），以阻止其他进程同时进入临界区
critical section;//临界区，访问临界资源的那段代码
exit section;//退出区，负责解除正在访问临界资源的标志（可理解为解锁）
remainder section;//剩余区，做其他处理
}
注意：
临界区是进程中访问临界资源的代码段
进入区和退出区是负责实现互斥的代码段
临界区也可称为“临界段”
为了实现对临界资源的互斥访问，同时保证系统整体性能，需遵循以下原则
空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待
进程互斥的软件实现方法
单标志法
算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予
单标志法只能按P0进程\rightarrowP1进程\rightarrowP0进程\rightarrowP1进程\rightarrow \cdots这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时运行进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。
也就是说，如果自己本次用完后临界区谦让给别人，但是别人一直不用，自己待会又需要用了，此时即使临界区空闲自己也用不了了。
因此，单标志法的主要问题：违背“空闲让进”原则
双标志先检查法
算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0]=true表示0号进程P0现在想要进入临界区。每个进程在进入临界区前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区
若两个程序并发执行，可能按照①⑤②⑥③⑦\cdots的顺序执行，P0和P1会同时访问临界区。
因此，双标志先检查法的主要问题是：违反“忙则等待”的原则。原因在于，进入区的“检查”和“上锁”这两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换
双标志后检查法
算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作无法一气呵成，因此导致了两个进程同时进入临界区的问题，因此人们又想到先“上锁”后“检查”的方法来避免上述问题
若两个程序并发进行，可能按照①⑤②⑥\cdots的顺序执行，P0和P1都无法进入临界区。
因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，因此各进程都长期无法访问临界资源而产生“饥饿”现象
Peterson算法
算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“谦让”，做一个有礼貌的过程
Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则，
Peterson算法相较于之前三种软件解决方案来说是最好的，但依然不够好
进程互斥的硬件实现方法
中断屏蔽方法
利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）
优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）
TestAndSet指令
检查TS指令，也有称TestAndSetLock指令，或TSL指令
TSL指令是用硬件实现的，执行的过程中不允许被中断，只能一气呵成
下面是TestAndSet指令用C语言描述的逻辑：
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”
Swap指令
有的地方称为Exchange执行，或简称XCHG指令
其实与TestAndSet指令差不多
Swap指令是用硬件实现的，执行的过程中不允许被中断，只能一气呵成
下面是Swap指令用C语言描述的逻辑：
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”
互斥锁
解决临界区最简单的工具就是互斥锁（mutex lock），一个进程在进入临界区时应获得锁，在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁
每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放
acquire(){
while(!available);//忙等待
available = false;//获得锁
}
release(){
available = true;//释放锁
}
acquire()和release()的执行必须时原子操作，因此互斥锁通常采用硬件机制来实现
互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享一个CPU时，就浪费了CPU周期。因此互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行
需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如TSL指令、swap指令、单标志法
特性：
需忙等，进程时间片用完才下处理机，违反“让权等待”
优点：等待期间不需要切换进程上下文，多处理器系统中，若上锁时间短，则等待代价很低
常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
不太适用于单处理机系统，在一个时间片内忙等的过程中不可能解锁
信号量机制
回顾与反思： 进程互斥的四种软件实现方式：单标志法、双标志先检查、双标志后检查、Peterson算法 进程互斥的三种硬件实现方式：中断屏蔽方法、TS/TSL指令、Swap/XCHG指令
在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致两个进程都有可能同时进入临界区的问题
所有的解决方案都无法实现“让权等待”
1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便地实现了进程互斥、进程同步
信号量其实就是一个变量（可以是一个整数，或者更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的，软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题
一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数
wait、signal原语通常简称为P、V操作（来自荷兰语），因此常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)
整型信号量
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量 与普通整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作
记录型信号量
整型信号量的缺陷是存在“忙等”的问题，因此提出了记录型信号量，即用记录型数据结构表示的信号量
wait(S)与Signal(S)也可记为P(S)和V(s)，这对原语可用于实现系统资源的“申请”和“释放”
S.value的初值表示系统中某种资源的数目
对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value--，表示资源数-1，当S.value<0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞（当前运行的进程从运行态\rightarrow阻塞态），主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象
对信号S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数+1，若+1后仍是S.value<=0，表示依然有进程在等待该资源，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态\rightarrow就绪态）
用信号量机制实现进程互斥、同步、前驱关系
信号量的值=这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）
P(S)——申请一个资源S，如果资源不够就阻塞等待 V(S)——释放一个资源S，如果有进程在等待该资源，则唤醒一个进程
信号量机制实现进程互斥
分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
设置互斥信号量mutex，初值为1
在进入区P(mutex）申请资源
在退出区V(mutex）释放资源
信号量mutex表示“进入临界区的名额” 对不同的临界资源需要设置不同的互斥信号量
P、V操作必须成对出现。缺少P(mutex）就不能保证临界资源的互斥访问。缺少V(mutex）会导致资源永不被释放，等待进程永不被唤醒
//P操作
void wait(semaphore S) {
S.value--;
if(S.value<0){
block(S.L);
}
}
//V操作
void signal(semaphore S){
S.value++;
if(S.value<=0){
wakeup(S.L);
}
}
信号量机制实现进程同步
进程同步：要让各并发进程按要求有序地推进
P1(){
代码1;
代码2;
代码3;
}
P2(){
代码4;
代码5;
代码6;
}
比如，P1、P2并发执行，由于存在异步性，因此两者交替推进的次序是不确定的 若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行
这就是进程同步问题，让本来异步并发进程互相配合，有序推进
用信号量机制实现进程同步：
分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
设置同步信号量S，初值为0
在“前操作”之后执行V(S)
在“后操作”之前执行P(S) 口诀：前V后P
信号量机制实现前驱关系
前驱关系本质上就是多级同步
生产者、消费者问题
问题描述：系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（这里的“产品”理解为某种数据） 生产者、消费者共享一个初始为空、大小为n的缓冲区
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待
缓冲区是临界资源，各进程必须互斥地访问，否则可能出现数据覆盖等问题
PV操作题目分析步骤
关系分析。找出题目中描述的各个进程，分析他们之间的同步、互斥关系
整理思路。根据各进程的操作流程确定P、V
设置信号量，并根据题目条件确定信号量初值（互斥信号量初值一般为1，同步信号量的初值要看对应资源的初始值为多少）
思考：能否改变相邻P、V操作的顺序？
不能改变P操作的顺序，否则会产生“死锁”。实现互斥的P操作一定要在实现同步的p操作之后 可以改变V操作顺序，因为V操作不会导致进程阻塞
多生产者-多消费者问题
问题描述：桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子等着吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出水果
在本题中，即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象。 原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个时1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利进入临界区
如果盘子（缓冲区）容量为2：父亲P后可以访问盘子，母亲P后也可以访问盘子，此时父亲网盘子里放苹果的同时母亲也往盘子里放橘子，于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区数据相互覆盖的情况，因此，如果缓冲区大小大于1，就必须专门设置一个互斥信号量mutex来保证互斥访问缓冲区。如果缓冲区大小等于1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然这不是绝对的。
要从“事件”的角度考虑
吸烟者问题
问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放在桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料在桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）
本质上这题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”
吸烟者问题可以为我们解决“可以生产多个产品的单生产者问题”提供一个思路 使用一个整型变量i来实现“轮流让各个吸烟者吸烟”这个过程的
读者写者问题
问题描述：有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：
运行多个读者可以同时对文件执行读操作
只允许一个写者往文件中写信息
任一写者在完成写操作之前不允许其他读者或写者工作
写者执行写操作前，应让已有的读者和写者全部退出
与消费者进程不同，读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可以同时访问共享数据
由第一个读进程负责给读之前“加锁”，最后一个读进程负责读完后“解锁”，期间不能允许写进程访问。使用互斥信号量mutex保证对count变量的互斥访问
为了实现读写公平而不是上面这种的读优先，可以再加一个互斥信号量
总结：核心思想在于设置了一个计数器count用来记录当前正在访问的共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理
另外，对count变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，应该想到使用互斥信号量
哲学家进餐问题
问题描述：一张圆桌上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的经历用于思考和进餐。哲学家在思考时并不影响他人，只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以进餐，当进餐完毕后，放下筷子继续思考
哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时次有两个临界资源，因此就有“死锁”问题的隐患。
如果遇到一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题目中给出的进程之间是否会发生循环等待，是否会发生死锁。
管程
信号量机制存在的问题：编写程序困难、易出错
管程是一种特殊的软件模块，有这些部分组成（类似于面向对象程序设计）：
局部于管程的共享数据结构说明
对该数据结构进行操作的一组过程（也就是函数）
对局部于管程的共享数据设置初始值的雨具
管程有一个名字
管程的基本特征：
局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
用管程解决生产者消费者问题
引入管程的目的无非就是要更方便地实现进程互斥和同步
需要在管程中定义共享数据（如生产者消费者问题的缓冲区）
需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区中取出产品）
只有通过这些特定的“入口”才能访问共享数据
管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只有一个进程在访问缓冲区。注意，这种互斥特性是由编译器负责实现的，程序员不用关心）
可以在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
程序员可以用某种特殊的语法定义一个管程（比如上面的monitor ProducerConsumer)，之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。
Java中类似于管程的机制
使用synchronized
