[Linux-ia64] Re: web page on O(1) scheduler

[Linux-ia64] Re: web page on O(1) scheduler

[Arjan van de Ven]

[-- Attachment #1: Type: text/plain, Size: 675 bytes --]

On Wed, 2003-05-21 at 08:49, David Mosberger wrote:

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

[Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

At 11:49 PM 5/20/2003 -0700, David Mosberger wrote:
>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>

>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 

[Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

[-- Attachment #1: Type: text/plain, Size: 210 bytes --]

At 11:26 AM 5/21/2003 +0200, Mike Galbraith wrote:

>Try the attached overly simplistic (KISS:) diff, and watch your starvation 
>issues be very noticably reduced.

Ahem ;-)

Now even attached.

         -Mike 

[-- Attachment #2: xx.diff --]
[-- Type: application/octet-stream, Size: 929 bytes --]

--- linux-2.5.69/kernel/sched.c.org	Wed May 21 07:45:00 2003
+++ linux-2.5.69/kernel/sched.c	Wed May 21 08:27:09 2003
@@ -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);

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Duraid Madina]

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.


Arjan van de Ven wrote:
 > oh you mean the OpenMP broken behavior of calling sched_yield() in a
 > tight loop to implement spinlocks ?

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Christoph Hellwig]

*plonk*

[Linux-ia64] Re: web page on O(1) scheduler

[David Mosberger]

>>>>> On 21 May 2003 11:01:33 +0200, Arjan van de Ven <arjanv@redhat.com> said:

  Arjan> On Wed, 2003-05-21 at 08:49, David Mosberger wrote:
  >>  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

[Linux-ia64] Re: web page on O(1) scheduler

[David Mosberger]

>>>>> On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <efault@gmx.de> 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).

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

[Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

At 10:56 AM 5/21/2003 -0700, David Mosberger wrote:
> >>>>> On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <efault@gmx.de> 
> 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).

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.

>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 

[Linux-ia64] Re: web page on O(1) scheduler

[Rik van Riel]

On Wed, 21 May 2003, Mike Galbraith wrote:
> At 11:49 PM 5/20/2003 -0700, David Mosberger wrote:
> >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
-- 
Engineers don't grow up, they grow sideways.
http://www.surriel.com/		http://kernelnewbies.org/

[Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

At 08:38 PM 5/21/2003 -0400, Rik van Riel wrote:
>On Wed, 21 May 2003, Mike Galbraith wrote:
> > At 11:49 PM 5/20/2003 -0700, David Mosberger wrote:
> > >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.

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 

[Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

[-- Attachment #1: Type: text/plain, Size: 951 bytes --]

At 10:56 AM 5/21/2003 -0700, David Mosberger wrote:
> >>>>> On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <efault@gmx.de> 
> 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).
>
>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 

[-- Attachment #2: xx.diff --]
[-- Type: application/octet-stream, Size: 1553 bytes --]

--- linux-2.5.69.virgin/kernel/sched.c.org	Wed May 21 07:45:00 2003
+++ linux-2.5.69.virgin/kernel/sched.c	Thu May 22 11:06:12 2003
@@ -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);

[Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

At 11:52 AM 5/22/2003 +0200, Mike Galbraith wrote:
>At 10:56 AM 5/21/2003 -0700, David Mosberger wrote:
>> >>>>> On Wed, 21 May 2003 11:26:31 +0200, Mike Galbraith <efault@gmx.de> 
>> 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).
>>
>>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:) 

[Linux-ia64] Re: web page on O(1) scheduler

[David Mosberger]

>>>>> On Thu, 22 May 2003 18:25:54 +0200, Mike Galbraith <efault@gmx.de> said:

  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

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Hans Boehm]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2114 bytes --]

On Wed, 21 May 2003, Arjan van de Ven wrote:

> 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

-- 
Hans Boehm
(hboehm@hpl.hp.com)

[-- Attachment #2: ao-0.2.tar.gz --]
[-- Type: APPLICATION/x-gzip, Size: 13274 bytes --]

[-- Attachment #3: time_lock.s --]
[-- Type: TEXT/PLAIN, Size: 1759 bytes --]

#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;
}

Re: [Linux-ia64] Re: web page on O(1) scheduler

[Arjan van de Ven]

On Thu, May 22, 2003 at 06:07:46PM -0700, Hans Boehm wrote:
> 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 ?

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Boehm, Hans]

[-- Attachment #1: Type: text/plain, Size: 1526 bytes --]

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

> -----Original Message-----
> From: Arjan van de Ven [mailto:arjanv@redhat.com]
> Sent: Friday, May 23, 2003 1:31 AM
> To: Hans Boehm
> Cc: Arjan van de Ven; davidm@hpl.hp.com; linux-kernel@vger.kernel.org;
> linux-ia64@linuxia64.org
> Subject: Re: [Linux-ia64] Re: web page on O(1) scheduler
> 
> 
> On Thu, May 22, 2003 at 06:07:46PM -0700, Hans Boehm wrote:
> > 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 ?
> 


[-- Attachment #2: time_lock.c --]
[-- Type: application/octet-stream, Size: 1760 bytes --]

#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, "Pthread lock: %lu msecs\n",
	  elapsedTime(end_time - start_time));
  return 0;
}

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Boehm, Hans wrote:

> 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

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Boehm, 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:

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

> -----Original Message-----
> From: Davide Libenzi [mailto:davidel@xmailserver.org]
> 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; 
> linux-ia64@linuxia64.org
> Subject: RE: [Linux-ia64] Re: web page on O(1) scheduler
> 
> 
> On Fri, 23 May 2003, Boehm, Hans wrote:
> 
> > 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
> 

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Boehm, Hans wrote:

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

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.


> 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

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Boehm, 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:

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

> -----Original Message-----
> From: Davide Libenzi [mailto:davidel@xmailserver.org]
> 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; 
> linux-ia64@linuxia64.org
> Subject: RE: [Linux-ia64] Re: web page on O(1) scheduler
> 
> 
> On Fri, 23 May 2003, Boehm, Hans wrote:
> 
> > 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.
> 
> 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.
> 
> 
> > 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
> 

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Boehm, Hans wrote:

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

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.



> 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

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Fri, 23 May 2003, Davide Libenzi wrote:

> 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

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Hans Boehm]

On Sat, 24 May 2003, Davide Libenzi wrote:

> On Fri, 23 May 2003, Davide Libenzi wrote:
> 
> > 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.
> 
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.)

-- 
Hans Boehm
(hboehm@hpl.hp.com)

RE: [Linux-ia64] Re: web page on O(1) scheduler

[Davide Libenzi]

On Sat, 24 May 2003, Hans Boehm wrote:

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

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

[Linux-ia64] Re: web page on O(1) scheduler

[Mike Galbraith]

