Feedback requested: TaskManager shutdown, Fair scheduling

re: Feedback requested: TaskManager shutdown, Fair scheduling

art_scott@msn.com — Fri, 01 Aug 2008 21:07:14 GMT

What are the implications for games and media, like HD motion pictures? Or both together?

re: Feedback requested: TaskManager shutdown, Fair scheduling

Thomas Danecker — Fri, 01 Aug 2008 21:08:12 GMT

Some sort of fairness is a must! It doesn't have to be a fifo; it should be ok to prefer "fresh" tasks as long as older tasks get a chance and the problem of possible starvation is taken into account. With the use of the TPL, we should be able to easily create a lot of small tasks without having to worry about scheduling and associated problems like starvation/fairness (the TPL should choose the most performant - but fair enough - approach to process all the tasks we throw at it). On the other hand, we also should have the possibility to force strong fifo order, in the case our model relies on that fact (e.g. when a task manager is used as a workqueue - though I would still prefer an own WPF-like Dispatcher for that purpose).

re: Feedback requested: TaskManager shutdown, Fair scheduling

toub — Sat, 02 Aug 2008 04:23:25 GMT

Thomas, thanks for the feedback. Can you elaborate on the scenarios where this freshness is important? For these scenarios, are you creating the tasks from within other tasks or from outside of the target scheduler's threads?

re: Feedback requested: TaskManager shutdown, Fair scheduling

toub — Sat, 02 Aug 2008 04:24:26 GMT

art_scott, it really depends on particular algorithms. Could you elaborate?

re: Feedback requested: TaskManager shutdown, Fair scheduling

Justin James — Sat, 02 Aug 2008 07:20:20 GMT

I originally got very interested in PEL because I thought that it would support a true fork()/join(). I've used it, and I like the library, but I think that fork()/join() would be a really great thing, especially given the number of people already familiar and comfortable with that paradigm. I also think that fork()/join() offers a much lower complexity level than needing to handle delegates/lambda.

J.Ja

re: Feedback requested: TaskManager shutdown, Fair scheduling

David — Sat, 02 Aug 2008 09:50:22 GMT

Awhile back I write a application that needed to process a virtually unlimited amount of data. Essentially the data was being processes as fast as it came in. The application ran continuously with virtually no hope of catching up. As the data was processed its results became available for other parts of the system to use. If the data had been processed in a LIFO order than older data (if I understand this right) would never get processed. This would result in gaps and errors in the results. It was not essential that the data be processed in a strict FIFO manner but it was important that ALL data did get processed "near" each other. It sounds like this is an example where "Fairness" is prefered.

re: Feedback requested: TaskManager shutdown, Fair scheduling

Steffen Zeidler — Sat, 02 Aug 2008 20:09:06 GMT

The TPL is designed to split efficiently CPU time consuming tasks on multi cores.

Is it planed to use the TPL to control concurrency processes and real time tasks too?

I think the Concurrency and Coordination Runtime (CCR) is in many aspects similar to the TPL (TaskManager/Dispatcher, Task/Task, Future/Port) and it would be nice to merge both in one library.

re: Feedback requested: TaskManager shutdown, Fair scheduling

Pointernil — Mon, 04 Aug 2008 12:31:50 GMT

I think a way to influence the scheduling of tasks is a must.

It's not only about FIFO or LIFO, a mechanism using a prioritization metric comes handy most of the time...

my prefered impl. of such a metric uses mostly a combination of PRIO, SIZE and AGE of the task to decide what to execute next.

re: Feedback requested: TaskManager shutdown, Fair scheduling

Stephan — Mon, 04 Aug 2008 18:39:19 GMT

Don't know where to deposit this feedback: I would really like to see Parallel.Do return. It simply is useful.

re: Feedback requested: TaskManager shutdown, Fair scheduling

dimkaz — Mon, 04 Aug 2008 19:10:25 GMT

Fair scheduling or even better a priority queue would be very useful.

Thanks

re: Feedback requested: TaskManager shutdown, Fair scheduling

toub — Wed, 06 Aug 2008 04:21:16 GMT

Thanks for all of the feedback! This is great. For those folks asking for prioritization, can you provide some real-world examples of how you'd use it?

Stephan, the Do method has simply been renamed: it's now Parallel.Invoke rather than Parallel.Do.

re: Feedback requested: TaskManager shutdown, Fair scheduling

Rama — Thu, 07 Aug 2008 03:34:27 GMT

I think it would be very useful to have both the sync, and asynch methods to stop the taskmanager, and most importantly it should support stopping even when the taskmanger is not done with all the tasks.

