计算机操作系统

¶一、操作系统结构

¶1、操作系统定义

• 从用户、控制的角度，操作系统是个控制软件，管理应用程序、为应用程序提供服务、杀死应用程序。
• 从资源分配的角度来说，操作系统进行资源管理、管理各种外设、对资源进行分配。
• 操作系统将物力资源进行抽象：CPU抽象成进程、磁盘抽象成文件、内存抽象成地址空间提供给应用程序使用。

¶2、操作系统地位

• 硬件之上、应用程序之下。是个中间层的系统软件。
• 操作系统位于应用软件之下、为应用软件提供服务支撑，完成对硬件的管理。
• 操作系统有两层对外的接口：对外暴露的接口外壳（Shell），和面向内部的内核（Kernel）。

¶3、操作系统分类

¶4、操作系统软件的组成

• shell：命令行接口，方便用户操作
• gui：图形用户接口
• kernel：内核，执行资源管理。

Kernel：操作系统内部组件，包括：CPU调度、物理内存管理、虚拟内存管理（给上层应用提供相对独立而且尽可能大的内存）、文件系统管理（存储和访问永久保存的数据）、中断处理与设备驱动（和底层设备直接打交道）等。

¶5、操作系统内核特征

• 并发：计算机系统中同时存在多个运行的程序，需要OS管理和调度。注意区分并发和并行。并发指的是在一段时间内有多个程序可以运行。并行指的是在一个时间点上有多个程序可以同时执行。要实现并行，一般要求有多个CPU。单核CPU无法实现并行。
• 共享：多个应用程序在宏观上可以“同时”访问内存、I/O等资源，但在微观可能是互斥的（同一个时间点，某些资源只能由一个程序使用）。
• 虚拟：利用多道程序设计技术，把一台物理机器虚拟成多台虚拟机器。让每个用户都觉得有一个计算机专门为他服务。
• 异步：程序的执行不是一贯到底，而是走走停停的，向前推进的速度不可预知，取决于系统的管理。但只要运行环境相同，OS需要保证程序运行的结果也要相同。

¶6、操作系统演变

主要功能：硬件抽象和协调管理

• 单用户系统
• 批处理系统：顺序执行和批处理
• 多道程序系统：顺序执行变为多道程序交替执行，多个作业，一个作业放弃CPU，另一个作业占用CPU执行
• 分时系统：前者基础上，交替条件变为时钟中断，操作系统管理控制时钟中断。利于短作业执行，CPU效率可能下降，但用户体验感更好！
• 个人计算机：这时效率不是重点，功能和安全才是
• 分布式计算机：网络的支持，高可用，高可靠，解耦

¶7、操作系统结构

• 简单结构：MS-DOS（1981-1994）不分模块的单体内核，接口和功能水平没有很好分离，主要使用汇编
• 分层结构：每一层都建立在低层次之上，仅使用更低一层的的功能和服务，最底层是硬件，最高层是用户
• 微内核结构：分层结构分层太多造成的效率低。尽可能把内核的功能移到用户空间。应用的服务通过消息传递机制的松耦合方式进行交互。灵活安全但性能下降。
• 外核结构：内核放更少的东西，只起到资源的保护和隔离作用，把资源的管理任务交给用户态的应用程序完成，原来操作系统的功能由用户态的函数库提供，程序链接到操作系统库libOS实现操作系统抽象。（类似VM虚拟机）
• VMM，虚拟机管理器：从操作 系统-硬件 变为 操作系统-VMM-硬件。多操作系统共享硬件资源。VMM负责资源的隔离，操作系统负责资源的管理

¶二、中断及系统调用

¶1、BIOS

¶启动时计算机内存和磁盘布局

• BIOS启动时系统处于实模式
• 第一条指令的位置就是代码段寄存器左移四位再加上指令指针寄存器。
• 加电时候，处于实模式，地址总线可用地址空间为20bit，即1MB

BIOS：Basic Input Output System，是一组固化到ROM上的程序，是个人电脑启动时加载的第一个软件

BIOS启动固件作用：

• 基本输入输出程序
• 系统设置信息
• 开机后自检程序
• 系统自启动程序

¶加载程序的内存地址空间

将加载程序从磁盘都引导扇区（512字节）加载到0x7c00，之后跳转到0x7c00，将操作系统的代码和数据从硬盘加载到内存中，跳转到操作系统的起始地址！

¶BIOS系统调用

BIOS以中断调用的方式提供了基本的I/O功能

• INT 10h：字符显示
• INT 13h：磁盘扇区读写
• INT 15h：检测内存大小
• INT 16h：键盘输入

只能在x86的实模式下访问

¶2、系统启动流程

¶计算机启动流程

¶CPU初始化

CPU加电稳定后从0XFFFF0读第一条指令

• CS:IP = 0xf000:fff0
• 第一条指令是跳转指令

CPU初始状态为16位实模式

• CS:IP是16位寄存器
• 指令指针PC = 16*CS+IP
• 最大地址空间是1MB

¶BIOS初始化过程

• 硬件自检POST
• 检测系统中内存和显卡等关键部件的存在和工作状态
• 查找并执行显卡等接口卡BIOS，进行设备初始化
• 执行系统BIOS，进行系统检测：检测和配置系统中安装的即插即用设备;
• 更新CMOS中的扩展系统配置数据ESCD
• 按指定启动顺序从软盘、硬盘或光驱启动

¶主引导记录MBR格式

共512字节

有硬盘分区表描述分区状态和位置，加载并跳转到磁盘上引导程序，跳到活动分区的引导分区，再跳转到加载程序！

启动代码：446字节

• 检查分区表正确性
• 加载并跳转到磁盘上的引导程序

硬盘分区表：64字节

• 描述分区状态和位置
• 每个分区描述信息占据16字节

结束标志字：2字节（55AA）

• 主引导记录的有效标志

¶分区引导扇区格式

• 跳转指令：跳转到启动代码，与平台相关代码
• 文件卷头：文件系统描述信息
• 启动代码：跳转到加载程序
• 结束标志：55AA

¶加载程序BootLoader

加载程序（bootloader）从文件系统中读取启动配置信息，根据配置去加载内核

¶系统启动规范

BIOS

• 固化到计算机主板上的程序
• 包括系统设置、自检程序和系统自启动程序BIOS-MBR、BIOS-GPT（全局唯一标识分区表，可大于四个分区）、PXE（网络标准分区）

UEFI

• 接口标准
• 在所有平台上一致的操作系统启动服务

UEFI：统一的可扩展固件接口(Unified Extensible Firmware Interface）再所有平台上一致的操作系统启动服务，对引导记录可行性进行检查！

¶X86启动流程

1.  X86 PC开机时，CPU处于实模式，这时候内存的计算方式是 段基址 <<4 + 段内偏移；
   

2.  CPU的第一条指令是通过CS：IP来取得，而此时CS=0xFFFF，IP=0x0000。这是硬件设定好的。
   

3.  所以最开始执行的指令地址就是0xFFFF0，放在这里的是个跳转指令，调到系统BIOS中真正的启动代码处：主板的BIOS ROM（只读存储区）中。
   

4.  系统BIOS的启动代码首先进行加电自检（POST，Power-On Self Test），检测系统中的一些关键设备是否存在和能否正常工作，例如内存和显卡等。
   

5.  寻找显卡的BIOS。
   

6.  将BootLoader加载到内存中。BootLoader一般放在硬盘的第一个主引导扇区，也就是磁盘0磁道0扇区（一般512个字节）。比如在X86中，BIOS将BootLoader加载在0x7cdd。
   

7.  之后BootLoader将操作系统的代码和数据从硬盘加载到内存中。
   

完成上述操作后，跳转到操作系统的起始地址，将计算机系统的硬件管理交给OS。

¶3、中断、异常、系统调用

为什么应用程序不能直接访问外设，而必须通过操作系统？

• 在计算机运行中，内核是被信任的第三方，而应用程序不是，如果直接访问外设，可能带来安全问题。
• 只有内核可以执行特权指令。
• 为了方便应用程序，给应用程序提供简洁的接口。

中断、异常、系统调用三者关系：

¶定义

• 异常：非法指令或其他原因导致当前指令执行失败（如内存出错）后的处理请求。
• 中断：来自不同的硬件设备的计时器和网络的中断（来源于外设，键盘、鼠标、网卡等，产生各种事件）。
• 系统调用：应用程序主动向操作系统发出都服务请求，来源于应用程序。异步或同步。

¶三者比较

源头

• 中断：外设
• 异常：应用程序意想不到的行为
• 系统调用：应用程序请求操作提供服务

响应方式

• 中断：异步，应用程序不知道什么时候会发生这件事。
• 异常：同步，由用户代码出错主动引起
• 系统调用：异步或同步，应用程序知道它什么时候会发出系统调用请求，所以发出请求是同步的，但应用程序不知道操作系统什么时候会返回一个结果，因此是异步的。应用程序需要等待系统调用的响应，之后才能继续执行。

处理机制

• 中断：持续，对用户应用程序是透明的
• 异常：杀死或者重新执行意想不到的应用程序指令
• 系统调用：等待和持续

¶中断处理机制

每种中断有个特定的编号（比如不同的外设会有不同的编号），收到中断后，CPU去访问中断表，在表中查到对应的中断服务程序的地址，从相应的地址去执行。

具体是通过硬件和软件两部分来执行的！

硬件处理

• 在CPU初始化时设置中断使能标志，即在许可外界打扰CPU的执行之前，CPU是不会对外界的任何中断请求发出响应的
• 依据内部或外部事件设置中断标志
• 依据中断向量调用相应中断服务例程

软件处理

• 现场保存（编译器)
• 中断服务处理(服务例程)
• 清除中断标记（服务例程)
• 现场恢复（编译器

¶中断嵌套

硬件中断服务例程可被打断

• 不同硬件中断源可能硬件中断处理时出现
• 硬件中断服务例程中需要临时禁止中断请求
• 中断请求会保持到CPU做出响应

异常服务例程可被打断

• 异常服务例程执行时可能出现硬件中断

异常服务例程可嵌套

• 异常服务例程可能出现缺页

¶异常

应用程序执行特定的指令会触发异常，CPU得到异常ID号。

首先保存现场，然后根据异常ID号进行处理。可能会杀死应用程序，也有可能进行弥补后，恢复现场，重新执行。

¶系统调用

• 操作系统服务的编程接口
• 通常由高级语言编写（C或者C+＋)
• 程序访问通常是通过高层次的API接口而不是直接进行系统调用
• 三种最常用的应用程序编程接口( API )
  • Win32 API用于Windows
  • POSIX API用于POSIX-based systems(包括UNIX、LINUX，Mac oS X的所有版本)
  • Java API用于JAVA虚拟机(JVM)

¶系统调用的实现

• 每个系统调用对应一个系统调用号
• 系统调用接口根据系统调用号来维护表的索引
• 系统调用接口调用内核态中的系统调用功能实现，并返回系统调用的状态和结果
• 用户不需要知道系统调用的实现
• 需要设置调用参数和获取返回结果
• 操作系统接口的细节大部分都隐藏在应用编程接口后
• 通过运行程序支持的库来管理

¶系统调用和函数调用的不同

系统调用

• INT和IRET指令用于系统调用
• 系统调用时，堆栈切换和特权级的转换

函数调用

• CALL和RET用于常规调用
• 常规调用时没有堆栈切换

系统调用开销大于函数调用

• 引导机制
• 建立内核堆栈验证参数
• 内核态映射到用户态的地址空间
• 更新页面映射权限
• 内核态独立地址空间，TLB

¶三、内存分配

¶0、连续内存分配

分配给一个程序的物理内存是连续的。

缺点：

• 内存利用率低
• 存在内碎片、外碎片的问题。
• 内存分配的动态修改困难
• 内存利用率较低

¶1、计算机体系结构和内存层次

¶计算机体系结构

CPU划分！

¶内存的层次结构

内存的层次结构研究的是，CPU能够访问的指令和数据所处的位置。

从上到下：

• 寄存器、cache，都位于CPU内部，CPU直接访问，操作系统不能对其进行直接管理，但速度很快，容量很少。
• 主存（物理内存）放置操作系统本身和运行的代码和数据。容量比cache和寄存器大，速度慢些。
• 磁盘：内存有时候不够大，需要把一些数据放在磁盘里（虚拟内存），并且把一些需要永久保存的数据（断电后也能保存下来）放在磁盘里。

¶操作系统的内存管理目标

• 抽象：逻辑地址空间，希望应用程序在运行中不需要考虑一些物理细节，只需访问一个连续的地址空间，我们称之为逻辑地址空间。
• 保护：独立地址空间，多个应用程序可能会因为某些原因去访问其他进程的空间，会破坏其他进程的空间。因此需要一个有效的机制去对他们的各自空间进行隔离、保护。
• 共享：访问相同内存，进程之间可能需要交互，通过提供共享空间，让进程之间可以安全、可靠、有效地进行数据的传递。
• 虚拟化：更大都地址空间，当内存不够的时候，为了让应用程序有足够空间运行，把最需要放在内存的数据放在内存中，暂时不需要的数据可以临时放在硬盘上，通过这个方法可以实现一个大的内存，这个过程对应用程序是透明的，程序看到的都是逻辑地址空间。

¶操作系统的内存管理方式

操作系统是个软件，它内存管理的实现高度依赖于硬件，比如MMU（内存管理单元）：硬件组件负责处理CPU的内存访问请求。

• 重定位 relocation：短地址 + 偏移
• 分段 segmentation：代码、数据、堆栈三段
• 分页 paging：比分段单位更小的结构
• 虚拟存储 virtual memory：目前多数系统采用按需方式虚拟存储

实现高度依赖硬件

• 与计算机存储架构紧耦合
• MMU(内存管理单元)：处理CPU存储访问请求的硬件

¶2、地址空间和地址生成

¶地址空间定义

两种地址空间：

• 物理地址空间：和硬件直接对应，如内存条所代表的主存和硬盘。物理空间的管理由硬件完成。
• 逻辑地址空间：一个运行的程序能看到的地址空间，是个一维的线性的地址空间。

¶逻辑地址生成

编译、汇编、链接函数库、重新加载重定位！

• 首先，将代码编译，成为汇编程序。在C代码中，程序，变量的地址其实就是逻辑地址。
• 汇编语言很多变量还是通过变量名来表示的。通过汇编器转化为机器语言（.o文件），机器语言中，起始地址都是从0开始，并且变量名和函数名都被转化为地址。
• Linker将多个.o程序链接为单个可执行的程序（.exe），存放在硬盘中。这个程序的地址已经是全局的分布了，不同的.o程序中变量的地址都已经在单一的程序中有相应的定义。
• Loader将硬盘中的可执行程序放在内存中的相应位置，此时将逻辑地址进行相应的分配，使得应用程序在内存中可以正常运行。程序在内存中存在一个偏移量，可以通过偏移量和逻辑地址，可以对程序进行正确的访问和指令的操作。

上面那些转化过程基本不需要操作系统的介入，只需编译器、linker、loader的配合即可完成。

¶地址生成时机和限制

编译时

• 假设起始地址已知
• 如果起始地址改变，必须重新编译

