详解进程同步

进程和线程都是CPU的调度单元,所以进程同步和线程同步是一样的概念,文中不具体细分进程和线程

一、进程同步

在详解操作系统进程中，介绍过了并发进程，并发进程之间分为独立关系和交互关系，独立关系的进程分别在自己的变量集合上运行，互不影响；但交互关系的并发进程在执行过程中需要共享或交换数据，因此交互的并发进程之间存在着竞争和协作关系。

1.1 竞争

以一个打印机程序为例，当一个进程需要打印文件时，将文件放入打印机程序的打印目录中，目录中有很多槽位，每个槽位放置一个文件，每个进程在需要打印文件前，需要先知道接下来的那个槽位是空的(槽位是桉按顺序的)，然后才能将文件放置该槽位。

假设现在有A和B两个进程都需要打印文件，A进程执行程序，获取打印机的空闲槽位为5，但是在向槽位5放置文件之前，A进程发生了一次时钟中断(CPU时间片用完)，此时B进程进入CPU开始执行，它也发现槽位5是空的，于是将b文件放入槽位5中，而后退出CPU；接着A进程之前已经知道了槽位5是空闲的，于是直接将a文件放置在了槽位5，B进程的b文件被覆盖掉，当打印机程序从槽位取出文件打印时，只能打印出a文件。

类似上面的这种情况，即两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精准时序，称为竞争条件(Race Condition)

1.2 异步

Asynchronous means Random，随机事件，任何时刻都会发生，没有一定的规则和顺序

上面打印机的例子，如果A进程在槽位5放置完文件才退出CPU，那么B进程就把文件放入槽位6，这样打印机程序就可以把a文件和b文件都打出出来了，完全取决于随机时序。

异步才会引发竞争条件

1.3 同步

Process Synchronization means a mechanism to the consistency of data shared in cooperative process

进程同步是一种维持交互进程之间共享数据一致性的机制

同步的工具：Mutex Lock(互斥锁)和Semaphore(信号量)

二、互斥锁

互斥锁用于解决并发进程中竞争关系

2.1 临界区

在上面的进程同步中，说到了当两个进程同时操作共享数据时，如果不加以干涉就会出问题，换言之，我们需要共享数据的进程之间互斥，即以一种手段确保当一个进程在使用共享数据时，其他进程不能做同样的操作。

每个进程中，对共享数据进行访问的程序片段被称为“临界区”。

临界区定义

Each concurrent process has a segment of code,called a critical section ,in which the process may be changing common variables,updating a table,writing a file,and so on.

每个并发进程中，修改公共数据、更新表、写文件(像这样的操作)的代码段称为重要区域(临界区)
The important feature of the system is that,when one process is executing in its critical section,no other process is allowed to execute in its critial section.That is,NO two processes are executing in their cirtical sections at the same time.

操作系统的重要特性是，当一个进程正在它的临界区执行时，没有其他进程被允许在临界区执行。换句话说，没有两个进程同时在临界区执行
The critical-section problem is to design a protocol that the processes can use to cooperate.

临界区问题就是设计一个进程可以协作的协议

临界区可以避免竞争，但不能保证共享数据的并发进程能够高效正确地协作，对于一个好的临界区协议，需要满足以下条件：

任何两个进程不能同时处于其临界区中
不应对CPU的速度和数量做任何假设(外部条件无关)
临界区运行的进程不能阻塞其他进程
不得使进程无限期等待进入临界区(有限等待)

进程在进入临界区前,首先需要获得许可,使用完临界区退出时,要归还许可,其他进程才能进入临界区

临界区协议的实现有软件和硬件两类方案，其中软件方案比较出名的是Dekker算法和Peterson算法，而硬件方案主要是Mutex Lock

2.2 互斥锁(Mutex Lock)

Mutex Lock定义

Operating-systems designers build software tools to solve the critical-section problem.The simplets of these tools is mutex lock

操作系统设计人员建立软件工具来解决临界区问题，最简单的工具就是互斥锁
- A procss must acquire the lock before entering a critical section
  
  一个进程进入临界区之前必须获取锁
- It must release the lock when it exits the critical section
  
  进程在退出临界区时必须释放锁

为什么说互斥锁是硬件的实现方案呢，因为互斥锁需要通过执行TSL指令来获取锁，而TSL指令称为测试并加锁(test and set lock)，但它是一个原子操作，由硬件保证原子性，执行TSL指令时，执行该指令的CPU通过硬件锁住内存总线，其他CPU将无法访问内存，直到TSL指令执行完测试并加锁。

Lock原理

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

