Concurrent Programming November 28, 2007Concurrent Programming is Hard!Echo Server OperationIterative ServersFundamental Flaw of Iterative ServersConcurrent Servers: Multiple ProcessesThree Basic Mechanisms for Creating Concurrent FlowsReview: Sequential ServerInner Echo LoopEcho Server: accept IllustratedProcess-Based Concurrent ServerProcess-Based Concurrent Server (cont)Process Execution ModelImplementation Issues With Process-Based DesignsPros and Cons of Process-Based DesignsTraditional View of a ProcessAlternate View of a ProcessA Process With Multiple ThreadsLogical View of ThreadsConcurrent Thread ExecutionThreads vs. ProcessesPosix Threads (Pthreads) InterfaceThe Pthreads "hello, world" ProgramExecution of Threaded“hello, world”Thread-Based Concurrent Echo ServerThread-Based Concurrent Server (cont)Slide 27Potential Form of Unintended SharingIssues With Thread-Based ServersPros and Cons of Thread-Based DesignsEvent-Based Concurrent Servers Using I/O MultiplexingThe select FunctionMacros for Manipulating Set DescriptorsOverall StructureRepresenting Pool of ClientsPool ExampleMain LoopPool InitializationInitial PoolAdding ClientAdding Client with fd 11Checking ClientsConcurrency LimitationsPro and Cons of Event-Based DesignsApproaches to ConcurrencyConcurrent ProgrammingNovember 28, 2007Concurrent ProgrammingNovember 28, 2007TopicsTopicsLimitations of iterative serversProcess-based concurrent serversEvent-based concurrent serversThreads-based concurrent servers15-213class25.ppt15-213, F’07– 2 –15-213, F’07Concurrent Programming is Hard!Concurrent Programming is Hard!The human mind tends to be sequentialThe human mind tends to be sequentialThe notion of time is often misleadingThe notion of time is often misleadingThinking about all possible sequences of events in a computer Thinking about all possible sequences of events in a computer system is at least error prone and frequently impossiblesystem is at least error prone and frequently impossibleClassical problem classes of concurrent programs:Classical problem classes of concurrent programs:Races: outcome depends on arbitrary scheduling decisions elsewhere in the systemExample: who gets the last seat on the airplane?Deadlock: improper resource allocation prevents forward progressExample: traffic gridlockLifelock / Starvation / Fairness: external events and/or system scheduling decisions can prevent sub-task progressExample: people always jump in front of you in lineMany aspects of concurrent programming are beyond the scope Many aspects of concurrent programming are beyond the scope of 15-213of 15-213– 3 –15-213, F’07Client / ServerSessionEcho Server OperationEcho Server OperationClientServersocket socketbindlistenrio_readlinebrio_writenrio_readlinebrio_writenConnectionrequestrio_readlinebclosecloseEOFAwait connectionrequest fromnext clientopen_listenfdopen_clientfdacceptconnect– 4 –15-213, F’07Iterative ServersIterative ServersIterative servers process one request at a time.Iterative servers process one request at a time.client 1 server client 2call connectcall acceptret connectret acceptcall connectcall writereadret writecloseclosecall acceptret connectcall writeret writeclosereadret acceptclose– 5 –15-213, F’07Fundamental Flaw of Iterative ServersFundamental Flaw of Iterative ServersSolution: use Solution: use concurrent servers concurrent servers instead.instead.Concurrent servers use multiple concurrent flows to serve multiple clients at the same time.client 1 server client 2call connectcall acceptcall readret connectret acceptcall connectcall fgetsUser goesout to lunchClient 1 blockswaiting for userto type in dataClient 2 blockswaiting to completeits connection request until afterlunch!Server blockswaiting fordata fromClient 1– 6 –15-213, F’07Concurrent Servers:Multiple ProcessesConcurrent Servers:Multiple ProcessesConcurrent servers handle multiple requests concurrently.Concurrent servers handle multiple requests concurrently.client 1 server client 2call connectcall acceptcall readret connectret acceptcall connectcall fgetsforkchild 1User goesout to lunchClient 1 blockswaiting for user to type in datacall acceptret connectret acceptcall fgetswriteforkcall readchild 2writecall readend readcloseclose...– 7 –15-213, F’07Three Basic Mechanisms for Creating Concurrent FlowsThree Basic Mechanisms for Creating Concurrent Flows1. Processes1. ProcessesKernel automatically interleaves multiple logical flows.Each flow has its own private address space.2. Threads2. ThreadsKernel automatically interleaves multiple logical flows.Each flow shares the same address space.3. I/O multiplexing with 3. I/O multiplexing with select()select()User manually interleaves multiple logical flows.Each flow shares the same address space.Popular for high-performance server designs.– 8 –15-213, F’07Review: Sequential ServerReview: Sequential Serverint 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 requestHandle echo requests until client terminates– 9 –15-213, F’07Inner Echo LoopInner Echo Loopvoid echo(int connfd) { size_t n; char buf[MAXLINE]; rio_t rio; Rio_readinitb(&rio, connfd); while((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) {printf("server received %d bytes\n", n);Rio_writen(connfd, buf, n); }}Server reads lines of textEchos them right back– 10 –15-213, F’07Echo Server: accept IllustratedEcho Server: accept Illustratedlistenfd(3)Client1. Server blocks in accept, waiting for connection request on listening descriptor listenfd.clientfdServerlistenfd(3)ClientclientfdServer2. Client makes connection request by calling and blocking in connect.Connectionrequestlistenfd(3)ClientclientfdServer3. Server returns connfd from accept. Client returns from connect. Connection is now established between clientfd and connfd.connfd(4)– 11 –15-213, F’07int main(int argc, char **argv) { int listenfd, connfd; int port = atoi(argv[1]); struct sockaddr_in clientaddr; int clientlen=sizeof(clientaddr); Signal(SIGCHLD, sigchld_handler); listenfd = Open_listenfd(port); while (1) {connfd =
View Full Document