操作系統(tǒng)

OS對資源的管理，就是對硬件+軟件兩種資源的管理。
硬件：CPU+存儲（主存）+裝備
軟件：文件（系統(tǒng)）
這就是操作系統(tǒng)的4個章節(jié)。

進程線程

單核達不到程序級并行，但可以到達指令級并行（pipeline）。

進程

基礎

概念：
目的：為了實現并發(fā)，要不然直接傻瓜調度就好了，就不需要進程了。
進程與程序的區(qū)分：動態(tài)vs靜態(tài)；進程有PCB；2者多對多（1個進程可以觸及多個程序–>通過系統(tǒng)調用；1個程序可以對應多個進程–>通過量次履行）

進程狀態(tài)

狀態(tài)：運行，阻塞（等待除CPU的資源，如IO，內存等），就緒（等CPU），還有創(chuàng)建&終結
3個核心狀態(tài)構成4條有向邊：
1. 運行 –> 阻塞：等待IO等資源；
2. 阻塞 –> 就緒：IO等資源完成，等待CPU；
3. 就緒 –> 運行：終究搶到了CPU；
4. 運行 –> 就緒：時間片用完了。。。

另外，新建（fork）以后進程處于就緒狀態(tài)，運行完落后程也可能直接變成結束狀態(tài)。

進程控制塊

是1種數據結構。
包括PID，進程狀態(tài)，優(yōu)先級，現場保存區(qū)，所需資源已分配資源，調度信息等。現場保存區(qū)就是釋放CPU時，用來記錄CPU此時的寄存器、程序狀態(tài)字等狀態(tài)的。
創(chuàng)建進程就是創(chuàng)建PCB，殺死進程就是撤消PCB ==> PCB就是進程存在的標志和唯1代表。它包括了進程的狀態(tài)調度和控制此進程的所有信息。
進程 = 程序段 + 數據塊 + PCB

進程控制

即：創(chuàng)建，撤消，狀態(tài)轉換。
原語primitive
創(chuàng)建start() 撤消exit() 阻塞await() 喚醒notify()
撤消原語撤消的是PCB而不是程序段，由于程序段有可能被幾個進程同享。

進程間通訊 IPC

管道、信號、消息隊列、同享內存、信號量、套接字 等
Pipe：比如cat -A hello.cpp | head，只能承載無格式字節(jié)流；
Signal：比如9號代表SIGKILL，所以有kill ⑼ xxx；
消息隊列：是消息的鏈接表，克服了信號承載信息量少，管道只能承載無格式字節(jié)流和緩沖區(qū)大小受限等缺點；
同享內存：多個進程可以訪問同1塊內存空間，是最快的可用IPC情勢。是針對其他通訊機制運行效力較低而設計的。常常與其它通訊機制，如信號量結合使用，來到達進程間的同步及互斥。
信號量（semaphore）：主要作為進程間和同1進程不同線程之間的同步手段。
Socket：更加1般的進程間通訊機制，可用于不同機器之間的進程間通訊。

進程調度

先來先服務FCFS、輪轉（時間片）、優(yōu)先級法（優(yōu)先級高的弄完了再釋放CPU）、分級輪轉（優(yōu)先級+時間片：多個優(yōu)先級不同的隊列，先處理優(yōu)先級高的隊列）

進程同步、互斥

信號量機制可以用來解決進程的同步與互斥問題。
臨界資源：某些時段只能允許1個進程使用的資源。
臨界區(qū)：訪問臨界資源的程序段。臨界區(qū)是代碼，代碼段。

同步

也叫直接制約關系。進程間協同工作，有前后次序。

互斥

也叫間接制約關系。訪問臨界資源時。

原則

空閑讓進，忙則等待（兩句空話，無需解釋）
有限等待，讓權等待（正解！對要求訪問的進程，應保證能在有限時間內進入臨界區(qū)；如果進不去臨界區(qū)，應當立即釋放處理器，避免忙等待）

整型信號量（lock/unlock原語）

