CS计算机代考程序代写 concurrency [537] Locks and Condition Variables

[537] Locks and Condition Variables

Semaphores
Questions answered in this lecture:
Review: How to implement join with condition variables?
Review: How to implement producer/consumer with condition variables?
What is the difference between semaphores and condition variables?
How to implement a lock with semaphores?
How to implement semaphores with locks and condition variables?
How to implement join and producer/consumer with semaphores?
How to implement reader/writer locks with semaphores?

CSE 2431
Systems 2
Based on slides by Andrea C. Arpaci-Dusseau
Remzi H. Arpaci-Dusseau

Concurrency Objectives
Mutual exclusion (e.g., A and B don’t run at same time)
– solved with locks

Ordering (e.g., B runs after A does something)
– solved with condition variables and semaphores

Condition Variables
wait(cond_t *cv, mutex_t *lock)
– assumes the lock is held when wait() is called
– puts caller to sleep + releases the lock (atomically)
– when awoken, reacquires lock before returning

signal(cond_t *cv)
– wake a single waiting thread (if >= 1 thread is waiting)
– if there is no waiting thread, just return, doing nothing

Join Implementation:
COrrect
void thread_exit() {
Mutex_lock(&m); // a
done = 1; // b
Cond_signal(&c); // c
Mutex_unlock(&m); // d
}
void thread_join() {
Mutex_lock(&m); // w
if (done == 0) // x
Cond_wait(&c, &m); // y
Mutex_unlock(&m); // z
}
Parent:
Child:
Parent: w x y z
Child: a b c d
Use mutex to ensure no race between interacting with state
and wait/signal

Producer/Consumer Problem
Producers generate data (like pipe writers)
Consumers grab data and process it (like pipe readers)
Use condition variables to:
make producers wait when buffers are full
make consumers wait when there is nothing to consume

