第四章 存储器管理.

Slides:



Advertisements
Similar presentations
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
Advertisements

Linux 系统. 操作系统发展需求 1 没有操作系统 2 简单批处理操作系统 3 多道程序设计的批处理 4 多道程序设计的分时操作系统 5 多处理机并行系统 6 网络操作系统 7 分布式操作系统.
计算机系统结构 (第9讲).
第3单元 主存管理 第3节 分页存储管理 一页一页的放………… 怎么解决分段带来的碎片问题? 页与页框 地址映射 多级页表 快表 举例
实用操作系统概念 张惠娟 副教授 1.
第3章 存储管理 3.1 存储管理概述 3.2 基于连续分配的内存管理方法 3.3 基于离散分配的内存管理方法 3.4 虚拟存储管理
3.1 虚拟存储器 3.2 内存管理方式 段页机制 3.4 Linux存储管理 3.5 小结 习题
第四章 存储器管理.
Oracle数据库 Oracle 子程序.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
第4章 存储管理 本章学习目标 4.1 存储管理的功能 4.2 实存管理 4.3 虚拟存储器管理 4.4 碎片与抖动问题 开 始.
第五章 存储管理 2006年11月.
在PHP和MYSQL中实现完美的中文显示
Kvm异步缺页中断 浙江大学计算机体系结构实验室 徐浩.
Hadoop I/O By ShiChaojie.
IPv6 地址空间.
中国科学技术大学计算机系 陈香兰 2013Fall 第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 2013Fall.
内存管理基本概念.
存储系统.
走进编程 程序的顺序结构(二).
辅导课程六.
存储管理 存储体系 存储管理的任务 分区存储管理 页式存储管理 交换技术与覆盖技术 虚拟存储.
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第十章 IDL访问数据库 10.1 数据库与数据库访问 1、数据库 数据库中数据的组织由低到高分为四级:字段、记录、表、数据库四种。
Online job scheduling in Distributed Machine Learning Clusters
第九章 存储管理 9.1 概述 一、存储器的层次:三级存储器结构 本章主要讨论几种常用的内存管理技术。 Cache 内存 外存 由硬件寄存器
逆向工程-汇编语言
CPU结构和功能.
用event class 从input的root文件中,由DmpDataBuffer::ReadObject读取数据的问题
操作系统原理 Operating System Principles
《手把手教你学STM32-UCOS》 主讲人 :正点原子团队 硬件平台:正点原子STM32开发板 版权所有:广州市星翼电子科技有限公司
Unit 11.Operating System 11.1 What’s OS 11.2 Related Courses
内容摘要 ■ 课程概述 ■ 教学安排 ■ 什么是操作系统? ■ 为什么学习操作系统? ■ 如何学习操作系统? ■ 操作系统实例
C语言程序设计 主讲教师:陆幼利.
微机系统的组成.
第四章 存储器管理 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式
第四章 存 储 器 管 理 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配存储管理方式
顺序表的删除.
本节内容 随机读取 视频提供:昆山爱达人信息技术有限公司.
VisComposer 2019/4/17.
实验四、TinyOS执行机制实验 一、实验目的 1、了解tinyos执行机制,实现程序异步处理的方法。
WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了,与其他文章的区别是什么? 2.Charging Control的手段是什么? 3.Power Reigon是什么东西?
VB与Access数据库的连接.
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
iSIGHT 基本培训 使用 Excel的栅栏问题
段式存储管理(Segmentation)
本节内容 结构体 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 线性地址的管理 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 文件系统 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第七、八次实验要求.
3.1私有内存的分配.
临界区问题的硬件指令解决方案 (Synchronization Hardware)
GIS基本功能 数据存储 与管理 数据采集 数据处理 与编辑 空间查询 空间查询 GIS能做什么? 与分析 叠加分析 缓冲区分析 网络分析
第9章 存储管理.
本节内容 Windows线程切换_时钟中断切换 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
第六章 Excel的应用 五、EXCEL的数据库功能 1、Excel的数据库及其结构 2、Excel下的数据排序 (1)Excel的字段名行
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
本节内容 动态链接库 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
数据表示 第 2 讲.
本节内容 进程 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第四章 UNIX文件系统.
FVX1100介绍 法视特(上海)图像科技有限公司 施 俊.
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
入侵检测技术 大连理工大学软件学院 毕玲.
实验六、COM类型病毒分析实验 实验开发教师: 刘乃琦 谌黔燕.
Presentation transcript:

第四章 存储器管理

本章要点(1/4) 目标:了解简单存储器的管理方式和它们的实现方法。 重定位的基本概念 重定位的实质是什么,如何实现重定位? 为什么要引入重定位? 静态重定位适用于何种场合,它有何优缺点? 动态重定位是为了解决什么问题而引入的? 在连续分配方式、分页系统和分段系统中,分别是如何实现动态重定位的?

