第一章

★L(fēng)操作系統(tǒng)的概念：通常把操作系統(tǒng)定義為用以控制和管理計(jì)算機(jī)系統(tǒng)資源方便用戶使用的

程序和數(shù)據(jù)結(jié)構(gòu)的集合。

★2.操作系統(tǒng)的基本類型：批處理操作系統(tǒng)、分時(shí)操作系統(tǒng)、實(shí)時(shí)操作系統(tǒng)、個(gè)人計(jì)算機(jī)操作

系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)、分布式操作系統(tǒng)。

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

特點(diǎn)：

用戶脫機(jī)使用計(jì)算機(jī)

成批處理

多道程序運(yùn)行

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

由于系統(tǒng)資源為多個(gè)作業(yè)所共享，其工作方式是作業(yè)之間自動(dòng)調(diào)度執(zhí)行。并在運(yùn)行過程中用戶

不干預(yù)自己的作業(yè)，從而大大提高了系統(tǒng)資源的利用率和作業(yè)吞吐量。

缺點(diǎn)：

無交互性，用戶一旦提交作業(yè)就失去了對(duì)其運(yùn)行的控制能力；而且是批處理的，作業(yè)周轉(zhuǎn)時(shí)間長，用戶使用不方便。

批處理系統(tǒng)中作業(yè)處理及狀態(tài)

②分時(shí)操作系統(tǒng)（TimeSharingOS）

分時(shí)操作系統(tǒng)是一個(gè)聯(lián)機(jī)的多用戶交互式的操作系統(tǒng)，如UNIX是多用戶分時(shí)操作系統(tǒng)。

分時(shí)計(jì)算機(jī)系統(tǒng)：由于中斷技術(shù)的使用，使得一臺(tái)計(jì)算機(jī)能連接多個(gè)用戶終端，用戶可通過各

自的終端使用和控制計(jì)算機(jī)，我們把一臺(tái)計(jì)算機(jī)連接多個(gè)終端的計(jì)算機(jī)系統(tǒng)稱為分時(shí)計(jì)算機(jī)系

統(tǒng)，或稱分時(shí)系統(tǒng)。

分時(shí)技術(shù)：把處理機(jī)的響應(yīng)時(shí)間分成若于個(gè)大小相等（或不相等）的時(shí)間單位，稱為時(shí)間片（如

100毫秒），每個(gè)終端用戶獲得CPU,就等于獲得一個(gè)時(shí)間片，該用戶程序開始運(yùn)行，當(dāng)時(shí)間片

到（用完），用戶程序暫停運(yùn)行，等待下一次運(yùn)行。

特點(diǎn)：

人機(jī)交互性好：在調(diào)試和運(yùn)行程序時(shí)由用戶自己操作。

共享主機(jī)：多個(gè)用戶同時(shí)使用。

用戶獨(dú)立性：對(duì)每個(gè)用戶而言好象獨(dú)占主機(jī)。

③實(shí)時(shí)操作系統(tǒng)(real-timeOS)

實(shí)時(shí)操作系統(tǒng)是一種聯(lián)機(jī)的操作系統(tǒng)，對(duì)外部的請(qǐng)求，實(shí)時(shí)操作系統(tǒng)能夠在規(guī)定的時(shí)間內(nèi)處理

完畢。

特點(diǎn)：

有限等待時(shí)間

有限響應(yīng)時(shí)間

用戶控制

可靠性高

系統(tǒng)出錯(cuò)處理能力強(qiáng)

設(shè)計(jì)實(shí)時(shí)操作系統(tǒng)要考慮的一些因素：

(1)實(shí)時(shí)時(shí)鐘管理

(2)連續(xù)的人一機(jī)對(duì)話

(3)過載

(4)高度可靠性和安全性需要采取冗余措施。

④通用操作系統(tǒng)

同時(shí)兼有多道批處理、分時(shí)、實(shí)時(shí)處理的功能，或其中兩種以上的功能。

⑤個(gè)人計(jì)算機(jī)上的操作系統(tǒng)

個(gè)人計(jì)算機(jī)上的操作系統(tǒng)是聯(lián)機(jī)的交互式單用戶操作系統(tǒng)，目前在個(gè)人計(jì)算機(jī)上使用的操作系

統(tǒng)以windows系列和linux系統(tǒng)為主。

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

特征：

（1）計(jì)算機(jī)網(wǎng)絡(luò)是一個(gè)互連的計(jì)算機(jī)系統(tǒng)群體。這些計(jì)算機(jī)在物理上是分散的。

（2）這些計(jì)算機(jī)是自治的，每臺(tái)計(jì)算機(jī)有自己的操作系統(tǒng)，各自獨(dú)立工作，它們?cè)诰W(wǎng)絡(luò)協(xié)議控

制下協(xié)同工作。

（3）系統(tǒng)互連要通過通信設(shè)施（硬件、軟件）來實(shí)現(xiàn)。

（4）系統(tǒng)通過通信設(shè)施執(zhí)行信息交換、資源共享、互操作和協(xié)作處理。

⑦分布式系統(tǒng)（DistributedSystem）

特征：

（1）功能的分布

（2）堅(jiān)強(qiáng)性

（3）高可靠性

★3.操作系統(tǒng)的功能

處理機(jī)管理、存儲(chǔ)管理（內(nèi)存分配、存儲(chǔ)保護(hù)、內(nèi)存擴(kuò)充）、設(shè)備管理（通道、控制器、輸入輸

出設(shè)備的分配及管理，設(shè)備獨(dú)立性）、信息管理（文件系統(tǒng)管理）、用戶接口（程序一級(jí)的接口、

作業(yè)一級(jí)的接口）。

4.通道和中斷技術(shù)

O通道：用于控制I/O設(shè)備及內(nèi)存間的數(shù)據(jù)傳輸。啟動(dòng)后可獨(dú)立于CPU運(yùn)行，實(shí)現(xiàn)

CPU及I/O的并行。

O通道有專用的I/O處理器，可及CPU并行工作

o可實(shí)現(xiàn)I/O聯(lián)機(jī)處理

O中斷是指CPU在收到外部中斷信號(hào)后，停止原來工作，轉(zhuǎn)去處理該中斷事件，完

畢后回到原來斷點(diǎn)繼續(xù)工作。

中斷處理過程：中斷請(qǐng)求，中斷響應(yīng)，中斷點(diǎn)（暫停當(dāng)前任務(wù)并保存現(xiàn)場），中斷處理例程，中

斷返回（恢復(fù)中斷點(diǎn)的現(xiàn)場并繼續(xù)原有任務(wù)

監(jiān)督程序發(fā)展為執(zhí)行系統(tǒng)(executivesystem),常駐內(nèi)存

★5.多道批處理系統(tǒng)

特點(diǎn)

O多道：內(nèi)存中同時(shí)存放幾個(gè)作業(yè)；

O宏觀上并行運(yùn)行：都處于運(yùn)行狀態(tài)，但都未運(yùn)行完；

微觀上串行運(yùn)行：各作業(yè)交替使用CPU；

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

o資源利用率高：CPU和內(nèi)存利用率較高；

作業(yè)吞吐量大：單位時(shí)間內(nèi)完成的工作總量大；

缺點(diǎn)：

O用戶交互性差：整個(gè)作業(yè)完成后或中間出錯(cuò)時(shí)，才及用戶交互，不利于調(diào)試和修

改；

作業(yè)平均周轉(zhuǎn)時(shí)間長：短作業(yè)的周轉(zhuǎn)時(shí)間顯著增長；

多道程序系統(tǒng)中，要解決的問題：同步互斥、內(nèi)存不夠、使用效率、內(nèi)存保護(hù)

6.計(jì)算機(jī)硬件：

構(gòu)成計(jì)算機(jī)的基本硬件元素：處理器、存儲(chǔ)器、輸入輸出控制及總線、外部設(shè)備。

及操作系統(tǒng)相關(guān)的幾種主要的寄存器

數(shù)據(jù)寄存器

■地址寄存器

■條件碼寄存器

■程序計(jì)數(shù)器

■指令計(jì)數(shù)器

■程序狀態(tài)字PSW

■中斷現(xiàn)場保護(hù)寄存器

■過程調(diào)用用堆棧

存儲(chǔ)器的訪問速度

大小

指令的執(zhí)行和中斷

操作系統(tǒng)的啟動(dòng)

啟動(dòng)電源一一產(chǎn)生中斷信號(hào)——觸發(fā)CPU中的一段指令發(fā)現(xiàn)操作系統(tǒng)引導(dǎo)區(qū)位置——導(dǎo)入內(nèi)存

執(zhí)行一一操作系統(tǒng)程序加載到內(nèi)存制定區(qū)域——初始化硬件……

7.算法

begin-,end算法的開始于結(jié)束

repeat操作…..until條件當(dāng)“條件”未被滿足時(shí)重復(fù)所描述的“操作”

while條件do操作…….od當(dāng)“條件”滿足時(shí)，進(jìn)行相應(yīng)的“操作”

if條件then操作else操作fi滿足“if”所指的“條件”時(shí)，進(jìn)行“then”后的相關(guān)

“操作”，否則完成“else”后的相關(guān)操作。

第二章

★1.作業(yè)：在一次應(yīng)用業(yè)務(wù)處理過程中，從輸入開始到輸出結(jié)束，用戶要求計(jì)算機(jī)所做的有關(guān)

該次業(yè)務(wù)處理的全部工作稱為一個(gè)作業(yè)。

作業(yè)由不同的順序相連的作業(yè)步組成，作業(yè)步是一個(gè)作業(yè)的處理過程中計(jì)算機(jī)所做的相對(duì)獨(dú)立

的工作。

2,作業(yè)的組織：

作業(yè)由三部分組成，即程序、數(shù)據(jù)和作業(yè)說明書。作業(yè)中包含的程序和數(shù)據(jù)完成用戶所要求的

業(yè)務(wù)處理工作，作業(yè)說明書則體現(xiàn)用戶的控制意圖。

★由作業(yè)說明書在系統(tǒng)中生成一個(gè)稱為作業(yè)控制塊（JCB）的表格，JCB包括：作業(yè)名、估計(jì)執(zhí)

行時(shí)間、優(yōu)先數(shù)（用于調(diào)度）、作業(yè)說明書文件名、程序類型、資源要求（靜態(tài)申請(qǐng)和動(dòng)態(tài)申請(qǐng)）、

