ProcessSync

进程的同步

定义 Definition

每一个进程具有顺序性，但是在多道程序设计系统中，多个进程要竞争，轮流占用处理器。
有两个进程 A 和 B，它们各自顺序执行时的操作序列如下：
进程 A ： a1，a2，a3，…，am
进程 B ： b1，b2，b3，…，bm
在多道程序设计系统中，处理器可能执行的操作序列
a1， b1 ，a2， b2 ，a3， b3 …
a1， a2， b1 ，a3 ，b2 ，b3 …

进程的并发性:在一个进程的工作没有完成之前，另一个进程就可以开始工作，这些进程就称为可同时执行的。或者称它们具有并发性，并且把可同时执行的进程称为并发进程。

• 如果一个进程的执行不影响另一个进程的执行结果，也不依赖另一个进程的进展情况，即它们是各自独立的，则称这些进程相互之间是无关的。
• 如果一个进程的执行要依赖其他进程的进展状况，或者可能会影响其他进程的执行结果，则说这些进程是有交互的。
  • 对于有交互的并发进程来说，并发会破坏“封闭性”和“可再现性”

进程互斥:多个进程不能同时使用同一个资源，某个进程使用该资源时，其他进程必须等待。
进程同步:多个进程的调用存在时序关系，某些进程的执行必须先于另一些进程。
进程通信:多个进程之间传递消息。

问题引入 Intro

由于进程交替修改了共享变量造成结果可能不正确。

     生产者                           消费者
 register1∶ = counter;             register2∶= counter;
 register1∶= register1+1;         register2∶ = register2-1;
 counter∶= register1;               counter∶ = register2;
假设：counter的当前值是5。
无论生产者先执行，还是消费者先执行，结果都是5.
但是，如果按下述顺序执行：
         register1 ∶  = counter;               (register1 = 5)
         register1 ∶  = register1 + 1;        (register1 =6)
         register2 ∶  = counter;               (register2 = 5)
         register2 ∶  = register2 - 1;         (register2=4)
         counter  ∶  = register 1;             (counter=6)
         counter  ∶  = register2;               (counter=4)
Counter的值最终为4。
两次结果不一致，程序执行失去了再现性

有交互的并发进程执行时出现与时间有关(time-dependent,即与进程调度的顺序有关)的错误，其根本原因是对共享资源（变量）的使用不受限，为了使并发进程能正确地执行，必须对共享变量的使用加以限制。

进程竞争资源首先必须解决“互斥”问题。某些资源必须互斥使用，如打印机、共享变量、表格、文件等。这类资源又称为临界资源 critical resource，访问临界资源的那段代码称为临界区 critical section。
任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。

可把一个访问临界资源的循环进程描述如下：

repeat
    entry section
    critical section
    exit section
    remainder section
until false

<entry section>:判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，
阻止其它后来的进程进入临界区。
<critical section>:进入临界区，使用临界资源。
<exit section>:当临界区内的进程执行完毕并退出临界区时，在“退出区”修改临界区使用标志，
并负责唤醒阻塞队列中的一个进程，让其进入临界区。
<remainder section>:其它代码

阻塞队列 Blocking Queue:当一个进程试图进入临界区，而临界区已经被其它进程占用时，该进程必须等待，直到临界区空闲为止。这些等待进程的队列称为阻塞队列。
死锁 Deadlock:当两个或多个进程互相等待对方释放资源，而导致它们都无法继续执行时，称为死锁。

临界区使用原则(互斥条件)

1. 空闲让进 Entry Allowed WHen Free:如果临界区空闲，则只要有进程申请就立即让其进入
2. 忙则等待 Bust Then Wait:每次仅允许一个进程处于临界区
3. 有限等待 Limited Waiting:进程只能在临界区内逗留有限时间，不得使其他进程在临界区外无限期等待
4. 让权等待 Yeilding While Waiting:当进程不能进入自己的临界区时，应立即释放处理机，以免进程处于“忙等”状态

信号量 Semaphore

1965 年，荷兰的 E.W.Dijkstra 提出了信号量同步机制用于进程同步,现广泛应用于存在临界资源和临界区控制的场合
信号量是一个一般的锁,信号量即信号的数量;开锁实际上就是发一个信号,等待锁打开就是等待一个信号
锁: {0,1} 信号量: {-∞, … , -2, -1, 0, 1, 2, … , ∞}

信号量按照功能来分：