本章要点(2/4) 动态分区分配方式 什么是动态内存分配? 在动态内存分配中如何提高内存利用率? 造成动态分区分配方式内存浪费的主要原因是什么,它可以通过什么办法加以解决? 动态分区分配算法可采用哪两种数据结构来描述分区的情况?可采用哪些算法来进行内存的分配和回收? 在采用不同的分配算法时,系统是如何组织空闲分区表或空闲分区链的,它们又是如何进行分区的分配和回收的。

本章要点(3/4) 分页和分段存储管理方式 是在什么推动力的作用下,使内存管理由动态分区分配方式发展为分页存储管理方式? 分页系统是如何将地址空间中的作业划分为若干个页,它又是如何进行内存分配的? 掌握分页系统逻辑地址的结构。 为了进行逻辑地址到物理地址的转换,分页系统必须为每个作业配置什么样的数据结构并提供哪些硬件支持? 为什么引入快表可加快分页系统存取指令和数据的速度?

本章要点(4/4) 分页和分段存储管理方式 由分页发展为分段,并进一步发展为段页式存储管理方式的主要推动力是什么? 分段和段页式系统是如何管理作业的地址空间和内存空间的,它们的地址变换是如何完成的? 试将分页系统与分段系统加以比较。 为什么分段系统比分页系统更容易实现信息的共享和保护?

本章内容 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配存储管理方式 4.4 对换(Swapping) 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配存储管理方式 4.4 对换(Swapping) 4.5 分页存储管理方式 4.6 分段存储管理方式

4.1 存储器的层次结构 7

4.1.1 多层结构的存储器系统 1、存储器的多层结构 理想存储器 速度快,能跟上处理机的速度 容量大 价格便宜 图4-1 计算机系统 4.1.1 多层结构的存储器系统 理想存储器 速度快,能跟上处理机的速度 容量大 价格便宜 1、存储器的多层结构 图4-1 计算机系统 存储层次示意 CPU寄存器 寄存器 高速缓存 主存储器 磁盘缓存 固定磁盘 可移动存储介质 可执行存储器 主存 速度 价格 存储容量 辅存

2、可执行存储器

4.1.2 主存储器与寄存器 1、主存储器 2、寄存器 主存储器:也称内存、主存或可执行存储器 寄存器 4.1.2 主存储器与寄存器 1、主存储器 主存储器:也称内存、主存或可执行存储器 CPU的控制部件只能从主存储器中取得指令和数据; CPU与外围设备交换的信息一般依托于主存储器地址空间。 寄存器 访问速度最快,完全能与CPU协调工作; 容量小、价格昂贵; 寄存器的长度一般以字(word)为单位。 2、寄存器

4.1.3 高速缓存和磁盘缓存 1、高速缓存 2、磁盘缓存 高速缓存: 磁盘缓存 容量大于寄存器,但比内存小,访问速度快于主存储器 4.1.3 高速缓存和磁盘缓存 1、高速缓存 高速缓存: 容量大于寄存器,但比内存小,访问速度快于主存储器 根据程序执行局部性原理,将主存中一些经常访问的信息存放在高速缓存中,减少访问主存储器的次数,提高程序执行速度。 磁盘缓存 存放外部存储器中频繁使用的一部分磁盘数据和信息 利用主存中的存储空间,来暂存从磁盘中读出的信息 2、磁盘缓存

4.2 程序的装入和链接

程序在成为进程前的准备工作 编辑→编译→链接→装入→运行 图4-2 对用户程序的处理步骤 编译 链接 装入 Compiler Linker Loder 图4-2 对用户程序的处理步骤

4.2.1 程序的装入 在可执行文件装入时需要解决可执行文件中地址(指令和数据)和内存地址的对应。由操作系统中的装入程序loader来完成。 4.2.1 程序的装入 在可执行文件装入时需要解决可执行文件中地址(指令和数据)和内存地址的对应。由操作系统中的装入程序loader来完成。 装入模块的三种装入方式: 绝对装入方式 可重定位装入方式 动态运行时装入方式

1、绝对装入方式(Absolute Loading Mode) 在可执行文件中记录内存地址,装入时不再作地址重 定位,直接定位在上述(即文件中记录的地址)内存地址。 绝对地址的产生: (1)由编译器完成; (2)由程序员编程完成。 对编译器而言,编程用符号地址,在编译或汇编时再 将符号地址转换为绝对地址。 优点:装入过程简单。 缺点:过于依赖于硬件结构,不适于多道程序系统

1、绝对装入方式(Absolute Loading Mode) 绝对地址 内存地址 1024 1024 JUMP 1424 1424 装入程序 1424 LOAD 2224 2224 2224 绝对装入模块

2、可重定位装入方式(Relocation Loading Mode) 由装入程序根据内存当时的实际使用情况,将装入模块装入到内存的适当地方。 重定位:在装入时对目标程序中的指令和数据地址的修改过程。 静态重定位:地址变换只是在装入时一次完成,以后不再改变。 缺点:一个程序通常需要占用连续的内存空间,程序装入内存后不能移动。不易实现共享。

