1、第一章（一）1.未配置操作系統的計算機系統（ 1）人工操作方式（人機矛盾）（ 2）脫機輸入 / 輸出方式2.單道批處理系統內存里一道作業3.多道批處理系統優點：（1）資源利用率高（ CPU 、內存、 I/0 設備）（2）系統吞吐量大缺點：（1）平均周轉時間長（2）無交互能力3.分時系統（解決人機交互）及時接收：多個用戶（配置多路卡） 、為每個用戶配置一個緩沖區及時處理：（1）作業直接進入內存（ 2）采用輪轉運行方式（時間片）響應時間 = 時間片×終端數4.實時系統周期性實時任務和非 .硬實時任務和軟 .（二）操作系統的基本特性1.并發（進程才能）實現并發執行的前提是：多道程序環境2.

2、共享互斥共享方式、同時訪問方式3.虛擬（ 1 ）時空復用技術（虛擬處理機技術、虛擬設備技術）（ 2）空分復用技術（虛擬磁盤技術、虛擬儲存器技術）4.異步5.操作系統兩個最基本的特征：并發和共享第二章（一）1.前趨圖（有向無環圖）：描述進程之間執行的先后順序2.順序執行：順序性、封閉性、可再現性并發執行：間斷性、失去封閉性、不可再現性（與時間有關的錯誤）Bernstein條件（二）1.進程實體：包括程序段、數據的和PCB2.進程的特征：動態性、并發性、獨立性、異步性（按各自速度推進）3.進程的三種基本狀態：就緒、執行、阻塞相互之間的轉換注意：執行 - （時間片完） -> 就緒4.進程的創建

3、（狀態）：申請空白 PCB-> 分配資源 -> 掛到就緒隊列進程的終止（狀態）：保存記錄 ->PCB 返還系統5.進程的掛起（不再被調度不在內存了、suspend 原語）活動就緒 - （掛起） -> 靜止就緒活動阻塞 - （掛起） -> 靜止阻塞執行- （掛起） -> 靜止就緒進程的激活（ active 原語）靜止就緒 - （激活） -> 活動就緒靜止阻塞 - （激活） -> 活動阻塞6.PCB 中的信息： P41PCB 組織方式：線性方式、鏈接方式、索引方式(三)1.OS 內核：常駐內存OS 狀態 :系統態（管態、內核態）用戶態（目態）2.父進

4、程創建子進程： 3 種返回值進程圖 :描述進程家族關系的一棵樹3.進程的創建（ Creat 原語）引起進程創建的事件：用戶登錄、作業調度、提供服務（創建打印進程） 、應用請求（用戶創建）創建過程：申請空白 PCB-> 分配資源（從系統或父進程） -> 初始化進程控制塊（初始化內容見 P45 ）-> 插入就緒隊列4.進程的終止引起進程終止的事件：正常結束、異常結束、外界干預終止過程： P465.進程的阻塞（ block 原語）引起事件：請求共享資源失敗、等待某種操作的完成（ I/O 操作）、新數據未到達（合作進程中）、等待新任務的到來（發送進程，沒有信息可發送）阻塞過程：狀態：

5、執行變為阻塞->PCB 掛到阻塞隊列 -> 調度其他進程6.進程的喚醒（ wakeup原語）喚醒過程：移除阻塞隊列-> 掛到就緒隊列（四）1.進程的同步（ 1）同步 :即某件事要等待另一件事完成才可以開始（ 2）2 種相互制約關系 ：間接相互制約關系（進程互斥訪問資源） 、直接相互制約關系（進程合作）2.臨界資源、臨界區（進入區、退出區、剩余區）3.同步機制遵循的規則 :空閑讓進、忙則等待、 有限等待、讓權等待（請求資源失敗應釋放 CPU ）4.3 種信號量：互斥信號量（初值為1 ）、資源信號量（初值可為n）、同步信號量 (初值為 0)P（ wait ）原語：減 1V(sig

6、nal) 原語：加 1（五）1.進程的互斥和同步稱為低級進程通信，還有基于共享數據結構的通信方式也是2.進程通信方式（ 1）直接通信方式（基于共享存儲區）申請一個緩沖區 -> 將進程 A 發送區的內容復制給緩沖區 -> 將緩沖區掛到進程 B 的消息隊列 -> 進程 B 將緩沖區復制到自己的接收區（ 2）管道通信方式（對管道的 write 和 read ）管道是一個 pipe 文件，作為一個中介（ 3）消息傳遞方式（封裝） ：直接和間接（有中間實體：郵箱）（六）進程和線程的區別重第三章（一）1.三大調度：高級調度（作業調度） ：調度作業（外存 -> 內存），只用于多道批處

