CPU scheduling algorithms

Introduction

CPU scheduling is a pivotal aspect of operating systems, orchestrating the sequence in which various processes are executed by the CPU. This optimization process categorizes into two primary types: Preemptive and non-preemptive scheduling. However, before delving into these classifications, it's essential to grasp the concept of the ready state. The ready state signifies a phase where a process is prepared for CPU execution and resides in the RAM, eagerly awaiting its turn for processing.

Preemptive scheduling allows a running process to yield the CPU and return to the ready state during execution. For example, in the round-robin approach, each process is allocated a fixed time quantum, after which it gracefully relinquishes control to the next process in line. This cyclic nature of processing ensures fairness and responsiveness in multitasking environments. Conversely, non-preemptive scheduling dictates that once a process begins execution, it continues uninterruptedly until completion before the CPU proceeds to the next process in the queue. Prominent examples of non-preemptive scheduling include the first-come, first-served (FCFS) and shortest job first (SJF) algorithms.

To thoroughly comprehend scheduling algorithms, it's crucial to familiarize oneself with several fundamental terms:

• Arrival Time: The moment a process enters the ready state.

• Burst Time: The duration required by a process for CPU processing.

• Completion Time: When a process finishes its execution.

• Turnaround Time: The interval between completion and arrival time (Completion - Arrival).

• Waiting Time: The duration a process remains in the ready state before execution (Turnaround - Burst).

• Response Time: The time when a process first interacts with the CPU, subtracted from the arrival time.

First Come First Serve (FCFS) Algorithm:

FCFS is the most straightforward scheduling algorithm, initiating with the first process and proceeding sequentially through to the last. Widely adopted in operating systems, it prioritizes the earliest arriving processes.

int main(){
    int arrT[20],burstT[20];
    int waitT[20],turnT[20];
    float avgWaitT=0,avgTurnT=0;
    int pid[20];
    int p;
    waitT[0]=0;
    printf("Enter the number of process: ");
    scanf("%d",&p);
    printf("Enter the burst and arrival time for each\n");
    for(int i=0;i<p;i++){
        printf("%d:",i+1);
        scanf("%d %d",&burstT[i],&arrT[i]);
        pid[i]=i+1;
    }
    //sorting the arrival time in ascending order    
    for(int i=0;i<p;i++){
        for(int j=0;j<p-i-1;j++){
            if(arrT[j]>arrT[j+1]){
                int temp=arrT[j];
                arrT[j+1]=arrT[j];
                arrT[j]=temp;
                temp=pid[j];
                pid[j+1]=pid[j];
                pid[j]=temp;
                temp=burstT[j];
                burstT[j+1]=burstT[j];
                burstT[j]=temp;
            }
        }
    }
    // waiting time is the time waited in ready state before execution
    for(int i=1;i<p;i++){
        waitT[i]=waitT[i-1]+burstT[i-1];
    }
    // turnaround time is the total time in the ready state
    for(int i=0;i<p;i++){
        turnT[i]=waitT[i]+burstT[i];
    }
    printf("The sorted burst time and arrival time: \nPID\tArrival Time\tBurst Time\tWait Time\tTurn Around Time\n");
    for(int i=0;i<p;i++){
        printf("%d\t%d\t\t%d\t\t%d\t\t%d\n",pid[i],arrT[i],burstT[i],waitT[i],turnT[i]);
    }
}

Shortest Job First (SJF) Algorithm:

SJF selects processes with the shortest burst time for execution, thereby minimizing the overall waiting time. In cases of equal burst times, it prioritizes the process with the earliest arrival time. Should a tie persist, the process with the smallest process number is chosen, ensuring determinism in process selection.

int main(){
    int burstT[20],arrT[20],turnT[20],waitT[20],pid[20];
    int p,avgT=0,avgW=0;
    waitT[0]=0;
    printf("Enter the number of processes: ");
    scanf("%d",&p);
    for(int i=0;i<p;i++){
        printf("%d: ",i+1);
        scanf("%d %d",&arrT[i],&burstT[i]);
        pid[i]=i+1;
    }
    // here the burst time is sorted in order, incase of equal burst time, the one with the lower process id will be executed first.
    for(int i=0;i<p;i++){
        for(int j=0;j<p-i-1;j++){
            if(burstT[j]>burstT[j+1]){
                int temp=burstT[j];
                burstT[j+1]=burstT[j];
                burstT[j]=temp;
                temp=arrT[j];
                arrT[j+1]=arrT[j];
                arrT[j]=temp;
                temp=pid[j];
                pid[j+1]=pid[j];
                pid[j]=temp;
            }
        }
    }
    for (int i = 1; i < p; i++)
    {
        waitT[i]=waitT[i-1]+burstT[i-1];
    }
    for (int i = 0; i < p; i++)
    {
        turnT[i]=waitT[i]+burstT[i];
        avgT+=turnT[i];
        avgW+=waitT[i];
    }
    printf("SJF scheduling algorithm\nPID\tArrival Time\tBurst Time\tWaiting Time\tTurn around Time\n");
    for (int i = 0; i < p; i++)
    {
        printf("%d\t%d\t\t%d\t\t%d\t\t%d\n",pid[i],arrT[i],burstT[i],waitT[i],turnT[i]);
    }
    printf("Average waiting time: %d\nAverage turn around time: %d\n",avgW,avgT);
}

