操作系统教程
——进程调度算法
进程调度算法的模拟实现
● 实验目的
1.本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。
2.利用程序设计语言编写算法,模拟实现先到先服务算法FCFS、轮转调度算法RR、最短作业优先算法SJF、优先级调度算法PRIOR、最短剩余时间优先算法SRTF。
3.进行算法评价,计算平均等待时间和平均周转时间。
● 实验内容及结果
1.先来先服务算法
2.轮转调度算法
3. 优先级调度算法
4. 最短时间优先算法
5. 最短剩余时间优先算法
● 实验总结
在此次模拟过程中,将SRTF单独拿了出来用指针表示,而其余均用数组表示。
● 完整代码
【Srtf.cpp代码如下:】
//最短剩余时间优先算法的实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct
{
int remain_time; //进程剩余执行时间
int arrive_time; //进程到达时间
int Tp; //进入就绪队列的时间
int Tc; //进入执行队列的时间
int To; //进程执行结束的时间
int number; //进程编号
}Process_Block; //定义进程模块
typedef struct _Queue
{
Process_Block PB;
struct _Queue *next;
}_Block,*Process; //定义一个进程模块队列中结点
typedef struct
{
Process head; //队列头指针
Process end; //队列尾指针
}Process_Queue; //进程队列
Process_Queue PQ; //定义一个全局队列变量
int t; //全局时间
Process Run_Now; //当前正在运行的进程,作为全局变量
void InitQueue(Process_Queue PQ)
{
PQ.head ->next = NULL;
PQ.end ->next = PQ.head;
}/*初始化队列*/
int IsEmpty(Process_Queue PQ)
{
if(PQ.end->next == PQ.head)
return 1; //队列空的条件为头指针指向尾指针并且尾指针指向头指针
else
return 0;
}/*判定队列是否为空队列*/
void EnQueue(Process_Queue PQ,Process P)
{
Process temp =(Process)malloc(sizeof(_Block));
temp = PQ.end;
temp->next->next = P;
PQ.end->next = P;
}/*插入队列操作*/
Process DeQueue(Process_Queue PQ)
{
if(IsEmpty(PQ))
return NULL;
Process temp = PQ.head->next;
PQ.head->next= temp ->next;
if(PQ.end->next == temp)
PQ.end->next = PQ.head;
return temp;
}/*出列操作*/
Process ShortestProcess(Process_Queue PQ)
{
if(IsEmpty(PQ)) //如果队列为空,返回
{
if(!Run_Now)
return NULL;
else
return Run_Now;
}
Process temp,shortest,prev;
int min_time;
if(Run_Now) //如果当前有进程正在执行,
{
shortest = Run_Now; //那么最短进程初始化为当前正在执行的进程,
min_time = Run_Now->PB.remain_time;
}
else //如果当前没有进程执行,
{
shortest = PQ.head->next; //则最短进程初始化为队列中第一个进程
min_time = PQ.head->next->PB.remain_time;
}
temp = PQ.head;
prev = temp;
while(temp->next)
{
if(temp->next->PB.remain_time
{
shortest = temp->next; //则保存当前进程,
min_time = shortest->PB.remain_time;
prev=temp; //及其前驱
}
temp=temp->next;
}
if(shortest == PQ.end->next) //如果最短剩余时间进程是队列中最后一个进程,
PQ.end->next = prev; //则需要修改尾指针指向其前驱
prev->next = shortest->next; //修改指针将最短剩余时间进程插入到队头
return shortest;
}/*调度最短剩余时间的进程至队头*/
void Run()
{
Run_Now->PB.remain_time--; //某一时间运行它的剩余时间减
return;
}/*运行函数*/
void Wait()
{
return ;
}
int sum(int array[],int n)
{
int i,sum=0;
for(i=0;i
sum+=array[i];
return sum;
}
int main()
{
PQ.head = (Process)malloc(sizeof(_Block));
PQ.end = (Process)malloc(sizeof(_Block));
Run_Now = (Process)malloc(sizeof(_Block));
Run_Now =NULL;
InitQueue(PQ);
int i,N,Total_Time=0; //Total_Time为所有进程的执行时间之和
printf("请输入计算机中的进程数目:\n");
scanf("%d",&N);
Process *P,temp;
P = (Process*)malloc(N*sizeof(Process));
int *wt,*circle_t;
wt =(int*)malloc(N*sizeof(int));
circle_t =(int*)malloc(N*sizeof(int));
for(i=0;i
{
P[i] = (Process)malloc(sizeof(_Block));
P[i]->PB.number =i+1;
P[i]->next =NULL;
wt[i] =0;
circle_t[i] =0;
printf("输入第%d个进程的到达时间及剩余执行时间:\n",i+1);
scanf("%d %d",&P[i]->PB.arrive_time,&P[i]->PB.remain_time);
}
for(i=0;i
Total_Time+=P[i]->PB.remain_time;
printf("\n进程按顺序运行依次为:\n");
i=0;
int k=0;
for(t=0;;t++)
{
if(Run_Now) //如果当前有进程正在执行
{
Run();
if(t == P[i]->PB.arrive_time) //如果当前时间正好有进程进入
{
if(P[i]->PB.remain_time < Run_Now->PB.remain_time)
{
temp = P[i];
P[i] = Run_Now;
Run_Now = temp; //则调度它至运行队列中,
Run_Now->PB.Tp=t;
Run_Now->PB.Tc=t;
wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;
printf("%d ",Run_Now->PB.number);
}
EnQueue(PQ,P[i]); //并将当前运行进程重新插入队列中
P[i]->PB.Tp=t;
k++;
i=(i+1)>(N-1)?(N-1):(i+1);
}
if(Run_Now->PB.remain_time == 0) //如果当前进程运行结束,
{
Run_Now->PB.To=t; //进程运行结束的时间
circle_t[Run_Now->PB.number-1] +=t-Run_Now->PB.arrive_time;
free(Run_Now); //则将它所占资源释放掉,
Run_Now =NULL; //并修改Run_Now为NULL
Run_Now = ShortestProcess(PQ); //从就绪队列中调出最短剩余时间进程至队头,
if(!Run_Now) //如果队列为空,转为等待状态
{
if(IsEmpty(PQ) && k >= N) break;
Wait();
continue;
}
else
{
Run_Now->PB.Tc=t;
wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;
printf("%d ",Run_Now->PB.number);
}
}
}
else //如果当前运行进程为空,那么
{
if(t == P[i]->PB.arrive_time) //如果正好这时有进程入队
{
k++;
EnQueue(PQ,P[i]);
Run_Now = DeQueue(PQ); //则直接被调入运行队列中
Run_Now->PB.Tp=t;
Run_Now->PB.Tc=t;
printf("%d ",Run_Now->PB.number);
i=(i+1)>(N-1)?(N-1):(i+1);
}
else
{
Wait();
continue;
}
}
}
printf("\n");
printf("平均等待时间是:\n%f\n",((float)sum(wt,N))/N);
printf("平均周转时间是:\n%f\n",((float)sum(circle_t,N))/N);
return 0;
}
//////////////////////////////////////////////////////
【Process.cpp代码如下:】
#include<iostream>
#include<string>
using namespace std;
class Process
{
public:
string ProcessName; // 进程名字
int Time; // 进程需要时间
int leval; // 进程优先级
int LeftTime; // 进程运行一段时间后还需要的时间
};
void Copy ( Process proc1, Process proc2); // 把proc2赋值给proc1
void Sort( Process pr[], int size) ; // 此排序后按优先级从大到小排列
void sort1(Process pr[], int size) ; // 此排序后按需要的cpu时间从小到大排列
void Fcfs( Process pr[], int num, int Timepice); // 先来先服务算法
void TimeTurn( Process process[], int num, int Timepice); // 时间片轮转算法
void Priority( Process process[], int num, int Timepice); // 优先级算法
void main()
{
int a;
cout<
cout<<" 选择调度算法:"<
cout<<" 1: FCFS 2: 时间片轮换 3: 优先级调度 4: 最短作业优先 5: 最短剩余时间优先"<
cin>>a;
const int Size =30;
Process process[Size] ;
int num;
int TimePice;
cout<<" 输入进程个数:"<
cin>>num;
cout<<" 输入此进程时间片大小: "<
cin>>TimePice;
for( int i=0; i< num; i++)
{
string name;
int CpuTime;
int Leval;
cout<<" 输入第"<< i+1<<" 个进程的名字、cpu时间和优先级:"<
cin>>name;
cin>> CpuTime>>Leval;
process[i].ProcessName =name;
process[i].Time =CpuTime;
process[i].leval =Leval;
cout<
}
for ( int k=0;k
process[k].LeftTime=process[k].Time ;//对进程剩余时间初始化
cout<<" ( 说明: 在本程序所列进程信息中,优先级一项是指进程运行后的优先级!! )";
cout<
cout<<"进程名字"<<"共需占用CPU时间 "<<" 还需要占用时间 "<<" 优先级"<<" 状态"<
if(a==1)
Fcfs(process,num,TimePice);
else if(a==2)
TimeTurn( process, num, TimePice);
else if(a==3)
{
Sort( process, num);
Priority( process , num, TimePice);
}
else // 最短作业算法,先按时间从小到大排序,再调用Fcfs算法即可
{
sort1(process,num);
Fcfs(process,num,TimePice);
}
}
void Copy ( Process proc1, Process proc2)
{
proc1.leval =proc2.leval ;
proc1.ProcessName =proc2.ProcessName ;
proc1.Time =proc2.Time ;
}
void Sort( Process pr[], int size) //以进程优先级高低排序
{// 直接插入排序
for( int i=1;i
{
Process temp;
temp = pr[i];
int j=i;
while(j>0 && temp.leval
{
pr[j] = pr[j-1];
j--;
}
pr[j] = temp;
} // 直接插入排序后进程按优先级从小到大排列
for( int d=size-1;d>size/2;d--)
{
Process temp;
temp=pr [d];
pr [d] = pr [size-d-1];
pr [size-d-1]=temp;
} // 此排序后按优先级从大到小排列
}
/* 最短作业优先算法的实现*/
void sort1 ( Process pr[], int size) // 以进程时间从低到高排序
{// 直接插入排序
for( int i=1;i
{
Process temp;
temp = pr[i];
int j=i;
while(j>0 && temp.Time < pr[j-1].Time )
{
pr[j] = pr[j-1];
j--;
}
pr[j] = temp;
}
}
/* 先来先服务算法的实现*/
void Fcfs( Process process[], int num, int Timepice)
{ // process[] 是输入的进程,num是进程的数目,Timepice是时间片大小
while(true)
{
if(num==0)
{
cout<<" 所有进程都已经执行完毕!"<
exit(1);
}
if(process[0].LeftTime==0)
{
cout<<" 进程"<
for (int i=0;i
process[i]=process[i+1];
num--;
}
else if(process[num-1].LeftTime==0)
{
cout<<" 进程"<
num--;
}
else
{
cout<
process[0].LeftTime=process[0].LeftTime- Timepice;
process[0].leval =process[0].leval-1;
cout<<" "<
cout<
}
} // else
cout<
system(" pause");
cout<
} // while
}
/* 时间片轮转调度算法实现*/
void TimeTurn( Process process[], int num, int Timepice)
{
while(true)
{
if(num==0)
{
cout<<" 所有进程都已经执行完毕!"<
exit(1);
}
if(process[0].LeftTime==0)
{
cout<<" 进程"<
for (int i=0;i
process[i]=process[i+1];
num--;
}
if( process[num-1].LeftTime ==0 )
{
cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕! "<
num--;
}
else if(process[0].LeftTime > 0)
{
cout<
process[0].LeftTime=process[0].LeftTime- Timepice;
process[0].leval =process[0].leval-1;
cout<<" "<
cout<
if(s==1)
cout<<" 就绪"<
else
cout<<" 等待"<
}
Process temp;
temp = process[0];
for( int j=0;j
process[j] = process[j+1];
process[num-1] = temp;
} // else
cout<
system(" pause");
cout<
} // while
}
/* 优先级调度算法的实现*/
void Priority( Process process[], int num, int Timepice)
{
while( true)
{
if(num==0)
{
cout<< "所有进程都已经执行完毕!"<
exit(1);
}
if(process[0].LeftTime==0)
{
cout<<" 进程" << process[0].ProcessName <<" 已经执行完毕! "<
for( int m=0;m
process[m] = process[m+1]; //一个进程执行完毕后从数组中删除
num--; // 此时进程数目减少一个
}
if( num!=1 && process[num-1].LeftTime ==0 )
{
cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕! "<
num--;
}
if(process[0].LeftTime > 0)
{
cout<
process[0].LeftTime=process[0].LeftTime- Timepice;
process[0].leval =process[0].leval-1;
cout<<" "<
cout<
if(s==1)
cout<<" 就绪"<
else
cout<<" 等待 "<
}
} // else
Sort(process, num);
cout<
system(" pause");
cout<
} // while
}
操作系统实验报告二实验题目进程调度算法实验环境C实验目的编程模拟实现几种常见的进程调度算法通过对几组进程分别使用不同的调度算法计算…
进程调度算法模拟专业XXXXX学号XXXXX姓名XXX实验日期20XX年XX月XX日一实验目的通过对进程调度算法的模拟加深对进程概…
操作系统教程进程调度算法进程调度算法的模拟实现●实验目的1.本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。2.…
操作系统实验报告实验一进程调度算法学生学号学院系别专业实验时间报告时间一实验内容按优先数调度算法实现处理器调度二实验目的在采用多道…
实验一进程调度一实验题目1编写并调试一个模拟的进程调度程序采用最高优先数优先调度算法对五个进程进行调度2编写并调试一个模拟的进程调…
操作系统实验题设计一若干并发进程的进程调度程序一实验目的无论是批处理系统分时系统还是实时系统用户进程数一般都大于处理机数这将导致用…
1实验目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解掌握进程状态之间的切换同时掌握进程调度算法的实现方法和技巧…
1实验目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解掌握进程状态之间的切换同时掌握进程调度算法的实现方法和技巧…
实验一进程调度一实验题目1编写并调试一个模拟的进程调度程序采用最高优先数优先调度算法对五个进程进行调度2编写并调试一个模拟的进程调…
操作系统实验报告二实验题目进程调度算法实验环境C实验目的编程模拟实现几种常见的进程调度算法通过对几组进程分别使用不同的调度算法计算…
算法分析与设计实验报告实验报告题目实验一递归与分治策略一实验目的1加深学生对分治法算法设计方法的基本思想基本步骤基本方法的理解与掌…