COMP 3000 Operating Systems
Inter-Process Communication and Concurrency (part 2)
Lianying Zhao
No True Shared Memory without Hardware Support
• Example of hardware support: dual-ported RAM? • Still, one port is read-only
• Does not solve our problem
• Ideally:
• The CPU architecture (hardware) provides per-purpose
instructions. One instruction for everything? • In reality:
• We only need a few hardware primitives to facilitate such effort by the OS, e.g., the LOCK prefix (assembly)
COMP 3000 (Winter 2021) 2
Locks
• Since atomicity cannot be directly achieved, we look for mutual exclusion
• Only allow access from one party who holds the “lock” • The lock is just a variable
• How it works:
• Tries to acquired the lock: if free, lock acquired, otherwise, blocked
• When lock acquired, enters the critical section • When done, release the lock
• Apparently, naïve ways wont’ work…
while (lock == 1); lock = 1;
counter = counter + 1; lock = 0;
COMP 3000 (Winter 2021) 3
Lock Implementations
• Mutex (in pthread)
• Mutual exclusion: to ensure only one process/thread is in the critical section
at a time
• Different instances of mutexes can be declared
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; pthread_mutex_lock(&lock);
counter = counter + 1; pthread_mutex_unlock(&lock);
• Spin-wait vs. sleep
• Spin-waiting is very inefficient
• What about waiting for a condition?
COMP 3000 (Winter 2021) 4
Condition Variables
• Also a primitive from the POSIX threads (pthread) • for signaling of a certain condition
• pthread_cond_wait()and pthread_cond_signal() • Must be used with a lock (mutex)
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t cond = PTHREAD_COND_INITIALIZER; pthread_mutex_lock(&lock);
while (ready == 0)
pthread_cond_wait(&cond, &lock); pthread_mutex_unlock(&lock);
COMP 3000 (Winter 2021) 5
Semaphores
• Generalizing locks (mutex) and condition variables • It’s also a variable
• Binary semaphore • Mutex!
• Reflects how many parties are waiting, if negative • sem_wait() and sem_post()
• Whether to wait: not greater than or equal to 0
• Some care for the initial value
• To make a mutex: set it to 1
• To make a condition variable: set it to 0
COMP 3000 (Winter 2021) 6
Deadlocks
• Two or more processes/threads waiting on each other, forever…
• Example:
• Process A holds lock 1, waiting to acquire lock 2 • Process B holds lock 2, waiting to acquire lock 1
• Deadlocks are one consequence of concurrency issues
• Execution is not making progress
• Another one is logic/data corruption
• Trying to avoid one not carefully enough can lead to the other
COMP 3000 (Winter 2021) 7
Necessary Conditions for Deadlock
1. Mutual exclusion 2. Hold-and-wait
3. No pre-emption
4. Circular wait
• Not necessarily caused by using synchronization mechanisms like mutex or semaphore
• Timeout is a way out, inelegant, but works
COMP 3000 (Winter 2021) 8
The Dining Philosopher’s Problem
• Five philosophers, five forks (chopsticks?)
• Each philosopher may think or eat at a
given time
• Two forks are needed
• Goals:
• Nobody starves
• No deadlock
• High concurrency
• Question: how to grab and put forks? COMP 3000 (Winter 2021)
Source: Wikipedia 9
The Producer/Consumer Problem
• AKA: the bounded buffer problem
• A more common scenario, e.g., cat sample.txt | wc -l
• The producer produces items, to be placed to the buffer • If full, just wait
• The consumer consumes items, from the buffer • If empty, just wait
• The buffer has a fixed length
• The goals are the same: no deadlock and high concurrency
COMP 3000 (Winter 2021) 10