时间片.cpp

包含操作系统原理书籍中所提到的很多方法的实现函数

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

//#include "stdafx.h"


/*按时间片轮转法进行CPU调度*/
/*源程序*/
/*—数据结构定义及符号说明*/
/**/
#define N 20
#include <stdio.h>
#include <conio.h>


typedef struct pcb  /*进程控制块定义*/
{
	char pname[N];     /*————进程名*/
	int runtime;       /*一———运行时间*/
	int arrivetime;    /*一———到达时间*/
	char state;        /*一———进程状态*/
	struct pcb *next;  /*一———链接指针*/
}PCB;

PCB head_input;
PCB head_run;
PCB *pcb_input;

static char R='r',C='c';
unsigned  long current;/*记录系统当前时间的变量*/
void inputprocess();/*————建立进程函数*/
int readyprocess();  /*——建立就序队列函数*/
int readydata();     /*判断进程是否就序函数*/
int runprocess();    /*—运行进程函数*/
FILE *f;
 
/*——定义建立就序队列函数*/
int readyprocess()
{
	while(1)
	{
		if (readydata()==0) /*判断是否就序函数*/
			return 1;
		else
			runprocess();   /*—运行进程函数*/
	}
}

/*定义判断就绪队列是否有进程函数*/
int readydata()
{
	if (head_input.next==NULL)
	{
		if (head_run.next==NULL)
			return 0;
		else
			return 1;
   }

	PCB *p1,*p2,*p3;

	p1 = head_run.next;
	p2 = &head_run;
	while( p1 != NULL)
	{
		p2 = p1;
		p1 = p2->next;  
	}
	p1 = p2;
	p3 = head_input.next;
	p2 = &head_input;
	while( p3 != NULL)
	{
		if(( (unsigned long)p3->arrivetime <= current)&&(p3->state == R))
		{
			printf("Time slice is %8d ( time %4d ); Process %s start,\n",
               current, (current+500)/1000, p3->pname);
			fprintf(f,"Time slice is %8d ( time %4d ); Process %s start,\n",
               current, (current+500)/1000, p3->pname);
			p2->next = p3->next;
			p3->next = p1->next;
			p1->next = p3;
			p3 = p2;
		}
		p2 = p3;
		p3 = p3->next;
	}
	return 1;
}
      
int runprocess()   /*—定义运行进程函数*/

{
	PCB *p1,*p2;
	if (head_run.next == NULL)
	{
		current++;
		return 1;
	}
	else
	{
		p1 = head_run.next;
		p2 = &head_run;
		while( p1 != NULL)
		{
			p1->runtime--;
			current++;
			if(p1->runtime<=0)
			{
			  printf("Time slice is %8d time %4d; Process %s end. \n", current, (current+500)/1000,p1->pname);
			  fprintf(f,"Time slice is %8d time %4d; Process %s end. \n", current, (current+500)/1000,p1->pname);
			  p1->state = C;
			  p2->next = p1->next;
			  delete p1;
			  p1 = NULL;
			}
			else
			{
				p2 = p1;
				p1 = p2->next;
			}
		}
		return 1;
	}
}

/*——定义建立进程函数*/
void inputprocess()
{
	PCB *p1,*p2;
	int num;           /*要建立的进程数*/
	unsigned  long max=0;
	printf("How many processes do you want to run: ");
	fprintf(f,"How many processes do you want to run: ");
	scanf("%d", &num);
	fprintf(f,"%d\n", num);
	p1 = &head_input;
	p2 = p1;
	p1->next = new PCB;
	p1 = p1->next;
	for(int i = 0; i<num; i++)
     { 
		 printf("NO. %3d  process input pname: ",i+1);
		 fprintf(f,"NO. %3d  process input pname: ",i+1);
		 scanf("%s",p1->pname);
		 fprintf(f,"%s\n",p1->pname);
		 printf("                        runtime: ");
		 fprintf(f,"                        runtime: ");
		 scanf("%d",&(p1->runtime));
		 fprintf(f,"%d\n",p1->runtime);
		 printf("                    arrivetime: ");
		 fprintf(f,"                    arrivetime: ");
		 scanf("%d",&(p1->arrivetime));
		 fprintf(f,"%d\n",p1->arrivetime);	
		 p1->runtime = (p1->runtime)*1000;
		 p1->arrivetime = (p1->arrivetime)*1000;
		 p1->state = R;
		 if((unsigned long)( p1->arrivetime) > max)
			 max = p1->arrivetime;
		 p1->next = new PCB;
		 p2=p1; 
		 p1=p1->next;
	 }
	 delete p1;
	 p1 = NULL;
	 p2->next = NULL;
}

