初识进程同步与进程互斥

要认识进程的同步，要先从其并发性和异步性说起。并发执行的各个进程能以各自独立的、不可预知的速度向前推进。但有时候，多个进程可能需要相互合作以完成某个任务，因此不能允许这些进程各自为营，需要在某些时刻、某些位置协调他们的工作次序，由此会产生一种直接制约关系，这就叫进程的同步。

在谈到进程的互斥之前，先从资源共享开始。各个并发执行的进程不可避免的要共享一些系统资源。系统资源的共享可以分为两类：互斥共享方式和同时共享方式。互斥共享是指，系统中的某些资源，虽然可以提供给多个进程使用，但是一个时间段内只允许一个进程访问该资源。而同时共享是指，系统中的某些资源，允许一个时间段内由多个进程同时对它们进行访问。我们把一个时间段内只允许一个进程使用的资源成为临界资源。对临界资源的访问，必须互斥地进行。进程的互斥是指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待，当前访问临界资源的进程访问结束释放该资源后，另一个进程才可以去访问该资源。

对临界资源的互斥访问，逻辑上可以概括如下：

1
2
3
4
5
6
do {
	entry section;      //进入区
	critical section;   //临界区
	exit section;       //退出区
	remainder section;  //剩余区
}
  • 进入区：检查是否可进入临界区，如可以，上锁，防止别人进。
  • 临界区：访问临界资源。
  • 退出区：解锁
  • 剩余区：做其他处理

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

  • 空闲让进。临界区空闲的话，可以允许一个请求进入的进程立即进入临界区，不能谁也不让用。
  • 忙则等待：已有进程进入临界区，其他试图进入的必须等待。
  • 有限等待：必须保证请求进入临界区的进程在有限时间内能进入临界区，即不会发生饥饿。
  • 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

  1. 单标志法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int turn = 0;

    P0:
    while (turn != 0);
    critical section;
    turn = 1;
    remainer section;

    P1:
    while (turn != 1);
    critical section;
    turn = 0;
    remainder section;

    单标志法用一个变量turn来指明此时拥有临界区访问权限的进程，每个进程在进入区时只是检查turn的值，看自己是否拥有进入权限，是的话继续运行，不是的话阻塞，进入区并不进行所谓上锁的操作。在一个进程访问完临界区后将turn设置为另一进程的，也就是把临界区的使用权指定给其它进程，逻辑上相当于给自己上锁，给另一进程解锁。这种方法中，进入临界区的权限只能由另一个进程赋予。

    单标志法存在的主要问题是不遵循“空闲让进”的原则。例如P0进程访问结束后设置turn=1，此时临界资源的访问权在P1手上，但是P1进程迟迟不访问该临界资源，也就是说此时临界资源空闲，只有P1能访问但P1偏偏不访问，导致违背”空闲让进“原则。

  2. 双标志先检查法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool flag[2];
    flag[0] = false;
    flag[1] = false;

    P0:
    while (flag[1]);
    flag[0] = true;
    critical section;
    flag[0] = false;
    remainder section;

    P1:
    while (flag[0]);
    flag[1] = true;
    critical section;
    flag[1] = false;
    remainder section;

    双标志先检查法采用flag数组指明每个进程是否有进入临界区的意愿。一个进程开始时先判断对方是否有进入临界区的意愿，如果有，那么自己阻塞，展现风度，不去抢临界区。如果对方没有进入临界区的意愿，那么就将自己的flag置为true，表示自己有进入临界区的意愿，这样当其它进程判断出这个进程有进入意愿的时候，也会谦让（将心比心，我为人人，人人为我）。而在退出临界区时，要再将自己的flag置为false，表示自己没有进入临界区的意愿了，别人不用再谦让它了。

    这种方法看似大家都不争不抢，互相谦让，十分和谐，但是也存在一些问题。两个进程并发执行，可能出现如下的执行顺序：

    • P0先判断，发现P1的flag为false，对方并无进入临界区的意愿，那么自己也就不会阻塞；
    • 在P0还没来得及将自己的flag置为true时，时间片轮转到P1，P1发现P0的flag为false，以为对方并无进入临界区的意愿，那么自己也就不会阻塞；
    • 同样的，P1也没来得及将自己的flag置为true，时间片轮转到P0，P0将自己的flag置为true并访问临界区；
    • 时间片轮转到P1，P1也将自己的flag置为true并访问临界区
    • ……

    从上述过程可以看出，P0和P1可能同时访问临界区，双标志先检查法违背了“忙则等待”的原则。

    这种方法中，双方首先都想着谦让，但是有时候就是这么巧，双方都以为对方确实没有进入的意愿，便决定自己先用，结果一起开始用了。双方都无恶意，甚至都很礼貌，但是结果却产生了冲突。

  3. 双标志后检查法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool flag[2];
    flag[0] = false;
    flag[1] = false;

    P0:
    flag[0] = true;
    while (flag[1]);
    critical section;
    flag[0] = false;
    remainder section;

    P1:
    flag[1] = true;
    while (flag[0]);
    critical section;
    flag[1] = false;
    remainder section;

    为了解决双标志位前检查法的缺陷，出现了双标志后检查法。顾名思义，先改变自己的flag，再去检查对方的flag。即想要进入的进程先声明自己的意愿，再去判断别人是否有意愿，有的话再谦让，没得话自己就进入临界区了。这样就解决了前检查法违背“忙则等待”的问题，但是，通过类比思想不难发现，先改变flag来声明意愿的方式，可能出现双方都改变了flag，表示想要进入临界区，继而都发现对方也有意愿，便都阻塞自己，谦让对方，导致谁也不用的情况，即违背了“空闲让进”的原则。

  4. Peterson算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    bool flag[2];
    flag[0] = false;
    flag[1] = false;
    int turn = 0;

    P0:
    flag[0] = true;
    turn = 1;
    while (flag[1] && turn==1);
    critical section;
    flag[0] = false;
    remainder section;

    P1:
    flag[1] = true;
    turn = 0;
    while (flag[0] && turn==0);
    critical section;
    flag[1] = false;
    remainder section;

    双标志后检查法出现问题的根本原因在于双方无休止的谦让，Peterson算法在双标志位后检查法的基础上增加了turn变量来解决这个问题，turn变量的含义与单标志位方法中的turn一致，都表示哪个进程拥有访问临界区的权限。进程在进入区先改变自己的flag为true，声明自己进入的意愿，然后将turn设为对方，表示将进入权限礼让给对方，之后只有在对方有进入意愿且对方拥有进入权限的时候，自己才会阻塞，在行动上进行谦让。通过这种方法，就避免了双标志后检查法中无休止谦让的情况，因为turn会且仅会赋给一个进程，任何时候都仅能有一个进程拥有进入临界区的权限，因此在判断后不可能双方都阻塞，总有且只会有一个进程不被阻塞，而去访问临界区。

