Recap

• processes need to be able to communicate with each other
• shared memory
• message passing
• remote procedure calls

Remote Procedure Calls (RPC)

• abstract procedure calls between processes on networked systems
• RPC calls can fail, be duplicated due to network errors
  • server side must keep timestamps, request history
  • server side must acknowledge all RPCs
  • client resends unacknowledges RPCs

Race Condition

• two or more processes read / write shared data
  • state of variable after race condition unclear

Critical Region

• region in program where shared memory is accessed

Avoiding Race Conditions

• only one process executes critical region at one time
• make no assumption about speed of CPUs
• no process outside critial region blocks other process
• no process waits forever to enter critical region

Disabling Interrups

• process disables its interrupts during its critical region
• no other process can be scheduled to run while process is in critical region
• (-) issues persist on multi processor CPUs

Lock Variables

• single shared variable for coordination
• init: lock = 0
• process enters critical region -> set lock = 1
• process leaves critical region -> set lock = 0
• (-) race condition in setting lock possible

Process Alternation

• shared variable turn indicates which process can enter its critical region
• init: turn = 0
• turn = 1 only for 1 process at one time
• (-) fast processe my wait very long for slow ones

Peterson's Solution

• shared variable turn indicates which process can enter its critical region
• flag array keeps track of processes ready to enter
• process enters critical region if turn == 0 or flag from the other process == 0

Using Atomic Instructions

• atomic instructions are used to ensure that the instruction is completed without interference
• Atomically load LOCK Variable and set it to 1 => No other process is allowed to use access its critical section
• after the critical section is finished a set LOCK to 0 with a normal instruction

Avoiding Busy Waiting

• Busy waiting wastes resources => Block process if it has to wait done with sleep and wakeup syscalls

Semaphore Operations

• down: checks the semaphore value
  • value > 0 : decrement, continue
  • value == 0 : put process to sleep, down operatoin remains pending
• up increments semaphore value
  • 1 > #processes are sleeping
    • wake up one process to execute its down operation

Mutual Exclusion Locks (MUTEX)

• simplified version of semaphore
• tow states: locked, unlocked
• mutex_lock enters critical region, and blocks all other processes for entering their critical region
• mutex_unlock:
• mutex_trylock: test mutex without blocking

Condition Variables

• ensures that processes are only proceeding when they should
• can block a process until some condition is met
• wait: a process can call this on a condition to block itself until another process allows sets the condition to true
• signal: used to wake up a blocked process
• if multiple processes are waiting: one is woken up (random)

Monitor

• collectoin of preocedures, variables and data structures to make it easier to write programs requiring mutual exclusion
• monitors are a programming-language-level construct
• processes can use monitors but not directly access internal data structures
• onyl one process at a time can be active within the monitor
• implemented by the compiler with mutex oder semaphore