操作系统(第三章)----1.内存管理基本概述

一 基本原理和要求

(一) 内存管理的概念

操作系统对内存的划分,动态分配和保护,就是内存管理的基本概念,其主要功能有:

• 内存的分配与回收
• 地址转化
• 内存扩充
• 内存保护

(二) 程序运行的基本原理

逻辑地址和物理地址

从写程序到运行程序

在进行具体的内存管理之前,还需了解程序运行的基本原理

• 编译:编译程序将用户源代码变成成若干目标模块
• 链接:链接程序将一组目标模块及所需的库函数链接在一起,形成一个完整的装入模块
• 装入:由装入程序将装入模块装入内存运行

链接的方式

• 静态链接: 运行之前完成目标模块和库函数的链接,之后不再分开
• 装入时动态链接: 在装入内存时,再将目标模块边装入变链接
• 运行时动态链接: 在程序运行中,需要某个目标模块时,在进行目标模块和库函数的链接.有利于目标模块的共享

装入的方式

• 绝对装入

  在编译时,若指导程序将驻留在内存中的某个位置,则编译程序将产生绝对地址的目标代码.装入程序按照装入模块的地址,将代码放入内存中,且无需修改地址

  ​

  缺点:只适合单道程序环境.

  ​

• 可重定位装入

  在多道环境下,多个模块模块的其实地址通常从0开始,程序中的其他地址都是相对于起始地址的.

  此时应采用可重定位装入,寻找内存中的合适起始位置,将装入模块的逻辑地址+该起始位置,修改

  成新的物理地址,该修改过程称为重定位

  特点: 在一个作业要进入内存时,必须为其分配所有的空间,且分配后,不能再移动

• 动态运行时装入

  装入时不会立即修改逻辑地址为物理地址,而是等到程序运行时再进行修改

  此方法需要借助一个重定位寄存器的支持,来存储内存中该程序的起始物理地址

  特点:允许程序在内存中进行移动

二 内存管理的功能

(一) 内存保护

多道环境下用户的进程不能受其他进程的影响,也即其他进程不能直接访问当前进程所占有的内存

因此,需要采取一定策略防止 内存越界的现象发生,以保证进程之间互补干扰

方法一

方法二

(二 )内存扩充

覆盖和交换技术是多道程序环境下内存扩充的两种基本方式

覆盖技术

• 思想:

由于程序 运行时并不会访问程序及数据的每个部分,因此可将程序划分成多个部分,将用户空间也划分成一个

固定去和若干个覆盖区.将活跃部分的程序放在固定区,

其余部分,若即将访问,就调入覆盖区,其他的放在外村中.

• 特点:

不必将程序一次性调入内存

交换技术

• 思想:

调出:将处于等待状态的进程移出到辅存中,把内存空间腾出来

调入:将准备好禁止CPU运行的程序从辅存移到内存中

CPU调度的中级调度算法采用的就是交换技术

总结

交换技术主要在不同进程之间进行,而覆盖则用于同一个进程中

显然,交换技术更适合多道程序环境

(三) 内存的分配与回收

内存的分配分为:

• 连续内存分配
• 非连续内存分配

下面我们来总结这两大类的分配方式

3. 连续内存分配

连续分配是指为用户进程分配一个连续的空间

(一)单一连续分配

• 将内存划分为系统区和用户区,每次只装入一道程序

(二) 固定分区分配

• 为了能在内存中装入多道程序,出现了固定分区分配,即将用户空间划分成大小固定的若干内存区,每块

  内存区装入一道程序

• 划分方式为:

  • 分区大小相等
  • 分区大小不相等

• 分区大小相等: 缺乏灵活性,但适合用于控制多个相同对象的场景

• 分区大小不相等:增加了灵活性,但是可能产生内存碎片(也即一个程序可能只有3m,但是却占据了5M的内存区)

• 分区表:操作系统通过建立一张分区表来说明分区,

需要内存分配时,通过申请的内存大小检索该表,获取未分配的区域

(三) 动态分区分配(可变分配)

这种方式不会事先划分内存区域,而是在程序装入时动态划分.并使分区的大小刚好适应

程序的大小,因此,这种方式下分区的大小和数目是可变的

(四) 四种动态分区分配算法

