MIT6.828 HW6 Threads and Locking

废话

本次作业的话主要还是理解下所给的ph.c的代码。所给的代码，通过用多线程来操作一个哈希表，多线程之下哈希表的读写会出现一些问题，从而引入了锁来保护读写，使得读写不出现错误。mit给的代码稍微有些晦涩，我尽量描述清楚。

正文

多线程，在接触mit6.828 之前应该已经有一些对多线程编程的经验。引入多线程的目的是为了加快程序的速度，充分利用多核处理器。但是这随之而来有一个问题就是，多个线程在操作同一个数据结构的时候，会导致数据的混乱，比如说链表，哈希表等等。比如说一个链表，我们采用头插法插入链表，这里我用java来写的，相对来说对java熟悉点,代码如下,代码这个就是啰嗦，随便一点代码就写的很长,代码如下:

import java.util.Collection;
import java.util.stream.IntStream;

class MyLinkedList {
    static class Node {
        int data;
        Node next;
        Node (int data) {
            this.data = data;
        }
    }
    private Node head = null;
    MyLinkedList() {}
    
    public void insert(int data) {
        Node node = new Node(data);
        node.next = this.head;
        this.head = node;
    }
    public void printList() {
        while(this.head != null) {
            System.out.println(this.head.data);
            this.head = this.head.next;
        }
    }
    public int getLength() {
        int i = 0;
        while(this.head != null) {
            i++;
            this.head = this.head.next;
        }
        return i;
    }
}

class MyThread extends  Thread {

    ThreadTask task;
    int[] nums;

    public MyThread(ThreadTask task, int[] nums) {
        this.task = task;
        this.nums = nums;
    }
    public MyThread(ThreadTask task) {
        this.task = task;
    }
    @Override
    public void run() {
        task.threadInsert(this.nums);
    }
}
class ThreadTask {
    private MyLinkedList list;

    public ThreadTask(MyLinkedList list) {
        this.list = list;
    }
    public void threadInsert(int[] nums) {
        for(int num : nums) {
            list.insert(num);
        }
    }
}
public class Foo {
    public static void main(String[] args) throws InterruptedException {
        int[] nums = IntStream.range(0,100).toArray();
        MyLinkedList list = new MyLinkedList();
        ThreadTask task = new ThreadTask(list);
        MyThread t1 = new MyThread(task,nums);
        MyThread t2 = new MyThread(task,nums);
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(list.getLength());

    }
}

对上述代码的一点解释，ThreadTask表示线程要执行的任务，它使用threadInsert()往链表中插入数据。MyThread是线程，它调用task.threadInsert(this.nums);插入数据。MyLinkedList是链表，插入数据为头插法。在main函数当中，定义了一个长度为100的输出，开启两个线程分别往链表中插入数据，最后在使用语句System.out.println(list.getLength());输出链表的长度。
多次运行代码，照理来说，输出结果200才是对的，但是在实际中会发现每次输出结果都不一样。在我的实验结果中，有时候输出188,196，有时候输出200。这就是引入多线程带来的问题。

问题产生的原因：
关键的代码是在插入这里,即下面的代码。考虑两个线程A和B，当线程A执行插入的时候，进行到语句this.head = node;，此时还未更新头节点，然后发生了线程切换，切换到了线程B。同样的线程B也开始执行插入的代码，他成功的插入了代码并且更新了头节点。然后又发生了进程切换回到A，此时A继续执行它刚才的代码。this.head = node把刚才B更新的头节点给覆盖了，所以相当于B没有插入节点一样，从而导致输出结果会小于200的情况出现。

    public void insert(int data) {
        Node node = new Node(data);
        node.next = this.head;
        this.head = node;
    }

为了避免这个情况，可以在insert函数之间加上synchronized关键字，这样输出结果就是正确的200，他所实现的效果就是锁的效果。

来看MIT的代码：

如果上面的情况理解以后，那么再来看MIT官网的给的代码，就会好理解一些。只不过他操作的不是链表，他操作的是一个哈希表(hash table)。
首先我们先把官网的ph.c复制过来，编译运行。得到下面的结果:

0: put time = 0.003053
1: put time = 0.003028
0: get time = 6.198966
0: 18182 keys missing
1: get time = 6.327815
1: 18182 keys missing
completion time = 6.331105

就看输出结果其实听茫然的，不知道讲的啥。可以看到put所花时间比较少，大部分的时间都是在get。接下来来看看单线程的情况。下面是单线程的输出结果:

0: put time = 0.003291
0: get time = 5.912693
0: 0 keys missing
completion time = 5.916224

