Chapter 2 2.5 Scheduling

本讲内容：调度算法

以下是关于调度算法的详细讲解，包括基本调度算法、交互式系统调度算法以及一些高级调度策略。

1. 什么是调度？

What is Scheduling?

• 定义：
Definition:
• 调度是操作系统决定哪个进程/线程获得CPU时间的过程。
Scheduling is the process by which the operating system decides which process/thread gets CPU time.

• 目标：
Goals:
• 提高CPU利用率，减少等待时间，确保公平性，满足实时需求等。
Improve CPU utilization, reduce waiting time, ensure fairness, meet real-time requirements, etc.

2. 何时调度？

When to Schedule?

调度可能在以下情况下发生：
Scheduling may occur in the following situations:

  1. 进程创建或终止时。
    When a process is created or terminated.
  2. 进程从运行状态切换到等待状态时。
    When a process switches from the running state to the waiting state.
  3. 进程从等待状态切换到就绪状态时。
    When a process switches from the waiting state to the ready state.
  4. 中断发生时。
    When an interrupt occurs.

3. 基本调度算法

Basic Scheduling Algorithms

批处理系统（Batch Systems）

  1. 先来先服务（First-Come First-Served, FCFS）：
    First-Come First-Served (FCFS):
    • 按照进程到达的顺序分配CPU时间。
    Allocate CPU time in the order processes arrive.
    • 优点： 简单易实现。
    Advantage: Simple and easy to implement.
    • 缺点： 可能导致“护航效应”，长任务阻塞短任务。
    Disadvantage: May lead to the "convoy effect," where long tasks block short tasks.

  2. 最短作业优先（Shortest Job First, SJF）：
    Shortest Job First (SJF):
    • 优先调度运行时间最短的进程。
    Schedule the process with the shortest running time first.
    • 优点： 最小化平均等待时间。
    Advantage: Minimizes the average waiting time.
    • 缺点： 需要预先知道作业的运行时间，可能导致长作业饥饿。
    Disadvantage: Requires prior knowledge of job running times and may cause starvation of long jobs.

交互式系统（Interactive Systems）

  1. 轮转调度（Round-Robin, RR）：
    Round-Robin (RR):
    • 每个进程分配一个固定时间片（quantum），时间片用完后切换到下一个进程。
    Each process is allocated a fixed time slice (quantum), and after the time slice is used up, switch to the next process.
    • 优点： 公平，响应时间短。
    Advantage: Fair and provides short response times.
    • 缺点： 时间片大小选择不当可能影响性能。
    Disadvantage: Poor choice of time slice size may affect performance.

  2. 优先级调度（Priority Scheduling）：
    Priority Scheduling:
    • 为每个进程分配一个优先级，优先调度高优先级进程。
    Assign a priority to each process and schedule high-priority processes first.
    • 优点： 灵活，可以满足不同需求。
    Advantage: Flexible and can meet different needs.
    • 缺点： 可能导致低优先级进程饥饿。
    Disadvantage: May cause starvation of low-priority processes.

  3. 多级队列调度（Multi-Queue Scheduling）：
    Multi-Queue Scheduling:
    • 将进程分为多个队列，每个队列采用不同的调度算法。
    Divide processes into multiple queues, each using a different scheduling algorithm.
    • 优点： 灵活，适应不同类型的进程。
    Advantage: Flexible and adapts to different types of processes.
    • 缺点： 实现复杂，可能导致队列间的不公平。
    Disadvantage: Complex to implement and may cause unfairness between queues.

  4. 多级反馈队列调度（Multi-Level Feedback Queue, MLFQ）：
    Multi-Level Feedback Queue (MLFQ):
    • 结合多级队列和优先级调度，动态调整进程的优先级和队列。
    Combines multi-queue and priority scheduling, dynamically adjusting process priorities and queues.
    • 优点： 适应性强，能有效处理不同类型的进程。
    Advantage: Highly adaptable and effectively handles different types of processes.Disadvantage: Complex to implement and may cause unfairness between queues.

  5. 多级反馈队列调度（Multi-Level Feedback Queue, MLFQ）：
    Multi-Level Feedback Queue (MLFQ):
    • 结合多级队列和优先级调度，动态调整进程的优先级和队列。
    Combines multi-queue and priority scheduling, dynamically adjusting process priorities and queues.
    • 优点： 适应性强，能有效处理不同类型的进程。
    Advantage: Highly adaptable and effectively handles different types of processes.
    • 缺点： 实现复杂，可能导致低优先级进程饥饿。
    Disadvantage: Complex to implement and may cause starvation of low-priority processes.

4. 高级调度策略

Advanced Scheduling Policies

  1. 保证调度（Guaranteed Scheduling）：
    Guaranteed Scheduling:
    • 确保每个进程获得一定比例的CPU时间。
    Ensure that each process gets a certain proportion of CPU time.
    • 优点： 公平，避免进程饥饿。
    Advantage: Fair and prevents process starvation.
    • 缺点： 实现复杂，可能影响系统性能。
    Disadvantage: Complex to implement and may affect system performance.

  2. 彩票调度（Lottery Scheduling）：
    Lottery Scheduling:
    • 为每个进程分配“彩票”，根据彩票数量决定调度概率。
    Assign "lottery tickets" to each process and determine scheduling probability based on the number of tickets.
    • 优点： 简单，公平，适应性强。
    Advantage: Simple, fair, and highly adaptable.
    • 缺点： 可能无法精确控制资源分配。
    Disadvantage: May not precisely control resource allocation.

  3. 公平共享调度（Fair Share Scheduling）：
    Fair Share Scheduling:
    • 根据用户或组的资源配额分配CPU时间。
    Allocate CPU time based on resource quotas for users or groups.
    • 优点： 公平，避免资源被少数用户独占。
    Advantage: Fair and prevents resources from being monopolized by a few users.
    • 缺点： 实现复杂，可能影响系统性能。
    Disadvantage: Complex to implement and may affect system performance.

5. 总结

Summary

• 调度是操作系统决定进程/线程获得CPU时间的过程，目标是提高CPU利用率、减少等待时间、确保公平性等。
Scheduling is the process by which the operating system decides which process/thread gets CPU time, with goals such as improving CPU utilization, reducing waiting time, and ensuring fairness.

• 基本调度算法包括先来先服务、最短作业优先、轮转调度、优先级调度、多级队列调度和多级反馈队列调度。
Basic scheduling algorithms include First-Come First-Served, Shortest Job First, Round-Robin, Priority Scheduling, Multi-Queue Scheduling, and Multi-Level Feedback Queue Scheduling.

• 高级调度策略包括保证调度、彩票调度和公平共享调度，用于满足更复杂的调度需求。
Advanced scheduling policies include Guaranteed Scheduling, Lottery Scheduling, and Fair Share Scheduling, used to meet more complex scheduling needs.

通过理解这些调度算法和策略，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding these scheduling algorithms and policies, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

调度与进程行为

以下是关于调度和进程行为的详细讲解，帮助你理解操作系统如何决定进程的执行顺序以及进程的行为模式。

1. 什么是调度？

What is Scheduling?

• 定义：
Definition:
• 调度是决定哪个进程/线程接下来占用资源（如CPU）运行的过程。
Scheduling is the process of deciding which process/thread should occupy the resource (e.g., CPU) to run next.

• 类比：
Analogy:
• 将CPU比作“马力”，多个进程（如马匹）争夺使用CPU的机会。
Think of the CPU as "horsepower," with multiple processes (horses) competing for the chance to use it.

