non_preemptive_priority_scheduling.c File Reference

Non-Preemptive Priority Scheduling is a scheduling algorithm that selects the tasks to execute based on priority. More...

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

Include dependency graph for non_preemptive_priority_scheduling.c:

Data Structures
struct	node
	Node, the basic data structure in the tree. More...

Typedefs
typedef struct node	node
	for assert

Functions
void	insert (node **root, int id, int at, int bt, int prior)
	To insert a new process in the queue.
void	delete (node **root, int id)
void	show_list (node *head)
	To show the process queue.
int	l_length (node **root)
	To length process queue.
void	update (node **root, int id, int ct, int wt, int tat)
	To update the completion time, turn around time and waiting time of the processes.
bool	compare (node *a, node *b)
	To compare the priority of two processes based on their arrival time and priority.
float	calculate_ct (node **root)
	To calculate the average completion time of all the processes.
float	calculate_tat (node **root)
	To calculate the average turn around time of all the processes.
float	calculate_wt (node **root)
	To calculate the average waiting time of all the processes.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Non-Preemptive Priority Scheduling is a scheduling algorithm that selects the tasks to execute based on priority.

In this algorithm, processes are executed according to their priority. The process with the highest priority is to be executed first and so on. In this algorithm, a variable is maintained known as the time quantum. The length of the time quantum is decided by the user. The process which is being executed is interrupted after the expiration of the time quantum and the next process with the highest priority is executed. This cycle of interrupting the process after every time quantum and resuming the next process with the highest priority continues until all the processes have been executed.

Author

Aryan Raj

Typedef Documentation

node

typedef struct node node

for assert

for boolean data type for IO operations (printf) for memory allocation eg: malloc, realloc, free, exit

Structure to represent a process

Function Documentation

calculate_ct()

float calculate_ct

(

node **

root

)

To calculate the average completion time of all the processes.

Parameters

root	pointer to the head of the queue

Returns

float average completion time

{
    // calculate the total completion time of all the processes
    node *ptr = *root, *prior, *rpt;
    int ct = 0, i, time = 0;
    int n = l_length(root);
    float avg, sum = 0;
    node *duproot = NULL;
    // create a duplicate queue
    while (ptr != NULL)
    {
        insert(&duproot, ptr->ID, ptr->AT, ptr->BT, ptr->priority);
        ptr = ptr->next;
    }
    ptr = duproot;
    rpt = ptr->next;
    // sort the queue based on the arrival time and priority
    while (rpt != NULL)
    {
        if (!compare(ptr, rpt))
        {
            ptr = rpt;
        }
        rpt = rpt->next;
    }
    // ptr is the process to be executed first.
    ct = ptr->AT + ptr->BT;
    time = ct;
    sum += ct;
    // update the completion time, turn around time and waiting time of the
    // process
    update(root, ptr->ID, ct, 0, 0);
    delete (&duproot, ptr->ID);
    // repeat the process until all the processes are executed
    for (i = 0; i < n - 1; i++)
    {
        ptr = duproot;
        while (ptr != NULL && ptr->AT > time)
        {
            ptr = ptr->next;
        }
        rpt = ptr->next;
        while (rpt != NULL)
        {
            if (rpt->AT <= time)
            {
                if (rpt->priority < ptr->priority)
                {
                    ptr = rpt;
                }
            }
            rpt = rpt->next;
        }
        ct += ptr->BT;
        time += ptr->BT;
        sum += ct;
        update(root, ptr->ID, ct, 0, 0);
        delete (&duproot, ptr->ID);
    }
    avg = sum / n;
    return avg;
}

Here is the call graph for this function:

calculate_tat()

float calculate_tat

(

node **

root

)

To calculate the average turn around time of all the processes.

Parameters

root	pointer to the head of the queue

Returns

float average turn around time

{
    float avg, sum = 0;
    int n = l_length(root);
    node *ptr = *root;
    // calculate the completion time if not already calculated
    if (ptr->CT == 0)
    {
        calculate_ct(root);
    }
    // calculate the total turn around time of all the processes
    while (ptr != NULL)
    {
        ptr->TAT = ptr->CT - ptr->AT;
        sum += ptr->TAT;
        ptr = ptr->next;
    }
    avg = sum / n;
    return avg;
}

Here is the call graph for this function:

calculate_wt()

float calculate_wt

(

node **

root

)

To calculate the average waiting time of all the processes.

Parameters

root	pointer to the head of the queue

Returns

float average waiting time

{
    float avg, sum = 0;
    int n = l_length(root);
    node *ptr = *root;
    // calculate the completion if not already calculated
    if (ptr->CT == 0)
    {
        calculate_ct(root);
    }
    // calculate the total waiting time of all the processes
    while (ptr != NULL)
    {
        ptr->WT = (ptr->TAT - ptr->BT);
        sum += ptr->WT;
        ptr = ptr->next;
    }
    avg = sum / n;
    return avg;
}

Here is the call graph for this function:

compare()

bool compare	(	node *	a,
		node *	b
	)

To compare the priority of two processes based on their arrival time and priority.

Parameters

a	pointer to the first process
b	pointer to the second process

Returns

true if the priority of the first process is greater than the the second process

false if the priority of the first process is NOT greater than the second process

{
    if (a->AT == b->AT)
    {
        return a->priority < b->priority;
    }
    else
    {
        return a->AT < b->AT;
    }
}

delete()

void delete	(	node **	root,
		int	id
	)

{
    node *ptr = *root, *prev;
    // if the root is null, return
    if (ptr == NULL)
    {
        return;
    }
    // if the root is the process to be deleted, make the next node the root
    if (ptr->ID == id)
    {
        *root = ptr->next;
        free(ptr);
        return;
    }
    // else traverse the queue and delete the process
    while (ptr != NULL && ptr->ID != id)
    {
        prev = ptr;
        ptr = ptr->next;
    }
    if (ptr == NULL)
    {
        return;
    }
    prev->next = ptr->next;
    free(ptr);
}

insert()

void insert	(	node **	root,
		int	id,
		int	at,
		int	bt,
		int	prior
	)

To insert a new process in the queue.

Parameters

root	pointer to the head of the queue
id	process ID
at	arrival time
bt	burst time
prior	priority of the process

Returns

void

{
    // create a new node and initialize it
    node *new = (node *)malloc(sizeof(node));
    node *ptr = *root;
    new->ID = id;
    new->AT = at;
    new->BT = bt;
    new->priority = prior;
    new->next = NULL;
    new->CT = 0;
    new->WT = 0;
    new->TAT = 0;
    // if the root is null, make the new node the root
    if (*root == NULL)
    {
        *root = new;
        return;
    }
    // else traverse to the end of the queue and insert the new node there
    while (ptr->next != NULL)
    {
        ptr = ptr->next;
    }
    ptr->next = new;
    return;
}

l_length()

int l_length

(

node **

root

)

To length process queue.

Parameters

root	pointer to the head of the queue

Returns

int total length of the queue

{
    int count = 0;
    node *ptr = *root;
    while (ptr != NULL)
    {
        count++;
        ptr = ptr->next;
    }
    return count;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

{
    test();  // run self-test implementations
 
    return 0;
}

Here is the call graph for this function:

show_list()

void show_list

(

node *

head

)

To show the process queue.

Parameters

head	pointer to the head of the queue

Returns

void

{
    printf("Process Priority AT BT CT TAT WT \n");
    while (head != NULL)
    {
        printf("P%d. %d %d %d %d %d %d \n", head->ID, head->priority, head->AT,
               head->BT, head->CT, head->TAT, head->WT);
        head = head->next;
    }
}

test()

static void test ( void  )

static

Self-test implementations.

Returns

void

{
    // Entered processes
    // printf("ID Priority Arrival Time Burst Time \n");
    // printf("1 0 5 1 \n");
    // printf("2 1 4 2 \n");
    // printf("3 2 3 3 \n");
    // printf("4 3 2 4 \n");
    // printf("5 4 1 5 \n");
 
    node *root = NULL;
    insert(&root, 1, 0, 5, 1);
    insert(&root, 2, 1, 4, 2);
    insert(&root, 3, 2, 3, 3);
    insert(&root, 4, 3, 2, 4);
    insert(&root, 5, 4, 1, 5);
    float avgCT = calculate_ct(&root);
    float avgTAT = calculate_tat(&root);
    float avgWT = calculate_wt(&root);
    assert(avgCT == 11);
    assert(avgTAT == 9);
    assert(avgWT == 6);
    printf("[+] All tests have successfully passed!\n");
    // printf("Average Completion Time is : %f \n", calculate_ct(&root));
    // printf("Average Turn Around Time is : %f \n", calculate_tat(&root));
    // printf("Average Waiting Time is : %f \n", calculate_wt(&root));
}

Here is the call graph for this function:

update()

void update	(	node **	root,
		int	id,
		int	ct,
		int	wt,
		int	tat
	)

To update the completion time, turn around time and waiting time of the processes.

Parameters

root	pointer to the head of the queue
id	process ID
ct	current time
wt	waiting time
tat	turn around time

Returns

void

{
    node *ptr = *root;
    // If process to be updated is head node
    if (ptr != NULL && ptr->ID == id)
    {
        if (ct != 0)
        {
            ptr->CT = ct;
        }
        if (wt != 0)
        {
            ptr->WT = wt;
        }
        if (tat != 0)
        {
            ptr->TAT = tat;
        }
        return;
    }
    // else traverse the queue and update the values
    while (ptr != NULL && ptr->ID != id)
    {
        ptr = ptr->next;
    }
    if (ct != 0)
    {
        ptr->CT = ct;
    }
    if (wt != 0)
    {
        ptr->WT = wt;
    }
    if (tat != 0)
    {
        ptr->TAT = tat;
    }
    return;
}