• 无结构文件

• 有结构文件

根据各条记录长度是否相等，可将记录划分为定长记录及可变长记录

比如专业大家都差不多，就是定长，但是换成特长，可能有的人很多，有的人没有，就是可变长

顺序文件

因此组合一下，顺序文件就有以下分类

链式存储，就像链表他是不能想要第几个节点就能马上得到的，必须从第一个开始遍历

顺序存储中可变长记录的话，没有特定的规律，不能通过简单地计算直接得到物理位置，因而也只能从第一个开始遍历

定长记录的话就类似于数组了，当然可以随机存取，特别地，如果使用串结构，则各记录不是按照关键字顺序排列的，就无法迅速查找到某关键字对应的记录；而如果是顺序结构，即根据关键字按顺序排列，就可以用折半查找(二分法)，就是从中间的那条记录与要查找的记录比较，再就根据升序或者降序向前或向后查找。

一般情况下顺序文件都是指顺序存储

但顺序文件的缺点是删除或增加一个记录很困难，但如果是串结构就相对简单了，因为他不是按关键字顺序的所以添加直接加在后面就行，删直接删就行不用考虑顺序问题

虽然定长记录查找起来更快一些，但现实使用更多的是可变长的，那该怎么办呢？

这就引出了索引文件(适用于对信息处理的及时性要求很高的场合)

• 索引表得连续的放在内存里，逻辑文件(不定长记录文件)可离散着放，这样的话索引表就相当与定长记录的顺序文件，就可以迅速找到第i个的地址，同时如果是按关键字排列，可以用折半查找的方法加快访问速度；

• 索引号可以替换成关键字，比如学号，姓名…

• 索引表的每个表项长度相同，联想前面的页表项

如果索引表的表项占得地方太大了，比如说文件的记录平均占8B，但每个索引表项却占32个字节，那索引表占的空间就比文件本身4倍，那这样内存的利用率就会大大降低

为了解决这个问题就引出了索引顺序文件

如上图所示，将文件分组，每一组对应索引顺序文件的一个索引表项，这样的话跟一对一相比，当然节省了很多空间，还有索引顺序文件的项不是按关键字排列，这样增加删除就更快了

那现在索引表确实是瘦了不少，那他是不是可以解决查找速度慢的问题呢

假如一个顺序文件有10000个记录，则按关键字检索，只能从头开始(不是定长)，则至少5000次

但如果用索引顺序表，假设将这10000条记录分成100组，则每组有100条记录，当要查找是肯定要先去索引顺序表找在哪个组，从头开始找，平均要50次，找到在哪一组之后，就要去对应的组找到具体的位置，一组有100条，那平均就要找50次；查找速度就是50+50=100次

由此看来，的确是减少了不少

但如果文件有10的6次方个记录，可分为1000组，每组1000个记录，这样平均要500+500=1000次才能找到，还是很大，那该怎么办呢

可以建立多级索引顺序表

就用上面的10的6次方的例子，这样就是拿出100组，每一项对应一组(100项)，再对应一组(100项)

这样访问次数就是50+50+50=150，相比于1000少了很多

文件：一组有意义的信息/数据集合

什么是死锁

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象

发生死锁后若无外力干涉，这些进程都将无法向前推进

死锁，饥饿，死循环区别

饥饿：由于长时间得不到想要的资源，导致各进程都堵塞

死循环：某进程执行过程中一直跳不出某个循环的现象，有的死循环是逻辑错误，有的是程序员故意的，比如前面生产者消费者问题中的死循环，就是为了阻止其他进程进来

死锁产生的必要条件

其中最后一段的意思就是，如果有同类可替代的资源，就算循环等待也可能不发生死锁，就像图中的老人也有一个筷子，他可以给哲学家3号用

什么时候会发生死锁

总之，对不可剥夺的资源的不合理分配，可能导致死锁

死锁的处理策略

静态策略：预防死锁

思想：破坏产生死锁的一个或几个必要条件

• 破坏互斥条件

把只能互斥访问的资源改为允许共享使用，就不会进入死锁状态

比如SPOOLing技术，就是把独占设备在逻辑上改造成共享设备

