操作系统1

CPU上电过程

1.BIOS-MBR-DBR

读取BIOS(存储在内存-ROM中)
大小1MB，有两个重要寄存器CS:IP，即代码段寄存器:指令指针寄存器
系统处于实模式，只提供几个最基本的中断调用以实现IO功能（只能在实模式下调用）
加电稳定后从FFFF:0000开始读取第一条JMP指令，跳转到自检指令段
- POST(硬件自检)：内存显卡等
- 设备初始化：查找对应的接口卡并执行相应的BIOS
- 系统检测：执行系统BIOS
根据启动顺序跳转到下一阶段设备的启动程序，即跳转到对应的第一个扇区MBR
MBR(主引导记录)
设备的第一个扇区，有512KB
启动代码：检查分区表正确性、跳转到设备的引导扇区DBR
硬盘分区表DPT：硬盘分区有很多好处。考虑到每个区可以安装不同的操作系统，MBR因此必须知道将设备控制权转交给哪个区。
结束标志：若为0x55或0xAA，则该设备可以用于启动；反之则不行
DBR(分区引导记录)：
- JMP指令：跳转到启动代码段
- 文件卷头
- 启动代码：跳转到加载程序
- 结束标志

2.VBR-Bootloader-OS

硬盘启动
卷引导记录VBR：哪里装着操作系统
扩展分区和逻辑分区：四个分区再分，成为逻辑分区
启动管理器Boot loader
- 文件系统中读取加载程序
- 选择操作系统内核、填入动态加载参数
- 跳到对应内核代码段
加载操作系统

中断、异常与系统调用

区别：外部中断、内部异常；中断为异步、异常为同步；非CPU指令执行后产生的叫中断，CPU指令执行后产生的叫异常
中断处理：
硬件：设置中断标志，按中断向量表跳转到对应中断指令段的入口（进入软件阶段）
软件：保存现场、执行中断指令、清除中断标志、现场恢复
软件处理可能会被硬件中断打断（比如缺页中断）、被其他软件处理嵌套
系统调用处理（利用中断的机制）
目的：隔离用户态与内核态
处理器的特权级存放在PSW中，详细状态内容存在CR3寄存器
程序状态字PSW：指示处理器状态（包括状态标志、控制状态），便于保存现场
RISCV中的PSW实际上被分散在了各个CSR中
区分缺页中断与缺页异常
中断：OS请求分页的过程中缺页触发缺页中断，因为请求分页属于OS操作（非CPU指令）
异常：访存时缺页触发缺页异常，因为访存指令属于CPU指令

内存管理

内存管理技术：

连续内存管理：分区
非连续内存管理：分段（segmentation）、分页（paging）、虚拟存储（virtual memory）

逻辑地址与物理地址的转换：

编程或编译时确定
静态重定位确定
动态重定位确定

1.连续物理内存-分区

物理地址 = 逻辑地址 + 基址

动态分配
最先分配FFA：直接选用第一个够用的分区。
最优分配BFA：空闲分区列表从小到大排序，搜索一个比它大但最小的分区，分区利用率最高。
最差分配BFA：与最优策略对应，空闲分区由大到小排。
它们各有优势，需注意它们之间的优点、缺点、产生碎片的区别
伙伴系统分配
采用二分的思路进行占用率相对较高的分配
合并时注意，两段内存可以合并的条件是，它们两个对应的节点在二叉树中的父节点相同。
碎片整理
紧凑策略：通过移动分配给进程的内存分区，以合并外部碎片
分区对换：通过抢占并回收出于等待状态进程的分区，从而增大可用内存空间。
- 类似windows的虚拟内存机制，相等于将一部分外存用作内存，.swp文件就来源于分区对换（swapping）
- 也是早期多进程实现方式

2.非连续物理内存-分段

