# Implementing an algorithm for parallel task scheduling

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"

1. 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.

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

3. 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

}
``````
• If there are two applications with the same execution cost `Ex` and they start executing immediately, does it take exactly `2*Ex` time for both of them to finish? (I asked this because the execution cost and the division of CPU time among different applications aren't explained clearly in your question.) – rwong Apr 19 '16 at 10:54
• Also, every aspect in the question appears to be of an "eager strategy", as long as resource permits. I don't see any aspect of "optimization". Is this question a scenario simulation question, and not an optimization algorithm question? – rwong Apr 19 '16 at 10:56
• @rwong This is a first iteration of my simulator so I am ignoring a lot of things. So if there are two applications and they start executing immediately then both of them take Ex times individually i.e. A1 Finishing time= Ex and A2 Finishing time=Ex. – bbbbbbbbbb Apr 19 '16 at 11:51