Process Synchronization Problem. o Shared data among cooperating processes/threads Directly:Shared local address space Indirectly:through files or messages o Concurrent access to shared data may result in data inconsistency o How to ensure the orderly execution to achieve data consistency 口⊙卡生年12月0C 东香兰xlanchen@ustc,edu.cn http:/staff..u011740i:Operating System操作系统原理 March29,20193/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Process Synchronization Problem. Shared data among cooperating processes/threads ▶ Directly: Shared local address space ▶ Indirectly: through files or messages Concurrent access to shared data may result in data inconsistency How to ensure the orderly execution to achieve data consistency 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 3 / 57
Outline Background 2 The Critical-Section Problem(临界区问题) Peterson's Solution ④ Synchronization Hardware o TestAndSet Instruction o Swap Instruction 5 Semaphores 6 Classical Problems of Synchronization 7 Monitors 8 Synchronization Examples 小结和作业 口18，走卡1，月00 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理斐 March29,20194/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 1 Background 2 The Critical-Section Problem (临界区问题) 3 Peterson’s Solution 4 Synchronization Hardware TestAndSet Instruction Swap Instruction 5 Semaphores 6 Classical Problems of Synchronization 7 Monitors 8 Synchronization Examples 9 小结和作业 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 4 / 57
Background o The processes are cooperating with each other directly or indirectly. Independent process cannot affect or be affected by the execution of another process Cooperating process can affect or be affected by the execution of another process o Concurrent access(并发访问)to shared data may result in data inconsistency(不-致) for example:printer,shared variables/tables/lists o Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes 口18，走卡11月00 陈话兰xlanchen@ustc.edu.cn http/staff.u0117401 Operating System操作系统原理斐 March29,.20196/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Background The processes are cooperating with each other directly or indirectly. ▶ Independent process cannot affect or be affected by the execution of another process ▶ Cooperating process can affect or be affected by the execution of another process Concurrent access (并发访问) to shared data may result in data inconsistency(不一致) ▶ for example: printer, shared variables/tables/lists Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 6 / 57
Background:Producer-Consumer Problem ●Producer-Consumer Problem(生产者-消费者问题，PC问题)： Paradigm for cooperating processes ~producer(生产者)process produces information that is consumed by a consumer(消费者)process.. o Previously,Shared-Memory solution with bounded-buffer producer consumer A buffer of items shared memory 口1回年走1,2月Q0 陈话兰xlanchen@ustc.edu.cn http/staff.u0117401 Operating System操作系统原理斐 March29,20197/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Background: Producer-Consumer Problem Producer-Consumer Problem (生产者-消费者问题，PC问题): Paradigm for cooperating processes ▶ producer (生产者) process produces information that is consumed by a consumer (消费者) process. Previously, Shared-Memory solution with bounded-buffer A buffer of items shared memory producer consumer 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 7 / 57
Bounded-Buffer-Shared-Memory Solution Insert()Method while (true)( /Produce an item/ while (((in 1)%BUFFER SIZE)==out) :/*do nothing--no free buffers"/ buffer[in]item; in =(in +1)%BUFFER SIZE; Shared variables reside in a Remove()Method shared region while(true)( #define BUFFER_SIZE 10 while (in =out) typedef struct{ /do nothing--nothing to consume /remove an item from the buffer 】item: item buffer[out]: item buffer[BUFFER SIZE]: out =(out +1)%BUFFER SIZE; return item; int in =0;/index of the next empty buffer int out =0,//index of the next full buffer oSolution is correct,but can only use BUFFER SIZE-1 elements all empty?VS.all full? 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理 March29,20198/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bounded-Buffer – Shared-Memory Solution n-1 0 1 Shared variables reside in a shared region #define BUFFER_SIZE 10 typedef struct { ... } item; item buffer[BUFFER_SIZE]; int in = 0; // index of the next empty buffer int out = 0; // index of the next full buffer Insert() Method while (true) { /* Produce an item */ while (((in + 1) % BUFFER_SIZE) == out) ; /* do nothing −− no free buffers */ buffer[in] = item; in = (in + 1) % BUFFER SIZE; } Remove() Method while (true) { while (in == out) ; // do nothing −− nothing to consume // remove an item from the buffer item = buffer[out]; out = (out + 1) % BUFFER SIZE; return item; } Solution is correct, but can only use BUFFER_SIZE-1 elements ▶ all empty? VS. all full? 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 8 / 57
Another solution using counting value oA solution to the PC problem that fills all the buffers(not BUFFER SIZE-1). oAn integer count:keeps track of the number of full buffers. Initially,count =0. Incremented by the producer after it produces a new buffer, and decremented by the consumer after it consumes a buffer. Producer Consumer while(true){ while(true){ /produce an item and put in while (count =0) nextProduced * ;∥do nothing while (count =BUFFER SIZE) nextConsumed buffer[out]; ;/∥do nothing out =(out 1)%BUFFER_SIZE; buffer [in]nextProduced; count--; in =(in +1)%BUFFER SIZE; /consume the item in count++; nextConsumed 陈香兰xlanchen@ustc.edu.cn http:/作taf.u01174O1i:Operating System操作系统原理 March29,20199/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Another solution using counting value A solution to the PC problem that fills all the buffers (not BUFFER_SIZE-1). An integer count: keeps track of the number of full buffers. ▶ Initially, count = 0. ▶ Incremented by the producer after it produces a new buffer, and decremented by the consumer after it consumes a buffer. Producer while (true) { /* produce an item and put in nextProduced */ while (count == BUFFER_SIZE) ; // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++; } Consumer while (true) { while (count == 0) ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count- -; /* consume the item in nextConsumed } 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 9 / 57
Background:Race Condition(竞争条件) count++could be implemented as count--could be implemented as register1 count register2 count register1 register1 +1 register2 register2-1 count register1 count register2 Code Example 0000000000400544: #include #include int count 1234; void main(void){ 400544:55 push %rbp 400545:4889e5mov%rsp,%rbp 400548:4883ec10sub$0x10,%rsp count++; 40054c:8b05d60a2000mov0x200ad6(%rip),%eax#601028 400552:83c001add$0x1,%eax 400555:8905cd0a2000mov%eax,0x200acd(%rip)#601028 Dae 东香兰xlanchen@ustc.edu.cn http:/作taf仟.u011740i:Operating System操作系统原理 March29,201910/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Background: Race Condition(竞争条件) count++ could be implemented as register1 = count register1 = register1 + 1 count = register1 count−− could be implemented as register2 = count register2 = register2 - 1 count = register2 Code Example 0000000000400544 : #include #include int count = 1234; void main(void){ 400544: 55 push %rbp 400545: 48 89 e5 mov %rsp,%rbp 400548: 48 83 ec 10 sub $0x10,%rsp count ++; 40054c: 8b 05 d6 0a 20 00 mov 0x200ad6(%rip),%eax # 601028 400552: 83 c0 01 add $0x1,%eax 400555: 89 05 cd 0a 20 00 mov %eax,0x200acd(%rip) # 601028 ...... 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 10 / 57
Background:Race Condition(竞争条件) count++could be implemented as count--could be implemented as register1 count register2 count register1 register1+1 register2 register2-1 count register1 count=register2 Consider this execution interleaving with "count=5"initially: S0:producer execute register1 count (register1 =5} S1:producer execute register1 register1 1 (register1 6) S2:consumer execute register2 count (register2 5} S3:consumer execute register2 register2-1 (register2 4) S4:producer execute count register1 (count 6} S5:consumer execute count register2 (count 4) Race Condition=A situation: where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access take place 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理 March 29,2019 10/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Background: Race Condition(竞争条件) count++ could be implemented as register1 = count register1 = register1 + 1 count = register1 count−− could be implemented as register2 = count register2 = register2 - 1 count = register2 Consider this execution interleaving with “count = 5” initially: ▶ S0: producer execute register1 = count {register1 = 5} ▶ S1: producer execute register1 = register1 + 1 {register1 = 6} ▶ S2: consumer execute register2 = count {register2 = 5} ▶ S3: consumer execute register2 = register2 - 1 {register2 = 4} ▶ S4: producer execute count = register1 {count = 6 } ▶ S5: consumer execute count = register2 {count = 4} Race Condition≡A situation: where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access take place 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 10 / 57
Outline 2 The Critical-Section Problem(l临界区问题) 口⊙生年12月0C 东香兰xlanchen@ustc,edu.cn http:/staff..u011740i:Operating System操作系统原理 March29,201911/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 2 The Critical-Section Problem (临界区问题) 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 11 / 57
Critical-Section(临界区） 。Critical Resources(l临界资源： 在一段时间内只允许一个进程访问的资源 。Critical Section(CS,临界区)： a segment of code,access and may change shared data(critical resources) Make sure,that any two processes will not execute in its own CSes at the same time o the CS problem is to design a protocol that the processes can use to cooperate. do entry section (each process must request permission to enter its CS) critical section exit section remainder section )while (TRUE) 陈适兰xlanchen@ustc.edu.cn http:/staf.u01174O1:Operating System操作系统原理 March29,201912/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Critical-Section (临界区) Critical Resources(临界资源): 在一段时间内只允许一个进程访问的资源 Critical Section (CS, 临界区): a segment of code, access and may change shared data (critical resources) ▶ Make sure, that any two processes will not execute in its own CSes at the same time the CS problem is to design a protocol that the processes can use to cooperate. do { entry section (each process must request permission to enter its CS) critical section exit section remainder section }while (TRUE) 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 12 / 57