1.1 课程概述

• 基本概念及原理
• 操作系统介绍
• 中断及系统调用
• 内存管理
• 进程及线程
• 调度
• 同步
• 文件系统
• I/O子系统

1.2 什么是操作系统

• 用户角度上，操作系统是一个控制软件
  管理应用程序
  为应用程序提供服务
  杀死应用程序
• 对内部管理而言
  资源管理
  管理外设、分配资源
• 操作系统架层次结构
  硬件之上，应用程序之下

1.2.1 kernel－操作系统内部组件

• CPU调度器
• 物理内存管理
• 虚拟内存管理
• 文件系统管理
• 中断处理与设备驱动
• OS kernel 的特征
  并发：一段时间内，有多个程序可以同时运行，需要OS管理和调度
  并行：一个时间点，（多个CPU）
  共享：分时访问，互斥共享
  虚拟：利用多道程序设计技术，让每个用户觉得有一个计算机为他服务
  异步： 程序的执行不是一贯到底，而是走走停停，向前推进的速度不可预知
  但是只要运行环境相同，OS需要保证程序运行的结果相同。

1.3 为什么要学习操作系统

顶级会议
SOSP
OSENIX
实际操作系统
Windows代码量巨大，不可能完全掌握
目标是要理解其核心内容
操作系统管理并发
操作系统代码管理原始硬件：时间依赖行为，非法行为，硬件故障。
操作系统代码必须是高效的：低耗CPU，内存，磁盘
操作系统出错，就意味着机器出错，OS必须比用户程序拥有更高的稳定性。
OS是系统安全的基础
操作系统需要权衡：

空间和时间
性能和可预测性
公平和性能
硬件方面，OS需要：

良好的硬件管理
合理的资源分配

1.4 操作系统的历史

早期计算机使用纸带传输程序和数据，OS只起到加载作用
CPU等硬件快速发展，计算机速度得到提升，性能为得到充分利用，成批／离线处理
内存的容量越来越大，CPU执行多个程序，多道程序设计
为了更好的利用计算机资源，并且更好的和用户交互，出现了分时系统。分时调度
网络的快速发展，出现了分布式的OS。松、紧耦合系统

1.5 操作系统的分类

• 批处理操作系统。

批处理是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。这种采用批量处理作业技术的操作系统称为批处理操作系统。批处理操作系统分为单道批处理系统和多道批处理系统。批处理操作系统不具有交互性，它是为了提高CPU的利用率而提出的一种操作系统。

• 分时操作系统。

利用分时技术的一种联机的多用户交互式操作系统，每个用户可以通过自己的终端向系统发出各种操作控制命令，完成作业的运行。分时是指把处理机的运行时间分成很短的时间片，按时间片轮流把处理机分配给各联机作业使用。

• 实时操作系统。

一个能够在指定或者确定的时间内完成系统功能以及对外部或内部事件在同步或异步时间内做出响应的系统,实时意思就是对响应时间有严格要求,要以足够快的速度进行处理.分为硬实时和软实时两种。

• 通用操作系统。

同时兼有多道批处理、分时、实时处理的功能，或者其中两种以上功能的操作系统。

• 网络操作系统。
  一种在通常操作系统功能的基础上提供网络通信和网络服务功能的操作系统。
• 分布式操作系统。
  一种以计算机网络为基础的，将物理上分布的具有自治功能的数据处理系统或计算机系统互联起来的操作系统。分布式系统中各台计算机无主次之分，系统中若干台计算机可以并行运行同一个程序，分布式操作系统用于管理分布式系统资源。
• 嵌入式操作系统
  一种运行在嵌入式智能芯片环境中，对整个智能芯片以及它所操作、控制的各种部件装置等资源进行统一协调、处理、指挥和控制的系统软件

2 中断 异常 系统调用

系统调用（来源于应用程序）
应用程序主动向操作系统发出服务请求
异常（来源于应用程序）
非法指令或其他坏的处理状态（如内存出错）
中断（来源于外设）
来自不同的硬件设备的计时器和网络的中断

2.1区别和特点

类型 源头 处理时间 响应
中断 外设 异步 持续，对用户应用程序是透明的
异常 应用程序意想不到的行为 同步 杀死或重新执行意想不到的应用程序指令
系统调用 应用程序请求提供服务 同步或异步 等待和持续

2.2 中断、异常和系统调用

（一）中断

硬件
设置中断标记（CPU初始化）
将内部、外部事件设置中断标记
中断事件的ID
软件（OS）
保存当前处理状态
中断服务程序处理
清除中断标记
恢复之前保存的状态
（二）异常：异常编号

保存现场
异常处理
杀死产生了异常的程序
重新执行异常指令
恢复现场
（三）系统调用

程序访问主要是通过高层次的API接口而不是直接进行系统调用
跨越操作系统边界的开销
在执行时间上的开销超过程序调用
开销：
建立中断/异常/系统调用号与对应服务例程映射关系的初始化开销
建立内核堆栈
验证参数
内核态映射到用户态的地址空间，更新页面映射权限
内核态独立地址空间，TLB（地址转换与安全保护）

7 进程和线程

• 进程（Process）描述
  进程定义
  进程的特点和组成
  进程控制结构
  进程状态（State）
  进程的生命周期管理
  进程创建
  进程运行
  进程等待
  进程唤醒
  进程结束
  进程状态变化模型
  进程挂起模型
