系列綜述：
??目的：本系列是個人整理為了操作系統(tǒng)學(xué)習(xí)，整理期間苛求每個知識點，平衡理解簡易度與深入程度。
??來源：材料主要源于南京大學(xué)操作系統(tǒng)jyy老師課程進行的，每個知識點的修正和深入主要參考各平臺大佬的文章，其中也可能含有少量的個人實驗自證。
??結(jié)語：如果有幫到你的地方，就點個贊和關(guān)注一下唄，謝謝???????。?！
??相關(guān)網(wǎng)址：jyy老師的博客

??點此到文末驚喜??

操作系統(tǒng)概述

生存指南

1. linux設(shè)計哲學(xué)
   • Keep it simple, stupid
   • Everything is a file
   • All in terimal
2. 學(xué)習(xí)操作系統(tǒng)的目的
   • 你體內(nèi)的編程力量沒有完全覺醒：看到一切東西都可以寫出來
   • 酷的事情和學(xué)的數(shù)學(xué)理論之間的gap連接起來
3. 操作系統(tǒng)定義
   • 充分利用軟硬件資源，為系統(tǒng)提高服務(wù)的程序
4. 兩個操作系統(tǒng)的頂會
   • OSDI/SOSP
5. 進程地址隔離的原因
   • 避免進程指針訪問錯誤，從而導(dǎo)致其他進程程序錯誤
6. 多道批處理系統(tǒng)
   • 進程與OSKernal交替運行，其他進程負責任務(wù)處理，kernel負責切換和資源調(diào)度
7. 程序的運行就是一個狀態(tài)機
   • 內(nèi)存和寄存器存儲狀態(tài)
   • cpu運行的指令改變內(nèi)存的狀態(tài)（pc指向的指令的執(zhí)行）

什么是程序和編譯器

1. 狀態(tài)機和數(shù)字電路
   • 狀態(tài)：內(nèi)存M+寄存器R
   • 初始狀態(tài)：RESET
   • 遷移：組合邏輯電路計算寄存器下一周期的值
2. 數(shù)字邏輯電路的步驟
   • 定義并初始化所有寄存器
   • 在一個時鐘周期到來時，運行組合邏輯電路
   • 將結(jié)果更新到寄存器中
3. 管道思想
   • 將一個程序的輸出作為下一個程序的輸入
4. 程序本質(zhì)是一個狀態(tài)機
   • 程序運行在計算機上
   • 計算機本質(zhì)是一個數(shù)字系統(tǒng)
   • 數(shù)字系統(tǒng)本質(zhì)是一個狀態(tài)機
5. C語言的程序也是狀態(tài)機
   • 堆棧表示狀態(tài)
   • 語句表示狀態(tài)遷移的規(guī)則
   • eg：單步調(diào)試就是狀態(tài)機中狀態(tài)的轉(zhuǎn)換，堆棧存儲的是當前的狀態(tài)
6. 函數(shù)調(diào)用的狀態(tài)機思路
   • 狀態(tài)：調(diào)用函數(shù)會創(chuàng)建對應(yīng)的棧幀
   • 執(zhí)行：函數(shù)中指令的執(zhí)行導(dǎo)致棧幀狀態(tài)的轉(zhuǎn)換
   • 函數(shù)調(diào)用的返回：將該函數(shù)的棧幀刪除
7. 狀態(tài)機之間的轉(zhuǎn)換需要通過 指令，指令有兩種
   • 計算
   • syscall
8. 狀態(tài)機可以觀測
9. 真正的計算機從業(yè)者應(yīng)該具有讀官方手冊的能力
10. 編譯器其實就是對于狀態(tài)機的生成和優(yōu)化

    extern int g; // 全局變量，其他程序可能使用，不可優(yōu)化
    void foo(int x){
    	g++;
    	asm volatile("nop"::"r"(x));
    	// __sync_synchronize();// 這個barrier將不可優(yōu)化
    	g++;
    }
    // 即使兩個g++中間代碼不可優(yōu)化，但使用-O2仍然可以優(yōu)化
    

11. 操作系統(tǒng)管理了所有的軟硬件資源，具有最高權(quán)限
12. 計算機系統(tǒng)不存在玄學(xué)，一切都建立在確定的機制上
13. 通過工具去觀測程序運行中狀態(tài)機的狀態(tài)
14. 程序運行
    • 另一個進程執(zhí)行execve設(shè)置初始狀態(tài)
    • 狀態(tài)機執(zhí)行計算指令和syscall
    • _exit(exit_group)退出
15. 程序 = 狀態(tài)機
    • 源代碼視角：狀態(tài)轉(zhuǎn)移 = 執(zhí)行語句
    • 二進制視角：狀態(tài)轉(zhuǎn)移 = 執(zhí)行指令

多處理器編程

1. 并發(fā)的基本單位：線程
   • 從狀態(tài)機視角：并發(fā)的線程實際是同一個基本狀態(tài)延申出來的，不同線程間執(zhí)行的狀態(tài)流是獨立的，通過共享內(nèi)存進行通信。
   • 并發(fā)程序執(zhí)行的每一步都是不確定的
2. join含義
   • 如果一個進程有三個線程t1、t2、t3，那么當t1.join()時，意味著t1狀態(tài)轉(zhuǎn)換的指令是while(t2沒結(jié)束&&t3沒結(jié)束);，即選擇t1執(zhí)行會進入狀態(tài)機的死循環(huán)，從而等待t2和t3執(zhí)行完成。
3. 線程是共享內(nèi)存空間的，即沒有邏輯地址空間的獨立性，但是有線程棧幀的獨立性
4. 在多處理器體系下，指令無法獨占處理器執(zhí)行，即多線程的狀態(tài)機中的初始狀態(tài)下下一個狀態(tài)可能是多分支的
5. 狀態(tài)機模型
   • 單線程
     
   • 多線程
     
6. 線程安全：能夠保證多線程的原子性
7. 并發(fā)問題的隊列解決
   • 99%的并發(fā)問題可以使用隊列這個數(shù)據(jù)結(jié)構(gòu)進行處理
   • 將大問題切分成小問題
   • worker thread去鎖保護隊列中取任務(wù)
   • 除去不可并行部分，可并行部分可以獲得線性的加速
8. 多處理器編程需要放棄對于單線程狀態(tài)機的舊理解
   • 放棄原子性：并發(fā)導(dǎo)致了狀態(tài)機中狀態(tài)的轉(zhuǎn)換可能出現(xiàn)分支
   • 放棄順序性：編譯器對于內(nèi)存訪問“evenual consistent”的處理導(dǎo)致共享內(nèi)存作為線程同步工具的失效
   • 放棄可見性：現(xiàn)代處理器對于指令的亂序發(fā)射的優(yōu)化，導(dǎo)致程序語義與指令語義的不同
9. 編譯器的優(yōu)化是按照單線程的狀態(tài)機進行代碼的優(yōu)化
   • 結(jié)果一致性：無論中間狀態(tài)的轉(zhuǎn)換，只要狀態(tài)機最后的狀態(tài)是一致的即可去除中間狀態(tài)轉(zhuǎn)換
10. 避免優(yōu)化：保持C和匯編語義的一致性
    • __sync_synchronize();
    • asm volatile("":::"memory");// 強制寫回內(nèi)存
11. 現(xiàn)代處理器也是一個動態(tài)編譯器
12. 在處理器中執(zhí)行的指令是一個DAG有向無環(huán)圖，這個圖是通過邏輯相關(guān)性確定的，每次盡可能的多發(fā)射指令進行處理
13. 線程內(nèi)存模型
    • x86架構(gòu)：每個線程有自己的緩存，結(jié)果一致性體現(xiàn)在共享內(nèi)存中
    • risc-v架構(gòu)：每個線程都有自己的內(nèi)存副本，是一種分布式的架構(gòu)，不需要保證內(nèi)存一致性
      
14. 現(xiàn)代的編譯器（處理器的一部分）：是一個動態(tài)的數(shù)據(jù)流分析器

理解并發(fā)程序執(zhí)行

