 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
操作系统 第4章 存储管理习题
下载积分：1000
内容提示：操作系统 第4章 存储管理习题
文档格式：DOC|
浏览次数：5|
上传日期： 10:41:27|
文档星级：
该用户还上传了这些文档
操作系统 第4章 存储管理习题
官方公共微信 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
操作系统 第4章 存储管理习题
下载积分：800
内容提示：操作系统 第4章 存储管理习题
文档格式：DOC|
浏览次数：0|
上传日期： 01:52:56|
文档星级：
该用户还上传了这些文档
操作系统 第4章 存储管理习题
官方公共微信存储管理习题与答案作业（doc X页）
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
存储管理习题与答案作业（doc X页）
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口面试问题系列：内存管理之虚拟内存
一、虚拟内存术语
& &&&虚拟内存& && && && && && && && && && && && && && &
& && & 在存储分配机制中，尽管备用地址是主内存的一部分，它也可以被寻址。程序引用内存使用的地址与内存系统用于识别的物理地址是不同的，程序生成的地址会自动转化为机器地址。虚拟存储的大小受计算机系统寻址机制和可用的备用内存量的限制，而不受内存储位置实际数量的限制
在虚拟内存中分配给某一位置的地址使该位置可以被访问，仿佛是主存的一部分
虚拟地址空间
分配给进程的虚拟存储
可用于某进程的内存地址范围
内存中存储位置的地址
二、分段和分页的特点（虚拟与非虚拟）
内存被划分为固定大小的小块，成为页框
内存被划分为固定大小的小块，成为页框
内存未被划分
内存未被划分
程序被划分为页
程序被划分为页
由程序员给编译器指定程序段
由程序员给编译器指定程序段
页框内有内部碎片
页框内有内部碎片
没有内部碎片
没有内部碎片
没有外部碎片
没有外部碎片
有外部碎片
有外部碎片
操作系统必须为每个进程维护一个页表，以说明每页对应的页框
操作系统必须为每个进程维护一个页表，以说明每页对应的页框
操作系统必须为每个进程维护一个段表，以说明每一段的加载地址和长度
操作系统必须为每个进程维护一个段表，以说明每一段的加载地址和长度
操作系统必须维护一个空闲页框页表
操作系统必须维护一个空闲页框页表
操作系统必须维护一个内存中空闲的空洞列表
操作系统必须维护一个内存中空闲的空洞列表
处理器使用页号和偏移地址来计算绝对地址
处理器使用页号和偏移地址来计算绝对地址
处理器使用段号和偏移量计算绝对地址
处理器使用段号和偏移量计算绝对地址
当进程运行时所有页必须在内存中，除非使用了覆盖技术
当进程在运行时，并不是所有页都必须在内存页框内，只是在需要时才读入页
当进程运行时所有段必须在内存中，除非使用了覆盖技术
当进程在运行时，并不是所有段都必须在内存，只是在需要时才读入段
把一页读入内存可能需要把另外一页写到磁盘
把一段读入内存可能需要把另外一段或几个段写到磁盘
三、系统抖动
当使用虚拟内存时，并不是把全部的进程页全部调用内存，只需要在内存中调用够用的页就可以了，当需要访问外存中的程序页时，再调用即可。这样减少了一个进程在内存中的空间，可以在主存里装入更多的进程，提高对计算机系统其他设备的利用率。但是，当页交换算法不合理时，如果一个页刚被调出内存，下面又要访问它，这样如果频繁地发生这种情况，那么处理器大部分时间都消耗在内存与外存之间的页交换上了，而不是执行指令。这种情况叫做“系统抖动”。
四、地址转换
1,分页系统中的地址转换
13:05:40 上传
(57.59 KB)
分页存储管理的基本原理是：将主存空间和辅存空间分别等分为大小相等的若干页，页的大小为个字节，如（1KB），（2KB），（4KB）等，并且为每个页按顺序指定一个页号，即0页、1页、2页、…。为了叙述方便，把主存的页（物理页或绝对页）称为页面。例如，若主存空间为8KB，辅存空间为16KB，页的大小为1KB，则主存空间可分为8个页面，其页面号为0～7；辅存空间可分为16个页，其页号为0～15。当程序运行时，以“页”为单位进行地址映射，即操作系统以页为单位把逻辑页从辅存调入主存，存放在物理页面上，供CPU执行。在分页存储管理机制中，把逻辑页对应的逻辑地址称为线性地址。
　在分页存储管理中，需要解决的关键问题是：选择哪一个物理页存放调入的逻辑页？如何将线性地址转换为物理地址？为了解决这些问题，系统为每一个页建立一个页表，保存在主存中，存放页的若干信息，如页号、容量、是否装入主存、存放在主存的哪一个页面上等。
　　CPU访问某页时，首先要查找页表，判断要访问的页是否在主存，若在主存为命中，否则为未命中。然后将未命中的页按照某种调度算法由辅存调入主存，并根据逻辑页号和存放的物理页面号的对应关系，将线性地址转换为物理地址。
　　页表在存储器中的位置由页表地址寄存器定位。页表中记录的状态信息为：第1项页号指示逻辑页；第2项特征位记录该逻辑页是否装入主存，“0”表示未装入，“1”表示已装入；第3项记录该逻辑页装入主存所存放的物理页的页面号，即1号逻辑页从辅存调入主存后，存放在第7号物理页面上。
　　存储单元的物理地址由页面号和页内地址两部分组成。 8KB主存的页内地址由地址线A9～A0提供，可寻址1KB的页内存储空间，地址范围为0～1 023；页面号由高3位地址线A12～A10提供，8个页面的页面号为0～7。由此可以看出，页面存储单元的物理地址为
　　物理地址＝页的大小×页面号＋页内地址
　　线性地址的确定方法与物理地址的确定方法完全相同，也是由页号和页内地址两部分组成，如图5.37（b）所示。16KB辅存空间可分为16页，页内地址由地址线A9～A0提供，其页号0～15由高4位地址线A13～A10提供。
13:15:59 上传
(28.63 KB)
　　在进行地址转换时，由于逻辑页和物理页的大小相等，它们的页内地址是相同的，所不同的是页号，只要将线性地址的页号转换为物理地址的页面号即可。在图5.36中，给出1号逻辑页中某条指令访问数据的逻辑地址为2＝1 476，它存入主存7页面上所对应的物理地址为1 024×7＋452＝7 620。
2,分段系统中的地址转换
13:16:19 上传
(44.17 KB)
分段存储管理的基本原理是：按程序的逻辑结构，以段为单位划分，各个段的长度因程序而异。为了说明逻辑段的各种属性，系统为每一个段建立一个段表（驻留在内存），记录段的若干信息，如段号、段起点、段长度和段装入情况等。CPU通过访问段表，判断该段是否已调入主存，并完成逻辑地址与物理地址之间的转换。
　　逻辑地址由段号S和段内地址W组成，段号S相当于逻辑段的段名，它表示该逻辑段的起始地址。在进行地址转换时，操作系统用S检索段表，段表中记录的信息1表明该段已调入主存，b是S段装入主存的起始地址，因此该逻辑地址对应的物理地址为b＋W。
　　在分段存储管理方式中，由于段的分界与程序的自然分界相对应，所以具有逻辑独立性，易于程序的编译、管理、修改和保护，也便于多道程序共享。但是，因为段的长度参差不齐，起点和终点不定，给主存空间分配带来了麻烦，容易在段间留下不能利用的“零头”，造成浪费
3、段页式系统中的地址转换
13:16:37 上传
(46.13 KB)
分页存储管理的主要特点是主存利用率高且对辅存管理容易，但模块化性能差；分段存储管理的主要特点是模块化性能好，但主存利用率不高且对辅存的管理比较困难。
段页存储管理是将分段存储管理和分页存储管理结合起来的一种折中方案。它首先将程序按其逻辑结构划分为若干个大小不等的逻辑段，然后再将每个逻辑段划分为若干个大小相等的逻辑页。主存空间也划分为若干个同样大小的物理页。辅存和主存之间的信息调度以页为基本传送单位，每个程序段对应一个段表，每页对应一个页表。CPU访问时，段表指示每段对应的页表地址，每一段的页表确定页所在的主存空间的位置，最后与页表内地址拼接，确定CPU要访问单元的物理地址
段页存储管理方式综合了段式管理和页式管理的优点，但需要经过两级查表才能完成地址转换，消耗时间多。
五、置换策略
置换算法有：最佳置换算法OPT、FIFO置换算法、最少使用页面置换算法、最近未使用页面置换算法、时钟页面置换算法等
OPT算法是理论算法，它将不再使用的页面换出，而实际中不能预知哪个页面不再使用，但是这个算法是最优算法，可以作为评测其他算法的性能。
FIFO算法：按照页面装进内存的时间进行置换，越老的页面最先被换出，不管该页面是否经常使用，这样就有可能导致缺页率增加，导致页面置换次数增加。
最少使用页面置换算法：按照上次使用时间进行排序，将离上次使用时间最长的页面换出，可以采用栈的数据结构，每次页面被访问将该页面号放在栈顶。
最近未使用页面置换算法：设置引用位R，每次调用将R=1，系统每个一段时间将R=0，当进行置换式检查哪个页面为零说明近期不会再使用，可以将其换出。
时钟页面置换算法：采用应用为R，当R=1说明被引用过，这种方法是FIFO的改进，根据装入内存时间和是否被引用过作为标准，首先从时间最长项检查，若R=0则置换出，若为1则检查下一项并将R=0。若全部R=1，则按照FIFO方法进行置换。
选择好置换的页面后，如何进行置换呢？
首先判断被置换的页面是否被修改过，若没有则可以直接擦出该页框，如修改过则必须首先保存到外存中，然后再读入新页面。
页面缓冲技术：不必先保存，因为每次都保存一个页面增加了IO操作，消耗过大。缓冲技术可以将被修改过和未修改过的页面存在缓冲区，然后对被修改过的页面进行批量保存，减少了IO操作。未修改的页面进行缓冲是为了防止在近期内被调用，不必再从外存调入内存，若在一段时间内不被调用则批量消除。
（感谢来源：http://blog.csdn.net/xue/article/details/8960770）
更多相关文章
为了开学的面试,就在博客里总结一下面试会问到的问题,今天就来谈谈内存管理,看到一篇文章非常不错,/,深入浅出,推荐大家去看看!
Objective-C使用一种(Retain Count)引用计数的机制来管理内存,在OC中,每个对象都持有自己 ...
我们都知道,在linux的内存管理机制中,采用了虚拟内存管理机制.linux内核的虚拟地址空间共4G,分为两部分内核空间(3G ~4G)以及用户空间(0~3G).内核空间对于每个进程而言都是可见的,而用户空间对于每个用户而言是独占的,其他用户不可见. 我们都知道,程序最终是要运行在物理内存之中的,所 ...
Java的内存分配有三种, 1.静态存储区:内存在程序编译时就分配好了,比如静态变量: 2.栈区:各种原始数据类型的局部变量都是在栈上创建的,当程序退出该变量的作用范围的时候,这个变量的内存会被自动释放. 3.堆区:对象(包括数组)都是在堆中创建的.程序在运行的时候用new关键字来创建对象,对象 ...
原文链接:http://blog.csdn.net/yeming81/article/details/2047879 本文背景: 在编程中,很多Windows或C++的内存函数不知道有什么区别,更别谈有效使用:根本的原因是,没有清楚的理解操作系统的内存管理机制,本文企图通过简单的总结描述,结合实例来 ...
全面介绍Windows内存管理机制及C++内存分配实例
十分感谢MS社区的帖子,讲得很好~
http://social./Forums/zh-CN/2219/thread/afc1269f-fe08-4dc7-bb94 ...
本文背景: 在编程中,很多Windows或C++的内存函数不知道有什么区别,更别谈有效使用:根本的原因是,没有清楚的理解操作系统的内存管理机制,本文企图通过简单的总结描述,结合实例来阐明这个机制. 本文目的: 对Windows内存管理机制了解清楚,有效的利用C++内存函数管理和使用内存. 本文内容: ...
转自:http://blog.csdn.net/yeming81/article/details/2046193 本文基本上是windows via c/c++上的内容,笔记做得不错.. 本文背景: 在编程中,很多Windows或C++的内存函数不知道有什么区别,更别谈有效使用:根本的原因是,没有清 ...
以前应用程序必须在载入内存后才能执行,现代操作系统的内存管理为解决这个问题而引入了虚拟内存. 本质上虚拟内存就是要让一个程序的代码和数据在没有全部载入内存时即可运行.运行过程中,当执行到尚未载入内存的代码,或者要访问还没有载入到内存的数据时,虚拟内存管理器动态地将这部分代码或数据从硬盘载入到内存中. ...
建立模型 第一步:在Models文件夹上点右键 &添加&类
类的名称自定,我用AdminViewModels命名的 因为是讲基本使用,我这里不做任何扩展. 第二步:添加如下命名空间 using S ...
首先是xml布局文件: &LinearLayout xmlns:android=&q ...
一.GProfile简介
GProfile是gcc的一个工具,用于对应用程序的 ...
http://blog.csdn.net/zhao_3546/article/details/ 最近使用 Help --& Check for Updates 升级了Eclipse部分插件,之后 ...
遇到的问题:一个条件查询与多个条件查询,所用到的方式不一样 参考文档: http://ww ...
最近,要在毕业论文的c++代码中调用OGC的服务,所以就上网查了一下,主要有以下几种方案:
1.使用gSOAP,跨平台,gSOAP是一个开源的项目,用它可以方便的使用c/c++地进行SOAP 客户端和服务 ...
昨天下班的时候,有一个同事问我对EXT熟不熟,我自然是不熟悉的.然后他又说现在有个项目基于SSH的,遇到一个问题,调了一天了,没有任何进展,SSH我也不熟悉,不过比较奇怪什么样的问题一整天没有任何眉目,所以就好奇的去 ...
Bear and Blocks time limit per test 1 second
在许多经典的操作系统教科书中,总是把进程定义为程序的执行实例,它并不执行什么, 只是维护应 ...
今天下午在调试测试VPS机器的时候,出现&504 gateway time-out&错误提示.VPS是安装的LNMP一键安装包,关于这个错误之前还没有见过,网上看到比较多的是502错误,对于504 ...一、存储器（storage, memmory）
能接收数据和保存数据、而且能根据命令提供这些数据的装置。
主存储器用于保存进程运行时的程序和数据。
由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，引入了寄存器和高速缓存。
为了扩充主存储器的存储空间，在磁盘上建立磁盘缓存，操作系统自动实现主存储器和磁盘缓存之间的程序和数据的调进调出，从而面向用户提供比实际主存容量大得多的存储空间。
寄存器、高速缓存、主存储器、磁盘缓存属于操作系统存储管理范畴，掉电后所存储的信息不复存在。
固定磁盘和可移动介质属于设备管理的对象，所存储的信息将被持久保存。
二、地址转换
1.程序的编译、链接、装入
源程序是不能直接执行的，源程序要经过编译、链接、装入这3个阶段处理后才能装入主存运行。
编译：将源程序翻译成等价的若干目标代码（目标模块）。
链接：把多个目标模块链接在一起，形成一个完整的可重定位目标程序（装载代码模块）。
装入：将装载代码模块装入系统分配的主存区。
2.地址转换
（1）目标程序的逻辑结构
逻辑地址：目标程序所使用的地址称为逻辑地址，也称为程序地址 、虚地址 。
逻辑地址空间：逻辑地址集合称为逻辑地址空间，也称为程序地址空间、虚地址空间。它的编址总是从0开始的，可以是一维的，也可以是二维的。
（2） 内存的物理组织
物理地址：
&&把内存分成若干个大小相等的存储单元，每个存储单元占8位，称作字节（byte）。每个单元给一个编号，这个编号称为物理地址（内存地址、绝对地址、实地址），
物理地址空间：
& 物理地址的集合称为物理地址空间（主存地址空间），它是一个一维空间。
（3）地址转换
将程序使用的逻辑地址变换成主存中的物理地址的过程称为地址转换，也称为地址重定位、地址映射
地址重定位有两种方式：
①静态地址重定位
②动态地址重定位
①静态地址重定位
目标程序被装入内存时完成程序的逻辑地址到内存物理地址的转换。&&&&&&&&&
物理地址=装入内存首地址+逻辑地址
例如，程序装入内存的首地址为1000，则装入程序就按物理地址=1000+逻辑地址对程序中所有地址部分进行修改，修改后指令Load
A，200就变为Load A，1200
优点：不需要硬件支持，易于实现。&
缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动位置。
这种技术只在早期单用户单任务系统中使用过。
②动态地址重定位
目标程序装入内存时，不进行地址转换。程序装入主存的起始地址置入重定位寄存器中，程序执行过程中，每次访问内存之前，将要访问的逻辑地址加上重定位寄存器的值，从而转换为内存物理地址。
允许程序在主存中移动，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。
便于多个进程共享同一个程序的代码。
一个程序不一定要求占用一个连续的内存空间。
动态地址重定位的代价：
需要硬件的支持。
实现存储管理的软件算法较为复杂。
现代计算机系统中都采用动态地址重定位。
三、 存储保护
在多道程序设计的环境下，内存中有系统程序和多个用户程序同时存在，系统程序和多个应用程序在主存中各有自己的存储区域，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？这就是存储保护所要解决的问题。
界地址寄存器被广泛使用的一种存储保护技术机制比较简单，易于实现.
实现方法有两种：上下界保护，基址、限长寄存器保护。
1.上下界保护
下界寄存器：存放程序装入内存后的首地址
上界寄存器：存放程序装入内存后的末地址
判别式：（下界寄存器）& ≤&
物理地址& ＜& （上界寄存器）
有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1005。
下界寄存器：500
上届寄存器：1500
&& 逻辑地址＋装入内存的首地＝ 物理地址
1、500＋500 ＝
500& ≤&& 1000
＜& 1500√
2、345＋500 ＝
845&&&&&&&
845& ＜& 1500√
500& ≤&& 1505
2.基址、限长寄存器保护
基址寄存器：存放程序的起始地址。
限长寄存器：程序的长度（单位：字节）
判别式：0 ≤逻辑地址〈（限长寄存器）
如果未越界，则按此地址访问主存，否则将产生程序中断——越界中断（存储保护中断）
有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1005。
&& 基址寄存器：500
&& 限长寄存器：1000
500& ＜& 1000√
345& ＜& 1000√
0& ≤&& 1005
3.两种存储保护技术的区别
（1）寄存器的设置不同；
（2）判别式中用的判别条件不同
上下界寄存器保护法用的是物理地址
基址、限长寄存器保护法用的是程序的逻辑地址
对于合法的访问地址这两者的效率是相同的，对不合法的访问地址来说，上下界存储保护浪费的CPU时间相对来说要多些。
四、存储管理的功能
(1)地址转换
&将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程.
(2)存储保护
保证用户程序(或进程映象)在各自的存储区域内操作，互不干扰。
(3)主存分配和回收
&按照一定的算法把某一空闲的主存区分配给进程，进程终止后回收主存区。
(4) 存储扩充
向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器，称为虚拟存储器。
&现代计算机操作系统都采用了虚拟存储技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。
连续存储空间管理
主存分配广泛采用连续分配方式。
一、单一连续分配（单个分区）
最简单的存储管理方式，用于多道程序设计技术之前。
内存分为系统区和用户区，系统区由操作系统使用。用户区作为一个连续的分区分配给一个作业。
优点：方法简单，易于实现
&1.仅适用于单道程序，只能用于单用户单任务的操作系统
2.系统资源利用率低
分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多个用户程序同时存在系统内存中，即共享内存空间。
按分区划分方式可分为固定分区和可变分区。
二、 固定分区存储管理
1.基本思想
把内存的用户区预先划分成多个分区，每个分区大小可以相同，也可以不同。（分区的划分由计算机的操作员或者由操作系统给出，并给出主存分配表）
分区个数固定，分区的大小固定。
一个分区中可装入一个作业，作业执行过程中不会改变存放区域。
2.主存分配表
为了说明各分区的分配和使用情况，需设置“主存分配表”，记录各分区及其使用情况。
主存分配表内容：分区号，分区的起始地址，长度，占用标志。
3.主存空间分配
主存存分配程序检索主存分配表，从中找到还未分配且大小满足要求的分区，则将此分区分配给该作业。若没找到满足条件的分区，则拒绝为该作业分配主存。
４.固定分区性能分析
在作业大小和出现频率均已知的情况下，固定分区是合适的。在这种情况下分区的大小选择与作业大小相当，这样内存的使用效率较高。
但是若作业的大小和出现的频率不知道时，势必造成分区的大小和作业的大小相差甚远，这样就会造成存储空间的浪费，从而影响整个系统的效率。
缺点：碎片问题，主存利用率很低。
三、 可变分区存储管理（动态分区）
1.基本思想
&&内存不是预先划分好的，而是在系统运行的过程中建立分区.当作业装入主存时，根据作业所需要的主存容量查看是否有足够的主存空间，若有则按需要分割一个分区给该作业；否则令该作业等待.
分区长度不固定,分区个数不固定.
这种存储管理的方法克服了固定分区严重浪费主存的问题，提高了主存资源的利用率。
2.实现动态分区需要的数据结构
在动态分区存储管理中，要有相应的数据结构来登记空闲区信息，它包括空闲区的大小和位置。
不同系统根据设计要求采用不同的结构。常用的有表结构和链结构。
系统还要设置了等待分区队列，当系统中无空闲区或无满足要求的空闲区时，则把申请者送入等待队列中，等待别的进程释放内存之后再唤醒队列中的进程。
3.分区分配算法
空闲区表（链）中的空闲区可按一定规则排列，例如按空闲区大小的升序（降序）排列；按空闲区地址升序（降序）组织。
根据空闲区表（链）排列方法不同，对应不同的分配算法，常用的可变分区分配算法有最先适应算法，下次适应分配算法，最优适应算法、最坏适应算法等。
(1)最先适应算法
空闲区按地址从小到大的次序排列。
分配：当进程申请大小为SIZE的内存时，系统顺序查找空闲区表（链），直到找到容量满足要求（≥SIZE）的空闲区为止。从该空闲区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区，但要修改其首址和大小。
优点：这种算法是尽可能地利用低地址部分的空闲区，而尽量地保证高地址部分的大空闲区，有利于大作业的装入。
缺点:主存低地址和高地址分区利用不均衡。在低地址部分,集中了许多非常小的空闲区(碎片),降低了主存的利用率。
（２）下次适应分配算法
最先适应算法的变种。
总是从空闲区上次扫描结束处顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止，分割一部分给作业，剩余部分仍作为空闲区。
(３)最优适应算法
空闲区按容量递增的次序排列。
分配：当进程申请存储空间，系统顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止。
采用最优适应算法选中的空闲区是满足容量要求的最小空闲区。
选中的空闲区是满足容量要求的最小空闲区，而不致于毁掉较大的空闲区。
空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储空间的浪费。
(４)最坏适应算法
为了克服最佳适应算法把空闲区切割得太小的缺点，人们提出了一种最坏适应算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，剩余的部分仍是一个较大的空闲区。避免了空闲区越分越小的问题。
要求空闲区按容量递减的顺序排列。
分配：进程申请存储区时，检查空闲区表（链）的第一个空闲区的大小是否满足要求，若不满足则令进程等待；若满足则从该空闲区中分配一部分存储区给用户，剩下的部分仍作为空闲区。
当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。
另一方面每次仅作一次查询工作，查找效率高。
4.可变分区的回收
&&&当某个进程释放某存储区时，系统首先检查释放区是否与系统中的空闲区相邻，若相邻则把释放区合并到相邻的空闲区中去，否则把释放区作为一个空闲区插入到空闲区表的适当位置。
(a)释放区与前空闲区相邻：将释放区与前空闲区合并为一个空闲区。其首址仍为前空闲区首址，大小为释放区大小与空闲区大小之和。
(b)释放区与后空闲区相邻：则把释放区合并到后空闲，首地址为释放区首地址，大小为二者大小之和。
(c)释放区与前后两个空闲区相邻：将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三个区大小之和，并取消原后空闲区表目。
(c)释放区不与任何空闲区相邻：将释放区作为一个空闲区，将其大小和首址插入到空闲区表的适当位置。
可变分区存储管理分析
1.有助于多道程序设计
2.不需过多硬件,仅需界地址寄存器用于存储保护
3.所采用的算法都比较简单,易于实现
1.碎片问题
由于空闲区的大小与申请内存的大小相等的情况是很少的，绝大多数情况是从一个空闲区中切去一块，剩下的部分作为一个空闲区仍留在空闲区表中，随着时间的推移，空闲区的发展趋势是越来越小，直至不能满足任何用户要求。
这种不能被任何用户使用的极小的空闲区称为碎片。碎片的出现造成了存储空间的浪费。
2.分区大小受主存容量限制,无法扩充主存容量
四、可重定位分区存储管理
解决碎片问题的一种简单方法是采用可重定位分区分配.
1.基本思想
例:内存中现有3个空闲区，如图所示，现有一作业到达，要求获得30k内存空间，没有分区满足容量要求，若想把作业装入，可将内存中所有作业进行移动，这样把原来分散的空闲区汇集成一个大的空闲区。
将内存中的作业进行移动,使它们连接在一起,把原来分散的多个小分区拼接成一个大的空闲区.这个过程称为”紧凑”或”移动”.
需解决的问题:每次”紧凑”后,程序或数据装入的物理地址变化,采用动态重定位.
2.动态重定位分区分配算法
与动态分区分配算法基本相同,差别在找不到足够大的空闲分区时进行”紧凑”.
分区分配方案评价
1.实现了主存共享,有助于多道程序设计,提高了系统资源的利用率;
主存利用率:可重定位分区分配&动态分区分配&固定分区分配
2.与后面所介绍的存储管理方式相比,实现分区分配所使用的表格,占用的存储空间较少,算法也相对简单;
3.实现存储保护的措施也较简单。
1.主存仍不能充分利用,除了可重定位分区法外,都存在碎片问题.
2.采用”紧凑”方法,虽解决了碎片问题,但系统开销太大.
3.不能实现对主存的扩充.因此作业大小受到主存可用空间限制.
把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域
程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）
覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间
一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖
&& 对用户不透明，增加了用户负担。
例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与暂驻模块也是一种覆盖结构。
现代操作系统极少使用覆盖技术。
为平衡系统负载，通过选择一个进程，把其暂时移出到磁盘，腾出空间给其他进程使用，同时把磁盘中的某个进程再换进主存，让其投入运行，这种互换称对换。
多用于分时系统中
选择原则（即：将哪个进程换出内存？）
&时间片轮转法或基于优先数的调度算法，通常把时间片耗尽或优先级较低的进程换出，因为短时间内它们不会被投入运行。
对换时机（即：何时需发生对换）
&批处理系统中，当有进程要求动态扩充主存且得不到满足时可触发对换；
分时系统中，对换可与调度结合在一起，每个时间片结束或执行I/O操作时实施。 &
与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；
交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。
覆盖只能覆盖那些与覆盖段无关的程序段。
上节所介绍的连续分配方式，会出现碎片问题，虽然采用“紧凑”的方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销，而无实用价值。如果允许将一个进程直接分散地装入到许多不相邻的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式。
离散分配方式：给进程分配几个不连续的内存区域，并可保证进程的正确执行。
离散分配方式按分配基本单位不同分为分页存储管理和分段存储管理。
分页存储管理
把一个进程的逻辑地址空间分成若干大小相等的片，每个片称为页面或页 。从0开始编制页号。
页面的大小应选择适中，一般页的大小为2的幂，通常为512 B～8 KB。
2.逻辑地址
分页存储管理逻辑地址分为两部分：地址的高位部分为页号，低位部分为页内位移。
3.物理块（页框）
把主存的物理地址空间分成和页面大小相等的区，每个区称为物理块或页框。从0开始编制块号。
4.物理地址&&页号+页内位移
5.分页存储管理基本原理
&&&&&&&&&&
以页为单位进行分配。当一个进程装入内存时，将进程的多个页面分别装入内存的多个物理块中，这些物理块可以是不相邻的。
进程的各个页面分散存放在主存不相邻的物理块中，系统如何知道页面和物理块的对应关系。
这就需要系统为每个进程建立一个页表，用来登记页号和块的对应关系和有关信息。
一个进程有多少个页面，页表就有多少项。
进程的页表大多驻留在内存中，页表在主存的首地址和长度存放在该进程的进程控制块。
二、地址转换
把程序的逻辑地址转换成内存的物理地址。
进程的页表放在内存中，页表在主存的首地址和页表长度保存在本进程的PCB中。
系统设置了一个页表寄存器，当系统调度一个进程运行前，系统把该进程的页表首地址和页表长度送入到该页表寄存器中，以便地址转换时使用。
三、快表和相联存储器
在页式存储技术中，我们可看到每次存取数据，就要做两次访问内存的工作，一次是地址转换查页表时要作一次访问内存的工作，然后是根据转换后的物理地址访问内存存取数据，这样存取速度降低一倍，将会影响整个系统的使用效率。可见，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。
为了提高提高地址变换速度，通常都设置一个专用的高速存储器，用来存放页表的一部分，这种高速存储器称为相联存储器（associative
memory），存放在相联存储器中的页表称快表。相联存储器的存取时间是远小于主存的，但造价高，故一般都是小容量的，只能存放几十个页表项。
在采用了快表的系统中，通常采用“双管齐下“的方针，一方面检索相联存储器，而同时又检索内存的页表，在相联存储器中一旦检索到所要的块号，便立即停止页表的检索，若相联存储器中找不到所要的块号，就应利用主存中页表查找的到，并将此页表项填入相联存储器中。
根据程序执行局部性的特点，所以快表的命中率可达90%以上。
硬件能自动分离出页号和页内地址，但我们只能通过计算才能得到。计算时要注意：
(1)逻辑地址以十六进制、八进制、二进制的形式给出
将逻辑地址转换成二进制的数；
按页的大小分离出页号和页内地址（低位部分是页内地址，高位部分是页号）；
根据题意产生页表；
将页内地址直接复制到物理地址的低位部分；
以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址的高位部分，从而形成内存物理地址。
(2)逻辑地址以十进制数给出
按下列公式计算出页号和页内地址
页号＝逻辑地址％页大小
页内地址＝逻辑地址 mod 页大小
根据题意产生页表；
以页号查页表，得到对应页装入内存的块号
内存地址＝块号&页大小＋页内地址
四、分页存储空间的分配与回收
位示图：记录主存物理块的使用情况
主存分配算法：
计算一个进程所需要的总块数N；
查空闲块数，看是否还有N个空闲块，若没有则令进程等待；
如有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB
查位示图找出N个为“0”的位，计算对应的物理块号，将块号填入页表；
修改位示图（相应位值占用标志，空闲块数-N）；
主存回收算法
&&&进程执行结束归还主存时，根据归还的物理块号，计算出对应位在位示图中的位置，将占有标志清“0”，并将归还的块数加入空闲块数中。
五、两级页表和多级页表
当页表项很多时，仅采用一级页表需要大片边续空间，可将页表也分页,由此构成二级页表。
具体做法：把整个页表分成一张张小页表,每个小页表每个小页表称为页表页，大小与物理块相同，对小页表顺序编号,允许小页表分散存放在不连续的物理块中,为了进行索引查找,应该为这些小页表建一张页目录表,其表项指出小页表所在物理块号及相关信息。于是系统要为每个进程建一张页目录表,它的每个表项对应一个小页表,而小页表的每个表项给出了页面和物理块的对应关系,页目录表是一级页表,小页表是二级页表。
解决页表页占用主存空间的问题
进程运行涉及页面的页表页应放在主存,其他页表页使用时再调入,
在页目录表中增加特征位,指示对应的页表页是否已调入主存,
地址转换机构根据逻辑地址中的页目录位移,去查页目录表对应表项,如未调入,应产生一个”缺页表页”中断信号，请求操作系统将页表页调入主存。
分段存储管理
为了解决碎片问题，提高内存利用率引入了分页存储管理。
引入分段存储管理主要是满足用户（程序员）编程和使用上的要求。
应用程序通常是由若干程序段（模块）组成，例如由主程序段、子程序段、数据段等组成，每段具有完整的逻辑意义。在分页存储管理中，页面是信息的物理单位，与源程序不存在逻辑关系，也就难以实现以段为单位的共享、保护、动态链接等。
用户程序划分
&一个用户程序往往由几个程序段（主程序、子程序和函数等）所组成。把程序按自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段段内也从0开始编址，段内地址是连续的。
(分段是由用户或编译器负责的）
逻辑地址：段号+段内位移
注意：分段地址空间是真正二维的
以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放
记录了进程的每个逻辑段在内存中的起始地址和段长。
每个进程设置一个段表，进程分为多少段，段表就应有几项。
段表放在内存， 段表在内存首地址和段表长度存放在本进程的PCB中。
二、地址变换
段地址变换由硬件地址变换机构完成，系统设置一对寄存器
段表始址寄存器：
&用于保存正在运行进程的段表的始址
段表长度寄存器：
&用于保存正在运行进程的段表的长度
同页地址变换一样，在段地址变换过程中，也有两次访问内存的问题。为了加快访问内存的速度也可采用快速存储器组成快表。
三、段的共享
在分段系统中实现段共享，只需在每个进程的段表中为共享段设置一个段表项。
四、分段和分页的比较
分段是信息的逻辑单位，由源程序的逻辑结构所决定，用户可见，
段长可根据用户需要来规定，段起始地址可从任何主存地址开始。
分段方式中，源程序(段号，段内位移)经连结装配后地址仍保持二维结构。
分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见，
页长由系统确定，页面只能以页大小的整倍数地址开始。
分页方式中，源程序(页号，页内位移)经连结装配后地址变成了一维结构。
五、段页式存储管理方式
分页系统能解决碎片问题，提高内存利用率；分段系统能很好满足用户的需求，便于实现段的共享，保护和动态链接。将两者结合形成一种新的存储管理方式。
用户程序划分
先将用户程序分成若干个段，再把每个段分成若干个页
逻辑地址：段号+段内页号+页内位移
&& 按页式存储管理方案
&& 以页为单位进行分配
二、& 地址转换
段表：记录了每一段的页表始址和页表长度
页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）
虚拟存储管理
前面介绍的各种存储管理方式中，在装入一个作业时要求将它全部装入内存，才可运行。
&& 可能出现两种情况：
（1）有些作业所需内存空间已超出内存总容量。
（2）为提高系统资源效率，内存中同时装入多道作业，用户作业所需空间超出了内存空闲空间。
程序局部性原理
程序在执行时呈现出高度的局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。
时间局部性
一条指令被执行了，则在不久的将来它可能再被执行,典型原因是程序中的循环。
空间局部性
若某一存储单元被访问，则在不久之后，与该存储单元相邻的单元也可能被访问,典型原因是程序的顺利执行。
基于程序局部性原理，就没有必要把一个作业一次性全部装入内存再开始运行。
而是仅将当前使用部分装入主存，其余部分存放在磁盘中，启动程序运行，进程执行过程中，若所访问的程序和数据在主存时可顺利执行；若不在主存时，由系统自动将这部分信息从磁盘装入主存（部分装入），若装入时没有足够空闲物理空间，便把主存中暂时不用的信息移至磁盘（部分替换）。
这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为虚拟存储器。
一、虚拟存储器概念
虚拟存储器是为了逻辑扩充内存，以解决小内存无法运行大程序的问题而引入的，是一种以CPU时间和外存空间换取内存空间的技术（是OS中的资源转换技术），也是迄今为止逻辑扩充内存程度最彻底的技术（远强于覆盖和交换技术）。
虚拟存储器是在1961年由英国曼彻斯特大学Fotheringham提出，并在该校的atlas机器上实现的一种存储技术。从1970年后被广泛应用
1.虚拟存储器定义
在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分替换功能，为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器”。
虚拟存储器的容量受限于计算机的地址结构和可用的磁盘容量，如Intel
x的地址线是32位，则程序的可寻址范围是4G，Windows和Linux都为应用程序提供一个4G的逻辑主存。
2.虚拟存储器实现方法
虚拟存储器是建立在离散分配的内存管理技术基础上的，它主要有以下3种实现方法：
请求分页虚拟存储管理
&&&用户程序要装入内存时，仅装入当前使用的页面，启动程序运行，在运行的过程中，若发现要访问的页面不在内存，则由系统自动装入所需页面，若内存空间已满，则根据某种算法置换某个页面，以便装入新的页面。
请求分段虚拟存储管理
用户程序要装入内存时，首先把当前需要的段装入主存，启动程序运行，在运行的过程中，若发现要访问的段不在内存，则由系统自动装入所需段，若内存空间已满，则根据某种算法置换某段，以便装入新的段。
请求段页式虚拟存储管理
请求分页 + 请求分段
二、请求分页虚拟存储管理
请求分页系统必须解决以下几个问题：
（1）当程序要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？
（2）当需要把外存上的某个页面调入内存时，此时内存中没有空闲物理块，应置换哪些页面，置换策略，置换算法。
1、页表机制
为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。
驻留位：指示该页是否在内存
修改位：指示该页调入内存后是否修改
访问字段：记录该页被访问的次数，或者最近已有多长时间未被访问，共选择换出页面时参考。
外存地址：指示该页在外存上的地址。
2、缺页中断处理
在地址转换过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，准备将该页调入内存
此时应将缺页的进程挂起（调页完成唤醒）
缺页中断同一般中断的异同？
保护现场& 中断处理& 恢复现场
缺页中断是在一条指令执行期间产生和处理中断，一般中断是一条指令完成后CPU检查是否有中断；
一条指令执行时可能产生多次缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中
3.页面分配策略
&&&&进程保持物理块数固定不变,称固定分配;
&&&&进程创建时,根据进程类型和程序员的要求决定物理块数,只要有一个缺页中断产生,进程就会有一页被替换。
&&&&进程分得的物理块数可变,
称可变分配;
&&&&进程执行的某阶段缺页率较高,说明目前局部性较差，系统可多分些物理块以降低缺页率，反之说明进程目前的局部性较好,可减少分给进程的物理块数。
4.页面替换策略
&&&如果页面替换算法的作用范围是整个系统，称全局页面替换算法,它可以在运行进程间动态地分配页框。
&&如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法,它实际上需要为每个进程分配固定的页框。
固定分配和局部替换策略配合使用
进程分得的物理块数不变，发生缺页中断，只能从进程的页面中选页替换，保证进程的物理块总数不变。
策略难点：应给每个进程分配多少物理块?给少了,缺页中断率高;给多了,使主存中能同时执行的进程数减少，进而造成处理器和其它设备空闲。
& 常用固定分配算法：
&&&&①平均分配，
&&&&②按比例分配,
&&&&③优先权分配。
可变分配和全局替换策略配合使用
&&&先每个进程分配一定数目物理块,os保留若干空闲物理块,进程发生缺页中断时，从系统空闲块中选一个给进程,这样产生缺页中断进程的主存空间会逐渐增大,有助于减少系统的缺页中断次数。
&&&系统拥有的空闲页框耗尽时，会从主存中选择一页淘汰，该页可以是主存中任一进程的页面，这样又会使那个进程的物理块数减少，缺页中断率上升。
可变分配和局部替换配合使用
(1)新进程装入主存时，根据应用类型、程序要求，分配给一定数目物理块。
(2)产生缺页中断时,从该进程页面中选一个页面替换。
(3)不时重新评价进程的缺页率，增加或减少分配给进程的物理块以改善系统性能。
5、& 页面置换算法&——Page
Replacement Algorithms
当要将一页面并装入入到全满的内存中时，必须把已在内存中的某一页置换掉。用来选择置换哪一页的规则叫做页面置换算法。
颠簸（抖动）现象
&在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。例如，一个每隔几条指令就发生一次页面故障的进程称为在颠簸（因为一条指令的执行只需几纳秒，而每从磁盘上读入一个页面则常需几十毫秒）。
系统发生颠簸的原因
&&&&页面置换算法不合理
&&&&分配给进程的物理页面数太少
（1）最佳页面置换换算法（OPT算法）
从内存中置换出以后永不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。
主要用于评价其他置换算法。
（2）先进先出页面置换算法（FIFO算法）
置换驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。
实现简单：只需把进程在内存的页面按先后次序链成1个队列，并设置1个替换指针，使它总是指向内存中最老的页面。
缺点：效率不高
（3）最近最久未使用页面置换算法（LRU算法）
选择在最近一段时间最久未使用的页面予以置换。
根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使用到。
该算法理论上性能好，但实现代价高（需硬件支持，如：为进程每个内存页面设一计时器或寄存器，或为进程所有内存页面设一栈/链表）。
(4)二次机会(SC, Second
Chance）置换算法&——FIFO法的一种改进实现
实现：页表目中增设访问位R，初值为0，页面访问时置1。发生缺页中断需置换时，OS按照先进先出置换算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则将该位置0，把该页放到内存页面链表的尾端，给它第二次机会，再检查内存页面链上的下一个页面。如果查到链尾还未找到置换对象，则再从链首开始，进行第2趟扫描检查。
优点：实现简单，且性能比FIFO好很多；
缺点：运行效率低，时间开销大。
(5)时钟(Clock)置换算法&
——SC的一种改进实现
SC算法因为常需把给予二次驻留机会的页面移到链尾而降低效率，若把其所用的内存页面单向链表改为循环链表，则就不必在链中移动页面了。这种改进的SC法就是Clock法。
影响缺页次数的因素
(1) 分配给进程的物理块数
(2) 页本身的大小
(3) 程序的编制方法
(4) 页淘汰算法
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}