• 互斥信号量：用于申请或释放资源的使用权，常初始化为 1。
• 资源信号量：用于申请或归还资源，可以初始化为大于 1 的正整数，表示系统中某类资源的可用个数。
  按照信号量机制的发展分为：
• 整形信号量
• 记录型信号量
• AND 型信号量
• 信号量集

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaphores are a type of synchronization primitive. A trivial semaphore is a plain variable that is changed (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.
The semaphore concept was invented by Dutch computer scientist Edsger Dijkstra in 1962 or 1963, when Dijkstra and his team were developing an operating system for the Electrologica X8. That system eventually became known as the THE multiprogramming system.

两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以“向前推进”的信号（被唤醒）。相应地，将实现信号灯作用的变量称为信号量。

整形信号量 Integer Semaphore

定义为一个整形量, 用来表示空闲资源的数目;仅能通过两个标准的原子操作 wait(s),signal(s)来访问它,又称为P 操作和 V 操作

• Proberen(荷兰语，意为“尝试”): wait(s) 操作用于申请资源（或使用权），进程执行 wait 原语时，可能会阻塞自己；
  while S <= 0 do no-op; S--; // 申请资源
• Verhogen(荷兰语，意为“增加”): signal(s)操作用于释放资源（或归还资源使用权），进程执行 signal 原语时，有责任唤醒一个阻塞进程。
  S++; // 释放资源

Note

1. 必须成对使用 wait和 signal原语
2. wait、signal 原语不能出现次序错误、重复或遗漏
   • 遗漏 wait 原语则不能保证互斥访问
   • 遗漏 signal 原语则不能在使用临界资源之后将其释放

记录型信号量 Record Semaphore

记录型信号量机制，是一种不存在忙等现象的进程同步机制。
操作系统内核以系统调用形式提供 wait和 signal原语，应用程序通过该系统调用实现进程间的互斥。
工程实践证明，利用信号量方法实现进程互斥是高效的，一直被广泛采用。

记录型信号量的数据结构

#include <stdio.h>
#include <stdlib.h>

// 链表节点，用于表示等待队列中的进程
typedef struct Node {
    int pid;  // 进程ID
    struct Node* next;  // 指向下一个节点的指针
} Node;

// 记录型信号量
typedef struct {
  // value的初值表示系统中某类资源的数目， value的初始值>1时，称为资源信号量， value的初始值=1时，称为互斥信号量
    int value;
    Node* listOfProcess;  // 信号量的阻塞队列
} RecordSemaphore;

“忙等”（Busy Waiting）是一种进程同步策略中的现象，也被称为”自旋等待”。当一个进程试图进入一个被其他进程占用的临界区时，如果使用了忙等策略，那么这个进程会在一个循环中不断检查临界区是否可用，直到它变为可用状态。换句话说，进程在等待期间保持活跃，并消耗 CPU 时间，而不是被挂起或转移到等待状态。
虽然忙等可以在某些情况下（如等待时间预期非常短）提供很好的响应时间，但它通常被视为一种效率低下的策略，因为它浪费了 CPU 的计算能力，尤其是在等待时间较长的情况下。
与此相反，记录型信号量机制（Blocking or Sleeping Semaphore Mechanism）允许进程在等待进入临界区时进入睡眠状态，从而不消耗 CPU 时间。当临界区可用时，进程会被唤醒。这种方法更有效，但可能导致上下文切换的开销，因为系统需要在运行和等待的进程之间切换。

记录型信号量的 P，V 操作 wait(s)和 signal(s)

s.value>=0 时，s.queue 为空；
s.value<0 时，s.value 的 绝对值为 s.queue 中等待进程的个数
s.value 初始值为 1 时，称为互斥信号量；s.value 初始值>1 时，称为资源信号量。
当仅有两个并发进程共享临界资源时，互斥信号量仅能取值 1、0、－1。其中，

• s.value=1, 表示无进程进入临界区
• s.value=0，表示已有一个进程进入临界区
• s.value=-1,则表示已有一进程正在等待进入临界区
  当用 s 来实现 n 个进程的互斥时，s.value 的取值范围为 1 ～-(n-1)

void wait(RecordSemaphore* s) {
    s->value--;
    if (s->value < 0) {
        block(s->listOfProcess); //进程阻塞, 进入S.L队列；
    }
}
void singal(RecordSemaphore* s) {
    s->value++;
    if (s->value <= 0) { // s->value=0时,则在s->value++之前value=-1,即有1个进程在等待
        wakeup(s->listOfProcess); // 唤醒阻塞队列中的一个进程
    }
}

AND 型信号量 AND Semaphore

如果一个进程需要事先获得一个或多个共享资源后才能执行任务。例如：

process A:                 process B:
wait(Dmutex);            wait(Emutex);
wait(Emutex);             wait(Dmutex);

最后，进程 A 和 B 就处于僵持状态，在无外力作用下，两个进程都无法从僵持状态中解脱出来，这此 A 和 B 进入死锁状态。

AND 同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全都地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。
原子操作：所有资源要么全部分配到进程，要么一个也不分配 .
在 wait 操作中，增加了一个“AND”条件，故称为 AND同步，或称为 同时wait操作.

void Swait(S1, S2, …, Sn)	{ //P原语；
  if (S1 ≥1 and S2 ≥ 1 … Sn ≥ 1) {//满足资源要求时的处理；
    for (i = 1; i <= n; ++i){
      // wait的处理是s先减1，再判断是否<0，若是就进入阻塞队列。如果要不阻塞，则s的初始值需要>=1
      // Swait与wait的处理不同，这里是在确信可满足资源要求时，才进行减1操作
      Si=Si-1;
    }
  } else {
    /*某些资源不够时的处理；
    进程进入第一个小于1的信号量的阻塞队列 ;
    恢复PC寄存器为Swait开始时的状态；*/
  }
}

void  Ssignal(S1, S2, …, Sn){
  for (i = 1; i <= n; i++){
    Si++; //释放占用的资源；
    for (each process P waiting in Si.L){
      //检查每种资源的阻塞队列中的所有进程；
      //从阻塞队列Si.queue中取出进程P;
      P = Si.queue.getHead();
      if(判断P是否通过Swait中的测试){//注:与signal不同，需重新判断进程P进入就绪队列;
        break;
      }else{ //未通过检查（资源不够用）时的处理；
        进程P进入某阻塞队列；//然后继续循环判断下一个进程
      }
    }
   }
 }

信号量集 Semaphore Set

在记录型信号量机制中，wait(S)或 signal(S)操作仅能对信号量施以加 1 或减 1 操作，意味着每次只能获得或释放一个单位的临界资源。
在每次分配时，采用信号量集来控制，可以分配多个单位的资源。

//Si—i 类资源现有数量；ti—i 类资源的分配下限值；di—申请i 类资源数量;
void Swait ( S1, t1, d1; ... ; Sn, tn, dn ){
  if (S1 ≥ t1 and S2 ≥ t2 … Sn ≥ tn) {
    for (i = 1; i <= n; i++){
      Si=Si-di;
    }
  } else {
    //假设首先发现 Sj < tj，进程进入Sj.L队列；
    //进程投入与Sj相关的阻塞队列
    //恢复PC寄存器为Swait开始时的状态；
    //启动进程调度程序，调度其它进程执行；
  }
}
//si—i 类资源现有数；di—i 类资源释放数量 ;
void Ssignal ( S1, d1; ... ; Sn, dn ){
  for (i = 1; i <= n; i++){
    Si=Si+di;
  }
  //把与Si有关队列中的进程移入就绪队列
}

“信号量集机制”可以用于各种情况的资源分配和释放，几种特殊情况：

• Swait(S, d, d)表示每次申请 d 个资源，当少于 d 个时，便不分配
• Swait(S, 1, 1)表示一般的记录型互斥信号量（S=1 时）或资源信号量（S>1 时）
• Swait(S, 1, 0)可作为一个可控开关（当 S1 时，允许多个进程进入临界区；当 S=0 时，禁止任何进程进入临界区）

信号量的应用

利用信号量实现进程互斥
为使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量 mutex，并设其初始值为 1，然后将各进程访问该资源的临界区 CS 置于 wait（mutex）和 signal（mutex）操作之间即可。
利用信号量来描述前趋（合作）关系
假设我们有两个任务 A 和 B，其中任务 B 依赖于任务 A 的完成。我们可以使用一个初始值为 0 的信号量来描述这种前驱关系。具体的操作步骤如下：
任务 A 在完成后，执行一个信号量的 V 操作（signal），将信号量的值加 1。
任务 B 在开始前，执行一个信号量的 P 操作（wait）。如果信号量的值大于 0，那么将信号量的值减 1 并继续执行。如果信号量的值等于 0，那么任务 B 将阻塞，直到信号量的值大于 0。

parbegin 和 parend 是并发编程中用来表示并行开始和并行结束的关键字

例：用 And 信号量来描述如下的前趋图

Var a,b,c,d,e,f,g: semaphore: 0,0,0,0,0,0,0;
Parbegin
       begin S1; Ssignal(a,b); end;
       begin wait(a); S2; Ssignal(c,d); end;
       begin wait(b); S3; signal(e); end;
       begin wait(c); S4; signal(f); end;
       begin wait(d); S5; signal(g); end;
       begin Swait(e,f,g); S6; end;
Parend;

硬件同步机制 Hardware Synchronization Mechanism

利用计算机硬件指令解决临界区问题
对临界区管理将标识看做一个锁，“锁开”进入，“锁关”等待。
初始打开，每个进入临界区的进程必须对锁进行测试。
测试和关锁操作必须连续（原子操作）

虽然可以利用软件方法解决诸进程互斥进入临界区的问题，但有一定难度，并且存在很大的局限性，因而现在已很少采用。相应地，目前许多计算机已提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。可利用这些特殊的指令来解决临界区问题。

1. 关中断
2. 利用 Test-and-Set 指令实现互斥
3. 利用 Swap 指令实现进程互斥

关中断实现互斥 Disable Interrupts

中断是指计算机在执行期间，系统内发生任何非寻常的或非预期的急需处理事件，使得 CPU 暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。
中断处理是指 CPU 响应中断，转入中断处理程序，系统开始处理中断。
中断响应是指 CPU 收到中断请求后转向相应的事件处理程序。
开中断就是指系统可以在连续运行时中断，去运行中断服务函数
关中断就是指关闭系统中断，系统不响应其他的中断，不允许系统打断连续的运行

关中断
进入锁测试前关闭中断，完成锁测试并上锁后打开中断
进程在临界区时计算机系统不响应中断，不会引发调度

Pros And Cons

• 关中断是实现互斥的最简单的方法之一。

---

• 滥用关中断权力可能导致严重后果；
• 关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；
• 关中断方法也不适用于多 CPU 系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

extern bool are_interrupts_enabled();

void atomic_operation(void (*operation)()) {
    start_atomic_operation();
    operation();
    end_atomic_operation(are_interrupts_enabled());
}

void start_atomic_operation() {
    // 如果中断是开启的，那么关闭中断
    if (are_interrupts_enabled()) {
        disable_interrupts();
    }
}

void end_atomic_operation(bool were_interrupts_enabled) {
    // 如果在原子操作开始之前中断是开启的，那么重新开启中断
    if (were_interrupts_enabled) {
        enable_interrupts();
        return;
    }
    enable_interrupts();
}

Test And Set 指令实现互斥

这是一种借助 TS(Test-and-Set)硬件指令以实现互斥的方法。在许多计算机中都提供了这种指令。

lock=false表示资源空闲，*lock=TURE表示资源正在被使用。
当资源被使用时，TS 返回 ture，则 while TS（&lock)；语句条件为真会一直循环等待。

