Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Carnegie Mellon15-213/18-243: Introduction to Computer SystemsInstructors: Bill Nace and Gregory Kesden(c) 1998 - 2010. All Rights Reserved. All work contained herein is copyrighted and used by permission of the authors. Contact [email protected] for permission or for more information.25th Lecture, 22 April 2010Programming for ConcurrencyCarnegie MellonTodayLimitations of iterative serversProcess-based concurrent serversThreads-based concurrent serversEvent-based concurrent serversCarnegie MellonConcurrent Programming is Hard!The human mind tends to be sequentialThe notion of time is often misleadingThinking about all possible sequences of events in a computer system is at least error prone and frequently impossibleClassical 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 gridlockLivelock / Starvation / Fairness: external events and/or system scheduling decisions can prevent sub-task progressExample: people always jump in front of you in lineMany aspects are beyond the scope of 15-213 / 18-243Carnegie MellonClient / ServerSessionEcho Server OperationClient Serversocket socketbindlistenrio_readlinebrio_writenrio_readlinebrio_writenConnectionrequestrio_readlinebcloseEOFAwait connectionrequest fromnext clientacceptconnectcloseopen_listenfdopen_clientfdCarnegie MellonIterative Serversclient 1 server client 2call connectcall acceptret connectret acceptcall connectcall writereadret writecloseclosecall acceptret connectcall writeret writeclosereadret acceptcloseCarnegie MellonFundamental Flaw of Iterative Serversclient 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 1Carnegie MellonConcurrent Servers: Multiple Processesclient 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...Carnegie MellonThree Basic Mechanisms for Creating Concurrent FlowsCarnegie MellonReview: 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);}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);}Carnegie MellonInner 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); }}void 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); }}Carnegie MellonEcho Server: accept Illustratedlistenfd(3)Client1. Server blocks in accept, waiting for connection request on listening descriptor listenfdclientfdServerlistenfd(3)ClientclientfdServer2. Client makes connection request by calling and blocking in connectConnectionrequestlistenfd(3)ClientclientfdServer3. Server returns connfd from accept. Client returns from connect. Connection is now established between clientfd and connfdconnfd(4)Carnegie MellonTodayLimitations of iterative serversProcess-based concurrent serversThreads-based concurrent serversEvent-based concurrent serversCarnegie Mellonint 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 = 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!) */ }}int 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 = 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!) */ }}Process-Based Concurrent ServerServer forks a separate process to deal with each clientNo communication between child processesCarnegie MellonProcess-Based Concurrent Server (cont’d)void sigchld_handler(int sig) { while (waitpid(-1, 0, WNOHANG) > 0) ; return;}void sigchld_handler(int sig) { while (waitpid(-1, 0, WNOHANG) > 0) ; return;}Carnegie MellonProcess Execution ModelEach client handled by independent processNo shared state between themWhen child created, each has copy of listenfd and connfdParent must close connfd, child must close listenfd Client 1 Server ProcessClient 1 Server ProcessListening ServerListening
View Full Document