可变分区内存管理 | 操作系统

目录

• 可变分区内存管理 | 操作系统


• 动态内存分配算法(连续内存)
  
  
  
  • 首次适应算法(FF)
  
  
  • 循环首次适应
  
  
  • 最优适应算法(BF)
  
  
  • 最坏适应算法(WF)
  
  
  • 快速适应算法
  
  
  • 分配算法对比分析
  
  
  
  


• 可变分区内存管理(连续内存)
  
  
  
  • 地址转换与内存保护
  
  
  • 伙伴系统
  
  
  
  


• 非连续内存分配分式
  
  
  
  • 页式存储管理
    
    
    
    • 页式存储管理的基本原理
    
    
    • 页式存储管理的内存的分配与回收
    
    
    • 快表
    
    
    
    
  
  
  
  


• 多级页表
  
  
  
  • 哈希页表
  
  
  • 倒排页表
    
    
    
    • 80x86的硬件分页机制
    
    
    
    
  
  
  
  
  
  


• 段式存储管理的基本原理
  
  
  
  • 逻辑地址空间分段
  
  
  • 段式存储管理的地址转换和内存保护
  
  
  • 段地址转换过程
  
  
  • 80x86 CPU的分段
  
  
  
  


• 段页式存储管理


• 分段和分页的比较


• null

操作系统的内存管理——Is——Interesting——?？

动态内存分配算法(连续内存)

这里的连续内存所说的连续有否指的是一个进程在内存中的数据存储是否是连续的。

首次适应算法(FF)

将所有空闲分区按照地址递增的次序链接，在申请内存分配时，从链首开始查找，将满足需求的第一个空闲分区分配给作业。

循环首次适应

从上次分配分区后的位置开始查找，找到第一个满足作业大小的空闲分区并分配

将所有空闲分区按照地址递增的次序链接，在申请内存分配时，总是从上次找到的空闲分区的下一个空闲分区开始查找，将满足需求的第一个空闲分区分配给作业

优点:

空闲分区的分布更加均匀，查找空闲分区所需要的时间更短

缺点:

"碎片"问题

剩余一些小片的空间无法使用, 这些不可用的碎片空间

最优适应算法(BF)

将所有空闲分区按照从小到大的顺序形成空闲分区链，在申请内存分配时，总是把满足需求的、最小的空闲分区分配给作业

挑选一个能满足作业要求的最小分区，以避免分割更大的分区，使大作业比较容易装入

把空闲区按长度递增排列，从最小的分区开始查找，直到找到满足要求的分区为止。回收分区时必须对空闲区链重新排列

优点:

缺点:

1. 分区一般都是无法正好满足作业的内存要求，分割后剩下的空闲区很小，成为"碎片"。碎片越来越多, 查找时间越来越长导致效率降低。

   
   



2. 小空闲区占据空闲区表的开始部分，增加查找的时间开销

   
   

最坏适应算法(WF)

挑选最大的分区给作业使用，可使分割后剩下的空闲区仍然比较大，仍然能满足以后的作业装入要求，减少内存中"碎片"

把空闲区按长度递减排列，使算法的查找效率很高。

优点:

• 对中、小作业有利

缺点:

• 随着系统的运行，大空闲区会不断减少，大的作业可能无法装入内存

快速适应算法

把空闲区按长度归类，为每种长度的空闲区设立单独的空闲区链表。系统中存在多个空闲分区链空闲分区表第1项指向2KB的空闲区链表,第2项指向4KB的空闲区链表，第3项指向8KB......

空闲区链表，根据作业大小查找空闲分区表，找到能够容纳它的最小的空闲分区链表的起始指针，再从相应的空闲分区链中取第一个空闲分区

优点:

• 查找迅速，找到的是能容纳它的最小空闲区，能保留大的空闲区

缺点:

• 回收分区较困难，算法复杂，系统开销大

分配算法对比分析

