LKDノート:カーネル同期方法

33962 ワード

前のセクションでは、カーネルの同期方法について説明しました.

げんしさぎょ

反発ロックと条件変数のこの論文から,複数のスレッドが同じ整数を自己増加操作しても同期問題があることが分かった(整数の自己増加操作は原子(性)ではないため).
したがって、カーネルは2つの原子的な操作インタフェースを提供します.1つのインタフェースは1つの整数を操作し、もう1つのインタフェースは整数のいずれかを操作します.これらのインタフェースの実装はCPUアーキテクチャに関連している.ほとんどのCPUアーキテクチャは、単純な算術操作の原子化バージョンを提供しています.

原子の整数操作

原子操作が可能な32ビット整数はatomic_t構造体で表される.

typedef struct {
    volatile int counter;
} atomic_t;

整数原子変数を定義して初期化するには、次のようにします.

atomic_t v; /* define v */
atomic_t u = ATOMIC_INIT(0); /* define u and initialize it to zero */

操作は簡単です.

atomic_set(&v, 4); /* v = 4 (atomically) */
atomic_add(2, &v); /* v = v + 2 = 6 (atomically) */
atomic_inc(&v); /* v = v + 1 = 7 (atomically) */

intに変換したい場合は、atomic_read()を使用します.

printk(“%d
”, atomic_read(&v)); /* will print “7” */

通常、原子整数操作を使用するシーンは、カウンタを実装するために使用されます.
もう1つの使用シーンは、1つの操作を原子的に実行し、結果をテストすることです.一般的な例は、原子的に減少し、テストすることです.

int atomic_dec_and_test(atomic_t *v)

この関数は原子変数の値を1つ減らします.結果が0の場合はtrueを返し、そうでない場合はfalseを返します.
完全な原子整数操作のリストは次のとおりです.

ATOMIC_INIT(int i)                          //At declaration, initialize to i.

int atomic_read(atomic_t *v)                //Atomically read the integer value of v.

void atomic_set(atomic_t *v, int i)         //Atomically set v equal to i.

void atomic_add(int i, atomic_t *v)         //Atomically add i to v.

void atomic_sub(int i, atomic_t *v)         //Atomically subtract i from v.

void atomic_inc(atomic_t *v)                //Atomically add one to v.

void atomic_dec(atomic_t *v)                //Atomically subtract one from v.

int atomic_sub_and_test(int i, atomic_t *v) //Atomically subtract i from v and return true if the result is zero; otherwise false.

int atomic_add_negative(int i, atomic_t *v) //Atomically add i to v and return true if the result is negative; otherwise false.

int atomic_add_return(int i, atomic_t *v)   //Atomically add i to v and return the result.

int atomic_sub_return(int i, atomic_t *v)   //Atomically subtract i from v and return the result.

int atomic_inc_return(int i, atomic_t *v)   //Atomically increment v by one and return the result.

int atomic_dec_return(int i, atomic_t *v)   //Atomically decrement v by one and return the result.

int atomic_dec_and_test(atomic_t *v)        //Atomically decrement v by one and return true if zero; false otherwise.

int atomic_inc_and_test(atomic_t *v)        //Atomically increment v by one and return true if the result is zero; false otherwise.

64ビット原子操作

原子操作が可能な64ビット整数はatomic64_t構造体で表される.

typedef struct {
    volatile long counter;
} atomic64_t;

32ビット原子操作関数接頭辞atomicをatomic 64に変更すると64ビット原子操作関数が得られる.

原子の位置操作

コアは原子のビット操作インタフェースも提供する.驚くべきことに、これらのビット操作関数は、整数ではなく一般的なメモリアドレスを操作します.関数のパラメータは、ポインタとビットを表す数です.1つの例を直接見てみましょう.

unsigned long word = 0;

set_bit(0, &word); /* bit zero is now set (atomically) */
set_bit(1, &word); /* bit one is now set (atomically) */
printk(“%ul
”, word); /* will print “3” */
clear_bit(1, &word); /* bit one is now unset (atomically) */
change_bit(0, &word); /* bit zero is flipped; now it is unset (atomically) */

