CS 105

“Tour of the Black Holes of Computing!”

Programming with Threads

Topics
 Threads
 Shared variables
 The need for synchronization
 Synchronizing with semaphores
 Thread safety and reentrancy
 Races and deadlocks

threads1.ppt
Traditional View of a Process
Process = process context + code, data, and stack

Process context Code, data, and stack

stack
Program context: SP
Data registers
Condition codes shared libraries
Stack pointer (SP)
brk
Program counter (PC) run-time heap
Kernel context: read/write data
VM structures PC read-only code/data
Descriptor table
brk pointer 0

–2– CS 105
Alternate View of a Process
Process = thread + code, data, and kernel context

Thread (main thread) Code and Data

shared libraries
stack
SP brk
run-time heap
read/write data
Thread context:
Data registers PC read-only code/data
Condition codes
0
Stack pointer (SP)
Program counter (PC)
Kernel context:
VM structures
Descriptor table
brk pointer

–3– CS 105
 A Process With Multiple Threads
Multiple threads can be associated with a process
 Each thread has its own logical control flow (sequence of PC
values)
 Each thread shares the same code, data, and kernel context
 Each thread has its own thread id (TID)
Thread 1 (main thread) Shared code and data Thread 2 (peer thread)
shared libraries
stack 1 stack 2
run-time heap

Thread 1 context: read/write data Thread 2 context:

Data registers read-only code/data Data registers
Condition codes Condition codes
0
SP1 SP2
PC1 Kernel context: PC2
VM structures
Descriptor table
brk pointer
–4– CS 105
Logical View of Threads
Threads associated with a process form a pool of peers
 Unlike processes, which form a tree hierarchy

Threads associated with process foo Process hierarchy

T2 P0
T4
T1
P1
shared code, data
and kernel context
sh sh sh

T5 T3
foo

bar
–5– CS 105
Concurrent Thread Execution
Two threads run concurrently (are concurrent) if their
logical flows overlap in time
Otherwise, they are sequential (just like processes)

Thread A Thread B Thread C

Examples:
 Concurrent: A & B, A&C
 Sequential: B & C

Time

–6– CS 105
Threads vs. Processes
How threads and processes are similar
 Each has its own logical control flow
 Each can run concurrently
 Each is context switched

How threads and processes are different

 Threads share code and data, processes (typically) do not
 Threads are somewhat less expensive than processes
 Process control (creating and reaping) is twice as expensive as
thread control
 Linux/Pentium III numbers:
» ~20K cycles to create and reap a process
» ~10K cycles to create and reap a thread

–7– CS 105
Posix Threads (Pthreads)
Interface
Pthreads: Standard interface for ~60 functions that
manipulate threads from C programs
 Creating and reaping threads
 pthread_create, pthread_join
 Determining your thread ID
 pthread_self
 Terminating threads
 pthread_cancel, pthread_exit
 exit [terminates all threads] , return [terminates current
thread]
 Synchronizing access to shared variables
 pthread_mutex_init, pthread_mutex_[un]lock
 pthread_cond_init, pthread_cond_[timed]wait

–8– CS 105
The Pthreads "hello, world"
Program
/*
* hello.c - Pthreads "hello, world" program
*/
#include "csapp.h" Thread attributes
(usually NULL)
void *howdy(void *vargp);

int main() { Thread arguments

pthread_t tid; (void *p)

Pthread_create(&tid, NULL, howdy, NULL);

Pthread_join(tid, NULL);
exit(0);
} return value
(void **p)
/* thread routine */
void *howdy(void *vargp) {
printf("Hello, world!\n");
return NULL;
}

–9– CS 105
 Execution of Threaded “hello,
world”
main thread

call Pthread_create()
Pthread_create() returns peer thread
call Pthread_join()
printf()
main thread waits for return NULL;
peer thread to terminate (peer thread
terminates)
Pthread_join() returns

exit()
terminates
main thread and
any peer threads

– 10 – CS 105
 Pros and Cons
of Thread-Based Designs
+ Easy to share data structures between threads
 E.g., logging information, file cache

+ Threads are more efficient than processes

– Unintentional sharing can introduce subtle and hard-

to-reproduce errors!
 Ease of data sharing is greatest strength of threads
 Also greatest weakness!

– 11 – CS 105
 Shared Variables in Threaded
C Programs
Question: Which variables in a threaded C program are
shared variables?
 Answer not as simple as “global variables are shared” and
