Chapter 7: Process Synchronization 进程同步

Presentation on theme: "Chapter 7: Process Synchronization 进程同步"— Presentation transcript:

1 Chapter 7: Process Synchronization 进程同步
7.1 Background 背景 7.2 The Critical-Section Problem 临界区问题 7.3 Synchronization Hardware 同步的硬件实现 7.4 Semaphores 信号量 7.5 Classical Problems of Synchronization 经典同步问题 7.6 Critical Regions 临界区 7.7 Monitors 管程 7.8 OS Synchronization 操作系统的同步机制 7.9 Atomic Transactions 原子事务处理 Operating System Concepts

2 7.1 Background 背景 Concurrent access to shared data may result in data inconsistency. 对共享数据的并发访问可能导致数据的不一致性 Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes. 要保持数据的一致性，就需要一种保证并发进程的正确执行顺序的机制 Operating System Concepts

3 Background (Cont.) Shared-memory solution to bounded-butter problem (Chapter 4) allows at most n – 1 items in buffer at the same time. A solution, where all N buffers are used is not simple. 第4章中解决有限缓冲区问题的共享内存方法…N项的缓冲器最多只能使用n-1项 Suppose that we modify the producer-consumer code by adding a variable counter, initialized to 0 and incremented each time a new item is added to the buffer 假定我们通过增加一个计数器变量修改生产者-消费者代码，初始值为 0，在缓冲区增加一个项目（数据）计数器加1 Operating System Concepts

4 Bounded-Buffer 有界缓冲区 Shared data #define BUFFER_SIZE 10
typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0; Operating System Concepts

5 Bounded-Buffer (Cont.-1)
Producer process item nextProduced; while (1) { while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; } Operating System Concepts

6 Bounded-Buffer (Cont.-2)
Consumer process item nextConsumed; while (1) { while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; } Operating System Concepts

7 Bounded Buffer (Cont.-3)
The statements counter++; counter--; must be performed atomically. Atomic operation means an operation that completes in its entirety without interruption. Operating System Concepts

8 Bounded Buffer (Cont.-4)
The statement “count++” may be implemented in machine language as: register1 = counter register1 = register1 + 1 counter = register1 The statement “count—” may be implemented as: register2 = counter register2 = register2 – 1 counter = register2 Operating System Concepts

9 Bounded Buffer (Cont.-5)
If both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved. 如果生产者和消费者并发地更新缓冲区,汇编语言语句可以得到的交替存取 Interleaving depends upon how the producer and consumer processes are scheduled. 交替取决于生产者和消费者进程如何调度 Operating System Concepts

10 Bounded Buffer (Cont.-6)
Assume counter is initially 5. One interleaving of statements is: producer: register1 = counter (register1 = 5) producer: register1 = register1 + 1 (register1 = 6) consumer: register2 = counter (register2 = 5) consumer: register2 = register2 – 1 (register2 = 4) producer: counter = register1 (counter = 6) consumer: counter = register2 (counter = 4) The value of count may be either 4 or 6, where the correct result should be 5. Operating System Concepts

11 Race Condition竞争条件 Race condition: The situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. Outcome of execution depends on the particular order in which the access takes place. 竞争条件：若干进程并发地访问并且操纵共享数据的情况。 共享数据的值取决于哪个进程最后完成 To prevent race conditions, concurrent processes must be synchronized. 防止竞争条件，并发进程必须被同步 Operating System Concepts

12 7.2 The Critical-Section Problem 临界区问题
n processes all competing to use some shared data 所有n 个进程竞争使用一些共享的数据。 Each process has a code segment, called critical section, in which the shared data is accessed. 每个进程有一个代码段, 称为临界区, 在那儿共享数据被访问. 临界区：访问临界资源的那段代码 Problem – ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section. 问题- 保证当一个进程正在临界区执行时，没有另外的进程进入临界区执行 多个进程共享临界资源时必须互斥使用 Operating System Concepts

13 临界资源 多道程序环境－>进程之间存在资源共享，进程的运行时间受影响
硬件或软件（如外设、共享代码段、共享数据结构），多个进程在对其进行访问时（关键是进行写入或修改），必须互斥地进行－－有些共享资源可以同时访问，如只读数据 进程间资源访问冲突 共享变量的修改冲突 操作顺序冲突 进程间的制约关系 间接制约：进行竞争－－独占分配到的部分或全部共享资源，“互斥” 直接制约：进行协作－－等待来自其他进程的信息，“同步” 临界资源:一次只允许一个进程使用(访问)的资源。如：硬件打印机、磁带机等，软件的消息缓冲队列、变量、数组、缓冲区等。 Operating System Concepts

14 Solution to Critical-Section Problem must satisfy 解决临界区问题需满足
1. Mutual Exclusion: If process Pi is executing in its critical section, then no other processes can be executing in their critical sections. 互斥：假定进程Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外. 2. Progress：If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. 有空让进：临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间. Operating System Concepts

15 Solution to Critical-Section Problem must satisfy (Cont.)
3. Bounded Waiting: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. 有限等待: 在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区前的等待时间必须是有限的. Assume that each process executes at a nonzero speed 假定每个进程都以非零的的速率执行. No assumption concerning relative speed of the n processes. 没有任何关于这n个进程相对执行速率的假定 Operating System Concepts

