进程的调度算法
在这条道路上越走越发现你知道的知识永远只是凤毛菱角,你只能不断学习,扩充你的知识面,才可以做到大佬的级别!当然,这条路还很长,还得不断学习!
如果不是整理知识点,我也不会发现,涵盖的知识点如此之多,虽然是概念性的知识点,但是这些就像灵魂一样,没有拥有这些知识储备,那也只能是码农级别的猿.好比只有身体,没有灵魂 !
当然,我会不断扩充自己的知识面的!加油!
前言知识点:
无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。
这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。
一、进程的基本状态及状态间的转换：
1.等待态：等待某个事件的完成；
2.就绪态：等待系统分配处理器以便运行；
3.运行态：占有处理器正在运行。
二、处理机
高级、中级和低级调度作业从提交开始直到完成，往往要经历下述三级调度：
高级调度：(High-Level Scheduling)又称为作业调度，它决定把后备作业调入内存运行；
低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪队列的某进程获得CPU；
中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。
一.进程的调度算法.
操作系统中调度是一种是一种资源分配!
操作系统管理了系统的有限资源，当有多个进程（或多个进程发出的请求）要使用这些资源时，因为资源的有限性，必须按照一定的原则选择进程（请求）来占用资源。这就是调度。目的是控制资源使用者的数量,选取资源使用者许可占用资源或占用资源。
有了调度当然就需要调度的方法了,那么调度算法随之而来
1>先来先服务
先来先服务（FCFS, First Come First Serve）是最简单的调度算法，按先后顺序进行调度。
定义
按照作业提交或进程变为就绪状态的先后次序，分派CPU；
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。
在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。
适用场景
比较有利于长作业，而不利于短作业。
有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
有点像队列
2>轮转法(Round Robin)
是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。
定义
将系统中所有的就绪进程按照FCFS原则，排成一个队列。
每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
在一个时间片结束时，发生时钟中断。
调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
进程可以未使用完一个时间片，就出让CPU（如阻塞）。
长度的确定
时间片长度变化的影响
过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。
过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。
对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)
就绪进程的数目：数目越多，时间片越小
系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。
3>短作业优先法
短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。
定义
对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。
SJF的特点
(1) 优点：
比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
提高系统的吞吐量；
(2) 缺点：
对长作业非常不利，可能长时间得不到执行；
未能依据作业的紧迫程度来划分执行的优先级；
难以准确估计作业（进程）的执行时间，从而影响调度性能。
4>最短剩余时间优先(短作业优先法的变形)
SJF的变型
“最短剩余时间优先”SRT(Shortest Remaining Time)（允许比当前进程剩余时间更短的进程来抢占）
“最高响应比优先”HRRN(Highest Response Ratio Next)（响应比R = (等待时间 + 要求执行时间) / 要求执行时间，是FCFS和SJF的折衷）
5>最高响应比优先法(HRN，Highest Response_ratio Next)
是对FCFS(先来先服务)方式和SJF(短时间优先)方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。
6>多级反馈队列
多级反馈队列算法(Round Robin with Multiple Feedback)是轮转算法和优先级算法的综合和发展。
定义
设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。
新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。
优点
为提高系统吞吐量和缩短平均周转时间而照顾短进程。
为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。
不必估计进程的执行时间，动态调节
几点说明
I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。