存储器历来都是计算机系统的重要部分。

对于计算机而言，存储层次至少分为三层：CPU寄存器、主存、辅存。还可以根据具体功能细分为：寄存器、高速缓存、主存储器、磁盘缓存、固定硬盘、可移动存储介质。寄存器、高速缓存、主存储器、磁盘缓存均属于操作系统存储管理的管辖范围，断电后信息不再存在。低级的固定磁盘和可移动存储介质则属于设备管理的管辖范围，将被长期保存。

在计算机系统的存储层次中，寄存器和主存器又被称为可执行存储器。进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进程访问。但是对辅存的访问则要通过I/O设备实现。对于不同层次的存储介质，由操作系统进行统一管理、回收以及提供在存储层次间数据移动的管理机制。

主存储器简称主存或内存，是计算机系统的主要部件，用于保护进程运行时的程序和数据，也称为可执行存储器。

寄存器具有与处理机相同的速度，故对寄存器的访问速度最快。

高速缓存是现代计算机结构的一个重要部件，它是介于寄存器和存储器之间的存储器。为了缓和内存和处理机速度之间的矛盾。

为了缓和磁盘的I/O与主存的速度不匹配。磁盘缓存并不是实际存在的存储器，而是利用主存中的部分存储空间存放在磁盘读写的信息。主存也可以看做是辅存的高速缓存。

用户程序要在系统中运行，必须现将它装入内存，然后将其转变为一个可以执行的程序。

当计算机系统很小，且仅能运行单道程序时，完全有可能知道程序将驻留在内存的什么位置。此时可以采用绝对装入方 式。程序中所使用的绝对地址既可在编译或汇编时给出，也可由程序员直接赋予。

可适合多道程序环境，但并不允许程序运行时在内存中移动位置。重定位装入程序将装入模块装入内存后，会使得装入模块中所有逻辑地址与实际装入内存的物理地址不同。在装入时对目标程序中指令和数据地址的修改过程成为重定位（静态重定位）。

一个进程被多次换出又被多次换入，应采用动态运行方式。

源程序经过编译后，可得到一组目标模块。链接程序的功能是将这组目标模块以及它们所需要的库函数装配成一个完整的装入模块。在对目标模块进行链接时，根据进行链接的时间不同，可以把链接分为以下三类：

为了将用户程序装入内存，必须为它提供一定大小的内存空间。连续分配方式可分为四类：单一连续分配、固定连续分配、动态分区分配、动态可重定位分区分配

在单道程序中，当时的存储器管理的方式是把内存分为用户区和系统区两个部分，系统区仅对OS使用，它通常放在内存的低址部分。

将分区按其大小进程排队，为之建立一张分区使用表，各表项包括了每个分区的起始地址，大小及状态，由内存分配表依据用户程序的大小检索该表。若未找到大小足够的分区，则拒绝为该用户程序分配内存。

动态分区分配又称为可变分区分配，依据进程的实际需要，动态地位置分配内存空间。涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作三个方面的问题。

为了实现动态分区分配，必须配置相应的数据结构用于描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有两种形式：①空闲分区表，②空闲分区链

为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。

主要操作为：分配内存和回收内存

FF算法要求空闲分区链以地址递增的次序链接。

为了避免地址部分留下许多很小的空闲分区，不再每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，知道找到一个能满足要求的空闲分区。

总是把能满足要求、又最小的空闲分区分配给作业，避免“大材小用”。

总是挑选一个最大的空闲区，以至于存储器中缺乏大的空闲区。

基于顺序搜索的动态分区分配算法比较适用于不太大的系统。

该算法又称为分类搜索法，将空闲分区根据容量大小进行分类，相同容量的所有空闲分区单独设立一个空闲分区链表。第一步确定进程的长度，从索引表中寻找能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配即可。优点是查找效率高。

该算法规定，武林已分配区间或空闲分区，大小均为2的k次幂的形式。时间性能比快速适应算法叉，但是采用了索引搜索算法，比孙旭搜索算法好。

哈希算法就是利用哈希快速查找的优点，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表。

连续分配方式的一个重要特点是，一个系统或用户程序必须被装入一个连续的内存空间中。

访问内存地址是相对地址与重定位寄存器中的地址相加形成的。

动态重定位分区分配算法与动态分区分配算法基本相同，差别在于：这种分配算法中，增加了“紧凑”功能。

对换技术也称为交换技术，最早用于麻省理工学院的分时系统中。

在多道程序环境下，一方面在内存中的某些进程由于某事件尚未发生而被阻塞运行，但却占用了大量空间，甚至有时可能出现在内存中所有进程都被阻塞而无可运行程序；另一方面又有许多作业驻留在外存因内存不足一直驻留在外存上。这是一种资源浪费。“对换”是指把内存中暂存不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把以具备条件的进程或进程所需的程序换入内存。对换是改善内存利用率的有效措施，可以直接提高处理机的利用率和系统的吞吐量。

具有对换功能的OS中，通常把磁盘文件分为文件区和对换区

文件区占用磁盘空间很大部分，是用于存放各类文件。对文件区空间的管理采取离散分离分配方式。

对换空间只占用磁盘空间的小部分，用于存放内存换出的进程。对对换区空间的管理采用连续分配方式，较少考虑外存的碎片问题。

空闲分区表和空闲分区链。空闲分区表包含两项：对换区的首址及大小，分别用盘块号和盘块数代替表示。

对换空间算法的分配与回收与动态分区方式时的内存分配与回收方法雷同。

