第一篇：操作系統期末考試總結

第一章 操作系統概論

第一章主要內容

各節基本概念，操作系統的發展過程，操作系統的基本特征。

操作系統的目標

1.有效性

2、方便性

3、可擴充性4．開放性

分時系統實現中的關鍵問題

(1)及時接收(2)及時處理

主要特征1.多路性2.獨占性3.及時性4.交互性

實時操作系統按其用途的不同可分為兩種類型：實時控制系統和實時信息處理系統 3．實時系統與分時系統特征的比較

(1)多路性。實時信息處理系統也按分時原則為多個終端用戶服務。實時控制系統的多路性則主要表現在系統周期性地對多路現場信息進行采集，以及對多個對象或多個執行機構進行控制。而分時系統中的多路性則與用戶情況有關，時多時少。

(2)獨立性。實時信息處理系統中的每個終端用戶在向實時系統提出服務請求時，是彼此獨立地操作，互不干擾；而實時控制系統中，對信息的采集和對對象的控制也都是彼此互不干擾。(3)及時性。實時信息處理系統對實時性的要求與分時系統類似，都是以人所能接受的等待時間來確定的；而實時控制系統的及時性，則是以控制對象所要求的開始截止時間或完成截止時間來確定的，一般為秒級到毫秒級，甚至有的要低于100微秒。

(4)交互性。實時信息處理系統雖然也具有交互性，但這里人與系統的交互僅限于訪問系統中某些特定的專用服務程序。它不像分時系統那樣能向終端用戶提供數據處理和資源共享等服務。(5)可靠性。分時系統雖然也要求系統可靠，但相比之下，實時系統則要求系統具有高度的可靠性。因為任何差錯都可能帶來巨大的經濟損失，甚至是無法預料的災難性后果，所以在實時系統中，往往都采取了多級容錯措施來保障系統的安全性及數據的安全性。

操作系統的特征

（1）共享性

從資源使用的角度來講，所謂共享性是指操作系統程序與多個用戶程序共同使用系統中的各種資源。

? 互斥共享方式 ? 同時訪問方式

（2）虛擬性

指把一個物理上的實體，變為若干個邏輯上的對應物。前者是實際存在的；而后者是虛的，只是用戶的一種感覺。

? 時分復用：虛擬處理機

? 空分復用：虛擬磁盤、虛擬I/O設備、虛擬存儲器

（3）并發性：

是指兩個或多個事件在同一時間間隔內發生。在多道程序環境下，并發性是指宏觀上在一段時間內有多道程序在同時運行。但在單處理機系統中，每一時刻僅能執行一道程序，故微觀上這些程序是在處理機上交替執行。

? ? ? 與并行的區別 進程 線程

（4）異步性(不確定性）

指在多道程序環境下，程序以異步方式執行。即每道程序在何時執行、各自執行的順序、完成每道程序所需要的時間都是不確定的，也是不可預知的。

并發 和 共享 是操作系統的兩個最基本的特征。5 大管理功能 1.處理機管理

(1)進程控制

2.存儲管理

(1)內存分配

3.設備管理

(1)設備分配

4.文件管理（軟件資源管理）

(1)文件存儲空間的管理

5．作業管理(用戶接口)

(1)命令接口提供一組命令供用戶直接或間接控制自己的作業；

(2)程序接口提供一組系統調用供用戶應用程序和其他系統程序調用操作系統的功能。

(2)目錄管理

(3)文件保護

(4)文件操作管理

(2)設備處理

(3)緩沖管理

(2)存儲保護

(3)存儲擴充

(4)地址映射

(2)進程調度

(3)進程同步

(4)進程通信

總結：

計算機操作系統是方便用戶使用，管理和控制計算機軟硬件資源的系統軟件。

目前操作系統有六大類型:批處理系統、分時系統、實時系統、單用戶系統、網絡系統和分布式系統。

五大管理功能:處理機管理、存儲管理、設備管理、文件管理和作業管理(用戶接口)。

四大特性:并發性、共享性、虛擬性和異步性。

操作系統的最主要設計目標有兩個：

1)向用戶提供方便、簡單的使用計算機的環境；

2)使計算機系統能高效地工作，提高系統資源的利用

第二章主要內容（重點）

2.1 進程的基本概念 2.2 進程控制 2.3 進程同步

2.4 經典進程的同步問題

以上各節講過的內容，重點是進程的基本狀態及轉換、信號量的原理和應用、進程同步和互斥。

第二章 進程管理

4.2.1 程序的裝入

1.絕對裝入方式(Absolute Loading Mode)

從R開始

2.可重定位裝入方式(Relocation Loading Mode)

從0開始

3.動態運行時裝入方式(Denamle Run-time Loading)重定位不在裝入內存時進行，在真正執行程序時執行

4.2.2 程序的鏈接

1.靜態鏈接方式(Static Linking)

2.裝入時動態鏈接(Load-time Dynamic Linking)

裝入時動態鏈接方式有以下優點：(1)便于修改和更新。(2)便于實現對目標模塊的共享。

3.運行時動態鏈接(Run-time Dynamic Linking)4.3 連續分配方式 4.3.1 單一連續分配

單用戶、單任務

? ? ? 存在內碎片問題

優點：易于實現，開銷小。缺點：

– –

? ? ? ? ? 內碎片造成浪費

分區總數固定，限制了并發執行的程序數目。4.3.2

固定分區分配

可以和覆蓋、交換技術配合使用。

采用的數據結構：分區表－－記錄分區的大小和使用情況

動態創建分區：在裝入程序時按其初始要求分配，或在其執行過程中通過系統調用進行分配或改變分區大小。優點：沒有內碎片。缺點：有外碎片。4.3.3 動態分區(dynamic partitioning)

1.分區分配中的數據結構

(1)空閑分區表(2)

空閑分區鏈。2.分區分配算法

(1)首次適應算法(first fit)

(2)循環首次適應算法(next fit)，該算法是由首次適應算法演變而成的。從上次分配的分區起查找

(3)最佳適應算法(best fit)。(4)最壞適應算法(worst fit)

(5)快速適應算法(quick fit)根據其容量大小進行分類

? 分區分配算法：尋找某個空閑分區，其大小需大于或等于程序的要求。若是大于要求，則將該分區分割成兩個分區，其中一個分區為要求的大小并標記為“占用”，而另一個分區為余下部分并標記為“空閑”。分區的先后次序通常是從內存低端到高端。? 分區釋放算法：需要將相鄰的空閑分區合并成一個空閑分區。(這時要解決的問題是：合并條件的判斷和合并時機的選擇)

內存回收時的情況

4.3.6 可重定位分區分配 1.動態重定位的引入

? ? ? 緊縮（或拼湊）可重定位分區法

緊縮時機

1釋放所占分區時

2分配進程分區時

4.3.7 對換(Swapping)

3.進程的換出與換入

阻塞狀態且優先級最低

換出時間(換出到磁盤上)最久的進程

4.4.3 兩級和多級頁表

4.5.2 分段系統的基本原理

段號 段內地址

例子

段式存儲管理中供用戶使用的邏輯地址為24位，其中段內地址占用16位 用戶程序最多可以分為多少段？2^8

當把用戶程序裝入內存時，每段占用內存的最大連續區為多少字節？2^16

4.6 虛擬存儲器的基本概念

4.6.1 虛擬存儲器的引入

1.常規存儲器管理方式的特征

(1)一次性。(2)駐留性。

2.虛擬內存可行性基礎：局部性原理

3.虛擬存儲器定義

：請求調入功能和置換功能

4.6.2 虛擬存儲器的實現方法

1.分頁請求系統

(1)硬件支持

① 請求分頁的頁表機制 ② 缺頁中斷機構

(2)實現請求分頁的軟件 4.6.3 虛擬存儲器的特征

多次性

對換性 虛擬性 離散性

③ 地址變換機構

最本質的特征：離散性；最重要的特征：虛擬性。

2.缺頁中斷機構

4.7.2 內存分配策略和分配算法

