Assignment #6 Solution



  1. [40 points] ProblemSet

    1. [20 points] 5.10 Which of the following scheduling algorithms could result in starvation?Explain.

      1. First-come,first-served

      2. Shortest jobfirst

      3. Roundrobin

      4. Priority

    2. [20 points] 5.12 Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks. Describe the CPU utilization fora

round-robin scheduler when:

      1. The time quantum is 1millisecond

      2. The time quantum is 10milliseconds

  1. [60 points] ProgrammingExercise

In this programming exercise, you are to build a CPU scheduler that can compute the schedule for a variety of policies and calculate the various cost functions.

    1. FIFO and PriorityQueue

A fundamental data structure in any CPU scheduler is a queue. Here, it can refer to a FIFO (first-in first-out) queue, but it may also refer to a priority queue, a LIFO (last-in first-out, also known as a stack), etc. Unlike random-access memory, where the reader or writer provides the memory address explicitly, a queue keeps track of its own addresses and provides only

.get()and.put()methods for reading and writing one element at a time.The following class is provided as an example:

———- file “” ———-


definit(self, initList=[]): self.A = list(initList)

defget(self): #remove elementandreturn itsevalue

returnself.A.pop(0) # throws underflow exception if empty

defput(self,val): # addelementself.A.append(val)

defhead(self): # A[0] if not empty, None instead of underflow exception


defiter(self): #iterator overitselements

foriinself.A: #convertabletotuple, list, for-in loop,etc


deflen(self): #allows callertocall len(f) wheref isFIFO


defrepr(self): # shows a representation; we just show it as list


