同步机制

进程互斥

由于各个进程要求使用共享资源（变量、文件等），而这些资源需要排他性使用，各个进程之间竞争使用这些资源，这一关系被称为进程互斥。

临界资源

系统中的某些资源一次只允许一个进程使用，称这些资源为临界资源或这互斥资源或共享资源。

临界区

每个进程中对某个临界资源（共享变量）实施操作的程序片段。

临界区（互斥区）的使用原则

• 没有进程在临界区时，想进入临界区的进程可以进去；
• 不允许两个进程同时处于它们的临界区；
• 临界区外运行的进程不得阻塞其他进程进入临界区；
• 不得是进程无限期等待进去临界区；

进程互斥的软件解决方法

错误解法

考虑两个进程 p 和 q，pturn 与 qturn 表示对应的进程进入临界区。

• p 进入临界区的条件：pturn && not qturn；
• q 进入临界区的条件：not pturn && qturn；

  // 进程p：
  pturn = true;     
  while (qturn);          
  visit();	//访问临界区
  pturn = false;
  
  // 进程q：
  qturn = true;     
  while (pturn) ;          
  visit();   	//访问临界区
  qturn = false;

  如果由于 CPU 调度使得两个进程全部都执行第一行语句，即 pturn 和 qturn 都为 true，那么在下一行 while 语句上，两个进程都会死循环，都在谦让对方，这样不满足不能使进程无限期等待进入临界区的原则。

Dekker 算法

同样假设有两个进程 p 和 q，变量 pturn 和 qturn 分别表示这两个进程是否想要进入临界区，为了解决进程无限期等待的问题，Dekker 算法加入了一个变量 turn 决定两个进程相互等待的时候谁进入临界区：

// 进程p：
pturn = true; 	// 进程p举手示意想要访问
while (qturn) { 	// 如果进程q也举手了
    if (turn == 2) {   // 资源被安排给了q
        pturn = false;   // 进程p把手放下
        while (turn == 2);   // 资源安排给q的时候一直等待
        pturn = true;    // 此时资源安排给了自己，进程p再举手
    }
}
visit();	// 访问临界区
turn = 2;   // 进程p使用完了，安排资源给q
pturn = false;	// 进程p把手放下

// 进程q：
qturn = true; 
while (pturn) { 
    if (turn == 1) { 
        qturn = false; 
        while (turn == 1); 
        qturn = true; 
    }
}
visit();	// 访问临界区
turn = 1;
qturn = false;

如果两个进程都执行完了第一行语句，也就是 pturn 和 qturn 都为true了，那么会根据变量 turn 进一步确定将资源安排给谁，如果安排给了另一个进程，那么当前进程就将自己的手放下，然后等待安排资源给自己。

和上一种错误解法相比，可以发现 Dekker 算法就是在原本的 while 循环前做了进一步的判断，引入的 turn 变量总是会安排一个进程进入到临界区。但是当其他进程不能上 CPU时，while 循环的测试实际上就在浪费时间，这就是强制轮流，是 Dekker 算法的一个缺陷。

Peterson 算法

Peterson 算法克服了强制轮流的缺点，可以正常解决并发进程互斥与同步。在进程出入临界区时，只需要使用两个函数即可：

enter_region(i);
visit();	// 访问临界区
leave_region(i);

其中 enter_region 和 leave_region 的实现如下：

#define FALSE 0
#define TRUE 1
#define N 2 // 进程的个数
int turn;   // 轮到谁
int interested[N];   // 兴趣数组，初始值均为FALSE

void enter_region(int process) // process = 0 或 1
{
    int other;     // 另外一个进程的进程号
    other = 1 - process;
    interested[process] = TRUE;  // 表明本进程感兴趣
    turn = process;  // 设置标志位         
    while(turn == process && interested[other] == TRUE); 
}

void leave_region(int process){
	interested[process] = FALSE;   // 本进程已离开临界区
}

如果有两个进程都要进入临界区，turn 会被设置为最后一个进程的进程号，按照先来后到的规定，后一个进程 while 中的 turn==process 成立，然后进入循环等待，这个时候先到的进程可以进入临界区。当先进入的进程离开了临界区执行了 leave_region 方法后，后到进程 while 循环中 interested[other]==TRUE 条件被打破，这个进程就可以跳出循环等待然后进入到它的临界区。

进程互斥的硬件解法

TSL 指令

TSL，TEST AND SET LOCK，测试并加锁