1. 并發(fā)程序 = 多個執(zhí)行流并且共享內(nèi)存的狀態(tài)機器
2. 通過狀態(tài)機視角，去理解程序的執(zhí)行。包括并發(fā)程序。
3. 互斥：兩個或多個線程不能同時執(zhí)行一段代碼
4. 并發(fā)問題鎖

   int locked = UNLOCK;
   void threadx(){
   	while(locked != UNLOCK);// 有鎖則自旋
   	locked = LOCK;
   	// 臨界區(qū)
   	locked = UNLOCK;
   }
   

   • 狀態(tài)機中包含兩個線程的棧幀和pc（程序計數(shù)器，即下一條指令地址），以及全局鎖變量（共享變量）
   • 錯誤并發(fā)的狀態(tài)機模型
     • 第一個狀態(tài)：線程1和線程2都建立了threadx的函數(shù)棧幀，pc均指向while指令處
     • 執(zhí)行：線程1執(zhí)行，讀locked為UNLOCK，執(zhí)行完while并pc指向下一條指令
     • 第二個狀態(tài)：線程1pc為locked=LOCK指令執(zhí)行處。線程2pc內(nèi)容為while指令處
     • 執(zhí)行：線程2執(zhí)行，讀locked為UNLOCK，執(zhí)行完while并pc指向下一條指令
     • 第二個狀態(tài)：線程1和線程2的pc均為locked=LOCK指令執(zhí)行處
     • 執(zhí)行：無論線程1或線程2執(zhí)行，在之后切換線程執(zhí)行時均會導(dǎo)致兩個線程都在臨界區(qū)中。
5. Pertenson算法（兩個線程看似謙讓，實則自私）
   • 任何一個線程想進入臨界區(qū)，先更改自己的flag，然后將共享變量更改為對方
   • 查看對方的flag和共享變量，如果對方的置flag為true并且門上名字不是自己則等待，否則進入
   • 當離開臨界區(qū)時，置自己的flag為flase
     
     
6. 把線程想象成自己和他人，把物理世界的客觀物體（旗子…）想象成共享內(nèi)存。
7. 線程讀?。吹剑┑墓蚕韮?nèi)存狀態(tài)是一個歷史history，而共享內(nèi)存寫入的東西是一個時間點（瞬間完成的）
8. liveness：任何狀態(tài)出發(fā)，總是能在有限步內(nèi)到達同一個確定的狀態(tài)
9. 任何程序可以建立狀態(tài)機轉(zhuǎn)換模型，通過暴力枚舉狀態(tài)機的方式進行程序正確性的證明。
10. 每一個程序的正確性驗證，都可以自己寫一個model checker程序，將狀態(tài)空間進行遍歷檢查
11. 抽象的角度看一個狀態(tài)機，它就是一個圖。通過圖論的方式，將所有的業(yè)務(wù)邏輯編寫成圖的形式。
12. 系統(tǒng)需要工具進行人機的交互解釋

并發(fā)控制

1. lock函數(shù)返回含義是調(diào)用線程獲取了獨占某個資源的鎖
2. 獨立瞬時的讀寫操作導(dǎo)致寫前和讀后對于狀態(tài)的未知性
   • 讀：看一眼就把眼睛閉上，即讀只能讀到一瞬間的狀態(tài)，讀的是一個history
   • 寫：閉著眼睛改變，即寫入只能覆蓋，無法知道寫入時的狀態(tài)
3. 問題無法解決就解決問題的假設(shè)（提出問題的人）
4. 只使用一個原子變量實現(xiàn)互斥
   • 實現(xiàn)讀寫的瞬間一致性：一個線程寫共享變量時，先讀后寫，且讀寫瞬間共享變量屏蔽其他線程
   • 匯編實現(xiàn)：atomic exchange（load+store）

   int xchg(volatile int *addr, int newval){
   	int result;
   	asm volatile("lock xchg %0, %1" : 
   		: "=r" (val), "+m" (*addr) : "m" (*ptr) , "0" (val)
   	);
   	return result;
   }
   // 自旋鎖
   int locked = 0;
   void lock() {
   	while(xchg(&locked, 1));
   }
   void unlock(){
   	xchg(&locked, 0);
   }
   

5. 代碼是兩個 層面的東西，一個層面是人所理解的業(yè)務(wù)邏輯，另一個是機器層面。真正理解代碼需要對于兩個層面都深入了解
6. 原子指令模型
   • 之前的所有store寫操作都會寫入到內(nèi)存中
   • 所有的內(nèi)存訪問都不能越過原子指令
7. 原子指令的實現(xiàn)
   • 通過一個bit表示總線資源的鎖，訪問內(nèi)存需要先獲得總線的鎖
8. x86中的L1緩存是連接在一起的，為了實現(xiàn)緩存的一致性
9. 常見原子操作的本質(zhì)
   • load
   • exec(處理器的寄存器的運算)
   • store
10. risc-v的原子操作：先運算出結(jié)果放到緩存中，當需要同步到內(nèi)存時，先打標記，再判斷標記是否存在，存在時再寫入內(nèi)存，然后刪除標記

    // CAS鎖（compare and swap）的實現(xiàn)機制
    int cas(int addr, int cmp_val, int new_val){
    	int old_val = *addr;// 讀取標記
    	if(old_val == cmp_val){// 標記等于自己的之前打的，則寫入
    		*addr = new_val;
    		return 0;
    	}else{
    		return 1;
    	}
    }
    

11. 自旋鎖的缺陷
    • lock和unlock執(zhí)行時是原子的，指令無法亂序
    • 除了進入臨界區(qū)的線程，處理器的上的其他線程都在空轉(zhuǎn)
    • 時間片輪轉(zhuǎn)：獲得自旋鎖的線程在就緒隊列中排隊，其他線程獲得CPU會空轉(zhuǎn)，實現(xiàn)了100%的資源浪費
12. 性能的評價維度
    • 空間復(fù)雜度
    • 時間復(fù)雜度
    • scalability伸縮性：多處理器性能的度量，難以嚴謹?shù)挠嬎悖–PU功耗受溫度影響，系統(tǒng)中的其他進程）
13. 自旋鎖的特點
    • 快的時候很快：鎖的爭搶比較少，只需要一條原子指令的開銷即可獲得鎖
    • 慢的時候很慢：多個線程爭搶時，只有一個線程獲得鎖，其他的均會自旋等待。如果持有自旋鎖的線程切換或睡眠，會發(fā)生100%的cpu資源浪費（一核有難，八核圍觀）
14. 解決自旋鎖慢的問題，C語言只能做到程序的計算，無法掌控資源的切換。資源的切換必須通過系統(tǒng)調(diào)用，所以自旋鎖通常放到內(nèi)核并發(fā)數(shù)據(jù)結(jié)構(gòu)中，作為一個系統(tǒng)調(diào)用給用戶程序使用
    • syscall(SYSCALL_lock, &lock);：嘗試獲取lock，如果失敗就立即切換到其他線程
    • syscall(SYSCALL_unlock, &lock);：釋放lock，如果有等待的線程則直接喚醒
15. 吸優(yōu)去慢（工程上的優(yōu)化，通常只優(yōu)化常見的80%或者最短的木桶板）
    • Fast path：一條原子指令，上鎖成功立即返回
    • Slow path：上鎖失敗，立即執(zhí)行系統(tǒng)調(diào)用，使進程睡眠，從而減少cpu資源的占用
16. POSIX線程鎖的實現(xiàn)
    • 待定
17. 有擁堵時，進內(nèi)核

內(nèi)聯(lián)匯編

1. 內(nèi)聯(lián)匯編
   • %number：是對于輸出對象和輸入對象的順序編號

   asm [ volatile ] ( // volatile向gcc聲明該匯編代碼不需要進行優(yōu)化（可選）
           "assembler template"		// 匯編模板代碼
           [ : output operands ]   	// 輸出對象（可選）
           [ : input operands  ]       // 輸入對象，即按序為匯編指令參數(shù)中的%num（可選）
           [ : list of clobbered registers ] // 告訴編譯器該寄存器可能會被修改，要在本次內(nèi)聯(lián)匯編使用
           );
   // 示例：將a賦值給b
   int a=10, b;
   asm ("movl %1, %%eax;   /* NOTICE: 下面會說明此處用%%eax引用寄存器eax的原因
         movl %%eax, %0;"
         :"=r"(b)          // 輸出參數(shù) %0
         :"r"(a)           // 輸入?yún)?shù) %1
         :"%eax"           // 可能用的寄存器
       );   
   

同步

1. 定義：兩個或兩個以上隨事件變化的量，在變化過程中保持一定的相對關(guān)系
2. 同步電路：所有觸發(fā)器在邊沿同時觸發(fā)
3. 線程同步：在某個時間點共同達到互相已知的狀態(tài)，條件不滿足其中一方要等待。
4. 99%的實際并發(fā)問題都可以使用生產(chǎn)者-消費者進行解決
   • 生產(chǎn)者：向隊列中添加資源（任務(wù)）
   • 消費者：從隊列中取出資源（任務(wù)）
   • 其中對于共享資源的使用需要進行加鎖和取消鎖
