2023年計算機操作系統(tǒng)面試知識點_第1頁
2023年計算機操作系統(tǒng)面試知識點_第2頁
2023年計算機操作系統(tǒng)面試知識點_第3頁
2023年計算機操作系統(tǒng)面試知識點_第4頁
2023年計算機操作系統(tǒng)面試知識點_第5頁
已閱讀5頁,還剩40頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

第一章

★1.操作系統(tǒng)的概念:通常把操作系統(tǒng)定義為用以控制和管理計算機系統(tǒng)資源方便用戶使

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

★2.操作系統(tǒng)的基本類型:批解決操作系統(tǒng)、分時操作系統(tǒng)、實時操作系統(tǒng)、個人計算機

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

①批解決操作系統(tǒng)

特點:

用戶脫機使用計算機

成批解決

多道程序運營

優(yōu)點:

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

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

缺陷:

無交互性,用戶一旦提交作業(yè)就失去了對其運營的控制能力;并且是批解決的,作業(yè)周

轉(zhuǎn)時間長,用戶使用不方便。

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

②分時操作系統(tǒng)(TimeSharingOS)

分時操作系統(tǒng)是一個聯(lián)機的多用戶交互式的操作系統(tǒng),如UNIX是多用戶分時操作系統(tǒng)。

分時計算機系統(tǒng):由于中斷技術(shù)的使用,使得一臺計算機能連接多個用戶終端,用戶可

通過各自的終端使用和控制計算機,我們把一臺計算機連接多個終端的計算機系統(tǒng)稱為

分時計算機系統(tǒng),或稱分時系統(tǒng)。

分時技術(shù):把解決機的響應(yīng)時間提成若于個大小相等(或不相等)的時間單位,稱為時

間片(如100毫秒),每個終端用戶獲得CPU,就等于獲得一個時間片,該用戶程序開始

運營,當(dāng)時間片到(用完),用戶程序暫停運營,等待下一次運營。

特點:

人機交互性好:在調(diào)試和運營程序時由用戶自己操作。

共享主機:多個用戶同時使用。

用戶獨立性:對每個用戶而言好象獨占主機。

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

實時操作系統(tǒng)是一種聯(lián)機的操作系統(tǒng),對外部的請求,實時操作系統(tǒng)可以在規(guī)定的時間

內(nèi)解決完畢。

特點:

有限等待時間

有限響應(yīng)時間

用戶控制

可靠性高

系統(tǒng)犯錯解決能力強

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

(1)實時時鐘管理

(2)連續(xù)的人一機對話

(3)過載

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

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

同時兼有多道批解決、分時、實時解決的功能,或其中兩種以上的功能。

⑤個人計算機上的操作系統(tǒng)

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

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

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

特性:

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

(2)這些計算機是自治的,每臺計算機有自己的操作系統(tǒng),各自獨立工作,它們在網(wǎng)絡(luò)

協(xié)議控制下協(xié)同工作。

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

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

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

特性:

(1)功能的分布

(2)堅強性

(3)高可靠性

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

解決機管理、存儲管理(內(nèi)存分派、存儲保護、內(nèi)存擴充)、設(shè)備管理(通道、控制器、

輸入輸出設(shè)備的分派與管理,設(shè)備獨立性)、信息管理(文獻系統(tǒng)管理)、用戶接口(程

序一級的接口、作業(yè)一級的接口)。

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

通道:用于控制I/O設(shè)備與內(nèi)存間的數(shù)據(jù)傳輸。啟動后可獨立于CPU運營,實現(xiàn)CPU與

I/O的并行。

O通道有專用的I/O解決器,可與CPU并行工作

O可實現(xiàn)I/O聯(lián)機解決

中斷是指CPU在收到外部中斷信號后,停止本來工作,轉(zhuǎn)去解決該中斷事件,完畢后回

到本來斷點繼續(xù)工作。

o中斷解決過程:中斷請求,中斷響應(yīng),中斷點(暫停當(dāng)前任務(wù)并保存現(xiàn)場),

