電腦操作系統(tǒng)知識

電腦操作系統(tǒng)知識2/195本章主要內(nèi)容1

概述2

存儲管理3

處理器管理4

設(shè)備管理5

文件管理6

操作系統(tǒng)的用戶接口33.1.1什么是操作系統(tǒng)？操作系統(tǒng)是一種復雜的系統(tǒng)軟件，它是用戶和計算機之間的接口。從計算機系統(tǒng)管理方面看，引入操作系統(tǒng)是為了合理組織計算機工作流程，使計算機中的軟硬件資源能為多個用戶共享，最大限度的發(fā)揮計算機的使用效率。從計算機用戶角度看，操作系統(tǒng)為用戶提供一個良好的工作環(huán)境，以便使用戶程序的開發(fā)、調(diào)試、運行更方便、靈活，從而提高工作效率。●操作系統(tǒng)是控制和管理計算機硬件和軟件資源，合理的組織計算機工作流程以及方便用戶的程序的集合。4/195

操作系統(tǒng)的定義

操作系統(tǒng)定義？一組控制和管理計算機軟、硬件資源，為用戶提供便捷使用計算機的程序的集合

作用管理計算機和使用計算機特征并發(fā)性、共享性、虛擬性和不確定性5/195操作系統(tǒng)的功能CPU與進程管理對處理器的時間進行合理分配、對處理器的運行實施有效的管理存儲器管理對存儲器進行分配、保護和擴充設(shè)備管理根據(jù)確定的設(shè)備分配原則對設(shè)備進行分配，使設(shè)備與主機能夠并行工作，為用戶提供良好的設(shè)備使用界面文件管理有效地管理文件的存儲空間，合理地組織和管理文件系統(tǒng)，為文件訪問和文件保護提供更有效的方法及手段用戶接口用戶操作計算機的界面,或稱為用戶界面，通過用戶接口，用戶只需進行簡單操作，就能實現(xiàn)復雜的應(yīng)用處理操作系統(tǒng)包含哪5大功能模塊？6/195

手工操作階段單道批處理階段執(zhí)行系統(tǒng)階段多道程序系統(tǒng)手工操作階段：程序的讀入、編譯、裝配和執(zhí)行都由操作人員人工控制。速度慢、效率低。單道批處理階段：早期批量處理：操作員事先把用戶提交的作業(yè)組合成一批作業(yè)，利用常駐在內(nèi)存中的監(jiān)督程序，把這批作業(yè)順序輸入磁帶中，然后逐個調(diào)入內(nèi)存中運行并輸出結(jié)果。雖然這種方式提高了系統(tǒng)的處理能力，但作業(yè)的輸入輸出和CPU的計算仍然串行的。脫機批量處理3.1.1操作系統(tǒng)的發(fā)展過程7/195

脫機批量處理—減少了人工干預的時間

為解決快速的主機與慢速的外設(shè)之間的矛盾，采用脫機技術(shù)。這種方式是用一臺價格較低、能力較弱的計算機，稱為“衛(wèi)星機”，將卡片或紙帶上的程序轉(zhuǎn)儲到磁帶上，再送到主機上執(zhí)行，同時將結(jié)果輸出到磁帶上，再由衛(wèi)星機將結(jié)果送到打印機或穿孔機上。其工作示意圖如下：衛(wèi)星機打印機卡片機主機輸出磁帶輸入磁帶脫機批處理系統(tǒng)8/1953.執(zhí)行系統(tǒng)階段由于脫機技術(shù)是用磁帶進行I/O操作，而磁帶是串行介質(zhì)，其作業(yè)按順序運行，每個作業(yè)獨占機器資源，只有當采用通道和中斷技術(shù)，才實現(xiàn)I/O與處理機并發(fā)運行。通道是一種硬件，它控制一臺或幾臺外設(shè)，使外設(shè)和內(nèi)存之間直接進行數(shù)據(jù)傳輸，而與CPU無關(guān)。中斷技術(shù)使系統(tǒng)能暫時中止正在運行的程序，轉(zhuǎn)向中斷處理程序，而被終止的程序在一定條件下又能重新恢復運行。各種中斷程序及負責輸入輸出的控制程序統(tǒng)稱為執(zhí)行系統(tǒng)。執(zhí)行系統(tǒng)控制和指揮其它系統(tǒng)程序和應(yīng)用程序，常駐內(nèi)存。9/1954.多道程序系統(tǒng)執(zhí)行系統(tǒng)中，雖然實現(xiàn)了I/O與處理機并發(fā)運行，但作業(yè)不論大小，CPU一次只能執(zhí)行一個作業(yè)，仍然不能充分利用計算機資源。因此該系統(tǒng)又稱為單一流批處理監(jiān)控系統(tǒng)。多道程序是指在一臺機器上同時運行若干道程序。系統(tǒng)按照各個程序在各個時刻對資源的需求，在這些程序間分配時間，如果分配得當，可以得到資源的最佳利用，這類系統(tǒng)稱為多流批處理監(jiān)控系統(tǒng)。103.1.3操作系統(tǒng)的基本類型多道批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)、通用操作系統(tǒng)多道批處理操作系統(tǒng)：“多道”指內(nèi)存中可存放多道作業(yè)；“批處理”指用戶與作業(yè)之間沒有交互作用，用戶不能直接控制作業(yè)的運行。此系統(tǒng)中，作業(yè)被調(diào)入系統(tǒng)，先存放在外存緩沖區(qū)中，形成一個作業(yè)隊列，系統(tǒng)按照一定的調(diào)度原則或根據(jù)作業(yè)的優(yōu)先程度從作業(yè)中調(diào)出一個或多個作業(yè)進入內(nèi)存運行。作業(yè)運行完畢，由用戶索取運行結(jié)果。此系統(tǒng)適用于大型計算機系統(tǒng)中，為了充分利用中央處理機及各種設(shè)備資源，要求對資源的分配及作業(yè)的調(diào)度有精心的設(shè)計，有較強的管理功能。11/195分時系統(tǒng)：多個用戶分享同一臺計算機，將CPU在時間上分割成很小的時間段，稱為時間片，系統(tǒng)將CPU的時間片輪流分配給多個用戶，每個用戶通過自己的終端直接控制程序的運行，進行人機交互。由于時間片分割很小，使每個用戶感覺自己獨占計算機一樣。

12/195實時系統(tǒng)：包括實時過程控制和實時信息處理兩種。實時操作系統(tǒng)能對外部發(fā)生的隨機事件作出及時響應(yīng)，并對它進行及時處理。適用于工業(yè)控制系統(tǒng)或事務(wù)處理系統(tǒng)。實時系統(tǒng)有較強的中斷處理機構(gòu)，可靠性要求比較高。4.前三種操作系統(tǒng)經(jīng)常組合起來使用，形成通用操作系統(tǒng)。13操作系統(tǒng)的功能(5個)處理器管理：解決CPU的分配策略、實施方法，最大限度地提高處理機的處理能力。存儲管理：解決多道程序在內(nèi)存中的分配，當進程被撤消時回收分配出去的內(nèi)存，通過對內(nèi)外存聯(lián)合管理來擴大存儲空間。設(shè)備管理：對設(shè)備進行分配、調(diào)度，為用戶使用I/O設(shè)備提供方便的命令和操作界面。3.1.4操作系統(tǒng)的功能和特性14文件管理：又稱文件系統(tǒng)，文件是計算機中的軟件資源，存儲在外存中。文件管理可實現(xiàn)對文件的檢索、存取、共享、安全和保密等操作，并提供相應(yīng)的操作命令。用戶接口：提供三種用戶接口，以便用戶提出請求和說明服務(wù)。程序一級的接口、作業(yè)控制語言（操作命令）和圖形接口。15/1952.操作系統(tǒng)的特性并發(fā)性：可同時運行多道程序，操作系統(tǒng)需解決各活動之間的切換，控制各活動之間的影響及同步操作等問題。共享性：多道程序可共享CPU、主存及外設(shè)，多用戶可共享同一程序副本、同一數(shù)據(jù)庫等資源和信息。虛擬性：把物理上的一個實體變成邏輯上的多個對應(yīng)物。

異步性：是指內(nèi)存中的多個進程均按照各自獨立的、不可預知的速度向前推進。在多道程序環(huán)境下，盡管允許多個進程并發(fā)執(zhí)行，但由于資源等因素的限制，進程通常不能一直不停地執(zhí)行，而是以走走停停的方式運行的。內(nèi)存中的每個進程何時執(zhí)行，何時暫停，需要多少時間才能完成等，都是不可預知的。進程是以異步方式運行的。

16/1953.2存儲管理3.2.1

存儲管理的功能及有關(guān)概念3.2.2

實存儲管理3.2.3

