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(); } }