操作系統(tǒng)課后部分習(xí)題及答案

第2章操作系統(tǒng)的運行環(huán)境

2.2現(xiàn)代計算機為什么設(shè)置目態(tài)/管態(tài)這兩種不同的機器狀態(tài)？現(xiàn)在的lntel80386設(shè)置

了四級不同的機器狀態(tài)（把管態(tài)又分為三個特權(quán)級），你能說出自己的理解嗎？

答：現(xiàn)在的Intel80386把執(zhí)行全部指令的管態(tài)分為三個特權(quán)級，再加之只能執(zhí)行非特

權(quán)指令的目態(tài)，這四級不同的機器狀態(tài)，按照系統(tǒng)處理器工作狀態(tài)這四級不同的機器狀態(tài)也

被劃分管態(tài)和目態(tài)，這也完全符合處理器的工作狀態(tài)。

2.6什么是程序狀態(tài)字？主要包括什么內(nèi)容？

答：如何知道處理器當(dāng)前處于什么工作狀態(tài)，它能否執(zhí)行特權(quán)指令，以及處理器何以知

道它下次要執(zhí)行哪條指令呢？為了解決這些問題，所有的計算機都有若干的特殊寄存器，如

用一個專門的寄存器來指示一條要執(zhí)行的指令稱程序計數(shù)器PC,同時還有一個專門的寄存

器用來指示處理器狀態(tài)的，稱為程序狀態(tài)字PSW。

主要內(nèi)容包括所謂處理器的狀態(tài)通常包括條件碼-反映指令執(zhí)行后的結(jié)果特征；中斷屏

蔽碼-指出是否允許中斷，有些機器如PDP-11使用中斷優(yōu)先級；CPU的工作狀態(tài)-管態(tài)還

是目態(tài)，用來說明當(dāng)前在CPU上執(zhí)行的是操作系統(tǒng)還是?般用戶，從而決定其是否可以使

用特權(quán)指令或擁有其它的特殊權(quán)力。

2.11CPU如何發(fā)現(xiàn)中斷事件？發(fā)現(xiàn)中斷事件后應(yīng)做什么工作？

答：處理器的控制部件中增設(shè)一個能檢測中斷的機構(gòu)，稱為中斷掃描機構(gòu)。通常在每條

指令執(zhí)行周期內(nèi)的最后時刻中掃描中斷寄存器，詢?yōu)槭欠裼兄袛嘈盘柕絹?。若無中斷信號，

就繼續(xù)執(zhí)行下一條指令。若有中斷到來，則中斷硬件將該中斷觸發(fā)器內(nèi)容按規(guī)定的編碼送入

程序狀態(tài)字PSW的相應(yīng)位（IBM-PC中是第16-31位），稱為中斷碼。

發(fā)現(xiàn)中斷事件后應(yīng)執(zhí)行相中斷處理程序，先由硬件進行如下操作：

1、將處理器的程序狀態(tài)字PSW壓入堆棧

2、將指令指針I(yè)P（相當(dāng)于程序代碼段落的段內(nèi)相對地址）和程序代碼段基地址寄存器

CS的內(nèi)容壓入堆棧，以保存被子中斷程序的返回地址。

3、取來被接受的中斷請求的中斷向量地址（其中包含有中斷處理程序的IP,CS的內(nèi)

容），以便轉(zhuǎn)入中斷處理程序。

4、按中斷向量地址把中斷處理程序的程序狀態(tài)字取來，放入處理器的程序狀態(tài)字寄存

器中。

2.16有四個作業(yè)A,B,C,D,要求定時喚醒運行，其要求如下：

A20秒后運行，經(jīng)過40秒后再次運行。

B30秒后運行。

C30秒后運行，經(jīng)過25秒后再次運行。

D65秒后運行。

答：請建立相應(yīng)原時鐘隊列。

ABCCAD

201002555

2.18什么叫重定位？有哪幾種重定位技術(shù)？有何區(qū)別？

答：故重定位是把程序中相對地址變換為絕對地址。

對程序進行重定位的技術(shù)目前按重定位的時機區(qū)分為兩種：靜態(tài)重定位和動態(tài)重定位。

靜態(tài)重定位是要把程序中所胡與地址有關(guān)的項在程序運行前（確切地說是在程序裝入主

存時）修改好，它是在程序裝入主存時由連接裝入程序進行重定位

動態(tài)重定位不是在程序裝入過程中進行。在處理器每次訪問主存時，由動態(tài)地址變換機

構(gòu)（硬件）自動進行把相對地址轉(zhuǎn)換為絕對地址。

2.20對比絕對裝入程序和連接裝入程序。

答：在個人計算機中用戶能使用的主存起始地址是可以知道的。這種機器上的編譯和匯

編程序往往把源程序翻譯成絕對地址形式的目標(biāo)程序（以該機器的用戶可用的起始地址作為

基準(zhǔn)地址）。因此當(dāng)需要再次裝入目標(biāo)程序時，就十分簡單-，沒有什么重定位問題。只要按

其給出的起始地址依次地將程序讀入即可。

在對多數(shù)多道程序系統(tǒng)使用相對裝程序（連接裝入程序）。其主要功能是把主程序同被

其調(diào)用的的各子程序連接裝配成一個大的完整的程序，并裝入主存運行。

第3章進程管理

P.57頁

3.1為什么要引入進程概念？進程的基本特征是什么？它與程序有何區(qū)別。

答：進程的概念是操作系統(tǒng)中最基本、最重要的概念。為了核畫系統(tǒng)內(nèi)部出現(xiàn)的情況，

描述系統(tǒng)內(nèi)部各作業(yè)的活動規(guī)律而引進的一個新的概念，山于處在這樣一個多道程序系統(tǒng)所

帶來的更為復(fù)雜的環(huán)境中，程序具有了并行、制約、動態(tài)的特征，使得原來的程序概念已難

以刻畫和反映系統(tǒng)中的情況了。

進程的基本特征是動態(tài)性，并行性；

進程與程序的區(qū)別：

1、進程是程序的執(zhí)行，故進程屬于動態(tài)概念，而程序是一組指令的有序集合，是靜態(tài)

的概念。

2、進程既然是程序的執(zhí)行，或者說是“一次運行活動”，因而它是有生命過程的。從

投入運行到運行完成，或者說是進程存在誕生（建立進程）和死亡（撤消進程）。換言之，

進程的存在是暫時，而程序的存在是永久的。

3、進程是程序的執(zhí)行，因此進程的組成應(yīng)包括程序和數(shù)據(jù)。除此之外，進程還山記錄

進程狀態(tài)信息的“進程控制塊”組成。

4、一個程序可能對應(yīng)多個進程。

5、一個進程可以包含多個程序。

3.2定義以下術(shù)語：程序、過程、處理器、進程、用戶、任務(wù)和作業(yè)。

答：程序-是完成某個功能的指令的集合；

過程-計算機處理一次事件的整個流程

處理器-計算機的核心硬件部份，負責(zé)處理用戶要求的各種運算任務(wù)。

進程-是一個具有??定獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。

用戶-是指計算機為他工作的人；

任務(wù)-是用戶要求計算機處理的事情。

作業(yè)-是用戶要求計算機給予計算（或處理）的一個相對獨立的任務(wù)。

3.3為什么為什么說PCB是進程存在的惟一標(biāo)志？

答：操作系統(tǒng)用一個稱為進程控制塊PCB的數(shù)據(jù)結(jié)構(gòu)來記錄本進程的屬性。進程控制

塊PCB是操作系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)。PCB的作用不但是記錄進程的屬性信息，以便操

作系統(tǒng)對進程進行控制和管理。而且PCB標(biāo)志進程的存在，操作系統(tǒng)根據(jù)系統(tǒng)中是否有該

進程的進程控制塊PCB而知道該進程的存在與否。系統(tǒng)在建立進程的同時就建立該進程的

PCB,在撤消一個進程時也就撤消其PCB。所以說進程的PCB對進程來說是它存在的具體

的物理標(biāo)志和體現(xiàn)。PCB對操作系統(tǒng)來說，也是調(diào)度進程的主要原因的數(shù)據(jù)基。

3.10試列舉出進程狀態(tài)轉(zhuǎn)換的典型原因，詳細列出引起進程調(diào)度的因素。

答：（1）系統(tǒng)有時可能出故障或某些功能受到破壞。這時就需要暫時將系統(tǒng)中的進程掛起，

以便系統(tǒng)把故障消除后，再把這些進程恢復(fù)到原來狀態(tài)。

（2）用戶檢查自己作業(yè)的中間執(zhí)行情況和中間結(jié)果時，因同預(yù)期想法不符而產(chǎn)生懷疑。這

時用戶要求掛起他的進程，以便進行某些檢查和改正。

（3）系統(tǒng)中有時負荷過重（進程數(shù)過多），資源數(shù)相對不足，從而造成系統(tǒng)效率下降。此時