选择处于阻塞状态或睡眠状态的进程，选择优先级最低的作为换出进程。

先申请对换空间，若申请成功，就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。

对换进程将定时执行换入操作，首先查看PCB集合中所有进程的状态，从中找出“就绪”状态但已换出的进程。

根据离散分配时所分配的地址空间和基本单位的不同，可将离散分配分为以下三种：

分页存储管理将进程的逻辑地址分为若干个页，并未各页加以编号。

减小页面有利于内存利用率的提高，但会导致页表过长，占用大量内存。页面过大会使页内随便增大。

逻辑地址为A，页面大小为L，页号P和页内地址d可按下式求得：P=INT[\frac{A}{L}]，d=[A] mod LP=INT[LA​]，d=[A]modL

在分页系统中，允许将多个页面离散地存储在内存的任一物理块中，为保证进程仍然能正确运行，即能在内存中，找到每个页面所对应的物理块，系统由为每个进程建立了一张页面映像表，简称页表。

该机制的任务是实现从逻辑地址到物理地址的转换。页面映射表的作用就是用于实现从页号到物理号的变化，因此地址变换的任务是借助于页表实现的。

从进程发出制定逻辑地址的有效访问，经过地址变换，到内存中找到相应的实际物理地址单元并取出数据，所需要花费的总时间，成为内存的有效时间。假设访问一次内存时间为t；在基本分页存储管理方式中，有效访问时间为：EAT=t+t=2t；快表分页中为：EAT=a×λ+(t+λ)(1-a)+t=2t+λ-t×a=2t+λ-t×a。上述中，a表示命中率，λ表示快速命中所需要的时间，t表示一次访存需要时间。

现代大多数计算机都支持非常大的逻辑空间，这样的环境下，页表就变得非常大，要占用相当大的内存空间，故每个进程仅仅页表就要占用1MB的空间问题，而且要求连续。这样是不显示的。我们采用两种方法解决这个问题：①对于页表所需要的空间可采用离散分配方式；②只将当前需要的部分页表项调入内存，其余的页表扔驻留在磁盘上，需要时再调入。

为离散分配的页表在建立一张页表，成为外层页表。

对于32位机器，采用两级页表结构是合适的，但对于64位机器，就不合适了。

一般页表的页选项是按页号进行排序的，页表项中的内容是物理编号，而反置表则是为每一个物理块设置一个页表项。

在反置表进行地址变换时，是根据进程识别符和页号，去检索反置页表。

引入分段存储的目的是为了满足用户（程序员）在编程和使用上多方面的要求。

通常，用户把自己的作业按照逻辑关系分为若干段，每个段都从0开始编址，并有自己的名字和长度。因此程序员们都迫切地需要访问的逻辑地址是由段名（段号）和段内偏移量（段内地址）决定的。

实现程序和数据的共享时，是以信息的逻辑单位为基础的。

信息保护是以信息的逻辑单位为基础的，而且经常是以一个过程、函数或文件为基本单位进行保护的。

为了提高内存的利用率，系统只将真正要运行的目标程序装入内存，动态链接在作业运行之前，并不是把所有的目标程序段都链接起来。

作业的地址空间被划分为若干个段，每个段都定义了一组逻辑信息。

分段式存储管理系统中，程序为每个段分配一个连续的分区。段表是用于实现逻辑段到物理内存区的映射的。

相似支出：而且都采用离散分配方式，以消除内存的外零头，提高内存利用率。不同：1. 页是信息的物理单位。2. 页的大小固定是由系统决定的3. 分页的用户程序地址空间是一维的。

分段系统的一个突出有点，是易于实现段的共享。

分页系统以页面为内存分配的基本单位，能有效提高内存利用率。而以内存为基本单位，能够更好地满足用户多方面的需求。段页式存储管理方式具有：便与实现、分段可共享、易于保护、可动态链接等一系列优点，很好地解决内存外部碎片问题。

段页系统的基本原理是分段和分页原理的结合，现将用户程序分为若干个阶段，再把每个段分为若干个页。段页式系统中，其地址结构由段号、段内页号及页内地址三部分组成。段页系统中，实现了从逻辑地址到物理地址的变换，系统需要同时配置段表和页表。

段页式系统中，为了获得一条指令和数据，需要三次防存，第一次找段表，第二次找页表，第三次才是真正地址。

为什么要配置层次式结构存储器

可采用哪几种方式将程序装入内存？它们分别适用于何种场合？

什么是基于顺序搜索的动态分区分配算法？它分为哪几种？

在采用首次适应算法回收内存时，可能出现哪几种情况？应怎样处理这几种情况？

什么是基于索引搜索的动态分区分配算法？它可分为那几种？

令Buddy_k(x)的大小为2^k、地址为x的块的伙伴系统地址，试写出Buddy_k(x)的通用表达式。Buddyk​(x)的大小为2k、地址为x的块的伙伴系统地址，试写出Buddyk​(x)的通用表达式。

f(x)= \begin{cases} x+2^k& \text{x mod $2^{k+1}=0$}\\ x-2^k& \text{x mod $2^{k+1}=2^k$} \end{cases}f(x)={x+2kx−2k​x mod 2k+1=0x mod 2k+1=2k​

为什么要引入对换？对换分为哪几种类型？

为了实现对换，系统用具备那几个方面的内容？

基于离散分配时所用的基本单位不同，可将离散分配分为哪几种？

什么是页表？页表的作用是什么？