操作系統(tǒng)課件

第1章操作系統(tǒng)概述

計(jì)算機(jī)是人類社會(huì)20世紀(jì)最偉大的創(chuàng)造之一，自1946年誕生第一臺(tái)計(jì)算機(jī)至今的短短50多年中，其技術(shù)得到了突飛猛進(jìn)的發(fā)展。目前它不僅被廣泛應(yīng)用于科學(xué)計(jì)算、過(guò)程控制、數(shù)據(jù)處理以及軍事技術(shù)等領(lǐng)域，而且也滲透到辦公、教育和家庭等方方面面，已成為社會(huì)信息化的重要支柱和人類文明高度發(fā)展的象征。 本章將講述以下三方面的內(nèi)容： （1）介紹作為現(xiàn)今計(jì)算機(jī)必備的系統(tǒng)軟件——操作系統(tǒng)的形成過(guò)程。 （2）介紹操作系統(tǒng)的四大功能。 （3）簡(jiǎn)述四類基本操作系統(tǒng)。退出1.1計(jì)算機(jī)系統(tǒng)1.2操作系統(tǒng)的定義與功能1.3操作系統(tǒng)的種類1.1計(jì)算機(jī)系統(tǒng)1.1.1硬件與軟件 計(jì)算機(jī)由硬件系統(tǒng)和軟件系統(tǒng)兩個(gè)部分組成，它們構(gòu)成了一個(gè)完整的計(jì)算機(jī)系統(tǒng)。 計(jì)算機(jī)硬件是各種物理設(shè)備的總稱，是完成工作任務(wù)的物質(zhì)基礎(chǔ)。按功能分，可以把硬件劃分成五大塊：運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備以及輸出設(shè)備，其中運(yùn)算器和控制器常被稱為中央處理機(jī)（CPU），如圖1-1所示。其中的實(shí)線代表控制信號(hào)，細(xì)虛線代表數(shù)據(jù)傳輸。

計(jì)算機(jī)軟件是指程序和與程序相關(guān)的文檔的集合，是計(jì)算機(jī)系統(tǒng)的重要組成部分。按功能劃分，軟件可分為系統(tǒng)軟件和應(yīng)用軟件兩種。系統(tǒng)軟件是指由計(jì)算機(jī)生產(chǎn)廠家提供、具有通用功能的那些軟件，比如：操作系統(tǒng)、語(yǔ)言處理程序（如C語(yǔ)言編譯程序）、數(shù)據(jù)庫(kù)管理系統(tǒng)以及各種完成服務(wù)功能的程序。應(yīng)用軟件是指為解決實(shí)際問(wèn)題而研制的那些軟件，它涉及計(jì)算機(jī)應(yīng)用的各個(gè)領(lǐng)域，比如：各種管理軟件、用于工程計(jì)算的軟件包，輔助設(shè)計(jì)軟件以及過(guò)程控制軟件等。1.1.2操作系統(tǒng)的形成 通常，把未配置任何軟件的計(jì)算機(jī)稱為“裸機(jī)”。如果讓用戶直接面對(duì)裸機(jī)，事事都深入到計(jì)算機(jī)的硬件里面去，那么他們的精力就絕對(duì)不可能集中在如何用計(jì)算機(jī)解決自己的實(shí)際問(wèn)題上，計(jì)算機(jī)本身的效率也不可能充分發(fā)揮出來(lái)。 舉例說(shuō)，要在一臺(tái)PC機(jī)上進(jìn)行硬盤讀操作，使用者至少應(yīng)該把磁盤地址、內(nèi)存地址、字節(jié)數(shù)和操作類型（讀/寫）等具體值裝入到特定的硬件寄存器中，否則根本談不上完成預(yù)定的輸入/輸出任務(wù)。實(shí)際上，對(duì)許多I/O設(shè)備而言，除此以外往往會(huì)要求比這更多的操作參數(shù)。在輸入/輸出結(jié)束后，還需要對(duì)設(shè)備返回的諸多狀態(tài)加以判別。

又例如，某計(jì)算機(jī)內(nèi)存儲(chǔ)器可供用戶使用的容量為576KB。若現(xiàn)在裝入的用戶程序占用其中的360KB，那么余下的216KB被閑置了。想象一下，如果能夠在內(nèi)存中裝入多個(gè)程序，比如在216KB中再裝一道需要存儲(chǔ)量116KB的程序進(jìn)去，當(dāng)?shù)谝粋€(gè)程序等待輸入/輸出完成而暫時(shí)不用CPU時(shí)，能讓第二道程序投入運(yùn)行，那么，整個(gè)計(jì)算機(jī)系統(tǒng)的利用率就會(huì)比原來(lái)的大為提高。理由是： （1）內(nèi)存浪費(fèi)得少了，原來(lái)浪費(fèi)216KB，現(xiàn)在只浪費(fèi)100KB；

（2）CPU比原來(lái)更加忙碌了，在第一個(gè)程序等待輸入/輸出完成時(shí)，原來(lái)CPU只能夠采取空轉(zhuǎn)的方式來(lái)等待，現(xiàn)在可以讓它去執(zhí)行第二個(gè)程序； （3）在CPU執(zhí)行第二個(gè)程序時(shí)，它與第一個(gè)程序啟動(dòng)的輸入/輸出設(shè)備呈現(xiàn)并行工作的態(tài)勢(shì)。 可見，為了從復(fù)雜的硬件控制中脫出身來(lái)，為了能合理有效地使用計(jì)算機(jī)系統(tǒng)，為了能給用戶使用計(jì)算機(jī)提供必要的方便，最好的解決辦法就是要開發(fā)一種軟件，通過(guò)它來(lái)管理整個(gè)系統(tǒng)，發(fā)揮系統(tǒng)的潛在能力，達(dá)到擴(kuò)展系統(tǒng)功能、方便用戶使用的目的。實(shí)際應(yīng)用的需要，就是“操作系統(tǒng)”這一軟件呼之欲出的根本原因。

第一臺(tái)電子管計(jì)算機(jī)出現(xiàn)后的若干年（1946~1958），計(jì)算機(jī)上并沒(méi)有名為“操作系統(tǒng)”的這種軟件。那時(shí)計(jì)算機(jī)的運(yùn)行速度慢，外部設(shè)備少，因此程序的裝入、調(diào)試以及控制程序的運(yùn)行等工作，全部由上機(jī)的人員自己通過(guò)按動(dòng)控制臺(tái)上的一排排開關(guān)和按鈕來(lái)實(shí)現(xiàn)。這一時(shí)代的特點(diǎn)是人工完成上、下機(jī)操作的，一臺(tái)計(jì)算機(jī)被一個(gè)用戶所獨(dú)占。 1958年，計(jì)算機(jī)進(jìn)入了晶體管時(shí)代（1958~1964）。這時(shí)計(jì)算機(jī)的速度、存儲(chǔ)容量、外部設(shè)備的功能和種類等都有了很大的發(fā)展，慢速的人工操作與快速的計(jì)算機(jī)處理能力之間顯得很不協(xié)調(diào)，出現(xiàn)了所謂的“人–機(jī)矛盾”。例如，有一道程序通過(guò)3min的安裝等手工操作后，在運(yùn)算速度為1萬(wàn)次/秒的計(jì)算機(jī)上用1h得到了結(jié)果。這時(shí)手工操作與程序運(yùn)行時(shí)間之比為1：20。把這道程序拿到第二代速度為60萬(wàn)次/秒的機(jī)器上運(yùn)行，它只需花費(fèi)CPU時(shí)間1min即可得到結(jié)果。如果在這種高速的機(jī)器上仍然堅(jiān)持手工操作，那么這時(shí)手工操作與程序運(yùn)行時(shí)間之比為3：1。這種比例是難以讓人接受的。

正是這種“人-機(jī)矛盾”，向軟件設(shè)計(jì)人員提出了“讓計(jì)算機(jī)自動(dòng)控制用戶作業(yè)的運(yùn)行，廢除上、下機(jī)手工交接”的要求。為了達(dá)到這個(gè)目的，需要用戶一方在編寫自己程序時(shí)，還要編寫“作業(yè)說(shuō)明書”，詳細(xì)規(guī)定程序運(yùn)行的步驟，并將其與程序、數(shù)據(jù)一起提交給系統(tǒng)；而系統(tǒng)一方需要設(shè)計(jì)一個(gè)“管理程序”（也稱監(jiān)督程序），它的功能是從磁盤上讀入第一個(gè)作業(yè)的作業(yè)說(shuō)明書，按照它的規(guī)定控制該作業(yè)執(zhí)行。這個(gè)作業(yè)運(yùn)行結(jié)束后，它又從磁盤上讀入第二個(gè)作業(yè)的作業(yè)說(shuō)明書，繼而執(zhí)行之。這一過(guò)程一直進(jìn)行到提交給系統(tǒng)的一批作業(yè)全部執(zhí)行完畢時(shí)為止，如圖1-2所示。由于這種系統(tǒng)一次集中處理一批用戶作業(yè)，故被稱為“批處理系統(tǒng)”，其管理程序就是現(xiàn)今操作系統(tǒng)的雛形。這個(gè)時(shí)代的特點(diǎn)是對(duì)一批作業(yè)自動(dòng)進(jìn)行處理，沒(méi)有人工交接，在一個(gè)用戶作業(yè)運(yùn)行時(shí)，仍獨(dú)占計(jì)算機(jī)。 1964年以后，計(jì)算機(jī)進(jìn)入了集成電路和大規(guī)模集成電路時(shí)代。這時(shí)，硬件又有了長(zhǎng)足的發(fā)展，中斷和通道技術(shù)的出現(xiàn)，為輸入/輸出設(shè)備和中央處理機(jī)并行操作奠定了物質(zhì)基礎(chǔ)。另外，隨著計(jì)算機(jī)應(yīng)用的日益廣泛，也要求進(jìn)一步發(fā)展和擴(kuò)大管理程序的功能，希望它能夠最大限度地挖掘計(jì)算機(jī)系統(tǒng)本身的潛在能力。這時(shí)，人們開始把CPU、存儲(chǔ)器、外部設(shè)備以及各種軟件都視為計(jì)算機(jī)系統(tǒng)的“資源”，提出不僅要合理地使用這些資源，而且要高效地使用這些資源。為此，在軟件設(shè)計(jì)上提出了“多道程序設(shè)計(jì)”的技術(shù)，即在計(jì)算機(jī)內(nèi)存中同時(shí)存放幾道相互獨(dú)立的程序，讓它們?nèi)ァ肮蚕怼?、去“?jìng)爭(zhēng)”系統(tǒng)中的這些資源，使系統(tǒng)中的各種資源盡可能地滿負(fù)荷工作，從而提高整個(gè)計(jì)算機(jī)系統(tǒng)的使用效率。具有這種功能的軟件就是“操作系統(tǒng)”。

操作系統(tǒng)可以被看作是計(jì)算機(jī)系統(tǒng)的核心，統(tǒng)管整個(gè)系統(tǒng)的所有資源，制定各種資源的分配策略，調(diào)度系統(tǒng)中運(yùn)行的用戶程序，協(xié)調(diào)它們對(duì)資源的需求，從而使整個(gè)系統(tǒng)在高效、有序的環(huán)境里工作。1.2操作系統(tǒng)的定義與功能1.2.1操作系統(tǒng)的定義 如圖1-3所示，操作系統(tǒng)是在裸機(jī)上加載的第一層軟件，是對(duì)計(jì)算機(jī)硬件系統(tǒng)功能的首次擴(kuò)充。從用戶的角度看，計(jì)算機(jī)系統(tǒng)配置了操作系統(tǒng)后，由于操作系統(tǒng)隱蔽了硬件的復(fù)雜細(xì)節(jié)，用戶會(huì)感到機(jī)器使用起來(lái)更簡(jiǎn)單、更容易了。通常就說(shuō)操作系統(tǒng)為用戶提供了一臺(tái)功能經(jīng)過(guò)擴(kuò)展了的機(jī)器，或“虛擬機(jī)”，因?yàn)楝F(xiàn)實(shí)生活中并不存在具有這種功能的真實(shí)機(jī)器，它只是用戶的一種感覺而已。從計(jì)算機(jī)系統(tǒng)的角度看，由于操作系統(tǒng)的組織與管理，系統(tǒng)中的各種硬、軟件資源得到了更有效的利用，機(jī)器的工作流程更為合理與協(xié)調(diào)。因此，操作系統(tǒng)是現(xiàn)今計(jì)算機(jī)系統(tǒng)中不可缺少的一個(gè)系統(tǒng)軟件。

至此，我們可以把操作系統(tǒng)定義為：“操作系統(tǒng)是控制和管理計(jì)算機(jī)硬件和軟件資源、合理地組織計(jì)算機(jī)工作流程以及方便用戶使用計(jì)算機(jī)的一個(gè)大型程序”。1.2.2操作系統(tǒng)的功能 從資源管理的角度看，操作系統(tǒng)應(yīng)該具有五個(gè)方面的功能：處理機(jī)管理、存儲(chǔ)管理、設(shè)備管理、文件管理以及作業(yè)管理。這五大部分相互配合，協(xié)同工作，實(shí)現(xiàn)對(duì)計(jì)算機(jī)系統(tǒng)的資源管理和控制程序的執(zhí)行。本書將處理機(jī)管理與作業(yè)管理合并在一起講述。下面就分四個(gè)方面對(duì)操作系統(tǒng)的功能做一個(gè)簡(jiǎn)略的說(shuō)明。

