前言

學校OS課程的知識和408有一定的重疊，但是還不太夠，因此我又一次打開了王道的OS課程。

這個筆記同理，只記最關鍵的內容和思考，直接針對408，基礎性的概念性的知識以視頻為主。

計算機系統概述

OS的基本概念

OS提供的服務：

1. 用戶級別：
   • GUI，就是windows
   • 命令接口
     • 聯機：有交互性，即cmd命令行
     • 脫機：批處理，即.bat文件
2. 程序員級別：
   • 系統調用：OS的api
   • 系統調用可以通過c語言的操作系統庫函數調用，但是c語言本質上比系統調用還高一級

異步的前提是并發，程序之間交叉前進，即走走停停，無法預知。

OS的發展歷程

1. 手工階段，缺點：
   • 獨占
   • 人太慢，機器速度逐漸加快，人拖累機器
2. 單通道批處理
   • 優：提升預處理速度，不拖累機器
   • 缺：獨占
3. 多通道批處理
   • 優：解決獨占，實現并發，提升效率
   • 缺：無交互能力
4. 分時系統
   • 優：解決交互能力，用戶“看起來”獨占
   • 缺：沒有優先級
5. 實時系統
   • 優：解決了優先級響應問題，及時可靠

OS的運行機制

OS內核相當于OS的管理員，因此特權指令只能是內核執行。

平時用戶的特權調用，操作都是向管理員申請，而不是親力親為。

兩個狀態的切換：

1. 升級：特權指令觸發中斷（硬件），OS響應中斷的時候進入核心態
2. 降級：OS主動修改PSW讓出控制權（軟件）
   • 修改PSW的指令，本身就是特權指令

中斷和計組第5章銜接

涉及到進程之間的協調，就一定要OS接入，進而需要系統調用。

需要注意，陷入指令是用戶態指令（請求），接下來才會因為內中斷進入核心態（執行）

OS體系結構

我們OS學的功能，可以放在內核，也可以放在用戶，這就形成了大內核和微內核的區別。

微內核暴露的接口多，易于維護和擴展，但是溝通成本大，要反復調用。

1. 分層結構
   • 類似于計網的層次結構，結構清晰，通病是效率偏低
2. 模塊化
   • 主模塊分離，模塊之間分離，平等
     • 優點：可以同時開發，且效率不錯
     • 缺點：模塊間的圖關系很難把握
   • 動態可加載模塊。
     • 可加載說白了就是插件，有沒有都不影響運行，因此可以動態加載，比如驅動