虛擬存儲管理173.2.1存儲管理的功能及有關(guān)概念主存儲器又稱內(nèi)存，是計算機中最重要的資源，用戶的程序和數(shù)據(jù)在運行時都要放在內(nèi)存中，再由CPU訪問。內(nèi)存的容量是有限的，因此如何對內(nèi)存進行管理和有效使用是操作系統(tǒng)最重要的內(nèi)容。存儲管理分為兩大類：實存儲管理和虛擬存儲管理。18/1951、存儲器的分級結(jié)構(gòu)高速緩沖存儲器（cache）：又稱緩存，速度快、容量小、價格貴，用來存放使用最頻繁的信息，以及緩沖CPU與內(nèi)存之間的速度差。主存儲器：又稱內(nèi)存，是程序運行時存放系統(tǒng)和用戶的指令及數(shù)據(jù)的設(shè)備。外部存儲器：又稱外存，如硬盤、磁盤、光盤等；存取速度慢、容量大、價格便宜；可以存放大量的系統(tǒng)和用戶的程序及數(shù)據(jù)；不能由CPU直接讀取。19/195分級存儲機構(gòu)示意圖高速緩存外存主存程序和數(shù)據(jù)可以直接被CPU訪問程序和數(shù)據(jù)必須交換到內(nèi)存后才能被CPU訪問分級存儲202、存儲管理功能內(nèi)存分配：內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩大部分。由于多道程序出現(xiàn)，內(nèi)存中需要存放多個用戶作業(yè)，因此內(nèi)存分配要解決如何合理分配內(nèi)存空間以保證各作業(yè)互不沖突，而且系統(tǒng)要提供適當?shù)膬?nèi)存分配算法，提高內(nèi)存的利用率和運行效率。存儲管理的功能主要分為內(nèi)存分配、地址轉(zhuǎn)換、存儲保護和內(nèi)存擴充四部分。21/1952）地址轉(zhuǎn)換或重定位地址空間和存儲空間

地址空間：編程人員采用相對地址來編程，其源程序存放的空間稱為名空間；經(jīng)匯編或編譯后其目標程序占有的地址范圍稱為地址空間；這些地址編號是相對于起始地址而定的，稱為邏輯地址或相對地址。

存儲空間：存儲空間是目標程序裝入內(nèi)存后占用的一系列物理單元的集合，這些單元編號稱為物理地址或絕對地址。00源程序目標程序內(nèi)存地址空間名空間存儲空間x640kB(c)(b)(a)22重定位：當用戶程序調(diào)入內(nèi)存時，需把相對地址轉(zhuǎn)換為絕對地址，同時要對程序中與地址相關(guān)的指令進行修改，這一過程稱為重定位。重定位的方式有靜態(tài)重定位和動態(tài)重定位兩種。

靜態(tài)重定位：把作業(yè)在裝入時就進行的地址轉(zhuǎn)換方式。2）地址轉(zhuǎn)換或重定位：x’=x+D

物理地址邏輯地址下界地址—內(nèi)存中的起始地址

動態(tài)重定位：在程序執(zhí)行過程中進行，當CPU訪問內(nèi)存指令時由動態(tài)變換機構(gòu)自動進行地址轉(zhuǎn)換。23/195

3)存儲保護：

為了保護存儲區(qū)內(nèi)各類程序和信息不受某些錯誤程序的破壞和干擾，須采取保護措施。在靜態(tài)重定位系統(tǒng)中，可用界地址寄存器來判斷當前進入內(nèi)存的程序是否在規(guī)定的上下界內(nèi)，即D≤x’

＜L，如果出現(xiàn)x’

不滿足上述條件，則系統(tǒng)立即發(fā)出越界錯誤，發(fā)出中斷，停止當前執(zhí)行的程序，轉(zhuǎn)去執(zhí)行錯誤處理程序。關(guān)于動態(tài)重定位系統(tǒng)的存儲保護將結(jié)合有關(guān)的存儲方式來討論24/1954)內(nèi)存擴充：

當作業(yè)的地址空間大于分配到的存儲空間時需采取內(nèi)存擴充技術(shù)，將內(nèi)外存聯(lián)合起來擴大存儲空間，常采用的內(nèi)存擴充技術(shù)有覆蓋、交換和虛擬存儲技術(shù)。25/1953.2.2實存儲管理分區(qū)分配可重定位分區(qū)分配覆蓋技術(shù)交換技術(shù)實存儲管理的特點是當作業(yè)要求調(diào)入內(nèi)存時，存儲管理要提供一個不小于作業(yè)地址空間的連續(xù)存儲空間，當空間不夠時，常采用覆蓋或交換技術(shù)來擴充內(nèi)存。幾種常用的實存儲管理方法：26/1951、分區(qū)分配將內(nèi)存劃分為若干個分區(qū)，每個分區(qū)分配給一個作業(yè)，用靜態(tài)重定位方式進行地址轉(zhuǎn)換，提供必要的保護手段，保證各作業(yè)互不干擾。在分區(qū)的劃分方式上有固定分區(qū)和可變分區(qū)兩種。固定分區(qū)分配：存儲器事先被劃分為若干個大小不等的分區(qū)，系統(tǒng)為每個分區(qū)設(shè)置一個目錄，說明該分區(qū)的大小、起始位置、分配狀況等信息，所有分區(qū)目錄構(gòu)成一個內(nèi)存狀態(tài)表；用戶為每個作業(yè)規(guī)定所需的最大存儲量，存儲管理程序負責找出一個足夠大的分區(qū)分配給此作業(yè)。27/1951）固定分區(qū)分配特點：分區(qū)大小固定，狀態(tài)表的結(jié)構(gòu)可以是順序表也可以是鏈表；實現(xiàn)了多個作業(yè)共享內(nèi)存；分區(qū)的分配和回收算法簡單；缺點是內(nèi)存利用不充足，有“碎片”，即作業(yè)所需空間和分區(qū)大小不一定恰好相等。28區(qū)號容量起始位置狀態(tài)18kB312kB已分配232kB320kB已分配332kB352kB未用4120kB384kB未用5520kB504kB已分配OS8kB32kB32kB120kB520kB312kB320kB352kB384kB504kB1024kB內(nèi)存內(nèi)存狀態(tài)表29/1952）可變分區(qū)分配：又稱動態(tài)存儲管理，只有當作業(yè)調(diào)入內(nèi)存時，才按作業(yè)大小建立分區(qū)，當作業(yè)執(zhí)行完后又釋放此空間。采用鏈結(jié)構(gòu)來構(gòu)造分區(qū)目錄。下面從空間的分配和回收來進行討論?？臻g分配：由于多作業(yè)調(diào)入內(nèi)存運行，有些作業(yè)運行結(jié)束后釋放所占空間，內(nèi)存區(qū)呈現(xiàn)占用塊與空閑塊交叉存在的狀態(tài)，如圖3.8所示。在每塊開始與結(jié)束的幾個字節(jié)中存放有關(guān)本塊狀態(tài)的信息，稱為控制信息區(qū)，并把所有的空閑塊鏈成一個雙向鏈表，如圖3.9所示。其中,Llink和Rlink為鏈表左右指針，tag=0表示空閑塊，tag=1表示占用塊，size是本塊的大小，Uplink為本塊的起始地址。2）可變分區(qū)分配30/195

可變分區(qū)分配P1P3P4P6P8圖3.8LlinktagsizeRlinktagUplink圖3.9控制信息區(qū)占用塊空閑塊31/195空間分配例題設(shè)某系統(tǒng)用戶區(qū)大小為5000字節(jié)，地址為1～5000，初始狀態(tài)如下圖a所示，依次分配給5個作業(yè)P1～P5,作業(yè)占用區(qū)大小分別為1000，300，600，900，700。P0為余下的空閑塊，各占用塊和空閑塊情況如下頁圖b和c所示。P1P2P3P4P5P01000

3006009007001500圖a32占用塊、空閑塊表示圖11000P1111300P211600P311700P511900P41100113012801190101500P00圖b—占用塊圖c—空閑塊av350133/195空間回收空間回收：當作業(yè)執(zhí)行完畢后，系統(tǒng)將空間收回，插入到空閑塊鏈表中，但插入時還要判斷左右相鄰塊是否空閑，若是則合并成一個較大的空間,它可通過每一塊中頭尾的控制信息區(qū)的tag標志來判斷。設(shè)當前回收塊起始地址為p,大小為n,則應(yīng)判斷它左鄰居p-1和右鄰居p+n的tag是否為0，若不為0則將當前回收塊插入到空閑塊鏈表中。若出現(xiàn)有tag為0的相鄰塊，則應(yīng)修改原空閑塊的大小，將本回收塊和相鄰塊合并。如下圖。左鄰居右鄰居P-1PP+nn34/195空間回收空間回收例題 在空間分配例題中，當作業(yè)P4完成后，應(yīng)回收P4分區(qū)到空閑塊鏈表中，見圖a；當P5作業(yè)完成后，回收使由于其左右鄰居均為空閑塊，因此應(yīng)進行合并，見圖b所示。

35空間回收過程圖01500P000900P403501190103100P0+P4+P50圖a圖bav1901P1P2P3P4P5P0P4釋放avP1P2P3P4P5P0P5釋放36/195空閑區(qū)分配算法

3）空閑區(qū)分配算法：由于空閑鏈表中各空閑塊的大小不同，在分配是由一個如何分配的問題。通常有三種分配策略。首次適應(yīng)法:將找到的第一個大小不小于所需大小n的空閑塊，將其一部分分配給用戶。最佳適應(yīng)法：將空閑塊鏈表中一個不小于n而最接近n的空閑塊的一部分分配給用戶。最差適應(yīng)法：將空閑塊鏈表中不小于n且是鏈表中最大空閑塊的一部分分配給用戶。37/195空閑區(qū)分配算法

