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 関数
こんな流れ
- spin lockのIRQ上のflagを保存
- カウントダウン
- カウンタが1以上:カウントダウン
(count—)
- カウンタが0:__down_common関数を叩く(status渡す)
- down_common関数:満室時の待ち処理
- カウンタが1以上:カウントダウン
- 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
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; }
- flagをIRQ保存
- 生のスピンロックさせるための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(); }
おしまい
カーネルは非常に奥が深く、奥にもぐっていくとどこまでも行けそう。
ちょっと、よく分からない所も多々あったのだが、
せっかく、色々調べたので、残しておく。
また、次もこのイベント行こうと思う。