pathterminuspages/notes/aboutcontactabout me

Semaphores

Computer Systems :: 13-01-2018

These notes might change over time, some might also be incomplete. If you find any errors or misleading text, please comment about it.

One problem occuring when multithreading in C is that shared state can be changed in an unintended way. Say we have the program:

#include <stdio.h> #include <stdlib.h> #include <pthread.h> #define ITERS 1000 #define DIMS 2 #define TESTS 20 int cnt; void *threadF(void *arg){ for(int i = 0; i < ITERS; i++){ cnt++; } } void runner(){ pthread_t tids [DIMS]; for(int i = 0; i < DIMS; i++){ pthread_create(&tids[i],NULL,threadF,NULL); } for(int i = 0; i < DIMS; i++){ pthread_join(tids[i],NULL); } printf("end : %d\n",cnt); } int main(){ for(int i = 0; i < TESTS; i++){ cnt = 0; runner(); } }

With the output (output varies each time the program is runned):

end : 4000 end : 4000 end : 4000 end : 4000 end : 4000 end : 3431 end : 3024 end : 4000 end : 3802 end : 4000 end : 4000 end : 4000 end : 3416 end : 3329 end : 3830 end : 3172 end : 3592 end : 3080 end : 3443 end : 3412

The result of each end should yield 4000. But doesn't. The reason is this. For every loop iteration in threadF the value of cnt instruction-wise is first loaded and changed and then stored. The last two probably happens in one instruction, but there isn't any way to ensure that control isn't passed to another thread after a value is loaded. Thus if a thread loads i = 10, and then control is passed to another thread which loads i = 10, saves the value and then passes control back to the last thread which stores, the value i = 10 + 1 is just stored twice.

For two threads running a progress graph can be drawn (the blue rectangle is a region where instructions operates on shared state, in this case it spans three instructions for each thread):

Progress graph

Where a step can be performed either x- or y-wise, but not both. The idea of this graph is that any path can be taken to reach point I1,I2. If the trajectory passes through the unsafe region, the above problem can occur.

To fix this mess we have to apply what is called semaphores. The most simple of these are mutexes. Applying, and the code becomes:

#include <stdio.h> #include <stdlib.h> #include <pthread.h> #define ITERS 100000 #define DIMS 2 #define TESTS 20 int cnt; pthread_mutex_t mutex; void *threadF(void *arg){ for(int i = 0; i < ITERS; i++){ pthread_mutex_lock(&mutex); cnt++; pthread_mutex_unlock(&mutex); } } void runner(){ pthread_t tids [DIMS]; for(int i = 0; i < DIMS; i++){ pthread_create(&tids[i],NULL,threadF,NULL); } for(int i = 0; i < DIMS; i++){ pthread_join(tids[i],NULL); } printf("end : %d\n",cnt); } int main(){ for(int i = 0; i < TESTS; i++){ cnt = 0; runner(); } }

In line 14 cnt is locked and again unlocked in line 16. A semaphore is a global variable, s, that works as follows:

  • lock(s) : if s is nonzero decrement and return. If s is zero suspend thread. When s becomes nonzero, the thread is restarted by an unlock. After restart lock decrements s and return control to the caller.
  • unlock(s) : increment s by 1. If there are any locked operations, then unlock restarts exactly one of these.

Both lock and unlock are performed without interruptions. Thus when lock is called, the thread called from keeps control until unlock is called. A semaphore which can only have the value 0 or 1, is called a mutex.

Deadlocks

A deadlock occurs when two or more threads, which uses two semaphores, reaches a state where each thread mutually waits for the other thread to unlock a semaphore.

Say we have two mutexes, m1 and m2, the shared state a and b and two threads:

Thread1: lock(m1) a += 1 lock(m2) a += 1 b += 1 unlock(m2) unlock(m1) Thread2: lock(m2) b += 1 lock(m1) a += 1 b += 1 unlock(m1) unlock(m2)

So what happens? Say thread1 reaches lock(m1) and thread2 reaches lock(m2). Now either one can move on since both mutexes are locked. This can be drawn as the trajectory where m1 = m2 = 1:

A program handling two mutexes and two threads can avoid deadlock by ordering the lock and unlock, ex. as so:

Thread1: lock(m1) a += 1 lock(m2) a += 1 b += 1 unlock(m1) unlock(m2) Thread2: lock(m1) b += 1 lock(m2) a += 1 b += 1 unlock(m1) unlock(m2)

Now if thread1 goes first, thread2 can't start before thread1 finishes.

Deadlock when threading and forking

Observe this code (stolen from a Computer Systems exam):

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; void hello() { pthread_mutex_lock(&lock); printf("hello\n"); pthread_mutex_unlock(&lock); } void* thread(void* unused) { hello(); return NULL; } int main() { pthread_t t; pthread_create(&t, NULL, thread, NULL); if (fork() == 0) { hello(); } else { wait(NULL); // Wait for child to finish. pthread_join(t, NULL); } }

Can it deadlock? Apparently so. Nice question, by the way. The question is answered here. The problem is that only one thread is running in the child process after the fork operation. With only one thread running the child can't pass control if the mutex is 0/locked and hence deadlocks. A solution is to move fork() up above the pthread_create(). In this manner two threads run in each process, and they can pass control.

CommentsGuest Name:Comment: