【文章內(nèi)容簡(jiǎn)介】 初值為 0 或某個(gè)正整數(shù)。程序員考試同步輔導(dǎo)(上午科目 )(第 2 版)661信號(hào)量 S 的物理意義：S ≥0 表示某資源的可用數(shù)，若 S0，則其絕對(duì)值表示阻塞隊(duì)列中等待該資源的進(jìn)程數(shù)。除了設(shè)置初值外，對(duì)信號(hào)量只能進(jìn)行特殊的操作：P 操作和 V 操作。P 操作和 V 操作都是不可分割的原子動(dòng)作，也稱為原語(yǔ)，其中 P 操作表示申請(qǐng)一個(gè)資源，V 操作表示釋放一個(gè)資源。P 操作和 V 操作都是原語(yǔ)。利用信號(hào)量 S 的取值表示共享資源的使用情況。在使用時(shí)，把信號(hào)量 S 放在進(jìn)程運(yùn)行的環(huán)境中，賦予其不同的初值，并在其上實(shí)施 P 操作和 V 操作，以實(shí)現(xiàn)進(jìn)程間的同步與互斥。P 操作和 V 操作的定義如下。P(S)：①S=S1；②若 S0，則該進(jìn)程進(jìn)入 S 信號(hào)量的隊(duì)列中等待。V(S)：①S=S+1 ；②若 S≤0，則釋放 S 信號(hào)量隊(duì)列上的一個(gè)等待進(jìn)程，使之進(jìn)入就緒隊(duì)列。當(dāng) S0 時(shí)，表示還有資源可以分配；當(dāng) S0 時(shí)，其絕對(duì)值表示信號(hào)量等待隊(duì)列中進(jìn)程的數(shù)目。每執(zhí)行一次 P 操作，意味著要求分配一個(gè)資源；每執(zhí)行一次 V 操作，就意味著釋放一個(gè)資源。2) 利用 P 操作和 V 操作實(shí)現(xiàn)進(jìn)程的互斥令信號(hào)量 mutex 的初值為 l，進(jìn)入臨界區(qū)時(shí)執(zhí)行 P 操作，退出臨界區(qū)時(shí)執(zhí)行 V 操作，于是臨界區(qū)就改寫(xiě)成下列形式的代碼段：P(mutex)。臨界區(qū)V(mutex)。由于 mutex 初值為 1，P 、V 是原子操作，可以實(shí)現(xiàn)互斥。3. 高級(jí)通信原語(yǔ)P 操作和 V 操作是用來(lái)協(xié)調(diào)進(jìn)程間關(guān)系的，編程較困難、效率低，而且沒(méi)有信息交換，故常稱為低級(jí)通信原語(yǔ)。交換的信息量多時(shí)要引入高級(jí)通信原語(yǔ)，進(jìn)程高級(jí)通信的類型主要有如下幾種。(1) 共享存儲(chǔ)系統(tǒng)：相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或存儲(chǔ)區(qū)，以實(shí)現(xiàn)進(jìn)程之間的通信。(2) 消息傳遞系統(tǒng)：進(jìn)程間的數(shù)據(jù)交換以消息為單位，程序員直接利用系統(tǒng)提供的一組通信命令(原語(yǔ))來(lái)實(shí)現(xiàn)通信。如 Send(A)、Receive( A)。(3) 管道通信：所謂管道，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程，以實(shí)現(xiàn)它們之間通信的共享文件(pipe 文件)。向管道(共享文件) 提供輸入的發(fā)送進(jìn)程(即寫(xiě)進(jìn)程) ，以字符流的形式將大量的數(shù)據(jù)送入管道；而接受進(jìn)程可從管道接受大量的數(shù)據(jù)。由于通信是采用管道的方式，所以叫管道通信。 進(jìn)程調(diào)度進(jìn)程調(diào)度即處理機(jī)調(diào)度，它的主要功能是確定在什么時(shí)候分派處理機(jī)，并確定分給哪一個(gè)進(jìn)程。在一些操作系統(tǒng)中，一個(gè)作業(yè)從提交到完成需要經(jīng)歷高、中、低 3 級(jí)調(diào)度。? 高級(jí)調(diào)度：又稱“長(zhǎng)調(diào)度”、“作業(yè)調(diào)度”或“接納調(diào)度”，它決定處于輸入池Error! No text of specified style in document.67中的哪個(gè)后備作業(yè)可以調(diào)入主系統(tǒng)做好運(yùn)行的準(zhǔn)備，成為一個(gè)或一組就緒進(jìn)程。系統(tǒng)中一個(gè)作業(yè)只需經(jīng)過(guò)一次高級(jí)調(diào)度。? 中級(jí)調(diào)度：又稱“中程調(diào)度”或“對(duì)換調(diào)度”，它決定處于交換區(qū)中的哪個(gè)就緒進(jìn)程可以調(diào)入內(nèi)存，以便直接參與對(duì) CPU 的競(jìng)爭(zhēng)。在內(nèi)存資源緊張時(shí)，為了將進(jìn)程調(diào)入內(nèi)存，必須將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程調(diào)至交換區(qū)，以便為調(diào)入進(jìn)程騰出空間。? 低級(jí)調(diào)度：又稱“短程調(diào)度”或“進(jìn)程調(diào)度”，它決定處于內(nèi)存中的哪個(gè)就緒進(jìn)程可以占用 CPU，是操作系統(tǒng)中最活躍、最重要的調(diào)度程序，對(duì)系統(tǒng)的影響很大。1. 調(diào)度方式調(diào)度方式是指當(dāng)有更高優(yōu)先級(jí)的進(jìn)程到來(lái)時(shí)如何分配 CPU。調(diào)度方式分為可剝奪式和不可剝奪式兩種?？蓜儕Z式是指當(dāng)有更高優(yōu)先級(jí)的進(jìn)程到來(lái)時(shí)，強(qiáng)行將正在運(yùn)行的進(jìn)程所占用的 CPU 分配給高優(yōu)先級(jí)的進(jìn)程；不可剝奪式是指當(dāng)有更高優(yōu)先級(jí)的進(jìn)程到來(lái)時(shí)，必須等待正在運(yùn)行的進(jìn)程自動(dòng)釋放占用的 CPU，然后將 CPU 分配給高優(yōu)先級(jí)的進(jìn)程。2. 進(jìn)程調(diào)算法常用的進(jìn)程調(diào)度算法有：先來(lái)先服務(wù)、時(shí)間片輪轉(zhuǎn)、優(yōu)先級(jí)調(diào)度和多級(jí)反饋調(diào)度算法。1) 先來(lái)先服務(wù)先來(lái)先服務(wù)(FCFS)是按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，分配 CPU。即每當(dāng)進(jìn)入進(jìn)程調(diào)度時(shí)，總是將就緒隊(duì)列隊(duì)首的進(jìn)程投入運(yùn)行。FCFS 的特點(diǎn)比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)；有利于 CPU 繁忙的作業(yè)，而不利于輸入/輸出繁忙的作業(yè)。2) 時(shí)間片輪轉(zhuǎn)FCFS 算法主要用于宏觀調(diào)度，時(shí)間片輪轉(zhuǎn)算法主要用于微觀調(diào)度，通過(guò)時(shí)間片輪轉(zhuǎn)，提高進(jìn)程并發(fā)性和響應(yīng)時(shí)間，從而提高資源利用率。時(shí)間片輪轉(zhuǎn)的實(shí)現(xiàn)過(guò)程是將系統(tǒng)中所有的就緒進(jìn)程按照 FCFS 原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將 CPU 分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長(zhǎng)度從幾毫秒到幾百毫秒。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷，調(diào)度程序據(jù)此暫停當(dāng)前運(yùn)行進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓 CPU(如阻塞) 。時(shí)間片長(zhǎng)度的確定主要考慮以下 4 個(gè)方面。? 時(shí)間片長(zhǎng)度變化的影響：時(shí)間片過(guò)長(zhǎng)，退化為 FCFS 算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，造成響應(yīng)時(shí)間長(zhǎng)；時(shí)間片過(guò)短，用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，系統(tǒng)效率降低，同樣造成響應(yīng)時(shí)間增長(zhǎng)。? 對(duì)響應(yīng)時(shí)間的要求：T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目) q(時(shí)間片)。? 就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越小。? 系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入在一個(gè)時(shí)間片內(nèi)能處理完，否則會(huì)使響應(yīng)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。3) 優(yōu)先級(jí)調(diào)度程序員考試同步輔導(dǎo)(上午科目 )(第 2 版)681優(yōu)先級(jí)調(diào)度分為靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)兩種。? 靜態(tài)優(yōu)先級(jí)：進(jìn)程的優(yōu)先級(jí)是在創(chuàng)建時(shí)就已確定好了 r ，直到進(jìn)程終止都不會(huì)改變。確定優(yōu)先級(jí)的依據(jù)主要有：進(jìn)程類型(系統(tǒng)進(jìn)程優(yōu)先級(jí)較高) 、對(duì)資源的需求(對(duì) CPU 和內(nèi)存需求較少的進(jìn)程優(yōu)先級(jí)較高 )、用戶要求( 緊迫程度和付費(fèi)多少)。? 動(dòng)態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)賦予一個(gè)優(yōu)先級(jí)，在進(jìn)程運(yùn)行過(guò)程中還可以改變，以便獲得更好的調(diào)度性能。進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)可能會(huì)降低到出讓 CPU 為止。4) 多級(jí)反饋調(diào)度多級(jí)反饋調(diào)度算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法的綜合與發(fā)展。其優(yōu)點(diǎn)是：照顧了短進(jìn)程、提高了系統(tǒng)吞吐量、縮短了平均周轉(zhuǎn)時(shí)間；照顧輸入/輸出型進(jìn)程，獲得較好的輸入/輸出設(shè)備利用率和縮短響應(yīng)時(shí)間；不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)優(yōu)先級(jí)。Error! No text of specified style in document.69 死鎖1. 死鎖的基本概念當(dāng)若干個(gè)進(jìn)程競(jìng)爭(zhēng)使用資源時(shí)，可能每個(gè)進(jìn)程要求的資源都已被另一進(jìn)程占用，于是也就沒(méi)有一個(gè)進(jìn)程能繼續(xù)運(yùn)行，這種情況稱為死鎖。例如，P1 進(jìn)程占有資源 R1，P2 進(jìn)程占有資源 R2，這時(shí)，P1 又需要資源 R2，P2 也需要資源 R1，它們?cè)诘却龑?duì)方占有的資源時(shí)，又不會(huì)釋放自己占有的資源，因而使雙方都進(jìn)入了無(wú)限等待狀態(tài)。死鎖是系統(tǒng)的一種出錯(cuò)狀態(tài)，不僅浪費(fèi)大量的系統(tǒng)資源，甚至?xí)?dǎo)致整個(gè)系統(tǒng)的崩潰，所以死鎖是應(yīng)該盡量預(yù)防和避免的。系統(tǒng)發(fā)生死鎖時(shí)，死鎖進(jìn)程的個(gè)數(shù)至少為兩個(gè)；所有死鎖進(jìn)程都有等待資源，其中至少有兩個(gè)進(jìn)程已占有資源。產(chǎn)生死鎖的情況主要有：進(jìn)程推進(jìn)順序不當(dāng)；同類資源分配不當(dāng)；PV 操作使用不當(dāng)。2. 產(chǎn)生死鎖的 4 個(gè)必要條件產(chǎn)生死鎖的原因：一是系統(tǒng)提供的資源數(shù)量有限，不能滿足每個(gè)進(jìn)程的使用；二是多道程序運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合理。發(fā)生死鎖必須同時(shí)具備下述 4 個(gè)條件。? 互斥：進(jìn)程互斥使用資源，任意時(shí)刻一個(gè)資源只為一個(gè)進(jìn)程所獨(dú)占，其他進(jìn)程若請(qǐng)求一個(gè)已被占用的資源，只能等待占用者釋放后才能使用。? 不可剝奪(不可搶占)：進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行剝奪，而只能由獲得該資源的進(jìn)程自己釋放。? 請(qǐng)求保持：進(jìn)程每次申請(qǐng)它所需要的一部分資源，在申請(qǐng)新的資源的同時(shí)，繼續(xù)占用已分配到的資源。零星地請(qǐng)求資源，即已獲得部分資源后再次請(qǐng)求資源時(shí)被阻塞。? 循環(huán)等待：在進(jìn)程資源有向圖中存在一個(gè)進(jìn)程環(huán)路，環(huán)路中每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求。進(jìn)程資源有向圖由方框、圓圈和有向邊 3 個(gè)部分組成。其中，方框表示資源，圓圈表示進(jìn)程。請(qǐng)求資源：○→□，箭頭由進(jìn)程指向資源；分配資源：○←□，箭頭由資源指向進(jìn)程。3. 解決死鎖的方法解決死鎖的方法如下。? 死鎖的預(yù)防：根據(jù)產(chǎn)生死鎖的 4 個(gè)必要條件，只要使其中之一不能成立，死鎖就不會(huì)出現(xiàn)。? 死鎖的避免：最著名的死鎖避免算法是 Dijkstra 提出的銀行家算法。? 死鎖的檢測(cè)：采用合理的死鎖檢測(cè)算法確定死鎖的存在，并識(shí)別出與死鎖有關(guān)的進(jìn)程和資源，以供系統(tǒng)采用適當(dāng)?shù)慕獬梨i的措施。? 死鎖的解除：檢測(cè)到死鎖發(fā)生后，常采用資源剝奪法和撤銷進(jìn)程法解除死鎖。 線程1. 線程的基本概念線程是比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位。在引入線程的操作系統(tǒng)中，線程是進(jìn)程程序員考試同步輔導(dǎo)(上午科目 )(第 2 版)701中的一個(gè)實(shí)體，是 CPU 調(diào)度和分派的基本單位。線程自己基本上不占用系統(tǒng)資源，只占用一點(diǎn)兒在運(yùn)行中必不可少的資源(如程序計(jì)數(shù)器、一組寄存器和棧) ，但它可與同屬一個(gè)進(jìn)程的其他線程共享該進(jìn)程所占用的全部資源。相應(yīng)的，線程也同樣有就緒、等待和運(yùn)行3 種基本狀態(tài)。在有的系統(tǒng)中線程還有終止?fàn)顟B(tài)。2. 線程的屬性線程的屬性如下。? 每個(gè)線程都有一個(gè)唯一的標(biāo)識(shí)符和一張線程描述表。? 不同的線程可以執(zhí)行相同的程序。? 同一進(jìn)程中的各個(gè)線程共享該進(jìn)程的內(nèi)存地址空間。? 線程是處理機(jī)的獨(dú)立調(diào)度單位，多個(gè)線程是可以并發(fā)執(zhí)行的。? 線程在生命周期內(nèi)會(huì)經(jīng)歷等待狀態(tài)、就緒狀態(tài)和運(yùn)行狀態(tài)等各種狀態(tài)變化。3. 引入線程的好處傳統(tǒng)的進(jìn)程有兩個(gè)基本屬性：可擁有資源的獨(dú)立單位、可獨(dú)立調(diào)度和分配的基本單位。由于在進(jìn)程的創(chuàng)建、撤銷和切換中，系統(tǒng)必須為之付出較大的時(shí)空開(kāi)銷，因此在系統(tǒng)中所設(shè)置的進(jìn)程數(shù)目不宜過(guò)多，進(jìn)程切換的頻率不宜太高，這就限制了并發(fā)程度的提高。引入線程后，將傳統(tǒng)進(jìn)程的兩個(gè)基本屬性分開(kāi)，將線程作為調(diào)度和分配的基本單位，而將進(jìn)程作為獨(dú)立分配資源的單位。用戶可以通過(guò)創(chuàng)建線程來(lái)完成任務(wù)，以減少程序并發(fā)執(zhí)行時(shí)付出的時(shí)空開(kāi)銷。引入線程的好處主要有如下幾個(gè)。? 創(chuàng)建一個(gè)新線程花費(fèi)的時(shí)間少。? 兩個(gè)線程間切換花費(fèi)的時(shí)間少。? 由于同一進(jìn)程內(nèi)的線程共享內(nèi)存和文件，線程之間相互通信無(wú)需調(diào)用內(nèi)核，故不需要額外的通信機(jī)制，使通信更簡(jiǎn)便，信息傳送速度也更快。? 線程能獨(dú)立執(zhí)行，能充分利用和發(fā)揮處理機(jī)與外圍設(shè)備并行工作的能力。 典型例題分析例 1：在操作系統(tǒng)的進(jìn)程管理中，若系統(tǒng)中有 10 個(gè)進(jìn)程使用互斥資源 R ，每次只允許 3 個(gè)進(jìn)程進(jìn)入互斥段( 臨界區(qū)) ，則信號(hào)量 S 的變化范圍是 (26) ；若信號(hào)量 S 的當(dāng)前 值 為 2， 則 表 示 系 統(tǒng) 口 有 (27) 一 個(gè) 正 在 等 待 該 資 源 的 進(jìn) 程 。 (2022 年 下 半 年 試題 2 27)(26) A. 7～1 B. 7～3 C. 3～0 D. 3～10(27) A. 0 B. 1 C. 2 D. 3 分析：本題考查的是進(jìn)程和信號(hào)量的知識(shí)。信號(hào)量 S 的物理意義：S ≥0 表示某資源的可用數(shù)，若 S0，則其絕對(duì)值表示阻塞隊(duì)列中等待該資源的進(jìn)程數(shù)。在操作系統(tǒng)的進(jìn)程管理中，若系統(tǒng)中有 10 個(gè)進(jìn)程使用互斥 資源 R ，每次只允許 3 個(gè)進(jìn)程進(jìn)入互斥段( 臨界區(qū))，則信號(hào)量 S 的變化范圍是 7～3 ；若信號(hào)量 S 的當(dāng)前值為 2，則表示系統(tǒng)中有 2 個(gè)正在等待該資源的進(jìn)程。答案：(26)B (27)CError! No text of specified style in document.71例 2：假設(shè)系統(tǒng)中進(jìn)程的三態(tài)模型如圖 22 所示，圖中 a 和 b 處應(yīng)分別填寫(xiě)(26) ，圖中的 c 和 d 處應(yīng)分別填寫(xiě) (27) 。(2022 年上半年試題 227)圖 22 進(jìn)程三態(tài)模型圖(26) A. 時(shí)間片到、作業(yè)調(diào)度程序調(diào)度 B. 執(zhí)行了 P 操作、時(shí)間片到C. 時(shí)間片到、進(jìn)程調(diào)度程序調(diào)度 D. 時(shí)間片到，執(zhí)行了 P 操作(27) A. I/O 完成、執(zhí)行了 P 操作 B. 執(zhí)行了 P 操作、 I/O 完成C. 時(shí)間片到、執(zhí)行了 V 操作 D. 執(zhí)行了 V 操作、 I/O 完成分析：由系統(tǒng)進(jìn)程的三態(tài)模型可知， a 處應(yīng)為時(shí)間片到， b 處應(yīng)為進(jìn)程調(diào)度程序調(diào)度；c處應(yīng)為執(zhí)行了 P 操作， d 處應(yīng)為 I/O 完成。答案：(26)C (27)B例 3：已知有 6 個(gè)進(jìn)程共享一個(gè)互斥段，如果最多允許 3 個(gè)進(jìn)程同時(shí)進(jìn)入互斥段，則信號(hào)量 S 的變化范圍是 (26) ；若信號(hào)量 S 的當(dāng)前值為 2，則表示系統(tǒng)中有 (27) 個(gè)正在等待該資源的進(jìn)程。( 2022 年下半年試題 227)(26) A. 5～1 B. 3～ 3 C. 2～4 D. 2～5(27) A. 0 B. 1 C. 2 D. 3　　分析：最多允許 3 個(gè)進(jìn)程同時(shí)進(jìn)入互斥段，所以信號(hào)量 S 初值應(yīng)為 3，當(dāng) 6 個(gè)進(jìn)程依次進(jìn)入互斥段時(shí)，S 逐漸遞減，最小 為 36=3，所以變化范圍為3～3。如果 S 為2，表示系統(tǒng)中有 2 個(gè)正在等待該資源的進(jìn)程。答案：(26)B (27)C例 4：若進(jìn)程 P1 正在運(yùn)行，操作系統(tǒng)強(qiáng)行撤下 P1 所占用的 CPU，讓具有更高優(yōu)先級(jí)的 進(jìn) 程 P2 運(yùn) 行 ， 此 時(shí) P1 進(jìn)