实验二间片轮转RR进程调度算法
1、实验目的
通过这次实验,加深对进程概念的理解,进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。
2、试验内容
问题描述:
设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统,它们需要的服务时间分别为S1, … ,Sn。分别利用不同的时间片大小q,采用时间片轮转RR进程调度算法进行调度,计算每个进程的完成时间、周转时间和带权周转时间,并且统计n个进程的平均周转时间和平均带权周转时间。
3、程序要求:
1)进程个数n;每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn;输入时间片大小q。
2)要求时间片轮转法RR调度进程运行,计算每个进程的周转时间和带权周转时间,并且计算所有进程的平均周转时间和带权平均周转时间;
3)输出:要求模拟整个调度过程,输出每个时刻的进程运行状态,如“时刻3:进程B开始运行”等等;
4)输出:要求输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。
4、需求分析
(1) 输入的形式和输入值的范围
时间片
真实进程数
各进程的到达时间
各进程的服务时间
(2) 输出的形式
模拟整个调度过程、周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。
(3)测试用例
5、调试分析
由于自己自编写代码方面与他人有一定的差距,因此在做实验的过程中我在网上搜了很多相关的资料,了解实现该算法的原理及各部分实现的代码,同时参考了几个别人写好的源代码,然后自己在理解的基础上不断的根据要求修改写程序,不过其中碰见的很多的问题。我已经自己调了好多错误,在一遍遍的调试和修改中,发现自己的经验在快速增长,这个感觉真的很不错。然而,实验的运行结果还不是很完美,每个进程在最后一个时间片的运行过程中,进程列表的更新总是修改错误。不过在在本次试验中学到了不少东西,一点点的在进步。
6、测试结果
输入时间片,进程数,进程到达时间,服务时间
输出
输入时间片,进程数,进程到达时间,服务时间
输出
7、附录(java)
package experiment;
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class B_RR {
// 声明变量
// 时间片
public static int q = 0;
// 允许的最大进程数
public static int MaxNum = 100;
// 真正的进程数
public static int realNum;
// order数组的一个下标
public static int number;
// 当前时间
public static int NowTime;
// 各进程的达到时间
public static int ArrivalTime[] = new int[MaxNum];
// 各进程的服务时间
public static int ServiceTime[] = new int[MaxNum];
// 各进程的服务时间(用于记录进程服务时间随时间片轮转减少的过程)
public static int PServiceTime[] = new int[MaxNum];
// 各进程的完成时间
public static int FinishTime[] = new int[MaxNum];
// 各进程的周转时间
public static int WholeTime[] = new int[MaxNum];
// 进程调度队列(存放的是各个进程的数字代号,如进程A数字代号为1)
public static int order[] = new int[MaxNum];
// 各进程的带权周转时间
public static double WeightWholeTime[] = new double[MaxNum];
// 平均周转时间、平均带权周转时间
public static double AverageWT, AverageWWT;
// 周转时间总和
public static int SumWT = 0;
// 带权周转时间总和
public static double SumWWT = 0;
// 进程是否已经结束的标志
public static boolean Finished[] = new boolean[MaxNum];
public static Scanner stdin;
public static void main(String[] args) throws FileNotFoundException {
// 从文件中输入数据
BufferedInputStream in = new BufferedInputStream(new FileInputStream(
"./file/02"));
System.setIn(in);
stdin = new Scanner(System.in);
q = stdin.nextInt(); // 时间片q
realNum = stdin.nextInt(); // 真实进程数
for (int i = 0; i < realNum; i++) { // 各进程的服务时间
ArrivalTime[i] = stdin.nextInt();
}
for (int j = 0; j < realNum; j++) { // 各进程的服务时间
ServiceTime[j] = stdin.nextInt();
PServiceTime[j] = ServiceTime[j]; //用于记录进程服务时间随时间片轮转减少的过程
Finished[j] = false;
}
stdin.close();
int all_add = 1; //就绪队列中的进程个数
order[0] = 0; //进程调度队列(存放的是各个进程的数字代号,如进程A数字代号为1)
number = 1;
NowTime = 0; //现在时间
while (order[0] != 100) { //order[0]为100,是认为规定进程调度结束的标志
// 调度程序
char w = 'A';
System.out.println("时刻" + NowTime + ":进程" + (char)(w + order[0]) + "开始运行;");
if (PServiceTime[order[0]] > q) { //进程还未完成
PServiceTime[order[0]] = PServiceTime[order[0]] - q; //对应的进程的服务时间减去一个时间片
NowTime += q; //现在时刻增加一个时间片
System.out.println("时刻" + NowTime + ":进程" + (char)(w + order[0]) + "停止运行,加入就绪序列尾;");
} else { //进程剩一个时间片后结束
NowTime += PServiceTime[order[0]]; //现在时间增加一个时间片
PServiceTime[order[0]] = 0; //对应进程的服务时间归零
System.out.println("时刻" + NowTime + ":进程" + (char)(w + order[0]) + "运行结束;");
FinishTime[order[0]] = NowTime;
WholeTime[order[0]] = NowTime - ArrivalTime[order[0]];
WeightWholeTime[order[0]] = 1.0 * WholeTime[order[0]] / ServiceTime[order[0]];
}
// 将到达的程序加入序列尾
if (all_add < realNum) {
for (int i = 1; i < realNum; i++) {
if (NowTime >= ArrivalTime[i] && Finished[i] == false) { //判断该进程是否已经在就绪队列中
order[number++] = i;
all_add++;
Finished[i] = true;
}
}
}
// 将序列首程序调到序列尾
int temp = order[0];
for (int i = 0; i < number - 1; i++){ //将order中的每个数前移一位
order[i] = order[i + 1];
}
if (PServiceTime[temp] == 0){ //进程已将全部调度结束,通过将order的第一个数标记为100,来结束进程调度
order[--number] = 100;
}else{ //进程还未调度结束
order[number - 1] = temp;
}
}
double all = 0, all1 = 0;
for (int i = 0; i < realNum; i++) {// 计算总周转时间和总带权周转时间
all += WholeTime[i];
all1 += WeightWholeTime[i];
}
System.out.println("\n进程名\t到达时间\t服务时间\t完成时间\t周转时间\t带权周转时间");
for (int i = 0; i < realNum; i++) {
System.out.println((char)(i + 'A') + "\t" + ArrivalTime[i] + "\t"
+ ServiceTime[i] + "\t" + FinishTime[i] + "\t"
+ WholeTime[i] + "\t" + WeightWholeTime[i]);
}
AverageWT = all / realNum;
System.out.println("平均周转时间:" + AverageWT);
AverageWWT = all1 / realNum;
System.out.println("平均带权周转时间: " + AverageWWT);
}
}
操作系统实验报告
实验二
时间片轮转进程调度算法
学号:
班级:
姓名:
【实验题目】:时间片轮转进程调度算法
【实验目的】
通过这次实验,加深对进程概念的理解,进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。
【实验内容】
问题描述:
设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统,它们需要的服务时间分别为S1, … ,Sn。分别利用不同的时间片大小q,采用时间片轮转RR进程调度算法进行调度,计算每个进程的完成时间,周转时间和带权周转时间,并且统计n个进程的平均周转时间和平均带权周转时间。
程序要求如下:
1)进程个数n;每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn;输入时间片大小q。
2)要求时间片轮转法RR调度进程运行,计算每个进程的周转时间,带权周转时间,并且计算所有进程的平均周转时间,带权平均周转时间;
3)输出:要求模拟整个调度过程,输出每个时刻的进程运行状态,如“时刻3:进程B开始运行”等等;
4)输出:要求输出计算出来的每个进程的周转时间,带权周转时间,所有进程的平均周转时间,带权平均周转时间。
实现提示:
用C++语言实现提示:
1)程序中进程调度时间变量描述如下:
int ArrivalTime[100];
int ServiceTime[100];
int PServiceTime[100];
int FinishTime[100];
int WholeTime[100];
double WeightWholeTime[100];
double AverageWT,AverageWWT;
bool Finished[100];
2)进程调度的实现过程如下:
Ø 变量初始化;
Ø 接收用户输入n,T1, … ,Tn,S1, … ,Sn;时间片大小q;
Ø 按照时间片轮转RR算法进行进程调度,计算进程的完成时间、周转时间和带权周转时间;
Ø 计算所有进程的平均周转时间和平均带权周转时间;
Ø 按格式输出调度结果。
实验要求:
1)上机前认真复习时间片轮转RR进程调度调度算法,熟悉进程调度的执行过程;
2)上机时独立编程、调试程序;
3)根据具体实验要求,完成好实验报告(包括实验的目的、内容、要求、源程序、实例运行结果截图)。
【源程序】
头文件RR.h
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define MaxNum 100
typedef struct pcb //定义进程控制块
{
char Name[MaxNum]; //进程名
int arrivetime; //到达时间
int runtime; //运行时间
int wholetime; //固定运行时间
int FinishTime; //完成时间
double WeightTime; //周转时间
double WeightWholeTime; //带权周转时间
char state; //运行后的状态
struct pcb *next;
}PCB;
//全局变量
int N; //实际进程数
double SumWT; //周转时间之和
double SumWWT; //带权周转时间之和
double AverageWT; //平均周转时间
double AverageWWT; //平均带权周转时间
typedef struct //定义队列,封装头结点,指针分别指向队头和队尾
{
PCB *front,*rear;
}queue;
queue *init() //进程队列置空
{
queue *head;
head=(queue*)malloc(sizeof(queue));
head->front=NULL;
head->rear=NULL;
return head;
}
int empty(queue *head) //检验队列是否为空
{
return (head->front?0:1);
}
queue *append(queue *head,char c[MaxNum],int a,int r,char s) //进程队列入队,往后插入
{
PCB *p;
p=(PCB *)malloc(sizeof(PCB));
strcpy(p->Name,c);
p->arrivetime=a;
p->runtime=r;
p->wholetime=r;
p->state=s;
//p->FinishTime=0;
//p->WeightTime=0;
//p->WeightWholeTime=0;
p->next=NULL;
if(empty(head))
head->front=head->rear=p;
else
{
head->rear->next=p;
head->rear=p;
}
return head;
}
queue *creat(queue *head) //创建进程队列
{
char c[MaxNum];
char s='R';
int a,r,i;
printf("请输入共有几个进程:\n");
scanf("%d",&N);
for(i=1;i<=N;i++)
{
printf("请输入第%d 个进程的进程名:\n",i);
getchar();
gets(c);
printf("请输入第%d 个进程的到达时间:\n",i);
scanf("%d",&a);
printf("请输入第%d 个进程的服务时间:\n",i);
scanf("%d",&r);
head=append(head,c,a,r,s);
}
return head;
}
void print(queue *head) //输入创建的进程队列
{
PCB *p;
p=head->front;
if(!p)
printf("时间片轮转调度队列为空!\n");
while(p)
{
printf("Name=%s arrivetime=%d runtime=%d state=%c",p->Name,p->arrivetime,p->runtime,p->state);
printf("\n");
p=p->next;
}
}
/*******************时间片轮转法调度算法的实现**************************/
void RR(queue *head,int q)
{
int t=head->front->arrivetime, lt=head->rear->arrivetime;
if(head->front->runtime<q)
t=t+head->front->runtime;
else
t=t+q;
/****进程队列为不空才可调度*****/
while(!empty(head))
{
PCB *p1,*p2;
printf("\n时刻 进程 运行后的状态\n");
/*第一种情况:当前运行的时间小于最后一个进程到达时间做一下操作*/
while(t<lt)
{
p1=head->front;
printf("%2d %s",t,p1->Name);
p1->runtime=p1->runtime-q;
//1.运行时间小于0,删除队首
if(p1->runtime<=0)
{
p1->state='C';
printf(" %c\n",p1->state);
p1->FinishTime=t;
p1->WeightTime=p1->FinishTime-p1->arrivetime;
p1->WeightWholeTime=p1->WeightTime/p1->wholetime;
SumWT+=p1->WeightTime;
SumWWT+=p1->WeightWholeTime;
printf("时刻%2d进程%s运行结束,进程%s周转时间=%5.2f,带权周转时间=%5.2f\n",t,p1->Name,p1->Name,p1->WeightTime,p1->WeightWholeTime);
head->front=p1->next;
free(p1);
}
//2.运行时间大于0,向后找位置插入
else
{
printf(" %c\n",p1->state);
p2=p1->next;
while(p2->next && p2->arrivetime != t)
{
p2=p2->next;
}
//此时无新进入队列的进程,有两种情况:1.不用找位置往后插入,队首不变,不做操作
//2.找位置往后插入
if(p2->arrivetime != t)
{
PCB *p3=p1,*p4;
while(p3->next && p3->arrivetime<t)
{
p4=p3;
p3=p3->next;
}
if(p3->arrivetime>t)
{
if(p4!=p1) //p1插在p4后,头为p1->next
{
head->front=p1->next;
p1->next=p4->next;
p4->next=p1;
}
else //不做操作
p4=p3=p2=NULL;
}
else
p4=p3=p2=NULL;
}
//此时有新进入队列的进程时:p1插在新进入队列的进程p2后,队首为p1->next
else
{
head->front=p1->next;
p1->next=p2->next;
p2->next=p1;
}
}
//时刻变化
if(head->front->runtime<q)
t=t+head->front->runtime;
else
t=t+q;
}
/*************第一种情况结束**************/
/******************第二种情况:当期运行的时间大于最后一个进程到达的时间做以下操作*********************/
while(t>=lt)
{
p1=head->front;
printf("%2d %s",t,p1->Name);
p1->runtime=p1->runtime-q;
//1.运行时间小于0,删除队首
if(p1->runtime<=0)
{
p1->state='C';
printf(" %c\n",p1->state);
p1->FinishTime=t;
p1->WeightTime=p1->FinishTime-p1->arrivetime;
p1->WeightWholeTime=p1->WeightTime/p1->wholetime;
SumWT+=p1->WeightTime;
SumWWT+=p1->WeightWholeTime;
printf("时刻%2d进程%s运行结束,进程%s周转时间=%5.2f,带权周转时间=%5.2f\n",t,p1->Name,p1->Name,p1->WeightTime,p1->WeightWholeTime);
//printf("时刻%2d进程%s运行结束",t,p1->pname);
head->front=p1->next;
free(p1);
}
//2.运行时间大于0,直接插在队尾
else
{
printf(" %c\n",p1->state);
//若原队列只有一个进程,不必往队尾插
if(!p1->next)
head->front=p1;
//若原队列有多个进程
else
{
head->front=p1->next;
head->rear->next=p1;
head->rear=p1;
p1->next=NULL;
}
}
//时刻变化,队列为空时不做时刻变化
if(empty(head))
return;
else
{
if(head->front->runtime<q)
t=t+head->front->runtime;
else
t=t+q;
}
}
/*******第二种情况结束*********/
}
}
//主程序Main.cpp
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
void main()
{
queue *head;
int q;
head=init();
head=creat(head);
printf("\n您输入的时间片轮转进程队列为:\n");
print(head);
printf("\n请输入时间片轮转调度的时间片为:");
scanf("%d",&q);
//时间片轮转调度
RR(head,q);
AverageWT=SumWT/N;
AverageWWT=SumWWT/N;
printf("平均周转时间=%5.2f,平均带权周转时间=%5.2f",AverageWT,AverageWWT);
}
【实例运行结果截图】
实例(教材P92-图3-4)
Q=2
Q=4
实验报告说明1实验项目名称要用最简练的语言反映实验的内容要求与实验指导书中相一致2实验类型一般需说明是验证型实验还是设计型实验是创…
操作系统实验报告第一次实验时间片调度轮转算法实验时间20xx117院系计算机科学与技术学院班级软件2班实验要求1实验选题时间片调度…
网络协议分析实验4实验名称用Ethereal研究DNS和HTTP协议实验目的通过对捕获分组的分析和研究加深对DNS协议和HTTP协…
实验二进程调度报告一基本信息123实验题目进程调度完成人报告日期二实验内容简要描述1实验目标进程调度是处理机管理的核心内容本实验要…
实验报告时间片轮转RR进程调度算法题目时间片轮转算法的实现班级软件工程2班姓名代其全学号1025111022完成日期20xx102…
操作系统实验题设计一若干并发进程的进程调度程序一实验目的无论是批处理系统分时系统还是实时系统用户进程数一般都大于处理机数这将导致用…
1实验目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解掌握进程状态之间的切换同时掌握进程调度算法的实现方法和技巧…
1实验目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解掌握进程状态之间的切换同时掌握进程调度算法的实现方法和技巧…
操作系统进程调度实验报告一实验目的用高级语言编写和调试一个进程调度程序以加深对进程的概念及进程调度算法的解进程调度时进程管理的主要…
实验一进程调度实验专业XXXXX学号XXXXX姓名XXX实验日期20XX年XX月XX日一实验目的通过对进程调度算法的模拟加深对进程…