操作系统课程设计六种算法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实时操作系统课程设计”。
《计算机操作系统》
学号：班级：软技姓名：张靖伟 课 程 设 计 报 告
4班
1367003270
目录实验：进程调度算法——时间片轮转算法 2 实验：银行家算法3 实验：分区分配算法——4 实验：页面置换算法——5 实验：磁盘调度算法——
BF和FF
FIFO和LRU SCAN和SSTF 1实验：进程调度算法——时间片轮转算法
1.实验设计说明
用时间片轮转算法模拟单处理机调度。
（1）建立一个进程控制块PCB来代表。PCB包括：进程名、到达时间、运行时间和进程后的状态。
进程状态分为就绪（R）和删除（C）。
（2）为每个进程任意确定一个要求运行时间和到达时间。
（3）按照进程到达的先后顺序排成一个队列。再设一个指针指向队首和队尾。（4）执行处理机调度时，开始选择对首的第一个进程运行。（5）执行： a)输出当前运行进程的名字；
b)运行时间减去时间片的大小。
（6）进程执行一次后，若该进程的剩余运行时间为零，则删除队首，并将该进程的状态置为C；若不为空，则将向后找位置插入。继续在运行队首的进程。
（7）若进程队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。
2.实验代码
/*****************时间片轮转调度算法*******************/ #include #include #include #define N 10 int time=0;bool spe=false;typedef struct pcb /*进程控制块定义*/ {
char pname[N];int runtime;/*进程名*/ /*服务时间*/ int arrivetime;/*到达时间*/ char state;/*进程状态*/ struct pcb*next;/*连接指针*/ }PCB;typedef struct back_team/*后备队列定义*/ { PCB*first,*tail;}BACK_TEAM;typedef struct pre_team/*就绪队列定义*/ { PCB*first,*tail;}PRE_TEAM;PCB*creat()/*创建PCB*/ {
char s[N];printf(“请输入进程名：n”);scanf(“%s”,s);printf(“请输入进程服务时间(/秒)：n”);int t;scanf(“%d”,&t);PCB*p=(PCB*)malloc(sizeof(PCB));strcpy(p->pname,s);p->runtime=t;printf(“请输入进程到达时间(/秒)：n”);scanf(“%d”,&t);p->arrivetime=t;p->state='R';p->next=NULL;getchar();return p;} PCB*copy(PCB*p)/*复制一个进程*/ {
} PCB*getnext(PCB*p,BACK_TEAM*head)/*得到队列中下一个进程*/ {
} void del(BACK_TEAM*head,PRE_TEAM*S)/*释放申请的空间*/ {
PCB*p=head->first->next;while(p){ free(head->first);head->first=p;PCB*s=head->first;if(!p)return NULL;if(!p)return NULL;PCB*s=(PCB*)malloc(sizeof(PCB));strcpy(s->pname,p->pname);s->next=NULL;s->arrivetime=p->arrivetime;s->runtime=p->runtime;s->state=p->state;return s;while(strcmp(s->pname,p->pname))s=s->next;return s->next;
} } p=p->next;head->first=head->tail=NULL;free(head);free(S);BACK_TEAM*creatbt(BACK_TEAM*head)/*创建后备队列*/ {
} bool recognize(PRE_TEAM*s1)/*判断运行是否结束*/ {
if(!s1||!s1->first)return false;PCB*p=creat();if(!head->first)else head->tail->next=p;head->first=p;head->tail=p;return head;if(s1->first==s1->tail)
if(s1->first->state!='C')else return false;return true;PCB*test=s1->first;while(test!=s1->tail&&(test->state!='C'))test=test->next;if(test==s1->tail)
} return true;else return false;PCB*run(PRE_TEAM*s)/*在CPU中运行*/ {
if(!s->first){
} printf(“%dt%st”,time,s->first);s->first->runtime--;time++;if(s->first->runtime
} PCB*p=s->first;s->first->state='C';printf(“%cn”,s->first->state);s->first=p->next;free(p);if(!s->first){
} goto next;s->tail=NULL;spe=false;return NULL;spe=false;return NULL;printf(“%cn”,s->first->state);next:PCB*head=s->first;
} int CREAT(PCB*HEAD,PRE_TEAM*head2,bool*test,PCB*c)/*创建就绪队列*/ {
int i=0;if(!head2->first)
if(HEAD){
} if(c){
} head2->first=head2->tail=HEAD;return 1;head2->first=c;c->next=HEAD;head2->tail=HEAD;return 1;s->first=head->next;if(!s->first){
} head->next=NULL;return head;s->tail=NULL;spe=true;if(head2->first==head2->tail){
} else {
} if(*test){
} if(c){
} head2->tail->next=c;head2->tail=c;if(head2->first->arrivetime!=time)for(i=0;ifirst->arrivetime;i++,time++);*test=false;return 1;if(c){
} if(c->arrivetime!=time){
} head2->tail->next=c;head2->tail=c;time++;return 1;if(HEAD){ head2->tail->next=HEAD;
} } head2->tail=HEAD;return 1;int main(void){
BACK_TEAM*head1=(BACK_TEAM*)malloc(sizeof(BACK_TEAM));head1->first=head1->tail=NULL;PRE_TEAM *head2=(PRE_TEAM*)malloc(sizeof(PRE_TEAM));head2->first=head2->tail=NULL;char ask;int num=0;bool test=true;do{
printf(“要创建进程吗(y/n):”);if((ask=getchar())=='y'||ask=='Y'){
} else if(ask=='n'||ask=='N')else return 1;break;head1=creatbt(head1);num++;}while(1);PCB*p=copy(head1->first);PCB*HEAD=NULL;head2->first=head2->tail=copy(head1->first);printf(“时刻t进程名t状态n”);
} while(spe||recognize(head2)){
} del(head1,head2);return 1;CREAT(HEAD,head2,&test,p);HEAD=run(head2);p=copy(getnext(p,head1));3.实验结果
和不马上运行:
当有两个进程的时候
当有多个进程的时候：
4.实验结果分析
RR算法：每次调度时，把CPU分配给队首进程，并且令其执行一个时间片，时间片的大小从几个ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便依据此信号来停止该进程的执行；并且把它送往就绪队列的队尾；然后，再把处理剂分配给就绪队列中的新队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一个给定时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内相应所有用户的请求.2实验：银行家算法
1.实验设计说明
1.该算法通过建立几个简单的二维数组Available,Max,Allocation,Need简单的模拟银行家算法和安全性算法，每个二维数组默认[][0]为A资源，[][1]为B资源，[][2]为C资源,默认有5个进程
2.程序首先要输入各个进程的三种资源的情况，包括每个进程最大的需求量，已经分配的资源量和现在还需要的资源量，以及系统现在剩余的资源量。3.程序会判断输入的信息是否在程序的规定范围内，正确才运行。
4．在执行安全算法开始时，Work∶=Available;② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true 5.从进程集合中找到一个能满足下述条件的进程： Finish［i］=false;并且 Need［i,j］≤Work［j］； 若找到，执行6，否则，执行7。
6.当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;然后继续执行5。
7.如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
2.实验代码
#include int Available[3],Max[5][3],Allocation[5][3],Need[5][3];bool Safe(int p){ int Work[3]={Available[0],Available[1],Available[2]};int Finish[5]={0,0,0,0,0};int i=0,m,num=0;if(Need[p][0]||Need[p][1]||Need[p][2])
return false;printf(“p%d可以运行n”,p);Work[0]+=Allocation[p][0];Work[1]+=Allocation[p][1];Work[2]+=Allocation[p][2];Finish[p]=1;while(num
if(!Finish[i]&&(Need[i][0]
{
printf(“p%d可以运行n”,i);
Work[0]+=Allocation[i][0];
Work[1]+=Allocation[i][1];
Work[2]+=Allocation[i][2];
Finish[i]=1;
}
num++;
i=(i+1)%5;
if(i==p)
i++;} for(m=0;m
if(Finish[m]==0)
break;if(m==5)
return true;else {
printf(“系统处于不安全状态!n”);
return false;} } void Banker(int p,int i,int j,int k){ int able[3]={Available[0],Available[1],Available[2]};int need[3]={Need[p][0],Need[p][1],Need[p][2]};int allocation[3]={Allocation[p][0],Allocation[p][1],Allocation[p][2]};if(i
if(i
{
Available[0]-=i;
Available[1]-=j;
Available[2]-=k;
Allocation[p][0]+=i;
Allocation[p][1]+=j;
Allocation[p][2]+=k;
Need[p][0]-=i;
Need[p][1]-=j;
Need[p][2]-=k;
if(!Safe(p))
{
Available[0]=able[0],Available[1]=able[1],Available[2]=able[2];
Need[p][0]=need[0],Need[p][1]=need[1],Need[p][2]=need[2];
Allocation[p][0]=allocation[0],Allocation[p][1]=allocation[1],Allocation[p][2]=allocation[2];
printf(“系统可能发生死锁!n”);
}
}
else
printf(“等待!系统资源不足!n”);else
printf(“错误!申请的资源错误!n”);} int main(void){ int i,j,k=0,p;printf(“请输入进程的三种资源的情况max{a,b,c} allocation{a,b,c} need{a,b,c}:n”);for(i=0;i
for(j=0;j
scanf(“%d”,&Max[i][j]);
for(j=0;j
scanf(“%d”,&Allocation[i][j]);
for(j=0;j
scanf(“%d”,&Need[i][j]);} printf(“请输入Available{a,b,c}情况:”);for(i=0;i
scanf(“%d”,&Available[i]);printf(“MaxtAllotNeedtAvain”);for(i=0;i
for(j=0;j
printf(“%d ”,Max[i][j]);
printf(“t”);
for(j=0;j
printf(“%d ”,Allocation[i][j]);
printf(“t”);
for(j=0;j
printf(“%d ”,Need[i][j]);
printf(“t”);
if(k!=4)
printf(“n”);
k++;} for(i=0;i:“);scanf(”%d %d %d %d“,&p,&i,&j,&k);if(p>=0&&p
4.实验结果分析
这个实验只是简单的演示了进程申请资源之后的进程运行的其中一个运行序列，因为这个算法课本上已经有详细的解说，所以这个程序并没有把算法的过程展现出来，只展现了进程的运行序列结果，另外，如果申请错误的话程序会有不同的结果
有时会发生死锁实验：分区分配算法——BF和FF 1.实验设计说明
1.这个算法模拟的是对内存空间的管理，这个程序用了一个简单的二维数组模拟分区表。2.程序首先要输入固定的五个分区的大小和始址，其次要输入作业的大小和实现的算法，由于这个程序把FF和BF放到一个程序中，便于比较两个算法。
首次适应算法FF(First Fit)把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表 最佳适应算法BF（Best Fit）
首先把分区表按空间大小从小到大排序。然后把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表
2.实验代码 #include int table[5][3];void FirstFit(int job[3],int ta[5][3]){
int i,j;for(j=0;j
for(i=0;i
if(ta[i][1]>=job[j]){
} ta[i][1]-=job[j];ta[i][2]+=job[j];break;if(i==5)printf(”内存不足!请等待!n“);
} printf(”空闲区t大小t始址n“);for(j=0;j
} for(i=0;i
int j1,temp1,temp2,temp3,i,j;for(j1=0;j1
for(i=0;i
for(j=0;j
if(table[j][1]>table[j+1][1]){ temp1=table[j][0];temp2=table[j][1];temp3=table[j][2];
table[j][0]=table[j+1][0];table[j][1]=table[j+1][1];table[j][2]=table[j+1][2];
}
table[j+1][0]=temp1;table[j+1][1]=temp2;table[j+1][2]=temp3;
} if(i==5)printf(”内存不足!请等待!n“);printf(”空闲区t大小t始址n“);for(j=0;j
} for(i=0;i
} for(i=0;i
if(table[i][1]>=job[j1]){
} table[i][1]-=job[j1];table[i][2]+=job[j1];break;printf(”n“);void main(){
int table1[5][3],job[3],j,i;printf(”请输入5个空分区的大小和始址：“);for(i=0;i
} for(j=0;j
} printf(”请输入3个要运行作业的大小：“);for(i=0;i
} scanf(”%d“,&table[i][j]);table1[i][j]=table[i][j];printf(”n“);printf(”请输入要实现的算法1(FF)2(BF):“);
} char c;scanf(”%d“,&i);getchar();if(i==1){
} else
if(i==2){
} BestFit(job);printf(”还要实现FF吗(y/n)“);if((c=getchar())=='y')FirstFit(job,table1);FirstFit(job,table1);printf(”还要实现BF吗(y/n)“);if((c=getchar())=='y')BestFit(job);3.实验结果
4.实验结果分析
首先输入分区表的分区情况，然后输入运行作业的大小，选择要实现的算法。第一个作业是96，所以找到第四个分区，第四个分区变为122，316，接着到第二个作业20，然后把第一个分区分给第二个作业，则第一个分区信息变为122，316，到第三个作业时，由于内存表中没有比第三个请求的分区还大的分区，所以会提示内存不足；
然后到BF算法，因为是按空间大小排序的，所以第一个作业96被分配给了已经排好序的内存为96的第五个分区，第二个作业被分配给大小为36的分区，第三个作业被分配给内存大小为218的分区，然后又对剩余空间再次排队，用来给下一批作业分配。实验：页面置换算法——FIFO和LRU 1实验设计说明
程序设置了两个结构体,freeBlock和jobQueue,其中freeBlock代表物理块,初次创建物理块时,物理块的计时器time=0,还有代表作业的index=-1;物理块有添加和删除的功能，每一次添加或删除都要初始化物理块。并且可以重复添加和删除，这样可以很好的测试算法的性能。2.算法设计的思想是：进入物理块时间越长的则物理块的计时器数值越大，如果物理块中有要访问的页面，则那个含页面的物理块的计数器变成1；并且物理块要满才会发生置换，于是设置了物理块计数器Time；
2.实验代码 #include #include typedef struct freeBlock { int index,time;struct freeBlock*next;}freeBlock;typedef struct jobQueue { int index;struct jobQueue*next;}jobQueue;jobQueue*creat(jobQueue*head,int num){
jobQueue*job=(jobQueue*)malloc(sizeof(jobQueue));job->index=num;job->next=NULL;if(!head){
jobQueue*j=head;while(j->next)j=j->next;j->next=job;head=job;else
} } return head;freeBlock*creat(freeBlock*head){
} freeBlock*inse(freeBlock*head){
} freeBlock*dele(freeBlock*head){ freeBlock*test=head;while(test){
} freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=head;head=free;return head;test->index=-1;test->time=0;test=test->next;freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=NULL;if(head)free->next=head;head=free;return head;
} freeBlock*test=head;while(test){
} freeBlock*f=head;head=f->next;free(f);return head;test->index=-1;test->time=0;test=test->next;bool check(freeBlock*free,int j){
} void LRU(freeBlock*free,jobQueue*job){
int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){ freeBlock*f=free;while(f){
} return false;if(f->index==j)return true;f=f->next;
} size++;ftest=ftest->next;printf(”LRU置换页面为：“);while(jtest){
ftest=free;while(ftest){
} ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ if(ftest->index==jtest->index){
} ftest->time++;if(Timetime)Time=ftest->time;time++;ftest=ftest->next;ftest->index=jtest->index;ftest->time++;time=0;break;ftest->time=0;if(ftest->index==-1)
}
}
}
} time=0;Time=0;break;if(ftest->time==Time){
} ftest=ftest->next;printf(”%d “,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(”n“);void FIFU(freeBlock*free,jobQueue*job){
int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){
} size++;ftest=ftest->next;
printf(”FIFU置换页面为：“);while(jtest){
ftest=free;while(ftest){
} ftest=free;while((time==size)&&ftest){
if(check(free,jtest->index)){
} if(ftest->time==Time)time=0;Time=0;break;if(ftest->index==-1){
} ftest->time++;if(Timetime)Time=ftest->time;time++;ftest=ftest->next;ftest->index=jtest->index;ftest->time++;time=0;break;
}
}
} {
} ftest=ftest->next;printf(”%d “,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(”n“);void main(){
int num,ch,p;freeBlock*block=NULL;jobQueue*job=NULL;printf(”请输入物理块数目：“);scanf(”%d“,&p);for(int i=0;i
} job=creat(job,ch);FIFU(block,job);LRU(block,job);while(true){
printf(”增加物理块（1）减少物理块（2）,否则按任意键scanf(“%d”,&num);if(num==1){
} else if(num==2){
printf(“要减少几块：”);scanf(“%d”,&ch);if(ch>=p){
} for(i=0;i
}
}
} FIFU(block,job);LRU(block,job);else ；break;3.实验结果
4.实验结果分析
程序开始要输入物理块数目和作业个数,然后再输入作业.在测试后可以随意添加或删除物理块来测试算法的性能。实验：磁盘调度算法——SCAN和SSTF 1.实验设计说明
算法定义了一个双向链表，利用双向链表可以很好的进行方向的转换，且双向链表的中有代表磁盘号的标识符index；两个算法均采用访问完一个磁盘序列时删除该序列，其中scan算法实现时有点麻烦，首先要找到当前磁盘号序列的Max最大值和最小值Min及指向他们的指针pmax，pmin，另外还要找到当前磁头的相邻的两个访问序列信息psmax，psmin；还有一个重要的标志，那就是访问的方向test；当遇到最大值或最小值时，便会反置test的值，也就是访问的方向
2.实验代码 #include #include #include typedef struct memory { int index;struct memory*left,*right;}memory;memory*creat(){
printf(“请输入磁道队列以-1结束！n”);int ch;memory*head=NULL,*tail,*p;scanf(“%d”,&ch);while(ch!=-1){
p=(memory*)malloc(sizeof(memory));p->index=ch;p->left=p->right=NULL;
}
} if(!head)head=p;else {
} tail=p;scanf(“%d”,&ch);tail->right=p;p->left=tail;return head;void SSTF(memory*head,int index){
int index1=index,num;memory*p1=head,*p,*p2=NULL;while(true){
num=abs(p1->index-index1);p=p1;while(p){
} if((abs(p->index-index1))
} p=p->right;num=abs(p->index-index1);if(p!=p1)p2=p;p=p1->right;if(p2){
} else { printf(“%d ”,p1->index);index1=p2->index;printf(“%d ”,p2->index);p2->left->right=p2->right;if(p2->right)p2->right->left=p2->left;free(p2);p2=NULL;
}
}
} index1=p1->index;if(!p){
} else {
} p=p1;p1=p1->right;free(p);continue;free(p1);break;void SCAN(memory*head,int index){
int index1=index,num,test,max=0,min=199,Max,Min;printf(“请输入磁头查询方向!n”);scanf(“%d”,&test);memory*p1=head,*p,*p2=NULL,*pmax,*pmin,*psmax=NULL,*psmin=NULL;
while(p1){
} p1=head;while(p1){ if(!test){ if(!test){
} else {
} p1=p1->right;pmin=p1;if(p1->indexindex;pmax=p1;if(p1->index>=max)Max=max=p1->index;
}
} pmin=p1;if(p1->indexindex;
else {
} p1=p1->right;pmax=p1;if(p1->index>=max)Max=max=p1->index;p1=head;while(true){
num=abs(p1->index-index1);p=p1;while(p){
if(!test){ if(p->index>=index1&&p->index
}
}
if((abs(p->index-index1))
}
psmin=p;
num=abs(p->index-index1);if(p->left&&p->right)p2=p;else {
} p=p->right;if(p->indexindex>=min)
if(abs(p->index-index1)
}
psmax=p;
num=abs(p->index-index1);if(p->left&&p->right)p2=p;if(p2)
{
if(!test){
} else {
index1=psmax->index;p=psmax;if(index1==Min){
} test=0;Max=Min=-1;p1=pmin;index1=psmin->index;p=psmin;if(index1==Max){
} test=1;Min=Max=-1;p1=pmax;
} printf(“%d ”,index1);if(!test){
} else { if(psmax)if(psmin){
} else {
} psmax->right->left=psmax->left;if(psmax->left)
psmax->left->right=psmax->right;psmin->left->right=psmin->right;if(psmin->right)
psmin->right->left=psmin->left;free(psmin);free(psmax);
}
} {
} else {
} psmin->right->left=psmin->left;if(psmin->left)
psmin->left->right=psmin->right;psmax->left->right=psmax->right;if(psmax->right)
psmax->right->left=psmax->left;free(psmax);free(psmin);else {
if(!test){
if(p1->index==Max){ test=1;
} } Min=Max=-1;else {
} if(psmax){
} else {
} printf(“%d ”,index1);index1=psmin->index;p=psmin;index1=psmax->index;p=psmax;if(p1->index==Min){
} test=0;Max=Min=-1;
}
}
} if(p->left&&!p->right){
} else if(p->right&&!p->left){
} else if(!p->right&&!p->left){
} free(p);free(p);break;p1=p->right;p1->left=NULL;p1=p->left;p1->right=NULL;p2=psmax=psmin=NULL;void main(){
int p,t;memory*head=creat();printf(“请输入磁头当前的位置(0-199)”);scanf(“%d”,&p);printf(“要进行的算法：”);scanf(“%d”,&t);if(!t)SCAN(head,p);else SSTF(head,p);} 3.实验结果
4.实验结果分析
输入要访问的磁盘号，然后选择要实现的算法就可以看到结果，当选0（正向）的时候由于当前的磁头在143处，所以要访问的磁盘号就必须大于143，当最大的磁盘号访问完时，就转向小于143的磁盘开始由大向小访问，选1的话则相反。最短寻道时间算法是从整个队列中选择距离磁头最近的访问，算法的实现运用了绝对值的概念
沈阳理工大学课程设计专用纸 Noi目 录 1 课程设计目的及要求……………………………………………………错误！未定义书签。 2 相关知识……………………………………......
1.实验题目:磁盘调度算法。 建立相应的数据结构；在屏幕上显示磁盘请求的服务状况；将一批磁盘请求的情况存磁盘文件，以后可以读出并重放； 计算磁头移动的总距离及平均移动距离； 支......
《计算机操作系统》课 程 设 计 报 告 题 目： 银行家算法班 级： XXXXXXXXXXXXXXXX 姓 名： XXM 学 号： XXXXXXXXXXXX 指导老师: XXXXXXXXXXXXXX 设计时间: XXXXXXXXXXXXXXX......
操作系统课程设计（银行家算法的模拟实现）一、设计目的 1、进一步了解进程的并发执行。2、加强对进程死锁的理解。3、用银行家算法完成死锁检测。二、设计内容给出进程需求矩阵......
操作系统课程设计注意事项：0.请每位同学必须按时提交课程设计报告（包括电子版和纸质版），算入期末成绩1.在三个题目中选择一个2.如果选择题目（一）进程调度算法，要求实现其中2个以上（......
