《操作系统》课程设计报告.docx
《《操作系统》课程设计报告.docx》由会员分享，可在线阅读，更多相关《《操作系统》课程设计报告.docx（22页珍藏版）》请在冰点文库上搜索。
《操作系统》课程设计报告
河海大学文天学院
《操作系统》课程设计报告
专业：
计算机科学与技术
班级：
五班
学号：
姓名：
时间：
2010/12/24
课程设计文档
实验一进程调度
一、实验目的
通过一个简单的进程调度模拟程序的实现，加深对进程调度算法，进程切换的理解。
二、实验内容
采用动态优先数的方法，编写一进程调度程序模拟程序。
模拟程序只进行相应的调度模拟操作，不需要实际程序。
三、实验流程图
四、算法思想
1、创建进程对象，成员属性有：
进程名，进程所需运行时间、进程的优先级和状态
2、使用ArrayList来存放模拟的进程（ArrayList是动态数组，不用去考虑容量问题，可以很好的解决不知道数量的进程数，同时可以不使用链表）。
3、对创建的进程进行排序，按照优先级的顺序进行相应的排序。
排序成功后进行模拟进程的运行，每运行一次进程，将该进程的优先级减少一个单位，运行时间减一个单位，依次循环，直至所有的进程的运行完成，运行时间变为0。
注意：
优先级和运行所需要的时间变为0时就不可以再减！
五、算法实现
#include
#include
#include
#include
//定义pcb结构体
typedefstructpcb{
charname[4];//进程名
intruntime;//进程要求运行时间
intpriority;//进程优先数
charstate;//进程状态R代表就绪，E代表结束
structpcb*next;
}*ProNode,Pro;
typedefstruct{
ProNodefront;
ProNoderear;
}PLinkQueue;
//初始化进程队列
voidInitPQueue（PLinkQueue*Q）
{
inti;
ProNodeP,q;
system（"cls"）;
Q->rear=Q->front=NULL;//构造一个空队列
//构造进程队列
printf（"\n请输入5个进程名、运行时间和优先数：
\n"）;
for（i=1;i<6;i++）//从键盘输入进程信息并按优先数从大到小排序
{
P=（ProNode）malloc（sizeof（Pro））;
printf（"\n*-*-*-*-*-*-*-*-*-*-*-*-*-*-进程%d-*-*-*-*-*-*-*-*-*-*-*-*-*-*\n",i）;
printf（"进程名:
"）;
scanf（"%s",P->name）;
printf（"\n运行时间:
"）;
scanf（"%d",&P->runtime）;
printf（"\n优先数:
"）;
scanf（"%d",&P->priority）;
P->state='R';
if（Q->front==NULL）//队列为空
{
Q->front=Q->rear=P;
P->next=NULL;
}
elseif（P->priority>Q->front->priority）//队列非空，新进程优先数最大，插入队首
{
P->next=Q->front;
Q->front=P;
}
else
{
q=Q->front;
while（q->next）
{
if（（q->priority>=P->priority）&&（q->next->prioritypriority））
{
P->next=q->next;//插入
q->next=P;
break;
}
q=q->next;
}
if（!
q->next）
{
Q->rear->next=P;
Q->rear=P;
P->next=NULL;
}//当前待插如进程优先数最小，插入进程尾
}
}
}//InitPQueue（PLinkQueue*Q）
//程序实现
voidDeQueue（PLinkQueue*Q）//队首进程运行完成后退出队列并释放节点
{
ProNodeP;
P=Q->front;
Q->front=P->next;
free（P）;
}//DeQueue（PLinkQueue*Q）
/*队首的进程占用CPU,运行一个固定时间段后调整队列，要求runtime=0的进程时退出队列，
否则按优先数从大到小的顺序插入至后续ready进程队列中*/
voidRun（PLinkQueue*Q）
{
ProNodeP,temp;
intt=0;
while（Q->front）//进程运行至队列空
{printf（"\n\n-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-\n"）;
printf（"时刻%d到%d,",t,t+1）;
P=Q->front;
printf（"进程%s正在运行\n",P->name）;
getchar（）;
P=Q->front;
P->runtime--;
P->priority--;
t++;
temp=Q->front;
if（P->runtime==0）
{
printf（"\n进程%s已经运行完毕，退出队列",P->name）;
P->state='E';
getchar（）;
DeQueue（Q）;
if（Q->front==NULL）
{
printf（"所有进程已经运行完毕!
"）;
getchar（）;
return;
}
}
else//使队列保持优先数递减次序,并打印就绪队列情况
{
while（temp->next）
{
if（（temp->priority>=P->priority）&&（temp->next->prioritypriority））
{
Q->front=Q->front->next;
P->next=temp->next;
temp->next=P;//插入到两进程间
break;
}
temp=temp->next;
}
if（!
temp->next）
{
Q->front=Q->front->next;
P->next=NULL;
temp->next=P;
Q->rear=P;
}//插入队列尾
}
temp=Q->front;
printf（"\n时刻%d进程运行情况:
\n",t）;//队列中进程运行状态打印
printf（"\n进程名\t要求运行时间\t\t优先数\t\t状态\n"）;
do
{
printf（"%s\t\t%d\t\t",temp->name,temp->runtime）;
printf（"%d",temp->priority）;
printf（"\t\t%c\n",temp->state）;
temp=temp->next;
}while（temp!
=NULL）;
getchar（）;
}
}//Run（PlinkQueue*Q）
voidmain（）
{
PLinkQueuePQueue;
printf（"/-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-\n"）;
printf（"**\n"）;
printf（"*动态优先数进程调度*\n"）;
printf（"**\n"）;
printf（"-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-/\n"）;
getchar（）;
InitPQueue（&PQueue）;
printf（"优先数进程调度过程如下:
\n"）;
Run（&PQueue）;
}
六、总结
这个实验主要是为了实验进程管理中的进程调度，运用的算法和整个的调度思想都是比较简单的，但是却体现了进程调度的重要性，操作系统的四大特征都是基于进程而形成的，所以我们可以从进程的角度来研究操作系统，进程调度是操作系统中一个极其重要的组成部分，进程调度算法就是为了实现进程调度，在进程调度算法中引入了最高优先权调度算法，一般经常用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可以用于实时系统中。
按照优先级的顺序进行排序是该实验的重要部分，排好了序列了才能进行其他操作，该实验加深了我们对进程调度算法和进程切换的学习，加深了对进程调度算法的熟悉和操作……
实验二存储管理
一、实验目的
存储管理的主要功能之一是合理地分配空间。
请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。
二、实验内容
虚拟存储器的工作原理以及虚拟页式存储管理中的页面置换算法
三、算法思想
1、使用随机数产生的函数，产生320个随机数，要求随机数的大小在1~100之间，在[0,319]的指令地址之间随机选取一起点m;顺序执行一条指令;在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m′;顺序执行一条指令,其地址为m′+1;在后地址[m′+2,319]中随机选取一条指令并执行;重复上述步骤,直到执行320次指令。
2、采用先进先出的算法（FIFO）；
3、最近最久未使用算法（LRU）;
四、算法实现
//test_1.cpp:
定义控制台应用程序的入口点。
//
/**************************************************************
*此程序为页面调度程序，用于模拟虚存与主存之间的页面置换
*并同时采用FIFO,LRU,OPT,LFT,NUR几种算法
*并比较在不同算法下及不同的主存页面状态下，主存的命中率的高低
**************************************************************
*/
#include"stdlib.h"
#include"stdio.h"
#include"time.h"
#defineTRUE1
#defineFALSE0
#defineINVALID-1/*页面失效符*/
#definenull0
#definetotal_instruction320/*指令流长*/
#definetotal_vp32/*虚页长*/
#defineclear_period50/*清零周期*/
typedefstruct{/*页面结构*/
intpn,pfn,counter,time;
}pl_type;
/*--pn为页面队列号,pfn为页面控制结构中的页号，counter为访问次数--*/
pl_typepl[total_vp];/*页面结构数组;建立虚存页面空间*/
/*******************************************************
*此程序有两种结构，一种是页面结构，用于页面的实际转换
*即将某一页面的实际参数作改变
*另一种是页面控制结构，用于控制页面的调度
******************************************************/
structpfc_struct{/*页面控制结构;主存中的页面调度结构*/
intpn,pfn;
structpfc_struct*next;
};
typedefstructpfc_structpfc_type;
/*--p272c语言书;;用于将定义语句structpfc_struct改成pfc_type--*/
/*--pfc[total_vp]为用户进程虚页控制结构；freepf_head闲页面头指针；
*--busypf_head 忙页面头指针；busypf_tail忙页面尾指针*/
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect,a[total_instruction];/*定义页面缺失次数diseffect和指令序列表a*/
intpage[total_instruction],offset[total_instruction];/*定义每条指令分别在哪一页page[i]以及在此页中的偏移量offset[i]*/
voidinitialize（）;
voidFIFO（）;
voidLRU（）;
voidOPT（）;
voidLFU（）;
voidNUR（）;
voidinitialize（inttotal_pf）/*初始化相关数据;total_pf用户进程的内存页面数*/
{inti;
diseffect=0;
for（i=0;i{pl[i].pn=i;
pl[i].pfn=INVALID;/*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;
pl[i].time=-1;/*页面控制结构中的访问次数为0，时间为-1*/
}
for（i=1;i{pfc[i-1].next=&pfc[i];
pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之间的链接*/
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0];/*空页面队列的头指针为pfc[0]*/
}
voidFIFO（inttotal_pf）/*FIFO（FirstInFirstOut）ALGORITHM*/
{
/*该算法中freepf_head用于指示主存页面中空闲页面的头位置,而并没有创建新的队列
*同样,busypf_head及busypf_tail也没有创建新的队列,而是用于指示主存结构中忙页面的头尾
*而且由于是纯算法,所以并没有考虑页面自己消掉的可能性,而纯粹由调度结构控制
*因此,当页面满后,只有命中不命中目标,只有当释放页面时,会暂时性地产生一个free页面
*/
inti,j;
pfc_type*p,*t;
initialize（total_pf）;/*利用子程序初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NULL;/*忙页面队列头，队列尾链接*/
for（i=0;i{
/*通过查看虚存中页面的pfn是否为INVALID来判断该页面是否在主存中
*若则应存在一个值*/
if（pl[page[i]].pfn==INVALID）/*页面失效*/
{diseffect++;/*失效次数*/
if（freepf_head==NULL）/*无空闲页面*/
{p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;/*将释放出的页面的pfn改为INVALID*/
freepf_head=busypf_head;/*释放忙页面队列中的第一个页面*/
freepf_head->next=NULL;/*因为只有一个空闲页面,所以next必为NULL*/
busypf_head=p;/*忙页面头指向下一个*/
}
p=freepf_head->next;/*按FIFO方式调新页面入内存页面*/
freepf_head->next=NULL;/*当前空闲页面将被占用,因此其next必为NULL*/
freepf_head->pn=page[i];/*这里的freepf_head指的是当前将被占用的页面*/
pl[page[i]].pfn=freepf_head->pfn;/*仅仅是存放一个值而已,用以区分页面不在主存中的INVALID*/
if（busypf_tail==NULL）
busypf_head=busypf_tail=freepf_head;/*当主存页面为空的情况下,处理尾部*/
else
{busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;/*空闲页面指向下一个*/
}
}
printf（"FIFO:
%6.4f---",1-（float）diseffect/320）;
}
voidLRU（inttotal_pf）/*LRU（LastRecentlyUsed）ALGORITHM*/
/*此处LRU算法并未用到pfc队列
*而是用是否为INVALID来判断该页面是否被载入内存
*若未被载入内存,则被载入,同时在有空闲页面的情况下将freepf_head指向下一个
*若没有空闲页面,则在pl[page[i]].pfn!
=INVALID的页中选出时间最小的,将之替换出去
*/
{intmin,minj,i,j,present_time;
initialize（total_pf）;
present_time=0;
for（i=0;i{
if（pl[page[i]].pfn==INVALID）/*页面失效*/
{diseffect++;/*失效次数*/
if（freepf_head==NULL）/*无空闲页面*/
{min=32767;
/*找出主存中时间最小的页面*/
for（j=0;j{
if（pl[j].pfn!
=INVALID&&min>pl[j].time）//在pl中的页面凡是标注有值的均是在主存中的页面！
！
{min=pl[j].time;
minj=j;
}
}
/*freepf_head=&pfc[pfc[minj].pfn];*///！
！
！
！
错误！
minj取值会大于total_pf
pl[minj].pfn=INVALID;
pl[minj].time=-1;
pl[page[i]].pfn=page[i];//为了表示命中,换入的页面的pfn值应不为INVALID
}
else//有空闲页面时,首先将新页面填入,然后freepf_head指向下一个
{
pl[page[i]].pfn=page[i];//标志此页面被载入内存
freepf_head=freepf_head->next;//freepf_head指向下一个
}
}
else
{pl[page[i]].time=present_time;/*页面有效则将命中的页面的time增大，以确保不被最先置换*/
}
present_time++;
}
printf（"LRU:
%6.4f---",1-（float）diseffect/320）;
}
voidNUR（inttotal_pf）/*NUR最近不经常使用算法ALGORITHM*/
{inti,j,dp,cont_flag,old_dp;
pfc_type*t;
initialize（total_pf）;
dp=0;
for（i=0;i{
if（pl[page[i]].pfn==INVALID）/*页面失效*/
{diseffect++;/*失效次数*/
if（freepf_head==NULL）/*无空闲页面*/
{cont_flag=TRUE;
old_dp=dp;
while（cont_flag）
if（pl[dp].counter==0&&pl[dp].pfn!
=INVALID）
cont_flag=FALSE;
else
{dp++;
if（dp==total_vp）dp=0;
if（dp==old_dp）
for（j=0;j}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter=1;
if（i%clear_period==0）
for（j=0;j}
printf（"NRU:
%6.4f",1-（float）diseffect/320）;
}
voidLFU（inttotal_pf）/*LFU（LeatFrequentlyUsed）ALGORITHM*/
{inti,j,min,minpage;
pfc_type*t;
initialize（total_pf）;
for（i=0;i{
if（pl[page[i]].pfn==INVALID）/*页面失效*/
{diseffect++;/*失效次数*/
if（freepf_head==NULL）/*无空闲页面*/
{min=32767;
for（j=0;j{if（min>pl[j].counter&&pl[j].pfn!
=INVALID）
升级会员 