作業(yè)狀態(tài)（提交后各執(zhí)行完成）。

作業(yè)說明書包括：作業(yè)基本情況描述（用戶名、作業(yè)名、使用語言名、允許最大處理時(shí)間等）、

作業(yè)控制描述（控制方式、操作順序、出錯(cuò)處理等）、作業(yè)資源要求描述（要求處理時(shí)間、內(nèi)存

空間、外設(shè)類型和數(shù)量、處理及優(yōu)先級(jí)、庫函數(shù)或?qū)嵱贸绦虻龋?/p>

★3.如何控制作業(yè)

①聯(lián)機(jī)輸入輸出方式

聯(lián)機(jī)輸入輸出方式大多用在交互式系統(tǒng)中，用戶及系統(tǒng)通過交互式會(huì)話輸入輸出作業(yè)。在聯(lián)機(jī)

輸入輸出方式中，外圍設(shè)備直接及主機(jī)相連接。

②脫機(jī)輸入輸出方式

脫機(jī)輸入又稱為預(yù)輸入方式，利用低檔個(gè)人計(jì)算機(jī)作為外圍處理機(jī)進(jìn)行輸入輸出處理。

③直接耦合方式

把主機(jī)及低檔外圍通過一個(gè)公用的大容量外存直接耦合起來。

④SPOOLING系統(tǒng)（外圍設(shè)備同時(shí)聯(lián)機(jī)操作）

多臺(tái)外圍設(shè)備通過通道或DMA器件和主機(jī)及外存連接起來。

⑤網(wǎng)絡(luò)聯(lián)機(jī)方式

網(wǎng)絡(luò)聯(lián)機(jī)方式以上述幾種輸入輸出方式為基礎(chǔ)。當(dāng)用戶通過計(jì)算機(jī)網(wǎng)絡(luò)中的某一臺(tái)設(shè)備對(duì)計(jì)算

機(jī)網(wǎng)絡(luò)中的另一臺(tái)主機(jī)進(jìn)行輸入輸出操作時(shí)，就構(gòu)成了網(wǎng)絡(luò)聯(lián)機(jī)方式。

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

系統(tǒng)調(diào)用大致可分為6類：

(1)設(shè)備管理：該類系統(tǒng)調(diào)用被用來請(qǐng)求和釋放有關(guān)設(shè)備以及啟動(dòng)設(shè)備操作等°

(2)文件管理：包括對(duì)文件的讀、寫、創(chuàng)建和刪除等。

(3)進(jìn)程控制：包括進(jìn)程創(chuàng)建、進(jìn)程執(zhí)行、進(jìn)程撤銷、進(jìn)程等待和執(zhí)行優(yōu)先級(jí)控制等。

(4)進(jìn)程通信：該系統(tǒng)調(diào)用被用在進(jìn)程之間傳遞消息或符號(hào)。

(5)存儲(chǔ)管理：包括調(diào)查作業(yè)占據(jù)內(nèi)存區(qū)的大小、獲取作業(yè)占據(jù)內(nèi)存區(qū)的始址等。

(6)線程管理：包括線程的創(chuàng)建、調(diào)度、執(zhí)行、撤銷等。

系統(tǒng)調(diào)用的實(shí)現(xiàn)：當(dāng)用戶使用系統(tǒng)調(diào)用時(shí)，產(chǎn)生一條相應(yīng)的指令，處理機(jī)在執(zhí)行到該指令時(shí)發(fā)

生相應(yīng)的中斷，并發(fā)出有關(guān)信號(hào)給該處理機(jī)制。該處理機(jī)制在收到了處理機(jī)發(fā)來的信號(hào)后，啟

動(dòng)相關(guān)的處理程序去完成該系統(tǒng)調(diào)用所要求的功能。

陷進(jìn)處理機(jī)構(gòu)：在系統(tǒng)中為控制系統(tǒng)調(diào)用服務(wù)的機(jī)構(gòu)稱為陷進(jìn)處理機(jī)構(gòu)。

陷進(jìn)指令：把由于系統(tǒng)調(diào)用引起處理機(jī)中斷的指令稱為陷進(jìn)指令。

第三章

1.程序的并發(fā)執(zhí)行

程序用來描述計(jì)算機(jī)所完成的獨(dú)立功能，并在時(shí)間上嚴(yán)格地按前后次序相繼地進(jìn)行計(jì)算機(jī)操作

序列集合，是一個(gè)靜態(tài)概念。

個(gè)程序由若干個(gè)程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式就稱為

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

■程序順序執(zhí)行的特點(diǎn)：

■1.順序性

■處理機(jī)嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每個(gè)操作必須在下一個(gè)操作開始之前結(jié)束。

■2.封閉性

■程序一旦開始執(zhí)行，其計(jì)算結(jié)果不受外界的影響，當(dāng)程序的初始條件紿定之后，其后

的狀態(tài)只能由程序本身確定，即只有本程序才能改變它。

■3.可再現(xiàn)性

程序執(zhí)行的結(jié)果及初始條件有關(guān)，而及執(zhí)行時(shí)間無關(guān)。即只要程序的初始條件相同，它的執(zhí)

行結(jié)果是相同的，不論它在什么時(shí)間執(zhí)行，也不管計(jì)算機(jī)的運(yùn)行速度。

多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化

■執(zhí)行環(huán)境的特點(diǎn)：

■(1)獨(dú)立性

在多道環(huán)境下執(zhí)行的每道程序都是邏輯上獨(dú)立的。

■(2)隨機(jī)性

程序和數(shù)據(jù)的輸入和執(zhí)行開始時(shí)間都是隨機(jī)的。

■(3)資源共享

軟硬件資源的有限性導(dǎo)致資源共享。

程序并發(fā)執(zhí)行：若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序的執(zhí)行在時(shí)間上是重迭的，一個(gè)程

序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始，即使這種重迭是很小的，也稱這幾個(gè)程

序段是并發(fā)執(zhí)行的。

2.支,進(jìn)程，進(jìn)程是一個(gè)程序?qū)δ硞€(gè)數(shù)據(jù)集的執(zhí)行過程，是分配資源的基本單位，

進(jìn)程和程序的區(qū)別及聯(lián)系：

①程序是指令的集合，是靜態(tài)的概念。進(jìn)程是程序在處理機(jī)上的一次執(zhí)行的過程，是動(dòng)態(tài)的概

念。程序可以作為軟件資料長期保存。進(jìn)程是有生命周期的。

②進(jìn)程是一個(gè)獨(dú)立的運(yùn)行單位，能及其它進(jìn)程并行(并發(fā))活動(dòng)。而程序則不是。

③進(jìn)程是競爭計(jì)算機(jī)系統(tǒng)有限資源的基本單位，也是進(jìn)行處理機(jī)調(diào)度的基本單位。

④不同的進(jìn)程可以包含同一程序，只要該程序所對(duì)應(yīng)的數(shù)據(jù)集不同。

作業(yè)和進(jìn)程的關(guān)系

作業(yè)是用戶需要計(jì)算機(jī)完成某項(xiàng)任務(wù)時(shí)要求計(jì)算機(jī)所做工作的集合。而進(jìn)程則是已提交完畢程

序的執(zhí)行過程的描述，是資源分配的基本單位。

■其主要區(qū)別如下：

■作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。

■一個(gè)作業(yè)可由多個(gè)進(jìn)程組成。

■作業(yè)的概念主要用于批處理系統(tǒng)中。

進(jìn)程描述

①在系統(tǒng)中一個(gè)進(jìn)程存在：進(jìn)程控制塊PCB.有關(guān)程序段、數(shù)據(jù)結(jié)構(gòu)集

②進(jìn)程控制塊PCB(ProcessControlBlock)

包含一個(gè)進(jìn)程的描述信息、控制信息及資源信息，有些系統(tǒng)還有進(jìn)程調(diào)度等待所使用的現(xiàn)場保

護(hù)區(qū)。PCB集中反映一個(gè)進(jìn)程的動(dòng)態(tài)特征。在創(chuàng)建時(shí)，建立PCB,并伴隨進(jìn)程運(yùn)行的全過程，當(dāng)

進(jìn)程完成其功能后，系統(tǒng)釋放PCB,進(jìn)程也隨之消亡

(1)描述信息

L進(jìn)程名或進(jìn)程標(biāo)識(shí)號(hào)name

每個(gè)進(jìn)程都必須有一個(gè)唯一的標(biāo)識(shí)符，可以是字符串，也可以是一個(gè)數(shù)字。UNIX系統(tǒng)中就是

一個(gè)整型數(shù)。在進(jìn)程創(chuàng)建時(shí)由系統(tǒng)賦予。

2.用戶名或用戶標(biāo)識(shí)號(hào)

每個(gè)進(jìn)程都隸屬于某個(gè)用戶，用戶名或用戶標(biāo)識(shí)號(hào)有利于資源共享和保護(hù)

3.家族關(guān)系processfamily

有的系統(tǒng)允許一個(gè)進(jìn)程可創(chuàng)建自己的子進(jìn)程，子進(jìn)程還可以創(chuàng)建，一個(gè)進(jìn)程往往處在一個(gè)

家族之中，就需要記錄進(jìn)程在家族中位置的信息。

(2)控制信息

1.進(jìn)程當(dāng)前狀態(tài)status

說明進(jìn)程當(dāng)前所處的狀態(tài)。

為了管理的方便，系統(tǒng)設(shè)計(jì)時(shí)會(huì)將相同的狀態(tài)的進(jìn)程組成一個(gè)隊(duì)列，如就緒進(jìn)程隊(duì)列，等待進(jìn)

程則要根據(jù)等待的事件組成多個(gè)等待隊(duì)列，如等待打印機(jī)隊(duì)列、等待磁盤I/O完成隊(duì)列等等。

2.進(jìn)程優(yōu)先級(jí)priority

進(jìn)程的優(yōu)先級(jí)反映進(jìn)程的緊迫程度，通常由用戶指定和系統(tǒng)設(shè)置。

3.執(zhí)行程序開始地址start-addr

4.各種計(jì)時(shí)信息

進(jìn)程占用系統(tǒng)資源的情況，不同的系統(tǒng)的處理差別很大。

5.通信信息communicationinformation

