补充题

第三章作业

详见教材第3章习题3-7、3-8、3-9、3-14、3-15、3-16、3-17、3-18、3-19、3-20、3-21。

3-7.

设系统有n+1个进程，其中有n个发送进程和1个接收进程。其中A1、A2、…、An通过一个单缓冲区分别不断地向进程B发送消息，B不断地取走缓冲区中的消息，而且必须取走发来的每一个消息。刚开始时，缓冲区为空。试用P、V操作正确实现进程之间的同步。

生产者和消费者问题

初始值：

empty = 1
full  = 0
mutex = 1

每个发送进程 Ai（循环发送消息）的 P、V 操作：

while (true) {
produce m           // 产生要发送的消息 m（在本进程私有空间）
P(empty)            // 等待有空槽
P(mutex)            // 进入临界区，独占访问缓冲区
  buffer = m      // 把消息放入缓冲区（覆盖之前的内容，但由于 empty/full 保证不会丢弃）
V(mutex)            // 退出临界区
V(full)             // 缓冲区中有消息，可唤醒接收者
}

接收进程 B（不断取走并处理消息）的 P、V 操作：

while (true) {
P(full)             // 等待有消息
P(mutex)            // 进入临界区，独占访问缓冲区
  m = buffer      // 取走缓冲区中的消息
V(mutex)            // 退出临界区
V(empty)            // 释放空槽，唤醒某个发送者
consume m           // 处理消息 m
}

3-8.

有一容量为100的循环缓冲区，有多个并发执行进程通过该缓冲区进行通信。为正确管理缓冲区，系统设置了两个读写指针，分别为OUT和IN。IN和OUT的值如何反应缓冲区为空还是满的情况？

环形队列

初始值 IN 和 OUT 都为0

缓冲区空：IN == OUT

缓冲区满：(IN + 1) % 100 == OUT

3-9.

有一阅览室，共有100个座位。为了很好利用它，读者进入时必须先在登记表上进行登记，该表表目设有座位号和读者姓名，离开时再将其登记项擦除。试问： (1) 为描述读者的动作，应编写几个程序？应设几个进程？它们之间的关系是什么？

一个读者程序，因为所有读者的行为逻辑是一样的。

多个读者进程，每个进程代表一个读者

关系：

读者之间是并发关系；

需要对共享资源（登记表与座位数）进行互斥访问；

不同读者之间不存在直接通信，只通过共享资源（登记表、座位）间接交互。

(2) 试用P、V操作描述读者之间的同步算法。

设两个信号量：

empty=100 资源信号量，表示可用座位数
mutex=1 互斥信号量，确保进程互斥

process Reader
{
    P(empty);              // 申请一个座位
    P(mutex);             // 申请登记
        登记(姓名, 座位号);
    V(mutex);
    	阅读();
    P(mutex);             // 离开时申请擦除登记
        擦除登记项();
    V(mutex);
    V(empty);              // 释放一个座位
}

3-14.

假定系统有N个进程共享M个同类资源，规定每个进程至少申请一个资源，每个进程的最大需求不超过M，所有进程的需求总和小于M+N。为什么在这种情况下也绝不会发生死锁？试证明。

如果会发生死锁，会有N个进程占满了总共M个资源，并且每个进程至少还需要一个资源，也就是>=N

所以需求总和需要大于等于N+M。和题中的“需求总和小于M+N”不符，所以这种情况是永远不会死锁的。

3-15.

设有8个进程M1、M2、…、M8，它们有如图所示的优先关系，试用P、V操作实现这些进程间的同步。

对每条边创建信号量，初值为0，表示不能运行

s_1_2 = 0; s_1_3 = 0; s_1_4 = 0; s_2_6 = 0; s_3_6 = 0; s_3_8 = 0; s_4_7 = 0; s_5_7 = 0; s_7_8 = 0;

