UNIS Template
Concurrency with
Threads and
Synchronization
Shuaiwen Song
• To learn what a thread is
• To understand the difference between processes and
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.
Objectives
• 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
Process Pros
• Forking a process is expensive
– Need to clone parent’s memory space
– Need to setup a separate context for child
Process Cons
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.
• 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
• Process = context + code, data, and stack
shared libraries
0
Program context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC)
Kernel context:
VM structures
Descriptor table
Code, data, and stack
run-time heap
read/write data
read-only code/data
stack
SP
PC
Process context
View of a Process
• Process = context + code, data, and stack
shared libraries
0
Program context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC)
Kernel context:
VM structures
Descriptor table
Code, data, and stack
run-time heap
read/write data
read-only code/data
stack
SP
PC
Process context
View of a Process
0
Thread context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC)
run-time heap
read/write data
read-only code/data
stack
SP
PC
• Process = thread + code, data, and kernel context
Thread (main thread) Code and Data
shared libraries
Kernel context:
VM structures
Descriptor table
Alternate View of a Process
• Multiple threads can be associated with a process
– Each thread has its own logical control flow
shared libraries
0
Thread 1 context:
Data registers
Condition codes
SP1
PC1
Shared code and data
run-time heap
read/write data
read-only code/data
stack 1
Thread 1 (main thread)
Kernel context:
VM structures
Descriptor table
Thread 2 context:
Data registers
Condition codes
SP2
PC2
stack 2
Thread 2 (peer thread)
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Each thread has its own logical control flow
– Each thread shares the same code, data, and kernel context
shared libraries
0
Thread 1 context:
Data registers
Condition codes
SP1
PC1
Shared code and data
run-time heap
read/write data
read-only code/data
stack 1
Thread 1 (main thread)
Kernel context:
VM structures
Descriptor table
Thread 2 context:
Data registers
Condition codes
SP2
PC2
stack 2
Thread 2 (peer thread)
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Each thread has its own logical control flow
– Each thread shares the same code, data, and kernel context
– Each thread has its own stack for local variables
shared libraries
0
Thread 1 context:
Data registers
Condition codes
SP1
PC1
Shared code and data
run-time heap
read/write data
read-only code/data
stack 1
Thread 1 (main thread)
Kernel context:
VM structures
Descriptor table
Thread 2 context:
Data registers
Condition codes
SP2
PC2
stack 2
Thread 2 (peer thread)
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Each thread has its own logical control flow
– Each thread shares the same code, data, and kernel context
– Each thread has its own stack for local variables
• but not protected from other threads
shared libraries
0
Thread 1 context:
Data registers
Condition codes
SP1
PC1
Shared code and data
run-time heap
read/write data
read-only code/data
stack 1
Thread 1 (main thread)
Kernel context:
VM structures
Descriptor table
Thread 2 context:
Data registers
Condition codes
SP2
PC2
stack 2
Thread 2 (peer thread)
A Process With Multiple Threads
• Multiple threads can be associated with a process
– Each thread has its own logical control flow
– Each thread shares the same code, data, and kernel context
– Each thread has its own stack for local variables
• but not protected from other threads
– Each thread has its own thread id (TID)
0
Thread 1 context:
Data registers
Condition codes
SP1
PC1
run-time heap
read/write data
read-only code/data
stack 1
Thread 1 (main thread)
Kernel context:
VM structures
Descriptor table
Thread 2 context:
Data registers
Condition codes
SP2
PC2
stack 2
Shared code and data Thread 2 (peer thread)
shared libraries
A Process With Multiple Threads
(typically functions)
Process
• Processes
– Represent an entire program
• Threads
– Represents smaller chunks of code
Threads
OS: Concept of a Thread
(typically functions)
Process
• Processes
– Represent an entire program
– High Overhead context switch
• Threads
– Represents smaller chunks of code
– Lower Overhead context switch
Threads
OS: Concept of a Thread
• Threads associated with process form a pool of peers
– Unlike processes which form a tree hierarchy
P0
P1
sh sh sh
foo
bar
T1
Process hierarchyThreads associated with process foo
T2
T4
T5 T3
shared code, data
and kernel context
Logical View of Threads
• How threads and processes are similar
– Each has its own logical control flow
– Each can run concurrently with others
– Each is context switched
Threads vs. Processes
• How threads and processes are similar
– Each has its own logical control flow
– Each can run concurrently with others
– Each is context switched
• How threads and processes are different
– Threads share code and some data
• Processes (typically) do not
Threads vs. Processes
• How threads and processes are similar
– Each has its own logical control flow
– Each can run concurrently with others
– Each is context switched
• How threads and processes are different
– 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
Threads vs. Processes
• 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:
Time
Thread A Thread B Thread C
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Time
Thread A Thread B Thread C
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Time
Thread A Thread B Thread C
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Time
Thread A Thread B Thread C
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Time
Thread A Thread B Thread C
Concurrent Threads
• Two threads are concurrent if their flows overlap in time
• Otherwise, they are sequential
• Examples:
Time
Thread A Thread B Thread C
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
Concurrent Threads
• Single Core Processor
– Simulate parallelism by
time slicing
Time
Thread A Thread B Thread C
• Multi-Core Processor
– Can have true
parallelism
Thread A Thread B Thread C
Run 3 threads on 2 cores
Concurrent Threads
• 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]
Posix Threads (Pthreads) Interface
/*
* hello.c – Pthreads “hello, world” program
*/
#include “csapp.h”
void *thread(void *vargp);
int main() {
pthread_t tid;
thread, NULL);Pthread_create(&tid, NULL,
Pthread_join(tid, NULL);
exit(0);
}
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL;
}
The Pthreads “hello, world” Program
program
/*
* hello.c – Pthreads “hello, world”
*/
#include “csapp.h”
void *thread(void *vargp);
int main() {
pthread_t tid;
thread, NULL);Pthread_create(&tid, NULL,
Pthread_join(tid, NULL);
exit(0);
}
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL;
}
thread routine that
the new thread executes
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program
*/
#include “csapp.h”
void *thread(void *vargp);
int main() {
pthread_t tid;
thread, NULL);Pthread_create(&tid, NULL,
Pthread_join(tid, NULL);
exit(0);
}
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL;
}
thread id
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;
}
Thread attributes
(usually 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;
}
Thread arguments
(void *p)
The Pthreads “hello, world” Program
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL;
}
program
/*
* hello.c – Pthreads “hello, world”
*/
#include “csapp.h”
void *thread(void *vargp);
int main() {
pthread_t tid;
thread, NULL);Pthread_create(&tid, NULL,
Pthread_join(tid, NULL);
exit(0);
} return value
(void **p)
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program
*/
#include “csapp.h”
void *thread(void *vargp);
int main() {
pthread_t tid;
thread, NULL);Pthread_create(&tid, NULL,
Pthread_join(tid, NULL);
exit(0);
}
/* thread routine */
void *thread(void *vargp) {
printf(“Hello, world!\n”);
return NULL;
}
The Pthreads “hello, world” Program
main thread
Execution of Threaded“hello, world”
main thread
call Pthread_create()
Execution of Threaded“hello, world”
main thread
call Pthread_create()
peer thread
Execution of Threaded“hello, world”
main thread
call Pthread_create()
peer thread
call Pthread_join()
main thread waits for
peer thread to terminate
Execution of Threaded“hello, world”
main thread
call Pthread_create()
peer thread
main thread waits for
peer thread to terminate
call Pthread_join()
printf()
return NULL;
(peer thread
terminates)
Execution of Threaded“hello, world”
main thread
call Pthread_create()
peer thread
main thread waits for
peer thread to terminate
call Pthread_join()
printf()
return NULL;
(peer thread
terminates)
Pthread_join() returns
Execution of Threaded“hello, world”
main thread
call Pthread_create()
peer thread
main thread waits for
peer thread to terminate
call Pthread_join()
printf()
return NULL;
(peer thread
terminates)
Pthread_join() returns
exit()
terminates
main thread and
any peer threads
Execution of Threaded“hello, world”
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; } Passing argument 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 value 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.\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;} %X.\n", What if I don’t use malloc? 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; } i-clicker: What is the output? void *thread (void *vargp) { int arg = *((int*)vargp); return &arg;} 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; } A. 0xDEADBEEF B. Segfault C. 0 D. -1 Returning pointer i-clicker solution: What is the output? void *thread (void *vargp) { int arg = *((int*)vargp); return &arg;} 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; } A. 0xDEADBEEF B. Segfault C. 0 D. -1 Returning pointer void *thread (void *vargp) { pthread_detach(pthread_self()); printf("hello from thread world!\n"); } 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; } Detached mode void *thread (void *vargp) { pthread_detach(pthread_self()); printf("hello from thread world!\n"); } 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; } Detached mode Detached mode • 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 void *thread (void *vargp) { pthread_detach(pthread_self()); printf("hello from thread world!\n"); } Detached mode • Easy to share global data structure • Easy to implement a cache that all the threads can use Concurrent Programming is Nice! • 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? Concurrent Programming is Hard! • Threads share the heap • Threads have separate stacks • But, C has pointers – which can point to anywhere, even the stack! • What if… – I pass a pointer to a peer thread that points to a location on the stack – 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; } Unintended sharing main thread for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i); } Main thread stack i Potential Form of Unintended Sharing main thread peer1 for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i); } i Main thread stack vargp Peer1 stack i = i1 Potential Form of Unintended Sharing main thread peer1 for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i); } i Main thread stack vargp Peer1 stack i = i1 peer2 i = i2 Peer2 stack vargp Potential Form of Unintended Sharing main thread peer1 for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i); } i Main thread stack vargp Peer1 stack i = i1 peer2 i = i2 Peer2 stack vargp *vargp Potential Form of Unintended Sharing main thread peer1 for(int i=0; i<10; i++) { pthread_create(&tid, NULL, thread, &i); } i Main thread stack vargp Peer1 stack i = i1 peer2 i = i2 vargp Peer2 stack *vargp *vargp Potential Form of 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;} Fix unintended sharing • 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. Data Race Race Condition 81 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: Tools that can help you with Synchronization Problems 82 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. https://www.internalpointers.com/post/gentle-introduction-multithreading#race-conditions https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual http://valgrind.org/docs/manual/hg-manual.html ■ 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. Mapping Variable Instances to Memory char **ptr; /* global */ int main() { "Hello "Hello from from int i; pthread_t tid; char *msgs[2] = { foo", 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); } Global var: 1 instance (ptr [data]) 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] ) Local static var: 1 instance (cnt [data]) 84 Mapping Variable Instances to Memory Is this program 100% correct? ■ Shared variables are handy... ■ …but introduce the possibility of nasty synchronization errors. Synchronizing Threads Data Race 86 / * Global shared variable * / long cnt = 0; / * Counter * / in t main(int argc, char **argv) { long niters; pthread_t t id1 , t id2; niters = atoi(argv[1]); pthread_create(&tid1, NULL, thread, &niters); pthread_create(&tid2, NULL, thread, &niters); pthread_join(tid1, NULL); pthread_join(tid2, NULL); / * Thread routine * / void *thread(void *vargp) { long i , niters = *((long *)vargp); for ( i = 0; i < ni ters; i++) cnt++; return NULL; / * Check result * / i f (cnt != (2 * n i ters ) ) printf("BOOM! cnt=%ld\n", cnt); el se printf("OK cnt=%ld\n", cnt) ; ex i t (0 ) ; badcnt.c} } linux> ./main 1000000
BOOM! cnt=1069894
What went wrong?
cnt should equal
2,000,000.
for (i = 0; i < niters; i++) cnt++; C code for counter loop in thread i cnt(%rip),%rdx $1, %rdx %rdx, cnt(%rip) $1, %rax %rcx, %rax .L3 movq (%rdi), %rcx testq %rcx,%rcx jle .L2 movl $0, %eax .L3: movq addq movq addq cmpq jne .L2: Hi :Head iT :Tail Li : Load cnt Ui : Update cnt Si : Storecnt Asm code for thread i Assembly Code for Counter Loop movq addq movq cnt(%rip),%rdx $1, %rdx %rdx, cnt(%rip) Suppose that cnt starts with value 0, and that two threads each execute the code below once. What are the possible values for cnt afterward? A) Only 2 B) 1 or 2 C) 0 or 1 or 2 D) None of the above Question movq addq movq cnt(%rip),%rdx $1, %rdx %rdx, cnt(%rip) Suppose that cnt starts with value 0, and that two threads each execute the code below once. What are the possible values for cnt afterward? A) Only 2 B) 1 or 2 C) 0 or 1 or 2 D) None of the above Question ■ Key idea: In general, any sequentially consistent interleaving is possible, but some give an unexpected result! Concurrent Execution 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. https://www.internalpointers.com/post/gentle-introduction-multithreading#data-races 91 ■ 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. Enforcing Mutual Exclusion 92 ■ 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 Enforcing Mutual Exclusion 93 ■ 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 94 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. ■ Semaphore: non-negative global integer synchronization variable. semaphore 95 Semaphores ■ Semaphore: non-negative global integer synchronization variable. semaphore2 96 Semaphores ■ Semaphore: non-negative global integer synchronization variable. semaphore1 97 Semaphores ■ Semaphore: non-negative global integer synchronization variable. semaphore0 98 Semaphores ■ Semaphore: non-negative global integer synchronization variable. semaphore1 99 Semaphores 100 ■ 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. Semaphores 101 ■ 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)
Semaphores
C Semaphore Operations
Pthreads functions:
#include
int sem_init(sem_t *s, 0, unsigned int val);} /* s = val */
102
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */
/ * Global shared variable * /
vo la t i l e long cnt = 0; / * Counter * /
in t main(int argc, char **argv)
{
long niters ;
pthread_t t id1 , t id2;
niters = atoi(argv[1]);
Pthread_create(&tid1, NULL,
thread, &niters);
Pthread_create(&tid2, NULL,
thread, &niters);
Pthread_join(tid1, NULL);
Pthread_join(tid2, NULL);
/ * Check result * /
i f (cnt != (2 * n i ters ) )
printf(“BOOM! cnt=%ld\n”, cnt);
e l se
printf(“OK cnt=%ld\n”, cnt);
ex i t (0 ) ;
}
/ * Thread routine * / void
*thread(void *vargp)
{
long i , niters =
*((long *)vargp);
for ( i = 0; i < ni ters; i++) cnt++; return NULL; } 103 How can we fix this using semaphores? Improper Synchronization 104 ■ Basic idea: ▪ Associate a unique semaphore mutex, initially 1, with each shared variable (or related set of shared variables). ▪ Surround corresponding critical sections with P(mutex) and V(mutex) operations. Using Semaphores for Mutual Exclusion 105 ■ Basic idea: ▪ Associate a unique semaphore mutex, initially 1, with each shared variable (or related set of shared variables). ▪ Surround corresponding critical sections with P(mutex) and V(mutex) operations. ■ Terminology: ▪ Binary semaphore: semaphore whose value is always 0 or 1 ▪ Mutex: binary semaphore used for mutual exclusion ▪ P operation: “locking” the mutex ▪ V operation: “unlocking” or “releasing” the mutex ▪ “Holding” a mutex: locked and not yet unlocked. ▪ Counting semaphore: used as a counter for set of available resources. Using Semaphores for Mutual Exclusion Proper Synchronization ■ Define and initialize a mutex for the shared variable cnt: volat i le long cnt = 0; /* Counter * / sem_t mutex; /* Semaphore that protects cnt * / sem_init(&mutex, 0 , 1) ; / * mutex = 1 * / ■ Surround critical section with P and V: for ( i = 0; i < ni ters; i++) { sem_wait(&mutex); cnt++; sem_post ( &mut ex) ; } goodcnt.c 106 linux> ./goodcnt 1000000
OK cnt=1000000
linux> ./goodcnt 1000000
OK cnt=1000000
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.
108
Producer
Producer
Producer
Buffer Queue
Consumer
Consumer
Consumer
Producer-Consumer with Semaphore
109
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 */
……
}
107
■ 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