總結(jié)：最佳適應(yīng)法適用于請求分配內(nèi)存大小范圍較廣的系統(tǒng)；最差適應(yīng)算法每次都從內(nèi)存中取最大的結(jié)點進行分配，從而使鏈表中結(jié)點大小趨于均勻，適用于請求分配內(nèi)存較均勻的系統(tǒng)；首次適應(yīng)法通常適用于實現(xiàn)不能掌握運行時可能出現(xiàn)的分配情況。

從時間上比較，首次適應(yīng)法分配時需查詢空閑塊鏈表，但回收時只要插入到表頭即可；最差適應(yīng)算法分配時不需查詢鏈表，而回收時要將剩余部分插入鏈表適當位置；最佳適應(yīng)法無論分配和回收，均需查找鏈表，最費時間。38/1952、可重定位分區(qū)分配碎片問題和存儲區(qū)的緊縮：在可變分區(qū)分配中，內(nèi)存區(qū)由于各作業(yè)的多次請求和釋放出現(xiàn)大量的碎片，浪費了大量的內(nèi)存空間。為了把分散的碎片集中起來成為一個大分區(qū)，需移動各用戶程序，使它們集中在主存的一端，稱為存儲器的“緊縮”。程序浮動和重定位：將主存中用戶程序進行移動稱為程序浮動；程序浮動需對程序中所有與地址有關(guān)的項重新進行定位，此工作是在程序運行過程中進行的，也就是在CPU每次訪問內(nèi)存單元前進行的，又稱動態(tài)重定位。39/195★動態(tài)重定位實現(xiàn)過程：◆先將用戶作業(yè)的目標程序原封不動的裝入主存某一分區(qū)，即用戶程序中與地址有關(guān)的各項均保持原來的相對地址，例如下頁圖b中Load1,1000指令（1000為相對地址）?！舢斣撚脩舫绦虮徽{(diào)度到處理器上執(zhí)行時，操作系統(tǒng)自動將該用戶作業(yè)區(qū)的起始地址（圖b中的10023）減去用戶目標程序的相對起始地址（圖a為0），然后將減得的值裝入定位寄存器中。◆當處理器要訪問主存時，操作系統(tǒng)將程序中的相對地址與定位寄存器中的內(nèi)容相加，得到主存的絕對地址去訪問數(shù)據(jù)，如圖b中絕對地址為11023。40/195：：Load1,1000：：0289：：Load1,1000：：02890010010000100100231012311023定位寄存器10023地址空間（a)存儲空間(b)動態(tài)重定位加法器41/195

動態(tài)重定位時程序在內(nèi)存中任意浮動而不影響其正確的執(zhí)行，容易進行存儲器緊縮；但需硬件支持，包括定位寄存器、加法器等。存儲器緊縮的兩種解決方法：

1）在某個分區(qū)釋放后立即緊縮，這樣系統(tǒng)中始終存在一個連續(xù)的自由分區(qū)而無碎片。這對于分區(qū)的分配管理十分容易，但緊縮工作進行頻繁，花費時間較多。

2）在請求分配分區(qū)找不到足夠大的自由分區(qū)時再進行緊縮。這樣緊縮的次數(shù)大大減少，但分配管理較復雜。42/1953、覆蓋技術(shù)當用戶作業(yè)的地址空間大于主存可用空間時，各作業(yè)就無法運行。為了能在較小的空間中運行較大的作業(yè)，許多機器采用了覆蓋技術(shù)。要進行覆蓋的作業(yè)必須滿足樹狀的模塊結(jié)構(gòu)，如圖a所示，其中根部為常駐內(nèi)存部分，稱為根段，其余部分均為覆蓋部分，同層模塊為一個覆蓋段，在同一時間只有其中一個模塊被調(diào)用，因此它們可以共享一個內(nèi)存空間，其大小按本覆蓋段中最大的模塊分配。如圖b所示。43/195覆蓋技術(shù)示意圖A(20kb)B(50kb)C(20kb)F(30kb)E(40kb)D(20kb)根部樹枝樹葉F71kb110kbA020kbB21kb70kbCDE圖a圖bB和C可以互相覆蓋F和D,E可以互相覆蓋不用覆蓋時需要180kb用覆蓋時需要110kb44/1954、交換技術(shù)

交換技術(shù)同樣是為了解決內(nèi)存不足的矛盾，它在分時、實時及批處理系統(tǒng)中均有應(yīng)用。它的基本思想是只允許一個或幾個用戶作業(yè)保留在主存中。

覆蓋和交換技術(shù)作為擴充內(nèi)存的方法，通常與分區(qū)分配方法結(jié)合使用。但仍存在不足，例如覆蓋技術(shù)要求用戶按模塊化結(jié)構(gòu)編制程序，并要寫出覆蓋文件；交換技術(shù)是以整個作業(yè)為單位進行內(nèi)外存交換，當作業(yè)較大時花費的代價較大。由此引發(fā)了虛擬存儲技術(shù)的出現(xiàn)。45/1953.2.3虛擬存儲管理

在前述的各種分區(qū)管理技術(shù)中，其共同的特點是作業(yè)運行時整個作業(yè)的地址空間必須全部裝入內(nèi)存的一個連續(xù)空間中，反之作業(yè)就無法運行。這類存儲管理技術(shù)統(tǒng)稱為“實存”。

“虛存”（虛擬存儲管理）技術(shù)是用軟件方法來擴充存儲器，虛擬存儲器的概念是指一種實際上并不存在的虛假存儲器，它能提供給用戶一個比實際內(nèi)存大的多的存儲空間，使用戶在編制程序時可以不必考慮存儲空間的限制。46

基本概念：

①虛擬地址：程序訪問的邏輯地址。

②實在地址：處理器可直接訪問的主存地址。

③虛擬地址空間：虛擬地址的集合。

④實在地址空間：計算機主存。注：程序和數(shù)據(jù)所在的虛擬地址必須放入主存的實在地址中才能運行。因此要建立虛擬地址和實在地址的對應(yīng)關(guān)系，這種地址轉(zhuǎn)換由動態(tài)地址映像機構(gòu)來完成。47實際上用戶的虛擬地址空間并不可能是無限大，它受到以下兩個條件制約：

1.指令中地址場長度的限制。

2.外存儲器容量的限制。

虛擬存儲管理技術(shù)需要解決的問題：

（1）什么時候把哪部分程序裝入內(nèi)存。（2）放在內(nèi)存什么位置。（3）當內(nèi)存空間不足時，把哪部分程序淘汰出內(nèi)存。

常用的虛擬存儲技術(shù)有：分頁存儲管理、分段存儲管理、段頁存儲管理。48/1951、分頁存儲管理（1）分頁管理的基本概念

①頁面、頁架（塊）在分頁存儲管理中，把每個作業(yè)的地址空間分成一些大小相等的片，稱為“頁”。同樣，把內(nèi)存的存儲空間也分成大小與頁相同的片，稱為“頁架”或者“塊”。系統(tǒng)以頁架為單位把內(nèi)存分配給各作業(yè)，每個作業(yè)占有的內(nèi)存無須連續(xù)，而且作業(yè)的所有頁面也不一定同時裝入內(nèi)存。例題如下頁。 假設(shè)系統(tǒng)選擇頁的大小為1k字節(jié)，則一個3k字節(jié)的作業(yè)將被劃分為3頁。此時主存有5個空白塊（塊2、3、8、9、11）。因此，當作業(yè)2的三塊裝入內(nèi)存時可以選擇任意3個空白塊。圖中假定第0頁裝入主存的塊2中，第一頁裝入塊3中，第2頁裝入塊8中（主存中塊9和塊11空閑）。49/195分頁映射存儲圖地址空間021328頁號頁架號操作系統(tǒng)Load1,2500

第0頁第1頁第2頁第0頁12345第1頁主存空間作業(yè)2的頁表作業(yè)2的地址空間010025003k1k2kLoad1,25001234502k3k4k5k6k7k8k9k10k11k12k作業(yè)10-1塊2塊作業(yè)38塊作業(yè)3作業(yè)2第0頁作業(yè)2第2頁作業(yè)2第1頁頁架號50/195（1）分頁管理的基本概念

②分頁系統(tǒng)中的地址結(jié)構(gòu)在分頁系統(tǒng)中，每個虛擬地址用一個數(shù)對（p,d）來表示，其中p為頁號，d是該虛擬地址在頁面號為p中的相對地址，稱為頁內(nèi)地址。為計算方便，規(guī)定頁的大小為2的冪。③頁表與頁表地址寄存器頁表：系統(tǒng)為每個作業(yè)建立一個頁面映像表（PMT），簡稱“頁表”。頁表中應(yīng)包括：頁號、頁架號、狀態(tài)。頁號：作業(yè)各頁的頁號，每個作業(yè)頁號從零開始。頁架號：該頁面在內(nèi)存中的頁架號。狀態(tài)：表示該頁是否在內(nèi)存中，用“0”表示該頁不在內(nèi)存，用“1”表示在內(nèi)存中。51/195（2）分頁系統(tǒng)中的地址轉(zhuǎn)換

