COMP30023 – Computer Systems
© University of Melbourne
Copyright By PowCoder代写 加微信 powcoder
Operating systems:
Process communication
• Inter process communication
• Process scheduling
© University of Melbourne 2
• Processes
• Threads: share and execute in the address
space of the same process
• Interrupts
© University of Melbourne
• Why concurrency: increase efficiency (parallelism)
through cooperation
• Exchange information between processes/threads
• Concerns:
– Processes can interfere with each other
– Proper sequencing and order
• Ensure system integrity and predictable behavior
© University of Melbourne
Interprocess communication
• Setting: multiple processes have access to shared
object (e.g., memory or file)
• All can read and write it
• Race condition arises when output depends on the
order of operations
• Very hard to debug
© University of Melbourne
Race condition
© University of Melbourne
Race condition example
Pseudo code for popping from a stack.
stack // global shared variable
void my_stack_function() {
if (isEmpty(stack)) return;
int s = pop(stack);
//do something with s…
© University of Melbourne
Race condition example
Pseudo code for popping from a stack.
stack // global shared variable
void my_stack_function() {
if (isEmpty(stack)) return;
int s = pop(stack);
//do something with s…
Processes A and B
© University of Melbourne
Race condition example
Pseudo code for popping from a stack.
stack // global shared variable
void my_stack_function() {
if (isEmpty(stack)) return;
int s = pop(stack);
//do something with s…
1. process A tests stack.isEmpty() ⇒
2. process A pops ⇒ stack is now empty
3. process B tests stack.isEmpty() ⇒
4. process B just returns – nothing to do
Potential execution transcript
© University of Melbourne
Race condition example
Pseudo code for popping from a stack.
stack // global shared variable
void my_stack_function() {
if (isEmpty(stack)) return;
int s = pop(stack);
//do something with s…
1. process A tests stack.isEmpty() ⇒
2. process B tests stack.isEmpty() ⇒
3. process A pops ⇒ stack is now
4. process B pops – Exception?
Another potential
execution transcript
• How to prevent race conditions?
– finding them later is hard
• Idea: prohibit access to shared object at the same
• Mutual exclusion: many design choices
• Identify critical region/section of the program
© University of Melbourne
Critical regions (1)
Requirements to avoid race conditions:
1. No two processes may be simultaneously inside their
critical regions.
2. No assumptions may be made about speeds or the
number of CPUs.
3. No process running outside its critical region may
block other processes.
4. No process should have to wait forever to enter its
critical region.
© University of Melbourne
Critical regions (2)
© University of Melbourne
Critical regions (3)
Figure 2-22. Mutual exclusion using critical regions.
© University of Melbourne
Critical region example
Pseudo code for popping from a stack.
stack // global shared variable
void my_stack_function() {
if (isEmpty(stack)) return;
int s = pop(stack);
//do something with s…
Put this code in critical region
Shared variable: lock
while (lock != 0) {# wait}
critical_region()
© University of Melbourne
Lock variable problem
Shared variable: lock
while (lock != 0) {# wait}
critical_region()
© University of Melbourne
Lock variable problem
Interrupt occurs
• Disabling Interrupts
• Strict Alternation
• Test and Set Lock
• Sleep and Wakeup
• Other: Semaphores, Monitors,
• Message passing
© University of Melbourne
Techniques for Avoiding Race
Conditions
Implementation:
• Busy Waiting
• Blocking
© University of Melbourne
Strict Alternation with Busy
Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
turn=1Thread A Thread B
Most CPUs come with a test and set lock instruction
TSL RX, LOCK
Set RX to LOCK
Test LOCK, if it is 0, set LOCK to 1
RX can be used to decide whether to enter critical region or not:
Compare RX and LOCK
© University of Melbourne
Test and Set Lock (TSL)
Atomic operation
When a process wants to enter a critical section
• it checks if the entry is allowed
• If not, the process executes a loop, checking if it is
allowed to enter a critical section
• Waste of CPU
• Priority Inversion Problem
– Low and high priority processes
– Low priority process may starve -> High priority
process is blocked by a lower lower priority process
© University of Melbourne
Busy Waiting
– Attempt to enter a critical section
– If critical section available, enter it
– If not, register interest in the critical section and block
– When the critical section becomes available, the OS
will unblock a process waiting for the critical section, if
one exists
Example: Sleep() and Wakeup()
Using blocking constructs improves the CPU utilization
© University of Melbourne
Deadlock: A set of processes is deadlocked if each process in
the set is waiting for an event that only another process in the
set can cause
May exist in many shared resource settings; not just memory
© University of Melbourne
Release_lock(M1)
Release_lock(M2)
Release_lock(M2)
Release_lock(M1)
Process A Process B
Deadlock: A set of processes is deadlocked if each process in
the set is waiting for an event that only another process in the
set can cause
May exist in many shared resource settings; not just memory
© University of Melbourne
Process A Process B
Release_lock(M1)
Release_lock(M2)
Release_lock(M2)
Release_lock(M1)
1. Ignore the problem
2. Detection (e.g., graph algorithms) and
3. Avoid by careful resource allocation
4. Prevention
© University of Melbourne
Dealing with deadlocks
Resource allocation graph:
• Race conditions
• Critical region
• Techniques to ensure mutual exclusion
• Deadlock
© University of Melbourne
Summary: Process Communication
• The slides were prepared by .
• Some of the images included in the notes were supplied as
part of the teaching resources accompanying the text books
listed in lecture 1.
• Reference: TB 2.3, 6.2.2
Acknowledgement
© University of Melbourne 50
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com