- my example and some of Vicente's comment snipped -

I think that it will not to much complex to provide a function that submit a task that must run on the context of a different thread. Would this kind of submit function help you?

I'm not sure that it would help, I think that I could construct a more complex example with more tasks and threads that would still deadlock. In general I think it ought to be a requirement that the threadpool works if it has only a single thread (in which case the above would not work).

...

I'm not sure that there is a general solution to this problem without using more threads so that any potentially runnable task will get a chance.

You are right this should be a deadlock problem with the current implementation. I don't think however that having more threads would solve the issue, but just reduce its frequency, as the issue appears when tasks T1 and T2 are handled on the same thread.

I agree, that is why I was not keen on reschedule-until. If blocking is used I think an unexpected deadlock could occur unless all blocked tasks can be resumed in any order, not strictly in reverse order of their reschedule calls as in the current implementation.

In order to avoid the issue we need to avoid two blocking tasks to be executed on the same thread. The user should state blocking task on the submit function. The scheduler will not take a blocking task while in the reschedule_until function. Of course, in order to be able to avoid any deadlock associated to the fact we are using a thread pool, the number of threads must grow, if there is no free worker threads able to handle the new blocking task. The reschedule_until function should throw an exception when the task is not a blocking task.

This should solve the issue, but introduce a burden at the user level, i.e. specify if the task can block or not.

Jeremy, Oliver, what do you think?

Best, Vicente

I think Oliver's intention to use a fiber style scheduler is the right one. To avoid problems all possible mechanisms of blocking would need to be considered and protected against and the temptation would be to declare most tasks as blocking. Even if tasks don't block they may run on the thread for a long time before returning. A dynamic thread pool would also be a solution, starting more threads as tasks block and cleaning them up when the queue is empty. This is the approach used in the Java Executors class (http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/Executors. html). I'm not sure if there is a way to detect the difference between threads being busy and being blocked as in general you would like to keep the number of unblocked threads down to the number of cores. Jeremy Jeremy Baxter Lead Researcher, UAVs & Autonomy Tel: 01684 894801 email: jwbaxter@QinetiQ.com www.QinetiQ.com QinetiQ - Delivering customer focused solutions Please consider the environment before printing this email. The information contained in this E-Mail and any subsequent correspondence is private and is intended solely for the intended recipient(s). The information in this communication may be confidential and/or legally privileged. Nothing in this e-mail is intended to conclude a contract on behalf of QinetiQ or make QinetiQ subject to any other legally binding commitments, unless the e-mail contains an express statement to the contrary or incorporates a formal Purchase Order. For those other than the recipient any disclosure, copying, distribution, or any action taken or omitted to be taken in reliance on such information is prohibited and may be unlawful. Emails and other electronic communication with QinetiQ may be monitored and recorded for business purposes including security, audit and archival purposes. Any response to this email indicates consent to this. Telephone calls to QinetiQ may be monitored or recorded for quality control, security and other business purposes. QinetiQ Limited Registered in England & Wales: Company Number:3796233 Registered office: 85 Buckingham Gate, London SW1E 6PD, United Kingdom Trading address: Cody Technology Park, Cody Building, Ively Road, Farnborough, Hampshire, GU14 0LX, United Kingdom http://www.qinetiq.com/home/notices/legal.html