进程同步

约 7522 个字 291 行代码 5 张图片 预计阅读时间 41 分钟

• 同步(Synchronization): 一个进程等待另一个进程完成某个操作后才能继续执行的机制.

• 异步(Asynchronization): 进程不需要等待其他进程完成操作,可以独立执行.

  实际上和数逻里面的同步异步是一个意思.

• 互斥(Mutual Exclusion): 确保多个进程在同一时间只能有一个进程访问共享资源的机制.

Example

有两个进程（线程）P1、P2，它们分别执行下面的程序，其中 total 是两个进程都能访问的共享变量，初值为 0（可理解为共享存储段中的存储单元），count 是每个进程的私有变量。假设这两个进程并发执行，并可自由交叉（interleave），则这两个进程都执行完后，变量 total 可能得到的最小取值是：

A. 50 B. 1 C. 2 D. 3

P1:

{
    int count;
    for (count = 1; count <= 50; count++)
        total = total + 1;
}

P2:

{
    int count;
    for (count = 1; count <= 50; count++)
        total = total + 2;
}

解答

total = total + 1 的操作可以分解为三个子操作：

1. 读 total 的值到寄存器 R 中
2. 在寄存器 R 中进行加法运算
3. 将寄存器 R 的值写回 total

假设 P1 和 P2 的交叉执行如下：

1. P1 读 total 的值 0 到寄存器 R 中，执行加法，R 变为 1
2. P2 直接进行 49 次循环（此时 P2 在寄存器中累加，但尚未写回）
3. 在 P2 进行第 50 次循环前，P1 将第一次循环的结果写回 total，导致 P2 读到的 total 是 1
4. P2 继续进行第 50 次循环，将寄存器 R 增加 2（基于它之前读到的值）
5. P1 继续进行剩下的 49 次循环并按其逻辑写回
6. P2 最后将其寄存器值写回 total，最终结果为 3

从上面的例子可以看出：当两个并发进程在没有适当同步的情况下操作同一共享变量时，可能会导致数据不一致。

那么，何时需要对两个进程进行同步？我们可以通过判断是否存在 Race Condition（竞争条件）来确定。

---

我们称两个或多个进程在访问共享资源时，如果它们的执行顺序会影响最终结果，就存在竞争条件.

竞争条件带来了临界区问题(Critical Section Problem)

临界区问题

当n个进程竞争某一共享资源时,每个进程都有一段代码,称为临界区(Critical Section),在这段代码中访问共享资源.

我们要考虑如何设计进程的执行顺序,使得在任何时刻,最多只有一个进程在其临界区内执行.

一次只允许一个进程访问的资源叫临界资源.临界资源的访问,可以分为四个步骤:

1. Entry Section: 进程请求进入临界区的代码段.在这里检查临界区是否空闲,并且如果能够进入临界区,则需要标记临界区为忙碌状态.

2. Critical Section: 进程访问临界资源的代码段.在这里,进程可以安全地访问和修改共享资源.

3. Exit Section: 进程离开临界区的代码段.在这里,进程需要标记临界区为空闲状态,以便其他进程可以进入.

4. Remainder Section: 进程在临界区之外执行的代码段.在这里,进程可以执行不涉及共享资源的操作.

所有能够解决临界区问题的算法,都必须满足以下三个条件:

1. 互斥(Mutual Exclusion): 在任何时刻,最多只有一个进程可以在其临界区内执行.

2. 空闲让进(Progress): 如果临界区为空闲,并且有一个或多个进程请求进入临界区,那么进入临界区的请求不能被无限推迟.也就是说,能进入的时候一定要立即进入.

3. 有限等待(Bounded Waiting): 每个进程在请求进入临界区后,都有一个有限的等待时间,不会被其他进程无限期地阻塞.

还有一个原则上需要,但是非必须的条件:

• 让权等待:当进程不能进入临界区时,它应该释放自己的CPU使用权,让其他进程运行.

Peterson算法

这是一个软件解决方案,适用于两个进程的临界区问题.

在介绍Peterson算法之前,我们先看看别的解决方案为什么不行.

单标志法

对于两个进程\(P_0\)和\(P_1\),我们设置一个共享变量turn,当turn为0时,表示允许\(P_0\)进入临界区;当turn为1时,表示允许\(P_1\)进入临界区.

进程P0

while(turn != 0);   // 进入区
critical section;   // 临界区
turn = 1;           // 退出区
remainder section;  // 剩余区

进程P1

while(turn != 1);   // 进入区
critical section;   // 临界区
turn = 0;           // 退出区
remainder section;  // 剩余区

