操作系统实验题：设计一若干并发进程的进程调度程序

一、实验目的

无论是批处理系统、分时系统还是实时系统，用户进程数一般都大于处理机数，这将导致用户进程互相争夺处理机。这就要求进程调度程序按一定的策略，动态地把处理及分配给处于就绪队列中的某一进程，以使之执行。进程调度是处理机管理的核心内容。本实验要求采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法编写和调试一个简单的进程调度程序。通过本实验可以加深理解有关进程控制块、进程队列的概念。并体会了优先数和先来先服务调度算法的具体实施办法。

二、实验要求

用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解．

三、实验内容

 进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法（将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理）。

每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。

进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。

进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。

就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。

如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。

每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。 重复以上过程，直到所要进程都完成为止。

四、实验算法流程

调度算法的流程图如下 :

　　

五、实验程序清单

#include "stdio.h"

#include ＜stdlib.h＞

#include ＜conio.h＞

#define getpch(type) (type*)malloc(sizeof(type))

#define NULL 0

struct pcb { /* 定义进程控制块PCB */

char name[10];

char state;

int super;

int ntime;

int rtime;

struct pcb* link;

}*ready=NULL,*p;

typedef struct pcb PCB;

char sort() /* 建立对进程进行优先级排列函数*/

{

PCB *first, *second;

int insert=0;

if((ready==NULL)||((p-＞super)＞(ready-＞super))) /*优先级最大者,插入队首*/

{

p-＞link=ready;

ready=p;

}

else /* 进程比较优先级,插入适当的位置中*/

{

first=ready;

second=first-＞link;

while(second!=NULL)

{

if((p-＞super)＞(second-＞super)) /*若插入进程比当前进程优先数大,*/

{ /*插入到当前进程前面*/

p-＞link=second;

first-＞link=p;

second=NULL;

insert=1;

}

else /* 插入进程优先数最低,则插入到队尾*/

{

first=first-＞link;

second=second-＞link;

}

}

if(insert==0) first-＞link=p;

}

}

char input() /* 建立进程控制块函数*/

{

int i,num;

//clrscr(); /*清屏*/

printf("\n 请输入被调度的进程数目：");

scanf("%d",&num);

for(i=0;i＜num;i++)

{

printf("\n 进程号No.%d:\n",i);

p=getpch(PCB);

printf("\n 输入进程名:");

scanf("%s",p-＞name);

printf("\n 输入进程优先数:");

scanf("%d",&p-＞super);

printf("\n 输入进程运行时间:");

scanf("%d",&p-＞ntime);

printf("\n");

p-＞rtime=0;p-＞state='w';

p-＞link=NULL;

sort(); /* 调用sort函数*/

}

}

int space()

{

int l=0; PCB* pr=ready;

while(pr!=NULL)

{

l++;

pr=pr-＞link;

}

return(l);

}

char disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/

{

printf("\n qname \t state \t super \t ndtime \t runtime \n");

printf("|%s\t",pr-＞name);

printf("|%c\t",pr-＞state);

printf("|%d\t",pr-＞super);

printf("|%d\t",pr-＞ntime);

printf("|%d\t",pr-＞rtime);

printf("\n");

}

char check() /* 建立进程查看函数 */

{

PCB* pr;

printf("\n **** 当前正在运行的进程是:%s",p-＞name); /*显示当前运行进程*/

disp(p);

pr=ready;

printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/

while(pr!=NULL)

{

disp(pr);

pr=pr-＞link;

}

}

char destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/

{

printf("\n 进程 [%s] 已完成.\n",p-＞name);

free(p);

}

char running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/

{

(p-＞rtime)++;

if(p-＞rtime==p-＞ntime)

destroy(); /* 调用destroy函数*/

else

{

(p-＞super)--;

p-＞state='w';

sort(); /*调用sort函数*/

}

}

main() /*主函数*/

{

int len,h=0;

char ch;

input();

len=space();

while((len!=0)&&(ready!=NULL))

{

ch=getchar();

h++;

printf("\n The execute number:%d \n",h);

p=ready;

ready=p-＞link;

p-＞link=NULL;

p-＞state='R';

check();

running();

printf("\n 按任一键继续......");

ch=getchar();

}

printf("\n\n 进程已经完成.\n");

ch=getchar();

}

六、运行结果分析

