《操作系統(tǒng)》

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

1.1操作系統(tǒng)的目標(biāo)和作用

1.1.1操作系統(tǒng)的目標(biāo)

目標(biāo)：

1.方便性。不需要人人都是程序員

2.有效性。工作協(xié)調(diào)高效

3.可擴(kuò)充性。各自獨(dú)立發(fā)展

4.開放性。移植和互操作

1.1.2操作系統(tǒng)的作用

1.OS作為用戶與計算機(jī)硬件系統(tǒng)之間的接口OS處于用戶與計算機(jī)硬件系統(tǒng)之間，用戶通

過OS來使用計算機(jī)系統(tǒng)。(從用戶角度來看，來操縱計算機(jī)。)

(1)命令輸入。形式又分為以下幾種：

命令行(CommandLineInput)：由OS提供的一組聯(lián)機(jī)命令(語言)，用戶可通過鍵盤輸

入有關(guān)命令，來直接操縱計算機(jī)系統(tǒng)。圖形用戶界面(GUI)：用戶通過顯示設(shè)備上的窗口

和圖標(biāo)來操縱計算機(jī)系統(tǒng)和運(yùn)行自己的程序。自然輸入方式(NUI)：用戶通過語音識別輸

入來操縱計算機(jī)系統(tǒng)和運(yùn)行自己的程序。

(2)系統(tǒng)調(diào)用方式(SystemCall),OS提供了一組系統(tǒng)調(diào)用，用戶可在自己的應(yīng)用程序中

通過相應(yīng)的使用編程調(diào)用API

1.1.3推動操作系統(tǒng)發(fā)展的主要動力

1.不斷提高計算機(jī)資源利用率

2.方便用戶

3.器件的不斷更新?lián)Q代

4.計算機(jī)體系結(jié)構(gòu)的不斷發(fā)展用戶的需求是推動OS發(fā)展的根本動力

2.OS作為計算機(jī)系統(tǒng)資源的管理者在一個計算機(jī)系統(tǒng)中通常都含有各種各樣的硬件和軟

件資源。需要空間和時間來使用這些資源，OS合理調(diào)配和使用。(這是從管理者的角度來看)

3.OS用作擴(kuò)展機(jī)、虛擬機(jī)隱藏了計算機(jī)具體細(xì)節(jié)，為用戶展現(xiàn)的是一臺虛擬機(jī)，功能上擴(kuò)

展了幾個功能部件的組合。(這是從發(fā)展的角度來看)Government

1.2操作系統(tǒng)的發(fā)展過程

-1-

1.2.1無操作系統(tǒng)的計算機(jī)系統(tǒng)

1.人工操作方式

從第一臺計算機(jī)ENIAC誕生（1945年2月）到50年代中期的計算機(jī)，屬于第一代。這種人

工操作方式有以下兩方面的缺點(diǎn)：（1）用戶獨(dú)占全機(jī)。（2）CPU等待人工操作。

2.脫機(jī)輸入/輸出（Off-LineI/O）方式這種脫機(jī)I/O方式的主要優(yōu)點(diǎn)如下：

（1）減少了CPU的空閑時間。（2）提高I/O速度。

-2-

1.2.2單道批處理系統(tǒng)

1.單道批處理系統(tǒng)(SimpleBatchProcessingSystem)的處理過程

2.單道批處理系統(tǒng)的特征

該系統(tǒng)的主要特征如下：(1)自動性。(2)順序性。(3)單道性。

1.2.3多道批處理系統(tǒng)

1.多道程序設(shè)計的基本概念

多道批處理系統(tǒng)(MultiprogrammedBatchProcessingSystem)。在該系統(tǒng)中，用戶所提

交的作業(yè)都先存放在外存上并排成一個隊(duì)列，稱為后備隊(duì)列；然后，由作業(yè)調(diào)度程序按一

定的算法從后備隊(duì)列中選擇若干個作業(yè)調(diào)入內(nèi)存，使它們共享CPU和系統(tǒng)中的各種資源。

這種調(diào)度稱之為作業(yè)調(diào)度。

1.2.4分時系統(tǒng)

1.分時系統(tǒng)(TimeSharingSystem)的產(chǎn)生

如果說，推動多道批處理系統(tǒng)形成和發(fā)展的主要動力，是提高資源利用率和系統(tǒng)吞吐量，

那么，推動分時系統(tǒng)形成和發(fā)展的主要動力，則是用戶的需求。用戶的需求具體表現(xiàn)在以

下幾個方面：

(1)人機(jī)交互。

(2)共享主機(jī)。

(3)便于用戶上機(jī)。

2.分時系統(tǒng)實(shí)現(xiàn)中的關(guān)鍵問題

分時系統(tǒng)性能好壞的主要指標(biāo)是響應(yīng)時間。

(1)及時接收。

(2)及時處理。

(3)符合使用習(xí)慣。

在OS中引入多道程序設(shè)計技術(shù)可帶來以下好處：

⑴提高CPU的利用率。

⑵可提高內(nèi)存和I/O設(shè)備利用率。

⑶增加系統(tǒng)吞吐量。

2.多道批處理系統(tǒng)的特征

(1)多道性。⑵無序性。⑶調(diào)度性。

-3-

3.多道批處理系統(tǒng)的優(yōu)缺點(diǎn)

(1)資源利用率高。

(2)系統(tǒng)吞吐量大?

(3)平均周轉(zhuǎn)時間長。

(4)無交互能力。

4.多道批處理系統(tǒng)需要解決的問題

⑴處理機(jī)管理問題。

(2)內(nèi)存管理問題。

(3)I/O設(shè)備管理問題。

(4)文件管理問題。

(5)作業(yè)管理問題。

3.分時系統(tǒng)的特征