中斷解決例程,中斷返回(恢復(fù)中斷點的現(xiàn)場并繼續(xù)原有任務(wù)

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

★5.多道批解決系統(tǒng)

特點

O多道:內(nèi)存中同時存放幾個作業(yè);

O宏觀上并行運營:都處在運營狀態(tài),但都未運營完;

。微觀上串行運營:各作業(yè)交替使用CPU;

優(yōu)點:

O資源運用率高:CPU和內(nèi)存運用率較高;

。作業(yè)吞吐量大:單位時間內(nèi)完畢的工作總量大;

缺陷:

o用戶交互性差:整個作業(yè)完畢后或中間犯錯時,才與用戶交互,不利于調(diào)試

和修改;

o作業(yè)平均周轉(zhuǎn)時間長:短作業(yè)的周轉(zhuǎn)時間顯著增長;

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

6.計算機硬件:

構(gòu)成計算機的基本硬件元素:解決器、存儲器、輸入輸出控制與總線、外部設(shè)備。

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

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

■地址寄存器

■條件碼寄存器

■程序計數(shù)器

■指令計數(shù)器

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

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

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

存儲器的訪問速度

大小

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

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

啟動電源——產(chǎn)生中斷信號——觸發(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)“條件”未被滿足時反復(fù)所描述的“操作”

while條件do操作....od當(dāng)“條件”滿足時,進行相應(yīng)的“操作”

if條件then操作else操作fi滿足“if”所指的“條件”時,進行“then”后的相

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

第二章

★1.作業(yè):在一次應(yīng)用業(yè)務(wù)解決過程中,從輸入開始到輸出結(jié)束,用戶規(guī)定計算機所做的

有關(guān)該次業(yè)務(wù)解決的所有工作稱為一個作業(yè)。

作業(yè)由不同的順序相連的作業(yè)步組成,作業(yè)步是一個作業(yè)的解決過程中計算機所做的相

對獨立的工作。

2.作業(yè)的組織:

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

規(guī)定的業(yè)務(wù)解決工作,作業(yè)說明書則體現(xiàn)用戶的控制意圖。

★由作業(yè)說明書在系統(tǒng)中生成一個稱為作業(yè)控制塊(JCB)的表格,JCB涉及:作業(yè)名、

估計執(zhí)行時間、優(yōu)先數(shù)(用于調(diào)度)、作業(yè)說明書文獻名、程序類型、資源規(guī)定(靜態(tài)申請

和動態(tài)申請)、作業(yè)狀態(tài)(提交后各執(zhí)行完畢)。

作業(yè)說明書涉及:作業(yè)基本情況描述(用戶名、作業(yè)名、使用語言名、允許最大解決時

間等)、作業(yè)控制描述(控制方式、操作順序、犯錯解決等)、作業(yè)資源規(guī)定描述(規(guī)定

解決時間、內(nèi)存空間、外設(shè)類型和數(shù)量、解決及優(yōu)先級、庫函數(shù)或?qū)嵱贸绦虻龋?/p>

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

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

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

在聯(lián)機輸入輸出方式中,外圍設(shè)備直接與主機相連接。

②脫機輸入輸出方式

脫機輸入又稱為預(yù)輸入方式,運用低檔個人計算機作為外圍解決機進行輸入輸出解決。

③直接耦合方式

把主機與低檔外圍通過一個公用的大容量外存直接耦合起來。

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

多臺外圍設(shè)備通過通道或DMA器件和主機與外存連接起來。

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

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

對計算機網(wǎng)絡(luò)中的另一臺主機進行輸入輸出操作時,就構(gòu)成了網(wǎng)絡(luò)聯(lián)機方式。

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

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

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

(2)文獻管理:涉及對文獻的讀、寫、創(chuàng)建和刪除等。

(3)進程控制:涉及進程創(chuàng)建、進程執(zhí)行、進程撤消、進程等待和執(zhí)行優(yōu)先級控制等。

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

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

(6)線程管理:涉及線程的創(chuàng)建、調(diào)度、執(zhí)行、撤消等。

系統(tǒng)調(diào)用的實現(xiàn):當(dāng)用戶使用系統(tǒng)調(diào)用時一,產(chǎn)生一條相應(yīng)的指令,解決機在執(zhí)行到該指

令時發(fā)生相應(yīng)的中斷,并發(fā)出有關(guān)信號給該解決機制。該解決機制在收到了解決機發(fā)來

的信號后,啟動相關(guān)的解決程序去完畢該系統(tǒng)調(diào)用所規(guī)定的功能。

陷進解決機構(gòu):在系統(tǒng)中為控制系統(tǒng)調(diào)用服務(wù)的機構(gòu)稱為陷進解決機構(gòu)。

陷進指令:把由于系統(tǒng)調(diào)用引起解決機中斷的指令稱為陷進指令。

第二早

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

程序用來描述計算機所完畢的獨立功能,并在時間上嚴(yán)格地按前后順序相繼地進行計算

機操作序列集合,是一個靜態(tài)概念。

個程序由若干個程序段組成,而這些程序段的執(zhí)行必須是順序的,這種程序執(zhí)行的方式

就稱為程序的順序執(zhí)行。

程序順序執(zhí)行的特點:

■1.順序性

解決機嚴(yán)格按照程序所規(guī)定的順序執(zhí)行,即每個操作必須在下一個操作開始之前結(jié)

束。

■2.封閉性

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

后的狀態(tài)只能由程序自身擬定,即只有本程序才干改變它。

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

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

它的執(zhí)行結(jié)果是相同的,不管它在什么時間執(zhí)行,也不管計算機的運營速度。

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

執(zhí)行環(huán)境的特點:

■(1)獨立性

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

■(2)隨機性

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

■(3)資源共享

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

程序并發(fā)執(zhí)行:若干個程序段同時在系統(tǒng)中運營,這些程序的執(zhí)行在時間上是重迭的,

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

也稱這幾個程序段是并發(fā)執(zhí)行的。

2.★.進程:進程是一個程序?qū)δ硞€數(shù)據(jù)集的執(zhí)行過程,是分派資源的基本單位。

進程和程序的區(qū)別與聯(lián)系:

①程序是指令的集合,是靜態(tài)的概念。進程是程序在解決機上的一次執(zhí)行的過程,是動

態(tài)的概念。程序可以作為軟件資料長期保存。進程是有生命周期的。

②進程是一個獨立的運營單位,能與其它進程并行(并發(fā))活動。而程序則不是。

③進程是競爭計算機系統(tǒng)有限資源的基本單位,也是進行解決機調(diào)度的基本單位。

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

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

作業(yè)是用戶需要計算機完畢某項任務(wù)時規(guī)定計算機所做工作的集合。而進程則是已提交

完畢程序的執(zhí)行過程的描述,是資源分派的基本單位。

其重要區(qū)別如下:

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

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

■作業(yè)的概念重要用于批解決系統(tǒng)中。

進程描述

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

①進程控制塊PCB(ProcessControlBlock)

包含一個進程的描述信息、控制信息及資源信息,有些系統(tǒng)尚有進程調(diào)度等待所使用的

現(xiàn)場保護區(qū)。PCB集中反映一個進程的動態(tài)特性。在創(chuàng)建時,建立PCB,并隨著進程運

營的全過程,當(dāng)進程完畢其功能后,系統(tǒng)釋放PCB,進程也隨之消亡

(1)描述信息

1、進程名或進程標(biāo)記號name

每個進程都必須有一個唯一的標(biāo)記符,可以是字符串,也可以是一個數(shù)字。UNIX系統(tǒng)

中就是一個整型數(shù)。在進程創(chuàng)建時由系統(tǒng)賦予。

2、用戶名或用戶標(biāo)記號

每個進程都從屬于某個用戶,用戶名或用戶標(biāo)記號有助于資源共享和保護

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

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

一個家族之中,就需要記錄進程在家族中位置的信息。

(2)控制信息

1、進程當(dāng)前狀態(tài)status

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

為了管理的方便,系統(tǒng)設(shè)計時會將相同的狀態(tài)的進程組成一個隊列,如就緒進程隊列,

等待進程則要根據(jù)等待的事件組成多個等待隊列,如等待打印機隊列、等待磁盤I/O完畢

隊列等等。

2、進程優(yōu)先級priority

進程的優(yōu)先級反映進程的緊迫限度,通常由用戶指定和系統(tǒng)設(shè)立。

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

4、各種計時信息

進程占用系統(tǒng)資源的情況,不同的系統(tǒng)的解決差別很大。

5、通信信息communicationinformation

是指某個進程在運營的過程中要與其它進程進行通信,該區(qū)記錄有關(guān)進程通信方面的信

息、O

(3)資源管理信息

涉及有關(guān)存儲器的信息、、使用輸入、輸出設(shè)備的信息、有關(guān)文獻系統(tǒng)的信息:

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

2、在某些復(fù)雜系統(tǒng)中,尚有對換或覆蓋用的有關(guān)信息。

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

4、輸入輸出設(shè)備的設(shè)備號,所要傳送的數(shù)據(jù)長度、緩沖區(qū)地址、緩沖區(qū)長度及使用設(shè)備

的有關(guān)數(shù)據(jù)結(jié)構(gòu)指針等。

5、指向文獻系統(tǒng)的指針及有關(guān)標(biāo)記等。