1．處理機(jī)管理2．存儲(chǔ)管理3．設(shè)備管理4．文件管理1.3操作系統(tǒng)的種類 1.3.1批處理操作系統(tǒng) 在單道批處理操作系統(tǒng)的控制和管理下，計(jì)算機(jī)系統(tǒng)的工作過(guò)程如下： 用戶為自己的作業(yè)編寫程序和準(zhǔn)備數(shù)據(jù)，同時(shí)編寫控制作業(yè)運(yùn)行的作業(yè)說(shuō)明書。然后將它們一并交給操作員。 （1）操作員將收到的一批作業(yè)信息存入輔助存儲(chǔ)器中等待處理。

（2）單道批處理操作系統(tǒng)從輔助存儲(chǔ)器中依次選擇作業(yè)，按其作業(yè)說(shuō)明書的規(guī)定自動(dòng)控制它的運(yùn)行，并將運(yùn)行結(jié)果存入輔助存儲(chǔ)器。 （3）操作員將該批作業(yè)的運(yùn)行結(jié)果打印輸出，并分發(fā)給用戶。 單道批處理操作系統(tǒng)有如下特點(diǎn)： （1）單路性：每次只允許一個(gè)用戶程序進(jìn)入內(nèi)存。 （2）獨(dú)占性：整個(gè)系統(tǒng)資源被進(jìn)入內(nèi)存的一個(gè)程序獨(dú)占使用，因此資源利用率不高。

（3）自動(dòng)性：作業(yè)一個(gè)一個(gè)地自動(dòng)接受處理，期間任何用戶不得對(duì)系統(tǒng)的工作進(jìn)行干預(yù)。由于沒(méi)有了作業(yè)上、下機(jī)時(shí)用戶手工操作耗費(fèi)的時(shí)間，因此提高了系統(tǒng)的吞吐量。 （4）封閉性：在一批作業(yè)處理過(guò)程中，用戶不得干預(yù)系統(tǒng)的工作。即便是某個(gè)程序執(zhí)行中出現(xiàn)一個(gè)很小的錯(cuò)誤，也只能等到這一批作業(yè)全部處理完畢后，才能進(jìn)行修改，這給用戶帶來(lái)不便。

在單道批處理的基礎(chǔ)上，引入多道程序設(shè)計(jì)技術(shù)，就產(chǎn)生了多道批處理操作系統(tǒng)。配置多道批處理操作系統(tǒng)的本質(zhì)仍然是批處理。不同的是由于采用了多道程序設(shè)計(jì)技術(shù)，允許若干個(gè)作業(yè)程序同時(shí)裝入內(nèi)存，造成對(duì)系統(tǒng)資源共享與競(jìng)爭(zhēng)的態(tài)勢(shì)。用戶為自己的作業(yè)編寫程序和準(zhǔn)備數(shù)據(jù)，同時(shí)編寫控制作業(yè)運(yùn)行的作業(yè)說(shuō)明書，然后將它們一并交給操作員。其工作過(guò)程如下：

（1）操作員將收到的一批作業(yè)信息存入輔助存儲(chǔ)器中等待處理。 （2）多道批處理操作系統(tǒng)中的作業(yè)調(diào)度程序從輔助存儲(chǔ)器里的該批作業(yè)中選出若干合適的作業(yè)裝入內(nèi)存，使它們不斷地輪流占用CPU來(lái)執(zhí)行，并同時(shí)使用各自所需的外部設(shè)備。若內(nèi)存中有作業(yè)運(yùn)行結(jié)束，則又可從輔助存儲(chǔ)器的后備作業(yè)中選擇對(duì)象裝入內(nèi)存執(zhí)行。

（3）操作員將該批作業(yè)的運(yùn)行結(jié)果打印輸出，分發(fā)給用戶。 多道批處理操作系統(tǒng)有如下特點(diǎn)： （1）多路性：每次允許多個(gè)用戶程序進(jìn)入內(nèi)存，它們輪流交替地使用CPU，提高了內(nèi)存儲(chǔ)器和CPU的利用率。 （2）共享性：整個(gè)系統(tǒng)資源被進(jìn)入內(nèi)存的多個(gè)程序共享使用，因此整個(gè)系統(tǒng)資源的利用率較高。

（3）自動(dòng)性：作業(yè)處理期間任何用戶不得對(duì)系統(tǒng)的工作進(jìn)行干預(yù)。由于沒(méi)有了作業(yè)上、下機(jī)時(shí)用戶手工操作耗費(fèi)的時(shí)間，因此提高了系統(tǒng)的吞吐量。 （4）封閉性：在一批作業(yè)處理過(guò)程中，用戶不得干預(yù)系統(tǒng)的工作。即便是某個(gè)程序執(zhí)行中出現(xiàn)一個(gè)很小的錯(cuò)誤，也只能等到這一批作業(yè)全部處理完畢后，才能進(jìn)行修改，這給用戶帶來(lái)不便。1.3.2分時(shí)操作系統(tǒng) 將多道程序設(shè)計(jì)技術(shù)與分時(shí)技術(shù)結(jié)合在一起，就產(chǎn)生了分時(shí)操作系統(tǒng)。配有分時(shí)操作系統(tǒng)的計(jì)算機(jī)系統(tǒng)稱為分時(shí)系統(tǒng)。 所謂分時(shí)系統(tǒng)，即一臺(tái)計(jì)算機(jī)與多個(gè)終端設(shè)備連接，最簡(jiǎn)單的終端可以由一個(gè)顯示器和一個(gè)鍵盤組成。每個(gè)用戶通過(guò)終端向系統(tǒng)發(fā)出命令，請(qǐng)求系統(tǒng)為其完成某項(xiàng)工作。系統(tǒng)根據(jù)用戶的請(qǐng)求完成指定的任務(wù)，并把執(zhí)行結(jié)果返回。這樣用戶可以根據(jù)運(yùn)行結(jié)果，再次通過(guò)終端向系統(tǒng)提出下一步請(qǐng)求。重復(fù)這種交互會(huì)話過(guò)程，直至每個(gè)用戶實(shí)現(xiàn)自己的預(yù)定目標(biāo)。圖1-4為分時(shí)系統(tǒng)工作過(guò)程的示意圖。

分時(shí)系統(tǒng)之所以能在較短的時(shí)間內(nèi)響應(yīng)用戶的請(qǐng)求，同時(shí)為多個(gè)終端用戶提供服務(wù)，主要是因?yàn)樵诜謺r(shí)操作系統(tǒng)中采用了“時(shí)間片輪轉(zhuǎn)”的處理機(jī)調(diào)度策略。這種調(diào)度策略是把處理機(jī)時(shí)間劃分成一個(gè)個(gè)很短的“時(shí)間片”，對(duì)提出請(qǐng)求的每個(gè)聯(lián)機(jī)用戶終端，系統(tǒng)輪流分配一個(gè)時(shí)間片給其使用。若在一個(gè)時(shí)間片內(nèi)，用戶所請(qǐng)求的工作未能全部做完，就會(huì)被暫時(shí)中斷執(zhí)行，等待下一輪循環(huán)再繼續(xù)做，讓出的CPU被分配給另一個(gè)終端使用。

由于計(jì)算機(jī)的處理速度很快，只要時(shí)間片的間隔取得適當(dāng)，那么用戶就不會(huì)感覺到從一個(gè)時(shí)間片跨越到另一個(gè)時(shí)間片之間的“停頓”，就好像整個(gè)系統(tǒng)全由他“獨(dú)占”使用似的。例如，若時(shí)間片為100ms，系統(tǒng)中有10個(gè)用戶終端分享CPU，并假定忽略操作系統(tǒng)為實(shí)現(xiàn)用戶終端之間的切換所需耗費(fèi)的時(shí)間，那么每個(gè)用戶平均響應(yīng)時(shí)間（即從用完一個(gè)時(shí)間片到獲得下一個(gè)時(shí)間片所需的時(shí)間間隔）為1s。這1s鐘的“停頓”，用戶是完全感覺不出來(lái)的。1.3.3實(shí)時(shí)操作系統(tǒng) 計(jì)算機(jī)應(yīng)用范圍日益擴(kuò)大，比如在控制飛機(jī)飛行、導(dǎo)彈發(fā)射以及冶煉軋鋼等生產(chǎn)過(guò)程中采用了實(shí)時(shí)控制系統(tǒng)，在飛機(jī)訂票、銀行業(yè)務(wù)中采用了實(shí)時(shí)信息處理系統(tǒng)，它們都打破了只把計(jì)算機(jī)用于科學(xué)計(jì)算和數(shù)據(jù)處理等方面的格局。 所謂“實(shí)時(shí)”，是指能夠及時(shí)響應(yīng)隨機(jī)發(fā)生的外部事件、并對(duì)事件做出快速處理的一種能力。而“外部事件”，是指與計(jì)算機(jī)相連接的設(shè)備向計(jì)算機(jī)發(fā)出的各種服務(wù)請(qǐng)求。因此可以把實(shí)時(shí)操作系統(tǒng)說(shuō)成是能對(duì)來(lái)自外部的請(qǐng)求和信號(hào)在限定的時(shí)間范圍內(nèi)做出及時(shí)響應(yīng)的那種操作系統(tǒng)。

圖1-5所示是一個(gè)用計(jì)算機(jī)系統(tǒng)控制化學(xué)生產(chǎn)反應(yīng)的例子。A、B兩種原料通過(guò)閥門進(jìn)入反應(yīng)堆。反應(yīng)堆中的各種傳感裝置周期性地把所測(cè)得的溫度、壓力、濃度等測(cè)量信號(hào)傳送給計(jì)算機(jī)系統(tǒng)。計(jì)算機(jī)中的實(shí)時(shí)操作系統(tǒng)及時(shí)接收這些信號(hào)，并調(diào)用指定的處理程序?qū)@些數(shù)據(jù)進(jìn)行分析，然后給出反饋信號(hào)，控制兩種原料A、B的流量，確保反應(yīng)堆中的諸原料參數(shù)維持在正常范圍之內(nèi)。若參數(shù)超過(guò)極限允許值，就立即發(fā)出報(bào)警，甚至關(guān)閉反應(yīng)堆，以免發(fā)生事故。1.3.4網(wǎng)絡(luò)操作系統(tǒng) 所謂計(jì)算機(jī)網(wǎng)絡(luò)，是指把地理上分散的、具有獨(dú)立功能的多個(gè)計(jì)算機(jī)和終端設(shè)備，通過(guò)通信線路加以連接，以達(dá)到數(shù)據(jù)通信和資源共享目的的一種計(jì)算機(jī)系統(tǒng)。計(jì)算機(jī)網(wǎng)絡(luò)是計(jì)算機(jī)和通信技術(shù)相結(jié)合的產(chǎn)物。 分時(shí)系統(tǒng)提供的資源共享有兩個(gè)限制：一是限于計(jì)算機(jī)系統(tǒng)內(nèi)部；一是限于同一地點(diǎn)（或地理位置很近）。計(jì)算機(jī)網(wǎng)絡(luò)在分時(shí)系統(tǒng)的基礎(chǔ)上，又大大前進(jìn)了一步。

在網(wǎng)絡(luò)范圍內(nèi)，用于管理網(wǎng)絡(luò)通信和共享資源，協(xié)調(diào)各計(jì)算機(jī)上任務(wù)的運(yùn)行，并向用戶提供統(tǒng)一的、有效方便的網(wǎng)絡(luò)接口的程序集合，就稱為網(wǎng)絡(luò)操作系統(tǒng)。要說(shuō)明的是，在網(wǎng)絡(luò)中各獨(dú)立計(jì)算機(jī)仍有自己的操作系統(tǒng)，由它管理著自身的資源。只有在它們要進(jìn)行相互間的信息傳遞、要使用網(wǎng)絡(luò)中的可共享資源時(shí)，才會(huì)涉及到網(wǎng)絡(luò)操作系統(tǒng)。第2章處理機(jī)管理

計(jì)算機(jī)系統(tǒng)中，最寶貴的資源是CPU。為了提高它的利用率，需要引入多道程序設(shè)計(jì)的概念。當(dāng)內(nèi)存儲(chǔ)器中同時(shí)有多個(gè)程序存在時(shí)，如果不對(duì)人們熟悉的“程序”概念加以擴(kuò)充，就無(wú)法刻畫多個(gè)程序共同運(yùn)行時(shí)系統(tǒng)呈現(xiàn)出的特征。因此，在本章將給出操作系統(tǒng)中的重要概念：“進(jìn)程”。它將是在多道程序運(yùn)行環(huán)境下，系統(tǒng)資源分配和獨(dú)立運(yùn)行的基本單位。本章著重講述四個(gè)方面的內(nèi)容：退出（1）進(jìn)程概念的引入；（2）進(jìn)程的組成與管理；（3）處理機(jī)的調(diào)度算法；（4）處理機(jī)的二級(jí)調(diào)度與作業(yè)管理。2.1進(jìn)程2.2進(jìn)程控制塊2.3進(jìn)程的調(diào)度與管理2.4作業(yè)調(diào)度2.1進(jìn)程2.1.1多道程序設(shè)計(jì) 所謂“程序”，是一個(gè)在時(shí)間上嚴(yán)格有序的指令集合。程序規(guī)定了完成某一任務(wù)時(shí)，計(jì)算機(jī)所需做的各種操作，以及這些操作的執(zhí)行順序。在沒(méi)有引入多道程序設(shè)計(jì)的概念之前，只要一提到程序，就表明它獨(dú)占使用系統(tǒng)中的一切資源，如處理機(jī)（指它里面的指令計(jì)數(shù)器、累加器、各種寄存器等）、內(nèi)存儲(chǔ)器、外部設(shè)備以及軟件等，沒(méi)有其他競(jìng)爭(zhēng)者與它爭(zhēng)奪與共享。

