Concurrency in Computer Science
CS 105
Lecture 21: Concurrency
Why Concurrent Programs?
Program Structure: expressing logically
concurrent programs
Responsiveness: shifting work to run
in the background
Performance: exploiting multiprocessors
Responsiveness: managing I/O devices
Traditional View of a Process
•
Process = process context + (virtual) memory state
0
Program context:
Data registers
Stack pointer (rsp)
Condition codes
Program counter (rip)
Virtual Memory
rsp
rip
brk
Process Control Block
Kernel context:
VM structures
File table
brk pointer
Alternate View of a Process
•
Process = thread + other state
Thread context:
Data
registers
Stack pointer (rsp)
Condition codes
Program counter (rip)
Other data
rsp
Thread (main thread)
Kernel context:
VM structures
File table
brk pointer
Stack
0
brk
A Process With Multiple Threads
•
Multiple threads can be associated with a process
•
Each thread has its own logical control flow
•
Each thread has its own stack for local variables
•
Each thread has its own thread id (TID)
•
Each thread shares the same code, data, and kernel context
Thread 1 (main thread)
Shared data
Thread 2 (peer thread)
Thread 1 context:
Data
registers
Stack pointer
Condition codes
Program counter
rsp
Stack 1
Thread
2
context:
Data
registers
Stack pointer
Condition codes
Program counter
rsp
Stack 2
Kernel context:
VM structures
File table
brk pointer
0
brk
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 space
•
Open files and installed handlers
•
Operationally, this model is not strictly enforced:
•
Register values are truly separate and protected, but…
•
Any thread can read and write the stack of any other thread
The mismatch between the conceptual and operation model
is a source of confusion and errors
6
Threads vs. Processes
•
How threads and processes are similar
•
Each has its own logical control flow
•
Each can run concurrently with others (possibly on different
cores)
•
Each is scheduled and context switched
•
How threads and processes are different
•
Threads share all code and data (except local stacks)
•
Processes (typically) do not
•
Threads are somewhat less expensive than processes
•
Thread control (creating and reaping) is half as expensive as process
control
•
~20K cycles to create and reap a process
•
~10K cycles (or less) to create and reap a thread
•
Thread context switches are less expensive (e.g., don't flush TLB)
Logical View of Threads
•
Threads associated with process form a pool of peers
•
Unlike processes which form a tree hierarchy
Posix Threads Interface
C (Pthreads)
•
Creating and reaping threads
•
pthread_create()
•
pthread_join()
•
Determining your thread ID
•
pthread_self()
•
Terminating threads
•
pthread_cancel()
•
pthread_exit()
•
exit()
[terminates all threads]
•
RET
[terminates current thread]
Python (threading)
•
Creating and reaping threads
•
Thread()
•
thread.join()
•
Determining your thread ID
•
thread.get_ident()
•
Terminating threads
•
thread.exit()
•
RET
[terminates current thread]
void
*
thread
(
void
*
vargp
)
/* thread routine */
{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);
}
hello.c
hello.c
Example Program to Illustrate Sharing
11
11
char
**
ptr
;
/* global var */
int
main
()
{long
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
);
}
void
*
thread
(
void
*
vargp
)
{long
myid
= (
long
)vargp;
static
int
cnt
= 0;
printf(
"[%ld]: %s (cnt=%d)\n"
,
myid, ptr[myid], ++cnt);
return
NULL
;
}
sharing.c
Mapping Variable Instances to Memory
•
Global variables
•
Def:
Variable declared outside of a function
•
V
i
r
t
u
a
l
m
e
m
o
r
y
c
o
n
t
a
i
n
s
e
x
a
c
t
l
y
o
n
e
i
n
s
t
a
n
c
e
o
f
a
n
y
g
l
o
b
a
l
v
a
r
i
a
b
l
e
•
Local variables
•
Def:
Variable declared inside function without
static
attribute
•
E
a
c
h
t
h
r
e
a
d
s
t
a
c
k
c
o
n
t
a
i
n
s
o
n
e
i
n
s
t
a
n
c
e
o
f
e
a
c
h
l
o
c
a
l
v
a
r
i
a
b
l
e
•
Local static variables
•
Def:
Variable declared inside function with the
static
attribute
•
V
i
r
t
u
a
l
m
e
m
o
r
y
c
o
n
t
a
i
n
s
e
x
a
c
t
l
y
o
n
e
i
n
s
t
a
n
c
e
o
f
a
n
y
l
o
c
a
l
s
t
a
t
i
c
v
a
r
i
a
b
l
e
.
12
12
char
**
ptr
;
/* global var */
int
main
(){long
i
;
pthread_t
tid
;
char
*
msgs
[2] = {"Hello from foo"
,
"Hello from bar"
};
ptr = msgs;
for
(int i = 0; i < 2; i++)
Pthread_create(&tid,
NULL
,
thread, (
void
*)i);
Pthread_exit(
NULL
);
}
void
*
thread
(
void
*
vargp
){long
myid
= (
long
)vargp;
static
int
cnt
= 0;
printf(
"[%ld]: %s (cnt=%d)\n"
,
myid, ptr[myid], ++cnt);
return
NULL
;
}
Mapping Variable Instances to Memory
13
13
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 space
•
Open files and installed handlers
•
Operationally, this model is not strictly enforced:
•
Register values are truly separate and protected, but…
•
Any thread can read and write the stack of any other thread
The mismatch between the conceptual and operation model
is a source of confusion and errors
14
14
char
**
ptr
;
/* global var */
int
main
(){long
i
;
pthread_t
tid
;
char
*
msgs
[2] = {"Hello from foo"
,
"Hello from bar"
};
ptr = msgs;
for
(int i = 0; i < 2; i++)
Pthread_create(&tid,
NULL
,
thread, (
void
*)i);
Pthread_exit(
NULL
);
}
void
*
thread
(
void
*
vargp
){long
myid
= (
long
)vargp;
static
int
cnt
= 0;
printf(
"[%ld]: %s (cnt=%d)\n"
,
myid, ptr[myid], ++cnt);
return
NULL
;
}
Exercise 1: Shared Variables
Which variables are
shared?
•
ptr
•
cnt
•
i.main
•
msgs.main
•
myid.thread0
•
myid.thread1
15
15
Exercise 1: Shared Variables
•
Which variables are shared?
•
A variable
x
is shared iff multiple threads reference at least one
instance of
x
.
•
p
t
r
,
c
n
t
,
a
n
d
m
s
g
s
a
r
e
s
h
a
r
e
d
•
i
a
n
d
m
y
i
d
a
r
e
n
o
t
s
h
a
r
e
d
16
16
Variable
Referenced by
Referenced by
Referenced by
instance
main thread?
peer thread 0?
peer thread 1?
ptr
cnt
i.main
msgs.m
ain
myid.thread0
myid.
thread
1
yes
yes
yes
no
yes
yes
yes
no
no
yes
yes
yes
no
yes
no
no
no
yes
17
17
/* 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);
else
printf(
"OK cnt=%ld\n"
, cnt);
exit(0);
}
/* Thread routine */
void
*
thread
(
void
*
vargp
){long
i
,
niters;
niters
= *((
long
*)vargp);
for
(i = 0; i < niters; i++){cnt++;
}
return
NULL
;
}
linux> ./badcnt 10000
OK cnt=20000
linux> ./badcnt 10000
BOOM! cnt=13051
linux>
Why not Concurrent Programs?
Assembly Code for Counter Loop
18
18
for (i = 0; i < niters; i++)
cnt++;
C code for counter loop in 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:
Asm code for thread i
Race conditions
•
A race condition is a timing-dependent error involving
shared state
•
whether the error occurs depends on thread schedule
•
program execution/schedule can be non-deterministic
•
compilers and processors can re-order instructions
A concrete example…
•
You and your roommate share a refrigerator. Being good
roommates, you both try to make sure that the refrigerator
is always stocked with milk.
•
L
i
v
e
n
e
s
s
:
i
f
y
o
u
a
r
e
o
u
t
o
f
m
i
l
k
,
s
o
m
e
o
n
e
b
u
y
s
m
i
l
k
•
S
a
f
e
t
y
:
y
o
u
n
e
v
e
r
h
a
v
e
m
o
r
e
t
h
a
n
o
n
e
q
u
a
r
t
o
f
m
i
l
k
A
l
g
o
r
i
t
h
m
1
:
Look in fridge.
If out of milk:
go to store,
buy milk,
go home
put milk in fridge
A
l
g
o
r
i
t
h
m
1
:
if (milk == 0) {// no milk
milk++;
// buy milk
}
A problematic schedule
You
3:00
Look in fridge; out of milk
3:05
Leave for store
3:10
Arrive at store
3:15
Buy milk
3:20
Arrive home; put milk in
fridge
Your Roommate
3:10
Look in fridge; out of milk
3:15
Leave for store
3:20
Arrive at store
3:25
Buy milk
3:30
Arrive home; put milk in
fridge
Safety violation:
You have too much milk and it spoils
Solution 1: Leave a note
•
You and your roommate share a refrigerator. Being good
roommates, you both try to make sure that the refrigerator
is always stocked with milk.
A
l
g
o
r
i
t
h
m
2
:
if (milk == 0) {// no milk
if (note == 0) {// no note
note = 1;
// leave note
milk++;
// buy milk
note = 0;
// remove note
}
}
Safety violation: you've introduced a Heisenbug!
Solution 2: Leave note before check note
•
You and your roommate share a refrigerator. Being good
roommates, you both try to make sure that the refrigerator
is always stocked with milk.
A
l
g
o
r
i
t
h
m
3
:
note1 = 1
if (note2 == 0) { // no note fromroommate
if (milk == 0) {// no milkmilk++;
// buy milk
}
}
note1 = 0
Liveness violation: No one buys milk
Solution 3: Keep checking for note
•
You and your roommate share a refrigerator. Being good
roommates, you both try to make sure that the refrigerator
is always stocked with milk.
A
l
g
o
r
i
t
h
m
4
:
note1 = 1
while (note2 == 1) {// wait until
;
// no note
}
if (milk == 0) {// no milk
milk++;
// buy milk
}
note1 = 0
Liveness violation: You've introduced deadlock
Solution 4: Take turns
•
You and your roommate share a refrigerator. Being good
roommates, you both try to make sure that the refrigerator
is always stocked with milk.
A
l
g
o
r
i
t
h
m
5
:
note1 = 1
turn = 2
while (note2 == 1 and turn == 2){;
}
if (milk == 0) {// no milk
milk++;
// buy milk
}
note1 = 0
(probably) correct, but complicated and inefficient
Locks
•
A
l
o
c
k
(
a
k
a
a
m
u
t
e
x
)
i
s
a
s
y
n
c
h
r
o
n
i
z
a
t
i
o
n
p
r
i
m
i
t
i
v
e
t
h
a
t
p
r
o
v
i
d
e
s
m
u
t
u
a
l
e
x
c
l
u
s
i
o
n
.
W
h
e
n
o
n
e
t
h
r
e
a
d
h
o
l
d
s
a
l
o
c
k
,
n
o
o
t
h
e
r
t
h
r
e
a
d
c
a
n
h
o
l
d
i
t
.
•
a lock can be in one of two states: locked or unlocked
•
a lock is initially unlocked
•
function acquire(&lock) waits until the lock is unlocked, then
atomically sets it to locked
•
function release(&lock) sets the lock to unlocked
Solution 5: use a lock
•
You and your roommate share a refrigerator. Being good
roommates, you both try to make sure that the refrigerator
is always stocked with milk.
A
l
g
o
r
i
t
h
m
6
:
acquire(&lock)
if (milk == 0) {// no milk
milk++;
// buy milk
}
release(&lock)
Correct!
Atomic Operations
•
Solution: hardware primitives to support synchronization
•
A machine instruction that (atomically!) reads and updates
a memory location
•
Example:
xchg
src, dest
•
one instruction
•
semantics: TEMP ← DEST; DEST ← SRC; SRC ← TEMP;
Spinlocks
acquire:
mov $1, eax
; Set EAX to 1
xchg eax, (rdi)
; Atomically swap EAX w/
lock val
test eax, eax
; check if EAX is 0 (lock unlocked)
jnz acquire
; if was locked, loop
ret
; lock has been acquired, return
release:
xor eax, eax
; Set EAX to 0
xchg eax, (rdi)
; Atomically swap EAX w/ lock val
ret
; lock has been released, return
Programming with Locks
C (pthreads)
•
Defines lock type pthread_mutex_t
•
functions to create/destroy
locks:
•
i
n
t
p
t
h
r
e
a
d
_
m
u
t
e
x
_
i
n
i
t
(
&
l
o
c
k
,
a
t
t
r
)
;
•
int pthread_mutex_destroy(&lock);
•
functions to acquire/release
lock:
•
i
n
t
p
t
h
r
e
a
d
_
m
u
t
e
x
_
l
o
c
k
(
&
l
o
c
k
)
;
•
i
n
t
p
t
h
r
e
a
d
_
m
u
t
e
x
_
u
n
l
o
c
k
(
&
l
o
c
k
)
;
Python (threading)
•
Defines class Lock
•
constructor to create locks:
•
Lock()
•
destroyed by garbage collector
•
functions to aquire/release
lock:
•
lock.acquire()
•
lock.release()
Exercise 2: Locks
•
TODO: Modify this example
to guarantee correctness
/* 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);
else
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++){cnt++;
}
return
NULL
;
}
Problems with Locks
1.
Locks are slow
•
threads that fail to acquire a lock on the first attempt must "spin",
which wastes CPU cycles
•
threads get scheduled and de-scheduled while the lock is still
locked
2.
Using locks correctly is hard
•
hard to ensure all race conditions are eliminated
•
easy to introduce synchronization bugs (deadlock, livelock)
Better Synchronization Primitives
•
Semaphores
•
stateful synchronization primitive
•
Condition variables
•
event-based synchronization primitive
Exercise 3: Feedback
1.
Rate how well you think this recorded lecture worked
1.
Better than an in-person class
2.
About as well as an in-person class
3.
Less well than an in-person class, but you still learned something
4.
Total waste of time, you didn't learn anything
2.
How much time did you spend on this video (including
exercises)?
3.
Do you have any particular questions you’d like me to
address in this week’s problem session?
4.
Do you have any other comments or feedback?
Concurrency in computer science involves running multiple threads or processes simultaneously, providing responsiveness, managing I/O devices, and improving performance by utilizing multiprocessors. This concept allows programs to handle tasks more efficiently and effectively through parallel execution. The comparison between threads and processes highlights their similarities in logical control flow and differences in data sharing and cost efficiency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 21: Concurrency CS 105
Why Concurrent Programs? Program Structure: expressing logically concurrent programs Responsiveness: shifting work to run in the background 1.2 1.06 Elapsed time (s) 1 0.8 0.6 0.540.28 0.3 0.29 0.4 0.2 0 1 2 Threads 4 8 16 Responsiveness: managing I/O devices Performance: exploiting multiprocessors
Traditional View of a Process Process = process context + (virtual) memory state Virtual Memory Process Control Block Program context: Data registers Stack pointer (rsp) Condition codes Program counter (rip) Kernel context: VM structures File table brk pointer Stack rsp brk Heap Data rip Code 0
Alternate View of a Process Process = thread + other state Thread (main thread) Other data brk Heap Stack Data rsp Code Thread context: Data registers Stack pointer (rsp) Condition codes Program counter (rip) 0 Kernel context: VM structures File table brk pointer
A Process With Multiple Threads Multiple threads can be associated with a process Each thread has its own logical control flow Each thread has its own stack for local variables Each thread has its own thread id (TID) Each thread shares the same code, data, and kernel context Thread 1 (main thread) Thread 2 (peer thread) Shared data brk Heap Stack 1 Stack 2 Data rsp rsp Code Thread 1 context: Data registers Stack pointer Condition codes Program counter Thread 2 context: Data registers Stack pointer Condition codes Program counter 0 Kernel context: VM structures File table brk pointer
Threads vs. Processes How threads and processes are similar Each has its own logical control flow Each can run concurrently with others (possibly on different cores) Each is scheduled and context switched How threads and processes are different Threads share all code and data (except local stacks) Processes (typically) do not Threads are somewhat less expensive than processes Thread control (creating and reaping) is half as expensive as process control ~20K cycles to create and reap a process ~10K cycles (or less) to create and reap a thread Thread context switches are less expensive (e.g., don't flush TLB)
Logical View of Threads Threads associated with process form a pool of peers Unlike processes which form a tree hierarchy Process hierarchy Threads associated with process foo P0 T2 T4 T1 P1 shared code, data and kernel context sh sh sh T3 T5 foo bar
Posix Threads Interface C (Pthreads) Python (threading) Creating and reaping threads pthread_create() pthread_join() Determining your thread ID pthread_self() Terminating threads pthread_cancel() pthread_exit() exit() [terminates all threads] RET [terminates current thread] Creating and reaping threads Thread() thread.join() Determining your thread ID thread.get_ident() Terminating threads thread.exit() RET [terminates current thread]
The Pthreads "hello, world" Program /* * hello.c - Pthreads "hello, world" program */ #include "csapp.h" void *thread(void *vargp); Thread attributes (usually NULL) Thread ID int main() { pthread_t tid; Pthread_create(&tid, NULL, thread, NULL); Pthread_join(tid, NULL); exit(0); } Thread routine Thread arguments (void *p) hello.c Return value (void **p) void *thread(void *vargp) /* thread routine */ { printf("Hello, world!\n"); return NULL; } hello.c
11 Example Program to Illustrate Sharing void *thread(void *vargp) { long myid = (long)vargp; static int cnt = 0; char **ptr; /* global var */ int main() { long i; pthread_t tid; char *msgs[2] = { "Hello from foo", "Hello from bar" }; printf("[%ld]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt); return NULL; } Peer threads reference main thread s stack indirectly through global ptr variable ptr = msgs; for (i = 0; i < 2; i++) Pthread_create(&tid, NULL, thread, (void *)i); Pthread_exit(NULL); } sharing.c
12 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.
13 Mapping Variable Instances to Memory Global var: 1 instance (ptr [data]) Local vars: 1 instance (i.m, msgs.m) char **ptr; /* global var */ int main(){ long i; pthread_t tid; char *msgs[2] = {"Hello from foo", "Hello from bar"}; ptr = msgs; for (int i = 0; i < 2; i++) Pthread_create(&tid, NULL, thread, (void *)i); Pthread_exit(NULL); } 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]) void *thread(void *vargp){ long myid = (long)vargp; static int cnt = 0; printf("[%ld]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt); return NULL; }
15 Exercise 1: Shared Variables char **ptr; /* global var */ Which variables are shared? int main(){ long i; pthread_t tid; char *msgs[2] = {"Hello from foo", "Hello from bar"}; ptr = msgs; for (int i = 0; i < 2; i++) Pthread_create(&tid, NULL, thread, (void *)i); Pthread_exit(NULL); } ptr cnt i.main msgs.main myid.thread0 myid.thread1 void *thread(void *vargp){ long myid = (long)vargp; static int cnt = 0; printf("[%ld]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt); return NULL; }
16 Exercise 1: Shared Variables Which variables are shared? A variable x is shared iff multiple threads reference at least one instance of x. Variable instance Referenced by main thread? Referenced by peer thread 0? Referenced by peer thread 1? yes no yes yes no no yes yes no yes yes no yes yes no yes no yes ptr cnt i.main msgs.main myid.thread0 myid.thread1 ptr, cnt, and msgs are shared i and myid are not shared
17 Why not Concurrent Programs? /* Thread routine */ void *thread(void *vargp){ long i, niters; niters = *((long *)vargp); for (i = 0; i < niters; i++){ cnt++; } /* 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); return NULL; } linux> ./badcnt 10000 OK cnt=20000 linux> ./badcnt 10000 BOOM! cnt=13051 linux> /* Check result */ if (cnt != (2 * niters)) printf("BOOM! cnt=%ld\n", cnt); else printf("OK cnt=%ld\n", cnt); exit(0); }
18 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 : Store cnt Ti : Tail
Race conditions A race condition is a timing-dependent error involving shared state whether the error occurs depends on thread schedule program execution/schedule can be non-deterministic compilers and processors can re-order instructions
A concrete example You and your roommate share a refrigerator. Being good roommates, you both try to make sure that the refrigerator is always stocked with milk. Liveness: if you are out of milk, someone buys milk Safety: you never have more than one quart of milk Algorithm 1: Algorithm 1: Look in fridge. If out of milk: go to store, buy milk, go home put milk in fridge if (milk == 0) { milk++; } // no milk // buy milk
A problematic schedule You Your Roommate 3:00 3:05 3:10 3:15 3:20 fridge Look in fridge; out of milk Leave for store Arrive at store Buy milk Arrive home; put milk in 3:10 3:15 3:20 3:25 3:30 fridge Look in fridge; out of milk Leave for store Arrive at store Buy milk Arrive home; put milk in Safety violation: You have too much milk and it spoils
Solution 1: Leave a note You and your roommate share a refrigerator. Being good roommates, you both try to make sure that the refrigerator is always stocked with milk. Algorithm 2: if (milk == 0) { if (note == 0) { // no note note = 1; milk++; note = 0; } } // no milk // leave note // buy milk // remove note Safety violation: you've introduced a Heisenbug!
Solution 2: Leave note before check note You and your roommate share a refrigerator. Being good roommates, you both try to make sure that the refrigerator is always stocked with milk. Algorithm 3: note1 = 1 if (note2 == 0) { // no note from if (milk == 0) {// no milk milk++; // buy milk } } note1 = 0 roommate Liveness violation: No one buys milk
Solution 3: Keep checking for note You and your roommate share a refrigerator. Being good roommates, you both try to make sure that the refrigerator is always stocked with milk. Algorithm 4: note1 = 1 while (note2 == 1) { // wait until ; } if (milk == 0) { milk++; } note1 = 0 // no note // no milk // buy milk Liveness violation: You've introduced deadlock
Solution 4: Take turns You and your roommate share a refrigerator. Being good roommates, you both try to make sure that the refrigerator is always stocked with milk. Algorithm 5: note1 = 1 turn = 2 while (note2 == 1 and turn == 2){ ; } if (milk == 0) { milk++; } note1 = 0 // no milk // buy milk (probably) correct, but complicated and inefficient
Locks A lock (aka a mutex) is a synchronization primitive that provides mutual exclusion. When one thread holds a lock, no other thread can hold it. a lock can be in one of two states: locked or unlocked a lock is initially unlocked function acquire(&lock) waits until the lock is unlocked, then atomically sets it to locked function release(&lock) sets the lock to unlocked
Solution 5: use a lock You and your roommate share a refrigerator. Being good roommates, you both try to make sure that the refrigerator is always stocked with milk. Algorithm 6: acquire(&lock) if (milk == 0) { milk++; } release(&lock) // no milk // buy milk Correct!
Atomic Operations Solution: hardware primitives to support synchronization A machine instruction that (atomically!) reads and updates a memory location Example: xchgsrc, dest one instruction semantics: TEMP DEST; DEST SRC; SRC TEMP;
Spinlocks acquire: mov $1, eax xchg eax, (rdi) test eax, eax jnz acquire ret ; Set EAX to 1 ; Atomically swap EAX w/lock val ; check if EAX is 0 (lock unlocked) ; if was locked, loop ; lock has been acquired, return release: xor eax, eax xchg eax, (rdi) ret ; Set EAX to 0 ; Atomically swap EAX w/ lock val ; lock has been released, return
Programming with Locks C (pthreads) Python (threading) Defines class Lock Defines lock type pthread_mutex_t functions to create/destroy locks: int pthread_mutex_init(&lock, attr); int pthread_mutex_destroy(&lock); constructor to create locks: Lock() destroyed by garbage collector functions to aquire/release lock: lock.acquire() lock.release() functions to acquire/release lock: int pthread_mutex_lock(&lock); int pthread_mutex_unlock(&lock);
Exercise 2: Locks /* Thread routine */ void *thread(void *vargp) { long i, niters = *((long *)vargp); for (i = 0; i < niters; i++){ cnt++; } /* 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); return NULL; } TODO: Modify this example to guarantee correctness /* Check result */ if (cnt != (2 * niters)) printf("BOOM! cnt=%ld\n", cnt); else printf("OK cnt=%ld\n", cnt); exit(0); }
Problems with Locks 1. Locks are slow threads that fail to acquire a lock on the first attempt must "spin", which wastes CPU cycles threads get scheduled and de-scheduled while the lock is still locked 2. Using locks correctly is hard hard to ensure all race conditions are eliminated easy to introduce synchronization bugs (deadlock, livelock)
Better Synchronization Primitives Semaphores stateful synchronization primitive Condition variables event-based synchronization primitive
Exercise 3: Feedback 1. Rate how well you think this recorded lecture worked 1. Better than an in-person class 2. About as well as an in-person class 3. Less well than an in-person class, but you still learned something 4. Total waste of time, you didn't learn anything 2. How much time did you spend on this video (including exercises)? 3. Do you have any particular questions you d like me to address in this week s problem session? 4. Do you have any other comments or feedback?