• 线程（Thread）
  为什么使用线程
  什么是线程
  线程的实现
  用户线程
  内核线程
  轻量级线程
  多线程编程接口举例
  进程控制
  进程切换（上下文切换）
  进程创建
  进程加载
  进程等待与退出
  进程间通信（Inter-Process communication）
  进程互斥与同步
  死锁（Dead Lock）

7.1 进程的定义

一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

7.2 进程的组成

• 一个进程一个包括：
  程序的代码；
  程序处理的数据；
  程序计数器中的值，指示下一条将运行的指令；
  一组通用的寄存器的当前值，堆、栈；
  一组系统资源（如打开的文件）；
• 总之，进程包含了正在运行的一个程序的所有状态信息。
  进程与程序的联系
  程序是产生进程的基础
  程序的每次运行构成不同的进程
  进程是程序功能的体现
  通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序
  进程和程序的区别
  进程是动态的，程序是静态的
  程序是有序代码的集合；进程是程序的执行，进程有核心态/用户态
  进程是暂时的，程序是永久的
  进程是一个状态变化的过程，程序可长久保存
  进程与程序的组成不同
  进程的组成包括程序、数据和进程控制块（即进程状态信息）

7.3 进程的特点

动态性：可动态地创建、结束进程
并发性：进程可以被独立调度并占用处理机运行
独立性：不同进程的工作不相互影响
制约性：因访问共享数据/资源或进程间同步而产生制约
程序 = 算法 + 数据结构
描述进程的数据结构：进程控制块（Process Control Block，PCB）
操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息

7.4 进程控制块结构

进程控制块：操作系统管理控制进程运行所用的信息集合
操作系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标志
使用进程控制块
进程的创建：为该进程生成一个PCB
进程的终止：回收它的PCB
进程的组织管理：通过PCB的组织管理来实现
PCB含有以下三大类信息：
进程标识信息

如本进程的标识，本进程的产生者标识（父进程标识），用户标识
处理机状态信息保存区。保存进程的运行现场信息

用户可见寄存器，用户程序可以使用的数据、地址等寄存器
控制和状态寄存器，如程序计数器（PC）、程序状态字（PSW）
栈指针，过程调用/系统调用/中断处理/和返回时需要用它
PCB的组织方式
链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表

各状态的进程形成不同的链表：就绪链表、阻塞链表
索引表：同一状态的进程归入一个index表（有index指向PCB），多个状态对应多个不同的index表

各状态的进程形成不同的索引表：就绪索引表、阻塞索引表

7.5 进程的生命周期管理

进程创建
引起进程创建的3个主要条件：
系统初始化时
用户请求创建一个新进程
正在运行的进程执行了创建进程的系统调用
进程运行
内核选择一个就绪的进程，让它占用处理机并执行
如何选择？
为何选择？
进程等待
在以下情况下，进程等待（阻塞）：

请求并等待系统服务，无法马上完成
启动某种操作，无法马上完成
需要的数据未到达
进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生

进程唤醒
唤醒进程的原因：
被阻塞进程需要的资源可被满足
被阻塞进程等待的事件到达
将该进程的PCB插入到就绪队列
进程只能被别的进程或操作系统唤醒
进程结束
在以下四种情况下，进程结束：
正常退出（自愿的）
错误退出（自愿的）
致命错误（强制性的）
被其他进程所杀（强制性的）

7.6 进程状态变化模型

进程的三种基本状态：
运行状态（Running）：当一个进程正在处理机上运行时
就绪状态（Ready）：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行
等待状态（又称阻塞状态 Blocked）：一个进程正在等待某一时间而暂停运行时。如等待某资源，等待输入/输出完成
进程在生命结束前处于且仅处于三种状态之一
不同系统设置的进程状态数目不同
进程的其它的基本状态：
创建状态（New）：一个进程正在被创建，还没被转到就绪状态之前的状态
结束状态（Exit）：一个进程正在从系统中消失时的状态，这是因为进程结束或由于其他原因。
可能的状态变化如下：
Null -> New：一个新进程被产生出来执行一个程序
New -> Ready：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态（时间很短）
Ready -> Running：处于就绪状态的进程被进程调度程序选中后，就分配到处理机上来运行
Running -> Ready：处于运行状态的进程在其运行过程中，由于分配给它的处理机时间片用完而让出处理机（操作系统完成）
Running -> Blocked：当进程请求某样东西且必须等待时
Blocked -> Ready：当进程要等待某事件到来时，它从阻塞状态变到就绪状态

7.7 进程挂起

Why？合理且充分地利用系统资源
进程在挂起状态时，意味着进程没有占用内存空间。处在挂起状态的进程映像在外存中。
挂起状态
阻塞挂起状态（Blocked-suspend）：进程在外存并等待某事件的出现
就绪挂起状态（Ready-suspend）：进程在外存，但只要进入内存，即可运行；
与挂起状态相关的状态转换
挂起（suspend）：把一个进程从内存转到外存，可能有以下几种情况：
阻塞到阻塞挂起： 没有进程处于就绪状态或就绪状态进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程。
就绪到就绪挂起：当有高优先级阻塞（系统认为很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程。
运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态。
在外存时的状态转换：
阻塞挂起到就绪挂起：当有阻塞挂起进程因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程。
解挂/激活（Activate）：把一个进程从外存转到内存，可能会有以下几种情况：
就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换。
阻塞挂起到阻塞：当一个进程释放足够多内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞进程。
状态队列
由操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；
不同的状态分别用不同的队列表示（就绪队列、各种类型的阻塞队列）；
每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另外一个队列。

