Mit6.828 Day31~32 HW9 Barriers

Mit6.828 Day31~32 HW9 Barriers

摘要: MIT6.828 HW9

0x01 写在前面

昨天刚整完Lab4 Part A,今天就先不冲Part B了,来做一个小的HW,这个HW是同Barriers(内存屏障)相关的。在开始进行HW前,我们先一起来阅读下Scheduling剩余的部分。

0x02 Remainder of Scheduling+相关源码阅读

以下是本人阅读过程中的一点笔记:

Sleep and wakeup

这里主要提到了序列协同或条件同步的sleep和wakeup机制。

由自旋锁的浪费资源到sleep和wakeup机制的提出到

sleep和wakeup解决资源浪费但因信号丢失导致的死锁问题再到

通过往sleep中传递锁解决该问题(这块还需要理一下

往下三节是源码阅读,找不太到源码了,先不看了,脑壳疼。

Real World

提了下现实世界中轮询机制的复杂性(加入了优先级后,可能出现的优先级倒转和护航问题)

提了下信号量机制

0x03 HW9: Barriers

内存屏障是应用程序中的一点,在这点上,所有的进程都需要等待直到剩余其他的进程到达了这个点,我们会在HW中使用条件变量来实现内存屏障。条件变量是一种类似于xv6中sleep和wakeup的序列协调技术。

首先,我们下载一下教案上给我们的barrier.c文件,而后编译运行得到一下结果:

根据教案的提示

这里的2指定的是同步在内存屏障前的线程的数量,每一个线程都停留在一个循环中,在每一个循环里,往复进行着一个线程调用barrier()然后sleep随机长度的毫秒。断言触发是由于一个线程在其他的线程到达屏障前离开了,我们预期的行为应该是所有的线程应该被屏蔽知道nthreads调用了barrier。

我们的任务是去实现预期的行为,为完成此项任务,我们需要一些新的线程原语。

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

wait函数释放mutex互斥量,并在返回前重新获得mutex。

我们接下来要做的就是实现barrier()函数从而上面的panic不会发生。我们需要解决两个问题:

1)我们需要解决barrier的重复调用问题,每次调用我们称之为round。在bstate.round中记录的当前的round,我们需要增加这个值在每个round开始的时候;

2)我们需要处理在所有其他的线程离开屏障前一个线程在循环中的round过程,确保一个线程退出屏障并且其循环不增加bstate.nthread的值。

我们先来读一遍barrier.c的源码:

1
2
3
4
5
6
7
8
9
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 barrier
int round; // Barrier round
} bstate;

开头nthread先初始化了线程数为1,而后是记录轮数的round;往下走是一个名为bstate的barrier结构体。

里面的nthread和round分别记录了到达了屏障的线程数量以及屏障的轮数,mutex为互斥锁,cond为线程间同步。

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
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()
{
bstate.round++;
}

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

而后的barrier_init()函数,首先初始化了线程锁,而后又初始化了线程间同步,再后初始化当前屏障中的线程数为0。

barrier()函数,每次调用bstate.round数增加。

thread()函数,用于模拟线程,内部调用barrier()

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
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(0);

barrier_init();

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

其实总结来讲,我们只需要保证每次循环执行了一次再进行下一次循环。在所有的线程都进行了本轮循环后round才加1并进入下一轮循环,我们实现的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void 
barrier()
{
pthread_mutex_lock(&bstate.barrier_mutex);
bstate.nthread++;
if(bstate.nthread == nthread){
bstate.round++;
bstate.nthread=0;
pthread_cond_broadcast(&bstate.barrier_cond);
}else{
pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
}
pthread_mutex_unlock(&bstate.barrier_mutex);
}

成功:

0x04 总结

本次homework主要是学习了内存屏障并自己通过互斥量实现了内存屏障,并在实现的过程中对pthread中的互斥锁有了一定的了解。以上。


评论