操作系統(tǒng)期末復習文檔

1、n什么是操作系統(tǒng)？并分別從功能、軟件、什么是操作系統(tǒng)？并分別從功能、軟件、管理者及用戶觀點敘述之管理者及用戶觀點敘述之 q操作系統(tǒng)是控制和管理計算機軟、硬件資源，合理組織計算操作系統(tǒng)是控制和管理計算機軟、硬件資源，合理組織計算機工作流程，以及方便用戶使用的系統(tǒng)軟件。機工作流程，以及方便用戶使用的系統(tǒng)軟件。q從功能角度看，操作系統(tǒng)是計算機的資源管理系統(tǒng)，由它負從功能角度看，操作系統(tǒng)是計算機的資源管理系統(tǒng)，由它負責對計算機系統(tǒng)的全部軟、硬件資源進行分配、控制、調度責對計算機系統(tǒng)的全部軟、硬件資源進行分配、控制、調度和回收；和回收；q 從軟件的觀點看，操作系統(tǒng)是一個大型系統(tǒng)軟件，由多個功從軟件的觀點

2、看，操作系統(tǒng)是一個大型系統(tǒng)軟件，由多個功能模塊及數(shù)據(jù)集合組成；能模塊及數(shù)據(jù)集合組成；q從管理者角度看，操作系統(tǒng)是計算機工作流程的組織者。它從管理者角度看，操作系統(tǒng)是計算機工作流程的組織者。它自動、高效、合理的對系統(tǒng)進行管理；自動、高效、合理的對系統(tǒng)進行管理； q從用戶觀點看，操作系統(tǒng)是一個服務質量高、使用方便的虛從用戶觀點看，操作系統(tǒng)是一個服務質量高、使用方便的虛擬機。它是用戶使用計算機的界面和橋梁。擬機。它是用戶使用計算機的界面和橋梁。 第1章 操作系統(tǒng)引論n操作系統(tǒng)的地位操作系統(tǒng)的地位 q操作系統(tǒng)是計算機系統(tǒng)中硬、軟件資源的總指揮部。操作系統(tǒng)是計算機系統(tǒng)中硬、軟件資源的總指揮部。q操作系統(tǒng)

3、的性能高低決定了整體計算機的潛在硬件操作系統(tǒng)的性能高低決定了整體計算機的潛在硬件性能能否發(fā)揮出來。性能能否發(fā)揮出來。q操作系統(tǒng)本身的安全可靠程度決定了整個計算機系操作系統(tǒng)本身的安全可靠程度決定了整個計算機系統(tǒng)的安全性和可靠性統(tǒng)的安全性和可靠性q操作系統(tǒng)是軟件技術含量最大、附加值最高的部分，操作系統(tǒng)是軟件技術含量最大、附加值最高的部分，是軟件技術的核心，是軟件的基礎運行平臺。是軟件技術的核心，是軟件的基礎運行平臺。 n為什么說操作系統(tǒng)實現(xiàn)了對計算機資源的抽象？為什么說操作系統(tǒng)實現(xiàn)了對計算機資源的抽象？qOS首先在裸機上覆蓋一層首先在裸機上覆蓋一層I/O設備管理軟件，實現(xiàn)設備管理軟件，實現(xiàn)了對計算

4、機硬件操作的第一層次抽象；了對計算機硬件操作的第一層次抽象；q在第一層軟件上再覆蓋文件管理軟件，實現(xiàn)了對硬在第一層軟件上再覆蓋文件管理軟件，實現(xiàn)了對硬件資源操作的第二層次抽象。件資源操作的第二層次抽象。qOS 通過在計算機硬件上安裝多層系統(tǒng)軟件，增強通過在計算機硬件上安裝多層系統(tǒng)軟件，增強了系統(tǒng)功能，隱藏了對硬件操作的細節(jié)，由它們共了系統(tǒng)功能，隱藏了對硬件操作的細節(jié)，由它們共同實現(xiàn)了對計算機資源的抽象。同實現(xiàn)了對計算機資源的抽象。設計現(xiàn)代設計現(xiàn)代OS 的主要目標是什么的主要目標是什么?.q答：方便性。配置操作系統(tǒng)后可使計算機系統(tǒng)更容易使用。答：方便性。配置操作系統(tǒng)后可使計算機系統(tǒng)更容易使用。q

5、有效性。配置操作系統(tǒng)后可提高系統(tǒng)資源的利用率，提高有效性。配置操作系統(tǒng)后可提高系統(tǒng)資源的利用率，提高系統(tǒng)的吞吐量。系統(tǒng)的吞吐量。q可擴充性。操作系統(tǒng)應采用模塊化結構，以便于增加新的可擴充性。操作系統(tǒng)應采用模塊化結構，以便于增加新的功能和修改老的功能模塊。功能和修改老的功能模塊。q開放性。為使出自不同廠家的計算機及其設備能通過網(wǎng)絡開放性。為使出自不同廠家的計算機及其設備能通過網(wǎng)絡加以集成化并正確、有效地協(xié)同工作，實現(xiàn)應用程序的可加以集成化并正確、有效地協(xié)同工作，實現(xiàn)應用程序的可移植性和互操作性，要求操作系統(tǒng)必須提供統(tǒng)一的開放環(huán)移植性和互操作性，要求操作系統(tǒng)必須提供統(tǒng)一的開放環(huán)境，進而要求境，進而

6、要求OS具有開放性。開放性是指系統(tǒng)能遵循世界具有開放性。開放性是指系統(tǒng)能遵循世界標準規(guī)范，特別是遵循開放系統(tǒng)互連（標準規(guī)范，特別是遵循開放系統(tǒng)互連（OSI）國際標準。）國際標準。n試說明操作系統(tǒng)與硬件、其他系統(tǒng)軟件以及用試說明操作系統(tǒng)與硬件、其他系統(tǒng)軟件以及用戶之間的關系戶之間的關系 q操作系統(tǒng)是覆蓋在硬件上的第一層軟件，它管理計算機的硬件和軟件資源，并向用戶提供良好的界面。操作系統(tǒng)與硬件緊密相關，它直接管理著硬件資源，為用戶完成所有與硬件相關的操作，從而極大地方便了用戶對硬件資源的使用并提高了硬件資源的利用率。操作系統(tǒng)是一種特殊的系統(tǒng)軟件，其他系統(tǒng)軟件運行在操作系統(tǒng)的基礎之上，可獲得操作系統(tǒng)

7、提供的大量服務，也就是說操作系統(tǒng)是其他系統(tǒng)軟件與硬件之間的接口。而一般用戶使用計算機除了需要操作系統(tǒng)支持外，還需要用到大量的其他系統(tǒng)軟件和應用軟件，以使其工作更方便和高效。可見，硬件、操作系統(tǒng)、其他系統(tǒng)軟件、應用程序和用戶之間存在著右圖所示的層次關系。 操作系統(tǒng)具有哪幾大特征？它們之間有何關系？操作系統(tǒng)具有哪幾大特征？它們之間有何關系？答：操作系統(tǒng)的特征有并發(fā)、資源共享、虛擬和異步性。它們的關系答：操作系統(tǒng)的特征有并發(fā)、資源共享、虛擬和異步性。它們的關系如下：如下：(1)并發(fā)和共享是操作系統(tǒng)最基本的特征。為了提高計算機資源的利并發(fā)和共享是操作系統(tǒng)最基本的特征。為了提高計算機資源的利用率，操作系

