計算機(jī)操作系統(tǒng)原理.ppt

1、計算機(jī)操作系統(tǒng)原理,李國 2007.12.3,基本授課內(nèi)容,一、操作系統(tǒng)引論 二、進(jìn)程管理 三、處理機(jī)調(diào)度與死鎖 四、存儲器管理 五、設(shè)備管理 六、文件管理 七、操作系統(tǒng)接口,第一章 操作系統(tǒng)引論,1.1 操作系統(tǒng)的目標(biāo)和作用 1.2 操作系統(tǒng)的發(fā)展過程 1.3 操作系統(tǒng)的基本特性 1.4 操作系統(tǒng)的主要功能 1.5 操作系統(tǒng)的結(jié)構(gòu)設(shè)計,1.1操作系統(tǒng)的目標(biāo)和作用,一、操作系統(tǒng)的目標(biāo) 方便性 有效性 可擴(kuò)充性 開放性,二、操作系統(tǒng)的作用 1、作為用戶與計算機(jī)硬件系統(tǒng)之間的接口。,2、作為計算機(jī)系統(tǒng)資源的管理者 主要包括四類資源：處理機(jī)、存儲器、I/O設(shè)備以及信息（數(shù)據(jù)與程序）。 3、操作系統(tǒng)用

2、作擴(kuò)充機(jī)器 虛擬機(jī)：在裸機(jī)的基礎(chǔ)上，每增加一層新的操作系統(tǒng)的軟件，就變成了功能更為強(qiáng)大的虛擬機(jī)或虛機(jī)器。,三、推動操作系統(tǒng)發(fā)展的主要動力,1、不斷提高計算機(jī)資源利用率 2、方便用戶 3、器件的不斷更新?lián)Q代 4、計算機(jī)體系結(jié)構(gòu)的不斷發(fā)展。,1.2 操作系統(tǒng)的發(fā)展過程,一、無操作系統(tǒng)的計算機(jī)系統(tǒng) 1、人工操作方式 （1946 50年代，電子管時代） 【特點】：計算機(jī)資源昂貴 ，沒有操作系統(tǒng) 【工作方式】： 用戶：用戶既是程序員、操作員，還是計算機(jī)專業(yè)人員； 編程語言：為機(jī)器語言； 輸入輸出：紙帶或卡片； 【計算機(jī)的工作特點】： 用戶獨占全機(jī)：用戶獨占計算機(jī)所有資源，資源利用率低； CPU等待用戶：

3、計算前，手工裝入紙帶或卡片；計算完成后，手工卸取紙帶或卡片；CPU利用率低； 【主要矛盾】： 計算機(jī)處理能力的提高，手工操作的低效率 用戶獨占全機(jī)的所有資源；,2、脫機(jī)輸入/輸出方式 引入外圍機(jī)控制數(shù)據(jù)的提前錄入和延后輸出，具體參照P5 圖1-2,二、單道批處理系統(tǒng),1、單道批處理系統(tǒng)的處理過程 引入監(jiān)督程序，成批的作業(yè)首先在外存排隊等待，由監(jiān)督程序負(fù)責(zé)將每一個作業(yè)裝入內(nèi)存，處理完成后，再掉調(diào)入下一個作業(yè)，直至運(yùn)行完畢。 2、單道批處理系統(tǒng)的特征 自動性 順序性 單道性,三、多道批處理系統(tǒng),1、多道程序設(shè)計的基本概念 用戶提交的作業(yè)都先存放在外存的后備隊列中，由作業(yè)調(diào)度程序按一定的算法選擇若干

4、作業(yè)調(diào)入內(nèi)存，共享CPU和系統(tǒng)的各種資源。 2、多道批處理的特征 （1）多道性：在內(nèi)存中有多個程序（嚴(yán)格而言為進(jìn)程）同時執(zhí)行（宏觀上）； （2）無序性：進(jìn)入內(nèi)存的順序與執(zhí)行完的順序無關(guān)； （3）調(diào)度性：經(jīng)過2次調(diào)度，先調(diào)度到內(nèi)存，轉(zhuǎn)換為進(jìn)程后，進(jìn)行進(jìn)程調(diào)度，要CPU進(jìn)行執(zhí)行。,3、多道批處理系統(tǒng)的優(yōu)缺點： （1）資源利用率高了； （2）系統(tǒng)吞吐量大了； （3）平均周轉(zhuǎn)時間長； （4）無交互能力。 4、多道批處理系統(tǒng)需要解決的問題 （1）處理機(jī)管理問題 （2）內(nèi)存管理問題 （3）I/O設(shè)備管理問題 （4）文件管理問題 （5）作業(yè)管理問題,處理上述問題組成一系列程序的集合，由此構(gòu)成了完整意義上的操

5、作系統(tǒng)。 操作系統(tǒng)的定義：操作系統(tǒng)是一組控制和管理計算機(jī)硬件和軟件資源，合理的組織計算機(jī)工作流程以及方便用戶使用的程序的集合。 四、分時系統(tǒng) 1、定義：在一臺主機(jī)上連接了多個帶有顯示器和鍵盤的終端，同時允許多個用戶通過自己的終端，以交互方式使用計算機(jī)，共享主機(jī)中的資源。,分時系統(tǒng)的結(jié)構(gòu)示意圖,2、分時系統(tǒng)實現(xiàn)的關(guān)鍵問題 （1）及時接收：多路卡 （2）及時處理：分時間片的原則。 為此： （1）用戶作業(yè)可以直接進(jìn)入內(nèi)存 （2）時間片選擇大小要適當(dāng)。 3、分時系統(tǒng)的特征： （1）多路性 （2）獨立性 （3）及時性 （4）交互性,五、實時系統(tǒng),1、理解：系統(tǒng)能及時響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成

6、對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致的運(yùn)行。 2、實時系統(tǒng)的應(yīng)用領(lǐng)域： 實時控制：要求與被控制的變化速度相比，其反應(yīng)速度足夠快；工作安全可；需要人工干預(yù)時，操作簡便。如生產(chǎn)過程控制，宇航自動控制等。 實時信息處理系統(tǒng)：要求計算機(jī)能夠在容許的延遲時間內(nèi)，相應(yīng)外部的事件請求，完成對該事件的處理，并控制所有的實時設(shè)備和實時任務(wù)協(xié)調(diào)運(yùn)行。如飛機(jī)訂票系統(tǒng), 期貨、股票交易系統(tǒng)等。,3、實時系統(tǒng)與分時系統(tǒng)的比較 （1）多路性 （2）獨立性 （3）及時性 （4）交互性 （5）高可靠性,1.3操作系統(tǒng)的基本特性,一、并發(fā)性(concurrency) 多個事件在同一時間段內(nèi)發(fā)生。操作系統(tǒng)是一個并發(fā)系統(tǒng)，各

7、進(jìn)程間的并發(fā)，系統(tǒng)與應(yīng)用間的并發(fā)。操作系統(tǒng)要完成這些并發(fā)過程的管理。并行(parallel)是指在同一時刻發(fā)生。 在多道程序處理時，宏觀上并發(fā)，微觀上交替執(zhí)行（在單處理器情況下） 。 程序的靜態(tài)實體是可執(zhí)行文件，而動態(tài)實體是進(jìn)程（或稱作任務(wù)），并發(fā)指的是進(jìn)程。,二、共享性(sharing) 多個進(jìn)程共享有限的計算機(jī)系統(tǒng)資源。操作系統(tǒng)要對系統(tǒng)資源進(jìn)行合理分配和使用。資源在一個時間段內(nèi)交替被多個進(jìn)程所用。 互斥共享方式（如音頻設(shè)備），資源分配后到釋放前，不能被其他進(jìn)程所用。 同時訪問方式，（如可重入代碼，磁盤文件）。 資源分配難以達(dá)到最優(yōu)化,三、虛擬性(virtual) 一個物理實體映射為若干個對

