由于第四章线程的介绍没有上传视频，故之后看书来补。
最近开始学习操作系统原理这门课程，特将学习笔记整理成技术博客的形式发表，希望能给大家的操作系统学习带来帮助。同时盼望大家能对文章评论，大家一起多多交流，共同进步！
本篇文章大致内容为：
- 基本概念(Basic Concept)
- 调度准则(Scheduling Criteria)
- 调度算法(Scheduling Algorithm)
- 实时调度(Real-Time Scheduling)
- 算法评价(Algorithm Evaluation)
基本概念(Basic Concept)
通过多道程序设计可以尽可能高的提高CPU利用率，但道数不可能无限增加。
同时： 宏观－程序进入内存，被操作系统调度； 微观－进程正在CPU上运行(Running)
调度：切换的过程中，切换越多，系统消耗越多，故道数不可能无限增加（另外还有内存方面的考虑）
CPU－I/O Burst Cycle CPU-I/O执行期
- 进程执行包括一系列的CPU执行期和输入输出等待期
CPU执行期分布：为指数型或多阶指数型
CPU型程序：大部分时间用在CPU上的程序
I/O型程序：大部分时间用在I/O上的程序
CPU调度（进程调度，低级调度，短程调度） CPU Scheduler
选择内存上的处于就绪状态的进程，并分配CPU给它们使用（依照算法）。
什么时候进行CPU调度？或CPU调度的时机：
- Switches from running to waiting state
- Switches from running to ready state
- Switches from waiting to ready state:就绪队列来了新进程。
- Switched from waiting to ready state
注：1和4为非剥夺式／非抢占式(nonpreemptive)的，2和3为剥夺式／抢占式(preemptive)的。
调度程序(Dispatcher)
调度程序将CPU的控制权交给就绪队列中选中的进程，包括：
- switching context 上下文切换（中断现场的保存与恢复）
- switching to user mode 切换到用户态（PSW最高位），用户态：非特权指令；系统态：非特权指令＋特权指令
- jumping to the proper location in the user program to restart that program 跳转到程序上一次中断前执行的语句的上一行
调度延时(Dispatch latency)
换下一个进程并换上另一个新进程所需的时间，也叫系统消耗(overload)
调度准则(Scheduling Criteria)
- CPU利用率(CPU utilization)
- 吞吐量(Throughout)：单位时间内执行作业的数量。
- 周转时间(Turnaround time)：提交完毕->执行结束所需时间。
- 等待时间(Waiting time)：在就绪队列内等待的时间，多次等待时间做和。
- 响应时间(Response time)：提交完成->首次给出相应所需时间。
周转时间的组成：后备等待＋就绪队列等待时间之和＋运行时间之和＋阻塞队列等待时间之和
优化准则(Optimization Criteria)：对于相同作业而言，
- Max CPU utilization CPU利用率最大化
- Max Throughput 单位时间最大吞吐量
- Min turnaround time 最小化周转时间
- Min waiting time 最小化等待时间
- Min response time 最小化响应时间
调度算法(Scheduling Algorithms)
- First-Come,First-Served(FCFS)：先来先服务的调度原则
- Shortest-Job-First(SJF) Scheduling：短作业优先调度原则
- Priority Scheduling：优先级调度原则
- Round-Robin Scheduling：时间块调度原则
- Multilevel Queue Scheduling：多级队列调度原则
- Multilevel Feedback Queue：多级反馈队列调度原则
FCFS Scheduling
Gantt Chart：甘特图
SJF Scheduling：选择下一次CPU执行期最短的进程执行，分为两种，nonpreemptive 非抢占式的 和 preemptive 抢占式的。
抢占式－Shortest-Remainging-Time-First(SRTF) 最短剩余时间优先
SJF可以获得最小的平均等待时间。
Example of Non-Preemptive SJF:
Example of Preeptive SJF:
确定下一次CPU执行期的长短(Determining Length of Next CPU Burst)
只能估计时间，可以使用指数平均法：
两种极端：
通常情况：
优先级调度(Priority Scheduling)
- 每一个进程都有一个优先级
- CPU调度给优先级最高的进程
- 优先级调度可以分为
- 可抢占式的(Preemptive)
- 不可抢占式的(Nonpreemptive)
SJF也是一类优先级算法。
存在问题：Infinite blocking(Starvation) 饥饿：优先级低的进程会被无限推迟。
解决方法：Aging（熬），可变优先级，动态优先级
时间片轮转(Round Robin, RR)
time slice - 时间片
- 每个进程都会得到一个CPU时间段（通常10～100milliseconds）
- 时间片到后，进程被抢占并被放入就绪队列的末尾
- 若有n个进程且时间片长度为q，则每个进程都会获1/n的CPU时间，并且每次执行不超过q，则没有进程会等待超过(n-1)q个时间片
性能：若q比较大，则等待时间长；若q比较小，则每个进程等待时间短，但上下文切换所需的系统消耗会变大，q必须大于上下文切换的中断时间否则系统不能正常运行。
多级队列排队 Multilevel Queue
就绪队列被分成两个队列，前台队列用于交互式进程，使用RR调度，后台队列用于批处理进程，使用fcfs调度，后台队列保证前台有比较快的响应。
多级反馈队列 Multilevel Feedback Queue
- 有多个队列，每个队列有不同的优先级
- 所有新进程都入最高优先级队列
- 按照Round Robin情况调度最高优先级队列一次，若进程完成则释放内存结束进程，否则将该进程降入次高级进程
- 当最高优先级队列为空时，用RR调度次高优先级队列
- 当调度优先级为*的队列内加入新进程时，若系统为抢占式调度，则当前进程进入中断，并回到当前队列的队尾。
多级反馈队列为一种综合性调度：多级+RR+优先级+SJF+FCFS
算法评价 Algorithm Evaluation
- 确定模型 Determining modeling
- 队列模型 Queueing modeling
- 使用仿真的方式评价（最常用）：在公共的平台基于同样的一组公共数据对算法进行评价。