CPU Scheduling Algorithm & Its type

0
32

CPU Scheduling Algorithm & Its type

CPU Scheduling

CPU Scheduling एक ऐसी Process है जो एक Process को CPU का प्रयोग करने का Permission देता है | जबकि दूसरी Process का Execution Resource की Unavailability के कारण hold होता है | जिससे CPU को Utilize किया जा सके | CPU Scheduling का Aim (उद्देश्य) System को Efficient, Fast, and Fair बनाना है |

जब भी CPU Idle हो जाता है, तो Operating System Ready Queue में Wait कर Process को Execute करने के लिए Select करता है | Selection Process Short-term Schedular के द्वारा Complete किया जाता है | Schedular Memory में से उन Process को Select करता है जो Execution के लिए तैयार है और उन्हें CPU Allocate करता है |

Type of CPU Scheduling

(i) Non-Preemptive Scheduling

Non-Preemptive Scheduling के अनुसार यदि एक बार CPU को एक Process को Allocate कर दिया गया है, तो वह Process CPU को अपने पास तब तक Hold करके रखती है जब तक उसका Execution Complete नहीं हो जाता है | यह एकमात्र Method है जिसका उपयोग कुछ Hardware Platform पर किया जाता है क्योंकि इसमें Preemptive Scheduling के लिए आवश्यक Special Hardware की आवश्यकता नहीं होती है |

Non-Preemptive Scheduling में CPU Currently Running Process को Disturb नहीं करता है | जबकि यह तब तक Wait करता है जब उस Process का Burst time Complete नहीं हो जाता है उसके बाद ही CPU को अन्य Process को Allocate किया जाता है |

Non-Preemptive Scheduling Algorithm Are – FCFS Scheduling, SJF Scheduling (Shortest Job First), and Priority Scheduling (Non-preemptive version).

(ii) Preemptive Scheduling

इस प्रकार के Scheduling मे Process को CPU Priority के आधार पर Assign किया जाता है | कभी-कभी ऐसे Process को Execute करने की आवश्यकता होती है जोकि Currently Running Process से Higher priority की होती है जिसके लिए पहले से Run हो रही process के Execution को कुछ देर के लिए Block कर दिया जाता है | तथा Higher Priority के Process के Complete Execute हो जाने के बाद उस process को पुनः Execute किया जाता है |

इस प्रकार के Scheduling का उपयोग मुख्यः रूप से तब किया जाता है जब कोई Process या तो Running State से Ready State में या Waiting State से Ready State में बदल जाती है | इसमें Resources limited time के लिए Process को Allocate किया जाता है और फिर वापस ले लिया जाता है और उसके बाद Process को फिर से Ready Queue में रखा जाता है यदि उस Process का Burst Time अभी Execute होना बाकी हो तो | वह Process Ready Queue में तब रहती है जब तक उसे दोबारा Execute होने के लिए CPU Availble न हो |

Preemptive Scheduling Algorithm Are – Round Robin Scheduling, Shortest remaining time First, Priority Scheduling (preemptive version).

Scheduling Algorithm

Decide करने के लिए की CPU को Maximum Utilize करने के लिए किस Process को पहले Execute किया जाये और कौन सी process को last में execute किया जाए | Scheduling Algorithm का प्रयोग किया जाता है जो निम्नलिखित है –

  1. First Come First Serve Scheduling Algorithm (FCFS)
  2. Shortest Job First Scheduling Algorithm (SJF)
  3. Round Robin Scheduling Algorithm (RR)

First Come First Serve Scheduling Algorithm (FCFS)

First Come First Serve Scheduling के अनुसार जो Process पहले आती है उसे पहले Execute किया जाता है | या जो Process CPU के लिए पहले Request करता है उसे CPU पहले Allocate किया जाता है | FIFO Scheduling Queue Data Structure के Rule को Follow करती है जिसके अनुसार जो Process Queue में पहले Add होती वो Process पहले Queue से Remove होती है | इसका प्रयोग Batch Operating System में किया जाता है |

Queue Data Structure का Use करके इसे Programmatically Implement करना आसान है, जहां नए Process को Tail Side से Add करते है और Schedular Head Side के द्वारा Prpocess को Execute करने के लिए Select करता है | FCFS का Perfect Real Time Example Ticket Counter से Ticket खरीदना है |

Important Formula
 Turn Around Time = Completion Time – Arrival Time
 Waiting Time = Turn Around Time – Burst Time
Example
Process Burst Time Order Arrival Time
P1 24 1 0
P2 3 2 0
P3 4 3 0

 

