编程辅导 CSE4100: System Programming

Sogang University
Concurrent Programming
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
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

Sogang University
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 allJ
§ We’ll cover some of these aspects in the next few lectures.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Iterative Servers
¢ Iterative servers process one request at a time
Wait for server to finish with Client 1
accept read
write read
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
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.
open_clientfd
rio_writen
rio_readlineb
Connection request
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Fundamental Flaw of Iterative Servers
User goes out to lunch
Client 1 blocks waiting for user to type in data
Server blocks waiting for data from Client 1
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

Sogang University
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

Sogang University
Approach #1: Process-based Servers ¢ Spawn separate process for each client
call connect
call fgets
User goes out to lunch
Client 1 blocks waiting for user to type in data
call connect
Child blocks
waiting for fork data from
call accept
ret accept
call accept
ret accept
call fgets
call … read
write close
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Process-Based Concurrent Echo Server
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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);
/* Child services client */
/* Child closes connection with client */ /* Child exits */
Close(connfd); /* Parent closes connected socket (important!) */ }
echoserverp.c

Sogang University
Process-Based Concurrent Echo Server (cont)
§ Reap all zombie children
void sigchld_handler(int sig) {
while (waitpid(-1, 0, WNOHANG) > 0) ;
echoserverp.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Concurrent Server: accept Illustrated
Connection request
listenfd(3)
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)
listenfd(3)
Server Child
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Process-based Server Execution Model
Connection requests
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
Listening server process
Client 1 server process
Client 2 server process
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
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) = 0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
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
§ Requires IPC (interprocess communication) mechanisms
§ FIFO’s (named pipes), System V shared memory and semaphores Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Concurrent Programming with I/O Multiplexing ¢ Why I/O Multiplexing?
§ Suppose you are asked to write an echo server that can respond to interactive commands that the user types to standard input in a single process
Event 1: a network client making a connection request
Event2: a user typing a command line at a keyboard
Echo Server
Which event do we wait for first?
Neither option is ideal…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Approach #2: Event-based Servers ¢ Server maintains set of active connections
§ Array of connfd’s
§ Determine which descriptors (connfd’s or listenfd) have pending inputs
§ e.g., using select or epoll functions
§ arrival of pending input is an event
§If listenfdhasinput,thenacceptconnection
§ and add new connfd to array
§ Service all connfd’s with pending inputs
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
I/O Multiplexed Event Processing
Active Descriptors
Read and service
Pending Inputs
listenfd = 3
listenfd = 3
0 1 2 3 4 5 6 7 8 9
Inactive Active
Never Used
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
I/O Multiplexed Event Processing ¢ I/O Multiplexing
§ Use the select or epoll functions to ask the kernel to suspend the process, returning control to the application only after one or more I/O events have occurred
§ Return when any descriptor in the set {0, 4} is ready for reading
§ Return when any descriptor in the set {1, 2, 7} is ready for writing.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
line 18: line 19-20:
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Due to a side effect from select which modifies the fd_set
pointed to by argument fdset to indicate a subset of the read set called
the ready set
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Issues with select.c ¢ Blocking problems
§ Once the server connects to a client, it continues echoing input lines until the client closes its end of the connection.
Thus, if a user types a command to standard input, he/she will not get a response until the server is finished with the client.
§ Thus, we need a way to multiplex at a finer granualarity, echoing (at most) one text line each time through the server loop!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
I/O Multiplexed Event Processing ¢ I/O multiplexing and event-driven programs
§ I/O multiplexing can be used as the basis for concurrent event- driven programs, where flows make progres as a result of certain events.
¢ Modeling logical flows as state machines
§ State machines is a collection of states, input events, and
transitions that map states and input events to states
¢ State machine for a logical flow in a concurrent event-
driven echo server
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
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

Sogang University
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

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

Sogang University
Alternate View of a Process
¢ Process = thread + code, data, and kernel context
Thread (main thread)
Code, data, and kernel context
Shared libraries
Run-time heap
Read/write data
Read-only code/data
Thread context: Data registers
Condition codes Stack pointer (SP) Program counter (PC)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Kernel context: VM structures
Descriptor 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 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
Sogang University
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
Thread 2 context: Data registers Condition codes SP2
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Kernel context: VM structures
Descriptor table brk pointer

Sogang University
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
sh sh sh foo
shared code, data and kernel context
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

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

Sogang University
Concurrent Thread Execution
¢ Single Core Processor
§ Simulate parallelism by time slicing
¢ Multi-Core Processor
§ Can have true parallelism
Thread A Thread B Thread C
Thread A Thread B Thread C
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Run 3 threads on 2 cores

Sogang University
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

Sogang University
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]
§ Synchronizing access to shared variables § pthread_mutex_init
§ pthread_mutex_[un]lock
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

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

Sogang University
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
Terminates main thread and
any peer threads
Peer thread
return NULL;
Peer thread terminates
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
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);
echoservert.c
§ malloc of connected descriptor necessary to avoid deadly race (later)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Sogang University
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

Sogang University
Thread-based Server Execution Model
Connection requests
Client 1 data Client 2 data
Client 1 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
Listening server main thread
Client 2 server peer thread

Sogang University
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

Sogang University
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

Sogang University
Summary: Approaches to Concurrency
¢ Process-based
§ Hard to share resources: Easy to avoid unintended sharing § High overhead in adding/removing

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com