⑴多路性。(2)獨(dú)立性。(3)及時性。(4)交互性。

1.2.5實(shí)時系統(tǒng)

實(shí)時系統(tǒng)(Real-TimeSystem)是指系統(tǒng)能及時(或即時)響應(yīng)外部事件的請求，在規(guī)定的問

內(nèi)完成對該事件的處理，并控制所有實(shí)時任務(wù)協(xié)調(diào)一致地運(yùn)行。

1.3操作系統(tǒng)的基本特性

1.3.1并發(fā)(Concurrence)

并行性和并發(fā)性是既相似又有區(qū)別的兩個概念，并行性是指兩個或多個事件在同?時刻發(fā)

生；而并發(fā)性是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生。最基本的特征！

1.3.2共享(Sharing)

在操作系統(tǒng)環(huán)境下，所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進(jìn)程(線程)共

同使用。

1.3.3虛擬(Virtual)

操作系統(tǒng)中的所謂虛擬，是指通過某種技術(shù)把一個物理實(shí)體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。

1.3.4異步性(Asynchronism)

在多道程序環(huán)境下，多個進(jìn)程是以停停走走的方式運(yùn)行。失去封閉性

-4-

第二章進(jìn)程管理

2.1進(jìn)程的基本概念

2.1.1程序的順序執(zhí)行及其特征

2.1.2前趨圖

前趨圖(PrecedenceGraph)是一個有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph),

用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。

2.1.3程序的并發(fā)執(zhí)行及其特征

2.1.4進(jìn)程的特征與狀態(tài)

Oneprogramwhichhasanindependentfunctionworksoncertaindatasetdynamically

andallocateresourcesdynamicallyWhatisaprocess?

一個具有一定獨(dú)立功能的程序?qū)δ硞€數(shù)據(jù)

集合上的一次動態(tài)執(zhí)行過程和資源分配過程

Code,Data,ProcessTableTheDifferenceBetweenProcessandProgramProcessis

dynamic,andtheprogramisstaticProcessistemporary,theprogramispermanence

TheelementsofprocessandprogramisdifferentCodeData-PTTherelationships

ofprocessandprogramarecomplexCreateSystemcall

2.進(jìn)程的三種基本狀態(tài)

1)就緒(Ready)狀態(tài)2)執(zhí)行狀態(tài)3)阻塞狀態(tài)

2.1.5進(jìn)程控制塊

1.進(jìn)程控制塊的作用

進(jìn)程控制塊的作用是記錄?個獨(dú)立運(yùn)行的進(jìn)程的基本信息。或者說，OS是根據(jù)PCB來對并

發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。

2.進(jìn)程控制塊中的信息

3.進(jìn)程控制塊的組織方式

1)鏈接方式2)索引方式

2.2進(jìn)程控制

2.2.1進(jìn)程的創(chuàng)建

(1)用戶登錄。

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

(3)提供服務(wù)。

-5-

(4)應(yīng)用請求。

(1)申請空白PCB。

(2)為新進(jìn)程分配資源。

(3)初始化進(jìn)程控制塊。

(4)將新進(jìn)程插入就緒隊(duì)列，如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程，便將新進(jìn)程插入就

緒隊(duì)列。

2.進(jìn)程的終止過程

(1)根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB,從中讀出該進(jìn)程的狀態(tài)。

(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于

指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。

(3)若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止，以防他們成為不可控的進(jìn)

程。

(4)將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)。

(5)將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出，等待其他程序來搜集信息。

2.2.2進(jìn)程的終止

1)正常結(jié)束(自愿的)

2)異常結(jié)束

普通錯誤退出(自愿的)

致命錯誤退出(非自愿的)

3)外界干預(yù)(非自愿的)

2.2.3進(jìn)程的阻塞與喚醒

1.引起進(jìn)程阻塞和喚醒的事件

1)請求系統(tǒng)服務(wù)

2)啟動某種操作

3)新數(shù)據(jù)尚未到達(dá)

4)無新工作可做

2.2.4進(jìn)程的掛起與激活

2.3進(jìn)程同步

2.3.1進(jìn)程同步的基本概念

1.兩種形式的制約關(guān)系

-6-

(1)間接相互制約關(guān)系。

(2)直接相互制約關(guān)系。

2.臨界資源(CriticalResource)

3.臨界區(qū)(criticalsection)

一個飛機(jī)訂票系統(tǒng)，兩個終端，運(yùn)行Tl、T2進(jìn)程

T1：

read(x);

ifx>=lthen

x:=x-l;

write(x);

T2：

read(x);

ifx>=lthen

x:=x-l;

write(x);

CriticalRegions

Comingdatablocks

Synchronization

4.同步機(jī)制應(yīng)遵循的規(guī)則

(1)空閑讓進(jìn)。

(2)忙則等待。

(3)有限等待。

(4)讓權(quán)等待。

(PetersonJsAlgorithm)：

先修改、后檢查、后修改者等待正確的算法

turn-j;描述可進(jìn)入的進(jìn)程(同時修改標(biāo)志時)

-7-

在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：

檢查對方flag,如果不在臨界區(qū)則自己進(jìn)入一一空閑則入

否則再檢查turn：保存的是較晚的一次賦值，則較晚的進(jìn)

程等待，較早的進(jìn)程進(jìn)入一一先到先入，后到等待

MutualExclusionwithBusyWaiting

Enteringandleavingacriticalregionusingthe

TSLinstruction

Sleepand

Wakeup

Producer-consumerproblemwithfatalracecondition

2.3.2信號量機(jī)制

1.整型信號量

最初由Dijkstra把整型信號量定義為一個整型量，僅能通過初始化和兩個標(biāo)準(zhǔn)的原子操作

(AtomicOperation)wait(S)和signal(S)來訪問。兩個操作被分別稱為P^V操作