加载时

• 如编译时起始位置未知，编译器需生成可重定位的代码(relocatable code)
• 加载时，生成绝对地址

执行时

• 执行时代码可移动
• 需地址转换(映射)硬件支持

¶地址生成过程

CPU

• ALU：需要逻辑地址的内存内容
• MMU：进行逻辑地址和物理地址的转换
• CPU控制逻辑：给总线发送物理地址请求

内存

• 发送物理地址的内容给CPU或接收CPU数据到物理地址

操作系统

• 建立逻辑地址LA和物理地址PA的映射

逻辑地址如何映射到物理地址？

CPU中有个MMU，MMU完成从逻辑地址到物理地址的映射！

• 当CPU要执行指令时，ALU向MMU发出请求，带有逻辑地址；
• MMU查找逻辑地址的映射表中是否存在对应的物理地址。如果没有，在内存中找，如果找到了，CPU的控制器对主存发出请求。
• 主存把内容通过指令传给CPU，CPU拿到指令的内容后开始执行。操作系统在这期间的角色是，在执行指令之前，要把映射表建立好。

¶地址检查

如何保证放在内存的程序相互之间不能干扰？

要确保每个程序访问的地址空间是合法的，在一定的范围内：

¶3、连续内存分配

¶连续内存分配和内存碎片

连续内存分配：给进程分配一块不小于指定大小的连续的物理内存区域

内存碎片：空闲内存不能被利用

外部碎片：分配单元之间的未被使用内存

内部碎片：分配单元内部的未被使用内存，取决于分配单元大小是否要取整

¶动态分区分配

动态分区分配

• 当程序被加载执行时,分配一个进程指定大小可变的分区(块、 内存块)
• 分区的地址是连续的

操作系统需要维护的数据结构

• 所有进程的已分配分区
• 空闲分区(Empty-blocks)

动态分区分配策略

• 最先匹配(First-fit)
• 最佳匹配(Best-fit)
• 最差匹配(Worst-fit)

¶最先匹配策略

原理&实现

• 空闲分区列表按地址顺序排序
• 分配过程时，搜索第一个合适的分区
• 释放分区时，检查是否可与临近的空闲分区合并

优点

• 简单
• 在高地址空间有大块的空闲分区（因为是从头（低地址）开始找的）

缺点

• 外部碎片
• 分配大块时较慢（从头低地址优先被找，也是被切割掉使用的，大块空闲的少，后面的多）

¶最佳匹配策略

原理&实现

• 空闲分区列表按照大小排序
• 分配时，查找一一个合适的分区
• 释放时,查找并且**合并临近（指地址临近）**的空闲分区(如果找到)

优点

• 大部分分配的尺寸较小时，效果很好
• 可避免大的空闲分区被拆分
• 可减小外部碎片的大小（找最佳的）
• 相对简单

缺点

• 外部碎片
• 释放分区较慢（合并需要找地址临近，而排序不是按地址排的）
• 易产生很多无用的小碎片

¶最差分配策略

原理&实现

• 空闲分区列表按由大到小排序
• 分配时，选最大的分区
• 释放时，检查是否可与临近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序

优点

• 中等大小的分配较多时，效果最好
• 避免出现太多的小碎片

缺点

• 释放分区较慢（合并需要找地址临近，而排序不是按地址排的）
• 外部碎片
• 容易破坏大的空闲分区，因此后续难以分配大的分区

¶4、碎片整理

¶紧凑

碎片整理：通过调整进程占用的分区位置来减少或避免分区碎片

碎片紧凑：通过移动分配给进程的内存分区，以合并外部碎片

碎片紧凑的条件

• 所有的应用程序可动态重定位

需要解决的问题

• 什么时候移动：不为了一小块区域去移动
• 开销：移动的开销是巨大的

¶分区对换

通过抢占并回收处于等待状态进程的分区（将其临时放入外存，内存够用时在将其放入内存），以增大可用内存空间！

例如 Linux 的 Swap 分区！

¶5、伙伴系统

¶伙伴系统

• 整个可分配的分区大小 2^u
• 需要的分区大小为 2^u-1 < s ≤ 2^u 时，把整个块分配给该进程;
• 如 s ≤ 2^i-1，将大小为 2ⁱ 的当前空闲分区划分成两个大小为 2^i-1 的空闲分区
• 重复划分过程，直到 2^i-1 < s ≤ 2ⁱ , 并把一个空闲分区分配给该进程

这时候的内部碎片最大：可能为可分配分区大小的一半 - 1，这时所需空间为 可分配分区大小的一半 + 1

¶伙伴系统实现

数据结构

• 空闲块按大小和起始地址组织成二维数组
• 初始状态:只有一个大小为2U的空闲块

分配过程

• 由小到大在空闲块数组中找最小的可用空闲块
• 如空闲块过大，对可用空闲块进行二等分，直到得到合适的可用空闲块

释放过程

• 释放的块放入空闲块数组
• 合并满足合并条件的空闲块

合并条件

• 大小相同 2ⁱ
• 地址相邻
• 起始地址较小的块的起始地址必须是 2^(i + 1) 的倍数

¶6、非连续内存分配

分配给一个程序的物理地址空间是非连续的。

优点：

• 更好的内存利用和管理
• 允许共享代码与数据
• 支持动态加载和动态链接。

缺点：带来额外的管理开销：如何建立虚拟地址和物理地址之间的转换。两种实现：软件方案和硬件方案。

两种硬件方案：分段、分页。

¶7、非连续内存分配的需求背景

非连续分配需要解决的问题

• 如何实现虚拟地址和物理地址的转换
• 软件实现 (灵活，开销大)
• 硬件实现 (够用，开销小)

非连续分配的硬件辅助机制

• 如何选择非连续分配中的内存分块大小
• 段式存储管理( segmentation )
• 页式存储管理( paging )

¶8、段式存储管理

段式存储管理segmentation：将进程空间由多个段组成：数据、代码、堆栈，粒度比较大

算机的程序其实是由各种各样的段组成的，不同的段之间有不同的属性，比如主程序、子程序、各种库等。数据有栈段、堆段，共享数据段等。

所谓分段，就是根据应用程序不同段的特点，将它们区别出来，进行分离、管理。

段管理机制特点：

• 段的大小可以不一致
• 段可以有重叠
• 段可以有特权级
• 段与段之间是可以不连续的

¶段地址空间

进程的段地址空间由多个段组成

• 主代码段
• 子模块代码段
• 公用库代码段
• 堆栈段(stack)
• 堆数据(heap)
• 初始化数据段
• 符号表等

¶段地址空间的不连续二维结构

逻辑地址空间虽然是连续的，但通过一些特定的方法，把各种段分离出来，它们位于不同的区域，物理地址实际上是不同的。

比如，左边是连续的逻辑地址，右边是分离的，分成一块一块的物理地址空间。我们需要一个映射机制把逻辑地址空间映射到物理地址空间

¶段地址空间的逻辑视图

逻辑的连续变为了物理的不连续！

分段的管理机制可以用软件来实现，也可以用硬件。但软件实现的开销非常大，所以我们要考虑如何用硬件实现。

¶段访问机制

段的概念

• 段表示访问方式和存储数据等属性相同的一段地址空间
• 对应一个连续的内存“块”
• 若干个段组成进程逻辑地址空间

段访问：逻辑地址由二元组(s, addr)表示

• s-段号
• addr-段内偏移

逻辑地址实际上是一维的，那我们如何把一维的逻辑地址跟物理地址对应？

可以将一维的地址分成两部分，一部分是段寻址，一部分是段内偏移的寻址。具体来说有如下图的两种寻址方式。

¶段访问的硬件实现

段号去段表找基址，加上偏移就是物理地址

X86使用的是段寄存器+地址寄存器实现方案。

• 从左上角开始看。当CPU在执行某条指令的时候，需要进行寻址（找数据，代码等），此时CPU得到的是一个逻辑地址。CPU将逻辑地址按照前半部分段号和后半部分偏移分开。
• 首先希望根据段号得到段所在物理内存的起始地址。这时候需要使用段表。
• 段表中存放了一个对应关系，那就是逻辑地址的段号和物理地址的对应关系。
• 另外，由于每个段的大小是不一样的。我们需要了解每个段的长度限制，这也要存在段表中。
• 段表有个索引，索引的每一项就是由段号决定的。
• 这样就可以根据段号，在段表中查到段对应的物理内存的起始地址，以及大小的限制。
• 找到之后，CPU比对这个大小限制和逻辑地址（通过Limit Register），看是否满足条件。如果不满足条件，就产生一个异常。
• 如果在合理区间之内，将起始地址和偏移量相加，得到一个实际的物理地址。

段表是操作系统在正式寻址之前建立好的。

¶9、页式存储管理

分段机制现在用得比较少，绝大部分现代计算机都用的分页机制。

分页机制跟分段类似，也需要一个页号和页内偏移量。分页跟分段的一个最大区别是，页的大小是不变的。

¶页面和页帧

页帧（帧、物理页面,Frame,Page Frame )

• 把物理地址空间划分为大小相同的基本分配单位
• 2的n次方，如512，4096，8192

页面(页、逻辑页面,Page )

• 把逻辑地址空间也划分为相同大小的基本分配单位
• 帧和页的大小必须是相同的

页面到页帧转换

• 逻辑地址到物理地址的转换
• 页表
• MMU/TLB（最大内存单元和快表）

¶帧

物理内存被分割为大小相等的帧!

一个内存物理地址是一个二元组(f, o)

• f-帧号(F位,共有2^F个帧)
• o-帧内偏移(S位,每帧有2^S字节)

物理地址 = 2^S x f + o

2^S 就是一个页帧大小！

下面有个地址计算的实例

¶页

计算方式跟前面是类似的。但因为这是逻辑地址，因此页号跟物理地址对应的帧号可能会不一样，但每一页的大小，以及页内偏移跟帧是一样的。

¶页式存储的地址映射

逻辑地址到物理地址的转换！

页到帧的映射

• 逻辑地址中的页号是连续的
• 物理地址中的帧号是不连续的
• 不是所有的页都有对应的帧

页表：保存了逻辑地址到物理地址之间的映射关系

• 跟前面分段的方法一样，首先CPU得到逻辑地址，逻辑地址分成两块，一块表示页号，一块表示页内偏移地址。跟前面一样，有一个页表，页表的索引就是页号，内容是帧号。我们可以通过页号查找到对应的帧号，帧号加上偏移，就能得到物理地址，找到物理地址对应的内存空间。
• 页表是由操作系统建立的。操作系统在操作系统初始化的时候，enable分页机制的时候就建立好了。
• 页寻址的好处就在于，页内偏移量和帧内偏移量一样，页跟帧的大小是一样的，这样就不用像段寻址那样还要去判断段内偏移是否合法，方便实现。
• 另外，逻辑地址空间是个连续的空间，但通过页寻址，映射到物理空间中，就不是连续的了，分散在不同的帧中。好处是有助于减少碎片。
• 有一种情况是，逻辑地址空间大于物理空间的时候，需要考虑虚拟内存。

¶10、页表

¶页表结构

页表其实就是个大数组。索引是页号，索引所对应的页表项存放的就是帧号。

每个进程都有一个页表

每个页面对应一个页表项随进程运行状态而动态变化

页表基址寄存器(PTBR: Page Table Base Register)：用来存储页表的起始位置

页表项组成：

• 存在位(resident bit)
• 修改位(dirty bit)
• 引用位(clock/reference bit)
• 只读位(read only OR read/write bit)

¶地址转换实例

• 首先看逻辑地址（4,0），首先通过页号4，在页表中找到相应的项（从下往上数，从0开始）。此时对应图中靠上的位置，标志位Flags为100，中间的resident bit存在位为0. resident bit为0，表示这个页在物理内存中不存在对应的帧，此时返回一个异常。
• 再看（3,1023），通过页号3，找到了相应的项，标志位为011，resident bit存在位为1，可以找到对应的帧。对应的帧号为00100，也就是帧号为4。偏移量跟逻辑地址的页偏移量一样，因此就可以找到对应的物理内存地址。

¶分页机制的性能问题

内存访问性能问题

• 访问一个内存单元需要2次内存访问
• 第一次访问：获取页表项
• 第二次访问：访问数据

页表大小问题

• 页表可能非常大
• 64位机器如果每页1024字节，那么一个页表的大小会是多少?

2⁶⁴ / 1024 = 2⁵⁴ 个页表项！

每个页表项占64位，即8个字节，不考虑页表项的标志位，则 2⁵⁴ * 8 = 2⁵⁷ 个字节占用！

每个应用程序都要维护一个页表，那就更加耗费空间了。

另外，页表特别大，所以页表没办法放在CPU里，只能放在内存中，两次内存访问性能会急剧下降！

如何处理?

• 缓存( Caching )（即快表）
• 间接(Indirection )访问（即多级页表），通过间接引用建立页表树
• 页寄存器：让页表与物理地址相对应，根据物理帧号寻找逻辑页号：逻辑地址进行hash变换->快表中找页表项
• 反置页表：类似页寄存器，把进程id也考虑进来：逻辑地址+pid进行hash变换->反置页表中找页表项

¶11、快表和多级页表

解决引入页表带来的问题！

¶快表

CPU中的内存管理单元（MMU）里，有Translation Look-aside Buffer（TLB），转换后备缓冲区，缓冲的是页表的内容。TLB是CPU内部特殊的一块区域，TLB的表项由Key 和Value组成。

缓存近期访问的页表项

• TLB使用关联存储(associative memory)实现，具备快速访问性能
• 如果TLB命中，物理页号可以很快被获取
• 如果TLB未命中，对应的表项被更新到TLB中

TLB是用一种相关存储器实现的，是一种快速查询存储器，可以并发地查找，但实现的代价很大，所以容量是有限的。可以把当前经常访问的页表项放到页表中。当CPU得到逻辑地址的时候，先去查TLB，当查找到的时候，就可以快速地访问到对应的物理内存。

当TLB里查不到的时候，只能去页表里查。如果页表里有对应项的存在位为1，就将那一项取回来放在TLB里（X86中，这一过程是用硬件实现的，而有些CPU，如MIPS则是靠软件实现的）。这样，最常用的就会留在TLB里。

在TLB找不到的情况不会很频繁，比如32位系统中，一个页为4k字节，一般访问4k次才会产生一个缺失，这是可以接受的。为了让TLB找不到的情况尽量少出现，设计程序的时候可以让程序具有访问的局部性，让大部分的访问都集中在一个区域中。

TLB可以让寻址的时间开销得到极大的降低。

¶多级页表

TLB提高了页表访问的速度。而为了缓解页表占据太多空间的问题，使用了多级页表。

可有效应对大地址空间！

通过一级页号作为下标在一级页表找到二级页表的偏移，加上逻辑地址的二级页表页号得到三级页表的偏移…

为什么说二级/多级页表可以节省空间？

第一，如果一级页表中的第一个PTE（分页）是空的，那么相应的二级页表就根本不会存在（有存在位标志为标志），这代表着一种巨大的潜在节约，因为对于一个典型的程序，比如4GB,8GB的虚拟地址空间的大部分都将是未匹配的。

