并发与并行
并发：从逻辑上讲是同时进行，但实际上是快速交替执行，只需要单核CPU即可实现 并行：是物理上在同时执行，真正的多个程序在同一时间同时运行，必须要多个CPU才可以实现程序的执行特点
CPU周期和I/O周期交替 如果任务串行执行，会导致效率低 程序运行时有大量时间在等I/O，如果CPU傻等就浪费了，调度策略是当任务A在等I/O时，操作系统立刻把CPU给B任务用，灯A设备准备好了再切回来运行A什么时候触发CPU进入内核态？系统调用，中断，异常
系统调用是进程or线程主动请求服务，是用户程序执行指令发起的 中断是硬件信号导致的（如时钟，键盘，磁盘完成等），由外部硬件发起 异常因为程序出错，由CPU检测到错误引起调度
为什么要调度？
多任务竞争使用CPU，需要对他们进行协调调度的基本要求
主要目标： 提升CPU利用率 在不同进程快速切换，使多个进程可以分时共享CPU资源 调度器要在合适的时间点，从就绪的进程中选择下一个在CPU上执行的进程调度发生的情况：
1.当前进程（或者线程）阻塞（非抢占，是进程主动请求） 2.当前进程（或线程）终止（非抢占，是进程主动结束） 3.当前进程（或线程）被中断，是可抢占点，时间片用完 4.进程被唤醒（或者线程），是可抢占点，可能被唤醒的进程优先级更高，剥夺当前进程进程A切换为进程B的情况与过程：
时间片用完 ：是被动切换，类型：中断 进程A发起I/O请求：是主动的，类型：系统调用 进程A申请内存：是主动的，类型：系统调用 进程A调用sleep()：是主动的，类型：系统调用 进程A调用yield:是主动的，类型：系统调用 进程A终止：是主动的，类型：系统调用 更高优先级进程变为就绪：是被动的，类型：中断非抢占点：
系统调用引发切换的完整过程：
进程转入终止态：
进程A在用户态运行>进程A发起exit系统调用>cpu进入内核态>回收进程A的资源>进程A状态变为终止态>调度器从就绪队列选中进程B>恢复B的上下文>cpu变为用户态运行进程B
进程阻塞： 进程A在用户态运行>进程A发起系统调用>CPU切换为内核态>保存A的上下文>执行内核服务代码>进程A需要等服务完成，状态变为阻塞，移出CPU>调度器从就绪队列中选入进程B>恢复进程B的上下文>CPU 切换为用户态，运行进程B可抢占点：
中断引发切换（进程时间片用完）： 进程A在用户态运行>硬件发送中断信号>CPU切换为内核态>将进程A的上下文保存>CPU执行操作系统内核中的中断代码>操作系统判定进程A的时间片用完后，>进程A变为就绪态移出cpu>调度器从就绪队列中选中进程B>恢复进程B的上下文>CPU 转为用户态，运行进程B 更高级别进程被唤醒： 进程B运行>进程A的磁盘I/O任务完成，硬件发中断信号>CPU进入内核态>中断处理,将等I/O的进程A由阻塞队列移动到就绪队列>调度器检查：进程A和B的优先级哪个更高>A 优先级更高>B变为就绪态并移出CPU>恢复进程A的上下文>cpu变为用户态>运行进程A ==注意：系统调用或者系统中断都不一定导致进程切换，只有当系统调用引发阻塞或者进程终止或者进程主动yield(进程主动让出CPU有，转去就绪队列）的时候才会切换，系统中断只有当前进程时间片用完或者被抢占时才会触发切换==调度开销
调度需要CPU从用户态转为内核态，保存原进程上下文，用调度器选中新进程，恢复新进程上下文，CPU从内核态转为用户态，加上地址空间切换就是完整的调度开销调度算法的评价指标
CPU利用率： 吞吐率：单位时间内完成的进程（任务数）数。完成的任务数除以完成这些任务的总用时 周转时间：进程完成时间-进程提交时间， 等待时间：进程被建立后等待被服务的时间，（算的是排队等CPU的时间）（应用场景在批处理系统） 响应时间：从发出服务请求到请求被满足的时间跨度（响应的终点实时系统开始给出反馈，而非全部完成）（是分时系统中的关键调度指标）CPU调度算法
FCFS
先来先服务，实现方式： 用一个FIFO队列来维护就绪进程 每次从FIFO队列取一个队首进程投入运行 新进入就绪态的进程放到队尾FCFS的护航效应
在这个调度算法中，一个长进程先到，所有后面的短进程被迫排队等待，平均等待时间大幅拉长短作业优先SJF
每次调度时优先选择下一个CPU周期最短的进程 以平均等待时间为指标的话，这是最优调度SJF的长进程饥饿问题
SJF总是优先短进程，如果段金册灰姑娘持续到大，长进程永远被排在后面，饿死最短剩余时间优先（SRTF）
可以视作SJF的抢占式版本 每次有新进程加入就绪队列，就需要进行一次重新调度 所有就绪进程与正在运行进程，都要进行一次剩余执行时间的比较，剩余时间最短的进程得到调度 意味着当前正在运行的进程可能会被剩余时间更短的进程抢占优先级调度
每个进程都被赋予一个优先数 每次调度时优先级最高的任务被选中执行 分抢占式和非抢占式最响应比优先调度
选取就绪队列中响应比最高的进程投入运行 响应比计算：（等待时间+要求服务时间）÷要求服务时间轮转调度
这是分时系统中的基础调度算法
1.系统将所有就绪进程按照到达时间的先后次序排成一个队列
2.进程调度程序总是选择这个就绪队列中的第一个进程执行，但是每次都只运行一个时间片
3.在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出CPU给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队等待再次运行
其目标是将CPU时间公平的分配给系统中的进程
*假设确定当前就绪队列的进程数为n，时间片为q,那么可以预计当前运行进程的最坏响应时间Rt=(n-1)q
为了保证见户型，q的值不可以设置的过大
多级队列调度(MLQ)
优先级队列
操作系统有很多任务，系统设置优先级区间，会存在多个任务属于同一优先级的情况,比如说优先级为1的任务组成一个队列，优先级为2的任务组成1个队列多级队列调度设计思路
1.不同的队列可以用不同的算法管理；比如将进程分为前台交互就绪序列和后台批处理队列，前台进程调度使用RR算法，后台进程调度使用FCFS算法 2.为不同的队列分配大小不同的时间配额；多级队列调度的优点与缺点
优点：
不同类型队列自由端则调度算法; 可以为不同类别的进程队列分配不同的时间配额缺点：
进程被固定于特定优先级序列，不便于动态调控; 高优先级队列中的进程具有优势，低优先级队列中的进程容易面临饥饿问题多级反馈队列调度（MLFQ）
针对多级队列调度（MLQ）的两个问题做了改进 设置了多个不同优先级的就绪进程队列，并且允许为每个队列设置不同的调度算法或者参数 MLFQ会持续分析进程的运行行为，并允许必要时对进程进行优先级调整，（允许进程在不同优先级队列中移动）主流操作系统都采用MLFQ算法作为核心算法
CPU调度
从串行模式开始考虑：在限定进程按照串行执行模式，那么调度问题转化为就绪队列的排序模式；但是串行执行的话效率太低 为什么需要调度？： 如果一个应用从一开始就是多进程方式设计，那么并发/并行会是基本选项，不会考虑串行执行 我们从队列的角度看进程：全体进程队列包含了就绪队列和等待队列（运行态的进程不在任何队列中，但仍然在全体进程队列中）操作系统中的三种调度层次：
长程调度：
是作业调度；所有待处理作业放在磁盘上的作业池，长程调度器从作业池中选取作业，选中的作业加载到内存，进入就绪队列中程调度：
内存紧张时，将就绪队列中的进程换出到磁盘；内存充裕时，将原本换出的进程从从盘中重新换回就绪队列短程调度：
CPU调度，从就绪队列中选进程，分配COPU执行，就是FCFS，SJF，RR等算法上下文切换：
记住一点即可：中断或者系统调用时，CPU从用户态切换为内核态的第一件事是将原本正在运行的进程状态保存到其PCB中；选中一个进程到CPU运行的第一件事是，从其PCB中恢复其状态到CPU进程上下文的细分：
1.用户及上下文：进程共享地址信息，包括代码、数据、用户栈堆、共享内存区 2.寄存器上下文：是进程的当前CPU运行状态，包括通用寄存器，栈寄存器，处理器状态寄存器，栈指针 3.系统及上下文：是操作系统管理进程的数据结构，包括进程控制块、内存管理信息、内核栈线程切换主要换的是寄存器上下文，用户及和系统级的大部分共享信息
进程切换三层全换，尤其是系统级的页表
Linux系统的CFS（完全公平调度器）调度算法
基本思想：让多个进程公平分享CPU时间 将CPU时间的分配像得到CPU时间少的任务倾斜 CFS通过vruntime来记录任务获取CPU时间的量 Vruntime= 实际运行时间*1024/任务权重 优先级高的任务，其虚拟时钟比真实时钟慢，反而获得较多的运行时间 优先级小的任务虚拟时钟比真实时钟快，获得较少的运行时间 调度器每次都选择Vruntime最小的任务执行问题
降低优先级的合理时机是？
时间片用完时；说明该进程已经充分利用了CPU资源，降低其优先级让其他进程有机会运行，符合公平调度原则
关于抢占式调度的缺点
系统开销大
满足段任务优先且不会发生饥饿现象的调度算法是
高响应比优先
优先级调度中的饥饿问题怎样解决
1.低优先级进程在就绪队列中的等待时间越长，优先级逐渐提升
2.高优先级在时间片用完后将优先级降低来让出机会
3.根据进程的行为（I/O密集型/CPU密集型）动态改变优先级
4.设置优先级上线，防止有些进程永远优先级最高
5.同优先级进程轮转，高优先级优先但不能独占
