Skip to content

Instantly share code, notes, and snippets.

@abbasEbadian
Last active May 12, 2021 11:35
Show Gist options
  • Select an option

  • Save abbasEbadian/729c4ee00e112ffa2310d82b0574b3b3 to your computer and use it in GitHub Desktop.

Select an option

Save abbasEbadian/729c4ee00e112ffa2310d82b0574b3b3 to your computer and use it in GitHub Desktop.
Non Preemptive SJF easy to understnad implementation with Python
# Check if all tasks have been executed
def check_all_done(tasks):
all_done = True
for task in tasks:
if tasks[task]["duration"] >0 :
all_done = False
break
return all_done
# Get the task with shortest remainig service time (duration)
def get_shortest_task(tasks, current_time):
task_list = [x for x in tasks if tasks[x]["arrival"] <= current_time]
return min(task_list,key=lambda x: tasks[x]["duration"])
# An alternative for queue, checks how many tasks can be executed at the moment of 'time'
def possible_tasks_count(tasks, time):
possibles = 0
for k, v in tasks.items():
if v["arrival"] <= time and v["duration"]> 0:
possibles += 1
return possibles
# Dummy data
tasks_count = 5
tasks = {
"p1": {
"arrival" : 2,
"duration": 6,
},
"p2": {
"arrival" : 5,
"duration": 2,
},
"p3": {
"arrival" : 1,
"duration": 8,
},
"p4": {
"arrival" : 0,
"duration": 3,
},
"p5": {
"arrival" : 4,
"duration": 4,
}
}
time = 0
current_task = None
total_wait_time = 0
# A string to pretty print execution order
process_text = ""
while not check_all_done(tasks):
current_task = get_shortest_task(tasks, time)
total_wait_time += possible_tasks_count(tasks, time) -1
tasks[current_task]["duration"] -= 1
if tasks[current_task]["duration"] == 0:
tasks.pop(current_task, None)
time += 1
process_text += f"{current_task} | "
print(process_text)
print("Total wait time: ",total_wait_time / tasks_count )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment