Date: Mon, 31 Aug 1998 16:10:00 -0700 (PDT) From: "Richard Seaman, Jr." <dick@tar.com> To: freebsd-bugs@FreeBSD.ORG Subject: Re: bin/7744: Pthread scheduler bug Message-ID: <199808312310.QAA27563@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
The following reply was made to PR bin/7744; it has been noted by GNATS.
From: "Richard Seaman, Jr." <dick@tar.com>
To: "freebsd-gnats-submit@freebsd.org" <freebsd-gnats-submit@freebsd.org>
Cc: Subject: Re: bin/7744: Pthread scheduler bug
Date: Mon, 31 Aug 98 18:05:29 -0500
-----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-----
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-bugs" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199808312310.QAA27563>