2. 进程调度器

Process Scheduler

• 调度器的任务：
Task of the Scheduler:
• 从就绪队列中选择一个进程，分配CPU时间。
Select a process from the ready queue and allocate CPU time.

• 调度示例：
Scheduling Example:
• Proc1需要20个时间单位，Proc2需要4个时间单位，Proc3需要2个时间单位。
Proc1 needs 20 time units, Proc2 needs 4 time units, Proc3 needs 2 time units.

• 抢占式与非抢占式调度：
Preemptive vs. Non-Preemptive Scheduling:
• 抢占式调度： 允许操作系统中断正在运行的进程，将CPU分配给其他进程。
Preemptive Scheduling: Allows the operating system to interrupt a running process and allocate the CPU to another process.
• 非抢占式调度： 进程运行直到完成或主动放弃CPU。
Non-Preemptive Scheduling: The process runs until it completes or voluntarily gives up the CPU.

3. 进程行为

Process Behavior

• 进程的组成：
Composition of Processes:
• 进程通常由CPU突发和I/O突发交替组成。
Processes typically consist of alternating CPU bursts and I/O bursts.

CPU突发（CPU Bursts）

• 定义：
Definition:
• 进程需要CPU的时间段称为CPU突发。
A period of time when a process needs the CPU is called a CPU burst.

I/O突发（I/O Bursts）

• 定义：
Definition:
• 进程需要I/O的时间段称为I/O突发。
A period of time when a process needs I/O is called an I/O burst.

4. 进程行为的类型

Types of Process Behavior

  1. CPU密集型进程（CPU-bound Process）：
    CPU-bound Process:
    • 特点： CPU突发时间长，I/O等待时间少。
    Characteristics: Long CPU bursts, infrequent I/O waits.
    • 示例： 数值计算任务、图像处理。
    Examples: Number crunching tasks, image processing.

  2. I/O密集型进程（I/O-bound Process）：
    I/O-bound Process:
    • 特点： CPU突发时间短，I/O等待时间多。
    Characteristics: Short CPU bursts, frequent I/O waits.
    • 示例： 从磁盘读取数据的任务，例如统计文件行数。
    Examples: Tasks that process data from disk, such as counting the number of lines in a file.

5. CPU与I/O突发的交替

Alternating Sequence of CPU and I/O Bursts

• 进程行为的模式：
Pattern of Process Behavior:
• CPU使用和I/O等待交替进行。
Bursts of CPU usage alternate with periods of I/O wait.

• 示例：
Examples:
1. CPU密集型进程：
CPU-bound Process:
◦ CPU突发时间长，I/O等待时间少。
Long CPU bursts, infrequent I/O waits.
2. I/O密集型进程：
I/O-bound Process:
◦ CPU突发时间短，I/O等待时间多。
Short CPU bursts, frequent I/O waits.

6. 进程行为的变化趋势

Trends in Process Behavior

• 随着CPU速度的提升：
As CPUs get faster:
• 进程趋向于更加I/O密集型。
Processes tend to become more I/O-bound.

总结

Summary

• 调度是决定哪个进程/线程接下来占用CPU运行的过程，分为抢占式和非抢占式调度。
Scheduling is the process of deciding which process/thread should occupy the CPU to run next, divided into preemptive and non-preemptive scheduling.

• 进程行为由CPU突发和I/O突发交替组成，分为CPU密集型进程和I/O密集型进程。
Process behavior consists of alternating CPU bursts and I/O bursts, divided into CPU-bound processes and I/O-bound processes.

• 随着CPU速度的提升，进程趋向于更加I/O密集型。
As CPUs get faster, processes tend to become more I/O-bound.

通过理解调度和进程行为，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding scheduling and process behavior, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

CPU调度

以下是关于CPU调度的详细讲解，包括调度时机、抢占式与非抢占式调度以及调度算法的分类。

1. CPU调度的问题

CPU Scheduling Problems

  1. 何时调度（When）：
    When to Schedule:
    • 在什么情况下进行调度？
    Under what circumstances should scheduling occur?

  2. 调度什么（What）：
    What to Schedule:
    • 使用什么调度算法？
    What scheduling algorithm should be used?

  3. 如何调度（How）：
    How to Schedule:
    • 如何进行上下文切换？
    How to perform context switching?

2. 调度时机

When to Schedule?

调度可能在以下情况下发生：
Scheduling may occur in the following situations:

  1. 新进程创建时。
    When a new process is created.
  2. 运行中的进程退出时。
    When the running process exits.
  3. 运行中的进程被阻塞时。
    When the running process is blocked.
  4. 发生I/O中断时（某些进程将变为就绪状态）。
    When an I/O interrupt occurs (some processes will become ready).
  5. 发生时钟中断时（例如每10毫秒）。
    When a clock interrupt occurs (e.g., every 10 milliseconds).

3. 抢占式与非抢占式调度

Preemptive vs. Non-Preemptive Scheduling

非抢占式调度（Non-Preemptive Scheduling）

• 定义：
Definition:
• 运行中的进程保持CPU直到它自愿放弃CPU。
The running process keeps the CPU until it voluntarily gives up the CPU.

• 放弃CPU的情况：
Situations where the CPU is released:
1. 进程退出。
The process exits.
2. 进程切换到阻塞状态。
The process switches to the blocked state.

• 缺点：
Disadvantage:
• 可能导致响应时间过长，影响系统性能。
May lead to long response times, affecting system performance.

抢占式调度（Preemptive Scheduling）

• 定义：
Definition:
• 运行中的进程可以被中断，必须释放CPU（可能被强制放弃CPU）。
The running process can be interrupted and must release the CPU (may be forced to give up the CPU).

• 抢占原则：
Preemptive Principles:
1. 更高优先级的进程变为就绪状态。
A higher-priority process becomes ready.
2. 时间片用完（例如轮转调度）。
The time slice is used up (e.g., Round-Robin Scheduling).
3. 发生中断（如I/O中断或时钟中断）。
An interrupt occurs (e.g., I/O interrupt or clock interrupt).

4. 调度算法的分类

Categories of Scheduling Algorithms

批处理系统（Batch System）

• 特点：
Characteristics:
• 非抢占式算法或抢占式算法，但每个进程的时间片较长。
Non-preemptive algorithms or preemptive algorithms with long time periods for each process.

• 目标：
Goal:
• 最大化吞吐量，最小化平均等待时间。
Maximize throughput and minimize average waiting time.

交互式系统（Interactive System）

• 特点：
Characteristics:
• 抢占式调度是必需的。
Preemption is essential.

• 目标：
Goal:
• 最小化响应时间，提高用户体验。
Minimize response time and improve user experience.

实时系统（Real-Time System）

• 特点：
Characteristics:
• 抢占式调度有时不需要。
Preemption is sometimes not needed.

• 目标：
Goal:
• 确保任务在截止时间内完成。
Ensure tasks are completed within deadlines.

总结

Summary

• CPU调度解决的问题包括何时调度、使用什么调度算法以及如何进行上下文切换。
CPU scheduling problems include when to schedule, what scheduling algorithm to use, and how to perform context switching.

• 调度时机包括新进程创建、进程退出、进程阻塞、I/O中断和时钟中断。
Scheduling opportunities include new process creation, process exit, process blocking, I/O interrupts, and clock interrupts.