需要掛起一部分進程以調(diào)整系統(tǒng)負荷，等系統(tǒng)中負荷減輕后再將被掛起進程恢復(fù)運行。

如果一個進程原來處于運行狀態(tài)或活動就緒狀態(tài)，此時可因掛起命令而由原來狀態(tài)變?yōu)閽炱?/p>

就緒狀態(tài)，此時它不能參與爭奪處理器，即進程調(diào)度程序不會把處于掛起就緒狀態(tài)的進程挑

選來運行。當(dāng)處于掛起就緒狀態(tài)的進程接到解除掛起命令后，它就由原狀態(tài)變?yōu)榛顒泳途w狀

態(tài)。如果一個進程原來處于活動阻塞狀態(tài)，它可因掛起命令而變?yōu)閽炱鸬却隣顟B(tài)，直到解除

掛起命令才能把它重新變?yōu)榛顒拥却隣顟B(tài)。處于掛起等待狀態(tài)的進程，其所等待的事件（如

正在等待輸入輸出工作完成，等待別的進程發(fā)給它一個消息）在該進程掛起期間并不停止這

些事件的進行。因而當(dāng)這些事件發(fā)生后（輸入輸出完成，消息已發(fā)送來了），該進程就由原

來掛起阻塞狀態(tài)變?yōu)閽炱鹁途w狀態(tài)。

第4章多線程

P78

4.3進程和線程的關(guān)系是什么？線程是由進程建立的，是嗎？線程對實現(xiàn)并行性比進程機制

有何好處？

答：線程是進程中相對獨立的一個控制流序列；線程也稱為輕質(zhì)進程。

不是，好處有：（1）用于創(chuàng)建和撤消線程的開銷比創(chuàng)建和撤消進程的系統(tǒng)開銷（CPU時間）

要少得多。（2）CPU在線程之間開關(guān)時的開銷也遠比進程之間開關(guān)的開銷小。（3）線程機

制也增加了通訊的有效性。（4）方便作簡化了用戶的程序結(jié)構(gòu)工作。

4.4什么是線程，它有哪些性質(zhì)？

答：線程是進程內(nèi)一個相對獨立的、可調(diào)度的執(zhí)行單位。

它有以下性質(zhì)：

（1）線程是進程內(nèi)的一個相對獨立的可執(zhí)行單元。因此不妨把線程看作是應(yīng)用中的一個子

任務(wù)的執(zhí)行。

（2）線程是操作系統(tǒng)中基本高度單元，因此線程中應(yīng)包含有調(diào)度所需的必要信息。

(3)由于線程是被調(diào)度的基本單位，而進程不是調(diào)度的單元。所以每個進程在創(chuàng)建時，至

少需要同時為該進程創(chuàng)建一個線程。也就是說進程中至少要有一個或一個以上線程，否則該

進程無法被調(diào)度執(zhí)行。

(4)需要時，線程可以創(chuàng)建其他線程。

(5)進程是被分給并擁有資源的基本單元，同一進程內(nèi)的多個線程共享該進程的資源。但

線程并不擁有資源，只是使用它們。

(6)由于共享資源(包括數(shù)據(jù)和文件)，所以線程間需要通信和同步機制。

(7)線程有生命期，有誕生和死亡。在生命期中有狀態(tài)的變化。

第3章操作系統(tǒng)

3.1概述

3.1.1本章的特點及學(xué)習(xí)建議

操作系統(tǒng)是計算機系統(tǒng)中最基本的系統(tǒng)軟件，目的是為了方便用戶和管理、控制計算機硬、

軟件資源，因此有人把它形容為計算機系統(tǒng)的“管家”。我們學(xué)習(xí)操作系統(tǒng)，并不是為了去

開發(fā)、編制操作系統(tǒng)軟件，主要是了解它的各部分構(gòu)成及工作原理，以便能更合理、有效地

使用它。

操作系統(tǒng)是計算機技術(shù)與管理技術(shù)的結(jié)合，因此它是一個獨立完整的管理軟件，在其中應(yīng)用

了數(shù)據(jù)結(jié)構(gòu)中的棧、隊、表、樹等結(jié)構(gòu)形式，我們在學(xué)習(xí)過程中應(yīng)與前面學(xué)過的數(shù)據(jù)結(jié)構(gòu)知

識聯(lián)系起來，以加深對它的理解。

當(dāng)今操作系統(tǒng)的種類很多，建議大家能多上機操作，體會操作系統(tǒng)的作用。如有可能，希望

能在多種不同的操作系統(tǒng)上進行操作，比較其異同，這樣可以大大增加對操作系統(tǒng)的感知認

識，更進一步體會操作系統(tǒng)在計算機中所發(fā)揮的作用。

3.1.2重點和難點

操作系統(tǒng)的出現(xiàn)及發(fā)展過程是隨著計算機技術(shù)的發(fā)展以及用戶對計算機使用的要求而不斷

改進的。為了充分利用計算機系統(tǒng)的資源，多道程序設(shè)計是當(dāng)前操作系統(tǒng)的重要核心技術(shù)之

一，也就是允許在一臺計算機上同時運行多道程序，因而出現(xiàn)了很多與多道程序有關(guān)的概念,

如并發(fā)性、共享性、不確定性、虛擬性等。為使多道程序能協(xié)調(diào)有序地工作，一定要有多種

技術(shù)措施來保證，從而提出為解決多道程序并發(fā)運行同步、互斥、死鎖等問題的方法。這些

都是操作系統(tǒng)中比較重要但又是比較難理解的部分。

3.1.3有關(guān)的概念及特性

1.操作系統(tǒng)發(fā)展的幾個階段

(1)手工操作階段：沒有操作系統(tǒng)

(2)早期批處理階段：分為早期聯(lián)機批處理與早期脫機批處理階段。它們節(jié)省了用戶操作

時間并發(fā)揮了主機的高速計算能力。

(3)執(zhí)行系統(tǒng)階段：借助通道和中斷技術(shù)，可以使CPU和各種外設(shè)并行操作。

(4)多道程序系統(tǒng)階段：實現(xiàn)多道程序在一臺機器上同時運行，可以實現(xiàn)資源的最佳利用。

2.操作系統(tǒng)的分類

(1)多道批處理操作系統(tǒng)

成批處理作業(yè)，提高了作業(yè)的吞吐量，也提高了系統(tǒng)資源的利用率。缺點是用戶以脫機

方式使用計算機，在計算過程中無法與機器交互。

(2)分時系統(tǒng)

一臺計算機與多臺終端相連接，終端上的用戶可以同時使用計算機。具有同時性與交互性特

點。

(3)實時系統(tǒng)

對于外來信息具有瞬時響應(yīng)的能力，多用于實時控制和實時信息處理領(lǐng)域。具有及時性和高

可靠性特點。

以上是三種最基本的操作系統(tǒng)類型。自20世紀80年代開始，微型機的普及以及計算機網(wǎng)絡(luò)

的發(fā)展，出現(xiàn)了網(wǎng)絡(luò)操作系統(tǒng)及分布式操作系統(tǒng)，這里不再詳述。

3.操作系統(tǒng)的功能及特性

(1)操作系統(tǒng)的功能

操作系統(tǒng)的功能概括起來就是方便用戶和充分利用計算機資源。具體的就是存儲管理、處

理器管理、設(shè)備管理、文件管理及用戶接口幾部分。

(2)操作系統(tǒng)的特性

?并發(fā)性

系統(tǒng)內(nèi)部具有并發(fā)機制，能協(xié)調(diào)多個終端用戶同時使用計算機資源，能控制多道程序同時

運行。

?共享性

由于操作系統(tǒng)具有并發(fā)性，整個系統(tǒng)的軟、硬件資源可以由多個程序共同使用。并發(fā)性與共

享性相輔相成，是操作系統(tǒng)的兩個基本特性。

?不確定性

在多道程序設(shè)計中，由于運行環(huán)境的影響，程序的運行時間、運行順序等均具有不確定性。

?虛擬性

“虛擬”是指把一個物理客體變?yōu)槿舾蓚€邏輯上的對應(yīng)物，從而擴展了它的功能。它體現(xiàn)在

操作系統(tǒng)的方方面面。如多道程序在單CPU的計算機上同時運行，使得多個程序好像獨占了

一個CPU：若干終端用戶分時使用一臺主機，好像每人獨占了一臺計算機；虛擬存儲器使得

比存儲器容量大得多的程序能在其上運行；虛擬設(shè)備可以把一臺獨占的輸入、輸出設(shè)備變成

多道程序共享的設(shè)備等。這些都體現(xiàn)了操作系統(tǒng)的虛擬性，希望大家能在后面幾節(jié)中加以體

會。

3.2存儲管理

3.2.1基本功能和相關(guān)的概念

1.存儲管理的基本功能