1. 从搜索速度及内存利用率来看，最先适应分配算法、循环首次适应分配算法和最优适应算法比最坏适应算法性能好空闲区按从小到大排列， 最先适应分配算法 = 最优适应分配算法。


2. 空闲区按从大到小排列，最先适应分配算法=最坏适应分配算法。


3. 空闲区按从小到大排列，最先适应分配算法能尽可能使用低地址区，从而在高地址空间有较多较大的空闲区来容纳大的作业。


4. 循环适应分配算法会使存储器空间得到均衡使用。


5. 最优适应分配算法的内存利用率最好;但是可能导致空闲区分割下来的部分很木，通常性能是最差的。

可变分区内存管理(连续内存)

地址转换与内存保护

动态重定位:地址转换由硬件机构完成。设置两个寄存器:

1. 基址寄存器


2. 限长寄存器

CPU通过逻辑地址访问内存可能出现的情况：

1. 逻辑地址<限长值:逻辑地址+基址寄存器= =绝对地址


2. 逻辑地址>限长值:作业欲访问的内存地址超出了所分得的内存区域，禁止访问，起到存储保护的目的

多道程序系统中，只需要一对基址/限长寄存器:

​ 当作业等待时，操作系统把基址限长寄存器的内容随同该作业的其它信息(如通用寄存器的内容) - -起保存起来。当作业被选中时,则把选中作业的基址限长值再送入基址限长寄存器最早的巨型。

系统运行一段时间后，产生许多碎片:每-块碎片都不能满足某一作业的内存请求，而所有碎片的总和却能满足。

紧凑技术：

• 一 把内存中的作业改变存放区域，使分散的空闲区能够汇聚成-个大的空闲区，从而有利于大作业的装入

缺点(代价很大)：

• 增加系统开销，且不是任何时候都能对程序进行移动v当外围设备正在与内存进行信息交换时，会按照已经确定的内存绝对地址完成信息传输，所以不能移动

伙伴系统

内存块大小一般为2k个字,且满足L≤K≤U,其中:

2^L表示分配的最小块大小; 2^U表示分配的最大块大小，通常为整个内存大小

下面是伙伴系统的一次内存分配过程示例：

在这里有一个原则：

需要相邻的两个空闲空间大小相等的时候才会合并, 否则不会合并而是继续保持独立的空闲状态， 我们可以通过二叉树的方式实现：

请求B释放后的伙伴关系的二二叉树表示。叶子节点表示内存中的当前分区，如果两个伙伴都是叶子节点，则至少一个被分配出去;否则，将合并成一个更大的块

分区内存管理的共同特点:连续性

每道程序都要占用一块连续的存储区域。当系统运行一-段时间后，会产生许多“碎片"。虽然紧凑技术能够将“碎片”再利用，但系统开销非常大所以一般不会使用紧凑技术。

非连续内存分配分式

非连续内存分配方式/离散分配方式:将进程逻辑地址空间划分成多个子部分，以子部分为单位装入物理内存，子部分可以分布在非连续的内存块上，以充分利用内存

主要包括:

1. 页式存储管理(想到了脏牛和DirtyPipe提权漏洞)
   
   
   
   1. 就是单纯以一个固定的大小分割程序数据, 不考虑程序的结构
   
   
   
   


2. 段式存储管理
   
   
   
   1. 考虑了程序的系统结构, 数据分片的截断点的选择是有一定规律的
   
   
   
   

页式存储管理

页(page)页面:

• 逻辑地址空间划分为大小相等的区，并对页从0开始编号

物理块/块(block)/页框/帧(frame) :

• 将物理内存划分成与页大小相等的区，并从0开始编号。

  
  



• 块大小通常取2的幂次

  
  



• 块的大小由计算机硬件决定，页的大小由块的大小决定, 例如:

  
  
  
  
  • Intel 80386系列处理器系统和Motorola 68030处理器系统的块的大小为4096B(4K)
  
  
  • IBM AS/400的块的大小为512B
  
  
  
  

页式存储管理的基本原理

