title

date

第一章

第一章的主要内容是 : 操作系统的一些知识

操作系统是什么？

用户角度：操作系统是一个控制软件

管理应用程序
为应用程序提供服务
杀死应用程序

程序角度：操作系统是资源管理器

管理外设、分配资源
抽象
- 将CPU抽象成进程
- 将磁盘抽象成文件
- 将内存抽象成地址空间

操作系统层次

位于硬件之上，应用程序之下。

操作系统的界面和内核

Linux Windows Android 的界面属于外壳(Shell) ，而不是内核(kernel)。操作系统研究的是内核，处于Shell之下。

操作系统内部组件

CPU调度器
物理内存管理
虚拟内存管理
文件系统管理
中断处理与设备驱动

操作系统特征

并发
- 一段时间内运行多个进程（并行 : 一个时间点运行多个进程，一般要求有多个CPU)
- 需要OS管理和调度
共享
- “同时”共享
- 互斥共享
虚拟
- 让每一个用户觉得的有一个计算机专门为他服务
异步
- 程序是走走停停，而不是一直运行

第二章

第二章的主要内容是 : 操作系统的异常/中断/系统调用

探究计算机启动过程

作用解析

Disk : 存放OS和Bootloader

BOIS : 基于I/O处理系统

Bootloader : 加载OS，将OS放入内存

结构

Disk

|___ OS

|___ Bootloader

开机流程

BIOS
- 开机后，寻找显卡和执行BIOS (此时, CS : IP = 0xF000 : 0xFFF0, CS/IP 两个寄存器)
- 将Bootloader从磁盘的引导扇区加载到0x7C00 (Bootloader一共占用512M字节的内存)
- 跳转到 CS : IP = 0x0000 : 0x7C00
Bootloader
- 将操作系统的代码和数据从硬盘加载到内存中
- 跳转到操作系统的起始地址

中断、异常、系统调用

中断

中断来源于外设，来自不同的硬件设备的计时器和网络的中断。

中断流程

硬件：设置中断标记（CPU初始化）

将内部、外部事件设置中断标记
中断事件的ID

软件

保存当前处理状态（寄存器之类的一些数据）
根据中断事件的ID跳转到中断服务程序，中断服务程序处理
清楚中断标记

异常

异常来源于不良的应用程序，非法指令或者其他坏的处理状态（如：内存出错）。

异常处理流程

保存现场
异常处理
1. 杀死了产生异常的程序
2. 重新执行异常指令
恢复现场

系统调用

系统调用来源于应用程序，应用程序主动向操作系统发出服务请求。程序访问主要是通过高层次的API，而不是直接调用系统调用函数。

APIs

Win32 API 用于Windows
POSIX API 用于 POSIX-based systems（包括UNIX，LINUX，Mac OS X）
Java API 用于JAVA虚拟机

特点

通常情况下，每个系统调用有对应的序号
- 系统调用接口根据这些序号来维护表的索引
系统调用接口调用内核态中预期的系统调用
- 并返回系统调用的状态和其他任何返回值
用户不需要知道系统调用是如何实现的
- 只需要获取API和了解操作系统将什么作为返回结果
- 操作系统接口的细节大部分都隐藏在API中

用户态：操作系统运行中，CPU处于的特权级别，不能直接执行特权指令

内核态：操作系统运行中，CPU处于的特权级别，可以执行任何一条指令

系统调用：触发CPU从用户态到内核态的转换，切换程序和内核的堆栈，需要一定的开销

跨越操作系统边界的开销（值得的且必须的，保证了操作系统的安全性）

在执行时间上的开销超过程序调用
开销：
- 建立中断、异常、系统调用号与对应服务例程映射关系的初始化开销
- 建立内核堆栈
- 验证参数
- 内核态映射到用户态的地址空间（更新页面映射权限）
- 内核态独立地址空间（TLB）

区别

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

异步：应用程序不知道什么时候会发生中断

同步：执行到某一条指令一定会发生该事件

为什么应用程序不能直接访问硬件？

在计算机运行时，内核是被信任的第三方
只有内核可以执行特权指令
为了方便应用程序

第三章

第三章的主要内容是 : 操作系统的物理内存管理

计算机体系结构

CPU
内存
I/O

内存分层体系

运行内存(主存) / 磁盘(虚拟内存). 主存是在运行程序时所需要保存的数据空间，而磁盘是用于持久化数据保存的数据空间.

CPU可以访问的内存包括两大类 : 寄存器 / cache(L1缓存 / L2缓存)

层次

微处理器(CPU访问)

|___CPU寄存器 / L1缓存

|___L2缓存

主存(程序访问)

磁盘(程序访问)

从CPU寄存器到磁盘，读写速度不断降低，单位成本不断降低，大小不断增大。

内存管理目标

抽象：逻辑地址空间
保护：独立地址空间
共享：访问相同内存
虚拟：更多的地址空间

内存管理方法

程序重定位
分段
分页
虚拟内存
按需分页虚拟内存

实现高度依赖于硬件, 其中内存管理单元(MMU)负责处理CPU的内存访问请求

地址空间

地址空间的定义

物理地址空间 —— 硬件支持的地址空间( address : [0, Max_sys] )
逻辑地址空间 —— 一个运行在程序所拥有的的内存范围( address : [0, Max_prog] )

连续内存分配

内存碎片问题

内存碎片问题指的是空闲的内存无法被利用

外部碎片 : 分配单元间的未使用内存
内部碎片 : 分配单元内的未使用内存

分区的动态分配

分区的动态分配方式有以下三种 :

第一匹配分配 : 在内存中找到第一个比需求大的空闲块, 分配给应用程序
最优适配分配 : 在内存中找到最小的空闲块, 分配给应用程序
最差适配分配 : 在内存中找到最大的空闲块, 分配给应用程序

分配方式的区别

分配方式	第一匹配分配	最优适配分配	最差适配分配
分配方式实现需求	1. 按地址排序的空闲块列表 2. 分配需要寻找一个合适的分区 3. 重分配需要检查是否可以合并相邻空闲分区	1. 按尺寸排序的空闲块列表 2. 分配需要寻找一个合适的分区 3. 重分配需要检查是否可以合并相邻空闲分区	1. 按尺寸排序的空闲块列表 2. 分配最大的分区 3. 重分配需要检查是否可以合并相邻空闲分区
优势	简单 / 易于产生更大空闲块	比较简单 / 大部分分配是小尺寸时高效	分配很快 / 大部分分配是中尺寸时高效
劣势	产生外部碎片 / 不确定性	产生外部碎片 / 重分配慢 / 产生很多没用的微小碎片	产生外部碎片 / 重分配慢 / 易于破碎大的空闲块以致大分区无法被分配

三种分配方式并无优劣之分，因为我们无法判断内存请求的大小

碎片整理方法

可以看到的是，三种分区动态分配的方式都会产生外部碎片，因此我们可以对碎片进行一定的整理来解决碎片问题。

压缩式碎片整理
- 重置程序以合并碎片
- 要求所有程序是动态可重置的
- 问题 :
  - 何时重置 ? (在程序处于等待状态时才可以重置)
  - 需要考虑内存拷贝的开销
交换式碎片整理
- 运行程序需要更多的内存时，抢占等待的程序并且回收它们的内存
- 问题 :
  - 哪些程序应该被回收 ?
- 情况 :
  
  运行中 : P3
  
  等待中 : P1 P2 P4
  
  内存分布 -> 主存 : OS / P1 / P3 / P2 / P4 磁盘 : 空
  
  当P3程序需要更大的内存时 ->
  
  内存分布 -> 主存 : OS / P1 / P3 / P2 磁盘 : P4

第四章

第四章的主要内容是：操作系统的非连续内存分配

第三章介绍的是连续内存管理, 即 : 操作系统加载到内存以及程序加载到内存中时, 分配一块连续的空闲(内存)块. 但是容易出现碎片问题, 这一章介绍的非连续内存分配可以有效的减少碎片的出现.

非连续内存分配的必要性

连续内存分配的缺点

分配给一个程序的物理内存是连续的
内存利用率低
有外碎片 / 内碎片的问题

非连续内存分配的优点

一个程序的物理地址空间是非连续的
更好的内存利用和管理
允许共享代码与数据(共享库等...)
支持动态加载和动态链接

非连续内存分配的缺点

建立虚拟地址和物理地址的转换难度大
- 软件方案
- 硬件方案(采用硬件方案) : 分段 / 分页

非连续内存分配

分段(Segmentation)

段 : 在程序中会有来自不同文件的函数 ; 在程序执行时, 不同的数据也有不同的字段, 比如 : 堆 / 栈 / .bss / .data 等

**分段 : ** 更好的分离和共享

程序的分段地址空间如下图所示 :

分段寻址方案

逻辑地址空间连续，但是物理地址空间不连续，使用映射机制进行关联.

一个段 : 一个内存"块"

程序访问内存地址需要 : 一个二维的二元组(s, addr) → (段号, 地址)

操作系统维护一张段表, 存储(段号, 物理地址中的起始地址, 长度限制)

物理地址 : 段表中的起始地址 + 二元组中的偏移地址

分页(Paging)

分页地址空间

划分物理内存至固定大小的帧(Frame)

大小是2的幂, 512 / 4096 / 8192

划分逻辑地址空间至相同大小的页(Page)

大小是2的幂, 512 / 4096 / 8192

建立方案 → 转换逻辑地址为物理地址(pages to frames)

页表
MMU / TLB

帧(Frame)

物理内存被分割为大小相等的帧. 一个内存物理地址是一个二元组(f, o) → (帧号, 帧内偏移)

帧号 : F位, 共有2^F个帧

帧内偏移 : S位, 每帧有2^S个字节

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

(例子 : 16-bit地址空间, 9-bit(512 byte) 大小的页帧物理地址 = (3,6) 物理地址 = 2^9 * 3 + 6 = 1542)

分页和分段的最大区别 : 这里的 S 是一个固定的数, 而分段中的长度限制不定

页(Page)

一个程序的逻辑地址空间被划分为大小相等的页. 页内偏移的大小 = 帧内偏移的大小页号大小 <> 帧号大小

一个逻辑地址是一个二元组(p, o) → (页号, 页内偏移)

页号 : P位, 共有2^P个页

页内偏移 : S位, 每页有2^S个字节

虚拟地址 = 2^S * p + o

页寻址方案

操作系统维护一张页表, 页表保存了逻辑地址——物理地址之间的映射关系

存储 : (页号, 帧号)

逻辑地址空间应当大于物理内存空间
页映射到帧
页是连续的虚拟内存
帧是非连续的物理内存(有助于减少碎片的产生)
不是所有的页都有对应的帧

页表(Page Table)

页表概述

每一个运行的程序都有一个页表

属于程序运行状态, 会动态变化
PTBR : 页表基址寄存器

转换流程

CPU根据程序的page的页号的若干位, 计算出索引值index, 在页表中搜索这个index, 得到的是帧号, 帧号和原本的offset组成物理地址.