7.8 为什么使用线程：

案例 编写一个MP3播放软件

核心功能模块有三个：
从MP3音频文件当中读取数据；
对数据进行解压缩；
把压缩后的音频数据播放出来。
单进程实现方法
问题：
播出来的声音是否连贯？
各个函数之间不是并发执行，影响资源的使用效率
多进程实现方法
问题：
进程之间如何通信、共享数据？
另外，维护进程的系统开销较大：创建进程时，分配资源、建立PCB；撤销进程时，回收资源、撤销PCB
进程切换时，保存当前进程的状态信息
怎么来解决这些问题？
需要提出一种新的实体，满足以下特性：
实体之间可以并发地执行；
实体之间共享相同的地址空间
这种实体就是线程。

7.9 什么是线程

Thread：进程当中的一条执行流程
从两个方面来重新理解进程：
从资源组合的角度：
进程把一组相关的资源组合起来，构成了一个资源平台（环境），包括地址空间（代码段、数据段）、打开的文件等各种资源；
从运行的角度：
代码在这个资源平台上的一条执行流程（线程）。
线程 = 进程 - 共享资源
线程的优点
一个进程中可以同时存在多个线程
各个线程之间可以并发地执行且共享地址空间和文件资源
线程的缺点
一个线程崩溃，会导致其所属进程所有线程崩溃
不同OS对线程的支持
MS-DOS：单进程单线程
Unix：多进程单线程
Windows NT：多进程多线程（Linux）
线程与进程的比较
进程是资源分配单位，线程是CPU调度单位
进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈
线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系
线程能减少并发执行的时间和空间开销：
线程的创建时间比进程短；
线程的终止时间比进程短；
同一进程内线程切换时间比进程短；
由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信。

7.10 线程的实现

主要有三种线程实现方式：

• 用户线程：在用户空间实现；
  POSIX Pthreads,Math C-threads,Solaris threads

• 内核线程：在内核中实现；
  Windows，Solaris，Linux

• 轻量级线程：在内核中实现，支持用户线程；
  Solaris

• 用户线程与内核线程的对应关系
  多对一
  一对一
  多对多

• 用户线程
  在用户空间实现的线程机制，它不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建、终止、同步和调度等。
  由于用户线程的维护由相应进程来完成（通过线程库函数），不需要操作系统内核了解用户线程的存在，可用于不支持线程技术的多进程操作系统；
  每个进程都需要它自己私有的线程控制块（TCB）列表，用来跟踪记录它的各个线程的状态信息（PC、栈指针、寄存器），TCB由线程库函数来维护；
  用户线程的切换也是由线程库函数来完成，无需用户态/核心态切换，所以速度特别快
  允许每个进程拥有自定义的线程调度算法。
  用户线程缺点
  阻塞性的系统调用如何实现？如果一个线程发起系统调用而阻塞，则整个进程在等待；
  当一个线程开始运行后，除非它主动地交出CPU的使用权，否则它所在的过程当中的其他线程都无法运行；
  由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会较慢。

• 内核线程
  是指在操作系统的内核当中实现的一种线程机制，由操作系统的内核来完成线程的创建、终止和管理。
  在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息（PCB和TCB）；
  线程的创建、终止和切换都是通过系统调用/内核函数的方式来进行，由内核来完成，因此系统的开销较大；
  在一个进程中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行；
  时间片分配给线程，多线程的进程获得更多的CPU时间；
  Windows NT 和 Windows 2001/XP 支持内核线程。

• 轻量级进程（LightWeight Process）
  它是内核支持的用户线程。一个进程可有一个或多个轻量级进程，每个量级进程由一个单独的内核线程来支持。（Solaris/Linux）

8 处理机调度

处理机调度概念
处理机调度
处理机调度时机
调度准则
调度策略
比较调度算法的准则
调度算法

先进先服务算法（FCFS：First Come, First Served）
短进程优先算法
SPN: Shortest Process Next
SJF: Shortest Job First（短作业优先算法）
SRT: Shortest Remaining Time（短剩余时间优先算法）
最高响应比优先算法（HRRN: Highest Response Ratio Next）
时间片轮转算法（RR: Round Robin）
多级队列调度算法（MQ: Multilevel Queues）
多级反馈队列算法（MFQ: Multilevel Feedback Queues）
公平共享调度算法（FSS: Fair Share Scheduling）
实时调度

实时操作系统
可调度性
实时调度算法
速度单调调度算法（RM，Rate Monotonic)
最早截止时间优先算法（EPF，Earlist Deadline First）
多处理器调度
优先级反转

8.1 处理机调度

CPU资源的时分复用
进程切换：CPU资源的当前占用者切换

保存当前进程在PCB中的执行上下文（CPU状态）
恢复下一个进程的执行上下文
处理机调度

从就绪队列中挑选下一个占用CPU运行的进程
从多个可用CPU中挑选就绪进程可使用的CPU
调度程序：挑选就绪进程的内核函数
调度策略
调度时机
调度时机
内核运行调度程序的条件
进程从运行状态切换到等待状态
进程被终结了
非抢占系统
当前进程主动放弃CPU时
可抢占系统
中断请求被服务例程响应完成时
当前进程被抢占
进程时间片用完
进程从等待切换到就绪

