Operating System

1092-交大-作業系統總整與實作

Introduction

  • 作業量: 5
  • 考試量: 0
  • 整體難易度: 4.5
    (滿分 5 分)

交大資工有名的 OSDI，作業硬出名的
每兩周一個作業、沒有考試，從期初到期末就是在樹梅派上從零開始刻出一套有基本功能的 OS
作業部分歷年的 code 以及同學的 code 都會放在 github 上，他也不怕你看，因為不懂理論知識你也看不懂XD
由於之前大部分都是在偏上層做些 application 應用，這門課修起來真的是硬到不行
上課方式都是先看預錄的影片，上課時間討論影片的內容及問題
上課老師很會帶領大家一起思考討論一些作業系統的問題，整個上課的過程中就有點像是強者之間的交流(雖然我很菜…)
此門課對於 OS 基礎工不好的以及未來想到竹科科技業發展的會有相當大的幫助

單看本篇文所整理的一些課程內容是沒辦法感受到本門課的精隨
最精華的部分就是在痛苦的作業地獄以及 demo 作業時與 TA 之間的問答，以及上課過程中老師的引導及思考
TA 們也每個都強如鬼，demo 過程就是不斷的問答你的 code 怎麼寫、怎麼改、有沒有更好的做法
對於有熱忱的技術宅會覺得每次的交流都很過癮，醍醐灌頂就是這樣的感覺

因為本門課的內容真的蠻底層，還會摸到一點硬體跟組語，對於跟硬體搭不上邊還完全沒修過組語的我一個人奮戰就是巴著 TA 問問題
如果有紮實的將本門課的內容好好的學習完，對基本功一定有相當程度的提升
本門課的 loading 幾乎是其他課 1.5-2 倍左右，修了之後最好不要選其他太硬的課
整體難硬度剩下的 0.5 就是給在沒有考試而已 :)
另外，這門課在上的時候本來為曹教授，後來換教授開課後就不確定課程內容是否相同

附上作業連結: Link
自己的作業: Github

Week1 - Before OSDI

OS 根本上就是支巨大且複雜的程式、Application

開發 OS 與大型軟體程式的開發相似但牽涉到領域知識太多，基本上幾乎是把 CS 學過的各種知識彙整並應用
在念 CS 領域大部分也都會有寫 OS 的人通常都是各種大神才能應付的領域
這門課程會將許多在學習 CS 過程中大家較為模糊的區塊以及概念拿出來討論
小弟在寫這篇文章的時候也會跟著每周上課進度以及 lab 的進度做撰寫，如果有錯誤的部分也歡迎大家一起在留言區討論

在大型的軟體與程式開發之前需要大致上了解一下幾個區塊

Kernel Space and User Space

我們先前在 OS 的課程中學過，程式的執行區塊會分為 Kernel space 以及 User space ，一般撰寫的 code 都會在 User space 中編譯並執行
而本門課的內容是 OS code 的撰寫，因此大多時候都會在 Kernel space 進行作業

Kernel Space 可以想成在電腦執行工作的管理階層，擁有較大的權限、處理電腦運行過程中所需要決定的事項
管理階層也有他們需要執行的工作，例如:決定工作地點(管理記憶體)、安排工作順序(Schedule)…

User Space 的權利較小，主要執行一般應用程式，如果需要使用到系統資源等功能就須使用 System call 請 Kernel 代為執行

因此 Kernel Space 會有自己的 Library 在撰寫時不會用到 User Space 的 Library 在 User Space 寫 code 也是相同的情況

Host computer and Target computer

Host computer定義為目前你正在寫 code 的電腦，要將寫完的 code 可以在 Target computer 上 run 起來
這個 Target computer 不一定要是實體的電腦，也可能是 Simulator, VM, … 等模擬環境

Editor

