操作系統(tǒng)_2013new

1、操作系統(tǒng)操作系統(tǒng)Operating Systems費翔林費翔林 操作系統(tǒng)教程操作系統(tǒng)教程(4)高教社，高教社，2008葛季棟多多道道程程序序設(shè)設(shè)計計程序的動程序的動態(tài)概念態(tài)概念內(nèi)存管理內(nèi)存管理提高性能和利用率提高性能和利用率提高提高CPU與與I/O，I/O之間的并行度之間的并行度固定固定/動態(tài)分區(qū)、動態(tài)分區(qū)、分頁分頁/分段分段處理器管理處理器管理/進程抽象進程抽象I/O設(shè)備管理設(shè)備管理設(shè)備抽象設(shè)備抽象, I/O軟件的分層軟件的分層虛存抽象虛存抽象處理器調(diào)度處理器調(diào)度虛擬分頁虛擬分頁虛擬段頁式虛擬段頁式文件抽象文件抽象單單/多線程結(jié)構(gòu)進程多線程結(jié)構(gòu)進程中斷技術(shù)中斷技術(shù)虛擬分段虛擬分段并發(fā)進程并發(fā)

2、進程, 同步與互斥同步與互斥(PV, 管程管程, 進程通信進程通信)磁盤管理磁盤管理/調(diào)度調(diào)度死鎖問題死鎖問題, 必要條件必要條件, 預(yù)預(yù)防防, 避免避免, 檢測和解除檢測和解除文件邏輯結(jié)構(gòu)文件邏輯結(jié)構(gòu)文件物理結(jié)構(gòu)文件物理結(jié)構(gòu)文件目錄文件目錄, 共享與保護共享與保護虛擬文件系統(tǒng)虛擬文件系統(tǒng)I/O控制方式控制方式, 緩沖技術(shù)緩沖技術(shù)設(shè)備分配設(shè)備分配, 虛擬設(shè)備虛擬設(shè)備Spooling文件管理文件管理文件系統(tǒng)文件系統(tǒng)文件抽象文件抽象Chap3Chap4Chap6Chap2Chap5Roadmap安全與保護安全與保護 Chap 7，網(wǎng)絡(luò)和分布式，網(wǎng)絡(luò)和分布式 Chap8主要內(nèi)容主要內(nèi)容l第一章、操作

3、系統(tǒng)概述第一章、操作系統(tǒng)概述l第二第二/三章、進程和處理機管理、進程同步、三章、進程和處理機管理、進程同步、互斥、通信與死鎖互斥、通信與死鎖l第四章、存儲管理第四章、存儲管理l第五章、設(shè)備管理和第五章、設(shè)備管理和I/O系統(tǒng)系統(tǒng)l第六章、文件管理第六章、文件管理第一章、操作系統(tǒng)概述第一章、操作系統(tǒng)概述l操作系統(tǒng)的定義操作系統(tǒng)的定義l操作系統(tǒng)的特征操作系統(tǒng)的特征l操作系統(tǒng)的功能操作系統(tǒng)的功能l操作系統(tǒng)的分類操作系統(tǒng)的分類第二第二/三章、進程和處理機管理，進程同步、三章、進程和處理機管理，進程同步、互斥、通信與死鎖互斥、通信與死鎖l進程進程定義定義特征特征組成組成l進程管理進程管理五狀態(tài)模型五狀態(tài)模

4、型l進程協(xié)作進程協(xié)作互斥、同步互斥、同步死鎖死鎖l處理機調(diào)度（作業(yè)管理）處理機調(diào)度（作業(yè)管理）調(diào)度算法調(diào)度算法第四章、存儲管理第四章、存儲管理l內(nèi)存管理內(nèi)存管理基本原理基本原理分區(qū)調(diào)度分區(qū)調(diào)度l虛存管理虛存管理頁面調(diào)度頁面調(diào)度l磁盤管理磁盤管理磁盤調(diào)度磁盤調(diào)度第五章、設(shè)備管理和第五章、設(shè)備管理和I/O系統(tǒng)系統(tǒng)lI/O設(shè)備數(shù)據(jù)傳送控制方式設(shè)備數(shù)據(jù)傳送控制方式l中斷技術(shù)中斷技術(shù)l虛擬設(shè)備虛擬設(shè)備lSpooling技術(shù)技術(shù)第六章、文件管理第六章、文件管理l文件文件概念概念實現(xiàn)實現(xiàn)l目錄目錄實現(xiàn)實現(xiàn)lFAT32文件系統(tǒng)文件系統(tǒng)物理設(shè)備微程序機器語言O(shè).S.命令解釋器編譯編輯銀行系統(tǒng)，飛機訂票硬件系統(tǒng)軟