(primitive)?

wait(S):whileSWOdonoop

s:=s-i；

signal(S):S：=S+1;

2.記錄型信號量

在整型信號量機(jī)制中的wait操作，只要是信號量S<0,就會不斷地測試。因此，該機(jī)制

并未遵循讓權(quán)等待的準(zhǔn)則，而是使進(jìn)程處于忙等的狀態(tài)。記錄型信號量機(jī)制，則是一種不

存在忙等現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了讓權(quán)等待的策略后，又會出現(xiàn)多個進(jìn)程等待訪

問同一臨界資源的情況。為此，在信號量機(jī)制中，除了需要一個用于代表資源數(shù)目的整型

變量value外，還應(yīng)增加?個進(jìn)程鏈表L,用于鏈接上述的所有等待進(jìn)程。記錄型信號量

是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。

P原語wait(s);down(s);P(s)

一s.count;//表示申請一個資源；

if(s.count<0)//表示沒有空閑資源；

{調(diào)用進(jìn)程進(jìn)入等待隊(duì)列s.queue;阻塞調(diào)用進(jìn)程;}

V原語signal(s);up(s);V(s)

-8-

++s.count;〃表示釋放一個資源；

if(s.count<=0)〃表示有進(jìn)程處于阻塞狀態(tài)；

{從等待隊(duì)列s.queue中取出一個進(jìn)程P;進(jìn)程P進(jìn)入就緒隊(duì)列;}

Semaphores

Theproducer-

consumer

problemusing

semaphores

Monitors

Exampleofamonitor

2.4經(jīng)典進(jìn)程的同步問題

2.4.1生產(chǎn)者消費(fèi)者問題

1.利用記錄型信號量解決生產(chǎn)者消費(fèi)者問題

DiningPhilosophers

Philosopherseat/think

Eatingneeds2forks

Pickoneforkatatime

Howtopreventdeadlock

2.4.2哲學(xué)家進(jìn)餐問題

讓奇數(shù)號的哲學(xué)家先取右手邊的筷子，讓偶數(shù)號的哲學(xué)家先取左手邊的筷子。

send(i)

begin

ifimod2=0thenelse

{{

P(c[i]);P(c[i+1mod5]);

P(c[i+1mod5]);P(c[i]);

eat;eat;

V(c[i+1mod5]);V(c[i]);

V(c[i]);V(c[i+1mod5]);

})

-9-

end

2.4.3讀者寫者問題

讀者-寫者問題描述

TheReaders

andWriters

Problem

1.利用記錄型信號量解決讀者寫者問題

-10-

TheSleepingBarberProblem

TheSleeping

Barber

Problem

Solutionto

sleepingbarber

problem

Sharedmemory(共享內(nèi)存)

Message(消息機(jī)制)

Pipe(管道)

Signal(信號)

Socket(套接字)

InterprocessCommunication

2.5進(jìn)程通信2.5.1進(jìn)程通信的類型

1.共享存儲器系統(tǒng)(SharedMemorySystem)

(1)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。

(2)基于共享存儲區(qū)的通信方式。

2.消息傳遞系統(tǒng)(Messagepassingsystem)

在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換，

是以格式化的消息(message)為單位的；

在計算機(jī)網(wǎng)絡(luò)中，又把message稱為報

文。程序員直接利用系統(tǒng)提供的一組通信命令

(原語)進(jìn)行通信。

3.管道(Pipe)通信

管道是指用于連接一個讀進(jìn)程和?個

寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個共享文

件，又名pipe文件。這種方式首創(chuàng)于UNIX

系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因

而又被引入到許多其它操作系統(tǒng)中。

-II-

2.5.2消息傳遞通信的實(shí)現(xiàn)方法

1.直接通信方式

通信命令(原語)：

Send(Receiver,message);發(fā)送一個消息給接收進(jìn)程；

Receive(Sender,message);接收Sender發(fā)來的消息；

例如，原語Send(P2,ml)表示將消息山發(fā)送給接收進(jìn)程P2;而原語Receive(Pl,ml)

則表示接收由P1發(fā)來的消息ml。

不指定發(fā)送者的接收原語可表示為：Receive(id,message);

利用直接通信原語，解決生產(chǎn)者消費(fèi)者問題。

repeat

produceaniteminnextp;

send(consumer,nextp);

untilfalse;

repeat

receive(producer,nextc);

consumetheiteminnextc;

untilfalse;

Message

Passing

.The

producer-

consumer

problem

withN

messages

2,間接通信方式

(1)信箱的創(chuàng)建和撤消。

-12-

(2)消息的發(fā)送和接收。

Send(mailbox,message);將一個消息發(fā)送到指定信箱；

Receive(mailbox,message);從指定信箱中接收一個消息;

3.進(jìn)程同步方式

(1)發(fā)送進(jìn)程阻塞、接收進(jìn)程阻塞。

(2)發(fā)送進(jìn)程不阻塞、接收進(jìn)程阻塞。

(3)發(fā)送進(jìn)程和接收進(jìn)程均不阻塞。

2.6線程

2.6.1線程的基本概念

為使程序能并發(fā)執(zhí)行，系統(tǒng)還必須進(jìn)行以下的一系列操作。

1)創(chuàng)建進(jìn)程

2)撤消進(jìn)程

3)進(jìn)程切換

1.線程的引入

TheThreadModel

(a)Threeprocesseseachwithonethread

(b)Oneprocesswiththreethreads

ForExampleTheThreadModel

Eachthreadhasitsownstack

2.線程的屬性

