操作系統(tǒng)知識(shí)重點(diǎn)-學(xué)生復(fù)習(xí)專用

1、操作系統(tǒng)復(fù)習(xí)重點(diǎn)操作系統(tǒng)復(fù)習(xí)重點(diǎn)重點(diǎn)知識(shí)點(diǎn)匯總整理重點(diǎn)知識(shí)點(diǎn)匯總整理考生復(fù)考生復(fù)習(xí)專用習(xí)專用2 1.2 操作系統(tǒng)的發(fā)展過程操作系統(tǒng)的發(fā)展過程無(wú)操作系統(tǒng)時(shí)代無(wú)操作系統(tǒng)時(shí)代單道批處理系統(tǒng)單道批處理系統(tǒng)多道批處理系統(tǒng)多道批處理系統(tǒng)分時(shí)系統(tǒng)分時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)微機(jī)操作系統(tǒng)微機(jī)操作系統(tǒng)31.3 操作系統(tǒng)的基本特性操作系統(tǒng)的基本特性 以多道程序設(shè)計(jì)為基礎(chǔ)的現(xiàn)代操作系統(tǒng)以多道程序設(shè)計(jì)為基礎(chǔ)的現(xiàn)代操作系統(tǒng)具有以下幾個(gè)主要特征：具有以下幾個(gè)主要特征：n并發(fā)性（并發(fā)性（ConcurrenceConcurrence）n共享性（共享性（SharingSharing）n異步性（異步性（AsynchronismAsy

2、nchronism）或稱不確定性）或稱不確定性（NondeterministicNondeterministic）n虛擬性（虛擬性（VirtualVirtual）4引入進(jìn)程引入進(jìn)程在多道程序系統(tǒng)中，為了能夠并發(fā)執(zhí)行，系統(tǒng)在多道程序系統(tǒng)中，為了能夠并發(fā)執(zhí)行，系統(tǒng)必須為每個(gè)程序建立進(jìn)程。必須為每個(gè)程序建立進(jìn)程。n程序是靜態(tài)的，進(jìn)程是動(dòng)態(tài)的。程序是靜態(tài)的，進(jìn)程是動(dòng)態(tài)的。n進(jìn)程能支持并發(fā)，程序不能。進(jìn)程能支持并發(fā)，程序不能。進(jìn)程由一組機(jī)器指令、數(shù)據(jù)和堆棧組成，是一進(jìn)程由一組機(jī)器指令、數(shù)據(jù)和堆棧組成，是一個(gè)能獨(dú)立運(yùn)行的活動(dòng)實(shí)體。個(gè)能獨(dú)立運(yùn)行的活動(dòng)實(shí)體。進(jìn)程是資源分配的獨(dú)立單位。進(jìn)程是資源分配的獨(dú)立單位。

3、多個(gè)進(jìn)程能并發(fā)執(zhí)行，進(jìn)程運(yùn)行時(shí)要占用一定多個(gè)進(jìn)程能并發(fā)執(zhí)行，進(jìn)程運(yùn)行時(shí)要占用一定的系統(tǒng)資源，如的系統(tǒng)資源，如CPU、存儲(chǔ)空間和、存儲(chǔ)空間和I/O設(shè)備等。設(shè)備等。51. 4操作系統(tǒng)功能操作系統(tǒng)功能操作系統(tǒng)有如下幾個(gè)基本功能：操作系統(tǒng)有如下幾個(gè)基本功能：u處理機(jī)管理u存儲(chǔ)器管理u設(shè)備管理u文件管理u用戶接口6（一）（一） 處理機(jī)管理處理機(jī)管理在傳統(tǒng)的多道程序系統(tǒng)中，處理機(jī)的分配和運(yùn)在傳統(tǒng)的多道程序系統(tǒng)中，處理機(jī)的分配和運(yùn)行都是以進(jìn)程為基本單位，因而行都是以進(jìn)程為基本單位，因而對(duì)處理機(jī)的管對(duì)處理機(jī)的管理可歸結(jié)為對(duì)進(jìn)程的管理理可歸結(jié)為對(duì)進(jìn)程的管理：進(jìn)程控制進(jìn)程控制n創(chuàng)建、撤銷、狀態(tài)轉(zhuǎn)換創(chuàng)建、撤銷、狀態(tài)

4、轉(zhuǎn)換進(jìn)程同步進(jìn)程同步n訪問臨界資源、協(xié)調(diào)合作次序訪問臨界資源、協(xié)調(diào)合作次序進(jìn)程通信進(jìn)程通信n合作進(jìn)程的消息交換合作進(jìn)程的消息交換調(diào)度調(diào)度n作業(yè)調(diào)度、進(jìn)程調(diào)度作業(yè)調(diào)度、進(jìn)程調(diào)度7（二）（二） 存儲(chǔ)器管理存儲(chǔ)器管理存儲(chǔ)管理的主要任務(wù)是管理存儲(chǔ)器資源，為多道程存儲(chǔ)管理的主要任務(wù)是管理存儲(chǔ)器資源，為多道程序運(yùn)行提供有力支撐。存儲(chǔ)管理的主要功能包括：序運(yùn)行提供有力支撐。存儲(chǔ)管理的主要功能包括： 內(nèi)存分配內(nèi)存分配n存儲(chǔ)管理將根據(jù)用戶程序的需要給它存儲(chǔ)管理將根據(jù)用戶程序的需要給它分配分配存儲(chǔ)器資源，存儲(chǔ)器資源，并在其使用完畢后并在其使用完畢后回收回收。 內(nèi)存保護(hù)內(nèi)存保護(hù)n存儲(chǔ)管理要把各個(gè)用戶程序存儲(chǔ)管理要把

5、各個(gè)用戶程序相互隔離相互隔離起來(lái)互不干擾，更起來(lái)互不干擾，更不允許用戶程序訪問操作系統(tǒng)的程序和數(shù)據(jù)，從而保護(hù)不允許用戶程序訪問操作系統(tǒng)的程序和數(shù)據(jù)，從而保護(hù)用戶程序存放在存儲(chǔ)器中的信息用戶程序存放在存儲(chǔ)器中的信息不被破壞不被破壞。 8（二）（二） 存儲(chǔ)管理存儲(chǔ)管理地址映射地址映射n進(jìn)程進(jìn)程邏輯地址邏輯地址到內(nèi)存到內(nèi)存物理地址物理地址的映射。這樣程的映射。這樣程序員無(wú)需知道自己的程序分配到內(nèi)存的什么具序員無(wú)需知道自己的程序分配到內(nèi)存的什么具體物理地址，僅僅知道自己的邏輯地址即可，體物理地址，僅僅知道自己的邏輯地址即可，體現(xiàn)了存儲(chǔ)的無(wú)關(guān)性。體現(xiàn)了存儲(chǔ)的無(wú)關(guān)性。內(nèi)存擴(kuò)充內(nèi)存擴(kuò)充n借助虛擬存儲(chǔ)技術(shù)，借

