zuoyediaodu.cpp

这是用VC++编写的实现操作系统中的作业调度算法程序

#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define get(type) (type*)malloc(sizeof(type))   //分配作业空间
#define  NULL 0

typedef struct PCB{
	char name;           //作业名
	char Estate;         //作业状态
	int Arrive_time;     //作业到达时间
	int Finish_time;     //作业完成时间
	int Serve_time;      //作业服务时间
	double Rp;           //高响应优先权
	double Turn_time;    //作业周转时间
	double Carry_time;   //作业带权周转时间
	struct PCB *next;    //指向下一个作业
}PCB;

typedef struct Average{
	double Average_turn_time;//平均周转时间
	double Average_carry_time;//带权平均周转时间
}Average;

void Input(PCB *ready)/*输入函数*/
{
	int i,num;
	printf("\n请输入作业的个数：");    
	scanf("%d",&num);
	PCB *p=NULL,*q=NULL;
	for(i=1;i<=num;i++)
    {
		p=get(PCB);
		printf("\n作业号NO.%d:  ",i);
		printf("\n输入作业名： ");
		scanf("%s",&p->name);
		printf("输入作业到达时间： ");
		scanf("%d",&p->Arrive_time);
		printf("输入作业服务时间： ");
        scanf("%d",&p->Serve_time );
		p->Carry_time=0;
		p->Estate='w';
		p->Finish_time=0;
		p->Rp=0;
		p->Turn_time=0;
		p->next=NULL;
		q=ready;
		while(q->next!=NULL)
		{
			q=q->next;
		}//使到q指到Ready->next的最后一个进程
		q->next=p;
	}
}

void sort(PCB *ready)//按照到达时间排序
{
	PCB *p,*q,*r,*z;
	p=ready;
	while(p->next!=NULL)
	{
		r=p->next;
		q=r->next;
		while(q!=NULL)
		{
			if(r->Arrive_time>q->Arrive_time)
			{
				r=q;
			}
			q=q->next;
		}
		if(ready==p&&p->next!=r)
		{
            z=p;
			while(z->next!=r)
			{
				z=z->next;
			}
			z->next=r->next;
			r->next=ready->next;
			ready->next=r;
		}
		else if(p->next!=r)
		{
			z=p;
			while(z->next!=r)
			{
				z=z->next;
			}
			z->next=r->next;
			r->next=p->next->next;
			p->next=r;	
		}
        p=p->next;
	}
}

void count(PCB *ready,Average *aver)//运行完成一次后给各个变量计算、赋值
{
    PCB *p;
	p=ready->next;
	double all_turn=0,n=0;
	double all_carry=0;
	while(p!=NULL)
	{
		p->Turn_time =p->Finish_time-p->Arrive_time ;
		p->Carry_time =p->Turn_time /p->Serve_time ;
		all_turn =all_turn+p->Turn_time;
		all_carry =all_carry+p->Carry_time;
		n++;
		p=p->next;
	}
	aver->Average_turn_time=all_turn/n;
	aver->Average_carry_time=all_carry/n; 
}

void FCFS(PCB *ready)//先进先服务算法
{
	sort(ready);
	PCB *p,*q;
	p=ready->next;
	p->Finish_time =p->Arrive_time +p->Serve_time ; 
	while(p->next!=NULL)
	{
		q=p->next;
		q->Finish_time=q->Serve_time +p->Finish_time ;
		p=p->next;
	}
}

void SJB(PCB *ready)//短作业优先算法
{
	int nowtime=0;
	PCB *front=NULL,*back=NULL,*p=NULL,*q=NULL,*temp=NULL;
	sort(ready);
	nowtime=ready->next->Arrive_time ;
	p=ready;
	while(p->next!=NULL)
	{
		front=p;
		q=front->next;
		while( q!=NULL && nowtime>=q->Arrive_time)
		{
			q=q->next;
			back=q;
		}
		temp=front->next;
		q=front->next;
		while(q!=back)
		{
			if(temp->Serve_time >q->Serve_time )
			{
				temp=q;
			}
			q=q->next;
		}
		if(front->next!=temp)
		{
			q=front;
			while(q->next!=temp)
			{
				q=q->next;
			}
			q->next=temp->next;
			temp->next=front->next;
			front->next=temp;
		}
		temp->Finish_time =nowtime+temp->Serve_time;
		nowtime=temp->Finish_time ;
		p=p->next;
	}   
}