5、件應(yīng)用程序圖圖1.2OSXENIXdos. UNIX.應(yīng)用程序裸機(硬件)第一章、操作系統(tǒng)概述第一章、操作系統(tǒng)概述l操作系統(tǒng)的定義操作系統(tǒng)的定義操作系統(tǒng)是計算機系統(tǒng)的一個系統(tǒng)軟件，它是這樣的一些程操作系統(tǒng)是計算機系統(tǒng)的一個系統(tǒng)軟件，它是這樣的一些程序模塊的集合：它們能有效的組織和管理計算機系統(tǒng)中的硬序模塊的集合：它們能有效的組織和管理計算機系統(tǒng)中的硬件及軟件資源，合理的組織計算機工作流程，控制程序的執(zhí)件及軟件資源，合理的組織計算機工作流程，控制程序的執(zhí)行，并向用戶提供各種服務(wù)功能，使得用戶能夠靈活、方便、行，并向用戶提供各種服務(wù)功能，使得用戶能夠靈活、方便、有效的使用計算機，使整個計算機系統(tǒng)能

6、高效地運行。有效的使用計算機，使整個計算機系統(tǒng)能高效地運行。l兩方面作用兩方面作用管理系統(tǒng)中的各種資源，包括硬件及軟件資源管理系統(tǒng)中的各種資源，包括硬件及軟件資源為用戶提供良好的為用戶提供良好的接口接口l普通用戶界面普通用戶界面l編程接口編程接口API操作系統(tǒng)的特征操作系統(tǒng)的特征l并發(fā)性并發(fā)性 - 指若干事件在指若干事件在同一時間間隔同一時間間隔內(nèi)發(fā)生內(nèi)發(fā)生 l共享性共享性 l隨機性隨機性 操作系統(tǒng)的功能操作系統(tǒng)的功能l進程管理進程管理對處理機進行管理對處理機進行管理l作業(yè)管理作業(yè)管理OS向用戶提供使用它自己的手段向用戶提供使用它自己的手段l存儲管理存儲管理管理存儲資源管理存儲資源操作系統(tǒng)的功

7、能操作系統(tǒng)的功能l文件管理文件管理有效的支持文件的存儲、檢索和修改等操作，解決有效的支持文件的存儲、檢索和修改等操作，解決文件的共享、保密和保護問題，以便用戶方便安全文件的共享、保密和保護問題，以便用戶方便安全地訪問文件。地訪問文件。l設(shè)備管理設(shè)備管理對計算機系統(tǒng)中的所有輸入對計算機系統(tǒng)中的所有輸入/輸出設(shè)備的管理。輸出設(shè)備的管理。l其他功能其他功能系統(tǒng)安全、網(wǎng)絡(luò)通信等系統(tǒng)安全、網(wǎng)絡(luò)通信等操作系統(tǒng)的分類操作系統(tǒng)的分類l批處理操作系統(tǒng)批處理操作系統(tǒng)l分時操作系統(tǒng)分時操作系統(tǒng)l實時操作系統(tǒng)實時操作系統(tǒng)l嵌入式操作系統(tǒng)嵌入式操作系統(tǒng)l網(wǎng)絡(luò)操作系統(tǒng)網(wǎng)絡(luò)操作系統(tǒng)l分布式操作系統(tǒng)分布式操作系統(tǒng)l個人計算機

8、操作系統(tǒng)個人計算機操作系統(tǒng)l智能卡操作系統(tǒng)智能卡操作系統(tǒng)第二、三章第二、三章 進程進程進程定義和描述進程定義和描述l進程是一個具有一定獨立功能的程序在一個數(shù)進程是一個具有一定獨立功能的程序在一個數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程。據(jù)集合上的一次動態(tài)執(zhí)行過程。l作為描述程序執(zhí)行過程的概念，進程具有動態(tài)作為描述程序執(zhí)行過程的概念，進程具有動態(tài)性、獨立性、并發(fā)性和結(jié)構(gòu)化等特征。性、獨立性、并發(fā)性和結(jié)構(gòu)化等特征。進程與程序的區(qū)別和聯(lián)系進程與程序的區(qū)別和聯(lián)系l進程是動態(tài)的，程序是靜態(tài)的。進程是動態(tài)的，程序是靜態(tài)的。l進程是暫時的，程序是永久的。進程是暫時的，程序是永久的。l進程和程序的組成不同。進程包括程序、

9、數(shù)據(jù)進程和程序的組成不同。進程包括程序、數(shù)據(jù)和進程控制塊。和進程控制塊。l進程和程序是密切相關(guān)的。通過多次執(zhí)行，一進程和程序是密切相關(guān)的。通過多次執(zhí)行，一個程序可對應(yīng)多個進程；通過調(diào)用關(guān)系，一個個程序可對應(yīng)多個進程；通過調(diào)用關(guān)系，一個進程可以包括多個程序。進程可以創(chuàng)建其他進進程可以包括多個程序。進程可以創(chuàng)建其他進程，而程序不能形成新的程序。程，而程序不能形成新的程序。進程控制塊進程控制塊l進程由進程由 代碼、數(shù)據(jù)和進程控制塊代碼、數(shù)據(jù)和進程控制塊PCB組成組成lPCB 是由操作系統(tǒng)維護的用來記錄進程相關(guān)是由操作系統(tǒng)維護的用來記錄進程相關(guān)信息的數(shù)據(jù)結(jié)構(gòu)。信息的數(shù)據(jù)結(jié)構(gòu)。l進程控制塊的內(nèi)容分為進程