这个方法满足了互斥条件,但是不满足空闲让进条件.假设turn为0,允许\(P_0\)进入临界区,但是\(P_0\)此时并不需要进入临界区,而\(P_1\)却需要进入临界区.由于\(P_0\)无法运行,turn的值没有改变,\(P_1\)将被无限期地阻塞.

双标志先检查法

设置一个bool类型的数组flag[2],表示每个进程是否想要进入临界区.

进程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;  // 剩余区

这个算法会违背互斥原则.例如,如果\(P_0\)先执行到while(flag[1]);时,此时flag[1]为false,所以\(P_0\)继续执行,但在\(P_0\)设置flag[0] = true;之前,如果\(P_1\)也执行到while(flag[0]);,此时flag[0]为false,所以\(P_1\)也继续执行,这样两个进程就都进入了临界区,违反了互斥条件.

双标志后检查法

针对“先检查再设置”会导致的竞态问题，改进思路是“先设置再检查”。

进程 P0（示意）

flag[0] = true;        // 1: 先设置自己的标志
while (flag[1]) ;      // 3: 检查对方的标志，若为 true 则等待
// critical section;  // 临界区
flag[0] = false;       // 退出区
remainder section;

进程 P1（示意）

flag[1] = true;        // 2: 先设置自己的标志
while (flag[0]) ;      // 4: 检查对方的标志
// critical section;  // 临界区
flag[1] = false;       // 退出区
remainder section;

如果两个进程按序列 1 → 2 → 3 → 4 执行（即双方先后设置各自的标志，然后各自检查对方），会出现双方都发现对方也想进入临界区而互相等待的情况。该情况违背“空闲让进（Progress）”原则，且可能导致长期无法进入临界区的“饥饿”现象（违背“有限等待（Bounded Waiting）”）。

---

Peterson算法综合了上述两种方法的优点,并且避免了它们的缺点.

同时使用一个bool类型的数组flag[2],表示每个进程是否想要进入临界区,以及一个整型变量turn,表示偏向于让哪个进程进入临界区.

每个进程进入临界区之前,先设置自己的flag标志,再给对方设置允许进入turn标志,表达"谦让";之后,再同时 检测对方的flag和 turn标志.

进程P0

flag[0] = true;        // 1: 表示 P0 想进入临界区
turn = 1;              // 2: 表示 P0 谦让 P1
while (flag[1] && turn == 1) ; // 3: 检测 P1 的状态
critical section;      // 临界区
flag[0] = false;       // 退出区
remainder section;     // 剩余区

进程P1

flag[1] = true;        // 1: 表示 P1 想进入临界区
turn = 0;              // 2: 表示 P1 谦让 P0
while (flag[0] && turn == 0) ; // 3: 检测 P0 的状态
critical section;      // 临界区
flag[1] = false;       // 退出区
remainder section;     // 剩余区

当两个进程都想进入临界区时,它们都会设置turn,但最终turn只会被赋给一个值,因此只有一个进程能够通过while循环进入临界区,从而保证了互斥性.当这个进程执行完之后,它会将自己的flag设置为false,允许另一个进程进入临界区.

Peterson算法满足互斥、空闲让进和有限等待三个条件,因此它是一个有效的解决临界区问题的算法,但没有满足让权等待条件.

硬件同步机制

禁止中断

由于进程的切换需要操作系统的调度,而调度需要中断,当一个进程在执行它的临界区代码时,可以禁止中断,这样就可以保证在它执行完临界区代码之前,不会发生进程切换.

然而这种方法的缺点很明显:

• 禁止中断会导致系统无法响应其他事件,降低系统的响应能力.

• 禁止中断只能在单处理器系统中使用,在多处理器系统中,其他处理器仍然可以访问共享资源.

Test-and-Set

Test-and-Set 是一种原子操作,用于实现进程间的互斥.

TS指令的效果是读出一个内存位置的值,然后将该值设置为1.这个操作是原子的,即在执行过程中不会被中断.

Test-and-Set 指令

int TestAndSet(int *lock) {
    int oldValue = *lock; // 读取目标地址的值
    *lock = 1;            // 设置目标地址的值为1
    return oldValue;        // 返回旧值
}

利用TS来实现同步的机制很简单,就是为每个共享资源设置一个锁变量lock,初始值为0.当一个进程想要进入临界区时,它先执行TestAndSet(lock),检查返回结果.如果返回值为0,表示锁是空闲的,进程可以进入临界区.如果返回值为1,表示锁已经被其他进程占用,进程需要等待.

使用 Test-and-Set 实现互斥