1.最小物理塊數的確定

2.物理塊的分配策略

內存分配策略－－即固定和可變分配策略。置換－－即全局置換和局部置換。

1)固定分配局部置換(Fixed Allocation, Local Replacement)

2)可變分配全局置換(Variable Allocation, Global Replacement)

3)可變分配局部置換(Variable Allocation, Local Replacemen 3.物理塊分配算法

1)平均分配算法

2)按比例分配算法

物理塊數b=(s/S)*m

m為物理塊總數 s頁面數 3)考慮優先權的分配算法 4.8 頁面置換算法

1.最佳置換算法（Optimal Replacement, OPT）：將來不被使用，或者是在最遠的將來才被訪問

2.先進先出(FIFO)頁面置換算法：總是淘汰在內存中停留時間最長（年齡最老）的一頁

? ? 優點：容易理解，方便程序設計。缺點：

●性能并不很好，效率不高

●存在Belady異常現象，即缺頁率隨內存塊增加而增加

4.8.2 最近最久未使用(LRU)置換算法：最近一段時間里最久沒有使用過的頁面予以淘汰。

LRU置換算法的硬件支持

47071******074112074

221074662107

1)寄存器

2)特殊棧

4.8.3 Clock置換算法

2.改進型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(A=0, M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0, M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1, M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=1, M=1): 最近已被訪問且被修改，該頁可能再被訪問。

其執行過程可分成以下三步

(1)從指針所指示的當前位置開始，掃描循環隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。

(2)如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。

(3)如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復0。然后重復第一步，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁。

4.8.4 其它置換算法

1.最少使用(LFU： Least Frequently Used)置換算法

選擇在最近時期使用最少的頁面作為淘汰頁。

2.頁面緩沖算法(PBA： Page Buffering Algorithm)兩個鏈表：空閑鏈表、已修改頁面的鏈表 4.9 請求分段存儲管理方式 4.9.1 請求分段中的硬件支持

1.段表機制2.缺段中斷機構3.地址變換機構

4.9.2 分段的共享與保護

1.共享段表

2.共享段的分配與回收 ：對第一個請求使用該共享段的進程，由系統為該共享段分配一物理區始址填入段表把count置為1 1)共享段的分配

2)共享段的回收：count∶=count-1 3.分段保護

1)越界檢查

2)存取控制檢查

? ? ?

? ? ? 只讀

只執行

讀/寫

3)環保護機構

一個程序可以訪問駐留在相同環或較低特權環中的數據。

一個程序可以調用駐留在相同環或較高特權環中的服務。

5.6.2 磁盤調度

1．先來先服務(FCFS)

2．最短尋道時間優先(SSTF):

每次的尋道時間最短

(從100#磁道開始，向磁道號增加方向訪問)被訪問的下 移動距離 一個磁道號(磁道數)150 50 160 10 184 24 90 94 58 32 55 3 39 16 38 1 18 20平均尋道長度：27.8(從100#磁道開始，向磁道號增加方向訪問)被訪問的下 移動距離 一個磁道號(磁道數)150 50 160 10 184 24 18 166 38 20 39 1 55 16 58 3 90 32平均尋道長度: 35.8

4．循環掃描(CSCAN)算法:CSCAN算法規定磁頭單向移動

第六章主要內容

6.1 文件和文件系統 6.2 文件的邏輯結構 6.3 外存分配方式 6.4 目錄管理

6.5 文件存儲空間的管理

以上各節講過的內容，重點是文件的邏輯結構、物理結構、目錄管理、存儲空間管理的方法 6.1 文件與文件系統

文件說明1）文件類型。2）文件長度。3）文件的位置。4）文件的存取控制。5）文件的建立時間

文件的分類

按文件用途：1.系統文件 2.用戶文件 3.庫文件 按數據形式：1.源文件 2.目標文件 3.可執行文件 按操作保護：1.只讀文件 2.讀寫文件3.執行文件 按文件性質：1.普通文件 2.目錄文件 3.特殊文件

4、文件的操作(文件接口）

（1）創建文件。（2）刪除文件。（3）打開文件（4）讀文件（5）寫文件（6）關閉文件 文件的邏輯結構：用戶關心：文件內容或記錄 1．有結構的文件(記錄型文件）

定長記錄型

變長記錄型 2．無結構文件（流式文件）

文件的物理結構：系統關心：文件存儲、提取 1．連續文件2.鏈接文件3．索引文件

記錄星文件的組織方式：1.順序文件 2 索引文件 3.索引順序文件

1、順序文件

1）分：串結構、順序結構

2）讀/寫操作

3）優

適合批量存取

缺點

不適合交互應用，記錄的刪改

2、索引文件

優：速度缺：存儲空間

3、索引順序文件

1）讀/寫操作

2）優點：折中

比較檢索效率 記錄個數N 順序文件N/2 索引順序文件 根號2

6.3.3 FAT和NTFS技術

計算以盤塊為分配單位時，所允許的最大磁盤容量。

? 一個FAT表所能描述的最大容量=最多允許表項數*盤塊大小 ? 最大磁盤容量 =一個FAT表所能描述的最大容量*卷的個數

=最多允許表項數*盤塊大小*卷的個數 故：FAT12 最大磁盤容量=212*29*4=8*220（8M）

引入一個新的分配單位——簇

問題:造成簇內零頭

6.4 文件目錄

文件目錄項（FCB）：一般情形下包括三類信息：1）基本信息2）存取控制信息3）使用信息類

目錄結構 單級目錄結構

缺點:(1)查找速度慢。(2)不允許重名。(3)不便于實現文件共享。

二級目錄結構優點：

(1)提高了檢索目錄的速度。

(2)在不同的用戶目錄中，可以使用相同的文件名。(3)不同用戶還可使用不同的文件名來訪問系統中的 同一個共享文件

多級目錄結構

1）樹型目錄結構2)路徑名

3)當前目錄(Current Directory)1.相對路徑名(relative path name)2.絕對路徑名(absolute path name)從根開始 6.4.3 目錄查詢技術 1．線性檢索法

線性檢索法又稱為順序檢索法。

根目錄結點6是132號盤塊是/usr的目錄/usr的目錄

1·6·

1· ·1· ·

bin 419dick 7dev132 30erik14lib

51jimetc 9 626astusr

tmp45bal 8 在結點6中查找usr字段

2．Hash方法

結點26是/usr/ast的目錄496號盤塊是/usr/ast的目錄26664·· ·grantsbooksmboxminiksrc49692608117對于使用了通配符的文件名，系統便無法利用Hash方法檢索目錄。

在進行文件名的轉換時，有可能把n個不同的文件名轉換為相同的Hash值，即出現了所謂的“沖突”。

6.5.1空閑表法和空閑鏈表法

1．空閑表法

空閑表法屬于連續分配方式

2、空閑塊（區）鏈

空閑鏈表法是將所有空閑盤區拉成一條空閑鏈

6.5.2．位示圖

對應物理塊：b=n*i+j（1，7）→16*1+7=23 6.5.3．成組鏈接法

第二篇：鄭州大學操作系統期末考試重點整理

操作系統是管理系統資源、控制程序執行、改善人機界面、提供各種服務、合理組織計算機工作流程和為用戶有效使用計算機提供良好運行環境的一種系統軟件。

資源管理1資源復用(空分復用共享，時分復用共享)2資源虛化3資源抽象4組合使用抽象和虛化技術

1）進程抽象（2）虛存抽象（3）文件抽象（4）其他資源抽象

操作系統的作用:（1）OS作為用戶接口和公共服務程序：（2）OS作為擴展計算機或者虛擬計算機（2）OS作為資源的管理者和控制者（4）OS作為程序執行的控制著和管理者 從資源管理的角度，看操作系統具有六項主要功能：處理器管理，存儲管理，設備管理，文件管理，網絡與通信管理，用戶接口

操作系統的主要特性：并發性，共享性，異步性 并發性：指兩個或兩個以上事件或活動在同一時間間隔內發生。

并行性：指兩個或兩個以上事件或活動在同一時刻發生。關系：并行活動一定是并發的，反之并發活動未必是并行的，并行性是并發性的特例，并發性是并行性的擴展。共享性：指操作系統中的資源可被多個并發執行的進程共同使用，而不是被其中某一個程序所獨占。

1，透明資源共享：必須妥善解決的問題有資源隔離，授權訪問2，顯式資源共享：獨占資源是指同一時間段內只允許一個進程訪問的資源

異步性：由計算機系統中的資源有限而進程眾多，每個進程的執行并非連貫的，而是以“走走停停”的方式向前推進。多道程序設計是指允許多個程序同時進入一個計算機系統的主存儲器并啟動進行交替計算的方法。從宏觀上看，多道程序并發運行，它們都處于運行過程中，但都未運行結束。從微觀上看，多道程序的執行是串行的，各道程序輪流占用CPU，交替地執行。1，提高CPU、主存和設備的利用率，2，提高系統的吞吐率，是單位時間內完成的作業數增加。3充分發揮計算機系統部件的并行性 操作系統可分為三種基本類型： 批處理操作系統 分時操作系統.實時操作系統

通用操作系統：如果某個操作系統兼具批處理、分時、實時處理的全部或兩種功能，則為通用OS

操作系統為用戶提供兩種調用其服務和功能的接口:程序接口：允許運行程序調用操作系統的服務和功能。許多操作系統的程序接口由一組系統調用（System Call)）組成，用戶程序使用“系統調用”就可獲得操作系統的底層服務，使用或訪問系統的各種軟硬件資源。操作接口：操作系統為用戶提供的操作控制計算機工作和提供服務手段的集合，通常有操作控制命令、圖形操作界面、以及批處理系統提供的作業控制語言等實現手段。內核是一組程序模塊，作為可信軟件來支持進程并發執行的基本功能和基本操作，通常駐留在內核空間，運行于核心態，具有訪問硬件設備和所有主存空間的權限，是僅有的能執行特權指令的程序。分類可分為微內核和單內核兩種類型。功能1）資源抽象2）資源分配3）資源共享。

