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

// Core task scheduling model
 
interface Task {
    id: string;
    arrivalTime: number;    // When task enters the system
    burstTime: number;      // Total processing time needed
    remainingTime: number;  // Time left to complete (for preemptive)
    priority?: number;      // Optional priority level
    deadline?: number;      // Optional deadline
    
    // Tracking metrics
    startTime?: number;     // When execution first began
    completionTime?: number; // When task finished
}
 
interface SchedulerMetrics {
    totalTasks: number;
    avgWaitingTime: number;     // Time spent in ready queue
    avgTurnaroundTime: number;  // Total time from arrival to completion
    avgResponseTime: number;    // Time from arrival to first execution
    cpuUtilization: number;     // Percentage of time CPU was busy
    throughput: number;         // Tasks completed per unit time
}
 
// The ready queue - heart of the scheduling system
class ReadyQueue {
    private queue: Task[] = [];
    
    enqueue(task: Task): void {
        this.queue.push(task);
    }
    
    dequeue(): Task | undefined {
        return this.queue.shift();  // FIFO: dequeue from front
    }
    
    peek(): Task | undefined {
        return this.queue[0];
    }
    
    isEmpty(): boolean {
        return this.queue.length === 0;
    }
    
    size(): number {
        return this.queue.length;
    }
}
 
/*
Key insight: The queue serves as a "holding area" for tasks
awaiting their turn at the processor. The scheduling algorithm
determines the ORDER in which tasks are added and removed.
 
Different algorithms = different queue disciplines:
- FCFS: Pure FIFO, tasks processed in arrival order
- Round Robin: Circular FIFO with time limits
- Priority: May require priority queue, not simple FIFO
*/

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

// First-Come-First-Served (FCFS) Scheduler Simulation
 
interface Task {
    id: string;
    arrivalTime: number;
    burstTime: number;
    startTime?: number;
    completionTime?: number;
}
 
interface SimulationResult {
    schedule: { time: number; taskId: string; action: string }[];
    metrics: {
        avgWaitingTime: number;
        avgTurnaroundTime: number;
        avgResponseTime: number;
    };
}
 
function fcfsScheduler(tasks: Task[]): SimulationResult {
    // Sort by arrival time (in case not already sorted)
    const sortedTasks = [...tasks].sort((a, b) => a.arrivalTime - b.arrivalTime);
    
    const readyQueue: Task[] = [];
    const schedule: { time: number; taskId: string; action: string }[] = [];
    const completed: Task[] = [];
    
    let currentTime = 0;
    let taskIndex = 0;  // Next task to arrive
    
    while (completed.length < tasks.length) {
        // Add all tasks that have arrived by currentTime
        while (taskIndex < sortedTasks.length && 
               sortedTasks[taskIndex].arrivalTime <= currentTime) {
            readyQueue.push(sortedTasks[taskIndex]);
            schedule.push({
                time: sortedTasks[taskIndex].arrivalTime,
                taskId: sortedTasks[taskIndex].id,
                action: 'arrived'
            });
            taskIndex++;
        }
        
        if (readyQueue.length > 0) {
            // Dequeue next task (FCFS: front of queue)
            const task = readyQueue.shift()!;
            
            // Record start time (response time reference)
            task.startTime = currentTime;
            schedule.push({
                time: currentTime,
                taskId: task.id,
                action: 'started'
            });
            
            // Execute task to completion (non-preemptive)
            currentTime += task.burstTime;
            
            task.completionTime = currentTime;
            completed.push(task);
            schedule.push({
                time: currentTime,
                taskId: task.id,
                action: 'completed'
            });
        } else {
            // CPU idle - jump to next task arrival
            if (taskIndex < sortedTasks.length) {
                currentTime = sortedTasks[taskIndex].arrivalTime;
            }
        }
    }
    
    // Calculate metrics
    let totalWaiting = 0;
    let totalTurnaround = 0;
    let totalResponse = 0;
    
    for (const task of completed) {
        const waitingTime = task.startTime! - task.arrivalTime;
        const turnaroundTime = task.completionTime! - task.arrivalTime;
        const responseTime = task.startTime! - task.arrivalTime;
        
        totalWaiting += waitingTime;
        totalTurnaround += turnaroundTime;
        totalResponse += responseTime;
    }
    
    return {
        schedule,
        metrics: {
            avgWaitingTime: totalWaiting / tasks.length,
            avgTurnaroundTime: totalTurnaround / tasks.length,
            avgResponseTime: totalResponse / tasks.length
        }
    };
}
 
