操作系統(tǒng)復習

1、操作系統(tǒng)復習 1、 P25 復習題 1.11.81 計算機的 4 個主要組成部分 處理器 控制計算機的操作，執(zhí)行數(shù)據(jù)處理功能 內(nèi)存 存儲數(shù)據(jù)和程序 輸入 / 輸出模塊 在計算機和外部環(huán)境之間移動數(shù)據(jù) 系統(tǒng)總線 為處理器、內(nèi)存和輸入 / 輸出模塊提供通信的設施2 處理器寄存器的兩張主要類別 用戶可見寄存器 可以由機器語言應用，一般對所有程序都可用 控制和狀態(tài)寄存器 用于控制處理器操作的寄存器，大部分此類寄存器對用戶不可見 一條機器指令能夠指定的四種不同操作 處理器 - 存儲器 處理器 -I/O 數(shù)據(jù)處理 控制 中斷的定義 處理器接收到內(nèi)部或外部的信號之后，放下手頭正在做的工作，處理一些其他工作，

2、之后再回來繼續(xù)做之前的工作的行為。 多中斷的處理方式是 第一種方式是當正在處理一個中斷時，禁止再發(fā)生中斷 第二種方法是定義中斷優(yōu)先級，允許高優(yōu)先級中斷打斷低優(yōu)先級中斷處理程序的運行內(nèi)存層次的各個元素間的特征是神馬 定義寄存器 - 高速緩存 - 主存 - 外存的級別由高到低，則從上往下 每一位價格遞減、容量遞增、存取時間遞增、處理器訪問存儲器的頻率遞減神馬是高速緩存 為了解決處理器和內(nèi)存之間速度不匹配，利用局部性原理，在處理器和內(nèi)存之間提供一個容量小而速度快的存儲器，稱作高速緩存。 I/0 操作的三種技術 可編程 I/O 當處理器執(zhí)行程序并遇到一個與 I/0 相關指令時，它通過給相應的 I/0

3、模塊發(fā)命令來執(zhí)行這個指令?？删幊?I/0 要求處理器在執(zhí)行 I/0 指令后，還要定期檢查 I/O 模塊的狀態(tài)，以確定 I/O 操作是否完成。 中斷驅動 I/O 處理器給模塊發(fā) I/O 命令，然后繼續(xù)做一些其他有用的工作，當 I/O 模塊準備好與處理器交換數(shù)據(jù)時，它打斷處理器的執(zhí)行并請求服務。處理器和前面一些執(zhí)行數(shù)據(jù)傳送，再恢復正常的執(zhí)行。 DMA 直接內(nèi)存存取 當處理器要讀寫一塊數(shù)據(jù)時，它給 DMA 模塊產(chǎn)生一條命令，之后處理器繼續(xù)其他工作。 DMA 負責存儲器與 I/0 之間數(shù)據(jù)傳送。直到整個傳送完成后， DMA 再發(fā)一個中斷信號給處理器，表明傳送已完成。2、 操作系統(tǒng)概述1 實地址和虛地址

4、的區(qū)別虛地址就是虛擬存儲器中的地址，而虛擬存儲器是允許程序從邏輯的角度訪問存儲器，而不考慮物理內(nèi)存上可用的空間數(shù)量。實地址就是實際的內(nèi)存中的地址。使用中，虛地址和實地址之間存在著動態(tài)的映射，當虛地址中內(nèi)容在實際內(nèi)存中不存在時，由存儲管理硬件載入這塊內(nèi)容到內(nèi)存。2 單體內(nèi)核和微內(nèi)核的區(qū)別單體內(nèi)核指操作系統(tǒng)應提供的功能由一個大內(nèi)核提供（這些功能包括調度、文件系統(tǒng)、網(wǎng)絡、設備驅動器、存儲管理），典型情況下，這個大內(nèi)核作為一個進程實現(xiàn)，所有元素共享相同的地址空間。微內(nèi)核體系下則只給內(nèi)核分配一些最基本的功能（包括地址空間、進程間通信、基本的調度），其他操作系統(tǒng)的服務都是由運行在用戶態(tài)下與其他應用程序類似

