上海交通大学：《操作系统 Operating System》课程教学资源（课件讲稿）OS-semaphore EXERCISES

操作系统 龚玲 Igong@sjtu.edu.cn 1

1 操作系统 龚玲 lgong@sjtu.edu.cn

Semaphores A semaphore s is a nonnegative integer acquire and release operate on s Semantics: release(s):increment s by 1 acquire (s):if s>0,decrement s;else wait until s>0 The waiting can be implemented by Blocking the process,or Busy-waiting (see Chapter 4) acquire and release are indivisible operations (atomic) 2

2 Semaphores  A semaphore s is a nonnegative integer  acquire and release operate on s  Semantics: release(s): increment s by 1 acquire(s): if s>0, decrement s; else wait until s>0  The waiting can be implemented by  Blocking the process, or  Busy-waiting (see Chapter 4)  acquire and release are indivisible operations (atomic)

Dijkstra's Semaphores A Semaphore is a non-negative integer,s (how many tasks can proceed simultaneously),and two indivisible operations: P(s),often written wait(s);think"Pause": cP'from“passaren'(pass"in Dutch)or from“prolagan,” combining "proberen"("try")and "verlagen"("decrease"). ■whi1e（s<1)/*wait*/;s=s-1 v(s),often written signal(s); think of the "V for Victory"2-finger salute: V'from“vrigeven'(release)or“verhogen”(increase") ■s=s+1； 3

3 Dijkstra’s Semaphores A Semaphore is a non-negative integer, s (how many tasks can proceed simultaneously), and two indivisible operations:  P(s), often written Wait(s); think “Pause”: “P” from “passaren” (“pass” in Dutch) or from “prolagan, ” combining “proberen” (“try”) and “verlagen” (“decrease”).  while (s<1)/*wait*/; s=s-1  V(s), often written Signal(s); think of the “V for Victory” 2-finger salute: “V” from “vrigeven” (“release”) or “verhogen” (“increase”).  s=s+1;

Mutual Exclusion with Semaphores semaphore mutex 1; cobegin i pi:while (1){ P(mutex);cSi;V(mutex) programi; 11 coend 4

4 Mutual Exclusion with Semaphores semaphore mutex = 1; cobegin ... // pi: while (1) { P(mutex); CSi; V(mutex); programi; } // ... coend;

Cooperation with Semaphores semaphore s =0; cobegin p1: 。。。 P(s);/*wait for signal * // p2: (s);/*send signal * .. coend 5

5 Cooperation with Semaphores semaphore s = 0; cobegin p1: ... P(s); /* wait for signal */ ... // p2: ... V(s); /* send signal */ ... ... coend;

条单向行驶的公路上有一座桥，该桥只允 许一辆汽车在桥上行驶，当桥上有汽车时，其 它汽车不能上桥。 (There is a bridge on a one-way road.Only one car is allowed to drive on the bridge at a time.If there is a car on the bridge,other cars are not allowed to go through the bridge.) 互斥还是同步？(mutex or cooperation?) 信号量及初值？(semaphore and the initial value?) 实现过程？ 6

6 练习：  在一条单向行驶的公路上有一座桥，该桥只允 许一辆汽车在桥上行驶，当桥上有汽车时，其 它汽车不能上桥。  (There is a bridge on a one-way road. Only one car is allowed to drive on the bridge at a time. If there is a car on the bridge, other cars are not allowed to go through the bridge.)  互斥还是同步？(mutex or cooperation?)  信号量及初值？(semaphore and the initial value?)  实现过程?

■互斥问题 ■S=1 汽车进程pi(i=0,1,2,…) acquire(s) 汽车上桥 汽车下桥 release(s) 7

7  互斥问题  s=1  汽车进程pi (i=0,1,2,…) acquire(s) 汽车上桥 汽车下桥 release(s)

在某地有一售票厅，可容纳20人。当厅内不足 20人时，购票者可进入该厅，当厅内已有20 人时，购票者需在厅外等候，当有厅内购票者 退出时方可进入。 A ticket hall can hold 20 persons . 8

8  在某地有一售票厅，可容纳20人。当厅内不足 20人时，购票者可进入该厅，当厅内已有20 人时，购票者需在厅外等候，当有厅内购票者 退出时方可进入。  ( A ticket hall can hold 20 persons .)

■互斥问题 ■S=20 ■购票者进程pi(=0,1,2,.…) acquire(s) 进入售票厅 购票 退出售票厅 release(s) 9

9  互斥问题  s=20  购票者进程pi (i=0,1,2,…) acquire(s) 进入售票厅 购票 退出售票厅 release(s)

在一个盒子里，混装了数量相等的围棋白子和 黑子。现在要用自动分检系统把白子和黑子分 开。该系统设有两个进程p1和p2,其中p1检 白子，p2检黑子。规定每个进程每次只检一 子。当一个进程正在检子时，不允许另一进程 去检。当一进程检了一子后必须让另一进程去 检。 10

10  在一个盒子里，混装了数量相等的围棋白子和 黑子。现在要用自动分检系统把白子和黑子分 开。该系统设有两个进程p1和p2，其中p1检 白子，p2检黑子。规定每个进程每次只检一 子。当一个进程正在检子时，不允许另一进程 去检。当一进程检了一子后必须让另一进程去 检