【正文】 程隊列的鏈接 ? 在多道程序設(shè)計的系統(tǒng)中往往會同時創(chuàng)建多個進(jìn)程。 撤消原語流圖 進(jìn)程的阻塞與喚醒 1. 引起進(jìn)程阻塞和喚醒的事件 有下述幾類事件會引起進(jìn)程阻塞或被喚醒 。 進(jìn)程樹 D E F GB CI J K MALH父進(jìn)程 祖先 子進(jìn)程 2． 引起創(chuàng)建進(jìn)程的事件 ? 用戶登錄 分時 OS ? 作業(yè)調(diào)度 批處理 OS ? 提供服務(wù) ? 應(yīng)用請求 系統(tǒng)內(nèi)核創(chuàng)建 應(yīng)用程序自己創(chuàng) 建 3． 進(jìn)程的創(chuàng)建 (Creation of Process) 調(diào)用進(jìn)程 創(chuàng)建原語 Creat( )按下述步驟創(chuàng)建一個新進(jìn)程 。 編譯程序和操作系統(tǒng)程序通常都是 可再入 程序，能同時被不同用戶調(diào)用而構(gòu)成不同的進(jìn)程。 例 2：解答 (1) 在不支持進(jìn)程運行環(huán)境的操作系統(tǒng)下 ， 依次執(zhí)行程序 C、程序 D，可以看到，先是打印機不停地打印工資報表，打完后，接著運行程序 C，不停地計算，最后顯示所計算的結(jié)果。 進(jìn)程及狀態(tài)的例子 ?醫(yī)院體檢 ?體檢表 —— 程序 ?體檢過程 —— 進(jìn)程 ?體檢中等待、就緒、運行對應(yīng)進(jìn)程的三種狀態(tài) 問題：單 CPU系統(tǒng)中，如果系統(tǒng)中有 N個進(jìn)程， ?運行進(jìn)程最多幾個，最少幾個？ ?就緒進(jìn)程最多幾個，最少幾個？ ?等待進(jìn)程最多幾個，最少幾個？ 解答： 運行進(jìn)程最多 1個，最少 0個； 就緒進(jìn)程最多 N1個，最少 0個； 等待進(jìn)程最多 N個，最少 0個； 小問題 下列進(jìn)程狀態(tài)變化中， ______變化是不可能產(chǎn)生的？ A 運行－ 就緒 B 運行 － 阻塞 C 阻塞 － 運行 D 阻塞 － 就緒 其他教材給出的進(jìn)程的狀態(tài)變圖 運 行 等 待 就 緒 服務(wù)請求 (請求 I/O等 ) 服務(wù)完成 / 事件來到 進(jìn)程調(diào)度 時間片到 討論進(jìn)程狀態(tài)變遷 運 行 等 待 就 緒 變遷 1 變遷 4 變遷 3 變遷 2 變遷 1—— 變遷 3？ 變遷 4—— 變遷 3？ 問題：如果操作系統(tǒng)里面存在多個進(jìn)程，找出所有的可能狀態(tài)轉(zhuǎn)換。 2) 執(zhí)行狀態(tài) (Running） 進(jìn)程已獲得 CPU，其程序正在執(zhí)行。 （ 2） 用戶進(jìn)程 執(zhí)行用戶程序的進(jìn)程 。而程序則不是。 ? 進(jìn)程的定義 較典型的進(jìn)程定義有： (1) 進(jìn)程是程序的一次 執(zhí)行 。N:=N+1。 } ? 程序 A和 B以不同的速度運行。 程序的順序執(zhí)行及其特征 程序的并發(fā)執(zhí)行及其特征 1． 程序的并發(fā)執(zhí)行 若干個程序段同時在系統(tǒng)中運行，這些程序段的執(zhí)行在時間上是 重疊 的，一個程序段的執(zhí)行尚未結(jié)束，另一個程序段的執(zhí)行已經(jīng)開始，即使這種重疊是很小的一部分，也稱這幾個程序段是 并發(fā)執(zhí)行 的。具體表現(xiàn)為： ? 提高了處理器的利用率； ? 充分利用外圍設(shè)備資源： ? 發(fā)揮了處理器與外圍設(shè)備以及外圍設(shè)備之間的并行工作能力； 從總體上說，采用多道程序設(shè)計技術(shù)后，可以有效地提高系統(tǒng)中資源的利用率，增加單位時間內(nèi)的算題量，從而提高了吞吐率。 、 多道程序設(shè)計（領(lǐng)會） ? 讓多個計算問題同時裝入一個計算機系統(tǒng)的主存儲器并行執(zhí)行，這種設(shè)計技術(shù)稱“多道程序設(shè)計”，這種計算機系統(tǒng)稱“多道程序設(shè)計系統(tǒng)” 或簡稱“多道系統(tǒng)”。 程序一旦開始執(zhí)行 ， 其執(zhí)行結(jié)果不受外界因素影響 。 ? 程序 A每執(zhí)行一次時，都要做 N:=N+1操作； ? 程序 B每執(zhí)行一次時，都要執(zhí)行 print(N)操作，然后再將 N置成 “ 0”。N值分別為 n+1， n+1， 0。 N值分別為 n， n+1， 0。 ? 程序是靜止的，進(jìn)程是動態(tài)的。如果我們再打開一個記事本程序的窗口，就會建立另一個進(jìn)程，此時運行的是同一個程序，但存在兩個進(jìn)程，第二個窗口中的編輯內(nèi)容就是第二個進(jìn)程的數(shù)據(jù)集。 進(jìn)程狀態(tài)（領(lǐng)會） ? 進(jìn)程的三種基本狀態(tài)： ? 等待態(tài)：等待某個事件的完成； ? 就緒態(tài)：等待系統(tǒng)分配處理器以便運行； ? 運行態(tài)：占有處理器正在運行。 ? 運行態(tài) → 就緒態(tài) 不是由于自身原因，而是由外界原因使運行狀態(tài)的進(jìn)程讓出處理器，這時候就變成就緒態(tài)。 (1) 在不支持進(jìn)程運行環(huán)境的操作系統(tǒng)下運行 (2) 在支持進(jìn)程運行環(huán)境的操作系統(tǒng)下運行 例 2：設(shè)有 2個程序 ， 程序 C是打印工資報表的程序 ， 程序D是計算 1000以內(nèi)所有素數(shù)并顯示最后結(jié)果程序 。 一個能被多個用戶同時調(diào)用的程序稱做 可再入 的程序。 作用： (1)記錄進(jìn)程的有關(guān)信息，以便操作系統(tǒng)的進(jìn)程調(diào)度程序?qū)M(jìn)程進(jìn)行調(diào)度。 (3) 若該進(jìn)程還有子孫進(jìn)程 ， 還應(yīng)將其所有子孫進(jìn)程予以終止 ， 以防它們成為不可控的進(jìn)程 。 3． 進(jìn)程喚醒過程 ? 當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時 ， 則由有關(guān)進(jìn)程調(diào)用 喚醒原語 wakeup( )， 將等待該事件的進(jìn)程喚醒 。 等待隊列：把等待資源或等待某些事件的進(jìn)程排列的隊列 ? 進(jìn)程的入隊和出隊。 A,標(biāo)識信息：包括用戶標(biāo)識和進(jìn)程標(biāo)識。 0號進(jìn)程又稱為交換進(jìn)程。 d,按父進(jìn)程中 p_size所示的長度為子進(jìn)程申請分配內(nèi)存。當(dāng)父進(jìn)程釋放后， wait繼續(xù)執(zhí)行，再從磁盤對換區(qū)中把子進(jìn)程的 user結(jié)構(gòu)讀入主存，釋放 user在對換區(qū)中所占的空間，然后把user存放的時間信息加在本進(jìn)程的 user結(jié)構(gòu)中，再釋放主緩沖去，把子進(jìn)程子 proc中的表項刪除。 意義：使系統(tǒng)運行效率提高。 ? 若有中斷發(fā)生，保護斷點信息 每個程序都有一個程序狀態(tài)字 (PSW)來反映本狀態(tài)的執(zhí)行狀態(tài)，如基本狀態(tài)、中斷碼和中斷屏蔽位等內(nèi)容。 中斷優(yōu)先級和中斷屏蔽（識記） 中斷優(yōu)先級是硬件設(shè)計時確定的。于是，當(dāng)中斷裝置檢查到有中斷事件后，便去查看 PSW中中斷屏蔽標(biāo)志，如果沒有屏蔽就響應(yīng)該中斷；否則，暫時不響應(yīng)該中斷，待屏蔽標(biāo)志消除后再響應(yīng)?？s短響應(yīng)時間 ?處理機是計算機系統(tǒng)中的重要資源 ?處理機調(diào)度算法對整個計算機系統(tǒng)的綜合性能指標(biāo)有重要影響 ?不同的 OS，處理機管理的策略不同 ?可把處理機調(diào)度分成三個層次： ? 高級調(diào)度 ? 中級調(diào)度 ? 低級調(diào)度 處理機調(diào)度的層次 處理器調(diào)度（領(lǐng)會） 處理機調(diào)度的層次 ?高級調(diào)度 （ 宏觀調(diào)度、作業(yè)調(diào)度、長程調(diào)度 ） 主要功能：根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。 (2) 作業(yè)步 (Job Step)。 ② 后備狀態(tài) ：作業(yè)的全部信息都已輸入，并存放在磁盤中等待運行。 1． 低級調(diào)度的功能 低級調(diào)度用于決定就緒隊列中的哪個進(jìn)程 (或內(nèi)核級線程 )應(yīng)獲得處理機 ， 然后再由分派程序執(zhí)行把處理機分配給該進(jìn)程的具體操作 。 當(dāng)對處理機進(jìn)行切換時，會發(fā)生 兩對 上下文切換 操作。 ? 缺點：難以滿足緊急任務(wù)的要求 —— 立即執(zhí)行 2) 搶占 方式 (Preemptive Mode) ? 當(dāng)一個進(jìn)程正在運行時，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進(jìn)程。 批處理作業(yè)的調(diào)度算法 ?設(shè)計調(diào)度算法的原則 ?公平性 ?平衡資源利用 ?極大的流量 ? 周轉(zhuǎn)時間 ：從作業(yè)被提交給系統(tǒng) Si（進(jìn)入輸入井）開始，到作業(yè)完成為止 Ei的這段時間間隔。 在此，我們通過一個例子來說明采用 FCFS調(diào)度算法時的調(diào)度性能。 HRN （ Highest Responseratio Next）是 對 FCFS和 SJF方式的一種 綜合平衡 。 4 優(yōu)先調(diào)度算法 (1)優(yōu)先權(quán)調(diào)度算法的類型 ? 為了照顧緊迫型作業(yè) /進(jìn)程，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。 改變進(jìn)程優(yōu)先級的方式： ??? 線形優(yōu)先級調(diào)度策略 新創(chuàng)建的進(jìn)程按 FCFS方式排成就緒隊列，優(yōu)先級以 a的速率增加，正在執(zhí)行的進(jìn)程優(yōu)先級以 b的速率下降。進(jìn)程的優(yōu)先數(shù)可以固定的，也可隨進(jìn)程執(zhí)行過程動態(tài)變化。 ?時間片輪轉(zhuǎn)法 1) 基本原理 將 CPU 的處理時間分成固定大小的時間片，系統(tǒng)將所有就緒進(jìn)程按 先來先服務(wù) 的原則排成隊列。時間片輪轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊列，每次總選擇該隊列中第一個進(jìn)程占用處理器，但規(guī)定只能使用一個時間片，如該進(jìn)程尚未完成，則排入隊尾，等待下一個供它使用的時間片。 圖 多級反饋隊列調(diào)度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至C P U至C P U至C P U至C P U( 時間片： S1＜ S2＜ S3)優(yōu)先級：隊列 1隊列 2隊列 3… 隊列 n Si=2Si1 時間片到 時間片到 時間片到 時間片到 ?? 多級反饋輪轉(zhuǎn)法 ?設(shè)置多個就緒隊列 ,每個隊列賦予不同地優(yōu)先級。 思考：如下調(diào)度用的進(jìn)程狀態(tài)變遷圖，有幾個隊列？調(diào)度算法和調(diào)度效果如何？ 運行 低優(yōu)先就緒 高優(yōu)先就緒 等待 首先選擇100ms 其次選擇500ms 請求 I/O I/O完成 超時間片 隊列結(jié)構(gòu) ? I/O等待隊列 —— 一個進(jìn)程如果請求 I/O，則進(jìn)入 I/O等待隊列。 若采用非時間片輪轉(zhuǎn)算法，則平均周轉(zhuǎn)時間的計算公式為： 平均周轉(zhuǎn)時間 ＝ （ 3T1 + 2T2 ＋ T3） / 3 = T1 + 2T2/3 + T3/3； 若采用時間片輪轉(zhuǎn)算法，設(shè)每個進(jìn)程需要 N1,N2,N3個時間片可以運行完，則周轉(zhuǎn)時間為 : 其中 Ts為時間片大小 平均周轉(zhuǎn)時間 ＝ 顯然可見，采用非時間片輪轉(zhuǎn)的平均周轉(zhuǎn)時間小于采用時間片輪轉(zhuǎn)算法，在各種非時間片輪轉(zhuǎn)的線程調(diào)度算法中，保證平均周轉(zhuǎn)時間最小的條件為 T1 T 2 T3，即遵循最短作業(yè)優(yōu)先的思想調(diào)度進(jìn)程運行。 ?簡答題：進(jìn)程調(diào)度中“可搶占”和“非搶占”兩種方式，哪一種系統(tǒng)的開銷更大？為什么？ ?簡答題：簡述進(jìn)程調(diào)度的功能。（ 3）一個進(jìn)程從等待狀態(tài)變成了就緒狀態(tài)（ 4）一個進(jìn)程完成工作后被撤消。 ? D C B BD D BD ? 進(jìn)程控制塊 系統(tǒng)進(jìn)程 用戶進(jìn)程 就緒態(tài) ? 這兩種方式下，“可搶占”方式的系統(tǒng)開銷更大。 A、成批處理作業(yè) B、分時多用戶 C、設(shè)置管、目態(tài) D、處理機與外設(shè)并行操作 ? 進(jìn)程有多個狀態(tài)，不會發(fā)生的狀態(tài)轉(zhuǎn)換是（ ） A、就緒態(tài)轉(zhuǎn)換為運行態(tài) B、運行態(tài)轉(zhuǎn)換為就緒態(tài) C、就緒態(tài)轉(zhuǎn)換為等待態(tài) D、等待態(tài)轉(zhuǎn)換為就緒態(tài) ? 進(jìn)程調(diào)度算法有多種，不是進(jìn)程調(diào)度