整型信號量被定義為1個用于表示資源數目的整型量S。
wait和signal操作可描寫為：

缺點：很明顯，缺點就是違背了“讓權等待”原則，信號量S<=0時，會不斷循環(huán)測試，進程處于忙等狀態(tài)。

記錄型信號量——P/V操作

之所以叫記錄型信號量，是由于信號量不再是單純的1個整形來表示，而使用1個結構體：

相應的wait(S)和signal(S)的操作以下：

wait操作，S.value–，表示進程要求1個該類資源，當S.value<0時，表示該類資源已分配終了，因此進程應調用block原語，進行自我阻塞，放棄處理機，并插入到該類資源的等待隊列S.L中，可見該機制遵守了“讓權等待”的準則。

signal操作，表示進程釋放1個資源，使系統(tǒng)中可供分配的該類資源數增1，故S.value++。若加1后還是S.value<=0，則表示在S.L中仍有等待該資源的進程被阻塞，故還應調用wakeup 原語，將S.L中的第1個等待進程喚醒。

利用信號量實現進程同步

利用信號量實現進程互斥

利用信號量實現先驅關系

具體參考信號量：整型、記錄型信號量和利用信號量實現進程互斥和先驅關系
TODO：生產者消費者 銀行家 等

管程

P/V操作有效，但是是低級的，如果不由程序員來控制完成，才是ok的。
管程，就是用來管理臨界資源的。
為了訪問臨界資源，管程每次只允許1個進程進入其內，不過這無需程序員操心，由編譯器保證。所以很高級。

死鎖

死鎖的條件：
1. 互斥；
2. 不剝奪；
3. 要求和保持；
4. 環(huán)路等待。

即：有爭取的東西；他人正在用東西的時候你不能侵占；沒拿全所需的東西的時候，已拿到的也不放手；最后大家都相互等待循環(huán)等待，gg。

Attention：環(huán)路等待和死鎖的關系。
死鎖，1定是出現了環(huán)路等待。但是環(huán)路等待未必會死鎖。
例如：兩個人要上廁所，需要穿鞋，有1只L鞋子，1只R鞋子。A拿到L，B拿到R，則環(huán)路等待，兩人都走不了路，死鎖。但是如果有兩只L鞋子，1只R鞋子，從等待關系上來看，兩個人還是會構成環(huán)路等待圈，但是其實不會死鎖。由于B可以集齊1套，用完以后釋放1只L1只R，此時A就能夠的到R，愉快上廁所=.=
所以：只有系統(tǒng)的每類資源都只有1個時，環(huán)路等待才等價于死鎖。

對待死鎖，有：死鎖預防、死鎖避免、思索檢測與消除。

預防死鎖（太守舊，寧可資源閑置，因此效力低）

資源獨占：斃掉3,即必須拿到所有的資源才能運行，如果拿不全的話，那就不拿。
缺點：資源利用率低，系統(tǒng)資源被嚴重浪費，其中有些資源可能僅在運行早期或運行快結束時才使用，乃至根本不使用。而且還會致使“饑餓”現象，當由于個別資源長時間被其他進程占用時，將導致等待該資源的進程遲遲不能開始運行。
資源順序分配：只要進程提出申請分配資源Ri，則該進程在以后的資源申請中，只能申請編號大于Ri的資源。
好處：提高資源利用率
缺點：問題是編號必須相對穩(wěn)定，這就限制了新類型裝備的增加

死鎖避免（介于“預防”與“檢測”之間，尋覓可能的安全順序）

銀行家算法：看看借出去的租能否收回來。如果全都借出去還滿足不了對方，不能收回來，那就先不借出去。

死鎖檢測與接觸

資源分配圖：要求邊、分配邊
死鎖定理：資源分配圖不能完全簡化 <==> 死鎖
實質上是如何讓釋放資源的進程繼續(xù)運行
資源剝奪法：掛起某些進程。被掛起的進程不能1直掛著處于“饑餓狀態(tài)”，餓死了怎樣辦。。。
撤消進程法：撤消某些進程。根據優(yōu)先級和撤消的代價決定。

