chulijidiaodu.cpp

里面有5个关于操作系统进程调度的算法源码

#include<stdio.h>
#include<stdlib.h>
#define RR 2   //时间片大小
/*时间片轮转算法*/
struct pro
{
	char num[20];//进程名
	int arriveTime;
	int burst;//运行时间
	int rt;   //记录进程被运行的次数
	int weight;   //优先数
	struct pro *next;
};
int TOTALTIME;   //记录所有进程的总时间
//函数声明
void insert(struct pro *head,struct pro *s); 
struct pro* searchByAT(struct pro *head,int AT); 
void del(struct pro* p);
int getCount(struct pro *head,int time);
struct pro* searchEnd(struct pro *head);
void move(struct pro *headF,struct pro *headT,int n); 
void run(struct pro *head);
void del(struct pro* p);
int getCount2(struct pro *head,int time);
void insert(struct pro *head,struct pro *s)   //插入节点按时间从小到达建立链表
{
	struct pro *p=searchByAT(head,s->arriveTime);
	s->next=p->next;
	p->next=s;
	return;
}
struct pro* searchByAT(struct pro *head,int AT)   //查找第一个到达时间大于等于AT的节点，返回其前一个指针
{
	struct pro *p,*q;
	p=head;
	q=head->next;
	while(q!=NULL&&q->arriveTime<=AT)
	{
		p=q;
	   q=q->next;
	}
	return p;//指向最小时间点
}
int getCount(struct pro *head,int time)   //察看在time之前到达但未移动到运行队列的进程数量
{
	int count=0;
	struct pro *s,*t;
	s=head;
	t=s->next;
	while(t!=NULL&&t->arriveTime<=time)
	{
		s=t;
		t=t->next; 
	    count++;   //count记录当前时刻到达的进程数
	}
	return count;
}
struct pro* searchEnd(struct pro *head)   //查找并返回循坏队列的尾节点的前一个节点
{
	struct pro *p,*q;
	p=head;
	q=head->next;
	while(q->next!=head)
	{
		p=q;
	    q=q->next;
	}
	return p;
}
void del(struct pro* p)    //删除p的下一个节点
{
	struct pro *tmp;
	tmp=p->next;
	p->next=tmp->next;
	free(tmp);
	return;
}
void move(struct pro *headF,struct pro *headT,int n)   //将headF后的n个节点移动到循环队列headT中
{
	struct pro *r,*s,*t;
	s=headF;
	t=s->next;
	r=t;   //r记录要移动的第一个节点
	while(n>1)
	{
		t=t->next;
		n--;
	}
	s->next=t->next;   //以上完成从原队列中摘除相关节点,r,t分别为第一个和最后一个节点 
	s=searchEnd(headT);
	t->next=s->next;
	s->next=r;
}
void run(struct pro *head)
{
	int time=0;   //记录当前时间
	int newarrive;//新到达进程数
	struct pro *runhead=(struct pro*)malloc(sizeof(struct pro));
	runhead->next=runhead;   //创建新的循环链表，存放当前就绪队列中的进程
	struct pro *p,*q;
	p=runhead;  
	q=p->next;   //q记录当前应当运行的进程
	while(time<=TOTALTIME)
	{
		newarrive=getCount(head,time);
	    if(newarrive>0)
		move(head,runhead,newarrive);   //将head后的newarrive个节点移动到runhead队列中
		if(runhead->next==runhead)   //就绪队列中没有进程
			time++;
		else
			if(q==runhead)
			{
				p=q;
				q=q->next;
			}
			else
			{
				printf("   进程名:%s\n",q->num);
				printf("   到达时间:%d\n",q->arriveTime);
				if(q->rt==1)
					printf("   等待时间:%d\n",time-q->arriveTime);
				else
					printf("   第%d次运行开始时间:%d\n",q->rt,time);
				if(q->burst<=RR)
				{
					time+=q->burst;
					printf("   第%d次运行结束时间:%d\n",q->rt,time);
					printf("   周转时间:%d\n",time-q->arriveTime);
					printf("*********************************************************\n");
					struct pro *tmp=q;
					q=q->next;
					p->next=q;
					free(tmp);
				}
				else   //q->burst>RR
				{
					time+=RR;
					printf("   第%d次运行结束时间:%d\n",q->rt,time);
					printf("*********************************************************\n");
					q->burst-=RR;
					q->rt++;
					p=q;
					q=q->next;
				}
			}
	}
}
/*短作业优先算法*/
int getCount2(struct pro *head,int time)    //察看当前就绪队列中的进程数
{
	int count=0;
	struct pro *p,*q;
	p=head;
	q=p->next;
	while(q!=NULL&&q->arriveTime<=time)
	{
		count++;
		p=q;
		q=q->next;
	}
	return count;
}
struct pro* SJF(struct pro *head,int count)    //在头节点后的count个节点中选择burst最小的，返回其前一个节点的指针
{
	int min;
	struct pro *p,*q,*flag;
	p=head;
	q=p->next;
	min=q->burst;
	flag=p;    //flag记录返回指针
	while(count>0)
	{
		if(q->burst<min)
		{
			min=q->burst;
			flag=p;
	    }
		count--;
		p=q;
		q=q->next;
	}
	return flag;
}
void run2(struct pro *head)    //按短作业优先算法调度进程，并输出其运行情况
{
	int time=0,count;
	struct pro *s,*t;
	while(head->next!=NULL)
	{
		count=getCount2(head,time);
		if(count==0)    //如果当前就绪队列中没有进程，时间自增
		time++;
		else 
			if(count==1)    //如果就绪队列中只有1个进程，则必定是第一个节点
			{
				t=head;
				s=t->next;
				printf("   进程名:%s\n",s->num);
				printf("   到达时间:%d\n",s->arriveTime);
				printf("   运行开始时间:%d\n",time);
				printf("   等待时间:%d\n",time-s->arriveTime);
				time+=s->burst;
				printf("   运行结束时间:%d\n",time);
				printf("   周转时间:%d\n",time-s->arriveTime);
				printf("******************************************************\n");
				del(t);
			}
			else    //如果就绪队列中的进程数>=2，则在head后的count个节点中进行短作业优先调度
			{
				t=SJF(head,count);
				s=t->next;
				printf("   进程名:%s\n",s->num);
				printf("   到达时间:%d\n",s->arriveTime);
				printf("   运行开始时间:%d\n",time);
				printf("   等待时间:%d\n",time-s->arriveTime);
				time+=s->burst;
				printf("   运行结束时间:%d\n",time);
				printf("   周转时间:%d\n",time-s->arriveTime);
				printf("******************************************************\n");
				del(t);
			}
	}
}
/*优先级计算法*/
struct pro* youxian(struct pro *head,int count)   //在头节点后的count个节点中选择weight最小的，返回其前一个节点的指针
{
	int min;
	struct pro *p,*q,*flag;
	p=head;
	q=p->next;
	min=q->weight;
	flag=p;   //flag记录返回指针
	while(count>0)
	{
		if(q->weight<min)
		{
			min=q->weight;
			flag=p;
		}
		count--;
		p=q;
		q=q->next;
	}
	return flag;
}
void run3(struct pro *head)   //按优先级算法调度进程，并输出其运行情况
{
	int time=0,count;
	struct pro *s,*t;
	while(head->next!=NULL)
	{
		count=getCount2(head,time);
		if(count==0)   //如果当前就绪队列中没有进程，时间自增
			time++;
		else if(count==1)   //如果就绪队列中只有1个进程，则必定是第一个节点
		{
			t=head;
			s=t->next;
			printf("   进程名:%s\n",s->num);
			printf("   到达时间:%d\n",s->arriveTime);
			printf("   运行开始时间:%d\n",time);
			printf("   等待时间:%d\n",time-s->arriveTime);
			time+=s->burst;
			printf("   运行结束时间:%d\n",time);
			printf("   周转时间:%d\n",time-s->arriveTime);
			printf("******************************************************\n");
			del(t);
		}
		else   //如果就绪队列中的进程数>=2，则在head后的count个节点中进行短作业优先调度
		{
			t=youxian(head,count);
			s=t->next;
			printf("   进程名:%s\n",s->num);
			printf("   到达时间:%d\n",s->arriveTime);
			printf("   运行开始时间:%d\n",time);
			printf("   等待时间:%d\n",time-s->arriveTime);
			time+=s->burst;
			printf("   运行结束时间:%d\n",time);
		    printf("   周转时间:%d\n",time-s->arriveTime);
			printf("******************************************************\n");
			del(t);
		}
	}
}
void main()
{  	
	char ch;
    ch='y';
	printf("                    欢迎使用处理机调度测试        \n");
	while(ch=='Y'||ch=='y')
	{
	int num,m;     //定义进程数
	printf("   请输入创建进程数:");
	scanf("%d",&num);
	if(num<=0)
	{
		printf("   输入错误!请重新输入大于0的正整数 !\n");
	}
	else
	{
	struct pro* head=(struct pro*)malloc(sizeof(struct pro));//创建链表
	head->next=NULL;  
	struct pro* s;
	TOTALTIME=0;
	for(int i=0;i<num;i++)
	{
		s=(struct pro*)malloc(sizeof(struct pro));
	    printf("   请输入进程名:   ");
	    scanf("%s",&(s->num));
    j:  printf("   请输入到达时间:   ");
	    scanf("%d",&(s->arriveTime));
		if(s->arriveTime<0)
		{
			printf("   输入错误!请重新输入大于0的正整数 !\n");
			goto j;
		}
    k:  printf("   请输入运行时间:   ");
	    scanf("%d",&(s->burst));
		if(s->burst<0)
		{
			printf("   输入错误!请重新输入大于0的正整数 !\n");
			goto k;
		}
    l:  printf("   请输入优先数:   ");
		scanf("%d",&(s->weight));
		if(s->weight<0)
		{
			printf("   输入错误!请重新输入大于0的正整数 !\n");
			goto l;
		}
	    TOTALTIME+=s->burst;   //计算总时间
	    s->rt=1;   //rt的初始值为1
	    s->next=NULL;
		insert(head,s);
	}
		printf("******************************************************\n");
		printf("   处理机调度方式如下:\n");
		printf("******************************************************\n");
		printf("\n   1.时间片轮转法\n   2.短作业优先法\n   3.优先级计算法\n   4.退出！\n");
		printf("   请选择处理机调度方式:");
  x:	scanf("%d",&m);
		if(m<1||m>4)
		{
			printf("   输入错误!请重新输入 !\n");
			goto x;
		}
		printf("******************************************************\n");
		switch(m)
		{
		case 1:
			{
				printf("                         时间片轮转法\n");
				printf("                         当前时间片大小为:%d\n",RR);
				printf("******************************************************\n");
				run(head);
				break;
			};
		case 2:
			{
				printf("                         短作业优先算法\n");
				printf("******************************************************\n");
				run2(head);
			break;};
		case 3:
			{
				printf("                          优先级算法\n");
				printf("******************************************************\n");
			    run3(head);
			    break;
			};
		case 4:exit(0);
		}
		printf("   是否继续? 是:Y/y; 否:任意键!");
		scanf("%s",&ch);
			printf("******************************************************\n");         
	}
	}
}