核心觀念

本題考查 CPU 排程的三項基本概念：

1. 可搶先排程（Preemptive Scheduling）的意義。
2. 作業系統決定 CPU 排程的時機。
3. FCFS 排程下，程序執行順序、甘特圖與平均等待時間的計算。

等待時間公式

程序的等待時間為：

$$\text{等待時間}=\text{開始執行時間}-\text{抵達時間}$$

平均等待時間為：

$$\text{平均等待時間} = \frac{\text{所有程序等待時間總和}}{\text{程序總數}}$$

---

解題方法

（一）可搶先排程（Preemptive）

可搶先排程是指：

程序尚未執行完畢時，作業系統可以中斷目前正在使用 CPU 的程序，暫停其執行，將 CPU 分配給其他程序。

被中斷的程序會保留其執行狀態，例如程式計數器、暫存器內容等，之後再恢復執行。

常見的觸發情形包括：

• 時間配額用完，例如 Round Robin。
• 新程序抵達，且其優先權高於目前執行中的程序。
• 發生較高優先權的系統工作或中斷。

可搶先排程的優點是反應時間較短，適合分時系統及互動式系統；缺點是會產生程序切換（Context Switch）的額外負擔。

相對地，非搶先排程中，程序一旦取得 CPU，通常會執行到完成，或執行至主動阻塞、等待 I/O，才會釋放 CPU。

---

（二）決定 CPU 排程的時間點

以下列出 3 個常見的 CPU 排程決定時機：

1. 目前執行中的程序由執行狀態轉為等待狀態

例如程序要求 I/O，必須等待磁碟或其他裝置完成。

2. 目前執行中的程序由執行狀態轉為就緒狀態

例如可搶先排程中，程序的時間配額用完，或被較高優先權程序搶占。

3. 某個程序由等待狀態轉為就緒狀態

例如 I/O 完成，原本等待中的程序重新進入就緒佇列。

此外，目前執行中的程序終止，也是作業系統重新進行 CPU 排程的時機。

---

（三）FCFS 甘特圖與平均等待時間

1. 決定執行順序

FCFS 的原則是：

依程序抵達就緒佇列的先後順序執行，先抵達者先取得 CPU。

題目給定的抵達順序為：

$$P2 \rightarrow P3 \rightarrow P1 \rightarrow P4$$

各程序所需處理時間為：

• $P2=3$ 毫秒
• $P3=2$ 毫秒
• $P1=10$ 毫秒
• $P4=4$ 毫秒

2. 計算各程序執行區間

核心觀念

本題考查兩個重點：

1. Docker 的容器化架構，以及 Docker Client、Docker Daemon、Image、Container、Registry 等元件的功能。
2. Docker Compose 如何依據 YAML 設定檔，建立並啟動由多個容器組成的微服務應用程式。

Docker 的核心概念是：將應用程式及其執行環境封裝成映像檔，再由容器引擎建立相互隔離、可快速部署的容器。

---

（一）Docker 的架構與組成元件

1. Docker 的整體架構

Docker 採用 Client–Server 架構，主要由 Docker Client 與 Docker Daemon 組成：

$$\text{Docker Client} \rightarrow \text{Docker Daemon} \rightarrow \begin{cases} \text{Images}\\ \text{Containers}\\ \text{Networks}\\ \text{Volumes} \end{cases}$$

Docker Client 負責接收使用者指令，Docker Daemon 負責實際執行容器、映像檔、網路及儲存空間的管理工作。

Docker Client 與 Docker Daemon 可位於同一部主機，也可透過 REST API、Unix socket 或 TCP 方式連接遠端 Docker 主機。

---

2. Docker Client

Docker Client 是使用者與 Docker 系統互動的介面，最常見的是 docker 命令列工具。

常見指令如下：

• docker run：建立並啟動容器。
• docker pull：從映像檔倉庫下載 Image。
• docker build：依據 Dockerfile 建立 Image。
• docker ps：查看執行中的容器。
• docker images：查看本機映像檔。
• docker stop：停止容器。
• docker rm：刪除容器。

Client 本身通常不直接建立容器，而是將請求傳送給 Docker Daemon 處理。

---

3. Docker Daemon

Docker Daemon 通常稱為 dockerd，是 Docker 主機上的背景服務，負責：

• 管理 Docker Images。
• 建立、啟動、停止及刪除 Containers。
• 管理 Docker Networks。
• 管理 Docker Volumes。
• 建立 Image。
• 與 Registry 傳送或接收映像檔。
• 透過容器執行環境啟動容器程序。

