Baby's User-level Threads

This post shows the implementaion of a simple user-level thread package. The package contains only two source files: uthread.c and uthread_switch.s

uthread.c

  1 #include <stdio.h>    // for printf()
  2 #include <stdlib.h>   // for exit()
  3 
  4 /* Possible states of a thread; */
  5 #define FREE        0x0
  6 #define RUNNING     0x1
  7 #define RUNNABLE    0x2
  8 
  9 #define STACK_SIZE  8192
 10 #define MAX_THREAD  4
 11 
 12 typedef struct thread thread_t, *thread_p;
 13 typedef struct mutex mutex_t, *mutex_p;
 14 
 15 struct thread {
 16   int        sp;                /* curent stack pointer */
 17   char       stack[STACK_SIZE];   /* the thread's stack */
 18   int        state;             /* running, runnable, waiting */
 19 };
 20 static thread_t all_thread[MAX_THREAD];
 21 thread_p  current_thread;
 22 thread_p  next_thread;
 23 extern void thread_switch(void);
 24 
 25 void 
 26 thread_init(void)
 27 {
 28   // main() is thread 0, which will make the first invocation to
 29   // thread_schedule().  it needs a stack so that the first thread_switch() can
 30   // save thread 0's state.  thread_schedule() won't run the main thread ever
 31   // again, because it is state is set to RUNNING, and thread_schedule() selects
 32   // a RUNNABLE thread.
 33   current_thread = &all_thread[0];
 34   current_thread->state = RUNNING;
 35 }
 36 
 37 static void 
 38 thread_schedule(void)
 39 {
 40   thread_p t;
 41 
 42   /* Find another runnable thread. */
 43   for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
 44     if (t->state == RUNNABLE && t != current_thread) {
 45       next_thread = t;
 46       break;
 47     }
 48   }
 49 
 50   if (t >= all_thread + MAX_THREAD && current_thread->state == RUNNABLE) {
 51     /* The current thread is the only runnable thread; run it. */
 52     next_thread = current_thread;
 53   }
 54 
 55   if (next_thread == 0) {
 56     printf("thread_schedule: no runnable threads; deadlock
");
 57     exit(1);
 58   }
 59 
 60   if (current_thread != next_thread) {         /* switch threads?  */
 61     next_thread->state = RUNNING;
 62     thread_switch();
 63   } else
 64     next_thread = 0;
 65 }
 66 
 67 void 
 68 thread_create(void (*func)())
 69 {
 70   thread_p t;
 71 
 72   for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
 73     if (t->state == FREE) break;
 74   }
 75   t->sp = (int) (t->stack + STACK_SIZE);      // set sp to the top of the stack
 76   t->sp -= 4;                              // space for return address
 77   * (int *) (t->sp) = (int)func;             // push return address on stack
 78   t->sp -= 32;                             // space for registers that thread_switch will push
 79   t->state = RUNNABLE;
 80 }
 81 
 82 void 
 83 thread_yield(void)
 84 {
 85   current_thread->state = RUNNABLE;
 86   thread_schedule();
 87 }
 88 
 89 static void 
 90 mythread(void)
 91 {
 92   int i;
 93   printf("my thread running
");
 94   for (i = 0; i < 100; i++) {
 95     printf("my thread 0x%x
", (int) current_thread);
 96     thread_yield();
 97   }
 98   printf("my thread: exit
");
 99   current_thread->state = FREE;
100   thread_schedule();
101 }
102 
103 
104 int 
105 main(int argc, char *argv[]) 
106 {
107   thread_init();
108   thread_create(mythread);
109   thread_create(mythread);
110   thread_schedule();
111   return 0;
112 }

uthread_switch.s

 1     .text
 2 
 3 /* Switch from current_thread to next_thread. Make next_thread
 4  * the current_thread, and set next_thread to 0.
 5  * Use eax as a temporary register, which should be caller saved.
 6  */
 7     .globl thread_switch
 8 thread_switch:
 9     pushal
10     movl current_thread, %eax
11     movl %esp, (%eax)              // save stack pointer of current thread
12     movl next_thread, %eax             
13     movl %eax, current_thread       
14     movl $0, next_thread            
15     movl (%eax), %esp              // switch stack pointer to resume next thread
16     popal                         
17     ret                             // pop return address from stack

Compliing and running the program (gcc 4.8.5, CentOS Linux release 7.1.1503, x86-64)

gcc -m32 -o uthread uthread.c uthread_switch.s

$ ./uthread 
my thread running
my thread 0x804c068
my thread running
my thread 0x804e070
my thread 0x804c068
my thread 0x804e070
...
my thread 0x804c068
my thread 0x804e070
my thread 0x804c068
my thread 0x804e070
my thread: exit
my thread: exit
thread_schedule: no runnable threads; deadlock

Discussion

The user-level thread package interacts badly with the operating system in several ways. For example, if one user-level thread blocks in a system call, another user-level thread won't run, because the user-level threads scheduler doesn't know that one of its threads has been descheduled by the OS's scheduler. As another example, two user-level threads will not run concurrently on different cores, because the OS scheduler isn't aware that there are multiple threads that could run in parallel. Note that if two user-level threads were to run truly in parallel, this implementation won't work because of several races (e.g., two threads on different processors could call thread_schedule concurrently, select the same runnable thread, and both run it on different processors.)

There are several ways of addressing these problems. One is using scheduler activations and another is to use one kernel thread per user-level thread (as Linux kernels do).