东风夜放花千树，更吹落，星如雨

---

2.3.1 进程同步，进程互斥

知识总览

什么是进程同步

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系,如等待、传递信息等，引入了进程同步的概念。进程同步是为了解决进程的异步问题。
一个简单的例子来理解这个概念。
例如，让系统计算1 + 2x3，假设系统产生两个进程: 一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后,但实际上操作系统具有异步性,若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生。
异步性：进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

什么是进程互斥

这里的同时是宏观上的共享 微观上依然是交替使用的,互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

知识回顾

2.3.2 进程互斥的软件实现方法

知识总览

如果没有进程互斥

软件实现方法的思想：在进入区设置并检查一些标志 来标明是否有进程在临界区中,若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

单标志法

双标志先检查法

双标志后检查法

Peterson算法

让权等待指的是若是当前这个进程此时进不了临界区，则让出处理机不在CPU上跑

谁最后说了客气话，谁就失去了行动的优先权，类如过年
阿姨:乖，收下阿姨的心意~
你:不用了阿姨,您的心意我领了
阿姨:对阿姨来说你还是个孩子，你就收下吧你:真的不用了阿姨，我已经成年了
结局…

知识回顾

2.3.3进程互斥的硬件实现方法

中断屏蔽方法

TestAndSet指令

下面代码只是表示一种逻辑，不代表真正的TestAndSet指令
执行TSL指令时，它的内部运转逻辑：
假设lock现在为false，代表临界资源A空闲，那么我就可以访问这个资源，同时将lock=true，提醒别的进程，这个临界资源A我正在使用，让他们等等
假设lock为true，代表临界资源正在有人使用，所以我必须等待，并且将lock=true，并不影响什么，所以没关系，只是为了让lock为false时可以上锁，将上锁与检查在一个TSL指令完成。

Swap指令

old是每个进程都要进行的一步，都必须将old=true
分析一下这样做的原因：
因为lock是某一特定临界资源的共享变量，当每一个进程准备访问这个特定的临界资源时，初始化old=true，然后进入while循环进行交换，如果当前lock是false,则交换后old=false,则当前进程可以跳出循环进入临界区代码段，同时因为交换，lock=old=true上锁，不让别的进程来打扰，别的进程会因为lock变为true,一直在while循环等待,当我使用完临界资源，则将lock=false,此时别的进程再交换old和lock就能判断old=false,可以跳出循环，使用临界资源

本节回顾

2.3.4 互斥锁

进程互斥：锁

忙等不是意味着一直占用处理机，当时间片用完依然会释放处理机

2.3.5 信号量机制

本节总览

信号量机制

信号量机制——整形信号量

信号量机制——记录型信号量

本节回顾

2.3.6 用信号量实现进程互斥，同步，前驱关系

知识总览

信号量机制实现进程互斥

信号量机制实现进程同步

前面活动完成后就执行V操作 后面活动执行前就执行P操作

知识回顾

2.3.7 生产者消费者问题

PV操作题目分析步骤:
1．关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2．整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3.设置信号量。并根据题目条件确定信号量初值.(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

能否改变相邻的PV操作的顺序

这里没有将使用产品放入到PV之间是因为放入之后，原则上是可以的，但是对临界资源锁的时间也会变长，对系统的效率造成影响

知识回顾

2.3.8 多生产者多消费者问题

前V后P:同步关系中，前面时间发生之后发生V操作，后面事件发生之前发生P操作

问题描述

关系分析

各个进程之间的PV操作

互斥关系很简单：就是在访问临界资源之后分别对临界变量实行一个P操作 一个V操作，
同步关系：前面事件发生之后我们实行一个V操作，后面事件发生之前执行一个P操作

设置信号量

对于实现互斥关系来说，我们当然需要设置一个初值为1的互斥信号量
对于同步关系我们需要根据具体的情况设置同步变量的值，这里由于刚开始的时候盘中是没苹果的，所以设置apple 设置为0，同样的srange也设置为0 ，刚开始的时候盘子本来就是空的所以设置为1

若是不设置互斥信号量

通过分析我们发现即使不设置专门的互斥变量mutex,也不会出现多个进程同时访问盘中的现象，原因在于，本题中的缓冲区大小为1，在任何时刻，apple,orange,plate 三个同步信号量最多只有一个是1 ，因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利的进入临界区

缓冲区大于一

知识回顾

2.3.9 吸烟者问题

知识回顾

2.3.10读者写者问题

实现

实现2

这里说一下为什么要加mutex。
比如：当count=0时，第一个读者进程执行到p(rw),rw=0,假设此时时间片到了，切换到第二个读者进程,第二个进程发现count=0,则执行p(rw)，但是此时rw=0，于是第二个进程被堵在p（rw）这里，同理，后面的可能会有多个进程堵在p(rw)，只有当第一个进程再次获得时间片，执行count++,让count不为0，然后其他进程就可以直接绕过if直接进行count++来访问文件，但是第三个读者进程和后面的几个可能堵在p(rw)的多个读者进程则必须得等count–为0后才可以再次和写进程竞争来访问文件，对count的访问没有做到一气呵成，会导致本来一些进程一直堵在p（rw）。

实现3

在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有 一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”的情况。
若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的writer()和 reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序

知识回顾

2.3.11哲学家进餐问题

解决方式

方案三

增加一个互斥信号量，使得只有左右筷子都存在的时候才会取，并且取筷子操作一气呵成，若是先进行第一个哲学家，然后进行4号哲学家，则依然可能会拿到一个筷子

知识回顾

2.3.12 管程

知识总览

为什么引入管程？

管程的定义和基本特征

管程解决生产者消费者问题

Java中类似管程的机制

知识回顾

2.4.1 死锁的概念

知识总览

什么是死锁

饥饿，死循环的区别

死锁产生的必要条件

什么时候会发生死锁

死锁的处理策略

知识回顾

2.4.2预防死锁

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

知识回顾

2.4.3 避免死锁（银行家算法）

知识总览

什么是安全序列

银行家算法

安全状态

不安全状态

知识回顾

2.4.4死锁的检测和解除

死锁的检测

死锁的解除

知识回顾

4