/*
Example:
Tasks: [
    { id: "P1", arrivalTime: 0, burstTime: 24 },
    { id: "P2", arrivalTime: 1, burstTime: 3 },
    { id: "P3", arrivalTime: 2, burstTime: 3 }
]
 
FCFS Execution:
Time 0-24: P1 runs (arrived first)
Time 24-27: P2 runs
Time 27-30: P3 runs
 
Timeline:
|-------- P1 (24) --------|-- P2 --|- P3 -|
0                        24       27     30
 
Metrics:
P1: Waiting = 0, Turnaround = 24
P2: Waiting = 23, Turnaround = 26
P3: Waiting = 25, Turnaround = 28
 
Average waiting time: (0 + 23 + 25) / 3 = 16
 
Notice the "convoy effect": Short tasks wait behind long ones!
*/

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
131
132
133
134
135
136
137
138
139
140
141

// Round-Robin Scheduler Simulation
 
interface TaskRR {
    id: string;
    arrivalTime: number;
    burstTime: number;
    remainingTime: number;
    firstRunTime?: number;
    completionTime?: number;
}
 
interface RRResult {
    ganttChart: { start: number; end: number; taskId: string }[];
    metrics: {
        avgWaitingTime: number;
        avgTurnaroundTime: number;
        avgResponseTime: number;
    };
}
 
function roundRobinScheduler(tasks: TaskRR[], quantum: number): RRResult {
    // Initialize remaining times
    const tasksCopy = tasks.map(t => ({
        ...t,
        remainingTime: t.burstTime
    }));
    const sortedTasks = tasksCopy.sort((a, b) => a.arrivalTime - b.arrivalTime);
    
    const readyQueue: TaskRR[] = [];
    const ganttChart: { start: number; end: number; taskId: string }[] = [];
    const completed: TaskRR[] = [];
    
    let currentTime = 0;
    let taskIndex = 0;
    
    // Add initial tasks
    while (taskIndex < sortedTasks.length && 
           sortedTasks[taskIndex].arrivalTime <= currentTime) {
        readyQueue.push(sortedTasks[taskIndex]);
        taskIndex++;
    }
    
    while (completed.length < tasks.length) {
        if (readyQueue.length > 0) {
            const task = readyQueue.shift()!;
            
            // Track first run (for response time)
            if (task.firstRunTime === undefined) {
                task.firstRunTime = currentTime;
            }
            
            // Execute for quantum or remaining time, whichever is smaller
            const executeTime = Math.min(quantum, task.remainingTime);
            
            ganttChart.push({
                start: currentTime,
                end: currentTime + executeTime,
                taskId: task.id
            });
            
            currentTime += executeTime;
            task.remainingTime -= executeTime;
            
            // Add newly arrived tasks BEFORE re-adding current task
            while (taskIndex < sortedTasks.length && 
                   sortedTasks[taskIndex].arrivalTime <= currentTime) {
                readyQueue.push(sortedTasks[taskIndex]);
                taskIndex++;
            }
            
            // If task not complete, add back to queue
            if (task.remainingTime > 0) {
                readyQueue.push(task);
            } else {
                task.completionTime = currentTime;
                completed.push(task);
            }
        } else {
            // CPU idle
            if (taskIndex < sortedTasks.length) {
                currentTime = sortedTasks[taskIndex].arrivalTime;
                readyQueue.push(sortedTasks[taskIndex]);
                taskIndex++;
            }
        }
    }
    
    // Calculate metrics
    let totalWaiting = 0, totalTurnaround = 0, totalResponse = 0;
    
    for (const task of completed) {
        const turnaround = task.completionTime! - task.arrivalTime;
        const waiting = turnaround - task.burstTime;
        const response = task.firstRunTime! - task.arrivalTime;
        
        totalWaiting += waiting;
        totalTurnaround += turnaround;
        totalResponse += response;
    }
    
    return {
        ganttChart,
        metrics: {
            avgWaitingTime: totalWaiting / tasks.length,
            avgTurnaroundTime: totalTurnaround / tasks.length,
            avgResponseTime: totalResponse / tasks.length
        }
    };
}
 
/*
Example with quantum = 4:
Tasks: [
    { id: "P1", arrivalTime: 0, burstTime: 24 },
    { id: "P2", arrivalTime: 1, burstTime: 3 },
    { id: "P3", arrivalTime: 2, burstTime: 3 }
]
 
RR Execution (Q=4):
Time 0-4:   P1 runs (20 remaining) → requeue
Time 4-7:   P2 runs (0 remaining) → DONE
Time 7-10:  P3 runs (0 remaining) → DONE
Time 10-14: P1 runs (16 remaining) → requeue
Time 14-18: P1 runs (12 remaining) → requeue
Time 18-22: P1 runs (8 remaining) → requeue
Time 22-26: P1 runs (4 remaining) → requeue
Time 26-30: P1 runs (0 remaining) → DONE
 
Timeline:
|P1-Q1|P2-P3|P1-Q2|P1-Q3|P1-Q4|P1-Q5|P1-Q6|
0    4    10   14   18   22   26   30
 
Metrics:
P1: Turnaround = 30 - 0 = 30, Waiting = 30 - 24 = 6
P2: Turnaround = 7 - 1 = 6, Waiting = 6 - 3 = 3
P3: Turnaround = 10 - 2 = 8, Waiting = 8 - 3 = 5
 
Avg waiting: (6 + 3 + 5) / 3 = 4.67 (vs 16 for FCFS!)
 
Much fairer for short tasks!
*/

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

