首先切换到thread分支
git checkout thread
make clean
Uthread:switch between threads
为用户级线程系统设计上下文切换机制
xv6中已经放了两个文件:
-
user/uthread.c和user/uthread_switch.S
-
以及一个规则:运行在Makefile中以构建
uthread
程序。 -
uthread.c包含大多数用户级线程包,以及三个简单测试线程的代码。
实现用户级线程切换,比起xv6中实现内核级线程,这个更简单一些,因为用户级线程不需要设计用户栈和内核栈,用户页表和内核页表切换等等
1.定义存储上下文的结构体tcontext(kernel/proc.h)同时修改uthread.c(user/uthread.c)中的thread结构体
2.类似按照kernel/swtch.S,修改user/uthread_switch.S中写入如下代码
3.更改thread_scheduler(user/uthread.c),进行线程的轮询并找到下一个需要执行的切换
其中thread_yield函数是默认提供好的
Using threads
在文件notxv6/ph.c中包含一个简单的哈希表,如果单个线程使用,该哈希表是正确,但是多个线程使用时,该哈希表不正确,可以在主目录中输入如下命令:
make ph
./ph 1
结果如下:
ph的参数指定在哈希表上执行put和get的线程数,可以看到没有missing,100000 puts 也对应 10000 gets
但是当使用多个线程的时候,例如2,结果如下:
$ ./ph 2
100000 puts, 4.385 seconds, 23044 puts/second
1: 16579 keys missing
0: 16579 keys missing
200000 gets, 8.422 seconds, 23597 gets/second
可以看到丢失了不少,但数字确实貌似是二倍的样子,pu运行两个基准程序,通过put()将许多键添加到哈希表,并以秒为单位打印puts的速率,然后它使用get()从哈希表中获取键,打印由于puts而应该在哈希表中单丢失的键的数量。然而,16579 keys missing的两行代表丢失了大量的键
所以这里需要使用多进程必须进行上锁
设定了五个散列桶,根据键除以5的余数来确定插入到哪个散列桶中,插入的方式是头插法
造成数据丢失原因:
-
假设现在有两个线程T1和T2,两个线程都走到put函数,且假设两个线程中 key%NBUCKET相同
-
两个线程同时调用
insert(key, value, &table[i], table[i])
,第一个参数是传需要插入的内存地址,第二个参数是需要插入的某块内存(插入到该内存之前)insert是通过头插法实现的。如果先insert的线程还未返回另一个线程就开始insert,那么前面的数据会被覆盖
1.在notxv6/ph.c为每个散列桶定义一个锁,将五个锁放在一个数组中,并进行初始化
2.在put函数中对insert函数上锁(get不需要,因为不会修改只是读)
加锁后测试:
Barrier
实现一个内存屏障(Barrier):
应用程序中的某个点,所有参与的线程都必须在此点上等待,知道其他所有参与的线程也到达该点
在notxv6/barrier.c中包含一个残缺的屏障实现
$ make barrier
$ ./barrier 2
barrier: notxv6/barrier.c:42: thread: Assertion `i == t' failed.
2 指明了在屏障上同步的线程数,每个线程执行一个循环,每次循环迭代中,线程都会调用barrier(),然后以随机微秒数休眠,如果一个线程在另一个线程到达屏障之前离开屏障将触发断言。希望达到的效果是每个线程在barrier()中阻塞,直到nthreads的所有线程都调用了barrier()
看一下notxv6/barrier.c中的代码逻辑(已经完成了barrier函数的实现)
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>
#include <pthread.h>static int nthread = 1;
static int round = 0;// 互斥锁,条件变量,到达屏障的线程数、轮数
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;//初始化屏障
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;
}//屏障函数,已经实现
static void
barrier()
{// YOUR CODE HERE//// Block until all threads have called barrier() and// then increment bstate.round.////申请锁,互斥操作pthread_mutex_lock(&bstate.barrier_mutex);// judge whether all threads reach the barrierif(++bstate.nthread != nthread) { // not all threads reach pthread_cond_wait(&bstate.barrier_cond,&bstate.barrier_mutex); // wait other threads} else { // all threads reachbstate.nthread = 0; // reset nthread++bstate.round; // increase roundpthread_cond_broadcast(&bstate.barrier_cond); // wake up all sleeping threads}pthread_mutex_unlock(&bstate.barrier_mutex);}//每个线程执行的函数
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;
}int
main(int argc, char *argv[])
{pthread_t *tha;void *value;long i;double t1, t0;if (argc < 2) {fprintf(stderr, "%s: %s nthread\n", argv[0], argv[0]);exit(-1);}//参数指定线程数量nthread = atoi(argv[1]);tha = malloc(sizeof(pthread_t) * nthread);// srandom 是 C 标准库中的一个函数,用于设置伪随机数生成器(PRNG)的起始种子 -- 输出只是伪随机而不是真正的随机数srandom(0);barrier_init();//创建n个线程执行for(i = 0; i < nthread; i++) {assert(pthread_create(&tha[i], NULL, thread, (void *) i) == 0);}for(i = 0; i < nthread; i++) {assert(pthread_join(tha[i], &value) == 0);}printf("OK; passed\n");
}