关于c:MIT-6181068286S081-操作系统工程-Lab6-Multithreading

Uthread: switching between threads (moderate)

要求

在本练习中，您将为用户级线程零碎设计上下文切换机制，而后实现它。为了帮忙您入门，您的 xv6 有两个文件 user/uthread.c 和 user/uthread_switch.S，以及 Makefile 中用于构建 uthread 程序的规定。uthread.c 蕴含大部分用户级线程包，以及三个简略测试线程的代码。线程包短少一些用于创立线程和在线程之间切换的代码。

您的工作是制订一个打算来创立线程并保留 / 复原寄存器以在线程之间切换，并实现。

当你实现后，在 xv6 上运行 uthread 将看到下列输入（三个测试秩序不确定）：

$ uthread
thread_a started
thread_b started
thread_c started
thread_c 0
thread_a 0
thread_b 0
thread_c 1
thread_a 1
thread_b 1
...
thread_c 99
thread_a 99
thread_b 99
thread_c: exit after 100
thread_a: exit after 100
thread_b: exit after 100
thread_schedule: no runnable threads
$

此输入来自三个测试线程，每个测试线程都有一个循环，该循环打印一行，而后将 CPU 提供给其余线程。

然而，此时，如果没有上下文切换代码，则不会看到任何输入。

• 你将须要在 user/uthread.c 中的 thread_create()、thread_schedule() 以及 user/uthread_switch.S 中的 thread_switch 中增加代码。
• 一个指标是确保当 thread_schedule() 首次运行给定线程时，线程在其本人的堆栈上执行传递给 thread_create() 的函数。
• 另一个指标是确保 thread_switch 保留被切换的线程的寄存器，复原正在切换到的线程的寄存器，并返回到后一个线程指令中上次中断的地位。
• 您必须决定在何处保留 / 复原寄存器；批改 struct thread 以保留寄存器是一个很好的打算。
• 您须要在 thread_schedule 中增加对 thread_switch 的调用; 您能够传递您须要的任何参数到 thread_switch 中，但目标是从线程 t 切换到next_thread。

提醒

• thread_switch只须要保留 / 复原被调用方保留寄存器。为什么？
• 您能够在 user/uthread.asm 中看到 uthread 的汇编代码，这对于调试可能很不便。
• 对于 gdb 调试

实现

1. 线程实现的思路：依据提醒、参考内核中过程的切换，可确定思路：

   • 线程状态与上下文：创立一个构造体记录线程本人的上下文和状态。在一个全局的该构造体数组中保护所有线程
   • 线程调度：在全局数组中寻找下一个可运行的线程，而后进行线程的切换操作
   • 线程切换：取出上一个线程寄存器中的值（状态）保留，将要执行的线程上一次保留的状态放入寄存器

   • 线程创立（线程初始化）：须要让线程执行传入的函数指针所指的函数、并实现线程堆栈初始化

     1. 通过 ra 寄存器实现线程的命令初始化：ra 寄存器示意函数返回地址，因而可用此寄存器保留要执行的函数地址，在 thread_switch 后将会返回 thread_schedule() 函数，若将 ra 更改为传入函数地址，则程序也会跳到传入函数的地址去执行命令
     2. 堆栈初始化：每个线程都该当有本人独立的堆栈，线程运行时通过寄存器 sp 来读写堆栈。寄存器 sp 保留指向堆栈顶部的指针，但线程的堆栈增长方向是从下向上增长的（即从大内存编号向向内存编号增长），因而 sp 中的指针该当指向 struct thread 中堆栈数组的最初一个元素。

2. 线程状态和上下文 ：创立构造体struct context 保留线程上下文，并在线程构造体中退出该字段

   struct context {
       uint64 ra;  // return address
       uint64 sp;  // stack pointer
   
       // 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;
   };

3. 线程初始化 ：在thread_create() 中实现线程初始化：①将函数地址放入保留函数返回地址的 ra 寄存器；②将堆栈数组最初一个元素的指针放入保留堆栈顶指针的 sp 寄存器

   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
       t->context.ra = (uint64)func;
       t->context.sp = (uint64)(t->stack + STACK_SIZE - 1);
   }

4. 线程调度 ：源码已给出调度的形式，这里只须要在指定地位调用thread_switch 即可。然而传入的参数须要本人确定，这里传入了切换前后两个线程保留上下文构造体的地址。（下一点阐明）

   void thread_schedule(void) {
       ...
       if (current_thread != next_thread) {  // 须要切换线程的状况
           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);
       }
       ...
   }

