Transcript Week-9

Chapter 5: CPU Scheduling
Operating System Concepts with Java – 8th Edition
5.1
Silberschatz, Galvin and Gagne ©2009
Algorithm Evaluation
 How to compare scheduling algorithms?
 How to determine which is a good algorithm for a
given system
 Deterministic modeling – takes a particular
predetermined workload and defines the
performance of each algorithm for that workload
 Queueing models
 Simulation
Operating System Concepts with Java – 8th Edition
5.2
Silberschatz, Galvin and Gagne ©2009
Evaluation of CPU schedulers by Simulation
Operating System Concepts with Java – 8th Edition
5.3
Silberschatz, Galvin and Gagne ©2009
End of Chapter 5
Operating System Concepts with Java – 8th Edition
5.4
Silberschatz, Galvin and Gagne ©2009
Chapter 6: Process Synchronization
Operating System Concepts with Java – 8th Edition
5.5
Silberschatz, Galvin and Gagne ©2009
Chapter 6: Process Synchronization
 Background
 The Critical-Section Problem
 Peterson’s Solution
 Synchronization Hardware
 Semaphores
 Classic Problems of Synchronization
 Monitors
 Synchronization Examples
 Atomic Transactions
Operating System Concepts with Java – 8th Edition
5.6
Silberschatz, Galvin and Gagne ©2009
Objectives
 To introduce the critical-section problem, whose
solutions can be used to ensure the consistency of
shared data
 To present both software and hardware solutions of
the critical-section problem
 To introduce the concept of an atomic transaction
and describe mechanisms to ensure atomicity
Operating System Concepts with Java – 8th Edition
5.7
Silberschatz, Galvin and Gagne ©2009
Background
 Processes and threads provide
concurrency
 Data sharing among cooperating
processes/threads
 Simultaneous access to shared data
(especially simultaneous writes) lead to
data inconsistency
 Producer/Consumer problem example
Operating System Concepts with Java – 8th Edition
5.8
Silberschatz, Galvin and Gagne ©2009
Producer
while (count == BUFFER.SIZE)
; // do nothing
// add an item to the buffer
buffer[in] = item;
in = (in + 1) % BUFFER.SIZE;
++count;
Operating System Concepts with Java – 8th Edition
5.9
Silberschatz, Galvin and Gagne ©2009
Consumer
while (count == 0)
; // do nothing
// remove an item from the
buffer item = buffer[out];
out = (out + 1) % BUFFER.SIZE;
--count;
Operating System Concepts with Java – 8th Edition
5.10
Silberschatz, Galvin and Gagne ©2009
Race Condition
 count++ can be implemented as
register1 = count
register1 = register1 + 1
count = register1
 count-- can be implemented as
register2 = count
register2 = register2 - 1
count = register2
Operating System Concepts with Java – 8th Edition
5.11
Silberschatz, Galvin and Gagne ©2009
Race Condition (Contd.)
 Consider a scenario with one producer and one consumer

count++ and count-- executed simultaneously
 Count value should remain unaltered
 Execution interleaving with “count = 5” initially:
T0: producer execute register1 = count {register1 = 5}
T1: producer execute register1 = register1 + 1
{register1 = 6}
T2: consumer execute register2 = count {register2 = 5}
T3: consumer execute register2 = register2 - 1
{register2 = 4}
T4: producer execute count = register1 {count = 6 }
T5: consumer execute count = register2 {count = 4}
Operating System Concepts with Java – 8th Edition
5.12
Silberschatz, Galvin and Gagne ©2009
Critical Section
 A conceptual tool to help programmers avoid race




conditions
A section of code where shared memory/resources
(variables, files, tables, etc.) are modified
At most one cooperating process can be in the critical
region at any given point in time
Processes needs to follow a protocol when they modify
shared resources – Critical Section Problem
 Process need to request permission before they enter
critical region
Program structured as “Entry Section”, Critical Section”,
“Exit Section” and “Remainder Section”
Operating System Concepts with Java – 8th Edition
5.13
Silberschatz, Galvin and Gagne ©2009
Structure of a Typical Process
Operating System Concepts with Java – 8th Edition
5.14
Silberschatz, Galvin and Gagne ©2009
Critical Section Solution Requirements
1. Mutual Exclusion - If process Pi is executing in its critical
section, then no other processes can be executing in their
critical sections.
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.
Operating System Concepts with Java – 8th Edition
5.15
Silberschatz, Galvin and Gagne ©2009
Critical Section Solution Assumptions
 Assume that each process executes at a nonzero
speed
 No assumption concerning relative speed of the
N processes
Operating System Concepts with Java – 8th Edition
5.16
Silberschatz, Galvin and Gagne ©2009
Peterson’s Solution
 Two process solution
 Theoretical solution – May not work correctly on modern