16 同步机制应遵循的准则 空闲让进。 当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。
忙则等待(互斥）。 当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其它试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源。 有限等待。 对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入“饥饿”状态。 让权等待。 当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。 Operating System Concepts

17 解释: 使用临界区的原则 每次只允许一个进程处于它的临界区(CS)中
若有多个进程同时想进入CS,应在有限时间内让其中一个进程进入CS,以免阻塞 进程在CS内只能逗留有限时间 不应使要进入CS的进程无限期地等待在CS之外 在CS之外的进程不可以阻止其他进程进入CS 不要预期和假定进程进展的相对速度以及可用的处理器数目. 因为这是不可预期的. Operating System Concepts

18 Fig 7.1 General structure of a typical process Pi
General structure of process Pi (other process Pj) do { entry section 进入区 critical section 临界区 exit section 退出区 reminder section 剩余区 } while (1); 临界区(critical section)：进程中访问临界资源的一段代码。 进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应"正在访问临界区"标志 退出区(exit section)：用于将"正在访问临界区"标志清除。 剩余区(remainder section)：代码中的其余部分。 Processes may share some common variables to synchronize their actions. Operating System Concepts

19 7.2.1 Two-Process Solutions Algorithm 1 （软件方法）
Only 2 processes, P0 and P1 Shared variables: int turn; initially turn = 0 turn = i  Pi can enter its critical section ( j=1-i) Process Pi do { while (turn != i) ; critical section turn = j; reminder section } while (1); Satisfies mutual exclusion, but not progress(不满足有空让进条件) Operating System Concepts

20 问题: 必须轮流使用临界区 如果一个进程失败,另一个进程将被永久阻塞
缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区； Operating System Concepts

21 7.2.1.2 Algorithm 2 Shared variables
boolean flag[2]; initially flag [0] = flag [1] = false. flag [i] = true  Pi ready to enter its critical section Process Pi do { flag[i] := true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1); Satisfies mutual exclusion, but not progress requirement (see next page). Operating System Concepts

22 7.2.1.2 Algorithm 2 not progress requirement：
if 两个进程在执行while语句前, 同时执行了: T0: P0 sets flag[0] := true T1: P1 sets flag[1] := true then P0 and P1 are looping forever in their respective while statements! 也即： Pi和Pj可能都进入不了临界区。当 Pi执行了flag[i] := true后， Pj执行了flag[j] := true，这样两个进程都无法进入临界区 Operating System Concepts

23 Algorithm 2-1 Shared variables
boolean flag[2]; initially flag [0] = flag [1] = false. flag [i] = true  Pi enter its critical section Process Pi do { while (flag[j]) ; { flag[i] := true; critical section} flag [i] = false; remainder section } while (1); Satisfies mutual exclusion, but not progress requirement. Pi和Pj可能同时进入临界区。当 Pi执行了while (flag[j])后，Pj执行while (flag[i]) ，这样两个进程同时进入了临界区 Operating System Concepts

24 7.2.1.3 Algorithm 3 Combined shared variables of algorithms 1 and 2.
Process Pi do { flag [i]:= true; turn = j; while (flag [j] and turn = j) ; critical section flag [i] = false; remainder section } while (1); Meets all three requirements; solves the critical-section problem for two processes. Operating System Concepts

25 Algorithm 3 结合算法1和算法2，是正确的算法 turn=j;描述可进入的进程（同时修改标志时）
在进入区先修改后检查，并检查并发修改的先后： 检查对方flag，如果不在临界区则自己进入－－空闲则入 否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入－－先到先入，后到等待 Operating System Concepts

26 7.2.1.3 Algorithm 3 To prove “Mutual exclusion” property
(That is Pi and Pj can’t be in CS at same time) Pi enter CS only if flag[j]==false or turn==i turn = 0 or 1, but cannot be both … To prove “Progress” property Pi is in while statements only when flag[j]==true and turn==j Then if Pj is not ready to enter CS, flag[j]==false if Pj ready to enter CS, flag[j]==true, but turn=i or j , so Pi or Pj can enter To prove “Bounded-waiting” property If Pj exit its CS, flag[j]=false, then Pi can enter its CS Operating System Concepts

27 Dekker算法 – 7.4题 var boolean flag[2] ; flag[0]=flag[1]=false;
int turn; turn=0/1; Pi:do { flag[i]=true; while flag[j] { if turn=j { flag[i]=false; while turn=j ; } Critical Section i 请证明：这个算法是否满足临界区 turn=j; 问题的三个条件 Remainder Section }while(1); Operating System Concepts

28 7.2.2 Multiple-Process Solutions Bakery Algorithm (面包房算法)
Algorithm of solving the Critical section for n processes Before entering its critical section, process receives a number. Holder of the smallest number enters the critical section. 在进入临界区前，进程接收一个数字，最小数字的持有者进入临界区 If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first. The numbering scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5... Operating System Concepts

29 Bakery Algorithm Define the following Notation
order : (a,b) -- (ticket #, process id #) (a,b) < (c,d) if a < c or if a = c and b < d max (a0,…, an-1) is a number, k such that k  ai for i = 0, …, n – 1 Shared data boolean choosing[n]; int number[n]; Data structures are initialized to false and 0 respectively Operating System Concepts

30 Fig 7.5 The structure of process Pi in the Bakery Algorithm
取一个编号（在原有编号基础上+1） do { choosing[i] = true; number[i] = max(number[0], number[1], …, number [n – 1])+1; choosing[i] = false; for (j = 0; j < n; j++) { while (choosing[ j]) ; while ((number[ j] != 0) &&((number[ j],j) < (number[i],i))) ; } critical section number[i] = 0; remainder section } while (1); Pj正在取编号 有j欲进入CS且Pj的编号<Pi ,或者Pi 和Pj同时拿到相同编号但j<i 此时Pi拥有最小的number[i] Operating System Concepts

31 实现进程同步的方式 Critical-section (软件方法) Synchronization hardware (硬件方法)
Semaphores (信号量方法） Operating System Concepts

32 7.3 Synchronization Hardware 同步的硬件实现 （硬件方法）
Hardware features can make the programming task easier and improve system efficiency. Hardware instruction: Test and modify the content of a word atomically. boolean TestAndSet(boolean &target) { boolean rv = target; target = true; return rv; } Operating System Concepts

33 Mutual Exclusion with Test-and-Set
Shared data: boolean lock = false; Process Pi do { while (TestAndSet(lock)) ; critical section lock = false; remainder section }while(1); 利用TestAndSet实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE 在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过； Operating System Concepts

34 The definition of Swap instruction
Atomically swap two variables. void Swap(boolean &a, boolean &b) { boolean temp = a; a = b; b = temp; } Operating System Concepts

35 Mutual Exclusion with Swap
Shared data (initialized to false): boolean lock; /* (a global variable) Process Pi do { key = true; /* ( a local variable) while (key == true) Swap(lock,key); critical section lock = false; remainder section } while (1); Don’t satisfy the bounded-waiting requirement (when Pi,Pj execute “key=true” at same time) Operating System Concepts

36 Fig 7.10 Bounded-waiting mutual exclusion with TestAndSet
Boolean waiting[n], lock ; global variables, to be initialize to false Do { waiting[i]=true; key= true; while ( waiting[i] && key ) key=TestAndSet(lock); waiting[i]=false; critical section; j= (i+1) % n ; while ((j != i) && !waiting[ j ]) j= (j+1) % n ; if (j == i) lock = false ; else waiting[ j ] = false ; remainder section ; }while(1) waiting[i] =false 意味着另一个进程从CS退出，并将Pi设置为可进入 Key=false 意味着已经没有一个进程处于CS 寻找下一个正在等待进入CS的进程 已经没有正在等待进入CS的进程 将Pj选为下一个可进入CS的进程 Operating System Concepts

37 Bounded-waiting mutual exclusion with TestAndSet
This algorithm satisfies all the critical section requirement . To prove that the mutual-exclusion（互斥条件） requirement Pi 可以进入CS只有在 waiting[i]== false 或 key == false时 只有在执行了 TestAndSet后，key 才可能变为 false；而且只有第一个执行了 TestAndSet 的进程，才能得到 key== false，其它进程必须等待 只有在一个进程离开CS时才会有一个（且最多仅有一个）进程的waiting[i] 由true变为false 从而确保满足互斥条件 Operating System Concepts

38 Bounded-waiting mutual exclusion with TestAndSet
To prove that the progress （有空让进条件）requirement (see p.200) 任何一个已经进入CS的进程在“exit section” 时，设置：lock =false 或 waiting[ j ]= false，确保了至少可以让一个进程进入CS To prove that the bounded-waiting（有限等待条件） requirement (see p.200) 任何一个已经进入CS的进程Pi在“exit section” 时， 将会依次扫描waiting 数组（i+1,i+2,…n-1,0,…i-1)，并仅将Pi后面最先找到的进程j的waiting[ j]设置为false 这就使进程能依此循环进入CS Operating System Concepts

39 适用于任意数目的进程，在单处理器或多处理器上 简单，容易验证其正确性 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量
硬件方法的优点 适用于任意数目的进程，在单处理器或多处理器上 简单，容易验证其正确性 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量 硬件方法的缺点 等待要耗费CPU时间，不能实现"让权等待" 可能"饥饿"：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上 可能死锁 Operating System Concepts

40 7.4 Semaphores信号量 --1965年由Dijkstra提出
软件和硬件方法解决互斥问题的缺陷: 软件:算法太复杂,效率不高 中断屏蔽方法:只能用于单机系统 硬件指令:忙等待 1965年，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具。在长期广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量机制发展到记录型信号量机制，进而发展为“信号集”机制。现在信号量机制已广泛应用于OS中。 Synchronization tool that does not require busy waiting.一种不需要忙等待的同步工具. Semaphore S – integer variable信号量S – 整型变量 解决N个进程的同步互斥问题 Operating System Concepts

41 每个信号量s除一个整数值s.value（计数）外，还有一个进程等待队列s.L，其中是阻塞在该信号量的各个进程的标识
信号量只能通过初始化和两个标准的原语来访问－－作为OS核心代码执行，不受进程调度的打断 初始化指定一个非负整数值，表示空闲资源总数（又称为"资源信号量"）－－若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数 “二值信号量(binary semaphore)"：只允许信号量取0或1值 Operating System Concepts

42 7.4.1 整型信号量 Semaphore S – integer variable信号量S – 整型变量
can only be accessed via two indivisible (atomic) operations 仅能通过两个不可分割的[原子]操作访问 wait (S): ( P-操作 ) while S 0 do no-op; S--; signal (S): ( V-操作) S++; Operating System Concepts

43 Fig 7.11 Multual-exclusion with semaphores
Shared data: semaphore mutex; //initially mutex = 1 Process Pi: do { wait(mutex); critical section signal(mutex); remainder section } while (1); Operating System Concepts

44 7.4.2 记录型信号量 To overcome the problem of “busy waiting”
Define a semaphore as a record typedef struct { int value; struct process *L; } semaphore; Assume two simple operations: block suspends the process that invokes it. wakeup(P) resumes the execution of a blocked process P. Operating System Concepts

45 Implementation Semaphore operations now defined as
wait(S) : S.value--; if (S.value < 0) { add this process to S.L; block; } signal(S) : S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } value 是负数，表示处于阻塞状态的进程数 Operating System Concepts

46 wait、signal操作讨论 信号量的物理含义 S.value >0 表示有S个资源可用；
S.value<0 则|S.value|表示在等待队列中进程的个数或表示等待进入临界区的进程个数。 wait(S)：表示申请一个资源；signal(S)表示释放一个资源。 Operating System Concepts

47 wait、signal操作讨论 wait、signal操作必须成对出现，有一个wait操作就一定有一个signal操作。当为互斥操作时，它们同处于同一进程。当为同步操作时，则不在同一进程中出现。 如果两个wait操作相邻，那么它们的顺序至关重要，而两个相邻的signal操作的顺序无关紧要。一个同步wait操作与一个互斥wait操作在一起时，同步wait操作在互斥wait操作前。 wait、signal操作的优缺点: 优点：简单，而且表达能力强（用wait、signal操作可解决任何同步互斥问题。） 缺点：不够安全；wait、signal操作使用不当会出现死锁；实现复杂。 Operating System Concepts

48 Semaphore as a General Synchronization Tool
Execute B in Pj only after A executed in Pi Use semaphore flag initialized to 0 Code: Pi Pj … … A wait(flag) signal(flag) B … … Operating System Concepts

49 同步原语的不可分割性 实现方法: 含义: 保证进程间互斥地使用同步原语 整体操作,不可分割 用软件的互斥算法,用开关中断保证整体性
不是好的解决方法 用硬件开关中断实现互斥和完整性 仅适用于单处理机系统 用硬件指令方法在多处理机中实现互斥 用硬件和固件直接实现同步原语 Operating System Concepts

50 同步原语的不可分割性 实例: 用硬件指令实现互斥使用的同步原语 Wait(S): While TS(lock) do skip; /* 上锁
While S<=0 do skip; /* 同步原语代码 S:=S-1; lock :=false ; /* 开锁 Signal(S): S:=S+1 /* 同步原语代码 Operating System Concepts

51 利用信号量实现：进程互斥 为使多个进程能互斥地访问某临界资源，只需为该资源设置一个互斥信号量mutex,并设其初值为1，然后将各进程的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。利用信号量实现共享打印机的A、B两进程互斥的类并行PASCAL程序描述如下： Operating System Concepts

52 利用信号量实现进程互斥-1 var mutex:semaphore:=1 ； begin parbegin A:begin B:begin
Input datd 1 from I/0 1 ； Input datd 2 from I/O 2 ； Compute……； Compute……； wait(mutex) ； wait(mutex) ； Print results1 by printer; Print results2 by printer; signal(mutex) ； signal(mutex) ； end end parend end Operating System Concepts

53 利用信号量实现：进程同步 利用信号量能解决进程间的同步问题，这里以下图所示的计算进程C和打印进程P通过缓冲区Buffer传送数据的同步问题为例说明。 Buffer C P Operating System Concepts

54 利用信号量实现进程同步-1 C和P两进程基本算法如下： C：begin P: begin repeat repeat
Compute next number ; take from Buffer ; add to Buffer ; print last number ; until false until false end end C和P两进程并发执行，必须在执行序列上遵循以下规则，才能避免错误: 只有当C进程把数据送入Buffer后，P进程才能从Buffer中取出数据来打印，否则P进程只能等待。 只有当P进程从Buffer中取走数据后，C进程才能将新计算的数据再存入Buffer,否则C进程也只能等待。 Operating System Concepts

55 利用信号量实现进程同步-2 为了实现进程同步，需采用同步信号量。 实现C和P两进程同步的类PASCAL程序：
为了满足第一条同步规则，设置一个同步信号量full，它代表的资源是缓冲器满，它的初值为0。 同样为了满足第二条同步规则，设置另一个同步信号量empty，它代表的资源是缓冲器空，它的初值为1 。 实现C和P两进程同步的类PASCAL程序： Operating System Concepts

56 var: empty,full:semaphore:=1,0 ； begin parbegin C: begin repeat
Compute next number ； wait(empty) ； Add to buffer ； siganl(full) ； until false end P: begin wait(full) ； Take from Buffer ； signal(empty) ； Print last number ； parend Operating System Concepts

57 7.4.3 Deadlock and Starvation
Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes. 死锁 – 两个或多个进程无限期地等待一个事件的发生，而该事件正是由其中的一个等待进程引起的 Let S and Q be two semaphores initialized to 1 S和Q是两个初值为1的信号量 P0 P1 wait(S); wait(Q); wait(Q); wait(S);   signal(S); signal(Q); signal(Q) signal(S); Operating System Concepts

58 Deadlock and Starvation
Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended. 饥饿 – 无限期地阻塞。进程可能永远无法从它等待的信号量队列中移去 Operating System Concepts

59 7.4.4 信号量集 AND型信号量集 一段处理代码需要同时获取两个或多个临界资源――可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让” 基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(Simultaneous Wait)。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。 Operating System Concepts

60 AND信号量 Swait(S1, S2, …, Sn) {while (TRUE)
{ if (S1 >=1 && S2 >= 1 && … && Sn >= 1) { for (i = 1; i <= n; ++i) --Si; break; } else {调用进程进入第一个小于1信号量的等待队列Sj.queue; 阻塞调用进程; Operating System Concepts

61 AND信号量 Ssignal(S1, S2, …, Sn) { for (i = 1; i <= n; ++i) { ++Si;
for (each process P waiting in Si.queue) { 从等待队列Si.queue中取出进程P; if (判断进程P是否通过Swait中的测试) { 进程P进入就绪队列; } else { 进程P进入某等待队列；} } Operating System Concepts

62 一般“信号量集” 一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁
       基本思想：在AND型信号量集的基础上进行扩充：进程对信号量Si的测试值为ti（用于信号量的判断，即Si >= ti，表示资源数量低于ti时，便不予分配），占用值为di（用于信号量的增减，即Si = Si - di和Si = Si + di ） Swait(S1, t1, d1; ...; Sn, tn, dn); Ssignal(S1, d1; ...; Sn, dn);        一般“信号量集”的几种特定情况：         Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配；         Swait(S, 1, 1)表示互斥信号量；        Swait(S, 1, 0)作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）；          一般“信号量集”未必成对使用Swait和Ssignal：如：一起申请，但不一起释放； Operating System Concepts

63 7.4.5 Two Types of Semaphores
Counting semaphore – integer value can range over an unrestricted domain. 计数信号量(一般信号量) – 变化范围没有限制的整型值 Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement. 二值(二元)信号量 – 变化范围仅限于0和1的信号量； --容易通过硬件方式实现 Operating System Concepts

64 Implementing S as a Binary Semaphore
A counting semaphore S can be implemented using binary semaphore. 计数信号量S可以用二值信号量实现 Data structures: binary-semaphore S1, S2; int C: Initialization: S1 = 1 S2 = 0 C = initial value of semaphore S Operating System Concepts

65 Implementing S wait operation wait(S1); C--; if (C < 0) {
signal(S1); wait(S2); } signal operation C ++; if (C <= 0) signal(S2); else S>0：表示可用资源数目 S=0：既无可用资源也无进程等待 S<0：绝对值表示等待的进程数 Operating System Concepts

66 7.5 Classical Problems of Synchronization 经典同步问题
7.5.1 Bounded-Buffer Problem 有限缓冲区问题（生产者消费者问题） 7.5.2 Readers and Writers Problem 读者写者问题 7.5.3 Dining-Philosophers Problem 哲学家就餐问题 Operating System Concepts

67 7.5.1 Bounded-Buffer Problem 有限缓冲区问题
（producer-consumer Problem ）生产者-消费者问题 生产者-消费者问题是最著名的同步问题，它描述一组生产者（P1 ……Pm）向一组消费者（C1……Cq）提供消息。它们共享一个有界缓冲池（bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息，如下图所示。生产者-消费者问题是许多相互合作进程的一种抽象。 Operating System Concepts

68 P1 Pmm C1 Cq B0 B …. …... ……… Bn-1 假定缓冲池中有n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，它只允许一个生产者投入消息，或者一个消费者从中取出消息。即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。所以必须设置互斥信号量mutex，它代表缓冲池资源，它的数值为1。 Operating System Concepts

69 生产者和消费者二类进程P和C之间应满足下列二个同步条件：
只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。 为了满足第一个同步条件，设置一个同步信号量full，它代表的资源是缓冲区满，它的初始值为0，它的值为n时整个缓冲池满。同样为了满足第二个同步条件，设置另一个同步信号量empty，它代表的资源是缓冲区空，它的初始值为n，表示缓冲池中所有缓冲区空。 Operating System Concepts

70 Bounded-Buffer Problem 有限缓冲区问题
Shared data Semaphore: full, empty, mutex; full – 满缓冲器的数量 empty – 空缓冲器的数量 mutex – 对缓冲器操作的互斥变量 Initially: full = 0, empty = n, mutex = 1 Operating System Concepts

71 Fig 7.12 The structure of Producer Process
do { … produce an item in nextp add nextp to buffer } while (1); Operating System Concepts

72 Fig 7.13 structure of the Consumer Process
do { … remove an item from buffer to nextc consume the item in nextc } while (1); Operating System Concepts

73 Fig 7.12 The structure of Producer Process
do { … produce an item in nextp wait(mutex); add nextp to buffer signal(mutex); } while (1); Operating System Concepts

74 Fig 7.13 structure of the Consumer Process
do { wait(mutex); … remove an item from buffer to nextc signal(mutex); consume the item in nextc } while (1); Operating System Concepts

75 Fig 7.12 The structure of Producer Process
do { … produce an item in nextp wait(empty); wait(mutex); add nextp to buffer signal(mutex); signal(full); } while (1); Operating System Concepts

76 Fig 7.13 structure of the Consumer Process
do { wait(full); wait(mutex); … remove an item from buffer to nextc signal(mutex); signal(empty); consume the item in nextc } while (1); Operating System Concepts

77 7.5.2 The Readers-Writers Problem 读者写者问题
一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称读者(Reader)，而另一些进程则要求修改数据集内容，它称写者(Writer)，几个读者可以同时读些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。 Shared data semaphore mutex, wrt; Initially mutex = 1, wrt = 1, readcount = 0 Operating System Concepts

78 Fig 7.14 The structure of a Writer Process
引人互斥信号量 wrt wait(wrt); … writing is performed signal(wrt); Operating System Concepts

79 Fig 7.15 The structure of a Reader Process
第一个读者到时: wait(wrt); … reading is performed 最后一个读者离开时: signal(wrt); Operating System Concepts

80 Fig 7.15 The structure of a Reader Process
用readcount变量来记录读者数，读者程序为： readcount++; if (readcount == 1) wait(wrt); … reading is performed readcount--; if (readcount == 0) signal(wrt); Operating System Concepts

81 Fig 7.15 The structure of a Reader Process
由于readcount是读者间共享变量，属于临界资源，它也需互斥，为此又 引人互斥信号量mutex: wait(mutex); /*确保互斥访问 readcount++; if (readcount == 1) /*第一个读者进入时 wait(wrt); 确保没有写者存在 signal(mutex); … reading is performed wait(mutex); /*确保互斥访问 readcount--; if (readcount == 0) /*最后一个读者离开时 signal(wrt); 唤醒可能等待的写者 signal(mutex)； Operating System Concepts

82 用一般信号集机制解读者-写者问题 采用一般"信号量集"机制：增加一个限制条件：同时读的"读者"最多RN个 mx表示"允许写"，初值是1
L表示"允许读者数目"，初值为RN var RN integer ; L , mx : semaphore :=RN ,1 ; begin parbegin reader : begin repeat Swait (L , 1 , 1 ) ; Swait (mx , 1 , 0 ) ; perform read operation Ssignal (L , 1) ; until false ; end Operating System Concepts

83 用一般信号集机制解读者-写者问题-1 writer: begin repeat Swait (mx ,1, 1, L , RN , 0 );
perform write operation Ssignal (mx , 1 ) ; until false ; end parend Operating System Concepts

84 7.5.3 Dining-Philosophers Problem 哲学家就餐问题
问题描述：（由Dijkstra首先提出并解决） 5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支； 哲学家的动作包括思考和进餐； 进餐时需要同时拿起他左边和右边的两支筷子；思考时则同时将两支筷子放回原处。 如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子； Operating System Concepts

85 Dining-Philosophers Problem
Shared data semaphore chopstick[5]; Initially all values are 1 Operating System Concepts

86 Fig 7.17 The structure of Philosophers i
Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) … eat signal(chopstick[i]); signal(chopstick[(i+1) % 5]); think } while (1); Operating System Concepts

87 哲学家就餐问题讨论 为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子
给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿 Operating System Concepts

88 7.6 Critical Regions 临界区 信号量存在的问题 Signal和Wait 使用次序颠倒 signal(mutex) …
critical section wait(mutex) 当多个进程同时访问临界区时,破坏了临界资源的互斥性 Operating System Concepts

89 Critical Regions 信号量存在的问题-1 Wait 被换成Signal wait(mutex) …
critical section Result: Deadlock will occur Operating System Concepts

90 Critical Regions 信号量存在的问题-2 缺少Wait或Signal Result: 破坏互斥性或造成死锁
Operating System Concepts

91 Critical Regions High-level synchronization construct
A shared variable v of type T, is declared as: v: shared T Variable v accessed only inside a region statement region v when B do S where B is a boolean expression. It means “while statement S is being executed, no other process can access variable v. ” Operating System Concepts

92 (conditional) Critical Regions
Regions referring to the same shared variable exclude each other in time. 访问区域相同共享变量同时互斥。 When a process tries to execute the region statement, the Boolean expression B is evaluated. If B is true, statement S is executed. If it is false, the process is delayed until B becomes true and no other process is in the region associated with v. Operating System Concepts

93 (conditional) Critical Regions
If two statements are executed concurrently in two processes: region v when (true) S1 region v when (true) S2 The result will be executed sequentially as “S1 followed by S2” or “S2 followed by S1” Operating System Concepts

94 Example – Bounded Buffer
Critical-region construct 可以有效地解决一般的同步问题。 例如：生产者-消费者问题： Shared data: struct buffer { int pool[n]; int count, in, out; } Operating System Concepts

95 Bounded Buffer Producer Process
Producer process inserts nextp into the shared buffer region buffer when( count < n) { pool[in] = nextp; in:= (in+1) % n; count++; } Operating System Concepts

96 Bounded Buffer Consumer Process
Consumer process removes an item from the shared buffer and puts it in nextc region buffer when (count > 0) { nextc = pool[out]; out = (out+1) % n; count--; } Operating System Concepts

97 Implementation region x when B do S (自学）
The conditional critical region could be implemented by a compiler. Associate with the shared variable x, the following variables: semaphore mutex, first-delay, second-delay; int first-count, second-count; Mutually exclusive access to the critical section is provided by mutex. mutex提供互斥访问临界区。 If a process cannot enter the critical section because the Boolean expression B is false, it initially waits on the first-delay semaphore; moved to the second-delay semaphore before it is allowed to reevaluate B. 如果因为布尔表达式 B 是false，进程不能进入临界区，它开始 等待first-delay信号量;在它被允许再计算B以前，改到second-delay信号量。 Operating System Concepts

98 Implementation region x when B do S (Cont.)
wait(mutex); while(!B) { first_count++; if (second_count>0) signal(second_delay); else signal(mutex); wait(first_delay); first_count--; second_count++; if (first_count>0) signal(first_delay); else signal(second_delay); wait(second_delay); second_count--; } S; Operating System Concepts

99 Implementation region x when B do S (Cont.)
If (first_count>0) signal(first_delay); else if (second_count>0) signal(second_delay); else signal(mutex); Operating System Concepts

100 Implementation Keep track of the number of processes waiting on first-delay and second-delay, with first-count and second-count respectively. 记录等待first-delay and second-delay的进程数 与first-count and second-count分别地。 The algorithm assumes a FIFO ordering in the queuing of processes for a semaphore. 算法假定信号量进程队列为一个FIFO For an arbitrary queuing discipline, a more complicated implementation is required. 为任意队列要求，需要更复杂的实现 Operating System Concepts

101 7.7 Monitors管程 用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。
管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。 管程可以函数库的形式实现。相比之下，管程比信号量好控制。 Operating System Concepts

102 1. 信号量同步的缺点 同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如wait、signal操作的次序错误、重复或遗漏） 易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序； 不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局； 正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误； Operating System Concepts

103 2. 管程的引入 最早由Dijkstra提出, 1974年，Hoare和Hanson所实现；其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。 管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。 管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性 引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。 Operating System Concepts

104 高级的同步机构允许并发进程间一种抽象的数据类型安全共享。
High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes. 高级的同步机构允许并发进程间一种抽象的数据类型安全共享。 A monitor is characterized by a set of programming-defined operators 一个管程表示一个编程定义操作的集合 The monitor construct ensures that only one process at a time can be active within monitor. 管程结构保证在某一时刻仅仅一个进程运行在管程里。 Operating System Concepts

105 3. 管程的主要特性 模块化：一个管程是一个基本程序单位，可以单独编译；
抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码 信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的； Operating System Concepts

106 4. 管程的实现要素 管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量；
为了保证管程共享变量的数据完整性，规定管程互斥进入； 管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作； Operating System Concepts

107 5. 管程中的多个进程进入 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如Ｐ唤醒Ｑ），管程中便存在两个同时处于活动状态的进程。 管程中的唤醒切换方法： P等待Q继续，直到Q等待或退出； Q等待P继续，直到P等待或退出； 规定唤醒为管程中最后一个可执行的操作； Operating System Concepts

108 入口等待队列：因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。
紧急等待队列：如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ等待Ｒ继续，...，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程（已被唤醒，但由于管程的互斥进入而等待），因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级。 Operating System Concepts

109 6. 条件变量(condition) 由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量----条件变量。每个表示一种等待原因，并不取具体数值－－相当于每个原因对应一个队列。 Operating System Concepts

110 Fig 7.21 Monitor With Condition Variables
Operating System Concepts

111 同步操作原语wait和signal：针对条件变量x，x.wait()将自己阻塞在x队列中，x.signal()将x队列中的一个进程唤醒。
x.wait()：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程排入x队列尾部（紧急等待队列与x队列的关系：紧急等待队列是由于管程的互斥进入而等待的队列，而x队列是因资源被占用而等待的队列） X.signal()：如果x队列为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程排入紧急等待队列的尾部 若进程P唤醒进程Q，则随后可有两种执行方式（进程P、Q都是管程中的进程） P等待，直到执行Q离开管程或下一次等待。Hoare采用。 Q送入Ready队列，直到执行P离开管程或下一次等待。1980年，Lampson和Redell采用。 Operating System Concepts

112 7. 管程的的组成 名称：为每个共享资源设立一个管程 数据结构说明：一组局部于管程的控制变量
操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。 初始化代码：对控制变量进行初始化的代码 Operating System Concepts

113 The syntax of a monitor管程的语法
monitor monitor-name { shared variable declarations procedure body P1 (…) { } procedure body P2 (…) { } procedure body Pn (…) { } { initialization code } Operating System Concepts

114 Fig 7.20 Schematic View of a Monitor
Operating System Concepts

115 8. 管程和进程的异同点 设置进程和管程的目的不同 系统管理数据结构 进程：PCB 管程：等待队列 管程被进程调用
管程是操作系统的固有成分，无创建和撤消 Operating System Concepts

116 Monitors (Cont.-1) To allow a process to wait within the monitor, a condition variable must be declared, as 允许一个进程在管程里等待（阻塞），一个条件变量必须被声明 condition x, y; Condition variable can only be used with the operations wait and signal. 条件变量只能使用wait 和 signal 操作 Operating System Concepts

117 Monitors (Cont.-2) The operation x.wait() means that the process invoking this operation is suspended until another process invokes x.signal(); x.wait ()操作表示调用这操作的进程挂起在条件x上，直到另外的进程调用 x.signal () The x.signal operation resumes exactly one suspended process. If no process is suspended, then the signal operation has no effect. x.signal()操作恢复（唤醒）在条件x上被挂起进程。如果没有进程被挂起，那么signal操作没有效果。[注意:与信号量的区别] Operating System Concepts

118 Fig 7.20 Schematic View of a Monitor
Operating System Concepts

119 Fig 7.21 Monitor With Condition Variables
Operating System Concepts

120 Structure of Monitor Procedure 1 Procedure k Initialization Code Exit
Entrance Queue of Entering Processes Monitior Waiting Area Condition c1 C1.wait . condition cn Cn.wait Urgent Queue Cx.signal Exit M0NITOR Local Data Condition Variables Procedure 1 Procedure k Initialization Code Operating System Concepts

121 Monitors (Cont.-2) When the x.signal() operation is invoked by process P, there is a suspended process Q associated with condition X. Two possibilities exist: 当 x.signal () 操作被进程 P 调用, 有一个与条件便变量 X相关的被挂进程Q 。存在二个可能性： P either waits until Q leaves the monitor, or waits for another condition. P等待直到 Q 离开管程，或等另外的条件。 2. Q either waits until P leaves the monitor, or waits for another condition. Q等待直到 P 离开管程，或等另外的条件。 Operating System Concepts

122 Example of Monitor A monitor solution to the Dining- Philosophers
Operating System Concepts

123 Fig 7.22 A monitor solution to the Dining- Philosophers
monitor dp { enum {thinking, hungry, eating} state[5]; //每个哲学家都处在“thinking, hungry, eating”三种状态之一 condition self[5]; void pickup(int i) // following slides void putdown(int i) // following slides void test(int i) // following slides void init() { for (int i = 0; i < 5; i++) state[i] = thinking; } Operating System Concepts

124 Fig 7.22 A monitor solution to the Dining- Philosophers (Cont.)
void pickup(int i) { state[i] = hungry; test[i]; if (state[i] != eating) self[i].wait(); } void putdown(int i) { state[i] = thinking; // test left and right neighbors test((i+4) % 5); //唤醒可能在self[i+4]上阻塞的进程 test((i+1) % 5); //唤醒可能在self[i+1]上阻塞的进程 Operating System Concepts

125 Fig 7.22 A monitor solution to the Dining- Philosophers (Cont.-1)
void test(int i) { if ( (state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating)) { state[i] = eating; self[i].signal(); } Operating System Concepts

126 Fig 7.22 A monitor solution to the Dining- Philosophers (Cont.-2)
Philosopher[i]: Do{ dp.pickup(i); eat dp.putdown(i); think }while(1) 确保: No deadlock will occur It’s possible for a philosopher to starve to death Operating System Concepts

127 Monitor Implementation Using Semaphores[*]
Variables semaphore mutex; // (initially = 1) semaphore next; // (initially = 0) int next-count = 0; Each external procedure F will be replaced by wait(mutex); … body of F; if (next-count > 0) signal(next) else signal(mutex); Mutual exclusion within a monitor is ensured. Operating System Concepts

128 Monitor Implementation [*]
For each condition variable x, we have: semaphore x-sem; // (initially = 0) int x-count = 0; The operation x.wait can be implemented as: x-count++; if (next-count > 0) signal(next); else signal(mutex); wait(x-sem); x-count--; Operating System Concepts

129 Monitor Implementation
The operation x.signal can be implemented as: if (x-count > 0) { next-count++; signal(x-sem); wait(next); next-count--; } Operating System Concepts

130 Monitor Implementation
Conditional-wait construct: x.wait(c); c – integer expression that is evaluated when the wait operation is executed. value of c (a priority number) stored with the name of the process that is suspended. when x.signal is executed, process with smallest associated priority number is resumed next. Operating System Concepts

131 Monitor Implementation(cont.)
Check two conditions to establish correctness of system:系统建立正确性要检查 2 个条件： User processes must always make their calls on the monitor in a correct sequence. 用户进程必须正确的顺序调用管程。 Must ensure that an uncooperative process does not ignore the mutual-exclusion gateway provided by the monitor, and try to access the shared resource directly, without using the access protocols. 必须保证不同步进程不忽略管程提供了的互斥网关，并且试图直接存取共享资源, 没有使用存取协议。 Operating System Concepts

132 7.8 OS Synchronization 操作系统的同步机制
7.8.1 Synchronization in Solaris 2 Implements a variety of locks to support multitasking, multithreading (including real-time threads), and multiprocessing. 实现各种锁支持多任务、多线程(包括实时线程)、和多进程 Uses adaptive mutexes for efficiency when protecting data from short code segments. 当保护数据短代码段时，为了效率使用可变互斥量 Uses condition variables and readers-writers locks when longer sections of code need access to data. 当代码的更长部分需要访问到数据时，使用条件变量和读者-写者锁 Uses turnstiles to order the list of threads waiting to acquire either an adaptive mutex or reader-writer lock. 使用 turnstiles(十字转门,栅门) 排列等待需要适应互斥或读者-写者锁的线程列表 Operating System Concepts

133 7.8.2 Windows 2000 Synchronization
Uses interrupt masks to protect access to global resources on uniprocessor systems. 在单处理机系统上使用中断屏蔽保护存取全局资源 Uses spinlocks(自旋锁) on multiprocessor systems. 在多处理机系统上使用自旋锁。 利用busy waiting 而非blocking来阻止进程前进； CPU不会去做其他事情，虽然浪费了部分CPU时间，但省去了进程切换； 适合短代码的加锁: wait(S): S--; while S<0 do{}; signal(S): S++; 与spin lock相对应的就是suspend lock（挂起锁），即一般的锁，会挂起（阻塞）进程的执行 Operating System Concepts

134 Windows 2000 Synchronization (cont.)
Provides dispatcher objects for thread synchronization outside of the kernel . 为内核外线程同步提供调度器对象 。 Using a dispatcher objects, a thread can synchronize according to several different mechanisms include mutexes 、semaphores and event. An event acts much like a condition variable. 使用一个调度器对象, 一个线程能根据不同的同步机制,包括 互斥 、信号量和事件等。一个事件类似一个条件变量。 Dispatcher objects may be in either a signaled or nonsignaled state. 调度器对象可以在任何一个signaled可用或 nonsignaled不可用状态。 Operating System Concepts

135 对象名称是由用户给出的字符串。不同进程中用同样的名称来创建或打开对象，从而获得该对象在本进程的句柄。
Windows 2000/XP的进程互斥和同步 在Windows 2000/XP中提供了互斥对象、信号量对象和事件对象等三种同步对象和相应的系统调用，用于进程和线程同步。从本质上讲，这组同步对象的功能是相同的，它们的区别在于适用场合和效率会有所不同。 对象名称是由用户给出的字符串。不同进程中用同样的名称来创建或打开对象，从而获得该对象在本进程的句柄。 对象状态可分成可用和不可用两种。对象可用(signaled state)表示该对象不被任何线程使用或所有；而对象不可用(nonsignaled state)表示该对象被某线程使用。 返回 Operating System Concepts

136 互斥对象(Mutex)相当于互斥信号量，在一个时刻只能被一个线程使用。
Windows 2000/XP的进程互斥和同步-1 互斥对象(Mutex)相当于互斥信号量，在一个时刻只能被一个线程使用。 信号量对象(Semaphore)是资源信号量，它的取值在0到指定最大值之间，用于限制并发访问的线程数。 事件对象(Event)相当于“触发器”，可通知一个或多个线程某事件的出现。 临界区对象(Critical Section)只能用于在同一进程内使用的临界区，同一进程内各线程对它的访问是互斥进行的。 互锁变量访问是最基本的互斥手段，其他的互斥和共享机制都是以它为基础的。它相当于硬件TS指令。用于对整型变量的操作，可避免线程间切换对操作连续性的影响。 Operating System Concepts

137 7.9 Atomic Transactions[*] 原子事务处理
To use database-systems techniques in operating system 7.9.1 System Model 系统模型 A collection of instructions (or operations) that performs a single logical function is called a transaction(事务). A major issue in processing transactions is the preservation of atomicity(保护原子性) despite the possibility of failures within the computer system. A transaction is simply a sequence of read and write operation,terminated by either a commit operation or an abort operation. The state of the data accessed by an aborted transaction must be restored to what it just before the started executing. Such a transaction has been rolled back回退. Ques纪录回退 Operating System Concepts

138 Atomic Transactions (cont.)
We are concerned with ensuring transaction atomicity in an environment where failure result in loss of information on volatile storage (nonvolatile storage ,stable storage). 7.9.2 Log-Based Recovery 基于日志的恢复 One way to ensure atomicity is to record , on stable storage, information describing all the modifications made by the transactions to the various data it accessed. The most widely used method for achieving this form of recording is write-ahead logging (预写日志纪录) 。 The system maintains , on stable storage , a data structure called the log(日志). Each log record describes a single operation of a transaction write , and has the following fields: Transaction Name , Data Item Name , Old Value and New Value. Operating System Concepts

139 Atomic Transactions (cont.)
Using the log , the system can handle any failure that does not result in the loss of information on nonvolatile storage. The recovery algorithm uses two procedures: undo(Ti) and redo(Ti). 7.9.3 Checkpoint 检查点 To reduce these types of overhead : most of the transactions need to be redone have already actually updated the data that the log says they need to modify, we introduce the concept of checkpoint. During execution ,the system maintain the write-ahead log and periodically performs checkpoint. 7.9.4 Concurrent Atomic Transactions 并行的原子事务处理 Operating System Concepts

140 Ex. 7.4Dekker算法 7.4 第一个公认的解决两进程（线程）临界区问题的算法是由Dekker提出的，故称为Dekker算法。算法如下所示。说明该算法满足临界区问题的三个必要条件。 共享变量： int turn, 初值为0； Boolean flag[2]，初值均为false; Pi(i=0,1) Operating System Concepts

141 Ex. 7.4Dekker算法(2) while(1) { flag[ i ] = true; 1.互斥(mutual exclusion)
while (flag[j]) { if (turn==j) { flag[ i ] = false; while ( turn == j ); } CS turn = j; RS 1.互斥(mutual exclusion) A) Pi和Pj不可能同时进入CS： turn==j 和turn==I不会同时满足 B)一个进程(如Pi)先进入CS,则flag[ i ]为true,则Pj无法进入 2.前进(progress） A)Pi申请进入，Pj不想进入，则flag[ i ]==false,Pi顺利进入 B)Pi和Pj都想进入，则turn==j时Pj进入，turn==i时Pi进入 3.有限等待(bounded waiting) Pi离开CS后，置turn=j,flag[ i ]=false,这时Pj可以进入，如果Pj没有进入，Pi又执行了falg[ i ]=true,则由于turn==j，所以Pi无法进入，而Pj可以进入 Operating System Concepts

142 Ex. 7.5Eisenberg and McGuire’s algorithm
7.5 第一个公认的n进程临界区问题的解决方法是由Eisenberg和McGuire提出的。该算法中，n个进程共享下面的变量： enum pstate { idle, want_in, in_cs }; pstate flag[n]; int turn; 算法描述如下页 证明该算法满足临界区问题的所有要求。 Operating System Concepts

143 Ex. 7.5Eisenberg and McGuire’s algorithm(2)
1.互斥(mutual exclusion) A) 两个进程Px和Py不可能同时进入CS： turn==x 和turn==y不会同时满足，故Px和Py的两个if 条件不会都满足 B)一个进程(如Px)先进入CS,则turn==x，flag[turn]==in_cs,则其他进程无法进入 2.前进(progress） A)Px申请进入，其他进程不想进入，则其他进程flag均为idle,则Px的j>=n成立，if条件成立，跳出while，进入CS B)若干进程想进入，如Pturn也想进入，则Pturn优先进入；否则，编号在turn后的最小号的想进入的进程进入CS 3.有限等待(bounded waiting) Pi离开CS时，置turn为想进入的进程中大于turn的最小欲进入之进程号，该进程就进入。 进程Pk不会饿死，最多等待（k-turn)个进程的CS执行 While(1) { while(1) { flag[i] = want_in; j = turn; while (j !=i) { if (flag[j]!=idle) j = turn else j = (j+1)%n; } flag[i] =in_cs; j = 0; while ((j<n)&&(j ==i || flag[j]!=in_cs) j ++ ; if ((j>=n)&&(turn==i||flag[turn]==idle)) break; turn = i ; CS j = (turn+1)%n; while(flag[j]==idle) j=(j+1)%n; turn=j; flag[i]=idle; RS Operating System Concepts

144 Ex. 7.8 理发问题 7.8 理发问题：一个理发店内有一张沙发，可以坐n个等待理发的顾客，理发室内有一张理发椅。当没有顾客时，理发师就休息；当一个新顾客进来时，如果所有的座位上都有人，他就离开理发店；如果沙发上有空位，他就坐下；如果理发师在休息，顾客就唤醒他让他为其理发。试用信号量来同步理发师和顾客的行为。 Operating System Concepts

145 Ex. 7.8 理发问题(2) Semaphore max; //初始n+1,表示理发店可以容纳总人数
Semaphore chair; //初始n，空闲的椅子 Semaphore barber; //初始1，表示理发椅空闲 Semaphore finished; //初始0，表示一次理发结束 Semaphore ready; //初始0，表示客人准备就绪 Customer: While(1){ wait(max); wait(chair); wait(barber); signal(chair); signal(ready); … barbered … wait(finished); signal(max); } Barber: wait(ready); … barbering… signal(finished); signal(barber); Operating System Concepts

146 Ex. 7.9抽烟问题 7.9抽烟问题：有一个烟草代理和三个抽烟者。抽烟者若要抽烟，必须具有烟叶、烟纸和火柴。三个抽烟者中，一人缺烟叶、一人缺烟纸、一人缺火柴。烟草代理会源源不断地分别供应烟叶、烟纸和火柴，并将他们放在桌上。如果他放的是烟叶，则缺烟叶的抽烟者拾起烟叶，制作香烟，然后抽烟；其他类推。试用信号量同步烟草代理和三个抽烟者。 Operating System Concepts

147 Ex. 7.9抽烟问题(2) Semaphore smoker[3]; //初始0，三个抽烟者
Semaphore material[3]; //初始0，三种原料 Semaphore agent; //初始1，供应商 Int turn; //初始0，轮到谁 Agent: While(1){ wait(agent); signal(smoker[turn]); signal(material[(turn+1)%3]); signal(material[(turn+2)%3]); turn= (turn+1)%3; } Smoker-i: wait(smoker[i]); wait(material[(i+1)%3]); wait(material[(i+2)%3]); signal(agent); Operating System Concepts

148 Ex. 7.11 7.11 写一个管程（monitor）用于实现有限缓冲区的生产者－消费者问题，要求将有限缓冲区置于管程内。
Operating System Concepts

149 Ex. 7.11(2) Monitor bounded_buffer { Producer process: While(1) {
item pool[n]; int count, in, out; condition full, empty; void get_item() if (count==0) full.wait(); get_from_buffer(); count--; empty.signal(); } void put_item() if (count==n) empty.wait(); put_to_buffer(); count++; full.signal(); void init() { count=in=out=0;} Producer process: While(1) { produce an item; bounded_buffer.put_item(); } Consumer process: While (1) { bounded_buffer.get_item(); consume the item; Operating System Concepts

150 2003年硕士研究生入学考试试题2 4. 关于临界区问题（critical section problem）的一个算法（假设只有进程P0和P1可能会进入该临界区）如下（i为0或1），该算法 。 A、不能保证进程互斥进入临界区，且会出现“饥饿”（Starvation) B、不能保证进程互斥进入临界区，但不会出现“饥饿” C、保证进程互斥进入临界区，但会出现“饥饿” D、保证进程互斥进入临界区，不会出现“饥饿” repeat retry：if (turn ) turn := i； if (turn i ) go to retry； turn := -1； Critical Section（临界区） turn := 0； remainder Section（其它区域） until false； 答：A Operating System Concepts

151 2000年硕士研究生入学考试试题2 (10分) 下述关于双进程临界区问题的算法（对编号为id的进程）是否正确： do{
blocked[id]=true; while(turn !=id)of { while(blocked[1-id]); turn=id; } <编号为id的进程的临界区 CS> blocked[id]=false; 编号为id的进程的非临界区 } while (true)： 其中，布尔型数组blocked[2]初始值为为{false,false}，整型turn初始值为0，id代表进程编号（0或1）。请说明它的正确性，或指出错误所在。 若此时进程切换，且让对方再次进入临界区，互斥条件无法满足 Operating System Concepts

152 2000年硕士研究生入学考试试题3 (10分) 信号量如果只能取0或1为值，就变成了二元信号量。二元信号量更容易实现。而且，信号量可以由二元信号量替换。以下所列函数试图用二元信号量操作waitB()和signalB()替换信号量wait()、signal()： …… 其中，用于互斥的二元信号量mutex初始化为1，用于进程挂起的二元信号量delay初始化为0。请指出该替换算法的错误所在。 Operating System Concepts

153 2000年硕士研究生入学考试试题3 (2) wait(semaphore s) signal(semaphore s) {
waitB(mutex); s = s-1; if (s<0) { signalB(mutex); waitB(delay); } else signalB(mutex); signal(semaphore s) { waitB(mutex); s= s+1; if(s<=0) signalB(delay); signalB(mutex); } 1、s = 0 时，p1 calls wait() and p2 calls wait()并都在执行waitB(delay)前交出CPU 2、p3 and p4 call signal()。此时本应允许p1 and p2 wakeup，但因delay升至1后无法再升，导致p1 or p2 中一个仍在wait(delay) Operating System Concepts

154 1997年硕士研究生入学考试试题4 program attemp; var c1，c2 ：integer；
下述流程是解决两进程互斥访问临界区问题的一种方法。试从“互斥”（mutual exclusion）、"空闲让进"（progress）、"有限等待"(bounded waiting)三方面讨论它的正确性。如果它是正确的，则证明之；如果它不正确，请说明理由。 program attemp; var c1，c2 ：integer； procedure p1（*第一个进程p1*） begin repeat Remain Section 1； c1=1-c2； until c2<>0 Critical Section；(*临界区*) C1=1； Until false End Operating System Concepts

155 1997年硕士研究生入学考试试题4 (2) Procedure p2 （*另一个进程p2*） begin repeat
Remain Section 2； Repeat c2=1-c1； Until c1<>0 Critical Section ；(*临界区*) c2=1； until false end begin（*主程序*） c1=1； cobegin p1； p2；（*二进程p1,p2开始*） coend Operating System Concepts

156 2005年硕士研究生入学考试试题2 试题2 （10分）试就Mutual Exclusion、 Progress、Bounded Waiting 论述以下解决双进程临界区问题的算法是错误的： Process P0: do { flag[0] =true; while (flag[1]); critical section flag[0] =false; remainder section } while (1); Process P1: flag[1] =true; while (flag[0]); flag[1] =false; Operating System Concepts

157 2005年硕士研究生入学考试试题2 （2） 答案： Mutual Exclusion （3分） 满足 Progress （4分） 不满足
反例：当P0对flag[0]赋值，紧接着，马上执行P1对flag[1]的赋值。于是，P0在while（flag[1]）语句中等待，而P1在while（flag[0]）语句等待 Bounded Waiting （3分） Operating System Concepts

158 2005年硕士研究生入学考试试题1 试题1 （20分） 设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms,打印100ms，再计算50ms，打印100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图（可以用Gantt Chart），并说明： （1）开始运行后，CPU有无空闲等待?若有，在哪段时间内等待？计算CPU的利用率 （2）进程A运行时有无等待现象？ 若有，在什么时候发生等待现象？ （3）进程B运行时有无等待现象？ 若有，在什么时候发生等待现象？ Operating System Concepts

159 Exercises 4, 8, 11 Operating System Concepts