(D輕型實(shí)體(容易創(chuàng)建和撤銷)。

(2)獨(dú)立調(diào)度和分派的基本單位。

(3)可并發(fā)執(zhí)行。

(4)共享進(jìn)程資源。

(5)適應(yīng)硬件的發(fā)展

TheThreadModel

Itemssharedbyallthreadsinaprocess

Itemsprivatetoeachthread

-13-

3.線程的狀態(tài)

(1)狀態(tài)參數(shù)。

(2)線程運(yùn)行狀態(tài)。

5.多線程OS中的進(jìn)程

在多線程OS中，進(jìn)程是作為擁有系統(tǒng)資源的基本單位，通常的進(jìn)程都包含多個線程并為它

們提供資源，但此時的進(jìn)程就不再作為一個執(zhí)行的實(shí)體。多線程OS中的進(jìn)程有以下屬性：

(1)作為系統(tǒng)資源分配的單位。

(2)可包括多個線程。

(3)進(jìn)程不是一個可執(zhí)行的實(shí)體。

4.線程的創(chuàng)建和終止

在多線程OS環(huán)境下，應(yīng)用程序在啟動時，通常僅有一個線程在執(zhí)行，該線程被人們稱為初

始化線程。它可根據(jù)需要再去創(chuàng)建若干個線程。終止線程的方式有兩種：?種是在線程完

成了自己的工作后自愿退出；另一種是線程在運(yùn)行中出現(xiàn)錯誤或由于某種原因而被其它線

程強(qiáng)行終止。

2.6.2線程間的同步和通信

1.互斥鎖(mutex)

互斥鎖是一種比較簡單的、用于實(shí)現(xiàn)線程間對資源互斥訪問的機(jī)制。

2.條件變量

Useofabarrier

processesapproachingabarrier

allprocessesbutoneblockedatbarrier

lastprocessarrives,allareletthrough

2.6.3內(nèi)核支持線程和用戶級線程

1.內(nèi)核支持線程

這里所謂的內(nèi)核支持線程，也都同樣是在內(nèi)核的支持下運(yùn)行的，即無論是用戶進(jìn)程中的線

程，還是系統(tǒng)進(jìn)程中的線程，他們的創(chuàng)建、撤消和切換等，也是依靠內(nèi)核實(shí)現(xiàn)的。此外，

在內(nèi)核空間還為每一個內(nèi)核支持線程設(shè)置了一個線程控制塊，內(nèi)核是根據(jù)該控制塊而感知

某線程的存在的，并對其加以控制。

ImplementingThreadsintheKernel

-14-

Athreadspackagemanagedbythekernel

2.用戶級線程

用戶級線程僅存在于用戶空間中。對于這種線程的創(chuàng)

建、撤消、線程之間的同步與通信等功能，都無須利用

系統(tǒng)調(diào)用來實(shí)現(xiàn)。對于用戶級線程的切換，通常是發(fā)生在

一個應(yīng)用進(jìn)程的諸多線程之間，這時，也同樣無須內(nèi)核的

支持:。由于切換的規(guī)則遠(yuǎn)比進(jìn)程調(diào)度和切換的規(guī)則簡單，

因而使線程的切換速度特別快?？梢?，這種線程是與內(nèi)核

無關(guān)的。

ImplementingThreadsinUserSpace

Auser-levelthreadspackage

HybridImplementations

Multiplexinguser-levelthreadsontokernel-

levelthreads

TheMultithreadingRevolution

第三章處理機(jī)調(diào)度與死鎖

3.1處理機(jī)調(diào)度的基本概念

BurstsofCPUusagealternatewithperiodsofI/Owait

aCPU-boundprocess

anI/O-boundprocess

SchedulingAlgorithmGoals

3.1.1高級、中級和低級調(diào)度

Threelevelscheduling

FCFS

SJF

HRF

SRF

FCFS

-15-

SPF

RR

PS

1.高級調(diào)度(HighScheduling)

宏觀調(diào)度

在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。

1)接納多少個作業(yè)？

2)接納哪些作業(yè)？

2.低級調(diào)度(LowLevelScheduling)微觀調(diào)度

1)非搶占方式(Non-preemptiveMode)

優(yōu)點(diǎn)：實(shí)現(xiàn)簡單、系統(tǒng)開銷小。

調(diào)度時機(jī)：

①正在執(zhí)行的進(jìn)程執(zhí)行完畢退出

②發(fā)生某事件而被阻塞(外部原因)

③執(zhí)行中的進(jìn)程提出阻塞請求(自我原因)

2)搶占方式(PreemptiveMode)

優(yōu)點(diǎn)：處理及時，實(shí)現(xiàn)復(fù)雜

搶占的時機(jī)：

①具有搶先權(quán)的進(jìn)程創(chuàng)建就緒

②具有搶先權(quán)的進(jìn)程被喚醒進(jìn)入就緒

③具有搶先權(quán)的進(jìn)程從掛起進(jìn)入就緒

3.中級調(diào)度(Intermediate-LevelScheduling)

中程調(diào)度

引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。

中級調(diào)度的算法主要由內(nèi)存管理來實(shí)現(xiàn)，與高級調(diào)度利低級調(diào)度的算法不同。

3.1.2調(diào)度隊(duì)列模型

1.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

2.具有高級和低級調(diào)度的調(diào)度隊(duì)列模型

3.同時具有三級調(diào)度的調(diào)度隊(duì)列模型

3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則

-16-

1.面向用戶的準(zhǔn)則

（1）周轉(zhuǎn)時間短（批處理）

平均周轉(zhuǎn)時間

帶權(quán)周轉(zhuǎn)時間WT/TS

而平均帶權(quán)周轉(zhuǎn)時間

（2）響應(yīng)時間快（交互式系統(tǒng)）

（3）截止時間的保證（實(shí)時系統(tǒng)）

（4）優(yōu)先權(quán)準(zhǔn)則（特權(quán)處理）

2.面向系統(tǒng)的準(zhǔn)則

