CPU Scheduler

A comprehensive npm package for CPU scheduling algorithms simulation including FCFS, SJF, SRTF, Round Robin, Priority, MLQ, and MLFQ with detailed metrics calculation.

Features

• 7 Scheduling Algorithms: FCFS, SJF, SRTF, Round Robin, Priority, MLQ, MLFQ
• Complete Metrics: Completion time, turnaround time, waiting time, and averages
• Gantt Chart: Visual representation of process execution timeline
• TypeScript Support: Full type definitions included
• Comprehensive Testing: 87 tests with 87%+ coverage
• Zero Dependencies: Lightweight and fast
• Input Validation: Robust error handling and validation

Installation

npm install cpu-scheduler

Quick Start

import { scheduleFCFS, scheduleSJF, scheduleRoundRobin, schedulePriority } from 'cpu-scheduler';

// Define your processes
const processes = [
  { id: 1, arrivalTime: 0, burstTime: 5 },
  { id: 2, arrivalTime: 1, burstTime: 3 },
  { id: 3, arrivalTime: 2, burstTime: 8 }
];

// FCFS Scheduling
const fcfsResult = scheduleFCFS(processes);
console.log('FCFS Results:', fcfsResult);

// Round Robin with quantum 2
const rrResult = scheduleRoundRobin(processes, 2);
console.log('Round Robin Results:', rrResult);

// Priority Scheduling
const priorityProcesses = [
  { id: 1, arrivalTime: 0, burstTime: 5, priority: 3 },
  { id: 2, arrivalTime: 1, burstTime: 3, priority: 1 },
  { id: 3, arrivalTime: 2, burstTime: 2, priority: 2 }
];
const priorityResult = schedulePriority(priorityProcesses);
console.log('Priority Results:', priorityResult);

Detailed Examples

1. First Come First Served (FCFS)

import { scheduleFCFS } from 'cpu-scheduler';

const processes = [
  { id: 1, arrivalTime: 0, burstTime: 5 },
  { id: 2, arrivalTime: 1, burstTime: 3 },
  { id: 3, arrivalTime: 2, burstTime: 2 }
];

const result = scheduleFCFS(processes);
console.log(result);
// Output:
// {
//   processes: [
//     { id: 1, arrivalTime: 0, burstTime: 5, completionTime: 5, turnaroundTime: 5, waitingTime: 0 },
//     { id: 2, arrivalTime: 1, burstTime: 3, completionTime: 8, turnaroundTime: 7, waitingTime: 4 },
//     { id: 3, arrivalTime: 2, burstTime: 2, completionTime: 10, turnaroundTime: 8, waitingTime: 6 }
//   ],
//   averages: { averageWaitingTime: 3.33, averageTurnaroundTime: 6.67 },
//   ganttChart: [
//     { processId: 1, startTime: 0, endTime: 5 },
//     { processId: 2, startTime: 5, endTime: 8 },
//     { processId: 3, startTime: 8, endTime: 10 }
//   ]
// }

2. Round Robin Scheduling

import { scheduleRoundRobin } from 'cpu-scheduler';

const processes = [
  { id: 1, arrivalTime: 0, burstTime: 5 },
  { id: 2, arrivalTime: 1, burstTime: 3 },
  { id: 3, arrivalTime: 2, burstTime: 2 }
];

const result = scheduleRoundRobin(processes, 2); // Quantum = 2
console.log(result);
// Processes are executed in round-robin fashion with time quantum 2

3. Priority Scheduling

import { schedulePriority } from 'cpu-scheduler';

const processes = [
  { id: 1, arrivalTime: 0, burstTime: 5, priority: 3 },
  { id: 2, arrivalTime: 1, burstTime: 3, priority: 1 },
  { id: 3, arrivalTime: 2, burstTime: 2, priority: 2 }
];

const result = schedulePriority(processes);
console.log(result);
// Lower priority number = higher priority
// Execution order: 2 (priority 1), 3 (priority 2), 1 (priority 3)

4. Multi-Level Queue (MLQ)

import { scheduleMLQ } from 'cpu-scheduler';

const processes = [
  { id: 1, arrivalTime: 0, burstTime: 5 },
  { id: 2, arrivalTime: 1, burstTime: 3 },
  { id: 3, arrivalTime: 2, burstTime: 2 }
];

const queues = [
  { priority: 1, quantum: 2, algorithm: 'rr' },    // High priority: Round Robin
  { priority: 2, quantum: 4, algorithm: 'fcfs' }   // Low priority: FCFS
];

const result = scheduleMLQ(processes, queues);
console.log(result);

5. Multi-Level Feedback Queue (MLFQ)

import { scheduleMLFQ } from 'cpu-scheduler';

const processes = [
  { id: 1, arrivalTime: 0, burstTime: 8 },
  { id: 2, arrivalTime: 1, burstTime: 4 },
  { id: 3, arrivalTime: 2, burstTime: 2 }
];

const queues = [
  { priority: 1, quantum: 2, algorithm: 'rr' },    // Highest priority
  { priority: 2, quantum: 4, algorithm: 'rr' },    // Medium priority
  { priority: 3, quantum: 8, algorithm: 'fcfs' }   // Lowest priority
];

const result = scheduleMLFQ(processes, queues);
console.log(result);
// Processes can move between queues based on their behavior

API Reference

Types

Process

interface Process {
  id: number;           // Unique process identifier
  arrivalTime: number;  // Time when process arrives (≥ 0)
  burstTime: number;    // CPU burst time required (> 0)
}