TSL 将一个内存字 lock 读到寄存器 RX 中，然后在该内存地址上存储一个非零值。读写指令能保证是一体的，不可分割的，一同执行的。在这个指令结束之前其他处理器均不允许访问内存。执行 TSL 指令的 CPU 会锁住内存总线，用来禁止其他 CPU 在这个指令结束之前访问内存。

锁住内存总线和屏蔽中断是不一样的：屏蔽中断并不能保证一个处理器在读写操作期间另一个处理器对内存的读写，而锁住内存总线可以做到屏蔽另一个处理器的影响。

为了使用 TSL 指令，要使用一个共享变量 LOCK 来协调对共享内存的访问。当 LOCK 为 0 时，任何进程都可以使用 TSL 指令将其设置为 1，并读写共享内存。当操作结束时，内存使用 MOVE 指令将 LOCK 重新设置为 0。

enter_region:
TSL REGISTER,LOCK       // 复制锁到寄存器然后将锁设为1
    CMP REGISTER,#0     // 锁是0吗？
    JNE enter_region    // 若不是0，说明锁已被设置，所以循环
    RET                 // 返回调用者，进入了临界区

leave_region:
MOVE LOCK,#0            // 在锁中存入0
    RET                 // 返回调用者

XCHG 指令

XCHG 原子性的交换了两个位置的内容：

enter_region:
MOVE REGISTER,#1        	// 在寄存器中放一个1
    XCHG REGISTER,LOCK      // 交换寄存器与锁变量的内容
    CMP REGISTER,#0         // 锁是0吗？
    JNE enter_region        // 若不是0，说明锁已被设置，所以循环
    RET                     // 返回调用者，进入了临界区

leave_region:
MOVE LOCK,#0            	// 在锁中存入0
    RET                     // 返回调用者

锁机制

在 TSL 和 XCHG 中都使用了锁机制，锁是一个代表共享资源状态的变量：

• 0 表示资源没有被占用，开锁状态
• 1 表示资源已被占用，加锁状态

在使用临界资源前需先考察锁变量的值，如果值为 0 则将锁设置为 1（加锁），如果值为 1 则重新考察锁变量的值。当进程使用完资源后，应将锁设置为 0（开锁）。

// 上锁
lock（w）
 {
    while（w==1）；
    w = 1；
 }
// 开锁
unlock（w）
 { 
     w = 0；
 }
// 锁机制实现互斥
进程P1             进程P2
   ┆                ┆
 lock(w)；         lock(w)；
 临界区；           临界区；
 unlock(w)；       unlock(w)；
   ┆                ┆

忙等待 && 自旋锁

• 忙等待（busy waiting）：在软件解决方法和硬件解决方法中，我们使用 while 循环测试是否开锁或者条件是否成立，导致等待进程在允许进入临界区之前会循环测试而浪费CPU的周期。

• 自旋锁（spin lock）：在多处理器的情况下，系统允许一个进程在某一个 CPU 上循环测试。如果当前进程想要进入临界区同时有其他的进程位于临界区，那么该进程就不断自旋、测试，直到临界区释放。

• 自旋锁是忙等待在多处理器情况下的演变，本质还是循环测试直到进程允许进入临界区。

进程同步

进程同步指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体地说，一个进程运行到某一点时， 要求一个伙伴进程为它提供消息，在未获得消息之前，该进程进入阻塞态，获得消息后被唤醒进入就绪态。

信号量及 PV 操作

信号量是一个特殊的变量，用于进程之间专递信息的一个整数值，定义如下：

struct semaphore
{  
	int count;			// 用来进程之间传递的整数值
	queueType queue;	// 进程可以挂在信号量所属的队列上
}

可以对信号量进行初始化（非负数）、P（down）和 V（up）操作，PV 操作均为原语操作。定义如下：

P(semaphore s) 
{
    s.count--;
    if (s.count < 0)
    {
        //该进程状态置为阻塞状态；
        //将该进程插入相应的等待队列s.queue末尾;
        //重新调度；
    }
}

V(semaphore s) {   
    s.count++;   
    if (s.count <= 0)   
    {      
        //唤醒相应等待队列s.queue中等待的一个进程；      
        //改变其状态为就绪态，并将其插入就绪队列；    
    } 
}

• 信号量的取值为二值（0 / 1），那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。
• 多值信号量则用来解决进程之间的同步问题。

用 PV 操作解决进程之间的互斥问题

• 分析并发进程的关键活动，划定临界区；
• 设计信号量 mutex，初始值为 1；
• 在进入临界区之前实施 P(mutex)；
• 在离开临界区之后实施 V(mutex)；

