OS: Process Synchronization

Critical-section Problem

一个好的解决方案需要符合以下 3 点

软件实现的用于两个进程间互斥访问临界区的方法

缺点，不使用于多处理器多进程同步的情况。

只能在内核中使用

原子的硬件实现的指令，实现如下逻辑功能

bool TestAndSet (bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

使用时进行如下操作

while (TestAndSet(&lock));
// critical section
lock = false;

适用于多处理器，但不满足让权等待。

硬件指令实现如下功能

void CompareAndSwap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

使用时进行如下操作

bool old = true;
while (old == true)
    CompareAndSwap(&lock, &old);
// critical section
lock = false;

互斥锁，上锁解锁操作具有原子性。

信号量，解决了上面所有方法都不能“让权等待”的问题。 wait(S) 和 signal(S) 操作具有原子性，这两个操作也称 P(S)，V(S) 操作。其中 wait 操作时会阻塞进程，而非自旋忙等。Semaphore 数据结构的定义如下

typedef struct {
    int value;
    struct Process *L;
} Semaphore;

为什么要引入管程？在出现管程之前，人们就是手动写 PV 操作来实现进程同步。管程就是编程语言内对同步机制的更高层的抽象，如 JAVA 中的 synchronized 关键字，表明一个函数或一个对象在同一时间内只能被一个线程调用，这个是由语言的编译器或解释器实现的。

必要条件

静态策略

动态策略，银行家算法，定义一种更容易通过规则保证和维护的安全状态，安全状态是不会发生死锁的状态的超集。

安全序列是按照一个特定的序列执行并发的任务，每个进程都能顺利完成并释放资源。只要能找到一个安全序列，当前状态就是安全状态。

资源分配图：一种数据结构，有两种节点

和两种边

当一个进程能够正常执行结束时，将其所有的边删除。如果出现死锁，则资源分配图中无法消除所有的边。

执行这些操作时，可以考虑进程的特征