Peter Firmstone wrote:
Patricia Shanahan wrote:
Now that I've made some progress on building and testing, I'm ready to
return to the substantive issues of the TaskManager refactoring project.
I've read the "com.sun.jini.thread lock contention" thread. I think at
this point the best strategy is to keep TaskManager, update its
interfaces to improve performance, and use API classes available in
JDK 1.5 as applicable in its implementation.
I see two objections to directly exposing ThreadPoolExecutor or
similar to the TaskManager callers.
1. There are new features in 1.6 that may be useful, but not until
River moves to 1.6. I would prefer to avoid having to change all the
callers to make use of future features. For example RunnableFuture is
a 1.6 interface.
Even within a ThreadPoolExecutor based implementation, I think the
pending tasks can be handled most simply by not handing them over to
the executor until they are ready to execute.
Ok, that all makes sense.
2. River may need some global data collection and operations to
support resistance to denial of service attacks. Having a central task
manager class may make that easier, if it is ever needed.
A good idea.
I have two immediate questions:
1. Are the current tests considered adequate? If nobody has an
opinion, I'll review them before starting on refactoring.
I'm unsure to be honest. I don't have access to hardware needed to test
scalability.
Actually, in this question I was really trying to get at tests for
functional correctness. I regard good functional correctness tests as a
necessary prior condition for refactoring.
I can find out either by reading test code or by experiment, making some
deliberate mistakes and seeing whether the tests detect them. For
example, if I make TaskManager occasionally ignore a dependency will the
tests catch me doing it? If not, I need to write some tests that will
catch that.
2. What areas of TaskManager performance most need improvement? What
are my objectives? The current implementation seems to me to be likely
to work quite fast for lightly loaded instances with few tasks, and
even fewer pending tasks, but unlikely to scale well. Is that correct?
Are there any known test cases that demonstrate performance problems?
Gregg Wonderly reported the original bottleneck, caused by TaskThread
extending Thread. Gregg uses his own fork of Jini / Apache River for
delayed unmarshalling of proxy's, I'm not sure if he'd be able to run
the tests in his environment.
Another bottle neck was SecurityManager and AccessController security
checks, due to single thread synchronization of the original
net.jini.security.policy.DynamicPolicyProvider.implies(ProtectionDomain,
Permission), that was until now, it has since changed to an empty SPI,
where the administrator has the choice of using
ConcurrentDynamicPolicyProvider or DynamicPolicyProviderImpl which was
renamed from the old DynamicPolicyProvider implementation. Sorry for
the convoluted explanation.
Since TaskManager may queue Task's unbounded, as the queue grows, the
time window required for single thread synchronization grows, to check
that no other Task in that list should run first and if true, returning
the Task to the back of the queue, all while holding the lock. During
this time no TaskThreads can take another Task and no Task's can be
placed in the queue.
I guess a better solution might be to only lock the queue long enough to
take a private snapshot for the Task, but then this isn't memory
efficient for large queues. Perhaps what's needed is something to
delegate the priority decision to, so that locking the queue is limited
to adding and removing tasks, then we can use a ConcurrentLinkedQueue.
Perhaps:?
1. When given to the TaskManager, tasks are registered with a
TaskProrityManager.
2. Take Task from queue
3. Ask the priority manager if the task is ready.
4. If not ready, return to the back of the queue.
5. If ready, Execute.
6. Execution complete, notify TaskPriorityManager.
Tasks could belong to groups, so the tasks in that group are Comparable,
the Priority Manger could group the tasks with a ConcurrentHashMap,
reducing the number of tasks being compared, a group could just be a
string name, or an integer hash, defined by the task implementation.
The Priority Manager could add tasks to each group when en queued and
remove them when complete.
ConcurrentHashMap<Group,SortedMap<Task>> taskGroups;
interface Group {
String toString();
boolean equals(Object o);
int hashCode();
}
interface Task {
Group getGroup();
+ existing method & comparable.
}
Just some thoughts, based on your comments.
Here's another idea I've been playing with in my mind.
1. Replace the Task runAfter method with:
/** Find the first Task in an Iterable's iteration order on which this
Task depends. Return null if there is no such task.
**/
public Task getDependency(Iterable<Task> candidates);
There would be two typical implementations. If implementing class has no
dependency issues, it would unconditionally return null. If there are
dependencies, it would be:
public Task getDependency(Iterable<Task> candidates){
for(Task candidate : candidates){
if( some condition involving this and candidate ){
return candidate;
}
}
return null;
}
I'm thinking of keeping all the Task instances for which the TaskManager
is currently responsible in a TreeSet based on reverse arrival order.
The Iterable would always be set up to search in increasing age order,
so getDependency will return the youngest Task on which this depends.
Incidentally, the business with passing a size parameter along with the
List in the current implementation is unnecessary. All the Collection
classes come with good sublist or subset capabilities. ArrayList, in
particular, can return a List view of any index range.
Consider an add of a Task x. Use x.getDependency on the whole TreeSet.
If it returns a hit y, put x in a Set associated with y. We then don't
have to consider x for placement in the ready set until y is removed or
terminates.
When y is removed or terminates, search only tasks older than y to look
for another dependency. There is a good chance there won't be many at
that point. If x and y belong to a serial order subset, there won't be
any, because y would not have run until all older tasks had finished.
Essentially, this is the usual operating system strategy of putting
threads that are not currently runnable in a data structure associated
with the reason for non-runnability, outside the priority structure that
dispatches runnable threads. This minimizes the cost to the dispatcher
of a thread that cannot do anything useful until some disk read finishes.
This approach has its highest cost if the TaskManager has a lot of
tasks, and we are adding a Task depends on none of them but is of a type
that might depends on another Task, so it has to scan the entire Iterable.
TreeSet seems attractive because it has a good balance of fast append,
scan forwards or backwards from a specified element, and removal, but I
am still thinking about data structures, and may experiment with
alternatives.
What do you think about this idea?
Patricia