Gantt Chart

 

Program for FCFS
// C program for implementation of FCFS
// scheduling
#include<stdio.h>
// Function to find the waiting time for all
// processes
void findWaitingTime(int processes[], int n,
                        int bt[], int wt[])
{
    // waiting time for first process is 0
    wt[0] = 0;

    // calculating waiting time
    for (int i = 1; i < n ; i++ )
        wt[i] = bt[i-1] + wt[i-1] ;
}

// Function to calculate turn around time
void findTurnAroundTime( int processes[], int n,
                int bt[], int wt[], int tat[])
{
    // calculating turnaround time by adding
    // bt[i] + wt[i]
    for (int i = 0; i < n ; i++)
        tat[i] = bt[i] + wt[i];
}

//Function to calculate average time
void findavgTime( int processes[], int n, int bt[])
{
    int wt[n], tat[n], total_wt = 0, total_tat = 0;

    //Function to find waiting time of all processes
    findWaitingTime(processes, n, bt, wt);

    //Function to find turn around time for all processes
    findTurnAroundTime(processes, n, bt, wt, tat);

    //Display processes along with all details
    printf("Processes Burst time Waiting time Turn around time\n");

    // Calculate total waiting time and total turn
    // around time
    for (int i=0; i<n; i++)
    {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        printf(" %d ",(i+1));
        printf("	 %d ", bt[i] );
        printf("	 %d",wt[i] );
        printf("	 %d\n",tat[i] );
    }
    int s=(float)total_wt / (float)n;
    int t=(float)total_tat / (float)n;
    printf("Average waiting time = %d",s);
    printf("\n");
    printf("Average turn around time = %d ",t);
}

// Driver code
int main()
{
    //process id's
    int processes[] = { 1, 2, 3};
    int n = sizeof processes / sizeof processes[0];

    //Burst time of all processes
    int burst_time[] = {10, 5, 8};

    findavgTime(processes, n, burst_time);
    return 0;
}
// This code is contributed by Shivi_Aggarwal

Output

Processes  Burst time  Waiting time  Turn around time
 1             10            0              10
 2              5           10              15
 3              8           15              23
Average waiting time = 8.33333
Average turn around time = 16

Shortest Job First Scheduling Algorithm (SJF)

SJF Scheduling में Ready Queue में Available Process की List में से सबसे कम Burst Time वाले Process को Execution के लिए आगे Schedule किया जाता है | हालांकि, किसी Process के लिए आवश्यक Burst Time Predict करना मुश्किल है इसीलिए इस Algorithm को System में Implement करना Difficult होता है | Waiting Time को Minimize करने का यह Best Approach है | इसका प्रयोग Mostly Batch Systems में किया जाता है | यह Preemptive and Non-Preemptive दोनों प्रकार का होता है |

(i) Non-Preemptive SJF
Process Burst Time Arrival Time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4
Gantt Chart

 

Program
// C++ program to implement Shortest Job first with Arrival
// Time
#include <iostream>
using namespace std;
int mat[10][6];

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void arrangeArrival(int num, int mat[][6])
{
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num - i - 1; j++) {
            if (mat[j][1] > mat[j + 1][1]) {
                for (int k = 0; k < 5; k++) {
                    swap(mat[j][k], mat[j + 1][k]);
                }
            }
        }
    }
}

void completionTime(int num, int mat[][6])
{
    int temp, val;
    mat[0][3] = mat[0][1] + mat[0][2];
    mat[0][5] = mat[0][3] - mat[0][1];
    mat[0][4] = mat[0][5] - mat[0][2];

    for (int i = 1; i < num; i++) {
        temp = mat[i - 1][3];
        int low = mat[i][2];
        for (int j = i; j < num; j++) {
            if (temp >= mat[j][1] && low >= mat[j][2]) {
                low = mat[j][2];
                val = j;
            }
        }
        mat[val][3] = temp + mat[val][2];
        mat[val][5] = mat[val][3] - mat[val][1];
        mat[val][4] = mat[val][5] - mat[val][2];
        for (int k = 0; k < 6; k++) {
            swap(mat[val][k], mat[i][k]);
        }
    }
}