屬性1）內核是由中斷驅動的2）內核的執行是連續的3）內核在屏蔽中斷狀態下執行4）內核可以使用特權指令。從操作系統的運行方式來看，可分成：獨立運行的內核模型、在應用進程內執行的模型和作為獨立進程運行的模型。處理器流可以分作以下四類：單指令流單數據流（SISD）：傳統的計算機系統。單指令流多數據流（SIMD）和多指令流多數據流（MIMD）都屬于并行計算機！多指令流單數據流（MISD）：在研究中

處理器現場：處理器包括一組寄存器，用于存放數據、變量和中間結果，這組寄存器所存儲的信息與程序的執行有很大關系，構成了處理器現場。

特權指令是指只能提供給操作系統的核心程序使用的指令，如啟動I/O設備、設置時鐘、控制中斷屏蔽位、清內存、建立存儲鍵，加載PSW（程序狀態字）等。

非特權指令：指供應用程序使用的、權限較低的指令。處理器狀態分類：核心狀態和用戶狀態。

核心態具體的權限有：1，CPUU運行可信軟件2，硬件執行全部機器指令3，可以訪問所有內存單元和系統資源4，具體改變處理器狀態的能力。

用戶態具有的權限有：1，CPU運行非可信軟件2，程序無法執行特權指令3，訪問權限僅限于當前進程的地址空間4，不具有改變處理器狀態的能力 處理器狀態之間的轉換：(1)用戶狀態向核心狀態的轉換：一是程序請求操作系統服務，執行一條系統調用；二是程序運行時，產生了一個中斷（或者異常）事件，運行程序被中斷，讓中斷處理程序工作。這兩種情況都是通過中斷機構發生的。中斷（異常）是用戶態到核心態轉換的唯一途徑。(2)核心狀態向用戶狀態的轉換 ：每臺計算機通常會提供一條特權指令稱作加載程序狀態字LPSW（Load PSW），用來實現操作系統向用戶程序的轉換。加載程序狀態字指令的作用：把哪個程序的程序狀態字加載到程序狀態字寄存器中，就意味著該程序獲得CPU控制權執行。

中斷是指程序執行過程中，遇到急需處理的某個事件時，暫時中止CPU上現行程序的運行，轉而執行相應的事件處理程序執行的過程，待處理完畢之后再返回斷點（繼續執行）或者調度其他程序執行。中斷源是引起中斷的事件。中斷裝置是發現中斷源并產生中斷的硬件。

中斷源分類：1.從中斷事件的性質和激活的手段來分，可以分成兩類：強迫性中斷事件和自愿性中斷事件。2按照中斷信號的來源和實現手段來分：可分為硬中斷和軟中斷兩類。硬中斷可以分為外中斷和內中斷。

中斷/異常響應需要順序執行的四個步驟： 發現中斷源，保護現場，轉向中斷/異常事件的處理程序，恢復現場。

進程(process)是一個可并發執行的具有獨立功能的程序關于某個數據集合的一次執行過程，也是操作系統進行資源分配和保護的基本單位。

進程的屬性(進程與程序比較)：(1)結構性(2)共享性(3)動態性(4)獨立性(5)制約性(6)并發性 三態模型：運行態，就緒態，等待態

五態模型：新建態，終止態，運行態，就緒態，等待態 進程映像的組成進程組成主要包括：進程控制塊，進程程序塊，進程核心棧，進程數據塊

進程控制塊三類信息：標識信息、現場信息、控制信息允許發生進程上下文切換的四種情況 ：(1)當進程進入等待態時；(2)當進程完成其系統調用返回用戶態，但不是最有資格獲得CPU時；(3)當內核完成中斷處理，進程返回用戶態但不是最有資格獲得CPU時；(4)當進程執行結束時。模式切換和進程切換的聯系與區別：1，模式切換不一定會引起進程狀態的轉換，也不一定引起進程切換。,2，在完成系統調用服務或者中斷處理之后，可通過模式切換來恢復被中斷進程的運行。

進程控制原語：1.進程創建 2.進程的撤銷 3.進程的阻塞和喚醒 4.進程的掛起和激活

線程的實現分三類：1，用戶級線程2內核級線程 3混合式線程

處理器調度可分為三個級別：高級調度、中級調度和低級調度

作業和進程的關系： ?作業是任務實體，進程是完成任務的執行實體；沒有作業任務，進程無事可干，沒有進程，作業任務沒法完成。?作業概念更多地用在批處理操作系統，而進程則可以用在各種多道程序設計系統

資源競爭產生兩個控制問題：一個是死鎖(Deadlock)問題，就是一組進程如果都獲得了部分資源，還想要得到其他進程所占用的資源，最終所有進程都將陷入死鎖。一個是饑餓(Starvation)問題，是指一個進程由于其它進程總是優先于它而被無限期拖延。既要解決饑餓問題，又要解決死鎖問題。解決饑餓問題的最簡單策略是FCFS資源分配策略。

臨界區的調度原則 :一次至多允許一個進程進入臨界區內；一個進程不能無限地停留在臨界區內；一個進程不能無限地等待進入臨界區；

管程：屬性共享性：安全性：互斥性： 進程通信分類：1）信號（signal）通信機制；2）管道（pipeline）通信機制；3）消息傳遞(message passing)通信機制；4）信號量（semaphore）通信機制5）共享主存（shared memory）通信機制

死鎖的定義:如果在一個進程集合中的每個進程都在等待只能由該集合中的其他一個進程才能引發的事件，而無限期陷入僵持的局面稱為（這一組進程）發生了死鎖。

產生死鎖的因素:系統擁有的資源數量。與資源分配策略。進程對資源的使用。并發進程的推進順序。

