湯子瀛版操作系統(tǒng)筆記

四、器管理六、文件管一、操作系統(tǒng)引OSOS，其目標(biāo)各有所側(cè)重。通常在計(jì)算機(jī)硬OS，其目標(biāo)有以下幾點(diǎn)：作為軟件接口，給用戶提供三種方式命令方式OS提供了一組聯(lián)機(jī)命令(語言)圖形、窗口方式。用戶通過屏幕上的窗口和圖標(biāo)來計(jì)算機(jī)系統(tǒng)和運(yùn)行為四類：處理器、器、I/O設(shè)備以及信息(數(shù)據(jù)和程序)。相應(yīng)地，OS的主要功能也正是針對這四類資源進(jìn)行有效的管理，即：（四類資源管理者）處理機(jī)管理，用于分配和控制處理機(jī)器管理，主要負(fù)責(zé)內(nèi)存的分配與回收；（最重要是內(nèi)存管理可見，OS確是計(jì)算機(jī)系統(tǒng)資源的管理者。事實(shí)上，世界上廣為流行的一個(gè)關(guān)于OS作用的觀點(diǎn)，正是把OS作為計(jì)算機(jī)系統(tǒng)的資源管理者。對于一臺完全無軟件的計(jì)算機(jī)系統(tǒng)(即機(jī))，即使其功能再強(qiáng)，也必定是難于使用的。如果我們在機(jī)上覆蓋上一層I/O設(shè)備管理軟件，用戶便可利用它所提供的I/O命令，來進(jìn)行數(shù)據(jù)輸入和打印輸出。此時(shí)用戶所看到的機(jī)器，將是一臺比機(jī)功能更強(qiáng)、使用更方便的機(jī)器通常把覆蓋了軟件的機(jī)器稱為擴(kuò)充機(jī)器或虛機(jī)器（虛擬機(jī)。如果我們又在第一層覆蓋一層面向用戶的窗口軟件，則用戶便可在窗口環(huán)境下方便地使用計(jì)算機(jī)，形成一臺功能更強(qiáng)的虛機(jī)器。無操作系統(tǒng)的計(jì)算機(jī)系統(tǒng)(1945年)50年代中期的計(jì)算機(jī)，屬于第一代，這時(shí)還未出現(xiàn)OS。人工操作方式有以下兩方面的缺點(diǎn)(1)(2CPU等待人工操作。單道批處理系統(tǒng)（50年代）過程：一批作業(yè)以脫機(jī)方式輸入到磁帶上，在監(jiān)督程序的控制下連續(xù)處理。該系統(tǒng)的主要特征如下：自動(dòng) 無人工干預(yù)。（缺少人機(jī)交互的特性，但相比之前較好（單道 內(nèi)存中只保存一道作業(yè)。（資源利用率低、吞吐量少多道批處理系統(tǒng)（60年代）多道技術(shù)是共享的基礎(chǔ)。多道性內(nèi)存中多道程序可并發(fā)執(zhí)行無序性完成時(shí)間和進(jìn)入內(nèi)存先后無關(guān)調(diào)度 作業(yè)從提交（送到系統(tǒng)的外存）到完成經(jīng)過兩次調(diào)度作業(yè)調(diào)度外存→內(nèi)存（選多個(gè)多道批處理系統(tǒng)的優(yōu)缺點(diǎn)：資源利用率高系統(tǒng)吞吐量大（2）平均周轉(zhuǎn)時(shí)間長作業(yè)周轉(zhuǎn)時(shí)間：從作業(yè)進(jìn)入系統(tǒng)開始到完成并退出系統(tǒng)經(jīng)歷的時(shí)間無交互能力分時(shí)系統(tǒng)（60年代）定義：一臺主機(jī)上連接了多個(gè)終端，同時(shí)允許多個(gè)用戶通過自己的終端，以人—機(jī)交互。（邊運(yùn)行邊調(diào)試多路 即同時(shí)性，宏觀上同時(shí)微觀上輪流獨(dú)立性每個(gè)用戶感覺獨(dú)占主機(jī)(Rel-imeysem)是指系統(tǒng)(或即時(shí))響應(yīng)外部事件的請求，在規(guī)定的時(shí)間內(nèi)完成對該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。應(yīng)用需求實(shí)時(shí)控制：工業(yè)生產(chǎn)、控制飛機(jī)的自動(dòng)駕計(jì)算機(jī)操作系統(tǒng)的三種基本類型：多道批處理系統(tǒng)、分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)實(shí)時(shí)信息處理：訂票系統(tǒng)（加鎖操作解決數(shù)據(jù)冗余操作系統(tǒng)的基本特征并行性和并發(fā)性是既相似又有區(qū)別的兩個(gè)概念，并行性是指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生并發(fā)性是指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。在多道程序環(huán)境（宏觀并發(fā)微觀串行可被分配到多個(gè)處理機(jī)上（每個(gè)處理機(jī)來處理一個(gè)可并發(fā)執(zhí)行的程序，這樣，多個(gè)程序便可同時(shí)執(zhí)行。共享性兩種資源共享方式：臨界資源：在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程的資源稱為臨界資源或獨(dú)占資源。如、磁帶機(jī)等硬件、棧、變量和表格等同時(shí)方多個(gè)進(jìn)程同時(shí)的資源，如：磁盤、重寫碼寫的文件。并發(fā)和共享是操作系統(tǒng)的兩個(gè)最基本的特征虛擬虛擬：是指通過某種技術(shù)把一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對應(yīng)物。如：虛擬處理機(jī)、虛擬內(nèi)存、虛擬外部設(shè)備和虛擬信道等。虛擬是通過分時(shí)來實(shí)現(xiàn)的時(shí)使用一臺處理機(jī)的。此時(shí)，雖然只有一臺處理機(jī)，但它能同時(shí)為多個(gè)用戶服務(wù)，使每個(gè)終端用戶都認(rèn)為是有一個(gè)CPU在專門為他服務(wù)。亦即，利用多道程序設(shè)計(jì)技CPU虛擬為多臺邏輯上的CPU，也稱為虛擬處理機(jī)，進(jìn)程以人們不可預(yù)知的速度向前推進(jìn)操作系統(tǒng)的五大功能處理機(jī)管理（硬件器管理（硬件資源管 設(shè)備管理（硬件 命令接口（用戶和計(jì)算機(jī)系統(tǒng)之間）脫機(jī)用戶接口（無交互） 圖形接聯(lián)機(jī)用戶接口組成：命令+終端處理程序+命令解釋程過程：用戶在終端或控制臺上每鍵入一條命令后，系統(tǒng)便立即轉(zhuǎn)入命令解釋程序，對該命令加用戶在鍵盤上輸入命令；終端處理程序接收命令并顯示在屏幕上命令解釋程序解釋并執(zhí)行該命令。（操作系統(tǒng)的最脫機(jī)用戶接口適用：批處理系統(tǒng)。又稱批處理用戶接口。（由預(yù)輸入過程）組成：JL+作業(yè)說明+命令解釋程序JCL：作業(yè)控制語言JobControl過程：用戶把對作業(yè)的控制用JCL寫在作業(yè)說明書上，命令解釋程序按照作業(yè)說明書解釋并程序接口目的：為用戶程序系統(tǒng)資源而設(shè)置。（是用戶程序取得操作系統(tǒng)服務(wù)的惟一途徑）組成：一組系統(tǒng)調(diào)用系統(tǒng)調(diào)用：一個(gè)系統(tǒng)調(diào)用是一個(gè)能完成特定功能的子程序OS結(jié)構(gòu)OS結(jié)構(gòu)現(xiàn)代OS結(jié)構(gòu)。二、進(jìn)程管進(jìn)程的基本概程序在并發(fā)環(huán)境中的執(zhí)行過進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位程序順序執(zhí)行時(shí)的特順序性：處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每一個(gè)操作必須在下一個(gè)操作執(zhí)行前結(jié)束。封閉性 程序在封閉環(huán)境下執(zhí)行，結(jié)果不受外界可再現(xiàn)性句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(PartialOrder)或前趨關(guān)系(PrecedenceRelation)“→”?！?{(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,Pi→Pj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。趨圖中，把沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(InitialNode)，把沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(FinalNode)。每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間程序的并發(fā)執(zhí)程序并發(fā)執(zhí)行間斷 共享、合作、制約導(dǎo)致：執(zhí)行——暫?！獔?zhí)失去封閉性資源狀態(tài)由多程序不可再現(xiàn) 相同環(huán)境和初始條件，重復(fù)執(zhí)行結(jié)果不同進(jìn)程的特PCB進(jìn)程控制塊（頭腦，一定處于內(nèi)存當(dāng)中→動(dòng)態(tài)特征的集中反映ProcessControl→描述要完成的功能→程序段和數(shù)據(jù)段可能與外存中，運(yùn)行過程中從外存動(dòng)態(tài)調(diào)進(jìn)程最基本的特征是動(dòng)態(tài)性進(jìn)程的生命周期：進(jìn)程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，有撤銷而消亡的過程：多個(gè)進(jìn)程同在內(nèi)存中，且能在一段時(shí)間同時(shí)運(yùn)行：進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源、獨(dú)立接收調(diào)度的基本單位：進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)進(jìn)程和程序的關(guān)進(jìn)程是一個(gè)動(dòng)態(tài)概念，程序是一個(gè)靜態(tài)概念進(jìn)程具有并行特征，程序沒有進(jìn)程是競爭資源的基本單位一個(gè)程序?qū)?yīng)多個(gè)進(jìn)程，一個(gè)進(jìn)程為多個(gè)程序服務(wù)就緒(Ready)這樣的進(jìn)程可能有多個(gè)，通常排成一個(gè)隊(duì)列，稱就緒隊(duì)列CPU在單處理機(jī)系統(tǒng)只有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)。多處理機(jī)系統(tǒng)則有多個(gè)處于執(zhí)行狀態(tài)。引起阻塞的事件：請求I/O，申請緩存。就時(shí)間片I/O完 進(jìn)程調(diào)阻 執(zhí)I/O請掛起狀