8、統(tǒng)必然采用多道程序設計技術，使多個程序共享系用率，操作系統(tǒng)必然采用多道程序設計技術，使多個程序共享系統(tǒng)資源，并發(fā)地執(zhí)行。統(tǒng)資源，并發(fā)地執(zhí)行。(2)并發(fā)和共享互為存在的條件。一方面，資源的共享是以程序（進并發(fā)和共享互為存在的條件。一方面，資源的共享是以程序（進程）的并發(fā)執(zhí)行為條件，若系統(tǒng)不允許程序并發(fā)執(zhí)行，自然不存程）的并發(fā)執(zhí)行為條件，若系統(tǒng)不允許程序并發(fā)執(zhí)行，自然不存在資源共享問題；另一方面，若系統(tǒng)不能對資源共享實施有效的在資源共享問題；另一方面，若系統(tǒng)不能對資源共享實施有效的管理，協(xié)調好諸進程對共享資源的訪問，也必將影響到程序的并管理，協(xié)調好諸進程對共享資源的訪問，也必將影響到程序的并發(fā)執(zhí)行

9、，甚至根本無法并發(fā)執(zhí)行。發(fā)執(zhí)行，甚至根本無法并發(fā)執(zhí)行。(3)虛擬技術以并發(fā)和資源共享為前提。為了使并發(fā)進程能更方便、虛擬技術以并發(fā)和資源共享為前提。為了使并發(fā)進程能更方便、更有效地共享資源，操作系統(tǒng)常采用多種虛擬技術來邏輯上增加更有效地共享資源，操作系統(tǒng)常采用多種虛擬技術來邏輯上增加CPU和設備的數(shù)量以及存儲器的容量，從而解決眾多并發(fā)進程對和設備的數(shù)量以及存儲器的容量，從而解決眾多并發(fā)進程對有限的系統(tǒng)資源的爭用問題。有限的系統(tǒng)資源的爭用問題。(4)異步性是并發(fā)和共享的必然結果。操作系統(tǒng)允許多個并發(fā)進程共異步性是并發(fā)和共享的必然結果。操作系統(tǒng)允許多個并發(fā)進程共享資源、相互合作，使得每個進程的運行

10、過程受到其他進程的制享資源、相互合作，使得每個進程的運行過程受到其他進程的制約，不再約，不再“一氣呵成一氣呵成”，這必然導致異步特性的產生。，這必然導致異步特性的產生。第2章 進程進程引入的原因PCB特征進程同步進程控制概念狀態(tài)就緒執(zhí)行阻塞結構特征動態(tài)性并發(fā)性獨立性進程通信臨界資源和臨界區(qū)同步與互斥四個準則同步機制管程信號量程序線程狀態(tài)概念線程控制引入的原因線程同步屬性類別用戶級線程內核支持線程類別應用整型記錄型特例區(qū)別區(qū)別組成部分n1.程序順序執(zhí)行的特征程序順序執(zhí)行的特征n2.前趨圖前趨圖：描述程序段或進程之間執(zhí)行的先后順：描述程序段或進程之間執(zhí)行的先后順序序n3.程序并發(fā)執(zhí)行時的特征程序并

11、發(fā)執(zhí)行時的特征q 間斷性間斷性 失去封閉性失去封閉性 不可再現(xiàn)性不可再現(xiàn)性n4.進程的概念進程的概念q 進程是一個可并發(fā)執(zhí)行的具有獨立功能的程進程是一個可并發(fā)執(zhí)行的具有獨立功能的程序關于某個數(shù)據(jù)集合的一次執(zhí)行過程，也是操序關于某個數(shù)據(jù)集合的一次執(zhí)行過程，也是操作系統(tǒng)進行資源分配和保護的基本單位（作系統(tǒng)進行資源分配和保護的基本單位（1978年全國操作系統(tǒng)學術會議）年全國操作系統(tǒng)學術會議）n5.進程的特征進程的特征q結構特征：每個進程實體中除了相應的程序段、數(shù)結構特征：每個進程實體中除了相應的程序段、數(shù)據(jù)段外，還必須包含一個數(shù)據(jù)結構據(jù)段外，還必須包含一個數(shù)據(jù)結構PCB，即進程控，即進程控制塊制塊q

12、動態(tài)性動態(tài)性q并發(fā)性并發(fā)性q獨立性獨立性q異步性異步性n6.在操作系統(tǒng)中為什么要引入進程概念在操作系統(tǒng)中為什么要引入進程概念?為了為了實現(xiàn)并發(fā)進程間的合作和協(xié)調工作，以及保證實現(xiàn)并發(fā)進程間的合作和協(xié)調工作，以及保證系統(tǒng)的安全性，操作系統(tǒng)在進程管理方面應做系統(tǒng)的安全性，操作系統(tǒng)在進程管理方面應做哪些工作？哪些工作？ q在多道程序環(huán)境中，程序的執(zhí)行是并發(fā)的，這樣就在多道程序環(huán)境中，程序的執(zhí)行是并發(fā)的，這樣就要失去封閉性，并且間斷且不可再現(xiàn)要失去封閉性，并且間斷且不可再現(xiàn) 。并發(fā)執(zhí)行。并發(fā)執(zhí)行的三個特點決定通常的程序是不能并發(fā)執(zhí)行的，于的三個特點決定通常的程序是不能并發(fā)執(zhí)行的，于是引進了進程的概念。

13、是引進了進程的概念。q操作系統(tǒng)應該在進程管理方面做以下工作：操作系統(tǒng)應該在進程管理方面做以下工作：n進程控制。進程調度。進程同步。進程進程控制。進程調度。進程同步。進程通信。防止死鎖。通信。防止死鎖。n7.進程與程序的區(qū)別進程與程序的區(qū)別l進程更能真實地描述并發(fā)，而程序不能進程更能真實地描述并發(fā)，而程序不能l進程是由程序和數(shù)據(jù)兩部分組成的進程是由程序和數(shù)據(jù)兩部分組成的l程序是靜態(tài)的，進程是動態(tài)的程序是靜態(tài)的，進程是動態(tài)的l進程有生命周期，有誕生有消亡，短暫的；進程有生命周期，有誕生有消亡，短暫的； 而程序是相對長久的而程序是相對長久的l一個程序可對應多個進程，反之亦然一個程序可對應多個進程，反

14、之亦然l進程具有創(chuàng)建其他進程的功能，而程序沒有進程具有創(chuàng)建其他進程的功能，而程序沒有n8.什么是進程控制塊？試從進程管理、進程通信、中什么是進程控制塊？試從進程管理、進程通信、中斷處理、文件管理、存儲管理、設備管理的角度設計斷處理、文件管理、存儲管理、設備管理的角度設計進程控制塊應包含的項目。進程控制塊應包含的項目。q進程控制塊（進程控制塊（PCB）是為了控制進程在多道程序環(huán)境下能）是為了控制進程在多道程序環(huán)境下能夠獨立并發(fā)地運行而設計的數(shù)據(jù)結構，它包含了控制和描述夠獨立并發(fā)地運行而設計的數(shù)據(jù)結構，它包含了控制和描述該進程所需要的所有信息。該進程所需要的所有信息。q從進程管理的角度：從進程管理

