Concurrency with Threads and Synchronization
Shuaiwen Song
Objectives
• To learn what a thread is
• Tounderstandthedifferencebetween processesand
threads
• To learn about programming with threads using the pthread library
• Data Race and Race condition
• Protecting shared resource: Synchronization, Atomic
Operations, Immutable Data
• Synchronization: Semaphores, Mutex, Conditional Variables, read-write locks, spin locks, etc.
Process Pros
• Clean Sharing Model
– Global variables (address spaces) are not shared – File tables (file descriptors) are shared
• Simple and straightforward
– Forking a child process is easy
– Reaping child processes is simple
– Processes are isolated for protection
• Forking a process is expensive
– Need to clone parent’s memory space
– Need to setup a separate context for child
Note: the concept of context switch and why it has high overhead: https://en.wikipedia.org/wiki/Context_switch#:~:text=In%20computing%2C%20 a%20context%20switch,of%20a%20multitasking%20operating%20system.
Process Cons
• Forking a process is expensive
– Need to clone parent’s memory space
– Need to setup a separate context for child
• Non-trivial to share data between processes – Need to use files/pipes to share data
– Can use shared memory
– Lots of overhead!
Process Cons
View of a Process
• Process = context + code, data, and stack
Process context
Code, data, and stack
stack
shared libraries
run-time heap
read/write data
read-only code/data
SP
Program context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC) Kernel context:
VM structures Descriptor table
PC
0
View of a Process
• Process = context + code, data, and stack
Process context
Code, data, and stack
stack
shared libraries
run-time heap
read/write data
read-only code/data
SP
Program context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC)
Kernel context: VM structures
Descriptor table
PC
0
Alternate View of a Process
• Process = thread + code, data, and kernel context
SP
Thread (main thread)
stack
Code and Data
shared libraries
run-time heap
read/write data
read-only code/data
Thread context:
Data registers Condition codes Stack pointer (SP) Program counter (PC)
PC
0
Kernel context: VM structures
Descriptor table
A Process With Multiple Threads
• Multiple threads can be associated with a process – Eachthreadhasitsownlogicalcontrolflow
Thread 1 (main thread)
stack 1
Shared code and data Thread 2 (peer thread)
stack 2
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
0
Thread 2 context: Data registers Condition codes SP2
PC2
Kernel context: VM structures
Descriptor table
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Eachthreadhasitsownlogicalcontrolflow
– Eachthreadsharesthesamecode,data,andkernelcontext
Thread 1 (main thread)
stack 1
Shared code and data Thread 2 (peer thread)
stack 2
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
0
Thread 2 context: Data registers Condition codes SP2
PC2
Kernel context: VM structures
Descriptor table
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Eachthreadhasitsownlogicalcontrolflow
– Eachthreadsharesthesamecode,data,andkernelcontext – Eachthreadhasitsownstackforlocalvariables
Thread 1 (main thread)
stack 1
Shared code and data Thread 2 (peer thread)
stack 2
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
0
Thread 2 context: Data registers Condition codes SP2
PC2
Kernel context: VM structures
Descriptor table
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Eachthreadhasitsownlogicalcontrolflow
– Eachthreadsharesthesamecode,data,andkernelcontext
– Eachthreadhasitsownstackforlocalvariables • but not protected from other threads
Thread 1 (main thread)
stack 1
Shared code and data
Thread 2 (peer thread)
stack 2
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
0
Thread 2 context: Data registers Condition codes SP2
PC2
Kernel context: VM structures
Descriptor table
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Eachthreadhasitsownlogicalcontrolflow
– Eachthreadsharesthesamecode,data,andkernelcontext
– Eachthreadhasitsownstackforlocalvariables • but not protected from other threads
– Eachthreadhasitsownthreadid(TID)
Thread 1 (main thread)
stack 1
Shared code and data
Thread 2 (peer thread)
stack 2
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
0
Thread 2 context: Data registers Condition codes SP2
PC2
Kernel context: VM structures
Descriptor table
OS: Concept of a Thread
Process
(typically functions)
Threads
• Processes
– Represent an entire program
• Threads
– Represents smaller chunks of code
OS: Concept of a Thread
Process
(typically functions)
Threads
• Processes
– Represent an entire program – High Overhead context switch
• Threads
– Represents smaller chunks of code – Lower Overhead context switch
Logical View of Threads
• Threads associated with process form a pool of peers – Unlike processes which form a tree hierarchy
Threads associated with process foo
Process hierarchy P0
P1
T2 T1
T4
shared code, data and kernel context
sh
foo
bar
sh sh
T5
T3
Threads vs. Processes
• Howthreadsandprocessesaresimilar – Each has its own logical control flow
– Each can run concurrently with others
– Each is context switched
Threads vs. Processes
• Howthreadsandprocessesaresimilar – Each has its own logical control flow
– Each can run concurrently with others
– Each is context switched
• Howthreadsandprocessesaredifferent – Threads share code and some data
• Processes (typically) do not
Threads vs. Processes
• Howthreadsandprocessesaresimilar – Each has its own logical control flow
– Each can run concurrently with others
– Each is context switched
• Howthreadsandprocessesaredifferent – Threads share code and some data
• Processes (typically) do not
– Threads are somewhat less expensive than processes
• Process control is twice as expensive as thread control • Linux numbers:
– ~20K cycles to create and reap a process
– ~10K cycles (or less) to create and reap a thread
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Thread A Thread B Thread C
Time
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Thread A Thread B Thread C
Time
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Thread A Thread B Thread C
Time
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Thread A Thread B Thread C
Time
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Thread A Thread B Thread C
Time
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Thread A Thread B Thread C
Time
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
– Concurrent: A & B, A&C – Sequential: B & C
Time
Thread A
Thread B
Thread C
• SingleCoreProcessor – Simulate parallelism by
time slicing
Thread A Thread B Thread C
Concurrent Threads
• Multi-CoreProcessor – Can have true
parallelism
Thread A Thread B Thread C
Time
Run 3 threads on 2 cores
Posix Threads (Pthreads) Interface
• Pthreads: Standard interface for ~60 functions that manipulate threads from C programs
Posix Threads (Pthreads) Interface
• Pthreads: Standard interface for ~60 functions that manipulate threads from C programs
– Creating and reaping threads • pthread_create()
• pthread_join()
Posix Threads (Pthreads) Interface
• Pthreads: Standard interface for ~60 functions that manipulate threads from C programs
– Creating and reaping threads • pthread_create()
• pthread_join()
Can only wait for a specific thread to terminate
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()
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()
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_exit() [terminates current threads] • exit() [terminates all threads]
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program */
#include “csapp.h”
void *thread(void *vargp);
int main() { pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL); Pthread_join(tid, NULL);
exit(0);
}
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL; }
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program */
#include “csapp.h”
void *thread(void *vargp);
int main() { pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL); Pthread_join(tid, NULL);
exit(0);
}
thread routine that the new thread executes
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL; }
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program */
#include “csapp.h”
void *thread(void *vargp);
int main() { pthread_t tid;
thread id
Pthread_create(&tid, NULL, thread, NULL); Pthread_join(tid, NULL);
exit(0);
}
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL; }
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program */
#include “csapp.h”
void *thread(void *vargp);
int main() { pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL); Pthread_join(tid, NULL);
exit(0);
}
Thread attributes (usually NULL)
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL;
}
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program */
#include “csapp.h”
void *thread(void *vargp);
int main() { pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL); Pthread_join(tid, NULL);
exit(0);
}
Thread arguments (void *p)
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL; }
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program */
#include “csapp.h”
void *thread(void *vargp);
int main() { pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL); Pthread_join(tid, NULL);
exit(0);
}
return value (void **p)
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL; }
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program */
#include “csapp.h”
void *thread(void *vargp);
int main() { pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL);
Pthread_join(tid, NULL);
exit(0); }
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL; }
Execution of Threaded“hello, world”
main thread
Execution of Threaded“hello, world”
main thread
call Pthread_create()
main thread
call Pthread_create()
Execution of Threaded“hello, world”
peer thread
main thread
call Pthread_create()
call Pthread_join()
main thread waits for peer thread to terminate
peer thread
Execution of Threaded“hello, world”
main thread
call Pthread_create()
call Pthread_join()
main thread waits for peer thread to terminate
peer thread
printf() return NULL;
(peer thread terminates)
Execution of Threaded“hello, world”
main thread
call Pthread_create()
call Pthread_join()
main thread waits for peer thread to terminate
Pthread_join() returns
peer thread
printf() return NULL;
(peer thread terminates)
Execution of Threaded“hello, world”
main thread
call Pthread_create()
call Pthread_join()
main thread waits for peer thread to terminate
Pthread_join() returns
exit()
terminates main thread and
any peer threads
peer thread
printf() return NULL;
(peer thread terminates)
Execution of Threaded“hello, world”
Passing argument
int main() {
int i; pthread_t tid;
for (i = 0; i < 2; i++)
pthread_create(&tid, NULL, thread, (void *)&i);
pthread_exit(NULL);
}
void *thread(void *vargp) {
int myid = (int)vargp; printf("hello from [%d]\n", myid); return NULL;
}
Passing argument
int main() {
int i; pthread_t
tid;
for (i = 0; i < 2; i++)
pthread_create(&tid, NULL, thread, (void *)&i);
pthread_exit(NULL);
}
void *thread(void *vargp) {
int myid = *((int *)vargp); printf("hello from [%d]\n", myid); return NULL;
}
Passing argument
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int) tid); pthread_join(tid, NULL);
printf("Main thread joined with peer thread.\n");
return 0; }
void *thread (void *vargp) {
int arg = *((int*) vargp); printf("hello from thread %X!\n", arg); return NULL;
}
Passing argument
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int) tid); pthread_join(tid, NULL);
printf("Main thread joined with peer thread.\n");
return 0; }
void *thread (void *vargp) {
int arg = *((int*) vargp); printf("hello from thread %X!\n", arg); return NULL;
}
Passing argument
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int) tid); pthread_join(tid, NULL);
printf("Main thread joined with peer thread.\n");
return 0; }
void *thread (void *vargp) {
int arg = *((int*) vargp); printf("hello from thread %X!\n", arg); return NULL;
}
Returning value
int main (int argc, char *argv[]) { pthread_t tid;
int ret_value;
pthread_create(&tid, NULL, thread, NULL); pthread_join(tid, (void **)(&ret_value)); printf("Main thread joined with peer thread: %X.\n",
ret_value);
return 0; }
void *thread (void *vargp) { return (int *) 0xDEADBEEF;
}
Returning pointer
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF; int* ret_value;
printf("Main thread creating peer thread.\n");
pthread_create(&tid, NULL, thread, &thread_arg);
printf("Main thread waiting for peer thread %u to complete...\n", (unsigned int)(tid));
pthread_join(tid, (void **)(&ret_value));
printf("Main thread joined with peer thread:%X.\n", *ret_value);
free(ret_value); return 0; }
void *thread (void *vargp) {
int arg = *((int*)vargp);
printf("hello from thread: %X!\n", arg); int *ret = (int*)malloc(sizeof(int)); *ret = arg;
return ret;}
Returning pointer
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF; int* ret_value;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int)(tid)); pthread_join(tid, (void **)(&ret_value)); printf("Main thread joined with peer thread:%X.\n",
*ret_value); free(ret_value); return 0; }
void *thread (void *vargp) {
int arg = *((int*)vargp);
printf("hello from thread: %X!\n", arg); int *ret = (int*)malloc(sizeof(int)); *ret = arg;
return ret;}
Returning pointer
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF; int* ret_value;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int)(tid)); pthread_join(tid, (void **)(&ret_value)); printf("Main thread joined with peer thread:%X.\n",
*ret_value); free(ret_value); return 0; }
void *thread (void *vargp) {
int arg = *((int*)vargp);
printf("hello from thread: %X!\n", arg); int *ret = (int*)malloc(sizeof(int)); *ret = arg;
return ret;}
Returning pointer
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF; int* ret_value;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int)(tid));
pthread_join(tid, (void **)(&ret_value));
printf("Main thread joined with peer thread:%X.\n", *ret_value);
free(ret_value); return 0; }
void *thread (void *vargp) {
int arg = *((int*)vargp);
printf("hello from thread: %X!\n", arg); int *ret = (int*)malloc(sizeof(int)); *ret = arg;
return ret;}
Returning pointer
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF; int* ret_value;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int)(tid)); pthread_join(tid, (void **)(&ret_value)); printf("Main thread joined with peer thread:%X.\n",
*ret_value);
free(ret_value); return 0; }
void *thread (void *vargp) {
int arg = *((int*)vargp);
printf("hello from thread: %X!\n", arg); int *ret = (int*)malloc(sizeof(int)); *ret = arg;
return ret;}
Returning pointer
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF; int* ret_value;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, &thread_arg); printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int)(tid)); pthread_join(tid, (void **)(&ret_value)); printf("Main thread joined with peer thread:%X.\n",
*ret_value);
free(ret_value);
return 0; }
void *thread (void *vargp) {
int arg = *((int*)vargp);
printf("hello from thread: %X!\n", arg); int *ret = (int*)malloc(sizeof(int)); *ret = arg;
return ret;}
Returning pointer
int main (int argc, char *argv[]) { pthread_t tid;
int thread_arg = 0xDEADBEEF; int* ret_value;
printf("Main thread creating peer thread.\n");
pthread_create(&tid, NULL, thread, &thread_arg);
printf("Main thread waiting for peer thread %u to
complete...\n", (unsigned int)(tid)); pthread_join(tid, (void **)(&ret_value)); printf("Main thread joined with peer thread:%X
*ret_value); free(ret_value); return 0; }
What if I don’t use malloc?
.
\
n
%
X
"
,
.
\
n
",
void *thread (void *vargp) {
int arg = *((int*)vargp);
printf("hello from thread: %X!\n", arg); int *ret = (int*)malloc(sizeof(int)); *ret = arg;
return ret;}
Returning pointer i-clicker: What is the output?
int main (int argc, char *argv[]) {
pthread_t tid;
int thread_arg = 0xDEADBEEF;
int* ret_value;
pthread_create(&tid, NULL, thread, &thread_arg); pthread_join(tid, (void **)(&ret_value)); printf("%X\n", *ret_value);
return 0; }
void *thread (void *vargp) { int arg = *((int*)vargp); return &arg;}
A. 0xDEADBEEF B. Segfault C.0
D. -1
Returning pointer i-clicker solution: What is the output?
int main (int argc, char *argv[]) {
pthread_t tid;
int thread_arg = 0xDEADBEEF;
int* ret_value;
pthread_create(&tid, NULL, thread, &thread_arg); pthread_join(tid, (void **)(&ret_value)); printf("%X\n", *ret_value);
return 0; }
void *thread (void *vargp) { int arg = *((int*)vargp); return &arg;}
A. 0xDEADBEEF
B. Segfault
C.0 D. -1
Detached mode
int main (int argc, char *argv[]) {
// This is used to record the thread id: pthread_t tid;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, NULL);
pthread_exit(NULL);
return 0; }
void *thread (void *vargp) { pthread_detach(pthread_self()); printf("hello from thread world!\n");
}
Detached mode
int main (int argc, char *argv[]) {
// This is used to record the thread id: pthread_t tid;
printf("Main thread creating peer thread.\n"); pthread_create(&tid, NULL, thread, NULL);
pthread_exit(NULL);
return 0; }
void *thread (void *vargp) {
pthread_detach(pthread_self());
printf("hello from thread world!\n"); }
Detached mode
Detached mode
void *thread (void *vargp) { pthread_detach(pthread_self()); printf("hello from thread world!\n");
}
• Run thread in “detached” mode.
– Runs independently of other threads
– Reaped automatically (by kernel) when it terminates
– without the need for another thread to join with the terminated thread
Concurrent Programming is Nice!
• Easy to share global data structure
• Easy to implement a cache that all the threads can use
Concurrent Programming is Hard!
• The human mind tends to be sequential
• The notion of time is often misleading
Concurrent Programming is Hard!
• The human mind tends to be sequential
• The notion of time is often misleading
• Thinking about all possible sequences of events in a computer system is at least error prone and frequently impossible
Concurrent Programming is Hard!
• Classical problem classes of concurrent programs:
– Races: outcome depends on arbitrary scheduling decisions
elsewhere in the system
• Example: who gets the last seat on the airplane?
• Threadssharetheheap
• Threadshaveseparatestacks
• But,Chaspointers
– which can point to anywhere, even the stack!
• Whatif...
– I pass a pointer to a peer thread that points to a
location on the stack
– Unintended Sharing!
Unintended Sharing
Unintended sharing
int main (int argc, char *argv[]) { pthread_t tid;
for(int i=0; i<10; i++) {
pthread_create(&tid, NULL, thread, &i); }
pthread_exit(NULL);
return 0; }
void *thread (void *vargp) { pthread_detach(pthread_self());
int arg = *((int*) vargp); printf("hello from thread %d!\n", arg); return NULL;
}
Unintended sharing
int main (int argc, char *argv[]) { pthread_t tid;
for(int i=0; i<10; i++) {
pthread_create(&tid, NULL, thread, &i);
} pthread_exit(NULL); return 0;
}
void *thread (void *vargp) { pthread_detach(pthread_self());
int arg = *((int*) vargp); printf("hello from thread %d!\n", arg); return NULL;
}
Potential Form of Unintended Sharing
for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i);
}
main thread
Main thread stack
i
Potential Form of Unintended Sharing
for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i);
}
main thread
Main thread stack
i = i1
i
peer1
Peer1 stack
vargp
Potential Form of Unintended Sharing
for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i);
}
main thread
Main thread stack
i = i1
i = i2
i
peer1
peer2
Peer1 stack
vargp
Peer2 stack
vargp
Potential Form of Unintended Sharing
for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i);
}
main thread
Main thread stack
i = i1
i = i2
i
peer1
*vargp
peer2
Peer1 stack
vargp
Peer2 stack
vargp
Potential Form of Unintended Sharing
for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i);
}
main thread
peer1
*vargp
peer2
*vargp
Peer1 stack
vargp
Peer2 stack
vargp
Main thread stack
i = i1
i = i2
i
Fix unintended sharing
int main (int argc, char *argv[]) { pthread_t tid;
int *argp;
for(int i=0; i<10; i++) {
argp = (int*)malloc(sizeof(int));
*argp = i;
pthread_create(&tid, NULL, thread, argp);
}
pthread_exit(NULL);
return 0;
}
void *thread (void *vargp) { pthread_detach(pthread_self());
int arg = *((int*) vargp); printf("hello from thread %d!\n", arg); free(vargp); return NULL;}
Data Race
• A data race occurs when two or more threads can access shared data and one of them is a write. Because the thread scheduling algorithm can swap between threads at any time, you don’t know the order in which the threads will attempt to access the shared data.
Race Condition
A race condition is a semantic error. It is a flaw that occurs in the timing or the ordering of events that leads to erroneous program behavior.
Many race conditions can be caused by data races, but this is not necessary. Consider the following simple example where x is a shared variable:
81
Tools that can help you with Synchronization Problems
Given the non-deterministic, (i.e. extremely hard) nature of multithreaded applications, people have developed interesting tools to detect errors and potential pitfalls in concurrent code. Projects like Google's TSan or Helgrind are just a few of them.
82
Mapping Variable Instances to Memory
■ Global variables
▪ Def: Variable declared outside of a function
▪ Virtual memory contains exactly one instance of any global variable
■ Local variables
▪ Def: Variable declared inside function without static attribute ▪ Each thread stack contains one instance of each local variable
■ Local static variables
▪ Def: Variable declared inside function with the static attribute
▪ Virtual memory contains exactly one instance of any local static variable.
Global var: 1 instance (ptr [data])
Mapping Variable Instances to Memory
Local vars: 1 instance (i.m, msgs.m)
Local var: 2 instances (
myid.p0 [peer thread 0’s stack], myid.p1 [peer thread 1’s stack]
)
char **ptr; /* global */
int main() {
int i;
pthread_t tid; char *msgs[2] = {
"Hello from foo",
"Hello from bar"
};
ptr = msgs;
for (i = 0; i < 2; i++)
Pthread_create(&tid,
NULL, thread, (void *)i);
Pthread_exit(NULL);
}
/* thread routine */
void *thread(void *vargp) {
int myid = (int)vargp;
static int cnt = 0;
printf("[%d]: %s (svar=%d)\n",
myid, ptr[myid], ++cnt);
}
Local static var: 1 instance (cnt [data]) 84
Is this program 100% correct?
■ Shared variables are handy...
■ ...but introduce the possibility of nasty synchronization errors.
Synchronizing Threads
Data Race
/* Global shared variable */ long cnt =0; /* Counter */
int main(int argc, char **argv) {
}
long niters; pthread_t tid1, tid2;
niters =atoi(argv[1]);
pthread_create(&tid1, NULL, thread, &niters);
pthread_create(&tid2, NULL, thread, &niters);
pthread_join(tid1, NULL); pthread_join(tid2, NULL);
/* Checkresult */
if (cnt!=(2*niters))
printf("BOOM!cnt=%ld\n", cnt); else
printf("OK cnt=%ld\n", cnt); exit(0);
badcnt.c
/* Threadroutine */ void *thread(void *vargp)
{
longi, niters=
*((long *)vargp);
for(i =0;i
BOOM! cnt=1069894
cnt should equal 2,000,000. What went wrong?
86
Assembly Code for Counter Loop
C code for counter loop in thread i
for (i = 0; i < niters; i++) cnt++;
Asm code for thread i
movq (%rdi), %rcx testq %rcx,%rcx jle .L2
movl $0, %eax
.L3:
movq cnt(%rip),%rdx addq $1, %rdx
movq %rdx, cnt(%rip) addq $1, %rax
cmpq %rcx, %rax
jne .L3
.L2:
Hi : Head
Li : Load cnt Ui : Update cnt Si : Storecnt
Ti:Tail
Question
Suppose that cnt starts with value 0, and that two threads each executethecodebelowonce. Whatarethepossiblevaluesforcnt afterward?
A) Only 2
B) 1or2
C) 0or1or2
D) None of the above
movq cnt(%rip),%rdx addq $1, %rdx
movq %rdx, cnt(%rip)
Question
Suppose that cnt starts with value 0, and that two threads each executethecodebelowonce. Whatarethepossiblevaluesforcnt afterward?
A) Only 2
B) 1or2
C) 0or1or2
D) None of the above
movq cnt(%rip),%rdx addq $1, %rdx
movq %rdx, cnt(%rip)
Concurrent Execution
■ Key idea: In general, any sequentially consistent interleaving is possible, but some give an unexpected result!
1.atomicity — if your code contains instructions that operate on data shared across multiple threads, an unregulated concurrent access to that data might trigger a data race. The code segment that contains those instructions is called critical section. You want to make sure that critical sections are executed atomically: an atomic operation can't be broken into smaller ones, so that while a thread is executing it no other thread can slip through;
2.ordering — sometimes you want two or more threads to perform their job in a predictable order, or put a restriction on how many threads can access a specific resource. Normally you don't have control over these things, which might be the root cause of race conditions. With synchronization you can orchestrate your threads to perform according to a plan.
Enforcing Mutual Exclusion
■ We must synchronize the execution of the threads so that they can never have overlap critical sections.
▪ i.e., need to guarantee mutually exclusive access for each critical section.
91
■
Enforcing Mutual Exclusion
We must synchronize the execution of the threads so that they can never have overlap critical sections.
▪ i.e., need to guarantee mutually exclusive access for each critical section.
Solutions:
▪ Semaphores
▪ Mutex locks
▪ Condition variables ▪ Atomic operations
■
92
■ Semaphore: non-negative global integer synchronization variable.
■ Unlike mutex (a locking mechanism), it is a signaling mechanism. It
guarantees both ordering and atomicity.
■ Unlike a mutex, any thread can release a semaphore, not only the one
that has acquired it in the first place.
Semaphores
93
A semaphore controls the access to a shared resource: the counter determines the maximum number of threads that can simultaneously access it. At the beginning of your program, when the semaphore gets initialized, you choose that number according to your needs. Then, a thread that wants to access a shared resource calls acquire:
• if the counter is greater than zero the thread can proceed. The counter gets reduced by one right away, then the current thread starts doing its job. When done, it calls release which in turn increases the counter by one.
• if the counter is equal to zero the thread cannot proceed: other threads have already filled up the available space. The current thread is put to sleep by the operating system and will wake up when the semaphore counter becomes greater than zero again (that is when any other thread calls release once its job is done).
• Unlike a mutex, any thread can release a semaphore, not only the one that has acquired it in the first place.
94
Semaphores
■ Semaphore: non-negative global integer synchronization variable.
semaphore
95
Semaphores
■ Semaphore: non-negative global integer synchronization variable.
2
semaphore
96
Semaphores
■ Semaphore: non-negative global integer synchronization variable.
1
semaphore
97
Semaphores
■ Semaphore: non-negative global integer synchronization variable.
0
semaphore
98
Semaphores
■ Semaphore: non-negative global integer synchronization variable.
1
semaphore
99
Semaphores
■ Semaphore: non-negative global integer synchronization variable. Manipulated by P and V operations.
■ P(s)
▪ If s is nonzero, then decrement s by 1 and return immediately.
▪ Test and decrement operations occur atomically (indivisibly)
▪ If s is zero, then suspend thread until s becomes nonzero and the thread is
restarted by a V operation.
▪ After restarting, the P operation decrements s and returns control to the caller.
■ V(s):
▪ Increment s by 1.
▪ Increment operation occurs atomically
▪ If there are any threads blocked in a P operation waiting for s to become non- zero, then restart exactly one of those threads, which then completes its P operation by decrementing s.
100
Semaphores
■ Semaphore: non-negative global integer synchronization variable. Manipulated by P and V operations.
■ P(s)
▪ If s is nonzero, then decrement s by 1 and return immediately.
▪ Test and decrement operations occur atomically (indivisibly)
▪ If s is zero, then suspend thread until s becomes nonzero and the thread is
restarted by a V operation.
▪ After restarting, the P operation decrements s and returns control to the caller.
■ V(s):
▪ Increment s by 1.
▪ Increment operation occurs atomically
▪ If there are any threads blocked in a P operation waiting for s to become non- zero, then restart exactly one of those threads, which then completes its P operation by decrementing s.
■ Semaphore invariant: (s >= 0)
101
C Semaphore Operations
Pthreads functions:
#include
int sem_init(sem_t *s, 0, unsigned int val);} /* s = val */
int sem_wait(sem_t *s); /* P(s) */ int sem_post(sem_t *s); /* V(s) */
102
Improper Synchronization
/* Global shared variable */ volatile long cnt =0; /* Counter */
int main(int argc, char **argv) {
long niters; pthread_t tid1, tid2;
niters =atoi(argv[1]); Pthread_create(&tid1, NULL,
thread, &niters); Pthread_create(&tid2, NULL,
thread, &niters); Pthread_join(tid1, NULL); Pthread_join(tid2, NULL);
/* Checkresult */
if (cnt!=(2*niters)) printf(“BOOM!cnt=%ld\n”, cnt);
else
printf(“OK cnt=%ld\n”, cnt); exit(0);
}
/* Threadroutine */ void *thread(void *vargp)
{
longi, niters=
*((long *)vargp);
for(i =0;i
linux> ./goodcnt 1000000 OK cnt=1000000
106
Binary Semaphore
› A semaphore whose counter is restricted to the values 0 and 1 is called binary semaphore: only one thread at a time can access the shared resource. Wait: this is basically a mutex protecting a critical section! You can actually replicate the mutex behavior with a binary semaphore. However there are two important points to keep in mind:
› a mutex can be unlocked only by thread that had locked it first, while a semaphore can be released from any other thread. This could lead to confusion and subtle bugs if what you want is just a locking mechanism;
› semaphores are signaling mechanisms that orchestrate threads, while mutexes are locking mechanisms that protects shared resources. You should not use semaphores to protect shared resources, nor mutexes for signaling: your intent will be more clear to you and to anyone who will read your code.
107
Producer-Consumer with Semaphore
› The producer-consumer scenario imposes the following constraints:
– The producer thread must not overwrite the shared buffer when the previous task
has not been picked up by a consumer thread.
– The consumer threads must not pick up tasks until there is something present in the shared buffer.
– Individual consumer threads should pick up tasks one at a time. Producer
Producer Producer
Consumer Consumer
Consumer
Buffer Queue
108
sem_t empty; // empty slot in buffer
sem_t occupied; // occupied slot in buffer sem_t p_lock; // mutex for producer function sem_t c_lock; // mutex for consumer function void *producer(void *producer_thread_data) {
while (!done()) {
} }
sem_wait(&empty);
sem_wait(&p_lock);
insert_into_queue();
sem_post(&p_lock);
sem_post(&occupied);
void *consumer(void *consumer_thread_data) { while (!done()) {
sem_wait(&occupied); sem_wait(&c_lock);
my_task = extract_from_queue();
sem_post(&c_lock);
sem_post(&empty);
process_task(my_task); }
}
void main() {
/* declarations and initializations */ sem_init(&p_lock, 0, 1); /* mutex = 0 */ sem_init(&c_lock, 0, 1); /* mutex = 0 */ sem_init(&empty, 0, BUFFER_SIZE); /* mutex = 0 */ sem_init(&occupied, 0, 0); /* mutex = 0 */
……
}
Producer-Consumer with Semaphore
109
■ Programmers need a clear model of how variables are shared by threads.
■ Variables shared by multiple threads must be protected to ensure mutually
exclusive access.
■ Semaphores are a fundamental mechanism for enforcing mutual exclusion.
Summary
107