计算机操作系统调度算法

àì夳堔傛蜴生んèń 2023-09-29 12:00 223阅读 0赞

## 处理机调度 ##

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATGlodWFfbmc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

### 1. 总述 ###

#### 1.1 处理机调度层次 ####

**高级调度**：调度对象是作业，决定将外存中的哪些作业调入内存，并创建进程，分配必要资源，然后放入就绪队列。

**中级调度**：也称内存调度，该调度的目的是提高内存利用率和系统吞吐率。把阻塞进程调到外存等待，当外存的进程进入就绪状态后，再调入内存。

**低级调度**：调度对象是进程。决定就续队列中的哪些进程能获得处理机。

#### 1.2 调度算法目标 ####

处理机调度算法最重要的共同目标就是提高CPU的利用率，同时能保证公平性就最好了。但是对于不同的系统有不同的要求。

像批处理系统则希望周转周期短一点，这样避免一个任务执行时间过长；分时系统则希望响应时间快一点；实时系统则希望能保证截止时间，并且有可预测性，不然如何保证截止时间？

### 2. 作业与作业调度 ###

#### 2.1 作业 ####

在批处理系统中，作业是用户提交给系统的相对独立的任务。在多道批处理系统中，为了管理和调度作业(相当于管理进程)，设置了一个作业控制块JCB。

#### 2.2 作业调度的目标 ####

作业调度是查看JCB中的信息，判断系统中的资源是否满足，然后根据算法把队列中的作业调入内存。应该做到几个比较基本的功能，判断接纳几个作业？因为内存是有限的，倘若接纳作业太多，会导致某些作业出现严重错误，发生中断；若接纳的作业太少，则大量的内存被浪费。

并且要判断接纳哪些作业？哪些先处理？哪些能处理？

#### 2.3 作业调度算法 ####

##### 2.3.1 先来先服务FCFS #####

**FCFS**是最简单的调度算法，日常生活中很多情况都是先来先服务，排队嘛。但是它的缺点也很多。

比如说，某一个作业时间很长，那后面有个作业很短的就不爽了，或者是某些优先级更高的操作被排在后面，那就是耽误事了。因此实际上FCFS不作为主要的调度算法，是作为混合调度算法中的辅助角色。

##### 2.3.2 短作业优先SJF #####

这个算法就是把当前作业中，花费时间比较短的先完成。但是也有几个问题。

第一个，如何判断作业时间长短？

第二个，倘若不断有短作业进来，最初的长作业不断被延迟，何时能完成？

##### 2.3.3 优先级调度算法PSA #####

其实先来先服务可以认为是优先级调度的变种，不过FCFS算法的优先级是到达时间。优先级调度则是设置任务的优先级，先完成优先级高的任务。

##### 2.3.4 高响应比优先调度算法HRRN #####

FCFS只考虑的作业的等待时间，没考虑运行时间；SJF只考虑的作业的运行时间没考虑等待时间；HRRN则同时考虑了这两个情况。

### 3. 进程调度 ###

#### 3.1 总述 ####

##### 3.1.1 任务 #####

要完成进程调度，有几个比较重要的任务要完成。

第一个，要保存当前的处理机现场，让唤醒后能从断点继续运行。

第二个，要按照算法选取进程，把就绪队列中的进程选一个出来执行

第三个，把处理机分配给进程，把进程中的相关数据信息装入相关寄存器中，然后把处理机控制权交给进程。

##### 3.1.2 方式 #####

进程调度分抢占和非抢占两种，抢占则会强制中断当前运行的进程，反之则反。

现代操作系统更多用抢占方式，因为很多调度算法的实现必须要用抢占方式。像时间片轮转算法，要强行中断当前的进餐，执行下一个进程。

#### 3.2 调度算法 ####

##### 3.2.1 时间片轮转调度算法 #####

轮转法就是每个进程拥有一个时间片，每个进程都执行一段时间，然后转到另一个进程。CPU设置一个时间片，当进程执行完时间片事件后，调下一个进程执行。

##### 3.2.2 优先级调度算法 #####

时间片轮转中，进程调用顺序是可以有考究的，可以用简单的FCFS算法，也可以通过优先级进行排序。但是，这个优先级也可以进行优化，优先级是静态的或者是动态变化的。如果优先级是动态变化的，把等待时间加权，那就把优先级和FCFS融合在一起了。

##### 3.2.3 多队列调度算法 #####

上诉的算法可以在单处理机中很好的提高CPU效率，但是在多处理机中则需要改进一下。设置多个就绪队列，对于不同的就绪队列可以使用不同的调度算法，实现更高的适配性。

### 4. 实时调度 ###

#### 4.1 最早截至时间算法EDF ####

#### 4.2 最低松弛度优先LLF ####

多处理机中则需要改进一下。设置多个就绪队列，对于不同的就绪队列可以使用不同的调度算法，实现更高的适配性。

### 4. 实时调度 ###

#### 4.1 最早截至时间算法EDF ####

#### 4.2 最低松弛度优先LLF ####

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATGlodWFfbmc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/f97b863f79cf47dd92cbd6e1f3426970.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATGlodWFfbmc=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center