5. 對自己的程序進行壓力測試，并編寫壓力測試的檢查程序，保證自己代碼的正確性
6. 將互斥鎖的自旋變成睡眠，直到某個條件變量被滿足時喚醒某些線程
   • wait(cv)：條件變量不滿足時，直接sleep()
   • signal(cv)：喚醒一個或多個等待的線程

   // 萬能的條件變量并發(fā)模板：可以將任何可并行算法編程并行的
   mutex_lock(&mutex);
   while (!condition) {
   	wait(&cv, &mutex);
   }
   assert(condition);
   // **********
   // 互斥鎖保證了在此期間條件變量condition總是成立
   // ***********
   mutex_unlock(&mutex);
   
   // 其他線程可能滿足時
   broadcast(&cv);
   

7. 多使用assert進行錯誤提示，可以進行bug定位

哲學(xué)家就餐問題

1. 如果所有哲學(xué)家都舉起同一邊的叉子，則所有的哲學(xué)家都會進行等待，即發(fā)生了死鎖
2. 萬能并發(fā)模板解決哲學(xué)家吃飯問題（所有人都均等的使用叉子并不好，沒有一個并發(fā)的數(shù)據(jù)結(jié)構(gòu)）

   mutex_lock(&mutex);
   while (!(avail[lhs] && avail[rhs])) {// 看左右手的叉子是否都在
   	wait(&cv, &mutex);// 有一個叉子不在，則睡眠
   }
   // 將左右手叉子都拿起來
   avail[lhc] = avail[rhs] = false;
   mutex_unlock(&mutex);// 釋放信號量
   
   mutex_lock(&mutex);
   avail[lhs] =avail[rhs] = true;// 還叉子
   broadcast(&cv);// 喚醒其他進程
   mutex_unlock(&mutex);
   
   

3. 讓一個人集中管理叉子，放棄信號量
   • 非集中式的管理共享資源，會導(dǎo)致分布式的自同步，每個線程都想試一下

// master/follower 生產(chǎn)者/消費者模型

void Tphilosopher(int id) {// 哲學(xué)家線程
	send_request(id, EAT);// 給服務(wù)員的隊列發(fā)一個消息，請求吃
	P(allowed[id]);// 等待服務(wù)員許可
	philosopher_eat();// 就餐
	send_request(id, DONE);// 給服務(wù)員的隊列發(fā)一個消息，吃完了
}

// 集中調(diào)度器：可以維護公平性（讓長時間不占叉子的線程，下次分配時等一等）
void Twaiter(){// 服務(wù)員線程
	while(1){
		(id, status) = receive_request();
		if(status == EAT){...}
		if(status == NONE){...}
	}
}

4. 在不了解系統(tǒng)的性能瓶頸之前，不要做任何的優(yōu)化

真實世界的并發(fā)編程

高性能計算

1. 計算機任務(wù)如何分解
   • 計算圖要更容易并行化（使用拓撲排序，分解有向無環(huán)圖）
   • 生產(chǎn)者-消費者解決一切
2. 問題劃分
   • 模擬宏觀世界：使用有限元模型
   • 模擬微觀世界：使用粒子模型
3. 數(shù)據(jù)中心：多副本下高可靠、低延遲數(shù)據(jù)的訪問
   • Consistency：數(shù)據(jù)要保持一致性
   • Availability：服務(wù)時刻保持可用
   • Partition tolerance：容忍機器離線
4. 每個線程做的事情：讀取——處理——寫回
5. 一個線程一次只能運行一個協(xié)程，協(xié)程不受操作系統(tǒng)調(diào)度。但是每個線程會占用可觀的操作系統(tǒng)資源。
6. 解決協(xié)程block問題：一個協(xié)程等待資源，其他協(xié)程也一起等待
   • Go同時實現(xiàn)多處理器并行和輕量級并發(fā)——goroutine（線程和協(xié)程的混合體）
   • 執(zhí)行到blockingAPI時（例如read、sleep）。
     • 成功：立即返回
     • 失?。毫⒓磞ield到另一個需要cpu的goroutine
   • 根本思想：當協(xié)程要做一件阻塞耗時的事情時，先發(fā)出資源請求的系統(tǒng)調(diào)用然后阻塞自己，yeild到另一個需要cpu資源的協(xié)程執(zhí)行，當系統(tǒng)資源準備完成時，阻塞協(xié)程重新進入就緒隊列 。這個過程中不會發(fā)生線程切換的堆棧資源開銷，幾乎每時每刻都有cpu和協(xié)程在運行，實現(xiàn)了近100%的cpu資源利用
7. 有原子操作可以實現(xiàn)條件變量，有條件變量可以實現(xiàn)任何的并發(fā)算法
8. 越底層，越自由，越容易出錯，越高效。但是大多數(shù)程序穩(wěn)定性要求要高于性能要求，所以可以使用通用的安全的接口去實現(xiàn)容易發(fā)生不安全的行為
   • 既然生產(chǎn)者-消費者可以解決絕大部分的并發(fā)問題，那提供一個安全高效的API不就可以了？

// go實現(xiàn)生產(chǎn)者和消費者模型
package main
import "fmt"
// 并發(fā)的共享隊列
var stream = make(chan int, 10)
const n = 4
 
 // 生產(chǎn)者
func produce() {
  for i := 0; ; i++ {
    fmt.Println("produce", i)
    stream <- i// 放一個到共享隊列中
  }
}
// 消費者
func consume() {
  for {
    x := <- stream
    fmt.Println("consume", x)
  }
}

func main() {
  for i := 0; i < n; i++ {
    go produce()
  }
  consume()
}

9. web前端的并發(fā)模型
   • 異步事件模型
     • 所有事件通過一個線程執(zhí)行，每個事件執(zhí)行都是原子的
     • 全局的事件隊列按序返回，其中耗時的API調(diào)用會立即返回，滿足條件時向隊列中增加一個事件
   • 缺點：多層嵌套，可維護性差。 可以通過流程圖進行事件的化重新劃分

并發(fā)bug和應(yīng)對

1. 始終假設(shè)自己的代碼時錯誤的
2. 需求 = 抽象代碼 + 規(guī)約(面試加分)
   • assert斷言機制，將代碼在運行后仍肯定存在的屬性進行內(nèi)在規(guī)約。
     • assert(對象之間的關(guān)系)，這里的對象通常是局部變量或者全局變量
   • 異常處理機制
3. 產(chǎn)生死鎖的必要條件（必須同時成立）
   • 互斥：一個資源每次只能被一個進程使用
   • 請求與保持：一個進程請求資源阻塞時，不是放已獲得的資源
   • 不剝奪：進程已獲得的資源不能強行剝奪
   • 循環(huán)等待：若干進程之間形成肉味詳解的循環(huán)等待資源關(guān)系
4. 解決死鎖的方法
   • AA型死鎖：使用防御性編程，if(holding(lk)) painc();
   • ABBA型死鎖：線程按照固定順序獲得鎖，消除循環(huán)等待條件。給鎖編號并檢查上鎖和解鎖的日志
5. 死鎖比較容易判斷的并發(fā)問題，因為死鎖會導(dǎo)致系統(tǒng)無發(fā)展
6. 數(shù)據(jù)競爭：不同的線程同時訪問同一段內(nèi)存，且至少有一個是寫
7. 并發(fā)程序的書寫
   • 無鎖的并發(fā)程序很難寫對
   • 用互斥鎖保護好共享數(shù)據(jù)可以實現(xiàn)一切并發(fā)程序
8. 并發(fā)程序
   • 互斥鎖（lock/unlock）：保證原子性
     • 如果忘記上鎖，則違反原子性（一次做完）導(dǎo)致并發(fā)出錯。例如t1-t2-t3（ABA）
   • 條件變量（wzait/signal）：保證同步
     • 如果忘記同步，則會導(dǎo)致違反執(zhí)行順序
   • 97%的非死鎖并發(fā)bug都是互斥鎖或條件變量
