操作系统（一）

引言

提前批面试被怼飞了，去实习前先给自己充充电，充实一下。从零开始学操作系统，有什么错误希望大家直接指出~
文章很长，慎入⊙﹏⊙，可以收藏了慢慢看~

文章导读

• 操作系统的启动
• 操作系统与设备和程序交互（中断，IO，系统调用，异常）
• 内存管理
• 连续内存分配（首次适配，最佳适配，最差适配）
• 非连续内存分配（分段，分页）
• 虚拟内存技术
• 页面置换算法（OPT，FIFO，LRU，Clock，LFU，工作集页置换算法，缺页率置换算法）

一、操作系统的启动

计算机刚打开时，执行了什么指令？
会走pc=？，具体地址是由硬件设计者决定。

首先简单来了解一下操作系统启动的过程，以x86 PC为例：
1. x86 PC刚开机时，CPU处于实模式。
注：这种模式下能够直接访问硬件，没有硬件等级和保护。
2. 开机时，CS=0xFFFF，IP=0x0000
注：CS是段寄存器，IP是偏移。
3. 寻址0xFFFF0（ROM BIOS映射区），进入BIOS模式。
注：寻址=CS<<4+IP
4. 检查RAM，键盘，显示器，软硬件磁盘
5. 将磁盘0磁道0扇区读入0x7c00处（一个扇区的大小是512字节）。
注：0磁道0扇区就是操作系统的引导扇区。
6. 设置cs=0x07c0，ip=0x0000
注：引导扇区加载完后，加载setup扇区......

简单来说，就是：
1. BIOS加电自检，寻找显卡和执行BIOS。
2. 将bootloader加载到内存中。
3. bootloader找到硬盘的起始扇区，将操作系统代码和数据从硬盘读取到内存中。

二、操作系统与设备和程序交互

首先得清楚与设备和程序交互的方式有哪些：

• 面向外设：中断，IO
• 面向应用程序：系统调用，异常

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

为什么不让应用程序直接访问外设？
1. 在计算机运行中，内核是被信任的第三方
2. 只有内核可以执行特权指令
3. 封装成接口，为了方便应用程序调用

2.1 中断的过程

硬件层面：设置中断标记。
1. 将内部、外部事件设置中断标记。
2. 产生中断事件的ID。
CPU根据中断标记产生中断号（中断事件ID），发送给操作系统。

软件层面
1. 保存当前处理状态。
2. 中断服务程序处理。
3. 清除中断标记。
4. 恢复之前保存的处理。

2.2 异常的过程

1. 产生异常编号。
2. 异常处理。
杀死产生异常的程序或重新执行异常指令。
3. 恢复现场。

2.3 系统调用的过程

1. 系统调用接口根据序号来维护表的索引。
2. 系统调用接口调用内核态中预期的系统调用，并返回系统调用的状态和其他任何返回值。
3. 用户不需要知道系统调用是怎么实现的，只要获取API，了解返回结果。大部分细节都隐藏在API中。

操作系统如何实现系统调用？
应用程序通过Library Code访问系统调用的接口；
触发用户态->内核态的转换，控制权从应用程序到操作系统；
sys_ 系统调用。

2.4 相关的开销

• 建立中断，异常，系统调用号与对应服务进程映射关系的初始化开销。
• 建立内核堆栈。
• 验证参数。
• 内核态映射到用户态的地址空间，更新页面映射权限。
• 内核态独立地址空间。

三、内存管理

3.1 管理内存的方法

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

实现依赖于硬件
MMU（内存管理单元）：硬件组件负责处理CPU的内存访问请求。

3.2 地址空间&地址的生成

物理地址空间
硬件支持的地址空间（主存和磁盘）。

逻辑地址空间
一个运行的程序所拥有的内存范围。

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

1.ALU需要某个逻辑地址的内存的内容。
2.内存管理单元（MMU）寻找在逻辑地址和物理地址之间的映射；如果没有就从内存中找。
3.控制器从总线发送在物理的内存内容的请求。
4.内存发送物理地址内存给CPU 。

具体步骤2是怎么建立逻辑地址和物理地址的映射，是如何查找的就是靠操作系统完成的。