我想這個大家應該很熟悉，指的是單純的編輯器，在寫 code 的時候需要有一些能夠寫 code 地方，就是透過 Editor，也算是 IDE 的前身
常用的 IDE 例如: Visual Studio Code, Code Blocks, InteliJ…
常用的 Editor 例如: Notepad++, Vim, …

Editor 如同 OS 一樣也是由他人透過程式寫出來的，因此也會有它的 source code 以及編譯他的 Compiler

Compiler

大部分情況下我們所寫的 source code 是屬於高階語言(C, Java, …)
我們必需透過編譯器(Compiler)將程式碼轉成 Low level 的 Machine code 才能夠讓電腦有辦法看懂，例如: gcc 編出來的 .o 檔
在 Compile 前也有可能會有 Preprocessor 的參與，以 C 的 Preprocesser 來說就是處理 # 開頭的 code

Assembler

組合語言的 Compiler ，將組合語言編成 Machine code
組合語言本身就較高階語言 Low level 些，處理的工作也較為底層，但一樣要轉為最後的 Machine code 再執行

Library

在寫 code 過程中有些重複常用的功能就會被包成 library 方便使用
因此 library 可以視為已經先幫你編好功能的 code 可以讓你自由使用
例如: C 語言常用的標準函示庫 stdlib.h

Linker

當 source code 被編成 .o 檔之後將要透過 Linker 將各個零散的 .o 檔以及用到的 library link 在一起產生最後的可執行檔
link 過程中主要決定的是將各個 .o 檔裡面程式沒有決定位置的部分連結在一起，以及一些外部符號等進行解析(C 的 extern)
例如:A Program 用到 B Program 的 Function，原先在 A Program 這個部分的位置並沒有確定，因此就要透過 Linker 決定位置

在提到 link 過程中最常提到的也就是 Static link 與 Dynamic link

  • Static link
    在編譯、連結階段就會將 lib 直接編入，佔空間但速度快

  • Dynamic link
    在程式執行階段才會載入 lib，不佔空間但速度較慢

最後補充一下 Linker 是由 linker script 所組成

Executable File

Linker link 完的檔案(a.out)便是可執行檔，一般存於硬碟中
而 Executable file 的內容大致從上到下會有

  • ELF Header (Executable and Linkable Format) 標頭檔
  • Program-Header Table
  • .text 存放程式
  • .rodata 存放唯讀資料
  • .data 存放已初始化的 global variables
  • .bss 存放未出化的 global variables

Memory

當程式執行時，會有 loader 將硬碟中的 Executable file 解析並放進 Memory 裡面待 CPU 執行
這部分的架構如下，大家應該是差不多看到爛掉了

記憶體從最下面是 0x0000 到上面 0xffff
最下面的 text 放程式碼
再來先放 initialized data 再放 uninitialized data
之後是 heap 從下往上放，放動態記憶體，例如:malloc, new
最後從上往下放的是 stack ，包含 local variable 或是 recursive 的 code(遞迴會爆掉就是這塊壓到下面的空間)

最後在這邊整理一下完成程式的執行過程

  • 先將原始碼(source code, assembly source code)經過 preprocesser 以及 Compiler, Assembler 編成 .o 檔
  • 將 .o 檔與 lib 透過 link 連結成可執行檔(a.out)存到硬碟等待執行
  • Loader 將硬碟中的可執行檔解析並搬至記憶體中再交給 CPU 執行

Makefile

當 Program 的程式量越來越大的時候，我們如果一個一個手動編成 .o 檔還要自己 link 是非常費神且沒有效率的事情
因此我們可以透過撰寫 Makefile 來幫我們自動化的進行這些動作，並依照是否有修改檔案決定是否需要重新 compile 與 link

Autoconf tool

在我們完成 program 後，我們會希望他在各個平台都有辦法執行
因此 Autoconf tool 可以幫我們做各平台檢查與轉換的工作

Debugger

