广西建设局网站首页,企业文化模板,微信小程序后端开发教程,w3c验证网站文章目录 Uthread: switching between threadstaskhints思路上下文的恢复和保存thread_createthread_schedule Using threads思路 Barrier Uthread: switching between threads
在这个练习中#xff0c;你将为一个用户级别线程系统设计上下文切换机制#xff0c;并实现它。 … 文章目录 Uthread: switching between threadstaskhints思路上下文的恢复和保存thread_createthread_schedule Using threads思路 Barrier Uthread: switching between threads
在这个练习中你将为一个用户级别线程系统设计上下文切换机制并实现它。
task
你的任务是提出一个计划并实现它
创造线程切换线程的时候保存和恢复寄存器
当你完成的时候make grade会显示你通过了uthreadtest
你将需要在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但是目标就是切换线程
hints
thread_switch只需要保存和恢复被调用函数保护寄存器你可以在user/uthread.asm中看到uthread的汇编代码
思路
代码非常少主要是要搞清楚整个流程。线程的切换主要就是通过一个ra寄存器记录切换后函数从哪开始执行通过一个sp寄存器记录切换之后栈的地址然后就是一些被调用者保护寄存器。 为什么只需要保存callee保护寄存器 因为switch函数就是一个普通的c函数在调用它的时候调用函数会将调用者保护寄存器压入栈中保存在它返回之后会从栈中恢复被调用者保护寄存器。在switch结束之后通过栈就可以恢复caller寄存器这也是为什么要保存和恢复sp指针。 而对于callee保护寄存器就是被调用的函数来保护的了。也就是说通过rasp以及callee保护寄存器我们就可以恢复到某个线程的某个函数执行之后的镜像缺一不可。 对于第一次被调度的进程就更无所谓了反正也不需要恢复什么caller和callee寄存器本质上只需要ra和sp即可但是为了统一写法操作一下callee寄存器也没问题 上下文的恢复和保存
而在我们的这个task中线程切换时也要用到上述功能因此需要模仿xv6构建一个context的结构体并将其加入到thread的定义中
struct context {uint64 ra;uint64 sp;// callee-saveduint64 s0;uint64 s1;uint64 s2;uint64 s3;uint64 s4;uint64 s5;uint64 s6;uint64 s7;uint64 s8;uint64 s9;uint64 s10;uint64 s11;
};然后修改uthread_switch的定义为extern void thread_switch(struct context *, struct context *);并将上下文保存和恢复的汇编加入对应的汇编文件 .text/** save the old threads registers,* restore the new threads 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 */thread_create
在这里我们需要设置ra和sp寄存器分别指向函数的入口地址和栈的初始地址。其中栈的地址应该定位在栈的最高地址因为它向下增长 // YOUR CODE HEREt-ctx.ra (uint64)func;t-ctx.sp (uint64)t-stack STACK_SIZE - 1;thread_schedule
最后在这个函数中加入一行即可 /* YOUR CODE HERE* Invoke thread_switch to switch from t to next_thread:* thread_switch(??, ??);*/thread_switch(t-ctx, current_thread-ctx);这个task自己要写的代码非常少但是uthread.c整个文件可以说包含了上下文切换最关键的部分了很值得学习。
并且原来在用户态也可以在c代码里面嵌入汇编代码神奇。
Using threads
首先为了避免插入时出错你需要在put和get中使用锁如果能够在make grade中通过ph_safe就说明成功
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然后你应该优化你的代码使得你能通过ph_fast的测试你可以在每个桶上添加一个锁。两个线程至少要达到1.25倍的速度
思路
直接一步到位了给每个bucker设置一个锁并在main函数中对锁初始化
pthread_mutex_t locks[NBUCKET];void init_lock() {for (int i 0; i NBUCKET; i) {pthread_mutex_init(locks[i], NULL);}
}然后构造两个宏省的后面输入一大串
#define LOCK(i) (pthread_mutex_lock(locks[i]));
#define UNLOCK(i) (pthread_mutex_unlock(locks[i]));最后在put和get的起始和末尾都加上一个LOCK(i)和UNLOC(i) Barrier
这部分的实验文档看得我迷迷糊糊的还是看了半天源代码才看懂是啥意思。
关键就是下面这个函数我们每一次for循环bstate.round都应该和循环轮数相同。再结合实验文档可以知道就是要求我们通过barrier实现所有线程都在同一次for循环里不能有人提前进入下一轮因为这样的话这个assert肯定就要错了。
static void *
thread(void *xa) {long n (long)xa;long delay;int i;for (i 0; i 20000; i) {int t bstate.round;assert(i t);barrier();usleep(random() % 100);}return 0;
}然后就是这个结构体它是关键。其中round代表的就是现在for循环的轮数而nthread代表的是目前已经有多少个线程到达了屏障正在阻塞等待然后上面就是两个锁一个是常规的互斥锁一个是条件变量
struct barrier {pthread_mutex_t barrier_mutex;pthread_cond_t barrier_cond;int nthread; // Number of threads that have reached this round of the barrierint round; // Barrier round
} bstate;条件变量的使用也很有意思。第一个wait操作要求这个线程必须持有锁然后调用wait之后这个线程会释放这个锁然后进入阻塞睡眠。第二个广播操作会将通过cond阻塞的所有线程都唤醒。
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上面两个锁的组合就可以构建barrier函数。有一些宏定义方便使用。
首先每个进入barrier的线程都应该将现在进入barrier的线程数量加1。而为了防止并发带来的问题1的过程肯定是要用锁的我们这里正好就是用了barrier_mutex。
然后我们需要判断目前的数量是否已经达到了线程总数nthread
如果没达到那就通过条件变量让它睡觉去吧如果达到了那么我们需要将所有因此阻塞的进程都唤醒 但是在唤醒之前我们需要先将bstate的round和nthread变量给更新了如果我们是在唤醒之后更新那么可能cpu瞬间就被别人抢去了然后那些人就进入了下一轮for循环直接assert失败。
还有一种很恶心的并发问题就是如果我们很早就UNLOCK了那么有可能某个线程还没有wait就有一个线程调用了广播那么后果就是这个线程永远不会被唤醒。不过在我们这里是不会出现这种情况的。
#define LOCK() (pthread_mutex_lock(bstate.barrier_mutex))
#define UNLOCK() (pthread_mutex_unlock(bstate.barrier_mutex))
#define WAIT() (pthread_cond_wait(bstate.barrier_cond, bstate.barrier_mutex))
#define BROADCAST() (pthread_cond_broadcast(bstate.barrier_cond))
static void
barrier() {// YOUR CODE HERE//// Block until all threads have called barrier() and// then increment bstate.round.//LOCK();bstate.nthread 1;if (bstate.nthread nthread) {WAIT();} else {bstate.round 1;bstate.nthread 0;BROADCAST();}UNLOCK();
}