第二，只有一级页表才需要总是在主存中；虚拟存储器系统可以在需要时创建，页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中，这种离散的存储方式是非常便利的。这就是多级页表的一个根本性的优点：可以离散存储。（单级页表为了随机访问必须连续存储，如果虚拟内存空间很大，就需要很多页表项，就需要很大的连续内存空间，但是多级页表不需要）

**使用多级页表可以减少每个进程的页表所需的内存。为什么节省了呢？**从你最终要存储的表项来看，无论如何你存储的表项是不会少的（都要用到这么多内存），而且多级页表还会增加存储开销。

其实是这样的，二级表只是从进程的角度来看，为进程节省了页表项（其实所有的页表存储空间增大了）。二级模式通过只为进程实际使用的那些虚拟内存区请求页表来减少页表，就是进程未使用的页暂时可以不用为其建立页表，因为如果使用一级页表的话，你就必须为所有的4G范围内分配页表，不能细分。每个活动进程必须有一个分配给它的页目录，不过没必要马上为进程的所有页表都分配ram，只有在进程实际需要一个页表时才给该页表分配ram，这样就提高了效率。

¶12、反置页表

解决引入页表带来的问题！

随着程序越来越大，逻辑（虚拟）地址空间的增长速度远快于物理地址空间。反向页表要解决的是大地址空间的问题，不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应。

反向页表跟前向映射页表的映射关系相反，以物理页号（帧）作为索引来查找对应的逻辑页页号。

¶大地址空间问题

对于大地址空间(64-bits)系统，多级页表变得繁琐

• 比如:5级页表
• 逻辑(虚拟)地址空间增长速度快于物理地址空间页

寄存器和反置页面的思路

• 不让页表与逻辑地址空间的大小相对应、
• 让页表与物理地址空间的大小相对应

¶基于页寄存器的方案

让页表与物理地址相对应，根据物理帧号寻找逻辑页号：逻辑地址进行hash变换->快表中找页表项

每个帧与一个页寄存器(Page Register)关联，寄存器内容包括：

• 使用位(Residence bit)：此帧是否被进程占用
• 占用页号(Occupier)：对应的页号p
• 保护位(Protection bits)：可读可写状态

页寄存器示例

• 物理内存大小：4096 * 4096 = 4K * 4KB =16 MB
• 页面大小：4096 bytes = 4KB
• 页帧数：4096= 4K
• 页寄存器使用的空间(假设每个页寄存器占8字节)：8 * 4096 = 32 Kbytes
• 页寄存器带来的额外开销：32K/16M= 0.2%(大约)
• 虚拟内存的大小：任意，与之无关，只是物理页面和页寄存器的对应

使用页寄存器的最大问题是，如何根据页号来找到对应的帧号？（要注意，页寄存器的索引是帧号，并不是页号）。

优点

• 页表大小相对于物理内存而言很小
• 页表大小与逻辑地址空间大小无关

缺点

• 页表信息对调后，需要依据帧号可找页号
• 在页寄存器中搜索逻辑地址中的页号（很困难）

¶页寄存器上的地址转换

CPU生成的逻辑地址如何找对应的物理地址?

• 对逻辑地址进行Hash映射，以减少搜索范围
• 需要解决可能的冲突

用快表缓存页表项后的页寄存器搜索步骤（优化）

• 对逻辑地址进行Hash变换
• 在快表中查找对应页表项
• 有冲突时遍历冲突项链表
• 查找失败时，产生异常

快表的限制

• 快表的容量限制（快表容量很小）
• 快表的功耗限制(StrongARM上快表功耗占27%)

¶基于反置页表方案

类似页寄存器，把进程id也考虑进来：逻辑地址+pid进行hash变换->反置页表中找页表项！

可有效应对大地址空间！

基于Hash映射值查找对应页表项中的帧号

• 进程标识与页号的Hash值可能有冲突
• 页表项中包括保护位、修改位、访问位和存在位等标识

无论有多少个进程，反向页表在内存中只需要一个，不需要像正向实现那样，每个进程都要有一个页表。

¶13、段页式存储管理

• 段式存储在内存保护方面有优势
• 页式存储再内存利用效率和优化转移到后备存储方面有优势

在段式存储管理都基础上，给每一个段加一级页表

逻辑地址->段表->页表->物理地址

段页式存储管理中的内存共享

通过指向相同的页表基址，实现进程间的段共享

不同进程的段表中的共享段，指向相同的页表项

¶四、虚拟存储

¶1、虚拟存储需求

程序规模的增长速度远远大于存储器容量的增长速度！

程序越来越大，内存容量却没办法快速增长，物理内存渐渐不够用了，怎么办？

用容量更大的硬盘来凑，将一些不常用的数据放在硬盘中，常用的放在内存中。但如果让程序员来考虑这个问题的话，就非常地麻烦了，因此把这个工作交给操作系统。

在计算机系统中，尤其是在多道程序运行的环境下，可能会出现内存不够用的情况，怎么办?

• 如果是程序太大，超过了内存的容量，可以采用手动的覆盖（overlay)技术，只把需要的指令和数据保存在内存当中;
• 如果是程序太多，超过了内存的容量，可以采用自动的交换（ swapping)技术，把暂时不能执行的程序送到外存中;
• 如果想要在有限容量的内存中，以更小的页粒度为单位装入更多更大的程序，可以采用自动的虚拟存储技术。

¶2、覆盖和交换

¶覆盖技术

目标

在较小的可用内存中运行较大的程序，常用于多道程序系统，与分区存储管理配合使用。

方法

依据程序逻辑结构，将程序划分为若干功能相对独立的模块

将不会同时执行的模块共享同一块内存区城

• 必要部分（常用功能）的代码和数据常驻内存
• 可选部分（不常用功能）放在其他程序模块中只在需要用到时装入内存
• 不存在调用关系的模块可相互覆盖，共用同一块内存区域

举个栗子，下面这个程序分为了A-E五个模块。左边的树状图表明了这个程序各个模块之间的调用关系。首先，A需要常驻内存，因为它会调用其他模块。B和C都被A调用，他们之间没有相互调用关系，所以B跟C分在一个区。同理，D、E、F也分在一个区。

我们可以看到，覆盖方法是不止一种的，可以通过程序员的精心安排，设计一个所需内存更小的覆盖方法。粒度是每个模块的大小。

覆盖技术的不足

• 增加编程困难：需程序员划分功能模块，并确定模块间的覆盖关系，增加了编程的复杂度
• 增加执行时间：从外存装入覆盖模块时间换空间

¶交换技术

目标

增加正在运行或需要运行的程序的内存

实现方法

• 可将暂时不能运行的程序放到外存
• 换入换出的基本单位：整个进程的地址空间
• 换出( swap out )：把一个进程的整个地址空间保存到外存
• 换入( swap in )：将外存中某进程的地址空间读入到内存

交换时机：何时需要发生交换?

• 只当内存空间不够或有不够的可能时换出

交换区大小

• 存放所有用户进程的所有内存映像的拷贝

程序换入时的重定位：换出后再换入时放在原处吗?

• 采用动态地址映射的方法

重点说一下程序换入时的重定位。程序在执行过程中，之前换出去的空间可能已经被占用了。此时换入的程序只能放在一个新的地方，如何确保寻址不出问题？

前面已经提到过，页表机制里，逻辑地址跟物理地址存在一个映射关系。因此，只要维护一个动态的页表，就能通过逻辑地址找到换入后的物理地址，这就是动态地址映射的方法。

覆盖与交换比较

覆盖

• 只能发生在没有调用关系的模块间
• 程序员须给出模块间的逻辑覆盖结构
• 发生在运行程序的内部模块间

交换

• 以进程为单位
• 不需要模块间的逻辑覆盖结构
• 发生在内存进程间

¶3、局部性原理

¶虚拟存储技术的目标

只把部分程序放到内存中，从而运行比物理内存大的程序

由操作系统自动完成，无需程序员的干涉

实现进程在内存与外存之间的交换，从而获得更多的空闲内存空间

在内存和外存之间只交换进程的部分内容

¶局部性原理

程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域！

时间局部性

• 一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内

空间局部性

• 当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内

分支局部性

• 一条跳转指令的两次执行，很可能跳到相同的内存位置

局部性原理的意义

• 从理论上来说，虚拟存储技术是能够实现的，而且可取得满意的效果

一个例子：

• 要注意，int型在32位机中占据的空间是4个字节，也就是说，程序提供给这个进程的4k空间，刚刚好能够存放A一行的数据，也就是1024个整数。
• 按照编写方法1，访问顺序为 A[0][0]、A[1][0]、A[2][0]、……、A[1023][0]、A[0][1]、A[1][1]、……，比如当我们从A[0][0]访问下一个数据A[1][0]的时候，因为第一行A[0][0]——A[0][1023]已经在内存中占据了所有分配给这个进程的空间，所以这个数组的其他数据其实还在硬盘中，并不在内存里，所以此时会产生一个缺页中断，操作系统就需要先把第一行保存到硬盘中，再把第二行，也就是A[1][0]所在的行从硬盘中挪到内存。依此类推，解法1发生了1024*1024次缺页中断。
• 按照编写方法2，因为是逐行访问的，所以对每一行进行赋值时，只有当访问这一行的第一个元素时，操作系统才会产生缺页中断，把A这一行的数据搬到内存中。访问这一行接下来的数据时，并不会产生缺页中断（毕竟这一行已经放在内存里了）。依此类推，共产生1024次中断。
• 完成同一个任务（对一个二维数组赋值），上面两个方法的开销是截然不同的。
• 因此，在编写程序的时候，我们希望程序具有良好的局部性。

¶4、虚拟存储概念

思路

• 将不常用的部分内存块暂存到外存

原理

• 装载程序时：只将当前指令执行需要的部分页面或段装入内存
• 指令执行中需要的指令或数据不在内存（称为缺页或缺段)时：处理器通知操作系统将相应的页面或段调入内存
• 操作系统将内存中暂时不用的页面或段保存到外存

实现方式

• 虚拟页式存储（虚拟二字代表要存到外存）
• 虚拟段式存储

有了虚拟内存管理技术，如果地址线有32位，那么即使物理内存空间很小，通过硬盘的补充配合，每个应用程序都能使用4G的地址空间（虚拟）。

虚拟存储的基本特征

不连续性

• 物理内存分配非连续
• 虚拟地址空间使用非连续

大用户空间

• 提供给用户的虚拟内存可大于实际的物理内存

部分交换

• 虚拟存储只对部分虚拟地址空间进行调入和调出

虚存储的支持

硬件：页式或段式存储中的地址转换机制

操作系统：管理内存和外存间页面或段的换入和换出

在页式管理中，页表完成逻辑页到物理页帧的映射。如果在某一次查找中，逻辑地址的页号在页表中找不到相应的物理页帧号（表示物理页帧号是否存在的标志位invalid为1表示存在，为0表示不存在），会返回一个中断。利用这个机制，可以成为虚拟内存管理的有效手段。

¶5、虚拟页式存储

¶虚拟页式存储管理

在页式存储管理的基础上，增加请求调页和页面置换

思路

• 当用户程序要装载到内存运行时，只装入部分页面，就启动程序运行
• 进程在运行中发现有需要的代码或数据不在内存时，则向系统发出缺页异常请求
• 操作系统在处理缺页异常时，将外存中相应的页面调入内存使得进程能继续运行

¶虚拟页式存储中的地址转换

在页式存储管理的基础上加了一个标志位，来标志对应的页知否在物理内存中！

¶虚拟页式存储的页表结构

为了实现虚拟内存管理的请求调页和页面置换功能，需要在页表项中增加一些位来实现一些功能。比较重要的四个如下：

• 驻留位：表示该页是否存放在内存
  • 1表示该页位于内存中，该页表项是有效的，可以使用
  • 0表示该页当前在外存中，访问该页表项将导致缺页异常
• 保护位：对一个页的访问类型的控制。只读，可读可写，可执行等！
• 修改位：表明该页在内存中是否被修改过。如果没被修改过，需要回收这一物理页的时候，就不用再把它写回外存了，直接释放那块空间即可。反之亦然
• 访问位：表明这页是否被访问过（读或写）。这个位用于页面置换算法。如果这个页在当前没被访问过，就可以将其置换出去。

¶虚拟页式存储示例

表示虚拟内存和物理页帧的映射关系。X表示驻留位为0，也就是这页目前保存在外存中，没有相应的物理页帧跟其对应。

其他数据表示与其对应的物理页帧号。

下面我们考虑两个命令：

（1）MOVE REG，0

这个命令的含义是：将逻辑地址0中的数据存读到寄存器中。

0地址在页表中对应的页号是0，偏移量为0。页号0对应的物理页帧号是2，偏移量不变也为0。因此，这个命令，实际上访问的是物理地址8k+0，也就是8192。

（2）MOVE REG，32780

这个命令的含义是：将逻辑地址32780中的数据读到寄存器中。

32780，对应的页号是32780/4k=8，也就是32k到36k的区间，这项的驻留位为0，也就是说，这页的内容其实是存放在外存中的，物理内存中不存在对应的页。此时返回一个缺页中断。

缺页操作系统就会将物理地址空间的某一项去掉，然后将该逻辑地址对应的内容写入该位置，并且修改标志位X

¶6、缺页异常

¶缺页中断处理

前面是缺页中断的一个最基本流程，我们可以发现，驻留位和修改位发挥了重要的作用。

¶外存管理、后备存储

一个程序中的大量数据其实是存放在外存中的，需要的时候才把它们读到内存中。那我们就会想知道，外存（硬盘）是用什么形式来放置内存中的数据和代码的呢。

在何处保存未被映射的页?

• 应能方便地找到在外存中的页面内容
• 交换空间(磁盘或者文件)：采用特殊格式存储未被映射的页面

虚拟页式存储中的外存选择

• 代码段：可执行二进制文件
• 动态加载的共享库程序段：动态调用的库文件
• 其它段:交换空间

¶虚拟存储的性能