(4)、CPU現(xiàn)場保護區(qū)cpustatus

當(dāng)進程因某種因素不能繼續(xù)占用CPU時(等待打印機),釋放CPU,這時就要將CPU的

各種狀態(tài)信息保護起來,為將來再次得到解決機恢復(fù)CPU的各種狀態(tài),繼續(xù)運營。

②進程上下文事實上是進程執(zhí)行活動全過程的靜態(tài)描述。

進程上下文是一個抽象的概念,它包含了每個進程執(zhí)行過的、執(zhí)行時的以及待執(zhí)行的指

令和數(shù)據(jù),在指令寄存器、堆棧(存放個調(diào)用子程序的返回點和參數(shù)等),狀態(tài)字寄存器

等中的內(nèi)容。

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

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

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

③進程上下文切換

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

為保存被切換進程的正文部分(或當(dāng)前狀態(tài))至有關(guān)存儲區(qū)。第二部分操作系統(tǒng)進程中

有關(guān)調(diào)度和資源分派程序執(zhí)行,并選取新的進程。第三部分則是將被選中進程的本來被

保存的正文部分從有關(guān)存儲區(qū)中選出,并送至有關(guān)寄存器或堆棧中,激活被選中進程執(zhí)

行。

I進程?執(zhí)行

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

保存進程修正文至PCB,

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

選取新進程22,恢復(fù)片上下文

.新進程&執(zhí)行

④進程空間和大小

任一進程都有自己的地址空間,把該空間稱為進程空間或虛空間。進程空間的大小只與

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

等都按一定的結(jié)構(gòu)排列在進程空間中。

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

為了防止用戶程序訪問系統(tǒng)空間,導(dǎo)致訪問犯錯,計算機通過程序狀態(tài)寄存器等設(shè)立不

同的執(zhí)行模式,即用戶模式(用戶態(tài))和系統(tǒng)模式(系統(tǒng)態(tài))來進行保護。

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

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

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

存在于解決機調(diào)度隊列中的那些進程,它們已經(jīng)準(zhǔn)備就緒,一旦得到CPU,就立即可以

運營,這些進程所取的狀態(tài)為就緒狀態(tài)。(有多個進程處在此狀態(tài))

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

當(dāng)進程由調(diào)度/分派程序分派后,得到CPU控制權(quán),它的程序正在運營,該進程所處的狀

態(tài)為執(zhí)行狀態(tài)。(在系統(tǒng)中,總只有一個進程處在此狀態(tài))

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

若一個進程正在等待某個事件的發(fā)生(如等待I/O的完畢),而暫停執(zhí)行,這時,即使給

它CPU時間,它也無法執(zhí)行,則稱該進程處在等待狀態(tài)。

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

運營到等待等待某事件的發(fā)生(如等待I/O完畢)

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

運營到就緒時間片到(例如,兩節(jié)課時間到,下課)

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

就緒到運營當(dāng)解決機空閉時,由調(diào)度(分派)程序從就緒進程隊列中選擇一個進程占

用CPUo

進程控制:就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進程以及完畢進程各

狀態(tài)的轉(zhuǎn)換,從而達成多進程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實現(xiàn)資源共享的目的。

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

用于進程控制的原語有:創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語。

進程創(chuàng)建方式:由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建;由父進程創(chuàng)建。進程創(chuàng)建系統(tǒng)調(diào)用:

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

進程撤消:(1)該進程已完畢所規(guī)定的功能而正常終止(2)由于某種錯誤導(dǎo)致非正常終

止(3)祖先進程規(guī)定撤消某個子進程。在一般操作系統(tǒng)中進程撤消的系統(tǒng)調(diào)用是:kill

UNIX系統(tǒng)中是exit()假如撤消進程有自己的子進程,則撤消原語先撤消其子進程的PCB

結(jié)構(gòu)并釋放子進程所釋放的資源后,再撤消當(dāng)前進程的PCB結(jié)構(gòu)和釋放其資源。

進程的阻塞與喚醒

當(dāng)一個處在運營狀態(tài)的進程,因等待某個事件的發(fā)生(如等待打印機)而不能繼續(xù)運營

時,將調(diào)用進程掛起系統(tǒng)調(diào)用,把進程的狀態(tài)置為阻塞狀態(tài),并調(diào)用進程調(diào)度程序(等

于讓出解決機)。

進程從運營狀態(tài)轉(zhuǎn)換成阻塞狀態(tài)是由進程掛起原語實現(xiàn)的,因此,調(diào)用進程掛起操作是

在進程處在運營狀態(tài)下執(zhí)行的。它的執(zhí)行將引起等待某事件的隊列的改變.

一個正在運營的進程會因等待某事件(例如,等待打印機)的發(fā)生,由運營狀態(tài)轉(zhuǎn)換成

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

由進程喚醒操作完畢。

喚醒一個進程有兩種方式:系統(tǒng)進程喚醒、事件發(fā)生進程喚醒。

調(diào)用進程喚醒操作一般在中斷解決、進程通信等過程中。例如,打印機完畢中斷解決程

序,在完畢了打印完畢的操作后,就去檢查等待打印機的隊列,若不為空,則調(diào)用進

程喚醒操作,喚醒一個(或多個)等待打印機的進程。

4.進程互斥

產(chǎn)生互斥的因素:資源共享、進程合作

★臨界資源:一次僅允許一個進程使用的資源稱為臨界資源。

★臨界區(qū):每個進程中訪問臨界資源的那段程序段稱為臨界區(qū)(臨界段)。

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

為有共享公有資源而導(dǎo)致的對并發(fā)進程執(zhí)行速度的間接制約,簡稱間接制約。

★互斥:在操作系統(tǒng)中,當(dāng)某一進程正在訪問某臨界區(qū)時,就不允許其它進程進入,否

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

進入臨界區(qū)的準(zhǔn)則:

(1)不能假設(shè)各并發(fā)進程的相對執(zhí)行速度;

(2)并發(fā)進程中的某個進程不在臨界區(qū)時,它不能阻止其他進程進入臨界區(qū);

(3)并發(fā)進程中的若干個進程申請進入界區(qū)時,只能允許一個進程進入;

(4)當(dāng)有若干個進程欲進入臨界區(qū)時,應(yīng)在有限的時間內(nèi)使其進入。

解決進程互斥的最簡樸的辦法是加鎖。

在系統(tǒng)中為每個臨界資源設(shè)立一個鎖位,

■1表達資源可用,

■0表達資源已被占用(不可用)。

這樣當(dāng)一個進程使用某個臨界資源之前必須完畢下列操作:

1、考察鎖位的值;

2、若本來的值是為“1”,將鎖位置為“0”(占用該資源);

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

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

