* How to determine if task is busy or not? @ 2009-08-08 10:49 Tomek Walkuski 2009-08-08 10:56 ` Ludovic Brenta 0 siblings, 1 reply; 7+ messages in thread From: Tomek Walkuski @ 2009-08-08 10:49 UTC (permalink / raw) Is there any way to determine if task is busy or not? I have pool of worker tasks and I want to choose one of them to give some work to do. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: How to determine if task is busy or not? 2009-08-08 10:49 How to determine if task is busy or not? Tomek Walkuski @ 2009-08-08 10:56 ` Ludovic Brenta 2009-08-08 11:27 ` Dmitry A. Kazakov 0 siblings, 1 reply; 7+ messages in thread From: Ludovic Brenta @ 2009-08-08 10:56 UTC (permalink / raw) Tomek Walkuski wrote: > Is there any way to determine if task is busy or not? > > I have pool of worker tasks and I want to choose one of them to give > some work to do. I don't think you should see the problem in these terms. You don't have to select a task from the pool; the tasks select themselves as they become available for a new job, e.g. each task would look like loop Queue.Get_Next (Job); Process (Job); end loop; where Queue is a protected object and Get_Next removes a job from it and passes it to the task. Of course, if there are no jobs in the queue, it blocks until one arrives. HTH -- Ludovic Brenta. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: How to determine if task is busy or not? 2009-08-08 10:56 ` Ludovic Brenta @ 2009-08-08 11:27 ` Dmitry A. Kazakov 2009-08-08 14:59 ` Maciej Sobczak 0 siblings, 1 reply; 7+ messages in thread From: Dmitry A. Kazakov @ 2009-08-08 11:27 UTC (permalink / raw) On Sat, 8 Aug 2009 03:56:11 -0700 (PDT), Ludovic Brenta wrote: > Tomek Walkuski wrote: >> Is there any way to determine if task is busy or not? >> >> I have pool of worker tasks and I want to choose one of them to give >> some work to do. > > I don't think you should see the problem in these terms. You don't > have to select a task from the pool; the tasks select themselves as > they become available for a new job, e.g. each task would look like > > loop > Queue.Get_Next (Job); > Process (Job); > end loop; > > where Queue is a protected object and Get_Next removes a job from it > and passes it to the task. Of course, if there are no jobs in the > queue, it blocks until one arrives. Just to add a pair words... The scheme described by Ludovic is not only simpler, it is also race condition free. The reverse scheme has a race condition in it. If you have asked if a task is idle, you do not know if it still is right now (or not terminated). To eliminate race condition you need one atomic operation "take job or fall back" and poll the pool of task with this operation. It is not only inefficient it is also a potential live lock or at least unbalanced servicing policy, if you have many job suppliers. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: How to determine if task is busy or not? 2009-08-08 11:27 ` Dmitry A. Kazakov @ 2009-08-08 14:59 ` Maciej Sobczak 2009-08-08 16:00 ` Tomek Wałkuski 2009-08-08 18:22 ` Dmitry A. Kazakov 0 siblings, 2 replies; 7+ messages in thread From: Maciej Sobczak @ 2009-08-08 14:59 UTC (permalink / raw) On 8 Sie, 13:27, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de> wrote: > The scheme described by Ludovic is not only simpler, it is also race > condition free. The reverse scheme has a race condition in it. If you have > asked if a task is idle, you do not know if it still is right now Depends. If it is the asking entity that is also providing the job, then the problem above cannot happen. In other words, if the "manager" asks the task whether it is busy or idle and the answer is "idle", then that answer it true until the same manager provides new work unit, because there is no other way for the task to switch from "idle" to "busy". Which means that the manager can always safely handle a new work unit to the "idle" task, no race is possible. The race can happen the other way round, though: the manager asks the task for its status, the task answers "busy" and the manager takes some decision based on this answer (move on to another task, perhaps?) even though it might not be true anymore (the task in question might be already "idle" by that time). This kind of race might be acceptable, though, at most at the price of underutilized on unbalanced server. The advantage of such a setup is that the manager knows whether the work can be handled *immediately* by any one of the tasks in the pool. False negatives can be harmless, as long as the positives are accurate. Using a queue, as suggested by Ludovic, makes sense only when the work units can *wait* for being processed. This might or might not be the case. There are examples of systems where either of these schemes are good (batch processing vs. real-time?). I would not say that one is better than another. To Tomek - the simplest way to deploy your original idea is to use a flag (Busy/Idle - an enumeration type is perfect here), which is shared and used by both the worker task and its manager. Protected object is a proper solution here and you might even use the same protected object for managing both the flag and the work unit itself. -- Maciej Sobczak * www.msobczak.com * www.inspirel.com Database Access Library for Ada: www.inspirel.com/soci-ada ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: How to determine if task is busy or not? 2009-08-08 14:59 ` Maciej Sobczak @ 2009-08-08 16:00 ` Tomek Wałkuski 2009-08-08 18:22 ` Dmitry A. Kazakov 1 sibling, 0 replies; 7+ messages in thread From: Tomek Wałkuski @ 2009-08-08 16:00 UTC (permalink / raw) On 8 Sie, 16:59, Maciej Sobczak <see.my.homep...@gmail.com> wrote: > Depends. If it is the asking entity that is also providing the job, > then the problem above cannot happen. In other words, if the "manager" > asks the task whether it is busy or idle and the answer is "idle", > then that answer it true until the same manager provides new work > unit, because there is no other way for the task to switch from "idle" > to "busy". Which means that the manager can always safely handle a new > work unit to the "idle" task, no race is possible. > Only manager is providing work to the tasks. So, as you said, no race is possible. > To Tomek - the simplest way to deploy your original idea is to use a > flag (Busy/Idle - an enumeration type is perfect here), which is > shared and used by both the worker task and its manager. Protected > object is a proper solution here and you might even use the same > protected object for managing both the flag and the work unit itself. > That was my first thought :) ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: How to determine if task is busy or not? 2009-08-08 14:59 ` Maciej Sobczak 2009-08-08 16:00 ` Tomek Wałkuski @ 2009-08-08 18:22 ` Dmitry A. Kazakov 2009-08-08 18:39 ` Ludovic Brenta 1 sibling, 1 reply; 7+ messages in thread From: Dmitry A. Kazakov @ 2009-08-08 18:22 UTC (permalink / raw) On Sat, 8 Aug 2009 07:59:51 -0700 (PDT), Maciej Sobczak wrote: > On 8 Sie, 13:27, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de> > wrote: > >> The scheme described by Ludovic is not only simpler, it is also race >> condition free. The reverse scheme has a race condition in it. If you have >> asked if a task is idle, you do not know if it still is right now > > Depends. If it is the asking entity that is also providing the job, > then the problem above cannot happen. In other words, if the "manager" > asks the task whether it is busy or idle and the answer is "idle", > then that answer it true until the same manager provides new work > unit, because there is no other way for the task to switch from "idle" > to "busy". Which means that the manager can always safely handle a new > work unit to the "idle" task, no race is possible. As I said, only if single job supplier (manager) is here. In that case it is still a poor scheme because of polling. A better (I tempted to say proper) one is when idle tasks queue themselves into the pool of idle tasks maintained by the manager. But a protected object of tasks would be better here as well. > The advantage of such a setup is that the manager knows whether the > work can be handled *immediately* by any one of the tasks in the pool. > False negatives can be harmless, as long as the positives are > accurate. No, it is not an advantage. 1. Job is done to get a result, it is a lengthy process, so there is a worker to perform it asynchronously. Until the job is done it is of little interest whether it has been started or not. (Some interest exists if jobs are cancelable if not initiated) 2. The manager is only a mediator here. If a job cannot be started immediately what the manger is supposed to do? If it does not cancel the job, the only option is to wait. This is what the job queue is for. > Using a queue, as suggested by Ludovic, makes sense only when the work > units can *wait* for being processed. This might or might not be the > case. See above. If there is some service timeout a queue is serviced by a monitor task (a special "mister no" worker). Still better. > There are examples of systems where either of these schemes are good > (batch processing vs. real-time?). I would not say that one is better > than another. > > To Tomek - the simplest way to deploy your original idea is to use a > flag (Busy/Idle - an enumeration type is perfect here), which is > shared and used by both the worker task and its manager. Protected > object is a proper solution here and you might even use the same > protected object for managing both the flag and the work unit itself. No, you don't need any extra shared data. Do conditional entry call do determine if the worker is ready: task body Worker is begin loop accept New_Job (Work_Item : in out Job); ... -- Service end loop; end Worker; The manager does a conditional entry call (RM 9.7.3): select Worker.New_Job (Thing_To_Do); else -- The chap is busy ... end select; -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: How to determine if task is busy or not? 2009-08-08 18:22 ` Dmitry A. Kazakov @ 2009-08-08 18:39 ` Ludovic Brenta 0 siblings, 0 replies; 7+ messages in thread From: Ludovic Brenta @ 2009-08-08 18:39 UTC (permalink / raw) Dmitry A. Kazakov wrote on comp.lang.ada: > Maciej Sobczak wrote: >> Dmitry A. Kazakov wrote: > >>> The scheme described by Ludovic is not only simpler, it is also race >>> condition free. The reverse scheme has a race condition in it. If you have >>> asked if a task is idle, you do not know if it still is right now > >> Depends. If it is the asking entity that is also providing the job, >> then the problem above cannot happen. In other words, if the "manager" >> asks the task whether it is busy or idle and the answer is "idle", >> then that answer it true until the same manager provides new work >> unit, because there is no other way for the task to switch from "idle" >> to "busy". Which means that the manager can always safely handle a new >> work unit to the "idle" task, no race is possible. > > As I said, only if single job supplier (manager) is here. In that case it > is still a poor scheme because of polling. A better (I tempted to say > proper) one is when idle tasks queue themselves into the pool of idle tasks > maintained by the manager. But a protected object of tasks would be better > here as well. > >> The advantage of such a setup is that the manager knows whether the >> work can be handled *immediately* by any one of the tasks in the pool. >> False negatives can be harmless, as long as the positives are >> accurate. > > No, it is not an advantage. > > 1. Job is done to get a result, it is a lengthy process, so there is a > worker to perform it asynchronously. Until the job is done it is of little > interest whether it has been started or not. (Some interest exists if jobs > are cancelable if not initiated) > > 2. The manager is only a mediator here. If a job cannot be started > immediately what the manger is supposed to do? If it does not cancel the > job, the only option is to wait. This is what the job queue is for. > >> Using a queue, as suggested by Ludovic, makes sense only when the work >> units can *wait* for being processed. This might or might not be the >> case. > > See above. If there is some service timeout a queue is serviced by a > monitor task (a special "mister no" worker). Still better. > >> There are examples of systems where either of these schemes are good >> (batch processing vs. real-time?). I would not say that one is better >> than another. > >> To Tomek - the simplest way to deploy your original idea is to use a >> flag (Busy/Idle - an enumeration type is perfect here), which is >> shared and used by both the worker task and its manager. Protected >> object is a proper solution here and you might even use the same >> protected object for managing both the flag and the work unit itself. > > No, you don't need any extra shared data. Do conditional entry call do > determine if the worker is ready: > > task body Worker is > begin > loop > accept New_Job (Work_Item : in out Job); > ... -- Service > end loop; > end Worker; > > The manager does a conditional entry call (RM 9.7.3): > > select > Worker.New_Job (Thing_To_Do); > else > -- The chap is busy > ... > end select; But that becomes unwieldy in the presence of multiple worker tasks, any one of which needs to be idle when enqueuing a job. How about: protected Queue is procedure Enqueue (J : in Job); entry Get_Next (J : out Job); private -- left as an exercise :) end Queue; protected body Queue is procedure Enqueue (J : in Job) is begin if Get_Next_Job'Count < 1 then raise No_Worker_Is_Presently_Waiting_For_A_Job; else -- ... end if; end Enqueue; entry Get_Next (J : out Job) when Jobs_Enqueued is begin ... end Get_Next; end Queue; Start all workers before the manager; all workers then start waiting on the Get_Next entry. The manager keeps enqueuing new jobs until all workers are busy, at which point no worker is waiting on Get_Next anymore and the manager gets an exception to signal that condition. Then the difficult part is to ensure that all workers collectively consume jobs at least as fast as the manager can enqueue them. -- Ludovic Brenta. ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2009-08-08 18:39 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2009-08-08 10:49 How to determine if task is busy or not? Tomek Walkuski 2009-08-08 10:56 ` Ludovic Brenta 2009-08-08 11:27 ` Dmitry A. Kazakov 2009-08-08 14:59 ` Maciej Sobczak 2009-08-08 16:00 ` Tomek Wałkuski 2009-08-08 18:22 ` Dmitry A. Kazakov 2009-08-08 18:39 ` Ludovic Brenta
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox