进程调度概述
一、操作系统的调度时机
1、什么时候进行进程调度？
主动放弃（进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞）
被动放弃（分给进程的时间片用完、有更紧急的事需要处理、有更高优先级的进程进入就绪队列）
2、什么时候不能进行进程调度？
（1）处理中断；
（2）访问临界区（临界区：在操作系统内核中，临界区是指一个程序段，它需要独占地访问某个共享资源，例如硬件设备或共享数据结构，以避免并发访问所导致的不一致性和错误。当一个进程进入临界区时，其他进程必须等待该进程退出临界区才能访问共享资源）；
（3）原语的执行过程之中；
3、进程的切换需要做的事情？
（1）对原来运行进程各种数据的保存；
（2）对新进程的数据环境的恢复；
二、进程调度的联系和对比
三、进程调度的方式
非剥夺调度方式（非抢占式）：只允许进程主动放弃处理机
剥夺调度方式（抢占式）：进程被动放弃，可以优先处理紧急任务，适合分时操作系统、实时操作系统
四、闲逛进程
闲逛进程的存在是为了防止出现所有进程均处于阻塞态导致cpu无进程可以运行的情况出现。当系统中除闲逛进程外的所有进程均阻塞，就会调度闲逛进程运行，并在运行过程中一直测试中断。闲逛进程的优先级最低，一旦有其他进程从阻塞态进入就绪态，就暂停闲逛进程，调度该进程运行。目的相当于需要定时器去一直监听是否存在需要处理的进程；
五、调度算法的评价指标
1、CPU利用率
CPU利用率=CPU忙碌的时间/总时间
2、系统吞吐量
=总共完成了多少道作业/总共画了多少时间
3、周转时间
周转时间（提交作业到完成作业花费的时间）、平均周转时间（各作业周转时间之和/作业数）
带权周转时间（作业周转时间/作业实际运行的时间）、平均带权周转时间（各作业带权周转时间/作业数）
4、等待时间
进程或作业等待处理机状态时间的和
进程：等待被服务的时间之和
作业：建立后的等待时间+作业在外存后备队列中等待的时间
5、响应时间
从用户提交请求到首次产生响应所用的时间
进程调度算法
1、先来先服务（FCFS）
先到达先进行服务
作业-后备队列；进程-就绪队列
非抢占式
公平、算法简单
对长作业有利、对短作业不利、不会饥饿
2、短作业优先（SJF，shortest job first）
最短（服务时间最短）的作业优先得到服务，时间相同，先到达的先被服务
非抢占式（SJF）：选最短需要时间的作业先进入运行态
抢占式（SRTN）：有新作业进入就绪队列或有作业完成了，考察队列中的最小需要时间的作业
在所有进程都几乎同时到达时，采用SJP调度算法的平均等待时间、平均周转时间最少
若无红色前提，抢占式的短作业/进程的平均时间最少
优点：“最短的”平均等待时间，平均周转时间
缺点：对短作业有利，对长作业不利，可能产生饥饿现象
3、高响应比优先（HRRN）
要综合考虑作业/进程的等待时间和要求服务的时间
在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
响应比=（等待时间+要求服务时间）/要求服务时间
非抢占式
进程主动放弃CPU时，需要该算法选取就绪队列的作业
不会饥饿
2.2_5 时间片轮转、优先级调度、多级反馈队列（适合交互式系统）
1、时间片轮转算法（RR）
算法思想：公平轮流地位各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列对位重新排队。
只能用于进程调度
抢占式
优点：响应块，适用于分时操作系统
缺点：由于高频率的进程切换，因此有一定的开销；不区分任务的紧急程度
不会饥饿
2、优先级调度算法
算法思想：根据任务的紧急程度来决定处理顺序
算法规则：每个进程/作业有各自的优先级，调度时选择优先级最高的作业/进程
适用：作业/进程/IO
抢占式/不可抢占均有
静态优先级：不变
动态优先级：可以变
通常：系统进程优先级高于用户进程，前台进程优先级高于后台进程，操作系统更偏好I/O进程
可以从追求公平、提升资源利用率等角度考虑改变优先级
可能会饥饿
3、多级反馈队列调度算法
算法思想：对其它算法调度的这种权衡
算法实现：设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。新进程到达时先进入第一级队列，按照FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列对位。如果此时已经在最下级的队列，则重新放回最下级队列末尾。啊只有第K级队头的进程为空时，才会为K+1级对头的进程分配时间片，被抢占处理机的进程重新放回原队列队尾。
优点：对各个进程相对公平（FCFS的优点），每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可以完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、IO密集型进程
默认抢占式，会饥饿