2、可重定位装入方式(Relocation Loading Mode) 图 4-3 作业装入内存时的情况

3、动态运行时装入方式(Dynamic Run-time Loading) 在把装入模块装入内存后,并不立即把装入模块中的逻辑地址转换为物理地址,而是把这种地址转换工作推迟到程序真正执行时才进行。因此,装入内存后的所有地址都是逻辑地址。 优点: OS可以将一个程序分散存放于不连续的内存空间,可以移动程序,有利用实现共享。 能够支持程序执行中产生的地址引用,如指针变量(而不仅是生成可执行文件时的地址引用)。 缺点: 需要硬件支持(重定位寄存器),OS实现较复杂。

4.2.2 程序的链接 链接程序的功能: 是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数,装配成一个完整的装入模块。 链接方式: 静态链接(static-linking) 装入时动态链接(Run-time dynamic-linking) 运行时动态链接(load-time)

1、静态链接方式(Static Linking) 静态链接:是在程序运行之前,先将各目标模块及它们所需的库函数链接成一个完整的装入模块,以后不再拆开的链接方式。 变换外部调用符号 对相对地址进行修改 图 4-4 程序链接示意图

2、装入时动态链接(Load-time Dynamic Linking) 用户源程序经编译后所得到的目标模块,是在装入内存时,采用边装入边链接的链接方式。 优点:便于软件版本的修改和更新 便于实现目标模块共享

3、运行时动态链接(Run-time Dynamic Linking) 在运行时,若发现一个被调用模块尚未装入内存,由OS去找到该模块,将它装入内存,并把它链接到调用者模块上。通常被链接的共享代码称为动态链接库(DLL)或共享库(shared library)。 优点: 共享:多个进程可以共用一个DLL,节省内存。 部分装入:一个进程可以将多种操作分散在不同的DLL中实现,而只将当前操作相应的DLL装入内存。 便于局部代码修改:即便于代码升级和代码重用; 便于运行环境适应:调用不同的DLL,就可以适应多种使用环境和提供不同功能。如:不同的显示卡只需厂商为其提供特定的DLL,而OS和应用程序不必修改。 缺点:链接开销、管理开销

4.3 连续分配存储管理方式

4.3 连续分配方式 连续分配方式: 指为一个系统或用户程序分配一个连续的内存空间。 单一连续分配 固定分区分配 动态分区分配 动态重定位分配

4.3.1 单一连续分配 单一连续分配方式:内存中仅驻留一道程序,整个内存区为一用户独占。 内存分为两个区域:系统区,用户区。 系统区仅供OS使用,通常位于内存的低端 用户区仅供用户使用,其中只能存放一道作业。 最简单,适用于单用户、单任务的OS。 优点:易于管理。 缺点:对要求内存空间少的程序,造成内存浪费;程序全部装入,很少使用的程序部分也占用内存

4.3.2 固定分区分配 又称定长分区或静态分区模式,是满足多道程序设计需要的最简单的存储管理技术 基本思想: 实现: 4.3.2 固定分区分配 又称定长分区或静态分区模式,是满足多道程序设计需要的最简单的存储管理技术 基本思想: 给进入主存的用户作业划分一块连续存储区域,把作业装入该连续存储区域,若有多个作业装入主存,则它们可并发执行。 实现: 系统启动时,系统操作员根据作业情况静态地把可分配的主存储器空间(用户空间)分割成若干个连续的区域,每个区域的位置固定,大小可相同也可不同,每个分区在任何时刻最多只装入一道程序执行

1、划分分区的方法 把内存划分为若干个固定大小的连续分区。 分区的划分方法: 分区大小相等:只适合于多个相同程序的并发执行(处理多个类型相同的对象)。 分区大小不等:多个小分区、适量的中等分区、少量的大分区。根据程序的大小,分配当前空闲的、适当大小的分区。 固定分区(大小相同) 固定分区(多种大小)

2、内存分配 内存分区使用表 作业调度方式 为了便于内存分配,通常将分区按大小进行排队,并为之建立一张分区使用表。 分区使用表包括:每个分区的起始地址、大小及状态 作业调度方式 当有一用户程序要装入时,由内存分配程序检索分区使用表,从中找出一个能满足要求的尚未分配的分区,分配给该程序,并将该表项中的状态置为“已分配”。 若未找到大小足够的分区,则拒绝为该用户程序分配内存。

3、固定分区分配评价 特点:适用于多道程序系统和分时系统 问题:可能存在内碎片和外碎片。 缺点: 支持多个程序并发执行 难以进行内存分区的共享。 比较适合已知程序(作业)大小和出现频率的情形 问题:可能存在内碎片和外碎片。 内碎片:占用分区之内未被利用的空间 外碎片:占用分区之间难以利用的空闲分区(通常是小空闲分区)。 缺点: 实际系统运行时,往往无法预知分区大小(太大,等同于“单用户分区模式”) 主存空间利用率仍然较低 无法适应动态扩充主存 分区数目预先确定,限制了多道运行程序的数量

