---
title: The Processor Scheduling
date: 2024-03-29
excerpt: Levels of processor scheduling, scheduling queue models and criteria, scheduling algorithms, and real-time scheduling.
tags:
  - OS
  - Process
cover: https://assets.vluv.space/cover/OS/Ch3-1ProcessScheduling.webp
updated: 2026-07-08 21:17:39
lang: en
i18n:
  cn: /Ch3-1TheProcessorScheduling
  translation: 2
---

## Process Scheduling Levels

### Overview

The processor is a key resource in a computer system. In a **multiprogramming environment**, the number of processes usually exceeds the number of processors, so the system must dynamically assign the processor to a process in the ready queue according to some policy. Processor utilization and system performance (throughput, response time) depend largely on processor scheduling.

- WHAT: by what principle the CPU is allocated — the scheduling algorithm
- WHEN: when the CPU is allocated — the timing of scheduling
- HOW: how the CPU is allocated — the scheduling procedure and process context switching

### Job

A job is the collection of work a user asks the computer system to perform during one computation or one transaction.
A job is a broader concept than a program: it may contain multiple programs and data, plus a job specification, and the system controls the programs in the job according to that specification. In batch systems, work is loaded from external storage into memory at the granularity of jobs.
To have the computer complete a specific task, the user first writes a source program and submits it to the computer; through compiling or assembling, linking, loading, and running, the computer finally outputs the results the user wants. From the computer's management perspective, this series of tasks executed by the computer is a job.

