Bug 7744

Comment 1 Masafumi Max NAKANE 1998-08-29 20:53:24 UTC

Responsible Changed
From-To: gnats-admin->freebsd-bugs

Misfiled PR. 

-----BEGIN PGP SIGNED MESSAGE-----

This provides additional information about this pr and
also about additional related bugs.


==============BEGIN FORWARDED MESSAGE==================
>From: "Richard Seaman, Jr." <dick@tar.com>
>To: "current@freebsd.org" <current@freebsd.org>
>Date: Mon, 31 Aug 98 07:54:30 -0500
>Reply-To: "Richard Seaman, Jr." <dick@tar.com>
>Priority: Normal
>X-Mailer: PMMail 1.92 For OS/2
>MIME-Version: 1.0
>Content-Type: text/plain; charset="us-ascii"
>Content-Transfer-Encoding: 7bit
>Subject: 1,000,001 yields and still second thread doesn't execute
>

I've suggested in a previous message (and a pr) that there may
be some bugs in the pthread scheduler.  Upon further investigation
it appears they may be more extensive than I thought.

I've attached a demonstration program.  It starts 2 threads. Depending
on the option, the threads are either "compute bound", or simply
"yield threads".  The latter threads basically just execute
pthread_yield.

For the yield thread case, even though a thread executes 1,000,001
yields, the other thread never executes until the executing thread
terminates.  It appears that whether a yield "works" depends on
the circumstances.  In some cases it works ok, but for this example
on this processor it doesn't.  (It's possible the results of this
demo may depend on the processor speed).

For the "compute bound" case, once a thread starts executing, it
is never pre-empted.  While it may be that the pthreads spec doesn't
require an executing thread to be pre-empted (ie. it may have to
block or explicitly yield), my reading of the FreeBSD pthreads
scheduler sure seems to imply that it intends for pre-emption every
.1 seconds.   

I've attached some patches that appear to correct these problems.
Perhaps someone who knows more about this than I do can look this
over.

Sample output:

dick@ns$ ./demo y 1000000                        
Thread     Count Start Time   End Time  Reverses 
- ------   ------- ----------   --------  -------- 
0        1000000   17.79662   35.03773         1 
1        1000000    0.00042   17.79638         1 
Total elapsed time is   35.03781 seconds         

dick@ns$ ./demo c 1000000                        
Thread     Count Start Time   End Time  Reverses 
- ------   ------- ----------   --------  -------- 
0        1000000   23.21921   46.52943         1 
1        1000000    0.00042   23.21886         1 
Total elapsed time is   46.52956 seconds         

Sample output after patches:

dick@ns$ ./demo y 1000000                        
Thread     Count Start Time   End Time  Reverses 
- ------   ------- ----------   --------  -------- 
0        1000000    0.00042   36.87421   1000000 
1        1000000    0.00045   36.87443   1000000 
Total elapsed time is   36.87446 seconds         

dick@ns$ ./demo c 1000000                        
Thread     Count Start Time   End Time  Reverses 
- ------   ------- ----------   --------  -------- 
0        1000000    0.00041   46.09844       153 
1        1000000    0.19127   46.61039       153 
Total elapsed time is   46.61044 seconds         

- ---------------------- start demo.c ---------------------------------------
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
typedef struct _mythreaddata {
   int            r;
   pthread_t      pth;
   int            revs;
   struct timeval tstart;
   struct timeval tend;
} mythreaddata, *pmythreaddata;

#define NUM_TEST_THREADS 2
void compute_bound_thread (pmythreaddata ptd);
void yield_thread         (pmythreaddata ptd);

mythreaddata td[NUM_TEST_THREADS];
int          reps;
pthread_t    lastth;

int main(int argc, char *argv[])
{
  int             i;
  struct timeval  tstart, tend;
  int             testtime;
  int             tstarttime;
  int             tendtime;
  void (*fn)(pmythreaddata);
 
  if (argc > 1 && (*(argv[1]) == 'c' || *(argv[1]) == 'C')){
     fn = compute_bound_thread;
  } else if (argc > 1 && (*(argv[1]) == 'y' || *(argv[1]) == 'Y')){
     fn = yield_thread;
  } else {
     exit(1);
  }
  if (argc > 2) {
     reps = atoi (argv[2]);
  } else {
     reps = 30000;
  }

  gettimeofday (&tstart, NULL);
  for (i = 0; i < NUM_TEST_THREADS; i++) 
     pthread_create(&(td[i].pth), NULL,(void *)fn, (void *) &(td[i]));
  for (i = 0; i < NUM_TEST_THREADS; i++)
     pthread_join(td[i].pth, NULL);
  gettimeofday (&tend, NULL);

  printf ("Thread     Count Start Time   End Time  Reverses\n");
  printf ("------   ------- ----------   --------  --------\n");
  for (i = 0; i < NUM_TEST_THREADS; i++) {
     tstarttime  = (td[i].tstart.tv_sec - tstart.tv_sec) * 1000000 + (td[i].tstart.tv_usec - tstart.tv_usec);
     tendtime    = (td[i].tend.tv_sec   - tstart.tv_sec) * 1000000 + (td[i].tend.tv_usec   - tstart.tv_usec);
     printf ("%i     %10i %10.5f %10.5f  %8i\n", i, td[i].r, (double)tstarttime / 1000000.0,
             (double)tendtime   / 1000000.0, td[i].revs);
  }
  testtime  = (tend.tv_sec - tstart.tv_sec) * 1000000 + (tend.tv_usec - tstart.tv_usec);
  printf ("Total elapsed time is %10.5f seconds\n", (double)testtime / 1000000.0);
  return 0; 
}