5、的進程提供。3 執(zhí)行上下文又稱進程狀態(tài)，是操作系統(tǒng)用來管理和控制進程所需的內(nèi)部數(shù)據(jù)，包括了操作系統(tǒng)管理進程以及處理器正確執(zhí)行進程所需要的全部信息。 4 時間片輪轉在固定時間間隔內(nèi)，當前用戶被剝奪處理器的使用權，另一用戶被載入。5 特權指令只能在內(nèi)核態(tài)下由操作系統(tǒng)執(zhí)行的指令，用戶程序希望執(zhí)行特權指令時應請求操作系統(tǒng)為自己執(zhí)行。3 、進程描述和控制 五狀態(tài)進程圖形 P79 五種狀態(tài) 新建 就緒 運行 阻塞 退出 六種轉換 新建 就緒 操作系統(tǒng)準備好接納一個進程時 就緒 運行 調度器選擇一個處于就緒態(tài)的進程運行 運行 退出 進程完成 取消 運行 就緒 到“允許不中斷的最大時間段” / 被其他進程搶占

6、 / 自愿釋放 運行 阻塞 進程請求一個它必須等待的事件 阻塞 就緒 進程等待的事件發(fā)生 有掛起的進程狀態(tài)轉換圖 七種狀態(tài) 新建 就緒 運行 阻塞 就緒 / 掛起 阻塞 / 掛起 退出 十三種轉換 新建 就緒 允許進入：同上 新建 就緒 / 掛起 允許進入：內(nèi)存不足 就緒 / 掛起 就緒 激活：內(nèi)存中沒有處于就緒態(tài)的進程 / 就緒 / 掛起態(tài)的進程比所有就緒態(tài)進程優(yōu)先級都高 就緒 就緒 / 掛起 掛起：為了釋放內(nèi)存 / 處于阻塞態(tài)的高優(yōu)先級進程即將就緒 就緒 運行 分派：同上 運行 退出 釋放：同上 運行 就緒 超時（不是很準確）：同上 運行 阻塞 事件等待：同上 阻塞 就緒 事件發(fā)生：同上

7、阻塞 阻塞 / 掛起 掛起 內(nèi)存中沒有就緒進程，換出以讓出空間 阻塞 / 掛起 阻塞 激活：最高優(yōu)先級即將就緒進程被優(yōu)先激活 阻塞 / 掛起 就緒 / 掛起 事件發(fā)生：同上 運行 就緒 / 掛起 掛起：掛起隊列中高優(yōu)先級就緒，直接換入搶占 哪些事件會導致創(chuàng)建一個進程 a) 新的批處理作業(yè) b) 交互登陸 c) 操作系統(tǒng)因為提供一項服務而創(chuàng)建 d) 由現(xiàn)有進程派生 什么是交換，其目的是 交換：當內(nèi)存中沒有處于就緒態(tài)的進程時，操作系統(tǒng)就把被阻塞的進程換出到磁盤中的掛起隊列，此后，操作系統(tǒng)取出掛起隊列中的另一個進程，或者接受一個新進程的請求，將其納入到內(nèi)存中運行。 為了應對內(nèi)存中所有進程都在阻塞的情

8、況（考慮 I/O 速度比處理器慢很多），在這種情況下提升處理器運行效率。 操作系統(tǒng)創(chuàng)建一個新進程的步驟 a) 給新進程分配一個唯一的進程標識符 b) 給進程分配空間 c) 初始化 PCB d) 設置正確的連接 e) 創(chuàng)建或擴充其他數(shù)據(jù)解雇 進程切換的步驟 a) 保存處理器上下文環(huán)境 b) 更新 PCB c) 將 PCB 移至相應的隊列 d) 選擇一個進程執(zhí)行 e) 更新所選進程的 PCB f) 更新內(nèi)存管理的數(shù)據(jù)結構、 g) 恢復所選進程最近一次被切出時的上下文環(huán)境 習題 3.2 灰常有歧義的一道題目 能確認的就是 運行態(tài)最大值是 B ，就緒掛起、阻塞掛起的最大值都沒有限制 各個狀態(tài)的最小值都

