は、Linuxカーネル

Question

にPIDハッシュテーブルを理解

ブック「の理解Linuxカーネル第3版」のこのセクションでは、代わりにPIDを見つけるために、プロセスのリストを検索すると、カーネルは4つのハッシュテーブルが導入されていることを説明してPIDの各タイプごとに1つ。

私が理解しているように、テーブルの各要素はPIDのハッシュです。しかし、それはどのようにして簡単に検索できるのでしょうか？たとえば、PIDを指定すると、4つのハッシュテーブルが存在するのは、すべてのPIDを照らして検索するのではなく、そのPIDタイプのハッシュだけで検索するほうが速いからです。また、なぜハッシュが役立つのでしょうか？シンプルな番号を検索するよりも、ハッシュを探しにくいのですか？

したがって、これらの4つのテーブルのいずれかのエントリは正確には何ですか？彼らはプロセス記述子ですか？私は彼らをそのように理解した。また、各プロセス記述子には、同じ状態の他の同様のプロセス、つまり同じグループと同じ状態にあるプロセスにリンクする構造があります。

これはこれですか？

Answer 1

カーネルは、すべてのプロセスをタスクリストに格納します。タスクリストは、環状の二重リンクリストです。リストの各要素が次の要素と前の要素へのポインタを持つことを意味します。最初のアイテムは最後のアイテムにリンクし、その逆も同様です。それは概念的には円と考えることができます。

各タスクの中には、興味のあるPID情報を保持するプロセス記述子があります。彼らが言っていることは、通常、あなたが殺そうとしているプロセスを見つけるためには、タスクリストあなたが探しているものが見つかるまで、各プロセスディスクリプタのPIDフィールドを調べます。メモリ内のどこにいなくてもPIDで直接参照することはできません。それがリンクのためのものです。そのため、タスクリストは連続したメモリ空間を占める必要はありません。再リンクするだけで簡単に挿入と削除を行うことができます。各プロセスは、ITがどこにあるかを知っています。そして、それはそれがそれが探しているプロセスを見つけるまでリンクをたどることがメモリ内の位置を使用することができます。

これは、リニアタイムサーチと呼ばれています。最悪の場合、N個の要素が与えられれば、結果を見つけるためにN回の操作が必要になります。そして、効率を説明するときには、常に最悪の場合を想定します。あなたが大量のデータを持っているかどうかを調べる際に、線形時間はかなり非効率的です。

彼らが言っていることは、あなたのPID（あなたの意図した目標に依存する）をハッシュ関数で入れて、あなたの結果の場所でテーブルをチェックし、正確にタスクリスト内のタスク。それは1つの操作です。衝突を緩和するのはハッシュ関数の仕事です。しかし、平均最悪の場合、それは一定時間と呼ばれています。はるかに高速。

単純な番号を検索することはありません。異種のメモリ位置にあるデータ構造をトラバースしています。 C配列を持っていた場合、それらは連続したメモリ空間のスタックにあらかじめ割り当てられています。その場合、配列のインデックス番号はすぐに必要なメモリのチャンクを示します。しかし、ここではそうではありません。これらのデータ構造は、静的でもなく、事前に割り当てられてもいません。だからあなたはメモリアドレスからメモリアドレスにジャンプする何らかの方法が必要です。これらのデータ構造が取り組んでいるものはどれですか。

私は物事をクリアすることを望む。

出典：それは一定の時間を持っているので https://en.wikipedia.org/wiki/Hash_table http://www.makelinux.net/books/lkd2/app01lev1sec1