6.828 操作系统 Homework: Multithread

作者: 找不到工作 | 来源:发表于2017-04-15 11:19 被阅读126次

6.828 操作系统 Homework: Multithread
6.828 操作系统 Homework: Shell
1 搭建实验环境
算法与数据结构概要
MultiThread
下载
mit6.828-操作系统实践
无标题文章
MIT6.828 学习心得
c++ multithread and lock--part 1

题目介绍

https://pdos.csail.mit.edu/6.828/2016/homework/lock.html
比较有价值的一个作业。重点考察了两个知识：

哈希表的实现
多线程与互斥锁

题目已给出基本的框架，大意是多核处理器下，使用多线程对共享数据（哈希表）进行操作，会带来效率的提升，然而如果不加锁就会出现不正确的结果。所以需要你在适当地方使用互斥锁。

直接上代码吧。为了方便理解做了一些变量名的更改与注释。

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <pthread.h>
#include <sys/time.h>

#define NBUCKET 5
#define NKEYS 100000

/*
 * 实现了一个哈希表，对 NBUCKET 取余进行散列
 *
 */

struct entry {
    int key;
    int value;
    struct entry *next;
};

// table 中存放的是 5 个地址，链表头
struct entry *table[NBUCKET];
int keys[NKEYS];
// 线程数量默认为1
int nthread = 1;
// done 用于统计有多少个线程已经完成
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 val, struct entry **p, struct entry *n) {
    // 在链表头插入
    struct entry *e = (struct entry *)malloc(sizeof(struct entry));
    e->key = key;
    e->value = val;
    e->next = n;
    *p = e;
}

static void put(int key, int val) {
    int i = key % NBUCKET;
    insert(key, val, &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;
}

static void *task(void *xa){

    long n = (long) xa;
    int b = NKEYS / nthread;
    int no_found_count = 0;
    double t0, t1;
    t0 = now();
    // 第 n 个线程put [n*b, (n+1)*b) 范围内的 entry
    for (int i = 0; i < b; i++) {
        put(keys[b*n + i], n);
    }
    t1 = now();
    printf("thread %ld: put time = %f\n", n, t1-t0);
    
    // 等待所有线程完成 put 操作
    __sync_fetch_and_add(&done, 1);
    while (done < nthread);

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

int main(int argc, char const *argv[]) {
    if (argc < 2) {
        printf("%s: %s nthread\n", argv[0], argv[0]);
        return -1;
    }
    nthread = atoi(argv[1]);
    // 分配好 threads 的空间，此后由 pthread_create 修改其内容为线程id
    pthread_t *threads = (pthread_t *)malloc(sizeof(pthread_t) * nthread);
    srandom(0);
    assert(NKEYS % nthread == 0);

    for (int i=0; i<NKEYS; i++) {
        keys[i] = random();
    }
    double t0 = now();
    for (int i=0; i<nthread; i++) {
        // arg0 线程id，
        // arg1 线程属性
        // arg2 需要执行的函数 void * (*task) (void  *)
        // arg3 函数的参数
        // 将 i 转为 void* 类型，内容还是 i，表明是第几个线程
        assert(pthread_create(&threads[i], NULL, task, (void *)i) == 0);
    }
    void *value;
    for (int i=0; i<nthread; i++) {
        // arg0 要回收的线程id
        // arg1 该线程的返回值
        // 会阻塞直到线程运行结束
        assert(pthread_join(threads[i], &value) == 0);
    }
    double t1 = now();
    printf("completion time = %.4f\n", t1-t0);
    return 0;
}

这个程序运行会出现问题，症状如下：

单线程

$ ./a.out 1
thread 0: put time = 0.004676
thread 0: get time = 11.021167
thread 0: 0 keys missing
completion time = 11.0260

多线程

$ ./a.out 2
thread 0: put time = 0.025475
thread 1: put time = 0.028295
thread 1: get time = 12.859959
thread 1: 15880 keys missing
thread 0: get time = 12.930442
thread 0: 15880 keys missing
completion time = 12.9592

显然，在几乎同样的时间里，多线程获得了效率提升（因为是多核cpu）。对整个哈希表查询了2轮，符合预期。然而，却出现了条目为空的情况。

分析

哪些是共享数据？
个人认为，本题中的共享数据，包括全局变量，以及在堆上的数据。
仅有写数据需要加锁，读数据并不需要。
在整个过程中，仅有 put 函数对全局变量做了更改。所以要加锁肯定加在 put 函数前。
为什么会丢失 key？
关键的 insert 函数中，如果线程 A 执行到e->next = n;切换到线程B，线程B执行完成 insert 函数，返回线程 A 执行，则会出现连续改动两次链表头，相当于线程 B 的链表头直接被覆盖，造成丢失。

static void insert(int key, int val, struct entry **p, struct entry *n) {
    // 在链表头插入
    struct entry *e = (struct entry *)malloc(sizeof(struct entry));
    e->key = key;
    e->value = val;
    e->next = n;
    *p = e;
}

修改代码，加入全局变量：

pthread_mutex_t lock;

在 main 函数中初始化：

pthread_mutex_init(&lock, NULL);

将 task 函数修改为：

static void *task(void *xa){
    long n = (long) xa;
    int b = NKEYS / nthread;
    int no_found_count = 0;
    double t0, t1;
    t0 = now();
    // put 时加锁
    pthread_mutex_lock(&lock);
    for (int i = 0; i < b; i++) {
        put(keys[b*n + i], n);
    }
    // put 结束时解锁
    pthread_mutex_unlock(&lock);

    t1 = now();
    printf("thread %ld: put time = %f\n", n, t1-t0);

    __sync_fetch_and_add(&done, 1);
    while (done < nthread);

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

现在单线程执行结果为：

$ ./a.out 1
thread 0: put time = 0.004574
thread 0: get time = 10.766191
thread 0: 0 keys missing
completion time = 10.7710

多线程执行结果为：

./a.out 2
thread 0: put time = 0.002329
thread 1: put time = 0.004662
thread 1: get time = 10.282535
thread 1: 0 keys missing
thread 0: get time = 10.282641
thread 0: 0 keys missing
completion time = 10.2877