Pthreads has safe synchronization using yields
authorBarret Rhoden <brho@cs.berkeley.edu>
Mon, 19 Apr 2010 23:48:40 +0000 (16:48 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:43 +0000 (17:35 -0700)
The mutexes and barriers will spin for a little and yield if they don't
win (adaptive mutexes) to avoid deadlock/horrible inefficiences if the
lock holder or slow one is descheduled.  pthread_join() also won't spin
anymore.

tests/pthread_test.c
user/include/pthread.h
user/parlib/pthread.c

index 6dc52fa..46f5bc5 100644 (file)
@@ -15,7 +15,7 @@ pthread_t my_threads[10];
 void *my_retvals[10];
 
 __thread int my_id;
-void *thread(void* arg)
+void *yield_thread(void* arg)
 {      
        for (int i = 0; i < 10; i++) {
                printf_safe("[A] pthread %d on vcore %d\n", pthread_self()->id, vcore_id());
@@ -26,23 +26,42 @@ void *thread(void* arg)
        return (void*)(pthread_self()->id);
 }
 
+void *hello_thread(void* arg)
+{      
+       printf_safe("[A] pthread %d on vcore %d\n", pthread_self()->id, vcore_id());
+       return (void*)(pthread_self()->id);
+}
+
 int main(int argc, char** argv) 
 {
        void *retval1 = 0;
        void *retval2 = 0;
 
+       /* yield test */
        printf_safe("[A] About to create thread 1\n");
-       pthread_create(&t1, NULL, &thread, NULL);
+       pthread_create(&t1, NULL, &yield_thread, NULL);
        printf_safe("[A] About to create thread 2\n");
-       pthread_create(&t2, NULL, &thread, NULL);
+       pthread_create(&t2, NULL, &yield_thread, NULL);
        printf_safe("About to create thread 3\n");
-       pthread_create(&t3, NULL, &thread, NULL);
+       pthread_create(&t3, NULL, &yield_thread, NULL);
        while(1);
+       #if 0
+       /* join on them */
+       printf_safe("[A] About to join on thread 1\n");
+       pthread_join(t1, &retval1);
+       printf_safe("[A] Successfully joined on thread 1 (retval: %p)\n", retval1);
+       printf_safe("[A] About to join on thread 2\n");
+       pthread_join(t2, &retval2);
+       printf_safe("[A] Successfully joined on thread 2 (retval: %p)\n", retval2);
+       printf_safe("About to join on thread 3\n");
+       pthread_join(t3, NULL);
+       #endif
 
+       /* create and join on hellos */
        while (1) {
                for (int i = 1; i < 10; i++) {
                        printf_safe("[A] About to create thread %d\n", i);
-                       pthread_create(&my_threads[i], NULL, &thread, NULL);
+                       pthread_create(&my_threads[i], NULL, &hello_thread, NULL);
                }
                for (int i = 1; i < 10; i++) {
                        printf_safe("[A] About to join on thread %d\n", i);
@@ -51,22 +70,4 @@ int main(int argc, char** argv)
                                    my_retvals[i]);
                }
        }
-
-       printf_safe("[A] About to create thread 1\n");
-       pthread_create(&t1, NULL, &thread, NULL);
-       printf_safe("[A] About to create thread 2\n");
-       pthread_create(&t2, NULL, &thread, NULL);
-       printf_safe("About to create thread 3\n");
-       pthread_create(&t3, NULL, &thread, NULL);
-
-       printf_safe("[A] Vcore0 spinning\n");
-       printf_safe("[A] About to join on thread 1\n");
-       pthread_join(t1, &retval1);
-       printf_safe("[A] Successfully joined on thread 1 (retval: %p)\n", retval1);
-       printf_safe("[A] About to join on thread 2\n");
-       pthread_join(t2, &retval2);
-       printf_safe("[A] Successfully joined on thread 2 (retval: %p)\n", retval2);
-       printf_safe("About to join on thread 3\n");
-       pthread_join(t3, NULL);
-       while(1);
 } 
index 8532dc3..78c3d33 100644 (file)
@@ -46,6 +46,8 @@ enum
 #define PTHREAD_MUTEX_INITIALIZER {0}
 #define PTHREAD_MUTEX_NORMAL 0
 #define PTHREAD_MUTEX_DEFAULT PTHREAD_MUTEX_NORMAL
+#define PTHREAD_MUTEX_SPINS 100 // totally arbitrary
+#define PTHREAD_BARRIER_SPINS 100 // totally arbitrary
 #define PTHREAD_COND_INITIALIZER {0}
 #define PTHREAD_PROCESS_PRIVATE 0
 
@@ -66,7 +68,7 @@ typedef struct
   volatile int sense;
   int count;
   int nprocs;
-  mcs_lock_t lock;
+  pthread_mutex_t pmutex;
 } pthread_barrier_t;
 
 typedef struct