6、助虛擬存儲(chǔ)技術(shù)，從邏輯上擴(kuò)充內(nèi)存從邏輯上擴(kuò)充內(nèi)存，使用，使用戶感覺到比實(shí)際大的多的內(nèi)存，可使更多程序戶感覺到比實(shí)際大的多的內(nèi)存，可使更多程序并發(fā)運(yùn)行。并發(fā)運(yùn)行。n功能：請(qǐng)求調(diào)入、置換功能：請(qǐng)求調(diào)入、置換9（三）（三） 設(shè)備管理設(shè)備管理設(shè)備管理的設(shè)備管理的主要任務(wù)主要任務(wù)：管理各類外圍設(shè)備管理各類外圍設(shè)備，完成用戶提出的，完成用戶提出的I/O請(qǐng)求，加快請(qǐng)求，加快I/O信息的傳送速度，信息的傳送速度，發(fā)揮發(fā)揮I/O設(shè)備的并行性，提高設(shè)備的并行性，提高I/O設(shè)備設(shè)備的利用率；的利用率；以及提供每種設(shè)備的設(shè)備驅(qū)動(dòng)程序和中以及提供每種設(shè)備的設(shè)備驅(qū)動(dòng)程序和中斷處理程序，斷處理程序，向用戶屏蔽硬件使用細(xì)節(jié)向

7、用戶屏蔽硬件使用細(xì)節(jié)。10（三）（三） 設(shè)備管理設(shè)備管理設(shè)備管理的設(shè)備管理的主要功能主要功能：1.緩沖管理緩沖管理w緩沖區(qū)，緩和緩沖區(qū)，緩和CPU和和I/O速度不匹配的矛盾速度不匹配的矛盾w單緩沖、雙緩沖、公用緩沖單緩沖、雙緩沖、公用緩沖2.設(shè)備分配設(shè)備分配w為進(jìn)程分配設(shè)備，以及設(shè)備控制器、通道為進(jìn)程分配設(shè)備，以及設(shè)備控制器、通道3.設(shè)備處理設(shè)備處理w設(shè)備驅(qū)動(dòng)程序：設(shè)備驅(qū)動(dòng)程序：CPU和設(shè)備控制器之間的通信和設(shè)備控制器之間的通信11（四）文件管理（四）文件管理上述三種管理是針對(duì)計(jì)算機(jī)上述三種管理是針對(duì)計(jì)算機(jī)硬件資源硬件資源的管的管理。理。文件管理則是對(duì)系統(tǒng)的文件管理則是對(duì)系統(tǒng)的軟件資源軟件資源

8、的管理。的管理。在現(xiàn)代計(jì)算機(jī)中，通常把程序和數(shù)據(jù)以文在現(xiàn)代計(jì)算機(jī)中，通常把程序和數(shù)據(jù)以文件形式存儲(chǔ)在外存儲(chǔ)器上，供用戶使用。件形式存儲(chǔ)在外存儲(chǔ)器上，供用戶使用。為此，為此，OS需配置文件管理機(jī)構(gòu)。需配置文件管理機(jī)構(gòu)。12（四）文件管理的主要功能（四）文件管理的主要功能文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理n為文件為文件分配外存分配外存空間，提高外存利用率空間，提高外存利用率n記錄記錄外存外存使用使用情況，情況，分配、回收分配、回收外存空間外存空間目錄管理目錄管理n為文件建立目錄項(xiàng)，有效組織，為文件建立目錄項(xiàng)，有效組織，按名存取按名存取文件的讀文件的讀/寫管理和保護(hù)寫管理和保護(hù)n向外存讀取向外存讀

9、取/寫入數(shù)據(jù)寫入數(shù)據(jù)n防止文件被非法竊取或破壞防止文件被非法竊取或破壞存取控制存取控制13（五）（五）OS與用戶之間的接口與用戶之間的接口1.用戶接口用戶接口n聯(lián)機(jī)接口聯(lián)機(jī)接口w命令，用戶通過和終端交互控制作業(yè)命令，用戶通過和終端交互控制作業(yè)n脫機(jī)接口脫機(jī)接口w作業(yè)控制語(yǔ)言作業(yè)控制語(yǔ)言(JCL)，用戶通過，用戶通過作業(yè)說明書作業(yè)說明書委托系統(tǒng)代委托系統(tǒng)代為控制作業(yè)為控制作業(yè)n圖形用戶接口圖形用戶接口w用直觀圖標(biāo)、菜單、對(duì)話框替代命令，免于單調(diào)、繁瑣用直觀圖標(biāo)、菜單、對(duì)話框替代命令，免于單調(diào)、繁瑣和記憶之累和記憶之累2.程序接口程序接口n供用戶程序使用供用戶程序使用OS服務(wù)的服務(wù)的系統(tǒng)調(diào)用系統(tǒng)調(diào)

10、用152.2.1 進(jìn)程的描述進(jìn)程的描述1.進(jìn)程的定義和特征2.進(jìn)程的基本狀態(tài)及轉(zhuǎn)換3.掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換4.進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)162.2.1 進(jìn)程的定義進(jìn)程的定義進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。其他經(jīng)典定義：n進(jìn)程是程序的一次執(zhí)行。n進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。n進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。17進(jìn)程的相關(guān)概念進(jìn)程的相關(guān)概念進(jìn)程控制塊(PCB: Process Control Block)n一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來(lái)描述進(jìn)程的基本情況和活動(dòng)過程，為操作系統(tǒng)管理和控制進(jìn)程所必需。進(jìn)程實(shí)

11、體n由程序段、數(shù)據(jù)段、PCB三部分構(gòu)成n通常所說的進(jìn)程實(shí)際上是指進(jìn)程實(shí)體創(chuàng)建進(jìn)程，實(shí)質(zhì)上是創(chuàng)建進(jìn)程實(shí)體中的PCB撤銷進(jìn)程，實(shí)質(zhì)上是撤銷進(jìn)程的PCB18進(jìn)程的特征進(jìn)程的特征動(dòng)態(tài)性n進(jìn)程的實(shí)質(zhì)：進(jìn)程實(shí)體的一次執(zhí)行過程n由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡并發(fā)性n多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中n能在同一段時(shí)間內(nèi)同時(shí)運(yùn)行獨(dú)立性n能夠獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度的基本單位異步性n進(jìn)程以各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。19進(jìn)程與程序的關(guān)系程序是指令的有序集合，其本身沒有任何運(yùn)行的含義，是一個(gè)靜態(tài)的概程序是指令的有序集合，其本身沒有任何運(yùn)行的含義，是一個(gè)靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行