页表中还有一些特殊标志位

dirty bit,
resident bit, (0 : 对应的物理页帧在内存中不存在 ; 1 : 存在)
clock / reference bit

转换实例

16位地址的系统

32KB的物理内存
每页的 1024 byte

逻辑地址空间 : (4, 0) ... (3, 1023)

页表 :

Flags | Frame nums

1 0 1 0 0 0 0 0 → 内存访问异常(可能要杀死程序)

0 1 1 0 0 1 0 0 → 页帧是4 偏移是 1023 → 物理地址 (4, 1023)

分页机制的性能问题

访问一个内存单元需要2次内存访问

一次用于获取页表项
一次用于访问数据

页表可能非常大

64位机器如果每页1024字节, 那么一个页表的大小会是多少？(2^64 / 2^10 = 2^54 存放不下)
每一个运行的程序都需要有一个页表

如何处理？

缓存(Caching)
间接(Indirection)访问

转换后备缓冲区(TLB)

缓解时间问题

Translation Look-aside Buffer(TLB) 是一个缓冲区. CPU中有快表TLB(可以将经常访问的页表存放在这边)

缓存近期访问的页帧转换表项

TLB使用关联内存实现, 具备快速访问性能
如果TLB命中, 物理页号可以很快被获取
如果TLB未命中, 对应的表项被更新到TLB中(x86的CPU由硬件实现, 其他的可能是由操作系统实现)

二级/多级页表

时间换空间

二级页表

将页号分为两个部分, 页表分为两个, 一级页号对应一级页表, 二级页号对应二级页表.
一级页号查表获得在二级页表的起始地址, 地址加上二级页号的值, 在二级页表中获得帧号
节约了一定的空间, 在一级页表中如果resident bit = 0, 可以使得在二级页表中不存储相关index,而只有一张页表的话, 这一些index都需要保留

多级页表

通过把页号分为k个部分, 来实现多级间接页表, 建立一棵页表"树"

反向页表

解决大地址空间问题

目的 : 根据帧号获得页号

反向页表只需要存在一张即可

有大地址空间(64-bits), 前向映射页表变得繁琐. 比如 : 使用了5级页表
不是让页表与逻辑地址空间的大小相对应, 而是当页表与物理地址空间的大小相对应. 逻辑地址空间增长速度快于物理地址空间

基于页寄存器(Page Registers)的方案

存储 (帧号, 页号) 使得表大小与物理内存大小相关, 而与逻辑内存关联减小.

每一个帧和一个寄存器关联, 寄存器内容包括 :

resident bit : 此帧是否被占用
occupier : 对应的页号 p
protection bits : 保护位

实例 :

物理内存大小是 : 4096 * 4096 = 4K * 4KB = 16 MB
页面大小是 : 4096 bytes = 4 KB
页帧数 : 4096 = 4 K
页寄存器使用的空间(假设8 bytes / register) : 8 * 4096 = 32 Kbytes
页寄存器带来的额外开销 : 32K / 16M = 0.2%
虚拟内存大小 : 任意

优势 :

转换表的大小相对于物理内存来说很小
转换表的大小跟逻辑地址空间的大小无关

劣势 :

需要的信息对调了, 即根据帧号可以找到页号
如何转换回来? (如何根据页号找到帧号)
在需要在反向页表中搜索想要的页号

基于关联内存(associative memory)的方案

硬件设计复杂, 容量不大, 需要放置在CPU中

如果帧数较少, 页寄存器可以被放置在关联内存中
在关联内存中查找逻辑页号
- 成功 : 帧号被提取
- 失败 : 页错误异常 (page fault)
限制因素:
- 大量的关联内存非常昂贵(难以在单个时钟周期内完成 ; 耗电)

基于哈希(hash)的方案

哈希函数 : h(PID, p) 从 PID 标号获得页号

在反向页表中通过哈希算法来搜索一个页对应的帧号

对页号做哈希计算, 为了在帧表中获取对应的帧号
页 i 被放置在表 f(i) 位置, 其中 f 是设定的哈希函数
为了查找页 i , 执行下列操作 :
- 计算哈希函数 f(i) 并且使用它作为页寄存器表的索引, 获取对应的页寄存器
- 检查寄存器标签是否包含 i, 如果包含, 则代表成功, 否则失败

第五章

第五章的主要内容是：操作系统的虚拟内存管理技术

虚拟内存的起因

使用硬盘/磁盘使更多的程序在有限的内存中运行

理想的存储器 : 更大更快更便宜和非易失性的存储区

覆盖技术

如果是程序太大, 超出了内存的容量, 可以采用手动的概率(overlay)技术, 只把需要的指令和数据保存在内存当中

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

原理 :

把程序按照其自身逻辑结构, 划分为若干个功能上相互独立的程序模块, 那些不会同时执行的模块共享同一块内存区域, 按时间先后来运行.

必要部分(常用功能)的代码和数据常驻内存;
可选部分(不常用功能)在其他程序模块中实现, 平时存放在外存中, 在需要用到时才装入内存;
不存在调用关系的模块不必同时装入到内存, 从而可以相互覆盖, 即这些模块共用一个分区.

也就是说,程序松耦合的部分可以按需装入内存,不需要的时候放在外存中,多个不常用部分共用一个分区.

实例 :

A(20k) B(50k) ____ D(30k) | ____ C(30k) ____ E(20k) | F(40k)

因此不需要将整个程序190k的数据全部放入内存中, 而是划分为常驻区(20k) 覆盖区0(50k) 覆盖区1(40k) 压缩至了110k的内存空间使用

缺点 :

由程序员来把一个大的程序划分为若干个小的功能模块, 并确定各个模块之间的覆盖关系, 费时费力, 增加了编程的复杂度;
覆盖模块并从外存装入内存, 实际上是以时间延长来换取空间节省.

交换技术

如果是程序太多, 超过了内存的容量, 可以采用自动的交换(swapping)技术, 把暂时不能执行的程序送到外存中

目的 : 多道程序在内存时, 让正在运行的程序或需要运行的程序获得更多的内存资源

原理 :

可将暂时不能运行的程序送到外存, 从而获得空闲内存空间. 操作系统把一个进程的整个地址空间的内容保存到外存中(换出 swap out), 而将外存中的某个进程的地址空间读入到内存中(换入 swap in). 换入换出内容的大小为整个程序的地址空间.

存在问题 :

交换时机的确定 : 何时需要发生交换? 只当内存空间不够或有不够的危险时换出;
交换区的大小 : 必须足够大以存放所有用户进程的所有内存映像的拷贝, 必须能够对这些内存映像进行直接存取
程序换入时的重定位 : 换出后再换入的内存位置一定要在原来的位置上嘛?(可能出现寻址问题) 最好采用动态地址映射的方法

覆盖技术和交换技术的对比

特点 :

覆盖只能发生在那些相互之间没有调用关系的程序模块之间, 因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构.
交换技术是以在内存中的程序大小为单位进行的, 它不需要程序员给出各个模块之间的逻辑覆盖结构.
换言之, 交换发生在内存中程序与管理程序或操作系统之间, 而覆盖则发生在运行程序的内部.

在内存不够用的情形下, 可以采用覆盖技术和交换技术, 但是 :

覆盖技术 : 需要程序要自己把整个程序划分为若干个小的功能模块, 并确定各个模块之间的覆盖关系, 增加了程序员的负担.
交换技术 : 以进程作为交换的单位, 需要把进程的整个地址空间都换入换出, 增加了处理器的开销.

虚拟内存管理技术

如果想要在有限容量的内存中, 以更小的页粒度为单位装入更多更大的程序, 可以采用自动的虚拟存储技术

目标

像覆盖技术那样, 不是把程序的所有内容都放在内存中, 因而能够运行比当前的空闲内存空间还要大的程序. 但做的更好, 由操作系统自动来完成, 无需程序员的干涉.

像交换技术那样, 能够实现进程在内存与外存之间的交换, 因而获得更多的空闲内存空间. 但做的更好, 只对进程的部分内容在内存和外存之间进行交换.
程序局部性原理

程序的局部性原理(principle of locality) : 指程序在执行过程中的一个较短时期, 所执行的指令地址和指令的操作数地址, 分别局限于一定的区域.
- 时间局部性 : 一条指令的一次执行和下次执行, 一个数据的一次访问和下次访问都集中在一个较短时期内 ;
- 空间局部性 : 当前指令和邻近的几条指令, 当前访问的数据和邻近的几个数据都集中在一个较小区域内.
程序的局部性原理表明, 从理论上来说, 虚拟存储技术是能够实现的. 而且在实现了以后应该是能够取得一个满意的效果.

实例 :
```
题目描述 :
页面大小为4k, 分配给每个进程的物理页面是1. 
在一个进程中, 定义了如下的二维数组 int A[1024][1024]. 该数组按行存放在内存, 每一行放在一个页面中.
考虑一下程序的编写方法对缺页率的影响?

程序编写方法1 : (发生了1024*1024次缺页中断)
for(j = 0; j < 1024; j++)
		for(i = 0; i < 1024; i++)
				A[i][j] = 0;

程序编写方法2 : (发生了1024次缺页中断)
for(i = 0; i < 1024; i++)
		for(j = 0; j < 1024; j++)
				A[i][j] = 0;
```
基本概念

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

页式内存管理

页表 : 完成逻辑页到物理页帧的映射

根据页号去页表中寻找索引, 先查看 resident bit 是否为0, 0表示不存在, 1表示映射关系存在, 获得帧号加上原本的偏移, 获得了物理地址.

虚拟页式内存管理
- 大部分虚拟存储系统都采用虚拟页式存储管理技术, 即在页式存储管理的基础上, 增加请求调页和页面置换功能.
- 基本思路
  - 当一个用户程序要调入内存运行时, 不是将该程序的所有页面都装入内存, 而是只装入部分的页面, 就可启动程序运行.
  - 在运行的过程中, 如果发现要运行的程序或要访问的数据不再内存, 则向系统发出缺页的中断请求, 系统在处理这个中断时, 将外存中相应的页面调入内存, 使得该程序能够继续运行.
- 页表表项
  
  逻辑页号 | 访问位 | 修改位 | 保护位 | 驻留位 | 物理页帧号
  
  驻留位 : 表示该页是在内存中还是在外存.
  
  保护位 : 表示允许对该页做何种类型的访问, 如只读, 可读写, 可执行等
  
  修改位 : 表示此页在内存中是否被修改过. 当系统回收该物理页面时, 根据此位来决定是否把它的内容写回外存
  
  访问位 : 如果该页被访问过(包括读写操作), 则设置此位. 用于页面置换算法.
