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 管程介绍
一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
其组成分为以下四个部分：
- 管程名称
- 共享数据结构的说明
- 基于该数据结构的一组过程（操作）
- 对共享数据的初始化语句
Monitor monitor_name { // 管程名称
share variable declarations; // 共享变量说明
cond declarations; // 条件变量说明
public: // 能被进程调用的过程
void P1(...) {...}; // 对数据结构操作的过程
void P2(...) {...};
......
{ // 管程主体
initialization code; // 初始化代码
......
}
}
设置两个同步工具：
-
原语 wait
当某进程通过管程请求临界资源失败时，将其排在等待队列上。
-
原语 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，之后便没有哲学家能够进餐。
面对这样的问题，可以采用以下几种解决方法：
- 至多只允许 4 位哲学家同时拿左边的筷子
- 仅当哲学家的左右两只筷子都可以使用时，才拿起筷子进餐，否则不拿（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 进程通信的类型
-
共享存储器系统
相互通信的进程共享某些数据结构或共享存储区。
-
管道通信系统
管道：连接一个读进程和写进程的文件，用于实现它们之间通信的共享。又名 pipe 文件。
-
消息传递系统
不借助任何共享存储区或数据结构。而是以格式化的消息为单位，使用操作系统的通信命令在进程之间进行通信。其包括：
- 直接通信方式
- 间接通信方式
-
客户机-服务器系统
主要实现方法有三类：
- 套接字（Socket）：通信标识类型的数据结构。
- 远程过程调用（RPC）：一个通信协议。
- 远程方法调用：采用面向对象编程的 RPC。
2.7.2 消息传递通信的实现方式
（1）直接消息传递系统
-
直接通信原语
-
对称寻址方式
send(reveiver, message);发送一个消息给接收进程receiver(sender, message)接受 Sender 发来的消息 -
非对称寻址方式
send(P, message);发送一个消息给接收进程 Preceiver(id, message)接受来自任何进程的消息
-
-
消息的格式
- 定长消息格式：消息格式简单，减少消息的处理和存储开销
- 变长消息格式：更多开销，但是方便了用户
-
进程的同步方式
- 发送进程阻塞，接收进程阻塞
- 发送继承不阻塞，接收进程阻塞
- 发送进程和接收进程都不阻塞
-
通信链路
两种通信方式：
- 建立通信链路，用完后拆除
- 使用系统原语发送命令
（2）信箱通信
-
信箱的结构
信箱定义为一种数据结构，可以分为以下两个部分：
-
信箱头
用以存放有关信箱的描述信息，如信箱标识符、信箱的拥有者、信箱口令、信箱的空格数等。
-
信箱体
由若干个可以存放消息（或消息头）的信箱格组成，信箱格的数目以及每格的大小是在创建信箱时确定的。
-
-
信箱通信原语
- 创建
- 撤销
- 发送：
Send(mailbox, message) - 接收：
Receive(mailbox, message)
-
信箱的类型
- 私用邮箱
- 公用邮箱
- 共享邮箱
相关文章
- ESXI5-WIN2008R2安装域控以及额外域笔记
- Apollo星火计划学习笔记——Control 专项讲解(LQR)
- Dofbot机械臂从零部署笔记（5）——开发环境改造（Jetson Nano升级Ubuntu20.04，支持ROS Noetic、Python3）
- [计算机视觉][神经网络与深度学习]R-FCN、SSD、YOLO2、faster-rcnn和labelImg实验笔记
- 23 DesignPatterns学习笔记：C++语言实现 --- 1.3 Singletion
- 23 DesignPatterns学习笔记：C++语言实现 --- 1.2 AbstractFactory
- Spring学习笔记
- iOS学习笔记（十六）——数据库操作(使用FMDB)
- Angular 学习笔记 Material
- angular2 学习笔记 ( Http 请求)
- K8S持久化存储PV、PVC笔记
- redis cluster集群管理工具redis-trib.rb命令小结-运维笔记
- Python文件夹copy器（多进程版）学习笔记
- OpenCV人工智能图像处理学习笔记 第6章 计算机视觉加强之机器学习下 Hog_SVM小狮子识别
- 计算机视觉系列 -OpenMMLab 2.0系列直播 学习笔记
- 计算机视觉系列-AlexNet论文复现学习笔记（二）
- 计算机视觉系列-全球小麦检测Kaggle比赛学习笔记trick专题 （8）
- 2021-11-29 《计算机操作系统》（第四版）学习笔记：第七章
- 2021-10-17 《计算机操作系统》（第四版）学习笔记：第二章（3）
- 2021-09-23 《计算机操作系统》（第四版）学习笔记：第二章（1）
- 2021-09-07 《计算机操作系统》（第四版）学习笔记：第一章
- 计算机组成之进程管理学习笔记
- 《被讨厌的勇气》笔记
- Prometheus学习笔记（2）Prometheus部署
- 【PMP】Head First PMP 学习笔记 第三章 过程框架
- Linux 学习笔记（十）系统日志