enter_regional:
	//复制锁到寄存器并将锁设为1,为什么直接设置为1呢？
	//只有TSL指令是原子操作,如果原来就是1,再设置成1没什么问题;如果原来是0,设置成1,防止TSL指令执行	   //完之后,其他进程来更改LOCK的值,能保证当前进程正确进入临界区
	TSL REGISTER,LOCK   
    //判断锁是否为0
    CMP REGISTER,#0
    //若不是0,说明锁已经被设置,所以循环等待
    JNE enter_regional
    RET
   
leave_regional:
	MOVE LOCK,#0    //在锁中存入0,表示该锁空闲
    RET				//返回调用者

通过上面的指令我们可以看出来，当一个进程想要获得lock锁，而lock又被其他进程占用时，就只能空循环等待

忙式等待

忙式等待是指占用CPU执行空循环实现等待
这种类型的互斥锁也被称为“自旋锁”(spin lock)

缺点：浪费CPU周期，可以将进程插入等待队列以让出CPU的使用权

优点：进程在等待时没有上下文切换，对于使用锁时间不长的进程，自旋锁还是可以接收的；在多处理器系统中，自旋锁的优势更加明显

三、信号量

用于解决并发进程中的协作关系,互斥锁中的竞争是协作中的一个特例

3.1 信号量的定义

信号量(Semaphore)是一种比互斥锁更强大的同步工具，它可以提供更高级的方法来同步并发进程。

信号量是由荷兰学者Dijkstra1965年提出的，网络中的链路状态算法也是他提出的。
A semaphore S is an integer variable that,apart from initialization,is accessed only through two standard atomic operations: P(proberen in dutch 测试) and V(verhogen in dutch 增加)

信号量S是一个整数，除了初始化之外，只能通过两个标准的原子操作P和V访问

P：wait() operation 等待操作

V：signal() operation 信号操作

3.2 信号量的实现

P(s){
    while(s <= 0)
        do nothing;
    s --;
}

V(s){
    s ++;
}

上面的代码演示了信号量P/V操作的原理，其中s为信号量，对信号量进行P操作时，首先测试信号量s是否小于等于0，如果小于等于0，则空循环进行等待(忙式等待)，如果大于0，就将信号量的值减一；对于V操作，只是简单地把信号地值进行加一操作。

因此，P对应地是测试操作，V对应的是增加操作

3.3 信号量的使用

BINARY SEMAPHORE

二值信号量的值只能是0或1，通常将其初始化为1(S=1)，用于实现互斥锁的功能
二值信号量实现互斥锁，代码如下
```
semaphore mutex = 1;
process pi{
    P(mutex);
    
    critical section
        
    V(mutex);
}
```
每次想要进入临界区之前，首先对信号量mutex进行P操作(测试)，测试通过才能进入临界区，因为P操作为原子操作，此时信号量的值为0，其他想要进入临界区的进程只能在P操作上进行忙式等待(自旋)；进程退出临界区时，对信号量进行V操作，信号量的值又变为1，让其他正在等待的进程在P操作中跳出死循环，进入临界区。

COUNTING SEMAPHORE

一般信号量的取值可以是任意数值(S > 1)，用于控制并发进程对共享资源的访问

例子：有个Y字型的交通路口，其中主干道的车要进入两个小路，而每条小路上最多只能有一辆车行驶
```
semaphore road = 2;
process Car{
    P(road);
    
    pass the fork
    in the road
        
    V(road);
}
```
1、假设现在有三辆车Car1、Car2、Car3都到达了Y字型路口，信号量road表示小路的数量，首先Car1通过P操作，将road减一，并进入了小路，此时road=1，还有一条小路可以用；

2、Car2也通过P操作，再将road减一，并进入小路，此时road=0，没有小路可用了；

3、当轮到Car3的时候，由于此时road=0，执行P操作的时候，进入到了空循环进行忙式等待(自旋)；

4、过了一段时间，Car1驶出了其中一条小路，并对信号量进行V操作，通过Car1的V操作，此时road=1，Car3在P操作中再次循环的时候就退出循环，将road减一，然后进入到小路。

PV操作必须成对出现,不然其他进程将处于永远等待的状态

3.4 信号量实现同步

在信号量的使用中,介绍了信号量S=1实现互斥和信号量S>1实现资源共享,信号量S=0时,可以用来解决进程间的同步问题

同步实现

同步问题实质是将异步的并发进程按照某种顺序执行
解决同步问题的本质就是要找到并发进程的交互点，利用信号量P操作等待的特点来调节进程的执行速度
通常初始值为0的信号量可以让进程直接进入等待状态，直到另一个进程唤醒它。

例子：

公交车司机和售票员的问题，只有当公交车门关的时候，车才能启动，只有当车停下的时候，车门才能打开

semaphore_d = 0;
semaphore_c = 0;


司机			   售票员
P(semaphore_d)   关车门
车启动            V(semaphore_d)
行驶中 		   售车票
                 P(semaphore_c)
