sjf.cpp

模拟先来先服务作业调度 模拟最短作业优先作业调度 模拟响应比高者优先作业调度

// SJF.cpp : Defines the entry point for the console application.
//

#include "dos.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "math.h"
#include "time.h"
#define getpch(type) (type*)malloc(sizeof(type)) 
#define NULL 0 
struct jcb { /* 定义作业控制块jcb */ 
	char outername[10]; //外部标识符
	int  innername; //内部标识符
	char state[10]; //记录三种基本状态
	int arrivetime; //到达时间
	int servetime;  //需要服务时间
	int CPUtime;     //已用CPU时间
	int finishtime;  //完成时间
	int cycletime;   //周转时间
	float weighttime;  //带权周转时间
	bool flag;
	int waittime;//等待时间
	float weight;//优先权(响应比)
	struct jcb* next; 
}*ready=NULL,*block=NULL,*p;//就绪队列,阻塞队列和当前作业
typedef struct jcb JCB;
JCB *first=NULL,fir[3][5];//作业到达时间队列
int blocktime,counting;//时间片中止时间
char how[10];
float avecycletime,aveweighttime;//平均周转时间,平均带权周转时间

void FIFCsort(JCB *pt)//先来先服务
{
	JCB *ptr;
	if((ready==NULL)||(pt->arrivetime<ready->arrivetime))
	{
		pt->next=ready;
		ready=pt;
	}
	else//插入队尾
	{
		ptr=ready;
		while(ptr->next!=NULL)
			ptr=ptr->next;
		ptr->next=pt;
	}
}

void SJFsort(JCB *pt)//设置最短作业优先就绪队列 
{
	JCB *ptr;
	if((ready==NULL)||((pt->servetime-pt->CPUtime)<(ready->servetime-ready->CPUtime)))//最短作业设置在队首为就绪
	{
		pt->next=ready;
		ready=pt;
	}
	else
	{
		ptr=ready;
		while(ptr->next!=NULL)//插入队列中
		{
			if((pt->servetime-pt->CPUtime)<(ptr->next->servetime-ready->CPUtime))
			{
				pt->next=ptr->next;
				ptr->next=pt;
				break;
			}
			ptr=ptr->next;
		}
		if(ptr->next==NULL)//插入队尾
			ptr->next=pt;
	}
}

void HighResponseSort(JCB *pt)
{
	JCB *ptr;
	if((ready==NULL)||(pt->weight > ready->weight))//高响应比优先+先来先服务设置在队首为就绪
	{
		pt->next=ready;
		ready=pt;
	}
	else
	{
		ptr=ready;
		while(ptr->next!=NULL)//插入队列中
		{
			if((pt->weight>ptr->next->weight)||(pt->weight==ptr->next->weight&&pt->arrivetime<ptr->next->arrivetime))
			{
				pt->next=ptr->next;
				ptr->next=pt;
				break;
			}
			ptr=ptr->next;
		}
		if(ptr->next==NULL)//插入队尾
			ptr->next=pt;
	}
}

void ArriveTimeSort(JCB *pt)
{
	JCB *ptr;
	if(pt->servetime==0)
	{
		free(pt);
	}
	else if((first==NULL)||((pt->arrivetime)<(first->arrivetime)))//设置在队首为就绪
	{
		pt->next=first;
		first=pt;
	}
	else
	{
		ptr=first;
		while(ptr->next!=NULL)//插入队列中
		{
			if((pt->arrivetime<ptr->next->arrivetime))
			{
				pt->next=ptr->next;
				ptr->next=pt;
				break;
			}
			ptr=ptr->next;
		}
		if(ptr->next==NULL)//插入队尾
			ptr->next=pt;
	}
}

void DeleteList(JCB *pt)
{
	free(pt);
}

bool detective(char a[],int &x)//将字符型转换成数字型
{
    int len;x=0;
	for(int i=0;a[i]!='\0';i++)
	{
		if(a[i]<'0'||a[i]>'9')//滤去其它字符
			return 0;
	}
	len=i;
	for(int j=len-1;j>=0;j--)//转成整数
	{
		    x+=(a[j]-'0')*(int)pow(10,len-j-1);
	}
	return 1;
}

void ClearList(JCB *pt)//清零
{
	JCB *p=pt;
	while(p!=NULL)
	{
		p->CPUtime=0;p->waittime=0;p->weight=0;
		strcpy(p->state,"Wait"); 
		p->finishtime=0;
		p->cycletime=0;
		p->weighttime=0;
		p=p->next;
	}
}

