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

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

概述2

存儲(chǔ)管理3

處理器管理4

設(shè)備管理5

文件管理6

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

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

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

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

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

脫機(jī)批量處理—減少了人工干預(yù)的時(shí)間

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

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

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

16/1953.2存儲(chǔ)管理3.2.1

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

實(shí)存儲(chǔ)管理3.2.3

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

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

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

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

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

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

3)存儲(chǔ)保護(hù)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基本概念：

①虛擬地址：程序訪(fǎng)問(wèn)的邏輯地址。

②實(shí)在地址：處理器可直接訪(fǎng)問(wèn)的主存地址。

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

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

1.指令中地址場(chǎng)長(zhǎng)度的限制。

2.外存儲(chǔ)器容量的限制。

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

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

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

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

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

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

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

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

2328501000

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

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

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

507108頁(yè)架號(hào)頁(yè)號(hào)引用位指針q01240342156

617108頁(yè)架號(hào)頁(yè)號(hào)引用位指針q59/195（4）分頁(yè)管理的存儲(chǔ)保護(hù)

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

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

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

主存空間頁(yè)架號(hào)01234567

1

0

3

0

1

1

2

5

狀態(tài)頁(yè)號(hào)頁(yè)架號(hào)PMT0

1

0

6

1

1

7

0

2

0

3

5PMT3

1

0

0

1

s

p

d邏輯地址SMT

L

b段表地址器存器頁(yè)表長(zhǎng)度頁(yè)表起始地址狀態(tài)

p’

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

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

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

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

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

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

處理器管理73/195

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

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

75/195⑵進(jìn)程和程序

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

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

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

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

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

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

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

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

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

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

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

85/195

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.進(jìn)程通信

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

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

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

Send(P,Msg):

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

Receive(P,Msg):

接收來(lái)自P進(jìn)程的一個(gè)消息，Msg為接收區(qū)首地址

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

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

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

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

R1和P2占用了

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

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

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

產(chǎn)生死鎖的原因?yàn)棰傧到y(tǒng)資源不足。②進(jìn)程推進(jìn)的順序不當(dāng)。

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

破壞條件①較難實(shí)現(xiàn)，因?yàn)橛行┫到y(tǒng)資源的性質(zhì)是非共享的，但可以采用假脫機(jī)技術(shù)將非共享設(shè)備變成共享設(shè)備來(lái)實(shí)現(xiàn)。

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

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

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

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

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

3.銀行根據(jù)當(dāng)時(shí)的資金情況，可能立即滿(mǎn)足用戶(hù)申請(qǐng)，或需要用戶(hù)等待一段有限時(shí)間。

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

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

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

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

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

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

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

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

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

～Pi為程序段。

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

P2

為矩陣求逆，P3為相加運(yùn)算。

P1、

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

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

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

CPU啟動(dòng)外設(shè)后要不斷詢(xún)問(wèn)外設(shè)的忙閑，當(dāng)外設(shè)為“忙”時(shí)，CPU不斷對(duì)它進(jìn)行測(cè)試，直到外設(shè)為“閑”時(shí)進(jìn)行輸入輸出。在此期間CPU不能進(jìn)行其它操作。

⑵程序中斷I/O方式：

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

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

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

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

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

1

611

7em12

4out

2

53

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