Nicholas Blogger

• 在 Multiprogramming 之下，記憶體內存在有多個 Process 執行，且各個 Process 的 size 並不相同，進入系統及完成工作的時間也不盡相同
• OS 採用 “Contiguous Allocation” 的方式，依據各個 Process 的大小，找到一塊夠大的連續可用空間，配置給該 Process 使用

• Def: 決定程式執行的起始位址

• 即： 程式要在記憶體的哪個地方開始執行
  • ∵ 所有程式與 Data 均須在 MM 中方可為 CPU 使用
  • 連帶地將程式內所宣告的資料與變數位在 MM 的什麼地方也一併確定了

Def: 令 G = (V, E) 為一有向圖，其中

• V (頂點集合) 可分成兩類：
  • Process:
  • Resource: “•” 表示該資源的數量。
• E (邊集合)也可分成兩類：
  • Request edge (申請邊)
  • Allocated edge (配置邊)

若 Dead Lock Prevention 與 Avoidance 都不用，則系統中可能存在 DeadLock。 ∴ 有必要提供下列機制：

• 偵測死結是否存在

• 若死結存在，則必須打破死結，恢復正常

• 優點：
  • Resource Utilization 較高
  • Throughput 提升
• 缺點：
  • Cost 太高

• Dead Lock Detection 與 Dead Lock Recovery 是一體的

當 Process 提出對資源的申請時，O.S. 會根據以下資訊執行銀行家演算法 (Banker’s Algo., 內含 Safety Algo.)，來判斷系統在假設 核准申請後是否處於 Safe State。若是，則真的核准其請求；否則否決此次申請，Process 須再等待一段時間，下一次再提出申請。

• 申請資源數量
• 各 Process 目前所持有的資源數量
• 各 Process 尚需要之資源需求量
• 系統目前可用的資源數量

概念: 打破四個必要條件其中之一，就可以保証死結永不發生。

系統中存在一組 Processes 陷入 “互相等待對方所擁有之資源” 的情況 (即: Circular Waiting) ，造成所有 Processes 皆無法往下執行，使得 CPU 利用度及産能大幅降低。

Example:

• 假設一個系統中有兩個資源 \(R_1\) 與 \(R_2\) ，而且該系統產生出兩個行程 \(P_1\) 與 \(P_2\)

Divide and conquer 是一種由上而下 ( top-down ) 的解題方式

• Def:
  • 可將母問題切割成較小的問題(切割)，使用相同的解決程序加以處理 (征服)。所有小問題的解可以成為母問題的最後解; 若有必要，則再將每個小問題的處理結果加以合併，就可以得到最後的答案。
    • 由於使用相同的解決程序處理每個小問題，這一個程序就會被遞迴呼叫，因此一個遞迴演算法則通常以一個副程式的型式出現，內部包含一個解決程序與遞迴呼叫。
    • 對於具有遞迴關係的問題，或是一些採用遞迴定義的資料結構，都適合採用 Divide and Conquer 演算法設計策略
  • 最簡潔、易懂
  • 效率差 ( ∵ 採用遞迴設計 )

本文蒐集

• LeetCode
• LeetCode
• LeetCode

本文蒐集

• LeetCode 67
• LeetCode 28
• LeetCode 14