int lock = 0; // 锁变量,初始值为0
while(TestAndSet(&lock));//Entry Section
// Critical Section
lock = 0; // Exit Section

这种方法的优点是简单易用,并且可以在多处理器系统中使用.但是它也有缺点,那就是不能实现让权等待,因为进程需要CPU资源来一直执行TestAndSet指令,如果锁被其他进程占用,它就会一直忙等,浪费CPU资源.

Swap

Swap 指令是另一种原子操作,用于实现进程间的互斥.

Swap 指令的效果是交换两个内存位置的值,这个操作也是原子的,即在执行过程中不会被中断.

Swap 指令

int Swap(int *a, int *b) {
    int temp = *a; // 读取 a 的值
    *a = *b;       // 将 b 的值赋给 a
    *b = temp;    // 将原来的 a 的值赋给 b
    return temp;  // 返回原来的 a 的值
}

Swap来实现同步的机制和Test-and-Set类似,每个共享资源有一个锁变量,初值为0,每个进程有一个自己的变量key,初值为1.当一个进程想要进入临界区时,它先执行Swap(&lock, &key),检查返回结果.如果返回值为0,表示锁是空闲的,进程可以进入临界区,并且此时锁已经是被占用的状态。如果返回值为1,表示锁已经被其他进程占用,进程需要等待.

使用 Swap 实现互斥

int lock = 0; // 锁变量,初始值为0
int key = 1;  // 进程的私有变量,初始值为1
while(Swap(&lock, &key) != 0); // Entry Section
// Critical Section
lock = 0; // Exit Section

然而,Swap方法也同样没有解决让权等待的问题.同时,它也可能导致饥饿的发生.

改进的Test-and-Set (有界等待)

为了解决上述硬件方法中可能存在的“饥饿”问题，并满足“有限等待”原则，我们介绍如下算法。该算法为每个希望进入临界区的进程设置了一个排队队列 waiting。

思路:

1. 当一个进程希望进入临界区时，它首先在自己的 waiting 标志中“排队”。

2. 然后，它使用 TestAndSet 尝试获取锁。如果获取失败，它会继续自旋等待。

3. 当一个进程离开临界区时，它不会立即释放锁。而是检查 waiting 队列，寻找下一个正在等待的进程（按循环顺序 (i+1)%n 查找）。

4. 如果找到了等待者 j，它会直接将 waiting[j] 设置为 false，相当于“叫号”，让进程 j 退出自旋并进入临界区。这样锁就从进程 i “传递”给了进程 j。

5. 如果没有其他进程在等待，它才会释放全局锁 lock。

实现:

boolean waiting[n]; // 排队队列，初值均为 false
boolean lock;       // 锁变量，初值为 false

while(1) {
    // Entry Section
    waiting[i] = true;
    key = true;
    while (waiting[i] && key) {
        key = TestAndSet(&lock);
    }
    waiting[i] = false;

    // Critical Section

    // Exit Section
    j = (i + 1) % n;
    while ((j != i) && !waiting[j]) {
        j = (j + 1) % n;
    }

    if (j == i) { // 如果没有其他进程在等待
        lock = false;
    } else { // 将“锁”直接传递给下一个等待的进程
        waiting[j] = false;
    }

    // Remainder Section
}

这样做确保了想要进入临界区的进程最多只需等待 n-1 个其他进程，从而满足了“有限等待”的要求，避免了饥饿现象。不过，它仍然没有解决“让权等待”的问题，因为等待的进程会处于“忙等”状态，消耗CPU资源。

互斥锁

也叫自旋锁,是一个高级的同步机制,用于实现进程间的互斥.

互斥锁(Mutex)是一个特殊的锁,它可以被多个进程共享,但在同一时刻只能有一个进程持有它.当一个进程想要进入临界区时,它需要先获取互斥锁,如果锁已经被其他进程持有,则该进程会被阻塞,直到锁被释放.

实际实现的机制和上面是一样的.

mutex_t lock; // 互斥锁
void acquire(mutex_t *lock) {
    while(!available(lock)) {
        // 等待锁可用
    }
    lock->flag = true; // 获取锁
}
void release(mutex_t *lock) {
    lock->flag = false; // 释放锁
}

信号量 (Semaphore)

信号量与两个原语有关:

• P操作（Proberen，荷兰语“尝试”）：用于请求资源或进入临界区。也称wait或down操作。

• V操作（Verhogen，荷兰语“增加”）：用于释放资源或离开临界区。也称signal或up操作。

整型信号量

整型信号量是最基本的信号量类型,它的值代表了可用资源的数量.

整型信号量允许三个操作,分别是初始化、P操作和V操作.