• 抢占式调度允许操作系统中断正在运行的进程，而非抢占式调度则要求进程自愿放弃CPU。
Preemptive scheduling allows the operating system to interrupt a running process, while non-preemptive scheduling requires the process to voluntarily give up the CPU.

• 调度算法分为批处理系统、交互式系统和实时系统，每种系统有不同的调度需求和目标。
Scheduling algorithms are divided into batch systems, interactive systems, and real-time systems, each with different scheduling needs and goals.

通过理解CPU调度的原理和分类，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding the principles and categories of CPU scheduling, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

调度算法与性能指标

以下是关于调度算法的设计目标以及不同系统性能指标的详细讲解。

1. 调度算法的设计目标

Goals of Scheduling Algorithms

  1. 公平性（Fairness）：
    Fairness:
    • 确保所有进程都能获得CPU时间，避免饥饿。
    Ensure all processes get CPU time and avoid starvation.

  2. 优先级（Priority）：
    Priority:
    • 高优先级进程优先获得CPU时间。
    High-priority processes get CPU time first.

  3. 效率（Efficiency）：
    Efficiency:
    • 最大化资源利用率，减少空闲时间。
    Maximize resource utilization and reduce idle time.

  4. 鼓励良好行为（Encourage Good Behavior）：
    Encourage Good Behavior:
    • 奖励短任务或I/O密集型任务，优化系统性能。
    Reward short tasks or I/O-bound tasks to optimize system performance.

  5. 支持高负载（Support Heavy Loads）：
    Support Heavy Loads:
    • 在高负载情况下，系统性能应平稳下降。
    System performance should degrade gracefully under heavy loads.

  6. 适应不同环境（Adapt to Different Environments）：
    Adapt to Different Environments:
    • 调度算法应适应交互式、实时等不同系统环境。
    Scheduling algorithms should adapt to different system environments, such as interactive and real-time systems.

2. 性能指标

Performance Criteria

所有系统的共同指标

Common Criteria for All Systems

  1. 公平性（Fairness）：
    Fairness:
    • 确保没有进程会因长时间等待而饥饿。
    Ensure no process suffers from starvation due to long waiting times.

  2. 效率（Efficiency）：
    Efficiency:
    • 尽可能保持资源忙碌，减少空闲时间。
    Keep resources as busy as possible and reduce idle time.

  3. 策略执行（Policy Enforcement）：
    Policy Enforcement:
    • 确保调度算法能够执行既定的策略。
    Ensure that the scheduling algorithm carries out the stated policy.

批处理系统的性能指标

Performance Criteria for Batch Systems

  1. 吞吐量（Throughput）：
    Throughput:
    • 单位时间内完成的进程数量。
    Number of processes that complete in a unit of time.

  2. 周转时间（Turnaround Time）：
    Turnaround Time:
    • 从进程进入系统到完成执行的总时间。
    Amount of time to execute a particular process from the time it enters the system.

  3. 等待时间（Waiting Time）：
    Waiting Time:
    • 进程在就绪队列中等待的总时间。
    Amount of time a process has been waiting in the ready queue.

  4. CPU利用率（Processor Utilization）：
    Processor Utilization:
    • CPU忙碌时间的百分比。
    Percentage of time the CPU is busy.

交互式系统的性能指标

Performance Criteria for Interactive Systems

  1. 响应时间（Response Time）：
    Response Time:
    • 从提交请求到产生第一个响应的时间。
    Amount of time from when a request is first submitted until the first response is produced.

  2. 比例性（Proportionality）：
    Proportionality:
    • 满足用户的期望，例如短任务应快速完成。
    Meet users' expectations, such as short tasks should be completed quickly.

实时系统的性能指标

Performance Criteria for Real-Time Systems

  1. 满足截止时间（Meeting Deadlines）：
    Meeting Deadlines:
    • 确保任务在截止时间内完成，避免数据丢失。
    Ensure tasks are completed within deadlines to avoid data loss.

  2. 可预测性（Predictability）：
    Predictability:
    • 无论系统负载如何，任务的处理时间和成本应保持一致。
    The time and cost of processing tasks should remain consistent regardless of the system load.

总结

Summary

• 调度算法的设计目标包括公平性、优先级、效率、鼓励良好行为、支持高负载和适应不同环境。
The goals of scheduling algorithms include fairness, priority, efficiency, encouraging good behavior, supporting heavy loads, and adapting to different environments.

• 所有系统的共同性能指标包括公平性、效率和策略执行。
Common performance criteria for all systems include fairness, efficiency, and policy enforcement.

• 批处理系统的性能指标包括吞吐量、周转时间、等待时间和CPU利用率。
Performance criteria for batch systems include throughput, turnaround time, waiting time, and processor utilization.

• 交互式系统的性能指标包括响应时间和比例性。
Performance criteria for interactive systems include response time and proportionality.

• 实时系统的性能指标包括满足截止时间和可预测性。
Performance criteria for real-time systems include meeting deadlines and predictability.

通过理解调度算法的设计目标和性能指标，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding the goals of scheduling algorithms and performance criteria, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

单处理器调度算法

以下是关于单处理器调度算法的详细讲解，包括批处理系统和交互式系统的调度算法。

1. 批处理系统的调度算法

Scheduling Algorithms for Batch Systems

先来先服务（First Come First Served, FCFS）

• 定义：
Definition:
• 最先请求CPU的进程最先获得CPU。
The process that requests the CPU first is allocated the CPU first.

• 特点：
Characteristics:
• 非抢占式调度算法。
Non-preemptive scheduling algorithm.
• 用于批处理系统。
Used in batch systems.
• 实现：使用FIFO队列。
Implementation: FIFO queues.
◦ 新进程进入队列尾部。
A new process enters the tail of the queue.
◦ 调度器从队列头部选择进程。
The scheduler selects from the head of the queue.

• 性能指标：
Performance Metric:
• 平均等待时间（Average Waiting Time）。
Average Waiting Time.

FCFS示例

• 进程参数：
Process Parameters:
| 进程 | 持续时间（ms） | 顺序 | 到达时间 | | ---- | -------------- | ---- | -------- | | P1 | 24 | 1 | 0 | | P2 | 3 | 2 | 0 | | P3 | 4 | 3 | 0 |

• 调度结果：
Schedule:

1
2
0──────24──────27──────31
P1 (24) P2 (3)  P3 (4)

• 等待时间：
Waiting Time:
• P1: 0
• P2: 24
• P3: 27

• 平均等待时间：
Average Waiting Time:
• (0 + 24 + 27) / 3 = 17

FCFS的护航效应（Convoy Effect）

• 问题描述：
Problem Description:
• 如果短进程排在长进程后面，会导致短进程长时间等待，降低系统性能。
If short processes are behind long processes, it leads to long waiting times for short processes, reducing system performance.

