操作系统——进程与线程(3)

本系列文章为408考研操作系统知识点整理仅涉及到一些重要的考研知识点并不是完全系统全面的知识，参考书目和视频资料：汤小丹计算机操作系统（第四版），操作系统考研复习指导，B站王道考研操作系统视频课。

2.3.1 同步和互斥的基本概念

进程同步

进程同步：进程同步又叫做直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调工作次序而产生一种制约关系

进程互斥

前面章节中提到了操作系统四大特征中的共享，其中有一种实现共享的方式叫做互斥共享：当进程访问某个资源时，必须先提出请求，若此时该资源空闲，则系统并将其分配给进程A使用，此后有其他进程也要访问该资源时，只要没有用完就必须等待。当且仅当进程A访问并释放资源后，才运行另一个进程对资源进行访问。这一段资源称之为临界资源，临界资源的访问过程分为4个部分
进入区：负责检查是否可以进入临界区，如果可以进入，则应该设置正在问临界资源标识，也就是上锁，以防止其他进程同时进入
临界区：访问临界资源的那段代码
退出区：负责接触正在访问临界资源标识，也就是解锁
剩余区：做其他处理

进程互斥：进程互斥叫做间接制约关系，它是指当一个进程访问某临界资源时，另一个想要访问该刻临界资源的进程必须等待。当前访问临界资源的进程访问结束后，并释放资源后，另一个进程才可以问。为禁止两个进程同时进入临界区，同步机制应遵循以下原则
空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待：对请求访问的进程，应该保证能在有限时间内进入临界区，也就是不能饥饿
让权等待：当进程不能进入临界区时，应该立即释放处理机，防止进程处于忙等待状态（互斥机制可以不遵循让权等待准则）

2.3.2 实现临界区互斥的软件方法

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另外一个进程，每个进程进入临界区的权限只能被另一个进程所赋予，该算法可以实现同一时刻最多只允许一个进程访问临界区

算法缺陷：违背了“空闲让进”原则。如果P0如果一直不访问临界区，那么虽然临界区空闲，但却不允许P1访问

双标志法先检查

算法思想：该算法会设置一个布尔型的数组flag[],用于标记各进程是否想要进入临界区，比如flag[0]=true"表示0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有则把自身对应的标志设置为true,之后开始访问临界区。

算法缺陷：违背了“忙则等待”原则。因为在这种算法下，两个进程是并发的，并发导致异步，意味着两个进程可能会同时访问临界区

双标志法后检查

双标志先检查法是先检查后上锁，这两个操作并非原子性操作，因此一定会导致两个进程同时访问临界区，所以我们可以先上锁后检查，具体实施和上一个算法基本一致，只不过把检查放在后面了

算法缺陷：违背了“空闲让进”原则和“有限等待”原则。因为在这种算法可能会导致两个进程都无法进入临界区，从而产生饥饿现象。

Peterson算法

算法思想：为了防止两个进程为了进入临界区而无限期等待，又设置了一个变量turn,每个进程先设置自己的标志后再设置turn标志，再同时检测另一个进程状态标志和不允许进入标志，以保证两个进程同时要求进入临界区时，只允许一个进程进入临界区。

算法优点：遵循了空闲让进、忙侧等待、有限等待这三个原则
算法缺陷：相较于前三种算法来说，是比较好的，但是还是有缺陷，未能遵循让权等待的原则。即便P不能进入临界区，它还是会卡在while循环，不能释放处理机，使处理机处于了忙等状态。

2.3.3 实现临界区互斥的硬件方法

中断屏蔽方法

思想：当一个进程正在使用处理机执行它的临界区代码时，为了防止其他进程进入临界区进行访问的，直接“暴力的”禁止一切中断发生或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换

优点：简单、高效
缺点：不适用于多处理机，限制了处理机交替执行程序的能力，因比执行的效率会明显降低；且只适用于内核进程，不适用于用户进程（因为开关中断指令属于特权指令）

TestAndSet指令(TSL)

思想：可以为每个临界资源设置一个共享布尔变量lock,lock=true表示正在被占用，初值设为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock,如果有进程在临界区，则重复检查，直到进程退出。

TestAndSet指令：这是一个原子操作，执行过程中绝对不会被中断，使用硬件实现。其功能是读出指令标志后把该标志设为true。

优点：相比软件方法，TSL把上锁和检查操作使用硬件的方式编程了原子操作。所以实现简单，不会像软件实现那样产生逻辑漏洞
缺点：不满足让权等待，暂时无法进入临界区的进程会占用CPU并循环执行TSL,使CPU忙等。