基本上寫 code 的過程中不可能會沒寫出 bug，因此我們需要 debugger 來輔助我們能更方便的找出程式在哪裡當掉
debugger 能夠找到這些資訊的原理為
debugger 會將我們寫好的程式編出來之後抹掉一個 Byte，並且告訴 CPU 說遇到這些部分當掉就跳過去找他

我們就可以在這樣的情況下取得當下程式的資訊(Callstack)

另外要提到的是在 User space 的 debugger 會由 kernel space 執行
那 Kernel space 的 debugger 怎麼辦?
聽說當初最早的創作人表示，如果會寫出 bug 就不要寫 kernel XD
不過由於我們都是普通人，因此現在還是有一些小程式可以輔助我們 debug，但這些 debugger 該怎麼 debug 就不要問我了

常見的 Debugger 有: gdb, kgdb, …

Simulator Enumerator VM

大致上理解的分別如下

  • Simulator 看起來跟正常環境一樣，但其實內容並不一樣
  • Enumerator 看起來跟正常環境一樣，內容也做得幾乎一樣，但也有可能透過其他方法達成一樣的效果
  • VM(Virtual Machine) 透過真正的環境切出部份資源產生出模擬環境，基本上與真正環境無異

Version Control

在多人大型軟體開發的情況下版本控制有多重要應該不用多做說明了
版本控制的原理主要是在每次更新的時候存下相異的部分(如果整個檔案重存太耗資源)
如果沒多人修改同一個檔案就直接將相異部分 merge 就好
如果有多人修改同一個檔案就先去打一架決定要用誰的再合併

常見有: git, SVN, …

Week2 - Booting

本周介紹的內容由按下開機鍵之後到你可以登入開始使用電腦的過程中發生了哪些事

按下開機鍵 -> 喚醒 CPU -> CPU 到指定的 Permanen Memory(通常是ROM) 拿第一個程式 (Bootloader1)
-> Bootloader1 做初步的初始化以及喚醒一些可以 drive 各個裝置的 Program (Bootloader2)
-> Bootloader2 將 device 內 load OS 的 Program 讀出來 (Bootloader3)
-> Bootloader3 將 OS load 出來執行 (Bootloader4)
-> Bootloader4(OS) 執行使用者需要的各種 Program

Bootloader1

CPU 剛被喚醒後並不清楚外面環境(device)的任何狀況，會先到指定的 Memory 位置執行指定的 Program，也就是 Bootloader1
SoC(System on Chip)，因此會找指定的 Memory(ROM) 去執行 Program
因此在出廠的時候就已經燒在 firmware 上
這個 Program 會將部分參數初始化後並檢查周邊的 hardware 狀況
可能會提供簡單的 Shell 提供使用(ex:x86/BIOS)
將 device 內的 Program(Bootloader2) load 進 Memory 並將主導權轉交給 Bootloader2

Bootloader2

將 OS 的 loader 給 load 進 Memory
可能提供簡單的 Shell 提供使用(選擇何種 OS 開機)
不是所有裝置都有這個部分的 Bootloader(ex:Smart Phone 開機時就已經決定是 Android 或是 IOS)
到目前為止都是在絕對位置去取得所需的資料，CPU 還不認得 filesystem
將主導權交給 Bootloader3

Bootloader3

將 OS load 進 Memory 並作一些初始化
load kernel, 各種 table, schedulder 等 Program
將主導權交給 OS(Bootloader4)

Bootloader4

OS 執行 Shell 提供 User 可以進行各種指令與程式的執行(fork)

Week3 Interrupt and Interrupt Handling I

CPU 的 Interrupt 常用於 Device Driver 上或是各種服務的中斷與執行

Device Driver

Driver 被定義為驅動各種裝置的 Program
Device 會透過物理上的連接(PIN)將訊號送到 bus 上
Assembly 透過正確的溝通方式(Protocal)對於 device 做操作
IO device 會佔據 Memory 區塊讓 OS 對此段 Memory 操作時對 device 發訊號
CPU 不會直接與 device 溝通(浪費資源)，會先與 Controller 溝通再由 Controller 對 device 發訊號

