• 2020 MIT6.s081 Lab: Multithreading

    文章目录

    Lec11: Thread Switching学习笔记

    1. 在RISC-V中，每个CPU都有一个hartid，且这个hartid保存在每个CPU的tp寄存器里。
      1. 在CPU的boot时，会将hartid保存至tp寄存器中；
      2. 在从内核态进入用户态时，在usertrapret函数中，会将hartid（也就是tp寄存器中的值）保存至trampoline page；
      3. 在从用户态进入内核态时，也就是在uservec中（文件trampoline.S），会restore寄存器tp的值；
    2. 线程共享内存问题：
      1. xv6的内核有多个内核线程，每个内核线程对应用户态的一个进程；
      2. xv6内核的线程共享内核内存；
      3. xv6的用户进程之间不会共享内存，且每个用户进程只有一个线程；
      4. 在linux中，用户进程之间不会共享内存，且每个用户进程可拥有多个线程，线程之间共享内存。（Linux比xv6更加复杂，但是我们这里重点理解工作原理）
      5. 还有一些系统不使用线程也能同时运行多个程序，感兴趣的可以搜索state-machine和event-driven programming。
    3. 线程调度：
      1. xv6为每个CPU都创建了一个线程调度器；
      2. 定时器中断，会将程序的控制权从用户空间转换至内核空间，因为中断处理程序的优先级更高；
      3. 中断处理的基本流程：定时器中断将CPU控制权从用户态转交为内核态，内核态再将控制权交给内核的线程调度器；
    4. 寄存器保存
      1. 用户寄存器保存在trapframe中；即trapframe保存的是用户进入和离开内核时的数据；
      2. 内核线程的寄存器保存在contex中；（通过函数swtch进行保存和交换，详细代码位于swtch.S中）；即contex保存的是内核线程和线程调度器切换时的数据。
    5. 调度器线程
      1. 每个CPU都有一个内核调度器线程，它有自己的contex对象，用于保存自己的寄存器；
      2. 当一个CPU上的内核线程进行切换时，首先old的内核线程会切换至内核调度器线程，之后再由内核调度器切换至new的内核线程；
      3. 每个线程调度器都有一个独立的栈；
      4. 线程调度器的栈和contex，是在启动时就设置好了
    6. contex对象保存位置：
      1. 内核线程分为两类：普通的内核线程和内核调度器线程；
      2. 普通的内核线程的contex，保存在与其对应的用户进程proc的字段contex中（也就是struct proc的contex字段）；
      3. 内核调度器的线程，保存在与其对应的CPU结构体的contex字段中（也就是struct cpu的contex字段）；
    7. CPU的工作：
      1. 一个CPU在一个时间点只会做以下三件事情中的一件；
        1. 在运行内核线程；
        2. 在运行用户进程；
        3. 在运行线程调度器；
      2. 线程的切换造成了CPU可运行多个线程的假象；
      3. 一个线程要么运行在一个CPU上，要么其状态保存在contex中；
    8. switch

      1. 每次调用switch，代码都会进行跳转，当内核再次调用switch并切换时，会跳转回来。

        1. 如果是从内核线程跳转至调度器线程，则一般是跳转至scheduler函数内；

        2. 如果是从调度器线程跳转至内核线程，则一般是跳转至内核线程执行switch函数的下一条语句。

          在这里插入图片描述

      2. 内核第一次调用switch时，其中一个contex是伪造的，因为并不存在与之交换的contex。

    实验链接

    https://pdos.csail.mit.edu/6.S081/2020/labs/thread.html

    实验

    Lab: Multithreading

    该实验的主要目标是实现用户级的线程管理和切换。相关代码位于user/uthread.c文件中。该文件一共涉及4个线程，main线程，thread_a线程，thread_b线程，thread_c线程。需要注意的点是：

    1. 本质上还是单个CPU在分时执行多个线程；
    2. 栈是从大地址往小地址增长的，即栈底是大地址，栈顶是小地址，如果程序搞反了，可能会导致各个线程之间的数据产生错乱。

    具体实现如下：

    1. 文件user/uthread.c

      // 为每个线程设置contex，为了进行线程切换时保存寄存器的现场
struct thread {
  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
  struct context* context;
};

// 直接从内核的context拷贝过来
// Saved registers for context switches.
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 context all_context[MAX_THREAD];

      • 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

    2. 文件user/uthread.c

      void 
