2020年2018级操作系统-信号量习题分析-v21

四. (15 points) An assembly line is to produce a product C with four part As, and three part Bs.

The worker of machining(加工) A and worker of machining B will produce two part As and one

part B independently each time. Then the two part As or one part B will be moved to the

station(工作台), which can hold at most 12 of part As and part Bs altogether. Two part As must

be put onto the station simultaneously. The workers must exclusively put a part on the station or

get it from the station. In addition, the worker to make C must get all part of As and Bs for one

product once.

Using semaphores to coordinate the three workers who are machining part A, part B and the

product C to manufacture the product without deadlock.

（1） worker A 生产出的 part A 后，必须一次性将 2 个 part A 同时放入工作台，此时工作

台上至少应有 2 个空位。

说明：

根据此要求，只有当工作台上至少有 2 个空位时，worker A 才能通过信号量操作进入

临界区，一次性向工作台放入 2 个 part A。不允许 worker A 两次进入临界区，每次向工作台

放入 1 个 part A，这样做有可能导致死锁，或阻塞 worker B 的操作。

例如，假设以多元信号量 empty 表示工作台中的空位数目。当前工作台中已有 6 个 part

A、5 个 part B，剩余空位数为 empty=12-(6+5)=1。此时应允许 work B 生产 1 个 part B，并放

入这剩余的 1 个空位中，但不允许 work A 将其生产的 2 个 part A 同时放入工作台。

考虑下述情况，work C 完全休眠，只有 work A、work B 采用分时方式，轮流占用 CPU

由于 worker A 先执行 wait 操作，占用了剩余的 1 个空位，但又无法同时生产 2 个 part A

并放入工作台，从而导致 worker B 也无法进入临界区并向工作台放入一个 part B。worker

A、worker B 均阻塞在信号量 empty 上。