From owner-freebsd-current Mon Aug 31 05:55:34 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id FAA14741 for freebsd-current-outgoing; Mon, 31 Aug 1998 05:55:34 -0700 (PDT) (envelope-from owner-freebsd-current@FreeBSD.ORG) Received: from ns.tar.com (ns.tar.com [204.95.187.2]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id FAA14736 for ; Mon, 31 Aug 1998 05:55:29 -0700 (PDT) (envelope-from dick@tar.com) Received: from ppro.tar.com (ppro.tar.com [204.95.187.9]) by ns.tar.com (8.9.1/8.8.7) with SMTP id HAA24463 for ; Mon, 31 Aug 1998 07:54:31 -0500 (CDT) Message-Id: <199808311254.HAA24463@ns.tar.com> From: "Richard Seaman, Jr." To: "current@freebsd.org" Date: Mon, 31 Aug 98 07:54:30 -0500 Reply-To: "Richard Seaman, Jr." 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 Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG 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 #include #include 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