CPU Scheduling Algorithms - JavaScript

In this post, I am going to share a JavaScript simulation for some well-known CPU/operation system scheduling algorithms. The ES6 JavaScript code can be run in the Node JS environment.

The Task

To begin with, we need some kind of CPU occupying task. Here’s one:

class Task {
  constructor(name, iterations) {
    this.name = name
    this.index = 0;
    this.iterations = iterations;
  }

  run() {
    this.index++;
    process.stdout.write(this.name + " " + Math.floor((this.index / this.iterations) * 100) + "% \r");
  }

  onFinish() {
    console.log(this.name + " 100%")
  }
}

In the constructor, we take task name, current running index, and the total number of iterations the task will take to complete.

Its run method simply increments the index field by 1 and prints the current percentage of progress. Using process.stdout.write and “\r” in the end lets us update the same printed line in the terminal/console.

onFinish is called to print the final message success message when the task completes.

The Scheduler

The scheduler will also be a class with the array of queued tasks it needs to process. It will have a run method that will have the algorithm to switch between the running tasks. Each algorithm will have a modified run method.

class Scheduler {
  constructor() {
    this.tasks = []; // the queued tasks
  }

  addTask(task) {
    this.tasks.push(task)
  }

  run() {
    while (){
      // the scheduling algorithm will come here
    }
  }
}

Note that in this simulation you won’t be able to add a new task during the while loop execution since it will have synchronously occupied/blocked the running thread.

Now, to the algorithms:

1. First Come First Serve (FCFS)

The most basic scheduling algorithm runs and completes the tasks in the order they were added.

In the while loop below, we continue the loop if the tasks array is not empty.
Next, we check if the task’s current index is smaller than its total iterations. If so, it means the task is not complete, and we invoke its run method.
Else we call its finish method and remove the task from the queue. The next while iteration will pick up the new task.

class Scheduler {
  // ...
  run() {
    while (this.tasks.length) {
      if (this.tasks[0].index < this.tasks[0].iterations) {
        this.tasks[0].run();
      }
      else {
        this.tasks[0].onFinish()
        this.tasks.shift();
      }
    }
  }
}

const scheduler = new Scheduler();

scheduler.addTask(new Task("A", 1000000));
scheduler.addTask(new Task("B", 3000000));
scheduler.addTask(new Task("C", 4000000));
scheduler.addTask(new Task("D", 2000000));

scheduler.run();

The result will be:

A 100% 
B 100% 
C 100% 
D 100%

2. Round Robin

In this algorithm, we give each task the same allocated chunk of time, no matter which task comes first. Unless the task is really small, it will be interrupted several times before it gets finally finished.

We modify the scheduler class to take timeSlotPerTask in the constructor. We also keep and check against the lastSetDate field in the run method to cut off the running task if it has exceeded the time per slot.

class Scheduler {
  constructor(timeSlotPerTask) {
    this.tasks = [];
    this.timeSlotPerTask = timeSlotPerTask;
  }

  addTask(task) {
    this.tasks.push(task)
  }

  run() {
    let lastSetDate = Date.now();
    while (this.tasks.length) {
      if (Date.now() - lastSetDate > this.timeSlotPerTask) {
        this.tasks.push(this.tasks.shift());
        lastSetDate = Date.now();
        if (this.tasks.length > 1) {
          console.log("");
        }
      }
      if (this.tasks[0].index < this.tasks[0].iterations) {
        this.tasks[0].run();
      }
      else {
        this.tasks[0].onFinish();
        this.tasks.shift();
      }
    }
  }
}


const scheduler = new Scheduler(1000); // time per slot will be 1 second

scheduler.addTask(new Task("A", 1000000));
scheduler.addTask(new Task("B", 2000000));
scheduler.addTask(new Task("C", 1000000));
scheduler.addTask(new Task("D", 3330000));

scheduler.run();

In the result below notice how all tasks are given 1 second each for processing, and they take turns before getting fulling complete.

A 51% 
B 28% 
C 59% 
D 17% 
A 100% 
B 33% 
C 100% 
D 22% 
B 57% 
D 38% 
B 84% 
D 54% 
B 100% 
D 100%

3. Shortest Job First (SJF)

As apparent from the name, the SJF always runs and completes the smallest task first. From the previous algorithms, we need to add task sorting based on their iteration size.

class Scheduler {
  // ...
  sort() {
    this.tasks.sort((a, b) => a.iterations - b.iterations); // sort by the smallest "iterations"
  }

  run() {
    this.sort(); // sort once before while loop
    while (this.tasks.length) {
      if (this.tasks[0].index < this.tasks[0].iterations) {
        this.tasks[0].run();
      }
      else {
        this.tasks[0].onFinish();
        this.tasks.shift();
        this.sort(); // sort before starting next cycle, in case a new task was added to the list
      }
    }
  }
}


const scheduler = new Scheduler();

scheduler.addTask(new Task("A", 100000));
scheduler.addTask(new Task("B", 200000));
scheduler.addTask(new Task("C", 1000));
scheduler.addTask(new Task("D", 2000));

scheduler.run();

The completion order will be C -> D -> A -> B:

C 100% 
D 100% 
A 100% 
B 100%

4. Shortest Remaining Time First (SRTF)

In terms of execution, the SRTF algorithm is exactly similar to Shortest Job First (SJF) above, except for the sort method, which sorts based on the remaining task pending.

sort() {
  // total iterations minus index gives us pending task/iterations
  this.tasks.sort((a, b) => (a.iterations - a.index) - (b.iterations - a.index)); 
}

5. Priority

The algorithm decides which task to take up from the queue based on the priority assigned to it. For its implementation, we take an additional priority parameter in the constructor and assign it a default value of 1. In the Scheduler class, we sort by priority

(Here, we’re assuming 1 to be of the highest priority, then 2, 3, and so on.)

class Task {
  constructor(name, iterations, priority = 1) {
    this.name = name
    this.index = 0;
    this.iterations = iterations;
    this.priority = priority;
  }
  // ...
};

class Scheduler {
  // ...
  sort() {
    this.tasks.sort((a, b) => a.priority - b.priority)
  }

  run() {
    this.sort();
    while (this.tasks.length) {
      if (this.tasks[0].index < this.tasks[0].iterations) {
        this.tasks[0].run();
      }
      else {
        this.tasks[0].onFinish();
        this.tasks.shift();
        this.sort();
      }
    }
  }
}


const scheduler = new Scheduler();

scheduler.addTask(new Task("A", 100000, 3));
scheduler.addTask(new Task("B", 200000, 2));
scheduler.addTask(new Task("C", 1000, 4));
scheduler.addTask(new Task("D", 2000, 1));

scheduler.run();

The result:

D 100% 
B 100% 
A 100% 
C 100%

javascript algorithms