9、為 0 有歧義的是內(nèi)存中的兩個狀態(tài) 就緒態(tài)和阻塞態(tài) 個人傾向于理解為題目中沒有涉及虛擬內(nèi)存（畢竟它根本沒提到操作系統(tǒng)），而我們要考慮虛擬內(nèi)存，這樣答案就是沒有限制 ( 這個和 ” 官方答案“一致，強調虛擬內(nèi)存意義，即使一個進程整個內(nèi)存都放不下，它也可以就緒的，即 C 無約束作用 ) 不過說到底，“在任何時候內(nèi)存最多容納 C 個進程”這句話就很有歧義，進程又不是一樣大的。 4 、線程、對稱多處理和微內(nèi)核 兩種線程 用戶級線程 ULT 所有有關線程的管理工作都是由應用程序實現(xiàn)，內(nèi)核意識不到線程的存在 內(nèi)核級線程 KLT 有關線程的管理工作都是由內(nèi)核實現(xiàn)，應用程序中沒有管理線程的代碼，只有一個到內(nèi)核

10、線程設施的 API 列舉使用線程相對于使用進程的好處 i) 時間花費少，具體包括創(chuàng)建新線程、線程切換、終止線程都少。 Ii) 通信便利高效，進程間通信需要內(nèi)核介入，而一個進程內(nèi)的線程共享內(nèi)存和文件，直接可以通信 列舉微內(nèi)核操作系統(tǒng)和單體內(nèi)核操作系統(tǒng) 7 個優(yōu)點和可能存在的缺點 優(yōu)點： i) 一致接口 ii) 可擴展性 iii) 靈活性 iv) 可移植性 v) 可靠性 vi) 分布式系統(tǒng)支持 vii) 適用于面向對象操作系統(tǒng)環(huán)境 可能存在的缺點： 性能問題 通過微內(nèi)核構造和發(fā)送消息，接受應答并解碼所花費的時間比進行一次系統(tǒng)調用的時間要多。5 、并發(fā)性：互斥和同步 名詞解釋 臨界區(qū) 要被多個進程訪

11、問的一個不可共享資源稱為臨界資源，使用臨界資源的那一部分程序稱為程序的臨界區(qū)。 死鎖 一組進程，當其中每一進程都因等待某一事件而被阻塞，而這事件僅可能由其他進程促發(fā)，則發(fā)生死鎖。 互斥 一次只允許一個程序在臨界區(qū)中，即一個進程在使用不可共享資源過程中一直擁有資源的控制權。 競爭條件 競爭條件發(fā)生在多個進程或線程讀寫數(shù)據(jù)時，其最終結果依賴于多個進程的指令執(zhí)行順序。2 生產(chǎn)者、消費者問題 圖 5.11基本：有一個活多個生產(chǎn)者生產(chǎn)某種類型的數(shù)據(jù)，并放置在緩沖區(qū)中，有一個消費者從緩沖區(qū)中取數(shù)據(jù)，每次取一項。要避免對緩沖區(qū)的重復操作，并保證緩沖區(qū)已滿時，生產(chǎn)者不向中加入數(shù)據(jù)（這個 MS 暫時不考慮， 5

12、.11 么）；緩沖區(qū)為空時，消費者不會移走數(shù)據(jù)。個人思考：i) 為什么要使用兩個信號量，主要是要完成兩個功能，即不重復操作 信號量 s 是做一個臨界區(qū)保護；緩沖區(qū)為空時，消費者不移走數(shù)據(jù) 信號量 delay + 計數(shù)量 n 實現(xiàn)。（這必須要用兩個信號量才夠?。﹊i) Delay + n 的實現(xiàn)方法之所以錯了， 就是由于這兩個之間存在“間隙”， n 存在的目的是作為不能多次計數(shù)的二元信號量 delay 的補充，而它的變化與 delay 變化的不同步導致了錯誤。（生產(chǎn)者程序插在了消費者 n 和 if(n = 0) semWaitB(delay) 之間）iii) 5.11 中用一般信號量 n 取代了

13、 delay + n 的組合，自然消除了這個問題iv) 在 P153 中也提到了， wait 的順序很重要。鑒于順序的隨機性，其實直接看 wait signal 的位置關系既可以發(fā)現(xiàn)會不會有死鎖3 讀者寫者問題 圖 5.22 5.23 基本：有一個多個進程共享的數(shù)據(jù)區(qū)，這個數(shù)據(jù)區(qū)可以是一個文件或一塊內(nèi)存，甚至是一組寄存器，有一些進程只讀取這個數(shù)據(jù)區(qū)中的數(shù)據(jù)，有一些只寫。條件如下： i) 任意多進程可以同時讀 ii) 一次只有一個可以寫 iii) 寫時禁止讀個人思考：i) 對于讀者優(yōu)先，比較簡單 , wsem 用于所有進程之間互斥， readcount 則避免讀進程之間互斥， x 用于對 rea

