observe and act upon workload parallelism: PERF_TYPE_PARALLELISM (Was: [RFC][PATCH] sched_wait_block: wait for blocked threads)
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Hi Stijn,
Thanks for replying!
I agree that our goals are slightly different, but I think they are not so different as one might think on first glance.
Using the CPU to the fullest is certainly our goal also, to be "work conserving" is a long-standing feature of any good scheduler.
I assert that our interface could certainly be used by a thread-pool to achieve the "only run one of us at a time/don't pre-empt us unless we misbehave" semantic.
I think it is not true however that our approach only works when timing is available from applications. It's true that the evaluation in our paper is focussed on those cases, but we do also have non-timesensitive tasks in our workloads (e.g. gcc).
The trick is that even if the application doesn't provide timing, our kernel scheduler will. When a task uses our coop_poll call, it receives a time value as a return value. This may be interpreted as "you may run until this time without fear of pre-emption, but you must voluntarily yield back to the kernel by this time, and you may not block before such yield". I'll discuss the "you must not block" below.
The time value returned by coop_poll is calculated by the kernel based on release times of other coop_poll tasks *and* the fairshare scheduling timeslice set by the kernel scheduling algorithm. So even if there are no other coop_poll release times (because the applications did not provide times to coop poll), the interface will still default to the kernel's fairshare timeslice based time.
Back to your case. Suppose the threads of a pool are running using coop_poll, but none of them provide times. If one of them is running and it blocks, the kernel removes it from the pool (coop group). The remaining members of the pool remain eligible for execution. Which task runs next depends on fair sharing criteria (maybe a task from another pool). Later when the blocked thread awakes, it will resume as a "best-effort" thread (still not in a thread pool), until it again yields by calling coop_poll, at that point it "re-joins" it's thread pool.
What does it mean?
1) if CPU intensive tasks avoid blocking (by isolating blocking calls to helper threads), and they honor coop_poll times, they will never be pre-empted. [ this is maybe where we differ, we assume that time sensitive applications have good reasons to isolate their time-sensitive and CPU intensive code from synchronous IO ]
2) if IO tasks are not CPU intensive, they will likely never be pre-empted either, even though they lose their "cooperative" status in the period between blocking on IO, waking up, until calling coop_poll again.
3) only "best-effort" tasks, i.e. tasks that don't use coop_poll at all, are pre-empted, in the normal way they would under regular fair share scheduling.
-- Buck
Quoted 103 lines · Stijn Devriendt
Hi Buck,
Thanks for taking the time to inform me about your research. I've just read up on it, but as far as I can tell there's still quite some difference between our goals. My goal was to utilize the CPU to it's fullest, regardless of blocking calls, in the context of a threadpool. Your approach seems to try and do away with scheduling latency and is better suited when timing information is available.
A generic threadpool doesn't have timing information about the work-items it is processing, so it cannot take part in this type of cooperative scheduling.
Secondly you're using
coop_poll()to wait for timeout and/or fds. In my case I'm trying to let every blocking syscall cause the wake-up of the next thread. This means that the threadpool should make no assumptions about work-items and threadpool users can write any code they want.Regards,
StijnQuoted 8 lines · Buck
Hi,
I think our research on scheduling is somewhat related to this topic.
I posted to the kernel list a while back, but I'm not sure anyone noticed. Here is a link to
that post, which contains links to slides and our paper.Quoted 66 lines
http://lwn.net/Articles/358295/
-- Buck
Quoted 61 lines · Stijn Devriendt
Quoted 10 lines
Think of it like a classic user-level threading package, where one process implements multiple threads entirely in user space, and switches between them. Except we'd do the exact reverse: create multiple threads in the kernel, but only run _one_ of them at a time. So as far as the scheduler is concerned, it acts as just a single thread - except it's a single thread that has multiple instances associated with it.
And every time the "currently active" thread in that group runs out of CPU time - or any time it sleeps - we'd just go on to the next thread in the group.
Without trying to sound selfish: after some thinking I can't see how this solves my problem. This is fine for the case you mentioned later on, like UI threads, but it's not powerful enough for what I'm trying to achieve.
Let's make the round-trip for the thread pool case and start with an empty thread pool queue:
- All threads are blocked on the queue condition variable untill new work is queued.
- Thread 1 happily wakes up and runs the work item untill it's blocked.
- A new work item arrives and Thread 2 is woken to handle the new work item.
- As long as new work arrives and Thread 2 is not blocked (regardless of preemption because the deal was that they will not preempt each other) Thread 2 keeps running this work.
Even when Thread 1 is woken, it will not preempt Thread 1.One solution would be to let Thread 2 call
sched_yield, but the question then is "when" and "how much". Every time a lightweight thread yields, you'll incur context switches. Because you don't know when or how much, you'll be penalized for context switching even when not needed. (Consider 1 blocked thread and 4 extra threads sched_yield'ing every 5 work items)Another option is to have a group-leader. Non-leader threads will call
sched_yieldonce in a while in order to try and jump back to the group-leader. The group-leader will always continue work without sched_yield'ing. There's no preemption between these threads.
The down-side is that in case multiple of these threads are waiting for an event, wake-ups must wake the group leader rather than the other coop-scheduled threads for this model to work.
Another down-side is that when a non-leader thread is blocked and the group-leader is run, the non-leader thread is treated unfair.Either solution's end-result is a very unfair threadpool where one cannot guarantee even a loose FIFO-model where items are handled more or less in the order they are queued and a library that needs to make trade-offs in performance to get this behaviour back.
The solution is great when the threads are blocked most of the time and have little CPU processing to do (like UI threads), but doesn't scale beyond that.
As ever, enlighten me when you have a great solution to this problem.
Stijn
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Hi Stijn:
Let me chime in a little bit ...
In one of your past responses, you've written:
Quoted 6 lines
One solution would be to let Thread 2 call
sched_yield, but the question then is "when" and "how much". Every time a lightweight thread yields, you'll incur context switches. Because you don't know when or how much, you'll be penalized for context switching even when not needed. (Consider 1 blocked thread and 4 extra threads sched_yield'ing every 5 work items)
You see, this is where the coop_poll() interface is so useful. Everytime you 'wake up' from coop_poll(), the kernel gives you a future time value at which you'd be calling coop_poll() again. Now the beauty of this approach is that this time value is calculated by the kernel to be just the amount that is necessary for maintaining a fair CPU sharing among all the runnable tasks. So you don't have to worry about the when part. Further, the fair sharing itself will determine how long you actually block within coop_poll(). As long as you maintain the cooperative polling semantics (by properly honoring the time value provided to you by the kernel), you are guranteed that only one of the threads within the cooperative thread pool will be ever run by the kernel.
Let me know if this makes any sense and me and Buck will try to answer your (or any other person's) doubts.
Cheers,
Ani
Quoted 171 lines · Buck
Hi Stijn,
Thanks for replying!
I agree that our goals are slightly different, but I think they are not so different as one might think on first glance.
Using the CPU to the fullest is certainly our goal also, to be "work conserving" is a long-standing feature of any good scheduler.
I assert that our interface could certainly be used by a thread-pool to achieve the "only run one of us at a time/don't pre-empt us unless we misbehave" semantic.
I think it is not true however that our approach only works when timing is available from applications. It's true that the evaluation in our paper is focussed on those cases, but we do also have non-timesensitive tasks in our workloads (e.g. gcc).
The trick is that even if the application doesn't provide timing, our kernel scheduler will. When a task uses our
coop_pollcall, it receives a time value as a return value. This may be interpreted as "you may run until this time without fear of pre-emption, but you must voluntarily yield back to the kernel by this time, and you may not block before such yield". I'll discuss the "you must not block" below.The time value returned by
coop_pollis calculated by the kernel based on release times of othercoop_polltasks *and* the fairshare scheduling timeslice set by the kernel scheduling algorithm. So even if there are no othercoop_pollrelease times (because the applications did not provide times to coop poll), the interface will still default to the kernel's fairshare timeslice based time.Back to your case. Suppose the threads of a pool are running using
coop_poll, but none of them provide times. If one of them is running and it blocks, the kernel removes it from the pool (coop group). The remaining members of the pool remain eligible for execution. Which task runs next depends on fair sharing criteria (maybe a task from another pool). Later when the blocked thread awakes, it will resume as a "best-effort" thread (still not in a thread pool), until it again yields by callingcoop_poll, at that point it "re-joins" it's thread pool.What does it mean?
1) if CPU intensive tasks avoid blocking (by isolating blocking calls to helper threads), and they honor
coop_polltimes, they will never be pre-empted. [ this is maybe where we differ, we assume that time sensitive applications have good reasons to isolate their time-sensitive and CPU intensive code from synchronous IO ]2) if IO tasks are not CPU intensive, they will likely never be pre-empted either, even though they lose their "cooperative" status in the period between blocking on IO, waking up, until calling
coop_pollagain.3) only "best-effort" tasks, i.e. tasks that don't use
coop_pollat all, are pre-empted, in the normal way they would under regular fair share scheduling.-- Buck
Quoted 103 lines · Stijn Devriendt
Hi Buck,
Thanks for taking the time to inform me about your research. I've just read up on it, but as far as I can tell there's still quite some difference between our goals. My goal was to utilize the CPU to it's fullest, regardless of blocking calls, in the context of a threadpool. Your approach seems to try and do away with scheduling latency and is better suited when timing information is available.
A generic threadpool doesn't have timing information about the work-items it is processing, so it cannot take part in this type of cooperative scheduling.
Secondly you're using
coop_poll()to wait for timeout and/or fds. In my case I'm trying to let every blocking syscall cause the wake-up of the next thread. This means that the threadpool should make no assumptions about work-items and threadpool users can write any code they want.Regards,
StijnQuoted 8 lines · Buck
Hi,
I think our research on scheduling is somewhat related to this topic.
I posted to the kernel list a while back, but I'm not sure anyone noticed. Here is a link to
that post, which contains links to slides and our paper.Quoted 66 lines
http://lwn.net/Articles/358295/
-- Buck
Quoted 61 lines · Stijn Devriendt
Quoted 10 lines
Think of it like a classic user-level threading package, where one process implements multiple threads entirely in user space, and switches between them. Except we'd do the exact reverse: create multiple threads in the kernel, but only run _one_ of them at a time. So as far as the scheduler is concerned, it acts as just a single thread - except it's a single thread that has multiple instances associated with it.
And every time the "currently active" thread in that group runs out of CPU time - or any time it sleeps - we'd just go on to the next thread in the group.
Without trying to sound selfish: after some thinking I can't see how this solves my problem. This is fine for the case you mentioned later on, like UI threads, but it's not powerful enough for what I'm trying to achieve.
Let's make the round-trip for the thread pool case and start with an empty thread pool queue:
- All threads are blocked on the queue condition variable untill new work is queued.
- Thread 1 happily wakes up and runs the work item untill it's blocked.
- A new work item arrives and Thread 2 is woken to handle the new work item.
- As long as new work arrives and Thread 2 is not blocked (regardless of preemption because the deal was that they will not preempt each other) Thread 2 keeps running this work.
Even when Thread 1 is woken, it will not preempt Thread 1.One solution would be to let Thread 2 call
sched_yield, but the question then is "when" and "how much". Every time a lightweight thread yields, you'll incur context switches. Because you don't know when or how much, you'll be penalized for context switching even when not needed. (Consider 1 blocked thread and 4 extra threads sched_yield'ing every 5 work items)Another option is to have a group-leader. Non-leader threads will call
sched_yieldonce in a while in order to try and jump back to the group-leader. The group-leader will always continue work without sched_yield'ing. There's no preemption between these threads.
The down-side is that in case multiple of these threads are waiting for an event, wake-ups must wake the group leader rather than the other coop-scheduled threads for this model to work.
Another down-side is that when a non-leader thread is blocked and the group-leader is run, the non-leader thread is treated unfair.Either solution's end-result is a very unfair threadpool where one cannot guarantee even a loose FIFO-model where items are handled more or less in the order they are queued and a library that needs to make trade-offs in performance to get this behaviour back.
The solution is great when the threads are blocked most of the time and have little CPU processing to do (like UI threads), but doesn't scale beyond that.
As ever, enlighten me when you have a great solution to this problem.
Stijn
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/