9. 當一個十倍程序員的前提是程序中bug極少，需要始終假設(shè)自己代碼是錯誤的
10. 要善于使用動態(tài)程序檢測工具，例如linux內(nèi)核中的動態(tài)分析軟件sanitizers （可以檢查數(shù)據(jù)競爭和非法訪問等）
11. 內(nèi)存越界檢查
    • Canary機制：犧牲堆棧頭尾的一些數(shù)據(jù)單元作為特殊標記，隔一段時間就檢查這些標記，如果被更改，則報錯
      • msvc中，為初始化的棧為0xcccc（GB2312編碼為燙燙）、為初始化的棧為0xcdcd（GB2312編碼為屯屯）

操作系統(tǒng)的狀態(tài)機模型

寫一個操作系統(tǒng)

1. 操作系統(tǒng)是程序，程序是狀態(tài)機，狀態(tài)機是狀態(tài)+指令/syscall形成狀態(tài)流

2. 計算機硬件也是一個狀態(tài)機，而軟硬件之間的橋梁是軟硬件工程師的約定（手冊）

3. 計算機的啟動(legacy BIOS方式)

   • 開機，發(fā)出一個RESET信號，RESET會初始化計算機硬件的開始狀態(tài)
     • pc初始化指向為內(nèi)存映射的ROM（0xffff0,跳轉(zhuǎn)到固件的jmp指令），ROM存儲了廠商提供的固件
     • 固件：廠商提供的代碼，可以將用戶數(shù)據(jù)加載到內(nèi)存上，如存儲介質(zhì)上的loader加載器
     • MBR（啟動磁盤的第一個512字節(jié)的扇區(qū)，末尾是55aa），cpu將mbr中啟動程序加載到內(nèi)存的0x7c00開始處

4. 如何理解一個程序，理解程序的狀態(tài)機變化，即使每執(zhí)行一條指令狀態(tài)機的變化

狀態(tài)機模型的應(yīng)用

用狀態(tài)機模型理解物理世界

1. 狀態(tài)+指令/syscall = 確定的下一個狀態(tài)
2. 時間旅行：從一個狀態(tài)回溯到之前的狀態(tài)，但是之前的狀態(tài)會進行分支一個拷貝，從而出現(xiàn)一個平行宇宙
3. strace工具可以將程序執(zhí)行的的每一條指令和syscall按序列出
4. gdb每次停下來都是停止在一個狀態(tài)上，可以使用s走一條語句，或者使用si走一條指令，查看下一個狀態(tài)
5. record full 打開gdb的記錄模式，使用rsi回溯上一條指令。但是難以回溯syscall執(zhí)行，可以使用非確定指令的結(jié)果記錄的方式進行回溯這種執(zhí)行
6. 初始狀態(tài)->確定性指令->狀態(tài)1->非確定性指令->狀態(tài)2->…
   • 確定性指令可以通過逆指令執(zhí)行，實現(xiàn)狀態(tài)的回溯
   • 非確定性指令可以通過結(jié)果狀態(tài)的快照，實現(xiàn)狀態(tài)的回溯
7. 性能優(yōu)化反問
   • 現(xiàn)在性能夠用嗎
   • 這個需要進行性能優(yōu)化嗎
   • 性能優(yōu)化的收益大嗎
8. gdb會在指令間打斷點，即入侵程序的指令來形成執(zhí)行的歷史。如何減少程序入侵
   • 程序在中斷后，內(nèi)核可以看到程序中斷前的狀態(tài)（profile軟件）

操作系統(tǒng)上的進程

1. 操作系統(tǒng)的內(nèi)核啟動：CPUReset->Firmware（ROM固件）->Boot loader ->啟動內(nèi)核kernel start()->創(chuàng)建第一個進程init
2. 操作系統(tǒng)為程序創(chuàng)建的API
   • 進程（狀態(tài)機）管理：狀態(tài)機的創(chuàng)建fork、改變execve、退出exit
   • 存儲（地址空間）管理：mmap虛擬地址空間
   • 文件（數(shù)據(jù)對象）管理
     • 文件訪問管理：open、read、write、close
     • 目錄管理：mkdir、link、unlink
3. 程序就是狀態(tài)機，所以操作系統(tǒng)在完成啟動后，會通過init創(chuàng)建操作系統(tǒng)的第一個進程（也是一個狀態(tài)機）
4. fork是狀態(tài)機整體的復(fù)制——拷貝父進程狀態(tài)，通過fork創(chuàng)建的狀態(tài)與父進程的狀態(tài)完成一樣（內(nèi)存的字節(jié)都一樣，但是地址不同），除了fork的返回值——進程的標識編號。
   • fork完成后，即存儲了多個進程，狀態(tài)機變成了并發(fā)狀態(tài)機模型
5. 本質(zhì)：操作系統(tǒng)是狀態(tài)機的管理者，虛擬化就是多個狀態(tài)機復(fù)用一個物理機
6. fork bomb

   fork(){
   	fork | fork &// fork管道給fork
   }; fork
   

7. 狀態(tài)機包含了所有進程和計算機軟硬件資源的狀態(tài)。而每個狀態(tài)機由于指令/syscall執(zhí)行導(dǎo)致出現(xiàn)新的狀態(tài)機，這些狀態(tài)機形成了執(zhí)行流
8. fork 無情的復(fù)制機器：會將進程所有的內(nèi)存和寄存器復(fù)制一份（包括庫函數(shù)的內(nèi)部狀態(tài)）
9. 標準輸出stdout
   • 輸出對象是終端，則為line buffer，以’\n’作為緩沖區(qū)一次輸出標志
   • 輸出對象是pipe/file，則為full buffer， 寫滿4096B才會將輸出一次
10. 程序是狀態(tài)機，正在執(zhí)行的程序是正在運行的狀態(tài)機，fork是創(chuàng)建狀態(tài)機的副本
11. execve(環(huán)境變量)：將狀態(tài)機重置成某個狀態(tài)，環(huán)境變量是重置狀態(tài)機的參數(shù)
12. 環(huán)境變量：應(yīng)用程序的執(zhí)行環(huán)境，在linux下可以使用env命令查看
    • PATH：可執(zhí)行文件的搜索路徑
    • PWD：當前路徑
    • HOME：home目錄
    • DISPLAY：圖形輸出
    • PS1：shell的提示符
13. 所有的進程的創(chuàng)建都需要fork，所有的進程啟動都需要一直reset即execve系統(tǒng)調(diào)用進行設(shè)置環(huán)境
14. _exit(int status)
    • 銷毀當前狀態(tài)機，并允許有一個返回值
    • 子進程終止會通知父進程
15. exit的幾種寫法
    • exit(0)：會調(diào)用atexit，終止當前進程
    • syscall(SYS_exit, 0)
      • 執(zhí)行exit系統(tǒng)調(diào)用終止當前線程
      • 不會調(diào)用atexit
    • _exit(0)：執(zhí)行exit_group系統(tǒng)調(diào)用終止整個進程

系統(tǒng)調(diào)用和shell

1. 計算機系統(tǒng)的構(gòu)建
   • 硬件NEMU：從CPUReset開始執(zhí)行指令
   • Firmware固件：加載操作系統(tǒng)
   • 操作系統(tǒng)：狀態(tài)機的管理者
     • 初始化第一個進程
     • 執(zhí)行系統(tǒng)調(diào)用
2. shell是操作系統(tǒng)內(nèi)核外面的中間殼，是人機交互的中間層?？梢詫⒂脩糁噶罘g稱為系統(tǒng)調(diào)用的語言
3. 使用man sh讀以下shell的手冊
4. shell中的管道實質(zhì)是將命令翻譯成一顆語法樹，然后再將將葉子節(jié)點翻譯成系統(tǒng)調(diào)用
   • 作用：父子進程可以共享管道，因為是一個完整的復(fù)制關(guān)系
5. 好的shell，如fish（自動補全的shell）、zsh。加入bert模型
6. 任何人機交互的程序都應(yīng)該使用大語言模型進行重構(gòu)
7. linux 的工具
   • zsh：兼容bash的shell
   • tmux：shell分屏
   • strace：追蹤系統(tǒng)調(diào)用的分析工具
8. 啟動一個shell
   • 打開一個session：內(nèi)部是很多個進程組process group，fork前后的進程都同屬于一個進程
   • controlling terminal：會建立一張進程關(guān)系表，即一個shell
   • 如果一個信號被terminal產(chǎn)生，則會相應(yīng)的發(fā)送給所有的進程組
9. 看完linux的sh手冊man sh
10. 一個功能完整的shell使用的操作系統(tǒng)對象和API
    • 控制結(jié)構(gòu)
      • session
      • process group
      • controlling terminal
    • 文件描述符
      • open
      • close
      • pipe
      • dup
      • read
      • write
    • 狀態(tài)機管理
      • fork
      • execve
      • exit
      • wait
      • signal
      • kill
      • setpgid
      • getpgid
        