- 缺页中断处理过程 :
  1. 如果在内存中有空闲的物理页面, 则分配一物理页帧f, 然后转第4步; 否则转到第2步;
  2. 采用某种页面置换算法, 选择一个将被替换的物理页帧f, 它所对应的逻辑页为q, 如果该页在内存期间被修改过, 则需要把它写回外存;
  3. 对q所对应的页表项修改, 把驻留位置为0;
  4. 将需要访问的页p装入到物理页面f当中;
  5. 修改p所对应的页表项的内容, 把驻留位置为1, 把物理页帧号置为f;
  6. 重新运行被中断是指令.
  在何处保存未被映射的页?
  - 能够简单地识别在二级存储器中的页
  - 交换空间(磁盘或者文件) : 特殊格式, 用于存储未被映射的页面
  后备存储(二级存储) :
  - 一个虚拟地址空间的页面可以被映射到一个文件(在二级存储中)的某个位置
  - 代码段 : 映射到可执行二进制文件
  - 动态加载的共享库程序段 : 映射到动态调用的库文件
  - 其他段 : 可能被映射到交换文件(swap file)
- 虚拟内存性能
  
  为了便于理解分页的开销, 使用有效存储器访问时间 effective memory access time (EAT)
  
  EAT = 访存时间 * 页表命中几率 + page fault处理时间 * page fault几率
  
  实例 :
  
  访存时间 : 10 ns
  
  磁盘访问时间 : 5 ms
  
  参数 p = page fault 几率
  
  参数 q = dirty page 几率(对页面写操作)
  
  EAT = 10*(1-p) + 5000000*p*(1+q)

第六章

第六章的主要内容是：操作系统的虚拟内存管理技术中的页面置换算法

功能与目标

功能 : 当缺页中断发生, 需要调入新的页面而内存已满时, 选择内存当中哪个物理页面被置换.

目标 : 尽可能地减少页面的换进换出次数(即缺页中断的次数). 具体来说, 把未来不再使用的或短期内较少使用的页面换出, 通常只能在局部性原理指导下依据过去的统计数据来进行预测.

页面锁定 : 用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程. 实现的方式是 : 在页表中添加锁定标记位(lock bit).

实验设置与评价方法

实例 :

记录一个进程对页访问的一个轨迹

举例 : 虚拟地址跟踪(页号, 偏移)...
- (3,0) (1,9) (4,1) (2,1) (5,3) (2,0) ...
生成的页面轨迹
- 3, 1, 4, 2, 5, 2, 1, ...

模拟一个页面置换的行为并且记录产生页缺失数的数量

更少的缺失, 更好的性能

局部页面置换算法

最优页面置换算法

基本思路 : 当一个缺页中断发生时, 对于保存在内存当中的每一个逻辑页面, 计算在它的下一次访问之前, 还需等待多长时间, 从中选择等待时间最长的那个, 作为被置换的页面.

这是一种理想情况, 在实际系统中是无法实现的, 因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问.

可用作其他算法的性能评价的依据.(在一个模拟器上运行某个程序, 并记录每一次的页面访问情况, 在第二遍运行时即可使用最优算法)

先进先出算法

基本思路 : 选择在内存中驻留时间最长的页面淘汰. 具体来说, 系统维护着一个链表, 记录了所有位于内存当中的逻辑页面. 从链表的排列顺序来看, 链首页面的驻留时间最长, 链尾页面的驻留时间最短. 当发生一个缺页中断时, 把链首页面淘汰出去, 并把新的页面添加到链表的末尾.

性能较差, 调出的页面有可能是经常要访问的页面. 并且有 belady现象. FIFO算法很少单独使用.

最近最久未使用算法

LRU(Least Recently Used)

基本思路 : 当一个缺页中断发生时, 选择最久未使用的那个页面, 并淘汰.

它是对最优页面置换算法的一个近似, 其依据是程序的局部性原理, 即在最近一小段时间(最近几条指令)内, 如果某些页面被频繁地访问, 那么再将来的一小段时间内, 他们还可能会再一次被频繁地访问. 反过来说, 如果过去某些页面长时间未被访问, 那么在将来它们还可能会长时间地得不到访问.

LRU算法需要记录各个页面使用时间的先后顺序, 开销比较大.

两种可能的实现方法是 :

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

时钟页面置换算法

基本思路 :

需要用到页表项的访问位, 当一个页面被装入内存时, 把该位初始化为0. 然后如果这个页面被访问, 则把该位置设为1;

把各个页面组织成环形链表(类似钟表面), 把指针指向最老的页面(最先进来);

当发生一个缺页中断时, 考察指针所指向的最老页面, 若它的访问位为0, 立即淘汰; 若访问位为0, 然后指针往下移动一格. 如此下去, 直到找到被淘汰的页面, 然后把指针移动到下一格.

流程 :

如果访问页在物理内存中, 访问位置1.

如果不在物理页, 从指针当前指向的物理页开始, 如果访问位0, 替换当前页, 指针指向下一个物理页; 如果访问位为1, 置零以后访问下一个物理页再进行判断. 如果所有物理页的访问位都被清零了, 又回到了第一次指针所指向的物理页进行替换.

二次机会算法

因为考虑到时钟页面置换算法, 有时候会把一些 dirty bit 为1(有过写操作)的页面进行置换, 这样的话, 代价会比较大. 因此, 可以结合访问位和脏位一起来决定应该置换哪一页.

used dirty → used dirty

0 0 replace

0 1 0 0

1 0 0 0

1 1 0 1

相当于说, 替换的优先级, 没有读写也没写过, 那么直接走, 如果写过或者访问过, 那么给你一次机会, 如果又写过, 又访问过, 那么久给你两次机会.

最不常用算法

Least Frequently used, LFU

基本思路 : 当一个缺页中断发生时, 选择访问次数最少的那个页面, 并淘汰.

实现方法 : 对每一个页面设置一个访问计数器, 每当一个页面被访问时, 该页面的访问计数器加1. 当发生缺页中断时, 淘汰计数值最小的那个页面.

LRU和LFU的对比 : LRU考察的是多久未访问, 时间越短越好. 而LFU考察的是访问的次数和频度, 访问次数越多越好.

Belady现象(科学家名字)

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

出现原因 : FIFO算法的置换特征与进程访问内存的动态特征是矛盾的, 与置换算法的目标是不一致的(即替换较少使用的页面), 因此, 被他置换出去的页面不一定是进程不会访问的.

LRU / FIFO 和 Clock 的比较

LRU和FIFO都是先进先出的思路, 只不过LRU是针对页面最近访问时间来进行排序, 所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序(有一个页面的最近访问时间变了). 而FIFO是针对页面进入内存的时间来进行排序, 这个时间是固定不变的, 所以各个页面之间的先后顺序是固定的. 如果一个页面在进入内存后没有被访问, 那么它的最近访问时间就是它进入内存的时间. 换句话说, 如果内存当中的所有页面都未曾访问过, 那么LRU算法就退化为了FIFO算法.

例如 : 给进程分配3个物理页面, 逻辑页面的访问顺序是 : 1,2,3,4,5,6,1,2,3 ...

全局页面置换算法

工作集模型

前面介绍的各种页面置换算法, 都是基于一个前提, 即程序的局部性原理. 但是此原理是否成立?

如果局部性原理不成立, 那么各种页面置换算法就没有说明分别, 也没有什么意义. 例如 : 假设进程对逻辑页面的访问顺序是1,2,3,4,5,6,6,7,8,9..., 即单调递增, 那么在物理页面数有限的前提下, 不管采用何种置换算法, 每次的页面访问都必然导致缺页中断.
如果局部性原理是成立的, 那么如何来证明它的存在, 如何来对它进行定量地分析? 这就是工作集模型.

工作集

工作集 : 一个进程当前正在使用的逻辑页面集合.

可以使用一个二元函数 W(t, delta) 来表示 :

t 是当前的执行时刻;

delta 称为工作集窗口, 即一个定长的页面访问的时间窗口;

W(t, delta) = 在当前时刻 t 之前的 delta 时间窗口当中的所有页面所组成的集合(随着 t 的变化, 该集合也在不断的变化)

|W(t, delta)| 是工作集的大小, 即逻辑页的数量.

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

常驻集

常驻集是指在当前时刻, 进程实际驻留在内存当中的页面集合.

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

工作集页置换算法

当工作集窗口在滑动过程中, 如果页面不在集合中, 那么就会直接丢失这个不在窗口中页面, 而不会等待缺页中断再丢弃.

缺页率置换算法

可变分配策略 : 常驻集大小可变. 例如 : 每个进程在刚开始运行的时候, 先根据程序大小给它分配一定数目的物理页面, 然后在进程运行过程中, 再动态地调整常驻集的大小.

可采用全局页面置换的方式, 当发生一个缺页中断时, 被置换的页面可以是在其他进程当中, 各个并发进程竞争地使用物理页面.
优缺点 : 性能较好, 但增加了系统开销.
具体实现 : 可以使用缺页率算法来动态调整常驻集的大小.

缺页率 : 表示 "缺页次数 / 内存访问次数"

影响因素 : 页面置换算法, 分配给进程的物理页面数目, 页面本身的大小, 程序的编写方法.

抖动问题

如果分配给一个进程的物理页面太少, 不能包含整个的工作集, 即常驻集属于工作集, 那么进程将会造成很多的缺页中断, 需要频繁的在内存与外存之间替换页面, 从而使进程的运行速度变得很慢, 我们把这种状态称为 "抖动".
产生抖动的原因 : 随着驻留内存的进程数目增加, 分配给每个进程的物理页面数不断就减小, 缺页率不断上升. 所以OS要选择一个适当的进程数目和进程需要的帧数, 以便在并发水平和缺页率之间达到一个平衡.

第七章

第七章的主要内容是：进程

进程(process)描述

进程定义

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

进程的组成

进程包括 :

程序的代码
程序处理的数据
程序计数器中的值, 指示下一条将运行的指令
一组通用的寄存器的当前值, 堆, 栈
一组系统资源(如打开的文件)

进程和程序的联系 :

程序是产生进程的基础
程序的每次运行构成不同的进程
进程是程序功能的体现
通过多次执行, 一个程序可以对应多个进程, 通过调用关系, 一个进程可包括多个程序.

进程和程序的区别 :

进程是动态的, 程序是静态的 : 程序是有序代码的集合. 进程是程序的执行, 进程有核心态 / 用户态.
进程是暂时的, 程序是永久的. 进程是一个状态变化的过程, 程序可以长久保存.
进程和程序的组成不同 : 进程的组成包括程序, 数据和进程控制块(进程状态信息)

进程的特点

动态性 : 可动态地创建, 结果进程;

并发性 : 进程可以被独立调度并占用处理机运行; (并发:一段, 并行:一时刻)

独立性 : 不同进程的工作不相互影响;(页表是保障措施之一)

制约性 : 因访问共享数据, 资源或进程间同步而产生制约.

抛出了一个问题 : 如果你要设计一个OS, 怎么样来实现其中的进程管理机制?

进程控制结构

描述进程的数据结构 : 进程控制块 (Process Control Block)

