程序代写代做代考 kernel C data structure cache concurrency Carnegie Mellon

程序代写 CS代考 / concurrency, C语言代写, data structure, kernel

Carnegie Mellon
Concurrent Programming
15-213: Introduction to Computer Systems 24rd Lecture, April 14, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1

Carnegie Mellon
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2

Carnegie Mellon
Data Race
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3

Carnegie Mellon
Deadlock
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4

Carnegie Mellon
Deadlock
 
Example from signal handlers.
Why don’t we use printf in handlers?
void catch_child(int signo) {
printf(“Child exited!\n”); // this call may reenter printf/puts! BAD! DEADLOCK! while (waitpid(-1, NULL, WNOHANG) > 0) continue; // reap all children
}

Printf code:
 Acquire lock  Do something  Release lock
Icurr lock Inext
signal
(Try to) acquire lock
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
Acquire Receive

Carnegie Mellon
Deadlock
 
Example from signal handlers.
Why don’t we use printf in handlers?
void catch_child(int signo) {
printf(“Child exited!\n”); // this call may reenter printf/puts! BAD! DEADLOCK! while (waitpid(-1, NULL, WNOHANG) > 0) continue; // reap all children
}

Printf code:
 Acquire lock  Do something  Release lock
Icurr lock Inext
signal
(Try to) acquire lock
Acquire Receive

What if signal handler interrupts call to printf?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
Deadlocked!

