TECHNOLOGY LINUX KERNEL

【第15回】元東大教員から学ぶLinuxカーネル「ブロックレイヤ」

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

前回を読んでいない方はこちらからどうぞ.

第14回Linuxカーネル
【第14回】元東大教員から学ぶLinuxカーネル「ファイルシステムとクラッシュ整合性」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. Linuxカーネルの記事一覧はこちらからどうぞ. 今回のテーマはファイルシステムとクラッシュ整合性です. 特に,Linuxカーネル ...

続きを見る

Linuxカーネルの記事一覧はこちらからどうぞ.

Linuxカーネル
元東大教員から学ぶLinuxカーネル

こういった私から学べます. Linuxカーネルとは,C言語で開発されたオープンソースのOSです. Linuxカーネルは主に以下のコンピュータで広く利用されています. スーパーコンピュータ サーバ An ...

続きを見る

今回のテーマはブロックレイヤです.

ブロックレイヤでは,HDD/SDD等のデバイスの読み書きを調停することがわかります.

ブロックレイヤ

file system

Linuxカーネルにおけるデバイスの種類は以下になります.

  • キャラクタデバイス(character device):シリアルポート,マウス,キーボード等のようにバイトのストリームとして順次アクセスされるデバイスです.ストリームアクセスなので,例えばキーボードでテストを打つ場合は'h','e','l','l','o'となります.比較的シンプルです.
  • ブロックデバイス(block device):HDD/SSD,CD/DVD,フロッピーディスク等のようなランダムアクセスによりデバイスが特定の位置にシークすることができます.キャラクタデバイスより複雑で性能が重要になります.

ブロックデバイスのような複雑で性能が重要が部分において,Linuxカーネルではブロックレイヤにより管理します(上図).

Linuxカーネルのブロックレイヤは以下の要素で構成されていますので,それぞれ解説していきます.

ブロックデバイスの構造はセクタとブロックから構成されます.

  • セクタ(sector):ブロックデバイスのアドレス指定可能な最小単位です.デバイスの物理的性質は,ハードセクタとデバイスブロックになります.一般的にセクタサイズは512バイト(CD-ROMは2Kバイト)です.
  • ブロック(block):ファイルシステムのアクセス単位で,ファイルシステムブロック,I/Oブロックのことを表します.ブロックサイズは,セクタの倍数(デバイスの制限)かつページの倍数(カーネルの制限)になります.ブロックサイズの多くは4Kバイトまたは8Kバイトです.

HDDのセクタとブロックは以下の動画がわかりやすいです.

バッファとバッファヘッド

バッファでは,ブロックがメモリに格納されます.

バッファヘッドは,バッファのメタデータのことです.

linux/include/linux/buffer_head.hのbuffer_head構造体でバッファヘッドを管理します.

buffer_head構造体でバッファの状態を管理するb_stateメンバ変数は以下の列挙になります.

BIOレイヤ:bio構造体

block io

bio構造体は,アクティブなブロックI/O操作のための基本コンテナです(上図).

各々のバッファはセグメントに分割され,メモリ上で連続である必要はありません.

ここで,セグメントとは,バッファの中で連続したメモリのチャンク(まとまり)を意味します.

linux/include/linux/blk_types.hにbio構造体があります.

linux/include/linux/bvec.hにbio_vec構造体とbvec_iter構造体があります.

bio structure

bio構造体,bio_vec構造体,bvec_iter構造体の関係は上図になります.

リクエストレイヤ:request_queue構造体

ブロックデバイスは,保留中のI/O要求を格納するためにリクエストキューを保持します.

リクエストはファイルシステムのような高レベルのコードによってキューに追加されます.

ブロックデバイスドライバによってキューから要求が取り出され,デバイスに送信されます.

linux/include/linux/blkdev.hで定義されているrequest_queue構造体でリクエストキューを表現します.

1つのリクエストは,request構造体で表現されます.

連続した複数のディスクブロックに対して操作できるため,1つ以上のbioオブジェクトで構成されます.

I/Oスケジューラ

リクエストが到着したときにディスクに直接送るのは最適とは言えません.

ランダムアクセスが増えるため,カーネルはディスクシークを可能な限り減らそうとします.

そこで,カーネルはリクエストキュー内のI/Oリクエストを結合し,並べ替えます(マージとソート).

