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

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

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

時間就緒隊就緒隊

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

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

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

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

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

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

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

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

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

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

相對地

重定位

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

……012

第0……第1……第n…兩級頁表結…

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

作業(yè)

內(nèi)存

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

483段表長度段表始址

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

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

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

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