線程

目的：進1步提高程序并發(fā)度，提高系統(tǒng)吞吐量
資源同享，減小開消，更好的并發(fā)性
進程是資源分配的基本單位，線程是CPU調度的基本單位。
進程有自己的地址空間，即便崩了也不會影響其他進程；線程沒有單獨的地址空間（但有自己的堆棧&局部變量），線程崩了全部進程就崩了。所以多進程比多線程更硬朗，但資源消耗太大，效力太差。
進程有自己的數據空間，所以進程間數據的傳遞需要進程間通訊；線程沒這么麻煩，同1進程下的線程同享進程的代碼段、數據段、系統(tǒng)資源（打開的文件等）等。

others

孤兒進程vs僵尸進程
爸爸gg了，孩子就是孤兒進程；孩子gg了，爸爸不去收尸，孩子就成了僵尸進程。
所有的進程（init進程除外）gg后都會經歷僵尸進程，等待爸爸來收尸^_^。
進程的TASK_ZOMBIE狀態(tài)：進程滅亡，PCB還在task數組中。發(fā)送信號給父進程，父進程釋放其task_struct結構。

存儲管理（內存）

地址轉換
相對地址（邏輯地址/地址空間）：源代碼編譯成的目標代碼中的地址
絕對地址（存儲空間）：可履行代碼在物理內存中的實際地址
地址重定位（地址映照）：邏輯地址 –> 絕對地址

靜態(tài)重定位
程序履行之前進行的定位，直接修改存有地址的源碼

動態(tài)重定位
程序履行進程中的地位，裝入代碼后，拿相對地址加上起始地址便可。

分區(qū)存儲管理

固定式分區(qū)

頁式存儲管理

MMU

存儲管理部件MMU，Memory Management Unit，有時稱作分頁內存管理單元（paged memory management unit，縮寫為PMMU）。它是1種負責處理CPU的內存訪問要求的計算機硬件。它的功能包括虛擬地址到物理地址的轉換（即虛擬內存管理，將虛頁號轉換為物理頁號，頁內偏移不用改動）等。

快表TLB

頁表在主存，1次讀寫操作需要兩次訪存。第1次從內存訪問頁表，獲得物理地址，第2次才是真實的根據物理地址獲得內存中的數據。
所以將1部份頁表放入cache，成為快表。就變成了1次“訪緩”+1次訪存。固然如果“訪緩”沒找到相應的頁，還得去主存中訪問頁表。（如果根據頁表得到的頁不在主存中，還需要產生缺頁中斷，由中斷處理程序將相應的頁從磁盤調入主存）

內存管理單元通常借助1種叫做轉譯旁觀緩沖器（Translation Lookaside Buffer，縮寫為TLB）的相聯高速緩存（associative cache）來將虛擬頁號轉換為物理頁號。當后備緩沖器中沒有轉換記錄時，則使用1種較慢的機制，其中包括專用硬件（hardware-specific）的數據結構（Data structure）或軟件輔助手段。這個數據結構稱為分頁表，頁表中的數據就叫做頁表項（page table entry，縮寫為PTE）。物理頁號結合頁偏移量便提供出了完全的物理地址。

段式存儲管理

段頁式存儲管理

覆蓋技術&交換技術

目的：利用外存來邏輯地擴充內存。

覆蓋技術

鐵定不會同時履行的程序段同享1個內存區(qū)域。不履行的先放在磁盤上。
對用戶要求太高，需要用戶指定哪些可以相互覆蓋，不人性化。

交換技術

也叫滾入滾出，roll-in, roll-out
需要動態(tài)重定位機構支持，即再度滾回來時不1定還是之前的內存地址。
交換技術對用戶透明，good！

虛擬存儲管理

以兩個技術為基礎——局部性原理、虛擬頁式存儲管理。

局部性原理

時間（循環(huán)/子程序/棧）&空間（順序履行/數組遍歷/相鄰寄存）