四、连续内存分配

内存分配分为连续内存分配和非连续内存分配。首先看下连续内存分配，在内存分配的过程中会产生一些内存碎片，先了解一下内存碎片的概念。

• 外部碎片：在分配单元间的未使用内存。
• 内部碎片：在分配单元中的未使用内存。

连续内存分配算法有首次适配，最佳适配，最差适配。

首次适配思路
1.按地址排序的空闲块列表。
2.分配需要找到一个合适的分区。
3.重分配时需要检查，看是否自由分区能合并于相邻的空闲分区。

优点：简单；易于产生更大空闲块。
缺点：外部碎片；不确定性。

最佳适配思路
为了分配n字节，使用最小的比n大的可用空闲块。
1.按尺寸排列的空闲块列表。
2.分配需要寻找一个适合的分区。
3.重分配需要搜索及合并于相邻的空闲分区。

优点：当大部分分配是小尺寸时非常有效；比较简单。
缺点：外部碎片；重分配慢；易产生很多没用的微小碎片。

最差适配
和最佳适配思路相反。为了分配n字节，使用最大可用空闲块，尽可能保证空闲块是最大的。1.按查村排列的空闲块列表。
2.分配很快。
3.重分配需要合并于相邻的空闲分区，调整空闲块列表。

优点：每次分配是中等尺寸效果最好。
缺点：重分配慢；外部碎片；易于破碎大的空闲块以至大分区无法被分配。

可以看出，在连续的分配算法下难免会产生一下碎片，只要这些进程存在，这些碎片真的就无法利用吗？针对于这个问题，有两种解决内存碎片的思路：

• 压缩式碎片整理
  将等待中的程序进行内存的挪动，减少外部碎片的出现。
• 交互式碎片整理
  当运行程序需要更多的内存时，可以回收等待的程序的内存，将其挪到磁盘中（虚拟内存）。

注：上述所说的内存都是物理内存。

五、 非连续内存分配

对于内存的连续分配，总是会有碎片的产生，内存利用率低，而且执行碎片整理的方法也都是有开销的。因此，非连续内存分配就能很好的解决碎片问题，也是操作系统中用的最多的内存分配方法。

非连续内存分配基本算法有分段，分页。

虽然非连续分配的好处挺多，但在实现上也有一些问题，比如如何建立虚拟地址和物理地址之间的转换？

这就是后序要磕的分段和分页及映射表的设计。

5.1 分段

逻辑地址=s（段号），o（段内偏移）
段表=s（段号），限制（段长），基址

分段有两种实现方案：

• 段寄存器+地址寄存器实现方案。
• 单地址实现方案。

简单看一下段寄存器+地址寄存器是如何找到逻辑地址对应的物理地址的。

过程：
1.首先判断逻辑地址的段号s是否超过段表寄存器中的段表长度，如果超过则会产生越界异常。
2.如果不超过则去段表中找到对应的段号（段表始值+段号）。
3.判断偏移o是否超过段长，不超过则找到对应的基址+偏移得到物理地址。
4.这个物理地址就是要访问的主存地址了。

在分段管理的过程中，段长不是固定的。如果是单地址实现方案则更加简单，没有段表寄存器。直接拿逻辑地址中的段号去段表中查，其他步骤和上述一样。

5.2 分页

绝大部分CPU采用分页机制。首先需要划分物理内存至固定大小的帧，划分逻辑地址空间至相同大小的页，然后需要借助页表和MMU/TLB。
先看一下几个关键的概念~

物理地址的寻址方式:
物理地址是通过逻辑地址和页表换算出来的。
f（帧号，F位，共2^F个帧），o（帧内偏移，S位，每帧2^S字节）
物理地址= 

逻辑地址的寻址方式：
页内偏移的大小=帧内偏移的大小。
p（页号，P位，2^P个页），o（页内偏移，S位，每页有2^S字节）
逻辑地址= 

页表
每个运行的程序都有一个页表。属于程序运行状态，会动态变化。
PTBR是页表基址寄存器。
页表是页号和一些标志位及帧号的映射。

下面这个思路是最容易想到的，也是有点小bug的路子。