有效存储访问时间 (effective memory access time EAT）

EAT = 访存时间 * (1-p) ＋ 缺页异常处理时间 * 缺页率p

上面的EAT=10(1-p)+5000000p(1+q)，10代表访问一次内存的时间，p表示出现缺页的概率。5000000表示访问一次硬盘所用的时间，可以看到，访问一次硬盘所用的时间比访问一次内存多得多。

需要注意的是，为什么要乘以（1+q）呢？q表示"需要换出的页已经被修改过的概率"，也就是说，如果需要换出的页已经被修改，那还需要将它在硬盘中对应的内容进行修改，还需要进行写硬盘操作，因此还要乘以（1+q）。

访问一次硬盘所用的时间比访问一次内存多得多，只有当p足够小的时候，才能使虚拟内存的平均访问时间接近物理内存。恰巧的是，大部分程序设计中都会尽量使之具有局部性，因此虚拟内存管理的性能是可以得到保障的。

¶五、页面置换算法

¶1、置换算法的功能和目标

¶功能

• 当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面

¶设计目标

• 尽可能减少页面的调入调出次数

• 把未来不再访问或短期内不访问的页面调出

¶页面锁定(frame locking)

• 描述必须常驻内存的逻辑页面
• 操作系统的关键部分
• 要求响应速度的代码和数据
• 页表中的锁定标志位(lock bit)来标识是否需要页面锁定

¶2、页面置换算法分类

局部页面置换算法

置换页面的选择范围仅限于当前进程占用的物理页面内！

算法：

• 最优算法（预测未来无法实现）、先进先出算法、最近最久未使用算法（统计过去，复杂度较高）
• 时钟算法、最不常用算法（这两种类似最近最久未使用算法）

全局页面置换算法

置换页面的选择范围是所有可换出的物理页面

算法：

工作集算法、缺页率算法

¶3、最优页面置换算法 OPT

基本思路

置换在未来最长时间不访问的页面

算法实现

缺页时，计算内存中每个逻辑页面的下一次访问时间

选择未来最长时间不访问的页面

算法特征

• 缺页最少，是理想情况
• 实际系统中无法实现
• 无法预知每个页面在下次访问前的等待时间
• 作为置换算法的性能评价依据
• 在模拟器上运行某个程序，并记录每一次的页面访问情况，第二遍运行时使用最优算法

算法示例

访问e物理页帧号没有，选择未来最长时间不访问的页面，即 d 页面，置换为e，访问到d，将发生第二次缺页！

¶4、先进先出算法 FIFO

思路

选择在内存驻留时间最长的页面进行置换

实现

• 维护一个记录所有位于内存中的逻辑页面链表
• 链表元素按驻留内存的时间排序，链首最长，链尾最短
• 出现缺页时，选择链首页面进行置换，新页面加到链尾

特征

• 实现简单
• 性能较差，调出的页面可能是经常访问的
• 进程分配物理页面数增加时，缺页并不一定减少(Belady现象)
• 很少单独使用（一般与其他算法混合使用）

算法示例

物理页没有时，选链表头的物理页帧（即驻留时间最长）的置换掉，极端情况下，可以构造一个例子，下次访问的就是上次置换出去的物理页帧！

¶5、最近最久未使用算法 LRU

思路

• 选择最长时间没有被引用的页面进行置换
• 如某些页面长时间未被访问，则它们在将来还可能会长时间不会访问（过去预测未来）

实现

• 缺页时，计算内存中每个逻辑页面的上一次访问时间
• 选择上一次使用到当前时间最长的页面

特征

最优置换算法的一种近似（仍然足够复复杂，不好实现）

算法示例

遇到缺页，则需要统计各页帧的上一次访问时间，选择距离当前最久远的进行置换！每次遇到缺页都需要统计！

LRU算法的可能实现方法

将统计的过程放在访问每一个页帧时来做！

页面链表

• 系统维护一个按最近一次访问时间排序的页面链表
• 链表首节点是最近刚刚使用过的页面
• 链表尾节点是最久未使用的页面
• 访问内存时，找到相应页面（需要扫描一遍），并把它移到链表之首（开销大）
• 缺页时，置换链表尾节点的页面

活动页面栈

• 访问页面时，将此页号压入栈顶，并将栈内相同的页号抽出（开销大）
• 缺页时，置换栈底的页面

特征：开销巨大

用栈实现LRU算法

查找栈内相同元素需要扫描一遍，若找到相同元素，仍需要将栈内元素反转位置，开销巨大！

¶6、时钟置换算法 Clock

思路

• 仅对页面的访问情况进行大致统计

数据结构

• 在页表项中增加访问位，描述页面在过去一段时间的内访问情况

• 各页面组织成环形链表

• 指针指向最先调入的页面

算法

• 访问页面时，在页表项记录页面访问情况
• 缺页时，从指针处开始顺序查找未被访问的页面进行置换

特征

• 时钟算法是LRU和FIFO的折中

算法实现

• 页面装入内存时，访问位初始化为0
• 访问页面(读/写)时，访问位置1
• 缺页时，从指针当前位置顺序检查环形链表
  • 访问位为0，则置换该页，将访问位 置1
  • 访问位为1，则访问位 置0，并指针移动到下一个页面，直到找到可置换的页面

算法示例

访问到将其置为1，缺页则从当前指针位置循环遍历第一个0的位置进行置换，置换完将其置为1

改进的时钟置换算法

思路

减少修改页的缺页处理开销

算法

• 在页面中增加修改位，并在访问时进行相应修改
• 缺页时，修改页面标志位，以跳过有修改的页面

使用位和修改位只有都为0时，才能进行置换，可以看指针扫描前后的变化！

算法示例

带有w标志的是写，即可读可写，标志位为11，不带w为可读，标志位为10，缺页时循环遍历，按照上面那张图指针扫描前后进行变化，直到遇到下一项是00为止即可置换！

¶7、最不常用算法 LFU

思路

缺页时，置换访问次数最少的页面

实现

• 每个页面设置一个访问计数
• 访问页面时，访问计数加1
• 缺页时，置换计数最小的页面

特征

• 算法开销大
• 开始时频繁使用，但以后不使用的页面很难置换
• 解决方法：计数定期右移

LRU和LFU的区别

• LRU关注多久未访问，时间越短越好
• LFU关注访问次数，次数越多越好

算法示例

¶8、Belady现象和局部置换算法

¶Belady现象

现象

采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象

原因

FIFO算法的置换特征与进程访问内存的动态特征矛盾

被它置换出去的页面并不一定是进程近期不会访问的

思考

哪些置换算法没有Belady现象?

• LRU和OPT算法没有Belady现象
• FIFO算法有Belady现象

¶局部转换算法比较

LRU、FIFO和Clock的比较

LRU算法和FIFO本质上都是先进先出的思路

• LRU依据页面的最近访问时间排序
• LRU需要动态地调整顺序
• FIFO依据页面进入内存的时间排序
• FIFO的页面进入时间是固定不变的

LRU可退化成FIFO

• 如页面进入内存后没有被访问，最近访问时间与进入内存的时间相同
• 例如∶给进程分配3个物理页面，逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3…

LRU算法性能较好,但系统开销较大

FIFO算法系统开销较小，会发生Belady现象

Clock算法是它们的折中

• 页面访问时,不动态调整页面在链表中的顺序,仅做标记
• 缺页时,再把它移动到链表末尾

对于未被访问的页面, Clock和LRU算法的表现一样好

对于被访问过的页面, Clock算法不能记录准确访问顺序,而LRU算法可以

¶9、工作集置换算法

局部置换算法没有考虑进程访存差异！

¶全局置换算法

思路

全局置换算法为进程分配可变数目的物理页面

全局置换算法要解决的问题

• 进程在不同阶段的内存需求是变化的
• 分配给进程的内存也需要在不同阶段有所变化
• 全局置换算法需要确定分配给进程的物理页面数

¶CPU利用率与并发进程数的关系

CPU利用率与并发进程数存在相互促进和制约的关系

• 进程数少时，提高并发进程数，可提高CPU利用率
• 并发进程导致内存访问增加
• 并发进程的内存访问会降低了访存的局部性特征
• 局部性特征的下降会导致缺页率上升和CPU利用率下降

¶工作集

一个进程当前正在使用的逻辑页面集合，可表示为二元函数 W(t, △)

• t是当前的执行时刻
• △称为工作集窗口( working-set window ) ，即一个定长的页面访问时间窗口
• w(t，△)是指在当前时刻t前的△时间窗口中的所有访问页面所组成的集合
• |w(t,A)| 指工作集的大小，即页面数目

工作集示例

如果△时间窗口的长度为10，那么

• w(t，A) = {3，4}
• w(1，A) = {1，2，5，6，7}
• w(t2,，A) = {3，4}

¶工作集变化

• 进程开始执行后，随着访问新页面逐步建立较稳定的工作集
• 当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定
• 局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值

¶常驻集

对工作集进行刻画！

在当前时刻，进程实际驻留在内存当中的页面集合！

工作集与常驻集的关系

• 工作集是进程在运行过程中固有的性质
• 常驻集取决于系统分配给进程的物理页面数目和页面置换算法

缺页率与常驻集的关系

• 常驻集包含工作集时，缺页较少
• 工作集发生剧烈变动（过渡）时，缺页较多
• 进程常驻集大小达到一定数目后，缺页率也不会明显下降

¶工作集置换算法

思路

换出不在工作集中的页面

窗口大小t

当前时刻前t个内存访问的页引用是工作集，t被称为窗口大小

实现方法

• 访存链表：维护窗口内的访存页面链表
• 访存时，换出不在工作集的页面，更新访存链表
• 缺页时，换入页面，更新访存链表

算法示例

由于窗口大小是4，起始状态规定了t=0,-1,-2表示a,d,e初始已经使用了1,2,3个窗口大小，因此当窗口大小到达4时候，就需要踢出工作集！

¶10、缺页率置换算法

¶缺页率

缺页次数 / 内存访问次数 或 缺页平均时间间隔的倒数！

影响缺页率的因素

• 页面置换算法
• 分配给进程的物理页面数目
• 页面大小
• 程序的编写方法

¶缺页率置换算法

通过调节常驻集大小，使每个进程的缺页率保持在一个合理的范围内！

• 若进程缺页率过高，则增加常驻集以分配更多的物理页面
• 若进程缺页率过低，则减少常驻集以减少他的的物理页面

算法实现

访存时，设置引用位标志

缺页时，计算从上次缺页时间tlast到现在tcurrernt的时间间隔

• 如果 tcurrent - tlast > T（常量），则置换所有在〔tlast, tcurrent] 时间内没有被引用的页
• 如果 tcurrent - tlast ≤ T，则增加缺失页到常驻集中

算法示例

窗口大小为2，即每两次相邻的缺页间隔大于2就需要将间隔内没有用到的踢出去！

¶11、抖动和负载控制

¶抖动问题

抖动

• 进程物理页面太少，不能包含工作集
• 造成大量缺页，频繁置换
• 进程运行速度变慢

产生抖动的原因

• 随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升

操作系统需在并发水平和缺页率之间达到一个平衡

• 选择一个适当的进程数目和进程需要的物理页面数

¶负载控制

通过调节并发进程数(MPL)来进行系统负载控制

求和 wsi （指的是工作集）= 内存的大小
平均缺页间隔时间(MTBF) = 缺页异常处理时间(PFST)

¶六、进程及线程

¶1、进程的概念

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

进程的组成

进程包含了正在运行的一个程序的所有状态信息

• 代码
• 数据
• 状态寄存器：CPU状态CRO、指令指针IP
• 通用寄存器：AX、BX、CX…
• 进程占用系统资源：打开文件、已分配内存…

进程的特点

• 动态性：可动态地创建、结束进程
• 并发性：进程可以被独立调度并占用处理机运行
• 独立性：不同进程的工作不相互影响
• 制约性：因访问共享数据/资源或进程间同步而产生制约

进程与程序的联系

• 进程是操作系统处于执行状态程序的抽象

  • 程序=文件(静态的可执行文件)

  • 进程=执行中的程序=程序＋执行状态

• 同一个程序的多次执行过程对应为不同进程

  • 如命令“Is”的多次执行对应多个进程

• 进程执行需要的资源

  • 内存:保存代码和数据CPU:执行指令

进程与程序的区别

• 进程是动态的，程序是静态的

  • 程序是有序代码的集合
  • 进程是程序的执行，进程有核心态/用户态

• 进程是暂时的，程序的永久的

  • 进程是一个状态变化的过程程序可长久保存

• 进程与程序的组成不同

  • 进程的组成包括程序、数据和进程控制块

¶2、进程控制块 PCB

进程控制块：操作系统管理控制进程运行所用的信息集合

• 操作系统用PCB来描述进程的基本情况以及运行变化的过程
• PCB是进程存在的唯一标志
• 每个进程都在操作系统中有一个对应的PCB

进程控制块使用

• 进程创建：生成该进程的PCB
• 进程终止：回收它的PCB进程的组织管理
• 通过对PCB的组织管理来实现

进程控制块内容

• 进程标识信息
• 处理机现场保存
• 进程控制信息

进程控制信息

• 调度和状态信息：调度进程和处理机使用情况
• 进程间通信信息：进程间通信相关的各种标识
• 存储管理信息：指向进程映像存储空间数据结构
• 进程所用资源：进程使用的系统资源，如打开文件等
• 有关数据结构连接信息：与PCB相关的进程队列

进程控制块的组织

链表

• 同一状态的进程其PCB成一链表，多个状态对应多个不同的链表
• 各状态的进程形成不同的链表：就绪链表、阻塞链表

索引表

• 同一状态的进程归入一个索引表（由索引指向PCB ) ，多个状态对应多个不同的索引表
• 各状态的进行形成不同的索引表：就绪索引表、阻塞索引表

¶3、进程状态

¶进程生命周期划分

• 进程创建
• 进程执行
• 进程等待
• 进程抢占
• 进程唤醒
• 进程结束

引起进程创建的情况

• 系统初始化时
• 用户请求创建一个新进程
• 正在运行的进程执行了创建进程的系统调用

进程执行：内核选择一个就绪的进程，让它占用处理机并执行

如何选择：处理机调度算法来做！

引起进程等待的情况

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

引起进程抢占的情况

• 高优先级进程就绪
• 进程执行当前时间用完

引起进程等待的情况

• 被阻塞进程需要的资源可被满足
• 被阻塞进程等待的事件到达

进程只能被别的进程或操作系统唤醒

引起进程结束的情况

• 正常退出(自愿的)
• 错误退出(自愿的)
• 致命错误(强制性的)
• 被其他进程所杀(强制性的)

¶4、三状态进程模型

五种状态

• 运行状态(Running)：进程正在处理机上运行
• 就绪状态(Ready)：进程获得了除处理机之外的所需资源，得到处理机即可运行
• 等待状态(又称阻塞状态Blocked )：进程正在等待某一事件的出现而暂停运行
• 创建状态(New)：一个进程正在被创建，还没被转到就绪状态之前的状态
• 结束状态(Exit)：一个进程正在从系统中消失时的状态，这是因为进程结束或由于其他原因所导致

状态的变迁

• NULL→创建：一个新进程被产生出来执行一个程序
• 创建→就绪：当进程被创建完成并初始化后，—切就绪准备运行时，变为就绪状态
• 就绪→运行：处于就绪状态的进程被进程调度程序选中后，就分配到处理机上来运
• 运行→结束：当进程表示它已经完成或者因出错，当前运行进程会由操作系统作结束处理
• 运行→就绪：处于运行状态的进程在其运行过程中，由于分配给它的处理机时间片用完而让出处理机
• 运行→等待：当进程请求某资源且必须等待时
• 等待→就绪：当进程要等待某事件到来时，它从阻塞状态变到就绪状态

¶5、挂起进程模型

进程挂起：处在挂起状态的进程映像在磁盘上，目的是减少进程占用内存

状态模型改变：

等待挂起状态( Blocked-suspend)：进程在外存并等待某事件的出现

就绪挂起状态( Ready-suspend )：进程在外存，但只要进入内存，即可运行

与挂起相关状态转换

挂起(Suspend) ：把一个进程从内存转到外存

• 等待到等待挂起：没有进程处于就绪状态或就绪进程要求更多内存资源

• 就绪到就绪挂起：当有高优先级等待（系统认为会很快就绪的）进程和低优先级就绪进程