15、的角度：PCB應該包含進程標識符、應該包含進程標識符、CPU狀態(tài)狀態(tài)信息、進程狀態(tài)、進程調度信息。信息、進程狀態(tài)、進程調度信息。q從進程通信的角度：從進程通信的角度：PCB應該包含指向消息隊列的指針，用應該包含指向消息隊列的指針，用于互斥訪問消息隊列的信號量。于互斥訪問消息隊列的信號量。q從中斷處理的角度：從中斷處理的角度：PCB應該包含中斷前的應該包含中斷前的CPU的狀態(tài)信息。的狀態(tài)信息。q從文件管理的角度：從文件管理的角度：PCB應該包含用戶文件描述符表。應該包含用戶文件描述符表。q從存儲管理的角度：從存儲管理的角度：PCB應該包含程序段、數(shù)據(jù)段和堆棧段應該包含程序段、數(shù)據(jù)段和堆棧段的地址

16、和長度。的地址和長度。q從設備管理的角度：從設備管理的角度：PCB應該包含該進程已分配到得設備和應該包含該進程已分配到得設備和運行還需要分配的設備的列表。運行還需要分配的設備的列表。n9. 為什么說為什么說PCB是進程存在的唯一標志？是進程存在的唯一標志？q在創(chuàng)建進程時，系統(tǒng)為他配置一個在創(chuàng)建進程時，系統(tǒng)為他配置一個PCB；在進；在進行進程調度時，系統(tǒng)根據(jù)行進程調度時，系統(tǒng)根據(jù)PCB中的狀態(tài)和優(yōu)先中的狀態(tài)和優(yōu)先級等信息來選擇新進程，然后將老進程的現(xiàn)場級等信息來選擇新進程，然后將老進程的現(xiàn)場信息保存到他的信息保存到他的PCB中，再根據(jù)新進程中，再根據(jù)新進程PCB中中所保存的處理機狀態(tài)信息來恢復現(xiàn)

17、場；執(zhí)行中所保存的處理機狀態(tài)信息來恢復現(xiàn)場；執(zhí)行中的進程，如果需要訪問文件或者需要與合作進的進程，如果需要訪問文件或者需要與合作進程實現(xiàn)同步或通信，也要訪問程實現(xiàn)同步或通信，也要訪問PCB；當進程因；當進程因某種原因而暫停執(zhí)行時，也必須將斷點的現(xiàn)場某種原因而暫停執(zhí)行時，也必須將斷點的現(xiàn)場信息保存到他的信息保存到他的PCB中；當進程結束時，系統(tǒng)中；當進程結束時，系統(tǒng)將回收他的將回收他的PCB?？梢姡龠M程的整個生命周。可見，再進程的整個生命周期中，系統(tǒng)總是通過其期中，系統(tǒng)總是通過其PCB對進程進行控制和對進程進行控制和管理。管理。n10.某分時系統(tǒng)的進程出現(xiàn)如下圖所示的狀態(tài)變化。某分時系統(tǒng)的進程

18、出現(xiàn)如下圖所示的狀態(tài)變化。等待打等待打印機輸印機輸出結果出結果運行運行等磁盤讀文件等磁盤讀文件就緒進程隊列就緒進程隊列試問：（試問：（1）你認為該系統(tǒng)采用的是何種進程調度算法？）你認為該系統(tǒng)采用的是何種進程調度算法？（2）把圖中所示的六個狀態(tài)變化的原因寫出來。）把圖中所示的六個狀態(tài)變化的原因寫出來。n【分析】從圖中可以看出在、和“就緒進程隊列”之間存在一個環(huán)路，有的進程在執(zhí)行過程中被剝奪處理機，排入就緒隊列的尾部，等待下一次調度，同時進程調度程序又去調度當前就緒隊列中的第一個進程，這樣的進程調度算法為時間片輪轉法。n解： n（1）該分時系統(tǒng)采用的進程調度算法是時間片輪轉法。n（2）進程被選中，

19、變成運行態(tài)；時間片到，運行的進程排入就緒隊列尾部；運行的進程啟動打印機，等待打印；打印工作結束，等待的進程排入就緒隊列尾部；等待磁盤讀文件工作；磁盤傳輸信息結束，等待的進程排入就緒隊列尾部。n11.進程控制進程控制q所謂進程控制，是指系統(tǒng)使用一些具有特定功能的所謂進程控制，是指系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤銷進程以及完成進程各狀態(tài)間轉程序段來創(chuàng)建、撤銷進程以及完成進程各狀態(tài)間轉換的一系列有效管理。操作系統(tǒng)是通過這些被稱為換的一系列有效管理。操作系統(tǒng)是通過這些被稱為原語的程序段對進程進行控制的原語的程序段對進程進行控制的n12.原語原語q原語是機器指令的延伸，由若干條機器指令構成，原

20、語是機器指令的延伸，由若干條機器指令構成，用于完成特定功能的一段程序。為了保證需哦的正用于完成特定功能的一段程序。為了保證需哦的正確性，原語在執(zhí)行的過程中是不可分割的，也即其確性，原語在執(zhí)行的過程中是不可分割的，也即其執(zhí)行過程是不允許被中斷的執(zhí)行過程是不允許被中斷的n13.進程同步進程同步q進程同步是指對多個相關進程在執(zhí)行次序上進行協(xié)調，進程同步是指對多個相關進程在執(zhí)行次序上進行協(xié)調，目的是使系統(tǒng)中諸進程之間能有效地共享資源和相互合目的是使系統(tǒng)中諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。用來實現(xiàn)同步的作，從而使程序的執(zhí)行具有可再現(xiàn)性。用來實現(xiàn)同步的機制被稱為同步機制。

21、機制被稱為同步機制。n14.進程的同步與互斥進程的同步與互斥q進程的互斥是指并發(fā)進程在競爭共享資源時的相互制約進程的互斥是指并發(fā)進程在競爭共享資源時的相互制約關系。關系。q進程的同步是指一個進程是否能使用共享資源依賴與其進程的同步是指一個進程是否能使用共享資源依賴與其他進程的執(zhí)行情況，一個進程在沒有受到其他進程的消他進程的執(zhí)行情況，一個進程在沒有受到其他進程的消息時必須等等待，直至另一進程送來消息后才可繼續(xù)執(zhí)息時必須等等待，直至另一進程送來消息后才可繼續(xù)執(zhí)行下去。行下去。同步與互斥的區(qū)別n同步q進程進程q時間次序上受到某種限制q相互清楚對方的存在及其作用，交換信息q往往指有幾個進程共同完成一個

22、任務q舉例：生產與消費之間，發(fā)送與接受之間，作者與讀者之間，供者與用者之間 n互斥q進程資源進程q競爭到某一物理資源時不允許進程工作q不一定清楚其它進程情況q往往指多個任務多個進程間通訊制約q舉例：交通十字路口，單軌火車的撥道岔 n15.臨界資源和臨界區(qū)臨界資源和臨界區(qū)q臨界資源特點：一次僅允許一個進程使用。臨界資源特點：一次僅允許一個進程使用。q臨界區(qū)：每個進程訪問臨界資源的那一段必須互斥執(zhí)行的程臨界區(qū)：每個進程訪問臨界資源的那一段必須互斥執(zhí)行的程序。一個共享變量可以有多個臨界區(qū)。把使用統(tǒng)一變量的一序。一個共享變量可以有多個臨界區(qū)。把使用統(tǒng)一變量的一組臨界區(qū)稱為組臨界區(qū)稱為“相關臨界區(qū)相關臨