图 4-5 固定分区使用表 ~ ~ (a) 分区说明表 (b) 存储空间分配情况 操作系统 20K 分区号 起始地址 长度 占用标志 1 未分配 2 32K 已分配 3 64K 4 128K 32K 作业A 64K 作业B 128K ~ ~ (a) 分区说明表 256K (b) 存储空间分配情况 图 4-5 固定分区使用表

4.3.3 动态分区分配 动态分区分配 又称变长分区模式 4.3.3 动态分区分配 动态分区分配 又称变长分区模式 基本思想:按作业的大小划分分区,但划分的时间、大小和位置均动态确定,系统在作业装入主存执行之前并不建立分区。存储空间的划分是在装作业时进行的。从可用的自由存储空间内,划出一个大小正好等于作业大小的存储区,并分配给这一作业。

1、分区分配中的数据结构 空闲分区表:用于记录每个空闲分区的情况。每个空闲分区占 一个表目,表目中包括分区序号、分区始址及分区的大小等数据项。 空闲分区链:用于实现对空闲分区的分配和链接。 前向指针 N个字节可用 后向指针 N+2 0(分配标识) 图 4-7 空闲链结构

2、动态分区分配算法 动态分区分配算法:为把一个新作业装入内存,须按照一定的分配算法,从空闲分区表或空闲分区链中,选出一分区分配给该作业。

3、分区分配操作 (1) 分配内存 图 4-8 内存分配流程

3、分区分配操作 (2) 回收内存(四种情况) 图 4-9 内存回收时的情况 1 F1 X B F1 B 2 A X F2 A F2 3 (2) 回收内存(四种情况) 1 F1 X B F1 B 2 A X F2 A F2 3 F1 X F2 F1 4 A X B A FX B 图 4-9 内存回收时的情况

F1 X B 1 F2 A X 2 A X B FX 4 图 4-10 内存回收流程

4.3.4 基于顺序搜索的动态分区分配算法 常用分配算法: 首次适应(FF)算法 循环首次适应(NF)算法 最佳适应(BF)算法 4.3.4 基于顺序搜索的动态分区分配算法 常用分配算法: 首次适应(FF)算法 循环首次适应(NF)算法 最佳适应(BF)算法 最坏适应(WF)算法 适用范围: 不太大的系统 系统中通常只设有一个空闲分区链

阴影部分表示已占用块,空白部分表示空闲块 申请40K内存 1、首次适应算法 (first fit, FF) 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 要求:空闲分区链以地址递增的次序链接 算法:从链首开始顺序搜索,直至找到一个大小能满足要求的空闲分区,从该分区中划出一块能放下作业的空间给请求者,剩下的空闲分区仍留在空闲链中。若未找到大小大于作业要求的大小,则分配失败。 缺点:低地址不断被划分,留下许多难以利用的、很小的空闲分区;因为每次查找都是从低地址开始,从而增加可用空闲分区查找的开销。

阴影部分表示已占用块,空白部分表示空闲块 申请40K内存 2、循环首次适应算法 (next fit, NF) 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 查找指针位置 该算法是由首次适应算法演变而成的。 算法:不从链首开始查找,从上次找到的空闲分区的下一空闲分区开始查找 要求:设置查找指针,指示下一次起始查询的空闲分区 采用循环查找方式 优点:减少了查找空闲分区的开销 缺点:缺乏大的空闲分区

阴影部分表示已占用块,空白部分表示空闲块 3、最佳适应算法 (best fit, BF) 阴影部分表示已占用块,空白部分表示空闲块 申请40K内存 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 要求:将空闲分区按容量从小到大形成空闲分区链。 算法:将能满足要求、又是最小的空闲分区分配给作业 缺点:留下许多难以利用的小空闲区

阴影部分表示已占用块,空白部分表示空闲块 4、最坏适应算法 (worst fit, WF) 阴影部分表示已占用块,空白部分表示空闲块 申请40K内存 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 要求:将空闲分区按容量从大到小形成空闲分区链。 算法:查找时只要看第一个分区能否满足作业要求 优点:产生碎片的几率最小;对中、小作业有利;查找效率很高 缺点:会使存储器中缺乏大的空闲分区

基于顺序搜索的动态分区分配算法的评价 引自操作系统概念第9版P363 Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization. Neither first fit nor best fit is clearly better than the other in terms of storage utilization, but first fit is generally faster.

例: 采用动态分区分配方式管理内存,内存空间为640K,高端40K为系统区。当前用户内存区空闲。对下列的请求序列:作业1申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K、作业6释放60K。画图表示出最佳适应算法进行内存分配和回收后内存的实际情况 作业1 作业5 130K 140K 作业2 190K 作业3 290K 作业4 空闲 490K 作业6 550K 作业7 600K 系统区 640K