车停下            开车门
V(semaphore_c)

车门关闭后车才能启动，所以在车启动之前，需要进行同步等待，当售票员关上车门之后，进行V操作，通知司机可以启动车子了，同样售票员只有在车停下时才能打开车门，所以司机把车停下时，也要执行V操作，通知售票员可以打开车门了

通过信号量实现了进程间的通信

经典同步问题

生产-消费者问题

生产者§与消费者©共用一个缓冲区，生产者不能往“满”的缓冲区中放产品，消费者不能从“空”的缓冲区取产品

假设缓冲区的大小为4，刚开始缓冲区是空的，伪代码如下：

semaphore empty = 4;
semaphore full = 0;

生产者:							消费者:
process product{				  process consume{
    while(true){				  	  while(true){
        make a product                    P(full);
        P(empty);                         pick product from buffer
        put a product into buffer         V(empty); 
        V(full);                          consume the product
    }                                  }
}                                 }

当缓冲区为空，生产者生产的产品可以放进入，但消费者无法从缓冲区获取产品，所以消费者处于等待状态，当生产者向缓冲区放入一个产品之后，对信号量full进行了V增加操作，此时消费者就可以从缓冲区获取产品了；

当生产者连续生产了四个产品放入缓冲区，但消费者都还没消费时，此时信号量empey=0，生产者无法继续向缓冲区存放产品，处于等待状态，当消费者从缓冲区取出一个产品，并对信号量empty进行V操作后，生产者可以继续向缓冲区存放产品

对于有界缓冲区，假设容量为K，代码如下：

item buffer[K];
semaphore empty = k;
semaphore full = 0;
int in = 0,out = 0; //in表示存放元素的下标,out表示获取元素的下标
Process product{                    Process consume{
    make a product                      P(full);
    P(empty);                           product = buffer[out];
    buffer[in] = product;               out = (out+1)%K;
    in = (in+1)%K;                      V(empty)
    V(full);                            consume a product
}                                   }

对于有界缓冲区，假设容量为K，如果有多个生产者和多个消费者的情况，需要对临界区资源进行加锁和解锁操作，代码如下：

item buffer[K];
semaphore empty = k;
semaphore full = 0;
int in = 0,out = 0; //in表示存放元素的下标,out表示获取元素的下标
semaphore mutex = 1;
Process product{                    Process consume{
    make a product                      P(full);
    									P(mutex);
    P(empty);                           product = buffer[out];
    P(mutex);
    buffer[in] = product;               out = (out+1)%K;
    									V(mutex);
    in = (in+1)%K;                      V(empty)
    V(mutex);
    V(full);                            consume a product
}                                   }

注意:在上面的例子中，因为生产者和消费者共用一个互斥信号量(实际应该用两个),生产者里面的P(empty)与P(mutex)以及消费者里面的P(full)与P(mutex)是不能颠倒的,对于生产者没太大影响,但对于消费者颠倒之后,如果消费者进程先拿到互斥锁,而缓冲区里面又没有产品,那么消费者将处于等待状态,由于消费者已经持有了互斥锁,生产者就无法拿到互斥锁而处于等待状态,从此双方都进入了等待状态,等待对方释放资源

苹果桔子问题

问题描述：桌上有一个盘子，每次只能放一个水果；爸爸专门向盘子中放苹果，妈妈专门向盘子中放桔子；儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果

伪代码如下

semaphore sp = 1;      /*盘子里只允许放一个水果(有界缓冲区)*/
semaphore sg1 = 0;     /*盘子没有苹果*/
semaphore sg2 = 0;     /*盘子没有橘子*/

Process father{                        Process monther{
    削一个苹果;							    剥一个桔子;
    P(sp);							       P(sp);
    把苹果放入plate;						    把桔子放入plate;
    V(sg1);                                V(sg2);
}                                       }

Process son{                           Process daughter{
    P(sg2);                                P(sg1);
    从plate取出桔子;                         从plate取出苹果;
    V(sp);                                 V(sp);
    吃桔子;                                 吃苹果;
} 									   }

上面问题中，爸爸和妈妈同为生产者，但他们之间又存在竞争关系，竞争空盘子的使用权，而儿子和女儿都是消费者，但他们之间没有竞争关系

Reader-Writer(读者-写者)问题

问题描述：有一个文件，有人写的时候，其他人既不能读也不能写；有人读的时候，其他人也可以读

问题分析：对于写文件的人，每次都必须要获取对文件的锁才行，但对于读者而言，只要有一个读者获取了锁，其他人就可以读
```
semaphore fileAccess = 1;
int reader_count = 0;

Process reader{                       Process writer{
    if(reader_count == 0)                 P(fileAccess);
        P(fileAccess);                    写文件;
    reader_count ++;                      V(fileAccess);
    读文件;
    reader_count --;
    if(reader_count == 0)
        V(fileAccess);
}									  {
```
对于写进程，每次都要先获得锁才能写文件，而对于读进程，首先判断是否已经有读者获取了锁，如果已经获取了锁，则可以直接读文件，当最后一个读者读完文件之后，需要释放对文件的锁

