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中的信息：P41 PCB組織方式：線性方式、鏈接方式、索引方式(三)1.OS內核：常駐內存 OS狀態:系統態（管態、內核態） 用戶態（目態）2.父進程創建子進程：3種返回值 進程圖:描述進程家

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

5、進程的喚醒（wakeup原語） 喚醒過程：移除阻塞隊列->掛到就緒隊列（四）1.進程的同步（1）同步:即某件事要等待另一件事完成才可以開始（2）2種相互制約關系：間接相互制約關系（進程互斥訪問資源）、直接相互制約關系（進程合作）2.臨界資源、臨界區（進入區、退出區、剩余區）3.同步機制遵循的規則:空閑讓進、忙則等待、有限等待、讓權等待（請求資源失敗應釋放CPU）4.3種信號量：互斥信號量（初值為1）、資源信號量（初值可為n）、同步信號量(初值為0) P（wait）原語：減1 V(signal)原語：加1（五）1.進程的互斥和同步稱為低級進程通信，還有基于共享數據結構的通信方式也是2.進程

6、通信方式（1）直接通信方式（基于共享存儲區） 申請一個緩沖區->將進程A發送區的內容復制給緩沖區->將緩沖區掛到進程B的消息隊列->進程B將緩沖區復制到自己的接收區（2）管道通信方式（對管道的write和read） 管道是一個pipe文件，作為一個中介（3） 消息傳遞方式（封裝）：直接和間接（有中間實體：郵箱）（六）進程和線程的區別 重第三章（一）1.三大調度：高級調度（作業調度）：調度作業（外存->內存），只用于多道批處理系統 低級調度（進程調度）：調度進程（就緒->獲得CPU） 中級調度（內存調度）：掛起（內存->外存->重入內存）2.CPU利用率

7、：CPU有效工作時間/(CPU有效工作時間+CPU空閑等待時間)（二）1.作業：包含程序和數據，還有作業說明書。 批處理系統中，是以作業為基本單位從外存調入內存的。2.作業控制塊（JCB）:作業在系統中存在的標志。包含：作業標識、.P883.作業進入系統時->“作業注冊”程序為其建立作業控制塊->放到作業后備隊列（外存）->調度作業進入內存4.作業的4種狀態：提交狀態、后備狀態、運行狀態（對應的進程有3種狀態）、完成狀態5.作業調度的任務：（1）接納多少個作業：取決于多道程序度 （2）接納哪些作業：取決于調度算法 調度時機：內存中的進程數小于多道度6.進程的響應時間（作業的周

8、轉時間）：完成時間-到達時間 或 服務時間+等待時間 平均周轉時間：N個的和除以N 帶權周轉時間：（服務時間+等待時間）/服務時間 或 1+等待時間/服務時間 平均帶權周轉時間：N個的和除以N7.調度算法(4種都可用于作業調度或進程調度)（1）先來先服務（FCFS） 只能非搶占式（2）短進程優先（SJF）：有效降低作業的平均周轉時間；對長作業不利（3）優先級調度算法(PSA)（4）高響應比優先調度算法（HRRN）:優先級隨等待時間延長而增加 優先權=（服務時間+等待時間）/服務時間 或 1+等待時間/服務時間 必須等某個進程完成時，才重新計算優先權，即運行某進程過程中有新進程到達也不會重新調度

9、后面3個對于作業只能非搶占式；對于進程，可搶占式或非搶占式8.題目未說明時，默認是非搶占式。（三）1.非搶占式：調度時機為（1）進程運行完畢（2）進程I/O請求（3）執行Block原語 搶占式：搶占原則（1）優先權（2）短進程優先（3）時間片2.調度算法（1）輪轉調度算法：基于時間片（2）優先級調度算法（3）多隊列調度算法：多個就緒隊列，不同隊列采用不同的調度算法（4）多級反饋隊列調度算法：對于長作業，往后時間片越長，得到的處理時間越長（5）最低松弛度優先算法：松弛度=必須完成時間-需要服務時間（四）1.可重用性資源（打印機）：請求資源->獲得資源->釋放資源 可消耗性資源（通信中

10、的消息）：進程運行期間動態創建和消耗的，不再返回 可搶占性資源（CPU、內存） 不可搶占性資源（打印機）：可能引起死鎖2.引起死鎖的3個原因：（1）競爭不可搶占性資源（2）競爭可消耗性資源（3）進程推進順序不當（不安全區D）3.產生死鎖的必要條件：（1）互斥條件（2）請求和保持條件（3）不可搶占條件（4）循環等待條件（產生回路）4.處理死鎖的方法：（1）預防死鎖（2）避免死鎖（3）檢測死鎖（4）解除死鎖5.預防死鎖：破壞其中一個條件（1）互斥條件不能破壞還應保持（2）破壞請求和保持條件：A.一次性申請所需全部資源 B.申請部分資源，用完釋放，然后繼續申請(資源靜態分配)（3）破壞不可搶占條件：

