操作系统课程设计六种算法.doc

操作系统课程设计六种算法

59
2020年4月19日
文档仅供参考，不当之处，请联系改正。
《计算机操作系统》

课
程
设
计
报
告

学号：
班级：软技4班
姓名：张靖伟

目 录

1 实验：进程调度算法——时间片轮转算法
2 实验：银行家算法
3 实验：分区分配算法——BF和FF
4 实验：页面置换算法——FIFO和LRU
5 实验：磁盘调度算法——SCAN和SSTF

1实验：进程调度算法——时间片轮转算法
1.实验设计说明
用时间片轮转算法模拟单处理机调度。
（1） 建立一个进程控制块PCB来代表。PCB包括：进程名、到达时间、运行时间和进程后的状态。
进程状态分为就绪（R）和删除（C）。
（2） 为每个进程任意确定一个要求运行时间和到达时间。
（3） 按照进程到达的先后顺序排成一个队列。再设一个指针指向队首和队尾。
（4） 执行处理机调度时，开始选择对首的第一个进程运行。
（5） 执行： a)输出当前运行进程的名字；
b)运行时间减去时间片的大小。
（6） 进程执行一次后，若该进程的剩余运行时间为零，则删除队首，并将该进程的状态置为C；若不为空，则将向后找位置插入。继续在运行队首的进程。
（7） 若进程队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。
2.实验代码
/*****************时间片轮转调度算法*******************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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)/*复制一个进程*/
{
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;
}
PCB*getnext(PCB*p,BACK_TEAM*head)/*得到队列中下一个进程*/
{
PCB*s=head->first;
if(!p)
return NULL;
while(strcmp(s->pname,p->pname))
s=s->next;
return s->next;
}
void del(BACK_TEAM*head,PRE_TEAM*S)/*释放申请的空间*/
{
PCB*p=head->first->next;
while(p)
{
free(head->first);
head->first=p;
p=p->next;
}
head->first=head->tail=NULL;
free(head);
free(S);
}
BACK_TEAM*creatbt(BACK_TEAM*head)/*创立后备队列*/
{
PCB*p=creat();
if(!head->first)
head->first=p;
else
head->tail->next=p;
head->tail=p;
return head;
}
bool recognize(PRE_TEAM*s1)/*判断运行是否结束*/
{
if(!s1||!s1->first)
return false;
if(s1->first==s1->tail)
if(s1->first->state!='C')
return true;
else
return false;
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)
{
spe=false;
return NULL;
}
printf("%d\t%s\t",time,s->first);
s->first->runtime--;
time++;
if(s->first->runtime<=0)
{
PCB*p=s->first;
s->first->state='C';
printf("%c\n",s->first->state);
s->first=p->next;
free(p);
if(!s->first)
{
s->tail=NULL;
spe=false;
return NULL;
}
goto next;
}
printf("%c\n",s->first->state);
next:PCB*head=s->first;
s->first=head->next;
if(!s->first)
{
s->tail=NULL;
spe=true;
}
head->next=NULL;
return head;
}
int CREAT(PCB*HEAD,PRE_TEAM*head2,bool*test,PCB*c)/*创立就绪队列*/
{
int i=0;
if(!head2->first)
if(HEAD)
{
if(c)
{
head2->first=c;
c->next=HEAD;
head2->tail=HEAD;
return 1;
}
head2->first=head2->tail=HEAD;
return 1;
}
if(head2->first==head2->tail)
{
if(*test)
{
if(head2->first->arrivetime!=time)
for(i=0;i<head2->first->arrivetime;i++,time++);
*test=false;
return 1;
}
if(c)
{
head2->tail->next=c;
head2->tail=c;
}
}
else
{
if(c)
{
if(c->arrivetime!=time)
{
time++;
return 1;
}
head2->tail->next=c;
head2->tail=c;
}
}
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')
{
head1=creatbt(head1);
num++;
}
else if(ask=='n'||ask=='N')
break;
else
return 1;
}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))
{
CREAT(HEAD,head2,&test,p);
HEAD=run(head2);
p=copy(getnext(p,head1));
}
del(head1,head2);
return 1;
}
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 <stdio.h>
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<=25)
{
if(!Finish[i]&&(Need[i][0]<=Work[0])&&(Need[i][1]<=Work[1])&&(Need[i][2]<=Work[2]))
{
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<5;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<=Need[p][0]&&j<=Need[p][1]&&k<=Need[p][2])
if(i<=Available[0]&&j<=Available[1]&&k<=Available[2])
{
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<5;i++)
{
for(j=0;j<3;j++)
scanf("%d",&Max[i][j]);
for(j=0;j<3;j++)
scanf("%d",&Allocation[i][j]);
for(j=0;j<3;j++)
scanf("%d",&Need[i][j]);
}
printf("请输入Available{a,b,c}情况:");
for(i=0;i<3;i++)
scanf("%d",&Available[i]);
printf("Max\tAllo\tNeed\tAvai\n");
for(i=0;i<5;i++)
{
for(j=0;j<3;j++)
printf("%d ",Max[i][j]);
printf("\t");
for(j=0;j<3;j++)
printf("%d ",Allocation[i][j]);
printf("\t");
for(j=0;j<3;j++)
printf("%d ",Need[i][j]);
printf("\t");
if(k!=4)
printf("\n");
k++;
}
for(i=0;i<3;i++)
printf("%d ",Available[i]);
printf("\n请输入要申请的进程和资源<0~4><A B C>:");
scanf("%d %d %d %d",&p,&i,&j,&k);
if(p>=0&&p<=4)
Banker(p,i,j,k);
else
printf("没有此进程!");
return 1; }
3.实验结果