整型信号量的实现

typedef struct {
    int value; // 信号量的值
} semaphore_t;

void init_semaphore(semaphore_t *sem, int initial_value) {
    sem->value = initial_value;
}

void P(semaphore_t *sem) {
    while (sem->value <= 0); // 忙等
    sem->value--;
}

void V(semaphore_t *sem) {
    sem->value++;
}

记录型信号量

解决了整型信号量的忙等问题,允许多个进程等待同一个信号量.

最大的改动就是在数据结构中增加了一个等待队列,用于存放等待该信号量的进程.

记录型信号量的实现

typedef struct {
    int value; // 信号量的值
    queue_t waiting_queue; // 等待队列
} semaphore_t;
void P(semaphore_t *sem) {
    sem->value--;
    if (sem->value < 0) {
        // 将进程加入等待队列并阻塞,运行->阻塞
        enqueue(sem->waiting_queue, current_process);
        block(current_process);
    }
}

void V(semaphore_t *sem) {
    sem->value++;
    if (sem->value <= 0) {
        // 从等待队列中唤醒一个进程,阻塞->就绪
        process_t *proc = dequeue(sem->waiting_queue);
        wakeup(proc);
    }
}

---

利用信号量实现互斥:

1. 初始化一个信号量mutex为1.

2. 每个进程的临界区代码前执行P(&mutex)操作,进入临界区后执行V(&mutex)操作.

   利用信号量实现互斥

   semaphore_t mutex=1;
   
   P1(){
       P(&mutex); // 进入临界区
       // 临界区代码
       V(&mutex); // 离开临界区
   }
   
   P2(){
       P(&mutex); // 进入临界区
       // 临界区代码
       V(&mutex); // 离开临界区
   }
   

---

利用信号量实现同步:

如果一个进程要用某种资源,则必须先执行P操作,如果资源不可用,则该进程被阻塞;当另一个进程产生了该资源后,执行V操作,唤醒等待该资源的进程.

1. 初始化一个信号量sync为0.(为了实现同步,需要P1先产生一个资源,然后P2才能使用这个资源,所以初始值为0)

2. P1在产生资源后执行V(&sync)操作,表示资源已经可用.

3. P2在使用资源前执行P(&sync)操作,如果资源不可用则阻塞等待.

   利用信号量实现同步

   semaphore_t sync=0;
   P1(){
       // 产生资源
       V(&sync); // 资源可用
   }
   
   P2(){
       P(&sync); // 等待资源可用
       // 使用资源
   }
   

经典同步问题

生产者-消费者问题

生产者-消费者问题也称有限缓冲问题（Bounded-Buffer Problem）。

问题描述:

系统中有一组生产者进程和一组消费者进程。它们共享一个初始为空、大小为 n 的缓冲区。

• 生产者: 每次生产一个产品并放入缓冲区。

• 消费者: 每次从缓冲区中取出一个产品并消费。

约束条件:

1. 只有当缓冲区未满时，生产者才能放入产品，否则必须等待。

2. 只有当缓冲区不空时，消费者才能取出产品，否则必须等待。

3. 缓冲区是临界资源，各进程必须互斥地访问。

问题分析:

1. 关系分析:

   • 互斥关系: 生产者和消费者在访问缓冲区时是互斥的。

   • 同步关系: 生产者生产后，消费者才能消费。生产者需要等待缓冲区有空位，消费者需要等待缓冲区有产品。

2. 信号量设置:

   • mutex: 互斥信号量，用于保证对缓冲区的互斥访问，初值为 1。

   • empty: 记录缓冲区中“空”槽位的数量，初值为 n。

   • full: 记录缓冲区中“满”槽位（即产品）的数量，初值为 0。

实现方案:

semaphore mutex = 1;  // 临界区互斥信号量
semaphore empty = n;  // 空闲缓冲区数量
semaphore full = 0;   // 满缓冲区（产品）数量

producer() {
    while(1) {
        // 生产一个产品...

        P(empty);       // 消耗一个空槽位 (同步)
        P(mutex);       // 进入临界区 (互斥)

        // 将产品放入缓冲区...

        V(mutex);       // 离开临界区 (互斥)
        V(full);        // 增加一个产品 (同步)
    }
}

consumer() {
    while(1) {
        P(full);        // 消耗一个产品 (同步)
        P(mutex);       // 进入临界区 (互斥)

        // 从缓冲区取出一个产品...

        V(mutex);       // 离开临界区 (互斥)
        V(empty);       // 增加一个空槽位 (同步)

        // 消费产品...
    }
}

P操作顺序的重要性：避免死锁

