第六周作业

1. 同步&互斥

同步： 合作者进程在执行次序上的协调关系称为同步关系。具体体现为一个进程到达关键点后，在尚未得到伙伴进程发来的消息或信号前应阻塞自己，等待消息或信号到达再被唤醒并继续执行。

互斥： 进程异步并发，但不能同时必须相互排斥地进入临界区。 2. (中山大学)CR& CS

CR 临界资源 一次（一段时间内）只能由一个进程使用的资源； CS 临界区 进程的程序文本中访问临界资源的代码段。 3. (复旦大学)请阐述对于互斥临界区的管理要求

答： 进程异步并发，不能同时且必须相互排斥进入临界区。保证一个进程在临界区执行时，不让另一个进程进入临界区，应让其等待，避免发生与时间有关的错误。进入临界区的进程必须在有限的时间内退出，以便让等待队列中的一个进程进入。 同步机构设计准则：

空闲让进 忙则等待 有限等待 让权等待 4. (中山大学)试述信号量及其值的物理含义。

信号量是联系和控制CR的数据结构。当信号量S之值大于0时，s.value表示CR的可用数目；当S之值等于0时，s.value表示无空闲CR，也无阻塞进程；当S之值小于0时， |s.value|表示因CR而阻塞的进程数。

5. （南航）试从物理概念上来说明记录型信号量的wait与signal操作。

Wait： 在一个原语中，将进入CS同时需要的多种临界资源，要么全部分配给它，要么一个都不分配，称为Swait，即同时wait操作或AND同步。

Signal： 用于同时需要多种临界资源、每种所需数目不同、且可分配的资源还存在一个安全临界值时的处理。 答案（网上）：

Wait(S)：当S.value>0时，表示目前系统中这类资源还有可用的，执行一次wait操作，意味着进程请求一个单位的该类资源，是系统中可供分配的该类资源减少一个，因此描述为S.value:=S.value-1；当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。

Signal(S)：执行一次signal操作，意味着释放一个单位的可用资源，使系统中可供分配的该类资源数增加一个，故执行S.value:=S.value+1操作。若加1后S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，因此应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。

6.(上海交大)请用信号量实现4*100（4人，每人100米）接力赛的同步过程。 解答：

P1 P2 P3 P4 S1 S2 S3

P1、P2、P3和P4分别代表四位运动员，他们的跑步顺序受其位置的限制。从上图表示可以看出，此题相当于是用信号量描述前趋关系。 S1、S2、S3、S4的初值均为0。 P1：起跑——>前进100米——>V(S1)

P2：P(S1)——>起跑——>前进100米——>V(S2) P3：P(S2)——>起跑——>前进100米——>V(S3) P4：P(S3)——>起跑——>前进100米——>到达终点

6. 在测量控制系统中的数据采集任务时，把所采集的数据送往一单缓冲区；计算任务从该缓冲

区中取出数据进行计算。试写出利用信号量机制实现两任务共享单缓冲区的同步算法。

a. Var mutex, empty, full: semaphore:=1, 1, 0;

gather: gather data in next p; begin

repeat …

signal(mutex); signal(full); until false;

end compute: begin repeat …

8. （哈尔滨工业大学）有一阅览室，共有100个座位。读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座位号和读者姓名。读者离开时要注销掉登记内容。试用某一种语言（或类语言）和P、V操作描述读者进程的同步结构。