4.实验结果分析
这个实验只是简单的演示了进程申请资源之后的进程运行的其中一个运行序列，因为这个算法课本上已经有详细的解说，因此这个程序并没有把算法的过程展现出来，只展现了进程的运行序列结果，另外，如果申请错误的话程序会有不同的结果
有时会发生死锁

3 实验：分区分配算法——BF和FF
1.实验设计说明
1.这个算法模拟的是对内存空间的管理，这个程序用了一个简单的二维数组模拟分区表。
2.程序首先要输入固定的五个分区的大小和始址，其次要输入作业的大小和实现的算法，由于这个程序把FF和BF放到一个程序中，便于比较两个算法。
首次适应算法FF(First Fit)
把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表
最佳适应算法BF（Best Fit）
首先把分区表按空间大小从小到大排序。然后把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表
2.实验代码
#include <stdio.h>
int table[5][3];
void FirstFit(int job[3],int ta[5][3])
{
int i,j;
for(j=0;j<3;j++)
for(i=0;i<5;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<5;j++)
{
for(i=0;i<3;i++)
printf("%d\t",ta[j][i]);
printf("\n");
}
}
void BestFit(int job[3])
{
int j1,temp1,temp2,temp3,i,j;
for(j1=0;j1<3;j1++)
{
for(i=0;i<5;i++)
for(j=0;j<4;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;
}
for(i=0;i<5;i++)
if(table[i][1]>=job[j1])
{
table[i][1]-=job[j1];
table[i][2]+=job[j1];
break;
}
}
if(i==5)printf("内存不足!请等待!\n");
printf("空闲区\t大小\t始址\n");
for(j=0;j<5;j++)
{
for(i=0;i<3;i++)
printf("%d\t",table[j][i]);
printf("\n");
}
}
void main()
{
int table1[5][3],job[3],j,i;
printf("请输入5个空分区的大小和始址：");
for(i=0;i<5;i++)
{
table[i][0]=i+1;
table1[i][0]=i+1;
for(j=1;j<3;j++)
{
scanf("%d",&table[i][j]);
table1[i][j]=table[i][j];
}
}
for(j=0;j<5;j++)
{
for(i=0;i<3;i++)
printf("%d\t",table[j][i]);
printf("\n");
}
printf("请输入3个要运行作业的大小：");
for(i=0;i<3;i++)
scanf("%d",&job[i]);
printf("请输入要实现的算法1(FF)2(BF):");
char c;
scanf("%d",&i);
getchar();
if(i==1)
{
FirstFit(job,table1);
printf("还要实现BF吗(y/n)");
if((c=getchar())=='y')
BestFit(job);
}
else
if(i==2)
{
BestFit(job);
printf("还要实现FF吗(y/n)");
if((c=getchar())=='y')
FirstFit(job,table1);
}
}

3.实验结果