这段代码是一个实现了简单的自旋锁（spinlock）的例子，使用了一个称为 Test-and-Set（TS）的原子操作。自旋锁是一种用于同步的低级别的原子操作，通常用于保护短期的临界区（critical section）。
自旋锁可能会导致资源浪费，因为在等待获取锁的过程中，线程并不会释放 CPU，而是会一直忙等待。因此，自旋锁通常只用于保护非常短期的临界区。对于保护长期的临界区，通常会使用其他的同步机制，如互斥锁（mutex）。

boolen TS(boolen *lock){
    boolean old;
    old = *lock;
    *lock =TURE;
    return old;
}

do{
    …
    while TS( &lock);
    critical section;
    lock :=FALSE;
    remainder section;
}while(TRUE);

利用 Swap 指令实现进程互斥

该指令称为对换指令，在 Intel 80x86中又称为 XCHG指令，用于交换两个字的内容。

管程 Moniter

虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作 wait（S）和 signal（s）。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的进程同步工具——管程 。

Monitors are a higher-level synchronization construct that simplifies process synchronization by providing a high-level abstraction for data access and synchronization. Monitors are implemented as programming language constructs, typically in object-oriented languages, and provide mutual exclusion, condition variables, and data encapsulation in a single construct.
Moniter-Ref