Process M1:
    // M1 无前驱，可直接执行
    do M1_work;
    V(s_1_2); V(s_1_3); V(s_1_4);

Process M2:
    P(s_1_2);           // 等待 M1 完成
    do M2_work;
    V(s_2_6);

Process M3:
    P(s_1_3);           // 等待 M1 完成
    do M3_work;
    V(s_3_6); V(s_3_8);

Process M4:
    P(s_1_4);           // 等待 M1 完成
    do M4_work;
    V(s_4_7);

Process M5:
    // M5 无前驱，可直接执行
    do M5_work;
    V(s_5_7);

Process M6:
    P(s_2_6); P(s_3_6); // 等待 M2 和 M3 都完成
    do M6_work;
    // 无后继信号量

Process M7:
    P(s_4_7); P(s_5_7); // 等待 M4 和 M5 都完成
    do M7_work;
    V(s_7_8);

Process M8:
    P(s_3_8); P(s_7_8); // 等待 M3 和 M7 都完成
    do M8_work;
    // 无后继信号量

3-16.

设有5个哲学家，共享一张放有5把椅子的圆桌。每人分得1把椅子。但是，桌子上总共只有5把叉子。哲学家们在肚子饥饿时才试图分两次从两边捡起2把叉子就餐。条件：

a. 每人只有拿到2把叉子时，哲学家才能吃饭；

b. 如果叉子已在他人手上，则该哲学家必须等到他人吃完之后才能拿到叉子。

c. 任性的哲学家在自己未拿到2把叉子吃饭之前，绝不放下自己手中的叉子。

试问：

(1) 什么情况下5个哲学家全部吃不上饭？

发生死锁的状态：

5个哲学家手上都有一把叉子，比如每个哲学家都拿到了左手边的叉子，并在等待右手边的叉子

(2) 描述一种避免有人饿死（永远拿不到2个叉子）的算法。

奇偶分配，奇数位的哲学家先拿左手边的叉子，后拿右手边的叉子；偶数位的哲学家先拿右手边的叉子，在拿左手边的叉子。

避免所有哲学家都拿同一侧的叉子导致死锁。

3-17.

在本章前面的读者与写者问题中，是用读者优先解决问题的。试分别用读者与写者公平竞争（无写者时，读者仍遵循多个读者可以同时读）、写者优先的算法解决这个问题。

读者优先

如果源源不断有读者进入，写者会一直等，可能“饿死”。

信号量：

mutex：控制对共享资源的互斥访问（初始化为1）。
write_mutex：控制写者的互斥访问（初始化为1）。
read_count：记录当前读者的数量（初始化为0）。
write_queue：用于等待的写者队列。

读者进程

P(mutex);                   // 进入临界区
read_count++;                // 增加读者计数
if (read_count == 1)         // 如果是第一个读者，阻止写者进入
    P(write_mutex);          // 阻止写者进入
V(mutex);                    // 退出临界区

// 执行读操作
read();                      // 执行读操作

P(mutex);                    // 进入临界区
read_count--;                 // 减少读者计数
if (read_count == 0)          // 如果是最后一个读者，释放写者
    V(write_mutex);           // 允许写者进入
V(mutex);                     // 退出临界区

写者进程

P(write_mutex);               // 获取写锁
// 执行写操作
write();                       // 执行写操作
V(write_mutex);                // 释放写锁

公平竞争

rmutex互斥共享readcount; rwmutex读写互斥，写写互斥；读写进程在z上排队。

信号量：

rwmutex = 1; // 控制资源访问 rmutex = 1; // 保护 readcount readcount = 0;

队列：z[]

读者进程：
c
P(queue);                // 进入等待队列（公平）
P(mutex);
readcount++;
if (readcount == 1)
   P(rw);               // 第一个读者锁住资源
V(mutex);
V(queue);                // 允许下一个进程排队

【读操作】

P(mutex);
readcount--;
if (readcount == 0)
   V(rw);