> Job and task are today vague, ambiguous terms, especially task. A “job” often means a set of processes, while a “task” may mean a process, a thread, a process or thread, or, distinctly, a unit of work done by a process or thread.
> [job, task and process, what's the difference](https://stackoverflow.com/questions/3073948/job-task-and-process-whats-the-difference)

#### Job Step

The computer completes a job through a series of ordered work steps, each finishing a specific part of the job. This series of ordered, relatively independent steps needed to complete a job is called a **job step**.
Although each job step is functionally independent, the steps are interrelated: one step's execution often needs the result of the previous step.

> From the user submitting the source program to obtaining the results, several steps are needed. First, the system edits the source program and checks the syntax, then compiling or assembling produces object code. Linking forms a load module, which loading brings into memory. Finally, running produces the results. Five steps, each completing a relatively independent piece of work.
>
> ![](https://assets.vluv.space/UESTC/OS/Ch3-1TheProcessorScheduling/Ch3-1TheProcessorScheduling-2024-03-29-15-12-12.webp)

#### Job State Transition

![Ch3-1TheProcessorScheduling-2024-03-29-15-26-26](https://assets.vluv.space/UESTC/OS/Ch3-1TheProcessorScheduling/Ch3-1TheProcessorScheduling-2024-03-29-15-26-26.webp)

#### JCB

After a job is submitted and enters the backlogged (held) state, the system creates a Job Control Block (JCB) for it.
The JCB exists throughout the job's entire run, and its contents change dynamically in step with the job's state. Only when the job finishes and leaves the system is the JCB destroyed. In short, **the JCB is the sole sign of a job's existence in the system**; only through the JCB does the system perceive the job.
The JCB contains the information needed to manage the job. Part of this information comes from the job control cards or job specification the user supplies; the rest records dynamic information from the job's run.

### Levels of Processor Scheduling

- In a multiprogramming system, a job usually passes through several levels of scheduling from submission to execution, such as high-level scheduling, low-level scheduling, intermediate-level scheduling, and I/O scheduling.
- System performance depends largely on scheduling: throughput, turnaround time, responsiveness, and so on.
- Scheduling is the key to multiprogramming systems.

|          Type           | Frequency | Duration | Algorithm Complexity | Storage                    | OS                          |
| :---------------------: | :-------: | :------: | :------------------: | -------------------------- | --------------------------- |
|   Process scheduling    |   High    |  Short   |         Low          | In memory                  | Batch, real-time, time-sharing |
| Intermediate scheduling |  Medium   | Shorter  |        Medium        | Memory/external swapping   | Batch, real-time, time-sharing |
|     Job scheduling      |    Low    |   Long   |         High         | External storage to memory | Batch                       |

#### High-Level Scheduling

**High-level scheduling**, also called **job scheduling, admission scheduling, or long-term scheduling**, mainly decides, by some algorithm, which jobs in the backlog queue on external storage to load into memory. It happens when one batch of jobs finishes and a new batch is loaded, so it runs infrequently. Batch systems need job scheduling; **time-sharing and real-time systems do not**. It is mainly used in batch systems. Its design goal is to maximize resource utilization and keep the various activities in the system fully parallel.

> [!example] Mixing jobs with different resource demands sensibly
>
> - Scientific computing is CPU-bound: it mainly relies on processor computation and needs little I/O.
> - Data processing is mostly I/O-bound: its computation logic is relatively simple (little CPU time), but it reads and writes data frequently.
> - Some recursive computations are memory-bound: they produce many intermediate results and need substantial memory to store them.
>
> If these jobs are scheduled together sensibly — CPU-bound jobs use the processor while I/O-bound jobs read and write data and memory-bound jobs work on in-memory data — their competition for the same resource is staggered in time, raising resource utilization and throughput.

##### Scheduling Metrics

> Degree of Multiprogramming: how many jobs are allowed to run in memory at the same time.
> Turnaround Time: the interval from when a job is submitted to the system until it completes, also called job turnaround time.
> Weighted Turnaround Time: the ratio of a job's turnaround time T to the service time TS the system provides it, $WTT=\frac{T_{\text{turnaround}}}{T_{\text{estimated run time}}}$
> Response Ratio: $RR=\frac{T_{\text{waiting}} + T_{\text{estimated run time}}}{T_{\text{estimated run time}}}=\frac{T_{\text{response}}}{T_{\text{estimated run time}}}$, note that `RR>=1`

#### Low-Level Scheduling

**Low-level scheduling is also called process scheduling or short-term scheduling**; it schedules processes. All three types of OS must have this level (the most basic scheduling). Low-level scheduling decides which process in the ready queue gets the processor, and then the **dispatcher** carries out the concrete operation of assigning the processor to that process. Its time scale is usually milliseconds, and it is the most frequent scheduling in the system, so it must be highly efficient.

**Basic mechanisms of low-level scheduling**

1. **Queuer**: to make process scheduling efficient, all ready processes in the system are arranged in advance into one or more queues in some order.
2. **Dispatcher**: the dispatcher removes the process selected by the scheduler from the ready queue, performs a context switch, and assigns the processor to it.
3. **Context switch mechanism**: when the processor is switched, two pairs of context switch operations occur.

**Functions of low-level scheduling**

1. Select a process by some algorithm (scheduling).
2. Save the processor's state information (first step of the context switch).
3. Restore the new process's CPU state, thereby assigning the processor to the new process (second step of the context switch).

#### Intermediate-Level Scheduling

Intermediate-level scheduling is also called medium-term scheduling.
Main purpose: to improve memory utilization and system throughput.
How it works:

- Processes that temporarily cannot run stop occupying precious memory and are moved out to swap space on external storage to wait; the process state at this point is called ready-on-disk or suspended.
- When these processes become runnable again and memory has some room, intermediate-level scheduling decides which ready processes on external storage to bring back into memory, changes their state to ready, and puts them on the ready queue to wait for process scheduling.

## Scheduling Model

All three levels of scheduling involve process queues, which gives three scheduling queue models:

- Process scheduling only (low-level scheduling)
- High-level plus low-level scheduling
- All three levels of scheduling

### Process Scheduling Only

Time-sharing systems usually have only process scheduling. The system organizes processes into one ready queue, and while executing, a process may be in one of these situations:

- The process holds the CPU and is executing.
- The task finishes within the given time slice and, after releasing the processor, is in the completed state.
- The task does not finish within the time slice and goes to the end of the ready queue.
- It blocks during execution because of some event.
  ![Scheduling queue model with process scheduling only (time-sharing system)](https://assets.vluv.space/UESTC/OS/Ch3-1TheProcessorScheduling/Ch3-1TheProcessorScheduling-2024-03-31-18-02-37.webp)

### High-Level and Low-Level Scheduling

Batch systems need not only process scheduling but also job scheduling.
Form of the ready queue: batch systems commonly use a priority queue. When a process enters the ready queue, it is inserted at the position matching its priority, and the scheduler always assigns the processor to the process at the head of the ready queue.
Multiple blocked queues: setting up multiple queues by event type improves efficiency.

![Scheduling queue model with high-level and low-level scheduling](https://assets.vluv.space/UESTC/OS/Ch3-1TheProcessorScheduling/Ch3-1TheProcessorScheduling-2024-03-31-18-04-45.webp)

### Queue Model with All Three Levels of Scheduling

Once intermediate-level scheduling is introduced into the OS, the ready state splits into memory-ready (the process is ready in memory) and disk-ready (the process is ready on external storage). Likewise, the blocked state further splits into memory-blocked and disk-blocked.
Swap-out can move a process from memory-ready to disk-ready, and from memory-blocked to disk-blocked.
Intermediate-level scheduling can move a process from disk-ready back to memory-ready.

![Scheduling queue model with all three levels of scheduling](https://assets.vluv.space/UESTC/OS/Ch3-1TheProcessorScheduling/Ch3-1TheProcessorScheduling-2024-03-31-18-11-01.webp)