Interrupt

在 CPU 工作時如果用無限迴圈去 handle IO 訊號相當浪費資源，因此在用新訊號出現時再透過 Interrupt 告知 CPU 有事情需處理
CPU 在處理完目前的工作時就會接著處理 Interrupt 內的訊息

Exception

通常我們會將軟體上的 Interupt (Software Interrupt) 稱為 Exception
而如果只說 Intterupt 通常指硬體上線路升為 high 與對應的處理
兩者的後續的行為大致相同(查 vector table 做對應的 handler)
Exception 的例子: Divid by Zero

Week4 Interrupt and Interrupt Handling II

PIC

各種 device 會將線路連接到 PIC (Programmable inerrupt controller) 再透過 PIC 連接到 CPU
當有新的 interrupt 訊號進來，device 會將線路升成 high 再透過 PIC 送給 CPU
PIC 也可能有多個串聯、並聯
CPU 收到 Interrupt 訊號會先將當前的事項處理完或是將 context 存下後，先查看是何種編號的 interrupt 再查詢 vector table 做對應處置
vector table 的內容擺放 jump 到對應執行的程式碼 (Interrupt Handler)

Exception timing

Interrupt 的整個過程 (Interrupt response time) 會包含 Interrupt lantency 與 Processing time
Interrupt lantency 為 device 送出訊號直到 CPU 收到訊號中間的時間，IO 需要點時間延遲送進 CPU
Processing time 為 CPU 開始執行對應的程式碼，可以透過撰寫者控制執行速度

Interrupt Handler

Interrupt Handler 大致會分為 Top Half 與 Bottom Half (概念上的設計方式)
某些 device 需要即時性的處理(例如網卡收封包)，就會在 Interrupt 之後在 Top Half 的部分先做處理
在 Top Half 的執行過程中，也有機會被 Priorty 較高的 Interrupt 所打斷
而封包的解析並沒有這麼的需要即時性，因此會先讓 CPU 回去處理原本的事物並接受其他 Interrupt
並將封包的處理排進 scedule 內等待處理，後半段處理的部分我們稱為 Bottom Half
透過上述的概念我們可以知道 Interrupt Handler 的執行可能會分散在 CPU 的工作時間內

Driver

當有新的 driver 進出時，會有 init 與 cleanup 的 module 讓 OS 去註冊
driver 會由許多定義好的 API 所組成，將 function 對應到 OS 的執行工作表上
例如當 OS 執行 write 時，就會將 function 對應到 C: 或是 D: 上 driver 的 API 執行

Softirq

Softirq 為 linux 系統提供的功能(Library)，起因是由於 Interrupt 之間存在許多互相打斷等等複雜的關係，因此 Linux 提供這項功能讓撰寫者能更方便的使用
Interrupt Handler 可以透過 Softirq 的方式執行，撰寫者必須 follow softirq 的建議的撰寫方法達到執行快速的效果
Softirq 內部會幫你做些整理或是排程，有可能把 Bottom Half 的部分在不同的 CPU 上去執行…等等
這些內部事項都是為了讓執行起來更快更有效率而做

舉例來說，假設 Softirq 內是空的時發生了 Interrupt A 之後在 Interrupt A 的 Bottom Half 執行時發生了 Interrupt B
完整的過程為
origin program -> Interrupt A -> A Top Half -> Softirq(目前只有 Interrupt A) -> A Bottom Half
-> Interrupt B -> B Top Half -> Softirq(裡面有 Interrupt A, B) -> A Bottom Half
-> Softirq(只剩 Interrupt B) -> B Bottom Half -> Softirq(空了) -> origin program

Tasklet

