Operating system process scheduling experiment report

1. Implement four different and process scheduling algorithms:

First come first service, time slice rotation, priority scheduling and short job priority scheduling algorithms.

2. Understand the concepts of process control block and process queue through experiments.

1. Run the code in the material and observe whether the execution result is correct? Are the functions of each scheduling algorithm perfect? If not, then perfect.

2. Input three job information according to the following table and output the results using different scheduling algorithms.

3. Based on the existing three scheduling algorithms, short job priority scheduling is further realized

ProcessID

arrivetime

servicetime

priority:

1

1

9

2

2

4

6

3

3

6

3

1

Parameter table 2

ProcessID

arrivetime

servicetime

priority:

1

1

2

2

2

7

2

4

3

5

7

1

4

9

1

3

explain:

  1. Get the number of processes from the keyboard in the main program, create a PCB, and call the layout () function to display the selection interface.
  2. Select the corresponding algorithm in the Layout() function and call related functions, such as FCFS(), and finally print.

A scheduling algorithm with N concurrent processes is designed

Process scheduling algorithm: each process is represented by a process control block (PCD). The process control block includes: process ID, priority, arrival time, required running time, etc.

Input program, debug and compile on linux system

Third, design the input data, select different process scheduling algorithms, and print the execution results

IV. fill in the experimental report according to the experimental requirements

-----Paste several call algorithm diagrams and add some simple analysis written by yourself

  1. Select FSFS algorithm results

  1. Result analysis: call the first come first service algorithm. Process 1 comes first, so it executes process 1 first. The processor start time is 1, plus the service time of process 1, it ends at 10; The arrival time of process 2 is 4, which is earlier than that of process 3. Therefore, execute process 2 first, and the time after execution is 16,; Finally, execute No. 3, and the execution completion time is 19

  • 2 - result of calling timesegment algorithm

  • 2 - result analysis: call the time slice rotation algorithm. In this example, set the time slice length to 3. Process 1 comes first and starts at time 1. Execute 3 first, then 2, and then 3. Then 3 has been completed, and then execute 3. At this time, the execution of process 10 and 3 is completed. After that, the time of one time slice will be executed on the 1st and 2nd in turn. The last execution on the 2nd will be 16 and the first will be 19

  • 3 - result of calling priority algorithm

  • 3 - Analysis of experimental results: call the priority non preemptive process algorithm. Process 1 comes first, so execute No. 1 first. Start from 1, execute No. 9, and 10 after the end of No. 1. The priority of process 2 is higher than that of process 3, and 16 after the end of No. 2; Then execute No. 3, and the result is 19

  • 4 - result of calling SJF algorithm

  • 4 - result analysis: call the non preemptive short job priority algorithm. Process 1 comes first and is 10 after execution; Then compare No. 2 and No. 3. The running time of No. 3 is short. Execute No. 3 first and 13 after execution,; Finally, No. 2 was executed, and it was 19

Reference code:

#include<stdio.h>
#include<malloc.h>
#include <stdbool.h>
#include<stdlib.h>
#define max 50

struct PCB
{
	int name;
	int arrivetime; //arrival time
	int servicetime; //service time 
	//int starttime[max]; // start time
    int finishtime; //Completion / end time
    int turntime; //Turnaround time
    int average_turntime; //Weighted turnaround time
	int sign; //Process completion flag
	int remain_time; //Remaining time
	int priority;  //priority
}pcb[max];

void init(int n)  //initialization
{ int i;
	for(i=0;i<n;i++)
	{
		pcb[i].arrivetime=0; 
		pcb[i].servicetime=0; 
	    //pcb[i].starttime=0; 
	    pcb[i].finishtime=0; 
	    pcb[i].turntime=0;
	    pcb[i].average_turntime=0;
		pcb[i].remain_time=0;
		pcb[i].sign=0;
		pcb[i].priority=0;
	}
}
void creat(int n) //Create PCB
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("\n%d:\n input the information of process\n input processID:",i);
		scanf("%d",&pcb[i].name);
		printf("input the arrivetime:");
		scanf("%d",&pcb[i].arrivetime);
		printf("input the servicetime:");
		scanf("%d",&pcb[i].servicetime);
		printf("input the priority:");
		scanf("%d",&pcb[i].priority);
		pcb[i].remain_time=pcb[i].servicetime;  //The remaining initialization time is the service time
	}
}