23、界區(qū)”。并發(fā)進程不允許同時或交叉。并發(fā)進程不允許同時或交叉地在各個相關臨界區(qū)中執(zhí)行。地在各個相關臨界區(qū)中執(zhí)行。n16.同步機制應遵循的規(guī)則同步機制應遵循的規(guī)則n17.信號量機制及其應用信號量機制及其應用q信號量的含義：信號量是一個用來實現(xiàn)同步的整型信號量的含義：信號量是一個用來實現(xiàn)同步的整型或記錄型變量，除了初始化外，對它只能執(zhí)行或記錄型變量，除了初始化外，對它只能執(zhí)行wait和和signal兩種操作。兩種操作。q信號量的物理意義：一個信號量信號量的物理意義：一個信號量S通常對應于一類通常對應于一類臨界資源。臨界資源。S.wait申請資源，申請資源，S.signal釋放資源。釋放資源。S.va

24、lue表示當前可用資源數(shù)表示當前可用資源數(shù)q用信號量實現(xiàn)互斥用信號量實現(xiàn)互斥q用信號量實現(xiàn)前趨關系用信號量實現(xiàn)前趨關系n18.進程通信的類型進程通信的類型q共享存儲器系統(tǒng)共享存儲器系統(tǒng)q消息傳遞系統(tǒng)消息傳遞系統(tǒng)q管道通信管道通信n19.消息緩沖隊列通信機制應具有那幾方面的功能消息緩沖隊列通信機制應具有那幾方面的功能q構成消息：發(fā)送進程在工作區(qū)設置發(fā)送區(qū)，填信息。構成消息：發(fā)送進程在工作區(qū)設置發(fā)送區(qū)，填信息。q發(fā)送消息：將消息從發(fā)送區(qū)復制到消息緩沖區(qū)，并把它發(fā)送消息：將消息從發(fā)送區(qū)復制到消息緩沖區(qū)，并把它插入到目標進程的消息隊列中。插入到目標進程的消息隊列中。q接受消息：從消息隊列中去消息并拷貝

25、到接收區(qū)接受消息：從消息隊列中去消息并拷貝到接收區(qū)q互斥與同步：互斥與同步：n20.線程的屬性線程的屬性q輕型實體。線程中的實體基本上不擁有系統(tǒng)資源，輕型實體。線程中的實體基本上不擁有系統(tǒng)資源，只是有一點必不可少的、能保證獨立運行的資源。只是有一點必不可少的、能保證獨立運行的資源。q獨立調度和分派的基本單位。獨立調度和分派的基本單位。q可并發(fā)執(zhí)行?？刹l(fā)執(zhí)行。q共享進程資源。共享進程資源。n22.進程與線程的比較進程與線程的比較q調度型：在傳統(tǒng)的操作系統(tǒng)中，擁有資源的基本單位和調度型：在傳統(tǒng)的操作系統(tǒng)中，擁有資源的基本單位和獨立調度、分派的基本單位都是進程。而在引入線程的獨立調度、分派的基本單

26、位都是進程。而在引入線程的OS中，則把線程作為調度和分派的基本單位，把進程中，則把線程作為調度和分派的基本單位，把進程作為資源擁有的基本單位。作為資源擁有的基本單位。q并發(fā)性。在引入線程的并發(fā)性。在引入線程的OS中，不僅進程間可以并發(fā)執(zhí)中，不僅進程間可以并發(fā)執(zhí)行，而且在一個進程的多個線程間也可以并發(fā)執(zhí)行行，而且在一個進程的多個線程間也可以并發(fā)執(zhí)行q擁有資源。在這兩種擁有資源。在這兩種OS中，擁有資源的基本單位都是中，擁有資源的基本單位都是進程。線程除了一點在運行時必不可少的資源（如線程進程。線程除了一點在運行時必不可少的資源（如線程控制塊、程序計數(shù)器、一組寄存器值和堆棧）外，本身控制塊、程序計

27、數(shù)器、一組寄存器值和堆棧）外，本身基本不擁有系統(tǒng)資源，但可訪問其隸屬進程的資源。基本不擁有系統(tǒng)資源，但可訪問其隸屬進程的資源。q開銷。由于創(chuàng)建或撤銷進程時，系統(tǒng)要分配或回收資源；開銷。由于創(chuàng)建或撤銷進程時，系統(tǒng)要分配或回收資源；進程切換時要保存和設置的現(xiàn)場信息也明顯多于線程，進程切換時要保存和設置的現(xiàn)場信息也明顯多于線程，因此，因此，OS在創(chuàng)建、撤銷和切換進程時所付出的開銷明在創(chuàng)建、撤銷和切換進程時所付出的開銷明顯地大于線程。另外，由于隸屬于同一個進程的多個線顯地大于線程。另外，由于隸屬于同一個進程的多個線程共享同一地址空間和該進程的所有已打開文件，從而程共享同一地址空間和該進程的所有已打開文

28、件，從而使它們之間的同步和通信的實現(xiàn)也比進程更方便。使它們之間的同步和通信的實現(xiàn)也比進程更方便。n1.一條小河上有一座獨木橋一條小河上有一座獨木橋,規(guī)定每次只允許規(guī)定每次只允許一個人過橋一個人過橋,現(xiàn)在河東河西都有人要過橋現(xiàn)在河東河西都有人要過橋,如如果把每個過橋者看作一個進程果把每個過橋者看作一個進程,為保證安全為保證安全,請用請用PV操作實現(xiàn)正確管理操作實現(xiàn)正確管理.n2.一條小河上有一座獨木橋一條小河上有一座獨木橋,同一方向的可連同一方向的可連續(xù)過橋續(xù)過橋;某方向有人過橋時另一方向的人等待某方向有人過橋時另一方向的人等待,現(xiàn)在河東河西都有人要過橋現(xiàn)在河東河西都有人要過橋,如果把每個過橋如

29、果把每個過橋者看作一個進程者看作一個進程,為保證安全為保證安全,請用請用PV操作實操作實現(xiàn)正確管理現(xiàn)正確管理.n3.在一間酒吧里有三個音樂愛好者隊列，第一隊的在一間酒吧里有三個音樂愛好者隊列，第一隊的音樂愛好者只有隨身聽，第二隊只有音樂磁帶，第音樂愛好者只有隨身聽，第二隊只有音樂磁帶，第三隊只有電池。而要聽音樂就必須隨身聽、音樂磁三隊只有電池。而要聽音樂就必須隨身聽、音樂磁帶和電池這三種物品俱全。酒吧老板一次出售這三帶和電池這三種物品俱全。酒吧老板一次出售這三種物品中的任意兩種。當一名音樂愛好者得到這三種物品中的任意兩種。當一名音樂愛好者得到這三種物品并聽完一首樂曲后，酒吧老板才能再一次出種物

