2021-10-12 《计算机操作系统》（第四版）学习笔记：第二章（2）

2.4.3 信号量的应用

（1）实现进程互斥

​ 初始化互斥量 mutex 为 1：

semaphore mutex = 1;

PA() {
    while (true) {
        wait(mutex);
        临界区;
        signal(mutex);
        剩余区;
    }
}

PB() {
    while (true) {
        wait(mutex);
        临界区;
        signal(mutex);
        剩余区;
    }
}

（2）实现前趋关系

​ 设两个并发的进程分别为 P1 和 P2，S1 在 P1 中，S2 在 P2 中。

​ 我们希望语句 S2 在语句 S1 后执行，则设置一个公用信号量 S = 0：

P1() { S1; signal(S); }
P2() { wait(S); S2; }

​ 对于下面的前趋图，设置多个信号量实现其前趋关系：

pl() { S1; signal(a); signal(b);}
p2() { wait(a); S2; signal(c); signal(d); }
p3() { wait(b); S3; signal(e); }
p4() { wait(c); S4; signal(f); }
p5() { wait(d); S5; signal(g); }
p6() { wait(e); wait(f); wait(g); S6; }

main() {
    semaphore a, b, c, d, e, f, g;
    a.value = b.value = c.value = 0;
    d.value = e.value = 0;
    f.value = g.value = 0;
    cobegin
        p1(); p2(); p3(); p4(); p5(); p6();
    coend
}

2.5 管程机制

​ 虽然信号量机制是一种方便、有效的同步机制但是这为各个进程的管理带来了麻烦，信号量会大量分布在每个进程中。因此产生了一种新的进程同步工具——管程。

2.5.1 管程介绍

​ 一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

​ 其组成分为以下四个部分：

1. 管程名称
2. 共享数据结构的说明
3. 基于该数据结构的一组过程（操作）
4. 对共享数据的初始化语句

Monitor monitor_name {             // 管程名称
    share variable declarations;   // 共享变量说明
    cond declarations;             // 条件变量说明
public:                            // 能被进程调用的过程
    void P1(...) {...};            // 对数据结构操作的过程
    void P2(...) {...};
    ......
        
    {                              // 管程主体
        initialization code;       // 初始化代码
        ......
    }
}

​ 设置两个同步工具：

1. 原语 wait

   当某进程通过管程请求临界资源失败时，将其排在等待队列上。

2. 原语 signal

   当另一进程访问完成并释放该资源后，唤醒等待队列中的队首进程。

2.5.2 条件变量

​ 仅仅有上述的同步工具是不行的，考虑以下情况：

一个进程调用管程时被阻塞或者用户挂起，直到解除时，这一阶段中其他进程无法进入管程，被迫长时间等待。

​ 因此，设置（多个）条件变量 condition x, y。对这些条件变量的访问只能在管程中进行。

​ 每个条件变量也是一种抽象数据类型，具有一个用于记录因该条件变量而阻塞的所有进程。相应的，可以提供两个操作：

• x.wait
  • 调用原因：调用管程的进程因条件 x 而被阻塞或挂起。
  • 作用：将该进程插入到 x 的等待队列上，直到条件 x 发生变化之前，释放管程。
• x.signal
  • 调用原因：调用管程的进程发现条件 x 发生了变化。
  • 作用：选择 x 等待队列中进程的一个并启动

2.6 经典进程的同步问题 2.6.1 生产者-消费者问题

（1）记录型信号量解决问题

​ 设生产者和消费者之间的公用缓冲池有 n 个缓冲区。做出以下设置：

• 信号量 mutex：互斥信号量
• 信号量 empty：缓冲池中空缓冲区的数量
• 信号量 full：缓冲池中满缓冲区的数量

int in = 0, out = 0;                // 生产和消费的缓冲区 id
item buffer[n];                     // n 个缓冲区
semaphore mutex = 1, empty = n, full = 0;    // 初始化

void producer() {
    do {
        produce an item nextp;      // 生产
        ......
        wait(empty);                // 顺序检查 empty 和 mutex
        wait(mutex);                // 二者顺序不可以交换，否则会造成死锁
        buffer[in] = nextp;         // 将产品放入缓冲区
        in = (in + 1) % n;          // 移动到下一个生产位置
        signal(mutex);              // 释放 mutex 和 full
        signal(full);               // 二者顺序并无影响
    } while (true);
}

void consumer() {
    do {
        wait(full);                 // 顺序检查 full 和 mutex
        wait(mutex);                // 二者顺序不可以交换，否则也会导致死锁
        nextc = buffer[out];        // 获取产品
        out = (out + 1) % n;        // 移动到下一个获取位置
        signal(mutex);              // 释放 mutex 和 empty
        signal(empty);              // 二者顺序无影响
        consumer the item in nextc; // 进行消费
        ......
    } while (true);
}