• 首次适应算法（First Fit）：

  算法思想：将空闲分区链以地址递增的顺序连接；在进行内存分配时，从链首开始顺序查找，直到找到一块分区的大小可以满足需求 时，按照该作业的大小，从该分区中分配出内存，将剩下的空闲分区仍然链在空闲分区链中。

​

​ 优点：高址部分的大的空闲分区得到保留，为大作业的内存分配创造了条件；

​ 缺点：（1）每次都是优先利用低址部分的空闲分区，造成低址部分产生大量的外碎片。

​ （2）每次都是从低址部分查找，使得查找空闲分区的开销增大；

• 循环首次适应算法（Next Fit）

算法思想：分配内存时不是从链首进行查找可以分配 内存的空闲分区，而是从上一次分配内存的空闲分区的下一个分区开始查找，直到 找到可以为该进程分配内存的空闲分区。

​

优点：（1）使得空闲分区分布更加均匀；

​ （2）空闲分区的查找开销小；

缺点：高址部分的大空闲分区被分小，使得大作业进入无法分配内存；

• 最佳适应算法（Best Fit）

  算法思想：将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。每次从链首进行查找合适的空闲分区 为作业分配内存，这样每次找到的空闲分区是和作业大小最接近的，所谓“最佳”.

​

​ 优点：第一次找到的空闲分区是大小最接近待分配内存作业大小的；

​ 缺点:产生大量难以利用的外部碎片。

• 最坏适应算法（Worst Fit）

算法思想：与最佳适应算法刚好相反，将空闲分区链的分区按照从大到小的顺序排序形成空闲分区链，每次查找时只要看第一个空闲分区是否满足即可。

​

优点：效率高，分区查找方便；

缺点：当小作业把大空闲分区分小了，那么，大作业就找不到合适的空闲分区。

四 非连续内存分配

非连续指可将作业分散到内存中的多个位置

(一) 分页管理

连续分配内存方式会形成许多“碎片”，通过紧凑的方式将碎片拼接成一块大的空间，但是拼接过程系统开销太大。如果允许将一个进程直接分散地装入到许多不相邻的分区中，那么就不需要再进行“紧凑”。基于这一思想而产生了离散分配方式。如果离散分配的基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式。

在分页管理方式中，如果不具备页面对换功能（将处于阻塞状态且优先级低的进程对换到外存），则称为基本的分页存储管理方式，或称为纯分页存储管理方式，它不具有支持实现虚拟存储器的功能，它要求把每个作业全部装入内存后才能运行。

1、页面与页表

1.1、页面

a)、页面和物理块

分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或者页，并为各页加以编号0、1、2…。相应地，把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框，也加以编号0、1、2…。在为进程分配内存时，以块为单位将进程中的若干个页面分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片——“页内碎片”。

b)、页面大小

在分页系统中的页面其大小适应中。页面若太小，一方面虽然可使内存碎片减小，从而减小了内存碎片的总空间，有利于提高内存利用率，但是另一方面也会使每个进程占用较多的页面，导致进程页表过长，占用大量内存，反而降低页面换进换出的效率。然而如果选择的页面较大，虽然可以减小页表的长度，提供页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择适中，且页面大小应该是2的幂，通常为512B~8KB。

1.2、地址结构

分页地址中的地址结构如下：

0_{11位为页内地址，即每页的大小为2^12=4KB；12}31位为页号，地址空间最多允许有2^20=1M页。

对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，每页的大小为L，则页号P=A/L和页内地址d=A%L。

1.3、页表

在分页系统中，允许将进程的各个页离散地存储在内存不同的物理块中，但系统应该保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。系统又为每个进程建立了一张页表，其记录着相应页在内存中对应的物理块号。进程在执行时，通过查找页表找到内存中对应的物理块号。可见，页表的作用的实现从页号到物理块号的地址映射。

2、地址变换机构

为了能将用户地址空间中的逻辑地址 变换为内存空间的物理地址，在系统中必须设置地址变换机构。其基本任务是实现从逻辑地址到物理地址的转换。即将逻辑地址中的页号转换为内存中的物理块号，借助页表来实现。

2.1、基本的地址变换机构

