进程同步——操作系统笔记

一、进程的同步和互斥

1、进程的同步

  例如：进程相互通信时，使用管道通信，必须先进行写数据再进行读数据。但是读进程和写进程并发地运行，由于并发必然导致异步性。因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据 → 读数据”的顺序来执行的。这就造成了异步问题，也是“进程同步”所讨论的内容。

  同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2、进程的互斥

  各个并发执行的进程不可避免的需要共享一些系统资源（比如：内存、打印机等）。资源共享方式分为：

• 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。
• 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问。

  我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如：摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。对临界资源的访问，必须互斥地进行。

  互斥亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

（1）临界资源的互斥访问

  对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

  临界区是进程中访问临界资源的代码段。 进入区和退出区是负责实现互斥的代码段。 临界区也可称为“临界段”。

  为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1. 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
3. 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
4. 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

3、总结

二、进程互斥的软件实现方法

1、单标志法

  算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。算法设计如下：

  turn 的初值为 0，即刚开始只允许 0 号进程进入临界区。 若 P1 先上处理机运行，则会一直卡在 ⑤ 。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。 代码 ① 不会卡住 P0，P0 可以正常访问临界区，在 P0 访问临界区期间即使切换回 P1，P1 依然会卡在 ⑤。 只有 P0 在退出区将 turn 改为 1 后，P1 才能进入临界区。

  因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”。但是这种算法，只能按 P0→P1→P0→P1→… 这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是 P0，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问。因此，单标志法存在的主要问题是：违背“空闲让进”原则。

2、双标志先检查

  算法思想：设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如：“flag[0]=ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。算法设计如下：

  因为进程并发执行的，所以若按照 ①⑤②⑥③⑦…. 的顺序执行，P0 和 P1 将会同时访问临界区。因此，双标志先检查法的主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

3、双标志后检查

  算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查” 的方法，来避免上述问题。算法设计如下：

  若按照 ①⑤②⑥… 的顺序执行，P0 和 P1 将都无法进入临界区。因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。 两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

4、Peterson 算法

  算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。

  Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。Peterson 算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

5、总结

三、进程互斥的硬件实现方法

1、中断屏蔽方法

  录用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）。

• 关中断：关中断后即不允许当前进程被中断，也必然不会发生进程切换；
• 临界区；
• 开中断：直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区。

优缺点：

• 优点：简单、高效。
• 不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）。

2、TestAndSet 指令

  TestAndSet 简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令。TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用 C 语言描述的逻辑：

  若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优缺点：

• 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞。适用于多处理机环境。
• 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致“忙等”。

3、Swap 指令

  Swap 有的地方也叫 Exchange 指令，或简称 XCHG 指令。Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用 C 语言描述的逻辑：

  逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

  优缺点和 TestAndSet 指令一样。

4、总结

四、信号量机制

  1965年，荷兰学者 Dijkstra 提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制。信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

  原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

  一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。wait、signal 原语常简称为 P、V 操作（来自荷兰语 proberen 和 verhogen）。因此，做题的时候常把 wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)。

1、整型信号量

  用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。与普通整数变量的区别：对信号量的操作只有三种，即：初始化、P 操作、V 操作。

  某计算机系统中有一台打印机… 存在的问题：不满足“让权等待”原则，会发生“忙等”。

2、记录型信号量

  整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

  wait(S)、signal(S) 也可以记为 P(S)、V(S)，这对原语可用于实现系统资源的“申请”和“释放”。S.value 的初值表示系统中某种资源的数目。信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）；P(S)：申请一个资源 S，如果资源不够就阻塞等待；V(S)：释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。

  对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value--，表示资源数减 1，当 S.value<0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态 → 阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了“让权等待”原则， 不会出现“忙等”现象。

  对信号量 S 的一次V操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加 1，若加 1 后仍是 S.value<=0，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态 → 就绪态）。

3、总结

五、信号量机制实现进程互斥、同步、前驱关系

1、实现进程互斥

  进程互斥就是控制各并发进程对临界资源的访问。

• 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）；
• 设置互斥信号量 mutex，初值为1；
• 在进入区 P(mutex)——申请资源；
• 在退出区 V(mutex)——释放资源。

  注意：对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少 P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。

2、实现进程同步

  进程同步就是让各并发进程按要求有序地推进。

• 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作；
• 设置同步信号量 S，初始为 0；
• 在“前操作”之后执行 V(S)；
• 在“后操作”之前执行P(S)；

  信号量 S 代表“某种资源”，刚开始是没有这种资源的。P2 需要使用这种资源，而又只能由P1 产生这种资源。

3、实现进程的前驱关系

  其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）因此，

• 要为每一对前驱关系各设置一个同步信号量；
• 在“前操作”之后对相应的同步信号量执行 V 操作；
• 在“后操作”之前对相应的同步信号量执行 P 操作

  进程 P1 中有句代码 S1，P2 中有句代码 S2，P3 中有句代码 S3 …… P6 中有句代码 S6。这些代码要求按如下前驱图所示的顺序来执行：

4、总结