如图中，实际上只是把进程们传到输出进程，有一种逻辑上共享的感觉，最终打印机还是一个一个打印

缺点：并不是所有资源都可以改造成可共享使用的资源，且为了系统安全，很多地方还需要保护这种互斥性，因此，很多时候无法破坏互斥条件

• 破坏不可剥夺条件

• 破坏请求和保持条件

上图的意思是，如果源源不断的有A类进程和B类进程，那当一个A进程释放后就会马上把资源1分给下一个A进程，B进程同理，只有A,B都不用，C才能用，因此可能造成C进程饥饿

• 破坏循环等待条件

缺点2解释：因为只能先占小的再占大的，所以当我想先用7号，再用5号，就只能先占5号，让他空闲一段时间，7号才能继续，这样就会造成资源浪费

缺点3解释：比如有的机器要先5后7，有的机器要先7后5，你就要改，就很麻烦

动态策略：避免死锁

安全序列：指系统如果按这种序列分配资源，则每个自愿都能顺利完成，只要能找出一个安全序列，系统就是安全状态，当然，安全序列可能不止一个

若分配资源后，系统找不到一个安全序列，系统就进入了不安全状态，这就意味着之后可能所有进程都无法顺利进行下去，但如果有进程归还了一些资源，系统也有可能重新回到安全状态，不过在分配资源之前我们要考虑到最坏的情况

如果系统处于安全状态，就一定不会发生死锁，如果系统进入不安全状态，可能发生死锁(处于不安全状态不一定发生了死锁，发生死锁一定是在不安全状态)

因此在分配资源之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，这也就是银行家算法的核心

银行家算法

注意这里的”把该进程加入安全序列，并把该进程持有的资源全部回收”，比如说我还有可用资源(6,3,2)，那我把他分配给进程P0，进程P0满足他的最大需求就会把资源都释放出来，我的可用资源就是(6,3,2)+(2,2,1)=(8,5,3)

死锁的检测和解除

若系统中不采取预防死锁的措施，也不采取避免死锁的措施，那系统就很有可能出现死锁，在这种情况下系统应提供以下两个算法

死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁

死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来

• 死锁的检测

① 用某种数据结构来保存资源的请求和分配信息

②提供一种算法（依次消除与不阻塞进程相连的边，直到无边可消），利用上述信息来检测系统是否已进入死锁状态

• 进程的解除

为什么引入管程

在之前用信号量实现进程同步，互斥时，我们知道很容易因为异步性导致出现死锁，编程困难，易出错，能不能设计一种机制让程序员不需要再关注复杂的PV操作，让写代码更轻松呢，这个时候就在Pascal语言里首次引入了”管程”的成分，一种高级同步机制

管程的定义和基本特征

管程是一种特殊的软件模块，有下面这些部分组成

1.局部于管程的共享数据结构说明

2.对该数据结构进行操作的一组过程(相当于函数)

3.对局部于管程的共享数据设置初始值的语句

4.管程有一个名字

管程的基本特征：

1.局部于管程的数据只能被局限于管程的过程所访问

2.一个进程只有通过管程内的过程才能进入管程访问共享数据

3.每次允许一个进程子管程内执行某个内部过程

综上，我认为可以把管程理解为面向对象中的封装，比如说类

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

比如

驻留集

指请求分页存储管理中给进程分配的物理块的集合

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的大小

若驻留集太大，会导致多道程序并发度下降，资源利用率降低，所以应该选择一个合适的驻留集大小(极端一点，驻留集等于进程大小，进程能一次性放进去)

若驻留集太小，又会导致缺页频繁，系统要花大量时间来处理缺页，实际用于进程推进的时间很少(极端点，驻留集是1，进程是100)

页面分配，置换策略

有了上面的问题就引出了分配，置换策略

固定分配：操作系统为每个进程分一组固定数目的物理块，在进程运行期间不再改变，即驻留集大小不变

可变分配：先为每个进程分一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，即驻留集大小可变

局部置换：发生缺页时只能选进程自己的物理块进行置换

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可将别的进程持有的物理块置换到外存，再分配给缺页进程

两两组合就有了下面的结果

其中未锁定是一些不要紧的进程，因为操作系统会将一些程序设成锁定，不允许别人动