10、描述信息、進程控進程控制塊的內(nèi)容分為進程描述信息、進程控制信息、資源占用信息和處理機現(xiàn)場保護結(jié)構(gòu)制信息、資源占用信息和處理機現(xiàn)場保護結(jié)構(gòu)4個部分。個部分。五狀態(tài)進程模型五狀態(tài)進程模型創(chuàng)建阻塞退出就緒運行創(chuàng)建新進程提交超時釋放事件出現(xiàn) 等待事件調(diào)度作業(yè)調(diào)度算法作業(yè)調(diào)度算法l先來先服務(wù)算法（先來先服務(wù)算法（First Come First Service）基本思想是按照進程到達的先后順序進行調(diào)度基本思想是按照進程到達的先后順序進行調(diào)度l最短作業(yè)優(yōu)先算法（最短作業(yè)優(yōu)先算法（Shortest Job First）要求作業(yè)在開始執(zhí)行時預(yù)計執(zhí)行時間，給預(yù)計執(zhí)行要求作業(yè)在開始執(zhí)行時預(yù)計執(zhí)行時間，給預(yù)計執(zhí)行時

11、間短的作業(yè)優(yōu)先分派處理機。后來的短作業(yè)不搶時間短的作業(yè)優(yōu)先分派處理機。后來的短作業(yè)不搶現(xiàn)正在執(zhí)行的作業(yè)。現(xiàn)正在執(zhí)行的作業(yè)。l優(yōu)先級算法（優(yōu)先級算法（Priority Scheduling）是多級隊列的改進，協(xié)調(diào)各進程隊列中進程的響應(yīng)是多級隊列的改進，協(xié)調(diào)各進程隊列中進程的響應(yīng)時間要求。分為搶占式和非搶占式。時間要求。分為搶占式和非搶占式。作業(yè)調(diào)度作業(yè)調(diào)度l計算各種調(diào)度算法下作業(yè)隊列的計算各種調(diào)度算法下作業(yè)隊列的平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間調(diào)度的類型調(diào)度的類型l長程調(diào)度長程調(diào)度: 決定加入到等待執(zhí)行的進程池中決定加入到等待執(zhí)行的進程池中l(wèi)中程調(diào)度中程調(diào)度：決定加入到部分或全部在主存中的進：決定加入到

12、部分或全部在主存中的進程集合中。程集合中。l短程調(diào)度短程調(diào)度：決定哪一個可用進程將保持處理器執(zhí)：決定哪一個可用進程將保持處理器執(zhí)行。行。lI/O調(diào)度調(diào)度：決定哪一個進程掛起的：決定哪一個進程掛起的I/O請求將被可請求將被可用的用的I/O設(shè)備處理。設(shè)備處理。 調(diào)度的決策模式調(diào)度的決策模式l非搶占非搶占：在這種情況下，一旦進程處于運行態(tài)，它就在這種情況下，一旦進程處于運行態(tài)，它就不斷執(zhí)行直到終止，或者為等待不斷執(zhí)行直到終止，或者為等待I/O或請求某或請求某些操作系統(tǒng)服務(wù)而阻塞自己。些操作系統(tǒng)服務(wù)而阻塞自己。 調(diào)度的決策模式調(diào)度的決策模式l搶占搶占：當前正在運行的進程可能被操作系統(tǒng)中斷，并轉(zhuǎn)移到就緒

13、當前正在運行的進程可能被操作系統(tǒng)中斷，并轉(zhuǎn)移到就緒態(tài)。關(guān)于搶占的決策可能是在一個態(tài)。關(guān)于搶占的決策可能是在一個新進程到達新進程到達時，或者在時，或者在一個一個中斷中斷發(fā)生后把一個被阻塞的進程置為就緒態(tài)時，或者發(fā)生后把一個被阻塞的進程置為就緒態(tài)時，或者基于基于周期性的時間周期性的時間中斷。中斷。 與非搶占策略相比，搶占策略可能會與非搶占策略相比，搶占策略可能會導(dǎo)致較大的開銷導(dǎo)致較大的開銷，但，但是可能對所有進程會提供較好的服務(wù)，因為它們避免了任是可能對所有進程會提供較好的服務(wù)，因為它們避免了任何一個進程獨占處理器太長時間。此外，通過使用有效的何一個進程獨占處理器太長時間。此外，通過使用有效的進程

