Ting's Blog

听的无名小站

0%

OS第五章总结

发表于 更新于 分类于 ，
💡 TIP

放一下存储器管理的笔记把

学习目标

Ø能够理解各层存储器的作用

Ø理解存储管理的基本任务

Ø理解逻辑地址、物理地址的概念

Ø理解程序装入的实现方式及特点

Ø理解程序链接的实现方式及特点

目标评价

  1. 说出常见的计算机存储硬件

  2. 说出存储层次中各硬件的特点

  3. 分析源程序、目标程序和可执行程序的地址形式

  4. 理解CPU对内存的访问过程

  5. 说出程序的装入和链接方式

基础概念

内存管理的任务

  • 内存分配回收

  • 地址转换

  • 存储扩充

  • 存储保护

💡 TIP

学后应能够回答的问题

image-20241213140352275

存储器的层次结构

image-20241213140513750

计算机存储层次示意图

寄存器

  • 存放CPU执行时的数据和指令

高速缓存

介于寄存器和存储器之间

  • 备份主存常用数据和指令，减少对主存储器的访问次数

  • 缓和内存和处理机之间的矛盾

📝 NOTE

image-20241213140854868

多级缓存

l1d：一级数据缓存

L1i：一级指令缓存

L2 cache：二级缓存

L3 cache：三级缓存

磁盘缓存

  • 暂时存放频繁使用的一部分磁盘数据和信息

  • 缓和主存和I/O设备在速度上的额不匹配

  • 利用主存的部分空间，主存可看成辅存的高速缓存

主存

性能指标

  • 按字节连续编址，没个存储单元为1个字节(8个二进制位)

  • 存储容量：所包含的存储单元总数(单位：MB或GB)

image-20241213141949137

💡 TIP

简例

image-20241213142102753

程序地址

程序在成为进程前的准备工作

📝 NOTE

总结
程序在成为进程前的准备工作

  • 编辑：形成源文件(符号地址)

  • 编译：形成目标模块(模块内符号地址解析)

  • 链接：由多个模块或程序库形成可执行文件(模块间符号地址解析)

  • 装入：构造PCB，形成进程(物理地址)

  1. 编辑：编写源程序

  2. 编译：由编译程序(Complier)对源程序进行编译，形成若干个目标模块

  3. 链接：由链接程序(Linker)将目标模块和他们所需要的库函数链接在一起，形成一个完整的装入模块

  4. 装入：由装入程序(Loader)，将装入模块装入内存

💡 TIP

就像C语言代码，到运行的过程：

  • 编译

  • 链接

  • 运行

程序各阶段的地址变换

  1. 源程序编译后的main.s

    image-20241213143808948

    add：符号表示

    符号地址

  2. 源程序汇编后的main.o和test.o反汇编的文件

    image-20241213143843828

    13：整数值

    相对地址

  3. 可执行程序myprog

    image-20241213144033296

    4004e2 ：整数值

    相对地址

  4. 可执行文件装入内存执行时的地址？

    内存单元地址由CPU对内存的访问方式决定

💡 TIP

编译、汇编、链接，三个过程的地址变换是编译器做的

而，将生成好的可执行文件，放到内存中运行，是操作系统要考虑的事情

物理地址和逻辑地址

物理地址(绝对地址)

  • 物理内存的地址，内存以字节位单位编址

  • 物理地址空间：所有物理地址的集合

逻辑地址(虚拟地址、相对地址)

  • 由CPU产生的地址，即成程序编译后使用的相对于0字节的地址

  • 逻辑地址空间：由程序所生成的所有逻辑地址的集合

地址转换(地址重定位、地址映射)

  • 程序中的逻辑地址转换为物理地址

💡 TIP

地址转换是操作系统内存管理任务之一

程序的装入

image-20241213150423225

程序装入示意图

地址转换时期

  • 绝对装入方式

    • 编译产生的地址使用绝对地址
    • 程序或数据被修改时，需要重新编译程序

  • 可重定位装入方式

    • 编译后的目标模块使用相对地址
    • 在装入时，完成重定位(静态重定位)
    • 需硬件支持

  • 动态运行时装入方式

    • 编译后的目标模块使用相对地址
    • 在运行时，完成重定位(动态重定位)

程序的链接

静态链接

  • 在程序运行前，将各目标模块及它们所需的库函数链接成一个完整的装配模块

  • 对相对地址进行修改；变换外部调用符号

装入时动态链接

  • 在装入内存时，采用边装入边链接的链接方式

  • 便于修改和更新

  • 便于实现对目标模块的共享

运行时动态链接

  • 将某些目标模块的链接推迟到执行时才执行

  • 加快装入过程，节省大量的内存空间

💡 TIP

对于运行时动态链接，动态链接库像是相关联的东西

动态链接库详细介绍

动态链接库（Dynamic Link Library，简称DLL）是包含可以由多个程序共享使用的代码和数据的文件。这种技术使程序能够高效地复用资源、减少重复代码以及节省内存空间。

💡 TIP

