进程同步

回顾:进程具有异步性的特征，即各个并发执行的进程以各自独立的，不可预知的速度向前推进

但进程的异步性在有些情况下可能会影响程序的正常运行，以上图的管道通信为例，进程1负责写入数据，进程2负责读取数据，只有进程1将管道数据填满后进程2才能成功取到数据，但两个进程并发执行，无法确定读写数据操作的先后顺序，而实际情况又要求必须先写后读的方式执行，此时就需要通过进程同步解决相关问题

进程同步亦称直接制约关系，它是指为完成某个任务而建立的两个或多个进程，这些进程由于需要在某些位置上协调工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作

进程互斥

两种资源共享方式

通过之前的知识我们知道，进程的“并发”依赖于“共享”的支持，各个并发执行的进程不可避免的需要共享一些系统资源

我们把一个时间段内只允许一个进程使用的资源称为临界资源，许多物理（摄像头，打印机）都属于临界资源，此外还有许多变量，数据，内存缓冲区都属于临界资源

对临界资源的访问，必须互斥地进行。

互斥亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待，当前访问临界资源的进程结束访问，释放临界资源后，另一个进程才能访问临界资源

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
do {
    //进入区
    entry_section() { 
        /*
        进入区负责检查是否可以进入临界区
        若可以进入，则应设置“正在访问临界资源的标志”（即上锁）
        以阻止其他进程同时进入临界区
        */
    }
    //临界区
    critical_section() {
        /*
        临界区就是访问临界资源的那段代码
        */
    }
    //退出区
    exit_section() {
        /*
        退出区负责接触“正在访问临界资源的标志”（即解锁）
        */
    }
    //剩余区
    remainder_section() {
        /*
        剩余区负责进行其他处理
        */
    }
}

注意：

  • 临界区是进程中访问临界资源的代码段
  • 进入区和退出区是负责实现互斥的代码段
  • 临界区有时也称为临界段

进程互斥需要遵循的原则

为了实现对临界资源的互斥访问，同时保证系统整体性能，进程互斥需要遵循以下原则

  1. 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
  2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
  3. 有限等待：对请求访问的进程，应保证能在有限时间进入临界区（避免饥饿）
  4. 让权等待：当进程不能进入临界区，应立即释放处理机，防止进程忙等待（处理机被占用，但没有真正运行）

进程互斥的软件实现方法

单标志法

算法思想

两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予

算法示例

从上面示例可以看到，turn初值设为0，即刚开始只允许0号进入临界区，若P1进程尝试进入临界区，则会在执行第五行代码时被循环卡在进入区，直到时间片用尽，切换P0进程运行，P0在进入区代码检查通过能够正常访问临界区

此时，即使发生进程切换导致P1再次执行也会由于进入区的检查导致P1无法进入临界区，只有当P0进程在临界区执行完毕，释放资源，执行第三行代码进入退出区后，P1才能进入临界区

可以看到，该代码保证了同一时刻最多只允许一个进程访问临界区

但是，这种算法的据现象在于，如果当前标志位turn所设置的进程一直不执行，则会导致另一个进程始终无法进入临界区，即违背了“空闲让进” 的原则

双标志先检查法

算法思想

设置一个布尔型数组flag[],数组中各个元素用来标记各个进程想进入临界区的意愿，例如“flag[0]=true”表示0号进程P0现在想要进入临界区，每个进程在进入临界区前都会先检查是否有其他进程想要进入临界区，若没有，则将自身标志位设为true，开始访问临界区

但是，由于进程执行过程中的异步性，代码的执行顺序是不确定的，若按照1，5，2，6，3，7的顺序执行，则会导致两个标志位同时被设置为true，同时进入临界区，违反了“忙则等待”原则

出现上面问题的核心原因就在于进入区中的“检查”和“上锁”处理不是原子性执行，而是分开执行的，在检查后，上锁前可能发生进程切换

双标志后检查法

算法思想

考虑到前面的先检查法出现问题是由于先检查后上锁，但是两个操作又无法原子性执行，所以后检查法希望通过先上锁，后检查来解决上面提到的问题

算法示例

很明显，这样的算法出现了另一个致命性的问题，加入代码执行按照1，5，2，6的顺序执行，则由于双方都提前进行了上锁，所以两个进程都只能处于循环等待的状态，P0和P1最终都无法进入临界区

综上，后检查法解决了“忙则等待” 的问题，却违背了“空闲让进”和“有限等待”原则，最终会导致饥饿现象的产生

Peterson算法

算法思想

双标志后检查法出现的问题在于最终可能双方都想进入临界区导致互相争夺都无法进入，而Peterson算法为了改进这种情况，提出了“谦让”的方式，主动让对方先使用临界区

算法示例

我们再利用异步性来检验当前算法是否能够保证所有原则，假设代码以1，2，3，6，7，8的顺序执行，由于在第三行代码判断时flag[1]=false，所以P0进程能够顺利进入临界区，P1进程需要在第八行代码处等待，直到P0进程释放资源并修改意愿为flag[0]=false，P1进程才能进入临界区

假设代码以1，6，2，3的顺序执行

  1. 首先经过1和6行代码，P0和P1都表示了想进入临界区的意愿
  2. P0进程在第二行代码处将turn设为1表示愿意谦让
  3. 随后到第三行代码发现P1进程想要进入临界区并且自己愿意谦让，所以P0开始循环等待
  4. 直到进程切换到P1
  5. P1继续执行第七行代码修改turn为0
  6. 然后执行第八行代码发现P0想要执行并且自己愿意谦让，P1开始循环等待
  7. 直到进程切换到P0
  8. P0继续执行第三行代码，发现P1虽然想要执行，但此时P1谦让（turn!=1）所以P0进入临界区
  9. P0执行完后，修改执行意愿
  10. P1进入临界区继续执行

可以看到，P0进程经过三次进程切换才得到成功执行，但由于谦让机制，最终一定会得到执行

算法总结

Peterson算法用软件方法解决了进程互斥问题，遵循了“空闲让进”，“忙则等待”，“有限等待”三个原则。不过依然没有遵循“让权等待”原则

进程同步的硬件实现方法

中断屏蔽方法

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

1
2
3
4
5
...
关中断; //关中断后即不允许当前进程被中断，也必然不会发生进程切换
临界区;
开中断; //直到当前进程访问完临界区，才执行开中断指令，别的进程才有机会上处理机并访问临界区
...
  • 优点：简洁，高效
  • 缺点：不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令都只能运行在内核态，这组指令不能让用户随意使用）

TestAndSet指令

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 布尔型的共享变量 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，不满足循环条件，能够成功进入临界区（此时已经成功在TSL指令内部进行了上锁）。若刚开始lock是true，则执行TSL指令后old的值为true，所以始终进行while循环，直到当前访问临界区的进程在退出区将lock设为false进行解锁

相比软件实现方法，TSL指令把上锁和检查操作用硬件的方式变成了只能一步执行到底的原子操作，避免了软件实现方法中的逻辑漏洞

  • 优点：实现简单，避免了软件实现中的逻辑漏洞，适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，导致忙等

Swap指令

又叫Exchange指令，或XCHG指令。Swap指令是用硬件实现的，执行的过程中不允许被中断，只能一气呵成。以下是用C语言描述其逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 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指令没有太大区别，都是先记录此时临界区是否上锁，再将上锁标记lock设为true，最后检查old，如果为false则可进入临界区，否则循环等待

  • 优点：实现简单，避免了软件实现中的逻辑漏洞，适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，导致忙等