4.3.5 基于索引搜索的动态分区分配算法 常用分配算法: 快速适应(QF)算法 伙伴系统 哈希算法 适用范围: 大、中型系统

1、快速适应(quick fit)算法(分类搜索法) 要求:将空闲分区根据容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,同时在内存中设立一张管理索引表,该表每个表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。 算法:根据进程长度,寻找能容纳它的最小空闲区链表,并取下第一块进行分配。 优点:查找效率高;既能保留大的分区,也不会产生内存碎片。 缺点:分区归还主存时算法复杂,系统开销较大;分配空闲分区时是以进程为单位,一个分区只属于一个进程,存在一定的浪费,且空闲分区划分越细,浪费越严重。

2、伙伴系统(buddy system) 伙伴系统:内存分区的大小为2k字节,l<=k<=m,其中:2l表示分配的最小分区的大小,而2m表示分配的最大分区的大小,通常2m是整个可分配内存的大小。空闲分区按分区的大小进行分类,对具有相同大小的所有空闲分区单独设立一个空闲分区双向链表,不同大小的空闲分区形成了k个空闲分区链表。 一个大小为2k,地址为x的内存块,其伙伴块的地址为buddyk(x)

2、伙伴系统(buddy system) 伙伴系统的分配算法: 伙伴系统的回收: 当有一个进程申请K字节时,首先计算一个i值,使2i-1<n<=2i,然后在空闲分区大小为2i的空闲分区链表中查找:若找到,则把该空闲分区分配给进程;否则,表明长度为2i的空闲分区已经耗尽,则在分区大小为2i+1的空闲分区链表中寻找,若存在2i+1的空闲分区,则把该空闲分区分为相等的两个分区,其中一个分区用于分配,另一个则加入分区大小为2i的空闲分区链表中。若不存在2i+1的空闲分区,则查找2i+2的空闲分区…… 伙伴系统的回收: 当一个进程释放内存时,回收过程需要查找该分区的伙伴是否也空闲,如果空闲,则与伙伴合并起来形成一个大分区。一次回收也可能要进行多次合并。

2、伙伴系统(buddy system) 伙伴系统分配举例: 假设内存的大小最初为256 KB,内核请求21KB的内存。 伙伴系统分配图

3、哈希(Hash)算法 分类搜索算法与伙伴系统算法的缺点:选择合适空闲链表的开销比较大,时间性能受影响。 哈希算法:利用哈希快速查找的优点,以及空闲分区在可利用空间表中的分布规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时,根据所需空闲分区大小,通过哈希函数计算,即得到在哈希表中的位置,从而得到相应的空闲分区链表,实现最佳分配策略。

4.3.6 可重定位分区分配 1、紧凑 引入紧凑的原因 紧凑 图 4-11 紧凑的示意 4.3.6 可重定位分区分配 1、紧凑 引入紧凑的原因 连续式分配中,总量大于作业大小的多个小分区不能容纳作业。 紧凑 通过作业移动将原来分散的小分区拼接成一个大分区。 作业的移动需重定位。 图 4-11 紧凑的示意

2、动态重定位 什么是动态运行时装入方式? 动态重定位:地址变换过程是在程序执行期间,随着对每条指令或数据的访问自动进行的。 动态重定位需要硬件地址变换机构的支持。

2、动态重定位 图 4-12 动态重定位示意图 重定位寄存器 load 1,2500 365 相对地址 10000 load 1,2500 load 1,2500 365 2500 10000 10100 100 12500 2500 + 15000 5000 作业J 处理机一侧 存储器一侧 图 4-12 动态重定位示意图

3、动态重定位分区分配算法 图 4-11 动态分区分配算法流程图

4.4 对换(Swapping)

4.4.1 多道程序环境下的对换技术 1、对换的引入 2、对换的类型 4.4.1 多道程序环境下的对换技术 1、对换的引入 对换:是指把内存中暂不能运行的进程,或暂时不用的程序和数据换出到外存上,以腾出足够的内存空间,把已具备运行条件的进程,或进程所需要的程序和数据换入内存。 整体对换(进程对换):以整个进程为单位 进行对换,广泛用于分时系统中,用于解决内存紧张问题,提高内存利用率。 部分对换 (页面对换或分段对换):以“页”或“段”为单位进行对换。是实现请求分页和请求分段式存储管理的基础,目的是为了支持虚拟存储系统。 2、对换的类型

4.4.2 对换空间的管理 1、对换空间管理的主要目标 对换空间的管理:把外存空间分为文件区和对换区 文件区:存放文件 4.4.2 对换空间的管理 1、对换空间管理的主要目标 对换空间的管理:把外存空间分为文件区和对换区 文件区:存放文件 管理目标:提高文件存储空间的利用率 →采用离散分配方式 对换区:存放从内存中换出的进程 管理目标:提高进程换入、换出的速度 →管理策略采用连续分配方式,较少考虑外存中的碎片问题。

