Shortest Job First (SJF) & SRTF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
#define MAX_PROCESSES 100
 
typedef struct {
    int pid;              // Process ID
    int arrival_time;     // Time process enters ready queue
    int burst_time;       // Total CPU burst time needed
    int remaining_time;   // For tracking (equals burst_time in non-preemptive)
    int start_time;       // When process first gets CPU
    int completion_time;  // When process finishes
    int waiting_time;     // Time spent in ready queue
    int turnaround_time;  // Total time from arrival to completion
    int started;          // Flag: has this process started?
} Process;
 
/**
 * Finds the process with shortest burst time among arrived processes
 * Returns -1 if no process is available
 */
int find_shortest_job(Process procs[], int n, int current_time, int completed[]) {
    int shortest_idx = -1;
    int min_burst = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        // Process must have arrived and not be completed
        if (procs[i].arrival_time <= current_time && !completed[i]) {
            // Select if shorter, or if equal length, prefer earlier arrival
            if (procs[i].burst_time < min_burst ||
                (procs[i].burst_time == min_burst && 
                 (shortest_idx == -1 || 
                  procs[i].arrival_time < procs[shortest_idx].arrival_time))) {
                min_burst = procs[i].burst_time;
                shortest_idx = i;
            }
        }
    }
    return shortest_idx;
}
 
/**
 * Non-preemptive SJF Scheduler
 * Simulates SJF scheduling and computes all metrics
 */
void sjf_schedule(Process procs[], int n) {
    int completed[MAX_PROCESSES] = {0};  // Track completed processes
    int completed_count = 0;
    int current_time = 0;
    
    printf("
SJF Scheduling Simulation:
");
    printf("═══════════════════════════════════════════════════════════
");
    
    while (completed_count < n) {
        // Find the shortest job among arrived, uncompleted processes
        int idx = find_shortest_job(procs, n, current_time, completed);
        
        if (idx == -1) {
            // No process available - fast forward to next arrival
            int next_arrival = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (!completed[i] && procs[i].arrival_time < next_arrival) {
                    next_arrival = procs[i].arrival_time;
                }
            }
            printf("Time %3d: CPU idle (waiting for process arrival)
", 
                   current_time);
            current_time = next_arrival;
            continue;
        }
        
        // Schedule the selected process
        Process *p = &procs[idx];
        p->start_time = current_time;
        p->completion_time = current_time + p->burst_time;
        p->turnaround_time = p->completion_time - p->arrival_time;
        p->waiting_time = p->turnaround_time - p->burst_time;
        
        printf("Time %3d: P%d starts (burst=%d, arrival=%d)
",
               current_time, p->pid, p->burst_time, p->arrival_time);
        
        current_time = p->completion_time;
        completed[idx] = 1;
        completed_count++;
        
        printf("Time %3d: P%d completes (wait=%d, turnaround=%d)
",
               current_time, p->pid, p->waiting_time, p->turnaround_time);
    }
    
    printf("═══════════════════════════════════════════════════════════
");
}
 
/**
 * Calculate and display average metrics
 */
void print_metrics(Process procs[], int n) {
    float total_wait = 0, total_turnaround = 0;
    
    printf("
%-5s %-10s %-10s %-10s %-10s %-12s
",
           "PID", "Arrival", "Burst", "Wait", "Turnaround", "Completion");
    printf("─────────────────────────────────────────────────────────
");
    
    for (int i = 0; i < n; i++) {
        printf("P%-4d %-10d %-10d %-10d %-10d %-12d
",
               procs[i].pid, procs[i].arrival_time, procs[i].burst_time,
               procs[i].waiting_time, procs[i].turnaround_time,
               procs[i].completion_time);
        total_wait += procs[i].waiting_time;
        total_turnaround += procs[i].turnaround_time;
    }
    
    printf("─────────────────────────────────────────────────────────
");
    printf("Average Waiting Time:    %.2f
", total_wait / n);
    printf("Average Turnaround Time: %.2f
", total_turnaround / n);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

/**
 * Min-Heap based SJF Ready Queue
 * Optimized for efficient minimum extraction
 */
 
#define HEAP_CAPACITY 1024
 
typedef struct {
    int pid;
    int burst_time;
    int arrival_time;
} HeapProcess;
 
typedef struct {
    HeapProcess data[HEAP_CAPACITY];
    int size;
} MinHeap;
 
/**
 * Comparison: returns true if a should come before b
 * Primary: shorter burst. Tie-breaker: earlier arrival.
 */
static inline int compare(HeapProcess *a, HeapProcess *b) {
    if (a->burst_time != b->burst_time)
        return a->burst_time < b->burst_time;
    return a->arrival_time < b->arrival_time;
}
 
/**
 * Bubble up: restore heap property after insertion
 */
void heapify_up(MinHeap *heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (compare(&heap->data[index], &heap->data[parent])) {
            // Swap with parent
            HeapProcess temp = heap->data[index];
            heap->data[index] = heap->data[parent];
            heap->data[parent] = temp;
            index = parent;
        } else {
            break;
        }
    }
}
 
/**
 * Bubble down: restore heap property after extraction
 */
void heapify_down(MinHeap *heap, int index) {
    while (1) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap->size && 
            compare(&heap->data[left], &heap->data[smallest])) {
            smallest = left;
        }
        if (right < heap->size && 
            compare(&heap->data[right], &heap->data[smallest])) {
            smallest = right;
        }
        
        if (smallest != index) {
            HeapProcess temp = heap->data[index];
            heap->data[index] = heap->data[smallest];
            heap->data[smallest] = temp;
            index = smallest;
        } else {
            break;
        }
    }
}
 
/**
 * Insert process into ready queue - O(log n)
 */
void heap_insert(MinHeap *heap, int pid, int burst, int arrival) {
    if (heap->size >= HEAP_CAPACITY) {
        fprintf(stderr, "Ready queue overflow
");
        return;
    }
    
    int index = heap->size++;
    heap->data[index] = (HeapProcess){pid, burst, arrival};
    heapify_up(heap, index);
}
 
/**
 * Get process with shortest burst - O(1)
 */
HeapProcess* heap_peek(MinHeap *heap) {
    if (heap->size == 0) return NULL;
    return &heap->data[0];
}
 
/**
 * Remove and return shortest burst process - O(log n)
 */
HeapProcess heap_extract_min(MinHeap *heap) {
    HeapProcess min = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    heapify_down(heap, 0);
    return min;
}
 
int heap_empty(MinHeap *heap) {
    return heap->size == 0;
}