void main() {
    cobegin
        producer(); consumer();
    coend
}

（2）AND 型信号量解决问题

​ 使用 Swait(empty, mutex) 代替 wait(empty) 和 wait(mutex)；

​ 使用 Ssignal(mutex, full) 代替 signal(mutex) 和 signal(full)；

​ 使用 Swait(full, mutex) 代替 wait(full) 和 wait(mutex)；

​ 使用 Ssignal(mutex, empty) 代替 signal(mutex) 和 signal(empty)；

​ 代码整体上差别不大。

int in = 0, out = 0;                // 生产和消费的缓冲区 id
item buffer[n];                     // n 个缓冲区
semaphore mutex = 1, empty = n, full = 0;    // 初始化

void producer() {
    do {
        produce an item nextp;      // 生产
        ......
        Swait(empty, mutex);        // 检查 empty 和 mutex
        buffer[in] = nextp;         // 将产品放入缓冲区
        in = (in + 1) % n;          // 移动到下一个生产位置
        Ssignal(mutex, full);       // 释放 mutex 和 full
    } while (true);
}

void consumer() {
    do {
        Swait(full, mutex);         // 检查 full 和 mutex
        nextc = buffer[out];        // 获取产品
        out = (out + 1) % n;        // 移动到下一个获取位置
        signal(mutex);              // 释放 mutex 和 empty
        Ssignal(mutex, empty);       // 释放 mutex 和 empty
        ......
    } while (true);
}

void main() {
    cobegin
        producer(); consumer();
    coend
}

​ 采用 AND 型信号量可以解决记录型信号量有关顺序的死锁问题：因为 AND 型信号量不同时满足条件则都不会占用资源。但是也正是因如此，可能导致资源使用过程中的浪费，利用率低。

2.6.2 哲学家进餐问题

​ 哲学家进餐问题：

​ 五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，圆桌上只有 5 个碗和 5 只筷子。平时，哲学家进行思考，饥饿时试图取用其左右最靠近的两只筷子，只有拿到两只筷子时才会进餐，进餐后才会放下筷子继续思考。

（1）记录型信号量解决问题

​ 采用信号量数组的方式：semaphore chopstick[5] = {1, 1, 1, 1, 1};

semaphore chopstick[5] = {1, 1, 1, 1, 1};

do {
    wait(chopstick[i]);
    wait(chopstick[(i + 1) % 5]);
    ...
    // eat
    ...
    signal(chopstick[i]);
    signal(chopstick[(i + 1) % 5]);
    ...
    // think
    ...
} while (true);

​ 上述解法可以保证不会有相邻的两个哲学家同时进餐，但是发生下述情况时，有可能引起死锁：

五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量 chopstick 均为 0，之后便没有哲学家能够进餐。

​ 面对这样的问题，可以采用以下几种解决方法：

1. 至多只允许 4 位哲学家同时拿左边的筷子
2. 仅当哲学家的左右两只筷子都可以使用时，才拿起筷子进餐，否则不拿（AND 型信号量原理）

（2）AND 型信号量解决问题

​ 要求每个哲学家先获得两个临界资源（筷子）后才进餐。

semaphore chopstick[5] = {1, 1, 1, 1, 1};

do {
    Swait(chopstick[(i + 1) % 5], chopstick[i]);
    ...
    // eat
    ...
    Ssignal(chopstick[(i + 1) % 5], chopstick[i]);
    ...
    // think
    ...
} while (true);

2.6.3 读者-写者问题

• 允许多个进程同时读一个共享对象，因为读操作不会使文件混乱
• 不允许一个 Writer 进程和其他 Reader 进程或 Writer 进程同时访问共享对象

（1）记录型信号量解决问题

• 信号量 Wmutex：Writer 进程的互斥信号量
• 整型变量 Readcount：正在读的进程数目
• 信号量 Rmutex：Reader 进程的互斥信号量

semaphore rmutex = 1, wmutex = 1;
int readcount = 0;

void reader() {
    do {
        // rmutex 封装，使得访问互斥
        wait(rmutex);
        if (readcount == 0) wait(wmutex);    // 准备进入读操作，关闭写操作入口，占用 wmutex
        readcount++;                         // 更新 Reader 数目
        signal(rmutex);
        
        ...
        perform read operation               // 读操作
        ...
            
        // rmutex 封装，使得访问互斥
        wait(rmutex);
        readcount--;                         // 先更新 Reader 数目
        if (readcount == 0) signal(wmutex);  // 如果没有 Reader 在读，打开写操作入口，释放 wmutex
        signal(rmutex);
    } while (true);
}