• 运行到就绪挂起：对抢先式分时系统，当有高优先级等待挂起进程因事件出现而进入就绪挂起

在外存时的内存转换：

• 等待挂起到就绪挂起：当有等待挂起进程因相关事件出现

激活( Activate ) ：把一个进程从外存转到内存

• 就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程
• 等待挂起到等待：当一个进程释放足够内存并有高优先级等待挂起进程

状态队列

• 由操作系统来维护一组队列，表示系统中所有进程的当前状态
• 不同队列表示不同状态：就绪队列、各种等待队列
• 根据进程状态不同，进程PCB加入相应队列：进程状态变化时，它所在的PCB会从一个队列换到另一个

¶6、线程的概念

¶线程的引入

多进程的实现：

• 进程之间如何通信，共享数据?
• 系统开销较大：创建进程、进程结束、进程切换

多线程解决思路

在进程内部增加一类实体（这种实体就是线程），满足以下特性

• 实体之间可以并发执行
• 实体之间共享相同的地址空间

¶线程的概念

线程是进程的一部分，描述指令流执行状态。它是进程中的指令执行流的最小单元，是CPU调度的基本单位。

• 进程的资源分配角色：进程由一组相关资源构成，包括地址空间(代码段、数据段)、打开的文件等各种资源
• 线程的处理机调度角色：线程描述在进程资源环境中的指令流执行状态

¶进程和线程的关系

• 代码、数据、打开文件：属于进程
• 寄存器和堆栈：属于每一个线程独有，线程是进程的一部分

线程 = 进程 - 共享资源（代码、数据、打开文件）

执行流的信息就成了线程控制块！

¶线程的优缺点

线程的优点：

• 一个进程中可以同时存在多个线程
• 各个线程之间可以并发地执行
• 各个线程之间可以共享地址空间和文件等资源

线程的缺点：

• 一个线程崩溃，会导致其所属进程的所有线程崩溃

¶线程和进程的比较

• 进程是资源分配单位，线程是CPU调度单位
• 进程拥有一个完整的资源平台，而线程只独享指令流执行的必要资源，如寄存器和栈
• 线程具有就绪、等待和运行三种基本状态和状态间的转换关系（与进程完全一致）
• 线程能减少并发执行的时间和空间开销
  • 线程的创建时间比进程短
  • 线程的终止时间比进程短
  • 同一进程内的线程切换时间比进程短
  • 由于同一进程的各线程间共享内存和文件资源，可不涌讨内核进行直接通信

¶7、用户线程

¶线程的三种实现方方式

• 用户线程：在用户空间实现
• 内核线程：在内核中实现
• 轻量级进程：在内核中实现，支持用户线程（前两种的结合）

¶用户线程

由一组用户级的线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度等！

内核只有PCB

¶用户线程的特征

不依赖于操作系统的内核内核

• 不了解用户线程的存在
• 可用于不支持线程的多进程操作系统

在用户空间实现的线程机制

• 每个进程有私有的线程控制块(TCB 线程控制块)列表
• TCB由线程库函数维护

同一进程内的用户线程切换速度快：无需用户态/核心态切换

允许每个进程拥有自已的线程调度算法

¶用户线程的不足

• 线程发起系统调用而阻塞时，则整个进程进入等待
• 不支持基于线程的处理机抢占：除非当前运行线程主动放弃，它所在进程的其他线程无法抢占CPU
• **只能按进程分配CPU时间：**多个线程进程中，每个线程的时间片较少

¶8、内核线程

¶内核线程

内核线程：由内核通过系统调用实现的线程机制，由内核完成线程的创建、终止和管理

内核有PCB和TCB!

¶内核线程的特征

• 由内核维护PCB和TCB
• 线程执行系统调用而被阻塞不影响其他线程
• 线程的创建、终止和切换相对较大：通过系统调用/内核函数，在内核实现
• 以线程为单位进行CPU时间分配：多线程的进程可获得更多CPU时间

¶轻权进程

内核支持的用户线程。一个进程可有一个或多个轻量级进程，每个轻权进程由一个单独的内核线程来支持。( Solaris/Linux )

前两集进程的实现是结合了用户线程和内核线程的优点，但是实现复杂，效果不理想！

¶用户线程和内核线程的对应关系

三种关系：最后的结论性做法是一对一的实现！

¶七、进程控制

¶1、进程切换

进程切换(上下文切换)

• 暂停当前运行进程，从运行状态变成其他状态
• 调度另一个进程从就绪状态变成运行状态

进程切换的要求

• 切换前，保存进程上下文
• 切换后，恢复进程上下文
• 快速切换（由汇编实现）

进程生命周期的信息

• 寄存器(PC,SP,…)
• CPU状态
• 内存地址空间

上下文切换图示

• 内核为每个进程维护了对应的进程控制块(PCB)
• 内核将相同状态的进程的PCB放置在同一队列

¶2、进程创建

创建新进程

Windows进程创建API : CreateProcess(filename)

• 创建时关闭所有在子进程里的文件描述符：CreateProcess(filename,CLOSE_FD)
• 创建时改变子进程的环境：CreateProcess(filename,CLOSE_FD,new_envp)
• 等等

Unix进程创建系统调用: fork/exec

• fork()把一个进程复制成二个进程：parent (old PID)， child (new PID)
• exec()用新程序来重写当前进程：PID没有改变

fork()创建一个继承的子进程

• 复制父进程的所有变量和内存
• 复制父进程的所有CPU寄存器(有一个寄存器例外)

fork()的返回值

• 子进程的fork()返回0
• 父进程的fork()返回子进程标识符
• fork()返回值可方便后续使用，子进程可使用getpid()获取PID

fork()的地址空间复制

• fork()执行过程对于子进程而言，是在调用时间对父进程地址空间的一次复制
• 对于父进程fork()返回child PID,对于子进程返回值为0

程序的加载和执行

系统调用exec( )加载新程序取代当前运行进程

fork()的开销

fork()的实现开销

• 对子进程分配内存
• 复制父进程的内存和CPU寄存器到子进程里
• 开销昂贵!!

在99%的情况里，我们在调用fork()之后调用exec()

• 在fork()操作中内存复制是没有作用的
• 子进程将可能关闭打开的文件和连接
• 为什么不能结合它们在一个调用中?

vfork()

• 创建进程时，不再创建一个同样的内存映像
• 一些时候称为轻量级fork()
• 子进程应该几乎立即调用exec()
• 现在使用Copy on Write (COW)技术

¶3、进程加载

程序加载和执行系统调用exec()

• 允许进程“加载”一个完全不同的程序，并从main开始执行(即_start)
• 允许进程加载时指定启动参数(argc, argv)exec
• 调用成功时：它是相同的进程…但是运行了不同的程序
• 代码段、堆栈和堆(heap)等完全重写

¶4、进程等待和退出

父进程等待子进程

wait()系统调用用于父进程等待子进程的结束

• 子进程结束时通过exit()向父进程返回一个值
• 父进程通过wait()接受并处理返回值

wait()系统调用的功能

• 有子进程存活时，父进程进入等待状态，等待子进程的返回结果

• 当某子进程调用exit()时,唤醒父进程，将exit()返回值作为父进程中wait的返回值

• 有僵尸子进程等待时，wait()立即返回其中一个值

• 无子进程存活时，wait()立刻返回

进程的有序终止exit()

进程结束执行时调用exit()，完成进程资源回收

exit()系统调用的功能

• 将调用参数作为进程的“结果"b
• 关闭所有打开的文件等占用资源b
• 释放内存
• 释放大部分进程相关的内核数据结构

检查是否父进程是存活着的

• 如存活，保留结果的值直到父进程需要它，进入僵尸( zombie/defunct)状态
• 如果没有，它释放所有的数据结构
• 清理所有等待的僵尸进程

进程终止是最终的垃圾收集(资源回收)

其他进程控制系统调用

优先级控制

• nice()指定进程的初始优先级
• Unix系统中进程优先级会随执行时间而衰减

进程调试支持

• ptrace()允许一个进程控制另一个进程的执行
• 设置断点和查看寄存器等

定时

• sleep()可以让进程在定时器的等待队列中等待指定

进程控制 VS 进程状态

¶八、处理机调度

¶1、处理机调度概念

¶CPU资源的时分复用

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

• 保存当前进程在PCB中的执行上下文(CPU状态)
• 恢复下一个进程的执行上下文

处理机调度

• 从就绪队列中挑选下一个占用CPU运行的进程
• 从多个可用CPU中挑选就绪进程可使用的CPU资源

调度程序：挑选就绪进程的内核函数

• 调度策略：依据什么原则挑选进程/线程?
• 调度时机：什么时候进行调度?

¶调度时机

内核运行调度程序的条件

• 进程从运行状态切换到等待状态

• 进程被终结了

非抢占系统

• 当前进程主动放弃CPU时可

抢占系统

• 中断请求被服务例程响应完成时
• 当前进程被抢占
  • 进程时间片用完
  • 进程从等待切换到就绪

¶2、调度准则

调度策略

确定如何从就绪队列中选择下一个执行进程

调度策略要解决的问题

• 挑选就绪队列中的哪一个进程?
• 通过什么样的准则来选择?

调度算法

在调度程序中实现的调度策略

比较调度算法的准则

哪一个策略/算法较好?

处理机资源的使用模式

• 进程在CPU计算和IO操作间交替
• 每次调度决定在下一个CPU计算时将哪个工作交给CPU
• 在时间片机制下，进程可能在结束当前CPU计算前被迫放弃CPU

比较调度算法的准则

• CPU使用率：CPU处于忙状态的时间百分比
• 吞吐量：单位时间内完成的进程数量
• 周转时间：进程从初始化到结束(包括等待)的总时间
• 等待时间：进程在就绪队列中的总时间
• 响应时间：从提交请求到产生响应所花费的总时间

吞吐量与延迟

调度算法的要求：希望“更快”的服务

什么是更快?

• 传输文件时的高带宽，调度算法的高吞吐量
• 玩游戏时的低延迟，调度算法的低响应延迟
• 这两个因素是独立的

与水管的类比

• 低延迟：喝水的时候想要一打开水龙头水就流出来
• 高带宽：给游泳池充水时希望从水龙头里同时流出大量的水，并且不介意是否存在延迟

处理机调度策略的响应时间目标

• 减少响应时间：及时处理用户的输入请求，尽快将输出反馈给用户
• 减少平均响应时间的波动：在交互系统中，可预测性比高差异低平均更重要
• 低延迟调度改善了用户的交互体验：如果移动鼠标时，屏幕中的光标没动，用户可能会重启电脑
• 响应时间是操作系统的计算延迟

处理机调度策略的吞吐量目标

• 增加吞吐量：减少开销（操作系统开销，上下文切换) 系统资源的高效利用( CPU，I/O设备)
• 减少等待时间：减少每个进程的等待时间
• 操作系统需要保证吞吐量不受用户交互的影响：操作系统必须不时进行调度，即使存在许多交互任务
• 吞吐量是操作系统的计算带宽

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

公平的定义

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

¶3、先来先服务 FCFS

• 依据进程进入就绪状态的先后顺序排列
• 进程进入等待或结束状态时，就绪队列中的下一个进程占用CPU

周转时间实例

特征

优点：简单

缺点

• 平均等待时间波动较大：短进程可能排在长进程后面
• I/O资源和CPU资源的利用率较低：CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待

¶4、短进程优先 SPN

• 选择就绪队列中执行时间最短进程占用CPU进入运行状态
• 就绪队列按预期的执行时间来排序

短剩余时间优先算法(SRT)

• SPN算法的可抢占改进 （来了一个新的进程，他比SPN算法当前执行的进程的剩余时间还要短，则允许抢占）

短进程优先算法SPN具有最优平均周转时间

特征

• 可能导致饥饿：连续的短进程流会使长进程无法获得CPU资源
• 需要预知未来：如何预估下一个CPU计算的持续时间?
  • 简单的解决办法∶询问用尸
  • 用户欺骗就杀死相应进程
  • 用户不知道怎么办? 用过去预测未来

短进程优先算法的执行时间预估

用历史的执行时间来预估未来的执行时间

¶5、最高响应比优先 HRRN

选择就绪队列中响应比R值最高的进程

R= ( w + s) / s

• w：等待时间(waiting time)
• s：执行时间(service time)
• 在短进程优先算法的基础上改进
• 不可抢占
• 关注进程的等待时间
• 防止无限期推迟

¶6、时间片轮转 RR

时间片：分配处理机资源的基本时间单元

算法思路

• 时间片结束时，按FCFS算法切换到下一个就绪进程
• 每隔(n-1)个时间片进程执行一个时间片q

算法示例

时间片为20！

时间片长度？

RR算法开销

• 额外的上下文切换

时间片太大

• 等待时间过长
• 极限情况退化成FCFS

时间片太小

• 反应迅速，但产生大量上下文切换
• 大量上下文切换开销影响到系统吞吐量

时间片长度选择目标

• 选择一个合适的时间片长度
• 经验规则：维持上下文切换开销处于1%以内

比较 FCFS 和 RR 算法？

¶7、多级反馈队列 MLFQ

¶多级队列调度算法MQ

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

如：前台(交互)、后台(批处理)

每个队列拥有自己的调度策略

如：前台-RR、后台-FCFS

队列间的调度

• 固定优先级：先处理前台，然后处理后台
• 可能导致饥饿
• 时间片轮转
• 每个队列都得到一个确定的能够调度其进程的CPU总时间
• 如：80%CPU时间用于前台，20%CPU时间用于后台

多级队列没有交互，多级队列反馈就是他的改进！

¶多级队列反馈算法MLFQ

进程可在不同队列间移动的多级队列算法

• 时间片大小随优先级级别增加而增加
• 如进程在当前的时间片没有完成，则降到下一个优先级

MLFQ算法的特征

• CPU密集型进程的优先级下降很快
• I/O密集型进程停留在高优先级

¶8、公平共享调度算法 FSS

FSS控制用户对系统资源的访问

• 一些用户组比其他用户组更重要
• 保证不重要的组无法垄断资源
• 未使用的资源按比例分配
• 没有达到资源使用率目标的组获得更高的优先级

¶六种传统调度算法总结

• 先来先服务算法：不公平，平均等待时间较差
• 短进程优先算法：不公平，平均周转时间最小。需要精确预测计算时间可能导致饥饿
• 最高响应比优先算法：基于SPN调度。不可抢占
• 时间片轮转算法：公平，但是平均等待时间较差
• 多级反馈队列：多种算法的集成
• 公平共享调度：公平是第一要素

¶9、实时调度和多处理器调度

¶实时调度

实时操作系统的定义

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

实时操作系统的性能指标

• 时间约束的及时性( deadlines )
• 速度和平均性能相对不重要

实时操作系统的特性

时间约束的可预测性

实时任务

任务（工作单元)：一次计算，一次文件读取，一次信息传递等等

任务属性：完成任务所需要的资源，定时参数

周期实时任务

周期实时任务：一系列相似的任务

• 任务有规律地重复
• 周期 p = 任务请求时间间隔(0<p)
• 执行时间 e = 最大执行时间(0<e < p)
• 使用率 U = e / p

