Reentrant lock & field in interface

I looked back to my last week's unsolved problem in this blog:

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.

Reentrant lock
So the question is, what if we run it in parallel. Naturally I thought about concurrency. However, when I tried to write a synchronized method for the problem, I realized that there is a recursion in my method. So I wondered: will it cause a deadlock?

The answer is no.

Recall that a thread cannot acquire a lock owned by another thread. But a thread can acquire a lock that it already owns. Allowing a thread to acquire the same lock more than once enables reentrant synchronization. This describes a situation where synchronized code, directly or indirectly, invokes a method that also contains synchronized code, and both sets of code use the same lock. Without reentrant synchronization, synchronized code would have to take many additional precautions to avoid having a thread cause itself to block.

In short, if I have a synchronized recursion method, when the method invokes itself again, it will transfer the lock to the recursive method, executing that first, then the lock is returned to the current method. Java does provide an explicit ReentrantLock class, if you are interested, take a look at the source code.

The fields in an interface
Since I need to implement the Task interface provided by the problem statement for test, I wrote a Trsk class. When I tried to print the label I defined in the Trsk class of a instance of the Task interface,  I got an error. So I thought, ok, maybe I should add the field label into the Task. However, for an interface, all fields are automatically public, static and final, and all methods are public.
There are two solutions to solve the problem:
1. Declare a Trsk object in my TaskSechduler class;
2. Cast Task to Trsk object when I need to access the Trsk fields and methods.

I choose the second one.

Back to the problem
Here is the simple dependency graph of my test code. a -> b indicates a is dependent on b.

So this problem, I wrote a synchronized method, and another class ExecuteTask and created two Threads to run. And here is the result:

Yep, Thread 1 never gets a chance to executing any Tasks. Since in my random test graph, everyone is sort of dependent on everyone, Task 6 (which doesn't depend on anyone) is executed first. And since it is in Thread 2, which leads Thread 2 always acquires the lock and executes tasks, until all tasks are executed. And when it comes to Thread 1's turn, it realizes that there is nothing left (Thanks Thread 2 for being very hard working!).

In order to let Thread 1 to get some job, I removed "synchronized" keyword:

First run

Second run

Third run

Now it's all about who is more aggressive. However, do notice that this will cause some order problems since we have no idea who is accessing the recourse.

The intuition here is that when you need to run parallel, be careful if you have some rules on the order.

The code

public class TaskSchedulerParallel {
 Set executed;
 Set inProcess;
 public TaskSchedulerParallel(){
  executed = new HashSet();
  //executed = Collections.synchronizedSet(new HashSet());
  inProcess = new HashSet();
  //inProcess = Collections.synchronizedSet(new HashSet());
 }
 public void schedule(Task t){
 //public synchronized void schedule(Task t) {
  inProcess.add(t);
  /*for(Task ta : executed)
   System.out.print(((Trsk)ta).label + " ");
  System.out.println();*/
  for(Task dep : t.GetDependencies()){
   if(!executed.contains(dep) && !inProcess.contains(dep))
    schedule(dep);
  }
  if(executed.add(t)){
   t.Run();
   inProcess.remove(t);
  }
 }
}
public class ExecuteTask implements Runnable{
 private TaskSchedulerParallel tsp;
 private Set toExecute;
 private int label;
 public ExecuteTask(int label, TaskSchedulerParallel tsp, Set tasks){
  this.tsp = tsp;
  toExecute = tasks;
  this.label = label;
 }
 @Override
 public void run() {
  System.out.println("Thread: " + label);
  for(Task t : toExecute){
   tsp.schedule(t);
  }
  System.out.println("Thread " + label + " finishes!");
 }
}
public class Trsk implements Task{
 int label;
 Set dependencies = new HashSet();
 public Trsk(int label){
  this.label = label;
 }
 @Override
 public void Run() {
  System.out.println(label + " is running!");
 }
 public boolean addDependency(Task t){
  return dependencies.add(t);
 }
 @Override
 public Set GetDependencies() {
  return dependencies;
 }
 

}
public class TaskTester {

 public static void main(String[] args) {
  TaskSchedulerParallel tsp = new TaskSchedulerParallel();
  Task t1 = new Trsk(1);
  Task t2 = new Trsk(2);
  Task t3 = new Trsk(3);
  Task t4 = new Trsk(4);
  Task t5 = new Trsk(5);
  Task t6 = new Trsk(6);
  t1.addDependency(t2);
  t1.addDependency(t4);
  t2.addDependency(t3);
  t3.addDependency(t4);
  t3.addDependency(t5);
  t4.addDependency(t6);
  t5.addDependency(t1);
  Set s1 = new HashSet();
  s1.add(t1);
  s1.add(t2);
  s1.add(t3);
  Set s2 = new HashSet();
  s2.add(t4);
  s2.add(t5);
  s2.add(t6);
  (new Thread(new ExecuteTask(1, tsp, s1))).start();
  (new Thread(new ExecuteTask(2, tsp, s2))).start();

 }

}