7、理系統低級調度（進程調度）：調度進程（就緒 -> 獲得 CPU ）中級調度（內存調度）：掛起（內存 -> 外存 -> 重入內存）2.CPU 利用率： CPU 有效工作時間 /(CPU 有效工作時間 +CPU 空閑等待時間 )（二）1.作業：包含程序和數據，還有作業說明書。批處理系統中，是以作業為基本單位從外存調入內存的。2.作業控制塊（ JCB） :作業在系統中存在的標志。包含：作業標識、 .P883.作業進入系統時 -> “作業注冊” 程序為其建立作業控制塊 -> 放到作業后備隊列（外存） -> 調度作業進入內存4.作業的 4 種狀態：提交狀態、后備狀態、

8、運行狀態（對應的進程有 3 種狀態）、完成狀態5.作業調度的任務：（ 1）接納多少個作業：取決于多道程序度（2）接納哪些作業：取決于調度算法調度時機：內存中的進程數小于多道度6.進程的響應時間（作業的周轉時間） ：完成時間 - 到達時間或 服務時間 + 等待時間平均周轉時間： N 個的和除以 N帶權周轉時間：（服務時間 + 等待時間） / 服務時間或 1+ 等待時間 / 服務時間平均帶權周轉時間： N 個的和除以 N7.調度算法 (4 種都可用于作業調度或進程調度)（ 1）先來先服務（ FCFS） 只能非搶占式（ 2）短進程優先（ SJF）：有效降低作業的平均周轉時間；對長作業不利（ 3）優先

9、級調度算法 (PSA)（ 4）高響應比優先調度算法（ HRRN ）:優先級隨等待時間延長而增加優先權 = （服務時間 + 等待時間） / 服務時間 或 1+ 等待時間 / 服務時間必須等某個進程完成時，才重新計算優先權，即運行某進程過程中有新進程到達也不會重新調度后面 3 個對于作業只能非搶占式；對于進程，可搶占式或非搶占式8.題目未說明時，默認是非搶占式。（三）1.非搶占式：調度時機為 （1 ）進程運行完畢（ 2）進程 I/O 請求（3 ）執行 Block 原語搶占式：搶占原則（ 1）優先權（ 2 ）短進程優先（ 3）時間片2.調度算法（ 1）輪轉調度算法：基于時間片（ 2）優先級調度算法（

10、 3）多隊列調度算法：多個 就緒隊列 ，不同隊列采用不同的調度算法（ 4）多級反饋隊列調度算法：對于長作業，往后時間片越長，得到的處理時間越長（ 5）最低松弛度優先算法：松弛度 = 必須完成時間 -需要服務時間（四）1.可重用性資源（打印機） ：請求資源 -> 獲得資源 -> 釋放資源可消耗性資源（通信中的消息） ：進程運行期間動態創建和消耗的，不再返回可搶占性資源（ CPU、內存）不可搶占性資源（打印機） ：可能引起死鎖2.引起死鎖的 3 個原因：（ 1）競爭不可搶占性資源（ 2 ）競爭可消耗性資源（ 3）進程推進順序不當（不安全區 D）3.產生死鎖的必要條件 ：（ 1）互斥條件

11、（ 2 ）請求和保持條件（ 3 ）不可搶占條件（ 4 ）循環等待條件（產生回路）4.處理死鎖的方法 ：（ 1）預防死鎖（ 2 ）避免死鎖（ 3）檢測死鎖（ 4 ）解除死鎖5.預防死鎖：破壞其中一個條件（ 1）互斥條件不能破壞還應保持（ 2）破壞請求和保持條件： A.一次性申請所需全部資源 B.申請部分資源，用完釋放，然后繼續申請 (資源靜態分配 )（ 3）破壞不可搶占條件：提出新的資源請求時，必須釋放自己已保持的所有資源（好像被搶占了）（ 4）破壞循環等待條件： 每個進程按序號遞增的順序請求資源（資源有序分配）6.避免死鎖：防止系統進入不安全狀態（ 1）系統安全狀態：分配資源后，系統能按一 安