在單道程序設(shè)計(jì)環(huán)境下，系統(tǒng)具有如下特點(diǎn)： （1）資源的獨(dú)占性：任何時(shí)候，位于內(nèi)存中的程序可以使用系統(tǒng)中的一切資源，不可能有其他程序與之競(jìng)爭(zhēng)。

（2）執(zhí)行的順序性：由于內(nèi)存中每次只有一個(gè)程序，因此各個(gè)程序是按次序執(zhí)行的，即做完一個(gè)以后，再做下一個(gè)。絕對(duì)不可能出現(xiàn)在一個(gè)程序運(yùn)行過(guò)程中，又夾雜進(jìn)另一個(gè)程序執(zhí)行的現(xiàn)象存在。圖2-1(a)對(duì)程序執(zhí)行的順序性做出了解釋。假定有三個(gè)程序，每個(gè)程序都是前后占用CPU執(zhí)行一段時(shí)間，中間要求打印輸出。具體是：程序A所需時(shí)間為（4，2，3），程序B所需時(shí)間為（5，4，2），程序C所需時(shí)間為（3，3，4）。不難看出，總共需要30個(gè)時(shí)間單位，才能把它們執(zhí)行完畢。從橫坐標(biāo)上看，在時(shí)間區(qū)間（4~6）、（14~18）以及（23~26）中，CPU為了等待打印結(jié)束，在那里空閑等待。

（3）結(jié)果的再現(xiàn)性：只要執(zhí)行環(huán)境和初始條件相同，重復(fù)執(zhí)行一個(gè)程序，獲得的結(jié)果總是一樣的。 在多道程序設(shè)計(jì)環(huán)境下，內(nèi)存中允許有多個(gè)程序存在，它們輪流地使用著CPU。這時(shí)，上述的三個(gè)特點(diǎn)就都蕩然無(wú)存了。 “資源的獨(dú)占性”被打破了。比如，內(nèi)存不再只由一個(gè)程序占用，而是被分配給若干個(gè)程序使用；又比如，原來(lái)內(nèi)存中的程序進(jìn)行輸入/輸出時(shí)，CPU就只能空轉(zhuǎn)，以等待輸入/輸出操作的完成。現(xiàn)在，當(dāng)程序A等待輸入/輸出操作完成時(shí)，就可以把CPU分配給內(nèi)存中的另一個(gè)可運(yùn)行的程序B去使用。這樣，CPU在運(yùn)行程序B，外部設(shè)備在為程序A服務(wù)。圖2-1(b)中的時(shí)間區(qū)間（4~6）正好是這種情況。 “執(zhí)行的順序性”被打破了。從圖2-1(b)中可以看出，時(shí)刻6程序A打印完畢，按說(shuō)應(yīng)該繼續(xù)執(zhí)行，但是CPU已經(jīng)分配給了程序B，因此程序A只能等到時(shí)刻9在程序B請(qǐng)求打印時(shí)，才能重新獲得CPU。這就是說(shuō)，在程序A執(zhí)行過(guò)程時(shí)，夾雜進(jìn)了程序B的執(zhí)行，打破了程序執(zhí)行的順序性，內(nèi)存中多個(gè)程序的執(zhí)行過(guò)程被交織在一起。從宏觀上看，好幾個(gè)程序都在運(yùn)行著（比如，在時(shí)間區(qū)間4~12，程序A和程序B都在做著自己的事情；在時(shí)間區(qū)間12~17，程序B和程序C都在做著自己的事情）；而從微觀上看，每個(gè)時(shí)刻CPU只能為一個(gè)程序服務(wù)，因此運(yùn)行著的程序都是走走停停?？傊?，在多道程序設(shè)計(jì)環(huán)境下，各個(gè)程序的執(zhí)行已經(jīng)不再可能完全依照自己的執(zhí)行次序執(zhí)行了。 “結(jié)果的再現(xiàn)性”被打破了。舉例來(lái)說(shuō)，為了了解某單行道的交通流量，在路口安放一個(gè)監(jiān)視器，功能是有車通過(guò)該路段時(shí)，就向計(jì)算機(jī)發(fā)送一個(gè)信號(hào)。為計(jì)算機(jī)系統(tǒng)設(shè)計(jì)兩個(gè)程序：程序A的功能是接收到監(jiān)視器的信號(hào)時(shí)，就在計(jì)數(shù)單元COUNT上加1；程序B的功能是每隔半小時(shí)，將計(jì)數(shù)單元COUNT的值打印輸出，然后清零。COUNT初始時(shí)為0，兩個(gè)程序的描述如圖2-2所示。

因?yàn)楝F(xiàn)在是多道程序設(shè)計(jì)環(huán)境，程序A和程序B同時(shí)在內(nèi)存。當(dāng)然，內(nèi)存中可能還會(huì)有其他的程序存在。由于執(zhí)行的順序性被打破了，這些程序的執(zhí)行過(guò)程被交織在一起，沒(méi)有任何規(guī)律可循。為了突出，單單挑出程序A和程序B來(lái)研究。在它們之間，不排除會(huì)有這樣的執(zhí)行順序發(fā)生：A1

A2

B1

B2

A1

A2

B3，即在程序B做了B1和B2后，沒(méi)有直接執(zhí)行B3，而是中間插入了程序A的兩個(gè)操作，這就出現(xiàn)了問(wèn)題。

假定系統(tǒng)在發(fā)生這一執(zhí)行順序前，情況一直正常，計(jì)數(shù)器COUNT里的值是9?，F(xiàn)在由A1收到監(jiān)視器發(fā)來(lái)的第10輛車通過(guò)的信息。于是由A2在COUNT上完成加1的操作，使得計(jì)數(shù)器COUNT取值為10。緊接著在B1延遲半小時(shí)后，由B2將COUNT中的10打印輸出。這時(shí)又做A1，它此時(shí)收到的是第11輛車到達(dá)的信息，通過(guò)A2，COUNT里成為11。這時(shí)做B3，把COUNT清零。結(jié)果該系統(tǒng)把第11輛車漏掉了，少計(jì)算了一輛車。要重現(xiàn)這一情況是困難的，因?yàn)闊o(wú)法清楚何時(shí)會(huì)出現(xiàn)這種執(zhí)行順序，這恰好說(shuō)明了結(jié)果再現(xiàn)性的不復(fù)存在。2.1.2進(jìn)程的定義 “進(jìn)程（Process）”是現(xiàn)代操作系統(tǒng)設(shè)計(jì)中的一個(gè)基本概念，也是一個(gè)管理實(shí)體。它最早被用于美國(guó)麻省理工學(xué)院的MULTICS系統(tǒng)和IBM的CTSS/360系統(tǒng)，不過(guò)那里稱其為“任務(wù)（Task）”，其實(shí)是兩個(gè)等同的概念。

由于要通過(guò)進(jìn)程概念來(lái)描述多道程序設(shè)計(jì)系統(tǒng)中程序的并發(fā)活動(dòng)，程序?qū)Y源的共享和競(jìng)爭(zhēng)，而這一切又千變?nèi)f化，具有極大的復(fù)雜性。因此迄今為止對(duì)這一概念還沒(méi)有非常確切和統(tǒng)一的描述。有的人稱“進(jìn)程是任何一個(gè)處于執(zhí)行的程序”；有的人稱“進(jìn)程是可以并行執(zhí)行的計(jì)算部分”；有的人稱“進(jìn)程是具有一定獨(dú)立功能的程序在某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)”；也有的人稱“進(jìn)程是一個(gè)實(shí)體。當(dāng)它執(zhí)行一個(gè)任務(wù)時(shí)，將要分配和釋放各種資源”。綜合起來(lái)看，可以從如下3個(gè)方面來(lái)描述進(jìn)程：

（1）進(jìn)程是程序的一次運(yùn)行活動(dòng)。 （2）進(jìn)程的運(yùn)行活動(dòng)是建立在某個(gè)數(shù)據(jù)集合之上的。 （3）進(jìn)程要在獲得資源的基礎(chǔ)上從事自己的運(yùn)行活動(dòng)。2.1.3進(jìn)程的特征 由于進(jìn)程是程序的一次執(zhí)行過(guò)程，因此程序是進(jìn)程賴以存在的基礎(chǔ)。沒(méi)有程序，猶如無(wú)米之炊，是根本談不上進(jìn)程的。這就是說(shuō)，進(jìn)程與程序之間有一種必然的聯(lián)系，但進(jìn)程又不等同于程序，它們是兩個(gè)完全不同的概念。進(jìn)程的主要特征以及與程序的區(qū)別有如下幾個(gè)方面。

（1）“進(jìn)程”是一個(gè)動(dòng)態(tài)的概念。既然進(jìn)程強(qiáng)調(diào)的是程序的一次“執(zhí)行”過(guò)程，所以它是一個(gè)動(dòng)態(tài)的概念；程序是一組有序指令的集合，在多道程序設(shè)計(jì)環(huán)境下，它不涉及“執(zhí)行”，因此是一個(gè)靜態(tài)的概念。可以這么來(lái)理解，一套電影拷貝相當(dāng)于一個(gè)程序，它可以長(zhǎng)期保存；該拷貝在電影院的一次放映，就相當(dāng)于一個(gè)進(jìn)程。

（2）不同進(jìn)程可以執(zhí)行同一個(gè)程序。從進(jìn)程的定義可知，區(qū)分進(jìn)程的條件一是所執(zhí)行的程序，二是數(shù)據(jù)集合，因此，即使多個(gè)進(jìn)程執(zhí)行同一個(gè)程序，只要它們運(yùn)行在不同的數(shù)據(jù)集合上，那么它們就是不同的進(jìn)程。例如，一個(gè)編譯程序同時(shí)被多個(gè)用戶調(diào)用，各個(gè)用戶程序的源程序是編譯程序的處理對(duì)象（即數(shù)據(jù)集合）。于是系統(tǒng)中形成了一個(gè)個(gè)不同的進(jìn)程，它們都運(yùn)行編譯程序，只是每個(gè)加工的對(duì)象不同。由此可知，進(jìn)程與程序之間，不存在一一對(duì)應(yīng)的關(guān)系。

（3）每一個(gè)進(jìn)程都有自己的生命期。既然進(jìn)程的本質(zhì)是程序的一次執(zhí)行過(guò)程，因此當(dāng)系統(tǒng)要完成某一項(xiàng)工作時(shí)，它就“創(chuàng)建”一個(gè)進(jìn)程，以便能去執(zhí)行事先編寫好的、完成該工作的那段程序。程序執(zhí)行完畢，完成了預(yù)定的任務(wù)后，系統(tǒng)就“撤消”這個(gè)進(jìn)程，收回它所占用的資源。一個(gè)進(jìn)程創(chuàng)建后，系統(tǒng)就感知到它的存在；一個(gè)進(jìn)程撤消后，系統(tǒng)就無(wú)法再感知到它。于是，從創(chuàng)建到撤消，這個(gè)時(shí)間段就是一個(gè)進(jìn)程的“生命期”。

（4）進(jìn)程之間具有并發(fā)性。在一個(gè)系統(tǒng)中，同時(shí)會(huì)存在多個(gè)進(jìn)程。于是與它們對(duì)應(yīng)的多個(gè)程序同時(shí)在系統(tǒng)中運(yùn)行，輪流占用CPU和各種資源。這正是多道程序設(shè)計(jì)的初衷，說(shuō)明這些進(jìn)程在系統(tǒng)中并發(fā)執(zhí)行著。 （5）進(jìn)程間會(huì)相互制約。由于進(jìn)程是系統(tǒng)中資源分配和運(yùn)行調(diào)度的單位，因此在對(duì)資源共享和競(jìng)爭(zhēng)中，必然會(huì)相互制約，影響了各自向前推進(jìn)的速度。2.1.4進(jìn)程的基本狀態(tài) 進(jìn)程間由于共同協(xié)作和共享資源，導(dǎo)致生命期中的狀態(tài)不斷發(fā)生變化。比如一個(gè)進(jìn)程在等待輸入/輸出的完成，這時(shí)它不能繼續(xù)運(yùn)行。另一種情形是一個(gè)進(jìn)程是可以運(yùn)行的，但由于操作系統(tǒng)把處理機(jī)分配給了別的進(jìn)程使用，于是它也只能處于等待。只有當(dāng)前占有CPU的進(jìn)程，才真正在處于運(yùn)行。 于是，進(jìn)程在其生命期內(nèi)，可以處于下面3種基本狀態(tài)之一。

（1）運(yùn)行狀態(tài)：獲得CPU的進(jìn)程處于此狀態(tài)，其對(duì)應(yīng)的程序正在處理機(jī)上運(yùn)行著。 （2）阻塞狀態(tài)：進(jìn)程為了等待某種外部事件的發(fā)生（如等待輸入/輸出操作的完成，等待另一個(gè)進(jìn)程發(fā)來(lái)消息），暫時(shí)無(wú)法運(yùn)行。阻塞狀態(tài)也稱等待狀態(tài)或掛起狀態(tài)。 （3）就緒狀態(tài)：已具備運(yùn)行所需的一切條件，只是由于別的進(jìn)程占用處理機(jī)而暫時(shí)無(wú)法運(yùn)行。

