MITのxv6を読もう - 第4章ロックは何故必要なのか -

6.828 / Fall 2014

この章から、ロックの説明に入る。まずは、ロックが必要なのかという説明から。こんなものMITの学生にしてみれば全く常識的な話だとは思うが、一応説明されている。

struct list {
    int data;
    struct list *next;
};

struct list *list = 0;

void
insert(int data)
{
    struct list *l;
    
    l = malloc(sizeof *l);
    l->data = data;
    l->next = list;
    list = l;
}

これをマルチプロセッサ上で実行してしまうと、最後のlistへの追加の部分で、どちらかのプロセッサで挿入しようとしたノードが欠落してしまう。これを理論的に説明するために、「不変性(invariant)」という用語で説明が行われているね。

不変性とは、処理の最初と最後で、変わらない特性のこと。ここでいう不変性は、insertが始まる前から、listはノードの先頭要素を保持し、全てのノードをリンクで繋いでいる、ということ。しかし、処理を実行している最中にその不変性が崩れる。以下の文だ。

    l->next = list;
    list = l;

新しく作成されたlはまだリンクに繋げられておらず、不変性が崩れている。また、list=lとする直前までは、この不変性が崩れている状態が続く。この不変性が崩れている状態に複数のプロセスが同時に入ると、「レースコンディション」という状態が発生し、一方のノードがリンクに接続されない状態となってしまう、という訳だ。

struct list *list = 0;
struct lock listlock;

void insert(int data)
{
    struct list *l;
    
    acquire(&listlock);
    l = malloc(sizeof *l);
    l->data = data;
    l->next = list;
    list = l;
    release(&listlock);
}

不変性が崩れる部分をロックで囲み、この部分をあるタイミングで唯一のプロセスが実行するようにする。これにより、不変性を崩すのはたった一つのCPUのみであり、これでリンクが破壊されることは無くなる。