8、應(yīng)的邏輯實體（分時或分空間）。虛擬是操作系統(tǒng)管理系統(tǒng)資源的重要手段，可提高資源利用率。 CPU每個用戶（進(jìn)程）的“虛處理機(jī)”。 存儲器每個進(jìn)程都占有的地址空間（指令數(shù)據(jù)堆棧）。 顯示設(shè)備多窗口或虛擬終端 如虛擬光驅(qū)。,四、異步性(asynchronism) 異步性也稱不確定性，指進(jìn)程的執(zhí)行順序和執(zhí)行時間及執(zhí)行結(jié)果的不確定性： 程序執(zhí)行結(jié)果不確定，不可再現(xiàn)。相同輸入與環(huán)境下多次運(yùn)行結(jié)果不同。 多道程序設(shè)計環(huán)境下，程序按異步方式運(yùn)行。多個進(jìn)程并發(fā)執(zhí)行，“時走時停”，不可預(yù)知每個進(jìn)程的運(yùn)行推進(jìn)快慢，引發(fā)執(zhí)行順序與時間的不確定。,1.4 操作系統(tǒng)的主要功能,一、處理機(jī)管理功能： 可歸結(jié)為進(jìn)程管理，包括

9、以下方面 進(jìn)程控制：進(jìn)程的創(chuàng)建和撤消、進(jìn)程狀態(tài)的轉(zhuǎn)換等； 進(jìn)程同步：協(xié)調(diào)進(jìn)程執(zhí)行的順序關(guān)系； 進(jìn)程通信； 調(diào)度：作業(yè)調(diào)度和進(jìn)程調(diào)度兩層。 。,二、存儲器管理功能： 1、內(nèi)存分配 2、內(nèi)存保護(hù) 3、地址映射 4、內(nèi)存擴(kuò)充 三、設(shè)備管理功能： 1、設(shè)備分配 2、設(shè)備處理（相當(dāng)于啟動） 3、緩沖管理 4、虛擬設(shè)備,四、文件管理功能： 1、文件存儲空間管理 2、目錄管理 3、文件讀寫管理 4、文件保護(hù)。 五、用戶接口： 1、命令接口 2、程序接口 3、圖形接口,1 .5操作系統(tǒng)的結(jié)構(gòu)設(shè)計,一、傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu) 1、無結(jié)構(gòu)操作系統(tǒng) 操作系統(tǒng)是由一組過程的集合，各過程之間相互調(diào)用，在操作系統(tǒng)內(nèi)部不存在任

10、何結(jié)構(gòu)，也因此稱為整體系統(tǒng)結(jié)構(gòu) 2、模塊化操作系統(tǒng)結(jié)構(gòu) 操作系統(tǒng)是由按其功能劃分為若干個具有一定獨立性和大小的模塊。每個模塊具有某個方面的管理功能，規(guī)定好模塊之間的接口。,3、分層式操作系統(tǒng)結(jié)構(gòu) 從物理機(jī)器開始，在上面不斷添加新的層次軟件，實現(xiàn)若干功能，構(gòu)成滿足需要的操作系統(tǒng)。 二、微內(nèi)核操作系統(tǒng) 1、微內(nèi)核是20世紀(jì)90年代發(fā)展的現(xiàn)代操作系統(tǒng)內(nèi)核結(jié)構(gòu)，典型的操作系統(tǒng)如WindowsNT。實現(xiàn)了以微內(nèi)核為操作系統(tǒng)核心，以客戶/服務(wù)器為基礎(chǔ)，并且采取了面向?qū)ο蟮某绦蛟O(shè)計方法的新型體系結(jié)構(gòu)。,2、客戶/服務(wù)器模式 操作系統(tǒng)劃分為兩部分：一部分用于提供各種服務(wù)的一組服務(wù)器，如進(jìn)程服務(wù)器、存儲器服務(wù)器

11、等，運(yùn)行在用戶態(tài)；另一部分是內(nèi)核，用于處理客戶和服務(wù)器之間的通信。CPU執(zhí)行內(nèi)核程序運(yùn)行在核心態(tài)。 3、微內(nèi)核技術(shù)： （1）定義：精心設(shè)計的，能實現(xiàn)現(xiàn)代操作系統(tǒng)核心功能的小型內(nèi)核，與一般操作系統(tǒng)不同，更小更精練，運(yùn)行在核心態(tài)，開機(jī)長駐內(nèi)存，并非一個完整的操作系統(tǒng)，是構(gòu)建通用操作系統(tǒng)的重要基礎(chǔ)。,（2）微內(nèi)核的基本功能 -進(jìn)程管理 -存儲器管理 -進(jìn)程通信管理 -I/O設(shè)備管理,第二章 進(jìn)程管理,2 .1進(jìn)程的基本概念 一、程序的順序執(zhí)行及特征 1、參照課本P27 圖2-1 2、特征： 順序性 封閉性 可再現(xiàn)性,二、程序的并發(fā)執(zhí)行及其特征 1、前趨圖：利用有向無環(huán)圖中結(jié)點描述進(jìn)程，有向弧描述進(jìn)程

12、執(zhí)行順序。 2、并發(fā)執(zhí)行的特征 間斷性 失去并發(fā)性 不可再現(xiàn)性,三、進(jìn)程的特征與狀態(tài) 1、進(jìn)程的特征 （1）結(jié)構(gòu)特征：進(jìn)程實體主要包括程序段、數(shù)據(jù)段和進(jìn)程控制塊三部分 。 （2）動態(tài)性是進(jìn)程最基本的特征，表現(xiàn)在進(jìn)程的創(chuàng)建、狀態(tài)的轉(zhuǎn)換、撤消等進(jìn)程是有生命周期的，程序本身是靜態(tài)的。 （3）并發(fā)性，所謂前面提到程序的并發(fā)實質(zhì)上是進(jìn)程的并發(fā),（4）獨立性：CPU進(jìn)行調(diào)度的獨立單位以及進(jìn)行資源分配的基本單位 （5）異步性，推進(jìn)順序是異步的。 2、進(jìn)程的定義： （1）進(jìn)程是程序的一次執(zhí)行。 （2）進(jìn)程是一個程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時所發(fā)生的活動。 （3）進(jìn)程是一個數(shù)據(jù)集合上運(yùn)行的過程，是系統(tǒng)進(jìn)行資源

13、分配和調(diào)度的一個獨立單位。 進(jìn)程是進(jìn)程實體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。,3、進(jìn)程的三種基本狀態(tài) （1）就緒狀態(tài)：當(dāng)進(jìn)程剛剛建立后處于就緒狀態(tài)，具備所有資源，只差CPU調(diào)度就可執(zhí)行，一個系統(tǒng)中處于就緒狀態(tài)的進(jìn)程有多個，構(gòu)成就緒隊列。 （2）執(zhí)行狀態(tài)：獲得CPU，進(jìn)行執(zhí)行，在單處理機(jī)內(nèi)只有1個執(zhí)行狀態(tài)進(jìn)程； （3）阻塞狀態(tài)：處于執(zhí)行狀態(tài)的進(jìn)程因為發(fā)生某事件而暫時無法繼續(xù)執(zhí)行，如等待I/O，申請緩沖區(qū)等，可以根據(jù)不同的阻塞原因放到不同的阻塞隊列中，從而構(gòu)成阻塞隊列。,程序1,程序2,程度段,數(shù)據(jù)段,程度段,數(shù)據(jù)段,進(jìn)程1,進(jìn)程2,進(jìn)程1,進(jìn)程2,Pcb區(qū)域,進(jìn)程1pcb,進(jìn)程