是指某個(gè)進(jìn)程在運(yùn)行的過程中要及其它進(jìn)程進(jìn)行通信，該區(qū)記錄有關(guān)進(jìn)程通信方面的信息。

（3）資源管理信息

包括有關(guān)存儲(chǔ)器的信息、使用輸入、輸出設(shè)備的信息、有關(guān)文件系統(tǒng)的信息：

1.占用內(nèi)存大小及管理用數(shù)據(jù)結(jié)構(gòu)指針。

2.在某些復(fù)雜系統(tǒng)中，還有對(duì)換或覆蓋用的有關(guān)信息。

3.共享程序段大小及起始地址。

4、輸入輸出設(shè)備的設(shè)備號(hào)，所要傳送的數(shù)據(jù)長度、緩沖區(qū)地址、緩沖區(qū)長度及使用設(shè)備的有關(guān)

數(shù)據(jù)結(jié)構(gòu)指針等。

5.指向文件系統(tǒng)的指針及有關(guān)標(biāo)識(shí)等。

（4）^CPU現(xiàn)場保護(hù)區(qū)cpustatus

當(dāng)進(jìn)程因某種原因不能繼續(xù)占用CPU時(shí)（等待打印機(jī)），釋放CPU,這時(shí)就要將CPU的各種狀

態(tài)信息保護(hù)起來，為將來再次得到處理機(jī)恢復(fù)CPU的各種狀態(tài)，繼續(xù)運(yùn)行。

②進(jìn)程上下文實(shí)際上是進(jìn)程執(zhí)行活動(dòng)全過程的靜態(tài)描述。

進(jìn)程上下文是一個(gè)抽象的概念，它包含了每個(gè)進(jìn)程執(zhí)行過的、執(zhí)行時(shí)的以及待執(zhí)行的指令和數(shù)

據(jù)，在指令寄存器、堆棧（存放個(gè)調(diào)用子程序的返回點(diǎn)和參數(shù)等），狀態(tài)字寄存器等中的內(nèi)容。

上文：已執(zhí)行過的進(jìn)程指令和數(shù)據(jù)在相關(guān)寄存器及堆棧中的內(nèi)容。

正文：正在執(zhí)行的指令和數(shù)據(jù)在相關(guān)寄存器及堆棧中的內(nèi)容。

下文：待執(zhí)行的指令和數(shù)據(jù)在相關(guān)寄存器及堆棧中的內(nèi)容。

③進(jìn)程上下文切換

進(jìn)程上下文切換發(fā)生在不同的進(jìn)程之間而不是同一個(gè)進(jìn)程內(nèi)。包含3個(gè)部分，第一部分為保存

被切換進(jìn)程的正文部分（或當(dāng)前狀態(tài)）至有關(guān)存儲(chǔ)區(qū)。第二部分操作系統(tǒng)進(jìn)程中有關(guān)調(diào)度和資

源分配程序執(zhí)行，并選取新的進(jìn)程。第三部分則是將被選中進(jìn)程的原來被保存的正文部分從有

關(guān)存儲(chǔ)區(qū)中選出，并送至有關(guān)寄存器或堆棧中，激活被選中進(jìn)程執(zhí)行。

|進(jìn)程片執(zhí)行

中斷或進(jìn)程調(diào)用

I

保存進(jìn)程修正文至PCB,

系統(tǒng)進(jìn)程執(zhí)行

選取新進(jìn)程心，恢復(fù)&上下文

|新進(jìn)程。2執(zhí)行

④進(jìn)程空間和大小

任一進(jìn)程都有自己的地址空間，把該空間稱為進(jìn)程空間或虛空間。進(jìn)程空間的大小只及處理機(jī)

的位數(shù)有關(guān)。程序的執(zhí)行都在進(jìn)程空間內(nèi)進(jìn)行。用戶程序、進(jìn)程的各種控制表格等都按一定的

結(jié)構(gòu)排列在進(jìn)程空間中。

在有的系統(tǒng)中進(jìn)程空間被劃分為兩部分：用戶空間和系統(tǒng)空間。

為了防止用戶程序訪問系統(tǒng)空間，造成訪問出錯(cuò)，計(jì)算機(jī)通過程序狀態(tài)寄存器等設(shè)置不同的執(zhí)

行模式，即用戶模式（用戶態(tài)）和系統(tǒng)模式（系統(tǒng)態(tài)）來進(jìn)行保護(hù)。

3.進(jìn)程狀態(tài)及其轉(zhuǎn)換

★進(jìn)程的三種基本狀態(tài)：執(zhí)行狀態(tài)、就緒狀態(tài)、等待狀態(tài)（又稱阻塞、掛起、睡眠）

就緒狀態(tài)（Ready）

存在于處理機(jī)調(diào)度隊(duì)列中的那些進(jìn)程，它們已經(jīng)準(zhǔn)備就緒，一旦得到CPU,就立即可以運(yùn)行,

這些進(jìn)程所取的狀態(tài)為就緒狀態(tài)。（有多個(gè)進(jìn)程處于此狀態(tài)）

執(zhí)行狀態(tài)（Running）

當(dāng)進(jìn)程由調(diào)度/分派程序分派后，得到CPU控制權(quán)，它的程序正在運(yùn)行，該進(jìn)程所處的狀態(tài)為執(zhí)

行狀態(tài)。（在系統(tǒng)中，總只有一個(gè)進(jìn)程處于此狀態(tài)）

等待狀態(tài)（Wait）

若一個(gè)進(jìn)程正在等待某個(gè)事件的發(fā)生（如等待I/O的完成），而暫停執(zhí)行，這時(shí)，即使給它CPU

時(shí)間，它也無法執(zhí)行，則稱該進(jìn)程處于等待狀態(tài)。

★進(jìn)程狀態(tài)轉(zhuǎn)換

運(yùn)行到等待等待某事件的發(fā)生（如等待I/O完成）

等待到就緒事件已經(jīng)發(fā)生（如I/O完成）

運(yùn)行到就緒時(shí)間片到（例如，兩節(jié)課時(shí)間到，下課）

新建進(jìn)程到就緒新創(chuàng)建的進(jìn)程進(jìn)入就緒狀態(tài)

就緒到運(yùn)行當(dāng)處理機(jī)空閉時(shí)，由調(diào)度（分派）程序從就緒進(jìn)程隊(duì)列中選擇一個(gè)進(jìn)程占用CPUo

進(jìn)程控制：就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤銷進(jìn)程以及完成進(jìn)程各狀態(tài)的

轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。

原語：把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。

用于進(jìn)程控制的原語有：創(chuàng)建原語、撤銷原語、阻塞原語、喚醒原語。

進(jìn)程創(chuàng)建方式：由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建；由父進(jìn)程創(chuàng)建。進(jìn)程創(chuàng)建系統(tǒng)調(diào)用：

create（name,priority,start-addr）UNIX系統(tǒng)：fork（）

進(jìn)程撤銷：（1）該進(jìn)程已完成所要求的功能而正常終止（2）由于某種錯(cuò)誤導(dǎo)致非正常終止（3）

祖先進(jìn)程要求撤銷某個(gè)子進(jìn)程。在一般操作系統(tǒng)中進(jìn)程撤消的系統(tǒng)調(diào)用是：killUNIX系統(tǒng)中

是exit。如果撤銷進(jìn)程有自己的子進(jìn)程，則撤銷原語先撤銷其子進(jìn)程的PCB結(jié)構(gòu)并釋放子進(jìn)

程所釋放的資源后，再撤銷當(dāng)前進(jìn)程的PCB結(jié)構(gòu)和釋放其資源。

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

當(dāng)一個(gè)處在運(yùn)行狀態(tài)的進(jìn)程，因等待某個(gè)事件的發(fā)生（如等待打印機(jī)）而不能繼續(xù)運(yùn)行時(shí)，將

調(diào)用進(jìn)程掛起系統(tǒng)調(diào)用，把進(jìn)程的狀態(tài)置為阻塞狀態(tài)，并調(diào)用進(jìn)程調(diào)度程序（等于讓出處理

機(jī)）。

進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)換成阻塞狀態(tài)是由進(jìn)程掛起原語實(shí)現(xiàn)的，因此，調(diào)用進(jìn)程掛起操作是在進(jìn)程

處于運(yùn)行狀態(tài)下執(zhí)行的。它的執(zhí)行將引起等待某事件的隊(duì)列的改變.

一個(gè)正在運(yùn)行的進(jìn)程會(huì)因等待某事件（例如，等待打印機(jī)）的發(fā)生，由運(yùn)行狀態(tài)轉(zhuǎn)換成阻塞狀

態(tài)，當(dāng)它等待的事件發(fā)生后，這個(gè)進(jìn)程將由阻塞狀態(tài)轉(zhuǎn)換成就緒狀態(tài)。這種轉(zhuǎn)換由進(jìn)程喚醒操

作完成。

喚醒一個(gè)進(jìn)程有兩種方式：系統(tǒng)進(jìn)程喚醒、事件發(fā)生進(jìn)程喚醒。

調(diào)用進(jìn)程喚醒操作一般在中斷處理、進(jìn)程通信等過程中。例如，打印機(jī)完成中斷處理程序，在

完成了打印完成的操作后，就去檢查等待打印機(jī)的隊(duì)列，若不為空，則調(diào)用進(jìn)程喚醒操作，喚

醒一個(gè)（或多個(gè)）等待打印機(jī)的進(jìn)程。

4.進(jìn)程互斥

產(chǎn)生互斥的原因：資源共享、進(jìn)程合作

★臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。

★臨界區(qū)：每個(gè)進(jìn)程中訪問臨界資源的那段程序段稱為臨界區(qū)（臨界段）。

間接制約：由于共享某公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象稱為有共

享公有資源而造成的對(duì)并發(fā)進(jìn)程執(zhí)行速度的間接制約，簡稱間接制約。

★互斥：在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某臨界區(qū)時(shí)，就不允許其它進(jìn)程進(jìn)入，否則就會(huì)

發(fā)生（后果）無法估計(jì)的錯(cuò)誤。我們把進(jìn)程之間的這種相互制約的關(guān)系稱為互斥。

進(jìn)入臨界區(qū)的準(zhǔn)則：

（1）不能假設(shè)各并發(fā)進(jìn)程的相對(duì)執(zhí)行速度；

（2）并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)、它不能阻止其他進(jìn)程進(jìn)入臨界區(qū);