虛擬頁式存儲管理

邏輯地址空間很大，實際主存有限。需要時調入主存便可。
缺頁中斷

頁面置換算法
1. 先進先出FIFO；
2. 最近最久未使用LRU；
3. 最優(yōu)算法OPT：foresee，impossible。

Linux的內存管理

地址空間大于主存物理空間
進程保護：每一個進程都有自己的虛擬地址空間，即便gg了也不會相互影響
虛擬內存可以隔離進程的地址空間，那末如果不同進程的虛擬地址映照到同1物理地址，就能夠實現內存同享，這就是同享虛擬內存！既可以節(jié)省物理內存，又可以實現進程間通訊。

IO

PCI總線：Peripheral Component Interconnect總線，外圍裝備互連總線。將CPU和存儲器連接到快速裝備和擴大總線上。
所以說PCI不是總線，是“外圍裝備互連”?！癙CI總線”才是總線。

控制器
很多IO裝備都有自己的控制器。
CPU操縱控制器，使裝備完成I/O傳輸。

IO方式的演化

1. 循環(huán)等待（忙等待）；
2. 中斷；
3. 直接內存訪問DMA；
4. 通道Channel。

循環(huán)等待

CPU不停掃描裝備控制器中的寄存器的狀態(tài)，明顯耽誤了CPU干正事兒。

中斷

CPU上有中斷要求線。
裝備接收CPU指令開始傳數據，緩沖寄存器滿了就開始產生中斷，CPU不能不來處理中斷，親身轉移這些數據。每一個字在存儲器與I/O控制器之間的傳輸都必須經過CPU,這就致使了中斷驅動方式依然會消耗較多的CPU時間。

中斷屏蔽 中斷向量表 中斷優(yōu)先級

中斷用于處理異步事件和系統(tǒng)調用（用圈套方式進入內核的管態(tài)）。

直接內存訪問

用于大容量傳輸裝備。
CPU通知數據傳輸的起始結束位置和大小，DMA將數據從裝備傳到內存（需要占用內存總線，暫時制止CPU訪存），弄完了就給CPU發(fā)出中斷，告知它完事兒了。

中斷 vs DMA
中斷的話，數據緩沖寄存器滿1次就得中斷CPU1次，CPU得親身轉移這批數據；DMA則是將所有數據傳輸終了后，才中斷CPU，減少了CPU的終端次數，而且數據傳輸不經過CPU。完全解放了CPU。

通道

通道是1個獨立與CPU的專門負責IO的PU。有自己的通道指令。
I/O通道方式是DMA方式的發(fā)展，它可以進1步減少CPU的干預，即把對1個數據塊的讀寫為單位的干預，減少為對1組數據塊的讀寫及有關的控制和管理為單位的干預。

I/O通道 vs 1般處理機
通道指令的類型單1，沒有自己的內存，通道所履行的通道程序是放在主機的內存中的，也就是說通道與CPU同享內存。

I/O通道 vs DMA
DMA方式需要CPU來控制傳輸的數據塊大小、傳輸的內存位置，而通道方式中這些信息是由通道控制的。另外，每一個DMA控制器對應1臺裝備與內存?zhèn)鬟f數據，而1個通道可以控制多臺裝備與內存的數據交換。

通道類型

字節(jié)多路通道：低速裝備（eg：打印機），1次1字節(jié)。
數據選擇通道：高速裝備（eg：磁盤/磁帶），以塊為單位傳送。但是1次只能對1臺裝備進行IO操作。
數組多路通道：高速，分時操作不同的裝備。

緩存（cache）和緩沖（buffer）

相同點： 都是介于高速裝備和低速裝備之間。

緩存

寄存的是低速裝備上的某些數據的復制的數據，也就是高速緩存上有的低速裝備上面必定有。這些數據常常要訪問，所以在高速緩存上是為了加快訪問速度。

緩沖

