Posix Thread SynchronizationCS 241: Systems ProgrammingDiscussion, Week 4slides prepared by Sameer SundreshMP3MotivationSemaphoresDeadlocksProducer-ConsumerMP3MP3MotivationSemaphoresDeadlocksProducer-ConsumerMotivationMultiple threads execute independently, but have access to the same memory and resources.This can be unsafe without coordination:int x = 0;void *up(void *arg) // in thread A{ int i; for (i = 0; i < N; i++) x++; }void *down(void *arg) // in thread B{ int i; for (i = 0; i < N; i++) x--; }Coordination conceptC doesn't have native atomic constructs,but what if it did?int x = 0;void *up(void *arg) // in thread A{int i;for (i = 0; i < N; i++)atomic { // how to implement atomic?x++;}}Synchronization constructsAny of these may be used for synchronization:●Mutexes (simple but low-level)–Mutual exclusion locks●Condition variables (kind of complicated)–Wait until the value of a special variable changes●Semaphores (we'll discuss these today)–Abstraction of a resource counter–Can simulate mutexes & condition variablesMP3MotivationSemaphoresDeadlocksProducer-ConsumerSemaphoresAbstraction of a resource counter.Operations:sem_wait(sem)wait until counter > 0,then decrement countersem_post(sem)increment counterThese operations must be atomic.Managing semaphoresOperations to create and destroy semaphores:sem_t sem;// ...int main(int argc, char **argv){sem_init(&sem, 0, init_value);// ...use sem in here...sem_destroy(&sem);}Example 1: Hello World!Let's make Hello World! safe (see disc4-ex1.c):mainhelloworldmainhelloworldsemExample 2: up/downLet's make up/down safe (see disc4-ex2*.c):int x = 0; sem_t sem;void *up(void *arg) // in thread A{int i;for (i = 0; i < N; i++) {sem_wait(&sem);x++;sem_post(&sem);}}MP3MotivationSemaphoresDeadlocksProducer-ConsumerDeadlocks (disc4-ex3.c)All is not calm in semaphore land... sem_init(&sem1, 0, 1); sem_init(&sem2, 0, 1);// Thread A // Thread Bsem_wait(&sem1); sem_wait(&sem2);sem_wait(&sem2); sem_wait(&sem1); // potential deadlock!sem_post(&sem2); sem_post(&sem1);sem_post(&sem1); sem_post(&sem2);Deadlock? (disc4-ex3.c) sem_init(&sem1, 0, 1); sem_init(&sem2, 0, 1);S1 S2 // Thread A // Thread B 1 1 sem_wait(&sem1); 0 1 sem_wait(&sem2); 0 0 sem_post(&sem2); 0 1 sem_post(&sem1); 1 1 sem_wait(&sem2); 1 0 sem_wait(&sem1); 0 0 sem_post(&sem1); 1 0 sem_post(&sem2); 1 1 OK...Deadlock! (disc4-ex3.c) sem_init(&sem1, 0, 1); sem_init(&sem2, 0, 1);S1 S2 // Thread A // Thread B 1 1 sem_wait(&sem1); 0 1 sem_wait(&sem2); 0 0 sem_wait(&sem2); 0 0 sem_wait(&sem2); DEADLOCKDeadlockn't (disc4-ex3b.c) sem_init(&sem1, 0, 2); sem_init(&sem2, 0, 2);S1 S2 // Thread A // Thread B 2 2 sem_wait(&sem1); 1 2 sem_wait(&sem2); 1 1 sem_wait(&sem2); 1 0 sem_wait(&sem1); 0 0 sem_post(&sem2); 0 1 sem_post(&sem1); 1 1 sem_post(&sem1); 2 1 sem_post(&sem2); 2 2 OK2 copies of resourcesMP3MotivationSemaphoresDeadlocksProducer-ConsumerProducer-Consumer model ProducerthreadConsumerthreadqueueProducer-Consumer modelNecessary atomic operations:int enqueue(queue_t *q, void *datum);// Return 1 on success, 0 on failure.void *dequeue(queue_t *q);// Wait if no data is available.How do we implement these with semaphores?See disc4-ex4*.cUnthreaded queueFirst draft—get the queue operations working before we worry about threadingdisc4-ex4.cWhile it may appear to function correctly even with multiple threads under simple test cases, it's not guaranteed to be thread-safe.Queue with a lockNow use a semaphore to mediate queue access:One resource, a single lockMust hold the lock to enqueue or dequeueTry using it with multiple threadsdisc4-ex4b.cTry adding delays into the enqueue thread!Queue with lock & counterAdd a counter semaphore to keep track of how many elements are waiting in the queue:Use sem_post() to indicate an insertionUse sem_wait() to claim a removal—and block the caller if the queue is empty.disc4-ex4c.cAgain try delays in the enqueue
View Full Document