结果分析：根据上述输入的三个进程的信息可以得到：优先级最高的是进程ping,所以最先调度进程ping,它的状态为运行态，需要执行的时间为5。而当前就绪队列状态为：进程xu的优先级比较高，处于就绪队列前面，而进程gui的优先级是三者中最低的，所以处于就绪队列的最后。而此时这两个进程的状态都为就绪态。

结果分析：当进程ping执行了一个时间片之后而它已占用 CPU时间已达到所需要的运行时间，则将它的优先级减1之后，再将三个进程按优先级的大小排列，从中选择优先级大的进程进入运行状态，则该次进入运行态的是进程xu。

按照这种方式一直运行下去 ，直到：

结果分析：当进程ping的CPU占用时间等于它需要的执行时间时，进程ping调度完成。则这时进程调度中还有两个进程：进程gui和进程xu。

结果分析：当调度进程中只剩下进程gui和进程xu时，这时根据进程优先级的大小，进程gui将进入运行态。

结果分析：当进程xu完成调度时，进程调度程序中直剩下进程gui了，这时进程gui将进入运行态，而当前就绪队列将为空。

结果分析：当进程gui的CPU占用时间等于所需要的执行时间时，进程gui调度完成，则这时进程调度中已经没有需要调度的进程了，则整个进程调度完成。

七、总结与体会

该实验利用进程调度中的优先级算法调度进程，开始给每一个进程设定一个优先级数，对于优先级高的进程先调度，优先级低的进程后调度，在调度一个进程时，其他进程将处于就绪态，而正在被调度的进程应处于运行态。

一开始在做这个实验的时候，我感觉大脑一片空白，不知道该从哪里动笔。后来根据书上的内容和从网上下载的资料，我慢慢地了解了大致的流程。通过这次实验，首先加深了我对进程调度方法和功能的认识，其次让我更加深刻地理解了操作系统中进程调度中优先级调度的基本原理。优先级调度算法只是进程调度算法的一种，我们还应依照书本去学习进程调度的其它算法，以便更好地了解进程调度。

 

第二篇：操作系统进程调度实验报告

实验一 进程调度实验

专业：XXXXX

学号：XXXXX

姓名：XXX

实验日期：20XX年XX月XX日

一、实验目的

通过对进程调度算法的模拟加深对进程概念和进程调度算法的理解。

二、实验要求

编写程序实现对5个进程的调度模拟，要求至少采用两种不同的调度算法分别进行模拟调度。

三、实验方法内容

1.算法设计思路

将每个进程抽象成一个控制块PCB， PCB用一个结构体描述。

构建一个进程调度类。将进程调度的各种算法分装在一个类中。类中存在三个容器，一个保存正在或未进入就绪队列的进程，一个保存就绪的进程，另一个保存已完成的进程。还有一个PCB实例。主要保存正在运行的进程。类中其他方法都是围绕这三个容器可以这个运行中的PCB展开。

主要用到的技术是STL中的vector以维护和保存进程容器、就绪容器、完成容器。

当程序启动时，用户可以选择不同的调度算法。然后用户从控制台输入各个进程的信息，这些信息保存到进程容器中。进程信息输入完毕后，就开始了进程调度，每调度一次判断就绪队列是否为空，若为空则系统时间加一个时间片。判断进程容器中是否有新的进程可以加入就绪队列。

2.算法流程图

主程序的框架：

进程调度过程：

3.算法中用到的数据结构

struct fcfs{ //先来先服务算法从这里开始

char name[10];

float arrivetime;

float servicetime;

float starttime;

float finishtime;

float zztime;

float dqzztime;

}; //定义一个结构体，里面包含的有一个进程相关的信息

4.主要的常量变量

vector＜PCB＞m_ProcessQueue;//进程输入队列

vector＜PCB＞m_WaitQueue;//进程就绪队列

vector＜PCB＞m_FinishQueue;//完成队列

vector＜PCB＞::iterator m_iter;//迭代器

PCB m_runProcess;//运行中的进程

int m_ProcessCount;//进程数

float m_RunTime;//运行时间

int m_tagIsRun;//是否在运行标志。表示正在运行，表示没有

float m_TimeSlice;//时间片大小

int m_TimeSliceCount;//指时间片轮转中一次分到的时间片个数

char m_SchedulerAlgorithm;//调度算法

5.主要模块

void PCBInput();//输入进程信息

void PCBSort();//对进程控制块按照优先级排序(采用冒泡排序)

void ProcessSelect();//若当前就绪队列不为空则根据选择的调度算法开始调度。否则，系统时间加.以等待新的进程到来

void PCBDisplay();//打印当前状况下。就绪队列、完成队列、运行中的进程信息