（1）系統(tǒng)吞吐量高（批處理）

（2）處理機(jī)利用率好（所有的）

（3）各類資源的平衡利用（所有的）

符合習(xí)慣思維（交互式）

具有前瞻預(yù)測（實(shí)時系統(tǒng)）

3.2調(diào)度算法

3.2.1先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法

1.先來先服務(wù)調(diào)度算法

2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法

FCFS的特點(diǎn)

比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁

忙的作業(yè)。

SJF的特點(diǎn)

優(yōu)點(diǎn)：

比FCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，縮短作業(yè)的等待時間；提高系統(tǒng)的吞吐量;

缺點(diǎn)：

對長作業(yè)非常不利，可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先

級；難以準(zhǔn)確估計作業(yè)（進(jìn)程）的執(zhí)行時間，從而影響調(diào)度性能。

SJF的變型

最短剩余時間優(yōu)先"SRT（Shortest

RemainingTime）

-17-

允許比當(dāng)前進(jìn)程剩余時間更短的進(jìn)程來搶占

.“最高響應(yīng)比優(yōu)先”HRRN（Highest

ResponseRatioNext）

響應(yīng)比R=（等待時間+要求執(zhí)行時間）/要

求執(zhí)行時間

是FCFS利SJF的折衷

3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法

1.優(yōu)先權(quán)調(diào)度算法的類型

1）非搶占式優(yōu)先權(quán)算法

2）搶占式優(yōu)先權(quán)調(diào)度算法

2.優(yōu)先權(quán)的類型

1）靜態(tài)優(yōu)先級

創(chuàng)建進(jìn)程時就確定，直到進(jìn)程終止前都不改變。通常是?個整數(shù)。

依據(jù)：

進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級較高）

對資源的需求（對CPU和內(nèi)存需求較少的進(jìn)程，優(yōu)先級較高）

用戶要求（緊迫程度和付費(fèi)多少）

2）動態(tài)優(yōu)先權(quán)

在創(chuàng)建進(jìn)程時賦予的優(yōu)先級，在進(jìn)程運(yùn)行過程中可

以自動改變，以便獲得更好的調(diào)度性能.

在就緒隊(duì)列中，等待時間延長則優(yōu)先級提高，從

而使優(yōu)先級較低的進(jìn)程在等待足夠的時間后，其優(yōu)先

級提高到可被調(diào)度執(zhí)行

進(jìn)程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而

一個進(jìn)程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓CPU

3.高響應(yīng)比優(yōu)先調(diào)度算法

3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法

1.時間片輪轉(zhuǎn)法

RoundRobinScheduling

listofrunnableprocesses

-18-

listofrunnableprocessesafterBusesupitsquantum

2.多級反饋隊(duì)列調(diào)度算法

(RoundRobinwithMultipleFeedback)

多級反饋隊(duì)列算法是時間片輪轉(zhuǎn)算法和優(yōu)

先級算法的綜合和發(fā)展。優(yōu)點(diǎn)：

為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧

短進(jìn)程

為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時間而

照顧I/O型進(jìn)程

不必估計進(jìn)程的執(zhí)行時間，動態(tài)調(diào)節(jié)

Aschedulingalgorithmwithfourpriorityclasses

PS

3.多級反饋隊(duì)列調(diào)度算法的性能

(1)終端型作業(yè)用戶。

(2)短批處理作業(yè)用戶。

(3)長批處理作業(yè)用戶。

3.2a實(shí)時調(diào)度

ScheduTablereal-timesystem

.Given

mperiodicevents

eventioccurswithinperiodPiandrequiresCi

seconds

Thentheloadcanonlybehandledif

WewilldiscussinthemultimediaOS

-19-

3.3產(chǎn)生死鎖的原因和必要條件

3.3.1產(chǎn)生死鎖的原因

(1)互斥資源分配不當(dāng)

(2)進(jìn)程間推進(jìn)順序不當(dāng)

1.競爭資源引起進(jìn)程死鎖

1)可剝奪和非剝奪性資源

2)競爭非剝奪性資源

3)競爭臨時性資源

Resources

Examplesofcomputerresources

-printers

tapedrives

-tables

Processesneedaccesstoresourcesinreasonable

order

SupposeaprocessholdsresourceAandrequests

resourceB

atsametimeanotherprocessholdsBandrequestsA

bothareblockedandremainso

ResourcesResources

Resources

Twoprocessresourcetrajectories

2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

IntroductiontoDeadlocks

Formaldefinition:

Asetofprocessesisdeadlockedifeachprocessintheset

iswaitingforaneventthatonlyanotherprocessinthe

setcancause

Usuallytheeventisreleaseofacurrentlyheld

-20-

resource

Noneoftheprocessescan…

-run

releaseresources

beawakened

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

(1)互斥條件

(2)請求和保持條件

(3)不剝奪條件

(4)環(huán)路等待條件

3.3.3處理死鎖的基本方法

(1)忽略死鎖

(2)檢測和解除死鎖

(3)避免死鎖

(4)預(yù)防死鎖

3.4解決死鎖的方法

3.4.1忽略死鎖

1.鴕鳥算法

死鎖發(fā)生的概率小

解決死鎖的代價太大

3.4.2死鎖的檢測與解除

3.4.2.1死鎖的檢測

1.資源分配圖(ResourceAllocationGraph)

DetectionwithOneResourceofEach

Type

Notetheresourceownershipandrequests

Acyclecanbefoundwithinthegraph,denotingdeadlock

T

2.死鎖定理

3.死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)

-21-

DetectionwithMultipleResourceofEach

Type

Anexampleforthedeadlockdetectionalgorithm

3.4.2.2死鎖的解除

(1)剝奪資源(2)回溯到還原點(diǎn)

(3)撤消進(jìn)程(4)重起系統(tǒng)