產生死鎖的四個必要條件：互斥條件：進程互斥使用資源。占有和等待條件(部分分配條件)：進程在請求資源得不到滿足而等待時，不釋放已占有資源。不剝奪條件：已占有的資源只能由屬主釋放，不允許其他進程強制剝奪。循環等待條件(環路條件)：存在一組循環等待鏈，其中每一個進程都在鏈中等待下一個進程所持有的資源，造成種族進程處于永遠等待狀態。

文件系統是操作系統中負責存取和管理信息的模塊，文件不但反映了用戶概念中的邏輯結構，而且和存放它的輔助存儲器的存儲結構緊密相關。一個文件必須從邏輯文件和物理文件兩個側面來觀察它。邏輯結構，即記錄及其邏輯關系，數據獨立于物理環境； 物理結構，數據被文件系統按照某種規則排列和存放到物理存儲介質上。

順序存取:按記錄順序進行讀/寫操作的存取方法.主要用于磁帶文件以及磁盤上的順序文件.直接存取:以任意次序直接讀寫某個記錄.用戶提供相對塊號給操作系統,絕對塊號由系統換算得到.索引存取:文件專門有一個按記錄關鍵字有序的索引表,用戶通過查找索引表定位并讀出記錄.文件系統給每個文件建立唯一的管理數據結構，即文件控制塊（FCB），也叫文件目錄項。

文件目錄的基本功能是將文件名轉變成此文件信息在磁盤上的物理位置。為了加快文件的查找速度，通常把ＦＣＢ集中起來進行管理，組成文件目錄。

目錄中的文件名和管理信息分開，后者單獨組成數據結構，稱索引節點（i-node）

塊是存儲介質上連續信息所組成的一個區域，也叫做物理記錄。塊是主存儲器和輔助存儲設備進行信息交換的物理單位，每次總是交換一塊或整數塊信息

文件的邏輯結構分兩種形式：流式文件，記錄式文件 流式文件指文件內的數據不再組成記錄，只是依次的一串信息集合，可以看成是只有一個記錄的記錄式文件 記錄式文件是一種有結構的文件,包含若干邏輯記錄，邏輯記錄是文件中按信息在邏輯上的獨立含意劃分的信息單位。順序文件(連續文件)一個文件中邏輯上連續的信息存放到存儲介質的依次相鄰的塊上便形成順序文件。連接文件使用連接字，又叫指針來表示文件中各個記錄之間的關系.第一塊文件信息的物理地址由文件目錄給出,每一塊的連接字指出文件下一個物理塊位置

直接文件(哈希文件)記錄的關鍵字與其地址間可通過某種方式建立對應關系，利用這種關系實現存取的文件叫直接文件。

索引文件的優點:不要求物理塊連續,便于直接存取,便于文件 的增、刪、改。缺點:增加了索引表的空間開銷和查找時間.文件的靜態共享：允許一個文件同時屬于多個目錄，但實際上文件僅有一處物理存儲，這種文件在物理上一處存儲，從多個目錄可到達該文件的結構稱為文件鏈接。要實現靜態鏈接，只要不同目錄的索引結點i-node號，指定為同一文件的索引結點即可。文件的動態共享：是系統中不同的用戶進程或同一用戶的不同進程并發地訪問同一文件。共享關系只有當用戶進程存在時才可能出現，一旦用戶的進程消亡，其共享關系也就自動消失。

外圍設備分為兩類:存儲型設備和輸入輸出型設備.I/O系統：I/O設備及其接口線路、控制部件、通道和管理軟件的總稱。I/O設備可以劃分為輸入型、輸出型和存儲型外圍設備三類。按照I/O信息交換的單位, I/O設備可分為字符設備和塊設備。

存儲型外圍設備可以劃分為順序存取存儲設備和直接存取存儲設備。順序存取存儲設備嚴格依賴信息的物理位置進行

定位和讀寫，如磁帶機。直接存取存儲設備的特點是存取任何一個物理塊所需的時間幾乎不依賴于此信息的位置，如磁盤。

I/O設備的4種控制方式分類：輪詢方式：輪詢方式又稱程序直接控制方式，特點：CPU不停測試設備狀態，直到設備準備就緒，開始傳輸數據；中斷方式：啟動I/O后，不必查詢I/O是否就緒，繼續執行現行程序。特點：不需要CPU做忙式測試，直到設備準備就緒之后產生中斷。DMA方式：I/O設備能直接與主存交換數據而不占用CPU,其利用率還可提高。特點：負責數據的交換，CPU不必參與；從設備讀數據，存入緩沖寄存器，這個過程與CPU無關；與內存交換數據時，是一次交換一塊數據；與內存進行數據交換時，需要搶占內存總線（周期竊取），此時CPU必須等待。通道方式：為獲得CPU和外圍設備間更高的并行工作能力,引入了自成獨立體系的通道結構。特點：通道負責管理設備與內存之間的數據傳送的一切工作；數據傳輸完畢后，產生中斷，CPU執行中斷處理；數據傳輸中如果出錯，產生中斷，CPU執行中斷處理。

I/O設備設備控制器或適配器，機械部件則是設備本身。操作系統基本上與控制器打交道，而非設備本身。I/O軟件總體設計目標:高效率。通用性。I/O軟件組織成四個層次: I/O中斷處理程序。設備驅動程序。與設備無關的操作系統I/O軟件。用戶層I/O軟件.籠統地說，設備驅動程序的功能是從獨立于設備的軟件中接收并執行 I/O請求。設備驅動程序主要包括三部分功能：1設備初始化2執行設備驅動例程3執行中斷處理例程。SPOOLing又稱為假脫機操作.Spooling技術就是利用一類物理設備模擬另一類物理設備的技術,是使獨占使用的設備變成可共享設備的技術.為什么需要緩沖技術？改善中央處理器與外圍設備之間速度不匹配的矛盾，協調邏輯記錄大小與物理記錄大小不一致，提高CPU和I/O設備的并行性。

提高磁盤I/O速度的方法:提前讀:在讀當前塊的同時，將下一個盤塊中的數據也讀入緩沖區。延遲寫:本應寫回磁盤的緩沖區中的數據不久之后可能還會再被訪問，因而不立即將其寫回磁盤。虛擬盤:利用內存空間仿真磁盤，又稱為RAM盤。虛擬盤中的數據在掉電或系統重啟動以及發生故障時會丟失。

設備獨立性帶來的好處:用戶與物理的外圍設備無關，系統增減或變更外圍設備時程序不必修改；易于對付輸入輸出設備的故障。

為了存放從輸入設備輸入的信息以及作業執行的結果,系統在磁盤上開辟兩個大的存儲空間,稱為井.存儲器的層次：寄存器、高速緩存、主存儲器，磁盤，磁帶。內存是程序運行的主要場所，是進程映像（進程實體）存在的主要位置。

把程序和數據的邏輯地址轉換為物理地址的工作稱為地址轉換或重定位.一種方式是在程序裝入時根據程序所裝入的內存位置由裝入程序依據重定位信息一次性將程序中所有的邏輯地址都轉變為物理地址，稱為靜態重定位，不允許程序在內存中移動位置。另一種方式是在程序執行過程中，地址轉換工作穿插在指令執行的過程中，每執行一條指令，CPU對指令中涉及的邏輯地址進行轉換，稱為動態重定位，允許程序在內存中移動位置。動態重定位必須借助于硬件的地址轉換機構實現。

頁框：物理地址分成大小相等的許多區域，每個區域叫做一塊（或者一個頁框page frame）。

頁面：邏輯地址分成大小相等的區域，每個區域的大小與塊的大小相等，叫做一個頁面（page）。

