操作系统_离散分配存储管理方式
目录
概述
为进程分配内存空间的两个基本原则——出于直觉:
(1)位置:为程序分配连续的内存空间，亦即按顺序存储在内存中:
(2)尺寸:按程序的大小来确定所分配内存空间的大小;
连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻接的分区中， 便可充分地利用内存空间，而无须再进行“紧凑”。基于这一思想而产生了离散分配方式。根据在离散分配时所分配地址空间的基本单位的不同，又可将离散分配分为以下三种：分段、分页、段页式存储管理方式。
一、分页存储管理方式
1，设计思想概述
分页存储管理将进程的逻辑地址空间分成若干个页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存的物理地址空间分成若干个块（页框），同样也为它们加以编号，如0#块、1#块等等。在为进程分配内存时，以块为单位，将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经 常装不满一块，而形成了不可利用的碎片，称之为“页内碎片”。
Windows系统使用此方法。
2，页面大小
页面过小：虽然一方面可以减小内存碎片，起到减少内存碎片总空间的作用，有利于内存利用率的提高，但另一方面却会造成每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存。此外，还会降低页面换进换出的效率。
页面过大：虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择适中，且页面大小应是2的幂，通常为1 KB~8 KB。
3，页表
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页(0~n)，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
即使在简单的分页系统中，也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容加以保护。当存取控制字段仅有一位时，可用来规定该存储块中的内容是允许读/写还是只读;若存取控制字段为二位，则可规定为读/写、只读和只执行等存取方式。如果有一进程试图去写一个只允许读的存储块时，将引起操作系统的一次中断。如果要利用分页系统去实现虚拟存储器，则还须增设一个数据项。
页表描述
- 以数组形式存放至内存中；（进程开始时，大小就已经固定）
- 页表大小不固定，故不存放在PCB中，只是在PCB中记录页表起始地址；
页表的作用:分页系统的核心数据结构
- 记录程序各页面所在的页框位置;
- 支持进行地址重定位;
- 实现页面访问控制;（地址结构中存取控制字段，但有时一个页面中数据和程序混合存放，而存取控制类型唯一，这也是分页存储的缺点）
- 存储保护:限制程序在操作系统指定的内存区域内运行。（页表长度寄存器）
4，地址机构
5，地址重定位
指令跨页怎么办？
PC+地址重定位
PC指向（逻辑地址中的）下一条指令的地址，每次取出一个字节，并对其进行地址重定位。
如图，一条多字节指令跨1-2两个页面，PC先指向页面1中的指令，进行地址重定位，并将物理地址放入内存，然后PC加一，到达页面2，接着进行地址重定位......。这样便解决了指令跨页的问题。
6，地址变换机构
操作系统调度某个进程到CPU上执行时，需要先布置CPU现场（包括通用寄存器设置，以及PCB中的页表地址寄存器和页表长度寄存器）
性能问题:
访问1次内存变量，涉及2次地址访问:页表+变量（访问内存中的页表，进而获得内存地址；访问内存地址，进而获得变量）
解决办法: 快表
- 设置在CPU内 部;
- 具有并行查找能力;
- 暂存当前正在使用的页表项;
- 尺寸:16-512。可达到90%以上命中率
- 别名:联想存储器(相联存储器) ( associative memory)，Intel术语: TLB( Translation lookaside buffers )
7，页表的存储问题
现代的大多数计算机系统都支持非常大的逻辑地址空间( B~
B)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。
例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即B，页表项占4字节，故一个页面可以存放1K个页表项。然而当一个进程所需页表项超过1K时（当页表项不超过1K时，一个页框可以存放所有页表项，故只需将页框号存放至PCB中即可），便无法满足需求。
我们可以采用这样两个方法来解决这一问题:
①对于页表所需的内存空间，可采用离散分配方式，以解决难以找到一块连续的大内存空间的问题;
②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
这里介绍一下方法一：离散分配方式——多级页表
仍然假设一个页框4KB，每个页表项占4字节，一个页框可容纳1024个页表项。由于页表的大小超过一个页框的大小，所以可以将页表分为若干个小的页表，每个1024个连续页表项占一个页框，并设置外部页表，来指向这些页表（即对页表项的存储也使用分页思想）。
此时地址结构变为：
外层页号确定页表在哪个页框（物理块），找到页框后，再对应页号找到变量在哪个页框，最后根据这个页框+偏移量，找到变量的物理地址。
二、分段存储管理方式
1，分段管理方式的引入
为什么要引入分段存储管理方式，可从下面两个方面说明:
- 一方面是由于通常的程序都可分为若干个段，如主程序段、子程序段A、子程序段B、...数据段以及栈段等，每个段大多是一个相对独立的逻辑单位；
- 另一方面，实现和满足信息共享、信息保护、动态链接以及信息的动态增长等需要，也都是以段为基本单位的。更具体地说，分段存储管理方式更符合用户和程序员多方面的需要。（分页系统中，4K的空间数据、程序混合存放，且只有一种存取方式，不方便进行信息共享）
2，分段
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。（这些分段在内存中的分配类似于动态分区分配的思想，会产生外零头）
例如，有主程序段MAIN、子程序段X、数据段D及栈段S等，如图4-19 所示。每个段都有自己的名字。为了实现简单起见，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因此各段的长度并不相等。
整个作业的地址空间由于被分成多个段，所以呈现出二维特性，亦即，每个段既包含了一部分地址空间，又标识了逻辑关系。其逻辑地址由段号(段名)和段内地址所组成。
- 分段是一段有意义的信息集合;
- 分段的划分由程序员完成;
- 分段的长度不定;
- 指令不存在跨分段情况;
3，地址结构
包括段号和段地址。
在下图地址结构中，允许-一个作业最长有64K个段，每个段的最大长度为64 KB。
4，段表
在前面所介绍的动态分区分配方式中，系统为整个进程分配一个 连续的内存空间。
而在分段式存储管理系统中，则是为每个分段分配一个连续的分区。
进程中的各个段，可以离散地装入内存中不同的分区中。为保证程序能正常运行，就必须能从物理内存中找出每个逻辑段所对应的位置。为此，在系统中，类似于分页系统，需为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。
段表可以存放在一组寄存器中，以利于提高地址转换速度。但更常见的方法是将段表放在内存中。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区。
可见，段表是用于实现从逻辑段到物理内存区的映射的。
段表的作用:分段系统的核心数据结构
- 记录程序各分段所在的内存位置;
- 支持进行地址重定位;
- 实现分段访问控制;
- 存储保护:限制程序在操作系统指定的内存区域内运行。
5，地址变换机构
为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度TL；
在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL,表示段号太大，是访问越界，于是产生越界中断信号。若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。
然后，再检查段内地址d是否超过该段的段长SL。若超过，即d>SL,同样发出越界中断信号。若未越界，则将该段的基址d与段内地址相加，即可得到要访问的内存物理地址。
6，分段与分页的区别
三、段页式存储管理方式
1，基本思想
分页系统：负责解决主存分配问题，内存按页分配;
分段系统：负责解决逻辑地址空间管理问题，按段为应用程序分配逻辑地址空间;
2，地址结构
3，段表与页表
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。
4，地址变化机构
在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问是访问内存中的段表，从中取得页表始址:第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址起形成指令或数据的物理地址: 第三次访问才 是真正从第二次访问所得的地址中取出指令或数据。