其实大体上和分段是一样的，区别在于页号上可能会有标志位，比如判断权限，是否在内存中。因为逻辑地址可能大于物理地址，这些标志位将在后序的虚拟页式内存管理中讲解。

如果按上述思路来实现，对于一个地址的转换，至少需要访问两次内存。一次是访问页表寻找帧号，一次是访问帧号对应的物理内存。如果计算机64位，一页为1024字节，就需要  字节大小的页表。而且一个进程建立一个页表，内存是一定不够用的。对于空间的代价也是很大的，但是最理想的状态是让空间代价，时间开销最小。

为了解决这个问题，操作系统可以利用CPU的cache对页表做一个缓存，但是cache非常小，所以可以存一些经常访问的页表映射。

页表的缓存
MMU（内存管理单元）中有一个TLB对于页表的缓存，一般存一页数据，是近期访问的页帧转换表项的缓存（这也是后序页面置换算法的参考点）。key->p；value->f。
注：p是页号，f是帧号，后序都用这两个字母表示。

如果TLB命中，物理页号可以很快被获取；如果TLB未命中，对应的表项被更新到TLB中。

多级页表
解决了时间的开销，再看看空间的代价。由于逻辑地址空间很大，所以需要很大的页表，为了使页表所占的空间变小，所以可以使用多级页表。

可以将页表中的页号细化，分为p1，p2。每级页表都存储下一级页表的索引，n级页表一次类推。下面是二级页表的寻址过程：

5.3 分页和分段的区别

（1）页是信息的物理单位，分页是为了减少内存碎片，提高内存利用率。分页仅仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它包含一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

（2）页的大小固定且由系统确定，逻辑地址的划分是由寄存器实现的，因而一个系统只能有一种大小的页面。段的长度不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

六、 虚拟内存

当前内存不够进程分配时，操作系统会怎么解决。此时，虚存技术就很关键，在虚存技术出来前，用得最多的是覆盖技术和交换技术。

覆盖技术
在较小的内存中运行较大的内存，将没有调用关系的程序放在一个分区。

B，D，E没有调用关系，也就是说，在调用B时，不可能同时调用D或E，所以共享一个覆盖区。早期用这个技术来节约内存。

缺点：有程序员来把一个大程序划分位若干个功能莫尽快，确定模块之间的覆盖关系，增加编程复杂度；覆盖模块从外存装入内存，是以时间换空间。

交换技术
将暂时不能运行的程序送到外存，从而获得空闲内存空间。粒度是一个程序，需要操作系统支持，对程序员透明。

缺点：以进程作为交换单位，需要把进程整个地址空间都换进换出，增加的处理器的开销。

覆盖与交换的比较

（1）覆盖只能发生在那些相互之间没有调用关系的程序模块之间。
（2）交换技术是在以内存中的程序大小为单位来进行的，一般一页以上。不需要程序员给出各个模块之间的逻辑覆盖结构。

覆盖和交换都有它的局限性，覆盖过于麻烦，而交换的粒度太大，以程序为单位。可以不可以把暂时不用的程序模块放到硬盘，把这一切都交给操作系统赋予特定的算法去完成呢？这就需要下面的虚存技术。

虚拟内存技术

把程序中的一部分放入到内存中，对程序员透明。可以根据内存的使用情况，动态的对程序部分内容在内存与外存中进行交换。

首先了解一下CPU的特性，程序的局部性原理：在程序执行过程中的一个较短时期，所有执行的指令地址和指令的操作地址分别局限于一定区域。

虚存技术的特征
1.大的用户空间，通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际内存空间，实现二者分离。
2.部分交换，调入调出都是对部分虚拟地址空间进行。
3.不连续性，物理内存分配的不连续，虚拟地址空间是哦那个的不连续

虚存技术的实现-虚拟页式内存管理

虚拟页式内存管理技术=页式内存管理+请求调页+页面置换功能。

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

页表=逻辑页号+访问位+修改位+保护位+驻留位+物理页帧号

下面挨个看看每个特征位：

驻留位
表示该页在内存还是外存。

保护位
允许对该页做何种类型的访问（只读，可读写，可执行等）。