re: Feedback requested: TaskManager shutdown, Fair scheduling

David — Thu, 07 Aug 2008 09:06:34 GMT

You want real-world example of a need for fair scheduling for a prioritization? There are hundreds of examples.

For one, just about every manufactoring segment has worked on this problem. I know of many papers devoted to this from the chemical processing industry.

http://docs.lib.purdue.edu/dissertations/AAI9540250/

In my world I have tens of thousands of tasks that need to be farmed out to dozens of seperate machines. I don't necessary know or care what the tasks do. I do know they each can take from near 0 time to hours. I also have a variety of prioritize that need to be honored. Some tasks take require order (pri 1 must come before pri 2). Some must complete _before_ a specific time. That one is much more tricky.

Recently I was asked to dynamically change the priority according to how much time it's been in the queue. In other words, the longer it's around the more likely it is to be processed sooner rather than later.

re: Feedback requested: TaskManager shutdown, Fair scheduling

toub — Sat, 23 Aug 2008 23:36:15 GMT

Great, thanks for the examples.

Please implement some kind of priorization

Nikolas — Mon, 15 Sep 2008 12:39:27 GMT

I would love to see some kind of priorization possibility for the fx library.

Right now im handling that myself, but I cant believe that this wouldnt benefit a lot of people out there.

Here is an easy example:

Im continuously querying data from a trading platform.

This data is the analyzed and if certain criterias are matched by the data actions are taken.

Before theses actions are taken, an update is issued for the relevant subset of data, to be sure that for example the prices havent chanaged since the last update.

This update has to be executed immediatly and can therefore not be handled by the continous update task queue.

Right now this is handled by a second TaskManager wich handles the higher priotitized updates.

The example is extremly simplified, if you are interested i can give a detailed description of this case.

re: Feedback requested: TaskManager shutdown, Fair scheduling

John Melville — Sun, 19 Oct 2008 06:31:07 GMT

I have a scenerio where I would benefit from some kind of guarentee that a task will eventually execute.

I am retrieving images out of a database, and I want to do the loading and decoding asynchronously. My method fires off a task to load the image. For ereyone who askes for the list while the task is executing I keep a record of who they were and return a default image. When the task completes, I signal all the callers that the "final" value is availaible.

This works great on my 4 proc desktop. when I put it on my one proc laptop machine the task never completes.

If I explicitly wait on the task, everything works on both the four proc and the one proc machine.

My requirements are not hard, but I would really like a guarentee that a task will eventually get scheduled, even if nobody ever waits on it.

re: Feedback requested: TaskManager shutdown, Fair scheduling

Darshan Shah — Fri, 20 Feb 2009 00:17:51 GMT

Some sort of fairness is absolutely necessary.

Without fairness, only kinds of problems you can solve are purely algorithmic. (Where, you do not care if some tasks may take indefinite amount of time to get started). In my opinion, it is very limited scope of very large parallel world out there.

In application domains, where you deal with physical world, such as process controls, test and measurement systems, simulations and even in massively parallel on-line games, tasks are started dynamically (their number is not known at compile time) and it can run for indefinite period of time because they life time is usually governed by external events. Applications in these domains simply cannot use TPL/Task Manager because task starvation for indefinite period of time is never acceptable.

Therefore not only some sort of fairness but additional control over their scheduling is absolutely necessary to use task parallel libraries in any domains outside algorithmic one. Ideally you could have priority based round robin scheduling among tasks. I could also accomplish the same if I could plug-in my own thread-pool under TaskManager, which can anxiously create new threads with the right priority, based on tasks that are getting started, dynamically in controlled fashion. Alternatively, Task Manager could fire an event, if a task is starved for more than x amount of time, which can be used to create more threads by that event subscriber (user) if he wishes to.

re: Feedback requested: TaskManager shutdown, Fair scheduling

toub — Fri, 20 Feb 2009 10:03:58 GMT

Thanks, everyone, for the great feedback!

Darshan, we've implemented an extensibility mechanism very similar to what you're looking for.

Also, based on all the good feedback here, we implemented a fairness mechanism.

Stay tuned...

re: Feedback requested: TaskManager shutdown, Fair scheduling

darshanshah — Tue, 24 Feb 2009 00:22:55 GMT

I am using VS2010 CTP (published on 10/31/2008) to evaluate task parallel libraries to enhance our scheduler. If viable, I would certainly like to test newer TPL bits that implements fairness scheduling of tasks and or any extensible mechanism to eliminate task starvation. How far is next CTP that will include enhancements of TPL/Task Manager?