在上述代码中，同步操作 P(empty) 和 P(full) 必须在互斥操作 P(mutex) 之前执行。如果顺序颠倒，可能会导致死锁。

假设生产者先执行 P(mutex)，再执行 P(empty)。

1. 当缓冲区已满时 (empty = 0)，一个生产者进程运行。

2. 该生产者成功执行 P(mutex)，获得了缓冲区的互斥访问权。

3. 接着，它执行 P(empty)，但因为没有空槽位，该生产者进程被阻塞。关键在于，它在阻塞时并没有释放 mutex 锁。

4. 此时，轮到消费者进程运行。它想要从缓冲区取走产品，于是尝试执行 P(mutex) 以进入临界区。

5. 然而，mutex 锁已被阻塞的生产者持有，所以消费者也被阻塞。

6. 最终，生产者等待消费者释放空槽位，而消费者等待生产者释放 mutex 锁，两者互相等待，形成死锁。

相比之下，V 操作的顺序则没有严格要求，V(mutex) 和 V(full)/V(empty) 的顺序可以互换，不会影响程序的正确性。

读者-写者问题

问题描述:

有读者和写者两组并发进程，它们共享一个文件。

约束条件:

1. 允许多读: 多个读者可以同时对文件执行读操作。

2. 写者互斥: 只允许一个写者往文件中写信息。

3. 读写互斥: 任意一个写者在完成写操作之前，不允许其他读者或写者工作。

4. 写者优先: 当一个写者准备好写入时，它应该尽快执行，不应有新的读者开始读。

问题分析:

1. 关系分析:

   • 读者-写者: 互斥。

   • 写者-写者: 互斥。

   • 读者-读者: 允许并发访问，不互斥。

2. 思路:

   • 写者进程与任何其他进程（读或写）都互斥，这部分比较简单，可以用一个互斥信号量解决。
   • 读者进程的逻辑较为复杂。需要引入一个计数器 count 来记录当前正在读的读者数量。
   • 只有当 count 为 0 时（即没有读者在读），写者才能开始写。
   • 多个读者对计数器 count 的访问本身也需要互斥。

方案一：读者优先

该算法中，只要有任何一个读者在读，后续的读者都可以直接进入，而写者必须等待所有读者都离开。

信号量设置:

• rw: 互斥信号量，用于实现读者和写者之间的互斥，以及写者和写者之间的互斥。初值为 1。
• mutex: 互斥信号量，用于保护对计数器 count 的互斥访问。初值为 1。
• count: 整型变量，记录当前读者的数量，初值为 0。

实现:

int count = 0;          // 记录当前读者数量
semaphore mutex = 1;    // 用于保护 count 的互斥信号量
semaphore rw = 1;       // 用于读者和写者互斥的信号量

writer() {
    while(1) {
        P(rw);          // 锁定文件，实现与其他写者或读者的互斥
        // 写文件...
        V(rw);          // 释放文件
    }
}

reader() {
    while(1) {
        P(mutex);       // 互斥访问 count
        if (count == 0) { // 如果是第一个读者
            P(rw);      // 则需要锁定文件，阻止写者进入
        }
        count++;
        V(mutex);       // 释放对 count 的锁

        // 读文件...

        P(mutex);       // 互斥访问 count
        count--;
        if (count == 0) { // 如果是最后一个读者
            V(rw);      // 则需要释放文件，允许写者进入
        }
        V(mutex);       // 释放对 count 的锁
    }
}

读者优先的问题

在这种策略下，如果读者源源不断地到来，写者进程可能会长时间等待，甚至被“饿死”。

方案二：写者优先（公平读写）

为了避免写者饥饿，可以增加一个信号量，实现一个“写者优先”的策略。当有写者请求访问时，会阻止新的读者进入，等待已有的读者退出后，写者就能立即执行。

新增信号量:

• w: 用于实现“写优先”的信号量，初值为 1。它构成了一个门，让读者和写者在尝试访问文件前先通过这扇门。

实现:

int count = 0;
semaphore mutex = 1;
semaphore rw = 1;
semaphore w = 1;        // 实现写优先

writer() {
    while(1) {
        P(w);           // 在与其他写者竞争前，先抢占“门”
        P(rw);          // 互斥访问文件
        // 写文件...
        V(rw);
        V(w);           // 释放“门”
    }
}

reader() {
    while(1) {
        P(w);           // 在无写者请求时进入
        P(mutex);
        if (count == 0) {
            P(rw);      // 第一个读者锁定文件
        }
        count++;
        V(mutex);
        V(w);           // 允许其他读者或写者进入

        // 读文件...

        P(mutex);
        count--;
        if (count == 0) {
            V(rw);      // 最后一个读者释放文件
        }
        V(mutex);
    }
}