3.4.3死鎖的避免

3.4.3.1.安全和不安全狀態(tài)

安全狀態(tài)之例：

假定系統(tǒng)中有三個進(jìn)程Pl、P2和P3,共有12分磁帶機(jī)。

進(jìn)程P1總共要求10臺磁帶機(jī)，P2和P3分別要求4臺和9臺。假

設(shè)在T0時刻，進(jìn)程Pl、P2和P3已分別獲得5臺、2臺和2臺磁帶

機(jī)，尚有3臺空閑未分配，如下表所示：

進(jìn)程最大需求一分配可用

P1

P2

P3

10

4

9

5

2

2

3

3.4.3.2利用銀行家算法避免死鎖

一個銀行家把他的固定資金

(capital)貸給若干顧客。

只要不出現(xiàn)一個顧客借走所

有資金后還不夠，銀行家的

資金應(yīng)是安全的。銀行家需

-22-

一個算法保證借出去的資金

在有限時間內(nèi)可收回。

3.4.4預(yù)防死鎖

1.摒棄互斥條件

2.摒棄“請求和保持”條件

3.摒棄“不剝奪”條件

4.摒棄“環(huán)路等待”

AttackingtheMutualExclusion

Condition

Somedevices(suchasprinter)canbespooled

onlytheprinterdaemonusesprinterresource

thusdeadlockforprintereliminated

Notalldevicescanbespooled

PCB,HD

,Principle:

avoidassigningresourcewhennotabsolutelynecessary

asfewprocessesaspossibleactuallyclaimtheresource

AttackingtheHoldandWaitCondition

Requireprocessestorequestresourcesbefore

starting

aprocessneverhastowaitforwhatitneeds

?Problems

maynotknowrequiredresourcesatstartofrun

alsotiesupresourcesotherprocessescouldbeusing

Variation:

processmustgiveupallresources

thenrequestallimmediatelyneeded

AttackingtheNoPreemptionCondition

Thisisnotaviableoption

Consideraprocessgiventheprinter

-23-

halfwaythroughitsjob

nowforciblytakeawayprinter

-!!??

AttackingtheCircularWaitCondition

Normallyorderedresources

Aresourcegraph

9

Summaryofapproachestodeadlockprevention

預(yù)防死鎖的各種分類對策

本章重要習(xí)題分析

第四章存儲器管理

4.1定位和重定位

4.2簡單連續(xù)分配方式

4.3基本頁式存儲管理方式

4.4基本段式存儲管理方式

4.5段頁式存儲管理

4.6虛擬存儲器

4.7請求式分頁的基本原理

4.8頁面置換算法

RelocationandProtection

Cannotbesurewhereprogramwillbeloadedin

memory

addresslocationsofvariables,coderoutinescannotbe

absolute

mustkeepaprogramoutofotherprocessespartitions

Usebaseandlimitvalues

addresslocationsaddedtobasevaluetomaptophysicaladdress

-24-

addresslocationslargerthanlimitvalueisanerror

4.1定位和重定位

4.1.1程序的裝入

1.絕對裝入方式(AbsoluteLoadingMode)

程序中所使用的絕對地址，既可在編譯或匯編時給出，也可山程序員直接賦予。

例如：

ORG1000H

dfb309a

dfb309a

OOf,3976

Ib3c44600f3976

Ib3c44600f3976

2.可重定位裝入方式(RelocationLoadingMode)

Pl

P2

P3

P4

P5

3.動態(tài)運(yùn)行時裝入方式(dynamicRun-timeLoading)

動態(tài)運(yùn)行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)

換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此，裝入內(nèi)存后

的所有地址都仍是相對地址。

4.1.2程序的鏈接

1.靜態(tài)鏈接方式(StaticLinking)

在將這幾個目標(biāo)模塊裝配成一個裝入模塊時，須解決以下兩個問題：

(1)對相對地址進(jìn)行修改。

(2)變換外部調(diào)用符號。

2.裝入時動態(tài)鏈接(LoadtimeDynamicLinking)

裝入時動態(tài)鏈接方式有以卜優(yōu)點(diǎn)：

(1)便于修改和更新。

-25-

(2)便于實(shí)現(xiàn)對目標(biāo)模塊的共享。

3.運(yùn)行時動態(tài)鏈接(Run-timeDynamicLinking)

在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝

入內(nèi)存，把它鏈接到調(diào)用者模塊上。這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的

內(nèi)存空間。

4.2簡單連續(xù)分配方式

4.2.1單一連續(xù)分配

這是最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存

儲管理方式時，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放

在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。

Monoprogramming

Threesimplewaysoforganizingmemory

anoperatingsystemwithoneuserprocess

無分區(qū)

4.2.2固定分區(qū)分配

1.劃分分區(qū)的方法

(1)分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。

(2)分區(qū)大小不等。

2.內(nèi)存分配

等額固定分區(qū)

差額固定分區(qū)

MultiprogrammingwithFixedPartitions

Fixedmemorypartitions

separateinputqueuesforeachpartition

singleinputqueue

動態(tài)分區(qū)

4.2.3動態(tài)分區(qū)分配

碎片Hole

1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

(1)空閑分區(qū)表。

-26-

(2)空閑分區(qū)鏈。

MemoryManagementwithBit

Maps

Partofmemorywith5processes,3holes

tickmarksshowallocationunits

shadedregionsarefree

Correspondingbitmap

Sameinformationasalist

MemoryManagementwithLinked

Lists

FourneighborcombinationsfortheterminatingprocessXFragment碎片

2.分區(qū)分配算法

