Scheduling algorithms in interactive systems

In an interactive system (time-sharing, servers, PCs) the aim is a quick response to users; scheduling must be preemptive so that no process can hog the CPU. The main algorithms are:

1. Round Robin (RR)

Each process gets a small time slice (quantum). When it expires, the process is preempted and put at the tail of the ready queue. It is simple and fair. A quantum that is too small wastes time in context switches; one that is too large behaves like FCFS (a typical value is 20-50 ms). Average waiting time is often long.

2. Priority scheduling

Each process has a priority and the highest-priority ready process runs. It may be preemptive. Priorities may be static or dynamic. A problem is starvation of low-priority processes, solved by aging (gradually raising the priority of waiting processes).

3. Multiple (multilevel feedback) queues

Priority classes use several ready queues. Queue 1 has the highest priority and a small quantum; a process that uses up its quantum moves to a lower queue with a bigger quantum. CPU-bound jobs sink, while I/O-bound and interactive jobs stay on top. It is flexible but complex to tune.

4. Shortest Process Next / Shortest Remaining Time

The process with the shortest expected next CPU burst is chosen. The burst is estimated by aging: τₙ₊₁ = a·tₙ + (1 − a)·τₙ, where tₙ is the most recent measured burst and τₙ is the previous estimate (0 ≤ a ≤ 1). It minimises average waiting time but may starve long jobs.

5. Guaranteed scheduling

The system promises each of n users 1/n of the CPU. It computes the ratio (actual CPU time used)/(entitled time) and runs the process with the lowest ratio.

6. Lottery scheduling

Each process holds lottery tickets for the CPU; at each scheduling decision a random ticket is drawn and its owner runs. More tickets means a larger share. It is simple, responsive and fair, and cooperating processes can exchange tickets.

7. Fair-share scheduling

The CPU is divided among users, not processes, so a user with many processes does not get more CPU time than a user with one.