14、2pcb,進(jìn)程i pcb,四、進(jìn)程控制塊 1、進(jìn)程控制塊的作用 進(jìn)程控制塊（PCB）是為了描述和控制進(jìn)程的運(yùn)行，為進(jìn)程定義的數(shù)據(jù)結(jié)構(gòu)，屬于進(jìn)程實體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)，記錄了操作系統(tǒng)所需要的、用于描述進(jìn)程當(dāng)前情況及控制進(jìn)程運(yùn)行的全部信息，操作系統(tǒng)通過PCB來對并發(fā)執(zhí)行的進(jìn)程來進(jìn)行控制和管理的。 進(jìn)程存在的唯一標(biāo)志是PCB。,2、進(jìn)程控制塊的基本組成 （1）進(jìn)程標(biāo)識符： a.內(nèi)部標(biāo)識符就是PCB區(qū)中的標(biāo)號，是數(shù)字。 b.外部標(biāo)識符就是進(jìn)程的實際名字 （2）處理機(jī)的狀態(tài)，中斷時處理狀態(tài)的保護(hù)，斷點地址保護(hù) （3）進(jìn)程調(diào)度所需信息（如進(jìn)程狀態(tài)、優(yōu)先級、進(jìn)程等待時間及阻塞原因等

15、 （4）進(jìn)程控制信息：如程序段和數(shù)據(jù)段的地址、資源清單、進(jìn)程同步與通信機(jī)制、進(jìn)程隊列中各進(jìn)程的鏈接指針。,3、PCB的組織方式： （1）鏈接方式 （2）索引方式,2.2進(jìn)程控制,一、進(jìn)程控制中心：操作系統(tǒng)內(nèi)核通過原語操作實現(xiàn)。 1、內(nèi)核是基于硬件的第一層軟件擴(kuò)充，并長駐內(nèi)存。它為系統(tǒng)對進(jìn)程和資源進(jìn)行控制和管理，提供了良好的環(huán)境。內(nèi)核通常包括中斷處理、時鐘管理、進(jìn)程控制、進(jìn)程通信和調(diào)度原語，以及資源管理中的基本操作等。 2、所謂原語，是由若干條機(jī)器指令構(gòu)成，用以完成特定功能的一段程序，為了保證其操作的正確性，它應(yīng)該是原子操作，即原語是一個不可分割的操作。,二、基本進(jìn)程控制原語 1、進(jìn)程創(chuàng)建原語

16、（1）申請空白PCB （2）為新進(jìn)程分配資源。 （3）初始化進(jìn)程控制塊 （4）將新進(jìn)程插入到就緒隊列。,2、進(jìn)程終止原語 （1）根據(jù)標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB，讀出進(jìn)程狀態(tài)。 （2）若被終止進(jìn)程屬執(zhí)行狀態(tài)，需要重新調(diào)度新進(jìn)程執(zhí)行。 （3）該進(jìn)程所有子孫進(jìn)程一并終止。 （4）被終止進(jìn)程的全部資源都被釋放。,3、進(jìn)程阻塞原語block() （1）將阻塞進(jìn)程由執(zhí)行狀態(tài)變?yōu)樽枞麪顟B(tài)，并加入到阻塞隊列中 （2）系統(tǒng)重新調(diào)度新進(jìn)程進(jìn)行執(zhí)行。 4、進(jìn)程喚醒原語wakeup() 將被喚醒進(jìn)程狀態(tài)由阻塞變換為就緒狀態(tài)，從阻塞隊列中刪除，加入到就緒隊列中。,2 .3 進(jìn)程同步,一、進(jìn)程同步的基本概

17、念 1、兩種形式的制約關(guān)系 （1）間接相互制約關(guān)系：因為臨界資源的特性造成進(jìn)程間的制約。 （2）直接相互制約關(guān)系：進(jìn)程之間相互協(xié)作、互相制約關(guān)系。 2、臨界資源：如打印機(jī)、磁帶機(jī)等一段時間內(nèi)只允許一個進(jìn)程進(jìn)行使用的資源。,3、臨界區(qū)： 每個進(jìn)程中訪問臨界資源的那段代碼成為臨界區(qū)。整個程序段分為：進(jìn)入?yún)^(qū)、臨界區(qū)、退出區(qū)以及剩余區(qū)。 4、同步機(jī)制應(yīng)遵循的規(guī)則： （1）空閑讓進(jìn) （2）忙則等待 （3）有限等待 （4）讓權(quán)等待,二、信號量機(jī)制： 1、整型信號量 Wait(s): while s0 do no-op s:=s-1; Signal(s):s:=s+1; 2、記錄型信號量 Wait(s):

18、s.value=s.value-1; if s.value0 block(s.l); Signal(s): s.value=s.value+1; if s.value=0 wakeup(s.l) ,記錄型信號量的物理意義 Wait:相當(dāng)于分配資源的過程。若有資源進(jìn)行分配，則分配后就不會小于0，因此可以完全執(zhí)行完Wait原語，然后進(jìn)入臨界區(qū)，如減1后出現(xiàn)小于0的情況則表示實際上已經(jīng)沒有資源可以分配了，因此該進(jìn)程要放到阻塞隊列L中，此時S.VALUE的絕對值就是阻塞進(jìn)程的數(shù)量。 Signal:相當(dāng)于釋放資源的過程。一個進(jìn)程執(zhí)行完正常釋放資源，但加1后仍小于等于0表示它原來是個負(fù)數(shù)，因此阻塞隊列里有

19、等待該資源沒有滿足的阻塞進(jìn)程，因此，在釋放資源的同時要喚醒阻塞進(jìn)程。如加1后正常的正數(shù)，就光釋放完資源就結(jié)束了。,3、記錄型信號量的應(yīng)用 （1）實現(xiàn)互斥 對于N個進(jìn)程對1個臨界資源的互斥共享，每個進(jìn)程的算法描述： VAR Mutex：=1； 進(jìn)程pi： Repeat Wait（Mutex）； 臨界區(qū)； Signal（Mutex） until false;,（2）實現(xiàn)前趨關(guān)系： 見p45 圖2-10 Var a,b,c,d,e,f,g:=0,0,0,0,0,0,0 S1: s1;signal(a);signal(b); S2:wait(a);s2;signal(c);signal(d); S3:

20、wait(b);s3;signal(e); S4:wait(c);s4;signal(f); S5:wait(d);s3;signal(g); S6:wait(e); wait(f);wait(g); s6;,3、利用信號量實現(xiàn)進(jìn)程同步,輸入進(jìn)程： Repeat 輸入數(shù)據(jù)； wait(P1); 放數(shù)據(jù)入緩沖區(qū)； signal(P2); until false;,計算進(jìn)程： Repeat wait(p2); 從緩沖區(qū)取數(shù)據(jù)； signal(P1); 計算數(shù)據(jù)； until false;,.4經(jīng)典進(jìn)程同步問題,一、生產(chǎn)者-消費者問題,多個生產(chǎn)者進(jìn)程和多個消費者進(jìn)程共享一個有N個緩沖區(qū)的緩沖池，生產(chǎn)

