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