关于“写者优先”的说明

这个算法通常被称为“公平读写”算法，而非严格的“写者优先”。因为如果一个读者比一个写者先到达并在信号量 w 上等待，那么当 w 被释放时，排在等待队列头部的读者会先被唤醒。它只是保证了当一个写者正在等待时，不会有新的读者能够开始读取。

哲学家就餐问题

有\(N\)个哲学家坐在一张圆桌旁,每个哲学家与邻居共享一只筷子.哲学家有两种状态:思考和就餐.当一个哲学家想要就餐时,他必须同时拿起左边和右边的筷子.如果某个筷子被邻居拿走了,则该哲学家必须等待.

就餐问题

在这个问题中,共享资源是:

• chopstick[i]: 表示第i个筷子是否被占用.

每个哲学家的行为可以表示为以下伪代码:

while (true) {
    wait(chopstick[i]);   // 请求左边的筷子
    wait(chopstick[(i+1) % N]); // 请求右边的筷子
    // 就餐
    signal(chopstick[i]); // 释放左边的筷子
    signal(chopstick[(i+1) % N]); // 释放右边的
    // 思考
}

但是很显然,这种做法会导致死锁.假设所有哲学家同时拿起左边的筷子,那么每个哲学家都在等待右边的筷子,从而形成死锁.

为了解决死锁,改进的方法有:

1. 限制并发人数（N-1 策略）

2. 思路：在允许同时尝试取筷子的哲学家数少于哲学家总数（最多 N-1），保证至少有一个人能同时拿到左右两只筷子，从而避免循环等待。

3. 伪代码：

   semaphore room = N - 1;
   semaphore fork[N] = {1,...,1};
   
   philosopher(i) {
       while (true) {
           think();
           P(&room);                // 控制并发人数
           P(&fork[i]);             // 先拿左筷子
           P(&fork[(i+1)%N]);       // 再拿右筷子
           eat();
           V(&fork[i]);
           V(&fork[(i+1)%N]);
           V(&room);
       }
   }
   

4. 奇偶/不对称策略

5. 思路：让奇数编号的哲学家先拿左再拿右，偶数编号的哲学家先拿右再拿左。避免所有哲学家都按照相同顺序拿筷子，从而打破循环等待。
6. 伪代码：

   if (i % 2 == 0) { P(&fork[i]); P(&fork[(i+1)%N]); }
   else { P(&fork[(i+1)%N]); P(&fork[i]); }
   

死锁

死锁的产生是由于多个进程在竞争有限的资源时,每个进程都持有一些资源并等待其他进程释放它们所需的资源,从而导致所有进程都无法继续执行.

死锁的必要条件

1. 互斥条件: 资源不能被多个进程共享,只能被一个进程占用.

2. 占有且等待条件: 一个进程至少持有一个资源,并且等待获取其他被其他进程占用的资源.

3. 非抢占条件: 资源不能被强制从一个进程中夺取,只能由该进程自己释放.

4. 循环等待条件: 存在一个进程循环等待的链,其中每个进程都在等待下一个进程所持有的资源.

资源分配图 (Resource-Allocation Graph)

为了更精确地描述死锁，我们可以引入资源分配图。这是一个有向图，由一组顶点 V 和一组边 E 构成。

1. 顶点 (Vertices)

顶点 V 分为两种类型：

• 进程 P: \(P = \{P_1, P_2, \dots, P_n\}\)，代表系统中所有活跃的进程。

• 资源类型 R: \(R = \{R_1, R_2, \dots, R_m\}\)，代表系统中所有的资源类型。每个资源类型 \(R_j\) 可能有多个实例（instance）。

2. 边 (Edges)

• 请求边 (Request Edge): 从进程 \(P_i\) 指向资源 \(R_j\) 的有向边 (\(P_i \to R_j\))。它表示进程 \(P_i\) 正在请求资源 \(R_j\) 的一个实例。
• 分配边 (Assignment Edge): 从资源 \(R_j\) 指向进程 \(P_i\) 的有向边 (\(R_j \to P_i\))。它表示资源 \(R_j\) 的一个实例已经被分配给了进程 \(P_i\)。

资源分配图示例

存在死锁的资源分配图

有环但无死锁的资源分配图

3. 通过资源分配图判断死锁