何时调入页面

从何处调入页面

抖动(颠簸)现象

刚刚换出的页面又要马上换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动或颠簸，产生抖动的主要原因是进程频繁访问页面数目高于可用物理块数(分配给进程的物理块不够)

为了解决物理块到底应该分多少的问题，有了工作集的概念

工作集

指在某段时间间隔，进程实际访问页面的集合

分页存储中的页表是单级页表，它有两个很严重的问题

1.页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框

2.没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面
第二个问题需要用到虚拟技术，以后再说

为了解决第一个问题也就有了两级页表，就是在页表的基础上为离散的页表再建个页表，称为页目录表

如上图所示就是把单级页表给离散开了，分成了1024个部分，至于为什么分为1024个部分，我们来慢慢推导，每个页面可以放2的10次方个页表项，那我总共有2的20次方个有页表项，那么就应该被分成1024个部分

那分出来的小页表的起始地址怎么求呢，这个时候就是我们的页目录表闪亮登场的时候了

页目录表第一列代表是小页表的页表号，第二列代表小页表在内存中的内存块号，比如根据一级页表(页目录表),0,3我可以知道0#页表存放在内存块号为3的位置，然后从3的位置拿出0#页表，就跟单级页表使用方法一样了

如何转换为物理地址

下面提醒几个需要注意的点

采用两级页表(没有快表)，需要三次访问内存，第一次访存是访问内存中的页目录表，第二次是访问内存中的二级页表，第三次是访问内存目标单元，根据推导，在没有快表的情况下，k级页表就要访存k+1次

基本变址机构

基本变址机构(两次访存)解决分页存储地址转换问题的，通常会在系统中放置一个页表寄存器来存放页表在内存中的起始地址F和页表长度M,进程未执行时，页表的始址和页表长度会放在进程控制快中，当进程调度时，操作系统内核会把他们放在页表寄存器里，具体流程看下图

动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足要求时，应选择哪个分区

首次适应算法(First Fit)

算法思想：每次从低地址开始查找，找到第一个能满足大小的空闲分区

实现方法：空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链或空闲分区表(链或表都按地址从小到大排列)，找到大小能满足要求的第一个空闲分区

最佳适应算法(Best Fit)

算法思想：因为动态分区分配是分配一块连续的内存，所以为了保证大一点的进程进来时能有足够的内存用，所以会尽量的留大块的空闲区，优先使用小的空闲区

实现方法：将空闲分区表或链按容量从小到大排序，当分配内存时，顺序查找表或者链，找到大小满足要求的第一个空闲分区，然后有必要的话重新排序表或者链(导致算法开销大)

缺点：若果我们每次都选最小的，那可能每次都要有一块很小(比如2MB)的内存难以被利用，这样就形成了很多外部碎片

最坏适应算法(Worst Fit)

算法思想：为了解决最佳适应算法会出现很多超级小的空闲分区，可以在每次分配时优先使用最大的空闲分区，这样剩下的就不会很小，方便以后使用

实现方法：将空闲分区表或链按容量从大到小排序，当分配内存时，顺序查找表或者链，找到大小满足要求的第一个空闲分区，然后有必要的话重新排序表或者链(导致算法开销大)

缺点：事实上我们每次找的第一个合适的就是最大的，因为他在表或链的最前面，肯定先匹配到他，这样的话每次都分割他，把它分成一块块小的区域，这样如果有个大一些的进程再来，那就谁也满足不了了

邻近适应算法(Next Fit)

算法思想：首次适应算法每次都从低地址开始查找，且低地址处被分成了很多很小的分区，这样在每次查找时都要经过这些小分区，但那些剩下来的很小的碎片可能都满足不了我却要在经过一遍，这就增加了查找的开销，因此就有了邻近适应算法，即从上次查找后的位置开始查找

实现方法：空闲分区以地址递增的次序排列(可排成一个循环链表)，每次分配内存时从上次查找后的位置开始顺序查找空闲分区链或空闲分区表(链或表都按地址从小到大排列)，找到大小能满足要求的第一个空闲分区，不需要重新排序表或者链

