CS计算机代考程序代写 data structure concurrency cache assembly algorithm Concurrency with Threads and Synchronization

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 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:
– 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()
– Determining your thread ID • pthread_self()
– Terminating threads
• pthread_cancel()

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 ./main 1000000
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 ./goodcnt 1000000 OK cnt=1000000
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

Related Posts