(1)內(nèi)存空間的分配和去分配

(2)地址轉(zhuǎn)換

(3)存儲空間保護

(4)內(nèi)存空間的擴充

2.有關(guān)存儲管理的概念

(1)絕對地址與相對地址

絕對地址又稱物理地址或?qū)嵉刂?，是指程序在主存儲器中的地址編碼。

相對地址又稱邏輯地址或虛地址，是指程序本身的地址編碼，一般從零地址開始。

(2)存儲空間與地址空間

存儲空間又稱物理地址空間，由絕對地址對應(yīng)的主存空間組成。

地址空間又稱邏輯地址空間，由邏輯地址的集合組成。

(3)重定位

可執(zhí)行程序裝入內(nèi)存時，邏輯地址與絕對地址一般是不相符的，必須通過地址轉(zhuǎn)換機構(gòu)將

邏輯地址轉(zhuǎn)換成絕對地址，稱為重地位。重定位的方式有靜態(tài)重定位和動態(tài)重定位兩種。

靜態(tài)重定位是在程序裝入時完成的，而動態(tài)定位是在程序運行時完成的。

存儲管理的形式很多，致使很多同學(xué)感到內(nèi)容很多又很零碎，因此建議大家在學(xué)習(xí)這部分

內(nèi)容時.，不要把各種方式孤立起來，而應(yīng)用連貫、發(fā)展的眼光來看待，因為各種形式之間是

有聯(lián)系的，一般來說，后者是前者的改進與補充。

3.2.2實存儲管理

失存儲管理方式要求把每一個作業(yè)放在主存的一片連續(xù)區(qū)域中，為了滿足多道程序的要

求，必須把主存的用戶區(qū)分成若干個連續(xù)分區(qū)。根據(jù)不同的分區(qū)劃分方式，可以有以下幾種

管理形式：

固定分區(qū)分配

把主存用戶區(qū)劃分成若干大小不等的分區(qū)，按作業(yè)的大小選擇合適的分區(qū)。

問題：作業(yè)地址空間不可能與分區(qū)大小絕對相等，因而出現(xiàn)了“碎片”，浪費了存儲空間。

2.可變分區(qū)分配

根據(jù)作業(yè)實際需求量對用戶區(qū)進行動態(tài)分割，系統(tǒng)設(shè)置一張鏈表或數(shù)組，用來登記當(dāng)時用戶

區(qū)的空閑塊，作為動態(tài)分配和回收主存空間的依據(jù)?？勺兎謪^(qū)常用的存儲空間分配策略有三

種。

(1)首次適應(yīng)算法：選擇所碰到的第一個滿足作業(yè)存儲量要求的塊分配給用戶。

(2)最佳適應(yīng)算法：選擇滿足作業(yè)需求塊中最小的一塊分配給用戶。

(3)最差適應(yīng)算法：在空閑塊中選出滿足作業(yè)要求的最大塊分配給用戶。

問題：經(jīng)過多次分配和回收以后，用戶區(qū)中可能會出現(xiàn)很多零碎的空間，不足以放入一個作

業(yè)，也稱為“碎片”，使新作業(yè)無法進入內(nèi)存。

3.可重定位分區(qū)分配

為解決可變分區(qū)分配的碎片問題，在適當(dāng)時候?qū)?nèi)存進行“緊縮”，即將內(nèi)存中的作業(yè)移向

存儲區(qū)一端，而將空閑塊集中到另一端，構(gòu)成較大的空閑塊以便新的作業(yè)進入。

由于緊縮工作是在程序執(zhí)行過程中進行的，因此要對內(nèi)存中的程序重新定位，稱為動態(tài)重定

位，它需要借助一些硬件設(shè)備來完成。

問題：緊縮過程需要耗費時間，不宜頻繁進行。

4.內(nèi)存“擴充”技術(shù)

在上述分區(qū)分配方式下，當(dāng)內(nèi)存空間小于作業(yè)所需的空間時，作業(yè)就無法進入內(nèi)存運行。在

不增加物理內(nèi)存容量時，一般采用“覆蓋”和“交換”技術(shù)來“擴充”內(nèi)存。

(1)覆蓋

系統(tǒng)提供用戶覆蓋機構(gòu)，它將整個作業(yè)分為常駐內(nèi)存和覆蓋兩部分，用戶只要將最大的子程

序作為覆蓋區(qū)告訴系統(tǒng)，即可運行。

問題：要求用戶把作業(yè)如何分段和作業(yè)的可覆蓋情況寫成覆蓋描述文件，同作業(yè)一起交給操

作系統(tǒng)。

(2)交換

當(dāng)內(nèi)存不夠時，系統(tǒng)按一定的策略設(shè)法騰空?些內(nèi)存空間，也即采用強制方法把內(nèi)存中部分

內(nèi)容暫時放到外存中去。

問題：以整個作業(yè)進行內(nèi)外存交換，代價較大。

3.2.3虛擬存儲管理

虛擬存儲管理是通過把內(nèi)、外存統(tǒng)一起來管理，給用戶造成一種仿佛系統(tǒng)內(nèi)具有巨大內(nèi)存供

用戶使用的假象。

虛擬存儲管理與實存儲管理在理念上的差別是:虛擬存儲管理認為作業(yè)在內(nèi)存空間中不一定

要求連續(xù)存放，其次作業(yè)在運行時不必全部都同時放在內(nèi)存中，可以允許有一部分放在外存

中，只要保證當(dāng)時被執(zhí)行的那部分在內(nèi)存即可。

虛擬存儲管理把作業(yè)的相對地址稱為“虛擬地址”，作業(yè)的地址空間為“虛擬地址空間”；把

分配給該作業(yè)的物理地址稱為“實在地址”，該存儲空間為“實在地址空間”。作業(yè)在運行時,

只要時時保證作業(yè)的實在地址與虛擬地址的對應(yīng)關(guān)系，而并不在乎虛擬地址空間與實在地址

空間大小是否相等，實際上實在地址空間遠比虛擬地址地址空間小。虛擬存儲器的容量取決

于內(nèi)存與外存的容量。一個虛擬存儲器的最大容量由計算機的地址結(jié)構(gòu)確定。

1.分頁存儲管理

(1)基本思路

?頁把作業(yè)的邏輯地址空間分成若干個長度相等的區(qū)域，稱為頁。

?頁架(塊)把內(nèi)存空間劃分成若干個與頁面長度相等的區(qū)域，稱為頁架。程序裝入內(nèi)存

時，每頁對應(yīng)一個頁架，這些頁架可以是不連接的，也不要求所有頁面同時裝入內(nèi)存中。

?頁表系統(tǒng)為每道作業(yè)建立一張頁血映射表，筒稱頁表，記錄相應(yīng)頁在內(nèi)存中對應(yīng)的頁架

號。

(2)地址轉(zhuǎn)換

采用動態(tài)重定位。

?地址變換機構(gòu)自動將邏輯地址分解為頁號P和頁內(nèi)位移do

?以頁號為索引去檢索頁表，得到該頁對應(yīng)的頁架號p'。

?將頁內(nèi)位移d拼接在頁架號后，得到相應(yīng)的物理地址。

?檢索頁表時，若對應(yīng)該頁的狀態(tài)為“0”，說明該頁當(dāng)時不在內(nèi)存中，則發(fā)出缺頁中斷，把

該頁血調(diào)入內(nèi)存后再進行地址轉(zhuǎn)換工作。

(3)頁面更換

當(dāng)系統(tǒng)將缺頁從外存調(diào)入內(nèi)存時，發(fā)現(xiàn)一無可用的物理空間時，則須從內(nèi)存中淘汰一個頁面

以騰出空間裝入缺頁。若被淘汰的頁面選擇不當(dāng)，可能會出現(xiàn)剛被淘汰的頁面馬上又要被訪

問，使系統(tǒng)花費大量的時間忙于進行頻繁的頁面交換，降低系統(tǒng)效率，甚至導(dǎo)致系統(tǒng)癱瘓，

這種現(xiàn)象稱為抖動現(xiàn)象。

常用的淘汰算法有：

?先進先出法(FIFO)

選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。

?最近最久未使用法(LRU)

選擇離當(dāng)前時間最久未使用過的頁面淘汰。

(4)優(yōu)缺點

?優(yōu)點虛存量大，用戶不必擔(dān)心內(nèi)存不夠；不要求作業(yè)連續(xù)存放，有效地解決了“碎片”

問題。

?缺點要求硬件支持，增加了成本；要處理頁面中斷，系統(tǒng)開銷較大，處理不當(dāng)還可能產(chǎn)

生“抖動”。

2.分段存儲管理

(1)基本思路

?段作業(yè)中每一個模塊稱為段，每段占有連續(xù)的地址空間，其邏輯地址是二維的，由段號

和段內(nèi)地址組成。