void ProcessRun();//进程运行一次。运行时间加个时间片。并判断进程是否达到完成条件。若是则ProcessStatus='f'.否则为'w';

void ProcessQueueProcess();//查看当前时间下，有无进程加入。若有则把该进程调入就绪队列

void ProcessDispatch();//进程分派，进程执行完成后决定进程该进入哪个队列(就绪、完成)

void TimePast(){ m_RunTime +=m_TimeSlice; ProcessQueueProcess();}//当前系统时间加个时间片，并检查是否有新的进程加入

void SchedulerStatistics();//调度统计，计算周转时间等

void FCFS();//先来先服务

void SJF();//最短进程优先调度

void RR();//简单时间片轮转

void PD();//最高优先数优先

四、实验代码

#include ＜cstdlib＞

#include ＜iostream＞

#include＜iomanip＞

using namespace std;

struct fcfs{ //先来先服务算法从这里开始

char name[10];

float arrivetime;

float servicetime;

float starttime;

float finishtime;

float zztime;

float dqzztime;

}; //定义一个结构体，里面包含的有一个进程相关的信息

fcfs a[100];

void input(fcfs *p,int N)

{

int i;

cout＜＜endl;

printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)\n\n");

for(i=0;i＜=N-1;i++)

{

printf(" 请您输入进程%d的信息:\t",i+1);

scanf("\t\t\t%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);

}

}

void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N)

{

int k;

printf("\n\n调用先来先服务算法以后进程运行的顺序是: ");

printf("%s",p[0].name);

for(k=1;k＜N;k++)

{

printf("--＞%s",p[k].name);

}

cout＜＜endl;

printf("\n 具体进程调度信息:\n");

printf("\t进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间\n");

for(k=0;k＜=N-1;k++)

{

printf("\t%s\t%-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\n",p[k].name,p[k].arrivetime,

p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);

}

getchar(); //此处必须要有这个函数，否则就看不到显示器上面的输出，可以看到的结果只是一闪而过的一个框剪

}

void sort(fcfs *p,int N) //排序

{

for(int i=0;i＜=N-1;i++)

for(int j=0;j＜=i;j++)

if(p[i].arrivetime＜p[j].arrivetime)

{

fcfs temp;

temp=p[i];

p[i]=p[j];

p[j]=temp;

}

}

void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //运行阶段

{

int k;

for(k=0;k＜=N-1;k++)

{

if(k==0)

{

p[k].starttime=p[k].arrivetime;

p[k].finishtime=p[k].arrivetime+p[k].servicetime;}

else

{

p[k].starttime=p[k-1].finishtime;

p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}

}

for(k=0;k＜=N-1;k++)

{

p[k].zztime=p[k].finishtime-p[k].arrivetime;

p[k].dqzztime=p[k].zztime/p[k].servicetime;

}

}

void FCFS(fcfs *p,int N)

{

float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;

sort(p,N);

deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);

Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);

getchar();

} //先来先服务算法到此结束

struct sjf{//最短进程优先调度算法从这里开始

char name[10];

float arrivetime; //到达时间

float servicetime; //运行时间

float starttime; //开始时间

float finishtime; //完成时间

};

sjf a1[100];

void input(sjf *p,int N1)//进程信息输入

{

int i;

cout＜＜endl;

printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)\n");

for(i=0;i＜=N1-1;i++)

{

printf(" 请您输入进程%d的信息:\t",i+1);

scanf("\t\t\t%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);

}

}

void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)//最终结果输出

{

int k;

printf("\n\t调用最短进程优先调度算法以后进程的调度顺序为:");

printf("%s",p[0].name);

for(k=1;k＜N1;k++)

{printf("--＞%s",p[k].name);}

cout＜＜endl;

printf("\n给个进程具体调度信息如下:\n");

printf("\n\t进程名\t到达时间\t运行时间\t开始时间\t完成时间\n");

for(k=0;k＜=N1-1;k++)

{

printf(" \t%s\t %-.2f\t\t %-.2f\t\t %-.2f\t\t %-.2f\t\n",p[k].name,p[k].arrivetime,

p[k].servicetime,p[k].starttime,p[k].finishtime);

}

getchar();

}

void sort(sjf *p,int N1)//排序

{

for(int i=0;i＜=N1-1;i++)

for(int j=0;j＜=i;j++)

if(p[i].arrivetime＜p[j].arrivetime)

{

sjf temp;

temp=p[i];

p[i]=p[j];

p[j]=temp;

}

}