30、品并聽完一首樂曲后，酒吧老板才能再一次出售這三種物品中的任意兩種。于是第二名音樂愛好售這三種物品中的任意兩種。于是第二名音樂愛好者得到這三種物品并開始樂曲。全部買賣就這樣進者得到這三種物品并開始樂曲。全部買賣就這樣進行下去，試用行下去，試用p、v操作正確解決這一買賣。操作正確解決這一買賣。 n4.某私廟，有小和尚、老和尚若干。一水桶，有一某私廟，有小和尚、老和尚若干。一水桶，有一水缸，由小和尚提水入缸供老和尚飲用。水缸可容水缸，由小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次只能容桶水，水取自同一井中。水井徑窄，每次只能容一個水桶取水。水桶總數(shù)為一個水桶取水。水桶

31、總數(shù)為3。每次入、取缸水僅。每次入、取缸水僅為一桶，且不可同時進行。試給出有關取水、入水為一桶，且不可同時進行。試給出有關取水、入水的算法描述。的算法描述。 第3章 處理及調度調調度度級級別別作作業(yè)業(yè)調調度度（高高級級調調度度）進進程程對對換換（中中級級調調度度）進進程程調調度度（低低級級調調度度）調調度度隊隊列列選選擇擇調調度度方方式式和和算算法法的的準準則則調調度度算算法法先先來來先先服服務務短短作作業(yè)業(yè)優(yōu)優(yōu)先先多多級級反反饋饋隊隊列列高高優(yōu)優(yōu)先先權權優(yōu)優(yōu)先先時時間間片片輪輪轉轉多多級級隊隊列列實實時時調調度度處處理理機機調調度度死死鎖鎖概概念念產產生生原原因因處處理理方方法法必必要要條條

32、件件競競爭爭資資源源進進程程推推進進順順序序非非法法互互斥斥條條件件請請求求和和保保持持條條件件不不剝剝奪奪條條件件環(huán)環(huán)路路等等待待條條件件死死鎖鎖預預防防死死鎖鎖避避免免死死鎖鎖檢檢測測死死鎖鎖解解除除限限制制條條件件銀銀行行家家算算法法可可能能引引起起第3章 處理機調度與死鎖1. 三級調度三級調度n高級調度（作業(yè)調度或長程調度）：決定將后備隊列高級調度（作業(yè)調度或長程調度）：決定將后備隊列中的哪些作業(yè)調入內存中的哪些作業(yè)調入內存n低級調度（進程調度或短程調度）：決定就需隊列中低級調度（進程調度或短程調度）：決定就需隊列中哪個進程先獲得處理機哪個進程先獲得處理機q非搶占式非搶占式q搶占式搶占

33、式 搶占原則：優(yōu)先權原則、短作業(yè)有先、時間片原則搶占原則：優(yōu)先權原則、短作業(yè)有先、時間片原則n中級調度（中程調度）中級調度（中程調度）q目的：解決內存緊張問題，常用在分時系統(tǒng)及具有虛擬存儲器目的：解決內存緊張問題，常用在分時系統(tǒng)及具有虛擬存儲器的系統(tǒng)中。的系統(tǒng)中。2.選擇調度算法的準則選擇調度算法的準則（1）面向用戶的準則：）面向用戶的準則：（a）周轉時間短）周轉時間短（b）響應時間快）響應時間快（c）截止時間的保證）截止時間的保證（d）優(yōu)先權準則）優(yōu)先權準則（2）面向系統(tǒng)的準則：）面向系統(tǒng)的準則：（a）系統(tǒng)吞吐量高）系統(tǒng)吞吐量高（b）處理機利用率好）處理機利用率好（c）各類資源的平衡利用）各

34、類資源的平衡利用第3章 處理機調度與死鎖3.調度算法調度算法（1）先來先服務）先來先服務(FCFS)算法算法（2）短作業(yè)（進程）優(yōu)先）短作業(yè)（進程）優(yōu)先(SJF/SPF)算法算法（3）高優(yōu)先權優(yōu)先）高優(yōu)先權優(yōu)先(HPF)算法算法（4）高響應比優(yōu)先調度）高響應比優(yōu)先調度(HRRN)算法算法（5）時間片輪轉）時間片輪轉(RR)算法算法(常用于交互式系統(tǒng)常用于交互式系統(tǒng))（6）多級反饋隊列調度）多級反饋隊列調度(FB)算法算法第3章 處理機調度與死鎖n進程調度算法解決以何種次序對各就緒進程進行處理進程調度算法解決以何種次序對各就緒進程進行處理機的分配以及按何種時間比例讓進程占用處理機。時機的分配以及

35、按何種時間比例讓進程占用處理機。時間片輪轉進程調度算法的基本思想是什么？時間片的間片輪轉進程調度算法的基本思想是什么？時間片的大小對系統(tǒng)有什么影響？在選取取時間片時應考慮哪大小對系統(tǒng)有什么影響？在選取取時間片時應考慮哪些因素？些因素？q時間片輪轉法時間片輪轉法(RR)主要是分時系統(tǒng)中使用的一種調度算法。主要是分時系統(tǒng)中使用的一種調度算法。時間片輪轉法的基本思想是時間片輪轉法的基本思想是:將將CPU 的處理時間劃分成一個的處理時間劃分成一個個時間片個時間片,就緒隊列中的諸進程輪流運行一個時間片。就緒隊列中的諸進程輪流運行一個時間片。q在輪轉法中在輪轉法中,時間片長度的選擇將直接影響系統(tǒng)開銷和響應

36、時時間片長度的選擇將直接影響系統(tǒng)開銷和響應時間。如果時間片長度很小間。如果時間片長度很小,則調度程序剝奪處理機的次數(shù)頻繁則調度程序剝奪處理機的次數(shù)頻繁,加重系統(tǒng)開銷；反之，如果時間片長度選擇過長加重系統(tǒng)開銷；反之，如果時間片長度選擇過長,則輪轉法就則輪轉法就退化成先進先出算法。退化成先進先出算法。q影響時間片大小設置的主要因素有影響時間片大小設置的主要因素有:系統(tǒng)響應時間，就緒進系統(tǒng)響應時間，就緒進程數(shù)目程數(shù)目(終端數(shù)目終端數(shù)目)和計算機處理能力。和計算機處理能力。 n某進程被喚醒后立即投入運行，我們就說這個系統(tǒng)采用的是剝奪調度方法，對嗎？q答：不對。因為，芮當前就緒隊列為空，這樣，被喚醒進程

37、就是就緒隊列中惟一的一個進程，于是調度程序會立即將該進程投入運行。n在單處理機的分時系統(tǒng)中，分配給進程P的時間片用完后，系統(tǒng)進行切換，結果調度到的仍然是進程P。有可能出現(xiàn)上述情形嗎？如果可能請說明理由。q答：有可能出現(xiàn)上述情況。例如，若在進程P時間片用完后，被迫回到就緒隊列時，就緒隊列為空，這樣進程P就是就緒隊列中惟一的一個進程，于是調度程序選中的進程必然是進程P；又如在按優(yōu)先級調度的系統(tǒng)中，就緒隊列按進程優(yōu)先級排列，在進程P時間片用完之后回到就緒隊列時，若其優(yōu)先級高于當前就緒隊列中的其它進程，則它將排在就緒隊列之首，從而再次被調度進程選中并投入運行。n現(xiàn)有兩道作業(yè)同時執(zhí)行，一道以計算為主，另

