中南大学操作系统实验报告.docx
《中南大学操作系统实验报告.docx》由会员分享,可在线阅读,更多相关《中南大学操作系统实验报告.docx(32页珍藏版)》请在冰点文库上搜索。
中南大学操作系统实验报告
中南大学
操作系统实验报告
姓名:
学院:
班级:
学号:
2015年6月10号
1.经典同步,并发算法
实验目的:
(1)通过编写程序实现进程同步和互斥,掌握有关进程(线程)同步与互斥的原理,以及解决进程(线程)同步和互斥的算法,从而进一步巩固进程(线程)同步和互斥等有关的内容。
(2)了解Windows7中多线程的并发执行机制,线程间的同步和互斥。
(3)学习使用Windows7中基本的同步对象,掌握相应的API函数。
(4)掌握进程和线程的概念,进程(线程)的控制原语或系统调用的使用。
实验内容:
在Window7操作系统下,使用java等编程语言,采用进程(线程)同步和互斥的技术编写程序实现生产者-消费者问题。
实验环境:
Computer,用eclipse编译环境。
Win7系统。
实验步骤:
(含原理图、流程图、关键代码,或实验过程中的记录、数据等)
生产者进程(进程由多个线程组成)生产信息,例如它可以是计算进程。
消费者进程使用信息,它可以是输出打印进程。
由于生产者和消费者彼此独立,且运行速度不确定,所以很可能出现生产者已产生了信息而消费者却没有来得及接受信息这种情况。
为此,需要引入由一个或者若干个存储单元组成的临时存储区,以便存放生产者所产生的信息,平滑进程间由于速度不确定所带来的问题。
这个临时存储区叫做缓冲区,通常用一维数组来表示。
由一个或若干个存储单元组成的缓冲区叫作“有穷缓冲区”。
下面我们来分析一下有穷缓冲的生产者和消费者的例子。
原理图
假设有多个生产者和多个消费者,它们共享一个具有n个存储单元的有穷缓冲区Buffer(0……n-1),这是一个环形队列。
其队尾指针Rear指向当前信息应存放的位置(Buffer[Rear]),队首指针Front指向当前取出信息的位置(Buffer[front])。
生产者进程总是把信息存放在Buffer[Rear]中,消费者进程则总是从Buffer[Rear]中取出信息。
如果想使生产者进程和消费者进程协调合作,则必须使它们。
遵循如下规则:
1)只要缓冲区有存储单元,生产者都可往其中存放信息;当缓冲区已满时,若任意生产者提出写要求,则都必须等待;
2)只要缓冲区中有消息可取,消费者都可从缓冲区中取出消息;当缓冲区为空时,若任意消费者想取出信息,则必须等待;
3)生产者们和消费者们不能同时读、写缓冲区。
(很重要)
程序代码:
publicclassProducerConsumer{
publicstaticvoidmain(String[]args){
SyncStackss=newSyncStack();
Producerp=newProducer(ss);
Consumerc=newConsumer(ss);
newThread(p).start();
newThread(p).start();
newThread(p).start();
newThread(c).start();
}
}
classJSY{
intid;
WoTou(intid){
this.id=id;
}
publicStringtoString(){
return"JSY:
"+id;
}
}
classSyncStack{
intindex=0;
WoTou[]arrWT=newWoTou[6];
publicsynchronizedvoidpush(JSYwt){
while(index==arrWT.length){
try{
this.wait();
}catch(InterruptedExceptione){
e.printStackTrace();
}
}
this.notifyAll();
arrWT[index]=wt;
index++;
}
publicsynchronizedJSYpop(){
while(index==0){
try{
this.wait();
}catch(InterruptedExceptione){
e.printStackTrace();
}
}
this.notifyAll();
index--;
returnarrWT[index];
}
}
classProducerimplementsRunnable{
SyncStackss=null;
Producer(SyncStackss){
this.ss=ss;
}
publicvoidrun(){
for(inti=0;i<20;i++){
JSYwt=newWoTou(i);
ss.push(wt);
System.out.println("生产了:
"+wt);
try{
Thread.sleep((int)(Math.random()*200));
}catch(InterruptedExceptione){
e.printStackTrace();
}
}
}
}
classConsumerimplementsRunnable{
SyncStackss=null;
Consumer(SyncStackss){
this.ss=ss;
}
publicvoidrun(){
for(inti=0;i<20;i++){
JSYwt=ss.pop();
System.out.println("消费了:
"+wt);
try{
Thread.sleep((int)(Math.random()*1000));
}catch(InterruptedExceptione){
e.printStackTrace();
}
}
}
}
结果:
(随机的)
生产了:
JSY:
0
生产了:
JSY:
0
消费了:
JSY:
0
生产了:
JSY:
1
生产了:
JSY:
1
生产了:
JSY:
1
生产了:
JSY:
2
生产了:
JSY:
3
消费了:
JSY:
2
消费了:
JSY:
3
生产了:
JSY:
4
消费了:
JSY:
4
生产了:
JSY:
5
消费了:
JSY:
5
生产了:
JSY:
6
消费了:
JSY:
6
生产了:
JSY:
2
消费了:
JSY:
2
生产了:
JSY:
3
消费了:
JSY:
3
生产了:
JSY:
4
消费了:
JSY:
4
生产了:
JSY:
5
消费了:
JSY:
5
生产了:
JSY:
6
消费了:
JSY:
6
实验心得:
经过不断的调试,程序能正确运行。
对线程的同步与互斥技术有了比较深刻的了解,生产者消费者问题是研究多线程程序时绕不开的问题,它的描述是有一块生产者和消费者共享的有界缓冲区,生产者往缓冲区放入产品,消费者从缓冲区取走产品,这个过程可以无休止的执行,不能因缓冲区满生产者放不进产品而终止,也不能因缓冲区空消费者无产品可取而终止。
解决生产者消费者问题的方法有两种,一种是采用某种机制保持生产者和消费者之间的同步,一种是在生产者和消费者之间建立一个管道。
前一种有较高的效率并且可控制性较好,比较常用,后一种由于管道缓冲区不易控制及被传输数据对象不易封装等原因,比较少用。
此实验以后我对操作系统的理解越来越深了。
学到了好多知识。
2.银行家算法:
实验目的:
1.通过实现银行家算法,理解操作系统进程管理,分配原理,达到深入理解操作系统的各项功能。
2.熟练银行家算法。
3.理解并能解释银行家算法。
实验内容:
我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全,银行家规定:
(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2)顾客可以分期贷款,但贷款的总数不能超过最大需求量;
(3)当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4)当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。
当进程在执行中继续申请资源时,先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。
若超过则拒绝分配资源,若能满足则按当前的申请量分配资源,否则也要推迟分配。
实验环境:
Computer,用Microsoftvisualc++编译环境。
Win7系统。
实验步骤:
进程i发出请求资源申请,
(1)如果Request[j]<=need[i,j],转向步骤
(2),否则认为出错,因为他所需要的资源数已经超过它所宣布的最大值。
(2)如果:
Requesti[j]<=available[i,j],转向步骤(3),否则表示尚无足够资源,进程i需等待。
(3)若以上两个条件都满足,则系统试探着将资源分配给申请的进程,并修改下面数据结构中的数值:
Available[i,j]=Available[i,j]-Request[j];
Allocation[i][j]=Allocation[i][j]+Request[j];
need[i][j]=need[i][j]-Request[j];
(4)试分配后,执行安全性检查,调用check()函数检查此次资源分配后系统是否处于安全状态。
若安全,才正式将资源分配给进程;否则本次试探分配作废,恢复原来的资源分配状态,让该进程等待。
(5)用do{…}while循环语句实现输入字符y/n判断是否继续进行资源申请。
(二)安全性检查算法
(1)设置两个向量:
工作向量Work,它表示系统可提供给进程继续运行所需的各类资源数目,在执行安全性算法开始时,Work=Available。
工作向量Finish,它表示系统是否有足够的资源分配给进程,使之运行完成。
开始时先做Finish[i]=false;当有足够的资源分配给进程时,再令Finish[i]=true。
(2)在进程中查找符合以下条件的进程:
条件1:
Finish[i]=false;
条件2:
need[i][j]<=Work[j]
若找到,则执行步骤(3)否则,执行步骤(4)
(3)当进程获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]=Work[j]+Allocation[i][j];
Finish[i]=true;
gotostep
(2);
(4)如果所有的Finish[i]=true都满足,则表示系统处于安全状态,否则,处于不安全状态。
程序源代码:
#include
#include
#include
#definem50
intno1;//进程数
intno2;//资源数
intr;
intallocation[m][m],need[m][m],available[m],max[m][m];
charname1[m],name2[m];//定义全局变量
voidmain()
{
voidcheck();
voidprint();
inti,j,p=0,q=0;
charc;
intrequest[m],allocation1[m][m],need1[m][m],available1[m];
printf("**********************************************\n");
printf("*银行家算法的设计与实现*\n");
printf("**********************************************\n");
printf("请输入进程总数:
\n");
scanf("%d",&no1);
printf("请输入资源种类数:
\n");
scanf("%d",&no2);
printf("请输入Max矩阵:
\n");
for(i=0;ifor(j=0;jscanf("%d",&max[i][j]);//输入已知进程最大资源需求量
printf("请输入Allocation矩阵:
\n");
for(i=0;ifor(j=0;jscanf("%d",&allocation[i][j]);//输入已知的进程已分配的资源数
for(i=0;ifor(j=0;jneed[i][j]=max[i][j]-allocation[i][j];//根据输入的两个数组计算出need矩阵的值
printf("请输入Available矩阵\n");
for(i=0;iscanf("%d",&available[i]);//输入已知的可用资源数
print();//输出已知条件
check();//检测T0时刻已知条件的安全状态
if(r==1)//如果安全则执行以下代码
{
do{
q=0;
p=0;
printf("\n请输入请求资源的进程号(0~4):
\n");
for(j=0;j<=10;j++)
{
scanf("%d",&i);
if(i>=no1)
{
printf("输入错误,请重新输入:
\n");
continue;
}
elsebreak;
}
printf("\n请输入该进程所请求的资源数request[j]:
\n");
for(j=0;jscanf("%d",&request[j]);
for(j=0;jif(request[j]>need[i][j])p=1;
//判断请求是否超过该进程所需要的资源数
if(p)
printf("请求资源超过该进程资源需求量,请求失败!
\n");
else
{
for(j=0;jif(request[j]>available[j])q=1;
//判断请求是否超过可用资源数
if(q)
printf("没有做够的资源分配,请求失败!
\n");
else//请求满足条件
{
for(j=0;j{
available1[j]=available[j];
allocation1[i][j]=allocation[i][j];
need1[i][j]=need[i][j];
//保存原已分配的资源数,仍需要的资源数和可用的资源数
available[j]=available[j]-request[j];
allocation[i][j]+=request[j];
need[i][j]=need[i][j]-request[j];
//系统尝试把资源分配给请求的进程
}
print();
check();//检测分配后的安全性
if(r==0)//如果分配后系统不安全
{
for(j=0;j{
available[j]=available1[j];
allocation[i][j]=allocation1[i][j];
need[i][j]=need1[i][j];
//还原已分配的资源数,仍需要的资源数和可用的资源数
}
printf("返回分配前资源数\n");
print();
}
}
}printf("\n你还要继续分配吗?
YorN?
\n");
//判断是否继续进行资源分配
c=getche();
}while(c=='y'||c=='Y');
}
}
voidcheck()//安全算法函数
{
intk,f,v=0,i,j;
intwork[m],a[m];
boolfinish[m];
r=1;
for(i=0;ifinish[i]=false;//初始化进程均没得到足够资源数并完成
for(i=0;iwork[i]=available[i];//work[i]表示可提供进程继续运行的各类资源数
k=no1;
do{
for(i=0;i{
if(finish[i]==false)
{
f=1;
for(j=0;jif(need[i][j]>work[j])
f=0;
if(f==1)//找到还没有完成且需求数小于可提供进程继续运行的资源数的进程
{
finish[i]=true;
a[v++]=i;//记录安全序列号
for(j=0;jwork[j]+=allocation[i][j];//释放该进程已分配的资源
}
}
}
k--;//每完成一个进程分配,未完成的进程数就减1
}while(k>0);
f=1;
for(i=0;i{
if(finish[i]==false)
{
f=0;
break;
}
}
if(f==0)//若有进程没完成,则为不安全状态
{
printf("系统处在不安全状态!
");
r=0;
}
else
{
printf("\n系统当前为安全状态,安全序列为:
\n");
for(i=0;iprintf("p%d",a[i]);//输出安全序列
}
}
voidprint()//输出函数
{
inti,j;
printf("\n");
printf("*************此时刻资源分配情况*********************\n");
printf("进程名/号|Max|Allocation|Need|\n");
for(i=0;i{
printf("p%d/%d",i,i);
for(j=0;j{printf("%d",max[i][j]);}
for(j=0;j{printf("%d",allocation[i][j]);}
for(j=0;j{printf("%d",need[i][j]);}
printf("\n");
}
printf("\n");
printf("各类资源可利用的资源数为:
");
for(j=0;j{printf("%d",available[j]);}
printf("\n");
}
实验心得:
本次实验不仅让我对银行家算法有了更深入的理解,并且还让我的编程能力得到了较大提高,希望能有更多这样的机会,借此较好的锻炼自己,从而更好的掌握和运用自己的专业知识,提高能力水平。
本次实验相对于c基础并不好的我有一定的难度,所以我在程序方面所做的较少。
而对银行家算法了解的比较透彻,在程序设计的原理和流程图方面做的工作较多,本次实验我学到的东西好多,也知道自己在很多方面的不足,
这实验让我更深入的了解操作系统方面的知识。
对它有了不少的认识。
我会继续努力的!
运行结果:
3.页面置换算法:
一、实验目的
1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。
2.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想,并至少用三种算法来模拟实现。
3.通过对几种置换算法页面的比较,来对比他们的优缺点,并通过比较更换频率来对比它们的效率。
二、实验内容:
设计一个虚拟存储区和内存工作区,并使用下述算法来模拟实现页面的置换:
1.先进先出的算法(FIFO)
2.最近最久未使用算法(LRU)
3.最佳置换算法(OPT)
三、实验分析
在进程运行过程中,若其所访问的页面不存在内存而需要把它们调入内存,但内存已无空闲时,为了保证该进程能够正常运行,系统必须从内存中调出一页程序或数据送磁盘的对换区中。
但应调出哪个页面,需根据一定的算法来确定,算法的好坏,直接影响到系统的性能。
一个好的页面置换算法,应该有较低的页面更换频率。
假设分给一作业的物理块数为3,页面数为20个。
页面号为(20个):
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
1.先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单,只需把一个进程已调入内存的页面,按照先后次序连接成一个队列,并设置一个替换指针,使它总指向最老的页面。
2.最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则,是根据页面调入内存后的使用情况来进行决策的。
该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进
行淘汰。
3.最佳(OPT)置换算法的思路
其所选择的被淘汰的页面,奖是以后不使用的,或者是在未来时间内不再被访问的页面,采用最佳算法,通常可保证获得最低的缺页率。
4.数据结构
structpageInfor
{
intcontent;//页面号
inttimer;//被访问标记
};
classPRA