操作系统为每个进程都维护了一个PCB, 用来保存与该进程有关的各种状态信息.

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

进程的创建 : 为该进程生成一个PCB

进程的终止 : 回收它的PCB

进程的组织管理 : 通过对PCB的组织管理来实现

(PCB具体包含什么信息? 如何组织的? 进程的状态转换?)

PCB有以下三大类信息 :

进程标志信息. 如本进程的标志, 本进程的产生者标志(父进程标志). 用户标志
处理机状态信息保存区 : 保存进程的运行现场信息 :
- 用户可见寄存器. 用户程序可以使用的数据, 地址等寄存器
- 控制和状态寄存器. 如程序计数器(PC), 程序状态字(PSW)
- 栈指针. 过程调用, 系统调用, 中断处理和返回时需要用到它
进程控制信息
- 调度和状态信息. 用于操作系统调度进程并占用处理机使用.
- 进程间通信信息. 为支持进程间与通信相关的各种标志, 信号, 信件等, 这些信息都存在接收方的进程控制块中.
- 存储管理信息. 包含有指向本进程映像存储空间的数据结构.
- 进程所用资源. 说明由进程打开, 使用的系统资源. 如打开的文件等.
- 有关数据结构的链接信息. 进程可以连接到一个进程队列中, 或连接到相关的其他进程的PCB.

进程的组织方式

链表 : 同一状态的进程其PCB成一链表, 多个状态对应多个不同的链表.(各状态的进程形成不同的链表 : 就绪链表, 阻塞链表)

索引表 : 同一状态的进程归入一个index表(由index指向PCB), 多个状态对应多个不同的index表(各状态的进行形成不同的索引表 : 就绪索引表, 阻塞索引表)

进程状态(state)

进程的生命期管理

进程创建

引起进程创建的3个主要事件 :

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

进程运行

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

(为何选择?如何选择?)

进程等待(阻塞)

在以下情况下, 进程等待(阻塞):

请求并等待系统服务, 无法马上完成
启动某种操作, 无法马上完成
需要的数据没有到达

进程只能自己阻塞自己, 因为只有进程自身才能知道何时需要等待某种事件的发生.

进程唤醒

唤醒进程的原因 :

被阻塞进程需要的资源可被满足
被阻塞进程等待的事件到达
将该进程的PCB插入到就绪队列

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

进程结束

在以下四种情况下, 进程结束 :

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

进程状态变化模型

进程的三种基本状态 : 进程在生命结束前处于三种基本状态之一.

不同系统设置的进程状态数目不同.

三种基本状态

运行状态(Running) : 当一个进程正在处理机上运行时
就绪状态(Ready) : 一个进程获得了除处理机之外的一切所需资源, 一旦得到处理机即可运行
等待状态(阻塞状态 Blocked) : 一个进程正在等待某一时间而暂停运行时. 如等待某资源, 等待输入/输出完成.

进程其它的基本状态

创建状态(New) : 一个进程正在被创建, 还没被转到就绪状态之前的状态

结束状态(Exit): 一个进程正在从系统中消失时的状态, 这是因为进程结束或由于其它原因所导致.

可能的状态变化如下 :

NULL → New : 一个新进程被产生出来执行一个程序

New → Ready: 当进程创建完成并初始化后, 一切就绪准备运行时, 变为就绪状态

Ready → Running : 处于就绪态的进程被进程调度程序选中后, 就分配到处理机上来运行

Running → Exit : 当进程表示它已经完成或者因出错, 当前运行进程会由操作系统作结束处理

Running → Ready : 处于运行状态的进程在其运行过程中, 由于分配它的处理机时间片用完而让出处理机

Running → Blocked: 当进程请求某样东西且必须等待时

Blocked → Ready : 当进程要等待某事件到来时, 它从阻塞状态变到就绪状态

进程挂起

进程挂起, 为了合理且充分地利用系统资源.

进程在挂起状态时, 意味着进程没有占用内存空间, 处在挂起状态的进程映像在磁盘上.(把进程放到磁盘上)

两种挂起状态

阻塞挂起状态 : 进程在外存并等待某事件的出现;
就绪挂起状态 : 进程在外存, 但只要进入内存, 即可运行.

与挂起相关的状态转换

挂起 : 把一个进程从内存转到外存, 可能有以下几种情况 :

阻塞到阻塞挂起 : 没有进程处于就绪状态或就绪进程要求更多内存资源时, 会进行这种转换, 以提交新进程或运行时就绪进程.
就绪到就绪挂起 : 当有高优先级阻塞(系统认为会很快就绪的)进程和低优先级就绪进程时, 系统会选择挂起低优先级就绪进程.
运行到就绪挂起 : 对抢先式分时系统, 当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时, 系统可能会把运行进程转导就绪挂起状态.

在外存时的状态转换 :

阻塞挂起到就绪挂起 : 当有阻塞挂起因相关事件出现时, 系统会把阻塞挂起进程转换为就绪挂起进程.

解挂, 激活 : 把一个进程从外存转到内存; 可能有以下几种情况 :

就绪挂起到就绪 : 没有就绪进程或挂起就绪进程优先级高于就绪进程时, 会进行这种转换.
阻塞挂起到阻塞 : 当一个进程释放足够内存时, 系统会把一个高优先级阻塞挂起(系统认为会很快出现所等待的事件)进程转换为阻塞进程.

抛出一个问题 : OS怎么通过PCB和定义的进程状态来管理PCB, 帮助完成进程的调度过程?

状态队列

由操作系统来维护一组队列, 用来表示系统当中所有进程的当前状态;
不同的状态分别用不同的队列来表示(就绪队列, 各种类型的阻塞队列);
每个进程的PCB都根据它的状态加入到相应的队列当中, 当一个进程的状态发生变化时, 它的PCB从一个状态中脱离出来, 加入到另外一个队列.

线程(thread)

为什么使用线程?

实例 : 编写一个MP3播放软件.

核心功能 : (1)从MP3音频文件中读取数据; (2)对数据进行解压缩; (3)把解压缩后的音频数据播放出来.

//单进程方式
while(1){
	Read();
	Decompress();
	Play();
}
//问题: 播放出来的声音能否连贯? 各个函数之间不是并发执行, 影响资源的使用效率.

//多进程
//进程1
while(1){
	Read();
}
//进程2
while(1){
	Decompress();
}
//进程3
while(1){
	Play();
}
//问题: 进程之间如何通信,共享数据?另外,维护进程的系统开销较大:
//创建进程时,分配资源,建立PCB;撤销进程时,回收资源,撤销PCB;进程切换时,保存当前进程的状态信息

因此需要提出一种新的实体, 满足以下特征:

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

这实体就是线程.

什么是线程

线程是进程当中的一条执行流程.

从两个方面重新理解进程:

从资源组合的角度: 进程把一组相关的资源组合起来,构成了一个资源平台(环境),包括地址空间(代码段,数据段),打开的文件等各种资源;
从运行的角度: 代码在这个资源平台上的一条执行流程(线程).

线程 = 进程 - 共享资源

线程的优缺点

线程的优点:

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

线程的缺点:

一个线程崩溃, 会导致其所属进程的所有线程崩溃.(给它了"权限"就得有更高的"责任")
线程所需的资源

不同的线程需要独立的寄存器和堆栈, 共享代码,数据和文件等.

线程和进程的比较

进程是资源分配单位, 线程是CPU调度单位;
进程拥有一个完整的资源平台, 而线程只独享必不可少的资源, 如寄存器和栈;
线程同样具有就绪,阻塞和执行三种基本状态,同样具有状态之间的转换关系;
线程能减少并发执行的时间和空间开销:
- 线程的创建时间比进程短;(直接利用所属进程的一些状态信息)
- 线程的终止时间比进程短;(不需要考虑把这些状态信息给释放)
- 同一进程内的线程切换时间比进程短;(同一进程不同线程的切换不需要切换页表)
- 由于同一进程的各线程之间共享内存和文件资源, 可直接进行不通过内核的通信.(直接通过内存地址读写资源)

线程的实现

主要有三种线程的实现方式:

用户线程 : 在用户空间实现; POSIX Pthreads, Mach C-threads, Solaris threads
内核线程 : 在内核中实现; Windows, Solaris, Linux
轻量级进程: 在内核中实现,支持用户线程; Solaris

用户线程

操作系统只能看到进程, 看不到线程, 线程的TCB在线程库中实现;

在用户空间实现的线程机制, 它不依赖于操作系统的内核, 由一组用户级的线程库来完成线程的管理, 包括进程的创建,终止,同步和调度等.

由于用户线程的维护由相应的进程来完成(通过线程库函数),不需要操作系统内核了解用户进程的存在,可用于不支持线程技术的多进程操作系统;
每个进程都需要它自己私有的线程控制块(TCB)列表,用来跟踪记录它的各个线程的状态信息(PC,栈指针,寄存器),TCB由线程库函数来维护;
用户线程的切换也是由线程库函数来完成,无需用户态/核心态切换,所以速度特别快;
允许每个进程拥有自定义的线程调度算法.

用户线程的缺点:

阻塞性的系统调用如何实现?如果一个线程发起系统调用而阻塞,则整个进程在等待;
当一个线程开始运行时,除非它主动地交出CPU的使用权,否则它所在的进程当中的其他线程将无法运行;
由于时间片分配给进程,所以与其他进程比,在多线程执行时,每个线程得到的时间片较少,执行会较慢.

内核线程

操作系统能够看到进程也可能看到线程,线程在内核中实现;

内核线程是在操作系统的内核当中实现的一种线程机制,由操作系统的内核来完成线程的创建,终止和管理.

在支持内核线程的操作系统中,由内核来维护进程和线程的上下文信息(PCB和TCB);
线程的创建,终止和切换都是通过系统调用,内核函数的方式来进行,由内核来完成,因此系统开销较大;
在一个进程当中,如果某个内核线程发起系统调用而被阻塞,并不会影响其他内核线程的运行;
时间片分配给线程,多线程的进程获得更多CPU时间;
Windows NT 和 Windows 2000/XP 支持内核线程.

轻量级进程

它是内核支持的用户线程.一个进程可以有一个或多个轻量化进程,每个量级进程由一个单独的内核线程来支持.(Solaris,Linux)

上下文切换

停止当前运行进程(从运行状态变成其他状态),并且调度其他进程(转变为运行状态)

必须在切换之前存储许多部分的进程上下文
必须能够在之后恢复他们,所以进程不能显示它曾经被暂停过
必须快速(上下文切换时非常频繁)

需要存储什么上下文?

寄存器(PC,SP...),CPU状态等信息
一些时候可能会费时,所以我们应该尽可能避免

操作系统为活跃进程准备了进程控制块

操作系统将进程控制块放置在一个合适的队列中

就绪队列
等待IO队列(每个设备的队列)
僵尸队列

进程控制

创建进程

fork()的简单实现

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

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