void HRN(PCB *ready)//响应比高优先算法
{
	int nowtime=0;
	PCB *front=NULL,*back=NULL,*p=NULL,*q=NULL,*temp=NULL;
	sort(ready);
	nowtime=ready->next->Arrive_time ;
	p=ready;
	while(p->next!=NULL)
	{
		front=p;
		q=front->next;
		while( q!=NULL && nowtime>=q->Arrive_time)
		{
			q=q->next;
			back=q;
		}
		temp=front->next;
		q=front->next;
		while(q!=back)
		{
			q->Rp=(q->Serve_time+nowtime-q->Arrive_time)/q->Serve_time ;
			q=q->next;
		}
		q=front->next;
		while(q!=back)
		{
			if(temp->Rp<q->Rp )
			{
				temp=q;
			}
			q=q->next;
		}
		if(front->next!=temp)
		{
			q=front;
			while(q->next!=temp)
			{
				q=q->next;
			}
			q->next=temp->next;
			temp->next=front->next;
			front->next=temp;
		}
		temp->Finish_time =nowtime+temp->Serve_time;
		nowtime=temp->Finish_time ;
		p=p->next;
	}   
}

void Print(PCB *ready,Average *aver)//打印这组作业
{ 
	PCB *p;
	p=ready->next;
	printf("\n作业名    到达时间    服务时间    完成时间       周转时间         带权周转时间\n");
	while(p!=NULL)
	{
		printf("\n   %c",p->name);
		printf("         %d",p->Arrive_time);
		printf("           %d",p->Serve_time);
		printf("           %d",p->Finish_time);
		printf("           %lf",p->Turn_time);
		printf("           %lf",p->Carry_time);
		p=p->next;
	}
	printf("\n平均周期时间： %lf",aver->Average_turn_time);
	printf("\n带权平均周期时间： %lf\n",aver->Average_carry_time);
}


void main()
{
	//int time=0;//作业运行时间标志
	int sign=1;//是否继续运行作业调度的标志"1"表示继续运行/"0"表示结束
	int ch=0;
	printf("\n****************************************************");
    printf("\n**                                                **");
    printf("\n**                  欢迎使用                      **");
    printf("\n**              作业调度应用程序                  **");
    printf("\n**                                                **");
    printf("\n****************************************************\n");
	while(sign)
	{
	        int choice;
	        Average *Aver=NULL;//平均变量
	        PCB *readyline=NULL;//作业链指针
	        readyline=get(PCB); //作业空间分配
	        readyline->next=NULL; 
	        Aver=get(Average);
		Input(readyline);//输入作业
		if(readyline==NULL)break;
		printf("请选择你要的作业调度算法(FCFS=0/SJB=1/HRN=2): ");  //选择作业调度算法
		scanf("%d",&choice);getchar();
		while(choice!=0&&choice!=1&&choice!=2)  //选择调度算法的序号是否正确
		{
			printf("你输入的调度算法号错误，请重新输入正确的调度算法号(FCFS=0/SJB=1/HRN=2): ");
                        scanf("%d",&choice);getchar();
		}
		switch(choice) {
		case 0:
			FCFS(readyline);  //先来先服务算法
			break;
		case 1:
			SJB(readyline);   //短作业调度算法
			break;
		case 2:
			HRN(readyline);  //响应比最高优先调度算法
			break; 
		}
		count(readyline,Aver);   //计算各作业
                Print(readyline,Aver);   //打印作业
		printf("\n是否继续运行作业调度算法(Y=1/N=0):  ");
		scanf("%d",&ch);getchar();
		if(ch==0)
		{
			sign=0;
		}
        
	}
	printf("\n\n谢谢你的使用!请按Enter键继续...");
	getch();
}