Computer Science › Section D · Operating systems › Topic D.4
Coordinating the machine: processes and scheduling
A laptop seems to play music, download files and respond to your typing all at once, even though it has far fewer processor cores than running programs. The operating system creates that effect by treating each running program as a process and switching the processor among them many times a second.
Programs and processes
A program is a fixed set of instructions stored in a file. A process is the activity of carrying out those instructions under the operating system's control, and it changes from moment to moment. One program can give rise to many processes: open the same text editor twice and you have two processes, each with its own document and position in the code. The OS tracks each process by a process identifier (PID). Managing processes means giving each the processor time, memory, files and devices it needs, while stopping them from interfering with each other.
Process state and the process table
At any instant a process has a state: a snapshot of where it is in its program, held in the program counter, plus the values in the other processor registers and in its memory. If the OS can save that snapshot and later put it back, the process can be stopped and resumed as if nothing had happened. To keep track of every process, the kernel maintains a process table in main memory. Each entry records items such as the process's PID, the memory area it was given by the memory manager, its priority, its saved registers and whether it is ready to run or waiting.
The life of a process
A process moves through a few states. It is new while being created, then ready when it could run but is waiting for a processor. When the processor is given to it, it is running. If it must wait for something outside itself, such as data from a disk, a key press or a message from another process, it becomes waiting, also called blocked, and uses no processor time. When the event happens it becomes ready again. A running process can also be sent back to ready when its time is up. Finally it is terminated and removed from the table.
The scheduler and the dispatcher
Two kernel components share the work. The scheduler admits new processes to the process table, removes finished ones and decides their priorities. The dispatcher hands out the processor. It divides time into short time slices, typically from a few to a few tens of milliseconds, and starts a timer each time it gives one to a process. When the slice ends, the timer sends an interrupt: the processor finishes its current instruction, saves its place and runs an interrupt handler, which is part of the dispatcher. The handler records the current process's state, picks the highest-priority ready process, restarts the timer and restores that process's state. Changing from one process to another like this is a context switch, or process switch.
Why switching saves time
Switching has a cost, yet it makes the machine more productive overall. Without it, a process that stops to wait for a disk or a user would leave the processor idle for that whole wait. Disk and network operations take far longer than processor instructions, so the idle time would be huge. Instead, when a process requests input or output, the OS marks it waiting and the dispatcher gives the processor to a ready process. A process that spends most of its time waiting for input and output is called I/O-bound; one that mostly computes is compute-bound, or CPU-bound. Mixing the two keeps both the processor and the devices busy.
Worked example: the price of a context switch
Suppose each context switch takes 0.5 ms, and each process uses its full slice before being switched out. What fraction of processor time does useful work? 1. With 20 ms slices, each cycle is 20 + 0.5 = 20.5 ms, of which 20 ms is useful: 20 ÷ 20.5 ≈ 97.6%. 2. With 2 ms slices, each cycle is 2.5 ms: 2 ÷ 2.5 = 80%. 3. So shorter slices waste more time on switching. 4. But longer slices make each process wait longer for its turn, so the system feels less responsive. 5. Check: the fraction is slice ÷ (slice + switch time), which nears 100% as slices lengthen. Real systems balance the two.
Scheduling policies
The rule for choosing the next process is the scheduling policy. First-come, first-served (FCFS) runs processes to completion in arrival order; it is simple, but one long job holds up every short one behind it. Shortest job first runs the shortest job first, which gives the lowest average waiting time for jobs that arrive together, if their lengths are known, which they rarely are. Round robin gives each ready process one time slice in turn, cycling through the queue. Priority scheduling always picks the most important ready process. Fixed priorities risk starvation, where a low-priority process never runs, so many systems use aging, gradually raising a waiting process's priority.
Worked example: FCFS against round robin
Processes A, B and C arrive together needing 10, 4 and 7 ms of processor time. Ignore switching time. 1. FCFS runs A from 0 to 10, B to 14 and C to 21. Average turnaround, from arrival to finish, is (10 + 14 + 21) ÷ 3 = 15 ms. 2. Round robin with 4 ms slices: A 0-4, B 4-8 (finished), C 8-12, A 12-16, C 16-19 (finished), A 19-21 (finished). 3. Average turnaround is (21 + 8 + 19) ÷ 3 = 16 ms, slightly worse. 4. But B and C first get the processor at 4 and 8 ms instead of 10 and 14 ms. 5. Check: both schedules end at 21 ms, the total work. Here round robin bought responsiveness, not speed.
Threads and multiple cores
A thread is one sequence of execution within a process. A process can have several threads that share its memory and open files but each have their own program counter and registers. A browser might draw the page in one thread while another downloads images. Switching between threads of one process is usually cheaper than switching processes, and sharing data is fast, though it needs care, as the next topic, Competition among processes: semaphores and deadlock, explains. On a multicore processor, the dispatcher can run different threads or processes on different cores at genuinely the same time, and must decide which work goes to which core.
Common mistakes to avoid
A program and a process are not the same thing: the program is the stored code, the process the running activity, and one program can have many processes. A waiting process is not ready: it cannot use the processor until its event occurs, so giving it a slice would be wasted. Round robin is not chosen to cut average turnaround, which can come out worse than under FCFS, as in the worked example; its gain is that every job gets a quick first turn. On a single core, time slicing only alternates between processes and never runs two at the same instant. And a time slice can end early: a process that requests input or output gives up the processor before its slice is over.
Key takeaways
A process is a program being executed, with a state made of its program counter, registers and memory. The process table records each process's memory, priority, saved state and whether it is ready or waiting. The scheduler manages the pool of processes and the dispatcher hands out time slices, using timer interrupts and context switches. Switching costs a little time but fills the idle gaps while processes wait for input and output. Policies include FCFS, shortest job first, round robin and priority scheduling, with aging to prevent starvation. Threads share a process's memory, and multicore processors run several at once.
Flashcards
Flashcard
A program being executed under OS control
Test your understanding
Question 1 of 5
Processes P, Q and R arrive together needing 5, 3 and 2 ms. Round robin uses 3 ms slices in the order P, Q, R, and switching time is ignored. When does P finish?
Question 2 of 5
A process has asked the disk for data and the data has not arrived. Which state is it in, and can the dispatcher give it a time slice?
Question 3 of 5
Time slices are 4 ms and each context switch takes 1 ms. If every process uses its full slice, what fraction of processor time does useful work?
Question 4 of 5
What happens at the moment a time slice ends?
Question 5 of 5
A system uses fixed priorities, and high-priority processes keep arriving. What problem can a low-priority process suffer, and what is a common fix?
