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<main>: #include <stdio.h> #include <unistd.h> int count 1234; void main(void){ 400544:55 push %rbp 400545:4889e5mov%rsp,%rbp 400548:4883ec10sub$0x10,%rsp count++; 40054c:8b05d60a2000mov0x200ad6(%rip),%eax#601028<count> 400552:83c001add$0x1,%eax 400555:8905cd0a2000mov%eax,0x200acd(%rip)#601028<count:> 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 <main>: #include <stdio.h> #include <unistd.h> 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 <count> 400552: 83 c0 01 add $0x1,%eax 400555: 89 05 cd 0a 20 00 mov %eax,0x200acd(%rip) # 601028 <count> ...... 陈香兰 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