什么是可執(zhí)行文件

1. 可執(zhí)行文件的使用通過系統(tǒng)調(diào)用execve實現(xiàn)， execve(可執(zhí)行文件，...)
   • 前提：execve用于狀態(tài)機的重置，重置的數(shù)據(jù)來源于可執(zhí)行文件
   • 本質(zhì)：可執(zhí)行文件是一個可遷移的數(shù)據(jù)結(jié)構(gòu)，描述了狀態(tài)機（寄存器R+內(nèi)存M）的初始狀態(tài)，elf加載器將execve中第一個參數(shù)指向的文件Reset狀態(tài)機
   • 寄存器：
     • 大部分由ABI決定，操作系統(tǒng)負責設(shè)置，如初始的PC
   • 地址空間
     • 二進制文件+ABI共同決定的，如argc和argv的存儲
2. 文件可執(zhí)行的前提
   • 具有可執(zhí)行權(quán)限x
   • 加載器能識別的可執(zhí)行文件
3. linux的執(zhí)行方式
   • 二進制文件a.out（不贊成）
   • ELF(Executable Linkable Format)
   • She-bang
4. GNU binutils查看、生成、修改二進制文件的工具
   • 生成可執(zhí)行文件
     • ld(linker)、as(assembler)
     • ar、ranlib
   • 分析可執(zhí)行文件
     • objcopy/objdump/readelf
     • addr2line/size/nm
   • 可執(zhí)行文件的運行時狀態(tài)
     • gdb
5. 調(diào)試信息
   • 將一個assembly(機器)狀態(tài)映射到C世界狀態(tài)的函數(shù)
     • 通過一個Turing Complete的指令集DW_OP_XXX
     • 可以執(zhí)行"任意計算"將當前計算狀態(tài)映射回C
   • 不完美
     • 對現(xiàn)代語言支持有限
     • 編譯器也無法保證調(diào)試信息
6. 狀態(tài)機器的編譯
   • C的語句狀態(tài)機通過語句進行轉(zhuǎn)移到下一個C語句狀態(tài)機
   • 指令狀態(tài)機通過指令/syscall進行轉(zhuǎn)移到下一個指令狀態(tài)機
   • 匯編器將指令狀態(tài)機翻譯成.o文件（描述指令狀態(tài)機），鏈接器將所有的.o文件約束成.out文件。（約束如在一個文件中只存在的聲明部分，而在另一個文件中存在的定義部分進行事后鏈接）
   • gcc將語句狀態(tài)機轉(zhuǎn)化成指令狀態(tài)機，而gdb就是將指令狀態(tài)機映射回C狀態(tài)機。匯編程序assembly將指令狀態(tài)機轉(zhuǎn)換成二進制的數(shù)據(jù)結(jié)構(gòu)和約束條件
7. 將要鏈接的未知符號的地址S+A-P=S-(P-A)
   • P-A就是現(xiàn)在的PC值，就是跳轉(zhuǎn)的目標地址減去現(xiàn)在的PC
8. 面向問題，而不是面向細節(jié)

動態(tài)鏈接和加載

1. 可執(zhí)行文件：描述狀態(tài)機初始狀態(tài)的數(shù)據(jù)結(jié)構(gòu)
   • 不同于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，指針都被偏移量所代替
   • elf定義：/usr/include/elf.h
2. 文件加載器file loader
   • 解析數(shù)據(jù)結(jié)構(gòu) + 復(fù)制到內(nèi)存 + 跳轉(zhuǎn)
   • 創(chuàng)建進程運行時的初始狀態(tài)
3. boot loader的作用
   • 引導(dǎo)扇區(qū)內(nèi)容：512B MBR + 1024B main argc + kernel（elf）
4. 動態(tài)鏈接的原因：如果每個可執(zhí)行文件都有所有庫函數(shù)的拷貝，會極大的浪費內(nèi)存空間
   • 動態(tài)鏈接庫版本無關(guān)性：調(diào)用者遵守基本的約定，與庫函數(shù)的版本無關(guān)
   • 原因：在程序運行時，找到編譯好的庫函數(shù)進行動態(tài)鏈接，即運行時才進行鏈接
5. 動態(tài)鏈接庫的功能
   • load(lib)一個動態(tài)鏈接庫
   • import(sym)一個符號
   • export(sym)一個符號
   • dsym(sym)引用一個外部符號
6. 動態(tài)鏈接本質(zhì)就是查表，先在符號表中的符號地址填入0，動態(tài)鏈接符號后，根據(jù)符號表中的符號地址進行間接跳轉(zhuǎn)
7. elf中字符串：將所有的字符串常量存放在常量池，統(tǒng)一的通過“指針”進行訪問
8. 符號表GOT和PLT：統(tǒng)一靜態(tài)與動態(tài)鏈接
9. 符號表GOT（global offset Table）
   • 作用 ：是Linux ELF文件中用于定位全局變量和函數(shù)的一個表
10. PLT（Procedure Linkage Table，過程鏈接表）
    • 作用：Linux ELF文件中用于延遲綁定的表，即函數(shù)第一次被調(diào)用的時候才進行動態(tài)綁定
    • 優(yōu)點：延遲綁定只綁定被調(diào)用的函數(shù)，沒用過就不進行綁定
11. 如果系統(tǒng)開啟了內(nèi)存布局隨機化ASLR，程序每次運行動態(tài)鏈接庫的加載位置都是隨機的，就很難通過調(diào)試工具直接確定函數(shù)的地址

Xv6 代碼導(dǎo)讀

1. UNIX - v6的現(xiàn)代版克隆：
   • 基本的工具集和shell
   • 命令執(zhí)行、管道、重定向
   • 支持多處理器
   • 支持RISC-V
2. xv6中基本的系統(tǒng)調(diào)用

3. 讀xv6的手冊，可以作為操作系統(tǒng)的實踐教學(xué)
4. 工具比什么都重要
5. vscode的執(zhí)行需要配置命令腳本，也可以在terimal中輸入
6. gdb的源代碼對照的按行調(diào)試
   • set pegination off
   • layout src
7. gdb tui

Xv6 上下文切換

1. 為什么死循環(huán)不能使計算機卡死
   • 硬件會發(fā)生中斷切換到內(nèi)核態(tài)執(zhí)行
   • 內(nèi)核態(tài)可以切換到另一個進程執(zhí)行
2. 操作系統(tǒng)的定義
   • 每個程序加載到內(nèi)存后成為進程，進程的執(zhí)行是一種狀態(tài)機的改變
   • 操作系統(tǒng)是狀態(tài)機的集合
   • 單cpu上的操作系統(tǒng)具有多個進程，可以通過時分復(fù)用進行處理
3. 協(xié)程是一種函數(shù)對象，可以設(shè)置錨點做暫停，然后再該錨點恢復(fù)繼續(xù)運行
   • 同步：因為協(xié)程本質(zhì)是函數(shù)，調(diào)用協(xié)程后原來的地方就會被阻塞，協(xié)程處理完了才返回結(jié)果，這是天然同步的
   • 并發(fā)：遇到阻塞條件時候，把cpu讓給別的協(xié)程，等條件滿足了再通過中斷可恢復(fù)的特性再繼續(xù)運行，就實現(xiàn)了并發(fā)
4. 通過協(xié)程可以在用戶態(tài)下，實現(xiàn)一個操作系統(tǒng)在用戶態(tài)的中斷。因為協(xié)程可以實現(xiàn)用戶態(tài)下的狀態(tài)機轉(zhuǎn)換
5. 進程對于持有的內(nèi)核區(qū)代碼是不可見的，只能通過系統(tǒng)調(diào)用與操作系統(tǒng)進行交互。
6. 文件描述符是進程狀態(tài)的一部分
7. 中斷和系統(tǒng)調(diào)用實際將進程的狀態(tài)進行保存，這是通過寄存器和內(nèi)存的虛擬化實現(xiàn)的
8. 操作系統(tǒng)的上下文管理和切換
   • 系統(tǒng)調(diào)用：操作系統(tǒng)開始真正處理系統(tǒng)調(diào)用/中斷時
   • 狀態(tài)機封存：所有進程的狀態(tài)機都可以封裝到操作系統(tǒng)中
   • 狀態(tài)機器處理：所有進程的狀態(tài)機使用數(shù)據(jù)結(jié)構(gòu)task_struct數(shù)組進行管理，操作系統(tǒng)可以通過數(shù)據(jù)結(jié)構(gòu)訪問每一個進程的狀態(tài)機，并修改
   • 調(diào)度并恢復(fù)：操作系統(tǒng)可以通過schedule將一個進程的狀態(tài)機（寄存器和內(nèi)存）恢復(fù)到CPU