12、全序列 推進（ 2）銀行家算法 ：二維數組 A. 表示每個進程對每個資源的最大需求量B.表示每個進程對每個資源已分配到的C.表示每個進程對每個資源還需要的一維數組A.表示每類資源的可分配數availableB.表示每個資源當前可分配數 （即加上某個進程運行完，釋放后的資源數）workC.表示每個進程能否獲得足夠資源而運行finish算法思路： P112-1147.檢測死鎖：（ 1）資源分配圖（ 2）死鎖定理： S 為死鎖的充分條件 :當且僅當 S 狀態的資源分配圖是 不可完全簡化的8.解除死鎖：（ 1）搶占資源（ 2）終止（撤銷）進程方法： A.終止所有進程B.逐個終止進程： 付出代價最小的死

13、鎖解除算法 P117-118第四章存儲器管理均稱為傳統存儲器管理方式，具有2 個特點：一次性和駐留性P153（一）1.存儲系統至少3 級：最高層為 CPU 寄存器，內存，最底層為輔存。2.可執行存儲器：寄存器和內存。3.進程訪問可執行存儲器：使用一條load 或 store 指令即可訪問輔存：需通過I/O 設備4.程序的裝入方式（ 1）絕對裝入方式 ：單道環境程序的相對地址（邏輯地址）與內存地址完全相同（ 2）靜態可重定位裝入方式 ：多道環境 在裝入時對目標程序中指令和數據地址進行修改，以后不再改變。（ 3）動態運行時的裝入方式 ：程序運行過程在內存的位置經常會改變 裝入內存，地址轉換推遲到程

14、序運行時才進行。A.工作原理：增設一個 重定位寄存器 ，存放程序在內存中的起始地址 -> 真正訪問內存地址 = 相對地址 + 寄存器中的地址-> 程序移動時，只需修改寄存器中的起始地址B.在“緊湊（拼接）”時，要用到。（二）連續分配存儲管理方式1.單一連續分配 ：單道環境內存分為系統區（多放在低址）和用戶區2.固定分區分配 ：多道環境 內存劃分為若干個固定大小的區域，一個區域裝入一道作業（ 1） a.分區大小相等 b. 分區大小不等（ 2）地址映射：采用靜態重定位（ 3）缺點：造成大量的內部碎片（ 4）數據結構：分區使用表包括分區號、大小、起址、狀態。3.動態分區分配（可變分區分配

15、） ：（ 1）分區分配：按需劃分分區回收：合并回收（ 2）數據結構：空閑分區表 包括分區號、大小、起址、狀態（全都是未分配）空閑分區鏈 雙向的（ 3）分配： P128 下面回收： P129 注意不同合并方式會對空閑分區表的修改不同（ 4）基于順序搜索的動態分區分配算法A.首次適應算法：每次分配從頭順序查找，找到大小可以滿足為止特點：優先利用內存地址空閑區，保留了高址的大空閑區缺點：低址不斷被劃分，產生許多碎片；查找效率低對固定分區：整體分配，易形成內碎片對可變分區：按需劃分，易形成外碎片B.循環首次適應算法：循環的，從上次找到的位置往下查找特點：使內存的空閑分區分布得更均勻缺點：缺乏大的空閑分

16、區C.最佳適應算法：所有空閑分區從小到大形成空閑分區鏈缺點：留下許多碎片對固定分區：內碎片小對可變分區：易形成外碎片D.最壞適應算法：所有空閑分區從大到小形成空閑分區鏈優點：產生碎片的可能性最小 ；查找效率高對固定分區：內碎片大對可變分區：剩余分區可再次利用（ 5）基于索引搜索的動態分區分配算法A.快速適應算法：相同容量的空閑分區形成一個空閑分區鏈設置索引表查找特點：不會對任何分區產生分割，不會產生內存碎片優點：查找效率高在分配分區時，以進程為單位，一個分區只屬于一個進程，或多或少存在浪費B.伙伴系統：原理、分配、回收、計算伙伴地址P132C.哈希算法：建立哈希函數，構造哈希表4.動態重定位分

