Process Scheduling

Scheduling

1. Short-term scheduling (STS): select a process from the ready queue to execute on the CPU.
2. Medium-term scheduling (MTS): select suspended processes in secondary storage to bring into memory; a process still awaiting an event remains blocked.
3. Long-term scheduling (LTS): select a job from secondary storage, bring it into memory, create its process, and add it to the ready queue.

Scheduling Criteria

Scheduling criteria are divided into user-oriented and system-oriented criteria.

User-oriented criteria include:

1. Fast response: response time is an important scheduling criterion. The policy should reduce response time to a level users can accept.
2. Short turnaround: turnaround is the interval from job submission to completion. It is an important measure of batch-system performance and a criterion for choosing scheduling methods and algorithms.
3. Meeting deadlines: a deadline is the latest time a task must start or finish and is important for evaluating real-time systems.
4. Priority: urgent jobs should be handled promptly; stricter requirements often need preemptive scheduling.

System-oriented criteria include:

1. High throughput: the number of jobs completed per unit time.
2. High processor utilization: utilization is an important performance measure.
3. Balanced resource use: use memory, secondary storage, I/O devices, and other resources effectively.
4. Fairness: processes should not suffer starvation.

Decision Modes

OS scheduling algorithms use nonpreemptive or preemptive decision modes.

• Nonpreemptive: once a process starts, it retains the processor until it exits, blocks, or yields. This mode is mainly used in batch systems.
• Preemptive: the running process can be interrupted and returned to ready, preventing one process from monopolizing the CPU. This mode is used in real-time, time-sharing, and performance-sensitive batch systems.

First-Come, First-Served (FCFS)

FCFS is the simplest CPU-scheduling algorithm and is easily implemented with a FIFO queue. When a process enters the ready queue, its PCB is linked to the tail. When the CPU becomes free, it is assigned to the process at the head, which is removed from the queue.

FCFS often has a long average waiting time.

Suppose these processes all arrive at time 0:

With queue order P1, P2, P3, the timeline is P1 [0,24) → P2 [24,27) → P3 [27,30).

P1 waits 0 ms, P2 waits 24 ms, and P3 waits 27 ms. Average waiting is $(0+24+27)/3=17$ ms.

With queue order P2, P3, P1, the timeline is P2 [0,3) → P3 [3,6) → P1 [6,30).

Average waiting is now $(0+3+6)/3=3$ ms, a substantial reduction.

FCFS has these characteristics:

• Idea: fairness in queue order.
• Rule: serve processes in arrival order.
• Decision mode: nonpreemptive.
• Advantages: queue-order service and simple implementation.
• Disadvantages: short jobs behind long ones wait a long time and have large normalized turnaround, producing a poor user experience.

Shortest Job First (SJF)

For known CPU bursts, simultaneous arrival, and no switching overhead, SJF minimizes average waiting time. Moving a short process ahead of a long one decreases the short process's waiting time more than it increases the long process's waiting time.

The difficulty is knowing the next CPU burst's length. One approach predicts it from previous bursts, assuming the next length will be similar, then selects the process with the shortest predicted burst.

SJF can be preemptive or nonpreemptive. When a new process arrives, its next burst may be shorter than the running process's remaining burst. Preemptive SJF switches to the new process; nonpreemptive SJF lets the running process complete its burst. Preemptive SJF is called shortest remaining time first (SRTF).

Suppose these processes arrive:

The preemptive SJF timeline is P1 [0,1) → P2 [1,5) → P4 [5,10) → P1 [10,17) → P3 [17,26).

P1 starts at time 0 because it is the only available process. P2 arrives at time 1. P1 has 7 ms remaining, more than P2's 4 ms, so P1 is preempted and P2 executes.

Average waiting is $[(10-1)+(1-1)+(17-2)+(5-3)]/4=26/4=6.5$ ms.

With nonpreemptive SJF, average waiting is 7.75 ms.

Priority Scheduling

Priority scheduling assigns each process a priority and chooses the highest-priority process at a scheduling decision. Giving a long process higher priority can reduce postponement by short processes, but low-priority processes can still starve.

Its advantage is giving important tasks CPU time; its disadvantage is possible starvation of low-priority tasks. Priorities can be adjusted dynamically, for example by reducing a process's priority after some CPU service or increasing a waiting process's priority. A process that waits a long time can eventually receive CPU time as its priority increases.

Suppose these processes arrive at time 0, with smaller numbers indicating higher priority:

The timeline is P2 [0,1) → P5 [1,6) → P1 [6,16) → P3 [16,18) → P4 [18,19). Since all arrive together, preemptive and nonpreemptive policies produce the same result here.

Average waiting is $(6+0+16+18+1)/5=8.2$ ms.

Round Robin (RR)

RR was designed for time-sharing systems. It resembles FCFS but adds preemption to switch processes. A small unit of time is called a quantum or time slice. Its size depends on the system; 10 to 100 ms is a traditional example range.

The ready queue is circular. The scheduler cycles through it, allocating no more than one quantum to each process.

Two cases can occur:

1. The process needs less than one quantum: it releases the CPU, and the scheduler handles the next process.
2. The process needs more than one quantum: when the slice expires, a context switch occurs, the process returns to the tail, and the scheduler selects the next process.

Average waiting under RR can be long, depending on the workload and quantum.

Suppose these processes all arrive at time 0:

With a 4 ms quantum, P1 executes for the first 4 ms. Since it needs another 20 ms, it is preempted. P2 executes next and finishes before its slice expires. P3 follows, then the CPU returns to P1 after each process has received a slice.

The timeline is P1 [0,4) → P2 [4,7) → P3 [7,10) → P1 [10,14) → P1 [14,18) → P1 [18,22) → P1 [22,26) → P1 [26,30).

Average waiting is $[(10-4)+4+7]/3=17/3\approx5.67$ ms.

RR performance depends strongly on quantum size. A very large quantum makes RR equivalent to FCFS; a very small one causes many context switches.