经典同步问题 Classic Synchronization Problems

• 生产者/消费者问题 Producer-Consumer Problem
• 哲学家进餐问题 Dining Philosophers Problem
• 读者/写者问题 Readers-Writers Problem

Producer-Consumer Problem

生产者与消费者是一个广义的概念，可以代表一类具有相同属性的进程。生产者和消费者进程共享一个大小固定的缓冲池;一个或多个生产者生产数据，并将生产的数据存入缓冲池;一个或多个消费者从缓冲池中取数据。

必须使生产者和消费者互斥进入缓冲区。即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其它任何生产者。
生产者不能向满缓冲池写数据，消费者也不能在空缓冲池中取数据，即生产者与消费者必须同步。

涉及两类进程：
生产者进程和消费者进程
需要保证以下同步关系：

1. 多个进程互斥地访问公共缓冲池；互斥信号量 mutex
2. 不能向满的缓冲池中添加产品；可用的空资源信号量 empty
3. 不能从空的缓冲池中提取产品。可用的满资源信号量 full
   full + empty=N

每个进程中各个 wait 操作的次序是重要的：先检查资源数目，再检查是否互斥.否则可能死锁
如：producer 先申请互斥，进入后，申请空资源，发现空资源不可用，必须等待 comsumer 先申请满资源，使用后释放出来。但此时，由于 producer 占用了互斥资源，因此 consumer 无法进入。故而陷入死锁状态