一個(gè)進(jìn)程的狀態(tài)，可以隨著自身的推進(jìn)和外界環(huán)境的變化而變化，從而使其從一種狀態(tài)變遷到另一種狀態(tài)。圖2-3是進(jìn)程狀態(tài)變遷圖，箭頭表示的是狀態(tài)變遷的方向，旁邊標(biāo)識(shí)的文字是引起這種狀態(tài)變遷的原因。 從圖2-3看出，一個(gè)正處于運(yùn)行狀態(tài)的進(jìn)程，比如會(huì)由于提出輸入/輸出請(qǐng)求而使自己的狀態(tài)變成為阻塞。由于這是進(jìn)程自己提出的請(qǐng)求，“知道”到這里就會(huì)阻塞，以便等待輸入/輸出的完成，所以這屬于進(jìn)程自身推進(jìn)過(guò)程中引起的狀態(tài)變化。在輸入/輸出操作完成后，會(huì)使某個(gè)進(jìn)程的狀態(tài)由阻塞變?yōu)榫途w。由于被阻塞的進(jìn)程并不知道它的輸入/輸出請(qǐng)求何時(shí)能夠完成，因此這屬于由于外界環(huán)境的變化而引起的狀態(tài)變化。

處于就緒狀態(tài)與阻塞狀態(tài)的進(jìn)程，雖然都“暫時(shí)無(wú)法運(yùn)行”，但兩者有著本質(zhì)上的區(qū)別。前者已做好了運(yùn)行的準(zhǔn)備，只要獲得CPU就可以投入運(yùn)行；而后者要等待某事件（比如輸入/輸出）完成后才能繼續(xù)運(yùn)行，因此即使此時(shí)把CPU分配給它，它也無(wú)法運(yùn)行。2.2進(jìn)程控制塊2.2.1進(jìn)程的三個(gè)組成部分 一個(gè)進(jìn)程創(chuàng)建后，需要有自己對(duì)應(yīng)的程序以及該程序運(yùn)行時(shí)所需的數(shù)據(jù)，這是不言而喻的。但僅有程序和數(shù)據(jù)還不行，我們知道，進(jìn)程在其生命期內(nèi)是走走停停，停停走走的，暫時(shí)停下來(lái)以后，至少應(yīng)該要有一個(gè)屬于它專用的地方，來(lái)記錄它暫停時(shí)的運(yùn)行現(xiàn)場(chǎng)。否則，它再次被投入運(yùn)行時(shí)，就無(wú)法從上次被打斷的地方繼續(xù)運(yùn)行下去。

因此，為了管理和控制進(jìn)程，系統(tǒng)在創(chuàng)建每一個(gè)進(jìn)程時(shí)，都為其開辟一個(gè)專用的存儲(chǔ)區(qū)，用以隨時(shí)記錄它在系統(tǒng)中的動(dòng)態(tài)特性。而當(dāng)一個(gè)進(jìn)程被撤消時(shí)，系統(tǒng)就收回分配給它的存儲(chǔ)區(qū)。通常，把這一存儲(chǔ)區(qū)稱為該進(jìn)程的“進(jìn)程控制塊”PCB（ProcessControlBlock）。 由于PCB是隨著進(jìn)程的創(chuàng)建而建立，隨著進(jìn)程的撤消而取消的，因此系統(tǒng)是通過(guò)PCB來(lái)“感知”一個(gè)個(gè)進(jìn)程的，PCB是進(jìn)程存在的唯一標(biāo)志。

這樣，在計(jì)算機(jī)系統(tǒng)內(nèi)部，一個(gè)進(jìn)程要由3個(gè)部分組成：程序、數(shù)據(jù)集合以及進(jìn)程控制塊PCB。圖2-4表示了進(jìn)程3個(gè)組成部分的可能關(guān)聯(lián)情形。其中圖2-4(a)表示程序和數(shù)據(jù)集合存放在一個(gè)連續(xù)存儲(chǔ)區(qū)的情形；圖2-4(b)表示程序和數(shù)據(jù)集合在不連續(xù)存儲(chǔ)區(qū)的情形；圖2-4(c)表示同一個(gè)程序運(yùn)行在不同數(shù)據(jù)集合上時(shí)，形成兩個(gè)進(jìn)程的情形。2.2.2進(jìn)程控制塊（PCB）的內(nèi)容 隨操作系統(tǒng)的不同，PCB的格式、大小以及內(nèi)容也不盡相同。一般地，在PCB中大致應(yīng)包含如圖2-5所示的4方面的信息。

表2-1是實(shí)時(shí)操作系統(tǒng)RTOS中PCB的具體構(gòu)成，每個(gè)PCB占用22個(gè)字節(jié)的存儲(chǔ)區(qū)，兩個(gè)字節(jié)為一個(gè)字，各字的內(nèi)容和作用如下：

（1）TPC：隨時(shí)記錄該進(jìn)程所對(duì)應(yīng)的程序執(zhí)行地址。最初它是程序的入口地址，隨后是進(jìn)程暫停時(shí)的斷點(diǎn)地址。 （2）TAC0~TAC3：該操作系統(tǒng)運(yùn)行的主機(jī)共有4個(gè)工作寄存器AC0~AC3。進(jìn)程程序暫停執(zhí)行時(shí)，就將工作寄存器的當(dāng)前內(nèi)容保存在此，所以這4個(gè)字加上TPC就構(gòu)成了進(jìn)程PCB中的現(xiàn)場(chǎng)保護(hù)區(qū)。 （3）TPRST：記錄該進(jìn)程運(yùn)行過(guò)程中的狀態(tài)變化和進(jìn)程的優(yōu)先數(shù)。

（4）TDELAY：當(dāng)要主動(dòng)讓進(jìn)程推遲一段時(shí)間再執(zhí)行時(shí)，在此存放所需要延遲的時(shí)間間隔。 （5）TLNK：這是PCB的隊(duì)列指針，里面總是存放隊(duì)列中下一個(gè)進(jìn)程的PCB地址。若該P(yáng)CB位于隊(duì)列尾，則TLNK=-1。 （6）TUSP：該進(jìn)程專用的堆棧指針，是進(jìn)程程序運(yùn)行時(shí)的工作區(qū)。 （7）TELN：若本PCB不夠使用時(shí)，可以開辟一個(gè)PCB擴(kuò)展區(qū)，并用這個(gè)指針指向擴(kuò)展區(qū)的起始地址。 （8）TID：進(jìn)程的標(biāo)識(shí)，也就是該進(jìn)程的名。2.2.3進(jìn)程控制塊隊(duì)列 在多道程序設(shè)計(jì)環(huán)境里，同時(shí)會(huì)創(chuàng)建多個(gè)進(jìn)程。當(dāng)計(jì)算機(jī)系統(tǒng)只有一個(gè)CPU時(shí)，每次只能讓一個(gè)進(jìn)程運(yùn)行，其他的進(jìn)程或處于就緒狀態(tài)，或處于阻塞狀態(tài)。為了對(duì)這些進(jìn)程進(jìn)行管理，操作系統(tǒng)要做三件事。 （1）把處于相同狀態(tài)的進(jìn)程的PCB，通過(guò)各自的隊(duì)列指針鏈接在一起，形成一個(gè)個(gè)隊(duì)列。

（2）為每一個(gè)隊(duì)列設(shè)立一個(gè)隊(duì)列頭指針，它總是指向排在隊(duì)列之首的進(jìn)程的PCB。 （3）排在隊(duì)尾的進(jìn)程的PCB，它的“隊(duì)列指針”項(xiàng)內(nèi)容應(yīng)該為“-1”，或一個(gè)特殊的符號(hào)，以表示這是該隊(duì)的隊(duì)尾PCB。

在單CPU系統(tǒng)，任何時(shí)刻系統(tǒng)中都只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)，因此運(yùn)行隊(duì)列中只能有一個(gè)PCB；系統(tǒng)中所有處于就緒狀態(tài)的進(jìn)程的PCB排成一隊(duì)，稱其為“就緒隊(duì)列”。一般地，就緒隊(duì)列中會(huì)有多個(gè)進(jìn)程的PCB排在里面，它們形成處理機(jī)分配的候選對(duì)象。如果就緒隊(duì)列里沒(méi)有PCB存在，則稱該隊(duì)列為空；所有處于阻塞狀態(tài)進(jìn)程的PCB，應(yīng)該根據(jù)阻塞的原因進(jìn)行排隊(duì)，每一個(gè)都稱為一個(gè)“阻塞隊(duì)列”。比如等待磁盤輸入/輸出進(jìn)程的PCB排成一個(gè)隊(duì)列，等待打印機(jī)輸出進(jìn)程的PCB排成一個(gè)隊(duì)列等。所以，系統(tǒng)中可以有多個(gè)阻塞隊(duì)列，每個(gè)阻塞隊(duì)列中可以有多個(gè)進(jìn)程的PCB，也可以為空。圖2-6是進(jìn)程各隊(duì)列的示意圖。

從圖上可以看出，現(xiàn)在名為PCB1的進(jìn)程正在CPU上運(yùn)行，因?yàn)樗腜CB排在運(yùn)行隊(duì)列中。現(xiàn)在就緒隊(duì)列中有四個(gè)進(jìn)程排在里面，它們分別是PCB2、PCB3、PCB7和PCB6。要注意，進(jìn)程名只是創(chuàng)建進(jìn)程時(shí)系統(tǒng)所給的一個(gè)編號(hào)。系統(tǒng)正常運(yùn)行時(shí)，誰(shuí)的PCB排在隊(duì)列的前面，誰(shuí)的PCB排在隊(duì)列的后面，那是無(wú)法預(yù)料的。現(xiàn)在進(jìn)程PCB5和PCB8排在阻塞隊(duì)列1中，它們被阻塞的原因相同?，F(xiàn)在進(jìn)程PCB10、PCB9和PCB4排在阻塞隊(duì)列2中，它們被阻塞的原因相同。

假定現(xiàn)在又創(chuàng)建了一個(gè)進(jìn)程，名為PCB11。對(duì)于一個(gè)剛被創(chuàng)建的進(jìn)程，系統(tǒng)總是賦予它“就緒”狀態(tài)，因此它的PCB應(yīng)該排在就緒隊(duì)列中。至于PCB11應(yīng)該排在隊(duì)列的什么位置，那將由系統(tǒng)所采取的處理機(jī)分配策略來(lái)確定。假定我們把它排在隊(duì)列之尾，那么圖2-6中的就緒隊(duì)列就變?yōu)閳D2-7所示的情形。2.3進(jìn)程的調(diào)度與管理 2.3.1進(jìn)程調(diào)度算法

1．先來(lái)先服務(wù)調(diào)度算法 先來(lái)先服務(wù)調(diào)度算法的基本思想是：以到達(dá)就緒隊(duì)列的先后次序?yàn)闃?biāo)準(zhǔn)來(lái)選擇占用處理機(jī)的進(jìn)程。一個(gè)進(jìn)程一旦占有處理機(jī)，就一直使用下去，直至正常結(jié)束或因等待某事件的發(fā)生而讓出處理機(jī)。采用這種算法時(shí)，應(yīng)該這樣來(lái)管理就緒隊(duì)列：到達(dá)的進(jìn)程的PCB總是排在就緒隊(duì)列末尾；調(diào)度程序總是把CPU分配給就緒隊(duì)列中的第一個(gè)進(jìn)程使用。圖2-8是先來(lái)先服務(wù)調(diào)度算法的示意圖。 2．時(shí)間片輪轉(zhuǎn)調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法的基本思想是：為就緒隊(duì)列中的每一個(gè)進(jìn)程分配一個(gè)稱為“時(shí)間片”的時(shí)間段，它是允許該進(jìn)程運(yùn)行的時(shí)間長(zhǎng)度。在使用完一個(gè)時(shí)間片后，即使進(jìn)程還沒(méi)有運(yùn)行完畢，也要強(qiáng)迫其釋放處理機(jī)，讓給另一個(gè)進(jìn)程使用。它自己則返回到就緒隊(duì)列末尾，排隊(duì)等待下一次調(diào)度的到來(lái)。采用這種調(diào)度算法時(shí)，對(duì)就緒隊(duì)列的管理與先來(lái)先服務(wù)完全相同。主要區(qū)別是進(jìn)程每次占用處理機(jī)的時(shí)間由時(shí)間片決定，而不是只要占用處理機(jī)就一直運(yùn)行下去，直到運(yùn)行完畢或?yàn)榈却骋皇录陌l(fā)生而自動(dòng)放棄。圖2-9是時(shí)間片輪轉(zhuǎn)調(diào)度算法的示意圖。 3．優(yōu)先數(shù)調(diào)度算法 如何確定進(jìn)程的優(yōu)先數(shù)（也就是進(jìn)程的優(yōu)先級(jí)）可以從如下幾個(gè)方面考慮。 （1）根據(jù)進(jìn)程的類型。比如說(shuō)，系統(tǒng)中有系統(tǒng)進(jìn)程和用戶進(jìn)程。系統(tǒng)進(jìn)程完成的任務(wù)是提供系統(tǒng)服務(wù)，分配系統(tǒng)資源，因此，給予系統(tǒng)進(jìn)程較高的優(yōu)先數(shù)，不僅合乎情理，而且也能夠提高系統(tǒng)的工作效率。 （2）根據(jù)進(jìn)程執(zhí)行任務(wù)的重要性。每個(gè)進(jìn)程所完成的任務(wù)，就其重要性和緊迫性講，肯定不會(huì)完全一樣。比如說(shuō)，系統(tǒng)中處理緊急情況的報(bào)警進(jìn)程的重要性是不言而喻的。賦予報(bào)警進(jìn)程高的優(yōu)先數(shù)，一旦有緊急事件發(fā)生時(shí)，讓它立即占有處理機(jī)投入運(yùn)行，誰(shuí)也不會(huì)提出異議。