硬时限(Hard deadline )

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

软时限(Soft deadline)

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

可调度性

可调度表示一个实时操作系统能够满足任务时限要求

需要确定实时任务的执行顺序

• 静态优先级调度
• 动态优先级调度

速率单调调度算法(RM,Rate Monotonic)

• 通过周期安排优先级
• 周期越短优先级越高
• 执行周期最短的任务

最早截止时间优先算法(EDF,Earliest Deadline Firs)

• 截止时间越早优先级越高
• 执行截止时间最早的任务

¶多处理器调度

多处理器调度的特征

• 多个处理机组成一个多处理机系统
• 处理机间可负载共享

对称多处理器(SMP, Symmetric multiprocessing)调度

• 截止时间越早优先级越高

• 每个处理器运行自己的调度程序

• 调度程序对共享资源的访问需要进行同步

对称多处理器的进程分配

静态进程分配

• 进程从开始到结束都被分配到一个固定的处理机上执行
• 每个处理机有自己的就绪队列
• 调度开销小
• 各处理机可能忙闲不均

动态进程分配

• 进程在执行中可分配到任意空闲处理机执行
• 所有处理机共享一个公共的就绪队列
• 调度开销大
• 各处理机的负载是均衡的

¶10、优先级反置

操作系统中出现高优先级进程长时间等待低优先级进程所占用资源的现象

基于优先级的可抢占调度算法存在优先级反置

优先级继承

占用资源的低优先级进程继承申请资源的高优先级进程的优先级

只在占有资源的低优先级进程被阻塞时,才提高占有资源进程的优先级

优先级天花板协议

占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同

• 不管是否发生等待,都提升占用资源进程的优先级
• 优先级高于系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会被阻塞

¶九、同步互斥

¶1、背景

¶并发进程的正确性

独立进程

• 不和其他进程共享资源或状态
• 确定性→输入状态决定结果
• 可重现→能够重现起始条件
• 调度顺序不重要

并发进程

• 在多个进程间有资源共享不确定性
• 不可重现

并发进程的正确性

• 执行过程是不确定性和不可重现的
• 程序错误可能是间歇性发生的

¶进程并发执行的好处

进程需要与计算机中的其他进程和设备进行协作

• 好处1∶共享资源

  • 多个用户使用同一台计算机
  • 银行账号存款佘额在多台ATM机操作
  • 机器人上的嵌入式系统协调手臂和手的动作

• 好处2∶加速

  • I/O操作和CPU计算可以重叠（并行)
  • 程序可划分成多个模块放在多个处理器上并行执行

• 好处3∶模块化

  • 将大程序分解成小程序
  • 以编译为例，gcc会调用cpp , cc1 , cc2 , as , ld
  • 使系统易于复用和扩展

¶原子操作

原子操作是指一次不存在任何中断或失败的操作

• 要么操作成功完成
• 或者操作没有执行
• 不会出现部分执行的状态

操作系统需要利用同步机制在并发执行的同时，保证一些操作是原子操作

¶2、临界区及临界区实现

¶临界区

临界区(critical section)：进程中访问临界资源的一段需要互斥执行的代码

进入区(entry section)

• 检查可否进入临界区的一段代码
• 如可进入，设置相应"正在访问临界区"标志

退出区(exit section)：清除“正在访问临界区”标志

剩余区(remainder section)：代码中的其余部分

临界区访问规则

• 空闲则入：没有进程在临界区时，任何进程可进入
• 忙则等待：有进程在临界区时，其他进程均不能进入临界区
• 有限等待：等待进入临界区的进程不能无限期等待
• 让权等待（可选）：不能进入临界区的进程，应释放CPU(如转换到阻塞状态)

临界区实现方法

• 禁用中断
• 软件方法
• 更高级的抽象方法

不同的临界区实现机制的比较

• 性能∶并发级别

¶基于禁用硬件中断

没有中断，没有上下文切换，因此没有并发

• 硬件将中断处理延迟到中断被启用之后
• 现代计算机体系结构都提供指令来实现禁用中断

进入临界区：禁止所有中断，并保存标志

离开临界区：使能所有中断，并恢复标志

缺点

• 禁用中断后，进程无法被停止
• 整个系统都会为此停下来
• 可能导致其他进程处于饥饿状态
• 临界区可能很长：无法确定响应中断所需的时间(可能存在硬件影响)
• 要小心使用

¶基于软件同步方法

线程可通过共享一些共享变量来同步他们的行为！

Peterson算法

满足线程Ti和Tj之间互斥的经典的基于软件的解决方法（1981年）

适用于两个线程！

Dekkers算法

N线程的软件方法(Eisenberg和McGuire)

基于软件的解决方法的分析

• 复杂：需要两个进程间的共享数据项
• 需要忙等待：浪费CPU时间

¶基于高级抽象同步方法

硬件提供了一些同步原语

• 中断禁用，原子操作指令等

操作系统提供更高级的编程抽象来简化进程同步

• 例如：锁、信号量
• 用硬件原语来构建

锁Lock

锁是一个抽象的数据结构

一个二进制变量(锁定/解锁)

• Lock::Acquire()：锁被释放前一直等待，然后得到锁
• Lock::Release()：释放锁，唤醒任何等待的进程

使用锁来控制临界区访问

原子操作指令

现代CPU体系结构都提供一些特殊的原子操作指令

• 测试和置位(Test-and-Set )指令
  • 从内存单元中读取值
  • 测试该值是否为1(然后返回真或假)
  • 内存单元值设置为1
• 交换指令( exchange )
  • 交换内存中的两个值

使用TS指令实现自旋锁 SpinLock

无忙等待锁

原子操作指令锁特征

优点

• 适用于单处理器或者共享主存的多处理器中任意数量的进程同步
• 简单并且容易证明
• 支持多临界区

缺点

• 忙等待消耗处理器时间
• 可能导致饥饿：进程离开临界区时有多个等待进程的情况
• 死锁
  • 拥有临界区的低优先级进程
  • 请求访问临界区的高优先级进程获得处理器并等待临界区

¶同步方法总结

锁是一种高级的同步抽象方法

• 互斥可以使用锁来实现
• 需要硬件支持

常用的三种同步实现方法

• 禁用中断(仅限于单处理器)
• 软件方法（复杂)
• 原子操作指令（单处理器或多处理器均可)

¶十、信号量与管程

¶1、信号量

¶回顾

并发问题：多线程并发导致资源竞争

同步概念

• 协调多线程对共享数据的访问
• 任何时刻只能有一个线程执行临界区代码

确保同步正确的方法

• 底层硬件支持
• 高层次的编程抽象

¶基本同步方法

¶信号量

信号量是操作系统提供的一种协调共享资源访问的方法

• 软件同步是平等线程间的一种同步协商机制
• OS是管理者，地位高于进程
• 用信号量表示系统资源的数量

由Dijkstra在20世纪60年代提出

早期的操作系统的主要同步机制：现在很少用(但还是非常重要在计算机科学研究)

信号是一种抽象数据类型

由一个整型(sem)变量和两个原子操作组成

P() (Prolaag (荷兰语尝试减少) )

• sem减1
• 如sem<0,进入等待,否则继续

V() (Verhoog (荷兰语增加))

• sem加1
• 如sem≤0,唤醒一个等待进程

¶信号量特性

信号量是被保护的整数变量

• 初始化完成后，只能通过P()和V()操作修改
• 由操作系统保证，PV操作是原子操作

P()可能阻塞，V()不会阻塞

通常假定信号量是“公平的"

• 线程不会被无限期阻塞在P()操作
• 假定信号量等待按先进先出排队

自旋锁不能实现先进先出策略！

¶信号量实现

¶2、信号量使用

¶信号量分类

可分为两种信号量

• 二进制信号量：资源数目为0或1
• 资源信号量：资源数目为任何非负值
• 两者等价：基于一个可以实现另一个

信号量的使用

• 互斥访问：临界区的互斥访问控制
• 条件同步：线程间的事件等待

¶信号量实现临界区的互斥访问

每类资源设置一个信号量，其初值为1

必须成对使用P()操作和V()操作

• P()操作保证互斥访问临界资源
• V()操作在使用后释放临界资源
• PV操作不能次序错误、重复或遗漏

¶信号量实现条件同步

条件同步设置一个信号量，其初值为0

若线程A先进入，线程A要等待线程B执行完V操作才能继续执行

若线程B先进入，线程B执行完V操作，信号量为1，线程A可以继续执行！

¶生产者消费者问题

有界缓冲区的生产者-消费者问题描述

• 一个或多个生产者在生成数据后放在一个缓冲区里
• 单个消费者从缓冲区取出数据处理
• 任何时刻只能有一个生产者或消费者可访问缓冲区

¶信号量解决生产者消费者问题

问题分析

• 任何时刻只能有一个线程操作缓冲区（互斥访问)
• 缓冲区空时，消费者必须等待生产者（条件同步)
• 缓冲区满时，生产者必须等待消费者（条件同步)

用信号量描述每个约束

• 二进制信号量mutex（互斥访问)
• 资源信号量fullBuffers（条件同步)
• 资源信号量emptyBuffers（条件同步)

信号量实现：

注意PV操作的顺序不可以调整，否则发生死锁！

¶信号量机制的问题

读/开发代码比较困难

• 程序员需要能运用信号量机制

容易出错

• 使用的信号量已经被另一个线程占用
• 忘记释放信号量

不能够处理死锁问题

¶3、管程

¶基本同步方法

解决信号量PV操作的分散性，可将其集中到一起！

¶管程

管程是一种用于多线程互斥访问共享资源的程序结构

• 采用面向对象方法，简化了线程间的同步控制
• 任一时刻最多只有一个线程执行管程代码
• 正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复

管程的使用

• 在对象/模块中，收集相关共享数据
• 定义访问共享数据的方法

¶管程的组成

一个锁：控制管程代码的互斥访问

0或者多个条件变量：管理共享数据的并发访问

¶条件变量

条件变量是管程内的等待机制

• 进入管程的线程因资源被占用而进入等待状态
• 每个条件变量表示一种等待原因,对应一个等待队列

Wait()操作

• 将自己阻塞在等待队列中
• 唤醒一个等待者或释放管程的互斥访问

Signal()操作

• 将等待队列中的一个线程唤醒
• 如果等待队列为空,则等同空操作

¶条件变量实现

¶管程解决生产者消费者问题

与信号量最大的不同就行管程进入临界区，也可以临时放弃互斥访问，即CPU执行权！

¶管程条件变量的释放处理方式

管程里的条件变量是内部的线程优先执行还是正占用的管程处于执行状态的！

Hansen 管程和 Hoare 管程

Hansen ：主要用于真实OS和Java中

Hoare ：主要见于教材中

Hansen管程

• 条件变量释放仅是一个提示
• 需要重新检查条件

特点：高效

Hoare管程

• 条件变量释放同时表示放弃管程访问
• 释放后条件变量的状态可用

特点：低效

¶4、哲学家就餐问题

¶问题描述

5个哲学家围绕一张圆桌而坐

• 桌子上放着5支叉子
• 每两个哲学家之间放一支

哲学家的动作包括思考和进餐

• 进餐时需同时拿到左右两边的叉子
• 思考时将两支叉子放回原处

如何保证哲学家们的动作有序进行?

如∶不出现有人永远拿不到叉子

¶方案一

不正确，可能导致死锁！

例如：每个人都去拿左手边的叉子，则谁都拿不到右边的叉子，造成死锁！

¶方案二

互斥访问正确，但每次只允许一人进餐！效率低下！

¶方案三

没有死锁，可多人同时就餐！

¶5、读者写者问题

¶问题描述

共享数据的两类使用者

• 读者：只读取数据，不修改
• 写者：读取和修改数据

读者-写者问题描述∶对共享数据的读写

• “读–读”允许：同一时刻，允许有多个读者同时读
• “读-写”互斥：没有写者时读者才能读没有读者时写者才能写
• “写-写”互斥：没有其他写者时写者才能写

¶信号量解决读者写者问题

用信号量描述每个约束

• 信号量WriteMutex：控制读写操作的互斥，初始化为1
• 读者计数Rcount：正在进行读操作的读者数目，初始化为0
• 信号量CountMutex：控制对读者计数的互斥修改，初始化为1

在这种情况下，读者是优先的，只要有读者到来就会进入读者进程执行，写者只能等待！

¶优先策略

• 读者优先策略
  • 只要有读者正在读状态，后来的读者都能直接进入
  • 如读者持续不断进入，则写者就处于饥饿
• 写者优先策略
  • 只要有写者就绪，写者应尽快执行写操作
  • 如写者持续不断就绪，则读者就处于饥饿

¶管程解决读者写者问题

解决方案-读者

解决方案-写者

¶十一、死锁与进程通信

¶1、死锁概念

由于竞争资源或者通信关系，两个或更多线程在执行中出现，永远相互等待，只能由其他进程引发的事件！

¶资源分类

可重用资源(Reusable Resource )

• 资源不能被删除且在任何时刻只能有一个进程使用
• 进程释放资源后，其他进程可重用
• 可重用资源示例
  • 硬件：处理器、I/〇通道、主和副存储器、设备等
  • 软件：文件、数据库和信号量等数据结构
• 可能出现死锁：每个进程占用一部分资源并请求其它资源

消耗资源(Consumable resource)

• 资源创建和销毁
• 消耗资源示例：在I/O缓冲区的中断、信号、消息
• 可能出现死锁：进程间相互等待接收对方的消息

¶资源分配图

描述资源和进程间的分配和占用关系的有向图

两类顶点

• 系统中的所有进程：P= {P1, P2，…，Pn}
• 系统中的所有资源：R= {R1，R2，…Rm}

两类有向边

• 资源请求边：进程Pi请求资源Rj，Pi→Rj
• 资源分配边：资源Rj已分配给进程Pi，Rj→Pi

该图不会发生死锁！

不满足死锁必要条件，循环等待，不会发生死锁！

该图会发生死锁！

有一个循环等待！

该图有循环，但不会发生死锁！

死锁必要条件 R1R2互斥不满足！不会发生死锁！

¶出现死锁必要条件

• 互斥：任何时刻只能有一个进程使用一个资源实例
• 持有并等待：进程保持至少一个资源，并正在等待获取其他进程持有的资源
• 非抢占：资源只能在进程使用后自愿释放
• 循环等待

¶2、死锁的处理方法

¶死锁处理

• 死锁预防(Deadlock Prevention)：确保系统永远不会进入死锁状态
• 死锁避免(Deadlock Avoidance)：在使用前进行判断，只允许不会出现死锁的进程请求资源
• 死锁检测和恢复(Deadlock Detection & Recovery)：在检测到运行系统进入死锁状态后，进行恢复
• 由应用进程处理死锁：通常操作系统忽略死锁，大多数操作系统（包括UNIX )的做法

¶死锁预防-限制申请方式

预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。

破坏任意一个必要条件即可！

互斥：把互斥的共享资源封装成可同时访问

持有并等待

• 进程请求资源时，要求它不持有任何其他资源
• 仅允许进程在开始执行时，一次请求所有需要的资源
• 资源利用率低