5.信號量與P、V原語

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

數(shù),但sem小于零時則表達正在等待使用臨界區(qū)的進程數(shù)。sem代表資源的實體。在實

際應(yīng)用中應(yīng)準(zhǔn)確地說明sem的意義和初值。

★P操作:

(1)sem減1;

(2)若sem減1后仍大于等于0,則進程繼續(xù)執(zhí)行;

(3)若結(jié)果小于0,則該進程掛起。

注:掛起該進程涉及:保存調(diào)用進程CPU現(xiàn)場;置“等待”狀態(tài);入等待隊列;轉(zhuǎn)進程調(diào)

度;

算法:v

輸入:s

輸出:無

(

S++;

if(s<=0)

喚醒等待S的進程:

)

V操作:

(1)s值力口1;

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

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

度。

算法:V

輸入:s

輸出:無

{

S-H-;

if(s<=0)

喚醒等待S的進程;

)

當(dāng)一個進程想要進入臨界區(qū)時,它必須先執(zhí)行P原語操作以將信號量sem減1。在一個進

程完畢對臨界資源的操作后,它必須執(zhí)行V原語操作以釋放它占用的臨界資源。由于信

號量初始值為1,所以,任一進程在執(zhí)行P原語操作之后將sem的值變?yōu)?,表達該進程

可以進入臨界區(qū)。在該進程未執(zhí)行V原語操作之前如有另一進程想進入臨界區(qū)的話,它

也應(yīng)先執(zhí)行P原語操作,從而使sem的值變?yōu)?1,因此,第二個進程將會被阻塞,直到

第一個進程執(zhí)行V原語操作之后,sem的值變?yōu)?,從而可喚醒第二個進程進入就緒隊列,

經(jīng)調(diào)度后進入臨界區(qū)。在第二個進程執(zhí)行完V原語操作之后,假如沒有其它進程申請進

入臨界區(qū)的話,則sem又恢復(fù)到初始值。

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

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

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

入類名為S的臨界區(qū),sem=-l表達進程Pa,Pb中,一個進程已進入臨界區(qū),而另一進程

等待進入臨界區(qū)。

(2)描述

Pa:

P(sem)

<S>

V(sem):

Pb:

P(sem)

<S>

V(sem)::

nainO兩個進程并發(fā)掘Mpmt值1、0、?1.

{?print=l>表澈有牌使用確機;

intprint=l;^pnnt=0,表示有一個進程正在使用打印機;

cobegin?print=-l,表示有一進程正在使用打卬機,

pa();還有一個進程等械用橢機

pb();

pa()pbO

({

P(print);QCpr*int);

使用打印機;使用打印機;

VCr>2rint);

v(print);

}

)

6.進程同步

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

互相等待,使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步。

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

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

用signal(消息名)表達向合作進程發(fā)送消息

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

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

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

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

(3)描述:

Pc:

A:wait(Bufempty)

計算

氤計算結(jié)果

V--

Bufemptyfalse

signal(Buffull)

GotoA

Pp:

B:wait(Bufful)

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

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

Bu^fulfalse

signal(Bufempty)

GotoB

★私有信號量(privateSemaphore):進程同步的信號量只與制約進程及被制約進程有關(guān)

而不是與整組并發(fā)進程有關(guān)。因此該信號量稱為私有信號量。

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

一方面,為各并發(fā)進程設(shè)立私有信號量,

然后,為私有信號量賦初值,

最后,運用P,V原語和私有信號量規(guī)定各進程的執(zhí)行順序。

例:設(shè)進程Pa和Pb通過緩沖區(qū)隊列傳遞數(shù)據(jù)。Pa為發(fā)送進程,Pb為接受進程。Pa發(fā)送

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

和接受過程滿足如下條件:

毛白~~—Bufl—―Buf2——…一一Bufz——Bufn—―

(1)在

PA:deposit(data):

beginlocalx

P(Bufempty);

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

Buf(x)―dat

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

V(Buflbll)

end

PB:remove(data):

Beginlocalx

P(Buffull);

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

data4—Buf(%)

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

V(Bufempty)

End

★7.生產(chǎn)者與消費者問題

對于生產(chǎn)者進程:產(chǎn)生一個數(shù)據(jù),當(dāng)要送入緩沖區(qū)時,要檢查緩沖區(qū)是否已滿,若未滿,

則可將數(shù)據(jù)送入緩沖區(qū),并告知消費者進程;否則,等待;

對于消費者進程:當(dāng)它去取數(shù)據(jù)時,要看緩沖區(qū)中是否有數(shù)據(jù)可取,若有則取走一個數(shù)

據(jù),并告知生產(chǎn)者進程,否則,等待。

這種互相等待,并互通信息就是典型的進程同步。

同時,緩沖區(qū)是個臨界資源,因此,諸進程對緩沖區(qū)的操作程序是一個共享臨界區(qū),因

此,尚有個互斥的問題。

deposit(data):

begin

P(avail)

P(mutex)

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

V(ftill)

V(mutex)

end

remove(data):

begin

P(ftill)

P(mutex)

取緩沖區(qū)中某單元數(shù)據(jù)

V(avail)

V(mutex)

End

full:緩沖區(qū)產(chǎn)品數(shù)目,初值為0;einpty:緩沖區(qū)可存放產(chǎn)品的空位,初值為n;

routex:對緩沖區(qū)互斥信號燈,初值為1;

producer()consumer()

{(

while(生產(chǎn)未完成)while(還要繼續(xù)消費)

{(

?■?P(full);

生產(chǎn)一個產(chǎn)品;p(mutex);

P(empty),從緩沖區(qū)中取出一個產(chǎn)品;

p(mutex);v(mutex);

將產(chǎn)品放入緩沖區(qū);V(empty);

v(mutex);消費一個產(chǎn)品;

????

V(full);9

))

))

8.進程通信

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

這些進程都具有各自獨立的功能,且大多數(shù)都被外部需要而啟動執(zhí)行。

在單機系統(tǒng)中進程的通信有4種形式:

(1)主從式

(2)會話式

(3)消息或郵箱機制

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

會話方式的特點:

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

(2)服務(wù)進程根據(jù)使用進程的規(guī)定提供服務(wù),但對所提供服務(wù)的控制由服務(wù)進程自身完畢。

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

消息或郵箱機制的特點是:

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

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

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

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

送進程和接受進程之間沒有時間上的限制。

共享存儲區(qū)方式不規(guī)定數(shù)據(jù)移動,兩個需要互相互換信息的進程通過共享數(shù)據(jù)區(qū)的操作

達成互相通信的目的。

9.死鎖問題