12、過程，它是一個(gè)動(dòng)態(tài)的概念。念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，它是一個(gè)動(dòng)態(tài)的概念。程序可以作為一種軟件資料長(zhǎng)期保存在某種介質(zhì)上，而進(jìn)程是有一定生程序可以作為一種軟件資料長(zhǎng)期保存在某種介質(zhì)上，而進(jìn)程是有一定生命期的，進(jìn)程被創(chuàng)建后存在于內(nèi)存中，進(jìn)程消亡后生命期結(jié)束，不再存命期的，進(jìn)程被創(chuàng)建后存在于內(nèi)存中，進(jìn)程消亡后生命期結(jié)束，不再存在。在。程序的每次運(yùn)行都將創(chuàng)建新的進(jìn)程，而進(jìn)程一旦消亡，就無(wú)法再被執(zhí)行。程序的每次運(yùn)行都將創(chuàng)建新的進(jìn)程，而進(jìn)程一旦消亡，就無(wú)法再被執(zhí)行。進(jìn)程更能真實(shí)地描述并發(fā)，而程序不能進(jìn)程更能真實(shí)地描述并發(fā)，而程序不能( (沒有沒有PCB)PCB)。進(jìn)程能夠獨(dú)立運(yùn)行、獨(dú)立分配資

13、源和獨(dú)立接受調(diào)度的基本單位，程序進(jìn)程能夠獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度的基本單位，程序（沒有（沒有PCBPCB）不能作為獨(dú)立的單位運(yùn)行。）不能作為獨(dú)立的單位運(yùn)行。202.2.2 進(jìn)程的基本狀態(tài)進(jìn)程的基本狀態(tài)就緒就緒(Ready)狀態(tài)狀態(tài)執(zhí)行執(zhí)行(Running)狀態(tài)狀態(tài)阻塞阻塞(Blocked)狀態(tài)狀態(tài)21就緒就緒(Ready)就緒狀態(tài)就緒狀態(tài)n是指進(jìn)程已處于準(zhǔn)備好運(yùn)行的狀態(tài)，已經(jīng)獲得是指進(jìn)程已處于準(zhǔn)備好運(yùn)行的狀態(tài)，已經(jīng)獲得除除CPU以外以外的的所有必要資源所有必要資源，因其，因其CPU正被其他進(jìn)程正被其他進(jìn)程占用而無(wú)法執(zhí)行，一旦獲得占用而無(wú)法執(zhí)行，一旦獲得CPU, 可以立即執(zhí)行?？梢粤?/p>

14、即執(zhí)行。就緒進(jìn)程就緒進(jìn)程n處于就緒狀態(tài)的進(jìn)程稱為就緒進(jìn)程。處于就緒狀態(tài)的進(jìn)程稱為就緒進(jìn)程。就緒隊(duì)列就緒隊(duì)列n所有的就緒進(jìn)程排成一個(gè)隊(duì)列，等待獲得所有的就緒進(jìn)程排成一個(gè)隊(duì)列，等待獲得CPU。n隊(duì)列的排序與調(diào)度策略有關(guān)。隊(duì)列的排序與調(diào)度策略有關(guān)。22執(zhí)行執(zhí)行(Running)執(zhí)行狀態(tài)執(zhí)行狀態(tài)n是指當(dāng)前進(jìn)程已經(jīng)是指當(dāng)前進(jìn)程已經(jīng)獲得獲得CPU，其程序，其程序正在執(zhí)行正在執(zhí)行的的狀態(tài)。狀態(tài)。當(dāng)前進(jìn)程當(dāng)前進(jìn)程n正在執(zhí)行的進(jìn)程稱為當(dāng)前進(jìn)程。正在執(zhí)行的進(jìn)程稱為當(dāng)前進(jìn)程。單處理機(jī)系統(tǒng)單處理機(jī)系統(tǒng)n任一時(shí)刻，只有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)任一時(shí)刻，只有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)多處理機(jī)系統(tǒng)多處理機(jī)系統(tǒng)n可有多個(gè)進(jìn)程同時(shí)處于執(zhí)

15、行狀態(tài)可有多個(gè)進(jìn)程同時(shí)處于執(zhí)行狀態(tài)23阻塞阻塞(Blocked)阻塞狀態(tài)阻塞狀態(tài)n也叫也叫等待等待狀態(tài)，是指狀態(tài)，是指原本正在執(zhí)行原本正在執(zhí)行的進(jìn)程由于的進(jìn)程由于發(fā)生發(fā)生某事件某事件（如（如I/O請(qǐng)求，等待其他進(jìn)程發(fā)來(lái)的信號(hào)）請(qǐng)求，等待其他進(jìn)程發(fā)來(lái)的信號(hào)）而暫時(shí)無(wú)法繼續(xù)執(zhí)行的狀態(tài)。而暫時(shí)無(wú)法繼續(xù)執(zhí)行的狀態(tài)。n也就是說，進(jìn)程的執(zhí)行受到也就是說，進(jìn)程的執(zhí)行受到阻塞阻塞。阻塞進(jìn)程阻塞進(jìn)程n處于阻塞狀態(tài)的進(jìn)程稱為阻塞進(jìn)程。處于阻塞狀態(tài)的進(jìn)程稱為阻塞進(jìn)程。n阻塞進(jìn)程尚阻塞進(jìn)程尚不具備運(yùn)行條件不具備運(yùn)行條件，即使，即使CPU空閑它也無(wú)空閑它也無(wú)法使用。法使用。阻塞隊(duì)列阻塞隊(duì)列n進(jìn)程在阻塞隊(duì)列中等待進(jìn)程在阻

16、塞隊(duì)列中等待n按阻塞原因排成不同隊(duì)列按阻塞原因排成不同隊(duì)列(大系統(tǒng)常用大系統(tǒng)常用)24三種基本狀態(tài)的轉(zhuǎn)換三種基本狀態(tài)的轉(zhuǎn)換25引起進(jìn)程狀態(tài)轉(zhuǎn)換的具體原因引起進(jìn)程狀態(tài)轉(zhuǎn)換的具體原因就緒就緒 - 執(zhí)行執(zhí)行n調(diào)度調(diào)度程序選擇一個(gè)新的進(jìn)程執(zhí)行程序選擇一個(gè)新的進(jìn)程執(zhí)行執(zhí)行執(zhí)行 - 就緒就緒n當(dāng)前進(jìn)程當(dāng)前進(jìn)程用完了時(shí)間片用完了時(shí)間片；n當(dāng)前進(jìn)程被中斷，被一個(gè)當(dāng)前進(jìn)程被中斷，被一個(gè)更高優(yōu)先級(jí)更高優(yōu)先級(jí)的的就緒進(jìn)程就緒進(jìn)程搶占搶占CPU執(zhí)行執(zhí)行 - 阻塞阻塞(等待等待)n發(fā)生某事件，導(dǎo)致等待發(fā)生某事件，導(dǎo)致等待：如：如OS尚未完成進(jìn)程請(qǐng)求的服務(wù)；進(jìn)程尚未完成進(jìn)程請(qǐng)求的服務(wù)；進(jìn)程向向OS申請(qǐng)緩沖空間；對(duì)某資源的