9. 操作系統(tǒng)是狀態(tài)機的管理者
   • 再xv6中$stap控制了狀態(tài)機的內(nèi)存訪問，內(nèi)核通過分頁映射機制實現(xiàn)了虛擬內(nèi)存到物理內(nèi)存的轉(zhuǎn)換
   • 操作系統(tǒng)持有所有的物理頁面（通過$stap和CR3進行任意映射）

處理器調(diào)度

1. 時分復(fù)用中斷機制

   • 處理器以固定的頻率進行中斷
   • 中斷/系統(tǒng)調(diào)用返回時，可以自由選擇進程/線程執(zhí)行

2. 有很多進程，如wait I/O進程、等待系統(tǒng)調(diào)用的進程、可能被中斷的進程。那應(yīng)該選哪個進程調(diào)度到處理器上運行

   • 時間片輪轉(zhuǎn)：保證了公平，但是可能對于交互不好
   • 優(yōu)先級調(diào)度：使用nice值標識進程的好壞，越好的人越愿意將CPU讓給別人（幫助別人總是最先得到？idea），實時操作系統(tǒng)通常是完全的優(yōu)先級調(diào)度
   • 通常的優(yōu)先級調(diào)度：nice值低的進程得到cpu機會更多，但是所有進程都能得到CPU可以發(fā)展
   • 動態(tài)優(yōu)先級別

3. 動態(tài)優(yōu)先級MLFQ

   • 系統(tǒng)自動設(shè)置優(yōu)先級
   • 設(shè)置若干嚴格時分復(fù)用的隊列，每個優(yōu)先級對應(yīng)一個隊列
   • 用完時間片的，將優(yōu)先級調(diào)低。讓出時間片，將優(yōu)先級調(diào)高
   • 問題：每次再時間片快結(jié)束時候，就讓出CPU。（看起來是好人，實際是壞人）
   • 可以隔一段時間，進行重置或者執(zhí)行完全的時間片輪轉(zhuǎn)

4. 現(xiàn)代linux調(diào)度器CFS（complete fair scheduling）

   • 用紅黑樹維護一個有序集合
   • 原則：
     • 公平的保證：誰虧給誰補，操作系統(tǒng)盡可能的讓每個進程都獲得同樣的運行時間
     • 優(yōu)先級的保證：每個進程執(zhí)行相同的1ms，nice值大的會執(zhí)行10ms，nice值小的會執(zhí)行5ms。即通過nice作為系數(shù)增加的虛擬時間，統(tǒng)一進程在運行時間上的調(diào)度策略
   • 問題1：進程的運行中出現(xiàn)fork，子進程會直接繼承父進程的狀態(tài)。不會減少，因為如果減少，可能一直fork出現(xiàn)饑餓
   • 問題2：如果出現(xiàn)狀態(tài)慢了極大，則需要補充10秒，則會導(dǎo)致其他進程卡頓
   • 問題3：vruntime是一個一直增長的整數(shù)，如果出現(xiàn)溢出，會導(dǎo)致溢出進程從極大變成極小。

   //比較相對大小
   bool less(u64 a, u64 b){
   	return (i64)(a-b) < 0;
   }
   

   • 問題4：低優(yōu)先級的獲得互斥鎖，但是運行時間少，所以釋放互斥資源就會慢。解決：當阻塞高優(yōu)先級的進程的時候，優(yōu)先級提升到和阻塞優(yōu)先級一樣高

5. 調(diào)度策略考慮的兩個維度

   • 同等優(yōu)先級考慮公平性
   • 不同優(yōu)先級考慮優(yōu)先級

6. 一個進程可能與其他進程進行交互，相互合作完成一個事情。

   • 高優(yōu)先級：pv操作一直讓出cpu，導(dǎo)致獲得大的運行權(quán)限
   • CFS：具有運行時間的記賬，可以相對的公平

7. 多核心多線程的計算機系統(tǒng)

   • 無法實現(xiàn)真正的公平，A用戶占用一個進程，B用戶并行執(zhí)行占用1000個線程，則A用戶可能會饑餓

8. 輕量級虛擬化容器docker，創(chuàng)造操作系統(tǒng)中的操作系統(tǒng)

   • cgroup以進程組為單位管理資源，解決多用戶的cpu分配不平均問題

9. dark silicon時代的困境（基本計算機模型的改變）

   • 功率和散熱無法同時支撐所有的電路工作，總有一部分要停下來
   • 解決：大小核異構(gòu)技術(shù)，小核功耗小，大核功耗大

10. 調(diào)度器隨著硬件的異構(gòu)，發(fā)生調(diào)度算法的基本假設(shè)不斷改變。甚至出現(xiàn)CPU hot plug（熱插拔）

11. 調(diào)度器是一個中央資源向下分配的問題

12. 建模 - 預(yù)測 - 決策，每個進程對自己的需求是最清楚的，所以應(yīng)該每個進程自己提出調(diào)度策略

13. 機制是可以做出來的，但是策略是一個做的好的問題。

持久化

極限速通操作系統(tǒng)

1. 數(shù)據(jù)競爭：多個進程同時訪問一個遍歷，并且至少一個是寫的。
2. 原子執(zhí)行的宏

   #define atomic \
   	for(int __i = (lock(), 0); __i < 1; __i++, unlock())
   // 具體執(zhí)行
   // 用法：atomic { body }
   // lock();
   // i = 0;
   // check i < 1 -> yes
   // body
   // i++
   // ublock();
   // check i < 1 ->no, exit loop
   

3. 在每個代碼模塊都進行assert判斷

   #ifdef AGGRESSIVE_CHECK
   	assert(conditionJudge());
   #endif
   // 示例
   #include<stdio.h>
   #define FLAG 1
   int main(int argc,char *argv[]){
   #ifdef FLAG
   printf("hello world");// 如果FLAG不進行宏定義為1就不會打印
   #endif
   }
   

4. 使用技巧盡可能的增加assert進行檢查，沒有使用技巧盡可能的寫的簡單。炫耀技巧的地方就是最容易錯誤的地方
5. 對自己的所有代碼給最大的不信任
6. 每一個 CPU 核心都會有一個 idle 進程，idle 進程是當系統(tǒng)沒有調(diào)度 CPU 資源的時候，會進入 idle 進程，而 idle 進程的作用就是不使用 CPU
7. 寫代碼寫兩個版本
   • 基本代碼（在腦袋中清晰）：要求簡單明確
   • 高級代碼（寫代碼要檢查）：要求性能
   • 兩個代碼在輸入和輸出上應(yīng)該是等價的

持久化：1-Bit 數(shù)據(jù)的存儲

1. 犧牲了掉電后的狀態(tài)丟失，換取使用電路的高速度
2. 磁芯內(nèi)存寫入數(shù)據(jù)：行選通和列選通，行列的交點的電路最大超過閾值，將交點置為1
3. segmentation fault的以前的含義core dumped（核心已轉(zhuǎn)儲）：程序出錯，將內(nèi)存的狀態(tài)轉(zhuǎn)移到外存
4. 內(nèi)存和寄存器的狀態(tài)失去，但是持久存儲的數(shù)據(jù)仍然存儲
5. 存儲設(shè)備通常是按照塊進行存儲的，一般為4KB
6. 光盤：通過坑進行持久化存儲，eg：CD是只讀的
7. SSD：通過施加正反向的電壓進行電子的轉(zhuǎn)移，而讀盤讀取電子的狀態(tài)。容量越大速度越快
   • 可能充電多會導(dǎo)致電子無法完全排空，導(dǎo)致出現(xiàn)壞點。
   • 通過控制器進行地址映射，進行均勻的寫，或者屏蔽壞點
8. 因為硬盤的邏輯映射，所以即使磁盤格式化后（不寫滿），logic block被覆蓋，但是physical block仍然可能存儲了數(shù)據(jù)
9. 軟件安裝包定義了程序運行的初始狀態(tài)

輸入輸出設(shè)備