5. 线程切换：首先能够确定这一步操作能够分为两小步：①保留上一个线程上下文；②将下一个构造体上次保留的上下文顺次放入寄存器。参考内核中用于切换过程的switch.S，可失去如下机器码。不难发现它通过传入参数寄存器 a0 中的地址，来把不同寄存器放入 a0 地址从 0 到 104 的偏移后地址来保留上下文，因而传入参数该当是指向上下文构造体的指针；复原下一个线程的办法同理。

   thread_switch:
       /* YOUR CODE HERE */
       // 先把寄存器内容保留到上一个 thread 的 context 中
       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)
       // 再把寄存器内容换成下一个 thread 的 context
       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 */

遇到的问题

无奈切换到 c 之外的线程

• 依据调试实践，failure 如下图所示
• Error：通过 gdb 调试我找到了第一个观测到的 error 状态：在每个线程中只有一 printf，该线程前边的线程的状态就会被扭转成奇怪的数字。因而在thread_schedule() 中无奈找到下一个状态是 RUNNABLE 的线程，也就无奈切换到 c 之外的其余线程。
• Bug：这部分还是很难在 Bug-Error 之间建立联系。想了半天忽然想起那句“堆栈的增长方向是向上”，即堆栈增长方向与常识不太一样，是从内存编号大往小的中央增长。于是在初始化时尝试扭转堆栈指针，果然修复了 bug。

后果

• 运行后果
• 测试后果

Using threads (moderate)

要求

在本作业中，您将摸索应用哈希表的线程和锁的并行编程。您应该在具备多个内核的实在 Linux 或 MacOS 计算机（不是 xv6，不是 qemu）上执行此调配。最新的笔记本电脑都有多核处理器。

文件 notxv6/ph.c 蕴含一个简略的哈希表，如果从单个线程应用，则正确，但在从多个线程应用时不正确。在您的主 xv6 目录中, 键入此内容

$ make ph
$ ./ph 1

请留神，要构建 ph，Makefile 应用操作系统的 gcc，而不是 6.S081 工具。ph 参数指定对哈希表执行搁置和获取操作的线程数。运行一段时间后，ph 1 将产生相似于以下内容的输入：

100000 puts, 3.991 seconds, 25056 puts/second
0: 0 keys missing
100000 gets, 3.981 seconds, 25118 gets/second

您看到的数字可能与此示例输入相差两倍或更多，具体取决于您的计算机的速度、它是否具备多个内核以及它是否忙于执行其余操作。

ph运行两个基准。首先，它通过调用 put() 向哈希表增加大量键，并以每秒 put 的数量为单位打印实现的速率。而后它应用 get() 从哈希表中获取 key。它打印因为 put 而应该在哈希表中但却没有的键的数量（在本例中为零），并打印每秒 get 的数。

你能够通知 ph 同时应用来自多个线程的哈希表，办法是给它一个大于 1 的参数。尝试 ph 2：

$ ./ph 2
100000 puts, 1.885 seconds, 53044 puts/second
1: 16579 keys missing
0: 16579 keys missing
200000 gets, 4.322 seconds, 46274 gets/second

输入的第一行批示当两个线程同时向哈希表增加条目时，它们的总速率为每秒 53,044 次插入。这大概是运行 ph 1 的单线程速率的两倍。这是一个杰出的“并行减速”，大概是人们所心愿的 2 倍（即两倍的内核，每单位工夫产生两倍的工作量）。
然而，短少 16579 键的两行示意哈希表中有大量键该当存在但理论却不存在。也就是说，put应该将这些键增加到哈希表中，但出了点问题。看看 notxv6/ph.c 尤其是 put() 和insert().

问题：为何 2 个线程会产生 missing 一个线程就不会？Identify 可能导致 key 失落的两个线程的时序图。

要防止这一系列事件，请在 put 和 get 中插入 lock 和 unlock 语句 notxv6/ph.c，以便短少的键数始终为 0，并且有两个线程。当 make grade 示意您的代码通过 ph_safe 测试时，您就实现了，这须要两个线程的零缺失键。此时，无奈通过 ph_fast 测试是失常的。

不要遗记调用 pthread_mutex_init()。首先应用 1 个线程测试代码，而后应用 2 个线程进行测试。它是否正确（即您是否打消了失落的键？）绝对于单线程版本，双线程版本是否实现了并行减速（即每单位工夫的总工作量更多）？
在某些状况下，并发 put() 在它们在哈希表中读取或写入的内存中没有重叠，因而不须要锁来互相爱护。您是否更改 ph.c 以利用这种状况来取得某些 put() 的并行减速？提醒：思考每个哈希桶的锁

