当有多个进程时,cpu调度决定了哪一个进程运行
计算机中,CPU与I/O交替运行
但是一个进程往往需要大量的计算,却有很少的I/O操作,并且I/O操作很费时间,于是乎,我们想让这个cpu的执行的时间更长一些,I/O更短一些,甚至可以同时把多个进程导入内存，使得一个进程在CPU中执行I/O时，一个进程用来填补CPU的时间
进程状态
在前面进程一章单独讲过进程状态,这里抽出三个比较主要的:
■ Running - process is running on CPU.
■ Ready - ready to run, but not actually running on the CPU.
■ Waiting - waiting for some event like IO
to happen
调度算法
✈算法关注点
- cpu使用率:让cpu尽可能高效
- 吞吐量：单位时间完成进程的数量
- 周转时间：从进程提交到进程完成
- 等待时间：在就绪队列等待的时间之和
- 响应时间：提交请求到第一次回复请求
不同的系统关注点不同:多道系统想要好的吞吐量和周转时间,而交互系统则更看中响应时间
一. 批处理系统
✈First-Come, First-Served (FCFS)
先到先服务,顾名思义,一个进只有被中断或者执行I/O才会放弃cpu资源,在其他情况下一直做个独裁者
假设有三个进程:
P1 (takes 24 seconds)
P2 (takes3 seconds)
P3 (takes 3 seconds)
□ If arrive in order P1, P2, P3, what is
Waiting Time? (24+27) / 3 = 17
Turnaround Time? (24+27+30) / 3 = 27
Throughput? 30 / 3 = 10.
✈Priority Scheduling
每个进程赋予一个优先级,优先级高的先运行,如果优先级相同:考虑FCFS算法
饥饿问题:优先级小的进程不容易运行,这里用老化解决:随着时间增长,那些一直没有运行的进程的优先级会逐步增加
假定这里有五个进程:
P1(burst time 10, priority 3), P2 (burst
time 1, priority 1), P3 (burst time 2,
priority 3), P4 (burst time 1, priority
4), P5 (burst time 5, priority 2). Lower
numbers represent higher priorities.
执行顺序按照权重
下面介绍优先调度算法的一个分支
Shortest-Job-First (SJF)
最小任务优先可以减少等待和周转时间,因为哪些时间长的任务放到了最后.前面提到,一个进程是由CPU区间和I/O区间交替组成的,而SJF是看哪个进程的CPU区间最短
- 抢占式：又称最短剩余优先，当新进来的进程的CPU区间比当前执行的进程所剩的CPU区间短，则抢占
- 非抢占：称为下一个最短优先，因为在就绪队列中选择最短CPU区间的进程放在队头
四个进程:
P1 (burst time 8)
P2(burst time 4)
P3 (burst time 9)
P4 (burst time 5)
that arrive one time unit apart in order P1, P2, P3, P4.
- 抢占的顺序是:P2(time 4)P4(time 5)P1(time 8)P3(time9)
- 非抢战的顺序:P1(time 1)P2(time 4)P4(time 5)P1(time 7)P3(time 9)
SJF用于长期调度而不能用短期调度,因为进程是一个整体,CPU没法知道进程中第一个CPU区间长度。
SJF需要确定下一个CPU区间的时间长度,可以通过近似估算出下一个CPU区间的长度,比如tn+1=atn+(1-a)rn tn为最近最近一次的CPU时间，rn为历史记录,a是给定的权重。
二.分时操作系统
✈轮转法/RR调度
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。
时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾
然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。
如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。
- 多级队列方法：将系统中所有进程分成若干类，每类为一级
- 多级反馈队列:多级反馈队列方式是在系统中设置多个就绪队列，并赋予各队列以不同的优先权---百度超详细讲解
假设Have 3 queues, numbered 0, 1, 2 with
corresponding priority.
■ So, for example, execute a task in queue
2 only when queues 0 and 1 are empty.
- 首先进程从就绪状态到队列0,然后让他运行8ms
- 到达队列1,让他运行16ms
- 运行队列2:如果是交互系统,采用RR调度(给他充足的运行时间).如果是批处理操作系统,采用FCFS算法
如果此时有其他进程准备就绪,则抢占队列2,这个算法也就是说,后进的不一定最慢完成
✈unix调度
作为分时操作系统最最典型的unix与linux,自然要介绍下让他们:
每个进程给予相同的优先级:60,由于系统时钟每秒产生一个50到100次的中断，所以我们假设每秒钟有60次中断,当被中断的进程运行时,时钟中断程序会在PCB上增加一个字段:cpu使用率
操作系统会运行优先级最高的进程,如果相同,会选择在就绪队列时间较长的那一个
每一秒,都会从新计算优先级和cpu使用率:
- cpu使用率=cpu使用率 / 2
- 优先级=cpu 使用率 / 2 + 基础优先级(60)
所以,不难看出,如果一个进程最近没有使用过cpu,那么他的优先级就会增高,与IO和交互相关的进程优先级往往很高，与CPU相关的进程优先级往往很低（这是您想要的）
unix还为每个进程提供一个"nice"值,用来修正优先级计算:
- 优先级= CPU使用率 / 2 + 基础优先级 + nice value
数字越低,优先级越高,并且您能通过nice值来减少一个进程的优先级
