Carnegie Mellon Multithreaded Synchronization Recitation
15/18-213 Recitation:
Multithreaded Synchronization
Isaac Manjarres
Recitation 14:
30 Nov 2015
Agenda
■
Proxy Lab
■
Basic server code examples
■
Debugging tools
■
Concurrency
■
The Good, The Bad, and The Ugly
■
Shared Memory: Synchronization
▪
Critical Sections and Locking
■
Common bugs
Proxy Lab
■
Due next Tuesday on December 8
th
, 2015
■
You may use a MAX of two late days
■
Make it robust to unexpected hiccups in input
■
The Internet is standardized, but not really
The Echo Server – Sequential Handling
void echo(int connfd) {size_t n; char buf[MAXLINE]; rio_t rio;
// initialize robust io for reading on file descriptor
Rio_readinitb(&rio, connfd);
while((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) {printf("server received %d bytes\n", (int)n);// read to buffer, and write it back
Rio_writen(connfd, buf, n);
}
}
The Echo Server – Sequential Handling
int main(int argc, char **argv) {int listenfd, connfd;
struct sockaddr_storage clientaddr; socklen_t clientlen;
char client_hostname[MAXLINE]; client_port[MAXLINE];
listenfd = Open_listenfd(argv[1]);
while(1) { // Handle requests one at a time. I hope I’m not popular!
clientlen = sizeof(struct sockaddr_storage);
// Important!
connfd = Accept(listenfd, (SA*)&clientaddr, &clientlen);
Getnameinfo((SA*)&clientaddr, clientlen, client_hostname,
MAXLINE, client_port, MAXLINE, 0);
echo(connfd);
Close(connfd);
}
assert(0);
}
The Echo Server: Finding Its Weakness
Using
telnet
, we can observe a weakpoint within this
iterative approach.
The second client cannot connect, because echo has
not yet closed its connection with the first client.
telnet localhost 15213
./echo 15213
telnet localhost 15213
More Advanced Debugging
■
Telnet requires you to type everything yourself
■
Web protocols (like HTTP) can be tedious to type
■
Use
curl
to form requests for you
curl --proxy
http://localhost:port
url.com
■
Redirect output using
>
, for non-text files
■
Don’t forget that binary data is not the same as text
data
■
Be careful when using functions that are meant to
operate only on strings. They will not work
properly with binary data
How Threads Work: Nuances
■
Threads run within the same process context
■
Arbitrary interleaving and parallelization similar to
processes from Shell Lab
■
B
u
t
k
e
e
p
i
n
m
i
n
d
t
h
e
y
a
r
e
s
e
p
a
r
a
t
e
l
o
g
i
c
a
l
f
l
o
w
s
,
n
o
t
s
e
p
a
r
a
t
e
p
r
o
c
e
s
s
e
s
■
This implies that there are still context switches, much
like with processes, but they are of less duration since
threads have less context to store away than processes
Critical Points for Threads
■
Threads have their own:
■
Thread ID
■
Stack(contained within the stack area for that process)
■
Stack Pointer
■
Instruction Pointer
■
General Purpose Registers
■
Status Codes
■
Threads share:
■
Code sections
■
Heap
■
Open files
Anatomy of pthread_create
■
Threads created with
pthread_create
:
int pthread_create(pthread_t *threadID,
const pthread_attr_t *attr,
void *(*start_routine)(void *), void
*arg);
P
o
i
n
t
e
r
t
o
a
v
a
r
i
a
b
l
e
t
h
a
t
w
i
l
l
h
o
l
d
t
h
e
n
e
w
t
h
r
e
a
d
’
s
I
D
N
U
L
L
f
o
r
t
h
i
s
c
o
u
r
s
e
P
o
i
n
t
e
r
t
o
a
f
u
n
c
t
i
o
n
t
h
a
t
t
a
k
e
s
i
n
a
v
o
i
d
p
o
i
n
t
e
r
,
a
n
d
r
e
t
u
r
n
s
a
v
o
i
d
p
o
i
n
t
e
r
.
T
h
i
s
f
u
n
c
t
i
o
n
i
s
w
h
a
t
t
h
e
n
e
w
t
h
r
e
a
d
w
i
l
l
e
x
e
c
u
t
e
.
P
o
i
n
t
e
r
t
o
a
n
a
r
g
u
m
e
n
t
f
o
r
t
h
e
f
u
n
c
t
i
o
n
t
h
a
t
t
h
e
t
h
r
e
a
d
w
i
l
l
e
x
e
c
u
t
e
.
C
a
n
p
a
s
s
M
u
l
t
i
p
l
e
a
r
g
u
m
e
n
t
s
b
y
p
u
t
t
i
n
g
t
h
e
m
i
n
a
s
t
r
u
c
t
a
n
d
p
a
s
s
i
n
g
a
p
o
i
n
t
e
r
t
o
t
h
e
s
t
r
u
c
t
Working Together: When to use Threads
Let’s sum up the elements in an array.
T
h
e
b
o
r
i
n
g
w
a
y
:
int sum = 0;
for (int i = 0; i < n; i++)
sum += nums[i];
Sums: The Fun Way
void *thread_fun(void *vargp) {int myid = *((int *)vargp);
size_t start = myid * nelems_per_thread;
size_t end = start + nelems_per_thread;
size_t i;
size_t index = myid*spacing;
data_t sum = 0;
for (i = start; i < end; i++)
// sum our section
sum += i;
psum[index] = sum;
return NULL;
}
Sums: The Fun Way
nelems_per_thread = nelems / nthreads;
// Create threads and wait for them to finish
for (i = 0; i < nthreads; i++) {myid[i] = i;
Pthread_create(&tid[i], NULL, thread_fun, &myid[i]);
}
for (i = 0; i < nthreads; i++)
Pthread_join(tid[i], NULL);
Sums: The Fun Way
result = 0;
// Add up the partial sums computed by each thread
for (i = 0; i < nthreads; i++)
result += psum[i*spacing];
// Add leftover elements
for (e = nthreads * nelems_per_thread; e < nelems; e++)
result += e;
return result;
Advantages & Disadvantages
Good:
■
We can (potentially) make it faster
■
We can exploit better use of the cache
Bad:
■
H
a
r
d
t
o
w
r
i
t
e
!
■
Shared resources difficult to manage
Here, we provide
mutual exclusion
by going to different
sections of the array between threads, but we can’t
always do this.
Critical Sections and Shared Variables
Let’s try some more counting with threads.
volatile int total = 0;
void incr(void *ptr) {pthread_detach(pthread_self());
for (int i = 0; i < *ptr; i++)
total++;
}
Critical Sections and Shared Variables
#define NTHREADS 2
#define NINCR 100
int main() {pthread_t tids[NTHREADS];
int y = NINCR;
for (int i = 0; i < NTHREADS; i++)
pthread_create(&tids[i], NULL, incr, &y);
// output will range between NTHREADS-y*NTHREADS
printf(“total is: %d”, total);
}
What happens
total
thread 1
thread 2
1
2
2
3
2
1
1
0
2
Mutexes
S
o
l
u
t
i
o
n
:
L
o
c
k
/
s
u
s
p
e
n
d
e
x
e
c
u
t
i
o
n
o
f
t
h
r
e
a
d
u
n
t
i
l
r
e
s
o
u
r
c
e
i
s
“
a
c
q
u
i
r
e
d
”
volatile int total = 0;
pthread_mutex_t M;
void incr(void *ptr) {pthread_detach(pthread_self());
for (int i = 0; i < *ptr; i++) {pthread_mutex_lock(&M);
total++;
// CRITICAL SECTION
pthread_mutex_unlock(&M);
}
}
Mutexes
Remember to initialize the mutex first!
#define NTHREADS 2
#define NINCR 100
volatile int total = 0;
pthread_mutex_t M;
...
int main() {...
pthread_mutex_init(&M);
...
}
Semaphores and Atomicity
Problem solved… right?
■
Locks in threads are
slow
■
T
h
i
s
i
s
a
t
e
r
r
i
b
l
e
w
a
y
t
o
s
u
m
u
p
t
o
2
0
0
■
Avoid shared memory if you can
■
This is one of the simpler models for thread sync.
■
Reading vs. Writing
■
Producers and Consumers
Synchronization Gone Wrong Part 1
Synchronization Gone Wrong Part 2
■
What’s wrong with this?
■
Note how there is only a small fraction of time per
thread where calculations are actually being done
■
The great majority of the time is spent waiting to
execute calculations again
■
This is a waste of valuable processor time
■
Do not do this
■
Solution
■
Write code that will minimize the amount of time
that the processor is not doing anything useful
Readers and Writers
cache
reader
writer
reader
reader
reader
Readers and Writers
cache
reader
writer
reader
reader
reader
:(
Readers and Writers
cache
reader
writer
reader
reader
reader
Readers and Writers
cache
reader
writer
reader
reader
reader
:(
Readers and Writers
cache
reader
writer
reader
reader
reader
Concurrency and Starvation
■
In previous example, readers block one writer
■
Writer might not get the resource
■
W
r
i
t
e
r
i
s
b
e
i
n
g
s
t
a
r
v
e
d
o
f
r
e
s
o
u
r
c
e
■
Make sure that readers don’t hold resource for long
P
r
o
b
l
e
m
:
D
e
a
d
l
o
c
k
Thread 1
Thread 2
I’ll give you x
if you give
me y.
I’ll give you y
if you give
me x.
Well, that’s
awkward.
P
r
o
b
l
e
m
:
D
e
a
d
l
o
c
k
■
Entire program will hang
■
Pay attention to how and where you lock/unlock
■
Program may or may not hang predictably
■
Thread scheduling is non-deterministic
■
Similar to race conditions, usually worse
■
C
r
i
t
i
c
a
l
s
e
c
t
i
o
n
s
h
o
u
l
d
b
e
a
s
s
m
a
l
l
a
s
p
o
s
s
i
b
l
e
P
r
o
b
l
e
m
:
L
i
v
e
l
o
c
k
■
Similar to Deadlock
■
Two programs feed back on one another
■
Spins indefinitely instead of hanging
■
Two people trying to get past each other in a hallway
■
Both move the same direction simultaneously
■
Both do an awkward dance from side to side
■
Dance continues indefinitely
■
Often happens when threads attempt to compensate
for deadlock
Recognitions
■
Slides adapted from Jack Biggs
Explore Carnegie Mellon's recitation on multithreaded synchronization, debugging tools, shared memory synchronization, critical sections, and locking. Dive into the Echo Server Sequential Handling code examples, finding weaknesses using telnet, and advanced debugging techniques with curl and binary data. The Proxy Lab emphasizes robustness and handling unexpected hiccups in input while discussing the standardization of the internet.
Uploaded on Sep 19, 2024 | 0 Views
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
Carnegie Mellon 15/18-213 Recitation: Multithreaded Synchronization Isaac Manjarres Recitation 14: 30 Nov 2015
Carnegie Mellon Agenda Proxy Lab Basic server code examples Debugging tools Concurrency The Good, The Bad, and The Ugly Shared Memory: Synchronization Critical Sections and Locking Common bugs
Carnegie Mellon Proxy Lab Due next Tuesday on December 8th, 2015 You may use a MAX of two late days Make it robust to unexpected hiccups in input The Internet is standardized, but not really
Carnegie Mellon The Echo Server Sequential Handling void echo(int connfd) { size_t n; char buf[MAXLINE]; rio_t rio; // initialize robust io for reading on file descriptor Rio_readinitb(&rio, connfd); while((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) { printf("server received %d bytes\n", (int)n); // read to buffer, and write it back Rio_writen(connfd, buf, n); } }
Carnegie Mellon The Echo Server Sequential Handling int main(int argc, char **argv) { int listenfd, connfd; struct sockaddr_storage clientaddr; socklen_t clientlen; char client_hostname[MAXLINE]; client_port[MAXLINE]; listenfd = Open_listenfd(argv[1]); while(1) { // Handle requests one at a time. I hope I m not popular! clientlen = sizeof(struct sockaddr_storage); // Important! connfd = Accept(listenfd, (SA*)&clientaddr, &clientlen); Getnameinfo((SA*)&clientaddr, clientlen, client_hostname, MAXLINE, client_port, MAXLINE, 0); echo(connfd); Close(connfd); } assert(0); }
Carnegie Mellon The Echo Server: Finding Its Weakness Using telnet, we can observe a weakpoint within this iterative approach. telnet localhost 15213 telnet localhost 15213 ./echo 15213 The second client cannot connect, because echo has not yet closed its connection with the first client.
Carnegie Mellon More Advanced Debugging Telnet requires you to type everything yourself Web protocols (like HTTP) can be tedious to type Use curl to form requests for you curl --proxy http://localhost:port url.com Redirect output using >, for non-text files Don t forget that binary data is not the same as text data Be careful when using functions that are meant to operate only on strings. They will not work properly with binary data
Carnegie Mellon How Threads Work: Nuances Threads run within the same process context Arbitrary interleaving and parallelization similar to processes from Shell Lab But keep in mind they are separate logical flows, not separate processes This implies that there are still context switches, much like with processes, but they are of less duration since threads have less context to store away than processes
Carnegie Mellon Critical Points for Threads Threads have their own: Thread ID Stack(contained within the stack area for that process) Stack Pointer Instruction Pointer General Purpose Registers Status Codes Threads share: Code sections Heap Open files
Carnegie Mellon Anatomy of pthread_create Pointer to a variable that will hold the new thread s ID Threads created with pthread_create: int pthread_create(pthread_t *threadID, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg); NULL for this course Pointer to a function that takes in a void pointer, and returns a void pointer. This function is what the new thread will execute. Pointer to an argument for the function that the thread will execute. Can pass Multiple arguments by putting them in a struct and passing a pointer to the struct
Carnegie Mellon Working Together: When to use Threads Let s sum up the elements in an array. The boring way: int sum = 0; for (int i = 0; i < n; i++) sum += nums[i];
Carnegie Mellon Sums: The Fun Way void *thread_fun(void *vargp) { int myid = *((int *)vargp); size_t start = myid * nelems_per_thread; size_t end = start + nelems_per_thread; size_t i; size_t index = myid*spacing; data_t sum = 0; for (i = start; i < end; i++) // sum our section sum += i; psum[index] = sum; return NULL; }
Carnegie Mellon Sums: The Fun Way nelems_per_thread = nelems / nthreads; // Create threads and wait for them to finish for (i = 0; i < nthreads; i++) { myid[i] = i; Pthread_create(&tid[i], NULL, thread_fun, &myid[i]); } for (i = 0; i < nthreads; i++) Pthread_join(tid[i], NULL);
Carnegie Mellon Sums: The Fun Way result = 0; // Add up the partial sums computed by each thread for (i = 0; i < nthreads; i++) result += psum[i*spacing]; // Add leftover elements for (e = nthreads * nelems_per_thread; e < nelems; e++) result += e; return result;
Carnegie Mellon Advantages & Disadvantages Good: We can (potentially) make it faster We can exploit better use of the cache Bad: Hard to write! Shared resources difficult to manage Here, we provide mutual exclusion by going to different sections of the array between threads, but we can t always do this.
Carnegie Mellon Critical Sections and Shared Variables Let s try some more counting with threads. volatile int total = 0; void incr(void *ptr) { pthread_detach(pthread_self()); for (int i = 0; i < *ptr; i++) total++; }
Carnegie Mellon Critical Sections and Shared Variables #define NTHREADS 2 #define NINCR 100 int main() { pthread_t tids[NTHREADS]; int y = NINCR; for (int i = 0; i < NTHREADS; i++) pthread_create(&tids[i], NULL, incr, &y); // output will range between NTHREADS-y*NTHREADS printf( total is: %d , total); }
Carnegie Mellon What happens 1 0 2 1 1 2 3 total 2 2 thread 1 thread 2
Carnegie Mellon Mutexes Solution: Lock/suspend execution of thread until resource is acquired volatile int total = 0; pthread_mutex_t M; void incr(void *ptr) { pthread_detach(pthread_self()); for (int i = 0; i < *ptr; i++) { pthread_mutex_lock(&M); total++; // CRITICAL SECTION pthread_mutex_unlock(&M); } }
Carnegie Mellon Mutexes Remember to initialize the mutex first! #define NTHREADS 2 #define NINCR 100 volatile int total = 0; pthread_mutex_t M; ... int main() { ... pthread_mutex_init(&M); ... }
Carnegie Mellon Semaphores and Atomicity A semaphore is a special counter with an invariant Let s represent some semaphore, and T be the time domain Invariant: At any given time, the value of a semaphore is non-negative (i.e. ? ?.??? ? 0) Mutexes are a subclass of semaphores in the sense that they either have a value of 0 or 1 P(s) operation locks a resource (by decrementing the value of s) such that when another thread tries to lock the resource by calling P(s), the value may be 0, and that thread will be suspended until the value of s is greater than 0 V(s) operation frees a resource (by incrementing the value of s) such that when it is called, s now has a value greater than 0, and any thread that may have been asleep as a result of waiting for s to be free can now be woken up Atomic Operation-An operation that is not interrupted once it has begun executing P and V operations are atomic
Carnegie Mellon Problem solved right? Locks in threads are slow This is a terrible way to sum up to 200 Avoid shared memory if you can This is one of the simpler models for thread sync. Reading vs. Writing Producers and Consumers
Carnegie Mellon Synchronization Gone Wrong Part 1
Carnegie Mellon Synchronization Gone Wrong Part 2 What s wrong with this? Note how there is only a small fraction of time per thread where calculations are actually being done The great majority of the time is spent waiting to execute calculations again This is a waste of valuable processor time Do not do this Solution Write code that will minimize the amount of time that the processor is not doing anything useful
Carnegie Mellon Readers and Writers writer cache reader reader reader reader
Carnegie Mellon Readers and Writers :( writer cache reader reader reader reader
Carnegie Mellon Readers and Writers writer cache reader reader reader reader
Carnegie Mellon Readers and Writers writer cache reader :( reader reader reader
Carnegie Mellon Readers and Writers writer cache reader reader reader reader
Carnegie Mellon Concurrency and Starvation In previous example, readers block one writer Writer might not get the resource Writer is being starved of resource Make sure that readers don t hold resource for long
Carnegie Mellon Problem: Deadlock I ll give you x if you give me y. I ll give you y if you give me x. Well, that s awkward. Thread 1 Thread 2
Carnegie Mellon Problem: Deadlock Entire program will hang Pay attention to how and where you lock/unlock Program may or may not hang predictably Thread scheduling is non-deterministic Similar to race conditions, usually worse Critical section should be as small as possible
Carnegie Mellon Problem: Livelock Similar to Deadlock Two programs feed back on one another Spins indefinitely instead of hanging Two people trying to get past each other in a hallway Both move the same direction simultaneously Both do an awkward dance from side to side Dance continues indefinitely Often happens when threads attempt to compensate for deadlock
Carnegie Mellon Recognitions Slides adapted from Jack Biggs
