单处理器调度

博主： Xherlock
发布时间：2022 年 06 月 10 日
404 次浏览
暂无评论
1807字数
分类：操作系统

# 单处理器调度

## 处理器调度的类型

调度目的：把进程分配到一个或多个处理器上执行（需要满足：响应时间、吞吐率、处理器效率、公平性）

**调度类型**

* 长程调度：决定加入待执行进程池，也称作业调度，仅仅是将作业调入内存，进程处于就绪态
* 中程调度：决定加入部分或全部位于内存中的进程集合
* 短程调度：决定处理器执行哪个可运行进程，也称进程调度，频度最高
* I/O调度：决定I/O设备处理哪个进程挂起的I/O请求

![image-20220510104408046.png](http://xherlock.top/usr/uploads/2022/06/1928133407.png)

**调度层次**

![image-20220510104848548.png](http://xherlock.top/usr/uploads/2022/06/3704469573.png)

调度本质上属于队列管理，用于在排队中减少延迟并优化性能

![image-20220510104918144.png](http://xherlock.top/usr/uploads/2022/06/2589360822.png)

### 长程调度

决定哪个程序加载入系统处理

* 控制系统的并发度
* 越多进程，每个进程执行的时间百分比越小（由于竞争处理器时间）

### 中程调度

交换功能的一部分，基于管理系统并发度的需求

### 短程调度

也被称为分派器（dispatcher），执行的最为频繁

导致当前进程阻塞或抢占当前运行进程的事件发生时，调用短程调度

* 时钟中断
* I/O中断
* OS调用
* 信号

## 调度算法

### 短程调度准则

* 面向用户：与单个用户或进程感知到的系统行为有关，如交互式系统中的响应时间
* 面向系统：重点是处理器使用的效果和效率，如吞吐量

另一个划分维度：性能

* 与性能相关：响应时间、吞吐量
* 其他：定性的，不宜测量和分析，如可预测性

### 选择调度策略

决策模式分为非抢占和抢占（OS中断运行中程序、新进程到达、中断发生后一个阻塞态置为就绪态、周期性时间中断）

区分静态/动态优先级：进程创建时优先级就确定的为静态优先级，如FCFS和SPN

#### FCFS，先来先服务

最简单，严格排队方案；当前正运行的进程停止执行后，选择就绪队列中存在时间最长的进程运行

（**非抢占**），缺点：短进程可能需要很长时间才能执行

#### RR，轮转

基于时钟的**抢占**策略，周期性产生时钟中断，出现中断时，当前正在运行的进程换出到就绪队列，然后基于FCFS选择下一个就绪作业运行（该技术称为**时间片**，time slicing，每个进程在被抢占前都会给定一片时间）

这里要尤其注意时间片长度的选择：长度很短，短作业会相对比较快地通过系统；长度很长，接近FCFS

改进的RR：VRR，虚拟轮转法：把因为I/O阻塞的进程放到单独的队列，并给予优先选择

#### SPN，最短进程优先

**非抢占**策略，下次选择预计处理时间会最短的进程

缺点：更长的进程可能会饥饿，很难预测未来

#### SRT，最短剩余时间

在SPN中增加了**抢占**机制，一个时间片结束时，优先选择最短剩余时间的进程

#### HRRN，最高响应比优先

**非抢占**，选择有最大响应比的进程，$R=\frac{w+s}{s}$，R为响应比，w为等待处理器的时间，s为预计的服务时间，相当于周转/驻留时间和实际服务时间的比值

偏向短作业时，长进程由于得不到服务，等待的时间增加，R变大，最终在竞争中赢了短进程

同SPN、SRT，这些都需要估计预计的服务时间

#### feedback，反馈法

如果不能获取各个进程相对长度，不能使用上述SPN、SRT、HRRN

处罚运行时间长的作业，即关注已执行的时间

调度基于**抢占**原则（按时间片）并使用动态优先级机制：长进程每次被抢占就降级到优先级低的队列中

最后修改：2022 年 06 月 10 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

应用层（四）
浏览次数: 704
socket实现局域网S-C通信
浏览次数: 447
输入/输出和存储系统
浏览次数: 852
网络层（二）
浏览次数: 389
RSA
浏览次数: 538

单处理器调度

Xherlock • 2022 年 06 月 10 日

# 单处理器调度

## 处理器调度的类型

调度目的：把进程分配到一个或多个处理器上执行（需要满足：响应时间、吞吐率、处理器效率、公平性）

**调度类型**

![image-20220510104408046.png](http://xherlock.top/usr/uploads/2022/06/1928133407.png)

**调度层次**

![image-20220510104848548.png](http://xherlock.top/usr/uploads/2022/06/3704469573.png)

调度本质上属于队列管理，用于在排队中减少延迟并优化性能

![image-20220510104918144.png](http://xherlock.top/usr/uploads/2022/06/2589360822.png)

### 长程调度

决定哪个程序加载入系统处理

* 控制系统的并发度
* 越多进程，每个进程执行的时间百分比越小（由于竞争处理器时间）

### 中程调度

交换功能的一部分，基于管理系统并发度的需求

### 短程调度

也被称为分派器（dispatcher），执行的最为频繁

导致当前进程阻塞或抢占当前运行进程的事件发生时，调用短程调度

* 时钟中断
* I/O中断
* OS调用
* 信号

## 调度算法

### 短程调度准则

* 面向用户：与单个用户或进程感知到的系统行为有关，如交互式系统中的响应时间
* 面向系统：重点是处理器使用的效果和效率，如吞吐量

另一个划分维度：性能

* 与性能相关：响应时间、吞吐量
* 其他：定性的，不宜测量和分析，如可预测性

### 选择调度策略

决策模式分为非抢占和抢占（OS中断运行中程序、新进程到达、中断发生后一个阻塞态置为就绪态、周期性时间中断）

区分静态/动态优先级：进程创建时优先级就确定的为静态优先级，如FCFS和SPN

#### FCFS，先来先服务

最简单，严格排队方案；当前正运行的进程停止执行后，选择就绪队列中存在时间最长的进程运行

（**非抢占**），缺点：短进程可能需要很长时间才能执行

#### RR，轮转

这里要尤其注意时间片长度的选择：长度很短，短作业会相对比较快地通过系统；长度很长，接近FCFS

改进的RR：VRR，虚拟轮转法：把因为I/O阻塞的进程放到单独的队列，并给予优先选择

#### SPN，最短进程优先

**非抢占**策略，下次选择预计处理时间会最短的进程

缺点：更长的进程可能会饥饿，很难预测未来

#### SRT，最短剩余时间

在SPN中增加了**抢占**机制，一个时间片结束时，优先选择最短剩余时间的进程

#### HRRN，最高响应比优先

偏向短作业时，长进程由于得不到服务，等待的时间增加，R变大，最终在竞争中赢了短进程

同SPN、SRT，这些都需要估计预计的服务时间

#### feedback，反馈法

如果不能获取各个进程相对长度，不能使用上述SPN、SRT、HRRN

处罚运行时间长的作业，即关注已执行的时间

调度基于**抢占**原则（按时间片）并使用动态优先级机制：长进程每次被抢占就降级到优先级低的队列中

发表评论 取消回复

单处理器调度

发表评论取消回复