river-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Peter Firmstone <j...@zeus.net.au>
Subject Re: A new implementation of TaskManager
Date Tue, 06 Jul 2010 02:45:22 GMT
Patricia Shanahan wrote:
> 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.

Oh, yes the tests are thorough, generally, although I haven't got the 
code in front of me right now.

>>> 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?

This is where you have to be careful of Distributed computing, I think 
you'd have to branch out in both directions, checking older and younger 
tasks as the tasks arrival may be a combination of  processing remote 
and local calls.  In fact a task might arrive so far out of sequence 
that it could be at the opposite end of the queue.

I think your right about the problem of a large queue, since it's using 
an Iterable, the queue has to be locked.  I noticed that many tasks 
don't depend on other tasks at all, perhaps an initial method might 
obviate the search altogether.  Although the current implementation 
would return quickly, it still has to wait to obtain a lock, by avoiding 
the need to obtain a lock the task can be executed immediately.


boolean hasDependency();

> Patricia

View raw message