void CreateProcess() /* 建立作业控制块函数*/ 
{ 
	int i,num=5;char ch[10];char order[10];
	printf("请指定初始化方式(按y自己设定,任意键随机设定):");
	scanf("%s",&order);
	srand(time(0));//种子
	for(i=0;i<num;i++) 
	{ 
		printf("\n %d号作业",i); 
		p=getpch(JCB); 		
		if(order[0]=='y')
		{
			printf("输入作业名:"); 
			scanf("%s",&p->outername); 	
			printf("作业到达时间:");
			loop:scanf("%s",&ch);
	        if(!detective(ch,p->arrivetime))//判断是否输入为数字型
			{
		       printf("请重新输入以1为单位的整型数:"); 
		       goto loop;
			}
			printf("作业需要服务时间:");
			loop1:scanf("%s",&ch);
	        if(!detective(ch,p->servetime))//判断是否输入为数字型
			{
		       printf("请重新输入以1为单位的整型数:"); 
		       goto loop1;
			}
		}
		else
		{
			printf("作业名:");
			p->outername[0]='a'+i;
			p->outername[1]='\0';
			printf("%s\n",p->outername);
			printf("作业到达时间:");
			p->arrivetime=rand()%10;
			printf("%d",p->arrivetime);
			printf("作业需要服务时间:");
			p->servetime=rand()%10;
			printf("%d\n",p->servetime);
		}
		p->innername=i;		
        p->CPUtime=0;p->waittime=0;p->weight=0;
		strcpy(p->state,"Wait"); 
		p->finishtime=0;
		p->cycletime=0;
		p->weighttime=0;
		p->next=NULL; 
		ArriveTimeSort(p);
	} 
} 

void PrintProcessQueue(JCB *pt)
{
	JCB *ptr=pt;
	printf("作业名|到达时间|服务时间|作业状态|响应比|完成时间|周转时间|带权周转时间\n");
	while(ptr!=NULL)
	{ 
		printf("%s",ptr->outername);
		printf("       ");
		printf("%d",ptr->arrivetime); 
		printf("       ");
		printf("%d",ptr->servetime);
		printf("        ");
		printf("%s ",ptr->state);
		printf("%d ",ptr->waittime);
		printf("%f",ptr->weight);
        printf("     %d",ptr->finishtime);
		printf("     %d",ptr->cycletime);
		printf("       %f\n",ptr->weighttime);
		ptr=ptr->next;
	}
}

void SetWeight()//冒泡算法重新调整就绪队列
{
	JCB *ptr=ready,*pt=ready,*p,*q=ready,*pc;
	while(pt!=NULL&&pt->flag!=0)
	{
		pt->flag=0;
		pt=pt->next;
	}
	while(ptr!=NULL)
	{
		if(ptr==ready) 
		{
			if(ptr->flag==0)
			{
				p=ready;
				ready=ptr->next;
				p->next=0;
				p->waittime++;
				p->weight=(float)(p->waittime+p->servetime)/p->servetime;
				p->flag=1;
				pc=first;
				while(pc!=NULL)
				{
					if(pc->innername==p->innername)
					{
						pc->waittime=p->waittime;
						pc->weight=p->weight;
					}
					pc=pc->next;
				}
				HighResponseSort(p);
				ptr=ready;
			}
			else
				q=ptr;ptr=ptr->next;
		}
		else 
		{
			if(q->next!=NULL&&q->next->flag==0)
			{
				p=q->next;
				q->next=q->next->next;
				p->next=0;
				p->waittime++;
				p->weight=(float)(p->waittime+p->servetime)/p->servetime;
				p->flag=1;
				pc=first;
				while(pc!=NULL)
				{
					if(pc->innername==p->innername)
					{
						pc->waittime=p->waittime;
						pc->weight=p->weight;
						break;
					}
					pc=pc->next;
				}
				HighResponseSort(p);
				ptr=ready;				
			}
			else
				q=ptr;ptr=ptr->next;
		}
	}
}