image-20241213161228676image-20241213161403091
链接示意图

💡 TIP

各种存储管理方案

image-20241213161739973

⚠️ WARNING

学习目标

掌握各种存储管理方案的内存分配回收、数据结构、地址转换、存储保护、主要技术、优缺点

  • 能够分析单一分区、固定分区、动态分区的管理方式及优缺点

  • 掌握操作系统分区管理的数据结构、分区分配算法、回收算法

  • 理解并应用分区管理的地址变换方法

  • 掌握分区管理的内存扩充技术：交换、覆盖、紧凑

image-20241213162230528

连续分配存储管理方式

连续存储方式：为一个用户程序分配一个连续的内存空间

💡 TIP

分类

  • 单一连续分区

  • 固定连续分区

  • 动态分区分配

  • 动态可重定位分区分配

单一连续分区

分配方式

单道程序环境下，仅装有一道用户程序，整个内存的用户空间由该程序独占。

  • 内存分配管理非常简单，内存利用率低

  • 用于单用户、单任务OS

  • CP/M、MS-DOS、RT11

固定分区

管理方式

多个分区可装多道程序

分区大小固定

分区个数固定

image-20241213163147362

固定分区(大小相同)(左)，固定分区(大小不同)(右)
📝 NOTE

固定分区中，使用固定分区使用表来管理分区的使用情况。

image-20241215134409673

固定分区使用表

地址重定位与存储保护

image-20241215134606043

  • 静态重定位

  • 界限寄存器

💡 TIP

静态重定位

  • 在程序装载时，由操作系统将逻辑地址加上分区的起始地址，转换为物理地址

  • 该方法简单，但程序装载后地址固定，无法移动(但固定分区情况下，程序确实不会发生移动)

界限寄存器

  • 每一个分区设置一个界限寄存器，记录该分区的最大地址范围。

  • 访问内存时，硬件检查物理地址是否在分区范围内，超出范围则触发包含异常。

特点

优点：易于实现，开销小

问题：

  1. 可能存在内碎片和外碎片

    📝 NOTE

    内碎片：占用分区之内未被利用的空间

    外碎片：占用分区之间难以利用的空闲分区通常是小的空闲分区

    💡 TIP

    举个例子：

    例如，现在操作系统分给的固定分区大小为16k

    但是又进程现在申请12k大小的内存，但是由于操作系统为固定分区模式，所以只能给该进程分一个大小为16k的分区，这样就有4k空间被浪费了，这浪费的4K空间称为内碎片

    另外，再比如，现在操作系统仅剩下1K的存储空间，所有进程都无法装入，这1K存储空间，就称为内碎片

  2. 分区数固定，限制了并发执行的程序数目

动态分区

image-20241215143909924

image-20241215143929060

image-20241215143947058

动态分区示意图

数据结构

image-20241215150022370

已分配分区表

image-20241215150156082

空闲分区表

image-20241215150357079

空闲分区链
💡 TIP

空闲分区链用于高效的管理空闲内存块

看起来，每一个空闲分区中，都会存放下一个空闲分区的首地址

另外，还会存放当前分区的大小

分配算法

基于顺序搜索的动态分区分配算法

  • 依次搜索空闲分区链上的空闲分区，寻找一个大小能够满足要求的分区

  • 首次适应算法、循环适应算法、最佳适应算法、最坏适应算法

首次适应算法

  • 空闲分区链以地址递增的次序链接(注意！这里不是按照空闲分区的大小进行链接)

  • 从链首开始顺序查找，直到找到一个大小能够满足要求的空闲分区为止

    此处的含义是：当找到一处空闲块，空闲分区的大小大于当前需要装入的进程时，就会将该空闲块中进程所需要的部分  分给进程，剩下的部分仍作为空闲分区

  • 缺点：低址部分留下许多小碎片

循环首次适应算法

  • 从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区

  • 空闲分区分布更均匀，减少了查找的开销

  • 缺乏大的空闲分区

最佳适应算法

  • 搜索整个序列，找到适合条件的最小分区进行分配

  • 空闲分区按其容量从小到大的顺序链接

  • 用最小空间满足要求；但留下许多难以利用的小碎片

最坏适应算法

  • 搜索整个序列，寻找最大分区进行匹配

  • 空闲分区按其容量从大到小的顺序链接

  • 分割后空闲块任为较大空块；缺乏大的空闲分区

💡 TIP

关于每种分配算法是否会产生 内/外碎片的讨论
首次适应算法

  • 不会产生内碎片：因为首次适应算法中，每次分给进程的都是刚好够进程请求的

  • 会产生外碎片：因为随着申请的进程数越来越多，空闲块就会被拆的越来越小，直到最后无法分给任何一个进程

循环首次适应

其实和首次适应算法差不多

最佳适应算法

也是动态分区的一种

一般来说，动态分区都是不会产生内碎片的，因为给进程分的，都恰好是进程所需要的

但由于是动态分区，则不可避免空闲块被切的越来越小，直到无法分给任何进程

💡 TIP