Docker Daemon 是 Docker 架構中的核心管理元件。Docker Client 發出的命令，最後由 Daemon 轉換成實際操作。

---

4. Docker Image

Docker Image 是建立容器的唯讀範本，內含：

• 基礎作業系統檔案。
• 應用程式程式碼。
• 執行環境與函式庫。
• 環境變數預設值。
• 啟動命令及相關設定。

Image 通常採用分層式結構，每一層代表檔案系統的部分變更。多個 Image 可共用相同的基礎層，以節省儲存空間及下載時間。

Image 本身不是正在執行的程式，必須由 Docker 依據 Image 建立 Container 後，才會執行應用程式。

---

5. Docker Container

Container 是由 Image 建立出的執行個體，可視為 Image 的執行狀態。

Container 具有以下特性：

• 使用隔離的程序、檔案系統、網路及資源環境。
• 與主機及其他容器分隔。
• 啟動速度快、所需資源通常比虛擬機器少。
• 容器內的主要程序結束後，容器通常也會停止。
• 容器可被建立、啟動、停止、重啟及刪除。

Container 與虛擬機器的主要差異，在於容器通常共用主機的作業系統核心；虛擬機器則需要執行完整的客體作業系統。

---

6. Docker Registry

Registry 是儲存及發佈 Docker Image 的映像檔倉庫。

常見用途包括：

• 使用 docker pull 下載 Image。
• 使用 docker push 上傳 Image。
• 由不同主機共享相同的 Image。
• 管理 Image 的版本與標籤。

Docker Hub 是常見的公有 Registry，企業也可建立私有 Registry，以保存內部應用程式映像檔。

---

7. Docker Network

Docker Network 負責容器之間及容器與外部網路的連線。

在微服務架構中，不同服務通常各自執行於不同容器，容器透過 Docker Network 彼此通訊。Compose 預設會建立一個應用程式專用網路，使服務可以使用服務名稱互相尋址。

例如，資料庫服務名稱為 db 時，應用程式容器可使用 db 作為主機名稱連線，而不必直接指定容器 IP 位址。

常見網路模式包括：

• bridge：單一 Docker 主機上最常見的網路模式。
• host：容器直接使用主機網路。
• none：容器不配置一般網路。
• overlay：用於多主機 Docker 網路環境。

---

8. Docker Volume

Container 的可寫入層通常具有暫時性，容器刪除後，寫入容器內的資料可能一併消失。因此需要使用 Volume 保存持久性資料。

Volume 常用於：

• 資料庫資料。
• 使用者上傳檔案。
• 日誌資料。
• 應用程式產生的持久性設定。

Volume 與容器生命週期分離，即使容器重新建立，資料仍可保留。

---

9. Dockerfile

Dockerfile 是建立 Docker Image 的設定檔，描述映像檔如何製作，例如：

• 使用哪一個基礎 Image。
• 複製哪些程式檔案。
• 安裝哪些套件。
• 設定哪些環境變數。
• 容器啟動時執行哪一個命令。

常見指令包括：

• FROM：指定基礎 Image。
• RUN：在建立 Image 時執行命令。
• COPY：複製檔案至 Image。
• ENV：設定環境變數。
• EXPOSE：宣告應用程式使用的連接埠。
• CMD：指定預設啟動命令。
• ENTRYPOINT：指定容器主要執行程式。

Dockerfile 用於「製作 Image」；Compose 用於「定義並啟動多個服務」。

---

10. 容器執行環境與隔離機制

Docker 容器並非完整虛擬機器，而是透過 Linux 核心提供的機制實現隔離與資源管理：

• Linux namespaces：隔離程序、網路、掛載點、主機名稱及使用者等。
• cgroups：限制及統計 CPU、記憶體等資源使用量。
• Union File System：以分層方式管理 Image 與容器檔案系統。
• Container runtime：負責實際建立及執行容器程序。

因此，Docker 容器具有輕量、快速及可攜性的特性。

---

（二）使用 Docker Compose 啟動微服務應用程式的基本步驟

1. Docker Compose 的用途

Docker Compose 是用來定義及管理多容器 Docker 應用程式的工具。

微服務應用程式通常包含多個服務，例如：

• Web 前端服務。
• API 後端服務。
• 資料庫服務。
• 快取服務。
• 訊息佇列服務。

Compose 將這些服務、映像檔、建置方式、連接埠、環境變數、網路、Volume 及相依關係集中寫在 YAML 設定檔中，通常檔名為 docker-compose.yml 或 compose.yml。

---