4.实验结果分析
首先输入分区表的分区情况，然后输入运行作业的大小，选择要实现的算法。
第一个作业是96，因此找到第四个分区，第四个分区变为122，316，接着到第二个作业20，然后把第一个分区分给第二个作业，则第一个分区信息变为122，316，到第三个作业时，由于内存表中没有比第三个请求的分区还大的分区，因此会提示内存不足；
然后到BF算法，因为是按空间大小排序的，因此第一个作业96被分配给了已经排好序的内存为96的第五个分区，第二个作业被分配给大小为36的分区，第三个作业被分配给内存大小为218的分区，然后又对剩余空间再次排队，用来给下一批作业分配。
4 实验：页面置换算法——FIFO和LRU
1实验设计说明
程序设置了两个结构体,freeBlock和jobQueue,其中freeBlock代表物理块,初次创立物理块时,物理块的计时器time=0,还有代表作业的index=-1;
物理块有添加和删除的功能，每一次添加或删除都要初始化物理块。而且能够重复添加和删除，这样能够很好的测试算法的性能。
2.算法设计的思想是：进入物理块时间越长的则物理块的计时器数值越大，如果物理块中有要访问的页面，则那个含页面的物理块的计数器变成1；而且物理块要满才会发生置换，于是设置了物理块计数器Time；

2.实验代码
#include<stdio.h>
#include<stdlib.h>
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)
head=job;
else
{
jobQueue*j=head;
while(j->next)
j=j->next;
j->next=job;
}
return head;
}
freeBlock*creat(freeBlock*head)
{
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*inse(freeBlock*head)
{
freeBlock*test=head;
while(test)
{
test->index=-1;test->time=0;
test=test->next;
}
freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));
free->index=-1;free->time=0;
free->next=head;
head=free;
return head;
}
freeBlock*dele(freeBlock*head)
{
freeBlock*test=head;
while(test)
{
test->index=-1;test->time=0;
test=test->next;
}
freeBlock*f=head;
head=f->next;
free(f);
return head;
}
bool check(freeBlock*free,int j)
{
freeBlock*f=free;
while(f)
{
if(f->index==j)
return true;
f=f->next;
}
return false;
}
void LRU(freeBlock*free,jobQueue*job)
{
int size=0,Time=0,time=0;
jobQueue*jtest=job;
freeBlock*ftest=free;
while(ftest)
{
size++;
ftest=ftest->next;
}
printf("LRU置换页面为：");
while(jtest)
{
ftest=free;
while(ftest)
{
if(ftest->index==jtest->index)
ftest->time=0;
if(ftest->index==-1)
{
ftest->index=jtest->index;
ftest->time++;
time=0;
break;
}
ftest->time++;
if(Time<ftest->time)
Time=ftest->time;
time++;
ftest=ftest->next;
}
ftest=free;
while((time==size)&&ftest)
{
if(check(free,jtest->index))
{
time=0;
Time=0;
break;
}
if(ftest->time==Time)
{
printf("%d ",ftest->index);
ftest->index=jtest->index;
ftest->time=1;
time=0;
Time=0;
break;
}
ftest=ftest->next;
}
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)
{
if(ftest->index==-1)
{
ftest->index=jtest->index;
ftest->time++;
time=0;
break;
}
ftest->time++;
if(Time<ftest->time)
Time=ftest->time;
time++;
ftest=ftest->next;
}
ftest=free;
while((time==size)&&ftest)
{
if(check(free,jtest->index))
{
time=0;
Time=0;
break;
}
if(ftest->time==Time)
{
printf("%d ",ftest->index);
ftest->index=jtest->index;
ftest->time=1;
time=0;
Time=0;
break;
}
ftest=ftest->next;
}
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<p;i++)
block=creat(block);
printf("请输入作业个数：");
scanf("%d",&num);
printf("请输入作业：");
for(i=0;i<num;i++)
{
scanf("%d",&ch);
job=creat(job,ch);
}
FIFU(block,job);
LRU(block,job);
while(true)
{
printf("增加物理块（1）减少物理块（2）,否则按任意键");
scanf("%d",&num);
if(num==1)
{
printf("要增加几块：");
scanf("%d",&ch);
for(i=0;i<ch;i++)
block=inse(block);
FIFU(block,job);
LRU(block,job);
}
else if(num==2)
{
printf("要减少几块：");
scanf("%d",&ch);
if(ch>=p)
{
printf("sorry!");
break;
}
for(i=0;i<ch;i++)
block=dele(block);
FIFU(block,job);
LRU(block,job);
}
else ；break;
}
}
3.实验结果

4.实验结果分析
程序开始要输入物理块数目和作业个数,然后再输入作业.
在测试后能够随意添加或删除物理块来测试算法的性能。

5 实验：磁盘调度算法——SCAN和SSTF
1.实验设计说明
算法定义了一个双向链表，利用双向链表能够很好的进行方向的转换，且双向链表的中有代表磁盘号的标识符index；两个算法均采用访问完一个磁盘序列时删除该序列，其中scan算法实现时有点麻烦，首先要找到当前磁盘号序列的Max最大值和最小值Min及指向她们的指针pmax，pmin，另外