其实我们可以看到邻近适应算法就是首次优先算法的一个改编，他不一定就是比首次适应算法好，下面我们来分析一下

首次适应算法虽然每次都要从头开始顺序查找，蛋挞让前面的小内存更可能被用到，而后面的大内存被尽可能的保留下来(最佳适应算法的优点)

邻近适应算法每次都从上次查找完的位置开始往下查找，那前面的小内存可能满足，却只能接着往下走去分割大内存，如此一直进行下去，后面的大内存会被分成很多个小内存，这样等到有大进程来了却没有能满足的了(最坏适应算法的缺点)

综合来看，首次适应算法是最好的

连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间

单一连续分配：内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间



优点：实现简单，无外部碎片(内存中某些空闲分区由于太小而难以利用)；可采用覆盖技术扩充内存，不一定需要内存保护

缺点：只能用于单用户，单任务的操作系统中，有内部碎片(分配给某进程的内存区域中，如果有些部分没有用上，这就是内部碎片)，存储器利用率极低

固定分区分配：

为了能在内存中装入多道程序，又让这些程序互不干扰，会将整个用户空间划分为若干个固定大小的分区，每个分区内只放一道作业

有两种固定分区的划分方法，一种是分区大小相等，即在用户区分出若干个大小一样的分区，这样必然会导致不灵活，有的小作业却独占那么大的内存，有的大作业因为内存不够而进不来，但这种方法适用于控制多个相同对象的场合

另一种是分区大小不等，这样当然是增加了灵活性，可以满足不同大小的进程要求

操作系统会建立一个数据结构——分区说明表，来实现各个分区的分配与回收。他会有一个是状态，但被占用了会修改状态为已分配

那固定分区分配的优点：实现简单，无外部碎片

缺点：当用户程序太大，可能所有分区都不能满足要求，此时不得不采用覆盖技术空充，但会境地性能；会产生内部碎片，内存利用率低

动态分区分配：

动态分区分配不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并是分区大小正好适合进程的需要。有外部碎片，无内部碎片

系统会用空闲分区表或者空闲分区链这两种数据结构来记录内存的使用情况

当有很多空闲分区都能 满足时，会按照动态区分配算法来分配，具体以后再说

回收：(合并！！！)若某分区只被占了一部分，就在相应的表或者链改数据，若彻底被占了就直接在相应的表或者链去掉一个，若是回收内存，就要和他相邻的空闲内存分区合并，并把相邻的分区在相应的表或者链改数据

外部碎片：提到了很多次外部碎片这个问题，那怎么解决这个问题呢，其实办法是有的，那就是紧凑技术，就是将 内存区挪动，使他腾出一块连续的内存，这也就是为什么我们在装入时最好选择动态重定位方式。虽然紧凑技术可以解决存在外部碎片的问题，但时间代价很大

## 非连续分配管理方式

非连续分配方式：为用户分配的是一些分散的内存空间

基本分页存储管理：

如图所示，我将内存区分成每块为10MB的分区，也就是固定分区，这个时候进程A来了，他是23MB，我的每个区都满足不了，我还得满足他只能被放在一个完整的分区里，那么这个时候我必然要使用覆盖技术，但这很浪费。那么怎么解决这个问题呢，我可不可以把进程A拆成10+10+3呢，然后分别放在三个不同的分区里(不用连续)，答案是可以的，这就是基本分页存储，但是需要注意的是，必须是按照分区大小拆，我不能拆成8+10+5,但是好像这么做我会留下一个7MB的内部碎片啊

那我们如果把分区划分的小一点呢，比如说化成2MB，那就是2*11+1，这样我只会有1MB的内存碎片，试着把分区划的更小，你会发现内存碎片也更小

基本分页存储的思想就是把内存的用户区分成一个个相等小的分区，再按照分区将进程拆分成一个个小部分，小分区越小，产生的内部碎片越少，实际上就是将固定分区分配改造成非连续分配版本。每个分区就是一个页框，每个页框有一个页框号，页框号从0开始，边框号小的在低地址。将进程按页框大小分成若干部分，每部分叫页或页面，页的编号时页号，也是从0开始。

那也就是说页面会被一一放到页框里，但最后一个页面的大小可能会小于页框的大小，因此页框大小不应太大，否则会产生过大的内部碎片。