17、訪問尚不能進(jìn)行；初始化申請(qǐng)緩沖空間；對(duì)某資源的訪問尚不能進(jìn)行；初始化I/O 且必須等待結(jié)果；等待某個(gè)進(jìn)程提供輸入且必須等待結(jié)果；等待某個(gè)進(jìn)程提供輸入, 阻塞阻塞(等待等待) - 就緒就緒n當(dāng)所等待的事件發(fā)生當(dāng)所等待的事件發(fā)生, 欠缺的運(yùn)行條件被滿足欠缺的運(yùn)行條件被滿足：如，得到所請(qǐng)求：如，得到所請(qǐng)求的資源；的資源；I/O操作完成；操作完成；OS完成進(jìn)程請(qǐng)求的服務(wù)；得到申請(qǐng)的完成進(jìn)程請(qǐng)求的服務(wù)；得到申請(qǐng)的緩沖區(qū)緩沖區(qū); 等待的數(shù)據(jù)已經(jīng)到達(dá)等待的數(shù)據(jù)已經(jīng)到達(dá); 26進(jìn)程控制塊的作用進(jìn)程控制塊的作用1.作為獨(dú)立運(yùn)行基本單位的標(biāo)志系統(tǒng)通過PCB感知進(jìn)程的存在PCB是進(jìn)程存在的唯一標(biāo)志2.實(shí)現(xiàn)間斷性運(yùn)行

18、方式保存被中斷進(jìn)程的CPU運(yùn)行現(xiàn)場(chǎng)3.提供進(jìn)程管理所需要的信息程序/數(shù)據(jù)保存位置資源清單4.提供進(jìn)程調(diào)度所需要的信息5.實(shí)現(xiàn)與其他進(jìn)程的同步和通信27進(jìn)程控制塊中的信息進(jìn)程控制塊中的信息1.進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符(用于識(shí)別進(jìn)程用于識(shí)別進(jìn)程)n內(nèi)部標(biāo)識(shí)符：操作系統(tǒng)使用內(nèi)部標(biāo)識(shí)符：操作系統(tǒng)使用n外部標(biāo)識(shí)符：用戶使用外部標(biāo)識(shí)符：用戶使用2.處理機(jī)狀態(tài)處理機(jī)狀態(tài)n即處理機(jī)上下文，主要包括處理機(jī)中各種寄存器即處理機(jī)上下文，主要包括處理機(jī)中各種寄存器的內(nèi)容：的內(nèi)容：w通用寄存器通用寄存器w指令計(jì)數(shù)器指令計(jì)數(shù)器(PC)w程序狀態(tài)字程序狀態(tài)字(PSW)w用戶棧指針用戶棧指針n進(jìn)程切換時(shí)，這些信息用來(lái)使當(dāng)前進(jìn)程被

19、上次中進(jìn)程切換時(shí)，這些信息用來(lái)使當(dāng)前進(jìn)程被上次中斷地方繼續(xù)執(zhí)行。斷地方繼續(xù)執(zhí)行。28進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式3.進(jìn)程調(diào)度信息n進(jìn)程狀態(tài)n進(jìn)程優(yōu)先級(jí)n調(diào)度所需其他信息n事件(阻塞原因)4.進(jìn)程控制信息n程序/數(shù)據(jù)的地址(內(nèi)/外存首地址)n同步/通信機(jī)制(消息隊(duì)列指針、信號(hào)量)n資源清單(需求、占用)n鏈接指針(隊(duì)列中下一個(gè)PCB)29進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式1.線性方式n所有進(jìn)程組織在一張線性表中 w實(shí)現(xiàn)簡(jiǎn)單，但查找時(shí)需掃描整張表2.鏈接方式n相同狀態(tài)進(jìn)程的PCB鏈接成一個(gè)隊(duì)列w就緒隊(duì)列、阻塞隊(duì)列、空白隊(duì)列3.索引方式n按進(jìn)程狀態(tài)的不同，建立幾張索引表n索引表的表

20、項(xiàng)：各進(jìn)程PCB首址線性方式線性方式30鏈接方式鏈接方式31索引方式索引方式322.4 進(jìn)程同步進(jìn)程同步進(jìn)程的進(jìn)程的異步性異步性，和對(duì)，和對(duì)臨界資源臨界資源的爭(zhēng)用，的爭(zhēng)用，會(huì)給系統(tǒng)帶來(lái)混亂。會(huì)給系統(tǒng)帶來(lái)混亂。進(jìn)程同步的進(jìn)程同步的主要任務(wù)：主要任務(wù)：n對(duì)多個(gè)相關(guān)進(jìn)程在對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上執(zhí)行次序上進(jìn)行進(jìn)行協(xié)協(xié)調(diào)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有有效效地地共享共享資源和相互資源和相互合作合作，從而使程，從而使程序的執(zhí)行具有序的執(zhí)行具有可再現(xiàn)性可再現(xiàn)性。33進(jìn)程間的兩種制約關(guān)系進(jìn)程間的兩種制約關(guān)系間接間接相互制約相互制約n源于源于資源共享資源共享，即對(duì)資源的，即對(duì)資源

21、的競(jìng)爭(zhēng)關(guān)系競(jìng)爭(zhēng)關(guān)系，進(jìn)程進(jìn)程需要互斥地訪問同一資源需要互斥地訪問同一資源直接直接相互制約相互制約n源于源于進(jìn)程合作進(jìn)程合作，即，即協(xié)作關(guān)系協(xié)作關(guān)系，某些進(jìn)程為完，某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作成同一任務(wù)需要分工協(xié)作34 同步機(jī)制應(yīng)遵循的規(guī)則同步機(jī)制應(yīng)遵循的規(guī)則1.空閑讓進(jìn)空閑讓進(jìn)n沒有進(jìn)程在臨界區(qū)，表明臨界資源空閑，應(yīng)允許一個(gè)請(qǐng)求進(jìn)沒有進(jìn)程在臨界區(qū)，表明臨界資源空閑，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入臨界區(qū)，以保證資源的入臨界區(qū)的進(jìn)程立即進(jìn)入臨界區(qū)，以保證資源的有效利用有效利用。2.忙則等待忙則等待n已有進(jìn)程進(jìn)入臨界區(qū)，表明臨界資源正在被訪問，其他請(qǐng)求已有進(jìn)程進(jìn)入臨界區(qū)，表明臨界資源正