在fork()操作中内存复制是没有作用的
子进程将可能关闭打开的文件和连接
开销因此是最高的
为什么不能结合它们在一个调用中(OS/2, windows)?

vfork()

一个创建进程的系统调用,不需要创建一个同样的内存映像
一些时候称为轻量级fork()
子进程应该几乎立即调用exec()
现在不再使用如果我们使用 copy on write 技术

加载和执行进程

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

exec()调用允许一个进程"加载"一个不同的程序并且在main开始执行(事实上 _start)

它允许一个进程指定参数的数量(argc)和它字符串参数数组(argv)

如果调用成功(相同的进程,不同的程序)

代码,stack,heap重写

int pid = fork(); //创建子进程
if(pid == 0) {    //子进程
	exec_status = exec("calc", argc, argv0,argv1,...);
	printf("Why would I execute?");
} else if(pid > 0) { //父进程
	printf("Whose your daddy?");
	...
	child_status = wait(pid);
}

等待和终止进程

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

一个子进程向父进程返回一个值,所以父进程必须接受这个值并处理
wait()系统调用担任这个要求
- 它使父进程去睡眠来等待子进程的结束
- 当一个子进程调用exit()的时候,操作系统解锁父进程,并且将通过exit()传递得到的返回值作为wait调用的一个结果(连同子进程的pid一起)如果这里没有子进程存活,wait()立刻返回
- 当然,如果这里有为父进程的僵尸等待,wait()立即返回其中一个值(并且解除僵尸状态)
进程结束执行之后,它调用exit()
这个系统调用:
- 将这程序的"结果"作为一个参数
- 关闭所有打开的文件,连接等等
- 释放内存
- 释放大部分支持进程的操作系统结构
- 检查是否父进程是存活着的:
  - 如果是的话,它保留结果的值直到父进程需要它;在这种情况里,进程没有真正死亡,但是它进入了僵尸状态
  - 如果没有,它释放所有的数据结构,这个进程死亡
- 清理所有等待的僵尸进程
进程终止是最终的垃圾收集(资源回收)

第八章

第八章的主要内容是：调度算法(感觉清华这门课程前几章比较精彩,后续讲的有点混乱)

背景

上下文切换

切换CPU的当前任务, 从一个进程/线程到另一个
保存当前进程/线程在PCB/TCB中的执行上下文(CPU状态)
读取下一个进程/线程的上下文

CPU调度

从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程
调度程序: 挑选进程/线程的内核函数(通过一些调度策略)
什么时候进行调度?

内核运行调度程序的条件(满足一条即可)

一个进程从运行状态切换到等待状态
一个进程被终结

不可抢占

调度程序必须等待事件结束

可以抢占

调度程序在中断被相应后执行
当前的进程从运行切换到就绪, 或者一个进程从等待切换到就绪
当前运行的进程可以被换出

调度原则

调度策略

人们通常都需要"更快"的服务

什么是更快?
- 传输文件时的高带宽
- 玩游戏时的低延迟
- 这两个因素是独立的
和水管类比
- 低延迟: 喝水的时候想要一打开水龙头水就流出来
- 高带宽: 给游泳池充水时希望从水龙头里同时流出大量的水,并且不介意是否存在延迟
我们的目标:
- 减少响应时间: 及时处理用户的输出并且尽快将输出提供给用户
- 减少平均响应时间的波动: 在交互系统中,可预测性比高差异性低平均更重要
- 增加吞吐量: 减少开销(操作系统开销,上下文切换);系统资源的高效率用(CPU,IO设备)
- 减少等待时间: 减少每个进程的等待时间
程序执行模型

执行模型 : 程序在CPU突发和IO中交替
- 每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU
- 在时间分片机制下,线程可能在结束当前CPU突发前被迫放弃CPU
评价指标

CPU使用率: CPU处于忙状态所占时间的百分比

吞吐量: 在单位时间内完成的进程数量

周转时间: 一个进程从初始化到结束,包括所有等待时间所花费的时间

等待时间: 进程在就绪队列中的总时间

响应时间: 从一个请求被提交到产生第一次相应所花费的总时间

各指标在操作系统上的表现:

低延迟调度增加了交互式表现(如果移动了鼠标,但是屏幕中的光标却没动,我们可能会重启电脑)

操作系统需要保证低吞吐量不受影响(我想要结束长时间的编程,所以操作系统必须不时进行调度,即使存在许多交互任务)

吞吐量是操作系统的计算带宽

响应时间是操作系统的计算延迟
公平的目标

举例:
- 保证每个进程占用相同的CPU时间
- 这公平嘛?如果一个用户比其他用户运行更多的进程怎么办
举例:
- 保证每个进程都等待相同的时间
公平通常会增加平均响应时间

调度算法

FCFS(先来先服务)

First come, First Served

如果进程在执行中阻塞,队列中的下一个会得到CPU

优点: 简单

缺点:
- 平均等待时间波动较大
- 花费时间少的任务可能排在花费时间长的任务后面
- 可能导致IO和CPU之间的重叠处理(CPU密集型进程会导致IO设备闲置时,IO密集型进程也在等待)
SPN(SJF) SRT(短进程优先(短作业优先)短剩余时间优先)[最优平均等待时间]

Shortest Process Next(Shortest Job First) Shortest Remaining Time

选择预测的完成时间来将任务入队

可以是抢占的或者是不可抢占的

可能导致饥饿
- 连续的短任务流会使场任务饥饿
- 短任务可用时的任何场任务的CPU时间都会增加平均等待时间
需要预测未来
- 怎么预估下一个CPU突发的持续时间
- 简单的解决: 询问用户
- 如果用户欺骗就杀死进程
- 如果不知道怎么办?
HRRN(最高响应比优先)

Highest Response Ratio Next
Round Robin(轮循)

使用时间切片和抢占来轮流执行任务

在叫做量子(或者时间切片)的离散单元中分配处理器

时间片结束时,切换到下一个准备好的进程

花销: 额外的上下文切换

时间量子太大:
- 等待时间过长
- 极限情况退化成FCFS
时间量子太小:
- 反应迅速
- 吞吐量由于大量的上下文切换开销受到影响
目标:
- 选择一个合适的时间量子
- 经验规则: 维持上下文切换开销处于1%以内
Multilevel Feedback Queues(多级反馈队列)

优先级队列中的轮循

就绪队列被划分成独立的队列: 比如前台(交互),后台(批处理)

每个队列拥有自己的调度策略: 比如前台(RR),后台(FCFS)

调度必须在队列间进行:
- 固定优先级: 先处理前台,然后处理后台;可能导致饥饿
- 时间切片: 每个队列都得到一个确定的能够调度其进程的CPU总时间;比如80%使用RR的前台,20%使用FCFS的后台
一个进程可以在不同的队列中移动

例如,n级优先级-优先级调度在所有级别中,RR在每个级别中
- 时间量子大小随优先级级别增加而增加
- 如果任务在当前的时间量子中没有完成,则降到下一个优先级
优点: CPU密集型任务的优先级下降很快;IO密集型任务停留在高优先级
Fair Share Scheduling(公平共享调度)

FSS控制用户对系统资源的访问
- 一些用户组比其他用户组更重要
- 保证不重要的组无法垄断资源
- 未使用的资源按照每个组所分配的资源的比例来分配
- 没有达到资源使用率目标的组获得更高的优先级

评价方式

确定性建模: 确定一个工作量,然后计算每个算法的表现

队列模型: 用来处理随机工作负载的数学方法

实现/模拟: 建立一个允许算法运行实际数据的系统;最灵活,最具一般性

实时调度

实时系统

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

性能指标: 时间约束的及时性;速度和平均性能相对不重要

主要特征: 时间约束的可预测性

分类:
- 强实时系统: 需要在保证时间内完成重要的任务,必须完成
- 弱实时系统: 要求重要的进程的优先级更高,尽量完成,并非必须
任务(工作单元): 一次计算,一次文件读取,一次信息传递等

属性: 去的进展所需要的资源;定时参数.
单调速率(RM)
- 最佳静态优先级调度
- 通过周期安排优先级
- 周期越短优先级越高
- 执行周期最短的任务
截止日期最早优先(EDF)
- 最佳的动态优先级调度
- Deadline越早优先级越高
- 执行Deadline最早的任务

多处理器调度

多处理器的CPU调度更复杂:

多个相同的单处理器组成一个多处理器
优点: 复杂共享

对称多处理器(SMP)

每个处理器运行自己的调度程序
需要在调度程序中同步

优先级反转

可以发生在任务基于优先级的可抢占的调度机制中

当系统内的环境强制使高优先级任务等待低优先级任务时发生

第九章

第九章的主要内容是：同步

背景

第一章到第八章内容, 到目前为止

多道程序设计: 现代操作系统的重要特性
并行很有用(为什么?) 提示: 多个并发实体: CPU IO 用户等
进程,线程: 操作系统抽象出来用于支持多道程序设计
CPU调度: 实现多道程序设计的机制
调度算法: 不同的策略

独立的线程:

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

合作线程:

在多个线程中共享状态
不确定性
不可重现

不确定性和不可重现意味着bug可能是间歇性发生的

进程,线程;计算机,设备需要合作

合作优点:

共享资源
- 一台电脑,多个用户
- 一个银行存款余额,多台ATM机
- 嵌入式系统
加速
- IO操作和计算可以重叠
- 多处理器
模块化
- 将大程序分解成小程序 gcc会调用cpp,cc1,cc2,as,ld
- 使系统易于扩展

程序可以调用函数fork()来创建一个新的进程

操作系统需要分配一个新的并且唯一的进程ID
因此在内核中,这个系统调用会运行 new_pid = next_pid++;
翻译成机器指令:
- Load next_pid Reg1
- STORE Reg1 new_pid
- INC Reg1
- STORE Reg1 next_pid

假设两个进程并发执行

如果next_pid等于100, 那么其中一个进程得到的ID应该是100, 另一个进程的ID应该是101, next_pid应该增加到102
可能在INC前进行了上下文切换, 最终导致两个进程的pid都是100,而next_pid也是101

无论多个线程的指令序列怎样交替执行,程序都必须正常工作

多线程程序具有不确定性和不可重现的特点
不经过专门设计,调试难度很高

不确定性要求并行程序的正确性

先思考清楚问题,把程序的行为设计清楚
切忌给予着手编写代码,碰到问题再调试

一些概念

前面的现象称为Race Condition(竞态条件)

系统缺陷: 结果依赖于并发执行或者时间的顺序,时间

不确定性
不可重现

怎么样避免竞态?

Atomic Operator(原子操作)

原子操作是指一次不存在任何终端或者失败的执行

该执行成功结束
或者根本没有执行
并且不应发生任何部分执行的状态

实际上操作往往不是原子的

有些看上去是原子操作,实际上不是
连x++这样的简单语句,实际上是由三条指令构成的
有时候甚至连单条假期指令都不是原子的(Pipeline,super-scalar,out-of-order,pape fault)