void AttemperProcess(int start,int time,char a)//一个时间片内的作业调度
{
	if(block!=NULL)
	{
		printf("\n... ...作业[%s]唤醒... ...",block->outername);
		p=block;
		switch(a)//进入就绪队列
		{
		case '2':
			FIFCsort(p);
			break;
		case '3':
			SJFsort(p);
			break;
		case '4':
			HighResponseSort(p);
			break;
		default:
			break;
		}		
		strcpy(block->state,"Wait");
		block=NULL;
	}
    JCB *execute=ready;JCB *ptr;
	printf("\n\t->->->->作业[%s]正在调度中... ...\n",execute->outername);
	ready=ready->next;
	if(ready!=NULL&&a=='4')
		SetWeight();
	for(int i=start+1;i<start+time+1;i++)
	{
		printf("\t\t... ...第%d个CPU时钟周期... ...\n",i);
		(execute->CPUtime)++;
		ptr=first;
		while(ptr!=NULL)
		{
			if(ptr->innername==execute->innername)
			{
				ptr->CPUtime=execute->CPUtime;
				break;
			}
			ptr=ptr->next;
		}
		if(execute->CPUtime==execute->servetime)//结束作业
		{
			printf("\n... ...作业[%s]完成... ...",execute->outername);
			execute->finishtime=i;
			printf("完成时间:%d\t",i);
			execute->cycletime=i-execute->arrivetime;
			printf("周转时间:%d\t",execute->cycletime);
			avecycletime+=execute->cycletime;
			execute->weighttime=(float)execute->cycletime/execute->servetime;
			printf("带权周转时间:%f\n",execute->weighttime);
			aveweighttime+=execute->weighttime;
			strcpy(execute->state,"Finish");			
			blocktime=i-start;counting++;
			ptr=first;
			while(ptr!=NULL)
			{
				if(ptr->innername==execute->innername)
				{
					ptr->finishtime=i;
					ptr->cycletime=execute->cycletime;
					ptr->weighttime=execute->weighttime;
					strcpy(ptr->state,"Finish");
					break;
				}
				ptr=ptr->next;
			}
			printf("... ...任意键继续... ...");
			free(execute);
			getch();
			break;
		}	
		if(how[0]=='y')
		for(int delay1=0;delay1<10000;delay1++)
			for(int delay2=0;delay2<20000;delay2++);
	}
	if(i==start+time+1)//进入阻塞状态
	{
		block=getpch(JCB);block=execute;block->next=NULL;
		printf("\n... ...作业[%s]阻塞... ...",block->outername);
		strcpy(block->state,"Block");
		if(how[0]=='y')
		for(int delay1=0;delay1<20000;delay1++)
			for(int delay2=0;delay2<20000;delay2++);
	}
}

void Attemper(int cyctime,char abc)
{
	int time=0,tim;
	JCB *ptr,*q;
	printf("请指定执行方式(按y观察模式,任意键快速执行):");
	scanf("%s",&how);
	system("cls");
	blocktime=time=0;ptr=first;avecycletime=aveweighttime=0;counting=0;	
	tim=first->arrivetime;//准入口
	while(1)//时间片轮转,轮转时间为2
	{
		if(how[0]=='y')
		{
			system("cls");
			printf("\n  作业队列为:\n");
			PrintProcessQueue(first);
			printf("\n  就绪队列为:\n");
			PrintProcessQueue(ready);
		}
		printf("\n------------------------------------------------------------------------");
		while(ptr!=NULL&&time==ptr->arrivetime)
		{
			q=getpch(JCB);
			*q=*ptr;
			ptr=ptr->next;				 
			q->next=0;
			switch(abc)
			{
			case '2':
				FIFCsort(q);
				break;
			case '3':
				SJFsort(q);//进入就绪队列
				break;
			case '4':
				HighResponseSort(q);
				break;
			default:
				break;
			}			
			printf("\n... ...新作业[%s]进入... ...",q->outername);
		}
		if(time<first->arrivetime)
		{
			printf("\n\t\t... ...第%d个CPU时钟周期... ...\n",time+1);
			if(ready!=NULL&&abc=='4')
				SetWeight();
		}
		if(how[0]=='y')
		for(int delay1=0;delay1<10000;delay1++)
			for(int delay2=0;delay2<20000;delay2++);
		if((ready!=NULL||block!=NULL)&&((time-tim)%cyctime==0||blocktime!=cyctime&&blocktime!=0))
		{
			if((blocktime!=cyctime&&blocktime!=0))
				tim+=blocktime;
			blocktime=0;
			AttemperProcess(time,cyctime,abc);					
			if(block==NULL&&ready==NULL&&ptr==NULL)//队列为空
			{
				printf("\n\n!!! !!!所有作业已经完成!!! !!!\n\n");
				avecycletime=avecycletime/counting;
				printf("\t平均周转时间:%f\t",avecycletime);
				aveweighttime=aveweighttime/counting;
				printf("平均带权周转时间:%f\n\n",aveweighttime);
				break;
			}
		}
		else
		{
			if(ready!=NULL&&abc=='4')		
				SetWeight();
		}
		++time;
	}
}