當某作業(yè)被調(diào)度到處理器上運行時，操作系統(tǒng)自動將該作業(yè)的頁表的起始地址和長度裝入頁表地址寄存器中，當CPU執(zhí)行一條訪問內(nèi)存指令時，地址變換機構(gòu)把邏輯地址分解成p和d兩部分，p為頁號，d為頁內(nèi)地址。按照p在頁表中找到相應(yīng)的頁架號和狀態(tài)，若狀態(tài)為“1”，將頁架號與頁內(nèi)地址合并為內(nèi)存實在地址。若狀態(tài)為“0”，表明此頁不在內(nèi)存中，系統(tǒng)將產(chǎn)生中斷，停止執(zhí)行用戶程序，由存儲管理模塊將該頁調(diào)入內(nèi)存。下面舉一個例題，假如某系統(tǒng)頁面大小為（512)10字節(jié)，即相當于（1000)8字節(jié)，若邏輯地址為（1320)8，就可以方便的分解得到p=1,d=320.由p及頁表起始地址b，找到相應(yīng)的頁，將該頁對應(yīng)的頁架號10送入地址變換機構(gòu)p’,與頁內(nèi)地址d合并成內(nèi)存實在地址號10320。5210320地址空間Lb頁表地址器存器031110120頁號頁架號狀態(tài)

…23285…主存空間頁表分頁管理的地址轉(zhuǎn)換圖頁架號011010320頁表長頁表起始地址1320pdp’dLoad1,1320

2328501000

132020003000地址變換機構(gòu)8進制地址表示53由于分頁管理中分配給每道程序的頁架數(shù)有限，因此內(nèi)存中的頁面要隨時進行更換，稱為頁面淘汰。頁面更換不當會導致剛淘汰出內(nèi)存的頁面又要調(diào)入內(nèi)存，這樣使處理器大部分時間都用于頁面調(diào)度上，稱為“抖動”，從而降低了系統(tǒng)運行的速度。為了避免產(chǎn)生這種現(xiàn)象，需要選擇一種較好的算法進行頁面淘汰。下面介紹兩種常用的算法。（3）頁面變換算法54/195先進先出法（FIFO—FirstInputFirstOutput）：

此算法的主要思想時認為最先進入內(nèi)存的頁面，不再被使用的可能性最大，所以最先進入內(nèi)存的頁面，最先被調(diào)出內(nèi)存。下面通過一個簡單的例子來說明。 設(shè)有一用戶程序共分為5頁，其執(zhí)行時頁面變化的規(guī)律稱為頁面走向P，分配給該程序的頁架數(shù)M為3，其頁面淘汰過程如下圖，其中F為“+”號表示頁面有交換。432143543215432143555211432143335224321444355+++++++++P=M=3F=FIFO頁面淘汰過程頁面走向先進后進55/195先進先出法（FIFO）：這一算法適用于按線性順序訪問地址的程序，否則效率不高。因為最先進入內(nèi)存的頁面可能是經(jīng)常被使用的頁面，這樣會引起頁面頻繁的變換。56/195（3）頁面變換算法最近最少使用法（LRU—LeastRecentlyUsed）

此算法的基本思想認為過去一段時間中不被訪問的頁面，在最近的將來不被訪問的可能性也最大，應(yīng)將這種頁面首先淘汰。這一算法比較普遍的適用于各種類型的程序，但實現(xiàn)起來較困難，因為要為每個頁面設(shè)置自上次訪問到現(xiàn)在的時間，工作量大，而且隨時要進行更新，軟硬件的開銷太大。因此實際上是采用近似算法。57/195最近最少使用法（LRU—LeastRecentlyUsed） 下面舉例說明近似算法，每個頁架中的頁面都設(shè)一位“引用位”，由頁面管理軟件周期性的把所有引用位重新置為零。當頁面被訪問時，將其置為“1”，而未被訪問的頁面為“0”。替換指針q總是指向最近被替換的頁所在的頁架，當發(fā)生缺頁中斷需要再次替換時，從它后一塊開始檢查其引用位，如引用位為“1”，則置“0”后再向前檢查，直到發(fā)現(xiàn)第一個引用位為“0”為止。圖a表示當頁面6被替換到內(nèi)存后的狀態(tài)，圖b表示再次發(fā)生頁面替換后狀態(tài)。58/195LRU頁面替換過程01240342156

507108頁架號頁號引用位指針q01240342156

617108頁架號頁號引用位指針q59/195（4）分頁管理的存儲保護

分頁環(huán)境下的存儲保護是通過頁表地址寄存器中的頁表長度來實現(xiàn)的，當CPU訪問某邏輯地址時，硬件自動將頁號與頁表長度進行比較，如果合法才進行地址轉(zhuǎn)換，否則產(chǎn)生越界中斷。（5）分頁管理的優(yōu)缺點優(yōu)點:

不要求作業(yè)在內(nèi)存中連續(xù)存放，較好的解決了碎片問題。作業(yè)地址空間不受內(nèi)存限制，對一些不常用的部分不必常駐內(nèi)存為用戶提供足夠大存儲空間，從而有利于多道程序作業(yè)。缺點：要求一定的硬件支持，增加了成本。系統(tǒng)要增加頁表及其管理程序，從而增加了內(nèi)存的開銷。同時CPU要占有一定時間來處理頁面交換。602、分段存儲管理分段管理的基本概念①段一個程序由若干個程序模塊組成，可以按模塊來分配存儲空間。分段管理把每個模塊的地址空間稱為“段”。每個段規(guī)定一個段號，每個段的地址空間都從“0”地址開始。②分段管理中的地址結(jié)構(gòu)在分段情況下，每一個虛擬地址需要用兩部分來描述，如下圖段號s段內(nèi)地址w！在分頁存儲管理中，一個虛擬地址可以分解為頁號和頁內(nèi)地址。61③段表、段地址寄存器系統(tǒng)為每個作業(yè)建立一個段映象表（SMT），簡稱段表，段表中包括：段號、段的長度、段在主存中的起始地址、段的狀態(tài)以及存取權(quán)限等。同時系統(tǒng)設(shè)立一個段表地址寄存器，指出當前運行作業(yè)的段表在主存中的起始地址b以及段表長度L。62（2）分段管理中的地址轉(zhuǎn)換當作業(yè)要進行存儲訪問時，由硬件地址轉(zhuǎn)換機構(gòu)與段表地址寄存器找到段表中相應(yīng)段的記錄，從而將段式地址空間的二維地址轉(zhuǎn)換成實際內(nèi)存地址。如下圖，將邏輯地址s=2，w=292轉(zhuǎn)換成實際地址8292。2292邏輯地址Lb段表地址器存器01kb6kb115004kb123008kb132009201段號長度起址狀態(tài)sw12345主存空間8292地址轉(zhuǎn)換機構(gòu)SMT表分段管理的地址轉(zhuǎn)換圖63（3）分段管理的存儲保護①越界保護當CPU訪問某邏輯地址時，硬件自動將段號與段地址寄存器中段表長度進行比較，同時要將段內(nèi)地址與段表中該段長度進行比較，如果合法則進行地址轉(zhuǎn)換，否則產(chǎn)生越界。②存取控制保護由于分段情況下段是邏輯上完整的信息集合，因此要防止其中的信息被不允許共享者竊取或修改，往往用存取權(quán)限來控制各類用戶對信息的共享程度。常用的控制類型有讀、寫、執(zhí)行、修改等。64/195（4）分段管理的優(yōu)缺點優(yōu)點:

便于程序模塊化處理。每個程序模塊構(gòu)成各自獨立的分段，并采用段的保護措施不受其它模塊的影響和干擾。便于處理變化的數(shù)據(jù)。根據(jù)實際應(yīng)用中數(shù)據(jù)長度隨輸入數(shù)據(jù)多少而變化的情況，要求動態(tài)擴大一個分段的地址空間，在分段系統(tǒng)中并不困難。便于共享分段。在分段系統(tǒng)中分段的共享只要通過各作業(yè)段表的相應(yīng)表目指向同一個共享段的物理副本來實現(xiàn)。65/195缺點：要求一定的硬件支持，增加了成本。要為地址變換花費CPU時間，為表格提供附加的存儲空間。分段尺寸的大小受到主存的限制。由于段的長度不固定，會出現(xiàn)“碎片”問題，處理機要為存儲器的緊縮付出代價。663、段頁式存儲管理段頁式管理的基本概念①段頁結(jié)構(gòu)段頁式管理是分頁和分段管理結(jié)合的結(jié)果。段頁式管理中，作業(yè)的地址空間采用分段方式，而作業(yè)的每一段采用分頁方式。整個主存分成大小相等的存儲塊，稱為頁架，主存以頁架為單位分配給每個作業(yè)。②段頁管理的地址結(jié)構(gòu)段頁式管理中的邏輯地址用三個參數(shù)表示，如下圖段號s頁號p頁內(nèi)地址d段頁式管理地址結(jié)構(gòu)67③段表、頁表、段地址寄存器系統(tǒng)為每個作業(yè)建立一個段表，并為每個段建立一個頁表，并設(shè)置一個段地址寄存器來指出當前運行作業(yè)段的段表起始地址和段表長度。68（2）段頁式管理的地址轉(zhuǎn)換①地址轉(zhuǎn)換硬件將邏輯地址中的段號s與段地址寄存器中的段表起始地址b相加得到該訪問段的表目。②從該段表目中得到該段頁表的起始地址，并與邏輯地址中的頁號p相加得到欲訪問頁在該段頁表中的地址。③從該頁表目中得到對應(yīng)的頁架號p’并與邏輯地址中的頁內(nèi)地址d相加得到絕對地址。下圖表示段頁管理的地址轉(zhuǎn)換過程。69/195段頁管理的地址轉(zhuǎn)換圖