(D首次適應(yīng)算法FF。

(2)循環(huán)首次適應(yīng)算法。

(3)最佳適應(yīng)算法。

(4)最壞適應(yīng)算法。

(5)快速適應(yīng)算法。

Pointer

Cominga

Newprocessis

16K

Worstfit

4.2.4可重定位分區(qū)分配

1.動態(tài)重定位的引入

2.動態(tài)重定位的實(shí)現(xiàn)

3.動態(tài)重定位分區(qū)分配算法

4.2.5對換(Swapping)

L對換的引入

2.對換空間的管理

3.進(jìn)程的換出與換入

-27-

(1)進(jìn)程的換出。

每當(dāng)?進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，

但又無足夠的內(nèi)存空間等情況發(fā)生時.，系統(tǒng)應(yīng)將某進(jìn)程換

出。

(2)進(jìn)程的換入。

系統(tǒng)應(yīng)定時地查看所有進(jìn)程的狀態(tài)，從中找出就緒

狀態(tài)但已換出的進(jìn)程，將其中換出時間(換出到磁盤上)最

久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)

程或無可換出的進(jìn)程為止。

4.3基本分頁存儲管理方式

4.3.1頁面與頁表

1.頁面

1)頁面和物理塊

2)頁面大小

在分頁系統(tǒng)中的頁面其大小應(yīng)適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，從而減

少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率，但另一方面也會使每個進(jìn)程占用較多的

頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存；此外，還會降低頁面換進(jìn)換出的效率。

然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進(jìn)換出的速度，但卻

又會使頁內(nèi)碎片增大。因此，頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2的幕，通常為

512B~8KB。

PageSize

Smallpagesize

Advantages

lessinternalfragmentation

betterfitforvariousdatastructures,code

sections

lessunusedprograminmemory

Disadvantages

programsneedmanypages,largerpagetables

0

-28-

Pagesizelarge,thefragmentationbig

Pagesizesmall,thepagetablebig

Fragmentation內(nèi)碎片

MostprogramJspiecesarelessthan4K

A.0

A.1

A.2

A.3

B.0

B.1

B.2

C.0

C.1

C.2

C.3

PageSize

Overheadduetopagetableandinternal

fragmentation

.Where

s=averageprocesssizeinbytes

p=pagesizeinbytes

e=pageentry

Optimizedwhen

internal

fragmentation

pagetablespace

2.地址結(jié)構(gòu)

分頁地址中的地址結(jié)構(gòu)如下：

頁號P位移量W

3112110

-29-

對某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中的地址為A,頁面的大小

為L,則頁號P和頁內(nèi)地址d可按下式求得：

3.頁表

4.3.2地址變換機(jī)構(gòu)

1.基本的地址變換機(jī)構(gòu)

2.具有快表的地址變換機(jī)構(gòu)

4.3.3兩級和多級頁表

現(xiàn)代的大多數(shù)計算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間（232、264）。在這樣的環(huán)境下，頁

表就變得非常大，要占用相當(dāng)大的內(nèi)存空間?？梢圆捎眠@樣兩個方法來解決這一問題：

①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題：②只將當(dāng)前需要的部

分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時再調(diào)入。

1.兩級頁表（Two-LevelPageTable）

邏輯地址結(jié)構(gòu)可描述如下：

Windows的多級頁表結(jié)構(gòu)

2.多級頁表

對于32位的機(jī)器，采用兩級頁表結(jié)構(gòu)是合適的；但對于64位的機(jī)器，如果頁面大小仍采

用4KB即212B,那么還剩下52位，假定仍按物理塊的大?。?12位）來劃分頁表，則將余

下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項(xiàng)，要占用16384GB的

連續(xù)內(nèi)存空間。必須采用多級頁表，將外層頁表再進(jìn)行分頁，也是將各分頁離散地裝入到

不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關(guān)系。

InvertedPageTables

Comparisonofatraditionalpagetablewithaninvertedpagetable

4.4基本分段存儲管理方式

4.4.1分段存儲管理方式的引入

引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一系列需要：

1）方便編程

2）信息共享

3）信息保護(hù)

4）動態(tài)增長

5）動態(tài)鏈接

-30-

4.4.2分段系統(tǒng)的基本原理

1.分段

分段地址中的地址具有如下結(jié)構(gòu)：

段號段內(nèi)地址

3116150

2.段表

4.分頁和分段的主要區(qū)別

(1)頁是信息的物理單位，分頁是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存

的利用率。或者說，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏

輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。

(2)頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由

機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定，決定于用

戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時，根據(jù)信息的性質(zhì)來劃分。

(3)分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符,

即可表示一個地址：而分段的作、也地址空間則是二維的，程序員在標(biāo)識?個地址時，既需

給出段名，又需給出段內(nèi)地址。

4.5段頁式存儲管理方式

4.5.1基本原理

4.5.2地址變換過程

4.6虛擬存儲器的基本概念

4.6.1虛擬存儲器的引入

1.常規(guī)存儲器管理方式的特征

(1)一次性。

⑵駐留性。

2.局部性原理

1968年，Denning.P指出:

(1)程序執(zhí)行時，大多數(shù)情況下仍是順序執(zhí)行的。

(2)過程調(diào)用將會使程序轉(zhuǎn)移，過程調(diào)用的深度在大多數(shù)情況下都不超過5。

(3)程序中存在許多循環(huán)結(jié)構(gòu)，它們將多次執(zhí)行。

(4)程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進(jìn)行操作，它們往往都局限于很小的

-31-

范圍內(nèi)。局限性又表現(xiàn)在下述兩個方面：(1)時間局限性。如果程序中的某條指令?旦執(zhí)

行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次

被訪問。產(chǎn)生時間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。

(2)空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被

訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是

程序的順序執(zhí)行。

3.虛擬存儲器定義

所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的

一種存儲器系統(tǒng)。其邏輯容量山內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存

速度，而每位的成本卻又接近于外存。可見，虛擬存儲技術(shù)是種性能非常優(yōu)越的存儲器