8.2 调度准则

（一）调度策略

调度策略
确定如何从就绪队列中选择下一个执行进程
调度策略要解决的问题

挑选就绪队列中的哪一个进程？
通过什么样的准则来选择？
调度算法

在调度程序中实现的调度策略
比较调度算法的准则

哪一个策略/算法较好？
调度算法的考核指标
处理机资源的使用模式
进程在CPU计算和I/O操作间交替
在时间片机制下，进程可能在结束当前计算前被迫放弃CPU
（二）比较调度算法的准则

系统利用效率角度：
CPU使用率
CPU处于忙状态的时间百分比
吞吐量
单位时间内完成的进程数量
用户角度：
周转时间
进程从初始化到结束（包括等待）的总时间
等待时间
进程在就绪队列的总时间
交互性应用角度：
响应时间
从提交请求到产生响应所花费的总时间
吞吐量与延迟
调度算法的要求
希望“更快”的服务
什么是更快？
传输文件时的高带宽，调度算法的吞吐量
玩游戏时的低延迟，调度算法的低响应延迟
这两个因素是独立的
处理机调度策略的响应时间目标
减少响应时间
及时处理用户的输入请求，尽快将输出反馈给用户
减少平均响应时间的波动
在交互系统中，可预测性比高差异低平均更重要
低延迟调度改善了用户的交互体验
响应时间是操作系统的计算延迟
处理机调度策略的吞吐量目标
增加吞吐量
减少开销（操作系统开销，上下文切换）
系统资源的高效利用（CPU，I/O设备）
减少等待时间

减少每个进程的等待时间
操作系统需要保证吞吐量不受用户交互的影响

操作系统必须不时进行调度，即使存在许多交互任务
吞吐量是操作系统的计算带宽

处理机调度策略的公平性目标
公平的定义

保证每个进程占用相同的CPU时间
保证每个进程的等待时间相同
公平通常会增加平均响应时间

8.3 调度算法

（一）先进先服务算法（FCFS：First Come, First Served）

依据进程进入就绪状态的先后顺序排列
进程进入与等待或结束状态时，就绪队列中的下一个进程占用CPU
先进先服务算法的周转时间
例

3个进程，计算时间分别为12，3，3
任务到达顺序：P1，P2，P3

执行时间：| 0 | P1 | 12 | P2 | 15 | P3 | 18|
周转时间：（12+15+18）/3 = 15
任务到达顺序：P2，P3，P1

执行时间：| 0 | P2 | 3 | P3 | 6 | P1 | 18|
周转时间：（3+6+18）/3 = 9
先进先服务算法特征
优点

简单
缺点

平均等待时间波动较大

短进程可能排在长进程后面
I/O资源CPU资源的利用率较低

CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待
（二）短进程优先算法（SPN: Shortest Process Next）

选择就绪队列中执行时间最短进程占用CPU进入运行状态
就绪队列按预期的执行时间来排序
短进程优先算法特征
优点

具有最优的平均周转时间
缺点

可能导致饥饿

连续的短进程流会使长进程无法获得CPU资源
需要预知未来

如何预知下一个CPU计算的持续时间？
简单的解决办法：询问用户
用户欺骗就杀死相应进程
用户不知道怎么办？
短进程优先算法执行时间预估
用历史的执行时间来预估未来的执行时间

τn+1 = αtn + (1-α)τn，其中 0 <= α <= 1

tn：第n次的CPU计算时间
τn+1：第n+1次的CPU计算时间预估
短剩余时间优先算法（SRT: Shortest Remaining Time）
短进程优先算法的可抢占改进
（三）最高响应比优先算法（HRRN: Highest Response Ratio Next）

选择就绪队列中响应比的R值最高的进程
R = （w+s)/s

w：等待时间（waiting time）
s：执行时间（Service time）

在短进程优先算法的基础上改进

不可抢占
关注进程的等待时间
防止无限期推迟
（四）时间片轮转算法（RR：Round Robin）

时间片

分配处理机资源的基本时间单元
算法思路

时间片结束时，按先进先服务算法切换到下一个就绪进程
每隔（n-1）个时间片进程执行一个时间片q
例

时间片为20的时间片轮转算法示例
4个进程的执行时间如下：
P1：53，P2：8，P3：68，P4：24
甘特图如下：
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
20 28 48 68 88 108 112 125 145 153
等待时间：

P1：（68-20）+（112-88） = 72
P2：（20-0）= 20
P3：（28-0）+（88-48）+（125-108）= 85
P4：（48-0）+（108-68）=88
平均等待时间：（72+20+85+88）/4 = 66.25

时间片长度
时间片轮转算法开销：

额外的上下文切换（靠时钟中断强行把正在执行的进程结束掉）
时间片太大（进程响应时间）

等待时间过长
极限情况退化成先进先服务算法
时间片太小（系统开销）

反应迅速，但产生大量的上下文切换
大量上下文切换开销影响到系统吞吐量
时间片长度选择目标

选择一个合适的时间片长度
经验规则：维持上下文切换开销在1%以内
（五）多级队列调度算法（MQ: Multilevel Queues）

就绪队列被划分成多个独立的子队列

如：前台（交互）、后台（批处理）
每个队列拥有自己的调度策略

如：前台–RR，后台：FCFS
队列间的调度

