廢話

本次作業(yè)的話主要還是理解下所給的ph.c的代碼。所給的代碼，通過用多線程來操作一個哈希表，多線程之下哈希表的讀寫會出現(xiàn)一些問題，從而引入了鎖來保護讀寫，使得讀寫不出現(xiàn)錯誤。mit給的代碼稍微有些晦澀，我盡量描述清楚。

正文

多線程，在接觸mit6.828 之前應該已經(jīng)有一些對多線程編程的經(jīng)驗。引入多線程的目的是為了加快程序的速度，充分利用多核處理器。但是這隨之而來有一個問題就是，多個線程在操作同一個數(shù)據(jù)結(jié)構(gòu)的時候，會導致數(shù)據(jù)的混亂，比如說鏈表，哈希表等等。比如說一個鏈表，我們采用頭插法插入鏈表，這里我用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表示線程要執(zhí)行的任務，它使用threadInsert()往鏈表中插入數(shù)據(jù)。MyThread是線程，它調(diào)用task.threadInsert(this.nums);插入數(shù)據(jù)。MyLinkedList是鏈表，插入數(shù)據(jù)為頭插法。在main函數(shù)當中，定義了一個長度為100的輸出，開啟兩個線程分別往鏈表中插入數(shù)據(jù)，最后在使用語句System.out.println(list.getLength());輸出鏈表的長度。
多次運行代碼，照理來說，輸出結(jié)果200才是對的，但是在實際中會發(fā)現(xiàn)每次輸出結(jié)果都不一樣。在我的實驗結(jié)果中，有時候輸出188,196，有時候輸出200。這就是引入多線程帶來的問題。

問題產(chǎn)生的原因：
關鍵的代碼是在插入這里,即下面的代碼?？紤]兩個線程A和B，當線程A執(zhí)行插入的時候，進行到語句this.head = node;，此時還未更新頭節(jié)點，然后發(fā)生了線程切換，切換到了線程B。同樣的線程B也開始執(zhí)行插入的代碼，他成功的插入了代碼并且更新了頭節(jié)點。然后又發(fā)生了進程切換回到A，此時A繼續(xù)執(zhí)行它剛才的代碼。this.head = node把剛才B更新的頭節(jié)點給覆蓋了，所以相當于B沒有插入節(jié)點一樣，從而導致輸出結(jié)果會小于200的情況出現(xiàn)。

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

為了避免這個情況，可以在insert函數(shù)之間加上synchronized關鍵字，這樣輸出結(jié)果就是正確的200，他所實現(xiàn)的效果就是鎖的效果。

來看MIT的代碼：

如果上面的情況理解以后，那么再來看MIT官網(wǎng)的給的代碼，就會好理解一些。只不過他操作的不是鏈表，他操作的是一個哈希表(hash table)。
首先我們先把官網(wǎng)的ph.c復制過來，編譯運行。得到下面的結(jié)果:

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

就看輸出結(jié)果其實聽茫然的，不知道講的啥。可以看到put所花時間比較少，大部分的時間都是在get。接下來來看看單線程的情況。下面是單線程的輸出結(jié)果:

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循環(huán)，所以增加線程沒有減少運行時間，這是因為在想同時間下工作量變多了。引入了多線程，導致了很多missing，所以我們接下來就是分析Missing產(chǎn)生的原因。

分析代碼
有一點說在前面好了，就是這個程序中keys[]這個數(shù)組被分割了，如果兩個線程，每個線程可以訪問各一半的keys，如果3個線程，可以訪問各三分之一的keys。放在前面顯得十分突兀，不過認真閱讀代碼可以理解到這一點的。
main函數(shù):

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]); //從命令行中獲得線程的個數(shù)
  tha = malloc(sizeof(pthread_t) * nthread); //為線程開辟內(nèi)存
  srandom(0); //隨機數(shù)種子 
  assert(NKEYS % nthread == 0);
  for (i = 0; i < NKEYS; i++) {
    //由隨機數(shù)產(chǎn)生各個keys，放入到數(shù)組當中,后來就會以keys數(shù)組中的各個數(shù)作為key來放入到hash table中
    keys[i] = random();  
  }
  t0 = now();
  for(i = 0; i < nthread; i++) {
    //創(chuàng)建線程,thread參數(shù)表示運行的函數(shù)
    assert(pthread_create(&tha[i], NULL, thread, (void *) i) == 0);
  }
  for(i = 0; i < nthread; i++) {
    //pthread_join等待每個線程結(jié)束
    assert(pthread_join(tha[i], &value) == 0);
  }
  t1 = now();
  printf("completion time = %f\n", t1-t0);
}

thread函數(shù)
thread函數(shù)是線程要運行的目標函數(shù)，代碼如下：

static void *
thread(void *xa)
{
  long n = (long) xa; //線程的序號
  int i;
  int b = NKEYS/nthread; //循環(huán)的次數(shù)
  int k = 0;   //missing的次數(shù)
  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);
    //以之前的隨機數(shù)產(chǎn)生的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()函數(shù):

static 
void put(int key, int value)
{
  int i = key % NBUCKET; //根據(jù)這個i來選擇對應的桶

  //missing發(fā)生的原因就是，當線程A執(zhí)行到insert的時候，初始化了一個新的entry，設置好了key，value，
  //但是沒有執(zhí)行*p = e;來更新頭節(jié)點。此時線程B又來執(zhí)行insert,它也初始化了entry，把原來的A的entry覆蓋掉了
  //這樣一來導致的后果就是,當使用keys[i]來從hash table中get的時候，會發(fā)現(xiàn)e->key == key不相等,從而得到0
  insert(key, value, &table[i], table[i]);
}

insert函數(shù)

static void 
insert(int key, int value, struct entry **p, struct entry *n)
{
  //在對應的鏈表中新插入一個節(jié)點,這里采用的應該是頭插法插入往鏈表中插入節(jié)點
  //所以必然涉及到更新鏈表頭的操作
  struct entry *e = malloc(sizeof(struct entry));
  e->key = key;
  e->value = value;
  e->next = n;
  //我覺得這里可能就實在更新鏈表頭，這里就是產(chǎn)生missing的根源
  *p = e;
}

ph.c中關鍵代碼的意思都寫在注釋里面了。最開始鏈表的例子如果已經(jīng)懂了，那么這里發(fā)生missing的原因也是很像的。哈希表就是數(shù)組和鏈表的結(jié)合體（不懂哈希表的去百度吧。。），所以很自然地也會發(fā)生插入鏈表失敗的情況。

為了解決這個問題，那么我們可以在insert中最關鍵的幾句代碼上鎖。要用到鎖，首先需要初始化一下鎖。我們在ph.c中新聲明一個變量，然后再main函數(shù)中將他初始化。代碼如下:

聲明一下鎖

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

在put函數(shù)和get函數(shù)中加入鎖，這樣就保證了互斥，只有一個線程可以進入臨界區(qū)。代碼如下所示，然后我們重新運行一下。

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

可以看到雖然結(jié)果正確了，但是程序運行的時間更長了，這樣就失去了多線程的優(yōu)點。所以在最后課程留下了兩個問題，在上鎖的情況下如何保證線程的并行同時也保證結(jié)果的正確性。其實造成插入錯誤的原因就是在insert函數(shù)。所以我們直接在insert之前上鎖。另外一方面， 讀取來說，多線程和單線程的讀取并沒有多大關系，因為它們的讀取都不會對數(shù)據(jù)本身造成影響，所以在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

運行一下發(fā)現(xiàn)，結(jié)果是正確的。
這是最后的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是不需要上鎖的。實驗結(jié)束~