POSIX Threads

In the UNIX environment a thread:

• Exists within a process and uses the process
resources.
POSIX Threads • Has its own independent flow of control as
long as its parent process exists or the OS
supports it.
HUJI • May share the process resources with other
Spring 2007 threads that act equally independently (and
dependently).
• Dies if the parent process dies (user thread).

1 2

Pthread Attributes Why Threads

A thread can possess an independent flow of • Managing threads requires fewer system
control and be schedulable because it resources than managing processes.
– fork() Versus pthread_create()
maintains its own:
• All threads within a process share the same
– Stack. address space.
– Registers. (CPU STATE!) – Inter-thread communication is more efficient and
– Scheduling properties (such as policy or priority). easier to use than inter-process communication
(IPC).
– Set of pending and blocked signals.
• Overlapping CPU work with I/O.
– Thread specific data. • Priority/real-time scheduling.
• Asynchronous event handling.
3 4

Pthread Library Creating Threads

The subroutines which comprise the Pthreads
API can be informally grouped into 3 major • Initially, your main() program comprises a
classes: single, default thread. All other threads must
– Thread management: The first class of functions be explicitly created by the programmer.
work directly on threads.
– Mutexes: The second class of functions deals int pthread_create (
with synchronization, called a "mutual exclusion". pthread_t *thread,
– Condition variables: The third class of functions
addresses communications between threads that const pthread_attr_t *attr=NULL,
share a mutex.
void *(*start_routine) (void *),
How to Compile? void *arg) ;
#include <pthread.h>
gcc ex3.c –o ex3 –lpthread 5 6

1
 #define NUM_THREADS 5

void *PrintHello(void *index) {

printf("\n%d: Hello World!\n", index);
Terminating Thread Execution pthread_exit(NULL);
}
int main(int argc, char *argv[]) {
• The thread returns from its starting pthread_t threads[NUM_THREADS];
int res, t;
routine (the main routine for the initial for(t=0;t<NUM_THREADS;t++){
thread). printf("Creating thread %d\n", t);
res = pthread_create(&threads[t], NULL,
• The thread makes a call to the PrintHello, (void *)t);
pthread_exit(status) subroutine. if (res){
printf("ERROR\n");
• The entire process is terminated due to exit(-1);
}
a call to either the exec or exit }
subroutines. pthread_exit(NULL);
}

7 8

Joining Threads Example Cont.

