Concurrent Programming November 18, 2008Three Basic Mechanisms for Creating Concurrent FlowsAppr. #3: Event-Based Concurrent Servers Using I/O MultiplexingThe select FunctionMacros for Manipulating Set DescriptorsOverall StructureRepresenting Pool of ClientsPool ExampleMain LoopPool InitializationInitial PoolSlide 12Adding ClientAdding Client with fd 11Checking ClientsConcurrency LimitationsPro and Cons of Event-Based DesignsA Process With Multiple ThreadsPros and Cons of Thread-Based DesignsShared Variables in Threaded C ProgramsThreads Memory ModelExample of Threads Accessing Another Thread’s StackMapping Variables to Mem. InstancesShared Variable Analysisbadcnt.c: An Improperly Synchronized Threaded ProgramAssembly Code for Counter LoopConcurrent ExecutionConcurrent Execution (cont)Slide 29Progress GraphsTrajectories in Progress GraphsCritical Sections and Unsafe RegionsSafe and Unsafe TrajectoriesSemaphoresSafe Sharing with SemaphoresSafe Sharing With SemaphoresConcurrent ProgrammingNovember 18, 2008Concurrent ProgrammingNovember 18, 2008TopicsTopicsEvent-based concurrent serversShared variablesThe need for synchronizationSynchronizing with semaphores15-213“The course that gives CMU its Zip!”lecture-23.ppt– 2 –15-213, F’08Three Basic Mechanisms for Creating Concurrent FlowsThree Basic Mechanisms for Creating Concurrent Flows1. Processes1. ProcessesKernel automatically interleaves multiple logical flowsEach flow has its own private address space2. Threads2. ThreadsKernel automatically interleaves multiple logical flowsEach flow shares the same address space3. I/O multiplexing with 3. I/O multiplexing with select()select()Programmer manually interleaves multiple logical flowsAll flows share the same address spacePopular for high-performance server designs– 3 –15-213, F’08Appr. #3: Event-Based Concurrent Servers Using I/O MultiplexingAppr. #3: Event-Based Concurrent Servers Using I/O MultiplexingMaintain a pool of connected descriptorsMaintain a pool of connected descriptorsRepeat the following forever:Repeat the following forever:Use the Unix select function to block until:(a) New connection request arrives on the listening descriptor(b) New data arrives on an existing connected descriptorIf (a), add the new connection to the pool of connectionsIf (b), read any available data from the connectionClose connection on EOF and remove it from the pool– 4 –15-213, F’08The select FunctionThe select Functionselect()select() sleeps until one or more file descriptors in the set sleeps until one or more file descriptors in the set readset readset are ready for readingare ready for reading#include <sys/select.h>int select(int maxfdp1, fd_set *readset, NULL, NULL, NULL);readset• Opaque bit vector (max FD_SETSIZE bits) that indicates membership in a descriptor set• If bit k is 1, then descriptor k is a member of the descriptor setmaxfdp1• Maximum descriptor in descriptor set plus 1• Tests descriptors 0, 1, 2, ..., maxfdp1 - 1 for set membershipselect()select() returns the number of ready descriptors and sets each bit of returns the number of ready descriptors and sets each bit of readsetreadset to indicate the ready status of its corresponding descriptor to indicate the ready status of its corresponding descriptor– 5 –15-213, F’08Macros for Manipulating Set DescriptorsMacros for Manipulating Set Descriptorsvoid FD_ZERO(fd_set *fdset);void FD_ZERO(fd_set *fdset);Turn off all bits in fdsetvoid FD_SET(int fd, fd_set *fdset);void FD_SET(int fd, fd_set *fdset);Turn on bit fd in fdsetvoid FD_CLR(int fd, fd_set *fdset);void FD_CLR(int fd, fd_set *fdset);Turn off bit fd in fdsetint FD_ISSET(int fd, *fdset);int FD_ISSET(int fd, *fdset);Is bit fd in fdset turned on?– 6 –15-213, F’08Overall StructureOverall Structurelistenfd10clientfd74-1-1125-1-1-10123456789• • •ActiveInactiveActiveNever UsedManage Pool of ConnectionsManage Pool of Connectionslistenfd: Listen for requests from new clientsActive clients: Ones with a valid connectionUse select to detect activityUse select to detect activityNew request on listenfdRequest by active clientRequired ActivitiesRequired ActivitiesAdding new clientsRemoving terminated clientsEchoing– 7 –15-213, F’08Representing Pool of ClientsRepresenting Pool of Clients/* * echoservers.c - A concurrent echo server based on select */ #include "csapp.h" typedef struct { /* represents a pool of connected descriptors */ int maxfd; /* largest descriptor in read_set */ fd_set read_set; /* set of all active descriptors */ fd_set ready_set; /* subset of descriptors ready for reading */ int nready; /* number of ready descriptors from select */ int maxi; /* highwater index into client array */ int clientfd[FD_SETSIZE]; /* set of active descriptors */ rio_t clientrio[FD_SETSIZE]; /* set of active read buffers */ } pool; int byte_cnt = 0; /* counts total bytes received by server */– 8 –15-213, F’08Pool ExamplePool Examplemaxfd = 12 maxi = 6read_set = { 3, 4, 5, 7, 10, 12 }10clientfd74-1-1125-1-1-10123456789• • •ActiveInactiveActiveNever Usedlistenfd = 3– 9 –15-213, F’08Main LoopMain Loopint main(int argc, char **argv) { int listenfd, connfd, clientlen = sizeof(struct sockaddr_in); struct sockaddr_in clientaddr; static pool pool; listenfd = Open_listenfd(argv[1]); init_pool(listenfd, &pool); while (1) { pool.ready_set = pool.read_set; pool.nready = Select(pool.maxfd+1, &pool.ready_set, NULL, NULL, NULL); if (FD_ISSET(listenfd, &pool.ready_set)) { connfd = Accept(listenfd, (SA *)&clientaddr,&clientlen); add_client(connfd, &pool); } check_clients(&pool); } }– 10 –15-213, F’08Pool InitializationPool Initialization/* initialize the descriptor pool */void init_pool(int listenfd, pool *p) { /* Initially, there are no connected descriptors */ int i; p->maxi = -1; for (i=0; i< FD_SETSIZE; i++) p->clientfd[i] = -1; /* Initially, listenfd is only member of select read set */ p->maxfd = listenfd; FD_ZERO(&p->read_set); FD_SET(listenfd, &p->read_set); }– 11 –15-213, F’08Initial PoolInitial Poolmaxfd = 3 maxi = -1read_set = { 3 }-1clientfd-1-1-1-1-1-1-1-1-10123456789•
View Full Document