はじめに

私はUniversity of the People という無償のonline大学(アメリカ)に行ってます。授業はすべて英語ですがレベルはかなり低く、たぶん40万くらいでアメリカのBachelor of Degreesという学士がもらえます。それが何の役に立つかはその人次第ですが、自分はただ「大学を卒業したと言いたい」ためにやってます。お金があればもっといい大学を選びましたが、当時手取り17万でその選択肢はありませんでした。

さて、そのCS(computer science)でOSの授業を取りました。それが難しく面白かったので、忘れないようにここにまとめたいと思います。9週間のクラスで、明日から8週目。テキストを読むのが追いつかなくて半分以上ジャーナル出せていないので、理解度は推して知るべしです。わかっていることわからないことを整理するためにこの記事を書きます。

教科書

メモリはChapter 12-24. 思ったより濃くてびっくりしました。

わかっていないこと

CPUの話が混ざってくるため、OS, CPU(MMU/TLB), RAM, Swapの垣根がよくわからなくなっている。
どうしても普段使うLinuxに紐づけて考えたいので、pseudoな理想論が混ざってよくわからなくなっている

はじまり

Chapter 12より前のお話

序盤はCPUの話がメイン。その中で重要なことは

すべてのinstruction(CPUへの命令、計算内容、つまりアプリのコード)はメモリに入れる必要がある
physical memoryを直接扱わず仮想メモリとして扱う。（ざっくりいうと）OSから見てハードウェアはすべて仮想的なフィルタを通して見る。ハードウェアはすべてVM扱い。linuxのkernel parameterに vm_ という名前が多いのはそのせい。ESXi/KVMのVMじゃなくて、ハードウェアがマシーンで、それをヴァーチャルにしたからVM. この授業でVMというとすべてそっちの話し。個人的にはvirtualなH/WということでVHWと呼びたい。weeek 1-2あたりでその2つのVM、contextをはっきりさせる課題が出された。うまい。なぜvmにする必要があるのかも教科書の前半にあるので、興味があればぜひ。

ここらへんの話とか面白いです。

niceしないデフォルトでprocess priorityがどうなるかの基本概念。SolarisとFreeBSDはだいぶちがうらし。 pic.twitter.com/Rhg8rq8MUi
— くじ@uturned (@uturned0) December 3, 2020

Chapter 13 Address Spaces code

OSがメモリ管理すると楽だよね、という話。開発者が他のprocessが使ってるメモリ領域を気にするなんてやってられない、だからやるんだよ。
address spaceはstackを前に、heapを後ろに配置する。真ん中は未使用領域で、中心に向かって領域を広げて使っていく。この違いはいまいちよくわかってない。

物理メモリを直接扱わず仮想メモリ（diskに置くRAMのことじゃなくて、RAM自体を仮想的に見るコンテキスト）にするのは、例えばメモリ1Gしかなくても2G以上のアプリ動かしたいじゃん。だったら仮想メモリ使うしかないよね、的な説明。

そのとき、物理メモリと仮想メモリのアドレスは違っちゃうよね。この差異がすべての始まり。

ゴールは３つ

開発者(process)にメモリのことを気にさせない
効率的に管理する（例えば4Gのメモリ管理するのに4Gの変換テーブル持ってたらそれで終わっちゃうよね）
セキュアにする(Aが使ってる領域をBに消されたらやばいよね的な)

Chapter 14 Memory API

stackは C-langで int x; としたときに automaticに 確保される領域。

Cのmalloc(), free()の話。

intでもdoubleでも適切な領域を確保する。free()はリリースする。
processが死ねば、領域はすべて自動的に開放される。これもOSの役目。

そこらのOSに「メモリちょうだい」とか頼む関数を API と呼ぶ。
OSが提供するAPI、という意味。

Chapter 15 Address Translation

ここから混乱が始まる。物理アドレスと仮想アドレスの変換話。「論理アドレス」という言葉は曖昧なので自分は使わないし、教科書にもほとんど出てこなかった気がする。

https://t.co/gRjm6vMOIiデジタル用語辞典では「論理アドレスから物理アドレスへの変換」と言っているので、 *論理アドレス* を仮想側のアドレス（programから見える方) として使っているhttps://t.co/MTt26Ofmti
— くじ@uturned (@uturned0) December 24, 2020