21、者進(jìn)程負(fù)責(zé)輸入數(shù)據(jù)，消費者進(jìn)程負(fù)責(zé)輸出數(shù)據(jù)，兩個相互合作。用信號量機(jī)制把每個進(jìn)程的執(zhí)行過程表達(dá)出來。因為緩沖區(qū)是臨界資源，一段時間內(nèi)只能有1個進(jìn)程使用，所以，對緩沖區(qū)的放數(shù)據(jù)及取數(shù)據(jù)只能有一個進(jìn)程來使用緩沖區(qū)，存在互斥問題；同時，生產(chǎn)-與消費構(gòu)成同步關(guān)系，相互合作，互相制約。,VAR mutex:=1,empty=n;full=0; buffter0.n-1; in out:=0,0; 生產(chǎn)者進(jìn)程i： Repeat 生產(chǎn)數(shù)據(jù)nextp； wait(empty); wait(mutex); bufferin:=nextp; in=(in+1)%n ; signal(full); until fa

22、lse;,消費者進(jìn)程i： Repeat wait(full); wait(mutex); Nextc=buffer(out); out=(out+1)%n ; signal(empty); until false;,二、哲學(xué)家就餐問題 5個哲學(xué)家圍做一個圓桌，5支筷子分布與每人的兩側(cè)，每人先是思考問題，然后拿起左右兩邊的筷子就餐，后放筷子繼續(xù)思考問題。用信號量機(jī)制描述每人的活動過程。 分析：筷子5支，都屬于臨界資源，因此互斥使用；,哲學(xué)家i： Repeat wait(SM); wait(chopsticki); wait(chopstick(i+1)%5); 就餐； signal(chopst

23、icki); signal(chopstick(i+1)%5); signal(sm) ; 繼續(xù)思考； until false; Chopstick0.4=1;sm=4(5支筷子最多允許4個人同時去搶，才總有一個人拿到2支，才能吃飯，他放下后別人可以繼續(xù)用，若允許5個人都搶，可能會出現(xiàn)一人1支筷子，出現(xiàn)僵持死鎖狀態(tài)),三、讀者-寫者問題 一個數(shù)據(jù)文件可以同時允許有多個讀者進(jìn)行訪問，但每次只允許1個寫者進(jìn)行修改，讀者和寫者不能同時出現(xiàn)。 分析：把多個讀者作為一個整體來考慮，則加上 n個寫者的話，這n+1個對象對數(shù)據(jù)塊互斥訪問，需要1個互斥信號量wmutex=1來控制;另外對于讀者整體中，考慮與寫

24、者互斥的只是第一個讀者來時要考慮的，有了第一個，其他讀者就可以跟著進(jìn)來，同樣，釋放資源時候也只是最后一個讀者，其他讀者想走就撤就可以。 為了表示到底有多少讀者，引入記數(shù)變量readcount，而對變量的使用，屬于臨界資源，一次只允許一個進(jìn)程使用，所以再引入信號量rwmutex=1;,讀者進(jìn)程i： REPAET wait(rmutex); if readcout=0 wait(wmutex); Readcount+; signal(rmutex); 訪問數(shù)據(jù)文件； wait(rmutex); Readcount-; if readcout=0 wait(wmutex); signal(rmute

25、x); until false;,寫者進(jìn)程i： REPAET wait(wmutex); 修改文件； signal(wmutex); until false;,例題1、司機(jī)與售票員的合作問題 VAR S1=1;S2=0;,司機(jī)： Wait(s1); 啟動車輛； 正常行車； 到站停車 Signal(s2);,售票員： Wait(s2); 開車門； 上下乘客； 關(guān)車門 Signal(s1); 售票,例題2：假定閱覽室能容納100個人閱讀，讀者進(jìn)入和離開閱覽室時，都必須在閱覽室門口的一個登記表上登記。假定每次只允許一個人登記和撤消登記，設(shè)閱覽室內(nèi)有100個座位，用信號量機(jī)制描述讀者進(jìn)程的同步算法。,

26、讀者進(jìn)程i: Var s=100;mutex=1; Wait(s); Wait(mutex); 查登記表，并置某座位為占用態(tài) Signal(mutex); 在座位上坐下閱讀； Wait(mutex); 查登記表，并置某座位為空閑狀態(tài) Signal(mutex); Signal(s);,例題：桌子上有一只盤子只能放一只水果，爸爸專門向盤子中放蘋果，媽媽專門向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用信號量機(jī)制實現(xiàn)他們之間的同步機(jī)制。 Var s=1,s1=s2=0,爸爸：準(zhǔn)備蘋果； wait(s); 將蘋果放在盤子內(nèi)； signal(s1); 媽媽：準(zhǔn)備橘子； wa

27、it(s); 將橘子放在盤子內(nèi)； signal(s2);,女兒：wait(s1); 從盤子上拿走蘋果； signal(s); 吃蘋果； 兒子：wait(s2); 從盤子上拿走橘子； signal(s); 吃橘子；,2.5管程機(jī)制,一、定義： 一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。 引入管程的目的是避免信號量機(jī)制書寫中的麻煩，具體例子參考P53。,2.6進(jìn)程通信,一、進(jìn)程通信的類型 1、共享存儲器系統(tǒng) （1）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 （2）基于共享存儲區(qū)的通信方式 2、消息傳遞系統(tǒng) （1）直接通信方式： Send(re

28、ceiver,message); Receive(sender,message); （2）間接通信方式 Send(mailbox,message); Receive(mailbox,message);,3、管道通信：所謂管道是用于連接一個讀進(jìn)程和一個寫進(jìn)程以實現(xiàn)他們通信的一個共享文件，又名Pipe文件，本身提供了互斥和同步進(jìn)程的能力。） 二、消息緩沖隊列通信機(jī)制 1、消息緩沖隊列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu) Type message buffer=record sender:發(fā)送者進(jìn)程標(biāo)識符； size:消息長度； text:消息正文； next:指向下一個消息緩沖區(qū)的指針 end 2、PCB中有關(guān)通

29、信的數(shù)據(jù)項 Mq:消息隊列隊首指針； Mutex:消息隊列互斥信號量 Sm:消息隊列資源信號量,3、發(fā)送原語 Procedure send(receiver,a) Begin Getbuf(a.size,i); i.sender=a.sizer; i.size=a.size; i.text=a.size; i.next=0; Getid(pcb set,receiver.j); Wait(j.mutex); Insert(j.mq,i); Signal(j.mutex); Signal(j.sm); End;,4、接收原語 Procedure receive(b) Begin J=intern

30、al name; Wait(j.sm); Wait(j.mutex); Remove(j.mq,i); Signal(j.mutex); b.sender=i.sizer; b.size=i.size; b.text=i.size; End;,2.7線程,一、線程的基本概念 1、線程的引入 進(jìn)程的兩個屬性：資源分配的獨立單位；CPU調(diào)度的獨立單位。 進(jìn)一步提高并發(fā)程度和減少系統(tǒng)開銷引入線程。 2、線程的屬性 （1）輕型實體 （2）獨立調(diào)度和分派的基本單位 （3）可并發(fā)執(zhí)行 （4）共享進(jìn)程資源。,第三章 處理機(jī)調(diào)度與死鎖,3.1處理機(jī)調(diào)度的基本概念 一、高級、中級和低級調(diào)度 1、高級調(diào)度（作業(yè)調(diào)

