Requirements for Mutual Exclusion(互斥)(P196) Mutual exclusion must be enforced o a process that halts in its noncritical section must do so without interfering with other processes It must not be possible for a process requiring access to a critical section to be delayed indefinitely ROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Requirements for Mutual Exclusion (互斥)(P196） ❖ Mutual exclusion must be enforced. ❖ A process that halts in its noncritical section must do so without interfering with other processes. ❖ It must not be possible for a process requiring access to a critical section to be delayed indefinitely
Requirements for Mutual exclusion o When no process is in a critical section, any process that requests entry to its critical section must be permitted to enter without delay. No assumptions are made about relative process speeds or number of processors. a process remains inside its critical section for a finite time only. PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Requirements for Mutual Exclusion ❖ When no process is in a critical section, any process that requests entry to its critical section must be permitted to enter without delay. ❖ No assumptions are made about relative process speeds or number of processors. ❖ A process remains inside its critical section for a finite time only
Mutual Exclusion: Software Approaches ☆ Dekker’ S Algorithm ☆ Peterson's algorithn PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Mutual Exclusion: Software Approaches ❖Dekker’s Algorithm ❖Peterson’s Algorithm
Dekker's algorithm--First Attempt Fig 5.2 An gloo for mutual exclusion The entrance and the igloo itself are small enough that only one person can be in the igloo at a time. Inside, there is a blackboard on which a single value can be written a process wishing to execute its critical section first enters the igloo and examines the blackboard. PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm—First Attempt ❖ Fig 5.2 An Igloo for Mutual Exclusion ٭ The entrance and the igloo itself are small enough that only one person can be in the igloo at a time. Inside, there is a blackboard on which a single value can be written. ٭ A process wishing to execute its critical section first enters the igloo and examines the blackboard
Dekker,s algorithm -First Attempt If its number is on the blackboard, then the process may leave the igloo and proceed to its critical section. After has completed the critical section, it should place the number of the other process on the board .8 If not its number, it leaves the igloo and is forced to wait From time to time, the process reenters the igloo to check the blackboard until it is alllowed to enter its critical section(busy waiting PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm —First Attempt ❖ If its number is on the blackboard, then the process may leave the igloo and proceed to its critical section. After has completed the critical section, it should place the number of the other process on the board ❖ If not its number, it leaves the igloo and is forced to wait. From time to time, the process reenters the igloo to check the blackboard until it is allowed to enter its critical section. (busy waiting)