Time slice rotation method (C language)

  1. Experiment purpose and requirements
    Topic 1: Design a program to realize processor scheduling according to the time
    slice rotation method
    A process control block (PCB) is represented. The format of the process control block is shown in the following table, and the parameters have the same meaning.

Process Name
Link Pointer
Arrival Time
Estimated Running Time
Process Status

(2) Arrange a circular queue according to the order in which the processes arrive, and set a queue head pointer to point to the first address of the first arriving process. In addition, a current running process pointer is set to point to the currently running process.
(3) When executing processor scheduling, first select the first process at the head of the team to run.
(4) Since this topic is a simulation experiment, the selected process does not actually start running, but only performs the following operations: 1) The estimated running time is reduced by 1;
2) The name of the currently running process is output.
Use these two operations to simulate a run of the process.
(5) After the process runs once, the subsequent scheduling will move the current pointer down one position in turn to point to the next process, that is, adjust the current running pointer to point to the process pointed to by the link pointer of the process to indicate that the process should be run, and also Determine whether the remaining running time of the process is 0. If it is not 0, wait for the next round of running. If the remaining running time of the process is 0, set the status of the process to completion status “C” and exit circular queue.
(6) If the ready queue is not empty, repeat the above steps (4) and (5) until all processes have run out.
(7) In the designed scheduler, display or print statements should be included in order to display or print the name of each selected process and the changes in the queue after running it once.

Second, the data structure and main symbols used in the program
(1), process structure, the variables of the structure are process name (PCBName), process arrival time (arriveTime), process running time (runTime), process status (status) . And the process information is stored with a structure array pcb[PCBNum].

typedef  struct { //Process structure 
    char PCBName; //Process name 
    int arriveTime; //Process arrival time 
    int runTime; //Process running time 
    char status; //Process status
}PCB;
pcb[PCBNum]; //Create a process structure array

(2) I used the chain queue to store the ready queue, so I created a node structure QueueNode and a chain queue structure LinkQueue. The variables in the node structure have a PCB structure data, a pointer next to the next node; the variables in the chain queue structure have a pointer front to the head of the queue, and a pointer to the rear of the queue, indicating the queue Length of integer data Q_size.

typedef  struct  QueueNode //Define a node   
{
    PCB data;
    struct QueueNode *next;
}QueueNode;

typedef  struct { //Chained queue 
    QueueNode *front; //Queue head pointer 
    QueueNode *rear; //Queue tail pointer 
    int Q_size; //Number of elements in the queue 
}LinkQueue;

(3) Description of main symbols:
The variable pcb1 of PCB type is used to save the process that is dequeued after one execution. tail.

PCB pcb1; // used to save the dequeuing element

MAX means infinity, which is used to prevent program errors caused by enqueuing pcb1 without data when the program runs for the first time, and also to prevent the program from being enqueued again after the program is executed.

# define MAX 99999 //means infinity

The integer variable n is used to indicate the number of loops of the loop body for judging whether there is a process arriving at this moment, the integer variable PCBNum indicates the number of processes, and the integer variable m is used to determine when to exit the time loop, that is, when all the processes are executed.

int n= 0 ; //Indicates the number of cycles 
    int PCBNum=(rand()% 4 )+ 3 ; //The number of processes is initialized to 3-6 
    int m=PCBNum; //Used to determine when to exit the time loop

  1. Program flow chart and source program with comments
    Program flow chart:

Source code:

# include <stdio.h>
 # include <stdlib.h>
 # include <time.h>
 # define MAX 99999 //Indicates infinity

typedef  struct { //Process structure 
    char PCBName; //Process name 
    int arriveTime; //Process arrival time 
    int runTime; //Process running time 
    char status; //Process status
}PCB;

typedef  struct  QueueNode //Define a node   
{
    PCB data;
    struct QueueNode *next;
}QueueNode;

typedef  struct { //Chained queue 
    QueueNode *front; //Queue head pointer 
    QueueNode *rear; //Queue tail pointer 
    int Q_size; //Number of elements in the queue
}LinkQueue;

void  init (PCB a[], int n) { //initialization process 
    char name= 'A' ;
     for ( int i= 0 ;i<n;i++){
        a[i].PCBName=name; //Process name 
        a[i].arriveTime=rand()% 8 ; //Process arrival time is initialized to 0-7 
        a[i].runTime=(rand()% 4 ) + 2 ; //The process running time is initialized to 2-5 
        a[i].status= 'R' ; //The process status is initialized to the ready state "Reader"
        name++;
    }
}

void  sort (PCB c[], int n) { //Sort by process arrival time (bubble sort)
    PCB temp;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(c[j].arriveTime>c[j+1].arriveTime){
                temp=c[j];
                c[j]=c[j+ 1 ];
                c[j+1]=temp;
            }
        }
    }
}

void  show (PCB b[], int n) { //Output process information 
    printf ( "Process information:\n" );
     printf ( "Process name\tProcess arrival time\tProcess running time\tProcess status\n" );
     for ( int i= 0 ;i<n;i++){
         printf ( " %c\t\t %d\t\t %d\t\t %c" ,b[i].PCBName,b[ i].arriveTime,b[i].runTime,b[i].status);
         printf ( "\n" );
    }
    printf ( "************************Start execution ******************** ********\n" );
}

void  InitQueue (LinkQueue *Q) { //Construct an empty queue 
    Q->front=Q->rear= NULL ;
    Q->Q_size=0;
}