• 如果图中没有环，则系统一定没有发生死锁。
• 如果图中存在环，则可能发生了死锁。
  • 情况一: 如果每个资源类型都只有一个实例，那么环的存在是死锁的充分必要条件。
  • 情况二: 如果某些资源类型有多个实例，环的存在仅是死锁的必要不充分条件。此时，存在环不一定意味着死锁，如上图“有环但无死锁”所示。

死锁定理: 系统处于死锁状态的充分条件是，当且仅当该状态下的资源分配图是不可完全简化的。这里的“简化”指的是通过一系列操作（如释放资源、满足请求）来消除图中的所有边。如果最后无法消除所有边，则说明系统发生了死锁。

“可完全简化”图的判定步骤:

1. 第一步: 先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞的（“不阻塞”即：系统有足够的空闲资源分配给它）。
2. 第二步: 把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来。
3. 第三步: 看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。
4. 第四步: 最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。

如果一个图可完全简化，则不会产生死锁；如果一个图不可完全简化（即：图中还有“边”存在），则会产生死锁。这就是“死锁定理”。

死锁处理

处理死锁的方法主要有三种:死锁预防、死锁避免和死锁检测与恢复.

死锁预防

预防死锁的方法是通过破坏死锁产生的四个必要条件中的一个或多个来实现的。

1. 破坏互斥条件: 允许资源被多个进程共享。例如,读者-写者问题中,多个读者可以同时访问共享资源.但是这个方法并不通用,有许多资源都是无法共享的.

2. 破坏占有且等待条件: 要求进程在请求资源时,必须一次性申请它所需要的所有资源,如果资源不足,则不允许进程占有任何资源.这种方法可能会导致资源利用率降低,因为进程可能会占有一些它暂时不需要的资源.有些资源只在进程初期有用,有些资源只在进程后期有用,一次性申请所有资源会导致资源的浪费.

   • 一种改进方法是允许进程在获取运行初期所需的资源后,就开始运行.直到进程释放了自己拥有的所有资源后,才能再次申请新的资源.

3. 破坏非抢占条件: 当一个持有不可抢占资源的进程请求不可用资源时,系统可以强制该进程释放它所持有的所有资源,并将这些资源分配给请求的进程.这种方法可能会导致进程频繁地被抢占,从而降低系统的效率.

4. 破坏循环等待条件: 给每个资源类型赋予一个唯一的编号,要求进程按照递增的顺序请求资源.这样就可以防止循环等待的发生.例如,如果一个进程已经持有了编号为i的资源,则它只能请求编号大于i的资源.

死锁避免

与死锁预防不同的是,死锁避免在每次分配资源时分析这次分配会不会带来死锁,而不是事先采取某些措施让死锁根本不会出现.

安全状态

安全状态指的是系统存在一种资源分配序列,使得按照序列的顺序分配资源的情况下,系统中的所有进程都能顺利完成它们的任务,即使它们都请求它们所需要的最大资源.

这个序列被称为安全序列。一个进程序列 \(<P_1, P_2, \dots, P_n>\) 是安全的，如果对于序列中的每一个进程 \(P_i\)，其未来仍然可能请求的资源数量，可以由当前系统可用的资源，加上所有排在它前面的进程 \(P_j\)（其中 \(j < i\)）所持有的资源来共同满足。

换言之：

• 如果进程 \(P_i\) 的资源需求不能立即被满足，那么 \(P_i\) 可以等待所有在它之前的进程 \(P_j\)（\(j < i\)）完成。

• 当一个进程 \(P_j\) 完成后，它会释放所持有的资源。这使得进程 \(P_i\) 最终能够获得它所需要的资源，然后执行、归还已分配的资源并终止。

• 当 \(P_i\) 终止后，下一个进程 \(P_{i+1}\) 就可以获得它所需要的资源，以此类推，直到所有进程都完成。

如果系统处于安全状态,则不会发生死锁.相反,如果系统处于不安全状态,则有可能发生死锁.

1. 资源分配图算法: 适用于每个资源类型只有一个实例的情况.通过检测资源分配图中的环来判断是否会发生死锁.

   • 在前面讲的基础上,加上一种新的边:

     • 假设边 (Claim Edge): 从进程 \(P_i\) 指向资源 \(R_j\) 的虚线 (\(P_i \dashrightarrow R_j\)). 它表示进程 \(P_i\) 可能在未来请求资源 \(R_j\) 的一个实例。

   • 在资源分配图中,假设边表示进程可能会请求的资源.当进程实际请求资源时,假设边变为请求边;当资源被分配给进程时,请求边变为分配边.

   • 如果进程\(P_i\)请求资源\(R_j\)时,只有在\(P_i \dashrightarrow R_j\)变为分配边\(R_j \to P_j\)之后,不会出现环,则允许分配资源给进程\(P_i\);否则,拒绝分配.

