Shortest Job First SJF -CPU Scheduling

 

SHORTEST JOB FIRST (SJF) CPU SCHEDULING (NON-PREEMPTIVE)

---

1. AIM

To simulate the Shortest Job First (SJF) Non-Preemptive CPU Scheduling Algorithm using arrival time and burst time of processes and compute:

• Completion Time (CT)

• Turnaround Time (TAT)

• Waiting Time (WT)

• Average Waiting Time

---

2. THEORY

Shortest Job First Scheduling

SJF selects the process with the smallest burst time from the ready queue.

Characteristics

• Non-preemptive: Once a process starts, it cannot be interrupted.

• Minimizes average waiting time.

• Not suitable for real-time systems because burst times must be known beforehand.

Key Performance Metrics

1. Completion Time (CT)
   Time at which process finishes execution.

2. Turnaround Time (TAT)

   $$TAT=CT-ArrivalTime$$

3. Waiting Time (WT)

   $$WT=TAT-BurstTime$$

---

3. ALGORITHM

1. Input number of processes n.

2. For each process, input:

   • Process ID

   • Arrival Time

   • Burst Time

3. At each step:

   • Select the process which has arrived and has smallest burst time.

   • Execute it to completion (non-preemptive).

4. For each process:

   • Compute CT, TAT, WT

5. Compute Average Waiting Time.

6. Display results.

---

4. C PROGRAM – SJF (Non-Preemptive) Using Structures

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

struct Process {
    int pid;
    int at;   // Arrival Time
    int bt;   // Burst Time
    int ct;   // Completion Time
    int tat;  // Turnaround Time
    int wt;   // Waiting Time
    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("Enter Arrival Time of P%d: ", i + 1);
        scanf("%d", &p[i].at);
        printf("Enter Burst Time of P%d: ", i + 1);
        scanf("%d", &p[i].bt);
        p[i].completed = 0;
    }

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

    while (completed != n) {
        int idx = -1;
        int minBT = INT_MAX;

        // Find the shortest job available at current time
        for (int i = 0; i < n; i++) {
            if (!p[i].completed && p[i].at <= time && p[i].bt < minBT) {
                minBT = p[i].bt;
                idx = i;
            }
        }

        // If no process has arrived yet
        if (idx == -1) {
            time++;
            continue;
        }

        // Execute the selected process
        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;
    }

    // Output table
    printf("\nSJF Scheduling Result:\n");
    printf("PID\tAT\tBT\tCT\tTAT\tWT\n");
    for (int i = 0; i < n; i++) {
        printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
               p[i].pid, p[i].at, p[i].bt, p[i].ct,
               p[i].tat, p[i].wt);
    }

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

    return 0;
}

---

5. SAMPLE INPUT

Enter number of processes: 4
Enter Arrival Time of P1: 0
Enter Burst Time of P1: 7

Enter Arrival Time of P2: 2
Enter Burst Time of P2: 4

Enter Arrival Time of P3: 4
Enter Burst Time of P3: 1

Enter Arrival Time of P4: 5
Enter Burst Time of P4: 4

---

6. GANTT CHART

Time: 0    7   8    12   16
       |----|----|----|----|
       | P1 | P3 | P2 | P4 |
       |----|----|----|----|

---

7. SAMPLE OUTPUT

SJF Scheduling Result:
PID   AT   BT   CT   TAT   WT
P1    0    7    7    7     0
P2    2    4    12   10    6
P3    4    1    8    4     3
P4    5    4    16   11    7

Average Waiting Time = 4.00

---

8. RESULT

The Shortest Job First (Non-Preemptive) scheduling algorithm was implemented successfully.
The program calculated:

• Completion Time

• Turnaround Time

• Waiting Time

• Average Waiting Time

for all processes according to SJF scheduling criteria.