Skip to contentSkip to conversation

sched_yield() makes OpenLDAP slow

DISCUSSION Howard Chu 4 participants 9 messages Aug 19, 2005 – Aug 20, 2005

lore
Share & tools
lore

Howard Chu

author
#0 lore raw

Hm, seems there's a great deal of misinformation in this thread.

Quoted 3 lines

I also think OpenLDAP is wrong. First, it should be calling pthread_yield() because slapd is a multithreading process and it just wants to run the other threads. See:

...

Quoted 2 lines

AFAIKS, sched_yield should only really be used by realtime applications that know exactly what they're doing.

pthread_yield() was deleted from the POSIX threads drafts years ago. sched_yield() is the officially supported API, and OpenLDAP is using it for the documented purpose. Anyone who says "applications shouldn't be using sched_yield()" doesn't know what they're talking about.

Quoted 5 lines

It's really more a feature than a bug that it breaks so easily because they should be really using futexes instead, which have much better behaviour than any sched_yield ever could (they will directly wake up another process waiting for the lock and avoid the thundering herd for contended locks)

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.

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/
#1 lore raw

Hi Howard,

Thanks for joining the discussion. One request, if I may, can you retain the CC list on posts please?

Quoted 7 lines · Howard Chu
Quoted 3 lines

AFAIKS, sched_yield should only really be used by realtime applications that know exactly what they're doing.

pthread_yield() was deleted from the POSIX threads drafts years ago. sched_yield() is the officially supported API, and OpenLDAP is using it for the documented purpose. Anyone who says "applications shouldn't be using sched_yield()" doesn't know what they're talking about.

Linux's SCHED_OTHER policy offers static priorities in the range [0..0]. I think anything else would be a bug, because from my reading of the standards, a process with a higher static priority shall always preempt a process with a lower priority.

And SCHED_OTHER simply doesn't work that way.

So sched_yield() from a SCHED_OTHER task is free to basically do anything at all. Is that the kind of behaviour you had in mind?

Quoted 8 lines
Quoted 5 lines

It's really more a feature than a bug that it breaks so easily because they should be really using futexes instead, which have much better behaviour than any sched_yield ever could (they will directly wake up another process waiting for the lock and avoid the thundering herd for contended locks)

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

You didn't explain why you can't use a mutex to do this. From your brief description, it seems like a mutex might just do the job nicely.

Quoted 2 lines

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.

Actually it should still be fast. It may yield excessive CPU to other tasks (including those that are reniced). You didn't rely on sched_yield providing some semantics about not doing such a thing, did you?

Send instant messages to your online friends http://au.messenger.yahoo.com

#2 lore raw
In reply to Howard Chu
Quoted 2 lines · Howard Chu

If the 2.6 kernel makes this programming model unreasonably slow, then quite simply this kernel is not viable as a database platform.

Pretty much everyone else manages to make it work.

#4 lore raw
In reply to Howard Chu

Howard Chu <[email protected]> writes:

[...]

Quoted 6 lines

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,

What prevents transaction monitor from using, say, condition variables to "yield cpu"? That would have an additional advantage of blocking thread precisely until specific event occurs, instead of blocking for some vague indeterminate load and platform dependent amount of time.

Quoted 3 lines

and then it must yield the CPU in
order to allow any other competing threads to complete their transaction.

Again, this sounds like thing doable with standard POSIX synchronization primitives.

Quoted 3 lines
Signature · 2 lines
-- 
  -- Howard Chu

Nikita.

author
#3 lore raw
In reply to Chris Wedgwood
Quoted 5 lines · Chris Wedgwood
Quoted 2 lines · Howard Chu

If the 2.6 kernel makes this programming model unreasonably slow, then quite simply this kernel is not viable as a database platform.

Pretty much everyone else manages to make it work.

And this contributes to the discussion how? Pretty much every other Unix-ish operating system manages to make scheduling with nice'd processes work. If you really want to get into what "everyone else manages to make work" you're in for a rough ride.

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/
author
#5 lore raw
In reply to Nikita Danilov
Quoted 8 lines · Nikita Danilov
Quoted 6 lines · Howard Chu

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,

Quoted 5 lines

What prevents transaction monitor from using, say, condition variables to "yield cpu"? That would have an additional advantage of blocking thread precisely until specific event occurs, instead of blocking for some vague indeterminate load and platform dependent amount of time.