基本单元：
按逻辑分段：主代码段，子模块代码段、公用库代码段、stack、heap、初始化数据段、符号表等
目的：段式存储在做==内存保护==方面有优势。在逻辑上拆分存储内容，如果访问内容所属类别与存储内容不一致，则可以判定为“段错误”。同时，段式存储还可以实现==段中模块的共享==，即不同进程使用物理内存中的同一个段。
逻辑地址与物理地址的转换：

MMU：内存管理单元
实现逻辑地址到物理地址的映射，还可以判断是否发生段页访问的错误。
TLB：一个高速缓存，用于缓存页表转换的结果（快表），从而缩短页表查询的时间。
TWU：一个页表遍历模块，页表是由操作系统维护在物理内存中，但是页表的遍历查询是由TWU完成的，这样减少对CPU资源的消耗。
段中各模块的共享（覆盖策略）
必要模块：常驻
可选模块：用到时装入
不会同时使用的模块：相互覆盖，共用存储

3.非连续物理内存-分页

基本单元：
物理地址空间中的单元叫做物理页面，一般地，称为页帧（page frame），简称帧（frame）。
逻辑地址空间中的单元称为逻辑页面，一般地，称为页面，简称页（page）。
帧和页的大小必须相同。
物理地址的二元组形式：
有时物理地址不是写成二进制，而是写为一个二元组(f,o)。f为帧号（占s位），o为偏移。
则二元组(f,o)的对应地址为$$ = f<<2^{s}+o = f\cdot2^{s}+o$$
逻辑地址与物理地址的转换：
设置一个页表寄存器PTR，保存内存中单一页表基址和页表长度

页表
每个进程都有一个页表，每一个页面都有一个页表项。
页表是按照逻辑页号的顺序排列的，所以页号并不需要存入页表项。
页表项中只储存物理帧号以及一些标志位。
页表中的内容随着进程的运行状态而动态变化。为了表征这些变化所以引入标志位，比如存在位、修改位、引用位等（这些后续会讲到）。
页表访问优化技术
减少相同的多次访问请求：使用TLB（快表）
页表可能非常大：间接访问（多级页表）
- CR3与PDBR寄存器：
- CR3寄存器：存储当前处理器的特权级
- PTBR寄存器：上文PTR的升级版，可以存储==不同特权级下不同页表==的==基址==，便于特定特权级下的页表查询
使用内存空间来减小页表大小：反置页表（但是会增加搜索时间————Hash冲突）
- 普通映射方式是：逻辑地址--(页号)-> 页表--(帧号)->物理地址，为了实现正向映射，页表的主键是页号。但由于每个进程的页号都是分开的，所以每个进程就要设置一个页表
- 而物理地址是共用的，如果==使用帧号来作为页表的主键==，那么所有进程就可以同时使用一个页表，称为==反置页表IPT==，这个时候就无法使用正向映射了。
- 同时，为了使所有进程都能使用一个页表，页表项必须加入==进程的PID==作为标识
- 为了实现映射，可以建立一个hash表减少搜索时间，key=PID与页号进行HASH，value=PID进程下页号对应的页表项。
- IPT与PT的差别：
  - PT = 按页号索引的页表。映射时使用页号根据PT索引，在页表中查找，查找到页表项后得到帧号。
  - IPT = 按帧号索引的页表。映射时用HASH在Hash表中查找，查找到对应页表项后，根据IPT索引得到帧号。

4.非连续物理内存-段页式

对每一个段进行分页
不同进程的共享段就可以共用一个页表了

总结

1.分页

页表存在内存中
页表可以是只读的
页表可以有特权级
页表项标志位：驻留位（是否在内存中）、修改位（脏位）、访问位（最近被访问过）、保护位（只读/可读写/可执行等）、锁定标志位（表明为关键页，防止被换出）

2.分段

段的大小可以不一致
不同进程的段可以有重叠
因为有共享段的存在，使得两个进程可以使用同一个段
即，同一个物理内存区域可以同时映射到多个进程的内存地址空间
段可以有特权级
段与段之间可以是不连续的