22、在被訪問，其他請(qǐng)求進(jìn)入臨界區(qū)進(jìn)程必須等待，以保證對(duì)臨界資源的進(jìn)入臨界區(qū)進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問互斥訪問。3.有限等待有限等待n一個(gè)進(jìn)程不能無(wú)限地等待進(jìn)入臨界區(qū)，一個(gè)進(jìn)程不能無(wú)限地等待進(jìn)入臨界區(qū)，避免避免“死等死等”。4.讓權(quán)等待讓權(quán)等待n進(jìn)程若不能進(jìn)入自己的臨界區(qū)，應(yīng)立即釋放處理機(jī)，進(jìn)程若不能進(jìn)入自己的臨界區(qū)，應(yīng)立即釋放處理機(jī)，避免避免“忙等忙等”。352.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制1.整型信號(hào)量2.記錄型信號(hào)量3.AND型信號(hào)量4.信號(hào)量集361.整型信號(hào)量整型信號(hào)量定義定義S為一個(gè)用于為一個(gè)用于表示資源數(shù)目表示資源數(shù)目的的整型量整型量，除初始化外，除初始化外，僅能通過兩個(gè)

23、標(biāo)準(zhǔn)的僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作原子操作wait(S)和和signal(S)來(lái)訪來(lái)訪問。這兩個(gè)操作也被稱為問。這兩個(gè)操作也被稱為P、V操作。操作。 wait(S) while (S - 切換迅速、開銷小切換迅速、開銷小 3.3.可并發(fā)執(zhí)行可并發(fā)執(zhí)行n同一進(jìn)程中的線程同一進(jìn)程中的線程n不同進(jìn)程中的線程不同進(jìn)程中的線程4.4.共享進(jìn)程資源共享進(jìn)程資源n如，地址空間、已打開文件、信號(hào)量等等如，地址空間、已打開文件、信號(hào)量等等52線程的狀態(tài)線程的狀態(tài)狀態(tài)參數(shù)n用于描述線程的一組數(shù)據(jù)，包括：w寄存器狀態(tài)、堆棧、線程運(yùn)行狀態(tài)、優(yōu)先級(jí)、線程專有存儲(chǔ)器、信號(hào)屏蔽等線程運(yùn)行狀態(tài)n執(zhí)行、就緒、阻塞第三章第三章 處

24、理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖543.1 處理機(jī)調(diào)度的層次 在多道程序系統(tǒng)中，一個(gè)作業(yè)被提交后必須經(jīng)過處理機(jī)調(diào)度后，方能獲得處理機(jī)執(zhí)行。不同系統(tǒng)中，調(diào)度過程有差異： 批量型作業(yè)：作業(yè)調(diào)度+進(jìn)程調(diào)度 終端型作業(yè)：進(jìn)程調(diào)度 較完善的OS中，增加了中級(jí)調(diào)度，一個(gè)批處理型作業(yè)可能要經(jīng)歷三級(jí)調(diào)度。55處理機(jī)調(diào)度的三個(gè)層次1. 高級(jí)調(diào)度（作業(yè)調(diào)度、長(zhǎng)程調(diào)度）2. 初級(jí)調(diào)度（進(jìn)程調(diào)度、短程調(diào)度）3. 中級(jí)調(diào)度（中程調(diào)度）563.1.1 高級(jí)調(diào)度 高級(jí)調(diào)度又稱為作業(yè)調(diào)度或長(zhǎng)程調(diào)度，主要功能是根據(jù)某種算法，把外存上處于后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi)存，調(diào)度的對(duì)象是作業(yè)。57作業(yè)的概念什么是作業(yè)：是用戶在一次解題或一

25、個(gè)事務(wù)處理過程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合。它包括用戶程序、所需要的數(shù)據(jù)及控制命令等。作業(yè)是由一系列有序的作業(yè)步組成的。一個(gè)作業(yè)由3部分組成，即程序、數(shù)據(jù)及作業(yè)說明書。其中，作業(yè)說明書體現(xiàn)了用戶對(duì)作業(yè)的控制意圖。583.1.1 高級(jí)調(diào)度 (High Scheduling) 作業(yè)調(diào)度也稱為接納調(diào)度。在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定： 1) 接納多少個(gè)作業(yè) 取決于多道程序度（允許多少道作業(yè)同時(shí)在內(nèi)存） 2) 接納哪些作業(yè) 取決于調(diào)度算法593.1.2. 低級(jí)調(diào)度(Low Level Scheduling) 低級(jí)調(diào)度稱為進(jìn)程調(diào)度或短程調(diào)度，調(diào)度的對(duì)象是進(jìn)程。低級(jí)調(diào)度用于決定就緒隊(duì)列中的哪

26、個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。低級(jí)調(diào)度的主要功能：保存處理機(jī)現(xiàn)場(chǎng)按某種算法選取進(jìn)程把處理機(jī)分配給進(jìn)程60進(jìn)程調(diào)度中的三個(gè)基本機(jī)制排隊(duì)器n將就緒進(jìn)程按照一定的方式排成一個(gè)或多個(gè)隊(duì)列，以便調(diào)度程序有效率地訪問。分派器（Dispatcher, 分派程序）n從就緒隊(duì)列上取出調(diào)度程序選中的進(jìn)程，進(jìn)行上下文切換，把處理機(jī)分配給它。上下文切換機(jī)制(CPU現(xiàn)場(chǎng)信息)n處理機(jī)切換時(shí)，會(huì)發(fā)生兩對(duì)上下文切換：w保存當(dāng)前進(jìn)程上下文，裝入分派程序上下文w移出分派程序，裝入新選中進(jìn)程的上下文61進(jìn)程的兩種調(diào)度方式 1.非搶占方式(Non-preemptive Mode)2.搶占方

27、式(Preemptive)62非搶占方式一旦處理機(jī)分配給某進(jìn)程，就讓它一直運(yùn)行下去，不管它運(yùn)行多長(zhǎng)時(shí)間，不允許其他進(jìn)程搶占已分配給它的處理機(jī)。除非進(jìn)程完成而釋放處理機(jī)，或進(jìn)程阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。63非搶占方式下的調(diào)度在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個(gè)： 正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； 執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行； 在進(jìn)程通信或同步過程中執(zhí)行了某種原語(yǔ)操作，如P操作(wait操作)、Block原語(yǔ)。64非搶占方式的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：n實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開銷小，適用于批處理系統(tǒng)環(huán)境。缺點(diǎn)：n難以滿足緊急任務(wù)的要求立即執(zhí)行，不適

28、合分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)。65搶占方式搶占方式允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。搶占方式是基于一定原則的：1.優(yōu)先權(quán)原則；2.短作業(yè)(進(jìn)程)優(yōu)先原則； 3.時(shí)間片原則。 66搶占方式的優(yōu)缺點(diǎn)優(yōu)點(diǎn):n防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī)n能為大多數(shù)進(jìn)程提供更公平的服務(wù)n能滿足對(duì)響應(yīng)時(shí)間需求嚴(yán)格的場(chǎng)合缺點(diǎn)：n調(diào)度開銷較大673.1.3 中級(jí)調(diào)度(Intermediate-Level Scheduling) 中級(jí)調(diào)度又稱中程調(diào)度(Medium-Term Scheduling)。 引入中級(jí)調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 為此，應(yīng)使那

