mit6.S081小結

這個課程的大部分視頻看完了，lab也全部做完或者抄完了，

這個課程的好處就是基于一個開發出來的簡易作業系統xv6來進行講課還有實驗，讓自己對于OS的理解不再基于書本視頻的一些很理論的東西，而是實際看了一些代碼還有添加了一些代碼的，課程很棒！

lab1 : utilities

利用xv6的syscall來實作一些功能，
理解fork exec pipe的基本作業原理，還是很有用的，至少對于后面寫csapp的shell lab，
1: 很簡單 呼叫系統的sleep即可
2: 利用遞回的一個函式來fork子行程，同時進行pipe的資料傳輸模擬實驗要求，
3: 這個我感覺有點難，因為代碼有點不好讀，find一個檔案，認真讀懂ls是怎么做的就可以了

lab2: system call

添加sys-call
按照要求添加相應的檔案，
1: trace行程，按照實驗要求就明白了，
2: sysinfo 我忘了是干嘛了 不太難，

lab3: virtual memory page table

虛擬記憶體
這個的的卻卻是最難的lab， lab的實驗要求還有提示看了很久都不懂，弄清sys-call的程序，包括了幾個程序 呼叫ecall 轉換kernel MODE， 保存暫存器，跳轉到對應的system的處理程序，對于具體的呼叫命令具體處理，回傳同理，對應了兩個不同的狀態，內核態 用戶態，他們使用的不同的虛擬記憶體，再系統初始化時候初始化內核的虛擬記憶體，在行程創建的時候初始化行程的基本虛擬記憶體，
對于某些系統呼叫，比如read write 需要記憶體的char*,但是進入內核態它的地址(虛擬地址) 并不對應他實際資料的位置，而是當前內核這個虛擬記憶體對應的位置，因此需要模擬這個行程的虛擬記憶體來找到這個char*對應的物理記憶體，這也再實作拷貝，拷貝到內核分配的一塊記憶體上再進行進一步處理，比如寫入磁盤， 因此實驗的目的是不要做這個操作，希望直接memmove，實作的方式就是通過對內核必須的頁面，在每個行程也進行內核的映射，如果一個系統呼叫進入內核態，直接進入對應行程創建的內核，內核的虛擬記憶體和行程的虛擬記憶體想對應，可以直接進行拷貝，

這個lab屬實受折磨的靈魂，20行不到的代碼，一開始沒有思路，后面又是各種page trap或者panic等問題，最后抄了老師的作業才完成，

lab 4:

trap， 在CSAPP里面講例外部分說到了trap是OS的一種trick，一直不太理解為什么是一種trick，感覺上很直觀啊， 后面的幾個lab可以讓你理解虛擬記憶體缺頁或者頁面訪問權限的問題的妙用，
1是幾個問答題，不難
2 制作一個類似于gdb的函式呼叫的一個跟蹤工具，但是沒有gdb那么高級可以顯示函式名，只是顯示函式呼叫的地址，搞清楚xv6的stack的構造，stack中有一個指向上一個stack frame地址的變數很重要，
3: alarm system call，這個還是很有難度的，用處就是大概作業系統的行程調度調度每一個行程的運行實際，如果一個行程運行時間太多了作業系統需要把CPU這種資源分配給其他行程(不然就餓死掉了~)，這里并不是實作這個功能，類似于實作行程呼叫計時器，到達時間運行某個函式，這個的難點在于，我被中斷后會進入內核態，如何在內核態運行一個用戶態的函式然后在回傳內核態，再yield或者回傳行程態，
user mode => tick trap=> kernel mode => excute function(handle) => user mode
程序大概就是這樣，

lab5: lazy allocation.

這個就是利用虛擬記憶體缺頁的問題來，對于sbrk系統呼叫，我們只是簡單地增加size，而不是去分配相應的物理記憶體(1是不需要分配物理記憶體的時間 2是節約了記憶體)， 但是問題就是 如果我增長的記憶體是這個行程需要使用的，我這個行程在使用這個lazy allocation分配的記憶體的時候，硬體(qemu模擬的硬體)會發生例外，因為沒有實際的物理記憶體和這個虛擬記憶體對應，因此需要在trap處理中處理這種情況，同時為了內核安全性的考慮，只有真正是我lazy allocation分配的記憶體才會進行這種處理，
處理的方式就是如果發生相應的缺頁，我再去分配就OK了，然后重新執行這條指令，相應的記憶體就會被分配，也就不會例外了，

lab6 : COW

