存储管理

1 存储器的层次结构⭐⭐⭐⭐⭐

计算机的存储器层次结构，从下到上依次为：

1. 寄存器：位于CPU内部的存储器，速度最快，容量最小，一般只存储少量临时数据和指令操作码。
2. 高速缓存（Cache）：位于CPU和主存之间的存储器，作为缓存来提供更快的访问速度和更高的访问效率，一般分为L1、L2、L3级别。
3. 主存储器（Main Memory）：由DRAM（Dynamic Random Access Memory）芯片组成的存储器，是计算机系统中存储数据的主要设备，速度比较快，但容量一般较小。
4. 辅助存储器（Auxiliary Storage）：例如硬盘、光盘等，容量很大、速度较慢而且访问时间不固定，主要用来长期存储和备份数据，可作为虚拟内存，供程序使用。

以下是存储器层次结构的图示：

   ---------------------------
    |           CPU           |
    ---------------------------
                |
    ---------------------------
    |          Cache          |
    ---------------------------
                |
    ---------------------------
    |        Main Memory      |
    ---------------------------
                |
    ---------------------------
    |     Auxiliary Storage   |
    ---------------------------

其中，CPU内部的寄存器与Cache的关系最近，Cache与主存之间的关系其次，主存与辅助存储器之间的关系最远。在程序进行读写操作时，从辅助存储器到CPU的路径上逐级访问，随着存储器层次的提高，存储器的存储速度逐渐提高，但是容量逐渐降低。

这些存储器的速度和容量随层次的不同，从上至下逐渐降低而容量逐渐增大，每级存储器的价格也会随着降低。优化程序在性能上应该利用好高速缓存和主存储器，在程序设计时尽量减少对辅助存储器的访问次数。

2 程序的装入和链接⭐⭐⭐

程序的装入

定义：是将可执行程序从外存调入内存的过程。程序的装入通常包括以下几个步骤：

1. 分配内存空间。操作系统需要查看可执行程序的大小，预留足够的内存空间。
2. 加载可执行代码。将可执行程序的二进制代码从外存读入内存中。
3. 加载数据段。将可执行程序中的数据段加载到内存中，通常是动态分配内存空间，将数据段内容复制到动态分配的内存空间中。
4. 重定位。在加载代码时，需要进行地址的重定位，将程序中使用的地址映射到正确的内存地址上，保证程序能够正确运行。

通常，操作系统会在程序运行启动时，预先分配一段内存用于存储可执行程序，该段内存称为进程空间。进程空间通常包括代码段、数据段、堆和栈等不同区域。可执行代码存储在代码段中，在代码段加载时，需要根据程序代码的起始地址和长度信息计算出代码段中具体的内存地址，并将代码全部加载到指定的内存地址中。

数据段通常存储程序的全局变量和静态变量等数据，由于数据大小可能不确定，因此数据段通常采用动态分配内存的方式进行加载。

在程序加载时，通常需要进行地址的重定位。在编写程序时，通常使用的是逻辑地址，即程序所使用的内存地址是虚拟的，需要在加载时转换成物理地址。由于程序加载位置可能不确定，因此需要将所有的逻辑地址都加上偏移量，计算得到正确的物理地址。

以上就是程序装入的基本步骤。

程序的链接

程序的链接是指将程序的各个模块之间相互调用的关系建立起来的过程，通常包括以下几个步骤：

1. 符号解析。将各个模块中的符号引用找到对应的符号定义。
2. 地址重定位。将引用的符号的地址映射到正确的地址上。
3. 符号决议。将静态链接的符号连接到代码中。
4. 重定义。将符号定义合并。

链接可以分为静态链接和动态链接。

静态链接是指将外部模块代码的副本直接拷贝到可执行文件中，使得可执行文件直接包含外部模块中的代码。这种方法使得可执行文件无需依赖外部模块的存在，也不需要在程序运行的时候进行链接。但是，这样会增加可执行文件的体积，使得可执行文件变得更大。

动态链接是指在程序运行时才进行链接，使得程序在链接的时候可以动态地使用外部模块。这种方式使得多个程序可以共享同一个库文件，并且在运行过程中能够动态地升级和替换库文件。但是，动态链接可能会降低程序的执行效率。

3 分配存储管理方式⭐⭐⭐⭐⭐

存储管理是操作系统中非常重要的一个功能。它的主要任务是对计算机的物理内存进行分配和管理，以便让不同的程序和进程能够共享计算机的内存资源。常见的存储管理方式包括以下几种：

1. 单一连续分配：将整个内存分配给一个进程使用，操作系统只有在进程执行完毕后才能释放内存。这种方式适用于单用户系统，但不适用于多任务操作系统。
2. 固定分区分配：将内存划分成多个固定大小的区域，每个区域只能分配给一个进程使用。这种方式比较简单，但是容易浪费内存空间。
3. 动态分区分配：将内存分成不同大小的块，每个进程请求分配内存时，会从可用的块中选择一个大小适合的块进行分配。这种方式比较灵活，但是需要维护一个内存管理表，而且容易产生内存碎片问题。
4. 伙伴系统：将内存分成大小相等的块，每次分配内存时，选择一个大小刚好的块进行分配，如果需要更大的内存时，则从相邻的两个较小块中合并成一个相对较大的块。这种方式相比于动态分区分配效率更高，但是实现相对较为复杂。
5. 虚拟存储：在实际内存不足时，将部分不常用的数据和代码转移到硬盘等外部存储器中，以释放内存空间。由于硬盘速度较慢，虚拟存储的性能相比于实际内存较低，但是可以大大扩展计算机的内存容量。