2. 準備應用程式與 Dockerfile

首先準備各微服務的程式碼及 Dockerfile。

若服務已有可用的 Image，可直接指定 Image；若尚未建立 Image，則需在 Compose 中指定 build，由 Dockerfile 建立 Image。

例如：

• frontend：前端服務。
• backend：後端 API 服務。
• db：資料庫服務。

---

3. 建立 Compose YAML 設定檔

Compose 設定檔描述每個服務的執行方式，例如：

• services：定義服務。
• image：指定使用的 Image。
• build：指定建置 Image 的位置。
• ports：主機與容器的連接埠對應。
• environment：環境變數。
• volumes：持久性資料掛載。
• networks：網路設定。

核心觀念

本題考查「LRU 近似分頁替換法」。由於精確的 LRU 必須記錄每一頁的實際使用時間，硬體成本較高，因此作業系統常以「參考位元（Reference Bit）」近似判斷頁面近期是否被使用。

本題採用最常見的 Second-Chance／Clock 演算法：

1. 每個頁框附有一個參考位元 $R$。
2. 頁面被載入或被存取時，設定 $R=1$。
3. 發生頁面錯誤時，從替換指標開始尋找：

• 若 $R=0$，選為替換頁面。
• 若 $R=1$，將其改為 $0$，給予一次「第二次機會」，再檢查下一個頁框。

4. 頁框以循環方式檢查。

本題假設：

• 初始時 4 個頁框皆為空。
• 頁框採循環排列。
• 替換指標從第 1 個頁框開始。
• 只有在頁面被存取時才設定參考位元，未指定週期性清除。

解題方法

設四個頁框為 $F_1,F_2,F_3,F_4$，並記錄各頁面的參考位元 $R$。

1. 依序載入頁面 $1,2,3,4$

前四次參考頁面均不在記憶體中，因此依序載入：

參考頁面	$F_1$	$F_2$	$F_3$	$F_4$	結果
$1$	$1(1)$	—	—	—	頁面錯誤，載入 1
$2$	$1(1)$	$2(1)$	—	—	頁面錯誤，載入 2
$3$	$1(1)$	$2(1)$	$3(1)$	—	頁面錯誤，載入 3
$4$	$1(1)$	$2(1)$	$3(1)$	$4(1)$	頁面錯誤，載入 4

括號內為參考位元。此時四個頁框均已使用過，故：

$$F_1=1(1),\quad F_2=2(1),\quad F_3=3(1),\quad F_4=4(1)$$

替換指標回到 $F_1$。

2. 參考頁面 $1$

頁面 $1$ 已在 $F_1$ 中，屬於頁面命中，將其參考位元維持為 $1$：

$$F_1=1(1),\quad F_2=2(1),\quad F_3=3(1),\quad F_4=4(1)$$

替換指標仍從 $F_1$ 開始。

3. 參考頁面 $5$

頁面 $5$ 不在記憶體中，發生頁面錯誤。依序檢查：

• $F_1$ 的頁面 $1$：$R=1$，改為 $0$，跳過。
• $F_2$ 的頁面 $2$：$R=1$，改為 $0$，跳過。
• $F_3$ 的頁面 $3$：$R=1$，改為 $0$，跳過。
• $F_4$ 的頁面 $4$：$R=1$，改為 $0$，跳過。
• 再回到 $F_1$：此時頁面 $1$ 的 $R=0$，予以替換。

因此，以頁面 $5$ 取代頁面 $1$：

$$F_1=5(1),\quad F_2=2(0),\quad F_3=3(0),\quad F_4=4(0)$$

替換指標移至 $F_2$。

4. 參考頁面 $2$

頁面 $2$ 位於 $F_2$，發生頁面命中，將其參考位元設為 $1$：

$$F_1=5(1),\quad F_2=2(1),\quad F_3=3(0),\quad F_4=4(0)$$

5. 參考頁面 $4$

頁面 $4$ 位於 $F_4$，發生頁面命中，將其參考位元設為 $1$：

$$F_1=5(1),\quad F_2=2(1),\quad F_3=3(0),\quad F_4=4(1)$$

6. 參考頁面 $3$

頁面 $3$ 位於 $F_3$，發生頁面命中，將其參考位元設為 $1$：

核心觀念

本題考查兩個觀念：

1. 叢集式系統（Cluster System）：將多部獨立電腦透過高速網路與叢集軟體連結，使其共同提供運算、儲存或服務功能。
2. 雲端運算系統（Cloud Computing System）：透過網路，以隨需、彈性、可擴充的方式提供運算資源與資訊服務。