固定优先级

先处理前台，然后处理后台
可能导致饥饿
时间片轮转

每个队列都得到一个确定的能够调度其进程的CPU总时间
如：80% CPU时间用于前台，20% CPU时间用于后台
（六）多级反馈队列算法（MFQ: Multilevel Feedback Queues）

进程可在不同队列间移动的多级队列算法
时间片大小随优先级增加而减小
如进程在当前时间片没有完成，则降到下一个优先级
多级反馈队列算法特征
CPU密集型进程的优先级下降很快（时间片大）
I/O密集型进程停留在高优先级（时间片小）
（七）公平共享调度算法（FSS: Fair Share Scheduling）

公平共享调度算法控制用户对系统资源的访问
一些用户组比其他用户组更重要
保证不重要的无法垄断资源
未使用的资源按比例分配
没有达到资源使用率目标的组获得更高的优先级（时间片减小）

8.4 实时调度

（一）实时操作系统

defs：正确性依赖于其时间和功能两方面的操作系统

性能指标：

时间约束的及时性（deadlines）
速度和平均性能相对不重要
特征：

时间约束的可预测性
实时任务
任务（工作单元）

一次计算、一次文件读取、一次信息传递等等
任务属性

完成任务所需要的资源
定时参数
周期实时任务
defs：一系列相似的任务

任务有规律的重复
周期 p = 任务请求时间间隔（ocp）
执行时间 e = 最大执行时间（ocecp)
使用率 U = e/p
硬时限（Hard deadline）

错过任务时限会导致灾难性或非常严重的后果
必须验证，在最坏情况下能够满足时限
软时限（Soft deadline）

通常能满足任务时限

如有时不能满足，则降低要求
尽力保证满足任务时限

（二）可调度性

defs：可调度表示一个实时操作系统能够满足任务时限要求
需要确定实时任务的执行顺序
静态优先级调度
动态优先级调度
（三）实时调度算法

速度单调调度算法（RM，Rate Monotonic)
通过周期安排优先级
周期越短优先级越高
执行周期最短的任务
最早截止时间优先算法（EPF，Earlist Deadline First）
截止时间越早优先级越高
执行截止时间最早的任务

8.5 多处理器调度

多处理器调度特征
多个处理机组成一个多处理机系统
处理机间可负载共享
对称多处理器（SMP，Symmetric multiprocessing)调度
每个处理器运行自己的调度程序
调度程序对共享资源的访问需要进行同步
对称多处理器的进程分配
静态进程分配
进程从开始到结束都被分配到一个固定的处理上执行
每个处理机有自己的就绪队列
调度开销小
各处理机可能忙闲不均
动态进程分配
进程在执行中可分配到任意空闲处理机上执行
所有处理机共享一个公共的就绪队列
调度开销大
多处理机的负载是均衡的

8.6 优先级反置（Priority Inversion）

操作系统中出现高优先级进程长时间等待低优先级进程所应用资源的现象
基于优先级的可抢占调度算法存在优先级反置
优先级继承（Priority Inheritance）
占用资源的低优先级进程继承申请资源的高优先级进程的优先级
只在占用资源的低优先级进程被阻塞时，才提高占用资源进程的优先级
优先级天花板协议（Priority ceiling protocol）
占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同
不管是否发生等待，都提升占用资源进程的优先级
优先级高于子系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会被阻塞

第3章：连续内存分配

3.1 地址空间与地址生成

（一）地址空间

物理地址空间–硬件支持的地址空间
逻辑地址空间–一个运行的程序所拥有的内存范围
（二）逻辑地址生成

.c file -> 编译 -> .s file -> 汇编 -> .o file -> 链接 -> .exe file -> 载入（程序重定位） -> 程序在内存中

（三）物理地址生成

CPU方面
运算器需要在逻辑地址内存内容
内存管理单元寻找在逻辑地址和物理地址之间的映射
控制器从总线发送在物理地址的内存内容的请求
内存方面
内存发送物理地址内存的内容给CPU
OS方面
建立逻辑地址和物理地址之间的映射

3.2 连续内存分配：内存碎片与分区的动态分配

（一）内存碎片问题

空闲内存不能被利用
外部碎片：在分配单元间的未使用内存
内部碎片：在分配单元中的未使用内存
（二）分区的动态分配

简单的内存管理方法

当一个程序准许运行在内存中时，分配一个连续的区间
分配一个连续的区间给运行的程序以访问数据
分配策略

首次适配
最优适配
最差适配
第一匹配适配
defs

为了分配 n 字节，使用第一个可用空闲块以致块的尺寸比 n 大
基本原理&实现

简单实现
需求：
按地址排序的空闲块列表
分配需要寻找一个合适的分区
重分配需要检查，看是否自由分区能合并于相邻的空闲分区（若有）
优势

简单
易于产生更大空闲块，向着地址空间的结尾
劣势

外部碎片
不确定性
最优匹配
defs

为了分配 n 字节，使用最小的可用空闲块，以致块的尺寸比 n 大
基本原理&实现

为了避免分割大的空闲块
为了最小化外部碎片产生的尺寸
需求：
按尺寸排序的空闲块列表
分配需要寻找一个合适的分区
重分配需要搜索及合并于相邻的空闲分区（若有）
优势

当大部分分配是小尺寸时非常有效
比较简单
劣势

