# MIT6.s081-2020 Lab7 Multithreading

lab 7 文档 (opens new window)

本实验将使您熟悉多线程。您将在用户级线程包中实现线程之间的切换，使用多个线程来加速程序，并实现屏障。

# 准备

 git fetch
 git checkout thread
 make clean
1
2
3

# Uthread: switching between threads

引言

在本节中，您将为用户级线程系统设计上下文切换机制，即创建线程并保存/恢复寄存器以在线程之间切换。

实现

本节内容需要在user/uthread.c中添加thread_create()和 thread_schedule()的具体实现，在user/uthread_switch.S中实现thread_switch来切换上下文资源。上述内容可以参考kernel/switch.S和kernel/proc.c

user/uthread_switch.S

thread_switch:
	/* YOUR CODE HERE */
        sd ra, 0(a0)
        sd sp, 8(a0)
        sd s0, 16(a0)
        sd s1, 24(a0)
        sd s2, 32(a0)
        sd s3, 40(a0)
        sd s4, 48(a0)
        sd s5, 56(a0)
        sd s6, 64(a0)
        sd s7, 72(a0)
        sd s8, 80(a0)
        sd s9, 88(a0)
        sd s10, 96(a0)
        sd s11, 104(a0)
        ld ra, 0(a1)
        ld sp, 8(a1)
        ld s0, 16(a1)
        ld s1, 24(a1)
        ld s2, 32(a1)
        ld s3, 40(a1)
        ld s4, 48(a1)
        ld s5, 56(a1)
        ld s6, 64(a1)
        ld s7, 72(a1)
        ld s8, 80(a1)
        ld s9, 88(a1)
        ld s10, 96(a1)
        ld s11, 104(a1)
	ret    /* return to ra */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

为了实现上下文寄存器的保存与回复，我们需要定义context 成员变量保存上下文，即

user/uthread.c

struct context {
  uint64 ra;
  uint64 sp;
  // callee-saved
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
};
struct thread {
  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
  struct context context;
};
void
thread_schedule(void)
{
  struct thread *t, *next_thread;
//...
  if (current_thread != next_thread) {         /* switch threads?  */
    next_thread->state = RUNNING;
    t = current_thread;
    current_thread = next_thread;
    /* YOUR CODE HERE
     * Invoke thread_switch to switch from t to next_thread:
     * thread_switch(??, ??);
     */
    thread_switch((uint64)&t->context,(uint64)&current_thread->context);
  } else
    next_thread = 0;
}
void
thread_create(void (*func)())
{
  struct thread *t;
//...
  // YOUR CODE HERE
  t->context.ra = (uint64)func;
  t->context.sp = (uint64)(&t->stack[STACK_SIZE]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

[注]：栈顶是在高地址，程序运行时新建栈帧往低地址变化，需要将sp指针指向了数组的末尾，避免修改不可修改的内容。

结果

启动xv6，运行uthread指令，即可通过以下测试用例。

image-lab7-1.jpg

# Using threads

引言

在本节中，您将使用哈希表探索线程和锁的并行编程。该部分内容将使用 UNIX下的pthread线程库，而非xv6。

实现

该小节内容涉及共享数据读写的数据冲突问题，需要使用锁的方式来解决。为避免这一系列事件，请在 put和get在notxv6/ph.c因此，缺少两个线程的键数始终为 0。相关的 pthread 调用是：

pthread_mutex_t lock;            // declare a lock
pthread_mutex_init(&lock, NULL); // initialize the lock
pthread_mutex_lock(&lock);       // acquire lock
pthread_mutex_unlock(&lock);     // release lock
1
2
3
4

为了避免多线程交替添加导致数据丢失的同时，提高数据的添加效率，我们可以为每一个哈希桶绑定其唯一的互斥锁，从而避免全局锁情况下，非同一哈希桶的竞争问题，提高效率。

notxv6/ph.c

struct entry *table[NBUCKET];
int keys[NKEYS];
int nthread = 1;
pthread_mutex_t lock[NBUCKET];
static
void put(int key, int value)
{
  int i = key % NBUCKET;
  // is the key already present?
  struct entry *e = 0;
  pthread_mutex_lock(&lock[i]);
  for (e = table[i]; e != 0; e = e->next) {
    if (e->key == key)
      break;
  }
  if(e){
    // update the existing key.
    e->value = value;
  } else {
    // the new is new.
    insert(key, value, &table[i], table[i]);
  }
  pthread_mutex_unlock(&lock[i]);
}
static struct entry*
get(int key)
{
  int i = key % NBUCKET;
  struct entry *e = 0;
  pthread_mutex_lock(&lock[i]);
  for (e = table[i]; e != 0; e = e->next) {
    if (e->key == key) break;
  }
  pthread_mutex_unlock(&lock[i]);
  return e;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

由于是先全部 put 再全部 get 我就不对 get 加锁了，实际写哈希表， get 还是要加锁的

结果

image-lab7-2.jpg

# Barrier

引言

在这个作业中，您将实现一个屏障：应用程序中的一个点，所有参与的线程都必须等待，直到所有其他参与的线程也到达该点。您将使用 pthread 条件变量，这是一种类似于 xv6 的睡眠和唤醒的序列协调技术。

实现

该小节需要设计一个屏障行为，即当且仅当所有需要的线程到达屏障时才能结束等待。您将需要以下新的 pthread 原语：

pthread_cond_wait(&cond, &mutex);  // go to sleep on cond, releasing lock mutex, acquiring upon wake up
pthread_cond_broadcast(&cond);     // wake up every thread sleeping on cond
1
2

notxv6/barrier.c

static void
barrier_init(void)
{
  assert(pthread_mutex_init(&bstate.barrier_mutex, NULL) == 0);
  assert(pthread_cond_init(&bstate.barrier_cond, NULL) == 0);
  bstate.nthread = 0;
  bstate.round = 0;
}
static void
barrier()
{
  // YOUR CODE HERE
  //
  // Block until all threads have called barrier() and
  // then increment bstate.round.
  //
  pthread_mutex_lock(&bstate.barrier_mutex);
  bstate.nthread++;
  if(bstate.nthread != nthread) {
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  } else {
    bstate.nthread = 0;
    bstate.round++;
    pthread_cond_broadcast(&bstate.barrier_cond);
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

结果

image-lab7-3.jpg

运行grade-lab-thread，可以通过所有的测试用例。

image-lab7-4.jpg

# 总结

该lab内容较为简单，所涉及的多线程内容，不论是上下文切换、锁、屏障，都是并发编程中常见的情况，加深我对线程交互的认识，所获颇丰。