主存空間頁架號01234567

1

0

3

0

1

1

2

5

狀態(tài)頁號頁架號PMT0

1

0

6

1

1

7

0

2

0

3

5PMT3

1

0

0

1

s

p

d邏輯地址SMT

L

b段表地址器存器頁表長度頁表起始地址狀態(tài)

p’

d物理地址70（3）段頁式管理的優(yōu)缺點優(yōu)點:

段頁式管理具有分頁、分段管理的優(yōu)點，是使用的最廣泛、最靈活的一種存儲管理技術(shù)。缺點：需要更多的硬件支持，增加了硬件的成本，同時也增加了軟件的復雜性和管理開銷。許多大中型計算機，如IBM370/168、Multics等都采用這種段頁式虛擬存儲器。71/1953.3處理器管理3.3.1基本概念與術(shù)語3.3.2作業(yè)調(diào)度3.3.3進程調(diào)度3.3.4多道程序并發(fā)運行出現(xiàn)的問題3.3.5

多道程序設(shè)計基礎(chǔ)—并行程序設(shè)計72/1953.3.1基本概念與術(shù)語

在多道程序系統(tǒng)中，處理器數(shù)小于程序數(shù)，于是處理器就在各程序間進行切換，因此在一個處理器上要交叉運行若干道程序。處理器管理就是要解決用戶遞交的作業(yè)何時調(diào)入內(nèi)存，在調(diào)入內(nèi)存的各個作業(yè)程序間如何分配處理器，以達到各道程序能協(xié)調(diào)一致運行，而系統(tǒng)資源又能得到最大程度的利用。

基本概念與術(shù)語作業(yè)和進程

特權(quán)指令、處理器狀態(tài)

處理器管理73/195

★作業(yè)和進程⑴作業(yè)、作業(yè)步

作業(yè)是用戶在一次算題過程中或一個事務(wù)處理中要求計算機系統(tǒng)所作工作的集合。一個作業(yè)由一系列的作業(yè)步組成。一個作業(yè)步運行的結(jié)果產(chǎn)生下一個作業(yè)步所需的文件。例如一個C語言程序要經(jīng)歷編輯、編譯、連接、運行四個作業(yè)步。74/195⑵進程和程序在多道程序系統(tǒng)中，多道程序并發(fā)運行，為了競爭有限的資源，相互間存在依賴與制約關(guān)系，它們在系統(tǒng)中的狀態(tài)是不斷變化的，即時而運行，時而停頓。因此引入新的概念---進程。一旦操作系統(tǒng)接受了某用戶的作業(yè)，并把它調(diào)入內(nèi)存執(zhí)行，系統(tǒng)就為此作業(yè)創(chuàng)建一個或多個進程。因此進程可以看成是程序的一次執(zhí)行，即是在指定內(nèi)存區(qū)域中的一組指令序列的執(zhí)行過程。多個進程可以并發(fā)進行，并可能由于各種原因隨時中斷。

75/195⑵進程和程序

從對進程的描述來看，進程既與程序有關(guān)，又與程序不同，它們的區(qū)別是：①進程是程序的執(zhí)行，因此屬于動態(tài)的概念；而程序是一組指令的集合，屬于靜態(tài)的概念。②進程既然是程序的執(zhí)行，因此它是有生命過程的，進程有誕生（創(chuàng)建進程）和死亡（撤消進程），應(yīng)此進程的存在是暫時的，而程序的存在是永久的。76/195★特權(quán)指令、處理器狀態(tài)

每個處理器都有自己的指令系統(tǒng)，在多道程序環(huán)境中為了保證系統(tǒng)正常工作，將指令系統(tǒng)中的指令分為兩類：

1.特權(quán)指令：只能由操作系統(tǒng)使用。

2.非特權(quán)指令：供一般用戶使用。對應(yīng)兩種不同的指令，處理器有兩種執(zhí)行狀態(tài)。管態(tài)：又稱主態(tài)、執(zhí)行狀態(tài),此時處理器執(zhí)行特權(quán)指令。目態(tài)：又稱算態(tài)、題目狀態(tài)，此時處理器處于用戶執(zhí)行狀態(tài)。77/195★處理器管理

在大型通用系統(tǒng)中，可能有數(shù)百個作業(yè)等待處理，處理器管理又稱處理器調(diào)度，就是解決如何從這些作業(yè)中挑選一些進入主存運行，又如何在主存各進程間分配處理器。它一般分為兩級：作業(yè)調(diào)度：又稱高級調(diào)度或宏觀調(diào)度。它的主要功能是按照某種調(diào)度原則，選取某些作業(yè)進入內(nèi)存，為它們分配必要的資源，建立相應(yīng)的進程，并當作業(yè)完成后做好一切善后工作。進程調(diào)度：又稱低級調(diào)度或微觀調(diào)度。它的主要功能是按照某種調(diào)度原則，實現(xiàn)處理器在各進程間的轉(zhuǎn)換。78/1951.作業(yè)狀態(tài)轉(zhuǎn)換及作業(yè)控制塊 一個作業(yè)從進入系統(tǒng)到運行結(jié)束，一般要經(jīng)歷以下四種狀態(tài):提交收容執(zhí)行完成。3.3.2作業(yè)調(diào)度提交收容完成去分配作業(yè)管理設(shè)備管理輔存執(zhí)行內(nèi)存作業(yè)的四種狀態(tài)79/1951.作業(yè)狀態(tài)轉(zhuǎn)換及作業(yè)控制塊提交狀態(tài)：用戶向機房提交作業(yè)或通過終端鍵盤將作業(yè)輸入，其作業(yè)所處的狀態(tài)為提交狀態(tài)。收容狀態(tài)：作業(yè)的全部信息已經(jīng)輸入外存等待運行，又稱為后備狀態(tài)。執(zhí)行狀態(tài)：作業(yè)被作業(yè)調(diào)度程序選中進入內(nèi)存，稱為執(zhí)行狀態(tài)。完成狀態(tài)：作業(yè)執(zhí)行完畢，釋放其占用的全部資源，準備退出系統(tǒng)。80/1951.作業(yè)狀態(tài)轉(zhuǎn)換及作業(yè)控制塊作業(yè)名：用戶作業(yè)的名稱。狀態(tài)：輸入/收容/執(zhí)行。優(yōu)先數(shù)：根據(jù)作業(yè)的重要程度，由系統(tǒng)或用戶確定。運行時間：估計完成本作業(yè)所需時間。位置：本作業(yè)在外存中的起始地址。長度：作業(yè)的地址空間。外設(shè)申請：作業(yè)運行時要求的外部設(shè)備。為了管理和調(diào)度作業(yè)，系統(tǒng)為每個作業(yè)建立一個作業(yè)控制塊（JCB-JobControlBlock），它詳細記錄每個作業(yè)的有關(guān)信息。不同系統(tǒng)的JCB不完全相同，主要有：81/1951.作業(yè)狀態(tài)轉(zhuǎn)換及作業(yè)控制塊所有的JCB可按作業(yè)的優(yōu)先數(shù)大小或作業(yè)到達系統(tǒng)的時間順序構(gòu)成一個作業(yè)隊列，如下圖所示作業(yè)名現(xiàn)在狀態(tài)優(yōu)先數(shù)時間估計位置長度外設(shè)申請…指向下一個JCB指針JCB1JCB2JCBn…作業(yè)控制塊與作業(yè)隊列82/1952.作業(yè)調(diào)度的功能按照某種調(diào)度算法，從作業(yè)隊列中選取作業(yè)進入內(nèi)存。調(diào)用存儲管理和設(shè)備管理程序，為被選中的作業(yè)分配內(nèi)存和外設(shè)。為選中的作業(yè)建立相應(yīng)的進程。作業(yè)運行完畢時回收該作業(yè)占用的資源，輸出必要的信息，撤消該作業(yè)的JCB與相應(yīng)的進程。83/1953.作業(yè)調(diào)度算法

多道程序下作業(yè)調(diào)度的目標是在眾多作業(yè)中選擇一個或多個作業(yè)投入運行，這些作業(yè)的組合使系統(tǒng)能運行盡可能多的作業(yè)，系統(tǒng)資源能得到充分利用，而且能對所有作業(yè)盡量公平合理。一般在設(shè)計調(diào)度算法時考慮的因素有：