（3）并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請(qǐng)進(jìn)入界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入；

（4）當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有限的時(shí)間內(nèi)使其進(jìn)入。

解決進(jìn)程互斥的最簡單的辦法是加鎖。

■在系統(tǒng)中為每個(gè)臨界資源設(shè)置一個(gè)鎖位，

■1表示資源可用，

■0表示資源已被占用（不可用）。

這樣當(dāng)一個(gè)進(jìn)程使用某個(gè)臨界資源之前必須完成下列操作：

L考察鎖位的值；

2.若原來的值是為“1”，將鎖位置為“0”（占用該資源）；

3、若原來值是為“0”，（該資源已被別人占用），則轉(zhuǎn)到1。

當(dāng)進(jìn)程使用完資源后，將鎖位置為“1”，稱為開鎖操作。

5.信號(hào)量及P、V原語

★信號(hào)量sem:是一個(gè)整數(shù)，在sem大于等于零時(shí)，代表可供并發(fā)資源使用的資源實(shí)體數(shù)，但

sem小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。sem代表資源的實(shí)體。在實(shí)際應(yīng)用中應(yīng)準(zhǔn)確

地說明sem的意義和初值。

★P操作：

（1）sem減1；

（2）若sem減1后仍大于等于0,則進(jìn)程繼續(xù)執(zhí)行；

（3）若結(jié)果小于0,則該進(jìn)程掛起。

注：掛起該進(jìn)程包括：保留調(diào)用進(jìn)程CPU現(xiàn)場；置“等待”狀態(tài)；入等待隊(duì)列；轉(zhuǎn)進(jìn)程調(diào)度；

V操作：

(1)S值加1；

(2)若相加結(jié)果大于0,進(jìn)程繼續(xù)執(zhí)行；

(3)否則，喚醒一個(gè)(或多個(gè))等待該信號(hào)燈的進(jìn)程，然后本進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。

算法:V

輸入：S

輸出：無

(

S++；

if(s<=0)

喚醒等待S的進(jìn)程;

}

★P、V原語實(shí)現(xiàn)互斥的原理

當(dāng)一個(gè)進(jìn)程想要進(jìn)入臨界區(qū)時(shí)，它必須先執(zhí)行P原語操作以將信號(hào)量sem減1。在一個(gè)進(jìn)程完成

對(duì)臨界資源的操作后，它必須執(zhí)行V原語操作以釋放它占用的臨界資源。由于信號(hào)量初始值為

1,所以，任一進(jìn)程在執(zhí)行P原語操作之后將sem的值變?yōu)?,表示該進(jìn)程可以進(jìn)入臨界區(qū)。在

該進(jìn)程未執(zhí)行V原語操作之前如有另一進(jìn)程想進(jìn)入臨界區(qū)的話，它也應(yīng)先執(zhí)行P原語操作，從

而使sem的值變?yōu)?1,因此，第二個(gè)進(jìn)程將會(huì)被阻塞，直到第一個(gè)進(jìn)程執(zhí)行V原語操作之后,

sem的值變?yōu)?,從而可喚醒第二個(gè)進(jìn)程進(jìn)入就緒隊(duì)列，經(jīng)調(diào)度后進(jìn)入臨界區(qū)。在第二個(gè)進(jìn)程執(zhí)

行完V原語操作之后，如果沒有其它進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)的話，則sem又恢復(fù)到初始值。

用信號(hào)量實(shí)現(xiàn)兩并發(fā)進(jìn)程Pa,Pb互斥的描述如下:

(1)設(shè)sem為互斥信號(hào)量，其取值范圍為(1,0,-Do

(2)其中sem=l標(biāo)志進(jìn)程Pa,Pb都未進(jìn)入類名為S的臨界區(qū)，sem=0表示進(jìn)程Pa,Pb已進(jìn)入

類名為S的臨界區(qū)，sem=-l表示進(jìn)程Pa,Pb中，一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一進(jìn)程等

待進(jìn)入臨界區(qū)。

⑶描述

Pa：

P(sem)

<S>

V(sem):

Pb：

P(sem)

<S>

V(sem)::

main()甫個(gè)進(jìn)程并發(fā)研時(shí)，pmt值1、0,7.

(若print*表示賄進(jìn)程使用打卬機(jī)；

intprint=l;￥pnnt=0,表示有一個(gè)進(jìn)攝正在使用打印機(jī);

cobegin若prints,表示有一進(jìn)程正在使用打削L,

pa();還有一個(gè)進(jìn)程等件使用瓶機(jī)

此。；

cnrl

pa()

{

p(print);PXnt)J

使用打印機(jī)；

使用打印機(jī);

vnt);

v(print);

??,/

1_

6.進(jìn)程同步

★同步：把異步環(huán)境下的一組并發(fā)進(jìn)程，因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等

待，使得各進(jìn)程按一定的速度執(zhí)行的過程稱為進(jìn)程間的同步。

用wait(消息名)表示進(jìn)程等待合作進(jìn)程發(fā)來的消息.

功能：等待到消息名為true的進(jìn)程繼續(xù)執(zhí)行。

用signal(消息名)表示向合作進(jìn)程發(fā)送消息

功能：發(fā)送消息名，并將其值置為true。

利用過程wait和singnal描述計(jì)算進(jìn)程Pc和打印進(jìn)程Pp的同步關(guān)系

(1)設(shè)消息名Bufempty表示buf為空，消息名Buffull表示Buf中裝滿了數(shù)據(jù)。

(2)初始化Bufempty=true,Buffull二false.。

(3)描述：

Pc:

A:wait(Bufempty)

計(jì)算

B苗計(jì)算結(jié)果

Bufemptyfalse

signal(Buffull)

GotoA

Pp：

B:wait(Bufful)

打印Buf中的數(shù)據(jù)

清除Buf中的數(shù)據(jù)

Buffulfalse

signal(Bufempty)

GotoB

★私有信號(hào)量(privateSemaphore):進(jìn)程同步的信號(hào)量只及制約進(jìn)程及被制約進(jìn)程有關(guān)而不

是及整組并發(fā)進(jìn)程有關(guān)。因此該信號(hào)量稱為私有信號(hào)量。

★用P,V原語操作實(shí)現(xiàn)同步

首先，為各并發(fā)進(jìn)程設(shè)置私有信號(hào)量，

然后，為私有信號(hào)量賦初值，

最后，利用P,V原語和私有信號(hào)量規(guī)定各進(jìn)程的執(zhí)行順序。

例：設(shè)進(jìn)程Pa和Pb通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)。Pa為發(fā)送進(jìn)程，Pb為接收進(jìn)程。Pa發(fā)送數(shù)據(jù)

時(shí)調(diào)用發(fā)送過程deposit(data),Pb接受數(shù)據(jù)時(shí)調(diào)用過程remove(data),且數(shù)據(jù)的發(fā)送和接受

過程滿足如下條件：

任口――Bufl—Buf2—―…一一Bufz——BufT?—

(1)在

PA：deposit(data)：

beginlocalx

P(Bufempty);

按FIFO方式選擇一個(gè)空緩沖區(qū)Buf(x)；

Buf(x)-dat

Buf(x)置滿標(biāo)記

V(Buffull)

end

PB：remove(data)：

Beginlocalx

P(Buffull)；

按FIFO方式選擇一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)Buf(x)

data?<—Buf(?)

Buf(%)置空標(biāo)記

V(Bufempty)

End

★7.生產(chǎn)者及消費(fèi)者問題

對(duì)于生產(chǎn)者進(jìn)程：產(chǎn)生一個(gè)數(shù)據(jù)，當(dāng)要送入緩沖區(qū)時(shí)，要檢查緩沖區(qū)是否已滿，若未滿，則可

將數(shù)據(jù)送入緩沖區(qū)，并通知消費(fèi)者進(jìn)程；否則，等待；

對(duì)于消費(fèi)者進(jìn)程：當(dāng)它去取數(shù)據(jù)時(shí)，要看緩沖區(qū)中是否有數(shù)據(jù)可取，若有則取走一個(gè)數(shù)據(jù)，并

通知生產(chǎn)者進(jìn)程，否則，等待。

這種相互等待，并互通信息就是典型的進(jìn)程同步。

同時(shí)，緩沖區(qū)是個(gè)臨界資源，因此,諸進(jìn)程對(duì)緩沖區(qū)的操作程序是一個(gè)共享臨界區(qū)，因此，還

有個(gè)互斥的問題。

deposit(data)：

begin

P(avail)

P(mutex)

送數(shù)據(jù)入緩沖區(qū)某單元

V(full)

V(mutex)

end

remove(data)：

begin

P(ftill)

P(mutex)

取緩沖X中某單元數(shù)據(jù)

V(avail)

V(mutex)

End

full：緩沖區(qū)產(chǎn)品數(shù)目,初佰為O,eg》：緩沖區(qū)可存放產(chǎn)品的空位.初值為n;

mutex:對(duì)鐐沖區(qū)互斥值號(hào)火丁.初值為1,

pr-oducer"()consumeirO

{{

while(:生產(chǎn)未完成)while(汪瞿名連續(xù)余肖贊)

{{

P(full)；

生*一個(gè)產(chǎn)品；p(mutex);

P(empty);從緩沖區(qū)中取用一個(gè)產(chǎn)品:

p(mutex);v(mutex);

乂存產(chǎn)品放入緩沖區(qū)；v(empty).

v(mut-ex);消費(fèi)一個(gè)產(chǎn)品；

v《full);???*?

)}

})

8.進(jìn)程通信

通信(communication)意味著進(jìn)程間傳遞數(shù)據(jù)。操作系統(tǒng)可以看作是各種進(jìn)程組成的，這些進(jìn)

程都具有各自獨(dú)立的功能，且大多數(shù)都被外部需要而啟動(dòng)執(zhí)行。

在單機(jī)系統(tǒng)中進(jìn)程的通信有4種形式：

(1)主從式

(2)會(huì)話式

(3)消息或郵箱機(jī)制

(4)共享存儲(chǔ)區(qū)方式

會(huì)話方式的特點(diǎn)：

(1)使用進(jìn)程在使用服務(wù)進(jìn)程所提供的服務(wù)之前，必須得到服務(wù)進(jìn)程的許可。