（3）根據(jù)進(jìn)程程序的性質(zhì)。一個(gè)CPU繁忙的進(jìn)程，由于需要占用較長(zhǎng)的運(yùn)行時(shí)間，影響系統(tǒng)整體效率的發(fā)揮，因此只能給予較低的優(yōu)先數(shù)。一個(gè)I/O繁忙的進(jìn)程，給予它較高的優(yōu)先數(shù)后，就能充分發(fā)揮CPU和外部設(shè)備之間的并行工作能力。 （4）根據(jù)對(duì)資源的要求。系統(tǒng)資源有處理機(jī)、內(nèi)存儲(chǔ)器和外部設(shè)備等?？梢园凑找粋€(gè)進(jìn)程所需資源的類型和數(shù)量，確定它的優(yōu)先數(shù)。比如給予占用CPU時(shí)間短或內(nèi)存容量少的進(jìn)程以較高的優(yōu)先數(shù)，這樣可以提高系統(tǒng)的吞吐量。 （5）根據(jù)用戶的請(qǐng)求。系統(tǒng)可以根據(jù)用戶的請(qǐng)求，給予它的作業(yè)及其相應(yīng)進(jìn)程很高的優(yōu)先數(shù)，作“加急”處理。 4．多級(jí)隊(duì)列調(diào)度算法 多級(jí)隊(duì)列調(diào)度算法也稱多級(jí)反饋隊(duì)列調(diào)度算法，它是時(shí)間片調(diào)度算法與優(yōu)先數(shù)調(diào)度算法的結(jié)合。實(shí)行這種調(diào)度算法時(shí)，系統(tǒng)中將維持多個(gè)就緒隊(duì)列，每個(gè)就緒隊(duì)列具有不同的調(diào)度級(jí)別，可以獲得不同長(zhǎng)度的時(shí)間片，如圖2-10所示。第1級(jí)就緒隊(duì)列中進(jìn)程的調(diào)度級(jí)別最高，可獲得的時(shí)間片最短。第n級(jí)就緒隊(duì)列中進(jìn)程的調(diào)度級(jí)別最低，可獲得的時(shí)間片最長(zhǎng)。

具體的調(diào)度方法是：創(chuàng)建一個(gè)新進(jìn)程時(shí)，它的PCB將進(jìn)入第1級(jí)就緒隊(duì)列的末尾。對(duì)于在第1級(jí)到第n-1級(jí)隊(duì)列中的進(jìn)程，如果在分配給它的時(shí)間片內(nèi)完成了全部工作，那么就撤離系統(tǒng)；如果在時(shí)間片沒(méi)有用完時(shí)提出了輸入/輸出請(qǐng)求或要等待某事件發(fā)生，那么就進(jìn)入相應(yīng)的阻塞隊(duì)列里等待。在所等待的事件出現(xiàn)時(shí)，仍回到原隊(duì)列末尾，參與下一輪調(diào)度（也就是每個(gè)隊(duì)列實(shí)行先來(lái)先服務(wù)調(diào)度算法）；如果用完了時(shí)間片還沒(méi)有完成自己的工作，那么只能放棄對(duì)CPU的使用，降到低一級(jí)隊(duì)列的末尾，參與那個(gè)隊(duì)列的調(diào)度。對(duì)位于最后一個(gè)隊(duì)列里的進(jìn)程，實(shí)行時(shí)間片輪轉(zhuǎn)調(diào)度算法。

整個(gè)系統(tǒng)最先調(diào)度1級(jí)就緒隊(duì)列；只有在上一級(jí)就緒隊(duì)列為空時(shí)，才去下一級(jí)隊(duì)列調(diào)度。當(dāng)比運(yùn)行進(jìn)程更高級(jí)別的隊(duì)列中到達(dá)一個(gè)進(jìn)程（可以肯定，在此之前比運(yùn)行進(jìn)程級(jí)別高的所有隊(duì)列全為空）時(shí)，系統(tǒng)將立即停止當(dāng)前運(yùn)行進(jìn)程的運(yùn)行，讓它回到自己隊(duì)列的末尾，轉(zhuǎn)去運(yùn)行級(jí)別高的那個(gè)進(jìn)程。

可以看出，多級(jí)隊(duì)列調(diào)度算法優(yōu)先照顧I/O繁忙的進(jìn)程。I/O繁忙的進(jìn)程在獲得一點(diǎn)CPU時(shí)間后就會(huì)提出輸入/輸出請(qǐng)求，因此它們總是被保持在1、2級(jí)等較前面的隊(duì)列中，總能獲得較多的調(diào)度機(jī)會(huì)。對(duì)于CPU繁忙的進(jìn)程，它們需要較長(zhǎng)的CPU時(shí)間，因此會(huì)逐漸地由級(jí)別高的隊(duì)列往下降，以獲得更多的CPU時(shí)間，它們“沉”得越深，被調(diào)度到的機(jī)會(huì)就越少。但是，一旦被調(diào)度到，就會(huì)獲得更多的CPU時(shí)間，所以，多級(jí)調(diào)度算法采用的是“你要得越多，你就必須等待越久”的原則來(lái)分配處理機(jī)的。2.3.2進(jìn)程管理的基本原語(yǔ) 為了對(duì)進(jìn)程進(jìn)行有效的管理和控制，操作系統(tǒng)要提供若干基本的操作，以便能創(chuàng)建進(jìn)程、撤消進(jìn)程、阻塞進(jìn)程和喚醒進(jìn)程。這些操作對(duì)于操作系統(tǒng)來(lái)說(shuō)是最為基本、最為重要的。為了保證執(zhí)行時(shí)的絕對(duì)正確，要求它們以一個(gè)整體出現(xiàn)，不可分割。也就是說(shuō)，一旦啟動(dòng)了它們的程序，就要保證做完，中間不能插入其他程序的執(zhí)行序列。在操作系統(tǒng)中，把具有這種特性的程序被稱為“原語(yǔ)”。

為了保證原語(yǔ)操作的不可分割性，通?？偸抢闷帘沃袛嗟姆椒?。也就是說(shuō)，在啟動(dòng)它們的程序時(shí)，首先關(guān)閉中斷，然后去做創(chuàng)建、撤消、阻塞或喚醒等工作，完成任務(wù)后，再打開中斷。下面簡(jiǎn)略對(duì)這四個(gè)原語(yǔ)的功能做一描述。

1．“創(chuàng)建進(jìn)程”原語(yǔ) 圖2-13給出了創(chuàng)建進(jìn)程原語(yǔ)的流程，其中，“屏蔽中斷”以及“打開中斷”操作是為了保證其不被分割而設(shè)置的。屏蔽中斷后，這三項(xiàng)任務(wù)才能作為一個(gè)整體（即原語(yǔ)）一次做完。2．撤消進(jìn)程原語(yǔ)3．阻塞進(jìn)程原語(yǔ)4．喚醒進(jìn)程原語(yǔ)2.4作業(yè)調(diào)度2.4.1用戶與操作系統(tǒng)的兩種接口1．特權(quán)指令、管態(tài)、目態(tài)2．系統(tǒng)調(diào)用命令

例如，在C語(yǔ)言中，write(fd,buf,count)是UNIX型有關(guān)文件的一個(gè)系統(tǒng)調(diào)用命令。通過(guò)它，用戶可以實(shí)現(xiàn)往一個(gè)文件里進(jìn)行寫的操作。即把buf指向的內(nèi)存緩沖區(qū)里的count個(gè)字節(jié)內(nèi)容寫到文件號(hào)為fd的磁盤文件上。因此，在C語(yǔ)言的源程序里，write表示一個(gè)UNIX的系統(tǒng)調(diào)用命令，且是要求調(diào)用文件寫功能的系統(tǒng)調(diào)用命令；括號(hào)里的fd、buf和count是由用戶提供的、表示要求系統(tǒng)按何條件去完成文件寫操作的參數(shù)。 C編譯程序在編譯C的源程序時(shí)，總是把系統(tǒng)調(diào)用命令翻譯成能夠引起軟中斷的訪管指令trap。該指令長(zhǎng)兩個(gè)字節(jié)，第1個(gè)字節(jié)為操作碼，第2個(gè)字節(jié)為系統(tǒng)調(diào)用命令的功能編碼。Trap的16進(jìn)制操作碼為89，write的功能碼為04。即write將被翻譯成一條二進(jìn)制值為“1000100100000100”的機(jī)器指令（其八進(jìn)制是104404）。Write命令括號(hào)中的參數(shù)，將由編譯程序把它們順序放在trap指令的后面。于是，源程序中的write(fd,buf,count)，經(jīng)過(guò)編譯后，就對(duì)應(yīng)于如圖2-14(a)所示的trap機(jī)器指令。 trap指令中的功能碼是用來(lái)區(qū)分不同的功能調(diào)用的。在UNIX操作系統(tǒng)中，有一張“系統(tǒng)調(diào)用程序入口地址表”。該表表目從0開始、以系統(tǒng)調(diào)用命令所對(duì)應(yīng)的功能碼為順序進(jìn)行排列。例如，write的功能碼是04，那么該表中的第5個(gè)表目?jī)?nèi)容就是對(duì)應(yīng)于write的。系統(tǒng)調(diào)用程序入口地址表的每個(gè)表目形式如圖2-14(b)所示。它由兩部分組成，一是給出該系統(tǒng)調(diào)用所需要的參數(shù)個(gè)數(shù)，一是給出該系統(tǒng)調(diào)用功能程序的入口地址。

現(xiàn)在可以清楚地描繪系統(tǒng)調(diào)用的處理過(guò)程了，如圖2-15所示。C語(yǔ)言編譯程序把系統(tǒng)調(diào)用命令write(fd,buf,count)翻譯成一條trap指令104404，簡(jiǎn)記為trap04。當(dāng)處理機(jī)執(zhí)行到trap04這條指令時(shí)，就產(chǎn)生中斷，硬件自動(dòng)把處理機(jī)的工作方式由目態(tài)轉(zhuǎn)變?yōu)楣軕B(tài)。于是CPU去執(zhí)行操作系統(tǒng)中的trap中斷處理程序，該程序根據(jù)trap后面的功能碼04，從系統(tǒng)調(diào)用處理程序入口地址表中的第5個(gè)表目中，得到該系統(tǒng)調(diào)用應(yīng)該有3個(gè)參數(shù)（它跟隨在目標(biāo)程序trap04指令的后面）。另外從表目中也得到該系統(tǒng)調(diào)用處理程序的入口地址。于是，就可以攜帶這3個(gè)參數(shù)去執(zhí)行write的處理程序，從而完成用戶提出的I/O操作要求。執(zhí)行完畢，又把處理機(jī)恢復(fù)到目態(tài)，返回目標(biāo)程序中trap指令的下一條指令（即斷點(diǎn)）繼續(xù)執(zhí)行。

不同的操作系統(tǒng)所提供的系統(tǒng)調(diào)用命令，在數(shù)量上、使用格式上以及功能上都會(huì)不同，但對(duì)系統(tǒng)調(diào)用的處理過(guò)程則大致如此。從功能上看，可以把系統(tǒng)調(diào)用命令分成五大類：一是關(guān)于進(jìn)程管理和控制的；二是關(guān)于外部設(shè)備輸入/輸出的；三是關(guān)于磁盤文件管理的；四是關(guān)于訪問(wèn)系統(tǒng)信息的；五是關(guān)于存儲(chǔ)申請(qǐng)與釋放的。前面所述的創(chuàng)建進(jìn)程原語(yǔ)等，屬于第一類系統(tǒng)調(diào)用命令。

使用命令接口，要求用戶熟練記住命令的名稱、具體的功能以及使用的格式，因此，不僅用起來(lái)感到不便，容易出錯(cuò)，而且耗費(fèi)時(shí)間。目前，大都被“窗口”這種圖形用戶接口所取代。這種接口具有形象、直觀、使用便利等優(yōu)點(diǎn)。圖2-16是Windows98的資源管理器窗口，用戶可以方便地通過(guò)菜單來(lái)建立自己的目錄，查看目錄下?lián)碛械奈募?，也可以調(diào)用所需的軟件，并投入運(yùn)行。2.4.2作業(yè)與作業(yè)管理