“stack variables are private”

Requires answers to the following questions:

 What is the memory model for threads?
 How are variables mapped to memory instances?
 How many threads reference each of these instances?

– 12 – CS 105
 Threads Memory Model
Conceptual model:
 Each thread runs in the context of a process
 Each thread has its own separate thread context
 Thread ID, stack, stack pointer, program counter, condition codes, and
general purpose registers
 All threads share remaining process context
 Code, data, heap, and shared library segments of process virtual
address space
 Open files and installed handlers

Operationally, this model is not strictly enforced:

 Register values are truly separate and protected
 But any thread can read and write the stack of any other thread

Mismatch between conceptual and operational model is a source

of confusion and errors
– 13 – CS 105
 Example of Threads Accessing
Another Thread’s Stack
char **ptr; /* global */ /* thread routine */
void *thread(void *vargp)
int main() {
{ int myid = (int)vargp;
int i; static int svar = 0;
pthread_t tid;
char *msgs[N] = { printf("[%d]: %s (svar=%d)\n",
"Hello from foo", myid, ptr[myid], ++svar);
"Hello from bar" }
};
ptr = msgs;
for (i = 0; i < 2; i++) Peer threads access main thread’s stack
Pthread_create(&tid, indirectly through global ptr variable
NULL,
thread,
(void *)i);
Pthread_exit(NULL);
}

– 14 – CS 105
 Mapping Vars to Mem. Instances
Global var: 1 instance (ptr [data])

Local automatic vars: 1 instance (i.m, msgs.m )

char **ptr; /* global */ Local automatic var: 2 instances (

myid.p0[peer thread 0’s stack],
int main() myid.p1[peer thread 1’s stack]
{ )
int i;
pthread_t tid;
char *msgs[N] = { /* thread routine */
"Hello from foo", void *thread(void *vargp)
"Hello from bar" {
}; int myid = (int)vargp;
ptr = msgs; static int svar = 0;
for (i = 0; i < 2; i++)
Pthread_create(&tid, printf("[%d]: %s (svar=%d)\n",
NULL, myid, ptr[myid], ++svar);
thread, }
(void *)i);
Pthread_exit(NULL);
Local static var: 1 instance (svar [data])
}
– 15 – CS 105
 Shared Variable Analysis
Which variables are shared?
Variable Referenced by Referenced by Referenced by
instance main thread? peer thread 0? peer thread 1?

ptr yes yes yes

svar no yes yes
i.m yes no no
msgs.m yes yes yes
myid.p0 no yes no
myid.p1 no no yes

Answer: A variable x is shared iff multiple threads reference at least one instance of x. Thus:
 ptr, svar, and msgs are shared.
 i and myid are NOT shared.

– 16 – CS 105
 badcnt.c: An Improperly
Synchronized Threaded Program
unsigned int cnt = 0; /* shared */ /* thread routine */
void *count(void *arg) {
int main() { int i;
pthread_t tid1, tid2; for (i=0; i<NITERS; i++)
Pthread_create(&tid1, NULL, cnt++;
count, NULL); return NULL;
Pthread_create(&tid2, NULL, }
count, NULL);
linux> ./badcnt
Pthread_join(tid1, NULL); BOOM! cnt=198841183
Pthread_join(tid2, NULL);
linux> ./badcnt
if (cnt != (unsigned)NITERS*2) BOOM! cnt=198261801
printf("BOOM! cnt=%d\n",
cnt); linux> ./badcnt
else BOOM! cnt=198269672
printf("OK cnt=%d\n",
cnt);
cnt should be
} 200,000,000.
What went wrong?!
– 17 – CS 105
 Assembly Code for Counter
Loop
C code for counter loop
for (i=0; i<NITERS; i++) Corresponding asm code
cnt++;
.L9:
movl -4(%ebp),%eax
Head (Hi) cmpl $99999999,%eax
jle .L12
jmp .L10
.L12:
Load cnt (Li) movl cnt,%eax # Load
Update cnt (Ui) leal 1(%eax),%edx # Update
Store cnt (Si) movl %edx,cnt # Store
.L11:
movl -4(%ebp),%eax
Tail (Ti) leal 1(%eax),%edx
movl %edx,-4(%ebp)
jmp .L9
.L10:

– 18 – CS 105
 Concurrent Execution