14、切換機制進程切換機制(盡可能地獲得硬件的幫助盡可能地獲得硬件的幫助)，以及提供比較，以及提供比較大的主存，使得大部分程序都在主存中，可使搶占的代價大的主存，使得大部分程序都在主存中，可使搶占的代價相對比較低。相對比較低。 習題習題 - 作業(yè)調(diào)度作業(yè)調(diào)度先來先服務(wù)算法先來先服務(wù)算法 (FCFS)l最簡單的調(diào)度策略是最簡單的調(diào)度策略是先來先服務(wù)先來先服務(wù)，也稱為先進先出或者嚴格，也稱為先進先出或者嚴格排隊方案。排隊方案。l當每個進程就緒后，它加入就緒隊列。當當前正在運行的進當每個進程就緒后，它加入就緒隊列。當當前正在運行的進程停止執(zhí)行時，選擇在就緒隊列中存在時間最長的進程運行。程停止執(zhí)行時，選擇在

15、就緒隊列中存在時間最長的進程運行。 非搶占非搶占FCFS最短作業(yè)優(yōu)先算法最短作業(yè)優(yōu)先算法l最短進程優(yōu)先是一個非搶占的策略，其原則是下一次選擇最短進程優(yōu)先是一個非搶占的策略，其原則是下一次選擇所需處理時間最短的進程。所需處理時間最短的進程。l短進程將會越過長作業(yè)，跳到隊列頭。短進程將會越過長作業(yè)，跳到隊列頭。 非搶占非搶占最短作業(yè)優(yōu)先算法最短作業(yè)優(yōu)先算法進程的協(xié)作進程的協(xié)作l進程的調(diào)度進程的調(diào)度并發(fā)并發(fā)l協(xié)作關(guān)系協(xié)作關(guān)系同步同步l競爭關(guān)系競爭關(guān)系互斥互斥互斥算法互斥算法l臨界資源是指計算機系統(tǒng)中需要互斥使用的硬件臨界資源是指計算機系統(tǒng)中需要互斥使用的硬件或軟件資源，如外設(shè)、共享代碼段、共享數(shù)據(jù)結(jié)

16、或軟件資源，如外設(shè)、共享代碼段、共享數(shù)據(jù)結(jié)構(gòu)等。構(gòu)等。(在一段時間內(nèi)，只允許一個進程訪問的資源在一段時間內(nèi)，只允許一個進程訪問的資源)l臨界區(qū)是指進程中訪問臨界資源的一段代碼。臨界區(qū)是指進程中訪問臨界資源的一段代碼。信號量信號量l信號量：由操作系統(tǒng)提供的管理公有資源的有效手段。信號信號量：由操作系統(tǒng)提供的管理公有資源的有效手段。信號量代表可用資源實體的數(shù)量，量代表可用資源實體的數(shù)量，0表示還有可用的資源，新來的進程可以直接執(zhí)行，表示還有可用的資源，新來的進程可以直接執(zhí)行，0表示已經(jīng)沒有可用的資源，有進程因此而阻塞，表示已經(jīng)沒有可用的資源，有進程因此而阻塞，0表示已經(jīng)沒有可用的資源，也沒有進程在

17、等待該資源。表示已經(jīng)沒有可用的資源，也沒有進程在等待該資源。P原語原語lP(s)：把信號量：把信號量s 減去減去1，如果計算后的信號量，如果計算后的信號量s小于小于0 ，則阻塞該進程則阻塞該進程V原語原語l V(s)：把信號量：把信號量s 加加1，如果計算后的信號量，如果計算后的信號量s小于或小于或等于等于0，則從阻塞隊列中激活一個等待的進程，則從阻塞隊列中激活一個等待的進程生產(chǎn)者生產(chǎn)者-消費者問題消費者問題l解決若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)解決若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)時的緩沖區(qū)資源使用問題。時的緩沖區(qū)資源使用問題。lOne Producer, One Consumer,

18、N BufferslOne Producer，N Consumer, N BufferslN Producer, One Consumer, N BufferslN Producer, N Consumer, N Buffers一個生產(chǎn)者一個生產(chǎn)者, 一個消費者一個消費者, 緩沖區(qū)容量為緩沖區(qū)容量為Nreadcount:=0semaphore Rmutex，Wmutex； Rmutex=1;Wmutex=1;Cobeginprocess reader_i( ) P(Rmutex); if(readcount=0) P(Wmutex); readcount+; V(Rmutex);讀文件; P(

19、Rmutex); readcount-; if(readcount=0) V(Wmutex); V(Rmutex);process writer_j( ) P(Wmutex); 寫文件; V(Wmutex); coend信號量解決讀者寫者問題-讀者優(yōu)先哲學家吃通心粉問題哲學家吃通心粉問題l有五個哲學家圍坐在一圓桌旁，桌子中央有一有五個哲學家圍坐在一圓桌旁，桌子中央有一盤通心面，每人面前有一只空盤子，每兩人之盤通心面，每人面前有一只空盤子，每兩人之間放一把叉子。每個哲學家思考、饑餓、然后，間放一把叉子。每個哲學家思考、饑餓、然后，欲吃通心面。為了吃面，每個哲學家必須獲得欲吃通心面。為了吃面，每個