Carnegie Mellon
Testing Printf Deadlock
void catch_child(int signo) {
printf(“Child exited!\n”); // this call may reenter printf/puts! BAD! DEADLOCK! while (waitpid(-1, NULL, WNOHANG) > 0) continue; // reap all children
}
int main(int argc, char** argv) {
…
for (i = 0; i < 1000000; i++) { if (fork() == 0) { // in child, exit immediately exit(0); } // in parent sprintf(buf, "Child #%d started\n", i); printf("%s", buf); } return 0; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 7 Child #0 started Child #1 started Child #2 started Child #3 started Child exited! Child #4 started Child exited! Child #5 started . . . Child #5888 started Child #5889 started Carnegie Mellon Why Does Printf require Locks?  Printf (and fprintf, sprintf) implement buffered I/O Buffered Portion Current File Position  Require locks to access the shared buffers no longer in buffer already read unread unseen Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8 Carnegie Mellon Livelock Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9 Carnegie Mellon Livelock Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10 Carnegie Mellon Starvation  Yellow must yield to green  Continuous stream of green cars  Overall system makes progress, but some individuals wait indefinitely Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 11 Carnegie Mellon 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?  Deadlock: improper resource allocation prevents forward progress  Example: traffic gridlock  Livelock / Starvation / Fairness: external events and/or system scheduling decisions can prevent sub-task progress  Example: people always jump in front of you in line  Many aspects of concurrent programming are beyond the scope of our course..  but, not all  We’ll cover some of these aspects in the next few lectures. Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 12 Carnegie Mellon Concurrent Programming is Hard! It may be hard, but ... it can be useful and msoomretaimndesmnoerceensseacreys!sary! Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13 Carnegie Mellon Reminder: Iterative Echo Server Client socket Server socket bind open_listenfd listen open_clientfd Client / Server Session Await connection request from next client connect Connection request accept rio_writen rio_readlineb rio_writen rio_readlineb close EOF rio_readlineb Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14 close Carnegie Mellon Iterative Servers  Iterative servers process one request at a time Client 1 connect write call read ret read close Server accept read write read close Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 15 Carnegie Mellon Iterative Servers  Iterative servers process one request at a time Client 1 connect write call read ret read close Server Client 2 connect write call read Wait for server to finish with Client 1 accept read write read close accept read write Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 16 ret read Carnegie Mellon Where Does Second Client Block?  Second client attempts to connect to iterative server  Call to connect returns  Even though connection not yet accepted  Server side TCP manager queues request  Feature known as “TCP listen backlog”  Call to rio_writen returns  Server side TCP manager buffers input data  Call to rio_readlineb blocks  Server hasn’t written anything for it to read yet. Client socket open_clientfd connect rio_writen rio_readlineb Connection request Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17 Carnegie Mellon Fundamental Flaw of Iterative Servers Client 1 connect write call read ret read User goes out to lunch Client 1 blocks waiting for user to type in data Server accept call read write call read Server blocks waiting for data from Client 1 Client 2 connect write call read Client 2 blocks waiting to read from server  Solution: use concurrent servers instead  Concurrent servers use multiple concurrent flows to serve multiple clients at the same time Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 18 Carnegie Mellon Approaches for Writing Concurrent Servers Allow server to handle multiple clients concurrently 1. Process-based  Kernel automatically interleaves multiple logical flows  Each flow has its own private address space 2. Event-based  Programmer manually interleaves multiple logical flows  All flows share the same address space  Uses technique called I/O multiplexing 3. Thread-based  Kernel automatically interleaves multiple logical flows  Each flow shares the same address space  Hybrid of of process-based and event-based Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 19 Carnegie Mellon Approaches for Writing Concurrent Servers Allow server to handle multiple clients concurrently 1. Process-based  Kernel automatically interleaves multiple logical flows  Each flow has its own private address space 2. Event-based  Programmer manually interleaves multiple logical flows  All flows share the same address space  Uses technique called I/O multiplexing 3. Thread-based  Kernel automatically interleaves multiple logical flows  Each flow shares the same address space  Hybrid of of process-based and event-based Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20 Carnegie Mellon Approach #1: Process-based Servers  Spawn separate process for each client client 1 call connect call fgets User goes out to lunch Client 1 blocks waiting for user to type in data child 1 call read Child blocks waiting for data from Client 1 server call accept ret accept fork call accept Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21 Carnegie Mellon Approach #1: Process-based Servers  Spawn separate process for each client client 1 call connect call fgets User goes out to lunch Client 1 blocks waiting for user to type in data server client 2 call connect child 1 call read Child blocks waiting for data from Client 1 call accept ret accept fork call accept ret accept fork call fgets write call read ret read close child 2 ... call read write close Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 22 Carnegie Mellon Iterative Echo Server Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23 int main(int argc, char **argv) { int listenfd, connfd; socklen_t clientlen; struct sockaddr_storage clientaddr; listenfd = Open_listenfd(argv[1]); while (1) { clientlen = sizeof(struct sockaddr_storage); connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen); echo(connfd); Close(connfd); } exit(0); } Accept a connection request Handle echo requests until client terminates echoserverp.c Carnegie Mellon Making a Concurrent Echo Server Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 24 int main(int argc, char **argv) { int listenfd, connfd; socklen_t clientlen; struct sockaddr_storage clientaddr; listenfd = Open_listenfd(argv[1]); while (1) { } } clientlen = sizeof(struct sockaddr_storage); connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen); echo(connfd); /* Child services client */ Close(connfd); /* child closes connection with client */ exit(0); echoserverp.c Carnegie Mellon Making a Concurrent Echo Server Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25 int main(int argc, char **argv) { int listenfd, connfd; socklen_t clientlen; struct sockaddr_storage clientaddr; Signal(SIGCHLD, sigchld_handler); listenfd = Open_listenfd(argv[1]); while (1) { clientlen = sizeof(struct sockaddr_storage); connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen); if (Fork() == 0) { Close(listenfd); /* Child closes its listening socket */ } } } echo(connfd); Close(connfd); exit(0); /* Child services client */ /* Child closes connection with client */ /* Child exits */ Close(connfd); /* Parent closes connected socket (important!) */ echoserverp.c Carnegie Mellon Making a Concurrent Echo Server Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 26 int main(int argc, char **argv) { int listenfd, connfd; socklen_t clientlen; struct sockaddr_storage clientaddr; Signal(SIGCHLD, sigchld_handler); listenfd = Open_listenfd(argv[1]); while (1) { clientlen = sizeof(struct sockaddr_storage); connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen); if (Fork() == 0) { Close(listenfd); /* Child closes its listening socket */ } } } echo(connfd); Close(connfd); exit(0); /* Child services client */ /* Child closes connection with client */ /* Child exits */ Close(connfd); /* Parent closes connected socket (important!) */ echoserverp.c Why? Carnegie Mellon Making a Concurrent Echo Server Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 27 int main(int argc, char **argv) { int listenfd, connfd; socklen_t clientlen; struct sockaddr_storage clientaddr; Signal(SIGCHLD, sigchld_handler); listenfd = Open_listenfd(argv[1]); while (1) { clientlen = sizeof(struct sockaddr_storage); connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen); if (Fork() == 0) { Close(listenfd); /* Child closes its listening socket */ } echo(connfd); Close(connfd); exit(0); /* Child services client */ /* Child closes connection with client */ /* Child exits */ Close(connfd); /* Parent closes connected socket (important!) */ } } echoserverp.c Carnegie Mellon Process-Based Concurrent Echo Server Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 28 int main(int argc, char **argv) { int listenfd, connfd; socklen_t clientlen; struct sockaddr_storage clientaddr; Signal(SIGCHLD, sigchld_handler); listenfd = Open_listenfd(argv[1]); while (1) { clientlen = sizeof(struct sockaddr_storage); connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen); if (Fork() == 0) { Close(listenfd); /* Child closes its listening socket */ } echo(connfd); Close(connfd); exit(0); /* Child services client */ /* Child closes connection with client */ /* Child exits */ Close(connfd); /* Parent closes connected socket (important!) */ } } echoserverp.c Carnegie Mellon Process-Based Concurrent Echo Server (cont) void sigchld_handler(int sig) { while (waitpid(-1, 0, WNOHANG) > 0)
;
return; }
echoserverp.c
 Reap all zombie children
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29

Carnegie Mellon
Concurrent Server: accept Illustrated
Client
clientfd
Connection request
Client
clientfd
listenfd(3)
Server
1. Server blocks in accept, waiting for connection request on listening descriptor listenfd
2. Client makes connection request by calling connect
3. Server returns connfd from accept. Forks child to handle client. Connection is now established between clientfd and connfd
listenfd(3)
Server
listenfd(3)
Server
Client
clientfd
connfd(4)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
30
Server Child

Carnegie Mellon
Process-based Server Execution Model
Connection requests
Listening server process
Client 1 server process
Client 1 data Client 2 data
 Each client handled by independent child process
 No shared state between them
 Both parent & child have copies of listenfd and connfd  Parent must close connfd
 Child should close listenfd
Client 2 server process
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31

Carnegie Mellon
Issues with Process-based Servers
 Listening server process must reap zombie children
 to avoid fatal memory leak
 Parent process must close its copy of connfd
 Kernel keeps reference count for each socket/open file
 After fork, refcnt(connfd) = 2
 Connection will not be closed until refcnt(connfd)
int main(int argc, char **argv) {
int listenfd, connfd;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
listenfd = Open_listenfd(argv[1]);
while (1) {
= 0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32
clientlen = sizeof(struct sockaddr_storage);
connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
if (Fork() == 0) {
}
echo(connfd);
Close(connfd);
exit(0);
/* Child services client */
/* Child closes connection with clien
/* Child exits */

Carnegie Mellon
Pros and Cons of Process-based Servers
 + Handle multiple connections concurrently
 + Clean sharing model  descriptors (no)
 file tables (yes)
 global variables (no)
 + Simple and straightforward
 – Additional overhead for process control
 – Nontrivial to share data between processes  (This example too simple to demonstrate)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
33

Carnegie Mellon
Approach #2: Event-based Servers  Server maintains set of active connections
 Array of connfd’s  Repeat:
 Determine which descriptors (connfd’s or listenfd) have pending inputs
 e.g., using select function
 arrival of pending input is an event
 If listenfd has input, then accept connection
 and add new connfd to array
 Service all connfd’s with pending inputs
 Details for select-based server in book Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
34

Carnegie Mellon
I/O Multiplexed Event Processing
Active Descriptors
Read and service Pending Inputs
listenfd = 3
connfd’s
listenfd = 3
connfd’s
10
7
4
-1
-1
12
5
-1
-1
-1
10
7
4
-1
-1
12
5
-1
-1
-1
0 1 2 3 4 5 6 7 8 9
Active
Inactive Active
Never Used
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
35
Anything happened?

Carnegie Mellon
Pros and Cons of Event-based Servers
 + One logical control flow and address space.
 + Can single-step with a debugger.
 + No process or thread control overhead.
 Design of choice for high-performance Web servers and search engines.
e.g., Node.js, nginx, Tornado
 – Significantly more complex to code than process- or thread- based designs.
 – Hard to provide fine-grained concurrency
 E.g., how to deal with partial HTTP request headers
 – Cannot take advantage of multi-core  Single thread of control
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
36

Carnegie Mellon
Quiz Time!
Check out:
https://canvas.cmu.edu/courses/13182
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
37

Carnegie Mellon
Approach #3: Thread-based Servers  Very similar to approach #1 (process-based)
 …but using threads instead of processes
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
38

Carnegie Mellon
Traditional View of a Process
 Process = process context + code, data, and stack
Process context
Code, data, and stack
SP
brk
PC
0
Stack
Shared libraries
Run-time heap
Read/write data
Read-only code/data
Program context:
Data registers Condition codes Stack pointer (SP) Program counter (PC)
Kernel context: VM structures
Descriptor table brk pointer
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
39

Carnegie Mellon
Alternate View of a Process
 Process = thread + code, data, and kernel context
Thread (main thread)
Code, data, and kernel context
brk
PC
0
Shared libraries
Run-time heap
Read/write data
Read-only code/data
SP
Stack
Thread context: Data registers
Condition codes Stack pointer (SP) Program counter (PC)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
40
Kernel context: VM structures
Descriptor table brk pointer

Carnegie Mellon
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)
Thread 1 (main thread) Thread 2 (peer thread)
stack 1 stack 2
Shared code and data
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
41
Thread 2 context: Data registers Condition codes SP2
PC2
0
Kernel context: VM structures
Descriptor table brk pointer

Carnegie Mellon
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
sh sh sh foo
bar
T2 T1
T4
shared code, data and kernel context
T5
T3
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42

Carnegie Mellon
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
43

Carnegie Mellon
Concurrent Thread Execution
 Single Core Processor  Simulate parallelism by
time slicing
Thread B
 Multi-Core Processor  Can have true
parallelism
Thread A Thread B Thread C
Thread A
Thread C
Time
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
44
Run 3 threads on 2 cores

Carnegie Mellon
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 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
 Process control (creating and reaping) 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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45

Carnegie Mellon
Threads vs. Signals
Receive
Icurr signal Handler
Inext
 Signal handler shares state with regular program  Including stack
 Signal handler interrupts normal program execution  Unexpected procedure call
 Returns to regular execution stream  Not a peer
 Limited forms of synchronization
 Main program can block / unblock signals
 Main program can pause for signal Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46

Carnegie Mellon
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()
 pthread_exit()
 exit() [terminates all threads] return [terminatescurrentthread]
 Synchronizing access to shared variables  pthread_mutex_init
 pthread_mutex_[un]lock
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47

Carnegie Mellon
The Pthreads “hello, world” Program
/*
* hello.c – Pthreads “hello, world” program
*/
#include “csapp.h”
void *thread(void *vargp);
int main(int argc, char** argv)
{
Thread ID
Thread routine
pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL);
Pthread_join(tid, NULL);
return 0;
}
hello.c
Thread attributes (usually NULL)
Thread arguments (void *p)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
Return value (void **p)
void *thread(void *vargp) /* thread routine */
{
printf(“Hello, world!\n”);
return NULL;
}
hello.c

Carnegie Mellon
Execution of Threaded “hello, world”
Main thread
call Pthread_create() Pthread_create()returns
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49

Carnegie Mellon
Or, …
Main thread
call Pthread_create() Pthread_create()returns
call Pthread_join()
Main thread doesn’t need to wait for peer thread to terminate
Pthread_join()returns
exit()
Terminates main thread and
any peer threads
Peer thread
printf()
return NULL;
Peer thread terminates
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
50
And many many more possible ways for this code to execute.

Carnegie Mellon
Thread-Based Concurrent Echo Server
int main(int argc, char **argv)
{
int listenfd, *connfdp;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
pthread_t tid;
listenfd = Open_listenfd(argv[1]);
while (1) {
clientlen=sizeof(struct sockaddr_storage);
connfdp = Malloc(sizeof(int));
*connfdp = Accept(listenfd, (SA *) &clientaddr, &clientlen);
Pthread_create(&tid, NULL, thread, connfdp);
}
return 0; echoservert.c }
 Spawn new thread for each client
 Pass it copy of connection file descriptor
 Note use of Malloc()! [but not Free()]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
51

Carnegie Mellon
Thread-Based Concurrent Server (cont)
/* Thread routine */
void *thread(void *vargp) {
int connfd = *((int *)vargp);
Pthread_detach(pthread_self());
Free(vargp);
echo(connfd);
Close(connfd);
return NULL;
}
echoservert.c
 Run thread in “detached” mode.
 Runs independently of other threads
 Reaped automatically (by kernel) when it terminates
 Free storage allocated to hold connfd  Close connfd (important!)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
52

Carnegie Mellon
Thread-based Server Execution Model
Connection requests
Client 1 data Client 2 data
Listening server main thread
Client 1 server
peer thread
Client 2 server peer thread
 Each client handled by individual peer thread
 Threads share all process state except TID
 Each thread has a separate stack for local variables
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53

Carnegie Mellon
Issues With Thread-Based Servers
 Must run “detached” to avoid memory leak
 At any point in time, a thread is either joinable or detached  Joinable thread can be reaped and killed by other threads
 must be reaped (with pthread_join) to free memory resources  Detached thread cannot be reaped or killed by other threads
 resources are automatically reaped on termination  Default state is joinable
 use pthread_detach(pthread_self()) to make detached
 Must be careful to avoid unintended sharing
 For example, passing pointer to main thread’s stack
 Pthread_create(&tid, NULL, thread, (void *)&connfd);
 All functions called by a thread must be thread-safe  (next lecture)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
54

Carnegie Mellon
Potential Form of Unintended Sharing
while (1) {
int connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
Pthread_create(&tid, NULL, thread, &connfd);
}
main thread
connfd = connfd1
connfd = connfd2
Main thread stack
connfd
peer1
Race!
peer2
connfd = *vargp
Peer1 stack
vargp
Peer2 stack
vargp
Why would both copies of vargp point to same location?
55
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
connfd = *vargp

Carnegie Mellon
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)
Thread 1 (main thread) Thread 2 (peer thread)
stack 1 stack 2
Shared code and data
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
56
Thread 2 context: Data registers Condition codes SP2
PC2
0
Kernel context: VM structures
Descriptor table brk pointer

But ALL memory is shared
Carnegie Mellon
Thread 1 context: Data registers Condition codes SP1
PC1
Thread 2 context: Data registers Condition codes SP2
PC2
Thread 1 (main thread) Thread 2 (peer thread)
stack 1 stack 2
shared libraries
run-time heap
read/write data
read-only code/data
0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
57
Kernel context: VM structures
Descriptor table brk pointer

Carnegie Mellon
while (1) {
int connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
Pthread_create(&tid, NULL, thread, &connfd);
}
Thread 1
Thread 2
shared libraries
run-time heap
read/write data
read-only code/data
&connfd
connfd
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
58
0
Kernel context: VM structures
Descriptor table brk pointer
Thread 2 context: Data registers Condition codes SP2
PC2
Thread 1 context: Data registers Condition codes SP1
PC1

Thread 1 context: Data registers Condition codes SP1
PC1
Carnegie Mellon
while (1) {
int connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
Pthread_create(&tid, NULL, thread, &connfd);
}
Thread 2 context: Data registers Condition codes SP2
PC2
Thread 3 context: Data registers Condition codes SP2
PC2
Thread 1
Thread 2 Thread 3
shared libraries
run-time heap
read/write data
read-only code/data
&connfd
&connfd
connfd
0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
59
Kernel context: VM structures
Descriptor table brk pointer

/* Thread routine */
void *thread(void *vargp) Thread 3 context:
Thread 1 context: Data registers Condition codes SP1
PC1
{
Data registers
int connfd = *((int *)vargp) Condition codes
SP2 PC2
Pthread_detach(pthread_self(
Free(vargp);
echo(connfd);
Close(connfd);
return NULL; Thread 3
shared libraries
Carnegie Mellon
Thread 1
Thread 2
}
&connfd
&connfd
connfd
run-time heap
read/write data
read-only code/data
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
Thread 2 context: Data registers Condition codes SP2
PC2
0
Kernel context: VM structures
Descriptor table brk pointer
0
; )

Carnegie Mellon
Could this race occur?
Main Thread
int i;
for (i = 0; i < 100; i++) { Pthread_create(&tid, NULL, thread, &i); } void *thread(void *vargp) { int i = *((int *)vargp); Pthread_detach(pthread_self()); save_value(i); return NULL; }  Race Test  If no race, then each thread would get different value of i  Set of saved values would consist of one copy each of 0 through 99 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 61 Carnegie Mellon Experimental Results No Race 2 1 0 3 2 1 0 Multicore server 14 12 10 8 6 4 2 0 0 2 4 6 8 101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698 Single core laptop 0 2 4 6 8 101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698  0 2 4 6 8 101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698 The race can really happen! Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 62 Carnegie Mellon Correct passing of thread arguments /* Main routine */ int *connfdp; connfdp = Malloc(sizeof(int)); *connfdp = Accept( . . . ); Pthread_create(&tid, NULL, thread, connfdp); /* Thread routine */ void *thread(void *vargp) { int connfd = *((int *)vargp); .. . Free(vargp); . .. return NULL; }  Producer-Consumer Model  Allocate in main  Free in thread routine Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 63 Carnegie Mellon Pros and Cons of Thread-Based Designs  + Easy to share data structures between threads  e.g., logging information, file cache  + Threads are more efficient than processes  – Unintentional sharing can introduce subtle and hard- to-reproduce errors!  The ease with which data can be shared is both the greatest strength and the greatest weakness of threads  Hard to know which data shared & which private  Hard to detect by testing  Probability of bad race outcome very low  But nonzero!  Future lectures Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 64 Carnegie Mellon Summary: Approaches to Concurrency  Process-based  Hard to share resources: Easy to avoid unintended sharing  High overhead in adding/removing clients  Event-based  Tedious and low level  Total control over scheduling  Very low overhead  Cannot create as fine grained a level of concurrency  Does not make use of multi-core  Thread-based  Easy to share resources: Perhaps too easy  Medium overhead  Not much control over scheduling policies  Difficult to debug  Event orderings not repeatable Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 65

Related Posts