操作系统系列内容的学习目录$\to$操作系统学习系列内容汇总。

4. 同步

  协作进程能与系统内的其他执行进程相互影响。协作进程或能直接共享逻辑地址空间（即代码和数据），或能通过文件或消息来共享数据。而共享数据的并发访问可能导致数据的不一致。
  进程可以并发或并行执行。这个过程中可能产生的问题举例：两个进程并发操作变量counter。
  即多个进程并发访问和操作同一数据并且执行结果与特定访问顺序有关，称为竞争条件。为了防止竞争条件，需要确保一次只有一个进程可以操作变量counter。为了做出这种保证，要求这些进程按一定方式来同步。
  问题： 协作进程如何进行进程同步和进程协作。

4.1 临界区问题

  假设某个系统有n个进程{P1，P1…Pn}，每个进程有一段代码，称为临界区，进程在执行临界区时可能修改公共变量。当一个进程在临界区内执行时，其他进程不允许在它们的临界区内执行。即没有两个进程可以在它们的临界区共同执行。
  临界区问题是，设计一个协议以便协作进程。在进入临界区前，每个进程应请求许可。实现这一请求的代码区段称为进入区。临界区之后可以有退出区，其他代码为剩余区。
  典型进程$P_i$的通用结构如下图所示。

  临界区问题的解决方案应满足如下3个要求：
    - 互斥： 进程$P_i$在其临界区内执行，其他进程都不能在其临界区内执行。
    - 进步： 如果没有进程在其临界区内执行，并且有进程需要进入临界区，那么只有那些不在剩余区内执行的进程可以参加选择，以便确定谁能下次进入临界区，而且这种选择不能无限推迟。
    - 有限等待： 从一个进程做出进入临界区的请求直到这个请求允许为止，其他进程允许进入其临界区的次数具有上限。
  用于处理操作系统临界区问题的两种常用方法：抢占式内核和非抢占式内核。抢占式内核允许处于内核模式的进程被抢占，非抢占式内核不允许处于内核模式的进程被抢占。处于内核模式运行的进程会一直运行，直到退出内核模式、阻塞或自愿放弃CPU控制。

4.2 硬件同步

  基于加锁（locking）为前提，即通过锁来保护临界区。通过硬件指令来解决临界区问题。

4.3 互斥锁

  临界区问题基于硬件的解决方案不但复杂，而且不能为程序员直接使用。因此，操作系统设计人员构建软件工具，以解决临界区问题。最简单的工具就是使用互斥锁来保护临界区，从而防止竞争条件。
  一个进程在进入临界区时应得到锁，它在退出临界区时释放锁。函数acquire()获取锁，函数release()释放锁。

  忙等待： 当一个进程在临界区中，任何其他进程在进入临界区时必须不断循环判断。这种互斥锁也称为自旋锁，进程不停的旋转，以等待锁变得可用。忙等待缺点是浪费CPU周期，优点是没有切换上下文。

4.4 信号量

  一个信号量（semaphore）S是一个整型变量。它除了初始化外只能通过两个标准原子操作：wait()和signal()来访问。
  操作wait()最初称为P原语（荷兰语proberen，测试），操作signal()最初称为V原语（荷兰语verhogen，增加）。

  可按如下来定义wait()：

wait(S) {
    while (S <= 0)
        ; // busy wait
    S--;
}

  可按如下来定义signal()：

signal(S){
    S++;
}

  在wait()和signal()操作中，信号量整数值的修改不可分割地执行。也就是说，当一个进程修改信号量值时，没有其他进程能够同时修改同一个信号量的值。另外，对于wait(S)，S整数值的测试（S<=0）和修改(S–)，也不能被中断。

4.4.1 信号量的使用

• 操作系统通常区分计数信号量与二进制信号量。
• 计数信号量的值不受限制，而二进制信号量的值只能是0或1。因此，二进制信号量类似于互斥锁。
• 计数信号量可以用于控制访问具有多个实例的某种资源。信号量的初值为可用资源数量。
• 当进程需要使用资源时，需要对该信号量执行wait()操作（减少信号量的计数）。
• 当进程释放资源时，需要对该信号量执行signal()操作（增加信号量的计数）。当信号量的计数为0时，所有资源都在使用中。之后，需要使用资源的进程将会阻塞，直到计数大于0。

4.4.2 死锁与饥饿

• 具有等待队列的信号量实现可能导致这样的情况：两个或多个进程无限等待一个事件，而该事件只能由这些等待进程之一来产生。这里的事件是由执行操作signal()。当出现这样的状态时，这些进程就为死锁（deadlocked）。
• 假设有一个系统，它有两个进程P0和P1，每个访问共享信号量S和Q，这两个信号量的初值均为1：
  
• 与死锁相关的另一个问题是无限阻塞或饥饿，即进程无限等待信号量。

4.4.3 优先级的反转