void writer() {
    do {
        wait(wmutex);                        // 占用 wmutex，不允许其他写操作进行
        
        perform write operation              // 写操作
            
        signal(wmutex);                      // 释放 wmutex
    } while (true);
}

void main() {
    cobegin
        reader(); writer();
    coend
}

​ 这种实现方式的特点是读者优先，即有读者正在读时，写者不能访问资源，但是其他读者仍可以读。

（2）信号量集解决问题

• RN：最多允许同时读的读者数
• L：表示最多还能允许读者数的信号量
• mx：读者和写者之间的互斥信号量

int RN;
semaphore L = RN, mx = 1;

void reader() {
    do {
        Swait(L, 1, 1);             // 剩余读者数减 1，若剩余读者数 < 1，不允许读
        Swait(mx, 1, 0);            // 如果 mx 没有被占用，才允许读
        
        ...
        perform read operation      // 读操作
        ...
            
        Ssignal(L, 1);              // 释放一个读者
    } while (true);
}

void writer() {
    do {
        Swait(mx, 1, 1, L, RN, 0);  // mx 没有被占用并且读者数为 RN 时，才允许写
        
        perform write operation     // 写操作
            
        Ssignal(mx, 1);             // 释放 mx
    } while (true);
}

void main() {
    cobegin
        reader(); writer();
    coend
}

​ wait(L, 1, 1) 控制读者的数目，每当有一个读者进入时，就要先执行 wait(L, 1, 1)操作，使 L 的值减 1。当有 RN 个读者进入读后，L 便减为 0，第 RN＋1 个读者要进入读时，会因 wait(L, 1, 1) 操作失败而阻塞。对利用信号量集来解决读者-写者问题的描述如下：

​ Swait(mx, 1, O) 语句起着开关的作用。只要无 writer 进程进入写操作，mx = 1，reader 进程就都可以进入读操作。但只要一旦有 writer 进程进入写操作时，其 mx = 0，则任何 reader 进程就都无法进入读操作。

​ Swait(mx, 1, 1, L, RN, O) 语句表示仅当既无 writer 进程在写操作（mx = 1）、又无 reader 进程在读操作（L = RN）时，writer 进程才能进入临界区进行写操作。

2.7 进程通信 2.7.1 进程通信的类型

1. 共享存储器系统

   相互通信的进程共享某些数据结构或共享存储区。

2. 管道通信系统

   管道：连接一个读进程和写进程的文件，用于实现它们之间通信的共享。又名 pipe 文件。

3. 消息传递系统

   不借助任何共享存储区或数据结构。而是以格式化的消息为单位，使用操作系统的通信命令在进程之间进行通信。其包括：

   • 直接通信方式
   • 间接通信方式

4. 客户机-服务器系统

   主要实现方法有三类：

   • 套接字（Socket）：通信标识类型的数据结构。
   • 远程过程调用（RPC）：一个通信协议。
   • 远程方法调用：采用面向对象编程的 RPC。

2.7.2 消息传递通信的实现方式

（1）直接消息传递系统

1. 直接通信原语

   • 对称寻址方式

     send(reveiver, message);发送一个消息给接收进程

     receiver(sender, message)接受 Sender 发来的消息

   • 非对称寻址方式

     send(P, message);发送一个消息给接收进程 P

     receiver(id, message)接受来自任何进程的消息

2. 消息的格式

   • 定长消息格式：消息格式简单，减少消息的处理和存储开销
   • 变长消息格式：更多开销，但是方便了用户

3. 进程的同步方式

   • 发送进程阻塞，接收进程阻塞
   • 发送继承不阻塞，接收进程阻塞
   • 发送进程和接收进程都不阻塞

4. 通信链路

   两种通信方式：

   • 建立通信链路，用完后拆除
   • 使用系统原语发送命令

（2）信箱通信

1. 信箱的结构

   信箱定义为一种数据结构，可以分为以下两个部分：

   • 信箱头

     用以存放有关信箱的描述信息，如信箱标识符、信箱的拥有者、信箱口令、信箱的空格数等。

   • 信箱体

     由若干个可以存放消息（或消息头）的信箱格组成，信箱格的数目以及每格的大小是在创建信箱时确定的。

2. 信箱通信原语

   • 创建
   • 撤销
   • 发送：Send(mailbox, message)
   • 接收：Receive(mailbox, message)

3. 信箱的类型

   • 私用邮箱
   • 公用邮箱
   • 共享邮箱