邏輯地址形式：分頁式存儲器的邏輯地址由兩部分組成：頁號和單元號(頁內位移)。頁表：操作系統需為每個作業建立一張頁表,該表登記該作業的頁號—物理塊號對應信息,系統通過頁表可以準確訪問內存中屬于一個作業的所有頁面.所以頁表實際上用于完成地址變換.虛擬存儲器的定義：在具有層次結構存儲器的計算機系統中，采用自動實現部分裝入和部分對換功能，為用戶提供一個比物理內存容量大得多的，可尋址的一種“內存儲器”。假定作業p共計n頁，系統分配給它的主存塊只有m塊（１≤m≤n）。如果作業p在運行中成功的訪問次數為s，不成功的訪問次數為F，則總的訪問次數Ａ為：A = S + F又定義：f = F / A稱f為缺頁中斷率。影響缺頁中斷率f的因素有：1)主存頁框數。2)頁面大小。3)頁面替換算法。4)程序特性。最佳頁面算法(OPT)、先進先出頁面淘汰算法(FIFO)、最近最久未使用頁面淘汰算法(LRU)、外圍設備分為兩類:存儲型設備和輸入輸出型設備。設備管理具有以下功能1外圍設備中斷處理。2緩沖區管理。3外圍設備的分配 4外圍設備驅動調度。5虛擬設備及其實現 存儲型外圍設備可以劃分為順序存取存儲設備和直接存取存儲設備。順序存取存儲設備嚴格依賴信息的物理位置進行定位和讀寫，如磁帶機直接存取存儲設備的特點是存取任何一個物理塊所需的時間幾乎不依賴于此信息的位置，如磁盤。

有三個并發進程：R 負責從輸入設備讀入信息塊，M 負責對信息塊加工處理；P 負責打印輸出信息塊。今提供； l）一個緩沖區，可放置K 個信息塊； 2）二個緩沖區，每個可放置K 個信息塊； 試用信號量和P、V 操作寫出三個進程正確工作的流程。答：1 一個緩沖區：cobegin

Semaphore sread,smanager,sprint;item a[K];int rr,rm,rp;item x;

sread=k;smanager=0;sprint=0;rr=rm=rp=0;process PR()

{while(true){ P(sread);a[rr]=x;

rr=(rr+1)%K;V(smanager);} }

process PM()

{ while(true){ P(smanager);x=a[rm];rr=(rr+1)%K;V(sprint);} } process PP()

{while(true){ P(sprint);x=a[rp];

rr=(rr+1)%K;V(sread);} } Coend

(2）兩個緩沖區：

semaphore swrite1, sread1, swrite2, sread2;Swrite1=swrite2=1;sread1 =sread2=0;

item A1[k],A2[k];read1=write1=read2=write2=0;cobegin

process PR { while(true){ P(swrite1);A1[write1]=x;

write1=(write1+1)%K;

V(sread1);} }process PM { while(true)

{ P(sread1);

x=A1[read1];

read1=(read1+1)%K;

V(swrite1);P(swrite2)

A2[write2]=x;

write2=(write+1)%K;V(sread2);}}process PP { while(true)

{ P(sread2);x=A2[read2];

read2=(read2+1)%K;V(swrite2);}}coend

設公共汽車上，司機和售票員的活動分別如下：司機的活動：啟動車輛：正常行車；到站停車。售票員的活動：關車門；售票；開車門。在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關系？用信號量和P、V 操作實現它們的同步。

答：在汽車行駛過程中，司機活動與售票員活動之間的同步關系為：售票員關車門后，向司機發開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開門讓乘客上下車。因此，司機啟動車輛的動作必須與售票員關車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步。應設置兩個信號量：S1、S2;S1 表示是否允許司機啟動汽車（其初值為0);S2 表示是否允許售票員開門（其初值為0）。用P、v 原語描述如下：

var S1 , S2 : semaphore;S1=0；S2=0； cobegin{ driver();busman();}coenddriver()begin

while(1){ P(S1)

啟動車輛；正常行車；到站停車；V(S2);}end

busman()begin

while(1){ 關車門；V(51)售票;P(S2)開車門；上下乘客； }end

一條公路兩次橫跨運河，兩個運河橋相距100 米，均帶有閘門，以供船只通過運河橋。運河和公路的交通均是單方向的。運河上的運輸由駁船擔負。在一駁船接近吊橋A 時就拉汽笛警告，若橋上無車輛，吊橋就吊起，直到駁船尾P 通過此橋為止。對吊橋B 也按同樣次序處理。一般典型的駁船長度為200 米，當它在河上航行時是否會產生死鎖？若會，說明理由，請提出一個防止死鎖的辦法，并用信號量來實現駁船的同步。

答：當汽車或駁船未同時到達橋A 時，以任何次序前進不會產生死鎖。但假設汽車駛過了橋A，它在繼續前進，并且在駛過橋B 之前，此時有駁船并快速地通過了橋A，駁船頭到達橋B，這時會發生死鎖。因為若吊起吊橋B 讓駁船通過，則汽車無法通過橋B ；若不吊起吊橋B 讓汽車通過，則駁船無法通過橋B。可用兩個信號量同步車、船通過兩座橋的動作。var Sa , Sb : semaphore;Sa:=Sb:=1;cobegin

{ process 駁船 beginP(Sa);P(Sb);

船過橋A、B;V(Sa);V(Sb);end

process 汽車 beginP(Sa);P(Sb);

車過橋A、B;V(Sa);V(Sb);end }coend

