Copyright (C) Ken'ichi Fukamachi, 2021-2025. CC BY-NC-SA 4.0
複数のプロセスがリソース(資源)を取り合う状態
スーパーの入場人数制限(競合状態の好例,右図)
これをモデル化したものがセマフォ(semaphore)(ダイクストラ,1965)
関数 確定 (商品) { 商品の在庫を -1 する // 在庫 -1 に成功できれば、このお客さんの商品を確保できている // このお客さんの購入品としてデータベースをアップデートなりする...}
if (操作してますフラグ == 0) { // 誰も操作してないなら 操作してますフラグ = 1 // 自分が操作します! 商品の在庫数を取得 商品の在庫を -1 する 操作してますフラグ = 0 // 操作終わりました!}
A if (操作してますフラグ == 0) { // プロセスAは操作してOKと思っているB if (操作してますフラグ == 0) { // プロセスBも操作してOKと思っているB 操作してますフラグ = 1 // 自分Bが操作します!B Bが在庫数を取得 // たとえば在庫数 = 100A 操作してますフラグ = 1 // 自分Aが操作します!A Aが在庫数を取得 // Aにも在庫数 = 100 と見えてしまうA 商品の在庫を -1 する // Aが在庫数を 99 に設定B 商品の在庫を -1 する // Bも在庫数を 99 に設定A 操作してますフラグ = 0 // 操作終わりました!B 操作してますフラグ = 0 // 操作終わりました!
A* if (操作してますフラグ == 0) { // プロセスAは操作してOKと思っているA* 操作してますフラグ = 1 // 自分Aが操作します!B if (操作してますフラグ == 0) { // Aが操作中Bは操作できない、のちほど再挑戦A Aが在庫数を取得 // 在庫数 = 100 を取得A 商品の在庫を -1 する // 在庫数を 99 に設定A 操作してますフラグ = 0 // Aは操作終わりました!B* if (操作してますフラグ == 0) { // プロセスBが再挑戦、操作できるようになったB* 操作してますフラグ = 1 // 自分Bが操作します!B Bが在庫数を取得 // 在庫数 = 99B 商品の在庫を -1 する // 在庫数を 98 に設定B 操作してますフラグ = 0 // Bは操作終わりました!
大昔はgiant lock (ジャイアントロック)、現代ではmutex(ミューテックス)を使います
ジャイアントロックの典型は「割り込みを禁止」する実装です
mutexを使い粒度をあげます
関数 HDDへの読み書き (HDD) { // もっとも大味なジャイアントロック版のイメージ 割り込み優先度をあげる // 他の割り込みをうけつけない HDDを読み書きする // HDDの読み書きだけが(排他的に)実行され続ける 割り込み優先度を下げる // 他の割り込みの受け付けを再開}
関数 HDDへの読み書き (HDD) { // mutex(を使うけれど単純化された大味)版のイメージ mutexの処理(「HDDを使ってます変数」だけをロック,他の仕事も平行処理が可能) HDDを読み書き mutexのロックを開放}
OS全体の利用効率や反応速度を上げるには、競合状態をさばく粒度を上げる必要があります
自力で書くのではなくOSの提供する機能を使うべきです
1 mutexでロックをかける 2 while (リソースを使っていますフラグ == 1) { // (mutexロック下で)使用中か?を確認 3 cv_wait(条件変数cv, mutex変数) // 条件変数cvで待つ(待つ間は休眠) 4 } // 注: whileを抜ける時はリソースが使えるようになった時, そしてmutexを再ロック済 5 リソースを使っていますフラグ = 1 // (mutexロック下で)フラグ=1 6 mutexのロックを外す 7 リソースを使う // デバイスドライバの処理本体を書くところ 8 mutexでロックをかける 9 リソースを使っていますフラグ = 0 // (mutexロック下で)フラグ=010 条件変数cvで待っているプロセスを起こす // 次に処理できるプロセスはスケジューラしだい11 mutexのロックを外す
memory mapped
IO mapped
メモリ上にデバイスアクセス用の場所
ポインタ操作でデバイスが制御できるため、 デバイスだけ特別あつかいをしない統一感のあるコードの書き方ができて綺麗
機種例
IO mappedもしくは port mapped
メモリは全てプログラム用、デバイスは別枠
実装例:Intel CPU
ポインタ *p; // 2バイト幅の変数へのポインタなので、p--すると2バイト減少することに注意ポインタpをHDDを制御できるアドレス(65280〜65291番地間)の一番上(65290)に合わせる*p-- = HDD上に書き込む場所の指定(セクタの番号)*p-- = メモリ上のバッファのアドレス*p-- = 読み書きするバイト数*p = コマンド// memory mappedの例: メモリ上の配置は以下のとおりで、アドレスは十進数表記に変更済65290 HDD上の場所の指定(セクタの番号)65288 メモリ上のバッファのアドレス(読み書きする場所、読み書きの方向はコマンド依存)65286 読み書きするバイト数65284 コマンド (読み/書きの指定)65282 デバイス側でエラーの理由を書き込む場所, READ ONLY65280 HDDのステータス(Drive Status Register, READ ONLY)
2.5インチのSATA HDD(左)と、 M.2 SSD(右側の銀色ヒートシンク下の板,よく見えないけど;-)
2.5インチのSSD(端子はSATA)、 見栄えは写真(左)のHDDと変わらない (-> ノートPCのHDDをSSDに入れ替えて高速化できる)
小さな磁石(N極とS極)で0と1を表現する媒体
YoutubeなどにHDDを分解して動作させている動画があるので、 それらを見た方がわかりやすいでしょう(-> 右の動画)
枯れた技術
コストパフォーマンスがよい
保存性能も予想以上に高い
ある程度の円盤の大きさは必要です(脚注1)
円盤を回しアームを動かすため
開放系
絶縁体の箱の中に電荷がある/なしで1/0を表現
書き込みや消去は電圧をかけて強引に絶縁体を越えて電荷を移動させます
(これがSSDを痛める原因の一つです)
大きく分けて二つの型がります
右図はフローティングゲート型。 箱内の電子量により基盤側に流れる電流が変化するので、 そこから値(1-3bits)を判断します
もうひとつチャージトラップ型というのがあり、TLCは両タイプの製品があります
微細化は限界
軽い、小さい
回転部品が無いので(HDDよりは)衝撃に強い
ランダムアクセスが得意(脚注1)
最近だいぶ安くなり実用的になりました(脚注2)
耐久性は(HDDほど)ない(脚注1)、wear levelingの性能が重要(脚注2)
動作原理の違いからくるデメリット。例:処理単位の大きさ、消去
コントローラ次第(脚注2)
容量単価、大容量性、長期保存性能という点で、 磁気テープが最強の保存媒体です
近年はLTFSという磁気テープ向けのファイルシステムも策定され使いやすくなりました!
ユーザとしては磁気テープよりAWS S3などにバックアップする時代でしょう
クラウド事業者などの裏側の話をすると
ランサムウエア対策にもなるので需要急増中(ここは個人/法人とわず)
SSDは万能ではありません
「新技術も特定の分野に秀でているだけで前時代の問題の全てを解決するわけではありません」
身の回りからHDDや磁気テープがなくなることはあるかもしれませんが、
クラウドの裏や業務用サーバでHDDや磁気テープがなくなることは(当面)ありません
Disks for Data Centers (Google, 2016)
Hyperscaler Storage (SNIA, 2016)
Y. Li et.al., “Facilitating Magnetic Recording Technology Scaling for Data Center Hard Disk Drives through Filesystem-Level Transparent Local Erasure Coding” (USENIX, 2017)
オンプレミスの業務用サーバの場合、 読み書きは図のように様々なシステムを経由して、 最終的にSSDやHDDに書きこまれます
図のような多段構造があります
主記憶装置 … メインメモリ
補助記憶装置
ファイル … 数字のバイト列を格納するもの
プロトコル
改行や空白(SPACEやTAB)を意味するコードを入れておき、 テキストを表示するプログラム(エディタやブラウザなど)が適切に表示
Q: 日本語は? A: UTF-8 (脚注)
HAMLETTo be, or not to be, that is the question,Whether 'tis nobler in the mind to suffer... 以下略 ...
ファイル=メタデータ+データ(本体)
ファイル操作の例
属性 | 備考 |
---|---|
ファイル名 | 文字列 |
ファイルの長さ | バイト数 |
所有者のID | uid(数字) |
所有者のグループ | gid(数字) |
ファイルモード | いわゆるpermission |
最終参照時刻 | unixtime |
最終更新時刻 | unixtime |
データ格納位置 | セクタ番号(群) |
表: メタデータの例
ファイルは本で、ディレクトリ(フォルダ)は本棚
本棚の中に本棚を作れます
Unixのファイルシステムの特徴
階層型ファイルシステム以外
ファイルをおさめる入れ物をUnix系ではディレクトリ、 Windowsなどではフォルダと呼びます (以下Unixの話をします)
ディレクトリは入れ子にでき、木構造を構成
Unixでは/で階層の区切りを表現します。 階層の一番上は/でrootと呼びます
Unixでは/で階層の区切りを表現します
階層の一番上は/でrootと呼びます
たとえば/usr/bin/viは図(の網線部の)ような階層をあらわしています
ファイルの位置を表現する/usr/bin/viのような表記をパス(path)と呼びます
相対パス … 作業中の場所からの相対表記
ディレクトリの移動はcdコマンドの引数にパスを書きます。 . (自分自身)と.. (一つ上,親ディレクトリ)は特別なパスです
/usr/bin/vi # #の右側はコメントですcd /usr/bin # /usr/binに移動して./vi # viを起動(/usr/bin/viの起動と同じ意味)cd .. # 一つ上に移動したので今いる場所は/usr./bin/vi # viを起動(/usr/bin/viの起動と同じ意味)
prompt> ls /altroot/ boot.cfg home/ libdata/ netbsd root/ tmp/bin/ dev/ kern/ libexec/ proc/ sbin/ usr/boot etc/ lib/ mnt/ rescue/ stand/ var/prompt> ls -l / ... 省略 ...drwxr-xr-x 2 root wheel 1024 May 12 22:15 bin/-rw-r--r-- 1 root wheel 172 May 12 22:15 boot.cfgdrwxr-xr-x 30 root wheel 2560 Oct 23 10:04 etc/ ... 省略 ...drwxr-xr-x 15 root wheel 512 Oct 20 09:59 usr/drwxr-xr-x 25 root wheel 512 Oct 8 21:12 var/permission ユーザ グループ サイズ 最終更新時刻 ファイル名もしくはディレクトリ名
HDDは回転する金属の円盤なので、その構造を意識した読み書きをすれば速くなるはず
たとえば、書きこむ際、 アームを極力動かさずにすむ配置を考え、 なるたけデータを同心円上に配置していきます
アームを直径方向には動かさず、円周に沿って読み書きするのが効率的です。 アームを上げて下げる必要がある場合は、上下の時間差と回転する分を考えてデータを配置しておきます
電源断などの非常事態からの復旧を容易にする工夫もあります
【注意】 これらは中途半端な状態にならない(一貫性を維持する)努力であって、 ハードウエア障害でデータがなくなることは避けられません
データの保存(確実な読み書き)はOSの最も重要な機能の一つです
障害対策の例
【運用】定期バックアップは基本
データにも参照の局所性があるので、よく使うファイルはストレージのごく一部です
SSD -> HDD -> 磁気テープの順に大容量ですが、その順に低速になります。 そこで、 まずはSSDに読み書きし、一ヶ月アクセスがないファイルはSSDからHDDへ移動し、 HDD上で3ヶ月アクセスがないファイルはHDDから磁気テープやAWS S3へ移動するといった運用が理想です(脚注2)
これも一種の多段キャッシュ構造です
レベル | 概要 | 冗長性 | 利用可能な最大容量 | コスト |
---|---|---|---|---|
0 | ストライピング:分散して書き込む | なし | 1 | 安価 |
1 | ミラーリング:2個のDISKに同じデータを書きこむ | あり | 1/2 | 高価 |
5 | データとパリティを書き込む | あり | (HDD数-1)/HDD数e.g.2/3 | やや高価 |
10 | RAID1群を作成後それらをRAID0で束ねる | あり | 1/2 | 高価 |
RAID 0 = ストライピング: 大容量かつ(HDDの並列動作で)高速化が可能ですが、HDDが1つ壊れるだけで全滅。 キャッシュなどの一時領域としては便利ですが、保存領域に使ってはいけません
RAID 1 = ミラーリング: 二つの HDD に同時に同じデータを書きこむ。 簡潔な理屈のため回路も簡単で信頼性が高いが、 HDDの半分しか使えない高価な手法。 読むときは2つのHDDから読みこむことで倍速が可
RAID 1のセットを作り、それらをRAID 0で束ねることで高速化と大容量化が可能
メリット: RAID 0と1のメリットのいいとこ取り
デメリット: RAID 1と同じでHDD数の1/2しか利用できない高価なところ
RAID 5 = RAID 1と0の妥協点とも言え、復旧するためのパリティデータを分散配置 (HDDが1台なら壊れても大丈夫、2台こわれたら全滅)。 パリティにHDD 1台分が使われますがRAID 1ほど高価な方法ではないため、よく見かけます。 例: 合計3台のHDDなら2個分、合計4なら3個分の容量が利用可能
RAID 6 = RAID 5 の拡張でパリティを二重にもつ方法です。 HDDの総容量はRAID 5より少なくなりますが故障には強くなります。 最近は 6 を見ることが多い気がします
Keyboard shortcuts
↑, ←, Pg Up, k | Go to previous slide |
↓, →, Pg Dn, Space, j | Go to next slide |
Home | Go to first slide |
End | Go to last slide |
Number + Return | Go to specific slide |
b / m / f | Toggle blackout / mirrored / fullscreen mode |
c | Clone slideshow |
p | Toggle presenter mode |
t | Restart the presentation timer |
?, h | Toggle this help |
Esc | Back to slideshow |