页表的功能可以由一组专门的寄存器来实现。一个页表项用一个寄存器。由于寄存器成本高，数量少，因此页表大多驻留在内存中。在系统中只设置一个页表寄存器PTR(Page-Table Register)，在其中存放页表在内存的起始地址和页表的长度。平时，进程未执行时，页表起始地址和页表长度是存放在本进程的PCB中，当调度程序调度该进程时，才将其放入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。

具体如何转化呢?

以一道题为例子:

(二) 分段管理

引入分段存储管理方式的目的：满足程序员在编程和使用上多方面的要求。这种存储管理方式已经成为当今所有存储管理方式的基础。

1、分段存储管理方式的引入

主要满足用户和程序员以下需求：

1)、方便编程

用户把自己的作业按照逻辑管理划分为若干段，每个段都是从0开始编址，并有自己的名字和长度。因此，希望要访问的逻辑地址是由段名（段号）和段内偏移量（段内地址）决定的。

LOAD1，[A] | ;//将分段A中D单元内的值读入寄存器1

STORE1，[B] | ;//将寄存器1的内容存入B分段的C单元中

2)、信息共享

在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。。比如共享某个例程和函数。分页系统中的页只是存放信息的物理单位（块），并无完整的意义，不便于实现共享；然而段却是信息的逻辑单位。由此可知，为了实现段的共享，希望存储管理能与用户程序分段的组织方式相适应。

3)、信息保护

4)、动态增长

有些段，会随着程序的使用不断增长。而事先又无法确切地知道数据段会增长到多大。

5)、动态链接

动态链接是指在作业运行前，并不把几个目标程序段链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中有需要调用某段时，才将该段调入内存并进行链接。可见动态链接也要求以段作为管理的单位。

2、分段系统的基本原理

2.1、分段

在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D及栈段S等。

在该地址结构中，允许一个作业最长有64K个段，每个段的最大长度为64KB。

分段方式已得到许多编译程序的支持，编译程序能自动地根据源程序的情况而产生若各个段。

2.1、段表

在动态分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存不同的分区中。为了使程序能正常运行，也能从物理内存中找出每个逻辑段所对应的位置，应像分页那样，在系统中为每个进程建立一段映射表，简称“段表”。每个段在表中占有一个表项。其中记录了该段在内存中的起始地址（基址）和段的长度。段表可以存放在一组寄存器中，以提高访问速度，但更常见的是将段表放在内存中。

在配置了段表后，执行中的进程可通过查找段表找到每个段所对应的内存区。可见段表是用于实现从逻辑段到物理内存区的映射：

2.3、地址变换机构

2.4、分页和分段的主要区别

a)、页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；段则是信息的逻辑单位，它含有一组其意义相对完整的信息，分段的目的是为了能更好地满足用户的需要。

b)、页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

c)、分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址是，即需给出段名，又需给出段内地址。

3、信息共享

在分段系统的允许若干个进程共享一个或多个分段，容易实现对段的保存和共享。

可重入代码又称为“纯代码”，是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何的改变。在每个进程中，都必须配以局部数据区，把在执行中可能改变的部分拷贝到该数据区，这样程序在执行时，只需对数据区中的内容进行修改，并不去改变共享的代码，这时的可共享代码级成为可重入码。

(三).段页式存储管理方式

3.0 分段,分页的优缺点

3.1、段页式基本原理

先分段，在段内进行分页，为每一个段赋予一个段名。以下展示出了一个作业地址空间的结构。该作业有三个段，页面大小4KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成。

3.2、地址变换过程

为了方便段页式系统中地址变换的实现，需配置一个段表寄存器，其中存放段表起始地址和段表长TL。比较段号与TL是否越界，从段表寄存器中获取段表始址找到段表，根据段表内的页表始址找到对应的页表，在根据页表的存储块找到内存中的物理块，从而获取物理地址。

段页式系统中，为了获得一条指令或数据，须三次访问内存：

①　访问内存中的段表，从中取得页表始址

②　访问内存中的页表，从中取出该页所在的物理块号，并与页内地址形成物理地址

③　访问真正从第二次访问所得的地址中，取出指令或者数据

多次访问内存，执行速度降低，因此在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可以从中得到相应页的物理块号，用来与页内地址一起形成物理地址；若未找到匹配表项，则仍需要再三次访问内存。