引入掛起狀態(tài)的原因終端用戶的請求父進(jìn)程請求負(fù)荷調(diào)節(jié)的需要。（實(shí)時(shí)操作系統(tǒng)操作系統(tǒng)的需要掛起引起的狀態(tài)轉(zhuǎn)換靜止?fàn)?活動(dòng)狀 注：活動(dòng)就緒在內(nèi)存，靜止就緒外進(jìn)程控制OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理PCB是進(jìn)程存在的唯一標(biāo)進(jìn)程標(biāo)識外部標(biāo)識 由字母、數(shù)字組成，給用戶使處理機(jī)狀處理機(jī)中主要的寄存12通用寄存器8~32個(gè)，用于暫存信息指令計(jì)數(shù)器要的下一條指令地123程序狀態(tài)字 條件碼、執(zhí)行方式（程序在系統(tǒng)態(tài)/用戶態(tài)執(zhí)行）、中斷3標(biāo)4用戶棧指 用戶進(jìn)程擁有的系統(tǒng)棧，存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地4 進(jìn)程控制信資源：除CPU之外所需資源與已經(jīng)分配資源（進(jìn)程執(zhí)行過程中動(dòng)態(tài)

1）方把統(tǒng)一狀態(tài)的PCB，用其中的字成一個(gè)隊(duì)列如就緒隊(duì)列、阻塞隊(duì)列（根44PCB0……建立就緒索引表、阻塞索引表等。把索引表在內(nèi)存的首地址放在內(nèi)存的的單執(zhí)行執(zhí)行指就緒索引阻塞表指就緒表指阻塞索引阻塞表指就緒表指進(jìn)程管理中最基本功能是進(jìn)程控制進(jìn)程控制一般OS內(nèi)核來實(shí)現(xiàn)引起創(chuàng)建進(jìn)程用戶登錄作業(yè)調(diào)度 由系統(tǒng)內(nèi)核創(chuàng)提供服務(wù)進(jìn)程的創(chuàng)建(背)原語CREAT（）按下列步驟創(chuàng)建一個(gè)新進(jìn)申請空PCBPCB初始化標(biāo)識信初始化處理機(jī)狀態(tài)信初始化處理及控制信引起進(jìn)程終止1越界錯(cuò)誤。這是指程序所的區(qū)，已越出該進(jìn)程的區(qū)域12保護(hù)錯(cuò)。進(jìn)程試圖去一個(gè)不允許的資源或文件，或者以不適當(dāng)?shù)姆绞竭M(jìn)行，例如，進(jìn)程試圖去寫一個(gè)只讀文件；23指令。程序試圖去執(zhí)行一條不存在的指令。出現(xiàn)該錯(cuò)誤的原因，可能是程序錯(cuò)誤地轉(zhuǎn)移到數(shù)據(jù)區(qū)，把數(shù)據(jù)當(dāng)成了指令；345456等待超時(shí)。進(jìn)程等待某事件的時(shí)間 超過了規(guī)定的最大值67算術(shù)運(yùn)算錯(cuò)。進(jìn)程試圖去執(zhí)行一個(gè)被的運(yùn)算，例如，被0除78I/O故障。這是指在I/O過程中發(fā)生了錯(cuò)誤等8外界干1操作員或操作系統(tǒng)干預(yù)。由于某種原因，例如，發(fā)生了死鎖，由操作員或1作系統(tǒng)終止該2父進(jìn)程請求。由于父進(jìn)程具有終止自己的任何子孫進(jìn)程的權(quán)利，因而當(dāng)父進(jìn)23父進(jìn)程終止 當(dāng)父進(jìn)程終止時(shí)，OS也將他的所有子孫進(jìn)程終止3進(jìn)程的終止過根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程 或者歸還給系統(tǒng)將被終止進(jìn)程(PCB)從所在隊(duì)列(或鏈表)進(jìn)程的阻塞和喚引起進(jìn)程阻塞和喚醒的事件（了解1）請求系統(tǒng)服啟動(dòng)某種操新數(shù)據(jù)尚未到無新工作可進(jìn)程阻塞過通過調(diào)用阻塞原語bock把自己阻塞bock態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列。如果系統(tǒng)中設(shè)置了因不同事件而阻塞的多個(gè)阻塞隊(duì)列，則應(yīng)將本進(jìn)程插入到具有相同事件的阻塞(等待)隊(duì)列。度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀態(tài)(在PCB中)PCB中的處理機(jī)狀態(tài)設(shè)置CPU的環(huán)境。→保留當(dāng)前進(jìn)程的CPU現(xiàn)場→置該進(jìn)程狀態(tài)→進(jìn)入等待隊(duì)列→轉(zhuǎn)進(jìn)程調(diào)度進(jìn)由喚醒原語WAKEUP成→從等待隊(duì)列中摘除被喚醒進(jìn)程→置該進(jìn)程為就緒狀態(tài)→進(jìn)入就緒隊(duì)列→轉(zhuǎn)進(jìn)程進(jìn)程的掛掛起原語：suspend將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起間接相互制約關(guān)系 進(jìn)程間由于共享某種系統(tǒng)資源，而形成的相互制約在執(zhí)行時(shí)間上必須按一定順序協(xié)調(diào)進(jìn)臨界資 一次僅允許一個(gè)進(jìn)程使用的共享資臨界資 一次僅允許一個(gè)進(jìn)程使用的共享資臨界 在每個(gè)進(jìn)程 臨界資源的那段程臨界資源的循環(huán)進(jìn)程描述如下 檢查臨界資源是否能 將臨界區(qū)標(biāo)志設(shè)為未同步機(jī)制應(yīng)遵循的規(guī)空閑讓進(jìn)忙則等待有限等待讓權(quán)等待信號量機(jī)信號量是一種數(shù)據(jù)結(jié)信號量的值僅由P、V操作來改變整型信號量整型 用S表示＜=0不可whileS≤0dono- //循環(huán)檢測S的狀S：=S-V操作（signal）原語 wait(S)signal(S)是兩個(gè)標(biāo)準(zhǔn)的原子操作(AtomicOperation)。缺點(diǎn)：只要信號量S<=0就不斷測試，不滿足讓權(quán)等待。記錄型信號量記錄型結(jié)構(gòu)，包含兩個(gè)數(shù)據(jù)項(xiàng)typeL:listofprocess;相應(yīng)地，wait(S)和signal(S)操作可描述為：procedure ifS.value＜0thenproceduresignal(S) varS:semaphore; ifS.value≤0thenwakeup(S,L);在記錄型信號量機(jī)制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號量，對它的每次wait 操作，意味著進(jìn)程請求一個(gè)單位的該類資源，因此描述為S.value∶=vae1；當(dāng)au＜0blck原語，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號量鏈表L中?？梢?，該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。此時(shí)aue。sialvale∶=vae1。若加1后仍是ale0wap原語，將Lae的初值為，表示只允許一個(gè)進(jìn)程臨界資源，時(shí)的信號量轉(zhuǎn)化為互斥信號量。 AND型信號量在兩個(gè)進(jìn)程中都要包含兩個(gè)DmutexEmutex的操作，process process 若進(jìn)程AB按下述次序交替執(zhí)行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processAwait(Emutex);Emutex=-1A阻塞processBwait(Dmutex);Dmutex=-1B阻塞在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作即Swait(Simultaneouswait)定義如下：Swait(S1,S2,…,Sn)ifS1≥1and…andSn≥1thenfori∶ 1tondoSi∶= placetheprocessinthewaitingqueueassociatedwiththefirstSifound Si＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationSsignal(S1,S2,…,fori∶ 1tondoRemovealltheprocesswaitinginthequeueassociatedwithSiintothe信號量一般“信號量集”的幾種特殊情況個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配Swait(S,1,1)。此時(shí)的信號量集已蛻化為一般的記錄型信號量(S＞1時(shí))或互斥信號量(S=1時(shí))。Swait(S10)。這是一種很特殊且很有用的信號量操作。當(dāng)S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)利用信號量實(shí)現(xiàn)進(jìn)程利用信號量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程可描述如下Varmutex:semaphore∶= process1:beginwait(mutex);//申請資源criticalsection//臨界區(qū)signal(mutex);//退出區(qū)remaindersection//untilprocess2:criticalsectionuntilfalse;在實(shí)現(xiàn)互斥時(shí)應(yīng)注意wait(mutex)和signal(mutex)必須成對的出缺wait(mutex)將會(huì)引起系統(tǒng)，不能保證對臨界資源的互斥signal(mutex)將會(huì)使該臨界資源永久不被釋放與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中；消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，例如：在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者而在輸出時(shí)，則計(jì)算進(jìn)程是生產(chǎn)者，而打印進(jìn)程是消費(fèi)者利用記錄型信號量解決生產(chǎn)者—消費(fèi)假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中，具有n個(gè)緩沖區(qū)，這時(shí)可利用互斥信號量muex實(shí)現(xiàn)諸進(jìn)程對緩沖池的互斥使用；利用信號量empy和ull分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將—消費(fèi)者問題可描述如下Varmutex,empty,full:semaphore∶ 1,n,0buffer:array［0,…,n-1］ofitem; in,out:integer∶= 0,0; …produceranitem //循環(huán)生產(chǎn)數(shù)buffer(in)∶ in∶= (in+1)modn; untilfalse; (out+1)modn;consumertheiteminnextc;untilfalse;wait(mutex)signal(mutex)其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計(jì)算進(jìn)程中，而signal(empty)則在打印進(jìn)程中，計(jì)算進(jìn)程若因執(zhí)行wait(empty)而阻塞，則以后將由打印進(jìn)程將它喚醒；最后，在每個(gè)程序中的多waitwait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。哲學(xué)家進(jìn)餐問Varchopstick:array［0,…,4］of所有信號量均被初始化為1，（記錄型信號量）第i位哲學(xué)家的活動(dòng)可描述為 //筷子從0-………untilfalse;0，當(dāng)他們再拿可采取以下幾種解決方法至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過的兩只筷子，從而使的哲學(xué)家能夠進(jìn)餐。僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學(xué)家相反。按此規(guī)定，將是1、2號哲學(xué)家競爭1號筷子；3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問在哲學(xué)家進(jìn)餐問題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號量機(jī)制可獲得最簡潔的解法。Varchopsiickarray［0,…,4］ofsemaphore∶ Sswait(chopstick［(i+1)mod5］,chopstick［i］);Ssignat(chopstick［(i+1)mod5］,chopstick［i］);untilfalse;讀者-寫者問要求讀的進(jìn)程稱為“Reader進(jìn)程”，其他進(jìn)程稱為“Writer進(jìn)程”程或Writer進(jìn)程同時(shí)共享對象。利用記錄型信號量解決讀者-寫者問為實(shí)ReaderWriter進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互Wmutex。另外，再設(shè)置一個(gè)整型變量Readcount表示正在讀的進(jìn)程數(shù)目。由于只要有一個(gè)Reader進(jìn)WriterReadcount=0Reader進(jìn)程在讀時(shí)，Reader進(jìn)程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進(jìn)操作后其值為0時(shí)，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進(jìn)程寫。又因?yàn)镽eadcount是一個(gè)可被多個(gè)Reader進(jìn)程的臨界資源，因此，應(yīng)該為它設(shè)置一個(gè)互斥信號量rmutex。讀者-寫者問題可描述如下Varrmutex,wmutex:semaphore∶ ifreadcount=0thenwait(wmutex); …performread… ifreadcount=0thensignal(wmutex);untilfalse;performwriteoperation;until交換的信息量一個(gè)狀態(tài)或數(shù)值低級通信：進(jìn)程的互斥和同OS提供的一組通信命令，高效的傳送大量數(shù)據(jù)的一高級通信的分類：共享器系統(tǒng)、消息傳遞系統(tǒng)、管道通信共享器系統(tǒng)基于共享區(qū)的通信方式。為了傳送大量的數(shù)據(jù)，在器中劃出一塊共享存消息傳遞系信息交換的單位是消息或報(bào)文，分兩直接通信方式：發(fā)送進(jìn)程直接把消息發(fā)給目標(biāo)進(jìn)這種中間實(shí)體稱為信訊Send(P2m1)m1P2;Receive(P1，m1)則表示接收由P1發(fā)來的消息m1。解決生產(chǎn)者-消費(fèi)者問題（直接通信方式…produceanitemin…untilfalse;receive(producer,…consumetheiteminnextc;untilfalse;間接通信方進(jìn)程可利用信箱創(chuàng)建原語來建立一個(gè)新信箱。創(chuàng)建者進(jìn)程應(yīng)給出信箱名字、信箱屬性(公用、私用或共享)；對于共享信箱，還應(yīng)給出共享者的名字。當(dāng)當(dāng)進(jìn)程之間要利用信箱進(jìn)行通信時(shí)，必須使用共享信箱，并利用系1)用戶進(jìn)程可為自己建立一個(gè)新信箱，并作為該進(jìn)程的一部分。信箱的擁有者從信單向通信鏈路的信箱來實(shí)現(xiàn)。當(dāng)擁有該信箱的進(jìn)程結(jié)束時(shí)，信箱也隨之。2）公它由操作系統(tǒng)創(chuàng)建，并提供給系統(tǒng)中的所有核準(zhǔn)進(jìn)程使用。核準(zhǔn)進(jìn)程既可把消息發(fā)送到該信箱中，也可從信箱中發(fā)送給自己的消息。顯然，公用信箱應(yīng)采向通信鏈路的信箱來實(shí)現(xiàn)。通常，公用信箱在系統(tǒng)運(yùn)行期間始終存在。3)的名字。信箱的擁有者和共享者，都從信箱中取走發(fā)送給自己的消息。在利用信箱通信時(shí)，在發(fā)送進(jìn)程和接收進(jìn)程之間，存在以下四種關(guān)系一對一關(guān)系。這時(shí)可為發(fā)送進(jìn)程和接收進(jìn)程建立一條兩者的通信鏈路，使多對一關(guān)系。允許提供服務(wù)的進(jìn)程與多個(gè)用戶進(jìn)程之間進(jìn)行交互，也稱為客/服務(wù)器交互(client/serverinteraction)一對多關(guān)系。允許一個(gè)發(fā)送進(jìn)程與多個(gè)接收進(jìn)程進(jìn)行交互，使發(fā)送進(jìn)程可用廣多對多關(guān)系。允許建立一個(gè)公用信箱，讓多個(gè)進(jìn)程都能向信箱中投遞消息；也可管道(Pipe)通信（建立在文件系統(tǒng)上所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名ppe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)，以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX為了協(xié)調(diào)雙方的通信，管道機(jī)制必須提供以下面的協(xié)調(diào)能力：①互斥，即一個(gè)進(jìn)程正在對ppe執(zhí)行讀/(另一)進(jìn)程必須等待。②(輸入)進(jìn)程把一定數(shù)量(如4KB)的數(shù)據(jù)寫入ppe，便去睡眠等待，直到讀(輸出)進(jìn)程取走數(shù)據(jù)后，再把他喚醒。當(dāng)讀進(jìn)程讀一空ppe時(shí)，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將之喚醒。③確定對方是否存在，只有確定了對方已存在時(shí)，才能進(jìn)行通信。線程（CPU系統(tǒng)和網(wǎng)絡(luò)操作系統(tǒng)進(jìn)程：使多個(gè)程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量OS具有更好的并發(fā)性引入線程的目的：進(jìn)程是可擁有資源的獨(dú)立單位和可獨(dú)立調(diào)度和分派的基本單位。創(chuàng)進(jìn)程不應(yīng)同時(shí)作為擁有資源的單位和可獨(dú)立調(diào)度和分派的基本單位，應(yīng)該輕裝上陣線程的屬輕型實(shí)體獨(dú)立調(diào)度和分派的基本單位可并發(fā)執(zhí)行共享進(jìn)程資源三、處理機(jī)調(diào)度與死高級調(diào)度 Scheduling)，又稱作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)，通常不需要作業(yè)調(diào)度)在OS中都必須配置非搶占方式(Non-preemptiveMode) 1在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個(gè)：正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；12執(zhí)行中的進(jìn)程因提出I/O請求而暫停23在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語3Wakeup原語等以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的。顯然，在要求比較嚴(yán)格搶占方式(PreemptiveMode)允許暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分派給另一進(jìn)優(yōu)先權(quán)原則短作業(yè)(進(jìn)程)優(yōu)先原則時(shí)間片原則中級調(diào)度(Intermediate-Level又稱中程調(diào)度(Medium-Term目的：是為了提高內(nèi)存利用率和系統(tǒng)吞吐作用內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。又稱對換調(diào)度隊(duì)列模僅有進(jìn)程調(diào)度的通常，把就緒進(jìn)程組織成FIFO隊(duì)列，每當(dāng)創(chuàng)建新進(jìn)程時(shí)排在就緒隊(duì)列的末尾，按時(shí)間進(jìn)程在執(zhí)行時(shí)，出現(xiàn)三種情況任務(wù)在時(shí)間片內(nèi)完成，進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)任務(wù)在時(shí)間片內(nèi)未完成 便將該任務(wù)再放入就緒隊(duì)列的末尾在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞?，將OS放入阻塞隊(duì)列件就緒隊(duì)列的形式。批處理系統(tǒng)中最常用的是優(yōu)先權(quán)隊(duì)列。也可采用無序鏈表方式列隊(duì)備列隊(duì)備后…………