同时页面不一定要放入连续的页框中，可以间隔地放入页框中

实现方式:与之前连续存储不同的是，我现在把每一块都分散着放了，我的物理地址该怎么获取，因此这个实现就是我怎么能根据逻辑地址转换成物理地址

如图所示，这种方式是之前说过的装入方式的一种，动态重定位，我们把自己想做操作系统，我怎么找到逻辑地址为80对应的物理地址呢？首先我知道1页有50的存储单元，那80就应该在1号页，相对于1号页的偏移地址为30，好了，搞清楚之后我要装入了，这个时候我就要弄清楚1号页的其实物理地址是多少，哦是在450，那我的逻辑地址为80对应的物理地址就应该是450+30=480

因此我要进行如下4步才能将逻辑地址转为物理地址

算出逻辑地址对应的页号(逻辑地址/页面长度)(取整数部分)

该页号在内存中的起始地址

算出逻辑地址在该页面的偏移量(逻辑地址%页面长度)

物理地址=页面地址+页内偏移量

但操作系统一般都会让页号，页内偏移量，页面大小为2的整数幂，这样可以很轻易的就得到物理地址

如上图我们可以看见，如果我用32位表示逻辑地址，页面大小是12位，那后12位(页内偏移量)就是偏移量，前32-12=20位就是页号，则一个页面大小是2的12次方，共有2的20次方个页面

那么我怎么获取相应的页号在内存中对应的起始地址呢？

光看图可能有点晦涩难懂，假设我知道是在1页，页框大小为50，那看图，在页表里页号为1对应着块号为6，那我的起始地址就是6*50=300

实际上每个页表项的长度是一定的，页号是隐含的，具体理解看下图

也就是说在页表里实际上是只有块号，因为页号直接就顺序排列了，至于上图为啥要算字节，是因为要按字节编址

基本分段存储管理：

分段：是将进程按照逻辑分为若干个段，每个段都有自己的段名(程序员自己命名的)，每段从零开始编址

如下图所示，就是程序员给进程段起段名，每一段地址都是从零开始，回忆分页管理，这里是不等分的，而分页管理是将内存等分很多块，然后进程对应内存没一块的大小来分割自己进入内存

与分页一样，在装入内存时存在映射关系，且在内存里可不连续，虽然程序员命名了进程段，但编译程序会将段名转换成段号，这样才能让操作系统认识

如此看来，与分页相比，采用分段是用户可见的，程序可读性更高，但分页对于用户是不可见的

分段系统的逻辑地址由段号和段内地址(段内偏移量)组成，比如：

段号的位数决定每个进程最多可以分多少个段

比如上面段号有16位，那他就最多能表示2的16次方个，因此进程最多被分为64K个段

段内地址的长度决定了每个段的最大长度是多少

比如上面段内地址有16位，如按字节编址，则每个段最大长度为64KB

段表：与页表差不多，只不过多了段长，因为分段不是等分的，同时，段表中段号也是隐式的，不占地址空间

其中，每个段表项的长度实际上是相同的，如上面说的假设逻辑地址=16位段号+16位段内地址，那么用16位表示段长(不会超过最大段内地址)就足够了，若物理内存是4GB，则可以用32位表示整个物理内存，因此，让每个段表项占16+32=48=6B就行了，因此若段表的起始地址是M，则K号段对应的段表项存放地址为M+K*6(注意这里说的是段表项，是在段表里找段表项，不是进程)

机器指令中的逻辑地址用二进制表示：00000000000000100000000100000000

其中前十六位表示段号，后十六位表示段内地址，那怎么将逻辑地址转为物理
地址呢

在段表上处理机之前，段表寄存器会被存放在系统区的PCB中

注意第4步，需要比较段内长度和段长，因为不等分，所以有违规的可能

分页与分段的区别：

• 分页的用户进程地址是一维的，程序员只需给出一个记忆符即可表示一个地址

分段的用户进程地址是二维的，程序员既要给出段名，也要给出段内地址

• 分段比分页更容易实现信息的共享和保护，比如下面的消费者进程和生产者进程都想访问1号段，分段就能体现出他的优越性，但是注意只能共享不能修改的代码(纯代码或可重入代码，不属于临界区)