2、对换区空闲盘块管理中的数据结构 3、对换空间的分配与回收 数据结构:对对换区的空闲盘进行管理。 空闲分区表:盘块号、盘块数 空闲分区链 对换空间的分配与回收:与动态分区方式时的内存分配与回收方法雷同。 分配算法:FF、NF、BF、WF等 回收操作:4种情况 3、对换空间的分配与回收

4.4.3 进程的换出与换入 1、进程的换出 选择被换出进程: 换出过程: 因素:处于阻塞状态,且优先级最低;考虑在内存驻留时间。 4.4.3 进程的换出与换入 1、进程的换出 选择被换出进程: 因素:处于阻塞状态,且优先级最低;考虑在内存驻留时间。 换出过程: 对进程换出时只能换出非共享的程序和数据段。 先申请对换空间; 启动磁盘,并将换出进程的程序和数据传送到磁盘的对换区; 若传送过程无错误,则回收对换进程所占用的内存空间,并修改对换进程的PCB; 若内存中还有换出的进程,则继续执行换出过程,直至无阻塞进程为止。

2、进程的换入 查看可换入的进程 选择换入进程 申请内存 查看PCB Set:“就绪”、已换出 换出时间、优先级 申请成功:直接将进程从外存调入内存 申请失败:先换出内存中的某些进程,再将进程调入

4.5 分页存储管理方式

离散分配方式:将一个进程直接分散地分配到许多不相邻的分区中。 离散分配三种方式: 基本思想: 允许作业存放在若干个不相邻的分区中,既可免去移动内存信息而产生的工作量,又可充分利用主存空间,尽量减少主存碎片。 离散分配方式:将一个进程直接分散地分配到许多不相邻的分区中。 离散分配三种方式: 分页存储管理(考虑存储器利用率) 分段存储管理(考虑用户要求) 段页式存储管理(考虑存储器利用率和用户要求) 分页存储管理方式:在分页存储管理方式中,如果不具备页面对换功能,则是基本分页存储管理方式,或称为纯分页存储管理方式。 不具有支持实现虚拟存储器的功能 要求把每个作业全部装入内存后方能运行

4.5.1 页面与页表 1、页面和物理块 页面:将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面(page)或页。 页框:把内存空间分成与页面相同大小的若干个存储块,称为(物理)块或页框( frame) 内存的分配以块为单位,并允许将一个进程的若干页分别装入到多个不相邻的物理块中。 页内碎片的形成。

1、页面和物理块 页面大小 结论:页面的大小应选择得适中,且页面大小应是2的幂,通常为1KB~8 KB。 1)页面小: 优点:使内存碎片减小,从而减少了内存碎片的总空间, 有利于提高内存利用率; 缺点:使每个进程占用较多的页面,从而导致进程的页表过长,占用大量内存;还会降低页面换进换出的效率。 2)页面大: 优点:可以减少页表的长度,提高页面换进换出的速度, 缺点:会使页内碎片增大 结论:页面的大小应选择得适中,且页面大小应是2的幂,通常为1KB~8 KB。

2、地址结构 分页地址结构:页号+页内地址 一页的大小为2的整数次幂 地址的高位部分为页号 低位部分为页内地址 页面大小为:212=4KB 空间最多允许有1M页: 220=1M 32位地址

2、地址结构 页号P和页内地址d的求法 设A — 逻辑地址空间中的地址 L — 页面大小 则 页号P = INT [ A / L ] 页内地址d = [A] MOD L 例 :A = 2170 B L = 1 KB P = INT [ A / L ] = INT [ 2170/1024 ] = 2 d = [ A ] MOD L = [ 2170 ] MOD 1024 =122

3、页表 页表由中存放着块号,通常还包括一存取控制字段。 作用:实现从页号到物理块号的地址映射 系统为每个进程建立的一张页面映射表。 图 4-14 页表的作用

4.5.2 地址变换机构 1、基本的地址变换机构 任务:实现从逻辑地址到物理地址的转换 通过设置页表寄存器实现,其中: 利用页面映射表,实现将逻辑地址中页号,转换为内存中的物理块号。 1、基本的地址变换机构 通过设置页表寄存器实现,其中: 对于较小系统,页表的功能可以由一组专门的寄存器来实现,一个页表项用一个寄存器,具有很高的访问速度。但寄存器成本较高。 现代计算机页表都很长,因此页表驻留在内存中。只在系统中配置一个页表寄存器(PTR),用于存放运行进程的页表始址和页表长度。

1、基本的地址变换机构 N ① ② ③ 页表始址+页号*页表项长度 图 4-15 分页系统的地址变换机构

例:某分页系统,主存容量为64K,页面大小为1K,对一个4页大的作业,其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址3500转换为物理地址的地址转换图 逻辑地址3500: 1.页号=3500/1K=3 2.页内地址=3500 MOD 1024=428, 3.查页表找到对应得物理块为7,物理地址=7*1K+428=7596