マージとソートのルールは,I/Oスケジューラにより定義されます.

Linuxには複数のI/Oスケジューラモデルが実装されています.

プロセススケジューラがCPUを仮想化するように,I/Oスケジューラはディスクを仮想化します.

シングルキューI/Oスケジューラ

シングルキューI/Oスケジューラを紹介します.

現在ではシングルキューI/Oスケジューラはサポートされていませんが,I/Oスケジューラの歴史を知る上で有用です.

Linus Elevator

Linus Elevatorは,Linuxカーネルのバージョン2.4までのデフォルトのI/Oスケジューラです.

次のリクエストがキューのどこに追加されるべきかを定義します.

  • フロントマージ,バックマージ
  • ソート挿入

Linus Elevatorの目標は,ディスクシークの最小化とグローバルスループットの最大化です.

Linus Elevatorのアルゴリズムは以下になります.

  1. 隣接するディスク上セクタへのリクエストがリクエストキューにある場合,既存のリクエストと新しいリクエストは1つのリクエストにマージされます.
  2. リクエストキューの中のリクエストが十分に古い場合,新しいリクエストは他の古いリクエストの飢餓状態を防ぐために,リクエストキューの最後尾に挿入されます.
  3. セクタ単位で適切な場所がリクエストキューにあれば,新しいリクエストはそこに挿入されます.これによって,リクエストキューはディスク上の物理的な位置でソートされた状態に保たれます.
  4. 最後に,そのような適切な挿入位置が存在しない場合,リクエストはリクエストキューの最後尾に挿入されます.

Linus Elevatorの課題は,その目標であるディスクシークの最小化とグローバルスループットの最大化により,飢餓状態を引き起こす可能性があることです.

書き込みにより読み込みが飢餓状態になってしまうため,以下の項目を検討する必要があります.

  • バッファページキャッシュでI/O操作をバッファリング
  • 書き込み操作はページキャッシュにバッファリング(非同期処理)
  • ページキャッシュがなくなったときの読み込み操作は即座に処理されるべき(同期処理)
  • 読み込みの遅延はシステムにとって重要なため,読み込みの飢餓状態を最小にする必要

Deadline I/O Scheduler

Deadline I/O Schedulerは,グローバルスループットを最大化しつつ,公平性を確保することを試みるI/Oスケジューラです.

各リクエストにはデッドラインと呼ばれる有効期限が設定されています.

例えば,読み込みは「現在時刻 + 0.5s」,書き込みは「現在時刻 + 5s」等です.

Deadline I/O Schedulerは以下の動画がわかりやすいです.

Anticipatory I/O Scheduler

Anticipatory I/O Schedulerは,Deadline I/O Schedulerのスループットを向上させるI/Oスケジューラです.

Anticipatory I/O Schedulerの特徴は,予期ヒューリスティック(Anticipation Heuristic)を利用することです.

すぐにシークバックするのではなく,アプリケーションが他のI/Oリクエストを送るのを期待して,数ms待ちます.

Complete Fair Queuing(CFQ)I/O Scheduler

Complete Fair Queuing(CFQ)I/O Schedulerは,プロセス単位のリクエストキューを持つI/Oスケジューラです.

プロセスによって提出された同期要求をプロセスごとの多数のキューに入れ,その後,各キューがディスクにアクセスするためのタイムスライスを割り当てます.

タイムスライスの長さと,リクエストキューが処理できるリクエストの数は,与えられたプロセスのI/O優先度に依存します.

Noop I/O Scheduler

Noop I/O Schedulerは,シーケンシャルなリクエストを結合する以外には特に何もしないI/Oスケジューラです.

フラッシュカードのような真にランダムなデバイスに使用されます.

マルチキューI/Oスケジューラ

マルチキューI/Oスケジューラを紹介します.

【デフォルト】Multiqueue Deadline I/O Scheduler

Multiqueue Deadline I/O Schedulerは,Deadline I/O Schedulerのマルチキュー版のI/Oスケジューラです.

Linuxカーネルでデフォルトで利用されています.

Budget Fair Queuing(BFQ)I/O Scheduler