常被 Softirq 拿來比較的 Tasklet 為 Softirq 裡面的一項功能
就我的理解，Tasklet 就像是一個小的 Softirq 並且在 Softirq 裡面參與排程
相對較不重要的 program bottom half 就會被丟到 Tasklet 裡面
Softirq 在排程的過程中也會執行到 Tasklet 這個功能，Tasklet 就會去看自己裡面有哪些待執行的 Bottom Half 並且排程後執行
例如 printer 的執行速度較不重要，就可以被丟到 Tasklet 裡面，待重要的部分執行完後再由 Tasklet 將一群都沒有很重要的排程後執行

Week5 Process Management I

OS 讓 CPU 執行 user 的指令經過以下步驟

CPU 跑第一個 Program A(init)
-> System call 請求 load Program B
-> OS 幫忙處理 Program, process, thread
-> OS Fork Program B
-> Execute
-> OS schedule
-> Context switch
-> CPU 執行 Program B

OS runs the first Program

CPU 在開機之後，把 OS load 進來並 init 之後，等待 user 指令

System Call

在某些程式執行的過程中會需要使用到某些 lib 裡面包含較危險、敏感的資料與操作(fork, open, …)
因此這些 lib 內會透過 System Call 讓 OS 幫你完成這些指令

目前 x86 使用 Exception 的方式，使 CPU 中斷去執行指定的服務
Exception 可以被理解為一道道被預設在 CPU 內的指令(Unknown Instruction, Divied by Zero, …)
OS 會在開機的時候將 Exception 對應的指令放在記憶體內(Vector Table)
當 CPU 執行 Program 的過程中觸發了某些意外 Exception 就會透過 Vector Table 去執行對應的指令

Process Context

在不同 Process 執行時會自己有相關的資料需要紀錄(Context)
在 CPU 執行指令時，如果有 System Call 進入 Kernel Space 不算是 Context Switch 最多只有更改 mode

Kernel Space and User Space

User space 與 Kernel Space 實際上放在記憶體的兩個區塊
User space 與 Kernel Space 各有自己的 stack (User stack, Kernel stack)
在不同的 space 執行會把 sp (stack pointer) 指到自己 space 的 stack 上

不同指令需要的權限不同，因此也會依權限將指令分為 Kernel mode 與 User mode 來管理
Kernel mode 與 User mode 的狀態為 CPU 在硬體上的狀態轉換，當在 Kernel mode 的底下，CPU 就能辦到更多的事情(傭有更多的權限)

Program and Process

在 Disk 裡面尚未執行的 Elf files(Execute file)，稱為 Program
將 Program load 到 Memory 裡面執行，稱為 Process

Fork

在 Program A 透過 OS fork 出 Program B 的時候會紀錄在 OS 的 Task structe 內
此 data structure 用來記錄執行時的相關資訊(discriptor, PID, parent, …)，以及執行狀態(也會用於 schedule)

Week6 Process Management II

Context Switch

Context Switch 指的是在不同 Process 之間的切換需要有相關資料的備份，與執行到的位置等等的儲存，實際上為 register 的備份行為
Context Switch 的過程必定是比只做一件事耗時的，但目前為了使用者體驗的原因(ex:一邊播音樂、一邊寫報告)
因此會使用 Context Switch 讓多個工作都能輪流被執行到
原則上應該使 Context Switch 的時間佔執行工作的比例較少的 % 數，否則 CPU 可能會一直在執行 Context Switch 不怎麼執行工作導致效率差

Interrupt Context

在 Interrupt 時，因為要求速度快且有會馬上回原 Program 的假設
因此僅有部分的 Context 儲存與備份，但並不是完整的 Context Switch，也通常不稱為 Context Switch
(Ex:收到網路封包 Interrupt 到分析確定是哪個 Program 的封包之前就屬於 Interrupt Context)

Scheduler