/* atomically sets bit zero and returns the previous value (zero) */
if (test_and_set_bit(0, &word)) {
/* never true ... */
}

/* the following is legal; you can mix atomic bit instructions with normal C */
word = 7;

完全なビット操作のリストは次のとおりです.

void set_bit(int nr, void *addr)            //Atomically set the nr-th bit starting from addr.

void clear_bit(int nr, void *addr)          //Atomically clear the nr-th bit starting from addr.

void change_bit(int nr, void *addr)         //Atomically flip the value of the nr-th bit starting from addr.

int test_and_set_bit(int nr, void *addr)    //Atomically set the nr-th bit starting from addr and return the previous value.

int test_and_clear_bit(int nr, void *addr)  //Atomically clear the nr-th bit starting from addr and return the previous value.

int test_and_change_bit(int nr, void *addr) //Atomically flip the nr-th bit starting from addr and return the previous value.

int test_bit(int nr, void *addr)            //Atomically return the value of the nrth bit starting from addr.

カーネルは、あるアドレスから最初の被置上位(または非被置上位)のビット数を検索する関数も提供します.

int find_first_bit(unsigned long *addr, unsigned int size)
int find_first_zero_bit(unsigned long *addr, unsigned int size)

スピンロック

臨界領域が単純な変数操作のみを含む場合,上記原子操作を用いればよい.しかし、現実の臨界領域での操作は、チェーンテーブルのようなデータ構造を操作するなど、より複雑である.このようなシーンでは、最も基本的なロックであるスピンロックが必要です.基本的な使い方は次のとおりです.

DEFINE_SPINLOCK(mr_lock);
spin_lock(&mr_lock);
/* critical region ... */
spin_unlock(&mr_lock);

スピンロックは同時に1つのスレッドにしか持たれません.すなわち,一度に1つのスレッドが臨界領域に入ることしか許されない.これにより、マルチプロセッサに必要なパラレルアクセス保護が提供されます.シングルプロセッサでは、スピンロックはコンパイル後には存在しません.カーネルプリエンプトをオフまたはオンにするタグとしてのみ使用されます.カーネルプリエンプトがコンパイル時に閉じられると、スピンロックはコンパイルが完了するとまったく存在しません.
注意:スピンロックは再帰的ではありません.自分がすでに持っているロックを取得しようとすると、スピンしてロックを解放するのを待っています.しかし、スピンしているので、ロックを解放することはありません.そうすれば、デッドロックになります.
スピンロックは割り込み処理関数で使用できますが、信号量は睡眠をとるため使用できません.割り込み処理関数でロックを使用する場合は、ロックを取得する前にローカル割り込みをオフにする必要があります.そうでない場合、割り込み処理関数は、ロックが保持されている間にカーネルコードを割り込み、ロックを取得しようとする可能性があります.このとき,割り込み処理関数はスピンでロック解放を待つ.しかしながら、ロックの所有者は、割り込み処理関数が完了した後にのみロックを解放する機会がある.これによりデッドロックが発生します.
ローカル割り込みをオフにするだけで、割り込みが別のプロセッサで発生した場合、ロックの所有者が最終的にロックを解除することを阻止しません.
カーネルは、ローカル割り込みを容易にオフにしてロックを取得するインタフェースを提供します.使用方法は次のとおりです.

DEFINE_SPINLOCK(mr_lock);
unsigned long flags;

spin_lock_irqsave(&mr_lock, flags);
/* critical region ... */
spin_unlock_irqrestore(&mr_lock, flags);

割り込みが臨界領域に入る前に開いていると判断した場合は、割り込み状態を回復する必要はありません.無条件にロックを解除してから割り込みを開くことができます.この場合、spin_lock_irq()およびspin_unlock_irq()の使用が最適である.

DEFINE_SPINLOCK(mr_lock);

spin_lock_irq(&mr_lock);
/* critical section ... */
spin_unlock_irq(&mr_lock);

しかし、カーネルコードの量が膨大なため、あるコードパスに割り込みが開いていることを確認するのは難しいので、この方法はお勧めしません.

その他のスピンロック方法

完全なスピンロック方法のリストは次のとおりです.

spin_lock()               //Acquires given lock