可以看到单线程和多线程完成的时间差不多。这里可能有人会疑问为什么多线程没有加快处理速度?
其实这是因为两个线程做的事情都是一样的。关键在下面的代码:

  for (i = 0; i < NKEYS; i++) {
    struct entry *e = get(keys[i]);
    if (e == 0) k++;
  }

两个线程都要做这个for循环，所以增加线程没有减少运行时间，这是因为在想同时间下工作量变多了。引入了多线程，导致了很多missing，所以我们接下来就是分析Missing产生的原因。

分析代码
有一点说在前面好了，就是这个程序中keys[]这个数组被分割了，如果两个线程，每个线程可以访问各一半的keys，如果3个线程，可以访问各三分之一的keys。放在前面显得十分突兀，不过认真阅读代码可以理解到这一点的。
main函数:

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 < NKEYS; i++) {
    //由随机数产生各个keys，放入到数组当中,后来就会以keys数组中的各个数作为key来放入到hash table中
    keys[i] = random();  
  }
  t0 = now();
  for(i = 0; i < nthread; i++) {
    //创建线程,thread参数表示运行的函数
    assert(pthread_create(&tha[i], NULL, thread, (void *) i) == 0);
  }
  for(i = 0; i < nthread; i++) {
    //pthread_join等待每个线程结束
    assert(pthread_join(tha[i], &value) == 0);
  }
  t1 = now();
  printf("completion time = %f\n", t1-t0);
}

thread函数
thread函数是线程要运行的目标函数，代码如下：

static void *
thread(void *xa)
{
  long n = (long) xa; //线程的序号
  int i;
  int b = NKEYS/nthread; //循环的次数
  int k = 0;   //missing的次数
  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);
    //以之前的随机数产生的keys为key，放入到hash table当中
    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++) {
    //遍历所有的key，获取key对应的entry
    //代码主要的运行时间都是花在这里
    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;
}

put()函数:

static 
void put(int key, int value)
{
  int i = key % NBUCKET; //根据这个i来选择对应的桶

  //missing发生的原因就是，当线程A执行到insert的时候，初始化了一个新的entry，设置好了key，value，
  //但是没有执行*p = e;来更新头节点。此时线程B又来执行insert,它也初始化了entry，把原来的A的entry覆盖掉了
  //这样一来导致的后果就是,当使用keys[i]来从hash table中get的时候，会发现e->key == key不相等,从而得到0
  insert(key, value, &table[i], table[i]);
}

insert函数

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;
  //我觉得这里可能就实在更新链表头，这里就是产生missing的根源
  *p = e;
}

ph.c中关键代码的意思都写在注释里面了。最开始链表的例子如果已经懂了，那么这里发生missing的原因也是很像的。哈希表就是数组和链表的结合体（不懂哈希表的去百度吧。。），所以很自然地也会发生插入链表失败的情况。

为了解决这个问题，那么我们可以在insert中最关键的几句代码上锁。要用到锁，首先需要初始化一下锁。我们在ph.c中新声明一个变量，然后再main函数中将他初始化。代码如下:

声明一下锁
然后再main函数中初始化它:

  pthread_t *tha;
  void *value;
  long i;
  double t1, t0;
  pthread_mutex_init(&lock, NULL);  
//其他代码省略

在put函数和get函数中加入锁，这样就保证了互斥，只有一个线程可以进入临界区。代码如下所示，然后我们重新运行一下。

0: put time = 0.022886
1: put time = 0.022929
0: get time = 12.035287
0: 0 keys missing
1: get time = 12.035289
1: 0 keys missing
completion time = 12.058463

可以看到虽然结果正确了，但是程序运行的时间更长了，这样就失去了多线程的优点。所以在最后课程留下了两个问题，在上锁的情况下如何保证线程的并行同时也保证结果的正确性。其实造成插入错误的原因就是在insert函数。所以我们直接在insert之前上锁。另外一方面， 读取来说，多线程和单线程的读取并没有多大关系，因为它们的读取都不会对数据本身造成影响，所以在get是不用上锁的。代码如下:

1: put time = 0.021644
0: put time = 0.022707
0: get time = 5.815429
0: 0 keys missing
1: get time = 6.025187
1: 0 keys missing
completion time = 6.048090

运行一下发现，结果是正确的。
这是最后的get和put的代码:

static 
void put(int key, int value)
{
  int i = key % NBUCKET;
  pthread_mutex_lock(&lock); 
  insert(key, value, &table[i], table[i]);
  pthread_mutex_unlock(&lock); 
}

static struct entry*
get(int key)
{
  struct entry *e = 0;
  //pthread_mutex_lock(&lock); 
  for (e = table[key % NBUCKET]; e != 0; e = e->next) {
    if (e->key == key) break;
  }
  //pthread_mutex_unlock(&lock); 
  return e;
}

如同在前面说过的，get是不需要上锁的。实验结束~