river-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Patricia Shanahan <p...@acm.org>
Subject Re: TaskManager progress
Date Thu, 22 Jul 2010 12:18:14 GMT
The best idea I have so far involves maintaining a separate sharable 
TreeSet of all except the most recently added tasks. It would be kept 
under a single-writer, multiple-reader lock. Tasks that complete or are 
removed from the TaskManager would continue to be represented in the 
sharable set, but with the TaskWrapper marked appropriately and the Task 
reference set to null.

A runAfter scan would begin with the elements added to allTasks since 
the last sharable set update, under the TaskManager lock. If that does 
not find a hit, the scan would continue against the sharable set using 
the read lock, so that several threads could do it in parallel. On hit 
in the sharable set, go synchronized, check the status of the task, and 
resume the scan if it is completed or removed.

When the number of deviations between the sharable set and allTasks 
reaches some limit, get the write lock and update the sharable set by 
deleting completed and removed tasks, and adding the tasks that were 
added to allTasks since the last update.

It is not very practical with JDK 1.5. It needs the TreeSet subSet 
methods, so that I can scan the portion of allTasks that represented 
tasks added since the last sharable set update.

An alternative approach is to add methods to let callers know about the 
state of the TaskManager, and encourage some form of throttling in the 
callers when the number of tasks in the TaskManager exceeds a limit.


Peter Firmstone wrote:
> I'll think about it some more & see if I can't think of something.
> Peter Firmstone wrote:
>> Patricia Shanahan wrote:
>>> You make some interesting points in your e-mails. I'm just going to
>>> comment on a couple of things tonight, and think more about the rest.
>>> On 7/21/2010 5:25 PM, Peter Firmstone wrote:
>>>> Hi Patricia,
>>>> Instead of Task passing an Iterable<Task>, it could pass an
>>>> Enumerator<Task>, which is inherently immutable. One more comment 
>>>> inline.
>>> I assume you mean Enumeration<Task>? I prefer Iterable<Task> because

>>> it allows for the enhanced for loop:
>> Yep.
>>> public Task runAfter(Iterable<Task> candidates){
>>>   for(Task t: candidates){
>>>     if(this has to wait for t){
>>>       return t;
>>>     }
>>>   }
>>>   return null;
>>> }
>>> Given the number of TaskManager callers, I think there is value in
>>> keeping their code as clean and simple as possible.
>> Ok, didn't think of that, still using the old for loop.
>>> On 7/21/2010 6:25 PM, Peter Firmstone wrote:
>>> ....
>>> > I try to keep synchronized blocks as small as possible, not so much 
>>> for
>>> > performance, but for bugs, not even necessarily my own bugs but client
>>> > code concurrency bugs. In the synchronized block, I don't call objects
>>> > which may be accessible from outside the object I'm calling from. 
>>> State
>>> > that needs to be atomically updated, I group together using the same
>>> > lock, I also consider using the ReadWriteLock, if reads will outnumber
>>> > writes. If multiple objects must be updated atomically, I might group
>>> > them together into an encapsulating object with the methods I need to
>>> > make it atomic. This is better than holding multiple locks.
>>> >
>>> The most important concurrency issue in TaskManager is probably the
>>> runAfter testing. In a TaskManager with n existing tasks, a runAfter
>>> test is O(n). The only other O(n) operation is getPending, which I think
>>> is much less frequent. Everything else is, or can be, O(1) or O(log n).
>>> I've arranged the order to minimize the number of calls, by finding the
>>> youngest runAfter task first. However, I do not have a good solution to
>>> a task that might need to runAfter, but does not in fact need to
>>> runAfter any of the existing tasks. I just has to scan the whole list.
>>> Moreover, I have to call back to the runAfter method in the caller's
>>> Task object.
>>> I've thought about some ideas, but so far nothing really satisfactory.
>> That's a tough one, we may have to accept it, you've already got 
>> significantly improved performance over the original implementation.
>> Peter.
>>> Patricia

View raw message