外部碎片
重分配慢
易产生很多没用的微小碎片（不怎么好）
最差匹配
defs

为了分配 n 字节，使用最大可用空闲块，以致块的尺寸比 n 大
基本原理&实现

为了避免太多微小的碎片
需求：
按尺寸排序的空闲块列表
分配很快（获得最大的分区）
重分配需要合并于相邻的空闲分区（若有），然后调整空闲块列表
优势

假如分配是中等尺寸效果最好
劣势

重分配慢
外部碎片
易于破碎大的空闲块以致大分区无法被分配

3.3 连续内存分配：压缩式与交换式碎片整理

（一）压缩式碎片整理

重置程序以合并孔洞
要求所有程序是动态可重置的
（二）交换式碎片整理

运行程序需要更多的内存
抢占等待的程序&回收它们的内存

第4章：非连续内存分配
标签（空格分隔）： 操作系统

4.1 非连续内存分配：分段

（一）为什么需要非连续内存分配

连续内存分配的缺点
分配给一个程序的物理内存是连续的
内存利用率较低
有外碎片、内碎片的问题
非连续内存分配的优点
一个程序的物理地址空间是非连续的
更好的内存利用和管理
允许共享代码和数据（共享库等）
支持动态加载和动态链接
非连续分配：缺点
如何建立虚拟地址和物理地址之间的转换
硬件方案
软件方案：开销大
两种硬件方案
分段
分页
分段
程序的分段地址空间
分段寻址方案

段访问机制：一个段，一个内存“块”，一个逻辑地址空间

程序访问需要：
一个二维的二元组（s, addr） s：段号，addr：段内偏移
段寄存器+地址寄存器实现方案
单地址实现方案

4.2 非连续内存分配：分页

（一）分页

分页地址空间
页寻址方案
划分物理内存至固定大小的帧（frames），大小是2的幂，512,4196……
划分逻辑地址空间至相同大小的页，大小是2的幂，512,4196……
建立方案，转换逻辑地址为物理地址（page to frames）
页表
MMU/TLB
帧（Frame）
物理内存被分割为大小相等的帧
一个内存物理地址是一个二元组（f, o）
f：帧号（F位，共有2^F个帧）
o：帧内偏移（S位，每帧有2^S个字节）
物理地址：2^S * f + o
例

16bit 的地址空间，9bit（512bytes）大小的页帧，物理地址=（3,6）
物理地址：2^93+6=5123+6=1536+6=1542
页（page）
一个程序的逻辑地址空间被划分为大小相等的页
页内偏移大小 = 帧内偏移的大小
页号大小 帧号大小 （页表）
一个逻辑地址是一个二元组（p,o）
p：页号（P位，2^P个页）
o：页内偏移（S位，每页有2^S个字节）
虚拟地址：2^S * p + o
页寻址机制
页映射到帧
页是连续的虚拟内存
帧是非连续的物理内存
不是所有的页都有对应的帧

4.3 非连续内存分配：页表 - 概述、TLB

页表概述
转换后备缓冲区（TLB）
二级/多级 页表
反向页表
（一）分页机制的性能问题

问题：访问一个内存单元需要2次内存访问
一次用于获取页表项
一次用于访问数据
页表可能非常大
（二）Translation Look-aside Buffer (TLB) 快表

缓存近期访问的页帧转换表项
TLB使用associate memory（关联内存）实现，具备快速访问性能
如果TLB命中，物理页号可以很快被获取
如果TLB未命中，对应的表项被更新到TLB中

4.4 非连续内存分配：页表 - 二级/多级 页表

多级页表
通过把页号分为k个部分，来实现多级间接页表
建立页表“树”，以时间换空间

4.5 非连续内存分配：页表 - 反向页表

（一）大地址空间

有大地址空间（64bits），前向映射表变得繁琐
不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应
逻辑（虚拟）地址空间增长速度快于物理地址空间
基于寄存器（Page Registers）的方案
每个帧和一个寄存器关联，寄存器内容包括：
Residence bit：此帧号是否已被占用
Occupier：对应的页号P
Protection bits：保护位
页寄存器：一个例子
物理内存大小：40964096=4kB4kB=16MB
页面大小：4096Bytes
页帧数：4096=4k
页寄存器使用的空间（假设8 Bytes/register）：8*4096=32kBytes
页寄存器带来的额外开销：32K/16M = 0.2%（大约）
虚拟内存的大小：任意
页寄存器方案的权衡
利：
转换表的大小相对于物理内存来说很小
转换表的大小跟逻辑地址空间的大小无关
弊：
需要的信息对调了，即根据帧号找到页号
如何转换回来？即根据页号找到帧号
需要在反向页表中搜索想要的页号

第5章：虚拟内存

起因
覆盖技术
交换技术
虚存技术
目标
程序局部性原理
基本概念
基本特征
虚拟页式内存管理

5.1 虚拟内存的起因

理想中的存储器
更大、更快、更便宜的非易失性存储器
OS支持的存储器
更大、更快、更便宜好用的易失性存储器
内存不够用
程序太大，手动的覆盖（overlay）技术，只把需要的指令和数据保存在内存当中
程序太多，自动的交换（swapping）技术，把暂时不能执行的程序送到外存
想在有限的内存中，以更小的页粒度为单位装入更多更大的程序，采用自动的虚拟存储技术

5.2 覆盖技术