31、度）：由作業(yè)調(diào)度程序按照一定算法選擇若干作業(yè)進(jìn)入內(nèi)存，創(chuàng)建出進(jìn)程，分配必要的資源，將新進(jìn)程掛到就緒隊列中。 （1）接納多少作業(yè)（2）接納哪些作業(yè),2、低級調(diào)度（進(jìn)程調(diào)度）：決定就緒隊列的進(jìn)程誰獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程。 非搶占方式：一旦處理機(jī)分配給某個進(jìn)程就要它一直執(zhí)行下去，直至進(jìn)程完成或者發(fā)生某事件而被阻塞時，才再把處理機(jī)分配給其他進(jìn)程。 搶占方式：正在執(zhí)行的進(jìn)程，若有新的優(yōu)先級更高的進(jìn)程到來后則停止正在執(zhí)行的進(jìn)程，新進(jìn)程搶占CPU。 搶占的標(biāo)準(zhǔn)為：（1）優(yōu)先權(quán)原則； （2）短作業(yè)優(yōu)先原則； （3）時間片原則。,3、中級調(diào)度 存儲管理中的對換功能，把內(nèi)存中暫時不運(yùn)

32、行的進(jìn)程換出到外存對換區(qū)，而把外存中具備運(yùn)行條件的進(jìn)程換入內(nèi)存，稱為中級調(diào)度。 二、調(diào)度隊列模型 1、僅有進(jìn)程調(diào)度的調(diào)度隊列模型 2、具有高級和低級調(diào)度的調(diào)度隊列模型 3、同時具有三級調(diào)度的調(diào)度隊列模型,三、選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1、面向用戶的準(zhǔn)則 （1）周轉(zhuǎn)時間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。包括四部分時間：作業(yè)在外存后備隊列上等待調(diào)度的時間、進(jìn)程在就緒隊列上等待進(jìn)程調(diào)度的時間、進(jìn)程在CPU上執(zhí)行的時間、進(jìn)程等待I/O操作完成的時間。 平均周轉(zhuǎn)時間 平均帶權(quán)周轉(zhuǎn)時間 （2）響應(yīng)時間。 （3）截止時間的保證 （4）優(yōu)先權(quán)準(zhǔn)則,2、面向系統(tǒng)的準(zhǔn)則 （1）系統(tǒng)吞

33、吐量高 （2）處理機(jī)利用率好 （3）各類資源的平衡利用。,3.2 調(diào)度算法,一、先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法 1、先來先服務(wù)調(diào)度算法 算法思想： （1）作業(yè)調(diào)度：每次調(diào)度都從后備作業(yè)隊列中，選擇一個或多個最先進(jìn)入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源，創(chuàng)建進(jìn)程，然后放入就緒隊列。 （2）進(jìn)程調(diào)度：每次調(diào)度是從就緒隊列中，選擇一個最先進(jìn)入該隊列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。 通常要考慮，目前系統(tǒng)是否滿足進(jìn)程資源要求。 例子參考P76,二、短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 對短作業(yè)或短進(jìn)程進(jìn)行優(yōu)先調(diào)度的算法。短作業(yè)調(diào)度算法是從后備隊列中選擇一個后若干個估計運(yùn)行時間最短的作業(yè)，將它們內(nèi)調(diào)入

34、內(nèi)存運(yùn)行。短進(jìn)程調(diào)度是從就緒隊列中選出一估計運(yùn)行時間最短的進(jìn)程，分配處理機(jī)。 注： （1）FCFS算法不利于短作業(yè)。 （2）SJF算法不利于長作業(yè)。,FCFS：,SJF：,三、高優(yōu)先權(quán)優(yōu)先調(diào)度算法 1、優(yōu)先權(quán)調(diào)度算法的類型 （1）非搶占方式：一旦處理機(jī)分配給某個進(jìn)程后，該進(jìn)程一直執(zhí)行下去，直至完成，其它進(jìn)程不得搶占CPU。 （2）搶占方式：把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程執(zhí)行，若來新進(jìn)程優(yōu)先級更高，則搶占CPU。 2、優(yōu)先權(quán)的類型： （1）靜態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時確定，整個運(yùn)行期間保持不變。一般用0-255或0-7中的某個整數(shù)來表示，有的系統(tǒng)中數(shù)字越大，優(yōu)先級越高，有的系統(tǒng)相反。 （2）動態(tài)優(yōu)先權(quán)

35、：隨著進(jìn)程的推進(jìn)或等待時間的增加，優(yōu)先權(quán)而發(fā)生改變。,非強(qiáng)占方式：ACDB 強(qiáng)占方式：A-B-C-D-B-A,3、高響應(yīng)比優(yōu)先調(diào)度算法 （1）優(yōu)先權(quán)的確定：優(yōu)先權(quán)=（等待時間+要求服務(wù)時間）/要求服務(wù)時間 （2）高響應(yīng)比優(yōu)先調(diào)度算法既照顧到了短作業(yè)，又考慮了長作業(yè)。 四、基于時間片的輪轉(zhuǎn)調(diào)度算法 1、時間片輪轉(zhuǎn)法 將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個隊列，每次調(diào)度時，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。,2、多級反饋隊列調(diào)度算法 是目前公認(rèn)的一種較好的調(diào)度算法： a.設(shè)定多個就緒隊列，每個隊列設(shè)定不同優(yōu)先級，由高到低，每個隊列中進(jìn)程獲得時間片有小到大； b.新進(jìn)程進(jìn)入內(nèi)存，先

36、放第1隊列的末尾，按FCFS原則進(jìn)行運(yùn)行，單位時間片運(yùn)行完結(jié)束，否則放到第2隊列末尾，依次類推，直至全部放到最后一級隊列，完全采取時間片輪轉(zhuǎn)原則進(jìn)行運(yùn)行 c.僅當(dāng)前面隊列全部空閑時，才運(yùn)行后面隊列中的進(jìn)程，若正在執(zhí)行第I級隊列的某進(jìn)程，來一個新進(jìn)程，則將當(dāng)前執(zhí)行進(jìn)程放到該級隊列的末尾，專而執(zhí)行新進(jìn)程。 兼顧了長作業(yè)和短作業(yè)，采用了FCFS以及時間片輪轉(zhuǎn)和優(yōu)先級高低綜合運(yùn)用的一種調(diào)度算法。,3.5產(chǎn)生死鎖的原因和必要條件,一、死鎖的定義和原因 1、定義：所謂死鎖是指多個進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局，若無外力作用，它們都將無法再向前推進(jìn)。 2、產(chǎn)生死鎖的原因 （1）競爭資源：可剝奪和

37、非剝奪性資源/臨時性資源 （2）進(jìn)程間推進(jìn)順序非法。,二、產(chǎn)生死鎖的必要條件 （1）互斥條件：資源本身的特性 （2）請求和保持條件：在請求不到新資源的時候進(jìn)程不釋放原來的資源 （3）不剝奪條件：進(jìn)程獲得的資源，為使用完前不可被剝奪 （4）環(huán)路等待條件：進(jìn)程對資源的請求形成一個請求環(huán)形鏈 三、處理死鎖的基本方法 1、預(yù)防死鎖 2、避免死鎖 3、檢測死鎖 4、解除死鎖,3.6 預(yù)防死鎖的方法,一、預(yù)防死鎖 1、打破請求和保持條件：要求進(jìn)程一次性申請到全部資源后再運(yùn)行，不會產(chǎn)生死鎖，但效率降低 2、打破不剝奪條件：要求進(jìn)程提出新資源要求不被滿足后，必須釋放原來的保持的資源，損失代價嚴(yán)重； 3、打破環(huán)