/*——定义建立进程函数*/
void inputprocess1()
{
	PCB *p1,*p2;
	int num;           /*要建立的进程数*/
	unsigned  long max = 0;
	printf("How many processes do you want to run: ");
	fprintf(f,"How many processes do you want to run: ");
	scanf("%d", &num);
	fprintf(f,"%d\n", num);
	pcb_input = new PCB;
	p1 = pcb_input;
	for(int i = 0; i<num; i++)
     { 
		 printf("NO. %3d  process input pname: ",i+1);
		 fprintf(f,"NO. %3d  process input pname: ",i+1);
		 scanf("%s",p1->pname);
         fprintf(f,"%s\n",p1->pname);
		 printf("                        runtime: ");
	     fprintf(f,"                        runtime: ");
		 scanf("%d",&(p1->runtime));
		 fprintf(f,"%d\n",p1->runtime);
		 printf("                    arrivetime: ");
		 fprintf(f,"                    arrivetime: ");
		 scanf("%d",&(p1->arrivetime));
		 fprintf(f,"%d\n",p1->arrivetime);
		 //p1->runtime = (p1->runtime);
		 //p1->arrivetime = (p1->arrivetime);
		 p1->runtime = (p1->runtime)*1000;
		 p1->arrivetime = (p1->arrivetime)*1000;
		 p1->state = R;
		 if( i != num-1 )
		 {		 
			 p1->next = new PCB;	
			 p1 = p1->next;
		 }
		 else
		 {
			 p1->next = pcb_input;
		 }
	 }
	 
	
	 p1 = pcb_input;
	 while( p1->next != pcb_input)
	 {
		 printf("process name is %s\n",p1->pname);
		 fprintf(f,"process name is %s\n",p1->pname);
		 p1 = p1->next;
	 }
     printf("process name is %s\n",p1->pname);
	 fprintf(f,"process name is %s\n",p1->pname);
}

void runprocess1()   /*—定义运行进程函数*/
{
	pcb *pre,*cur;
	if( pcb_input == NULL )
		return ;
	else 
	{
		cur = pcb_input;
		pre = cur->next;
		while( pre->next != cur ) // find the last node in the list
		{
			pre = pre->next;
		}
        		
		while( ( cur->runtime >= 0 ) || ( cur->next != cur ) )  
		//while(1)
		// if p1->next != p1 ,it means that there are more than one pcb jobs
		// if p1->next == p1 and p1->runtime <= 0 means all jobs have done;
		{
			if( current < (unsigned long)cur->arrivetime )
			{
				pre = cur;
				cur = cur->next;
			}
			else
			{
				if( current == (unsigned long)cur->arrivetime )
				{
					printf("Time slice is %8d ( time %4d ); Process %s start,\n",
						current, (current+500)/1000, cur->pname);
					fprintf(f,"Time slice is %8d ( time %4d ); Process %s start,\n",
						current, (current+500)/1000, cur->pname);

				}
				cur->runtime--;				
				if( cur->runtime < 0 ) // means the job have ended.
				{
			  
					printf("Time slice is %8d time %4d; Process %s end. \n",
						current, (current+500)/1000,cur->pname);
					fprintf(f,"Time slice is %8d time %4d; Process %s end. \n",
						current, (current+500)/1000,cur->pname);
					
					if( cur == cur->next ) // delete the last job then break;
					{
						delete cur;
						cur = NULL;
						//break;
						return;
					}
					else
					{
						pre->next = cur->next;
						pcb* tmp = cur;
						delete tmp;
						cur = pre->next;
					}                     
				}
				else
				{
					cur->runtime--;	
					pre = cur;
					cur = cur->next;
				}
				
			}
			current++;
		}
	}

}

//TODO set one cycle link to solve the problem

void main()
{  
	f=fopen("result.txt","w");
	printf("\ntime 1=1000 time slice\n");
	fprintf(f,"\ntime 1=1000 time slice\n");
	current = 0;
	inputprocess();
	readyprocess();
	//inputprocess1();
	//runprocess1();
	getch();
	fclose(f);
}


/*  results:

time 1=1000 time slice
How many processes do you want to run: 3
NO.   1  process input pname: pro1
                        runtime: 20
                    arrivetime: 38
NO.   2  process input pname: pro2
                        runtime: 80
                    arrivetime: 90
NO.   3  process input pname: pro3
                        runtime: 40
                    arrivetime: 110
Time slice is    38000 ( time   38 ); Process pro1 start,
Time slice is    58000 time   58; Process pro1 end. 
Time slice is    90000 ( time   90 ); Process pro2 start,
Time slice is   110000 ( time  110 ); Process pro3 start,
Time slice is   190000 time  190; Process pro3 end. 
Time slice is   210000 time  210; Process pro2 end. 
	
	*/