虚拟存储

已有的解决内存不够的方法：

段式存储中的覆盖策略
分区存储中的交换策略

1. 局部性原理

时间局部性：某条指令的执行，某个数据的访问集中在较短时期内
空间局部性：当前执行的几条指令、当前访问的一些数据集中在较小区域内
分支局部性：一条跳转指令的两次执行，很可能跳转到相同的内存位置

也就是说，除了这些局部区域的数据必须被内存存储以外，其他数据都可以先调出到外存，需要使用时再从外存调入。

2. 虚拟存储

虚存就是将外存作为虚拟的内存使用，实现时将不常用的部分内存块暂存到外存。需要使用时OS发送缺页/缺段中断
实现方式：虚拟页式存储、虚拟段式存储
表现：页数>=帧数（或块数），多余的页其实都存在虚存（即外存）中

虚拟页式存储

在之前的页式存储（非连续）的基础上，增加请求调页和页面置换的机制。

思路：

只装必要的部分即可运行
需要的代码或数据不在内存，发送缺页中断
中断程序从外存调入必要页面

缺页中断的发出：

缺页中断的处理：

在页面换入过程中，不一定有直接的空闲页面，所以我们要使用==页面置换算法==挑选其他可以调入的空闲页面。
在物理内存没有空闲以换入时，4将遵循如下的步骤：
依据==页面置换算法==（见下文），选择将被替换的物理帧f，对应逻辑页q（这里存在：物理帧->逻辑页的反向查找）
如果q的修改位为1，则要写回外存
修改q的驻留位为0
将页p装入页面f

虚拟页式存储管理的性能可以用有效存储访问时间EAT来评定：

为了使引入虚拟页式存储的时间尽可能小，必须要保证缺页率p相当低。

页面置换算法

在给出页面置换的结构之前，我们有一类特例，即不被换出的页面：页面锁定（frame locking）

操作系统的关键部分，描述必须常驻的逻辑页面，这部分页面对响应速度有要求
利用==页表中的锁定标志位==来实现

评价方法：页面轨迹统计，模拟页面置换行为，记录缺页次数

页面置换算法分类：

局部页面置换算法（选择范围仅限当前进程占用的物理页面）
最优算法：全知全能，量身定制，但不可能被实现
先进先出算法：先调入的页先调出
最近最久未使用算法：一个统计方法，实现较麻烦
时钟算法，最不常用算法
全局置换算法（选择范围是所有可换出的物理页面）
工作集算法
缺页率算法

局部页面替换算法

1.最优页面置换算法OPT

置换在未来的最长时间不访问的页面。需要预测未来的使用频率，无法被实现

2.先进先出算法FIFO（节点：进入内存）

选择在内存中驻留时间最长的页面进行换出。==实现：维护一个队列即可。==效果不太好，一般不用
Belady现象：进程分配页帧数增加时，缺页并不一定减少。
FIFO算法的置换特征与局部性原理不相符。
与进程访问的动态特征相矛盾，被它置换出去的页面并不一定是进程近期不会访问的。

3.最近最久未使用算法LRU（节点：被使用）

局部性原理表明，如某些页面长时间未被访问，则它们在将来可能会长时间不会访问。
选择最长时间没有被引用的页面进行置换。==实现：维护一个优先队列（最大堆/链表结构）。缺页时，计算内存中每个逻辑页面的上一次访问时间，时间越久，换出优先级越高。==时间复杂度太大，一般不用

4.时钟算法（Clock）

LRU的近似，FIFO的改进
思路：
页初始装入时，访问位置0；被访问时，访问位置1。
将一个进程在内存中的所有页面，连成一个钟表面，指针指向最老的页面（最先被装入）。
当发生一个缺页中断时，考察指针页面，若驻留位为1（页面在内存中）且访问位为0（视为最久未被访问的页面），立即换出该页面，同时指针后移；反之，访问位置为0（因为没有访问该页面），同时指针后移继续考察，直到换出一个页面。
注：每次移动指针时都要根据是否换出页面，来更新指向该页面的访问位

