So I have a FCFS and SJF CPU simulator scheduling algorithm, however I'm struggling to implement shortest remaining time first algorithm.
This is what I have so far.
def srtf(submit_times, burst_times):
"""First Come First Serve Algorithm returns the time metrics"""
cpu_clock = 0
job = 0
response_times = []
turn_around_times = []
wait_times = []
total_jobs = []
remaining_burst_times = []
for stuff in range(len(submit_times)):
total_jobs.append(tuple((submit_times[stuff], burst_times[stuff])))
remaining_burst_times.append(burst_times[stuff])
while job < len(submit_times):
if cpu_clock < int(submit_times[job]):
cpu_clock = int(submit_times[job])
ready_queue = []
for the_job in total_jobs:
job_time = int(the_job[0])
if job_time <= cpu_clock:
ready_queue.append(the_job)
short_job = ready_queue_bubble(ready_queue)
submit, burst = short_job[0], short_job[1]
next_event = cpu_clock + int(burst)
response_time = cpu_clock - int(submit)
response_times.append(response_time)
remaining_burst_times[job] = next_event - cpu_clock
# cpu_clock = next_event
if remaining_burst_times[job] == 0:
turn_around_time = next_event - int(submit)
wait_time = turn_around_time - int(burst)
turn_around_times.append(turn_around_time)
wait_times.append(wait_time)
else:
pass
job += 1
total_jobs.remove(short_job)
remaining_burst_times.remove(short_job[1])
return response_times, turn_around_times, wait_times
Basically the function takes in a list of submit times and burst times and returns lists for the response, turn around and wait times. I have been trying to edit remnants from my short job first with a ready queue, to no avail.
Can anyone point me in the right direction?
1 Answer
It's not a very simple simulation due to preemption. Designing simulations is all about representing 1) the state of the world and 2) events that act on the world.
State of the world here is:
Processes. These have their own internal state.
- Submit time (immutable)
- Burst time (immutable)
- Remaining time (mutable)
- Completion time (mutable)
Wall clock time.
Next process to be submitted.
Running process.
Run start time (of the currently running process).
Waiting runnable processes (i.e. past submit with remaining > 0).
There are only two kinds of events.
- A process's submit time occurs.
- The running process completes.
When there are no more processes waiting to be submitted, and no process is running, the simulation is over. You can get the statistics you need from the processes.
The algorithm initializes the state then gets executes a standard event loop:
processes = list of Process built from parameters, sorted by submit time
wall_clock = 0
next_submit = 0 # index in list of processes
running = None # index of running process
run_start = None # start of current run
waiting = []
while True:
event = GetNextEvent()
if event is None:
break
wall_clock = event.time
if event.kind == 'submit':
# Update state for new process submission.
else: # event.kind is 'completion'
# Update state for running process completion.
An important detail is that if completion and submit events happen at the same time, process the completion first. The other way 'round makes update logic complicated; a running process with zero time remaining is a special case.
The "update state" methods adjust all the elements of the state according to the srtf algorithm. Roughly like this...
def UpdateStateForProcessCompletion():
# End the run of the running process
processes[running].remaining = 0
processes[running].completion_time = wall_clock
# Schedule a new one, if any are waiting.
running = PopShortestTimeRemainingProcess(waiting)
run_start_time = clock_time if running else None
A new submit is more complex.
def UpdateStateForProcessCompletion():
new_process = next_submit
next_submit += 1
new_time_remaining = processes[new_process].remaining
# Maybe preempt the running process.
if running:
# Get updated remaining time to run.
running_time_remaining = processes[running].remaining - (wall_clock - run_start)
# We only need to look at new and running processes.
# Waiting ones can't win because they already lost to the running one.
if new_time_remaining < running_time_remaining:
# Preempt.
processes[running].remaining = running_time_remaining
waiting.append(running)
running = new_process
run_start_time = wall_clock
else:
# New process waits. Nothing else changes
waiting.append(new_process)
else:
# Nothing's running. Run the newly submitted process.
running = new_process
run_start_time = wall_clock
The only thing left is getting the next event. You need only inspect processes[next_submit].submit and wall_clock + processes[running].remaining. Choose the smallest. The event has that time and the respective type. Of course you need to deal with the cases where next_submit and/or running are None.
I may not have everything perfect here, but it's pretty close.
Addition
Hope you're done with your homework by this time. This is fun to code up. I ran it on this example, and the trace matches well. Cheers
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))