Notes for CSC 456, Wednesday 19 January 2000 ff Reading assignment: chapters 4 and 6 Unit on processes and scheduling (1st of 4 main units; others are memory management, disks and I/O, and networking/distributed systems) Top-level outline: review of basic process implementation busy-wait synchronization context switching scheduler-based synchronization lock-free synchronization scheduling policies deadlock (if time permits) Some of this will be review of 2/454 material. I'll go over that part fairly rapidly, and concentrate on the new stuff. ============================================================= BUSY-WAIT SYNCHRONIZATION Synchronization means constraining the order in which things can happen in different processes. The purpose of synchronization is to eliminate bad RACE CONDITIONS. A race condition is when it makes a noticeable difference whether events in different processes happen in a particular order, but we haven't required them to. (Each process is 'racing' to get to its event; one of them wins and we can't predict which in advance.) Most synchronization is either MUTUAL EXCLUSION or CONDITION SYNCHRONIZATION. Mutual exclusion ensures atomicity of critical sections. It requires N-process agreement ("consensus") on who is in the code. Condition synchronization ensures that a desired condition has occurred; it's easier. Recall bounded buffer example from 2/454. Synchronization mechanisms are also classified into BUSY-WAIT and SCHEDULER-BASED implementations. The former chew up processor cycles polling for the occurrence of the event. The latter give the processor to a different process in the interim. Busy-wait synchronization makes sense only on a multiprocessor. It's the better choice when you don't have anything else to do with the current processor or when the expected time you'll have to wait is less than the time required to switch to a different process and back. I'll talk about busy-wait synchronization first. Scheduler-based mechanisms will wait until I talk about the implementation of (multiprogrammed) processes. ----------------- All synchronization has to be based on an understanding of which operations in the hardware are ATOMIC (indivisible). Seen from outside, an atomic operation has either finished or not started; it's never in-between. On a uniprocessor, atomicity means we never switch from one process to another in the middle of an atomic operation. In the earliest computers, only loads and stores were atomic. (That's loads and stores of whole words. Theoreticians consider machine models in which only loads and stores of individual bits are atomic, but nobody builds machines that way.) Condition synchronization with atomic reads and writes is easy. You just cast each condition in the form of "location X contains value Y" and you keep reading X in a loop until you see what you want. Mutual exclution is harder. Much early research was devoted to figuring out how to build it from simple atomic reads and writes. Dekker is generally credited with finding the first correct solution for two processes in the early 1960s. Dijkstra published a version that works for N processes in 1965. Peterson published a much simpler version of the two-process version in 1981: | type pid = 1..2 | turn : pid // initial value doesn't matter | c : array [pid] of Boolean // initialized to false | processor local i, otherguy : pid | | procedure acquire | c[i] := true | turn := otherguy | repeat until (not c[otherguy]) or (turn = i) | | procedure release | c[i] := false | | Peterson also showed how to generalize his solution to N processes; you | might want to try to figure it out. Unfortunately, it takes O(log n) time | to get somebody into the critical section (it's hierarchical). In 1987, Lamport published the first N-process solution that requires constant time per acquisition IN THE ABSENSE OF CONTENTION: type pid = 1..N x, y : pid // initialized to 0 b : array [pid] of Boolean // initialized to false procedure acquire loop b[i] := true x := i // most recent process to begin protocol if y <> 0 b[i] := false repeat until y = 0 continue y := i if x <> i // competition: recover b[i] := false for j <> i in pid repeat until not b[j] if y <> i repeat until y = 0 continue return procedure release y := 0 b[i] := false Notice what happens in the absense of competition: b[i] := true x := i ( y = 0 ) y := i ( x = i ) y := 0 b[i] := false It can be proven that N-process synchronization with only loads and stores requires more than constant time in the presense of competition. It's an open question whether you can synchronize in O(min(k,log n) time when k of n processes are currently competing for access. Note that Lamport's alg. also requires space per lock linear in the number of processes. It's an open question whether you can do better than this without requiring a bound on the relative rates of progress of different processes. | Synchronization with only loads and stores is also very subtle and | difficult. You could always just build a mutex lock and put everything | on top of this, but we don't want to over-synchronize things. For | example, there are algorithms for on-the-fly garbage collection | (everybody know what that means?), developed by Steele, Dijkstra, | Gries, Ben-Ari, and others, that use only atomic reads and writes. | They are much faster than they would be if processes were running | around locking and unlocking things, but they are at least as subtle as | the mutual exclusion solutions, so you can't get rid of all the | messiness just by abstracting it away. So, what works better than loads and stores? (Still talking about busy-wait solutions) Two possibilities: (1) On a uniprocessor, you can get mutual exclusion by locking out interrupts. Observations: - You can only afford to do this for a little while, so you don't lose any interrupts (of course in general you don't want to protect expensive things with spin locks). - Nothing else works if you're sharing memory with a device -- you sure can't use a spin lock! (DEADLOCK). - This doesn't work on multiprocessors. (2) Use better (more powerful) atomic operations: Hardware designers began in the late 60's to build so-called read-modify-write, or fetch-and-phi, instructions into their machines. common fetch-and-phi instructions: test_and_set fetch_and_store (swap) compare_and_swap load_linked/store_conditional less commonly: fetch_and_or fetch_and_and fetch_and_add fetch_and_clear_then_add All of these return the old value, prior to changes, from which you can of course deduce the new value. The simple test_and_set lock: type lock = Boolean := false procedure acquire (L : ^lock) repeat until test_and_set (L) = false procedure release (L : ^lock) L^ := false Problems: not fair (possible starvation) LOTS of contention, for memory and interconnect bandwidth Slightly better is to spin in the cache instead of on the bus: procedure acquire (L : ^lock) while test_and_set (L) = true repeat until *L = false This still causes a flurry of bus/interconnect traffic whenever the lock is released under contention; doesn't scale to large machines. Better solution uses Ethernet-style exponential backoff: const base = // some small number const limit = // some large number procedure acquire (L : ^lock) backoff = base while test_and_set (L) = true // held by somebody else b := backoff := min (backoff*2, limit) repeat while --b This still causes unbounded amounts of traffic on really large machines. Best known scalable lock is due to Mellor-Crummey and Scott: type qnode = record next : ^qnode locked : Boolean type lock = ^qnode // parameter I, below, points to a qnode record allocated // (in an enclosing scope) in shared memory locally-accessible // to the invoking processor procedure acquire_lock (L : ^lock, I : ^qnode) I->next := nil predecessor : ^qnode := swap (L, I) if predecessor != nil // queue was non-empty I->locked := true predecessor->next := I repeat while I->locked // spin procedure release_lock (L : ^lock, I: ^qnode) if I->next = nil // no known successor if compare_and_swap (L, I, nil) return // compare_and_swap returns true iff it stored repeat while I->next = nil // spin I->next->locked := false ============================================================= PROCESS IMPLEMENTATION Before we can talk about scheduler-based synchronization, we have to understand how processes are implemented. Implementation of processes (on a uniprocessor) from the bottom up coroutines, with explicit A-to-B transfer (switch/transfer) explicit reschedule (yield) timeslicing (implicit, forced reschedule) processes with address spaces Coroutines: symmetric transfer of control Coroutines are similar to procedure calls, except that they provide a symmetric transfer of control. procedure P; : Fork Q; : SWITCH(self, Q); : end P; procedure Q; : SWITCH(self, P); : end Q; Think of it as multiprogramming with scheduling predetermined Each coroutine has its own contiguous stack. It also has a "context block" that serves as a placeholder in queues, and contains the stack pointer of a non-running coroutine. SWITCH works like this: push state onto the stack (or into context block) registers frame pointer program counter maybe other stuff (for exception handling or debugging, for example) (most of this can be saved as part of the normal procedure calling mechanism) put stack pointer into context block of old coroutine pull stack pointer out of new coroutine return (into a different coroutine!) To create a new coroutine we allocate a context block and a stack (e.g. from a heap). At the bottom of the stack we conjure up a return address that, when used, will cause the coroutine to 'return' to the beginning of its code. We then set the saved stack pointer in the context block to point at the return address. Now we can transfer to the new coroutine whenever we want. It will "wake up" in the middle of SWITCH, just as if it had been around forever, and will "return" and start its work. Real multiprogramming is generally built on top of coroutines. To program with coroutines, we have to keep track of which coroutines are in existence, and we have to tell SWITCH which one to switch to. To free processes from the burden of knowing who should run next, we provide a SCHEDULER they can call to decide. The scheduler maintains a set of lists or processes that it uses to make its decisions. One list, the READY LIST, contains all the ready processes. Other lists are for blocked processes; there is one such list for every synchronization object, where synchronization objects represent things that a process could be waiting for. When a running process discovers that it must wait, it puts its own context block into a data structure where somebody else will find it when it's time for it to continue calls Sleep, which in turn takes somebody off the beginning of the ready list and switches to them When a process finds that somebody who is currently blocked can run again, it moves their context block to the tail of the ready list. Both the ready list and the synchronization data structures must be protected via mutual exclusion, implemented by locking out interrupts on a uniprocessor, or by locking out interrupts AND using a spin lock on a multiprocessor: acquire: disable interrupts while ! TAS (lock) enable interrupts disable interrupts end while Locking out interrupts protects us from, say, calling Sleep because we want to block, taking a clock interrupt in the middle of the call, faking a call to Sleep in order to preempt ourself, and messing up the data structures. Unfortunately, the naive implementation of this "save a pointer to myself and Sleep" operation contains a bad race condition: we aren't executing in the new process until the middle of SWITCH, so we don't want anybody messing with the old process we stowed in a data structure. There are several ways of dealing with this: make Sleep a critical section, and pass arguments to it that specify what to do with the old process acquire a lock, put the old process someplace, and call Sleep with the understanding that it will release the lock (if there is more than one lock, pass it as a parameter). have a 'saved' bit in the context block. Prior to putting its context block into a synchronization data structure, a process sets the bit to say it is NOT yet saved. In the middle of Sleep, after the state is saved, we flip the bit the other way. Then when taking a process off the ready list, we spin until the bit says the state is consistent, prior to restoring it. This solution has higher concurrency than the previous one on a multiprocessor. We introduce timeslicing by introducing a clock handler. If we're running in user mode when the clock interrupt goes off, the clock handler modifies the machine state to make it look like the user-level program made an explicit 'yield' system call. Then it jumps to the yield syscall interrupt handler. Older kernels sometimes disable preemption in the kernel; this obviates the need for locks on a uniprocessor. If execution is currently in the kernel, the clock handler sets a flag that the kernel checks immediately before returning to user space or entering the idle loop. (Some OSes, Unix among them, implement the idle loop as a separate, low-priority process.) If the flag is set, the kernel goes off and does what the clock handler would have liked to have done. If we're talking about user-level processes, we need to change address spaces, too. We can delay this until just before we return to user space, so long as all address spaces intersect in the kernel. It is traditional (in a module-based OS) to make them do so; the kernel portion is made inaccessible in user mode. When you trap to the kernel you don't change address spaces, but the change to kernel mode allows you to start reading and writing kernel code and data. ============================================================= SCHEDULER-BASED SYNCHRONIZATION The problem with spin locks is that they waste processor cycles. Sychronization mechanisms are needed that interact with a process scheduler to put a process to sleep and run something else instead of spinning. Note, however, that spin locks are still valuable for certain things, and are widely used. In particular, it is better to spin than to sleep when the expected spin time is less than the rescheduling overhead. SEMAPHORES were the first proposed scheduler-based synchronization mechanism, and remain widely used. Monitors came later. They have higher level semantics, but a few sticky semantic problems. In the strict meaning of the term they require language and compiler support. You also see library-based implementations, but those are basically a mutual exclusion lock combined with memory-less condition variables (more detail in a minute). Conditional critical regions are intuitively appealing, but expensive to implement; they deserve mention, but are not widely used. 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. Here is one possible implementation: type semaphore = record L : lock N : integer // initialized to something non-negative Q : queue of processes procedure P (var S : sem) with S acquire (L) N := N-1 if N < 0 put self on Q release (L) yield // remember how we closed the timing window else release (L) procedure V (var S : sem) with S acquire (L) N := N + 1 if N <= 0 move somebody from Q to the ready list release (L) This is a so-called "general semaphore". Dijkstra originally proposed BINARY semaphores. A binary semaphore is all you need for mutual exclusion. It is always initialized to 1, and its value never exceeds 1. Acquire_mutex is P. Release_mutex is V. Usually they don't tell you what happens if you do two V's in a row. The idea is you never do, so say the second one is ignored, or is treated as a run-time error. It is easy to show that you can build either kind of semaphore with the other (if you don't think you could do this in a moment on an exam, take some time to figure it out :-) What else can we do with (general) 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. Problems with semaphores (1) They're pretty low-level. When using them for mutual exclusion, for example (the most common usage), it's easy to forget a P or a V, especially when they don't occur in strictly matched pairs (because you do a V inside an if statement, for example, as in the use of the spin lock in the implementation of P). (2) Their use is scattered all over the place. If you want to change how processes synchronize access to a data structure, you have to find all the places in the code where they touch that structure, which is difficult and error-prone. monitors Monitors were an attempt to address the two weaknesses of semaphores listed above. They were suggested by Dijkstra, developed more thoroughly by Brinch Hansen, and formalized nicely by Hoare (a real cooperative effort!) in the early 1970s. Several parallel programming languages have incorporated monitors as their fundamental synchronization mechanism; we'll see some of these later in the semester. (Interestingly, none, to my knowledge, incorporates the precise semantics of Hoare's formalization). It is possible to put things similar to monitors into library packages, but they depend on conventions for correct use. << Optional exercise: think about what it might look like. >> A monitor is a shared object (abstraction) with operations, internal state, and a number of condition queues. Only one operation of a given monitor may be active at a given point in time. A process that calls a busy monitor is delayed until the monitor is free. On behalf of its calling process, any operation may suspend itself by waiting on a condition (and thereby releasing control of the monitor). An operation may also signal a condition, in which case one of the waiting processes is resumed, usually the one that waited first. It is important to understand the difference between condition queues and semaphores. If nobody is waiting a signal operation is a no-op; a V is not. Recall the bounded buffer with semaphores (above). Here's the same thing with monitors: monitor BB buf : array [1..SIZE] of data next_full, next_empty : integer := 1 slots : integer := 0 emptied, filled : condition entry insert (m : data) if slots = SIZE wait (emptied) buf[next_empty] := m next_empty := next_empty mod SIZE + 1 slots := slots + 1 signal (filled) entry remove : data if slots = 0 wait (filled) m : data := buf[next_full] next_full := next_full mod SIZE + 1 slots := slots - 1 signal (emptied) return m ------------- It is easily proven that semaphores and monitors are equally powerful: each can be used to implement the other. There are lots of other synchronization primitives. In practice, what you see most often are spin locks and semaphores. ============================================================= Lock-free synchronization idea is that every high-level operation contains a distinguished atomic instruction (usually CAS or SC) at which it takes effect. Prior to that instruction the operation "hasn't happened"; after that it has. May require some cleanup to fully complete after the atomic op. May require some cleanup to undo first part if the atomic op fails. Exist special-purpose algorithms for some common, important data structures, including stacks, queues, counters, priority queues. Also exist general-purpose techniques that turn sequential abstractions (sets of methods) into lock-free concurrent version, but unfortunately these don't produce efficient code for most algorithms. Simplest example, due to Herlihy: data structure is accessed through a single pointer. to modify the structure: read the pointer copy the (whole) data structure make sure the pointer hasn't changed yet (so your copy is consistent) modify your copy if the pointer still hasn't changed, switch it to your copy otherwise start over [describe the ABA problem] ============================================================= Synchronization Summary Spin locks are useful ONLY if you have multiple processors. Interrupt lockout works ONLY if you have a single processor. Scheduler-based locks work only if you have a scheduler underneath you. An interrupt routine can't block, and can't afford to spin for more than a bounded amount of time. Interrupt handlers on separate processors must synchronize with each other using spin locks. Top half and bottom half routines on the same processor must synchronize with each other by locking out interrupts. (Think of the bottom half as being "underneath" processes -- bottom half activity doesn't have a process context. From the point of view of the top half, the operation of the bottom half looks like spontaneous atomic changes to data structures, occuring when interrupts are not disabled.) Top half and bottom half routines on multiple processors must synchronize using a combination of locking out interrupts and spin-waiting. If both spinning and blocking are options, you should generally spin if the expected wait time is less than twice the context switch time. Spin locks are vulnerable to pathological performance problems if a lock holder can be preempted. We can mitigate the problem to *some* degree if other processes are using spin-then-wait locks. Alternatively, we can consider scheduler modifications that avoid preempting a lock holder (I haven't talked about this, and it isn't trivial for user-level processes, because the kernel scheduler can't let a user hog the processor.) Lock-free data structures avoid the preemption problem, but are efficient only in special cases. ------------------------------------------- Handling device interrupts The simple case when a device interrupt occurs is that we can do everything we need to do in the interrupt handler, and just rfe to what we were doing before. Three complications may arise: (1) we may need more time than we have between interrupts; (2) we may need to access a data structure that needs to be protected by a scheduler-based lock, in which case the bottom half can't touch it; (3) we may need to re-schedule processes in the top half, because we want to unblock a process with higher priority than the previously-running process. Suppose we need more time (case (1)). If we need more time *on average* than we have between interrupts, we're in trouble: the OS won't work. But there are things for which we *sometimes* need extra time. Examples: - On some machines the clock interrupts at a high frequency. If we don't want to lose ticks, we have to rfe quickly. We may not have time to move a process to the ready list. We certainly don't have time to re-transmit packets in a time-driven reliable network protocol peruse physical page frames for page-out transmit heartbeat messages in a reliable distributed system - Some devices (e.g. Ethernet) are bursty. We may not have time to process an incoming packet before we get another one, but we can queue it for processing later. When we need extra time, we can get it by queueing notice of what we need done and arranging for somebody else to do it later. We can still do the work in the bottom half of the kernel by sending ourselves an interrupt at a lower priority level than the device. When we rfe, we'll get the next lower-priority interrupt. If no devices need urgent service, we'll get the low-priority interrupt we sent ourselves. [In Unix, the high-priority clock handler is called 'hardclock'; the low-priority handler is called 'softclock'.] If the thing that needs to be done in response to the interrupt is complicated enough that it may need to block, then there has to be a real process looking for the interrupt. The handler's job is to notify that real process. This is case (2) or (3) above. Commonly, the notification is given by doing a V on a semaphore. If we discover that a process is *currently* waiting, we have to move it to the ready list as part of the V operation. We may also want to reschedule, so that the blocked process can finish its (possibly high-priority) kernel operation. Rescheduling requires a high-level policy decision, which we don't want to make in the bottom half. It also has to be delayed if the interrupted activity was already in the (top half of) the kernel. So we need to do a fake syscall like the 'yield' call above. We might as well have the syscall do the whole V operation. That way the bottom half never has to manipulate process queues, and they don't have to be protected with interrupt-masking locks. To summarize: we have three ways to accomplish work in response to an interrupt: (1) do it in the (bottom-half) interrupt handler at interrupt priority (2) schedule a software interrupt to do it in the bottom half at lower priority (3) transfer control to the top half of the kernel -- if execution is currently in the top half, leave a notice where it will be seen before going back to user space; if execution is currently in user space, fake a syscall. (1) is clearly the most efficient, but is limited by how long you can afford to spend on it, and by whether you need to use data structures that can't reasonably be protected by interrupt-masking locks. (2) buys you time, but still can't block or use data structures not protected by interrupt-masking locks.