• 示例：
Example:
• 如果进程到达顺序为P2、P3、P1：
If the processes arrive in the order P2, P3, P1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
    0────3────7────31
    P2 (3) P3 (4) P1 (24)
    ```  
  • 等待时间：  
    **Waiting Time:**  
    ◦ P1: 7  
    ◦ P2: 0  
    ◦ P3: 3  
  • 平均等待时间：  
    **Average Waiting Time:**  
    ◦ (7 + 0 + 3) / 3 = 3.3

• **护航效应的原因：**  

> 注意护航效应！

  **Reason for Convoy Effect:**  
  • CPU密集型进程占用CPU时间过长，导致I/O密集型进程无法及时获得CPU，I/O设备空闲。  
    **CPU-bound processes occupy the CPU for too long, causing I/O-bound processes to wait and I/O devices to idle.**

---

#### **2. 交互式系统的调度算法**  
**Scheduling Algorithms for Interactive Systems**

---

##### **轮转调度（Round Robin, RR）**

• **定义：**  
  **Definition:**  
  • 每个进程分配一个固定时间片，时间片用完后切换到下一个进程。  
    **Each process is allocated a fixed time slice, and after the time slice is used up, switch to the next process.**

• **特点：**  
  **Characteristics:**  
  • 抢占式调度算法。  
    **Preemptive scheduling algorithm.**  
  • 用于交互式系统。  
    **Used in interactive systems.**

---

##### **优先级调度（Priority Scheduling）**

• **定义：**  
  **Definition:**  
  • 为每个进程分配一个优先级，优先调度高优先级进程。  
    **Assign a priority to each process and schedule high-priority processes first.**

• **特点：**  
  **Characteristics:**  
  • 可能导致低优先级进程饥饿。  
    **May cause starvation of low-priority processes.**

---

##### **多级队列调度（Multi-Queue Scheduling）**

• **定义：**  
  **Definition:**  
  • 将进程分为多个队列，每个队列采用不同的调度算法。  
    **Divide processes into multiple queues, each using a different scheduling algorithm.**

• **特点：**  
  **Characteristics:**  
  • 灵活，适应不同类型的进程。  
    **Flexible and adapts to different types of processes.**

---

##### **多级反馈队列调度（Multi-Level Feedback Queue, MLFQ）**

• **定义：**  
  **Definition:**  
  • 结合多级队列和优先级调度，动态调整进程的优先级和队列。  
    **Combines multi-queue and priority scheduling, dynamically adjusting process priorities and queues.**

• **特点：**  
  **Characteristics:**  
  • 适应性强，能有效处理不同类型的进程。  
    **Highly adaptable and effectively handles different types of processes.**

---

##### **保证调度（Guaranteed Scheduling）**

• **定义：**  
  **Definition:**  
  • 确保每个进程获得一定比例的CPU时间。  
    **Ensure that each process gets a certain proportion of CPU time.**

• **特点：**  
  **Characteristics:**  
  • 公平，避免进程饥饿。  
    **Fair and prevents process starvation.**

---

##### **彩票调度（Lottery Scheduling）**

• **定义：**  
  **Definition:**  
  • 为每个进程分配“彩票”，根据彩票数量决定调度概率。  
    **Assign "lottery tickets" to each process and determine scheduling probability based on the number of tickets.**

• **特点：**  
  **Characteristics:**  
  • 简单，公平，适应性强。  
    **Simple, fair, and highly adaptable.**

---

##### **公平共享调度（Fair Share Scheduling）**

• **定义：**  
  **Definition:**  
  • 根据用户或组的资源配额分配CPU时间。  
    **Allocate CPU time based on resource quotas for users or groups.**

• **特点：**  
  **Characteristics:**  
  • 公平，避免资源被少数用户独占。  
    **Fair and prevents resources from being monopolized by a few users.**

---

### **总结**  
**Summary**

• **批处理系统的调度算法包括先来先服务（FCFS）和最短作业优先（SJF）。**  
  **Scheduling algorithms for batch systems include First Come First Served (FCFS) and Shortest Job First (SJF).**

• **交互式系统的调度算法包括轮转调度（RR）、优先级调度、多级队列调度、多级反馈队列调度、保证调度、彩票调度和公平共享调度。**  
  **Scheduling algorithms for interactive systems include Round Robin (RR), Priority Scheduling, Multi-Queue Scheduling, Multi-Level Feedback Queue (MLFQ), Guaranteed Scheduling, Lottery Scheduling, and Fair Share Scheduling.**

• **先来先服务（FCFS）可能导致护航效应，降低系统性能。**  
  **First Come First Served (FCFS) may lead to the convoy effect, reducing system performance.**

通过理解这些调度算法，可以更好地设计和实现操作系统中的调度机制，优化系统性能。  
**By understanding these scheduling algorithms, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.**

---

### **最短作业优先（Shortest Job First, SJF）**

以下是关于最短作业优先（SJF）调度算法的详细讲解，包括非抢占式和抢占式SJF，以及其优缺点。

---

#### **1. 最短作业优先（SJF）的定义**  
**Definition of Shortest Job First (SJF)**

• **定义：**  
  **Definition:**  
  • 优先调度运行时间最短的作业。  
    **Schedule the job with the shortest elapsed time first.**

• **应用场景：**  
  **Application:**  
  • 批处理系统。  
    **Batch systems.**

• **类型：**  
  **Types:**  
  1. **非抢占式SJF：** 进程运行直到完成。  
     **Non-preemptive SJF:** The process runs until it completes.  
  2. **抢占式SJF（最短剩余时间优先，SRTF）：** 优先调度剩余时间最短的进程。  
     **Preemptive SJF (Shortest Remaining Time First, SRTF):** Schedule the job with the shortest remaining time required to complete.

• **要求：**  
  **Requirement:**  
  • 需要预先知道作业的运行时间。  
    **The elapsed time needs to be known in advance.**

---

#### **2. 非抢占式SJF示例**  
**Example of Non-Preemptive SJF**

• **进程参数：**  
  **Process Parameters:**  
| 进程 | 持续时间（ms） | 顺序 | 到达时间 |
| ---- | -------------- | ---- | -------- |
| P1   | 6              | 2    | 0        |
| P2   | 8              | 4    | 0        |
| P3   | 7              | 3    | 0        |
| P4   | 3              | 1    | 0        |

• **调度结果：**  
  **Schedule:**
0────3────9────16────24 P4 (3) P1 (6) P3 (7) P2 (8) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• **等待时间：**  
  **Waiting Time:**  
  • P4: 0  
  • P1: 3  
  • P3: 9  
  • P2: 16  

• **平均等待时间：**  
  **Average Waiting Time (AWT):**  
  • (0 + 3 + 9 + 16) / 4 = 7

---

#### **3. 与FCFS的比较**  
**Comparison with FCFS**

• **FCFS调度结果：**  
  **FCFS Schedule:**
0────6────14────21────24 P1 (6) P3 (7) P2 (8) P4 (3) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

• **等待时间：**  
  **Waiting Time:**  
  • P1: 0  
  • P3: 6  
  • P2: 14  
  • P4: 21  

• **平均等待时间：**  
  **Average Waiting Time (AWT):**  
  • (0 + 6 + 14 + 21) / 4 = 10.25

• **结论：**  
  **Conclusion:**  
  • SJF的平均等待时间（7）优于FCFS（10.25）。  
    **SJF provides a better average waiting time (7) compared to FCFS (10.25).**

---

#### **4. SJF的局限性**  
**Limitations of SJF**

1. **非同时到达的作业：**  
   **Jobs Not Available Simultaneously:**  
   • 如果作业不是同时到达，SJF可能不是最优的。  
     **If jobs do not arrive simultaneously, SJF may not be optimal.**

   • **示例：**  
     **Example:**  
   | 进程 | 持续时间（ms） | 顺序 | 到达时间 |
   | ---- | -------------- | ---- | -------- |
   | P1   | 10             | 1    | 0        |
   | P2   | 2              | 2    | 2        |

     ◦ **调度结果：**  
       **Schedule:**
0────10────12 P1 (10) P2 (2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

◦ **等待时间：**  
  **Waiting Time:**  
  ◦ P1: 0  
  ◦ P2: 8  

◦ **平均等待时间：**  
  **Average Waiting Time (AWT):**  
  ◦ (0 + 8) / 2 = 4

◦ **优化方案：**  
  **Optimization:**  
  ◦ 如果调度器等待2个时间单位：  
    **If the scheduler waits for 2 time units:**
0────2────14 P2 (2) P1 (10) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
       ◦ **等待时间：**  
         **Waiting Time:**  
         ▪ P1: 4  
         ▪ P2: 0  
       ◦ **平均等待时间：**  
         **Average Waiting Time (AWT):**  
         ▪ (0 + 4) / 2 = 2

2. **饥饿问题（Starvation）：**  
   **Starvation:**  
   • 如果有大量短作业不断到达，长作业可能永远无法获得CPU时间。  
     **If a large number of short jobs keep arriving, long jobs may never get CPU time.**

---

#### **5. 抢占式SJF（最短剩余时间优先，SRTF）**  
**Preemptive SJF (Shortest Remaining Time First, SRTF)**

• **定义：**  
  **Definition:**  
  • 优先调度剩余时间最短的进程。  
    **Schedule the job with the shortest remaining time required to complete.**

• **示例：**  
  **Example:**  
| 进程 | 持续时间（ms） | 顺序 | 到达时间 |
| ---- | -------------- | ---- | -------- |
| P1   | 10             | 1    | 0        |
| P2   | 2              | 2    | 2        |

  • **调度结果：**  
    **Schedule:**

0────2────4────12 P1 (2) P2 (2) P1 (8) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

  • **等待时间：**  
    **Waiting Time:**  
    ◦ P1: 2  
    ◦ P2: 0  

  • **平均等待时间：**  
    **Average Waiting Time (AWT):**  
    ◦ (0 + 2) / 2 = 1

---

#### **6. 交互式系统的调度算法**  
**Scheduling Algorithms for Interactive Systems**

• **特点：**  
  **Characteristics:**  
  • 通常是抢占式的。  
    **Usually preemptive.**  
  • 时间被划分为时间片（quantum）。  
    **Time is sliced into quantum (time intervals).**  
  • 每个时间片开始时进行调度决策。  
    **Scheduling decision is made at the beginning of each quantum.**

• **性能指标：**  
  **Performance Criteria:**  
  • 最小化响应时间。  
    **Minimize response time.**  
  • 最佳比例性。  
    **Best proportionality.**

• **代表性算法：**  
  **Representative Algorithms:**  
  • 轮转调度（Round-Robin）。  
  • 基于优先级的调度（Priority-based）。  
  • 多级队列调度和多级反馈队列调度（Multi-Queue & Multi-Level Feedback）。  
  • 保证调度（Guaranteed Scheduling）。  
  • 彩票调度（Lottery Scheduling）。  
  • 公平共享调度（Fair Share Scheduling）。

---

### **总结**  
**Summary**

• **最短作业优先（SJF）优先调度运行时间最短的作业，适用于批处理系统。**  
  **Shortest Job First (SJF) schedules the job with the shortest elapsed time first and is used in batch systems.**

• **SJF分为非抢占式和抢占式（最短剩余时间优先，SRTF）。**  
  **SJF is divided into non-preemptive and preemptive (Shortest Remaining Time First, SRTF).**

• **SJF的最优性依赖于所有作业同时到达的假设，否则可能导致饥饿问题。**  
  **The optimality of SJF depends on the assumption that all jobs arrive simultaneously; otherwise, it may lead to starvation.**

• **交互式系统通常使用抢占式调度算法，如轮转调度和优先级调度。**  
  **Interactive systems usually use preemptive scheduling algorithms, such as Round-Robin and Priority-based scheduling.**

通过理解这些调度算法，可以更好地设计和实现操作系统中的调度机制，优化系统性能。  
**By understanding these scheduling algorithms, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.**

---

### **轮转调度（Round-Robin, RR）**

以下是关于轮转调度（RR）算法的详细讲解，包括其工作原理、示例以及时间片大小的选择。

---

#### **1. 轮转调度的定义**  
**Definition of Round-Robin (RR)**

• **定义：**  
  **Definition:**  
  • 从就绪队列中按顺序选择进程/线程，每个进程分配一个固定时间片（quantum）。  
    **Select processes/threads from the ready queue in a round-robin fashion, allocating a fixed time slice (quantum) to each process.**

• **特点：**  
  **Characteristics:**  
  • 简单、公平、易于实现。  
    **Simple, fair, and easy to implement.**  
  • 不考虑优先级。  
    **Does not consider priority.**  
  • 上下文切换开销较大。  
    **Context switch overhead is significant.**

---

#### **2. 轮转调度的示例**  
**Example of Round-Robin (RR)**

• **进程参数：**  
  **Process Parameters:**  
| 进程 | 持续时间（ms） | 顺序 | 到达时间 |
| ---- | -------------- | ---- | -------- |
| P1   | 3              | 1    | 0        |
| P2   | 4              | 2    | 0        |
| P3   | 3              | 3    | 0        |

• **时间片大小：**  
  **Time Quantum:**  
  • 1个时间单位。  
    **1 unit.**

• **调度结果：**  
  **Schedule:**
0──1──2──3──4──5──6──7──8──9──10 P1 P2 P3 P1 P2 P3 P1 P2 P3 P2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

• **等待时间：**  
  **Waiting Time:**  
  • P1: 4  
  • P2: 6  
  • P3: 6  

• **平均等待时间：**  
  **Average Waiting Time (AWT):**  
  • (4 + 6 + 6) / 3 = 5.33

---

#### **3. 时间片大小的选择**  
**Choosing the Time Quantum**

1. **时间片过大：**  
   **Time Slice Too Large:**  
   • 行为类似于先来先服务（FCFS）。  （考点：一旦时间片太大就和先到先服务没有什么区别了，直接就跑完了）

2.   **Behavior similar to First Come First Served (FCFS).**  
   • 响应时间变长。  
     **Poor response time.**

3. **时间片过小：**  
   **Time Slice Too Small:**  
   • 上下文切换次数增加，开销过大。  
     **Too many context switches, leading to high overhead.**  
   • CPU利用率降低。  
     **Inefficient CPU utilization.**

4. **启发式方法：**  
   **Heuristic Approach:**  
   • 选择时间片大小，使得70-80%的作业在时间片内阻塞。  
     **Choose a time slice size such that 70-80% of jobs block within the time slice.**

5. **典型时间片大小：**  
   **Typical Time Slice Size:**  
   • 10到100毫秒。  
     **10 to 100 milliseconds.**

---

### **总结**  
**Summary**

• **轮转调度（RR）是一种简单、公平的调度算法，常用于交互式系统。**  
  **Round-Robin (RR) is a simple and fair scheduling algorithm commonly used in interactive systems.**

• **RR不考虑优先级，但上下文切换开销较大。**  
  **RR does not consider priority but has significant context switch overhead.**

• **时间片大小的选择对系统性能有重要影响：时间片过大会导致响应时间变长，时间片过小会增加上下文切换开销。**  
  **The choice of time quantum size has a significant impact on system performance: too large a time slice leads to long response times, while too small a time slice increases context switch overhead.**

通过理解轮转调度算法及其时间片大小的选择，可以更好地设计和实现操作系统中的调度机制，优化系统性能。  
**By understanding the Round-Robin scheduling algorithm and the choice of time quantum size, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.**

---



### **优先级调度（Priority Scheduling）**

以下是关于优先级调度算法的详细讲解，包括其工作原理、优先级设置方式以及存在的问题。

---

#### **1. 优先级调度的定义**  
**Definition of Priority Scheduling**

• **定义：**  
  **Definition:**  
  • 每个作业被分配一个优先级，优先调度高优先级作业。  
    **Each job is assigned a priority, and the highest priority job is scheduled first.**

• **特点：**  
  **Characteristics:**  
  • 在同一优先级内使用先来先服务（FCFS）。  
    **FCFS is used within each priority level.**  
  • 高优先级作业通常是关键任务。  
    **Higher priority jobs are typically mission-critical.**

• **问题：**  
  **Problems:**  
  • 可能无法提供最佳的平均等待时间（AWT）。  
    **May not provide the best average waiting time (AWT).**  
  • 可能导致低优先级作业无限期阻塞或饥饿。  
    **May cause indefinite blocking or starvation of low-priority jobs.**

---

#### **2. 优先级的设置**  
**Setting Priority**

1. **静态优先级（Static Priority）：**  
   **Static Priority:**  
   • 适用于系统已知且应用程序行为规律的环境。  
     **For systems with well-known and regular application behaviors.**

2. **动态优先级（Dynamic Priority）：**  
   **Dynamic Priority:**  
   • 适用于其他情况。  
     **Otherwise.**

• **优先级依据：**  
  **Priority may be based on:**  
  • 用户成本。  
    **Cost to user.**  
  • 用户重要性。  
    **Importance of user.**  
  • 进程类型。  
    **Process type.**  
  • 资源需求。  
    **Requirement to resource.**  
  • 老化（Aging）。  
    **Aging.**  
  • 过去X小时内使用的CPU时间百分比。  
    **Percentage of CPU time used in the last X hours.**

---

#### **3. 优先级调度的示例**  
**Example of Priority Scheduling**

• **进程参数：**  
  **Process Parameters:**  
| 进程 | 持续时间（ms） | 优先级 | 到达时间 |
| ---- | -------------- | ------ | -------- |
| P1   | 6              | 4      | 0        |
| P2   | 8              | 1      | 0        |
| P3   | 7              | 3      | 0        |
| P4   | 3              | 2      | 0        |

• **调度结果：**  
  **Schedule:**
0────8────11────18────24 P4 (3) P1 (6) P3 (7) P2 (8) ```