void FCFS(int n) //First come, first served
{
	int starttime;
	printf("input the start time: \n");
	scanf("%d",&starttime);
	if(starttime>=pcb[1].arrivetime)
	{
		pcb[1].finishtime=pcb[1].servicetime+starttime;
	}
	else
	{
		pcb[1].finishtime=pcb[1].arrivetime+ pcb[1].servicetime;
	}
         int i;
         pcb[1].turntime=pcb[1].finishtime-pcb[1].arrivetime;
	pcb[1].average_turntime=pcb[1].turntime/pcb[1].servicetime;
	for(i=1;i<n;i++)
	{
		if(pcb[i].finishtime>pcb[i+1].arrivetime)
		pcb[i+1].finishtime=pcb[i].finishtime+pcb[i+1].servicetime;
		else
			pcb[i+1].finishtime=pcb[i+1].arrivetime+pcb[i+1].servicetime;
		pcb[i+1].turntime=pcb[i+1].finishtime-pcb[i+1].arrivetime;
		pcb[i+1].average_turntime=pcb[i+1].turntime/pcb[i+1].servicetime;
	}
}

void print_FCFS(int n)
{
		//printf("ProcessID, arrivetime\t Servicetime\t finishtime\t turntime\t:,,%s\t%d\t%d\t%d\t%d\t%d\t"); // Process name, arrival time, service time, completion time, turnaround time, turnaround time
	printf("process ID  arrivetime servicetime finishtime turntime , averageturntime  .\n");
         int i;
	for(i=1;i<=n;i++)
	{
		printf("%d  ,%d  ,%d  ,%d  ,%d  ,%d  ",pcb[i].name  ,pcb[i].arrivetime  ,pcb[i].servicetime  ,pcb[i].finishtime  ,pcb[i].turntime  ,pcb[i].average_turntime);
		printf("\n");
	}

}
void time_segment(int n) //Time slice rotation
{
	int i,j;
	int T;   //Time slice
	int flag=1;   //Whether there are still processes in the ready queue. 0 means no process and 1 means there are processes
	//int time=pcb[0].arrivetime;   // Current time
	int time=0;
	int sum=0;   //Number of processes completed

	//Sort in ascending order according to the arrivetime of each process
	for(i=1;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].arrivetime<pcb[i].arrivetime)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}
	// Newly added
	time=pcb[1].arrivetime;
	    //printf("output the sort result:\n");
		//For (I = 1; I < = n; I + +) / / check whether the sorting is correct
     	//printf("%d\t",pcb[i].name);
	printf("input the slicetime:\n");
	scanf("%d",&T);
	//printf("\n running processID runtime resttime finishtime\n") / / start runtime runtime remaining service time end time

	while(sum<n) 
	{
		flag=0;   //There are no processes in the current ready queue
		int i;
                for(i=1;i<=n;i++)
		{
          //Flag whether the process is complete
			if(pcb[i].sign==1) continue; //Indicates that the process has completed
			else
			{


	           //Incomplete processes take longer than a time slice
				if(pcb[i].remain_time > T)
				{
					flag=1;
				if(time<pcb[i].arrivetime)
				time=pcb[i].arrivetime;
				else{
				time=time+T;
				}	
					
                 // Remaining is the remain ing time
					pcb[i].remain_time=pcb[i].remain_time-T;
          
					//printf("%10d%16d%12d%12d%12d\n",pcb[i].name,time-T,T,pcb[i].remain_time,time);
				}

				//Incomplete processes take less than or equal to a time slice
				else if(pcb[i].remain_time <= T)
				{
					flag=1;  //Join ready queue
					if(time<pcb[i].arrivetime)
				time=pcb[i].arrivetime;
					time=time+pcb[i].remain_time;
					pcb[i].finishtime=time;
                    pcb[i].sign=1;
					//printf("%10d%16d%12d%12d%12d\n",pcb[i].name,time-pcb[i].remain_time,pcb[i].servicetime,0,time); 
		 	        pcb[i].remain_time=0;
				}
				
				if(pcb[i].sign==1) sum++;
			}

		}//for


	if(flag==0&&sum<n)   // There are still processes that have not been executed and are ready to queue before entering 
	{
        int i;
	for(i=1;i<=n;i++)
	if(pcb[i].sign==0) {time=pcb[i].arrivetime;break;}
	}


	}//while

}
void print_time(int n)
{       int i;
	for(i=0;i<n;i++)
	{
	printf("\n processID servicetime finishtime\n");  //Process name service time completion time
	printf("%6d%10d%10d",pcb[i+1].name,pcb[i+1].servicetime,pcb[i+1].finishtime);
	printf("\n");
	}
}

void Priority(int n)
{
	int i,j;
	int time = pcb[1].arrivetime;
	//It is arranged in ascending order according to the arrivetime of each process, and the earliest arriving process is executed first
	for(i=1;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].arrivetime < pcb[i].arrivetime)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}
	
	    //printf("output the sort result: \n"); // Output sorting results
	    //For (I = 1; I < = n; I + +) / / check whether the sorting is correct
     	//printf("%d\t",pcb[i].name);

	printf("\n processID runtime priority fihishtime \n");//Process name service time priority completion time
	//The process that arrives first executes first
	if(i=1)
	{
		pcb[i].finishtime=pcb[i].arrivetime + pcb[i].servicetime;
		time =pcb[i].arrivetime + pcb[i].servicetime;
		printf("%6d%10d%10d%10d",pcb[i].name,pcb[i].servicetime,pcb[i].priority,pcb[i].finishtime);
		printf("\n");
		//Test that the output of the first process is correct
	/*	printf("output the first process:\n");//Output the of the first program
		printf("processID arrivetime finishtime\n");//Time of arrival name
		printf("%4d%8d%8d",pcb[i].name,pcb[i].arrivetime,pcb[i].finishtime);
		printf("\n"); */
		i++; 
	}
	
	