V(mutex);
写者进程：
c
P(queue);                // 按顺序进入
P(rw);                   // 独占资源
// 写操作
V(rw);
V(queue);

写者优先

信号量：

semaphore rw = 1;          // 控制资源访问
semaphore mutex = 1;       // 保护 readcount
semaphore wmutex = 1;      // 控制写者队列
semaphore rmutex = 1;      // 控制读者进入
int readcount = 0;

读者进程

P(rmutex);                 // 检查是否允许读（若有写者等候则阻塞）
P(mutex);
readcount++;
if (readcount == 1)
    P(rw);                 // 第一个读者锁资源
V(mutex);
V(rmutex);

//【读操作】

P(mutex);
readcount--;
if (readcount == 0)
    V(rw);                 // 最后一个读者释放资源
V(mutex);

写者进程

while(1){
    P(wmutex);                 // 写者队列互斥
    P(rmutex);                 // 阻止新读者进入
    P(rw);                     // 独占资源
    //【写操作】
    V(rw);
    V(rmutex);                 // 允许读者进入
    V(wmutex);
}

3-18.

有一个理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便坐在椅子上睡觉，但一个顾客到来时，必须唤醒理发师，请求理发；如果理发师正在理发时，又有顾客到来，只要有空椅子，他就坐下来等待，如果没有空椅子，他就离开。请为理发师和顾客各编写一段程序来描述他们的同步过程。

信号量：

semaphore customers = 0;   // 等待的顾客数
semaphore barbers = 0;     // 理发师可服务信号
semaphore mutex = 1;       // 互斥锁
int waiting = 0;           // 等待中的顾客数

理发师进程

while(true){  // 一个理发师服务多个客人，所以要循环
    P(customers);  // 等待顾客，没有就睡觉
    P(mutex);
    waiting--;        // 顾客减少
    V(barbers);       // 理发师准备好，通知顾客
    V(mutex);
    // 理发
}

顾客进程

P(mutex);  // 准备理发
if(waiting < n){  // 有空位
    waiting++;
    V(customers);     // 通知理发师
    V(mutex);
    P(barbers);       // 等理发师准备好
    // 理发
}
else{
    V(mutex);  // 没位置，离开
    离开理发店
}

3-19.

假定系统中只有一类资源，进程一次只申请一个单位的资源，且进程申请的资源数不会超过系统拥有的资源总数。假定进程申请的资源总数为2，且系统资源总数如下，问下列哪些情况会发生死锁？

序号	进程数	系统资源总数
(1)	1	2
(2)	2	2
(3)	2	3
(4)	3	3
(5)	3	5
(6)	4	5

2,4 会发生死锁

3-20.

系统有同类资源10个，进程P1、P2和P3需要该类资源的最大数量分别为8、6、7。它们使用资源的次序和数量如下表所示。

次序	进程	申请量
1	P1	3
2	P2	2
3	P3	4
4	P1	2
5	P2	2
6	P1	3
7	P3	3
8	P2	2

(1) 试给出采用银行家算法分配资源时，进行第5次分配后各进程的状态及各进程占用资源情况。

次序	进程申请	当前分配/所需资源	剩余资源
0	-	P1=0/8, P2=0/6, P3=0/7	10
1	P1申请3	P1=3/5, P2=0/6, P3=0/7	7
2	P2申请2	P1=3/5, P2=2/4, P3=0/7	5
3	P3申请4	5-4 = 1,而剩下进程所需资源都大于1，所以不安全，P3阻塞	5
4	P1申请2	P1=5/3, P2=2/4, P3=0/7（安全）	3
5	P2申请2	3-2 = 1,而剩下进程所需资源都大于1，所以不安全，P2阻塞	3
6	P1申请3	P1=（5+3）/0, P2=2/4, P3=0/7（安全）	0 -> 8（P1进程结束）
7	P3申请3
8	P2申请2

