《操作系统》课程教学资源（PPT课件）第七章 Process Synchronization

Module 7: Process Synchronization Background(背景) ° The critica|- Section Problen(临界区问题) ° Synchronization Hardware(同步的硬件实现) Semaphores(信号量) Classical Problems of Synchronization(经典同步问题) Monito(管程) Java Synchronization(Jawa中的同步机制) · Synchronization in Solaris2( Solaris2的同步机制) ° Synchronization in Windows NT( Windows nt的同步机制) Applied Operating System Concepts Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.1 Applied Operating System Concepts Module 7: Process Synchronization • Background（背景） • The Critical-Section Problem （临界区问题） • Synchronization Hardware （同步的硬件实现） • Semaphores （信号量） • Classical Problems of Synchronization（经典同步问题） • Monitors （管程） • Java Synchronization （Java中的同步机制） • Synchronization in Solaris 2 （Solaris 2的同步机制） • Synchronization in Windows NT （Windows NT的同步机制）

Background e Concurrent access to shared data may result in data inconsistency(对共享数据的并发访问可能导致数据的不一致性) Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes(要保持数据的 一致性,就需要一种保证并发进程的正确执行顺序的机制) Shared-memory solution to bounded-butter problem(Chapter 4) has a race condition on the class data count([第4章中]解决 有界缓冲区问题的共享内存方法在类数据 count上将一起竞争条件) Applied Operating System Concepts Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.2 Applied Operating System Concepts Background • Concurrent access to shared data may result in data inconsistency（对共享数据的并发访问可能导致数据的不一致性）. • Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes（要保持数据的 一致性，就需要一种保证并发进程的正确执行顺序的机制）. • Shared-memory solution to bounded-butter problem (Chapter 4) has a race condition on the class data count （[第4章中]解决 有界缓冲区问题的共享内存方法在类数据count 上将一起竞争条件）

Bounded Buffer public class Bounded Buffer( public void enter(object item) l/ producer calls this method public Object remove i l/ consumer calls this method l potential race condition on count private volatile int coun Applied Operating System Concepts Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.3 Applied Operating System Concepts Bounded Buffer public class BoundedBuffer { public void enter(Object item) { // producer calls this method } public Object remove() { // consumer calls this method } // potential race condition on count private volatile int count; }

enter( Method l/ producer calls this method public void enter(object item)i while(count== BUFFER SIZE ;∥ do nothing l/ add an item to the buffer ++count buffer[in]= item; in=(in+ 1)% BUFFER_SIzE, Applied Operating System Concepts 74 Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.4 Applied Operating System Concepts enter() Method // producer calls this method public void enter(Object item) { while (count == BUFFER_SIZE) ; // do nothing // add an item to the buffer ++count; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; }

remove( Method l/ consumer calls this method public object remove i Object item while(count ==0) ;∥ do nothing l/ remove an item from the buffer cou item= buffer[out] out=(out 1)% BUFFER SIZE, return item Applied Operating System Concepts Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.5 Applied Operating System Concepts remove() Method // consumer calls this method public Object remove() { Object item; while (count == 0) ; // do nothing // remove an item from the buffer --count; item = buffer[out]; out = (out + 1) % BUFFER_SIZE; return item; }

Solution to Critical-section Problem 1. Mutual Exclusion. If process Pi is executing in its critical section, then no other processes can be executing in their critical sections(互斥。假定 进程P在其临界区内执行,其他任何进程将被排斥在自己的临界区之外) 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(有空让进。临界区虽没有进程执行,但有些进程 需要进入临界区,不能无限期地延长下一个要进入临界区进程的等待时间 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 (X0 任何关于这n个进程相对执行速率的假定) Applied Operating System Concepts 76 Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.6 Applied Operating System Concepts Solution to Critical-Section Problem 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（有空让进。临界区虽没有进程执行，但有些进程 需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间 ）. 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个进程相对执行速率的假定）

Worker Thread public class Worker extends Thread i public Worker(String n, int i, MutualEXclusion s)i name n d shared =s public void run(( /*see next slide */y private String name; private int id private MutualEXclusion shared Applied Operating System Concepts 7.7 Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.7 Applied Operating System Concepts Worker Thread public class Worker extends Thread { public Worker(String n, int i, MutualExclusion s) { name = n; id = i; shared = s; } public void run() { /* see next slide */ } private String name; private int id; private MutualExclusion shared; }

runo Method of Worker Thread public void runo i while(true)i shared entering Critical Section(id) l/ in critical section code shared. leaving CriticalSection(id) l/ out of critical section code Applied Operating System Concepts 78 Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.8 Applied Operating System Concepts run() Method of Worker Thread public void run() { while (true) { shared.enteringCriticalSection(id); // in critical section code shared.leavingCriticalSection(id); // out of critical section code } }

MutualExclusion Abstract class public abstract class MutualExclusion i public static void criticalSectiono t l simulate the critical section public static void non CriticalSectiono i l simulate the non -critical section public abstract void entering CriticalSection(int t; public abstract void leav ing criticalSection(int t; public static final int TURN 0=0; public static final int TURN 1=1; Applied Operating System Concepts Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.9 Applied Operating System Concepts MutualExclusion Abstract Class public abstract class MutualExclusion { public static void criticalSection() { // simulate the critical section } public static void nonCriticalSection() { // simulate the non-critical section } public abstract void enteringCriticalSection(int t); public abstract void leavingCriticalSection(int t); public static final int TURN_0 = 0; public static final int TURN_1 = 1; }

Testing Each Algorithm public class TestAlgorithm public static void main (String args MutualExclusion alg= new Algorithm_10 Worker first new Worker("Runner, 0, alg): Worker second new Worker ("Runner 1", 1, alg) first start secondstart Applied Operating System Concepts 7.10 Silberschatz, GalVin, and Gagne @1999

Silberschatz, Galvin, and Gagne ©1999 7.10 Applied Operating System Concepts Testing Each Algorithm public class TestAlgorithm { public static void main(String args[]) { MutualExclusion alg = new Algorithm_1(); Worker first = new Worker("Runner 0", 0, alg); Worker second = new Worker("Runner 1", 1, alg); first.start(); second.start(); } }