MIT 6.S081入门lab7 多线程
一、参考资料阅读与总结
1.xv6 book书籍阅读（Chapter 7: Scheduling through Section 7.4)
1.概述：
由于操作系统往往运行比CPU数量更多的进程，因此需要对CPU进行虚拟化，使多个进程能够分时复用CPU资源
2.多路复用：
xv6中多路复用有2种方式：sleep和wakeup机制、轮转调度Round-Robin机制
虚拟化的核心：给进程以自己独占电脑资源的假象
- 核心问题：
- 如何安全的完成进程切换
- 切换需要透明+强制->时钟中断的轮转调度机制
- 考虑CPU的并发性->需要锁机制
- 进程资源的释放（注意内核相关资源的实现）
- 系统调用的解决->cpu需要了解当前执行进程是哪一个
- sleep和wake机制带来的wake loss的问题
2.代码：上下文切换
-
调度核心思想： 保存上下文，选择进程，恢复状态，执行进程
-
xv6的区别： xv6核心是针对内核线程进行调度，其调度核心是每个CPU的调度线程，内核态上下文是用户态的子集
-
核心函数 swtch(a0, a1)（kernel/swtch.S）： 实现对a0和a1内核的上下文的切换，其通过切换地址寄存器ra和栈寄存器sp实现了内核线程的切换；
注： swtch只保存被调用者保存的寄存器Callee-saved registers；由调用者保存的寄存器Caller-saved registers 由调用者保存在自己的内核栈上，具体寄存器可以查询lab4的risc-v寄存器章节：https://www.cnblogs.com/David-Dong/p/18035629； -
xv6调度的完整流程： 用户进程PA->usertrap->内核线程TA->yield(TA)->sched(TA)->swtch(TA, S)->调度线程S->swtch(S, TB)->sched(TB)->yield(TB)->内核线程TB->usertrapret->用户进程PB
kernel/swtch.S
# Context switch # # void swtch(struct context *old, struct context *new); # # Save current registers in old. Load from new. .globl swtch swtch: 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
3. 代码：调度线程
-
需要调度线程的原因： 由于在旧线程的内核栈上运行内核栈时，会导致多CPU调度冲突，因此，CPU只能在自己的调度线程内核栈上运行调度器；
-
调度流程： 陷入trap后，which_dev = 2,usertrap调用yield函数开始调用
-
yield: 获得进程锁，修改状态，调用sched();
yield kernel/proc.c:521
// Give up the CPU for one scheduling round. void yield(void) { struct proc *p = myproc(); acquire(&p->lock); p->state = RUNNABLE; sched(); release(&p->lock); } -
sched: 检查p->lock和其他的锁（通过检查中断嵌套层数），检查进程状态+中断状态， 调取mycpu，使用swtch切换进入cpu线程(调度线程)
sched kernel/proc.c:494
// Switch to scheduler. Must hold only p->lock // and have changed proc->state. Saves and restores // intena because intena is a property of this // kernel thread, not this CPU. It should // be proc->intena and proc->noff, but that would // break in the few places where a lock is held but // there's no process. void sched(void) { int intena; struct proc *p = myproc(); if(!holding(&p->lock)) panic("sched p->lock"); if(mycpu()->noff != 1) panic("sched locks"); if(p->state == RUNNING) panic("sched running"); if(intr_get()) panic("sched interruptible"); intena = mycpu()->intena; swtch(&p->context, &mycpu()->context); mycpu()->intena = intena; } -
scheduler： 使用循环寻找下一个需要执行的内核线程，并设定状态和运行空间，同时使用swtch切换回到内核线程的sched
scheduler kernel/proc.c
/ Per-CPU process scheduler. // Each CPU calls scheduler() after setting itself up. // Scheduler never returns. It loops, doing: // - choose a process to run. // - swtch to start running that process. // - eventually that process transfers control // via swtch back to the scheduler. void scheduler(void) { struct proc *p; struct cpu *c = mycpu(); c->proc = 0; for(;;){ // Avoid deadlock by ensuring that devices can interrupt. intr_on(); int nproc = 0; for(p = proc; p < &proc[NPROC]; p++) { acquire(&p->lock); if(p->state != UNUSED) { nproc++; } if(p->state == RUNNABLE) { // Switch to chosen process. It is the process's job // to release its lock and then reacquire it // before jumping back to us. p->state = RUNNING; c->proc = p; swtch(&c->context, &p->context); // Process is done running for now. // It should have changed its p->state before coming back. c->proc = 0; } release(&p->lock); } if(nproc <= 2) { // only init and sh exist intr_on(); asm volatile("wfi"); } } }
-
-
核心： sched和scheduler表现为一对协同程序，通过不同内核线程的sched和scheduler通过swtch切换实现
-
例外： 进程创建时，在allocproc中将ra设置为forkret，调度通过forkret直接返回到用户空间中、
allocproc kernel/proc.c
// Look in the process table for an UNUSED proc. // If found, initialize state required to run in the kernel, // and return with p->lock held. // If there are no free procs, or a memory allocation fails, return 0. static struct proc* allocproc(void) { struct proc *p; for(p = proc; p < &proc[NPROC]; p++) { acquire(&p->lock); if(p->state == UNUSED) { goto found; } else { release(&p->lock); } } return 0; found: p->pid = allocpid(); // Allocate a trapframe page. if((p->trapframe = (struct trapframe *)kalloc()) == 0){ release(&p->lock); return 0; } // An empty user page table. p->pagetable = proc_pagetable(p); if(p->pagetable == 0){ freeproc(p); release(&p->lock); return 0; } // Set up new context to start executing at forkret, // which returns to user space. memset(&p->context, 0, sizeof(p->context)); p->context.ra = (uint64)forkret; //调用forkret p->context.sp = p->kstack + PGSIZE; return p; }forkret kernel/proc.c
// A fork child's very first scheduling by scheduler() // will swtch to forkret. void forkret(void) { static int first = 1; // Still holding p->lock from scheduler. release(&myproc()->lock); if (first) { // File system initialization must be run in the context of a // regular process (e.g., because it calls sleep), and thus cannot // be run from main(). first = 0; fsinit(ROOTDEV); } usertrapret();//直接返回用户空间 } -
p->lock的保护： 在调度过程完成之前，保持该内核栈不被其他CPU运行
- 改变进程状态为RUNNABLE，防止进程状态的不一致。
- swtch发生的上下文切换，防止保存和恢复寄存器不完整。
- 停止使用当前内核线程的内核栈，因此防止两个CPU使用同一个内核栈。
- 其他：exit和wait之间的交互，避免唤醒丢失，进程在exit时产生的竞争条件等。
4.代码 Mycpu 和 Myproc
- 多cpu维护当前cpu运行进程的解决方案： 使用每个cpu的寄存器集合；
-
struct cpu结构保存了进程结构、调度上下文、中断信息；
struct cpu kernel/proc.h
// Per-CPU state. struct cpu { struct proc *proc; // The process running on this cpu, or null. struct context context; // swtch() here to enter scheduler(). int noff; // Depth of push_off() nesting. int intena; // Were interrupts enabled before push_off()? }; extern struct cpu cpus[NCPU]; -
mycpus实现了使用hartid查找当前cpu的信息
r_tp kernel/risc.h
// read and write tp, the thread pointer, which holds // this core's hartid (core number), the index into cpus[]. static inline uint64 r_tp() { uint64 x; asm volatile("mv %0, tp" : "=r" (x) ); return x; }mycpu，cpuid kernel/proc.c
// Must be called with interrupts disabled, // to prevent race with process being moved // to a different CPU. int cpuid() { int id = r_tp(); return id; } // Return this CPU's cpu struct. // Interrupts must be disabled. struct cpu* mycpu(void) { int id = cpuid(); struct cpu *c = &cpus[id]; return c; } -
tp寄存器设置：机器模式设置，并将其保存在trapframe进行恢复
-
myproc读取当前cpu运行的进程并返回
myproc kernel/myproc
// Return the current struct proc *, or zero if none. struct proc* myproc(void) { push_off(); struct cpu *c = mycpu(); struct proc *p = c->proc; pop_off(); return p; }
-
二、涉及函数（kernel/proc.c, kernel/swtch.S）
核心代码已经讨论过了，这里不再赘述
三、课程视频观看笔记（lec 11）
- 线程切换： 需求：多任务处理+线程加速
- 线程： 一种串行执行方式；
- 重要状态：PC、寄存器、堆栈；
- 需求：交错执行；线程切换。
- 如果共享内存时，需要锁
-xv6中，每一个用户进程有着相对应的内核线程（syscall的调度），同时用户进程只有一个线程 - 多任务的其他解决方式：状态机、事件驱动编程。
- 线程的挑战： 进程的切换+调度+保存和恢复+计算密集型线程的处理
- 处理方案：
- 定时器中断划分时间->内核获取控制权->内核调度（用户态抢占型调度，内核态自愿性调度）
- 进程状态：运行、可运行、睡眠
- 需要保存的数据：CPU运行状态：PC+寄存器；
- 用户态进程调度的核心： 内核线程的切换，即内核栈的切换；
- 每个内核CPU都有自己的堆栈,在entry.S中初始化
- 注意： 每个核心同时只在一个运行单一线程
- swtch调换机制： swtch通过ra和sp进行调换，同时，可以通过sp和ra判断当前程序，如果在非常前的地址，则是在cpu的初始化栈中。
- p->lock 的机制： 在yield中上锁，scheduler中释放/在scheduler上锁， yield中释放，保证启动和切换一个进程的过程是原子的。
- 进程切换的核心代码：swtch，保存易失性存储，即cpu的相应寄存器，到内存（非易失存储）
- linux线程：核心是共享内存的进程；
四、完成lab及其代码
-
Uthread: switching between threads
构建相应结构体，同时根据要求调用函数并初始化相应寄存器（ra和sp）user/uthread
... // Saved registers for user 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 thread { char stack[STACK_SIZE]; /* the thread's stack */ int state; /* FREE, RUNNING, RUNNABLE */ struct context context; /*context struct to save callee reg*/ }; ... void thread_schedule(void) { /* YOUR CODE HERE * Invoke thread_switch to switch from t to next_thread: * thread_switch(??, ??); */ thread_switch((uint64)&(t->context), (uint64)&(next_thread->context)); //调用switch函数切换栈和ra，并保存callee寄存器 } else next_thread = 0; } ... void thread_create(void (*func)()) { t->state = RUNNABLE; // YOUR CODE HERE t->context.ra = (uint64)func; //return to the func addr t->context.sp = (uint64)((char *)&t->stack + (STACK_SIZE - 1)); //保存栈信息（从高往低生长） }实现calle寄存器的入栈切换操作，参考内核中的switch
user/uthread_switch.S
.text /* * save the old thread's registers, * restore the new thread's registers. */ // void thread_switch(struct context *old, struct context *new); .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 */修改Makefile，添加文件编译
Markfile
UPROGS=\ ... $U/_uthread\ -
Using threads
核心是加锁+每个散列桶分开加锁（较细粒度锁）ph.c
... int nthread = 1; pthread_mutex_t lock[NBUCKET];//互斥锁结构 ... static void put(int key, int value) { int i = key % NBUCKET; pthread_mutex_lock(&lock[i]); //加锁 ... pthread_mutex_unlock(&lock[i]); //解锁 } static struct entry* get(int key) { int i = key % NBUCKET; pthread_mutex_lock(&lock[i]);//加锁 ... pthread_mutex_unlock(&lock[i]);//解锁 return e; } ... int main(int argc, char *argv[]) { ... for (int i = 0; i < NKEYS; i++) { keys[i] = random(); } for (int i = 0; i < NBUCKET; i++) { pthread_mutex_init(&lock[i], NULL); //初始化锁 } // // first the puts // } -
Barrier
核心是设置合适的barrier，即使用给定结构体中的nthread统计到达barrier的线程数量，之后根据是否达到线程数量进行睡眠/清空nthread计数+增加round计数+唤醒。注意在访问barrier时候需要是原子的，因为可能会出现barrier被多个线程同时访问，导致nthread计数混乱的情况barrier.c
static void barrier() { // YOUR CODE HERE //if thread enter the barrier , add nthread and check if nthread == nthread wake and round++else sleep pthread_mutex_lock(&bstate.barrier_mutex); 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); // Block until all threads have called barrier() and // then increment bstate.round. // }
参考文献
2020版xv6手册：http://xv6.dgs.zone/tranlate_books/book-riscv-rev1/c6/s0.html
xv6手册与代码笔记：https://zhuanlan.zhihu.com/p/353580321
xv6手册中文版：http://xv6.dgs.zone/tranlate_books/book-riscv-rev1/c4/s6.html
28天速通MIT 6.S081操作系统公开课：https://zhuanlan.zhihu.com/p/629202642
MIT6.s081操作系统笔记：https://juejin.cn/post/7016228101717753886
gdb使用手册：https://sourceware.org/gdb/current/onlinedocs/gdb.html/
维基百科：Barrier (computer science)：https://en.wikipedia.org/wiki/Barrier_(computer_science)