Mit6.828 Day23 HW6 multithreaded programing

Mit6.828 Day23 HW6 multithreaded programing

摘要:MIT6.828 HW6 multithreaded programing

0x01写在前面

按照schedule今天要做两件事情:

1、阅读完xv6参考书的第三章(其实已经是第四章了)以及相关的xv6源码;

2、完成HW6。

不磨叽,开始莽!

0x02 Chapter3 traps, interrupts and drives笔记

Systems calls, exceptions, and interrupts

系统调用、异常、中断导致正常的指令执行流程停止,注意三者区别

陷入由正在处理器上运行的进程产生;中断由设备产生

中断处理器

X86 protection

x86有四个特权级,0-3权级自高到低。常用0,3。意指内核模式以及用户模式,当前的特权在%cs的CPL子段

IDT存放了中断处理器,int n查找得到。int指令后内核栈图示:

剩下的部分就是跟着阅读源码了,没啥好记的笔记,跟着读就可。

Drivers

很多设备会产生中断,而驱动用来管理这些设备产生的中断。

轮询和中断

Real World

DMA用以替代I/O编程以提高访问速度

动态在轮询(polling)和中断(interrupt)之间替换

为了防止因为权限原因导致的复制,可以直接映射只读硬件页面给进程的地址空间

0x03 Homework: Threads and Locking

这次的作业是使用一台多核CPU的真电脑来通过线程和锁完成并行编程。跟着教案提示下载ph.c,编译后运行结果如下:

可以看到,双线程运行效果显著,但是存在不少的keys missing,这就是我们需要解决的问题。

这个程序的工作过程如下:

每个线程有两个工作,第一项工作,每个将NKEYS/nthread个keys放入到哈希表中;第二项工作,每个进程从hash表中那处NKEYS。

单线程工作是get的时候没有keys的丢失,但是多线程的时候有。教案需要我们完成两项任务:

1)找到导致missing的原因;

2)通过插入lock和unlock到put和get中避免missing发生。方式如下:

1
2
3
4
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

首先我们要做的是通读源码,理解程序的工作原理,一段一段来看:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
// 开头宏定义,第二个为哈希表条目数量;第三个为keys的数量
#define SOL
#define NBUCKET 5
#define NKEYS 100000
// 然后是哈希表条目结构体
struct entry {
int key;
int value;
struct entry *next;
};
struct entry *table[NBUCKET];
int keys[NKEYS];
int nthread = 1;
volatile int done;
/*
struct timeval
{
__time_t tv_sec; //Seconds.
__suseconds_t tv_usec; //Microseconds.
};
*/
double
now()
{
struct timeval tv;
gettimeofday(&tv, 0);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
//打印hash表中的条目
static void
print(void)
{
int i;
struct entry *e;
for (i = 0; i < NBUCKET; i++) {
printf("%d: ", i);
for (e = table[i]; e != 0; e = e->next) {
printf("%d ", e->key);
}
printf("\n");
}
}
// 插入值到表中
static void
insert(int key, int value, struct entry **p, struct entry *n)
{
struct entry *e = malloc(sizeof(struct entry));
e->key = key;
e->value = value;
e->next = n;
*p = e;
}
//put和get响应key到hash表中
static
void put(int key, int value)
{
int i = key % NBUCKET;
insert(key, value, &table[i], table[i]);
}

static struct entry*
get(int key)
{
struct entry *e = 0;
for (e = table[key % NBUCKET]; e != 0; e = e->next) {
if (e->key == key) break;
}
return e;
}
//线程处理put和get
static void *
thread(void *xa)
{
long n = (long) xa;
int i;
int b = NKEYS/nthread;
int k = 0;
double t1, t0;

// printf("b = %d\n", b);
t0 = now();
for (i = 0; i < b; i++) {
// printf("%d: put %d\n", n, b*n+i);
put(keys[b*n + i], n);
}
t1 = now();
printf("%ld: put time = %f\n", n, t1-t0);

// Should use pthread_barrier, but MacOS doesn't support it ...
// 原子性相加
__sync_fetch_and_add(&done, 1);
while (done < nthread) ;

t0 = now();
for (i = 0; i < NKEYS; i++) {
struct entry *e = get(keys[i]);
if (e == 0) k++;
}
t1 = now();
printf("%ld: get time = %f\n", n, t1-t0);
printf("%ld: %d keys missing\n", n, k);
return NULL;
}

// 主函数
int
main(int argc, char *argv[])
{
// typedef unsigned long int pthread_t;
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);
}
// atoi()将字符串转换为整型,这边用以获取线程数
nthread = atoi(argv[1]);
//分配对应线程数所需要的空间
tha = malloc(sizeof(pthread_t) * nthread);
//这个我没猜错的话是设置伪随机数种子
srandom(0);
//断言判断对应线程数能否整除key数
assert(NKEYS % nthread == 0);
//随机生成keys
for (i = 0; i < NKEYS; i++) {
keys[i] = random();
}
t0 = now();
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);
}
t1 = now();
printf("completion time = %f\n", t1-t0);
}

分析完整一个代码,我们可以很快发现问题所在。注意到thead中的这一段:

1
2
3
4
for (i = 0; i < b; i++) {
// printf("%d: put %d\n", n, b*n+i);
put(keys[b*n + i], n);
}

我们知道,CPU在执行多个线程的时候是通过时间片来进行调度的,每个线程执行对应的时间,执行完一个时间片后会换下一个线程。而在这个地方,就有可能存在多个线程写入同一个数值进入keys这个全局变量的可能性,从而造成后面get的时候的missing。故我们只需要在这里加入我们的lock就可,使其put成为一个原子操作。

1
2
3
4
5
6
for (i = 0; i < b; i++) {
// printf("%d: put %d\n", n, b*n+i);
pthread_mutex_lock(&lock); // acquire lock
put(keys[b*n + i], n);
pthread_mutex_unlock(&lock); // release lock
}

运行结果如下,符合要求:

至此,HW6完成。

0x04 总结

也没啥好总结的其实,这次HW主要是加深了对中断、陷入等操作的理解,而后的具体的线程作业中则加深了对多线程运行时加锁的理解。以上。


评论