A1.3 · Computer fundamentals
A1.3 · 计算机基础
Approaches to Scheduling
调度方式的比较
Hundreds of processes are ready to run and one core can run one at a time. The order the OS picks them in changes how quickly work finishes, how responsive the machine feels, and whether some processes wait forever.
上百个进程就绪待运行,而一个核心一次只能运行一个。操作系统选择它们的顺序,决定了工作完成得多快、机器用起来多灵敏,以及某些进程是否会永远等下去。
Explainer
讲解
What scheduling has to solve
调度要解决什么
Scheduling is the OS function that decides which of the ready processes runs on the CPU next, and for how long, so that CPU time is shared in a way that keeps the whole system performing well.
调度是操作系统的一项功能:它决定下一个由哪个就绪进程使用 CPU、用多久,从而以让整个系统保持良好表现的方式来分享 CPU 时间。
At any moment there may be hundreds of processes ready to run, some urgent, some long, some tiny. The scheduler is judged on a few measures: throughput (jobs finished per second), waiting time, turnaround time, responsiveness for interactive work, and fairness, avoiding starvation where a process never gets the CPU.
任何时刻都可能有上百个进程就绪待运行,有的紧急、有的很长、有的很小。评判调度器的指标有几个:吞吐量(每秒完成的任务数)、等待时间、周转时间、交互工作的响应性,以及公平性,即避免某个进程永远拿不到 CPU 的饥饿现象。
Every switch from one process to another is a context switch: the OS saves the first process’s registers and state and loads the next one’s. This is pure overhead, so an approach that switches very often pays a price.
从一个进程切换到另一个进程,每一次都是一次上下文切换:操作系统保存第一个进程的寄存器和状态,再载入下一个进程的。这纯粹是开销,所以切换非常频繁的方式要付出代价。
Explainer
讲解
The four approaches side by side
四种方式并排比较
| Approach | How it picks | Pre-emptive? | Main weakness |
|---|---|---|---|
| First-come first-served (FCFS) | Runs processes in arrival order, each to completion | No | The convoy effect: one long job delays every shorter job behind it |
| Round robin | Gives each process a fixed time slice (quantum) in turn, then moves it to the back of the queue | Yes | A quantum that is too small wastes time on context switches |
| Priority scheduling | Runs the ready process with the highest priority first | Can be either | Low-priority processes can starve |
| Multilevel queue | Splits the ready queue into several queues by process type, each with its own algorithm and priority | Yes | Complex to tune; lower queues can still starve |
| 方式 | 如何选择 | 是否抢占 | 主要弱点 |
|---|---|---|---|
| 先来先服务(FCFS) | 按到达顺序运行进程,每个都运行到结束 | 否 | 护航效应:一个长任务会拖延排在它后面的每个较短任务 |
| 轮转(round robin) | 轮流给每个进程一个固定的时间片(时间量),然后把它移到队尾 | 是 | 时间片太小会把时间浪费在上下文切换上 |
| 优先级调度 | 先运行优先级最高的就绪进程 | 两者皆可 | 低优先级进程可能饥饿 |
| 多级队列 | 按进程类型把就绪队列分成几个队列,每个队列有自己的算法和优先级 | 是 | 调优复杂;较低的队列仍可能饥饿 |
Explore
探索
How each approach behaves
每种方式的表现
Click each approach to see its mechanism, what it is good at, where it falls down, and the kind of system it suits.
点击每种方式,看看它的机制、擅长什么、在哪里失灵,以及它适合哪类系统。
Check your understanding
检验你的理解
A round robin scheduler is set with a very short time quantum. What is the most likely effect?
一个轮转调度器被设成了很短的时间片。最可能的后果是什么?
Common mistake
常见错误
RecurringTwo problems recur. First, answers describe each algorithm in a separate paragraph and never compare them: compare means put them against shared criteria (fairness, responsiveness, overhead, starvation) and say how they differ, ideally with a judgement about which suits a given system. Second, round robin and FCFS get confused: FCFS runs each job to completion in arrival order (non-pre-emptive); round robin interrupts each job after a fixed slice and cycles round (pre-emptive).
反复出现有两个问题反复出现。第一,答案用一段分别描述每个算法,却从不加以比较:比较意味着把它们放在共同的标准下(公平性、响应性、开销、饥饿),说明它们有何不同,最好还给出哪种适合某个系统的判断。第二,轮转和 FCFS 被搞混了:FCFS 按到达顺序把每个任务运行到结束(非抢占);轮转在固定的一片时间后打断每个任务并循环轮流(抢占)。
Two descriptions, no comparison: “FCFS runs jobs in the order they arrive. Round robin gives each job a time slice. Priority scheduling runs the most important job first.” Three facts, but nothing set against anything.
两段描述,没有比较: “FCFS 按到达顺序运行任务。轮转给每个任务一片时间。优先级调度先运行最重要的任务。”三个事实,却没有任何对比。
A real comparison: “FCFS and round robin both treat jobs equally, but FCFS is non-pre-emptive so a long job blocks short ones behind it (the convoy effect), while round robin pre-empts after a fixed slice so short interactive jobs stay responsive, at the cost of context-switch overhead. Priority scheduling beats both for urgent work but, unlike round robin, can starve low-priority jobs unless ageing is used.”
一次真正的比较: “FCFS 和轮转都平等对待任务,但 FCFS 非抢占,所以一个长任务会挡住排在它后面的短任务(护航效应),而轮转在固定一片时间后抢占,使短小的交互任务保持响应,代价是上下文切换的开销。优先级调度在处理紧急工作上胜过两者,但与轮转不同,除非采用老化机制,否则可能饿死低优先级任务。”
Revision questions
复习题
Specimen-paper style. Write an answer, then reveal the marking points and mark yourself.
采用样卷风格。写下答案,然后展开评分要点给自己打分。
[6]Compare first-come first-served and round robin scheduling.
[6]比较先来先服务调度与轮转调度。
Marking points
评分要点
- FCFS: non-pre-emptive, runs each job to completion in arrival order; round robin: pre-emptive, each job gets a fixed time slice then goes to the back of the queue.
- FCFS can suffer the convoy effect (a long job delays short jobs behind it); round robin keeps short interactive jobs responsive.
- Round robin adds context-switch overhead; FCFS has almost none.
- Both are fair in a sense: FCFS by arrival order, round robin by equal time share.
- FCFS:非抢占,按到达顺序把每个任务运行到结束;轮转:抢占,每个任务得到固定时间片后到队尾。
- FCFS 会有护航效应(长任务拖延后面的短任务);轮转让短小的交互任务保持响应。
- 轮转增加上下文切换开销;FCFS 几乎没有。
- 两者在某种意义上都公平:FCFS 按到达顺序,轮转按等时分享。
[4]Compare priority scheduling and multilevel queue scheduling.
[4]比较优先级调度与多级队列调度。
Marking points
评分要点
- Priority: runs the highest-priority ready process first; multilevel queue: splits the ready queue into several queues by process type, each with its own algorithm/priority.
- Both can starve low-priority work; multilevel queue can also starve its lower queues.
- Priority needs ageing to be safe; multilevel queue lets different job types be handled appropriately but is complex to tune.
- 优先级:先运行优先级最高的就绪进程;多级队列:按进程类型把就绪队列分成几个队列,每个有自己的算法 / 优先级。
- 两者都可能饿死低优先级工作;多级队列还可能饿死它较低的队列。
- 优先级需要老化机制才安全;多级队列能恰当处理不同类型的任务,但调优复杂。
[6]Compare the four scheduling approaches in terms of fairness and the risk of starvation.
[6]就公平性和饥饿风险,比较这四种调度方式。
Marking points
评分要点
- FCFS: fair by arrival order, but a process arriving during a long job effectively waits (near-starvation via the convoy effect).
- Round robin: designed to be fair, equal time slices, so no starvation.
- Priority: risks starvation of low-priority processes unless ageing raises their priority over time.
- Multilevel queue: inherently prioritises some queues, so lower queues can starve if higher ones stay busy.
- FCFS:按到达顺序公平,但在长任务期间到达的进程实际上要一直等(护航效应造成近似饥饿)。
- 轮转:设计上公平,等时片,所以不会饥饿。
- 优先级:低优先级进程有饥饿风险,除非老化机制随时间提高它们的优先级。
- 多级队列:本质上偏向某些队列,所以若较高队列一直忙,较低队列会饥饿。
[4]Explain how the choice of time quantum affects the behaviour of round robin scheduling.
[4]解释时间片的选择如何影响轮转调度的表现。
Marking points
评分要点
- A quantum that is too short means a context switch happens very often; the fixed cost of switching becomes a large share of CPU time, lowering throughput.
- A quantum that is too long means a process rarely gets pre-empted, so round robin starts to behave like FCFS and loses its responsiveness.
- The quantum has to balance responsiveness against switching overhead.
- 时间片太短意味着上下文切换非常频繁;切换的固定成本占了 CPU 时间的很大一部分,降低吞吐量。
- 时间片太长意味着进程很少被抢占,于是轮转开始表现得像 FCFS,失去响应性。
- 时间片必须在响应性与切换开销之间取得平衡。
[3]Explain how context switching creates overhead in a scheduler that switches processes frequently.
[3]解释在频繁切换进程的调度器中,上下文切换如何造成开销。
Marking points
评分要点
- A context switch saves the running process's registers and state and loads the next process's.
- This work produces no useful output; it is pure overhead.
- The more often the scheduler switches, the larger the fraction of CPU time spent on overhead rather than running programs.
- 上下文切换保存正在运行进程的寄存器和状态,并载入下一个进程的。
- 这项工作不产生任何有用的输出;它纯属开销。
- 调度器切换得越频繁,花在开销上而非运行程序上的 CPU 时间占比就越大。
Flashcards
记忆卡片
Active recall for this statement’s key terms.
针对本条考纲陈述关键术语的主动回忆练习。
Keep this statement’s practice with you
把这条考纲陈述的练习保存下来
Free account: save your progress and unlock every revision question for A1.3.3, and every other IB CS 2027 statement.
免费账户:解锁 A1.3.3 以及所有其他 IB CS 2027 考纲陈述的每一道复习题,并同步你的学习进度。