程序代写 COMP30023 – Computer Systems

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