【操作系统】第五章：虚拟内存（Part2:虚拟内存管理技术）
虚拟内存管理技术-简称虚存技术
解决覆盖技术和交换技术弊端的技术
区别：过程由OS完成，减轻程序猿负担。
根据当前执行情况可以动态的导出导入，但是粒度更小，不只是程序间，还可以以页或者段为粒度来进行导入导出。
如图所示，OS和MMU支持下，以P3为例，P3只在内存中放了2个内存页，其他的全放入了硬盘中。因为此时只用到了这一小部分数据，这样就使得一个本来比较大的程序在有效时间段内仅使用一小部分内存资源。虚存技术，除了需要硬件支持外，还需要程序具有局部性。
程序的局部性原理
局部性原理分为了时间局部性和空间局部性。
时间局部性：一条指令和下次执行，一个数据的访问和下一次访问都集中在一个较短时期内。
空间局部性：当前指令和邻近几条指令、当前访问和邻近的几个数据都集中在一个较小区域内。
分支局部性：一条跳转指令的两次执行，很可能跳到相同的内存位置
访问速度快、空间大、使用方便（不需要程序猿过多构思数据结构）
例子：
这个整数数组的空间大小是1024x1024,int型每一个是4byte，也就说这一个数组整体会占4M的内存空间。但是物理内存只有4K。此时，
程序1：A【0】【0】~ A【1023】【0】==>A【1023】【1023】
程序2：A【0】【0】~ A【0】【1023】==>A【1023】【1023】
区别：实际上A【1】【0】和A【0】【0】从空间上来看，中间差了1024个数据也就说是4K的数据大小，但是A【1】【0】和A【1】【1】之间的距离只有一个数据也就说4byte。
那么对于程序2而言，在数据A【0】【x】占据了一个页。当他第一次访问时，数组的数据还在硬盘上时，会产生缺页异常，此时OS会把仅有的4K空间使用上，并把A【0】【x】数组放入内存空间 ，然后就可以对A【0】【x】数组进行正常访问了。根据循环，第二次访问A【0】【1】时，因为已经有了对应的页，就不会发生页异常。内循环执行完后，进入下一个内循环，此时访问A【1】【0】发生一次中断，然后接下来的1023次访问不会再发生中断。具备很好的空间局部性和时间局部性。也就意味着一共发生了1024次缺页中断
对于程序1而言，在数据A【0】【x】占据了一个页。当他第一次访问时，数组的数据还在硬盘上时，会产生缺页异常，此时OS会把仅有的4K空间使用上，并把A【0】【x】数组放入内存空间 ，然后就可以对A【0】【x】数组进行正常访问了。根据循环，第二次访问时，会访问A【1】【0】，此时会再次产生缺页异常，因为对应A【1】【x】的页仍然不在内存，在硬盘中，需要再次把4K的物理内存用到A【1】【x】数组上，此后导入A【1】【x】的页。同理，在一个内循环中，每一次都会跳4K空间去访问一个数据，每一次访问都会发生缺页异常。也就意味着一共发生了1024x1024次缺页中断
可以看出程序的不同写法对开销的影响是相当大的。
缺页/段异常
上面讲到的，因为内存中只有部分数据，所以可能会发生程序进行到一定阶段后，接下来的数据访问不到的情况。因为另一部分数据不在内存中而在硬盘中，此时会发生一个缺页或者缺段异常。 此时OS会进行处理，如果内存还有空间，就会把数据或者指令从硬盘导入内存，这样程序就可以继续执行。如果内存空间不足，则OS需要考虑当前阶段不会立刻用到的数据导出到硬盘，然后把需要的数据换入内存。这个选择哪个程序导出也很重要。选择的好，访问读写的次数就会少，整体系统性能也会提高。
虚存技术的基本特征
1.空间大： 通过内存和外存结合，提供给用户的虚拟内存空间通常大于实际物理空间。 32位机器理论上可以访问4GB而且物理内存只有256M，但是硬盘容量很大。通过硬盘的补充，可以实现内存中跑多个程序，而且每个程序会认为自己占用了4GB的空间。kernel是常驻内存不能被换出。
2.部分交换：与交换技术相比，虚拟存储的调入和调出是对部分虚拟空间进行的
3.不连续性：物理内存分配不连续，虚拟空间使用也不连续。（因为换入换出会导致原本连续的地址空间很可能再换回后不再在换出位置）
虚存技术的实现
虚拟页式内存管理
如图所示， 逻辑地址空间和物理地址空间是靠页表来维持映射关系的。页表项的索引是页号，页表项的内容是页帧号。页表项除了页帧号之外，其实还有几个单位的bit作为标志位，比如存在位。那么这里的内存访问查找页表发现对应页表项的存在位是0，则说明这个虚拟地址空间没有对应的物理空间，产生访问异常。
大部分虚拟存储系统都采用虚拟页式内存管理。为了实现，除了页式内存管理的基本功能之外，在增加两个新的功能（请求调页和页面置换）【需要访问这个页时，才把这个页调入到内存中】
请求调页：当一个用户进程需要调入内存运行时，不会把所有程序都放入内存中，只是装入一部分程序。放到个别的页里，运行的时候就有可能出现访问的数据和代码不在内存中，此时就会由CPU发出缺页异常的信号，然后OS根据产生异常的地址来找到对应到外存中需要被调入的数据，然后将其放入相应的物理页去，使该页可以继续执行。
页面置换：访问过程中，随着程序的执行他占用内存越来越多，此时需要把不常用页换出，把当前需要的页换入，这就是页面置换。该功能实现的好坏就决定了整体效率，所以后面会专门设计一个有效的页面置换算法，后续会详细讲解。
为了实现这两个功能，我们需要在页表项里增加一些特殊的位，来辅助完成这些功能。有4个位比较重要。
1.存在位/驻留位：这个位表示该页是否存在内存中。0表示不在内存中，1表示在内存中。为1也就说逻辑页号一定对应一个物理页帧号。如果为0则说明内存中没有对应物理页支持，很有可能对应数据在外存中，此时访问会出现访问异常
2.保护位：表示允许该页做何种类型的访问，比如只读、只写，可读写、只执行等。 如果只读标识下执行写操作就会出现异常。
3.修改位：表明这个页是否被修改（写操作）过。如果这个页被写过，为1,；没被写过，就为0。如果内存中数据被写过，也就说当前数据与硬盘中数据不一致了，这时候最新的数据放入内存时，进行换出操作，需要把这个数据保存到硬盘中，使得硬盘中数据与内存中数据一致。如果修改位为0，则内外数据一致，此时如果进行换入换出操作，只需要释放就可以。所以修改位的使用可以有效提高修改位的效率。
4.访问位：这个也是否被访问过，访问过为1，没有访问为0。置换算法中，我们会把页换出去，那么换哪些？应该换当前没有访问的页，这位可以表明这个页是否经常使用，近期是否会使用等信息，我们可以根据这个特点决定换出对象。
驻留位为0，没有对应的虚拟地址映射到物理地址上。
这里执行了两个指令。
1.
访问，把虚拟0地址的内容赋给一个寄存器。0地址对应页表里的映射关系，是物理地址中的页帧号2位置，所以他的实际物理地址应该是2*4K=8K（8192Byte）
2. ==>
把虚拟地址32780读到寄存器中，32780其实对应到逻辑地址中的页号为8的项中，因为驻留位为0，没有对应到物理地址的映射，则会触发缺页异常。
缺页中断处理
①：CPU执行指令，如果一个内存地址没有对应的映射关系，发生缺页异常。
④：需要访问的地址对应的硬盘中的数据以页的单位从硬盘读入内存中，然后修改页表，驻留位改为存在并把页帧号改成该页帧号。
如果没有空闲空间时，需要使用页面替换算法。
后备存储（二级存储）
硬盘存储数据的特征：
1.数据：数据文件放在硬盘上，当需要时，如果内存中没有，则从数据文件中读出。这是一种后备存储。
2.代码：操作系统会在令程序执行很多指令，指令其实也是一种数据，放在执行程序里/硬盘里。同理，读入内存并让CPU执行，当指令不存在，会进一步从程序中读入这条指令。
3.动态链接库：库的代码数据也是放在硬盘的。同理也是需要时读入
4.交换文件(swap file)：程序运行过程中有可能产生许多数据，但是这些数据没有对应到具体的文件，就是动态产生的数据，这些数据也有可能占用了不小的空间且需要换出到硬盘中，则此时OS会在硬盘中开辟一个专门的区域——swap file。这个文件内的数据没有与文件直接对应的内存内容
这四类形成了后备存储（二级存储），有了二级存储的支持，保证了空间的有效性。
虚拟内存性能
分析执行开销：
分析这个例子中的参数，10代表一次内存的访问时间，页表命中率也就说没有缺页的概率，就是1-p；如果产生缺页，自然就需要访问磁盘，那么处理时间就是5ms（)。产生缺页后至少要做一个读操作，为。
q是页修改概率。代表对某一个内存页的写操作后，且该数据需要换出时，前面讲过这个换出操作导致当前数据与硬盘中数据不一致，需要个更新硬盘数据，也就说要对硬盘进行一个写操作。写硬盘操作的开销也是5ms，缺页且需要页修改的情况下的开销为。
脏页简单来说就是根据一个高速缓存表来不断更新数据的常用标识，因为硬盘的读写速度远赶不上内存的速度，系统就把读写比较频繁的数据事先放到内存中，以提高读写速度，这就叫高速缓存。页作为高速缓存的单位，当某一个页被访问后，对其标识新并且对上一个访问的页标识旧，旧的级别分为不同级别，当旧的级别达到一定程度时，修改高速缓存里，该页就被内核标记为脏页，内核将会在合适的时间把脏页的数据写到硬盘中去，以保持高速缓存中的数据和磁盘中的数据是一致的。
p足够小，那么平均访问时间就会接近10ns，p如果比较大，则会导致整个循环的效率比较差。但是因为程序的局部性特点，意味着缺页次数不会过多，此时效率可以得到保障。