• 分页分段都是两次访存，当然分段也可引入快表，加快地址变换速度

段页式管理方式：

分页，分段优缺点：

那结合分段分页就诞生了段页式管理

因此段页式管理的逻辑地址结构应该是

段号的位数决定了进程最多能被分成多少段：段号占16位，所以进程最多被分成2的16次方->64K个段

页号位数决定了每个段最多能分多少个页一：页号有四位，所以每个段最多被分成2的四次方->16个页面

页内偏移量决定了每个页面大小是多少：页内偏移量占了12位，因此每个页面大小为2的12次方,->4KB(按字节编址)

同样的用户只能看到分段，分页是由操作系统做的，用户看不见，因此段页式管理的地址空间是二维的

因此一个进程对应一个段表，多个页面

怎么将逻辑地址转换成物理地址

其中第四步，是因为段长度不等，所以要检查，和分段管理要检查段内地址是一个道理

当然也可以用快叫，这样如果命中就只需要一次访存

覆盖与交换是内存扩充的两种方法

覆盖技术

解决程序大小大于物理内存总和的问题，即将程序分为多个段，常用的段常驻在内存，不常用的段在需要的时候调入内存

内存被分为一个固定区和若干个覆盖区，需常驻内存的段放在固定去，调入后不再调出(除非运行结束)，不常用的段放在覆盖区内，需要时调入内存，不需要时调出内存

如下面的栗子

如图则是按照程序的逻辑将不可能同时被访问的程序段放在一个共享的覆盖区上，在逻辑上看，内存是被扩展了的。但上图程序的逻辑操作系统并不知道，只能由程序员声明覆盖结构

也就是覆盖技术的缺点：对用户不透明，增加了用户编程的负担

覆盖技术只适用于早期的操作系统，已成为历史

交换技术

设计思想：内存空间紧张时，系统将内存中某些进程暂时换到外存，把外存中已经具备运行条件的进程换入内存(进程在内存和磁盘中的调度–中级调度)，注意PCB会常驻内存，不被调出

那么就有了下面的几个问题

应该在外存的哪里保存换出来的进程？

首先要补充一个知识，磁盘存储空间分为对换区和文件区，文件区是存放文件的，主要追求存储空间的利用率，因此对文件空间的管理采用离散分配方式；对换区只占磁盘空间的一小部分，被换出的进程就放在这里，由于对换速度直接影响系统整体速度，所以对换区采用连续分配方式，因而对换区的I/O速度比文件区更快

什么时候进行交换？

在内存紧张时进行，系统负荷降低就暂停

应该换出哪些进程？

阻塞进程；优先级低的进程；有时考虑到有可能因为优先级低一进来就被调出，有的系统还会考虑进程在内存中的驻留时间

虚拟存储技术

我们知道，传统的存储管理再加上覆盖技术或者交换技术就可以实现内存扩充，提高效率。现在再讲一种扩容方法-虚拟存储技术

下面来看看传统的存储管理的缺点

• 传统的存储管理(连续分配，非连续分配)，很多时候暂时用不到的数据仍会占用内存，导致内存利用率不高。

• (一次性)作业又必须一次性全部装入内存才能运行，这就导致两个问题，一个是作业很大时，不能全部装入内存，导致大作业无法运行，第二个问题是，当有大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业可以运行，导致多道程序并发度降低。

• (驻留性)一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束，事实上，在上一个时间段，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中驻留大量的，暂时用不到的数据，浪费了宝贵的内存资源。

但！虚拟存储可以解决上面的所有问题

还记得之前讲过的两个局部性原理吗？一个是时间局部性，就是某条指令或数据可能会被经常多次刚问(比方说循环)，另一个是空间局部性，就是一块数据他周围的数据很可能被接连访问(比方说数据被连续，顺序存储)

那怎么利用这两个局部性来扩充内存呢？

答案是高速缓冲技术：将近期会频繁访问的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中

下面这幅图就是计算机存储器的层次结构，我们可以看到越往上越快，越贵，越小，就比方说之前提到的快表机制，就是将近期经常访问的页表项副本放到更高速的联想寄存器中，这样我们就可以快速的拿到要用的，将其他不常用的用更小的成本存储起来

