lxyuma BLOG

開発関係のメモ

linuxカーネルのセマフォについて

アルゴリズムとデータ構造についてOSSから勉強する会 という勉強会に行ってきた。

これは、とある掲示板の書き込みOSSで使われてるアルゴリズムが書かれている物があって、

これを元に、皆で読み解いて行こうという企画。

カーネル読むという意味でも、アルゴリズムの勉強という意味でも、

とても良い勉強会。

面白かった。

まとめ

自分のチームはセマフォやった。

まあ、色々と不慣れだったし分からない所も多かったが、勉強になった。

以下、発表したメモに加筆した。

概要

  • セマフォ(semaphore)とは
    • 複数プロセスによるアクセス制御に使われる仕組みの事
    • 任意の個数の資源を扱うcounting semaphoreと、値が0,1しかないbinary semaphoreがある。
      • 今日見たのは前者のcounting semaphore。この話を書いて行く。
      • ちなみに、後者がMutexになる(同等の機能を持つ)らしい

counting semaphoreって?

この仕組みが面白いのだが、

例えば、自習室に10個の机があって、

入り口の綺麗なお姉さんが、

机の数と同じ10枚のカードを持っていたとする。

(綺麗なお姉さんじゃなくてもいいけど、いきなりIRQの話でてきても嫌になると思うので、

想像の中で、優木まおみみたいなお姉さんがいたとしよう!もう結婚したけど。)

  • 利用する学生から見た時
    • 自習室に入りたければ、1枚カードを取って空いてる机に座る。
    • 自習室から退出したければ、自分の持ってる1枚のカードを返す。
    • もし、自習室のカードが全部、無くなった時は、自習室の前で並ぶ。(この辺り、正しくは後で例示する。一旦、とにかく待ち行列を作るイメージで。)
  • 入り口の綺麗なお姉さん(優木まおみ似)
    • 入り口のお姉さんは、「残り」のカードの枚数で、あと机が何個余っているのか知る。

この時、学生がプロセスにあたり、

優木まおみ似の綺麗なお姉さん!がセマフォにあたる。

お姉さんがカードを管理しているおかげで、自習室に人があふれない。

以下、ソースの説明も、この例を引き続き使う。

ソース

ヘッダファイルから。

https://github.com/mirrors/linux-2.6/blob/master/include/linux/semaphore.h

構造体として、以下を持っている

struct semaphore {
        raw_spinlock_t                lock;
        unsigned int                count;
        struct list_head        wait_list;
};
  • raw_spinlock_t
    • スピンロック:ロック獲得するまでに単純にループして定期的にチェックするロック
    • このロックに必要な情報を入れてるっぽい
  • count
    • 自習室のカードの「残り」枚数
  • wait_list

.cソース

https://github.com/mirrors/linux-2.6/blob/master/kernel/locking/semaphore.c

メインは以下の2種類の関数。

  • 入室=カード枚数が1枚減る
    • downという関数を実行する
  • 退出=カードが1枚戻ってくる=カード枚数が1枚増える
    • upという関数を実行する

downのvarionation

downは幾つかvariationがある。(down/down_interruptib/down_killable ..etc)

基本的には、殆ど一緒だが、違いは、

満室で待ってる時の対応が違うっぽい。

例えば、down_interruptibleは、満室で待ってる時に、シグナルを受けたら待つの止めるが、

down_killableは、満室で待ってる時に、fatalなシグナルを受けたら中断する。

こんな感じの違いがある。

以下より、(今はDeprecatedなのだが、基本的な動きは全部変わらないので)down関数を見る。

down 関数

こんな流れ

  1. spin lockのIRQ上のflagを保存
  2. カウントダウン
    • カウンタが1以上:カウントダウン (count—)
    • カウンタが0:__down_common関数を叩く(status渡す)
      • down_common関数:満室時の待ち処理
  3. spin lockのIRQ上のflagを戻す
void down(struct semaphore *sem)
{
        unsigned long flags;
        raw_spin_lock_irqsave(&sem->lock, flags);
        if (likely(sem->count > 0))
                sem->count--;
        else
                __down(sem);
        raw_spin_unlock_irqrestore(&sem->lock, flags);
}

まずは、raw_spin_lock_irqsaveを見てみる。

raw_spin_lock_irqsave

#define raw_spin_lock_irqsave(lock, flags)                        \
        do {                                                \
                typecheck(unsigned long, flags);        \
                flags = _raw_spin_lock_irqsave(lock);        \
        } while (0)

一見、ループっぽいのだが、do while(0)って、これだった。

http://www.jpcert.or.jp/sc-rules/c-pre10-c.html

ただの固まり。

そもそもIRQとは

この関数名にある、IRQは何なのかというと、

  • IRQ = Interrupt ReQuestの略で、割り込み要求の事。

    • 割り込み要求とはハードウェア(keyboard等)がCPUを呼び出す時に起きる。
    • ソフトウェア側でも例外発生時に、割り込み要求を出す事がある。
    • 要求を受け付ける場合は、現在実行中の処理を中断して優先的に割り込み要求を実施する
  • 以下のコマンドでIRQを見る事ができる