剩余资源 = 3 分配情况：P1=5（运行）, P2=2（阻塞）, P3=0（阻塞）

(2) 在以后的申请中，哪次的申请可以得到最先满足？给出一个进程完成序列。

根据第一题中的表格，可以看到P1是先完成分配的,然后回到次序2,4

完成序列为：P1,P2,P3

3-21.

考虑某一系统，它有4类资源R1、R2、R3、R4，有5个并发进程P0、P1、P2、P3、P4。请按照银行家算法回答下列问题：

(1) 各进程的最大资源请求和已分配的资源矩阵及系统当前的剩余资源向量如下图所示，计算各进程的剩余资源请求向量组成的矩阵。

Max=

> \begin{matrix} > 0 & 0 & 1&2 \\ > 1 & 7 & 5&0 \\ > 2 & 3 & 5&6\\ > 0&6&5&2\\ > 0&6&5&6 > \end{matrix} \tag{1} >

Allocation=

>\begin{matrix} > 0 & 0 & 1&2 \\ > 1 &0 & 0&0 \\ > 1 & 3 & 5&4\\ > 0&6&3&2\\ > 0&0&1&4 > \end{matrix} \tag{1} >

Need=

>\begin{matrix} > 0 & 0 & 0&0 \\ > 0 & 7 & 5&0 \\ > 1 & 0 & 0&2\\ > 0&0&2&0\\ > 0&6&4&2 > \end{matrix} \tag{1} >

Available=（1,5,0,2）

(2) 系统当前处于安全状态吗？当进程P2申请的资源分别为(1,0,0,1)时，系统能立即满足吗？

当前Available =（1,5,0,2）

P0完成后，Available =（1,5,1,4），可以让P2完成。

P2完成后，Available =（2,8,6,8）剩余资源数可以让剩下所有的进程都完成，所以系统是安全的。

Available =（1,5,0,2）

当进程P2申请的资源分别为(1,0,0,1)时，（1,5,0,2）> (1,0,0,1)

可以满足

某寺庙中有若干个老和尚和小和尚，并有一个水缸能储存10桶水，小和尚每天从寺庙的水井中打水入缸供老和尚饮用。寺庙中有3个水桶，小和尚从井中打水时，由于水井口窄，每次只能使用1个水桶；每次打水入缸和从缸中取水仅为1桶，且不可同时进行。试给出小和尚从井中打水和老和尚从缸中取水的算法描述。

有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件（0<x<M），B的信箱中有y个邮件（0<y<N）。辩论者每取出一个邮件，邮件数减1。A和B两人的操作过程描述如下：CoBegin

A{
   while(TRUE) {
      从A的信箱中取出一个邮件；
      回答问题并提出一个新问题；
      将新邮件放入B的信箱；
   }
}

B{
  while(TRUE) {
   从B的信箱中取出一个邮件；
   回答问题并提出一个新问题；
   将新邮件放入A的信箱；
  }
}

在消息传递方式下，

(1) 发送进程和接收进程在通信过程中可以采取哪3种同步方式？

(2) 试以下面给出的发送进程和接收进程（将接收到的数据存入S）为例，说明当接收进程执行到标号为L2的语句时，采用这3种同步方式，X的值可能各是多少？

发送进程P
    M=10;
    L1:   send M to Q;
    L2:   M=20;
    Goto L1;

接收进程Q
    S=-100;
    L1:   receive S from P;
    L2:   X=S+1;

进程资源的使用情况和可用情况如下表所示，

(1) 请画出资源分配图；

(2) 该资源分配图是否可以简化？若可以，请给出简化步骤。

(3) 在上表所示情况下系统会发生死锁吗？

第六章作业 →操作系统 →第四章作业 →

第三章作业

3-7.

3-8.

3-9.

3-14.

3-15.

3-16.

3-17.

读者优先

公平竞争

写者优先

3-18.

3-19.

3-20.

3-21.

补充题

相关文章