内存分配的基本单位一页， 当程序装入时，按页为单位,每一-页装入-个块中

进程的最后一页经常装不满一块，在最后-块形成不可利用的“内部碎片"

逻辑地址:

用页号和页内偏移表示

• 32位系统逻辑地址是32位，如果每页大小4096B,那么页内偏移占用低12位。

  剩余的高20位表示页号，最多允许2^20 (1M) 个页面。页面编号从0到2^20-1。

  
  



• 页内偏移

  
  

页式存储管理的内存的分配与回收

• 操作系统为每个进程建立一-张页表一逻辑地址中的页号与内存中物理块号的对应关系


• 页式存储管理系统中存在一-张作业表一登记作业的页表始址和长度

页表的创建由进程进行，创建后得到一个带有属性标记的页表

页表的管理由操作系统进行，操作系统通过作业表对页表进行管理，每个进程对应一个页表。

从逻辑内存到物理内存之间按通过页表建立映射关系：

在这里D进程的数据就是通过页存储的方式拆分后进行了在内存中的不连续存放

通过例子理解一下：

但是实际上计算机的消耗最大的就是触发运算，同时我们取得页号和页内偏移地址的方式已经在前面给出了：

例如在32位的操作系统我们可以取前面的低10位和高22位分别表示页内偏移和页号

页表表项中还有存取控制字段，实现对物理块的保护，比如:

P: 是否在内存

M: 修改位

• 

  页表长度由进程长度决定，每个内存中的进程都会建立一张页表

  
  

一个处理器只需要一 个页表寄存器:

进程处于不运行状态，页表的起始地址和长度存放在PCB中。进程被调度运行时，系统才将页表起始地址和长度装入页表寄存器

地址转换需硬件_ (地址转换机构)完成

1. 地址转换机构自动从逻辑地址的低地址部分得到页内偏移,从高地址部分得到页号

   
   



2. 将页号与页表寄存器中的页表长度比较，如果页号2页表长度，表示地址已经越界，产生地址越界中断入

   
   



3. 否则，从页表寄存器得到负表在内存中的起始地址。页号*页表项长度+页表的起始地址=页表项在页表中的位置，查到物理块号

   
   



4. 将页内偏移装入物理地址寄存器的低位字段，将物理块号装入物理地址寄存器的高位字段，即物理地址

   

   
   

考虑效率:

• 两次访问内存:
  
  1.根据逻辑地址访问内存中的页表得到物理地址
  
  2.根据物理地址再去访问内存得到需要的指令或数据


• 所以我们引入快表（就当于一个存放页表的Cache）

快表

为提高速度，根据局部性原理，可将最近访问过的页表项存放在高速缓存中，称为快表(TLB, TranslationLookaside Buffer,转换后备缓冲区)

• 相联存储器(associative memory) : 一个专用的高速缓冲存储器来存放页表的一部分，造价高，故一般容量小，例如8~1024个单元


• 相联存储器工作周期与处理器的工作周期接近，所以访问快表远远快于访问内存中页表

借助快表，物理地址形成的过程:

1. 按逻辑地址中的页号查快表，若在快表中(命中)则由块号和块内偏移形成物理地址;否则，查内存中的页表形成物理地址，同时将该页登记到快表中


2. 当快表填满，又要登记新页时，则需在快表中
   
   按一定策略淘汰旧的登记项 (页面置换算法)

en....这个和计组的计算机组成原理里面讲的Cache差不多

如果我们命中那么CPU：

• 访问一次相联存储器 + 访问内存读取数据

CPU未命中那么CPU：

• 访问一次相联存储器 + 一次内存读取页表 + 访问内存读取数据

虽然我们未命中的时候会花费更多的时间， 但是整体上结果实践我们建立快表的方式是明显可以提高效率的(因为命中情况所减少的总时间多于未命中的情况多花费的总时间)

特点

整个系统只有一个相联存储器，只有占用CPU的进程才能占有相联存储器

