操作系統(tǒng)復(fù)習(xí)重點模板

第1章 操作系統(tǒng)引論操作系統(tǒng)為一系統(tǒng)軟件，既管理硬件資源又管理軟件資源。操作系統(tǒng)的目標(biāo)：方便性，有效性，可擴充性，開放性。作用：1，是用戶與計算機之間的硬件接口最終用戶與硬件的接口：命令、圖形界面。程序員與硬件的接口：系統(tǒng)調(diào)用2，是計算機系統(tǒng)資源的管理者3，實現(xiàn)了對計算機資源的抽象，用作擴充機器。推動發(fā)展的主要動力:1，不斷提高計算機資源利用率2，方便用戶3，器件的不斷更新?lián)Q代4，計算機體系結(jié)構(gòu)的不斷發(fā)展。5，不斷提出新的應(yīng)用需求操作系統(tǒng)的發(fā)展過程：一：未配置操作系統(tǒng)的計算機系統(tǒng)1945年到50年代中期，還沒有出現(xiàn)操作系統(tǒng)1. 人工操作方式 （19461955） 特點：用戶獨占全機，cpu等待人工操作。降低了計算機資源利用效率2. 脫機輸入輸出方式 優(yōu)點：減少了CPU的空閑時間，提高I/O速度二：單道批處理系統(tǒng) 特點：自動性，順序性，單道性 優(yōu)點：1，減少人工操作的時間 缺點：.作業(yè)獨占cpu，cpu等待使cpu利用率低三 多道批處理系統(tǒng) 特點：多道性，無序性，調(diào)度性 優(yōu)點：cpu利用率高，提高內(nèi)存和io設(shè)備的利用率，增加量系統(tǒng)吞吐量 缺點：平衡周轉(zhuǎn)時間長 無交互能力一旦作業(yè)提交給系統(tǒng)，修改調(diào)試 極不方便四 分時系統(tǒng) 特征：多路性，獨立性，及時性，交互性五 實時系統(tǒng) 特征：快速反映，高可靠性，及時響應(yīng)。 實時任務(wù)類型： 周期性和非周期性 硬實時任務(wù)和軟實時任務(wù)實時系統(tǒng)與分時系統(tǒng)的比較 實時系統(tǒng)有以下幾種常見類型：工業(yè)（武器）控制系統(tǒng)，信息查詢系統(tǒng)，多媒體系統(tǒng)，嵌入式系統(tǒng)。1 多路性信息查詢系統(tǒng)和分時系統(tǒng)中的多路性都表現(xiàn)為系統(tǒng)按分時原則為多個終端用戶服務(wù)。實時控制系統(tǒng)的多路性則指系統(tǒng)周期性對多路現(xiàn)場信息進(jìn)行采集，以及對多個對象和多個執(zhí)行機構(gòu)進(jìn)行控制。2獨立性信息查詢系統(tǒng)中每個終端用戶在與系統(tǒng)交互時，彼此互相獨立互不干擾。同樣在實時控制系統(tǒng)中，對信息的采集和對對象的控制也都是彼此互不干擾的。3，及時性 4，交互性5，可靠性微機操作系統(tǒng)的發(fā)展：單用戶單任務(wù)操作系統(tǒng) ，單用戶多任務(wù)操作系統(tǒng)，多用戶多任務(wù)操作系統(tǒng)操作系統(tǒng)的基本特征：1.3.1 并發(fā)：并行性是指兩個或多個事件在同一時刻發(fā)生；而并發(fā)性是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生。1.3.2 共享：指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進(jìn)程(線程)共同使用。1.3.3 虛擬：是指通過某種技術(shù)把一個物理實體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。1.3.4 異步性：并發(fā)執(zhí)行的程序以不同的“速度”前進(jìn)。操作系統(tǒng)的主要功能 處理機管理功能 1進(jìn)程控制2進(jìn)程同步3進(jìn)程通信4調(diào)度 存儲器管理功能 1 內(nèi)存分配2內(nèi)存保護(hù)3地址映射4. 內(nèi)存擴充 設(shè)備管理功能 1 緩沖管理2設(shè)備分配3設(shè)備處理 文件管理功能 1. 文件存儲空間的管理 2. 目錄管理 3. 文件的讀/寫管理和保護(hù) 文件系統(tǒng)不僅方便了用戶，保證了文件的安全性，還有效地提高系統(tǒng)資源的利用率。 操作系統(tǒng)與用戶之間的接口傳統(tǒng)操作系統(tǒng)的功能： 用戶接口：方便用戶直接或間接的控制自己的作業(yè)，操作系統(tǒng)向用戶提供了命令接口。該接口進(jìn)一步分為聯(lián)機用戶接口，脫機用戶接口和圖形用戶接口 程序接口：為用戶程序在執(zhí)行中訪問系統(tǒng)資源而設(shè)置的，是用戶程序取得操作系統(tǒng)服務(wù)的唯一途徑?，F(xiàn)代操作系統(tǒng)的新功能;除了具有傳統(tǒng)操作系統(tǒng)的功能外，還添加了面向安全面向網(wǎng)絡(luò)和面向多媒體等功能。第2章 進(jìn)程的描述與控制第一節(jié)前趨圖 有向無循環(huán)圖 直接前驅(qū) 直接后繼 初始結(jié)點 終止結(jié)點重量 每個結(jié)點具有一個重量，表示該結(jié)點所含有的程序量或者程序的執(zhí)行時間。第二節(jié) 進(jìn)程程序的順序執(zhí)行 僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。程序順序執(zhí)行時的特征 (1)順序性;(2) 封閉性; (3) 可再現(xiàn)性; 相鄰語句并發(fā)執(zhí)行的條件 R(S1) W(S2)=， W(S1) R(S2)=， W(S1) W(S2)= 程序并發(fā)執(zhí)行時的特征 1.間斷性 2.失去封閉性 3.不可再現(xiàn)性 進(jìn)程的特征：1) 結(jié)構(gòu)特征：程序段、相關(guān)的數(shù)據(jù)段、PCB構(gòu)成了進(jìn)程實體。2) 動態(tài)性 ：進(jìn)程是進(jìn)程實體的一次執(zhí)行過程。3) 并發(fā)性：多個進(jìn)程實體，同存于內(nèi)存中，能在一段時間內(nèi)同時 運行。 4) 獨立性：獨立運行和資源調(diào)度的基本單位。5) 異步性 ：各自獨立的、以不可預(yù)知的速度向前推進(jìn)。進(jìn)程的定義： 進(jìn)程是進(jìn)程實體的運行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位”。進(jìn)程是一個具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。它可以申請和擁有系統(tǒng)資源，是一個動態(tài)的概念，是一個活動的實體。它不只是程序的代碼，還包括當(dāng)前的活動，通過程序計數(shù)器的值和處理寄存器的內(nèi)容來表示。終止 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程同步資源有正負(fù)，負(fù)的絕對值為等待資源的進(jìn)程個數(shù)什么叫臨界區(qū)？ 在并發(fā)進(jìn)程中，對共享變量操作的那段程序叫臨界區(qū)。同步機制應(yīng)遵循的規(guī)則 ：（1）空閑讓進(jìn)。（2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。PV操作：例題：生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝在一個箱子里，現(xiàn)要用自動分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個并發(fā)執(zhí)行的進(jìn)程組成，功能如下： 1）進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；（2）每個進(jìn)程每次只揀一個子，當(dāng)一個進(jìn)程在揀子時不允許另一個進(jìn)程去揀子； 分析：由功能（2）可知進(jìn)程之間是互斥的關(guān)系。process BbeginL2:P(s);揀白子；V(s);goto L2;end;設(shè)置一個公有信號量s，其值取決于公有資源的數(shù)目，由于箱子只有一個，s的初值就設(shè)為1。process A beginL1: P(s); 揀黑子；V(s);goto L1;end; （3） 當(dāng)一個進(jìn)程揀了一個棋子（黑子或白子）以后，必讓另一個進(jìn)程揀一個棋子（黑子或白子）。分析：第一步：確定進(jìn)程間的關(guān)系。由功能（1）（2）（3）可知，進(jìn)程間的關(guān)系為同步關(guān)系。第二步：確定信號量及其值。進(jìn)程A和B共享箱子這個公有資源，但規(guī)定兩個進(jìn)程必須輪流去取不同色的棋子，因而相互間要互通消息。對于進(jìn)程A可設(shè)置一個私有信號量s1，該私有信號量用于判斷進(jìn)程A是否能去揀黑子，初值為1。對于進(jìn)程B同樣設(shè)置一個私有信號量s2，該私有信號量用于判斷進(jìn)程B是否能去揀白子，初值為0。當(dāng)然你也可以設(shè)置s1初值為0，s2初值為1。 s1:=1; s2:=0;process BbeginL2:P(s2); 揀白子； V(s1);goto L2;end;process A begin L1: P(s1); 揀黑子； V(s2); goto L1; end; 例題：有一個倉庫，可以存放A和B 兩種產(chǎn)品。要求： (1)每次只能存入一種產(chǎn)品(A或B)； (2)一NA產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量M。試用PV操作描述產(chǎn)品A與產(chǎn)品B的入庫過程。在系統(tǒng)中安裝三種顏色的燈泡（如紅黃藍(lán)三種）和一個報警器，當(dāng)對mutex，sa，sb進(jìn)行p操作時，讓系統(tǒng)監(jiān)控三個信號燈的數(shù)值變化，一旦某個值小于零時，系統(tǒng)控制發(fā)出警報聲并且對應(yīng)的燈泡亮，這樣可以通過警報聲和發(fā)亮的燈泡的顏色來及時排除非法操作。互斥信號量 mutex=1；同步信號量 sa=M一1，sb=N一1int mutex=1; int sa=M-1; int sb=N-1;main( )while(true)取一個產(chǎn)品； if（取的是A產(chǎn)品） else P(sa)； P(sb)；P(mutex)； P(mutex)；將產(chǎn)品入庫； 將產(chǎn)品入庫；V(mutex)； V(mutex)；V(sb)； V(sa)；用PV操作實現(xiàn)進(jìn)程間同步與互斥應(yīng)注意些什么? 答：(1)對每一個共享資源(含變量)都要設(shè)立信號量，互斥時對一個共享資源設(shè)一個信號量，同步時對一個共享資源可能要設(shè)兩個或多個信號量，視由幾個進(jìn)程來使用該共享變量而定。(2)互斥時信號量的初值可大于或等于1,同步時，至少有一個信號量的初值大于等于1。(3)PV操作一定要成對調(diào)用，互斥時在臨界區(qū)前后對同一信號量作PV操作，同步時則對不同的信號量作PV操作，PV操作的位置一定要正確。(4)對互斥和同步混合問題PV操作可能會嵌套，一般同步的PV操作在外，互斥的PV操作在內(nèi)。 p是減1，V是加1.例題有兩個用戶進(jìn)程A和B，在運行過程中都要使用系統(tǒng)中的一臺打印機輸出計算結(jié)果。（1）試說明A、B兩進(jìn)程之間存在什么樣的制約關(guān)系？ 答：A、B兩進(jìn)程之間存在互斥的制約關(guān)系。因為打印機屬于臨界資源，必須一個進(jìn)程使用完之后另一個進(jìn)程才能使用。 （2） 為保證這兩個進(jìn)程能正確地打印出各自的結(jié)果，請用信號量和P、V操作寫出各自的有關(guān)申請、使用打印機的代碼。要求給出信號量的含義和初值。 答：mutex：用于互斥的信號量，因為只有一臺打印機，所以初值為1。進(jìn)程A 進(jìn)程B . . . . P(mutex)； P(mutex)； 申請打印機； 申請打印機； 使用打印機； 使用打印機； V(mutex)； V(mutex)； 例題：某車站售票廳，任何時刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時，廳外的購票者可立即進(jìn)入，否則需要在外面等待。每個購票者可看成一個進(jìn)程。分析：首先確定進(jìn)程間的關(guān)系，售票廳是各進(jìn)程共享的公有資源，當(dāng)售票廳中多于20名購票者時，廳外的購票者需要在外面等待，所以進(jìn)程間是互斥的關(guān)系；然后確定信號量及其值，只有一個公有資源：售票廳，所以設(shè)置一個信號量mutex售票廳最多容納20個進(jìn)程，即可用該資源實體數(shù)為20，mutex的初值就設(shè)為20程序如下：REPEATP(mutex)；進(jìn)入售票廳；購票；退出；V(mutex)；UNTIL false; 由此可知，互斥信號量的初值可大于等于1(當(dāng)售票廳內(nèi)至多容納1名購票者時，初值為1)，初值取什么，關(guān)鍵是可用資源數(shù)例2：在公共汽車上，司機和售票員各司其職。司機：正常行車、到站停車、啟動開車；售票員：售票、開車門、關(guān)車門。司機和售票員之間應(yīng)該密切配合，協(xié)調(diào)一致，以確保行車安全。請用PV操作實現(xiàn)司機和售票員之間的同步。司機和售票員在到站、開門、關(guān)門、啟動開車幾件事情上存在有同步關(guān)系：到站后才能開門，關(guān)門后才能開車用2個私有信號量stop、run分別表示可以開門和可以開車設(shè)初始狀態(tài)是汽車行車和售票員售票，所以初值應(yīng)該都為0，到站后才會有司機發(fā)消息讓開門程序如下：司機： 售票員： REPEAT REPEAT 正常行車； 售票； 到站停車； P(stop)； V(stop)； 開車門； P(run)； 關(guān)車門； 啟動開車； V(run)； UNTIL false； UNTIL false；如果司機和售票員的工作流程如下，司機：啟動開車、正常行車、到站停車；售票員：開車門、關(guān)車門、售票此時，設(shè)初始狀態(tài)為停車而還沒開門狀態(tài)，設(shè)stop=1、run=0，兩個程序為：司機： 售票員： REPEAT REPEAT P(run)； P(stop)； 啟動開車； 開車門； 正常行車； 關(guān)車門； 到站停車； V(run)； V(stop)； 售票； UNTIL false： UNTIL false 例題：假定閱覽室最多可同時容納100個人閱讀，讀者進(jìn)入時，必須在閱覽室門口的一個登記表上登記，內(nèi)容包括姓名、座號等，離開時要撤掉登記內(nèi)容。用P、V操作描述讀者進(jìn)程的同步算法。 算法的信號量有三個： seats表示閱覽室是否有座位（初值為100，代表閱覽室的空座位數(shù)）； readers表示閱覽室里的讀者數(shù)，初值為0； mutex 用于互斥的，初值為1。讀者進(jìn)入閱覽室的動作描述getin： while(TRUE) P (seats); /*沒有座位則離開*/P（mutex） /*進(jìn)入臨界區(qū)*/填寫登記表;進(jìn)入閱覽室讀書;V（mutex） /*離開臨界區(qū)*/V（readers） 讀者離開閱覽室的動作描述getout： while(TRUE)P（readers） /*閱覽室是否有人讀書*/P（mutex） /*進(jìn)入臨界區(qū)*/消掉登記；離開閱覽室； V（mutex） /*離開臨界區(qū)*/V（seats） /*釋放一個座位資源*/ 進(jìn)程的兩個基本屬性1、進(jìn)程是一個可擁有資源的獨立單位。2、進(jìn)程是一個可以獨立調(diào)度和分派的基本單位。系統(tǒng)為使程序并發(fā)執(zhí)行而進(jìn)行的一系列操作。1、創(chuàng)建進(jìn)程。2、撤銷進(jìn)程。3、進(jìn)程切換。線程的基本概念（為什么引入線程）1、由于進(jìn)程同時是資源擁有者，在進(jìn)程創(chuàng)建、撤銷、切換時需要較大的時空開銷，所以系統(tǒng)中所設(shè)置的進(jìn)程數(shù)和進(jìn)程切換的頻率都受到了限制，影響了OS并發(fā)程度的提高。2、引入線程，作為獨立調(diào)度和分派的單位，不獨立擁有資源（僅有少量基本資源），而與其它線程共享同一進(jìn)程的資源，減少了系統(tǒng)的時空開銷。3、實質(zhì)：把進(jìn)程的任務(wù)劃分為更小、不能繼續(xù)分的、具有獨立功能的單位，以線程的形式來并發(fā)執(zhí)行，以提高程序并發(fā)執(zhí)行的程度1、線程是進(jìn)程中的一個實體，是被系統(tǒng)獨立調(diào)度和分派的基本單位。2、線程只擁有在運行中必需的資源（程序計數(shù)器，一組寄存器和棧），但它可與同屬一個進(jìn)程的其它線程共享進(jìn)程所擁有的全部資源。3、一個線程可以創(chuàng)建和撤銷另一個線程。4、同一進(jìn)程中的多個線程可以并發(fā)執(zhí)行。5、線程在運行中呈現(xiàn)間斷性，也有就緒、阻塞和執(zhí)行三種基本狀態(tài)。第三章 處理機調(diào)度和死鎖按什么原則分配CPU 進(jìn)程調(diào)度算法CPU調(diào)度的目的：分配CPU。進(jìn)程調(diào)度的分類有：按調(diào)度層次，分為：高級調(diào)度（作業(yè)），中級調(diào)度（進(jìn)程），低級調(diào)度（內(nèi)存）（引入中級調(diào)度的目的：提高內(nèi)存利用率和系統(tǒng)吞吐量）按OS的類型，分為：批處理調(diào)度，分時調(diào)度，實時調(diào)度，多處理機調(diào)度。CPU利用率（處理機利用率）=cpu的有效工作時間/cpu有效工作時間+cpu空閑等待時間先來先服務(wù)調(diào)度算法（FCFS）（不可搶占）： 優(yōu)點:實現(xiàn)簡單 缺點:沒考慮進(jìn)程的優(yōu)先級。此算法是有利于長(大)作業(yè)(進(jìn)程)，不利于短(小)作業(yè)(進(jìn)程)；有利于CPU繁忙的作業(yè)(進(jìn)程)，不利于I/O繁忙的作業(yè)(進(jìn)程)。短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法（SJF/SPF）： 優(yōu)點：該算法相對FCFS來說調(diào)度性能要好些，且能滿足大多數(shù)作業(yè)(均是短作業(yè))用戶的要求。 缺點：該算法對長作業(yè)不利。該算法未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程 ）及時得到處理。該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。優(yōu)先權(quán)調(diào)度算法（PSA）：基本原理是：對于進(jìn)程調(diào)度，它總是把處理機分配給就緒隊列中具有最高優(yōu)先權(quán)的進(jìn)程；對于作業(yè)調(diào)度，它總選擇后備隊列中若干具有高優(yōu)先權(quán)的作業(yè)進(jìn)入內(nèi)存。優(yōu)先級調(diào)度算法又可分為： 非搶占的優(yōu)先級調(diào)度法 可搶占的優(yōu)先級調(diào)度法 1.靜態(tài)優(yōu)先權(quán) 確定靜態(tài)優(yōu)先權(quán)的依據(jù)有： (1)進(jìn)程類型 (2)進(jìn)程對資源的需求 (3)用戶要求的優(yōu)先權(quán)。 靜態(tài)優(yōu)先權(quán)簡單易行，系統(tǒng)開銷小，但不精確。 2.動態(tài)優(yōu)先權(quán)：動態(tài)優(yōu)先權(quán)是基于某種原則，使進(jìn)程的優(yōu)先權(quán)隨時間而改變。 高響應(yīng)比優(yōu)先調(diào)度算法(HRRN): 響應(yīng)比Rp定義如下： Rp=作業(yè)響應(yīng)時間tR /要求執(zhí)行的時間 作業(yè)響應(yīng)時間tR=作業(yè)進(jìn)入系統(tǒng)后等待時間+要求執(zhí)行的時間 Rp=1+(作業(yè)等待時間tW /要求執(zhí)行的時間) Rp=等待時間+要求服務(wù)時間/要求服務(wù)時間 響應(yīng)時間=等待時間+要求服務(wù)時間 周轉(zhuǎn)時間=結(jié)束時間-進(jìn)入時間 帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/運行時間時間片輪轉(zhuǎn)法： 基本原理 輪轉(zhuǎn)法是最簡單又最公平的進(jìn)程調(diào)度算法。主要用于分時系統(tǒng)中作為其主調(diào)度算法。輪流使用CPU。如果時間片到期時，進(jìn)程尚未完成運行，調(diào)度程序?qū)儕Z它正在使用的CPU，轉(zhuǎn)讓給另一進(jìn)程使用；如果進(jìn)程在使用完它的某一時間片之前已經(jīng)完成運行或已阻塞，CPU也立即轉(zhuǎn)讓給另一進(jìn)程使用。 時間片選擇有：固定時間片和可變時間片；與時間片大小有關(guān)的因素有：系統(tǒng)響應(yīng)時間、就緒進(jìn)程個數(shù)和CPU處理能力三個。 死鎖：死鎖引起的原因：競爭不可搶占性資源引起死鎖，競爭可消耗資源引起死鎖，進(jìn)程推進(jìn)順序不當(dāng)引起死鎖。定義：如果一組進(jìn)程中的每一個進(jìn)程都在等待僅有該組進(jìn)程中的其他進(jìn)程才能引發(fā)的事件，那么該組進(jìn)程是死鎖的。產(chǎn)生死鎖的必要條件：互斥條件，請求和保持條件，不可搶占條件，循環(huán)等待條件。處理死鎖的方法：(1) 預(yù)防死鎖。 （事先設(shè)置某些限制條件，破壞產(chǎn)生死鎖的必要條件，破壞請求和保持條件，不可搶占條件，循環(huán)等待條件。）(2) 避免死鎖。 （在資源動態(tài)分配過程中，利用算法避免死鎖）(3) 檢測死鎖。 (4) 解除死鎖。銀行家算法：Work Need Allocation work+Allocation FinishABC ABC ABC P1P2存在安全序列死鎖的檢測和解除 資源分配圖死鎖定理：S為死鎖的充分條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。死鎖的解除：1 搶占資源2 終止（撤銷）進(jìn)程 進(jìn)程優(yōu)先級大小，進(jìn)程已經(jīng)執(zhí)行了多長時間，還有。 進(jìn)程運行中使用了多少資源，以后。進(jìn)程的性質(zhì)是交互式的還是批處理的。第4章 ：程序的裝入：絕對裝入方式，可重定位裝入方式，動態(tài)運行時的裝入方式。程序的鏈接：靜態(tài)鏈接方式，（(1) 對相對地址進(jìn)行修改。 (2) 變換外部調(diào)用符號） 裝入時動態(tài)鏈接（(1)便于修改和更新。 (2) 便于實現(xiàn)對目標(biāo)模塊的共享。） 運行時動態(tài)鏈接(加快程序的裝入過程，可節(jié)省大量的內(nèi)存空間。)連續(xù)分配方式:單一連續(xù)分配 , 固定分區(qū)分配 固定分區(qū)式分配是將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)。它是一種最簡單的可運行多道程序的存儲管理方式。(優(yōu)點：易于實現(xiàn)，開銷小。缺點：內(nèi)碎片造成浪費；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。)動態(tài)分區(qū)分配算法：(1)首次適應(yīng)算法FF空閑區(qū)鏈：首址遞增排列；申請：按分區(qū)的先后次序，從頭查找，找到符合 要求的第一個分區(qū)；優(yōu)點：盡量使用低地址空間， 高地址空間保持大的空閑區(qū)域。缺點：隨著低地址分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)（內(nèi)存碎片），每次分配時查找時間開銷會增大。2) 循環(huán)首次適應(yīng)算法空閑區(qū)鏈：首址遞增排列；申請：從上次分配的分區(qū)起查找（到最后分區(qū)時再回到開頭），找到符合要求的第一個分區(qū)，應(yīng)設(shè)置一個查詢指針。特點：空閑分區(qū)分布均勻； 大的空閑分區(qū)不易保留； 查找時間開銷會減小。(3) 最佳適應(yīng)算法空閑區(qū)鏈：分區(qū)容量遞增排列；申請：找到符合要求的第一個分區(qū)。特點：碎片較小，但從整體來看，會形成較多的碎片(4) 最差適應(yīng)算法空閑區(qū)鏈：分區(qū)容量遞減排列；申請：找到符合要求的第一個分區(qū)。特點：大的空閑分區(qū)不易保留。邏輯地址(相對地址)：程序用來訪問信息所用的一系列地址單元物理地址(絕對地址)：主存中一系列儲存物理單元。地址空間：一個目標(biāo)程序所限定的地址范圍分頁地址中的地址結(jié)構(gòu)：位移量W頁號P31 12 11 0 0-11位為頁內(nèi)地址，每頁大小為4kb，12-31位為頁號，地址空間最多允許有1M頁。給定一個邏輯空間中的地址為A，頁面大小為L，則頁號和業(yè)內(nèi)地址按下示求P=INTA/L，d=AMOD L；為什么引入分段儲存管理方式：分段存儲管理方式更符合用戶和程序員的需要：方便編程，信息共享，信息保護(hù)，動態(tài)增長，動態(tài)鏈接。分頁和分段的主要區(qū)別：（1） 頁是信息的物理單位。分頁僅僅是系統(tǒng)管理上的需要，分段的目的在于更好的滿足用戶的需要。（2） 頁的大小固定且有系統(tǒng)決定，段的長度決定于用戶所編寫的程序（3） 分頁的用戶程序地址空間是一維的，分頁是系統(tǒng)行為而分段是用戶的行為。段頁式存儲管理方式1. 基本原理 將用戶程序劃分若干個段，然后再把每個段分成若干頁，并為每一段賦一個段名。 為了實現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)中需要同時配置段表和頁表. 為了便于實現(xiàn)地址轉(zhuǎn)換，須配置一個段表寄存器，存放段表始址和段長TL。 為了獲得一條指令或數(shù)據(jù)需要三次訪問內(nèi)存。虛擬存儲器基本概念：兩種情況： (1) 有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，導(dǎo)致該作業(yè)無法運行。 (2) 有大量作業(yè)要求運行，但是由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)的作業(yè)裝入內(nèi)存讓它們先運行，而將其它大量的作業(yè)留在外存上等待。虛擬存儲器特征：（1） 一次性：作業(yè)必須一次性的全部裝入內(nèi)存后方能開始運行。（2） 駐留性，作業(yè)被裝入內(nèi)存后，整個作業(yè)一直駐留在內(nèi)存中，其中任何部分都不會換出，直至作業(yè)運行結(jié)束。局部性原理：（1） 程序執(zhí)行時，除少部分的轉(zhuǎn)移和過程調(diào)用外，在大多數(shù)情況下是按順序執(zhí)行的，（2） 過程調(diào)用會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域。（3） 程序中存在許多循環(huán)結(jié)構(gòu)，被多次調(diào)用，（4） 程序中包括對數(shù)據(jù)結(jié)構(gòu)的處理局部性又同時表現(xiàn)在下述兩個方面：時間局部性（典型原因 程序中存在大量的循環(huán)操作）空間局部性（典型情況程序的順序執(zhí)行）虛擬存儲器定義：所謂虛擬存儲器， 是指具有請求調(diào)入功能和置換功能， 能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。虛擬存儲器的特征：多次性， 多次性是指一個作業(yè)被分多次調(diào)入內(nèi)存。多次性是虛擬存儲器最重要的特征對換性，對換性是指允許在作業(yè)的運行過程中換進(jìn)、換出。換進(jìn)和換出能夠有效提高內(nèi)存利用率。虛擬性，虛擬性是指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)遠(yuǎn)大于實際容量。虛擬性是以多次性和對換性為基礎(chǔ)的。內(nèi)存分配策略和分配算法 最小物理塊數(shù)的確定 最小物理塊數(shù)是指能保證進(jìn)程正常運行所需的最小物理塊數(shù)。 物理塊的分配策略 1) 固定分配局部置換 2) 可變分配全局置換3) 可變分配局部置換 物理塊分配算法 1) 平均分配算法 2)按比例分配算法 3) 考慮優(yōu)先權(quán)的分配算法 一個好的頁面置換算法應(yīng)該具有較低的頁面更換頻率。 最佳置換算法optimal 先進(jìn)先出置換算法（FIFO） 最近最久未使用(LRU)置換算法 第6章 輸入輸出系統(tǒng)I/O系統(tǒng)的基本功能：隱藏物理設(shè)備的細(xì)節(jié)，與設(shè)備無關(guān)性，提高處理機和I/O設(shè)備的利用率，對I/O設(shè)備進(jìn)行控制，確保對設(shè)備的正確共享，錯誤處理設(shè)備控制器的基本功能1）接收和識別命令 2) 數(shù)據(jù)交換 3) 標(biāo)識和報告設(shè)備的狀態(tài) 4) 地址識別 5) 數(shù)據(jù)緩沖 6) 差錯控制 對I/O設(shè)備的控制方式（傳送數(shù)據(jù)的四種方式）使用可輪詢的可編程I/O方式使用中斷可編程的I/O方式直接存儲器訪問方式I/O通道控制方式與設(shè)備無關(guān)的I/O軟件 目的：方便用戶和提高OS的可適應(yīng)性和可擴展性。 基本含義：應(yīng)用系統(tǒng)中所使用的設(shè)備，不局限于使用某個具體的物理設(shè)備，為每個設(shè)備所配置的設(shè)備驅(qū)動程序是與硬件緊密相關(guān)的軟件。為了實現(xiàn)設(shè)備獨立性，必須在設(shè)備驅(qū)動程序之上設(shè)置一層軟件，稱為與設(shè)備無關(guān)的I/O軟件呢，或者設(shè)備獨立軟件。假脫機系統(tǒng)（SPOOLing）SPOOLing系統(tǒng)特點：(1) 提高了I/O的速度(2) 將獨占設(shè)備改造為共享設(shè)備(3) 實現(xiàn)了虛擬設(shè)備功能磁盤訪問時間尋道時間Ts，旋轉(zhuǎn)延遲時間Tyi，傳輸時間Tt早期磁盤調(diào)度算法：先來先服務(wù)FCFS，最短尋道優(yōu)先（SSTF）基于掃描的磁盤調(diào)度算法：掃描算法（SCAN），循環(huán)掃描算法（CSCAN）第七章文件管理文件：由創(chuàng)建者所定義的，具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。文件屬性：文件類型，文件長度，文件的物理位置，文件的建立時間文件類型：按用途分類：系統(tǒng)文件，用戶文件，庫文件按文件中的數(shù)據(jù)形式分類：源文件，目標(biāo)文件，可執(zhí)行文件按存儲控制屬性分類：只執(zhí)行文件，只讀文件，讀寫文件按組織形式和處理方式分類：普通文件，目錄文件，特殊文件文件目錄管理要求：1，實現(xiàn)“按名存取”2，提高對目錄的檢索速度3，文件共享4，允許文件重名第8章 磁盤儲存器的管理磁盤儲存器管理的主要要求和任務(wù)是1） 有效的利用儲存空間2） 提高磁盤的I/O速度3） 提高磁盤系統(tǒng)的可靠性外存組織方式（文件物理結(jié)構(gòu)）1）連續(xù)組織方式 文件物理結(jié)構(gòu)是順序式的優(yōu)點：順序訪問容易，訪問速度快，缺點：要求為一個文件分配連續(xù)的儲存空間必須事先知道文件的長度不能靈活的刪除和插入記錄動態(tài)增長的文件很難為其分配空間，即使實現(xiàn)知道文件最終大小，也會使大量的儲存空間長期空閑2） 鏈接組織方式 鏈接式文件結(jié)構(gòu)優(yōu)點：消除了磁盤的外部碎片，提高了外存利用率插入，刪除修改記錄十分容易能適應(yīng)文件的動態(tài)增長，無需事先知道文件的大小。分類：隱式鏈接（順序訪問，隨機訪問速度低） 顯示鏈接（文件分配表）3）索引組織方式 索引式文件結(jié)構(gòu)FAT文件分配表，一個字節(jié)為8位，F(xiàn)AT12，每個Fat表項占12位計算文件最大長度（注意問的是系統(tǒng)還是。）直接地址：（提高文件檢索速度，在索引節(jié)點中設(shè)置10個節(jié)點）假設(shè)每個盤塊大小為4KB，文件不大于40KB，可直接從索引中讀出該文件的全部盤塊號一次間址：大中型文件 1K*4K=4GB兩次間址 文件長度大于4MB+40KB時 1K*1K*4K三次間址 1K*