1．作業(yè)與作業(yè)步 一個(gè)作業(yè)的各個(gè)作業(yè)步之間是有聯(lián)系的。通常，上一個(gè)作業(yè)步的輸出是下一個(gè)作業(yè)步的輸入。下一個(gè)作業(yè)步能否順利執(zhí)行，取決于上一個(gè)作業(yè)步的結(jié)果是否正確。圖2-17是一個(gè)典型的C語(yǔ)言作業(yè)處理過(guò)程，具體步驟如下。 （1）用戶通過(guò)鍵盤在編輯程序的支持下建立起以“.C”為擴(kuò)展名的源程序。 （2）C編譯程序以該源程序做為輸入進(jìn)行編譯，產(chǎn)生出以“.OBJ”為擴(kuò)展名的目標(biāo)程序。 （3）連接裝配程序以目標(biāo)程序、系統(tǒng)庫(kù)函數(shù)和包含文件等做為輸入，產(chǎn)生一個(gè)以“.EXE”為擴(kuò)展名的可執(zhí)行文件。這個(gè)文件才是真正可以投入運(yùn)行的程序。 2．作業(yè)控制塊 創(chuàng)建一個(gè)進(jìn)程時(shí)，要開辟一個(gè)進(jìn)程控制塊PCB，以便隨時(shí)記錄進(jìn)程的信息。類同地，在把一個(gè)作業(yè)提交給系統(tǒng)時(shí)，系統(tǒng)也要開辟一個(gè)作業(yè)控制塊JCB（JobControlBlock），以便隨時(shí)記錄作業(yè)的信息。圖2-18給出了JCB中可能包含的信息，這些信息有的來(lái)自作業(yè)說(shuō)明書，有的則會(huì)在運(yùn)行過(guò)程中不斷發(fā)生變化。 3．作業(yè)調(diào)度

4．作業(yè)的狀態(tài)與狀態(tài)的變遷 猶如一個(gè)進(jìn)程有生命期一樣，從作業(yè)提交給系統(tǒng)，到作業(yè)運(yùn)行完畢被撤消，就是一個(gè)作業(yè)的生命期。在這個(gè)期間，作業(yè)隨著自己的推進(jìn)，隨著多道程序系統(tǒng)環(huán)境的變化，其狀態(tài)也在發(fā)生著變化。它由提交狀態(tài)變?yōu)楹髠錉顟B(tài)，變?yōu)檫\(yùn)行狀態(tài)，最后變?yōu)橥瓿蔂顟B(tài)，如圖2-19所示。2.4.3作業(yè)的調(diào)度算法 從用戶的角度出發(fā)，總希望自己的作業(yè)提交后能夠盡快地被選中，并投入運(yùn)行。從系統(tǒng)的角度出發(fā)，它既要顧及到用戶的需要，還要考慮系統(tǒng)效率的發(fā)揮。這就是說(shuō)，在確定作業(yè)調(diào)度算法時(shí)，應(yīng)該注意如下的一些問(wèn)題： （1）公平對(duì)待后備作業(yè)隊(duì)列中的每一個(gè)作業(yè)，避免發(fā)生無(wú)故或無(wú)限期地延遲一個(gè)作業(yè)的執(zhí)行，使各類用戶感到滿意。

（2）使進(jìn)入內(nèi)存的多個(gè)作業(yè)，能均衡地使用系統(tǒng)中的資源，避免出現(xiàn)有的資源沒(méi)有作業(yè)使用、有的資源卻被多個(gè)作業(yè)爭(zhēng)搶的“忙閑”不均的情形。 （3）力爭(zhēng)在單位時(shí)間內(nèi)為盡可能多的作業(yè)提供服務(wù)，提高整個(gè)系統(tǒng)的吞吐能力。 在本節(jié)，將介紹批處理環(huán)境下的作業(yè)調(diào)度算法，并總是用系統(tǒng)的吞吐能力來(lái)判定一個(gè)算法的優(yōu)劣。

在批處理系統(tǒng)中，是使用作業(yè)的“周轉(zhuǎn)時(shí)間”來(lái)描述系統(tǒng)的吞吐能力的。假定作業(yè)i提交給系統(tǒng)（也就是它成為后備作業(yè)隊(duì)列中的一個(gè)成員）的時(shí)間為Si，其完成（也就是用戶得到運(yùn)行結(jié)果）的時(shí)間為Wi。那么該作業(yè)的周轉(zhuǎn)時(shí)間Ti為：Ti=Wi-Si

對(duì)于一批n個(gè)作業(yè)而言，他們的平均周轉(zhuǎn)時(shí)間T為：T=(T1+T2+…+Tn)/n

1．“先來(lái)先服務(wù)”作業(yè)調(diào)度算法 以作業(yè)進(jìn)入后備作業(yè)隊(duì)列的先后次序，作為作業(yè)調(diào)度程序挑選作業(yè)的依據(jù)，這就是先來(lái)先服務(wù)作業(yè)調(diào)度算法的基本思想。這就是說(shuō)，哪個(gè)作業(yè)在后備作業(yè)隊(duì)列中等待的時(shí)間最長(zhǎng)，下次調(diào)度即是選中者。不過(guò)要注意，這是以其資源需求能夠得到滿足為前提的。如果它所需要的資源暫時(shí)無(wú)法獲得，那么它就會(huì)被推遲選中，因?yàn)橹挥羞@樣才合乎情理。第3章存儲(chǔ)管理

計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)器可以分為兩種：內(nèi)存儲(chǔ)器和輔助存儲(chǔ)器。前者可被CPU直接訪問(wèn)，后者不能。輔助存儲(chǔ)器與CPU之間只能夠在輸入輸出控制系統(tǒng)的管理下，進(jìn)行信息交換。 既然內(nèi)存儲(chǔ)器可被CPU直接訪問(wèn)，因此它是計(jì)算機(jī)系統(tǒng)中的一種極為重要的資源。在操作系統(tǒng)中，把管理內(nèi)存儲(chǔ)器的部分稱為“存儲(chǔ)管理”。能否合理地使用內(nèi)存，會(huì)在很大程度上影響到整個(gè)計(jì)算機(jī)系統(tǒng)的性能。退出

本章將要介紹兩個(gè)重要概念。一個(gè)是“地址重定位”。在多道程序設(shè)計(jì)環(huán)境下，用戶無(wú)法事先約定各自占用內(nèi)存的哪個(gè)區(qū)域，也不知道自己的程序會(huì)放在內(nèi)存的什么位置，但程序地址如果不反映其真實(shí)的存儲(chǔ)位置，就不可能得到正確的執(zhí)行。所以在存儲(chǔ)管理中，必須解決地址的重定位問(wèn)題。二是“虛擬存儲(chǔ)”。曾經(jīng)有人說(shuō)過(guò)：“存儲(chǔ)器有多大，程序就會(huì)有多大”。因此，在計(jì)算機(jī)系統(tǒng)中，雖然內(nèi)存的容量隨著硬件的發(fā)展得到了很大的擴(kuò)充，但仍然無(wú)法滿足實(shí)際的需要，必須打破“程序只有全部在內(nèi)存，才能得以運(yùn)行”的限制。為此，通過(guò)“虛擬存儲(chǔ)”這一技術(shù)手段，可以達(dá)到不用真正擴(kuò)充內(nèi)存而“擴(kuò)充”內(nèi)存的目的。本章著重講述四個(gè)方面的內(nèi)容：（1）地址的靜態(tài)重定位和動(dòng)態(tài)重定位；（2）不同的存儲(chǔ)管理方案；（3）存儲(chǔ)共享和存儲(chǔ)保護(hù)；（4）存儲(chǔ)擴(kuò)充和虛擬存儲(chǔ)器。3.1固定分區(qū)存儲(chǔ)管理3.2可變分區(qū)存儲(chǔ)管理3.3分頁(yè)式存儲(chǔ)管理3.4虛擬存儲(chǔ)與請(qǐng)求頁(yè)式存儲(chǔ)管理3.1固定分區(qū)存儲(chǔ)管理3.1.1地址重定位 舉例說(shuō)，假定用戶程序A的相對(duì)地址空間為0~3KB(0~3071)，在該程序中地址為3000的地方，有一條調(diào)用子程序（其入口地址為100）的指令：“call100”，如圖3-1(a)所示。

很清楚，用戶程序指令中出現(xiàn)的都是相對(duì)地址，即都是相對(duì)于“0”的地址。若當(dāng)前操作系統(tǒng)在內(nèi)存儲(chǔ)器占用0~20KB的存儲(chǔ)區(qū)。這時(shí)，如果把程序A裝入到內(nèi)存儲(chǔ)器中20KB往下的存儲(chǔ)區(qū)域中，那么，它這時(shí)占據(jù)的是內(nèi)存儲(chǔ)器中20KB~23KB的區(qū)域。這個(gè)區(qū)域就是它的絕對(duì)地址空間?，F(xiàn)在它還不能正確運(yùn)行，因?yàn)樵趫?zhí)行到位于絕對(duì)地址23480（20KB+3000）處的“call100”指令時(shí)，它會(huì)到絕對(duì)地址100處去調(diào)用所需的子程序，但這個(gè)地址卻在操作系統(tǒng)里面，如圖3-1(b)所示。之所以出錯(cuò)是因?yàn)閏all后面所跟隨的子程序入口地址現(xiàn)在應(yīng)該是20580，而不應(yīng)該保持原來(lái)的100。這表明，當(dāng)把一個(gè)程序裝入內(nèi)存后，如果不將其指令中的地址進(jìn)行調(diào)整，以反映當(dāng)前所在的存儲(chǔ)位置，那么執(zhí)行時(shí)勢(shì)必會(huì)引起混亂。

在操作系統(tǒng)中，把用戶程序指令中的相對(duì)地址變換成為所在絕對(duì)地址空間中的絕對(duì)地址的過(guò)程，稱為“地址重定位”。也就是說(shuō)，把指令“call100”中的100變換成20580，就是地址重定位，如圖3-1(c)所示。地址重定位與用戶程序占用的絕對(duì)地址空間的起始地址有關(guān)。在圖3-1(c)中，由于是把程序A裝入到（20KB~23KB）絕對(duì)地址空間里，因此call指令中相對(duì)地址100所對(duì)應(yīng)的絕對(duì)地址是20KB+100=20580。如果把程序A裝入到（22KB~25KB）的絕對(duì)地址空間里，那么call指令中相對(duì)地址100所對(duì)應(yīng)的絕對(duì)地址就應(yīng)該是22KB+100=22628了。如圖3-1(d)所示。3.1.2地址的靜態(tài)重定位 如果在程序運(yùn)行之前，就為用戶程序?qū)嵭辛说刂分囟ㄎ坏墓ぷ?，那么稱這種地址重定位為地址的“靜態(tài)重定位”。一般地，靜態(tài)重定位工作是由操作系統(tǒng)中的重定位裝入程序來(lái)完成的。用戶把自己的作業(yè)鏈接裝配成一個(gè)相對(duì)于“0”編址的目標(biāo)程序，它就是重定位裝入程序的輸入，即加工對(duì)象。重定位裝入程序根據(jù)當(dāng)前內(nèi)存的分配情況，按照分配區(qū)域的起始地址逐一調(diào)整目標(biāo)程序指令中的地址部分。于是，目標(biāo)程序在經(jīng)過(guò)重定位裝入程序加工之后，不僅進(jìn)入到分配給自己的絕對(duì)地址空間中，而且程序指令里的地址部分全部進(jìn)行了修正，反映出了自己正確的存儲(chǔ)位置，從而保證程序的正確運(yùn)行。3.1.3單一連續(xù)分區(qū)存儲(chǔ)管理 就早期計(jì)算機(jī)或個(gè)人微機(jī)而言，每次只有一個(gè)用戶使用計(jì)算機(jī)，無(wú)從提及多道程序設(shè)計(jì)，因此，在這些機(jī)器上運(yùn)行的操作系統(tǒng)，其存儲(chǔ)管理都采用單一連續(xù)分區(qū)的分配策略。 單一連續(xù)分區(qū)分配策略的基本思想是總體上把內(nèi)存儲(chǔ)器分為兩個(gè)分區(qū)。一個(gè)分區(qū)固定分配給操作系統(tǒng)使用；另一個(gè)分配給用戶使用，稱為“用戶區(qū)”。如圖3-2(a)所示。

可以看出，采用單一連續(xù)分區(qū)存儲(chǔ)管理方案的系統(tǒng)有如下特點(diǎn)： （1）系統(tǒng)總是把整個(gè)用戶區(qū)分配給一個(gè)用戶使用，比如圖3-2(a)中的a~b區(qū)域。 （2）實(shí)際上，內(nèi)存用戶區(qū)又被分為“使用區(qū)”和“空閑區(qū)”兩部分。見圖3-2(b)，其中使用區(qū)為a~c，空閑區(qū)為c~b。使用區(qū)是用戶作業(yè)程序真正占用的那個(gè)連續(xù)存儲(chǔ)區(qū)域；空閑區(qū)是分配給了用戶、但未被使用的區(qū)域。在操作系統(tǒng)中，把分配給了用戶、但又未使用的區(qū)域稱為“內(nèi)部碎片”。內(nèi)部碎片的存在是對(duì)內(nèi)存資源的一種浪費(fèi)。

（3）由于任何時(shí)刻內(nèi)存儲(chǔ)器的用戶區(qū)中只有一個(gè)作業(yè)運(yùn)行，因此這種系統(tǒng)只適用于單用戶（或單道）的情況。 （4）進(jìn)入內(nèi)存的作業(yè)，獨(dú)享系統(tǒng)中的所有資源，包括內(nèi)存中的整個(gè)用戶區(qū)。 （5）由于整個(gè)用戶區(qū)都分配給了一個(gè)用戶使用，因此作業(yè)程序進(jìn)入用戶區(qū)后，沒(méi)有移動(dòng)的必要。采用這種存儲(chǔ)分配策略時(shí)，將對(duì)用戶程序?qū)嵭徐o態(tài)重定位。