快表是动态变化的，所以让出相联存储器时应把快表保护好以便再执行时使用。

当一道程序占用处理器时，除设置页表寄存器外还应将它的快表送入相联存储器

页式管理有利于实现作业共享程序和数据:编译程序、编辑程序、解释程序、公共子程序、公用数据等，共享信息在内存中只要保留一一个副本V假定系统有40个用户，每个用户执行一个文本编辑器。

例如:

1. 如果编辑器有150KB代码和50KB数据，共需要8000KB


2. 如果代码段是可重入代码，则需要空间21 50KB

共享须解决信息的保护问题:

1.页表中增加标志位:读/写;只读;只可执行;不可访问等，在执行时进行核对

2.要想向只读块写入信息则指令停止，产生中断

多级页表

为了能够快速查找页表页在内存中的物理块号，为页表页再设计一个地址索引表，即页目录表

系统将页表分为两级:

1. 一级为页目录表，


2. 二级为页表页。

页表页中的每个表项记录了每个页的页号和对应的物理块号。

优点:

1. 减小了内存存放的页表数据大小

●

二级页表的逻辑地址被划分为三部分:

页目录、页表页、页内偏移

1. 页目录表寄存器保存当前运行进程的页目录表(一级页表)在内存中的起始地址


2. 页目录表在内存中的起始地址+页目录号(即需要查找的页表某页在页目录中的编号),得到页表页的物理块号


3. 通过页表页的物理块号得到该页表页，由页表页号(某页在页表页中的编号)查询该页表页项,得到对应的物理块号


4. 将该物理块号加上页内偏移,得到物理地址

二级页表地址变换获取内存信息需要三次访问内存:

1. 访问页目录表


2. 访问页表页


3. 通过物理地址获取内存信息

为节约时间，可采用快表

当逻辑地址的位数更多时，系统会采用三级、四级,甚至更多级的页表。级别更多，灵活性越大，管理也更复杂

对于64位系统,

多级页表能满足需求吗?

如果每 个页表条目为4B,第二级外部页表: 大小仍然需要232x4B

页表的缺陷:页表的大小与虚拟地址空间的大小成比例增长)

解决方案:

1. 哈希页表


2. 倒排页表(Inverted Page Table) - 一PowerPC、 IA-64. 上广泛应用

哈希页表

逻辑地址:

• p为逻辑页号. d为页内偏移

哈希表内

• q和p为逻辑页号


• r和s为块号(相当于一个页的起始地址)

每个进程都有一个哈希表

因为哈希函数多对一所以哈希表内结构为链式结构, 所以这个哈希表可能会很大

倒排页表

上面的都是从逻辑地址找到物理地址

●减少存储每个页表所需要的内存空间，但当引|用页时增加了查找页表所需要的时间

●由于页表按照物理地址排序，而查找按照虚拟地址排序，因此可能导致需要查找整个表来寻求匹配

80x86的硬件分页机制

●80386开始支持分页:通过设置cr0寄存器的PG标记启用;

PG=0,虚拟地址=物理地址

●采用二级页面，页面大小为4KB(2^12) :



●正在使用的页目录的物理地址存放在控制寄存器cr3中(也就是页表寄存器)

IA-32体系结构只使用了两级页表; 64位体系结构(Alpha、 Sparc64、 IA-64等)地址空间比较大，需要三级或四级的页表

段式存储管理的基本原理

逻辑地址空间分段

• 程序往往由一个程序段、若干子程序数组段和工作区段
  
  所组成，每个段都从"0"开始编址，段内地址是连续的

  
  



• 按照程序的逻辑段结构，将程序按段为单位来分配内存,
  
  一段占用一 块连续的内存地址空间，段之间不需要连续

  
  

• 页式存储管理中，如何分页对用户不可见，连续的逻辑地址空间根据内存物理块的大小自动分页

  
  



• 段式存储管理中，由用户决定逻辑地址如何分段。用户在编程时，每个段的最大长度受到地址结构的限制,每个程序中允许的最多段数也可能受到限制

  
  