5.改进的Clock算法（二次机会法）

加入修改位（脏位）来帮助置换
可以区分页被读还是被写
被读：访问位为1，修改位为0；被写：访问位为1，修改位为1
改进原因
如果这个页在内存中==仅发生过读操作==，那么该页在内存中的数据==在外存中的数据，换出时可以直接扔掉，效率很高。
如果这个页在内存中发生过写操作，那么该页在内存中的数据=/=在外存中的数据，换出时还需要复制到外存，效率低。
二次机会法
clock算法中需要尽量避免换出：进行过写操作的页面
当指针指向一个进行过写操作的页面（访问位0修改位1）时，需要避免换出，指针后移，同时修改位置0（下一次还要换它的话就不阻止了，即给它第二次机会）。

6.最不常用算法LFU

LRU的改进（不维护优先队列，只维护链表上的几个计数器）
每个页面增加访问计数，访问页面时，计数+1；缺页时换出计数最小的页面。
LFU和LRU的区别：
LRU：时间越久优先级越高
LFU：频率越少优先级越高

全局页面替换算法

工作集模型

可以定量分析局部性原理的模型
工作集：一个进程当前正在使用的页面集合。以$$W(t,\Delta t)$$表示。t表示当前时刻；$$\Delta t$$表示工作集窗口，即访问一个定长页面所需的时间长度；$$W(t,\Delta t)$$表示t时刻之前的$$\Delta t$$时间段中，包含的所有页面组成的集合。（设$$\Delta t$$固定，则t变化，W也会跟着变化）注意，集合包含t时间点本身
工作集的模：对应的页面数目
驻留集：当前时刻，进程实际驻留在内存中的页面集合。
工作集与驻留集的区别：工作集是实际需要访问的页面，可能在内存中也可能不在；而驻留集一定在内存中。驻留集属于工作集。

1.工作集页面替换算法（主动换出）

主动换出：不需要等到缺页时再换出，而是==每次访存时==都要换出不在工作集的页面。
实现：每次访问就往工作集中加一个页面（不去重），滑动窗口前移，并将离开窗口的页面主动换出。
换入不能主动换入，只能发生缺页时再换，因为我们不能预知谁会被访问到。
类似于维护一个头为$$t-\Delta t$$、长度为$$\Delta t$$、尾为$$t$$的==大小固定==的滑动窗口。

2.缺页率页面替换算法PFF

工作集页面替换算法的改进，需要维护一个==长度不固定==的滑动窗口，长度变化的依据是缺页率。
缺页率PFR计算：$$PFR = 缺页次数/内存访问次数$$ 或者 $$PFF = 1/MTBR$$
MTBR：平均缺页时间间隔
若缺页率高时则说明工作集太小，需要增加工作集；反之则减小工作集。
- 工作集太大的缺点：会降低并发度，使CPU利用率下降

实现：初始给一个工作集大小$$\Delta t0$$。每当缺页发生时，记录当前时间T1，并计算==上次缺页时间T0到当前T1的缺页时间间隔$$\Delta t1$$==。
若缺页时间间隔大于$$\Delta t0$$，说明缺页率较低，需要减小工作集，将$$\Delta t1$$间隔外的页面移除。
反之，说明缺页率较高，需要增加工作集，仅移入页面。
效果：将缺页时间间隔稳定在$$\Delta t0$$左右。

抖动问题（Thrashing）

量化参数
MTBF：平均页缺失时间
PFST：页缺失服务时间

Thrashing

最佳的点处于$$N_{I/O-Balance}$$点，即MTBF=PFST的时候，对应的CPU利用率也很高。
PFF算法可以做到这一点。