（6）實(shí)行靜態(tài)重定位，并不能阻止用戶有意無(wú)意地通過(guò)不恰當(dāng)?shù)闹噶铌J入操作系統(tǒng)所占用的存儲(chǔ)區(qū)域。如何阻止對(duì)操作系統(tǒng)的侵?jǐn)_，這就是所謂的“存儲(chǔ)保護(hù)”問(wèn)題。在單一連續(xù)分區(qū)存儲(chǔ)管理中，為了有效阻止用戶程序指令中的地址闖入操作系統(tǒng)所占用的區(qū)域，在CPU中設(shè)置一個(gè)用于存儲(chǔ)保護(hù)的專用寄存器——“界限寄存器”，如圖3-2(c)所示。在界限寄存器中，總是存放著內(nèi)存用戶區(qū)的起始地址（比如圖3-2(c)中為a）。當(dāng)CPU在管態(tài)下工作時(shí)，允許訪問(wèn)內(nèi)存中的任何地址；當(dāng)CPU在目態(tài)下工作時(shí)，對(duì)內(nèi)存儲(chǔ)器的每一次訪問(wèn)，都要在硬件的控制下，與界限寄存器中的內(nèi)容進(jìn)行比較。一旦發(fā)現(xiàn)該訪問(wèn)的地址小于界限寄存器中的地址，就會(huì)產(chǎn)生“地址越界”中斷，阻止這次訪問(wèn)的進(jìn)行，從而將作業(yè)限制在規(guī)定的存儲(chǔ)區(qū)域內(nèi)運(yùn)行，確保被保護(hù)區(qū)中的信息不受外來(lái)的破壞。

單一連續(xù)分區(qū)存儲(chǔ)管理有如下缺點(diǎn)： （1）由于每次只能有一個(gè)作業(yè)進(jìn)入內(nèi)存，故它不適用于多道程序設(shè)計(jì)，整個(gè)系統(tǒng)的工作效率不高，資源利用率低下。 （2）只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會(huì)形成碎片，造成內(nèi)存儲(chǔ)器資源的浪費(fèi)。如果用戶作業(yè)很小，那么這種浪費(fèi)是巨大的。

（3）若用戶作業(yè)的相對(duì)地址空間比用戶區(qū)大，那么該作業(yè)就無(wú)法運(yùn)行。即大作業(yè)無(wú)法在小內(nèi)存上運(yùn)行。 早期計(jì)算機(jī)在一定的條件下，可以采用所謂的“覆蓋”技術(shù)，使得大作業(yè)在小內(nèi)存上得以運(yùn)行。舉例說(shuō)，有一個(gè)用戶作業(yè)程序的調(diào)用結(jié)構(gòu)如圖3-3(a)所示。主程序MAIN需要存儲(chǔ)量10KB。運(yùn)行中，它要調(diào)用程序A或B，它們各需要存儲(chǔ)量50KB和30KB。程序A在運(yùn)行中要調(diào)用程序C，它需要的存儲(chǔ)量是30KB。程序B在運(yùn)行中要調(diào)用程序D或程序E，它們各需要存儲(chǔ)量20KB或40KB。通過(guò)連接裝配的處理，該作業(yè)將形成一個(gè)需要存儲(chǔ)量180KB的相對(duì)地址空間，如圖3-3(b)所示。這表明，只有系統(tǒng)分配給它180KB的絕對(duì)地址空間時(shí)，它才能夠全部裝入并運(yùn)行。

其實(shí)不難看出，該程序中的子程序A和B不可能同時(shí)調(diào)用，即MAIN調(diào)用程序A，就肯定不會(huì)調(diào)用程序B，反之亦然。同樣地，子程序C、D和E也不可能同時(shí)出現(xiàn)，所以，除了主程序必須占用內(nèi)存中的10KB外，A和B可以共用一個(gè)存儲(chǔ)量為50KB的存儲(chǔ)區(qū)，C、D和E可以共用一個(gè)存儲(chǔ)量為40KB的存儲(chǔ)區(qū)，如圖3-3(c)所示。也就是說(shuō)，只要分給該程序100KB的存儲(chǔ)量，它就能夠運(yùn)行。由于A和B共用一個(gè)50KB的存儲(chǔ)區(qū)，C、D和E共用一個(gè)40KB的存儲(chǔ)區(qū)，我們就稱50KB的存儲(chǔ)區(qū)和40KB的存儲(chǔ)區(qū)為覆蓋區(qū)。因此，所謂“覆蓋”，是早期為程序設(shè)計(jì)人員提供的一種擴(kuò)充內(nèi)存的技術(shù)，其中心思想是允許一個(gè)作業(yè)的若干個(gè)程序段使用同一個(gè)存儲(chǔ)區(qū)，被共用的存儲(chǔ)區(qū)被稱為“覆蓋區(qū)”。不過(guò)，這種技術(shù)并不能徹底解決大作業(yè)與小內(nèi)存的矛盾。

為了讓單一連續(xù)分區(qū)存儲(chǔ)管理能具有“多道”的效果，在一定條件下，可以采用所謂的“對(duì)換”技術(shù)來(lái)實(shí)現(xiàn)。“對(duì)換”的中心思想是：將作業(yè)信息都存放在輔助存儲(chǔ)器上，根據(jù)單一連續(xù)分區(qū)存儲(chǔ)管理的分配策略，每次只讓其中的一個(gè)進(jìn)入內(nèi)存投入運(yùn)行。當(dāng)運(yùn)行中提出輸入輸出請(qǐng)求或分配給的時(shí)間片用完時(shí)，就把這個(gè)程序從內(nèi)存儲(chǔ)器“換出”到輔助存儲(chǔ)器，把輔助存儲(chǔ)器里的另一個(gè)作業(yè)“換入”內(nèi)存儲(chǔ)器運(yùn)行，如圖3-4所示。這樣，從宏觀上看，系統(tǒng)中同時(shí)就有幾個(gè)作業(yè)處在運(yùn)行之中。不過(guò)要注意，由于單一連續(xù)分區(qū)存儲(chǔ)管理實(shí)行的是靜態(tài)重定位，所以，“換出”的作業(yè)程序再被“換入”時(shí)，仍應(yīng)該裝到與它“換出”前相同的存儲(chǔ)區(qū)中去，以保證能夠正確地繼續(xù)運(yùn)行。不難看出，“對(duì)換”是以輔助存儲(chǔ)器作為內(nèi)存的后援而得以實(shí)行的，沒(méi)有它的支持，就談不上“對(duì)換”。 3.1.4固定分區(qū)存儲(chǔ)管理

1．對(duì)作業(yè)的組織 一般地，固定分區(qū)存儲(chǔ)管理總是把內(nèi)存用戶區(qū)劃分成幾個(gè)大小不等的連續(xù)分區(qū)。由于分區(qū)尺寸在劃分后保持不變，因此系統(tǒng)可以為每一個(gè)分區(qū)設(shè)置一個(gè)后備作業(yè)隊(duì)列，形成多隊(duì)列的管理方式，如圖3-5(a)所示。在這種組織方式下，一個(gè)作業(yè)到達(dá)時(shí)，總是進(jìn)入到“能容納該作業(yè)的最小分區(qū)”的那個(gè)后備作業(yè)隊(duì)列中去排隊(duì)。比如圖3-5(a)中，作業(yè)A、B、C排在第1分區(qū)的隊(duì)列上，說(shuō)明它們對(duì)內(nèi)存的需求都不超過(guò)8KB；作業(yè)D排在第2分區(qū)的隊(duì)列上，表明它對(duì)內(nèi)存的需求大于8KB小于32KB；作業(yè)E和F排在第4分區(qū)的隊(duì)列上，表明它們對(duì)內(nèi)存的需求大于64KB小于132KB。

把到達(dá)的作業(yè)根據(jù)上述原則排成若干個(gè)后備隊(duì)列時(shí)，可能會(huì)產(chǎn)生有的分區(qū)隊(duì)列忙碌、有的分區(qū)隊(duì)列閑置的情形。比如圖3-5(a)中，作業(yè)A、B、C都在等待著進(jìn)入第1分區(qū)。按照原則，它們不能進(jìn)入目前空閑的第3分區(qū)，雖然第3分區(qū)的大小完全能夠容納下它們。 作為一種改進(jìn)，可以采用多個(gè)分區(qū)只設(shè)置一個(gè)后備作業(yè)隊(duì)列的辦法，如圖3-5(b)所示。當(dāng)某個(gè)分區(qū)空閑時(shí)，統(tǒng)一都到這一個(gè)隊(duì)列里去挑選作業(yè)，裝入運(yùn)行。 2．分區(qū)的分配與釋放 在操作系統(tǒng)中，要確定選用某一種管理策略時(shí)，應(yīng)該考慮多方面的因素，權(quán)衡利弊，絕對(duì)好的方案是少見的。 為了具體管理內(nèi)存中的各個(gè)分區(qū)，操作系統(tǒng)的做法是設(shè)置一張名為“分區(qū)分配表”的表格，用它記錄各分區(qū)的信息以及當(dāng)前的使用情況。表3-1即為一種分區(qū)配表。

分區(qū)分配表中至少應(yīng)該有每個(gè)分區(qū)的起始地址和長(zhǎng)度，并且有一個(gè)使用標(biāo)志。當(dāng)某分區(qū)的使用標(biāo)志為“0”時(shí)，表示該分區(qū)當(dāng)前是空閑的，可以分配；當(dāng)某分區(qū)的使用標(biāo)志不為“0”時(shí)，表示該分區(qū)已經(jīng)分配給一個(gè)作業(yè)使用，該標(biāo)志里存放的即是這個(gè)作業(yè)的名稱。從表3-1可以看出，該系統(tǒng)共有4個(gè)分區(qū)。第1分區(qū)已經(jīng)分配給作業(yè)1使用，第2分區(qū)分配給了作業(yè)6使用，第4分區(qū)分配給了作業(yè)2使用。當(dāng)前只有第3分區(qū)是空閑的。

當(dāng)需要把一個(gè)作業(yè)裝入內(nèi)存時(shí)，按照分區(qū)號(hào)掃視分區(qū)分配表，找到使用標(biāo)志為“0”的分區(qū)，隨后把要裝入內(nèi)存的作業(yè)尺寸與該分區(qū)的長(zhǎng)度進(jìn)行比較。若能夠容納該作業(yè)，并符合所采取的分配策略，那么就把它分配給這個(gè)作業(yè)，同時(shí)修改分區(qū)分配表中該分區(qū)表目的使用標(biāo)志為非0（即把該作業(yè)的名字填入），從而完成分區(qū)的分配工作；當(dāng)一個(gè)作業(yè)運(yùn)行結(jié)束時(shí)，只需根據(jù)作業(yè)名，在分區(qū)分配表里找到它所使用的表目，然后將該表目的使用標(biāo)志改為“0”，從而完成該分區(qū)的釋放工作。

3．地址重定位與存儲(chǔ)保護(hù) 在固定分區(qū)存儲(chǔ)管理中，不僅要防止用戶程序?qū)Σ僮飨到y(tǒng)形成的侵?jǐn)_，也要防止用戶程序與用戶程序之間形成的侵?jǐn)_。因此必須在CPU中設(shè)置一對(duì)專用的寄存器，用于存儲(chǔ)保護(hù)，如圖3-6所示。 在圖3-6中，將兩個(gè)專用寄存器分別起名為“低界限寄存器”和“高界限寄存器”。當(dāng)進(jìn)程調(diào)度程序調(diào)度某個(gè)作業(yè)進(jìn)程運(yùn)行時(shí)，就把該作業(yè)所在分區(qū)的低邊界地址裝入低界限寄存器，把高邊界地址裝入高界限寄存器。比如現(xiàn)在調(diào)度到分區(qū)1里的作業(yè)1運(yùn)行，于是就把第1分區(qū)的低地址a裝入到低界限寄存器中，把第1分區(qū)的高地址b裝入到高界限寄存器中。作業(yè)1運(yùn)行時(shí)，硬件會(huì)自動(dòng)檢測(cè)指令中的地址，如果超出a或b，那么就產(chǎn)生出錯(cuò)中斷，從而限定作業(yè)1只在自己的區(qū)域里運(yùn)行。3.2可變分區(qū)存儲(chǔ)管理3.2.1可變分區(qū)存儲(chǔ)管理的基本思想 固定分區(qū)存儲(chǔ)管理中的“固定”有兩層含義，一是分區(qū)數(shù)目固定，一是每個(gè)分區(qū)的尺寸固定。采用這種內(nèi)存管理技術(shù)時(shí)，分配出去的分區(qū)總可能會(huì)有一部分成為內(nèi)部碎片而浪費(fèi)掉。究其原因，是因?yàn)檫M(jìn)入分區(qū)的作業(yè)大小，不可能剛好等于該分區(qū)的尺寸。那么能否不事先劃分好分區(qū)，而是按照進(jìn)入作業(yè)的相對(duì)地址空間的大小來(lái)分配存儲(chǔ)，從而避免固定式分區(qū)所產(chǎn)生的存儲(chǔ)浪費(fèi)，這實(shí)際上就是可變分區(qū)存儲(chǔ)管理考慮問(wèn)題的出發(fā)點(diǎn)。

可變分區(qū)存儲(chǔ)管理的基本思想是：在作業(yè)要求裝入內(nèi)存儲(chǔ)器時(shí)，如果當(dāng)時(shí)內(nèi)存儲(chǔ)器中有足夠的存儲(chǔ)空間滿足該作業(yè)的需求，那么就劃分出一個(gè)與作業(yè)相對(duì)地址空間同樣大小的分區(qū)分配給它。