Key idea: In general, any sequentially consistent
interleaving is possible, but some are incorrect!
 Ii denotes that thread i executes instruction I
 %eaxi is the contents of %eax in thread i’s context
i (thread) instri %eax1 %eax2 cnt
1 H1 - - 0
1 L1 0 - 0
1 U1 1 - 0
1 S1 1 - 1
2 H2 - - 1
2 L2 - 1 1
2 U2 - 2 1
2 S2 - 2 2
2 T2 - 2 2
1 T1 1 - 2
OK

– 19 – CS 105
 What Is
“Sequential Consistency?”
Two (or more) parallel executions are sequentially
consistent iff instructions of each thread (or
process) are executed in sequential order
 No restrictions on how threads relate to each other
 Each thread runs at arbitrary speed
 Any interleaving is legitimate
 Any (or all) instructions of B can run between any two
instructions of A

– 20 – CS 105
 Concurrent Execution (cont)
Incorrect ordering: two threads increment the counter,
but the result is 1 instead of 2

i (thread) instri %eax1 %eax2 cnt

1 H1 - - 0
1 L1 0 - 0
1 U1 1 - 0
2 H2 - - 0
2 L2 - 0 0
1 S1 1 - 1
1 T1 1 - 1
2 U2 - 1 1
2 S2 - 1 1
2 T2 - 1 1
Oops!

– 21 – CS 105
 Concurrent Execution (cont)
How about this ordering?
i (thread) instri %eax1 %eax2 cnt
1 H1
1 L1
2 H2
2 L2
2 U2
2 S2
1 U1
1 S1
1 T1
2 T2

We can clarify our understanding of concurrent

execution with the help of the progress graph

– 22 – CS 105
 Progress Graphs
A progress graph depicts
Thread 2 the discrete execution
state space of concurrent
threads.
T2
(L1, S2)
Each axis corresponds to
S2 the sequential order of
instructions in a thread.
U2
Each point corresponds to
a possible execution state
L2 (Inst1, Inst2).

E.g., (L1, S2) denotes state

H2
where thread 1 has
Thread 1 completed L1 and thread
H1 L1 U1 S1 T1
2 has completed S2.

– 23 – CS 105
 Trajectories in Progress
Graphs
Thread 2
A trajectory is a sequence
of legal state transitions
T2 that describes one possible
concurrent execution of
the threads.
S2

Example:
U2
H1, L1, U1, H2, L2,
S1, T1, U2, S2, T2
L2

H2
Thread 1
H1 L1 U1 S1 T1

– 24 – CS 105
 Critical Sections and Unsafe
Regions
Thread 2 L, U, and S form a
critical section with
respect to the shared
T2 variable cnt.

S2 Instructions in critical
sections (wrt to some
critical shared variable) should
section U2 Unsafe region not be interleaved.
wrt cnt

L2
Sets of states where such
interleaving occurs
form unsafe regions.
H2
Thread 1
H1 L1 U1 S1 T1

critical section wrt cnt

– 25 – CS 105
 Safe and Unsafe Trajectories
Thread 2

T2 Safe trajectory
Def: A trajectory is safe
iff it doesn’t enter any
S2 Unsafe region Unsafe part of an unsafe region.
trajectory
critical Claim: A trajectory is
section U2
correct (wrt cnt) iff it is
wrt cnt
safe.
L2

H2
Thread 1
H1 L1 U1 S1 T1

critical section wrt cnt

– 26 – CS 105
 Semaphores
Question: How can we guarantee a safe trajectory?
 Synchronize threads so they never enter unsafe state
Classic solution: Dijkstra's P and V operations on
semaphores
 Semaphore: non-negative integer synchronization variable
 P(s): while(1){[ if (s>0) {s--; break}] wait_a_while()}