批改代码，以便某些 put 操作并行运行，同时放弃正确性。当 make grade 说你的代码通过了 ph_safe 和ph_fast测试时，你就实现了。ph_fast测试要求两个线程每秒的 put 数量至多是一个线程的 1.25 倍。

实现

1. 依据提醒，可为哈希表的每个桶创立一个锁，因为不同桶中的键值对存取不存在并发抵触。因而在 ph.c 结尾的定义全局数组：

   struct entry {...};
   struct entry* table[NBUCKET];
   pthread_mutex_t locks[NBUCKET];
   ...

2. 在 main() 中，在创立线程前增加锁的初始化：

   int main() {
       ...
       // init locks
       for (int i = 0; i < NBUCKET; ++i) {pthread_mutex_init(locks + i, 0);
       }
       // 创立线程......
   }

3. 为波及临界区内存读写的 put 和get增加互斥锁：

   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);  // lock!
       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);  // unlock!
   }
   
   static struct entry* get(int key) {
       int i = key % NBUCKET;
       struct entry* e = 0;
       pthread_mutex_lock(locks + i);  // lock!
       for (e = table[i]; e != 0; e = e->next) {if (e->key == key) break;
       }
       pthread_mutex_unlock(locks + i);  // unlock!
       return e;
   }

后果

• 运行后果
• 测试后果
• 留神：如果没有依照提醒，只用一把互斥锁的话，速度会大大减小导致无奈通过ph_fast。

  起因就是，分桶的锁能够使不同的桶的存取操作仍然放弃并发，而一把锁则使得所有的存取操作都必须非并发。

Barrier(moderate)

要求

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

您应该在实在计算机上（不是 xv6，不是 qemu）上执行此操作。

文件 notxv6/barrier.c 蕴含一个不残缺的屏障。

$ make barrier
$ ./barrier 2
barrier: notxv6/barrier.c:42: thread: Assertion `i == t' failed.

参数 2 指定在屏障上同步的线程数（barrier.c 中的 nthread）。每个线程执行一个循环。在每次循环迭代中，线程调用 barrier()，而后休眠随机微秒。断言触发是因为一个线程在另一个线程达到屏障之前来到屏障。冀望的行为是每个线程在 barrier() 中阻塞，直到它们的所有 nthreads 个线程都调用了 barrier。

您的指标是实现所需的屏障行为。除了您在 ph 工作中看到的互斥锁原语之外，您还须要以下新的 pthread 原语。

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

pthread_cond_wait调用时开释互斥锁，并在返回之前从新获取互斥锁。

咱们曾经给了你barrier_init。你的工作是实现 barrier()，这样就不会产生 panic。咱们曾经为您定义了struct barrier; 其字段供您应用。

有两个问题使您的工作复杂化：

• 你必须解决一连串 barrier 的调用，每一波咱们称之为一轮。bstate.round记录以后轮次。每次所有线程都达到阻碍时，都应递增 bstate.round。
• 您必须解决一个线程在其余线程退出阻碍之前绕循环运行的状况。尤其是，您正在从一轮到下一轮重用 bstate.nthread 变量。确保来到阻碍并围绕循环运行的线程在上一轮仍在应用它时不会减少 bstate.nthread。

应用一个、两个和两个以上的线程测试代码。

实现

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);
}

后果

• 运行后果
• 测试后果

总结

make grade

集体播种

1. 实际上线程的实现与过程十分相似，基本思路可总结为保留 / 复原上下文、线程创立、线程调度、线程切换四个根本局部。（如前所述）

2. 互斥锁和条件变量的应用有 API，绝对简略。但原理很重要：

   • 自旋锁：若能获取🔒就执行；若不能就始终循环直到获取锁。占用 CPU
   • 互斥锁：切换到内核态，若能获取🔒就返回用户态执行；若不能获取锁就休眠。
   • pthread 中的 mutex：开始是自旋锁，若能获取🔒就执行；若不能获取，循环一段时间后还不行就切换到内核使该线程睡眠

3. 条件变量原理：在获取锁的状况下判断是否符合条件

   • 若符合条件则持续向下执行，出临界区要开释锁；
   • 若不符合条件，则开释锁而后进入睡眠，期待唤醒；醒来后再次获取锁，持续判断是否符合条件 …
   • 可通过播送 or 随机告诉一个线程的形式唤醒因不合乎某条件睡眠的应用同一条件变量的线程