也称 CPU 调度算法：CPU空闲时，操作系统给内存中「就绪」进程分配 CPU
1、什么时候会发生CPU调度？进程从 运行 转到 1等待 / 2就绪 / 4终止 状态，3等待转就绪
1 和 4 「非抢占式」：完成当前运行，才让cpu
2 和 3 「抢占式调度」：可被打断，把 CPU 让出。分时间片、优先权、短作业优先原则
ps：2 通常是时间片，时间片到了就中断，抢占运行进程，从而占CPU
2、调度算法影响等待时间（就绪队列中等调度时间总和），不影响进程用 CPU 和 I/O 时间
3、常见调度算法：1先来先服务、2最短作业优先、3高响应比优先、4时间片轮转、5最高优先级、6多级反馈队列
一、先来先服务调度算法（First Come First Severd, FCFS ）
最简单，非抢占式：选最先进队列的进程，运行到进程退出或被阻塞，从队列中选第一个接着运行
ps：但当长作业先运行，短作业等待时间长，不利于短作业
适用：CPU 繁忙型作业系统，不适用： I/O 繁忙型作业系统
二、最短作业优先调度算法（Shortest Job First, SJF）
选运行时间最短进程，提高吞吐量
对长作业不利，造成极端，长作业长期不会被运行
三、高响应比优先调度算法（（Highest Response Ratio Next, HRRN））
权衡长短作业：计算「响应比优先级」，把最高进程投入运行
公式说明：
「等待时间」相同，「要求服务时间」越短，「响应比」越高，短作业易被选中
「要求的服务时间」相同，「等待时间」越长，「响应比」就越高，兼顾长作业，因响应比可随等待时间增加而提高，等待足够长，响应便升高，获得运行的机会
四、时间片轮转调度算法
使用最广，最古老、简单、公平且的算法
1、每个进程被分配一个时间片（Quantum），允许该时间段运行
时间片用完，进程还运行，把进程从 CPU 释放，CPU 分配出去
时间片结束前结束，CPU 立即切换
2、时间片长度很关键：太短过多进程上下文切换，降低CPU效率；太长对短作业响应时间变长；通常 20ms~50ms折中值。
五、最高优先级调度算法（Highest Priority First，HPF）
多用户系统，希望调度有优先级，选最高运行
1、静态优先级：创建进程时，确定优先级，不会变
2、动态优先级：根据动态变化调整，如果运行时间增加，则降低优先级，就绪队列等待时间增加，升高，就是随时间推移增加等待进程优先级。
两种处理分，非抢占式和抢占式。
缺点，低优先级永不运行
六、多级反馈队列调度算法（Multilevel Feedback Queue）
「时间片轮转算法」和「最高优先级算法」综合和发展。
多级：多个队列，优先级高到低，优先级越高时间片越短
反馈：新优先级高加进来，立刻停止当前运行
如何工作
1）新进程，放到第一级队列末尾，先来先服务排队等待被调度，
2）第一级队列时间片内没运行完，转第二级队列末尾
3）运行时，有新高，停止运行，移入原队列末尾
4）短作业可能在一级很快被处理完。长作业，一级处理不完转移，虽然等待时间变长，但运行时间更长
兼顾了长短作业，同时有较好响应时间
https://mp.weixin.qq.com/s/JWj6_BF9Xc84kQcyx6Nf_g
网友评论