sched_yield() makes OpenLDAP slow
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 1 line · Howard Chu
You assume that spinlocks are the only reason a developer may want to yield the processor. This assumption is unfounded. Case in point - the primary backend in OpenLDAP uses a transactional database with page-level locking of its data structures to provide high levels of concurrency. It is the nature of such a system to encounter deadlocks over the normal course of operations. When a deadlock is detected, some thread must be chosen (by one of a variety of algorithms) to abort its transaction, in order to allow other operations to proceed to completion. In this situation, the chosen thread must get control of the CPU long enough to clean itself up, and then it must yield the CPU in order to allow any other competing threads to complete their transaction. The thread with the aborted transaction relinquishes all of its locks and then waits to get another shot at the CPU to try everything over again. Again, this is all fundamental to the nature of transactional programming. If the 2.6 kernel makes this programming model unreasonably slow, then quite simply this kernel is not viable as a database platform.
I fail to see how sched_yield is going to be very helpful in this situation. Since that call can sleep from a range of time ranging from zero to a long time, it's going to give unpredictable results.
It seems to me that this sort of thing is why we have POSIX pthread synchronization primitives.. sched_yield is basically there for a process to indicate that "what I'm doing doesn't matter much, let other stuff run". Any other use of it generally constitutes some kind of hack.
Signature · 3 lines
Robert Hancock Saskatoon, SK, Canada To email, remove "nospam" from [email protected] Home Page: http://www.roberthancock.com/
Quoted 3 lines · Robert Hancock
I fail to see how
sched_yieldis going to be very helpful in this situation. Since that call can sleep from a range of time ranging from zero to a long time, it's going to give unpredictable results.
Well, not sleep technically, but yield the CPU for some undefined amount of time.
Quoted 2 lines
It seems to me that this sort of thing is why we have POSIX pthread synchronization primitives..
sched_yieldis basically there for a process to indicate that "what I'm doing doesn't matter much, let other stuff run". Any other use of it generally constitutes some kind of hack.
In SCHED_OTHER mode, you're right, sched_yield is basically meaningless.
In a realtime system, there is a very well defined and probably useful behaviour.
Eg. If 2 SCHED_FIFO processes are running at the same priority, One can call sched_yield to deterministically give the CPU to the other guy.
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 7 lines · Nick Piggin
Quoted 3 lines · Robert Hancock
I fail to see how
sched_yieldis going to be very helpful in this situation. Since that call can sleep from a range of time ranging from zero to a long time, it's going to give unpredictable results.Well, not sleep technically, but yield the CPU for some undefined amount of time.
Since the slapd server was not written to run in realtime, nor is it commonly run on realtime operating systems, I don't believe predictable timing here is a criteria we care about. One could say the same of sigsuspend() by the way - it can pause a process for a range of time ranging from zero to a long time. Should we tell application writers not to use this function either, regardless of whether the developer thinks they have a good reason to use it?
Quoted 5 lines
Quoted 5 lines
It seems to me that this sort of thing is why we have POSIX pthread synchronization primitives..
sched_yieldis basically there for a process to indicate that "what I'm doing doesn't matter much, let other stuff run". Any other use of it generally constitutes some kind of hack.
In terms of transaction recovery, we do an exponential backoff on the retries, because our benchmarks showed that under heavy lock contention, immediate retries only made things worse. In fact, having arbitrarily long backoff delays here was shown to improve transaction throughput. (We use select() with an increasing timeval in combination with the yield() call. One way or another we get a longer delay as desired.)
sched_yield is there for a *thread* to indicate "what I'm doing doesn't matter much, let other stuff run."
I suppose it may be a hack. But then so is TCP congestion control. In both cases, empirical evidence indicates the hack is worthwhile. If you haven't done the analysis then you're in no position to deny the value of the approach.
Quoted 9 lines
In
SCHED_OTHERmode, you're right,sched_yieldis basically meaningless.In a realtime system, there is a very well defined and probably useful behaviour.
Eg. If 2
SCHED_FIFOprocesses are running at the same priority, One can callsched_yieldto deterministically give the CPU to the other guy.
Well yes, the point of a realtime system is to provide deterministic response times to unpredictable input.
I'll note that we removed a number of the yield calls (that were in OpenLDAP 2.2) for the 2.3 release, because I found that they were redundant and causing unnecessary delays. My own test system is running on a Linux 2.6.12.3 kernel (installed over a SuSE 9.2 x86_64 distro), and OpenLDAP 2.3 runs perfectly well here, now that those redundant calls have been removed. But I also found that I needed to add a new yield(), to work around yet another unexpected issue on this system - we have a number of threads waiting on a condition variable, and the thread holding the mutex signals the var, unlocks the mutex, and then immediately relocks it. The expectation here is that upon unlocking the mutex, the calling thread would block while some waiting thread (that just got signaled) would get to run. In fact what happened is that the calling thread unlocked and relocked the mutex without allowing any of the waiting threads to run. In this case the only solution was to insert a yield() after the mutex_unlock(). So again, for those of you claiming "oh, all you need to do is use a condition variable or any of the other POSIX synchronization primitives" - yes, that's a nice theory, but reality says otherwise.
To say that sched_yield is basically meaningless is far overstating your point.
Signature · 4 lines
-- Howard Chu Chief Architect, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc OpenLDAP Core Team http://www.openldap.org/project/
Quoted 10 lines · Howard Chu
But I also found that I needed to add a new
yield(), to work around yet another unexpected issue on this system - we have a number of threads waiting on a condition variable, and the thread holding the mutex signals the var, unlocks the mutex, and then immediately relocks it. The expectation here is that upon unlocking the mutex, the calling thread would block while some waiting thread (that just got signaled) would get to run. In fact what happened is that the calling thread unlocked and relocked the mutex without allowing any of the waiting threads to run. In this case the only solution was to insert ayield()after themutex_unlock().
That's exactly the behavior I would expect. Why would you expect unlocking a mutex to cause a reschedule, if the calling thread still has timeslice left?
Lee
Quoted 12 lines · Lee Revell
Quoted 10 lines · Howard Chu
But I also found that I needed to add a new
yield(), to work around yet another unexpected issue on this system - we have a number of threads waiting on a condition variable, and the thread holding the mutex signals the var, unlocks the mutex, and then immediately relocks it. The expectation here is that upon unlocking the mutex, the calling thread would block while some waiting thread (that just got signaled) would get to run. In fact what happened is that the calling thread unlocked and relocked the mutex without allowing any of the waiting threads to run. In this case the only solution was to insert ayield()after themutex_unlock().
Quoted 3 lines
That's exactly the behavior I would expect. Why would you expect unlocking a mutex to cause a reschedule, if the calling thread still has timeslice left?
That's beside the point. Folks are making an assertion that sched_yield() is meaningless; this example demonstrates that there are cases where sched_yield() is essential.
Signature · 4 lines
-- Howard Chu Chief Architect, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc OpenLDAP Core Team http://www.openldap.org/project/
Quoted 14 lines · Howard Chu
Quoted 12 lines · Lee Revell
Quoted 10 lines · Howard Chu
But I also found that I needed to add a new
yield(), to work around yet another unexpected issue on this system - we have a number of threads waiting on a condition variable, and the thread holding the mutex signals the var, unlocks the mutex, and then immediately relocks it. The expectation here is that upon unlocking the mutex, the calling thread would block while some waiting thread (that just got signaled) would get to run. In fact what happened is that the calling thread unlocked and relocked the mutex without allowing any of the waiting threads to run. In this case the only solution was to insert ayield()after themutex_unlock().
Quoted 7 lines
Quoted 3 lines
That's exactly the behavior I would expect. Why would you expect unlocking a mutex to cause a reschedule, if the calling thread still has timeslice left?
That's beside the point. Folks are making an assertion that
sched_yield()is meaningless; this example demonstrates that there are cases wheresched_yield()is essential.
The point is, with SCHED_OTHER scheduling, sched_yield() need not do anything. It may not let any other tasks run.
The fact that it does on Linux is because we do attempt to do something expected... but the simple matter is that you can't realy on it to do what you expect.
I'm not sure exactly how you would solve the above problem, but I'm sure it can be achieved using mutexes (for example, you could have a queue where every thread waits on its own private mutex).... but I don't do much userspace C programming sorry.
Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 13 lines · Howard Chu
Quoted 12 lines · Lee Revell
Quoted 10 lines · Howard Chu
But I also found that I needed to add a new
yield(), to work around yet another unexpected issue on this system - we have a number of threads waiting on a condition variable, and the thread holding the mutex signals the var, unlocks the mutex, and then immediately relocks it. The expectation here is that upon unlocking the mutex, the calling thread would block while some waiting thread (that just got signaled) would get to run. In fact what happened is that the calling thread unlocked and relocked the mutex without allowing any of the waiting threads to run. In this case the only solution was to insert ayield()after themutex_unlock().
Quoted 7 lines
Quoted 3 lines
That's exactly the behavior I would expect. Why would you expect unlocking a mutex to cause a reschedule, if the calling thread still has timeslice left?
That's beside the point. Folks are making an assertion that
sched_yield()is meaningless; this example demonstrates that there are cases wheresched_yield()is essential.
It is not essential, it is non-portable.
Code you described is based on non-portable "expectations" about thread scheduling. Linux implementation of pthreads fails to satisfy them. Perfectly reasonable. Code is then "fixed" by adding sched_yield() calls and introducing more non-portable assumptions. Again, there is no guarantee this would work on any compliant implementation.
While "intuitive" semantics of sched_yield() is to yield CPU and to give other runnable threads their chance to run, this is _not_ what standard prescribes (for non-RT threads).
Quoted 3 lines
--
-- Howard Chu
Nikita.
Quoted 14 lines · Nikita Danilov
Quoted 3 lines · Howard Chu
That's beside the point. Folks are making an assertion that
sched_yield()is meaningless; this example demonstrates that there are cases wheresched_yield()is essential.It is not essential, it is non-portable.
Code you described is based on non-portable "expectations" about thread scheduling. Linux implementation of pthreads fails to satisfy them. Perfectly reasonable. Code is then "fixed" by adding
sched_yield()calls and introducing more non-portable assumptions. Again, there is no guarantee this would work on any compliant implementation.
Quoted 4 lines
While "intuitive" semantics of
sched_yield()is to yield CPU and to give other runnable threads their chance to run, this is _not_ what standard prescribes (for non-RT threads).
Very well; it is not prescribed in the standard and it is non-portable. Our code is broken and we will fix it.
But even Dave Butenhof, Mr. Pthreads himself, has said it is reasonable to expect sched_yield to yield the CPU. That's what pthread_yield did in Pthreads Draft 4 (DCE threads) and it is common knowledge that sched_yield is a direct replacement for pthread_yield; i.e., pthread_yield() was deleted from the spec because sched_yield fulfilled its purpose. Now you're saying "well, technically, sched_yield doesn't have to do anything at all" and the letter of the spec supports your position, but anybody who's been programming with pthreads since the DCE days "knows" that is not the original intention. I wonder that nobody has decided to raise this issue with the IEEE/POSIX group and get them to issue a correction/clarification in all this time, since the absence of specification here really impairs the usefulness of the spec.
Likewise the fact that sched_yield() can now cause the current process to be queued behind other processes seems suspect, unless we know for sure that the threads are running with PTHREAD_SCOPE_SYSTEM. (I haven't checked to see if PTHREAD_SCOPE_PROCESS is still supported in NPTL.)
Signature · 4 lines
-- Howard Chu Chief Architect, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc OpenLDAP Core Team http://www.openldap.org/project/
Quoted 9 lines · Howard Chu
Quoted 7 lines · Nick Piggin
Quoted 3 lines · Robert Hancock
I fail to see how
sched_yieldis going to be very helpful in this situation. Since that call can sleep from a range of time ranging from zero to a long time, it's going to give unpredictable results.Well, not sleep technically, but yield the CPU for some undefined amount of time.
Quoted 7 lines
Since the slapd server was not written to run in realtime, nor is it commonly run on realtime operating systems, I don't believe predictable timing here is a criteria we care about. One could say the same of
sigsuspend()by the way - it can pause a process for a range of time ranging from zero to a long time. Should we tell application writers not to use this function either, regardless of whether the developer thinks they have a good reason to use it?
Of course not. We should tell them that if they use sigsuspend() they cannot assume that the process will not wake up immediately.
Lee
Quoted 1 line · Howard Chu
I'll note that we removed a number of the yield calls (that were in OpenLDAP 2.2) for the 2.3 release, because I found that they were redundant and causing unnecessary delays. My own test system is running on a Linux 2.6.12.3 kernel (installed over a SuSE 9.2
x86_64distro), and OpenLDAP 2.3 runs perfectly well here, now that those redundant calls have been removed. But I also found that I needed to add a newyield(), to work around yet another unexpected issue on this system - we have a number of threads waiting on a condition variable, and the thread holding the mutex signals the var, unlocks the mutex, and then immediately relocks it. The expectation here is that upon unlocking the mutex, the calling thread would block while some waiting thread (that just got signaled) would get to run. In fact what happened is that the calling thread unlocked and relocked the mutex without allowing any of the waiting threads to run. In this case the only solution was to insert ayield()after themutex_unlock(). So again, for those of you claiming "oh, all you need to do is use a condition variable or any of the other POSIX synchronization primitives" - yes, that's a nice theory, but reality says otherwise.
I encountered a similar issue with some software that I wrote, and used a similar workaround, however this was basically because there wasn't enough time available at the time to redesign things to work properly. The problem here is essentially caused by the fact that the mutex is being locked for an excessively large proportion of the time and not letting other threads in. In the case I am thinking of, posting the messages to the thread that was hogging the mutex via a signaling queue would have been a better solution than using yield and having correct operation depend on undefined parts of thread scheduling behavior..
Signature · 3 lines
Robert Hancock Saskatoon, SK, Canada To email, remove "nospam" from [email protected] Home Page: http://www.roberthancock.com/
Quoted 30 lines · Robert Hancock
Quoted 10 lines · Howard Chu
I'll note that we removed a number of the yield calls (that were in OpenLDAP 2.2) for the 2.3 release, because I found that they were redundant and causing unnecessary delays. My own test system is running on a Linux 2.6.12.3 kernel (installed over a SuSE 9.2
x86_64distro), and OpenLDAP 2.3 runs perfectly well here, now that those redundant calls have been removed. But I also found that I needed to add a newyield(), to work around yet another unexpected issue on this system - we have a number of threads waiting on a condition variable, and the thread holding the mutex signals the var, unlocks the mutex, and then immediately relocks it. The expectation here is that upon unlocking theQuoted 8 lines
mutex, the calling thread would block while some waiting thread (that just got signaled) would get to run. In fact what happened is that the calling thread unlocked and relocked the mutex without allowing any of the waiting threads to run. In this case the only solution was to insert a
yield()after themutex_unlock(). So again, for those of you claiming "oh, all you need to do is use a condition variable or any of the other POSIX synchronization primitives" - yes, that's a nice theory, but reality says otherwise.I encountered a similar issue with some software that I wrote, and used a similar workaround, however this was basically because there wasn't enough time available at the time to redesign things to work properly. The problem here is essentially caused by the fact that the mutex is being locked for an excessively large proportion of the time and not letting other threads in. In the case I am thinking of, posting the messages to the thread that was hogging the mutex via a signaling queue would have been a better solution than using yield and having correct operation depend on undefined parts of thread scheduling behavior..
Quoted 5 lines
--
Robert Hancock Saskatoon, SK, Canada
To email, remove "nospam" from [email protected] Home Page: http://www.roberthancock.com/
I reported thet sched_yield() wasn't working (at least as expected) back in March of 2004.
for(;;)
sched_yield();
... takes 100% CPU time as reported by top. It should take practically 0. Somebody said that this was because top was broken, others said that it was because I didn't know how to code. Nevertheless, the problem was not fixed, even after schedular changes were made for the current version.
One can execute:
usleep(0);
... instead of:
sched_yield();
... and Linux then performs exactly like other Unixes when code is waiting on mutexes.
Cheers,
Dick Johnson
Penguin : Linux version 2.6.12.5 on an i686 machine (5537.79 BogoMips). Warning : 98.36% of all statistics are fiction.
.
I apologize for the following. I tried to kill it with the above dot :
****************************************************************
The information transmitted in this message is confidential and may be privileged. Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to [email protected] - and destroy all copies of this information, including any attachments, without reading or disclosing them.
Thank you.
Quoted 11 lines · linux-os (Dick Johnson)
I reported thet
sched_yield()wasn't working (at least as expected) back in March of 2004.for(;;)
sched_yield();... takes 100% CPU time as reported by
top. It should take practically 0. Somebody said that this was becausetopwas broken, others said that it was because I didn't know how to code. Nevertheless, the problem was not fixed, even after schedular changes were made for the current version.
This is what I would expect if run on an otherwise idle machine. sched_yield just puts you at the back of the line for runnable processes, it doesn't magically cause you to go to sleep somehow.
Signature · 3 lines
Robert Hancock Saskatoon, SK, Canada To email, remove "nospam" from [email protected] Home Page: http://www.roberthancock.com/
Quoted 13 lines · Robert Hancock
Quoted 11 lines · linux-os (Dick Johnson)
I reported thet
sched_yield()wasn't working (at least as expected) back in March of 2004.for(;;)
sched_yield();... takes 100% CPU time as reported by
top. It should take practically 0. Somebody said that this was becausetopwas broken, others said that it was because I didn't know how to code. Nevertheless, the problem was not fixed, even after schedular changes were made for the current version.
Quoted 4 lines
This is what I would expect if run on an otherwise idle machine.
sched_yieldjust puts you at the back of the line for runnable processes, it doesn't magically cause you to go to sleep somehow.
When a kernel build is occurring??? Plus top itself.... It damn well sleep while giving up the CPU. If it doesn't it's broken.
Quoted 5 lines
--
Robert Hancock Saskatoon, SK, Canada
To email, remove "nospam" from [email protected] Home Page: http://www.roberthancock.com/
Cheers,
Dick Johnson
Penguin : Linux version 2.6.12.5 on an i686 machine (5537.79 BogoMips). Warning : 98.36% of all statistics are fiction.
.
I apologize for the following. I tried to kill it with the above dot :
****************************************************************
The information transmitted in this message is confidential and may be privileged. Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to [email protected] - and destroy all copies of this information, including any attachments, without reading or disclosing them.
Thank you.
Quoted 16 lines · linux-os \(Dick Johnson\)
Quoted 13 lines · Robert Hancock
Quoted 11 lines · linux-os (Dick Johnson)
I reported thet
sched_yield()wasn't working (at least as expected) back in March of 2004.for(;;)
sched_yield();... takes 100% CPU time as reported by
top. It should take practically 0. Somebody said that this was becausetopwas broken, others said that it was because I didn't know how to code. Nevertheless, the problem was not fixed, even after schedular changes were made for the current version.
Quoted 7 lines
Quoted 4 lines
This is what I would expect if run on an otherwise idle machine.
sched_yieldjust puts you at the back of the line for runnable processes, it doesn't magically cause you to go to sleep somehow.When a kernel build is occurring??? Plus
topitself.... It damn well sleep while giving up the CPU. If it doesn't it's broken.
top doesn't run all the time:
# strace -o top.strace -tt top
14:52:19.407958 write(1, " 758 root 16 0 104 2"..., 79) = 79
14:52:19.408318 write(1, " 759 root 16 0 100 1"..., 79) = 79
14:52:19.408659 write(1, " 760 root 16 0 100 1"..., 79) = 79
14:52:19.409001 write(1, " 761 root 18 0 2604 39"..., 74) = 74
14:52:19.409342 write(1, " 763 daemon 17 0 108 1"..., 78) = 78
14:52:19.409672 write(1, " 773 root 16 0 104 2"..., 79) = 79
14:52:19.410010 write(1, " 774 root 16 0 104 2"..., 79) = 79
14:52:19.410362 write(1, " 775 root 16 0 100 1"..., 79) = 79
14:52:19.410692 write(1, " 776 root 16 0 104 2"..., 79) = 79
14:52:19.411136 write(1, " 777 daemon 17 0 108 1"..., 86) = 86
14:52:19.411505 select(1, [0], NULL, NULL, {5, 0}) = 0 (Timeout)
hrrr..... psssss.......14:52:24.411744 time([1124797944]) = 1124797944
14:52:24.411883 lseek(4, 0, SEEK_SET) = 0
14:52:24.411957 read(4, "24822.01 18801.28\n", 1023) = 18
14:52:24.412082 access("/var/run/utmpx", F_OK) = -1 ENOENT (No such file or directory) 14:52:24.412224 open("/var/run/utmp", O_RDWR) = 8
14:52:24.412328 fcntl64(8, F_GETFD) = 0
14:52:24.412399 fcntl64(8, F_SETFD, FD_CLOEXEC) = 0
14:52:24.412467 _llseek(8, 0, [0], SEEK_SET) = 0
14:52:24.412556 alarm(0) = 0
14:52:24.412643 rt_sigaction(SIGALRM, {0x4015a57c, [], SA_RESTORER, 0x40094ae8}, {SIG_DFL}, 8) = 0
14:52:24.412747 alarm(1) = 0
However, kernel compile shouldn't.
I suggest stracing with -tt "for(;;) yield();" test proggy with and without kernel compile in parallel, and comparing the output...
Hmm... actually, knowing that you will argue to death instead...
# cat t.c #include <sched.h>
int main() {
for(;;) sched_yield();
return 0;
}
# gcc t.c
# strace -tt ./a.out
...
15:03:41.211324 sched_yield() = 0
15:03:41.211673 sched_yield() = 0
15:03:41.212034 sched_yield() = 0
15:03:41.212400 sched_yield() = 0
15:03:41.212749 sched_yield() = 0
15:03:41.213126 sched_yield() = 0
15:03:41.213486 sched_yield() = 0
15:03:41.213835 sched_yield() = 0
15:03:41.214220 sched_yield() = 0
15:03:41.214577 sched_yield() = 0
15:03:41.214939 sched_yield() = 0
I start "while true; do true; done" on another console...
15:03:43.314645 sched_yield() = 0
15:03:43.847644 sched_yield() = 0
15:03:43.954635 sched_yield() = 0
15:03:44.063798 sched_yield() = 0
15:03:44.171596 sched_yield() = 0
15:03:44.282624 sched_yield() = 0
15:03:44.391632 sched_yield() = 0
15:03:44.498609 sched_yield() = 0
15:03:44.605584 sched_yield() = 0
15:03:44.712538 sched_yield() = 0
15:03:44.819557 sched_yield() = 0
15:03:44.928594 sched_yield() = 0
15:03:45.040603 sched_yield() = 0
15:03:45.148545 sched_yield() = 0
15:03:45.259311 sched_yield() = 0
15:03:45.368563 sched_yield() = 0
15:03:45.476482 sched_yield() = 0
15:03:45.583568 sched_yield() = 0
15:03:45.690491 sched_yield() = 0
15:03:45.797512 sched_yield() = 0
15:03:45.906534 sched_yield() = 0
15:03:46.013545 sched_yield() = 0
15:03:46.120505 sched_yield() = 0
Ctrl-C# uname -a Linux firebird 2.6.12-r4 #1 SMP Sun Jul 17 13:51:47 EEST 2005 i686 unknown unknown GNU/Linux -- vda
Quoted 9 lines · Denis Vlasenko
Quoted 9 lines
Quoted 5 lines
This is what I would expect if run on an otherwise idle machine.
sched_yieldjust puts you at the back of the line for runnable processes, it doesn't magically cause you to go to sleep somehow.When a kernel build is occurring??? Plus
topitself.... It damn well sleep while giving up the CPU. If it doesn't it's broken.
unless you have all of the kernel source in the buffer cache, a concurrent kernel build will spend a fair bit of time in io_wait state .. as such its perfectly plausible that sched_yield keeps popping back to the top of 'runnable' processes . . .
cheers,
lincoln.