時(shí)間就緒隊(duì)就緒隊(duì)

列等待事列…等待事……等待事…

進(jìn)程同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模調(diào)出時(shí)，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)變?yōu)橥獯婢途w，由內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞辉谥屑壵{(diào)度室外存就緒轉(zhuǎn)變?yōu)閮?nèi)存就緒。作業(yè)調(diào) 時(shí)間片掛選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)面向用戶的準(zhǔn)周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間的保證優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng)的準(zhǔn)系統(tǒng)吞吐量高處理機(jī)利用率好各類資源的平衡利用進(jìn)程在CPU上執(zhí)行的時(shí)間1 nT Tin 帶權(quán)周轉(zhuǎn)時(shí)間T：作業(yè)的周期時(shí)W 1W n Ti1Si例：有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序是：1/2/3.求平均周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)間作提交時(shí)間/運(yùn)行時(shí)間12213解作提交時(shí)運(yùn)行時(shí)開始時(shí)完成時(shí)周轉(zhuǎn)時(shí)帶權(quán)周轉(zhuǎn)時(shí)1222133平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間響應(yīng)時(shí)間：是從用戶通過鍵盤提交一個(gè)請求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間間隔。它包截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。對于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn)。吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。評價(jià)批處理系統(tǒng)性能的重要指標(biāo)。吐量可達(dá)到數(shù)十道作業(yè)。調(diào)度算法：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法是一種最簡單的調(diào)度算法，既可用于作業(yè)調(diào)度也可用于進(jìn)程調(diào)度有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。（用帶權(quán)周轉(zhuǎn)時(shí)間評價(jià)CPU繁忙型，帶權(quán)周轉(zhuǎn)時(shí)間接近于1，I/O繁忙型作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間遠(yuǎn)遠(yuǎn)大于短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJP)F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。高優(yōu)先權(quán)優(yōu)先調(diào)度算優(yōu)先權(quán)調(diào)度算法的類在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。搶占式優(yōu)先權(quán)調(diào)度算在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。因此，在采用這種iPi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但如果是Pi＞Pj,則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對性能要求較高的批處理和分時(shí)系統(tǒng)中。優(yōu)先權(quán)的類靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0~7或0~255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。優(yōu)缺點(diǎn)：簡單、開銷??；不精確，僅在要求不高的系統(tǒng)中使用。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：進(jìn)程類型用戶要求高響應(yīng)比優(yōu)先調(diào)度算等待時(shí)間由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為優(yōu)先權(quán)等待時(shí)間要求服務(wù)時(shí)間要求服務(wù)