COW(奶牛lab)， copy-on-write： 原理就是對于某個已經分配了物理記憶體的頁我進行拷貝，我不進行實際的物理頁面創建,甚至相應的虛擬頁面創建我也不進行創建，也就是一種lazy的方法，
這么做的好處，比如shell呼叫fork 然后fork的子程式再去執行一個什么程式，我fork的記憶體完全沒有用到就"拋棄"了，非常浪費記憶體以及記憶體拷貝 虛擬記憶體創建的時間，因此采用一種lazy的方法來做，
如果這個拷貝的記憶體是要使用的，和上面一樣 會觸發一個 virtual memory trap, 一樣在trap中處理進行虛擬地址實際物理地址的創建，

這里的理論用一個圖來說明，如何保證這樣的正確性，
在STL中也有用到這個技巧的，就是string， 比如你拷貝一個string， 不做實際的char*的拷貝，而是僅僅建立一個reference, 但是標記為只讀，如果這兩個某一個需要拷貝，這個時候再進行拷貝，標記為讀和寫(write&read),這樣就可以做modify了，

lab7 : multi-threading.

1: 模擬內核切換行程時候需要記錄的暫存器，直接CV 不多BB
2 :用一下linux下的pthread的lock unlock的東西，實作hash的執行緒安全版本，對于hash的每個slot創建一個lock就可以了，
3: barrier 一種同步的機制，多個執行的執行緒(行程) 執行到同一個點, 才會向下進行，我覺得用C++的方法類似于 一個

condition_variable _cond;
size_t _cur_size;
size_t _max_size;

因為我需要知道多少個到達這個點，因此需要size來初始化，比如對于某個進行，進入到這個條件，當前的size如果沒有到達最大的size，那么就sleep， 如果到達了相當于用一個條件變數通知所有對此等待的執行緒進行喚醒，繼續執行， 比較簡單

但是這個相關內容的視頻講解有點難度，我沒想到sleep 等和thread相關的函式有這么多細節，包括鎖的使用，真的是細節滿滿，
同時降到了lock是如何實作的，只是講了最簡單的spin-lock，以前不直覺得就算是lock也不能保證資料正確性，聽了知道是通過硬體的機制來保證lock的原子性的，

lab7: lock

這個lab難度我覺得僅次于lab3, 因為第二個問題如何避免死鎖的同時增大并發度對我有點難度，
1: 對于OS，我們管理真是的物理記憶體是用一個free_list， 記住xv6模擬的是多個cores，也就是是多行程可以同時運行的，而物理記憶體是只有一塊記憶體，也就是說多個cores可以同時去索取物理記憶體的，因此需要lock，這里用了一個spin-lock來鎖住對于free_list的改變，不管你是alloc還是free 直接鎖住，是為了保證資料的正確性，

對于多執行緒程式，1:首先保證正確性 2: 盡可能增加并行度，

這里要求我們增大free_list的并發度，并且提示我們了怎么做，
明天畫圖說明這里，

對于每個core創建一個free_list來分割所有記憶體，每個free_list加一個lock，同時加一個全域的lock，
如何保證沒有死鎖?
首先對于某個core進入相應的free_list, 如果沒有記憶體可以分配了，他需要其其他core的free_list來借記憶體， 你和其他記憶體借記憶體，你會改變其他core的free_list 這里就是一個競爭的點，因此我可以通過直接或者你的鎖，(就算是ordering也不行 畫圖說明) 這樣會有一個死鎖，死鎖的原因是兩個core同時需要找其他的core借物理記憶體，
于是加一個全域鎖，這個全域的鎖就是保證我要去獲取這個全域鎖，這樣別的core沒有記憶體需要等我這個core來借記憶體，向下的時候首先check是否holding-lock 如果hold我們可以假設你也是沒有記憶體再等這個全域鎖(問題可能是他有記憶體，只是剛好再分配或者釋放的時候加了一個鎖)， 但是我們不去等它，而是不斷回圈每一個core尋找能夠進入的，能夠進入如果可以分配(借給我)記憶體，那么就OK，飯hi這個記憶體就可以了，

2: 這個問題和檔案系統相關，檔案系統的訪問也是有一層快取，這個快取是通過LRU進行快取和分配的，這里是用一個回圈鏈表加一個lock來實作，但是很多行程都需要訪問檔案系統，只有一個鎖，資料保證是對的了，但是并發度非常非常低，而且一個檔案讀取的實際非常久，這樣這個等待可能非常非常久，
于是要求就是提高檔案系統快取的并發度，提示我們用一個static-hash配合LRU， 其實實作一個沒有dead-lock的方案我感覺挺難的 ，
中途寫了3個方案，一個是區域的LRU(可以沒有死鎖) 第二個是一個有點復雜的(很多鎖，我中途卡死了) 最后實作了一個方法， 用goto的辦法實作了一個沒有鎖的辦法，