» Dutch for “test” ("Proberen“)
 V(s): [ s++; ]
» Dutch for “increment” ("Verhogen")
 OS guarantees that operations between brackets [ ] are
executed indivisibly
 Only one P or V operation at a time can modify s
 When while loop in process X terminates, only that process has
decremented s

Semaphore invariant: (s >= 0)

– 27 – CS 105
 Safe Sharing with Semaphores
Here is how we would use P and V operations to
synchronize the threads that update cnt

/* Semaphore s is initially 1 */

/* Thread routine */
void *count(void *arg)
{
int i;

for (i=0; i<NITERS; i++) {

P(s);
cnt++;
V(s);
}
return NULL;
}

– 28 – CS 105
 Safe Sharing With
Semaphores
Thread 2
1 1 0 0 0 0 1 1
Provide mutually
T2
1 1 0 0 0 0 1 1
exclusive access to
shared variable by
V(s) surrounding critical
0 0 Forbidden region 0 0
-1 -1 -1 -1
section with P and V
S2 operations on semaphore
0 0 0 0
-1 -1 -1 -1 s (initially set to 1).
U2 Unsafe region
0 0 0 0
-1 -1 -1 -1 Semaphore invariant
L2 creates forbidden region
-1 -1 -1 -1
0 0 0 0 that encloses unsafe
P(s)
region and is never
1 1 0 0 0 0 1 1 touched by any trajectory.
H2
1 1 0 0 0 0 1 1
H1 P(s) L1 U1 S1 V(s) T1
Initially Thread 1
s=1
– 29 – CS 105
 POSIX Semaphores
/* Initialize semaphore sem to value */
/* pshared=0 if thread, pshared=1 if process */
void Sem_init(sem_t *sem, int pshared, unsigned int value) {
if (sem_init(sem, pshared, value) == -1)
unix_error("Sem_init");
}

/* P operation on semaphore sem */

void P(sem_t *sem) {
if (sem_wait(sem) == -1)
unix_error("P");
}

/* V operation on semaphore sem */

void V(sem_t *sem) {
if (sem_post(sem) == -1)
unix_error("V");
}

– 30 – CS 105
 Sharing With POSIX Semaphores
/* goodcnt.c - properly sync’d /* thread routine */
counter program */ void *count(void *arg)
#include "csapp.h" {
#define NITERS 10000000 int i;

unsigned int cnt; /* counter */ for (i=0; i<NITERS; i++) {

sem_t sem; /* semaphore */ P(&sem);
cnt++;
int main() { V(&sem);
pthread_t tid1, tid2; }
return NULL;
Sem_init(&sem, 0, 1); /* sem=1 */ }

/* create 2 threads and wait */

...

if (cnt != (unsigned)NITERS*2)
printf("BOOM! cnt=%d\n", cnt);
else
printf("OK cnt=%d\n", cnt);
exit(0);
}
– 31 – CS 105
 Signaling With Semaphores
producer shared consumer
thread buffer thread

Common synchronization pattern:

 Producer waits for slot, inserts item in buffer, and “signals” consumer
 Consumer waits for item, removes it from buffer, and “signals”
producer
 “Signals” in this context has nothing to do with Unix signals

Examples
 Multimedia processing:
 Producer creates MPEG video frames, consumer renders the frames
 Event-driven graphical user interfaces
 Producer detects mouse clicks, mouse movements, and keystrokes and
inserts corresponding events in buffer
 Consumer retrieves events from buffer and paints display
– 32 – CS 105
 Producer-Consumer on a Buffer
That Holds One Item
/* buf1.c - producer-consumer int main() {
on 1-element buffer */ pthread_t tid_producer;
#include “csapp.h” pthread_t tid_consumer;

#define NITERS 5 /* initialize the semaphores */

Sem_init(&shared.empty, 0, 1);
void *producer(void *arg); Sem_init(&shared.full, 0, 0);
void *consumer(void *arg);
/* create threads and wait */
struct { Pthread_create(&tid_producer, NULL,
int buf; /* shared var */ producer, NULL);
sem_t full; /* sems */ Pthread_create(&tid_consumer, NULL,
sem_t empty; consumer, NULL);
} shared; Pthread_join(tid_producer, NULL);
Pthread_join(tid_consumer, NULL);

exit(0);
}

– 33 – CS 105
 Producer-Consumer (cont)
Initially: empty = 1, full = 0.

/* producer thread */ /* consumer thread */

void *producer(void *arg) { void *consumer(void *arg) {
int i, item; int i, item;

for (i=0; i<NITERS; i++) { for (i=0; i<NITERS; i++) {

/* produce item */ /* read item from buf */
item = i; P(&shared.full);
printf("produced %d\n", item = shared.buf;
item); V(&shared.empty);

/* write item to buf */ /* consume item */

P(&shared.empty); printf("consumed %d\n",
shared.buf = item; item);
V(&shared.full); }
} return NULL;
return NULL; }
}

– 34 – CS 105
 Thread Safety
Functions called from a thread must be thread-safe

We identify four (non-disjoint) classes of thread-unsafe