• 如果一个较高优先级的进程需要读取或修改内核数据，而且这个内核数据当前正被较低优先级的进程访问(这种串联方式可涉及更多进程)，那么就会出现一个调度挑战。
• 由于内核数据通常是用锁保护的，较高优先级的进程将不得不等待较低优先级的进程用完资源。
• 如果较低优先级的进程被较高优先级的进程抢占，那么情况变得更加复杂。
• 作为一个例子，假设有三个进程，L、M和H，它们的优先级顺序为L<Ｍ<H。假定进程H需要资源R，而R目前正在被进程L访问。通常，进程H将等待L用完资源R。但是，现在假设进程M进入可运行状态，从而抢占进程L。间接地，具有较低优先级的进程M，影响了进程H应等待多久，才会使得进程L释放资源R。
   这个问题称为优先级反转(priority in version) 。它只出现在具有两个以上优先级的系统中，因此一个解决方案是只有两个优先级。然而，这对于大多数通用操作系统是不够的。
   通常， 这些系统在解决问题时采用优先级继承协议(priority-inheritance protocol) 。根据这个协议，所有正在访问资源的进程获得需要访问它的更高优先级进程的优先级，直到它们用完了有关资源为止。当它们用完时，它们的优先级恢复到原始值。在上面的示例中，优先级继承协议将允许进程L临时继承进程H的优先级，从而防止进程M抢占执行。当进程L用完资源R时，它将放弃继承的进程H的优先级，以采用原来的优先级。因为资源R现在可用，进程H，而不是进程M，会接下来运行。

4.5 经典同步问题

  使用信号量来解决同步的问题。
    - 有界缓存问题
    - 读写问题
    - 哲学家就餐问题

4.5.1 有界缓存问题

• 问题：生产者和消费者共享以下数据结构：
  
  假设缓冲池有n个缓冲区，每个缓冲区可存一个数据项。信号量mutex提供缓冲池访问的互斥要求，并初始化为1。信号量empty和full分别用于表示空的和满的缓冲区数量。信号量empty初始化为n，而信号量full初始化为0。
• 生产者进程的代码：
  
• 消费者进程的代码：
  

4.5.2 哲学家就餐问题

• 哲学家只做两件事：思考和吃饭。饥饿的时候需要拿起相邻的两个叉子才能进餐，但一个哲学家一次只能拿起一个叉子。吃完后，会放下两个叉子，继续思考…吃饭…思考…
   如果所有哲学家都同时拿起自己右手边的叉子且不愿放下，会发生死锁，则所有哲学家都会饿死。
   解决方案： 每个叉子都用一个信号量来表示。一个哲学家通过执行wait()操作试图获取相应的叉子，他会通过执行signal()操作以释放相应的叉子。因此，共享数据为semaphore fork[5];，其中，fork的所有元素都初始化为1。
   这种方式可能导致死锁问题。死锁问题的补救措施：
    - 允许最多4个哲学家同时坐在桌子上。
    - 只有一个哲学家的两个叉子都可用时，才能拿起它们。
    - 使用非对称解决方案，即单号的哲学家先拿起左边的叉子，接着右边的叉子。而双号的哲学家先拿起右边的叉子，接着左边的叉子。
   解决方案应保证：没有一个哲学家会饿死。没有死锁的解决方案不一定能消除饥饿的可能性。

4.6 管程

  管程在功能上和信号量及PV操作类似，属于一种进程同步互斥工具，但是具有与信号量及PV操作不同的属性。

4.6.1 管程的定义

  管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块。

4.6.2 管程的组成部分

  1）局部于管程的共享变量；
  2）对数据结构进行操作的一组过程；
  3）对局部于管程的数据进行初始化的语句。

4.6.3 管程的属性

  共享性： 管程可被系统范围内的进程互斥访问，属于共享资源。
  安全性： 管程的局部变量只能由管程的过程访问，不允许进程或其它管程直接访问，管程也不能访问非局部于它的变量。
  互斥性： 多个进程对管程的访问是互斥的。任一时刻，管程中只能有一个活跃进程。
  封装性： 管程内的数据结构是私有的，只能在管程内使用，管程内的过程也只能使用管程内的数据结构。进程通过调用管程的过程使用临界资源。

4.6.4 引入管程的原因

  信号量机制的缺点：进程自备同步操作，P(S)和V(S)操作大量分散在各个进程中，不易管理，易发生死锁。1974年和1977年，Hore和Hansen提出了管程。
  管程的特点：管程封装了同步操作，对进程隐蔽了同步细节，简化了同步功能的调用界面。用户编写并发程序如同编写顺序(串行)程序。
  引入管程机制的目的：1、把分散在各进程中的临界区集中起来进行管理；
            2、防止进程有意或无意的违法同步操作；
            3、便于用高级语言来书写程序，也便于程序正确性验证。