1般在內存區(qū)域，用來存儲數據。用于裝備之間或裝備與程序之間，彌補CPU和IO裝備速度的不匹配。解決基本數據單元大?。磾祿６龋┎黄ヅ涞膯栴}。提高CPU和I/O裝備之間的并行性。
雖然也能夠在硬件上采取硬件緩沖器實現，但是太貴了。

假脫機Spool

同享打印機是使用SPOOLing技術的1個實例，用于多用戶系統(tǒng)和局域網絡中。
當用戶進程要求打印輸出時，SPOOLing系統(tǒng)同意為它打印輸出，但其實不真正立即把打印機分配給該用戶進程，而只為它做兩件事：
1. 由輸出進程在輸出井中為之申請1個空閑磁盤塊區(qū)，并將要打印的數據送入其中。
2. 輸出進程再為用戶進程申請1張空白的用戶要求打印表，并將用戶的打印要求填入其中，再將該表掛到要求打印隊列上。

SPOOLing系統(tǒng)的主要特點有：提高了I/O的速度；將獨占裝備改造為同享裝備；實現了虛擬裝備功能。

文件系統(tǒng)

文件：具有符號名的相干數據的集合。
無結構文件：1系列的字符串組成，流式文件。
有結構文件：相干記錄的集合。比如表格等。

文件轉儲：全量轉儲、增量轉儲。

目錄：文件系統(tǒng)層次結構的非終結結點。
文件：終結結點。

文件系統(tǒng)：負責存取和管理外存上文件信息的功能模塊。

文件控制塊FCB

進程 = PCB + 程序段 + 數據段
文件 = FCB + 文件體
文件名、用戶名、物理地址、格式、編碼、屬性、密碼等。

文件系統(tǒng)層次結構

文件系統(tǒng)3大職能：
1. 建立文件；
2. 加工文件；
3. 輸出加工后的文件。

磁盤

調度
先來先服務FCFS：
最短尋道時間優(yōu)先shortest seed time first, SSTF：（貪心算法），不能保證平均最短，但是明顯好過 FCFS?？赡苁?些進程饑餓。
SCAN算法：不但斟酌最短尋道，還要斟酌必須與當前磁頭移動方向相同。磁頭類似電梯來來回回，又稱為“電梯調度算法”。
循環(huán)掃描CSCAN，circular scan：磁頭單向移動，到達最外道時再從最里道開始掃描。

1般選擇SSTF，磁盤負荷重的系統(tǒng)選擇SCAN/CSCAN，避免死等。

便宜冗余磁盤陣列RAID，redundant arrays of inexpensive disks

操作系統(tǒng)概述

存儲程序式計算機，馮 諾依曼計算機：運算器、控制器（自動化操作）、存儲器（存儲程序和數據）、IO部件。

操作系統(tǒng)(Operating System, OS)是指控制和管理全部計算機系統(tǒng)的硬件和軟件資源，并公道地組織調度計算機的工作和資源的分配，以提供給用戶和其他軟件方便的接口和環(huán)境的程序集合。
操作系統(tǒng)是計算機系統(tǒng)中最基本的系統(tǒng)軟件。

操作系統(tǒng)的特性：
并發(fā)：
同享：并發(fā)與同享相互依存。
不肯定：OS需要隨時處理系統(tǒng)中的不肯定事件。
虛擬：內存、CPU、外設等都采取了虛擬技術，邏輯上擴充了數量。

手工操作階段（此階段無操作系統(tǒng)）

批處理階段（操作系統(tǒng)開始出現）

為了解決人機矛盾及CPU和I/O裝備之間速度不匹配的矛盾，出現了批處理系統(tǒng)。它按發(fā)展歷程又分為單道批處理系統(tǒng)、多道批處理系統(tǒng)（多道程序設計技術出現以后）。

分時操作系統(tǒng)

時間片

實時操作系統(tǒng)

網絡操作系統(tǒng)和散布式計算機系統(tǒng)

個人計算機操作系統(tǒng)

系統(tǒng)調用

操作系統(tǒng)和利用程序之間的接口。