17、區分配算法：與 3 （3）基本相同，差別僅在于增加了緊湊的功能（三）對換1.對換：進程或程序和數據：內存<-> 外存2.對換的類型 ：（ 1）整體對換（進程對換） ：整個進程為單位對換（ 2）頁面 / 分段對換（部分對換）：以進程的一個頁面或分段為單位對換目的：支持虛擬存儲系統3.磁盤空間分為文件區和對換區（對換空間）文件區：離散分配對換區：按需分配（分配算法上面4 種都可以）、合并回收4.進程的換進換出的選擇標準P137換出：換到 無阻塞進程為止換入：第一個換“就緒”且換出時間最久的進程，繼續換到 無處于“就緒且換出”狀態的進程為止（四）分頁存儲管理方式：提高內存利用率1.程序分

18、為若干固定大小的頁面，內存同樣稱為物理塊（頁框）2.頁面大小應為2 的冪，通常為 1KB-8KB3.地址結構：頁號P+ 頁內地址 W （一維的）若頁面的大小為 L,則邏輯地址 LA=P*L+W4.每個進程一張 頁面映像表（頁表）：存放在內存里，實現從頁號到物理塊號的地址映射頁表大小 = 表項數 *表項大小P1395.地址變換機構：實現從邏輯地址到物理地址的轉換6.頁表寄存器：存放頁表始址+ 頁表長度進程未執行時，頁表始址 + 頁表長度放在 本進程 PCB 中-> 執行時，裝入頁表寄存器7.查找過程（ 2 次訪問內存）：頁表寄存器 -> 頁表（內存里） -> 得到內存物理地址，

19、到內存取指令8.具有快表（聯想寄存器） ：先查快表看能否命中，未能命中則 查完頁表后還要修改快表9.查快表 t1, 查頁表和取指令t2:若同時查塊表和頁表：命中：t1+t2未命中： t2+t1( 修改快表 )+t2若命中率為 h, 可得有效訪問內存的時間:h*t1+(1-h)*(t2+t1)+t2（五）分段存儲管理方式：滿足用戶編程和使用的要求1.作業分為若干個大小不同的段2.一個作業最多64K 個段，每個段最大長度為64KB3.地址結構：段號 + 段內地址（二維的）段號太大，段表中找不到則表示 越界；段內地址太大， 超過段表中目的段的大小，則表示 段內越界 。4.每個進程一張段映射表（段表）

20、 ：存放在內存里，每個表項包含一個 段的起始地址（基址） + 該段的長度5.地址變換機構：段表寄存器，存放段表始址+ 段表長度6.查找過程（ 2 次訪問內存）：段表寄存器 -> 段表（內存里） -> 得到內存物理地址，到內存取指令7.具有聯想寄存器的：與分頁式相同8.分頁與分段的區別： P148( 重)（六）段頁式存儲管理方式1.程序分成若干段，每個段再分成若干頁2.地址結構：段號 + 段內頁號 + 頁內地址（二維的）3.需要段表寄存器、段表、頁表：每個進程一張段表，段表包含頁表始址+ 頁表大小4.查找過程（ 3 次訪問內存）：段表寄存器 -> 找段表（內存里），得到該段對應

21、的頁表起始地址 -> 找頁表（內存里），得到該頁的物里塊號 -> 形成物理地址，到內存取指令5.具有聯想寄存器的：與分頁式相同第五章虛擬儲存器原理：局部性原理（時間局部性、空間局部性）（一）概述1.虛擬儲存器：具有 請求調入 功能和置換功能，從邏輯上對內存容量擴充2.特征：多次性、對換性、虛擬性3.實現虛擬儲存器的基礎：離散存放、多次裝入（二）請求分頁存儲管理方式1.頁表增加 4 個字段：狀態位（該頁是否已調入內存） 、訪問位（訪問次數或多久未訪問）、修改位（有被修改的置換時要寫回外存）、外存地址2.缺頁中斷機構 ：指令執行期間，發現要訪問的指令或數據不在內存，馬上發出中斷這種屬于