临界区(Critical section)是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域

互斥(Mutual exclusion)是指当一个进程处于临界区并访问共享资源时,没有其他进程会处于临界区并且访问任何相同的共享资源

死锁(Dead lock)是指两个或以上进程,在相互等待完成特定任务,而最终没法将自身任务进行下去

饥饿(Starvation)是指一个可执行的进程,被调度器持续忽略,以至于虽然处于可执行状态却不被执行

临界区

互斥: 同一时间临界区中最多存在一个线程

Progress: 如果一个线程想要进入临界区,那么它最终会成功

有限等待: 如果一个线程i处于入口区,那么在i的请求被接受之前,其他线程进入临界区的时间是有限制的

无忙等待(可选): 如果一个进程在等待进入临界区,那么在它可以进入之前会被挂起

方法1:禁用硬件中断

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

硬件将中断处理延迟到中断被启用之后
大多数现代计算机体系结构都提供指令来完成

进入临界区

禁用中断

离开临界区

开启中断

一旦中断被禁用,线程就无法被停止

整个系统都会为你停下来
可能导致其他线程处于饥饿状态

要是临界区可以任意长怎么办?

无法限制响应中断所需的时间(可能存在硬件影响)

要小心使用,适合于较小的操作

方法2:基于软件的解决方案

满足进程Pi和Pj之间互斥的经典的基于软件的解决方法(1981年)

使用两个共享数据项

int turn; //指示该谁进入临界区
bool flag[]; //指示进程是否准备好进入临界区

进入临界区:

flag[i] = true;
turn = j;
while(flag[j] && turn == j);

退出临界区:

flag[i] = false;

实例:

do{
	flag[i] = true;
	turn = j;
	while(flag[j] && turn == j);
	CRITICAL SECTION
	flag[i] = false;
	REMAINDER SECTION
}while(true);

Bakery 算法(N个进程的临界区)

进入临界区之前,进程接收一个数字
得到的数字最小的进入临界区
如果进程Pi和Pj收到相同的数字,那么如果i<j,Pi先进入临界区,否则Pj先进入临界区
编号方案总是按照枚举的增加顺序生成数字

Dekker算法(1965): 第一个针对双线程例子的正确解决方案

Bakery算法(1979): 针对n线程的临界区问题解决方案

复杂: 需要两个进程的共享数据项

需要忙等待: 浪费CPU时间

没有硬件保证的情况下无真正的软件解决方案: Perterson算法需要原子的LOAD和STORE指令

方法3:更高级的抽象

硬件提供了一些原语

像中断禁用, 原子操作指令等
大多数现代体系结构都这样

操作系统提供更高级的编程抽象来简化并行编程

例如,锁,信号量
从硬件原语中构建

锁是一个抽象的数据结构

一个二进制状态(锁定,解锁),两种方法
Lock::Acquire() 锁被释放前一直等待,然后得到锁
Lock::Release() 锁释放,唤醒任何等待的进程

使用锁来编写临界区

前面的例子变得简单起来:

lock_next_pid->Acquire();
new_pid = next_pid++;
lock_next_pid->Release();

大多数现代体系结构都提供特殊的原子操作指令

通过特殊的内存访问电路
针对单处理器和多处理器

Test-and-Set 测试和置位

从内存中读取值
测试该值是否为1(然后返回真或假)
内存值设置为1

交换

交换内存中的两个值

bool TestandSet(bool *target){
		bool rv = *target;
		*target = true;
		return rv;
}

void Exchange(bool *a, bool *b){
		bool tmp = *a;
		*a = *b;
		*b = tmp;
}

总结

锁是更高等级的编程抽象
- 互斥可以使用锁来实现
- 通常需要一定等级的硬件支持
常用的三种实现方法
- 禁用中断(仅限于单处理器)
- 软件方法(复杂)
- 原子操作指令(单处理器或多处理器均可)
可选的实现内容:
- 有忙等待
- 无忙等待

第十章

第十章的主要内容是：信号量和管程

信号量

信号量的抽象数据类型

一个整形(sem),具有两个原子操作
P(): sem减一,如果sem<0,等待,否则继续
V(): sem加一,如果sem≤0,唤醒一个等待的P

信号量是整数

信号量是被保护的变量

初始化完成后,唯一改变一个信号量的值的办法是通过P()和V()
操作必须是原子

P()能够阻塞,V()不会阻塞

我们假定信号量是公平的

没有线程被阻塞在P()仍然堵塞如果V()被无限频繁调用(在同一个信号量)
在实践中,FIFO经常被使用

两个类型信号量

二进制信号量: 可以是0或1
计数信号量: 可以取任何非负数
两者相互表现(给定一个可以实现另一个)

信号量可以用在2个方面

互斥
条件同步(调度约束——一个线程等待另一个线程的事情发生)

信号量使用

用二进制信号量实现的互斥

mutex = new Semaphore(1);

mutex->P();
...
mutex->V();

用二进制信号量实现的调度约束

condition = new Semaphore(0);

//Thread A
...
condition->P(); //等待线程B某一些指令完成之后再继续运行,在此阻塞
...

//Thread B
...
condition->V(); //信号量增加唤醒线程A
...

一个线程等待另一个线程处理事情

比如生产东西或消费东西(生产者消费者模式),互斥(锁机制)是不够的

有界缓冲区的生产者-消费者问题
- 一个或者多个生产者产生数据将数据放在一个缓冲区里
- 单个消费者每次从缓冲区取出数据
- 在任何一个时间只有一个生产者或消费者可以访问该缓冲区
正确性要求
- 在任何一个时间只能有一个线程操作缓冲区(互斥)
- 当缓冲区为空时,消费者必须等待生产者(调度,同步约束)
- 当缓存区满,生产者必须等待消费者(调度,同步约束)
每个约束用一个单独的信号量
- 二进制信号量互斥
- 一般信号量 fullBuffers
- 一般信号了 emptyBuffers
```
class BoundedBuffer{
		mutex = new Semaphore(1);
		fullBuffers = new Semaphore(0);   //说明缓冲区初始为空
 		emptyBuffers = new Semaphore(n);  //同时可以有n个生产者来生产
};

BoundedBuffer::Deposit(c){
		emptyBuffers->P();
		mutex->P();
		Add c to the buffer;
		mutex->V();
		fullBuffers->V();
}

BoundedBuffer::Remove(c){
		fullBuffers->P();
		mutex->P();
		Remove c from buffer;
		mutex->V();
		emptyBuffers->V();
}
```

信号量实现

使用硬件原语

禁用中断
原子指令

类似锁

禁用中断

class Semaphore{
		int sem;
		WaitQueue q;
};

Semaphore::P(){
		--sem;
		if(sem < 0){
				Add this thread t to q;
				block(p);
		}
};

Semaphore::V(){
		++sem;
		if(sem <= 0){
				Remove a thread t from q;
				wakeup(t);
		}
}

信号量的双用途

互斥和条件同步
但等待条件是独立的互斥

读,开发代码比较困难

程序员必须非常精通信号量

容易出错

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

不能够处理死锁问题

管程

目的: 分离互斥和条件同步的关注

什么是管程

一个锁: 指定临界区
0或者多个条件变量: 等待,通知信号量用于管程并发访问共享数据

一般方法

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

Lock

Lock::Acquire() 等待直到锁可用,然后抢占锁
Lock::Release() 释放锁,唤醒等待者如果有

Condition Variable

允许等待状态进入临界区
- 允许处于等待(睡眠)的线程进入临界区
- 某个时刻原子释放锁进入睡眠
Wait() operation
- 释放锁,睡眠,重新获得锁放回
Signal() operation(or broadcast() operation)
- 唤醒等待者(或者所有等待者),如果有

实现

需要维持每个条件队列
线程等待的条件等待signal()

class Condition{
		int numWaiting = 0;
		WaitQueue q;
};

Condition::Wait(lock){
		numWaiting++;
		Add this thread t to q;
		release(lock);
		schedule(); //need mutex
		require(lock);
}

Condition::Signal(){
		if(numWaiting > 0){
				Remove a thread t from q;
				wakeup(t); //need mutex
				numWaiting--;
		}
}

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

class BoundedBuffer{
		Lock lock;
		int count = 0;  //buffer 为空
		Condition notFull, notEmpty;
};

BoundedBuffer::Deposit(c){
		lock->Acquire();    //管程的定义:只有一个线程能够进入管程
		while(count == n)
				notFull.Wait(&lock); //释放前面的锁
		Add c to the buffer;
		count++;
		notEmpty.Signal();
		lock->Release();
}

BoundedBuffer::Remove(c){
		lock->Acquire();
		while(count == 0)
				notEmpty.Wait(&lock);
		Remove c from buffer;
		count--;
		notFull.Signal();
		lock->Release();
}

开发,调试并行程序很难

非确定性的交叉指令

同步结构

锁: 互斥
条件变量: 有条件的同步
其他原语: 信号量

怎么样有效地使用这些结构

制定并遵循严格的程序设计风格,策略

经典同步问题

读者-写者问题

动机: 共享数据的访问

两种类型的使用者: 读者(不修改数据) 写者(读取和修改数据)

问题的约束:

允许同一时间有多个读者,但在任何时候只有一个写者
当没有写者时,读者才能访问数据
当没有读者和写者时,写者才能访问数据
在任何时候只能有一个线程可以操作共享变量

多个并发进程的数据集共享

读者: 只读数据集;他们不执行任何更新
写者: 可以读取和写入

共享数据

数据集
信号量CountMutex初始化为1
信号量WriteMutex初始化为1
整数Rcount初始化为0(当前读者个数)

读者优先设计

只要有一个读者处于活动状态, 后来的读者都会被接纳.如果读者源源不断的出现,那么写者使用处于阻塞状态.

//信号量实现
//writer
sem_wait(WriteMutex);
write;
sem_post(WriteMutex);

//reader
sem_wait(CountMutex);
if(Rcount == 0)
		sem_wait(WriteMutex); //确保后续不会有写者进入
++Rcount;
read;
--Rcount;
if(Rcount == 0)
		sem_post(WriteMutex); //全部读者全部离开才能唤醒写者
sem_post(CountMutex);

写者优先设计

一旦写者就绪,那么写者会尽可能的执行写操作.如果写者源源不断的出现的话,那么读者就始终处于阻塞状态.

//writer
Database::Write(){
		Wait until readers/writers;
		write database;
		check out - wake up waiting readers/writers;
}
//reader
Database::Read(){
		Wait until no writers;
		read database;
		check out - wake up waiting writers;
}

//管程实现
AR = 0; // # of active readers
AW = 0; // # of active writers
WR = 0; // # of waiting readers
WW = 0; // # of waiting writers
Condition okToRead;
Condition okToWrite;
Lock lock;
//writer
Public Database::Write(){
		//Wait until no readers/writers;
		StartWrite();
		write database;
		//check out - wake up waiting readers/writers;
		DoneWrite();
}

