程序代写案例-COMP30023
时间:2022-04-06
COMP30023 – Computer Systems
© University of Melbourne
Operating systems:
Process communication
Olya Ohrimenko
• Inter process communication
• Process scheduling
Today
© University of Melbourne 2
• Processes
• Threads: share and execute in the address
space of the same process
• Interrupts
© University of Melbourne
Recap
3
• Why concurrency: increase efficiency (parallelism)
through cooperation
• Exchange information between processes/threads
• Concerns:
– How?
– Processes can interfere with each other
– Proper sequencing and order
• Ensure system integrity and predictable behavior
© University of Melbourne
Interprocess communication
4
• 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
Process 1
Process 2
Process N
Shared
memory
…..
5
© 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...
}
6
© 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...
}
7
A B
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() ⇒
false
2. process A pops ⇒ stack is now empty
3. process B tests stack.isEmpty() ⇒
true
4. process B just returns – nothing to do
8
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() ⇒
false
2. process B tests stack.isEmpty() ⇒
false
3. process A pops ⇒ stack is now
empty
4. process B pops – Exception?
9
Another potential
execution transcript
• How to prevent race conditions?
– finding them later is hard
• Idea: prohibit access to shared object at the same
time
• Mutual exclusion: many design choices
• Identify critical region/section of the program
© University of Melbourne
Critical regions (1)
10
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)
11
© University of Melbourne
Critical regions (3)
Figure 2-22. Mutual exclusion using critical regions.
12
© 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
13
Shared variable: lock
while (lock != 0) {# wait}lock = 1critical_region()lock = 0
© University of Melbourne
Lock variable problem
14
Shared variable: lock
while (lock != 0) {# wait}lock = 1critical_region()lock = 0
© University of Melbourne
Lock variable problem
Interrupt occurs
15
Methods:
• 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
16
© University of Melbourne
Strict Alternation with Busy
Waiting
17
Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
turn=0
18
Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
19
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
20
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
21
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
22
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
23
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
24
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
25
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
26
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
27
turn=0Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
28
turn=1Thread A Thread B
© University of Melbourne
Strict Alternation with Busy
Waiting
29
turn=1Thread A Thread B
Most CPUs come with a test and set lock instructionTSL 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
43
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
Cons:
• 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
44
Approach
– 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
Blocking
45
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
Deadlocks
Lock(M1)
DoWork(…)
Lock(M2)
DoWork(…)
Release_lock(M1)
Release_lock(M2)
Lock(M2)
DoWork(…)
Lock(M1)
DoWork(…)
Release_lock(M2)
Release_lock(M1)
Process A Process B
46
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
Deadlocks
Process A Process B
Lock(M1)
DoWork(…)
Lock(M2)
DoWork(…)
Release_lock(M1)
Release_lock(M2)
Lock(M2)
DoWork(…)
Lock(M1)
DoWork(…)
Release_lock(M2)
Release_lock(M1)
47
1. Ignore the problem
2. Detection (e.g., graph algorithms) and
recovery
3. Avoid by careful resource allocation
4. Prevention
© University of Melbourne
Dealing with deadlocks
M1 M2
Process A
Process B
48
Resource allocation graph:
• Race conditions
• Critical region
• Techniques to ensure mutual exclusion
• Deadlock
© University of Melbourne
Summary: Process Communication
49
• The slides were prepared by Olya Ohrimenko.
• 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
essay、essay代写