15 213 Concurrent Programming November 18 2009 Topics Class23 ppt Limitations of iterative servers Process based concurrent servers Event based concurrent servers Threads based concurrent servers Concurrent Programming is Hard z The human mind tends to be sequential z The notion of time is often misleading z Thinking about all possible sequences of events in a computer system is at least error prone and frequently impossible z Classical problem classes of concurrent programs Races outcome depends on arbitrary scheduling decisions elsewhere in the system z Example who gets the last seat on the airplane Deadlock improper resource allocation prevents forward progress z Example traffic gridlock Lifelock Starvation Fairness external events and or system scheduling decisions can prevent sub task progress z Example people always jump in front of you in line z Many aspects of concurrent programming are beyond the scope of 15 213 2 15 213 F 09 Echo Server Operation Client Server socket socket bind open listenfd open clientfd listen connect Client Server Session rio writen accept rio readlineb rio readlineb close 3 Connection request rio writen EOF Await connection request from next client rio readlineb close 15 213 F 09 Iterative Servers Iterative servers process one request at a time client 1 server call connect call accept client 2 call connect ret connect ret accept read call write ret write close close call accept ret accept ret connect call write read ret write close close 4 15 213 F 09 Fundamental Flaw of Iterative Servers client 1 server client 2 call accept call connect ret connect ret accept call fgets User goes out to lunch Server blocks waiting for data from Client 1 call read Client 1 blocks waiting for user to type in data call connect Client 2 blocks waiting to complete its connection request until after lunch Solution use concurrent servers instead Concurrent servers use multiple concurrent flows to serve multiple clients at the same time 5 15 213 F 09 Concurrent Servers Multiple Processes Concurrent servers handle multiple requests concurrently client 1 server client 2 call accept call connect call connect ret connect ret accept call fgets User goes out to lunch Client 1 blocks waiting for user to type in data fork child 1 call accept call read ret accept fork child 2 call read ret connect call fgets write call read write close end read close 6 15 213 F 09 Three Basic Mechanisms for Creating Concurrent Flows 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 User manually interleaves multiple logical flows Each flow shares the same address space Popular for high performance server designs 7 15 213 F 09 Review Sequential 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 8 15 213 F 09 Inner Echo Loop 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 Server reads lines of text Echos them right back 9 15 213 F 09 Echo Server accept Illustrated listenfd 3 Server Client clientfd Connection request Client listenfd 3 Server clientfd listenfd 3 Client clientfd 1 Server blocks in accept waiting for connection request on listening descriptor listenfd Server connfd 4 2 Client makes connection request by calling and blocking in connect 3 Server returns connfd from accept Client returns from connect Connection is now established between clientfd and connfd 10 15 213 F 09 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 15 213 F 09 Process Based Concurrent Server cont void sigchld handler int sig while waitpid 1 0 WNOHANG 0 return Reap all zombie children 12 15 213 F 09 Process Execution Model Connection Requests Listening Server Client 1 data Client 1 Server Client 2 Client 2 data Server Each client handled by independent process No shared state between them When child created each have copies of listenfd and connfd z Parent must close connfd child must close listenfd 13 15 213 F 09 Implementation Issues With Process Based Designs Server must reap zombie children to avoid fatal memory leak Server must close its copy of connfd Kernel keeps reference for each socket After fork refcnt connfd 2 Connection will not be closed until refcnt connfd 0 14 15 213 F 09 Pros and Cons of Process Based Designs Handles 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 15 15 213 F 09 Traditional View of a Process Process process context code data and stack Process context Program context Data registers Condition codes Stack pointer SP Program counter PC Code data and stack stack SP shared libraries brk run time heap read write data Kernel context VM structures Descriptor table brk pointer PC read only code data 0 16 15 213 F 09 Alternate View of a Process Process thread code data and kernel context Thread main thread Code and Data shared libraries SP stack brk run time heap read write data Thread context Data registers Condition codes Stack pointer SP Program counter PC PC read only code data 0 Kernel context VM structures Descriptor table brk pointer 17 15 213 F 09 A Process With Multiple Threads Multiple threads can be associated with a process Each thread has its own logical control flow Each
View Full Document
Unlocking...