操作系統(tǒng)復(fù)習(xí)筆記

1、第一章 操作系統(tǒng)引論OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口，OS處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過(guò)OS來(lái)使用計(jì)算機(jī)系統(tǒng)單道批處理系統(tǒng)：?jiǎn)蔚佬?順序性 自動(dòng)性多道批處理系統(tǒng)：多道性 無(wú)序性 調(diào)度性分時(shí)系統(tǒng) 滿足用戶請(qǐng)求 特征：多路性 獨(dú)立性 及時(shí)性 交互性實(shí)時(shí)系統(tǒng) 即時(shí)處理 完成截止時(shí)間 開始截止時(shí)間操作系統(tǒng)的特征并發(fā)性：與并行不同共享性：互斥共享 同時(shí)訪問(wèn)異步性：表現(xiàn)為“走走停停”虛擬性：指通過(guò)某種技術(shù)把一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對(duì)應(yīng)物 通過(guò)虛擬存儲(chǔ)器技術(shù)，將一臺(tái)機(jī)器的物理存儲(chǔ)器變?yōu)樘摂M存儲(chǔ)器，以便從邏輯上來(lái)擴(kuò)充存儲(chǔ)器的容量。 操作系統(tǒng)功能處理機(jī)管理：進(jìn)程管理（進(jìn)程控制 進(jìn)程同步 進(jìn)程

2、通信 進(jìn)程調(diào)度）存儲(chǔ)管理：內(nèi)存分配 內(nèi)存保護(hù) 內(nèi)存擴(kuò)充 地址映射設(shè)備管理：緩沖管理（單緩沖 雙緩沖 緩沖池） 設(shè)備分配（設(shè)備控制器 通道） 設(shè)備處理 虛擬設(shè)備文件管理操作系統(tǒng)和用戶接口用戶接口脫機(jī)用戶接口聯(lián)機(jī)用戶接口程序接口圖形接口第二章 進(jìn)程管理程序的順序執(zhí)行及其特征順序性：封閉性： 可再現(xiàn)性： 前趨圖(Precedence Graph)是一個(gè)有向無(wú)循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系偏序關(guān)系程序的并發(fā)執(zhí)行及其特征 間斷性失去封閉性 不可再現(xiàn)性 進(jìn)程的特征和定義 進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一

3、個(gè)獨(dú)立單位結(jié)構(gòu)特征動(dòng)態(tài)性 并發(fā)性 獨(dú)立性 異步性進(jìn)程的三種基本狀態(tài)就緒執(zhí)行阻塞掛起態(tài)：把暫時(shí)無(wú)法執(zhí)行的進(jìn)程從內(nèi)存調(diào)出到外出 提高內(nèi)存利用率進(jìn)程控制塊PCB進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的 進(jìn)程控制塊的組織方式鏈接方式索引方式原語(yǔ)：由若干條指令組成的，完成一定功能的一段程序。原子性進(jìn)程的創(chuàng)建(Creation of Progress) (1)申請(qǐng)空白PCB。 (2) 為新進(jìn)程分配資源。 (3) 初始化進(jìn)程控制塊。 (4) 將新進(jìn)程插入就緒隊(duì)列，如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程， 便將新進(jìn)程插入就

4、緒隊(duì)列進(jìn)程的終止正常結(jié)束異常結(jié)束外界干涉進(jìn)程的終止過(guò)程 (1) 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)。 (2) 若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。 (3) 若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止，以防他們成為不可控的進(jìn)程。 (4) 將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程， 或者歸還給系統(tǒng)。 (5) 將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出， 等待其他程序來(lái)搜集信息。 進(jìn)程阻塞過(guò)程阻塞原語(yǔ)block進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為先立即停止執(zhí)行

5、，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列進(jìn)程喚醒過(guò)程調(diào)用喚醒原語(yǔ)wakeup( )，將等待該事件的進(jìn)程喚醒。喚醒原語(yǔ)執(zhí)行的過(guò)程是：首先把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該P(yáng)CB插入到就緒隊(duì)列中進(jìn)程的掛起系統(tǒng)將利用掛起原語(yǔ)suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起進(jìn)程的激活過(guò)程系統(tǒng)將利用激活原語(yǔ)active( )將指定進(jìn)程激活。 激活原語(yǔ)先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動(dòng)就緒；若為靜止阻塞便將之改為活動(dòng)阻塞進(jìn)程同步兩種形式的制約關(guān)系間接相互制約關(guān)系：競(jìng)爭(zhēng)臨界資源

