I. Shortest Job First CPU Scheduling (7pts) In this exercise you will be modifying the CPU!time slicing program that we discussed in class so that it implements a shortestjobfirst (SJF) scheduling algorithm instead. Answer the questions about the algorithm, and then follow the steps to write the code.

1) Shortest Job First is a CPU scheduling algorithm that removes the shortest job from the process queue and executes it first. It keeps doing this until all of the processes are executed.

What might be an advantage of this algorithm?

What might be a disadvantage of this algorithm?

2) Download the code for the CPU time slicing program: http://www.cs.uri.edu/~cingiser/csc110/handouts/python/cpu_timeslice.py

There is one important difference between the implementation of a time sliceCPU scheduling algorithm and a SJF CPU scheduling algorithm: the Queue data structure used in the time slice program is designed for FIFO access it only allows you to get the process at the end of the queue. To implement SJF you will need to use a list to store the processes so that we can get the shortest job to process. The main changes you will have to make to the program are:

a) The function to get the data from the file should return two lists (a list of processes and a list of execution times) instead of a single list with both.

b) The function to schedule process will choose the next process by finding the shortest execution time from the lists. It will replace the queue data structure with the pair of lists.

c) You will have to write a function to find the shortest process from the and remove it.

3) Get the data from the file:

To get you started, we provide the function for getting the two lists from the file:

def getProcs():

fname = input("Enter the name of the data file")

infile = open(fname, 'r')

procList = []

execList = []

# Loop through the file inserting processes into the list

for line in infile:

line = line.strip()

proc, eTime = line.split(',')

procList = procList + [proc]

execList = execList + [int(eTime)]

infile.close()

return procList, execList

Modify the cpu_timeslice.py program so that it uses this function to get the data Instead of the one that inserts the data into a queue. Now modify the main so that all it does is call the getProcs() function!and then print the two lists.

Use this file to test your code: http://www.cs.uri.edu/~cingiser/csc110/handouts/python/sjf_processes.txt

When you have this much done, test your program to make sure it works so far.

4) Find the shortest process: The next step is to write a function that finds the shortest process to execute. The function will take as a parameter the list of execution times, and return the POSITION in the list of the shortest time. The skeleton for the function!looks like this:

def findShortestProcess(execList):

# Given a list of process execution times

# (execList), find the position of the shortest

# time in the list and return it

return shortestPos

When you have this function working, add it to the program. Then add to your main function a call to the findShortestProcess function. To make sure it is working correctly, also add to the main a couple of print statements to print the process ID of the shortest process. Test the program again to make sure this much works so far.

5) Schedule!the!processes:

Finally, we will modify the function that schedules the processes.In the original code for the time slice algorithm, the scheduleProcs function takes the processes out of a queue and runs them one at a time.In this program, we will be taking processes out of the two lists (execList, procList), one at a time, shortest first.

Python provides a builtBin function pop() that removes an element from a list given the index (position) of the element. So, if you have a list created like this:

myList = [a, b, c, d]

and you use the command:

myList.pop(1)

the function removes the list item at position 1, and the result would be:

[a, c, d]

Using this function and the findShortestProcess function, modify the scheduleProcs function so that it takes as parameters the two lists, and executes the processes using the Shortest(Job(First algorithm. The signature for the function should!be:

def scheduleProcs(procList, execList):

# The code should look similar to the timeslice

# program except now you will loop through until

# the procList is empty and each time through the

# loop, find the shortest process, execute the

# shortest process, and then remove the shortest

# process from both lists.

return

Finish the program by making sure you call the functions correctly from the main function. Be sure to include enough print statements to indicate which process is executing its instructions.

II. Dining Philosophers

In this exercise, we will experiment with the Dining Philosophers program that we discussed in class.

Download it from here: http://www.cs.uri.edu/~cingiser/csc110/handouts/python/simple_dining_phils.py

Recall that this program cannot run from IDLE because it uses multiple processes. So lets run it from the command line. The instructions here are for a Mac, but if you use a Windows machine, just open the command window, and the rest should be the same

a) Download the file and save it to the desktop.

b) From the Applications folder, open the Utilities folder and run Terminal.

c) You will need to change directories to the desktop. Do this by typing:

cd desktop

d) Make sure your dining philosophers program is in this directory by typing:

ls

to list the contents of the directory(that is the letter l not the number one). You should see the file simple_dining_phils.py listed.

e) Run the program using Python version 3.2 by typing:

python3 simple_dining_phils.py

You should see the output of the program, which is information about the philosophers and what they are doing.

Did deadlock occur when you ran the program? Explain why.

If the program did deadlock, make a change to the code to fix it.If the code did not deadlock, make a change to the code to make deadlock occur