Dining Philosophers Problem

五个哲学家五只筷子，哲学家循环做着思考和吃饭的动作，吃饭程序是：先取左边筷子，再取右边筷子，再吃饭，再放筷子。

1. 至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。
2. 在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的 AND 同步问题，故用 AND 信号量机制可获得最简洁的解法,且可避免死锁。
3. 规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是 2,3 号哲学家竞争 3 号筷子,4,5 号哲学家竞争 5 号筷子.即三个哲学家都  竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会 1 个哲学家能获得两支筷子而进餐.

Readers-Writers Problem

该问题为多个进程访问一个共享数据区建立了一个通用模型，如数据库、文件、内存区及一组寄存器等数据。若干读进程只能读数据，若干写进程只能写数据。

例如，一个联网售票系统，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修改（读/写）其中某一条数据的情形。多个进程同时读一条记录是可以的。如果一个进程正在更新数据库中的某条记录，则所有其他进程都不能访问（读或写）该记录，否则可能会将同一个座位销售多次。

读者/写者进程满足的条件

1. 允许多个读者进程可以同时读数据；
2. 不允许多个写者进程同时写数据，即只能互斥写数据；
3. 若有写者进程正在写数据，则不允许读者进程读数据。

Sol
利用记录型信号量解决读者-写者问题
利用信号量集解决读者-写者问题

Exercies

EX1
三个进程 P1，P2，P3 协作解决文件打印问题，P1 将文件记录从磁盘读入内存的缓冲区 1，每执行一次读一个记录；P2 将缓冲区 1 的内容取出放到缓冲区 2 中；P3 将缓冲区 2 的内容打印出来，每执行一次打印一个记录。缓冲区的大小和一个记录大小一样。
用 P、V 操作来保证文件的正确打印。
引申
有三个进程 A1、A2、A3，它们共享两个缓冲区 B1 和 B2。缓冲区 B1 中可以存放 n 件产品，缓冲区 B2 中可以存放 m 件产品。进程 A1 每次生产一件产品，并把产品存入缓冲区 B1。进程 A2 每次生产一件产品，并把产品存入缓冲区 B2。进程 A3 每次从缓冲区 B2 中取一件产品区消费。为了防止把产品存入已满的缓冲，或者从空缓冲中取产品，或重复取一产品，用 PV 操作实现它们的相互制约关系。

---

EX2
某工厂有一个可以存放设备的仓库，总共可以存放 8 台设备。生产部门生产的每一台设备都必须入库，销售部门可以从仓库中提出设备供应客户。设备出/入库需要借助运输工具，现只有一套运输工具，每次只能运一台设备
请设计生产部门和销售部门进程。

---

EX3
桌上放一个盘子，每次只能放一个水果，爸爸像盘子里放苹果，妈妈向盘子里放橘子，女儿专吃苹果,儿子专吃橘子。盘子空的时候爸爸或妈妈才能向盘子里面放一个水果，仅当盘子里有自己需要的水果时才可取一个水果。把爸爸、妈妈、儿子、女儿看做四个进程，用 PV 操作进行管理，使这四个进程能正确地并发执行。
引申
如果盘子的容量改为 2，且任何时刻只允许爸爸、妈妈、女儿、儿子中的一个进程去访问盘子（放或者取）。

Ref

Semaphore-wikipedia
https://www.cnblogs.com/youxin/p/3586577.html
Moniter