如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。先級便可升到很高，從而也可獲得處理機(jī)。優(yōu)點(diǎn)：兼顧長缺點(diǎn)：由于做相應(yīng)比計(jì)算，增加了系統(tǒng)開銷時(shí)間片輪轉(zhuǎn)CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。（分時(shí)系統(tǒng)）多級反饋隊(duì)列調(diào)度算應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級。第一個(gè)隊(duì)列的優(yōu)先級最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長一倍，……，第i+1個(gè)隊(duì)列的時(shí)間片要比第i當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按CS原則排隊(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ì)列的末尾，再同樣地按CFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，……，如此下去，當(dāng)一個(gè)長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。僅當(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ì)列(第~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)程。多級反饋隊(duì)列調(diào)度算法的性短批處理作業(yè)用戶。其周轉(zhuǎn)時(shí)間短長批處理作業(yè)用戶。不必?fù)?dān)心作業(yè)長期得不到處理提供必要的信就緒時(shí)間開始截止時(shí)間和完成截止時(shí)間處理時(shí)間資源要求系統(tǒng)處理能力在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：mCii1系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50增強(qiáng)其處理能力，以顯著地減少對每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：mCimi 具有快速切換機(jī)該機(jī)制應(yīng)具有如下兩方面的能力對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時(shí)系統(tǒng)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男。詼p少任務(wù)切換的時(shí)間開銷。非搶占式調(diào)度算法算法簡單、用于小型實(shí)時(shí)系統(tǒng)或要求不嚴(yán)的實(shí)時(shí)控制系統(tǒng)非搶占式輪轉(zhuǎn)調(diào)度算法。用于工業(yè)群控系統(tǒng)，一臺計(jì)算機(jī)控制若干個(gè)相同的（或類似的對象，為每個(gè)被控對象建立一個(gè)實(shí)時(shí)任務(wù)，并將它們拍成一個(gè)輪轉(zhuǎn)隊(duì)列。調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)運(yùn)行。完成后，便把他們掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下一次調(diào)度運(yùn)行，這次調(diào)度程序在選擇下一個(gè)（隊(duì)首）任務(wù)執(zhí)行?？色@得數(shù)秒至數(shù)十秒響應(yīng)時(shí)間。非搶占式優(yōu)先調(diào)度算法。針對有一定要求的系統(tǒng)，為實(shí)時(shí)性要求高的任務(wù)賦予較高的優(yōu)先級。優(yōu)先安排在就緒隊(duì)列隊(duì)首，待當(dāng)前任務(wù)結(jié)束后，被調(diào)度執(zhí)行。響應(yīng)時(shí)間為數(shù)秒或數(shù)百毫秒基于時(shí)高優(yōu)先級的實(shí)時(shí)任務(wù)到達(dá)后不立即搶占，等到時(shí)鐘中斷到來時(shí)再重新分配處理機(jī)立即搶占的優(yōu)先權(quán)調(diào)度算法高優(yōu)先級的實(shí)時(shí)任務(wù)到達(dá)后，只要當(dāng)前任務(wù)未處于臨界區(qū)就立即把處理機(jī)分配給他