11、提出新的資源請求時，必須釋放自己已保持的所有資源（好像被搶占了）（4）破壞循環等待條件：每個進程按序號遞增的順序請求資源（資源有序分配）6.避免死鎖：防止系統進入不安全狀態（1）系統安全狀態：分配資源后，系統能按一安全序列推進（2）銀行家算法：二維數組 A.表示每個進程對每個資源的最大需求量 B.表示每個進程對每個資源已分配到的 C.表示每個進程對每個資源還需要的 一維數組 A.表示每類資源的可分配數 available B.表示每個資源當前可分配數（即加上某個進程運行完，釋放后的資源數）work C.表示每個進程能否獲得足夠資源而運行 finish 算法思路：P112-1147.檢測死鎖：（

12、1）資源分配圖（2）死鎖定理：S為死鎖的充分條件:當且僅當S狀態的資源分配圖是不可完全簡化的8.解除死鎖：（1）搶占資源（2）終止（撤銷）進程 方法：A.終止所有進程 B.逐個終止進程：付出代價最小的死鎖解除算法P117-118第四章 存儲器管理均稱為傳統存儲器管理方式，具有2個特點：一次性和駐留性 P153（一）1.存儲系統至少3級：最高層為CPU寄存器，內存，最底層為輔存。2.可執行存儲器：寄存器和內存。3.進程訪問可執行存儲器：使用一條load或store指令即可 訪問輔存：需通過I/O設備4.程序的裝入方式（1）絕對裝入方式：單道環境 程序的相對地址（邏輯地址）與內存地址完全相同（2）

13、靜態可重定位裝入方式：多道環境 在裝入時對目標程序中指令和數據地址進行修改，以后不再改變。（3）動態運行時的裝入方式：程序運行過程在內存的位置經常會改變 裝入內存，地址轉換推遲到程序運行時才進行。 A.工作原理：增設一個重定位寄存器，存放程序在內存中的起始地址->真正訪問內存地址=相對地址+寄存器中的地址 ->程序移動時，只需修改寄存器中的起始地址 B.在“緊湊（拼接）”時，要用到。（二）連續分配存儲管理方式1.單一連續分配：單道環境 內存分為系統區（多放在低址）和用戶區2.固定分區分配：多道環境 內存劃分為若干個固定大小的區域，一個區域裝入一道作業（1）a.分區大小相等 b.分區

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

15、，易形成內碎片 對可變分區：按需劃分，易形成外碎片 B.循環首次適應算法：循環的，從上次找到的位置往下查找 特點：使內存的空閑分區分布得更均勻 缺點：缺乏大的空閑分區 C.最佳適應算法：所有空閑分區從小到大形成空閑分區鏈 缺點：留下許多碎片 對固定分區：內碎片小 對可變分區：易形成外碎片 D.最壞適應算法：所有空閑分區從大到小形成空閑分區鏈 優點：產生碎片的可能性最小；查找效率高 對固定分區：內碎片大 對可變分區：剩余分區可再次利用（5）基于索引搜索的動態分區分配算法 A.快速適應算法：相同容量的空閑分區形成一個空閑分區鏈 設置索引表查找 特點：不會對任何分區產生分割，不會產生內存碎片 優點：

16、查找效率高 在分配分區時，以進程為單位，一個分區只屬于一個進程，或多或少存在浪費 B.伙伴系統：原理、分配、回收、計算伙伴地址 P132 C.哈希算法：建立哈希函數，構造哈希表4.動態重定位分區分配算法：與3（3）基本相同，差別僅在于增加了緊湊的功能（三）對換1.對換：進程或程序和數據：內存<->外存2.對換的類型：（1）整體對換（進程對換）：整個進程為單位對換（2）頁面/分段對換（部分對換）：以進程的一個頁面或分段為單位對換 目的：支持虛擬存儲系統3.磁盤空間分為文件區和對換區（對換空間） 文件區：離散分配 對換區：按需分配（分配算法上面4種都可以）、合并回收4. 進程的換進換出

