一、层次结构

1. 通用层次结构：

CPU 主存 辅存

2. 具体功能划分

寄存器、高速寄存器cache、主存储器、磁盘缓存、固定磁盘、可移动存储介质。

二、程序装入和链接

1. 存储器管理

对象：内存
目标：用户方便使用存储器，提供充分大的存储空间，提高内存利用率。

2. 程序进入内存的流程步骤

编译 -> 链接 -> 装入内存

3. 程序的装入

绝对装入：绝对映射，程序中逻辑地址与内存物理地址完全相同
可重定位装入：静态映射，在装入时对逻辑地址进行修改
动态运行时装入：逻辑地址到物理地址的映射在程序运行时才执行

4. 程序的链接

静态链接、装入时动态链接、运行时动态链接

三、连续分配方式

1. 单一连续分配

一个用户程序独占连续的内存用户区
只能用于单用户、单任务的OS中
系统分两个内存区：系统区和用户区

2. 固定分区分配：划分多个区域可供多用户、多任务使用

（1）划分方法：
分区大小相等的划分方法，一般用于多个相同任务。
分区大小不等的划分方法，根据实际任务大小分配。
（2）缺点：容易造成浪费
（3）分配方法：同样有FF和BF，简单一点：随遇而安FF，孟母三迁BF。

3. 动态分区分配

根据程序大小，动态地分配连续的内存空间，分配的内存大小等于程序大小
（1）分区数据结构

空闲分区表

空闲分区(双向)链表

（2）分配算法

• 首次适应(FF)
  优点：保留高地址部分的大空闲区
  缺点：低地址存在很多小的、无法利用的空闲分区，且查找时间较长
• 首次适应循环算法（CF）：从上次找到空闲分区的下一个分区开始，按序选择第一个满足要求的内存区
  优点：空闲分区在内存中均匀分布,查找时间少
  缺点：缺乏大的空闲分区
• 最佳适应（BF）：在所有空闲分区中查找与程序大小最相近的空闲分区
  为了加快速度，可以把空闲分区从小到大排列
  优点：提高内存使用率，保留大空闲去
  缺点：仍然会存在小片无法利用的空闲分区
• 最坏适应算法（WF）：在整个空闲分区中查找最大空闲分区分割给作业（分区从大到下）
  优点：不产生很小的碎片，查找效率高
  缺点：缺乏大的空闲分区
• 快速适应算法（QF）
  将空闲分区按大小分类，同一类设立一个空闲链表，根据进程长度寻找容纳它的最小空闲区链表
  优点：查找效率高，不分割空闲去，保留大分区
  缺点：算法复杂，开销大

• 习题：

  
  
  三种分配对比

（3）分配操作

内存分配

动态重定位分区分配
①紧凑（拼接）：空闲分区的搬迁及合并
②动态重定位：要有动态定位机制支持

动态重定位分区分配算法

（4）回收操作

• 无相邻空闲分区自己建立一个新表项
• 回收区与相邻的空闲分区合并以前一个空闲分区地址的首址为新空闲分区的首址

（5）伙伴系统
口诀：大于一半拿整个，小于一半拿一半。

4. 对换

对换是指把内存中暂不能运行的进程，或暂时不用的数据，换出到外存上，以腾出内存空间
整体对换：以进程为单位(挂起操作)
部分对换：以页或段为单位(虚拟存储器)
换出操作：选择阻塞态并且优先级最低的进程，启动盘块把进程的程序数据都传送到磁盘的对换区。传送成功就回收内存空间，修改其PCB。
换入操作：找出换出并在就绪状态的进程，对换出时间最久的进程进行换入，直到满了或者空了。

四、 基本分页存储管理方式

1. 基本概念：

在内存上是非连续分配的，逻辑划分是页，物理划分是物理块。页和块大小相等，页面可任意存放在任何物理快中，最后一页可不放满。页编号在逻辑地址上是连续的，在物理块上是离散的。

2. 页的大小：

通常是512B-8KB

3. 页的地址结构和计算方式

页的地址结构和计算方式

4. 页表：

记录进程每一页在内存存放的块号

页和物理块

5. 页表管理

页表数据在内存
页表的起始地址和长度放在PCB
地址转换的时候，页表的其实地址和长度送入页表寄存器PTR

6. 地址变换过程

进程访问某个逻辑地址时，分页地址机构自动将逻辑地址分为页号和页内地址
页号大于页表长度，越界错误
根据页号计算位置，从页表中查物理块号
页内地址直接对应块内地址
通过物理块号和块内地址得到物理地址
根据物理地址读取数据

// 经典题目
有一基本分页存储管理系统，页面大小为1024B，地址长度为16位，请问该系统共有多少内存块？写出逻辑地址8230H的页号和页内地址；如果该页对应的内存块号为18H，求该逻辑地址对应的物理地址。 
①系统地址长度为16位；
   现每页大小为1024B = 210B，即页内地址占10位；
   因此系统中可表示页码的位数为：16-10=6位，即系统中内存块数为：26 = 64（块）。
②逻辑地址8230H展开成二进制为：1000,0010,0011,0000B
   页内地址占后10位，其余高位为页号；
   因此，页内地址为：10,0011,0000 = 230H；
   页号为：10,0000 = 20H。
③现该页对应的内存块号为18H，表示成二进制为：0001,1000B；
   块内地址与页内地址相同，即：10,0011,0000；
   将内存块号与块内地址合并后，得：0110,00 10,0011,0000B = 6230H。