14、dcount 相關操作進行臨界區(qū)保護。ii) 寫者優(yōu)先比較實際一點，但復雜度。其實也不是很復雜x 、 readcount 、 wsem 用途不變y 用于保護 writecount, writecount 用于在有寫進程等待（至少一個即可 ）的情況下禁止讀z 則保證 rsem 上永遠只有一個讀進程在等待這么看真的不復雜，但這些信號量放置的位置 (wait signal) 要很小心4 習題 5.4 不管這是神馬語言了，直接 C 語言寫了 ( 這里認為通用的信號量 = 二元信號量 )信號量聲明Semaphore sa = 1, sb = 0 ， b_end_flg = 0;A 部分：semWait(

15、sa);if (b_end_flg = 0) semSignal(sb); Else semSignal(sa); B 部分：semWait(sb);b_end_flg = 1;semSignal(sa);. MS 所有 pv 就是 .p(sa) .v(sa) 這樣進行上鎖和解鎖。6 、死鎖和饑餓 死鎖發(fā)生的 4 個條件 :互斥 一個資源一次只能被一個進程使用持有并等待 一個進程持有已分配資源的同時，等待分配其他資源不可剝奪 資源在被進程持有時不可被強制剝奪循環(huán)等待 存在一個進程鏈，使得每一個進程至少占有一個此鏈中下一個進程所等待的資源如何預防占有并等待條件 進程一次性請求所有需要資源，并阻塞

16、直至所有請求都被滿足。如何防止不可搶占 當進程的資源請求被拒絕時，它必須釋放它最初占有的資源，如有必要，可再次一次請求這些資源；一個進程請求當前被另一進程占有的一個資源，操作系統(tǒng)可以搶占另一進程，要求它釋放資源（要求任意兩進程優(yōu)先級不同）。如何防止循環(huán)等待 定義資源類型的線性順序，如果一個進程已分配到 R 類型資源，則它后面請求的資源只能是 R 類型之后的。2 習題 6.5 畫資源分配圖 a) 暫時理解為隨便算b) 資源分配圖是對多線程中運行的一個時間點狀態(tài)的描述，所以要說明死鎖的可能性只需要構造一個這樣的時間點并畫圖（內(nèi)含閉環(huán)）即可。針對本題，其實只要畫 T1 、 T2 、 T3時間點為 T

17、1 擁有 s1 請求 s2 T2 擁有 s2 、 s4( 可不畫 ) 請求 s5 T3 擁有 s5 、 s6( 可不畫 ) 請求 s1 習題 6.6 死鎖檢測就是 189 頁的算法1） 標記 Aij 中全零行 這樣的進程不可能導致死鎖，直接標記2） 初始化 A 的計數(shù)變量 W3） 后面類似銀行家算法，就是找一個 Ri 小于 W 的，走掉（標記），釋放資源（將 Ai 加到 W 中去），回頭繼續(xù)找滿足條件 Ri最后沒有滿足條件 Ri 了，就看是不是所有進程都標記了，都標記了，就沒有問題；所有沒標記的都是要死鎖的。習題 6.11 銀行家算法總需求量 Cij 一定，總可用量 R 一定，銀行家算法的目的

18、在于規(guī)范過程中每次申請資源請求（申請資源后會導致 Aij ，即剩余請求量 Rij = Cij - Aij 和剩余資源量 A ，如存在這個 A 可以完全消化 Rij, 則為安全狀態(tài)，否則，不安全 這次的自愿申請無效）a) 基本的 b ） c) d) ( a) 中先算出 A 和 Rij 可以減少一點計算量 ) 注意題目中給出的是 R B 可以 c 不行 d 顯然不行 7 、內(nèi)存管理1 重定位，為什么要重定位進程的能力 程序被傳出到磁盤之后，重新載入內(nèi)存時可以放置在與之前不同的一個位置。（也可以說還包括壓縮） 為什么 交換的需求實際存在，而如果要求進程換入時放置的位置必須和換出前一致，會對內(nèi)存的使用

