操作系統(tǒng)重點知識匯總（1）

操作系統(tǒng)重點 第一 章 有效性（系統(tǒng)管理人員的觀點） ;方便性（用戶的觀點）；可擴(kuò)充性（開放的觀點）；開放性 儲器、外部設(shè)備、信息（數(shù)據(jù)和軟件）； 源的當(dāng)前狀態(tài)（數(shù)量和使用情況）、資源的分配、回收和訪問操作，相應(yīng)管理策略（包括用戶權(quán)限） 統(tǒng)對作業(yè)的處理是成批進(jìn)行的，內(nèi)存中始終保持一道作業(yè) 動性；順序性；單道性 ：提高 利用率；可提高內(nèi)存和 I/O 設(shè)備利用率；增加系統(tǒng)吞吐量。 7.*多道批處理系統(tǒng)的優(yōu)缺點：資源利用率高；作業(yè)吞吐量大；用戶交互性差；作業(yè)平均周轉(zhuǎn)時間長 一臺主機(jī)上連接了多個帶有顯示器和鍵盤的終端，同時允許許多個用戶通過自己的終端，以交互方式使用用計算機(jī)，共享主機(jī)中的資源 路性；獨立性；及時性；交互性 統(tǒng)能及時響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致地運行 路性：（實時控制系統(tǒng)的多路性主要表 現(xiàn)在系統(tǒng)周期性地對多路現(xiàn)場信息進(jìn)行采集，以及對多個對象或多個執(zhí)行機(jī)構(gòu)進(jìn)行控制，分時系統(tǒng)中的多路性則與用戶情況有關(guān)時多時少）獨立性：（實時信息處理系統(tǒng)中的每個終端用戶在向?qū)崟r系統(tǒng)提出服務(wù)請求時是彼此獨立操作地互不干擾，實時控制系統(tǒng)中，對信息的采集和對象的控制也都是彼此互不干擾）及時性： (實時信息處理系統(tǒng)對實時性的要求和分時性系統(tǒng)類似，都是以人所能接受的等待時間來確定的，而實時控制系統(tǒng)的及時性則是以控制對象所要求的開始截止時間或完成時間來確定的，一般為秒級到毫秒級，甚至有的要低于 100 微妙 )交互性： (實時信息處 理系統(tǒng)雖然也具有交互性但這里人與系統(tǒng)的交互僅限于訪問系統(tǒng)中某些特定的專用服務(wù)程序，它不像分時系統(tǒng)那樣能向終端用戶提供數(shù)據(jù)處理和資源共享等服務(wù) )可靠性： (分時系統(tǒng)雖然也要求系統(tǒng)可靠但相比之下實時系統(tǒng)則要求具有高度上午可靠性 ) 并發(fā)性：是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生 *并行性 (指兩個或多個事件在同一時刻發(fā)生。 共享性：多個進(jìn)程共享有限的計算機(jī)系統(tǒng)資源 方式分為：互斥共享方式（如音頻設(shè)備）資源分配后到釋放前不能被 其他進(jìn)程所用； 同時訪問方式（如可重入代碼，磁盤文件） 虛擬技術(shù)：指通過某種技術(shù)（分時或分空間）把一個物理實體映射為 若干個對應(yīng)的邏輯實體。 實現(xiàn)方式包括：時分復(fù)用技術(shù)：虛擬處理機(jī)技術(shù)、虛擬設(shè)備技術(shù)； 空分復(fù)用技術(shù)：虛擬磁盤技術(shù)、虛擬存儲器技術(shù) 異步性：進(jìn)程是以人們不可預(yù)知的速度向前推進(jìn)。 擬以并發(fā)和共享為前提；異步性是并發(fā)和共享的必然結(jié)果 理機(jī)管理；存儲管理；設(shè)備管理信息管理；用戶接口 用戶接口：包括聯(lián)機(jī)用戶接口，脫機(jī)用戶接口、圖形接口用戶接口； 程序接口 第二章 進(jìn)程管理 1、程序：是一組有序指令的集合，有存放于某種介質(zhì)上，其本身并不具有運 動的含義，是靜態(tài)的 2、進(jìn)程的特征： （ 1）結(jié)構(gòu)特征：為使程序（含數(shù)據(jù)）能獨立運行，應(yīng)為之配置一進(jìn)程控制塊（ 由程序段、相關(guān)的數(shù)據(jù)段和 （ 2）動態(tài)性：進(jìn)程的實質(zhì)是進(jìn)程實體的一次執(zhí)行過程，是進(jìn)程的最基本的特征，進(jìn)程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡 （ 3）并發(fā)性：指多個進(jìn)程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運行 （ 4）獨立性：指進(jìn)程實體是一個能獨立運行、獨立分配資源和獨立接受調(diào)度的基本單位 （ 5）異步性：指進(jìn)程按各自獨立的、不可預(yù)知的速度向前推進(jìn)，或說進(jìn)程實體按異步 方式運行 3、程序和進(jìn)程的區(qū)別：程序是靜態(tài)的，不能并發(fā)執(zhí)行；進(jìn)程是動態(tài)的，能夠并發(fā)執(zhí)行 4 (1) (2) (3) 進(jìn)程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。 (4) 進(jìn)程是進(jìn)程實體的運行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位 5、進(jìn)程的三種基本狀態(tài)（記?。?（ 1）就緒狀態(tài)：當(dāng)進(jìn)程已分配到除以外的所有必要資源后，只要再獲得，便可立即執(zhí)行， 進(jìn)程這時的狀態(tài)稱為就緒狀態(tài) （）執(zhí)行狀態(tài)：進(jìn)程已獲得，其程序正在運行 （）阻塞狀態(tài)：正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機(jī)而處于暫停狀態(tài)，亦即進(jìn)程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)。致使進(jìn)程阻塞的典型事件有：請求，申請緩沖空間等 6、進(jìn)程控制塊：是進(jìn)程實體的一部分，操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。其作用是使一個在多道程序環(huán)境下不能獨立運行的程序 (含數(shù)據(jù) )，成為一個能獨立運行的基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f， 根據(jù) 對并發(fā)執(zhí)行的 進(jìn)程進(jìn)行控制和管理的。 7、原語：是由若干條指令組成的，用于完成一定功能的一個過程。 原子操作：一個操作中的所有動作要么全做，要么全不做，是一個不可分割的基本單位 8、（ 1）引起進(jìn)程阻塞和喚醒的事件： 1）請求系統(tǒng)服務(wù) 2) 啟動某種操作 3) 新數(shù)據(jù)尚未到達(dá) 4) 無新工作可做 （ 2）進(jìn)程阻塞：正在執(zhí)行的進(jìn)程，當(dāng)所請求的某事件沒出現(xiàn)時，由于無法繼續(xù)執(zhí)行，于是進(jìn)程便通過調(diào)用阻塞原語自己阻塞。進(jìn)程阻塞是進(jìn)程自身的一種主動行為。 (3) 程喚醒：當(dāng)被阻塞進(jìn)程所期待的事 件出現(xiàn)時，如 I/O 完成或其所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程 (比如，用完并釋放了該 I/O 設(shè)備的進(jìn)程 )調(diào)用喚醒原語 )，將等待該事件的進(jìn)程喚醒。 9、進(jìn)程同步：是對多個相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。 10、臨界資源：臨界資源是指每次僅允許一個進(jìn)程訪問的資源。如打印機(jī)、磁帶機(jī)等都屬于臨界資源。諸進(jìn)程間應(yīng)采取互斥方式，實現(xiàn)對這種資源的共享。 11、臨界區(qū)：把在每個進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū) 12、同步機(jī)制應(yīng) 遵循的四條規(guī)則：（ 1）空閑讓進(jìn) (2) 忙則等待 (3) 有限等待 (4) 讓權(quán)等待 13、信號量機(jī)制 （ 1）整型信號量：一個用于表示資源數(shù)目的整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作 ()和 )來訪問。 （ 2）記錄型信號量：一種采取了“讓權(quán)等待”的策略使進(jìn)程不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。除了需要一個用于代表資源數(shù)目的整型變量 ，還應(yīng)增加一個進(jìn)程鏈表 L，用于鏈接上述的所有等待進(jìn)程。 14、經(jīng)典進(jìn)程的同步問題：生產(chǎn)者 消費者問題 結(jié)合 課后練習(xí)復(fù)習(xí)） 15、進(jìn)程通信：指進(jìn)程之間的信息交換，其所交換的信息量少者是一個狀態(tài)或數(shù)值，多者則是成千上萬個字節(jié)。 16、管道機(jī)制提供的三方面協(xié)調(diào)能力：（ 1）互斥 （ 2）同步 （ 3）確定對方是否存在，只有確定了對方已存在時，才能進(jìn)行通信 17、線程：不擁有系統(tǒng)資源，能獨立運行的基本單位，也是獨立調(diào)度和分派的基本單位。 第三章 處理機(jī)調(diào)度的層次 ：（運行頻率：低級調(diào)度 中級調(diào)度 高級調(diào)度） 業(yè)調(diào)度、長程調(diào) 度、接納調(diào)度）：將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建 ，插入就緒隊列。 一般用于批處理系統(tǒng)，分 /實時系統(tǒng)一般直接入內(nèi)存，無此環(huán)節(jié)。 程調(diào)度，短程調(diào)度） 主要是決定就緒隊列中的哪個進(jìn)程應(yīng)獲得處理機(jī)，然后由分派程序（ 派處理機(jī)。 兩種調(diào)度方式： 1)非搶占方式：簡單、系統(tǒng)開銷小，實時性差 (如 2)搶占方式：（ 1）優(yōu)先權(quán)原則（ 2）短進(jìn)程優(yōu)先原則（ 3）時間片原則 程調(diào)度）：為提高系統(tǒng)吞吐量和內(nèi)存利用率而引入的一 內(nèi) 出時，進(jìn)程為掛起 或就緒駐外存狀態(tài)） 面向用戶的準(zhǔn)則 （ 1）周轉(zhuǎn)時間短（常用于批處理系統(tǒng)） 概念：作業(yè)從提交到完成的時間 外存等待調(diào)度時間；駐內(nèi)存等待調(diào)度時間；執(zhí)行時間；阻塞時間 平均周轉(zhuǎn)時間： 平均帶權(quán)時間： （可見帶權(quán) w 越小越好 ,實際服務(wù)時間。） 面向系統(tǒng)的準(zhǔn)則 （ 1）吞吐量高（特別是批處理）：單位時間完成作業(yè)數(shù) （ 2）處理機(jī)利用率好：（因 ，特別是大中型多用戶系統(tǒng)） （ 3）各類資源的平衡利用。 先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 點：簡單，有利于長作業(yè)（進(jìn)程） 即 忙性作業(yè) ,不利于短作業(yè)（進(jìn)程） 程）優(yōu)先調(diào)度算法 ： )F 提高了平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間（從而提高了系統(tǒng)吞吐量） 特點：對長作業(yè)不利，有可能得不到服務(wù) 估計時間不易確定 計算：帶權(quán)周轉(zhuǎn)時間 =周轉(zhuǎn)時間 /服務(wù)時間；完成時間： 順序完成作業(yè)， 成第一個作業(yè)后選擇服務(wù)時間最短的作業(yè)依次完成； 11 ni n ii 型： 1）非搶占式優(yōu)先權(quán)算法 2）搶占式優(yōu)先權(quán)算法，實時性更好。 優(yōu)先權(quán)類型： 1）靜態(tài)優(yōu)先權(quán)：進(jìn)程優(yōu)先權(quán)在整 個運行期不變。 特點：簡單，但低優(yōu)先權(quán)作業(yè)可能長期不被調(diào)度（饑餓）。 2）動態(tài)優(yōu)先權(quán)：進(jìn)程優(yōu)先級可隨進(jìn)程的推進(jìn)或等待時間的增加而改變。 優(yōu)點：長短兼顧 缺點：需經(jīng)常計算各進(jìn)程優(yōu)先級 高響應(yīng)比優(yōu)先調(diào)度算法：（短作業(yè) ） 響應(yīng)比 s） /等待時間 +要求服務(wù)時間） /要求服務(wù)時間 =優(yōu)先權(quán) =響應(yīng)時間 /要求服務(wù)時間 系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求 時間片大小的確定：太大：退化為 ?。合到y(tǒng)開銷過大 作業(yè)名 A B C D E 平均 到達(dá)時間 0 1 2 3 4 服務(wù)時間 4 3 4 2 4 RR q 1 完成時間 15 12 16 9 17 周轉(zhuǎn)時間 15 11 14 6 13 權(quán)周轉(zhuǎn)時間 R q 4 完成時間 4 7 11 13 17 周轉(zhuǎn)時間 4 6 9 10 13 權(quán)周轉(zhuǎn)時間 1 2 間片大小不同時帶權(quán)周轉(zhuǎn)時間于完成時間也不同； 實時調(diào)度 ：對用戶的實時響應(yīng) 實現(xiàn)實時調(diào)度 的基本條件 1提供必要 的調(diào)度信息 （ 1）就緒時間；（ 2）開始 /完成截止時間；（ 3）處理時間；（ 4）資源要求；（ 5）優(yōu)先級； 2系統(tǒng)處理能力強(qiáng) 1）剝奪方式：一般都采用此方式 2）非剝奪方式（實現(xiàn)簡單）：一般應(yīng)使實時任務(wù)較小，以及時放棄 1）具有快速響應(yīng)外部中斷能力。 2）快速任務(wù)分派 死鎖： 指多個進(jìn)程在運行過程中因爭奪資源而造成的一種僵局。 產(chǎn)生死鎖的原因。 1、競爭資源引起死鎖。 產(chǎn)生死鎖的必要條件 1）互斥條件（資源的臨界性） 2）請 求和保持條件 3）不剝奪條件 4）環(huán)路等待條件 處理死鎖的基本方法 1預(yù)防死鎖： 破壞 4 個條件之一：有效，使資源利用率低。 2避免死鎖：防止進(jìn)入不安全態(tài)。 3檢測死鎖：檢測到死鎖再清除。 4解除死鎖：與 “檢測 ”配套。 1、）互斥條件是資源固有屬性，不能避免。 2、）摒棄請求和保持條件 3、）摒棄 “不剝奪 ”條件，增加系統(tǒng)開銷，且進(jìn)程前段工作可能失效。 4、）摒棄 “環(huán)路 ”條件 有序資源分配法：為資源編號，申請時需按編號進(jìn)行。 缺點：（ 1）新增資源不便，（原序號已排定）（ 2）資源與進(jìn)程使用順序 不同造成浪費 （ 3）用戶不自由 在 “避免死鎖 ”方法中的判斷條件 安全狀態(tài)： 能找到安全序列的狀態(tài)為安全狀態(tài)。 （ 系統(tǒng)按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序完成的序列為安全序列。） 例： 進(jìn)程 最大需求 已分配 可用 0 5 3 2 2 安全序列： 銀行家算法避免死鎖 j=k: 系統(tǒng)現(xiàn)有 資源 k 個； i,j=k: 進(jìn)程 i 需要 最大數(shù) k 個； i,j=k: 進(jìn)程 i 已得到 資源 k 個； i,j=k: 進(jìn)程 i 需要 資源 k 個 有： i,j= i,j i,j （ 程 i 請求資源數(shù)； 程 i 執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)） i：布爾量，表進(jìn)程 i 能否順序完成。 ） 分配； 分配 求 =i= i= 直到進(jìn)程的 i都為 系統(tǒng)處于安全狀態(tài) 死鎖的解除 1） 剝奪資源。 2) 撤消進(jìn)程。 第四章 現(xiàn)代計算機(jī)結(jié)構(gòu)中的一重要部件，其容量大于或遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個數(shù)量級左右，從幾十 幾 問速度快于主存儲器 . 身并不是一種實際存在的存儲介質(zhì)，它依托于固定磁盤，提供對主存儲空間的擴(kuò)充，即利用主存中的存儲空間，來暫存從磁盤中讀出（或?qū)懭耄┑男畔ⅰ?1 絕對裝入方式：編譯后，裝入前已產(chǎn)生了絕對地 址（內(nèi)存地址），裝入時不再作地址重定位 ,適用于單道系統(tǒng)。 2 可重定位裝入方式：靜態(tài)重定位：裝入時完成，主要工作是對相對地址中的指令和數(shù)據(jù)地址的調(diào)整過程；可重定位裝入方式在裝入后不能移動程序 3 動態(tài)運行時裝入方式：該情況一般在執(zhí)行時才完成相對和絕對地址的轉(zhuǎn)換且有硬件的支持 ,能保證進(jìn)程的可移動性 1 單一連續(xù)分配：是最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。可把內(nèi)存分為系統(tǒng)和用戶兩個部分系統(tǒng)區(qū)僅提供給 用，通常是放在內(nèi)存的低址部分，用戶區(qū)是系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。 2 固定分區(qū)分配：是最簡單的一種可運行多道程序的存儲管理方式，是將內(nèi)存用戶空間分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)，這樣把用戶空間劃分為幾個分區(qū)，便允許有多到作業(yè)并發(fā)運行。特點：簡單，有碎片（內(nèi)零頭） ,浪費。劃分分區(qū)大小的方法：分區(qū)大小相等；分區(qū)大小不等。內(nèi)存分配：將分區(qū)按大小排序，建立分區(qū)使用表，并將其地址、分配標(biāo)識作記錄 3 動態(tài)分區(qū)分配：是根據(jù)進(jìn)程的實際需要，動態(tài)地為之分配內(nèi)存空間。 分區(qū)分配中常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式：空閑分區(qū)表；空閑分區(qū)。 分區(qū)分配算法： 1 首次適應(yīng)算法 求：空閑分區(qū)鏈以地址遞增的次序鏈接； 特點：找到第一個大小滿足的分區(qū)，劃分，有外零頭，低址內(nèi)存使用頻繁，增加系統(tǒng)開銷 2 循環(huán)首次適應(yīng)算法：從上次找到的空閑分區(qū)的下一個開始查找。 特點：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)。 3 最佳適應(yīng) 算法：每次分配內(nèi)存是總是把能滿足要求、又是最小的空閑區(qū)分配給作業(yè)，避免大材小用。分區(qū)按大小遞增排序；分區(qū)釋放時需插入到適當(dāng)位置 4 最壞適應(yīng)算法：選一個最大的空閑區(qū)分割給作業(yè)使用。優(yōu)點：使剩下的空閑區(qū)不至太小，產(chǎn)生碎片的幾率最小對中小作業(yè)有利，查找效率高。缺點：缺乏大的空閑分區(qū) 5 快速適應(yīng)算法：按空閑分區(qū)容量分類，對每類相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，管理索引表。優(yōu)點：查找效率高；缺點：算法復(fù)雜，系統(tǒng)開銷大。 要操作（分區(qū)分配操作）： 1 分配內(nèi)存：系統(tǒng)應(yīng)用某種算法，從空閑分區(qū)鏈（表）中找到所需大小的分區(qū) 2 回收內(nèi)存：上鄰空閑區(qū)：合并，改大小。下鄰空閑區(qū)：合并，改大小，首址。上、下鄰空閑區(qū)：合并，改大小。不鄰接，則建立一新表項。 把內(nèi)存中暫時不能運行的進(jìn)程或者暫時不用的程序和數(shù)據(jù)調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存。 類型：整體對換 /進(jìn)程對換： 一整個進(jìn)程為單位，應(yīng)該于解決內(nèi)存緊張 部分對換：頁面對換 /分段對換 /部分對換：是請求分段和請求分頁式存儲管理的基礎(chǔ)，提供虛存支持。 具備頁面對換功能，不具備支持現(xiàn)實虛擬存儲器的功能，要求把每個作業(yè)全部妝容內(nèi)存后方可運行。 頁面或頁：將一個進(jìn)程的邏輯地址空間分成若干個大小相等的片，并為各頁加以編號； L O A D 1 , 2 5 0 03 6 501 0 02 5 0 05 0 0 02 5 0 0相 對 地 址1 0 0 0 0重 定 位 寄 存 器L O A D 1 , 2 5 0 03 6 51 0 0 0 01 0 1 0 01 2 5 0 01 5 0 0 0作 業(yè) 機(jī) 一 側(cè) 存 儲 器 一 側(cè)主 存物理塊或頁框：把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，并為它們加以編號； 地址結(jié)構(gòu)： 31 12 11 0 頁號 P 位移量 W 頁號 P；邏輯地址 A；頁面大小 L； 頁內(nèi)地址 d P= d=A 例如，系統(tǒng)的頁面大小為 1 A=2170B，求頁號和頁內(nèi)地址。 解： 110B=1024B 頁號 P=170/1024=2 頁內(nèi)地址 d=217022 實現(xiàn)從頁號到物理塊號的地址映射。 現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，見 4 具快表，則需兩次訪問內(nèi)存：第一次訪問頁表；第二次訪問得到絕對地址內(nèi)容。 為了提高地址變換速度 ，可在地址變換機(jī)構(gòu)中增設(shè)一個具有并行查尋能力的特殊高速緩沖器，又稱為“聯(lián)想寄存器”或“快表”。 輯地址結(jié)構(gòu)可描述如下： 外層頁號 外層頁內(nèi)地址 頁內(nèi)地址 2 d 31 22 21 12 11 0 要看得懂就行） 分段和分頁原理的結(jié)合，即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名 ，即“先分段后分頁”。 了獲得一條指令或數(shù)據(jù)，須三次訪問內(nèi)存。第一次訪問段表取得頁表始址；第二次訪問頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問才是真正從第二次訪問所得的地址中，取出指令或數(shù)據(jù)。 1）多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運行。 （ 2）對換性：允許在作業(yè)的運行過程中進(jìn)行換進(jìn)、換出。 （ 3）虛擬性：能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實際內(nèi)存容量。 求分頁存儲管理方式： 1，請求分頁中的硬件支持：一定容量的內(nèi)存，外存的計算機(jī)系統(tǒng)，還需要頁表機(jī)制，缺頁中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)。 2、頁面分配和置換策略。 1）固定分配局部置換。缺點：難以確定固定分配的頁數(shù) .(少：置換率高 多：浪費 ) 2）可變分配全局置換 3）可變分配局部置換根據(jù)進(jìn)程的缺頁率進(jìn)行頁面數(shù)調(diào)整，進(jìn)程之間相互不會影響。 面置換算法： 1）最佳置換算法， 2）先進(jìn)先出（ 面置換算法 3）最近最久（ 使用置換算法 (要懂的這幾種算法的實現(xiàn)，看例題 ) 求分段存儲管理方 式： 1，請求分段管理所需的硬件支持有段表機(jī)制，缺段中斷機(jī)構(gòu)，以及地址變換機(jī)構(gòu) 2，在請求芬頓式管理中所需的主要數(shù)據(jù)結(jié)構(gòu)式段表。 第五章 設(shè)備管理 1、 I/O 設(shè)備的類型： 1）按設(shè)備的使用特性分類： （ 1）存儲設(shè)備 （ 2）輸入 /輸出設(shè)備 （ 3）交互式設(shè)備 2）按傳輸速率分類： （ 1）低速設(shè)備 如鍵盤、鼠標(biāo)器等 （ 2）中速設(shè)備 如打印機(jī) （ 3）高速設(shè)備 如磁帶機(jī) 3）按信息交換的單位分類： （ 1）塊設(shè)備 磁盤 ,可定位 （ 2）字符設(shè)備 打印機(jī) 4）按設(shè)備的共享屬性分類： （ 1）獨占設(shè)備。指一段時間內(nèi)質(zhì)循序一個用戶（進(jìn)程）訪問的設(shè)備。即臨界資源。 （ 2）共享設(shè)備。指在一段時間內(nèi)循序多個進(jìn)程同時訪問的設(shè)備。如磁盤。 （ 3）虛擬設(shè)備。指通過虛擬即使將一臺獨占設(shè)備變換為若干臺邏輯設(shè)備，供若干個用戶（進(jìn)程）同時使用。 2、 I/O 通道：是一種特殊的處理機(jī)，它具有執(zhí)行 I/O 指令的能力，并通過執(zhí)行通道（ I/O）程序來控制 I/O 操作。 引入的目的是為了建立獨立的 I/O 操作，解脫 I/O 的組織、管理。 3、 I/O 控制方式： 1）程序 I/O 方式：或稱為忙 在處 理機(jī)向控制器發(fā)出一條 I/O 指令啟動輸入設(shè)備輸入數(shù)據(jù)時，要同時把狀態(tài)寄存器中的忙 /閑標(biāo)志 為 1，然后不斷地循環(huán)測試 種方式 源浪費極大。 2）中斷驅(qū)動 I/O 控制方式：即當(dāng)某進(jìn)程要啟動某個 I/O 設(shè)備工作時，便由 相應(yīng)的設(shè)備控制器發(fā)出一條 I/O 命令，然后立即返回繼續(xù)執(zhí)行原來的任務(wù)。 這種方式用于字符設(shè)備 I/O。 3）直接存儲器訪問（ I/O 控制方式：用于塊設(shè)備的 I/O。 4、單緩沖：（簡單了解原理） 工作區(qū)處理 ( C )緩沖區(qū)傳送 ( M ) 輸入 ( T )I / O 設(shè)備( a )T 1M 1C 1T 2M 2C 2T 3M 3C 3T 4t( b )用戶進(jìn)程 塊設(shè)備輸入時（圖 a），系統(tǒng)每一塊數(shù)據(jù) 的處理時間表示為 ,T)+M；字符設(shè)備輸入時 (圖 b)，緩沖區(qū)用于暫存用戶輸入的一行數(shù)據(jù)，在輸入期間，用戶進(jìn)程被掛起以等待數(shù)據(jù)輸入完畢，在輸出時，用戶進(jìn)程將一行數(shù)據(jù)輸入到緩沖區(qū)后，繼續(xù)進(jìn)行處理。 5、雙循環(huán) 在塊設(shè)備輸入時（圖 a），先將數(shù)據(jù)送入第一緩沖區(qū)，裝滿后便轉(zhuǎn)向第二緩沖區(qū)，此時操作系統(tǒng)可從第一緩沖區(qū)中移出數(shù)據(jù)，送入用戶進(jìn)程。系統(tǒng)處理一塊數(shù)據(jù)的時間可以粗略地認(rèn)為是 ,T)；對于字符設(shè)備（圖 b），用戶在輸入完第一行之后，在 行第一行中的命令時，用戶可向第二緩沖區(qū)輸入下一行數(shù)據(jù)。 6、循環(huán)緩沖 循環(huán)緩沖由多個緩沖區(qū)和多個指針組成。 6.（ 55 工作區(qū)用戶進(jìn)程緩沖區(qū) 1緩沖區(qū) 2 I / O 設(shè)備T 1 ( 緩沖 1 )M 1C 1M 2C 2M 3C 3T 2 ( 緩沖 2 ) T 3 ( 緩沖 3 )M 4C 4T 4 ( 緩沖 4 )( a )( b )3） 統(tǒng)： 概念：在聯(lián)機(jī)情況下同時出現(xiàn)外圍操作。 組成：輸入井和輸出井 輸入緩沖區(qū)和輸出緩沖區(qū) 輸入進(jìn)場 輸出進(jìn)程 點：提高 I/O 速度； 將獨占設(shè)備改造為共享設(shè)備； 實現(xiàn)了虛擬設(shè)備功能 （ 4） 磁盤的結(jié)構(gòu)和布局： 的圖 （ 5） 磁盤訪問時間： 1）尋道時間： TS=m*n+s m：常量， n：磁道數(shù)， s：磁臂啟動時間。 2）旋轉(zhuǎn)延時間 定扇區(qū)旋轉(zhuǎn)到磁頭下所需時間。 設(shè)每秒 r 轉(zhuǎn)，則 1/2r（均值） 3）數(shù)據(jù)傳輸時間 b/rN b：讀寫字節(jié)數(shù) N：每道上的字節(jié)數(shù) 訪問時間： s+1/2r+b/ 6） 磁盤調(diào)度 （ 1） 來先服務(wù) 特點：公平、簡單，尋道時間長，相當(dāng)于隨機(jī)訪問模式。 僅適用于請求磁盤 I/O 的進(jìn)程數(shù)目較少的場合。 （ 2）、 短尋道優(yōu)先）最短尋道時間優(yōu)先 更好的尋道性能 貪心的算法 饑餓現(xiàn)象 不能保證平均尋道時間最短 度算法 度算法 （ 3） 描算法（也稱為電 梯算法）。 法： 在移動方向固定的情況下采用了 避免饑餓現(xiàn)象 存在請求進(jìn)程等待延遲現(xiàn)象 （ 4）、循環(huán)掃描 頭單向移動 一個方向讀完，不是象 樣回頭，而是循環(huán)掃描。 請求延遲時間： 2T T+度算法示例 度算法示例 （ 7） 磁盤高速緩存 形式 ：邏輯上是磁盤、物理上是駐留在內(nèi)存中的盤塊 固定大小和可變大小 （ 8） 虛擬盤：利用內(nèi)存空間去仿真磁盤，又稱 和磁盤高速緩存區(qū)別：虛擬盤由用戶控制；磁盤高速緩存由系統(tǒng)控制。 第六章 一、文件類型 按用途分類：系統(tǒng)文件，用戶文件，庫文件。（用戶對以上三者的訪問權(quán)限不同） 按文件中的數(shù)據(jù)形式分類 ： 源文件，目標(biāo)文件，可執(zhí)行文件。 存取控制：只執(zhí)行文件，只讀文件，讀寫文件。 （ E， R， R/W） 按組織形式和處理方式分類：普通文 件，目錄文件，特殊文件。 二、最基本的文件操作：創(chuàng)建文件，刪除文件，讀文件，寫文件，截斷文件，設(shè)置文件的讀 /寫位置。 三、文件存在的兩種形式： 文件的邏輯結(jié)構(gòu)：用戶所能觀察和訪問到的文件的數(shù)據(jù)結(jié)構(gòu)組織，獨立于物理特性，容易檢索和修改。它可以分為 2類：（ 1）有結(jié)構(gòu)文件（ 2）無結(jié)構(gòu)文件 文件的物理結(jié)構(gòu)：又稱文件的存儲結(jié)構(gòu)，是指文件在外存上的組織形式。這不僅與存儲介質(zhì)的存儲性能有關(guān)，且與所采用的外存分配方式有關(guān)。 四、文件邏輯結(jié)構(gòu)的類型 1、有結(jié)構(gòu)文件：記錄式文件 a 類： （ 1）定長記錄 （ 2）變長記錄 b 類： （ 1）順序文件：通常是定長記錄，（為何，因變長采用此方式查詢速度慢） （ 2）索引文件： （ 3）索引順序文件：順序組織多個組，每組記錄中的第一個記錄設(shè)置一索引項。 2、無結(jié)構(gòu)文件：流式文件 以字節(jié)為單位，利用讀 /寫指針進(jìn)行訪問。 五、順序文件 1、邏輯記錄的排序 （ 1）按記錄錄入的時間排 :串結(jié)構(gòu)。 （ 2）按關(guān)鍵字排序：順序結(jié)構(gòu)。 后一種情況更有利于提高查詢速度。如可用折半查找法等。 2、對順序文件的讀 /寫操作 定長記錄順序文件：例：順序讀 易于定位，甚至可隨機(jī)讀取。 變長記錄：不易定位，只能順序讀取 。 六、索引文件 由變長記錄組成的順序文件不容易直接存取，因此，為其建立一有序的索引表，對索引采用折半查找，速度更快。 特點：提高了速度，增加了存儲開銷 放索引文件。 增、刪記錄時，對索引表作相應(yīng)的修改。 七、索引順序文件 將順序文件中若干記錄分為一組，每組的第一項在索引表中占一項。 速度： 例 1： 10000 個記錄，順序文件： 5000 次查找查到。 索引順序文件，設(shè) 100 個記錄一組，索引表的找法設(shè)為順序法的情況下，則平價查找次數(shù)為 50+50=100。 例 2： 1000000 個紀(jì)錄： 一級索引：（ 100 個紀(jì)錄 一組）：平價查找 5050 次 二級索引：平價查找 50+50+50=150 次 八、連續(xù)分配方式 連續(xù)分配（磁帶，磁盤都可采用）（順序文件） 每個文件分配一組相鄰盤塊。 優(yōu)點： 因磁頭移動距離小，順序訪問容易且速度快 . 缺點： 要求連續(xù)空間，一段時間后需整理磁盤以消除外部碎片。 必須事先知道長度，文件不易動態(tài)增長和刪除。 文件對應(yīng)目錄項（屬性）中包含： 始址、總塊數(shù)、最后一塊字節(jié)數(shù)。 九、連接方式分為隱式鏈接和顯示連接兩種形式。 隱式鏈接： 文件目錄表中有 號，每塊中有指向下一塊號的指針。 缺點：只適合 于順序訪問，對隨機(jī)訪問效率低，可靠性差。 十、索引分配 1、單級索引分配 鏈接分配問題： 不能高效直接存取； 占較大的內(nèi)存。 概念：為每個文件分配一個索引塊 特點：支持直接訪問；不會產(chǎn)生外部碎片 問題： （ 1）文件較大時有利。文件較小時浪費外存空間（還需為小文件建索引塊） （ 2）當(dāng)文件較大時，索引塊太多，查找速度減慢 解決：當(dāng)索引太大時，則需建立多級索引 2、多級索引分配 兩級 :為索引塊再建立一級索引 設(shè)一個盤塊大小為 1k，每個盤塊號占 4一個索引塊可存放 256 個盤塊號。 所以兩級 索引存放的文件的盤塊號總數(shù)為： 256 256=64k,故文件的最大長度為 64M 三、四級 :適用于文件更大時 設(shè)每個塊大小為 4k，一索引項（盤塊號）占 4 字節(jié)，則 1)直接地址 )：小文件（ =40k)則立即讀出。 2)一次間址 0)：一次間址塊中存放 1K 個盤塊， 4M 大小 3)多次尋址 : 二次間址 1)： 1K*1K 個盤塊， 4G 三次間址 2): 1K*1K*1K 個盤塊， 4T 例子： 十一、文件控制塊：為了能對系統(tǒng)中的大量文件施以有效的 管理，在文件控制塊中通常有三類信息 基本信息，存取控制信息，使用信息。 十二、索引結(jié)點：含文件描述信息。 為何引入： 含 :文件名、描述信息，它們較占空間 十三、多級目錄結(jié)構(gòu)： 樹型目錄結(jié)構(gòu)（多級目錄） 特點： 能有效地提高對目錄的檢索速度 允許文件重名 便于實現(xiàn)文件共享 （ 1）目錄結(jié)構(gòu)： 目錄文件中的目錄項可為：目錄文件（節(jié)點）、數(shù)據(jù)文件（樹葉） （ 2）路徑名： （ 3）當(dāng)前目錄 /工作目錄。 十四、空閑表法和空閑鏈表法 1、空閑表法： 分配：首次 /循環(huán)首次 /最佳 /最壞 回收：判斷是否合并 。 由于連續(xù)分配比較快，因此對對換空間及小文件的管理適用。 1)空閑盤塊鏈 缺點：可能該鏈很長。 2)空閑盤區(qū)鏈： 一個盤區(qū)含多個盤塊，類似于內(nèi)存分區(qū)分配與回收 (合并 )。 十五、位示圖 1、盤塊的分配： （ 1）順序掃描，找一個或一組 =0 的塊。（ 2）根據(jù)找到的行 /列得以盤塊號。 b=n(j （ 3）修改位圖，令 i,j=1。 2、回收 （ 1）由磁塊號得 (i,j) i=(n +1 j=(n +1 （ 2）修改位圖：令 i,j=0。 特點：因不占空間，可放入內(nèi)存，易于訪問 以下 的大題，大家看看并做做不懂得再問問： 第四章 (以下題目是老師講到過的 ) 例 1：某系統(tǒng)采用頁式存儲管理策略，擁有邏輯空間 32 頁，每頁 2K，擁有物理空間 1M 寫出邏輯地址的格式 若不考慮訪問