6、 比如打印機(jī)直接相互制約關(guān)系：協(xié)同工作臨界資源：一次只允許一個(gè)進(jìn)程訪問(wèn)進(jìn)入?yún)^(qū) 臨界區(qū) 退出區(qū) 剩余區(qū)同步機(jī)制應(yīng)遵循的規(guī)則：空閑讓進(jìn)忙則等待有限等待讓權(quán)等待信號(hào)量機(jī)制解決進(jìn)程問(wèn)題整型信號(hào)量：違反了“讓權(quán)等待”規(guī)則記錄型信號(hào)量：wait（s），signal（s）語(yǔ)句AND型信號(hào)量：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配Swait(S1, S2, , Sn) if Si1 and and Sn1

7、 then for i = 1 to n do Si = Si-1; endfor else place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endif Ssignal(S 1, S 2, , S n) for i = 1 to n do Si=Si+1; Remove all the process waiting in

8、 the queue associated with Si into the ready queue. endfor;信號(hào)量機(jī)制Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i=1 to n do Si=Si-di; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operati

9、on. endif signal(S1, d1, , Sn, dn) for i =1 to n do Si = Si+di; Remove all the process waiting in the queue associated with Si into the ready queue Endfor 一般“信號(hào)量集”的幾種特殊情況： (1) Swait(S, d, d)。 此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S， 但允許它每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配。 (2) Swait(S, 1, 1)。 此時(shí)的信號(hào)量集已蛻化為一般的記錄型信號(hào)量(S1時(shí))或互斥信號(hào)量(S=1時(shí))。 (

10、3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開關(guān)。 Var mutex:semaphore = 1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder seetion until false; end process 2: begin repeat wait(mutex); critical section signal(mutex

11、); remainder section until false; end parend利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系管程機(jī)制 局部于管程的共享變量說(shuō)明； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程 對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句。此外，還須為管程賦予一個(gè)名字。進(jìn)程通信（1）共享存儲(chǔ)器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。 基于共享存儲(chǔ)區(qū)的通信方式（2）消息傳遞系統(tǒng)直接通信方式Send(Receiver, message); 發(fā)送一個(gè)消息給接收進(jìn)程；Receive(Sender, message); 接收Sender發(fā)來(lái)的消息間接通信方式 Send(mailbox, message); 將一個(gè)消息發(fā)送到指定信箱；

12、Receive(mailbox, message); 從指定信箱中接收一個(gè)消息郵箱分為私有郵箱，公共郵箱，共享郵箱。（3）管道(Pipe)通信所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)， 以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它操作系統(tǒng)中 借助外存實(shí)現(xiàn)線程輕型實(shí)體 獨(dú)立調(diào)度和分派的基本單位 可并

13、發(fā)執(zhí)行共享進(jìn)程資源第三章 處理機(jī)調(diào)度和死鎖調(diào)度類型高級(jí)調(diào)度：將作業(yè)從外存后備隊(duì)列中調(diào)入內(nèi)存中級(jí)調(diào)度：對(duì)應(yīng)于掛起狀態(tài)，提高內(nèi)存的利用率和系統(tǒng)的吞吐量低級(jí)調(diào)度：進(jìn)程調(diào)度調(diào)度方式搶占式（高優(yōu)先權(quán)，短道作業(yè)（進(jìn)程）優(yōu)先，時(shí)間片）非搶占式面向用戶的準(zhǔn)則(1) 周轉(zhuǎn)時(shí)間短(2) 響應(yīng)時(shí)間快。 (3) 截止時(shí)間的保證。 (4) 優(yōu)先權(quán)準(zhǔn)則。 面向系統(tǒng)的準(zhǔn)則(1)系統(tǒng)吞吐量高(2) 處理機(jī)利用率好 (3) 各類資源的平衡利用 周轉(zhuǎn)時(shí)間：完成時(shí)間 到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間 / 服務(wù)時(shí)間 =（等待時(shí)間+服務(wù)時(shí)間）/服務(wù)時(shí)間調(diào)度算法先來(lái)先服務(wù)FCFS：按作業(yè)到達(dá)順序，順序執(zhí)行短道作業(yè)（進(jìn)程）優(yōu)先SJF/SPF

