进程同步的基本概念

复习定位

多个进程同时访问共享资源时如果不加控制——结果将取决于各进程执行的具体顺序——这就是竞态条件——结果不可预测。操作系统必须提供同步机制——保证当进程在临界区内操作共享资源时其他进程不能进入临界区(互斥)——并保证多个进程按期望的次序完成某一工作(同步)。信号量是由Dijkstra提出的经典同步机制。

临界资源与临界区

临界资源是一次只允许一个进程使用的资源——如打印机、共享变量、计数器、文件。多个进程同时使用一台打印机将导致输出混乱——所以必须互斥地使用临界资源。

临界区是进程中访问临界资源的那段代码——而不是进程中所有代码。比如访问共享计数器counter++的汇编指令序列就是临界区。临界区要尽量短——减少互斥给并发带来的性能损失。

访问临界区需要遵循四个原则：

1. 空闲让进——当没有进程在临界区内——允许一个请求进入临界区的进程进入。
2. 忙则等待——当已经有进程在临界区内——其他试图进入的进程必须等待。
3. 有限等待——等不到进入临界区的进程不能饿死——必须在有限时间内进入。
4. 让权等待——等不到进入的进程应该释放CPU(而不是占用CPU空转等待)——让其他进程有机会执行。

Peterson算法——纯软件解决方案

两个进程共享两个标志: flag[0]和flag[1](表示进程想进入临界区)和一个turn变量(表示应该轮到谁)。算法如下(进程P0)——对P1对称:

flag[0] = true;               // 想进临界区
turn = 1;                     // 让给P1
while (flag[1] && turn == 1); // 等P1用完后进行
// 临界区
flag[0] = false;              // 用完退出

Peterson算法满足互斥——一个临界区中最多只有一个进程。同时不会饥饿。但该算法假设flag和turn的读写操作是原子的——现代编译器可能对代码重排——因此Peterson算法实际的C实现可能需要内存栅栏——这使得它的适用性主要局限在普适理论层面——被操作系统内核和锁硬件化的替代解决。

信号量机制

信号量(Semaphore)是一个整数变量——除了初始化外只能通过两个原子操作访问：

• P操作(wait): while(S<=0)等待; S=S-1;
• V操作(signal): S=S+1;

P和V的原子性意味着在P操作中"检测S是否<=0"和"S=S-1"之间——不可以有其他进程插入。这个原子性在单核CPU上通过关中断保证——在多核上通过硬件指令(Test-and-Set或CAS)实现。

信号量的用途：

互斥——设一个互斥信号量mutex初始化为1——在每个进程临界区入口处P(mutex)——出口处V(mutex)。mutex=1代表没进程在临界区——P(mutex)将信号量变为0——其他进程再P(mutex)时等待。V(mutex)将信号量恢复为1——唤醒一个等待进程。

同步——如进程A在向缓冲区写数据之前——进程B必须先在屏幕上打印提示。设信号量sync初始化为0——A的读同步等待前P(sync)——B的输出完成后V(sync)。这样A会一直等待直到B执行完V。

用信号量解决经典同步问题

生产者-消费者问题：生产者进程生产数据放入有限大小的缓冲池——消费者进程从缓冲池取出数据消费。设置mutex=1保护缓冲池、empty=n表示空缓冲区数量、full=0表示满缓冲区数量。生产者：P(empty)→P(mutex)→放入数据→V(mutex)→V(full)。消费者对称：P(full)→P(mutex)→取出数据→V(mutex)→V(empty)。

读者-写者问题：多个读者可以同时访问共享数据——但写者必须独占。使用信号量rw_mutex=1控制写入——读者计数器read_count跟踪读者数量。第一个读者P(rw_mutex)、最后一个读者V(rw_mutex)。写者始终P(rw_mutex)并V(rw_mutex)。此方案优先给读者——如果连续读者持续到达——写者可能永远得不到资源——加一个额外信号量wry_mutex可防止写者无穷饥饿。

复习检查

1. 临界区的四个原则中——"忙则等待"和"有限等待"之间的区别——已经有一个在临界区了——调用P(mutex)的另一个进程必须"让权等待"——使其阻塞还是自旋？

2. 使用信号量实现互斥——初始P(mutex)和最后的V(mutex)——如果V(mutex)被某进程忘记执行——导致什么后果？

3. 生产者-消费者必须同时保证互斥和同步——信号量empty和full的P/V顺序可以颠倒吗？如果先P(mutex)再P(empty)——当缓冲区满时会发生什么？

4. 读者-写者中读者计数器是什么类型的变量——需要mutex保护吗？

5. 竞争条件(Race Condition)和同步的关系——多个进程访问共享变量不协调必然导致对变量操作的预期结果错误——信号量用来同步各进程的执行序列以避免竞争条件。用具体的例子说明这个关系。