?段表系統(tǒng)為每個作業(yè)建立一張段表，記錄該段在內(nèi)存中的起始地址和段長。各段可存放

在內(nèi)存不同的分區(qū)中，也不要求所有的段同時調(diào)入內(nèi)存中。

(2)地址轉(zhuǎn)換

采用動態(tài)重定位

?地址轉(zhuǎn)換機構(gòu)取出邏輯地址的段號和段內(nèi)地址。

?根據(jù)段號檢索段表，找到該段的對應(yīng)表目。

?將該段的起始地址與段內(nèi)地址想加得到絕對地址。

?若對應(yīng)該段狀態(tài)為“0”，說明該段不在內(nèi)存，需要通過中斷調(diào)入。

(3)段的共享

由于段是有完整的邏輯意義，可以提供給多個作業(yè)共享。若多個作業(yè)段表中的某一項指向內(nèi)

存的同一地址，則內(nèi)存中以該地址為起始地址的那一段便被共享了。

(4)優(yōu)缺點

?優(yōu)點方便用戶編程，便于共享與保護，便于動態(tài)鏈接和增長。

?缺點增加硬件成本，由于段的長度不等，會出現(xiàn)與分區(qū)管理相同的“碎片”問題。

3.段頁式存儲管理

(1)基本思路

將段式與頁式管理結(jié)合起來，克服各自存在的一些問題。它把作業(yè)分成若干段，每個段分成

若干頁。為了實現(xiàn)地址轉(zhuǎn)換，必須為每個作業(yè)配置一張段表和若干張頁表。

(2)地址轉(zhuǎn)換

作業(yè)的邏輯地址是二維的，包括段號和段內(nèi)地址，其中段內(nèi)地址又包含頁號和頁內(nèi)地址。

?地址轉(zhuǎn)換機構(gòu)取出邏輯地址，再將段內(nèi)地址細分為頁號和頁內(nèi)地址。

?根據(jù)段號檢索段表，取出相應(yīng)的頁架號。

?把頁架號與頁內(nèi)地址合并得到物理地址。

(3)優(yōu)缺點

?優(yōu)點具有分段分頁的優(yōu)點。

?缺點更增加硬件成本與軟件復(fù)雜性。

3.3處理器管理

中央處理器(CPU)是計算機系統(tǒng)中負責(zé)運算與控制的部件，調(diào)入內(nèi)存中的作業(yè)只有占有了

CPU才能運行。在單CPU的系統(tǒng)中，要實現(xiàn)多道程序并發(fā)運行，一定要合理地分配CPU,使

得從宏觀上看各個程序都在隨著時間向前推進。在這一部分將討論三個問題：

(1)當(dāng)多個用戶把各自的作業(yè)提交給計算機后，操作系統(tǒng)如何對它們進行調(diào)度管理。

(2)已進入內(nèi)存中的作業(yè)，如何對它們合理地分配CPU。

(3)如何解決多道程序并發(fā)運行時出現(xiàn)的同步、互斥與死鎖問題。

3.3.1基本概念與術(shù)語

1.作業(yè)

作業(yè)是用戶交給計算機運行的程序、數(shù)據(jù)及說明。一個作業(yè)可以分解成若干個作業(yè)步。

2.進程

當(dāng)系統(tǒng)將某一個用戶程序調(diào)入內(nèi)存運行時，稱為進程。這是由于多道程序環(huán)境下實現(xiàn)資源共

享和程序并發(fā)運行的需要，它具有以下的基本特性：

(1)動態(tài)特性進程是程序的一次執(zhí)行過程，具有“創(chuàng)建一執(zhí)行一撤消”的生存周期。

(2)并發(fā)特性內(nèi)存中眾多進程不僅可隨機地并發(fā)產(chǎn)生和消亡，同時可以并行地活動。

(3)獨立性進程在邏輯上是獨立的，在獲得必須的資源后，可以按照各自目的，以不可

預(yù)知的速度向前推行。

(4)相互制約性由于共享資源和進程之間某些協(xié)同動作，有些進程間會有相互制約的關(guān)

系。

因此程序是一種靜態(tài)的觀點，進程則反映了操作系統(tǒng)動態(tài)活動的內(nèi)在本質(zhì)。

3.管態(tài)、目態(tài)

(1)管態(tài)此時系統(tǒng)只執(zhí)行造作系統(tǒng)的特權(quán)指令，不允許執(zhí)行用戶指令。

(2)目態(tài)系統(tǒng)處于用戶執(zhí)行狀態(tài)。

3.3.2作業(yè)調(diào)度

作業(yè)調(diào)度主要是實現(xiàn)對作業(yè)的組織、輸入/輸出、調(diào)度和運行控制。不同的操作系統(tǒng)對

作業(yè)有不同的處理方式，主要分為批處理作業(yè)和交互方式處理作業(yè)兩類。

1.批處理作業(yè)的管理

在批處理系統(tǒng)中，由于用戶不能直接與計算機交互，因此在進入計算機系統(tǒng)之前，除了要準(zhǔn)

備好源程序和初始數(shù)據(jù)外，還必須用該操作系統(tǒng)提供的作業(yè)控制語言來書寫作業(yè)控制說明

書，規(guī)定如何控制作業(yè)運行。

(1)作業(yè)狀態(tài)及轉(zhuǎn)換

一個作業(yè)在它的生命周期內(nèi)要經(jīng)過提交、收容、執(zhí)行、完成四個階段，每一個階段稱為作業(yè)

的一種狀態(tài)。

為了描述和管理系統(tǒng)內(nèi)的作業(yè)，還必須為每道作業(yè)建立一個專門的數(shù)據(jù)結(jié)構(gòu)，稱為作業(yè)捽制

塊（JCB）它包含了系統(tǒng)對作業(yè)進行管理所必需的信息，作業(yè)管理就是對作業(yè)各個階段進行

宏觀控制。

（2）作業(yè)調(diào)度

在批處理系統(tǒng)中，作業(yè)調(diào)度程序按照某種調(diào)度策略從收容狀態(tài)隊列中選擇某些作業(yè)進入內(nèi)

存。調(diào)度的關(guān)鍵是在于確定調(diào)度算法，以獲得一個較好的作業(yè)搭配，使得系統(tǒng)資源得到高效

的利用。

衡量算法的性能指標(biāo)有：

?周轉(zhuǎn)時間作業(yè)從進入系統(tǒng)直到完成所經(jīng)歷的時間。

?平均周轉(zhuǎn)時間被測定作業(yè)數(shù)（n）的周轉(zhuǎn)時間平均值。

?系統(tǒng)吞吐量系統(tǒng)在單位時間內(nèi)平均完成的作業(yè)數(shù)。

（3）調(diào)度算法

作業(yè)調(diào)度算法很多，這里介紹幾種常用的算法：

?先來先服務(wù)（FCFS）

按作業(yè)到達系統(tǒng)的先后次序調(diào)度它們運行。

?短作業(yè)優(yōu)先（SJF）

選擇運行時間較短的作業(yè)先運行。這樣可使作業(yè)流的平均周轉(zhuǎn)時間取值最小，但對長作業(yè)不

公平。

?最高響應(yīng)比優(yōu)先（HRF）

響應(yīng)比=等待時間/運行時間

優(yōu)先選擇響應(yīng)比最大的作業(yè)，他兼顧了短作業(yè)與等待時間長的作業(yè)。

?優(yōu)先數(shù)法

按操作員或用戶指定的作業(yè)優(yōu)先級高的作業(yè)首先運行。

實際系統(tǒng)中往往采用幾種算法的組合形式，以提高系統(tǒng)的整體效率。

2.交互式作業(yè)管理

在分時系統(tǒng)中，用戶通過終端和系統(tǒng)提供的終端命令語言向系統(tǒng)提供作業(yè)。作業(yè)的提交方式

是由用戶動態(tài)地提交，即每完成一個作業(yè)步動作后，系統(tǒng)給出相應(yīng)的回答信息，用戶繼續(xù)提

交下一個作業(yè)步，知道作業(yè)全部完成。山于系統(tǒng)對終端用戶提交的每一作業(yè)步必須加以識別

并立即解釋執(zhí)行，因此系統(tǒng)不再設(shè)置作業(yè)的收容狀態(tài)，也不存在作業(yè)調(diào)度等問題。

有些系統(tǒng)同時支持批處理和分時功能，則用戶可以提供任意一種類型的作業(yè)，其中交互式作

業(yè)稱為“前臺”作業(yè)，批處理作業(yè)稱為“后臺”作業(yè)。

3.3.3進程調(diào)度

進程調(diào)度的任務(wù)是控制、協(xié)調(diào)進程對CPU的競爭，按照一定的調(diào)度算法，使某一個就緒的進

程得到CPU,轉(zhuǎn)成運行狀態(tài)。

1.進程的狀態(tài)及轉(zhuǎn)換

一個進程在它的生命期內(nèi)有三種基本狀態(tài)：