14、 對(duì)長(zhǎng)作業(yè)不利高優(yōu)先權(quán)HPF：搶占式 非搶占式時(shí)間片輪轉(zhuǎn) 系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來(lái)停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間高響應(yīng)比優(yōu)先既考慮了短作業(yè)，又考慮了長(zhǎng)作業(yè)如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)

15、 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)多級(jí)反饋隊(duì)列調(diào)度算法 (1) 應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí) (2) 當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片

16、輪轉(zhuǎn)的方式運(yùn)行。 (3) 僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行； 僅當(dāng)?shù)?(i-1) 隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。注意是時(shí)間片用完的情況還是外界干預(yù)情況，區(qū)別對(duì)待。優(yōu)先權(quán)類型：靜態(tài) 動(dòng)態(tài)死鎖：多個(gè)進(jìn)程因競(jìng)爭(zhēng)臨界資源而陷入僵局的狀態(tài)產(chǎn)生死鎖的原因競(jìng)爭(zhēng)資源進(jìn)程間推進(jìn)順序非法產(chǎn)生死鎖的必要條件互斥條件請(qǐng)求和保持條件不可剝奪條件環(huán)路等待條件處理

17、死鎖的方法預(yù)防死鎖1. 摒棄“請(qǐng)求和保持”條件 采用資源一次性分配方式 2. 摒棄“不剝奪”條件 如果無(wú)法獲取其他資源，立即釋放現(xiàn)在已申請(qǐng)到的資源3. 摒棄“環(huán)路等待”條件 避免死鎖：安全性算法 找進(jìn)程執(zhí)行的安全序列檢測(cè)死鎖：資源分配圖解除死鎖：剝奪資源 撤銷進(jìn)程系統(tǒng)的安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1, P2, ，Pn)(稱P1, P2, , Pn序列為安全序列)，來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)死鎖檢測(cè)：資源分配圖（找到一個(gè)既不阻塞又不獨(dú)立的進(jìn)程結(jié)點(diǎn)開始簡(jiǎn)化）利

18、用銀行家算法避免死鎖(1) 可利用資源向量Available 這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目 Availablej=K(2) 最大需求矩陣Max這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K(3) 已分配矩陣Allocation這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)(4) 需求矩陣Need一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果N

19、eedi,j=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)Needi,j=Maxi,j- Allocationi,j 執(zhí)行過(guò)程系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向

20、量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 第四章 存儲(chǔ)器管理程序的裝入絕對(duì)裝入方式：物理內(nèi)存的地址可重定位裝入方式：動(dòng)態(tài)裝入方式：把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此， 裝入內(nèi)存后的所有地址都仍是相對(duì)地址。程序的鏈接方式靜態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接：運(yùn)行時(shí)由OS去找該模塊并裝入內(nèi)存，這樣未用到的都不會(huì)被調(diào)入內(nèi)存內(nèi)存分配方式連續(xù)分配方式（1）單一連續(xù)

21、分配把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間， 提供給用戶使用（2）固定分區(qū)分配 劃分分區(qū)（分區(qū)大小相等或不等） 內(nèi)存碎片（3）動(dòng)態(tài)分區(qū)分配 涉及的數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表 空閑分區(qū)鏈 分區(qū)分配算法首次適應(yīng)算法：循環(huán)適應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法分配內(nèi)存操作可重定位分區(qū)分配，使用緊湊技術(shù)動(dòng)態(tài)重定位分區(qū)分配內(nèi)存回收對(duì)換技術(shù)（swapping）所謂“對(duì)換”， 是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對(duì)換是提高內(nèi)

22、存利用率的有效措施。對(duì)應(yīng)于掛起狀態(tài) 提高內(nèi)存的利用率將具有對(duì)換功能的OS，外存分為文件區(qū)和對(duì)換區(qū)文件區(qū)：存放文件 目的是實(shí)現(xiàn)對(duì)文件存儲(chǔ)空間的利用率對(duì)換區(qū)：存放從內(nèi)存中對(duì)換出來(lái)的進(jìn)程 提高進(jìn)程換入換出的速度基本分頁(yè)存儲(chǔ)管理方式頁(yè)面：對(duì)應(yīng)于邏輯地址空間，將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁(yè)面或頁(yè)物理塊：對(duì)應(yīng)于物理內(nèi)存空間，把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為(物理)塊或頁(yè)框(frame)由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁(yè)內(nèi)碎片”頁(yè)面大?。旱刂忿D(zhuǎn)換：（邏輯地址>物理地址）頁(yè)號(hào)+偏移量若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面的大小為L(zhǎng)

