学号P7******* 专业计算机科学与技术姓名
实验日期2017/12/7教师签字成绩
实验报告
【实验名称】磁盘调度——先来先服务策略最短寻道策略【实验目的】
磁盘调度中寻道时间直接影响到数据访问的快慢，通过本次实验学习如何处理好磁盘寻道时间。
【实验原理】
1. 先来先服务算法
先来先服务算法根据进程请求访问磁盘的先后次序进行调度。
2. 最短寻道时间优先算法
最短寻道时间优先算法要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。
【数据结构和符号说明】
ypedef struct Track
{
int id;//磁道序列
int state=0;//是否访问过，未被访问置状态为0
} Track;
Track track[N];//最大磁道数为100
Track track1[N];
int step[N];//移动距离
int num,i,current_track,num1;//需要访问的次数
函数说明：
void init()//初始化程序
void input()//输入函数
void FCFS()//先来先服务
int abs(int a,int b)//相减的绝对值
int Serch_min_pos()//寻找到当前磁道最短的需求磁道void SSTF()//最短寻道优先
void output(Track a[])//输出函数
void output_average_track()//输出平均寻道时间
int show()//显示用户界面
先来先服务（FCFS）
最短寻道时间优先（SSTF）
寻找当前磁道最近需求磁道
代码：
#include
#define N 100
typedef struct Track
{
int id;//磁道序列
int state=0;//是否访问过，未被访问置状态为0
} Track;
Track track[N];//最大磁道数为100
Track track1[N];
int step[N];//移动距离
int num,i,current_track,num1;
void init()//初始化程序
{
num=0;
for (i=0; i { track[i].state=-1;//id置为1 track1[i].state=-1; step[i]=-1;//移动距离为-1 } } void input()//输入函数 { printf("输入当前磁道\n"); scanf("%d",¤t_track); num1=current_track; printf("输入要访问的磁道数目\n"); scanf("%d",&num); printf("输入要访问磁道序列\n"); for(i=0; i scanf("%d",&track[i].id); } void FCFS()//先来先服务 { for(i=0; i { if((current_track-track[i].id)<0)//求移动距离 step[i]=track[i].id-current_track; else step[i]=current_track-track[i].id;//取绝对值 track[i].state=1;//状态置为1 current_track=track[i].id;//更新当前磁道 } } int abs(int a,int b)//相减的绝对值 { return a-b>0?a-b:b-a; } int Serch_min_pos()//寻找到当前磁道最短的需求磁道 { int min=45536;//最小距离标志 int pos; for(int i=0; i if(track[i].state==1) continue; else if(min>abs(track[i].id,current_track))//寻找最小距离 { min=abs(track[i].id,current_track); pos=i; } track[pos].state=1; return pos;//返回在数组中的位置 } void SSTF()//最短寻道优先 { for(i=0; i { track1[i]=track[Serch_min_pos()];//更新到要输出的数组中 step[i]=abs(track1[i].id,current_track);//移动距离 current_track= track1[i].id;//标志 } } void output(Track a[])//输出函数 { printf("\n\n <从%d号磁道开始>\n",num1); printf("==================================================\n");//排班 printf("被访问的下一个磁道\t\t移动距离（磁道数）\n"); for(i=0; i printf("\t%4d\t\t||\t%4d\n",a[i].id,step[i]); printf("==================================================\n"); } void output_average_track()//输出平均寻道时间 { double sum=0;//和 for(i=0; i sum+=step[i]; printf(" 平均寻道长度%3.2f\n\n\n",sum/num);//输出} int show()//显示用户界面 { int choose;//选择 printf("\n******************早期的磁盘调度算法******************\n"); printf("\t\t1、先来先服务(FCFS)\n"); printf("\t\t2、最短寻道时间优先（SSTF)\n"); printf("\t\t3、退出（EXIT）\n"); scanf("%d",&choose); return choose; } int main() { do { init(); switch(show())//返回值是选择 { case 1://FCFS input(); FCFS(); output(track); output_average_track(); break; case 2://最短寻道 input(); SSTF(); output(track1); output_average_track(); break; case 3://退出 return 0; default: break; } } while(1); return 0; } 截图： 主界面开始，输入选择先来先服务还是最短寻道优先，输入当前磁道，输入要访问的磁道，输入要访问的磁道序列。 先来先服务(FCFS) 最短寻道优先（SSTF） 【小结与讨论】 1、先来先服务算法是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是较为公平与简单，并且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长；而最短寻道时间优先算法要求每次访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短，因为只能做到局部最优。 2、本实验用数组就可以很方便简洁地解决问题，唯一需要注意的就是在算法中，每一次寻道需要对之前的磁道号进行暂存设置一个current_track(当前磁道)，如果已查询到，需将状态置为1，这样才方便寻找和计算寻道距离。 3、FCFS算法根据磁道号需要被访问的顺序依次访问磁道，所以磁道被访问顺序在磁道需要顺序确定时，即被确定，然后用依次减法即可算出移动距离，相对来说实验的复杂度较低，易于实现。 4、SSTF算法则相较于FCFS算法复杂得多。在确定被访问的下一个磁道号 时，需要计算后面每一个磁道号与当前磁道号的距离，然后取最小距离的磁道号作为被访问的下一个磁道号。即实现SSTF算法需找到最小距离的磁道号再写入。 5、本次实验通过编写程序让我对磁盘的相关调度有了更深入的理解，对计算机内部原理也有了更深的认识，代码能力也有所提高。 目录 1．问题的提出 (2) 1.1关于页面置换算法模拟程序问题的产生 (2) 1.2任务分析 (2) 2．需求分析 (2) 3．方案设计 (3) 4．总体设计 (4) 4.1程序N-S图 (4) 4.2主要的函数 (4) 4.3主要流程图及代码 (5) 4.3.1 FIFO（先进先出） (5) 4.3.2 LRU（最近最久未使用） (6) 4.3.3 OPT（最佳置换算法） (8) 4.4实现结果 (11) 5．程序测试 (14) 5.1设计测试数据 (14) 5.2测试结果及分析 (15) 摘要 随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要 提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果. 本课程设计是学生学习完《操作系统教程》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。 关键词：编制页面置换算法模拟程序、打印页面、FIFO页面算法、LRU页面置换算法、OPT页面置换算法。 一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、简单时钟(钟表)算法（CLOCK） 命中率＝１－页面失效次数／页地址流(序列)长度 三、实验原理 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 四、算法描述 本实验的程序设计基本上按照实验内容进行。即使用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’ D：顺序执行一条指令，其地址为m’+1 ●假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的 一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。 定义信号量sum,mutex，初值分别为100，1。（3分）则第i个读者的活动描述为：procedure P i(i=1,2,3……) begin wait(sum); wait(mutex); 登记； signal(mutex); 进入阅览室； 阅读; wait(mutex); 登记； signal(mutex); 离开阅览室； signal(sum); end ●请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向 有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。 将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B 方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下： Var SA,SB,mutex:semaphore:=1,1,1; CountA,countB:integer:=0,0: begin parbegin process A: begin wait(SA); if(countA=0) then wait(mutex); countA:=countA+1; signal(SA); 过独木桥； wait(SA); countA:=countA-1; if (countA=0) then signal(mutex); signa(SA); end process B: begin wait(SB); 操作系统课程设计-页面置换算法C语言 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求 1、编写算法，实现页面置换算法FIFO、LRU； 2、针对内存地址引用串，运行页面置换算法进行页面置换； 3、算法所需的各种参数由输入产生（手工输入或者随机数产生）； 4、输出内存驻留的页面集合，页错误次数以及页错误率； 四．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、设计说明 1、采用数组页面的页号 2、FIFO算法，选择在内存中驻留时间最久的页 面予以淘汰； 分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。3、LRU算法，根据页面调入内存后的使用情况 进行决策； 同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。 选择置换算法，先输入所有页面号，为系统分 淮海工学院计算机工程学院实验报告书 课程名：《操作系统原理A 》 题目：虚拟存储器管理 页面置换算法模拟实验 班级：软件*** 学号：20**1228** 姓名：**** 一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内， 此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问 一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前 实验4 页面置换算法（2学时） 一、实验目的 通过实验加强对虚拟存储管理中页面置换算法的理解和掌握。 二、实验内容 编写程序实现虚拟存储管理中OPT,FIFO,LRU页面置换算法。 三、实验要求 1、任意给出一组页面访问顺序（如页面走向是1、 2、5、7、5、7、1、4、 3、5、6、 4、3、2、1、 5、2）。 2、分配给该作业一定的物理块（如3块、4块等）。 3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。 4、每访问一个页面均需给出内存中的内容（内存中的页面号），若有淘汰还需给出淘汰的页面号。 5、通过给出特殊的页面访问顺序，分配不同的物理块，利用FIFO 算法计算其缺页率，进一步理解Belady现象。 6、（附加）实现CLOCK置换算法，修改位可在确定页面号时直接任意给出。 代码部分： #include int v; int i; int a; srand(time(NULL)); for(i=0; i 6. 算法题（共32个题目） 200348. 在信号量机制中，若P（S）操作是可中断的，则会有什么问题？ 此题答案为：答： P（S）的操作如下： Begin S.Value:= S.Value-1; ① If S.Value<0 Then ② Begin Insert(*,S.L); Block(*) ③ End End. 若P（S）可中断的，例如进程A在执行了语句①之后从CPU上退 下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value 的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误： 本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。 200350. 何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？ ＃define true; # define false; Int flag[2]; flag[1]=flag[2]=false; enter-crtsec(i) int i; { While(flag[1-i]) flag[i]=true; } feave-crtsec(i) Int i; { flag[i]=false; } process I; … Enter-crtsec(i); In critical section; Leave-crtsec(i); 此题答案为：答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。 从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。 这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。 200353. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题： （1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。 （2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。 Cobegin PROCESS Pi(i=1,2,…) Begin 进入售票厅； 购票； 退出； End; 专业计算机科学与技术 目录 1.设计目的 (2) 2.课设要求 (2) 3.系统分析 (3) 4.系统设计 (3) 4.1问题分析 (3) 4.2程序整体框图 (5) 4.3 FIFO算法 (5) 4.4 LRU算法 (6) 4.5 OPT算法 (7) 5.功能与测试 (8) 5.1开始界面 (8) 5.2 FIFO算法 (9) 5.3 LRU算法 (10) 5.4 OPT算法 (10) 6.结论 (11) 7.附录 (12) 1.设计目的 1、存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本次设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。 2、提高自己的程序设计能力、提高算法设计质量与程序设计素质； 2.课设要求 设计一个请求页式存储管理方案。并编写模拟程序实现之。要求包含： 1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成： ①50%的指令是顺序执行的； ②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； 具体的实施方法是： 在[0，319]的指令地址之间随机选区一起点M; 顺序执行一条指令，即执行地址为M+1的指令； 在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’; 顺序执行一条指令，其地址为M’+1； 在后地址[M’+2，319]中随机选取一条指令并执行； 重复A—E，直到执行320次指令。 2．指令序列变换成页地址流 设：（1）页面大小为1K； 用户内存容量为4页到32页； 用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 实验四页面置换算法模拟（2）一．题目要求： 设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再 被访问的页面换出。 2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留 时间最久的页面予以淘汰。 3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的： 1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 实验五. 请求页式存储管理的模拟 [实验内容]: 熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。 [实验要求]： 1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法和最近最久未使 用算法（LRU）置换算法后，给出最佳置换算法的模拟程序实现，并集成到参考程序中。 2、执行2个页面置换模拟程序，分析缺页率的情况。最好页框数和访问序列长度可调节，在使用同一组访问序 列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。 3、在每次产生置换时要求显示分配状态和缺页率。程序的地址访问序列通过随机数产生，要求具有足够的长度。 最好页框数和访问序列长度可调节。 实验的执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）： 程序源代码： #include 操作系统期末考试（A） 一、单项选择题（在每小题的四个备选答案中，只有一个是正确的，将其写在题干的括号中。每小题2分，共20分） 1、文件系统的主要组成部分是（） A、文件控制块及文件 B、I/O文件及块设备文件 C、系统文件及用户文件 D、文件及管理文件的软件 2、实现进程互斥可采用的方法（） A、中断 B、查询 C、开锁和关锁 D、按键处理 3、某页式管理系统中，地址寄存器的低9位表示页地址，则页面大小为（） A、1024字节 B、512字节 C、1024K D、512K 4、串联文件适合于（）存取 A、直接 B、顺序 C、索引 D、随机 5、进程的同步与互斥是由于程序的（）引起的 A、顺序执行 B、长短不同 C、信号量 D、并发执行 6、信号量的值（） A、总是为正 B、总是为负 C、总是为0 D、可以为负整数 7、多道程序的实质是（） A、程序的顺序执行 B、程序的并发执行 C、多个处理机同时执行 D、用户程序和系统程序交叉执行 8、虚拟存储器最基本的特征是（） A、从逻辑上扩充存容量 B、提高存利用率 C、驻留性 D、固定性 9、飞机定票系统是一个（） A、实时系统 B、批处理系统 C、通用系统 D、分时系统 10、操作系统中，被调度和分派资源的基本单位，并可独立执行的实体是（） A、线程 B、程序 C、进程 D、指令 二、名词解释（每小题3分，共15分） 1.死锁: 2.原子操作: 3.临界区: 4.虚拟存储器: 5.文件系统: 三、判断改错题（判断正误，并改正错误，每小题2分，共20分） 1、通道是通过通道程序来对I/O设备进行控制的。（） 2、请求页式管理系统中，既可以减少外零头，又可以减少零头。（） 3、操作系统中系统调用越多，系统功能就越强，用户使用越复杂。（） 4、一个进程可以挂起自已，也可以激活自已。（） 5、虚拟存储器的最大容量是由磁盘空间决定的。（） 6、单级文件目录可以解决文件的重名问题。（） 7、进程调度只有一种方式：剥夺方式。（） 8、程序的顺度执行具有顺序性，封闭性和不可再现性。（） 9、并行是指两个或多个事件在同一时间间隔发生，而并发性是指两个或多个事件在同 一时刻发生。（） 10、进程控制一般都由操作系统核来实现。（） 四、简答题（每小题5分，共25分） 1、简述死锁产生的原因及必要条件。 2、什么是多道程序技术，它带来了什么好处？ 实验编号４ 名称页面置换算法模拟 实验目的 通过请求页式存储管理中页面置换算法模拟设计，以便： 1、了解虚拟存储技术的特点 2、掌握请求页式存储管理中页面置换算法 实验容与步骤 设计一个虚拟存储区和存工作区，并使用FIFO和LRU算法计算访问命中率。 <程序设计> 先用srand()函数和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算相应的命中率。 <程序1> #include int pn, pfn; struct pfc_struct *next; }pfc_type; pfc_type pfc[32]; pfc_type *freepf_head,*busypf_head,*busypf_tail;//空闲页头指针，忙页头指针，忙页尾指针 int NoPageCount; //缺页次数 int a[total_instruction];//指令流数组 int page[total_instruction], offset[total_instruction];//每条指令的页和页偏移 void initialize( int ); void FIFO( int );//先进先出 void LRU( int );//最近最久未使用 void NRU( int );//最近最不经常使用 /**************************************************************************** main() *****************************************************************************/ void main(){ int i,s; //srand(10*getpid());//用进程号作为初始化随机数队列的种子//Linux版 srand(10*GetCurrentProcessId());//用进程号作为初始化随机数的种子//Windows版 s=rand()%320;//在[0，319]的指令地址之间随机选取一起点m for(i=0;i 实验5 页面置换算法 一、实验题目：页面置换算法（请求分页） 二、实验目的： 进一步理解父子进程之间的关系。 1）理解内存页面调度的机理。 2）掌握页面置换算法的实现方法。 3）通过实验比较不同调度算法的优劣。 4）培养综合运用所学知识的能力。 页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。 三、实验内容及要求 这是一个综合型实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。 程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series[]中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。要求： 1）每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。 设缺页的次数为diseffect。总的页面访问次数为total_instruction。 缺页率= disaffect/total_instruction 命中率= 1- disaffect/total_instruction 2）将为进程分配的内存页面数mframe 作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。 四、程序流程图 开始 创建子进程1 创建子进程2 结束 操作系统课程设计报告题目：页面置换算法模拟程序 学院名称: 专业班级： 学生姓名： 指导教师： 成绩： 目录 一、设计目的 (3) 二、设计题目 (3) 2.1设计内容 (3) 2.2设计要求 (3) 三、设计过程 (4) 3.1 FIFO（先进先出） (4) 3.2 LRU（最近最久未使用） (5) 3.3 OPT（最佳置换算法） (6) 3.4 随机数发生器 (7) 四、完整代码 (7) 五、运行结果演示 (13) 六、设计心得 (16) 七、参考文献 (16) 操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。 本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。 二、设计题目：页面置换算法模拟程序 2.1设计内容 编制页面置换算法的模拟程序。 2.2设计要求 1).用随机数方法产生页面走向，页面走向长度为L(15<=L<=20),L由控制台输入。 2).根据页面走向，分别采用Optinal、FIFO、LRU算法进行页面置换，统计缺页率。 3).假定可用内存块为m(3<=m<=5)，m由控制台输入，初始时，作业页面都不在内存。 4).要求写出一份详细的设计报告。课程设计报告内容包括：设计目的、设计内容、设计原理、算法实现、流程图、源程序、运行示例及结果分析、心得体会、参考资料等。 操作系统课程实验报告 断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出（FIFO）法。 2、算法流程图 3、步骤说明 （1）初始化 void init(){//初始化 int i; for (i = 0; i < page_frame_number; i++){ page_table[i].page_id = -1; page_table[i].load_time = -1; page_table[i].last_visit_time = -1; } } （2）选择算法，输入插入页面号。进入判断函数 int judge(){//判断页框是否满，或者页框里面是否已存在页面 int i; for (i = 0; i < page_frame_number; i++){ if (page_table[i].page_id == -1 || page_table[i].page_id == page_id) return i; } return -2; } 之后根据返回数的不同决定了不同类型 返回-2则说明页框满且页框里面没有存在要插入的页面。 返回-1则说明页框未满 返回其它数则说明页框里存在相同的页面 （3）//当没有空页框，并且页面本身也没有存在，则执行一下代码 qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp);//按照装入时间从小到大排序 page_table[0].page_id = page_id; page_table[0].load_time = counter; page_table[0].last_visit_time = counter; page_interrupt_number++; 将页框号为0的页面置换成最新插入的页面。 int cmp(const void *p, const void *q){//按照装入时间从小到大排序 int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q).load_time; if (c > 0) return 1; else return -1; } 排序函数，将页面按装入时间从小到大排序 （4）//如果页面未满，则将页面替换在空页框里 if (page_table[j].page_id == -1){ page_table[j].page_id = page_id; page_table[j].load_time = counter; page_table[j].last_visit_time = counter; page_interrupt_number++; 则将页面替换在页框号最小的空页框里 （5）//如果页面本身存在页框中，则执行一下代码 page_table[j].last_visit_time = counter; 则更新页面的最近访问时间 （6）qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp3);//按照装入时间从小到大排序 print(2); 打印出页表详细信息 printf("页表信息：\n页号页框号装入时间最近访问时间\n"); for (j = 0; j < page_frame_number; j++){ printf("%4d%8d%7d%7d\n", page_table[j].page_id, j, page_table[j].load_time, 课程设计报告 课程名称操作系统 课题名称页面置换算法模拟设计 专业通信工程 班级 学号 姓名 指导教师 2014年6 月29 日 湖南工程学院 课程设计任务书 课程名称操作系统 课题页面置换算法模拟设计 专业班级 学生姓名 学号 指导老师 审批 任务书下达日期2014 年 6 月23 日 任务完成日期2014 年 6 月29 日 目录 1课题概述 (4) 1.1设计要求 (4) 1.2 理论分析 (4) 2系统分析 (6) 3程序实现 (8) 4程序测试 (13) 5心得体会 (15) 6附录 (16) 7 评分表 (30) 课题：页面置换算法模拟设计 1课题概述 1.1设计要求 计算并输出下述各种算法在不同内存容量下的命中率。 A. FIFO先进先出的算法 B. LRR最近最少使用算法 C. OPT最佳淘汰算法（先淘汰最不常用的页地址） D. LFR最少访问页面算法 E. NUR最近最不经常使用算法 设计技术参数： （1）命中率=1-页面失效次数/页地址流长度 （2）本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。 （3）随机数产生方法，采用系统提供函数SRAND()和RAND ()来产生 1.2 理论分析 在进程运行过程中，若其所要访问的页面不在内存所需把他们调入内存，但内存已无空闲时，为了保证进程能够正常运行，系统必须从内存中调入一页程序或数据送磁盘的对换区中。但应将那个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上将讲，应将那些以后不再访问的页面换出，或把那些较长时间内不再访问的页面调出。目前存在着不同的算法，他们都试图更接近与理论上的目标。 淮海工学院计算机科学系实验报告书 课程名：《操作系统原理A 》 题目：虚拟存储器管理 页面置换算法模拟实验 班级： 学号： 姓名： 一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内， 此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问 一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前 页面置换算法实验报告 一、实验目的： 设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比较。 二、实验内容： ●虚拟内存页面总数为N，页号从0到N-1 ●物理内存由M个物理块组成 ●页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序 列串中的每个元素p表示对页面p的一次访问 ●页表用整数数组或结构数组来表示 ?符合局部访问特性的随机生成算法 1.确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页 数e，工作集移动率m（每处理m个页面访问则将起始位置p +1）， 以及一个范围在0和1之间的值t； 2.生成m个取值范围在p和p + e间的随机数，并记录到页面访问序 列串中； 3.生成一个随机数r，0 ≤r ≤1； 4.如果r < t，则为p生成一个新值，否则p = (p + 1) mod N； 5.如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。 三、实验环境： 操作系统：Windows 7 软件：VC++6.0 四、实验设计： 本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的数据结构实现，而是根据不同算法的特点用不同的数据结构来实现： 1、最佳置换和随机置换所需操作不多，用整数数组模拟内存实现； 2、先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内 存来实现； 3、CLOCK置换和改进的CLOCK置换具有循环队列的特性，故用循环队 列模拟内存实现； 4、所有算法都是采用整数数组来模拟页面访问序列。 计算机操作系统经典题库及答案 一填空： 1．操作系统为用户提供三种类型的使用接口，它们是(命令方式)和(系统调用)和图形用户界面。 2．主存储器与外围设备之间的数据传送控制方式有程序直接控制、(中断驱动方式)、(DMA方式)和通道控制方式。 3．在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，(运行时间短)的作业将得到优先调度；当各个作业要求运行的时间相同时，(等待时间长)的作业得到优先调度。 4．当一个进程独占处理器顺序执行时，具有两个特性：(封闭性)和可再现性。5．程序经编译或汇编以后形成目标程序，其指令的顺序都是以零作为参考地址，这些地址称为(逻辑地址)。 6．文件的逻辑结构分(流式文件)和记录式文件二种。 7．进程由程度、数据和(FCB)组成。 8．对信号量S的操作只能通过(原语)操作进行，对应每一个信号量设置了一个等待队列。 9．操作系统是运行在计算机(裸机)系统上的最基本的系统软件。 10．虚拟设备是指采用(SPOOLING)技术，将某个独享设备改进为供多个用户使用的的共享设备。 11．文件系统中，用于文件的描述和控制并与文件一一对应的是(文件控制块)。12．段式管理中，以段为单位，每段分配一个(连续区)。由于各段长度(不同)，所以这些存储区的大小不一，而且同一进程的各段之间不要求连续。 13．逻辑设备表（LUT）的主要功能是实现(设备独立性)。 14在采用请求分页式存储管理的系统中，地址变换过程可能会因为(缺页)和(越界)等原因而产生中断。 16. 段的共享是通过（共享段）表实现的。 17．文件的物理结构分为顺序文件、（索引文件）和（索引顺序文件）。 18．所谓（设备控制器），是一块能控制一台或多台外围设备与CPU并行工作的页面置换算法模拟程序-附代码
页面置换算法实验报告
操作系统经典习题+解释
操作系统课程设计-页面置换算法C语言
虚拟存储器管理 页面置换算法模拟实验
页面置换算法(操作系统试验)
计算机操作系统算法题(最全)
页面置换算法课程设计
实验四页面置换算法代码
《操作系统》实验五页面置换算法模拟
操作系统精彩试题及问题详解
页面置换算法模拟实验报告
实验5 页面置换算法
(流程图)页面置换算法课程设计
第7次 常用页面置换算法模拟实验
页面置换算法模拟设计
操作系统页面置换算法模拟实验
页面置换算法实验报告
计算机操作系统经典题库及答案
相关主题
文本预览