• PDP-11/45的段址结构为:
  
  段号占3位，段内地址占13位，也就是一个作业最多可分8段，每段的长度最大8K字节

  
  

1. 操作系统为每个作业创建一-张段表一 有段号、 段长、段在内存的起始地址和存取控制字段等信息


2. 段式存储管理系统还包括一 张作业表一 将作业的段表进行登记

内存分配类似于可变分区内存分配算法可以参照可变分区分配算法来设计，如最先适应、最优适应或最差适应法等

段地址转换借助于段表完成。段表寄存器用来存放当前运行作业的段表始址和长度，查询段表得到每段在内存的起始地址段的起始地址+段内偏移=物理地址

段式存储管理的地址转换和内存保护

段地址转换过程

1. 将逻辑地址由地址转换机构分为段号和段内偏移


2. 查询段表寄存器得到段表在内存的起始地址


3. 查询段表，得到该段在内存的起始地址和段长


4. 将段内地址与段长比较,如果段内地址大于段长，则发出越界中断;否则合法
   
   段在内存的起始地址+段内地址 = 内存物理地址


5. 借助于快表(保存最近使用过的段表项)，可以更快地实现地址转换

• 段共享/共享分区:计算机系统要提供多对基址限长寄存器。几个作业共享的例行程序可放在一个公共分区中， 只要让共享部分有相同的基址限长值

  
  



• 由于段号仅仅用于段之间的相互访问，段内程序的执行和访问只使用段内地址，因此不会出现页共享时出现的问题,对数据段和代码段的共享都不要求段号相同

  
  



• 对共享区的信息必须进行保护，如规定只能读出不能写入，欲想往该区域写入信息时将遭到拒绝并产生中断

  
  

80x86 CPU的分段

实模式采用段式存储器管理或单一连续存储器管理，不启用分页机制，只能寻址1MB地址空间(2^20) -- DOS

虚模式(保护模式)采用三种内存管理方式:段式、页式和段页式虚拟存储器管理 -- Linux和Windows

虚拟模式是在保护模式下的实模式的仿真，允许多个8086应用程序在386以上CPU中运行

段页式存储管理

在段式存储管理的基础上实现分页式存储管理，是目前应用最多的一-种存储管理方式

段页式存储管理的基本原理:

1.程序根据自身的逻辑结构划分成若干段

2.内存的物理地址空间划分成大小相等的物理块

3.将每- -段的线性地址空间划分成与物理块大小相等的页面，形成段页式存储管理

4.逻辑地址分3个部分: 段号、段内页号和页内位移.

对用户而言，虚拟地址由段号s和段内位移d'组成。用户看不到分页，操作系统自动把d"解释成两部分:段内页号p和页内位移d,即 d'= p * 块长 + d

操作系统: 分页

程序: 分段

内存中同时有段表和页表,也同时有段表和页表的快表

通过段表寄存器找到页表, 页表寄存器找到页起始地址, 最后通过起始地址加上页内偏移量找到数据地址

需要三次内存访问(不考虑快表):

1. 段表寄存器


2. 页表寄存器


3. 访问数据内存取出数据

分段和分页的比较

• 段是信息的逻辑单位，由源程序的逻辑结构决定，用户可见，段长可根据用户需要来规定，段起始地.址可以从任何地址开始。在分段方式中，源程序(段号，段内偏移)经连结装配后仍保持二维结构


• 页是信息的物理单位，与源程序的逻辑结构无关,用户不可见，页长由系统确定，页面只能以页大小.的整倍数地址开始。在分页方式中，源程序(页号,页内偏移)经连结装配后变成了一维结构


• 页式存储基于存储器的物理结构，存储利用率高,便于管理，但难以实现存储共享、保护和动态扩充


• 段式存储基于应用程序的结构，有利于模块化程序设计，便于段的扩充、动态链接、共享和保护，但会形成段之间的碎片，浪费存储空间