进程互斥的硬件实现方法

  1. 中断屏蔽方法

    使用开关中断的方式实现进程互斥，逻辑上可以概括为：

    1
    2
    3
    关中断；
    临界区；
    开中断；

    进程在开始访问临界区到结束访问临界区的这段时间，是不允许被中断的，也就不会发生进程的切换。这种方式简单高效，但是并不适用于处理多处理机；而且由于开关中断指令只能运行在内核态，因此并不适用于用户进程，仅适用于操作系统内核进程。

  2. TsetAndSet(TS指令)

    TS指令是用硬件实现的，执行的过程不允许被中断，其逻辑可以用代码描述为：

    1
    2
    3
    4
    5
    6
    bool TestAndSet (bool *lock){
        bool old;
        old = *lock;
        *lock = true;
        return old;
    }

    使用TS指令实现互斥的算法逻辑为：

    1
    2
    3
    4
    while (TestAndSet (&lock));
    临界区；
    lock = false;
    剩余区；

    可以发现，本质上在进入区还是在进行检查和上锁的操作，只是相比软件实现方法，这里的检查和上锁是一气呵成的原子操作，也就避免了上面双标志位先检查法和后检查法中可能出现的那些违反“忙则等待”或“空闲让进”的问题。且相比于中断屏蔽方法，TS指令能够适用于多处理机环境。

  3. Swap指令(XCHG指令)

    Swap指令是另一种硬件实现进程互斥的方法，其逻辑可以用代码描述为：

    1
    2
    3
    4
    5
    6
    Swap (bool *a, bool *b) {
        bool temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }

    使用Swap指令实现互斥的算法逻辑为：

    1
    2
    3
    4
    5
    6
    bool old = true;
    while (old == true)
        swap (&lock, &old);
    临界区；
    lock= false；
    剩余区

    本质上与TS指令无太大区别，优缺点与TS指令也一致，硬件实现的重点在于原子操作能保证检查与上锁的一气呵成，不会在某种特定执行顺序下产生逻辑漏洞。

    上述这些软硬件方法都还未实现“有限等待”和“让权等待“。