/*
	//The processes are arranged in descending order according to the priority of each process, and the process with the highest priority is executed first
	for(i=2;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].priority > pcb[i].priority)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}
	
	for(i=2;i<=n;i++)
	{
		time = time + pcb[i].servicetime;
		pcb[i].finishtime = time;
		printf("%6d%10d%10d%10d",pcb[i].name,pcb[i].servicetime,pcb[i].priority,pcb[i].finishtime);
		printf("\n");
	}//for
	
*/

int num=2;
	for(i=2;i<=n;i++)
	{
//The processes are arranged in descending order according to the priority of each process, and the process with the highest priority is executed first

	for(i=num;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].priority > pcb[i].priority)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}
//After priority adjustment, judge the process number that arrives first at this time
for(i=num;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].arrivetime< pcb[i].arrivetime)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}




i=num;
  if(time<pcb[i].arrivetime)
{
  time=pcb[i].arrivetime;
pcb[i].finishtime = time+pcb[i].servicetime;
}
else
{
time = time + pcb[i].servicetime;
pcb[i].finishtime = time;
}
printf("%6d%10d%10d%10d",pcb[i].name,pcb[i].servicetime,pcb[i].priority,pcb[i].finishtime);
printf("\n");
time=pcb[i].finishtime;

num++;
	}//for

}//void

void SJF(int n)
{
int i,j;
	int time = pcb[1].arrivetime;
	//It is arranged in ascending order according to the arrivetime of each process, and the earliest arriving process is executed first
	for(i=1;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].arrivetime < pcb[i].arrivetime)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}
	
	    

	printf("\n processID runtime priority fihishtime \n");//Process name service time priority completion time
	//The process that arrives first executes first
	if(i=1)
	{
		pcb[i].finishtime=pcb[i].arrivetime + pcb[i].servicetime;
		time =pcb[i].arrivetime + pcb[i].servicetime;
		printf("%6d%10d%10d%10d",pcb[i].name,pcb[i].servicetime,pcb[i].priority,pcb[i].finishtime);
		printf("\n");
		
	
		i++; 
	}
	
	



int num=2;
	for(i=2;i<=n;i++)
	{
//It is arranged in descending order according to the service time of each process

	for(i=num;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].servicetime < pcb[i].servicetime)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}
	if(pcb[num-1].finishtime<pcb[num].arrivetime)
	{
//After priority adjustment, judge the process number that arrives first at this time
for(i=num;i<=n;i++)
	for(j=i+1;j<=n;j++)  
	{
		if(pcb[j].arrivetime< pcb[i].arrivetime)
		{
			pcb[0]=pcb[j];
			pcb[j]=pcb[i];
			pcb[i]=pcb[0];	
		}
	}
	}




i=num;
  if(time<pcb[i].arrivetime)
{
  time=pcb[i].arrivetime;
pcb[i].finishtime = time+pcb[i].servicetime;
}
else
{
time = time + pcb[i].servicetime;
pcb[i].finishtime = time;
}
printf("%6d%10d%10d%10d",pcb[i].name,pcb[i].servicetime,pcb[i].priority,pcb[i].finishtime);
printf("\n");
time=pcb[i].finishtime;

num++;
	}//for


}

void layout(int n) 
{

while(true)
{
	int ch=0;
	printf("\t\t************schedule algorithm************\n");
	printf("\t\t1.FSFS\n");
	printf("\t\t2.timesegment\n");
	printf("\t\t3.priority\n");
	printf("\t\t4.SJF\n");
	printf("\t\t5 Indicates exit\n");
	printf(" choose the algorithm:\n");
	scanf("%10d",&ch);
	switch(ch)
	{
	case 1:
		    FCFS(n);
		    print_FCFS(n); break;
	case 2:
		    time_segment(n);
		    print_time(n); break;
	case 3:
		    Priority(n); break;
        case 4:
		    SJF(n); break;
	case 5:     exit(0);	    
	default:printf("enter error data!\n");
	//P: For variables of type int, do not add '' after case
	}
}
}

int main()
{ 
	int n;
	printf("input the number of process\n");
	scanf("%d",&n);
	init(n);
	creat(n);
	layout(n);
	//FCFS(n);
	//print_FCFS(n);
	//time_segment(n);
	//print_time(n);
	//Priority(n);
	return 0;
}

Tags: C++ Linux

Posted by Sk8Er_GuY on Tue, 17 May 2022 03:39:12 +0300