环境

  1. 准备随便一个Linux(最好已经配置完vscode等)
  2. 拉取仓库
1
git clone https://gitee.com/tjucs/xv6-homework.git

实验操作

PART 1

  1. 先运行不加锁的版本
1
2
3
4
cd ~/xv6-homework
gcc -g -O2 ph.c -pthread -o ph
./ph 1
./ph 2

输出如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
qlc@virtual-machine:~/xv6-homework$ ./ph 1
0: put time = 0.004243
0: get time = 4.143612
0: 0 keys missing
completion time = 4.148539
qlc@virtual-machine:~/xv6-homework$ ./ph 2
1: put time = 0.004632
0: put time = 0.004715
1: get time = 4.322610
1: 16701 keys missing
0: get time = 4.356405
0: 16701 keys missing
completion time = 4.361408

可以看到双线程有 ‘16701 keys missing’ ，需要在ph.c添加锁保护哈希表操作
2. 使用vscode等编辑器编辑ph.c

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
141
142
143
144
145
146
147
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include <sys/time.h>

#define SOL
#define NBUCKET 5
#define NKEYS 100000

struct entry {
  int key;
  int value;
  struct entry *next;
};
struct entry *table[NBUCKET];
pthread_mutex_t locks[NBUCKET]; // 每个桶一个锁
int keys[NKEYS];
int nthread = 1;
volatile int done;


double
now()
{
 struct timeval tv;
 gettimeofday(&tv, 0);
 return tv.tv_sec + tv.tv_usec / 1000000.0;
}

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

static 
void put(int key, int value)
{
  int i = key % NBUCKET;

  pthread_mutex_lock(&locks[i]); // 加锁
  insert(key, value, &table[i], table[i]);
  pthread_mutex_unlock(&locks[i]); // 解锁
}

static struct entry*
get(int key)
{
  int i = key % NBUCKET;
  struct entry *e = 0;

  pthread_mutex_lock(&locks[i]);  // 加锁
  for (e = table[key % NBUCKET]; e != 0; e = e->next) {
    if (e->key == key) break;
  }
  pthread_mutex_unlock(&locks[i]);  // 解锁
  return e;
}

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[])
{
  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);
  assert(NKEYS % nthread == 0);

  // 初始化所有桶的锁
  for (i = 0; i < NBUCKET; i++) {
    pthread_mutex_init(&locks[i], NULL);
  }

  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);
}
  1. 重新编译运行
1
2
3
4
gcc -g -O2 ph.c -pthread -o ph
./ph 1
./ph 2
./ph 4

预期输出：

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
qlc@virtual-machine:~/xv6-homework$ ./ph 1
0: put time = 0.003361
0: get time = 4.385354
0: 0 keys missing
completion time = 4.390409
qlc@virtual-machine:~/xv6-homework$ ./ph 2
0: put time = 0.014913
1: put time = 0.021419
0: get time = 4.742750
0: 0 keys missing
1: get time = 4.820615
1: 0 keys missing
completion time = 4.842471
qlc@virtual-machine:~/xv6-homework$ ./ph 4
2: put time = 0.007668
0: put time = 0.014003
3: put time = 0.020238
1: put time = 0.020935
1: get time = 7.500120
1: 0 keys missing
2: get time = 7.508389
2: 0 keys missing
3: get time = 7.514590
3: 0 keys missing
0: get time = 7.515985
0: 0 keys missing
completion time = 7.537222

线程越多，实践反而长了：桶竞争，线程越多，竞争越激烈

PART 2

  1. 尝试编译运行barrier.c，会失败：
    1. barrier() 没有让线程等待，直接增加 round
    2. 没有使用条件变量让线程阻塞
    3. 线程之间不同步，断言 i == t 失败
1
2
gcc -g -O2 barrier.c -pthread -o barrier
./barrier 2
  1. 编辑barrier.c:
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
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>
#include <pthread.h>

// #define SOL

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
  int waiting; // 已经到达屏障点、正在等待被唤醒的线程数量
} 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 = nthread;  // 设置总线程数
  bstate.waiting = 0; 
}

static void 
barrier()
{
  pthread_mutex_lock(&bstate.barrier_mutex);
  
  int current_round = bstate.round;
  bstate.waiting++;

  if(bstate.waiting == bstate.nthread){
    // 最后一个到达的线程：进入下一轮
    bstate.round++;
    bstate.waiting = 0;
    pthread_cond_broadcast(&bstate.barrier_cond);
  }else{
    // 等待其他线程
    while (bstate.round == current_round) {
      pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
    }
  }
  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);
  }
}

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");
}
  1. 重新编译运行
1
2
3
4
5
gcc -g -O2 barrier.c -pthread -o barrier
./barrier 1
./barrier 2
./barrier 4
./barrier 8

预期输出：

1
2
3
4
5
6
7
8
qlc@virtual-machine:~/xv6-homework$ ./barrier 1
OK; passed
qlc@virtual-machine:~/xv6-homework$ ./barrier 2
OK; passed
qlc@virtual-machine:~/xv6-homework$ ./barrier 4
OK; passed
qlc@virtual-machine:~/xv6-homework$ ./barrier 8
OK; passed

COMPLETED!!!