目标：是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用
原理：把程序按照自身逻辑结构，划分为若干个功能上相对独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来运行
必要部分（常用功能）的代码和数据常驻内存
可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中，在需要用到时才装入内存
不存在调用关系的模块不必同时装入内存，从而可以相互覆盖，即这些模块共用一个分区
缺点：
由程序员来把一个大的程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，费时费力，增加了编程的复杂度
覆盖模块从外存装入内存，实际上是以时间延长来换取空间节省

5.3 交换技术

目标：多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源
方法：
可将暂时不能运行的程序送到外存，从而获得空闲内存空间
操作系统把一个进程的整个地址空间的内容保存到外存中（换出swap out），而将外存中的某个进程的地址空间读入到内存中（换入swap in）。换入换出内容 的大小为整个程序的地址空间
几个问题
交换时机的确定：只有当内存空间不够或有不够的危险时换出
交换区的大小：必须足够大以存放所有用户进程的所有内存映像的拷贝；必须能对这些内存映像进行直接存取
程序换入时的重定位：换出后再换入内存位置一定要在原来的位置上吗？最好采用动态地址映射的方法
覆盖与交换的比较
覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内各个模块之间的逻辑覆盖结构
交换技术是以在内存中的程序大小为单位进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构。换言之，交换发生在内存中程序与管理程序或操作系统之间，而覆盖发生在运行程序的内部。

5.4.1 虚存技术（上）

目标：在内存不够用的情形下，可以采用覆盖技术和交换技术，但是

覆盖技术：需要程序员自己把整个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了程序员的负担。
交换技术：以进程为交换的单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销。
像覆盖技术一样，不是把程序的所有内容都放在内存中，因而能够运行比当前空闲内存空间还要大的程序。但做得更好，由操作系统自动来完成，无需程序员的干涉

像交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。但做得更好，只对进程的部分内容在内存和外存之间进行交换
程序的局部性原理
指程序在执行的过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域，可以表现为：

时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短时期内
空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在较小的区域内。
基本概念：

可以在页式或段式内存管理的基础上实现
在装入程序时，不必将其全部装入到内存，而只需将当前执行的部分页面或段装入到内存，就可以让程序开始执行
在程序执行过程中，如果需执行的指令或访问的数据尚未在内存中（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序
另一方面，操作系统将内存中暂时不使用的页面或段调出保存在外存上，从而腾出更多的空闲空间存放将要装入的程序以及将要调入的页面或段
基本特征：
大的用户空间：通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离
部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的
不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续

5.4.2 虚存技术（下）

虚存技术 - 虚拟页式内存管理
大部分虚拟存储系统都采用虚拟页式存储管理技术，即在页式存储管理的基础上，增加请求调页和页面置换功能
基本思路：

当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行
在运行过程中，如果发现要运行的程序或要访问数据不再内存，则向系统发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能够继续运行
页表表项：

逻辑页号i | 访问位 | 修改位 | 保护位 | 驻留位 | 物理页帧号 |
驻留位：表示该页是在内存还是在外存，如果该位为1，表示该页位于内存当中，即该页表项是有效的，可以使用；如果该位为0，表示该页当前还在外存当中，如果访问该页表项，将导致缺页中断
保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等
修改位：表明此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存
访问位：如果该页面被访问过（包括读操作或写操作），则设置此位。用于页面置换算法
缺页中断处理过程：
如果在内存中有空闲的物理页面，则分配一物理页帧f，然后转第4步；
采用某种页面置换算法，选择一个将被替换的物理页帧f，它所对应的逻辑页为q。如果该页在内存期间被修改过，则需把它写回外存；
对q所对应的页表项进行修改，把驻留位置为0；
将需要访问的页p装入到物理页面f当中；
修改p所对应的页表项的内容，把驻留位置为1，把物理页帧号置为f；
重新运行被中断的指令；
后备存储（Backing store）
在何处保存未被映射的页？
能够简单的识别在二级存储器中的页
交换空间（磁盘或文件）：特殊格式，用于存储未被映射的页面
概念：
一个虚拟地址空间的页面可以被映射到文件（在二级存储中）中的某个位置
代码段：映射到可执行二进制文件
动态加载的共享库程序段：映射到动态调用的库文件
其他段：可能被映射到交换文件（swap file）
虚拟内存性能
为了便于理解分页的开销，使用有效存储器访问时间（EAT）
EAT = 访存时间 * 页表命中几率 + page fault 处理时间 * page fault 几率
例

• 访存时间：10 ns
• 磁盘访问：5 ms
• 参数p = page fault 几率
• 参数q = dirty page 几率
• EAT = 10(1-p) + 5,000,000 p(1*q)

第6章：页面置换算法

功能与目标
实验设置与评价方法
局部页面置换算法
最优页面置换算法（OPT，optional）
先进先出算法（FIFO，First-In First-Out）
最近最久未使用算法（LRU，Least Recently Used）
时钟页面置换算法（Clock）
二次机会法
最不常用算法（LFU，Least Frequently Used）
Belady 现象
LRU、FIFO和Clock的比较
全局页面置换算法
工作集模型
工作集置换算法
缺页率置换算法

• （一）功能目标

功能：
当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置顶
目标：
尽可能地减少页面的换入换出次数（即缺页中断的次数），具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测
页面锁定（frame locking）：
用于描述必须常驻内存的操作系统的关键部分或时间关键（time - critical）的应用进程。实现的方法是：在页表中添加锁定标志位（lock bit）