3. 宏內核和微內核
   • 微內核相當于一個服務器，中轉不同模塊之間的`消息傳遞
4. 外核
   • 外核可以提供一些高級的資源（未經抽象的資源）分配方式
   • 內核分配的資源都是抽象的，虛擬化的，比如虛擬地址，外核可以直接分配物理地址，在一些需要頻繁跳躍的場景，外核直接分配一片連續空間效果會很好。當然，外核也負責保證安全。
   • 跳過虛擬步驟，就相當于跳過了映射層，可以提高效率，缺點是復雜。

OS引導

簡單來說，就是開機掃ROM就可以把操作系統拉起來，但是具體還是要分幾步走：

1. 掃ROM，啟動BIOS，自檢
2. 讀磁盤的MBR，獲取分區
3. 從活動分區（C盤）中讀PBR，獲取C盤根目錄
4. 通過目錄找到操作系統的程序，拉到內存中，完成OS啟動

這四步環環相扣，前一個獲取了信息，后一步才能根據此信息行動。

而第4步用的程序，位置一般在C:/Windows/Boot/下面。

虛擬機

1. 第一類VMM，相當于傳統OS的加強版，直接運行在硬件上
   • 虛擬OS看起來像一個OS，也有內核，但是實際上還是用戶態，因此一個特權指令實際上要經過一次虛擬的系統調用+一次真正的系統調用。
   • 遷移性差，因為直接和硬件耦合
2. 第二類VMM，是寄居在宿主OS之上的，分為兩部分
   • 用戶態的VMM和宿主的應用程序是共存的
   • 核心態的VMM是以驅動的形式存在的，持續運行在內核態

進程和線程

進程和線程基礎

進程

PCB，記錄進程元數據：

1. 描述信息。用于區分進程，PID，UID
2. 進程控制和管理信息。和進程運行狀態有關
3. 資源分配清單。
   • 資源是進程外部的，而數據段是程序產生的內部數據
4. 處理器相關信息。寄存器上下文

進程特征：

1. 并發性和異步是一起的
2. 結構性指的是每個進程的結構都一樣，都是PCB+數據段+程序段

進程狀態

進程控制

創建原語分為4步：

1. PCB創建和初始化
2. 分配資源（此時進入就緒態）
3. 插入就緒隊列

撤銷是逆過程：

1. 剝奪所有資源，清理子進程
2. 刪除PCB

阻塞和喚醒，是可逆的過程

1. 修改PCB：可逆，所以現場要保護起來
2. 切換隊列：把PCB放到對應隊列中

無論是阻塞還是進程切換，都要剝奪CPU，而進程有一些內容還存在寄存器中，這些寄存器上下文就是保護現場要做的工作，是中斷隱指令的內容。

進程通信

1. 共享儲存
   • 把兩個進程的虛擬儲存，映射到同一個物理儲存區域
   • 因此要互斥訪問
2. 消息傳遞
   • 每一個進程都有一個消息隊列
   • 直接通信：A進程把消息直接掛到B進程消息隊列里
   • 間接通信：以信箱為中介，B要主動去信箱取出A發來的消息
3. 管道通信
   • 聯系生產者消費者，管道其實就是一個循環隊列，是個內存緩沖區
   • 管道互斥訪問，因此是半雙工（像水管）

線程

1. TCB：Thread CB
2. 一個進程內部，線程之間資源共享
   • 因此切換成本很小，其就是為了頻繁切換，提高并發性而生的。
3. 一個程序的多線程可以放到不同進程中
   • 多核CPU的超線程
   • 但是這樣就無法共享資源了，各用個的

線程可以理解為剝離掉公用資源后，剩下的相互獨立的部分

因此線程的內容比較少，切換的時候只需要保證TCB里面的一些寄存器上下文就可以，比進程少很多。

線程實現

用戶級線程，適用于早期OS沒有線程管理功能的時候：

1. 本質上是用戶自己用代碼（線程庫）管理線程的調度
   • 在OS看來，只有一個進程而已
   • 線程的調度是純用戶態行為，這種調度非常簡單（線程庫的邏輯）
2. 優缺點
   • 優：不需要系統調用，高效
   • 缺：假線程，代碼在一個線程卡住，實際上都卡住了

內核級線程，這是經典的OS負責的線程：

1. 優點：真并發
2. 缺點：核心壓力大

因此內核級線程又分出多種模式：

1. 一對一
   • 這其實和內核級線程一樣
2. 多對一：多個用戶級線程對應一個內核線程，而CPU只能看到內核線程
   • 這個模式比較雞肋，和用戶級線程一樣
3. 多對多：多個用戶級線程，映射到多個內核線程
   • 這才是真神
   • 可以把用戶線程切分成3塊，每一塊都用多對一模型映射到一個線程，整體上三個部分有序工作，互相之間不會拖累，兼顧了效率和并發性

CPU調度

調度的層次

作業調度，作業≈一個程序，儲存的位置是外存，作業調度≈程序啟動
低級調度，針對進程，切換CPU

中級調度，和作業調度一樣都是在內外存之間的，區別如下：

1. 作業調度是比較徹底，就是啟動和終止
2. 中級調度類似于休眠（掛起），暫時放到外存（手機的擴展內存技術就是這樣實現的）
   • 引入7狀態模型，對就緒和阻塞分別增加對應的掛起狀態
   • 在掛起狀態（外存里），也可以實現阻塞到就緒的轉變
   • 從運行態可以跳過就緒態，直接跳到掛起

進程調度細節

進程調度時機：

1. 主動
2. 被動。說白了就是被搶占
   • 中斷處理（中斷隱指令）和原子操作，都會關中斷，因此不會被打斷
   • OS內核處理內核臨界區的時候，權限高，不可被打斷

區分一下：

1. 狹義進程調度。在CPU空閑的時候，抓一個就緒態進程激活
2. 進程切換。剝奪一個運行的進程，換成另外一個進程
   • 兩個操作都要恢復新現場
   • 相比于調度，切換額外要做的操作是保護舊現場

廣義的進程調度，可能包含了進程切換這一過程

最后提一嘴調度程序，我們說，調度是由OS控制的，本質上就是軟件，那么說白了，負責調度的管理者，還是一個程序。

這個程序什么時候會運行呢？

1. 如果是非搶占的時候，就是異步的運行，在特殊情況才運行（創銷，阻塞喚醒）
2. 搶占式的，那么就要定期巡查，決定一個CPU是否應該搶占

調度算法

評價指標

1. 周轉時間=等待+處理時間
2. 帶權周轉時間
   • 本質上是個比例值，可以衡量等待時間在周轉時間中的占比
   • 越大，則等待越久
3. 等待時間。
   • 執行之前的時間，執行起來后等IO的時間不算
   • 作業的等待時間是在成為進程之前的那段時間
   • 進程的等待時間就是創建態+就緒態的那段時間
4. 響應時間
   • 和等待時間類似，但是針對的只是一種請求，比如鍵盤，鼠標

批處理調度算法

對于非純計算程序，IO時間不算等待，因此還要拋去IO操作的部分。

FCFS（其實就是FIFO），之所以對短作業不利，就是因為短作業的帶權周轉時間會很大，這代表其體驗很差。

短=Short，即SJF，SPF

具體計算，要分為三部分：

1. 還沒來的作業
2. 作業池中的作業
3. 正在運行的作業

正在運行的作業只能在作業池中挑選，而不能是還沒有進入作業池的，因此第一個任務只能是P1，即使他時間很長。

SJF分兩種：

1. 非搶占式的SJF如上
   • 比較簡單，順序操作
   • 只需要在作業完成時，分析作業池即可
2. 搶占式的SJF（SRTN）
   • 如果有一個新的作業來了，那么就有可能比當前正在運行的作業的剩余時間短，此時就把作業替換回作業池中（記得標注剩余時間）
   • 具體做題的時候，比非搶占式要額外多分析新作業來的時間點

1. 題目區分細節
   • 默認非搶占，但是比較模糊
   • 考慮到搶占，SRTN的平均周轉時間肯定是最少的
   • 如果默認作業沒有到達順序的先后之分，那么非搶占SJF=SRTN
2. SJF對長作業不利，無論是否搶占，都可能造成饑餓現象

HRRN用到響應比指標，綜合了等待時間和處理時間，在保證了優先級的前提下，修復了SJF饑餓的問題。

分析思路和SJF類似，都是分成三部分，HRRN為非搶占式的，所以只在CPU空閑的時候對作業池進行分析。

注意，其等待時間是從到達開始計數的。

交互式調度方法

RR（時間片輪轉）

1. 輪轉本身很簡單
   • 建立一個就緒隊列，每一個時間片出隊，處理隊頭對應的進程
   • 時間片完了以后就插到隊尾
2. 難在新任務來的時候，會改變隊列結構
   • 新任務來了，也是插在隊尾
   • 如果A任務的時間片完了，此時B任務剛來，這二者的順序以B為先，畢竟新來的要照顧一下（注意，這個照顧順序只針對想要同時入隊的兩個任務，前面早就在隊里的任務仍然在前面）
3. 如果任務處理完，時間片還沒用完，會直接終止當前時間片
   • 很正常很人性化的設計，干等著沒意思

因此，整個分析過程需要考慮的也是處理完以及新任務剛來的兩種時刻。

嚴格來說，RR不會剝奪正在執行的時間片，但是先來先插到隊尾的這種邏輯，以及規定時間片用完就剝奪，這兩個操作具有搶占性，所以我們規定RR是搶占式的（剝奪的來源是時間片本身，而不是其他進程）

時間片太大，就會退化為FCFS，太小則切換開銷占時間片的比例就太大了（類似于流水線那個感覺），效率降低。

優先級調度算法。優先數越高，就越排在前面激活。

此方法分為搶占式和非搶占式。
分析節點參考SJF。

多級反饋隊列調度，這個是666，真神

我們直接分析一下其性質，相當復雜，但是又相當合理：

1. 隊列內部是RR，隊列之間是搶占
2. 關于優先級
   • 新手保護：剛來的，優先級最高
   • 耗時降級：如果耗時長，每完整執行一個時間片，優先級就會降低一級，直到降無可降
   • 被剝奪不降級：被剝奪嚴格來說不算執行完一個時間片，因此不降級，只是按RR原則放到了隊尾。不過還會有補償，新獲得的時間片又是一個完整的時間片
3. 關于輪轉
   • 優先高級：高一級的隊列為空，才對下一級進行RR遍歷（有搶占性，如果高一級來了新的，則立馬切到高一級）
   • 保障低級：越低級，時間片越長。雖然低優先級低人一等，但是總得讓人家執行完，所以低優先級的時間片反而會更多，一旦輪到了，就可以持續執行很長時間（當然，如果你不爭氣，執行不完那就繼續降級，又或者被強占，總之還是低人一等）

優缺點分析：

1. 公平：FCFS
2. 快響應：RR+優先級調度
3. 短進程優先：SPF
4. 自動優先級
   • 如果想要保證任務的高優先級，可以盡量讓其不降級，比如如果進程因為IO主動放棄時間片，此時我們不認為其執行完畢，因此不降級，這樣就保證了IO的高優先級
5. 缺點：仍然不是絕對公平，因此會造成饑餓

在具體實踐中，為了防止饑餓出現，可能一個隊列會分配固定的時間上限，如果超過這個界限，還是要切換隊列的，不能一直卡在高優先級隊列。
此外，不同隊列內部的策略還可以不一樣。

同步與互斥

基本概念

異步就是無序性
同步就是有序性，A一定在B前。

遵循的原則，總結起來就是，忙可以先等一下，等久了就撤（讓權），但是你不能讓我等太久，過一段時間我還得拿回權利并且進入臨界區。

互斥

互斥軟件實現

單標志法是最原始的輪詢

本質上，turn代表謙讓以及指定，剛開始就指定一個進程，而一個進程執行完以后又會指定另外一個進程。
但是其問題在于，臨界區使用權和CPU占用權是分裂的，讓給你用，并不代表你就能用，即空閑也進不去，違背“空閑讓進”

比如此時標記0進程能用臨界區，但是此時CPU時間片屬于1，此時while循環就會持續1個時間片，一邊是忙等，另一邊是空閑沒人用

雙標志法，把謙讓邏輯變成了，將指定變成了排他邏輯，占用邏輯。

占用和釋放，只修改自己的占用標記，不去指定他人。

雙標志先檢查，檢查和上鎖不連貫，此時，按照1526順序，A還沒上鎖，B就通過檢查了，就會同時進入臨界區，即“忙”也能進去，違反了忙則等待。

為了修正，出現了雙標志后檢查法，這種方法先把臨界區標記了，再檢查，那么就可以確保別人拿不到臨界區（缺德做法），但是這很明顯不靠譜，會出現都用不上的情況，按照1526順序，AB都標記，則會排他，那么AB就都會卡在檢查階段。

此時，即使臨界區空閑，AB誰也不讓著誰，誰也用不上，這違背了“空閑讓進”，而且一直卡死，違背了“有限等待”

peterson算法，綜合了單標志和雙標志后檢查法

標志代表意愿，turn代表謙讓，最后被謙讓的那一個，就可以獲得使用權。

以1627舉例，2先謙讓一下，但是7后面有謙讓一下，于是2就勉為其難的進入了，和現實的套路一模一樣。
本質上，turn同一時間有且只能有一個值，因此同一時間只能有一個進程跳出循環，且必有一個進程跳出循環。

非常牛逼的思路，但是仍然優缺點，因為進程仍然是忙等狀態，即違反了“讓權等待”，但是已經是成本最低的了，這個操作可以通過時間片輪轉來剝奪。

互斥硬件實現

關中斷的缺點：

1. 多處理機，關不了其他CPU，進程可以借助其他CPU訪問臨界
2. 僅內核。因為這個操作給用戶太危險

TestSet的操作，說白了就是用old檢查，并對lock進行上鎖，這是一個原子過程，檢查和上鎖是一氣呵成的。
如果lock原來就是true，那么再上也無所謂
如果lock原來是false，那么就可以同時實現上鎖+退出循環，不用擔心被打斷

上面這個代碼只是模擬，實際上是硬件TSL指令實現的，是原子的，而軟件編程是無法達到這個效果的。
缺點和peterson一樣，都是忙等，不滿足“讓權等待”原則

還有一個Swap指令（Exchange，XCHG指令），和TSL基本一樣的邏輯和特性

互斥鎖（自旋鎖）

互斥鎖是一種思想，和mutex操作很像，就是申請和釋放。

但是其申請過程是忙等的，所以TSL，swap指令都是自旋鎖，單標指法其實也是自旋鎖，申請過程都具有原子性

當然，正如單標志法哪里說的，忙等其實不完全忙等，時間片沒了就退出（單處理器沒有RR，所以就是徹底忙等）。甚至說有時候反而有意外效果，等待的時候不用切換上下文，有時候成本反而低。

信號量

信號量機制

整形信號量，說白了就是雙標志先檢查，但是P和V是原語，可以保證不會同時進入

但是因為底層還是一個循環，仍然會忙等，不滿足讓權等待。

記錄型信號量引入阻塞隊列，解決了忙等現象

1. 原來是忙等，現在發現資源不夠就丟到阻塞隊列里。
   • 極限情況為0，-1后為負，此時是第一個進程阻塞
2. 如果資源夠了，且阻塞隊列里有進程，就喚醒
   • 極限情況為-1，+1后為0，此時把阻塞隊列里最后一個進程喚醒

信號量實現互斥同步

semaphore mutex = 1 ：代表記錄型信號量，有等待隊列

互斥比較簡單，mutex=1，PV夾住臨界區。

同步是前V后P，用一個信號量關聯兩個進程，等V操作執行完后，P才能執行下去。

給定一個拓撲圖，只需要把每一個前驅后繼關系都用一個信號量定義一下即可。
之后每一個節點都是一個進程，把邊定義的前驅后繼關系寫到進程里面即可：

1. 入邊寫P
2. 出邊寫V

經典信號量問題

生產者消費者——基本的分析思路

需要注意一個細節就是，P操作是不可互換的，因為mutex只夾臨界區，夾得多了就會出問題（死鎖）
V操作可以互換，因為V操作一定不會被卡住

多生產者多消費者——多種生產者

首先是最簡單的兩組關系：

1. apple和orange各自有一對同步關系
2. plate關系：關鍵在于盤子，盤子是雙方的一個中介，并不能單看父或者母，要把父母統一為一方，把子女統一為另一方
   

具體實現如下，三個同步信號量，這里將plate設置為“還可以放的空間”，因此初值為1

因此，整體就實現了一個PV結構，每一個進程，都是有P有V。
mutex實際上可有可無，因為我們這里的資源上限為1，已經相當于mutex的作用了，但是如果盤子空間變成2，就得加mutex了，否則就可能發生覆蓋現象。

如果反過來呢，plate=盤中可用水果數量，會出問題，比如dad，此時就是V（apple），V（plate），可以看到這個進程是沒有P的，也就是說不會被阻塞，他可以一直釋放。

所以我們這里還可以總結出一條生產者消費者問題中，隱性的要求，就是PV一定是要成環的，相互制約，一個進程只有V無P，必然是有問題的，在我們制定信號量意義的時候，也應該考慮構造一個PV環結構。

吸煙者問題——多功能生產者

一個多功能生產者，給多個單功能消費者提供原料，同步關系如下

再拓展一下思路，如果finish定義為1呢？

那么就要把生產者的P操作放在最開始，消費者是不變的，仍然可以正常運行（因為仍然是PV環，而且PV關系沒有變）

分析一下是否需要mutex，因為只有一個生產者，所以緩沖區最多有1個元素，不會出問題。
但是呢，如果有n生產者，此時因為生產者是V在前的，第一次生產不受阻塞，所以就可能會讓緩沖區里存在n個元素，所以這種寫法其實不好，如果是按照我那個P在前的寫法，即使是有多個生產者進程，只要規定finish=1，就只能有一個元素被生產

哲學家進餐問題——連續申請多個資源

這個問題本身不難，難在如何解決死鎖。

哲學家進餐問題的死鎖情況為，每個哲學家都只P了一半，都卡在了第二個P上。
本質上，哲學家進餐是連續申請多個資源，如果申請的途中被卡了，而且是集體卡頓，那就死鎖了。

所以解決哲學家死鎖，就要從這些領域入手：

1. 最多讓n-1個哲學家同時進餐，這樣就一定可以保證有1個哲學家不會被卡死
   • 可以用一個值為n-1的信號量限制
2. 限定哲學家拿資源的順序，強制哲學家進行兩兩競爭
   • 比如指定奇數哲學家先左邊的，偶數先拿右邊的，那么這一對哲學家必然是兩個必有一個阻塞，而另一個沒被阻塞的哲學家，在另一邊不存在競爭，一定可以吃到
3. 保證哲學家多個P操作的原子性
   • 在一連串P外面加個mutex即可
   • 即使一個哲學家被卡，其他哲學家也不可能是P操作被卡，即其他哲學家在吃飯，這是暫時的，可以恢復的

讀者寫者問題

死鎖