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?
-What problems do you think we might encounter?
Terminology:
Shared data: Critical Sections: Race Condition: Mutual Exclusion: Atomic:
Instruction Flow
For the array example shown above example above what is the
Shared data:
Critical Section:
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: unlock:
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: Solution:
Spinlock /Busy waiting
– a lock where waiter spins, looping until the lock is acquired
Alternative
What are the limitations of using Atomic Memory Exchange
Very expensive Blocking bridge analogy
Pros:
Cons:
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?
What is a condition variable? How do you create one? How do you use it?
What do lock, unlock, wait, signal and broadcast do?
– lock
– unlock
– wait
– signal
– broadcast
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
DiskRead with Mutexes Revisited
Answer
Compare the pros and cons of each approach
Disallowing new readers while writer is waiting
Semaphores
What is a semaphore?
Change the code shown below to use semaphores. We need to ensure that b is not printed to the screen until a prints.
4_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
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);
}
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();
return 0; }
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); }
What does create do?
How do wait and signal work
DiskRead with Semaphores
Why don’t we need to have scheduleRead&wait or signal in a critical section?
Queue with Semaphores
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?
Why do we need a critical section?
What is the role of the semaphore length?
Why is wait(length) outside of critical section?
Can we record the signals in enqueue?
(i.e., can we move the signals (qlength) to inside the mutex)
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?
– add uthread_sem_wait(a_can_run) to line 8 and uthread_sem_signal(a_can_run) to line 20?
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. _________________________________________
2. _________________________________________