22、陷進（軟中斷），之前打印機那些是硬中斷3.地址變換過程P158( 重 )注意最后必有“修改訪問位和修改位”這一步驟4.最小物理塊數：進程能正常運行的最小物理塊數5.內存分配策略 ：（ 1）固定分配局部置換固定分配：為每個進程分配固定數目的物理塊，不再改變局部置換：只能從分配給該進程的頁面中選一頁換出（ 2）可變分配全局置換（ 3）可變分配局部置換一進程運行時缺頁率很低，可以減少分配給該進程的物理塊數6.物理塊分配算法（ 1）平均分配算法：平均分配給各個進程（ 2）按比例分配算法：按進程大?。?3）考慮優先級的分配算法7.頁面調入策略（ 1）何時調入A.預調頁策略 ：將預計不久后會被訪問的頁面預

23、先調入內存，可用于首次調入時B.請求調頁策略 ：缺頁請求時再調入，一次只調入一頁（ 2）何處調入UNIX 方式：從未運行過的，從文件區調入置換在對換區的，從對換區調入8.缺頁率：訪問頁面失敗的次數F/ 訪問頁面總次數A（三）頁面置換算法1.最佳置換算法（無法實現的） ：換出未來最遲被訪問的頁面2.先進先出置換算法： 可能產生 Belady 異常，即分配的頁面數越多，缺頁率反而越多原因：先進的一般都是經常被訪問的3.最近最久未使用置換算法（LRU）:需要移位寄存器或棧兩個硬件之一的支持移位寄存器：每個在內存的頁面配置一個R=Rn-1Rn-2.R1R0進程訪問某物理塊時，將相應的寄存器的 Rn-1

24、 位置 1。每隔一段時間寄存器右移一位。最小數值那個就是最近最久未使用的頁面。棧：棧頂總是最近訪問的頁面號（命中時調到棧頂） ，棧低總是最久的（置換時從棧底淘汰）4.最少使用置換算法（ LFU）:即看訪問次數最少的采用移位寄存器方式：每次訪問某頁，將該寄存器最高位置 1 ，每隔一段時間右移一位。最小數值那個就是最少使用的頁面。5.簡單的 Clock 置換算法（最近未用算法NRL ）：每頁設置訪問位 (A) ，將內存中所有頁面構成循環隊列。 某頁被訪問時，訪問位置 1置換時，若訪問位為0 則換出，為 1 則改為 0改進的 Clock 置換算法 ：多了修改位 (W) ，修改為為 1 表示修改過第一

25、步： 優先置換“ A=0 ，W=0 ”的頁面 ，不改變訪問位A第二步：找“ A=0 ，W=1 ”的頁面，同時將A=1 的改為 A=0第三步：重復第一步6.頁面緩沖算法（ PBA）：（ 1）影響頁面換進換出效率的因素A.頁面置換算法B.寫回磁盤的頻率C.讀入內存的頻率（ 2）算法原理 :A.空閑頁面鏈表：用于分配給頻繁缺頁的進程、一個 未被修改 的頁面（有數據）要換出時，不換出，接到該鏈末尾B.修改頁面鏈表：一個 已修改的 頁面要換出時，不換出，接到該鏈末尾，方便集中寫回磁盤（四）抖動與工作集1.工作集：某段時間內，進程實際所要訪問頁面的集合不同時間的工作集大小不同，所含的頁面數也不同P1712

26、.抖動（ 1）產生原因：進程太多，缺頁頻繁， CPU 效率急劇下降（進程處于“抖動”狀態）（ 2）產生前提：采取可變分配 + 全局置換（ 3）預防方法 ：A.采取局部置換策略B.把工作集算法融入到處理機調度中調入作業之前，檢查每個進程在內存的駐留頁面是否足夠多。C.利用“ L=S ”準則調節缺頁率P172D.選擇暫停的進程：掛起若干進程第六章（一） I/O 系統1.I/O 系統的層次結構：從下往上：硬件 -> 中斷處理程序 -> 設備驅動程序 -> 設備獨立性軟件 -> 用戶層軟件2.I/O 系統的上、下接口：I/O 系統接口、軟件 / 硬件接口（下面就是硬件部分了）3