(2)服務(wù)進(jìn)程根據(jù)使用進(jìn)程的要求提供服務(wù)，但對(duì)所提供服務(wù)的控制由服務(wù)進(jìn)程自身完成。

(3)使用進(jìn)程和服務(wù)進(jìn)程在進(jìn)行通信時(shí)有固定連接關(guān)系。

消息或郵箱機(jī)制的特點(diǎn)是：

(1)只要存在空緩沖區(qū)或郵箱，發(fā)送進(jìn)程就可以發(fā)送消息。

(2)及會(huì)話系統(tǒng)不同，發(fā)送進(jìn)程和接受進(jìn)程之間無直接聯(lián)接關(guān)系。

(3)發(fā)送進(jìn)程和接受進(jìn)程之間存在緩沖區(qū)或郵箱用來存放被傳送消息。

郵箱通信就是由發(fā)送進(jìn)程申請(qǐng)建立一及接受進(jìn)程聯(lián)接的郵箱。設(shè)置郵箱的最大好處是發(fā)送進(jìn)程

和接受進(jìn)程之間沒有時(shí)間上的限制。

共享存儲(chǔ)區(qū)方式不要求數(shù)據(jù)移動(dòng)，兩個(gè)需要互相交換信息的進(jìn)程通過共享數(shù)據(jù)區(qū)的操作達(dá)到互

相通信的目的。

9.死鎖問題

死鎖：指個(gè)并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前

不會(huì)釋放自己所擁有的資源。從而造成大家都想得到資源而又得不到資源，個(gè)并發(fā)進(jìn)程不能繼

續(xù)向前推進(jìn)的狀態(tài)。

★死鎖的起因：根本原因在于系統(tǒng)提供的資源個(gè)數(shù)少于并發(fā)進(jìn)程所要求的該類資源數(shù)。

★產(chǎn)生死鎖有四個(gè)必要條件：

(1)互斥條件。并發(fā)進(jìn)程所要求和占有的資源是不能同時(shí)被兩個(gè)以上進(jìn)程使用或操作的，進(jìn)程

對(duì)他所需要的資源進(jìn)行排他性控制。

(2)不剝奪條件。進(jìn)程所獲得的資源在未使用完畢之前，不能被其它進(jìn)程強(qiáng)行剝奪，而只能由

獲得該資源的進(jìn)程自己釋放。

(3)部分分配。進(jìn)程每次申請(qǐng)它所需要的一部分資源，在等待新資源的同時(shí)，繼續(xù)占用已分配

的資源。

(4)環(huán)路等待條件。存在一種進(jìn)程循環(huán)鏈，鏈中每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所

請(qǐng)求。

只要有一個(gè)條件不滿足，死鎖就可解除。

預(yù)防死鎖

1.破壞“請(qǐng)求及保持條件”每個(gè)進(jìn)程在運(yùn)行之前，必須預(yù)先提出自己所要使用的全部資源，調(diào)

度程序在該進(jìn)程所需要的資源末得到滿足之前，不讓它們投入運(yùn)行，并且當(dāng)資源一旦分配給某

個(gè)進(jìn)程之后，那么在該進(jìn)程的整個(gè)運(yùn)行期間相應(yīng)資源一直被它占有，這就破壞了產(chǎn)生死鎖的部

分分配條件。

2.破壞環(huán)路條件對(duì)系統(tǒng)提供的每一項(xiàng)資源，由系統(tǒng)設(shè)計(jì)者將它們按類型進(jìn)行線性排隊(duì)，并

賦予不同的序號(hào)。

3.資源受控動(dòng)態(tài)分配為了避免死鎖發(fā)生，操作系統(tǒng)必須根據(jù)預(yù)先掌握的關(guān)于資源用法的信息

控制資源分配，使得共同進(jìn)展路徑的下一步不致于進(jìn)入危險(xiǎn)區(qū)，即只要有產(chǎn)生死鎖的可能性,

就避免把一種資源分配給一個(gè)進(jìn)程。

死鎖的檢測和恢復(fù)

1.資源剝奪法

(1)還原算法。即恢復(fù)計(jì)算結(jié)果和狀態(tài)。

(2)建立檢查點(diǎn)主要是用來恢復(fù)分配前的狀態(tài)。

2.撤消進(jìn)程法

按一定的順序中止進(jìn)程序列，直至已釋放到有足夠的資源來完成剩下的資源為止。

第四章

L一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng)，一般都要經(jīng)歷提交、收容、執(zhí)行和完成

四個(gè)狀態(tài)。

一個(gè)作業(yè)在其處于從輸入設(shè)備進(jìn)入外部存儲(chǔ)設(shè)備的過程成為提交狀態(tài)。處于提交狀態(tài)的作業(yè),

因其信息尚未全部進(jìn)入系統(tǒng)，所以不能被調(diào)用程序選取。

收容狀態(tài)也稱為后備狀態(tài)，輸入管理系統(tǒng)不斷地將作業(yè)輸入到外存中對(duì)應(yīng)部分（或稱輸入井,

即專門用來存放待處理作業(yè)信息的一組外存分區(qū)）。若一個(gè)作業(yè)的全部信息已全部被輸入進(jìn)輸入

井，那么，在它還未被調(diào)度去執(zhí)行之前，該作業(yè)處于收容狀態(tài)。

作業(yè)調(diào)度程序從后備作業(yè)中選取若干作業(yè)到內(nèi)存投入運(yùn)行。它為被選中作業(yè)建立進(jìn)程并分配必

要的資源，這時(shí)，這些被選中的作業(yè)處于執(zhí)行狀態(tài)。

當(dāng)作業(yè)運(yùn)行完畢，但它所占用的資源尚未全部被系統(tǒng)收回時(shí)，該作業(yè)處于完成狀態(tài)。

一般來說，處理機(jī)調(diào)度可分為4級(jí)：作業(yè)調(diào)度、交換調(diào)度、進(jìn)程調(diào)度、線程調(diào)度。

作業(yè)調(diào)度：又稱宏觀調(diào)度或高級(jí)調(diào)度，其主要任務(wù)是按一定的原則對(duì)外存輸入井上的大量后備

作業(yè)進(jìn)行選擇，給選出的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等必要的資源，并建立相應(yīng)的根程序,

以使該作業(yè)的進(jìn)程獲得競爭處理機(jī)的權(quán)利，另外，當(dāng)該作業(yè)執(zhí)行完畢時(shí)，還負(fù)責(zé)回收系統(tǒng)資

源。

交換調(diào)度：又稱中級(jí)調(diào)度，其主要任務(wù)是按照給定的原則和策略，將處于外存交換區(qū)中的就緒

狀態(tài)或就緒等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存，或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進(jìn)程交換到外

存交換區(qū)。交換調(diào)度主要涉及內(nèi)存的管理和擴(kuò)充，一般將它歸在存儲(chǔ)管理之中。

進(jìn)程調(diào)度：又稱微觀調(diào)度或低級(jí)調(diào)度，其主要任務(wù)是按照某種策略和方法選取一個(gè)處于就緒狀

態(tài)的進(jìn)程占用處理機(jī)。

只有在多道批處理系統(tǒng)中才有作業(yè)調(diào)度，而在分時(shí)和實(shí)時(shí)系統(tǒng)中一般只有進(jìn)程調(diào)度、交換調(diào)度

和線程調(diào)度。

這是因?yàn)樵诜謺r(shí)和實(shí)時(shí)系統(tǒng)中，為了縮短響應(yīng)時(shí)間或?yàn)榱藵M足用戶需求的截止時(shí)間，作業(yè)不是

建立在外存中，而是直接建立在內(nèi)存中。

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

作業(yè)調(diào)度的功能:

(1)記錄系統(tǒng)中各作業(yè)的狀況，包括執(zhí)行階段的有關(guān)情況。通常，系統(tǒng)為每個(gè)作業(yè)建立一個(gè)作

業(yè)控制表JCB記錄這些有關(guān)信息。

作業(yè)控制塊JCB：在作業(yè)調(diào)度的過程中記錄作業(yè)各方面的信息。它隨作業(yè)的創(chuàng)建而產(chǎn)生，隨作業(yè)

的撤消而被清除。

(2)從后備隊(duì)列中選取一部分作業(yè)投入執(zhí)行

(3)為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。

(4)在作業(yè)執(zhí)行結(jié)束時(shí)做好善后處理工作。

(1)作業(yè)調(diào)度目標(biāo)：

(2)對(duì)所有作業(yè)應(yīng)該是公平合理的。

(3)應(yīng)使設(shè)備有高的利用率。

(4)每天執(zhí)行盡可能多的作業(yè)

(5)有快的響應(yīng)時(shí)間

對(duì)于批處理系統(tǒng)，作業(yè)的平均周轉(zhuǎn)時(shí)間或平均帶權(quán)周轉(zhuǎn)時(shí)間，被作為衡量調(diào)度算法優(yōu)劣的標(biāo)

準(zhǔn)；對(duì)于分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)，外加平均響應(yīng)時(shí)間作為衡量調(diào)度算法優(yōu)劣的標(biāo)準(zhǔn)

★⑴周轉(zhuǎn)時(shí)間：

作業(yè)i從提交時(shí)刻到完成時(shí)刻稱為作業(yè)的周轉(zhuǎn)時(shí)間。Ti=Tei-Tsi

Tei為作業(yè)i的完成時(shí)間，Tsi為作業(yè)的提交時(shí)間

一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間，包含兩部分：一是等待時(shí)間；二為執(zhí)行

時(shí)間

Ti=Twi+Tri

Twi主要是指作業(yè)i由后備狀態(tài)到執(zhí)行狀態(tài)的等待時(shí)間，它不包括作業(yè)進(jìn)入執(zhí)行狀態(tài)后的等待

時(shí)間。

★一批作業(yè)的平均周轉(zhuǎn)時(shí)間為:

T==l/nETi

i=l

★帶權(quán)周轉(zhuǎn)時(shí)間

Wi=Ti/TriTi作業(yè)周轉(zhuǎn)時(shí)間Tri作業(yè)執(zhí)行時(shí)間

★一批作業(yè)的平均帶權(quán)周轉(zhuǎn)時(shí)間為

n

W=l/nSWi

i=l

3.進(jìn)程調(diào)度

進(jìn)程調(diào)度的功能：

①用PCB塊記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況

