上海交通大学：《操作系统 Operating System》课程教学资源（课件讲稿）OS-Process Synchronization_Lec13

OPERATING SYSTEMS 1 龚玲 lgong@sjtu.edu.cn

OPERATING SYSTEMS 龚玲 lgong@sjtu.edu.cn 1

Chapter 6:Process Synchronization

Chapter 6: Process Synchronization

REVIEW o Background o The Critical-Section Problem o Peterson's Solution o synchronization Hardware o http://wenku.baidu.com/course/study/77fldcccda38376ba flfae94#665ea0c7aa00b52acfc7ca94

REVIEW  Background  The Critical-Section Problem  Peterson’s Solution  Synchronization Hardware  http://wenku.baidu.com/course/study/77f1dcccda38376ba f1fae94#665ea0c7aa00b52acfc7ca94

Goals for today o Semaphores o Classic Problems of Synchronization o Monitors

Goals for today  Semaphores  Classic Problems of Synchronization  Monitors

Race condition oSeveral processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place

Race condition Several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place

Cooperation o Problems with software solutions: Difficult to program and to verify Processes loop while waiting(busy-wait) Applicable to only to critical problem:Competition for a resource o Cooperating processes must also synchronize 6

Cooperation  Problems with software solutions:  Difficult to program and to verify  Processes loop while waiting (busy-wait)  Applicable to only to critical problem: Competition for a resource  Cooperating processes must also synchronize 6

Semaphore o Synchronization tool that does not require busy waiting o Semaphore S-integer variable o Two standard operations modify S:acquire0 and release( Originally called PO and VO o Less complicated o Can only be accessed via two indivisible(atomic)operations acquire(){ while value <=0 ;/no-op value--; release(){ value++;

Semaphore  Synchronization tool that does not require busy waiting  Semaphore S – integer variable  Two standard operations modify S: acquire() and release()  Originally called P() and V()  Less complicated  Can only be accessed via two indivisible (atomic) operations

Atomic Operations o To understand a concurrent program,we need to know what the underlying indivisible operations are! o Atomic Operation:an operation that always runs to completion or not at all It is indivisible:it cannot be stopped in the middle and state cannot be modified by someone else in the middle Fundamental building block-if no atomic operations,then have no way for threads to work together On most machines,memory references and assignments (i.e. loads and stores)of words are atomic o Many instructions are not atomic Double-precision floating point store often not atomic VAX and IBM 360 had an instruction to copy a whole array

Atomic Operations  To understand a concurrent program, we need to know what the underlying indivisible operations are!  Atomic Operation: an operation that always runs to completion or not at all  It is indivisible: it cannot be stopped in the middle and state cannot be modified by someone else in the middle  Fundamental building block – if no atomic operations, then have no way for threads to work together  On most machines, memory references and assignments (i.e. loads and stores) of words are atomic  Many instructions are not atomic  Double-precision floating point store often not atomic  VAX and IBM 360 had an instruction to copy a whole array

Semaphore as General Synchronization Tool o Counting semaphore-integer value can range over an unrestricted domain o Binary semaphore-integer value can range only between 0 and 1;can be simpler to implement Also known as mutex locks Semaphore S=new Semaphore(); S.acquire(); /critical section S.release(); /∥remainder section

Semaphore as General Synchronization Tool  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  Also known as mutex locks

Semaphore Implementation o Must guarantee that no two processes can execute acquire and release on the same semaphore at the same time o Thus,implementation becomes the critical section problem where the wait and signal code are placed in the critical section. Could now have busy waiting in critical section implementation oBut implementation code is short oLittle busy waiting if critical section rarely occupied Note that applications may spend lots of time in critical sections and therefore this is not a good solution

Semaphore Implementation  Must guarantee that no two processes can execute acquire () and release () on the same semaphore at the same time  Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section.  Could now have busy waiting in critical section implementation But implementation code is short Little busy waiting if critical section rarely occupied  Note that applications may spend lots of time in critical sections and therefore this is not a good solution