Python CPU Scheduler Simulator

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))