選擇的調(diào)度算法應(yīng)與系統(tǒng)整個設(shè)計的目標一致。如在批處理系統(tǒng)中，應(yīng)著重提高處理器的使用效率；分時系統(tǒng)中應(yīng)保證用戶所能忍受的響應(yīng)時間；實時系統(tǒng)中應(yīng)在保證及時響應(yīng)的前提下才考慮系統(tǒng)資源的使用效率。應(yīng)注意系統(tǒng)資源的均衡使用。應(yīng)保證進入系統(tǒng)的作業(yè)能在規(guī)定時間內(nèi)完成。84/195下面介紹三種常用的作業(yè)調(diào)度算法：先來先服務(wù)算法：這是一種最簡單的調(diào)度算法。系統(tǒng)按作業(yè)錄入的先后次序建成作業(yè)隊列，調(diào)度程序從隊頭開始調(diào)度作業(yè)。

基于優(yōu)先級的調(diào)度算法：作業(yè)的優(yōu)先級可以由用戶在申請作業(yè)時根據(jù)作業(yè)的緊急程度制訂一個優(yōu)先數(shù)，有時為保證輸出量少，要求運行時間短的作業(yè)或已等待較久的作業(yè)能得到運行，可用如下的計算公式：

優(yōu)先數(shù)=(等待時間)2

－(要求運行時間)－(輸出量）它的基本思想是既保證優(yōu)先照顧各種短作業(yè)，但是也不致使長作業(yè)因等待過久而等不到運行機會。

3.作業(yè)調(diào)度算法

85/195

分時和優(yōu)先級結(jié)合的調(diào)度算法：這種調(diào)度算法主要用于具有分時操作的系統(tǒng)中，將后備作業(yè)按優(yōu)先數(shù)分成幾個隊列，系統(tǒng)為每個隊列分配一個相應(yīng)的時間片。作業(yè)調(diào)度程序總從優(yōu)先數(shù)高的隊列中選擇作業(yè)運行，當該作業(yè)時間片用完后，它回到比原先低一級的后備作業(yè)隊列中。86/1951.進程的狀態(tài)轉(zhuǎn)換和進程控制塊 當作業(yè)管理程序?qū)⒂脩糇鳂I(yè)調(diào)入內(nèi)存后，作業(yè)以進程形式出現(xiàn)。在內(nèi)存中的多個進程具有不同的狀態(tài)，它們隨著系統(tǒng)運行狀況的變化而不斷變化。進程的三種基本狀態(tài)（就緒、運行、阻塞）如下：（1）就緒狀態(tài)：進程已具備各種必要的資源，只等待獲得CPU。（2）運行狀態(tài)：系統(tǒng)根據(jù)調(diào)度算法，將CPU分配給某一個就緒進程使之運行，該進程就處于運行狀態(tài)。當運行的進程由于分配的CPU時間已到或是由于I/O要求，則必須交出CPU就轉(zhuǎn)入就緒或阻塞狀態(tài)。3.3.3進程調(diào)度87/195（3）阻塞狀態(tài)：進程在運行中由于要等待I/O設(shè)備或發(fā)生其它錯誤時，就轉(zhuǎn)入阻塞狀態(tài)。待到阻塞原因消除后，重新回到就緒狀態(tài)。

與作業(yè)管理相似，系統(tǒng)為每個進程建立一個進程控制塊（PCB—ProcessControlBlock)。PCB中的信息分為如下兩種：a.說明信息：包括進程名、優(yōu)先數(shù)及當前狀態(tài)。b.保留信息：是保留該進程由運行狀態(tài)轉(zhuǎn)入阻塞或就緒狀態(tài)時當時各寄存器的內(nèi)容，以便當該進程重新進入運行時恢復當時各寄存器狀況，如下圖所示。88/195進程各狀態(tài)之間轉(zhuǎn)換的示意圖進程名優(yōu)先數(shù)當前狀態(tài)寄存器內(nèi)容…指向下一個PCB進程調(diào)度就緒運行阻塞作業(yè)管理完成I/O完成時間到I/O要求說明信息保留信息89/1952.進程控制

進程控制對系統(tǒng)中全部進程實施有效的管理，即它應(yīng)具有創(chuàng)建進程、撤消進程、改變進程狀態(tài)的功能。 在非結(jié)構(gòu)系統(tǒng)中，進程控制按功能由操作系統(tǒng)內(nèi)部完成，用戶無法參與，這類系統(tǒng)中各進程是互相平等的。在樹型結(jié)構(gòu)系統(tǒng)中，一個進程能夠創(chuàng)建一個或多個進程，前者稱為父進程，后者稱為子進程。這樣就形成了一個進程家族。如下圖所示。90/195進程的層次結(jié)構(gòu)P0P1P2P4P5P6P3P791/1952.進程控制

原語是機器指令的延伸，由若干條機器指令構(gòu)成，用以完成某一特定功能的程序段，又稱為廣義指令。原語在執(zhí)行期間是不允許被中斷的。它可以提供給用戶在程序中調(diào)用，通用的調(diào)用形式為：原語名稱（參數(shù)集）。對應(yīng)進程控制的原語有四個：3.3.3進程調(diào)度

92/195（1）創(chuàng)建原語：按調(diào)用者提供的參數(shù)，構(gòu)成該進程的PCB.（2）掛起原語：中斷該進程的運行，把PCB中的狀態(tài)置為阻塞狀態(tài)。（3）激活原語：把某阻塞進程置為就緒狀態(tài)，等待分配CPU。（4）撤消原語：停止該進程的執(zhí)行，釋放它所占有的各種資源，刪除該進程的PCB。93/1953.進程調(diào)度算法

進程調(diào)度的核心是采用某種算法動態(tài)的把處理器分配給就緒隊列中的某個進程。進程調(diào)度算法與作業(yè)調(diào)度算法有很多相似處。（1）優(yōu)先數(shù)法：把處理器分配給具有最高優(yōu)先數(shù)的進程。（2）輪轉(zhuǎn)調(diào)度法：適用于多道批處理系統(tǒng)。按照規(guī)定的時間片將處理器輪流分配給就緒隊列中的進程。94/195（3）分級調(diào)度法：

是上述兩種算法的結(jié)合。因為在簡單輪轉(zhuǎn)法中，對于在一個時間片內(nèi)不能完成的進程，優(yōu)先數(shù)的作用不明顯，為使進程能正比于優(yōu)先數(shù)的速度向前推進，可將單就緒隊列改為雙就緒隊列，一個稱為前臺隊列，它具有較高的優(yōu)先數(shù)，另一個稱為后臺隊列，它具有較低的優(yōu)先數(shù)。進程調(diào)度以固定的時間片把處理器分配給前臺隊列中的進程，僅當前臺隊列中的進程完成或等待I/O時，才把處理器分配給后臺進程。95/195進程的同步與互斥

（1）同步與互斥現(xiàn)象

“同步”是指兩個事件的發(fā)生存在某種時序上的關(guān)系，如果系統(tǒng)中有若干個進程要共同完成某一任務(wù)，那么它們相互之間必須協(xié)調(diào)配合，這就需要有一種工具使它們同步運行。

“互斥”是進程間的一種關(guān)系。當多個進程要求共享系統(tǒng)中某些硬件或軟件資源，而這些資源卻又要求排它性使用時，往往引起由于多個進程競爭同一資源使運行結(jié)果出現(xiàn)問題。6.3.4多道程序并發(fā)運行出現(xiàn)的問題96/195Count中只增加1進程的同步與互斥（1）同步與互斥現(xiàn)象例如：有兩個進程P1,P2都對公共變量count作加1操作P1:R1<-count;P2:R2<-count;P1:R1<-R1+1;count<-R1;P2:R2<-R2+1;count<-R2;97/195(2)解決進程同步與互斥的工具

解決同步與互斥的工具有很多，可以由硬件或軟件實現(xiàn)。下面介紹一種用同步原語對某信號量進行操作以實現(xiàn)同步與互斥的方法，通常稱為P-V操作。98/195