这样，基于局部性原理，在程序装入时，可以将程序中很快会用到的布恩装入内存，暂时用不到的部分留在外存，就可以让程序开始执行

在程序执行过程中，当所访问的信息不在内存中时，由操作系统负责将所需信息从外存调到内存，然后继续执行程序

当内存空间不够时，由操作系统负责将内存中暂时用不到的信息换到外存

在操作系统的管理下，用户会觉得有一个比实际内存大得多的内存，这就是虚拟内存(这就是操作系统虚拟性的体现，实际的物理内存没有变，只是在逻辑上进行了扩充)

需要注意的是

虚拟内存的最大容量是计算机的地址结构(CPU寻址范围)确定的

虚拟内存的实际容量是min(内存和外存之和，CPU寻址范围)

虚拟内存的三大特征

• 多次性：无需在作业运行时将作业一次性全部装入内存，而是允许分为多次调入内存

• 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入，换出

• 虚拟性：从逻辑上扩充了内存的容量，远大于实际的容量

那怎么实现虚拟内存技术呢？

因为我们需要允许一个作业多次调入内存，就肯定不能采用连续分配方式，会不方便实现，那虚拟内存的实现就需要建立在离散分配的内存管理方式的基础上，也就有了虚拟内存技术的三种方式

与传统的离散分配有两点区别

• 在程序执行中，当所需信息不在内存，操作系统需要从外存调进来，也就是说操作系统要提供请求调页(或请求调段功能)

• 如果内存空间不够，操作系统还要负责将内存中暂时用不到的信息换到外存，也就是说操作系统要有页面置换(或段置换)的功能

请求分页存储管理

• 页表机制

为了实现请求调页，操作系统需要知道每个页面是否已经调入内存，如果还没有调入，操作系统需要知道页面在外存的什么位置；为了实现页面置换，操作系统需要根据一些指标来判定谁被调出去，有的页面没有被修改过，就不需要再费力把它调回外存，有的页面被修改过，就需要将外存中的旧数据覆盖，因此，操作系统需要记录各个页面是否被修改过

下面是请求分页存储管理的页表与基本分页存储管理的页表的对比

• 缺页中断机构

在请求分页系统中，每当要访问的信息不在内存中需要去调入时，就会发生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断，这个时候缺页进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列

若果内存中有空闲块，就为该进程分配一个空闲块，将所缺页面装入该快，并修改相应页表中额页表项

若内存中没有空闲块，就要用页面置换算法将一个页面淘汰，若盖爷年在内存期间被修改过，就要写回外存，未修改过的页面不用写会外存

缺页中断是因为当前执行的指令想访问的目标页面未调入内存而产生的，因此属于内中断

一条指令当中可能发生多次缺页中断，比如copy a to b,因为a，b不在一个页面，就可能会发生两次缺页中断

• 地址变换机构

除上图之外还有几点细节

快表中的页面一定是在内存中，若某个页面被调到外存，快表中的相应表项也要删除，否则可能访问错误的页面

只有写指令才需要修改”修改位”，并且，一般来说只需要修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表，这样可以减少访存次数

和普通中断处理一样，缺页中断也需要保留CPU现场

需要用某种页面置换算法来决定换出哪个页面

换入换出操作都依赖于I/O操作，因此若换入换出操作太频繁会有很大的开销

页面调入内存后，需要修改慢表，同时也需将表项复制到快表中

• 页面置换算法

页面的换入换出需要磁盘I/O，会有较大开销，因此好的页面置换算法应该追求更少的缺页率

最佳置换算法：

每次选择淘汰的页面将是以后永不使用或最长时间不被使用的页面，这样可以保证最低的缺页率，拿下面这个例子举例

当要访问页面2时，内存里没有，就发生缺页，这个时候发现内存已经满了，因此要用页面置换算法淘汰一个，若用最佳置换算法，目前内存里有7,1,0这三个页面，看看没页面2后面一次出现0,1,7，因此页面7是最长时间内不被使用的页面，因此淘汰7

