design pattern for concurrent task execution with constraints

I have 3 classes of task (I, D, U) which come in on a queue, tasks of the same class must be processed in order. I want tasks to run as concurrently as possible; however there are some constraints:

• U and D cannot run concurrently
• U and I cannot run concurrently
• I(n) requires U(n) has completed

Q: What design pattern(s) would fit this class of problem?

I have two approaches I am considering:

Approach 1: Use 1 Thread per task, each with its own queue. Each thread h开发者_StackOverflowas a synchronized start phase where it checks start conditions, then runs, then a synchronized stop phase. It is easy to see that this will provide good concurrency but I am unsure if it correctly implements my constraints and doesnt deadlock.

D_Thread { ...
 while (task = D_Queue.take()) {
  synchronized (State) {   // start phase
   waitForU();
   State.setRunning(D, true);
  }
  run(task);  // run phase
  synchronized (State) {   // stop phase
    State.setRunning(D, false) 
  }
 }
}

Approach 2: Alternatively, a single dispatch thread manages execution state, and schedules tasks in a ThreadPool, waiting if necessary for currently scheduled tasks to complete.

---

The Objective-C Foundation framework includes classes NSOperationQueue and NSOperation that satisfy some of these requirements. NSOperationQueue represents a queue of NSOperations. The queue runs a configurable maximum number of operations concurrently. Operations have a priority and a set of dependencies; all of the operations that an operation depends on must be completed before the queue will start running the operation. The operations are scheduled to run on a dynamically-sized pool of threads.

What you need requires a somewhat smarter version of NSOperationQueue that applies the constraints you have expressed, but NSOperationQueue and company provide an example of how roughly your problem has been solved in a production framework that resembles your second suggested solution of a dispatch thread running tasks on a thread pool.

---

Actually this turns out to be more simple than it seemed: a mutex is mainly all that is needed:

IThread(int k) {
 synchronized (u_mutex) {
  if (previousUSet.contains(k))) U(k);
 }
 I(k);
}

DThread(int k) {
 synchronized (u_mutex) {
  D(k);
  previousUSet.add(k);
 }
}