在多個程式之間的切換與執行需要優先度、執行時間等等的安排，這邊所依靠的就是 Scheduler
在一般的 Process 開始執行前，Kernel 會加上 Timer Interrupt，每隔一段時間就會打進 User 的程式，就有機會被 Scheduler switch 掉
又或者是 User Program call 到任一 System Call 都有可能藏有 Scheduler 的呼叫在裡面，讓 Kernel 有機會將你 switch 掉

通常 IO bound 的 Process 優先度會較高(因為較高機會是 Interactive 的 Process，ex:browser)
各種 OS ，各種版本，Schedule 的方法都可能會有些差異

User preemption

作業系統是否有將 User Process Interrupt 後切換成另一個 User Process 的能力 (較簡單)

Kernel preemption

作業系統是否有在 User Process 透過 System Call 進入 Kernel 後 Interrupt 成另一個 User Process 的能力 (較困難)

Process and Thread

如果今天開了很多個 word process，每個都要完整的資料結構會浪費空間
因此 thread 的用途就會將程式的部分重用，資料的部分 copy on write 以節省資源

Week7 Memory Management I

Memory access in a Program

在 compile code 時，Compiler 會自己(或透過 linker)將各指令或 data 分配好要放在記憶體的哪個位置
CPU 看到的與 Compiler 相同為 physical memory 的位置，程式的執行指令與 data 就會被放在記憶體上等待被執行

使用 virtual memory 比 physical memory 的好處?

  • physical memory 會被多個 process shared 無法很好的管控

  • virtual memory 可將各個 process 的 memory 獨立分開

  • 對 CPU / Compiler / User 來說，看到的是連續且較大的記憶體

  • 使用 memory 更有效率

  • virtual memory 多一些單元(MMU)與轉換，較高成本也較慢

Virtual to physical address

Compiler / CPU / User 看到的 physical address 其實拉遠來看為 Virtual Memory，會透過一些方式轉換到 Physical Memory 上
實際上 Compiler 看到的連續記憶體，可能其實是透過 MMU 轉換到 Physical Memory 的各個地方看
更複雜的例子來看：如果程式執行過程中透過 Virtual Memory 到 Physical Memory 拿到自己要到指定的 Address 拿 Data 的話
這個 Address 也是 Virtual Memory，一樣會透過 MMU 轉換到正確的 Physicla Memory 位置拿資料

對於每個 Process 來說可能都會擁有 4K 的 Memory 可以使用，但事實上可能只有正在使用 Memory 有 Physical Memory 的對應
尚未使用到的 Memory 可能其實還沒有 alloc physical memory 給你，這樣可以充分使用 physical memory

Segmentation and paging

在 Memory 轉換的過程需要對應的 Segmentation table，大部分這個 table 會放在 memory 內，少部分放在 CPU 內(較為快速)
在程式執行時會透過這個 table 將 virtual memory 轉換到 physical memory 上，若 access 的 memory 超出限制就會產生錯誤，跳去 Exception

x86 example
Logical Address -> Segmentation -> Linear Address -> Paging -> Physical Address

Page table and TLB

Page table 放在 memory 內，MMU 會透過這個 table 做 virtual 到 physical 的轉換
各個 Process 會有各自的 Page Table，Process A 的 0x1234 可能對到 0x6666、Process B 的 0x1234 對到 0x7777
TLB 會將常用的 address 存起來(Page table Cache) 就能不需要查表，直接轉換
在轉換的過程中，有可能 Physical memory 還沒被準備到 table 上，就會產生 Page Fault Exception
之後的 handler 就會將還未使用 Physical memory 的 address 填進 table 上，使 process 能正常執行

先前提到的 Context Switch 也會將 TLB 清掉及 Page Table 切換成另一個 Process 的 Context

Cache

Cache 的目的是讓存取的速度更快，會將常用的 address 放在離 CPU 最近的位置上，只要 hit 到就能快速的存取內容

x86/Linux example