生产者-消费者问题

生产者-消费者问题又被叫做有界缓冲区问题，问题描述：

• 一个或多个生产者生产某种类型的数据放置在了缓冲区中。当缓冲区已满时，生产者不会继续向其中添加数据；
• 有消费者从缓冲区中取数据，每次取一项。当缓冲区为空时，消费者不会从中移走数据。
• 只能有一个生产者或者消费者对缓冲区进行操作；

使用三个信号量，其中 mutex 用来解决互斥问题，empty 和 full 用来解决同步的问题。

#define N 100;			// 缓冲区的个数
typedef int semaphore;	// 信号量是一种特殊的整型数据
semaphore mutex = 1;	// 互斥信号量：控制对临界区的访问
semaphore empty = N;	// 空缓冲区的个数
semaphore full = 0;		// 满缓冲区的个数

void producer(void) {
    int item;
    while (True) {
        int item = produce_item();
        p(&empty);
        p(&mutex);
        insert_item(item);
        v(&mutex);
        v(&full);
    }
}

void consumer() {
    while (True) {
        p(&full);
        p(&mutex);
        int item = remove_item();
        v(&mutex);
        v(&empty);
        consume_item(item);
    }
}

• 不能交换两个 P 操作的位置，假设交换消费者中的两个 P 操作，buffer 中为空。那么将先执行P(&mutex) ，mutex=0，再执行 P(&full)，消费者会等待在 full 信号量的队列中。接着在消费者让出CPU 后，生产者进入 CPU 先执行 P(&empty)，然后执行 P(&mutex)，但是 mutex=-1，生产者等待进入临界区。此时消费者等待生产者生产产品，生产者等待进入临界区，就会出现死锁问题。
• 两个 V 操作的的位置最好也不要交换，交换不会带来死锁问题，但是会扩大临界区的范围，这样子其他进程进入临界区的时间可能会延迟。同理，produce_item() 和 consume_item() 也不应该放入临界区中。

互斥操作时，相同信号量的 PV 操作是在同一个进程中的。同步操作时，一个信号量的 PV 操作是分散在两个或多个进程中的，一个进程做 P 操作，另一个做 V 操作。

读者-写者问题

问题描述：多个进程共享一个数据区，这些进程分为只读数据区中的数据的读者进程和只往数据区中写数据的写者进程。允许多个读者同时执行读操作，不允许多个写者同时操作，不允许读者、写者同时操作。在这里讨论读者优先的情况：
当读者进程执行：

• 无其他读者、写者，该读者可以读；
• 若已有写者等，但有其他读者正在读，则该读者也可以读；
• 若有写者正在写，该读者 必须等；

当写者进程执行：

