Notes for CSC 2/456, 26 January 2000 ff Read chapter 5. (You should already have read 1-4 and 6) ============================================================= SCHEDULING POLICIES Scheduling is deciding what to run when there's more than one thing you could run. It's hard because you have to balance some conflicting goals: cpu utilization: how busy is the cpu -- don't want it idle, or otherwise wasting time. Might be idle if you don't context switch on I/O; might waste time if you context switch too often (since that induces overhead) throughput (especially important for batch systems): how many jobs go thru the sytem per unit time response time (especially important for time-sharing systems): how long the user has to wait for trivial operations (e.g. character echoing). Both latency and variance matter; human-factors studies tend to indicate that latencies are indistinguishable under half a second (maybe a tenth of a second for echoing), and that low variance above half a second is often more important than low latency. turnaround time (especially important in batch systems): average time each job is in the system -- how long you expect to wait to get your results. fairness We can't meet all goals at once. For example, utilization and response time conflict directly. Maximum utilization comes from a RUN-UNTIL-BLOCK policy. Good response time requires a PREEMPTIVE policy -- frequent context switches. Types of Scheduling long-term: deciding which job to accept into the system long-term scheduling is important for batch systems, but irrelevant for time-sharing medium-term: deciding which running process must block for resources (NOT synchronization) swapping is a form of medium-term scheduling. so are various deadlock-avoidance algorithms (e.g. banker's) short-term: deciding who runs among the processes that can run This is what I'll focus on below. ------------------------------ Info that can drive policy: intrinsic to process: memory needs, cpu needs, resources held extrinsic to process: user priority, job cost status of overall system: size of the ready list, amount of memory available ------------------------------ Common Policies Simplest run-until-block policy: FIRST-COME-FIRST SERVED (FCFS) Guarantees eventual service. Sometimes interpreted (by some authors) to mean you don't switch on I/O, but that's silly. Better interpretation is: when the current job blocks, switch to the job that's been waiting longest for the CPU. Simplest preemptive policy: ROUND ROBIN The scheduler allows a process to run for some QUANTUM time t, after which it is interrupted and moved to the tail of the ready queue. If the quantum is too high, RR = FCFS. If quantum is too low, RR spends too much time context switching. (Typical context switching requires a few thousand cycles, plus whatever time may be needed to re-establish cache and TLB footprint.) Optimal policy for expected turnaround time: SHORTEST JOB FIRST Provably optimal policy for expected turnaround time is to run the job with shortest time to completion next (avoids "convoy effect"). Requires that you know time to completion. You have a pretty good idea in some environments (e.g. commercial transaction processing), but not in most. Many fancier schemes use some notion of PRIORITY Always run the process with the highest priority. If several processes are tied for first, do them round-robin. Priorities can be based on lots of things, including degree of interactiveness and user id. We can favor interactive jobs (good for response time) by giving higher priority to processes that only use part of their quanta before blocking. To give the system stability, we probably want to base decisions on a several-quantum interval, with the most recent ones being most important. Here's how this can work: base priority on fraction of last quantum used (e.g. priority = 1/f, where f is fraction). If we think you'll use the whole quantum, your priority is 1. If we think you'll use only 1/10 of it, your priority is 10. To get our estimate of the fraction you'll use, average the current estimate and the actual fraction used in the most recent quantum to get the new estimate. (Can use a weighted average if you prefer). Note that priority scheduling can lead to starvation. Probably want to up the priority of processes that haven't run in a long time, even if they don't measure up on other criteria, so they eventually get some time and get out of the system. This is known as AGING. It can be implemented by a scheme very much like the one in the preceding paragraph. The art of compromise: MULTIPLE QUEUES, MULTI-LEVEL SCHEDULING Divide jobs into classes. Each class of job has its own scheduling queue. Each scheduling queue has its own scheduling policy (e.g. compute-bound jobs get longer quanta). There's a meta-policy for priorities among queues. Examples: CTSS gives compute-bound jobs longer quanta less frequently. Swap-based systems always run in-core jobs, but periodically cycle some things out to disk and some things in from disk. Modern Unix variants have a special class for (soft) real-time processes, which always get priority over non-real-time processes. Linux has two real-time classes, one preemptive and one (the highest) non-preemptive. In the language of the text, this is "Multilevel Queue Scheduling". It's not the same as "Multilevel Feedback Queue Scheduling". That's what Unix does (see below). It's basically unrelated; I wish Silbershatz and Galvin didn't use such similar names. Note that priorities introduce the possibility of high-priority things waiting a LONG time because they need resources held by low-priority things, which never get to run because of the existence of unrelated medium-priority things. This is known as *priority inversion*. We'll consider this issue some later under the subject of deadlock. The usual solution is for the high-priority thing to lend its priority to the low-priority thing for which it is waiting. A relatively recent entry: LOTTERY SCHEDULING (Waldspurger et al., first OSDI, Nov. '94) Hand out "lottery tickets" -- each job gets a quantity of tickets proportional to its importance. When it comes time to re-schedule, choose a ticket randomly and give it to the process that holds that ticket. Over time, processes with more tickets tend to get a bigger share of the CPU, and there's no need for aging, feedback (see below), etc. Very simple and, probabilistically, very nice behavior. Note that use of lottery scheduling is independent of *when* you choose to reschedule; you can have both preemptive and non-preemptive lottery systems. How do you implement tickets? One simple scheme is to keep all ticket holders in a linked list, where each entry indicates the number of tickets held. Also remember the total number N of tickets extant. To schedule, choose a random number I in the interval 1..N. Traverse the list, adding up the number of tickets in each process, until you find the process with the Ith ticket. Note that tickets don't have individual identities -- which subrange a process has changes as processes come and go -- and that you naturally get "inflation" and "deflation" of ticket values as processes come and go. ------------------------------ Example: Scheduling in Berkeley Unix (inc. FreeBSD/NetBSD and Solaris [I think], but not Linux) Priorities range from 0 (highest) to 127 (lowest). 0 swap daemon 4 waiting for memory 8 waiting for file control information 16 waiting for disk I/O completion 20 waiting for kernel-level file system lock 22 generic in-the-kernel priority 24 waiting on a socket 32 waiting for a child to exit 36 waiting for user-level file system lock 40 waiting for a signal >=50 in user mode Multi-level feedback scheme. Each group of 4 consecutive priority levels has a separate run queue. The first process on the highest priority queue is selected to run. Processes on a queue are served round-robin (1/10 sec quantum). If a runable process gets a priority above that of the running process the running process gets to finish its quantum. If a blocked process gets a priority above that of the running process a switch happens at the end of the current or next system call. Currently running process is not on any queue. No special idle process; the scheduler contains an idle loop. User-level priorities are dynamically adjusted based on load average and estimate of process's CPU utilization. The load average is the average number of runable processes over the last minute. The CPU utilization estimate is a unitless integer between zero and roughly 200, determined by the balance of two competing calculations: The bottom-half "hardclock" timer interrupt handler increments the utilization estimate of the currently-running process on every clock tick (100x/sec). The top-half "softclock" timer interrupt handler (scheduled as necessary by hardclock) applies a decay factor of 2L/(2L+1) once per second, where L is the load average. 2L/(2L+1) is always less than 1, so if a process blocks for a long time, its utilization estimate drops toward zero. If a process monopolizes the CPU, then it accumulates 100 ticks per second. At the same time, the ready list must be empty (else the process wouldn't keep running), so so the load average is 1 and 2L/(2L+1) = 2/3. Thus over time the process's utilization average approaches (100 x 2/3) + (100 x 4/9) + (100 x 8/27) + ... 2/3 = 100 sum (2/3)^i = 100 x ------- = 200 i>=1 (1 - 2/3) If two compute-bound processes share the CPU, each gets about 50 ticks per second, and its utilization average approaches (50 x 4/5) + (50 x 16/25) + (50 x 64/125) + ... 4/5 = 50 sum (4/5)^i = 50 x ------- = 200 i>=1 (1 - 4/5) If ten compute-bound processes share the CPU, each gets about 10 ticks per second, and its utilization average approaches (10 x 20/21) + (50 x 400/441) + ... 20/21 = 10 sum (20/21)^i = 10 x --------- = 200 i>=1 (1 - 20/21) The formula for priority is PUSER + estcpu/4. Hardclock recalculates this value for the currently-running process if that process has accumulated 4 ticks since the last calculation. (4 is the right number because it can move a process to the next lower queue.) There's no point in re-calculating the priority of a blocked process, since it can't run anyway. Instead just maintain enough information to update prioirity when it wakes up. Since it wouldn't have been accumulating ticks, the only effect to capture is the decay calculation performed for runnable processes by softclock. That's easy to duplicate given an estimate of wait time. 'nice' is a weighting factor, with two effects. 2*nice is added onto the top when calculating priority ( <= 40 slot shift). Also, nice is factored into the softclock decay calculation in such a way that priviliged processes approach a lower utilization asymptote, and drop faster when not running. On a heavily-loaded system, a non-running anti-privileged program may not age, and thus may starve. Note that to keep things in bounds we have to pull extreme calculated priorities back into the range of 50..127. ------------------------------- Other systems Linux has a single ready list. When it needs to reschedule it scans the whole list, calculating priorities for every runnable process. The algorithm is rather ad-hoc, but seems to work ok. Windows NT also has a single ready list, which it keeps sorted by priority. Priorities don't change as much as they do in BSD. They have a "base" value that is temporarily increased on I/O completion, GUI wait, and apparent starvation (ad-hoc patch for priority inversion). NT does something interesting that BSD does not, however: it allows different processes to have different base quantum lengths, and it dynamically increases the quantum length of the foreground interactive thread. ------------------------------- Multiprocessor issues Recall that a MP OS may be symmetric or asymmetric. If asymmetric, all scheduling is probably done by the master processor. If symmetric we have some organizational options: process-based between processors: send other processor a message. Internal organization can be either process-based or module-based. module-based throughout: modify remote structures directly requires hybrid (spin/interrupt-masking) locks (as discussed last time) if accessible from bottom-half routines requires *some* sort of locks (prob. just spin lock mutex) even if accessible only from top-half routines requires remote interrupt mechanism to force immediate rescheduling. Remote interrupt handler can then do work (e.g. modify read list) itself if structure is accessible to bottom half, or can wake up its own top half if structure is not accessible Module-based inter-node organization works best on small-scale bus-based machines. On really big machines, memory is distributed around the machine, and operations on non-local memory may be expensive enough that for non-trivial operations it's cheaper to send a message and get somebody at the far end to do the operation than it is to do the operation yourself by manipulating data structures remotely. Parallel programs introduce some new policy problems. These include user-level synchronization, which can interact badly with scheduling. We've already discussed the problem of preemption while holding a lock. *Gang scheduling*, or *co-scheduling*, is the idea of getting all the processes in a given application to run at the same time. Good for barrier-based programs. Not so good for producer-consumer or client-server programs. Requires some non-trivial (and maybe non-possible) bin packing if you've got a lot of applications. What works well depends a lot on the machine. In particular, moving things between processors may or may not be possible/cheap. device needs cache footprint TLB footprint availability of main memory even processor types Emerging consensus in the research community is that (1) some sort of coscheduling and *processor affinity* (try to keep processes where they ran most recently, to exploit cache and TLB footprint) makes sense for small bus-based multiprocessors, and (2) some sort of *processor partitioning* (semi-permanently allocating some fraction of the processors of the machine to each application) makes sense for large-scale network-based machines. Commercially, most small multiprocessors currently use round-robin, possibly augmented with processor affinity, and large multiprocessors do something ad-hoc and non-standard. ============================================================= USER-KERNEL INTERFACE WRT PROCESS MANAGEMENT Recall from CSC 2/454 that there are several ways to specify process creation (co-begin, par-do, implicit receipt, fork/join, early reply). When talking about OS-supported processes, fork (and maybe join) are what you usually see. The *right* way to fork is to specify the program that the newly-created process is supposed to run. Due to historical accident, Unix doesn't do it this way... Example: Unix Processes Historicall Unix didn't have "lightweight" kernel processes, so the kernel calls to create heavyweight and lightweight processes were introduced a long way apart in time, and look very different. You're using the lightweight process creation calls (thr_create or pthread_create) in the current assignment. These create a new LWP or thread (your choice) within your program. They require you to specify the subroutine in which the LWP or thread should start executing, and optionally allow you to specify additional parameters (location of stack, scheduling discipline, LWP v. thread, etc.) For heavyweight processes, what the rest of the world calls 'fork' is divided in Unix into two pieces, one of which is called 'fork' and the other of which is called 'exec'. // clone this process in a copy of the address space // return child's process id to parent, 0 to child // child inherits (shares) open file descriptors, which it can pass to // exec if desired process_id := fork(); if process_id = 0 then // child code exec(filename, args*); : // die, passing status to parent: exit(status); else // parent code : status = wait(process_id); : kill(process_id,signal); : end if; The common fork-then-exec idiom is very wasteful: it copies the address space for nothing. Most modern Unix variants reduce the cost as much as possible, consistent with the advertised semantics, by doing *copy-on-write* (more on this later). Most also provide a "vfork" variant in which the child borrows the address space of the parent long enough to execute an exec or exit call. The parent is suspended in the meantime. Note that this changes the semantics: any changes to global variables made by the child will be visible to the parent when it wakes up. ------------------------------- Signals Book doesn't talk about this much, but one of the main things an OS has to do in the way of process management is to handle exceptional conditions, generally including a mechanism by which processes can poke one another. In Unix this mechanism is called the signal, and it's one of the messiest parts of process management. Lots of different kinds of signals. errors timers I/O debugging start/stop (^S/^Q) use of non-process-group terminal (for job control) change in window size Lots of different default actions if signal not expected ("handled"). Some signals may not be allowed to be handled (uncatchable). Signals resemble interrupts from the virtual machine implemented by the kernel. Modern (BSD, Posix) Unix gives them hardware-like characteristics: reliable maskable temporarily masked when delivered not un-vectored when delivered Many signals need to be delivered even when the process is currently blocked in the middle of a system call. Unix has a mechanism for *aborting* the current system call in order to deliver a signal. When setting up the signal handler the user can specify whether aborted system calls should be re-started automatically. If so, the kernel munges the user state ("backs up the PC") when delivering the signal so that return from the signal handler (via return-from-subroutine instruction) will make it re-execute the trap instruction. If kernel calls are NOT to be re-started automatically, the user should always check the return status of the system call for the possibility "aborted due to signal". Note that resuming the process in the middle of the system call is not generally an option: the signal handler has all the normal rights of a user-level program, including the right to make *another* system call, and allowing a single process to be "in the kernel" twice simultaneously just gets too complicated. Signals are never delivered to processes with extremely high priority; such priorities are employed only for critical atomic kernel functions like swapping in and out.