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)
- clock time on a wall.
- The process needs to get submitted after that.
- operating procedure
- running time (of the currently running process).
- 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:
"""A description of a process in the system."""
def __init__(self, id, submit, burst):
return None if self.first_run is None else self.first_run - self.submit
return None if self.completion is None else self.completion - self.submit
return None if self.turnaround is None else self.turnaround - self.burst
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.
"""Switch the running process to the given one, which may be None."""
nonlocal running, run_start
running.first_run = running.first_run or 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):
wall_clock = run_start + running.remaining
running.completion = wall_clock
run(pq.heappop(waiting)[1] if waiting else None)
# 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
# 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:
running.remaining = running_time_remaining
pq.heappush(waiting, (running_time_remaining, running))
pq.heappush(waiting, (new_time_remaining, new_process))
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])
print(srtf(submits, bursts))
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))
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