P操作P(s)s←s-1if(s<0)then{status(q)←”blocked”//將進程q置為“阻塞”//Insert(Q,q)}//將q插入阻塞隊列Q中//return V操作V(s)s←s+1if(s≤0)then{remove(Q,R)//將R移出阻塞隊列//status(R)←”ready”//將R置為就緒//Insert(RL,R)}//將R插入就緒隊列RL中//return99/195(3)用P-V操作實現(xiàn)進程互斥在上述例子中，如果在進程P1,P2中加入P-V操作，可以實現(xiàn)對公用變量count的互斥使用。其中P(s),V(s)之間的程序段稱為臨界區(qū)。P1…P(s)R1←count臨R1←R1+1界Count←R1區(qū)V(s)…P2…P(s)R2←count臨R2←R2+1界Count←R2區(qū)V(s)…s=s-1=0設(shè)初值s=1s=s+1=0s=s-1=-1<0,p2插入到阻塞隊列Q,直到p1執(zhí)行完臨界區(qū)和v(s)操作后，使s=0才可能激活p2.100/195

★非對稱制約如果進程p1在執(zhí)行到L1處需要從進程p2獲取信息，而這些信息卻是p2到達L2后才能提供，為此兩進程必須采用如下方式進行同步：P1…L1:P(s){獲取信息}…P2…{產(chǎn)生信息}L2:V(s)…●設(shè)置初值S=0，在進程P2尚未完成V(S)操作之前，進程P1只能處于等待狀態(tài)。101/195★雙向制約—生產(chǎn)者和消費者問題

生產(chǎn)者和消費者問題是并發(fā)進程內(nèi)在關(guān)系的一種抽象，具有很大的使用價值。生產(chǎn)者生產(chǎn)物品放入公共緩沖區(qū)供消費者使用。但在運行過程中，要防止生產(chǎn)者將物品放入已滿的緩沖區(qū)；禁止消費者從空緩沖區(qū)取物品?？梢杂肞-V操作實現(xiàn)生產(chǎn)者和消費者兩個進程之間的同步。生產(chǎn)者L1:{生產(chǎn)物品}P(s1){將物品放入緩沖區(qū)}V(s2)GotoL1消費者C1:P(s2){從緩沖區(qū)取物品}V(s1){消費物品}GotoC1●設(shè)置初值s1=1，s2=0，這樣當兩個進程運行時，不論在何處中斷，均能進行協(xié)調(diào)工作。s1用來防止生產(chǎn)者將物品放入已滿的緩沖區(qū)；s2用來防止消費者從空緩沖區(qū)取物品。102/195

2.進程通信

由于一個作業(yè)可以被分解成多個進程并行執(zhí)行，因此進程間應(yīng)保持聯(lián)系，這種聯(lián)系通常表現(xiàn)為進程之間需要交換一定量的信息，稱為進程通信。（1）直接通信

直接通信又稱消息緩沖區(qū)。是指一個進程直接發(fā)送一組消息給接收進程。發(fā)送的消息由消息頭和消息正文組成：發(fā)送進程名（N)

消息長度（size）消息正文（text）消息頭103/195系統(tǒng)提供發(fā)送和接收原語：

Send(P,Msg):

向P進程發(fā)送一個消息，Msg為發(fā)送區(qū)首地址

Receive(P,Msg):

接收來自P進程的一個消息，Msg為接收區(qū)首地址

下面舉一個例題：從進程A發(fā)送字符串“hello”到進程B。發(fā)送進程A用Send(B,dA)原語把發(fā)送消息從發(fā)送區(qū)dA復制到消息緩沖區(qū)。進程B的PCB中增加一個指針Hptr，指向發(fā)送到B進程的第一個消息緩沖區(qū)，所有發(fā)送到進程B的消息緩沖區(qū)構(gòu)成一個消息隊列。接收進程B用Receive(A,dB)原語把發(fā)送來的消息復制到接收區(qū)，并將該消息緩沖區(qū)從消息隊列中刪除。104/195兩個進程A,B進行通信Send(B,dA)N:BSize:5Text:helloA進程dAReceive(B,dB)N:ASize:5Text:helloB進程dBHptrB進程的PCBSptr:ASize:5Text:helloNptr第一個消息緩沖區(qū)Nptr:0第2個消息緩沖區(qū)SendReceive接收區(qū)發(fā)送區(qū)105/195（2）信箱通信

這是一種間接通信方式。進程間通信的消息以信件方式存放在信箱內(nèi)。當兩個進程要進行通信時，由發(fā)送方創(chuàng)建一個鏈接兩個進程的信箱，信箱的結(jié)構(gòu)分為信箱頭和正文，要進行通信時只需把信件投入信箱，接受進程可在任何時候取走。信箱通信的原語形式為

Send(A,Msg):發(fā)送消息到信箱AReceive(A,Msg):從信箱A接收一個消息106/1953死鎖

死鎖是指計算機系統(tǒng)中進程所處的一種狀態(tài)。在多道程序系統(tǒng)中，實現(xiàn)資源共享是操作系統(tǒng)的基本目標，但不少資源要求互斥地使用，如果使用不當就會產(chǎn)生死鎖。 例如系統(tǒng)有兩個進程P1和P2，以及一個打印機（R1）和輸入機（R2）。在運行過程中，P1占用了

R1和P2占用了

R2，此時P1又申請輸入機而P2又申請打印機，那么這時P1和P2均無法運行，系統(tǒng)進入死鎖狀態(tài)。用下圖所示。進程循環(huán)鏈P1P2R1R2107/195(1)死鎖的原因和必要條件

隨著系統(tǒng)的不斷增大和復雜化，產(chǎn)生死鎖的可能性也隨著增加，解決死鎖的方法大致有以下三類：①死鎖的預防。②死鎖的避免。③死鎖的檢測和恢復。

108/195（1）死鎖的原因和必要條件

產(chǎn)生死鎖的原因為①系統(tǒng)資源不足。②進程推進的順序不當。

產(chǎn)生死鎖的必要條件為①所涉及的資源是非共享的。②進程在等待新資源時，繼續(xù)占用已分配到的資源。③一個進程占有的資源不能被別的進程強行搶占。④一個進程獲得的資源同時被另一個進程所請求，從而形成一個進程的循環(huán)鏈。109/195（2）死鎖的預防鎖的預防是研究如何破壞產(chǎn)生死鎖的必要條件之一，從而達到不使死鎖發(fā)生的目的。下面討論破壞四個必要條件的可能和方法。

破壞條件①較難實現(xiàn)，因為有些系統(tǒng)資源的性質(zhì)是非共享的，但可以采用假脫機技術(shù)將非共享設(shè)備變成共享設(shè)備來實現(xiàn)。

破壞條件②的方法是規(guī)定各進程所需的全部資源只能事先一次申請（靜態(tài)分配），并在沒有獲得全部資源之前，不能運行。實現(xiàn)較容易，但分配到的資源可能使用時間很短，而被某個進程長時間占用，浪費資源。必要條件110/195 破壞條件③的方法是規(guī)定一個規(guī)則，當某進程的資源請求被拒絕時，必須釋放其所有已獲得的資源。但這一策略對某些設(shè)備行不通。

破壞條件④可以對各類設(shè)備設(shè)置一個分配序號，如果某進程已分配到第k號設(shè)備，則以后只能再申請k以后序號的資源，稱為按序分配。這是動態(tài)分配方法。但是當進程請求高序號資源后，不能再申請低序號的資源，而提前申請又造成資源空閑等待的浪費現(xiàn)象。必要條件111/195（3）死鎖的避免

死鎖的避免并不嚴格限制必要條件的存在，因為必要條件的存在并不一定產(chǎn)生死鎖。死鎖的避免是考慮萬一當死鎖有可能出現(xiàn)時，小心避免。下面介紹一種死鎖避免的算法—銀行算法。銀行算法是由Dijkstra于1965年首先提出的。它是研究銀行與用戶間的資金借貸問題，但和操作系統(tǒng)中資源分配問題相似。算法規(guī)定：

1.每個用戶必須預先申請它所需的貸款總數(shù)，且數(shù)值不能超過銀行資金總數(shù)。112/195

2.每個用戶每次只能向銀行申請一個單位貸款數(shù)。

3.銀行根據(jù)當時的資金情況，可能立即滿足用戶申請，或需要用戶等待一段有限時間。

4.當用戶貸款總數(shù)達到申請數(shù)后，必須在有限時間內(nèi)一次歸還所有貸款。

按上述借貸規(guī)定，若銀行能滿足每個用戶的申請，又能收回資金，則稱此狀態(tài)是安全的，否則為不安全的。113/195

例如某銀行資金總數(shù)為10萬元，用戶甲、乙、丙申請貸款總數(shù)分別為8萬元、3萬元、9萬元。用戶每次向銀行申請貸款數(shù)為1萬元。其借貸過程如下表，詳細描述過程見下頁。狀態(tài)銀行甲乙丙

A10(8)(3)(9)…………B24(4)2(1)2(7)114/195①A為初始狀態(tài)，銀行庫存10萬元，甲乙丙申請貸款分別為8，3，9萬元。②當借貸進行到狀態(tài)B時，甲、乙、丙分別得到貸款4，2，2萬元。括號中的數(shù)字為尚可申請的貸款數(shù)。③若甲乙丙繼續(xù)提出貸款申請，銀行要考慮庫存與各用戶尚可申請的貸款數(shù)，為使借貸安全，只同意繼續(xù)提供用戶乙的貸款，而甲和丙暫時等待，待用戶乙獲得全部貸款并在有限時間內(nèi)全部歸還后再考慮貸款。如此進行下去，各用戶均能獲得貸款，而銀行也可以如數(shù)收回資金，其過程如下頁表所示：115/195銀行算法狀態(tài)銀行甲乙丙

C14(4)3(0)2(7)D4歸還…………E08（0）2（7）F8歸還……G19（0）H10歸還116/195非銀行算法可能引起的死鎖狀態(tài)狀態(tài)銀行甲乙丙

C15(3)2(1)2(7)D05(3)

2(1)3(6)E(死鎖)

如果銀行隨意給各申請用戶貸款，則可能出現(xiàn)銀行庫存滿足不了甲、乙、丙的申請余額，使它們永不歸還貸款，從而使銀行無法收回資金，系統(tǒng)處于死鎖狀態(tài)，如下表所示。117/195