23、，則頁(yè)號(hào)P和頁(yè)內(nèi)地址d可按下式求得：物理地址=由頁(yè)號(hào)索引得到的塊號(hào)*頁(yè)面大小+偏移量的d頁(yè)表：頁(yè)號(hào)+塊號(hào)地址變換機(jī)構(gòu)越界中斷：是指計(jì)算的頁(yè)號(hào)值大于頁(yè)表的索引值，而發(fā)生中斷缺頁(yè)中斷：所申請(qǐng)?jiān)L問(wèn)的頁(yè)面不在內(nèi)存，產(chǎn)生中斷將其從外存調(diào)入具有快表的地址轉(zhuǎn)換機(jī)構(gòu)兩級(jí)和多級(jí)頁(yè)表基本分段存儲(chǔ)管理方式段號(hào)+段內(nèi)地址分頁(yè)和分段的主要區(qū)別(1) 頁(yè)是信息的物理單位，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭， 提高內(nèi)存的利用率?；蛘哒f(shuō)， 分頁(yè)僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對(duì)完整的信息。 分段的目的是為了能更好地滿足用戶的需要。(2) 頁(yè)的大小固定且由系統(tǒng)決定，由

24、系統(tǒng)把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁(yè)面；而段的長(zhǎng)度卻不固定， 決定于用戶所編寫的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來(lái)劃分。(3) 分頁(yè)的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址； 而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名， 又需給出段內(nèi)地址段頁(yè)式存儲(chǔ)管理方式虛擬存儲(chǔ)器虛擬存儲(chǔ)器， 是指具有請(qǐng)求調(diào)入功能和置換功能， 能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。特點(diǎn)：對(duì)換性 多次性 虛擬性程序運(yùn)行的局部性原理 內(nèi)存分配算法最小物理塊數(shù)：指能保證進(jìn)

25、程正常運(yùn)行所需的最小物理塊數(shù)。單地址指令 直接尋址 2個(gè)其他的將多于2個(gè)分配策略1) 固定分配局部置換2) 可變分配全局置換3) 可變分配局部置換物理塊分配算法1）平均分配算法2）按比例分配算法3）考慮優(yōu)先權(quán)的分配算法調(diào)頁(yè)策略預(yù)調(diào)策略請(qǐng)求調(diào)入策略外存分為兩部分，用于存放文件的文件區(qū)，和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)(1) 系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度(2) 系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對(duì)于那些可能被修改的部分，在將它們換

26、出時(shí)，便須調(diào)到對(duì)換區(qū)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入(3) UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面，由于是被放在對(duì)換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入每當(dāng)程序所要訪問(wèn)的頁(yè)面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁(yè)中斷。中斷處理程序首先保留CPU環(huán)境，分析中斷原因后， 轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過(guò)查找頁(yè)表，得到該頁(yè)在外存的物理塊后， 如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出頁(yè)面置換算法1）最佳置換算法Opt 向后看算法2）先進(jìn)先

27、出置換算法FIFO 3）最近最久未使用置換算法LRU 向前看算法此處涉及缺頁(yè)率計(jì)算Clock置換算法簡(jiǎn)單的Clock置換算法改進(jìn)的Clock置換算法在虛擬內(nèi)存中，頁(yè)面在內(nèi)存和外存之間頻繁的調(diào)度，以至于調(diào)度頁(yè)面所需要的時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)，系統(tǒng)效率劇烈下降，甚至導(dǎo)致系統(tǒng)崩潰，這種現(xiàn)象被稱為抖動(dòng)或顛簸。分段保護(hù)越界檢查存取控制檢查等第五章 設(shè)備管理I/O設(shè)備分類按傳輸速率分為 低速設(shè)備 中速設(shè)備 高速設(shè)備按信息交換的單位分為 塊設(shè)備（DMA） 字符設(shè)備按共享屬性分為 獨(dú)占設(shè)備 共享設(shè)備 虛擬設(shè)備設(shè)備控制器的基本功能：接收和識(shí)別命令 數(shù)據(jù)交換 標(biāo)識(shí)和報(bào)告設(shè)備狀態(tài) 地址識(shí)別 數(shù)據(jù)緩沖 差