19、造成很大的限制。2 內(nèi)部碎片和外部碎片由于被裝入的數(shù)據(jù)塊小于分區(qū)的大小，導致分區(qū)內(nèi)部存在空間的浪費，這種現(xiàn)象稱為內(nèi)部碎片。動態(tài)分區(qū)隨著時間推移，導致內(nèi)存中出現(xiàn)越來越多的空洞，內(nèi)存利用率隨之下降，這種現(xiàn)象稱為外部碎片。3 邏輯地址、相對地址、物理地址 邏輯地址 與當前數(shù)據(jù)在內(nèi)存中物理分配地址無關的訪問地址，在執(zhí)行內(nèi)存訪問前必須將它轉換成物理地址。 相對地址 邏輯地址的一個特例，是相對于某些已知點的存儲單元。 物理地址（絕對地址） 數(shù)據(jù)在內(nèi)存中的實際位置4 頁、段、幀（頁框） 幀（頁框） 內(nèi)存中一個固定長度的塊 頁 一個固定長度的數(shù)據(jù)塊，儲存在二級存儲器中。數(shù)據(jù)頁可以臨時復制入內(nèi)存的頁框中 段 一

20、個變長的數(shù)據(jù)塊，儲存在二級存儲器中。整個段可以臨時復制到內(nèi)存的一個可用區(qū)域內(nèi)（分段）或者將一個段分為許多頁，將每頁單獨復制到內(nèi)存中（分頁 + 分段）5 習題 7.2 固定分區(qū)方案 最佳適應分配 最佳可得分配 （照著它說的做就行了）a) 最佳適應分配1-p0 10ms 3-p0 20ms 5-p0 15ms2-p1 5ms4-p3 15ms 6-p3 10ms 顯見需要 10+20+15 = 45ms 完成 b) 最佳可得分配1-p0 10ms 2-p1 5ms 5-p1 15ms 3-p2 20ms 4-p3 15ms 6-p3 10ms 總共需要 15+10 = 25ms 習題 7.6 動態(tài)

21、分區(qū)方案 首次適配 最佳適配 下次適配（ P215 動態(tài)分區(qū)的放置算法，很簡單） a) 首次適配80MB 20MB 120MBb) 最佳適配230MB 20MB 160MBc) 下次適配80MB 120MB 160MB習題 7.7 伙伴系統(tǒng) （ P217 的實例很容易理解） 1MBA 請求 25K A=32K 32K 64K 128K 256K 512KB 請求 500K A=32K 32K 64K 128K 256K B=512KC 請求 60K A=32K 32K C=64K 128K 256K B=512KD 請求 100K A=32K 32K C=64K D=128K 256K B=5

22、12KE 請求 30K A=32K E=32K C= 64K D=128K 256K B= 512K 釋放 A 32K E=32K C=64K D= 128K 256K B= 512KF 申請 20K F=32K E=32K C= 64K D= 128K 256K B=512K 5 個內(nèi)部碎片，分別 F 12K E 2K C 4K D 28K B 12K 習題 7.12 3 級頁表 （ P219P221 關于分頁 頁號 偏移量 頁框號）a) 頁大小 212 = 4KBb)2(32-12) = 1MBc)232 = 4GBd) 這個同意 syz 觀點，“ 6 位表示頁號”應該是頁框號，否則物理內(nèi)

23、存大小不可知2(6+12) = 256KB習題 7.14 (P222 分段 和分頁不同只是進程維護的映射信息不一樣，分頁 - 頁框號 分段 - 段長 + 段起始物理地址）a) 660 + 198b) 222 + 156c) 530 > 442 段錯誤d) 996+444e) 660 + 222 8、 虛擬內(nèi)存1 駐留集 進程執(zhí)行中的任何時候都在內(nèi)存中的部分定義為進程的駐留集2 抖動處理器的大部分時間都用于交換塊，而不是執(zhí)行指令的情況3 轉換檢測緩沖區(qū)（ TLB ） 虛擬內(nèi)存的方案中為頁表項使用的一個特殊的高速緩存。4 習題 8.2 多級頁表設計（ P236 的實例） 這里的頁表項不用考慮