就緒進程具備運行條件，但尚未占用CPU；

運行進程正在占用CPU；

等待（阻塞）進程由于等待某一事件不能享用CPU。

當(dāng)進程處于運行狀態(tài)時，它是微觀意義下的運行，而不管進程處于何種狀態(tài)，只要它已開始

執(zhí)行而尚未結(jié)束執(zhí)行，都是宏觀意義下的運行。

和作業(yè)管理相似，當(dāng)作業(yè)一旦進入內(nèi)存構(gòu)成進程后，系統(tǒng)為每個進程建立一個進程控制塊

（PCB）,記錄有關(guān)該進程的固有信息以及動態(tài)信息。

2.進程控制

操作系統(tǒng)必須提供一組與進程控制有關(guān)的原語（系統(tǒng)調(diào)用）供用戶編程時調(diào)用。

(1)創(chuàng)建進程為調(diào)用者動態(tài)創(chuàng)建一個進程。

(2)撤消進程停止該進程運行，釋放它所占有的資源。

(3)掛起進程把該進程暫時置為阻塞狀態(tài)。

(4)激活進程把該進程從阻塞態(tài)改為就緒態(tài)。

3.進程調(diào)度

按照一定的調(diào)度算法，使某一就緒進程得到CPU,轉(zhuǎn)換成運行狀態(tài)。衡量調(diào)度算法的指標(biāo)主

要有：

?CPU利用率CPU處于忙狀態(tài)的時間與開機運行總時間的比值。

?等待時間指在就緒狀態(tài)中進程的等待時間。

?響應(yīng)時間指在分時系統(tǒng)中，用戶在終端上發(fā)一條命令直到系統(tǒng)作出回答所需的時間。

4.調(diào)度算法

進程調(diào)度算法有些和作業(yè)調(diào)度相似，如先來先服務(wù)(FCFS)、短進程優(yōu)先(SPF)、優(yōu)先級調(diào)

度等。還有適用于分時系統(tǒng)的輪轉(zhuǎn)調(diào)度法。

?先來先服務(wù)按進入就緒隊列先后次序獲取CPU,這是一種不可搶占的方式。

?短進程優(yōu)先根據(jù)下一次所需時間的長短，從就緒隊列中選擇運行時間最短的進程首先占

有CPU。

?優(yōu)先級調(diào)度按進程的優(yōu)先級高低確定占有CPU的次序。

?輪轉(zhuǎn)調(diào)度法進程先按FIFO規(guī)則排成隊列，每次從隊首取出個進程分配CPU,并規(guī)定

執(zhí)行完一個時間片后便被剝奪，并被送到隊尾，如此反復(fù)。

實際系統(tǒng)會根據(jù)不同的系統(tǒng)目標(biāo)，結(jié)合各種算法特點采用相應(yīng)的調(diào)度算法。

3.3.4多道程序并發(fā)運行出現(xiàn)的問題

1.進程的同步與互斥

進程的同步：完成同一任務(wù)的進程間，山于需要在某些位置上協(xié)調(diào)它們的工作而互相等待與

相互交換信息所產(chǎn)生的制約。

進程的互斥：進程之間因相互競爭使用獨占型資源而產(chǎn)生的制約。

(1)臨界區(qū)問題

一次僅允許一個進程使用的資源稱為臨界資源，各個進程必須互斥地執(zhí)行的那種程序段稱為

臨界區(qū)。對臨界區(qū)的調(diào)度原則為：當(dāng)沒有進程在臨界區(qū)時，允許?個進程立即進入；若已有

一進程在臨界區(qū)內(nèi)，則其他需進入的進程必須等待，且必須在有限的時間內(nèi)得到滿足。

(2)原語

原語本身不是一條機器指令，而是山若干條指令組成的程序段，它是機器指令的擴充。它在

進程管理中能完成某些特定的功能，例如前面提到的進程控制原語，以及后面將提到的P.V

操作等。原語是在管態(tài)下運行，因此在執(zhí)行中一次完成不能被打斷。

(3)P.V操作

用常規(guī)的程序來實現(xiàn)進程間的同步和互斥關(guān)系需要復(fù)雜的算法，因此引入P.V操作，P.V操

作都是原語，在執(zhí)行期間是不可分割的。

(4)用P.V操作實現(xiàn)進程之間的互斥和同步

?實現(xiàn)互斥：令S初值為1,進程A,B競爭臨界區(qū)的程序，可以寫成：

進程A進程B

P(S)P(S)

臨界區(qū)臨界區(qū)

V(S)V(S)

?實現(xiàn)同步：設(shè)Si初值為n,表示緩沖區(qū)中有n個位置等待裝入信息；S2初值為0,表示緩

沖區(qū)中無信息可取。

進程A進程B

P(S|)P(S2)

把信息送入緩沖區(qū)從緩沖區(qū)取走信息

V(S2)V(Sj)

在練習(xí)題中將提供一些采用P.V操作解決同步與互斥的習(xí)題，希望能通過分析這些例子，對

解決操作系統(tǒng)內(nèi)的同步、互斥問題有所啟發(fā)。

2.死鎖

(1)死鎖的定義和必要條件

?死鎖的定義在一個進程集合中，若每個進程都在等待某些時間的發(fā)生，而這些事件又必

須由這個進程集合中的某些進程來產(chǎn)生，則稱該進程集合處于死鎖狀態(tài)。

?產(chǎn)生死鎖的四個必要條件

①互斥系統(tǒng)中必須存在互斥使用的資源。

②占有等待進程已分配到了某些資源，但還須等待另外的資源，而對已分配到的資源并不

釋放。

③非剝奪在出現(xiàn)死鎖的系統(tǒng)中，一定存在有不可剝奪的資源，即在該進程未主動釋放之前,

其他進程不可奪走該資源。

④循環(huán)等待形成一個處于等待狀態(tài)的進程集合｛P。，P”…，Pn｝，其中Pi等待的資源被

P/D占有，Pn等待的資源被P。占有。

(2)死鎖的預(yù)防

只要使死鎖產(chǎn)生的四個必要條件之一不成立，死鎖就不會出現(xiàn)。

(3)死鎖的避免

死鎖的避免是在系統(tǒng)運行過程中小心地避免死鎖的最終發(fā)生。最著名的是銀行算法。

安全狀態(tài)：安全狀態(tài)是指如果存在一個由系統(tǒng)中所有進程構(gòu)成的序列｛P。，P”…，Pn｝,如

果對于其中每一個進程Pi(IWiWn),它以后要申請的資源數(shù)量不超過系統(tǒng)中當(dāng)前剩余的

資源數(shù)量與所有進程B(jWi)當(dāng)前占有的資源量之和，則該進程序列稱為安全序列，此狀

態(tài)為安全狀態(tài)，安全狀態(tài)是沒有死鎖的狀態(tài)，而不安全狀態(tài)不一定是死鎖狀態(tài)。

銀行家算法是對系統(tǒng)中每一個進程發(fā)出的資源申請命令加以動態(tài)檢查，如果發(fā)現(xiàn)若分配資源

后系統(tǒng)將進入不安全狀態(tài)，則不予分配。

(4)死鎖的檢測與解除

死鎖的檢測通常采用化簡資源分配圖的方法，其過程為：

?在圖中找一個進程R,R的請求邊均能立即滿足。

?將R與其相連的邊全部刪去，繼續(xù)尋找請求邊滿足的進程進行化簡。

如果化簡后所有進程都成了孤立點，就稱為完全化簡，無死鎖現(xiàn)象；反之稱為不完全化簡，

非孤立點的進程處于死鎖狀態(tài)。

一旦發(fā)生死鎖應(yīng)立即排除，以確保系統(tǒng)正常運行，常采用資源剝奪法和撤消進程法。

3.4設(shè)備管理

3.4.1基本概念

1.設(shè)備管理的功能與目標(biāo)

設(shè)備管理的功能是按用戶需求制定分配和使用設(shè)備的策略，為I/O操作的進程分配一條傳輸

信息的通路，最大程度地實行并行操作。

要求達到的目標(biāo)是：

(1)方便性用戶無須了解物理設(shè)備的細節(jié)，方便地使用設(shè)備。

(2)并行性使CPU與設(shè)備，設(shè)備與設(shè)備之間并行操作。

(3)均衡性使CPU和I/O設(shè)備操作的忙閑程度保持相對平衡。

(4)獨立性用戶程序與設(shè)備相對獨立，用戶在程序中只須用相對設(shè)備代號。

2.設(shè)備分類

可以從不同的角度將設(shè)備劃分成不同的類型。這里主要提出：

(1)按使用性質(zhì)分

?獨享設(shè)備

?共享設(shè)備

?虛擬設(shè)備

(2)按使用方法分

?物理設(shè)備

?邏輯設(shè)備

3.I/O控制方式的改進