2、具有快表的地址变换机构 问题的提出:由于页表是存放在内存中的,这使CPU每次要存取一个数据时,都要两次访问内存。使计算机的处理速度降低近1/2。 “联想存储器“或“快表”:为了提高地址的变换速度,在地址变换机构中,增设的一个具有并行查寻能力的特殊高速缓冲存储器。 快表作用:存放当前访问的那些页表项。 快表效果:取决于对快表的访问命中率。 快表的大小:通常存放16-512个页表项。

2、具有快表的地址变换机构 ② ① ③ ④ 图 4-16 具有快表的地址变换机构

4.5.3 访问内存的有效时间 内存的有效访问时间(EAT):从进程发出指定逻辑地址的访问请求,经过地址变换,到内存中找到对应的实际物理地址单元并取出数据,所需花费的总时间。 假定访问一次内存的时间为t,λ为查找快表所需要的时间,a为快表的命中率,则: 基本分页存储管理方式中:EAT=2t 引入快表的分页存储管理方式中: EAT=a × λ+(t+ λ)(1-a)+t=2t+ λ-t × a

例:在一个引入了快表的分页存储系统中,页表放在内存中,多数活动页表项都可以存在快表中。假定一次内存访问时间是100ns,查找快表的时间为20ns,若快表的命中率是85%,则访问内存的有效时间为多少?若快表的命中率为50%,那么访问内存的有效时间为多少? 解:当快表的命中率为85%时,有效存取时间为: EAT=0.85×20+(100+20)×(1-0.85) + 100=135ns 当快表的命中率为50%时,有效存取时间为: EAT=0. 5×20+(100+20)×(1-0.5) + 100=170ns

4.5.4 两级和多级页表 现代大多数计算机系统,都支持非常大的逻辑地址空间,页表非常大,要占用相当大的内存空间。 4.5.4 两级和多级页表 现代大多数计算机系统,都支持非常大的逻辑地址空间,页表非常大,要占用相当大的内存空间。 例如32位的逻辑地址空间的分页系统,规定页面大小为4KB(占12位),则在每个进程页表中的页表项可达1M(20位)个,占4MB(每个页表项占4B)的内存空间,而且要求连续存放。 一般采用下面两个方法来解决这一问题。 1)对页表所需的存储空间,采用离散的分配方式; 2)只将当前需要的部分页表项调入内存,其余的表项仍驻留在磁盘上,需要时再调入。

1、两级页表(Two-Level Page Table) 方法:针对难以找到大的连续内存空间以存放页表的问题,采用将页表进行分页的办法,使每个页面的大小与内存物理块的大小相同,并进行编号。 实现了离散地将每个页表的页面分别放在不同的物理块中的目的。 外层页表(Outer Page Table):为离散分配的页表页面建立的一张页表,该页表的每个页表项中记录了页表页面的物理块号。 图 4-17 两级页表逻辑地址结构

1、两级页表(Two-Level Page Table) 第0页页表 1 1 4 1011 1 2 6 1 1078 … 2 … 3 2 1023 4 第1页页表 … 5 114 1 115 6 n 2 1742 7 … … … 外部页表 1023 114 第n页页表 115 1468 1 … 2 1468 … … 1023 … 图 4-18 两级页表结构

1、两级页表(Two-Level Page Table) 具有两级页表的地址变换机构图

2、多级页表 对于32机器采用两级页表结构是合适的,但对于64位机器需采用三级、四级页表结构。

4.5.5 反置页表 1、反置页表的引入 反置页表的引入:现代计算机系统,进程的逻辑地址空间很大,为减少页表占用的内存空间,所以引入了反置页表。 反置页表:为每个物理块设置一个页表项,内容包括页号和页号隶属进程的标识符,并将它们按物理块的编号排序。

2、地址变换 根据进程标识符和页号检索反置页表 反置页表地址变换示意图 检索到匹配的页表项,则该页表项的序号i与页内地址就直接拼接成物理地址。 未检索到,则表明此页未装入内存。 反置页表地址变换示意图

例:某分页系统,主存容量为64K,页面大小为1K,对一个4页大的作业,其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、4500转换为物理地址。

例:某系统有224字节的内存,固定分区的大小为216字节,1)进程表中的每个表项至少要用多少位来记录分配给进程的分区?2)界限寄存器必须要有多少位? 答:1)224字节/ 216字节= 28字节,因此需要8位来存储28个分区中的一个。 2)固定分区的大小为216字节,故最大合法地址是216-1,二进制中216-1是16位,所以界限寄存器有16位。

例:在某简单分页系统中,有224字节的物理内存,256页的逻辑地址空间,且页的大小为210字节,问逻辑地址有多少位? 答:逻辑地址空间包括了256=28个大小为 210字节的页,总的逻辑地址空间是 210×28=218字节,因此需要18位的地址来表示218字节地址空间。