20、哲學家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。去取叉子。錯誤的解法錯誤的解法出現(xiàn)死鎖出現(xiàn)死鎖 semaphore fork5; for (int i=0;i物理內(nèi)存映物理內(nèi)存映射射)頁框號頁框號不連續(xù)，不連續(xù)，非連續(xù)的非連續(xù)的內(nèi)存空間內(nèi)存空間分頁式存儲管理分頁式存儲管理: 邏輯地址邏輯地址 物理地址物理地址lLogical addresslPhysical addressPage NumoffsetFrame Numoffset例子例子: 分頁式管理的邏輯地址分頁式管理的邏輯地址-物理地址轉(zhuǎn)換計算物理地址轉(zhuǎn)換計算l頁面與幀的大小為頁面與

21、幀的大小為10241024字節(jié)字節(jié), , 指令指令 MOV 2100, 3100 MOV 2100, 3100 l求求MOVMOV指令中兩個操作數(shù)的物理地址指令中兩個操作數(shù)的物理地址l2100 2100 102410242 2 52523468頁表地址控制寄存器 2 52 6 52主存6196offsetPage numoffsetframe numl頁面與幀的大小為頁面與幀的大小為10241024字節(jié)字節(jié), , 指令指令 MOV 2100, 3100 MOV 2100, 3100 l求求MOVMOV指令中兩個操作數(shù)的物理地址指令中兩個操作數(shù)的物理地址l3100 3100 ? =? =1024

22、10243 3 28283468頁表地址控制寄存器主存8220offsetPage numoffsetframe num282838例子例子: 分頁式管理的邏輯地址分頁式管理的邏輯地址-物理地址轉(zhuǎn)換計算物理地址轉(zhuǎn)換計算？段式存儲管理基本原理段式存儲管理基本原理l將程序的地址空間劃分為若干段將程序的地址空間劃分為若干段（segment），這樣每個進程都有一個二維），這樣每個進程都有一個二維的地址空間。系統(tǒng)為每個段分配一個連續(xù)的分的地址空間。系統(tǒng)為每個段分配一個連續(xù)的分區(qū)，而進程中的各個段可以不連續(xù)的存放在內(nèi)區(qū)，而進程中的各個段可以不連續(xù)的存放在內(nèi)存的不同分區(qū)中。程序加載時，存的不同分區(qū)中。程序加

23、載時，OS為所有段為所有段分配其所需內(nèi)存，這些段不必連續(xù)。段式存儲分配其所需內(nèi)存，這些段不必連續(xù)。段式存儲管理也需要硬件支持，實現(xiàn)邏輯地址到物理地管理也需要硬件支持，實現(xiàn)邏輯地址到物理地址的映射。址的映射。程序的用戶視圖程序的用戶視圖分段管理的邏輯視圖分段管理的邏輯視圖13241423用戶空間的邏輯視圖用戶空間的邏輯視圖物理的內(nèi)存空間物理的內(nèi)存空間分段式存儲管理的基本原理分段式存儲管理的基本原理(2) 段控制寄存器 段表始址 段表長度 段號s 位移d 段長 基址 物理地址越界? 段表分段式存儲管理的實現(xiàn)分段式存儲管理的實現(xiàn)l分頁是機械地將程序劃分成大小相等的頁，另外也可以將分頁是機械地將程序劃

24、分成大小相等的頁，另外也可以將將程序劃分成大小不等的段。將程序劃分成大小不等的段。l采用分段技術(shù)，程序和相關(guān)的數(shù)據(jù)被劃分成一組段采用分段技術(shù)，程序和相關(guān)的數(shù)據(jù)被劃分成一組段(segment) ，不要求所有程序的所有段的長度相等，有點，不要求所有程序的所有段的長度相等，有點類似于動態(tài)分區(qū)類似于動態(tài)分區(qū)l邏輯地址邏輯地址由兩部分組成：段號和偏移量由兩部分組成：段號和偏移量 l與動態(tài)分區(qū)不同，通過與動態(tài)分區(qū)不同，通過段表段表實現(xiàn)不連續(xù)存儲的重定位實現(xiàn)不連續(xù)存儲的重定位l段表段表：段的長度、段的起始地址、其他控制位與標志位：段的長度、段的起始地址、其他控制位與標志位比較比較: 分頁分頁 與與 分段分段