4 动态分区分配算法⭐⭐⭐⭐⭐

动态分区分配是一种可以动态地为进程分配内存的方式，根据进程的需要，将内存分成多个不同大小的块。当进程需要内存时，动态分区分配算法会按照一定规则从内存块中选取一个大小适合的块分配给进程。主要的动态分区分配算法包括以下几种：

1. 首次适应算法（First Fit）：分配时从内存分区的起始地址开始查找，找到第一个能满足需求的分区进行分配。由于查找速度快，所以操作效率较高，但是可能会产生较多的内存碎片。
2. 最佳适应算法（Best Fit）：分配时从内存分区中找到能满足需求且大小最小的分区进行分配。这种方式可以更充分地利用内存空间，但是搜索代价较大，容易产生大量的未分配空间。
3. 最坏适应算法（Worst Fit）：分配时从内存分区中找到能满足需求且大小最大的分区进行分配。与最佳适应算法相比，最坏适应算法更容易产生较大的未分配空间。
4. 循环首次适应算法（Next Fit）：与首次适应算法类似，但是从上次分配分区的下一个开始搜索，避免了每次都从头开始搜索的开销，减少了碎片产生的概率。

这些算法各有优缺点，根据实际需求选择合适的算法。

5 分页存储管理方式⭐⭐⭐⭐

分页存储管理方式是一种内存分配方式，将物理内存分成大小相等的若干个固定大小的块，称为页框（Page Frame）。同时，将进程的虚拟地址空间分成大小相等的若干个固定大小的块，称为页面（Page）。当进程需要使用某个页面时，操作系统将其映射到某个页框中，页框的大小通常为 4KB 或 8KB。

此外，分页存储管理方式需要使用页表（Page Table）进行虚拟地址到物理地址的转换。页表是一个记录了所有页面与页框之间映射关系的数据结构，每个进程都有自己独立的页表。当进程访问某个页面时，操作系统会根据页表将该页面映射到对应的物理地址上。

分页存储管理方式的优点是：

1. 提高了内存利用率：按照固定大小划分内存空间，避免了内存碎片的产生，提高了内存利用率。
2. 方便了进程的内存管理：通过使用页表实现虚实地址的映射，进程可以更方便地进行内存管理。
3. 提高了系统的可靠性：通过使用分页机制，使得操作系统能够更方便地对内存空间进行保护和管理，提高了系统的可靠性。

但分页存储管理方式也存在一些缺点：

1. 由于每个进程都需要有一份页表，并且页表较大，需要额外的内存空间，因此会增加操作系统的开销。
2. 分页会导致一些额外的开销，如页表的查询和更新、页面的拷贝等，这些操作都会导致一定的开销。

6 分段存储管理方式⭐⭐⭐⭐

分段存储管理方式是一种将进程的虚拟内存空间划分为多个大小不同的段，每个段代表着不同的逻辑单元，如代码段、数据段、堆栈段等。与分页方式类似，每个段都被映射到物理内存中的某个区域。

分段存储管理方式的优点：

1. 每个段都有特定的逻辑含义，使得程序的分析和设计更为方便。
2. 每个段的大小可以根据其需要进行动态分配，可以更精确地控制内存的使用。
3. 避免了由内部碎片带来的浪费。
4. 同一段内的地址空间可以连续使用，便于内存的管理和维护。

分段存储管理方式的缺点：

1. 由于每个进程的段数及大小都不同，因此需要使用表格来存储段信息，会增加表格的复杂程度。
2. 分段模式中，段与段之间不是必须紧密相邻的，并且可能会发生随机存取，这样就会造成重复而频繁的内存空间的调用和切换，这样会拖累整个系统的速度。
3. 由于段的大小不同，因此碎片问题仍然存在，如果不加以管理，会浪费部分内存空间。

总的来说，分段存储管理方式的优缺点与分页相比，二者都有其适用的场景。分页更适合于进程内存的紧凑管理，而分段更适合于程序中多个逻辑单元的分离存储。

7 段页式存储管理方式⭐⭐⭐⭐

段页式存储管理方式是将段式存储管理方式和页式存储管理方式结合起来的一种存储管理方式。它将进程的虚拟地址空间划分为多个段，然后将每个段再划分为多个页面。

段页式存储管理方式的优点：

1. 可以兼具段式存储管理方式和页式存储管理方式的优点，既能够体现程序的逻辑结构，又能够提高内存利用率。
2. 分页可以减小内存碎片，有效提高了内存的使用率。
3. 不同的段可以分别采用不同的分页方式，用于不同的内存管理需求，灵活性更高。
4. 可以避免页式存储管理方式由于过多的交换页面导致的性能下降问题。

段页式存储管理方式的缺点：

1. 管理复杂度高，需要维护多级页表和多级段表，增加了内存访问的开销。
2. 物理内存分配过小，可能会导致分配不足的问题，这需要系统支持动态内存分配。
3. 段与段之间的地址空间可能不连续，需要额外的机制来处理段与段之间的访问。

总的来说，段页式存储管理方式是在分段和分页的基础上结合起来的一种存储管理方式，既具有段式存储方式的管理优点，又避免了页式存储管理方式的管理缺陷。但是由于其管理复杂度高，因此需要在实际应用中进行权衡和选择。

8 简述LRU算法及其实现方式。⭐⭐⭐⭐

LRU（Least Re