Private Database::StartWrite(){
		lock.Acquire();
		while((AW + AR) > 0){
				WW++;
				okToWrite.wait(&lock);
				WW--;		
		}
		AW++;
		lock.Release();
}

Private Database::DoneWrite(){
		lock.Acquire();
		AW--;
		if(WW > 0){
				okToWrite.signal();
		}
		else if(WR > 0){
				okToRead.broadcast(); //唤醒所有reader 
		}
		lock.Release();
}

//reader
Public Database::Read(){
		//Wait until no writers;
		StartRead();
		read database;
		//check out - wake up waiting writers;
		DoneRead();
}

Private Database::StartRead(){
		lock.Acquire();
		while(AW + WW > 0){    //关注等待的writer,体现出写者优先
				WR++;
				okToRead.wait(&lock);
				WR--;
		}
		AR++;
		lock.Release();
}

private Database::DoneRead(){
		lock.Acquire();
		AR--;
		if(AR == 0 && WW > 0){  //只有读者全部没有了,才需要唤醒
				okToWrite.signal();
		}
		lock.Release();
}

哲学家就餐问题(学习自 github.com/cyc2018)

共享数据:

Bowl of rice(data set)
Semaphone fork [5] initialized to 1

#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think(i);
        take_two(i);
        eat(i);
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
    check(RIGHT);
    up(&mutex);
}