②按照一定的調(diào)度算法，選擇一個(gè)處于就緒狀態(tài)的進(jìn)程，給它分配處理機(jī)（這是最重要的功能）

③實(shí)施進(jìn)行進(jìn)程上下文的切換

（1）引起進(jìn)程調(diào)度的原因：

（2）正在執(zhí)行的進(jìn)程執(zhí)行完畢。這時(shí)，如果不選擇新的就緒進(jìn)程執(zhí)行，將浪費(fèi)處理機(jī)資源。

（3）執(zhí)行中進(jìn)程自己調(diào)用阻塞原語將自己阻塞起來進(jìn)入睡眠等待狀態(tài)。

（4）執(zhí)行中進(jìn)程調(diào)用了P原語操作，從而因資源不足而被阻塞;或調(diào)用了V原語激活了等待資

源的進(jìn)程隊(duì)列。

（5）執(zhí)行中進(jìn)程提出了I/O請(qǐng)求后被阻塞。

（6）在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完。

在執(zhí)行完系統(tǒng)調(diào)用，在系統(tǒng)程序返回用戶進(jìn)程，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一

新的用戶程序執(zhí)行。

以上都是CPU執(zhí)行不可剝奪方式下做引起的進(jìn)程調(diào)度的原因，在CPU執(zhí)行方式是可剝奪時(shí)，還

有:

就緒隊(duì)列中的某進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級(jí)，從而也將發(fā)生進(jìn)程調(diào)度。

可剝奪方式：即就緒隊(duì)列中一旦有優(yōu)先級(jí)高于當(dāng)前進(jìn)程優(yōu)先級(jí)的進(jìn)程存在時(shí)，便立即發(fā)生進(jìn)程

調(diào)度，轉(zhuǎn)讓處理機(jī)。

非剝奪方式（不可剝奪方式）：即使在就緒隊(duì)列存在有優(yōu)先級(jí)高于當(dāng)前執(zhí)行進(jìn)程時(shí)，當(dāng)前進(jìn)程仍

將繼續(xù)占有處理機(jī)，直到該進(jìn)程因自己調(diào)度調(diào)用原語操作或、等待I/O進(jìn)入阻塞狀態(tài)或時(shí)間片

用完時(shí)才重新發(fā)生調(diào)度讓出處理機(jī)。

進(jìn)程調(diào)度性能評(píng)價(jià)

（1）進(jìn)程調(diào)度性能是衡量操作系統(tǒng)性能的一個(gè)重要指標(biāo)

（2）在大多數(shù)情況下，利用測試或模擬系統(tǒng)響應(yīng)時(shí)間的方法來評(píng)價(jià)進(jìn)程調(diào)度的性能

★4.調(diào)度算法

①先來先服務(wù)（FCFS）算法

將用戶作業(yè)和就緒進(jìn)程按提交順序或變成就緒狀態(tài)的先后排成隊(duì)列，并按照先來先服務(wù)的方式

進(jìn)行調(diào)度處理。

優(yōu)點(diǎn)：在一般意義下是公平的，即每個(gè)作業(yè)或進(jìn)程都按照它們?cè)陉?duì)列中等待時(shí)間長短來決定它

們是否優(yōu)先享受服務(wù)。

缺點(diǎn)：對(duì)于那些執(zhí)行時(shí)間較短的作業(yè)或進(jìn)程來說，如果它們?cè)谀承﹫?zhí)行時(shí)間很長的作業(yè)或進(jìn)程

之后到達(dá)，則它們等待很長時(shí)間。

②（時(shí)間片）輪轉(zhuǎn)法（RR）

算法描述：就緒隊(duì)列按進(jìn)程到達(dá)的時(shí)間來排列。處理機(jī)的時(shí)間被分為固定大小的時(shí)間片。調(diào)度

程序總是選擇就緒隊(duì)列中的第一個(gè)進(jìn)程。一個(gè)執(zhí)行進(jìn)程如果在用完一個(gè)時(shí)間片后還沒有完成其

任務(wù)，它就自動(dòng)釋放處理機(jī)回到就緒隊(duì)列的末尾重新排隊(duì)，等待下一次被調(diào)度。

缺點(diǎn)：只能用來分配那些可搶占資源，而且這種算法只能用于進(jìn)程調(diào)度，不能用于作業(yè)調(diào)度（作

業(yè)調(diào)度包含了不可搶占資源）。

時(shí)間片的選取非常重要，時(shí)間片長度的選擇會(huì)直接影響系統(tǒng)開銷和響應(yīng)時(shí)間。如果時(shí)間

片長度過短，則調(diào)度程序剝奪處理機(jī)的次數(shù)增多，這將使進(jìn)程上下文交換次數(shù)也大大增加，加

重了系統(tǒng)開銷。如果時(shí)間片長度選擇過長（大），大到一個(gè)進(jìn)程足以完成其全部運(yùn)行工作所需的

時(shí)間，那么時(shí)間片輪轉(zhuǎn)法就退化為先來先服務(wù)策略了。最佳的時(shí)間片量值應(yīng)能使分時(shí)用戶得到

好的響應(yīng)時(shí)間。

時(shí)間片的確定

在輪轉(zhuǎn)法中，時(shí)間片長度q根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求R和就緒隊(duì)列中所能容納的最大進(jìn)程數(shù)

Nmax確定的。q=R/Nmax

一種改進(jìn)的方法就是每當(dāng)一輪調(diào)度開始時(shí)，系統(tǒng)根據(jù)就緒隊(duì)列中當(dāng)前的進(jìn)程數(shù)計(jì)算一次q,作

為新一輪調(diào)度的時(shí)間片。

③多級(jí)反饋輪轉(zhuǎn)法（進(jìn)程調(diào)度）

（1）在時(shí)間片輪轉(zhuǎn)法中設(shè)置三個(gè)就緒隊(duì)列

a.時(shí)間片完成就緒隊(duì)列

b.等待結(jié)束就緒隊(duì)列

c.新進(jìn)程就緒隊(duì)列

（2）每個(gè)隊(duì)列建立時(shí)按FCFS排列，同一隊(duì)列中進(jìn)程的優(yōu)先級(jí)相同，不同隊(duì)列具有不同的優(yōu)先

級(jí)

優(yōu)先級(jí)高的隊(duì)列中進(jìn)程的時(shí)間片短，優(yōu)先級(jí)低的隊(duì)列中進(jìn)程的時(shí)間片長。

（3）進(jìn)程調(diào)度時(shí)，先調(diào)度高優(yōu)先級(jí)就緒隊(duì)列中的進(jìn)程，當(dāng)高優(yōu)先級(jí)就緒隊(duì)列為空時(shí)才調(diào)度優(yōu)先

級(jí)低的就緒隊(duì)列中的進(jìn)程

（4）一個(gè)進(jìn)程在執(zhí)行過程中要經(jīng)歷不同的就緒隊(duì)列

④優(yōu)先級(jí)法

算法描述：按照某種原則給作業(yè)或進(jìn)程確定一個(gè)優(yōu)先級(jí)，進(jìn)程的就緒隊(duì)列或作業(yè)的后備隊(duì)列按

對(duì)象的優(yōu)先級(jí)進(jìn)行排列，高前低后。對(duì)象進(jìn)入隊(duì)列是插入。當(dāng)調(diào)度發(fā)生時(shí)，排列在最前面的進(jìn)

程或作業(yè)被調(diào)度。

確定優(yōu)先級(jí)的方法有兩類：動(dòng)態(tài)法和靜態(tài)法

靜態(tài)法是根據(jù)作業(yè)或進(jìn)程的靜態(tài)特性，在作業(yè)或進(jìn)程開始執(zhí)行之前就確定它們的優(yōu)先級(jí)，一旦

開始執(zhí)行后就不能改變。

動(dòng)態(tài)法：把作業(yè)或進(jìn)程靜態(tài)性和動(dòng)態(tài)性結(jié)合起來確定作業(yè)或進(jìn)程的優(yōu)先級(jí)，隨著作業(yè)或進(jìn)程的

執(zhí)行過程，優(yōu)先級(jí)不斷變化。

（1）作業(yè)調(diào)度中靜態(tài)優(yōu)先級(jí)確定原則：

（2）由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)?shù)膬?yōu)先級(jí)

（3）由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級(jí)。

（4）系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級(jí)。

（1）進(jìn)程調(diào)度靜態(tài)優(yōu)先級(jí)確定原則：

（2）按照進(jìn)程的類型給及不同的優(yōu)先級(jí)。

（3）將作業(yè)的靜態(tài)優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)。

由于在進(jìn)程調(diào)度中靜態(tài)優(yōu)先級(jí)確定方法的缺陷：系統(tǒng)效率低、調(diào)度性能不高，所以多采用動(dòng)態(tài)

的方法確定優(yōu)先級(jí)。

（1）進(jìn)程調(diào)度動(dòng)態(tài)優(yōu)先級(jí)確定原則：

根據(jù)進(jìn)程占有CPU時(shí)間的長短來決定。一個(gè)進(jìn)程占有處理機(jī)時(shí)間越長，則在被阻塞后再次獲得

調(diào)度的優(yōu)先級(jí)越低，反之，獲得調(diào)度的可能性越大

根據(jù)就緒進(jìn)程等待CPU的時(shí)間長短來決定。一個(gè)就緒進(jìn)程在就緒隊(duì)列中等待的時(shí)間越長，則它

獲得調(diào)度選中的優(yōu)先級(jí)就越高。

⑤最短作業(yè)優(yōu)先法SJF（作業(yè)調(diào)度）

選擇那些估計(jì)需要執(zhí)行時(shí)間最短的作業(yè)投入執(zhí)行，為它們創(chuàng)建進(jìn)程和分配資源。

優(yōu)點(diǎn)：可使得系統(tǒng)在同一時(shí)間內(nèi)處理的作業(yè)個(gè)數(shù)最多，從而吞吐量也就大于其他調(diào)度方式。

缺點(diǎn)：對(duì)于一個(gè)不斷有作業(yè)進(jìn)入的批處理系統(tǒng)來說，最短作業(yè)優(yōu)先法有可能使得那些長作業(yè)永

遠(yuǎn)得不到調(diào)度執(zhí)行的機(jī)會(huì)。

⑥最高響應(yīng)比優(yōu)先法（作業(yè)調(diào)度）

