Sogang University
Synchronization: Basics
CSE4100: System Programming
Youngjae Kim (PhD)
Copyright By PowCoder代写 加微信 powcoder
https://sites.google.com/site/youkim/home
Distributed Computing and Operating Systems Laboratory (DISCOS)
https://discos.sogang.ac.kr
Office: R911, E-mail:
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Shared Variables in Threaded C Programs
¡é Question: Which variables in a threaded C program are shared?
¡ì The answer is not as simple as ¡°global variables are shared¡± and ¡°stack variables are private¡±
¡é Def: A variable x is shared if and only if multiple threads reference some instance of x.
¡é Requires answers to the following questions: ¡ì What is the memory model for threads?
¡ì How are instances of variables mapped to memory?
¡ì How many threads might reference each of these instances?
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Threads Memory Model
¡é Conceptual model:
¡ì Multiple threads run within the context of a single process
¡ì Each thread has its own separate thread context
¡ì Thread ID, stack, stack pointer, PC, condition codes, and GP registers
¡ì All threads share the remaining process context
¡ì Code, data, heap, and shared library segments of the process virtual address
¡ì Open files and installed handlers
¡é Operationally, this model is not strictly enforced:
¡ì Register values are truly separate and protected, but…
¡ì Any thread can read and write the stack of any other thread
The mismatch between the conceptual and operation model is a source of confusion and errors
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Example Program to Illustrate Sharing
char **ptr; /* global var */
int main() {
pthread_t tid;
char *msgs[2] = {
“Hello from foo”,
“Hello from bar”
ptr = msgs;
for (i = 0; i < 2; i++)
Pthread_create(&tid,
(void *)i);
Pthread_exit(NULL);
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
void *thread(void *vargp)
long myid = (long)vargp;
static int cnt = 0;
printf("[%ld]: %s (cnt=%d)\n",
myid, ptr[myid], ++cnt);
return NULL;
Peer threads reference main thread¡¯s stack indirectly through global ptr variable
Sogang University
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: Variabledeclaredinside functionwiththestaticattribute
¡ì Virtual memory contains exactly one instance of any local static variable.
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Mapping Variable Instances to Memory
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] )
char **ptr; /* global var */
int main() {
pthread_t tid;
char *msgs[2] = {
"Hello from foo",
"Hello from bar"
ptr = msgs;
for (i = 0; i < 2; i++)
Pthread_create(&tid,
(void *)i);
Pthread_exit(NULL);
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Local static var: 1 instance (cnt [data]) 6
void *thread(void *vargp)
long myid = (long)vargp;
static int cnt = 0;
printf("[%ld]: %s (cnt=%d)\n",
myid, ptr[myid], ++cnt);
return NULL;
Sogang University
Shared Variable Analysis ¡é Which variables are shared?
Variable instance
msgs.m yes
myid.p0 no
Referenced by main thread?
Referenced by peer thread 0?
yes yes no
Referenced by peer thread 1?
yes no yes
¡é Answer: A variable x is shared iff multiple threads reference at least one instance of x. Thus:
n ptr, cnt, and msgs are shared n i and myid are not shared
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Synchronizing Threads ¡é Shared variables are handy...
¡é ...but introduce the possibility of nasty synchronization errors.
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
/* 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);
/* Check result */
if (cnt != (2 * niters)) printf("BOOM! cnt=%ld\n", cnt);
printf("OK cnt=%ld\n", cnt);
exit(0); }
/* Thread routine */
void *thread(void *vargp)
long i, niters =
*((long *)vargp);
for (i = 0; i < niters; i++)
return NULL;
linux> ./badcnt 10000 OK cnt=20000
linux> ./badcnt 10000 BOOM! cnt=13051 linux>
badcnt.c: Improper Synchronization
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
cnt should equal 20,000. What went wrong?
Sogang University
Assembly Code for Counter Loop
C code for counter loop in thread i
for (i = 0; i < niters; i++) cnt++;
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Asm code for thread i
movq (%rdi), %rcx
testq %rcx,%rcx
movl $0, %eax
movq cnt(%rip),%rdx addq $1, %rdx
movq %rdx, cnt(%rip)
addq $1, %rax
cmpq %rcx, %rax
Li : : Update cnt Si : Store cnt
Sogang University
Concurrent Execution
¡é Key idea: In general, any sequentially consistent interleaving is possible, but some give an unexpected result!
¡ì Ii denotes that thread i executes instruction I
¡ì %rdxi is the content of %rdx in thread i¡¯s context
i (thread)
%rdx1 %rdx2 cnt
Thread 1 critical section
Thread 2 critical section
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Concurrent Execution (cont)
¡é Incorrect ordering: two threads increment the counter, but the result is 1 instead of 2
i (thread)
instri %rdx1 %rdx2 cnt
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Concurrent Execution (cont) ¡é How about this ordering?
i (thread) instri %rdx1 %rdx2 cnt
¡é We can analyze the behavior using a progress graph Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Progress Graphs
H1 L1 U1 S1 T1
A progress graph depicts the discrete execution state space of concurrent
Each axis corresponds to the sequential order of instructions in a thread.
Each point corresponds to a possible execution state (Inst1, Inst2).
E.g., (L1, S2) denotes state where thread 1 has completed L1 and thread 2 has completed S2.
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Trajectories in Progress Graphs
H1 L1 U1 S1 T1
A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads.
H1, L1, U1, H2, L2, S1, T1, U2, S2, T2
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Critical Sections and Unsafe Regions
S2 critical
section wrt cnt
L, U, and S form a critical section with respect to the shared variable cnt
Instructions in critical sections (wrt some shared variable) should not be interleaved
Sets of states where such interleaving occurs form unsafe regions
H1 L1 U1 S1 T1
critical section wrt cnt Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Unsafe region
Sogang University
Critical Sections and Unsafe Regions
S2 critical
section wrt cnt
Def: A trajectory is safe iff it does not enter any unsafe region
Claim: A trajectory is correct (wrt cnt) iff it is safe
Unsafe region
H1 L1 U1 S1 T1
critical section wrt cnt Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
Enforcing Mutual Exclusion
¡é Question: How can we guarantee a safe trajectory?
¡é Answer: We must synchronize the execution of the threads so that they can never have an unsafe trajectory.
¡ì i.e., need to guarantee mutually exclusive access for each critical section.
¡é Classic solution:
¡ì Semaphores (Edsger Dijkstra)
¡é Other approaches (out of our scope) ¡ì Mutex and condition variables (Pthreads) ¡ì Monitors (Java)
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
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.
¡ì 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) Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
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) */
CS:APP wrapper functions:
#include “csapp.h¡±
void P(sem_t *s); /* Wrapper function for sem_wait */ void V(sem_t *s); /* Wrapper function for sem_post */
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
/* 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);
/* Check result */
if (cnt != (2 * niters)) printf(“BOOM! cnt=%ld\n”, cnt);
printf(“OK cnt=%ld\n”, cnt);
/* Thread routine */
void *thread(void *vargp)
long i, niters =
*((long *)vargp);
for (i = 0; i < niters; i++)
return NULL;
badcnt.c: Improper Synchronization
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
How can we fix this using semaphores?
Sogang University
Using Semaphores for Mutual Exclusion ¡é 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.
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
goodcnt.c: Proper Synchronization
¡é Define and initialize a mutex for the shared variable cnt:
volatile 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 < niters; i++) { P(&mutex);
V(&mutex); }
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
linux> ./goodcnt 10000 OK cnt=20000
linux> ./goodcnt 10000 OK cnt=20000
Warning: It¡¯s orders of magnitude slower than badcnt.c.
Sogang University
Why Mutexes Work
U2 L2 P(s)
H1 P(s) L1 U1 S1 V(s) T1 Initially
Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s (initially set to 1)
Semaphore invariant
creates a forbidden region that encloses unsafe region and that cannot be entered by any trajectory.
00 Forbidden region 00
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
Unsafe region
00 11000011
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Sogang University
¡é 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.
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com