圖3-7是可變分區(qū)存儲(chǔ)管理思想的示意圖。圖3-7(a)是系統(tǒng)維持的后備作業(yè)隊(duì)列，作業(yè)A需要內(nèi)存15KB，作業(yè)B需要20KB，作業(yè)C需要10KB，等等；圖3-7(b)表示系統(tǒng)初啟時(shí)的情形，整個(gè)系統(tǒng)里因?yàn)闆](méi)有作業(yè)運(yùn)行，因此用戶區(qū)就是一個(gè)空閑分區(qū)；圖3-7(c)表示將作業(yè)A裝入內(nèi)存時(shí)，為它劃分了一個(gè)分區(qū)，尺寸為15KB，此時(shí)的用戶區(qū)被分為兩個(gè)分區(qū)，一個(gè)是已經(jīng)分配的，一個(gè)是空閑區(qū)；圖3-7(d)表示將作業(yè)B裝入內(nèi)存時(shí)，為它劃分了一個(gè)分區(qū)，尺寸為20KB，此時(shí)的用戶區(qū)被分為三個(gè)分區(qū)；圖3-7(e)表示將作業(yè)C裝入內(nèi)存時(shí)，為它劃分了一個(gè)分區(qū)，尺寸為10KB，此時(shí)的用戶區(qū)被分為四個(gè)分區(qū)。由此可見，可變分區(qū)存儲(chǔ)管理中的“可變”也有兩層含義，一是分區(qū)的數(shù)目隨進(jìn)入作業(yè)的多少可變，一是分區(qū)的邊界劃分隨作業(yè)的需求可變。

由于實(shí)施可變分區(qū)存儲(chǔ)管理時(shí)，分區(qū)的劃分是按照進(jìn)入作業(yè)的尺寸進(jìn)行的，因此在這個(gè)分區(qū)里不會(huì)出現(xiàn)內(nèi)部碎片。這就是說(shuō)，可變分區(qū)存儲(chǔ)管理消滅了內(nèi)部碎片，不會(huì)出現(xiàn)由于內(nèi)部碎片而引起的存儲(chǔ)浪費(fèi)現(xiàn)象。 但是，為了克服內(nèi)部碎片而提出的可變分區(qū)存儲(chǔ)管理模式，卻引發(fā)了很多新的問(wèn)題。只有很好地解決這些問(wèn)題，可變分區(qū)存儲(chǔ)管理才能真正得以實(shí)現(xiàn)。下面我們通過(guò)圖3-8來(lái)看一下可變分區(qū)存儲(chǔ)管理的工作過(guò)程，歸納出需要解決的一些技術(shù)問(wèn)題。

假定有作業(yè)請(qǐng)求序列：作業(yè)A需要存儲(chǔ)16KB，作業(yè)B需要存儲(chǔ)100KB，作業(yè)C需要存儲(chǔ)70KB，作業(yè)D需要存儲(chǔ)75KB，等等。內(nèi)存儲(chǔ)器共256KB，操作系統(tǒng)占用20KB，系統(tǒng)最初有空閑區(qū)236KB，如圖3-8(a)所示。下面著重討論236KB空閑區(qū)的變化。作業(yè)A到達(dá)后，按照它的存儲(chǔ)要求，劃分一個(gè)16KB大小的分區(qū)分配給它，于是出現(xiàn)兩個(gè)分區(qū)，一個(gè)已經(jīng)分配，一個(gè)為空閑，如圖3-8(b)所示。作業(yè)B到達(dá)后，按照它的存儲(chǔ)要求，劃分一個(gè)100KB大小的分區(qū)分配給它，于是出現(xiàn)三個(gè)分區(qū)，兩個(gè)已經(jīng)分配，一個(gè)為空閑，如圖3-8(c)所示。緊接著為作業(yè)C劃分一個(gè)分區(qū)，從而形成四個(gè)分區(qū)，三個(gè)已經(jīng)分配，一個(gè)空閑，如圖3-8(d)所示。

當(dāng)作業(yè)D到達(dá)時(shí)，由于系統(tǒng)內(nèi)只有50KB的空閑區(qū)，不夠D的需求，因此作業(yè)D暫時(shí)無(wú)法進(jìn)入。如果這時(shí)作業(yè)B運(yùn)行完畢，釋放它所占用的100KB存儲(chǔ)量，這時(shí)系統(tǒng)中雖然仍保持為四個(gè)分區(qū)，但有的分區(qū)的性質(zhì)已經(jīng)改變，成為兩個(gè)已分配，兩個(gè)空閑，如圖3-8(e)所示。由于作業(yè)B釋放的分區(qū)有100KB大，可以滿足作業(yè)D的需要，因此系統(tǒng)在36KB~136KB的空閑區(qū)中劃分出一個(gè)75KB的分區(qū)給作業(yè)D使用。這樣36KB~136KB分區(qū)被分為兩個(gè)分區(qū)，一個(gè)分配出去（36KB~111KB），一個(gè)仍為空閑（111KB~136KB），如圖3-8(f)所示。這樣，總共有五個(gè)分區(qū)：三個(gè)已經(jīng)分配，兩個(gè)空閑。 3.2.2地址的動(dòng)態(tài)重定位 圖3-9是對(duì)動(dòng)態(tài)重定位過(guò)程的一個(gè)描述。這里仍沿用圖3-1的信息?，F(xiàn)在為了對(duì)圖3-9(a)中的用戶作業(yè)A實(shí)行可變分區(qū)存儲(chǔ)管理，假定按照當(dāng)前內(nèi)存儲(chǔ)器的分配情況，把它原封不動(dòng)地裝入到22KB~25KB的分區(qū)里面?？梢钥吹?，在其絕對(duì)地址空間里，位于22KB+3000單元處的指令仍然是“call100”，未對(duì)它做任何的修改。如果現(xiàn)在調(diào)度到該作業(yè)運(yùn)行，操作系統(tǒng)就把它所占用的分區(qū)的起始地址22KB裝入到定位寄存器中，如圖3-9(b)所示。當(dāng)執(zhí)行到位于單元22KB+3000中的指令“call100”時(shí)，硬件的地址變換線路就把該指令中的地址100取出來(lái)，與定位寄存器中的22KB相加，形成絕對(duì)地址22628（=22KB+100）。然后就按照這個(gè)地址去執(zhí)行call指令。于是，程序就正確轉(zhuǎn)移到22628的子程序處去執(zhí)行了。3.2.3空閑區(qū)的合并 在可變分區(qū)存儲(chǔ)管理中實(shí)行地址的動(dòng)態(tài)重定位后，用戶程序就不會(huì)被“釘死”在分配給自己的存儲(chǔ)分區(qū)中。必要時(shí)，它可以在內(nèi)存中移動(dòng)，為空閑區(qū)的合并帶來(lái)了便利。 內(nèi)存區(qū)域中的一個(gè)分區(qū)被釋放時(shí)，與它前后相鄰接的分區(qū)可能會(huì)有四種關(guān)系出現(xiàn)，如圖3-10所示。在圖中，我們做這樣的約定：位于一個(gè)分區(qū)上面的分區(qū)，稱為它的“前鄰接”分區(qū)，一個(gè)分區(qū)下面的分區(qū)，稱為它的“后鄰接”分區(qū)。

（1）圖3-10(a)表示釋放區(qū)的前鄰接分區(qū)和后鄰接分區(qū)都是已分配區(qū)，因此沒(méi)有合并的問(wèn)題存在。此時(shí)釋放區(qū)自己形成一個(gè)新的空閑區(qū)，該空閑區(qū)的起始地址就是該釋放區(qū)的起始地址，長(zhǎng)度就是該釋放區(qū)的長(zhǎng)度。 （2）圖3-10(b)表示釋放區(qū)的前鄰接分區(qū)是一個(gè)空閑區(qū)，后鄰接分區(qū)是一個(gè)已分配區(qū)，因此，釋放區(qū)應(yīng)該和前鄰接的空閑區(qū)合并成為一個(gè)新的空閑區(qū)。這個(gè)新空閑區(qū)的起始地址是原前鄰接空閑區(qū)的起始地址，長(zhǎng)度是這兩個(gè)合并分區(qū)的長(zhǎng)度之和。

（3）圖3-10(c)表示釋放區(qū)的前鄰接分區(qū)是一個(gè)分配區(qū)，后鄰接分區(qū)是一個(gè)空閑區(qū)，因此，釋放區(qū)應(yīng)該和后鄰接的空閑區(qū)合并成為一個(gè)新的空閑區(qū)。這個(gè)新空閑區(qū)的起始地址是該釋放區(qū)的起始地址，長(zhǎng)度是這兩個(gè)合并分區(qū)的長(zhǎng)度之和。 （4）圖3-10(d)表示釋放區(qū)的前鄰接分區(qū)和后鄰接分區(qū)都是一個(gè)空閑區(qū)，因此，釋放區(qū)應(yīng)該和前、后兩個(gè)鄰接的空閑區(qū)合并成為一個(gè)新的空閑區(qū)。這個(gè)新空閑區(qū)的起始地址是原前鄰接空閑區(qū)的起始地址，長(zhǎng)度是這三個(gè)合并分區(qū)的長(zhǎng)度之和。

空閑分區(qū)的合并，有時(shí)也被稱為“存儲(chǔ)緊湊”。何時(shí)進(jìn)行合并，操作系統(tǒng)可以有兩種時(shí)機(jī)的選擇方案：一是調(diào)度到某個(gè)作業(yè)時(shí)，當(dāng)時(shí)系統(tǒng)中的每一個(gè)空閑分區(qū)尺寸都比它所需要的存儲(chǔ)量小，但空閑區(qū)的總存儲(chǔ)量卻大于它的存儲(chǔ)請(qǐng)求，于是就進(jìn)行空閑存儲(chǔ)分區(qū)的合并，以便能夠得到一個(gè)大的空閑分區(qū)，滿足該作業(yè)的存儲(chǔ)需要；另一是只要有作業(yè)運(yùn)行完畢歸還它所占用的存儲(chǔ)分區(qū)，系統(tǒng)就進(jìn)行空閑分區(qū)的合并。比較這兩種方案可以看出，前者要花費(fèi)較多的精力去管理空閑區(qū)，但空閑區(qū)合并的頻率低，系統(tǒng)在合并上的開銷少；后者總是在系統(tǒng)里保持一個(gè)大的空閑分區(qū)，因此對(duì)空閑分區(qū)談不上更多的管理，但是空閑區(qū)合并的頻率高，系統(tǒng)在這上面的開銷大。3.2.4分區(qū)的管理與組織方式 采用可變分區(qū)方式管理內(nèi)存儲(chǔ)器時(shí)，內(nèi)存中有兩類性質(zhì)的分區(qū)：一類是已經(jīng)分配給用戶使用的“已分配區(qū)”，另一類是可以分配給用戶使用的“空閑區(qū)”。隨著時(shí)間的推移，它們的數(shù)目在不斷地變化著。如何知道哪個(gè)分區(qū)是已分配的，哪個(gè)分區(qū)是空閑的，如何知道各個(gè)分區(qū)的尺寸是多少，這就是分區(qū)管理所要解決的問(wèn)題。 對(duì)分區(qū)的管理，常用的方式有三種：表格法、單鏈表法和雙鏈表法。下面逐一介紹它們各自的實(shí)現(xiàn)技術(shù)。

1．表格法 為了記錄內(nèi)存中現(xiàn)有的分區(qū)以及各分區(qū)的類型，操作系統(tǒng)設(shè)置兩張表格，一張為“已分配表”，一張為“空閑區(qū)表”，如圖3-11(b)和3-11(c)所示。表格中的“序號(hào)”是表目項(xiàng)的順序號(hào)，“起始地址”、“尺寸”和“狀態(tài)”都是該分區(qū)的相應(yīng)屬性。由于系統(tǒng)中分區(qū)的數(shù)目是變化的，因此每張表格中的表目項(xiàng)數(shù)要足夠的多，暫時(shí)不用的表目項(xiàng)的狀態(tài)被設(shè)為“空”。

假定圖3-11(a)為當(dāng)前內(nèi)存中的分區(qū)使用情況，那么圖3-11(b)記錄了已分配區(qū)的情形，圖3-11(c)記錄了空閑區(qū)的情形。當(dāng)作業(yè)進(jìn)入而提出存儲(chǔ)需求時(shí)，就去查空閑區(qū)表里狀態(tài)為“空閑”的表目項(xiàng)。如果該項(xiàng)的尺寸能滿足所求，那么就將它一分為二：分配出去的那一部分在已分配表中找一個(gè)狀態(tài)為“空”的表目項(xiàng)進(jìn)行登記，剩下的部分（如果有的話）仍在空閑區(qū)表中占據(jù)一個(gè)表目項(xiàng)。如果有一個(gè)作業(yè)運(yùn)行結(jié)束，則根據(jù)作業(yè)名到已分配表中找到它的表目項(xiàng)，將該項(xiàng)的“狀態(tài)”改為“空”，隨之在空閑區(qū)表中尋找一個(gè)狀態(tài)為“空”的表目項(xiàng)，把釋放分區(qū)的信息填入，并將表目項(xiàng)狀態(tài)改為“空閑”。當(dāng)然，這時(shí)可能還會(huì)進(jìn)行空閑區(qū)的合并工作。 2．單鏈表法 把內(nèi)存儲(chǔ)器中的每個(gè)空閑分區(qū)視為一個(gè)整體，在它的里面開辟出兩個(gè)單元，一個(gè)用于存放該分區(qū)的長(zhǎng)度（size），一個(gè)用于存放它下一個(gè)空閑分區(qū)的起始地址（next），如圖3-14(a