Priority Scheduling is a CPU scheduling algorithm in which the CPU performs the task having higher priority at first. If two processes have the same priority then scheduling is done on FCFS basis (first come first serve). Priority Scheduling is of two types : Preemptive and Non-Preemptive.
Preemptive: In this case, resources can be voluntarily snatched.
Non-Preemptive: In this type, if a process is once started, it will execute completely i.e resources cannot be snatched.
Following are the basic terminologies:
Waiting Time: Time for which the process has to wait in the ready queue.
Turn Around Time: Total time taken by the process for execution (waiting time + burst time).
Write a C Program to implement priority scheduling.
Example:
Following is the example of non preemptive scheduling with arrival time zero.
Process | Burst Time | Priority |
---|---|---|
P1 | 5 | 1 |
P2 | 7 | 6 |
P3 | 2 | 4 |
P4 | 3 | 5 |
Since scheduling is non preemptive, which means that the process will be fully executed once its execution is started. So processes will be executed in the same order of priority.
Order: P2, P4, P3, P1
P2 will be executed from 0 to 7.
P4 will be executed from 7 to 10.
P3 will be executed from 10 to 12.
P1 will be executed from 12 to 17.
Process Id | Burst Time | Wait Time | Turn Around Time |
---|---|---|---|
P2 | 7 | 0 | 7 |
P4 | 3 | 7 | 10 |
P3 | 2 | 10 | 12 |
P1 | 5 | 12 | 17 |
Priority Scheduling Algorithm:
Step 1: Start the Program.
Step 2: Input the number of processes.
Step 3: Input the burst time and priority for each process.
Step 4: Sort the element on the basis of priority.
Step 5: Print order of execution of their process with their time stamp (wait time and turnaround time).
Step 6: End the Program.
Here is the source code of the C program to implement priority scheduling. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C program to implement priority scheduling
*/
#include <stdio.h>
//Function to swap two variables
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int main()
{
int n;
printf("Enter Number of Processes: ");
scanf("%d",&n);
// b is array for burst time, p for priority and index for process id
int b[n],p[n],index[n];
for(int i=0;i<n;i++)
{
printf("Enter Burst Time and Priority Value for Process %d: ",i+1);
scanf("%d %d",&b[i],&p[i]);
index[i]=i+1;
}
for(int i=0;i<n;i++)
{
int a=p[i],m=i;
//Finding out highest priority element and placing it at its desired position
for(int j=i;j<n;j++)
{
if(p[j] > a)
{
a=p[j];
m=j;
}
}
//Swapping processes
swap(&p[i], &p[m]);
swap(&b[i], &b[m]);
swap(&index[i],&index[m]);
}
// T stores the starting time of process
int t=0;
//Printing scheduled process
printf("Order of process Execution is\n");
for(int i=0;i<n;i++)
{
printf("P%d is executed from %d to %d\n",index[i],t,t+b[i]);
t+=b[i];
}
printf("\n");
printf("Process Id Burst Time Wait Time TurnAround Time\n");
int wait_time=0;
for(int i=0;i<n;i++)
{
printf("P%d %d %d %d\n",index[i],b[i],wait_time,wait_time + b[i]);
wait_time += b[i];
}
return 0;
}
1. First, enter the total number of processes and store it in variable n.
2. After that, provide the burst time and priority and store it in variable b and p.
3. Finding out highest priority element and placing it at its desired position.
4. Sort the processes on the basis of the priority.
5. After that print the processed with their time stamp (starting time and ending time). Variable T stores the starting time of process.
6. In the end, print the waiting time and turnaround time for each process. Waiting time is the time spent in the ready queue, while turnaround time is the total time taken by process (burst time + waiting time).
Time Complexity: O(n*n)
Sorting takes time of the order of O(n*n), So time complexity is of the order of O(n*n).
Space Complexity: O(n)
Space is required to store burst time, arrival time and index, So space complexity is O(n).
In this case, we enter “3” as the number of processes, and the burst time and priority value are “p1: 10 2”, “p2: 5 0”, and “p3: 8 1”.
Enter Number of Processes: 3 Enter Burst Time and Priority Value for Process 1: 10 2 Enter Burst Time and Priority Value for Process 2: 5 0 Enter Burst Time and Priority Value for Process 3: 8 1 Order of process Execution is P1 is executed from 0 to 10 P3 is executed from 10 to 18 P2 is executed from 18 to 23 Process Id Burst Time Wait Time TurnAround Time P1 10 0 10 P3 8 10 18 P2 5 18 23
To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.
- Practice Computer Science MCQs
- Watch Advanced C Programming Videos
- Practice BCA MCQs
- Apply for Computer Science Internship
- Apply for C Internship