29、些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來(lái)決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。中級(jí)調(diào)度實(shí)際上就是存儲(chǔ)器管理(第4章)中的對(duì)換功能。683.3 調(diào)度算法調(diào)度的實(shí)質(zhì)：一種資源分配(CPU、內(nèi)存)調(diào)度算法：根據(jù)系統(tǒng)資源分配策略制定的資源分配算法。不同的系統(tǒng)具有不同的資源分配目標(biāo)，因而采用的調(diào)度算法也不同。n資源分配目標(biāo)：傾向于滿足用戶交互還是充分利用計(jì)算機(jī)資源，吞吐量/響應(yīng)時(shí)間/周轉(zhuǎn)時(shí)間/優(yōu)先權(quán)

30、/公平性調(diào)度算法的適用：進(jìn)程調(diào)度，作業(yè)調(diào)度，或者都適用。693.3 調(diào)度算法 3.3.1 先來(lái)先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法 1. 先來(lái)先服務(wù)(FCFS，F(xiàn)irst Come, First Served)調(diào)度算法 適用：進(jìn)程調(diào)度、作業(yè)調(diào)度 有利于長(zhǎng)作業(yè)/進(jìn)程，不利于短作業(yè)/進(jìn)程 有利于CPU繁忙型作業(yè)/進(jìn)程，不利于IO繁忙型作業(yè)/進(jìn)程702. 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。短進(jìn)程

31、優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度?？捎行Ы档妥鳂I(yè)/進(jìn)程的平均等待時(shí)間。71圖 3-4 FCFS和SJF調(diào)度算法的性能 SJF: Short Job First,短作業(yè)優(yōu)先 72SJ(P)F缺點(diǎn)： (1) 該算法對(duì)長(zhǎng)作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長(zhǎng)作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來(lái)的)短作業(yè)(進(jìn)程)，將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度。（不利長(zhǎng)作業(yè)） (2

32、) 該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。（不及時(shí)） (3) 由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。（不完全可靠） 73調(diào)度算法練習(xí)題74先來(lái)先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法340.8010.3010.100.209.50446.51.3010.8010.600.209.5042111.1010.1010.000.109.0033161.6010.6010.500.109.00344.62.3010.8010.300.508.502242

33、.0010.5010.000.508.502112.0010.008.002.008.001112.0010.008.002.008.001執(zhí)行順序帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間完成時(shí)間開始時(shí)間運(yùn)行時(shí)間提交時(shí)間作業(yè)先來(lái)先服務(wù)調(diào)度算法平均周轉(zhuǎn)時(shí)間 t = 1.725平均帶權(quán)周轉(zhuǎn)時(shí)間 w = 6.875短作業(yè)優(yōu)先調(diào)度算法平均周轉(zhuǎn)時(shí)間 t = 1.55平均帶權(quán)周轉(zhuǎn)時(shí)間 w = 5.1575作作業(yè)業(yè)進(jìn)進(jìn)入入時(shí)時(shí)間間估估計(jì)計(jì)運(yùn)運(yùn)行行時(shí)時(shí)間間（分分鐘鐘）J JO OB B1 18 8: :0 00 0 1 12 20 0J JO OB B2 28 8: :5 50 0 5 50 0J JO OB B3 39 9:

34、:0 00 0 1 10 0J JO OB B4 49 9: :5 50 0 2 20 0例題：?jiǎn)蔚拉h(huán)境下四個(gè)作業(yè)，它們進(jìn)入系統(tǒng)的時(shí)間如例題：?jiǎn)蔚拉h(huán)境下四個(gè)作業(yè)，它們進(jìn)入系統(tǒng)的時(shí)間如下：下：(1)給出給出FCFS , SJF下的作業(yè)執(zhí)行次序下的作業(yè)執(zhí)行次序(2)給出給出FCFS , SJF下的作業(yè)平均周轉(zhuǎn)時(shí)間和帶權(quán)平均下的作業(yè)平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間76作作業(yè)業(yè)進(jìn)進(jìn)入入時(shí)時(shí)間間估估計(jì)計(jì)運(yùn)運(yùn)行行時(shí)時(shí)間間（分分鐘鐘）SJF完完成成時(shí)時(shí)刻刻FCFS完完成成時(shí)時(shí)刻刻JOB18:0012010:0010:00JOB28:505011:2010:50JOB39:001010:1011:00J

35、OB49:502010:3011:20773.3.2 3.3.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 1 1 優(yōu)先級(jí)調(diào)度算法w優(yōu)先級(jí)調(diào)度算法（priority-scheduling algorithmpriority-scheduling algorithm）是指每個(gè)進(jìn)程都有一個(gè)優(yōu)先級(jí)與其相關(guān)聯(lián)，具有最高優(yōu)先級(jí)的就緒進(jìn)程會(huì)被分派到CPUCPU, ,具有相同優(yōu)先級(jí)的進(jìn)程按FCFSFCFS順序調(diào)度。 w優(yōu)先級(jí)通常為固定區(qū)間的數(shù)字，如0 0到7 7，或者0 0到40954095。不過，對(duì)于0 0是最高還是最低的優(yōu)先級(jí)，并沒有定論。有的系統(tǒng)用低數(shù)字表示低優(yōu)先級(jí)，而有的系統(tǒng)使用低數(shù)字表示高優(yōu)先級(jí)。78例3-23-2：

36、有5 5個(gè)進(jìn)程P1P1、P2P2、P3P3、P4P4、P5P5，它們同時(shí)依次進(jìn)入就緒隊(duì)列，它們的優(yōu)先數(shù)和需要的處理機(jī)時(shí)間如下： 進(jìn)程 處理機(jī)時(shí)間 優(yōu)先數(shù) P1 10 3P1 10 3 P2 1 1 P2 1 1 P3 2 3 P3 2 3 P4 1 4 P4 1 4 P5 5 2 P5 5 2 忽略進(jìn)程調(diào)度所花的時(shí)間，要求：（1 1）分別寫出采用先來(lái)先服務(wù)調(diào)度算法和靜態(tài)優(yōu)先級(jí)調(diào)度算法中進(jìn)程的執(zhí)行次序；（2 2）分別計(jì)算各進(jìn)程在就緒隊(duì)列中的等待時(shí)間和平均等待時(shí)間。FCFSFCFS等待時(shí)間等待時(shí)間 靜態(tài)優(yōu)先級(jí)法等待時(shí)間靜態(tài)優(yōu)先級(jí)法等待時(shí)間 0 1 0 1 10 18 10 18 11 11 11

37、11 13 0 13 0 14 13 14 13 解:(1)采用FCFS調(diào)度算法時(shí)各進(jìn)程的執(zhí)行次序?yàn)椋篜1P2P3P4P5。 采用靜態(tài)優(yōu)先級(jí)調(diào)度算法時(shí)各進(jìn)程的執(zhí)行次序?yàn)椋?P4P1P3P5P2（假設(shè)優(yōu)先數(shù)與優(yōu)先權(quán)成正比）。 (2)FCFS中，平均等待時(shí)間（0+10+11+13+14）/59.6； 靜態(tài)優(yōu)先級(jí)法中，平均等待時(shí)間（1+18+11+0+13）/58.6793.3.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 2. 優(yōu)先權(quán)調(diào)度算法的類型 1) 非搶占式優(yōu)先權(quán)算法 在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成； 或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可