38、路等待條件：對資源進(jìn)行線性排序編號，要求每個進(jìn)程必須從低號到高號申請資源，而不考慮進(jìn)程實際申請資源的先后順序。,二、系統(tǒng)安全狀態(tài) 1、安全狀態(tài)：系統(tǒng)能按某種進(jìn)程順序（p1,p2,pn）序列，來為某個進(jìn)程pi分配其所需要資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 進(jìn)入不安全狀態(tài)，進(jìn)而會出現(xiàn)死鎖狀態(tài)，但并非所有不安全狀態(tài)都進(jìn)入死鎖狀態(tài)。 2、安全狀態(tài)舉例。,三、利用銀行家算法避免死鎖 1、數(shù)據(jù)結(jié)構(gòu)： （1）n個進(jìn)程對m 類資源的最大需求情況構(gòu)成最大需求矩陣Max； （2）分配矩陣Allocation表示當(dāng)前已經(jīng)分配的

39、資源情況； （3）目前還差多少資源就可運(yùn)行完畢構(gòu)成需求矩陣Need； （4）目前系統(tǒng)的 m類資源的可用數(shù)量Available一維數(shù)組。 Needi,j=Maxi,j- Allocationi,j,2、銀行家算法：主要用來判斷在當(dāng)前狀態(tài)下如果有進(jìn)程提出資源請求request，看是否能滿足該請求： a： 判斷請求的合法性，是否滿足小于NEED矩陣中的向量； b：請求的可滿足性判斷，是否小于available向量； c：試探分配，修改相應(yīng)的參數(shù)availableallocationneed; d：進(jìn)行安全性檢查，若分配后安全，則進(jìn)行分配，若判斷從此進(jìn)入了不安全狀態(tài)，則恢復(fù)原來數(shù)據(jù)，對進(jìn)程請求不予滿足

40、。,3、安全性算法檢查： （1）設(shè)定兩個向量work=available;finishi=true （2）從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：finishi=false;needij workj;若找到，執(zhí)行步驟3，否則執(zhí)行步驟4 （3）當(dāng)進(jìn)程pi獲得資源后，可順利執(zhí)行，直到執(zhí)行，并釋放出分配給它的資源 workj= workj+allocationij; finishi=true; Go to step2 (4) 如果所有進(jìn)程finishi=true都滿足，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)。,4、銀行家算法舉例。,（1）當(dāng)前狀態(tài)是否安全 （2）p1請求（1，0，2）是否可以分配。

41、 （3）p4請求（3，3，0）是否可以分配 （4）p0請求（0，2，0）是否可以分配,3.7死鎖的檢測與解除,一、死鎖的檢測 1、資源分配圖： 2、死鎖定理：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。該充分條件被稱為死鎖定理。 3、死鎖檢測算法。P100,二、死鎖的解除 1、剝奪資源 2、撤消進(jìn)程,第四章 存儲器管理,4.1 程序的裝入和鏈接 一、程序的執(zhí)行過程 （1）編譯 （2）鏈接 （3）裝入,二、程序的裝入 1、絕對裝入方式：編譯時知道程序駐留在內(nèi)存的什么位置，編譯后產(chǎn)生絕對地址的目標(biāo)代碼，將程序裝入內(nèi)存，程序的邏輯地址與實際物理地址完全相同，不需要進(jìn)行地址變換。絕對裝入方式只適用于單

42、道程序環(huán)境。 2、可重定位裝入方式：把裝入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。又因為地址變換通常是在裝入時一次完成的，以后不再改變，故稱為靜態(tài)重定位。不允許程序運(yùn)行時在內(nèi)存中移動位置。 3、動態(tài)運(yùn)行時裝入方式：采取動態(tài)重定位方式進(jìn)行地址變換。,三、程序的鏈接 1、靜態(tài)鏈接：程序運(yùn)行前先鏈接，再裝入內(nèi)存。 （1）對相對地址的改變 （2）變換外部調(diào)用符號 2、裝入時動態(tài)鏈接：裝入內(nèi)存時，邊裝入邊鏈接。 3、運(yùn)行時動態(tài)鏈接：某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行，用不到的模塊可以不調(diào)入內(nèi)存。,4.2連續(xù)分配方式,為程序分配一個連續(xù)的存儲空間。 一、單一連續(xù)分配技術(shù)：只能應(yīng)用與單用戶單任務(wù)操作系統(tǒng)

43、，如DOS，整個內(nèi)存空間除了常駐內(nèi)存的操作系統(tǒng)內(nèi)核所占的系統(tǒng)區(qū)外，其他都是分配給用戶程序的用戶區(qū)。,系統(tǒng)區(qū),用戶區(qū),二、固定分區(qū)分配方式：屬于最簡單的多道程序的存儲管理方式， 1、劃分分區(qū)的方法： （1）分區(qū)大小相等 （2）分區(qū)大小不等 分區(qū)的數(shù)量的確定也就決定了在內(nèi)存中只能安排多少程序同時存放和執(zhí)行。一個分區(qū)里只能放一個作業(yè)，不管剩余多少空間，都不能再分配給別的作業(yè)了。因此內(nèi)存利用率不會太高。,2、內(nèi)存分配：將各區(qū)建立一個分區(qū)使用表，表示分區(qū)號、分區(qū)的大小、分區(qū)的起始地址以及分區(qū)的狀態(tài)（即已分配還是未分配），作為將來分配給作業(yè)的一個數(shù)據(jù)結(jié)構(gòu)。 三、動態(tài)分區(qū)分配 1、分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)：主要有

44、空閑分區(qū)表或者空閑分配鏈，把每個空閑分區(qū)的序號、大小和其始地址，作為一個表目存放在空閑分區(qū)表或鏈結(jié)點內(nèi)，作為分配的依據(jù)。 2、分區(qū)分配算法：,（1）首次適應(yīng)算法：把空閑分區(qū)按地址遞增的順序排列，從第一個分區(qū)開始搜索到第一個滿足作業(yè)需求的分區(qū)進(jìn)行分配，剩余的空間作為新的空閑區(qū)，將來仍然作為分配對象。缺點，每次都從地址低的部分進(jìn)行搜索，低址部分會比較瑣碎，增加系統(tǒng)開銷。 （2）循環(huán)首次適應(yīng)算法，在首次適應(yīng)算法基礎(chǔ)上下一個作業(yè)的搜索從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，該算法會使空閑分區(qū)比較均勻，但缺少大分區(qū)。,（3）最佳適應(yīng)算法：將空閑分區(qū)按大小遞增的順序排列，每次選擇最恰當(dāng)?shù)姆謪^(qū)分配給作

45、業(yè)，但剩余的空間往往是最小的，有可能因為太小就不能滿足任何一個作業(yè)的內(nèi)存需求而造成浪費，我們稱之為內(nèi)存“零頭”或者“碎片”。 （4）最壞適應(yīng)算法：要求空閑分區(qū)按地址遞減的順序排列，每次選取最大的空閑分區(qū)分配給作業(yè)，因為由此剩下的空閑區(qū)也是最大的，更容易分配出去，但會缺乏大分區(qū)。,4、分區(qū)分配操作 （1）分配內(nèi)存：參考P110圖4-6 （2）回收內(nèi)存：當(dāng)一個作業(yè)執(zhí)行完畢，釋放內(nèi)存空間時，需要涉及和前后空閑區(qū)的合并問題，若回收區(qū)前面是一個空閑區(qū)的，則只修改前空閑區(qū)的大小就可以合并了，若回收區(qū)后面是空閑區(qū)，則需修改后面空閑區(qū)的大小和起始地址進(jìn)行合并，若回收區(qū)前后都是空閑區(qū)，則回收就要三者合并，將第一