實(shí)時(shí)進(jìn)程請求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成 常用的幾種實(shí)時(shí)調(diào)度最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算根據(jù)任務(wù)的開始截止時(shí)間確定優(yōu)先級，截止時(shí)間越早優(yōu)先級越系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)優(yōu)先級就緒隊(duì)列，調(diào)度程序選擇對首任務(wù)分配處理機(jī)可采取搶占式和非搶占式調(diào)度 242431t

最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)優(yōu)先級就緒隊(duì)列，調(diào)度程序選擇對首任務(wù)分配處理提高元器件的運(yùn)行速度，特別是處理機(jī)的速改進(jìn)計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)，特別是在系統(tǒng)中引入多個(gè)處理器或多臺計(jì)算機(jī)功能較強(qiáng)的主機(jī)系統(tǒng)和服務(wù)器都采用多處理器系統(tǒng)從多處理機(jī)之間耦合的緊密程度上，可分緊密耦合(TightlyCoupted)MPS通過高速總線或高速交叉開關(guān)，來實(shí)現(xiàn)多個(gè)處理器之間的互連地址總線、控制總線（單向）、數(shù)據(jù)總線它們共享主器系統(tǒng)和I/O設(shè)，并求主器分若干能立的存儲器模塊，以便多個(gè)處理機(jī)能同時(shí)對主存進(jìn)行。系統(tǒng)中的所有資源和進(jìn)程，都由操作系統(tǒng)實(shí)施統(tǒng)一的控制和管理。松散（弛）耦合(LooselyCoupled)MPS通過通道或通信線路，來實(shí)現(xiàn)多臺計(jì)算機(jī)之間的互連。每臺計(jì)算機(jī)都有自己的器I/OOS來管理本地資源和在本地運(yùn)行的進(jìn)程。因此，每一臺計(jì)算機(jī)都能獨(dú)立地工作，必要時(shí)可通過通信線路與其它計(jì)算機(jī)交換信息，以及協(xié)調(diào)它們之間根據(jù)系統(tǒng)中處理器的相同與否可分為MPSSMPS(SymmetricMultiProcessorSystem)。在系統(tǒng)中所包含的各處理器單元，在功能和結(jié)構(gòu)上都是相同的，當(dāng)前的絕大多數(shù)MPS都屬于SMP系統(tǒng)。例如，IBMSR/6000ModelF50,4PowerPC處理器構(gòu)成的MPS非對稱多處理器系統(tǒng)。在系統(tǒng)中有多種類型的處理單元，它們的功進(jìn)程分配方式（針對多處理機(jī)系統(tǒng)非對稱系統(tǒng)中進(jìn)程只能分配到某一合適運(yùn)行的處理器對稱多處理器系統(tǒng)中的進(jìn)程分配方式在MP系統(tǒng)中，所有的處理器都是相同的，因而可把所有的處理器作為一個(gè)處理器池(Pocesorpol)，由調(diào)度程序或基于處理器的請求，將任何一個(gè)進(jìn)程分配給池中的任何一個(gè)處理器去處理。在進(jìn)行進(jìn)程分配時(shí)，可采用以下兩種方式之一。靜態(tài)分配(StaticAssigenment)方特點(diǎn)：進(jìn)程被固定分配到一個(gè)處理器上；與單機(jī)進(jìn)程調(diào)度方式相同。優(yōu)點(diǎn)：開銷小缺點(diǎn)：各處理機(jī)忙閑不均動(dòng)態(tài)分配(DynamicAssgement)方非對稱MPS中的進(jìn)程分配方式每當(dāng)從機(jī)空閑時(shí)，便向主機(jī)發(fā)送一索求進(jìn)程的信號，然后，便等待主機(jī)為它分配進(jìn)程。在主機(jī)中保持有一個(gè)就緒隊(duì)列，只要就緒隊(duì)列不空，主機(jī)便從其隊(duì)首摘下一進(jìn)程分配給請求的從機(jī)。從機(jī)接收到分配的進(jìn)程后便運(yùn)行該進(jìn)程，該進(jìn)程結(jié)束后從機(jī)又優(yōu)點(diǎn)：系統(tǒng)處理簡單，因?yàn)檫M(jìn)程分配由主機(jī)獨(dú)自處理，使進(jìn)程間的同步問題化進(jìn)程(線程)調(diào)度方自調(diào)度(Self-Scheduling)方自調(diào)度機(jī)在多處理器系統(tǒng)中，自調(diào)度方式是最簡單的一種調(diào)度方式。它是直接由單處理機(jī)環(huán)境下的調(diào)度方式演變而來的。在系統(tǒng)中設(shè)置有一個(gè)公共的進(jìn)程或線程就緒隊(duì)列，所有的處理器在空閑時(shí)，都可自己到該隊(duì)列中取得一進(jìn)程(或線程)來運(yùn)行。在自調(diào)度方式中，可采用在單處理機(jī)環(huán)境下所用的調(diào)度算法，如先來先服務(wù)(CFS)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等。自調(diào)度方式的優(yōu)其調(diào)度算法也可沿用單處理機(jī)系統(tǒng)所用的算法，亦即，很容易將單處理機(jī)環(huán)境下的調(diào)度機(jī)制移植到多處理機(jī)系統(tǒng)中，故它仍然是當(dāng)前多處理機(jī)系統(tǒng)中較常用的調(diào)度方式。其次，處理機(jī)的利用率高，只要系統(tǒng)中有任務(wù)，或者說只要公共就緒隊(duì)列不空，就不會(huì)出現(xiàn)處理機(jī)空閑的情況，也不會(huì)發(fā)生處理器忙閑不均的現(xiàn)象，因而有利于提高處理器的利用率。自調(diào)度方式的缺瓶頸問題線程切換頻繁成組調(diào)度(GangScheduling)方面向所有應(yīng)用程序平均分配處理器時(shí)面向所有線程平均分配處理器時(shí)優(yōu)點(diǎn)：減少線程切換，優(yōu)于自調(diào)處理器分配(DedicatedProcessorAssigement)方器，供應(yīng)用程序直至該應(yīng)用程序完成。缺點(diǎn)：造成單個(gè)處理機(jī)的浪引入原因：多處理機(jī)系統(tǒng)中單個(gè)處理機(jī)的利用率不很在一個(gè)應(yīng)用程序的運(yùn)行中完全避免了進(jìn)程或線程的切換，大大加速運(yùn)行死多個(gè)進(jìn)程在運(yùn)行過程中因競爭資源而造成的一種僵局各并發(fā)進(jìn)程彼此等待對方擁有的資源，且在得到對方資源前不釋放自己的資源。產(chǎn)生死鎖的原因競爭資源進(jìn)程間推進(jìn)順序1.競爭資源引起進(jìn)程死可和非性資競爭非性資非資源的數(shù)量不能滿足進(jìn)程運(yùn)行的需要，會(huì)使進(jìn)程在運(yùn)行過程中，因爭奪這些資源而陷入僵局。3競爭臨時(shí)性資源CPU完后自行釋放，如磁帶機(jī)、。競爭臨時(shí)性資