25、l區(qū)別區(qū)別分頁對程序員是分頁對程序員是不可見的，有內(nèi)部碎片，無外部碎片不可見的，有內(nèi)部碎片，無外部碎片分段對程序員通常是分段對程序員通常是可見的，無內(nèi)部碎片，有外部碎片可見的，無內(nèi)部碎片，有外部碎片l分段的特點分段的特點為組織程序和數(shù)據(jù)的一種方便手段提供給程序員。一般情況下，程序為組織程序和數(shù)據(jù)的一種方便手段提供給程序員。一般情況下，程序員或編譯器把程序和數(shù)據(jù)指定到不同的段。為了實現(xiàn)模塊化程序設(shè)計員或編譯器把程序和數(shù)據(jù)指定到不同的段。為了實現(xiàn)模塊化程序設(shè)計地目的，程序或數(shù)據(jù)可能進一步分成多個段。地目的，程序或數(shù)據(jù)可能進一步分成多個段。 例子例子: 分段分段l采用分段法，l某個分段的邏輯地址的段

26、號為2, 段內(nèi)偏移量為100, 計算它的物理地址。段表長度 段表地址控制寄存器 2 100 8k 100主存8292offsetseg numoffset基址1k8005002006k4k8k92008K+100=8292段表長度段表地址頁式和段式系統(tǒng)的區(qū)別頁式和段式系統(tǒng)的區(qū)別 -4.1.8l頁是信息的物理單位，段是信息的邏輯單位。頁是信息的物理單位，段是信息的邏輯單位。l頁的大小固定且由系統(tǒng)決定，段的大小通常取頁的大小固定且由系統(tǒng)決定，段的大小通常取決于用戶所寫的程序。決于用戶所寫的程序。l頁式系統(tǒng)地址空間是一維的，分段的作業(yè)地址頁式系統(tǒng)地址空間是一維的，分段的作業(yè)地址空間是二維的?？臻g是二

27、維的。段頁式存儲管理基本原理段頁式存儲管理基本原理 -4.1.7l用頁式方法來分配和管理內(nèi)存空間，即把內(nèi)存劃分成用頁式方法來分配和管理內(nèi)存空間，即把內(nèi)存劃分成若干大小相等的頁面；若干大小相等的頁面；l用段式方法對用戶程序按照其內(nèi)在的邏輯關(guān)系劃分成用段式方法對用戶程序按照其內(nèi)在的邏輯關(guān)系劃分成若干段；若干段；l再按照劃分內(nèi)存頁面的大小，把每一段劃分成若干大再按照劃分內(nèi)存頁面的大小，把每一段劃分成若干大小相等的頁面；小相等的頁面；l用戶程序的邏輯地址由三部分組成，形式如下：用戶程序的邏輯地址由三部分組成，形式如下： 段號段號 頁號頁號 頁內(nèi)地址頁內(nèi)地址 ；l內(nèi)存是以頁為基本單位分配給每個用戶程序的

28、，在邏內(nèi)存是以頁為基本單位分配給每個用戶程序的，在邏輯上相鄰的頁面內(nèi)存不一定相鄰。輯上相鄰的頁面內(nèi)存不一定相鄰。 虛存管理：頁面置換算法（虛存管理：頁面置換算法（1）l先進先出算法（先進先出算法（FIFO）選擇置換裝入最早的頁面。選擇置換裝入最早的頁面。l最近最久未使用算法（最近最久未使用算法（Least Recently Used, LRU）選擇置換內(nèi)存中最久未使用的頁面。但是由于要記選擇置換內(nèi)存中最久未使用的頁面。但是由于要記錄頁面使用時間的先后關(guān)系，硬件開銷大。錄頁面使用時間的先后關(guān)系，硬件開銷大。l計算缺頁中斷次數(shù)和缺頁中斷率計算缺頁中斷次數(shù)和缺頁中斷率頁面置換算法頁面置換算法l最優(yōu)策

29、略最優(yōu)策略 (Optimal policy) 又稱為又稱為Belady算法算法選擇替換下次訪問距當前時間最長的那些頁，可以看出該選擇替換下次訪問距當前時間最長的那些頁，可以看出該算法能導(dǎo)致最少的頁錯誤，算法能導(dǎo)致最少的頁錯誤，但是由于它要求操作系統(tǒng)必須知道將來的事件，顯然這是但是由于它要求操作系統(tǒng)必須知道將來的事件，顯然這是不可能實現(xiàn)的。不可能實現(xiàn)的。作為一種標準來衡量其他算法的性能作為一種標準來衡量其他算法的性能 。 頁面置換算法頁面置換算法l最近最少使用最近最少使用 Least Recently Used (LRU)替換主存中上次使用距離當前最遠的頁替換主存中上次使用距離當前最遠的頁 根據(jù)

