CPU scheduler in python

The problem of CPU scheduler in python

We will learn how to develop code for several operating system scheduling algorithms in this blog. In other words, we’ll use Python to simulate the CPU scheduler. The algorithm we’ll use is the shortest path left to travel first.

Solution

The simulation is not very simple because of preemption. The condition of the world as it is right now and the events that have shaped it are the two major elements of simulation design.

The current state of the world is:

Processes:  They each have a unique internal state.

• Give time (immutable)
• Burst period (immutable)
• Time left to go (mutable)
• Time to completion (mutable)

1. clock time on a wall.
2. The process needs to get submitted after that.
3. operating procedure
4. running time (of the currently running process).
5. awaiting runnable processes (i.e., submitted but with more than zero seconds left).

Only two different types of events exist.

• The submission time of a procedure happens.
• The ongoing procedure finishes.

When there are no longer any processes running and no new processes waiting to be submitted, the simulation is over. You can get the statistics you need from the processes. Before beginning a standard event loop, the method first initializes the state and then continues till the procedure is complete. Below is the code for the same:

import heapq as pq

class Process(object):
  """A description of a process in the system."""
  def __init__(self, id, submit, burst):
    self.id = id
    self.submit = submit
    self.burst = burst
    self.remaining = burst
    self.completion = None
    self.first_run = None

  @property
  def response(self):
    return None if self.first_run is None else self.first_run - self.submit

  @property
  def turnaround(self):
    return None if self.completion is None else self.completion - self.submit

  @property
  def wait(self):
    return None if self.turnaround is None else self.turnaround - self.burst
 
  def __repr__(self):
    return f'P{self.id} @ {self.submit} for {self.burst} ({-self.remaining or self.completion})'


def srtf(submits, bursts):
  # Make a list of processes in submit time order.
  processes = [Process(i + 1, submits[i], bursts[i]) for i in range(len(submits))]
  processes_by_submit_asc = sorted(processes, key=lambda x: x.submit)
  process_iter = iter(processes_by_submit_asc)
  
  # The state of the simulation:
  wall_clock = 0  # Wall clock time.
  next_submit = next(process_iter, None)  # Next process to be submitted.
  running = None  # Running process.
  run_start = None  # Time the running process started running.
  waiting = []  # Heap of waiting processes. Pop gets min remaining.
 
  def run(process):
    """Switch the running process to the given one, which may be None."""
    nonlocal running, run_start
    running = process
    if running is None:
      run_start = None
      return
    running.first_run = running.first_run or wall_clock
    run_start = wall_clock

  while next_submit or running:
    print(f'Wall clock: {wall_clock}')
    print(f'Running: {running} since {run_start}')
    print(f'Waiting: {waiting}')

    # Handle completion first, if there is one.
    if running and (next_submit is None or run_start + running.remaining <= next_submit.submit):
      print('Complete')
      wall_clock = run_start + running.remaining
      running.remaining = 0
      running.completion = wall_clock
      run(pq.heappop(waiting)[1] if waiting else None)
      continue

    # Handle a new submit, if there is one.
    if next_submit and (running is None or next_submit.submit < run_start + running.remaining):
      print(f'Submit: {next_submit}')
      new_process = next_submit
      next_submit = next(process_iter, None)
      wall_clock = new_process.submit
      new_time_remaining = new_process.remaining
      if running:
        # Maybe preempt the running process. Otherwise new process waits.
        running_time_remaining = running.remaining - (wall_clock - run_start)
        if new_time_remaining < running_time_remaining:
          print('Preempt!')
          running.remaining = running_time_remaining
          pq.heappush(waiting, (running_time_remaining, running))
          run(new_process)
        else:
          pq.heappush(waiting, (new_time_remaining, new_process))
      else:
        run(new_process)

  for p in processes:
    print(f'{p} {p.response} {p.turnaround} {p.wait}')

  return ([p.response for p in processes],
          [p.turnaround for p in processes],
          [p.wait for p in processes])


submits = [6,3,4,1,2,5]
bursts = [1,3,6,5,2,1]
print(srtf(submits, bursts))

Output

Also Read: AlphaFold : Accurate protein structure prediction