计算机操作系统-详细版-王道
鑒于有人需要離線版的PDF文檔，這里給出本文章的PDF版本，下載鏈接如下：https://pan.itnxd.cn/d/123Pan/operating-system.pdf
一、操作系統概述
1、操作系統定義
操作系統（Operating System，OS）：是指控制和管理整個計算機系統的硬件和軟件資源，并合理地組織調度計算機的工作和資源的分配，以提供給用戶和其他軟件方便的接口和環境，它是計算機系統中最基本的系統軟件。
2、操作系統功能和目標
作為系統資源的管理者
- 處理機調度（管理）：在多道程序環境下，cpu的分配和運行都以進程（或線程）為基本單位，因此對cpu的管理可理解為對進程的管理。進程管理的主要功能包括進程控制、進程同步、進程通信、死鎖處理、處理機調度等
- 存儲器管理：為多道程序的運行提供良好的環境，方便用戶使用及提高內存的利用率，主要包括內存分配與回收、地址映射、內存保護與共享和內存擴充等功能。
- 文件管理：計算機中所有的信息都是以文件的形式存在的，操作系統中負責文件的管理的部分稱為文件系統，文件管理包括文件存儲空間的管理、目錄管理及文件讀寫管理和保護等。
- 設備管理：主要任務是完成用戶的I/O請求，方便用戶使用各種設備，并提高設備的利用率，主要包括緩存管理、設備分配、設備處理和虛擬設備等功能。
作為用戶與計算機硬件系統之間的接口
命令接口： 允許用戶直接使用
- 聯機命令接口：用戶說一句，系統做一句 = 交互式命令接口
- 脫機命令接口：用戶說一堆，系統做一堆 = 批處理命令接口
程序接口： 允許用戶通過程序間接使用
由一組系統調用組成（程序接口=系統調用）
系統調用 = 系統調用命令 = 廣義指令
GUI： 現代操作系統中最流行的圖形用戶接口
作為最接近硬件的層次
需要提供的功能和目標：實現對硬件機器的拓展
沒有任何軟件支持的計算機稱為裸機。在裸機上安裝的操作系統，可以提供資源管理功能和方便用戶的服務功能，將裸機改造成功能更強、使用更方便的機器。
通常把覆蓋了軟件的機器稱為擴充機器，又稱之為虛擬機。
3、操作系統的特征
并發
并發：指兩個或多個事件在同一時間間隔內發生。這些事件宏觀上是同時發生的，但微觀上是交替發生的。
并行：指兩個或多個事件在同一時刻同時發生。
操作系統的并發性指計算機系統中同時存在著多個運行著的程序。
一個單核處理機（CPU）同一時刻只能執行一個程序，因此操作系統會負責協調多個程序交替執行（這些程序微觀上是交替執行的，但宏觀上看起來就像是在同時執行）
事實上，操作系統就是伴隨著“多道程序技術”而出現的。因此，操作系統和程序并發是一起誕生的。
共享
共享：即資源共享，是指系統中的資源可供內存中多個并發執行的進程共同使用。
所謂的“同時”往往是宏觀上的，而在微觀上，這些進程可能是交替地對該資源進行訪問的（即分時共享）
- 互斥共享方式
- 同時共享方式
并發和共享的關系（互為存在條件）
通過上述例子來看并發與共享的關系：
使用QQ發送文件A，同時使用微信發送文件B。
１、兩個進程正在并發執行（并發性）
如果失去并發性，則系統中只有一個程序正在運行，則共享性失去存在的意義
２、需要共享地訪問硬盤資源（共享性）
如果失去共享性，則QQ和微信不能同時訪問硬盤資源，就無法實現同時發送文件，也就無法并發。
虛擬
虛擬：指把一個物理上的實體變為若干個邏輯上的對應物。物理實體（前者）是實際存在的，而邏輯上對應物（后者）是用戶感受到的。
虛擬技術：用于實現虛擬的技術
虛擬處理器（CPU）：通過多道程序設計技術，采用讓多道程序并發執行的方法，分時來使用一個CPU，實際物理上只有一個CPU，但是用戶感覺到有多個CPU
虛擬存儲器：從邏輯上擴充存儲器容量，用戶感覺到的但實際不存在的存儲器
虛擬設備：將一臺物理設備虛擬為邏輯上的多臺設備，使多個用戶在同一時間段內訪問同一臺設備，即同時共享，用戶宏觀上感覺是同時的，但實際上是微
觀交替訪問同一臺設備的
虛擬技術
- 時分復用技術：如處理器的分時共享
- 空分復用技術：如虛擬存儲器
沒有并發，就探不上虛擬性
異步
異步： 指在多道程序環境下，允許多個程序并發執行，但由于資源有限，進程的執行不是一貫到底的，而是走走停停，以不可預知的速度向前推進，這就是進程的異步性。
顯然，如果失去了并發性，則系統只能串行地處理各個進程，每個進程地執行會一貫到底。只有系統擁有并發性，才有可能導致異步性。
沒有并發和共享，就談不上虛擬和異步，因此并發和共享是操作系統的兩個最基本的特征。
4、操作系統的發展和分類
手工操作階段
過程： 用戶把程序寫在紙帶上（其實就是在紙帶上打孔），然后輸入到計算機中，計算機隨后會處理這個程序，把輸出結果又放在紙帶中（其實還是打孔），展示給用戶看。
由于用戶在紙帶上編寫程序的速度很慢，紙帶輸入輸出的速度也很慢，而計算機的處理速度快，所以系統資源的利用率極低。
主要缺點：用戶獨占全機、人機速度矛盾導致資源利用率極低
批處理階段 — 單道批處理系統
引入脫機輸入/輸出技術（用磁帶完成），并使用監督程序（操作系統的雛形）負責控制作業的輸入、輸出。
由于磁帶錄入到處理器中的速度比紙帶快得多，所以單道批處理系統一定程序上緩和了人機速度矛盾，資源利用率有所提升。
主要優點： 緩解了一定程度的人機速度矛盾，資源利用率有所提升。
主要缺點： 內存中僅能有一道程序運行，只有該程序運行結束之后才能調入下一道程序。CPU有大量的時間是在空閑等待I/O完成。資源利用率依然很低。
批處理階段 — 多道批處理系統
每次往內存中輸入多道程序，操作系統正式誕生，并引入了中斷技術，由操作系統負責管理這些程序的運行。各個程序并發執行。
主要優點： 多道程序并發執行，共享計算機資源。資源利用率大幅提升，CPU和其他資源保持“忙碌”狀態，系統吞吐量增大。
主要缺點： 用戶響應時間長，沒有人機交互功能（用戶提交自己的作業之后就只能等待計算機處理完成，中間不能控制自己的作業執行）
分時操作系統
計算機以時間片為單位輪流為各個用戶/作業服務，各個用戶可通過終端與計算機進行交互。
主要優點： 用戶請求可以被即時響應，解決了人機交互問題。允許多個用戶同時使用一臺計算機，并且用戶對計算機的操作相互獨立，感受不到別人的存在。
主要缺點： 不能優先處理一些緊急任務。操作系統對各個用戶/作業都是完全公平的，循環地為每個用戶/作業服務一個時間片，不區分任務的緊急性。
實時操作系統
在實時操作系統的控制下，計算機系統接收到外部信號后及時進行處理，并且要在嚴格的時限內處理完事件。實時操作系統的主要特點是及時性和可靠性。
主要優點： 能夠優先響應一些緊急任務，某些緊急任務不需時間片排隊。
- 硬實時系統：必須在絕對嚴格的規定時間內完成處理（導彈系統）
- 軟實時系統：能接受偶爾違反時間規定（12306火車票）
其他操作系統
網絡操作系統
工作方式：把計算機網絡中的各臺計算機有機的結合起來，提供統一、經濟而有效的使用各臺計算機的方法、實現各臺計算機之間的數據互相傳送
特點：有主從關系、網絡中資源共亨、網絡中的計算機通過協議通信
分布式操作系統
工作方式︰系統中的各計算機相互協同并行完成同一任務
特征
-
系統中任意兩臺計算機通過通信方式交換信息
-
系統中的計算機都具有同等地位，無主從關系
-
每臺計算機上的資源為所有用戶共享
-
系統中的任意臺計算機都可以構成一個子系統，并且還能重構
-
任何工作都可以分布在幾臺計算機上、由他們并行工作、協同完成
特點：分布性和并行性
嵌入式操作系統
固話在硬件里面的系統、比如手機、路由器等
特點
- 完成某一項特定的功能、不具有通用性
- 廣泛用于文字處理、電子表格、游戲中等
個人計算機操作系統
常見的有Windows、Linux、Macintosh等
5、操作系統運行機制
兩種指令
指令：就是處理器（CPU）能識別、執行的最基本命令
- 特權指令： 如內存清零指令 --> 不允許用戶程序使用。
- 非特權指令： 如普通的運算指令
CPU如何判斷當前是否可以執行特權指令？
用程序狀態寄存器（PSW）中的某標志位來標識當前處理器處于什么狀態，如0為用戶態，1為核心態。
- 用戶態（目態）： 此時CPU只能執行非特權指令
- 核心態（管態）：特權指令、非特權指令都可以執行
兩種程序
- 內核程序： 操作系統的內核程序是系統的管理者，既可以執行特權指令，也可以執行非特權指令，運行在核心態。
- 應用程序： 為了保證系統能安全運行，普通應用程序只能執行非特權指令，運行在用戶態。
6、操作系統內核
內核：計算機上配置的底層軟件，是操作系統最基本、最核心的部分。
實現操作系統內核功能的那些程序就是內核程序。
時鐘管理： 實現計時功能
中斷處理： 負責實現中斷機制
原語
- 是一種特殊的程序
- 處于操作系統最底層，是最接近硬件的部分
- 這種程序的運行具有原子性 —— 其運行只能一氣呵成，不可中斷
- 運行時間較短，調用頻繁
對系統資源進行管理的功能 （有的操作系統不把這部分功能歸為 “ 內核功能 ”。也就是說不同的操作系統，對內核功能的劃分可能并不一樣）
- 進程管理
- 存儲器管理
- 設備管理
7、操作系統體系結構
- 大內核
- 將操作系統的主要功能模塊都作為系統內核，運行在核心態
- 優點：高性能
- 缺點：內核代碼龐大，結構混亂，難以維護
- 微內核
- 只把最基本的功能保留在內核
- 優點：內核功能少，結構清晰，方便維護
- 缺點：需要頻繁地在核心態和用戶態之間切換，性能低
8、中斷和異常
中斷機制誕生
早期的計算機：各程序只能串行執行，系統資源利用率低
為了解決上述問題，人們發明了操作系統（作為計算機的管理者），引入中斷機制，實現了多道程序并發執行。
本質：發生中斷就意味著需要操作系統介入，開展工作。
中斷概念和作用
1、當中斷發生時，CPU立即進入核心態
2、當中斷發生后，當前運行的進程暫停運行，并由操作系統內核對中斷進行處理
3、對于不同的中斷信號，會進行不同的處理
由于操作系統的管理工作（比如進程切換、分配I/O設備等）需要使用特權指令，因此CPU要從用戶態轉為核心態。中斷可以使CPU從用戶態切換為核心態，使操作系統獲得計算機的控制權。有了中斷，才能實現多道程序并發執行。
用戶態、核心態之間的切換是怎么實現的？
- “ 用戶態 --> 核心態 ” 是通過中斷實現，并且中斷是唯一途徑。
- “ 核心態 --> 用戶態 ” 的切換是通過執行一個特權指令，將程序狀態字（PSW）的標志位設置為用戶態。
用戶態和核心態就是程序狀態寄存器0或1標志的，因此核心態到用戶態可以通過特權指令進行設置！
中斷分類
- 內中斷
- 外中斷
分類二
外中斷
外中斷處理過程
更詳細過程
9、系統調用
什么是系統調用
系統調用： 是操作系統提供給應用程序（程序員/編程人員）使用的接口，可以理解為一種可供應用程序調用的特殊函數，應用程序可以發出系統調用請求來獲得操作系統的服務。
功能： 應用程序通過系統調用全球操作系統的服務。系統中的各種共享資源都由操作系統統一掌管，因此在用戶程序中，凡是與資源有關的操作（如存儲分配、I/O操作、文件管理等），都必須通過系統調用的方式向操作系統提出服務請求，由操作系統代為完成。這樣可以保證系統的穩定性和安全性，防止用戶進行非法操作。
系統調用相關處理涉及到對系統資源的管理、對進程的控制，這些功能需要執行一些特權指令才能完成，因此系統調用的線管處理需要在核心態下進行。
系統調用按功能分類
- 設備管理：完成設備的請求/釋放/啟動等功能
- 文件管理：完成文件的讀/寫/創建/刪除等功能
- 進程控制：完成進程的創建/撤銷/阻塞/喚醒等功能
- 進程通信：完成進程之間的消息傳遞/信號傳遞等功能
- 內存管理：完成內存的分配/回收等功能
系統調用與庫函數的區別
系統調用背后的過程
二、進程管理
0、大綱
- 進程與線程
- 處理機調度及調度算法
- 進程同步與互斥
- 死鎖
1、進程概述
進程定義
程序：就是一個指令序列
- 早期的計算機（只支持單道程序）
- 引入多道程序技術之后：為了方便操作系統管理，完成各程序并發執行，引入了進程、進程實體的概念。
PCB： 系統為每個運行的程序配置一個數據結構，稱為進程控制塊（PCB），用來描述進程的各種信息（如代碼存放位置）
PCB、程序段、數據段三部分構成了進程實體（進程映像）。一般情況下，我們把進程實體簡稱為進程，例如，所謂創建進程，實質上是創建進程實體中的PCB；而撤銷進程，實質上是撤銷進程實體中的PCB。PCB是進程存在的唯一標志！
定義： 強調動態性
進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位。
嚴格來說，進程實體和進程不一樣，進程實體是靜態的，進程則是動態的。
進程組成
進程（進程實體）由程序段、數據段、PCB三部分組成。
- 數據段：程序運行時使用、產生的運算數據。如全局變量
- 程序段：程序代碼即存放在此
- PCB：操作系統通過PCB來管理進程，因此PCB中應該包含操作系統對其進行管理所需的各種信息。
進程組織
進程的組成討論的是一個進程內部由哪些部分構成的問題，而進程的組織討論的是多個進程之間的組織方式問題。
進程的組織方式：
- 鏈接方式
- 按照進程狀態將PCB分為多個隊列
- 操作系統持有指向各個隊列的指針
- 索引方式
- 根據進程狀態的不同，建立幾張索引表
- 操作系統持有指向各個索引表的指針
進程特征
- 動態性 （進程最基本的特征）：進程是程序的一次執行過程，是動態地產生、變化和消亡地
- 并發性：內存中有多個進程實體，各進程可并發執行
- 獨立性 （進程是資源分配、接受調度的基本單位）：進程是能獨立運行、獨立獲得資源、獨立接受調度的基本單位
- 異步性 （會倒置并發程序執行結果的不確定性）：各進程按各自獨立的、不可預知的速度向前推進，操作系統要提供“進程同步機制”來解決異步問題
- 結構性：每個進程都會配置一個PCB。結構上看，進程由程序段、數據段、PCB組成
2、進程狀態與轉換
進程狀態
進程是程序的一次執行過程。在這個執行過從中，有時進程正在被CPU處理，有時又需要等待CPU服務，可見 ，進程的狀態是會有各種變化。為了方便對各個進程的管理，操作系統需要將進程合理地劃分為幾種狀態。
三種基本狀態
運行態（Running）：
- 占有CPU，并在CPU上運行
- 注意：單核處理機環境下，每一個時刻最多只有一個進程處于運行態。雙核環境下可以同時有兩個進程處于運行態
就緒態（Ready）：
- 已經具備運行條件，但由于沒有空閑CPU，而暫時不能運行。
- 進程已經擁有了除處理機之外所有需要的資源，一旦獲得處理機，即可立即進入運行態開始運行。
阻塞態（Waiting/Blocked，又稱：等待態）：
- 因等待某一事件而暫時不能運行
- 如：等待操作系統分配打印機、等待讀磁盤操作的結果。CPU是計算機中最昂貴的部件，為了提高CPU的利用率，需要先將其他進程需要的資源分配到位，才能得到CPU的服務
另外兩種狀態：
創建態（New，又稱：新建態）
- 進程正在被創建，操作系統為進程分配資源、初始化PCB
終止態（Terminated，又稱：結束態）
- 進程正在從系統中撤銷，操作系統會回收進程擁有的資源、撤銷PCB
進程轉換
- 處理機是否占用
- 其他是否擁有
根據以上即可知道處于哪個狀態！
3、進程控制
進程控制的主要功能是對系統中的所有進程實施有效的管理，它具有創建新進程、撤銷已有進程、實現進程狀態轉換等功能。
如何實現進程控制？
用原語實現進程控制。原語的特點是執行期間不允許中斷，只能一氣呵成。
這種不可被中斷的操作即原子操作。
原語采用“關中斷指令”和“開中斷指令”實現
顯然，關/開中斷指令的權限非常大，必然只允許在核心態下執行的特權指令。
原語任務
- 更新PCB中的信息（如修改進程狀態，將運行環境保存到PCB、從PCB恢復運行環境）
- 所有的進程控制原語一定都會修改進程狀態標志
- 剝奪當前運行進程的CPU使用權必然需要保存其運行環境
- 某進程開始運行前必然要恢復其運行環境
- 將PCB插入合適的隊列
- 分配/回收資源
進程的創建
進程的終止
進程的阻塞
進程的切換
4、進程通信
進程通信是指進程之間的信息交換。PV操作是低級通信方式，高級通信方式是指以較高的程效率傳輸大量數據的通信方式。
進程是分配系統資源的單位（包括內存地址空間)，因此各進程擁有的內存地址空間相互獨立。
為了保證安全，一個進程不能直接訪問另一個進程的地址空間。
但是進程之間的信息交換又是必須實現的。為了保證進程間的安全通信，操作系統提供了一些方法。
共享存儲
兩個進程對共享空間的訪問必須是互斥的（互斥訪問通過操作系統提供的工具實現）。
操作系統只負責提供共享空間和同步互斥工具（如P、v操作)
共享存儲
- 基于數據結構共享：比如共享空間里只能放一個長度為10的數組。這種共享方式速度慢、限制多，是一種低級通信方式
- 基于存儲區共享：基于在內存中畫出一塊共享存儲區，數據的形式、存放位置都由進程控制，而不是操作系統。相比之下，這種共享方式速度更快，是一種高級通信方式。
管道通信
“管道”是指用于連接讀寫進程的一個共享文件，又名pipe文件。其實就是在內存中開辟一個大小固定的緩沖區
- 管道只能采用半雙工通信，某一時間段內只能實現單向的傳輸。如果要實現雙向同時通信，則需要設置兩個管道。
- 各進程要互斥地訪問管道。
- 數據以字符流的形式寫入管道，當管道寫滿時，寫進程的write() 系統調用將被阻塞，等待讀進程將數據取走。當讀進程將數據全部取走后，管道變空，此時讀進程的read() 系統調用將被阻塞。（緩沖區的特性）
- 如果沒寫滿，就不允許讀。如果沒讀空，就不允許寫。（緩沖區的特性）
- 數據一旦被讀出，就從管道中被拋棄，這就意味著讀進程最多只能有一個，否則可能會有讀錯數據的情況。
消息傳遞
進程間的數據交換以格式化的消息（Message）為單位。進程通過操作系統提供的“發送消息 / 接收消息”兩個原語進行數據交換。
消息
- 消息頭：包括發送進程ID、接受進程ID、消息類型、消息長度等格式化的信息（計算機網絡中發送的“報文”其實就是一種格式化的消息)
- 消息體
消息傳遞方式
- 直接消息傳遞：消息直接掛到接收進程的消息緩沖隊列上
- 間接消息傳遞：消息要先發送到中間實體（信箱）中，因此也稱“信箱通信方式”。Eg：計網中的電子郵件系統
5、線程概念&多線程模型
線程概述
有的進程可能需要“同時”做很多事，而傳統的進程只能串行地執行一系列程序。為此，引入了“線程”，來增加并發度。
- 傳統的進程是程執行流的最小單位
- 引入線程后，線程成為了程序執行流的最小單位
可以把線程理解為“輕量級進程”。
線程是一個基本的CPU執行單元，也是程序執行流的最小單位。
引入線程之后，不僅是進程之間可以并發，進程內的各線程之間也可以并發，從而進一步提升了系統的并發度，使得一個進程內也可以并發處理各種任務（如QQ視頻、文字聊天、傳文件)
引入線程后，進程只作為除CPU之外的系統資源的分配單元（如打印機、內存地址空間等都是分配給進程的）。
引入線程帶來的變化
資源分配、調度
- 傳統進程機制中，進程是資源分配、調度的基本單位
- 引入線程后，進程是資源分配的基本單位，線程是調度的基本單位
并發性
- 傳統進程機制中，只能進程間并發
- 引入線程后，各線程間也能并發，提升了并發度
系統開銷
- 傳統的進程間并發，需要切換進程的運行環境，系統開銷很大
- 線程間并發，如果是同一進程內的線程切換，則不需要切換進程環境，系統開銷小
- 引入線程后，并發所帶來的系統開銷減小
線程屬性
- 線程是處理機調度的單位
- 多CPU計算機中，各個線程可占用不同的CPU
- 每個線程都有一個線程ID、線程控制塊(TCB)
- 線程也有就緒、阻塞、運行三種基本狀態
- 線程幾乎不擁有系統資源
- 同一進程的不同線程間共享進程的資源
- 由于共享內存地址空間，同- -進程中的線程間通信甚至無需系統干預
- 同一進程中的線程切換，不會引起進程切換
- 不同進程中的線程切換，會引起進程切換
- 切換同進程內的線程，系統開銷很小
- 切換進程，系統開銷較大
線程實現方式
用戶級線程
- 用戶級線程由應用程序通過線程庫實現。所有的線程管理工作都由應用程序負責（包括線程切換)
- 用戶級線程中，線程切換可以在用戶態下即可完成，無需操作系統干預。
- 在用戶看來，是有多個線程。但是在操作系統內核看來，并意識不到線程的存在。（用戶級線程對用戶不透明，對操作系統透明)
- 可以這樣理解，“用戶級線程”就是“從用戶視角看能看到的線程”
內核級線程
- 內核級線程的管理工作由操作系統內核完成。線程調度、切換等工作都由內核負責，因此內核級線程的切換必然需要在核心態下才能完成。
- 可以這樣理解，“內核級線程”就是“從操作系統內核視角看能看到的線程”
在同時支持用戶級線程和內核級線程的系統中，可采用二者組合的方式:將n個用戶級線程映射到m個內核級線程上 ( n >= m)
- 操作系統只“看得見”內核級線程，因此只有內核級線程才是處理機分配的單位。
- 例如：該進程由兩個內核級線程，三個用戶級線程，在用戶看來，這個進程中有三個線程。但即使該進程在一個4核處理機的計算機上運行，也最多只能被分配到兩個核，最多只能有兩個用戶線程并行執行（只能分配到有限的兩個內核級線程）。
多線程模型
在同時支持用戶級線程和內核級線程的系統中，由幾個用戶級線程映射到幾個內核級線程的問題引出了“多線程模型”問題。
多對一模型：多個用戶及線程映射到一個內核級線程。每個用戶進程只對應一個內核級線程。
- 優點:用戶級線程的切換在用戶空間用戶態即可完成，不需要切換到核心態，線程管理的系統開銷小，效率高
- 缺點:當一個用戶級線程被阻塞后，整個進程都會被阻塞，并發度不高。多個線程不可在多核處理機上并行運行（只有一個內核級線程）
一對一模型：一個用戶及線程映射到一個內核級線程。每個用戶進程有與用戶級線程同數量的內核級線程。
- 優點:當一個線程被阻塞后，別的線程還可以繼續執行，并發能力強。多線程可在多核處理機上并行執行。
- 缺點:一個用戶進程會占用多個內核級線程，線程切換由操作系統內核完成，需要切換到核心態，因此線程管理的成本高，開銷大。
多對多模型：n用戶及線程映射到m個內核級線程(n >= m） 。每個用戶進程對應m個內核級線程。
- 克服了多對一模型并發度不高的缺點，又克服了一對一模型中一個用戶進程占用太多內核級線程，開銷太大的缺點。
6、處理機調度
基本概念
當有一堆任務要處理，但由于資源有限，這些事情沒法同時處理。這就需要確定某種規則來決定處理這些任務的順序，這就是“調度”研究的問題。
在多道程序系統中，進程的數量往往是多于處理機的個數的，這樣不可能同時并行地處理各個進程。處理機調度，就是從就緒隊列中按照一定的算法選擇一個進程并將處理機分配給它運行，以實現進程的并發執行。
高級調度
由于內存空間有限，有時無法將用戶提交的作業全部放入內存，因此就需要確定某種規則來決定將作業調入內存的順序。
高級調度（作業調度）：按一定的原則從外存上處于后備隊列的作業中挑選一個（或多個）作業，給他們分配內存等必要資源，并建立相應的進程（建立PCB），以使它（們）獲得競爭處理機的權利。
高級調度是輔存（外存）與內存之間的調度。每個作業只調入一次，調出一次。作業調入時會建立相應的PCB，作業調出時才撤銷PCB。高級調度主要是指調入的問題，因為只有調入的時機需要操作系統來確定，但調出的時機必然是作業運行結束才調出。
中級調度
引入了虛擬存儲技術之后，可將暫時不能運行的進程調至外存等待。等它重新具備了運行條件且內存又稍有空閑時，再重新調入內存。
這么做的目的是為了提高內存利用率和系統吞吐量。
暫時調到外存等待的進程狀態為掛起態。值得注意的是，PCB并不會一起調到外存，而是會常駐內存。PCB中會記錄進程數據在外存中的存放位置，進程狀態等信息，操作系統通過內存中的PCB來保持對各個進程的監控、管理。被掛起的進程PCB會被放到的掛起隊列中。
中級調度（內存調度）：就是要決定將哪個處于掛起狀態的進程重新調入內存。
一個進程可能會被多次調出、調入內存，因此中級調度發生的頻率要比高級調度更高。
低級調度
低級調度（進程調度）：其主要任務是按照某種方法和策略從就緒隊列中選取一個進程，將處理機分配給它。
進程調度是操作系統中最基本的一種調度，在一般的操作系統中都必須配置進程調度。
進程調度的頻率很高，一般幾十毫秒一次。
三層調度對比
七狀態模型
暫時調到外存等待的進程狀態為掛起態
掛起態又可以進一步細分為就緒掛起、阻塞掛起兩種狀態
五狀態模型 升級為 七狀態模型
注意“掛起”和“阻塞”的區別
兩種就緒掛起 狀態都是暫時不能獲得CPU的服務，但掛起態是將進程映像調到外存去了，而阻塞態下進程映像還在內存中。
有的操作系統會把就緒掛起、阻塞掛起分為兩個掛起隊列，甚至會根據阻塞原因不同再把阻塞掛起進程進一步細分為阻塞掛起 多個隊列。
進程調度時機
需要進行進程調度與切換的情況
- 當前運行的進程主動放棄處理機
- 進程正常終止
- 運行過程中發生異常而終止進程主動請求阻塞（如等待l/O)
- 當前運行的進程被動放棄處理機
- 分給進程的時間片用完
- 有更緊急的事需要處理（如I/O中斷)有更高優先級的進程進入就緒隊列
不能進行進程調度與切換的情況
- 在處理中斷的過程中。中斷處理過程復雜，與硬件密切相關，很難做到在中斷處理過程中進行進程切換。
- 進程在操作系統內核程序臨界區中。
- 在原子操作過程中（原語)。原子操作不可中斷，要一氣呵成（如之前講過的修改PCB中進程狀態標志，并把PCB放到相應隊列)
臨界資源：一個時間段內只允許一個進程使用的資源。各進程需要互斥地訪問臨界資源。
臨界區：訪問臨界資源的那段代碼。
進程調度的切換和過程
“狹義的進程調度”與“進程切換”的區別：
狹義的進程調度指的是從就緒隊列中選中一個要運行的進程。（這個進程可以是剛剛被暫停執行的進程，也可能是另一個進程，后一種情況就需要進程切換）
進程切換是指一個進程讓出處理機，由另一個進程占用處理機的過程。
過程
廣義的進程調度包含了選擇一個進程和進程切換兩個步驟。
進程切換的過程主要完成了：
- 對原來運行進程各種數據的保存
- 對新的進程各種數據的恢復（如：程序計數器、程序狀態字、各種數據寄存器等處理機現場信息，這些信息一般保存在進程控制塊）
注意：進程切換是有代價的，因此如果過于頻繁的進行進程調度、切換，必然會使整個系統的效率降低，使系統大部分時間都花在了進程切換上，而真正用于執行進程的時間減少。
進程調度的方式
非剝奪調度方式，又稱非搶占方式。即，只允許進程主動放棄處理機。在運行過程中即便有更緊迫的任務到達，當前進程依然會繼續使用處理機，直到該進程終止或主動要求進入阻塞態。
- 實現簡單，系統開銷小但是無法及時處理緊急任務，適合于早期的批處理系統
剝奪調度方式，又稱搶占方式。當一個進程正在處理機上執行時，如果有一個更重要或更緊迫的進程需要使用處理機，則立即暫停正在執行的進程，將處理機分配給更重要緊迫的那個進程。
- 可以優先處理更緊急的進程，也可實現讓各進程按時間片輪流執行的功能（通過時鐘中斷）。適合于分時操作系統、實時操作系統
7、進程調度算法
調度算法評價指標
CPU利用率：指CPU “忙碌”的時間占總時間的比例。
利用率 = 忙碌的時間 / 總時間
系統吞吐量：單位時間內完成作業的數量
系統吞吐量 = 總共完成了多少道作業 / 總共花了多少時間
周轉時間，是指從作業被提交給系統開始，到作業完成為止的這段時間間隔。
它包括四個部分：
- 作業在外存后備隊列上等待作業調度（高級調度）的時間、
- 進程在就緒隊列上等待進程調度（低級調度）的時間、
- 進程在CPU上執行的時間、
- 進程等待I/O操作完成的時間。
后三項在一個作業的整個處理過程中，可能發生多次
- 周轉時間=作業完成時間–作業提交時間
- 平均周轉時間=各作業周轉時間之和/作業數
- 帶權周轉時間=作業周轉時間/作業實際運行的時間=(作業完成時間–作業提交時間)/作業實際運行的時間
- 平均帶權周轉時間=各作業帶權周轉時間之和/作業數
帶權周轉時間與周轉時間都是越小越好
等待時間，指進程 / 作業處于等待處理機狀態時間之和，等待時間越長，用戶滿意度越低。
無I/O處理：等待時間 = 周轉時間 - 運行時間
有I/O處理：等待時間 = 周轉時間 - 運行時間 - I/O處理時間
- 對于進程來說，等待時間就是指進程建立后等待被服務的時間之和，在等待I/O完成的期間其實進程也是在被服務的，所以不計入等待時間。
- 對于作業來說，不僅要考慮建立進程后的等待時間，還要加上作業在外存后備隊列中等待的時間。
一個作業總共需要被CPU服務多久，被I/O設備服務多久一般是確定不變的，因此調度算法其實只會影響作業 / 進程的等待時間。當然，與前面指標類似，也有“平均等待時間”來評價整體性能。
響應時間，指從用戶提交請求到首次產生響應所用的時間。
先來先服務FCFS
公平
按照作業 / 進程到達的先后順序進行服務
用于作業 / 進程調度：用于作業調度時，考慮的是哪個作業先到達后備隊列；用于進程調度時，考慮的是哪個進程先到達就緒隊列
非搶占式的算法
優點：公平、算法實現簡單
缺點：排在長作業（進程）后面的短作業需要等待很長時間，帶權周轉時間很大，對短作業來說用戶體驗不好。即，FCFS算法對長作業有利，對短作業不利
不會產生饑餓現象
短作業優先SJF
算法思想：追求最少的平均等待時間，最少的平均周轉時間、最少的平均平均帶權周轉時間（選擇當前已到達的時間最短的執行）
算法規則： 最短的作業 / 進程優先得到服務（所謂“最短”，是指要求服務時間最短）
**即可用于作業調度，也可用于進程調度。**用于進程調度時稱為“短進程優先（SPF, Shortest Process First）算法”
SJF和SPF是非搶占式的算法。但是也有搶占式的版本——最短剩余時間優先算法（SRTN, Shortest Remaining Time Next）（新到達的進程的剩余時間比當前運行的進程剩余時間更短，新進程搶占處理機）
優點:“最短的”平均等待時間、平均周轉時間（搶占式的SRTN更短）
缺點:不公平。對短作業有利，對長作業不利?？赡墚a生饑餓現象。另外，作業/進程的運行時間是由用戶提供的，并不一定真實，不一定能做到真正的短作業優先
會產生饑餓。如果源源不斷地有短作業/進程到來，可能使長作業/進程長時間得不到服務，產生“饑餓”現象。如果一直得不到服務．川稱為“餓死”
高響應比優先HRRN
算法思想：要綜合考慮作業/進程的等待時間和要求服務的時間
算法規則：在每次調度時先計算各個作業/進程的響應比，選擇響應比最高的作業/進程為其服務
響應比= 等待時間 + 要求服務時間 / 要求服務時間
即可用于作業調度，也可用于進程調度
非搶占式的算法。因此只有當前運行的作業/進程主動放棄處理機時，才需要調度，才需要計算響應比
優缺點：
- 綜合考慮了等待時間和運行時間（要求服務時間)
- 等待時間相同時，要求服務時間短的優先（SJF的優點)
- 要求服務時間相同時，等待時間長的優先(FCFS的優點)
- 對于長作業來說，隨著等待時間越來越久，其響應比也會越來越大，從而避免了長作業饑餓的問題
不會產生饑餓
三種算法總結1
- 這幾種算法主要關心對用戶的公平性、平均周轉時間、平均等待時間等評價系統整體性能的指標，但是不關心“響應時間”，也并不區分任務的緊急程度
- 因此對于用戶來說，交互性很糟糕。因此這三種算法一般適合用于早期的批處理系統，當然，FCFS算法也常結合其他的算法使用，在現在也扮演著很重要的角色。
時間片輪轉調度算法
算法思想：公平地、輪流地為各個進程服務，讓每個進程在一定時間間隔內都可以得到響應
算法規則：按照各進程到達就緒隊列的順序，輪流讓各個進程執行一個時間片（如100ms）。若進程未在一個時間片內執行完，則剝奪處理機，將進程重新放到就緒隊列隊尾重新排隊。
用于進程調度(只有作業放入內存建立了相應的進程后，才能被分配處理機時間片）
若進程未能在時間片內運行完，將被強行剝奪處理機使用權，因此時間片輪轉調度算法屬于搶占式的算法。由時鐘裝置發出時鐘中斷來通知CPU時間片已到
優點：公平;響應快，適用于分時操作系統;
缺點：由于高頻率的進程切換，因此有一定開銷，不區分任務的緊急程度。時間片太大會退化為FCFS算法，太小進程切換開銷太大！
不會產生饑餓
優先級調度算法
算法思想：隨著計算機的發展，特別是實時操作系統的出現，越來越多的應用場景需要根據任務的緊急程度來決定處理順序
算法規則：每個作業/進程有各自的優先級，調度時選擇優先級最高的作業/進程
既可用于作業調度，也可用于進程調度。甚至，還會用于在之后會學習的I/O調度中
搶占式、非搶占式都有。做題時的區別在于:非搶占式只需在進程主動放棄處理機時進行調度即可，而搶占式還需在就緒隊列變化時，檢查是否會發生搶占。（即新到達的是否比正在運行的優先級要高，高則搶占處理機）
優點：用優先級區分緊急程度、重要程度，適用于實時操作系統。可靈活地調整對各種作業/進程的偏好程度。
缺點：若源源不斷地有高優先級進程到來，則可能導致饑餓
會產生饑餓
- 就緒隊列未必只有一個，可以按照不同優先級來組織。另外，也可以把優先級高的進程排在更靠近隊頭的位置
- 根據優先級是否可以動態改變，可將優先級分為靜態優先級和動態優先級兩種。
- 靜態優先級:創建進程時確定，之后一直不變。
- 動態優先級:創建進程時有一個初始值，之后會根據情況動態地調整優先級。
合理設置優先級
- 合理高于用戶進程
- 前臺進程優先級高于后臺進程
- 操作系統更偏好l/O型進程（或稱IO繁忙型進程）
注：與I/O型進程相對的是計算型進程（或稱CPU繁忙型進程）
什么時候跳轉優先級？
- 可以從追求公平、提升資源利用率等角度考慮
- 如果某進程在就緒隊列中等待了很長時間，則可以適當提升其優先級，如果某進程占用處理機運行了很長時間，則可適當降低其優先級如果發現一個進程
- 頻繁地進行l/O操作，則可適當提升其優先級
多級反饋隊列調度算法
**算法思想：**對其他調度算法的折中權衡
算法規則：
- 設置多級就緒隊列，各級隊列優先級從高到低，時間片從小到大
- 新進程到達時先進入第1級隊列，按FCFS原則排隊等待被分配時間片，若用完時間片進程還未結束，則進程進入下一級隊列隊尾。如果此時已經是在最下級的隊列，則重新放回該隊列隊尾
- 只有第k 級隊列為空時，才會為k+1級隊頭的進程分配時間片用于進程調度
搶占式的算法。在k級隊列的進程運行過程中，若更上級的隊列(1~k-1級）中進入了一個新進程，則由于新進程處于優先級更高的隊列中，因此新進程會搶占處理機，原來運行的進程放回k級隊列隊尾。
優缺點：
對各類型進程相對公平(FCFS的優點），每個新到達的進程都可以很快就得到響應（RR的優點），短進程只用較少的時間就可完成(SPF的優點），不必實現估計進程的運行時間（避免用戶作假），可靈活地調整對各類進程的偏好程度，比如CPU密集型進程、I/O密集型進程（拓展:可以將因I/O而阻塞的進程重新放回原隊列，這樣/o型進程就可以保持較高優先級)
會產生饑餓 （連續新進程到達，則會導致當前進程餓死）
例子
三種算法總結2
比起早期的批處理操作系統來說，由于計算機造價大幅降低，因此之后出現的交互式操作系統（包括分時操作系統、實時操作系統等）更注重系統的響應時間、公平性、平衡性等指標。而這幾種算法恰好也能較好地滿足交互式系統的需求。因此這三種算法適合用于交互式系統。(比如UNIX使用的就是多級反饋隊列調度算法)
8、進程同步&進程互斥
概述
進程同步：同步亦稱直接制約關系，它是指為完成某種任務而建立的兩個或多個進程，這些進程因為需要在某些位置上協調它們的工作次序而產生的制約關系。進程間的直接制約關系就是源于它們之間的相互合作。（解決異步的不可預知性）
進程互斥：對臨界資源的訪問，必須互斥地進行。互斥，亦稱間接制約關系。進程互斥指當一個進程訪問某臨界資源時，另一個想要訪問該臨界資源的進程必須等待。當前訪問臨界資源的進程訪問結束，釋放該資源之后，另一個進程才能去訪問臨界資源。
臨界資源：我們把一個時間段內只允許一個進程使用的資源稱為臨界資源。許多物理設備（比如攝像頭、打印機）都屬于臨界資源。此外還有許多變量、數據、內存緩沖區等都屬于臨界資源。
臨界資源互斥訪問，可劃分為四個部分：
- 進入區：負責檢查是否可進入臨界區,若可進入，則應設置正在訪問臨界資源的標志（可理解為“上鎖”)，以阻止其他進程同時進入臨界區
- 臨界區：訪問臨界資源的那段代碼
- 退出區：負責解除正在訪間臨界資源的標志（可理解為“解鎖”)
- 剩余區：做其他處理
臨界資源的互斥訪問原則
- 空閑讓進。臨界區空閑時，可以允許一個請求進入臨界區的進程立即進入臨界區;
- 忙則等待。當已有進程進入臨界區時，其他試圖進入臨界區的進程必須等待;
- 有限等待。對請求訪問的進程，應保證能在有限時間內進入臨界區（保證不會饑餓）;
- 讓權等待。當進程不能進入臨界區時，應立即釋放處理機，防止進程忙等待。
進程互斥軟件實現
單標志法
算法思想：兩個進程在訪問完臨界區后會把使用臨界區的權限轉交給另一個進程。也就是說每個進程進入臨界區的權限只能被另一個進程賦予
該算法可以實現“同一時刻最多只允許一個進程訪問臨界區”
單標志法存在的主要問題是：違背“空閑讓進”原則。
由于執行順序一定是P1P2輪流執行，因此P1只要不觸發執行，P2一定無法執行！
雙標志先檢查法
算法思想：設置一個布爾型數組flag[]，數組中各個元素用來標記各進程想進入臨界區的意愿，比如“flag[0]=ture”意味著0號進程P0現在想要進入臨界區。每個進程在進入臨界區之前先檢查當前有沒有別的進程想進入臨界區，如果沒有，則把自身對應的標志flag[i]設為true，之后開始訪問臨界區。
雙標志先檢查法存在的主要問題是：違背“忙則等待”原則。
第一步和第五步若發生進程切換，則對鄰接資源的訪問就不互斥了！
原因在于先檢查的兩句代碼不是原子操作！
雙標志后檢查法
算法思想：雙標志先檢查法的改版。前一個算法的問題是先“檢查”后“上鎖”，但是這兩個操作又無法一氣呵成，因此導致了兩個進程同時進入臨界區的問題。因此，人們又想到先“上鎖”后“檢查”的方法，來避免上述問題。
解決了“忙則等待”的問題，但是又違背了“空閑讓進”和“有限等待”
同樣第一步和第五步進程切換，就會發生二者都進不去臨界區！
Peterson算法
算法思想：雙標志后檢查法中，兩個進程都爭著想進入臨界區，但是誰也不讓誰，最后誰都無法進入臨界區。Gary L. Peterson想到了一種方法，如果雙方都爭著想進入臨界區，那可以讓進程嘗試“孔融讓梨”，主動讓對方先使用臨界區。
Peterson算法用軟件方法解決了進程互斥問題，遵循了空閑讓進、忙則等待、有限等待三個原則，但是依然未遵循讓權等待的原則。
進程互斥硬件實現
中斷屏蔽方法
利用“開 / 關中斷指令”實現（與原語的實現思想相同，即在某進程開始訪問臨界區到結束訪問為止都不允許被中斷，也就不能發生進程切換，因此也不可能發生兩個同時訪問臨界區的情況）
- 關中斷
- 臨界區
- 開中斷
優點：簡單、高效
缺點：不適用于多處理機；只適用于操作系統內核進程，不適用于用戶進程（因為開 / 關中斷指令 只能運行在內核態，這組指令如果能讓用戶隨意使用會很危險）
TestAndSet指令
簡稱TS 指令，也有地方稱為TestAndSetLock 指令，或TSL 指令 . TSL 指令是用硬件實現的，執行的過程不允許被中斷，只能一氣呵成。
相比軟件實現方法，TSL指令把“上鎖”和“檢查”操作用硬件的方式變成了一氣呵成的原子操作。
優點：實現簡單，無需像軟件實現方法那樣嚴格檢查是否會有邏輯漏洞;適用于多處理機環境
缺點：不滿足“讓權等待”原則，暫時無法進入臨界區的進程會占用CPU并循環執行TSL指令，從而導致“忙等”。
Swap指令
有的地方也叫Exchange 指令，或簡稱XCHG 指令。
Swap 指令是用硬件實現的，執行的過程不允許被中斷，只能一氣呵成。
邏輯上來看Swap 和TSL 并無太大區別，都是先記錄下此時臨界區是否已經被上鎖（記錄在old量上），再將上鎖標記lock 設置為true，最后檢查 old，如果 old 為false 則說明之前沒有別的進程對臨界區上鎖，則可跳出循環，進入臨界區。
優點：實現簡單，無需像軟件實現方法那樣嚴格檢查是否會有邏輯漏洞；適用于多處理機環境
缺點：不滿足“讓權等待”原則，暫時無法進入臨界區的進程會占用CPU并循環執行TSL指令，從而導致“忙等”。
9、信號量機制
信號量機制
用戶進程可以通過使用操作系統提供的一對原語來對信號量進行操作，從而很方便的實現了進程互斥、進程同步。
信號量其實就是一個變量（可以是一個整數，也可以是更復雜的記錄型變量） ，可以用一個信號量來表示系統中某種資源的數量，比如：系統中只有一臺打印機，就可以設置一個初值為1 的信號量。
原語是一種特殊的程序段，其執行只能一氣呵成，不可被中斷。原語是由關中斷/開中斷指令實現的。
一對原語：wait(S) 原語和signal(S) 原語，可以把原語理解為我們自己寫的函數，函數名分別為wait和signal，括號里的信號量S 其實就是函數調用時傳入的一個參數。
wait、signal 原語常簡稱為P、V操作（來自荷蘭語proberen 和verhogen）。因此，做題的時候常把wait(S) 、signal(S) 兩個操作分別寫為P(S) 、V(S)
整型信號量
用一個整數型的變量作為信號量，用來表示系統中某種資源的數量。
與普通整數變量的區別：對信號量的操作只有三種，即初始化、P操作、V操作
記錄型信號量
整型信號量的缺陷是存在“忙等”問題，因此人們又提出了“記錄型信號量”，即用記錄型數據結構表示的信號量。
wait(S) 、signal(S) 也可以記為P(S) 、V(S) ，這對原語可用于實現系統資源的“申請”和“釋放”。
S.value 的初值表示系統中某種資源的數目。
對信號量S 的一次P 操作意味著進程請求一個單位的該類資源，因此需要執行S.value-- ，表示資源數減1，當S.value < 0 時表示該類資源已分配完畢，因此進程應調用block 原語進行自我阻塞（當前運行的進程從運行態 ----> 阻塞態），主動放棄處理機，并插入該類資源的等待隊列S.L 中?？梢?#xff0c;該機制遵循了“讓權等待”原則，不會出現“忙等”現象。
對信號量S 的一次V 操作意味著進程釋放一個單位的該類資源，因此需要執行S.value++，表示資源數加1，若加1后仍是 S.value <= 0，表示依然有進程在等待該類資源，因此應調用wakeup 原語喚醒等待隊列中的第一個進程（被喚醒進程從阻塞態 ----> 就緒態）。
信號量機制實現進程互斥
理解：信號量mutex 表示“進入臨界區的名額”
注意：
- 對不同的臨界資源需要設置不同的互斥信號量。
- P、V操作必須成對出現。缺少P(mutex) 就不能保證臨界資源的互斥訪問。缺少V(mutex) 會導致資源永不被釋放，等待進程永不被喚醒。
信號量機制實現進程同步
進程同步：要讓各并發進程按要求有序地推進。
比如，P1、P2 并發執行，由于存在異步性，因此二者交替推進的次序是不確定的。若P2 的“代碼4”要基于 P1 的“代碼1”和“代碼2”的運行結果才能執行，那么我們就必須保證“代碼4”一定是在“代碼2”之后才會執行。
這就是進程同步問題，讓本來異步并發的進程互相配合，有序推進。
用信號量實現進程同步：
技巧口訣：前V后P
信號量機制實現前驅關系
進程P1 中有句代碼S1，P2 中有句代碼S2 ，P3中有句代碼S3 …… P6 中有句代碼S6。這些代碼要求按如下前驅圖所示的順序來執行
其實每一對前驅關系都是一個進程同步問題（需要保證一前一后的操作）
因此：
-
要為每一對前驅關系各設置一個同步信號量
-
在“前操作”之后對相應的同步信號量執行V 操作
-
在“后操作”之前對相應的同步信號量執行P 操作
10、經典進程同步問題
生產者消費者問題
問題描述
系統中有一組生產者進程和一組消費者進程，生產者進程每次生產一個產品放入緩沖區，消費者進程每次從緩沖區中取出一個產品并使用。（注：這里的“產品”理解為某種數據）
生產者、消費者共享一個初始為空、大小為n的緩沖區。
- 只有緩沖區沒滿時，生產者才能把產品放入緩沖區，否則必須等待。（同步關系）
- 只有緩沖區不空時，消費者才能從中取出產品，否則必須等待。（同步關系）
- 緩沖區是臨界資源，各進程必須互斥地訪問。(互斥關系)
問題分析
PV操作題目分析步驟：
如何實現
能否改變相鄰的PV操作順序？
① -> ② -> ③
若此時緩沖區內已經放滿產品，則empty=0，full=n。
則生產者進程執行①使mutex變為0，再執行②，由于已沒有空閑緩沖區，因此生產者被阻塞。由于生產者阻塞，因此切換回消費者進程。消費者進程執行③，由于mutex為0，即生產者還沒釋放對臨界資源的“鎖”，因此消費者也被阻塞。這就造成了生產者等待消費者釋放空閑緩沖區，而消費者又等待生產者釋放臨界區的情況，生產者和消費者循環等待被對方喚醒，出現“死鎖”。
③ -> ④ -> ①
同樣的，若緩沖區中沒有產品，即full=0，empty=n。按③④① 的順序執行就會發生死鎖。
因此，實現互斥的P操作一定要在實現同步的P操作之后。
V操作不會導致進程阻塞，因此兩個V操作順序可以交換。
多生產者多消費者問題
問題描述
桌子上有一只盤子，每次只能向其中放入一個水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，兒子專等著吃盤子中的橘子，女兒專等著吃盤子中的蘋果。只有盤子空時，爸爸或媽媽才可向盤子中放一個水果。僅當盤子中有自己需要的水果時，兒子或女兒可以從盤子中取出水果。
問題分析
- 互斥關系：（mutex = 1）：對緩沖區（盤子）的訪問要互斥地進行
- 同步關系（一前一后）：
- 父親將蘋果放入盤子后，女兒才能取蘋果
- 母親將橘子放入盤子后，兒子才能取橘子
- 只有盤子為空時，父親或母親才能放入水果
如何實現
不設置互斥信號量？
原因在于：本題中的緩沖區大小為1，在任何時刻，apple、orange、plate三個同步信號量中最多只有一個是1。因此在任何時刻,最多只有一個進程的P操作不會被阻塞，并順利地進入臨界區…
如果緩沖區大小為2，則兩個生產者會都進入臨界區（可能造成后者將前者的數據覆蓋掉），這時候就必須得設置互斥信號量了！
注意：
- 互斥信號量加不加，加上肯定沒錯
- 實現互斥的P操作一定要在實現同步的P操作之后，否則可能導致死鎖
- 分析問題應該以事件角度考慮，而不是以進程角度考慮
吸煙者問題
問題描述
假設一個系統有三個抽煙者進程和一個供應者進程。每個抽煙者不停地卷煙并抽掉它，但是要卷起并抽掉一支煙，抽煙者需要有三種材料：煙草、紙和膠水。
三個抽煙者中，第一個擁有煙草、第二個擁有紙、第三個擁有膠水。
供應者進程無限地提供三種材料，供應者每次將兩種材料放桌子上，擁有剩下那種材料的抽煙者卷一根煙并抽掉它，并給供應者進程一個信號告訴完成了，供應者就會放另外兩種材料再桌上，這個過程一直重復（讓三個抽煙者輪流地抽煙）
問題分析
同步關系
-
桌上有組合一 → 第一個抽煙者取走東西
-
桌上有組合二 → 第二個抽煙者取走東西
-
桌上有組合三 → 第三個抽煙者取走東西
-
發出完成信號 → 供應者將下一個組合放到桌上
互斥關系
- 桌子抽象為容量為1的緩沖區，需要互斥訪問
如何實現
讀者寫者問題
問題描述
有讀者和寫者兩組并發進程，共享一個文件，當兩個或兩個以上的讀進程同時訪問共享數據時不會產生副作用，但若某個寫進程和其他進程（讀進程或寫進程）同時訪問共享數據時則可能導致數據不一致的錯誤。
因此要求：
- 允許多個讀者可以同時對文件執行讀操作
- 只允許一個寫者往文件中寫信息
- 任一寫者在完成寫操作之前不允許其他讀者或寫者工作
- 寫者執行寫操作前，應讓已有的讀者和寫者全部退出。
問題分析
兩類進程：寫進程、讀進程
互斥關系：寫進程—寫進程、寫進程—讀進程。讀進程與讀進程不存在互斥問題。
- 寫者進程和任何進程都互斥，設置一個互斥信號量rw，在寫者訪問共享文件前后分別執行P、V操作。讀者進程和寫者進程也要互斥，因此讀者訪問共享文件前后也要對rw執行P、V操作.
- P(rw)和V(rw)其實就是對共享文件的“加鎖”和“解鎖”。既然各個讀進程需要同時程與寫進程又必須互斥訪問，那么我們可以讓第一個訪問文件的讀進程“加鎖”，讓最后一個訪問完文件的讀進程“解鎖”。可以設置一個整數變量count 來記錄當前有幾個讀進程在訪問文件。
如何實現
此種實現是讀進程優先的，讀進程一直進入，則會導致寫進程餓死！
寫優先，但不是真正的寫優先，相對公平的先來先服務原則，又叫做讀寫公平法！
哲學家進餐問題
問題描述
一張圓桌上坐著5名哲學家，每兩個哲學家之間的桌上擺一根筷子，桌子的中間是一碗米飯。哲學家們傾注畢生的精力用于思考和進餐，哲學家在思考時，并不影響他人。只有當哲學家饑餓時，才試圖拿起左、右兩根筷子（一根一根地拿起）。如果筷子已在他人手上，則需等待。饑餓的哲學家只有同時拿起兩根筷子才可以開始進餐，當進餐完畢后，放下筷子繼續思考。
問題分析
這些進程之間只存在互斥關系，但是與之前接觸到的互斥關系不同的是，每個進程都需要同時持有兩個臨界資源，因此就有“死鎖”問題的隱患。
- 關系分析。系統中有5個哲學家進程，5位哲學家與左右鄰居對其中間筷子的訪問是互斥關系。
- 整理思路。這個問題中只有互斥關系，但與之前遇到的問題不同的是，每個哲學家進程需要同時持有兩個臨界資源才能開始吃飯。如何避免臨界資源分配不當造成的死鎖現象，是哲學家問題的精髓。
- 信號量設置。定義互斥信號量數組 chopstick[5]={1,1,1,1,1} 用于實現對5個筷子的互斥訪問。并對哲學家按0~4編號，哲學家 i 左邊的筷子編號為i，右邊的筷子編號為 (i+1)%5。
如何實現
錯誤方案
合理方案
- 可以對哲學家進程施加一些限制條件，比如最多允許四個哲學家同時進餐。這樣可以保證至少有一個哲學家是可以拿到左右兩只筷子的
- 要求奇數號哲學家先拿左邊的筷子，然后再拿右邊的筷子，而偶數號哲學家剛好相反。用這種方法可以保證如果相鄰的兩個奇偶號哲學家都想吃飯，那么只會有其中一個可以拿起第一只筷子，另一個會直接阻塞。這就避免了占有一支后再等待另一只的情況。
- 僅當一個哲學家左右兩支筷子都可用時才允許他抓起筷子。
第三種方案的實現：
可以保證至少有一人可以吃到飯！
11、管程
為什么要引入管程
信號量機制存在的問題：編寫程序困難、易出錯
能不能設計一種機制，讓程序員寫程序時不需要再關注復雜的PV操作，讓寫代碼更輕松呢？
1973年，Brinch Hansen 首次在程序設計語言 (Pascal)中引入了“管程”成分，即一種高級同步機制
管程定義
管程是一種特殊的軟件模塊，由這些部分組成：
類似于 類 ！
管程基本特征
前兩句類似：類對象對類的訪問！
管程解決生產者消費者問題
引入管程的目的無非就是要更方便地實現進程互斥和同步。
簡單來說：封裝思想！
- 需要在管程中定義共享數據（如生產者消費者問題的緩沖區）
- 需要在管程中定義用于訪問這些共享數據的“入口”——其實就是一些函數（如生產者消費者問題中，可以定義一個函數用于將產品放入緩沖區，再定義一個函數用于從緩沖區取出產品）
- 只有通過這些特定的“入口”才能訪問共享數據
- 管程中有很多“入口”，但是每次只能開放其中一個“入口”，并且只能讓一個進程或線程進入（如生產者消費者問題中，各進程需要互斥地訪問共享緩沖區。管程的這種特性即可保證一個時間段內最多只會有一個進程在訪問緩沖區 注意：這種互斥特性是由編譯器負責實現的，程序員不用關心）
- 可在管程中設置條件變量及等待 / 喚醒操作以解決同步問題?？梢宰屢粋€進程或線程在條件變量上等待（此時，該進程應先釋放管程的使用權，也就是讓出“入口”）；可以通過喚醒操作將等待在條件變量上的進程或線程喚醒。
12、死鎖
腦圖
什么是死鎖
哲學家進餐問題中，如果5位哲學家進程并發執行，都拿起了左手邊的筷子…
每位哲學家都在等待自己右邊的人放下筷子，這些哲學家進程都因等待筷子資源而被阻塞。即發生“死鎖”
在并發環境下，各進程因競爭資源而造成的一種互相等待對方手里的資源，導致各進程都阻塞，都無法向前推進的現象，就是“死鎖”。發生死鎖后若無外力干涉,這些進程都將無法向前推進。
死鎖&饑餓&死循環
死鎖：各進程互相等待對方手里的資源，導致各進程都阻塞，無法向前推進的現象。
饑餓：由于長期得不到想要的資源，某進程無法向前推進的現象。比如:在短進程優先(SPF) 算法中，若有源源不斷的短進程到來，則長進程將一直得不到處理機， 從而發生長進程“饑餓”。
死循環：某進程執行過程中一直跳不出某個循環的現象。有時是因為程序邏輯bug導致的，有時是程序員故意設計的。
死鎖產生必要條件
產生死鎖必須同時滿足以下四個條件，只要其中任一條件不成立，死鎖就不會發生。
互斥條件：只有對必須互斥使用的資源的爭搶才會導致死鎖(如哲學家的筷子、打印機設備)。像內存、揚聲器這樣可以同時讓多個進程使用的資源是不會導致死鎖的(因為進程不用阻塞等待這種資源)。
不剝奪條件：進程所獲得的資源在未使用完之前，不能由其他進程強行奪走，只能主動釋放。
請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程被阻塞，但又對自己已有的資源保持不放。
循環等待條件：存在一種進程資源的循環等待鏈，鏈中的每一個進程已獲得的資源同時被下一個進程所請求。
注意：發生死鎖時一定有循環等待，但是發生循環等待時未必死鎖( 循環等待是死鎖的必要不充分條件)
如果同類資源數大于1，則即使有循環等待，也未必發生死鎖。但如果系統中每類資源都只有一個，那循環等待就是死鎖的充分必要條件了。
什么時候發生死鎖
對系統資源的競爭。各進程對不可剝奪的資源(如打印機)的競爭可能引起死鎖，對可剝奪的資源(CPU)的競爭是不會引起死鎖的。
進程推進順序非法。請求和釋放資源的順序不當，也同樣會導致死鎖。例如，并發執行的進程P1、P2分別申請并占有了資源R1、R2，之后進程P1又緊接著申請資源R2，而進程P2又申請資源R1,兩者會因為申請的資源被對方占有而阻塞，從而發生死鎖。
信號量的使用不當也會造成死鎖。如生產者~消費者問題中，如果實現互斥的P操作在實現同步的P操作之前，就有可能導致死鎖。(可以把互斥信號量、同步信號量也看做是一種抽象的系統資源)
總之，對不可剝奪資源的不合理分配，可能導致死鎖。
死鎖處理策略
預防死鎖
腦圖
破壞互斥條件
互斥條件：只有對必須互斥使用的資源的爭搶才會導致死鎖。
如果把只能互斥使用的資源改造為允許共享使用，則系統不會進入死鎖狀態。比如 : SPOOLing技術。
操作系統可以采用SPOOLing 技術把獨占設備在邏輯上改造成共享設備。比如，用SPOOLing技術將打印機改造為共享設備…（打印機添加任務隊列即可）
該策略的缺點：并不是所有的資源都可以改造成可共享使用的資源。并且為了系統安全，很多地方還必須保護這種互斥性。因此，很多時候都無法破壞互斥條件。
破壞不剝奪條件
不剝奪條件：進程所獲得的資源在未使用完之前，不能由其他進程強行奪走，只能主動釋放。
方案一：當某個進程請求新的資源得不到滿足時，它必須立即釋放保持的所有資源，待以后需要時再重新申請。也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件。
方案二：當某個進程需要的資源被其他進程所占有的時候，可以由操作系統協助，將想要的資源強行剝奪。這種方式一般需要考慮各進程的優先級（比如：剝奪調度方式，就是將處理機資源強行剝奪給優先級更高的進程使用）
該策略的缺點：
- 實現起來比較復雜。
- 釋放已獲得的資源可能造成前一階段工作的失效。因此這種方法一般只適用于易保存和恢復狀態的資源，如CPU。
- 反復地申請和釋放資源會增加系統開銷，降低系統吞吐量。
- 若采用方案一，意味著只要暫時得不到某個資源，之前獲得的那些資源就都需要放棄，以后再重新申請。如果一直發生這樣的情況，就會導致進程饑餓。
破壞請求和保持條件
請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程被阻塞，但又對自己已有的資源保持不放。
可以采用靜態分配方法，即進程在運行前一次申請完它所需要的全部資源，在它的資源未滿足前，不讓它投入運行。一旦投入運行后，這些資源就一直歸它所有，該進程就不會再請求別的任何資源了。
該策略實現起來簡單，但也有明顯的缺點：
- 有些資源可能只需要用很短的時間，因此如果進程的整個運行期間都一直保持著所有資源，就會造成嚴重的資源浪費，資源利用率極低。另外，該策略也有可能導致某些進程饑餓。
破壞循環等待條件
循環等待條件：存在一種進程資源的循環等待鏈，鏈中的每一個進程已獲得的資源同時被下一個進程所請求。
可采用順序資源分配法。首先給系統中的資源編號，規定每個進程必須按編號遞增的順序請求資源，同類資源（即編號相同的資源）一次申請完。
原理分析：一個進程只有已占有小編號的資源時，才有資格申請更大編號的資源。按此規則，已持有大編號資源的進程不可能逆向地回來申請小編號的資源，從而就不會產生循環等待的現象。
該策略的缺點：
避免死鎖
安全序列&不安全狀態&死鎖
安全序列，就是指如果系統按照這種序列分配資源，則每個進程都能順利完成。只要能找出一個安全序列，系統就是安全狀態。當然，安全序列可能有多個。
如果分配了資源之后，系統中找不出任何一個安全序列，系統就進入了不安全狀態。這就意味著之后可能所有進程都無法順利的執行下去。當然，如果有進程提前歸還了一些資源，那系統也有可能重新回到安全狀態，不過我們在分配資源之前總是要考慮到最壞的情況。
如果系統處于安全狀態，就一定不會發生死鎖。如果系統進入不安全狀態，就可能發生死鎖（處于不安全狀態未必就是發生了死鎖，但發生死鎖時一定是在不安全狀態）
因此可以在資源分配之前預先判斷這次分配是否會導致系統進入不安全狀態，以此決定是否答應資源分配請求。這也是“銀行家算法”的核心思想。
銀行家算法
銀行家算法是荷蘭學者Dijkstra 為銀行系統設計的，以確保銀行在發放現金貸款時，不會發生不能滿足所有客戶需要的情況。后來該算法被用在操作系統中，用于避免死鎖。
核心思想：在進程提出資源申請時，先預判此次分配是否會導致系統進入不安全狀態。如果會進入不安全狀態，就暫時不答應這次請求，讓該進程先阻塞等待。
銀行家算法步驟：
- 檢查此次申請是否超過了之前聲明的最大需求數
- 檢查此時系統剩余的可用資源是否還能滿足這次請求
- 試探著分配，更改各數據結構
- 用安全性算法檢查此次分配是否會導致系統進入不安全狀態
數據結構：
- 長度為m 的一維數組Available 表示還有多少可用資源
- n * m 矩陣Max 表示各進程對資源的最大需求數
- n * m 矩陣Allocation 表示已經給各進程分配了多少資源
- Max – Allocation = Need 矩陣表示各進程最多還需要多少資源
- 用長度為m 的一位數組Request 表示進程此次申請的各種資源數
安全性算法步驟：
- 檢查當前的剩余可用資源是否能滿足某個進程的最大需求，如果可以，就把該進程加入安全序列，
- 并把該進程持有的資源全部回收。
- 不斷重復上述過程，看最終是否能讓所有進程都加入安全序列。
死鎖的檢測和解除
腦圖
死鎖檢測
為了能對系統是否已發生了死鎖進行檢測，必須：
- 用某種數據結構來保存資源的請求和分配信息；
- 提供一種算法，利用上述信息來檢測系統是否已進入死鎖狀態。
如果系統中剩余的可用資源數足夠滿足進程的需求，那么這個進程暫時是不會阻塞的，可以順利地執行下去。如果這個進程執行結束了把資源歸還系統，就可能使某些正在等待資源的進程被激活，并順利地執行下去。相應的，這些被激活的進程執行完了之后又會歸還一些資源，這樣可能又會激活另外一些阻塞的進程…
如果按上述過程分析，最終能消除所有邊，就稱這個圖是可完全簡化的。此時一定不發生死鎖（相當于能找到一個安全序列）
如果最終不能消除所有邊，那么此時就是發生了死鎖
死鎖例子：
死鎖解除
一旦檢測出死鎖的發生，就應該立即解除死鎖。
補充：并不是系統中所有的進程都是死鎖狀態，用死鎖檢測算法化簡資源分配圖后，還連著邊的那些進程就是死鎖進程
解除死鎖的主要方法有：
- 資源剝奪法。掛起（暫時放到外存上）某些死鎖進程，并搶占它的資源，將這些資源分配給其他的死鎖進程。但是應防止被掛起的進程長時間得不到資源而饑餓。
- 撤銷進程法（或稱終止進程法）。強制撤銷部分、甚至全部死鎖進程，并剝奪這些進程的資源。這種方式的優點是實現簡單，但所付出的代價可能會很大。因為有些進程可能已經運行了很長時間，已經接近結束了，一旦被終止可謂功虧一簣，以后還得從頭再來。
- 進程回退法。讓一個或多個死鎖進程回退到足以避免死鎖的地步。這就要求系統要記錄進程的歷史信息，設置還原點。
如何絕對對誰動手？
- 進程優先級低的
- 已執行時間少的
- 還有很久才能完成的
- 進程使用資源多的
- 交互式和批處理式，優先處理批處理式
三、內存管理
1、內存基礎知識
內存
- 內存是用于存放數據的硬件
- 程序執行前需要先放到內存中才能被cpu處理
- 如果計算機"按字節編址", 每個存儲單元大小為 8 bit
- 如果計算機"按字編址", 每個存儲單元大小為 16 bit
指令的編指一般采用邏輯地址，即相對地址
物理地址 = 起始地址 + 邏輯地址
相對地址又稱邏輯地址，絕對地址又稱物理地址。
進程運行基本原理
- 編輯
- 編譯：由編譯程序將用戶源代碼編譯成若干個目標模塊
- 鏈接
- 裝入
三種鏈接方式
鏈接：由連接程序將編譯后形成的一組目標模塊以及所需函數連接在一起, 形成一個完整的裝入模塊
- 靜態鏈接：在程序運行之前，先將各目標模塊以及它們所需的庫函數連接成一個完整的可執行文件（裝入模塊），之后不再拆開。
- 裝入時動態鏈接：將各目標模塊裝入內存時，邊裝入邊鏈接的鏈接方式。
- 運行時動態鏈接：在程序執行中需要該目標模塊時，才對它進行鏈接。其優點是便于修改和更新，便于實現對目標模塊的共享。
三種裝入方式
裝入：由裝入程序將裝入模塊裝入內存運行
為了使編程更方便，程序員寫程序時應該只需關注指令、數據的邏輯性。而邏輯地址到物理地址的轉換（這個過程稱為地址重定位），應該由操作系統負責，這樣就保證了程序員寫程序時不需要關注物理內存的實際情況。
- 絕對裝入
在編譯時，如果知道程序將放到內存的哪個位置，編譯程序將產生絕對地址的目標代碼, 裝入程序按照裝入模塊中的地址，將程序和數據裝入內存【靈活性低, 只適合單道程序環境】
絕對裝入只適用于單道程序環境。還未產生操作系統，由編譯器完成！
程序中使用的絕對地址，可在編譯或匯編時給出，也可由程序員直接賦予。通常情況下都是編譯或匯編時再轉換為絕對地址。
- 靜態重定位
又稱為可重定位裝入。 編譯, 鏈接后的裝入模塊地址都是從 0 開始的，指令中使用的地址和數據存放的地址都是相對于起始地址而言的邏輯地址?？梢愿鶕却娴漠斍盃顩r將裝入模塊裝入到內存的適當位置。裝入時對地址進行"重定位"，邏輯地址變換為物理地址（地址變換是在裝入時一次完成的）。【早期多道批處理系統】
靜態重定位的特點是在一個作業裝入內存時，必須分配其要求的全部內存空間，如果沒有足夠的內存，就不能裝入該作業。作業一旦進入內存后，在運行期間就不能再移動，也不能再申請內存空間。
- 動態重定位
又稱動態運行時裝入。編譯、鏈接后的裝入模塊的地址都是從0開始的，裝入程序把裝入模塊裝入內存后不會立即把邏輯地址轉換為物理地址，而是把地址轉換推遲到程序真正要執行時才進行。因此裝入內存后所有的地址依然是邏輯地址。這種方式需要一個重定位寄存器（存放裝入模塊的起始位置）的支持。【現代操作系統】
操作系統內存管理
1、2、4 將在下方講解！
2、內存保護采用的方法
3、內存空間的擴充
大綱
- 覆蓋技術
- 交換技術
- 虛擬存儲技術
覆蓋技術
覆蓋技術：將程序分為多個段，常用的段常駐內存，不常用的段在需要的時候調入內存
內存中分為一個"固定區" 和若干個"覆蓋區"，常用的段放在固定區，不常用的段放在覆蓋區
缺點：必須由程序員聲明覆蓋結構， 對用戶不透明， 增加了用戶的編程負擔，覆蓋技術只用于早期的操作系統中。
交換技術
交換技術：內存空間緊張時, 系統將內存中某些進程暫時換出外存，把外存中某些已具備運行條件的進程換入內存(即進程在內存與磁盤間動態調度)
應該在外存（磁盤）的什么位置保存被換出的進程？
具有對換功能的操作系統中，通常把磁盤空間分為文件區和對換區兩部分。文件區主要用于存放文件，主要追求存儲空間的利用率，因此對文件區空間的管理采用離散分配方式；對換區空間只占磁盤空間的小部分，被換出的進程數據就存放在對換區。由于對換的速度直接影響到系統的整體速度，因此對換區空間的管理主要追求換入換出速度，因此通常對換區采用連續分配方式。總之，對換區的I/O速度比文件區的更快。
什么時候應該交換？
交換通常在許多進程運行且內存吃緊時進行，而系統負荷降低就暫停。例如：在發現許多進程運行時經常發生缺頁，就說明內存緊張，此時可以換出一些進程;如果缺頁率明顯下降，就可以暫停換出。
應該換出哪些進程？
可優先換出阻塞進程；可換出優先級低的進程；為了防止優先級低的進程在被調入內存后很快又被換出，有的系統還會考慮進程在內存的駐留時間。
PCB仍然得常駐內存！
虛擬存儲技術
大綱
傳統存儲方式問題
-
一次性：作業必須一次性全部裝入內存后才能開始運行
- 作業很大時，無法裝入導致大作業無法運行
- 大量作業要求運行時內存無法容納所有作業，導致多道程序并發度下降
-
駐留性：一旦作業被裝入內存，就會一直駐留在內存中，直到作業運行結束，這樣會導致內存中駐留大量的，暫時用不到的數據，浪費內存資源。
高速緩沖技術
是對局部性原理的應用！
將近期會頻繁訪問到的數據放到更高速的存儲器中，暫時用不到的數據放在更低速存儲器中。
虛擬內存的定義和特征
- 在程序裝入時，將程序中很快會用到的部分裝入內存，暫時用不到的部分留在外存，就可以讓程序開始執行。
- 在程序執行過程中，當所訪問的信息不在內存時，由操作系統負責將所需信息由外存調入內存，然后繼續執行程序。請求調頁/段
- 內存空間不夠時， 操作系統負責將內存中暫時用不到的信息換出到外存。頁面置換
- 在用戶看來，就有一個比實際內存大很多的內存，這就叫虛擬內存。
虛擬內存的最大容量是由計算機的地址結構（CPU的尋址范圍）確定的
虛擬內存的實際容量 = min（內存容量+外存容量，CPU尋址范圍）
特征：
多次性：無需在作業運行時一次性全部裝入內存，而是允許被分成多次調入內存。
對換性：在作業運行時無需一直常駐內存，而是允許在作業運行過程中，將作業換入、換出。
虛擬性：從邏輯上擴充了內存的容量，使用戶看到的內存容量遠大于實際容量。
虛擬內存的實現
虛擬內存技術，允許一個作業分多次調入內存。如果采用連續分配方式，會不方便實現。因此，虛擬內存的實現需要建立在離散分配（非連續分配）的內存管理方式基礎上。
對應傳統的三種非連續分配存儲管理，有三種虛擬存儲的實現：
- 請求分頁存儲管理
- 請求分段存儲管理
- 請求段頁式存儲管理
調入：在程序執行過程中，當所訪問的信息不在內存時，由操作系統負責將所需信息從外存調入內存，然后繼續執行程序。（操作系統要提供請求調頁 / 調段功能）
調出：若內存空間不夠，由操作系統負責將內存中暫時用不到的信息換出到外存。（操作系統要提供頁面置換 / 段置換的功能）
請求分頁存儲管理
與基本分頁管理方式的區別：
- 調入：請求調頁
- 調出：頁面置換
大綱
頁表機制
與基本分頁管理相比，請求分頁管理中，為了實現“請求調頁”，操作系統需要知道每個頁面是否已經調入內存;如果還沒調入，那么也需要知道該頁面在外存中存放的位置。
當內存空間不夠時，要實現“頁面置換”，操作系統需要通過某些指標來決定到底換出哪個頁面;有的頁面沒有被修改過，就不用再浪費時間寫回外存。有的頁面修改過，就需要將外存中的舊數據覆蓋，因此，操作系統也需要記錄各個頁面是否被修改的信息。
缺頁中斷機構
在請求分頁操作系統中，每當要訪問的頁面不在內存時，便產生一個缺頁中斷, 然后由操作系統的缺頁中斷處理程序處理中斷。
此時缺頁的進程阻塞，放入阻塞隊列，調頁完成后再將其喚醒, 放回就緒隊列。
- 如果內存中有空閑塊，則為進程分配一個空閑塊，將所缺頁面裝入該塊，并修改頁表中相應的頁表項
- 如果內存中沒有空閑塊，則由頁面置換算法選擇一個頁面淘汰，若該頁面在內存期間被修改過，則要將其寫回外存，未修改過的頁面不用寫回外存。
缺頁中斷是因為當前執行的指令想要訪問目標頁面未調入內存而產生的，因此屬于內中斷（故障） 。
一條指令在執行期間，可能產生多次缺頁中斷。(如: copy A to B，即將邏輯地址A中的數據復制到邏輯地址B，而A、B屬于不同的頁面，則有可能產生兩次中斷）
地址變換機構
- 新增步驟1：請求調頁（查到頁表項時進行判斷）
- 新增步驟2：頁面置換（需要調入頁面，但沒有空閑內存塊時進行)
- 新增步驟3：需要修改請求頁表中新增的表項
頁面置換算法
大綱
詳細參考： https://www.itnxd.cn/posts/8398.html#五、頁面置換算法
頁面的換入、換出需要磁盤I/O，會有較大的開銷，因此好的頁面置換算法應該追求更少的缺頁率！
最佳置換算法(OPT)
優先淘汰以后永不使用或者在最長時間內不會使用的頁面，保證最低的缺頁率。
但是操作系統無法預判頁面訪問序列，這種算法是無法實現的。
先進先出置換算法(FIFO)
優先淘汰最早進入內存的頁面。
實現 ：將調入內存的頁面根據調入的先后順序排成一個隊列，需要置換頁面的時候選擇隊首的頁面。
實現簡單；算法性能差，不適應進程實際運行時的規律，可能出現 Belady 異常。
Belady異常――當為進程分配的物理塊數增大時，缺頁次數不減反增的異?，F象。
只有FIFO算法會產生Belady異常。
最近最久未使用置換算法(LRU)
優先淘汰最近最久未使用的頁面。
性能好，但實現起來需要專門的硬件支持，算法開銷大。
時鐘置換算法(CLOCK)
又叫做 最近未用算法 NRU
為每個頁面設置一個訪問位，再將內存中的頁面都通過鏈接指針鏈接成一個循環隊列。
循環掃描各頁面，第一輪淘汰訪問位 = 0 的，并將掃描過的頁面訪問位改為1。若第一輪沒選中，則進行第二輪掃描。（最多會掃描兩輪！）
實現簡單，算法開銷小；但未考慮頁面是否被修改過。
簡單的時鐘置換算法僅考慮到了一個頁面最近是否被訪問過，但是事實上，如果被淘汰的頁面沒有被修改過，就不需要執行I/O操作寫回外存。只有被淘汰的頁面被修改過時，才需要寫回外存。
因此, 除了考慮一個頁面最近有沒有被訪問過之外，操作系統還應該考慮頁面有沒有被修改過。
在其他條件都相同時，應該優先淘汰沒有修改過的頁面, 避免I/O操作，這就是改進型的時鐘置換算法的思想。
改進型的時鐘置換算法
利用**(訪問位，修改位)** 的形式表示各頁面狀態
- 第一輪 : 找第一個 (0, 0)的幀用于替換 ( 不修改標志位 )
- 第二輪 : 找第一個 (0, 1)的幀用于替換 ( 將所有掃描過的幀訪問位設為0)
- 第三輪 : 找第一個 (0, 0)的幀用于替換 ( 不修改標志位 )
- 第四輪 : 找第一個 (0, 1)的幀用于替換
簡而言之：按照00,01,10,11的優先級進行替換！
算法開銷小，性能也不錯。
最多掃描四輪！
頁面分配策略
大綱
駐留集：請求分頁存儲管理器中給進程分配的物理塊的集合。
在采用虛擬存儲技術的系統中, 駐留集的大小一般小于進程的總大小
- 如果駐留集太小，會導致缺頁頻繁，系統要花大量的時間來處理缺頁，實際用于進程推進的時間很少。
- 如果駐留集太大，會導致多道程序并發度下降，資源利用率降低。
策略
- 固定分配：操作系統為每個進程分配一組固定數目的物理塊，在進程運行期間不再改變。即，駐留集大小不變。
- 可變分配：先為每個進程分配一定數目的物理塊，在進程運行期間，可根據情況做適當的增加或減少。即，駐留集大小可變。
局部置換：發生缺頁時只能選進程自己的物理塊進行置換。
全局置換：可以將操作系統保留的空閑物理塊分配給缺頁進程，也可以將別的進程持有的物理塊置換到外存，再分配給缺頁進程。
頁面分配&置換策略？
固定分配局部置換：系統為每個進程分配一定數量的物理塊，在整個運行期間都不改變。若進程在運行中發生缺頁，則只能從該進程在內存中的頁面中選出一頁換出，然后再調入需要的頁面。這種策略的缺點是:很難在剛開始就確定應為每個進程分配多少個物理塊才算合理。(采用這種策略的系統可以根據進程大小、優先級、或是根據程序員給出的參數來確定為一個進程分配的內存塊數)
可變分配全局置換：剛開始會為每個進程分配一定數量的物理塊。操作系統會保持一個空閑物理塊隊列。當某進程發生缺頁時，從空閑物理塊中取出一塊分配給該進程;若已無空閑物理塊，則可選擇一個未鎖定的頁面換出外存，再將該物理塊分配給缺頁的進程。采用這種策略時，只要某進程發生缺頁，都將獲得新的物理塊，僅當空閑物理塊用完時，系統才選擇一個未鎖定的頁面調出。被選擇調出的頁可能是系統中任何一個進程中的頁，因此這個被選中的進程擁有的物理塊會減少，缺頁率會增加。
可變分配局部置換：剛開始會為每個進程分配一定數量的物理塊。當某進程發生缺頁時，只允許從該進程自己的物理塊中選出一個進行換出外存。如果進程在運行中頻繁地缺頁，系統會為該進程多分配幾個物理塊，直至該進程缺頁率趨勢適當程度;反之，如果進程在運行中缺頁率特別低，則可適當減少分配給該進程的物理塊。
- 可變分配全局置換：只要缺頁就給分配新物理塊
- 可變分配局部置換：要根據發生缺頁的頻率來動態地增加或減少進程的物理塊
何時調入頁面？
預調頁策略：根據局部性原理（主要指空間局部性），一次調入若干個相鄰的頁面可能比一次調入一個頁面更高效。但如果提前調入的頁面中大多數都沒被訪問過，則又是低效的。因此可以預測不久之后可能訪問到的頁面，將它們預先調入內存，但目前預測成功率只有50%左右。故這種策略主要用于進程的首次調入，由程序員指出應該先調入哪些部分。（運行前調入）
請求調頁策略：進程在運行期間發現缺頁時才將所缺頁面調入內存。由這種策略調入的頁面一定會被訪問到，但由于每次只能調入一頁，而每次調頁都要磁盤I/O操作，因此I/O開銷較大。（運行時調入）
何處調入頁面？
- 系統擁有足夠的對換區空間：頁面的調入、調出都是在內存與對換區之間進行，這樣可以保證頁面的調入、調出速度很快。在進程運行前，需將進程相關的數據從文件區復制到對換區。
- 系統缺少足夠的對換區空間：凡是不會被修改的數據都直接從文件區調入，由于這些頁面不會被修改，因此換出時不必寫回磁盤，下次需要時再從文件區調入即可。對于可能被修改的部分，換出時需寫回磁盤對換區，下次需要時再從對換區調入。
- UNIX方式：運行之前進程有關的數據全部放在文件區，故未使用過的頁面，都可從文件區調入。若被使用過的頁面需要換出，則寫回對換區，下次需要時從對換區調入。
抖動現象？
剛剛換出的頁面馬上又要換入內存，剛剛換入的頁面馬上又要換出外存，這種頻繁的頁面調度行為稱為抖動，或顛簸。
產生抖動的主要原因是進程頻繁訪問的頁面數目高于可用的物理塊數( 分配給進程的物理塊不夠)。
- 為進程分配的物理塊太少，會使進程發生抖動現象。
- 為進程分配的物理塊太多，又會降低系統整體的并發度，降低某些資源的利用率
為了研究為應該為每個進程分配多少個物理塊，Denning提出了進程“工作集”的概念
工作集？
- 工作集：指在某段時間間隔里，進程實際訪問頁面的集合。
- 駐留集：指請求分頁存儲管理中給進程分配的內存塊的集合。
工作集大小可能小于窗口尺寸，實際應用中，操作系統可以統計進程的工作集大小，根據工作集大小給進程分配若干內存塊。如:窗口尺寸為5，經過一段時間的監測發現某進程的工作集最大為3，那么說明該進程有很好的局部性，可以給這個進程分配3個以上的內存塊即可滿足進程的運行需要。
一般來說，駐留集大小不能小于工作集大小，否則進程運行過程中將頻繁缺頁。
拓展：基于局部性原理可知，進程在一段時間內訪問的頁面與不久之后會訪問的頁面是有相關性的。因此，可以根據進程近期訪問的頁面集合(工作集）來設計一種頁面置換算法――選擇一個不在工作集中的頁面進行淘汰。
4、內存空間的分配和回收
大綱
- 連續分配管理方式
- 單一連續分配
- 固定分區分配
- 動態分區分配
- 非連續分配管理方式
- 基本分頁存儲管理
- 基本分段存儲管理
- 段頁式存儲管理
連續分配管理方式
連續分配：指為用戶進程分配的必須是一個連續的內存空間。
單一連續分配
在單一連續分配的方式中, 內存被分為系統區和用戶區， 系統區用于存放操作系統的相關數據，用戶區用于存放用戶進程的相關數據。內存中只能有一道用戶程序，用戶程序獨占整個用戶區空間。
優點 : 實現簡單, 無外部碎片; 可以采用覆蓋技術擴充內存; 不一定需要采取內存保護
缺點 : 只能用于單用戶, 單任務的操作系統中; 有內部碎片; 存儲器利用率極低
內部碎片 : 分配給某進程的內存區域有一部分沒有用上，即存在" 內部碎片 ".
外部碎片 : 內存中的某些空閑分區由于太小而難以利用
固定分區分配
在產生了支持多道程序的系統后，為了能在內存中裝入多道程序而互相之間不產生干擾，將整個用戶區劃分為若干個固定大小的分區(分區大小可以相等也可以不相等)，在每個分區中只能裝入一道作業， 形成了最早的可運行多道程序的內存管理方式。
固定分區分配
- 分區大小相等：缺乏靈活性，但是很適合用于用一臺計算機控制多個相同對象的場合
- 分區大小不等：增加了靈活性，可以滿足不同大小的進程需求。根據常在系統中運行的作業大小情況進行劃分
操作系統如何記錄內存中的各個分區？
操作系統建立分區說明表來實現各個分區的分配和回收。
每個表對應一個分區，通常按分區大小排列。每個表項包括對應分區的大小，起始地址，狀態（是否已分配）。
用數據結構的數組（或鏈表）即可表示這個表。
當某用戶程序要裝入內存時，由操作系統內核程序根據用戶程序大小檢索該表，從中找到一個能滿足大小的、未分配的分區，將之分配給該程序，然后修改狀態為 ” 已分配 “ 。
優點：實現簡單，無外部碎片。
缺點：
- 當用戶程序太大時，可能所有的分區都不能滿足需求，此時不得不采用覆蓋技術來解決，但這又會降低性能。
- 會產生內部碎片，內存利用率低。
動態分區分配
動態分區分配又稱為可變分區分配， 這種分配方式不會預先劃分內存分區。而是在進程裝入內存時根據進程大小動態地建立分區，并使得分區的大小正好適合進程的需要。系統分區的大小和數目是可變的！
系統要用什么樣的數據結構記錄內存的使用情況？
- 空閑分區表：每個空閑分區對應一個表項。表項中包含分區號、分區大小、分區起始地址等信息。
- 空閑分區鏈：每個分區的其實部分和末尾部分分別設置前向指針和后向指針。起始部分處還可記錄分區大小等信息。
動態分配不會產生內部碎片, 而會產生外部碎片, 外部碎片可以通過" 緊湊"的方式解決。
當很多個空閑分區都能滿足需求時，應該選擇哪個分區進行分配?
把一個新作業裝入內存時，須按照一定的動態分區分配算法（后面詳細講解），從空閑分區表（或空閑分區鏈）中選出一個分區分配給該作業。由于分配算法算法對系統性能有很大的影響，因此人們對它進行了廣泛的研究。
如何進行分區的分配與回收操作?
- 修改表項或鏈表節點值（分區還有剩余）
- 刪除表項或鏈表節點（分區恰好分配完畢）
- 兩個空閑分區的合并
動態分區分配算法
首次適應算法
每次都從低地址開始查找，找到第一個能滿足大小的空閑分區。
實現：把空閑分區按地址遞增的次序排列。
每次分配內存時順序地查找空閑分區鏈，找到大小能滿足要求的第一個空閑分區。
優點：綜合看性能最好。算法開銷小，回收分區后一般不需要對空閑分區隊列重新排序。
最佳適應算法
優先使用小的空閑分區
實現： 空閑分區按容量遞增次序排序。
每次分配內存時順序查找空閑分區鏈, 找到大小能滿足要求的第一個空閑分區。
優點：會有更多的大分區被保留下來，更能滿足大進程需求。
缺點：每次都選擇最小的分區進行分配，會留下越來越多的容量很小難以利用的內存塊，即產生很多的外部碎片；算法開銷大，回收分區后可能需要對空閑分區隊列重新排序。
最壞適應算法
優先使用大的空閑分區
實現： 空閑分區按容量遞減次序排序
優點：可以減少難以利用的小碎片。
缺點：每次都選用最大的分區進行分配，當較大的連續空閑區被小號之后，如果有大進程到來則沒有內存分區可以利用；算法開銷大。
鄰近適應算法
在首次適應算法的基礎上，每次都從上次查找結束的位置開始查找空閑分區鏈(表)，找到大小能滿足的第一個空閑分區。
優點：不用每次都從低地址的小分區開始檢索。算法開銷小。
缺點：鄰近適應算法導致無論低地址還是高地址的空閑分區都有相同的概率被使用，也就導致了高地址部分的大分區更可能被使用劃分為小分區，最后導致沒有大分區可用。
小總結
算法開銷大：最佳適應法, 最壞適應法 ( 需要經常排序)
算法開銷小：首次適應算法, 鄰近適應算法
非連續分配管理方式
連續分配管理方式缺點：
- 固定分區分配：缺乏靈活性，會產生大量的內部碎片,內存的利用率很低。
- 動態分區分配：會產生很多外部碎片，雖然可以用“緊湊”技術來處理，但是“緊湊”的時間代價很高
基于這一思想，產生了“非連續分配方式”，或者稱為“離散分配方式”。
非連續：為用戶進程分配的可以是一些分散的內存空間！
基本分頁存儲管理
大綱
分頁存儲基本概念
思想：把內存分為一個個相等的小分區, 再按照分區大小把進程拆分成一個個小部分.
頁框：將內存大小分為一個個大小相等的分區，每個分區就是一個 “ 頁框 ”，或稱 “ 頁幀 ”、“ 內存塊 ”、“ 物理塊 ”。每個頁框有一個編號，即 “ 頁框號 ”，或稱 “ 內存塊號 ”、“ 頁幀號 ”、“ 物理塊號 ” ，頁框號從 0 開始。
頁面：將用戶進程的地址空間也分為與頁框大小相等的一個個區域，稱為 “ 頁 ” 或 “ 頁面 ”。每個頁面也有一個編號，即 “ 頁號 ”，頁號也是從 0 開始。
- 進程的最后一個頁面可能沒有一個頁框那么大。因此。頁框不能太大，否則可能產生過大的內部碎片。
- 操作系統以頁框為單位為各個進程分配內存空間。進程的每個頁面分別放入一個頁框中。也就是說，進程的頁面與內存的頁框有一一對應的關系。
- 各個頁面不必連續存放，也不必按先后順序來，可以放到不相鄰的各個頁框中。
如何實現地址轉換
例子：
CPU執行指令1，需要訪問邏輯地址為80的內存單元，如何轉化為物理地址?
邏輯地址為80的內存單元，應該在1號頁，該頁在內存中的起始位置為450，邏輯地址為80的內存單元相對于該頁的起始地址而言，“偏移量”應該是30。
實際物理地址 = 450 + 30 = 480
- 要算出邏輯地址對應的頁號
- 要知道該頁號對應頁面在內存中的起始地址
- 要算出邏輯地址在頁面內的“偏移量”
- 物理地址 = 頁面始址 ＋ 頁內偏移量
如何計算:
頁號 = 邏輯地址 / 頁面長度（取除法的整數部分）
頁內偏移量 = 邏輯地址 % 頁面長度（取除法的余數部分）
頁面在內存中的起始位置：操作系統需要用某種數據結構記錄進程各個頁面的起始位置。
頁號 = 80 / 50 = 1
頁內偏移量 = 80 % 50 = 30
1 號頁在內存中存放的起始位置 450
為了方便計算機計算頁號、頁內偏移量，頁面大小一般設為2的整數冪！
邏輯地址結構
邏輯地址結構包含兩個部分：前一部分為頁號，后一部分為頁內偏移量w。在上圖所示的例子中，地址長度為32位，其中0 ~ 11位為“頁內偏移量”，或稱“頁內地址”;12~31位為“頁號”。
- 如果有K位表示“頁內偏移量”，則說明該系統中，一個頁面的大小是2^K個內存單元
- 如果有M位表示“頁號”，則說明在該系統中，一個進程最多允許有2^M個頁面
頁表
解決地址轉換的第二步：計算頁號對應頁面在內存中的起始地址
為了能知道進程的每個頁面在內存中存放的位置，操作系統要為每個進程建立一張頁表。
- 一個進程對應一張頁表
- 進程的每一頁對應一個頁表項
- 每個頁表項由 “ 頁號 ” 和 “ 塊號 ” 組成
- 頁表記錄進程頁面和實際存放的內存塊之間的對應關系
- 每個頁表項的長度是相同的，頁號是“隱含”的
例子
假設某系統物理內存大小為4GB，頁面大小為4KB，則每個頁表項至少應該為多少字節?
4GB = 2^32B，4KB = 2^12B
因此4GB的內存總共會被分為 2^32 / 2^12 = 2^20 個內存塊，因此內存塊號的范圍應該是0 ~ 2^20 - 1 因此至少要20個二進制位才能表示這么多的內存塊號，因此至少要3個字節才夠 (每個字節8個二進制位，3個字節共24個二進制位)
各頁表項會按順序連續地存放在內存中
如果該頁表在內存中存放的起始地址為X，則M號頁對應的頁表項一定是存放在內存地址為 X ＋ 3 * M 因此，頁表中的**“頁號”可以是“隱含”的**。只需要知道頁表存放的起始地址和頁表項長度，即可找到各個頁號對應的頁表項存放的位置！
在本例中，一個頁表項占3B，如果進程由n個頁面，則該進程的頁表總共會占 3 * n 個字節
基本地址變換機構
大綱
用于實現邏輯地址到物理地址轉換（借助進程的頁表）的一組硬件機構
- 通常會在系統中設置一個頁表寄存器（PTR)，存放頁表在內存中的起始地址 F 和頁表長度 M。
- 進程未執行時，頁表的始址和頁表長度放在進程控制塊（PCB）中；
- 當進程被調度時，操作系統內核會把它們放到頁表寄存器中。
設頁面大小為L，邏輯地址A到物理地址E的變換過程如下:
頁表長度指的是這個頁表中總共有幾個頁表項，即總共有幾個頁；頁表項長度指的是每個頁表項占多大的存儲空間；頁面大小指的是一個頁面占多大的存儲空間
在分頁存儲管理（頁式管理）的系統中，只要確定了每個頁面的大小，邏輯地址結構就確定了。
因此，頁式管理中地址是一維的。即，只要給出一個邏輯地址，系統就可以自動地算出頁號、頁內偏移量兩個部分，并不需要顯式地告訴系統這個邏輯地址中，頁內偏移量占多少位。
- 一共需要訪問兩次內存：第一次用來查頁表，第二次用于訪問目標內存單元。
- 頁式管理中地址是一維的。
- 為了方便找到頁表項，頁表一般是放在連續的內存塊的。
- 一個頁框可以存放的頁表項就是頁框大小 / 用于表示頁表中內存塊號所占的字節數（通常內存塊號用2的整數次冪的字節表示，可以消除內存塊中的頁內碎片）
理論上，頁表項長度為3B即可表示內存塊號的范圍，但是，為了方便頁表的查詢，常常會讓一個頁表項占更多的字節，使得每個頁面恰好可以裝得下整數個頁表項。
具有快表的地址變換機構
是基本地址變換機構的改進版本！
局部性原理？
- 時間局部性：如果執行了程序中的某條指令, 那么不久之后這條指令很有可能再次執行; 如果某個數據被訪問過, 不久之后該數據很可能再次被訪問。( 程序中存在大量的循環 )
- 空間局部性：一旦程序訪問了某個存儲單元, 在不久之后, 其附近的存儲單元也很有可能被訪問到。( 很多數據在內存中連續存放 )
上小節介紹的基本地址變換機構中，每次要訪問一個邏輯地址，都需要查詢內存中的頁表。由于局部性原理，可能連續很多次查到的都是同一個頁表項。既然如此，能否利用這個特性減少訪問頁表的次數呢?
什么是快表TLB？
快表又成為聯想寄存器（TLB），是一種訪問速度比內存塊很多的高速緩沖存儲器，用來存放當前訪問的若干頁表項, 以加速地址變換的過程. 與此對應的，內存中的頁表常稱為慢表。
引入快表的地址變換過程？
由于查詢快表的速度比查詢頁表的速度快很多，因此只要快表命中，就可以節省很多時間。因為局部性原理，一般來說快表的命中率可以達到90%以上。
基本地址變換機構 VS 具有快表的地址變換機構
兩級頁表
大綱
單級頁表存在的問題？
1、假設某計算機系統按字節尋址，支持32位邏輯地址，采用分頁存儲管理，頁面大小為4KB，頁表項長度為4B。
4KB = 2^12B，因此頁內地址要用12位表示，剩余20位表示頁號。
因此，該系統中用戶進程最多有2^20 頁。相應的，一個進程的頁表中，最多會有 2^20 個頁表項，所以一個頁表最大需要2^20 * 4B = 2 ^ 22B。一個頁框（內存塊）大小為 4B，所以需要2^22 / 2^12 （頁面大小為4KB）= 2^10個頁框存儲該頁表。而頁表的存儲是需要連續存儲的，
因為根據頁號查詢頁表的方法：K號頁對應的頁表項的位置 = 頁表起始地址 + K * 4B，所以這就要求頁表的存儲必須是連續的。當頁表很大時，需要占用很多個連續的頁框。
回想一下，當初為什么使用頁表，就是要將進程劃分為一個個頁面可以不用連續的存放在內存中，但是此時頁表就需要1024個連續的頁框，與當時的目標相悖。
2、根據局部性原理可知，很多時候，進程在一段時間內只需要訪問某幾個頁面就可以正常運行了。因此沒有必要讓整個頁表都常駐內存。
- 問題一：頁表必須連續存放，因此當頁表很大時，需要占用很多個連續的頁框。（解決方法：兩級頁表）
- 問題二：沒有必要讓整個頁表常駐內存，因為進程在一段時間內可能只需要訪問某幾個特定的頁面。
- 可以在需要訪問頁面時才把頁面調入內存（解決方法：虛擬存儲技術）?？梢栽?strong>頁表項中增加一個標志位，用于表示該頁資是否已經調入內存
- 若想訪問的頁面不在內存中，則產生缺頁中斷（內中斷），然后將目標頁面從外存調入內存
解決方法
可將長長的頁表進行分組，使每個內存塊剛好可以放入一個分組，再將各組離散地放到各個內存塊中。
例子，頁面大小4KB，每個頁表項4B，每個頁面可存放1K個頁表項，因此每1K個連續的頁表項為一組，每組剛好占一個內存塊，再講各組離散地放到各個內存塊中！
另外，為離散分配的頁表再建立一張頁表，稱為頁目錄表，或稱外層頁表，或稱頂層頁表
實現地址轉換
例子
細節
- 若采用多級頁表機制，則各級頁表的大小不能超過一個頁面。
- 兩級頁表的訪存次數分析（假設沒有快表機構）
- 第一次訪存：訪問內存中的頁目錄表
- 第二次訪存：訪問內存中的二級頁表
- 第三次訪存：訪問目標內存單元
例子
基本分段是存儲管理
大綱
什么是分段
分段：進程的地址空間會按照自身的邏輯關系劃分為若干個段, 每個段都有一個段名, 每段從0開始編址。
內存分配規則：以段為單位進行分配，每個段在內存中占據連續空間，但各段之間可以不相鄰。
分段系統的邏輯地址結構由段號（段名）和段內地址（段內偏移量〉所組成。
段號的位數決定了每個進程最多可以分為幾個段
段內地址位數決定了每個段的最大長度是多少
什么是段表
段表：程序分多個段，各段離散地裝入內存，為了保證程序能正常運行，就必須能從物理內存中找到各個邏輯段的存放位置。為此，需為每個進程建立一張段映射表。
例如：某系統按字節尋址，采用分段存儲管理，邏輯地址結構為（段號16位,段內地址16位），因此用16位即可表示最大段長。物理內存（即基址范圍）大小為4GB（可用32位表示整個物理內存地址空間)。
因此，可以讓每個段表項占16+32=48位，即6B。
由于段表項長度相同，因此段號可以是隱含的，不占存儲空間。
若段表存放的起始地址為M，則K號段對應的段表項存放的地址為 M ＋ K * 6（即段號時隱含的！）
如何實現地址轉換
分段分頁管理對比
- 頁是信息的物理單位。分頁的主要目的是為了實現離散分配，提高內存利用率（沒有頁內碎片）。分頁僅僅是系統管理上的需要，完全是系統行為，對用戶是不可見的。
- 段是信息的邏輯單位。分段的主要目的是更好地滿足用戶需求（便于編程）。一個段通常包含著一組屬于一個邏輯模塊的信息。分段對用戶是可見的，用戶編程時需要顯式地給出段名。
- 頁的大小固定且由系統決定。段的長度卻不固定，決定于用戶編寫的程序。
- 分頁的用戶進程地址空間是一維的，程序員只需給出一個記憶符（邏輯地址）即可表示一個地址。（各頁相鄰）
- 分段的用戶進程地址空間是二維的，程序員在標識一個地址時，既要給出段名，也要給出段內地址。（各段間不相鄰）
- 出現的原因：分頁主要用于實現虛擬內存，從而獲得更大的地址空間；分段主要是為了使程序和數據可以被劃分為邏輯上獨立的地址空間并且有助于共享和保護。
分段比分頁更容易實現信息的共享和保護。（類似指針，二者短表項一致即可同時指向共享內存）
不能被修改的代碼稱為純代碼或可重入代碼(不屬于臨界資源)，這樣的代碼是可以共享的.可修改的代碼是不能共享的(比如，有一個代碼段中有很多變量，各進程并發地同時訪問可能造成數據不一致)
簡單來說：
- 分頁的每頁大小是固定的，共享的數據不一定會被分到一個頁，就會導致共享的和不允許共享的在一個頁中出現！
- 分段的每段大小是不定的，共享的數據完全可以被特殊處理到一個段，不會發生問題！
訪問一個邏輯地址需要幾次訪存?
- 分頁（單級頁表)：第一次訪存――查內存中的頁表，第二次訪存――訪問目標內存單元?？偣矁纱卧L存
- 分段：第一次訪存――查內存中的段表，第二次訪存――訪問目標內存單元。總共兩次訪存
- 與分頁系統類似，分段系統中也可以引入快表機構，將近期訪問過的段表項放到快表中，這樣可以少一次訪問，加快地址變換速度。
段頁式存儲管理
大綱
分頁分段管理方式優缺點
分段管理中產生的外部碎片也可以用“緊湊”來解決，只是需要付出較大的時間代價
分頁 + 分段 = 段頁式管理
將進程按邏輯模塊分段，再將各段分頁（如每個頁面4KB)
再將內存空間分為大小相同的內存塊/頁框/頁幀/物理塊
進程前將各頁面分別裝入各內存塊中
段頁式邏輯地址結構
由段號、頁號、頁內地址（頁內偏移量）組成！
分段系統的端內地址拆分為：頁號 + 頁內偏移
- 段號的位數決定了每個進程最多可以分幾個段
- 頁號位數決定了每個段最大有多少頁
- 頁內偏移量決定了頁面大小、內存塊大小是多少
" 分段 " 對用戶是可見的，而將各段"分頁"對用戶是不可見的，系統會根據段內地址自動劃分頁號和段內偏移量，因此段頁式管理的地址結構是 " 二維 " 的。
段表頁表
每一個進程對應一個段表，每一個段又對應一個頁表，因此一個進程可能對應多個頁表。
每個段對應一個段表項，每個段表項由段號、頁表長度、頁表存放塊號(頁表起始地址）組成。
每個段表項長度相等，段號是隱含的。
每個頁面對應一個頁表項，每個頁表項由頁號、內存存放的內存塊號組成。
每個頁表項長度相等，頁號是隱含的。
如何實現地址轉換
1、由邏輯地址得到段號、頁號、頁內偏移
2、段號與段表寄存器的段長度比較，檢查是否越界
3、由段表始址, 段號找到對應段表項
4、根據段表中記錄的頁表長度，檢查頁號是否越界
5、由段表中的頁表地址, 頁號得到查詢頁表，找到相應頁表項
6、由頁面存放的內存塊號，頁內偏移得到最終的物理地址
7、訪問目標單元
需要三次訪存，第一次查段表，第二次查頁表，第三次訪問目標單元。
四、文件管理
1、文件管理簡介
大綱
文件的屬性
文件名、標識符、類型、位置、大小、創建時間、上次修改時間、文件所有者信息、保護信息
文件的分類
-
無結構文件（流式文件）：文件內部的數據是由一系列的二進制或字符流組成，如文本文件（.txt文件）
-
有結構文件（記錄式文件）：由一組相似的記錄文件組成，每條記錄又由若干個數據項組成，如數據庫表。一般來說，每條記錄有一個數據項作為關鍵字。根據各條記錄的長度（占用的存儲空間）是否相等，又可分為定長記錄和可變長記錄。
記錄是一組相關數據項的集合
操作系統應向上提供哪些功能
create、delete、open、close、read、write 等系統調用功能！
2、文件的邏輯結構
文件邏輯結構
- 無結構文件（流式文件）：文件內部的數據是由一系列的二進制或字符流組成，如文本文件（.txt文件）
- 有結構文件（記錄式文件）：由一組相似的記錄文件組成，每條記錄又由若干個數據項組成，如數據庫表。一般來說，每條記錄有一個數據項作為關鍵字。根據各條記錄的長度（占用的存儲空間）是否相等，又可分為定長記錄和可變長記錄。
- 順序文件
- 索引文件
- 順序索引文件
邏輯結構：指在用戶看來，文件內部的數據應該是如何組織起來的。
物理結構：指的是在操作系統看來，文件的數據是如何存放在外存的。
大綱
順序文件
順序文件：文件中的記錄一個接一個地順序排列（邏輯上），記錄可以是定長的或可變長的。各個記錄在物理上可以順序存儲（物理上連續）或鏈式存儲（物理上可能不連續）。
- 串結構：記錄之間的順序與關鍵字無關（通常按照記錄存入的時間決定記錄的順序）
- 順序結構：記錄之間的順序按關鍵字順序排列
順序文件（順序結構）的缺點是增加/刪除一個記錄比較困難（如果是串結構則相對簡單）
索引文件
解決可變長記錄的快速查找問題！
索引表本身是定長記錄的順序文件。因此可以快速找到第i個記錄對應的索引項。
可將關鍵字作為索引號內容，若按關鍵字順序排列，則還可以支持按照關鍵字折半查找。
每當要增加/刪除一個記錄時，需要對索引表進行修改。由于索引文件有很快的檢索速度，因此主要用于對信息處理的及時性要求比較高的場合。
另外，可以用不同的數據項建立多個索引表。如:學生信息表中，可用關鍵字“學號”建立一張索引表。也可用“姓名”建立一張索引表。這樣就可以根據“姓名”快速地檢索文件了。
順序索引文件
索引文件的缺點：每個記錄對應一個索引表項，因此索引表可能會很大。比如：文件的每個記錄平均只占8B，而每個索引表項占32個字節，那么索引表都要比文件內容本身大4倍，這樣對存儲空間的利用率就太低了。
索引順序文件是索引文件和順序文件思想的結合。索引順序文件中，同樣會為文件建立一張索引表，但不同的是：并不是每個記錄對應一個索引表項，而是一組記錄對應一個索引表項。
若一個順序文件有10000個記錄，則根據關鍵字檢索文件，只能從頭開始順序查找（這里指的并不是定長貢錄、順序結構的順序文件），平均須查找5000個記錄。
若采用索引順序文件結構，可把10000個記錄分為100 組，每組100個記錄。則需要先順序查找索引表找到分組（共100個分組，因此索引表長度為100，平均需要查50次），找到分組后，再在分組中順序查找記錄（每個分組100個記錄，因此平均需要查50次）?？梢?#xff0c;采用索引順序文件結構后，平均查找次數減少為50+50= 100次。
同理，若文件共有1000000個記錄，則可分為1000個分組，每個分組1000個記錄。根據關鍵字檢索一個記錄平均需要查找500+500 = 1000次。這個查找次數依然很多，如何解決呢?
多級索引順序文件
為了進一步提高檢索效率，可以為順序文件建立多級索引表。
套娃即可！ 空間換時間！
3、文件目錄
大綱
文件控制塊
- 目錄本身就是一種有結構文件，由一條條記錄組成。每條記錄對應一個在該目錄下的文件。
- 目錄文件中的一條記錄就是一個文件控制塊（FCB）。
- FCB 實現了文件名和文件之間的映射。使用戶程序可以實現 ” 按名存取 “。
FCB中包含
- 文件的基本信息（ 文件名、物理地址、邏輯地址、物理結構等）
- 存取控制信息（是否可讀/可寫、禁止訪問的用戶名單等）
- 使用信息（如文件的建立時間、修改時間等）
對目錄進行的操作：搜索、創建文件、刪除文件、顯示目錄、修改目錄
目錄結構
單級目錄結構
早期的操作系統并不支持多級目錄，整個系統只建立一張目錄表，每個文件占一個目錄項。
單級目錄實現了 " 按名存取 "，但是不允許文件重名。
單級目錄不支持多用戶操作系統。
兩級目錄結構
早期的多用戶操作系統采用兩級目錄結構，分為主文件目錄 （MFD，Master File Directory）和用戶文件目錄（UFD，User File Directory）。
- 主文件目錄記錄用戶名及相應用戶文件目錄的存放位置
- 用戶文件目錄由該用戶的文件FCB組成
優點：兩級目錄允許不同用戶的文件重名，也可以在目錄上實現訪問限制（檢查此時登錄的用戶名是否匹配）。
缺點：缺乏靈活性，用戶不能對自己的文件進行分類。
多級目錄結構
又稱樹形目錄結構
用戶(或用戶進程）要訪問某個文件時要用文件路徑名標識文件，文件路徑名是個字符串。各級目錄之間用“/”隔開。從根目錄出發的路徑稱為絕對路徑。
從當前目錄出發的路徑稱為相對路徑。
系統根據絕對路徑一層一層地找到下一級目錄。剛開始從外存讀入根目錄的目錄表；找到“照片”目錄的存放位置后，從外存讀入對應的目錄表；再找到“2015-08”目錄的存放位置，再從外存讀入對應目錄表；最后才找到文件“白拍.jpg”的存放位置。整個過程需要3次讀磁盤I/O操作。
相對路徑可以減少磁盤 I/O 操作次數。
優點：樹形目錄結構可以很方便地對文件進行分類，層次結構清晰，也能夠更有效地進行文件的管理和保護。
缺點：樹形結構不便于實現文件的共享。
對此，提出了“ 無環圖目錄結構 ”。
無環圖目錄結構
在樹形目錄結構的基礎上，增加一些指向同一節點的有向邊，使整個目錄成為一個有向無環圖。
可以更方便地實現多個用戶間的文件共享。
可以用不同的文件名指向同一個文件，甚至可以指向同一個目錄（共享同一目錄下的所有內容）。
需要為每個共享結點設置一個共享計數器，用于記錄此時有多少個地方在共享該結點。用戶提出刪除結點的請求時，只是刪除該用戶的FCB、并使共享計數器減1，并不會直接刪除共享結點。減到0時，才能刪除該節點！
索引節點
對FCB的改進！
由來：其實在查找各級目錄的過程中只需要用到“文件名”這個信息，只有文件名匹配時，才需要讀出文件的其他信息。因此可以考慮讓目錄表“瘦身”來提升效率。
將除了文件名之外的文件描述信息都放到索引結點中。由于目錄項長度減小，因此每個磁盤塊可以存放更多各目錄項，可以大大提升文件檢索速度。
當找到文件名對應的目錄項時，才需要將索引結點調入內存，索引結點中記錄了文件的各種信息，包括文件在外存中的存放位置，根據“ 存放位置 ”即可找到文件。
存放在外存中的索引結點稱為“磁盤索引結點”，當索引結點放入內存后稱為“內存索引結點”。
相比之下內存索引結點中需要增加一些信息，比如：文件是否被修改、此時有幾個進程正在訪問該文件等。
4、文件的物理結構（非空閑塊）
文件物理結構（文件）分配方式
即文件數據應該怎樣存放在外存中。
是對非空閑塊的管理！
文件塊和磁盤塊
磁盤塊
類似于內存分頁，磁盤中的存儲單元也會被分為一個個 ” 塊 / 磁盤塊 / 物理塊 “。
很多操作系統中，磁盤塊的大小與內存塊、頁面的大小相同。
內存與磁盤之間的數據交換（即 讀/寫操作、磁盤I/O）都是以” 塊 “ 為單位進行的。
即每次讀入一塊，或每次寫出一塊
文件塊
在內存管理中, 進程的邏輯地址空間被分為一個個的頁面
同樣的, 在外存管理中, 為了方便對文件數據的管理, 文件的邏輯地址空間也被分為了一個個的文件塊
于是文件的邏輯地址也可以表示為 **（邏輯塊號, 塊內地址）**的形式
連續分配
連續分配方式要求每個文件在磁盤上占有一組連續的塊。
用戶給出要訪問的邏輯塊號，操作系統找到該文件對應的目錄項（FCB） …
物理塊號 = 起始塊號＋ 邏輯塊號（就是偏移）
當然，還需要檢查用戶提供的邏輯塊號是否合法（邏輯塊號≥長度就不合法)
操作系統可以直接算出邏輯塊號對應的物理塊號，因此連續分配支持順序訪問和直接訪問( 隨機訪問 )
連續分配方式要求每個文件在磁盤上占有一組連續的塊。
讀取某個磁盤塊時，需要移動磁頭。訪問的兩個磁盤塊相隔越遠，移動磁頭所需時間就越長。
優點：連續分配的文件在順序讀/寫時速度最快。
缺點：采用連續分配的文件不方便拓展；存儲利用率低，會產生難以利用的磁盤碎片。( 類似外部碎片，可以采用緊湊的方法來處理碎片, 但是需要耗費很大的時間代價 )
鏈接分配
鏈接分配采取離散分配的方式，可以為文件分配離散的磁盤塊。
- 隱式鏈接
- 顯示鏈接
隱式鏈接
隱式鏈接：除文件的最后一個盤塊之外，每個盤塊中都存有指向下一個盤塊的指針。文件目錄包括文件第一塊的指針和最后一塊的指針。
實現文件的邏輯塊號到物理塊號的轉變
用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB） …
從目錄項中找到起始塊號（即0號塊），將0號邏輯塊讀入內存，由此知道1號邏輯塊存放的物理塊號，于是讀入1號邏輯塊，再找到2號邏輯塊的存放位置…
以此類推。
因此，讀入i號邏輯塊，總共需要i+1次磁盤I/O。
優點：很方便文件拓展 （掛到文件鏈尾即可，可通過結束塊號找到尾）；所有的空閑磁盤塊都可以被利用，不會有碎片問題，外存利用率高。
缺點：只支持順序訪問，不支持隨機訪問，查找效率低，指向下一個盤塊的指針也需要耗費少量的存儲空間。
顯式鏈接
顯示鏈接：把用于鏈接文件各物理塊的指針顯式地存放在一張表中。即文件分配表（FAT，File Allocation Table）。
- 一個磁盤僅設置一張 FAT。
- 開機時，將 FAT 讀入內存，并常駐內存。
- FAT 的各個表項在物理上連續存儲，且每一個表項長度相同，因此 ”物理塊號“ 字段可以是隱含的。
實現文件的邏輯塊號到物理塊號的轉變
- 用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項(FCB）
- 從目錄項中找到起始塊號，若i > 0，則查詢內存中的文件分配表FAT，往后找到i號邏輯塊對應的物理塊號。 邏輯塊號轉換成物理塊號的過程不需要讀磁盤操作。（FAT常駐內存）
結論：
- 采用顯式鏈接方式的文件，支持順序訪問，也支持隨機訪問（想訪問i號邏輯塊時，并不需要依次訪問之前的0~ i-1號邏輯塊)。
- 由于塊號轉換的過程不需要訪問磁盤，因此相比于隱式鏈接來說，訪問速度快很多。
- 顯式鏈接也不會產生外部碎片，也可以很方便地對文件進行拓展
優點：很方便文件拓展，不會有碎片問題，外存利用率高，并且支持隨機訪問。相比于隱式鏈接來說，地址轉換時不需要訪問磁盤，因此文件的訪問效率更高。
缺點：文件分配表的需要占用一定的存儲空間。
索引分配
簡介
索引分配允許文件離散地分配在各個磁盤塊中，系統會為每個文件建立一張索引表，索引表中記錄了文件的各個邏輯塊對應的物理塊（索引表的功能類似于內存管理中的頁表一―建立邏輯頁面到物理頁之間的映射關系）。索引表存放的磁盤塊稱為索引塊。文件數據存放的磁盤塊稱為數據塊。
假設某個新創建的文件“aaa”的數據依次存放在磁盤塊2 -> 5 -> 13 -> 9 。7號磁盤塊作為“aaa”的索引塊,索引塊中保存了索引表的內容。
注：在顯式鏈接的鏈式分配方式中，文件分配表FAT是一個磁盤對應一張。而索引分配方式中，索引表是一個文件對應一張。
可以用固定的長度表示物理塊號（如：假設磁盤總容量為1TB=2^40B，磁盤塊大小為1KB，則共有 2^30 個磁盤塊，則可用4B表示磁盤塊號)，因此，索引表中的“邏輯塊號”可以是隱含的。
實現文件的邏輯塊號到物理塊號的轉變？
-
用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB）
-
從目錄項中可知索引表存放位置，將索引表從外存讀入內存，并查找索引表即可知道 i 號邏輯塊在外存中的存放位置。
可見，索引分配方式可以支持隨機訪問。文件拓展也很容易實現（只需要給文件分配一個空閑塊，并增加一個索引表項即可）。
問題解決
若每個磁盤塊1KB，一個索引表項4B，則一個磁盤塊只能存放256個索引項。
如果一個文件的大小超過了256塊，那么一個磁盤塊是裝不下文件的整張索引表的，如何解決這個問題?
- 鏈接方案
- 多層索引
- 混合索引
鏈接方案
如果索引表太大，一個索引塊裝不下，那么可以將多個索引塊鏈接起來存放。
多層索引
建立多層索引（原理類似于多級頁表）。使第一層索引塊指向第二層的索引塊。還可根據文件大小的要求再建立第三層、第四層索引塊。
混合索引
解決多層索引對于小文件仍需要多層處理的問題！
多種索引分配方式的結合。
例如，一個文件的頂級索引表中，既包含直接地址索引(直接指向數據塊），又包含一級間接索引（指向單層索引表)、還包含兩級間接索引（指向兩層索引表)。
小總結
- 鏈接方案：如果索引表太大，一個索引塊裝不下，那么可以將多個索引塊鏈接起來存放。
- 缺點：若文件很大，索引表很長，就需要將很多個索引塊鏈接起來。想要找到i號索引塊，必須先依次讀入0 ~ i-1號索引塊，這就導致磁盤l/O次數過多，查找效率低下。
- 多層索引：建立多層索引（原理類似于多級頁表)。使第一層索引塊指向第二層的索引塊。還可根據文件大小的要求再建立第三層、第四層索引塊。采用K層索引結構，且頂級索引表未調入內存，則訪問一個數據塊只需要K +1次讀磁盤操作。
- 缺點：即使是小文件，訪問一個數據塊依然需要K+1次讀磁盤。
- 混合索引：多種索引分配方式的結合。例如，一個文件的頂級索引表中，既包含直接地址索引（直接指向數據塊），又包含一級間接索引（指向單層索引表)、還包含兩級間接索引（指向兩層索引表)。
- 優點：對于小文件來說，訪問一個數據塊所需的讀磁盤次數更少。
重點：
- 要會根據多層索引、混合索引的結構計算出文件的最大長度(Key：各級索引表最大不能超過一個塊)﹔
- 要能自己分析訪問某個數據塊所需要的讀磁盤次數（Key: FCB中會存有指向頂級索引塊的指針，因此可以根據FCB讀入頂級索引塊。每次讀入下一級的索引塊都需要一次讀磁盤操作。另外，要注意題目條件――頂級索引塊是否已調入內存)
5、文件存儲空間管理（空閑塊）
對空閑塊的管理！
大綱
存儲空間劃分與初始化
文件卷：將物理磁盤劃分為一個個文件卷（邏輯卷，邏輯盤）例如：windows CDE盤
- 目錄區：主要存放文件目錄信息(FCB)，用于磁盤存儲空間管理的信息
- 文件區：存放文件數據
空閑表法
適用于連續分配方式。
空閑鏈表法
空閑鏈表法
- 空閑盤塊鏈：以盤塊為單位組成一條空閑鏈
- 空閑盤區鏈：以盤區為單位組成一條空閑鏈
空閑盤塊鏈
適用于離散分配的物理結構。
空閑盤區鏈
以盤區為單位組成一條空閑鏈
離散分配、連續分配都使用。
為一個文件分配多個盤塊時效率更高
位示圖法
位示圖：每個二進制位對應一個盤塊。在本例中，“O”代表盤塊空閑，“1”代表盤塊已分配。
如何分配
若文件需要K個塊
- 順序掃描位示圖，找到K個相鄰或不相鄰的“0”；
- 根據字號、位號算出對應的盤塊號，將相應盤塊分配給文件；
- 將相應位設置為“1”。
如何回收
- 根據回收的盤塊號計算出對應的字號、位號；
- 將相應二進制位設為“ 0 ”。
成組鏈表法
空閑表法、空閑鏈表法不適用于大型文件系統，因為空閑表或空閑鏈表可能過大。
UNIX 系統中采用了成組鏈接法對磁盤空閑塊進行管理。
文件卷的目錄區中專門用一個磁盤塊作為 “超級塊”，當系統啟動時需要將超級塊讀入內存。
并且要保證內存與外存中的 “超級塊” 數據一致。
成組鏈表法詳講：https://blog.csdn.net/Ajay666/article/details/73569654
6、文件基本操作
創建文件
進行 " create 系統調用 "
需要提供的參數：
- 所需的外存空間大小（如：一個盤塊，即1KB)
- 文件存放路徑（“D:/Demo”）
- 文件名（這個地方默認為“新建文本文檔.txt”)
操作系統在處理create系統調用時，主要做了兩件事：
- 在外存中找到文件所需的空間（例如使用空閑鏈表法、位示圖等管理策略，找到空閑空間）
- 根據文件的存放路徑的信息找到該目錄對應的目錄文件，在目錄中創建該文件對應的目錄項 。目錄項中包含了文件名，文件在外存中的存放位置等信息。
刪除文件
進行 " delete 系統調用 "
需要提供的參數：
- 文件存放路徑（“ D:/Demo ”)
- 文件名 (“ test.txt ”)
操作系統在處理delete系統調用時，主要做了幾件事：
- 根據文件存放路徑找到相應的目錄文件，從目錄中找到文件名對應的目錄項。
- 根據該目錄項記錄的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盤塊。(回收磁盤塊時，根據空閑表法、空閑鏈表法、位圖法等管理策略的不同，需要做不同的處理)
- 從目錄表中刪除文件對應的目錄項。
打開文件
進行 ” open 系統調用 “
需要提供的要參數：
- 文件存放路徑 (“D:/Demo”)
- 文件名 (“test.txt”)
- 要對文件的操作類型（如：r只讀；rw讀寫等)
操作系統在處理delete系統調用時，主要做了幾件事：
- 根據文件存放路徑找到相應的目錄文件，從目錄中找到文件名對應的的目錄項，并檢查該用戶是否有指定的操作權限。
- 將目錄項復制到內存中的“打開文件表”中。并將對應表目的編號返回給用戶。之后用戶使用打開文件表的編號來指明要操作的文件。
打開文件表
每個進程有自己的打開文件表，系統中也有一張總的打開文件表
- 打開計數器：記錄此時有多少個進程打開了此文件。
- 讀寫指針：記錄該進程對文件的讀/寫操作進行到的位置。
- 訪問權限：如果打開文件時聲明的是 ” 只讀 “，則該進程不能對文件進行寫操作。
關閉文件
進行 ” close 系統調用 “
- 將進程的打開文件表相應表項刪除。
- 回收分配給該文件的內存空間等資源。
- 系統打開文件表的打開計數器 count 減1，若count = 0，則刪除對應表項。
讀文件
進行 ” read 系統調用 “
需要提供的參數
- 需要指明是哪個文件（在支持“打開文件”操作的系統中，只需要提供文件在打開文件表中的索引號即可）
- 還需要指明要讀入多少數據（如：讀入1KB）
- 指明讀入的數據要放在內存中的什么位置。
操作系統在處理read系統調用時，會從讀指針指向的外存中，將用戶指定大小的數據讀入用戶指定的內存區域中。
寫文件
進行 ” write 系統調用 “
需要提供的參數
- 需要指明是哪個文件（在支持“打開文件”操作的系統中，只需要提供文件在打開文件表中的索引號即可）
- 還需要指明要寫出多少數據（如：寫出1KB）
- 寫回外存的數據放在內存中的什么位置
7、文件共享&文件保護
文件共享
基于索引結點的共享方式（硬鏈接）
索引結點：是一種文件目錄瘦身策略。由于檢索文件時只需用到文件名，因此可以將除了文件名之外的其他信息放到索引結點中。這樣目錄項就只需要包含文件名、索引結點指針。
索引結點中設置一個鏈接計數變量count，用于表示鏈接到本索引結點上的用戶目錄項數。
若 count =2，說明此時有兩個用戶目錄項鏈接到該索引結點上，或者說是有兩個用戶在共享此文件。
若某個用戶決定“ 刪除 ”該文件，則只是要把用戶目錄中與該文件對應的目錄項刪除，且索引結點的 count 值減1。
若 count > 0，說明還有別的用戶要使用該文件，暫時不能把文件數據刪除，否則會導致指針懸空。
當 count = 0 時系統負責刪除文件。
基于符號鏈的共享方式（軟鏈接）
當 User3 訪問 “ ccc ” 時，操作系統判斷文件 “ ccc ” 屬于 Link 類型文件，于是會根據其中記錄的層層查找目錄，最終找到 User1的目錄表中的 “ aaa ” 表項，于是就找到了文件1的索引結點。（類似Windows快捷方式）
速度慢于硬鏈接！
文件保護
口令保護
為文件設置一個 “ 口令 ” （如: abc112233），用戶請求訪問該文件時必須提供 “ 口令 ”。
口令一般存放在文件對應的 FCB 或索引結點中。
用戶訪問文件前需要先輸入“口令”，操作系統會將用戶提供的口令與FCB中存儲的口令進行對比。
如果正確，則允許該用戶訪問文件。
優點：保存口令的空間開銷不多，驗證口令的時間開銷也很小。
缺點：正確的 “口令” 存放在系統內部，不夠安全。
加密保護
使用某個 “ 密碼 ” 對文件進行加密，在訪問文件時需要提供正確的 “ 密碼 ” 才能對文件進行正確的解密。
優點：保密性強，不需要在系統中存儲“密碼”
缺點：編碼/譯碼，或者說加密/解密要花費一定時間。
訪問控制
在每個文件的 FCB （或索引結點）中增加一個訪問控制列表（Access-Control List, ACL)，該表中記錄了各個用戶可以對該文件執行哪些操作。
8、文件系統層次結構
從上到下依次是：文件基本操作，文件目錄，文件保護，文件邏輯地址，文件物理地址，文件存儲空間管理，磁盤設備管理！
用一個例子來輔助記憶文件系統的層次結構：
假設某用戶請求刪除文件“D:/工作目錄/學生信息…xlsx”的最后100條記錄。
五、磁盤管理
1、磁盤結構
磁盤&磁道&扇區
磁盤：表面由一些磁性物質組成，可以用這些磁性物質來記錄二進制數據。
磁道 : 磁盤的盤面被劃分成一個個磁道， 一個圈就是一個磁道。
扇區 : 每一個磁道被劃分成一個個扇區，每個扇區就是一個個 " 數據塊 "，各個扇區存放的數據量相同。
最內側磁道上的扇區面積最小, 因此數據密度最大
磁盤如何讀寫
需要把 “ 磁頭 ” 移動到想要讀/寫的扇區所在的磁道。
磁盤會轉起來，讓目標扇區從磁頭下面劃過，才能完成對扇區的讀/寫操作。
盤面&柱面
磁盤物理地址
可用（柱面號，盤面號，扇區號）來定位任意一個“磁盤塊”。"在“文件的物理結構”小節中，我們經常提到文件數據存放在外存中的幾號塊，這個塊號就可以轉換成（柱面號，盤面號，扇區號)的地址形式。
可根據該地址讀取一個“塊”
- 根據“柱面號”移動磁臂，讓磁頭指向指定柱面;
- 激活指定盤面對應的磁頭;
- 磁盤旋轉的過程中，指定的扇區會從磁頭下面劃過，這樣就完成了對指定扇區的讀/寫。
磁盤分類
磁頭可以移動的稱為活動頭磁盤。磁臂可以來回伸縮來帶動磁頭定位磁道。
磁頭不可移動的稱為固定頭磁盤。這種磁盤中每個磁道有一個磁頭。
盤片可以更換的稱為可換盤磁盤。
盤片不可以更換的稱為固定盤磁盤。
2、磁盤調度算法
尋道時間&延遲時間&傳輸時間
尋找時間(尋道時間)Ts：在讀/寫數據前，將磁頭移動到指定磁道所花的時間。
- 啟動磁頭臂是需要時間的。假設耗時為s;
- 移動磁頭也是需要時間的。假設磁頭勻速移動，每跨越一個磁道耗時為m，總共需要跨越n條磁道。則尋道時間 Ts = s + m * n
延退睦潮Tr：通過旋轉磁盤，使磁頭定位到目標扇區所需要的時間。設磁盤轉速為r(單位:轉/秒，或轉/分），則平均所需的延遲時間Tr =(1/2) * (1/r) = 1/2r
傳輸時間Tt：從磁盤讀出或向磁盤寫入數據所經歷的時間，假設磁盤轉速為r，此次讀/寫的字節數為b，每個磁道上的字節數為N。則:傳輸時間Tt=(1/r) * (b/N) = b/(rN)
總的平均存取時間T = Ts + 1/2r + b/(rN)
延遲時間和傳輸時間都與磁盤轉速相關，且為線性相關。而轉速是硬件的固有屬性，因此操作系統也無法優化延遲時間和傳輸時間！
但是操作系統的磁盤調度算法會直接影響尋道時間
先來先服務FCFS
根據進程請求訪問磁盤的先后順序進行調度。
優點：公平；如果請求訪問的磁道比較集中的話，算法性能還算過得去。
缺點：如果有大量進程競爭使用磁盤，請求訪問的磁道很分散，則FCFS在性能上很差，尋道時間長。
最短尋道時間優先SSTF
SSTF 算法會優先處理的磁道是與當前磁頭最近的磁道?？梢员ＷC每次的尋道時間最短，但是并不能保證總的尋道時間最短。(其實就是貪心算法的思想，只是選擇眼前最優，但是總體未必最優）
優點：性能較好，平均尋道時間短。
缺點：可能產生 “ 饑餓 ” 現象。
產生饑餓的原因在于：磁頭在一個小區域內來回來去地移動。
掃描算法SCAN
為了防止饑餓問題，可以規定，只有磁頭移動到最外側磁道的時候才能往內移動，移動到最內側磁道的時候才能往外移動。
這就是掃描算法（SCAN）的思想。由于磁頭移動的方式很像電梯，因此也叫電梯算法。
優點：性能較好，平均尋道時間較短，不會產生饑餓現象
缺點：
- 只有到達最邊上的磁道時才能改變磁頭移動方向
- SCAN算法對于各個位置磁道的響應頻率不平均
LOOK 調度算法
相對于掃描算法，如果在磁頭移動方向上已經沒有別的請求，就可以立即改變磁頭移動方向。
邊移動邊觀察，因此叫 LOOK。
優點：比起SCAN算法來，不需要每次都移動到最外側或最內側才改變磁頭方向，使尋道時間進一步縮短。
循環掃描算法C-SCAN
SCAN算法對于各個位置磁道的響應頻率不平均，而C-SCAN算法就是為了解決這個問題。
規定只有磁頭朝某個特定方向移動時才處理磁道訪問請求，而返回時直接快速移動至起始端而不處理任何請求。
優點：比起SCAN來，對于各個位置磁道的響應頻率很平均。
缺點：只有到達最邊上的磁道時才能改變磁頭移動方向，事實上，處理了184號磁道的訪問請求之后就不需要再往右移動磁頭了;并且，磁頭返回時其實只需要返回到18號磁道即可，不需要返回到最邊緣的磁道。另外，比起SCAN算法來，平均尋道時間更長。
C-LOOK 調度算法
C-SCAN 算法的主要缺點是只有到達最邊上的磁道時才能改變磁頭移動方向，并且磁頭返回時不一定需要返回到最邊緣的磁道上。
C-LOOK算法就是為了解決這個問題。如果磁頭移動的方向上已經沒有磁道訪問請求了，就可以立即讓磁頭返回，并且磁頭只需要返回到有磁道訪問請求的位置即可。
優點：比起C-SCAN算法來，不需要每次都移動到最外側或最內側才改變磁頭方向，使尋道時間進一步縮短。
3、減少磁盤延遲方法
磁頭讀入一個扇區數據后需要一小段時間處理，如果邏輯上相鄰的扇區在物理上也相鄰，
則讀入幾個連續的邏輯扇區，可能需要很長的“延遲時間”（因為扇片在不停的旋轉，寫一次轉到是才可能繼續去讀）
交替編號
若采用交替編號的策略，即讓邏輯上相鄰的扇區在物理上有一定的間隔，可以使讀取連續的邏輯扇區所需要的延遲時間更小。
磁盤地址結構的設計
磁盤的物理地址是 （柱面號、盤面號、扇區號）
為什么不是 （盤面號、柱面號、扇區號）？
在讀取地址連續的磁盤塊時，可以減少磁頭移動消耗的時間。
- 同一個柱面無需移動多次磁頭
- 若盤面號在前，則柱面號可能會變，就會造成多次移動磁頭
- 移動磁頭開銷太大
錯位命名
讓相鄰盤面的扇區編號 “錯位”。
即將多個盤面的磁頭指向的扇區編號并不一致即可！
若指向的扇區編號一致：則0號扇面讀完要讀1號扇面時，1號扇面的磁頭仍需要時間激活，因此就會將需要讀的扇區錯過，進行轉動第二圈才能讀到
若指向的扇區編號不一致：1號扇面磁頭開始讀時，由于編號不一致，即此時磁頭的指向并不是要讀的數據，完全有時間激活磁頭，激活完畢順便將需要讀的扇區讀了，轉一圈即可完成！減少延遲時間！
4、磁盤的管理
磁盤初始化
引導塊
計算機開機時需要進行一系列初始化的工作，
這些初始化工作是通過執行初始化程序 (自舉程序) 完成的。
初始化程序 ( 自舉程序 ) 如果直接放在ROM（只讀存儲器）中。ROM中的數據在出廠時就寫入了。并且以后不能再修改，會很不方便。
解決方法：
- 完整的自舉程序放在磁盤的啟動塊(即引導塊/啟動分區）上，啟動塊位于磁盤的固定位置。
- ROM中只存放很小的 “ 自舉裝入程序 ”。
- 開機時計算機先運行 “ 自舉裝入程序 ”，通過執行該程序就可找到引導塊，并將完整的 “ 自舉程序 ” 讀入內存，完成初始化。
- 擁有啟動分區的磁盤稱為啟動磁盤或系統磁盤（C盤）
壞塊管理
壞了、無法正常使用的扇區就是“壞塊”。
這屬于硬件故障，操作系統是無法修復的。應該將壞塊標記出來，以免錯誤地使用到它。
對于簡單的磁盤，可以在邏輯格式化時（建立文件系統時）對整個磁盤進行壞塊檢查，
標明哪些扇區是壞扇區，比如：在FAT表上標明。（在這種方式中，壞塊對操作系統不透明)
對于復雜的磁盤，磁盤控制器（磁盤設備內部的一個硬件部件）會維護一個壞塊鏈表。
在磁盤出廠前進行低級格式化（物理格式化）時就將壞塊鏈進行初始化。
會保留一些“備用扇區”，用于替換壞塊。
這種方案稱為扇區備用。且這種處理方式中，壞塊對操作系統透明。
六、設備管理
1、IO設備概念&分類
概念
“ I/O ” 就是“ 輸入/輸出 ”（lnput/Output）
I/O 設備就是可以將數據輸入到計算機，或者可以接收計算機輸出數據的外部設備，屬于計算機中的硬件部件。
UNIX系統將外部設備抽象為一種特殊的文件， 用戶可以使用與文件操作相同的方式對外部設備進行操作。
Write：向外部設備寫出數據。
Read：向外部設備讀入數據。
分類
按使用特性
- 人機交互類外設：鼠標、鍵盤、打印機等?！?用于人機交互 —— 數據傳輸速度慢
- 存儲設備：移動硬盤、光盤等。 —— 用于數據存儲 —— 數據傳輸速度快
- 網絡通信設備：調制解調器等。 —— 用于網絡通信 —— 數據傳輸速度介于上面兩者之間
按傳輸速率
- 低速設備：鼠標、鍵盤等 —— 傳輸速率為每秒幾個到幾百字節。
- 中速設備：如激光打印機等 —— 傳輸速率為每秒數千至上萬個字節。
- 高速設備：如磁盤等 —— 傳輸速率為每秒數千字至千兆字節。
按信息交換的單位
- 塊設備：如磁盤等 ―― 數據傳輸的基本單位是 “ 塊” ?！?傳輸速率較高，可尋址，即對它可隨機地讀/寫任一塊。
- 字符設備：鼠標、鍵盤等 ―― 數據傳輸的基本單位是字符?！?傳輸速率較慢，不可尋址，在輸入/輸出時常采用中斷驅動方式。
2、IO控制器
用于實現對IO設備的控制！
機械部件 vs 電子部件
IO設備有機械部件和電子部件組成！
l/O 設備的機械部件主要用來執行具體 l/O 操作。
如我們看得見摸得著的鼠標/鍵盤的按鈕；顯示器的LED屏；移動硬盤的磁臂、磁盤盤面。
l/O 設備的電子部件通常是一塊插入主板擴充槽的印刷電路板。
CPU 無法直接控制 I/O 設備的機械部件，因此 I/O 設備還要有一個電子部件作為 CPU 和 I/O 設備機械部分之間的 “中介”, 用于實現CPU對設備的控制。
這個電子部件就是 I/O 控制器，又稱設備控制器。
CPU可控制 I/O 控制器，又由 I/O 控制器來控制設備的機械部件。
I/O 控制器的功能
- 接受和識別 CPU 發出的命令：如 CPU 發來的 read/write 命令，I/O 控制器中會有相應的控制寄存器來存放命令和參數。
- 向 CPU 報告設備的狀態：I/O 控制器中會有相應的狀態寄存器，用于記錄 I/O 設備的當前狀態。如：1表示空閑，0表示忙碌。
- 數據交換：I/O 控制器中會設置相應的數據寄存器。
- 輸出時，數據寄存器用于暫存CPU發來的數據，之后再由控制器傳送設備。
- 輸入時，數據寄存器用于暫存設備發來的數據，之后CPU從數據寄存器中取走數據。
- 地址識別：類似于內存的地址，為了區分設備控制器中的各個寄存器，也需要給各個寄存器設置一個特定的“地址”。
- I/O 控制器通過 CPU 提供的 “ 地址 ” 來判斷 CPU 要讀/寫的是哪個寄存器。
I/O 控制器的組成
- CPU與控制器的接口：用于實現 CPU 與控制器之間的通信，CPU 通過控制線發出命令，通過地址線指明要操作的設備，通過數據線來取出輸入數據，或放入輸出數據。
- I/O邏輯：負責接收和識別 CPU 的各種命令, 并負責對設備發出命令。
- 控制器與設備的接口：用于實現控制器與設備之間的通信。
值得注意的小細節：
- 一個 I/O 控制器可能會對應多個設備；
- 數據寄存器、控制寄存器、狀態寄存器可能有多個（如：每個控制/狀態寄存器對應一個具體的設備），且這些寄存器都要有相應的地址，才能方便CPU操作。有的計算機會讓這些寄存器占用內存地址的一部分，稱為內存映像 I/O；另一些計算機則采用 I/O 專用地址，即寄存器獨立編址。
內存印像I/O VS 寄存器獨立編址
3、IO控制方式
即用什么樣的方式來控制 I/O 設備的數據讀/寫
程序直接控制方式
通過 輪詢 實現，以讀操作為例。
數據傳送的單位：每次讀/寫一個字。
CPU千預的頻率
很頻繁，I/O操作開始之前、完成之后需要CPU介入，并且在等待l/O完成的過程中CPU需要不斷地輪詢檢查。
數據的流向：
- 讀操作（數據輸入）：I/O 設備 → CPU（指CPU的寄存器） → 內存
- 寫操作（數據輸出）：內存 → CPU → I/O 設備
每個字的讀/寫都需要CPU的幫助。
優點：實現簡單。在讀/寫指令之后，加上實現循環檢查的一系列指令即可。（因此才稱為“程序直接控制方式”）
缺點：CPU 和 I/O 設備只能I/O串行工作，CPU 需要一直輪詢檢查，長期處于"忙等"狀態，CPU 利用率低。
中斷驅動方式
引入中斷機制。
由于 I/O 設備速度很慢，因此在 CPU 發出讀/寫命令后，可將等待 I/O 的進程阻塞，先切換到別的進程執行。當 I/O 完成后，控制器會向 CPU 發出一個中斷信號，CPU檢測到中斷信號后，會保存當前進程的運行環境信息，轉去執行中斷處理程序處理該中斷。
處理中斷的過程中，CPU從 I/O 控制器讀一個字的數據傳送到 CPU 寄存器，再寫入主存。接著，CPU恢復等待 I/O 的進程（或其他進程）的運行環境，然后繼續執行。
注意：
- CPU 會在每個指令周期的末尾檢查中斷；
- 中斷處理過程中需要保存、恢復進程的運行環境,這個過程是需要一定時間開銷的?？梢?#xff0c;如果中斷發生的頻率太高，也會降低系統性能。
CPU干預的頻率：
每次 I/O 操作開始之前、完成之后需要 CPU 介入。
等待 I/O 完成的過程中 CPU 可以切換到別的進程執行。
數據傳送的單位：每次讀/寫一個字。
數據的流向：
- 讀操作（數據輸入）：I/O 設備 → CPU → 內存
- 寫操作（數據輸出）：內存 → CPU → I/O 設備
優點：與 “ 程序直接控制方式 ” 相比，在“中斷驅動方式”中，I/O 控制器會通過中斷信號主動報告I/O 已完成，CPU不再需要不停地輪詢。CPU 和 I/O 設備可并行工作，CPU利用率得到明顯提升。
缺點：每個字在 I/O 設備與內存之間的傳輸，都需要經過 CPU。而頻繁的中斷處理會消耗較多的CPU時間。
DMA方式
DMA方式（Direct Memory Access，直接存儲器存取）。
主要用于塊設備的 I/O 控制，相對于 “中斷驅動方式 ” 有這樣幾個改進：
- 數據的傳送單位是 “ 塊 ”。不再是一個字、一個字的傳送；
- 數據的流向是從設備直接放入內存，或者從內存直接到設備。不再需要 CPU 作為“快遞小哥”
- 僅在傳送一個或多個數據塊的開始和結束時，才需要CPU干預。
DR (Data Register，數據寄存器)：暫存從設備到內存，或從內存到設備的數據。
MAR (Memory Address Register，內存地址寄存器)：在輸入時，MAR表示數據應放到內存中的什么位置；輸出時MAR表示要輸出的數據放在內存中的什么位置。
DC(Data Counter，數據計數器)：表示剩余要讀/寫的字節數。
CR (Command Register，命令/狀態寄存器)：用于存放 CPU 發來的 I/O 命令，或設備的狀態信息。
CPU干預的頻率：僅在傳送一個或多個數據塊的開始和結束時，才需要CPU干預。
數據傳送的單位：每次讀/寫一個或多個塊
每次讀寫的只能是連續的多個塊，且這些塊讀入內存后在內存中也必須是連續的
數據的流向：
- 讀操作（數據輸入）： I/O 設備 → 內存
- 寫操作（數據輸出）：內存 → I/O 設備
優點：數據傳輸以“塊”為單位，CPU 介入頻率進一步降低。數據的傳輸不再需要先經過 CPU 再寫入內存，數據傳輸效率進一步增加。CPU 和 I/O 設備的并行性得到提升。
缺點：CPU 每發出一條 I/O 指令，只能讀/寫一個或多個連續的數據塊。
如果要讀/寫多個離散存儲的數據塊，或者要將數據分別寫到不同的內存區域時，CPU要分別發出多條 I/O 指令，進行多次中斷處理才能完成。
通道控制方式
通道：一種硬件，可以理解為是 “ 弱雞版的 CPU ”。通?？梢宰R別并執行一系列的通道指令。
與 CPU 相比，通道可以執行的指令很單一，并且通道程序是放在主機內存中的，也就是說通道與CPU 共享內存。
CPU 干預的頻率：極低，通道會根據 CPU 的指示執行相應的通道程序，只有完成一組數據塊的讀/寫后才需要發出中斷信號，請求 CPU 干預。
數據傳送的單位：每次讀/寫一組數據塊。
數據的流向〈在通道的控制下進行)
- 讀操作（數據輸入）：I/O 設備 → 內存
- 寫操作（數據輸出）：內存 → I/O 設備
優點：CPU、通道、I/O 設備可并行工作，資源利用率很高。
缺點：實現復雜，需要專門的通道硬件支持。
小總結
4、IO軟件層次結構
用戶層軟件：實現與用戶交互的接口，向上提供方便易用的庫函數。
設備獨立性軟件：
- 向上層提供統一的調用接口（如read/write系統調用）；
- 設備的保護：原理類似于文件保護。設備被看做是一種特殊的文件，不同用戶對各個文件的訪問權限是不一樣的，同理，對設備的訪問權限也不一樣。
- 差錯處理：設備獨立性軟件需要對一些設備的錯誤進行處理
- 設備的分配與回收
- 數據緩沖區管理：可以通過緩沖技術屏蔽設備之間數據交換單位大小和傳輸速度的差異
- 建立邏輯設備名到物理設備名的映射關系：根據設備類型選擇調用相應的驅動程序
- 用戶或用戶層軟件發出I/O操作相關系統調用的系統調用時，需要指明此次要操作的I/O設備的邏輯設備名
- 設備獨立性軟件需要通過“邏輯設備表（LUT，Logical UnitTable）”來確定邏輯設備對應的物理設備，并找到該設備對應的設備驅動程序
設備驅動程序：主要負責對硬件設備的具體控制，將上層發出的一系列命令（如read/write）轉化成特定設備“能聽得懂”的一系列操作。包括設置設備寄存器，檢查設備狀態等
中斷處理程序：進行中斷處理。當I/O任務完成時，I/O控制器會發送一個中斷信號，系統會根據中斷信號類型找到相應的中斷處理程序并執行。中斷處理程序的處理流程如下:
硬件：執行 I/O 操作，有機械部分、電子部分組成。不同的I/O設備有不同的硬件特性，具體細節只有設備的廠家才知道。因此廠家需要根據設備的硬件特性設計并提供相應的驅動程序。
操作系統系統可以采用兩種方式管理邏輯設備表（LUT) :
- 第一種方式，整個系統只設置一張LUT，這就意味著所有用戶不能使用相同的邏輯設備名，因此這種方式只適用于單用戶操作系統。
- 第二種方式，為每個用戶設置一張LUT，各個用戶使用的邏輯設備名可以重復，適用于多用戶操作系統。系統會在用戶登錄時為其建立一個用戶管理進程，而LUT就存放在用戶管理進程的PCB中。
5、IO核心子系統
I/O 核心子系統要實現的功能其實就是中間三層要實現的功能。
I/O調度、設備保護、假脫機技術(SPOOLing技術）、設備分配與回收、緩沖區管理（即緩沖與高速緩存)
I/O調度&設備保護
I/O 調度：用某種算法確定一個好的順序來處理各個 I/O 請求。
如：磁盤調度（先來先服務算法、最短尋道優先算法、SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法）。當多個磁盤I/O請求到來時，用某種調度算法確定滿足l/O請求的順序。
同理，打印機等設備也可以用先來先服務算法、優先級算法、短作業優先等算法來確定I/O調度順序。
設備保護：
操作系統需要實現文件保護功能，不同的用戶對各個文件有不同的訪問權限。
在 UNIX 系統中，設備被看做是一種特殊的文件，每個設備也會有對應的FCB。
當用戶請求訪問某個設備時，系統根據FCB中記錄的信息來判斷該用戶是否有相應的訪問權限，以此實現“設備保護”的功能。（參考 文件保護 小結）
假脫機技術 SPOOLing
脫機技術
手工操作階段：主機直接從I/O設備獲得數據，由于設備速度慢，主機速度很快。人機速度矛盾明顯，主機要浪費很多時間來等待設備
批處理階段引入了脫機輸入/輸出技術（用磁帶完成)
引入脫機技術后，緩解了CPU與慢速I/O設備的速度矛盾。另一方面，即使CPU在忙碌，也可以提前將數據輸入到磁帶;即使慢速的輸出設備正在忙碌，也可以提前將數據輸出到磁帶。
脫機：脫離主機的控制進行輸入輸出操作！
假脫機技術
“假脫機技術”，又稱“SPOOLing 技術”，用軟件的方式模擬脫機技術。SPOOLing 系統的組成如下：
- 輸入井：模擬脫機輸入時的磁帶，用于收容I/O設備輸入的數據
- 輸出井：模擬脫機輸出時的磁帶，用于收容用戶進程輸出的數據
- 輸入進程：模擬脫機輸入時的外圍控制機
- 輸出進程：模擬脫機輸入時的外圍控制機
- 輸入緩沖區：在輸入進程的控制下，“輸入緩沖區”用于暫存從輸入設備輸入的數據，之后再轉存到輸入井中
- 輸出緩沖區：在輸出進程的控制下，“輸出緩沖區”用于暫存從輸出井送來的數據，之后再傳送到輸出設備上
- 內存：輸入緩沖區和輸出緩沖區是在內存中的緩沖區
- 磁盤：在磁盤上開辟出兩個存儲區域――“輸入井”和“輸出井”
要實現SPOOLing 技術，必須要有多道程序技術的支持。系統會建立“輸入進程”和“輸出進程”。
共享打印機器原理
獨占式設備：只允許各個進程串行使用的設備。一段時間內只能滿足一個進程的請求。
共享設備：允許多個進程“同時”使用的設備（宏觀上同時使用，微觀上可能是交替使用）?？梢酝瑫r滿足多個進程的使用請求。
打印機是一種 " 獨占式設備 "，但是可以用SPOOLing技術改造成 " 共享設備 "。
獨占式設備的例子：若進程1正在使用打印機，則進程2請求使用打印機時必然阻塞等待
當多個用戶進程提出輸出打印的請求時，系統會答應它們的請求，但是并不是真正把打印機分配給他們而是由假脫機管理進程為每個進程做兩件事：
當打印機空閑時，輸出進程會從文件隊列的隊頭取出一張打印請求表，并根據表中的要求將要打印的數據從輸出井傳送到輸出緩沖區，再輸出到打印機進行打印。用這種方式可依次處理完全部的打印任務
雖然系統中只有一個臺打印機，但每個進程提出打印請求時，系統都會為在輸出井中為其分配一個存儲區（相當于分配了一個邏輯設備），使每個用戶進程都覺得自己在獨占一臺打印機，從而實現對打印機的共享。
設備的分配與回收
大綱
設備分配要考慮因素
設備的固有屬性可分為三種：獨占設備、共享設備、虛擬設備。
- 獨占設備：一個時段只能分配給一個進程（如打印機）
- 共享設備：可同時分配給多個進程使用（如磁盤)，各進程往往是宏觀上同時共享使用設備，而微觀上交替使用。
- 虛擬設備：采用SPOOLing技術將獨占設備改造成虛擬的共享設備，可同時分配給多個進程使用（如采用SPOOLing技術實現的共享打印機)
設備分配算法：
- 先來先服務
- 優先級高者優先
- 短任務優先
從進程運行的安全性上考慮，設備分配有兩種方式：
1、安全分配方式：為進程分配一個設備后就將進程阻塞，本次 I/O 完成后才將進程喚醒。
一個時段內每個進程只能使用一個設備
優點：破壞了 “ 請求和保持 ” 條件，不會死鎖。
缺點：對于一個進程來說，CPU 和 I/O 設備只能串行工作。
2、不安全分配方式：進程發出 I/O 請求后，系統為其分配 I/O 設備，進程可繼續執行，之后還可以發出新的 I/O 請求。只有某個 I/O 請求得不到滿足時才將進程阻塞。
一個進程可以同時使用多個設備
優點：進程的計算任務和 I/O 任務可以并行處理，使進程迅速推進。
缺點：有可能發生死鎖（死鎖避免、死鎖的檢測和解除)。
靜態分配&動態分配
靜態分配：進程運行前為其分配全部所需資源，運行結束后歸還資源。破壞了“請求和保持”條件，不會發生死鎖
動態分配：進程運行過程中動態申請設備資源
設備分配管理數據結構
設備、控制器、通道之間的關系
一個通道可控制多個設備控制器，每個設備控制器可控制多個設備。
設備控制表（DCT）
系統為每個設備配置一張DCT，用于記錄設備情況。
控制器控制表（COCT）
每個設備控制器都會對應一張COCT。操作系統根據COCT的信息對控制器進行操作和管理。
通道控制表（CHCT）
通道控制表（CHCT):每個通道都會對應一張CHCT。操作系統根據CHCT的信息對通道進行操作和管理。
系統設備表（SDT）
記錄了系統中全部設備的情況，每個設備對應一個表目。
設備分配步驟
缺點：
- 用戶編程時必須使用 “ 物理設備名 ”，底層細節對用戶不透明，不方便編程。
- 若換了一個物理設備，則程序無法運行。
- 若進程請求的物理設備正在忙碌，則即使系統中還有同類型的設備，進程也必須阻塞等待。
設備分配步驟改進方法
建立邏輯設備名與物理設備名的映射機制，用戶編程時只需提供邏輯設備名。
某用戶進程第一次使用設備時使用邏輯設備名向操作系統發出請求，操作系統根據用戶進程指定的設備類型（邏輯設備名)查找系統設備表，找到一個空閑設備分配給進程，并在LUT中增加相應表項。
如果之后用戶進程再次通過相同的邏輯設備名請求使用設備，則操作系統通過LUT表即可知道用戶進程實際要使用的是哪個物理設備了，并且也能知道該設備的驅動程序入口地址。
邏輯設備表的設置問題：
整個系統只有一張LUT：各用戶所用的邏輯設備名不允許重復，適用于單用戶操作系統
每個用戶一張LUT：不同用戶的邏輯設備名可重復，適用于多用戶操作系統
緩沖區管理
大綱
什么是緩沖區
緩沖區是一個存儲區域，可以由專門的硬件寄存器組成，也可以利用內存作為緩沖區。
使用硬件作為緩沖區的成本較高，容量較小， 一般僅用在對速度要求非常高的場合。
比如聯想寄存器 ( 快表 ) 就是硬件作為緩沖區。
一般情況下， 更多的是利用內存作為緩沖區。
緩沖區的作用：
- 緩和CPU與I/O設備之間速度不匹配的矛盾
- 減少對CPU的中斷頻率，放寬對CPU中斷相應時間的限制
- 解決數據粒度不匹配的問題
- 提高CPU與I/O設備之間的并行性
單緩沖
假設某用戶進程請求某種塊設備讀入若干塊的數據。若采用單緩沖的策略，操作系統會在主存中為其分配一個緩沖區（若題目中沒有特別說明，一個緩沖區的大小就是一個塊）。
當緩沖區數據非空時，不能往緩沖區沖入數據，只能從緩沖區把數據傳出；
當緩沖區為空時，可以往緩沖區沖入數據，但必須把緩沖區充滿以后，才能從緩沖區把數據傳出。
雙緩沖
假設某用戶進程請求某種塊設備讀入若干塊的數據。若采用雙緩沖的策略，操作系統會在主存中為其分配兩個緩沖區（若題目中沒有特別說明，一個緩沖區的大小就是一個塊)。
結論：采用雙緩沖策略，處理一個數據塊的平均耗時為Max (T, C + M)
注：管道通信中的“管道”其實就是緩沖區。要實現數據的雙向傳輸，必須設置兩個管道
循環緩沖
將多個大小相等的緩沖區鏈接成一個循環隊列。
注：以下圖示中，橙色表示已充滿數據的緩沖區，綠色表示空緩沖區。
緩沖池
緩沖池由系統中共用的緩沖區組成。
這些緩沖區按使用狀況可以分為：
- 空緩沖隊列
- 裝滿輸入數據的緩沖隊列（輸入隊列）
- 裝滿輸出數據的緩沖隊列（輸出隊列）。
根據一個緩沖區在實際運算中扮演的功能不同，又設置了四種工作緩沖區：
- 用于收容輸入數據的工作緩沖區（hin)
- 用于提取輸入數據的工作緩沖區（sin)
- 用于收容輸出數據的工作級沖區( hout）
- 用于提取輸出數據的工作緩沖區（sout）。
總結
以上是生活随笔為你收集整理的计算机操作系统-详细版-王道的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 前端学习（1553）：复习2
- 下一篇： 前端学习（1607）：跨域请求