Budget Fair Queuing(BFQ)I/O Schedulerは,各プロセスにI/Oバジェットを割り当て,多くのヒューリスティックと組み合わせることで,特に低速なデバイスのI/Oレスポンスを大幅に改善するI/Oスケジューラです.

Budget Fair Queuing(BFQ)I/O Schedulerは,HDDを使用するユーザにもメリットがありますが,低速のSSDを使用する場合にもメリットがあります.

例えば,スマホやタブレットなどのデバイスです.

Budget Fair Queuing(BFQ)I/O Schedulerの解説動画はこちらです.

Kyber I/O Scheduler

Kyber I/O Schedulerは,I/Oリクエストを同期リクエストと非同期リクエスト,つまり読み込み用と書き込み用の2つの主要なキューに分けるI/Oスケジューラです.

読み込み要求を発行したプロセスは,通常その要求が完了しデータが利用可能になるまで処理を進めることができないため,このような要求は同期型とみなされます.

一方,書き込みは,後で完了する可能性があるため,書き込みを開始するプロセスは,通常は書き込みが実際にいつ行われるかを気にしません.

そのため,書き込みよりも読み込みを優先させるのが一般的ですが,書き込みができなくなるようなことはありません.

Kyber I/O Schedulerのキーアイデアは,ディスパッチキュー(デバイスに直接操作を送るキュー)に送られる操作(読み込みと書き込みの両方)の数を厳しく制限し,これらのキューを比較的短い状態に保つことです.

ディスパッチキューが短ければ,あるリクエストがキューで待機している間の時間(リクエスト単位の遅延)も比較的短くなります.

そのため,より優先度の高いリクエストを素早く完了させることができます.

None I/O Scheduler

None I/O Schedulerは,Noop I/O Schedulerのマルチキュー版のI/Oスケジューラです.

Noop I/O Schedulerと同様に,None I/O Schedulerはフラッシュカードのような真にランダムなデバイスに使用されます.

I/Oスケジューラの設定方法

I/Oスケジューラの設定方法を紹介します.

I/Oスケジューラはデバイスごとに選択できます.

プライマリディスク(sda)で現在利用可能なI/Oスケジューラと利用しているI/Oスケジューラは以下になります.

  • mq-deadline:Multiqueue Deadline I/O Scheduler
  • none:None I/O Scheduler

※[mq-deadline]と[]があるのは,現在Multiqueue Deadline I/O Schedulerを利用しているという意味になります.

none(None I/O Scheduler)に変更したい場合は,以下のコマンドを入力して下さい.

利用しているI/Oスケジューラを確認すると,[none]になっていることがわかります.

また,I/Oスケジューラは,Linuxのブート時にカーネルパラメータ「-elevator=<value>」として選択できます.

valueは,私のLinuxカーネルではmq-deadline,noneのいずれかになります.

ここで,私のLinuxカーネルでは,Budget Fair Queuing(BFQ)I/O SchedulerとKyber I/O Schedulerは無効になっているので注意して下さい.

Linuxカーネルのコンフィグのオプションで有効にしてビルドすれば利用できます.

Linuxカーネルのビルド方法を知りたいあなたはこちらからどうぞ.

C言語 Linuxカーネル ビルド
【C言語】Linuxカーネルのビルド方法と新しいシステムコールの実装方法

こういった悩みにお答えします. こういった私から学べます. 目次1 Linuxカーネルのビルド方法1.1 GRUBを編集して起動するLinuxカーネルを指定1.2 Linuxカーネルのビルド環境の構築 ...

続きを見る

まとめ

今回はブロックレイヤを紹介しました.

ブロックレイヤは,BIOレイヤ,リクエストレイヤ,I/Oスケジューラで構成されていることがわかりました.

ブロックレイヤを深掘りしたいあなたは,以下を読みましょう!

以下の動画もおすすめです!

最後まで読んで頂きありがとうございました.

LinuxカーネルはC言語で書かれています.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

次回はこちらからどうぞ.

第16回Linuxカーネル
【第16回】元東大教員から学ぶLinuxカーネル「ソケット通信(TCP/UDP/IP)」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. Linuxカーネルの記事一覧はこちらからどうぞ. 今回のテーマはソケット通信(TCP/UDP/IP)です. 本記事では,以下を習得 ...

続きを見る

-TECHNOLOGY, LINUX KERNEL
-, , , , , , ,