hash提高并發度非常顯而易見， 多個slots 分別加鎖，假如對于都是訪問的操作，那么肯定是提高并發度的，而且你的hash約均勻 這個并發度越高，問題在于會有寫操作，快取的大小是固定的，也就是說如果發生了cache miss，你必須要選擇一個victim 來進行替換，同時利用time-stamp(利用系統的tick)組織一個LRU的演算法進行victim的選擇，

問題1: 如何組織全域的LRU
問題2: 如何處理假如選擇了一個victim， 如何進行替換，因為涉及兩個hash-slot的訪問，很可能死鎖，
問題3：選擇了一個victim，假如這個時候又來訪問了，這個victim如何處理？

對于問題3是一個trade-off問題，我認為這個時候訪問，這個victim應該還是做為快取， 因此這個victim應該從新進行選擇，但這樣死鎖的風險似乎變大了，

系統圖（還妹畫呢 憋急） :

對于所有可能死鎖的問題進行考慮，
最終通過了測驗，奈斯，

課堂筆記: 避免死鎖的一個方法是order 這里就現學現用了一下，鎖還不能多次釋放或者多次lock 是錯誤的 注意，
小結: 一開始學習死鎖覺得這不是有手就行？ 還能死鎖？ 現在覺得我真是NT， 這樣一個簡單的問題都要考慮很久，

lab8: file system
file system 遠不是我想想的那么簡單，很多layer，強烈建議看視頻，講的非常清楚，
結構如下(圖1 2 3):

理解了結構 lab還是比較容易的
1: 擴容xv6的檔案系統，支持更大的file，搞清楚圖就行了，比較簡單
圖：
2: 軟鏈接，這個有點難度，因為需要查資料弄清楚軟鏈接，硬鏈接，看了一個別人的解決方案才搞懂的，
軟鏈接查找檔案的程序是一個遞回的，因為鏈接的可能也是一個軟鏈接，遞回yyds，
圖 :

lab 9: mmap

這個lab其實有點像 lazy location， lazy location的目標是物理記憶體，它的目標是檔案，
目標: 我們操作檔案的方式通過 file descriptor(fd) 通過open來完成的，offset是記錄在fd中，在我們不知道的地方默默記錄著(以前還一直搞不明白這，知道這個了豁然開朗)，
現在對于檔案我們認為是一段虛擬記憶體， 認為可以像指標一樣 隨意地取地址，實驗的內容就是建立這樣的映射，當然有標志位的設定，意義也很清晰，read 就是單純的只讀，不能更改， write允許修改，但是這個修改是否對真正的檔案產生影響取決于另一個flag: private || public 如果是private 那么這個write只是對我這個行程可見，不會持久化到檔案系統，但是如果是public 那么這個修改會持久化到檔案系統(這種情況需要lock一下這個檔案，因為允許我修改，其他人也修改，那么這個檔案最終的一致性沒法保證，因此使用一個檔案lock(我忘了是不是用lock還是什么，大概意思是這樣)， 從而保證原子性)， 相應的mmap的虛擬記憶體如果被釋放，是可以寫的檔案那么會寫回磁盤，

課程筆記: 這節課講了 logging system， log也并不簡單，之前聽分布式系統覺得log 系統可以保證recovery 但是沒想到一個log system很難構建，有非常多的細節，！！！ xv6實作了一個簡易的但是性能很差的log 系統，后面降到了linux實作的log系統， 通過對多個事務進行糅合增加性能，

講了一個非常重要的assumption: 對于disk的單個block的寫入是原子的,這個應該是用硬體來完成的，否則之上的log系統也不能保證 crash recovery.

lab 10: networking.

最后一個lab了， 蕪湖，這個lab要看一些檔案，我感覺迷迷糊糊的但是大概明白的是 通過buf來分配，設備可以直接寫入記憶體中，通過一些標志位(設定在暫存器中) 告訴網路設備 下一個來的包寫入哪里(哪個buf)
network stack: 比如一個包從設備接受了，一步一步向上到應用層的程序，

小結

配置環境可以先配置riscv-gcc qemu 再從清華的鏡像下載最近的riscv-gdb編譯，簡單無痛，無需github龜速下載工具，

lab程序，老師也提到了很重要的一點:
你的程式的不變數(invariant)到底是什么，你通過什么樣的才做來保證(maintain)，同時通過一些運行時檢查措施來保證你不變數，這是一種很好的寫程式方式，對應于lab就是多寫panic再你覺得可能有問題的時候，其他程式比如用_assert() ，比如一些例外可以通過函式呼叫(trace)的方法來進行除錯，多執行緒的除錯printf() yyds.

視頻也值得看，有的老師關于一個點進行了講解，直接分析所有，比如fork, 行程切換， system-call, sleep, uart(鍵盤輸入輸出的設備) 等等， 非常棒！

有的圖還沒配，后面上傳，