内存管理

主要包括虚地址、地址变换、内存分配和回收、内存扩充、内存共享和保护等功能。
连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式

内存分配的方式

单一连续存储管理

系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。
其特点是，最简单，适用于单用户、单任务的操作系统。
CP／M和 DOS 2．0以下就是采用此种方式。这种方式的最大优点就是易于管理。

分区式存储管理

分区式存储管理是把内存分为一些大小相等或不等的分区，
操作系统占用其中一个分区，其余的分区由应用程序使用，
每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，
但难以进行内存分区的共享。

固定分区

固定式分区的特点是把内存划分为若干个固定大小的连续分区。
分区大小可以相等：这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等：

动态分区

动态分区的分区分配就是寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，
则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，
而另一个分区为余下部分并标记为“空闲”。分区分配的先后次序通常是从内存低端到高端。
动态分区的分区释放过程中有一个要注意的问题是，将相邻的空闲分区合并成一个大的空闲分区。

最先适配法(nrst-fit)：按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。
该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区，每次分配时查找时间开销便会增大。

下次适配法(循环首次适应算法 next fit)：按分区在内存的先后次序，从上次分配的分区起查找(到最后{区时再从头开始}，
找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大空闲分区不易保留。

最佳适配法(best-fit)：按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。
从个别来看，外碎片较小；但从整体来看，会形成较多外碎片优点是较大的空闲分区可以被保留。

最坏适配法(worst- fit)：按分区在内存的先后次序从头查找，
找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，当对内存需求较大的进程需要运行时，其要求不易被满足。

伙伴系统

固定分区和动态分区的折中方法
当需要为进程分配一个长度为n的存储空间时:
首先计算一个 i 值，使 2 ^ (i－1) < n ≤ 2 ^ i，
然后在空闲分区大小为2 ^ i的空闲分区链表中查找。
若找到，即把该空闲分区分配给进程。
否则，表明长度为2 ^ i的空闲分区已经耗尽，则在分区大小为2 ^ (i ＋ 1)的空闲分区链表中寻找。
若存在 2 ^ (i ＋ 1)的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于配，
而把另一个加入分区大小为2 ^ i的空闲分区链表中。
若大小为2 ^ (i ＋ 1)的空闲分区也不存在，则需要查找大小为2 ^ (i ＋ 2)的空闲分区， 若找到则对其进行两次分割：
第一次，将其分割为大小为 2 ^ (i ＋ 1)的两个分区，一个用于分配，一个加入到大小为 2^(i ＋ 1)的空闲分区链表中；
第二次，将第一次用于分配的空闲区分割为 2^i的两个分区，一个用于分配，一个加入到大小为 2^i的空闲分区链表中。
若仍然找不到，则继续查找大小为 2 ^ (i ＋ 3)的空闲分区，以此类推。

内存紧缩（地址变换）

将各个占用分区向内存一端移动, 然后将各个空闲分区合并成为一个空闲分区。

覆盖技术

引入覆盖 (overlay)技术的目标是在较小的可用内存中运行较大的程序。
这种技术常用于多道程序系统之中，与分区式存储管理配合使用。

交换技术

交换 (swapping)技术在多个程序并发执行时，可以将暂时不能执行的程序（进程）送到外存中，从而获得空闲内存空间来装入新程序（进程），
或读人保存在外存中而处于就绪状态的程序。交换单位为整个进程的地址空间。交换技术常用于多道程序系统或小型分时系统中，
因为这些系统大多采用分区存储管理方式。与分区式存储管理配合使用又称作“对换”或“滚进／滚出” (roll-in／roll-out)。
暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），
而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，
并将该进程送到就绪队列（换入swap in）。

内存分配

页式和段式存储管理

地址空间：将源程序经过编译后得到的目标程序，
存在于它所限定的地址范围内，这个范围称为地址空间。地址空间是逻辑地址的集合。

存储空间：指主存中一系列存储信息的物理单元的集合，
这些单元的编号称为物理地址存储空间是物理地址的集合。

根据分配时所采用的基本单位不同，可将离散分配的管理方式分为以下三种：
页式存储管理、段式存储管理和段页式存储管理。其中段页式存储管理是前两种结合的产物。

页式存储管理

将程序的逻辑地址空间划分为固定大小的页(page)，
而物理内存划分为同样大小的页框(page frame)。
程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。
该方法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。
在页式存储管理方式中地址结构由两部构成，前一部分是页号，后一部分为页内地址w（位移量）

没有外碎片，每个内碎片不超过页
一个程序不必连续存放。
便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。

页式管理的数据结构

在页式系统中，指令所给出的地址分为两部分：逻辑页号和页内地址。
原理：
CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，
将物理页框号与页内地址相加形成物理地址
逻辑页号，页内偏移地址－>查进程页表，得物理页号－>物理地址

若给定一个逻辑地址为A，页面大小为L，则
页号P=INT[A/L]，页内地址W=A  MOD  L
物理地址：物理块号 * 页面大小+ 页内偏移= 28683

段式存储管理

页面是主存物理空间中划分出来的等长的固定区域。分页方式的优点是页长固定，因而便于构造页表、易于管理，且不存在外碎片。
但分页方式的缺点是页长与程序的逻辑大小不相关。例如，某个时刻一个子程序可能有一部分在主存中，另一部分则在辅存中。
这不利于编程时的独立性，并给换入换出处理、存储保护和存储共享等操作造成麻烦。

另一种划分可寻址的存储空间的方法称为分段。段是按照程序的自然分界划分的长度可以动态改变的区域。
通常，程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中，并且每个程序可以有多个相同类型的段。

作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例程序段、数据段等。每个段都从0开始编址，
并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。
整个作业的地址空间是二维的。

每个程序设置一个段表，段表的每一个表项对应一个段，每个表项至少包括三个字段：
有效位（指明该段是否已经调入主存）、段起址(该段在实存中的首地址)和段长（记录该段的实际长度）。

绝对地址=根据段号找到段表中的起始地址+段内地址 (如果段内地址超过限长则产生“地址越界”程序性中断事件达到存储保护)

题目

已知逻辑空间地址为2^m个字节（也就是说逻辑地址的长度是m位），
已知页大小是2^n字节。那么一共可以有2^(m-n)个页。
因此页码部分会占m-n位，之后的n位，用来存储页偏移。


举个例子， 页大小为4B，而逻辑内存为32B（8页），
逻辑地址0的页号为0，页号0对应帧5，
因此逻辑地址映射为物理地址5*4+0=20。逻辑地址3映射物理地址5*4+3=23。
逻辑地址13(4*3+1，页号为3，偏移为1，因为帧号为5)，映射到物理地址21。
13 / 4 = 3
13 mod 4 = 1
5 * 4 + 1 = 21

页式的逻辑地址是连续的，段式的逻辑地址可以不连续
页式的地址是一维的，段式的地址是二维的
分页是操作系统进行的，分段是用户确定的

段页式管理中，地址映像表是每个进程一张段表，每个段一张页表