// Multi-Level Queue (MLQ) Scheduler
 
type TaskType = 'realtime' | 'interactive' | 'batch';
 
interface MLQTask {
    id: string;
    type: TaskType;
    arrivalTime: number;
    burstTime: number;
    remainingTime: number;
    priority: number;  // Higher = more urgent
}
 
class MultiLevelQueueScheduler {
    // Three queues with different priorities
    private realtimeQueue: MLQTask[] = [];     // Highest priority, FCFS
    private interactiveQueue: MLQTask[] = [];   // Medium priority, Round-Robin
    private batchQueue: MLQTask[] = [];         // Lowest priority, FCFS
    
    private interactiveQuantum = 4;
    
    addTask(task: MLQTask): void {
        switch (task.type) {
            case 'realtime':
                this.realtimeQueue.push(task);
                break;
            case 'interactive':
                this.interactiveQueue.push(task);
                break;
            case 'batch':
                this.batchQueue.push(task);
                break;
        }
    }
    
    getNextTask(): { task: MLQTask; quantum: number } | null {
        // Priority: realtime > interactive > batch
        
        if (this.realtimeQueue.length > 0) {
            const task = this.realtimeQueue.shift()!;
            return { task, quantum: Infinity };  // Run to completion
        }
        
        if (this.interactiveQueue.length > 0) {
            const task = this.interactiveQueue.shift()!;
            return { task, quantum: this.interactiveQuantum };
        }
        
        if (this.batchQueue.length > 0) {
            const task = this.batchQueue.shift()!;
            return { task, quantum: Infinity };  // Run to completion
        }
        
        return null;  // All queues empty
    }
    
    requeue(task: MLQTask): void {
        // After quantum expires, re-add to appropriate queue
        this.addTask(task);
    }
}
 
/*
Example scenario:
 
Time 0: Batch task B1 (burst 100) arrives
Time 5: Interactive task I1 (burst 10) arrives
Time 7: Realtime task R1 (burst 5) arrives
 
Execution:
0-5:   B1 runs (95 remaining)
5-7:   I1 runs (8 remaining)  ← preempts B1!
7-12:  R1 runs to completion  ← preempts I1!
12-16: I1 runs (4 remaining)
16-20: I1 runs to completion
20-115: B1 runs to completion
 
Higher-priority queues always preempt lower ones!
*/

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
131
132
133

// Event-Driven Task Scheduling Simulation
 
type EventType = 'TASK_ARRIVAL' | 'TASK_COMPLETE' | 'QUANTUM_EXPIRE';
 
interface Event {
    time: number;
    type: EventType;
    taskId?: string;
    task?: Task;
}
 
interface Task {
    id: string;
    arrivalTime: number;
    burstTime: number;
    remainingTime: number;
}
 
class EventDrivenSimulator {
    private eventQueue: Event[] = [];  // Sorted by time
    private readyQueue: Task[] = [];
    private currentTask: Task | null = null;
    private currentTime = 0;
    private quantum = 4;
    private log: string[] = [];
    
    constructor(tasks: Task[]) {
        // Schedule all arrival events
        for (const task of tasks) {
            this.scheduleEvent({
                time: task.arrivalTime,
                type: 'TASK_ARRIVAL',
                task: { ...task, remainingTime: task.burstTime }
            });
        }
    }
    
    private scheduleEvent(event: Event): void {
        // Insert maintaining time order
        let i = 0;
        while (i < this.eventQueue.length && 
               this.eventQueue[i].time <= event.time) {
            i++;
        }
        this.eventQueue.splice(i, 0, event);
    }
    
    run(): void {
        while (this.eventQueue.length > 0) {
            const event = this.eventQueue.shift()!;
            this.currentTime = event.time;
            this.handleEvent(event);
        }
        
        console.log("Simulation Log:");
        this.log.forEach(line => console.log(line));
    }
    
    private handleEvent(event: Event): void {
        switch (event.type) {
            case 'TASK_ARRIVAL':
                this.handleArrival(event.task!);
                break;
            case 'QUANTUM_EXPIRE':
                this.handleQuantumExpire();
                break;
            case 'TASK_COMPLETE':
                this.handleCompletion();
                break;
        }
    }
    
    private handleArrival(task: Task): void {
        this.log.push(`[Time ${this.currentTime}] Task ${task.id} arrived`);
        this.readyQueue.push(task);
        this.trySchedule();
    }
    