27、.I/O 系統的分層：從下往上：中斷處理程序 -> 設備驅動程序 -> 設備獨立性軟件4.I/O 系統接口：有 3 種（ 1）塊設備接口A.塊設備：以 數據塊 為單位（磁盤）特點：傳輸速率高；可尋址；磁盤設備的 I/O 常采用 DMA 方式B.塊設備接口特征：隱藏了磁盤的二維結構（磁道號+ 扇區）；將抽象的命令映射為底層操作（ 2）流設備接口A.流設備：以字符為單位（鍵盤、打印機） 特點：傳輸速率低；不可尋址；流設備的 I/O 常采用中斷驅動方式B.程序用 get 和 put 操作，只能順序存取C.大多數流設備屬于獨占設備（互斥方式），要提供打開 / 關閉操作。（ 3）網絡通信接口

28、（二）硬件部分1.I/O 設備的類型：存儲設備和I/O 設備、低速設備（鍵盤、鼠標）和中速設備（打印機）和高速設備（磁盤、光盤）2.設備控制器（控制一個或多個I/O 設備）（ 1）三部分組成：A.設備控制器與 CPU 的接口（并行）：數據總線 ->DR: 內存 <-> 設備->C/S: 狀態：設備 ->CPU啟動： CPU-> 設備地址總線：設備名 -> 譯碼電路（ I/O 邏輯） -> 接口控制總線：操作碼 -> 譯碼電路 ->CRB.設備控制器與設備的接口（串行） ：數據線：設備 <->DR狀態線：設備 ->C/

29、S控制線： C/S-> 設備C.譯碼電路（ I/O 邏輯）：實現對設備的控制上面 2 個譯碼功能 + 并行 - （分解） -><-(組裝 )- 串行（ 2） CPU 啟動一個設備的過程：啟動命令 -> 設備控制器地址（即要選哪個設備） - 地址線 -> 設備控制器 ->I/O 邏輯進行譯碼 -> 選中設備（ 3）設備 ->DR: 數據準備； DR-> 內存：數據傳送（ 4）設備控制器的功能：A.接收和識別命令B.數據交換C.標識和報告設備的狀態D.地址識別（設備控制器可連接多個設備、其里面也有很大寄存器，都需要地址）E.數據緩沖區F.差錯控

30、制3.I/O 通道（特殊處理機）（ 1）在 CPU 與設備控制器之間目的：建立獨立的I/O 操作（ 2）過程： CPU 發 I/O 指令 -> 通道 -> 內存中取對應的通道程序并執行 -> 完成后，向 CPU 發中斷信號（ 3）通道與 CPU 共享內存（其通道程序放在內存）（ 4）通道的類型：A.字節多路通道：每個字通道連接一個設備，按時間片輪轉共享主通道適合低速設備B.數組選擇通道：每次只允許一個設備傳輸數據C.數組多路通道（三）設備驅動程序1.設備驅動程序的功能：A.將命令中的抽象要求轉換為與設備相關的底層操作B.檢查 I/O 請求的合法性，設置設備的工作方式C.啟動

31、I/O 設備D.及時響應設備控制器發來的中斷請求，調用相應的中斷處理程序2.設備驅動程序的特點：A.用匯編語言編寫B.允許可重入3.設備處理方式：A.每類設備一個進程來控制B.整個系統一個進程或一個輸入一個輸出共2 個進程C.不設置進程（常用）4.設備驅動程序的處理過程：將抽象要求轉換為具體要求 -> 對服務請求進行校驗 -> 檢查設備的狀態 -> 傳送必要的參數-> 啟動 I/O 設備啟動后，驅動程序把控制返回給I/O 系統，自己阻塞起來， 直到中斷到來被喚醒I/O 操作是在設備控制器的控制下進行，實現處理機與 I/O 設備的并行操作5.對 I/O 設備的控制方式（

32、1）輪詢的可編程 I/O 方式：數據傳送過程中， CPU 一直查詢CPU 與設備、設備之間只能串行工作（ 2）中斷的可編程I/O 方式（以 字節為單位 傳送數據）：數據傳送過程中， CPU 干別的事， 傳送好控制器通過控制線發中斷給CPU，CPU 取走數據寫入內存能并行工作（ 3）直接儲存器訪問方式（DMA 方式）：A.以數據塊為單位 、直接從設備到內存、在控制器的控制下不用經過CPUB.DMA 控制器：三部分組成：DMA 控制器與主機的接口、 與設備的接口、 I/O 控制邏輯含有 4 個寄存器：數據寄存器 DR、控制 / 狀態寄存器 CR、數據計數器DC、內存地址寄存器 MARC.工作過程： CPU 要