死鎖的檢測和恢復技術(shù)是一種變通的方法，它允許死鎖發(fā)生，但能在適當時間檢測出來，并設(shè)法進行恢復。死鎖的檢測算法通常使用在允許前三個死鎖必要條件存在的系統(tǒng)中。檢測算法主要是檢查系統(tǒng)中是否存在第四種死鎖條件（存在進程的循環(huán)鏈）。我們利用化簡進程—資源有向圖的方法來檢測系統(tǒng)在某一特定狀態(tài)時是否處于死鎖狀態(tài)。進程—資源有向圖是表示系統(tǒng)運行中某一時刻進程占有的資源以及需要的資源情況。（不講）（4）死鎖的檢測和恢復118/195

死鎖的恢復技術(shù)有：①強制性的從系統(tǒng)中撤消某些進程，并剝奪它們的資源給剩下的進程使用。這樣被撤消進程前面已完成的工作全部損失了。②使用一個有效的掛起和解除掛起機構(gòu)來掛起一些進程，從掛起進程那里搶占資源以解除死鎖。

119/195SFP1P2Pi3.3.5多道程序設(shè)計基礎(chǔ)—并行程序設(shè)計 多道環(huán)境下的程序設(shè)計稱為并行程序設(shè)計，而傳統(tǒng)的程序設(shè)計稱為順序程序設(shè)計。

順序程序設(shè)計：執(zhí)行完一條指令再執(zhí)行一條指令。順序程序設(shè)計的工作流程如下圖所示。其中S為起始，F(xiàn)為結(jié)束，P1

～Pi為程序段。

120/195順序程序設(shè)計的特點為程序的順序性：程序的執(zhí)行嚴格按照程序所規(guī)定的順序，每一個操作必須在下一個操作開始之前結(jié)束。程序環(huán)境的封閉性：由于運行程序獨占系統(tǒng)全部資源，只有程序本身的動作才能改變環(huán)境，不受其它程序等外界因素影響。程序運行的確定性與可再現(xiàn)性：程序運行與執(zhí)行速度、時間無關(guān)，可以用相同的初始條件再現(xiàn)前一次計算情況。121/195并行程序設(shè)計：有些作業(yè)各操作之間只要求部分共享，有些部分可以并行執(zhí)行。并行程序設(shè)計的操作流程如下圖所示。例如要計算兩個矩陣求逆后相加，其中S為起始，F(xiàn)為結(jié)束，P1、

P2

為矩陣求逆，P3為相加運算。

P1、

P2可以并行運行后再進行相加運算。SFP1P2P3122/195并行程序設(shè)計的特點為并行性：多個程序或程序段可以并行執(zhí)行，在單處理器系統(tǒng)中即可互相切換。共享性：系統(tǒng)中各程序不但共享硬件資源，而且共享軟件資源。同步與互斥123/1953.4設(shè)備管理3.4.1設(shè)備管理的功能及基本概念3.4.2設(shè)備管理的工作過程3.4.3虛擬設(shè)備—假脫機系統(tǒng)124/195設(shè)備管理的基本任務(wù)是按照用戶的要求來控制外部設(shè)備的工作，以完成用戶所希望的輸入輸出操作。外部設(shè)備是信息的輸入輸出（I/O）機構(gòu)，它為進程提供與外部世界的通信。但是I/O設(shè)備具有多樣性，各種外部設(shè)備有不同的性能和操作方式。例如：

速度差異傳送單位不同數(shù)據(jù)表示方式不同操作方式不同125設(shè)備管理的功能方便性：操作系統(tǒng)的設(shè)備管理能提供標準的輸入輸出控制系統(tǒng)供用戶使用，省去了用戶自己編寫設(shè)備輸入輸出程序的麻煩，為用戶提供一個友好的使用環(huán)境。設(shè)備獨立性：用戶的程序與設(shè)備互相獨立。用戶在程序中只需用相對設(shè)備號表示設(shè)備，當程序運行時由設(shè)備管理把相對設(shè)備號與具體設(shè)備對應(yīng)起來。并行性：設(shè)備管理可以使外設(shè)與CPU并行工作，提高設(shè)備利用率和系統(tǒng)效率。有效性與均衡性：由于輸入輸出設(shè)備工作速度與CPU差異很大，因此輸入輸出操作往往成為計算機系統(tǒng)中的“瓶頸”，設(shè)備管理可以保持各設(shè)備的有效工作和忙閑均衡。3.4.1設(shè)備管理的功能及基本概念126設(shè)備分類按設(shè)備的使用性質(zhì)分：獨享設(shè)備：一般為低速輸入輸出設(shè)備，用戶獨占，如打印機共享設(shè)備：允許多個用戶同時共同使用的設(shè)備，如光盤虛擬設(shè)備：通過軟件功能，把原來的獨享設(shè)備轉(zhuǎn)換成共享設(shè)備127邏輯設(shè)備與物理設(shè)備：絕對設(shè)備號：按物理設(shè)備編號。相對設(shè)備號：又稱設(shè)備類型號或邏輯設(shè)備號相對號:如果用戶要使用幾臺同類型的設(shè)備時，則應(yīng)加上該類設(shè)備的相對號。符號名：在操作系統(tǒng)的命令語言中，通常用符號名來代替設(shè)備類型號。如LPT為并行打印機128

3.通道與中斷 計算機訪問外設(shè)的方式是隨著通道與中斷的產(chǎn)生逐漸得到改進的。⑴循環(huán)測試I/O方式：

CPU啟動外設(shè)后要不斷詢問外設(shè)的忙閑，當外設(shè)為“忙”時，CPU不斷對它進行測試，直到外設(shè)為“閑”時進行輸入輸出。在此期間CPU不能進行其它操作。

⑵程序中斷I/O方式：

當有中斷設(shè)施時，CPU啟動外設(shè)后就轉(zhuǎn)向其它程序，只在發(fā)出I/O中斷請求時，再轉(zhuǎn)去進行輸入輸出操作，因此大部分時間CPU可做它用。129⑶通道I/O方式：中斷方式中每處理一個字即要進行一次中斷處理，當有大批數(shù)據(jù)要傳送時，中斷次數(shù)多，要花費很多處理器的時間，通道的出現(xiàn)建立了I/O的獨立管理機構(gòu)，這時只要CPU發(fā)一條I/O指令給通道，告訴通道要執(zhí)行I/O操作的設(shè)備和傳送數(shù)據(jù)的位置，由通道完成成批數(shù)據(jù)的傳送，此時CPU可以運行其它程序。1304.緩沖技術(shù)

緩沖技術(shù)是指在內(nèi)存中劃出一個由N個單元組成的區(qū)域，稱為緩沖區(qū)，作為外設(shè)在進行數(shù)據(jù)傳輸時的暫存區(qū)，以解決CPU處理數(shù)據(jù)速度與外設(shè)傳輸數(shù)據(jù)速度不匹配的問題，減少瓶頸現(xiàn)象。根據(jù)需要可以采用不同的結(jié)構(gòu)形式—單緩沖區(qū)和雙緩沖區(qū)、多緩沖區(qū)、緩沖池。131

⑴單緩沖區(qū)和雙緩沖區(qū)：

單緩沖區(qū)中系統(tǒng)僅設(shè)一個緩沖區(qū)，進程與外設(shè)間的輸入輸出如下圖所示。在單緩沖區(qū)下，當某一外設(shè)占用緩沖區(qū)后，必須等緩沖區(qū)為空后，才能放新數(shù)據(jù)，因此外設(shè)間是串行工作的。雙緩沖區(qū)是開設(shè)兩個緩沖區(qū)，配合使用，可以使兩個外設(shè)并行工作，提高設(shè)備效率。進程緩沖區(qū)外設(shè)I/OI/O132/195⑵多緩沖區(qū)：當進程輸入輸出數(shù)據(jù)量很大或不均勻時，為使外設(shè)與CPU能很好的并行工作，應(yīng)設(shè)置多緩沖區(qū)，一般將輸入、輸出緩沖區(qū)分別連接成環(huán)形多緩沖區(qū)，如下圖所示。RqGGGGRp說明:（1）對輸入緩沖區(qū)，指針p指示進程下次可取用的緩沖區(qū)，指針q指示輸入設(shè)備輸入時可用的緩沖區(qū)地址。（2）對輸出緩沖區(qū)來說，進程把輸出數(shù)據(jù)按指針q依次輸入緩沖區(qū)，而輸出設(shè)備則按指針p依次輸出。133⑶緩沖池：

當把輸入輸出緩沖區(qū)統(tǒng)一起來，形成一個既能用于輸入又能用于輸出的緩沖區(qū)，稱為緩沖池。在緩沖池中存在三種類型緩沖區(qū)：輸入數(shù)據(jù)緩沖區(qū)、輸出數(shù)據(jù)緩沖區(qū)、空白緩沖區(qū) 每一種緩沖區(qū)都通過鏈指針鏈成三個隊列，稱為輸入隊列(in),輸出隊列(out)，空白隊列(em)，如下圖所示。in

1

611

7em12

4out

2

53

8910134/1951.通道、控制器和設(shè)備計算機的外設(shè)由控制部分與設(shè)備本身兩部分組成，有時將控制部分分離出來稱為控制器，可以用來控制若干個設(shè)備。這樣由通道、控制器和設(shè)備構(gòu)成一個輸入輸出通路，它們之間可以有不同的連接方式。如下面三個圖所示。不同的連接方式需要不