03-存储管理

1. 操作系统虚拟存储管理

    虚拟存储（ virtual memory）技术的概念是：把很大的程序（数据）分成许多较小的块，全部存储在辅存（硬盘、U盘）中。运行时，把要用到的程序（数据）块先调入主存，并且把马上就要用到的程序块从主存调入高速缓存（catch）。这样，一边运行程序，一边进行所需程序（数据）块的调进调出只要及时供应所需处理的程序与数据，程序就能顺利而高速地运行下去。因此，对于应用程序员来说就好像有一个比实际主存大得多且可以放下整个程序的虚拟主存空间。当辅存中的程序块调入主存时，必须使程序在主存中定位（程序运行时找到数据在内存中的位置），该工作由系统自动完成，应用程序员不用考虑如何把程序地址映像和变换成实际主存的物理地址，因此，虚存技术对于应用程序员来说是透明的。

早期的分区化管理， 将内存分区化，在内存中划定用户区域，供用户程序调入内存时使用， 如果执行1G大小的程序，需要将1G大小的文件一次性调入内存，如果此时内存没有1G的连续空间， 执行将失败。基于这样的问题， 提出了页式存储，段式存储、段页式存储的方法。

2. 页式存储

    用户程序等分为大小相等的页， 物理内存也等分页。用户程序调入内存的时候，不再是一次性调入整个程序，而是要运行哪些块就调入哪些块到内存中，此时需要一个“页表”来记录用户程序和物理内存的映射关系，这样可以运行超越内存容量的程序（运行时，只是部分页加载中内存中，然后继续加载时会发生页面置换，使用了页面淘汰算法）。

    优点： 利用率高，碎片小、分配和管理简单。如程序有102K，此时需要分配26个页，每个页大小为4K，一共需要分配104K，只有2K浪费。

    缺点：增加了系统开销，可能产生抖动现象。 页式存储需要查页表来查找程序页面与内存的映射关系，不像之前连续的地址空间的时候，不需要查找页表。

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

    高级程序语言使用逻辑地址， 运行状态，内存中使用物理地址。

    逻辑地址组成： 页号+页内地址， 物理地址组成： 块号+页内地址

    逻辑地址与物理地址： 他们的页内地址是相同的， 但是页号不同。逻辑地址的页号是连续的， 而物理地址的页号一般是不连续的。

        转换步骤： 

            1. 求出逻辑地址的页内地址（逻辑地址的页内地址即为物理地址的页内地址）

            2. 求出逻辑地址的页号， 根据页表查到物理地址的块号（物理地址的块号又称页帧号） 

            3. 物理地址即为 ： 物理块号+页内地址

3. 段式存储

    各个段的大小可以不同， 段表： 存储的是段号、段长、基地址

    优点：多道程序共享内存，各段程序修改互不影响（ 一个函数就是一个段， 可供多个程序调用， 便于程序共享）

    缺点：内存利用率低，内存碎片浪费大

    经常会有这样的考题：

    段的地址为： (2, 100K) 判定是否合法？ 2为段号，100K为偏移量， 从上图中可以看出，段长只有15K，120K是段的基地址，100K远大于15K，地址非法。

3. 段页式存储

    结合段式、页式两种，先分段再分页， 折中产物，两者优点集合起来

    先查段表，然后查页表， 效率大大降低。

    优点：空间浪费小、存储共享容易、存储保护容易、能动态连接

    缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

4. 快表

    页表放到高速缓存（Catch）中，速度快，提高了查询速度。

    快表是一块小容量的相联存储器（ Associative Memory），由高速缓存器组成速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

    段表、页表放到内存中，是一种慢表，放到cache中是快表，快表用来存放当前访问最频繁的少数活动页面的页号。

5. 页面置换算法

    常见的页面淘汰算法有最优算法、随机算法、FIFO、LRU

    最优算法Optional OPT： 理论层面的页面淘汰算法，已知页面系列的情况下， 计算什么时间淘汰哪个页面性能最高，针对每一个场景，最优算法不一样，没有普遍的规律，在实际执行中，预先是无法知道页面序列的， 没办法直接应用。

应用场景： 认为最优的写出来，然后与其他的方案进行对比。

    随机算法： RAND，随机淘汰一个，性能不稳定。

    先进先出算法 FIFO：可能产生抖动现象和Belady现象

        FIFO的抖动现象的解释

        在请求分页存储管理中，可能出现这种情况，即对刚被替换出去的页，立即又要被访问。需要将它调入，因无空闲内存又要替换另一页，而后者又是即将被访问的页，于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重导致系统瘫痪，这种现象称为抖动现象。 抖动现象发生在FIFO页面置换算法中，FIFO还会产生Belady现象，因而FIFO并不是一个好的置换算法。

        FIFO的Belady现象图示

        如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，但缺页率反而提高的异常现象

    最近最少使用算法 LRU：不会产生抖动和Belady现象，分配的资源越多，表现的性能越好