• 等待时间：
Waiting Time:
• P2: 0
• P4: 8
• P3: 11
• P1: 18

• 平均等待时间：
Average Waiting Time (AWT):
• (0 + 8 + 11 + 18) / 4 = 9.25

• 与SJF的比较：
Comparison with SJF:
• SJF的平均等待时间为7，优于优先级调度的9.25。
SJF provides a better average waiting time (7) compared to priority scheduling (9.25).

4. Unix中的“nice”命令

Be “nice” in Unix

• 定义：
Definition:
• nice命令用于调整进程的优先级，使其更“友好”（即降低优先级）。
The nice command is used to adjust the priority of a process, making it "nicer" (i.e., lowering its priority).

• 用途：
Purpose:
• 避免低优先级进程占用过多CPU资源，影响高优先级进程的执行。
Prevent low-priority processes from consuming too much CPU resources, affecting the execution of high-priority processes.

总结

Summary

• 优先级调度根据作业的优先级进行调度，适用于关键任务。
Priority scheduling schedules jobs based on their priority and is suitable for mission-critical tasks.

• 优先级可以是静态的或动态的，依据包括用户成本、用户重要性、进程类型等。
Priority can be static or dynamic, based on factors such as cost to user, importance of user, process type, etc.

• 优先级调度可能导致低优先级作业饥饿，因此需要结合老化（Aging）等机制来避免这一问题。
Priority scheduling may cause starvation of low-priority jobs, so mechanisms such as aging are needed to avoid this issue.

