Saturday, March 28, 2015

Task Scheduler

Given the interface below, implement a task scheduler.
interface Task {
    void Run();
    Set<Task> GetDependencies();
}

Additionally, the task scheduler should follow two rules.
1. Each task may only be executed once.
2. The dependencies of a task should be executed before the task itself.

This one is quite straightforward. Given a set of task, using a DFS approach.


public class TaskScheduler {
 Set executed;
 Set allTasks;
 Set inProcess;
 public TaskScheduler(Set tasks){
  allTasks = tasks;
  executed = new HashSet();
  inProcess = new HashSet();
 }
 public void schedule(Set allTasks){
  for(Task t : allTasks){
   if(executed.contains(t))
    continue;
   if(!inProcess.isEmpty() && inProcess.contains(t)){
    t.Run();
    inProcess.remove(t);
    executed.add(t);
    continue;
   }
   inProcess.add(t);
   schedule(t.GetDependencies());
   t.Run();
   inProcess.remove(t);
   executed.add(t);
  }
 }
}


Now comes the second one:


implement the same task scheduler with parallel task execution.

So I am thinking, maybe it needs a concurrency approach. So I go back to my old posts and tried to come up an approach. Since all dependencies should be executed first, I use a stack to schedule all tasks. The scheduler will first add all its dependencies to the stack. Then I use a releaseCount to track the available resources. If releaseCount == 0 or if the current Task is not on top of the stack, it should wait for its turn. Pop the task out and execute it, while executing, the task has acquired the resource, so releaseCount should decrement by one, after executing, the task should release the resource, so releaseCount increment by one.

However, I am not sure if my approach is correct, so I have an open question on Stackoverflow.


public class TaskSchedulerParallel {
 Set executed;
 Stack scheduler;
 int releaseCount;
 //number of parallel nodes
 public TaskSchedulerParallel(int N){
  executed = new HashSet();
  scheduler = new Stack();
  releaseCount = N;
 }
 public synchronized void schedule(Task t) throws InterruptedException {
  scheduler.push(t);
  for(Task dep : t.GetDependencies()){
   if(!executed.contains(dep) && !scheduler.contains(dep))
    schedule(dep);
  }
  if(releaseCount == 0 || (!scheduler.isEmpty() && scheduler.peek() != t))
   t.wait();
  releaseCount--;
  scheduler.pop();
  t.Run();
  executed.add(t);
  releaseCount++;
 }
 

}

No comments:

Post a Comment