1. I/O設(shè)備：使計算機能夠感知外部狀態(tài)，對外實施動作。能和CPU交換數(shù)據(jù)的設(shè)備/控制器
2. 設(shè)備是交換信息的接口，交換的是狀態(tài)/命令/數(shù)據(jù)
3. 串口UART：可進可出的字節(jié)流
4. 鍵盤控制器
   • 硬編碼到兩個I/O port：0x60data，0x64status/command
5. 設(shè)備本質(zhì)是通過設(shè)備寄存器的讀寫，與CPU進行交互
6. 80386：cpu通過一個多路選擇器mux與多個設(shè)備進行連接
7. 現(xiàn)在架構(gòu)：cpu連接一個I/O設(shè)備（總線），I/O設(shè)備連接多個設(shè)備插槽，CPU告知I/O設(shè)備指令和訪問地址，I/O設(shè)備負責與具體設(shè)備進行交互。所有設(shè)備都在cpu的地址空間中，所以cpu可以通過總線訪問
8. CPU有一個中斷引腳
   • 收到某個特定的電信號會觸發(fā)中斷
     • 保存5個寄存器（cs、rip、rflags、ss、rsp）
     • 跳轉(zhuǎn)到中斷向量表的對應(yīng)項進行執(zhí)行
   • 系統(tǒng)中的其他設(shè)備可以向中斷控制器進行連線
9. DMA：一個專門執(zhí)行memcpy程序的CPU，通常直接將DMA控制器連接到總線和內(nèi)存上支持幾種
   • memory->memory
   • memory->device(register)
   • device(register)->memory
10. 將單調(diào)的工作給一個單獨的設(shè)備進行處理，如早期GPU只能執(zhí)行程序到設(shè)備圖形的映射
11. 圖形學(xué)：任何n邊形都可以分解成n-2個三角形
12. 下一個時代是異構(gòu)計算的統(tǒng)一化的時代

設(shè)備驅(qū)動程序

1. 協(xié)處理器：用于處理特殊任務(wù)的微處理器，如GPU、I/O總線···
2. 將設(shè)備進行抽象
   • 字節(jié)流設(shè)備，如terminal、打印機
   • 塊設(shè)備，如硬盤
3. linux中將設(shè)備抽象為文件
   • read：從設(shè)備的某個指定的位置讀出數(shù)據(jù)
   • write：向設(shè)備某個指定位置寫入數(shù)據(jù)
   • ioctl：讀取/設(shè)置設(shè)備狀態(tài)
4. 設(shè)備驅(qū)動程序：將程序的通用的系統(tǒng)調(diào)用序列通過翻譯成對應(yīng)的設(shè)備的驅(qū)動程序
5. 設(shè)備驅(qū)動程序是一種內(nèi)核代碼，一般是廠商，但是是內(nèi)核數(shù)量最大、質(zhì)量最差的代碼
6. 狀態(tài)機進行的取指令——譯碼——執(zhí)行
7. GPU的架構(gòu)SMT
   • 所有cpu都有各自的寄存器組，但是共享內(nèi)存和pc指針。
   • pc指針的共享可以
8. 磁盤的訪問特性
   • 以數(shù)據(jù)塊為單位進行訪問
     • 傳輸有最小單元，不支持任意的隨機訪問
     • 最佳傳輸模式與設(shè)備相關(guān)
   • 大吞吐量：使用DMA進行數(shù)據(jù)傳輸
   • 應(yīng)用程序不直接訪問
     • 訪問者通常是文件系統(tǒng)
     • 大量并發(fā)的訪問
9. 文件系統(tǒng)就是在block I/O API上構(gòu)建的持久化的數(shù)據(jù)結(jié)構(gòu)
   10.設(shè)備驅(qū)動的核心是 將read/write/ioctl翻譯成設(shè)備可以聽得懂的語言

文件系統(tǒng)的API

1. 設(shè)備在應(yīng)用程序間共享
   • 對于磁盤來說，block不是一個好的抽象
2. 磁盤、所有的應(yīng)用程序···都是字節(jié)序列，可以將磁盤抽象成應(yīng)用程序可以持有的虛擬磁盤
3. 文件系統(tǒng)：設(shè)計目標
   • 提供合理的API使多個應(yīng)用程序可以共享數(shù)據(jù)
   • 提供一定的隔離，使錯誤程序的傷害不能擴大
4. 存儲設(shè)備（字節(jié)序列）的虛擬化
   • 磁盤是一個I/O設(shè)備，是能讀/寫的字節(jié)序列
   • 虛擬磁盤是文件，是能讀/寫的動態(tài)字節(jié)序列
5. 允許任何目錄mount（掛載）一個設(shè)備代表的目錄樹
   • linux下的mount工具是mount系統(tǒng)調(diào)用的一個封裝
6. linux文件的掛載
   • 文件是磁盤上的虛擬磁盤，掛載文件是在虛擬磁盤上虛擬出來的虛擬磁盤
   • 回環(huán)設(shè)備loopback device：可以將文件映射為虛擬的塊設(shè)備。這個虛擬的塊設(shè)備可以被當作一個普通的物理設(shè)備來訪問。
7. linux下每個文件都是一個虛擬的磁盤
   • 硬鏈接：存儲直接訪問虛擬磁盤的指針
   • 軟連接： 在文件里面存儲一個跳轉(zhuǎn)提示（即使跳轉(zhuǎn)目標不存在），是一個有向圖
8. 每個進程的都有一個工作目錄，使用pwd進行查看
9. 系統(tǒng)調(diào)用open會返回一個文件描述符fd，這個文件描述符會指向虛擬磁盤
10. 系統(tǒng)調(diào)用read和write都是從指定文件描述符fd中讀或?qū)懼付ù笮〉臄?shù)據(jù)塊到指定buf中，但是讀寫完后fd會指向數(shù)據(jù)末尾
11. fork子進程時，會同時復(fù)制父進程的fd。當父子進程同時通過這個fd進行訪問虛擬磁盤時，會有一個中間的offset進行記錄。防止出現(xiàn)父子進程都從都寫出現(xiàn)交替覆蓋的情況。
12. 文件系統(tǒng)的兩大部分
    • 虛擬磁盤（文件）
      • mmap、read、write、lseek、ftruncate
    • 虛擬磁盤的命名管理（目錄樹和鏈接）
      • mount、chdir、mkdir、rmdir、unlink、open

FAT和UNIX文件系統(tǒng)

1. 數(shù)據(jù)結(jié)構(gòu)課程的假設(shè)
   • 具有隨機存取的存儲器
   • 每條指令都是O(1)的
2. 文件系統(tǒng)自底向上的基本實現(xiàn)
   • balloc和bfree的實現(xiàn)
     • balloc返回一個空閑可用的數(shù)據(jù)塊
     • 釋放一個數(shù)據(jù)塊
   • 文件（ 塊的array）的實現(xiàn)
   • 目錄的實現(xiàn)
3. 文件系統(tǒng)File Allocation Table（FAT）
   • balloc和bfree的實現(xiàn)：
     • 每個節(jié)點都有各自的指針域： 實現(xiàn)簡單，但是每塊可能不是$2^k$，單純的lseek需要遍歷整個鏈表
     • 將指針域集中存儲：指針域具有局部性，并可以放到內(nèi)存中進行緩存。但是指針域破壞后，出現(xiàn)文件系統(tǒng)損壞。（進行備份可以解決這個問題，這個指針域表稱為FAT）
   • 目錄的實現(xiàn)
     • 目錄 = 32byte定長目錄項的集合
4. 定義指定字節(jié)數(shù)量的字符

   struct BPB{
   	u8 BS_jmpBoot[3];// 3個字節(jié)
   	u16 BS_byte[8];// 16個字節(jié)
   	...
   	u8 padding[100];
   };
   // 健壯性檢查
   #ifdef ASSERT_CHECK
   assert(sizeof(struct BPB) == 119);
   #endif
   

5. FAT
   • 適合小文件，無法隨機存取，所以適合大文件
   • 會維護若干個FAT副本，防止數(shù)據(jù)破壞
6. 高性能文件系統(tǒng)EX2
   • 文件系統(tǒng)的元數(shù)據(jù)節(jié)點中的數(shù)據(jù)域，使用多級目錄進行索引。
     • 例如每個塊4KB可以存儲1024條索引項，小于4KB的文件，一個塊就可以直接所有。而大文件如4kB*1024的可以先索引一個索引塊，然后用這個索引塊進行二級索引文件
   • 如果出現(xiàn)存儲文件元信息的inode破壞，會出現(xiàn)大量文件的丟失
     