• Unix中的nice命令用于调整进程的优先级，使其更“友好”。
The nice command in Unix is used to adjust the priority of a process, making it "nicer."

通过理解优先级调度算法及其应用，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding the priority scheduling algorithm and its applications, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

多级反馈队列调度（Multi-Level Feedback Queue, MLFQ）

考试常考

以下是关于多级反馈队列调度算法的详细讲解，包括其工作原理、细节以及示例。

1. 多级反馈队列调度的定义

Definition of Multi-Level Feedback Queue (MLFQ)

• 定义：
Definition:
• 一种结合多级队列和优先级调度的调度算法，允许进程在队列之间移动。
A scheduling algorithm that combines multi-queue and priority scheduling, allowing processes to move between queues.

• 工作原理：
Working Principle:
• 每个进程开始时在高优先级队列中，每次CPU突发完成后，移动到较低优先级队列。
Start each process in a high-priority queue; as it finishes each CPU burst, move it to a lower-priority queue.
• 每个队列代表具有相似CPU使用情况的作业。
Each queue represents jobs with similar CPU usage.
• 每个队列中的作业使用特定的时间片执行。
Jobs in a given queue are executed with a given time slice.

• 设计理念：
Rationale:
• I/O密集型进程完成I/O请求后应具有更高的CPU优先级。
Once an I/O process completes an I/O request, it should have higher CPU priority.

2. 多级反馈队列调度的细节

Details of Multi-Level Feedback Queue (MLFQ)

• 示例（CTSS）：
Example (CTSS):
• 队列Queuei的时间片为t * 2^i。
Queuei has a time slice of t * 2^i.
• 如果队列Queuei中的作业在时间片结束时未阻塞，则移动到Queuei+1。
If a job in Queuei doesn't block by the end of the time slice, it is moved to Queuei+1.
• 最低优先级队列使用FCFS调度算法。
The lowest priority queue uses FCFS scheduling.

3. 多级反馈队列调度的示例

Example of Multi-Level Feedback Queue (MLFQ)

• 队列设置：
Queue Setup:
1. Q0： 时间片8ms。
Q0: Time slice of 8ms.
2. Q1： 时间片16ms。
Q1: Time slice of 16ms.
3. Q2： 使用FCFS调度算法。
Q2: Uses FCFS scheduling.

• 工作流程：
Workflow:
1. 新进程进入Q0，使用8ms的时间片执行。
A new process enters Q0 and executes with an 8ms time slice.
2. 如果进程在8ms内未完成，则移动到Q1，使用16ms的时间片执行。
If the process does not complete within 8ms, it moves to Q1 and executes with a 16ms time slice.
3. 如果进程在16ms内仍未完成，则移动到Q2，使用FCFS调度算法执行。
If the process still does not complete within 16ms, it moves to Q2 and executes using FCFS scheduling.

总结

Summary

• 多级反馈队列调度是一种结合多级队列和优先级调度的调度算法，允许进程在队列之间移动。
Multi-level feedback queue scheduling is a scheduling algorithm that combines multi-queue and priority scheduling, allowing processes to move between queues.

• 每个队列代表具有相似CPU使用情况的作业，并使用特定的时间片执行。
Each queue represents jobs with similar CPU usage and executes them with a given time slice.

• 最低优先级队列使用FCFS调度算法，确保长作业最终能够完成。
The lowest priority queue uses FCFS scheduling to ensure long jobs eventually complete.

通过理解多级反馈队列调度算法及其应用，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding the multi-level feedback queue scheduling algorithm and its applications, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