    private handleQuantumExpire(): void {
        if (this.currentTask && this.currentTask.remainingTime > 0) {
            this.log.push(
                `[Time ${this.currentTime}] Quantum expired for ${this.currentTask.id}, ` +
                                        `${this.currentTask.remainingTime} remaining`
            );
            this.readyQueue.push(this.currentTask);
            this.currentTask = null;
            this.trySchedule();
        }
    }
    
    private handleCompletion(): void {
        this.log.push(
            `[Time ${this.currentTime}] Task ${this.currentTask!.id} completed`
        );
        this.currentTask = null;
        this.trySchedule();
    }
    
    private trySchedule(): void {
        if (this.currentTask !== null) return;  // CPU busy
        if (this.readyQueue.length === 0) return;  // Nothing to run
        
        this.currentTask = this.readyQueue.shift()!;
        const runTime = Math.min(this.quantum, this.currentTask.remainingTime);
        
        this.log.push(
            `[Time ${this.currentTime}] Starting ${this.currentTask.id} ` +
                                    `for ${runTime} units`
        );
        
        this.currentTask.remainingTime -= runTime;
        
        if (this.currentTask.remainingTime === 0) {
            this.scheduleEvent({
                time: this.currentTime + runTime,
                type: 'TASK_COMPLETE'
            });
        } else {
            this.scheduleEvent({
                time: this.currentTime + runTime,
                type: 'QUANTUM_EXPIRE'
            });
        }
    }
}
 
/*
This event-driven approach is how real simulators work:
- No busy-waiting or polling
- Jump directly from event to event
- Accurate timing without iterating every time unit
- Scales to millions of events efficiently
*/

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

// Common Job Queue Patterns
 
// Pattern 1: Simple Worker Pool
class WorkerPool {
    private jobQueue: (() => Promise<void>)[] = [];
    private activeWorkers = 0;
    private maxWorkers: number;
    
    constructor(maxWorkers: number) {
        this.maxWorkers = maxWorkers;
    }
    
    enqueue(job: () => Promise<void>): void {
        this.jobQueue.push(job);
        this.tryProcessNext();
    }
    
    private async tryProcessNext(): Promise<void> {
        if (this.activeWorkers >= this.maxWorkers) return;
        if (this.jobQueue.length === 0) return;
        
        const job = this.jobQueue.shift()!;
        this.activeWorkers++;
        
        try {
            await job();
        } finally {
            this.activeWorkers--;
            this.tryProcessNext();  // Check for more work
        }
    }
}
 
// Usage:
const pool = new WorkerPool(4);  // 4 concurrent workers
for (let i = 0; i < 100; i++) {
    pool.enqueue(async () => {
        console.log(`Processing job ${i}`);
        await simulateWork(1000);  // 1 second
    });
}
 
// Pattern 2: Rate-Limited Queue
class RateLimitedQueue {
    private queue: { job: () => Promise<void>; retries: number }[] = [];
    private processing = false;
    private requestsPerSecond: number;
    
    constructor(rps: number) {
        this.requestsPerSecond = rps;
    }
    
    enqueue(job: () => Promise<void>): void {
        this.queue.push({ job, retries: 0 });
        this.startProcessing();
    }
    
    private async startProcessing(): Promise<void> {
        if (this.processing) return;
        this.processing = true;
        
        while (this.queue.length > 0) {
            const { job, retries } = this.queue.shift()!;
            
            try {
                await job();
            } catch (error) {
                if (retries < 3) {
                    // Re-queue with backoff
                    this.queue.push({ job, retries: retries + 1 });
                }
            }
            
            // Wait to enforce rate limit
            await sleep(1000 / this.requestsPerSecond);
        }
        
        this.processing = false;
    }
}
 
// Pattern 3: Priority Job Queue
interface PriorityJob {
    priority: number;  // Higher = more urgent
    job: () => Promise<void>;
}
 
class PriorityJobQueue {
    private queue: PriorityJob[] = [];
    
    enqueue(job: () => Promise<void>, priority: number): void {
        // Insert in priority order
        const item = { priority, job };
        let i = 0;
        while (i < this.queue.length && 
               this.queue[i].priority >= priority) {
            i++;
        }
        this.queue.splice(i, 0, item);
    }
    
    async processNext(): Promise<boolean> {
        if (this.queue.length === 0) return false;
        const { job } = this.queue.shift()!;
        await job();
        return true;
    }
}
 
async function simulateWork(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
}
 
async function sleep(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
}
 
/*
These patterns appear in:
- Message brokers (RabbitMQ, Kafka)
- Task queues (Celery, Sidekiq, Bull)
- Cloud services (AWS SQS, Azure Queue)
- Background job processors
*/