[超初心者向け！]Lock 実装を理論からわかりやすく解説 [Two Phase Locking / Compare and Swap]

はじめに

Lock 実装をコーディング初心者でも分かるように解説してみました

この記事の対象者

・トランザクションの記事を読んでくれた人
・B+treeが実装できた人

一緒に実装しましょう！

トランザクションの記事はこちらから

https://zenn.dev/risaaa/articles/1e7b632db3f4bf

目次

1. processとthreadの違い
2. なぜ Lock がいるのか
3. Lock の種類
4. コード解説
   コードの書き方はあくまで一例です
   絶対的な解ではありませんので、参考にしていただければ幸いです

1. processとthreadの違い

複数の CPU に分けて処理するため、process から thread を作成します
複数あるスレッド (マルチスレッド) を複数の CPU (マルチプロセッサ) が操作することで より高速に処理を終えることができます

2. なぜ Lock がいるのか

同時にメモリから読み込んで、別々の CPU (マルチプロセッサ)で処理をしてそれぞれメモリに書き込む場合、本来なって欲しい値と違う値がメモリに記録されてしまうことがあります
これを Lost Update といいます

このような不整合 (アノマリー)　をなくすためには Lock が必要です

3. Lock の種類

2PLでは (Two phase Locking) ２種類のロックが使用されます

Shared lock

トランザクションが読み込むデータアイテムに使用されます

同じデータアイテムに対して、複数の Shared lockを取ることができます
読むだけだったら、値が変わることはないためいくつロックを取ったとしてもアノマリーが発生することはないからです
しかし Shared lockを取った後に Exclusive lockを取ることはできません

Exclusive lock

トランザクションが書き込むデータアイテムに使用されます

同じデータアイテムに対して、Exclusive lockを取った後にExclusive lockを取ることはできません
また、Exclusive lockを取った後にShared lockを取ることはできません

4. コード解説

1. Exclusive lock

まずはとりあえず実装を見てみましょう

pointer.cpp

void lock()
    {
        int64_t expected;
        while (true)
        {
            expected = __atomic_load_n(&cnt, __ATOMIC_SEQ_CST); // 値はatomicにloadする必要がある
            if (expected == 0 && __atomic_compare_exchange_n(&cnt, &expected, -1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))
            {
                return;
            }
        }
    }

lockする時の手順はこちらです
①lockの値をアドミックに読む
②Compare and Swap して、もし書くまえにもう一回読んでloadした値と一緒だったら書く
③もしlockがとれなかった場合ループする

②アトミックに読むとは？

メモリ階層は優先度が高い順にレジスタ、キャッシュ、メモリです
CPU にはレジスタとキャッシュが入っています

複数のCPU(マルチプロセッサ)の場合、データがどこに配置されるかはOSが自動で設定します(paging)
そのため、もしcacheに入ってしまうと、他のCPUが読めなくなってしまいます

これにより変更内容は必ずメモリに配置されるようにするためアトミックにロックを外す必要があります

③Compare and Swap とは？

データを変更するまえにもう一回読んで、もしloadした値と一緒だったら書くことです
このように、ロックカウンターを同時にロードしてから書き換えた場合、本来は一個しか取れないロックが二つ取れてしまうという状況になってしまいます

そこで Compare and swap を導入することで、ロックが必ず１つしか取れないようにします

Compare and swap の手順は以下の通りです
①loadする
②書くまえにもう一回読んでloadした値と一緒だったら書く

こうすることによって、読んでから書く間に書き換えられている心配がありません

2. unlock

unlock.cpp

 void unlock()
    {
        //__atomic_fetch_add(&cnt, 1, __ATOMIC_SEQ_CST); -1 => 0
        __atomic_store_n(&cnt, 0, __ATOMIC_SEQ_CST);

        // この実装だと壊れる
        // int cur_cnt = cnt; // load
        // cnt = cur_cnt + 1; // store
        //
    } // unlock: 1

手順はこちらです
①アトミックにロックを外す
こちらも上記に記した通り、メモリ階層の関係でアトミックに外す必要があります。(変更内容が必ずメモリに入るようにしないと他の CPU が読むことができなくなってしまう)

3. Shared lock

shared_lock.cpp

 void lock_shared()
    {
        int64_t expected;
        while (true)
        {
            expected = __atomic_load_n(&cnt, __ATOMIC_SEQ_CST);
            if (expected >= 0 && __atomic_compare_exchange_n(&cnt, &expected, expected + 1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))
            {
                return;
            }
        

Shared lock はとられるたびに、Lock counter が1ずつ増えます
Exclusive lockはとられるとLock counterが-1になる

つまり、Lock counter の状態をまとめると以下のようになります
Shared lockが取られている状態: Shared lock毎に+1
なにもLockが取られていない状態: 0
Exclusive lock: -1

最後に Exclusive lockだけではありますが、コードを載せておきます。ぜひ実行してみてください

pointer.cpp

#include <cassert>
#include <unordered_map>
#include <thread>
#include <vector>
#include <iostream>
#include <stdio.h>

class Lock
{
public:
    Lock()
        : cnt(0) {}
    void initialize()
    {
        cnt = 0; // if locked: -1, if unlocked: 0
    }
    void lock()
    {
        int64_t expected;
        while (true)
        {
            expected = __atomic_load_n(&cnt, __ATOMIC_SEQ_CST); // 値はatomicにloadする必要がある
            if (expected == 0 && __atomic_compare_exchange_n(&cnt, &expected, -1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))
            {
                return;
            }
        }
    }

    void unlock()
    {
        //__atomic_fetch_add(&cnt, 1, __ATOMIC_SEQ_CST); -1 => 0
        __atomic_store_n(&cnt, 0, __ATOMIC_SEQ_CST);

        // この実装だと壊れる
        // int cur_cnt = cnt; // load
        // cnt = cur_cnt + 1; // store
        //
    } // unlock: 1

private:
    int64_t cnt = 0;
    // cnt==-1 誰かがlockを取っている
    // cnt==0 誰もlockをとっていない
};

int river_tshirt = 100;
Lock lock;

void function()
{
    // river_tshirt--;

    lock.lock(); // acquire lock
    int current_stock = river_tshirt;
    river_tshirt = current_stock - 1;
    lock.unlock(); // release lock
}

int main()
{
    int thread_num = 100;
    std::vector<std::thread> threads;
    for (int i = 0; i < thread_num; i++)
    {
        threads.emplace_back(function); // start thread
    }

    for (int i = 0; i < thread_num; i++)
    {
        threads[i].join(); // end thread
    }

    std::cout << river_tshirt << std::endl;
}

// tony: function()   load:3                  store:2
// risa: function()           load:3                   store:2
// rina: function()                                             load:2    store:1

// コードの説明
// ①100個tshirtがある
// ②100個のthreadが一つずつtshirtを購入
// ③最終的に0個になり0が出力される

最後まで読んでくださりありがとうございました！