void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//运行阶段

{ int k;

for(k=0;k＜=N1-1;k++)

{

if(k==0)

{

p[k].starttime=p[k].arrivetime;

p[k].finishtime=p[k].arrivetime+float(p[k].servicetime)/60;}

else

{

p[k].starttime=p[k-1].finishtime;

p[k].finishtime=p[k-1].finishtime+float(p[k].servicetime)/60;}

}

}

void sjff(sjf *p,int N1)

{

float arrivetime=0,servicetime=0,starttime=0,finishtime=0;

sort(p,N1);

for(int m=0;m＜N1-1;m++)

{if(m==0)

p[m].finishtime=p[m].arrivetime+float(p[m].servicetime)/60;

else

p[m].finishtime=p[m-1].finishtime+float(p[m].servicetime)/60;

int i=0;

for(int n=m+1;n＜=N1-1;n++)

{

if(p[n].arrivetime＜=p[m].finishtime)

i++;

}

float min=p[m+1].servicetime;

int next=m+1;

for(int k=m+1;k＜m+i;k++)

{

if(p[k+1].servicetime＜min)

{min=p[k+1].servicetime;

next=k+1;}

}

sjf temp;

temp=p[m+1];

p[m+1]=p[next];

p[next]=temp;

}

deal(p,arrivetime,servicetime,starttime,finishtime,N1);

Print(p,arrivetime,servicetime,starttime,finishtime,N1);

getchar();

}//最短进程优先调度算法到这里结束

char menu()//用来输出相关信息的函数

{

char cse1;

while(1)

{

system("cls");

fflush(stdin);

cout＜＜endl;

cout＜＜endl;

cout＜＜"\t"＜＜"|| ＜＜＜＜＜＜＜＜＜＜＜＜欢＜＜＜＜＜＜＜＜＜＜＜ ＞＞＞＞＞＞＞＞＞＞＞＞迎＞＞＞＞＞＞＞＞＞＞＞ ||"＜＜endl ;

cout＜＜"\t"＜＜"|| ||"＜＜endl ;

cout＜＜"\t"＜＜"||"＜＜"\t 实 验 一 进 程 调 度 算 法 实 验"＜＜"\t\t"＜＜"||"＜＜endl;

cout＜＜"\t"＜＜"|| ||"＜＜endl ;

cout＜＜"\t"＜＜"||"＜＜"\t\t 1.先来先服务调度算法 "＜＜"\t\t"＜＜"||"＜＜endl;

cout＜＜"\t"＜＜"|| ||"＜＜endl ;

cout＜＜"\t"＜＜"||"＜＜"\t\t 2.最短进程优先调度算法"＜＜"\t\t"＜＜"||"＜＜endl;

cout＜＜"\t"＜＜"|| ||"＜＜endl ;

cout＜＜"\t"＜＜"|| ＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜＜您＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞＞ ||"＜＜endl ;

cout＜＜endl;

cout＜＜endl;

cout＜＜"\t\t 请输入您的选择（1/2）：";

cse1=getchar();

if(cse1＜'1'||cse1＞'2')

cout＜＜"你的输入有错！"＜＜endl;

else

break;

}

}

int main(int argc, char *argv[])

{

while(1)

{

switch(menu())

{

case '1':

int N;

cout＜＜endl;

cout＜＜endl;

printf("\t\t＜＜---@@@先来先服务调度算法@@@---＞＞\n");

cout＜＜endl;

printf("输入进程数目:");

scanf("%d",&N);

input(a,N);

FCFS(a,N);

case '2':

int N1;

cout＜＜endl;

cout＜＜endl;

printf("\t\t＜＜---@@@最短进程优先调度算法@@@---＞＞\n");

cout＜＜endl;

printf("输入进程数目: ");

scanf("%d",&N1);

input(a1,N1);

sjf *b=a1;

sjf *c=a1;

sjff(b,N1);

getchar();

}

}

system("PAUSE");

return EXIT_SUCCESS;

}

五、实验结果

1.执行结果

2.结果分析

先来先服务调度算法就是根据进程达到的时间为依据，哪一个进程先来那么该进程就会先执行；最短进程优先调度算法则是以每个进程执行所需时间长短为依据，某一个进程执行所需花的时间要短些那么该进程就先执行。以上就是本次进程调度实验的依据。

六、实验总结

通过本次实验了解到算法很重要，又更加明白算法本身可以节约时间，而且不同的函数之间在调用的时候要注意很多的问题。