操作系统 龚玲 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检黑子。规定每个进程每次只检一 子。当一个进程正在检子时，不允许另一进程 去检。当一进程检了一子后必须让另一进程去 检