Condition variables offer no control over which thread is waken up. We're wandering into the design of the SleepyCat BerkeleyDB library here, and we don't exert any control over that either. BerkeleyDB doesn't appear to use pthread condition variables; it seems to construct its own synchronization mechanisms on top of mutexes (and yield calls). In this specific example, we use whatever BerkeleyDB provides and we're certainly not about to write our own transactional embedded database engine just for this.

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/
#6 lore raw
Quoted 1 line · Howard Chu

Nikita Danilov wrote:

[...]

Quoted 8 lines
Quoted 6 lines

What prevents transaction monitor from using, say, condition variables to "yield cpu"? That would have an additional advantage of blocking thread precisely until specific event occurs, instead of blocking for some vague indeterminate load and platform dependent amount of time.

Condition variables offer no control over which thread is waken up.

When only one thread waits on a condition variable, which is exactly a scenario involved, --sorry if I weren't clear enough-- condition signal provides precise control over which thread is woken up.

Quoted 4 lines

We're wandering into the design of the SleepyCat BerkeleyDB library here, and we don't exert any control over that either. BerkeleyDB doesn't appear to use pthread condition variables; it seems to construct its own synchronization mechanisms on top of mutexes (and yield calls).

That returns us to the core of the problem: sched_yield() is used to implement a synchronization primitive and non-portable assumptions are made about its behavior: SUS defines that after sched_yield() thread ceases to run on the CPU "until it again becomes the head of its thread list", and "thread list" discipline is only defined for real-time scheduling policies. E.g.,

int sched_yield(void)

{
       return 0;
}

and

int sched_yield(void)

{
       sleep(100);
       return 0;
}

are both valid sched_yield() implementation for non-rt (SCHED_OTHER) threads.

Nikita.

author
#7 lore raw
Quoted 14 lines · Nikita Danilov

That returns us to the core of the problem: sched_yield() is used to implement a synchronization primitive and non-portable assumptions are made about its behavior: SUS defines that after sched_yield() thread ceases to run on the CPU "until it again becomes the head of its thread list", and "thread list" discipline is only defined for real-time scheduling policies. E.g.,

int sched_yield(void)

{
       return 0;
}

and

Quoted 8 lines

int sched_yield(void)

{
       sleep(100);
       return 0;
}

are both valid sched_yield() implementation for non-rt (SCHED_OTHER) threads.

I think you're mistaken:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/0d4eaf3703131e86/da051ebe58976b00#da051ebe58976b00

sched_yield() is required to be supported even if priority scheduling is not supported, and it is required to cause the calling thread (not process) to yield the processor.

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/
#8 lore raw
Quoted 21 lines · Howard Chu
Quoted 20 lines · Nikita Danilov

That returns us to the core of the problem: sched_yield() is used to implement a synchronization primitive and non-portable assumptions are made about its behavior: SUS defines that after sched_yield() thread ceases to run on the CPU "until it again becomes the head of its thread list", and "thread list" discipline is only defined for real-time scheduling policies. E.g.,

int sched_yield(void)

{
       return 0;
}

and

int sched_yield(void)

{
       sleep(100);
       return 0;
}
Quoted 8 lines
Quoted 2 lines

are both valid sched_yield() implementation for non-rt (SCHED_OTHER) threads.

I think you're mistaken:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/0d4eaf3703131e86/da051ebe58976b00#da051ebe58976b00

sched_yield() is required to be supported even if priority scheduling is not supported, and it is required to cause the calling thread (not process) to yield the processor.

Of course sched_yield() is required to be supported, the question is for how long CPU is yielded. Here is the quote from the SUS (actually the complete definition of sched_yield()):

The sched_yield() function shall force the running thread to relinquish the processor until it again becomes the head of its thread list.

As far as I can see, SUS doesn't specify how "thread list" is maintained for non-RT scheduling policy, and implementation that immediately places SCHED_OTHER thread that called sched_yield() back at the head of its thread list is perfectly valid. Also valid is an implementation that waits for 100 seconds and then places sched_yield() caller to the head of the list, etc. Basically, while semantics of sched_yield() are well defined for RT scheduling policy, for SCHED_OTHER policy standard leaves it implementation defined.

Quoted 3 lines
Signature · 2 lines
-- 
  -- Howard Chu

Nikita.