38、一道以輸入輸出為主，你將怎樣賦予作業(yè)進程占有處理器的優(yōu)先級？為什么？q解解 如果計算進程的優(yōu)先級高于或者等于輸入輸出進程的優(yōu)先級，系統(tǒng)效率也不會提高。因為計算進程一旦占用了CPU便忙于計算，使輸入輸出進程得不到運行機會，同樣會使設備空閑，不能提高系統(tǒng)效率。q如果輸入輸出進程的優(yōu)先級高于計算進程的優(yōu)先級，系統(tǒng)效率就能夠得到提高。因為輸入輸出操作是一種速度極慢的操作。若該項操作的優(yōu)先級高，那么，當它完成一項輸入輸出操作后，便能立即獲得CPU，為下一次輸入輸出作準備工作，并啟動外部設備。當設備被啟動起來后，它便主動讓出CPU，由系統(tǒng)將CPU交給計算機進程使用。從而獲得較好的運行效率。4.產生死鎖的原

39、因產生死鎖的原因（1）競爭資源）競爭資源（2）進程間推進順序非法）進程間推進順序非法5.產生死鎖的必要條件產生死鎖的必要條件（1）互斥條件）互斥條件（2）請求和保持條件）請求和保持條件（3）不剝奪條件）不剝奪條件（4）環(huán)路等待條件）環(huán)路等待條件第3章 處理機調度與死鎖6.處理死鎖的基本方法處理死鎖的基本方法（1）預防死鎖）預防死鎖（2）避免死鎖）避免死鎖（3）檢測死鎖）檢測死鎖（4）解除死鎖）解除死鎖第3章 處理機調度與死鎖第3章 處理機調度與死鎖7.銀行家算法銀行家算法用到四個數(shù)據(jù)結構，執(zhí)行流程是：用到四個數(shù)據(jù)結構，執(zhí)行流程是：（1）某個進程發(fā)出資源請求）某個進程發(fā)出資源請求（2）判斷資源請

40、求是否合法，即：請求量不大于）判斷資源請求是否合法，即：請求量不大于最大需求量、不大于可用資源量最大需求量、不大于可用資源量（3）試探性將資源分配給該進程）試探性將資源分配給該進程（4）系統(tǒng)執(zhí)行）系統(tǒng)執(zhí)行安全性判定算法安全性判定算法，檢查分配后系統(tǒng)，檢查分配后系統(tǒng)是否處于安全狀態(tài)。如果安全，則確認此次分配，是否處于安全狀態(tài)。如果安全，則確認此次分配，否則撤銷此次分配。否則撤銷此次分配。n在解決死鎖問題的幾個方法中，哪種方法最容易實現(xiàn)?哪種方法使資源的利用率最高?q答：a. 解決死鎖可歸納為四種方法：q預防死鎖。通過一些限制條件的設置來破壞死鎖發(fā)生的四個必要條件中的一個或多個，以預防死鎖的發(fā)生。

41、q避免死鎖。在資源動態(tài)分配過程中用某些算法加以限制，防止系統(tǒng)進入不安全狀態(tài)從而避免死鎖的發(fā)生。q檢測死鎖。采取一定的機制檢測系統(tǒng)是否死鎖，以配合死鎖的解除。q解除死鎖。通過撤銷一些進程來回收資源把系統(tǒng)從死鎖中解脫出來。qb. 其中，預防死鎖是最容易實現(xiàn)的；c. 避免死鎖使資源的利用率最高.n有3個進程P1、P2和P3并發(fā)工作。進程P1需要資源S3和S1，進程P2需要資源S1和S2，進程P3需要資源S2和S3。那么，若對資源分配不加限制，會發(fā)生什么情況？為什么？為保證進程正確地工作，應采用怎樣的資源分配策略？為什么？n解：若對進程間的資源分配不加限制，可能會發(fā)生死鎖，因為這樣的分配可能導致進程間

42、的“循環(huán)等待”，并且這種狀態(tài)將永遠持續(xù)下去。進程P1、P2和P3分別獲得資源S3、S1和S2，后再繼續(xù)申請資源時都要等待。n為保證進程正確地工作，系統(tǒng)應該采取一定的資源分配策略來限制死鎖發(fā)生的必要條件。q限制請求和保持條件的發(fā)生?？梢砸筮M程只有一次性申請到了它所需的所有資源后才能得到運行，否則將放棄它申請到的資源。即采用靜態(tài)分配。q限制不剝奪條件的發(fā)生。可以允許系統(tǒng)中的進程在申請了系統(tǒng)中已經沒有了的資源后，可以從其他沒有在運行的進程中搶奪該資源。q限制環(huán)路等待條件的發(fā)生?？梢砸筮M程按照資源的編號來順序地申請資源。即P1進程先申請S1再申請S3，P2進程先申請S1再申請S2，P3進程先申請S

43、2再申請S3。第4章 存儲器管理程程序序處處理理步步驟驟內內存存分分配配算算法法優(yōu)優(yōu)點點優(yōu)優(yōu)點點請求頁式請求段式虛虛擬擬存存儲儲器器需需要要時時裝裝入入需需要要時時裝裝入入單單一一固固定定分分區(qū)區(qū)動動態(tài)態(tài)分分區(qū)區(qū)首首次次適適應應循循環(huán)環(huán)首首次次適適應應最最差差適適應應最最佳佳適適應應頁頁面面置置換換算算法法存存在在的的問問題題FIFOPBALRUOptimalNRULFUBelady異異常常抖抖動動裝裝入入到到哪哪里里？編編譯譯鏈鏈接接裝裝入入靜靜態(tài)態(tài)鏈鏈接接動動態(tài)態(tài)鏈鏈接接裝裝入入時時動動態(tài)態(tài)運運行行時時動動態(tài)態(tài)絕絕對對裝裝入入可可重重定定位位裝裝入入動動態(tài)態(tài)運運行行裝裝入入動動態(tài)態(tài)可可重重

44、定定位位離離散散分分配配方方式式連連續(xù)續(xù)分分配配方方式式基基本本分分頁頁段段頁頁式式基基本本分分段段一、內存管理概念n1.內存管理的功能存儲管理的主要任務時為多道程序的運行提供良好的環(huán)境，方便用戶使用存儲器、提高存儲器的利用率以及從邏輯上擴充存儲器。為此，存儲管理應具有如下功能：q內存的分配和回收q地址變換q擴充內存容量q存儲保護一、內存管理概念n2.應用程序的處理過程（1）用戶先編輯好應用程序（2）通過相關語言的編譯程序將其編譯成若干個目標模塊（3）再通過鏈接程序將編譯后的目標模塊以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊（4）最后通過裝入程序將它們裝入內存進行運行。一、內存管

45、理概念q程序的鏈接方式：n靜態(tài)鏈接：在程序運行之前，先把各個目標模塊及它們所需要的庫函數(shù)鏈接成一個完整的可執(zhí)行程序，以后不再拆開。n裝入時動態(tài)鏈接：將應用程序編譯后所得到的一組目標模塊在裝入內存時采用邊裝入邊鏈接方式。n運行時動態(tài)鏈接：對一些目標模塊的鏈接直到程序運行時才去對它進行鏈接，其優(yōu)點是便于修改和更新，便于實現(xiàn)目標模塊的共享。一、內存管理概念q程序的裝入方式n絕對裝入：在編譯時就知道程序將要駐留的內存地址，編譯程序產生絕對地址目標代碼。不適合多道程序設計。n可重定位裝入：根據(jù)內存當前的使用情況，將裝入模塊裝入到內存的適當位置，地址變換通常是在裝入時一次性完成的，之后都不再改變，也稱為靜