void compute_bound_thread (pmythreaddata ptd)
{
  int i, j, x;

  pthread_yield();
  gettimeofday (&(ptd->tstart), NULL);

  for (i = 0;  i < reps; i++) {

    /* do some calculation -- be careful this doesn't get optimized away */
    for (j = 0; j < 1000; j++) x = x + i;

    /* a crude and possibly inaccurate measure of our concurrency. */
    if (ptd->pth != lastth)
       ptd->revs++;
    lastth = ptd->pth;

    ptd->r++;
  }
  gettimeofday (&(ptd->tend), NULL);
}

void yield_thread (pmythreaddata ptd)
{
  int i, j, x;

  pthread_yield();
  gettimeofday (&(ptd->tstart), NULL);

  for (i = 0;  i < reps; i++) {

    /* We can do a little something here if we want, without changing the outcome 
    for (j = 0; j < 1000; j++) x = x + i;
    */

    /* Yield to allow other threads to continue. Doesn't work. */
    pthread_yield();

    /* a crude measure of our concurrency.*/
    if (ptd->pth != lastth)
       ptd->revs++;
    lastth = ptd->pth;

    ptd->r++;
  }
  gettimeofday (&(ptd->tend), NULL);
}
- ---------------------- end demo.c -----------------------------------------
- ---------------------- start patches --------------------------------------
*** uthread_kern.c.orig	Fri Aug 28 08:11:15 1998
- --- uthread_kern.c	Fri Aug 28 14:30:47 1998
***************
*** 285,294 ****
  			 * Accumulate the number of microseconds that this
  			 * thread has run for: 
  			 */
! 			_thread_run->slice_usec += (_thread_run->last_inactive.tv_sec -
! 				_thread_run->last_active.tv_sec) * 1000000 +
! 				_thread_run->last_inactive.tv_usec -
! 				_thread_run->last_active.tv_usec;
  
  			/*
  			 * Check if this thread has reached its allocated
- --- 285,296 ----
  			 * Accumulate the number of microseconds that this
  			 * thread has run for: 
  			 */
! 			if (_thread_run->slice_usec != -1) {
!  			        _thread_run->slice_usec += (_thread_run->last_inactive.tv_sec -
! 				        _thread_run->last_active.tv_sec) * 1000000 +
! 				        _thread_run->last_inactive.tv_usec -
! 				        _thread_run->last_active.tv_usec;
!                         }
  
  			/*
  			 * Check if this thread has reached its allocated
***************
*** 321,327 ****
  				 * the last incremental priority check was
  				 * made: 
  				 */
! 				else if (timercmp(&_thread_run->last_inactive, &kern_inc_prio_time, <)) {
  					/*
  					 * Increment the incremental priority
  					 * for this thread in the hope that
- --- 323,329 ----
  				 * the last incremental priority check was
  				 * made: 
  				 */
! 				else if (timercmp(&pthread->last_inactive, &kern_inc_prio_time, <)) {
  					/*
  					 * Increment the incremental priority
  					 * for this thread in the hope that
***************
*** 661,666 ****
- --- 663,669 ----
  				 * Do a sigreturn to restart the thread that
  				 * was interrupted by a signal: 
  				 */
+ 		                _thread_kern_in_sched = 0;
  				_thread_sys_sigreturn(&_thread_run->saved_sigcontext);
  			} else
  				/*
*** uthread_sig.c.orig	Fri Aug 28 08:12:24 1998
- --- uthread_sig.c	Fri Aug 28 14:30:58 1998
***************
*** 149,155 ****
  		 * unfortunate time which one of the threads is
  		 * modifying the dead thread list:
  		 */
! 		if (thread_dead_lock.access_lock)
  			/*
  			 * Set a flag so that the thread that has
  			 * the lock yields when it unlocks the
- --- 149,155 ----
  		 * unfortunate time which one of the threads is
  		 * modifying the dead thread list:
  		 */
! 		else if (thread_dead_lock.access_lock)
  			/*
  			 * Set a flag so that the thread that has
  			 * the lock yields when it unlocks the
- ---------------------- end patches ----------------------------------------












===================END FORWARDED MESSAGE===================


Dick

Richard Seaman, Jr.         dick@tar.com
5182 North Maple Lane       voice: 414-367-5450
Nashotah, WI 53058          fax:   414-367-5852
PGP key available from:     dick-pgp-key@tar.com                            

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3a
Charset: noconv

iQCVAwUBNessOei0Y7619PhpAQFSZgP/Sk8XEZ6BtrS+xYW/iYBPzmcFa6jL1DxI
YjO6oVBxyKQgdO9AvDOI9UBvgcF+24AMOC/TMG5rBrPERd0LHKFe5ft4McXQQv8F
qrydXrAZIb8hHtSk7ZE+8vhFNLEKE9K/A13BYFT6L9GGkbSlG5/TR1iJTYUtcXG7
9q4Tf8+X/sg=
=5qnL
-----END PGP SIGNATURE-----

Comment 3 dt 1998-10-09 21:34:17 UTC

State Changed
From-To: open->closed

Fixed in -current. Thanks.