缺点：访问一次逻辑地址，必须两次访问内存。
第一次访问内存(即访问页表)为取得逻辑地址对应的内存物理地址
第二次访问内存为取得逻辑地址中的数据

7. 地址变换的缺点

需要访问两次内存才能取出数据
一次访问页表，查找物理块号，计算物理地址
一次根据物理地址读取数据。

8.快表

把页表部分内容（经常命中）放在快表，这样可以减少转换。
快表访问时间为20ns的话，内存访问为100ns的话。块表命中则120ns，快表不命中则220ns。

9.单级页表的缺陷

数据形式存储，属于连续分配。
页表不能超过单个物理块。
逻辑空间很大，占用页表也大。

10.解决方法

离散分配管理页表
需要的页表调入内存，不需要的驻留磁盘。

11. 两级页表：对页表本身采用分页式管理，对页表本身增加了一层页表管理

有一基本分页存储管理系统，内存块大小为4096Bytes，每个块号占用4个Bytes，如果页表也以离散方式放在内存(块)中，求采用一级页表和两级页表，系统能支持文件的逻辑空间最多为多少？假如逻辑地址为123456H，求页内地址和外层页号。
   每个内存块占4Bytes，即每个页表项占4B
   每个内存块大小为4096Bytes，
   每个内存可放下最多4096/4=1024个页表项
   采用一级页表能支持文件的逻辑空间最多为：1024x4096=4MBytes
   采用二级页表能支持文件的逻辑空间最多为：1024x1024x4096=4GBytes
   4096占用12bits,即页内地址占12bits
   1024占10bits，即外层页内地址占10bits
   123456H=0001,0010,0011,0100,0101,0110b
   页内地址=后12bits=0100,0101,0110b=456H
   外层页号=(12+10)bits以上地址=00b=0H

一个32位地址的计算机系统使用二级页表,虚地址被分为9位顶级页表,11位二级页表和偏移.请问:
1)页面长度是多少?
2)空间共有多少个页面?
虚地址共32位，顶级页表占9位，二级页表占11位，所以32-9-11=12位是偏移，因此页面长度是2的12次方，即4K。顶级页表和二级页表共9+11=20位，因此虚地址空间中共有2的20次方，即1M个页面。

操作系统中逻辑地址与物理地址的转换
在一分页存储管理系统中,逻辑地址长度为16位,页面大小为4096B,现有一逻辑地址为2F6AH,且第0、1、2页依次存放在物理块5、10、11中,问相应的物理地址为多少?
4096B=2^12B
16位寻址一共2^16B
分页存储.共分的页：2^16/2^12=2^4=16 共分16页.
第0页的地址范围 0 - FFFH
第1页的地址范围 1000H - 1FFFH
第2页得地址范围 2000H - 2FFFH
第11页 B000H - BFFFH
第15页 F000H - FFFFH
2F6AH=10 1111 0110 1010 在2页的范围对应物理块11
所以物理地址为：
2F6AH - 2000H + B000H = F6AH + B000H= BF6AH

设一页式管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存中共有8个存储块。试问逻辑地址至少应为多少位？内存空间有多大？
2的4次方=16，所以页号占4位，页长为2048=2的11次方，所以页内地址占11位，逻辑地址15位
存储块有8个，每个存储块对应2048B大小的页框，所以主存空间为16KB

❗下面没给出答案

有一基本分页存储管理系统，假定页面大小为1024字节，页表采用离散方式放在内存中。每个页表项占用4个字节。在忽略页表及系统区等占用空间的条件下：
若采用一级页表，系统能支持的逻辑空间最多为多少？
若采用二级页表，系统能支持的逻辑空间最多为多少？
在二级页表中，现有逻辑地址为542783，求该地址对应的外层页号，外层页内地址和页内地址？ 
注意题目中所有数据都是十进制

五、 基本分段存储管理方式

1. 分段存管理的目的：

方便编程、分段共享、分段保护、动态链接、动态增长

段地址

2. 变换过程

进程访问某个逻辑地址时，先取得段号
若段号大于段表长度，越界错误
查段表得到段开始地址和段长度
若段内地址大于段长度，越界错误
通过段开始地址和段内地址得到物理地址
根据物理地址读取数据

3.快表

这个也可以放进快表

4.分页分段区别

• 页是信息的物理单位，满足系统空间管理需要。分页实现离散分配方式，以消减内存的外零头， 提高内存的利用率。
  段是信息的逻辑单位，满足用户需要
• 页的大小固定，由系统决定
  段的长度不固定， 由用户决定
• 分页的作业地址空间是一维的
  分段的作业地址空间则是二维的

5.段页式

段页式管理的优点：既节省内存空间，提高内存分配的效率，又兼顾用户编程的需要

段页式

6. 段页式地址变换机构

当进程要访问某个逻辑地址时，先取得段号
如果段号大于段表长度，越界错误
将段表始址与段号相加，得段表中位置
从段表中相应位置，得到该段页表的首址
将段内页号与页表首址相加，得页表中位置
从页表中相应位置，得到物理块号p
将块号p与页内地址d组合成物理地址

变址

题目：

题目

六、 虚拟存储器的基本概念

七、 请求分页存储管理方式

八、 页面置换算法

九、 请求分段存储管理方式