一、Switching threads


这个作业要求在 xv6 中实现用户级线程,并实现线程间的上下文切换。

首先在 xv6 中添加两个文件: uthread.cuthread_switch.S。再在 xv6/Makefile 中 _forktest rule 后面添加:

_uthread: uthread.o uthread_switch.o
	$(LD) $(LDFLAGS) -N -e main -Ttext 0 -o _uthread uthread.o uthread_switch.o $(ULIB)
	$(OBJDUMP) -S _uthread > uthread.asm

最后在 UPROGS 中添加 _uthread\。这时启动 xv6 会报错 Page Fault(trapno=14):

wu@wu-insparition:~/6.828/xv6/xv6-public$ make CPUS=1 qemu-nox
qemu-system-i386 -nographic -drive file=fs.img,index=1,media=disk,format=raw -drive file=xv6.img,index=0,media=disk,format=raw -smp 1 -m 512 
xv6...
cpu0: starting 0
sb: size 1000 nblocks 941 ninodes 200 nlog 30 logstart 2 inodestart 32 bmap start 58
init: starting sh
$ uthread
pid 4 uthread: trap 14 err 5 on cpu 0 eip 0xffffffff addr 0xffffffff--kill proc

这时需要我们深入理解上面提供的代码。实现用户级线程(以后简称线程)的关键就是下面这个数据结构:

struct thread {
  int        sp;                /* saved stack pointer */
  char stack[STACK_SIZE];       /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
};

线程需要维护自己的栈区(内存区域)和线程状态,并且手动维护栈指针来管理栈。这里要注意主线程栈区和我们实现的线程栈区的区别,下面是它俩在虚拟地址空间中的位置关系:

+------------+
|   kernel   |
+------------+
|  run-time  |
|   stack    | <-+ main thread
+-----+------+
|     |      |
|     v      |
|            |
|     ^      |
|     |      |
+-----+------+
|            |
|    heap    |
|            |
+------------+
|    .bss    | <-+ user-level thread
+------------+
|   .data    |
+------------+
|  read-only |
|    code    |
|   segment  |
+------------+
|  unused    |
+------------+

首先是 thread_init() 函数:

void 
thread_init(void)
{
  current_thread = &all_thread[0];
  current_thread->state = RUNNING;
}

这个函数将主线程(main)当做数组 all_thread[] 中第一个元素来管理,然后调用两次 thread_create() 函数:

void 
thread_create(void (*func)())
{
  thread_p t;
  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == FREE) break;
  }
  t->sp = (int) (t->stack + STACK_SIZE);  
  t->sp -= 4;                            
  *(int *) (t->sp) = (int)func;           
  t->sp -= 32;                            
  t->state = RUNNABLE;
}

这个函数寻找数组 all_thread[] 中线程状态为 FREE 的空槽,对其初始化,如果将 .bss 放大(暂时忽略结构体中为了对齐而产生的空隙):

              .bss
         +-------------+
         |     ...     |
  +----> +-------------+
  |      |    state    | RUNNABLE
  |      +-------------+
  |      |    func     |
  |      +-------------+ <--------+
  |      |   thread    |          |
  |      |   switch    |    32 Bytes(8 registers)
  |      |  registers  |          |
  |      +-------------+ <-+ sp +-+
Thread 2 |    ...      |
  |      +-------------+
  |      |     sp      |
  +----> +-------------+
  |      |    state    | RUNNING
  |      +-------------+
  |      |    func     |
  |      +-------------+ <--------+
  |      |   thread    |          |
  |      |   switch    |    32 Bytes(8 registers)
  |      |  registers  |          |
  |      +-------------+ <-+ sp +-+
Thread 1 |    ...      |
  |      +-------------+
  |      |     sp      |
  +----> +-------------+ <-+ next_thread
  |      |    state    | RUNNING
  |      +-------------+
  |      |     ...     |
Thread 0 |    stack    |
 (main)  |     ...     |
  |      +-------------+
  |      |     sp      |
  +----> +-------------+ <-+ current_thread
         |     ...     |
         +-------------+

然后执行 thread_schedule() 函数:

static void 
thread_schedule(void)
{
  thread_p t;
  next_thread = 0;
  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == RUNNABLE && t != current_thread) {
      next_thread = t;
      break;
    }
  }
  if (t >= all_thread + MAX_THREAD && current_thread->state == RUNNABLE) {
    next_thread = current_thread;
  }
  if (next_thread == 0) {
    printf(2, "thread_schedule: no runnable threads\n");
    exit();
  }
  if (current_thread != next_thread) {
    next_thread->state = RUNNING;
    thread_switch();
  } else
    next_thread = 0;
}

thread_schedule() 函数在线程数组中顺序找到一个 RUNNABLE 的线程,然后执行 thread_switch 汇编开始线程的上下文切换。下面是完成后的 thread_switch

	.text
	.globl thread_switch
thread_switch:
    pushal
    movl    current_thread, %eax
    movl    %esp, (%eax)
    movl    next_thread, %eax
    movl    (%eax), %esp
	popal
    movl    next_thread, %eax
    movl    %eax, current_thread
    movl    $0, %eax
    movl    %eax, next_thread
	ret			

第一次进入 thread_switch() 后,以后的栈指针就一直指向我们自己实现的用户栈。每次进入 thread_switch() 都让 esp 指向下一个线程的栈顶,那里存放着恢复上下文所需的寄存器信息。完成 current_thread 和 next_thread 的重新赋值后,执行 ret 指令,将 ret address 中的内容放进 eip,转去执行另一个线程。

                                           .bss
                                      +-------------+
                                      |     ...     |
                               +----> +-------------+
                               |      |    state    | RUNNABLE
+-----------------+            |      +-------------+
|    main()       |            |      |    func     | ^ ret address
+-----------------+            |      +-------------+ <--------+
| thread_init()   |            |      |   thread    |          |
+-----------------+            |      |   switch    |    32 Bytes(8 registers)
| thread_create() |            |      |  registers  |          |
+-----------------+            |      +-------------+ <-+ sp +-+
| thread_create() |          Thread 2 |    ...      |
+-----------------+            |      +-------------+
|thread_schedule()|            |      |     sp      |
+-----------------+            +----> +-------------+
|     pushal      |            |      |    state    | RUNNING
|    registers    |            |      +-------------+
+-----------------+ <--+ esp   |      |    func     | <- reg address
|                 |       +    |      +-------------+ <--------+
|                 |       |    |      |   thread    |          |
|                 |       |    |      |   switch    |    32 Bytes(8 registers)
|                 |       |    |      |  registers  |          |
|                 |       |    |      +-------------+ <-+ sp +-+
|                 |       |  Thread 1 |    ...      |
|                 |       |    |      +-------------+
|                 |       |    |      |     sp      |
|                 |       |    +----> +-------------+ <-+ next_thread
|                 |       |    |      |    state    | RUNNING
|                 |       |    |      +-------------+
|                 |       |    |      |     ...     |
+-----------------+       |  Thread 0 |    stack    |
                          |   (main)  |     ...     |
                          |    |      +-------------+
                          |    |      |     sp      | <-------------------+
                          |    +----> +-------------+ <-+ current_thread  |
                          |           |     ...     |                     |
                          |           +-------------+                     |
                          +-----------------------------------------------+

上图中线程栈中的内容只有第一次被调用前是这些内容,一旦第一次调度到这个线程后,将 func 中的内容恢复到 eip,这个线程栈就表现得与一个正常的栈无异了。

               +------------------+
               |    state         |
               +------------------+
               |                  |
               |  thread_yield()  |
               |                  |
               +------------------+
               |                  |
               |thread_schedule() |
               |                  |
         +---> +------------------+
         |     |                  |
         |     |     pushal       |
thread_switch  |    registers     |
         |     |                  |
         +---> +------------------+
               |                  |
               |      ...         |
               |                  |
               +------------------+
               |      sp          |
               +------------------+

栈指针 %esp 不断的在两个栈上来回切换,成功在用户级让两个线程形成并发。

init: starting sh
$ uthread
my thread running
my thread 0x2DE8
my thread running
my thread 0x4DF0
my thread 0x2DE8
my thread 0x4DF0
my thread 0x2DE8
my thread 0x4DF0
...
my thread 0x2DE8
my thread 0x4DF0
my thread: exit
my thread: exit
thread_schedule: no runnable threads
$ 

 

二、Optional Challenges


TODO

按照上面的实现,存在着两个问题:

解决这些问题有两种方法:

Add locks, condition variables, barriers, etc. to thread package.