24、神馬控制位之類的 頁表項 32 位 偏移量為 10 （頁大小 1KB ），則頁表項總數(shù)為 222 需要限制頁表大小為 1 個頁，即 210 ，而頁表項為 22(32 字節(jié) ) ，所以頁表中頁表項的數(shù)目限制為 28 總頁表項數(shù)位 222 ，所以需要三級頁表， 8 ， 8, 6 按照第三問，要使總的頁數(shù)最小的話，數(shù)據(jù)頁數(shù)固定，即使頁表數(shù)目最少，這時候顯然將大頁放下，小頁放上效果最好。（數(shù)學說明的話，就假設數(shù)據(jù) X 頁，三級頁表從上往下一次 x,y,z, 則有總頁表數(shù)目 X/2 z + X/2 z +y +X/2 z+y+x , 要使這個求和結果最?。ㄔ?x+y+z 結果一定情況下），顯然要保證 z

25、 >= y >= x ）所以應該 6,8,8 習題 8.4 置換算法 FIFO LRU 時鐘算法 （ P246249 的基本算法，也不復雜，注意時鐘算法要求了解到用兩位 訪問位、修改位的實現(xiàn)） a) 置換頁框 3 3 加載時間最早，根據(jù) FIFO ，優(yōu)先被換出 b) 置換頁框 1 1 訪問時間最早，即上一次訪問距現(xiàn)在時間最長，根據(jù) LRU ，換出 c) 對于時鐘算法的個人理解就是 FIFO （用循環(huán)指針掃描、置 0 訪問位，仍然有優(yōu)先換出早加載的頁的傾向） + 弱 LRU （只具備短期的記憶） 簡單模擬是時鐘算法過程的話可以用書上得 * 符號表示訪問位 如果在訪問位的基礎上引入了修

26、改位，則基本思想是最優(yōu)先換出沒有被修改的（節(jié)省寫回的成本）不過這個的細節(jié)需要了解一下（第一遍循環(huán)不置 0 訪問位，第二遍才置 0 ，第三遍指針重置，全部置 0 ） 置換頁框 1 R= 0 M = 0 最優(yōu)先 d) 置換頁框 3 即換出頁 3 ，因為在 03 四個頁中，從下面訪問串看，頁 3 最后被再次訪問到e) MS 算不要求？關于這部分要涉及工作集，稍微有點難理解，題目本身也有點問題，畢竟工作集主要用作評估，而不是直接替換 ( 那樣的話就是 FIFO 了 )習題 8.6 FIFO LRU OPT 計算缺頁次數(shù)（同上）1) 頁面大小為 100 字節(jié)，則總共有 04 五個頁引用串 0 0 1 1

27、 0 3 1 2 2 4 4 32) 200 字節(jié)，即兩個頁框 0 1 仿照書上寫法來LRU 0 0 01 01 01 F03 F13 F12 12 F42 42 F43 共 5 次缺頁FIFO 0 0 01 01 01 F31 31 F32 32 F42 42 F43 共 4 次缺頁OPT 0 0 01 01 01 F31 31 F32 32 F34 34 34 共 3 次缺頁習題 8.8 64 位系統(tǒng)，一級頁表需要多少地址a) 264 b) 252c) 頁表變得非常大（頁表項非常多），使用一級頁表成本很高（不可能在內(nèi)存中維護這么大的表）。解決：多級頁表。9 、單處理器調度 周轉時間 指一個

28、進程從提交到完成之間的時間間隔，包括實際執(zhí)行時間加上等待資源（包括處理器資源）的時間。2 各種調度策略基本： 吞吐量 每個時間單位完成的進程數(shù)目 響應時間 對于交互進程，從提交一個請求到開始接受響應之間的事件間隔w 進程到目前為止在系統(tǒng)中停留的時間 E 進程自創(chuàng)建已經(jīng)執(zhí)行的時間 s 進程所需要的總的服務時間（必須估計或用戶給出）選擇函數(shù)，如 max(w)決策模式 搶占 / 非搶占下面就是各種調度策略：（關于其中不強調是神馬意思不明，是不是很確定？不以這個為賣點 / 缺陷？） P277 表格FCFS frist-come-first-served 先來先得 / 嚴格排隊Max(w) 非搶占 不強

29、調吞吐量 響應可能很慢，畢竟排隊 開銷最小 對短進程不利，對 I/0 密集進程不利RR round robin 輪轉常數(shù)（到一定時間即可） 搶占（時間片完時） 時間片小，吞吐量低（切換開銷大） 短進程響應快 開銷最小 對各進程公平（不過公平而非照顧就會產(chǎn)生問題） 個人理解：就是有時限的排隊，當時限非常大時直接退化為排隊SPN shortest process next 最短進程優(yōu)先Min(s) 非搶占 吞吐量高 短進程響應快 開銷可能比較高（要得到 s ） 對長進程不利，甚至可能導致長進程饑餓個人理解：允許短進程插隊的排隊SRT shortest remaining time 最短剩余時間Mi