其实，循环首次适应、最佳适应、最坏适应，都只是对首次适应算法的改进，都只是修改了适应算法，而分配空间的核心相同

基于索引搜索的动态分区分配算法

  • 提高搜索分区的速度，在大、中型系统中采用

  • 快速适应算法、伙伴系统和哈希算法

快速适应算法

  • 将空闲分区按其容量大小进行分类，具有相同容量的所有空闲分区设有一个空闲分区链表

  • 分配时，根据进程长度，从索引表中寻找能容纳它的最小空闲分区链表；从链表取下第一块进行分配

  • 特点

    • 优点：不分割分区，不产生碎片，查找效率高
    • 缺点：分区归还主存时算法复杂，系统开销较大，存在浪费
伙伴系统
💡 TIP

固定分区方式不够灵活，当进程大小与空闲分区大小不 匹配时，内存空间利用率很低。 动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。 伙伴系统 (buddy system)是介于固定分区与可变分区之间的动态分区技术。 伙伴：在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为“伙伴”。

摘自存储器管理_OS_快速适应算法-CSDN博客

伙伴算法规定，无论已分配分区或空闲分区，其大小均为 $2$ 的 $k$ 次幂，$k$ 为整数，$n <= k <= m$，其中：$2^n$ 表示分配的最小分区大小，$2^m$ 标识分配的最大分区的大小，通常$2^m$ 是整个可分配内存的大小。

在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区。

内存管理模块保持有多个空闲块链表，空闲块的大小可以为 2，4，8，$2^m$ 字节（$m$ 为正整数）

系统初起时，只有一个最大的空闲块（整个内存）。

当一个长度为$n$的进程申请内存时，系统就分给它一个大于或等于所申请尺寸的最小的2的幂次的空闲块。(并没有一定和进程所需内存相同；即，即使进程用不了那么多，操作系统还是会分给它)

伙伴系统的缺点：不能有效的利用内存。进程大小不一定是2的整数被，因此会造成浪费，内碎片严重。

同时也会出现外碎片，因为还是会有进程无法放入较小的分区。

内存分配流程

image-20241215205802867

内存回收

image-20241215205944359

地址转换

image-20241215210048568

动态重定位示意图

相关技术

主存不足的存储管理技术

  • 内存紧凑

  • 交换

  • 覆盖

分页存储管理

image-20241215210511208

image-20241215210526994

学习目标及目标评价

分页存储的基本原理

将内存空间分为一个个大小相等的分区（比如：每个分区4KB）

每个分区就是一个“页框”或称“页帧”、“内存块”、“物理块”

每个页框有一个编号，即“页框号”或者“内存块号”、“页帧号”、“物理块号”

页框号从0开始。

页与页框

页与页框
(完)

地址结构

内存地址(逻辑地址)范围（1块大小为1KB）

image-20241215211426833

内存地址结构：

image-20241215211502226 image-20241215211616857
分页地址中的结构(32位)

页号P

  • 12-31位：20位

  • 地址空间最多运行有1M（$2^{20}$）页

位移量W（页内地址）

  • 0-11：12位

  • 每页大小为4KB（$2^{12}$）

对某特定机器，地址结构是一定的。

若给抵挡一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得

image-20241215212411760

数据结构

  • 进程页表：每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；

    • 逻辑页号（本进程的地址空间）-> 物理页号（实际内存空间）；

  • 物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用情况

    • 数据结构：位示图，空闲分区链表

  • 请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程PCB里

💡 TIP

页表不属于进程的地址空间

但每个进程均有一个页表，由操作系统维护。

页表的主要作用是将进程的虚拟地址（Virtual Address）映射到物理地址（Physical Address）。每个进程都有独立的虚拟地址空间，而页表是管理这种虚拟地址空间的关键数据结构。

页表本身存储在内存中，由操作系统维护。它记录了虚拟页面与物理页面之间的映射关系，例如页面是否在内存中、页面权限等。

image-20241215212545948

页表结构

内存有效访问时间EAT

image-20241220213940979

1156ee8355ca107182c5e49788ac3c3

💡 TIP

当快表未命中时，根据程序的局部性原理，下一次再次访问的概率会很大，所以需要将缺失的信息写入到块表中，以便下次查询时可以命中。

相关技术

两级或多级页表

image-20241220221715989

image-20241220221737815

image-20241220223823781

💡 TIP

对于该题，通过逻辑地址空间和页大小可以得出

逻辑地址结构即寻址到一个位

逻辑地址共$10 + 16 = 26$位，

则，寻址到一个位需要：$26$位，即逻辑地址长度为$26$

而通过页表项大小和页大小可以算出一个页表可以存下$2^9$个页表，即逻辑地址结构中页号长度为$9$位

页内偏移量长度即页大小$10$位

所以可以推出现在已经用了$10 + 9 = 19$位

则剩下$7$位

全为页目录号长度

则，页目录号包含表项的个数至少为$2^7$

页目录表，指的是一级页表。

包含表项，指的一级页表中的一项。