以 Linux 的來說，一個 4G 的 Space，User Program 會佔 X ，Kernel 會佔 4G - X
而最大 Size User 會佔 3G，Kernel 佔 1G
User Process 在轉換 address 過程中會被擋下，無法存取 Kernel (除了 System Call, Exception…)
Kernel Process 在轉換時可以看到 User 的內容

Week8 Memory Management II

Physical memory management

顧名思義，管理實際存在的物理記憶體，作業系統會準備管理實體記憶體的 table
當某個 app 來跟 OS 要一塊記憶體時，記憶體就能透過此表尋找登記實體記憶體的分配，並把指標回傳給 app
在 Kernel 使用時，通常需要連續的記憶體，使得 Kernel 能有更好的效能，jump 時也能直接跳到指定的 offset 上
在管理物理記憶體的層級中就不包含 MMU(虛擬記憶體對實體記憶體的對應) 的使用
缺少了 MMU 也少了對記憶體的保護，某些硬體會使用 MPU(Memory Protection Units) 來保護記憶體的使用(Read/Write Region/Segment)
可以透過 MPU 對整塊 Memory Region 定義使用權限，就能達到 Kernel/User 權限管理的效果

Kernel memory management

管理記憶體本身也會花記憶體，因此資料結構不能太複雜產生過大的 table
Kernel Process 為了效能要求連續的 physical memory，User Process 則可以讓 physical memory 分散
此資料結構管理時，Search 時要越快越好，最好能 O(1)，否則依現在 app 的量肯定找到天荒地老
必須將 User Process 的 Logic Address 對 Physical memory 對應提供 API，以及 Kernel 對 Physical memory 的 API

Internal and external fragmentation

External fragmentation，在記憶體不斷的配置與釋放後，配置的記憶體之間會出現許多零碎的片段無法使用因此浪費
此種問題可以透過將 Memory 切成不同大小的 Page frame，例如:2^0 * 4K, 2^1 * 4K, 2^4 * 4K
直接按照需求給對應大小的 Memory，但此種行為容易造成許多的 Internal fragmentation

Internal fragmentation，舉例來說:當 app 跟 OS 要 0.5 * 4K 的 memory，OS 會直接給 2^1 * 4K 的大小
這樣子的方法會使多給的記憶體浪費掉，產生 Internal fragmentation

x86/linux kernel management

Linux Kernel 採用 Buddy System 進行 physical memory 的管理
Buddy System 會產生大塊的 page frame 交給 app，但會產生很大的 Internal fragmentation
另外如果需要較小的 memory 會使用 Slab Allocator 減少 Internal fragmentation 的問題
在 physical memory 管理上因為還是有速度上的差距，因此另外還有使用 ZONE 的結構去管理不同速度的 memory 供不同情境下使用

Week9 Memory Management III

Process address space

在 Linux 系統中，Process 的 Memory 分給 Kernel space 1G, User space 3G 而這裡的 Memory 是 Logic Memory
每個 Process 就會有自己的 Memory 配置，實際上 OS 會對應到不同地方的 Physical Memory
在 Process 上會有 task_struct 去存此項 Process 的執行狀況，內部又有 mm_struct 負責記錄 memory 管理的狀況
mm_struct 中有多個 vm_area_struct，用於管理 virtual memory 的位置，讓 Process 看起來自己像是完整的 memory 以及保護區塊的使用

VMA

VMA 記錄了 virtual memory 所對應到的 page 或是 file，幫助 OS 找到實際的資料要在哪個位置找
VMA 也幫忙保護 memory area 的存取，若 access 受保護的部分將會產生 segmentation falut
若此 page 還未放進 physical memory 中，將會產生 page falut

Page Falut

當無法在 physical memory 找到對應的 page 時，產生了 page fault
page fault 後 OS 會將需要的 page load 到存取的位置，之後再請 process 重新讀一次
就能使 process access 到正確的內容

Memory Region