index b7781ed..9322bab 100644 (file)
@@ -24,6 +24,7 @@ int threads_active = 0;
 
 /* Helper / local functions */
 static int get_next_pid(void);
+static inline void spin_to_sleep(unsigned int spins, unsigned int *spun);
 
 __thread struct pthread_tcb *current_thread = 0;
 
@@ -246,9 +247,8 @@ int pthread_join(pthread_t thread, void** retval)
                printf("[pthread] trying to join on a detached pthread");
                return -1;
        }
-       // TODO: something smarter than spinning (deschedule, etc)
-       while(!thread->finished)
-               cpu_relax(); // has a memory clobber
+       while (!thread->finished)
+               pthread_yield();
        if (retval)
                *retval = thread->retval;
        free(thread);
@@ -362,11 +362,25 @@ int pthread_mutex_init(pthread_mutex_t* m, const pthread_mutexattr_t* attr)
   return 0;
 }
 
+/* Set *spun to 0 when calling this the first time.  It will yield after 'spins'
+ * calls.  Use this for adaptive mutexes and such. */
+static inline void spin_to_sleep(unsigned int spins, unsigned int *spun)
+{
+       if ((*spun)++ == spins) {
+               pthread_yield();
+               *spun = 0;
+       }
+}
+
 int pthread_mutex_lock(pthread_mutex_t* m)
 {
-  while(pthread_mutex_trylock(m))
-    while(*(volatile size_t*)&m->lock);
-  return 0;
+       unsigned int spinner = 0;
+       while(pthread_mutex_trylock(m))
+               while(*(volatile size_t*)&m->lock) {
+                       cpu_relax();
+                       spin_to_sleep(PTHREAD_MUTEX_SPINS, &spinner);
+               }
+       return 0;
 }
 
 int pthread_mutex_trylock(pthread_mutex_t* m)
@@ -536,18 +550,19 @@ int pthread_barrier_init(pthread_barrier_t* b, const pthread_barrierattr_t* a, i
 
   b->sense = 0;
   b->nprocs = b->count = count;
-  mcs_lock_init(&b->lock);
+  pthread_mutex_init(&b->pmutex, 0);
   return 0;
 }
 
 int pthread_barrier_wait(pthread_barrier_t* b)
 {
+  unsigned int spinner = 0;
   int id = vcore_id();
   int ls = b->local_sense[32*id] = 1 - b->local_sense[32*id];
 
-  mcs_lock_lock(&b->lock);
+  pthread_mutex_lock(&b->pmutex);
   int count = --b->count;
-  mcs_lock_unlock(&b->lock);
+  pthread_mutex_unlock(&b->pmutex);
 
   if(count == 0)
   {
@@ -557,12 +572,16 @@ int pthread_barrier_wait(pthread_barrier_t* b)
   }
   else
   {
-    while(b->sense != ls);
+    while(b->sense != ls) {
+      cpu_relax();
+      spin_to_sleep(PTHREAD_BARRIER_SPINS, &spinner);
+    }
     return 0;
   }
 }
 
 int pthread_barrier_destroy(pthread_barrier_t* b)
 {
+  pthread_mutex_destroy(&b->pmutex);
   return 0;
 }