web page on O(1) scheduler
Quoted 6 lines · David Mosberger
I think the web pages should be most relevant to the HPTC (high performance technical computing) community, since this is the community that is most likely affected by some of the performance oddities of the O(1) scheduler. Certainly anyone using OpenMP on Intel platforms (x86 and ia64) may want to take a look.
oh you mean the OpenMP broken behavior of calling sched_yield() in a tight loop to implement spinlocks ?
I'd guess that instead of second guessing the runtime, they should use the pthreads primitives which are the fastest for the platform one would hope.. (eg futexes nowadays)
Quoted 5 lines · David Mosberger
Recently, I started to look into some odd performance behaviors of the O(1) scheduler. I decided to document what I found in a web page at:
<snip>
Quoted 1 line
Comments welcome.
The page mentions persistent starvation. My own explorations of this issue indicate that the primary source is always selecting the highest priority queue. Combine that with the round-robin, and you have a good chance of being grossly unfair with some workloads. I know for certain that lock holders in the active array can be starved for very long periods by tasks entering higher priority queues, thereby causing even more starvation when they finally get the cpu and can release the lock (sleepers go through the roof).
Try the attached overly simplistic (KISS:) diff, and watch your starvation issues be very noticably reduced.
-Mike
Quoted 1 line · Mike Galbraith
Try the attached overly simplistic (KISS:) diff, and watch your starvation issues be very noticably reduced.
Ahem ;-)
Now even attached.
-Mike
kernel/sched.c renamed from kernel/sched.c.org +17 -3
@@ -1264,7 +1264,7 @@task_t *prev, *next;runqueue_t *rq;prio_array_t *array; -struct list_head *queue; +struct list_head *head, *curr;int idx;/*
@@ -1331,8 +1331,22 @@ } idx =sched_find_first_bit (array->bitmap); - queue = array->queue + idx; - next =list_entry (queue->next, task_t, run_list); +next_queue: + head = array->queue + idx; + curr = head->next; + next =list_entry (curr, task_t, run_list); + curr = curr->next; +/* +* If we are about to wrap back to the head of the queue, +* give a lower priority queue a chance to sneak one in. +*/ +if (idx == prev->prio && curr == head && array->nr_active >1 ) { +int tmp =find_next_bit (array->bitmap,MAX_PRIO , ++idx); +if (tmp <MAX_PRIO ) { + idx = tmp; + goto next_queue; + } + } switch_tasks:prefetch (next);
Dear Arjan,
///////
// O
// > This is a graduate
/ \__ ~ student, laboratory
|| ///// assistant, automotive
(\ \) (~) // o <--- engineer or other
( \ \ / / // > unfortunate soul
( \ \/ / ____________/ \__O attempting to get
( \__/ / ___ ______\// performance out of a
/ | /@ ( / / ______)/ machine running Linux
( |// \ \ / / (_) by writing a simple
\ () \ \O/ and correct
\ | ) ) multithreaded program.
) ) / /
( |_ / /_
(____> (____>
^
|
|
|
|
This is you.
(with apologies to the haxor brothers,)
Duraid.Quoted 2 lines · Arjan van de Ven
oh you mean the OpenMP broken behavior of calling
sched_yield()in a tight loop to implement spinlocks ?
*plonk*
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Arjan van de Ven
Quoted 5 lines · David Mosberger
Quoted 5 lines
I think the web pages should be most relevant to the HPTC (high
performance technical computing) community, since this is the community that is most likely affected by some of the performance oddities of the O(1) scheduler. Certainly anyone using OpenMP on Intel platforms (x86 and ia64) may want to take a look.
Arjan> oh you mean the OpenMP broken behavior of calling Arjan> sched_yield() in a tight loop to implement spinlocks ?
Please have the courtesy of reading the web page before jumping to conclusions.
--david
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Mike Galbraith
Mike> The page mentions persistent starvation. My own explorations Mike> of this issue indicate that the primary source is always Mike> selecting the highest priority queue.
My working assumption is that the problem is a bug with the dynamic prioritization. The task receiving the signals calls sleep() after handling a signal and hence it's dynamic priority should end up higher than the priority of the task sending signals (since the sender never relinquishes the CPU voluntarily).
However, I haven't actually had time to look at the relevant code, so I may be missing something. If you understand the issue better, please explain to me why this isn't a dynamic priority issue.
--david
Quoted 7 lines · David Mosberger
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <[email protected]>
said:
Mike> The page mentions persistent starvation. My own explorations Mike> of this issue indicate that the primary source is always Mike> selecting the highest priority queue.
Quoted 5 lines
My working assumption is that the problem is a bug with the dynamic prioritization. The task receiving the signals calls
sleep()after handling a signal and hence it's dynamic priority should end up higher than the priority of the task sending signals (since the sender never relinquishes the CPU voluntarily).
The only thing that matters is how much you sleep vs run, so yes, it should have a higher priority unless that handling is heavy on cpu. If it doesn't, then you have to have a different problem, because the dynamic priority portion of the scheduler is dead simple. The only way I can imagine that priority could end up lower than expected is heavyweight interrupt load, or spinning out of control.
Quoted 3 lines
However, I haven't actually had time to look at the relevant code, so I may be missing something. If you understand the issue better, please explain to me why this isn't a dynamic priority issue.
I just saw your other post regarding the web page. Now that I know that there's a detailed description in there somewhere, I'll go read it and see if any of what I've gleaned from crawling around the scheduler code is useful. I thought you might be encountering the same kind of generic starvation I've seen. Ergo, the simple diag patch.
-Mike
Quoted 10 lines · Mike Galbraith
Quoted 5 lines · David Mosberger
Recently, I started to look into some odd performance behaviors of the O(1) scheduler. I decided to document what I found in a web page at:
The page mentions persistent starvation. My own explorations of this issue indicate that the primary source is always selecting the highest priority queue.
It's deeper than that. The O(1) scheduler doesn't consider actual CPU usage as a factor of CPU priority.
Rik
Signature · 2 lines
Engineers don't grow up, they grow sideways. http://www.surriel.com/ http://kernelnewbies.org/
Quoted 6 lines · Rik van Riel
Quoted 5 lines · Mike Galbraith
Quoted 4 lines · David Mosberger
Recently, I started to look into some odd performance behaviors of the O(1) scheduler. I decided to document what I found in a web page at:
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
The page mentions persistent starvation. My own explorations of this issue indicate that the primary source is always selecting the highest priority queue.
It's deeper than that. The O(1) scheduler doesn't consider actual CPU usage as a factor of CPU priority.
Oh, there's no doubt in my mind that it's _much_ deeper than my little surface scratchings ;-)
It does consider cpu usage though. Your run history is right there in your accumulated sleep_avg. Unfortunately (in some ways, fortunate in others.. conflict) that information can be diluted down to nothing instantly by new input from one wakeup.
-Mike
Quoted 13 lines · David Mosberger
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <[email protected]>
said:
Mike> The page mentions persistent starvation. My own explorations Mike> of this issue indicate that the primary source is always Mike> selecting the highest priority queue.
My working assumption is that the problem is a bug with the dynamic prioritization. The task receiving the signals calls
sleep()after handling a signal and hence it's dynamic priority should end up higher than the priority of the task sending signals (since the sender never relinquishes the CPU voluntarily).
Quoted 3 lines
However, I haven't actually had time to look at the relevant code, so I may be missing something. If you understand the issue better, please explain to me why this isn't a dynamic priority issue.
You're right, it looks like a corner case. It works fine here with the attached diff.
-Mike
kernel/sched.c renamed from kernel/sched.c.org +21 -4
@@ -1264,7 +1264,7 @@task_t *prev, *next;runqueue_t *rq;prio_array_t *array; -struct list_head *queue; +struct list_head *head, *curr;int idx;/*
@@ -1286,7 +1286,6 @@ rq =this_rq ();release_kernel_lock (prev); - prev->last_run = jiffies;spin_lock_irq (&rq->lock);/*
@@ -1303,6 +1302,9 @@break ; }default : +/* One sleep credit for releasing the cpu immediately. */ +if (prev->last_run == jiffies && prev->sleep_avg <MAX_SLEEP_AVG ) + prev->sleep_avg++;deactivate_task (prev, rq);case TASK_RUNNING : ;
@@ -1331,8 +1333,22 @@ } idx =sched_find_first_bit (array->bitmap); - queue = array->queue + idx; - next =list_entry (queue->next, task_t, run_list); +next_queue: + head = array->queue + idx; + curr = head->next; + next =list_entry (curr, task_t, run_list); + curr = curr->next; +/* +* If we are about to wrap back to the head of the queue, +* give a lower priority queue a chance to sneak one in. +*/ +if (idx == prev->prio && curr == head && array->nr_active >1 ) { +int tmp =find_next_bit (array->bitmap,MAX_PRIO , ++idx); +if (tmp <MAX_PRIO ) { + idx = tmp; + goto next_queue; + } + } switch_tasks:prefetch (next);
@@ -1342,6 +1358,7 @@if (likely (prev != next)) { rq->nr_switches++; rq->curr = next; + prev->last_run = next->last_run = jiffies;prepare_arch_switch (rq, next); prev =context_switch (rq, prev, next);
Quoted 14 lines · Mike Galbraith
Quoted 13 lines · David Mosberger
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <[email protected]>
said:
Mike> The page mentions persistent starvation. My own explorations Mike> of this issue indicate that the primary source is always Mike> selecting the highest priority queue.
My working assumption is that the problem is a bug with the dynamic prioritization. The task receiving the signals calls
sleep()after handling a signal and hence it's dynamic priority should end up higher than the priority of the task sending signals (since the sender never relinquishes the CPU voluntarily).
Quoted 5 lines
Quoted 3 lines
However, I haven't actually had time to look at the relevant code, so I may be missing something. If you understand the issue better, please explain to me why this isn't a dynamic priority issue.
You're right, it looks like a corner case.
Out of curiosity, is someone hitting that with a real program?
-Mike
aside:
if so, I suppose nano-ticks may be needed. rounding up gave us too many "nano-ticks", and was the first problem with irman, which brought round down into activate_task(). now, test-starve.c appears, and it turns out to be too many nano-ticks _missing_. (rounding up doesn't "fix" that one btw [too fast], but what I did to demonstrate the problem does re-break irman rather nicely:)
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Mike Galbraith
Mike> Out of curiosity, is someone hitting that with a real program?
Yes, it caused a failure in a validation program. The test case is a stripped-down version of the original program and, of course, doesn't make much sense other than to demonstrate the scheduling problem.
--david
Quoted 7 lines · Arjan van de Ven
oh you mean the OpenMP broken behavior of calling
sched_yield()in a tight loop to implement spinlocks ?I'd guess that instead of second guessing the runtime, they should use the pthreads primitives which are the fastest for the platform one would hope.. (eg futexes nowadays)
That really depends on the circumstances. I think there will always be applications that use custom synchronization because they need the last bit of performance in their specific environment.
I just ran a quick test to compare
a) 10,000,000 lock/unlock pairs with a rudimentary custom user-level spinlock implementation, and
b) 10,000,000 pthread_mutex_lock/pthread_mutex_unlock pairs.
All locking is done by a single thread; this is the completely contention-free case.
On a 1GHz Itanium 2 I get
Custom lock: 180 msecs
Custom lock: 1382 msecs
On a 2GHz Xeon, I get
Custom lock: 646 msecs
Custom lock: 1659 msecs
There are good reasons for the differences:
1) The pthread implementation needs an atomic operation on lock exit to check whether waiters need to be awoken. The spin lock just needs a release barrier, which is cheap on both platforms.
2) The custom lock can be inlined. The pthread one normally involves a dynamic library call. That has to be the case if you want to be able to plug in different thread implementations.
3) Pthread locks come in various flavors, and the interface is designed such that you have to check at runtime which flavor you have.
In the contention case there are other interesting issues, since it's often far more efficient to spin before attempting to yield, and pthreads implementations don't always do that.
The original case may also have involved barrier synchronization instead of locks, in which case there is probably at least as much motivation to "roll your own".
To reproduce my results from attached files (ao is my current attempt at a portable atomic operations library):
tar xvfz ao-0.2.tar.gz
cp time_lock.c ao-0.2
cd ao-0.2
gcc -O2 time_lock.c -lpthread
./a.out
Signature · 2 lines
Hans Boehm ([email protected])
#include <pthread.h>
#include <stdio.h>
#include <sys/time.h>
#include "atomic_ops.h"
/* Timing code stolen from Ellis/Kovac/Boehm GCBench. */
#define currentTime() stats_rtclock()
#define elapsedTime(x) (x)
unsigned longstats_rtclock( void )
{
struct timeval t;
struct timezone tz;
if (gettimeofday( &t, &tz ) == -1)
return 0;
return (t.tv_sec * 1000 + t.tv_usec / 1000);
}
AO_TS_T my_spin_lock = AO_TS_INITIALIZER;
pthread_mutex_t my_pthread_lock = PTHREAD_MUTEX_INITIALIZER;
void spin_lock_ool(AO_TS_T *lock)
{
/* Should repeatly retry the AO_test_and_set_acquire, perhaps */
/* after trying a plain read. Should "exponentially" back off */
/* between tries. For short time periods it should spin, for */
/* medium ones it should use sched_yield, and for longer ones usleep. */
/* For now we punt, since this is a contention-free test. */
abort(); }
inline void spin_lock(AO_TS_T *lock)
{
if (__builtin_expect(AO_test_and_set_acquire(lock) != AO_TS_CLEAR, 0))
spin_lock_ool(lock); }
inline void spin_unlock(AO_TS_T *lock)
{
AO_CLEAR(lock);
}
int main()
{
unsigned long start_time, end_time;
int i;
start_time = currentTime();
for (i = 0; i < 10000000; ++i) {
spin_lock(&my_spin_lock);
spin_unlock(&my_spin_lock);
}
end_time = currentTime();
fprintf(stderr, "Custom lock: %lu msecs\n",
elapsedTime(end_time - start_time));
start_time = currentTime();
for (i = 0; i < 10000000; ++i) {
pthread_mutex_lock(&my_pthread_lock);
pthread_mutex_unlock(&my_pthread_lock);
}
end_time = currentTime();
fprintf(stderr, "Custom lock: %lu msecs\n",
elapsedTime(end_time - start_time)); return 0;
}
Quoted 11 lines · Hans Boehm
case.
On a 1GHz Itanium 2 I get
Custom lock: 180 msecs
Custom lock: 1382 msecsOn a 2GHz Xeon, I get
Custom lock: 646 msecs
Custom lock: 1659 msecs
is the pthreads one with nptl ?
Sorry about the typo and misnaming for the test program. I attached the correct version that prints the right labels.
The results I posted did not use NPTL. (Presumably OpenMP wasn't targeted at NPTL either.) I don't think that NPTL has any bearing on the underlying issues that I mentioned, though path lengths are probably a bit shorter. It should also handle contention substantially better, but that wasn't tested.
I did rerun the test case on a 900 MHz Itanium 2 machine with a more recent Debian installation with NPTL. I get 200msecs (20nsecs/iter) with the custom lock, and 768 for pthreads. (With static linking that decreases to 658 for pthreads.) Pthreads (and/or some of the other infrastructure) is clearly getting better, but I don't think the difference will disappear.
I don't have a Xeon with NPTL handy. On an old PPro, the results were 1133 and 4379 msecs for custom and NPTL respectively.
Hans
Quoted 24 lines
-----Original Message-----
From: Arjan van de Ven [mailto:[email protected]]
Sent: Friday, May 23, 2003 1:31 AM
To: Hans Boehm
Cc: Arjan van de Ven; [email protected]; [email protected]; [email protected]
Subject: Re: [Linux-ia64] Re: web page on O(1) schedulerQuoted 11 lines · Hans Boehm
case.
On a 1GHz Itanium 2 I get
Custom lock: 180 msecs
Custom lock: 1382 msecsOn a 2GHz Xeon, I get
Custom lock: 646 msecs
Custom lock: 1659 msecsis the pthreads one with nptl ?
Quoted 5 lines · Hans
Sorry about the typo and misnaming for the test program. I attached the correct version that prints the right labels.
The results I posted did not use NPTL. (Presumably OpenMP wasn't targeted at NPTL either.) I don't think that NPTL has any bearing on the underlying issues that I mentioned, though path lengths are probably a bit shorter. It should also handle contention substantially better, but that wasn't tested.
I did rerun the test case on a 900 MHz Itanium 2 machine with a more recent Debian installation with NPTL. I get 200msecs (20nsecs/iter) with the custom lock, and 768 for pthreads. (With static linking that decreases to 658 for pthreads.) Pthreads (and/or some of the other infrastructure) is clearly getting better, but I don't think the difference will disappear.
To make things more fair you should test against pthread spinlocks. Also, for tight loops like that, even an extra call deep level (that pthread is likely to do) is going to matter.
- Davide
Pthread_spin_lock() under the NPTL version in RH9 does basically what my custom locks do in the uncontested case, aside from the function call. But remember that this began with a discussion about whether it was reasonable for user locking code to explicitly yield rather than relying on pthreads to suspend the thread. I don't think pthread_spin_lock is relevant in this context, for two reasons:
1) At least the RH9 version of pthread_spin_lock in NPTL literally spins and makes no attempt to yield or block. This only makes sense at user level if you are 100% certain that the processors won't be overcommitted. Otherwise there is little to be lost by blocking once you have spun for sufficiently long. You could use pthread_spin_trylock and block explicitly, but that gets us back to custom blocking code.
2) AFAICT, pthread_spin_lock is currently a little too bleeding edge to be widely used. I tried to time it, but failed. Pthread.h doesn't include the declaration for pthread_spin_lock_t by default, at least not yet. It doesn't seem to have a Linux man page, yet. I tried to define the magic macro to get it declared, but that broke something else.
Hans
Quoted 39 lines
-----Original Message-----
From: Davide Libenzi [mailto:[email protected]]
Sent: Friday, May 23, 2003 11:05 AM
To: Boehm, Hans
Cc: 'Arjan van de Ven'; Hans Boehm; MOSBERGER, DAVID (HP-PaloAlto,unix3); Linux Kernel Mailing List; [email protected]
Subject: RE: [Linux-ia64] Re: web page on O(1) schedulerQuoted 1 line · Hans
Sorry about the typo and misnaming for the test program. I
attached the correct version that prints the right labels.
Quoted 2 lines
The results I posted did not use NPTL. (Presumably OpenMP
wasn't targeted at NPTL either.) I don't think that NPTL has any bearing on the underlying issues that I mentioned, though path lengths are probably a bit shorter. It should also handle contention substantially better, but that wasn't tested.
Quoted 2 lines
I did rerun the test case on a 900 MHz Itanium 2 machine
with a more recent Debian installation with NPTL. I get 200msecs (20nsecs/iter) with the custom lock, and 768 for pthreads. (With static linking that decreases to 658 for pthreads.) Pthreads (and/or some of the other infrastructure) is clearly getting better, but I don't think the difference will disappear.
To make things more fair you should test against pthread spinlocks. Also,
for tight loops like that, even an extra call deep level (that pthread is
likely to do) is going to matter.- Davide
Quoted 7 lines · Hans
Pthread_spin_lock()under the NPTL version in RH9 does basically what my custom locks do in the uncontested case, aside from the function call. But remember that this began with a discussion about whether it was reasonable for user locking code to explicitly yield rather than relying on pthreads to suspend the thread. I don't thinkpthread_spin_lockis relevant in this context, for two reasons:
Quoted 6 lines
1) At least the RH9 version of
pthread_spin_lockin NPTL literally spins and makes no attempt to yield or block. This only makes sense at user level if you are 100% certain that the processors won't be overcommitted. Otherwise there is little to be lost by blocking once you have spun for sufficiently long. You could usepthread_spin_trylockand block explicitly, but that gets us back to custom blocking code.
Yes, that would be a spinlock. Your code was basically a spinlock that instead of spinning was doing abort() in contention case. Again, you measured two different things. Even if the pthread mutex does something very simple like :
spinlock(mtx->lock);
while (mtx->busy) {
spinunlock(mtx->lock);
waitforunlocks();
spinlock(mtx->lock);
}
mtx->busy++;
spinunlock(mtx->lock);Only the fact that this code likely reside inside a deeper call lever will make you pay in a tight loop like your.
Quoted 5 lines
2) AFAICT,
pthread_spin_lockis currently a little too bleeding edge to be widely used. I tried to time it, but failed.Pthread.hdoesn't include the declaration forpthread_spin_lock_tby default, at least not yet. It doesn't seem to have a Linux man page, yet. I tried to define the magic macro to get it declared, but that broke something else.
$ gcc -D_GNU_SOURCE ...
- Davide
Thanks for the pointer. In the statically linked case, I get 200/568/345 for custom/pthread_mutex/pthread_spin.
I agree that this is not a fair comparison. That was my point. An implementation with custom yield/sleep
code can do things that you can't do with blocking pthreads primitives at the same performance. (Of course pthreads_mutex_lock will win in other cases.)
Please forget about the abort() in the contention case. I put that there for brevity since it is not exercised by the test. The intent was to time the noncontention performance of a custom lock that first spins, then yields, and then sleeps, as was stated in the comment.
You are forgetting two issues in your analysis of what pthreads is/should be doing relative to the spin-lock-like code:
1) The unlock code is different. If you potentially do a waitforunlocks() in the locking code, you need to at least check whether the corresponding notification is necessary when you unlock(). For NPTL that requires another atomic operation, and hence another dozen to a couple of hundred cycles, depending on the processor. You need to look at both the lock and unlock code.
2) (I hadn't mentioned this before.) The (standard interpretation of) the memory barrier semantics of the pthreads primitives is too strong. Arguably they need to be full memory barriers in both directions.
The pthread_spin_lock code inserts an extra full
memory barrier on IA64 as a result, instead of just
using the acquire barrier associated with the cmpxchg.acq instruction. (I think the spin unlock code doesn't do this. One could argue that that's a bug, though I would argue that the bug is really in the pthreads spec.)
Hans
Quoted 69 lines
-----Original Message-----
From: Davide Libenzi [mailto:[email protected]]
Sent: Friday, May 23, 2003 5:20 PM
To: Boehm, Hans
Cc: 'Arjan van de Ven'; Hans Boehm; MOSBERGER, DAVID (HP-PaloAlto,unix3); Linux Kernel Mailing List; [email protected]
Subject: RE: [Linux-ia64] Re: web page on O(1) schedulerQuoted 1 line · Hans
Pthread_spin_lock()under the NPTL version in RH9 doesbasically what my
Quoted 1 line
custom locks do in the uncontested case, aside from the
function call.
Quoted 2 lines
But remember that this began with a discussion about whether it was reasonable for user locking code to explicitly yield rather
than relying
Quoted 1 line
on pthreads to suspend the thread. I don't think
pthread_spin_lockisQuoted 3 lines
relevant in this context, for two reasons:
1) At least the RH9 version of
pthread_spin_lockin NPTLliterally spins
Quoted 1 line
and makes no attempt to yield or block. This only makes
sense at user
Quoted 2 lines
level if you are 100% certain that the processors won't be overcommitted. Otherwise there is little to be lost by
blocking once you
Quoted 1 line
have spun for sufficiently long. You could use
pthread_spin_trylockandQuoted 1 line
block explicitly, but that gets us back to custom blocking code.
Yes, that would be a spinlock. Your code was basically a spinlock that instead of spinning was doing
abort()in contention case. Again, you measured two different things. Even if the pthread mutex does something
very simple like :spinlock(mtx->lock); while (mtx->busy) { spinunlock(mtx->lock); waitforunlocks(); spinlock(mtx->lock); } mtx->busy++; spinunlock(mtx->lock);Only the fact that this code likely reside inside a deeper call lever will
make you pay in a tight loop like your.Quoted 1 line
2) AFAICT,
pthread_spin_lockis currently a little toobleeding edge to
Quoted 2 lines
be widely used. I tried to time it, but failed.
Pthread.hdoesn't include the declaration forpthread_spin_lock_tby default,at least not
Quoted 1 line
yet. It doesn't seem to have a Linux man page, yet. I
tried to define
Quoted 1 line
the magic macro to get it declared, but that broke something else.
$ gcc -D_GNU_SOURCE ...- Davide
Quoted 16 lines · Hans
Thanks for the pointer. In the statically linked case, I get 200/568/345 for custom/pthread_mutex/pthread_spin.
I agree that this is not a fair comparison. That was my point. An implementation with custom yield/sleep
code can do things that you can't do with blocking pthreads primitives at the same performance. (Of coursepthreads_mutex_lockwill win in other cases.)Please forget about the
abort()in the contention case. I put that there for brevity since it is not exercised by the test. The intent was to time the noncontention performance of a custom lock that first spins, then yields, and then sleeps, as was stated in the comment.You are forgetting two issues in your analysis of what pthreads is/should be doing relative to the spin-lock-like code:
Quoted 6 lines
1) The unlock code is different. If you potentially do a
waitforunlocks()in the locking code, you need to at least check whether the corresponding notification is necessary when youunlock(). For NPTL that requires another atomic operation, and hence another dozen to a couple of hundred cycles, depending on the processor. You need to look at both the lock and unlock code.
That code was completely independent by what pthread might do. I didn't look at the code but I think the new pthread uses futexes for mutexes. The code wanted only to show that a mutex lock does more than a spinlock. And this "more" is amplified by your tight loop.
Quoted 8 lines
2) (I hadn't mentioned this before.) The (standard interpretation of) the memory barrier semantics of the pthreads primitives is too strong. Arguably they need to be full memory barriers in both directions.
Thepthread_spin_lockcode inserts an extra full
memory barrier on IA64 as a result, instead of just
using the acquire barrier associated with the cmpxchg.acq instruction. (I think the spin unlock code doesn't do this. One could argue that that's a bug, though I would argue that the bug is really in the pthreads spec.)
You need a write memory barrier even on the unlock. Consider this :
spinlock = 1; ... protected_resource = NEWVAL; spinlock = 0;
( where spinlock = 0/1 strip down, but do not lose the concept, the lock operation ). If a CPU reorder those writes, another CPU might see the lock drop before the protected resource assignment. And this is usually bad for obvious reasons.
- Davide
Quoted 11 lines · Davide Libenzi
You need a write memory barrier even on the unlock. Consider this :
spinlock = 1; ... protected_resource = NEWVAL; spinlock = 0;( where spinlock = 0/1 strip down, but do not lose the concept, the lock operation ). If a CPU reorder those writes, another CPU might see the lock drop before the protected resource assignment. And this is usually bad for obvious reasons.
David made me notice about a brain misfire here. You need protection even for loads crossing the unlock. For the same obvious reasons :) Yes, a realease barrier will be sufficent for ia64, while you'll need an mfence on P4.
- Davide
Quoted 14 lines · Davide Libenzi
Quoted 11 lines · Davide Libenzi
You need a write memory barrier even on the unlock. Consider this :
spinlock = 1; ... protected_resource = NEWVAL; spinlock = 0;( where spinlock = 0/1 strip down, but do not lose the concept, the lock operation ). If a CPU reorder those writes, another CPU might see the lock drop before the protected resource assignment. And this is usually bad for obvious reasons.
Quoted 5 lines
David made me notice about a brain misfire here. You need protection even for loads crossing the unlock. For the same obvious reasons :) Yes, a realease barrier will be sufficent for ia64, while you'll need an mfence on P4.
Agreed. The problem is that pthreads arguably requires a full barrier, not just a release barrier, though on second though that's not completely clear. At the moment the IA64 spin_unlock code just uses st.rel, which is what I would do in my own lock implementation. On the other hand, the code to acquire the lock uses
mf;; cmpxchg4.acq
which is more expensive than what I would use.
Clearly the two are inconsistent. I would vote for dropping the fence in the lock acquisition code, since it's really useless, AFAICT.
(I think the standards require that memory be "synchronized" at locks and unlocks, which would tend to argue for a full barrier. On the other hand, accessing shared variables outside of locks invokes undefined behavior, so there's probably no way to tell if it's really only a one-way barrier.)
Signature · 2 lines
Hans Boehm ([email protected])
Quoted 11 lines · Hans Boehm
Agreed. The problem is that pthreads arguably requires a full barrier, not just a release barrier, though on second though that's not completely clear. At the moment the IA64
spin_unlockcode just uses st.rel, which is what I would do in my own lock implementation. On the other hand, the code to acquire the lock usesmf;; cmpxchg4.acqwhich is more expensive than what I would use.
Quoted 8 lines
Clearly the two are inconsistent. I would vote for dropping the fence in the lock acquisition code, since it's really useless, AFAICT.
(I think the standards require that memory be "synchronized" at locks and unlocks, which would tend to argue for a full barrier. On the other hand, accessing shared variables outside of locks invokes undefined behavior, so there's probably no way to tell if it's really only a one-way barrier.)
The problem is the abstraction used by pthread. It uses a system dependent testandset() and a system independent __pthread_acquire(). The problem is the the system dependent testandset() carry with it some "useful" properties in many CPUs. Sadly enough those properties are not enough to guarantee the complete spinlock semantics. So some extra memory fencing is required to complete it. This extra memory fencing might indeed hurt some CPU performance. My suggestion would be to move __pthread_acquire() and __pthread_release() inside the system dependent bits so that we can take full advantage of the more consistent memory fencing mechanism.
- Davide
Quoted 13 lines · Mike Galbraith
Quoted 12 lines · Rik van Riel
Quoted 10 lines · Mike Galbraith
Quoted 5 lines · David Mosberger
Recently, I started to look into some odd performance behaviors of the O(1) scheduler. I decided to document what I found in a web page at:
The page mentions persistent starvation. My own explorations of this issue indicate that the primary source is always selecting the highest priority queue.
Quoted 6 lines
Quoted 2 lines
It's deeper than that. The O(1) scheduler doesn't consider actual CPU usage as a factor of CPU priority.
Oh, there's no doubt in my mind that it's _much_ deeper than my little surface scratchings ;-)
It does consider cpu usage though. Your run history is right there in your accumulated
sleep_avg. Unfortunately (in some ways, fortunate in others.. conflict) that information can be diluted down to nothing instantly by new input from one wakeup.
Or did you mean that it misses a bunch of cpu usage? I went looking at cpu usage, and...
Unless there's something seriously b0rked in the attached (don't _think_ so, but...;), trusting an irq that happens 1/ms to tick tasks isn't 100% effective, even if you aren't context switching a zillion times faster. The attached diff produced the attached log while running test-starve.c. I get some pretty serious thievery even when doing ho-hum stuff. We can deactivate tasks at _really_ high frequency, and besides, if the timer interrupt doesn't fire while the last runnable task is active, he can be missed for a while and have accumulated up nearly a full ms. It seems to me that with the right timing, you could end up stealing a bunch of cpu (my logs say it's happening a _lot_ under load. again, diff might be b0rked)
-Mike
COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. ROADRUNNER! 308:19 stole 2 msecs. COYOTE! 309:22 not ticked for 27 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 4 msecs. COYOTE! 309:22 not ticked for 5 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 36 msecs. COYOTE! 309:22 not ticked for 37 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 74 msecs. COYOTE! 309:22 not ticked for 75 msecs. COYOTE! 309:22 not ticked for 76 msecs. COYOTE! 309:22 not ticked for 77 msecs. COYOTE! 309:22 not ticked for 78 msecs. COYOTE! 309:22 not ticked for 79 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 65 msecs. COYOTE! 309:22 not ticked for 66 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 4 msecs. COYOTE! 309:22 not ticked for 5 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 38 msecs. COYOTE! 309:22 not ticked for 39 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 3 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:22 not ticked for 2 msecs. COYOTE! 309:22 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 47 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. ROADRUNNER! 309:23 stole 30 msecs. ROADRUNNER! 309:23 stole 1 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 68 msecs. COYOTE! 309:23 not ticked for 69 msecs. COYOTE! 309:23 not ticked for 70 msecs. COYOTE! 309:23 not ticked for 71 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 60 msecs. COYOTE! 309:23 not ticked for 61 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 3 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 309:23 not ticked for 2 msecs. COYOTE! 309:23 not ticked for 1 msecs. COYOTE! 308:20 not ticked for 1 msecs.
include/linux/sched.h renamed from include/linux/sched.h.org +2 -1
@@ -328,7 +328,8 @@prio_array_t *array;unsigned long sleep_avg; -unsigned long last_run; +unsigned long long last_run; +unsigned int used_nsecs;unsigned long policy;unsigned long cpus_allowed;
kernel/sched.c renamed from kernel/sched.c.org +58 -16
164 lines not on this page · raw message
arch/i386/kernel/timers/timer_tsc.c renamed from arch/i386/kernel/timers/timer_tsc.c.org +3 -2
@@ -102,12 +102,13 @@static unsigned long long monotonic_clock_tsc (void ) {unsigned long long last_offset, this_offset, base; +unsigned long flags;/* atomically read monotonic base & last_offset */ -read_lock_irq (&monotonic_lock); +read_lock_irqsave (&monotonic_lock, flags); last_offset = ((unsigned long long )last_tsc_high<<32 )|last_tsc_low; base = monotonic_base; -read_unlock_irq (&monotonic_lock); +read_unlock_irqrestore (&monotonic_lock, flags);/* Read the Time Stamp Counter */ rdtscll (this_offset);
kernel/printk.c renamed from kernel/printk.c.org +2 -0
@@ -510,8 +510,10 @@ console_may_schedule =0 ;up (&console_sem);spin_unlock_irqrestore (&logbuf_lock, flags); +#if 0 if (wake_klogd && !oops_in_progress &&waitqueue_active (&log_wait))wake_up_interruptible (&log_wait); +#endif }/** console_conditional_schedule - yield the CPU if required