Shortest Remaining Time First (SRTF) Algorithm:

Similar to SJF, SRTF is preemptive, dynamically allocating time slices to processes based on burst time, arrival time, and process number. This dynamic adjustment ensures optimal resource utilization and responsiveness in dynamic workloads.

struct Process{
    int pid;
    int arrT;
    int waitT;
    int burstT;
    int turnT;
    int compT;
    int remain;
};

int main(){
    struct Process processes[20];
    int p;
    int count=0;
    int time=0;
    int smallest=0;
    float wait_time;
    float turnaround_time;
    int totTime=0;
    printf("Enter the number of processes: ");
    scanf("%d",&p);
    printf("Enter the arrival and burst time\n");
    for (int i = 0; i < p; i++)
    {
        printf("%d: ",i+1);
        scanf("%d %d",&processes[i].arrT,&processes[i].burstT);
        processes[i].remain=processes[i].burstT;
        totTime+=processes[i].burstT;
        // finding the smallest arrival index and time
        if (processes[i].arrT<processes[smallest].arrT)
        {
            smallest=i;
            time=processes[smallest].arrT;
        }
        processes[i].pid=i+1;
    }
    // to track process is complete or not
    int flag=0;
    // to give the last process having the largest time
    processes[19].remain=1000;

    for (time = time; count!=p; time++)
    {
        smallest=19;
        for (int i = 0; i < p; i++)
        {
            if (processes[i].arrT<=time && processes[i].remain<processes[smallest].remain && processes[i].remain>0)
            {
                smallest=i;
                printf("%d%d\n",smallest,processes[smallest].remain);
            }
        }
        if (processes[smallest].remain>0)   
        {
            processes[smallest].remain-=1;
            if (processes[smallest].remain==0)
            {
                flag=1;
            }
        }
        if(processes[smallest].remain==0 && flag==1){
            count++;
            // updating the completion time
            processes[smallest].compT=time+1;
            processes[smallest].turnT=processes[smallest].compT-processes[smallest].arrT;
            processes[smallest].waitT=processes[smallest].turnT-processes[smallest].burstT;
            wait_time+=processes[smallest].waitT;
            turnaround_time+=processes[smallest].turnT;
            flag=0;
        } 
    }
    printf("Si No:\tArrival Time\tBurst Time\tWaiting time\tTurn Around Time\n");
    for(int i=0;i<p;i++){
        printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",processes[i].pid,processes[i].arrT,processes[i].burstT,processes[i].waitT,processes[i].turnT);
    }
    printf("\n\nAverage Waiting Time:\t%f\n", wait_time/(float)p);
    printf("Average Turnaround Time:\t%f\n", turnaround_time/(float)p);
    return 0;
}

Round Robin Algorithm:

In the round-robin algorithm, each process receives a fixed time quantum for execution before yielding to the next. This approach typically involves two queues: the ready queue and the running queue. Round-robin scheduling strikes a balance between fairness and throughput, ensuring that each process gets a fair share of CPU time while preventing starvation and ensuring timely responsiveness.

int main(){
    int burstT[20],burstT2[20],waitT[20],turnT[20],pid[20];
    int p;
    int timeQ,turn=0;
    float avgTurnT=0,avgWaitT=0;
    int count=0;
    waitT[0]=0;
    printf("Enter the number of process: ");
    scanf("%d",&p);
    printf("Enter time quantume: ");
    scanf("%d",&timeQ);
    printf("Enter the burst time of %d processes: ",p);
    for (int i = 0; i < p; i++)
    {
        printf("%d: ",i+1);
        scanf("%d",&burstT[i]);
        burstT2[i]=burstT[i];
        pid[i]=i;
    }
    for (int i = 0; i < p; i++)
    {
        waitT[i]=0;
        turnT[i]=0;
    }
    for (;;)
    {
        count=0;
        for (int i = 0; i < p; i++)
        {
            if (burstT2[i]<=0)
            {
                count++;
                continue;
            }
            if (timeQ>burstT2[i])
            {
                turnT[i]=burstT2[i]+turn;
                turn+=burstT2[i];
                burstT2[i]=0;
            }
            else{
                turnT[i]=timeQ+turn;
                burstT2[i]=burstT2[i]-timeQ;
                turn+=timeQ;
            }
        }
        if (count==p)
        {
            break;
        }
    }
    for (int i = 0; i < p; i++)
    {
        waitT[i]=turnT[i]-burstT[i];
        avgWaitT+=waitT[i];
        avgTurnT+=turnT[i];
    }
    printf("Si No:\tBurst Time\tWaiting time\tTurnAround Time\n");
    for(int i=0;i<p;i++){
        printf("%d\t%d\t\t%d\t\t%d\n",pid[i]+1,burstT[i],waitT[i],turnT[i]);     
    }
    printf("Avgerage Waiting Time: %f \n Average Turnaround Time: %f\n",avgWaitT/p,avgTurnT/p);
}