28、錯(cuò)控制結(jié)構(gòu)：與處理機(jī)的接口 與設(shè)備的接口 I/O邏輯I/O通道設(shè)備目的 將CPU從繁忙的IO操作中解脫出來(lái)I/O通道是一種特殊的處理機(jī)。它具有執(zhí)行I/O指令的能力，并通過(guò)執(zhí)行通道(I/O)程序來(lái)控制I/O操作一是其指令類型單一，這是由于通道硬件比較簡(jiǎn)單， 其所能執(zhí)行的命令，主要局限于與I/O操作有關(guān)的指令； 二是通道沒(méi)有自己的內(nèi)存，通道所執(zhí)行的通道程序是放在主機(jī)的內(nèi)存中的， 換言之，是通道與CPU共享內(nèi)存通道類型 字符多路通道 不適合連接高速設(shè)備 數(shù)組選擇通道 可連接多臺(tái)高速設(shè)備，但只含一個(gè)分配型子通道，一段時(shí)間內(nèi)只能執(zhí)行一道通道程序，控制一臺(tái)設(shè)備。不允許搶占。數(shù)組多路通道它含有多個(gè)非分配型子

29、通道， 因而這種通道既具有很高的數(shù)據(jù)傳輸速率，又能獲得令人滿意的通道利用率瓶頸問(wèn)題單通路I/O系統(tǒng)解決瓶頸問(wèn)題 ，是多通路IO系統(tǒng)多通路I/O系統(tǒng)PCI 總線？I/O控制方式程序查詢方式在該方式中，CPU要不斷地測(cè)試I/O設(shè)備的狀態(tài)，致使CPU的絕大部分時(shí)間都處于等待I/O設(shè)備完成數(shù)據(jù)I/O的循環(huán)測(cè)試中， 造成對(duì)CPU的極大浪費(fèi)中斷驅(qū)動(dòng)方式 使CPU與I/O設(shè)備并行工作，僅當(dāng)輸完一個(gè)數(shù)據(jù)時(shí)，才需CPU花費(fèi)極短的時(shí)間去做些中斷處理DMA方式 特點(diǎn)是： 數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊，即在CPU與I/O設(shè)備之間，每次傳送至少一個(gè)數(shù)據(jù)塊； 所傳送的數(shù)據(jù)是從設(shè)備直接送入內(nèi)存的，或者相反； 僅在傳送一個(gè)或多

30、個(gè)數(shù)據(jù)塊的開始和結(jié)束時(shí)，才需CPU干預(yù)，整塊數(shù)據(jù)的傳送是在控制器的控制下完成的(1) 命令/狀態(tài)寄存器CR。用于接收從CPU發(fā)來(lái)的I/O命令或有關(guān)控制信息， 或設(shè)備的狀態(tài)(2) 內(nèi)存地址寄存器MAR。在輸入時(shí)，它存放把數(shù)據(jù)從設(shè)備傳送到內(nèi)存的起始目標(biāo)地址；在輸出時(shí)，它存放由內(nèi)存到設(shè)備的內(nèi)存源地址(3) 數(shù)據(jù)寄存器DR。用于暫存從設(shè)備到內(nèi)存，或從內(nèi)存到設(shè)備的數(shù)據(jù)(4) 數(shù)據(jù)計(jì)數(shù)器DC。 存放本次CPU要讀或?qū)懙淖?節(jié))數(shù)I/O通道控制方式 I/O通道方式是DMA方式的發(fā)展，它可進(jìn)一步減少CPU的干預(yù)，即把對(duì)一個(gè)數(shù)據(jù)塊的讀(或?qū)?為單位的干預(yù)，減少為對(duì)一組數(shù)據(jù)塊的讀(或?qū)?及有關(guān)的控制和管理為單位的