int pthread_join(pthread_t thread, // main thread waits for the other threads
void **value_ptr); for(t=0;t<NUM_THREADS;t++) {
res = pthread_join(threads[t], (void **)&status);
if (res) {
printf("ERROR \n");
• The pthread_join() subroutine blocks the exit(-1);
calling thread until the specified thread thread }
printf("Completed join with thread %d status=
terminates. %d\n",t, status);
• The programmer is able to obtain the target }
pthread_exit(NULL);
thread's termination return status if specified }
through pthread_exit(void *status).
9 10

Example 1 - pthread_join
void *printme(void *ip) {
int *i;
i = (int *) ip;
printf("Hi. I'm thread %d\n", *i);
return NULL;
}
main() {
Few Examples int i, vals[4];
pthread_t tids[4];
void *retval;
for (i = 0; i < 4; i++) {
vals[i] = i;
pthread_create(tids+i, NULL, printme, vals+i);
}
for (i = 0; i < 4; i++) {
printf("Trying to join with tid %d\n", i);
pthread_join(tids[i], &retval);
printf("Joined with tid %d\n", i);
11 } 12
}

2
 Example 2 - pthread_exit
void *printme(void *ip) {

Output int *i;

i = (int *) ip;
Trying to join with tid 0 printf("Hi. I'm thread %d\n", *i);
pthread_exit(NULL);
Hi. I'm thread 0 }
Hi. I'm thread 1 main() {
int i, vals[4];
Hi. I'm thread 2 pthread_t tids[4];
Hi. I'm thread 3 void *retval;
Joined with tid 0 for (i = 0; i < 4; i++) {
vals[i] = i;
Trying to join with tid 1 pthread_create(tids+i, NULL, printme, vals+i);
Joined with tid 1 }
pthread_exit(NULL);
Trying to join with tid 2 for (i = 0; i < 4; i++) {
Joined with tid 2 printf("Trying to join with tid %d\n", i);
Trying to join with tid 3 pthread_join(tids[i], &retval);
printf("Joined with tid %d\n", i);
Joined with tid 3 }
13 14
}

Example 3 - Exit
void *printme(void *ip) {
The Output int *i;
i = (int *) ip;
printf("Hi. I'm thread %d\n", *i);
Hi. I'm thread 0 }
exit(0);

Hi. I'm thread 1 main() {

int i, vals[4];
Hi. I'm thread 2 pthread_t tids[4];
void *retval;
for (i = 0; i < 4; i++) {
Hi. I'm thread 3 vals[i] = i;
pthread_create(tids+i, NULL, printme, vals+i);
}
for (i = 0; i < 4; i++) {
printf("Trying to join with tid %d\n", i);
pthread_join(tids[i], &retval);
printf("Joined with tid %d\n", i);
}
15 16
}

Output?
Trying to join with tid 0
Hi. I'm thread 0 Pthread Synchronization

17 18

3
 Mutex
Critical Section
• Mutex variables are one of the primary
Balance 1st thread 2nd thread means of implementing thread
1000$ Read balance: synchronization and for protecting shared
1000$ data when multiple writes occur.
1000$ Read balance: • A mutex variable acts like a "lock" protecting
1000$ access to a shared data resource.
1000$ Deposit: 200$ • The basic concept of a mutex as used in
1000$ Deposit: 200$ Pthreads is that only one thread can lock (or
own) a mutex variable at any given time.
1200$ Update balance
1200$ Update balance 19 20

Work Flow Creating and Destroying Mutex

Mutex variables must be declared with type
A typical sequence in the use of a mutex is as pthread_mutex_t, and must be initialized before
follows: they can be used:
• Create and initialize a mutex variable. – Statically, when it is declared. For example:
• Several threads attempt to lock the mutex. pthread_mutex_t mymutex =
PTHREAD_MUTEX_INITIALIZER;
• Only one succeeds and that thread owns the
mutex. – Dynamically,
pthread_mutex_init(mutex, attr)
• The owner thread performs some set of actions.
This method permits setting mutex object attributes (for
• The owner unlocks the mutex. default setting use NULL).
• Another thread acquires the mutex and repeats pthread_mutex_destroy(mutex) should be
the process. used to free a mutex object when is no longer
• Finally the mutex is destroyed. needed.
21 22

Locking Mutex Unlock Mutex

• The pthread_mutex_lock(mutex) • pthread_mutex_unlock(mutex)
routine is used by a thread to acquire a will unlock a mutex if called by the
lock on the specified mutex variable. owning thread. Calling this routine is
• If the mutex is already locked by required after a thread has completed
another thread, this call will block the its use of protected data.
calling thread until the mutex is • An error will be returned if:
unlocked. – If the mutex was already unlocked.
– If the mutex is owned by another thread.

23 24

4
 Example Fixed Example
pthread_mutex_lock (&mut);
Thread 1: Thread 2: a = counter;
a++;
a = counter;
counter = a;
b = counter; pthread_mutex_unlock (&mut);
a++;
pthread_mutex_lock (&mut);
b--; b = counter;
counter = a; b--;
counter = b; counter = b;
pthread_mutex_unlock (&mut);
25 26

Conditional Variables
Condition Variables
• While mutexes implement synchronization by • Useful when a thread needs to wait for a
controlling thread access to data, condition certain condition to be true.
variables allow threads to synchronize based • In pthreads, there are four relevant
upon the actual value of data. procedures involving condition variables:
– pthread_cond_init(pthread_cond_t *cv,
• Without condition variables, The programmer NULL);
would need to have threads continually polling – pthread_cond_destroy(pthread_cond_t
(usually in a critical section), to check if the *cv);
– pthread_cond_wait(pthread_cond_t *cv,
condition is met. pthread_mutex_t *lock);
• A condition variable is a way to achieve the same – pthread_cond_signal(pthread_cond_t
*cv);
goal without polling (a.k.a. busy wait)
27 28

Creating and Destroying

Conditional Variables pthread_cond_wait
• Condition variables must be declared with type • pthread_cond_wait(cv, lock) is called
pthread_cond_t, and must be initialized by a thread when it wants to block and wait
before they can be used. for a condition to be true.
• Statically, when it is declared. For example: • It is assumed that the thread has locked the
pthread_cond_t myconvar = mutex indicated by the second parameter.
PTHREAD_COND_INITIALIZER; • The thread releases the mutex, and blocks
• Dynamically until awakened by a
pthread_cond_init(cond, attr); pthread_cond_signal() call from another
Upon successful initialization, the state of the thread.
condition variable becomes initialized. • When it is awakened, it waits until it can
• pthread_cond_destroy(cond) should be acquire the mutex, and once acquired, it
used to free a condition variable that is no returns from the pthread_cond_wait()
longer needed. 29 call. 30

5
 typedef struct {
pthread_cond_signal pthread_mutex_t *lock;
pthread_cond_t *cv;
• pthread_cond_signal() checks to see if int *ndone;
int id;
there are any threads waiting on the specified } TStruct;
condition variable. If not, then it simply returns. #define NTHREADS 5
void *barrier(void *arg) {
• If there are threads waiting, then one is TStruct *ts;
awakened. int i;
ts = (TStruct *) arg;
• There can be no assumption about the order in printf("Thread %d -- waiting for barrier\n", ts->id);
pthread_mutex_lock(ts->lock);
which threads are awakened by *ts->ndone = *ts->ndone + 1;
pthread_cond_signal() calls. if (*ts->ndone < NTHREADS) {
pthread_cond_wait(ts->cv, ts->lock);
• It is natural to assume that they will be }
awakened in the order in which they waited, but else {
that may not be the case… for (i = 1; i < NTHREADS; i++)
pthread_cond_signal(ts->cv);
• Use loop or pthread_cond_broadcast() to }
pthread_mutex_unlock(ts->lock);
awake all waiting threads. printf("Thread %d -- after barrier\n", ts->id);
31 32
}

main() {
TStruct ts[NTHREADS];
pthread_t tids[NTHREADS];
int i, ndone;
Output
pthread_mutex_t lock; Thread 0 -- waiting for barrier
pthread_cond_t cv;
void *retval; Thread 1 -- waiting for barrier
pthread_mutex_init(&lock, NULL); Thread 2 -- waiting for barrier
pthread_cond_init(&cv, NULL);
ndone = 0;
Thread 3 -- waiting for barrier
for (i = 0; i < NTHREADS; i++) { Thread 4 -- waiting for barrier
ts[i].lock = &lock; Thread 4 -- after barrier
ts[i].cv = &cv;
ts[i].ndone = &ndone; Thread 0 -- after barrier
ts[i].id = i; Thread 1 -- after barrier
}
for (i = 0; i < NTHREADS; i++)
Thread 2 -- after barrier
pthread_create(tids+i, NULL, barrier, ts+i); Thread 3 -- after barrier
for (i = 0; i < NTHREADS; i++) done
pthread_join(tids[i], &retval); 33 34
printf("done\n"); }

Classical Problems of Synchronization Bounded-Buffer Problem

• Bounded-Buffer Problem • One buffers that can hold N items
• Readers and Writers Problem • Semaphore mutex initialized to the value 1
• Dining-Philosophers Problem • Semaphore full initialized to the value 0
• Semaphore empty initialized to the value N

35 36

6
 Bounded-Buffer Problem – Bounded-Buffer Problem –
Cont. Cont.
• The structure of the producer process • The structure of the consumer process

while (true) { while (true) {

P (full);
// produce an item P (mutex);

P (empty); // remove an item from buffer

P (mutex);
V (mutex);
// add the item to the buffer V (empty);

V (mutex); // consume the removed item

V (full);
} }
37 38

Readers-Writers Problem
Readers-Writers Problem – Cont.
• A data set is shared among a number of concurrent processes
– Readers – only read the data set; they do not perform any updates • The structure of a writer process
– Writers – can both read and write.

• Problem while (true) {

– allow multiple readers to read at the same time.
P (wrt) ;
– Only one single writer can access the shared data at the same time.
– If a writer is writing to the file, no reader may read it
// writing is performed
• Shared Data
– Data set
– Semaphore mutex initialized to 1. V (wrt) ;
– Semaphore wrt initialized to 1. }
– Integer readcount initialized to 0. 39 40

Readers-Writers Problem – Cont. Writer-Priority: The Writer

• The structure of a reader process • Extra semaphores and variables:
– Semaphore read initialized to 1 – inhibits readers when a writer wants to
write.
while (true) { – Integer writecount initialized to 0 – controls the setting of semaphore read.
P (mutex) ; Any problem?? – Semaphore wmutex initialized to 1 – controls the updating of writecount.
readcount ++ ;
if (readcount == 1) P (wrt) ; What if a writer is while (true) {
V (mutex) waiting to write P(wmutex)
writecount++;
but there are if (writecount ==1) P(read)
// reading is performed
readers that read V(wmutex)
all the time? P (wrt) ;
P (mutex) ;
// writing is performed
readcount--;
V (wrt) ;
if (readcount == 0) V (wrt) ;
P(wmutex)
V (mutex) ; writecount--;
}
Writers are subject to
if (writecount ==0) V(read)
starvation! V(wmutex)
41
} 42

7
 Writer-Priority: The Reader
while (true) { Queue semaphore, initialized to 1:
Dining-Philosophers Problem
P(queue) Since ‘read’ can not be a queue
P(read) (otherwise, writer won’t skip
multiple readers), we have to
P (rmutex) ;
maintain another semaphore
readcount ++ ;
if (readcount == 1) P (wrt) ;
V (rmutex)
V(read)
V(queue)
// reading is performed
P (rmutex) ;
readcount - - ;
if (readcount == 0) V (wrt) ; Shared data
V (rmutex) ; Bowl of rice (data set)
}
43 Semaphore chopstick [5] initialized to 1 44

Dining-Philosophers Problem – Cont. Dining Philosophers Problem

• An abstract problem demonstrating some
• The structure of Philosopher i: fundamental limitations of the deadlock-free
synchronization
While (true) {
P ( chopstick[i] ); • There is no symmetric solution
P ( chopStick[ (i + 1) % 5] );
// eat • Solutions
V ( chopstick[i] );
V (chopstick[ (i + 1) % 5] ); – Execute different code for odd/even
– Give them another fork
// think
} – Allow at most 4 philosophers at the table
• Does it solve the problem? – Randomized (Lehmann-Rabin)
45 46