Concurrency and Synchronisation
1
Learning Outcomes
• Understand concurrency is an issue in operating systems and multithreaded applications
• Know the concept of a critical region.
• Understand how mutual exclusion of critical regions can be used to solve concurrency issues
• Including how mutual exclusion can be implemented correctly and efficiently.
• Be able to identify and solve a producer consumer bounded buffer problem.
• Understand and apply standard synchronisation primitives to solve synchronisation problems.
2
Textbook
• Sections 2.3 – 2.3.7 & 2.5
3
Concurrency Example
count is a global variable shared between two threads.
After increment and decrement complete, what is the value of count?
void increment () void decrement () {{
int t;
}}
We have a
race condition
int t;
t = count;
t = t + 1;
count = t;
t = count;
t = t – 1;
count = t;
4
Where is the concurrency?
• (a) Three processes each with one thread • (b) One process with three threads
There is in-kernel concurrency even for single-
threaded processes
Process’s user-level stack and execution state
User Mode
Process A Process B Process C Operating System
Kernel Mode
Process’s in-kernel stack and execution state
Critical Region
• We can control access to the shared resource by controlling access to the code that accesses the resource.
A critical region is a region of code where shared resources are accessed.
• Variables, memory, files, etc…
• Uncoordinated entry to the critical region results in a race condition
Incorrect behaviour, deadlock, lost work,…
7
Identifying critical regions
• Critical regions are regions of code that:
• Access a shared resource,
• and correctness relies on the shared resource not being concurrently modified by another thread/process/entity.
void increment () void decrement () {{
int t;
t = count;
t = t + 1;
count = t;
}}
int t;
t = count;
t = t – 1;
count = t;
8
Accessing Critical Regions
Mutual exclusion using critical regions
9
Example critical regions
struct node {
int data;
struct node *next;
};
struct node *head;
void insert(struct *item)
{
item->next = head;
head = item; }
void init(void) {{
head = NULL; }
• Simple last-in-first-out queue implemented as a linked list.
struct node *remove(void)
struct node *t;
t = head;
if (t != NULL) {
head = head->next;
}
return t; }
10
Example Race
void insert(struct *item)
{
item->next = head;
head = item; }
void insert(struct *item)
{
item->next = head;
head = item; }
11
Example critical regions
struct node {
int data;
struct node *next;
};
struct node *head;
void insert(struct *item)
{
item->next = head;
head = item; }
void init(void) {{
head = NULL;
• Critical sections
struct node *remove(void)
struct node *t;
return t; }
}
t = head;
if (t != NULL) {
head = head->next;
}
12
Critical Regions Solutions
• We seek a solution to coordinate access to critical regions.
• Also called critical sections
• Conditions required of any solution to the critical region problem
1. Mutual Exclusion:
• No two processes simultaneously in critical region
2. No assumptions made about speeds or numbers of CPUs 3. Progress
• No process running outside its critical region may block another process 4. Bounded
• No process waits forever to enter its critical region
13
A solution? • A lock variable
• If lock == 1,
• somebody is in the critical section and we must wait
• If lock == 0,
• nobody is in the critical section and we are free to enter
14
A solution?
while(TRUE) {
while(lock == 1);
lock = 1;
critical();
lock = 0
non_critical();
while(TRUE) {
while(lock == 1);
lock = 1;
critical();
lock = 0
non_critical();
}}
15
A problematic execution sequence
while(TRUE) {
while(lock == 1);
lock = 1;
critical();
lock = 0
non_critical();
while(TRUE) {
while(lock == 1);
lock = 1;
critical();
lock = 0
non_critical();
}
16
}
Observation
• Unfortunately, it is usually easier to show something does not work, than it is to prove that it does work.
• Easier to provide a counter example
• Ideally, we’d like to prove, or at least informally demonstrate, that our solutions work.
17
Mutual Exclusion by Taking Turns
Proposed solution to critical region problem (a) Process 0. (b) Process 1.
18
Mutual Exclusion by Taking Turns • Works due to strict alternation
• Each process takes turns
• Cons
• Busy waiting
• Process must wait its turn even while the other process is doing something else.
• With many processes, must wait for everyone to have a turn • Does not guarantee progress if a process no longer needs a turn.
• Poor solution when processes require the critical section at differing rates
19
Mutual Exclusion by Disabling Interrupts
• Before entering a critical region, disable interrupts
• After leaving the critical region, enable interrupts
• Pros
• simple
• Cons
• Only available in the kernel
• Blocks everybody else, even with no contention • Slows interrupt response time
• Does not work on a multiprocessor
20
Hardware Support for mutual exclusion • Test and set instruction
• Can be used to implement lock variables correctly • It loads the value of the lock
• If lock == 0,
• set the lock to 1
• return the result 0 – we acquire the lock • Iflock==1
• return 1 – another thread/process has the lock
• Hardware guarantees that the instruction executes atomically.
• Atomically: As an indivisible unit.
21
Mutual Exclusion with Test-and-Set
Entering and leaving a critical region using the TSL instruction
22
Test-and-Set
• Pros
• Simple (easy to show it’s correct)
• Available at user-level
• To any number of processors
• To implement any number of lock variables
• Cons
• Busy waits (also termed a spin lock)
• Consumes CPU
• Starvation is possible when a process leaves its critical section and more than one process is waiting.
23
Tackling the Busy-Wait Problem • Sleep / Wakeup
• The idea
• When process is waiting for an event, it calls sleep to block, instead of
busy waiting.
• The event happens, the event generator (another process) calls wakeup to unblock the sleeping process.
• Waking a ready/running process has no effect.
24
The Producer-Consumer Problem
• Also called the bounded buffer problem
• A producer produces data items and stores the items in a buffer
• A consumer takes the items out of the buffer and consumes them.
Producer
X
X
X
Consumer
25
Issues
• We must keep an accurate count of items in buffer
• Producer
• should sleep when the buffer is full,
• and wakeup when there is empty space in the buffer
• The consumer can call wakeup when it consumes the first entry of the full buffer • Consumer
• should sleep when the buffer is empty
• and wake up when there are items available
• Producer can call wakeup when it adds the first item to the buffer
Producer
X
X
X
Consumer
26
Pseudo-code for producer and consumer
int count = 0;
#define N 4 /* buf size */
prod() {
while(TRUE) {
item = produce()
if (count == N)
con() {
while(TRUE) {
if (count == 0)
sleep();
remove_item();
count–;
if (count == N-1)
} }
sleep();
insert_item();
count++;
if (count == 1)
wakeup(con);
wakeup(prod);
} }
27
Problems
int count = 0;
#define N 4 /* buf size */
prod() {
while(TRUE) {
item = produce()
if (count == N)
con() {
while(TRUE) {
if (count == 0)
sleep();
remove_item();
count–;
if (count == N-1)
} }
sleep();
insert_item();
count++;
if (count == 1)
wakeup(con);
} }
wakeup(prod);
Concurrent uncontrolled access to the buffer
28
Problems
int count = 0;
#define N 4 /* buf size */
prod() {
while(TRUE) {
item = produce()
if (count == N)
con() {
while(TRUE) {
if (count == 0)
sleep();
remove_item();
count–;
if (count == N-1)
} }
sleep();
insert_item();
count++;
if (count == 1)
wakeup(con);
} }
wakeup(prod);
Concurrent uncontrolled access to the counter
29
Proposed Solution
• Lets use a locking primitive based on test-and-set to protect the concurrent access
30
Proposed solution?
int count = 0;
#define N 4 /* buf size */ prod() {
while(TRUE) {
item = produce()
if (count == N)
sleep();
acquire_lock()
insert_item();
count++;
release_lock()
if (count == 1)
con() {
while(TRUE) {
if (count == 0)
sleep();
acquire_lock()
remove_item();
count–;
release_lock();
if (count == N-1)
} }
wakeup(prod);
wakeup(con);
} }
31
Problematic execution sequence
prod() {
while(TRUE) {
item = produce()
if (count == N)
sleep();
acquire_lock()
insert_item();
count++;
release_lock()
if (count == 1)
wakeup(con);
if (count == 0)
wakeup without a matching sleep is lost
sleep();
acquire_lock()
remove_item();
count–;
release_lock();
if (count == N-1)
wakeup(prod);
32
con() {
while(TRUE) {
} }
Problem
• The test for some condition and actually going to sleep needs to be atomic
• The following does not work:
acquire_lock()
if (count == N)
sleep();
release_lock()
The lock is held while asleep count will never change
acquire_lock()
if (count == 1)
wakeup();
release_lock()
33
Semaphores
• Dijkstra (1965) introduced two primitives that are more powerful than simple sleep and wakeup alone.
• P(): proberen, from Dutch to test.
• V(): verhogen, from Dutch to increment. • Also called wait & signal, down & up.
34
How do they work
• If a resource is not available, the corresponding semaphore
blocks any process waiting for the resource
• Blocked processes are put into a process queue maintained
by the semaphore (avoids busy waiting!)
• When a process releases a resource, it signals this by means of the semaphore
• Signalling resumes a blocked process if there is any
• Wait and signal operations cannot be interrupted
• Complex coordination can be implemented by multiple semaphores
35
Semaphore Implementation
• Define a semaphore as a record typedef struct {
int count;
struct process *L; } semaphore;
• Assume two simple operations:
• sleep suspends the process that invokes it.
• wakeup(P) resumes the execution of a blocked process P.
36
• Semaphore operations now defined as
wait(S):
S.count–;
if (S.count < 0) {
add this process to S.L; sleep;
}
signal(S): S.count++;
if (S.count <= 0) {
remove a process P from S.L; wakeup(P);
}
• Each primitive is atomic
• E.g. interrupts are disabled for each
37
Semaphore as a General
Synchronization Tool
• Execute B in Pj only after A executed in Pi • Use semaphore count initialized to 0
• Code:
Pi Pj
⁞⁞
A wait(flag)
signal(flag) B
38
Semaphore Implementation of a Mutex • Mutex is short for Mutual Exclusion
• Can also be called a lock
semaphore mutex;
mutex.count = 1; /* initialise mutex */
wait(mutex); /* enter the critcal region */
Blahblah();
signal(mutex); /* exit the critical region */
Notice that the initial count determines how many waits can progress before blocking and requiring a signal mutex.count initialised as 1
39
Solving the producer-consumer problem with semaphores
#define N = 4
semaphore mutex = 1;
/* count empty slots */
semaphore empty = N;
/* count full slots */
semaphore full = 0;
40
Solving the producer-consumer problem with semaphores
prod() {
while(TRUE) {
con() {
while(TRUE) {
item = produce()
wait(empty);
wait(mutex)
insert_item();
signal(mutex);
signal(full);
}
}
wait(full);
wait(mutex);
remove_item();
signal(mutex);
signal(empty);
} }
41
Summarising Semaphores
• Semaphores can be used to solve a variety of concurrency problems
• However, programming with then can be error-prone • E.g. must signal for every wait for mutexes
• Too many, or too few signals or waits, or signals and waits in the wrong order, can have catastrophic results
42
Monitors
• To ease concurrent programming, Hoare (1974) proposed monitors.
• A higher level synchronisation primitive • Programming language construct
• Idea
• A set of procedures, variables, data types are grouped in a special kind of module, a monitor.
• Variables and data types only accessed from within the monitor
• Only one process/thread can be in the monitor at any one time
• Mutual exclusion is implemented by the compiler (which should be less error prone)
43
Monitor
• When a thread calls a monitor procedure that has a thread already inside, it is queued and it sleeps until the current thread exits the monitor.
44
Monitors
Example of a monitor
45
Simple example
monitor counter {
int count;
procedure inc() {
Note: “paper” language
• Compiler guarantees only one thread can be active in
count = count + 1; themonitoratanyonetime
}
procedure dec() {
count = count –1;
}
}
• Easy to see this provides mutual exclusion
• No race condition on count.
46
How do we block waiting for an event?
• We need a mechanism to block waiting for an event (in addition to ensuring mutual exclusion)
• e.g., for producer consumer problem when buffer is empty or full • Condition Variables
47
Condition Variable
• To allow a process to wait within the monitor, a condition variable must be declared, as
condition x, y;
• Condition variable can only be used with the operations wait and signal.
• The operation
x.wait();
• means that the process invoking this operation is suspended until another process invokes • Another thread can enter the monitor while original is suspended
x.signal();
• The x.signal operation resumes exactly one suspended process. If no process is suspended, then the signal operation has no effect.
48
Condition Variables
49
Monitors
• Outline of producer-consumer problem with monitors
• only one monitor procedure active at one time • buffer has N slots
50
OS/161 Provided Synchronisation Primitives
• Locks
• Semaphores
• Condition Variables
51
Locks
• Functions to create and destroy locks
struct lock *lock_create(const char *name);
void lock_destroy(struct lock *);
• Functions to acquire and release them
void lock_acquire(struct lock *); void lock_release(struct lock *);
52
Example use of locks
int count;
struct lock *count_lock
main() {
count = 0;
count_lock =
lock_create(“count
lock”);
if (count_lock == NULL)
panic(“I’m dead”);
stuff(); }
procedure inc() {
lock_acquire(count_lock);
count = count + 1;
lock_release(count_lock);
}
procedure dec() {
}
lock_acquire(count_lock);
count = count –1;
lock_release(count_lock);
53
Semaphores
struct semaphore *sem_create(const char *name, int initial_count);
void sem_destroy(struct semaphore *);
void P(struct semaphore *);
void V(struct semaphore *);
54
Example use of Semaphores
int count;
struct semaphore
*count_mutex;
main() {
count = 0;
count_mutex =
sem_create(“count”,
1);
procedure inc() {
P(count_mutex);
count = count + 1;
V(count_mutex);
}
procedure dec() {
P(count_mutex);
count = count –1;
V(count_mutex);
}
if (count_mutex == NULL)
panic(“I’m dead”);
stuff(); }
55
Condition Variables
struct cv *cv_create(const char *name);
void
void
• •
void void
• •
cv_destroy(struct cv *);
cv_wait(struct cv *cv, struct lock *lock);
Releases the lock and blocks
Upon resumption, it re-acquires the lock
• Note: we must recheck the condition we slept on
cv_signal(struct cv *cv, struct lock *lock);
cv_broadcast(struct cv *cv, struct lock *lock);
Wakes one/all, does not release the lock
First “waiter” scheduled after signaller releases the lock will re- acquire the lock
Note: All three variants must hold the lock passed in.
56
Condition Variables and Bounded Buffers
Non-solution
lock_acquire(c_lock)
if (count == 0)
sleep();
remove_item();
count--;
lock_release(c_lock)
;
Solution
lock_acquire(c_lock)
while (count == 0)
cv_wait(c_cv, c_lock);
remove_item();
count--;
lock_release(c_lock);
57
Alternative Producer-Consumer Solution Using OS/161 CVs
int count = 0;
#define N 4 /* buf size */ prod() {
while(TRUE) {
item = produce()
lock_aquire(l)
while (count == N)
cv_wait(full,l);
insert_item(item);
count++;
cv_signal(empty,l);
lock_release(l)
}} }}
con() {
while(TRUE) {
lock_acquire(l)
while (count == 0)
cv_wait(empty,l);
item = remove_item();
count--;
cv_signal(full,l);
lock_release(l);
consume(item);
58
Dining Philosophers
• Philosophers eat/think
• Eating needs 2 forks
• Pick one fork at a time
• How to prevent deadlock
59
Dining Philosophers
Solution to dining philosophers problem (part 1) 60
Dining Philosophers
A nonsolution to the dining philosophers problem
61
Dining Philosophers
Solution to dining philosophers problem (part 2) 62
63
The Readers and Writers Problem
• Models access to a database • E.g. airline reservation system
• Can have more than one concurrent reader • To check schedules and reservations
• Writers must have exclusive access
• To book a ticket or update a schedule
64
The Readers and Writers Problem
A solution to the readers and writers problem 65