[-- Attachment #1: Type: text/plain, Size: 1936 bytes --]

At 07:52 AM 5/22/2003 +0200, Mike Galbraith wrote:
>At 08:38 PM 5/21/2003 -0400, Rik van Riel wrote:
>>On Wed, 21 May 2003, Mike Galbraith wrote:
>> > At 11:49 PM 5/20/2003 -0700, David Mosberger wrote:
>> > >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.
>
>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 

[-- Attachment #2: xx.log --]
[-- Type: application/octet-stream, Size: 7260 bytes --]

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.

[-- Attachment #3: xx.diff --]
[-- Type: application/octet-stream, Size: 6575 bytes --]

--- linux-2.5.69.virgin/include/linux/sched.h.org	Fri May 23 07:14:23 2003
+++ linux-2.5.69.virgin/include/linux/sched.h	Sat May 24 08:03:40 2003
@@ -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;
--- linux-2.5.69.virgin/kernel/sched.c.org	Sun May 25 06:05:42 2003
+++ linux-2.5.69.virgin/kernel/sched.c	Sun May 25 10:04:14 2003
@@ -74,6 +74,10 @@
 #define MAX_SLEEP_AVG		(10*HZ)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
+#define SCHED_NANOSECOND	1
+#define SCHED_MILLISECOND	(1000000 * SCHED_NANOSECOND)
+
+extern unsigned long long monotonic_clock(void);
 
 /*
  * If a task is 'interactive' then we reinsert it in the active
@@ -342,7 +346,8 @@
  */
 static inline int activate_task(task_t *p, runqueue_t *rq)
 {
-	long sleep_time = jiffies - p->last_run - 1;
+	unsigned long long now = monotonic_clock();
+	long sleep_time =  (long)(now - p->last_run) / SCHED_MILLISECOND;
 	int requeue_waker = 0;
 
 	if (sleep_time > 0) {
@@ -514,7 +519,9 @@
 				__activate_task(p, rq);
 			else {
 				requeue_waker = activate_task(p, rq);
-				if (p->prio < rq->curr->prio)
+				if (p->prio < rq->curr->prio ||
+						(0 && p->prio == rq->curr->prio &&
+						p->time_slice > rq->curr->time_slice))
 					resched_task(rq->curr);
 			}
 			success = 1;
@@ -1182,11 +1189,12 @@
 	int cpu = smp_processor_id();
 	runqueue_t *rq = this_rq();
 	task_t *p = current;
+	int idle = p == rq->idle, used_msecs;
 
 	if (rcu_pending(cpu))
 		rcu_check_callbacks(cpu, user_ticks);
 
-	if (p == rq->idle) {
+	if (idle) {
 		/* note: this timer irq context must be accounted for as well */
 		if (irq_count() - HARDIRQ_OFFSET >= SOFTIRQ_OFFSET)
 			kstat_cpu(cpu).cpustat.system += sys_ticks;
@@ -1194,8 +1202,7 @@
 			kstat_cpu(cpu).cpustat.iowait += sys_ticks;
 		else
 			kstat_cpu(cpu).cpustat.idle += sys_ticks;
-		rebalance_tick(rq, 1);
-		return;
+		goto out;
 	}
 	if (TASK_NICE(p) > 0)
 		kstat_cpu(cpu).cpustat.nice += user_ticks;
@@ -1203,12 +1210,12 @@
 		kstat_cpu(cpu).cpustat.user += user_ticks;
 	kstat_cpu(cpu).cpustat.system += sys_ticks;
 
+	spin_lock(&rq->lock);
 	/* Task might have expired already, but not scheduled off yet */
 	if (p->array != rq->active) {
 		set_tsk_need_resched(p);
-		return;
+		goto out_unlock;
 	}
-	spin_lock(&rq->lock);
 	/*
 	 * The task was running during this tick - update the
 	 * time slice counter and the sleep average. Note: we
@@ -1217,8 +1224,15 @@
 	 * it possible for interactive tasks to use up their
 	 * timeslices at their highest priority levels.
 	 */
-	if (p->sleep_avg)
-		p->sleep_avg--;
+	if ((used_msecs = p->used_nsecs / SCHED_MILLISECOND)) {
+		p->used_nsecs -= used_msecs * SCHED_MILLISECOND;
+		if (p->sleep_avg >= used_msecs)
+			p->sleep_avg -= used_msecs;
+		else p->sleep_avg = 0;
+		if (p->policy != SCHED_FIFO && used_msecs > p->time_slice)
+			printk(KERN_DEBUG "ROADRUNNER! %d:%d stole %d msecs.\n",
+				p->pid, p->prio-100, used_msecs - p->time_slice);
+	}
 	if (unlikely(rt_task(p))) {
 		/*
 		 * RR tasks need a special form of timeslice management.
@@ -1233,7 +1247,7 @@
 			dequeue_task(p, rq->active);
 			enqueue_task(p, rq->active);
 		}
-		goto out;
+		goto out_unlock;
 	}
 	if (!--p->time_slice) {
 		dequeue_task(p, rq->active);
@@ -1249,9 +1263,10 @@
 		} else
 			enqueue_task(p, rq->active);
 	}
-out:
+out_unlock:
 	spin_unlock(&rq->lock);
-	rebalance_tick(rq, 0);
+out:
+	rebalance_tick(rq, idle);
 }
 
 void scheduling_functions_start_here(void) { }
@@ -1264,8 +1279,9 @@
 	task_t *prev, *next;
 	runqueue_t *rq;
 	prio_array_t *array;
-	struct list_head *queue;
+	struct list_head *head, *curr;
 	int idx;
+	static int last_pid, last_msused;
 
 	/*
 	 * Test if we are atomic.  Since do_exit() needs to call into
@@ -1286,7 +1302,6 @@
 	rq = this_rq();
 
 	release_kernel_lock(prev);
-	prev->last_run = jiffies;
 	spin_lock_irq(&rq->lock);
 
 	/*
@@ -1331,8 +1346,32 @@
 	}
 
 	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 (0 && 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;
+		}
+	}
+	if (prev != rq->idle && prev->array == rq->active &&
+			prev->used_nsecs / SCHED_MILLISECOND >= 1) {
+		if (last_pid != prev->pid ||
+				last_msused != prev->used_nsecs / SCHED_MILLISECOND)
+		printk(KERN_DEBUG "COYOTE! %d:%d not ticked for %d msecs.\n",
+			prev->pid, prev->prio-100,
+			prev->used_nsecs / SCHED_MILLISECOND);
+		last_pid = prev->pid;
+		last_msused = prev->used_nsecs / SCHED_MILLISECOND;
+	}
 
 switch_tasks:
 	prefetch(next);
@@ -1340,8 +1379,11 @@
 	RCU_qsctr(prev->thread_info->cpu)++;
 
 	if (likely(prev != next)) {
+		unsigned long long now = monotonic_clock();
 		rq->nr_switches++;
 		rq->curr = next;
+		prev->used_nsecs += now - prev->last_run;
+		prev->last_run = next->last_run = now;
 
 		prepare_arch_switch(rq, next);
 		prev = context_switch(rq, prev, next);
--- linux-2.5.69.virgin/arch/i386/kernel/timers/timer_tsc.c.org	Sat May 24 08:55:05 2003
+++ linux-2.5.69.virgin/arch/i386/kernel/timers/timer_tsc.c	Sat May 24 09:26:09 2003
@@ -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);
--- linux-2.5.69.virgin/kernel/printk.c.org	Sun May 25 09:10:38 2003
+++ linux-2.5.69.virgin/kernel/printk.c	Sun May 25 09:11:04 2003
@@ -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