死鎖:指個并發(fā)進程彼此互相等待對方所擁有的資源,且這些并發(fā)進程在得到對方的資

源之前不會釋放自己所擁有的資源。從而導(dǎo)致大家都想得到資源而又得不到資源,個并

發(fā)進程不能繼續(xù)向前推動的狀態(tài)。

★死鎖的起因:主線因素在于系統(tǒng)提供的資源個數(shù)少于并發(fā)進程所規(guī)定的該類資源數(shù)。

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

(1)互斥條件。并發(fā)進程所規(guī)定和占有的資源是不能同時被兩個以上進程使用或操作的,

進程對他所需要的資源進行排他性控制。

(2)不剝奪條件。進程所獲得的資源在未使用完畢之前,不能被其它進程強行剝奪,而

只能由獲得該資源的進程自己釋放。

(3)部分分派。進程每次申請它所需要的一部分資源,在等待新資源的同時,繼續(xù)占用

已分派的資源。

(4)環(huán)路等待條件。存在一種進程循環(huán)鏈,鏈中每一個進程已獲得的資源同時被下一個

進程所請求。

只要有一個條件不滿足,死鎖就可解除。

防止死鎖

1.破壞”請求與保持條件”每個進程在運營之前,必須預(yù)先提出自己所要使用的所有資源,

調(diào)度程序在該進程所需要的資源末得到滿足之前,不讓它們投入運營,并且當(dāng)資源一旦

分派給某個進程之后,那么在該進程的整個運營期間相應(yīng)資源一直被它占有,這就破壞

了產(chǎn)生死鎖的部分分派條件。

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

并賦予不同的序號。

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

的信息控制資源分派,使得共同進展途徑的下一步不致于進入危險區(qū),即只要有產(chǎn)生死

鎖的也許性,就避免把一種資源分派給一個進程。

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

1.資源剝奪法

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

(2)建立檢查點重要是用來恢復(fù)分派前的狀態(tài)。

2.撤消進程法

按一定的順序中止進程序列,直至已釋放到有足夠的資源來完畢剩下的資源為止。

第四章

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

完畢四個狀態(tài)。

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

作業(yè),因其信息尚未所有進入系統(tǒng),所以不能被調(diào)用程序選取。

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

入井,即專門用來存放待解決作業(yè)信息的一組外存分區(qū))。若一個作業(yè)的所有信息已所有

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

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

分派必要的資源,這時,這些被選中的作業(yè)處在執(zhí)行狀態(tài)。

當(dāng)作業(yè)運營完畢,但它所占用的資源尚未所有被系統(tǒng)收回時,該作業(yè)處在完畢狀態(tài)。

一般來說,解決機調(diào)度可分為4級:作業(yè)調(diào)度、互換調(diào)度、進程調(diào)度、線程調(diào)度。

作業(yè)調(diào)度:又稱宏觀調(diào)度或高級調(diào)度,其重要任務(wù)是按一定的原則對外存輸入井上的大

量后備作業(yè)進行選擇,給選出的作業(yè)分派內(nèi)存、輸入輸出設(shè)備等必要的資源,并建立相

應(yīng)的根程序,以使該作業(yè)的進程獲得競爭解決機的權(quán)利,此外,當(dāng)該作業(yè)執(zhí)行完畢時,

還負責(zé)回收系統(tǒng)資源。

互換調(diào)度:又稱中級調(diào)度,其重要任務(wù)是按照給定的原則和策略,將處在外存互換區(qū)中

的就緒狀態(tài)或就緒等待狀態(tài)的進程調(diào)入內(nèi)存,或把處在內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的

進程互換到外存互換區(qū)。互換調(diào)度重要涉及內(nèi)存的管理和擴充,一般將它歸在存儲管理

之中。

進程調(diào)度:又稱微觀調(diào)度或低檔調(diào)度,其重要任務(wù)是按照某種策略和方法選取一個處在

就緒狀態(tài)的進程占用解決機。

只有在多道批解決系統(tǒng)中才有作業(yè)調(diào)度,而在分時和實時系統(tǒng)中一般只有進程調(diào)度、互

換調(diào)度和線程調(diào)度。

這是由于在分時和實時系統(tǒng)中,為了縮短響應(yīng)時間或為了滿足用戶需求的截止時間,作

業(yè)不是建立在外存中,而是直接建立在內(nèi)存中。

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

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

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

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

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

隨作業(yè)的撤消而被清除。

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

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

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

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

(1)對所有作業(yè)應(yīng)當(dāng)是公平合理的。

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

(3)天天執(zhí)行盡也許多的作業(yè)

(4)有快的響應(yīng)時間

對于批解決系統(tǒng),作業(yè)的平均周轉(zhuǎn)時間或平均帶權(quán)周轉(zhuǎn)時間,被作為衡量調(diào)度算法優(yōu)劣

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

★(1)周轉(zhuǎn)時間:

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

Tei為作業(yè)i的完畢時間,Tsi為作業(yè)的提交時間

一個作業(yè)的周轉(zhuǎn)時間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時間,包含兩部分:一是等待時間;二

為執(zhí)行時間

Ti=Twi+Tri

Twi重要是指作業(yè)i由后備狀態(tài)到執(zhí)行狀態(tài)的等待時間,它不涉及作業(yè)進入執(zhí)行狀態(tài)后的

等待時間。

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

n

T==l/n£Ti

i=l

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

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

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

n

W=l/nXWi

i=l

3.進程調(diào)度

進程調(diào)度的功能:

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

②按照一定的調(diào)度算法,選擇一個處在就緒狀態(tài)的進程,給它分派解決機(這是最重要的

功能)

③實行進行進程上下文的切換

引起進程調(diào)度的因素:

(1)正在執(zhí)行的進程執(zhí)行完畢。這時,假如不選擇新的就緒進程執(zhí)行,將浪費解決機資

源。

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

(3)執(zhí)行中進程調(diào)用了P原語操作,從而因資源局限性而被阻塞;或調(diào)用了V原語激活

了等待資源的進程隊列。

(4)執(zhí)行中進程提出了I/O請求后被阻塞。

(5)在分時系統(tǒng)中時間片已經(jīng)用完。

(6)在執(zhí)行完系統(tǒng)調(diào)用,在系統(tǒng)程序返回用戶進程,可認(rèn)為系統(tǒng)進程執(zhí)行完畢,從而可

調(diào)度選擇一新的用戶程序執(zhí)行。

以上都是CPU執(zhí)行不可剝奪方式下做引起的進程調(diào)度的因素,在CPU執(zhí)行方式是可剝奪

時,尚有:

(7)就緒隊列中的某進程的優(yōu)先級變得高于當(dāng)前執(zhí)行進程的優(yōu)先級,從而也將發(fā)生進程