例:某系统的用户空间共有32个页面,每页1KB,主存16KB。试问: 1)逻辑地址的有效位是多少? 2)物理地址需要多少位? 3)假定某时刻系统为用户的第0,1,2,3页分别分配的物理块号为5,10,4,7,试将虚地址0A5CH和093CH变换为物理地址。 答:1)逻辑地址空间包括了32=25个大小为 210字节的页,总的逻辑地址空间是 25×210=215字节,因此需要15位的地址来表示215字节地址空间。 2)物理地址=主存16KB=214,因此物理地址需要14位。 3)0A5CH=000101001011100B,前5位为逻辑地址中的页号,为00010B=2,即该地址的物理块号为4,表示为5位的二进制为00100B,因此0A5CH的物理地址是001001001011100,即125CH。同样的方法求得,093CH对应的物理地址是113CH。

4.6 分段存储管理方式

4.6.1 分段存储管理方式的引入 引入分段存储管理方式, 主要是为了满足用户和程序员的下述一系列需要: 方便编程 信息共享 信息保护 动态增长 动态链接

4.6.2 分段系统的基本原理 1、分段 用户程序划分 逻辑地址 4.6.2 分段系统的基本原理 1、分段 用户程序划分 按程序自身的逻辑关系划分为若干个程序段,每个程序段都有一个段名,且有一个段号。段号从0开始,每一段也从0开始编址,段内地址是连续的; 整个程序的地址空间分成多个段,各段长度不等; 分段方式已得到编译程序的支持,根据源程序自动产生段。 逻辑地址 31 16 15 0 段号 段内地址 16位 16位

1、分段 内存划分 内存空间被动态的划分为若干个长度不相同的区域,称为物理段,每个物理段由起始地址和长度确定。 内存分配 以段为单位分配内存,每一个段在内存中占据连续空间(内存随机分割,需要多少分配多少),但各段之间可以不连续存放。

2、段表 为每个进程建立一张段映射表(段表) 每个段在段表中占有一表项 表项记录了该段在内存中的起始地址(基址)和段的长度 段表实现了从逻辑段到物理内存区的映射 段表按段号从小到大的顺序排列,并包含该进程的全部段

2、段表 图 4-19 利用段表实现地址映射

3、地址变换机构 ① TL ④ ② ③ 图 4-20 分段系统的地址变换过程

4.6.3 信息共享 分段系统的共享 分页和分段系统的共享区别 可重入代码 允许若干个进程共享一个或多个段 4.6.3 信息共享 分段系统的共享 允许若干个进程共享一个或多个段 分页和分段系统的共享区别 在分段系统中比分页系统中更容易实现共享。 可重入代码 是一种允许多个进程同时访问的代码(只读不写)。

图 4-21 分页系统中共享editor的示意图

图 4-22 分段系统中共享editor的示意图

分段优缺点 优点 缺点 便于处理变化的数据结构 便于共享 提供了虚拟存储功能 提供了动态连接的便利 便于控制存取访问 要产生外部碎片,为存储紧缩付出处理机的代价 分段的最大尺寸受到主存大小的限制 在外存中管理可变尺寸的分段比较困难 与分页一样,提高了硬件成本

课堂练习 段号 段长 内存起始地址 660 219 1 14 3330 2 100 90 3 580 1237 4 96 1952 计算[0,430], [1,10], [2,500], [3,400], [4,20], [5,100]的内存地址 [0,430]:219+430=649 [1,10]:3330+10=3340 [2,500]:段内地址越界 [3,400]:1237+400=1637 [4,20]:1952+20=1972 [5,100]:段号越界

分页和分段的主要区别

4、分页和分段的主要区别

4.6.4 段页式存储管理方式 产生背景:结合页式段式优点,克服二者的缺点 基本思想 将用户程序按内容或过程(函数)关系分为若干个段 4.6.4 段页式存储管理方式 产生背景:结合页式段式优点,克服二者的缺点 基本思想 将用户程序按内容或过程(函数)关系分为若干个段 把每个段分成大小相等的若干个页 把主存分为与页大小相等的物理块 为每个用户程序创建一张段表,存放段表起始地址和段表长度 为每个段创建一张页表 地址结构:由段号、 段内页号、页内地址组成。

1、基本原理 基本思想 内存划分:按页式存储管理方案 内存分配:以页为单位进行分配

1、基本原理 图 4-23 作业地址空间和地址结构

图 4-24 利用段表和页表实现地址映射

2、地址变换过程 地址变换过程 以段号为索引在段表中找到该段对应的页表始址 以页号为索引找到该页对应的物理块号 物理块号和页内地址构成物理地址 需要3次访存

2、地址变换过程 ① ④ ② ③ 图 4-25 段页式系统中的地址变换机构

3、段页式存储优缺点 优点 缺点 1)与分页和分段一样,提供了虚拟存储器的功能; 2)以物理块为单位分配主存,无紧缩问题,没有页外碎片 3)便于处理变化的数据结构,段可动态增长; 4)便于共享; 5)提供了动态连接的便利; 6)便于控制存取访问。 缺点 增加了硬件成本;增加了软件复杂性和管理开销;同分页系统一样仍然存在页内碎片。