17、的選擇標準 P137 換出：換到無阻塞進程為止 換入：第一個換“就緒”且換出時間最久的進程，繼續換到無處于“就緒且換出”狀態的進程為止（四）分頁存儲管理方式：提高內存利用率1.程序分為若干固定大小的頁面，內存同樣稱為物理塊（頁框）2.頁面大小應為2的冪，通常為1KB-8KB3.地址結構：頁號P+頁內地址W（一維的） 若頁面的大小為L,則邏輯地址LA=P*L+W4.每個進程一張頁面映像表（頁表）：存放在內存里，實現從頁號到物理塊號的地址映射 頁表大小=表項數*表項大小 P1395.地址變換機構：實現從邏輯地址到物理地址的轉換6.頁表寄存器：存放頁表始址+頁表長度 進程未執行時，頁表始址+頁表長度

18、放在本進程PCB中->執行時，裝入頁表寄存器7.查找過程（2次訪問內存）：頁表寄存器->頁表（內存里）->得到內存物理地址，到內存取指令8.具有快表（聯想寄存器）：先查快表看能否命中，未能命中則查完頁表后還要修改快表9.查快表t1,查頁表和取指令t2: 若同時查塊表和頁表：命中：t1+t2 未命中：t2+t1(修改快表)+t2 若命中率為h,可得有效訪問內存的時間:h*t1+(1-h)*(t2+t1)+t2（五）分段存儲管理方式：滿足用戶編程和使用的要求1.作業分為若干個大小不同的段2.一個作業最多64K個段，每個段最大長度為64KB3.地址結構：段號+段內地址（二維的） 段

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

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

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

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

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

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

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

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

27、中速設備（打印機）和高速設備（磁盤、光盤）2.設備控制器（控制一個或多個I/O設備）（1）三部分組成： A.設備控制器與CPU的接口（并行）： 數據總線->DR:內存<->設備 ->C/S:狀態：設備->CPU 啟動：CPU->設備 地址總線：設備名->譯碼電路（I/O邏輯）->接口 控制總線：操作碼->譯碼電路->CR B.設備控制器與設備的接口（串行）： 數據線：設備<->DR 狀態線：設備->C/S 控制線：C/S->設備 C.譯碼電路（I/O邏輯）：實現對設備的控制 上面2個譯碼功能+并行-（分解）-&

28、gt;<-(組裝)-串行（2）CPU啟動一個設備的過程： 啟動命令->設備控制器 地址（即要選哪個設備）-地址線->設備控制器->I/O邏輯進行譯碼->選中設備（3）設備->DR:數據準備；DR->內存：數據傳送（4）設備控制器的功能： A.接收和識別命令 B.數據交換 C.標識和報告設備的狀態 D.地址識別（設備控制器可連接多個設備、其里面也有很大寄存器，都需要地址） E.數據緩沖區 F.差錯控制3.I/O通道（特殊處理機）（1）在CPU與設備控制器之間 目的：建立獨立的I/O操作（2）過程：CPU發I/O指令->通道->內存中取對應的通

29、道程序并執行->完成后，向CPU發中斷信號（3）通道與CPU共享內存（其通道程序放在內存）（4）通道的類型： A.字節多路通道：每個字通道連接一個設備，按時間片輪轉共享主通道 適合低速設備 B.數組選擇通道：每次只允許一個設備傳輸數據 C.數組多路通道（三）設備驅動程序1.設備驅動程序的功能： A.將命令中的抽象要求轉換為與設備相關的底層操作 B.檢查I/O請求的合法性，設置設備的工作方式 C.啟動I/O設備 D.及時響應設備控制器發來的中斷請求，調用相應的中斷處理程序2.設備驅動程序的特點： A.用匯編語言編寫 B.允許可重入3.設備處理方式： A.每類設備一個進程來控制 B.整個系統

30、一個進程或一個輸入一個輸出共2個進程 C.不設置進程（常用）4.設備驅動程序的處理過程：將抽象要求轉換為具體要求->對服務請求進行校驗->檢查設備的狀態->傳送必要的參數 ->啟動I/O設備 啟動后，驅動程序把控制返回給I/O系統，自己阻塞起來，直到中斷到來被喚醒 I/O操作是在設備控制器的控制下進行，實現處理機與I/O設備的并行操作5.對I/O設備的控制方式（1）輪詢的可編程I/O方式：數據傳送過程中，CPU一直查詢 CPU與設備、設備之間只能串行工作（2）中斷的可編程I/O方式（以字節為單位傳送數據）： 數據傳送過程中，CPU干別的事，傳送好控制器通過控制線發中斷給CPU，CPU取走數據寫入內存 能并行工作（3）直接儲存器訪問方式（DMA方式）： A.以數據塊為單位、直接從設備到內存、在控制器的控制下不用經過CPU B.DMA控制器：三部分組成：DMA控制器與主機的接口、與設備的接口、I/O控制邏輯 含有4個寄存器：數據寄存器DR、控制/狀態寄存器C