非抢占

• 如进程请求不能立即分配的资源，则释放已占有资源
• 只在能够同时获得所有需要资源时，才执行分配操作

循环等待

• 对资源排序，要求进程按顺序请求资源

¶死锁避免

利用额外的先验信息，在分配资源时判断是否会出现死锁，只在不会死锁时分配资源

• 要求进程声明需要资源的最大数目
• 限定提供与分配的资源数量，确保满足进程的最大需求
• 动态检查资源分配状态，确保不会出现环形等待

¶系统资源分配的安全状态

当进程请求资源时，系统判断分配后是否处于安全状态

系统处于安全状态

• 针对所有已占用进程，存在安全序列序列

序列<P1 , P2 ,…，PN>是安全的

• Pi要求的资源≤当前可用资源＋所有Pj持有资源其中j<i
• 如Pi的资源请求不能立即分配，则Pi等待所有Pj( j<i)完成
• Pi完成后，Pi +1可得到所需资源，执行并释放所分配的资源
• 最终整个序列的所有Pi都能获得所需资源

¶安全状态和死锁关系

• 系统处于安全状态，一定没有死锁
• 系统处于不安全状态，可能出现死锁
• 避免死锁就是确保系统不会进入不安全状态

¶3、银行家算法

¶银行家算法介绍

银行家算法是一个避免死锁产生的算法。

以银行借贷分配策略为基础，判断并保证系统处于安全状态！

• 客户在第一次申请贷款时，声明所需最大资金量，在满足所有贷款要求并完成项目时，及时归还
• 在客户贷款数量不超过银行拥有的最大值时，银行家尽量满足客户需要

类比

• 银行家→操作系统
• 资金→资源
• 客户→申请资源的线程

¶数据结构

n=线程数量, m=资源类型数量

Max(总需求量) : nxm矩阵

• 线程T最多请求类型R;的资源Max[i,j]个实例

**Available(剩余空闲量)**∶长度为m的向量

• 当前有Available[i]个类型Rj的资源实例可用

Allocation(已分配量) : nxm矩阵

• 线程T当前分配了Allocation[i, j]个R;的实例

Need(未来需要量) : nxm矩阵

• 线程T未来需要Need[i,j]个R;资源实例

Need[i,j] = Max[i,j]-Allocation[i,j]

¶安全状态判断

模拟整个过程，去循环查找未来需要的比剩余的少的，及说明该线程可以正常执行完毕，将该线程可用的加上系统总剩余的得到当前可用，继续循环！

• 直到所有线程都可以政策执行完毕，则说明系统处于安全状态！
• 否则，处于不安全状态！

¶银行家算法

初始化:

• Requesti线程Ti的资源请求向量
• Requesti[j]线程Ti请求资源Rj的实例

循环:

1. 如果Requesti ≤ Need [i]，转到步骤2。否则，拒绝资源申请，因为线程已经超过了其最大要求
2. 如果Requesti ≤ Available，转到步骤3。否则，Ti必须等待，因为资源不可用
3. 通过安全状态判断来确定是否分配资源给Ti，生成一个需要判断状态是否安全的资源分配环境
   1. Available = Available -Requesti
   2. Allocation[i]= Allocation[i]+ Requesti
   3. Need[i]= Need[i]-Requesti
4. 调用安全状态判断
   1. 如果返回结果是安全，将资源分配给Ti
   2. 如果返回结果是不安全，系统会拒绝Ti的资源请求

¶4、死锁检测

¶死锁检测

• 允许系统进入死锁状态
• 维护系统的资源分配图
• 定期调用死锁检测算法来搜索图中是否存在死锁
• 出现死锁时，用死锁恢复机制进行恢复

¶死锁检测数据结构

• Available：长度为m的向量，每种类型可用资源的数量
• Allocation：—个nxm矩阵
  • 当前分配给各个进程每种类型资源的数量
  • 进程Pi拥有资源Ri的Allocation[i,j]个实例

¶死锁检测算法

¶死锁检测示例

当前可用资源，初始状态都为0！

¶死锁检测算法的使用

死锁检测的时间和周期选择依据

• 死锁多久可能会发生
• 多少进程需要被回滚

资源图可能有多个循环

• 难于分辨“造成”死锁的关键进程

¶死锁恢复-进程终止

终止所有的死锁进程

一次只终止一个进程直到死锁消除

终止进程的顺序应该是

• 进程的优先级
• 进程已运行时间以及还需运行时间
• 进程已占用资源
• 进程完成需要的资源
• 终止进程数目
• 进程是交互还是批处理

¶死锁恢复-资源抢占

• 选择被抢占进程：最小成本目标
• 进程回退：返回到一些安全状态,重启进程到安全状态
• 可能出现饥饿：同一进程可能一直被选作被抢占者

¶5、进程通信的概念

¶进程通信

进程通信是进程进行通信和同步的机制

进程通信IPC提供2个基本操作

• 发送操作: send(message)
• 接收操作: receive(message)

进程通信流程

• 在通信进程间建立通信链路
• 通过send/receive交换消息

进程链路特征

• 物理(如，共享内存，硬件总线)
• 罗辑(如，逻辑属性）

¶通信方式

¶直接通信

进程必须正确的命名对方

• send (P,message)-发送信息到进程P
• receive(Q,message)-从进程Q接受消息

通信链路的属性

• 自动建立链路
• 一条链路恰好对应—对通信进程
• 每对进程之间只有一个链接存在
• 链接可以是单向的，但通常为双向的

¶间接通信

通过操作系统维护的消息队列实现进程间的消息接收和发送

• 每个消息队列都有一个唯一的标识
• 只有共享了相同消息队列的进程，才能够

通信通信链路的属性

• 只有共享了相同消息队列的进程，才建立连接
• 连接可以是单向或双向
• 消息队列可以与多个进程相关联
• 每对进程可以共享多个消息队列

通信流程

• 创建一个新的消息队列
• 通过消息队列发送和接收消息
• 销毁消息队列

基本通信操作

• send(A, message)-发送消息到队列A
• receive(A, message)-从队列A接受消息

¶阻塞与非阻塞通信

进程通信可划分为阻塞（同步）或非阻塞（异步)

阻塞通信

• 阻塞发送：发送者在发送消息后进入等待，直到接收者成功收到
• 阻塞接收：接收者在请求接收消息后进入等待，直到成功收到一个消息

非阻塞通信

• 非阻塞发送：发送者在消息发送后，可立即进行其他操作
• 非阻塞接收：没有消息发送时，接收者在请求接收消息后，接收不到任何消息

¶通信链路缓冲

进程发送的消息在链路上可能有3种缓冲方式

• 0容量：发送方必须等待接收方
• 有限容量：通信链路缓冲队列满时，发送方必须等待
• 无限容量：发送方不需要等待

¶6、信号和管道

¶信号

信号

• 进程间的软件中断通知和处理机制
• 如:SIGKILL,SIGSTOP, SIGCONT等

信号的接收处理

• 捕获(catch)：执行进程指定的信号处理函数被调用
• 忽略(Ignore)：执行操作系统指定的缺省处理，例如︰进程终止、进程挂起等
• 屏蔽( Mask )：禁止进程接收和处理信号，可能是暂时的(当处理同样类型的信号)

不足

传送的信息量小，只有一个信号类型

¶管道

进程间基于内存文件的通信机制

• 子进程从父进程继承文件描述符
• 缺省文件描述符:0 stdin,1 stdout,2 stderrI

进程不知道（或不关心!)的另一端

• 可能从键盘、文件、程序读取
• 可能写入到终端、文件、程序

与管道相关系统调用

• 读管道：read(fd, buffer, nbytes)，scanf()是基于它实现的
• 写管道：write(fd, buffer,nbytes)，printf()是基于它实现的
• 创建管道：pipe(rgfd)
  • rgfd是2个文件描述符组成的数组
  • rgfd[0]是读文件描述符
  • rgfd[1]是写文件描述符

管道示例

¶7、消息队列和共享内存

¶消息队列

消息队列是由操作系统维护的以字节序列为基本单位的间接通信机制

• 每个消息(Message)是一个字节序列
• 相同标识的消息组成按先进先出顺序组成一个消息队列(Message Queues )

消息队列相关系统调用

• msgget ( key, flags )：获取消息队列标识
• msgsnd ( QID, buf, size, flags )：发送消息
• msgrcv (QID, buf, size, type, flags )：接收消息
• msgctl( … )：消息队列控制

¶共享内存

共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制

进程

• 每个进程都有私有内存地址空间
• 每个进程的内存地址空间需明确设置共享内存段

线程

• 同一进程中的线程总是共享相同的内存地址空间

优点

• 快速、方便地共享数据

不足

• 必须用额外的同步机制来协调数据访问

共享内存的实现

特点

• 最快的方法
• 一个进程写另外一个进程立即可见
• 没有系统调用干预
• 没有数据复制
• 不提供同步：由程序员提供同步

共享内存相关系统调用

• shmget( key,size, flags )：创建共享段
• shmat( shmid, *shmaddr,flags )：把共享段映射到进程地址空间
• shmdt( *shmaddr )：取消共享段到进程地址空间的映射
• shmctl( …)：共享段控制
• 需要信号量等机制协调共享内存的访问冲突

¶十二、文件系统

¶1、文件系统和文件

文件系统是操作系统中管理持久性数据的子系统，提供数据存储和访问功能

• 组织、检索、读写访问数据
• 大多数计算机系统都有文件系统
• Google也是一个文件系统

文件是具有符号名，由字节序列构成的数据项集合

• 文件系统的基本数据单位
• 文件名是文件的标识符号

¶文件系统功能

分配文件磁盘空间

• 管理文件块（位置和顺序)
• 管理空闲空间(位置)
• 分配算法(策略)

管理文件集合

• 定位：文件及其内容
• 命名：通过名字找到文件
• 文件系统结构：文件组织方式

数据可靠和安全

• 安全：多层次保护数据安全
• 可靠：持久保存文件，避免系统崩溃、媒体错误、攻击等

¶文件属性

文件属性：名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间、

文件头：文件系统元数据中的文件信息

• 文件属性

• 文件存储位置和顺序

¶2、文件描述符

• 文件访问模式：进程访问文件数据前必须先“打开”文件
• 内核跟踪进程打开的所有文件：操作系统为每个进程维护一个打开文件表
• 文件描述符是打开文件的标识

¶文件描述符

操作系统在打开文件表中维护的打开文件状态和信息

文件指针

• 最近一次读写位置
• 每个进程分别维护自己的打开文件指针

文件打开计数

• 当前打开文件的次数
• 最后一个进程关闭文件时，将其从打开文件表中移除

文件的磁盘位置

• 缓存数据访问信息

访问权限

• 每个进程的文件访问模式信息

¶文件用户视图和系统视图

文件的用户视图

• 持久的数据结构

系统访问接口

• 字节序列的集合(UNIX)
• 系统不关心存储在磁盘上的数据结构

操作系统的文件视图

• 数据块的集合
• 数据块是逻辑存储单元，而扇区是物理存储
• 块大小不等于扇区大小

¶用户视图到系统视图转换

进程读文件

• 获取字节所在的数据块
• 返回数据块内对应部分

进程写文件

• 获取数据块
• 修改数据块中对应部分
• 写回数据块

文件系统中的基本操作单位是数据块

例如，getc()和putc()即使每次只访问1字节的数据，也需要缓存目标数据4096字节

¶访问模式

操作系统需要了解进程如何访问文件

顺序访问：按字节依次读取
大多数的文件访问都是顺序访问

随机访问：从中间读写

• 不常用,但仍然重要
• 例如，虚拟内存中把内存页存储在文件

索引访问：依据数据特征索引

• 通常操作系统不完整提供索引访问
• 数据库是建立在索引内容的磁盘访问上

¶文件内部结构

• 无结构：单词、字节序列
• 简单记录结构：
  • 分列
  • 固定长度
  • 可变长度
• 复杂结构
  • 格式化的文档(如，MS Word, PDF)
  • 可执行文件

¶文件共享和访问控制

多用户系统中的文件共享是很必要的

访问控制

• 每个用户能够获得哪些文件的哪些访问权限
• 访问模式:读、写、执行、删除、列表等l

文件访问控制列表(ACL)

• <文件实体，权限>

Unix模式

• <用户|组|所有人，读|写|可执行>
• 用户标识ID：识别用户，表明每个用户所允许的权限及保护模式
• 组标识ID：允许用户组成组，并指定了组访问权限

¶语义一致性

规定多进程如何同时访问共享文件

• 与同步算法相似
• 因磁盘I/O和网络延迟而设计简单

Unix文件系统(UFS)语义

• 对打开文件的写入内容立即对其他打开同一文件的其他用户可见
• 共享文件指针允许多用户同时读取和写入文件

会话语义

• 写入内容只有当文件关闭时可见

读写锁

• 一些操作系统和文件系统提供该功能

¶3、目录&文件别名&文件系统

¶分层文件系统

文件以目录的方式组织起来

目录是一类特殊的文件：目录的内容是文件索引表<文件名,指向文件的指针>

目录和文件的树型结构：早期的文件系统是扁平的(只有一层目录)

¶目录操作

典型目录操作

• 搜索文件
• 创建文件
• 删除文件
• 列目录
• 重命名文件
• 遍历路径

操作系统应该只允许内核修改目录

• 确保映射的完整性
• 应用程序通过系统调用访问目录

¶目录实现

文件名的线性列表，包涵了指向数据块的指针

• 编程简单
• 执行耗时

哈希表-哈希数据结构的线性表

• 减少目录搜索时间
• 冲突-两个文件名的哈希值相同
• 固定大小

¶文件别名

两个或多个文件名关联同一个文件

• 硬链接：多个文件项指向一个文件
• 软链接：以“快捷方式”指向其他文件，通过存储真实文件的逻辑名称来实现

¶文件目录中的循环

如何保证没有循环?

• 只允许到文件的链接，不允许在子目录的链接
• 增加链接时，用循环检测算法确定是否合理

更多实践

• 限制路径可遍历文件目录的数量

¶名字解析（路径解析）

名字解祈：把逻辑名字转换成物理资源（如文件)

• 依据路径名，在文件系统中找到实际文件位置
• 遍历文件目录直到找到目标文件

举例：解析“/bin/ls"

• 读取根目录的文件头(在磁盘固定位置)
• 读取根目录的数据块，搜索“bin”项
• 读取bin的文件头
• 读取bin的数据块;搜索“ls”顶
• 读取ls的文件头

当前工作目录(PWD)

• 每个进程都会指向一个文件目录用于解析文件名
• 允许用户指定相对路径来代替绝对路径，如，PwD= " /bin”能够解析"ls”

¶文件系统挂载

• 文件系统需要先挂载才能被访问
• 未挂载的文件系统被挂载在挂载点上

¶文件系统种类

磁盘文件系统

• 文件存储在数据存储设备上，如磁盘
• 例如：FAT,NTFS, ext2/3,ISO9660,等

数据库文件系统

• 文件特征是可被寻址（辨识）的
• 例如：WinFS

日志文件系统

• 记录文件系统的修改/事件

网络/分布式文件系统