swap指令

思想：可以为每个临界资源设置一个共享布尔变量lock,lock=true表示正在被占用，初值设为false；然后在每个进程中再设置一个局部变量key,，用于和lock交换信息。在进入临界区之前，先利用swap指令交换lock与key的内容，然后检查key的状态，有进程在临界区时，重复交换和检查过程，直到进程退出。

1.如果刚开始临界区就已经被上锁，那么先将其记录在key上，也即key=true,那么此时while循环条件满足，一直执行swap,直到此时处在临界区的进程退出时将lock设为false,交换给key,然后结束循环
2.如果刚开始临界区没有被上锁，那么先将其记录在key上，也即key=false,那么此时while循环条件不满足，直接进入临界区。

优点：实现简单，不会像软件实现那样产生逻辑漏洞，适用于多处理机环境
缺点：不满足让权等待，暂时无法进入临界区的进程会占用CPU并循环执行TSL,使CPU忙等

2.3.4 信号量机制

信号量：本质就是一个变量（分为整形和记录型两种），表示系统中某种资源的数量。控制信号量有两种原子操作：
P操作(wait(S)原语)：这个操作会把信号量减去1，相减后如果信号量<0则表示资源已经被占用，进程需要阻塞；相减后如果信号量>0，则表明还有资源可以使用，进程可以正常执行
V操作(signal(S)原语)：这个操作会把信号量加上1，相加后如果信号量≤0，则表明当前有阻塞中的进程，于是会把该进程唤醒；相加后如果信号量>0，则表明当前没有阻塞中的进程

整型信号量：使用一个整型变量作为信号量，用来表示系统中某种资源的数量。比如某种资源S初始为1

缺陷：不满足让权等待，会发生忙等

记录型信号量：除了需要使用一个用于代表资源数目的整形变量value外，还需要增加一个进程链表L,用于链接所有等待该资源的进程，使用一个指针指向。其用于记录的数据结构为：

而signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增l,因此有S.value+。

若加1后仍是S.value≤0，则表示在S.L中仍有等待该资源的进程被阻塞，因此还应调用wakeup
原语，将S.L中的第一个等待进程唤醒。

2.3.5 用信号量实现进程互斥、同步和前驱关系

利用信号量实现同步

前V后P：在前操作后执行V(S)，在后操作前执行P(S)。

利用信号量实现互斥

1：分析并发进程的关键活动，划定临界区
2：设置互斥信号量mutex,初值1
3：在临界区之前执行P操作
4：在临界区之后执行V操作

1：对不同的临界资源需要设置不同的互斥信号量。例如P1和P2进程争抢A这种资源，那么就可以设置互斥信号量为mutex1,P3和P4进程争抢B这种资源，那么就可以设置互斥信号量为mutex2

2: 一定注意P、V操作必须成对出现
缺少P操作：不能保证临界资源的互斥访问
缺少V操作：导致资源永远不会释放，继而等待进程永远不会被唤醒

利用信号量实现前驱关系

所谓前的驱关系就是要实现多组进程的同步关系。

遵循前V后P：在前操作后执行V(S)，在后操作前执行P(S)。

2.3.6 管程(Monitor)及条件变量

管程(Monito):它是一种特殊的软件模块，由以下部分组成：
局部于管程的共享数据结构说明——可以理解为类的成员
对该数据结构进行操作的一组过程（函数）——可以理解为类的方法
对局部于管程的数据设置初始值的语句——可以理解为类的构造函数
管程有一个名字——可以理解为类名

管程是一个代表共享资源的数据结构，进程对共享资源的申请、释放等操作是通过过程来实现的（过程就是对这一数据结构的操作)，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。

局部于管程的数据只能被局部的过程所问——可以理解为类成员变量只能被类方法访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据——可以理解为访问要合法进行
每次仅允许一个进程在管程内执行某个内部过程

条件变量condition

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程，为此，将阻塞原因定义为条件变量condition
如果一个进程被阻塞的原因有多个，那么就设置多个条件变量，而每一个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对于条件变量的操作只有两种：wait和signal
x.wait：当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程
x.signal：当x对应的条件发生了变化，则调用x.signal,唤醒一个因x条件而阻塞的进程

条件变量和信号量的比较：
相似点：条件变量的wait/signal操作类似于信号量的PV操作，可以实现进程的阻塞/唤醒。
不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。