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

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