多级反馈队列调度（MLFQ）示例与计算

以下是关于多级反馈队列调度的详细示例，包括调度时间线和平均周转时间的计算。

1. 问题描述

Problem Description

• 进程参数：
Process Parameters:
| 进程ID | 到达时间 | 突发时间 | | ------ | -------- | -------- | | A | 0 | 7 | | B | 2 | 9 | | C | 5 | 4 | | D | 7 | 8 | | E | 8 | 2 |

• 队列设置：
Queue Setup:
1. Q0： 时间片3ms，优先级基于到达时间。
Q0: Time slice of 2ms, priority based on arrival time.
2. Q1： 时间片4ms，优先级基于到达时间。
Q1: Time slice of 4ms, priority based on arrival time.
3. Q2： 使用FCFS调度算法。
Q2: Uses最短作业优先（考试题）

img

总结

Summary

• 多级反馈队列调度根据进程的到达时间和突发时间动态调整优先级，确保系统响应性和公平性。
Multi-level feedback queue scheduling dynamically adjusts priorities based on process arrival times and burst times, ensuring system responsiveness and fairness.

• 通过调度时间线和周转时间计算，可以验证多级反馈队列调度的性能。
The scheduling timeline and turnaround time calculation verify the performance of multi-level feedback queue scheduling.

• 平均周转时间为18.2，表明多级反馈队列调度在该示例中表现良好。
The average turnaround time of 18.2 indicates that multi-level feedback queue scheduling performs well in this example.

通过理解多级反馈队列调度算法及其应用，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding the multi-level feedback queue scheduling algorithm and its applications, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

调度算法回顾

以下是对调度算法的总结，涵盖了批处理系统和交互式系统中常用的调度算法。

1. 批处理系统中的调度算法

Scheduling Algorithms in Batch Systems

批处理系统的目标是最大化吞吐量和最小化平均等待时间，通常使用非抢占式调度算法。

1.1 先来先服务（First Come First Served, FCFS）

• 定义：
• 最先到达的进程最先获得CPU。
The process that arrives first is allocated the CPU first. • 特点：
• 非抢占式调度算法。
Non-preemptive scheduling algorithm. • 简单易实现，但可能导致护航效应（长作业阻塞短作业）。
Simple to implement but may cause convoy effects (long jobs block short jobs). • 适用场景：
• 批处理系统。
Batch systems.

1.2 最短作业优先（Shortest Job First, SJF）

• 定义：
• 优先调度运行时间最短的作业。
The job with the shortest elapsed time is scheduled first. • 类型：
1. 非抢占式SJF：
◦ 进程运行直到完成。
The process runs until it completes. 2. 抢占式SJF（最短剩余时间优先，SRTF）：
◦ 优先调度剩余时间最短的进程。
The job with the shortest remaining time is scheduled first.

• **优点：**  

• 如果所有作业同时到达，SJF是最优的，提供最小的平均等待时间。  

**If all jobs arrive simultaneously, SJF is optimal and provides the minimum average waiting time.**

• 缺点：
• 需要预先知道作业的运行时间。
Requires prior knowledge of job execution times. • 可能导致饥饿（长作业永远无法运行）。
May cause starvation (long jobs may never run). • 适用场景：
• 批处理系统。
Batch systems.

2. 交互式系统中的调度算法

Scheduling Algorithms in Interactive Systems

交互式系统的目标是最小化响应时间和提高用户体验，通常使用抢占式调度算法。

2.1 轮转调度（Round-Robin, RR）

• 定义：
• 每个进程分配一个固定时间片，时间片用完后切换到下一个进程。
Each process is allocated a fixed time slice, and after the time slice is used up, the next process is scheduled. • 特点：
• 抢占式调度算法。
Preemptive scheduling algorithm. • 公平，但可能导致上下文切换开销。
Fair but may incur high context switch overhead. • 适用场景：
• 交互式系统。
Interactive systems.

2.2 优先级调度（Priority Scheduling）

• 定义：
• 每个进程分配一个优先级，优先调度高优先级进程。
Each process is assigned a priority, and higher-priority processes are scheduled first. • 特点：
• 可以是静态优先级（基于进程类型或用户重要性）或动态优先级（根据运行情况调整）。
Can be static (based on process type or user importance) or dynamic (adjusted based on runtime behavior). • 可能导致低优先级进程饥饿。
May cause starvation of low-priority processes. • 适用场景：
• 实时系统或需要区分任务重要性的场景。
Real-time systems or scenarios where task importance needs to be distinguished.

2.3 多级队列调度（Multi-Queue Scheduling）

• 定义：
• 将就绪队列分为多个子队列，每个子队列代表一类进程（如交互式进程、后台进程等）。
The ready queue is divided into multiple sub-queues, each representing a class of processes (e.g., interactive, background). • 特点：
• 每个子队列可以使用不同的调度算法。
Each sub-queue can use a different scheduling algorithm. • 高优先级队列中的进程优先执行。
Processes in higher-priority queues are scheduled first. • 适用场景：
• 需要根据进程类型分类调度的场景。
Scenarios where processes need to be classified and scheduled based on their type.

2.4 多级反馈队列调度（Multi-Level Feedback Queue, MLFQ）

• 定义：
• 结合多级队列和优先级调度，允许进程在队列之间动态移动。
Combines multi-level queue and priority scheduling, allowing processes to move between queues dynamically. • 特点：
• 新进程从高优先级队列开始，每次完成时间片后降级到低优先级队列。
New processes start in the highest-priority queue and are demoted to lower-priority queues after completing a time slice. • 低优先级队列通常使用FCFS调度算法。
The lowest-priority queue typically uses FCFS scheduling. • 动态调整优先级，避免低优先级进程饥饿。
Dynamically adjusts priorities to avoid starvation of low-priority processes. • 适用场景：
• 需要兼顾响应性和公平性的场景。
Scenarios that require a balance between responsiveness and fairness.

3. 调度算法总结

Summary of Scheduling Algorithms

算法 特点 适用场景
先来先服务（FCFS） 简单易实现，但可能导致护航效应。 批处理系统。
最短作业优先（SJF） 最优的平均等待时间，但需要预先知道作业时间，可能导致饥饿。 批处理系统。
轮转调度（RR） 公平，但可能导致上下文切换开销。 交互式系统。
优先级调度 区分任务重要性，但可能导致低优先级进程饥饿。 实时系统或任务重要性区分场景。
多级队列调度 根据进程类型分类调度，灵活性高。 需要分类调度的场景。
多级反馈队列调度（MLFQ） 动态调整优先级，兼顾响应性和公平性，避免饥饿。 需要平衡响应性和公平性的场景。

总结

Summary

• 批处理系统通常使用FCFS和SJF，目标是最大化吞吐量和最小化平均等待时间。
Batch systems typically use FCFS and SJF, aiming to maximize throughput and minimize average waiting time.

• 交互式系统需要更灵活的调度算法，如RR、优先级调度和MLFQ，以满足实时性和用户体验需求。
Interactive systems require more flexible scheduling algorithms, such as RR, priority scheduling, and MLFQ, to meet real-time and user experience requirements.

• 多级反馈队列调度（MLFQ）是一种高级调度算法，结合了多级队列和优先级调度的优点，适合复杂的多任务环境。
Multi-level feedback queue scheduling (MLFQ) is an advanced scheduling algorithm that combines the advantages of multi-level queue and priority scheduling, suitable for complex multitasking environments.