修改位
表明此页是否被修改过。如果被修改过就会导致内存中和硬盘中的数据不一致，所以换入换出时需要保证数据的一致性。当系统回收物理页面时，根据此位来决定是否把它的内容写回外存。

访问位
该页面是否被访问过，用于页面置换算法。

有了这些，当页表中某个页号没有对应帧号时，会引发缺页中断，我们大概可以推测出缺页中断的流程：

图片来源于网络

1）如果在内存中有空闲的物理页面，则分配一物理页帧f，然后转4）；否则转2）。
2）采用某种页面置换算法，选择一个将被替换的物理页帧f，如果对应的逻辑页位q，若在该页在内存中修改过，则需将其写回外存。
3）对q所对应的页表向进行修改，驻留位=0。
4）将需要访问的页p转入到物理页面f中。
5）修改p所对应的页表项的内容，驻留位=1，把物理页帧置f。
6）重新运行被中断的指令。

那么，没有被映射的页是怎么被存储在硬盘的呢？
一般放在交换空间，以特殊的格式保存。
代码段->映射到可执行的二进制文件。
动态加载的共享库程序段->映射到动态调用的库文件。
其他段->可能被映射到交换文件。

还有一个问题，如果频繁发生缺页异常，进行页面置换，就会增加操作系统的开销。这里需要引入一个指标来描述虚存技术的性能-EAT（Effective Memory Access Time）。

EAT（使用有效存储器访问时间）=访存时间*页表命中率+缺页中断处理时间*缺页概率

从公式可以看出，缺页率越大，EAT越小，性能越差。基于程序的局部性特点，其实缺页率还是比较小的，这个其实跟程序代码的书写也有关系......

七、页面置换算法

采用什么样的置换算法对于缺页率的控制还是很关键的~

置换算法分为局部和全局页面置换算法。

局部页面置换算法：

• 最优页面置换算法（OPT）
• 先进先出算法（FIFO）
• 最近最久未使用（LRU）
• 时钟页面置换算法（Clock）
• 最不常用算法（LFU）

全局页面置换算法：

• 工作集页置换算法
• 缺页率置换算法

7.1 局部页面置换算法

最优页面置换算法（OPT）

思路：把将来最长时间不需要的页面置换。
该算法无法实现，但是会利用该算法作为参考，评价其他算法。

如上图所示，当时间=4时，需要置换一页，此时看a，b，c，d在将来什么时候会被访问。a=6，b=5，c=7，d=8，因此置换d。

先进先出算法（FIFO）

思路：将内存中驻留时间最长的页面置换。其实就是维护一个队列，每次置换队头那页。
性能较差，调初的页面可能是经常要访问的页面，并且有Belady现象（类似于逆向优化的现，增加内存的大小，很难降低缺页率）。FIFO很少单独使。

Belady的产生原因

算法置换特征与程序访问内存的动态特征是矛盾的，所以置换出去的页面不一定是进程会访问的。

最近最久未使用（LRU）

思路：选择最久未使用的那个页面置换。是对最优页面置换算法的近似，根据过去推测未来。

操作系统具体可以用以下方法实现：

• 维护一个链表，刚使用的放表头，最久未使用的作为尾节点。每次访问内存时，找到相应的页面，把它移到表头。发生缺页中断后，淘汰链表末尾的页面。
• 设置一个活动栈，访问页面时，将次页号压入栈顶，将栈内相同的页号都删掉。每次总是置换栈底元素。

虽然这样会让缺页的次数比较少，但实现效率不高。

时钟置换算法（Clock）

利用页表中的访问位（Access Bit），初始化为0，每次访问后都会置为1，操作系统又定期将其变为0。

思路：当发生缺页中断时，若当前访问位==1则置0，指针向下走，直到遇到访问位==0的页面就进行置换；若当前访问位==0则置换该页，然后指针指向下一个地址。在这个过程中，指针类似于时钟往一个方向走。
下图就是对于时钟置换完整的复现过程。

一开始，a，b，c，d在内存中，访问位初始化为0。每次访问，更新访问位，直到时间=5，第一次引发缺页中断，将当前访问位置0并向下走，遍历完回来，发现页面a访问位==0则替换a。后面的情况以此类推~
只有在发生缺页中断时，指针才会向下走。

