©2020-2024 ioDraw All rights reserved,
Privacy Policy
CPU调度：控制、协调进程对CPU的竞争；按一定的调度算法，从就绪序列里选一个进程，把CPU的使用权交给被选中的进程；如果没有就绪进程，系统会安排一个系统空闲进程或idle进程；
系统场景：N个进程就绪、等待上CPU运行；M个CPU，M>=1；需要决策：给哪个进程分配哪个CPU
CPU调度要解决的3个问题：what：按什么原则原则下一个要执行的进程，调度算法；when：合适选择，调度时机；how：如何让被选中的进程上CPU运行，调度过程(进程的上下文切换)
CPU调度时机：事件发生—-当前运行的进程暂停—-硬件机制响应后—-进入操作系统，处理相应的事件—-结束处理后：某些进程的状态会发生变化，也可能又创建了一些新的进程—-就绪队列改变了—-需要进程调度根据预设的调度算法从就绪队列选一个进程。包括下面4个情况：
进程正常终止 或 由于某种错误终止
新进程创建 或 一个等待进程变成就绪
当一个进程从运行态进入等待态
当一个进程从运行态变为就绪态
调度过程——进程切换：一个进程让出CPU，另一个进程占用CPU的过程；包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复。切换时要做的两件事：
1 切换全局页目录 以 加载一个新的地址空间
2 切换内核栈和硬件上下文，其中硬件上下文包括了内核执行新进程需要的全部信息，如CPU相关寄存器
上下文切换具体步骤：进程a下CPU，进程b上CPU
保存进程a的上下文环境(程序计数器、程序状态字、其他寄存器)
用新状态和其他相关信息更新进程a的PCB
把进程a移至合适的队列(就绪、阻塞。。)
将进程b的状态设置为运行态
从进程b的PCB中恢复上下文(程序计数器、程序状态字、其他寄存器。。)
上下文切换开销：直接开销：内核完成切换所用的CPU时间；间接开销：高速缓存cache、缓冲区缓存、TLB失效
CPU调度算法衡量指标：
吞吐量：每单位时间完成的进程数目
周转时间：每个进程从提出请求到运行完成的时间
响应时间：从提出请求到第一次回应的时间
其他:CPU利用率，CPU做有效工作的时间比例；等待时间，每个进程在就绪队列中等待的时间
进程优先级(数)：
优先级，反映紧迫程度；
优先数，反映优先级，UNIX优先数小的优先级高；
静态、动态优先级。等待久的动态优先级高
抢占与非抢占：
抢占：有高优先级进程就绪时，系统可以强行剥夺优先级低的进程的CPU给高优先级的进程先用
不可抢占：除非自身放弃CPU，否则一直运行
I/O密集型和CPU密集型：
I/O密集型，I/O型，频繁进行I/O，通常会花很多时间等待I/O操作完成；一般的输入输出程序对i/o更友好
CPU密集型，需要大量的CPU时间进行计算
时间片
一个时间段，分配给调度上CPU的进程，允许该进程运行的时间长度
如何选择时间片：考虑进程切换开销、对响应时间的要求、就绪进程个数、CPU能力、进程的行为
批处理系统中采用的调度算法：先来先服务、最短作业优先、最短剩余时间优先、最高响应比优先
算法选择原则：吞吐量、周转时间、CPU利用率、公平服务
先来先服务FCFS：先进先出，按照进程就绪的先后顺序使用CPU，非抢占
公平，实现简单，长进程后的短进程需要等很长时间，不利于用户体验
最短作业优先SJF：具有最短完成时间的进程优先执行，非抢占
最短剩余时间优先SRTN：就是sjf的抢占式版本，当一个新就绪的进程比当前运行进程具有更短的完成时间时，系统抢占当前进程，选择新就绪的进程执行
短作业优先调度算法：最短的平均周转时间(前提是所有进程同时可运行时)；不公平(源源不断的短任务到来，可能使长的任务长时间得不到运行，产生饥饿现象
最高响应比优先HRRN：折中权衡，先来先服务和短作业优先的取长补短
调度时，先计算每个进程的响应比R；之后，总是选择R最高的进程执行
响应比R=周转时间/处理时间=(处理时间+等待时间)/ 处理时间 = 1+(等待时间/处理时间)
交互式系统中采用的调度算法：轮转调度、最高优先级调度、多级反馈队列，最短进程优先；追求指标：响应时间、公平平衡；
时间片轮转调度算法：目标：为短任务改善平均响应时间，解决周期性切换，每个进程分配一个时间片，时钟中断–轮换。
如何选择合适的时间片：太长–大于典型的交互时间–退化成先来先服务算法，延长短进程的响应时间；太短–小于典型的交互时间–进程切换浪费CPU时间；经验值50ms左右；
时间片轮转算法优缺点：公平、有利于交互式计算、响应时间快、由于进程切换，时间片轮转算法要花费较高的开销、RR对不同大小的进程是有利的，但是对于大小相同的进程可能就不利了
虚拟轮转算法：所有I/O型进程，从等待变成就绪时，进入辅助队列，调度算法在选择进程时，首先从辅助队列选择进程，直到辅助队列为空，再去执行就绪队列，改善了时间片轮转算法对I/O型进程的不公
最高优先级调度算法：
选择优先级最高的进程投入运行；
系统进程一般高于用户进程；前台进程一般高于后台进程；操作系统更偏好i/o型进程；
优先级可以是静态的，也可以是动态变化的：优先数可以决定优先级
就绪队列可以安札优先级组织
实现简单；不公平，容易导致优先级低的进程产生饥饿现象
优先级反转问题：
基于优先级的抢占式：一个低优先级进程占有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行；
影响：系统错误；高优先级进程停滞不前，导致系统性能降低
解决方案：
(1)设置优先级上限：凡是进入临界区的进程，给它个高的优先级，便于先执行完，把临界区的控制权还回去，不进临界区的，给个低优先级；
(2)优先级继承：低的阻碍了高的，他可以继承这个高的优先级，先把任务执行完，把临界区还回去
(3)使用中断禁止：凡是进入临界区的进程就不再响应中断了，直到他出了临界区才响应中断，就保护了这个进程，让他去执行，直到把临界区还回去
多级反馈队列调度算法：
设置多个就绪队列，第一级队列优先级最高
给不同就绪队列中的进程分配长度不同的时间片，第一级队列时间片最小，级别降低，时间片变长
第一级队列为空是，在第二级队列调度，以此类推
每个队列都按照时间片轮转方式进行调度
当一个新创建进程就绪后，都进入第一级队列
当进程用完时间片，而放弃CPU，进入下一级就绪队列
由于阻塞而放弃CPU的进程进入
各种调度算法对比
FCFS
Round Robin
SJF
SRTN
HRRN
Feedback
多处理器调度算法设计：
不仅要决定选择哪个进程执行，还要决定在哪个CPU上执行；
要考虑进程在多个CPU之间迁移时的开销，应该尽可能使进程总是在同一个CPU上执行，考虑负载均衡问题
典型操作系统所采用的的调度算法：
UNIX：动态优先数法
5.3BSD：多级反馈队列法
Linux：抢占式调度
Windows：基于优先级的抢占式多任务调度
Solaris：综合调度算法
Linux调度算法的演化过程：
Linux2.4简单的基于优先级调度
Linux2.6 O(1)调度算法
Linux2.6 SD调度器补丁
Linux2.6 RSDL调度器补丁
Linux2.6 CFS调度算法(完全公平调度算法)
Windows的线程调度：
调度单位是线程(因为Windows系统支持内核级线程)
采用基于动态优先级的、抢占式调度，结合时间配额的调整
基本思想：
就绪线程按照优先级进入不同的就绪队列
操作系统总是选择优先级最高的就绪线程运行
同一优先级的各线程按时间片轮转进行调度
多CPU系统中允许多个线程并行运行
Windows线程调度：
引发条线程调度的条件：一个线程的优先级改变了
一个线程改变了他的亲和处理机集合
线程正常终止 或 由于某种错误终止
新线程创建 或 一个等待线程变成就绪
当一个线程从运行态进入阻塞态
当一个线程从运行态变成就绪态
线程优先级：
windows使用32个线程优先级，分成3类：
16-31：实时优先级线程，一旦确定就不改变优先级了
1-15：可变优先级：可以在一定范围内提升或降低，分为基本优先级、当前优先级
0：零页线程：用于对系统中空闲物理页面清零
时间配额：多给点时间配额，就像是给某个进程多点时间运行
Windows线程调度策略：
主动切换
抢占：当线程被抢占时，它被放回相应优先级的就绪队列的队首；处于实时优先级的线程被抢占时，时间配额被重置为一个完整的时间配额，再次上CPU运行的时候运行的是一个完整的时间配额；处于可变优先级的线程在被抢占时，时间配额不变，重新得到CPU后将运行剩余的时间配额。区别出两种不同类型的线程
时间配额用完：1
2
3线程a的优先级没有降低：如果队列中有其他就绪线程，选择下一个线程执行，a回到原来就绪队列末尾；如果队列中没有其他就绪线程，系统给线程a重新分配一个新的时间配额，让他继续运行；
线程a的优先级降低了：Windows将选择一个更高优先级的线程去运行；
线程优先级提升与时间配额调整：1
2
3提升线程的优先级
给线程分配一个很大的时间配额
提升线程的优先级：(只针对可变优先级线程)1
2
3
4
5
6
7
8
9I/O操作完成
信号量或时间等待结束
前台进程中的线程完成一个等待操作
由于窗口活动而唤醒窗口线程
线程处于就绪态超过了一定的时间还没有被调度运行(产生了饥饿现象)