thread_init(void)
{
  // 增加初始化context的内容  
  for (int i = 0; i < MAX_THREAD; i++) {
    all_thread[i].context = &all_context[i];
  }
  current_thread = &all_thread[0];
  current_thread->state = RUNNING;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10

    3. 文件user/uthread.c

      void 
thread_schedule(void)
{
  struct thread *t, *next_thread;

  /* Find another runnable thread. */
  next_thread = 0;
  t = current_thread + 1;
  for(int i = 0; i < MAX_THREAD; i++){
    if(t >= all_thread + MAX_THREAD)
      t = all_thread;
    if(t->state == RUNNABLE) {
      next_thread = t;
      break;
    }
    t = t + 1;
  }

  if (next_thread == 0) {
    printf("thread_schedule: no runnable threads\n");
    exit(-1);
  }

  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(??, ??);
     */
      // +++++ begin +++++++
    thread_switch((uint64)(t->context), (uint64)(next_thread->context));
      // ------ end ----------
  } else
    next_thread = 0;
}

      • 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

    4. 文件user/uthread.c，更改thread_create函数

      void 
thread_create(void (*func)())
{
  struct thread *t;

  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == FREE) break;
  }
  t->state = RUNNABLE;
  // YOUR CODE HERE
  memset(t->stack, 0, sizeof(char) * MAX_THREAD);
  t->context->ra = (uint64)(*func);
  // 注意栈的方向，否则会导致数据错乱  
  t->context->sp = (uint64)(&(t->stack[STACK_SIZE - 1]));
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15

    5. 文件user/uthread_switch.S

      	.text

	/*
         * save the old thread's registers,
         * restore the new thread's registers.
         */

	.globl thread_switch
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
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43

    Lab: Using threads

    该实验比较简单，主要目的是为Hashtable加锁，为了加快速度，这里我们主要在桶级别进行加锁。代码如下：

    1. 文件ph.c，首先初始化锁

      struct entry {
  int key;
  int value;
  struct entry *next;
};
struct entry *table[NBUCKET];
// ++++ begin +++++++++
pthread_mutex_t locks[NBUCKET];
// ---- end ------------

// 增加函数初始化锁
void
initlock()
{
  for (int i = 0; i < NBUCKET; i++) {
    pthread_mutex_init(&locks[i], NULL);
  }
}

// 在main函数中初始化锁
int
main(int argc, char *argv[])
{
  assert(NKEYS % nthread == 0);
  for (int i = 0; i < NKEYS; i++) {
    keys[i] = random();
  }
  // +++++ begin ++++++  
  initlock();
  // ------ end -------  
  //
  // first the puts
  //
  t0 = now();
}


      • 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

    2. 桶级加锁

      static 
void put(int key, int value)
{
  int i = key % NBUCKET;

  // is the key already present?
  struct entry *e = 0;
  pthread_mutex_lock(&locks[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(&locks[i]); // +++++ 
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22

    3. 结果

      在这里插入图片描述

    4. 可以看到速度提升了，但是不到2倍。

    Barrier

    该题主要是练习pthread_cond的使用，设置barrier主要目标是为了同步线程。

    1. 文件user/barrier.c，更改函数barrier为如下内容

      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_broadcast(&bstate.barrier_cond);
    bstate.nthread = 0;
    bstate.round++;
  } else {
    // go to sleep on cond, releasing lock mutex, acquiring upon wake up
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  }

  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

    2. 执行结果

      在这里插入图片描述

    结果

    $ make grade

    • 1

    在这里插入图片描述

    提交结果

    $ git commit -m "lab multithreading"
$ make handin

    • 1
    • 2

    查看结果

    登录网站https://6828.scripts.mit.edu/2020/handin.py/student，可以看到提交的结果。

    在这里插入图片描述

    参考链接

    https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081

    https://pdos.csail.mit.edu/6.S081/2020/schedule.html

    Github

    源码： https://github.com/aerfalwl/mit-xv6-labs-2020

  • 相关阅读:
    浏览器的缓存机制 优点 缺点 协商缓存和强缓存 浏览器缓存过程 如何判断强缓存是否过期
    VR全景平台应该具备哪些功能，怎样选择VR全景平台
    反射&注释API
    一文搞定IDEA中SpringBoot项目环境的热部署
    Amazon MSK 基于 S3 的数据导出、导入、备份、还原、迁移方案
    “Python+”集成技术高光谱遥感数据处理与机器学习深度应用
    我的项目day02:前端全局样式和js配置，simpleui的使用，跨域问题，cors解决跨域问题，git的下载与安装，pycharm中配置git
    计算机网络408考研 2020
    数据分析基础之《jupyter notebook工具》
    CodeQL笔记之基础语法（二）
  • 原文地址：https://blog.csdn.net/u014110320/article/details/126246585