Date: Mon, 31 Aug 98 07:54:30 -0500 From: "Richard Seaman, Jr." <dick@tar.com> To: "current@freebsd.org" <current@FreeBSD.ORG> Subject: 1,000,001 yields and still second thread doesn't execute Message-ID: <199808311254.HAA24463@ns.tar.com>
next in thread | raw e-mail | index | archive | help
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 ----------------------------------------
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199808311254.HAA24463>