持久數(shù)據(jù)的可靠性 (RAID; 崩潰一致性; FSCK 和日志)

1. 數(shù)據(jù)結(jié)構(gòu)的假設(shè)
   • 內(nèi)存可靠并且可以接收斷電的數(shù)據(jù)丟失
   • 持久數(shù)據(jù)是不能接收丟失的
2. 磁盤冗余陣列RAID（虛擬化的力量）
   • 擁有多個不太可靠的物理磁盤，而共同組成了一個可靠性高的但容量稍小一些的虛擬磁盤
   • 容錯概率是指數(shù)級的增長
   • 反向虛擬化
     • 進程：把一個cpu分時虛擬成多個虛擬的cpu
     • 虛擬內(nèi)存：把一份內(nèi)存通過MMU虛擬成為多個地址空間
     • 文件：把一個存儲設(shè)設(shè)備虛擬稱為多個虛擬磁盤
   • 鏡像分儲：增加讀，降低寫。但是容錯
     • 將數(shù)據(jù)分成兩個部分，分別存儲不同的兩塊的磁盤
     • 讀效率翻倍：可以用滿兩個磁盤的帶寬進行讀
     • 寫效率降低：一份寫要分別寫入兩個磁盤
       
   • 交叉合并：擴容擴速但不容錯
     • 將兩個盤內(nèi)區(qū)塊交錯合并為一個虛擬盤，順序讀寫時，可以分別占用兩塊磁盤的帶寬
       
   • 底層使用鏡像分儲，高層使用交替合并。
     
   • RAID-4將鏡像存儲的數(shù)據(jù)劃分為bit位
     • $A\oplus A=0$，自身的異或值為零。
     • 如果有一個bit錯誤，則讓該部分bit數(shù)組自己異或自己，即可知道錯誤位
     • 通過一塊磁盤存儲，異或值。如果其中一塊磁盤損壞，可以進入recovery模型，進行快速計算和恢復(fù)
     • eg：99塊存數(shù)據(jù)，一塊存校驗和。讀寫速度提高99倍，容忍一塊磁盤的損壞。但是隨機寫的性能是一塊磁盤的1/2。
   • RAID-5將校驗部分交替存儲到每個盤中，提高讀取速度
3. 云計算：將多個不可靠的計算機，合并成為一個又大、又快、又可靠的云計算中心
4. 崩潰一致性（Crash Consistency）
   • 數(shù)據(jù)的寫入要并行或串行執(zhí)行很多步驟，要進行步驟的安排和算法進行保證數(shù)據(jù)可靠性
5. 磁盤調(diào)度算法導(dǎo)致，磁盤可能會不按照用戶代碼規(guī)定的順序?qū)懭?，而是進行亂序?qū)懭耄ㄏ葘懭腚x磁頭近的）
6. 狀態(tài)機的歷史
   • 每一個狀態(tài)
   • 起始狀態(tài)和每次狀態(tài)轉(zhuǎn)換的指令
7. 歷史文件操作的記錄：日志
   • 當文件操作時，先將操作記錄到日志中
   • 更新數(shù)據(jù)結(jié)構(gòu)
   • 崩潰后，進行日志檢查，將所有未完整寫入的操作重做一遍（每個操作序列做一個操作完成標記）

Xv6文件系統(tǒng)的實現(xiàn)

1. 通常文件系統(tǒng)是以4KB為單位訪問的
2. 磁盤的數(shù)據(jù)結(jié)構(gòu)
   • 目錄（數(shù)據(jù)塊的索引表）
   • 文件（虛擬磁盤塊集合）
   • 文件描述符（磁盤中的偏移量）
3. 數(shù)據(jù)的集中可以更好的利用局部性
4. vscode的使用
   • ctrl + p 輸入# 要查找的標號名稱
5. 理解一個代碼最好的方式是看它的執(zhí)行流程
6. 寫一個gdb的腳本，不需要每次調(diào)試設(shè)置環(huán)境
7. 文件系統(tǒng)的緩沖池
   • 將要讀取的磁盤塊加載到內(nèi)存緩沖區(qū)中，然后從緩沖區(qū)中對磁盤塊的鏡像進行讀寫操作
   • 當寫入的鏡像磁盤塊時，將該磁盤塊置為dirty。可不用立即將磁盤塊寫入到磁盤中，等待多個磁盤塊一起寫回
   • 使用日志保證系統(tǒng)crash后的數(shù)據(jù)一致性
8. 先寫日志，再保證日志落盤，再進行操作

現(xiàn)代存儲系統(tǒng)

1. 表格：每一行都是一個對象，每一列都是對象某個屬性的抽象
2. SQL描述出“你想做什么”，數(shù)據(jù)引擎幫你想辦法做到
3. 數(shù)據(jù)庫把數(shù)據(jù)的訪問和應(yīng)用程序的邏輯分離，可以提供原子性
4. SQL的原子性

   // 可以保證中間操作的原子性
   BEGIN  WORK;
   INSERT INTO students VALUES(...);
   INSERT INTO students VALUES(...);
   INSERT INTO students VALUES(...);
   COMMIT;
   

5. 編譯優(yōu)化：將語句編譯成等價的更快的機器語言
6. 虛擬磁盤上的數(shù)據(jù)結(jié)構(gòu)
   • 把SQL查詢翻譯成read，write， lseek，fsync的調(diào)用
   • 并發(fā)控制（事務(wù)處理）
7. cmu的15445，使用c++17寫一個數(shù)據(jù)塊
8. raft
   • 基本概念
     • 一致性：在分布式系統(tǒng)中的多個節(jié)點在狀態(tài)上達成一致，但是現(xiàn)實場景中由于系統(tǒng)崩潰等原因可能難以完成
     • leader身份：負責處理客戶端的交互請求、日志操作等，一般一個分布式系統(tǒng)中只有一個Leader
     • follower身份：類似選民，完全被動，在探測不到leader存在時，follower在超時時間過后會轉(zhuǎn)化成candidate
     • candidate身份：候選人身份，可以被選為一個新的leader
     • term：選舉任期
   • Raft選舉的三個規(guī)約
     • 超過半數(shù)投票
     • 節(jié)點只能響應(yīng)任期號大于或等于自己任期的請求
     • 同一個任期內(nèi)只能選舉一次
   • 選舉情況：A隨機時間最短，將term+1并轉(zhuǎn)換為candidate，然后投自己一票。并行給其他節(jié)點發(fā)送投票，并等待其他節(jié)點的回復(fù)。
     • 第一種：A收到大部分的投票（都包含自己的一票），則贏得選舉成為leader，并立刻告訴其他所有節(jié)點
     • 第二種： 被告知別人已經(jīng)當選，則會自行切換到選民follower身份
     • 第三種：所有節(jié)點沒有獲得大部分投票，都轉(zhuǎn)變?yōu)楹蜻x人，繼續(xù)發(fā)起投票，直到產(chǎn)生leader為止
   • 優(yōu)點
     • 通過election timeout一定程度上解決了候選人爭搶選票導(dǎo)致選舉時間過長的問題
     • Raft比Paxos算法更容易理解，且更容器工程化實現(xiàn)
9. 分布式友好的數(shù)據(jù)模型key-value
   • put(k, v)操作：可以將(k, v)直接追加到文件末尾，具有順序性
   • get(k, v)操作：需要遍歷整個文件，效率差
10. 分層存儲，讀的多的在上面，讀的少的放到下一層

android操作系統(tǒng)

1. 前端應(yīng)用比較重要的：網(wǎng)絡(luò)和人機交互
2. 對象使用棧進行存儲
3. 如何理解一個技術(shù)，需要從解決的問題和執(zhí)行過程進行理解
4. 多線程與鎖：會產(chǎn)生低優(yōu)先級線程持有資源的鎖，而高優(yōu)先級線程進行等待的情況
5. 后臺應(yīng)用程序通常優(yōu)先級低于前臺的交互程序

課程總結(jié)

1. 數(shù)理邏輯通過特定邏輯電路構(gòu)建體系結(jié)構(gòu)，操作系統(tǒng)通過端口控制體系結(jié)構(gòu)

??點此跳轉(zhuǎn)到首行??文章來源地址http://www.zghlxwxcb.cn/news/detail-468164.html

參考博客

1. 待定引用
2. 待定引用
3. 待定引用
4. 待定引用
5. 待定引用
6. 待定引用
7. 待定引用
8. 待定引用

到了這里，關(guān)于【操作系統(tǒng)筆記】南京大學(xué)jyy老師的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！