Lecture notes for CSC 252, Tues. Apr. 24, 2007ff Announcements A7 due Friday noon, Fri. May 4 Final exam Sat. May 12, 8:30am, this room Skim chapter 12-13 ============================== Concurrency processes and threads kernel-level and user-level threads blocking kernel calls shared memory v. message passing In Linux processes share memory via mmap or shm library routines threads get shared memory by default (actually difficult to get transparent separate copies) processes send messages over sockets, both within and across machines Take networks course (257) to learn (much) more about sockets. Take operating systems (256) to learn more about threads. Take languages (254) to learn about linguistic support. Take parallel & distributed systems (258) to learn more about algorithmic issues for all of the above. ------------------ Two main uses for threads/processes conceptual structuring e.g. web browser (or server) parallelism e.g. web server ================== create processes with fork() and execve() have to create shared memory explicitly with mmap or shmem create (Posix) threads with pthread_create global memory is automatically shared #include ... int pthread_create(pthread_t * thread, pthread_attr_t * attr, void * (*start_routine)(void *), void * arg); Returns 0 on success, various non-zero values on error. Stores id of new thread at location specified by first arg. Runs start_routine, passing arg. pthread_attr_t has fields to control various things: whether thread is "joinable" or "detached" scheduling policy (normal, RR real-time, FIFO real-time) scheduling priority whether these last two are new or inherited from parent (ignored) system or process-level scheduling "scope" (Linux supports only the former) where to put the stack some non-standard extensions (notably Solaris LWP) support additional parameters. if thread is joinable, join up with pthread_join(pthread_t thread, void ** thread_return) thread's return value (of type void *) is stored in specified location ================== synchronization SYNCHRONIZATION is the act of ensuring that events in different processes happen in a desired order. Synchronization can be used to eliminate bad race conditions, e.g. to enforce MUTUAL EXCLUSION or CONDITION SYNCHRONIZATION. Also classify synchronization mechanisms as busy-wait (spinning) v. scheduler-based. I'll focus on the latter; the former is a bad idea on a uniprocessor. Also note that synchronization between event handlers and main program requires masking on the part of the main program, since the handler can neither spin nor be descheduled. Example: bounded buffer. Used, e.g., for pipes or server tasks queues. shared buf : array [1..SIZE] of data shared next_full, next_empty : integer = 1 procedure insert (d : data) : put something into the buffer, waiting if it's full procedure remove returns data : take something out of the buffer, waiting if it's empty A solution requires (1) that only one process manipulate the buffer (or at least any given slot of the buffer) at a time. (2) that processes wait for non-full or non-empty conditions as appropriate. (1) is mutual exclusion; (2) is condition synchronization. You might be tempted to think of mutual exclusion as a form of condition synchronization (the condition being that nobody else is in the critical section), but it isn't. The distinction is basically existential v. universal quantification. Mutual exclusion requires multi-process consensus. We do NOT in general want to over-synchronize. That eliminates parallelism, which we generally want to encourage for performance. Basically, we want to eliminate "bad" race conditions -- the ones that cause the program to give incorrect results. ------------------ semaphores A semaphore is a special counter. It has an initial value and two operations, P and V, for changing that value. (P and V are initials for words in Dutch; think of them as Pause and something else [Voice maybe?]). A semaphore keeps track of the difference between the number of P and V operations that have occurred. A P operation is delayed (the process is de-scheduled) until #P-#V <= C, the initial value of the semaphore. Unix provides semaphores: #include int sem_init(sem_t *sem, 0, unsigned int value); second arg is non-zero for semaphores shared among threads from different processes, which Linux does not yet support int sem_wait(sem_t *s); // P(s) int sem_post(sem_t *s); // V(s) return 0 if OK; -1 on error What can we do with semaphores? Here is a bounded buffer: shared buf : array [1..SIZE] of data shared next_full, next_empty : integer = 1 shared mutex : semaphore = 1 shared empty_slots, full_slots : semaphore = SIZE, 0 procedure insert (d : data) : P (empty_slots) P (mutex) buf[next_empty] = d next_empty = next_empty mod SIZE + 1 V (mutex) V (full_slots) function remove returns data : P (full_slots) P (mutex) d : data = buf[next_full] next_full = next_full mod SIZE + 1 V (mutex) V (empty_slots) return d It is generally assumed that semaphores are fair, in the sense that processes complete P operations in the same order they start them. Pthreads also provide binary semaphores: #include ... int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr); // attr controls handling of priority and whether multiple // invocations by the same thread are ok, error, or uncaught int pthread_mutex_lock(pthread_mutex_t *mutex); int pthread_mutex_unlock(pthread_mutex_t *mutex); int pthread_mutex_destroy(pthread_mutex_t *mutex); As well as "condition variables", which are like memory-less semaphores (as used in monitors, for those who've had 254): #include ... int pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr); // attr controls whether condition can be shared with threads in // other processes int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); int pthread_cond_timedwait(pthread_cond_t *cond, pthread_mutex_t *mutex, const struct timespec *abstime); // Mutex must alread be held when these last two are called. // Is also held when call returns, but is released in-between. // Purpose: make waiting and checking a condition atomic. int pthread_cond_signal(pthread_cond_t *cond); int pthread_cond_bradcast(pthread_cond_t *cond); // These two are no-ops if no threads are waiting. // They should be called while holding the mutex used by waiters. normal idiom: pthread_mutex_lock(...) while (! condition) { pthread_cond_wait(...) } pthread_mutex_unlock(...) Exist lots of other synchronization mechanisms, e.g. monitors, Java synchronized methods, conditional critical regions, event counts & synchronizers, etc. Many of these are best with language support. ------------------ Barriers common in data-parallel programs separate algorithm phases easy to build given locks: class barrier { int participants; int parity; // for sense reversal pthread_mutex_t mutex; int count[2]; pthread_cond_t sem[2]; public: void wait() { VERIFY(pthread_mutex_lock(&mutex)); int my_parity = parity; ++count[my_parity]; if (count[my_parity] == participants) { // I was the last to arrive count[my_parity] = 0; parity = 1 - my_parity; VERIFY(pthread_cond_broadcast(&sem[my_parity])); } else { while (!count[my_parity] == 0) { VERIFY(pthread_cond_wait(&sem[my_parity], &mutex)); } } VERIFY(pthread_mutex_unlock(&mutex)); } barrier(int n) : participants(n) { count[0] = count[1] = 0; parity = 0; VERIFY(pthread_mutex_init(&mutex, 0)); VERIFY(pthread_cond_init(&sem[0], 0)); VERIFY(pthread_cond_init(&sem[1], 0)); } ~barrier() { VERIFY(pthread_mutex_destroy(&mutex)); VERIFY(pthread_cond_destroy(&sem[0])); VERIFY(pthread_cond_destroy(&sem[1])); } }; Parity serves to distinguish between threads that have not yet left the current barrier and threads that have just arrived at the next one. Without it the while loop wouldn't work right. ------------------ How a scheduler works (take 254 and 258 for more) ready list synchronization lists preemption ============================== Client-server programming IP, (UDP), TCP data on the wire is big-endian ("network byte order") TCP connections bidirectional socket address at each end typically client port is "ephemeral", assigned arbitrarily by kernel server port is "well known" C interface is messy. Book introduces wrapper functions to simplify it somewhat, but these are non-standard. Java has standard wrappers, which are a good bit nicer. I'll use these to illustrate the concepts. Server "listens" on a well-known port: ServerSocket myServerSocket = new ServerSocket(portID); Socket clientConnection = myServerSocket.accept(); // Blocks until server receives a connection request from a // client. Typically server will fork a thread to talk to the // client, and then go back to listening for other clients. Client sends request for connection via Socket constructor: Socket serverConnection = new Socket(hostName, portID); // hostName is a string; portID is an integer Once server and client are connected, they typically create streams to talk through: Buffered Reader in = new InputStreamReader(clientConnection.getInputStream()); PrintStream out = new PrintStream(clientConnection.getOutputStream()); // client would make similar calls using serverConnection ... String s = in.readLine(); ... out.println("Hi, Mom\n"); ============================== Multiprocessors v. multithreaded machines cache coherence the cache coherence problem snooping MESI protocol state see do goto --------------------------------------------------------- invalid PrRd BusRd(S) shared BusRd(NS) exclusive PrWr BusRdX modified shared PrRd -- -- PrWr BusRdX modified BusRd flush? -- BusRdX flush? invalid exclusive (clean) PrRd -- -- PrWr -- modified BusRd flush shared BusRdX flush invalid modified (dirty) PrRd -- -- PrWr -- -- BusRd flush shared BusRdX flush invalid flush?: provide data only if machine supports cache-to-cache transfers (need arbitration to discern if it's my responsibility) _ / \ read hit v | invalid <--bus write-once-- shared <--read miss-- ^ < > ^ | | \ / | | | bus \ / bus | | | write \ / read | | | miss \ / miss | | | / \ | | | / \ | | write | / \ | | hit | / \ | v write miss--> modified <---write hit--- exclusive | ^ \_/ write hit note existence of directory-based coherence protocols