PriorityProcess

interface PriorityProcess extends Process {
  priority: number;     // Process priority (lower = higher priority)
}

SchedulingResult

interface SchedulingResult {
  processes: ProcessResult[];  // Results for each process
  averages: Averages;         // Average waiting and turnaround times
  ganttChart: GanttEntry[];   // Process execution timeline
}

ProcessResult

interface ProcessResult extends Process {
  completionTime: number;   // Time when process completes
  turnaroundTime: number;   // Total time from arrival to completion
  waitingTime: number;      // Time spent waiting in ready queue
}

Averages

interface Averages {
  averageWaitingTime: number;     // Average waiting time across all processes
  averageTurnaroundTime: number;  // Average turnaround time across all processes
}

GanttEntry

interface GanttEntry {
  processId: number;  // ID of the process
  startTime: number;  // When execution starts
  endTime: number;    // When execution ends
}

QueueConfig

interface QueueConfig {
  priority: number;                    // Queue priority (lower = higher priority)
  quantum: number;                     // Time quantum for RR algorithm
  algorithm: 'fcfs' | 'sjf' | 'rr';   // Scheduling algorithm for this queue
}

Functions

Basic Scheduling Algorithms

scheduleFCFS(processes: Process[]): SchedulingResult

First Come First Served - processes execute in arrival order.

scheduleSJF(processes: Process[]): SchedulingResult

Shortest Job First (Non-preemptive) - processes with shorter burst times execute first.

scheduleSRTF(processes: Process[]): SchedulingResult

Shortest Remaining Time First (Preemptive) - process with shortest remaining time executes.

scheduleRoundRobin(processes: Process[], quantum: number): SchedulingResult

Round Robin - processes execute in circular fashion with fixed time quantum.

schedulePriority(processes: PriorityProcess[]): SchedulingResult

Priority Scheduling (Non-preemptive) - processes execute by priority (lower number = higher priority).

Advanced Scheduling Algorithms

scheduleMLQ(processes: Process[], queues: QueueConfig[]): SchedulingResult

Multi-Level Queue - processes assigned to different priority queues with different algorithms.

scheduleMLFQ(processes: Process[], queues: QueueConfig[]): SchedulingResult

Multi-Level Feedback Queue - processes can move between queues based on their behavior.

Utility Functions

calculateTurnaroundTime(completionTime: number, arrivalTime: number): number

Calculate turnaround time for a process.

calculateWaitingTime(turnaroundTime: number, burstTime: number): number

Calculate waiting time for a process.

calculateAverageWaitingTime(processes: ProcessResult[]): number

Calculate average waiting time across all processes.

calculateAverageTurnaroundTime(processes: ProcessResult[]): number

Calculate average turnaround time across all processes.

calculateProcessMetrics(process: Process & { completionTime: number }): ProcessResult

Calculate all metrics for a single process.

calculateAverages(processes: ProcessResult[]): Averages

Calculate both average waiting and turnaround times.

createGanttChart(ganttData: Array<{ processId: number; startTime: number; endTime: number }>): GanttEntry[]

Create Gantt chart entries from execution timeline.

Error Handling

The package includes comprehensive input validation:

// Invalid input examples that will throw errors:
scheduleFCFS([]);                    // Error: At least one process is required
scheduleFCFS(null);                  // Error: Processes must be an array
scheduleRoundRobin(processes, 0);    // Error: Quantum must be a positive number
schedulePriority([{ id: 1, arrivalTime: 0, burstTime: 5 }]); // Error: missing priority

Performance Comparison Example

import { 
  scheduleFCFS, 
  scheduleSJF, 
  scheduleSRTF, 
  scheduleRoundRobin 
} from 'cpu-scheduler';

const processes = [
  { id: 1, arrivalTime: 0, burstTime: 5 },
  { id: 2, arrivalTime: 1, burstTime: 3 },
  { id: 3, arrivalTime: 2, burstTime: 2 }
];

// Compare different algorithms
const fcfs = scheduleFCFS(processes);
const sjf = scheduleSJF(processes);
const srtf = scheduleSRTF(processes);
const rr = scheduleRoundRobin(processes, 2);

console.log('FCFS Average Waiting Time:', fcfs.averages.averageWaitingTime);
console.log('SJF Average Waiting Time:', sjf.averages.averageWaitingTime);
console.log('SRTF Average Waiting Time:', srtf.averages.averageWaitingTime);
console.log('RR Average Waiting Time:', rr.averages.averageWaitingTime);

Development

# Install dependencies
npm install

# Build the project
npm run build

# Run tests
npm test

# Run tests with coverage
npm run test:coverage

# Watch mode for development
npm run dev

Testing

The package includes 87 comprehensive tests covering:

• All 7 scheduling algorithms
• Edge cases and error conditions
• Input validation
• Calculation accuracy
• Type safety

Run tests with:

npm test
npm run test:coverage

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

1. Fork the repository
2. Create your feature branch (git checkout -b feature/amazing-feature)
3. Commit your changes (git commit -m 'Add some amazing feature')
4. Push to the branch (git push origin feature/amazing-feature)
5. Open a Pull Request

License

MIT © Rishi Tiwari

Repository

GitHub Repository

Changelog

v1.0.0

• Initial release
• 7 CPU scheduling algorithms implemented
• Complete TypeScript support
• Comprehensive test suite (87 tests)
• Full documentation and examples