46、空閑區(qū)的大小修改，刪除后面一個空閑分區(qū)表項，造成總的空閑分區(qū)表數(shù)量減1，若回收區(qū)上下都沒有空閑區(qū)，則在空閑分區(qū)表中添加一個新的表項。,五、可重定位分區(qū)分配 1、動態(tài)重定位的引入 （1）“零頭”或“碎片” （2）“拼接”或“緊湊” 2、動態(tài)重定位的實現(xiàn)：地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動進(jìn)行的，故稱動態(tài)重定位。 3、動態(tài)重定位的分區(qū)分配算法。參考P112圖4-10,六、對換： 所謂對換是把內(nèi)存中暫時不運(yùn)行的進(jìn)程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入到內(nèi)存。對換是提高內(nèi)存利用率的有效措施。,4 .3

47、 基本分頁存儲管理方式,一、頁面與頁表 1、頁面、塊：將一個進(jìn)程的邏輯地址分成若干個大小相等的片，稱為頁面或頁。每個頁面從0開始編號，同時將內(nèi)存空間也分成與頁面大小相等的物理塊，也稱為頁框或塊。 2、頁面大?。好總€頁面大小是1KB，2KB或者4KB，都是2的冪， 3、頁表：為了實現(xiàn)頁面與物理塊的對應(yīng)，引入一張頁面和它存儲的物理塊的映射表稱為頁表。頁表中主要有頁號和它對應(yīng)的物理塊號兩項，,4、地址結(jié)構(gòu) （1）根據(jù)頁面大小，從邏輯地址的低位確定出頁內(nèi)偏移量，剩余二進(jìn)制位表示頁號。從而將邏輯地址分解成兩部分。如P114 （2）數(shù)學(xué)計算公式： p=int(A/L) d=A%L p表示頁號，d表示頁內(nèi)偏

48、移量。,已知頁面大小為1024字節(jié)，邏輯地址分別是1011，2148，3000。4000。5012,答案：3059，1124，1976，7072，邏輯地址非法,二、地址變換機(jī)構(gòu) 1、基本地址變換機(jī)構(gòu)：在進(jìn)程沒有執(zhí)行前，頁表在內(nèi)存的起始地址和頁表的長度存儲在進(jìn)程的PCB內(nèi)，當(dāng)進(jìn)程獲得執(zhí)行后，頁表起始地址和頁表長度放到了頁表寄存器內(nèi) 。 2、基本地址變換過程： 首先將邏輯地址轉(zhuǎn)換為p和d兩部分，根據(jù)頁表寄存器內(nèi)頁的長度判斷該頁號是否屬于越界訪問，若沒有越界，根據(jù)頁表在內(nèi)存的起始地址找到頁表，查找到該頁對應(yīng)的索引項，得出該頁號對應(yīng)的實際物理塊，同時，頁內(nèi)偏移量同時也是物理塊的偏移量，因此，物理塊號*

49、塊的大小（1KB或4KB）+偏移量=實際物理地址；或者物理塊號的二進(jìn)制編碼加上偏移量的二進(jìn)制代碼表示組成實際物理地址。,3、具有快表的地址變換機(jī)構(gòu) （1）快表：聯(lián)想寄存器，在地址變換機(jī)構(gòu)中增設(shè)的具有并行查尋能力的特殊的高速緩沖寄存器，用以存放當(dāng)前訪問的那些頁表項。 （2）地址變換過程：給出邏輯地址后，先到快表中查找索引項，若有，直接地址變換就可以形成物理地址而不用訪問主存了，若快表中沒有，再到內(nèi)存去查找頁表，從中找到物理塊號進(jìn)行地址變換，但同時要把該索引項重新寫到聯(lián)想寄存器內(nèi)，若已滿，則換出認(rèn)為不再需要的索引項。這樣，根據(jù)程序執(zhí)行的局部原理，90%的檢索頁表索引項的過程可以在聯(lián)想寄存器內(nèi)實現(xiàn)，

50、從而提高檢索效率。,4.4基本分段存儲管理方式,一、分段存儲管理方式的引入 1、方便編程 2、信息共享 3、信息保護(hù) 4、動態(tài)增長 5、動態(tài)鏈接,二、分段系統(tǒng)的基本原理 1、分段：將作業(yè)的邏輯地址空間分為若干個段，每個段內(nèi)定義一組邏輯信息。作業(yè)的地址空間分為段號（名）+段內(nèi)地址兩部分。 2、段表：將不同的段分配到內(nèi)存不連續(xù)的存儲空間，當(dāng)然，具體每個段，因為長度可能不同，但是需連續(xù)的存儲空間，因此，段表內(nèi)需確定段號、段的長度、段在內(nèi)存的起始地址。,3、地址變換機(jī)構(gòu) 給定邏輯地址（段號S和段內(nèi)地址d），先拿段號和段表寄存器內(nèi)的段的長度進(jìn)行比較，看是否越界，然后拿段表寄存器的起始地址到段表中檢索到該

51、段段表項，根據(jù)段的長度與邏輯地址的段內(nèi)地址進(jìn)行比較，再次判斷是否越界，若沒有越界，根據(jù)段的內(nèi)存的基地址加上段內(nèi)地址d形成實際物理地址。也需要兩次訪問內(nèi)存，也可以引入聯(lián)想寄存器。,邏輯地址:0,430 1,10 2,500 3,400 4,112 5,32,答案:640 1360 非法 1750 非法,4、分頁與分段區(qū)別： （1）頁是信息的物理單位，為了提高內(nèi)存利用率引入的；段是信息的邏輯單位，是考慮用戶編程需要分成的段。 （2）頁的大小固定，段的大小不確定 （3）頁的邏輯地址是1維的，段的邏輯地址是2維的。 二、信息共享 參考P122 分段存儲管理方式與分頁存儲管理方式比較更方便于實施信息共享

52、。,二、段頁式存儲管理方式 1、基本原理：首先用戶程序分成若干個段，每個段內(nèi)再實施分頁，為每個段賦予一個段名。在段頁式系統(tǒng)中，其地址結(jié)構(gòu)由段號、段內(nèi)頁號及頁內(nèi)地址三部分組成。 2、地址變換過程（詳細(xì)見P124圖4-22）,4.5虛擬存儲器的基本概念,一、虛擬存儲器的引入 1、常規(guī)存儲器的特征 （1）一次性 （2）駐留性 2、程序執(zhí)行的局部性原理 （1）時間的局限性 （2）空間的局限性,3、虛擬存儲器的定義 所謂虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定的。 二、虛擬存儲器的實現(xiàn)方法 1、分頁請求系統(tǒng) 2、請求

53、分段系統(tǒng),三、虛擬存儲器的特征 1、多次性 2、對換性 3、虛擬性,4.6請求分頁存儲管理方式,一、請求分頁中的硬件支持 1、頁表機(jī)制 在原來頁號和物理塊號的基礎(chǔ)上增加輔助項，狀態(tài)位（0表示在外存，沒有調(diào)入，1表示在內(nèi)存）；訪問字段（一段時間內(nèi)訪問次數(shù)或是否被訪問過，供頁面置換出去時參考）；修改位（一段時間內(nèi)是否被修改過，置換時需要回寫到外存對換區(qū)）；外存地址（將來調(diào)入內(nèi)存時使用）； 2、缺頁中斷機(jī)構(gòu),3、地址變換機(jī)構(gòu)參考P130圖4-24,二、內(nèi)存分配策略和分配算法 1、最小物理塊的確定 保證進(jìn)程正常運(yùn)行所需要的最小物理塊數(shù)。 2、物理塊的分配策略 （1）固定分配局部置換 （2）可變分配全局

