进程调度课程设计
2.1实验目的
用高级语言编写和调试一个有 N个进程并行的进程调度程序,以加深对进程的概念及进程调度算法的理解。
2.2实验设备
PC机、windows2000 操作系统、Turbo C 2.0 / VC++6.0
2.3实验要求
实验前应复习实验中所涉及的理论知识和算法,针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告,按时上交。
2.4实验内容
设计一个有N个进程并行的进程调度程序。
进程调度算法:采用最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)和先来先服务算法。具体描述如下:
每个进程有一个进程控制块( PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
分析:进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。
进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪 W(Wait)、运行R(Run)、或完成F(Finish)三种状态之一。
就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。
如果运行一个时间片后,进程的已占用 CPU时间已达到所需要的运行时间,则撤消该进程,如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减1(即降低一级),然后按照优先数的大小把它插入就绪队列等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB,以便进行检查。
重复以上过程,直到所要进程都完成为止。
调度算法的参考流程图如下:
2.5实 验 结 果 及 分 析
实验代码:
#include<stdio.h>
#include<stdlib.h>
struct pcb
{
char name[2];
char status;
int priority;
int need_time;
int used_time;
struct pcb *next;
};
typedef struct pcb *PCB;
PCB Initpcb()
{
PCB P;
P=(PCB)malloc(sizeof(struct pcb));
P->next=NULL;
return P;
}
void Sort(PCB P,struct pcb *p)
{
struct pcb *s,*q;
s=P->next;
if(s==NULL)
{
p->next=P->next;
P->next=p;
}
else
{
q=s->next;
while(q!=NULL)
{
if(p->priority<=s->priority&&p->priority>q->priority)
{
s->next=p;
p->next=q;
break;
}
else
{
s=q;
q=q->next;
}
}
if(p->priority<=s->priority)
{
s->next=p;
p->next=q;
}
else
{
s=P->next;
P->next=p;
p->next=s;
}
}
}
void Input(PCB P)
{
int SIZE,i;
struct pcb *p;
printf("Please input the number of process:");
scanf("%d",&SIZE);
printf("Please input the process's name status priority need_time used_time:\n ");
for(i=0;i<SIZE;i++)
{
printf("Process NO.%d \n",i+1);
p=(struct pcb *)malloc(sizeof(struct pcb));
scanf("%s %c %d %d %d",p->name,&p->status,&p->priority,&p->need_time,&p->used_time);
printf("\n");
p->next=NULL;
Sort(P,p);
}
}
int QueueNull(PCB P)
{
if(P->next==NULL)
return 0;
}
void Timeout(PCB P,int time)
{
int t;
t=P->next->need_time-P->next->used_time;
if(t>time)
P->next->used_time=P->next->used_time+time;
else
P->next->used_time=P->next->used_time+t;
P->next->priority=P->next->priority-1;
}
void display2(PCB P)
{
int n=0;
struct pcb *s,*t;
s=t=P;
s=P->next;
while(s!=NULL)
{
if(n==0)
{
printf("Running process:\n");
printf(" Name Status Priority Need_Time Used_time\n");
s->status='R';
printf("%6s%10c%11d%12d%12d\n",s->name,s->status,s->priority+1,s->need_time,s->used_time-2);
n=1;
}
else
{
printf("Waiting process:\n");
s->status='W';
printf(" Name Status Priority Need_Time Used_time\n");
printf("%6s%10c%11d%12d%12d\n",s->name,s->status,s->priority,s->need_time,s->used_time);
}
t=s;
s=t->next;
}
printf("\n\n");
}
void Deletepcb(PCB P)
{
struct pcb * s,*q;
s=P;
q=P->next;
P->next=q->next;
free(q);
}
void Sort2(PCB P)//该函数的作用是将头结点的后一个节点在链表中重新排序
{
struct pcb * s,*q,*p;
s=P->next;
p=s;
q=s->next;
P->next=q;
Sort(P,p);
//排序函数
}
main()
{
int time;
struct pcb * s,*q,*p;
printf("Please input the size of time:");
scanf("%d",&time);
PCB P;
s=P;
P=Initpcb();
Input(P);
while(QueueNull(P))
{
Timeout(P,time);
display2(P);
if(P->next->used_time==P->next->need_time)
Deletepcb(P);
else
{
Sort2(P);
}
}
}
实验截图:
第二篇:进程调度课程设计报告
课程设计报告
操作系统原理
专业 计算机科学与技术
M计算机081
20xx年1月10日 学生姓名 班学级 号 指导教师 完成日期
题目: 进程调度 的模拟实现
一、设计目的
本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练,通过课程设计,更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,加强学生的动手能力。
二、设计内容
(1)概述
编写并调试一个单道处理系统的作业等待模拟程序。
在多道程序和多任务系统中,系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作,必须选用某种调度策略,选择一进程占有处理机。要求学生设计一个模拟处理机调度算法,以巩固和加深处理机制调度的概念。
设计要求:
(1)进程调度算法包括:时间片轮转法,短作业优先算法,动态优先级算法。
(2)可选择进程数量。
(3)本程序包括三种算法,用C++语言实现,执行时在主界面选择算法,进入子页面后输入进程数,执行,显示结果。
(2)设计原理
1、先来先服务算法
原理:每次调度是从就绪队列中,选择一个最先进入就绪队列的进程,把处理器分配给该进程,使之得到执行。该进程一旦占有了处理器,它就一直运行下去,直到该进程完成或因发生事件而阻塞,才退出处理器。
特点:利于长进程,而不利于短进程。
2、短作业优先服务算法
原理:它是从就绪队列中选择一个估计运行时间最短的进程,将处理器分配给该进程,使之占有处理器并执行,直到该进程完成或因发生事件而阻塞,然后退出处理器,再重新调度。
3、最高响应比优先算法
原理:它是从就绪队列中选择一个响应比最高的进程,让其获得处理器执行,直到该进程完成或因等待事件而退出处理器为止。
特点:既照顾了短进程,又考虑了进程到达的先后次序,也不会使长进程长期得不到服务,因此是一个比较全面考虑的算法,但每次进行调度时,都需要对各个进程计算响应比。所以系统开销很大,比较复杂。
(3)详细设计及编码
1
源代码:
#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<<endl;
cout<<" 选择调度算法: "<<endl;
cout<<" 1: FCFS 2: 时间片轮换 3: 优先级调度 4: 最短作业优先 "<<endl; cin>>a;
const int Size =30;
Process process[Size] ;
int num;
int TimePice;
cout<<" 输入进程个数:"<<endl;
cin>>num;
cout<<" 输入此进程时间片大小: "<<endl;
cin>>TimePice;
for( int i=0; i< num; i++)
{
2
string name;
int CpuTime;
int Leval;
cout<<" 输入第 "<< i+1<<" 个进程的名字、 cpu时间和优先级 :"<<endl;
cin>>name;
cin>> CpuTime>>Leval;
process[i].ProcessName =name;
process[i].Time =CpuTime;
process[i].leval =Leval;
cout<<endl;
}
for ( int k=0;k<num;k++)
process[k].LeftTime=process[k].Time ;//对进程剩余时间初始化
cout<<" ( 说明: 在本程序所列进程信息中, 优先级一项是指进程运行后的优先级 !! )"; cout<<endl; cout<<endl;
cout<<"进程名字 "<<"共需占用CPU时间 "<<" 还需要占用时间 "<<" 优先级 "<<" 状态 "<<endl;
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)
3
{
proc1.leval =proc2.leval ;
proc1.ProcessName =proc2.ProcessName ;
proc1.Time =proc2.Time ;
}
/////////////////////////////////////////////
void Sort( Process pr[], int size) //以进程优先级高低排序 {// 直接插入排序
for( int i=1;i<size;i++)
{
Process temp;
temp = pr[i];
int j=i;
while(j>0 && temp.leval<pr[j-1].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<size;i++)
{
Process temp;
temp = pr[i];
int j=i;
while(j>0 && temp.Time < pr[j-1].Time )
{
pr[j] = pr[j-1];
4
j--;
}
pr[j] = temp;
}
}
////////////////////////////////
////
//// 先来先服务算法的实现
/////////////////////////////////
void Fcfs( Process process[], int num, int Timepice)
{ // process[] 是输入的进程,num是进程的数目,Timepice是时间片大小
//
while(true)
{
if(num==0)
{
cout<<" 所有进程都已经执行完毕 !"<<endl;
exit(1);
}
if(process[0].LeftTime==0)
{
cout<<" 进程 "<<process[0].ProcessName<< " 已经执行完毕 !"<<endl;
for (int i=0;i<num;i++)
process[i]=process[i+1];
num--;
}
else if(process[num-1].LeftTime==0)
{
cout<<" 进程 "<<process[num-1].ProcessName<< " 已经执行完毕 !"<<endl;
num--;
}
else
{
cout<<endl; //输出正在运行的进程
process[0].LeftTime=process[0].LeftTime- Timepice;
process[0].leval =process[0].leval-1;
cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<" ";
5
cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运行";
cout<<endl;
for(int s=1;s<num;s++)
{
cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<" ";
cout<<process[s].LeftTime <<" "<<process[s].leval<<"
等待 "<<endl; ;
}
} // else
cout<<endl;
system(" pause");
cout<<endl;
} // while
}
////////////////////////////////////////////////
///
/// 时间片轮转调度算法实现
//////////////////////////////////////////////
void TimeTurn( Process process[], int num, int Timepice)
{
while(true)
{
if(num==0)
{
cout<<" 所有进程都已经执行完毕 !"<<endl;
exit(1);
}
if(process[0].LeftTime==0)
{
cout<<" 进程 "<<process[0].ProcessName<< " 已经执行完毕 !"<<endl;
for (int i=0;i<num;i++)
process[i]=process[i+1];
num--;
}
if( process[num-1].LeftTime ==0 )
{
6
cout<<" 进程 " << process[num-1].ProcessName <<" 已经执行完毕! "<<endl; num--;
}
else if(process[0].LeftTime > 0)
{
cout<<endl; //输出正在运行的进程
process[0].LeftTime=process[0].LeftTime- Timepice;
process[0].leval =process[0].leval-1;
cout<<" "<<process[0].ProcessName <<"
";
cout<<process[0].LeftTime
"<<process[0].leval<<" 运行";
cout<<endl;
for(int s=1;s<num;s++)
{
cout<<" "<<process[s].ProcessName <<"
";
cout<<process[s].LeftTime <<"
if(s==1)
cout<<" 就绪 "<<endl;
else
cout<<" 等待 "<<endl;
}
Process temp;
temp = process[0];
for( int j=0;j<num;j++)
process[j] = process[j+1];
process[num-1] = temp;
} // else
cout<<endl;
system(" pause");
cout<<endl;
} // while
}
7 "<<process[0].Time <<" <<" "<<process[s].Time <<" "<<process[s].leval;
/////////////////////////////////////////////////
///
/// 优先级调度算法的实现
////////////////////////////////////////////////
void Priority( Process process[], int num, int Timepice)
{
while( true)
{
if(num==0)
{
cout<< "所有进程都已经执行完毕!"<<endl;
exit(1);
}
if(process[0].LeftTime==0)
{
cout<<" 进程 " << process[0].ProcessName <<" 已经执行完毕! "<<endl;
for( int m=0;m<num;m++)
process[m] = process[m+1]; //一个进程执行完毕后从数组中删除
num--; // 此时进程数目减少一个
}
if( num!=1 && process[num-1].LeftTime ==0 )
{
cout<<" 进程 " << process[num-1].ProcessName <<" 已经执行完毕! "<<endl;
num--;
}
if(process[0].LeftTime > 0)
{
cout<<endl; //输出正在运行的进程
process[0].LeftTime=process[0].LeftTime- Timepice;
process[0].leval =process[0].leval-1;
cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<" ";
cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运
行";
cout<<endl;
// 输出其他进程
for(int s=1;s<num;s++)
{
cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<" ";
8
cout<<process[s].LeftTime <<" "<<process[s].leval ; if(s==1)
cout<<" 就绪 "<<endl;
else
cout<<" 等待 "<<endl;
}
} // else
Sort(process, num);
cout<<endl;
system(" pause");
cout<<endl;
} // while }
流程图:
9
10
(4)结果及分析
(5)设计小结
这次实验使我加深对处理机进程调度机制的理解,对进程的概念有了更深一层次的认识。通过实现不同调度算法来实现调度进程,比较了不同调度算法的优缺点,掌握进程状态转换过程和处理机调度策略的实现。在编程中我不仅对课本内容有了更好的理解也提高了自己的编程能力。
(6)参考文献
(参考的书籍、网页等的作者信息、出处等)
11