代写代考 COMP30023 – Computer Systems

COMP30023 – Computer Systems
Operating systems:
Process communication

• Inter process communication
• Process scheduling
© University of Melbourne

• Processes
• Threads: share and execute in the address
space of the same process • Interrupts
© University of Melbourne

Interprocess communication
• Whyconcurrency:increaseefficiency(parallelism) through cooperation
• Exchangeinformationbetweenprocesses/threads
• Concerns:
– Processes can interfere with each other – Proper sequencing and order
• Ensuresystemintegrityandpredictablebehavior
© University of Melbourne

Race condition
• Setting:multipleprocesseshaveaccesstoshared object (e.g., memory or file)
• Allcanreadandwriteit
• Raceconditionariseswhenoutputdependsonthe
order of operations • Veryhardtodebug
Process 1 Process 2
Shared memory
© 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… }
Potential execution transcript
1. process A tests stack.isEmpty() ⇒ false
2. process A pops ⇒ stack is now empty
3. process B tests stack.isEmpty() ⇒
4. process B just returns – nothing to do
© University of Melbourne

Race condition example
Pseudo code for popping from a stack. stack // global shared variable
Another potential
execution transcript
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?
© University of Melbourne

Critical regions (1)
• Howtopreventraceconditions? – finding them later is hard
• Idea:prohibitaccesstosharedobjectatthesame time
• Mutualexclusion:manydesignchoices
• Identifycriticalregion/sectionoftheprogram
© University of Melbourne

Critical regions (2)
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 (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
© University of Melbourne

Lock variable problem
Shared variable: lock
while (lock != 0) {# wait} lock = 1
critical_region()
© University of Melbourne

Lock variable problem
Shared variable: lock
while (lock != 0) {# wait} lock = 1
critical_region()
Interrupt occurs
© University of Melbourne

Techniques for Avoiding Race Conditions
• Disabling Interrupts
• Strict Alternation
• Test and Set Lock
• Sleep and Wakeup
• Other: Semaphores, Monitors,
• Message passing
Implementation: • Busy Waiting • Blocking
© University of Melbourne

Strict Alternation with Busy Waiting
© University of Melbourne

Test and Set Lock (TSL)
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
Atomic operation
RX can be used to decide whether to enter critical region or not: Compare RX and LOCK
© University of Melbourne

Busy Waiting
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

– 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

Lock(M1) DoWork(…) Lock(M2) DoWork(…) Release_lock(M1) Release_lock(M2)
Lock(M2) DoWork(…) Lock(M1) DoWork(…) Release_lock(M2) Release_lock(M1)
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

Dealing with deadlocks
1. Ignoretheproblem
2. Detection(e.g.,graphalgorithms)and recovery
3. Avoidbycarefulresourceallocation
4. Prevention
Resource allocation graph:
© University of Melbourne

Summary: Process Communication
• Race conditions
• Critical region
• Techniques to ensure mutual exclusion • Deadlock
© University of Melbourne

Acknowledgement
• 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
© University of Melbourne

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts