CS241 System ProgrammingOutlineReviewReviewCondition VariablesExampleCreating / Destroying CVsWaiting on CVsSignaling on CVsExampleProducer-Consumer ProblemImplementation using CVsImplementation using CVsProducer-Consumer ProblemImplementation using SemaphoresImplementation using SemaphoresReader-Writer ProblemRead-Write LocksCreating / Destroying rwlockAcquiring / Releasing rwlockCPU SchedulingCPU SchedulingA Simple Example (Priority)A Simple Example (Priority)A Simple Example (Priority)A Simple Example (Priority)A Simple Example (Priority)A Simple Example (Priority)A Simple Example (Priority)POSIX SchedulingSummaryCS241 System ProgrammingDiscussion Section 4Feb 13 – Feb 16Outlinez Synchronizationz Condition Variablesz Producer-Consumer Problemz Reader-Writer Problemz CPU Schedulingz Metricsz ExamplesReviewz What is wrong with the following code fragment in multi-threaded environment? How would you modify it?static int count;void increment(void) {count++;}void decrement(void) {count--; }int getcount() {return count; }Reviewz Thread-Safe version (using mutex)static int count = 0; static pthread_mutex_t countlock = PTHREAD_MUTEX_INITIALIZER;int increment(void) { /* decrement() similar */int error; if (error = pthread_mutex_lock(&countlock))return error; count++;return pthread_mutex_unlock(&countlock);}int getcount(int *countp) {int error; if (error = pthread_mutex_lock(&countlock)) return error; *countp = count; return pthread_mutex_unlock(&countlock); }Condition Variablesz Allows explicit event notificationz Implements a monitor along with a mutexz #include <pthread.h>z Type: pthread_cond_tz Two main operationsz Wait: pthread_cond_waitz Signal: pthread_cond_signalExamplez Waiting for x==y conditionpthread_mutex_lock(&m); while (x != y) pthread_cond_wait(&v, &m); /* modify x or y if necessary */ pthread_mutex_unlock(&m);z Notifying the waiting thread that it has incremented xpthread_mutex_lock(&m); x++; pthread_cond_signal(&v);pthread_mutex_unlock(&m);Creating / Destroying CVsz Creating a condition variablez Standard Initializerint pthread_cond_init(pthread_cond_t *restrict cond, const pthread_condattr_t *restrict attr);z Static Initializerpthread_cont_t cond = PTHREAD_COND_INITIALIZER;zDestroying a condition variableint pthread_cond_destroy(pthread_cond_t *cond);zReturns 0 if successful, nonzero error code if unsuccessfulWaiting on CVsint pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex);z Called with a mutex lock heldz Internalsz Causes the thread to release the mutexz Sleeps until signaledz Reacquires the lock when waken upz Variation: pthread_cond_timedwaitSignaling on CVsz Signalz Wakes up one waiting threadint pthread_cond_signal(pthread_cond_t *cond);z Broadcastz Wakes up all waiting threadsint pthread_cond_broadcast(pthread_cond_t *cond);Examplez Thread-safe Barrier (Program 13.13)int waitbarrier(void) { /* wait at the barrier until all n threads arrive */int berror = 0;int error;if (error = pthread_mutex_lock(&bmutex)) /* couldn't lock, give up */return error;if (limit <= 0) { /* make sure barrier initialized (limit = #threads) */pthread_mutex_unlock(&bmutex);return EINVAL;}count++;while ((count < limit) && !berror)berror = pthread_cond_wait(&bcond, &bmutex);if (!berror)berror = pthread_cond_broadcast(&bcond); /* wake up everyone */error = pthread_mutex_unlock(&bmutex);if (berror)return berror;return error;}Producer-Consumer Problemz Given variablesstatic buffer_t buffer[BUFSIZE];static pthread_mutex_t bufferlock = PTHREAD_MUTEX_INITIALIZER;static int bufin = 0;static int bufout = 0;static pthread_cond_t items = PTHREAD_COND_INITIALIZER;static pthread_cond_t slots = PTHREAD_COND_INITIALIZER;static int totalitems = 0;z Implement the following functions using CVsz int getitem(buffer_t *itemp)z removes item from butter and put in *itempz int putitem(buffer_t item)z Inserts item in the bufferImplementation using CVsint getitem(buffer_t *itemp) {int error;if (error = pthread_mutex_lock(&bufferlock))return error;while ((totalitems <= 0) && !error)error = pthread_cond_wait (&items, &bufferlock);if (error) {pthread_mutex_unlock(&bufferlock);return error;}*itemp = buffer[bufout];bufout = (bufout + 1) % BUFSIZE;totalitems--;if (error = pthread_cond_signal(&slots)) {pthread_mutex_unlock(&bufferlock);return error;}return pthread_mutex_unlock(&bufferlock);}Implementation using CVsint putitem(buffer_t item) { int error;if (error = pthread_mutex_lock(&bufferlock))return error;while ((totalitems >= BUFSIZE) && !error)error = pthread_cond_wait (&slots, &bufferlock);if (error) {pthread_mutex_unlock(&bufferlock);return error;}buffer[bufin] = item;bufin = (bufin + 1) % BUFSIZE;totalitems++;if (error = pthread_cond_signal(&items)) {pthread_mutex_unlock(&bufferlock);return error;}return pthread_mutex_unlock(&bufferlock);}Producer-Consumer Problemz Given variablesstatic buffer_t buffer[BUFSIZE];static pthread_mutex_t bufferlock = PTHREAD_MUTEX_INITIALIZER;static int bufin = 0;static int bufout = 0;static sem_t semitems;static sem_t semslots;z Implement the following functions using semaphoresz int getitem(buffer_t *itemp)z removes item from butter and put in *itempz int putitem(buffer_t item)z Inserts item in the bufferImplementation using Semaphoresint getitem(buffer_t *itemp) {int error;while (((error = sem_wait(&semitems)) == -1) && (errno == EINTR)) ;if (error)return errno;if (error = pthread_mutex_lock(&bufferlock))return error;*itemp = buffer[bufout];bufout = (bufout + 1) % BUFSIZE;if (error = pthread_mutex_unlock(&bufferlock))return error;if (sem_post(&semslots) == -1)return errno;return 0;}Implementation using Semaphoresint putitem(buffer_t item) {int error;while (((error = sem_wait(&semslots)) == -1) && (errno == EINTR)) ;if (error)return errno;if (error = pthread_mutex_lock(&bufferlock))return error;buffer[bufin] = item;bufin = (bufin + 1) % BUFSIZE;if (error = pthread_mutex_unlock(&bufferlock))return error;if (sem_post(&semitems) == -1)return errno;return 0;}Reader-Writer Problemz Two types of accessz Read: may be sharedz Write: must be exclusivez Reader-Writer Synchronizationz Strong Reader Synchronizationz Preference to readers (e.g. a library database)z Strong Writer Synchronizationz Preference to writers (e.g. an airline reservation system)z POSIX provides read-write locksRead-Write Locksz Allows multiple readers to acquire a lockz When a writer does not hold the lockz #include <pthread.h>z Type:
View Full Document