Carnegie Mellon Concurrent Programming 15 213 Introduction to Computer Systems 22nd Lecture Nov 11 2010 Instructors Randy Bryant and Dave O Hallaron 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 2 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 15 213 3 Carnegie Mellon Iterative Echo Server Client Server socket socket bind open listenfd open clientfd listen Connection request connect Client Server Session accept rio writen rio readlineb rio readlineb close rio writen EOF Await connection request from next client rio readlineb close 4 Carnegie Mellon Iterative Servers Iterative servers process one request at a time client 1 server client 2 connect connect accept write call read ret read close read write call read write close accept Wait for Client 1 read write ret read 5 Carnegie Mellon Where Does Second Client Block Second client attempts to connect to iterative server Even though connection not yet accepted Server side TCP manager queues request Feature known as TCP listen backlog Client socket open clientfd rio writen rio readlineb Call to rio writen returns Server side TCP manager Connection request connect Call to connect returns buffers input data Call to rio readlineb blocks Server hasn t written anything for it to read yet 6 Carnegie Mellon Fundamental Flaw of Iterative Servers client 1 server client 2 connect accept write call read ret read User goes out to lunch Client 1 blocks waiting for user to type in data read write Server blocks waiting for data from Client 1 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 7 Carnegie Mellon Creating Concurrent Flows Allow server to handle multiple clients simultaneously 1 Processes Kernel automatically interleaves multiple logical flows Each flow has its own private address space 2 Threads Kernel automatically interleaves multiple logical flows Each flow shares the same address space 3 I O multiplexing with select Programmer manually interleaves multiple logical flows All flows share the same address space Relies on lower level system abstractions 8 Carnegie Mellon Concurrent Servers Multiple Processes Spawn separate process for each client client 1 server call accept call connect ret connect call fgets User goes out to lunch Client 1 blocks waiting for user to type in data client 2 call connect ret accept child 1 fork call accept call read ret accept fork child 2 call read ret connect call fgets write call read write close end read close 9 Carnegie Mellon Review Iterative Echo Server int main int argc char argv int listenfd connfd int port atoi argv 1 struct sockaddr in clientaddr int clientlen sizeof clientaddr listenfd Open listenfd port while 1 connfd Accept listenfd SA clientaddr clientlen echo connfd Close connfd exit 0 Accept a connection request Handle echo requests until client terminates 10 Carnegie Mellon Process Based Concurrent Server int main int argc char argv int listenfd connfd int port atoi argv 1 struct sockaddr in clientaddr int clientlen sizeof clientaddr Fork separate process for each client Does not allow any communication between different client handlers Signal SIGCHLD sigchld handler listenfd Open listenfd port while 1 connfd Accept listenfd SA clientaddr clientlen if Fork 0 Close listenfd Child closes its listening socket echo connfd Child services client Close connfd Child closes connection with client exit 0 Child exits Close connfd Parent closes connected socket important 11 Carnegie Mellon Process Based Concurrent Server cont void sigchld handler int sig while waitpid 1 0 WNOHANG 0 return Reap all zombie children 12 Carnegie Mellon Process Execution Model Connection Requests Listening Server Process Client 1 data Client 1 Server Process Client 2 Server Client 2 data Process Each client handled by independent process No shared state between them Both parent child have copies of listenfd and connfd Parent must close connfd Child must close listenfd 13 Carnegie Mellon Concurrent Server accept Illustrated listenfd 3 Client Server clientfd Connection request Client listenfd 3 Server 1 Server blocks in accept waiting for connection request on listening descriptor listenfd 2 Client makes connection request by calling and blocking in connect clientfd listenfd 3 Server Client clientfd Server Child connfd 4 3 Server returns connfd from accept Forks child to handle client Client returns from connect Connection is now established between clientfd and connfd 14 Carnegie Mellon Implementation Must dos With Process Based Designs Listening server process must reap zombie children to avoid fatal memory leak Listening server process must close its copy of connfd Kernel keeps reference for each socket open file After fork refcnt connfd 2 Connection will not be closed until refcnt connfd 0 15 Carnegie Mellon View from Server s TCP Manager Client 1 Client 2 Server srv echoserverp 15213 cl1 echoclient greatwhite ics cs cmu edu 15213 srv connected to 128 2 192 34 port 50437 cl2 echoclient greatwhite ics cs cmu edu 15213 srv connected to 128 2 205 225 port 41656 Connection Host Port Host Port Listening 128 2 220 10 15213 cl1 128 2 192 34 50437 128 2 220 10 15213 cl2 128 2 205 225 41656 128 2 220 10 15213 16 Carnegie Mellon View from Server s TCP Manager Connection Host Port Host Port Listening 128 2 220 10 15213 cl1 128 2 192 34 50437 128 2 220 10 15213 cl2 128 2 205 225 41656 128 2 220 10 15213 Port Demultiplexing TCP manager maintains separate stream for each connection Each represented to application program as socket New connections directed to listening socket Data from clients directed to one of the connection sockets 17 Carnegie Mellon Pros and Cons of Process Based Designs Handle multiple
View Full Document
Unlocking...