进程同步、互斥及实现方法

1 进程同步

回顾进程的特征：动态性、并发性、异步性、独立性、结构性。
由于进程的异步性，各个进程按各自独立的、不可预知的速度向前推进，例如下面两段伪代码：

P0进程
{
代码1;  ............1
代码2;  ............2
代码3;  ............3
}

P1进程
{
代码4;  ............4
代码5;  ............5
代码6;  ............6
}

如P0进程先获取到CPU执行权，先执行了代码1，之后切换到P1进程，执行了代码4、5、6，之后再切换到P0进程，执行了代码2和代码3。
如果P0进程先获取到CPU执行权，可能先执行了代码1、2，之后切换到P1进程，执行了代码4和代码5....

由于进程间的切换，导致了进程以不可预知的速度（顺序）执行。
举个例子，在进程通信中有一种通信方式——管道通信。在读写进程并发的条件下，由于读写进程执行的先后顺序是不确定的，但是实际要求必须按照先写再读顺序。

所以为了能够实现上述的需求，操作系统就需要提供“进程同步机制”。
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生制约关系。

2 进程互斥

临界资源：是指一个时间段内只允许一个进程使用的资源。许多物理设备（如摄像头、打印机）都是属于临界资源。此外，很多变量，数据、内存缓冲区都是临界资源。
对临界资源的访问，必须互斥的进行。进程互斥指一个进程访问某个临界资源时，另一个进程想要访问这个临界资源必须要等当前访问临界资源的进程访问结束，释放该资源之后，才可以访问。

访问临界资源

do{
      entry section;  //进入区，负责检查是否可以进入临界区，如可以进入，
                     //则设置正在访问临界区的标识，以阻止其他进程同时进入临界区
      critical section; // 临界区，访问临界资源的那段代码
      exit section;//退出区，负责解除正在访问临界资源的标识
      remainder section;// 保留区，做一些其他处理。
} while

  临界区是进程访问临界资源的代码段。
  进入区和退出区是负责实现互斥的代码段。
  为了实现对临界资源的互斥访问，同时保证系统的整体性能，需要遵循以下原则：

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

3 进程同步和互斥小结

4 进程互斥的软件实现方法

单标志法、双标志先检查法、双标志后检查法、Peterson算法

4.1 单标志法

算法思想：两个进程在访问完临界资源区后会把使用临界区的权限转交给另一个进程，即每个进程进入临界区的权限只能被另一个进程赋予。

turn的初始值为0，则刚开始只允许0号进程进入临界区。
若P1先上处理机，则会一直循环，直到P1进程的时间片用完，发生调度，P0进程开始执行，在P0进程访问临界区过程中，不管有没有发生调度，P1进程都进不去临界区，因为此时turn的值为0，只有P0进程访问完了临界资源，并将turn的值改为1，当再次进程切换时，P1才能访问临界区。

此算法可以实现同一时刻只允许一个进程访问临界区。
单标志法对临界区的访问是轮流访问，这会带来一个问题，如果刚开始允许进入临界区的是P0进程，但是P0进程一直不访问临界区，从而导致P1进程也一直无法访问临界区。所以单标志法存在的问题就是：违背了空闲让进原则。

4.2 双标志先检查法

算法思想：设置一个布尔类型的数组flag[]，数组中的各个元素用来标记各进程想进入临界区的意愿，每个进程进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自己对应的标志flag[i]设为true，之后开始访问临界区。

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

4.3 双标志后检查法

算法思想：双标志先检查法的改版。前一个算法先检查后上锁，该算法先上锁后检查。

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

4.4 Peterson算法

算法思想：对于双标志后检查法中，如果两个进程都争着进入临界区，那可以让进程尝试？“孔融让梨”，主动让对方先使用临界区。

Peterson算法可以很好的解决了前面3中算法的问题，无论何种顺序都可以保证同一个时刻只有一个进程访问临界区。但是当一个进程访问临界区时，另一个进程不会释放处理机，会一直循环等待条件满足访问临界区，违背了“让权等待”的原则。

5 进程互斥的软件实现方法总结

6 进程互斥的硬件实现方法

进程互斥的硬件实现方法：中断屏蔽方法、TestAndSet（TS指令/TSL指令）、Swap指令（XCHG指令）。

6.1 中断屏蔽方法

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

优点：简单、高效。
缺点：不适用于多处理机；只适用于操作系统内核进程，不适合用户进程（因为开/关中断指令只能运行在内核态）。

6.2 TestAndSet指令

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

// 布尔型共享变量 lock 表示当前临界区是否加锁
// true 表示枷锁，false 表示未加锁
bool TestAndSet (bool *lock) {
    bool old;
    old = *lock;  //old用于存放lock原来的值
    *lock = true;  // 无论之前是否加锁，都将lock设为true
    return old;  // 返回lock原来的值
}

// 以下是使用 TSL 指令实现互斥的算法逻辑
while(TestAndSet (&lock)); // 上锁并检查，
临界区代码...
lock = false;  // "解锁"
剩余区代码...

若刚开始lock是false，表示当前临界区可以访问，则TSL返回的old值为false，while条件不满足，直接跳过循环进入临界区。若刚开始是lock是true，表示临界区不可以被访问，则TSL执行后old返回值为true，while循环条件满足，会一直循环，直到当前访问的临界区的进程退出并解锁。

  相比于软件实现方法，TSL指令把上锁和检查操作用硬件的方式变成原子操作。
  优点：实现简单，适用于多处理机环境。
  缺点：违背让权等待的原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致忙等。

6.3 Swap指令

Swap指令也是用硬件实现的，执行过程不能中断。以下是用C语言描述其逻辑：

//Swap 指令的作用是交换两个变量的值
Swap(bool *a,bool *b){
  bool temp;
  temp = *a;
  *a = *b;
  *b = temp;
}
//以下是使用 Swap指令实现互斥的算法逻辑
// lock 表示当前临界区是否被加锁
bool old = true;
while(old == true)
  Swap(&lock,&old);
临界区代码...
lock = false;  // "解锁"
剩余区代码...

  逻辑上看，Swap指令和TSL没有多大的区别，都是先记录下临界区是否已经被上锁（记录在old变量上），再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
  优点：实现简单，适用于多处理机环境。
  缺点：违背让权等待的原则，暂时无法进入临界区的进程会占用CPU，从而导致忙等。

本文完

如发现错误，请指正！！！