調(diào)度。

可剝奪方式:即就緒隊列中一旦有優(yōu)先級高于當(dāng)前進程優(yōu)先級的進程存在時,便立即發(fā)

生進程調(diào)度,轉(zhuǎn)讓解決機。

非剝奪方式(不可剝奪方式):即使在就緒隊列存在有優(yōu)先級高于當(dāng)前執(zhí)行進程時,當(dāng)前

進程仍將繼續(xù)占有解決機,直到該進程因自己調(diào)度調(diào)用原語操作或、等待I/O進入阻塞狀

態(tài)或時間片用完時才重新發(fā)生調(diào)度讓出解決機。

進程調(diào)度性能評價

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

(2)在大多數(shù)情況下,運用測試或模擬系統(tǒng)響應(yīng)時間的方法來評價進程調(diào)度的性能

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

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

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

的方式進行調(diào)度解決。

優(yōu)點:在一般意義下是公平的,即每個作業(yè)或進程都按照它們在隊列中檔待時間長短來

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

缺陷:對于那些執(zhí)行時間較短的作業(yè)或進程來說,假如它們在某些執(zhí)行時間很長的作業(yè)

或進程之后到達,則它們等待很長時間。

②(時間片)輪轉(zhuǎn)法(RR)

算法描述:就緒隊列按進程到達的時間來排列。解決機的時間被分為固定大小的時間片。

調(diào)度程序總是選擇就緒隊列中的第一個進程。一個執(zhí)行進程假如在用完一個時間片后還

沒有完畢其任務(wù),它就自動釋放解決機回到就緒隊列的末尾重新排隊,等待下一次被調(diào)

度。

缺陷:只能用來分派那些可搶占資源,并且這種算法只能用于進程調(diào)度,不能用于作業(yè)

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

時間片的選取非常重要,時間片長度的選擇會直接影響系統(tǒng)開銷和響應(yīng)時間。假

如時間片長度過短,則調(diào)度程序剝奪解決機的次數(shù)增多,這將使進程上下文互換次數(shù)也

大大增長,加重了系統(tǒng)開銷。假如時間片長度選擇過長(大),大到一個進程足以完畢其所

有運營工作所需的時間,那么時間片輪轉(zhuǎn)法就退化為先來先服務(wù)策略了。最佳的時間片

量值應(yīng)能使分時用戶得到好的響應(yīng)時間。

時間片的擬定

在輪轉(zhuǎn)法中,時間片長度q根據(jù)系統(tǒng)對響應(yīng)時間的規(guī)定R和就緒隊列中所能容納的最大

進程數(shù)Nmax擬定的。q=R/Nmax

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

q,作為新一輪調(diào)度的時間片。

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

(1)在時間片輪轉(zhuǎn)法中設(shè)立三個就緒隊列

a.時間片完畢就緒隊列

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

c.新進程就緒隊列

(2)每個隊列建立時按FCFS排列,同一隊列中進程的優(yōu)先級相同,不同隊列具有不同

的優(yōu)先級

優(yōu)先級高的隊列中進程的時間片短,優(yōu)先級低的隊列中進程的時間片長。

(3)進程調(diào)度時,先調(diào)度高優(yōu)先級就緒隊列中的進程,當(dāng)高優(yōu)先級就緒隊列為空時才調(diào)

度優(yōu)先級低的就緒隊列中的進程

(4)一個進程在執(zhí)行過程中要經(jīng)歷不同的就緒隊列

④優(yōu)先級法

算法描述:按照某種原則給作業(yè)或進程擬定一個優(yōu)先級,進程的就緒隊列或作業(yè)的后備

隊列按對象的優(yōu)先級進行排列,高前低后。對象進入隊列是插入。當(dāng)調(diào)度發(fā)生時,排列

在最前面的進程或作業(yè)被調(diào)度。

擬定優(yōu)先級的方法有兩類:動態(tài)法和靜態(tài)法

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

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

動態(tài)法:把作業(yè)或進程靜態(tài)性和動態(tài)性結(jié)合起來擬定作業(yè)或進程的優(yōu)先級,隨著作業(yè)或

進程的執(zhí)行過程,優(yōu)先級不斷變化。

作業(yè)調(diào)度中靜態(tài)優(yōu)先級擬定原則:

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

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

(3)系統(tǒng)根據(jù)作業(yè)規(guī)定資源情況擬定優(yōu)先級。

進程調(diào)度靜態(tài)優(yōu)先級擬定原則:

(1)按照進程的類型給與不同的優(yōu)先級。

(2)將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進程的優(yōu)先級。

由于在進程調(diào)度中靜態(tài)優(yōu)先級擬定方法的缺陷:系統(tǒng)效率低、調(diào)度性能不高,所以多采

用動態(tài)的方法擬定優(yōu)先級。

進程調(diào)度動態(tài)優(yōu)先級擬定原則:

(1)根據(jù)進程占有CPU時間的長短來決定。一個進程占有解決機時間越長,則在被阻

塞后再次獲得調(diào)度的優(yōu)先級越低,反之,獲得調(diào)度的也許性越大

(2)根據(jù)就緒進程等待CPU的時間長短來決定。一個就緒進程在就緒隊列中檔待的時

間越長,則它獲得調(diào)度選中的優(yōu)先級就越高。

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

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

優(yōu)點:可使得系統(tǒng)在同一時間內(nèi)解決的作業(yè)個數(shù)最多,從而吞吐量也就大于其他調(diào)度方

式。

缺陷:對于一個不斷有作業(yè)進入的批解決系統(tǒng)來說,最短作業(yè)優(yōu)先法有也許使得那些長

作業(yè)永遠得不到調(diào)度執(zhí)行的機會。

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

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

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

優(yōu)點:長作業(yè)有機會獲得調(diào)度執(zhí)行

缺陷:同一時間內(nèi)解決的作業(yè)數(shù)少于最短作業(yè)優(yōu)先法,吞吐量也小于最短作業(yè)優(yōu)先法

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

算法評價

FCFS算法

入:作業(yè)到達率;

u:服務(wù)器(主機)的服務(wù)率;

只有當(dāng)人<R時系統(tǒng)才是穩(wěn)定的。

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

R:系統(tǒng)響應(yīng)時間;

P:人/",是系統(tǒng)中存在作業(yè)的概率,1-P是系統(tǒng)中沒有作業(yè)的概率。

n=P/(I-P)

Little結(jié)果:n=入R;R=n/人

FCFS算法的評價:

R=n/入=P/(I-P)*1/A

RR算法

q:時間片;

k:每個進程平均需要的時間片數(shù),即該進程到達等待隊列的次數(shù);

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

