Non - Preemptive Priority Scheduling

 

NON-PREEMPTIVE 

PRIORITY SCHEDULING

(Considering Higher Number = Higher Priority)

---

1. AIM

To simulate the Non-Preemptive Priority Scheduling Algorithm, where higher priority value indicates higher importance, and compute:

• Completion Time (CT)

• Turnaround Time (TAT)

• Waiting Time (WT)

• Average Waiting Time

• Gantt Chart

---

2. THEORY

CPU scheduling determines which process from the ready queue gets the CPU next.
In Priority Scheduling, each process is assigned a priority, and the CPU is given to the process with the highest priority.

Non-Preemptive Priority Scheduling

• CPU is allocated to the highest priority process among those that have already arrived.

• Once a process starts executing, it cannot be preempted, even if a process with a higher priority arrives.

• Here we consider:

  $$\text{Higher number} \Rightarrow \text{Higher Priority}$$

• Used in systems where tasks with higher importance must run before others.

Performance Metrics

• Completion Time (CT): Time at which a process completes.

• Turnaround Time (TAT)

  $$TAT = CT - AT$$
  

• Waiting Time (WT)

  $$WT = TAT - BT$$
  

• Average Waiting Time (AWT)

  $$AWT = \frac{\sum WT}{n}$$

Advantages

• Simple and fast.

• Useful when processes have different importance levels.

Disadvantages

• Starvation of low-priority processes.

• No fairness without aging.

---

3. ALGORITHM

1. Input number of processes n.

2. For each process, input:

   • Arrival Time (AT)

   • Burst Time (BT)

   • Priority

3. Set all processes as not completed.

4. At current time, select the process that:

   • Has arrived (AT ≤ time)

   • Has highest priority (largest priority number)

   • Is not completed

5. Execute it non-preemptively until completion.

6. Calculate:

   • CT = completion time

   • TAT = CT − AT

   • WT = TAT − BT

7. Repeat until all processes are completed.

8. Compute Average Waiting Time.

---

4. SAMPLE INPUT (Example)

Process	Arrival Time	Burst Time	Priority
P1	0	4	2
P2	1	3	4
P3	2	1	1
P4	3	2	5

Higher number → Higher priority

---

5. GANTT CHART

0      4      6      9     10
|  P1  |  P4  |  P2  |  P3  |

---

6. COMPUTATION TABLE

PID	AT	BT	Priority	CT	TAT	WT
P1	0	4	2	4	4	0
P4	3	2	5	6	3	1
P2	1	3	4	9	8	5
P3	2	1	1	10	8	7

Average Waiting Time

$$AWT = \frac{0 + 1 + 5 + 7}{4} = 3.25$$

7. C PROGRAM – NON-PREEMPTIVE PRIORITY SCHEDULING

(Higher Number = Higher Priority)

#include <stdio.h>
#include <limits.h>

struct Process {
    int pid;
    int at;
    int bt;
    int priority;
    int ct, tat, wt;
    int completed;
};

int main() {
    int n;
    printf("Enter number of processes: ");
    scanf("%d", &n);

    struct Process p[n];

    for (int i = 0; i < n; i++) {
        p[i].pid = i + 1;
        printf("\nEnter Arrival Time for P%d: ", i + 1);
        scanf("%d", &p[i].at);
        printf("Enter Burst Time for P%d: ", i + 1);
        scanf("%d", &p[i].bt);
        printf("Enter Priority for P%d: ", i + 1);
        scanf("%d", &p[i].priority);
        p[i].completed = 0;
    }

    int completed = 0, time = 0;
    float totalWT = 0;

    while (completed != n) {
        int idx = -1;
        int bestPriority = -1; // For highest priority selection

        for (int i = 0; i < n; i++) {
            if (!p[i].completed && p[i].at <= time) {
                // Higher number = higher priority
                if (p[i].priority > bestPriority) {
                    bestPriority = p[i].priority;
                    idx = i;
                }
            }
        }

        if (idx == -1) {
            time++;
            continue;
        }

        time += p[idx].bt;
        p[idx].ct = time;
        p[idx].tat = p[idx].ct - p[idx].at;
        p[idx].wt = p[idx].tat - p[idx].bt;

        p[idx].completed = 1;
        completed++;

        totalWT += p[idx].wt;
    }

    printf("\nNon-Preemptive Priority Scheduling Result:\n");
    printf("PID\tAT\tBT\tPR\tCT\tTAT\tWT\n");

    for (int i = 0; i < n; i++) {
        printf("P%d\t%d\t%d\t%d\t%d\t%d\t%d\n",
               p[i].pid, p[i].at, p[i].bt, p[i].priority,
               p[i].ct, p[i].tat, p[i].wt);
    }

    printf("\nAverage Waiting Time = %.2f\n", totalWT / n);

    return 0;
}

---

8. SAMPLE OUTPUT

Enter number of processes: 4

Enter Arrival Time for P1: 0
Enter Burst Time for P1: 4
Enter Priority for P1: 2

Enter Arrival Time for P2: 1
Enter Burst Time for P2: 3
Enter Priority for P2: 4

Enter Arrival Time for P3: 2
Enter Burst Time for P3: 1
Enter Priority for P3: 1

Enter Arrival Time for P4: 3
Enter Burst Time for P4: 2
Enter Priority for P4: 5

PID   AT   BT   PR   CT   TAT   WT
P1    0    4    2    4    4     0
P4    3    2    5    6    3     1
P2    1    3    4    9    8     5
P3    2    1    1    10   8     7

Average Waiting Time = 3.25

---

9. RESULT

The Non-Preemptive Priority Scheduling Algorithm was successfully implemented.
Considering “higher number = higher priority,” the program correctly computed:

• Completion Time

• Turnaround Time

• Waiting Time

• Average Waiting Time

and produced the execution sequence and Gantt Chart.