38、再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。 80 2) 搶占式優(yōu)先權(quán)調(diào)度算法 在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。 顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中， 以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。 3.3.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 813. 優(yōu)先權(quán)的類型 1) 靜態(tài)優(yōu)先權(quán) 靜態(tài)

39、優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如，07或0255中的某一整數(shù)， 又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。 特點(diǎn)：簡(jiǎn)單易行，開銷小，但不精確，低優(yōu)先權(quán)作業(yè)可能長(zhǎng)期不被調(diào)度。82 2) 動(dòng)態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。例如: 在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增加，優(yōu)先權(quán)以速率a提高，避免優(yōu)先權(quán)低的進(jìn)程長(zhǎng)期得不到執(zhí)行； 或者當(dāng)采用搶占式調(diào)度時(shí)，

40、正在執(zhí)行的進(jìn)程，隨著執(zhí)行時(shí)間的增加，優(yōu)先權(quán)以速率b下降，防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期壟斷CPU。2. 優(yōu)先權(quán)的類型 833.3.高響應(yīng)比優(yōu)先調(diào)度算法該算法，就是每次調(diào)度一個(gè)作業(yè)投入運(yùn)行時(shí)，計(jì)算后備作業(yè)表中每個(gè)作業(yè)的響應(yīng)比，然后挑選響應(yīng)比最高的投入運(yùn)行。843. 高響應(yīng)比優(yōu)先調(diào)度算法 要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)引入動(dòng)態(tài)優(yōu)先權(quán)后，優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為： 要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)85高響應(yīng)比優(yōu)先調(diào)度算法舉例46.51.3010.8010.600.209.5

41、042111.1010.1010.000.109.00334.22.1010.6010.100.508.502112.0010.008.002.008.001執(zhí)行順序帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間完成時(shí)間開始時(shí)間運(yùn)行時(shí)間提交時(shí)間作業(yè)高響應(yīng)比優(yōu)先調(diào)度算法平均周轉(zhuǎn)時(shí)間 t = 1.625平均帶權(quán)周轉(zhuǎn)時(shí)間 w =5.67586 (1) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。 (2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。 (3) 對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足

42、夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高， 從而也可獲得處理機(jī)。 缺點(diǎn)：每次調(diào)度前都要計(jì)算響應(yīng)比，增加了系統(tǒng)開銷。3. 高響應(yīng)比優(yōu)先調(diào)度算法 873.3.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 1. 時(shí)間片輪轉(zhuǎn)法 在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來(lái)停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)

43、，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。883.3.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 2. 時(shí)間片大小的確定 在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響，如選擇很小的時(shí)間片，將很有利于短作業(yè)，但會(huì)頻繁發(fā)生中斷和進(jìn)程上下文的切換；反之，如選擇太長(zhǎng)的時(shí)間片，使得每一個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成，時(shí)間片輪轉(zhuǎn)算法便退化為FCFS算法，無(wú)法滿足交互式用戶的需求。 時(shí)間片應(yīng)略大于一次典型的交互所需要的時(shí)間。 舉例見課本P95892. 多級(jí)反饋隊(duì)列調(diào)度算法 (1) 應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。 第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中

44、進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍，第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍。 圖 3-7 是多級(jí)反饋隊(duì)列調(diào)度算法的示意。 903.5 產(chǎn)生死鎖的原因和必要條件多進(jìn)程的并發(fā)執(zhí)行，可改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但也可能發(fā)生一種危險(xiǎn)死鎖。死鎖：n多個(gè)進(jìn)程中運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們將無(wú)法再向前推進(jìn)。91死鎖產(chǎn)生的原因（1）資源有限。當(dāng)系統(tǒng)中多個(gè)進(jìn)程共享資源，如打印機(jī)、公用隊(duì)列等，其數(shù)目不足以滿足諸進(jìn)程的需要，會(huì)引起

45、進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。（2）并發(fā)進(jìn)程間的推進(jìn)順序不當(dāng)。進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)，也會(huì)導(dǎo)致產(chǎn)生進(jìn)程死鎖。 92系統(tǒng)中的資源類型可剝奪性資源n資源分配給進(jìn)程之后，可以被系統(tǒng)或其他進(jìn)程剝奪。n如：CPU非剝奪性資源n資源一旦分配給進(jìn)程，不能強(qiáng)行收回，只能等進(jìn)程用完自行釋放。n如：打印機(jī)臨時(shí)性資源n由進(jìn)程通信產(chǎn)生的，具有一定時(shí)效性的資源，如消息n相應(yīng)地，CPU、打印機(jī)屬永久性資源93資源競(jìng)爭(zhēng)引起進(jìn)程死鎖1.競(jìng)爭(zhēng)非剝奪性資源2.競(jìng)爭(zhēng)臨時(shí)性資源雖然競(jìng)爭(zhēng)的資源類型有區(qū)別，但是產(chǎn)生死鎖的原理相同，都出現(xiàn)了“進(jìn)程資源”環(huán)路。n如圖3-13，3-14.94進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程運(yùn)行具

46、有異步性特征，多個(gè)并發(fā)進(jìn)程的推進(jìn)順序有多種可能性。n如果進(jìn)程以某種順序推進(jìn)，不會(huì)引起死鎖，稱這種推進(jìn)順序是合法的n否則稱進(jìn)程的推進(jìn)順序非法（會(huì)引起死鎖）w在進(jìn)程推進(jìn)示意圖中，推進(jìn)路線進(jìn)入不安全區(qū)。95死鎖產(chǎn)生的必要條件: :1.互斥條件：進(jìn)程對(duì)分配到的資源進(jìn)行排他性使用。2.請(qǐng)求和保持條件（部分分配條件）：進(jìn)程在等待一新資源時(shí)繼續(xù)占有已分配的資源。3.不剝奪條件：不能強(qiáng)行剝奪進(jìn)程擁有的資源。4.環(huán)路等待條件：存在“進(jìn)程資源”的環(huán)形鏈，鏈中的每一個(gè)進(jìn)程已獲得的資源同時(shí)被鏈中的下一個(gè)進(jìn)程所請(qǐng)求。 96u 預(yù)防死鎖：u指通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來(lái)防止死鎖