This will handle any data type. An example is (assume you save it in


>>>f =FIFO(range(3))

>>>f[0, 1,2]





In addition, we also provide an implementation of a priority queue based on min-heap. You

don’t get the source code but you can import it from the minheap.pyc file provided: (updated 10/27 17:30)

minheap.pyc(for python 2.7.13)minheap.pyc(for python 3.5.2)minheap.pyc(for python 3.5.3)minheap.pyc(for python 3.6.2)

It has the following API:

——– file “” ———–







defput(self, value):


defbuildheap(self): #reinitialize contentto beheapagain

One difference is that your minheap data structure typecasts its elements to tuples before comparison, and Python will compare tuples in lexicographical order, and we will exploit this characteristic later when prioritizing tasks to run.


>>>h = MinHeap()

>>>foriin[(2,3), (3,4), (2,4), (4,5), (5, 6)]: h.put(i)


[(2,3), (3, 4), (2, 4), (4, 5), (5,6)]

>>>h.get()(2, 3)


[(2, 4), (3, 4), (5, 6), (4, 5)]

>>>h.get()(2, 4)


[(3, 4), (4, 5), (5, 6)]


>>>h.get()(3, 4)


[(5, 6), (4, 5), (6, 7)]

    1. Task class [10points]

You need to declare aTaskclass for representing the properties of a task to be scheduled, including properties given by the user and additional data for bookkeeping purpose. Here, we use the term Task to mean the workload to be performed, with or without having a process or a thread attached to it. A thread or process may be recycled to run different tasks over time. But sometimes tasks and processes are used interchangeably when the task is attached to a process. The given data are passed as arguments to the constructors. You may use the following template to define your task. Look for the italicized comments to add your own code.

——— file “” : save and rename it as “” ———-


definit(self, name, release, cpuBurst):

# the task has a string name, release time and cpuBurst.

# the constructor may also need to initialize other fields,# forstatisticspurpose. Examplesinclude

# waiting time, remaining time, last dispatched time, and# completion time


# returns a string that looks like constructor syntax +'(%s,%d,%d)’%(repr(,\self.release,self.cpuBurst)



defsetPriorityScheme(self, scheme=”SJF”):”””

theschemecan be”FCFS”, “SJF”, “RR”,etc”””

self.scheme = scheme

if notscheme in _KNOWN_SCHEMES:

raiseValueError(“unknown scheme%s:mustbeFCFS, SJF,RR” %scheme)


# call this method to decrement the remaining time of this task


# returns the remaining time of this task


# returns a boolean for if this task has remaining work to do

defsetCompletionTime(self, time):

# record the clock value when the task is completed


# returns the turnaround time of this task, as defined on# slide 10 of week 7 lecture


# increment the amount of waiting time for this task


# returns the release time of this task


# this enables converting the task into a tuple() type so that

# the priority queue can just cast it to tuple before comparison.# it depends on thepolicy

if(self.scheme == ‘FCFS’):

t =# your tuple that defines thepriority

elif(self.scheme==’SJF’):#shortestjobfirstt =# your tuple that defines thepriority

elif(self.scheme == ‘RR’): # round robin

t =# your tuple that defines the priority


raiseValueError(“Unknown scheme %s” % self.scheme)



    1. Nonpreemptive Scheduler (20points)

    1. The NPScheduler class is instantiated with a policy and up to N time steps. Then the caller may add tasks to be scheduled, either as the scheduler runs or all at the beginning. The scheduler runs one time step at a time to fill in the Gantt chart with scheduled tasks. It also provides methods for the statistics. Use the following template (, rename it to make your scheduler




classNPScheduler: # nonpreemptive scheduler

definit(self, N, policy=’SJF’):

self.N=N #numberoftimestepstoscheduleself.running=None

self.clock=0 # thecurrent timestep beingscheduledself.policy=policy

# instantiate the readyQueue, which may be a FIFO or MinHeap# you may need additional queues for

# – tasks that have been added but not released yet# – tasks that have been completed

# – the Gantt chart

defaddTask(self, task):

# if the release time of the new task is not in the future, then# put it in ready queue; otherwise, put into not-ready queue.

# you may need to copy the scheduler policy into the task

defdispatch(self, task):

# dispatch here means assign the chosen task as the one to run# in the current time step.

# the task should be removed from ready-queue by caller;# The task may be empty (None).

# This method will make an entry into the Gantt chart and perform# bookkeeping, including

# – recording the last dispatched time of this task,

# – increment the wait times of those tasks not scheduled# but in the readyqueue


thisiscalledat thebeginningofscheduling each time steptoseeif newtasks became readyto bereleasedtoready queue, whentheirrelease timeis nolater thanthecurrentclock.



r = self.notReadyQueue.head()

# assuming the not-Ready Queue outputs by release time

ifrisNoneorr.releaseTime() > self.clock:


r =self.notReadyQueue.get() r.setPriorityScheme(self.policy) self.readyQueue.put(r)


# if there is a current running task, check if it has just finished.# (i.e., decrement remaining time and see if it has more work to do. # If so, perform bookkeeping for completing the task,

# – move task to done-queue, set its completion time and lastrun time# set the scheduler running task to None, and return True

# (so that a new task may be picked.)# but if not completed, return False.

# If there is no current running task, also return True.



# your codehere


# scheduler that handles nonpreemptive scheduling.

# thepolicy suchas RR,SJF,orFCFSishandledby thetaskasit#definestheattributetocompare(in itsiter()method)

#first, checkifaddedbutunreleased tasksmay now bereleased#(i.e., addedtoready queue)


ifself.checkTaskCompletion() == False:

#Thereis acurrent running taskand it is notdoneyet!# the same task will continue running to its completion.# simply redispatch the current running task.


# task completed or no running task.

# get the next task from priority queue and dispatch it.


# this method runs the scheduler one time step at a time.

forself.clockinrange(self.N): # now run scheduler here self.schedule()



return‘-‘.join(map(str, self.ganttChart))

deftestNPScheduler(tasks,policy):nClocks= 20

scheduler = NPScheduler(nClocks, policy)

fortintasks: scheduler.addTask(t)



print(‘nonpreemptive%s: %s’ %(scheduler.policy,scheduler.getSchedule()))

ifname ==’main‘:

tasks=[Task(*i)foriin[(‘A’,0, 7),(‘B’,2, 4),(‘C’,4, 1),(‘D’,

5, 4)]]

print(‘tasks = %s’ % tasks)

forpolicyin[‘SJF’, ‘FCFS’, ‘RR’]:

tasks=[Task(*i)foriin[(‘A’,0, 7),(‘B’,2, 4),(‘C’,4,1),

(‘D’, 5, 4)]]

testNPScheduler(tasks, policy)

——— Your output would look like this:


tasks=[Task(‘A’,0, 7),Task(‘B’,2, 4),Task(‘C’,4, 1),Task(‘D’,5,4)]

nonpreemptive SJF: A-A-A-A-A-A-A-C-B-B-B-B-D-D-D-D-None-None-None-None nonpreemptive FCFS:A-A-A-A-A-A-A-B-B-B-B-C-D-D-D-D-None-None-None-NonenonpreemptiveRR:A-A-A-A-A-A-A-B-B-B-B-C-D-D-D-D-None-None-None-None

    1. Preemptive Scheduler (20points)

For this part, make a copy of your nonpreemptive scheduler and make it a preemptive one. The overall structure is the same as the Nonpreemptive scheduler.

——– file “”, rename and save as “”

classPScheduler(NPScheduler):#subclass from nonpreemptive scheduler#this meansit caninherit

#init(),addTask(), dispatch(),releaseTasks()#clockGen(),getSchedule()


# this is the new method to add to put the running task

# back into ready queue, plus any bookkeeping if necessary.

defschedule(self): self.releaseTasks()#sameasbefore

ifself.checkTaskCompletion()==False:#still have operationto do.

# see if running task or next ready task has higher priority

#hint: comparebyfirst typecastingthetaskstotuple()first# andcompare themastuples. Thetuplesaredefinedin

# theiter()methodof theTask class basedonpolicy.

# ifnext readyis nothigher priority, redispatch currenttask.#otherwise,

# -swapoutcurrent running(bycalling preemptmethod)#task completedorswappedout

# pick next task from ready queue to dispatch, if one exists.

deftestPScheduler(tasks, policy):

#thisissameasbefore,butinstantiatethepreemptivescheduler.nClocks= 20

scheduler=PScheduler(nClocks,policy)# therestis thesameasbefore

fortintasks: scheduler.addTask(t)



print(‘preemptive %s: %s’ % (scheduler.policy, scheduler.getSchedule()))

ifname ==’main‘:

tasks = [Task(*i) for i in [(‘A’, 0, 7), (‘B’, 2, 4), (‘C’, 4, 1), (‘D’,

5, 4)]]

print(‘tasks = %s’ % tasks)

for policy in [‘SJF’, ‘FCFS’, ‘RR’]:

tasks=[Task(*i)for i in[(‘A’,0, 7),(‘B’,2, 4),(‘C’,4,1),

(‘D’, 5, 4)]]

testPScheduler(tasks, policy)

Your output would look like

tasks=[Task(‘A’,0, 7),Task(‘B’,2, 4),Task(‘C’,4, 1),Task(‘D’,5,4)]

preemptive SJF: A-A-B-B-C-B-B-D-D-D-D-A-A-A-A-A-None-None-None-None

preemptive FCFS: A-A-A-A-A-A-A-B-B-B-B-C-D-D-D-D-None-None-None-None

preemptie RR: A-A-B-A-B-C-A-D-B-A-D-B-A-D-A-D-None-None-None-None

    1. Add Statistics (10points)

Implement the following methods to the nonpreemptive scheduler code (and the preemptive one will automatically get the same code due to inheritance).


# throughput is the number of processes completed per unit time.

# returns a tuple for (number of done processes, number of clocks)


# returns a tuple for (total wait time of processes, #processes)


# returns a tuple for (total turnaround times, #processes)

Combine the nonpreemptive and preemptive schedulers into the same test bench and print out the statistics, so that the output looks like


tasks=[Task(‘A’,0, 7),Task(‘B’,2, 4),Task(‘C’,4, 1),Task(‘D’,5,4)]

nonpreemptive SJF: A-A-A-A-A-A-A-C-B-B-B-B-D-D-D-D-None-None-None-None

thruput = (4,

4) = 8.00

preemptive SJF:

16) =0.25, waittimes=(16,4) =4.00, turnaroundtime=



thruput = (4, 16) =0.25, waittimes=(12,4) =3.00, turnaroundtime=


4) = 7.00

nonpreemptive FCFS: A-A-A-A-A-A-A-B-B-B-B-C-D-D-D-D-None-None-None-None thruput= (4, 16) =0.25, waittimes=(19,4) =4.75, turnaroundtime=(35,

4) = 8.75

preemptive FCFS: A-A-A-A-A-A-A-B-B-B-B-C-D-D-D-D-None-None-None-None

thruput= (4, 16) =0.25, waittimes=(19,4) =4.75, turnaroundtime=(35,

4) = 8.75

nonpreemptiveRR:A-A-A-A-A-A-A-B-B-B-B-C-D-D-D-D-None-None-None-None thruput= (4, 16) =0.25, waittimes=(19,4) =4.75, turnaroundtime=(35,

4) = 8.75

preemptive RR: A-A-B-A-B-C-A-D-B-A-D-B-A-D-A-D-None-None-None-None

thruput= (4, 16) =0.25, waittimes=(22,4) =5.50, turnaroundtime=(38,

4) = 9.50