1、第一章1、操作系統是計算機硬件與應用之間的系統軟件 用處：方便人們更高效的使用計算機硬件，方便人們管理計算機資源，實現了對資源的抽象化。2、操作系統的發(fā)展（三個線索） 線索一：20世紀50年代中單道批處理系統（一次處理一個作業(yè)）20世紀60年代中多道批處理系統（一次處理多個）程序一旦進入用戶不能進行干預分時系統-允許用戶通過多個終端同時訪問主機資源-人機交互、 共享主機、及時接收、 及時處理UNIX出現Unix到LINUX 線索二： PC與DOS、MS_DOS到windows 線索三： MAC OS3、操作系統的主要功能 1>處理機管理 進程控制（進程的創(chuàng)建、撤銷、狀態(tài)轉換）、進程同步、

2、進程通信、調度（作業(yè)調度、進程調度） 2>存儲器管理內存分配、內存保護、地址映射（邏輯地址到物理地址轉換）、內存擴充（請求調入功能、置換功能）3>設備管理任務：(1) 完成用戶進程提出的I/O請求，為用戶進程分配所需的I/O設備，并完成指定的I/O操作。(2) 提高CPU和I/O設備的利用率，提高I/O速度，方便用戶使用I/O設備。功能：緩沖管理、設備分配、設備處理4>文件管理功能文件存儲空間的管理、目錄管理、文件的讀/寫管理和保護5>接口管理用戶接口（聯機用戶接口、脫機用戶接口、圖形用戶接口）、程序接口4、操作系統的結構<1>整體結構-無結構<2&g

