第三章 程序排程與死鎖 (課後題)

文章目錄

• 選擇與填空
• 簡答題.
• • 1. 程序排程的功能是什麼?時機是什麼?(p88)
  • 2. 什麼是時間片輪轉排程算法?(p92)
  • 3. 什麼多級隊列排程算法?(p93)
  • 4. 什麼是自排程方式? 自排程有什麼優缺點?(p100)
  • 5. 什麼是死鎖? 引起死鎖的原因是什麼?(p101)
• 簡單應用

選擇與填空

1. 影響時間片大小選擇的主要因素有3個: (p92)

   解析: (1). 系統對響應時間的要求: 系統響應時間與程序數和時間片大小成正比, 是以在系統允許的最大程序數一定的情況下, 時間片的長短取決于系統要求的響應時間. 響應時間越短, 時間片的取值應該越小.

   (2). 就緒隊列中的程序數量: 系統程序數給定的情況下, 那麼程序越多, 響應時間越長, 是以當設定了最長響應時間值後, 時間片大小與系統允許的最大程序數成反比.

   (3). 系統的處理能力.

2. 關于多級隊列排程算法正确的是: 各就緒隊列的排程算法和優先權都可能不相同(p93)
3. 某系統中有4個并發程序, 都需要同類資源3個, 那麼該系統不會發生死鎖的最少資源數是:

   9個

   解析:4個并發程序, 每個程序預配置設定 2個資源, 最後一個可用資源, 可以輪流使用, 是以24+1 = 9個

   是以, 可以總結出公式: M個并發程序, 都需要同類資源N個, 最少資源數為M(N-1)+1個

4. FCFS(先來先服務)算法适合

   長程序

   , 不利于

   短程序

   (p89 <張瓊聲編著的作業系統概論 2017年版, 書後答案本題有誤>)
5. 采用基于靜态優先權的排程算法, 若不斷有高優先權程序進入就緒隊列, 低優先權程序可能進入

   饑餓

   狀态.

6. 銀行家

   算法是用來避免死鎖的算法.
7. S為死鎖狀态的

   充分

   條件是:當且僅當S狀态的資源配置設定圖是

   不可完全簡化

   的

簡答題.

1. 程序排程的功能是什麼?時機是什麼?(p88)

• 功能:
  • 程序排程功能是由作業系統核心的程序排程程式完成, 是按照某種政策和算法從就緒狀态程序隊列中為目前空閑CPU選擇在其上運作的新程序.
• 時機:
  • 當一個程序結束, 程序阻塞, 中斷傳回, 更高優先級的程序到來, 時間片用完, 系統都會發生排程

2. 什麼是時間片輪轉排程算法?(p92)

• 在時間片輪轉算法中, 程序需要在CPU上運作的時間總數(這裡稱為時間區間),或小于一個時間片,或大于一個時間片. 對于程序的時間區間小于時間片的情況, 程序在CPU上運作結束後, 程序本身會釋放CPU. 然後由作業系統排程為另一個就緒程序配置設定CPU. 對于程序的時間區間大于一個時間片的情況, 程序可能需要若幹個時間片.每當程序在CPU上連續運作的時間等于一個時間片長度時, 作業系統在時鐘中斷處理過程中就會搶占CPU. 進行程序切換, 用新的就緒程序替代目前程序,被替換的目前程序重新回到就緒隊列中.

3. 什麼多級隊列排程算法?(p93)

• 将就緒隊列分成多個獨立隊列, 根據程序的某些屬性, 如需要占用的記憶體大小, 程序優先權或程序類型, 程序會被永久配置設定到一個隊列, 每個隊列有自己的排程算法, 不的隊列的優先權不同, 排程算法也可能不同.

4. 什麼是自排程方式? 自排程有什麼優缺點?(p100)

• 采用自排程的系統中設定一個公共的就緒隊列, 任何一個空間的處理器都可以自行從該就緒隊列中選取一個程序或線程運作.
• 優點
  • 易移植
  • 有利于提高CPU的使用率
• 缺點
  • 瓶頸問題.
  • 低效性
  • 線程切換頻繁

5. 什麼是死鎖? 引起死鎖的原因是什麼?(p101)

• 如果一個程序所申請的資源被其他處于阻塞狀态的程序占有, 該程序就會因為不能獲得所申請的資源被阻塞. 若此時該程序恰好又占有了前述程序的所需要的資源, 那麼這一組程序就可能因為等待釋放自己所需要但被其它程序已占用的資源而無法向前推進, 這種由于多個程序競争共享資源而引起的不程序不能向前推進的僵死狀态, 稱為死鎖.
• 原因:

  競争共享資源且配置設定資源的順序不當.

簡單應用

考慮下面的一個系統在某一時刻的狀态, 如表所示

程序名稱	allocation;(ABCD)	Max(ABCD)	Available (ABCD)
p0	0012	0012	1520
p1	1000	1750
p2	1354	2356
p3	0632	0652
p4	0014	0656

使用銀行家算法回答下列問題.

1. need矩陣的内容是怎樣的?

• p0程序已經有0,0,1,2, 最多需求是0,0,1,2, 是以need = max-allocation = 0-0, 0-0, 1-1, 2-2,也就是0, 0, 0,0
• 同理, p1程序就是1-1, 7-0, 5-0, 0-0, 也就是0, 7, 5, 0
• p2程序就是2-1, 3-3, 5-5, 6-4, 也就是1, 0,0,2
• p3程序就是0-0, 6-6, 5-3, 2-2, 也就是0,0,2,0
• p4就是0-0, 6-0, 5-1, 6-4,也就是0, 6, 4, 2

1. 系統是否處于安全狀态?106

   課本中有算法公式, 我看不習慣, 是以用文字描述,

   下列是個安全檢測過程:

   p0 需求0, 0, 0, 0資源, 可以運作, 完後成釋放0, 0, 1, 2, 此時空閑1+0, 5+0, 1+2, 2+0, 也就是1, 5, 3, 2

   此時p2程序申請1, 0,0 ,2資源後, 空閑資源為:0, 5, 3, 0, 運作完成,釋放0+2, 5+3, 3+5, 0+6 , 也就是2, 8,8, 6

   此時p3程序申請0, 0, 2,0資源, 空閑2-0, 8-0, 8-2, 6-0, 運作完成後, 釋放2+0, 8+6, 6+5, 6+2, 也就是2, 14, 11, 8

   此時p4程序申請0, 6, 4, 2資源, 空閑2-0, 14-6, 11-4, 8-2 運作完後, 釋放2+0, 8+6, 7+5, 6+6, 也就是2, 14, 12, 12,

   此時p1程序申請0, 7, 5, 0 資源,可以完全滿足運作

   至此, 找到安全序列< p0 - p2- p3 - p4 - p1>, 是以此時系統處于安全狀态.

2. 如果p1提出資源請求(0,4,2,0), 這個請求能否立刻被滿足?