• 例如：FS,SMB,AFS,GFS

特殊/虚拟文件系统

¶网络&分布式文件系统

文件可以通过网络被共享

• 文件位于远程服务器
• 客户端远程挂载服务器文件系统
• 标准系统文件访问被转换成远程访问
• 标准文件共享协议：NFS for Unix,CIFS for Windows

分布式文件系统的挑战

• 客户端和客户端上的用户辨别起来很复杂
• 例如，NFS是不安全的
• 一致性问题
• 错误处理模式

¶4、虚拟文件系统

¶文件系统的实现

分层结构

• 虚拟(逻辑)文件系统(VFS,Virtual File System)
• 特定文件系统模块

¶虚拟文件系统

目的

• 对所有不同文件系统的抽象

功能

• 提供相同的文件和文件系统接口
• 管理所有文件和文件系统关联的数据结构
• 高效查询例程,遍历文件系统
• 与特定文件系统模块的交互

¶文件系统数据结构

文件卷控制块(Unix: "superblock)

• 每个文件系统一个
• 文件系统详细信息
• 块、块大小、空余块、计数/指针等

文件控制块(Unix: “vnode” or"inode” )

• 每个文件一个
• 文件详细信息
• 访问权限、拥有者、大小、数据块位置等

目录项(Linux: “dentry” )

• 每个目录项一个(目录和文件)
• 将目录项数据结构及树型布局编码成树型数据结构
• 指向文件控制块、父目录、子目录等

¶文件系统数据结构

文件系统数据结构

• 卷控制块(每个文件系统一个)

• 文件控制块(每个文件一个)

• 目录节点(每个目录项一个)

持久存储在外存中

• 存储设备的数据块中

当需要时加载进内存

• 卷控制模块：当文件系统挂载时进入内存
• 文件控制块：当文件被访问时进入每次
• 目录节点：在遍历一个文件路径时进入内存

¶文件系统存储视图

¶5、文件缓存&打开文件

¶多种磁盘缓存位置

¶数据块缓存

数据块按需读入内存

• 提供read()操作
• 预读：预先读取后面的数据块

数据块使用后被缓存

• 假设数据将会再次用到
• 写操作可能被缓存和延迟写入

两种数据块缓存方式

• 数据块缓存
• 页缓存：统一缓存数据块和内存页

¶页缓存

虚拟页式存储

• 在虚拟地址空间中虚拟页面可映射到本地外存文件中

文件数据块的页缓存

• 在虚拟内存中文件数据块被映射成页
• 文件的读/写操作被转换成对内存的访问
• 可能导致缺页和/或设置为脏页
• 问题：页置换算法需要协调虚拟存储和页缓存间的页面数

¶打开文件数据结构

文件描述符

• 每个被打开的文件都有一个文件描述符
• 文件状态信息
  目录项、当前文件指针、文件操作设置等

打开文件表

• 每个进程一个进程打开文件表
• 一个系统级的打开文件表
• 有文件被打开时，文件卷就不能被卸载

¶打开文件表

¶打开文件锁

一些文件系统提供文件锁，用于协调多进程的文件访问

• 强制：根据锁保持情况和访问需求确定是否拒绝访问
• 劝告：进程可以查找锁的状态来决定怎么做

¶6、文件分配

¶文件大小

大多数文件都很小

• 需要对小文件提供很好的支持
• 块空间不能太大

一些文件非常大

• 必须支持大文件(64位文件偏移)
• 大文件访问需要高效

¶文件分配

如何表示分配给一个文件数据块的位置和顺序！

分配方式

• 连续分配
• 链式分配
• 索引分配

指标

• 存储效率：外部碎片等
• 读写性能：访问速度

¶连续分配

文件头指定起始块和长度

分配策略

• 最先匹配
• 最佳匹配

优点

• 文件读取表现好
• 高效的顺序和随机访问

缺点

• 碎片!
• 文件增长问题，预分配? 按需分配?

¶链式分配

文件以数据块链表方式存储！

文件头包含了到第一块和最后一块的指针！

优点

• 创建、增大、缩小很容易
• 没有碎片

缺点

• 无法实现真正的随机访问
• 可靠性差：破坏一个链，后面的数据块就丢了

¶索引分配

为每个文件创建一个索引数据块

指向文件数据块的指针列表

文件头包含了索引数据块指针

优点

• 创建、增大、缩小很容易
• 没有碎片
• 支持直接访问

缺点

• 当文件很小时，存储索引的开销大
• 如何处理大文件?

¶大文件的索引分配

¶UFS多级索引分配

UFS：unix file system

文件头包含13个指针

• 10个指针指向数据块
• 第11个指针指向索引块
• 第12个指针指向二级索引块
• 第13个指针指向三级索引块

效果

• 提高了文件大小限制阀值
• 动态分配数据块，文件扩展很容易
• 小文件开销小
• 只为大文件分配间接数据块，大文件在访问数据块时需要大量查询

¶7、空闲空间管理&冗余磁盘阵列

¶空闲空间管理

跟踪记录文件卷中未分配的数据块！

采用什么数据结构表示空闲空间列表?

¶位图

用位图代表空闲数据块列表

• 111111111111111001110101011101111…
• Di = 0 表明数据块i是空闲，否则，表示已分配

使用简单但是可能会是一个大的很大向量表

• 160GB磁盘->40M数据块->5MB位图
• 假定空闲空间在磁盘中均匀分布，则找到“0”之前要扫描n/r
• n = 磁盘上数据块的总数
• r = 空闲块的数目

其他空闲空间组织方式

¶磁盘分区

通常磁盘通过分区来最大限度减小寻道时间

• 分区是一组柱面的集合
• 每个分区都可视为逻辑上独立的磁盘

¶典型磁盘文件系统组织

文件卷：一个拥有完整文件系统实例的外存空间

通常常驻在磁盘的单个分区上

¶多磁盘管理

使用多磁盘可改善

• 吞吐量(通过并行)
• 可靠性和可用性(通过冗余)

冗余磁盘阵列(RAID,Redundant Array of Inexpensive Disks)

• 多种磁盘管理技术

• RAID分类：如 RAID-0，RAID-1，RAID-5

冗余磁盘阵列的实现

• 软件：操作系统内核的文件卷管理
• 硬件：RAID硬件控制器(I/O)

¶RAID-0 磁盘条带化

• 把数据块分成多个子块，存储在独立的磁盘中
• 通过独立磁盘上并行数据块访问提供更大的磁盘带宽

¶RAID-1 磁盘镜像

• 向两个磁盘写入，从任何一个读取
• 可靠性成倍增长
• 读取性能线性增加

¶RAID-4 带校验的磁盘条带化

• 数据块级的磁盘条带化加专用奇偶校验磁盘

• 允许从任意一个故障磁盘中恢复

¶RAID-5 带分布式校验的磁盘条带化

¶基于位和基于块的磁盘条带化

• 条带化和奇偶校验按“字节”或者“位”
• RAID-0/4/5：基于数据块
• RAID-3：基于位

¶可纠正多个磁盘错误的冗余磁盘连列

• RAID-5：每组条带块有一个奇偶校验块，允许一个磁盘错误
• RAID-6：每组条带块有两个冗余块，允许两个磁盘错误

¶RAID嵌套

¶十三、I/O子系统

¶1、I/O特点

¶设备接口类型

• 字符设备：如：键盘/鼠标，串口，并口等
• 块设备：如：磁盘驱动器、磁带驱动器、光驱等
• 网络设备：如：以太网、无线、蓝牙等

¶设备访问特征

字符设备

• 访问特征

  • 以字节为单位顺序访问

• I/O命令

  • get()，put()等

  • 通常使用文件访问接口和语义

块设备

• 访问特征

  • 均匀的数据块访问

• I/O命令

  • 原始I/O或文件系统接口

  • 内存映射文件访问

网络设备

• 访问特征
  • 格式化报文交换
• I/O命令
  • send/receive网络报文
  • 通过网络接口支持多种网络协议

¶同步与异步I/O

阻塞I/O：“Wait”

• 读数据(read)时，进程将进入等待状态，直到完成数据读出
• 写数据(write)时，进程将进入等待状态，直到设备完成数据写入处理

非阻塞I/O：“Don’ t Wait”

• 立即从read或write系统调返回，返回值为成功传输字节数
• read或write的传输字节数可能为零

异步I/O：“Tell Me Later”

• 读数据时，使用指针标记好用户缓冲区，立即返回。稍后内核将填充缓冲区并通知用户
• 写数据时，使用指针标记好用户缓冲区，立即返回。稍后内核将处理数据并通知用户

¶2、I/O结构

¶一个例子

北桥：连接高速设备

• 内存
• AGP/PCI-Express
• Built-in display

南桥：连接I/O设备

• ATA/IDE
• PCI总线
• USB/Firewire总线
• Serial/ Parallel接口
• DMA控制器
• Interrupt控制器
• RTC,ACPI,BIOS,…

¶CPU与设备连接

设备控制器

• CPU和I/O设备间的接口
• 向CPU提供特殊指令和寄存器

I/O地址

• CPU用来控制I/O硬件
• 内存地址或端口号
  • I/O指令
  • 内存映射I/O

CPU与设备的通信方式

• 轮询、设备中断 和 DMA

¶I/O指令和内存映射I/O

I/O指令

• 通过I/O端口号访问设备寄存器
• 特殊的CPU指令：out 0x21,AL

内存映射I/O

• 设备的寄存器/存储被映射到内存物理地址空间中
• 通过内存load/store指令完成I/О操作
• MMU设置映射，硬件跳线或程序在启动时设置地址

¶内核I/O结构

¶IO请求生命周期

¶3、I/O数据传输

¶CPU与设备控制器的数据传输

程序控制I/O(PIO,Programmed I/O)

• 通过CPU的in/out或者load/store传输所有数据

• 特点

  • 硬件简单，编程容易

  • 消耗的CPU时间和数据量成正比

• 适用于简单的、小型的设备I/O

直接内存访问(DMA)

• 设备控制器可直接访问系统总线
• 控制器直接与内存互相传输数据
• 特点
  • 设备传输数据不影响CPU
  • 需要CPU参与设置
• 适用于高吞吐量I/O

¶通过直接IO寻址读取磁盘数据

¶I/O设备通知操作系统的机制

操作系统需要了解设备状态

• I/O操作完成时间
• I/O操作遇到错误

两种方式

• CPU主动轮询
• 设备中断

¶轮询

I/O设备在特定的状态寄存器中放置状态和错误信息

操作系统定期检测状态寄存器

特点

• 简单
• I/O操作频繁或不可预测时，开销大和延时长

¶设备中断

设备中断处理流程

• CPU在I/O之前设置任务参数
• CPU发出I/O请求后，继续执行其他任务
• I/O设备处理I/O请求
• I/О设备处理完成时，触发CPU中断请求
• CPU接收中断，分发到相应中断处理例程

特点

• 处理不可预测事件效果好
• 开销相对较高

一些设备可能结合了轮询和设备中断

• 如：高带宽网络设备
• 第一个传入数据包到达前采用中断
• 轮询后面的数据包直到硬件缓存为空

¶中断I/O处理流程

少了一条第六到第一条的箭头！

¶4、磁盘调度

¶磁盘工作机制和性能参数

读取或写入时，磁头必须被定位在期望的磁道，并从所期望的柱面和扇区的开始

寻道时间：定位到期望的磁道所花费的时间

旋转延迟：从零扇区开始处到达目的地花费的时间

平均旋转延迟时间 = 磁盘旋转一周时间的一半

¶磁盘I/O传输时间

传输时间公式：

• Ta：访问时间
• Ts：寻道时间
• 1/2r：旋转延迟
  • 1/r：旋转一周的时间
• b/rN：传输时间
  • b：传输的比特数
  • N：磁道上的比特数
  • r：磁盘转数

¶磁盘调度算法

通过优化磁盘访问请求顺序来提高磁盘访问性能

• 寻道时间是磁盘访问最耗时的部分
• 同时会有多个在同一磁盘上的I/O请求
• 随机处理磁盘访问请求的性能表现很差

¶先进先出算法 FIFO

• 按顺序处理请求
• 公平对待所有进程
• 在有很多进程的情况下，接近随机调度的性能

算法示例

¶最短服务时间优先 SSTF

• 选择从磁臂当前位置需要移动最少的I/O请求
• 总是选择最短寻道时间

算法示例

¶扫描算法 SCAN

• 磁臂在一个方向上移动，访问所有未完成的请求，直到磁臂到达该方向上最后的磁道
• 调换方向
• 也称为电梯算法(elevator algorithm)

算法示例

¶循环扫描算法 C-SCAN

• 限制了仅在一个方向上扫描
• 当最后一个磁道也被访问过了后，磁臂返回到磁盘的另外一端再次进行

¶C-LOOK算法

• 磁臂先到达该方向上最后一个请求处，然后立即反转，而不是先到最后点路径上的所有请求

¶N步扫描算法 N-step-SCAN

磁头粘着(Arm Stickiness)现象

• SSTF、SCAN及CSCAN等算法中，可能出现磁头停留在某处不动的情况
• 如：进程反复请求对某一磁道的I/O操作

N步扫描算法

• 将磁盘请求队列分成长度为N的子队列
• 按FIFO算法依次处理所有子队列
• 扫描算法处理每个队列

¶双队列扫描算法 FSCAN

FSCAN算法是N步扫描算法的简化

• FSCAN只将磁盘请求队列分成两个子队列

FSCAN算法

• 把磁盘I/O请求分成两个队列
• 交替使用扫描算法处理一个队列
• 新生成的磁盘I/O请求放入另一队列中
• 所有的新请求都将被推迟到下一次扫描时处理

¶5、磁盘缓存

¶磁盘缓存

缓存

• 数据传输双方访问速度差异较大时，引入的速度匹配中间层

磁盘缓存是磁盘扇区在内存中的缓存区

• 磁盘缓存的调度算法很类似虚拟存储调度算法
• 磁盘的访问频率远低于虚拟存储中的内存访问频率
• 通常磁盘缓存调度算法会比虚拟存储复杂

¶单缓存双缓存

单缓存类似生产者消费者算法，I/O设备输入时，用户进程就不能进行读取！

¶访问频率置换算法

访问频率置换算法(Frequency-based Replacement)

问题

• 在一段密集磁盘访问后，LFU算法的引用计变化无法反映当前的引用情况

算法思路

• 考虑磁盘访问的密集特征，对密集引用不计数
• 在短周期中使用LRU算法，而在长周期中LFU算法

把LRU算法中的特殊栈分成三部分，并在每个缓存块增加一个引用计数

• 新区域(New Section)
• 中间区域(Middle Section)
• 旧区域(Old Section)

栈中缓存块被访问时移到栈顶，如果该块在新区域，引用计数不变;否则，引用计数加1

• 在新区域中引用计数不变的目的是避免密集访问对引用计数不利影响
• 在中间区域和旧区域中引用计数加1是为了使用LFU算法

未缓存数据块读入后放在栈顶，引用计数为1

在旧区域中引用计数最小的缓存块被置换

• 中间区域的定义是为了避免新读入的缓存块在第一次出新区域时马上被置换，有一个过渡期