四、死锁

哲学家就餐问题

有五个哲学家围坐在一个圆桌，每个哲学家的右手边放有一根筷子共五根筷子，每个哲学家只有拿到两只筷子才能就餐(同时只能有两个哲学家同时就餐)，存在一种特殊情况，当五个哲学家都拿到了自己右手边的筷子时，此时都在等待自己左手边的筷子空闲，这种现象称为死锁(DeadLock)。

4.1 死锁定义

In a multiprogramming enviroment,serveral processes may compete for a finite number of resources

在多道程序设计环境中，某些进程可能竞争有限数量的资源
A process requests resource;if the resource are not available at the time,the process enters a waiting state

一个进程请求资源，如果该资源此时不可用，该进程进入等待状态
Sometimes a waiting process is never again able to change state,because the resources it has requested are held by other waiting process

有时候一个等待进程由于请求的资源被另一个处于等待状态的进程所持有，永远无法再次改变状态
This situation is called a deadLock

上面描述的这类情况称作死锁

在上面的定义中所说的资源是指不可抢占资源,对于可抢占资源不会发生死锁

死锁与饥饿的区别：

饥饿是进程长时间等待，对于饥饿进程而言，如果前面的进程都执行完了，是可以自动接触饥饿状态的

死锁是多个进程相互等待被对方占用的资源，如果没有外部干涉，死锁将无法终止

4.2 资源死锁的必要条件

互斥条件

同一时刻，一个资源只能被一个进程占用；即每个资源要么已经分配给了进程不可用，要么可用
占有和等待

一个进程请求资源得不到满足等待时，不释放已占用资源
不可抢占/剥夺

除了占用资源的进程主动释放资源，其他进程都不可抢占资源
循环等待(上面三种情况同时存在产生的结果)

每一个进程分别等待它前一个进程所占用的资源；死锁发生，系统中一定有由两个或多个进程组成的一条环路，该环路中每个进程都在等待下一个进程所占用的资源

4.3 死锁解决方案

对于解决死锁问题，有三种不同的立场：

1、不允许死锁出现，必须预防或避免死锁状态的发生

2、允许死锁出现，但操作系统可以检测和恢复

3、假装死锁从来没有在系统发生过

具体解决方案如下：

死锁防止

破坏四个必要条件之一；

破坏资源互斥，允许同时共享使用，将会出现最后一张机票卖给两个人的情况
将资源变成可抢占的系统将奔溃
破坏占用和等待的条件，一个进程一次性申请允许所需的所有资源，直到运行结束才释放，这将导致严重的资源浪费
破坏循环条件，对资源进行排序，保证每个线程在申请后面的资源时已经占用了前面的资源，可以避免形成环路，但也会导致一个线程一次性申请了很多资源

死锁避免

允许产生死锁的四个必要条件同时存在，在并发进程中妥善安排避免死锁的发生

利用安全算法，在每次资源请时先判断是否会引起死锁，再决定是否给该进程分配资源

Dijkstra提出了一种能够避免死锁的调度算法，称为银行家算法。

系统对进程的每一次资源申请都进行详细的计算，根据计算结果决定分配资源还是让其等待，确保系统始终处于安全状态，避免死锁发生。

简单来说，假设银行家有A、B、C三种资源，剩下数量分别为2、0、1，现在有三个进程分别占有和仍需的资源如下：

分配资源仍需资源

A B C A B C

P1 3 2 1 3 2 2

P2 2 3 2 1 1 3

P3 0 2 3 1 0 1

对于上面的一个矩阵，银行家算法需要如何给进程分配资源才能避免死锁，如果银行家把剩下的资源都给了P1，但P1任然需要资源，就会导致死锁；如果给了P2，P2由于缺少B和C资源而进入等待；如果给了P3，P3所需资源得到了满足，可以正常运行至结束，P3退出资源回收以后，银行家现有资源数量为2、4、4，同样，如果把剩下资源分配给P1，P1仍然需要资源而处于等待，如果把资源分配给P2，P2就可以正常运行结束然后回收资源，再给P1分配资源，P1正常运行直至结束

上面的例子中，银行家根据安全算法给进程分配资源，如果能找到不发生死锁的资源分配顺序(先给谁再给谁)，则系统状态是安全的。如果找不到一个这个的顺序，则系统状态是不安全。

如果一个系统状态是安全的，就不会有死锁发生。

如果一个系统状态是不安全，可能导致死锁发生。

银行家算法：