31、干預(yù)。 同時(shí)，又可實(shí)現(xiàn)CPU、通道和I/O設(shè)備三者的并行操作，從而更有效地提高整個(gè)系統(tǒng)的資源利用率緩沖管理(1) 緩和CPU與I/O設(shè)備間速度不匹配的矛盾。 (2) 減少對(duì)CPU的中斷頻率， 放寬對(duì)CPU中斷響應(yīng)時(shí)間的限制。 (3) 提高CPU和I/O設(shè)備之間的并行性緩沖首部：管理緩沖區(qū)緩沖體：存放緩沖數(shù)據(jù)（1）單緩沖single buffer處理時(shí)間=MAX(C,T)+M（2）雙緩沖Double buffer（3）循環(huán)緩沖 在此機(jī)制中，設(shè)置多個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)大小相同，包括：多個(gè)緩沖區(qū)用于輸入數(shù)據(jù)空緩沖區(qū)R：已裝滿數(shù)據(jù)的緩沖區(qū)G計(jì)算進(jìn)程正在使用的現(xiàn)行緩沖區(qū)C多個(gè)指針指示計(jì)算進(jìn)程下一個(gè)可用緩

32、沖區(qū)G的指針Nextg指示輸入進(jìn)程下次可用的空緩沖區(qū)R的指針Nexti指示進(jìn)程現(xiàn)在正在使用的緩沖區(qū)C的指針Current(1) Nexti指針追趕上Nextg指針。 已把全部可用的空緩沖區(qū)轉(zhuǎn)滿(2) (2) Nextg指針追趕上Nexti指針。 全部被轉(zhuǎn)滿的緩沖區(qū)已被抽空Getbuf過(guò)程Releasebuf過(guò)程（4）緩沖池buffer pool既可用于輸入又可用于輸出的公用緩沖池三個(gè)隊(duì)列指針（1）空緩沖隊(duì)列emq。 (2) 輸入隊(duì)列inq。 (3) 輸出隊(duì)列outq。 四個(gè)緩沖區(qū)收容輸入提取輸入收容輸出提取輸出設(shè)備驅(qū)動(dòng)程序：即設(shè)備處理程序，是I/O進(jìn)程與設(shè)備控制器之間的通信程序。設(shè)備獨(dú)立性：即

33、設(shè)備無(wú)關(guān)性，應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備引入概念：物理設(shè)備，邏輯設(shè)備優(yōu)點(diǎn)：設(shè)備分配靈活 易于實(shí)現(xiàn)I/O重定向 設(shè)備分配設(shè)備控制表DCT控制器控制表COCT通道控制表CHCT系統(tǒng)設(shè)備表SDT獨(dú)占設(shè)備的分配程序獨(dú)立設(shè)備分配過(guò)程：SDTDCTCOCTCHCT設(shè)備的固有屬性：獨(dú)占性 共享性 虛擬性設(shè)備分配算法：FCFS HPFSPOOLing技術(shù)：即假脫機(jī)技術(shù)，實(shí)現(xiàn)脫機(jī)輸入、 輸出功能輸入井：模擬脫機(jī)輸入的磁盤設(shè)備，暫存I/O設(shè)備輸入的數(shù)據(jù)輸出井：模擬脫機(jī)輸出的磁盤設(shè)備，暫存用戶程序的輸出數(shù)據(jù)在輸入輸出設(shè)備與磁盤之間設(shè)置輸入輸出緩沖區(qū)，進(jìn)行速度上的匹配輸入進(jìn)程 輸出進(jìn)程以打印機(jī)為例說(shuō)明該技術(shù) 當(dāng)用

34、戶進(jìn)程請(qǐng)求打印輸出時(shí)， SPOOLing系統(tǒng)同意為它打印輸出， 但并不真正立即把打印機(jī)分配給該用戶進(jìn)程， 而只為它做兩件事： 由輸出進(jìn)程在輸出井中為之申請(qǐng)一個(gè)空閑磁盤塊區(qū)， 并將要打印的數(shù)據(jù)送入其中； 輸出進(jìn)程再為用戶進(jìn)程申請(qǐng)一張空白的用戶請(qǐng)求打印表，并將用戶的打印要求填入其中， 再將該表掛到請(qǐng)求打印隊(duì)列上。特點(diǎn)：提高了I/O操作 將獨(dú)占設(shè)備改造為共享設(shè)備 實(shí)現(xiàn)了虛擬設(shè)備功能磁盤存儲(chǔ)管理固定頭磁盤在每條磁道上都有一讀/寫磁頭，所有的磁頭都被裝在一剛性磁臂中。通過(guò)這些磁頭可訪問(wèn)所有各磁道，并進(jìn)行并行讀/寫，有效地提高了磁盤的I/O速度。 這種結(jié)構(gòu)的磁盤主要用于大容量磁盤上固定頭磁盤每一個(gè)盤面僅配