アセンブリが出てくるので辛いが、その前のclass(名前忘れた、CS1105的なのだったかな）で触ってるのでなんとなく読んでいく。
アセンブリが何をしてるかって言うと、CPU - レジスタ - メモリの間のバケツリレーを表している。aをbにcopyしたい場合、aをレジスタに入れる。レジスタをbに入れる、ということをしていく。そのレジスタが eaxだったりebxという名前だったりする。たぶん。

OSは起動時にpage tableを作る。ここで物理メモリの容量に合ったテーブルができるので、OS起動中のメモリ容量変更ができない理由なんだと思う。そこでinitializeがされる。kernelの大事な領域(trap, system call handler etc)が確保される（これは他の章だったかな）

興味深かったのは役割の橋渡しフロー図で、ハードウェアがOSとprogramの間にいること。hw, os, programかと思ったらos, hw, programなのね。
OSが命令し、CPUが演算し、結果をprogramに返す。programが必要に応じてsystem callでOS経由の命令を出す。

context switchをするためにOSがtimerを使ってprocessのstop/restartをする。そのたびにCPUのレジスタはprocess固有の内容に入れ替えられる。

internal flagmentation

Linuxではpage sizeが4Kに固定されている。1byteのデータがほしくても4KB使ってしまう。このムダをinternal flagmentationと呼ぶ。これ、後々度々出てくる。

Chapter 16 Segmentation

segmentation fault よく見るよね、あれは正しくないアドレスが指定された時に出る。例えばstart:0 size:8 の領域がある時にstart:5のアクセスが来ると、それはデータの中ではあるけど、スタート地点として正しくないのでfaultされる、的な。たぶん。このstart地点のことをoffsetと呼ぶ。たぶん。

各メモリ領域にはメタデータ的なエリアがあり、protection bitなどがある。r/w権限のチェックができたりする。

process Aは1G使う。 B は2G使う。このとき、メモリの分割最小単位は何にするか？という話。ここらへん混乱して何度も教科書読んだ。

結局、この後出てくるpagingと比較するとわかりやすい

Segmentaion: 動的にpage sizeを変える
Paging: 固定サイズ(Linuxなら4K)にする

最初はsegmentationをpagingの中にある1機能的な捉え方をしてたので超混乱した。

メモリ管理の勉強混乱してきた。英語文献の充実度はすごい。
Paging allows the memory to be divided into fixed sized block whereas the segmentation, divides the memory space into segments of the variable block size.https://t.co/jaRlt8GpoY
— くじ@uturned (@uturned0) December 28, 2020

どちらにもPros and Consはあるが、segmentationはオーバーヘッドが大きくPagingが主流みたい。
アドレスのスタート地点がバラバラだと、頭からnodeを追っていかないといけなかったり、後述するpaging / buddy systemの2本木構造（高速fetch）ができなかったりする。
ただ必要な分しか確保しないから、internal flagmentionが起きないのは利点だよね。
でもその代償として external flagmentationが起こる。例えば1K, 3K, 2Kの領域がポツポツと飛び飛びに空いたとしよう。並べて6Kの領域にしたいけど、もうどこにも連続した空きがない場合、じゃあ、1K使ってるところを入れ替えさせてもらおう的な・・・1Kのやつどこにいる？　結果、全部が入る場所を探すのは大変だ。

ん？使ってない場所を探すのってどうやるんだ？→次の章へ

Chapter 17 Free Space Management

この章は面白かった。未使用領域をOSはどうmanagementするのか？なるほど言われてみると、そうか、使っていないところを認識するには使っていないという知識を使う必要があるのだ。考えたことがなかった。

Slab allocatorやBuddy allocator(Linuxで使われている。 cat /proc/buddy* してみて)の話が出てくる。

malloc(サイズ) で容量を指定するが、free(変数名)だけでサイズは不要。これはアロケータが容量をテーブルに持っているからできる。

1Mの領域くれと言われ、複数の領域が空いている時allocatorはどうやってそれを選ぶ？ best hit = 全部なめて、最小限で済む領域を返す。 worst fit = いっちゃんでかい領域を使う。それなら入りやすそうだね！って、非効率的だからworstなのね。First hit = 最初に見つけた十分な領域を使う。とかまあいろいろ。

Buddy allocator
2のn乗の二本探索木で空き領域を記録。64byteメモリだったらその下に32byte * 2 がぶら下がる。片方の32Bがusedで、requestが32byteだったら、もう片方の32byteに賭けるしかない、的な判断がしやすい。

buddyもslab allocatorもそうだけど、問題はscalingに弱いこと。途中で物理メモリが増減したら、buddyなら二本木が破綻しちゃうね。

glibc allocatorがreal worldだとの紹介だけあるが、そこまでまだresearchできてない。

とにかくアロケータは複雑で色んなものがあって、すげーんだぜ。

Chapter 18 Introduction to Paging

pagingの話。固定サイズの領域だと高速にアドレス変換しやすいね。

メモリアドレスの変換計算がまあ苦手だった。0x011234 はVPN(Virtual page number) と offset に分けられる。 VPN=01 offset=1234
変換テーブルには VPNの変換がある。例えば 01が仮想アドレスのとある丁目で、それは物理の32丁目に対応するてきな。offsetは番地で、ここは変換されない。仮想アドレスだと1丁目1234番地が、物理では32丁目1234番地になる、的な。

例
Linuxのpage sizeは4K固定。
メモリが128Kなら、page数は 128/4 = 32pages必要ということになる。
32をbinaryで表すと(2進数にすると) 2**5 = 5bit 必要。要求されたアドレスの上位5bitをアドレス変換し、残りはoffsetとしてそのまま物理アドレスへGO.

ここでいくつか追加の判定用bitが紹介される。

valid bit: 未使用領域はinvalidになってるので、想定と違うとOSにtrapを投げる。OSはprocessを殺す、的な。

dirty bit : 書き換えがあると立つ。後の Chapter: page replacementで出てくるが無駄なpagingを防ぐなどの用途に使う

どこの章か忘れたのでここに書くけど、protection bitは大事。
他のprocessなら読めない。kernelのなら読めない。2018年（だっけ）のspecture/heart breed 問題で、kernelとuser processのメモリ空間は完全に分離された。これ、日本語に多いkernel 2.6あたりの文献だと同じとこに入ってると書いてあるので要注意です。

Figure 18.7: A Virtual (And Physical) Memory Trace はまったく理解不能だった。

混乱は加速していく。この変換テーブルの話はOS+RAMの話だ。次の章でTLBが出て爆発する。

Chapter 19 Translation Lookaside Buffers

TLBは address-translation cache. メモリ内容をキャッシュするんじゃなくて、変換テーブルをキャッシュする。

大事だからもう一度いうよ！！

**TLBは address-translation cache. **

これは僕の勝手なsummarizeなんだけどこういうことだと思う、たぶん

通常時

program: cpuに命令変数xを見せろ
cpu: x の場所わからんおいOS、教えろや
os: 変換テーブル(RAMに置いてあるので遅い)だと2丁目5番地でさ
cpu: とってきたで

TLBがある場合

program: cpuに命令変数xを見せろ
cpu: なあTLB, x の場所知っとる？
tlb: さっきも来たピョン。2丁目5番地だピョン(cpu内にあるので超早い)
cpu: とってきたで

最初に「xがほしい」という情報を受け取るのはCPUなので、CPU内で「変換作業が」完結すると早い(TLB-hit)。OSに聞きに行くと遅い。RAMに取りに行くところは遅いが、それは仕方ない。もしかしたらCPUのレジスタの中にあったりしたら爆速で早い。
TLBになければTLB-miss. TLB-missを減らし、TLB-hitを高速に行う方法がpage replacementの永遠の課題につながる。

いやー、この記事書いてよかった。いろいろ理解できた。このsummarizeができるようになった。復習してよかった。余裕大事。今週はもう課題出し終わってるから焦らなくてよくて。余裕があると教科書の意味が理解できるな！！！！余裕大事だな！！！

Chapter 20 Advanced Page Tables

pagingをsegmentationとhybridにしたり、multi-level page tableを持つ話が出てくる。要は

page tableがでかくなるとfetchに時間がかかる
page tableが小さくなるとhitしない

この相反する問題をなんとかするために、小さいtable、ちょっと大きいtable, 大きいtable、みたいな多段構えにしてfetch早い→hitしやすいまで段階を作ろう的な話なんだと思ってる。余裕なくてじっくり読めてない。

linuxは4階層だったがkernel 3?4?あたりから5階層もできるようになってた気がする。

ここらへんでpage size変えてパフォーマンス測ろうとしてみて、このツイートをする。

Linuxのpage sizeって4Kから変えれないのか。MMUがそれで決まっちゃってるのか。でもCPUの中とOSを一緒にしないといけないのかしら。スピード考えれば当然そうだからそうなったのかな
— くじ@uturned (@uturned0) December 29, 2020

Chapter 21 Swapping: Mechanisms

あーswapね的な内容。メモリが足りないとHDD使うよ。遅いよ。でも仮想アドレスでよかったね！的な。

swapにも上限があるよ。だって、最初にaddress translation table作るでしょ？　そこが上限さ。

あーたしかに、となりました。

Chapter 22 Swapping: Policies

ここが面白かった。課題は「paging in/outを減らすためにOSは何がんばってる？」的なやーつ。ただ疲れたのでツイート抜粋でゴメ。

一言でいうと、未来さえわかれば最良の選択ができるが、当然不可能なので、「なんとなくこうなるんじゃないかな」を手持ちの情報から取捨選択してく、感じ。

メモリ不足を再現したらOOMはちゃんとstressを殺してる。OSはどうやってこのprocessを選んでるんだろうな。 pic.twitter.com/1PnfdvhU2W
— くじ@uturned (@uturned0) December 29, 2020

Optimal policyでは読み込み待ちの列にいるメモリアドレスは対象から外されていく(すぐに必要になることがわかっているため)。Linuxがそのpolicyかまだわからないけど、stressが確保した領域は一切の読み込みがされていないだろうから、kill対象として持ち上げられるのは納得がいく。
— くじ@uturned (@uturned0) December 29, 2020

やっぱりなとｗ
Unfortunately, as we saw before in the development of scheduling
policies, the future is not generally known; you can’t build the optimal
policy for a general-purpose operating system
— くじ@uturned (@uturned0) December 29, 2020

FIFOは超シンプルだけどいまいち
Comparing FIFO to optimal, FIFO does notably worse: a 36.4% hit rate (or 57.1% excluding compulsory misses). FIFO simply can’t determine the importance of blocks: even though page 0 had been accessed
a number of times, FIFO still kicks it out
— くじ@uturned (@uturned0) December 29, 2020

FIFOはcache sizeを増やしてもヒット率が上がるどころか下がることがありBelady’s Anomalyと呼ばれている。Randomも同様の様子。LRUはヒット率が変わらないか上がる。
— くじ@uturned (@uturned0) December 29, 2020

メモリ管理の文脈では「重要なアドレス」をpage outさせないことが大事だ。その「重要」というのは「大事なプロセス」という観点ではなく「どうせまた呼ばれるアドレス」になる。呼び出される頻度が高いものが重要ぽい。LRUのLeastというのはきっと呼び出し回数に対するLeastなんじゃないかな
— くじ@uturned (@uturned0) December 29, 2020

呼び出し回数はLFU(frequently)だった。LRUはRecentlyで、最近呼ばれたものは次もすぐ呼ばれる(for文の元arrayとかね）と信じるポリシー。Optimalと似た結果になる。
ここの章で出るのはこれだけか。あとはprefetchingとgrouping of writes, OOM killerだった。これでdiscussionかな。
— くじ@uturned (@uturned0) December 29, 2020

答えあった。メモリを大量に使ってるプロセスから殺すんだ。経験上のやっぱり感ｗ
Linux run an out-of-memory
killer when memory is oversubscribed; this daemon chooses a memoryintensive process and kills it, thus reducing memory in a none-too-subtle
manner.
— くじ@uturned (@uturned0) December 29, 2020

Chapter 23 Complete VM Systems

むかしの革新的なOS, VAX/VMSの話。あらゆる今も現役の技術が
1970年代にあった。

メモリの0番地は必ずinvalidになっている。なぜか？ programが間違ってundefined的な、0番地を読みに来る可能性があるからだ。これが null-pointer access だ。配列が0から始まるように、computerは0から始まる。なのに、実用性を考えて0を必ずinvalidにした。これはすごい判断だと思う。

demand zeroing

page-outがいるとき、zero書き込みまですると時間がかかる。mapping tableだけ書き換えて、実際のメモリ領域はそのままにしておく。
→ 「やっぱりまだ必要でした」のとき、data領域はupdate不要で再利用できる！
→「違うデータに使う(page-in)」とき、初めてzero書き込みする（というかたぶん新しいデータで直接上書きしたりしてんじゃないのかな？）

copy-on-write (COW for short).

page-outさせる候補からdirtyな領域を除く。cleanなところはさっと取り除けるが、dirtyはwriteしてからdiscardするので時間がかかる。
これには副次的な効果もあり、writeをある程度溜めておいて一気に書き込むほうが、disk側にとって都合がいい。細切れのリクエスト(e.g. 3, 11, 5, 9)より、一気にくれたほうが 3, 5, 9, 11の順で行くと早いな、的な判断ができるんじゃないだろうか（適当想像）

kernelのアドレス空間とuserのはまったく違う。kernelのは物理にdirect mapping (DMA) されてて早かったりする？的な？　ごめんあまり読めてない

huge pages
DBMSなどで使われている、page sizeを4K以上にするやーつ。ごめん見れてないし試してなんかまったくいない。理解してない。でも実際linuxで使えるぽいからいつか。

序盤の章で、programから見えるメモリ領域はかぶるということを知った。中身が同じprocess aとbを走らせて両方で使う変数 x のアドレスを見るとまったく同じ(Cent7で再現した)。実際はアドレス変換されて違う物理アドレスに入ってるんだけど、プログラムからは同じ場所にあるようにみえーる。ハッカーからすると、ようわからんくても2丁目3番地にクレカの番号が来る、とわかってれば便利そうだよね。ここの章でそれが出てきて、ハッカーは、呼び出されている関数のreturnが来る場所のメモリアドレスを自分のmaliciousなコードに流す。これをreturn-oriented programming (ROP)と呼ぶそうだ。quite brilliantだと褒められている。天才すぎる。

で、そのprogram固定な仮想アドレスがmacだとランダムになったりしている。security対策だ。

論理的には同じ場所にあるはずのrankが、てんでバラバラのアドレスにあることがわかる。これは、Mac OSXが「アドレス空間ランダム化(Address Space Layout Randomization, ASLR)」と呼ばれるセキュリティ技術を採用しているからである

へぇ！https://t.co/QhMt2yzTkf
— くじ@uturned (@uturned0) December 24, 2020

このアタックを return-to-libc attack と呼ぶ。防御策は address space layout randomization (ASLR) だ。

Meltdown And Spectreの話もここで出てくる。なぜ投機的実行をするのか？未来がわからないからだよ。投機的実行(speculative execution、これ覚えられない）は、"計算を早くしたい" というよりも 早くメモリ読みたい という欲求が生み出したんだとこの授業のおかげで飲み込めた。memory allocatorの延長線にいるんだ。

Chapter 24 Summary

ごめん読んでない

これは前半に遊んでたツイートのメモ。linuxのcacheを実際に触って見れる。おすすめ。

LinuxがPage cacheを使って高速化するのを体験してみる on @Qiita https://t.co/BiKbnwKP67
— くじ@uturned (@uturned0) December 22, 2020

Linuxの先読みキャッシング read_ahead_kb on @Qiita https://t.co/x1gd5pXr0H
— くじ@uturned (@uturned0) December 22, 2020

vmstat コマンドの buff と cache の違い [Linux] on @Qiita https://t.co/QEF3CZDOgC
— くじ@uturned (@uturned0) December 22, 2020

おわりに

rebootは世界を救う

とりあえず再起動するのは別に悪くないんやでって教科書も言ってます。twitterもfacebookもきっと定期再起動してるんや pic.twitter.com/zbB4uZzGUC
— くじ@uturned (@uturned0) December 2, 2020

はあ疲れた。この数週間まじで疲れた。私にメモリを増設してください。