functions:
 Class 1: Failing to protect shared variables
 Class 2: Relying on persistent state across invocations
 Class 3: Returning pointer to static variable
 Class 4: Calling thread-unsafe functions

– 35 – CS 105
 Thread-Unsafe Functions
Class 1: Failing to protect shared variables
 Fix: Use P and V semaphore operations
 Issue: Synchronization operations will slow down code
 Example: goodcnt.c

– 36 – CS 105
 Thread-Unsafe Functions (cont)
Class 2: Relying on persistent state across multiple
function invocations
 Random number generator relies on static state
 Fix: Rewrite function so that caller passes in all necessary
state

/* rand - return pseudo-random integer on 0..32767 */

int rand(void)
{
static unsigned int next = 1;
next = next*1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}

/* srand - set seed for rand() */

void srand(unsigned int seed)
{
next = seed;
}

– 37 – CS 105
 Thread-Unsafe Functions (cont)
Class 3: Returning pointer struct hostent
*gethostbyname(char* name)
to static variable {
static struct hostent h;
Fixes: <contact DNS and fill in h>
 1. Rewrite code so caller return &h;
}
passes pointer to struct
» Issue: Requires hostp = Malloc(...));
changes in caller gethostbyname_r(name, hostp);
and callee
 2. Lock-and-copy
struct hostent
» Issue: Requires only
*gethostbyname_ts(char *p)
simple changes in {
caller (and none in struct hostent *q = Malloc(...);
callee) P(&mutex); /* lock */
» However, caller must p = gethostbyname(name);
*q = *p; /* copy */
free memory
V(&mutex);
return q;
}
– 38 – CS 105
 Thread-Unsafe Functions
Class 4: Calling thread-unsafe functions
 Calling one thread-unsafe function makes an entire function
thread-unsafe

 Fix: Modify the function so it calls only thread-safe functions

– 39 – CS 105
 Reentrant Functions
A function is reentrant iff it accesses NO shared variables when called from multiple threads
 Reentrant functions are a proper subset of the set of thread-safe functions

All functions

Thread-safe
NOTE: The fixes to Class 2 and 3 thread-unsafe functions require modifying the function to make it reentrant (only first fix for Class 3 is reentrant)

functions
Thread-unsafe
functions
Reentrant
functions

– 40 – CS 105
 Thread-Safe Library Functions
Most functions in the Standard C Library (at the back of
your K&R text) are thread-safe
 Examples: malloc, free, printf, scanf

All Unix system calls are thread-safe

Library calls that aren’t thread-safe:
Thread-unsafe function Class Reentrant version
asctime 3 asctime_r
ctime 3 ctime_r
gethostbyaddr 3 gethostbyaddr_r
gethostbyname 3 gethostbyname_r
inet_ntoa 3 (none)
localtime 3 localtime_r
rand 2 rand_r

– 41 – CS 105
 Races
Race happens when program correctness depends on one
thread reaching point x before another thread reaches
point y
/* a threaded program with a race */
int main() {
pthread_t tid[N];
int i;
for (i = 0; i < N; i++)
Pthread_create(&tid[i], NULL, thread, &i);
for (i = 0; i < N; i++)
Pthread_join(tid[i], NULL);
exit(0);
}

/* thread routine */
void *thread(void *vargp) {
int myid = *((int *)vargp);
printf("Hello from thread %d\n", myid);
return NULL;
– 42 – } CS 105
 Deadlock
Locking introduces
Thread 2 potential for deadlock:
V(s) deadlock waiting for a condition
forbidden state that will never be true.
region for s
Any trajectory that enters
V(t)
deadlock region will
eventually reach
deadlock state, waiting for
P(s)
either s or t to become
deadlock forbidden nonzero.
region region for t
P(t) Other trajectories luck out
and skirt deadlock region.

Unfortunate fact: deadlock

P(s) P(t) V(s) V(t) Thread 1 is often non-deterministic.
Initially, s=t=1
– 43 – CS 105
 Threads Summary
Threads provide another mechanism for writing
concurrent programs
Threads are growing in popularity
 Somewhat cheaper than processes
 Easy to share data between threads

However, the ease of sharing has a cost:

 Easy to introduce subtle synchronization errors
 Tread carefully with threads!

For more info:

 D. Butenhof, “Programming with Posix Threads”, Addison-
Wesley, 1997

– 44 – CS 105