6.1 最优页面置换算法（OPT，optional）

基本思路：
当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面
这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从得知每一个页面要等待多长时间以后才会再次被访问
可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次页面访问情况，在第二遍运行时即可使用最优置换算法）

6.2 先进先出算法（FIFO，First-In First-Out）

基本思路：
选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页淘汰出局，并把新的页面添加到链表的末尾。
性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象，FIFO算法很少单独使用。

6.3 最近最久未使用算法（LRU，Least Recently Used）

基本思路：

当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。
它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁地访问，那么在将来的一小段时间内，它们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问。
LRU算法需要记录各个页面使用时间的先后顺序，开销较大
两种可能的实现方法是：

系统维护一个页面链表，最近刚使用过的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首，如果没有，则直接插入到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。
设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。

6.4 时钟页面置换算法（Clock）

LRU的近似，对FIFO的一种改进
基本思路：
需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0.然后如果这个页面被访问（读/写），则把该位置为1；
把各个页面组织成环形链表（类似时钟表面），把指针指向最老的页面（最先进来）；
当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

6.5 二次机会法

这里有一个巨大的代价来替换“脏页”
修改Clock算法，使它允许脏页总是在时钟头扫描中保留出来
同时使用脏位和使用位来指导置换
used dirty used’ dirty’
0 0 replace page
0 1 0 0
1 0 0 0
1 1 0 1

6.6 最不常用算法（LFU，Least Frequently Used）

基本思路：
当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。
实现方法：
对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。在发生缺页中断时，淘汰计数值最小的那个页面。
LRU 和 LFU的区别：

LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频率，访问次数越多越好。
问题：

一个页面在进程开始时使用得多，但以后就不使用了。实现费时费力。
解决方法：

定期把次数寄存器右移一位

6.7 Belady现象

Belady现象：

在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象。
原因：

FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因为，被它置换出去的页面并不一定是进程不会访问的。

6.8 LRU、FIFO和Clock的比较

LRU算法和FIFO本质上都是先进先出的思路，只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次访问的时候动态地调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）；而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以各个页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就退化为FIFO算法。
LRU算法性能较好，但系统开销大；FIFO算法系统开销较小，但可能会发生Belady现象。因此，折中的办法是Clock算法，在每一次页面访问时，它不必去动态地调整该页面在链表中的顺序，而仅仅是做一个标记，然后等到发生缺页中断时，再把它移动到链表的末尾，对于内存中那些被访问过的页面，它不能像LRU算法一样，记住它们的准确位置。

6.9 工作集模型

（一）工作集

defs:
一个进程当前正在使用的逻辑页面集合，可以用一个二元函数 w(t,△）来表示
t 是当前执行时刻
△ 称为工作集窗口（working-set window），即一个定长的页面访问的时间窗口
w(t,△）= 在当前时刻t之前的 △ 时间窗口当中的所有页面组成的集合（随着t的变化，该集合也在不断的变化）
|w(t,△）|指工作集的大小，即页面数目|
（二）常驻集

defs:
是指在当前时刻，进程实际驻留在内存当中的页面集合
工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法
如果一个进程的整个工作集都在内存当中，即常驻集包含（=）工作集，那么进程将很顺利的运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）
当进程常驻集的大小达到某个数目后，再给它分配更多的物理页面，缺页率也不会明显下降

6.10 两个全局页面置换算法

（一）缺页率页面置换算法

可变分配策略：
常驻集大小可变。例如，每个进程在刚开始运行的时候，先根据程序的大小给它分配一定数目的物理页面，然后在运行过程中，再动态的调整常驻集的大小。
可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程当中，各个并发进程竞争地使用物理页面。
优缺点：

性能较好，但增加了系统开销
具体实现：

可以使用缺页率算法（PFF, Page fault frequency)来动态调整常驻集的大小
缺页率：

缺页率表示“缺页次数/内存访问次数”（比率）或“缺页的平均时间间隔的倒数”。
影响缺页率的因素：

页面置换算法
分配给进程的物理页面数目
页面本身的大小
程序的编写方法
缺页率算法
若运行的程序的缺页率过高，则通过增加工作集来分配更多的物理页面
若运行的程序缺页率过低，则通过减少工作集来减少它的物理页面数
力图使运行的每个程序的缺页率保持在一个合理的范围内
一个交替的工作集计算明确的适于最小化页缺失
当缺页率高的时候–增加工作集
当缺页率低的时候–减少工作集
算法：
保持追踪缺失发生概率
当缺失发生时，从上次页缺失起计算这个时间记录这个时间，t’last 是上次的页缺失时间
如果发生页缺失之间的时间是“大”的，之后减少工作集
如果 t’current - t’last > T，之后从内存中移除所有在[t’last,t’current]时间内没有被引用的页
如果发生页缺失之间的时间是“小”的，之后增加工作集
如果 t’current - t’last <= T，之后增加缺失页到工作集中

6.11 抖动问题(Trashing)

defs:
如果分配给一个进程的物理页面很少，不能包含整个的工作集，那常驻集含于工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存到外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为“抖动”。
产生抖动的原因：

随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以操作系统要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。
抖动问题可能会被本地的页面置换算法改善

更好的规则为加载控制：调整MPL
平均页缺失时间（MTBF, mean time between page faults)
页缺失服务时间（PFST，page fault service time）