通过理解这些调度算法的特点和适用场景，可以更好地设计和实现操作系统中的调度机制，优化系统性能。
By understanding the characteristics and application scenarios of these scheduling algorithms, we can better design and implement scheduling mechanisms in operating systems, optimizing system performance.

高级调度算法与实时系统调度

以下是关于保证调度（Guaranteed Scheduling）、彩票调度（Lottery Scheduling）、公平共享调度（Fair-Share Scheduling）以及实时系统调度的详细讲解。

7. 保证调度（Guaranteed Scheduling, QoS）

• 定义：
Definition:
• 向用户做出实际的性能承诺，并兑现这些承诺。
Make real promises to users about performance and then fulfill them.

• 工作原理：
Working Principle:
• 假设有n个进程正在运行，调度器确保每个进程获得1/n的CPU时间。
If there are n processes running, the scheduler ensures that each process gets 1/n of the CPU cycles. • 计算每个进程实际消耗的CPU时间与其应得CPU时间的比率，选择比率最低的进程运行。
Compute the ratio of actual CPU time consumed to CPU time entitled, and select the process with the lowest ratio.

• 优点：
Advantages:
• 提供公平的资源分配，避免某些进程长期占用CPU。
Provides fair resource allocation and prevents certain processes from monopolizing the CPU.

• 缺点：
Disadvantages:
• 需要精确的CPU时间监控和调度决策，可能增加系统开销。
Requires precise monitoring of CPU time and scheduling decisions, which may increase system overhead.

8. 彩票调度（Lottery Scheduling）

• 定义：
Definition:
• 基于概率的调度算法，为每个进程分配“彩票”，调度时随机选择一张彩票，持有该彩票的进程获得资源。
A probability-based scheduling algorithm that assigns "lottery tickets" to processes. At scheduling time, a lottery ticket is chosen randomly, and the process holding the ticket gets the resource.

• 工作原理：
Working Principle:
• 高优先级进程获得更多的彩票（近似优先级调度）。
Higher-priority processes are given more tickets (approximates priority scheduling).
• 短作业可以获得更多的彩票（近似最短作业优先调度）。
Short jobs are given more tickets (approximates shortest job first scheduling).

• 优点：
Advantages:
• 简单易实现。
Simple to implement.
• 高度响应性。
Highly responsive.
• 支持进程间的协作。
Supports cooperation between processes.
• 易于支持优先级和比例需求。
Easily supports priority and proportion requirements.

• 缺点：
Disadvantages:
• 彩票分配可能导致不公平（例如，高优先级进程可能长期占用资源）。
Ticket allocation may lead to unfairness (e.g., high-priority processes may monopolize resources for a long time).

9. 公平共享调度（Fair-Share Scheduling）

• 定义：
Definition:
• 基于用户的公平共享调度，确保每个用户获得公平的CPU时间，而不是仅仅基于进程数量。
A user-based fair-share scheduling ensures that each user gets a fair share of CPU time, rather than just based on the number of processes.

• 工作原理：
Working Principle:
• 每个用户分配一定的CPU时间配额。
Each user is assigned a certain CPU time quota.
• 示例：
Example:
◦ Alice有4个进程（A1, A2, A3, A4），Bob有1个进程（B1）。
Alice has 4 processes (A1, A2, A3, A4), and Bob has 1 process (B1).
◦ Alice的每个进程只能获得50%的CPU时间，而Bob的进程可以获得另外50%的CPU时间。
Each of Alice's processes is entitled to only 50% of the CPU time, while Bob's process is entitled to the other 50%.
◦ 可能的调度序列：
Possible scheduling sequence:
A1 → B1 → A2 → B1 → A3 → B1 → A4 → B1 → ...

• 优点：
Advantages:
• 避免了某些用户独占CPU资源的情况。
Prevents certain users from monopolizing CPU resources.

• 缺点：
Disadvantages:
• 可能导致某些进程的响应时间变长。
May result in longer response times for certain processes.

10. 实时系统调度（Scheduling in Real-Time Systems）

• 定义：
Definition:
• 调度器对用户的截止时间或CPU利用率做出实际承诺。
The scheduler makes real promises to users in terms of deadlines or CPU utilization.

• 可调度性条件：
Schedulability Condition:
• 给定m个周期性事件：
Given m periodic events:
◦ 事件i在周期Pi内发生，需要Ci秒的CPU时间。
Event i occurs within period Pi and requires Ci seconds of CPU time.
◦ 如果满足以下条件，则系统是可调度的：
The system is schedulable if:
$ _{i=1}^{m} $ ◦

系统是可调度的。

11. 用户级线程调度（User-Level Thread Scheduling）

• 定义：
Definition:
• 用户级线程的调度由用户空间的线程库管理，操作系统内核不直接参与。
User-level thread scheduling is managed by a user-space thread library, and the operating system kernel is not directly involved.

• 示例：
Example:
• 假设时间片为50ms，每个线程运行5ms的CPU突发时间。
Assume a quantum of 50ms, and each thread runs for 5ms of CPU burst time.

12. 内核级线程调度（Kernel-Level Thread Scheduling）

• 定义：
Definition:
• 内核级线程的调度由操作系统内核直接管理，内核负责分配CPU时间片。
Kernel-level thread scheduling is directly managed by the operating system kernel, which is responsible for allocating CPU time slices.

• 示例：
Example:
• 假设时间片为50ms，每个线程运行5ms的CPU突发时间。
Assume a quantum of 50ms, and each thread runs for 5ms of CPU burst time.

• 与用户级线程调度的区别：
Differences from User-Level Thread Scheduling:
• 内核级线程调度由操作系统内核直接管理，支持多核处理器和优先级调度。
Kernel-level thread scheduling is directly managed by the OS kernel, supporting multi-core processors and priority scheduling.
• 用户级线程调度由用户空间的线程库管理，性能更高，但无法利用多核处理器。
User-level thread scheduling is managed by a user-space thread library, offering higher performance but cannot utilize multi-core processors.

总结

• 保证调度（Guaranteed Scheduling）： 提供公平的资源分配，确保每个进程获得承诺的CPU时间。
Guaranteed Scheduling provides fair resource allocation and ensures each process gets the promised CPU time.

• 彩票调度（Lottery Scheduling）： 基于概率的调度算法，简单高效，支持优先级和比例需求。
Lottery Scheduling is a probability-based scheduling algorithm that is simple, efficient, and supports priority and proportion requirements.

• 公平共享调度（Fair-Share Scheduling）： 基于用户的公平调度，确保每个用户获得公平的CPU时间。
Fair-Share Scheduling ensures each user gets a fair share of CPU time.

• 实时系统调度： 通过可调度性条件确保系统能够满足实时任务的截止时间和资源需求。
Real-time system scheduling ensures the system can meet the deadlines and resource requirements of real-time tasks through schedulability conditions.

• 用户级线程调度与内核级线程调度： 用户级线程调度性能更高，但无法利用多核；内核级线程调度支持多核，但性能稍低。
User-level thread scheduling offers higher performance but cannot utilize multi-core processors, while kernel-level thread scheduling supports multi-core but has slightly lower performance.

通过理解这些高级调度算法和实时系统调度机制，可以更好地设计和实现操作系统中的调度策略，优化系统性能和用户体验。
By understanding these advanced scheduling algorithms and real-time system scheduling mechanisms, we can better design and implement scheduling strategies in operating systems, optimizing system performance and user experience.