54、置換 （3）可變分配局部置換,3、物理塊分配算法 （1）平均分配算法 （2）按比例分配算法 （3）考慮優(yōu)先權(quán)的分配算法 三、調(diào)頁策略 1、何時調(diào)入頁面 2、從何處調(diào)入頁面 3、頁面調(diào)入過程,4.7頁面置換算法,一、最佳置換算法（OPT）和先進(jìn)先出置換算法 1、 OPT 算法：選擇被淘汰的頁面是以后永不使用或者最長時間內(nèi)不被執(zhí)行的頁面，因為將來的事情不可預(yù)知，所以不可實現(xiàn)。 2、先進(jìn)先出置換算法（FIFO），完全考慮進(jìn)入內(nèi)存的先后時間； 頁面引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,二、最近最久未使用（LRU）算法： 1、 LRU算法：選擇淘汰頁面選

55、擇最近最久未使用的頁面予以淘汰。 2、LRU置換算法的硬件支持 （1）移位寄存器法 （2）棧,三、Clock置換算法 1、簡單的Clock置換算法：只考慮訪問位的情況作為置換頁面的依據(jù)。 2、改進(jìn)型Clock置換算法：除考慮訪問位之外，增加考慮修改位的情況。 四、其它頁面置換算法 1、最少使用置換算法 2、頁面緩沖算法,4.8請求分段存儲管理方式,一、請求分段中的硬件支持 1、段表機(jī)制 在段號、段長、段的基地址的基礎(chǔ)上，增加存取方式、訪問字段、修改位、存在位、增補(bǔ)位以及外存地址。存取方式主要是只讀、可寫、可讀寫等對段實施保護(hù)，訪問字段確定被訪問的次數(shù)，存在位表示是否在內(nèi)存，修改位同樣是供置換參

56、考。增補(bǔ)位表示該段是否動態(tài)增長過，外存地址同樣是在外存的盤塊號。,2、缺段中斷機(jī)構(gòu) 3、地址變換機(jī)構(gòu) 二、分段的共享與保護(hù) 1、共享段表 2、共享段的分配與回收 3、分段保護(hù),第五章 設(shè)備管理,5.1 I/O系統(tǒng) 一、I/O設(shè)備 1、按傳輸速率分類： （1）低速設(shè)備：每秒幾個字節(jié)至數(shù)百字節(jié)，鍵盤、鼠標(biāo)、語音的輸入、輸出設(shè)備 （2）中速設(shè)備：每秒數(shù)千字節(jié)至數(shù)萬字節(jié)的設(shè)備，如行式、激光打印機(jī) （3）高速設(shè)備：數(shù)百千字節(jié)至數(shù)十兆字節(jié)，磁帶機(jī)、磁盤機(jī)、光盤機(jī)。,2、按信息交換單位分類 （1）塊設(shè)備。存儲信息以數(shù)據(jù)塊為基本單位，典型設(shè)備為磁盤，傳輸速度快，可尋址，I/O控制方式為DMA方式 （2）字符設(shè)

57、備。打印機(jī)等，傳輸速度低，以字符為傳送單位，不可尋址，采用中斷驅(qū)動方式。 3、按設(shè)備的共享屬性分類 （1）獨占設(shè)備、 （2）共享設(shè)備 （3）虛擬設(shè)備,二、設(shè)備控制器 設(shè)備控制器是在CPU和I/O設(shè)備之間的接口，一個設(shè)備控制器控制幾個設(shè)備。 1、設(shè)備控制器的組成： （1）設(shè)備控制器與處理機(jī)的接口 （2）設(shè)備控制器與設(shè)備的接口 （3）I/O邏輯,2、設(shè)備控制器的功能 （1）接收和識別命令 （2）數(shù)據(jù)交換 （3）標(biāo)識和報告設(shè)備的狀態(tài) （4）地址識別 （5）數(shù)據(jù)緩沖 （6）差錯控制,三、通道 1、通道是特殊的處理機(jī)，是專門通過執(zhí)行內(nèi)存中的通道程序來控制I/O操作的可與CPU同時工作的處理機(jī)，指令單一，

58、只去實現(xiàn)控制I/O過程的。 2、I/O系統(tǒng) （1）主機(jī)系統(tǒng)：整個主機(jī)中的I/O系統(tǒng)包括了三級控制，四級連接，即內(nèi)存、通道、設(shè)備控制器及設(shè)備。 （2）微機(jī)系統(tǒng)：沒有通道，因此采取CPU與內(nèi)存通過總線結(jié)構(gòu)與設(shè)備控制器連接。,3、“瓶頸”問題： （1）一個通道連接多個設(shè)備控制器，一個控制器連接多個設(shè)備，這樣在實際通路中因為設(shè)備控制器和通道數(shù)量的遞減從而在構(gòu)造數(shù)據(jù)通路的時候出現(xiàn)一種“瓶頸“現(xiàn)象，越向內(nèi)存數(shù)量越少。 （2）解決瓶頸問題的有效方法是增加通路而不增加通道，因為通道價格昂貴，可以將一個設(shè)備連接多個控制器，一個控制器連接多個通道，從而盡可能的增加通路。,5.2I/O控制方式,一、程序I/O方式

59、處理機(jī)向控制器發(fā)出I/O指令啟動設(shè)備輸入數(shù)據(jù)時，把busy信號設(shè)定為1，以后不斷循環(huán)檢測該信號，當(dāng)設(shè)備控制器輸入數(shù)據(jù)完成，修改信號為0,由CPU將該數(shù)據(jù)送入內(nèi)存。,二、中斷驅(qū)動I/O控制方式 CPU發(fā)送指令給設(shè)備控制器后，轉(zhuǎn)而做別的工作去，每接受一個字符到設(shè)備控制器的數(shù)據(jù)寄存器后，就發(fā)中斷給CPU，要CPU放數(shù)據(jù)入內(nèi)存。例如打印機(jī)等字符設(shè)備采取該中斷驅(qū)動方式。 三、直接存儲器訪問DMA I/O控制方式 1、DMA控制方式的引入： 塊設(shè)備的專門的控制器就是DMA控制器，通過控制器接收設(shè)備來的數(shù)據(jù)直接送數(shù)據(jù)進(jìn)入內(nèi)存的存儲單元中，不用CPU干涉，只是到連續(xù)盤塊的數(shù)據(jù)全部輸入或輸出完成后才發(fā)中斷給CPU）。,（1）數(shù)據(jù)傳輸基本單位是數(shù)據(jù)塊 （2）所傳送的數(shù)據(jù)是從設(shè)備直接送入內(nèi)存或者相反 （3）僅在傳輸一個或多個數(shù)據(jù)塊的開始或結(jié)束時，才需要CPU干預(yù)。 2、DMA控制器的組成： 主機(jī)與DMA控制器的接口；DMA控制器與塊設(shè)備的接口、I/O控制邏輯 四類寄存器： （1）命令/狀態(tài)寄存器CR （2）內(nèi)存地址寄存器MAR （3）數(shù)據(jù)寄存器DR （4）數(shù)據(jù)計