在 VMA 不斷的 allocate, free 中，也需要找出空的 region 處理新的 allocate 需求
在 Linux 中使用 Red-Black Tree 做此部分的的記憶體管理，在 O(log n)中找到想要的空間

Memory Mapping

透過 virtual Memory 來使用 physcial memory 可以帶來許多好處
保證每個 process 可以自己看到乾淨的 memory 不互相干擾
若不同 process 用到的相同的 lib，OS 可以將兩個 process 的 lib 對應到相同的 physical memory 以節省空間
process 本身也不用擔心資料源自哪裡，OS 可以將 virtual memory 對應到 physical memory 也可以對應到 file(cache, disk)

Week10 FileSystem and Block IO

File Open

在 open file 時，system call 進入 kernel 後，kernel 會先在 memory 尋找是否有 file 的資料，如果沒有就交由 filesystem 去找
filesystem 透過 parse 過的 file path，從 root 開始一層一層往下找 block (不同 filesystem 可能有些不同)
一個 device driver 直接對於 hardware 做讀取操作，filesystem 建立在 device driver 上層
因此一個 device driver 可以用不同的 filesystem 去讀取，只要此 filesystem 有辦法正確的與 device driver 做溝通

Virtual Filesystem

在接到各種 filesystem 前，OS 會與 virtual filesystem 進行溝通
vitrual filesystem 與 OO 的繼承概念相同，各種不同的 filesystem 可以掛在 virtual filesystem 下 implement
因此上層在使用的時候可以透過相同的操作方式，並透過 virtual filesystem 對下層實際的 filesystem 操作

I/O Scheduler

在操作硬碟時的 operation 需要有一定的結構性，因此使用 Queue 的方式對 hardware 做存取
將各種 request 的 merge, sorting 等操作時，有一定的演算法結構去做操作，以提升 performance

Week11 Kernel Synchronization

Critical Region(Critical Section)

在 multithreading 的情況下操作 share data 時，要避免 data race 的問題
必須考慮執行的先後順序，或是必須完整的操作結束才能給其他 thread 使用
在這段操作 share data 期間的程式就屬於 critical section

Atomic Instruction

CPU 設計的 instruction 會設計一些 atomic operation 來保證指令唯一的執行
可以保證 instruction 是單一的並不時由多個指令組成，避免多個指令執行間被中斷

Lock

最常見避免 race 的問題就是使用各種 lock 將 data 鎖住
等待 share data 的 release 之後才繼續進行操作

Deadlock

在 lock 的過程中，很常遇到拿出來談的一件事就是 deadlock
當兩個 thread 同時要 lock 一個以上的 data 時
若 thead1 lock dataA, thread2 lock dataB
接下來 thread1 需要 lock dataB, thread2 lock dataA
就算造成雙方 lock 不到需要的 data，也不 release 自己的 data
在開發 multithreading 的過程中若沒有小心注意，容易產生此種問題並有嚴重當掉的後果

Spin Lock

最基本的 lock 形式 - Spin lock，被擋住的 thread 直接 busy loops 去等待 data 被 release
在準備 lock data 前，會先 disable kernel preemption 避免 lock 的過程中被中斷
由於 lock 的時候為 busy waiting 因此會浪費 CPU 的效能，最好不要 lock 太久

Semaphore

sleeping locks，等待資源的時候就會將自己丟到 wait queue 之後就先將 CPU context switch 去別的 thread
對於整體的執行效率會比較好，在等待時就先將 CPU 切去做其他事，之後再回來處理
但對於自身的 thread 反而執行速度會變慢，可能要等一輪 schedule 才能再回來

Memory Barrier

在執行 code 時，CPU 因為最佳化可能會將執行順序調換，此時加入 memory barrier 就能保證執行的順序

Week12 Network Protocol and NIC Driver

網路部分的內容主要以 protocal, 網路傳送的原理概略
以及作業系統與網路 lib 之間的關係
此部分內容較散，參考網程這門課的內容可能會比較詳細
1091-網程