(1)循環(huán)測試I/O方式

(2)程序中斷I/O方式

(3)通道I/O方式

4.緩沖技術(shù)

緩解CPU與外設(shè)之間速度不匹配的矛盾。

3.4.2設(shè)備管理的工作過程

1.通道、控制器和設(shè)備

通道、控制器和設(shè)備可以采用各種不同的連接形式構(gòu)成傳輸信息的通路。系統(tǒng)為每個通道、

控制器與設(shè)備建立各自的控制塊。

2.設(shè)備分配程序

當(dāng)用戶進程提出對某I/O設(shè)備的請求后，設(shè)備分配程序根據(jù)當(dāng)時設(shè)備、控制器、通道的忙閑

情況選擇相應(yīng)設(shè)備組合；若當(dāng)時沒有找到，則把該進程按?定的調(diào)度算法插入到申請該設(shè)備

的隊列中等待。對設(shè)備的調(diào)度算法也有先請求先服務(wù)、優(yōu)先數(shù)法等。在分配時還要考慮防止

由于分配不當(dāng)而產(chǎn)生死鎖。

3.設(shè)備處理程序

主要的功能為：

(1)發(fā)出I/O命令，啟動分配到的I/O設(shè)備，完成指定的I/O操作。

(2)及時響應(yīng)中斷請求，調(diào)用相應(yīng)的中斷處理程序。

(3)根據(jù)用戶的I/O請求，自動構(gòu)成通道程序。

3.4.3虛擬設(shè)備--假脫機系統(tǒng)

它是一種預(yù)輸入、緩輸出和轉(zhuǎn)儲的管理技術(shù)，實現(xiàn)外部設(shè)備聯(lián)機并行操作。它必須有高速隨

機外存儲設(shè)備的支持，統(tǒng)稱采用磁盤。

1.組成

主要有以下三部分：

(1)輸入井和輸出井

在磁盤上開辟兩個存儲空間：輸入井模擬脫機輸入時的磁盤,用于收容外部設(shè)備輸入的數(shù)據(jù);

輸出井模擬脫機輸出時的磁盤，用于收容用戶程序的輸出數(shù)據(jù)。

(2)輸入緩沖區(qū)和輸出緩沖區(qū)

在內(nèi)存中開辟兩個緩沖區(qū)；輸入緩沖區(qū)用于暫存由輸入設(shè)備送來的數(shù)據(jù)，以后再傳送到輸入

井；輸出緩沖區(qū)用于暫存從輸出井送來的數(shù)據(jù)，以后再傳送給輸出設(shè)備。

(3)輸入進程和輸出進程

輸入進程模擬脫機輸入時的衛(wèi)星機，它將用戶要求的數(shù)據(jù)從輸入機通過輸入緩沖區(qū)再送到輸

入井(輸入收存)，當(dāng)CPU需要輸入數(shù)據(jù)時，直接從輸入并讀入內(nèi)存(輸入發(fā)出)；輸出進程

模擬脫機輸出時的衛(wèi)星機，把用戶需要輸出的數(shù)據(jù)先從內(nèi)存送到輸出井(輸出收存)，待輸

出設(shè)備空閑時，再將輸出井中數(shù)據(jù)，經(jīng)過輸出緩沖區(qū)送到輸出設(shè)備上(輸出發(fā)送)。

2.效果

(I)提高了I/O的速度

從對低速I/O設(shè)備進行的I/O操作演變?yōu)閷斎刖蜉敵鼍當(dāng)?shù)據(jù)的存取，如同脫機輸出/輸

入一樣，提高了I/O速度，緩和了CPU與低速I/O設(shè)備之間速度不匹配的矛盾。

(2)將獨占設(shè)備改造為共享設(shè)備

偽脫機系統(tǒng)實際上并沒有為任何進程分配設(shè)備，它只是在輸入井或輸出井中為進程分配一個

存儲區(qū)和建立一張I/O請求表，這樣就把獨占設(shè)備改造為共享設(shè)備。

(3)實現(xiàn)虛擬設(shè)備的功能

在宏觀上看，雖然是多個進程在同時使用一臺獨占設(shè)備，但對每一個進程而言，他們都認為

自己是獨占了一個設(shè)備，實際上這只是個邏輯上的設(shè)備，因此偽脫機系統(tǒng)實現(xiàn)了將獨占設(shè)備

變換為若干臺對應(yīng)的邏輯設(shè)備的功能。

3.5文件管理

3.5.1基本概念與術(shù)語

文件管理是操作系統(tǒng)中管理文件和數(shù)據(jù)的軟件，它負責(zé)文件的組織、存取、控制和使用。

1.文件

邏輯上具有完整意義的數(shù)據(jù)或字符的集合，每個文件都有一個文件名，文件由若干個記錄組

成。

2.文件系統(tǒng)

文件系統(tǒng)即文件管理系統(tǒng)。它的基本功能為：

(1)實施文件存儲空間(磁盤)的分配和回收。

(2)提供文件共享及保護、保密措施。

(3)實現(xiàn)用戶要求的各種操作。

3.文件的分類

可以有多種分類方式，主要有：

(1)按文件性質(zhì)和用途分為系統(tǒng)文件、庫文件和用戶文件。

(2)按存儲控制屬性分為執(zhí)行文件、只讀文件和讀寫文件。

(3)按文件中數(shù)據(jù)形式分為源文件、目標(biāo)文件和可執(zhí)行文件。

4.文件的存儲介質(zhì)

文件是存儲在外存空間中，它的存儲介質(zhì)可以有多中，目前使用最普通的為磁盤。

3.5.2文件的結(jié)構(gòu)及存取方式

1.文件的邏輯結(jié)構(gòu)

文件的邏輯結(jié)構(gòu)是指用戶概念的文件形式。一般來說一個文件是由若干條等長或不等長的記

錄組成。

2.文件的物理結(jié)構(gòu)

文件的物理結(jié)構(gòu)是指文件在存儲介質(zhì)上的組織方式，它與具體的存儲介質(zhì)有關(guān)。常用的文件

物理結(jié)構(gòu)有：

(1)順序結(jié)構(gòu)

把文件按邏輯記錄順序存放到連續(xù)的物理塊中。特點：存取速度快，空間利用率地低，文件

的插入或刪除操作只能在文件末尾進行。

(2)鏈接結(jié)構(gòu)

把文件信息存放在非連續(xù)的物理塊中，每個物理塊中設(shè)有一個指針，指向其后續(xù)塊。

特點：空間利用率高易于文件擴充，但搜索效率低。

(3)索引結(jié)構(gòu)

為每個文件建立一個索引表，其中每一表項指出文件記錄所在的物理塊好，表目按記錄中某

一關(guān)鍵字順序排列。

特點：可以滿足文件動態(tài)增長要求，存取方便，但建立索引表增加了存儲空間的開銷。

3.5.3文件目錄

1.文件目錄與目錄文件

文件目錄與目錄文件是兩個不同的概念。文件目錄中記錄了該文件的管理信息，又稱文件控

制塊。目錄文件是全部文件目錄組成的文件，它可以像其他文件一樣進行讀寫等處理。

2.文件目錄的結(jié)構(gòu)

(1)一級目錄結(jié)構(gòu)

把系統(tǒng)中所有文件構(gòu)成一個目錄表。

特點：管理簡單，但檢索效率低，不允許文件重名，不便于文件共享，只適用于單用戶系統(tǒng)。

(2)二級目錄結(jié)構(gòu)

把文件目錄分成主目錄和若干個用戶文件目錄兩級。

特點：克服了一級目錄結(jié)構(gòu)的缺點，提高了檢索效率，不同用戶的文件允許重名，多個用戶

可共享一個文件。

(3)多級目錄結(jié)構(gòu)

又稱樹形目錄結(jié)構(gòu)，其中主文件目錄稱為根目錄，其下層可設(shè)置各級子目錄。從根目錄出發(fā)

到某文件的道路上各級子目錄名構(gòu)成該文件的“路徑名北

特點：檢索效率高，允許重名，利于文件分類，能進行存取權(quán)限控制。

3.5.4文件存儲空間的管理

文件中以物理塊為單位交換信息，因此文件存儲空間的管理實質(zhì)上是空閑塊的組織與管理問

題。常見的有：

1.空白文件目錄

系統(tǒng)為存儲區(qū)中空閑空間建立一個目錄，它的分配與回收與內(nèi)存管理中的動態(tài)分區(qū)管理方式

相似，此方法易產(chǎn)生空閑塊碎片。

2.位示圖

系統(tǒng)為每個文件建立一張位示圖，反映每個文件存儲設(shè)備物理塊的使用情況。位示圖較小，

可以保存在內(nèi)存中。

3.空白塊鏈

把存儲設(shè)備上所有空閑塊用指針鏈接在一起，此方法簡單可靠，但空間開銷大，I/O操作較