綜合平衡FCFS和SJF,既考慮等待時(shí)間長的作業(yè)，也照顧執(zhí)行時(shí)間短的作業(yè)。

響應(yīng)比：R=（等待時(shí)間W+執(zhí)行時(shí)間T）/執(zhí)行時(shí)間T

優(yōu)點(diǎn)：長作業(yè)有機(jī)會(huì)獲得調(diào)度執(zhí)行

缺點(diǎn)：同一時(shí)間內(nèi)處理的作業(yè)數(shù)少于最短作業(yè)優(yōu)先法，吞吐量也小于最短作業(yè)優(yōu)先法

調(diào)度前計(jì)算響應(yīng)比，系統(tǒng)開銷增加。

算法評(píng)價(jià)

FCFS算法

X：作業(yè)到達(dá)率；

口：服務(wù)器（主機(jī)）的服務(wù)率；

只有當(dāng)人＜口時(shí)系統(tǒng)才是穩(wěn)定的。

n:系統(tǒng)中的平均作業(yè)個(gè)數(shù)；

R：系統(tǒng)響應(yīng)時(shí)間；

P：X/u,是系統(tǒng)中存在作業(yè)的概率，1-P是系統(tǒng)中沒有作業(yè)的概率。

n=P/（1-P）

Little結(jié)果：n=XR；R=n/人

FCFS算法的評(píng)價(jià)：

R=n/X=p/（1-p）*1/X

RR算法

q：時(shí)間片；

k：每個(gè)進(jìn)程平均需要的時(shí)間片數(shù)，即該進(jìn)程到達(dá)等待隊(duì)列的次數(shù)；

線性優(yōu)先級(jí)法的調(diào)度性能

1/U：平均服務(wù)時(shí)間，貝！I：l/P=kXq

RR算法的評(píng)價(jià)：

已使用過k次時(shí)間片的進(jìn)程的響應(yīng)時(shí)間是：

R（k）=p/（X（1-P））

=1/（U（1-P））=kXq/（l-p）

FCFS方式短作業(yè)駐留時(shí)間及長作業(yè)相同，對(duì)短作業(yè)不利。

輪轉(zhuǎn)法所需服務(wù)時(shí)間短的顧客響應(yīng)時(shí)間將會(huì)小于所需服務(wù)時(shí)間長的顧客響應(yīng)時(shí)間。

實(shí)時(shí)調(diào)度算法分類：靜態(tài)表格驅(qū)動(dòng)類、靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶先式調(diào)度算法類、動(dòng)態(tài)計(jì)劃調(diào)度算法

類、盡力而為調(diào)度算法類。

具有代表性的實(shí)時(shí)調(diào)度算法

時(shí)限式調(diào)度法（靜態(tài)表格驅(qū)動(dòng)類代表）：是一種以滿足用戶要求時(shí)限為調(diào)度原則的算法。

算法描述：時(shí)限有兩種：處理開始時(shí)限和處理結(jié)束時(shí)限，在實(shí)際中可以使用任一種時(shí)限。

頻率單調(diào)調(diào)度（靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶先式調(diào)度算法類代表）：是一種被廣泛用于多周期性實(shí)時(shí)處

理的調(diào)度算法。其基本原理是頻率低（周期越長）的任務(wù)優(yōu)先級(jí)越低。

第五章

L存儲(chǔ)器：能接收數(shù)據(jù)和保存數(shù)據(jù)、而且能根據(jù)命令提供這些數(shù)據(jù)的裝置。

存儲(chǔ)器分成兩類：內(nèi)存儲(chǔ)器（簡稱內(nèi)存、主存、物理存儲(chǔ)器）外存儲(chǔ)器（簡稱外存、輔助存儲(chǔ)

器）

虛擬存儲(chǔ)器：為用戶提供一種不受物理存儲(chǔ)器結(jié)構(gòu)和容量限制的存儲(chǔ)器的技術(shù)稱為虛擬存儲(chǔ)器,

或稱虛擬存儲(chǔ)技術(shù)。虛擬存儲(chǔ)器需要大容量的外存儲(chǔ)器的支持，或稱物資基礎(chǔ)。

程序地址：用戶編程序時(shí)所用的地址（或稱邏輯地址、虛地址），基本單位可及內(nèi)存的基本

單位相同，也可以不相同。

程序地址空間（邏輯地址空間、虛地址空間）：用戶的程序地址的集合稱為邏輯地址空間，它的

編址總是從0開始的，可以是一維線性空間，也可以是多維空間。

物理地址：把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)存

地址（物理地址、絕對(duì)地址、實(shí)地址），存儲(chǔ)單元占8位，稱作字節(jié)（byte）。

物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維的線性空

間。

（1）安排進(jìn)程的地址方法：

（2）按照物理存儲(chǔ)器中的位置賦予實(shí)際物理地址。好處：CPU執(zhí)行目標(biāo)代碼時(shí)的執(zhí)行速度高。

壞處:由于物理存儲(chǔ)器的容量限制，能裝入內(nèi)存并發(fā)執(zhí)行的進(jìn)程數(shù)將會(huì)大大減少，對(duì)于某

些較大的進(jìn)程來說，當(dāng)其所要求的總內(nèi)存容量超過內(nèi)存容量時(shí)將會(huì)無法執(zhí)行；由于編譯程

序必須知道內(nèi)存的當(dāng)前空閑部分及其地址，并且把一個(gè)進(jìn)程的不同程序段連續(xù)的存放起

來，因此編譯程序?qū)⒎浅?fù)雜。

（3）編譯鏈接程序把用戶源程序編譯后鏈接到一個(gè)以0地址為始地址的線性或多維虛擬地址

空間。

2.存儲(chǔ)管理功能：

★地址映射將程序地址空間中使用的邏輯地址變換成主存中的地址的過程

主存分配按照一定的算法把某一空閑的主存區(qū)分配給作業(yè)或進(jìn)程。

存儲(chǔ)保護(hù)保證用戶程序（或進(jìn)程映象）在各自的存儲(chǔ)區(qū)域內(nèi)操作,互不干擾。

提供虛擬存儲(chǔ)技術(shù)使用戶程序的大小和結(jié)構(gòu)不受主存容量和結(jié)構(gòu)的限制，即使在用戶程序比

實(shí)際主存容量還要大的情況下，程序也能正確運(yùn)行.

★實(shí)現(xiàn)地址映射有三種方式：

①.編程或編譯時(shí)確定地址映射關(guān)系

②.靜態(tài)地址映射

③.動(dòng)態(tài)地址映射

（1）編程或編譯時(shí)確定地址映射關(guān)系

編程時(shí)確定虛一實(shí)地址的關(guān)系是指在用機(jī)器指令編程時(shí)，程序員直接按物理內(nèi)存地址編程，這

種程序在系統(tǒng)中是不能做任何移動(dòng)的，否則就會(huì)出錯(cuò)。

（2）靜態(tài)地址映射

靜態(tài)地址映射是在程序裝入內(nèi)存時(shí)完成從邏輯地址到物理地址的轉(zhuǎn)換的。在一些早期的系統(tǒng)中

都有一個(gè)裝入程序（加載程序），它負(fù)責(zé)將用戶程序裝入系統(tǒng)，并將用戶程序中使用的訪問內(nèi)

存的邏輯地址轉(zhuǎn)換成物理地址。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，不要硬件的支持。

缺點(diǎn)：程序一旦裝入內(nèi)存，移動(dòng)就比較困難。有時(shí)間上的浪費(fèi)。在程序裝入內(nèi)存時(shí)要將所有訪

間內(nèi)存的地址轉(zhuǎn)換成物理地址。

必須占用連續(xù)的內(nèi)存空間，很難做到程序和數(shù)據(jù)的共享。

（3）動(dòng)態(tài)地址映射

動(dòng)態(tài)地址映射是在程序執(zhí)行時(shí)由系統(tǒng)硬件完成從邏輯地址到物理地址的轉(zhuǎn)換的。動(dòng)態(tài)地址映射

是由硬件地執(zhí)行時(shí)完成的，程序中不執(zhí)行的程序就不做地址映射的工作，這樣節(jié)省了CPU的時(shí)

間。重定位寄存器的內(nèi)容由操作系統(tǒng)用特權(quán)指令來設(shè)置，比較靈活。實(shí)現(xiàn)動(dòng)態(tài)地址映射必須

有硬件的支持，并有一定的執(zhí)行時(shí)間延遲。現(xiàn)代計(jì)算機(jī)系統(tǒng)中都采用動(dòng)態(tài)地址映射技術(shù)。

優(yōu)點(diǎn)：可以對(duì)內(nèi)存進(jìn)行非連續(xù)分配，動(dòng)態(tài)重定位提供了實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)，有利于程序段

的共享。

動(dòng)態(tài)地址映射技術(shù)能滿足以下目標(biāo)：

（1）具有給一個(gè)用戶程序任意分配內(nèi)存區(qū)的能力；

（2）可實(shí)現(xiàn)虛擬存儲(chǔ)；

（3）具有重新分配的能力

（4）對(duì)于一個(gè)用戶程序，可以分配到多個(gè)不同的存儲(chǔ)區(qū)

3.內(nèi)外存數(shù)據(jù)傳輸?shù)目刂?/p>

要實(shí)現(xiàn)內(nèi)存擴(kuò)充，在程序執(zhí)行過程中，內(nèi)存和外存之間必須經(jīng)常地交換數(shù)據(jù)。內(nèi)外存的數(shù)據(jù)流

動(dòng)控制方法有兩種

一種是用戶自己控制程序，例子：覆蓋技術(shù)，一種早期的主存擴(kuò)充技術(shù)，要求用戶了解程序結(jié)

構(gòu)，指定各程序段調(diào)入內(nèi)存的先后次序。

另一種是操作系統(tǒng)控制，A交換方式：操作系統(tǒng)把等待狀態(tài)的進(jìn)程換出內(nèi)存，而把等待事件已發(fā)

生，處于就緒態(tài)的進(jìn)程換入內(nèi)存。B請(qǐng)求調(diào)入方式和預(yù)調(diào)入方式：請(qǐng)求調(diào)入方式：在程序執(zhí)行時(shí),

如果所要訪問的程序段或數(shù)據(jù)段不在內(nèi)存中，則操作系統(tǒng)自動(dòng)地從外存將有關(guān)程序段和數(shù)據(jù)段