1/U:平均服務(wù)時間,則:1/U=kXq

RR算法的評價:

已使用過k次時間片的進程的響應(yīng)時間是:

R(k)=P/(X(l-p))

=l/(U(l-P))=kXq/(l-p)

FCFS方式短作業(yè)駐留時間與長作業(yè)相同,對短作業(yè)不利。

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

實時調(diào)度算法分類:靜態(tài)表格驅(qū)動類、靜態(tài)優(yōu)先級驅(qū)動搶先式調(diào)度算法類、動態(tài)計劃調(diào)

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

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

時限式調(diào)度法(靜態(tài)表格驅(qū)動類代表):是一種以滿足用戶規(guī)定期限為調(diào)度原則的算法。

算法描述:時限有兩種:解決開始時限和解決結(jié)束時限,在實際中可以使用任一種時限。

頻率單調(diào)調(diào)度(靜態(tài)優(yōu)先級驅(qū)動搶先式調(diào)度算法類代表):是一種被廣泛用于多周期性實

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

第五章

1.存儲器:能接受數(shù)據(jù)和保存數(shù)據(jù)、并且能根據(jù)命令提供這些數(shù)據(jù)的裝置。

存儲器提成兩類:內(nèi)存儲器(簡稱內(nèi)存、主存、物理存儲器)外存儲器(簡稱外存、輔

助存儲器)

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

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

程序地址:用戶編程序時所用的地址(或稱邏輯地址、虛地址),基本單位可與內(nèi)存的

基本單位相同,也可以不相同。

程序地址空間(邏輯地址空間、虛地址空間):用戶的程序地址的集合稱為邏輯地址空間,

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

物理地址:把內(nèi)存提成若干個大小相等的存儲單元,每個單元給一個編號,這個編號稱

為內(nèi)存地址(物理地址、絕對地址、實地址),存儲單元占8位,稱作字節(jié)(byte)。

物理地址空間:物理地址的集合稱為物理地址空間(主存地址空間),它是一個一維的線

性空間。

安排進程的地址方法:

(1)按照物理存儲器中的位置賦予實際物理地址。好處:CPU執(zhí)行目的代碼時的執(zhí)行速

度高。壞處:由于物理存儲器的容量限制,能裝入內(nèi)存并發(fā)執(zhí)行的進程數(shù)將會大大

減少,對于某些較大的進程來說,當(dāng)其所規(guī)定的總內(nèi)存容量超過內(nèi)存容量時將會無

法執(zhí)行;由于編譯程序必須知道內(nèi)存的當(dāng)前空閑部分及其地址,并且把一個進程的

不同程序段連續(xù)的存放起來,因此編譯程序?qū)⒎浅?fù)雜。

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

地址空間。

2.存儲管理功能:

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

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

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

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

序比實際主存容量還要大的情況下,程序也能對的運營.

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

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

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

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

(1)編程或編譯時擬定地址映射關(guān)系

編程時擬定虛一實地址的關(guān)系是指在用機器指令編程時,程序員直接按物理內(nèi)存地址編

程,這種程序在系統(tǒng)中是不能做任何移動的,否則就會犯錯。

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

靜態(tài)地址映射是在程序裝入內(nèi)存時完畢從邏輯地址到物理地址的轉(zhuǎn)換的。在一些初期的

系統(tǒng)中都有一個裝入程序(加載程序),它負責(zé)將用戶程序裝入系統(tǒng),并將用戶程序中使

用的訪問內(nèi)存的邏輯地址轉(zhuǎn)換成物理地址。

優(yōu)點:實現(xiàn)簡樸,不要硬件的支持。

缺陷:程序一旦裝入內(nèi)存,移動就比較困難。有時間上的浪費。在程序裝入內(nèi)存時要將

所有訪問內(nèi)存的地址轉(zhuǎn)換成物理地址。

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

(3)動態(tài)地址映射

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

址映射是由硬件地執(zhí)行時完畢的,程序中不執(zhí)行的程序就不做地址映射的工作,這樣節(jié)

省了CPU的時間。重定位寄存器的內(nèi)容由操作系統(tǒng)用特權(quán)指令來設(shè)立,比較靈活。實

現(xiàn)動態(tài)地址映射必須有硬件的支持,并有一定的執(zhí)行時間延遲。現(xiàn)代計算機系統(tǒng)中都采

用動態(tài)地址映射技術(shù)。

優(yōu)點:可以對內(nèi)存進行非連續(xù)分派,動態(tài)重定位提供了實現(xiàn)虛擬存儲器的基礎(chǔ),有助于

程序段的共享。

動態(tài)地址映射技術(shù)能滿足以下目的:

(1)具有給一個用戶程序任意分派內(nèi)存區(qū)的能力;

(2)可實現(xiàn)虛擬存儲;

(3)具有重新分派的能力

(4)對于一個用戶程序,可以分派到多個不同的存儲區(qū)

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

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

數(shù)據(jù)流動控制方法有兩種

一種是用戶自己控制程序,例子:覆蓋技術(shù),一種初期的主存擴充技術(shù),規(guī)定用戶了解

程序結(jié)構(gòu),指定各程序段調(diào)入內(nèi)存的先后順序。

另一種是操作系統(tǒng)控制,A互換方式:操作系統(tǒng)把等待狀態(tài)的進程換出內(nèi)存,而把等待

事件已發(fā)生,處在就緒態(tài)的進程換入內(nèi)存。B請求調(diào)入方式和預(yù)調(diào)入方式:請求調(diào)入方式:

在程序執(zhí)行時,假如所要訪問的程序段或數(shù)據(jù)段不在內(nèi)存中,則操作系統(tǒng)自動地從外存

將有關(guān)程序段和數(shù)據(jù)段調(diào)入內(nèi)存地一種操作系統(tǒng)控制方式。預(yù)調(diào)入方式:系統(tǒng)預(yù)測在不

遠的將來會訪問到的哪些程序段和數(shù)據(jù)段,并在它們訪問前調(diào)入。

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

在多道程序設(shè)計的環(huán)境中,內(nèi)存分派的功能涉及:制定分派策略、構(gòu)造分派用的數(shù)據(jù)結(jié)

構(gòu)、響應(yīng)系統(tǒng)的內(nèi)存分派的請求和回收系統(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ū)

域(或位置),即如何在若干個空閑區(qū)中選擇一個或幾個空閑區(qū)的原則;

(3)互換策略當(dāng)內(nèi)存局限性時,決定將某些信息調(diào)出內(nèi)存的策略。

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

(5)回收策略回收的時機,對所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存空閑區(qū)的整理。

5.內(nèi)存信息的共享與保護

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

(1)上下界保護(常用的硬件保護法)

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

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

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