多，效率低。

3.5.5文件的共享與文件的安全性

1.文件的共享

(1)通過文件路徑實現(xiàn)共享

只要用戶已知欲共享文件的文件路徑，而且該文件的主人允許使用該文件。

(2)通過連接操作實現(xiàn)共享

用戶在自身的文件目錄表中建立一個欲共享文件的表目，通過操作系統(tǒng)提供的連接操作命令

(系統(tǒng)調(diào)用)，實現(xiàn)文件共享。

2.文件的存取控制

(1)存取控制矩陣

用一個二維矩陣出每個用戶對每個文件的存取權(quán)限。

(2)按用戶分類存取控制

系統(tǒng)用9位二進制數(shù)表示對三類不同用戶設(shè)置不同的存取權(quán)限。

(3)口令

用戶為自身文件設(shè)置保密口令。

3.5.6文件的操作使用命令及文件系統(tǒng)的一般模型

1.文件的操作使用

文件系統(tǒng)為用戶提供系統(tǒng)調(diào)用命令來使用和控制文件，最基本的操作有：建立與撤消文件，

打開與關(guān)閉文件，讀寫文件。

(1)文件的建立與撤消

?建立文件系統(tǒng)為該文件建立一個目錄表目。

?撤消文件清除該文件目錄表目。

(2)打開與關(guān)閉文件

?打開文件將欲訪問文件表目調(diào)入內(nèi)存的活動文件表中。

?關(guān)閉文件把用戶要寫入文件中的記錄寫入文件中區(qū)相應(yīng)位置。

2.文件系統(tǒng)的一般模型

一個文件系統(tǒng)要完成上述各種功能，就要有若干個主要的功能模塊來實現(xiàn)。模塊之間具有層

次關(guān)系?？梢酝ㄟ^教材中提供的例題，了解各模塊要完成的功能及整個工作流程。

3.6操作系統(tǒng)的用戶接口

3.6.1用戶接口的任務(wù)和功能

任何一種軟件首先涉及的是人機交互界面，計算機應(yīng)用離不開操作系統(tǒng)的接口，又稱界面。

它已成為計算機系統(tǒng)的一個重要組成部分，也是計算機領(lǐng)域中的一個競爭焦點，它極大地影

響了最終用戶的使用，影響著計算機的推廣應(yīng)用，也影響著人的工作與生活。界面管理的功

能主要有：

(1)實現(xiàn)高效的人機通信。

(2)改善計算機的可用性、可學(xué)性和有效性。

3.6.2兩種用戶接口

1.操作命令接口

這是用戶表示作業(yè)執(zhí)行步驟的一種手段，常用的有作業(yè)控制語言和操作控制命令兩種。

(1)作業(yè)控制語言用于批處理系統(tǒng)中，用戶在提交作業(yè)之前，用作業(yè)控制語言編寫一份

作業(yè)控制說明書，連同作業(yè)一起交給系統(tǒng)。

(2)操作控制命令用于分時系統(tǒng)中，用戶可以從鍵盤上輸入操作控制命令或從“命令菜

單”中選擇命令指出作業(yè)的執(zhí)行步驟。用戶每輸入一條命令，操作系統(tǒng)就按命令要求進行控

制，當(dāng)一條命令的控制要求完成后，通知用戶執(zhí)行下一條，直到作業(yè)執(zhí)行結(jié)束。

2.程序一級接口-一系統(tǒng)調(diào)用

系統(tǒng)調(diào)用是用戶在程序中調(diào)用操作系統(tǒng)所提供的一些子功能。凡是與資源相關(guān)的操作都必須

通過這種方式向操作系統(tǒng)提出服務(wù)請求，并由操作系統(tǒng)代為完成。

操作系統(tǒng)的程序與用戶程序是分別在管態(tài)和目態(tài)卜運行的，當(dāng)用戶程序需要操作系統(tǒng)為其服

務(wù)時.，通過中斷系統(tǒng)將操作系統(tǒng)中具體的服務(wù)程序轉(zhuǎn)為用戶服務(wù)，服務(wù)程序結(jié)束后返回，退

出中斷。

不同的操作系統(tǒng)提供的系統(tǒng)調(diào)用不全相同，大致可分為如下幾類：

(1)文件操作例如打開/關(guān)閉文件、讀/寫文件以及建立/撤消文件等。

(2)資源申請例如申請/釋放存儲空間，申請/釋放外圍設(shè)備等。

(3)控制例如正常/異常結(jié)束，返回斷點/指定點等。

(4)信息維護例如設(shè)置日期、時間、設(shè)置或獲取文件屬性等。

3.6.3用戶界面的發(fā)展

1.第一代用戶界面——維界面

操作員記憶、敲擊鍵盤。例如常用的DOS操作系統(tǒng)和UNIX操作系統(tǒng)，用戶操作使用計算機,

首先要熟悉一整套操作命令，而且不同的操作系統(tǒng)命令是不相同的。它的優(yōu)點是對于一些專

用系統(tǒng)中反復(fù)使用的復(fù)雜操作,使用命令實現(xiàn)一次性有條件的復(fù)雜操作,反而顯得快捷方便。

2.第二代用戶界面-一二維空間界面

用戶觀看、點擊圖符進行操作。以美國微軟公司為代表的Windows操作系統(tǒng)界面是這方面的

一個里程碑，已被用戶廣泛接納和使用。圖形界面便于用戶操作使用計算機，在顯示屏上可

以建立起很多縮微型形象化的圖標(biāo)，用戶用鼠標(biāo)器一點就能調(diào)出所需程序工作。

3.第三代用戶界面一-三維空間界面

隨著計算機技術(shù)發(fā)展，利用三維計算機圖形顯示，加上語言、圖像、動畫等多媒體支持，現(xiàn)

有的界面己可看到很多“虛擬儀器”，在計算機屏幕上顯示出人們熟悉的一起設(shè)備的操作面

板，用鼠標(biāo)點擊，如同按動真實的設(shè)備一樣。進一步的發(fā)展，可使計算機能對人的語言、視

點和姿勢等作出反應(yīng)，達到“身臨其境”的“虛擬”世界。

練習(xí)題

1.現(xiàn)代操作系統(tǒng)兩個最基本的特性是什么？

2.分時操作系統(tǒng)需要使用下面哪些成分？

(1)多道程序設(shè)計技術(shù)

(2)作業(yè)說明書

(3)終端命令解釋程序

(4)中斷處理

(5)優(yōu)先級調(diào)度

(6)系統(tǒng)調(diào)用

3.批處理系統(tǒng)的主要缺點是：

(1)CPU利用率低

(2)不能并發(fā)執(zhí)行

(3)缺少交互性

(4)以上都不是

4.允許多個用戶以交互方式使用計算機的操作系統(tǒng)稱為()；允許多個用戶將多個作業(yè)

交給計算機集中處理的操作系統(tǒng)稱為()；計算機系統(tǒng)能及時處理過程控制數(shù)據(jù)并做出響