35、有一個(gè)磁頭，也被裝入磁臂中。為能訪問(wèn)該盤面上的所有磁道，該磁頭必須能移動(dòng)以進(jìn)行尋道?？梢?jiàn)，移動(dòng)磁頭僅能以串行方式讀/寫，致使其I/O速度較慢；但由于其結(jié)構(gòu)簡(jiǎn)單， 故仍廣泛應(yīng)用于中小型磁盤設(shè)備中磁盤訪問(wèn)時(shí)間尋道時(shí)間：指把磁臂(磁頭)移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間Ts=m×n+s 旋轉(zhuǎn)延遲時(shí)間：指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間傳輸時(shí)間：把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間r 為轉(zhuǎn)速，b 所讀/寫字節(jié)數(shù)，N 一條磁道上的字節(jié)數(shù)可訪問(wèn)時(shí)間為磁盤調(diào)度算法先來(lái)先服務(wù)FCFS： 從當(dāng)前盤塊順序執(zhí)行完畢最短尋道優(yōu)先SSTF：同時(shí)雙向查找距當(dāng)前位置最近的盤塊，導(dǎo)致“饑餓”現(xiàn)象掃描SCAN： 先

36、沿盤塊號(hào)增大的方向執(zhí)行SSTF算法，然后在反向執(zhí)行SSTF算法循環(huán)掃描CSCAN： 先沿單向執(zhí)行SSTF算法，反向時(shí)無(wú)操作，然后繼續(xù)按第一次的執(zhí)行過(guò)程進(jìn)行操作 計(jì)算平均尋道長(zhǎng)度第六章 文件管理記錄：是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對(duì)象在某方面的屬性，一個(gè)記錄可包括多個(gè)數(shù)據(jù)項(xiàng)文件：指由創(chuàng)建者所定義的，具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件（記錄型文件）和無(wú)結(jié)構(gòu)文件（流式文件）兩種。在有結(jié)構(gòu)的文件中，文件由若干個(gè)相關(guān)記錄組成；而無(wú)結(jié)構(gòu)文件則被看成是一個(gè)字符流UNIX系統(tǒng)中，所有的文件都被看作是流式文件；即使是有結(jié)構(gòu)文件，也被視為流式文件；系統(tǒng)不對(duì)文件進(jìn)行格式處理。文件類型用途系統(tǒng)文件

37、 用戶文件 庫(kù)文件數(shù)據(jù)形式源文件 目標(biāo)文件 可執(zhí)行文件存取控制屬性只執(zhí)行文件 只讀文件 讀寫文件組織形式和處理方式普通文件 目錄文件 特殊文件（linux和unix中）特指系統(tǒng)中的各類I/O設(shè)備文件系統(tǒng)接口：命令接口 程序接口 對(duì)于任何一個(gè)文件，都存在著以下兩種形式的結(jié)構(gòu)文件邏輯結(jié)構(gòu)文件物理結(jié)構(gòu)：即存儲(chǔ)結(jié)構(gòu)，是指文件在外存上的存儲(chǔ)組織形式順序文件：分為串結(jié)構(gòu)的和順序結(jié)構(gòu)的缺點(diǎn)：不利于記錄的增刪鏈接分配方式隱式鏈接：指針隱藏在存放文件數(shù)據(jù)的盤塊中 訪問(wèn)方式：順序訪問(wèn) 文件的大小訪問(wèn)后才知道 文件目錄項(xiàng)中要給出起始盤塊號(hào)和終止盤塊號(hào)。顯式鏈接：指針顯式的存放在內(nèi)存的一張鏈接表中 文件目錄只給出起始盤號(hào)單級(jí)索引多級(jí)索引目錄管理：實(shí)現(xiàn)按名存取，提高檢索速度，文件共享文件和文件控制塊一一對(duì)應(yīng)單級(jí)目錄 簡(jiǎn)