30、局部性原理，這也是最近最不可能訪問到的頁。實根據(jù)局部性原理，這也是最近最不可能訪問到的頁。實際上，際上，LRU策略的性能接近于策略的性能接近于OPT策略。策略。該方法的問題在于比較難于實現(xiàn)。該方法的問題在于比較難于實現(xiàn)。一種實現(xiàn)方法是給每一頁添加一個最后一次訪問的一種實現(xiàn)方法是給每一頁添加一個最后一次訪問的時間時間標簽標簽，并且必須在每次訪問存儲器時，不論訪問的是指，并且必須在每次訪問存儲器時，不論訪問的是指令還是數(shù)據(jù)，都更新這個標簽。即使有支持這種方案的令還是數(shù)據(jù)，都更新這個標簽。即使有支持這種方案的硬件，開銷仍然非常大。硬件，開銷仍然非常大。另一種可選擇的方法是維護一個關(guān)于訪問的棧，當開銷

31、另一種可選擇的方法是維護一個關(guān)于訪問的棧，當開銷同樣很大同樣很大。 頁面置換算法頁面置換算法l先進先出先進先出 First-in, first-out (FIFO)把分配給進程的頁幀看做是一個循環(huán)緩沖區(qū)，按循環(huán)方式把分配給進程的頁幀看做是一個循環(huán)緩沖區(qū)，按循環(huán)方式移動頁。它所需要的只是一個指針，這個指針在該進程的移動頁。它所需要的只是一個指針，這個指針在該進程的頁幀中循環(huán)。頁幀中循環(huán)。是是 一種實現(xiàn)起來最簡單的頁替換策略。一種實現(xiàn)起來最簡單的頁替換策略。隱含的邏輯隱含的邏輯是替換駐留在主存中時間最長的頁；一個在很是替換駐留在主存中時間最長的頁；一個在很久以前取入主存的頁，到現(xiàn)在可能已經(jīng)不會在用

32、到了。久以前取入主存的頁，到現(xiàn)在可能已經(jīng)不會在用到了。這個推理常常是錯誤的，因為經(jīng)常會出現(xiàn)一部分程序或數(shù)這個推理常常是錯誤的，因為經(jīng)常會出現(xiàn)一部分程序或數(shù)據(jù)據(jù)在整個程序的生命周期中使用頻率都很高在整個程序的生命周期中使用頻率都很高的情況，如果的情況，如果使用使用FIFO算法，則這些頁會反復(fù)地需要被換入換出。算法，則這些頁會反復(fù)地需要被換入換出。 預(yù)知未來預(yù)知未來回顧過去回顧過去理論上理論上FFFFFF磁盤管理：磁盤訪問時間磁盤管理：磁盤訪問時間 -4.3.3l尋道時間尋道時間 Ts把磁臂從當前位置移動到指定的磁道上所經(jīng)歷的時把磁臂從當前位置移動到指定的磁道上所經(jīng)歷的時間。間。l旋轉(zhuǎn)延遲時間旋轉(zhuǎn)

33、延遲時間Tr扇區(qū)移動到磁頭下面所經(jīng)歷的時間。扇區(qū)移動到磁頭下面所經(jīng)歷的時間。l傳輸時間傳輸時間Tt把數(shù)據(jù)從磁盤讀出，或者寫入數(shù)據(jù)所經(jīng)歷的時間。把數(shù)據(jù)從磁盤讀出，或者寫入數(shù)據(jù)所經(jīng)歷的時間。磁盤調(diào)度算法磁盤調(diào)度算法- 4.3.4（1）l先來先服務(wù)算法（先來先服務(wù)算法（FCFS）根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度。根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度。l最短尋道時間優(yōu)先算法（最短尋道時間優(yōu)先算法（SSTF）選擇訪問磁道與當前磁頭所在位置距離最近的進程。選擇訪問磁道與當前磁頭所在位置距離最近的進程。l掃描算法（掃描算法（SCAN）不僅考慮距離，同時考慮當前磁頭的移動方向（電梯不僅考慮距離，同時考

34、慮當前磁頭的移動方向（電梯調(diào)度）。調(diào)度）。l計算磁道移動距離計算磁道移動距離l磁道磁道 0 199l55, 58, 39, 18, 90, 160, 150, 38, 184 l當前位置當前位置 100FCFS先來先服務(wù)算法先來先服務(wù)算法(FCFS)最短尋道時間優(yōu)先算法最短尋道時間優(yōu)先算法(SSTF)掃描算法掃描算法(SCAN)文件系統(tǒng)文件系統(tǒng) 5l定義定義文件是具有一定名稱的一組相關(guān)數(shù)據(jù)的集合。文件是具有一定名稱的一組相關(guān)數(shù)據(jù)的集合?？臻g分配策略空間分配策略(1) -5.1.2 l連續(xù)空間分配連續(xù)空間分配每個文件都占據(jù)了一個完整且連續(xù)的磁盤區(qū)域。實現(xiàn)每個文件都占據(jù)了一個完整且連續(xù)的磁盤區(qū)域。

