2023年进程调度算法实验报告_第1页
2023年进程调度算法实验报告_第2页
2023年进程调度算法实验报告_第3页
2023年进程调度算法实验报告_第4页
2023年进程调度算法实验报告_第5页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

操作系统实验报告(二)

实验题目:进程调度算法

实验环境:C++

实验目的:编程模拟实现几种常见的进程调度算法,通过对几组进程分别使用不

同的调度算法,计算进程的平均周转时间和平均带权周转时间,比较

各种算法的性能优劣。

实验内容:编程实现如下算法:

1.先来先服务算法;

2.短进程优先算法;

3.时间片轮转调度算法。

设计分析:

程序流程图:

1.先来先服务算法

2.短进程优先算法

3.时间片轮转调度算法

实验代码:

1.先来先服务算法

#include<iostream.h>

#definen20

typedefstruct

intid;〃进程名

intatime;//进程到达时间

intruntime;//进程运营时间

}fcs;

voidmain()

{

intamount,i,j.diao.huan:

fcsf[n];

cout<<"请输入进程个数:"Vvendl;

cin>>amount;

for(i=0;i<amount;i++)

(

cout<v”请输入进程名,进程到达时间,进程运营时间:"vvendl;

cin>>f[i].id;

cin»f[i].atime;

cin>>f[i].runtime;

)

for(i=0;i<amount;i++)//按进程到达时间的先后排序

(〃假如两个进程同时到达,按在屏幕先输入的先运营

for(j=0;j<amount-i-1;j++)

{if(f[j].atime>f[j+1J.atime)

{diao=f[j].atime;

f[j].atime=f[j+1].atime;

f[j+1].atime=diao;

huan=f[j].id:

f[j].id=f0+U.id;

f[j+1].id=huan;

}

)

}

for(i=0;i<amount;i++)

(

coutvv"进程:"V<f从«f[i],atime<<"开始"在"

«f[i].atime+f[i].runtime之前结束。"<<endl:

f[i+1].atime=f[i].atime+f[i].runtime;

)

2.短进程优先算法

#include<stdio.h>

#definen5

#definenum5

#definemax65535

typedefstructpro

{intPROJD;

intarrive_time;

intsum_time;

intflag;

}Pro;〃整数排序

intbubble(inttempQ)

(

ointi,j,tem=0;

for(i=1;i<num;i++)

o{intlastX=1;

gfor(j=0;j<num-i;j++)

Mif(temp[j]>temp[j+1])

0o{tem=temp[j];

oootemp[j]=temp[j+1]:

otemp[j+1]=tem;

lastX=0;

)

&if(lastX==1)break;

)

ooreturntemp(0];

)

〃进程排序

Probubble(PropO)

{

int\,j:

Protemp={0};

oPros[num];

ofor(i=0;i<num;i4-+)

{s[i]=p[i];

DO}

oofor(i=1;i<num;i++)

oo{

DointlastX=1;

gfor(j=O;j<num—i;j++)

ob{

ggif(s[j].sum_time>s[j4-1].sum_time)

o(

otemp=s[j];

0Ms[j]=sO+1];

oooos[j+1]=temp;

ooolastX=0;

)

ooo)

»if(lastX==1)break;

g}

oreturns[0];

)

VOidSPF(intp)

(

oif(n>0)

(

inti,j,k,l,tc=0;

ooProseq[n];

oProtemp_seq[n];

oprintf("短进程优先调度算法SPF\n");

gPrintf("请依次输入5个进程的进程号、到达时间和执行时间\n");

printf("成员变量用逗号隔开;进程间用回车隔开\n”);

ofor(i=0;i<n;i++)(

Dscanf(M%d,%d,%d”,&seq[i].PRO_ID,&seq[i].arrive_time,&seq[i].sum_time);

o)

gprintf("调度顺序是:\n");o

初始化tc

ointtemp[num];

for(i=0;i<num;i4-+)

o(

otemp[i]=seq[i].arrive_time;

}

otc=bubble(temp);//tc是断点啊

//flag表达相应i的pr。的队列情况

//-i表达未进入过队列,0表达在队列中,1表达被清除r

»for(i=0;i<n:i++){

seq[i].f1ag=-1;

0}

for(i=0;i<n;i++){

ofor(j=0;j<n;j++){

0Dif(seq[j].f1ag!=1&&seq[j].arrive_time<=tc){

00Dseq[j].flag=0;

Doo}

0}

0bforQ=0;j<n;j++){

gtemp_seq[j]=seq[j];

0oif(seq[jj.flag!=0){

DOtemp_seq[j].sum_time=max;

g)

o}

&l=bubble(temp_seq).PRO」D;

0ofor(j=0:j<n:j++){

0>jf(|==seq[j].PRO」D){

02k=j;

0。)

0)

gtc=tc+bubbIe(temp_seq).su

seq[k].flag=1;o

00printf("%d",I);

)

printf("\n");

)

)

voidmain()

(

SPF(n);

}

3.时间片轮转调度算法

头文献RR.h

#include<iostream>

#include<stdjo.h>

#incIude<string.h>

#include<stdlib.h>

#include<clype.h>

#defineMaxNum100

typedefstructpcb〃定义进程控制块

(

charName[MaxNum];〃进程名

ointarrivetime;//到达时间

ointruntime;〃运营时间

intwholetime;//固定运营时间

intFinishTime;〃完毕时间

odoubleWeightTime;//周转时间

doubleWeightWholeTime:〃带权周转时间

ocharstate:〃运营后的状态

ostructpcb*next;

}PCB;

〃全局变量

intN;//实际进程数

doubleSumWT;/倜转时间之和

doubleSumWWT;//带权周转时间之和

doubIeAverageWT;〃平均周转时间

doubIeAverageWWT;〃平均带权周转时间

typedefstruct〃定义队列,封装头结点,指针分别指向队头和队尾

{

oPCB*front,*rear;

}queue;

queue*init()〃进程队列置空

(

queue*head;

ohead=(queue*)ma1loc(sizeof(queue));

ohead->front=NULL;

ohead->rear=NULL;

oreturnhead;

}

intempty(queue*head)〃检查队列是否为空

(

oreturn(head->front?0:1);

)

queue*append(queue*head,charc[MaxNum],inta,intr,chars)//进程队列入队,往后插入

oPCB*p;

op=(PCB*)malloc(sizeof(PCB));

ostrcpy(p->Name,c);

p->arrivetime=a;

p->runtime=r;

p->whoIetime=r;

op->state=s;

o/Zp—>FinishTime=0;

//p->WeightTime=0;

//p->WeightWhoIeTime=0:

op->next=NULL;

if(empty(head))

head->front=head->rear=p;

else

M

ohead->rear->next=p;

ohead—>rear=p;

oreturnhead;

}

queue*creat(qucue*head)〃创建进程队列

(

charc[MaxNum];

chars='R';

ointa,r,i;

printf("请输入共有几个进程:\n");

oscanf("%d",&N);

for(i=1;i<=N;i++)

o(

»printf("请输入第%d个进程的进程名:

ogetchar();

oogets(c);

0printf("请输入第%:1个进程的到达时间:\n",i);

scanf("%d",&a);

0printf("请输入第%d个进程的服务时间:\n",i);

ooscanf("%d*',&r);

ohead=append(head,c,a,r,s);

)

returnhead;

)

voidprint(queue*head)〃输入创建的进程队列

(

oPCB*p;

t>p=head->front;

oif(!p)

DPrintf("时间片轮转调度队列为空!'nM);

owhiIe(p)

(

DPrintf("Name=%sarrivetime=%druntime=%dstate=%c'\p->Name,p—>arrivetime,p—>run

time,p->state);

oprintf(M\n");

p=p->next;

/*******************时间片轮转法调度算法的实现************************

voidRR(queue*headjntq)

(

intt=head—>front—>arrivetime,1t=head->rear->arrivetime;

if(head->front->runtime<q)

oot=t+head->front->runtime;

oelse

ot=t+q;

/****进程队列为不空才可调度*****/

while(!empty(head))

M

PCB*p1,*p2;

printf”n时刻进程运营后的状态\n");

o/*第一种情况:当前运营的时间小于最后一个进程到达时间做一下操作7

while(t<1t)

M

gp1=head->front;

owprintf("%2d%sH,t,p1->Name);

op1->runtime=p1->runtime-q:

o//1.运营时间小于0,删除队首

ooif(p1->runtime<=0)

p1—>state-C";

DOOPrintf("%c\n",p1->state);

op1->FinishTime=t;

o»p1—>WeightTime=p1->FinishTime—p1->arrivetime;

oP1->WeightWhoIeTime=p1->WeightTime/p1—>whoIetime;

SumWT+=p1—>WeightTime;

ooSumWWT-|-=p1->WeightWhoIeTime;

oPrintf("时刻%2d进程%s运营结束,进程%s周转时间=%5.2f,带权周转时间=%5.2加”,t,p1->Name,

P1->Name,p1->WeightTime,pI->WeightWhoIeTime);

ohead->front=p1—>next;

free(p1);

Q

〃2.运营时间大于。,向后找位置插入

oelse

000{

oprintf(M%c\n0,p1->state):

oop2=p1->next;

owwhile(p2->next&&p2->arrivetime!=t)

。(

00p2=p2->next;

g}

g"/此时无新进入队列的进程,有两种情况:1.不用找位置往后插入,队首不变,不做操作

。〃2.找位置往后插入

boif(p2->arrivetime!=t)

o(

oPCB*p3=p1,*p4;

0000whi1e(p3->next&&p3->arrivetime<t)

0

oo&wp4=p3;

p3=p3->next;

0o)

oif(p3->arrivctime>t)

o6if(p4!=p1)//p1插在p4后,头为p1->next

000

t>oohead->front=p1->next;

oooop1->next=p4->next;

MOOop4->next=p1;

gw}

ooelse//不做操作

oowP4=p3=p2=NULL;

。)

oeIse

ooop4=p3=p2=NULL;

oo〃此时有新进入队列的进程时:p1插在新进入队列的进程p2后,队首为p1->next

ooo&else

oohead->front=p1—>next;

op1->next=p2->next;

o(x>op2->next=p1:

o

oo)

gW时刻变化

oif(head->front->runtime<q)

ot=t+head—>front—>runtime;

e1se

0ot=t+q;

o)

W*************第一种情况结束**************/

oo/******************第二种情况:当期运营的时间大于最后一个进程到达的时间做以下操作*********************/

while(t>=lt)

oo{

gpL=head->front;

goprintf("%2d%s",t,p1->Name);

p1->runtime=p1—>runtime—q;

o〃1.运营时间小于0,删除队首

if(p1->runtime<=0)

e(

p1->state-C";

gprintf("%c\n",p1->state);

p1->FinishTime=t;

gp1->WeightTime=p1—>FinishTime-p1->arrivetime;

owp1->WeightWhoIeTime=p1->WeighITime/p1->wholetime;

SumWT+=p1->WeightTime;

ooSumWWT+=p1—>WeightWholeTime;

DMprintf("时刻%2d进程%s运营结束,进程%s周转时间=%5.2f,带权周转时间=%5.2f\n",t,p1->Name,p1->

Name.p1->WeightTime,p1—>WeightWhoIeTime);

0//printf0时刻%2d进程%s运营结束”,t,p1->pname);

oohead->front=p1->next:

ooofree(p1);

)

W/2.运营时间大于0,直接插在队尾

oelse

。(

oprintf("%c\n",p1—>state);

g若原队列只有一个进程,不必往队尾插

if(!p1->next)

ohead->front=p1;

oo〃若原队列有多个进程

oweIse

ohead—>front=p1->next;

ohead->rear->next=p1;

oohead->rear=p1;

op1->next=NULL;

ooo}

g}

mW时刻变化,队列为空时不做时刻变化

if(empty(head))

ooreturn;

ooeIse

ooo(

00if(head->front->runtime<q)

owt=t+head->front->runtime:

goelse

00ot=t+q;

g}

)

/*******第二种情况结束*********/

)

0

主程序Main.cpp

#include<iostream>

#inc1ude<sldio.h>

#include<string.h>

#include<stdlib.h>

#inc1ude<ctype.h>

#include"RR.h”

voidmain()

(

o<lueue*head;

intq;

ohead=init();

head=creat(head);

oprintf("\n您愉入的时间片轮转进程队列为:\n");

oprint(head);

oprintf("\n请输入时间片轮转调度的时间片为:");

scanf("%d",&q);

时间片轮转调度

RR(head,q);

t>AverageWT=SumWT/N;

AverageWWT=SumWWT/N;

OPrintf("平均周转时间=%5.2f,平均带权周转时间=%5.2f',AverageWT,AverageWWT);

)

运营结果:

先来先服务:

二0X

,进程到达时间,进程运行时间:

,进程到达时间,进程运行时间:

®

004甲.A

=-口•

汝.•

4福

干A

14'Q1.

,W

H结

239于-A

H千

349于-A494

长d

H千A

*,结

,福

654-C3之

片HI*,

千/

A枪

46于

3-C,4之

HHI,

583-A说

41吸

H口*,

C,。

71-洁

e19A1r-。

件N

口*p

历.42

81喀

A洁

41R-。

便2

.不84,

8.A1洁

-。

9从1485。n

口zB

.子

口一

-人19n

1A、

8E)乒

女/

1619-

0/于1

1k1千AEn

19女20j

2:256乒

1吴

k甲A22

1女E

,乒B-

96,J

>2于I

千A

1'?女EUE

八6SB-

:3,、

00o-

y:ytcO-

anke-

ess-

-

-

短进程:-

元P

的SP

时间

行密

4

0,

1,35

2,10

7,21

9,35

11,23

12,42

13,1

0,14,7

1,20,5

2,23,3

.3,24,22

调度顺序是:

>034910121125137168

Pressanykeytocontinue

时间片轮:

-进

.-1冏

±进S

T,-

-口Le

进6

T-士=1

即=

-口

亨7

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论