30、n(s e) 搶占 吞吐量高時間響應快 開銷可能比較高（同樣要 s ） 對長進程不利，可能饑餓個人理解：允許剩余時間最短的進程直接踢開隊首的人，很兇殘HRRN highest response rate nextmax(w+s)/s) 非搶占 吞吐量高 時間響應好 開銷可能比較高（理由同上） 很好平衡（等的多了，機會也大了）個人理解：同樣大家一起等（不算排隊了），不過用了一個科學的指標衡量等的時間的長短，以此決定誰先反饋 可以說沒有選擇函數(shù)吧 搶占（結合了時間片） 不強調吞吐量不強調響應時間 開銷可能比較高（要維護一串隊列） 可能對 I/0 密集型進程有利（因為反饋是歧視老進程和長進程的 ,I

31、/0 多就一直是“新”進程） 可能會導致長進程的饑餓，這個有一個解決方法就是增大下層隊列的時間片的長度，時間片長 = 2I i = 隊列號3 習題 9.1 9.2 給定進程的到達時間、處理時間表格，畫出調度圖（看來考試那天要帶尺 = = ， P279 ） ( 表格 MS 沒要求，不過看一下也很簡單，進程、到達時間、服務時間 Ts ， 針對每一種調度策略：完成時間，周轉時間 Tr ， Tr/Ts) 對于 9.1FCFS A3 B5 C2 D5 E5RR(q = 1) 有一個問題，就是在一個時間點一個進程超時回到隊列尾，同時一個新進程加入隊列尾，這兩者之間前后關系該怎么定 從書上看應該是新的在前，

32、超時的在后 A1 B1 A1 B1 C1 A1 B1 C1 B1 D1 B1 D1 .RR(q =4) 類似上面SPN A3 C2 B5 D5 E 5SRT A3 C2 B5 D5 E5HRRN A3 B5 C2 D5 E5反饋 (q = 1) 也有一些問題，從例子 p279 看：降級只發(fā)生在被“別的進程”搶占時，時間片到了然后還是自己執(zhí)行不算 ( 更完整說的話， 同級或下級 隊列中有進程時 ，盡管沒有進程來搶占當前進程， 都需要降級 ) 認為級數(shù)無限制這個畫幾張狀態(tài)圖會很清楚A1 B1 A1 C1 B1 A1 C1 B2 D2 B1 E2 D1 E1 D1 E1 D1 E1根據(jù)標準答案（第五

33、版），這道題目上面這樣是不對的，所以，目前認為反饋的基本原則如下： 新來的永遠最優(yōu)先 所有進程在同一級隊列時不降級，其余降級A1 B1 A1 C1 B1 A1 C1 B2 D1 B1 D1 E1 D1 E1 D1 E1 D1 E2反饋（ q=2i ）類似上面10 、多處理器和實時調度 習題 10.1 具有完成 deadline 的周期任務，畫出 固定優(yōu)先級調度圖 最早最后期限調度圖 （ P317 例子，一章只看兩頁，清楚明了 = = ） 個人覺得調度就是要用合理的執(zhí)行順序安排達到并行的效果。 這道題目并不復雜，注意這個和例題的第一個是對應的 周期性任務、完成最后期限， 比較的是固定優(yōu)先級 和 最早最后期限 固定優(yōu)先級：有 6 種方法，保證第一次 A 不丟，只有 ABC ACB BAC ABC C 丟 ACB B 丟 BAC C 丟 所以都是不行的（其實從 10 * 50/20 + 10 +15 = 50 滿滿的可以大致猜出是不行的），這樣的話應該畫一個圖意思一下就行 最早最后期限 在這里要設定一下，最后期限相同時，進程的執(zhí)行順序是 ABC A1 10 B1 10 A2 10 C1 15 A3 10 B2 5 A4 10 B2 5 C2 5 A5 10 C5 10 100 個時間單位可以認為是一個周期，用最早最后期限調度可以完成三個周期任務的調度。 習題