spin_lock_irq()           //Disables local interrupts and acquires given lock

spin_lock_irqsave()       //Saves current state of local interrupts, disables local interrupts, and acquires given lock

spin_unlock()             //Releases given lock

spin_unlock_irq()         //Releases given lock and enables local interrupts

spin_unlock_irqrestore()  //Releases given lock and restores local interrupts to given previous state

spin_lock_init()          //Dynamically initializes given spinlock_t

spin_trylock()            //Tries to acquire given lock; if unavailable, returns nonzero

spin_is_locked()          //Returns nonzero if the given lock is currently acquired, otherwise it returns zero

スピンロックと下半部

下半分がプロセスコンテキストコードをプリエンプトする可能性があるため、データが下半分とプロセスコンテキストの間で共有されている場合は、ロックを使用して下半分をオフにしてプロセスコンテキスト内のデータを保護する必要があります.同様に、割り込み処理関数は最下位を占める可能性があるため、割り込み処理関数と最下位との間でデータが共有されている場合は、適切なロックを取得し、割り込みをオフにする必要があります.
思い出すと、2つの同じタイプのtaskletsが同時に実行することはできません.したがって、同じタイプのtasklets間で共有されるデータは保護する必要はありません.しかし、データが異なるタイプのtasklets間で共有されている場合は、データにアクセスする前にスピンロックを取得する必要があります.1つのプロセッサのtaskletが別のtaskletに奪われないため、後半部をオフにする必要はありません.
データがソフトブレークダウン間で共有されている場合は、ロック保護を使用する必要があります.2つの同じタイプのソフトブレークが同時に複数のプロセッサで実行できるためです.1つのソフトブレークは、同じプロセッサで実行されているもう1つのソフトブレークを奪うことはありません.したがって、後半部をオフにする必要もありません.

読み書きスピンロック

ロックの使用は、読み取りパスと書き込みパスに明確に分けることができる場合がある.たとえば、更新と検索を同時に行うチェーンテーブルを考えます.チェーンテーブルが更新(書き込み)されている場合、他のスレッドがチェーンテーブルの書き込みまたは読み取りを実行していないことを確認することが重要です.つまり、書き込み操作ではアクセスが反発します.一方、チェーンテーブルが検索(読み取り)されると、他のスレッドがチェーンテーブルを書いていないことを確認するだけです.つまり、他のスレッドがチェーンテーブルを書いていない限り、複数のスレッドが同時にチェーンテーブルを読むのは安全です.このような場合、このチェーンテーブルは、読み書きスピンロックを使用して保護することができる.
読み書きスピンロックはスピンロックの変種であり、読み書きロックと書き込みロックを含むと理解できる.1人以上の読者が同時にリードロックを持つことができる.書き込みロックは、逆に、最大1人の書き込み者にしか持たれない(他の読者もいない).読み書きロックは、共有/排他ロックとなることもある.
読み書きロックの使用方法は次のとおりです.

DEFINE_RWLOCK(mr_rwlock);

// 
read_lock(&mr_rwlock);
/* critical section (read only) ... */
read_unlock(&mr_rwlock);

// 
write_lock(&mr_rwlock);
/* critical section (read and write) ... */
write_unlock(&mr_lock);

完全な読み書きスピンロック方法は次のとおりです.

read_lock()               //Acquires given lock for reading

read_lock_irq()           //Disables local interrupts and acquires given lock for reading

read_lock_irqsave()       //Saves the current state of local interrupts, disables local interrupts, and acquires the given lock for reading

read_unlock()             //Releases given lock for reading

read_unlock_irq()         //Releases given lock and enables local interrupts

read_unlock_irqrestore()  // Releases given lock and restores local interrupts to the given previous state

write_lock()              //Acquires given lock for writing

write_lock_irq()          //Disables local interrupts and acquires the given lock for writing

write_lock_irqsave()      //Saves current state of local interrupts, disables local interrupts, and acquires the given lock for writing

write_unlock()            //Releases given lock

write_unlock_irq()        //Releases given lock and enables local interrupts

write_unlock_irqrestore() //Releases given lock and restores local interrupts to given previous state

