Shortest Remaining Time

[Benderbrau]

Hello, I've got a problem that I can't seem to figure out. I'm writing a program to simulate a process manager, and I'm doing four different algorithms: First come first serve, shortest job next, shortest remaining time, and round robin. I've got the first two down perfect, but I'm having trouble with shortest remaining time.

So I've got two lists:
arrive=[0,3,6,7,7,10,15,16]
exe=[12,3,11,1,4,5,20,7]

"arrive" is the arrival time of a job and "exe" is the execution duration. I can only process one job at a time, and for this algorithm the processor is allocated to the job closest to completion (as long as it has arrived).

So, for example, in my lists, a job arrives at time 0 with a duration of 12. Now, I would only process it for 3 times through because the next job arrives at 3 and it has a shorter execution duration.

Hopefully that makes sense. Basically I just need help setting something up. I've been adding the arrived items to their own list, with their execution duration in another. I can post my code for the other algorithms if it would help anyone. I could also post any code for this algorithm that I've attempted. Thanks!!!!

[woooee]

Is this logic correct?
arrive=[0, 3, 6, 7, 7, 10, 15, 16]
exe= [12, 3, 11, 1, 4, 5, 20, 7]

The first piece arrives at 0 and takes 12 units to complete, so if we add completion time, we have
arrive=[0]
exe=[12]
completion=[12]

arrive=[0, 3]
exe=[12, 3]
completion=[12, 6]
The second piece arrives at 3, and takes 3 units to complete=completes at 6. Since it's completion time is less than the first piece, work is done on it. So at the completion of the second piece, that is at "6", we have for this first piece:
arrive=[6] ## time now
exe=[9] ## units left --> 12-3
completion=[15]
etc.

So you would use a function to compute completion whenever a piece is added, or when one piece completes and take the lowest completion time?

[Benderbrau]

Yes, your logic seems to be correct. As for the completion list, I would want to compute it whenever a piece is added. I'll be back online in a few with some code...I went ahead and finished the fourth algorithm today since I already had it worked out on paper. I think I can get it working...it's just one of those things I have to wrap my brain around and scribble out pseudo code. Thanks for the help so far, it's giving me some new ideas!

[Benderbrau]

Alright, so remember "arrive" and "exe" are my two main lists. "arrived" is the list for jobs that have arrived, and "waitToExe" is the list for waiting job's execution duration. "msCount" is to count time (fake milliseconds).

def SRT(arrive,exe,arrived,waitToExe,msCount):
	tempArrived=[]
	tempWaitToExe=[]
	while arrived == []:
		a=0
		#print "Time: ",msCount,"ms"
		while a < len(arrive): #match an arrival time for the current msCount
			if arrive[a] == msCount:
				arrived.append(arrive[a])
				waitToExe.append(exe[a])
			a+=1
		msCount+=1
	while sum(waitToExe) != 0: #while the sum of waiting's execution duration is NOT zero...
		#print "----------------------------" #this was commented out since it's looping
		#print arrived
		#print waitToExe
		#print "----------------------------"
		n=0
		while n<len(waitToExe): #for length of waiting...
			sortWaitToExe = sorted(waitToExe) #sort to get smallest job duration
			if waitToExe[n] == sortWaitToExe[0] and waitToExe[n]!=0: #if current item = the lowest item in the sorted list
				print "Processing item! Time: ",msCount #"process"
				print arrived
				print waitToExe
				waitToExe[n] = waitToExe[n]-1 #subtract one "ms" from waiting duration
				sortWaitToExe[0] = sortWaitToExe[n]-1 #subtract one "ms" from first sorted item
				msCount+=1 #add to count
				a=0
				while a < len(arrive):  #then check again if any new jobs have arrived....
					if arrive[a] == msCount:
						tempArrived.append(arrive[a])
						tempWaitToExe.append(exe[a])
					a+=1
				for item in tempWaitToExe:  #if an item in temp list is larger than an item in the real list, then break loop
					if item<sortWaitToExe[0]:
						n=len(waitToExe)
			n+=1
		for item in tempArrived:
			arrived.append(item) #add temp items
		for item2 in tempWaitToExe:
			waitToExe.append(item2) #same...
		tempArrived=[] #clear temp list
		tempWaitToExe=[]#same

Anyway, this works fine until it finishes the second job and for some reason it croaks.

[Benderbrau]

Oops, ignore line 26...I'm really tired.

[woooee]

It appears that the problem is here
while sum(waitToExe) != 0: #while the sum of waiting's execution duration is NOT zero...

You subtract from waitToExe, but not until it reaches zero. It appears that you only subtract once for each "n".