$ cat /proc/interrupts 
           CPU0       CPU1       CPU2       
  0:        132          0          0   IO-APIC-edge      timer
  1:          7          0          0   IO-APIC-edge      i8042
  8:          0          0          0   IO-APIC-edge      rtc0
  9:          0          0          0   IO-APIC-fasteoi   acpi
 10:  133723985          0          0   IO-APIC-fasteoi   virtio0, virtio2
 11:   14239496          0          0   IO-APIC-fasteoi   uhci_hcd:usb1, virtio1, virtio3
 12:        102          0          0   IO-APIC-edge      i8042
 14:          0          0          0   IO-APIC-edge      ata_piix
 15:         62          0          0   IO-APIC-edge      ata_piix
NMI:          0          0          0   Non-maskable interrupts
LOC: 3207352625 2940858960 2935259295   Local timer interrupts
SPU:          0          0          0   Spurious interrupts
PMI:          0          0          0   Performance monitoring interrupts
PND:          0          0          0   Performance pending work
RES:   71463290   73636621   72198537   Rescheduling interrupts
CAL:        291        552        648   Function call interrupts
TLB:    1270192    1591796    1461926   TLB shootdowns
TRM:          0          0          0   Thermal event interrupts
THR:          0          0          0   Threshold APIC interrupts
MCE:          0          0          0   Machine check exceptions
MCP:      79072      79072      79072   Machine check polls
ERR:          0
MIS:          0

これが、例示していた自習室の、linuxカーネル内の実際のイメージ。

カーネルはこのIRQを管理するために、セマフォを使ってるみたい。

raw_spin_lock_irqsaveは、このIRQに一旦、保存してるっぽい。

中身を更にほじると、

raw_spin_lock_irqsave

https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/spinlock_api_smp.h

static inline unsigned long __raw_spin_lock_irqsave(raw_spinlock_t *lock)
{
        unsigned long flags;

        local_irq_save(flags);
        preempt_disable();
        spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
        /*
         * On lockdep we dont want the hand-coded irq-enable of
         * do_raw_spin_lock_flags() code, because lockdep assumes
         * that interrupts are not re-enabled during lock-acquire:
         */
#ifdef CONFIG_LOCKDEP
        LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
#else
        do_raw_spin_lock_flags(lock, &flags);
#endif
        return flags;
}
  1. flagをIRQ保存
  2. 生のスピンロックさせるためのflagを立ててるっぽい

今、これで、IRQに自分のプロセスを示すフラグを登録した状態。

奥迄深入りするのは、ここまでにして、down関数の話に戻る。

次に、メインとなる、カウントダウンをする。

カウントダウン処理

今、IRQを1つ占有したので、カウントダウンしないといけない。

元の例で言うと、自習室の机を1つ取ったので、カードを1枚ひかないといけない。

  • もし、まだカードがあれば、
    • 単純にカードを引いて(カウントダウン)
  • もし、カードが無ければ
    • down_common実行する(これが満室時の待ち処理)

※なので、このロジックを正しく例示すると、満室だろうが学生は自習室にとにかく入っていて、自分の名前を勝手に部屋に落書きした後、自習室カードの奪い合いをしてるイメージになる。(カードを貰わないと、自習は始められない)

__down_common

大まかな流れ

  • 待ち行列に自分を入れる
  • 無限ループ ( for(;;){ } )
    • 一旦、unlockして、少し待ってから、その後、ロックし直す。
    • もし、semaphore_waiterが実行中になったら、抜ける。

この無限ループしてる所が、スピンロックの実体と思われる。

static inline int __sched __down_common(struct semaphore *sem, long state,
                                                                long timeout)
{
        struct task_struct *task = current;
        struct semaphore_waiter waiter;

        list_add_tail(&waiter.list, &sem->wait_list);
        waiter.task = task;
        waiter.up = false;

        for (;;) {
                if (signal_pending_state(state, task))
                        goto interrupted;
                if (unlikely(timeout <= 0))
                        goto timed_out;
                __set_task_state(task, state);
                raw_spin_unlock_irq(&sem->lock);
                timeout = schedule_timeout(timeout);
                raw_spin_lock_irq(&sem->lock);
                if (waiter.up)
                        return 0;
        }

unlock_irqrestore

この後、IRQに登録したflagをrestore

static inline void __raw_spin_unlock_irqrestore(raw_spinlock_t *lock,
                                            unsigned long flags)
{
        spin_release(&lock->dep_map, 1, _RET_IP_);
        do_raw_spin_unlock(lock);
        local_irq_restore(flags);
        preempt_enable();
}

おしまい

カーネルは非常に奥が深く、奥にもぐっていくとどこまでも行けそう。

ちょっと、よく分からない所も多々あったのだが、

せっかく、色々調べたので、残しておく。

また、次もこのイベント行こうと思う。