47、的發(fā)生。u 避免死鎖：u指在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。u 檢測(cè)死鎖：u允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖，但可設(shè)置檢測(cè)機(jī)構(gòu)及時(shí)檢測(cè)死鎖的發(fā)生，并采取適當(dāng)措施加以清除。u 解除死鎖：u當(dāng)檢測(cè)出死鎖后，便采取適當(dāng)措施將進(jìn)程從死鎖狀態(tài)中解脫出來(lái)。處理死鎖的基本方法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理984.3 連續(xù)分配方式連續(xù)分配方式連續(xù)分配方式：為一個(gè)用戶程序分配一個(gè)連續(xù)的存儲(chǔ)空間。1.1.單一連續(xù)分配2.2.固定分區(qū)分配3.3.動(dòng)態(tài)分區(qū)分配4.4.動(dòng)態(tài)重定位分區(qū)分配99單一連續(xù)分配單一連續(xù)分配最簡(jiǎn)單，只適用于單用戶、單任務(wù)系統(tǒng)內(nèi)存分為兩部分：n系統(tǒng)區(qū)w

48、內(nèi)存的低址部分，僅供OS使用n用戶區(qū)w系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，供用戶程序使用系統(tǒng)區(qū)用戶區(qū)0mn地址：地址：0m內(nèi)存緩沖區(qū)-打印機(jī)，打印 重復(fù)上述過程，直至隊(duì)列為空，該進(jìn)程阻塞自己，再有打印請(qǐng)求時(shí)才被喚醒163SPOOLing技術(shù)技術(shù)特點(diǎn)n提高I/O速度w對(duì)低速I/O的操作，演變?yōu)閷?duì)磁盤(輸入井、輸出井)的操作n獨(dú)占設(shè)備共享設(shè)備w沒有分配實(shí)際設(shè)備，只是分配了輸入井或輸出井中的存儲(chǔ)區(qū)和I/O請(qǐng)求表n實(shí)現(xiàn)虛擬設(shè)備功能w可使多個(gè)進(jìn)程以獨(dú)占方式同時(shí)使用一臺(tái)物理設(shè)備，即一臺(tái)物理設(shè)備被虛擬為多臺(tái)邏輯設(shè)備1646.6 磁盤存儲(chǔ)器的管理磁盤存儲(chǔ)器的管理主要任務(wù)：設(shè)法改善磁盤系統(tǒng)的性能1.磁盤性能簡(jiǎn)述2.磁盤調(diào)

49、度3.磁盤高速緩存4.提高磁盤I/O速度的其他方法5.廉價(jià)磁盤冗余陣列165磁盤調(diào)度磁盤調(diào)度目標(biāo)：減少尋道時(shí)間1. FCFS（Fisrt Come First Second）n特點(diǎn)：簡(jiǎn)單，尋道時(shí)間長(zhǎng)，相當(dāng)于隨機(jī)訪問模式。2. SSTF（最短尋道優(yōu)先）166 FCFS調(diào)度算法調(diào)度算法 SSTF調(diào)度算法調(diào)度算法100道開始道開始被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動(dòng)距離移動(dòng)距離5545583391918219072160701501038112184146平均尋道長(zhǎng)度：平均尋道長(zhǎng)度：55.3100道開始道開始被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動(dòng)距離移動(dòng)距離901058325533916381

50、18201501321601018424平均尋道長(zhǎng)度：平均尋道長(zhǎng)度：27.5167磁盤調(diào)度磁盤調(diào)度3. 掃描(SCAN)算法nSSTF存在進(jìn)程“饑餓”現(xiàn)象nSCAN算法w采用SSTF時(shí)，考慮當(dāng)前移動(dòng)方向考慮當(dāng)前移動(dòng)方向，一直移動(dòng)到最外/內(nèi)層磁道時(shí)，折返，進(jìn)行反方向移動(dòng)，可避免饑餓現(xiàn)象w尋道方向：，里外，外里，；4. 循環(huán)掃描CSCAN（圖9-5）n一個(gè)方向讀完，不是象SCAN那樣反向掃描，而是循環(huán)掃描n尋道方向：，里外，里外，；或者相反n訪問延遲：從2T減小為T+SmaxwT：?jiǎn)蜗驋呙杷写诺赖臅r(shí)間wSmax：從最里直接移動(dòng)到最外(或者相反)的時(shí)間168SCAN調(diào)度算法調(diào)度算法 CSCAN調(diào)度

51、算法調(diào)度算法100道開始，增加方向道開始，增加方向被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動(dòng)距離移動(dòng)距離1505016010184249094583255339163811820平均尋道長(zhǎng)度：平均尋道長(zhǎng)度：27.8100道開始，增加方向道開始，增加方向被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動(dòng)距離移動(dòng)距離15050160101842418166382039155165839032平均尋道長(zhǎng)度：平均尋道長(zhǎng)度：35.8169磁盤調(diào)度磁盤調(diào)度5. NStepSCAN和FSCAN算法。NStepSCAN算法n將磁盤請(qǐng)求隊(duì)列分為長(zhǎng)為N的子隊(duì)列m個(gè)，按FCFS處理各子隊(duì)列，對(duì)每個(gè)子隊(duì)列按SCAN處理。wN=1

52、時(shí)，退化為FCFSwN很大時(shí)，性能接近SCAN磁臂粘著(Armstickiness)：由于連續(xù)對(duì)某磁道訪問引起的壟斷訪問NStepSCAN算法可避免粘著現(xiàn)象FSCAN算法nNStepSCAN算法的簡(jiǎn)化，只有兩個(gè)隊(duì)列n一個(gè)是當(dāng)前掃描中的隊(duì)列n一個(gè)是掃描期間新出現(xiàn)的磁盤I/O請(qǐng)求的隊(duì)列第七章第七章 文件管理文件管理171文件管理的任務(wù)和功能文件管理的任務(wù)和功能任務(wù)任務(wù)n對(duì)文件和文件系統(tǒng)進(jìn)行管理，方便用戶使用，對(duì)文件和文件系統(tǒng)進(jìn)行管理，方便用戶使用，并保證文件的安全性并保證文件的安全性基本功能基本功能n文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理n目錄管理目錄管理n文件讀文件讀/寫管理和保護(hù)寫管理和保護(hù)1727.1 文件和文件系統(tǒng)文件和文件系統(tǒng)1.文件、記錄和數(shù)據(jù)項(xiàng)2.文件類型和文件系統(tǒng)模型173數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是文件系統(tǒng)中最低級(jí)的數(shù)據(jù)組織形式基本數(shù)據(jù)項(xiàng)n可命名的最小邏輯單位(原子數(shù)據(jù))，也稱數(shù)據(jù)元素、字段n用于描述一個(gè)對(duì)象的某種屬性n具有“名”、“型”和“值”組合數(shù)據(jù)項(xiàng)n由若干個(gè)基本數(shù)據(jù)項(xiàng)組成，簡(jiǎn)稱組項(xiàng)174記錄記錄記錄：一組相關(guān)數(shù)據(jù)項(xiàng)(值)的集合，是關(guān)于某對(duì)象的若干屬性的描述關(guān)鍵字(key)：能唯一地標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)（一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的組合）175文件文件文件：指由創(chuàng)建者定義、具有文件名