Interview Question
Senior Software Development EngineersCountry: India
Interview Type: In-Person
Threads must be having some attribute(s). For example, resource , availability , ownership etc. Based on them we can have a priority among the threads set.
And based on priority we can put them in a heap. So whenever a request comes, we take the top element from the heap and assign it. And later re-arrange the heap.
Short answer is a "synchronized queue".
If you look at the Java's Thread Pool implementation, I am talking about the java.util.concurrent package specifically, the thread pool Executors uses synchronized queues that implement the BlockingQueue<E> interface and the BlockingQueue<E> interface extends the generic java.util.Queue<E> interface.
You can look at the javadoc and see how the whole system is designed and not reinvent the wheel. Basically your thread pool implementation will use [Abstract]Factory pattern (see ThreadPool, Executor, ExecutorService, ThreadPoolExecutor classes) to create and execute your tasks and your tasks needs to implement the Java Runnable interface which is the Command design pattern. So you can use these design patterns along with a synchronized queue to come up with a Thread Pool implementation in any language of your own.
It depends a lot of the requirements for the thread pool. List, queue even stack, are all conceivable. What do you mean by 'assign a thread'?
I might opt to go in with Priority Queue or per se Heap (note these two things are usually the same as the former can be implemented with Heap Data Structure, and still provide good space and time complexity. Not necessary implement in linked-list way to have full graph representation, but vector or even fixed-array is suffice).
Ok, back to decision of choosing Priority Queue (I say Heap from now).
It serves the following requirement
1. good time complexity when I need a new idle thread to be grabbed and used. We can achieve it with O(1) at the root
2. able to get the most prioritized thread from the pool to use. This most prioritized thread can be associated with the largest priority value, thus making 1. possible. When we grabbed such thread, Heap will update itself and 2nd best prioritized thread will be ready sitting tight for next time. Whenever we're done with executing the current thread, we can decrement its priority value, so when it gets back to the Heap it won't be at the root node, but lower thus give other threads chance to be selected freely with less effort.
3. We might not have to maintain busy list of threads. After each thread done its job, just push it into Heap. The cost will be N*logN wheres N is number of idle threads at that time.
Trade-off, just one thing I can think of that we miss from going with Heap according to above reasoning
1. We have no control over busy threads in execution. We cannot query info about it during run-time, only wait until it's done.
There's no right or wrong, but depends on your use case, requirement.
queue data structure is used
- jaya May 22, 2013