下载文档原格式
实验四 用先进先出（FIFO ）页面调度算法处理缺页中断1．实验目的深入了解页式存储管理如何实现地址转换；进一步认识页式虚拟存储管理中如何处理缺页中断。
2．实验预备知识页式存储管理中的地址转换的方法；页式虚拟存储的缺页中断处理方法。
3．实验内容编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。
实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所作工作进程测试。
假定主存64KB ，每个主存块1024字节，作业最大支持到64KB ，系统中每个作业分得主存块4块。
4．提示与讲解页式存储管理中地址转换过程很简单，假定主存块的大小为2n 字节，主存大小为2m'字节和逻辑地址m 位，则进行地址转换时，首先从逻辑地址中的高m-n 位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m'-n 位，最后从逻辑地址中取得低n 位放入物理地址的低n 位就得到了物理地址，过程如图1所示。
图1 页式存储管理系统地址转换示意图地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程，模拟地址转换的流程图如图2所示（实验中假定主存64KB ，每个主存块1024字节，逻辑地址即n=10,m'=16，物理地址中块号6位、块内地址10位；作业最大64KB，即m=16，逻辑地址中页号6位、页内地址10位）。
在页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则按上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”，由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。
页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过）。
（答案在后面）一、 填空题（每空1分,共10分)1. 常见的I/O 控制方式有程序I/O 方式、 中断 I/O 控制方式、 DMA I/O 控制方式和 通道 I/O 控制方式四种。
2. 操作系统向用户提供的两个基本接口是 程序 接口和 用户 接口。
3. 若在一分页存储管理系统中，某作业的页表如下所示。
已知页面大小为1024字节，逻辑地址（3082）10转化得到的物理地址是 6154 . 4. 具有多路性、独立性、及时性和交互性特征的操作系统是 分时操作系统.5. 通道用于控制 设备控制器 与内存之间的信息交换。
6. 事务的最基本特性是. 7. 若盘块大小为4KB ，每个盘块号占4字节，在采用两级索引时允许的最大文件长度为 4GB 。
二、单选题（每题2分,共20分）1. 用磁带作为文件存贮介质时，文件只能组织成（ )。
A. 顺序文件B. 链接文件 C 。
索引文件D. 目录文件2. 一作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，则其响应比是（ C ）。
A. 2B. 1C. 3D. 0。
5 3. 文件系统采用多级目录结构后，对于不同用户的文件，其文件名( C )。
A 。
应该相同 B. 应该不同 C. 可以相同，也可以不同 D 。
受系统约束 4. 死锁预防是保证系统不进入死锁状态的静态策略，其解决方法是破坏产生死锁的四个必要条件之一。
下列方法中破坏了“循环等待”条件的是( D ）. A 。
银行家算法 B. 一次性分配策略 C. 剥夺资源法 D 。
资源有序分配法 5. 进程状态从就绪态到运行态的转化工作是由（B ）完成的。
A 。
作业调度B 。
进程调度 C. 页面调度 D 。
设备调度 6. 采用缓冲技术的主要目的是（C ）。
A. 改善用户编程环境 B 。
提高CPU 的处理速度 C. 提高CPU 和设备间的并行程度 D 。
实现与设备无关性 7. 目录文件所存放的信息是（ D )。
操作系统第二次作业一、选择题1.虚拟存储器的容量是由计算机的地址结构决定的，若CPU有32位地址，则它的虚拟地址空间为【A】。
A．4G B．2G C．64K D．100K2.在请求分页存储管理方案中，若某用户空间为3个页面，页长1KB，现有页表如下，则逻辑地址1800。
A．1052 B．3124 C．1076 D．58963.【 A】用于管理各种不同的真实文件系统，是真实文件系统与服务之间的接口。
A.VFSB.Ext2C. vfatD.JFS4.用磁带作为文件存贮介质时，文件只能组织成【 A】A.顺序文件B.链接文件C.索引文件D.目录文件5.按数据组织分类，【 B】是以字节为单位直接读写的设备。
A．块设备B．字符设备C．网络设备 D．虚拟设备6.在现代操作系统中采用缓冲技术的主要目的是【 C】。
A．改善用户编程环境 B.提高CPU的处理速度C．提高CPU和设备之间的并行程度 D.实现与设备无关性7.【 D】是将大量计算机通过网络连接在一起，以获得极高的运算能力和数据共享的系统。
A. 实时系统B.分时系统C. 网络系统D.分布系统式8.若一个文件的访问控制权限值为0754，请问同组用户对该文件具有【 C】权限。
A. 可读B.可读可写C. 可读可执行D.没有权限9.操作系统的安全问题中【 D】是绕过安全性控制、获取对程序或系统访问权的程序方法。
A．木马B．病毒C．蠕虫D．后门10.虚拟存储器的最大容量是由【B】决定的。
A．页表长度B．计算机系统的地址结构和外存空间C．内存空间D．逻辑空间11.在请求分页存储管理方案中，若某用户空间为3个页面，页长1KB，现有页表如下，则逻辑地址2100。
A．1052 B．3124 C．1076 D．529612.下面的【 B】不是文件的物理存储结构。
A. 索引文件B.记录式文件C. 顺序文件D.链接文件13.从用户的角度看，引入文件系统的主要目的是【C】。
A. 实现虚拟存储B.保存文件系统C. 实现对文件的按名存取D.保存用户和系统的文档14.使用SPOOLing系统的目的是为了提高【D】的使用效率。
实验五存储管理（二）学号：姓名：班级：实验目的：1. 了解虚拟存储器。
2. 掌握分页存储管理的原理，熟悉段式存储和段页式存储管理。
3. 掌握常用的页面置换算法。
实验内容：一、选择：1.可变分区方式常用的主存分配算法中，（C）总是找到能满足作业要求的最大空闲区分配A、最佳适应算法B、首次适应算法C、最坏适应算法D、循环首次适应算法2．下列（A ）存储方式不能实现虚拟存储器A、分区B、页式C、段式D、段页式3．操作系统处理缺页中断时，选择一种好的调度算法对主存和辅存中的信息进行高效调度尽可能地避免（D）A、碎片B、CPU空闲C、多重中断D、抖动4．分页式存储管理的主要特点是（C）A、要求处理缺页中断B、要求扩充主存容量C、不要求作业装入到主存的连续区域D、不要求作业全部同时装人主存5．LRU页面调度算法淘汰（B）的页A、最近最少使用B、最近最久未使用C、最先进入主存D、将来最久使用6．分区管理要求对每一个作业都分配（A）的主存单元A、地址连续B、若干地址不连续的C、若干连续的页D、若干不连续的帧7．在存储管理中，采用覆盖与交换技术的目的是（A）A、节省主存空间B、物理上扩充主存容量C、提高CPU的效率D、实现主存共享8．分页虚拟存储管理中，缺页中断时，欲调度一页进入主存中，内存己无空闲块，如何决定淘汰已在主存的块时，（B）的选择是很重要的A、地址变换B、页面调度算法C、对换方式D、覆盖技术9．（D）存储管理兼顾了段式在逻辑上清晰和页式在存储管理上方便的优点A、分段B、分页C、可变分区方式D、段页式10．在固定分区分配中，每个分区的大小是（C）A、随作业长度变化B、相同C、可以不同但预先固定D、可以不同但根据作业长度固定11．下述（B）页面置换算法会产生Belady现象A、最佳置换算法B、先进先出算法C、LRU算法D、Clock算法12．在一个分页式存储管理系统中，页表的内容为：若页的大小为4KB，则地址转换机构将相对地址0转换成的物理地址是（A）。
四、计算题1、某虚拟存储器的用户编程空间共32个页面，每页为1KB ，内存为16KB 。
假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。
1．解：页式存储管理的逻辑地址分为两部分：页号和页内地址。
由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。
由“内存为16KB”，可知有16块，块号为4位。
逻辑地址0A5C （H ）所对应的二进制表示形式是：000 1010 0101 1100，根据上面的分析，下划线部分为页内地址，编码 “000 10” 为页号，表示该逻辑地址对应的页号为2。
查页表，得到物理块号是11（十进制），即物理块地址为：10 11，拼接块内地址10 0101 1100，得10 1110 0101 1100，即2E5C （H ）。
2、对于如下的页面访问序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5当内存块数量为3时，试问：使用FIFO 、LRU 置换算法产生的缺页中断是多少？写出依次产生缺页中断后应淘汰的页。
（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。
要求写出计算步骤。
） 2．解：采用先进先出（FIFO ）调度算法，页面调度过程如下：页面次序主存 页面 情况共产生缺页中断9次。
依次淘汰的页是1、2、3、4、1、2。
采用最近最少使用（LRU ）调度算法，页面调度过程如下： 共产生缺页中断10次。
依次淘汰的页是1、2、3、4、5、1、2。
3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。
现有以下作业序列：96K 、20K 、200K 。
若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么?空闲分区表页面次序1 2 3 4 1 2 5 1 2 3 4 5 主存 页面 情况3．解：若采用最佳适应算法，在申请96K 存储区时，选中的是5号分区，5号分区大小 与申请空间大d,-致，应从空闲分区表中删去该表项；接着申请20K 时，选中1号分区，分配后1号分区还剩下12K ；最后申请200K ，选中4号分区，分配后剩下18K 。
操作系统实验报告一、实验题目：用先进先出（FIFO）页面调度算法处理缺页中断。
[提示]（1）在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。
如果主存中已经没有空闲块，则可用FIFO 页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。
调出和装入后都要修改页表页表中对应页的标志。
（2）FIFO 页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。
假定作业被选中时，把开始的m 个页面装入主存，则数组的元素可定为m 个。
例如：P[0]，P[1]，….，P[m-1]其中每一个P[i]（i=0，1，….，m-1）表示一个在主存中的页面号。
它们的初值为：P[0]:=0，P[1]:=1，….，P[m-1]:=m-1用一指针k 指示当要装入新页时，应淘汰的页在数组中的位置，k 的初值为“0”。
当产生缺页中断后，操作系统选择P[k]所指出的页面调出，然后执行：P[k]:=要装入页的页号k:=(k+1) mod m，再由装入程序把要访问的一页信息装入到主存中。
重新启动刚才那条指令执行。
（3）编制一个FIFO 页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副本）而直接装入一个新页将其覆盖。
因此在页表中增加是否修改过的标志，为“1”表示修改过，为“0”表示未修改过，格式为：由于是模拟调度算法，所以，不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。
把第一题中程序稍作修改，与本题结合起来，FIFO 页面调度模拟算法如图2-2。
（4）磁盘上，在磁盘上的存放地址以及已装入主存的页和作业依次执行的指令序列都同第一题中（4）所示。
于是增加了“修改标志”后的初始页表为：按依次执行的指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后的数组P 的值。
对⽤LRU和FIFO算法计算“缺页中断”的理解输⼊缺页次数页⾯流：0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2 FIFO分析：012發別調⼊內存，則內存：012(3次缺⾴)調⼊3逃汰最先進⼊的0,則內存：123(4次缺⾴)調⼊2來命中,則內存：123(內存中有2不缺⾴)調⼊1來命中,則內存：123(內存中有1不缺⾴)調⼊3來命中,則內存：123(內存中有3不缺⾴)調⼊5逃汰最先進⼊的1,則內存：235(5次缺⾴)2，3別別命中，則內存：235調⼊6逃汰最先進⼊的,則內存：356(6次缺⾴)調⼊2逃汰最先進⼊的,則內存：562(7次缺⾴)調⼊1逃汰最先進⼊的,則內存：621(8次缺⾴)最后2命中，所以缺页8次=============================在LRU算法中，最近最少使⽤的页⾯被先换出输⼊:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0写出LRU算法实现页⾯更换，并给出缺页次数.(设在内存中占四个页架）分析：1题⽬给了访问串7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 02题⽬给了内存中占四个页架3题⽬给了⽤LRU算法来实现。
要求：画出算法实现。
LRU给出⾏ 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0头-----> 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 01 2 0 3 0 4 2 3 0 3 2 1 2 0 1 70 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1底-----> 7 7 1 1 2 3 0 4 4 4 0 0 3 3 2 2淘汰出内存的页⾯： 7 1 4 3整个的表格是怎么来的呢？请注意：题⽬给了7, 写7；题⽬给了0，写0, 7下⼀格；题⽬给了1, 写1，0下⼀格；题⽬给了2, 写2，1下⼀格；注意：已经四个了从上到下是：2107达到了2的要求：内存中占四个页架。
缺页中断及页⾯置换算法1. 缺页中断 在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页⾯是否存在于内存中。
每当所要访问的页⾯不在内存时，会产⽣⼀次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的⼀页，将其调⼊内存。
缺页本⾝是⼀种中断，与⼀般的中断⼀样，需要经过4个处理步骤： 1. 保护CPU现场 2. 分析中断原因 3. 转⼊缺页中断处理程序进⾏处理 4. 恢复CPU现场，继续执⾏ 但是缺页中断时由于所要访问的页⾯不存在与内存时，有硬件所产⽣的⼀种特殊的中断，因此，与⼀般的中断存在区别： 1. 在指令执⾏期间产⽣和处理缺页中断信号 2. ⼀条指令在执⾏期间，可能产⽣多次缺页中断 3. 缺页中断返回时，执⾏产⽣中断的那⼀条指令，⽽⼀般的中断返回时，执⾏下⼀条指令2. 页⾯置换算法 进程运⾏过程中，如果发⽣缺页中断，⽽此时内存中有没有空闲的物理块是，为了能够把所缺的页⾯装⼊内存，系统必须从内存中选择⼀页调出到磁盘的对换区。
但此时应该把那个页⾯换出，则需要根据⼀定的页⾯置换算法（Page Replacement Algorithm)来确定。
2.1 最佳置换（Optimal， OPT)2.1.1 基本思想 置换以后不再被访问，或者在将来最迟才回被访问的页⾯，缺页中断率最低。
但是该算法需要依据以后各业的使⽤情况，⽽当⼀个进程还未运⾏完成是，很难估计哪⼀个页⾯是以后不再使⽤或在最长时间以后才会⽤到的页⾯。
所以该算法是不能实现的。
但该算法仍然有意义，作为很亮其他算法优劣的⼀个标准。
2.1.2 算例 采⽤固定分配局部置换的策略，嘉定系统为某进程在内存中分配了3个物理块，页⾯访问顺序为2、3、2、1、5、2、4、5、3、2、5、2。
假定系统未采⽤预调页策略，即未事先调⼊任何页⾯。
进程运⾏时，⼀次将2、3、1三个页⾯调⼊内存，发⽣3次缺页中断。
当第⼀次访问页⾯5时，产⽣第4次缺页中断，根据OPT算法，淘汰页⾯1，因为它在以后不会在使⽤了；第5次缺页中断时，淘汰页⾯2，因为它在5、3、2三个页⾯中，是在将来最迟才会被页⾯访问的页⾯。
页面置换算法大题
页面置换算法是操作系统中的一种调度算法，用于解决内存管理中的问题。
它可以将内存中的页面（也就是存储单元）与外存中的页面进行交换，以实现内存空间的有效管理。
常见的页面置换算法有以下几种：
1. 先进先出（FIFO）算法：按照页面进入内存的先后顺序进
行置换，先进入内存的页面将先被置换出去。
这种算法简单直观，但是容易出现Belady异常，即页面置换频率增加导致缺
页率上升的现象。
2. 最近最久未使用（LRU）算法：根据页面最近的使用情况进行置换，最近使用过的页面会被保留在内存中，而最久未使用过的页面将会被置换出去。
这种算法相对较为复杂，需要记录每个页面最近的使用时间，并进行相应的计算。
3. 最不经常使用（LFU）算法：根据页面使用的频率进行置换，使用频率最低的页面将被置换出去。
该算法需要记录每个页面的使用次数并进行相应的计算。
4. 时钟（Clock）算法：通过维护一个类似于时钟的循环链表
结构，当需要进行页面置换时，顺时针遍历链表，找到一个未被访问过的页面进行置换。
这种算法相对简单，适合于硬件实现。
5. 最佳置换（OPT）算法：根据未来一段时间内每个页面的访
问情况进行置换，选择未来最久才会被访问的页面进行置换。
这种算法需要对未来一段时间内的页面访问情况进行预测，因此比较困难。
每种页面置换算法都有其优势和局限性，选择合适的页面置换算法需要根据具体的应用场景和需求来进行权衡和选择。
//页面调度算法（FIFO）#include<stdio.h>#define TRUE 1#define FALSE 0#define MAX 7 // 页的最大数#define IN 4 // 在主存中的页数#define count 13 // 指令数量int P[IN]; // 表示已在主存中的页面int k; // 表示P数组中最先进入内存的页的位置typedef struct{int num; // 页号bool pre; // 标志int random; // 主存块号bool revise; // 修改标志int location; // 在磁盘上的位置}Page_Item;Page_Item Page_Record[MAX];// 指令数据结构typedef struct{char oper; // 操作符int Page_Num; // 页号int Unit_Num; // 单元号}Instruction;Instruction IC[count];// 初始化指令和页表void Init(){k=0; // 指向最先进入内存的页// 初始化页表Page_Record[0].num=0;Page_Record[0].pre=TRUE;Page_Record[0].random=5;Page_Record[0].revise=FALSE;Page_Record[0].location=011;Page_Record[1].num=1;Page_Record[1].pre=TRUE;Page_Record[1].random=8;Page_Record[1].revise=FALSE;Page_Record[1].location=012; Page_Record[2].num=2;Page_Record[2].pre=TRUE; Page_Record[2].random=9; Page_Record[2].revise=FALSE; Page_Record[2].location=013;Page_Record[3].num=3;Page_Record[3].pre=TRUE; Page_Record[3].random=1; Page_Record[3].revise=FALSE; Page_Record[3].location=021;Page_Record[4].num=4;Page_Record[4].pre=FALSE; Page_Record[4].random=0; Page_Record[4].revise=FALSE; Page_Record[4].location=022;Page_Record[5].num=5;Page_Record[5].pre=FALSE; Page_Record[5].random=0; Page_Record[5].revise=FALSE; Page_Record[5].location=023;Page_Record[6].num=6;Page_Record[6].pre=FALSE; Page_Record[6].random=0; Page_Record[6].revise=FALSE; Page_Record[6].location=121;// 初始化指令序列IC[0].oper='+';IC[0].Page_Num=0;IC[0].Unit_Num=70;IC[1].oper='+';IC[1].Page_Num=1;IC[1].Unit_Num=50;IC[2].oper='*';IC[2].Page_Num=2;IC[2].Unit_Num=15;IC[3].oper='w';IC[3].Page_Num=3;IC[3].Unit_Num=21;IC[4].oper='r';IC[4].Page_Num=0;IC[4].Unit_Num=56;IC[5].oper='-';IC[5].Page_Num=6;IC[5].Unit_Num=40;IC[6].oper='>';IC[6].Page_Num=4;IC[6].Unit_Num=53;IC[7].oper='+';IC[7].Page_Num=5;IC[7].Unit_Num=23;IC[8].oper='w';IC[8].Page_Num=1;IC[8].Unit_Num=37;IC[9].oper='r';IC[9].Page_Num=2;IC[9].Unit_Num=78;IC[10].oper='+';IC[10].Page_Num=4;IC[10].Unit_Num=1;IC[11].oper='r';IC[11].Page_Num=6;IC[11].Unit_Num=84;IC[12].oper='#';IC[12].Page_Num=0;IC[12].Unit_Num=0;}// 根据FIFO算法替换页,所需要的参数是被调入页的页结构体void replace(Page_Item page){// 被替换的页已经修改了if(TRUE==Page_Record[P[k]].revise){// 修改被调出页的存在标志Page_Record[P[k]].pre=FALSE;// 修改被调出页的修改标志Page_Record[P[k]].revise=FALSE;printf("调出%d页\n",P[k]);}// 将调入页的存在标志修改为TRUEpage.pre=TRUE;// 将被调出页的主存块号赋给调入页的主存块号page.random=Page_Record[P[k]].random;// 将调入页的页号赋给P[k]P[k]=page.num;printf("调入%d页\n",page.num);// 修改k指针k=(k+1)%IN;}// 指令执行过程void excute(){int i=0; // 指向当前正在执行的指令while('#'!=IC[i].oper){printf("执行%c指令,需%d页\n",IC[i].oper,IC[i].Page_Num);// 若正在执行的指令所需的页不在内存中if(FALSE==Page_Record[IC[i].Page_Num].pre){printf("该页不在内存中,请求调入.........\n");// 调用替换函数，调入所需的页replace(Page_Record[IC[i].Page_Num]);}// 修改指令对该页的操作if('+'==IC[i].oper||'*'==IC[i].oper||'-'==IC[i].oper||'>'==IC[i].oper){printf("%c指令修改了%d页\n",IC[i].oper,IC[i].Page_Num);// 修改该页的修改标志Page_Record[IC[i].Page_Num].revise=TRUE;}i++; // 指向下一条指令}for(i=0;i<IN;i++){if(TRUE==Page_Record[P[i]].revise){printf("%d页写回外存!\n",P[i]);}}}void main(){Init();excute();}。