46、態(tài)重定位。特點：在一個作業(yè)裝入內存時必須分配其要求的全部內存空間，此外，不能在內存中移動或增加內存空間。n動態(tài)運行裝入：允許程序運行時在內存中移動位置，把裝入模塊裝入到內存后所有的地址都是相對地址，只有到程序需要真正執(zhí)行時才把相對地址轉換成絕對地址，也稱為動態(tài)重定位。特點：可以將程序分配到不連續(xù)的存儲區(qū)中，課裝入部分代碼。二、連續(xù)分配方式1.固定分區(qū)分配劃分分區(qū)的方法：分區(qū)大小相等、分區(qū)大小不等內存分配：將分區(qū)按大小進行排序，建立一張分區(qū)使用表優(yōu)點：可用于多道程序系統(tǒng)最簡單的存儲分配，無外部碎片缺點：不能實現(xiàn)多進程共享一個主存區(qū)，所以存儲空間利用率較低，有內部碎片。二、連續(xù)分配方式2.可變分區(qū)

47、分配q數(shù)據(jù)結構：空閑分區(qū)表、空閑分區(qū)鏈q分配算法：（1）首次適應n優(yōu)點：優(yōu)先利用內存低址部分的內存空間，無內部碎片n缺點：低址部分不斷劃分，有外部碎片；每次查找從低址部分開始，增加了查找的開銷。n要求：空閑分區(qū)表或空閑分區(qū)鏈按地址從低到高排列n循環(huán)首次適應、最佳（差）適應二、連續(xù)分配方式2.可變分區(qū)分配q數(shù)據(jù)結構：空閑分區(qū)表、空閑分區(qū)鏈q分配算法：（2）循環(huán)首次適應n優(yōu)點：使內存空閑分區(qū)分布均勻，減少查找開銷，無內部碎片n缺點：會導致缺乏大的空閑分區(qū)，有外部碎片n要求：空閑分區(qū)表或空閑分區(qū)鏈按地址從低到高排列二、連續(xù)分配方式2.可變分區(qū)分配q數(shù)據(jù)結構：空閑分區(qū)表、空閑分區(qū)鏈q分配算法：（3）最

48、佳適應算法n優(yōu)點：產生的外部碎片很小，無內部碎片n缺點：產生許多難以利用的小空閑區(qū)，仍有外部碎片n要求：空閑分區(qū)表或空閑分區(qū)鏈按其容量從小到大排列（4）最壞適應算法n優(yōu)點：使得留下來的空閑區(qū)較大，便于下次利用，無內部碎片n缺點：大的空閑區(qū)不容易保留，有外部碎片n要求：空閑分區(qū)表或空閑分區(qū)鏈按其容量從大到小排列二、連續(xù)分配方式2.可變分區(qū)分配q回收：合并相鄰的空閑區(qū)q拼接技術q分區(qū)的存儲保護：上下界寄存器方法、基址限長寄存器方法q動態(tài)分區(qū)分配的優(yōu)缺點n優(yōu)點：實現(xiàn)了多道程序共享主存、管理方案相對簡單，不需要更多的軟硬件開銷，實現(xiàn)存儲保護的手段比較簡單n缺點：主存利用不夠充分，即存在內部碎片，無法實

49、現(xiàn)多進程共享存儲器的信息，無法實現(xiàn)主存的擴充采用可變分區(qū)方式管理主存空間時，若主存中按地址順序依次有五個空閑區(qū)，空閑區(qū)大小分別為15k，28k，10k，226k，110k。現(xiàn)有五個作業(yè)Ja、Jb、Jc、Jd和Je，它們需要的主存依次為10k，15k，102k，26k，80k。如果采用最先適應算法能把這五個作業(yè)按JaJe的次序全部裝入主存嗎？用什么分配算法裝入這五個作業(yè)可使主存的利用率最高？ 1.離散分配方式分類分頁、分段2.基本分頁存儲管理的實現(xiàn)思想作業(yè)分頁，內存分塊，頁大小等于塊大小3.分頁地址結構頁號+頁內位移4.分頁地址變換（1）求頁號和頁內位移；（2）查頁表得塊號；（3）計算物理地址：

50、塊號*塊大小+頁內位移5.基本分頁存儲管理方式的優(yōu)缺點q優(yōu)點：存在頁內碎片，但碎片相對較小，內存利用率教高；實現(xiàn)了離散分配，消除了程序浮動；便于存儲訪問控制，有利于代碼共享；無外部碎片。q缺點：需要專門的硬件支持，尤其是快表；內存訪問的效率下降；不支持動態(tài)鏈接，不能實現(xiàn)真正的共享；有內部碎片6.分頁和分段有何異同三、離散分配方式n為滿足264地址空間的作業(yè)運行，采用多級分頁存儲管理方式，假設頁面大小為4KB，在頁表中的每個頁表項需要占8個字節(jié)，則為了滿足系統(tǒng)的分頁管理至少應采用多少級頁表？n解：頁面大小=4KB=212字節(jié)，每個頁表項為8字節(jié)，所以一個頁面中可以存放212/23=29個頁表項。

51、設有n層分頁，則64位邏輯地址形式為： 第1層頁號第2層頁號第n層頁號頁內偏移量其中其中,頁面大小為頁面大小為212字節(jié)，所以頁內偏移量占字節(jié)，所以頁內偏移量占12位位.剩下剩下64-12=52位位,由由于每層指向一個物理塊于每層指向一個物理塊,其中可放下其中可放下29個頁表項個頁表項,所以所以52/9=6(向上取整向上取整)。四、虛擬內存管理1.虛擬存儲器的定義 虛擬存儲器是指具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統(tǒng)。2.實現(xiàn)虛擬存儲技術的硬件支持q要有相當數(shù)量的外存：足以存放多個用戶的程序q要有一定容量的內存：因為在處理機上運行的程序必須有一部分信息存放在內

52、存中。q地址變換機構：以動態(tài)實現(xiàn)虛地址到實地址的地址變換3.常用的虛擬存儲技術q請求分頁存儲管理q請求分段存儲管理q請求段頁式存儲管理4.虛擬存儲器的特征多次性、對換性、虛擬性五、請求分頁存儲管理1.請求分頁的硬件支持頁表、缺頁中斷（指令執(zhí)行期間發(fā)生中斷）、地址變換機構2.內存分配策略和分配算法（1）最小物理塊數(shù)的確定：能保證程序運行所需的最小物理塊數(shù)（2）物理塊的分配策略 固定分配局部置換、可變分配全局置換、可變分配局部置換（3）物理塊分配算法 平均分配算法、按比例分配算法、考慮優(yōu)先權分配算法3.調頁策略（1）調入頁面的時間：請求調頁策略、預調頁策略（2）從何處調入：兌換區(qū)、文件區(qū)（未修改的