while n<len(waitToExe): #for length of waiting...
         sortWaitToExe = sorted(waitToExe) #sort to get smallest job duration
         if waitToExe[n] == sortWaitToExe[0] and waitToExe[n]!=0: #if current item = the lowest item in the sorted list
            print "Processing item! Time: ",msCount #"process"
            print arrived
            print waitToExe
            waitToExe[n] = waitToExe[n]-1 #subtract one "ms" from waiting duration

Also, you do not return arrived or waitToExe from the function, so they should be returned or should just be defined by the function. I would suggest using a few functions instead on one long block of code to pinpoint the errors to a small function.

[Benderbrau]

Thanks a lot for the help...I'll clean it up and see if I can it working. I'll post back soon.

[woooee]

This appears to work, but is still rough and just a proof of concept. It adds the unit to a dictionary as it's arrive time is reached, so that any finished units can be deleted from the dictionary as well. So a unit is processed until it is finished or until the next arrive time is reached. At the end the remaining units are processed in the order received but can be sorted and processed in any other order. The toughest part of this is to break it into small enough pieces that can be easily coded.

import datetime
import time

""" Results Should Be The Following: 
    arrive=[0,3,6,7,7,10,15,16]
    exe=[12,3,11,1,4,5,20,7]

Num  Process   Time     Time
      Time   Remaining   Now
0               12        0  added
0       3        9        3
1                3           added
1       3        0        6  #1 Finished
2               11           added
0       1        8        7
3                1           added
4                4           added
3       1        0        8  #3 Finished
4       2        2       10
5                5           added
4       2        0       12  #4 Finished
5                5
5       3        2       15
6               20           added
5       1        1
"""

class ProcessUnit:
    def __init__(self, arrive, exe):
        unit_to_process = {}
        ctr = 0
        unit_number = 0
        time_now = 0
        next_start_time = 0
        add_ctr = 0
        stop = len(arrive) - 2

        ## add first unit to start the process
        unit_to_process[add_ctr] = [ arrive[add_ctr], exe[add_ctr] ]
        while add_ctr < stop:
            ctr += 1
            if ctr > 500:     ## limit to 500 cycles
                add_ctr = stop +1

            print "\n", "-"*60

            ## add next unit to the dictionary ?
            if arrive[add_ctr+1] <= time_now:
                add_ctr += 1
                unit_to_process[add_ctr] = [ arrive[add_ctr], exe[add_ctr] ]
                print "added #", add_ctr
                next_start_time = arrive[add_ctr+1]
            print unit_to_process

            ##  initialize stop time = next start time - time now
            stop_time = arrive[add_ctr+1] - time_now
##            print "initialize stop time", arrive[add_ctr+1], time_now
            if stop_time < 0:      ## two units arrive at same time
                stop_time = 99999

            ##  find smallest completion time and compare to
            ##  the current stop time (next arrive time)
            smallest = 99999
            for key in unit_to_process:
##               print "time remaining", unit_to_process[key][1], stop_time
               if unit_to_process[key][1] < smallest:
                   smallest = unit_to_process[key][1]
                   unit_number = key   # process smallest unit no matter how long the time is

            if smallest < stop_time:
                stop_time = smallest

            print "processing next unit, stop_time", stop_time, "unit number", unit_number
            self.process_unit(stop_time)
            time_now += stop_time
            unit_to_process[unit_number][0] += stop_time
            unit_to_process[unit_number][1] -= stop_time

            ##  if completed, delete from dictionary
            if unit_to_process[unit_number][1] < 1:
                print "dictionary delete key", unit_number
                del unit_to_process[unit_number]


        ## add last unit and process remaining in order received
        print "\n-------- processing remaining units ----------------"
        add_ctr += 1
        unit_to_process[add_ctr] = [ arrive[add_ctr], exe[add_ctr] ]
        print unit_to_process, "\n"

        units = unit_to_process.keys()
        units.sort()
        for key in units:
            print "unit =", key, "  time =", unit_to_process[key][1]
            self.process_unit(unit_to_process[key][1])


    def process_unit(self, time_to_process):
        print "     ",
        for n in range(0, time_to_process):
            time.sleep(1.0)
            print n,
        print

##===================================================================
arrive=[0,3,6,7,7,10,15,16]
exe=[12,3,11,1,4,5,20,7]

start_time = datetime.datetime.now()
P = ProcessUnit(arrive, exe)
print "\n", datetime.datetime.now() - start_time

[majid_shqeer]

there is an error in the last SJF

[majid_shqeer]

## add last unit and process remaining in order received print "\n-------- processing remaining units ----------------"
in this step the error