應(yīng)的操作系統(tǒng)稱為(

(1)批處理操作系統(tǒng)

(2)分時操作系統(tǒng)

(3)多處理機操作系統(tǒng)

(4)實時操作系統(tǒng)

(5)網(wǎng)絡(luò)操作系統(tǒng)

5.卜列哪些選擇不是操作系統(tǒng)關(guān)心的問題：

(1)管理計算機裸機

(2)設(shè)計、提供用戶程序與計算機硬件系統(tǒng)的界面

(3)管理計算機系統(tǒng)資源

(4)高級程序設(shè)計語言的編譯器

6.引入多道程序設(shè)計的主要目的為：

(1)提高實時響應(yīng)速度

(2)充分利用處理機

(3)有利于代碼共享

(4)充分利用外圍設(shè)備

(5)減少存儲碎片

7.最佳適應(yīng)算法的空閑塊是：

(1)按大小遞減順序連在?起

(2)按大小遞增順序連在一起

(3)按地址由小到大排列

(4)按地址由大到小排列

8.設(shè)某一操作系統(tǒng)采用可變分區(qū)的存儲管理方式，用戶區(qū)內(nèi)存為512KB,空閑塊鏈入空閑

塊表，分配時截取空閑塊的前半部分(小地址部分)。初始時用戶區(qū)全部空閑，分別采用首

次適應(yīng)算法與最佳適應(yīng)算法求出在執(zhí)行了如下的申請、釋放操作序列后的內(nèi)存情況。

(1)申請300KB(2)申請100KB(3)釋放300KB(4)申請150KB

(5)申請50KB(6)申請90KB(7)申請80KB

9.在一個分頁管理系統(tǒng)中，假如系統(tǒng)分配給一個作業(yè)的物理塊數(shù)為3,并且此作業(yè)的頁面

走向為2,3,2,1,5,2,4,5,3,2,5,2。試用FIFO和LRU兩種算法分別計算出程序

訪問過程中所發(fā)生的缺頁次數(shù)。

10.在某個分頁管理系統(tǒng)中，某一個作業(yè)有4個頁面，被分別裝入到主存的第3,4,6,8

頁架中，假定頁面和頁架大小均為1024字節(jié)，當(dāng)作業(yè)在CPU上運行時，執(zhí)行到其地址空間

第500號處遇到一條傳送命令

MOV2100,3100

請用地址變換圖計算出MOV指令中兩個操作數(shù)的物理地址。

11.假定某操作系統(tǒng)存儲器采用分頁管理，某作業(yè)在存儲器中的頁表為：

頁號0123456789

頁架號6432000000

狀態(tài)1111000000

假定該作業(yè)的代碼長度為320字，每頁長為32字，現(xiàn)有邏輯地址(八進制)為：101,204,

576,若能翻譯成相應(yīng)的物理地址，則說明翻譯過程；若不能翻譯，請說明原因。

12.覆蓋技術(shù)與虛擬技術(shù)有何本質(zhì)不同？交換技術(shù)與虛存中使用的調(diào)入調(diào)出技術(shù)有何相同與

不同之處？

13.假設(shè)某長度為n的存儲單元中，存放一長度為m的作業(yè)(n>m),則長度為(n-m)的空

間稱為該單元的內(nèi)部碎片；若存儲單元長度為n,在該系統(tǒng)采用的調(diào)度算法下，無法選出一

道作業(yè)能放入此存儲單元中，則稱該存儲空間為外部碎片。在固定分區(qū)分配、可變分區(qū)分配、

分頁存儲系統(tǒng)、分段存儲系統(tǒng)中，各會出現(xiàn)何種碎片？為什么？

14.在一個同時容納4個進程的操作系統(tǒng)中，假設(shè)在一段時間內(nèi)有6個作業(yè)提交，提交的時

間為：

作業(yè)號提交時間估計運行時間(分)

Jobl8:0060

Job28:2035

Job38:2520

Job48:3025

Job58:355

Job68:4010

系統(tǒng)采用短作業(yè)優(yōu)先的調(diào)度算法，作業(yè)一旦被調(diào)度進入內(nèi)存后不再中途退出，在內(nèi)存中的4

個進程其運行的優(yōu)先次序取決于當(dāng)時各進程實際剩余的運行時間。

(1)按照所選擇的調(diào)度算法，分別給出上述6個作業(yè)執(zhí)行的時間序列。

(2)計算在上述調(diào)度算法下，作業(yè)的平均周轉(zhuǎn)時間。

15.在?個批處理系統(tǒng)中，有2個作業(yè)進程，有一個作業(yè)序列其到達時間及估計運行時間如

下：

作業(yè)到達時間估計運行時間(分)

J110：0035

J210：1030

J310：1545

J410：2020

J510：3030

作業(yè)采用最高響應(yīng)比優(yōu)先調(diào)度算法，進程調(diào)度采用最短進程優(yōu)先算法。

(1)列出各作業(yè)執(zhí)行時間段

(2)計算這批作業(yè)的平均周轉(zhuǎn)時間

16.在某單道批處理系統(tǒng)中，有5個批處理作業(yè)(A,B,C,D,E)幾乎同時到達一個計算

中心，估計運行時間分別為(2,4,6,8,10)分，優(yōu)先數(shù)分別為(1,2,3,4,5)(1為

最低)，對下面每種調(diào)度算法分別計算作業(yè)的平均周轉(zhuǎn)時間：

(1)最高優(yōu)先級優(yōu)先

(2)FCFS(作業(yè)到達順序為C,D,B,E,A)

(3)短作業(yè)優(yōu)先

17.假定一個操作系統(tǒng)的進程調(diào)度采用剝奪式短進程優(yōu)先調(diào)度算法，即每當(dāng)新的進程加入就

緒隊列或某一進程運行結(jié)束時，都應(yīng)重新進行一次調(diào)度選擇，選取當(dāng)前所運行時間最短的進

程。系統(tǒng)為單CPU系統(tǒng)，系統(tǒng)中各進程到達就緒隊列的時刻以及執(zhí)行時間如下：

進程到達就緒隊列時間執(zhí)行時間

108

214

329

433

請給出各進程的調(diào)度次序，并計算平均等待時間和平均周轉(zhuǎn)時間。

18.有5個進程A,B,C,D,E兒乎同時到達，它們預(yù)計運行時間為10,6,2,4,8分鐘,

其優(yōu)先級分別為3,5,2,1,4,這里5為最高優(yōu)先級。對于下列每一種調(diào)度，計算其品軍

進程周轉(zhuǎn)時間。

(1)先來先服務(wù)(按A,B,C,D,E)

(2)優(yōu)先級調(diào)度

(3)時間片輪轉(zhuǎn)(時間片為2分)

19.設(shè)有8個程序porgl,porg2,porg8,它們在并發(fā)系統(tǒng)中執(zhí)行時有如圖3.1所示的制約

關(guān)系，試用P.V操作實現(xiàn)這些程序之間的同步。

Prog2

Prog

Prog5

Prog3

Prog4

Prog6Prog7

Prog8

圖3.1程序間同步關(guān)系

20.兄弟倆共同使用一個存折amount初值為0,每次限存或取10元，存錢與取錢的進程分

別為:

存錢取錢

miamount-m2amount—

minii+10V—股叱-10V—

amountm,<-amountm2■<-

由于兄弟倆可能同時存錢或取錢，因此兩個進程是并發(fā)的，若哥哥先存了兩次錢，但在

第三次存錢的時候，弟弟正在取錢，請問最后存折上可能出現(xiàn)的值？如何用P.V操作實現(xiàn)兩

并發(fā)進程的互斥執(zhí)行？

21.試從物理概念上來說明P.V操作中的信號量。

22.某數(shù)據(jù)庫有一個寫進程，n個讀進程，它們之間讀、寫操作的互斥要求是：

(1)寫進程正在寫該數(shù)據(jù)庫時，不能有其他進程讀該數(shù)據(jù)庫；

(2)讀進程之間不互斥，可以同時讀該數(shù)據(jù)庫；

(3)如果有若干進程正在讀該數(shù)據(jù)庫，一個寫進程在等待寫，則隨后欲讀的進程不能讀

該數(shù)據(jù)庫，需讓寫進程先寫。

用P.V操作描述這一組進程的互斥工作過程。

23.設(shè)公共汽車上，司機、售票員的活動分別是：

司機售票員

啟動車輛上乘客

正常行車關(guān)車門

到站停車售票

開車門

下乘客

假設(shè)售票員關(guān)車門后司機才可啟動車輛，到站停車后售票員方可開車門，在汽車不斷到

站、停車、行駛過程中，這兩個活動有什么同步關(guān)系？用P.V操作實現(xiàn)它們的同步。

24.桌子上有一直盤子，最多可容納兩個水果，每次只能放入或取出一個水果，爸爸專向盤

子中放蘋果(apple),媽媽專向盤子中放橘子(orange),兩個兒子專等吃盤子中的橘子，

兩個女兒專等吃盤子中的蘋果，請用P.V操作來實現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互

斥關(guān)系。

25.A,B兩個并發(fā)進程，它們共享一個臨界區(qū)，其執(zhí)行臨界區(qū)的算法如下：

A進程B進程

L1：臨界區(qū)L2：P(S))

V(S))臨界區(qū)

P(S2)V(S2)

GOTOLIGOTOL2

試判斷算法是否有錯？請說明理由，如有錯，請改正。S?8的初值均為0。

26.用P.V操作處理生產(chǎn)者和消費者問題如下：

mutex初值為1；empty初值為n；full初值為0

生產(chǎn)者消費者

L1：生產(chǎn)產(chǎn)品L2：P(full)

P(empty)P(mutex)

P(mutex)取出產(chǎn)品

產(chǎn)品裝入緩沖區(qū)V(empty)

V(full)V(mutex)

V(mutex)GOTOL2

GOTOLI

(1)信號量mutex,empty,full的作用是什么?

(2)為什么P操作的順序不能調(diào)換？

27.按序分配是防止死鎖的一種策略，什么是按序分配？為什么可以防止死鎖？

28.一個系統(tǒng)具有150個存儲單元，在某時刻分配給3個進程：

進程最大需求已分到

Pi7025

Pz6040

P36045

Pl60

對下列請求，用銀行算法分別判定是否安全？

(1)第4個進程請求分配25個單元；

(2)第4個進程請求分配35個單元。

29.設(shè)系統(tǒng)中有3種類型資源(A,B,C)和5個進程(P“P2,P3,P”Ps),A資源數(shù)量為

17,B資源數(shù)量為5,C資源數(shù)量為20,在t。時刻系統(tǒng)狀態(tài)如下：

進程最大資源需求量已分配資源數(shù)量

ABCABc

Pi559212

P2