• 无其他读者、写者，该写者可以写；
• 如果有读者正在读，该写者等待；
• 如果有其他写者正在写，该写者等待；

  typedef int semaphore;
  semaphore count_mutex = 1;	// 多个进程可能同时修改count，所以对count加锁
  semaphore data_mutex = 1;	// 对读写的数据加锁
  int count = 0;	// 对数据进行读操作的进程数量
  
  void reader() {
      while(TRUE) {
          p(&count_mutex);
          count = count + 1;		
          if(count == 1) p(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
          v(&count_mutex);
          
          read();
          
          p(&count_mutex);
          count = count - 1;
          if(count == 0) v(&data_mutex); // 最后一个读者需要对数据解锁，让写进程访问
          v(&count_mutex);
      }
  }
  
  void writer() {
      while(TRUE) {
          p(&data_mutex);
          write();
          v(&data_mutex);
      }
  }

管程

因为信号量机制在程序编写的时候困难、易出错，所以在程序设计语言中引入了管程，是一种高级的同步机制。

管程是一种特殊的数据类型，其中包含了共享资源的数据结构及在该资源上的一组操作过程。进程只能通过调用管程中的过程来间接访问管程中的数据结构。

互斥 / 同步

• 互斥：管程是互斥进入的，互斥性由编译器实现。
• 同步：管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，应该释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒。

进程运行的过程中会出现多个进程同时出现在管程内（例如 P 唤醒了 Q），有三种解决方法：

• HOARE管程：P 等待 Q 执行；
• MESA 管程：P 继续执行，Q 等待 P 执行结束；
• Hansen管程：规定唤醒操作为管程中最后一个可以执行的操作；

HOARE 管程

因为管程是互斥进入的，所以当一个进程试图进入一个被占用的管程时，需要在管程的入口等待队列等待。

如果进程 P 唤醒了进程 Q，则 P 等待 Q 执行；如果进程 Q 执行中又唤醒了进程 R，则 Q 等待 R 执行；如此反复，在管程内可能出现多个等待进程。所以在管程内设置了紧急等待队列，该队列的优先级高于入口等待队列。

* HOARE 管程中的条件变量

条件变量是在管程内部说明和使用的一种特殊类型的变量，对于条件变量可以执行 wait 和 signal 操作：

• wait(c)：如果紧急等待队列为空，则唤醒队列中的第一个等待者；否则释放管程的互斥权，执行该操作的进程进入条件变量 c 链的末尾；
• signal(c)：如果 c 链为空，则相当于空操作，执行 signal 操作的进程继续执行；否则唤醒 c 链上的第一个等待者，执行 signal 操作的进程进入紧急等待队列的末尾；

* 用管程解决生产者-消费者问题

monitor ProducerConsumer
	condition full, empty; // 条件变量
    integer count;
	
	producer insert(item: integer);
	begin
    		if count == N then wait(full); // 如果产品数量为N，则生产者在条件变量full上等待
			insert_item(item); count++;
			if count == 1 then signal(empty); // 如果产品数量为1，唤醒在条件变量empty中可能等待的消费者
	end;

	function remove: integer;
	begin
    		if count == 0 then wait(empty); // 如果产品数量为0，则消费者在条件变量上empty上等待
			remove = remove_item; count--;
			if count == N-1 then signal(full); // 如果产品数量为N-1，唤醒在条件变量full中可能等待的生产者
	end;
	count:=0;
end monitor;

// 生产者
procedure producer
begin
		while true do
        begin
        		item = produce_item;
		end
end;

// 消费者
procedure consumer;
begin
		while true do
        begin
        		item = ProducerConsumer.remove;
				consume_item(item);
		end
end;

MESA 管程

HOARE 管程有个缺点就是会有两次额外的进程切换，因此 MESA 管程将原本的 signal 操作变为 notify 操作：当一个正在管程中的进程执行 notify(x) 时，它使得 x 条件队列得到通知，发信号的进程继续执行，而位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行。

由于收到通知时并未执行，且对等待进程在 notify 之后何时运行没有任何限制，所以当进程真正被调度时，条件不一定成立，因而这个进程必须重新检查条件，也就是用 while 循环取代if语句。

IPC

IPC，InterProcess Communication，进程间通信，是指在不同的进程之间传播或交换信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通行，传输一些进程同步所需要的信息。

IPC 包含管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Stream等方式。其中 Socket 和 Stream 支持不同主机上的两个进程进行通信。

管道

通常指的是无名管道，是 UNIX 系统 IPC 最古老的形式。

管道是通过调用 pipe 函数创建的，当一个管道建立时，它会创建两个文件描述符：fd[0] 为读而打开，fd[1] 为写而打开，要关闭管道只需要将这两个文件描述符关闭即可。

单个进程中的管道几乎没有任何用处。所以，通常调用了 pipe 的进程接着调用 fork，这样就创建了父进程和子进程之间的 IPC 通道。若要数据流从父进程流向子进程，则关闭父进程的读端（fd[0]）与子进程的写端（fd[1])；反之，则可以使数据流从子进程流向父进程。

特点：

• 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端
• 它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）

FIFO

FIFO 也称为命名管道，它是一种文件类型，可以在无关的进程之间交换数据，与无名管道不同。

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

消息队列

消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（队列 ID）来标识。

• 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
• 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
• 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。

信号量

信号量是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

共享内存

共享内存指两个或多个进程共享一个给定的存储区，因为数据不需要在进程之间复制，所以这是最快的一种 IPC。由于多个进程可以同时操作，所以信号量与共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

如下图所示，两个进程 1 和 2 都有各自的内存地址空间，在物理内存空间有一块共享内存，两个进程中都有一块内存空间映射到了同一块物理内存（即共享内存）。共享内存也包含了一个读者-写者问题：不能多个进程同时写入，但支持同时读取。假设进程1想往共享内存写数据，只需要往本地映射的内存空间写入数据，相当于是写入了共享内存。

套接字

与其他的通信机制不同，它可以用于不同机器之间的进程通信。

参考

1. 北京大学操作系统原理（Operating Systems）
2. 操作系统原理-同步机制-水木今山
3. CS-Notes
4. 【操作系统】同步互斥机制（二）：管程与进程间通信机制（IPC）
5. 操作系统-同步互斥机制2