判斷兩者關係時，必須區分：

• 叢集是系統架構或建置方式。
• 雲端運算是資源提供與服務交付模式。

雲端系統經常使用叢集作為底層硬體架構，但雲端運算本身不等同於叢集式系統。

---

解題方法

本題適合分成兩個層次回答：

• 第一小題先說明叢集由哪些元件組成，再說明常見架構與系統特性。
• 第二小題比較「叢集」與「雲端」的定義，判斷兩者是包含關係、實作關係，還是完全相同。

答題時不可只寫「雲端就是叢集」或「雲端不是叢集」，必須說明：雲端可以採用叢集建置，但雲端的核心還包括虛擬化、資源池化、自動配置、彈性伸縮與服務化等機制。

---

（一）叢集式系統的架構及其特性

1. 叢集式系統的定義

叢集式系統是由兩部以上的獨立電腦所組成，各節點通常具有自己的：

• 處理器
• 主記憶體
• 作業系統
• 輸入輸出裝置
• 網路介面

各節點透過高速互連網路連結，並由叢集管理軟體協調工作，使多部電腦能共同提供服務。

叢集中的每一部電腦稱為一個 Node（節點）。對使用者而言，整個叢集通常被視為一個整體服務平台。

---

2. 常見的叢集式系統架構

（1）節點層

叢集由多個運算節點組成。每個節點通常可以獨立執行作業系統與應用程式，節點之間透過高速網路交換資料、分派工作及偵測彼此狀態。

節點可以是：

• 一般伺服器
• 多核心伺服器
• 工作站
• 專用運算節點
• 虛擬機器所在的主機

近年常見的叢集多採用大量標準化伺服器組成，以降低建置成本並方便擴充。

（2）互連網路層

節點之間需要透過互連網路進行：

• 工作分派
• 節點狀態偵測
• 資料交換
• 故障通知
• 叢集控制訊息傳遞

互連網路的效能會直接影響叢集的整體表現。高效能叢集通常使用低延遲、高頻寬的網路，以減少節點間通訊成本。

（3）儲存層

叢集可採取下列儲存方式：

• 各節點使用本機儲存設備
• 多個節點共用儲存設備
• 使用分散式檔案系統
• 使用儲存區域網路提供共用資料存取

若叢集用於高可用性服務，通常需要考慮資料同步、共用儲存及故障切換問題。

（4）叢集管理與中介軟體層

叢集軟體負責將多個節點整合成一個可管理的系統，主要功能包括：

• 節點註冊與管理
• 工作分派
• 負載平衡
• 節點健康狀態監控
• 故障偵測
• 服務重新啟動
• 故障切換
• 資源分配
• 資料同步

此層是叢集能夠正常運作的關鍵。若只有多部電腦透過網路連接，而沒有叢集管理機制，通常只能稱為分散式電腦群組，不能充分發揮叢集的整合功能。

---

3. 常見的叢集分類

（1）高可用性叢集

高可用性叢集的重點是避免單一節點故障造成服務中斷。

常見架構包括：

• Active-Active：多個節點同時提供服務，故障時由其他節點繼續處理工作。
• Active-Standby：主要節點平時提供服務，備援節點處於待命狀態；主要節點故障時，由備援節點接手。

叢集會利用心跳訊號監測節點狀態。當系統偵測到節點失效時，便進行故障切換（Failover）。

（2）負載平衡叢集

負載平衡叢集將使用者要求分配到多個節點，以避免單一伺服器過載。

其基本流程如下：

1. 使用者提出服務要求。
2. 負載平衡器或叢集控制元件接收要求。
3. 系統依節點負載、連線數或服務狀態選擇適當節點。
4. 由選定節點處理服務。
5. 節點故障時，系統將要求轉送至其他正常節點。

此架構常用於網站、資料庫、郵件服務及企業應用系統。

（3）高效能運算叢集

高效能運算叢集又稱 HPC Cluster，將大型工作分割成多個子工作，再分派給不同節點平行執行。

例如一項工作包含 $n$ 個可平行處理的子工作，可分配至 $p$ 個節點。理想情況下，執行時間可接近原本的：

$$\frac{1}{p}$$

但實際效能會受到下列因素影響：

• 工作是否能完全平行化
• 節點間通訊時間
• 工作分割與合併成本
• 負載是否平均
• 共用資源競爭

因此，節點數增加不代表效能一定按比例增加。

（4）儲存叢集

儲存叢集將多個儲存節點整合，提供較大的容量、較高的存取效能與資料備援能力。