二次机会法

二次机会法是对时钟置换算法的改进。
在置换的过程中，每次置换都需要先将当前页写回到磁盘。如果在内存中只是读操作，是不是可以减少这个写回的代价呢？

利用Dirty Bit（修改位），表示该页在内存中是否被修改过来指导置换。当内存中某个页被修改后，dirty bit会被置1。

思路：每次指针经过时，会将访问位置0，如果访问位已经为0，则将Dirty Bit置0。如果dirty bit已经为0，则直接置换该页。尽可能的让脏页在一次时钟中保留，也就是尽可能置换只读的页。

最不常用法（LFU）

思路：当缺页中断发生时，将访问次数最少的那个页面置换。

缺点：一个页面在一开始频繁访问，后续就不访问了。会导致内存利用率不高。

LRU，FIFO，Clock总结

• LRU和FIFO本质上都是先进先出的思路，但LRU是针对页面最近访问时间来排序，每次对内存的访问都要排序而FIFO不需要。
• 当内存中所有的页面都没被访问过时，LRU就退化为FIFO。
• LRU算法性能好，但系统开销较大；FIFO系统开销小，但可能会发生Belady。而Clock算法就是他们的折衷，每次页面访问时不用调整页面在链表的顺序，而是用寄存器中原生的标记，等发生缺页中断时再维护链表。Clock性能和LRU差不多，但对于曾经访问过的页面不能记住他们准确的位置。

7.2 全局页面置换算法

局部页面置换算法的问题

操作系统给每个进程分配物理页帧时应该是有所顾虑的。物理页帧的大小会对最终的页面置换算法的缺页率有较大的影响。程序在运行的过程中，对内存的读取一定是动态的，对物理页帧的需求也是变化的，如果按固定的页帧来算，势必会影响程序的灵活性。如何按照程序的需求动态的分配物理页帧呢？下面需要先引入几个概念。

工作集模型

如果程序对内存的访问不满足局部性原理，则不管用什么置换算法，一定会导致缺页中断；如果局部性成立，对它进行定量的分析就可以用工作集模型。个人理解工作集模型就是根据窗口大小，确定工作集，描述内存访问规律的模型。

工作集

单位时间内，访问的所有页面的集合。体现程序执行过程中，对页面访问的属性。

常驻集

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

工作集页置换算法

思路：随着时间和程序的运行，将不在工作集的窗口范围内的页面丢弃。

缺页率页面置换算法

工作集的窗口是固定的，能不能让它灵活的变化呢？

思路：若缺页率过高，则增加工作集，来分配更多的物理页面；若缺页率过低，则减少工作集。

设置一个时间段，当前缺页时间-上次缺页时间>时间段，则认为缺页频率低，可以减少给当前进程分配的页帧，从工作集中移除未在这个区间内访问的页面；当前缺页时间-上次缺页时间<时间段，则认为缺页率高，增加缺失的页面。

7.3 总结

影响缺页率的因素

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

局部和全局置换算法比较

（1）使用场景：如果程序对内存的需求是有规律的，则全局页面置换算法更有优势。
（2）执行时机：全局页面置换算法根据工作集，中断间隔来动态调整页面并且只有的中断时才会置换；局部页面置换算法是在当前内存满了才会执行。

7.4 抖动问题

当进程造成很多缺页中断时，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变慢，这种状态就是抖动。

当驻留内存的进程数增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以OS要选一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡，提高CPU的利用率。

X轴表示当前有N个程序，Y轴表示CPU的利用率。

图片来源于网络

深色（紫色）的曲线说明当程序越来越多，对CPU的利用率先增大；超过峰值后，则会频繁出现抖动的现象，以至于利用率不高。 浅色（蓝色）曲线表示平均缺页时间/缺页服务时间比值随程序的增加而减少。这个比值越大则说明操作系统进行页面置换，换入换出的时间越少，程序运行的时间越多。当其约为1时，就是比较好的平衡点，并发量比较不错，CPU利用率也比较高。

参考文章：操作系统第六篇【存储器管理】

感谢支持，喜欢我的文章可以关注我的知乎专栏~