第四章存储管理
4.1 概述
存储器和中央处理器(CPU)一样是计算机系统的重要组成部分。它为操作系统、各种系统程序和用户程序所共享。存储器空间被划分成系统存储区（简称系统区）和用户作业存储区（简称用户区）两大部分。存储器管理讨论的主要对象是内存的用户区。
4.1.1 信息的二级存储
主存: 划分成系统存储区（简称系统区）和用户作业存储区（简称用户区）两大部分。系统区存放操作系统与硬件的接口信息（新旧PSW、定时时间、I/O工作情况）、操作系统的管理信息（PCB）和驱动程序、标准子程序等。
辅助存储器：提供大容量存储空间
4.1.2 存储器管理的功能
1．存储器管理的基本目的是：①充分发挥内存的利用率；②为用户使用存储器提供方便。
2．存储器管理的功能可以归纳为4个方面。
（1）内存分配：为多个程序分配内存空间，各程序在规定的那一部分内存空间里运行。内存分配的主要方式有静态分配和动态分配。
（2）地址重定位（地址转换）：把程序的逻辑地址变换为存储器的物理地址。地址重定位的方式有静态重定位和动态重定位。
（3）内存空间的共享与保护：对操作系统以及各用户的信息提供保护措施。
（4）内存扩充：通过软件方法扩充逻辑存储空间。
4．2 重定位
4．2．1 地址空间和存储空间
源程序经过汇编或编译后再经过连接形成程序的装配模块形式，即转换为相对地址编址形式，它是以0为基址顺序进行编址的。相对地址又叫逻辑地址或虚地址。
逻辑地址空间（简称地址空间）是逻辑地址的集合，物理地址空间（简称存储空间）是物理地址的集合。
4．2．2地址重定位
所谓地址重定位是指把程序空间中的逻辑地址转换为存储空间的物理地址的过程．又称为地址映射。
地址重定位的方式有静态重定位和动态重定位。
静态重定位是在程序目标模块装入时由装入程序完成的。装入程序把目标模块中的逻辑地址与本程序在内存中的起始地址相加得到正确的物理地址。（亦称绝对装入方式）（P96 图4.2 静态地址再定位）优点：容易实现，无需硬件支持，可由专门设计的程序来完成。
缺点：（1）程序经地址再定位后就不能再移动了，因而不能重新分配内存，不利于内存的有效利用；
（2）程序在存储空间中只能连续分配；
（3）若干用户很难共享内存中的同一程序，若要共享，则需使用各自的副本。
动态重定位是在程序运行时完成的，靠硬件地址变换机构实现。最简单的办法是利用一个重定位寄存器。在程序实际运行前，由操作系统把程序在内存的起始地址送入重定位寄存器。在程序运行期间，凡遇到访问内存的操作，就由硬件机制自动地把用户程序的相对地址与重定位寄存器的内容相加，其和就是实际访问内存的有效地址。（P97 图4.3 动态地址再定位）
优点：（1）用户程序在内存中可以移动，这有利于内存的充分利用；
（2）程序不必连续存放在内存中，只需对分散的内存使用基址-限长寄存器即可；
（3）若干用户可以共享同一程序。
缺点：需要附加的硬件支持，增加了成本，实现存储管理的软件算法比较复杂。
4.3 分区存储管理（连续分配存储管理方式）
连续分配是指为一个用户程序分配一个连续的内存空间，有两种方式，即单一连续分配方式和多个分区分配方式。其中，多个分区分配方式是一种可用于多道程序的较简单的存储管理方式，它又可以进一步细分为固定分区方式和可变(动态)分区方式。
4．3．1 一个分区的存储管理（单一连续分配存储管理方式）
单一连续分配方式只能用于单用户、单任务的操作系统。内存分为系统区和用户区。系统区仅提供给操作系统使用；用户区指除系统区以外的全部内存空间，提供给用户使用。仅当内存中没有其它作业时才有可能调度一个作业投入运行；被调度的作业所需主存的大小仅当不超过可用的主存容量时，才能将其装入主存并投入运行，否则该作业无法运行。
地址重定位时，只要将指令或数据的逻辑地址加上用户区基地址，就可以形成物理地址。
为了防止操作系统程序受到用户程序有意或无意的破坏，需要设置内存保护机构，如采用基址寄存器和界限寄存器机制。
优点：方法简单，易于实现。
缺点：仅适用于单道程序，不能使处理机和主存得到充分利用。
4.3.2 多个分区的存储管理之一：固定分区管理方式(分区大小、个数均固定)（P99）
一.原理
将内存空间划分为若干个固定大小的区域（所有分
区可以大小相等，也可以大小不等，但事先必须固定，
以后也不能改变），在每个分区中可以装入一道作业，
这样当内存中划分成几个分区时，便允许几道作业并
发运行；当有一个分区空闲时，便可从外存的后备队
列中，选择一个适当大小的作业装入该分区；当该作
业运行结束时，又可从后备队列中找出另一个作业调
入该分区。
为了便于内存分配，通常将这些分区根据它们的大小
进行排队，并为之建立一张分区分配（使用）表。每个
表项包括该分区的起始地址、大小及状态。当有一用户
程序要装入时，由内存分配程序检索该表，从中找出一
个能满足要求的、尚未分配的分区，将它分配给该程序，
然后修改分区使用表中的状态；若找不到大小
足够的分区，则拒绝为该程序分配内存。
优缺点：固定分区分配是最简单的多道程
序的存储管理方式。但由于每个分区的大小固
定，必然会造成存储空间的浪费；而且，程序
大小受分区空间大小的限制。
二.地址转换与存储保护
由于在每个分区中只可以装入一道作业，
且作业在执行过程中不会改变存放区域，因此
该作业的起始地址固定，可以采用静态重定
位。
设置上、下界限寄存器：下限地址<=绝对
地址<=上限地址
三.主存空间的利用
（1） 按分区大小从小到大排列分区；
（2） 根据经常出现的作业的大小和频率划分分区；
（3） 多队列的固定分区法。
4.3.3 多个分区的存储管理之二：可变分区管理(动态分区分配)（P100）
一．分区分配中的数据结构：
可变分区分配是根据作业的实际需要，动态地为之分配连续的内存空间。它是在作业装入和处理过程中建立的分区，并且要使分区的容量能正好适应作业的大小。为了实现分区分配，系统中必须设置相应的数据结构，如已分配区表和空闲分区表(或空闲分区链)，用来记录内存的使用情况，为内存分配提供依据。
二．分区分配算法：常见的分区分配算法，有首次适应算法（FF ）、循环首次适应算法（CFF ）、最佳适应算法（BF ）、最差适应算法（WF ）。
在首次适应算法中，空闲分区按地址递增的顺序形成空闲分区链，分配时从空闲分区链的第一个空闲分区开始向后扫描，直到找到第一个能满足需要的空闲分区。该算法倾向于优先利用内存中低地址部分空闲区，从而保留了高地址部分大的空闲区，分区合并较简单。缺点是低地址部分会留下许多难以利用的小空闲区，而每次查找又都从低地址部分开始，增加了开销。
循环首次适应算法中，空闲分区也按地址递增的顺序形成空闲分区链，分配时不是从空闲分区链的第一个空闲分区开始，而是从上一次找到的空闲分区的下一个空闲分区开始向后扫描，直到找到第一个能满足需要的空闲分区。该算法可以使得小的空闲区均匀地分布在可用存储空间中，当回收时，与大的空闲区合并的机会增加。但保留大的空闲区的可能性减小了。
在最佳适应算法中，空闲分区按大小递增的顺序形成空闲分区链，分配时从空闲分区链的第一个空闲分区开始向后扫描，直到找到第一个能满足需要的空闲分区，很显然该分区是满足需要而且是最接近需要的空闲区。该算法可以保留大的空闲区，但会留下许多小的空闲区．而且空闲区回收也更复杂一些。 在最差适应算法中，空闲分区按大小递减的顺序形成空闲分区链，分配时直接从从空闲分区链的第一个空闲分区中分配（不能满足需要则不分配）。很显然，如果第一个空闲分区不能满足需要，则再没有空闲分区能满足需要。该算法克服了最佳适应算法留下许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。
一般采用动态重定位方式装入作业，要有硬件的地址转换机构作支持。
动态分区解决了固定分区空间浪费严重的问题。但在
连续分配方式中．必须把一个程序装入到一个连续的内存
空间，这样就会形成许多“碎片”。可通过移动方法将碎片
拼接成一个可用的大块空间，但必须付出很大的系统开销
（损失了处理机时间），而且移动也是有条件的。另外，程
序大小受内存空间的限制。
五、多重分区分配：
给一个作业分配一个以上分区的方法，称为多重分区
分配。，采用该分配方案可使存储空间的利用率提高，能实现对子程序、数据段的共享。但作业的分段
越多，分区越小，结果使存储器分得过碎，没有较大的空白区，另外要求更多的硬件支持，管理也比较
复杂。
六、分区分配方案的评价：（p106）
4.4 分页存储管理方式
4.4.1基本思想
将一个进程的逻辑地址空间分成若干个大小相等的页（或称页面），内存空间分成与页相同大小的
物理块（或称页框）。在为进程分配内存时，以块为单位进行分配，每页分配一块。系统为每个进程建
立一张页面映射表（简称页表），记录相应页在内存中对应的物理块号。
4.4.2 地址变换
当过程访问某逻辑地址时，地址变换
机构自动地将逻辑地址分为页号和页内地
址两部分。再以页号为索引去检索页表，
得到该页的物理块号，把该物理块号与页
内地址拼接成物理地址，完成地址变换过
程，如图5．17所示。在进行地址变换的
同时，把页号与页表长度相比较，若大于
页表长度，则产生越界中断。
4.4.3 快表
由于页表是存放在内存中，这使CPU
每访问一个数据（或一条指令）时，都必
须两次访问内存。一次是访问页表，另一
次才是所需要的数据（或指令）。大大降低
了计算机的处理速度
为解决这一问题，在地址变换机构中，
必须增设一个联想存储器，又称快表，用以
存放当前使用的那些页表项。快表用硬件实
现，查快表可以不必占用一个访存周期。
引入快表后，地址变换过程是，在进行
地址变换时，首先检索快表。若找到，则直
接用快表中给出的物理块号与逻辑地址中
的页内地址形成物理地址。若未找到，则应
去内存中查找页表，此时应将该页的页表项
写入快表（快表满时，调出一个页表项，然
后写入），然后用页表中给出的物理块号与
逻辑地址中的页内地址形成物理地址。
可以看出，当快表命中时，只有一次访存；当快表不命中
时，仍然需要二次访存。所以，快表的命中率如何，对于等效
访存时间有很大的影响。
4．4．5页的共享和保护
在分页存储管理系统中，多个作业并发运行，共享同一内
存块里的程序或数据是可行的。为了实现共享，必须在各共享
者的页表中分别有指向共享内存块的表目。首先，必须保证被
共享的程序或数据占有整数块，以便与非共享部分分开。其次，
由于共享程序或数据被多个进程访问，所以每个进程对共享程
序或数据的访问都应该是有限制条件的。因此，从共享和保护
的实现上来看，须共享的程序段或数据段是一个逻辑单位，而
分段存储管理中被共享的程序或数据作为一个整体（一段），
实现共享和保护就要方便得多。
5.4.6多级页表
从上面的地址变换过程可以看出，页表必须占据连续的内存空间，如果页表长度超过一个页面，那页表的访问就出现了新的问题。解决的办法有两种，一是对页表所需的空间，采用离散分配方式，形成两级（甚至多级页表）；二是只将当前所需要的部分页表项调入内存，其余部分仍然驻留在磁盘上，需要时再将它们调入内存。
优缺点：分页存储管理显著提高了内存的利用率，只有最后一页可能是不满的，每个进程平均碎片长度为半个页面，因而基本上消除了碎片。但动态地址变换机构增加了计算机成本，页表要占用内存空间，需二次访存，仍然无法解决存储扩充问题。
4.5 分段式存储管理方式
引入分段存储管理主要是为了方便编程；便于共
享与保护；支持动态链接和动态增长。
4.5.1 基本思想
程序的地址空间被分成若干个段，每段采用连续
的地址空间。这样程序的逻辑地址就形成一个二维地
系统为每段分配一个连续区域（相当于一个分
区），各段可以存放在不同的分区中，即段与段之间
的地址是不连续的。系统为每个进程建立一张段表，
记录该段在内存中的起始地址和段长。段的分配和释
放过程，与动态分区管理完全相同。
4.5.2 主存空间的分配和回收
与可变分区管理方式相同。
4.5.3 地址变换与存储保护
当进程访问某逻辑地址时，地址变换机构以段号
为索引去检索段表（以段表寄存器的段表起始地址与
段号相加）、得到该段的起始地址和段长。
然后以段起始地址加上段内偏移就可以得
到该逻辑地址对应的物理地址，完成地址变
换过程，如图5．23所示。
在进行地址变换的过程中，要判断地址
越界。若段号大于段表长度（段表寄存器的
一部分）或段内偏移大手段长（从段表中读
出），都产生越界中断。同样的道理，分段
存储管理方式也存在二次访内问题，可以通
过增设快表来解决。
4.5.4 段的共享
分段系统的一个突出优点是便于实现
段的共享，而且段的保护也十分简单易行。
共享的代码段必须是可重入代码。
可重入代码又称为纯代码，是一种允许
多个进程同时访问的代码。
总之，分段式存储管理，方便了编程，便于实现
共享与保护，便于实现动态链接。从存储空间利用率来说，介于动态分区管理和分页管理之间。
4.5.5 分段与分页的区别
分段和分页都是离散分配方式，地址变换机构也比较类似，但从概念上说，两者是完全不同的。这可以从下述几个方面加以区别。
（1）页是信息的物理单位；段是信息的逻辑单位。
（2）页的大小固定而且由系统确定，硬件实现；段的长度不固定，决定于用户编写的程序。
（3）分页的程序地址空间是一维的；分段的程序地址空间是二维的。
4.6 段页式存储管理方式
分页和分段存储管理方式都各有其优缺点，分页系统能有效地提高内存利用率，而分段系统能很好地满足用户需要。段页式系统是分页和分段的结合，用户程序分成若干段，每个段划分成若干页，每段
为了实现地址变换，必须同时配置段表和页表。
当进程访问某逻辑地址（二维，包括段号和段内偏移）时，地址变换机构以段号为索引去检索段表（以段表寄存器的段表起始地址与段号相加），得到该段的页表起始地址和页表长度。然后，地址变换机构自动地将段内地址分为页号和页内地址两部分，再以页号为索引去检索页表（起站地址已从段表中获得），得到该页的物理块号，把该物理块号与页内地址拼接成物理地址，完成地址变换过程。
很显然，为了获得一条指令或数据，需要三次访问内存，因此决表是必不可少的。引入快表后，地址变换过程是，在进行地址变换时，首先检索快表。若找到，直接用快表中给出的物理块号与逻辑地址中的页内地址（由地址变换机构自动从段内偏移中划分出来的）形成物理地址。若未找到．则应去内存中先查找段表，再查找页表，得到物理块号。此时应将该页的页表项写入快表（快表满时，调出一个页表项，然后写入）．然后用页表中给出的物理块号与逻辑地址中的页内地址形成物理地址。所以，快表的命中率如何，对等效访存时间有很大的影响。
4.7 虚拟存储器
4.7.1 虚拟存储器的基本概念
1．程序局部性原理
程序局部性原理是指程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。
局部性又表现为时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行。如果某数据结构被访问，则不久以后该数据结构可能再次被访问。空间局部性是指一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。
2．虚拟存储器
基于程序局部性原理，一个作业在运行之前，没有必要全部装入内存，而仅将那些当前要运行的那部分页面或段先装入内存，就可以启动运行。这样就可以使一个较大的程序在较小的内存空间中运行，同时还可以装入更多的程序并发执行。通常把这样的存储器称为虚拟存储器。
所谓虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统。它具有请求调入功能和替换功能，能从逻辑上对内存容量进行扩充。
虚拟存储器最基本的特征是离散性，在此基础上又形成了多次性及对换性的特征。所表现出来的最重要的特征是虚拟性。
虚拟存储器的容量取决于主存与辅存的容量之和。一个虚拟存储器的最大容量是由计算机的地址结构确定的。实现虚拟存储器应有一定的硬件基础，即应有相当容量的辅存、一定容量的主存和地址变换机构。
虚拟存储器的实现都是建立在离散分配存储管理方式基础上的，目前常用的方式是请求分页存储管
理方式和请求分段存储管理方式。
覆盖技术（解决小内存运行大作业）:
覆盖技术是在程序运行过程中，把同一存储区在不同时刻分配给不同的程序段或数据段来共享的一种存储分配技术。
使用覆盖技术要求程序员必须小心地设计程序及其数据结构，使得要覆盖的段（块）具有相对独立性，不存在直接联系或相互交叉访问。该方法主要用于早期的操作系统。
对换技术（解决小内存实现分时系统）:
将作业不需要或暂时不需要的部分移到辅存，让出主存空间以调入需要的部分，交换到辅存的部分也可以再次被调入。实际上这是用辅存作缓冲，让用户程序在较小的存储空间中通过不断地换出作业而运行较大的作业。该方法仍用于现代的操作系统。
洋葱皮算法:减少对换的信息量。
4．7．2 页式虚拟存储管理(请求分页方式管理)
一．硬件支持
页表机制——页表中除了有页号、物理块号两项外，还需要状态位、访问字段、修改位、外存地址等信息。
缺页中断机构——每当所要访问的页面不在内存时，便要产生缺页中断，请求操作系统将所缺的页面调入内存。缺页中断与一般中断的区别，在于在指令的执行期间产生和处理缺页中断，而且一条指令执行期间，可能有多次缺页中断。
地址变换机构——在进行地址变换时，首先检索快表。若找到，则直接用快表中给出的物理块号与逻辑地址中的页内地址形成物理地址。若未找到，则应去内存中查找页表（慢表），将有两种可能。若
该页已调入内存，此时则应将该页的页表项写入快表（快表满时，调出一个页表项，然后写入），用页表中给出的物理块号与逻辑地址中的页内地址形成物理地址；若该页求调入内存，则产生缺负中断，请求操作系统从外存中调入。
缺页中断的处理过程是，保留CPU现场；从外存中找到缺的页面；若内存已满，则选择一页换出；从外存读入缺页，写入内存，修改页表。
二．页面替换算法
（1）最佳（Optimal）替换算法——选择永不使用或在未来最长时间内不再被访问的页面予以替
缺页中断率为：f=F/A=9/20=45%
（
缺页中断率为：f=F/A=15/20=75%
（
缺页中断率为：f=F/A=12/20=60%
三．缺页中断率
设作业执行中访问页面的总次数为A，其中有F次访问的页面尚未装入主存，故产生了F次缺页中断。现定义缺页中断率为：
f=F/A
影响缺页中断率的因素：
1．页面分配
（1）最小物理块数——能保证进程正常运行所需的最少物理块数。与计算机硬件结构有关，取决于指令的格式、功能和寻址方式。
（2）页面分配与替换策略——分配策略可以是固定分配和可变分配。替换策略可以是全局替换和部分替换。于是可以组合出三种策略：
固定分配局部替换:为每个进程分配一固定页数的内存空间，缺页时从中选出一页进行淘汰。
可变分配全局替换：先为每个进程分配一定页数的内存空间，缺页时由系统从管理的空闲物理块队列中取出一块分配给该进程。当空闲物理块队列中的物理块用完时，OS才从系统中任一进程中选出一页进行淘汰。
可变分配局部替换：先为每个进程分配一固定页数的内存空间，缺页时从中选出一页进行淘汰。但当某进程缺页频繁时系统再为该进程分配若干附加的空闲物理块，直到进程的缺页率减少到适当程度为止。
（4）分配算法
平均分配算法：
按比例分配算法：根据进程的大小按比例分配物理块。
考虑优先权的分配算法：
一般来说，分配给作业的实页数越多，缺页率会越低。但在使用FIFO 替换算法时，有时会出现分配的实页数增加，缺页次数反而增加的奇怪现象，这种现象称为Belay 现象。FIFO 替换算法产生Belady 现象的原因在于它根本没有考虑程序执行的动态特征。
（5）页面调入策略——页面调入可以采用预调页策略或请求调页策略。
2. 页面的大小
3．程序编制方法： int a[8][8] for (j=0;j<8;j++) for (k=0;k<8;k++) a[j][k]=0;
缺页中断次数=8-1=7
4．抖动与工作集
访问，需要将它调入，因无空闲内存又要替换另一页，而后者可能是即将被访问的页。于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重时导致系统瘫痪。这种现象称为抖动现象。
防止抖动现象可以有多种办法，例如，采取局部替换策略、引入工作集算法、挂起若干进程等。 所谓工作集是指在某段时间间隔里，进程实际要访问的页面的集合。引入虚拟存储器后，虽然程序只须有少量的内存就可以运行，但为了使程序有效运行，较少产生缺页，就必须使程序的工作集全部在内存中。
4.7.3 段式虚拟存储管理（请求分段存储管理方式）
一．段表机制
段表中除了有段号、段长、段的基址三项外，还需要存取方式、访问字段、修改位、存在位、增补位、外存起始地址等信息。
二．缺段中断机制
与缺页中断类似，每当所要访问的段不在内存时，便要产生缺段中断，请求操作系统将所缺的段调入内存。
在进行地址变换时，若发现被访问的段不在内存，必须先通过缺段中断将所缺的段调入内存，并修改段表。其余的过程与分段管理类似。
缺段中断的处理过程与缺页中断处理的过程类似，但比缺页中断更复杂。因为段长不固定，可能需要替换一个或多个段才能形成一个合适的空闲分区。
4．8 UNIX操作系统存储管理
在早期的UNIX操作系统中，为了提高内存的利用率，提供了内存和外存之间的进程交换机制。在UNIX 操作系统V中，除保留了交换机制外，还支持请求分页存储管理方式，内存空间的分配和回收都以页为单位进行。页面大小 512 B～4 KB。为实现请求分页存储管理，系统配置了4种数据结构，即页表、磁盘块描述表、页框数据表和交换使用表，并专门设置了一个换页进程。
4．9例题精选
例4．1某虚拟存储器的用户空间共有32个页面，每页 1KB，主存 16KB。试问：（1）逻辑地址的有效位是多少？
（2）物理地址需要多少位？
（3）假定某时刻系统为用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，试将虚地址0A5C和093C变换为物理地址。
解（1）程序空间的大小为 32 KB，因此逻辑地址的有效位数是 15位。
（2）存储空间的大小是 16 KB，因此物理地址至少需要 14位。
（3）当页面为1KB时，虚地址 0A5C表示页号为 00010，页内地址是 1001011100。
该页在内存的第4块，即块号为0100，因此0A5C的物理地址是01001001011100，即125CH。用同样的方法可以求得，093C的物理地址是113CH。
讨论分页存储管理的地址变换非常简单，只要记住一点，由页号查页表得物理块号，然后与页内地址拼接成物理地址。
例4．2某段式存储管理中采用如表4．1所示的段表。
（1）给定段号和段内地址，说明段式管理中的地址变换过程。
（2）计算［0，430］，［1．10］，［2，500〕，［3，400］，［4，20］，［5，100］的内存地址，其中方括号内的第一元素是段号，第二元素是段内地址。
（3）说明存取主存中的一条指令或数据至少要访问几次主存。
解（1）为了实现从逻辑地址到物理地址的变换，在系统中需要设置段表寄存器，存放段表起站地址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号S与段表长度TL进行比较。若S＞TL，则表示段号太大，是访问越界（段号越界），产生越界中断。若未越界，则根据段表的起始地址和段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始位置和段长SL，再检查段内地址d是否超过该段的段长SL。若超过，即d＞SL，则同样发出越界中断信号（段内地址越界）；若未越界，则将该段的起始地址与段内地址d相加，即得要访问的内存物理地址。
（2）［0，430］的物理地址是219＋430=649。
［1，10］的物理地址是3330＋10=3340。
因 500＞100，所以［2，500］越界（段内地址越界）。
［3，400］的物理地址是1237＋400=1637。
［4，20］的物理地址是1952＋20=1972。
因 5＞4，所以［5，100］越界（段号越界）。
（3）存取主存中的一条指令或数据至少要访问2次主存。一次是访问段表，另一次是访问需要的指令或数据。
讨论在分段存储管理的地址变换过程中，要点是由段号查段表得段起始地址，然后与段内地址相加得物理地址。但要注意，段地址是二维地址，段号和段内地址都有可能越界。
例4．3分页和分段有何区别？为什么说分段系统较之分页系统更易于实现信息共享和保护？如何实现？
解分页和分段都采用离散分配方式，但两者有显著的差别。
（1）页是信息的物理单位，分页是系统的需要，是为了提高内存的利用率；段是信息的逻辑单位，目的在于更好地满足用户的需要。
（2）页的大小固定，且由系统确定，一个系统只能有一种大小的页面；段的长度不固定，决定于用户的程序。
（3）分页的作业地址空间是一维的，单一的线性地址空间；分段的作业地址空间是二线的，一个地址包括段号和段内地址。
在分页和分段存储管理系统中，多个作业并发运行，共享同一内存块里的程序或数据是可行的。为了实现共享，必须在各共享者的段表或页表中分别有指向共享内存块的表目。对分段式系统，被共享的程序或数据可作为单独的一段。在物理上它是一段，在不同的进程中，可以对应不同的逻辑段，相对来说比较易于实现。对分页管理，则要困难得多。首先，必须保证被共享的程序或数据占有整数块，以便与非共享部分分开。其次，由于共享程序或数据被多个进程访问，所以每个进程对共享程序或数据的访
问都应该是有限制条件的。因此，从共享和保护的实现上来看，须共享的程序段或数据段是一个逻辑单
位，而分段存储管理中被共享的程序或数据作为一个整体（一段），实现共享和保护就要方便得多。
分段系统的共事是通过两个（或多个）进程的段表之相应表目都指向同一个物理段，并设置共享计数来实现的。每段设置访问方式，就可以实现段的保护。
讨论分页与分段的逻辑地址一个是一维，一个是二维，一定要加以区别。从共享与保护来讲．分页管理也可以实现，但非常复杂，一般系统不易实现。
例4．4在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5。
计算访问过程中所发生的缺页次数和缺页率；比较所得结果。
缺页次数=10次，缺页率=（10／12）*100％=83％。
通过以上缺页次数和缺页率的分析计算，可以看出，对于LRU算法，增加物理块数，可以减少缺页次数，降低缺页率。而对FIFO算法，增加物理块数，不一定能减少缺页次数。
讨论计算缺页次数和缺页率时，要注意初始时刻所有物理块为空。调入页面时，不需要页面替换，但是需要引起缺页中断。
例4．5什么是虚拟存储器？在分页存储管理系统中如何实现虚拟存储？
解所谓虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统。它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充。
请求分页存储管理系统是在分页管理的基础上实现的。页表中除了有页号、物理块号两项外，还需要状态位、访问字段、修改位、外存地址等信息。由于是部分调入内存，每当所要访问的页面不在内存时，便要产生缺页中断，请求操作系统将所缺页调入内存。缺页中断的处理过程是保留CPU现场；从外存中找到所缺的页面；若内存已满，则选择一页换出，从外存读入所缺的页面，写入内存，修改页表。
在进行地址变换时，若发现被访问的页不在内存，必须先通过缺页中断将所缺的页面调入内存，并修改页表。其余的过程与分页管理类似。全过程如图4．3所示。
讨论请求分页存储管理系统实现的重点，在于对地址变换过程和缺页中断处理过程的
理解。
例4．6类似于请求分页存储管理中的请求式调页那样，在请求分段存储管理中也可以采用请求式调段策略。试提出一个合理的段替换算法，并说明在段替换过程中会出现哪些在负面替换过程中不出现的问题。
解可以使用FIFO替换算法。它在内存中查找第一个满足要求的段。为避免内部存储碎片，可把该段的末被占用的部分并入空闲空间表中。若找不到满足要求的段，则可以选择两个或多个连续的段来满足要求。
在段替换过程中，必须要考虑到段的大小变化，但在页面替换中页面的大小是固定的。
讨论关于请求分段存储管理的段替换算法，考虑到段大小的不固定，可能需要替换若干个连续的段才能满足要求，所以替换算法应力求简单，FIFO算法成为首选。
4．3习题
4．1填空题：
（1）存储管理方案中，可采用覆盖技术。
（A）单一连续区存储管理（B）可变分区存储管理
（C）段式存储管理（D）段页式存储管理
（2）对如图4．4所示的内存分配情况（其中，阴影部分表示已占用块，空白部分表示空闲块），若要申请一块 40 KB的内存，对于最佳适应分配策略给出分配区域的首地址是。
（A） 110 KB （B） 190KB （C） 330 KB （D） 410 KB
（3）在图4.4所示中，若要申请一块40KB的内存，使首地址最大的分配策略是。
（A）首次适应分配策略（B）最佳适应分配策略
（C）最坏适应分配策略（D）单一连续区分配策略
（4）下列算法中会产生 Belady异常现象的是。
（A）先进先出（FIFO）页面替换算法
（B）最近最久未使用（LRU）替换算法
（C）最不经常使用（LFU）页面替换算法
（D）最佳（Optimal）页面替换算法
4．2为什么要引入动态重定位？如何实现？
4．3在动态分区管理中，有哪些分区分配算法？各有何优
缺点?
4．4在采用首次适应算法的分区管理中，回收内存时可能出现哪几种情况？应怎样处理这些情况？
4．5什么叫覆盖？使用覆盖技术有什么要求？
4．6在系统中引入交换技术后带来哪些好处？为实现交换，系统应具备哪些方面的功能？
4．7对于一个利用快表且页表存于内存的分页系统，假定CPU一次访存时间为1.5us。访问快表的时间可以忽略不计。试问：
（1）如果85％的地址映射可以直接通过快表完成（即快表命中率为85％）那么进程完成一次内存读写的平均有效访问时间是多少？
（2）若快表的命中率只有50％，那么进程完成一次内存读写的平均有效访问时间又是多少？
（3）快表命中率对平均有效访问时间有何影响？
4．8什么叫动态装入？动态装入的优点是什么？
4．9为什么引入虚拟存储概念？虚拟存储器的容量由什么决定？受什么影响？
4.10请指出下面哪些程序设计技术和数据结构适合于请求分页存储管理环境，哪些不适合请求式分页存储管理环境。
（1）栈（2）杂凑符号表（3）顺序查找（4）折半查找（5）纯代码（6）向量操作。
4．11假定有一个请求分页存储管理系统，测得各相关成分的利用率为：CPU利用率为 20％；磁盘交换区为 96.7％；其他 I／0设备为 50％。
试问下面哪些措施将（可能）改进CPU的利用率？
（1）增加一个更快速的CPU。（2）增大磁盘交换区的容量。
（3）增加多道程序的度数。（4）减少多道程序的度数。
（5）增加其他更快速的I／0设备。
4．12设有二维数组
int A［1..100］［1..100］；
其中数组元素A［1，1］存放在页面大小为200的分页存储管理系统中的地址200处，数组按行存储。使用该数组的一个较小的程序存放在第0页中（地址0～199），这样将只会从第0页取指令。
假定现有三个页面，第一个页面存放程序，其余两个页面用于存放数据,初始为空。试问：若使用LRU替换算法，下面的数组初始化循环将会产生多少次缺页中断？若每页的页面大小为100, 数组初始化循环将会产生多少次缺页中断？并说明页面大小对缺页中断次数的影响.
（1）for(j=1;j<=100;j++)for(k=1;k<=100;k++)A[j][k]=0;
（2）for(j=1;j<=100;j++)for(k=1;k<=100;k++)A[k][j]=0;
4．13考虑下面的页访问串：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 假定有1，2，3，4，5，6，7个页块。试问：若应用下面的页面替换算法，各会出现多少次缺页中断？注意，所给定的页块初始均为空，因此，首次访问一页时就会发生缺页中断。
（1）LRU替换算法。（2）FIFO替换算法。（3）Optima替换算法。
4．14什么是局部性原理？什么是抖动？有什么办法可以减少系统的抖动现象？
4．15什么叫工作集？工作集模型的优点是什么？
认真是成功的秘诀，粗心是失败的伴侣。
——童第周——
操作系统内存管理
操作系统内存管理 1. 内存管理方法 内存管理主要包括虚地址、地址变换、内存分配和回收、内存扩充、内存共享和保护等功能。 2. 连续分配存储管理方式 连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。 2.1 单一连续存储管理 在这种管理方式中，内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。CP／M和 DOS 2．0以下就是采用此种方式。这种方式的最大优点就是易于管理。但也存在着一些问题和不足之处，例如对要求内
存空间少的程序，造成内存浪费；程序全部装入，使得很少使用的程序部分也占用—定数量的内存。 2.2 分区式存储管理 为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行内存分区的共享。 分区式存储管理引人了两个新的问题：内碎片和外碎片。 内碎片是占用分区内未被利用的空间，外碎片是占用分区之间难以利用的空闲分区(通常是小空闲分区)。 为实现分区式存储管理，操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。
分区式存储管理常采用的一项技术就是内存紧缩(compaction)。 2.2.1 固定分区(nxedpartitioning)。 固定式分区的特点是把内存划分为若干个固定大小的连续分区。分区大小可以相等：这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 优点：易于实现，开销小。 缺点主要有两个：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。 2.2.2动态分区(dynamic partitioning)。 动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是：没有内碎
实验三存储管理实验 Pleasure Group Office【T985AB-B866SYT-B182C-BS682T-STT18】
实验三存储管理实验 一. 目的要求： 1、通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。 2、通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。二．实验内容： 1、设计一个固定式分区分配的存储管理方案，并模拟实现分区的分配和回收过程。 可以假定每个作业都是批处理作业，并且不允许动态申请内存。为实现分区的分配和回收，可以设定一个分区说明表，按照表中的有关信息进行分配，并根据分区的分配和回收情况修改该表。 算法描述： 本算法将内存的用户区分成大小相等的四个的分区，设一张分区说明表用来记录分区，其中分区的表项有分区的大小、起始地址和分区的状态，当系统为某个作业分配主存空间时，根据所需要的内存容量，在分区表中找到一个足够大的空闲分区分配给它，然后将此作业装入内存。如果找不到足够大的空闲分区，则这个作业暂时无法分配内存空间，系统将调度另一个作业。当一个作业运行结束时，系统将回收改作业所占据的分区并将该分区改为空闲。 算法原程序 #include "" #include "" #include <>
#include <> #define PCB_NUM 5 行程序."); printf("\n\t\t\t0.退出程序."); scanf("%d",&m); switch(m) { case1: break; case0: system("cls"); menu(); break; default: system("cls"); break; } } void paixu(struct MemInf* ComMem,int n) { int i,j,t; for(j=0; j
第四章存储管理 1. C存储管理支持多道程序设计，算法简单，但存储碎片多。 A. 段式 B. 页式 C. 固定分区 D. 段页式 2.虚拟存储技术是 B 。 A. 补充内存物理空间的技术 B. 补充相对地址空间的技术 C. 扩充外存空间的技术 D. 扩充输入输出缓冲区的技术 3.虚拟内存的容量只受 D 的限制。 A. 物理内存的大小 B. 磁盘空间的大小 C. 数据存放的实际地址 D. 计算机地址位数 4.动态页式管理中的 C 是：当内存中没有空闲页时，如何将已占据的页释放。 A. 调入策略 B. 地址变换 C. 替换策略 D. 调度算法 5.多重分区管理要求对每一个作业都分配 B 的内存单元。 A. 地址连续 B. 若干地址不连续 C. 若干连续的帧 D. 若干不连续的帧 6.段页式管理每取一数据，要访问 C 次内存。 A. 1 B. 2 C. 3 D. 4 7.分段管理提供 B 维的地址结构。 A. 1 B. 2 C. 3 D. 4 8.系统抖动是指 B。 A. 使用计算机时，屏幕闪烁的现象 B. 刚被调出内存的页又立刻被调入所形成的频繁调入调出的现象 C. 系统盘不干净，操作系统不稳定的现象 D. 由于内存分配不当，造成内存不够的现象 9.在 A中，不可能产生系统抖动现象。 A. 静态分区管理 B. 请求分页式管理 C. 段式存储管理 D. 段页式存储管理 10.在分段管理中 A 。 A. 以段为单元分配，每段是一个连续存储区 B. 段与段之间必定不连续 C. 段与段之间必定连续 D. 每段是等长的 11.请求分页式管理常用的替换策略之一有 A 。 A. LRU B. BF C. SCBF D. FPF 12.可由CPU调用执行的程序所对应的地址空间为 D 。 A. 名称空间 B. 虚拟地址空间 C. 相对地址空间 D. 物理地址空间 13. C 存储管理方式提供二维地址结构。 A. 固定分区 B. 分页
学生学号 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称 计算机操作系统 开 课 学 院 计算机科学与技术学院 指导老师姓名 学 生 姓 名 学生专业班级 2016 — 2017 学年第一学期
实验三 内存管理 一、设计目的、功能与要求 1、实验目的 掌握内存管理的相关内容，对内存的分配和回收有深入的理解。 2、实现功能 模拟实现内存管理机制 3、具体要求 任选一种计算机高级语言编程实现 选择一种内存管理方案：动态分区式、请求页式、段式、段页式等 能够输入给定的内存大小，进程的个数，每个进程所需内存空间的大小等 能够选择分配、回收操作 内购显示进程在内存的储存地址、大小等 显示每次完成内存分配或回收后内存空间的使用情况 二、问题描述 所谓分区，是把内存分为一些大小相等或不等的分区，除操作系统占用一个分区外，其余分区用来存放进程的程序和数据。本次实验中才用动态分区法，也就是在作业的处理过程中划分内存的区域，根据需要确定大小。 动态分区的分配算法：首先从可用表/自由链中找到一个足以容纳该作业的可用空白区，如果这个空白区比需求大，则将它分为两个部分，一部分成为已分配区，剩下部分仍为空白区。最后修改可用表或自由链，并回送一个所分配区的序号或该分区的起始地址。 最先适应法：按分区的起始地址的递增次序，从头查找，找到符合要求的第一个分区。
最佳适应法：按照分区大小的递增次序，查找，找到符合要求的第一个分区。 最坏适应法：按分区大小的递减次序，从头查找，找到符合要求的第一个分区。 三、数据结构及功能设计 1、数据结构 定义空闲分区结构体，用来保存内存中空闲分区的情况。其中size属性表示空闲分区的大小，start_addr表示空闲分区首地址，next指针指向下一个空闲分区。 //空闲分区 typedef struct Free_Block { int size; int start_addr; struct Free_Block *next; } Free_Block; Free_Block *free_block; 定义已分配的内存空间的结构体，用来保存已经被进程占用了内存空间的情况。其中pid作为该被分配分区的编号，用于在释放该内存空间时便于查找。size表示分区的大小，start_addr表示分区的起始地址，process_name存放进程名称，next指针指向下一个分区。 //已分配分区的结构体 typedef struct Allocate_Block { int pid; int size; int start_addr; char process_name[PROCESS_NAME_LEN]; struct Allocate_Block *next; } Allocate_Block; 2、模块说明 2.1 初始化模块 对内存空间进行初始化，初始情况内存空间为空，但是要设置内存的最大容量，该内存空间的首地址，以便之后新建进程的过程中使用。当空闲分区初始化
实验三、存储管理 一、实验目的： ? 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。 在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验理解在分页式存储管理中怎样实现虚拟存储器。 在本实验中，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。 二、实验题目： 设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 对分区的管理法可以是下面三种算法之一：（任选一种算法实现） 首次适应算法 循环首次适应算法 最佳适应算法 三．实验源程序文件名:cunchuguanli.c
执行文件名:cunchuguanli.exe 四、实验分析： 1)本实验采用可变分区管理，使用首次适应算法实现主存的分配和回收 1、可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并 且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表 ? 空闲区说明表格式如下：? 第一栏 第二栏 其中，起址——指出一个空闲区的主存起始地址，长度指出空闲区的大小。 长度——指出从起始地址开始的一个连续空闲的长度。 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业完成后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。 2、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。 有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分
存储器管理 单项选择题 存储管理的目的是（）。 A.方便用户 B.提高内存利用率 C.方便用户和提高内存利用率 D.增加内存实际容量 外存（如磁盘）上存放的程序和数据（）。 A．可由CPU直接访问 B．必须在CPU访问之前移入内存 C．是必须由文件系统管理的 D．必须由进程调度程序管理 当程序经过编译或者汇编以后，形成了一种由机器指令组成的集合，被称为（）。 A.源程序 B.目标程序 C.可执行程序 D.非执行程序 4、可由CPU调用执行的程序所对应的地址空间为（ D ）。 A.符号名空间 B.虚拟地址空间 C.相对地址空间 D.物理地址空间 5、经过（），目标程序可以不经过任何改动而装入物理内存单元。 A.静态重定位 B.动态重定位 C.编译或汇编 D.存储扩充 6、若处理器有32位地址，则它的虚拟地址空间为（）字节。 A.2GB B.4GB C.100KB D.640KB 7、分区管理要求对每一个作业都分配（）的内存单元。 A.地址连续 B.若干地址不连续 C.若干连续的帧 D.若干不连续的帧 8、（）是指将作业不需要或暂时不需要的部分移到外存，让出内存空间以调入其他所需数据。 A.覆盖技术 B.对换技术 C.虚拟技术 D.物理扩充 9、虚拟存储技术是（）。 A.补充内存物理空间的技术 B.补充相对地址空间的技术 C.扩充外存空间的技术 D.扩充输入输出缓冲区的技术 10、虚拟存储技术与（）不能配合使用。 A.分区管理 B.动态分页管理 C.段式管理 D.段页式管理 11、以下存储管理技术中，支持虚拟存储器的技术是（）。 A．动态分区法 B．可重定位分区法 C．请求分页技术 D．对换技术 12、在请求页式存储管理中，若所需页面不在内存中，则会引起（）。 A.输入输出中断 B. 时钟中断 C.越界中断 D. 缺页中断 13、在分段管理中，（）。 以段为单位分配，每段是一个连续存储区 段与段之间必定不连续 段与段之间必定连续 每段是等长的 14、（）存储管理方式提供一维地址结构。 A.固定分区 B.分段 C.分页 D.分段和段页式 15、分段管理提供（）维的地址结构。 A.1 B.2 C.3 D.4 16、段页式存储管理汲取了页式管理和段式管理的长处，其实现原理结合了页式和段式管理的基本思想，即（）。 用分段方法来分配和管理物理存储空间，用分页方法来管理用户地址空间。 用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间。 用分段方法来分配和管理主存空间，用分页方法来管理辅存空间。
操作系统存管理 1. 存管理方法 存管理主要包括虚地址、地址变换、存分配和回收、存扩充、存共享和保护等功能。 2. 连续分配存储管理方式 连续分配是指为一个用户程序分配连续的存空间。连续分配有单一连续存储管理和分区式储管理两种方式。 2.1 单一连续存储管理 在这种管理方式中，存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。CP／M和DOS 2．0以下就是采用此种方式。这种方式的最大优点就是易于管理。但也存在着一些问题和不足之处，例如对要求存空间少的程序，造成存浪费；程序全部装入，使得很少使用的程序部分也占用—定数量的存。
2.2 分区式存储管理 为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行存分区的共享。 分区式存储管理引人了两个新的问题：碎片和外碎片。 碎片是占用分区未被利用的空间，外碎片是占用分区之间难以利用的空闲分区(通常是小空闲分区)。 为实现分区式存储管理，操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。 分区式存储管理常采用的一项技术就是存紧缩(compaction)。
2.2.1 固定分区(nxedpartitioning)。 固定式分区的特点是把存划分为若干个固定大小的连续分区。分区大小可以相等：这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 优点：易于实现，开销小。 缺点主要有两个：碎片造成浪费；分区总数固定，限制了并发执行的程序数目。 2.2.2动态分区(dynamic partitioning)。 动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程过系统调用进行分配或改变分区大小。与固定分区相比较其优点是：没有碎片。但它却引入了另一种碎片——外碎片。动态分区的分区分配就是寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要
OS实验指导四——虚拟存储器管理
————————————————————————————————作者：————————————————————————————————日期： 2
《操作系统》实验指导四 开课实验室：A207、A209 2015/11/23 、2015/11/24 实验类型设计 实验项目（四）虚拟存储器管理实验 实验学时 4 一、实验目的 设计一个请求页式存储管理方案，并编写模拟程序实现。 二、设备与环境 1. 硬件设备：PC机一台 2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发 环境，如C \C++\Java 等编程语言环境。 三、实验要求 1) 上机前认真复习页面置换算法，熟悉FIFO算法和LRU页面分配和置换算法的过程； 2) 上机时独立编程、调试程序； 3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行 结果截图）。 四、实验内容 1、问题描述： 设计程序模拟FIFO和LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，并计算每种算法缺页次数和缺页率。 2、程序具体要求如下： 编写程序用来模拟虚拟页式存储管理中的页面置换 要求： 1)快表页面固定为4块 2)从键盘输入N个页面号 3)输出每次物理块中的页面号和缺页次数，缺页率 4)实现算法选择
3、程序流程图 3、源程序参考： （1）FIFO 算法部分 #include "stdio.h" #define n 12 #define m 4 void main() { int ym[n],i,j,q,mem[m]={0},table[m][n]; char flag,f[n]; printf("请输入页面访问序列\n "); for(i =0;i 一、选择 1．分页存储管理的存储保护是通过( )完成的. A.页表（页表寄存器） B.快表 C.存储键 D.索引动态重定 2．把作业地址空间中使用的逻辑地址变成存中物理地址称为（）。 A、加载 B、重定位 C、物理化 D、逻辑化3．在可变分区存储管理中的紧凑技术可以---------------。 A.集中空闲区 B.增加主存容量 C.缩短访问时间 D.加速地址转换 4．在存储管理中，采用覆盖与交换技术的目的是( )。 A.减少程序占用的主存空间 B.物理上扩充主存容量 C.提高CPU效率 D.代码在主存中共享 5．存储管理方法中，( )中用户可采用覆盖技术。 A．单一连续区 B. 可变分区存储管理 C．段式存储管理 D. 段页式存储管理 6．把逻辑地址转换成物理地址称为（）。 A.地址分配 B.地址映射 C.地址保护 D.地址越界 7．在存分配的“最佳适应法”中，空闲块是按（）。 A.始地址从小到大排序 B.始地址从大到小排序 C.块的大小从小到大排序 D.块的大小从大到小排序 8．下面最有可能使得高地址空间成为大的空闲区的分配算法是（）。A.首次适应法 B.最佳适应法 C.最坏适应法 D.循环首次适应法 9．那么虚拟存储器最大实际容量可能是( ) 。 A.1024K B.1024M C.10G D.10G+1M 10．用空白链记录存空白块的主要缺点是（）。 A.链指针占用了大量的空间 B.分配空间时可能需要一定的拉链时间 C.不好实现“首次适应法” D.不好实现“最佳适应法” 11．一般而言计算机中（）容量(个数)最多. A.ROM B.RAM C.CPU D.虚拟存储器 12．分区管理和分页管理的主要区别是（）。 A.分区管理中的块比分页管理中的页要小 B.分页管理有地址映射而分区管理没有 C.分页管理有存储保护而分区管理没有 D.分区管理要求一道程序存放在连续的空间而分页管理没有这种要求。13．静态重定位的时机是（）。 A.程序编译时 B.程序时 C.程序装入时 D.程序运行时 14．通常所说的“存储保护”的基本含义是（） A.防止存储器硬件受损 B.防止程序在存丢失 C.防止程序间相互越界访问 D.防止程序被人偷看 15．能够装入存任何位置的代码程序必须是( )。 A.可重入的 B.可重定位 系统运行环境配置及安装说明 一、系统运行环境配置 本系统为网络版，在服务器上安装后，局域网内所有计算机都可以连接使用。安装后系统的数据库和应用程序分别存放在Microsoft SQL Server中和用户指定的磁盘上。 1.硬件环境 1.1网络环境 本系统需要运行在单位局域网上，要求服务器、客户端（档案室）计算机连接在此网络上。建议配置100M网络速度。 1.2满足系统运行的客户机、服务器的基本配置 CPU: PⅣ1.6G以上 内存：256M以上，建议512M 硬盘：40G以上 VGA：分辨率800*600或者更高 网卡：100M以上 其他：光驱、3.5英寸软驱、鼠标 2.软件环境 2.1服务器操作系统配置： Windows 2000 Server 或Windows 2000 Advanced Server 。 2.2服务器数据库配置： Microsoft SQL Server 7.0 或 Microsoft SQL Server 2000 。 第一次在服务器上安装Microsoft SQL Server，在安装过程中会出现提示输入“连接客户端数”的窗口，请增加100个客户端。 服务器上已经安装了Microsoft SQL Server，请运行“开始”-->“程序”-->“管理工具”-->“授权”检查Microsoft SQL Server的许可连接数，如果其连接数为0或不足100，请设置为100个客户端连接。 2.3客户端浏览器配置：IE5.0以上。 二、系统安装说明 请插入“中国科学院院属单位综合档案管理系统”光盘，双击SETUP[2.50].EXE。按照系统提示的步骤安装到PC机或服务器上。用户只能将本系统安装在计算机的根目录下，如：C:\ 。 安装完成后请重新启动服务器。 三、数据库软件安装说明 本系统需要安装SQL SERVER 7.0或者SQL SERVER 2000数据库软件，安装具体步骤如下。 1.SQL SERVER 7.0的安装 把SQL SERVER 7.0数据库安装光盘放到光驱中，双击光盘盘符，进入光盘内容。打开光盘后，如图3.1-1。 图3.1-1 双击“AUTORUN.EXE”图标即可进入数据库的安装画面，如图3.1-2： 内存管理模拟 实验目标： 本实验的目的是从不同侧面了解Windows 2000／XP 对用户进程的虚拟内存空间的管理、分配方法。同时需要了解跟踪程序的编写方法(与被跟踪程序保持同步，使用Windows提供的信号量)。对Windows分配虚拟内存、改变内存状态，以及对物理内存(physical memory)和页面文件(pagefile)状态查询的API 函数的功能、参数限制、使用规则要进一步了解。 默认情况下，32 位Windows 2000／XP 上每个用户进程可以占有2GB 的私有地址空间，操作系统占有剩下的2GB。Windows 2000／XP 在X86 体系结构上利用二级页表结构来实现虚拟地址向物理地址的变换。一个32 位虚拟地址被解释为三个独立的分量——页目录索引、页表索引和字节索引——它们用于找出描述页面映射结构的索引。页面大小及页表项的宽度决定了页目录和页表索引的宽度。 实验要求： 使用Windows 2000／XP 的API 函数，编写一个包含两个线程的进程，一个线程用于模拟内存分配活动，一个线程用于跟踪第一个线程的内存行为，而且要求两个线程之间通过信号量实现同步。模拟内存活动的线程可以从一个文件中读出要进行的内存操作，每个内存操作包括如下内容： 时间：操作等待时间。 块数：分配内存的粒度。 操作：包括保留(reserve)一个区域、提交(commit)一个区域、释放(release)一个区域、回收(decommit)一个区域和加锁(lock)与解锁(unlock)一个区域，可以将这些操作编号存放于文件。保留是指保留进程的虚拟地址空间，而不分配物理 存储空间。提交在内存中分配物理存储空间。回收是指释放物理内存空间，但在虚拟地址空间仍然保留，它与提交相对应，即可以回收已经提交的内存块。释放是指将物理存储和虚拟地址空间全部释放，它与保留(reserve)相对应，即可以释放已经保留的内存块。 大小：块的大小。 访问权限：共五种，分别为PAGE_READONLY,PAGE_READWRITE ，PAGE_EXECUTE，PAGE_EXECUTE_READ 和PAGE EXETUTE_READWRITE。可以将这些权限编号存放于文件中跟踪线程将页面大小、已使用的地址范围、物理内存总量，以及虚拟内存总量等信息显示出来。 一页式管理 1 页式管理的基本原理将各进程的虚拟空间划分成若干个长度相等的页(page)，页式管理把内存空间按页的大小划分成片或者页面（page frame），然后把页式虚拟地址与内存地址建立一一对应页表，并用相应的硬件地址变换机构，来解决离散地址变换问题。页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理。 它分为 1 静态页式管理。静态分页管理的第一步是为要求内存的作业或进程分配足够的页面。系统通过存储页面表、请求表以及页表来完成内存的分配工作。静态页式管理解决了分区管理时的碎片问题。但是，由于静态页式管理要求进程或作业在执行前全部装入内存，如果可用页面数小于用户要求时，该作业或进程只好等待。而且作业和进程的大小仍受内存可用页面数的限制。 2 动态页式管理。动态页式管理是在静态页式管理的基础上发展起来的。它分为请求页式管理和预调入页式管理。 优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。便于改变程序占用空间的大小（主要指随着程序运行而动态生成的数据增多，要求地址空间相应增长，通常由系统调用完成而不是操作系统自动完成）。 缺点：程序全部装入内存。 要求有相应的硬件支持。例如地址变换机构，缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了机器成本。增加了系统开销，例如缺页中断处理机，请求调页的算法如选择不当，有可能产生抖动现象。虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用果页面较大，则这一部分的损失仍然较大。 二段式管理的基本思想 把程序按内容或过程（函数）关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应一个二维线形虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址影射机构把段式虚拟地址转换为实际内存物理地址。 程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。其优点是：可以分别编写和编译。可以针对不同类型的段采取不同的保护。可以按段为单位来进行共享，包括通过动态链接进行代码共享。 三段页式管理的实现原理 1 虚地址的构成 一个进程中所包含的具有独立逻辑功能的程序或数据仍被划分为段，并有各自的段号s。这反映相继承了段式管理的特征。其次，对于段s中的程序或数据，则按照一定的大小将其划分为不同的页。和页式系统一样，最后不足一页的部分仍占一页。这反映了段页式管理中的页式特征。从而，段页式管理时的进程的虚拟地址空间中的虚拟地址由三部分组成：即段号s，页号P和页内相对地址d。虚拟空间的最小单位是页而不是段，从而内存可用区也就被划分成为着干个大小相等的页面，且每段所拥有的程序和数据在内存中可以分开存放。分段的大小也不再受内存可用区的限制。 2 段表和页表 实验三存储管理 实验目的 1) 加深对存储管理的理解； 2) 掌握几种页面置换算法； 3) 通过实验比较各种置换算法的优劣。 实验要求 1) 编写程序完成实验内容； 2) 对测试数据进行分析； 3) 撰写实验报告。 实验内容 1) 定义为进程分配的物理块数； 2）定义进程运行所需访问的页面号； 3）定义页的结构； 4）模拟两种页面置换算法； 5）计算页面置换算法的命中率； 6）比较两种算法的优劣。 实验原理 1.虚拟存储 基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果它所要访问的页(段)已调入内存，便可继续执行下去；但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页(段)，则还须再利用页(段) 的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。 2.页面置换算法 1）最佳(Optimal)置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。 2）最近最久未使用(LRU)置换算法 FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。 a）寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=R n-1R n-2R n-3… R2R1R0当进程访问某物理块时，要将相应寄存器的R n-1位置成1。此时，定时信号将每隔一定时间(例如100 ms)将寄存器右移一位。如果我们把n位寄存器的数看做是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。 b）栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。 内存分段和请求式分页 在深入i386架构的技术细节之前，让我们先返回1978年，那一年Intel 发布了PC处理器之母：8086。我想将讨论限制到这个有重大意义的里程碑上。如果你打算知道更多，阅读Robert L.的80486程序员参考（Hummel 1992）将是一个很棒的开始。现在看来这有些过时了，因为它没有涵盖Pentium处理器家族的新特性；不过，该参考手册中仍保留了大量i386架构的基本信息。尽管8086能够访问1MB RAM的地址空间，但应用程序还是无法“看到”整个的物理地址空间，这是因为CPU寄存器的地址仅有16位。这就意味着应用程序可访问的连续线性地址空间仅有64KB，但是通过16位段寄存器的帮助，这个64KB大小的内存窗口就可以在整个物理空间中上下移动，64KB逻辑空间中的线性地址作为偏移量和基地址（由16位的段寄存器给处）相加，从而构成有效的20位地址。这种古老的内存模型仍然被最新的Pentium CPU支持，它被称为：实地址模式，通常叫做：实模式。 80286 CPU引入了另一种模式，称为：受保护的虚拟地址模式，或者简单的称之为：保护模式。该模式提供的内存模型中使用的物理地址不再是简单的将线性地址和段基址相加。为了保持与8086和80186的向后兼容，80286仍然使用段寄存器，但是在切换到保护模式后，它们将不再包含物理段的地址。替代的是，它们提供了一个选择器（selector），该选择器由一个描述符表的索引构成。描述符表中的每一项都定义了一个24位的物理基址，允许访问16MB RAM，在当时这是一个很不可思议的数量。不过，80286仍然是16位CPU，因此线性地址空间仍然被限制在64KB。 1985年的80386 CPU突破了这一限制。该芯片最终砍断了16位寻址的锁链，将线性地址空间推到了4GB，并在引入32位线性地址的同时保留了基本的选择器/描述符架构。幸运的是，80286的描述符结构中还有一些剩余的位可以拿来使用。从16位迁移到32位地址后，CPU的数据寄存器的大小也相应的增加了两倍，并同时增加了一个新的强大的寻址模型。真正的32位的数据和地址为程序员带了实际的便利。事实上，在微软的Windows平台真正完全支持32位模型是在好几年之后。Windows NT的第一个版本在1993年7月26日发布，实现了真正意义上的Win32 API。但是Windows 3.x程序员仍然要处理由独立的代码和数据段构成的64KB内存片，Windows NT提供了平坦的4GB地址空间，在那儿可以使用简单的32位指针来寻址所有的代码和数据，而不需要分段。在内部，当然，分段仍然在起作用，就像我在前面提及的那样。不过管理段的所有责任都被移给了操作系统。 存储器管理（二） 一、目的 本课题实验的目的是，使学生实验存储器管理系统的设计方法；加深对所学各种存储器管理方案的了解；要求采用一些常用的存储器分配算法，设计一个存储器管理模拟系统并调试运行。 二、题目 存储器管理 三、要求及提示 1、要求采用一种常用的存储器分配算法，设计一个存储器管理模拟系统。允许进行 多次的分配和释放，并可向用户反馈分配和释放情况及当前内存的情况；采用 “命令菜单”选择和键盘命令输入的会话方式，根据输入请求调用分配模块， 或回收模块，或内存查询模块，或最终退出系统。 2、编程实现。 3、工具：C语言或其它高级语言 4、实验时间：3学时 四、实验报告 1、写出存储器管理的思想。 2、画出算法流程图和设置的数据结构。 3、写出调试程序出现的问题及解决的方法。 4、打印实验报告及程序清单。 5、报告给出测试的结果。 五、范例 采用可变分区存储器管理方案的模拟系统。 1、问题描述 该模拟系统的外部特性与真实系统基本一样。存储分配算法采用首次适应法。用“拼，接”和“紧凑”技术来处理存储器碎片。 2、算法 存储分配算法采用首次适应（FF）法。根据指针freep查找自由链，当找到第一块可满足分配请求的空闲区时便分配之。当某空闲区被分配后的剩余空闲区空间大于规定的碎片最小容量min时，则形成一个较小的空闲区留在自由链中。 回收时，根据MAT将指定分区链入自由链。若该分区有前邻或后邻空闲分区，则将他们拼接成一块加大的空闲区。 当某个分配请求不能被满足，但此时系统中所有碎片总量满足分配请求的容量时，系统立即进入内存“紧凑”以消除碎片。即将各作业占用区集中下移到用户内存区的下部（高地址部分），形成一片连接的作业区，而在用户内存区的上部形成一块较大的空闲区。然后再进行分配。 本系统的主要程序模块包括：分配模块ffallocation，回收模块ffcolection，紧凑模块coalesce及命令处理模块menu。Menu用以模拟系统的输入，采用“命令菜单”选择和键盘命令输入的会话方式，根据输入请求调用分配模块，或回收模块，或内存查询模块，或最终退出系统。 系统的主流程如图3所示。 3、数据结构 （1）自由链与区头。内存空闲区采用自由链结构。链首由freep指向，链中各个空 第九章习题 1.在一个请求分页虚拟存储管理系统中，一个作业共有5页，执行时其访问 页面次序为： (1) 1、4、3、1、2、5、1、4、2、1、4、5。 (2) 3、2、1、4、4、5、5、3、4、3、2、1、5。 若分配给该作业三个页框，分别采用FIFO和LRU面替换算法，求出各自的缺页中断次数和缺页中断率。 答：(1) 采用FIFO为9次，9/12=75%。采用LRU为8次，8/12=67%。 (2) 采用FIFO和LRU均为9次，9/13=69%。 2.一个32位地址的计算机系统使用二级页表，虚地址被分为9位顶级页表， 11位二级页表和偏移。试问：页面长度是多少虚地址空间共有多少个页面 答：因为32-9-11=12，所以，页面大小为212B=4KB，页面个数为29+11=220个。 3.一台机器有48位虚地址和32位物理地址，若页长为8KB，问页表共有多 少个页表项如果设计一个反置页表，则有多少个页表项 答:8KB=213B.页表共有248-13=235个页表项。 反置页表，共有232-13=219个页表项。 4.一个有快表的请页式虚存系统，设内存访问周期为1微秒，内外存传送一 个页面的平均时间为5毫秒。如果快表命中率为75%，缺页中断率为10%。忽略快表访问时间，试求内存的有效存取时间。 答：快表命中率为75%，缺页中断率为10%，所以，内存命中率为15%。故内存的有效存取时间=1×75%+2×15%+(5000+2)×10%=微秒。 5.在请求分页虚存管理系统中，若驻留集为m个页框，页框初始为空，在长 为p的引用串中具有n个不同页面(n>m)，对于FIFO、LRU两种页面替换算法，试给出缺页中断的上限和下限，并举例说明。 答：对于FIFO、LRU两种页面替换算法，缺页中断的上限和下限：为p和n。因为有n 个不同页面，无论怎样安排，不同页面进入内存至少要产生一次缺页中断，故下限为n次。由于m 同组同学学号： 同组同学姓名： 实验日期：交报告日期： 实验(No. 4 )题目：编程与调试：内存管理 实验目的及要求： 实验目的： 操作系统的发展使得系统完成了大部分的内存管理工作，对于程序员而言，这些内存管理的过程是完全透明不可见的。因此，程序员开发时从不关心系统如何为自己分配内存，而且永远认为系统可以分配给程序所需的内存。在程序开发时，程序员真正需要做的就是：申请内存、使用内存、释放内存。其它一概无需过问。本章的3个实验程序帮助同学们更好地理解从程序员的角度应如何使用内存。 实验要求： 练习一：用vim编辑创建下列文件，用GCC编译工具，生成可调试的可执行文件，记录并分析执行结果，分析遇到的问题和解决方法。 练习二：用vim编辑创建下列文件，用GCC编译工具，生成可调试的可执行文件，记录并分析执行结果。 练习三：用vim编辑创建下列文件，用GCC编译工具，生成可调试的可执行文件，记录并分析执行结果。 改编实验中的程序，并运行出结果。 实验设备：多媒体电脑 实验内容以及步骤： 在虚拟机中编写好以下程序： #include 计算机操作系统存储管理练习题
系统运行环境配置与安装说明
操作系统课程设计内存管理
windows操作系统内存管理方式综述
实验三 存储管理指导
操作系统内存管理原理
实验 存储器管理(二)
操作系统第九章习题,存储管理
操作系统 内存管理实验报告
相关主题
文本预览