調(diào)入內(nèi)存地一種操作系統(tǒng)控制方式。預(yù)調(diào)入方式：系統(tǒng)預(yù)測在不遠(yuǎn)的將來會(huì)訪問到的哪些程序

段和數(shù)據(jù)段，并在它們?cè)L問前調(diào)入。

4.內(nèi)存的分配和回收

在多道程序設(shè)計(jì)的環(huán)境中，內(nèi)存分配的功能包括：制定分配策略、構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)、響

應(yīng)系統(tǒng)的內(nèi)存分配的請(qǐng)求和回收系統(tǒng)釋放的內(nèi)存區(qū)。內(nèi)存管理策略有5種：

（1）分配結(jié)構(gòu)登記內(nèi)存使用情況，供分配程序使用的表格和鏈表。

（2）放置策略確定調(diào)入內(nèi)存的程序和數(shù)據(jù)在內(nèi)存中的位置。決定內(nèi)存中放置信息的區(qū)域（或

位置），即如何在若干個(gè)空閑區(qū)中選擇一個(gè)或幾個(gè)空閑區(qū)的原則；

（3）交換策略當(dāng)內(nèi)存不足時(shí)，決定將某些信息調(diào)出內(nèi)存的策略。

（4）調(diào)入策略外存中的程序段和數(shù)據(jù)段什么時(shí)間按照什么樣的控制方式進(jìn)入內(nèi)存

（5）回收策略回收的時(shí)機(jī)，對(duì)所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存空閑區(qū)的整理。

5,內(nèi)存信息的共享及保護(hù)

常用的存儲(chǔ)保護(hù)有三種。硬件法、軟件法、軟硬件結(jié)合

（1）上下界保護(hù)（常用的硬件保護(hù)法）

上界寄存器存放程序裝入內(nèi)存后的開始地址（首址）

下界寄存器存放程序裝入內(nèi)存后的末地址

判別式：上界寄存器W物理地址W下界寄存器

（2）保護(hù)鍵法：為每一個(gè)被保護(hù)存儲(chǔ)塊分配一個(gè)單獨(dú)的保護(hù)鍵。在程序狀態(tài)字中則設(shè)置相應(yīng)的

保護(hù)鍵開關(guān)字段。

（3）界限寄存器及CPU的用戶態(tài)或核心態(tài)工作方式相結(jié)合的保護(hù)方式。用戶態(tài)進(jìn)程只能訪問那

些在界限寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分，而核心態(tài)進(jìn)程則可以訪問整個(gè)內(nèi)存地址空間。

6.分區(qū)存儲(chǔ)管理

分區(qū)管理：把內(nèi)存劃分成若干個(gè)大小不等的區(qū)域，除操作系統(tǒng)占用一個(gè)區(qū)域之外，其余由多道

環(huán)境下的各并發(fā)進(jìn)程共享。

分區(qū)管理基本原理：給每一個(gè)內(nèi)存中的進(jìn)程劃分一塊適當(dāng)大小的存儲(chǔ)區(qū)，以連續(xù)存儲(chǔ)各進(jìn)程的

數(shù)據(jù)和程序，使各進(jìn)程得以并發(fā)執(zhí)行。

按分區(qū)的時(shí)機(jī)，分區(qū)管理可以分為固定分區(qū)、動(dòng)態(tài)分區(qū)。

(1)固定分區(qū)

把內(nèi)存空間分成若干個(gè)大小不等的區(qū)域，稱為分區(qū)。每個(gè)用戶程序(作業(yè)、進(jìn)程)調(diào)入內(nèi)存后,

占用其中一個(gè)分區(qū)，程序運(yùn)行完成后釋放該分區(qū)。

(2)動(dòng)態(tài)分區(qū)

系統(tǒng)生成后，操作系統(tǒng)占用內(nèi)存的一部分，剩下的部分作為一個(gè)空閑區(qū)，當(dāng)一個(gè)用戶程序(作

業(yè)、進(jìn)程)調(diào)入內(nèi)存時(shí)，把這個(gè)空閑區(qū)的低地址部分的區(qū)域分配給它，當(dāng)有作業(yè)完成后釋放所

占用的存儲(chǔ)區(qū)。在系統(tǒng)運(yùn)行的過程中，系統(tǒng)中形成多個(gè)空閑的不連續(xù)的存儲(chǔ)區(qū)，稱主空閑。

分區(qū)的分配及回收

(1)固定分區(qū)時(shí)的分配和回收

當(dāng)用戶程序要裝入執(zhí)行時(shí)，通過請(qǐng)求表提出內(nèi)存分配要求和所要求的內(nèi)存空間大小。存儲(chǔ)管理

程序根據(jù)請(qǐng)求表查詢分區(qū)說明表，從中找出一個(gè)滿足要求的空閑分區(qū)，并將其分配給申請(qǐng)者。

當(dāng)進(jìn)程執(zhí)行完畢，不再需要內(nèi)存資源時(shí)，管理程序?qū)?duì)應(yīng)的分區(qū)狀態(tài)置為未使用即可。

(2)動(dòng)態(tài)分區(qū)時(shí)的分配和回收

動(dòng)態(tài)分區(qū)時(shí)的分配及回收主要解決三個(gè)問題：分配空閑區(qū)、更新可用表、合并空閑區(qū)

動(dòng)態(tài)分區(qū)時(shí)的分配方法從可用表或自由鏈中尋找空閑區(qū)的方法：首次適應(yīng)算法、最佳適應(yīng)算法、

最壞適應(yīng)算法

①首次適應(yīng)算法

首次適應(yīng)算法的表是按空閑區(qū)首址升序的(即空閑區(qū)表是按空閑區(qū)首址從小到大)方法組織的。

分配時(shí)從表首開始，以請(qǐng)求內(nèi)存區(qū)的大小逐個(gè)及空閑區(qū)進(jìn)行比較，找到第一個(gè)滿足要求的空閑

后，若空閑區(qū)大小及請(qǐng)求區(qū)的大小相等，則將該空閑區(qū)分配給請(qǐng)求者，并撤消該空閑區(qū)所在表

目；若大于請(qǐng)求區(qū)，就將該空閑區(qū)的一部分分配給請(qǐng)求者，然后，修改空閑區(qū)的大小和首址。

②最佳適應(yīng)算法

最佳適應(yīng)算法是將申請(qǐng)者放入及其大小最接近的空閑區(qū)中。切割后的空閑區(qū)最小，若系統(tǒng)中有

及申請(qǐng)區(qū)大小相等的空閑區(qū)，這種算法肯定能將這種空閑區(qū)分配給申請(qǐng)者。(首次適應(yīng)法則不一

定)這種算法最大的缺點(diǎn)是分割后的空閑區(qū)將會(huì)很小，直至無法使用，而造成浪費(fèi)。

③最壞適應(yīng)算法

為了克服最佳適應(yīng)算法把空閑區(qū)切割得大小的缺點(diǎn)，人們提出了一種最壞適應(yīng)算法，即每次分

配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，其依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割了

一部分后可能仍是一個(gè)較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。

(3)動(dòng)態(tài)分區(qū)的分配及回收

分配算法中切割空閑區(qū)是從低地址開始的，剩下的部分仍作為一個(gè)空閑區(qū)，門限值是切割空閑

區(qū)后剩下的區(qū)域若小于門限值，就不切割該空閑區(qū)，統(tǒng)統(tǒng)分給申請(qǐng)者。

這三種放置算法的優(yōu)劣很難區(qū)分，要具體情況具體分析。

例如：某時(shí)刻系統(tǒng)中有三個(gè)空閑區(qū)，其大小和首址為：(35KB,100KB)>(12KB,156KB)>(28KB,

200KB)o有一作業(yè)系列：(J0B1,12KB)、(J0B2,30KB)、(J0B3,28KB)

〈單位：KB>〈單位：KB>

大小苜址大小首址

351OO23

1215612156不能繼續(xù)迸合?分配

2820028200

OO

joHl

《單位，KB>（單位：KB〉

天小首址大:小首址

1215628200

28200351OO

351OOO

O

也住適應(yīng)算法jot*1

〈單位：KB>〈單位：KB>

大小苜址大小首址

3b1OU23112

2820028200不能繼續(xù)迸行分配

1215612156

OO

霞杯適及算法jol?L

從搜索速度上看，最先適應(yīng)算法具有最佳性能。從回收過程來看，最先適應(yīng)算法也是最佳的。

最先適應(yīng)法盡可能地利用了地地址空間，從而保證高地址有較大的空閑區(qū)來放置要求內(nèi)存較多

的作業(yè)或進(jìn)程。

最佳適應(yīng)法找到的空閑區(qū)是最佳的，最壞適應(yīng)法是基于不留下碎片空閑區(qū)這一點(diǎn)出發(fā)的，它選

擇最大的空閑區(qū)來滿足用戶的需求，以期分配后的剩余部分仍能進(jìn)行再分配。

分區(qū)存儲(chǔ)管理的優(yōu)缺點(diǎn)：

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

（1）實(shí)現(xiàn)了多個(gè)作業(yè)或進(jìn)程對(duì)內(nèi)存的共享，有助于多道程序設(shè)計(jì)，從而提高了系統(tǒng)的資源利

用率

該方法要求的硬件支持少，管理算法簡單，因而容易實(shí)現(xiàn)

缺點(diǎn)：

（1）內(nèi)存利用率仍然不高

（2）作業(yè)或進(jìn)程的大小受分區(qū)大小控制，除非配合采用覆蓋技術(shù)和交換技術(shù)

（3）無法實(shí)現(xiàn)各分區(qū)之間的信息共享

覆蓋及交換技術(shù)

7.覆蓋及交換技術(shù)是在多道環(huán)境下用來擴(kuò)充內(nèi)存的兩種方法。

覆蓋技術(shù)要求程序員提供一個(gè)清楚地覆蓋結(jié)構(gòu)。即程序員必須完成把一個(gè)程序劃分成不同的程

序段，并規(guī)定好它們的執(zhí)行和覆蓋順序的工作。操作系統(tǒng)根據(jù)程序員提供的覆蓋結(jié)構(gòu)來完成程

序段之間的覆蓋。

交換技術(shù)是指先將內(nèi)存某部分的程序或數(shù)據(jù)寫入外存交換區(qū)，再從外存交換區(qū)中調(diào)入指定的程

序或數(shù)