cs357 Lecture Notes Spring 2000 Week 6, Tuesday For today you should have finished homework 3 and finished reading Chapter 4. For next time you should pick up homework 4, compile and run the code, print documentation, and do the first experiment. Also, read the handout about threads! Topics for today ---------------- 1) Threads! 2) Maybe some C. Interprocess communication -------------------------- Two fundamental mechanisms: 1) Explicit message-passing, like sockets. 2) Shared state a) Parent and child share a file system. One can read what the other rights. b) A generalization of that idea is that two processes can share some part of their process state. Such processes are called threads! Look at the definition of process state and see what part can be shared between processes/threads and which parts have to be "private" (i.e. every thread gets its own version). Threads ------- The fundamental state of a thread is the program counter, which indicates where in the thread of execution we are. Also, the hardware state of a thread has to be private, since otherwise one thread would mangle another's variables (although you could imagine a system in which the registers are divided up among the threads). Finally, if we want to allow threads to execute procedures, we have to give them private stacks. Everything else -- the text segment, the static variables, and the heap -- can be shared! Remember that all these segments together are called a process's "address space". Threads are said to share an address space, or run in the same address space. OS Classification ----------------- You could classify an OS according to the number of address spaces it provides, and the number of threads that can run in each address space. One address space, one thread Old versions of MacOS and DOS Many address spaces (processes), but only one thread per Old versions of UNIX One address space, but many threads Some dedicated systems, including the Lego robots! Many address spaces, many threads per (in the old days) VMS, Mach (now) most modern OS Historically, as operating systems added threads, they did it in ad hoc, non-standard ways. Now, there is a standard interface, called POSIX threads, or pthreads, that is implemented in many (most?) UNIX environments, inlcuding Linux. And we're gonna use it. Good things about threads 1) easy inter process communication (inter thread?) 2) natural expression of real time behavior a) GUI in one thread, actions create new threads particularly important when duration of tasks is unpredictable, as in network-land (web browser) b) real-time event-handling with priorities c) concurrent garbage collection 3) accurate representation of dependencies sequential programs tend to enforce stronger sync than necessary exposes parallelism for hardware that can use it Bad things about threads 1) no memory protection between threads -- one bad thread brings the whole thing down (example: multiple browser windows, two threads or two processes) 2) non-deterministic behavior -- hard to prove correctness, hard to replicate and find bugs 3) tricky to handle syncronization correctly Synchronization --------------- This does not mean that the concurrent threads agree about what time it is; it means they work together in an organized way. In general, if two threads are concurrent, we cannot make any statements about the relative ordering of statements. In reality, we know that threads tend to run for many instructions per quantum, but we cannot count on that. In order to consider all possibilities, we imagine that any thread can be interrupted at any point. This leads to non-deterministic behavior; i.e. we cannot know by looking at the program what the program will do. It depends on: 1) decisions made by the scheduler at run time 2) the timing of interrupts, which are usually generated off chip by processes that are independent of the running program (like the user pressing a key) Casually, we might say that these effects are "random", but in fact there are characteristics of these processes that have real effects on programs and that make pure random models unrealistic. Example 1: writer vs. writer Assume that in the initial state there is a shared variable x = 1. Two concurrent threads write a new value... Thread 1 Thread 2 -------- -------- x = 2 x = 3 And then one of them prints the value. Since we don't know the order the statements execute, we don't know which value "sticks". Example 2: reader vs. writer Again, the initial state has x = 1 Thread 1 Thread 2 -------- -------- x = 2 y = x We don't know whether y will get the old or the new value of x. Example 3: read/write vs. read/write Again, the initial state has x = 1 Thread 1 Thread 2 -------- -------- x++ x++ It seems like it doesn't matter what order these happen in; either way, x gets incremented twice. But it turns out that when this code gets compiled, it looks more like: Thread 1 Thread 2 -------- -------- t1 <- x t2 <- x t1 <- t1 + 1 t2 <- t2 +1 x <- t1 x <- t1 Now it is not clear whether x will get incremented once or twice! This example show that in order to understand syncronization, we have to understand which operations are atomic, and which are subject to interruption. If the hardware provides an instruction that increments the value of a memory location, as the VAX did, then it is usually not possible to interrupt in the middle. If the hardware is a register machine that has to load, modify and store, then it usually is possible. But if the compiler had made x a register variable, then it would not be possible!!! Here's another unpleasant hardware evilness. Reading and writing a word is atomic, but on some machines reading or writing a double is not! Thread 1 Thread 2 -------- -------- x = -1.0 x = 2.0 It is possible for this code to result in x = -2.0! Assignment 4, experiment 1 -------------------------- How do all these stacks get packed into an address space? How can we find out? Assignment 4, experiment 2 -------------------------- The race is on! Thread 1 Thread 2 -------- -------- i = n pthread_create while (i < 2n) while (i > 0) i++ i-- print "parent wins!" print "child wins!"