Implementing an algorithm for parallel task scheduling

Question

Problem

Given a set of applications "A[]" with execution cost "Ex" ,Arrival Time "t", Resource requirements "R" and the system having free resources "Fr", calculate the finishing time of all of the applications.

Important Restrictions

1. Every application will try to execute in parallel given that the following conditions are true:

a). Arrival Time "t" >= Current Time

b). Resources requirements "R" <= Free system resources "Fr"

2. If a set of applications are executing and condition "a" becomes true for a new application but condition "b" is not yet true then the new application must wait for some of the applications to finish till it has enough free resources to start.

3. As soon as an application is "scheduled", the free system resources must be updated i.e Fr-R

4. As soon as an application is finished then the free system resources must be given back to the system i.e Fr+R

Condition "a" is quite simple to check but I am stuck at condition "b". The problem is that how to find the appropriate waiting and finishing times of an application given that the execution is instantaneous i.e. We dont want to wait two hours for the algorithm if the execution cost of an application is 2 hours. The finishing time of an application is simple addition i.e startTime+ExecutionCost. startTime can be different from arrival time given that an application must wait for free resources.

Incomplete Algorithm

This is what I have so far. The finishing times are wrong as they dont account for the time an application must spent waiting for free resources. I am also not updating the virtual time anywhere as I am not sure when to update that.

for(int i=0; i< A.size();i++){ if(A.arrivalTime>=virtualTime) { submit(A[i]) } } Submit(Application A){ if(A.requiredResources<=SystemResources){ A.startTime=virtualTime Schedule(A) } } Schedule(Application A){ A.finishingtime=A.startTime+A.ExecutionCost }