2. 银行家算法

内容较多,见银行家算法

死锁检测

Info

每种资源只有一个实例每种资源有多个实例

在这样的情况下,我们引入一个新概念: 等待图 (Wait-for Graph)

• 等待图是资源分配图的变形。

• 节点 (Nodes): 图中的节点代表进程。

• 边: 如果 \(P_i\) 正在等待 \(P_j\)，则存在一条从 \(P_i\) 到 \(P_j\) 的有向边 (\(P_i \to P_j\))。

• 检测: 定期调用算法在图中搜索环。

• 复杂度: 检测图中是否存在环的算法需要 \(n^2\) 数量级的操作，其中 \(n\) 是图中的顶点数。

这种情况下的检测做法类似于银行家算法，但有以下关键区别。

死锁检测算法 (Deadlock Detection Algorithm)

1. 数据结构:

   • Available: 长度为 \(m\) 的向量，表示每种资源的可用数量。

   • Allocation: \(n \times m\) 矩阵，表示每个进程当前持有的资源数量。

   • Request: \(n \times m\) 矩阵，表示每个进程当前请求的资源数量。（注意：这里是 Request 而不是银行家算法中的 Need）。

2. 算法步骤:

   • • Work = Available

     初始化:

     • 对于 \(i = 1, \dots, n\):

       • 如果 Allocation[i] != 0，则 Finish[i] = false

       • 否则，Finish[i] = true (不占有资源的进程不会导致死锁)

   • 查找: 找到一个下标 \(i\) 满足：

     • Finish[i] == false

     • Request[i] <= Work

   • 分配与回收: 如果找到这样的 \(i\):

     • Work = Work + Allocation[i]

     • Finish[i] = true

     • 以此类推，重复查找步骤。

   • 判断: 如果没有这样的 \(i\) 存在，且此时仍有 Finish[i] == false，则系统处于死锁状态，且进程 \(P_i\) 参与了死锁。

   该算法的时间复杂度为 \(O(m \times n^2)\):

   • 这是因为在最坏的情况下,算法需要遍历\(n\)次进程列表(假设每次只能找到一个可以Finish的进程),每次遍历\(n\)个进程,对于每个未完成的进程都需要比较其\(m\)个资源请求是否小于等于当前可用资源。故总的时间复杂度为\(O(m \times n^2)\)

死锁恢复

当检测到死锁后,系统可以采取两种基本措施:通知系统管理员(人工干预)或让系统自动恢复.

系统自动恢复主要通过打破死锁来实现,主要有两种方法:进程终止和资源抢占.

进程终止 (Process Termination)

1. 终止所有死锁进程 (Abort all deadlocked processes):

   • 这种方法最简单,但代价很大.因为这些进程可能已经计算了很长时间,终止它们意味着这些计算成果都将丢失,必须重新计算.

2. 逐个终止进程 (Abort one process at a time):

   • 每次终止一个进程,直到死锁循环被消除.
   • 这种方法的开销较大,因为每次终止一个进程后,都需要重新运行死锁检测算法,以确定死锁是否已被消除.

选择被终止进程的依据: 在选择终止哪个进程时,通常会考虑以下因素(类似于调度算法):

• 进程的优先级 (Priority).

• 进程已运行的时间以及完成任务还需要的时间.

• 进程已使用的资源数量和类型.

• 进程完成任务还需要多少资源.

• 需要终止多少个进程才能打破死锁.

• 进程是交互式(interactive)的还是批处理(batch)的.

资源抢占 (Resource Preemption)

如果不终止进程,也可以通过抢占资源来打破死锁.即从一个或多个进程中夺取资源,并将这些资源分配给其他进程.

1. 选择受害者 (Selecting a victim):

   • 也就是选择抢占哪个进程的资源.
   • 主要原则是最小化代价 (minimize cost).例如,抢占一个使用了较少资源的进程的资源,或者抢占一个刚刚开始运行的进程的资源.

2. 回滚 (Rollback):

   • 当一个进程的资源被抢占后,它无法继续执行.
   • 必须将该进程回滚到某个安全状态,并从该状态重启进程.
   • 最简单的回滚方法是完全回滚(Total Rollback),即终止进程并重新执行.更有效的方法是回滚到足够打破死锁的那个状态.

3. 饥饿 (Starvation):

   • 如果总是选择同一个进程作为受害者(例如基于成本因素),那么该进程可能永远无法完成任务,导致饥饿.
   • 解决方案: 在成本因素中包含回滚次数.确保一个进程只能在有限的次数内被选为受害者.