architectures
Assume that the LOAD and STORE instructions are atomic; that is,
cannot be interrupted.
The two processes share two variables:
 int turn;
 boolean flag[2]
The variable turn indicates whose turn it is to enter the critical
section.
The flag array is used to indicate if a process is ready to enter the
critical section. flag[i] = true implies that process Pi is ready!
Operating System Concepts with Java – 8th Edition
5.17
Silberschatz, Galvin and Gagne ©2009
Algorithm for Process Pi
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = false;
remainder section
}
Operating System Concepts with Java – 8th Edition
5.18
Silberschatz, Galvin and Gagne ©2009
Peterson’s Solution – Points to Note
 Each process plays the “nice guy”
 Asserts it is the other processes turn to enter
into the critical section
 The infinite wait loop is broken if at least one of
the following holds


The other process is not interested in entering the
critical region
The other process’s write on the “turn” variable
survived (i.e., turn has been set to this process)
Operating System Concepts with Java – 8th Edition
5.19
Silberschatz, Galvin and Gagne ©2009
Peterson’s Solution – Correctness proof
 Mutual exclusion
 Impossible for both processes to break the while loop
simultaneously – Why?
 Progress and bounded wait
 Process Pi can be stuck in the wait loop only if turn
== j and flag[j] == true
 If both conditions hold -- Pj wants to be in critical
region and it has necessary permission to do so
 When Pj exits the critical section it sets flag[j] to false
 Pi enters critical region after at most one entry by Pj
 When Pj is in the remainder region it has no effect on
Pi’s entry into critical region
Operating System Concepts with Java – 8th Edition
5.20
Silberschatz, Galvin and Gagne ©2009
Locks – A Generic Hardware Paradigm
 Critical regions protected by locks
 Processes need to acquire lock before entering CR
 Acquiring and releasing locks are atomic operations
while (true) {
acquire lock
critical section
release lock
remainder section
}
Operating System Concepts with Java – 8th Edition
5.21
Silberschatz, Galvin and Gagne ©2009
Synchronization Hardware
 Modern machines provide special atomic
hardware instructions
 Atomic
mean non-interruptable (i.e., the
instruction executes as one unit)
 getAndSet() -- Test memory word and set its
value
 swap() – exchange the contents of two
memory words
Operating System Concepts with Java – 8th Edition
5.22
Silberschatz, Galvin and Gagne ©2009
Illustration of getAndSet and swap
Operating System Concepts with Java – 8th Edition
5.23
Silberschatz, Galvin and Gagne ©2009
Solution using GetAndSet Instruction
Operating System Concepts with Java – 8th Edition
5.24
Silberschatz, Galvin and Gagne ©2009
Solution using Swap Instruction
Operating System Concepts with Java – 8th Edition
5.25
Silberschatz, Galvin and Gagne ©2009
Semaphore
 Synchronization tool for programmers
 Semaphore S – integer variable
 Two standard operations modify S: acquire() and
release()

Originally called P() (proberen) and V() (verhogen)
 Can only be accessed only via the above atomic
operations
Operating System Concepts with Java – 8th Edition
5.26
Silberschatz, Galvin and Gagne ©2009
Semaphore for Mutual Exclusion
 Binary semaphore – integer value can range only
between 0 and 1

Also known as mutex locks
Operating System Concepts with Java – 8th Edition
5.27
Silberschatz, Galvin and Gagne ©2009
Java Example Using Semaphores
Operating System Concepts with Java – 8th Edition
5.28
Silberschatz, Galvin and Gagne ©2009
Java Example Using Semaphores
Operating System Concepts with Java – 8th Edition
5.29
Silberschatz, Galvin and Gagne ©2009
Semaphore for Imposing Order
 P1 and P2 are concurrently running processes
 S1– Statement in process P1; S2 – Statement in
Process P2
 Ensure that S2 gets executed only after S1
Initialize semaphore synch to 0
Process P1:
Process P2:
S1;
synch.release();
synch.acquire();
S2;
Operating System Concepts with Java – 8th Edition
5.30
Silberschatz, Galvin and Gagne ©2009
Counting Semaphores
 Counting semaphore – integer value can range
over an unrestricted domain
 Controlling access to a resource with finite number
of instances
 Initialize semaphore to # of available instances
 A process wanting to access resource will do an
acquire on the semaphore
 Processes will do a release on the semaphore
after using the resource
 Processes will wait if all available resources are
currently being used
Operating System Concepts with Java – 8th Edition
5.31
Silberschatz, Galvin and Gagne ©2009
Semaphore Implementation
 Must guarantee that no two processes can
execute acquire () and release () on the same
semaphore at the same time
 Disadvantage: Required busy waiting
 Processes
continually wait in the entry code
– another name for this type of
semaphore
 Spinlock
 Wastes
CPU cycles
Operating System Concepts with Java – 8th Edition
5.32
Silberschatz, Galvin and Gagne ©2009