35、實現(xiàn)簡單，存取速度快。但是，文件長度不易動態(tài)增加。簡單，存取速度快。但是，文件長度不易動態(tài)增加。l鏈接空間分配鏈接空間分配每個文件都有一張相應(yīng)的磁盤塊的鏈接表。這些磁盤每個文件都有一張相應(yīng)的磁盤塊的鏈接表。這些磁盤塊可以分散在磁盤的任何地方，除了最后一個磁盤塊塊可以分散在磁盤的任何地方，除了最后一個磁盤塊外，每個磁盤塊都有一個指針指向下一個磁盤塊。沒外，每個磁盤塊都有一個指針指向下一個磁盤塊。沒有外部碎片，文件可以任意的增長而沒有其他限制。有外部碎片，文件可以任意的增長而沒有其他限制。但是，只有在順序訪問時，鏈接空間分配策略才是高但是，只有在順序訪問時，鏈接空間分配策略才是高效的。（要訪問效的

36、。（要訪問i：1-i；然后要訪問；然后要訪問i-1：1-i-1）。）。此外，必須給指針分配空間。此外，必須給指針分配空間?？臻g分配策略空間分配策略(2) -5.1.2l索引空間分配索引空間分配每一個文件有一個索引塊，這個索引塊就是一個表，每一個文件有一個索引塊，這個索引塊就是一個表，每個表項存放文件所占有的單個磁盤塊的地址。避每個表項存放文件所占有的單個磁盤塊的地址。避免了外部碎片問題和文件長度受限制的問題，而且免了外部碎片問題和文件長度受限制的問題，而且還支持對任何一個文件塊的直接訪問。但是，索引還支持對任何一個文件塊的直接訪問。但是，索引塊的分配增加了系統(tǒng)存儲空間的開銷。同時，存取塊的分配

37、增加了系統(tǒng)存儲空間的開銷。同時，存取文件需要兩次訪問外存（先讀取索引，再訪問具體文件需要兩次訪問外存（先讀取索引，再訪問具體磁盤），降低了文件的存取速度。磁盤），降低了文件的存取速度。l組合空間分配組合空間分配多種策略的組合。多種策略的組合。目錄的實現(xiàn)目錄的實現(xiàn)l線性表算法線性表算法順序遍歷順序遍歷l哈希表算法哈希表算法直接訪問直接訪問l其他其他B+樹樹FAT32文件系統(tǒng)原理（文件系統(tǒng)原理（1） 5.4.3l卷的組織結(jié)構(gòu)：卷的組織結(jié)構(gòu)：P273圖圖5-18l文件分配表文件分配表以以FAT文件系統(tǒng)格式化的卷以簇為單位進行分配，默認的簇文件系統(tǒng)格式化的卷以簇為單位進行分配，默認的簇的大小由卷的大小

38、決定。的大小由卷的大小決定。類型類型0 x0000表示未使用，表示未使用，0 xFFF7表示損壞，表示損壞，0 xFFF8-F表示表示最后一個最后一個文件分配表的利用：圖文件分配表的利用：圖5-20，p275l目錄項目錄項大小為大小為32字節(jié)，內(nèi)容包括文件名、擴展名、屬性字節(jié)、最后字節(jié)，內(nèi)容包括文件名、擴展名、屬性字節(jié)、最后一次修改時間和日期、第一個簇的編號、文件長度。一次修改時間和日期、第一個簇的編號、文件長度。I/O設(shè)備數(shù)據(jù)傳送控制方式設(shè)備數(shù)據(jù)傳送控制方式l程序直接控制程序直接控制l中斷中斷l(xiāng)DMA中斷技術(shù)中斷技術(shù) 6.2.1l基本概念基本概念中斷是指計算機在執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生任何不尋常

39、的或非中斷是指計算機在執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生任何不尋常的或非預(yù)期的急需處理的事件，使得預(yù)期的急需處理的事件，使得CPU暫時中斷當前正在執(zhí)行的暫時中斷當前正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完畢后又返回程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或調(diào)度新的進程執(zhí)行的過程。原來被中斷處繼續(xù)執(zhí)行或調(diào)度新的進程執(zhí)行的過程。引起中斷發(fā)生的事件稱為中斷源。引起中斷發(fā)生的事件稱為中斷源。中斷源向中斷源向CPU發(fā)出的請求中斷處理信號稱為中斷請求發(fā)出的請求中斷處理信號稱為中斷請求CPU收到中斷請求后轉(zhuǎn)到相應(yīng)的事件處理程序的過程稱為中收到中斷請求后轉(zhuǎn)到相應(yīng)的事件處理程序的過程稱為中斷響應(yīng)斷響應(yīng)軟中斷軟中斷/硬中斷硬中斷l(xiāng)硬中斷（強迫性中斷