(2)保護鍵法:為每一個被保護存儲塊分派一個單獨的保護鍵。在程序狀態(tài)字中則設(shè)立

相應(yīng)的保護鍵開關(guān)字段。

(3)界線寄存器與CPU的用戶態(tài)或核心態(tài)工作方式相結(jié)合的保護方式。用戶態(tài)進程只能

訪問那些在界線寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分,而核心態(tài)進程則可以訪問整個內(nèi)存地

址空間。

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

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

由多道環(huán)境下的各并發(fā)進程共享。

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

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

按分區(qū)的時機,分區(qū)管理可以分為固定分區(qū)、動態(tài)分區(qū)。

(1)固定分區(qū)

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

內(nèi)存后,占用其中一個分區(qū),程序運營完畢后釋放該分區(qū)。

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

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

序(作業(yè)、進程)調(diào)入內(nèi)存時,把這個空閑區(qū)的低地址部分的區(qū)域分派給它,當(dāng)有作業(yè)

完畢后釋放所占用的存儲區(qū)。在系統(tǒng)運營的過程中,系統(tǒng)中形成多個空閑的不連續(xù)的存

儲區(qū),稱主空閑。

分區(qū)的分派與回收

(1)固定分區(qū)時的分派和回收

當(dāng)用戶程序要裝入執(zhí)行時,通過請求表提出內(nèi)存分派規(guī)定和所規(guī)定的內(nèi)存空間大小。存

儲管理程序根據(jù)請求表查詢分區(qū)說明表,從中找出一個滿足規(guī)定的空閑分區(qū),并將其分

派給申請者。當(dāng)進程執(zhí)行完畢,不再需要內(nèi)存資源時,管理程序?qū)⑾鄳?yīng)的分區(qū)狀態(tài)置為

未使用即可。

(2)動態(tài)分區(qū)時的分派和回收

動態(tài)分區(qū)時的分派與回收重要解決三個問題:分派空閑區(qū)、更新可用表、合并空閑區(qū)

動態(tài)分區(qū)時的分派方法從可用表或自由鏈中尋找空閑區(qū)的方法:初次適應(yīng)算法、最佳適

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

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

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

組織的。

分派時從表首開始,以請求內(nèi)存區(qū)的大小逐個與空閑區(qū)進行比較,找到第一個滿足規(guī)定

的空閑后,若空閑區(qū)大小與請求區(qū)的大小相等,則將該空閑區(qū)分派給請求者,并撤消該

空閑區(qū)所在表目;若大于請求區(qū),就將該空閑區(qū)的一部分分派給請求者,然后,修改空

閑區(qū)的大小和首址。

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

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

統(tǒng)中有與申請區(qū)大小相等的空閑區(qū),這種算法肯定能將這種空閑區(qū)分派給申請者。(初次

適應(yīng)法則不一定)這種算法最大的缺陷是分割后的空閑區(qū)將會很小,直至無法使用,而

導(dǎo)致浪費。

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

為了克服最佳適應(yīng)算法把空閑區(qū)切割得大小的缺陷,人們提出了一種最壞適應(yīng)算法,即

每次分派時,總是將最大的空閑區(qū)切去一部分分派給請求者,其依據(jù)是當(dāng)一個很大的空

閑區(qū)被切割了一部分后也許仍是一個較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。

(3)動態(tài)分區(qū)的分派與回收

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

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

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

例如:某時刻系統(tǒng)中有三個空閑區(qū),其大小和首址為:(35KB,100KB)、(12KB,156KB)、

(28KB,200KB)o有一作業(yè)系列:(J0B1,12KB)、(JOB2,30KB)、(JOB3,28KB)

(單位:KB>〈單位:KB>

大小首址大<1、首址

351OO23112

1215612156不.,維絨迸行分西已

2820028200

OO

行j=—jobT

(單位:KB)(單位:KB>〈單位:KB>(單位:KB>

大小苜址大<J、首址|大內(nèi)、|首證|大小|首證

121562820028~_200~~11S~~13.0

28200351OO~~130O

351CMDO°

O111111

最佳適應(yīng)券法->1jot>2]cb3

工單位:KB><單位:KB>

大:小首址大小首址

351OO2^112

2820028200不能.繼續(xù)進刊?分配

1215612156

OO

承環(huán)運成算法job1

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

佳的。最先適應(yīng)法盡也許地運用了地地址空間,從而保證高地址有較大的空閑區(qū)來放置

規(guī)定內(nèi)存較多的作業(yè)或進程。

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

它選擇最大的空閑區(qū)來滿足用戶的需求,以期分派后的剩余部分仍能進行再分派。

分區(qū)存儲管理的優(yōu)缺陷:

優(yōu)點:

(1)實現(xiàn)了多個作業(yè)或進程對內(nèi)存的共享,有助于多道程序設(shè)計,從而提高了系統(tǒng)的資

源運用率

(2)該方法規(guī)定的硬件支持少,管理算法簡樸,因而容易實現(xiàn)

缺陷:

(1)內(nèi)存運用率仍然不高

(2)作業(yè)或進程的大小受分區(qū)大小控制,除非配合采用覆蓋技術(shù)和互換技術(shù)

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

覆蓋與互換技術(shù)

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

覆蓋技術(shù)規(guī)定程序員提供一個清楚地覆蓋結(jié)構(gòu)。即程序員必須完畢把一個程序劃提成不

同的程序段,并規(guī)定好它們的執(zhí)行和覆蓋順序的工作。操作系統(tǒng)根據(jù)程序員提供的覆蓋

結(jié)構(gòu)來完畢程序段之間的覆蓋。

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

定的程序或數(shù)據(jù)到內(nèi)存中來,并讓其執(zhí)行的一種內(nèi)存擴充技術(shù)。

互換技術(shù)不規(guī)定程序員給出程序段之間的覆蓋結(jié)構(gòu),互換重要是在進程或作業(yè)之間進行,

覆蓋則重要是在同一個作業(yè)或進程內(nèi)執(zhí)行,覆蓋只能覆蓋那些與覆蓋程序段無關(guān)的程序

段。

互換進程由換入和換出兩個過程組成。

8.頁式管理

頁式管理的基本原理

一方面,進程虛擬地址空間提成大小相等的頁面,進程的虛擬地址變?yōu)轫撎朠與頁內(nèi)地

址W組成。內(nèi)存空間也按頁的大小劃分稱片或頁面,這些頁面為系統(tǒng)中的任一進程所共

享(除去操作系統(tǒng)以外),分頁管理時,用戶進程在內(nèi)存空間內(nèi)除了在每個頁面內(nèi)地址連

續(xù)之外,每個頁面之間不

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論