void *consumer(void *arg) {
while(1) {
Mutex_lock(&m); // c1
while(numfull == 0) // c2
Cond_wait(&cond, &m); // c3
int tmp = do_get(); // c4
Cond_signal(&cond); // c5
Mutex_unlock(&m); // c6
printf(“%d\n”, tmp); // c7
}
}
void *producer(void *arg) {
for (int i=0; ivalue = initval;
}
User cannot read or write value directly after initialization
Wait or Test (sometimes P() for Dutch word)
Waits until value of sem is > 0, then decrements sem value
Signal or Increment or Post (sometimes V() for Dutch)
Increment sem value, then wake a single waiter
wait and post are atomic

Join with CV vs Semaphores
void thread_exit() {
Mutex_lock(&m); // a
done = 1; // b
Cond_signal(&c); // c
Mutex_unlock(&m); // d
}
void thread_join() {
Mutex_lock(&m); // w
if (done == 0) // x
Cond_wait(&c, &m); // y
Mutex_unlock(&m); // z
}
CVs:
void thread_exit() {
sem_post(&s)
}
void thread_join() {
sem_wait(&s);
}
sem_t s;
sem_init(&s, ???);

Semaphores:
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Initialize to 0 (so sem_wait() must wait…)

Equivalence Claim
Semaphores are equally powerful to Locks+CVs
– what does this mean?

One might be more convenient, but that’s not relevant

Equivalence means each can be built from the other

Proof Steps
Want to show we can do these three things:
Locks
Semaphores
CV’s
Semaphores
Locks
Semaphores
CV’s

Build Lock from Semaphore
typedef struct __lock_t {
// whatever data structs you need go here
} lock_t;

void init(lock_t *lock) {
}

void acquire(lock_t *lock) {
}

void release(lock_t *lock) {
}
Locks
Semaphores
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Build Lock from Semaphore
typedef struct __lock_t {
sem_t sem;
} lock_t;

void init(lock_t *lock) {
sem_init(&lock->sem, ??);
}
void acquire(lock_t *lock) {
sem_wait(&lock->sem);
}
void release(lock_t *lock) {
sem_post(&lock->sem);
}
Locks
Semaphores
1  1 thread can grab lock
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Building CV’s over Semaphores
Possible, but really hard to do right

Read about Microsoft Research’s attempts:
http://research.microsoft.com/pubs/64242/ImplementingCVs.pdf
CV’s
Semaphores

Build Semaphore from Lock and CV
Typedef struct {
// what goes here?

} sem_t;

Void sem_init(sem_t *s, int value) {
// what goes here?

}

Locks
Semaphores
CV’s
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Build Semaphore from Lock and CV
Typedef struct {
int value;
cond_t cond;
lock_t lock;
} sem_t;

Void sem_init(sem_t *s, int value) {
s->value = value;
cond_init(&s->cond);
lock_init(&s->lock);
}

Locks
Semaphores
CV’s
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Build Semaphore from Lock and CV
Sem_wait{sem_t *s) {
// what goes here?

}

Sem_post{sem_t *s) {
// what goes here?

}

Locks
Semaphores
CV’s
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Build Semaphore from Lock and CV
Sem_wait{sem_t *s) {
lock_acquire(&s->lock);
// this stuff is atomic

lock_release(&s->lock);
}

Sem_post{sem_t *s) {
lock_acquire(&s->lock);
// this stuff is atomic

lock_release(&s->lock);
}

Locks
Semaphores
CV’s
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Build Semaphore from Lock and CV
Sem_wait{sem_t *s) {
lock_acquire(&s->lock);
while (s->value <= 0) cond_wait(&s->cond);
s->value–;
lock_release(&s->lock);
}

Sem_post{sem_t *s) {
lock_acquire(&s->lock);
// this stuff is atomic

lock_release(&s->lock);
}

Locks
Semaphores
CV’s
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Build Semaphore from Lock and CV
Sem_wait{sem_t *s) {
lock_acquire(&s->lock);
while (s->value <= 0) cond_wait(&s->cond);
s->value–;
lock_release(&s->lock);
}

Sem_post{sem_t *s) {
lock_acquire(&s->lock);
s->value++;
cond_signal(&s->cond);
lock_release(&s->lock);
}

Locks
Semaphores
CV’s
Sem_wait(): Waits until value > 0, then decrement
Sem_post(): Increment value, then wake a single waiter

Producer/Consumer: Semaphores #1
Simplest case:
Single producer thread, single consumer thread
Single shared buffer between producer and consumer
Requirements
Consumer must wait for producer to fill buffer
Producer must wait for consumer to empty buffer (if filled)
Requires 2 semaphores
emptyBuffer: Initialize to ???
fullBuffer: Initialize to ???
Producer
While (1) {
sem_wait(&emptyBuffer); Fill(&buffer);
sem_signal(&fullBuffer);
}
Consumer
While (1) {
sem_wait(&fullBuffer); Use(&buffer);
sem_signal(&emptyBuffer);
}
1  1 empty buffer; producer can run 1 time first
0  0 full buffers; consumer can run 0 times first

Producer/Consumer:
Semaphores #2
Next case: Circular Buffer
Single producer thread, single consumer thread
Shared buffer with N elements between producer and consumer
Requires 2 semaphores
emptyBuffer: Initialize to ???
fullBuffer: Initialize to ???
Producer
i = 0;
While (1) {
sem_wait(&emptyBuffer);
Fill(&buffer[i]);
i = (i+1)%N;
sem_signal(&fullBuffer);
}
Consumer
j = 0;
While (1) {
sem_wait(&fullBuffer);
Use(&buffer[j]);
j = (j+1)%N;
sem_signal(&emptyBuffer);
}
N  N empty buffers; producer can run N times first
0  0 full buffers; consumer can run 0 times first

Producer/Consumer:
Semaphore #3
Final case:
Multiple producer threads, multiple consumer threads
Shared buffer with N elements between producer and consumer
Requirements
Each consumer must grab unique filled element
Each producer must grab unique empty element
Why will previous code (shown below) not work???
Producer
i = 0;
While (1) {
sem_wait(&emptyBuffer);
Fill(&buffer[i]);
i = (i+1)%N;
sem_signal(&fullBuffer);
}
Consumer
j = 0;
While (1) {
sem_wait(&fullBuffer);
Use(&buffer[j]);
j = (j+1)%N;
sem_signal(&emptyBuffer);
}
Are i and j private or shared? Need each producer to grab unique buffer

Producer/Consumer:
Multiple Threads
Producer
While (1) {
sem_wait(&emptyBuffer);
myi = findempty(&buffer);
Fill(&buffer[myi]);
sem_signal(&fullBuffer);
}
Consumer
While (1) {
sem_wait(&fullBuffer);
myj = findfull(&buffer);
Use(&buffer[myj]);
sem_signal(&emptyBuffer);
}
Are myi and myj private or shared? Where is mutual exclusion needed???
Final case:
Multiple producer threads, multiple consumer threads
Shared buffer with N elements between producer and consumer
Requirements
Each consumer must grab unique filled element
Each producer must grab unique empty element

Producer/Consumer:
Multiple Threads
Consider three possible locations for mutual exclusion
Which work??? Which is best???
Producer #1
sem_wait(&mutex);
sem_wait(&emptyBuffer);
myi = findempty(&buffer);
Fill(&buffer[myi]);
sem_signal(&fullBuffer);
sem_signal(&mutex);
Consumer #1
sem_wait(&mutex);
sem_wait(&fullBuffer);
myj = findfull(&buffer);
Use(&buffer[myj]);
sem_signal(&emptyBuffer);
sem_signal(&mutex);
Problem: Deadlock at mutex (e.g., consumer runs first; won’t release mutex)

Producer/Consumer:
Multiple Threads
Consumer #2
sem_wait(&fullBuffer);
sem_wait(&mutex);
myj = findfull(&buffer);
Use(&buffer[myj]);
sem_signal(&mutex);
sem_signal(&emptyBuffer);
Producer #2
sem_wait(&emptyBuffer);
sem_wait(&mutex);
myi = findempty(&buffer);
Fill(&buffer[myi]);
sem_signal(&mutex);
sem_signal(&fullBuffer);
Consider three possible locations for mutual exclusion
Which work??? Which is best???
Works, but limits concurrency:
Only 1 thread at a time can be using or filling different buffers

Producer/Consumer:
Multiple Threads
Consumer #3
sem_wait(&fullBuffer);
sem_wait(&mutex);
myj = findfull(&buffer);
sem_signal(&mutex);
Use(&buffer[myj]);
sem_signal(&emptyBuffer);
Producer #3
sem_wait(&emptyBuffer);
sem_wait(&mutex);
myi = findempty(&buffer);
sem_signal(&mutex);
Fill(&buffer[myi]);
sem_signal(&fullBuffer);
Consider three possible locations for mutual exclusion
Which work??? Which is best???
Works and increases concurrency; only finding a buffer is protected by mutex;
Filling or Using different buffers can proceed concurrently

Reader/Writer Locks
Goal:
Let multiple reader threads grab lock (shared)
Only one writer thread can grab lock (exclusive)
No reader threads
No other writer threads

Let us see if we can understand code…

Reader/Writer Locks
1 typedef struct _rwlock_t {
2 sem_t lock;
3 sem_t writelock;
4 int readers;
5 } rwlock_t;
6
7 void rwlock_init(rwlock_t *rw) {
8 rw->readers = 0;
9 sem_init(&rw->lock, 1);
10 sem_init(&rw->writelock, 1);
11 }
12

Reader/Writer Locks
13 void rwlock_acquire_readlock(rwlock_t *rw) {
14 sem_wait(&rw->lock);
15 rw->readers++;
16 if (rw->readers == 1)
17 sem_wait(&rw->writelock);
18 sem_post(&rw->lock);
19 }
21 void rwlock_release_readlock(rwlock_t *rw) {
22 sem_wait(&rw->lock);
23 rw->readers–;
24 if (rw->readers == 0)
25 sem_post(&rw->writelock); ]
26 sem_post(&rw->lock);
27 }
29 rwlock_acquire_writelock(rwlock_t *rw) { sem_wait(&rw->writelock); }
31 rwlock_release_writelock(rwlock_t *rw) { sem_post(&rw->writelock); }

T1: acquire_readlock()
T2: acquire_readlock()
T3: acquire_writelock()
T2: release_readlock()
T1: release_readlock()
T4: acquire_readlock()
T5: acquire_readlock() // ???
T3: release_writelock()
// what happens???

Semaphores
Semaphores are equivalent to locks + condition variables
Can be used for both mutual exclusion and ordering
Semaphores contain state
How they are initialized depends on how they will be used
Init to 1: Mutex
Init to 0: Join (1 thread must arrive first, then other)
Init to N: Number of available resources
Sem_wait(): Waits until value > 0, then decrement (atomic)
Sem_post(): Increment value, then wake a single waiter (atomic)
Can use semaphores in producer/consumer relationships and for reader/writer locks