《计算机操作系统》实验要求.docx
《《计算机操作系统》实验要求.docx》由会员分享，可在线阅读，更多相关《《计算机操作系统》实验要求.docx（28页珍藏版）》请在冰点文库上搜索。
《计算机操作系统》实验要求
《计算机操作系统》实验要求
为了顺利完成操作系统课程实验，应做到：
（1）实验前，认真学习教材以及实验要求的相关内容，提前做好实验准备。
（2）实验结束后三天内提交实验报告的电子版和打印版。
实验报告内容应包括：
实验目的、实验内容、设计思路和流程框图，主要程序代码、测试结果以及实验总结。
（实验报告模板见“OS实验模板”）
（3）遵守机房纪律，服从指挥，爱护实验设备。
实验的验收将分为两个部分。
第一部分是上机操作，随机抽查程序运行和即时提问；第二部分是提交书面的实验报告。
要杜绝抄袭现象，一经发现雷同，双方成绩均以0分计算。
实验内容安排：
实验内容与要求
编写程序，模拟某个算法。
实验一和实验二选一，实验三必选
实验一
熟悉进程调度相关内容；根据进程调度算法，选择先来先服务、短进程优先、时间片轮转、高优先权优先调度等算法中的一个，编写算法模拟程序。
实验二
熟悉页面置换相关内容；选择最佳置换算法、先进先出置换算法、LRU置换算法中的一个，编写算法模拟程序。
实验三
熟悉银行家算法，并编写程序进行模拟。
实验一进程调度实验3
实验二页面置换算法模拟10
实验三银行家算法模拟15
实验一进程调度实验
【开发语言及实现平台或实验环境】
C++/C#
TurboC/MicrosoftVisualStudio6.0/MicrosoftVisualStudio.NET2010
【实验目的】
（1）加深对进程的概念及进程调度算法的理解；
（2）在了解和掌握进程调度算法的基础上，编制进程调度算法通用程序，将调试结果显示在计算机屏幕上，并检测机算和笔算的一致性。
【实验要求】
（1）了解进程调度；
（2）理解利用进程调度算法进行调度的原理；
（3）使用某种编程语言进行算法模拟。
【实验原理】
（注意：
这个仅是个例子，可以参考本例，选择其他算法进行实验）
一、例题：
设计一个有N个进程的进程调度算法。
进程调度算法：
采用最高优先数的调度算法（即把处理机分配给优先数最高的进程）。
每个进程有一个进程控制块（PCB）表示。
进程控制块可以包含如下信息：
进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
进程的优先数及需要的运行时间可以事先人为的指定（也可以由随机数产生）。
进程的到达时间为进程的输入的时间。
进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
就绪进程获得CPU后都只能运行一个时间片。
用已占用CPU时间加1表示。
如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤销该进程，如果运行一个时间片后，进程的已占用CPU时间还未达到所需要的运行时间，也就是进程还需要继续运行，此时应该将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。
重复以上过程，直到所要的进程都完成为止。
分析:
使用固定队列与静动态优先级结合每个优先级为0~0xFF,并且以小的数字为高优先级，大的数字为低优先级，每次皆使用循环得到最高优先级的进程并执行，然后将其动态优先级设置为最低，并将其他进程动态优先级提高，以使得每个进程都有机会运行。
进程的优先级与运行时间由随机数产生。
二、代码试例
#include
#include
#include
/*常量和状态定义*/
#definePRO_NUM0x05
#defineMAX_TIME0xFF
/*状态宏*/
#defineWAIT0x01
#defineRUN0x02
#defineFINISH0x03
#defineID_ERROR0x10
#defineMIN_PRIOR0xFF
#defineMAX_PRIOR0x00
typedefunsignedintUint32;
/*进程PCB*/
structPCB_Info
{
Uint32s_id;
Uint32s_static_prior;
Uint32s_dynamic_prior;
Uint32s_start_time;
Uint32s_need_time;
Uint32s_used_time;
Uint32s_state;
};
/*进程队列*/
PCB_Infog_queue[5];
Uint32g_time;
/*模拟进程执行函数*/
voidSimulator（）;
/*初始化5个进程函数*/
voidInit_Process（）;
/*初始化进程队列函数*/
voidInit_Queue（）;
/*创建进程函数*/
Uint32Create_Process（Uint32pri,Uint32needtime）;
/*系统运行函数*/
voidRun_Process（）;
/*得到最高优先级进程ID函数*/
Uint32Get_PriProcess（）;
/*进程时间片执行函数*/
voidWork_Process（Uint32id）;
/*改变进程状态和优先级函数*/
voidChange_Process（Uint32id）;
/*打印进程状态函数*/
voidPrint_State（）;
/*结束系统函数*/
voidEnd_Process（）;
/*入口函数*/
intmain（intargc,char*argv[]）
{
Simulator（）;
return0;
}
voidSimulator（）
{
Init_Process（）;
Run_Process（）;
End_Process（）;
}
voidInit_Process（）
{
inti;
Uint32id;
srand（（unsigned）time（NULL））;
Init_Queue（）;
for（i=0;i{
/*在这里修改随机数的范围，建议优先级取值为0到4之间，进程工作总时间为1到10之间*/
id=Create_Process（rand（）%4,1+rand（）%10）;
if（id!
=ID_ERROR）
{
printf（"**********************************\n"）;
printf（"创建进程成功\n"）;
printf（"进程ID号为:
%d\n",id）;
printf（"进程的静态优先权为:
%d\n",g_queue[id].s_static_prior）;
printf（"进程的动态优先权为:
%d\n",g_queue[id].s_dynamic_prior）;
printf（"进程的到达时间为:
%d\n",g_queue[id].s_start_time）;
printf（"进程需要时间为:
%d\n",g_queue[id].s_need_time）;
printf（"进程已用CPU时间为:
%d\n",g_queue[id].s_used_time）;
printf（"进程的状态为:
%d\n",g_queue[id].s_state）;
printf（"\n"）;
}
else
{
printf（"创建进程失败\n"）;
}
}
}
voidInit_Queue（）
{
inti;
for（i=0;i{
g_queue[i].s_id=i;
g_queue[i].s_dynamic_prior=MIN_PRIOR;
g_queue[i].s_need_time=0;
g_queue[i].s_start_time=0;
g_queue[i].s_static_prior=MIN_PRIOR;
g_queue[i].s_used_time=0;
g_queue[i].s_state=FINISH;
}
}
Uint32Create_Process（Uint32pri,Uint32needtime）
{
inti=0;
Uint32id=ID_ERROR;
for（i=0;i{
if（g_queue[i].s_state==FINISH）
{
id=g_queue[i].s_id;
g_queue[i].s_dynamic_prior=MIN_PRIOR;
g_queue[i].s_need_time=needtime;
g_queue[i].s_start_time=g_time;
g_queue[i].s_state=WAIT;
g_queue[i].s_static_prior=pri;
g_queue[i].s_used_time=0x0;
break;
}
}
returnid;
}
voidRun_Process（）
{
Uint32id;
while（（id=Get_PriProcess（））!
=ID_ERROR）
{
Work_Process（id）;
Change_Process（id）;
}
}
voidPrint_State（）
{
inti;
printf（"时间进程ID\t状态已用时间需要时间开始时间静优先级动优先级\n"）;
for（i=0;i{
printf（"%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",g_time,g_queue[i].s_id,g_queue[i].s_state,g_queue[i].s_used_time,g_queue[i].s_need_time,
g_queue[i].s_start_time,g_queue[i].s_static_prior,g_queue[i].s_dynamic_prior）;
}
}
Uint32Get_PriProcess（）
{
Uint32id=ID_ERROR;
inti,prev_id=ID_ERROR;
Uint32prior=MIN_PRIOR*2,temp_prior;
for（i=0;i{
if（g_queue[i].s_state!
=FINISH）
{
temp_prior=g_queue[i].s_dynamic_prior+g_queue[i].s_static_prior;
if（temp_prior<=prior）
{
id=i;
prior=temp_prior;
}
}
}
returnid;
}
voidWork_Process（Uint32id）
{
++g_time;
g_queue[id].s_state=RUN;
++g_queue[id].s_used_time;
Print_State（）;
}
voidChange_Process（Uint32id）
{
inti;
if（g_queue[id].s_need_time==g_queue[id].s_used_time）
{
g_queue[id].s_state=FINISH;
}
else
{
g_queue[id].s_dynamic_prior=MIN_PRIOR;
g_queue[id].s_state=WAIT;
}
for（i=0;i{
if（（i!
=id）&&（g_queue[i].s_state!
=FINISH））
{
g_queue[i].s_dynamic_prior>0?
--g_queue[i].s_dynamic_prior:
g_queue[i].s_dynamic_prior=0;
}
}
}
voidEnd_Process（）
{
printf（"所有进程结束状态:
\n"）;
Print_State（）;
printf（"所有进程已经结束!
\n"）;
}
实验二请求页式存储管理中常用页面置换算法模拟
【开发语言及实现平台或实验环境】
C++/C#
TurboC/MicrosoftVisualStudio6.0/MicrosoftVisualStudio.NET2010
【实验目的】
（1）了解内存分页管理策略
（2）掌握调页策略
（3）掌握一般常用的调度算法
（4）学会各种存储分配算法的实现方法。
（5）了解页面大小和内存实际容量对命中率的影响。
【实验要求】
（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；
（2）实现OPT算法（最优置换算法） 、LRU算法（LeastRecently） 、FIFO算法（FirstINFirstOut）的模拟；
（3）使用某种编程语言模拟页面置换算法。
【实验原理】
分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。
在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。
但应将哪个页面调出，须根据算法来确定。
通常，把选择换出页面的算法称为页面置换算法。
一个好的页面置换算法，应具有较低的页面更换频率。
从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
一、最佳置换算法OPT（Optimal）
它是由Belady于1966年提出的一种理论上的算法。
其所选择的被淘汰页面，将是以后永不使用的或许是在最长（未来）时间内不再被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是可以利用此算法来评价其它算法。
如果编写程序模拟该算法，可以提前设定页面访问次序，获知某个页面是否在未来不再被访问。
二、先进先出（FIFO）页面置换算法
这是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
三、最近最久未使用置换算法
1、LRU（LeastRecentlyUsed）置换算法的描述
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。
最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
2、LRU置换算法的硬件支持
LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。
为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：
1）寄存器
为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为
R=Rn-1Rn-2Rn-3……R2R1R0当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。
此时，定时信号将每隔一定时间（例如100ms）将寄存器右移一位。
如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
下图显示了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。
这里，把8个内存页面的序号分别定为1--8。
由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。
R7
R6
R5
R4
R3
R2
R1
R0
1
0
1
0
1
0
0
1
0
2
1
0
1
0
1
1
0
0
3
0
0
0
0
0
1
0
0
4
0
1
1
0
1
0
1
1
5
1
1
0
1
0
1
1
0
6
0
0
1
0
1
0
1
1
7
0
0
0
0
0
1
1
1
8
0
1
1
0
1
1
0
1
2）栈
可利用一个特殊的栈来保存当前使用的各个页面的页面号。
每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。
因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用的页面的页面号。
【实验步骤】
参考实验步骤如下：
（注意：
这个仅是个例子，可以参考本例，选择其他算法进行实验）
（1）现定义数据结构和全局变量。
#include
#include
#defineM4
#defineN17
#defineMyprintfprintf（"|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n"）
/*表格控制*/
typedefstructpage
{intnum;/*记录页面号*/
inttime;/*记录调入内存时间*/
}Page;/*页面逻辑结构，结构为方便算法实现设计*/
Pageb[M];/*内存单元数*/
intc[M][N];/*暂保存内存当前的状态：
缓冲区*/
intqueue[100];/*记录调入队列*/
intK;/*调入队列计数变量*/
（2）初始化内存单元、缓冲区
voidInit（Page*b,intc[M][N]）
{inti,j;
for（i=0;i{b[i].num=-1;
b[i].time=N-i-1;}
for（i=0;ifor（j=0;jc[i][j]=-1;
}
（3）取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
intGetMax（Page*b）
{inti;
intmax=-1;
inttag=0;
for（i=0;i{if（b[i].time>max）
{max=b[i].time;
tag=i;}}
returntag;
}
（4）判断页面是否已在内存中*/
intEquation（intfold,Page*b）
{inti;
for（i=0;iif（fold==b[i].num）returni;
return-1;
}
（5）LRU算法
voidLru（intfold,Page*b）
{inti;
intval;
val=Equation（fold,b）;
if（val>=0）
{b[val].time=0;
for（i=0;iif（i!
=val）b[i].time++;
}
else
{queue[++K]=fold;/*记录调入页面*/
val=GetMax（b）;
b[val].num=fold;
b[val].time=0;
for（i=0;iif（i!
=val）b[i].time++;
}}
（6）主程序
voidmain（）
{
inta[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4};
inti,j;
start:
K=-1;
Init（b,c）;
for（i=0;i{Lru（a[i],b）;
c[0][i]=a[i];
/*记录当前的内存单元中的页面*/
for（j=0;jc[j][i]=b[j].num;
}
/*结果输出*/
printf（"内存状态为：
\n"）;
Myprintf;
for（j=0;jprintf（"|%2d",a[j]）;
printf（"|\n"）;
Myprintf;
for（i=0;i{for（j=0;jif（c[i][j]==-1）printf（"|%2c",32）;
else
printf（"|%2d",c[i][j]）;
printf（"|\n"）;
}
Myprintf;
printf（"\n调入队列为:
"）;
for（i=0;iprintf（"%3d",queue[i]）;
printf（"\n缺页次数为：
%6d\n缺页率：
%16.6f",K+1,（float）（K+1）/N）;
printf（"\nAreyoucontinuing!
\ty?
"）;
if（getche（）=='y'）gotostart;
}
可以参照以上代码写出FIFO的算法。
实验三银行家算法模拟
【开发语言及实现平台或实验环境】
C++/C#
TurboC/MicrosoftVisualStudio6.0/MicrosoftVisualStudio.NET2010
【实验目的】
（1）理解利用银行家算法避免死锁的问题；
（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，并检测机算和笔算的一致性。
（3）理解和掌握安全序列、安全性算法
【实验要求】
（1）了解和理解死锁；
（2）理解利用银行家算法避免死锁的原理；
（3）使用某种编程语言模拟该算法。
【实验原理】
升级会员 