假定磁盤有200 個柱面，編號O-199，當前存取臂的位置在143 號柱面上，并剛剛完成了125 號柱面的服務請求，如果請求隊列的先后順序是：86 , 147 , 91 , 177 , 94 , 150 , 102 , 175 , 130 ；試問：為完成上述請求，下列算法存取臂移動的總量是多少？并算出存取臂移動的順序。(1）先來先服務算法FCFS;

(2）最短查找時間優先算法SSTF :(3）掃描算法SCAN。(4）電梯調度。答：(l）先來先服務算法FCFS 為565，依次為143-86-147-91-177-94-150-102-175-130。(2）最短查找時間優先算法SSTF 為162，依次為143-147-150-130-102-94-91-86-175-177。(3）掃描算法SCAN 為169，依次為143-147-150-175-177-199-130-102-94-91-86。(4）電梯調度為125，依次為143-147-150-175-177-130-102-94-91-86。

先來先服務算法 FCFS策略：按照作業進入系統的先后次序來挑選作業，先進入系統的作業優先被挑選。這是一種非剝奪式算法。

最短作業優先算法SJF：以進入系統的作業所要求的CPU時間為標準，總選取估計計算時間最短的作業投入運行。這是一種非剝奪式調度算法 例： 作業所需CPU 9 作業作業作業作業

?SJF的作業調度順序為作業2、4、1、3，平均作業周轉時間T =(4+12+21+31)/4= 17

平均帶權作業周轉時間W=(4/4+12/8+21/9+31/10)/4 = 1.98 ?如果對它們施行FCFS調度算法，平均作業周轉時間T =(9+13+23+31)/4 = 19

平均帶權作業周轉時間W =(9/9+13/4+23/10+31/8)/4 = 2.51

最短剩余時間優先SRTF算法

把SJF算法改為搶占式的調度算法：當一個作業正在執行時，一個新作業進入就緒狀態，如果新作業需要的CPU時間比當前正在執行的作業剩余下來還需的CPU時間短，SRTF強行趕走當前正在執行作業 優先級調度算法

這種算法是根據確定的優先級來選取進程/線程，每次總是

選擇優先級最高的作業。

第三篇：操作系統總結

什么是OS，OS有哪幾個特征？其最基本的特征是什么？

答：操作系統是為了達到方便用戶和提高利用率的目的而設計的，控制和管理計算機硬件和軟件資源，合理的組織計算機工作流程的程序的集合它具有并發，共享，虛擬，異步性四個基本特征。其中最基本的特征為并發性

2什么是進程及與程序的區別與聯系，為什么PCB是進程存在的唯一標志？

進程是程序的一次執行過程，是系統進行資源分配和調度的一個獨立單位。

區別：（1）進程是動態的，程序是靜態的。（2）進程具有并發性，而程序沒有（3）進程是資源分配和處理機調度的獨立單位，其并發性受系統制約（4）一個程序多次執行，對應多個進程，不同的進程可以包含同一程序PCB：因為在進程的整個生命期中，系統總是通過PCB對進程進行控制的3處理機三級調度分別完成什么工作？

（1）高級調度：就是作業調度，用于決定把外存上處于后備隊列中的哪些作業調入內存，并為它們創建進程，分配必要的資源，然后，再將新創建的進程排在就緒隊列上，準備執行

（2）低級調度：就是進程調度，它決定就緒隊列中的哪個進程將獲得處理機，然后由分派程序執行把處理機分配給該進程的操作

（3）中級調度：實際上就是存儲器管理中的對換功能試說明引起進程調度的時機是什么？

（1）進程完畢（2）時間片用完（3）I/O請求發生某個事件（4）原語：wait操作，阻塞（5）高優先者進入 5什么是臨界資源和臨界區？

一次僅允許一個進程訪問的資源稱為臨界資源。訪問臨界資源的代碼段稱為臨街區

6試修改下面生產者---消費問題中，如果將兩個wait操作即wait(full)和wati(mutex)互換 位置，或者將signal(mutex)與signal(full)互換位置，結果會如何？

（1）wait(full)和wait(mutex)互換位置后，因為mutex在這兒是全局變量，執行完wait(mutex)，則mutex賦值為0，倘若full 也為0，則該生產者進程就會轉入進程鏈表進行等待，而生產者進程會因全局變量mutex為0 而進行等待，使full 始終為0，這樣就形成了死鎖.（2）而signal(mutex)與signal(full)互換位置后，從邏輯上來說應該是一樣的.7什么是死鎖?死鎖產生的有哪些

死鎖是因多個進程因競爭資源而造成的一種僵局（1）互斥條件：一個資源每次只能被一個進程使用。（2）請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。

（3）不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。（4）環路等待條件:若干進程之間形成一種頭尾相接的循環等待資源關系。同步機制應遵循的基本準則是什么?

(1)空閑讓進（2）忙則等待（3）有限等待（4）讓權等待.程序有幾種連接方式

（1）靜態鏈接方式（2）裝入時動態鏈接（3）運行時動態鏈接

10什么是動態重定位方式及為什么要引入動態重定位方式及如何實現？

程序和數據裝入內存時需對目標程序中的地址進行修改。這種把邏輯地址轉變為內存的物理地址的過程叫重定位

11什么是分頁，什么是分段，在存儲管理中兩者的區別

（1）分頁是將一個進程的邏輯地址空間分成若干大小相等的部分，每一部分稱作頁面，內存劃分成與頁面大小相等的物理塊，進程的任何一頁可放入內存的任何一個物理塊中,段是信息的邏輯單位，含有一組意義相對完整的信息，更好的來滿足用戶的需要。

（2）分段是一組邏輯信息的集合，即一個作業中相對獨立的部分。多個段在內存中占有離

散的內存單元，對每個段，在內存占有一連續的內存空間，其內存的分配與回收同可變分區的內存分配與回收辦法

分頁與分段的主要區別是？

（1）頁是信息的物理單位，分頁是為了實現離散分配方式，以消減內存的外零頭，提高內存的利用率（2）頁的大小固定，并且有系統決定，而段的長度不固定決定于用戶所編寫的程序（3）分頁作業的地址空間是一維的，段是二維的。

12動態分區存儲管理中內存的回收方式

13.什么是對換，對換的分類及主要用途在進程換出時應遵循什么原則

對換是把內存中暫時不能運行的進程或者暫時不用的程序和數據調出到外存上，以便騰出足夠的內存空間，再把因具備運行條件的進程或者進程所需要的程序或數據調入內存。

分類：（1）整體對換（進程對換）：以整個進程為單位（2）頁面對換（分段對換/部分對換）：以頁和段為單位

規則：內存空間不夠用才換出。系統處于阻塞狀態，且優先級最低的進程最先換出。若換入：系統處于就緒狀態，且優先級最高的進程最先換入，直至無可換入的進程為止。

14.什么是虛擬存儲器虛擬存儲器具有哪些特性，最基本的特性是什么？虛擬存儲器的容量受哪兩方面的限制？

虛擬存儲器：是指具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統。

特征：（1）離散性（最基本的特征）（2）多次性（3）對換性（4）虛擬性

虛擬存儲器的容量主要受指令中表示地址的字長和外存的容量的限制。

15.在沒有快表的分頁存儲管理中取一條指令需訪問幾次內存及訪問內存的目的，及具有快表的分頁存儲管理系統的地址變換過程。

兩次。第一次：訪問內存中的頁表，從中找到頁的物理塊號，再將塊號與頁內偏移量W拼接，形成物理地址。第二次：從第一次所得的物理地址中獲得所需數據

地址變換過程：CPU給出有效地址后，地址變換機構將頁號與快表中的所有頁號進行比較，若有與此相匹配的頁號，則表示所訪問的頁在快表中，從中讀出物理塊號與頁內地址相拼接，得到物理地址；若訪問的頁不在快表中，則要訪問在內存中的頁表，從頁表中讀出物理塊號與頁內地址相拼接，得到物理地址，同時，還應將此頁表項寫入快表中，若此時快表已滿，則OS必須找到一個老的并且被認為不再需要的頁表項將它換出。

16.什么是緊湊技術及為什么要引入

緊湊：把原來多個分散的小分區拼接成一個大分區的方法

引入：提高內存的利用率，讓大容量的作業可以裝入并且減少零頭或碎片

17程序的局部性原理是什么局限性的兩個主要表現方面

局部性原理：（1）程序執行時，除少部分轉移和過程調用指令外，大多數條件下任是順序執行的（2）過程調用將會使程序的執行軌跡由一部分區域轉至另一部分區域，但經驗就看出過程調用的深度在大多數情況下不會超過5（3）程序中存在許多循環結構，這些雖然只能由少數指令構成但它們將多次執行（4）程序中還包括許多對數據結構的處理

主要表現在：（1）時間局限性（2）空間局限性

18.什么是spooling技術spooling系統有哪些組成Spooling技術是對脫機輸入，輸出系統的模擬。

組成：（1）輸入井和輸出井（2）輸出緩沖區和輸入緩沖區（3）輸入進程SPi和輸出進程SPo（4）請求打印隊列

特點：（1）提高了I/O的速度（2）將獨占設備改為共享設備（3）實現了虛擬設備功能

第四篇：操作系統總結

第一部分概述

一、導論

1.操作系統做什么

① 馮諾依曼體系結構

② OS角色：對上：控制程序正確執行，使用方便；對下：資源分配器

③ 核心功能：進程管理，內存管理，文件管理，輸入輸出，保護和安全

2.計算機系統組織

① 中斷

② 存儲結構：寄存器→高速緩存→主存→電子磁盤→光盤→磁帶

③ I/O結構：I/O的同步、異步；慢速設備（中斷）快速設備（DMA）

3.操作系統結構：多道（使CPU總有一個任務執行）、分時（高頻率切換任務）

4.進程管理

① 進程有其生命周期，進程是執行中的程序

② 管理活動：創建或刪除用戶或系統進程；掛起或重啟進程；防死鎖；提供進程

同步、通信機制

③ 目的：使進程可以運行，相互協調不死鎖

5.內存管理

① 目標：內核健壯

② 保護方法：獨立操作模式:用戶模式，內核模式；計數器定時中斷防止死循環

6.存儲管理

① 解決問題：速度匹配→緩存（緩存的命中率）

② 等級問題：一致性；多處理器下各緩存的一致性

二、操作系統結構

1.操作系統服務：用戶界面，程序執行，I/O操作，文件系統操作，通信，錯誤檢測，資源分配，統計，保護和安全。

2.操作系統的用戶界面：命令解釋程序，圖形用戶界面

3.系統調用類型：進程控制，文件管理，設備管理，信息維護，通信

4.系統程序分類：文件管理，狀態信息，文件修改，程序設計語言支持，程序裝入和

執行，通信，系統工具，應用程序。

5.操作系統結構：

① 簡單結構(MS-DOS)：小空間多功能，應用程序直接操作硬件，不安全，無模塊，接口和功能層次沒有區分

② 分層法：難劃分，效率低，但是構造和調試簡單化

③ 微內核：包括最小的進程和內存管理以及通信，便于擴充操作系統。

④ 模塊化：動態加載模塊，允許內核提供核心服務，也能動態的實現特定的功能 ⑤ 組合結構

第二部分進程管理

一、進程

1.進程的概念

① 進程通常包括：程序計數器，棧，數據段

② 進程狀態：新建，運行，等待，就緒，終止

③ 進程控制塊PCB：進程狀態，程序計數器，CPU寄存器，CPU調度信息，內存

管理信息，記賬信息，I/O狀態信息

④

2.進程調度

① 調度隊列：作業隊列，就緒隊列，設備隊列P80

② 調度程序：長期調度程序（作業調度程序）：從作業池中選擇進程，并裝入內存

準備執行。短期調度程序（CPU調度程序）：從準備執行的進程中選擇進程，并為之分配CPU時間。中期調度程序：能將進程從內存中移出。

長短期的區別是執行頻率；長期調度控制多道程序設計的程度，中期調度可以降低多道。

③ I/O綁定進程，CPU綁定進程

④ 上下文切換：將CPU切換到另一個進程需要保存當前進程的狀態和恢復另一進

程的狀態。

3.進程操作

① 進程創程：創建新進程的執行方式（父子進程并發執行；父進程等待直到某個

或全部子進程執行完畢）

新進程地址空間（子進程是父進程的副本；子進程裝入另一個新程序）

資源共享（所有/子集/不共享）

② 進程終止

父進程終止子進程的原因（子進程使用了超過它分配的資源；分配給子程序的任務不需要了；父進程結束）

4.進程間通信

① 通信基本模型：共享內存，消息傳遞

② 共享內存：消費者可能等待生產者；無限緩沖區，有限緩沖區的區別

③ 消息傳遞：

命名：直接通信（對稱尋址：接受者命名發送者；非對稱尋址：接受者不需要命名發送者）間接通信（郵箱、端口的參與）

同步：阻塞與非阻塞（發送，接收），同步與異步

緩沖：零容量（無緩沖）；有限容量、無限容量（自動緩沖）

5.客戶機-服務器通信：套接字SOCKET，RPC遠程調用，RMI遠程方法調用

二、線程

1.概述：多線程優點：響應度高，資源共享，經濟，多處理器體系結構的利用

2.多線程模型：用戶層的用戶線程或內核層的內核線程，用戶線程受內核支持，而無

需內核管理，而內核線程由操作系統直接支持和管理，這兩種方法支持多線程。① 多對一模型（效率比較高，阻塞系統調用的后果）

② 一對一模型（更好的并發功能，缺點是創建一個用戶線程就需要一個內核進程）③ 多對多模型（用戶可以創建任意多的線程；二級模型=多對多+一對一）

3.多線程問題

① 系統調用fork().exex()

② 線程取消異步取消（立即終止），延遲取消（檢查是否應該終止）

③ 信號處理：信號必須有一個處理程序

④ 線程池：優點（處理請求速度快，線程數量可控制）

三、CPU調度

1.基本概念

① CPU區間和I/O區間的概念

② 搶占與非搶占調度的概念（發生在：一個進程從運行切換到等待、運行切換到

就緒、等待切換到就緒、以及終止，1,4非搶占，2,3搶占）

2.調度準則：CPU利用率（使CPU盡量忙），吞吐量（測量工作的方法），周轉時間（從

進程提交到完成的時間），等待時間，響應時間

3.調度算法

① 先到先服務調度FCFS（非搶占的）

② 最短作業優先調度SJF（搶占，最優算法，難知道下一CPU區間長度，用于長

期調度）

③ 最短剩余時間優先調度SRTF（強占式的SJF，適合長期調度）

④ 優先級調度（問題：無窮阻塞或饑餓，老化來解決；非搶占方式不用占用CPU

切換）

⑤ 輪轉調度RR（專為分時系統設計，是可搶占的，時間片過大變為FCFS，時間片

過小等待時間段，但是切換頻繁）

⑥ 多級隊列調度（前臺與后臺的調度算法不同，RR與FCFS）？

⑦ 多級反饋隊列調度

⑧ 實時調度：硬實時（在特定硬件上保證時間），軟實時：盡力而為，優先級不變，沒有饑餓現象

4.算法評估

① 確定性模型甘特圖

② 排隊模型 N=入*W（N平均隊列長度，W為隊列的平均等待時間，入為新進程

到達隊列的平均到達率）

③ 模擬

④ 實現

四、進程同步

1． 背景：競爭條件：共享內存，共享變量

2． 臨界區問題

① 臨界區解決方案：進入去，臨界區，退出區，剩余區

② 效果：互斥，有空讓進，有限等待

③ 證明：1.互斥，臨界區一個時間只能有一個進程2.前進，臨界區內無進程執行，那么只有那些不在剩余區內執行的進程可參加選擇，這種選擇不能無限延遲3.有限等待，從一個進程做出進入臨界區的請求，知道該請求允許為止，其他進程允許進入其臨界區的次數有上限。

④ PETERSON算法

3． 信號量：計數信號量，二進制信號量

① 技術信號量用于控制訪問：當每個線程需要使用資源時，需要對該信號量執行

acquire()操作，當線程釋放資源時，需要對該信號執行release()操作。

② 用信號量解決同步問題

4． 管程：管程結構確保一次只有一個進程能在管程內活動

5． 經典同步問題

① 生產者消費者問題

② 讀者寫者問題

③ 哲學家吃飯問題

五、死鎖

1.死鎖特征

① 必要條件：互斥，占有并等待，非搶占，循環等待

② 資源分配圖：分配圖沒有環則沒有死鎖，有環則有死鎖；有環則可能有死鎖。

2.死鎖預防

① 互斥：通常不能通過否定互斥條件來預防死鎖：有的資源本身就是非共享的。② 占有并等待：協議一：每個進程在執行前申請并獲得所有資源；協議二，允許

進程在沒有資源時才可以申請資源。協議缺點：資源利用率低，可能發生饑餓。③ 非搶占：協議：如果一個進程占有資源并申請另一個不能立即分配的資源，那

么其現在已分配的資源都可被搶占。

④ 循環等待：對所有資源類型進行完全排序，且要求每個進程按遞增順序來申請

資源。

3.死鎖避免

① 安全狀態:如果系統能按某個順序為每個進程分配資源并能避免死鎖，那么系統

狀態就是安全的。

② 單實例：資源分配圖：申請邊，分配邊，需求邊

③ 多實例：銀行家算法Available(向量),Max（矩陣）,Allocation（矩陣），Need(矩

陣),4.死鎖檢測

① 單實例：等待圖：當且僅當等待圖中有一個環時，系統存在死鎖

② 多實例：類似銀行家算法

5.死鎖恢復

① 進程終止：終止所有死鎖進程；一次只終止一個進程，直到取消死鎖循環為止 ② 資源搶占：問題：選擇一個犧牲品；回滾；饑餓

第三部分內存管理

一、內存管理

1.背景

① 地址綁定：編譯時（編譯時就知道進程將在內存中的駐留地址，那么就可以生

成絕對代碼），加載時（生成可重定位的代碼），運行時（如果進程在執行時可以從一個內存段移到另一個內存段，那么綁定必須延遲到執行時才進行）

② 邏輯地址（CPU所生成的地址）物理地址（內存單元所看到的地址）

③ 動態加載（子程序只在調用時加載，優點不用的子程序絕不會被加載）④ 動態鏈接與共享庫（將連接延遲到運行時）

2.交換（沒看）

3.連續內存分配：單分區，多分區

4.非連續內存分配：分頁（分頁技術不會產生外部碎片）

5.動態存儲分配問題：首次適應，最佳適應，最差適應

6.頁表結構：層次頁表，哈希頁表，反向頁表

二、虛擬內存

1.背景

① 多道盡可能多的程序，這也是內存管理的目標

② 虛擬內存好處：可以運行比物理內存大的程序；更快的啟動和響應（載入更快）；

更多的多道；更容易的共享文件盒地址空間；更少的輸入輸出。

2.按需調頁：在需要時才調入頁

① 有效位-無效位來來確定頁是否在內存

② 有幀就加入，無幀就換頁，頁錯誤處理流程：檢查內部表確定引用是否合法→

非法則終止，合法則調入→找到空閑幀，裝入內存→修改內部表→重啟指令 ③ 按需調頁的有效訪問時間：effective access time=(1-p)*ma+p*處理頁錯誤的時間

3.頁面置換（引用串）

① FIFO 先入先出

② 最優算法：向后看，換頁的時候看內存中哪個頁最晚用；是所有算法中產生頁

錯誤最低的算法；問題：需要引用串的未來知識

③ LRU最近最少使用算法：往前看，內存中哪頁在列表序列中離的最遠，無Belady

異常

④ 算法實現：計數器（最近最少使用：換計數器值最小的）代價大：系統級，可

能溢出，一定會寫全表

頁碼堆棧：每當引用一個頁，該頁就從棧中刪除并放在棧頂。嚴格實現，但是代價高。

二次機會：引用位，引用時改為1,；換頁時，是1則置零，是0則換

計數算法：LFU最不經常使用，MFU最經常使用（可采用老化）

4.幀分配

① 分配策略限制：所分配的幀不能超過可用幀的數量，大于最小需求

② 每個進程幀的最少數量是由體系結構決定的，而最大數量幀是由可用物理內存

決定的。

③ 當指令完成之前出現頁錯誤，該指令必須重新執行

④ 幀分配方法：

固定分配：平均分配、按比例分配

優先級分配：全局置換（幀數可變），局部置換（固定）；全局置換算法的一個問題是進程不能控制其頁錯誤率，但是全局置換通常會有更好的系統吞吐量，且更為常用。

5.系統顛簸

① 顛簸產生的原因：搶幀→I/O上升→CPU使用率降低→多道繼續增加→忙于換頁 ② 工作集合策略防止了顛簸，并盡可能的提高了多道程序的程度，可以通過頁錯

誤頻率PFF來直接測量和控制頁錯誤以防止顛簸。上限之上分配更多，下限之下，減少幀數

6.其他問題

① 預調頁關鍵問題：采用預調頁的成本是否小于處理響應頁錯誤的成本。② 頁大小問題：最佳頁大小的選擇，大頁，小頁

③ 優化程序結構

第四部分存儲管理

一、文件系統接口

1.文件概念

① 文件是邏輯外存的最小分配單元，即數據除非在文件中，否則不能寫到內存中。② 文件操作：寫，讀，重定位，刪除，截短

③ 文件加鎖：共享鎖，專用鎖；強制，建議文件加鎖機制

2.訪問方法：順序訪問，直接訪問，其他方法（索引）

3.目錄結構

① 目錄操作：創建文件，刪除文件，遍歷目錄，重命名文件，跟蹤文件系統 ② 評價目錄結構：命名（不同文件同名），分組（同一文件不同命名）

③ 單層結構目錄（命名，分組均無），雙層結構目錄（可命名不可分組），樹狀結

構（絕對，相對路徑；可命名分組），無環圖目錄（硬鏈接，軟鏈接），通用圖目錄

二、文件系統實現

1.文件系統結構：應用程序→邏輯文件系統→文件組織模塊→基本文件系統→I/O控

制→設備

2.目錄實現：線性列表（編程簡單，運行費時，查找文件需要線性搜索）

哈希表（采取策略避免沖突）

3.分配方法

① 連續分配：每個文件在磁盤上占有一組連續的塊；困難時為新文件找到空間，外部碎片問題也可能很大，確定文件分配多大空間，② 鏈接分配：解決了連續分配的所有問題；必須順序訪問文件，指針需要空間，由于指針分配在整個磁盤，可靠性就成了一個問題。

FAT文件分配表：改善了隨機訪問時間，但是需要大量磁頭尋道時間

③ 索引分配：把所有指針都放在一起，構成索引塊；支持直接訪問，且沒有外部

碎片問題，但是會浪費空間；索引塊分多大是個問題

鏈接方案（一個索引塊可以指向另一索引塊構成鏈接）

多層索引（第一個索引塊指向第二個索引塊，第二個指向文件數據塊）

組合方案P404 N級間接塊（計算）

4.空閑空間管理：為向量（1空0滿）塊號碼計算：（值為0的數字）*（一個字的位

數）+第一個值為1的位的偏移；鏈表（所有空閑的塊用鏈表鏈接起來）；組（將N個空閑塊的地址存儲在第一個空閑塊中）；計數（）

第五篇：操作系統總結

操作系統基本基礎概念

多任務是指用戶可以在同一時間內運行多個應用程序,每個應用程序被稱作一個任務。像Windows、LINUX就是支持多任務的操作系統。每個任務使用由操作系統分配的短暫的時間片(Timeslice)輪流使用CPU,由于CPU對每個時間片的處理速度非常快,在用戶看來好像這些任務在同時執行，這叫做時間片輪轉調度法。還有更多的多任務調度方法。

實時系統

（REAL TIME system）是指系統能及時的響應外部時間的請求，在規定的時間內完成對該事件的處理，并控制所有實時任務協調一致的運行。分為硬實時任務和軟實時任務，系統對任務的截止時間有要求否則會出現難以預測的結果，這就是硬實時任務，反之要求不是很嚴格則為軟實時任務。

操作系統的基本特性

并發與并行：并發性是兩個或多個事件在同一時刻發生。而并行性是兩個或多個事件在同一時間間隔內發生。

進程：為了使多個程序能并發的執行，系統必須為每個程序建立進程（process）。簡單說來~進程是指在操作系統中能獨立運行并作為資源分配的基本單位。他是由一組機器指令數據、堆棧等組成的，是一個能獨立運行的活動實體。多個進程之間可以并發的執行和交換信息。一個進程在運行時需要一定的資源，如CPU、內存空間、IO設備等。

我的注解：進程很重要。Linux的進程之間的關系可以這樣描述：一個完整的main函數運行的時候，在linux里是以進程的形式存在的。系統啟動之后運行的第一個進程的進程號是1，叫做init進程，一切進程都從它派生出來，一個父進程可以派生另一個進程，即為子進程，這倆進程為并行關系。子進程也可以創建子進程。

進程的創建在linux里邊用fork（）函數它有兩個返回值，一個是在父進程中返回，返回的是子進程號，一個是在子進程中返回，如果子進程創建成功，則返回的是0。子進程是父進程的一個拷貝，現代的進程創建都用vfork（）創建子進程之后，并不拷貝全部的進程空間，只有在用到時才拷貝，叫做寫時復制技術（copy on write）。

Linux里邊這樣創建子進程：

pid_t pid=fork();//這里的pid_t是一種數據類型（如int），這里代表進程號（實質上也是個整形變量int）

If(pid==0){這里邊就是子進程代碼}

Else if(pid>0){這里邊是父進程代碼，pid的值是子進程的進程號PID}

線程：通常在一個進程中可以包含若干個線程，他們可以利用進程所擁有的資源。在引入線程的操作系統中，一般都把進程作為分配資源的基本單位。而把線程作為獨立運行和獨立調度的基本單位。優點：運行效率更高。

進程的狀態：一般分為就緒狀態。執行狀態。阻塞狀態。

操作系統產生死鎖的原因：1.競爭資源。2.進程間推進順序非法。比如說：一個進程占有一個資源A，當他運行到需要用到被另一個進程占用的資源B時，沒有得到，于是進入等待退出運行，而這個占有資源B的進程還想得到資源A，但是占有A的進程此刻在休眠，也沒得到，所以這個進程也進入等待退出運行。這樣兩兩相互等待造成了死鎖。解決方法：1.在進程運行開始時就把所有資源占好。2.按順序加鎖。比如要得到資源B首先要對A加鎖，如果得不到就不能加鎖。所有進程都按照這個方法進行。