I/O設(shè)備共享時(shí)的死鎖情臨時(shí)性資源：由一個(gè)進(jìn)程產(chǎn)生由另一個(gè)進(jìn)程使用暫短時(shí)間后便無用的資源產(chǎn)生死鎖的必要條件進(jìn)產(chǎn)生死鎖的必要條件（3）不 條請（3）不 條（4）環(huán)路等待條指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源環(huán)形鏈，即進(jìn)程集合{P0、P1、 P0P1占有的資源；P1P2占有的資源，……，Pn正在等待已被P0占用的資源。處理死鎖的基預(yù)防死鎖。用嚴(yán)格的條件限設(shè)置某些限制條件，破壞四個(gè)條件中的一個(gè)或幾個(gè)條件 簡單、較易實(shí)在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)可獲得較高的資源利用率及系統(tǒng)吞吐量實(shí)現(xiàn)上有一定的難度檢測死鎖缺點(diǎn)：資源被嚴(yán)重浪費(fèi)，了系統(tǒng)利用率；是進(jìn)程延遲運(yùn)序號必須相對穩(wěn)定，限制了新設(shè)備類型的增加作業(yè)（進(jìn)程）限制了用戶編程系統(tǒng)安全狀指系統(tǒng)能按某種進(jìn)程順序(P1,P,…，Pn)(稱〈P,P,…,Pn〉序列為安全序列)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。系統(tǒng)進(jìn)入不安全狀態(tài)后可能進(jìn)入死只要系統(tǒng)出于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)可利用資源向量ilale。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代類資源的分配和回收而動(dòng)態(tài)地改變。如果ilale［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。最大需求矩陣Max。這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程m類資源的最大需求。如Max［i,j］=K，則表示進(jìn)i需要Rj類資源的最大數(shù)目為K。分配矩陣Allocation。這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation［i,j］=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。Need［i,j］=K，則表示進(jìn)程iRjK個(gè)，方能完成其任務(wù)。Need［i,j］=Max［i,j］-銀行家算法的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰娜绻鸕equesti［j］≤Available［j］，便轉(zhuǎn)向步驟(3)；否則 表示尚無足夠資源系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available［j］∶=Available［j］-Requesti［j］Allocation(3)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源Pi等待。3.安全性算Work:它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work∶=AvailableFinish:它表示夠資源分配給進(jìn)程時(shí)，再令Finish［i］∶=true。從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程Finish［i］=false;Need［i,j］≤Work［j］；(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)行 gotostepFinish［i］=true假定系統(tǒng)中有五個(gè)進(jìn)程｛P0P1P2P3P4｝和三類資源｛AB,C｝，各種資源的數(shù)量分別10、5、7，在T0時(shí)刻的資源分配情況如圖3-15所示。P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查①Request1(1,0,2)≤Need1(1,2,②Request1(1,0,2)≤Available1(3,3,P1Available,Allocation1Need1向量，由此形成的資源變化情況如圖3-15中的圓括號所示。 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查①Request4(3,3,0)≤Need4(4,3,,P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)①Request0(0,2,0)≤Need0(7,4,②Request0(0,2,0)≤Available(2,3,資源分配圖(ResourceAllocation3-19(2Ee∈EPR中的一個(gè)結(jié)點(diǎn)，e={pirj}是資源請求邊，由進(jìn)程pirj它表示進(jìn)程pi請求一個(gè)單位rj資源。e={rj,pi}是資源分配邊，由資源rjpi,rjpi。(a (b死鎖檢測中的數(shù)據(jù)結(jié)

可利用資源向量Available，它表示了m把不占用資源的進(jìn)程(向量Allocation∶=0)記入L表中，即Li∪LWork∶=Work+AllocationiL表中。化的。因此，該系統(tǒng)狀態(tài)將發(fā)生死鎖。WorkL∶= forallLi LdoforallRequesti≤WorkdoWork∶=Work+Allocationi;deadlock∶ (L={p1,p2,…,死鎖的解(1)資源(2)撤消進(jìn)程為把系統(tǒng)從死鎖狀態(tài)中解脫出來，所花費(fèi)的代價(jià)可表示為SP1(cukSP1(cukP1(cud3-21四、器管程序的裝入和連續(xù)分配方基本分頁管理方基本分段管理方虛擬器的基本概請求分頁管理方頁面置換算請求分 管理方內(nèi)存分（4）內(nèi)存擴(kuò)充——解決“求大于供”的問題，采用虛 （4）內(nèi)存擴(kuò)充——解決“求大于供”的問題，采用虛 技（3）內(nèi)存保護(hù)——檢查地址 ，防止越程序的裝入和從用戶的源程序進(jìn)入系統(tǒng)到相應(yīng)的程序在機(jī)器上運(yùn)行，所經(jīng)歷的主要處理階段有：編譯 編譯程序：將用戶源代碼編譯成若干個(gè)目標(biāo)模塊 程序：將一組目標(biāo)模塊及它們所需要的庫函數(shù)在一起，形成一個(gè)完整的裝入塊裝入程序：將裝入模塊裝入內(nèi)存內(nèi)存空間（或物理空間、絕對空間）由內(nèi)存一系列單元所限定的地址范圍。邏輯地址空間（或地址空間）由程序中邏輯地址組成的地址范圍。相對地址（或邏輯地址用戶程序經(jīng)編譯之后的每個(gè)目標(biāo)模塊都以 為址順序編址這種地址稱為相對地絕對地址（或物理地址）內(nèi)存中各物理單元的地址是從統(tǒng)一的址順序編址，這程序的裝絕對裝入方式(AbsoluteLoading程序中所使用的絕對地址，既可在編譯或匯編時(shí)給出，也可由程序員直接賦予。但在由程序員直接給出絕對地址（邏輯地址與絕對地址相同）時(shí)，不僅要求程序員熟悉內(nèi)存的使用序中采用符號地址，然后在編譯或匯編時(shí)，再將這些符號地址轉(zhuǎn)換為絕對地址?？芍囟ㄎ谎b入方式(RelocationLoading目標(biāo)模塊從0編址，其它地址相對于起始地址計(jì)算0

作業(yè)裝入內(nèi)存時(shí)的情動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DenamleRun-time動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推程序真正要執(zhí)行時(shí)才進(jìn)行。因此，裝入內(nèi)存程序的靜態(tài)方式(StaticLinking)執(zhí)行前將目標(biāo)模塊和他們的庫函數(shù)，連接成一個(gè)完兩個(gè)問題模塊A模塊A0模塊B模塊B模塊模塊

模塊模塊模塊模塊L(a)目標(biāo)模 (b)裝入模裝入時(shí)動(dòng)態(tài) timeDynamic將某些目標(biāo)模塊的，推執(zhí)行時(shí)才進(jìn)行。即在執(zhí)行過程中若發(fā)現(xiàn)一個(gè)被調(diào)用模裝入時(shí)動(dòng)態(tài)方式有以下優(yōu)點(diǎn)便于修改和更新便于實(shí)現(xiàn)對目標(biāo)模塊的共享連續(xù)分配方為一個(gè)用戶程序分配續(xù)的內(nèi)存空間分為：單一連續(xù)分配、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配、動(dòng)態(tài)（可）重定位分區(qū)分OS使用，通常是放在內(nèi)存的低址部序，整個(gè)用戶區(qū)為一用戶獨(dú)占。這種分配方式僅能用于單用戶、單任務(wù)OS中。劃分分區(qū)的方分區(qū)大小不等 可根據(jù)程序大小為它分配適當(dāng)分區(qū)固定分區(qū)使用空閑分區(qū)鏈。在每一個(gè)分區(qū)的起始部分設(shè)置用于控制分區(qū)的信息、向前指針，在分區(qū)尾部設(shè)置一個(gè)后向指針，形成雙向鏈表。00N＋20N＋2分區(qū)分0N＋2首次適應(yīng)算法FF空閑分區(qū)鏈以地址遞增的次序大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑連中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)滿足要求的分區(qū)，則失敗返回。循環(huán)首次適應(yīng)算法，該算法是由首次適應(yīng)算法演變而成的。每一次從上次找到的下一個(gè)分區(qū)開始查找。指導(dǎo)找到一個(gè)能滿足要求的分區(qū)。最佳適應(yīng)算法。將所有的空閑分區(qū)按其容量從小到大的順序形成一個(gè)空閑分區(qū)鏈，不可再切割的剩余分區(qū)大小如果m.size- 將整個(gè)分區(qū)分配給請求者，否則剩余部分留在空閑分區(qū)鏈（表中將分區(qū)的首地址返回給調(diào)用者檢檢索返繼續(xù)檢索下從頭開始查返將返將該分區(qū)從從該分區(qū)中u.size大小的分當(dāng)進(jìn)程釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首值，從空閑區(qū)鏈（表）中找到相應(yīng)的插入點(diǎn)，回收區(qū)可能出現(xiàn)四種情況：同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接 三區(qū)合動(dòng)態(tài)（可）重定位分區(qū)分動(dòng)態(tài)重定位的引碎片：內(nèi)存中不能被利用的小分區(qū)稱為“零頭”或“碎片”分散的小分區(qū)拼接成一個(gè)大分區(qū)的方法，稱為“拼接”或“緊湊用戶程序用戶程序10用戶程序30用戶程序14用戶程序26用戶程序用戶程序用戶程序用戶程序80緊湊 (b)緊湊動(dòng)態(tài)重定位的實(shí)

緊湊的示增設(shè)硬件機(jī)構(gòu)：重定位寄存器0作業(yè)

相對地

重定位

主動(dòng)態(tài)重定位分區(qū)分配對換(Swap)即中級調(diào)把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠內(nèi)存利用率的有效措施。頁面對換對換空間的管即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)。外存包括對換區(qū)為提高對換速度采用連續(xù)分配方式進(jìn)程的換每一進(jìn)程由創(chuàng)建子進(jìn)程需要內(nèi)存空間但又足夠的內(nèi)空間等情況生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進(jìn)程作現(xiàn)錯(cuò)誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并對該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。進(jìn)程的換入系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。離散分配方基本思想：將一個(gè)進(jìn)程分散的裝入不相鄰的分區(qū)分 管理方式離散分配的基本單位是頁，則稱為分 分 管理方式將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁，并為各頁編號，從0開始，如第0頁、第一頁等。把內(nèi)存空間分成與頁面大小相等的若干個(gè)塊，稱為塊或者頁框，也加以編號，0#、1#塊等以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相鄰接的物理塊中頁面大通常512B-頁面太?。喉搩?nèi)碎片小，提高內(nèi)存利用率，但頁表過長，占內(nèi)存；降低對換效率頁面太大：提高了對換速度，但頁內(nèi)碎片大，降低了內(nèi)存利用率地址結(jié)構(gòu)分頁地址中的地址結(jié)構(gòu)如下A，頁面的大L，則頁P(yáng)和頁內(nèi)地d可按下式求得：頁頁面系統(tǒng)為了能在內(nèi)存中找到每個(gè)頁面對應(yīng)的物理塊而為進(jìn)程建立的一張頁面映像表，簡稱頁表。頁表作用：實(shí)現(xiàn)從頁號到物理塊號的地址映只地址變換機(jī)地址變換任務(wù)頁表由一組專門的寄存器來實(shí)現(xiàn)，一個(gè)頁表項(xiàng)用一個(gè)寄存器頁表大多數(shù)駐留在內(nèi)存中系統(tǒng)中只設(shè)置一個(gè)頁表寄存 PTR，存放頁表在內(nèi)存的始值和頁表的長度PCB中。當(dāng)調(diào)度到進(jìn)程時(shí)裝入分頁系統(tǒng)的地址變換塊號與頁內(nèi)偏移量W拼接成物理地址第二次內(nèi)存時(shí)從所得地址中獲得所需數(shù)據(jù)（或向此地址中寫入數(shù)據(jù)）為提高地址變換速度：增設(shè)了一個(gè)具有并行查詢能力的高速緩沖寄存器，稱為“聯(lián)想寄存器”或“快表”，用于存放當(dāng)前的頁表項(xiàng)。 頁＋頁號塊b輸b bd快表通常只放16- 個(gè)頁表項(xiàng)，大型作業(yè)表只能將其一部分頁表項(xiàng)放入其中，從塊能找到所需頁表項(xiàng)中率可達(dá)兩級和多級頁現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對于一個(gè)具有32位邏輯址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB即212B，則在每個(gè)進(jìn)程頁表中的頁表14KB的內(nèi)存空間，而且還要求是連續(xù)的?？梢圆捎眠@樣兩個(gè)方法來解決這一問題：①采用離表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。邏輯地址結(jié)構(gòu)可描述如下 2

……012

第0……第1……第n…兩級頁表結(jié)…

…………234567外部頁 外部頁內(nèi)地 dd…………外部頁 頁具有兩級頁表的地址變換機(jī)基本分段管理方引入分段管理方式 主要是為了滿足用戶和程序員的下述一系列需要?jiǎng)討B(tài)段段 段 基 000

作業(yè)

內(nèi)存

0利用段表實(shí)現(xiàn)地址映控制寄存器

483段表長度段表始址

有效地址物理地址主分段系統(tǒng)的地址變換分頁和分段的主要區(qū)內(nèi)存的利用率?；蛘哒f，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址；而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址?？芍厝氪a：又稱純代碼：一種允許多個(gè)進(jìn)程同時(shí)但不允許任何進(jìn)程對它進(jìn)行修改的代碼?！黜擁摗雾撌焦芾矸剑?）硬件支持請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；②缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要的頁面尚未調(diào)入內(nèi)存OS將所缺的頁調(diào)入內(nèi)存；③地址變換機(jī)構(gòu)，它同樣(2)虛虛 器的特多次 請求分頁管理方請求分頁中的硬件支頁物理塊狀態(tài)位字段A修改位外存地缺頁中斷機(jī)與一般中斷的在指令執(zhí)行期間產(chǎn)生和處理中斷信號最小物理塊能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)，與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)。取決于指令的格式、功能和尋址方式。物理塊的分配策固定分配局部置為每一個(gè)進(jìn)程分配一個(gè)固定頁數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行過程中都不改變。如果缺頁，則只能從該進(jìn)程的頁面中選擇一頁換出，再調(diào)入一頁。：應(yīng)為每個(gè)進(jìn)程分配多少個(gè)頁的內(nèi)存難以確定，若太少會(huì)頻繁地出現(xiàn)缺頁中斷降低吞吐量；太多，又使內(nèi)存中進(jìn)程數(shù)減少，進(jìn)而可能造成CPU或其他資源空閑，而且進(jìn)程對換會(huì)花分費(fèi)的時(shí)間?？勺兎峙淙种孟葹槊總€(gè)進(jìn)程分配一定數(shù)目的物理塊。OS保持一個(gè)空閑物理塊隊(duì)列當(dāng)空閑物理塊隊(duì)列為空時(shí)從內(nèi)存中選擇一頁調(diào)出可變分配局部置基于進(jìn)程的類型或程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的物理塊。缺頁時(shí)從該進(jìn)程中的頁面中選擇一頁換出。如果進(jìn)程頻繁地發(fā)生缺頁中斷，則在為該進(jìn)程分配附加的物理塊。若一個(gè)進(jìn)程的缺頁率特別低，則可適當(dāng)減少該進(jìn)程的物理塊。調(diào)頁策預(yù)調(diào)頁策略主要應(yīng)用于首次調(diào)請求調(diào)頁策從何處調(diào)入頁面（對換區(qū)都在外存I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：系統(tǒng)擁有足夠的對換區(qū)空間，這時(shí)可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。系統(tǒng)缺少足夠的對換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而IX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文應(yīng)從對換區(qū)調(diào)入。由于UIX系統(tǒng)允許頁面共享，因此，某進(jìn)程所請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再從對換區(qū)調(diào)入。頁面調(diào)入過每當(dāng)程序所要的頁面未在內(nèi)存時(shí)，便向 發(fā)出一缺頁中斷，中斷處理程序首保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為“1。缺頁入存后利修改的表，去形成所要數(shù)據(jù)的物理地址，再去內(nèi)存數(shù)據(jù)。頁面置換算法（選擇換出頁面的算法抖動(dòng)導(dǎo)致進(jìn)程在運(yùn)行中，把大部分時(shí)間花費(fèi)在頁面置換上最佳(Optimal)最佳置換算法是由Belady于1966年一種理論上的算法其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時(shí)間內(nèi)不再被訪可利用該算法評價(jià)其他算法假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊 并考慮有以下的頁面號串進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁面裝入內(nèi)存。以后，當(dāng)進(jìn)程要頁面率 0120324320120324320320頁框(物理塊先進(jìn)先出(FIFO)頁面置換算率 頁

01 231230430420423001231230430420423023070最近最久未使用(LRU)根據(jù)頁面調(diào)入內(nèi)存后的使用情 最近的過去近似最近的將率 頁

03 4034024320303403402432032132102107每頁設(shè)置一位位。再將內(nèi)存中的所有頁面都通過指針鏈成一個(gè)循環(huán)隊(duì)列當(dāng)某也被時(shí)，其位置1.淘汰時(shí)檢查其位，如果是0則換出；若是1則重新將它復(fù)0.再按FIFO算法檢查下個(gè)頁面。到隊(duì)列中的最后一個(gè)頁面時(shí)，若其位仍為1，則又稱為最近未用算法由位A和修改位M可以組合成下面四種類型的頁面類(A=0,M=1)：表示該頁最近未被，但已被修改，并不是很好的淘汰頁類(A=1,M=1):最近已被且被修改，該頁可能再被。A=0M=0的第一類頁面，將所遇到的第一個(gè)頁面作為所選中的淘汰頁。在第一次掃描期間不改變位A。如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的位都置0。如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁。其它置換算1）最少使用(LFULeastFrequentlyUsed)置換算法2）頁面緩沖算法(PBA：PageBufferingAlgorithm)如果頁面未被修改，就把它直接放入空閑鏈表；否則，放入以修改頁面的鏈表中。頁面在內(nèi)存并不做物理移動(dòng)而只是將頁表中的表項(xiàng)移到鏈表之中字A修改M存在P存取方式 表示本段的屬性：只讀、只執(zhí)行、允許讀/字段A 頻修改 M。用于表示該也在進(jìn)入內(nèi)存后是否被修改過，供置換頁面時(shí)參考存在 P。指示本段是否已調(diào)入內(nèi)存，供程 時(shí)參增補(bǔ)位 特有的字段，用于本段在運(yùn)行過程中，是否做過動(dòng)態(tài)增外存始址 本段在外存中的起始地址，即起始盤塊缺段中斷機(jī)回回地址變換機(jī) 請求分段系統(tǒng)的地址變換過w段長段S在主存是 分段的共享與?！巍味蝺?nèi)存始狀外存始共享狀進(jìn)程進(jìn)程段存取控……………共享段存取控制字段。對于一個(gè)共享段，應(yīng)給不同的進(jìn)程以下不同的存取權(quán)限段號。對于一個(gè)共享段，不同的進(jìn)程可以各用不同的段號去共享該段共享段的分在為共享段分配內(nèi)存時(shí)，對第一個(gè)請求使用該共享段的進(jìn)程，由系統(tǒng)為該共享段分配一物段表中增加一表項(xiàng)，填寫有關(guān)數(shù)據(jù)，把cont置為1段時(shí)，由于該共享段已被調(diào)入內(nèi)存，故此時(shí)無須再為該段分配內(nèi)存，而只需在調(diào)用進(jìn)程的段表中，增加一表項(xiàng)，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進(jìn)程的進(jìn)程名、存取控制等，再執(zhí)行cout∶=cout+1操作，以表明有兩個(gè)進(jìn)程共享該段。共享段的回所對應(yīng)的表項(xiàng)，以及執(zhí)行count∶=count-10，則須由系統(tǒng)回收該共享段否則(減1結(jié)果不為0)，則只是取消調(diào)用者進(jìn)程在共享段表中的有關(guān)記錄。檢查段內(nèi)地址是否大于等于段長存取控制檢只讀/一個(gè)程序可以駐留在相同環(huán)或較低環(huán)中的數(shù)據(jù)。一個(gè)程序可以調(diào)用駐留在相同環(huán)或較高環(huán)中的服務(wù)環(huán)環(huán)環(huán)環(huán)環(huán)環(huán)環(huán) 五、設(shè)備管設(shè)備分虛擬設(shè)實(shí)現(xiàn)設(shè)備獨(dú)立 系實(shí)現(xiàn)信息輸入、輸出和的系統(tǒng)。包括I/O通道I/O處理機(jī)按傳輸速率分按傳輸速度的高低，可將I/O設(shè)備分為三類第一類是低速設(shè)備，這是指其傳輸速率僅為每秒鐘幾個(gè)字節(jié)至數(shù)百個(gè)字節(jié)的一類設(shè)備。屬于低速設(shè)備的典型設(shè)備有鍵盤、鼠標(biāo)器、語音的輸入和輸出等設(shè)備。第二類是中速設(shè)備，這是指其傳輸速率在每秒鐘數(shù)千個(gè)字節(jié)至數(shù)萬個(gè)字節(jié)的一類設(shè)備。典型的中速設(shè)備有行式、激光等。第三類是高速設(shè)備，這是指其傳輸速率在數(shù)百千個(gè)字節(jié)至數(shù)十兆字節(jié)的一類設(shè)備。典型的高速設(shè)備有磁帶機(jī)、磁盤機(jī)、光盤機(jī)等。第一類是塊設(shè)備(BlockDevice)，這類設(shè)備用于信息。由于信息的存取總是以數(shù)據(jù)塊為單位，故而得名。它屬于有結(jié)構(gòu)設(shè)備512B~4KB。磁盤設(shè)備的基本特征是其傳輸速率較高，通常每秒鐘為幾兆位；另一特征是可尋址，即對它可隨機(jī)地讀/I/O常采用DMA（直接存?。┓绞?。第二類是字符設(shè)備(CharacterDevice)，用于數(shù)據(jù)的輸入和輸出稱為字符設(shè)備?；咎卣魇莻鬏斝实秃筒豢蓪ぶ贰］斎胼敵鰰r(shí)常采用中斷驅(qū)動(dòng)方式。按設(shè)備的共享屬性分這種分類方式可將I/O設(shè)備分為如下三類獨(dú)占設(shè)備 在一段時(shí)間內(nèi)只允許一個(gè)用戶（進(jìn)程）設(shè)備。如共享設(shè)備 在一段時(shí)間只允許多個(gè)用戶（進(jìn)程）設(shè)備。如：磁虛擬設(shè)備設(shè)備與控制器之間的控制

I/O設(shè)沖狀態(tài)信沖狀態(tài)信號數(shù)據(jù)信號。對輸入是由設(shè)備發(fā)