write_trylock()           //Tries to acquire given lock for writing; if unavailable, returns nonzero

rwlock_init()             //Initializes given rwlock_t

Linux読み書きスピンロックについて重要なのは、読者の優先度が書き込み者より高いことです.リードロックが読者によって所有され、ライターが反発のアクセスをスピンして待っている場合、次の読者がリードロックを取得することは成功します.スピンしているライターは、すべての読者がリードロックを解除してからライトロックを持つことができます.そのため、多くの読者が待っている執筆者を飢えさせます.使用時にはこの点を考慮しなければならない.

しんごうりょう

Linuxの信号量は睡眠ロックです.タスクが信号量を取得しようとして失敗すると、タスクは信号量の待機キューに配置され、スリープに入ると、プロセッサは他のコードを実行するために解放されます.信号量が取得可能になると、待機キューのタスクが起動して信号量を取得します.
信号量の睡眠行動から興味深い結論を見つけることができます

競合するタスクは、ロックが取得可能になるのを待つ間に睡眠中であるため、信号量は、ロックを長時間保持する必要があるシーンに適している.

とは対照的に、信号量は、睡眠、メンテナンス待ちキュー、起動タスクのオーバーヘッドがロックの保有時間を超えやすいため、ロックを保持する時間が短いシーンには適していない.

競合ロック時にスレッドがスリープするため、信号量はプロセスコンテキストでのみ使用できます(中断コンテキストではスケジューリングが実行できないため).

信号量を持っている間に睡眠をとることができますが、別のプロセスが同じ信号量を取得した場合、デッドロックは発生しません.

信号量を取得する前にスピンロックを持つことはできません.信号量を取得すると睡眠に入る可能性があり、スピンロックを保持すると睡眠できません.

カウントと二値信号量

参照Posix信号量.1つは応用層の信号量であり,1つはカーネル中の信号量であり,両者はよく似ている.

信号量の作成と初期化

静的に宣言された信号量は、次のように作成されます.

struct semaphore name;
sema_init(&name, count);

静的に2値信号量を作成する方法は、次のとおりです.

static DECLARE_MUTEX(name);

動的に作成される2値信号量の初期化方法は、次のとおりです.

init_MUTEX(sem);

しようしんごうりょう

関数down_interruptible()は、1つの信号量を取得しようと試みる.信号量が取得できない場合、プロセスはTASK_INTERRUPTIBLE睡眠状態に入る.タスクが睡眠中に信号を受信すると、タスクは起動され、down_interruptible()は-EINTRに戻ります.
関数down()は、睡眠のタスクをTASK_UNINTERRUPTIBLE状態に設定し、睡眠のタスクは信号を無視します.通常はそうしたくないので、down_interruptible()関数はもっとよく使われています.down_trylock()を使用して、ブロックされていない信号量を取得することができます.
1つの信号量を解放し、up()を呼び出す.1つの例は次のとおりです.

/* define and declare a semaphore, named mr_sem, with a count of one */
static DECLARE_MUTEX(mr_sem);

/* attempt to acquire the semaphore ... */
if (down_interruptible(&mr_sem)) {
/* signal received, semaphore not acquired ... */
}

/* critical region ... */

/* release the given semaphore */
up(&mr_sem);

完全な信号量の方法は以下の通りです.

sema_init(struct semaphore *, int)      //Initializes the dynamically created semaphore to the given count
  
init_MUTEX(struct semaphore *)          //Initializes the dynamically created semaphore with a count of one

init_MUTEX_LOCKED(struct semaphore *)   //Initializes the dynamically created semaphore with a count of zero (so it is initially locked)
  
down_interruptible (struct semaphore *) //Tries to acquire the given semaphore and enter interruptible sleep if it is contended
  
down(struct semaphore *)                //Tries to acquire the given semaphore and enter uninterruptible sleep if it is contended
  
down_trylock(struct semaphore *)        //Tries to acquire the given semaphore and immediately return nonzero if it is contended
  
up(struct semaphore *)                  //Releases the given semaphore and wakes a waiting task, if any

リードライト信号量

信号量との関係と読み書きスピンロックとスピンロックの関係は類似している.使用方法の省略、