電腦操作系統知識2/195本章主要內容1

概述2

存儲管理3

處理器管理4

設備管理5

文件管理6

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

操作系統的定義

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

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

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

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

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

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

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

16/1953.2存儲管理3.2.1

存儲管理的功能及有關概念3.2.2

實存儲管理3.2.3

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

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

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

靜態重定位：把作業在裝入時就進行的地址轉換方式。2）地址轉換或重定位：x’=x+D

物理地址邏輯地址下界地址—內存中的起始地址

動態重定位：在程序執行過程中進行，當CPU訪問內存指令時由動態變換機構自動進行地址轉換。23/195

3)存儲保護：

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

＜L，如果出現x’

不滿足上述條件，則系統立即發出越界錯誤，發出中斷，停止當前執行的程序，轉去執行錯誤處理程序。關于動態重定位系統的存儲保護將結合有關的存儲方式來討論24/1954)內存擴充：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基本概念：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2328501000

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

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

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

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

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

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

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

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

主存空間頁架號01234567

1

0

3

0

1

1

2

5

狀態頁號頁架號PMT0

1

0

6

1

1

7

0

2

0

3

5PMT3

1

0

0

1

s

p

d邏輯地址SMT

L

b段表地址器存器頁表長度頁表起始地址狀態

p’

d物理地址70（3）段頁式管理的優缺點優點:

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

多道程序設計基礎—并行程序設計72/1953.3.1基本概念與術語

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

基本概念與術語作業和進程

特權指令、處理器狀態

處理器管理73/195

★作業和進程⑴作業、作業步

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

75/195⑵進程和程序

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

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

1.特權指令：只能由操作系統使用。

2.非特權指令：供一般用戶使用。對應兩種不同的指令，處理器有兩種執行狀態。管態：又稱主態、執行狀態,此時處理器執行特權指令。目態：又稱算態、題目狀態，此時處理器處于用戶執行狀態。77/195★處理器管理

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

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

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

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

優先數=(等待時間)2

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

3.作業調度算法

85/195

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

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

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

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

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

進程調度的核心是采用某種算法動態的把處理器分配給就緒隊列中的某個進程。進程調度算法與作業調度算法有很多相似處。（1）優先數法：把處理器分配給具有最高優先數的進程。（2）輪轉調度法：適用于多道批處理系統。按照規定的時間片將處理器輪流分配給就緒隊列中的進程。94/195（3）分級調度法：

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

（1）同步與互斥現象

“同步”是指兩個事件的發生存在某種時序上的關系，如果系統中有若干個進程要共同完成某一任務，那么它們相互之間必須協調配合，這就需要有一種工具使它們同步運行。

“互斥”是進程間的一種關系。當多個進程要求共享系統中某些硬件或軟件資源，而這些資源卻又要求排它性使用時，往往引起由于多個進程競爭同一資源使運行結果出現問題。6.3.4多道程序并發運行出現的問題96/195Count中只增加1進程的同步與互斥（1）同步與互斥現象例如：有兩個進程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)解決進程同步與互斥的工具

解決同步與互斥的工具有很多，可以由硬件或軟件實現。下面介紹一種用同步原語對某信號量進行操作以實現同步與互斥的方法，通常稱為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操作實現進程互斥在上述例子中，如果在進程P1,P2中加入P-V操作，可以實現對公用變量count的互斥使用。其中P(s),V(s)之間的程序段稱為臨界區。P1…P(s)R1←count臨R1←R1+1界Count←R1區V(s)…P2…P(s)R2←count臨R2←R2+1界Count←R2區V(s)…s=s-1=0設初值s=1s=s+1=0s=s-1=-1<0,p2插入到阻塞隊列Q,直到p1執行完臨界區和v(s)操作后，使s=0才可能激活p2.100/195

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

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

2.進程通信

由于一個作業可以被分解成多個進程并行執行，因此進程間應保持聯系，這種聯系通常表現為進程之間需要交換一定量的信息，稱為進程通信。（1）直接通信

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

消息長度（size）消息正文（text）消息頭103/195系統提供發送和接收原語：

Send(P,Msg):

向P進程發送一個消息，Msg為發送區首地址

Receive(P,Msg):

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

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

這是一種間接通信方式。進程間通信的消息以信件方式存放在信箱內。當兩個進程要進行通信時，由發送方創建一個鏈接兩個進程的信箱，信箱的結構分為信箱頭和正文，要進行通信時只需把信件投入信箱，接受進程可在任何時候取走。信箱通信的原語形式為

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

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

R1和P2占用了

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

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

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

產生死鎖的原因為①系統資源不足。②進程推進的順序不當。

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

破壞條件①較難實現，因為有些系統資源的性質是非共享的，但可以采用假脫機技術將非共享設備變成共享設備來實現。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

119/195SFP1P2Pi3.3.5多道程序設計基礎—并行程序設計 多道環境下的程序設計稱為并行程序設計，而傳統的程序設計稱為順序程序設計。

順序程序設計：執行完一條指令再執行一條指令。順序程序設計的工作流程如下圖所示。其中S為起始，F為結束，P1

～Pi為程序段。

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

P2

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

P1、

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

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

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

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

⑵程序中斷I/O方式：

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

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

⑴單緩沖區和雙緩沖區：

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

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

1

611

7em12

4out

2

53

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