int main()
{
    int num, temp;

    cout << "Enter number of Process: ";
    cin >> num;

    cout << "...Enter the process ID...\n";
    for (int i = 0; i < num; i++) {
        cout << "...Process " << i + 1 << "...\n";
        cout << "Enter Process Id: ";
        cin >> mat[i][0];
        cout << "Enter Arrival Time: ";
        cin >> mat[i][1];
        cout << "Enter Burst Time: ";
        cin >> mat[i][2];
    }

    cout << "Before Arrange...\n";
    cout << "Process ID\tArrival Time\tBurst Time\n";
    for (int i = 0; i < num; i++) {
        cout << mat[i][0] << "\t\t" << mat[i][1] << "\t\t"
            << mat[i][2] << "\n";
    }

    arrangeArrival(num, mat);
    completionTime(num, mat);
    cout << "Final Result...\n";
    cout << "Process ID\tArrival Time\tBurst Time\tWaiting "
            "Time\tTurnaround Time\n";
    for (int i = 0; i < num; i++) {
        cout << mat[i][0] << "\t\t" << mat[i][1] << "\t\t"
            << mat[i][2] << "\t\t" << mat[i][4] << "\t\t"
            << mat[i][5] << "\n";
    }
}

 

(ii) Preemptive SJF
Process Burst Time Arrival Time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4
Gantt Chart

 

Program
// C++ program to implement Shortest Remaining Time First
// Shortest Remaining Time First (SRTF)

#include <bits/stdc++.h>
using namespace std;

struct Process {
    int pid; // Process ID
    int bt; // Burst Time
    int art; // Arrival Time
};

// Function to find the waiting time for all
// processes
void findWaitingTime(Process proc[], int n,
                                int wt[])
{
    int rt[n];

    // Copy the burst time into rt[]
    for (int i = 0; i < n; i++)
        rt[i] = proc[i].bt;

    int complete = 0, t = 0, minm = INT_MAX;
    int shortest = 0, finish_time;
    bool check = false;

    // Process until all processes gets
    // completed
    while (complete != n) {

        // Find process with minimum
        // remaining time among the
        // processes that arrives till the
        // current time`
        for (int j = 0; j < n; j++) {
            if ((proc[j].art <= t) &&
            (rt[j] < minm) && rt[j] > 0) {
                minm = rt[j];
                shortest = j;
                check = true;
            }
        }

        if (check == false) {
            t++;
            continue;
        }

        // Reduce remaining time by one
        rt[shortest]--;

        // Update minimum
        minm = rt[shortest];
        if (minm == 0)
            minm = INT_MAX;

        // If a process gets completely
        // executed
        if (rt[shortest] == 0) {

            // Increment complete
            complete++;
            check = false;

            // Find finish time of current
            // process
            finish_time = t + 1;

            // Calculate waiting time
            wt[shortest] = finish_time -
                        proc[shortest].bt -
                        proc[shortest].art;

            if (wt[shortest] < 0)
                wt[shortest] = 0;
        }
        // Increment time
        t++;
    }
}

// Function to calculate turn around time
void findTurnAroundTime(Process proc[], int n,
                        int wt[], int tat[])
{
    // calculating turnaround time by adding
    // bt[i] + wt[i]
    for (int i = 0; i < n; i++)
        tat[i] = proc[i].bt + wt[i];
}

// Function to calculate average time
void findavgTime(Process proc[], int n)
{
    int wt[n], tat[n], total_wt = 0,
                    total_tat = 0;

    // Function to find waiting time of all
    // processes
    findWaitingTime(proc, n, wt);

    // Function to find turn around time for
    // all processes
    findTurnAroundTime(proc, n, wt, tat);

    // Display processes along with all
    // details
    cout << "Processes "
        << " Burst time "
        << " Waiting time "
        << " Turn around time\n";

    // Calculate total waiting time and
    // total turnaround time
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << proc[i].pid << "\t\t"
            << proc[i].bt << "\t\t " << wt[i]
            << "\t\t " << tat[i] << endl;
    }

    cout << "\nAverage waiting time = "
        << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "
        << (float)total_tat / (float)n;
}

// Driver code
int main()
{
    Process proc[] = { { 1, 6, 1 }, { 2, 8, 1 },
                    { 3, 7, 2 }, { 4, 3, 3 } };
    int n = sizeof(proc) / sizeof(proc[0]);

    findavgTime(proc, n);
    return 0;
}

Round Robin Scheduling Algorithm (RR)

Round Robin (RR) Scheduling algorithm mainly Time-sharing System के लिए Design किया गया है | यह Algorithm FCFS के समान ही है लेकिन Round Robin में Preemption Allowed होता है | जो System को Process के बीच में Switch करने में सक्षम बनाता है | इसमें प्रत्येक को Execution के लिए Fixed Time Allot किया जाता है जिसे Time-Quantum कहते है |

