Motivation for Concurrency
Stack Linked-List Example:
Instruction Flow
Adding multiple CPUs to our picture…
-What benefits can we gain with threads and multiple CPUs?
speed
-What problems do you think we might encounter?
coordinating access to memory shared among multiple threads control flow transfers among threads
Terminology:
Shared data: data that can be access by multiple threads
Critical Sections: sections of code that access shared data
Race Condition: simultaneous access to critical sections by multiple threads (a race to data don’t know who will get there first)
Mutual Exclusion: a mechanism to ensure critical sections are accessed one thread at a time
Atomic: indivisible, should occur as one
Mutual Exclusion using locks
– a lock is either held by a thread, or available
– at most one thread can hold a lock at a time
– a thread attempting to acquire a lock already held is forced to wait
lock: acquire a lock, wait if lock is already held
unlock: release a lock, allowing another thread to acquire if waiting
Lock Implementation
Same issue exists at the assembly level as well
Atomic Memory Exchange Instruction
– atomically read and write a memory location
– no way an interrupt can occur before the whole ‘unit’ is finished
Problem: atomic exchange is a very expensive instruction. It blocks all traffic on the bus between CPU and memory!
For the array example shown above example above what is the
Shared data:
n, array
Critical Section:
the if block in both functions
Solution: Only use xchg when we think the lock is free
Alternative
Spinlock /Busy waiting
– a lock where waiter spins, looping until the lock is acquired
What are the limitations of using Atomic Memory Exchange
Very expensive Blocking bridge analogy
Pros: We get mutual exclusion! Minimize expensive xchg use Cons: Wastes CPU cycles if/when the spinner waits a long time
Blocking Locks
Big issue with spinlocks is when threads wait a long time
Instead of spinning, why don’t we block the thread and then unblock when the lock becomes available (a different thread can unblock when it is finished in the critical section) –HOW?!
Monitors
What is a monitor/mutex? How do you create one? How do you use it?
– Just a lock that busy waits if not used with a condition variable
– But special in that you can create a condition associated with the
lock
What is a condition variable? How do you create one? How do you use it?
– Creation associated with a mutex
– Allow the thread to block on that condition instead of busy waiting What do lock, unlock, wait, signal and broadcast do?
– lock acquires the lock (busy waiting) – it is ok because no one holds it very long
– unlock releases the lock (critical section in between just like example from last lecture)
– wait releases the lock and then blocks itself (why must it release the lock), when unblock requests lock
– signal unblocks at most one waiter (does mean it will be the running thread or that is has the lock)
– broadcast unblocks all waiting threads
Ordering A and B Statements
See the zip file order_demo.zip that details the various versions
Reader-Writer Monitors
Allowing new readers while writer is waiting
It maximizes throughput, but it unfair because the writer is bypassed.
In addition, if you don’t have a limit on the number of readers that can bypass the writer in the queue, you risk having the readers exposed to stale data. Think of seat reservation on an airline website. It would not be good if when you started searching for a seat all were empty and then the next update was that all were full.
Note: if a reader required the new data it would be runnable but would have been blocked.
DiskRead with Mutexes Revisited
Compare the pros and cons of each approach
Disallowing new readers while writer is waiting
It is more fair and ensures that the most current version of the data is being read by readers.
It reduces throughput as the reader threads have to wait even though they could be running.
We have to guarantee that the wait comes before the signal.
The lock enforces the order; if scheduleRead is called then wait occurs as well. In Version 2 without the lock there is no guarantee that an interrupt external to our program occurs right after scheduleRead so that the signal ends of happening before wait is called.
Semaphores
What is a semaphore?
– an atomic counter that can never be less than 0
– attempting to make counter negative blocks calling thread
– can never read the value of counter – only signal and wait (atomic
instructions)
What does create do?
It creates a semaphore with an initial value >=0
How do wait and signal work
– try to reduce s
– atomically blocks until s>0 then decrements s
– increase s
atomically increase s unblocking threads waiting in P as appropriate DiskRead with Semaphores
Why don’t we need to have scheduleRead&wait or signal in a critical section?
Signalling on a semaphore has memory.
If you signal before you wait with condition variables it was a problem, but we don’t have that problem here, because when wait occurs after signal, it will check to semaphore value recognize that the signal has occurred (i.e. semaphore value >0) and continue
Change the code shown below to use semaphores. We need to ensure that ‘b’ is not printed to the screen until ‘a’ prints.
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
uthread_mutex_t mx; uthread_cond_t b_can_run;
int control = 0;
void a() { sleep(1);
uthread_mutex_lock (mx);
printf (“a\n”);
control = 1; uthread_cond_signal (b_can_run); uthread_mutex_unlock (mx);
}
#include “uthread_sem.h” uthread_sem_t b_run;
void b() { sleep(1);
uthread_mutex_lock (mx); if (control == 0)
uthread_cond_wait(b_can_run); printf (“b\n”);
uthread_mutex_unlock (mx); }
void* startThread0 (void* v) { a();
return 0; }
void* startThread1 (void* v) { b();
printf (“a\n”); uthread_sem_signal(b_run);
return 0; }
b_run = uthread_sem_create(0);
uthread_sem_wait(b_run); printf (“b\n”);
int main (int argc, char *argv[]) { uthread_init (3);
mx = uthread_mutex_create(); b_can_run = uthread_cond_create(mx);
uthread_t t0 = uthread_create (startThread0, 0); uthread_t t1 = uthread_create (startThread1, 0); uthread_join (t0, 0);
uthread_join (t1, 0); }
Queue with Semaphores
– add uthread_sem_wait(a_can_run) to line 8 and uthread_sem_signal(a_can_run) to line 20?
6_order.c
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
uthread_sem_t a_can_run; uthread_sem_t b_can_run;
void a() {
printf (“a\n”);
uthread_sem_signal (b_can_run);
printf (“aa\n”); }
void b() {
uthread_sem_wait (b_can_run);
printf (“b\n”);
printf (“bb\n”); }
void* goA (void* v) { a();
return 0; }
void* goB (void* v) { b();
return 0; }
int main() { uthread_init (3);
Drawn out on next page
a_can_run = uthread_sem_create(0); b_can_run = uthread_sem_create(0); uthread_t t0 = uthread_create(goA, 0); uthread_t t1 = uthread_create(goB, 0);
uthread_join (t0, 0);
uthread_join (t1, 0); }
Why don’t we need to loop?
Semaphores check and update the variable atomically so there is no way another thread can take the signal that just occurred. If you wait and then are signaled, in a sense it is like the monitor lock is being passed over to you (not exactly though)
Why do we need a critical section?
Because to update a shared variable we still need to make sure that only one thread is accessing the variable.
What is the role of the semaphore length?
To keep track of the number of items in the queue and to make sure that we only remove from a non-empty queue.
Why is wait(length) outside of critical section?
If the wait(length) was inside of the critical section then the thread is waiting while holding the mutex and so no other thread will be able to enter the critical section and update length so deadlock.
Can we record the signals in enqueue?
(i.e., can we move the signals (qlength) to inside the mutex) Yes
In the following implementation, there is an unused semaphore declared/initialized: a_can_run. We want to us this semaphore to ensure some kind of waiting between the threads. What is the output of each of the options below:
– add uthread_sem_wait(a_can_run) to line 10 and uthread_sem_signal(a_can_run) to line 20?
– add uthread_sem_wait(a_can_run) to line 8 and uthread_sem_signal(a_can_run) to line 16?
Rules
Philosophers can’t communicate with each other
They must pick up two of the nearest chopsticks in order to eat
They must pick up the chopsticks one at a time, not together.
If they pick up one and the other isn’t available, they wait for the second (they don’t drop the first)
They can not count how many chopsticks are available on the table
They don’t know if the other is available
They cannot add new chopsticks, a coordinator or get rid of the philosophers
What is the issue if we have one thread running y and another running x?
Definitions
Deadlock – state where threads are waiting on others to release a lock Livelock – repeated instructions in response to a state that doesn’t result in
useful changes to the system. No progress is made
Starvation – the result of a policy that determines who gets the resources
leads to certain threads not getting serviced.
Dining Philosophers Problem
Develop a policy to ensure for allocating the chopsticks (resources) among server philosophers (processes) in a manner that is deadlock free.
Accepted Solutions that follow all the rules
1. Random Timer – not waiting the same length of time, pick a random
number and if a collision occurs, increase the range of the wait times,
This is how wifi works.
2. Order the fork so that every fork has a number and there is a rule you
must pick up the lowest number first, so at least 1 philosopher will use the other hand.
Solutions that break at least 1 rule.
X locks a and Y locks B, It is holding A waiting for B and the
other one is holding B and waiting for A, deadlock
Any time there is a cycle in a waiter graph it is deadlock 5.
3.
Have a waiter that you ask for permission. Only gives permission to one person (mutex) at a time and if only 1 fork is left no permission. You drop the fork if you can’t get another fork. Precedence, detect, and destroy – Kill a philosopher. With only 4 philosophers one person will get the fork and proceed.
Timer – hold a fork, time out and wait, if it is the exact same wait time then the system is in livelock. Threads are starving to death but not in deadlock state.
Precedence, detect, and destroy – Kill a philosopher. With only 4 philosophers one person will get the fork and proceed.
4.