void SaveList(JCB *pt,int n)
{
	JCB *ptr=pt;int i=0;
	while(ptr!=NULL)
	{
		fir[n][i]=*ptr;
		ptr=ptr->next;
		i++;
	}
}

void RestoreList(JCB *pt,int n)
{
	JCB *ptr=pt;int i=0;
	while(ptr!=NULL)
	{
		*ptr=fir[n][i];
		ptr=ptr->next;
		i++;
	}
}

int main(int argc, char* argv[])
{
	char ch[10],order[10];ch[0]='1';int cyctime=2;
	float a[3],b[3];int i;
	printf("\n-----------------------作业调度算法演示程序-----------------------\n");
	printf("\n\t\t制作者是软件2班李建康,谢谢使用!\n\n\n");
	while(1)
	{
		switch(ch[0])
		{
		case '1':
			printf("... ...作业初始化... ...\n");
			if(first!=NULL)
				DeleteList(first);
			first=NULL;
            CreateProcess();
			printf("\n  作业队列为:\n");
			PrintProcessQueue(first);
			for(i=0;i<3;i++)
			{
				a[i]=0;b[i]=0;
			}
			printf("\n... ...任意键继续... ...\n");		    
			getch(); 
			break;
		case '2':
			system("cls");
			printf("\t\t... ...模拟先来先服务作业调度... ...\n\n");						
		    Attemper(cyctime,ch[0]);
			a[0]=avecycletime;b[0]=aveweighttime;
            SaveList(first,0);
			printf("\n... ...任意键继续... ...");
			getch();
			break;
		case '3':
			system("cls");
			printf("\t\t... ...模拟最短作业优先作业调度... ...\n\n");		
		    Attemper(cyctime,ch[0]);
			a[1]=avecycletime;b[1]=aveweighttime;
			SaveList(first,1);
			printf("\n... ...任意键继续... ...");		    
			getch();
			break;
		case '4':
			system("cls");
			printf("\t\t... ...模拟高响应比优先作业调度... ...\n\n");			
		    Attemper(cyctime,ch[0]);
			a[2]=avecycletime;b[2]=aveweighttime;
			SaveList(first,2);
			printf("\n... ...任意键继续... ...");		    
			getch();
			break;
		case '5':
			system("cls");
			printf("... ...算法分析... ...\n");
			printf("\n  先来先服务作业队列为:\n");
			RestoreList(first,0);
			PrintProcessQueue(first);
			printf("  最短作业优先作业队列为:\n");
			RestoreList(first,1);
			PrintProcessQueue(fir[1]);
			printf("  高响应比优先作业队列为:\n");
			RestoreList(first,2);
			PrintProcessQueue(fir[2]);
			printf("------------------------------------------------------------------------");
			printf("\t\t\t先来先服务\t最短作业优先\t高响应比优先\n");
			printf("平均周转时间:\t\t%f\t%f\t%f\n",a[0],a[1],a[2]);
			printf("平均带权周转时间:\t%f\t%f\t%f",b[0],b[1],b[2]);
			printf("\n... ...任意键继续... ...");		    
			getch();
			break;
		case '6':
			printf("\n... ...重新设置时间片的长度:");
            loop2:scanf("%s",&order);
	        if(!detective(order,cyctime))//判断是否输入为数字型
			{
		        printf("请重新输入以1为单位的整型数:"); 
		        goto loop2;
			}
			printf("\n... ...任意键继续... ...");
			if(cyctime==0)
				cyctime=1;
			getch();
	        break;
		case '7':
			DeleteList(ready);
			DeleteList(first);
			DeleteList(block);
			return 0;
			break;
		default:
			break;
		}
		if(first==NULL)
		{
			system("cls");
			continue;
		}
		ClearList(first);
		system("cls");
		printf("\n-----------------------作业调度算法演示程序-----------------------\n");
		printf("\n\t\t制作者是软件2班李建康,谢谢使用!\n\n");
		printf("\n\t\t1.重新初始化作业");
		printf("\n\t\t2.模拟先来先服务作业调度");
		printf("\n\t\t3.模拟最短作业优先作业调度");
		printf("\n\t\t4.模拟响应比高者优先作业调度");
		printf("\n\t\t5.算法分析");
		printf("\n\t\t6.重新设置时间片的长度(默认为2)");
		printf("\n\t\t7.结束演示\n");
        printf("您的选择是:");
		scanf("%s",&ch);
	}
	return 1;
}