处理机调度概念与调度准则
概念
挑选进程/线程的内核函数（通过一些调度策略）使得效率最高，满足用户需求
时机：抢占式调度与不可抢占式调度
内容：内核态抢占和用户态抢占
准则
快：用户响应要快，单进程执行要快
公平：进程间要公平
调度算法
先来先服务（FCFS）
队列，先进先出
简单，但是功能也简单，性能差
短进程优先（SPN、SJF）
按运行时间排序
最小的平均等待时间和周转时间
导致长任务饥饿，不能保证公平，需要预知进程的时间
最高响应比优先（HRRN）
（w+s）/s ；等待时间越长，优先级越高
防止进程饥饿，交互性，响应性更好
对抢占性的支持不够，也需要预知进程的时间
时间片轮转
时间片结束时切换到下一个的进程，经常排序仍采用FCFS
公平，相对稳定
平均等待时间较长，额外的上下文切换
多级反馈队列（很好的算法）
多级队列：把就绪队列划分成过个独立子队列
多级队列满足不同任务的需求，但优先级固定，可能导致饥饿
执行时间越长，优先级越低，分的时间片越大
继承了时间片轮转和多级队列的优点后，完美解决了时间片轮转的缺点（上下文 切换的开销），多级队列的缺点（进程饥饿）
公平共享调度
在多级队列上，再次优化而来
按权重分配资源，未达到配额的享有优先享有权
实时调度
含义：必须在规定时间完成规定任务
分类
硬实时系统/强实时系统：如果某个任务没完成有严重后果
软实时系统/弱实时系统：重要的进程优先级更高，要尽量完成
调度算法
静态优先级调度（速率单调调度算法）:周期越短，优先级越高
动态优先级调度（最早截止时间优先算法）:截止时间越早，优先级越高
多处理器调度
各自调度，共享资源访问需同步
静态进程分配：
进程创建时分配，分配后就在一个处理机上运行到死，一个处理机一个就绪队列
开销小，但处理器间分配不均
动态进程分配：
所有处理机共享一个就绪队列
调度开销大，但处理机的负载均衡
优先级反转
形成原因：A占用资源a，B占用资源b，C需要a，A需要b，但B>A,结果A在等B，C在等A。但C>B>A,违反了优先级法则
解决方案
优先级继承：当一个任务阻塞了若干个任务时，若阻塞任务有高优先级任务，则将所有阻塞任务中的最高优先级作为其优先级
优先级天花板：类似优先级继承，只不过继承的不是最高级，而是事先设定的可能达到的最高级