53、頁面）+兌換區(qū)、unix方式是文件區(qū)（未運行過的頁面）+兌換區(qū)（運行過又被換出的頁面）4.頁面置換算法 最佳置換算法、先進先出（FIFO）置換算法、最近最久未使用（LRU）置換算法、Clock置換算法 頁面置換時，一定有頁面被寫到磁盤交換區(qū)嗎？（no） 5.缺頁率 影響缺頁的因素：q頁面置換算法：其優(yōu)略影響缺頁中斷次數(shù)q主存物理塊數(shù)：其數(shù)目越多，缺頁率越低q頁面大小：頁面大，缺頁率低，反之，缺頁率高q程序特性：編程方法對缺頁中斷次數(shù)有影響目前，大多數(shù)計算機系統(tǒng)都支持虛擬頁式地址轉換機制。試回答下列問題：(1)頁式存儲管理方案中，用戶地址空間怎樣劃分？內存地址空間怎樣劃分？內存分配過程是怎樣的？

54、(2)頁表應設計哪些數(shù)據(jù)項，每個數(shù)據(jù)項的作用是什么？(3)頁式存儲管理方案中，地址映射機制需要哪種寄存器的支持？為了加快地址映射速度，需要采取什么措施？該措施的作用是什么？答：(1)系統(tǒng)將用戶程序的邏輯空間按照相等大小劃分成若干界面，稱為邏輯頁面。各個邏輯頁面從0開始依次編號，每個邏輯頁面內也從0開始編址，稱為頁內地址。用戶程序的邏輯地址由邏輯頁號和頁內地址兩部分組成。頁式存儲管理將內存空間按照邏輯頁面大小劃分成等長的若干區(qū)域，每個區(qū)域為一個內存塊。內存的所有內存塊從0開始編號。內存分配時，以頁面（塊）為單位，并按用戶程序所需頁數(shù)多少進行分配。邏輯上相鄰的頁面在內存中不一定相鄰，即分配給用戶程

55、序的內存塊不一定連續(xù)。(2)頁表表項有：邏輯頁面號；物理頁面號（或塊號）；駐留位（中斷位或特征位）：指示該頁在內存還是在外存；外存地址：指示該頁在外存的地址；修改位：指示該頁在內存駐留期間是否被修改過；(3)系統(tǒng)提供一對硬件寄存器：頁表始址寄存器和頁表長度寄存器。頁表始址寄存器，用于保存正在運行進程的頁表在內存的首地址。當進程被調度程序選中投入運行時，系統(tǒng)將其頁表首地址從進程控制塊中取出送入該寄存器。頁表長度寄存器，用于保存正在運行進程的頁表的長度。當進程被選中運行時，系統(tǒng)將它從進程控制塊中取出送入該寄存器。為了加快地址映射速度，可在地址映射機制中增加一個小容量的聯(lián)想寄存器（相聯(lián)存儲器），它由

56、高速寄存器組成，成為一張快表，快表用來存放當前訪問最頻繁的少數(shù)活動頁的頁號。 n什么是抖動? 產生抖動的原因是什么?n答a. 抖動(Thrashing)就是指當內存中已無空閑空間而又發(fā)生缺頁中斷時，需要從內存中調出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中，如果算法不適當，剛被換出的頁很快被訪問，需重新調入，因此需再選一頁調出，而此時被換出的頁很快又要被訪問，因而又需將它調入，如此頻繁更換頁面，以致花費大量的時間，我們稱這種現(xiàn)象為抖動;nb. 產生抖動的原因是由于CPU 的利用率和多道程序度的對立統(tǒng)一矛盾關系引起的，為了提高CPU 利用率，可提高多道程序度，但單純提高多道程序度又會造成缺頁率的急劇上升，導

57、致CPU 的利用率下降，而系統(tǒng)的調度程序又會為了提高CPU 利用率而繼續(xù)提高多道程序度，形成惡性循環(huán)，我們稱這時的進程是處于抖動狀態(tài)。一個好的調度算法應減少和避免抖動現(xiàn)象。以存儲管理中的段式存儲管理為例，請敘述操作系統(tǒng)對內存的具體管理方案（包括功能、數(shù)據(jù)結構和算法）。首先從內存劃分、程序邏輯地址劃分、內存分配幾方面考慮段式存儲管理方案的工作原理：內存劃分：內存空間被動態(tài)地劃分為若干個長度不相同的區(qū)域，每個區(qū)域稱作一個物理段、每個物理段在內存中有一個起始地址，稱作段首址。將物理段中的所有單元從0 開始依次編址，稱為段內地址。邏輯地址空間劃分：用戶程序按邏輯上有完整意義的段來劃分。稱為邏輯段。例如

58、主程序、子程序、數(shù)據(jù)等都可各成一段，每段對應于一個過程，一個程序模塊或一個數(shù)據(jù)集合。將一個用戶程序的所有邏輯段從0 開始編號，稱為段號。將一個邏輯段中的所有單元從0開始編址，稱為段內地址。用戶程序的邏輯地址由段號和段內地址兩部分組成：段號，段內地址內存分配：系統(tǒng)以段為單位進行內存分配，為每一個邏輯段分配一個連續(xù)的內存區(qū)(物理段)。邏輯上連續(xù)的段在內存不一定連續(xù)存放。然后，從實現(xiàn)方法上考慮：建立段表系統(tǒng)為每個用戶程序建立一張段表，用于記錄用戶程序的邏輯段與內存物理段之間的對應關系，包括邏輯段號，物理段首地址和物理段長度三項內容。用戶程序有多少邏輯段，該段表里就登記多少行，且按邏輯段的順序排列。段

59、表存放在內存系統(tǒng)區(qū)里。建立空閑區(qū)表系統(tǒng)中設立一張內存空閑區(qū)表，記錄內存中空閑區(qū)域情況，用于為段分配和回收內存。系統(tǒng)在尋找空閑區(qū)時可采用以下三種分配算法。首先適應算法根據(jù)申請，在空閑區(qū)表中選取第一個滿足申請長度的空閑區(qū)。此算法簡單，可以快速做出分配決定。最佳適應算法根據(jù)申請，在空閑區(qū)表中選擇能滿足申請長度的最小空閑區(qū)。此算法最節(jié)約空間，因為它盡量不分割大的空閑區(qū)。其缺點是可能會形成很多很小的空閑區(qū)域，稱作碎片。最壞適應算法根據(jù)申請，在空閑區(qū)表中選擇能滿足申請要求的最大的空閑區(qū)。該算法的出發(fā)點是：在大空頭區(qū)中裝人信息后，分割剩下的空閑區(qū)相對也大，還能用于裝入新的信息。該算法的優(yōu)點是可以避免形成碎片

60、；缺點是分割大的空閑區(qū)后，再遇到較大的申請時，無法滿足的可能性較大。 設某計算機的邏輯地址空間和物理地址空間均為設某計算機的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。若，按字節(jié)編址。若某進程最多需要某進程最多需要6頁數(shù)據(jù)存儲空間，頁的大小為頁數(shù)據(jù)存儲空間，頁的大小為1KB。操作系統(tǒng)采用固定。操作系統(tǒng)采用固定分配局部置換策略為此進程分配分配局部置換策略為此進程分配4個頁框，如下個頁框，如下：頁號頁號頁框號頁框號裝入時刻裝入時刻訪問位訪問位071301142301222001391601當該進程執(zhí)行到當該進程執(zhí)行到260時刻時，要訪問邏輯地址為時刻時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請