3、t;模塊化結構-按功能分成不同的模塊模塊獨立性：高內聚（模塊內部各部分聯系緊密），低耦合（模塊間相互聯系和相互影響程度低）-模塊的獨立性好<3>分層式結構-自底向上的設計（每一層軟件都是在他下層軟件基礎上構建的）優(yōu)：易保證系統正確性、易擴充和易維護 缺：系統效率低<4>虛擬機<5>客戶-服務器模型（微內核）第二章-進程的描述與控制1、前趨圖：DAG 有向無循環(huán)圖 結點間的有向線段表示兩結點有前趨或偏序關系偏序（Partial Order）：設A是一個非空集，P是A上的一個關系，若P滿足下列條件： 對任意的aA，（a,a）P;(自反性） 若（a,b）P，且（b

4、,a）P，則 a=b;（反對稱性） 若（a,b）P，（b,c）P，則（a,c）P;（傳遞性）則稱P是A上的一個偏序關系2、程序順序執(zhí)行 特點：順序性，封閉性（一旦開始不受外界干擾，占用全部資源），可再現性（執(zhí)行環(huán)境，初始條件相同）3、程序并發(fā)執(zhí)行 特點：間斷性（由于共享資源，相互合作，導致相互制約）、失去封閉性、不可再現性4、進程-具有獨立功能的程序在一個數據集合上運行的過程，是系統進行資源分配和調度的一個獨立單位。（由程序、數據、PCB構成）【1】特征：動態(tài)性（最基本）、并發(fā)性、獨立性、異步性程序是一組有序指令的集合，是靜態(tài)的。【2】三種基本狀態(tài)：就緒、執(zhí)行、阻塞狀態(tài)【3】創(chuàng)建狀態(tài)

5、：申請空白PCB 寫入控制和管理信息 分配資源 進入就緒隊列 終止狀態(tài)：等待OS進行善后處理 PCB清零，并返還系統【4】掛起操作：停止一切，處于靜止狀態(tài)，原因：終端用戶要求，父進程請求，負荷調節(jié)需要、操作系統需要一旦進程被掛起，必須經過激活操作才能繼續(xù)進行5、進程控制塊PCB【1】作用：作為獨立運行基本單位的標志、實現間斷性運行方式、提供進程管理所需信息、提供進程調度所需信息、實現與其他進程的同步與通信。【2】包含信息：1）進程標識符：外部標識符、內部標識符2）處理機狀態(tài)（各種寄存器內容）3）進程調度信息（進程狀態(tài)、優(yōu)先級、所需信息、事件-阻塞原因）4）進程控制信息（程序和數據的地址、同步和

6、通信機制、資源清單、鏈接指針）【3】組織方式：線性方式、鏈接方式、索引方式6、進程控制（創(chuàng)建、終止、置于阻塞態(tài)、運行中狀態(tài)轉換）一般由OS中的原語實現處理機執(zhí)行狀態(tài)：系統態(tài)（管態(tài)/內核態(tài)），用戶態(tài)（自態(tài)）。7、OS內核包含功能【1】支撐功能：中斷處理（最基本）、時鐘管理（基本）、原語操作（原子操作-不可中斷分割）【2】資源管理功能：進程控制、存儲器管理、設備管理8、進程創(chuàng)建：【1】引起創(chuàng)建的事件：用戶登錄、作業(yè)調度、提供服務、應用請求9、進程終止：【1】引起的事件：正常結束、異常結束、外界干預10、進程阻塞：是進程自身的一種主動行為。調用阻塞原語block阻塞，調用喚醒原語wakeup喚醒，必

7、須成對出現。喚醒后由阻塞狀態(tài) 轉變?yōu)?就緒狀態(tài)。11、進程同步-協調進程次序，更好的共享資源，避免出現死鎖【1】制約關系：間接相互制約關系（訪問臨界資源-先申請，再訪問）、直接相互制約關系（一個進程等待其他進程的結果）【2】同步機制要遵守的規(guī)則：空閑讓進、忙則等待、有限等待、讓權等待12、硬件同步機制（P51）：【1】關中斷-進入鎖測試之前關閉中斷，測試完成上鎖后再打開中斷【2】利用Test-and-Set（TS）指令實現互斥，【3】利用Swap指令實現進程互斥13、信號量機制【1】整型信號量僅通過兩個原子操作（執(zhí)行中不能中斷）P、V操作wait(S)和(signal(S)來訪問Wait(S)

8、 /S資源數目 signal（S）While(S<=0); s-; S+; 【2】記錄型信號量-不存在“忙等”現象進程同步機制-增加一個進程鏈表指針list，用于鏈接所有等待進程【3】AND型信號量-共享數據作為臨界資源And同步機制基本思想：將進程所需的資源，一次性全部分配給進程，只要有一個資源不到位其他資源也不分配給他。【4】信號量集-每次分配前測試資源數量是否大于可分配下限，再決定是否分配14、信號量的應用【1】利用信號量實現進程互斥-多個進程互斥訪問臨界資源，增添一個互斥信號量，將臨界區(qū)至于P、V操作之間【2】利用信號量實現前趨關系-前趨圖【1】定義：代表共享資源的數據結構、對該

9、數據結構實施操作的一組過程所組成的資源管理程序共同構成了一個操作系統的資源管理模塊，稱之為管程【2】組成：管程的名稱局部于管程的共享數據結構說明對該數據結構進行操作的一組過程對局部于管程的共享數據設置初始值的語句【3】特性：模塊化，抽象數據類型，信息掩蔽【4】與進程的區(qū)別：（P54）【5】條件變量：利用管程實現同步時，必須設置同步工具16、進程通信【1】進程間的信息互換【2】進程互斥與同步低級進程通信【3】進程通信類型：共享存儲器系統（基于數據結構的通信方式（低級），基于共享存儲區(qū)的通信方式（高級）、管道通信系統（管道鏈接一個讀進程、一個寫進程，必須提供三方面協調能力：互斥、同步、確定對方是否

10、存在）、消息傳遞系統（高級、分成：直接通信方式、間接通信方式）、客戶機-服務器系統（三種實現方法：套接字、遠程過程調用和遠程方法調用）【4】 消息傳遞的實現方式;1、直接消息傳遞系統1） 直接通信原語：對稱尋址方式、非對稱尋址方式2） 消息的格式3） 進程的同步方式4） 通信鏈路2、信箱通信間接通信方式-進程間的通信1）信箱的結構-信箱頭+信箱尾2）信箱的通信原語創(chuàng)建、撤銷、發(fā)送（send()），接收（receive（）3）類型：私有、公有、共享關系：一對一，一對多，多對一，多對多【5】 直接消息傳遞系統實例1、 消息緩沖隊列通信機制中的數據結構消息緩沖區(qū)PCB中有關通信的數據項2、 發(fā)送原語

11、-send()3、 接受原語-receive(b)17、線程1、作為調度和分配的基本單位2、運行時的三種狀態(tài)：執(zhí)行狀態(tài)、就緒狀態(tài)、阻塞狀態(tài)3、線程控制塊-TCB4、線程是進程的一部分，一個進程可以還有多個線程，是CPU調度的基本單位，可以并發(fā)執(zhí)行，5、缺點：一個線程崩潰，所有線程都要崩潰第三章、處理機調度與死鎖311、調度實質資源分配。處理機調度是對處理機資源進行分配2、處理機調度層次：1）高級調度（幾分鐘一次）-長程調度/作業(yè)調度調度對象：作業(yè)2）低級調度（10-100MS一次）-進程調度/短程調度調度對象：進程（或內核級線程）3）中級調度（介于以上兩者之間）-內存調度目的：提高內存利用率和

12、系統吞吐量3、處理機調度算法的目標1、共同目標：（1）資源利用率（2）公平性：獲得合理的CPU時間（3）平衡性：為使系統中的CPU和各種外部設備都能經常處于忙碌狀態(tài)（4）策略強制執(zhí)行2、批處理系統的目標（1）平均周轉時間短（2）系統吞吐量高（3）處理機利用率高3、分時系統的目標（1）相應時間快（2）均衡性4、實時系統的目標（1）截至時間的保證-HRT（硬實時系統）任務必須確保對截至時間的要求，SRT（軟實時系統）任務基本上能保證對截至時間的要求（2）可預測性3.21、作業(yè)：從外存調入內存的基本單位-包含:程序、數據、作業(yè)說明書，系統根據作業(yè)說明書來控制程序2、作業(yè)步：作業(yè)經過若干個相互獨立又相

13、互關聯的順序加工步驟（作業(yè)步）得到3、作業(yè)控制塊-JCB4、作業(yè)運行的三個階段，三個狀態(tài)：收容、運行、完成-后備狀態(tài)、運行狀態(tài)、完成狀態(tài)5、作業(yè)調度的主要任務：決定接納多少個作業(yè)（根據系統規(guī)模、運行速度、作業(yè)大小、能否獲得較好的系統性能）、接納哪些作業(yè)-分時系統、實時系統不需要作業(yè)調度6、調度算法<1>先來先服務(FCFS)-依據進程進入就緒狀態(tài)的先后順序排列<2>短作業(yè)優(yōu)先（SJF）-選取就緒隊列中運行時間最短的進入運行狀態(tài)<3>優(yōu)先級調度算法（PSA）-外部賦予優(yōu)先級<4>高響應比優(yōu)先調度算法（HRRN）跟據響應比RP確定執(zhí)行順序（1）等待時

14、間相同，要求的服務時間越短，優(yōu)先級越高，類似SJF （2）要求服務時間相同，等待時間越長，優(yōu)先級越高，類似FCFS （3）對于長作業(yè)，隨等待時間的增加，優(yōu)先級提高3.3 進程調度1、進程調度的任務：保存處理機的現場信息、按某種算法選取進程、把處理器分配給進程2、調度機制中應具有：排隊器、分派器、上下文切換器3、進程的調度方式：非搶占式、搶占式搶占原則：優(yōu)先權原則、短進程優(yōu)先原則、時間片原則4、輪轉調度算法：【1】按先來先服務策略排成隊列，設置一個時間片，把CPU分配給對首進程，并令其執(zhí)行一個時間片，所有進程都能獲得一個時間片的處理機時間。【2】進程切換時機 若一個時間片尚未用完，正在運行的進程

15、便已經完成，就立即激活調度程序，將它從就緒隊列中刪除，再調度就緒隊列中隊首的進程運行，并啟動一個新的時間片。 在一個時間片用完時，計時器中斷處理程序被激活。如果進程尚未運行完畢，調度程序將把它送往就緒隊列的末尾。5、優(yōu)先級調度算法非搶占式優(yōu)先級調度算法，搶占式優(yōu)先調度算法（用于實時性要求高的系統）【1】優(yōu)先級類型：靜態(tài)優(yōu)先級（創(chuàng)建進程時確定，整個運行期間不變），動態(tài)優(yōu)先級（創(chuàng)建時先賦予一個，其值歲進程的推進或等待時間的增加而改變）6、多隊列調度算法7、多級反饋隊列調度算法目前公認的一種較好的調度算法按優(yōu)先級將就緒隊列分成多個隊列，優(yōu)先級高的時間片小，每個隊列采用FCFS算法，按隊列優(yōu)先級調度8

16、、基于公平原則的調度算法：保證調度算法（每個進程都獲得相同的處理機時間）、公平分享調度算法（多個用戶共享相同的處理機時間，不考慮進程數目）3.4 實時調度1、 實現實時調度的基本條件1） 提供必要的信息：就緒時間、開始截止時間和完成截止時間、處理時間、資源要求、優(yōu)先級2） 系統處理能力強：假定系統中有m個周期性的硬實時任務HRT，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件系統才是可調度的 多處理機情況下，處理機數為N <=N3） 采用搶占式調度機制4） 具有快速切換機制-該機制應具有如下兩方面的能力1、 對中斷的快速響應能力2、 快速的任務

17、分派能力2、 實時調度算法分類1、 根據實時任務性質：硬實時調度算法、軟實時調度算法2、 按調度方式：非搶占調度算法（非搶占式輪轉調度算法、非搶占式優(yōu)先調度算法）、搶占調度算法（基于時鐘中斷的搶占式優(yōu)先級調度算法、立即搶占的優(yōu)先級調度算法）3、最早截止時間優(yōu)先算法（EDF）1、根據任務的截至時間確定優(yōu)先級，截至時間早，優(yōu)先級高2、非搶占式調度方式用于非周期實時任務3、搶占式調度方式用于周期實時任務4、最低松弛度優(yōu)先（LLF）算法 1、確定任務優(yōu)先級根據任務的緊急（或松弛）程度，愈緊急優(yōu)先級越高，松弛度小優(yōu)先級高2、主要用于可搶占的調度方式中5、優(yōu)先級倒置 1、 高優(yōu)先級進程被低優(yōu)先級進程延遲或

18、阻塞的現象稱為優(yōu)先級倒置現象 2、解決方法：共享臨界資源時，占有資源的低優(yōu)先級進程，繼承等待資源的高優(yōu)先級進程的優(yōu)先級3.5死鎖概述1、定義：如果一組進程中的每一個進程都在等待僅由該組進程中的其他進程才能引發(fā)的事件，那么改組進程是死鎖的2、產生死鎖的必要條件：互斥條件、請求和保持條件、不可搶占條件、循環(huán)等待條件3、產生死鎖的幾種情況：競爭不可搶占性資源引起的死鎖，競爭可消耗資源引起的死鎖、進程推進順序不當引起的死鎖4、處理死鎖的方法：預防，避免，檢測，解除 1）、預防死鎖：破壞產生死鎖的必要條件中一個或幾個，主要破壞后三個，互斥條件應加以保證。 【1】破壞請求和保持條件：不能持有不可搶占的資源

19、；通過兩種協議實現：一次性申請整個運行過程中的全部資源。：獲取初期資源，運行過程中逐步釋放已用完的，再逐步請求新的資源【2】破壞不可搶占條件-代價大申請資源的不到滿足時，釋放已有的資源【3】破壞“循環(huán)等待”條件對資源類型進行線性排序，并賦予不同序號，進程請求時按序號遞增的順序請求2）、避免死鎖-在資源動態(tài)分配過程中，避免系統進入不安全狀態(tài)系統進入不安全狀態(tài)，有可能出現死鎖【1】 銀行家算法（1） 數據結構：（1） 可利用資源向量Available，m個元素的數組（2） 最大需求矩陣Max ，n*m矩陣（3） 分配矩陣Allocation, n*m（4） 需求矩陣Need ,n*mNeedi,j

20、=Maxi,j-Allocationi,j (2)銀行家算法(1) 如果RequestijNeedi, j，便轉向步驟(2)； 否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉向步驟(3)； 否則，表示尚無足夠資源，Pi須等待。(3) 系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值： Availablej = Availablej-Requestij; Allocationi, j = Allocationi, j+Requestij; Needi, j = Needi, j-Requestij; (4) 系統執(zhí)行

21、安全性算法，檢查此次資源分配后系統是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。（3）安全性算法(1) 設置兩個向量： 工作向量Work，它表示系統可提供給進程繼續(xù)運行所需的各類資源數目，它含有m個元素，在執(zhí)行安全算法開始時，Work := Available； Finish：它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi := false；當有足夠資源分配給進程時，再令Finishi := true。(2) 從進程集合中找到一個能滿足下述條件的進程： Finishi=fa

22、lse; Needi, jWorkj;若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。 (3) 當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行： Workj = Workj+Allocationi, j; Finishi =true; go to step 2; (4) 如果所有進程的Finishi=true都滿足，則表示系統處于安全狀態(tài)；否則，系統處于不安全狀態(tài)。3）死鎖的檢測與解除<1>死鎖檢測算法<2>死鎖的解除：搶占資源、終止（或撤銷）進程（終止所有死鎖進程、逐個終止進程）第四章、存儲器管理1、存儲層次至少三層：最高層CPU寄存器、中

23、間是主存、最底層是輔存2、CUP寄存器、主存屬于操作系統存儲管理的管轄范疇，掉電后存儲的信息不復存在，輔存屬于設備管理的管轄范疇，存儲的信息長期保存RAM 隨機存儲器 斷電后信息丟失ROM 只讀存儲器 斷電后信息不丟失3、可執(zhí)行存儲器：寄存器和主存儲器4、主存儲器簡稱為內存或主存，主存儲器的訪問速度遠低于CPU指令的速度5、寄存器具有與處理機相同的速度，完全能與CPU協調工作，造價昂貴6、高速緩存：介于存儲器和寄存器之間的存儲器、主要備份主存中常用的數據4.2 程序的裝入和鏈接1、程序變成可執(zhí)行程序經過：編譯 、 鏈接 、裝入2、程序的裝入：【1】絕對裝入方式：適合單道系統【2】可重定位裝入方

24、式（靜態(tài)重定位）：裝入后不再移動【3】動態(tài)運行時的裝入方式：將邏輯地址裝入，等到運行時再轉換為物理地址，裝入后可移動3、程序的鏈接：【1】靜態(tài)鏈接方式：運行之前鏈接，不再拆開【2】裝入時動態(tài)鏈接：邊裝入邊來鏈接【3】運行時動態(tài)鏈接：在程序運行的時候需要該模塊的時候才鏈接4.3連續(xù)分配存儲管理方式分為四類1、單一連續(xù)分配：用戶區(qū)內存中僅裝有一道用戶程序，即整個內存的用戶空間由該程序獨占2、固定分區(qū)分配：將整個用戶內存分區(qū)分成固定大小的區(qū)域（相等/不等），每個區(qū)域只裝入一道作業(yè)3、動態(tài)分區(qū)分配：按照進程的需要動態(tài)的分配內存分配算法順序搜索【1】首次適應（FF）算法：空閑分區(qū)地址遞增排序，找到第一個

25、大小能滿足的分區(qū)【2】循環(huán)首次適應（NF）算法：不再從頭查找，從上一次的空閑分區(qū)開始查找，直至找到一個能滿足進程需要的空閑分區(qū)【3】最佳適應（BF）：按空間從小到大排序，分配第一個合適的空閑分區(qū)【4】最壞適應（WF）：按空間從大到小排序，分配第一個合適的空閑分區(qū)-索引搜索1、快速適應算法（分類搜索法）：將空閑分區(qū)根據其大小分類，每一類單獨設立一個空閑分區(qū)鏈表，同時設立一張管理索引表 查找效率高，分區(qū)歸還時算法復雜，以空間換時間2、伙伴系統：該算法規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪(k為整數，lkm)。通常2m是整個可分配內存的大小(也就是最大分區(qū)的大小)。 假設進程需要長度為

26、n的存儲空間： （1）計算i，使2i-1-1 < n <= 2i，在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找，如果找到，則分配。 （2）沒找到，則在2i+1的空閑分區(qū)鏈表中查找，如果找到，則將該區(qū)等分，一個分配，一個加入2i的空閑分區(qū)鏈表。 （3）如果仍沒找到，則繼續(xù)類似（2）的處理。在伙伴系統中，對于一個大小為2k，地址為x的內存塊，其伙伴塊的地址則用buddyk(x)表示，其通式為3、哈希算法：建立哈希函數，分配時根據所需空閑分區(qū)大小，通過哈希函數計算，得到空閑分區(qū)的位置4、動態(tài)重定位分區(qū)分配算法：在動態(tài)分區(qū)的基礎上，增加緊湊功能（合并小的空閑分區(qū)）。4.5、分頁存儲管理方式離散分配1、分頁存儲管理方式 將程序的邏輯地址空間劃分為固定大小的頁(page)，而物理內存劃分為同樣大小的頁框(page frame)。程序加載時，可將任意一頁放人內存中任意一個頁框，這些頁框不必連續(xù)，從而實現了離散分配。【1】地址結構：A：邏輯地址空間的地址，頁面大小L，頁號P，頁內地址dINT 整除 MOD 求余【2】頁表-記錄相應頁在內存中對應的物理塊號 每一個進程有一個頁表，頁表的作用是實現頁號到物理塊號的地址映射。【3】地址變換機構：