Skip to contentSkip to conversation

web page on O(1) scheduler

Linux-ia64 Arjan van de Ven 9 participants 25 messages May 21, 2003 – May 25, 2003 Scheduler

lore
Share & tools
lore
#0 lore raw
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)

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

http://www.hpl.hp.com/research/linux/kernel/o1.php

<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

#2 lore raw
In reply to Arjan van de Ven
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);
#3 lore raw
In reply to Arjan van de Ven

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 ?

#5 lore raw
In reply to Arjan van de Ven
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
#6 lore raw
In reply to Arjan van de Ven
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
#7 lore raw
In reply to Arjan van de Ven
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

#8 lore raw
In reply to Arjan van de Ven
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:

http://www.hpl.hp.com/research/linux/kernel/o1.php

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/
#9 lore raw
In reply to Arjan van de Ven
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

http://www.hpl.hp.com/research/linux/kernel/o1.php

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

#10 lore raw
In reply to Arjan van de Ven
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);
#11 lore raw
In reply to Arjan van de Ven
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:)

#12 lore raw
In reply to Arjan van de Ven
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
#13 lore raw
In reply to Arjan van de Ven
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 long
stats_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;
}

#14 lore raw
In reply to Arjan van de Ven
Quoted 11 lines · Hans Boehm

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

is the pthreads one with nptl ?

#15 lore raw
In reply to Arjan van de Ven

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) scheduler

Quoted 11 lines · Hans Boehm

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

is the pthreads one with nptl ?

#16 lore raw
In reply to Arjan van de Ven
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

#17 lore raw
In reply to Arjan van de Ven

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) scheduler

Quoted 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

#18 lore raw
In reply to Arjan van de Ven
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 think pthread_spin_lock is relevant in this context, for two reasons:

Quoted 6 lines

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.

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_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.

$ gcc -D_GNU_SOURCE ...

- Davide

#19 lore raw
In reply to Arjan van de Ven

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) scheduler

Quoted 1 line · Hans

Pthread_spin_lock() under the NPTL version in RH9 does

basically 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_lock is

Quoted 3 lines

relevant in this context, for two reasons:

1) At least the RH9 version of pthread_spin_lock in NPTL

literally 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_trylock and

Quoted 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_lock is currently a little too

bleeding edge to

Quoted 2 lines

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

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

#20 lore raw
In reply to Arjan van de Ven
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 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:

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 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.

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.
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.)

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

#21 lore raw
In reply to Arjan van de Ven
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

#22 lore raw
In reply to Arjan van de Ven
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])
#23 lore raw
In reply to Arjan van de Ven
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_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.

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

#24 lore raw
In reply to Arjan van de Ven
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:

http://www.hpl.hp.com/research/linux/kernel/o1.php

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