OS:处理机进程调度

1.BackGround：为什么要进行进程调度？

        在多进程环境下，内存中存在着多个进程，其数目往往多于处理机核心数目。这就要求系统可以按照某种算法，动态的将处理机CPU资源分配给处于就绪状态的进程。调度算法的实质其实是一种资源分配策略。进程调度一般可以分为抢占式与非抢占式。

Note：进程的状态可以分为创建状态->就绪状态->运行状态->等待状态(IO或其他阻塞事务) 其实还有一个挂起状态，IO时切换至内核态等待完成事件，此时可以直接挂起进程，事件完成唤醒进程，执行其他用户指令。

创建状态 -> 就绪状态 -> 运行状态 -> 等待状态 -> 就绪状态 -> 运行状态 -> 挂起状态
                                   ^             |                   |               |
                                   |             v                   v               v
                               终止状态      挂起状态-> 就绪挂起状态 <-> 等待挂起状态
 

2.调度算法的目标

如何选择调度算法类型与其设计目标有关，例如批处理系统、实时系统，需要具体问题具体分析。

总体目标有以下方面：

（1）资源利用率：与CPU繁忙程度有关

（2）公平性：尽量避免进程饥饿现象。主要考虑长作业进程跟短作业进程如何平衡资源分配。

（3）平衡性：多种类型进程例如计算密集型进程、IO密集型进程需要保持资源使用的平衡性。

（4）安全性：安全策略只要需要就必须强制优先执行。

3.调度算法

（1）FCFS(First Come First-served)先来先服务调度算法

        顾名思义，选择就绪队列中最先进入的分配CPU资源执行；类似先来后到；

        缺点：短作业有可能不可以及时响应，如果其前方有一个长作业的话。

（2）SFJ(short job first)短作业优先调度算法

        SFJ使用作业进程的服务事件计算优先级，服务时间越短，优先级越高。

        缺点:长作业饥饿，有可能被无限期延后。

                有时无法准确预估作业所需时间，如果判断失误会出现问题。

                人机无法实时交互。

（3）HRRN（Highest Response Ratio Next）高相应比优先调度算法

        其本质是先来先服务与短作业优先的这种，（1）（2）无法兼顾短作业与长作业；

        定义一个相应比（优先权）= 1 + 等待时间/要求服务时间

        当等待时间相同时，服务时间越短优先级越高，体现短作业优先；

        当服务时间相同时，等待时间越长优先级越高，可以兼顾长作业；

        缺点：使用该算法，有计算相应比的开销；

（4）时间片轮转调度算法

        Round-Robin系统根据FCFS策略将所有就绪进程排列成一个就绪队列，设置一个时间片，时间到了产生一个中断，激活调度程序将CPU分给队首进程。难点在于确定时间片长度。

（5）多级反馈队列调度算法(multieved feedback queue)

        设置多个就绪队列，每个队列赋予不同优先级，优先级高的时间片短，优先级低的时间片长；默认先执行优先级高队列中的Task采用FCFS算法，执行完毕再执行下一优先级；如果时间片耗尽未执行完则优先级降级，将其加入下一等级队列尾部。