एक बार दी गयी Time-Quantum के लिए Execute होने के बाद उस process Preempt करके System अन्य Process को Execute करना Start कर देता है | Preempted Processes की States को Save करने के लिए Context Switch का Use किया जाता है | यह Algorithm Simple एवं Easy to Implement है | यह Algorithm Starvation-free क्योंकि सभी Process को CPU का उचित हिस्सा Fixed Time के लिए उपयोग करने के लिए मिलता है | Time Quantum की Length 10 से 100 Millisecond तक होती है |

Example
Process Burst Time
P1 21
P2 3
P3 6
P4 2
Gantt Chart

 

Program
// Program implementation in C++ for Round Robin scheduling 
#include<iostream> 
using namespace std; 

//The Function to find the waiting time for all processes 
void fWaitingTime(int processes[], int n, 
            int bt[], int wt[], int quantum) 
{ 
    // Let us Make a copy of burst times bt[] to store remaining burst times
    
    int rem_bt[n]; 
    for (int i = 0 ; i < n ; i++) 
        rem_bt[i] = bt[i]; 

    int t = 0; // for Current time 

    // Let us keep traverse the processes in the round robin manner until all of them are not done.

    while (1) 
    { 
        bool done = true; 

        //let us Traverse all processes one by one repeatedly 
        for (int i = 0 ; i < n; i++) 
        { 
            // If burst time of a process is greater than 0 then there is a need to process further
            if (rem_bt[i] > 0) 
            { 
                done = false; // indicates there is a pending process 

                if (rem_bt[i] > quantum) 
                { 
                    // By Increasing the value of t it shows how much time a process has been processed 
                    t += quantum; 

                    // Decreasing the burst_time of current process by the quantum
                    rem_bt[i] -= quantum; 
                } 

                // If burst time is smaller than or equal to the quantum then it is Last cycle for this process 
                else
                { 
                    // Increase the value of t to show how much time a process has been processed 
                    t = t + rem_bt[i]; 

                    // Waiting time is current time minus time used by this process.
                    wt[i] = t - bt[i]; 

                    // As the process gets fully executed thus remaining burst time becomes 0.
                    
                    rem_bt[i] = 0; 
                } 
            } 
        } 

        // If all the processes are done 
        if (done == true) 
        break; 
    } 
} 

// Function used to calculate the turn around time 
void fTurnAroundTime(int processes[], int n, 
                        int bt[], int wt[], int tat[]) 
{ 
    // calculating turnaround time by adding bt[i] + wt[i] 
    for (int i = 0; i < n ; i++) 
        tat[i] = bt[i] + wt[i]; 
} 

// Function to calculate the average time 
void findavgTime(int processes[], int n, int bt[], 
                                    int quantum) 
{ 
    int wt[n], tat[n], total_wt = 0, total_tat = 0; 

    // Function to find waiting time of all processes 
    fWaitingTime(processes, n, bt, wt, quantum); 

    // Function to find turn around time for all processes 
    fTurnAroundTime(processes, n, bt, wt, tat); 

    // Display processes along with all details 
    cout << "Processes "<< " Burst time "
        << " Waiting time " << " Turn around time\n"; 

    // Calculate the total waiting time and total turn 
    // around time 
    for (int i=0; i<n; i++) 
    { 
        total_wt = total_wt + wt[i]; 
        total_tat = total_tat + tat[i]; 
        cout << " " << i+1 << "\t\t" << bt[i] <<"\t "
            << wt[i] <<"\t\t " << tat[i] <<endl; 
    } 

    cout << "Average waiting time = "
        << (float)total_wt / (float)n; 
    cout << "\nAverage turn around time = "
        << (float)total_tat / (float)n; 
} 

//Given below is the Driver Code
int main() 
{ 
    // process id's 
    int processes[] = { 1, 2, 3,4}; 
    int x = sizeof processes / sizeof processes[0]; 

    // Burst time of all processes 
    int burst_time[] = {21, 13, 6,12}; 

    // Time quantum 
    int quantum = 2; 
    findavgTime(processes, x, burst_time, quantum); 
    return 0; 
}

Output:

Processes  Burst time  Waiting time  Turn around time
 1            21            31              52
 2            13            32              45
 3             6            16              22
 4            12            30              42
Average waiting time = 27.25
Average turn around time = 4.25

 

Striver SDE Sheet Problem

What is Machine Learning

LEAVE A REPLY

Please enter your comment!
Please enter your name here