void eat(int i) {
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

第十一章

第十一章的主要内容是：死锁和进程通信

死锁问题

一组阻塞的进程持有一种资源等待获取另一个进程所占有的一个资源

示例:

系统有2个磁带驱动器
P1和P2各有一个,都需要另外一个

系统模型

资源类型R1,R2,..,Rm(CPU, memory space, IO devices)

每个资源类型Ri有Wi个实例.

每个进程使用资源如下:

require,get ← free resource
use,hold ← requested,used resource
release ← free resource

可重复使用的资源

在一个时间只能有一个进程使用且不能被删除
进程获得资源,后来释放由其他进程重用
处理器,IO通道,主和副存储器,设备和数据结构,如文件,数据库和信号量
如果每个进程拥有一个资源并请求其他资源,死锁可能发生

使用资源

创建和销毁
在IO缓存区的中断,信号,消息,信息
如果接收消息阻塞可能会发生死锁
可能少见的组合事件会引起死锁

资源分配图

一组顶点V和边E的集合

V有两种类型:
- P={P1,P2,...,Pn},集合包括系统中的所有进程
- R={R1,R2,...,Rm},集合包括系统中的所有资源类型
requesting,claiming edge - directed edge Pi → Rj
assignment,holding edge - directed edge Rj → Pi

基本情况

如果图中不包含循环:

没有死锁

如果图中包含循环:

如果每个资源类只有一个实例,那么死锁
如果每个资源类有几个实例,可能死锁

死锁特征

死锁出现一定会出现以下四个条件,但是出现以下四个条件不一定死锁:

互斥: 在一个时间只能有一个进程使用资源
持有并等待: 进程保持至少一个资源正在等待获取其他进程持有的额外资源
无抢占: 一个资源只能被进程资源释放,进程已经完成了它的任务之后
循环等待: 存在等待进程集合{P0,P1,...,Pn},P0正在等待P1所占用的资源,P1正在等待P2占用的资源...Pn-1在等待Pn的资源,Pn正在等待P0所占用的资源

死锁处理方法

常见方法

确保系统永远不会进入死锁状态
运行系统进入死锁状态,然后恢复.
忽略这个问题,假装系统中从来没有发生死锁,用于大多数操作系统,包括UNIX

Deadlock Prevention 预防

限制申请方式

互斥 - 共享资源不是必须的,必须占用非共享资源
占用并等待 - 必须保证当一个进程请求的资源,它不持有任何其他资源
- 需要进程请求并分配其所有资源,它开始执行之前或允许进程请求资源仅当进程没有资源
- 资源利用率低,可能发生饥饿
无抢占 -
- 如果进程占有某些资源,并请求其他不能被立即分配的资源,则释放当前正占有的资源
- 被抢占资源添加到资源列表中
- 只有当它能够获得旧的资源以及它请求新的资源,进程可以得到执行
循环等待 - 对所有资源类型进行排序,并要求每个进程按照资源的顺序进行申请

Deadlock Avoidance 避免

需要系统具有一些额外的先验信息提供

最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目
资源的分配状态是通过限定提供与分配的资源数量,和进程的最大需求
死锁避免算法动态检查的资源分配状态,以确保永远不会有一个环形等待状态
当一个进程请求可用资源,系统必须判断立即分配是否能使系统处于安全状态
系统处于安全状态指: 针对所有进程,存在安全序列
序列<P1,P2,...,Pn>是安全的: 针对每个Pi,Pi要求的资源能够由当前可用的资源+所有的Pj持有的资源来满足,其中j<i.
- 如果Pi资源的需求不是立即可用,那么Pi可以等到所有Pj完成
- 当Pi完成后,Pi+1可以得到所需要的资源,执行,返回所分配的资源,并终止.
- 用同样的方法,Pi+2,Pi+3和Pn能获得其所需的资源.
如果系统处于安全状态→无死锁
如果系统处于不安全状态→可能死锁
避免死锁: 确保系统永远不会进入不安全状态

Deadlock Detection 检测

每个资源类型单一实例

Maintain wait-for graph

节点是进程
Pi→Pj: Pi等待Pj

定期调用检测算法来搜索图中是否存在循环

算法需要n^2次操作,n是图中顶点的数目

数据结构:

Available: 长度为M的向量表示每种类型可用资源的数量
Allocation: 一个nxm矩阵定义了当前分配给各个进程每种类型资源的数量,如果Alocation[i, j] = k, 进程Pi拥有资源Rj的k个实例
Request: 一个nxm矩阵表示各进程的当前请求.如果Request[i, j] = k,表示进程Pi请求k个资源Pj的实例

具体算法(跳过了,看视频)

检查算法使用

何时,使用什么样的频率来检测依赖于:

死锁多久可能会发生?
多少进程需要被回滚? one for each disjoint cycle

如果检测算法多次被调用,有可能是资源图有多个循环,所以我们无法分辨出多个可能死锁进程中的哪些"造成"死锁

Recovery from Deadlock 恢复

终止所有的死锁进程

在一个时间内终止一个进程直到死锁消除

终止进程的顺序应该是:

进程的优先级
进程运行了多久以及需要多少时间才能完成
进程占用的资源
进程完成需要的资源
多少进程需要被终止
进程是交互还是批处理

选择一个受孩子 - 最小的成本

回滚 - 返回到一些安全状态,重启进程到安全状态

饥饿 - 同一进程可能一直被选作受害者,包括回滚的数量

IPC

概述

进程通信的机制及同步

不使用共享变量的进程通信

IPC facility 提供2个操作:

send(message) - 消息大小固定或者可变
receive(message)

如果P和Q想通信,需要:

在它们之间建立通信链路
通过send/recevie交换消息

通信链路的实现

物理(例如,共享内存,硬件总线)
逻辑(例如,逻辑属性)

直接通信

进程必须正确的命名对方:

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

通信链路的属性

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

间接通信

定向从消息队列接收消息

每个消息对垒都有一个唯一的ID
只有它们共享了一个消息队列,进程才能够通信

通信链路的属性

只有进程共享一个共同的消息队列,才建立链路
链接可以与许多进程相关联
每对进程可以共享多个通信链路
链接可以是单向或者双向

操作

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

原语的定义如下:

send(A, message)
receive(A, message)
通信链路缓冲

通信链路缓存大小:
1. 0容量 - 0 message : 发送方必须等待接收方
2. 有限容量 - n messages的有限长度 : 发送方必须等待,如果队列满
3. 无限容量 - 无限长度 : 发送方不需要等待

信号

信号Signal

软件中断通知事件处理
Examples: SIGFPE, SIGKILL, SIGUSRI, SIGSTOP, SIGCONT

接收到信号时会发生什么?

catch: 指定信号处理函数被调用
ignore: 依靠操作系统的默认操作(abort, memory dump, suspend or resume process)
mask: 闭塞信号因此不会传送(可能是暂时的,当处理同样类型的信号)

不足:

不能传输要交换的任何数据

管道

数据交换

子进程从父进程继承文件描述符(0 stdin, 1 stdout, 2 stderr)

进程不知道(或不关心)从键盘,文件,程序读取或写入到终端,文件,程序.

例如: $ ls | more (两个进程, 管道是缓存,对于ls来说是stdout,对于more来说是stdin )

消息队列

消息队列按FIFO来管理消息

message: 作为一个字节序列存储
message queues: 消息数组
FIFO & FILO configuration

共享内存

进程

每个进程都有私有地址空间
在每个地址空间内,明确地设置了共享内存段

优点

快速,方便地共享数据

不足

必须同步数据访问

最快的方法

一个进程写另一个进程立即可见

没有系统调用干预

没有数据复制

不提供同步

Socket

第十二章

第十二章的主要内容是：文件管理

基本概念

文件系统和文件

文件系统: 一种用于持久性存储的系统抽象

在存储上: 组织,控制,导航,访问和检索数据
在大多数计算机系统包含文件系统
个人电脑,服务器,笔记本电脑
ipod,tivo,机顶盒,手机,电脑
google可能也是由一个文件系统构成的

文件: 文件系统中的一个单元的相关数据在操作系统中的抽象

文件系统的功能:

分配文件磁盘空间
- 管理文件块(哪一块属于哪一个文件)
- 管理空闲空间(哪一块是空闲的)
- 分配算法(策略)
管理文件集合
- 定位文件及其内容
- 命名: 通过名字找到文件的接口
- 最常见: 分层文件系统
- 文件系统类型(组织文件的不同方式)
提供的便利及特征
- 保护: 分层来保护数据安全
- 可靠性,持久性: 保持文件的持久即使发生崩溃,媒体错误,攻击等

文件和块:

文件属性: 名称,类型,位置,大小,保护,创建者,创建时间,最久修改时间...

文件头: 在存储元数据中保存了每个文件的信息,保存文件的属性,跟踪哪一块存储块属于逻辑上文件结构的哪个偏移

文件描述符

文件使用模式:

使用程序必须在使用前先"打开"文件

f = open(name, flag);
...
... = read(f, ...);
...
close(f);

内核跟踪每个进程打开的文件:

操作系统为每个进程维护一个打开文件表
一个打开文件描述符是这个表中的索引

需要元数据来管理打开文件:

文件指针: 指向最近的一次读写位置,每个打开了这个文件的进程都这个指针

文件打开计数: 记录文件打开的次数 - 当最后一个进程关闭了文件时,允许将其从打开文件表中移除

文件磁盘位置: 缓存数据访问信息

访问权限: 每个程序访问模式信息

用户视图: 持久的数据结构

系统访问接口:

字节的集合(UNIX)

系统不会关心你想存储在磁盘上的任何的数据结构

操作系统内部视角:

块的集合(块是逻辑转换单元,而扇区是物理转换单元)

块大小<> 扇区大小: 在UNIX中, 块的大小是 4KB

当用户说: 给我2-12字节空间时会发生什么?

获取字节所在的快

返回快内对应部分

如果要写2-12字节?

获取块

修改块内对应部分

写回块

在文件系统中的所有操作都是在整个块空间上进行的: getc() putc() 即使每次只访问1字节的数据,也会缓存目标数据4096字节(一个磁盘块)

用户怎么访问文件: 在系统层面需要知道用户的访问模式

顺序访问: 按字节依次读取(几乎所有的访问都是这种方式)

随机访问: 从中间读写(不常用,但是仍然重要,如: 虚拟内存支持文件,内存页存储在文件中;更加快速,不希望获取文件中间的内容的时候也必须先获取块内所有字节)

内容访问: 通过特征

文件内部结构:

无结构: 单词,比特的队列

简单记录结构: 列,固定长度,可变长度

复杂结构: 格式化的文档(word, PDF), 可执行文件, ...

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

访问控制:

谁能够获得哪些文件的哪些访问权限

访问模式: 读,写,执行,删除,列举等

文件访问控制列表(ACL):

<文件实体, 权限>

UNIX模式:

<用户|组|所有人,读|写|可执行>

用户ID识别用户,表明每个用户所允许的权限及保护模式

组ID允许用户组成组,并指定了组访问权限

指定多用户,客户如何同时访问共享文件:

和过程同步算法相似

因磁盘IO和网络延迟而设计简单

UNIX文件系统(UFS)语义:

对打开文件的写入内容立即对其他打开同一文件的其他用户可见

共享文件指针允许多用户同时读取和写入文件

会话语义:

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

锁:

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

文件别名

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

硬链接: 多个文件项指向一个文件

软链接: 以快捷方式指向其他文件

通过存储真实文件的逻辑名称来实现

如果删除一个有别名的文件会如何呢? : 这个别名将成为一个悬空指针

Backpointers 方案:

每个文件有一个包含多个backpointers的列表,所以删除所有的Backpointers

backpointers使用菊花链管理

添加一个间接层: 目录项数据结构

链接: 已存在文件的另外一个名字(指针)

链接处理: 跟随指针来定位文件

我们如何保证没有循环呢?

只允许到文件的链接, 不允许在子目录的链接

每增加一个新的链接都用循环检测算法确定是否合理

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

文件系统种类

磁盘文件系统: 文件存储在数据存储设备上,如磁盘; 例如: FAT,NTFS,ext2,3,ISO9660等

数据库文件系统: 文件根据其特征是可被寻址的; 例如: WinFS

日志文件系统: 记录文件系统的修改,事件; 例如: journaling file system

网络,分布式文件系统: 例如: NFS,SMB,AFS,GFS

特殊,虚拟文件系统

虚拟文件系统

分层结构:

顶层: 文件,文件系统API

上层: 虚拟(逻辑)文件系统 (将所有设备IO,网络IO全抽象成为文件,使得接口一致)

底层: 特定文件系统模块

目的: 对所有不同文件系统的抽象

功能:

提供相同的文件和文件系统接口

管理所有文件和文件系统关联的数据结构

高效查询例程,遍历文件系统

与特定文件系统模块的交互

数据结构:

卷[第四声]控制块(UNIX: "superblock")

每个文件系统一个

文件系统详细信息

块,块大小,空余块,计数,指针等

文件控制块(UNIX: "vnode" or "inode")

每个文件一个

文件详细信息

许可,拥有者,大小,数据库位置等

目录节点(Linux: "dentry")

将目录项数据结构及树形布局编码成树形数据结构

指向文件控制块,父节点,项目列表等

其中: 卷控制块(每个文件系统一个),文件控制块(每个文件一个),目录节点(每个目录项一个)

持续存储在二级存储中: 在分配在存储设备中的数据块中

当需要时加载进内存:

卷控制块: 当文件系统挂载时进入内存

文件控制块: 当文件被访问时进入内存

目录节点: 在遍历一个文件路径时进入内存

数据块缓存

数据块按需读入内存:

提供 read() 操作

预读: 预先读取后面的数据块

数据块使用后被缓存:

假设数据将会再次被使用

写操作可能被缓存和延迟写入

两种数据块缓存方式:

普通缓冲区缓存

页缓存: 同一缓存数据块和内存页

分页要求: 当需要一个页时才将其载入内存

支持存储: 一个页(在虚拟地址空间中)可以被映射到一个本地文件中(在二级存储中)

打开文件的数据结构

打开文件描述:

每个被打开的文件一个

文件状态信息

目录项,当前文件指针,文件操作设置等

打开文件表:

一个进程一个

一个系统级的

每个卷控制块也会保存一个列表

所以如果有文件被打开将不能被卸载

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

调节对文件的访问

强制和劝告:

强制 - 根据锁保持情况和需求拒绝访问

劝告 - 进程可以查找锁的状态来决定怎么做

文件分配

大多数文件都很小:

需要对小文件提供强力的支持

块空间不能太小

一些文件非常大:

必须支持大文件(64-bit 文件偏移)

大文件访问需要相当高效

如何为一个文件分配数据块

分配方式:

连续分配

链式分配

索引分配

指标:

高效: 如存储利用(外部碎片)

表现: 如访问速度

连续分配:

文件头指定起始块和长度

位置,分配策略: 最先匹配,最佳匹配,...

优势: 文件读取表现好;高效的顺序和随机访问

劣势: 碎片;文件增长问题

链式分配:

文件以数据块链表方式存储

文件头包含了到第一块和最后一块的指针

优势: 创建,增大,缩小很容易;没有碎片

劣势: 不可能进行真正的随机访问;可靠性

索引分配:

为每个文件创建一个名为索引数据块的非数据数据块(到文件数据块的指针列表)

文件头包含了索引数据块

优势: 创建,增大,缩小很容易;没有碎片;支持直接访问

劣势: 当文件很小时,存储索引的开销大;处理大文件难

空闲空间列表

跟踪在存储中的所有未分配的数据块

空闲空间列表存储在哪里?

空闲空间列表的最佳数据结构怎么样?

用位图代表空闲数据块列表: 11111101101110111 如果 i = 0表明数据块i是空闲的,反之是分配的

使用简单但是可能会是一个big vector:

160GB disk → 40M blocks → 5MB worth of bits

然而,如果空闲空间在磁盘中均匀分布,那么再找到"0"之前需要扫描磁盘上数据块总数 / 空闲块的数目

需要保护:

指向空闲列表的指针

位图:

必须保存在磁盘上;在内存和磁盘拷贝可能有所不同;不允许block[i]在内存中的状态为bit[i]=1而在磁盘中bit[i]=0

解决:

在磁盘上设置bit[i] = 1; 分配block[i]; 在内存中设置bit[i] = 1

多磁盘管理 - RAID

通常磁盘通过分区来最大限度减小寻道时间:

一个分区是一个柱面的集合

每个分区都是逻辑上独立的磁盘

分区: 硬件磁盘的一种适合操作系统指定格式的划分

卷: 一个拥有一个文件系统实例的可访问的存储空间(通常常驻在磁盘的单个分区上)

使用多个并行磁盘来增加: 吞吐量(通过并行),可靠性和可用性(通过冗余)

RAID - 冗余磁盘阵列: 各种磁盘管理技术;RAID levels: 不同RAID分类,如RAID-0,RAID-1,RAID-5

实现: 在操作系统内核: 存储,卷管理; RAID硬件控制器(IO)

RAID-0

数据块分成多个子块, 存储在独立的磁盘中: 和内存交叉相似

通过更大的有效块大小来提供更大的磁盘带宽

RAID-1

可靠性成倍增长

读取性能线性增加(向两个磁盘写入,从任何一个读取)

RAID-4

数据块级磁带配有专用奇偶校验磁盘: 允许从任意一个故障磁盘中恢复

条带化和奇偶校验按byte-by-byte或者bit-by-bit: RAID-0,4,5: block-wise ;RAID-3: bit-wise

RAID-5

每个条带快有一个奇偶校验块,允许有一个磁盘错误

RAID-6

两个冗余块,有一种特殊的编码方式,允许两个磁盘错误

磁盘调度

读取或写入时,磁头必须被定位在期望的磁道,并从所期望的扇区开始

寻道时间: 定位到期望的磁道所花费的时间

旋转延迟: 从扇区的开始处到到达目的处花费的时间

平均旋转延迟时间 = 磁盘旋转一周时间的一半

寻道时间是性能上区别的原因

对单个磁盘,会有一个IO请求数目

如果请求是随机的,那么会表现很差

FIFO:

按顺序处理请求

公平对待所有进程

在有很多进程的情况下,接近随机调度的性能

最短服务优先:

选择从磁臂当前位置需要移动最少的IO请求

总是选择最短寻道时间

skan:

磁臂在一个方向上移动,满足所有为完成的请求,直到磁臂到达该方向上最后的磁道

调换方向

c-skan:

限制了仅在一个方向上扫描

当最后一个磁道也被访问过了后,磁臂返回到磁盘的另外一端再次进行扫描

c-loop(c-skan改进):

磁臂先到达该方向上最后一个请求处,然后立即反转

Files

Deep_into_OperatingSystem.md

Latest commit

History

Deep_into_OperatingSystem.md

File metadata and controls

第一章

操作系统是什么？

操作系统层次

操作系统的界面和内核

操作系统内部组件

操作系统特征

第二章

探究计算机启动过程

中断、异常、系统调用

中断

异常

系统调用

区别

为什么应用程序不能直接访问硬件？

第三章

计算机体系结构

内存分层体系

内存分层体系

内存管理目标

内存管理方法

地址空间

连续内存分配

内存碎片问题

分区的动态分配

碎片整理方法

第四章

非连续内存分配的必要性

连续内存分配的缺点

非连续内存分配的优点

非连续内存分配的缺点

非连续内存分配

分段(Segmentation)

分页(Paging)

分页地址空间

页寻址方案

页表(Page Table)

页表概述

分页机制的性能问题

转换后备缓冲区(TLB)

二级/多级页表

反向页表

基于页寄存器(Page Registers)的方案

基于关联内存(associative memory)的方案

基于哈希(hash)的方案

第五章

虚拟内存的起因

覆盖技术

交换技术

覆盖技术和交换技术的对比

虚拟内存管理技术

第六章

功能与目标

实验设置与评价方法

局部页面置换算法

最优页面置换算法

先进先出算法

最近最久未使用算法

时钟页面置换算法

二次机会算法

最不常用算法

Belady现象(科学家名字)

LRU / FIFO 和 Clock 的比较

全局页面置换算法

工作集模型

工作集

常驻集

工作集页置换算法

缺页率置换算法

抖动问题

第七章

进程(process)描述

进程定义

进程的组成

进程的特点