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

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

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

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

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

优点:

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

缺点:

"碎片"问题

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

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

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

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

优点:

缺点:

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

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

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

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

优点:

缺点:

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

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

优点:

缺点:

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

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

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

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

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

紧凑技术：

缺点(代价很大)：

内存块大小一般为2k个字,且满足L≤K≤U,其中: 2^L表示分配的最小块大小; 2^U表示分配的最大块大小，通常为整个内存大小

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

在这里有一个原则：

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

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

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

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

页(page)页面:

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

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

块大小通常取2的幂次

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

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

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

逻辑地址:

用页号和页内偏移表示

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

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

页内偏移

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

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

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

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

通过例子理解一下：

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

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

页表表项中还有存取控制字段，实现对物理块的保护，比如: P: 是否在内存 M: 修改位

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

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

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

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

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

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

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

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

考虑效率:

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

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

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

如果我们命中那么CPU：

CPU未命中那么CPU：

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

特点

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

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

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

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

例如:

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

1.页表中增加标志位:读/写;只读;只可执行;不可访问等，在执行时进行核对 2.要想向只读块写入信息则指令停止，产生中断

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

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

优点:

● 二级页表的逻辑地址被划分为三部分: 页目录、页表页、页内偏移

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

为节约时间，可采用快表

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

对于64位系统, 多级页表能满足需求吗?

如果每 个页表条目为4B,第二级外部页表: 大小仍然需要232x4B 页表的缺陷:页表的大小与虚拟地址空间的大小成比例增长) 解决方案:

逻辑地址:

哈希表内

每个进程都有一个哈希表

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

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

●减少存储每个页表所需要的内存空间，但当引|用页时增加了查找页表所需要的时间 ●由于页表按照物理地址排序，而查找按照虚拟地址排序，因此可能导致需要查找整个表来寻求匹配

●80386开始支持分页:通过设置cr0寄存器的PG标记启用; PG=0,虚拟地址=物理地址 ●采用二级页面，页面大小为4KB(2^12) : ●正在使用的页目录的物理地址存放在控制寄存器cr3中(也就是页表寄存器)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

段页式存储管理的基本原理: 1.程序根据自身的逻辑结构划分成若干段 2.内存的物理地址空间划分成大小相等的物理块 3.将每- -段的线性地址空间划分成与物理块大小相等的页面，形成段页式存储管理 4.逻辑地址分3个部分: 段号、段内页号和页内位移.

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

操作系统: 分页

程序: 分段

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

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

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