当你把这个表完全分析完之后，你会发现，缺页发生了9次，但页面置换只发生了4次，因此却也不一定会发生页面置换，只有在内存中没有空闲块时才会发生页面置换

但是，想使用最佳置换算法就得知道访问页面的顺序，这可想而知，在进程运行时才知道下一步要访问谁，因此最佳置换算法是无法实现的

先进先出置换(FIFO)：

每次选择淘汰的页面是最早进入内存的页面

实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可，队列的最大长度取决于系统为进程分配了多大内存块

具体过程很简单，就不赘述，但需要注意的是我给进程分了更多的内存块，他的缺页次数却不减反增，这是Belady异常，只有FIFO算法才会产生Belady异常，另外，虽然FIFO算法实现简单，但是该算法与进程实际运行的规律不适应，因为先进入的页面有可能最经常被访问，因此，算法性能差

最近最久未使用置换算法(LRU)：

每次淘汰的是最近最久未使用的页面

实现方法：页表的每一个页表项增添一个”访问字段”，记录该页面自上次被访问以来所经历的时间t，当要淘汰一个页面时，淘汰现有页面t最大的，即最近最久未使用的页面

下面举个栗子来直观感受下这个算法

如图走到箭头位置时，内存给分的内存块都满了，这个时候就要淘汰一个页面，目前内存里有1,8,7,2这四个页面，那根据最近最久，那从3逆向前找，依次找到8,1,2，7,；那7就是最近最久，淘汰7

因为该算法实现需要专门的硬件支持，虽然算法性能很好但实现困难，开销大

时钟置换算法(CLOCK)：

最佳置换算法的性能最好，却无法实现；先进先出置换算法随实现简单但性能差；最近最久未用置换算法性能好，是最接近最佳置换算法的，但实现起来需要硬件支持，算法开销大

时钟置换算法是一种性能和开销均衡的算法，又称最近未使用算法(NRU)

实现方法：为每个页面设置一个访问位

将内存里的页面通过链接指针依次连接成一个循环队列，当某页被访问时，其访问未知为1；当要淘汰页面时，从队头开始，若访问位是0，就将该页换出，若访问位为1，就将它置为0，暂不换出，继续检查下一页面，若第一轮扫描的所有页面都是1，则将这些页面置为0后，进行第二轮扫描时，一定会有访问位为0的页面，因此，时钟置换算法选择淘汰页面最多会经过两轮扫描

要淘汰时，指针开始动，第一次检查在队首，其他看情况而定

淘汰之后，指针才挪到下一位

eg：假设系统为某进程分配了5个内存块，并考虑以下页面引用串：1,3,4,2,5,6,3,4,7

分配了5个内存块，因此访问前五个页面时，只需依次链接成循环队列即可，且每访问一个页面就把该页面的访问位置为1

当想访问第6个页面时，已经没位置了，这个时候就要淘汰页面了，就从1号页(队头)开始，发现他的访问位是1，则将它置换成0，再来到3号页，发现他也是1，再将它置换成0，如此向下，把这一圈都检查完了，也都置成了0

接下来开始第二轮，检查1号页时，发现他是0，那就把它淘汰，将6号页换过来并置为1

接着往下走(像时钟一样不会逆着走，因此这里不是从6号页开始，而是继续到下一个页面)，3号页面在内存里，而且访问位是0，就将它的访问位置成1，接着往下走，4号页同理，注意3,4这里不需要淘汰页面，因此指针不走，还在3

要访问7页面时发现内存里没有，因为要淘汰页面了，指针开始动，这个时候就从3号页开始了，他是1，就将它置为0，指针来到4号页，发现他是1，就将它改成0，指针来到2号页，发现他本来就是0，因此置换出他，换上7号页，并置为1，淘汰后，指针指向5号页

改进型的时钟置换算法

注意几个点，第一轮找(0,0)因为这个时候没有被修改的，且第一轮扫描不修改任何标志位

第二轮找(0,1)，因为第一轮没有(0,0)，所以只能退而求其次来选择(0,1),这次要修改访问位，置为0

第三轮找(0,0)，因为第2轮没找到(0,1)，且都将访问位置成了0，不修改任何标志位

第四轮找(0,1)