void  EnQueue (LinkQueue*Q,PCB data) { // 
    Enqueue QueueNode *newNode1=(QueueNode*) malloc ( sizeof (QueueNode)); //Allocate node space for enqueued elements
    newNode1->data=data;
    newNode1->next= NULL ;
     if (Q->Q_size== 0 ){ //Queue is empty
        Q->front=newNode1;
        Q->rear=newNode1;
        Q->Q_size++; //Queue element +1
    }
    else { //Queue is not empty
        Q->rear->next=newNode1;
        Q->rear=newNode1;
        Q->Q_size++; //Queue element +1
    }
}

void  DeQueue (LinkQueue*Q) { // Dequeue 
    if (Q->Q_size== 0 ){ //Queue is empty 
        exit ( 1 );
    }
    else  if (Q->Q_size== 1 ){ //The queue has only one element 
        Q->front= NULL ;
        Q->rear=NULL;
        Q->Q_size--; //The queue element is reduced by 1
    }
    else{
        QueueNode *q=(QueueNode*) malloc ( sizeof (QueueNode)); //Apply for memory 
        q=Q->front; //q points to the queue head element 
        q->data=Q->front->data; //Save The value of the queue head element 
        Q->front=q->next; //Modify the head pointer 
        Q->Q_size--; //Queue element-1 
        free (q); //Release memory
    }
}

void  DestroyQueue (LinkQueue *Q) { //Destroy the queue 
    if (Q->front!= NULL ){
        Q->rear=Q->front;
        free(Q->front);
        Q->front=Q->rear;
    }
}

void  remove_pcb (PCB e[], int n) { //Remove the process whose running time is 0 in the queue 
    int i= 0 ;
     int j= 0 ;
     for ( int k= 0 ;k<n;k++){
         if ( e[k].runTime != 0 ){
            e[i]=e[j];
            i++;
        }
        j++;
    }
}

void  show_Q (LinkQueue *Q) { // Traverse the ready queue 
    QueueNode *newNode2=(QueueNode*) malloc ( sizeof (QueueNode));
     if (Q->front!= NULL ){
        newNode2=Q->front;
        do {
             printf ( "Process name:%c\tProcess arrival time:%d\tProcess remaining running time:%d\tProcess status:%c\n" ,newNode2->data.PCBName,\
            newNode2->data.arriveTime,newNode2->data.runTime,newNode2->data.status);
            newNode2=newNode2->next;
        }while(newNode2!=NULL);
    }
    else {
         printf ( "No process in ready queue!\n" );
    }
}

void  main () {
    srand(( unsigned  int )time( 0 ));
     int n= 0 ; //Indicates the number of cycles 
    int PCBNum=(rand()% 4 )+ 3 ; //The number of processes is initialized to 3-6 
    int m=PCBNum; //Used to determine when to exit the time loop 
    PCB *pcb=(PCB*) malloc (PCBNum* sizeof (PCB));
    pcb[PCBNum]; //Create a process structure array 
    PCB pcb1; //Use to save the dequeuing element 
    pcb1.arriveTime=MAX; //Initialize the arrival time of pcb1 to infinity to prevent pcb1 from entering the queue when it runs for the first time 
    init( pcb,PCBNum); //Initialize process data 
    sort(pcb,PCBNum); //Sort by process arrival time 
    show(pcb,PCBNum); //Output process information 
    LinkQueue *Q=(LinkQueue*) malloc ( sizeof (LinkQueue) );
    InitQueue(Q); //Initialize the queue 
    for ( int time= 0 ;;time++){ //Indicates that the time increases by 
        n=m; //Update the number of cycles 
        printf ( "\nTime%d:\n" ,time);
         for ( int i= 0 ;i<n;i++){
             if (time==pcb[i].arriveTime){ //A process arrives at the current time 
                EnQueue(Q,pcb[i]); // Enqueue 
                printf ( "Process %c arrives\n" ,pcb[i].PCBName); //Output the name of the executed process
            }  
        }
        if(pcb1.arriveTime!=MAX){
            EnQueue(Q,pcb1); //Re-enqueue the head element
        }
        printf ( "Process status in ready queue:\n" );
        show_Q(Q); //Output the ready queue process information 
        if (Q->Q_size!= 0 ){ //The ready queue is not empty 
            for ( int i= 0 ;i<PCBNum;i++){ //Update the pcb array Process information in 
                if (pcb[i].PCBName==Q->front->data.PCBName){
                    pcb[i].runTime--; //Run time-1 
                    if (pcb[i].runTime== 0 ){
                        pcb[i].status= 'C' ; //The process status is updated to "C" 
                        m--; //The number of processes is reduced by 1
                    }
                    break;
                }
            }
            printf ( "Process %c is executing\n" ,Q->front->data.PCBName);
            Q->front->data.runTime--; //The running time of the executing process is reduced by 1 
            if (Q->front->data.runTime== 0 ){ //The process is executed 
                Q->front->data .status= 'C' ; //Update the process status to "C" 
                printf ( "Process %c has been executed, exit the ready queue\n" ,Q->front->data.PCBName);
                DeQueue(Q); // 
                Dequeue pcb1.arriveTime=MAX; //Update the value in pcb1 to prevent re-entering the queue
            }
            else{
                pcb1=Q->front->data; //Save the head element of the ready queue 
                DeQueue(Q); // Dequeue
            }
            remove_pcb(pcb,n); //Remove the process whose running time is 0 in the process queue 
            if (m<= 0 ){ //The process is all executed 
                printf ( "\nThe process has all been executed!\n" );
                 break ;
            }
        }
        else { //No process arrives 
            printf ( "No process arrives, no process runs\n\n" );
        }
    }
    free(pcb);
    DestroyQueue(Q);
    printf ( "Queue destroyed!\n" );
    system("pause");
}

  1. Execute the program name, and print the initial value and operation result when the program is running.
    The first test:

Leave a Comment

Your email address will not be published. Required fields are marked *