管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機(jī)器和微型機(jī)中。CPU及其存儲器的地址線寬度

4.6.2虛擬存儲器的實(shí)現(xiàn)方法

1.分頁請求系統(tǒng)

(1)硬件支持。

①請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請求分頁

的數(shù)據(jù)結(jié)構(gòu)；

②缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時便產(chǎn)生一缺頁中斷，以請

求OS將所缺的頁調(diào)入內(nèi)存

③地址變換機(jī)構(gòu)，它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。

(2)實(shí)現(xiàn)請求分頁的軟件。

PageTables

Typicalpagetableentry

Virtualtimeandsoon

OnlyformemorymappedI/O

Theworsepagefaultshappens

Beyondfault

4.6.3虛擬存儲器的特征

1.多次性

對換性

3.虛擬性

-32-

4.7請求分頁存儲管理方式

4.7.1請求分頁中的硬件支持

1.頁表機(jī)制

2.缺頁中斷機(jī)構(gòu)

3.地址變換機(jī)構(gòu)

4.7.2內(nèi)存分配策略和分配算法

1.最小物理塊數(shù)的確定

2.物理塊的分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時;

也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

1）固定分配局部置換（FixedAllocation,LocalReplacement）

2）可變分配全局置換（VariableAllocation,GlobalReplacement）

3）可變分配局部置換（VariableAllocation,LocalReplacemen

2）按比例分配算法

根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)

為Si,則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m,則每個進(jìn)

程所能分到的物理塊數(shù)為bi,將有：b應(yīng)該取整，它必須大于最小物理塊數(shù)。

3.物理塊分配算法

1）平均分配算法

3）考慮優(yōu)先權(quán)的分配算法

在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空

間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配

給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程在

有的系統(tǒng)中，如重要的實(shí)時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。

4.7.3調(diào)頁策略

1.何時調(diào)入頁面

1）預(yù)調(diào)頁策略

2）請求調(diào)頁策略

2.從何處調(diào)入頁面

在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換

-33-

區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁

盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時.，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，

可分成如下三種情況：

(1)系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。

為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。

(2)系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而

當(dāng)換出這些頁面時，由于它們未被修改而不必再將它們換出，以后再調(diào)入時，仍從文件區(qū)

直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時，便須調(diào)到對換區(qū)，以后需要

時，再從對換區(qū)調(diào)入。

(3)UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文

件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入

時，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此，某進(jìn)程所請求的頁面有可能已

被其它進(jìn)程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。Solaris存儲3.頁面調(diào)入過程每當(dāng)

程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU

環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存

的物理塊后，如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改

頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出：如果該頁未

被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改，則必須將它寫回磁盤，然后再

把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為“1,并將此頁表項(xiàng)寫入

快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去

訪問內(nèi)存數(shù)據(jù)。

4.8頁面置換算法

Pagefaultforceschoice

whichpagemustberemoved

makeroomforincomingpage

Modifiedpagemustfirstbesaved

unmodifiedjustoverwritten

Betternottochooseanoftenusedpage

willprobablyneedtobebroughtbackinsoon

4.8.1最佳置換算法和先進(jìn)先出置換算法

-34-

1.最佳(Optimal)置換算法

最佳置換算法是山Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，

將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法,

通常可保證獲得最低的缺頁率。

OPT432143543215

頁1432111555211

頁243333333555

頁34444444444

xxxxVVxVVxx

共缺頁中斷7次

2.先進(jìn)先出(FIFO)頁面置換算法

SecondChancePageReplacement

Algorithm

Operationofasecondchance

pagessortedinFIFOorder

Pagelistiffaultoccursattime20,AhasRbitset

(numbersabovepagesareloadingtimes)

TheClockPageReplacement

Algorithm2.改進(jìn)型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(AR,M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0,\仁1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=l,M=l):最近已被訪問且被修改，該頁可能再被訪問。

1.簡單的Clock置換算法

4.8.2Clock置換算法

NotRecentlyUsedPageReplacementAlgorithm

EachpagehasReferencebit,Modifiedbit

bitsaresetwhenpageisreferenced,modified

-35-

Pagesareclassified

1.notreferenced,notmodified

2.notreferenced,modified

3.referenced,notmodified

4.referenced,modified

NRUremovespageatrandom

fromlowestnumberednonemptyclass

4.8.3最近最久未使用(LRU)置換算法

1.LRU(LeastRecentlyUsed)置換算法的描述

2.LRU置換算法的硬件支持

4.8.4其它置換算法

1.最少使用(LFU：LeastFrequentlyUsed)置換算法

2.頁面緩沖算法(PBA：PageBufferingAlgorithm)

TheWorkingSetPageReplacementAlgorithm

Theworkingsetisthesetofpagesusedbythekmostrecentmemoryreferences

w(k,t)isthesizeoftheworkingsetattime,tLocalityofreference

TheWorkingSetPageReplacementAlgorithm

Theworkingsetalgorithm

0

TheWSClock

Page

Replacement

Algorithm

OperationoftheWSClockalgorithm

ReviewofPageReplacement

Algorithms

4.8.5其它

Belady'sAnomaly

StackAlgorithm

TheDistanceString

-36-

PredictingPageFaultRates

Belady，sAnomaly

FIFOwith3pageframes

FIFOwith4pageframes

P'sshowwhichpagereferencesshowpagefaults

DESIGNISSUESFORPAGINGSYSTEMS

LocalversusGlobalAllocationPolicies

LoadControl

PageSize

SeparateInstructionandDataSpaces

SharedPages

CleaningPolicy

VirtualMemoryInterface

LocalversusGlobalAllocationPolicies

Originalconfiguration

Localpagereplacement

Globalpagereplacement

7fram