Operating System Concepts 作業系統概論 Operating System Concepts 第二版(2nd Edition) 賈蓉生 胡大源 林金池 編著

第一章 導讀(Introduction) 1-1 簡介 1-2 本書主要內容 1-3 Java 系統程式 1-4 專有名詞索引 1-5 習作習題 1-6 光碟使用

1-1 簡介 作業系統(Operating System) 是學習電腦的基礎課目，內容含及電腦系統之結構、執行管理、儲存管理、資料傳遞、網路應用、與保護安全等項目。在未來學習電腦的大道上，這些項目提供了一個輪廓，可令讀者胸有成竹地向前邁進。

1-2 本書主要內容 本書內容概分七篇，內容包括概論、行程管理、儲存管理、輸入輸出、分散式系統、保護與安全、與應用系統。

1-3 Java 系統程式 本書內容是人與機器間之介面--作業系統(Operating System)，其中有許多觀念的描述(Descriptions)、執行方法的演算(Algorithms) 等均需以一個眾所認同的語言型態來表示，本書採用具有物件導向意義(Object-Oriented Approach) 之Java語言。有關Java系統之架構，讀者可參閱本書第二十四章。

1-4 專有名詞索引 為了幫助讀者整理專有名詞，本書編輯中文專有名詞索引約1,000個(如附錄D)，以筆劃查閱；英文專有名詞索引約1,000個(如附錄E)，以字母查閱。其中質量幾已涵蓋所有中英文專有名詞，足夠儲備讀者未來閱讀原文書籍或期刊的能力。

1-5 習作習題 作業系統是學習電腦的基礎課目，也是各重點考試的必考科目，如升學考試、公職考試、甚或求職考試等。本書將各章節重點內容整理成各類考題，對準備考試有最全面性、深入性的幫助。有關習題答案，讀者可向碁峄圖資公司或作者以E-Mail直接索取。

1-6 光碟使用 本書隨書附光碟一片，內容有Java安裝程式(System)、範例應用程式(Program)；另於出版書局附教學光碟一片，內容有教學投影(Ppt)、習題解答(Ex)、Java安裝程式(System)、範例應用程式(Program)。

第一篇 導論(Over View) 作業系統(Operating) 是一組系統程式(System Program)，介於使用者(User) 與電腦硬體(Hardware) 之間，幫助使用者方便使用，監督電腦有效執行。 作業系統內容複雜，範圍龐大，為了讓讀者在深入研讀之前，有一粗略全盤概念的認識，本篇就基礎觀念、電腦系統結構、與作業系統架構先作介紹。

第二章 基礎概念(Introduction) 2-1 簡介 2-2 大型電腦系統(Mainframe Systems) 2-3 微型電腦系統(Microcomputer Systems) 2-4 多處理器系統(Multiprocessor System) 2-5 分散式系統(Distributed System) 2-6 習題(Exercises)

2-1 簡介 作業系統(Operating System) 是一組系統程式，用於支配(manage) 電腦本機硬體及週邊設備等資源之使用，並促進使用者方便使用(conveniently)、有效使用(efficiently)。

圖2-1

2-2 大型電腦系統(Mainframe Systems) 通常大型電腦具有強大綜合性的功能(如IBM370)，可同時執行單一工作(Job)、或多個工作，因不同之需求，作業系統可類分為批次系統(Batch Systems)、即時系統(Real-Time Systems)、多工系統(Multi-programmed Systems)、與分時系統(Time-Sharing Systems) 等。

2-3 微型電腦系統 (Microcomputer Systems) 微型電腦有：個人桌上型電腦系統(PC或稱Desktop)、筆記型電腦系統(Notebook或稱Laptop)、手持式電腦系統(Handheld) 等。 PC微型電腦快速發展於1970s年代，與大型電腦(Mainframe) 比較，微型電腦硬體資源較少但便宜；使用者單純，通常是由一個使用者霸佔使用。因此其作業系統之設計自與大型電腦不同。

2-4 多處理器系統 (Multiprocessor System) 一台電腦一個CPU處理器(Central Processing Unit)，既使是新型電腦亦多是如此配置，擁有一個主CPU處理器。一台電腦若擁有多個處理器，其作業系統將對應於多處理器系統(Multiprocessor System)， 多處理器系統可類分為對稱多處理器系統(Symmetric Multiprocessing) 與非對稱多處理器系統(Asymmetric Multiprocessing)。

圖2-4-1

圖2-4-2

2-5 分散式系統 (Distributed System)

圖2-5-1

圖2-5-2

2-6 習題(Exercises) 1、何謂作業系統？ 2、一套完整之電腦系統可概分那四組區塊？ 3、何謂批次系統(Batch Systems)？ 4、何謂即時系統(Real-Time Systems)？ 5、何謂多工系統(Multiprogrammed Systems)？ 6、何謂分時系統(Time-Sharing Systems)？ 7、微型電腦有那些？ 8、多處理器的優點為何？ 9、何謂分散式系統(Distributed System)。 10、網路應用範圍可分為幾類？ 11、網路之連接技術可分為幾類？ 12、分散式系統在功能分配上可類分為幾類？

第三章電腦系統結構 (Computer SystemStructure) 3-1 簡介 3-2 起始操作(Start Running) 3-3 中斷(Interrupt) 3-4 輸入輸出架構(I/O Structure) 3-5儲存架構(Storage Structure) 3-6硬體保護(Hardware Protection) 3-6-1 輸入輸出保護(I/O Protection) 3-6-2 記憶體保護(Memory Protection) 3-6-3 中央處理器保護(CPU Protection) 3-7網路架構(Network Structure) 3-7-1 區域網域(Local-Area Network) 3-7-2 廣域網域(Wide-Area Network) 3-8 習題(Exercises) 3-9範例系統程式(Programming) 3-9-1中斷例外處理(模擬3-3節)

3-1 簡介 在我們深入探討電腦作業系統之前，有些關於電腦的基本系統結構須先有一概念性的了解，本章將粗略討論電腦系統結構，內容如起動(StartUp)、輸入/輸出(I/O)、儲存(Storage) 等，及計算機結構(Computer Architecture) 與作業系統(Operating System)間之互動架構。

3-2 起始操作(Start Running) 當開啟電腦的同時，即啟動 “初始程式(Initial Program 或稱Bootstrap Program” )，為求快捷，此程式特置於唯讀記憶體中(ROM Ready-Only Memory)，初始啟動CPU、裝置控制器(Device Controllers)、傳導器(Adapters)、與記憶體(Memory)。初始程式將作業系統(Operating System) 載入記憶體作核心運行(Kernel)。

圖3-2

圖3-3

3-4 輸入輸出架構(I/O Structure) 當某裝置要求執行資料輸入輸出(I/O) 時，CPU載入該裝置控制器內之特殊功能暫存器，由作業系統導引中斷(Interrupt) 執行資料的輸入輸出。

I/O中斷可類分為同步I/O(Synchronous) 如圖3-4-1、與非同步I/O(Asynchronous) 如圖3-4-2

圖3-4-3

3-5儲存架構(Storage Structure) CPU是電腦的執行中樞，直接對主記憶體(Main Memory) 隨機存取(random access)資料，典型的指令執行週期(Instruction Execution Cycle) 如范紐曼(Von Neumann) 所提出之執行架構(如圖3-5-1)

圖3-5-1

圖3-5-2

3-6硬體保護 (Hardware Protection) 一台電腦硬體受傷害的原因來自電腦本身的機會不大，多是來自人為程式的錯誤，受傷害的硬體亦多是發生於I/O系統、記憶體、或CPU。因此所謂電腦硬體保護Hardware Protection) 就是摒除人為程式的錯誤，而保護的對象為： (1) I/O系統(I/O)、(2) 記憶體(Memory)、(3) 中央處理器(CPU)。

3-6-1 輸入輸出保護(I/O Protection) 使用者(Users) 可利用輸入輸出的機會，傳遞非法指令(illegal Instructions)、或資料(Data)，非法進入系統程式(Operating System) 領域執行破壞行為，為了避免如此傷害行為，所有的輸入輸出指令(I/O Instructions) 均定義納入系統模式(System Mode)。

圖3-6-1

3-6-2 記憶體保護(Memory Protection) 當使用者之工作程序進入記憶體後，作業系統以兩個暫存器鎖定記憶體之使用範圍，基底暫存器(Base Register) 存置起始地址(Address)；限制暫存器(Limit Register) 存置範圍距離，如圖3-6-2

圖3-6-2

3-6-3 中央處理器保護(CPU Protection) CPU的保護機制是在設定CPU之使用時間，作業系統對每一進入CPU之程式作使用時間設定，超過該設定時間即判定為非法無限迴圈，從CPU踢出該程式，執行CPU保護。

3-7網路架構(Network Structure) 多台電腦以網路連通，相互支援程序執行與檔案存取，是謂 “網路架構(Network Structure)。常見的網路架構有：小範圍區域網域(LAN Local-Area Network)、與大範圍廣域網域(WAN Wide-Area Network)。

3-8 習題(Exercises) 1、何謂核心運行(Kernel)？ 2、何謂事件中斷(Event Interrupt)？ 3、中斷表(Table of Interrupt) 與中斷程序之關係為何？ 4、何謂同步I/O中斷？ 5、何謂非同步I/O中斷？ 6、記憶體直接存取方法(DMA) 的使用條件為何？ 7、主記憶體與CPU的關係為何？ 8、主記憶體有那些無法克服的困難？ 9、何謂快取記憶體(Cache)？ 10、硬體傷害常發生在那些裝置上？ 11、何謂雙模操作法？ 12、如何作I/O保護？ 13、如何作記憶體保護？ 14、如何作CPU保護？ 15、何謂區域網域(LAN)？ 16、何謂廣域網域(WAN)？

第四章 作業系統架構 (Operating System Structure) 4-1 簡介 4-2 系統組成要件(System Components) 4-2-1行程管理(Process Management) 4-2-2主記憶體管理(Main Memory Management) 4-2-3檔案管理(File Management) 4-2-4輸入輸出系統管理(I/O System Management) 4-2-5輔助記憶體管理(Secondary Storage Management) 4-2-6網路連通管理(Networking Management) 4-2-7保護系統管理(Protection Management) 4-2-8介面指令管理(Shell Command Interpreter Management) 4-3 作業系統服務(Operating System Services) 4-4 系統呼叫(System Calls) 4-5 系統程式(System Programs) 4-6 應用程式(Application Programs) 4-7 系統架構(System Structure) 4-7-1 簡易架構(Simple Structure) 4-7-2 階層架構(Layered Approach) 4-7-3 微核心(Microkernel) 4-7-4 模組架構(Modules) 4-8 虛擬機器(Virtual Machines) 4-9 系統設計與編寫(System Design and Implementation) 4-10 檢選系統(System Generation) 4-11 開機系統(System Boot) 4-12 習題(Exercises)

4-1 簡介 作業系統是一個非常龐大且複雜的程式，如果沒有一系列井然有序的描述，將不易了解，本章就其組成要件、服務、程式架構、系統程式、應用程式、設計規範、開機系統等，作輪廓描述，讓讀者先有清晰概念，本書將於爾後各章節詳細敘述。

4-2 系統組成要件(System Components) 作業系統(Operating System) 即龐大又複雜，本節就其功能性(如圖4-2-1) 將系統類分成程序管理(Process Management)、主記憶體管理(Main Memory Management)、檔案管理(File Management)、輸入輸出管理(I/O Management)、輔助記憶體(Secondary Storage Management)、網路連通管理(Networking Management)、保護管理(Protection Management)、指令解釋管理(Command Interpreter Management)，並作概念描述。

圖4-2-1

4-3 作業系統服務 (Operating System Services)

4-4 系統呼叫(System Calls) 當行程(Process) 衝撞系統時，行程要求系統呼應執行是謂 “系統呼叫(System Call)”。除了低階語言(如組合語言Assembly Language) 與少數高階語言之某些狀況外，為了保護系統安全，一般高階語言均不被允許直接(Directly) 作系統呼叫。

圖4-4-1

圖4-4-2

圖4-4-3

4-5 系統程式(System Programs) 回憶圖2-1，最底層是電腦硬體(Hardware)，其次是作業系統(Operating System)，再其次即是系統程式(System Programs) 與應用程式(Application Programs)。系統程式(System Programs) 提供使用者程式(User’s Program) 一個良好的執行環境，亦即使用者與系統程式間的介面(Interface)，可藉系統呼叫(System Call) 或其他方式執行

4-6 應用程式(Application Programs) 如圖2-1，與系統程式在相同地位的是 “應用程式(Application Program 或 System Utilities)，用以支援解決一般之應用問題。這些程式包括網路瀏覽器(Web Browsers)、文字處理器(Word Processors)、試算表(Spreadsheets)、資料庫(Database Systems)、繪圖(Plotters)、統計分析(Statistical Analysis)、遊戲(Games) 等。

4-7 系統架構(System Structure) 隨著電腦應用需求之增加，作業系統已變成龐大且複雜，其結構概念也由整體架構(Monolithic System) 改向為小單位分割架構(Partition of Small Components System)。整體架構之缺點為反應遲緩，任何錯誤均將禍及整體系統甚至當機，優點為設計簡易、管理方便；小單位分割架構之缺點為設計複雜，優點為反應靈巧，區隔錯誤使其不影響其他部份。

圖4-7-1

圖4-7-2

圖4-7-3

圖4-7-4

圖4-7-5

4-8 虛擬機器(Virtual Machines) 一般作業系統可類分為3個主要區塊(如圖4-8-1)，包括行程(Processes)、核心(Kernel)、與硬體(Hardware) 三部份。

圖4-8-1

圖4-8-2

圖4-8-3

4-9 系統設計與編寫 (System Design and Implementation) 規劃設計藍圖之前，須先考量為何種電腦硬體設計？設計何種系統？採用批次執行(Batch)？分時執行(Time Shared)？一個使用者(Single User)？多個使用者(Multiusers)？即時系統(Real Time)？分散式據點(Distributed)？產生方式(Generation)？ 關鍵機制(Mechanisms) 用於處理如何作為(How)？，執行計劃(Policies) 用於處理做些什麼(What)？系統通常以低階語言--組合語言(Assembly Language)--編寫，也有小部份以高階語言--C、C++ --編寫，新型作業系統以Java編寫。

4-10 檢選系統 (System Generation) 一般系統程式之設計考量應是：(1) 適用於同型電腦(Class of Machine)，(2) 適用於不同的場所(Varity of Sits)，(3) 適用於不同的周邊環境(Varity of Peripheral Configurations)。 同類型電腦因是相同機件，可作統一設計，但為了滿足不同的場所與周邊環境，則須先考量納入所有可能發生的狀況，於臨場實地使用時，再篩選有用的內容納入當時的作業系統，如是設計的作業系統稱為 “檢選系統(SYSGEN System Generation)”。

4-11 開機系統(System Boot) 當電腦開啟電源(Power on) 或重新啟動(Reset) 時，立即將指令暫存器(IR Instruction Register) 載入，同時執行開機程式(Bootstrap Program)。開機程式儲存於ROM內，不須作任何初始動作(Initialization)，開機就執行，亦不受任何病毒的入侵。

4-12 習題(Exercises) 1、作業系統(Operating System)有那些要件？ 2、作業系統應有那些行程管理內容？ 3、在安排記憶體上、作業系統應有那些行程管理內容？ 4、作業系統應有那些檔案管理內容？ 5、作業系統應有那些I/O管理內容？ 6、作業系統應有那些輔助記憶體管理內容？ 7、作業系統應有那些網路連通管理內容？ 8、作業系統應有那些保護管理內容？ 9、作業系統應有那些介面命令管理內容？ 10、作業系統之服務要旨為何？ 11、系統呼叫可藉參數(Parameter) 傳遞訊息之方法有那些？ 12、系統呼叫可類分為那幾類？ 13、系統程式可類分那幾類？ 14、作業系統之架構可類分那機類？

行程管理(Process Management) 第二篇 行程管理(Process Management)

第五章 行程(Processes) 5-1 簡介 5-2 行程之觀念(Process Concept) 5-2-1 行程狀態(Process State) 5-2-2 行程控制區段(Process Control Block) 5-2-3 執行緒(Threads) 5-3 排程(Process Scheduling) 5-3-1 排程佇列(Scheduling Queues) 5-3-2 排程器(Schedulers) 5-3-3 內文切換(Context Switch) 5-4 行程操作(Operations on Processes) 5-4-1 行程產生 (Process Creation) 5-4-2行程結束(Process Termination) 5-5 合作行程 (Cooperating Processes) 5-6行程通訊 (Interprocess Communication) 5-6-1 訊息傳遞(Message Passing System) 5-6-2 同步操作(Synchronization) 5-6-3 緩衝(Buffering) 5-7網路連通(Server/Client Network) 5-8 習題(Exercises) 5-9 範例系統程式 5-9-1 父行程與子行程之繼承關係(模擬5-4-1節) 5-9-2 合作行程(模擬5-5節) 5-9-3 網路連通(模擬5-7節)

5-1 簡介 程式(Program) 是程式碼之檔案(File)，行程(Process) 是正在執行的程式(Program in Execution)。早期電腦當執行程式時，整個系統資源均用於支援該一個程式；今日電腦系統可同時支援多個程式之執行。 行程是工作的單元(Unit of Work)，一個程式有數個行程。系統內有多個行程競爭進入CPU作執行，CPU切換(Switch) 於各行程之間，盡求公平執行各行程。

5-2 行程之觀念(Process Concept) 如前述，行程(Process) 是正在執行的程式(Program in Execution)，一個程式可能有數個行程，有些書將行程(Process) 亦稱為工作(Job)，本書為了爾後的清晰解述，一般應用名稱使用 “行程(Process)”；特定意義應用名稱使用 “工作(Job)”，如工作排程(Job Scheduling) 等。

圖5-2-1

5-3 排程(Process Scheduling) CPU是系統的執行中樞，有其自身的執行能力限制(limitations)，不會因外在的強求而改變，亦無法完全配合周遭瞬息萬變的條件環境(Environment)。以行程(Process)為例，如有多個行程競爭進入CPU，因CPU一個時間只能執行一個工作，無法同時將這些行程同時執行，但可退而求其次，以其能力範圍內，輪流切換(switch) 執行各個行程，切換(switch) 的流程如圖5-3-1。

圖5-3-1

圖5-3-2

圖5-3-3

圖5-3-4

5-4 行程操作(Operations on Processes) 行程(Processes) 不定期隨機(dynamically) 產生，亦不定期隨機終結消失，為了可以處理如此不定期的多個行程，多數作業系統(Operating System) 均設計為可操作行程作並行執行(execute concurrently)。

5-5 合作行程 (Cooperating Processes) 一個行程如果不影響其他行程、不被其他行程影響、亦不與其他行程共享資料(Data) 或資源(Resource)，如是行程是謂 “獨立行程(Independent Process)”；否則即謂 “合作行程(Cooperating Process)。

5-6行程通訊 (Interprocess Communication) 兩個行程(Processes) 互通訊息是謂 “行程通訊(IPC Interprocess Communication)”，這兩個行程可能演譯自同一程式(Program)，亦可能演譯自不同的多個程式(Programs)。

圖5-6-1

圖5-6-2

5-7網路連通(Server/Client Network) 今日電腦網路蓬勃發展，網路連通已是作業系統的基本功能之一，網路連通(如圖5-7) 之要件為網址(IP)、埠(Port)、與平台(Socket)。請參考本章5-9節，實作一個網路連通範例，以Java作為執行語言，設定Server，Client兩個網路行程。

圖5-7

5-8 習題(Exercises) 1、何謂行程(Process)？ 2、行程有那5個狀態(States)？ 3、何謂 “行程控制區段(PCB Process Control Block)” ？ 4、行程控制區段(PCB Process Control Block) 內有那些資料？ 5、何謂 “排程佇列(Scheduling Queue)”？ 6、何謂 “排程器(Scheduler)”？ 7、除了因完成任務而結束外，行程尚有那些原因被迫結束？ 8、行程合作的理由有那些？ 9、直接通訊 (Direct Communication) 之優缺點為何？ 10、間接通訊 (Indirect Communication) 之優缺點為何？ 11、何謂同步操作(Synchronization)？ 12、何謂非同步操作(Asynchronization)？ 13、網路連通要件有那些？

第六章 執行緒(Threads) 6-1 簡介 6-2 執行緒定義(Overview) 6-3 多執行緒模型(Multithreading Models) 6-4 執行緒操作(Operations of Threads) 6-4-1 執行緒之終止(Cancellation) 6-4-2 信號管理(Signal Handling) 6-4-3 執行緒池(Thread Pools) 6-5 執行緒與CPU(Threads and CPU) 6-6 習題(Exercises) 6-7範例系統程式(Programming) 6-7-1 執行緒與CPU(模擬6-5節)

6-1 簡介 於前章我們針對行程(Processes) 已作概念性的討論，本章我們將討論更為靈活的執行單元 “執行緒(Threads)”。行程(Process) 是工作單元(Unit of work)，系統內有多個行程同時存在，但CPU一個時間只能處理一個行程，因此多數的行程都在等待狀態(Waiting State)，競爭進入CPU被執行，如此形式的行程又稱為 “執行緒(Thread)”。早期系統一個行程即是一個執行緒，新型電腦一個行程可視其多元性之工作內容，允許依不同工作內容分割出多個執行緒，利用CPU分時執行方法(Time Sharing)，在一個時間中可執行多個任務(Tasks)。

6-2 執行緒定義(Overview) 執行緒(Thread) 是CPU之基本執行單元(Basic Unit)，如前述，早期系統一個行程即是一個執行緒，新型電腦系統一個行程可視其多元性之工作內容，允許依不同工作內容分割出多個執行緒，利用CPU分時執行方法(Time Sharing)，在一個時間中執行多個任務(Tasks)。 如圖6-2-1，每個執行緒(Thread) 擁有各自的識別碼(ID)、指令計數器(Program Counter)、暫存器組(Register Set)、與一個堆疊(Stack)。如圖6-2-2，同屬一個行程(Process) 的各執行緒可共享程式碼(Code)、資料(Data)、檔案(Files) 等系統資源。

圖6-2-1

圖6-2-2

6-3 多執行緒模型(Multithreading Models) 於前節已描述使用者執行緒(User Threads) 與核心執行緒(Kernel Threads)，使用者執行緒由核心支援(support)，但由使用者管理(managed)；核心執行緒由核心支援，亦由核心管理。本節將就使用者執行緒、與核心執行緒兩者之對應關係(Mapping Relations) 作更進一步的探討。

圖6-3-1

圖6-3-2

圖6-3-3

6-4 執行緒操作(Operations of Threads) 經過前數章節對執行緒的描述，讀者對執行緒已有基礎應用上的概念，本節將再就執行緒之其他執行事項作進一步的分析。

6-5 執行緒與CPU(Threads and CPU) Java系統內建Thread類別，其功能是將CPU分割成多個工作時段，適當地提供給條件最優的工作片斷作執行。使用者可藉：(1) 以新類別繼承Thread類別，再由該新繼承類別以new產生執行物件，(2) 或以 “new” 由類別Thread直接產生新執行物件，搶CPU時段給予條件最優的工作片斷先作執行。

6-6 習題(Exercises) 1、執行緒(Thread) 擁有那些基本設定？ 2、同屬一個行程(Process) 的各執行緒可共享那些資源？ 3、一個多元性工作的行程(Process)，可依其不同工作內容分割出多個執行緒(Threads)，其優點有為何？ 4、使用者執行緒(User Threads) 與核心執行緒(Kernel Threads) 有那些關係模型？ 5、當標的執行緒執行 “終止” 時，視系統的不同，有那兩種情況伴隨發生？ 6、設置執行緒池的理由為何？

第七章 CPU排程(Scheduling) 7-1 簡介 7-2 排程概念(Scheduling Concepts) 7-2-1 CPU與I/O週期(CPU and I/O Cycle) 7-2-2 CPU排程器(Scheduler) 7-2-3 搶先排程(Concept of Preemptive Scheduling) 概念 7-2-4 分配器(Dispatcher) 7-3 排程評量要件(Scheduling Criteria) 7-4 排程演算法(Scheduling Algorithms) 7-4-1 先到先執行(FCFS First-Come-First-Served Scheduling) 7-4-2 最短工作優先(SJF Shortest-Job-First Scheduling) 7-4-3 搶先排程( Preemptive Scheduling) 7-4-4 優先權排程( Priority Scheduling) 7-4-5循環分時 (RR Round-Robin) 排程 7-4-6多層佇列(Multilevel Queues) 排程 7-4-7多層回授佇列 (Multilevel Feedback-Queue) 排程 7-4-8多處理器 (Multi-Processor) 排程 7-5 排程評量(Algorithm Evaluation) 7-6 習題(Exercises) 7-7範例系統程式(Programming) 7-7-1 優先權排程(模擬7-4-4節)

7-1 簡介 CPU排程(Scheduling) 是多工作業系統(Multiprogramming Operating System) 的基石之一，當多個行程(Processes) 或執行緒(Threads) 在就緒佇列(Ready Queues) 中等待進入CPU時，系統如何選擇適當的行程優先進入CPU即謂 “CPU排程”。 本章除了對CPU排程作概念描述之外，另列出數種排程演算法(Algorithms) 及應用分析。

7-2 排程概念(Scheduling Concepts) CPU一個時間只能允許一個行程(例如P0) 進入執行，當行程P0執行完畢後，再輪由其他行程Pi依序進入CPU執行。此其間P0可能去執行I/O，而CPU也因等待P0而怠惰(Idle)，如此珍貴的CPU時間用於等待(Waiting) 實為可惜。

7-3 排程評量要件(Scheduling Criteria) 如7-2-2節所述，至今已發展出許多排程演算法，至於要選用那一種則無一定的定見，要配合當時的電腦系統與執行環境、與程式本身之條件而定。本節介紹5類評量要件，以其計量的數據評量出最佳選擇。

7-4 排程演算法(Scheduling Algorithms) 當行程置入就緒佇列(Ready Queue) 後，隨即等待系統依排程演算法選擇進入CPU，行程從進入CPU開始至離開CPU為止所需的時間是謂 “CPU時間(Burst Time)”，不同的演算法有其不同的執行意義，本節將探討目前常用的各類排程演算法。

7-4-1 先到先執行 (FCFS First-Come-First-Served Scheduling) 將就緒佇列(Ready Queue) 內等待的各行程，依先到先執行的法則排序進入CPU執行，如是法則是謂 “先到先執行排程(FCFS)”。

圖7-4-1-1

7-4-2 最短工作優先 (SJF Shortest-Job-First Scheduling) 於前節，我們已觀察到，於就緒佇列(Ready Queue) 內等待的各行程，將CPU時間較小的行程先選入CPU執行，可節省大量的平均等待時間，如是法則是謂 “最短工作優先排程(SJF )”。

圖7-4-2-1

7-4-3 搶先排程( Preemptive Scheduling) 如7-2-3節所述，同時考量時間(Time) 與權值(Weight) 的排程是謂 “搶先排程(Preemptive Scheduling)”。例如行程P1的權值高於P2的權值，理應先選P1後選P2，但於決選時刻，P1尚未抵達，只有P2出現，此時系統先選擇權值次高的P2，若P1隨後到達，系統再以當時的狀況重新考量最佳之選擇，其優點是不浪費等待的時間。

圖7-4-3

7-4-4 優先權排程( Priority Scheduling) 因為工作重要性的需要，可付予行程適當的優先權值(Priority)，優先等級較高的行程，優先被選擇進入CPU。

圖7-4-4

7-4-5循環分時 (RR Round-Robin) 排程 設有行程P1、P2、P3 依FCFS排序，將CPU時間切割成數個時間分量(Time Quantum) q，行程P1進入CPU在時間分量q範圍內作執行，如果未完成執行，跳出CPU，讓P2進入CPU。P1等待下一循環再進入CPU繼續執行，直至各行程執行完畢為止。如是作為是謂 “循環分時排程(RR)”。

圖7-4-5

7-4-6多層佇列(Multilevel Queues) 排程 在眾多行程中，為了管理方便，可將功能性相同的各行程納入同一群組(Group)，同一群組內，行程與行程間執行適當之排程(Suitable Scheduling)，群組與群組間亦執行適當之排程。如此雙線排程是謂 “多層佇列排程(Multilevel Queues Scheduling)” 如圖7-4-6。

圖7-4-6

7-4-7多層回授佇列排程 (Multilevel Feedback-Queue) 於前節，我們已認識多層佇列排程的缺點是：如果某群組的優先等級過低，則該群組的所有行程就可能失去進入CPU的機會。 為了改善上述缺點，我們設計多層回授佇列排程(Multilevel Feedback-Queue Scheduling) 如圖7-4-7，如果某群組之CPU時間超過規定之時間分量(Quantum Time)，系統即強迫將CPU使用權交付予較低層之群組使用，如此每一層群組都有進入CPU的機會。

圖7-4-7

7-4-8多處理器 (Multi-Processor) 排程 到目前為止，我們探討的排程模型均為一個CPU，如果系統擁有多個CPU，執行效率將大為提高且精彩，如此環境執行的排程是謂 “多處理器排程(Multi-Processor Scheduling)。

圖7-4-8-1

圖7-4-8-2

圖7-4-8-4

7-5 排程評量(Algorithm Evaluation) 於前數節中，我們已探討過多種排程方法，每一種方法都有其獨特的優點與缺點，我們也很難評量出那一種方法為最佳法則。除了排程方法外，當時的執行環境亦是重要影響因素之一。事實上，觀察實際執行的現象才是較為可靠的評量。

7-6 習題(Exercises) 1、何謂CPU排程(Scheduling)？ 2、何謂I/O型行程(I/O-Bound Process)？ 3、何謂CPU型行程(CPU-Bound Process)？ 4、何謂搶先排程(Preemptive Scheduling)？ 5、系統需要考量排程的關鍵時機為何？ 6、排程評量要件(Scheduling Criteria) 有那些？ 7、設有行程與其CPU時間如下，試以FCFS計算其平均等待時間？ 8、設有行程與其CPU時間如下，試以SJF計算其平均等待時間？ 9、設有行程與其CPU時間如下，試以Preemptive與SJF計算其平均等待時間？ 10、設有行程與其CPU時間如下，試以優先權排程計算其平均等待時間？ 11、著手執行評量，可類分那3個執行階層？

第八章 行程與同步並行(Process Synchronization) 8-1 簡介 8-2 並行條件(Concurrency Conditions) 8-3 臨界區(Critical Section) 8-4 兩任務演算法(Two-Tasks Algorithms) 8-4-1演算法1(Algorithm1) 8-4-2演算法2(Algorithm2) 8-4-3演算法3(Algorithm3) 8-5 硬體並行指令(Synchronization Hardware) 8-5-1 方法程序getAndset( ) 8-5-2 方法程序swap( ) 8-6 信號(Semaphores) 8-6-1 信號(Semaphores) 與臨界區(Critical Section) 8-6-2 信號(Semaphores) 與並行序列(Synchronization) 8-7 應用(Application) 8-8 習題(Exercises) 8-9範例系統程式(Programming) 8-9-1 臨界區演算法1(模擬8-4-1節) 8-9-2 臨界區演算法2(模擬8-4-2節) 8-9-3 臨界區演算法3(模擬8-4-3節) 8-9-4 臨界區硬體指令getAndset( ) (模擬8-5-1節) 8-9-5 臨界區硬體指令getAndset( ) (模擬8-5-2節) 8-9-6 號碼機與synchronized類別(模擬8-7節)

8-1 簡介 我們曾於5-5節述及合作行程(Cooperating Process)，於執行時，行程之間可相互影響，分享記憶體(Memory)，分享資料(Data)，但往往因管理不周嚴，使得資料失去一致性(Inconsistency)。例如有一個銀行帳戶，哥哥到銀行臨櫃存錢，同一時間，弟弟以提款卡到提款機取錢，如此同步並行，如果管理不當，資料失去一致性，帳戶餘額將會混亂錯誤。 因此、在多個行程同步並行時，如何保持資料的一致性(Consistency)，是行程作業的一個重要環節，本章將深入探討之。

8-2 並行條件(Concurrency Conditions) 如前述，在多個行程同步並行時，如何保持資料的一致性(Consistency)，是行程並行作業的重要一環，設有程式片斷： S1： a ← 5 S2： b ← a+1 S3： c ← a+2 S4： d ← b+c 圖8-2-1

S1： a ← 5 S2： b ← a+1 S3： c ← a+2 S4： a ← b S5： a ← c S6： print a 圖8-2-2

8-3 臨界區(Critical Section) 每一執行緒(Thread) 之寫入/讀取(W/R) 功能碼(Code)，均可視為該執行緒之臨界區(CS Critical Section)。於臨界區，執行緒可對共享資源(Shared Resource) 存取(Access) 資料，如共用記憶體或變數(Common Variables)、檔案(Files) 等。

8-4 兩任務演算法(Two-Tasks Algorithms) 於系統中，有多個執行緒(T1、T2、…、Tn) 等待執行，為了容易解說，將此n個執行緒類分為2種角色：(1) 使用者關心的執行緒Ti；(2) 其他執行緒Tj。例如使用者關心T3，則Ti = {T3}、Tj = { T1、T2、T4、…、Tn}。

圖8-4

8-4-1演算法1(Algorithm1) 圖8-4-1

8-4-2演算法2(Algorithm2) 圖8-4-2-1

8-4-3演算法3(Algorithm3) 圖8-4-3

8-5 硬體並行指令 (Synchronization Hardware) 在形式上或非形式上，可直接控制記憶體的指令是謂 “硬體控制指令(Hardware Instructions)”，本節關心的是將記憶體鎖住的指令(lock)，如果能將記憶體鎖住，防止不必要的執行緒作資料存取，8-4節所談的各演算法均可輕易迎刃而解。

8-5-1 方法程序getAndset( ) 圖8-5-1

8-5-2 方法程序swap( ) 圖8-5-2

8-6 信號(Semaphores) 於執行緒同步並行設計中，信號方法(Semaphores) 是一很有意義的一環，其可達成兩個重要意義：(1) 解決臨界區的問題、(2) 自動調配並行序列的連貫性。

8-6-1 信號(Semaphores) 與 臨界區(Critical Section) 圖8-6-1

8-6-2 信號(Semaphores) 與 並行序列(Synchronization) 圖8-6-2-1

圖8-6-2-2

8-7 應用(Application) 當我們走進高鐡車站，先到售票機按鈕買票，進入月台再依車票座位號碼找車箱座位。本節就以售票機為設計範例，如果有多個旅客同時按鈕買票，亦即同時進入售票系統之臨界區，此時各旅客可能領到相同座位號碼的車票(讀者是否還記得，高鐡通車時買票混亂之情形)。請讀者參考本章8-9節範例系統程式，以了解其混亂的原因與改進之方法。

8-8 習題(Exercises) 1、何謂 伯恩斯坦同步並行條件(Bernstein Condition) ？ 2、何謂臨界區(CS Critical Section)。於臨界區？ 3、同步並行須滿足那三個要件？ 4、何謂2任務演算法？ 5、使用者關心的執行緒Ti，有那三種關鍵機制訊息？ 6、何謂硬體控制指令(Hardware Instructions)？ 7、信號(Semaphore) 的概念為何？

第九章 死結(Deadlocks) 9-1 簡介 9-2 死結定義(Deadlock Definition) 9-3 死結特性(Deadlock Characterization) 9-3-1 必要條件(Necessary Conditions) 9-3-2 資源分配圖(Resource – Allocation Graph) 9-4 死結預防(Deadlock Prevention) 9-5 死結避免(Deadlock Avoidance) 9-5-1 銀行家概念(Conception of Banker) 9-5-2 安全演算法(Safety Algorithm) 9-5-3 資源要求演算法(Resource Request Algorithm) 9-5-4 單一裝置(Single Instance) 9-6 死結偵測(Deadlock Detection) 9-6-1 偵測演算法 9-6-2 單一裝置(Single Instance) 9-6-3 啟動偵測時機(Detection Algorithm Usage) 9-7 死結消弭(Recovery from Deadlock) 9-7-1 行程終止法(Process Termination) 9-7-2 資源釋放法(Resource Preemption) 9-8 習題(Exercises) 9-9 範例系統程式(Programming) 9-9-1 循環等待之死結(模擬9-3-2節)

9-1 簡介 在多工環境(Multiprogramming Environment)，隨時都有多個行程(Processes) 或執行緒(Threads) 競爭有限數量的資源(Resources)，如果執行緒Ti需要的資源Ri當時不方便(not Available)，Ti即轉為等待狀態(Waiting State)。 如上述，執行緒Ti需要資源Ri，此時若Ri被其他執行緒Tj控制佔有，而Tj也處於等待狀態，且不釋放Ri，如此現象是謂 “死結(Deadlock)”。

9-2 死結定義(Deadlock Definition) 死結形成的基本原因是資源(Resource) 的不敷使用，資源包括實體資源(Physical Resource) 和程式中的邏輯資源(Logical Resource)，若一味因資源不足而增加資源，則將付出不菲的代價(Payment)，故行程(Processes) 與資源(Resource) 的優良管理是避免死結(Prevent Deadlocks) 的最佳途徑。

圖9-2

9-3 死結特性(Deadlock Characterization) 系統陷入死結(Deadlock) 時，行程(Process) 無法完成執行，資源(Resource) 被工作綁住而無法脫身。

9-3-1 必要條件(Necessary Conditions) 要避免死結發生，須先了解死結發生的因素特性(Characters)，死結發生的必要條件是當下列四個狀態同時產生時： 互斥(Mutual Exclusion) 佔有與等待(Hold and Wait) 無搶先機制(No Preemption) 循環等待(Circular Wait)

9-3-2 資源分配圖 (Resource – Allocation Graph)

要求(Request)： 行程向系統提出某資源之使用要求，如圖9-3-2-1，行程P1對資源R1提出要求。其表示式為： 行程集合P = {P1}。 資源集合R = {R1}。 關係邊集合E = {P1→R1}。

圖9-3-2-1

2、佔用(Use) / 佔有(Hold)： 如圖9-3-2-2，行程P2佔用或佔有資源R1的一件裝置(Instance)。其中佔用(Use) 是P2正在使用該項資源R1；佔有(Hold) 是P2除了已抓取R1之外，尚等待要求其他資源，亦可能是因此造成死結之原因。表示式為： 行程集合P = {P2}。 資源集合R = {R1}。 關係邊集合E = { R1→P2}。

圖9-3-2-2

3、佔有(Hold) 與要求(Request)： 如圖9-3-2-3，P3除了已抓取R1之外，尚等待要求其他資源R2。表示式為： 行程集合P = {P3}。 資源集合R = {R1, R2}。 關係邊集合E = { R1→P3, P3→R1}。

圖9-3-2-3

4、循環等待(Circular Wait)： 如圖9-3-2-4，P1已佔有R1，且提出要求R2，但R2已被P2佔有；P2已佔有R2，且提出要求R1，但R1已被P1佔有。如此永久等待無法解開的迴圈是謂 “循環等待(Circular Wait)”，亦是造成死結的元兇原因。表示式為： 行程集合P = {P1, P2}。 資源集合R = {R1, R2}。 關係邊集合E = { R1→P1→R2→P2→R1 }。

圖9-3-2-4

5、迴圈(Cycle Graph)： 如圖9-3-2-5，雖然與圖9-3-2-4有一樣的迴圈，但在死結的意義上却不相同。於圖(a)，R1有兩件裝置(Instance)，P2不會永久等待，故不會產生死結。於圖(b)，當P3正在佔用R1的一件資源時，P2等待；一旦P3釋放R1，P2即不需再等待，故也不會產生死結。

圖9-3-2-5 (a) (b)

9-4 死結預防(Deadlock Prevention) 為了預防死結發生，我們可從上述之死結必要條件著手，亦即想盡方法不讓上述四個條件發生。 1、互斥(Mutual Exclusion) 2、佔有與等待(Hold and Wait) 3、無搶先機制(No Preemption) 4、循環等待(Circular Wait)

9-5 死結避免(Deadlock Avoidance) 本節提出避免死結(Avoidance) 以取代預防死結(Prevention) 之觀念。如圖9-5-1，(1) 安全區為絕無發生死結可能之區域，亦即無9-4節所述之死結必要條件。(2) 非安全區為已觸及死結的必要條件，但尚未真正產生死結。(3) 死結區為已發生死結。

圖9-5-1

圖9-5-1-1/圖9-5-1-2

9-5-2 安全演算法(Safety Algorithm) 當行程Pi需求資源Needi時，系統有足夠的可用資源提供使用，即Needi ≦ Available。如果如此狀態能滿足每一個行程，系統已處於安全狀態，且安排出行程安全序列<Pi, Pj, Pk, …>。其演算法為： 1. 宣告 work ← Available; finish[i] ← false; (其中 i = 0, 1, …, n-1) string ← Ø; 2. 依序測試 for (i=0; i<n; i++) if (finish[i] ==false) and (Needi≦work) then string ← string + “Pi”; goto step3; goto step 4; 3. work ← work + Allocation; finish[i] ← true; goto step 2; 4. 依序測試 for (i=0; i<n; i++) if finish[i] == true 表示行程Pi順利完成，如果每一行程均順利完成，系統在安全狀態; 5. print string;

圖9-5-2-1/圖9-5-2-2

9-5-3 資源要求演算法 (Resource Request Algorithm) 當行程Pi提出資源要求量Requesti，要求量不得多於需求量(Need)，即Requesti ≦ Needi，否則有致發生死結的可能；同時要求量亦不得多於可用量(Available)，即Requesti ≦ Available，否則須等待系統釋出足夠的資源。其演算法為： 1. 行程Pi提出資源要求Requesti; 2. if Requesti ≦ Needi then goto step 2; else 有致生死結的可能; 3. if Requesti ≦ Available then goto step 3; 4. 系統依照安全規則運行： Available ← Available – Requesti; Allocationi ← Allocationi + Requesti; Needi ← Needi – Requesti;

9-6 死結偵測(Deadlock Detection) 如前述，如果將系統一直維持在安全區內，雖可預防死結之發生，但也傷害了系統的效率。我們可放任系統於非安全區遊走在死結之邊緣外圍，並於一定時間之間隔，執行一次死結偵測，當發現有死結發生，立即執行挽救措施，雖然很危險，但可將系統效率推升至最高點。我們設計一些演算法，密切監視系統運行狀況。

9-6-1 偵測演算法 偵測演算法與9-5-2節之安全演算法是屬同一架構，當行程Pi要求資源時Requesti，系統沒有足夠的可用資源提供使用，即Requesti ≧ Available。如果如此狀態發生，系統已處於死結狀態。其演算法為： 1. 宣告 work ← Available; finish[i] ← false; (其中 i = 0, 1, …, n-1) 2. 依序測試 for (i=0; i<n; i++) if (finish[i] ==false) and (Requesti≦work) then goto step3; goto step 4; 3. work ← work + Allocation; finish[i] ← true; goto step 2; 4. 依序測試 for (i=0; i<n; i++) if finish[i] == false 表示行程Pi已處於死結狀態;

圖9-6-1-1 /圖9-6-1-2

9-6-2 單一裝置(Single Instance) 如前述，於資源分配圖，如果各資源類僅有一件裝置如圖9-6-2，只要有迴圈，就表示死結已發生。

圖9-6-2

9-7 死結消弭(Recovery from Deadlock) 當偵測到發生死結時，我們採取兩個對應步驟：通知系統管理員(Operator) 採用適當死結消弭措施；或是以信號告知作業系統起動死結消弭措施。死結消弭措施可由兩個切入點著手：(1) 從行程切入，(2) 從資源切入。

9-8 習題(Exercises) 1、何謂死結(Deadlock)？ 2、當一個行程使用資源時，有那三個過程？ 3、死結發生的必要條件為何？ 4、如何預防死結發生？ 5、如何避免死結發生？ 6、如9-5-2節，自行設計系統資源狀況，執行安全演算法。 7、如9-6-1節，自行設計系統資源狀況，執行偵測演算法。 8、何時啟動偵測演算法？ 9、消弭死結，有那兩種方法？

儲存管理(Storage Management) 第三篇 儲存管理(Storage Management)

第十章 記憶體管理(Memory Management) 10-1 簡介 10-2 記憶體之觀念(Concept of Memory) 10-2-1 地址方式(Address Binding) 10-2-2 邏輯地址 / 實體地址(Logical / Physical Address) 10-2-3 機動載入 / 連接(Dynamic Loading / Linking) 10-2-4 重疊(Overlays) 10-3 置換(Swapping) 10-3-1 回存裝置(Backing Store) 10-3-2 置換時間 10-3-3 重疊置換(Overlapped Swapping) 10-4 連續記憶體配置(Contiguous Memory Allocation) 10-4-1 記憶體保護(Memory Protection) 10-4-2 記憶體分配(Memory Allocation) 10-4-3 碎片(Fragmentation) 10-5 分頁(Paging) 10-5-1 分頁方法(Paging Methods) 10-5-2 硬體支援(Hardware Support) 10-5-3 框頁保護(Frames Protection) 10-5-4 框頁分享(Shared Pages) 10-6 區段(Segmentation) 10-7 區段分頁(Segmentation with Paging) 10-8 習題(Exercises) 10-9範例系統程式(Programming) 10-9-1區段應用(模擬10-6節)

10-1 簡介 於前數章節，我們談到多個行程(Processes) 競爭CPU的使用方法；於本章，我們將另談及多個行程(Processes) 競爭記憶體(Memory) 的應用。為了安排記憶體作最佳使用，過程中需要良好的管理，早期僅有單純的記憶體(Bare Machine) 使用，近期發展出置換(Swapping)、分頁(Paging)、與區段(Segmentation) 等方法，增加記憶體使用之效率。

10-2 記憶體之觀念(Concept of Memory) 一個行程或執行緒在進入CPU前，必須先置入主記憶體(Main Memory)，CPU直接對主記憶體(Main Memory) 隨機存取(random access) 資料，典型的指令執行週期(Instruction Execution Cycle) 如范紐曼(Von Neumann) 所提出之執行架構(如圖3-5-1)，由控制單元(CU Control Unit) 安排從主記憶體(Main Memory) 抓取(fetch) 指令碼(Instruction) 至邏輯運算單元(Arithmetic Logic Unit) 內之暫存器(Register) 作解碼(decode)，視指令碼之需要，再從主記憶體抓取執行所需的資料(Data)。執行完成後將結果(Result) 傳回主記憶體。等待執行下一個執行週期。

圖10-2 (a) (b)

10-2-1 地址方式(Address Binding) 當一個程式(Program) 從開始編輯(Editing) 到執行完畢(Execution)，其間各程式碼也隨著不同的過程(Stages / Time)，有著不同的記憶體地址方式(Address Binding)。

圖10-2-1

10-2-2 邏輯地址 / 實體地址 (Logical / Physical Address) 經由CPU處理過而產生的一批資料，可自成一組單元，有其自身之資料置放次序，此時各資料的次序位置是謂 “邏輯地址(Logical Address)”。如此儲存這些資料的空間是謂 “邏輯地址空間(Logical Address Space)”。

圖10-2-2

10-2-3 機動載入 / 連接 (Dynamic Loading / Linking) 一個完整的執行程式，除了有主程式(Main Program) 外，另有多個等待被呼叫的函數(Functions) 或副程式(Subroutine)，如圖10-2-3，這些程式碼均完整地儲存在實體記憶體(Physical Memory) 中。當被執行時，需先將程式碼載入(Load) 執行記憶體(Execution Memory) 或稱邏輯空間記憶體(Logical Address Space Memory)。 執行記憶體的容量可能不足以容納全部程式碼，除了主程式必須載入外，其他函數或副程式則於需要時才被載入，亦即未獲呼叫(call) 時不必載入，以節省有限的記憶體空間，如此之載入是謂 “機動載入(Dynamic Loading)”。

圖10-2-3

10-2-4 重疊(Overlays) 當一個程式的程式碼無法同時容納於執行記憶體時，我們可以重疊方法(Overlays)支援執行，先將經常需要執行的指令(Instructions) 與資料(Data) 置入執行記憶體，其他指令與資料則於需要時再載入，執行完畢後置換出，將記憶體空間留給次一批指令與資料使用，如此作為是謂 “重疊(Overlays)”。

10-3 置換(Swapping) 我們已了解，一個行程必須先置入執行記憶體(Main Memory)，才可進入CPU執行。如圖10-3，在主記憶體的行程(Process) 可視需要暫時置換移出至回存裝置(Backing Store)，或在回存裝置的行程亦可視需要暫時置換移入至主記憶體，如此移出移入是謂 “置換(Swapping)”。其機制是 “置換器(Swapper)”。

圖10-3

10-3-1 回存裝置(Backing Store) 回存裝置是一快速性能的記憶體裝置，一般來言為一磁碟或磁鼓，當行程從主記憶體被置換出(Swap out) 時，可在此暫時存駐，並等待時機再置換入(Swap in) 主記憶體。 回存裝置的容量至少要大於主記憶體的容量，換言之，需要有足夠容量容納主記憶體上所有的行程，如此才可勝任回存之任務(Task)。

10-3-2 置換時間 行程愈大，置換時間愈長，即置換時間與行程大小成正比。由圖10-3-2可知，行程在主記憶體的置換時間亦將影響CPU的工作效率： Ecpu = (T – (tin + tout)) / T

圖10-3-2

10-3-3 重疊置換(Overlapped Swapping) 於前節，我們認識，當行程在置換時，CPU無法工作以致處於等待狀態。為了解決此問題，我們可於主記憶體設置兩個以上之緩衝區(Buffers)，如圖10-3-3，當置換行程2之同時，可將已在緩衝區之行程3調入執行區進入CPU執行。如此作為是謂 “重疊置換(Overlapped Swapping)”，CPU將不再浪費在等待上。

圖10-3-3

圖10-4

10-4-1 記憶體保護(Memory Protection) 記憶體保護之方法有：(1) 界限保護(Bound Protection)，(2) 基底保護(Base Protection)

圖10-4-1 (b) (a)

10-4-2 記憶體分配(Memory Allocation) 記憶體(Main Memory) 隨時有行程(Processes) 進出，有些空間被佔用，有些空間未被使用，如圖10-4-2，這些未被使用之空白區域是謂 “未使用坑(Hole)”。

圖10-4-2

10-4-3 碎片(Fragmentation) 如圖10-4-3-1，設有記憶體如圖(a)，置入行程Pi後，剩餘未被佔用的空間是謂 “碎片(Fragmentation)，如圖(b)。

圖10-4-3-1 (b) (a)

圖10-4-3-2

10-5 分頁(Paging) 於前節，為了 “行程-記憶體” 作適當配對，我們飽受連續記憶體(Contiguous Memory) 與碎片(Fragmentation) 之苦。本節探討分頁(Paging)，其構想來自於： 1、指標運用(Using Pointers) 2、框頁運用(Using Frame)

圖10-5-1

圖10-5-2

10-5-1 分頁方法(Paging Methods) 範例如圖10-5-1-1，將行程的程式碼，在邏輯空間(Logical Space) 中分三頁置放，經過作業系統分頁表(Page Table) 之配置，將行程的Page0配置於實體空間(Physical Space) 的第3頁；行程的Page1配置於實體空間的第6頁；行程的Page2配置於實體空間的第1頁。

圖10-5-1-1

圖10-5-1-2

10-5-2 硬體支援(Hardware Support) 如圖10-5-2-1，TLB是以快速存取硬體材質製造，框頁數量不多，功能與分頁表(Page Table) 相同，但在存取速度上，TLB較分頁表快速許多。當 “邏輯-實體” 對應地址頁目配對時，除了必須記錄於分頁表外，另擇常用的頁目抄錄至TLB。

圖10-5-2-1

10-5-3 框頁保護(Frames Protection) 如圖10-5-3-1，我們可於分頁表(Page Table) 增設一個位元(Bit)，標註 “可用(Valid)” 與 “禁用(Invalid)”。 標註 “可用(Valid)” 是指當時可對該框頁執行存取；標註 “禁用(Invalid)” 是指當時禁止對該框頁執行存取，亦即對該框頁實施保護(Protection)。如圖10-5-3-1，實體空間的第5頁。

圖10-5-3-1

10-5-4 框頁分享(Shared Pages) 如圖10-5-4-1，行程P1之第0頁Data0與行程P2之第0頁Data0相同；行程P1之第1頁Data1與行程P2之第1頁Data1相同，因此P1與P2可分享實體記憶體(Physical Memory) 之Data0與Data1。其優點為可節省框頁。

圖10-5-4-1

10-6 區段(Segmentation) 如圖10-6-1，為了管理方便，系統將相近功能的程式碼以邏輯地址叢聚在一個區段內，亦可如分頁方法以區段表(Segment Table) 對映至實體記憶體。

圖10-6-1

圖10-6-2

圖10-6-3

10-7 區段分頁(Segmentation with Paging) 如圖10-7，我們將區段方法(Segmentation) 與分頁方法(Paging) 合併使用，其間對映過程： (1) 於區段表(Segmentation Table)，邏輯區段起始位址(Segmentation Number) 對映實體區段基底地址(Physical Base Address)； (2) 區段表(Segmentation Table) 中該區段之邏輯相對距離(Logical Offset) 對映至分頁表(Page Table) 之邏輯分頁目(Logical Pages)； (3) 於分頁表(Page Table)，邏輯分頁目(Logical Pages) 對映實體分頁目(Physical Pages)； (4) 綜合項(1) 之實體區段基底地址(Physical Base Address) 與項(3) 之實體分頁目(Physical Pages)，可將各區段以區段分頁方法(Segmentation with Paging) 完整地對映至實體記憶體。

圖10-7

10-8 習題(Exercises) 1、記憶體之地址(Address) 有那兩種表示方式？ 2、絕對地址與相對地址之關係為何？ 3、何謂邏輯地址(Logical Address)？ 4、何謂機動載入(Dynamic Loading)？ 5、何謂重疊(Overlays)？ 6、何謂置換(Swapping)？ 7、置換時間與CPU的工作效率有合關係？ 8、記憶體保護之方法有那些？ 9、行程-未使用坑之配對法則有那些？ 10、何謂內部碎片(Internal Fragmentation)？ 11、何謂外部碎片(External Fragmentation)？ 12、何謂快取分頁緩衝器(TLB Translation Look-aside Buffer)？

第十一章 虛擬記憶體(Virtual Memory) 11-1 簡介 11-2 虛擬記憶體之觀念(Concept of Virtual Memory) 11-3 分頁要求(Demand Paging) 11-4 框頁替換(Page Replacement) 11-5 頁框分配(Allocation of Frames) 11-6 輾轉混亂現象(Thrashing) 11-7 其他考量(Other Considerations) 11-8 習題(Exercises) 11-9範例系統程式(Programming) 11-9-1分頁設計(模擬11-3-2節)

11-1 簡介 於前章，我們很努力地探討記憶體與其管理，目的無非是要如何配合多工程式(Multiprogramming) 之執行，即記憶體如何同時(simultaneously) 容納多個行程(Processes)。於本章，我們更關切，無論行程有多大，在執行前，我們如何將該行程之全部程式碼先搬置於主記憶體內。 事實上，一定有某些行程(Processes) 大於主記憶體之實體容量，亦即在執行前，我們無法將該行程之全部程式碼先搬置於主記憶體內。此時我們可藉本章提出之虛擬記憶體方法尋求解決。

11-2 虛擬記憶體之觀念 (Concept of Virtual Memory) 我們已非常了解，任何要進入CPU執行的行程(Process) 均需先置入主記憶體，如果行程大於主記憶體的容量，我們無法將該行程的程式碼同時完整地置入主記憶體，亦即無法達到執行條件的要求(Execution Requirements)。

圖11-2

11-3 分頁要求(Demand Paging) 於一般作業系統，虛擬記憶體(Virtual Memory) 之形成，均是因執行 “分頁要求(Demand Paging)” 而產生的。同理、“區段要求(Segment Paging)” 亦可產生虛擬記憶體。

圖11-3

11-3-1 分頁要求觀念 (Concept of Demand Paging) 分頁要求器(Pager) 僅將需要執行的框頁置換入主記憶體，如此可節省記憶體之實體容量，及節省不必要框頁的置換時間。

圖11-3-1-1

圖11-3-1-2

11-3-2 分頁要求之執行意義 (Performance of Demand Paging) 於前節我們已了解，當系統檢視分頁表(Page Table) 之檢視位元(Valid / Invalid) 時，如果是v則表示該框頁已置入實體空間，可進入CPU執行；如果是i則表示該框頁尚未置換入實體空間，此時若被選中，則視為 “選頁錯誤(Page Fault)”，系統將執行 “選頁錯誤中斷(Page Fault Interrupt Trap)”。

11-4 框頁替換(Page Replacement) 以圖11-4為例，當執行行程(Process) P0時，有3個框頁要求，檢視分頁表知該3頁已置入實體記憶體之0~2頁，可立即執行P0。

圖11-4

11-4-1 框頁替換之觀念 (Concept of Page Replacement) 繼續上述範例，如圖11-4-1，行程P1有4個框頁要求，檢視分頁表，有2頁已置入實體記憶體之3~4頁，另外2頁P1_Pg2、P1_Pg3却無空間可置入(實體記憶體之5~6頁為Invalid不得置入資料)

圖11-4-1

11-4-2 先入先出框頁替換 (FIFO Page Replacement) 範例如圖11-4-2-1，Position Labels為時間位置，Demand Page Reference String為框頁要求序列，長方形為框頁(本例有3頁)，星號(*) 為撃中(Hit)。

圖11-4-2-1

畢勒得異常(Belady’s Anomaly) 圖11-4-2-2

11-4-3 最佳框頁替換 (Optimal Page Replacement) 依框頁要求序列，依序將每頁資料置入頁框，當頁框數量不足時，實施框頁替換，系統檢視未來各資料之使用機會，將機會最低的資料置出。如圖11-4-3

圖11-4-3

11-4-4 最近最少使用框頁替換 (Least Recently Used Page Replacement) 前節所述的最佳框頁替換，是預估未來的機會，要付出極高的代價，甚或不可行。本節之最近最少使用框頁替換(LRU Least Recently Used Page Replacement) 是從相反的方向來檢視，預估未來很困難，檢視過去的歷史記錄則很容易。其著眼點是如果此時使用過某資料，可能有機會再提出使用要求。如圖11-4-4

圖11-4-4

11-5 頁框分配(Allocation of Frames) 於作業系統，分頁要求是影響工作效率的重要因素之一，相對的，頁框數量的多寡却是影響此項因素的重要資源(Resource)。框頁分配(Allocation of Frames) 得到愈多，選頁錯誤(Page Fault) 愈少，撃中率(Hit Rate) 愈高，以致整體系統的工作效率(Efficiency) 也隨之提高。

11-6 輾轉混亂現象(Thrashing) 當一個行程(Process) 分配得到的頁框數量少於其最低需求數量時，系統應立即終止該行程，並將其已佔有的頁框分配給予其他行程使用。 當任何行程的頁框不足時，如11-3-1節所述，很快即發生 “選頁錯誤(Page Fault)”，該行程必須立刻執行框頁替換，但因頁框不足，所有的框頁均在使用中，沒有空間可供替換，選頁錯誤(Page Fault) 立即又再發生，前一個替換尚未解決，次一個替換又接踵而來，如此惡性分頁替換是謂 “輾轉混亂現象(Thrashing)”。

圖11-6-1

圖11-6-2

圖11-6-3

11-6-4 選頁錯誤頻率 (Page Fault Frequency) 我們已了解，當頁框數量不足時，擊中率降低，選頁錯誤率增加。如圖11-6-3，系統可設一選頁錯誤頻率上限，當到達上限時，表示頁框數量開始不足，系統應增遣頁框以供使用。如果選頁錯誤頻率仍不下降，表示已發生輾轉混亂現象(Thrashing)，系統應終止部份行程，減少競爭頁框的對手，同時釋出頁框。當到達下限時，表示頁框數量充裕，系統可減少頁框之數量，節省系統資源。

圖11-6-4

11-7 其他考量(Other Considerations) 由前述各節，我們認識到 “分頁作業(Page Operation)” 的重點考慮是在：(1) 分頁替換，與 (2) 頁框分配，其意義均是為了增加系統效率。除了前述各節述及的考量外，本節再探討一些其他考量。 1、預先分頁(Prepaging) 2、分頁大小(Page Size) 3、快取分頁緩衝器(TLB Translation Look-aside Buffer) 4、程式結構(Program Structure) 5、I/O鎖定

圖11-7-1

圖11-7-2

11-8 習題(Exercises) 1、為了節省使用空間，系統總是先檢視那些不會立刻使用的程式碼？ 2、使用虛擬記憶體方法，可以虛擬記憶體(Virtual Memory) 補助實體記憶體(Physical Memory) 之不足，其利益優勢為何？ 3、何謂 “懶惰置換(Lazy Swapping)”？ 4、何謂 “選頁錯誤(Page Fault)”？ 5、先進先出框頁替換法(FIFO Page Replacement) 之優缺點為何？ 6、最佳框頁替換(Optimal Page Replacement) 的優缺點為何？ 7、頁框數量的多寡如何影響系統的工作效率？ 8、理論上，一個行程至少應分配得到那些頁框？ 9、何謂全域替換(Global Replacement)？ 10、何謂局部替換(Local Replacement)？ 11、何謂 “輾轉混亂現象(Thrashing)” ？ 12、挽救輾轉混亂現象(Thrashing) 的方法為何？

第十二章 檔案系統介面(File System Interface) 12-1 簡介 12-2 檔案概念(File Concept) 12-2-1 檔案屬性特徵(File Attributes) 12-2-2 檔案操作(File Operations) 12-2-3 開啟 / 關閉檔案(Open / Close File) 12-2-4 鎖住 / 釋出檔案(Lock / Release File) 12-2-5 檔案類型(File Types) 12-3 檔案存取方法(Access Methods) 12-4 目錄結構(Directory Structure) 12-4-1 單層目錄(Single Level Directory) 12-4-2 雙層目錄(Two Level Directory) 12-4-3 樹狀目錄(Tree Structured Directories) 12-4-4 非迴路圖形目錄(Acyclic Graph Directories) 12-4-5 綜合圖形目錄(General Graph Directories) 12-5 檔案系統掛載(File System Mounting) 12-6 檔案分享(File Sharing) 12-7 檔案保護(File Protection) 12-8 習題(Exercises) 12-9 範例系統程式(Programming) 12-9-1讀取檔案屬性(模擬12-2-1節) 12-9-2檔案之寫入/讀取(模擬12-2-2節)

12-1 簡介 對使用者來言，檔案(File) 是能見度相當高的作業系統應用，無論是作業系統的程式(Program) 與資料(Data)、或是使用者的程式與資料，檔案都提供了線上(On Line)記憶體之存取機制(Access Mechanism)。 檔案系統可概分為兩類：(1) 檔案系統、與 (2) 目錄系統。檔案系統處理檔案本身的資料存取問題，目錄系統處理各檔案的歸類問題。也有少數大型電腦設置叢目錄系統(Partition)，處理各目錄的歸類問題。

12-2 檔案概念(File Concept) 電腦的實體儲存裝置有光碟、磁碟、與磁帶，檔案儲存於這些裝置，均不會因停電、關機、與重新啟動而丟失資料。 檔案(File) 是以一個名稱(Name) 集合有關係資料(Related Information) 的組合，亦即一個名稱及一串位元(Bits)、位元組(Bytes)、列(Lines)、與資料錄(Records)，從邏輯空間(Logical Space) 由作業系統對映至實體空間(Physical Space)。

12-2-1 檔案屬性特徵(File Attributes) 1、檔案名稱(Name) 2、檔案識別碼(Identifier) 3、檔案類型(Type) 4、檔案位置(Location) 5、檔案大小(Size) 6、檔案保護(Protection) 7、時間(Time)

12-2-2 檔案操作(File Operations) 檔案操作(File Operations) 是指系統可直接處理檔案的模式，經常執行的操作有：(1) 建立檔案(Creating a File)、(2) 寫入檔案(Writing a File)、(3) 讀取檔案(Reading a File)、(4) 刪除檔案(Deleting a File)、(5) 重新命名檔案(Renaming a File)、(6) 合併檔案(Appending New Information)、(7) 截斷檔案(Truncating a File)等

12-2-3 開啟 / 關閉檔案(Open / Close File) 當寫入檔案或讀出檔案之前，需先藉由系統呼叫open( )、或read( ) / write( ) 將檔案開啟(Open)；以close( ) 關閉檔案、或當執行完畢後系統自動將檔案關閉。 如圖12-2-3-1，系統設置 “開啟檔案表(Open File Table)”，將當時正被開啟的各檔案納入其中，使用者(Users) 與系統(System) 可於該表查詢已開啟的檔案，減免在記憶體搜尋所付出的代價。當檔案被關閉後，亦將於表中刪除該檔案。

圖12-2-3-1

圖12-2-3-2

圖12-2-3-3

12-2-4 鎖住 / 釋出檔案(Lock / Release File) 鎖住檔案(Lock File) 的意義是：除了某些特定行程(Specific Processes) 之外，其他行程(Other Processes) 均不得進出該檔案。 讀取鎖住(Readers Locks) 分享鎖住(Shared Lock) 委託鎖住(Mandatory Lock)

12-2-5 檔案類型(File Types) 通常於檔案名稱上註明檔案類型，將檔案名稱分為兩部份：主檔名(File Name)與副檔名(File Extension Name)，之間以句點(Period Character) 分隔。主檔名為檔案名稱，也即檔案的起始位置；副檔名為該檔案的類型(Type)，如testFile.java。 隨著不同的系統，檔案名稱也會受到一些限制，例如Dos系統：主檔名不得大於8個字元，副檔名不得大於3個字元。我們常見到的檔案類型如圖12-2-5。

圖12-2-5

12-3 檔案存取方法(Access Methods) 使用檔案資料(Information)，即是將檔案資料讀取(Read File) 至電腦系統記憶體、或是將電腦系統之資料寫入至檔案(Write File)，可統稱謂 “檔案存取(Access File)”。常用的存取方法有 (1) 循序存取(Sequential Access)，(2) 直接存取(Direct Access)，(3) 索引存取(Index Access)。 1、循序存取(Sequential Access) 2、直接存取(Direct Access) 3、索引存取(Index Access)

圖12-3-1

圖12-3-2

圖12-3-3

12-4 目錄結構(Directory Structure) 一般電腦系統均擁有數千個檔案(Files)，良好的管理是非常有必要的，檔案儲存在記憶體中，故檔案管理亦即是記憶體管理的延伸，例如於輔助記憶體(如磁碟)，我們可分為兩階段處理： 1、磁碟分割(Partitions) 2、建立目錄(Directory)

圖12-4 (a) (b)

12-4-1 單層目錄(Single Level Directory)

圖12-4-1

12-4-2 雙層目錄(Two Level Directory) 當某使用者註冊後，如圖12-4-2，系統立即將該使用者名稱建立於主檔目錄(MFD) 內，並允許該使用者建立自己的使用者目錄(UFD)，指向使用者檔案的入口(Entries)。

圖12-4-2

12-4-3 樹狀目錄 (Tree Structured Directories) 如圖12-4-3，樹狀目錄的特徵有： (1) 連通性(Connectivity) (2) 無循環迴圈(Acyclic Connection)

圖12-4-3

12-4-4 非迴路圖形目錄 (Acyclic Graph Directories) 首先我們須辨別何謂迴圈(Cyclic Connection)？何謂迴路(Cyclic Graph)？由圖12-4-4與圖12-4-5，可作非常清楚地說明，於圖12-4-4之rbcda是迴圈，但不是迴路；於圖12-4-5之abc是迴圈，亦是迴路。

圖12-4-4

圖12-4-5

12-5 檔案系統掛載(File System Mounting) 為了更靈活應用檔案系統，有些系統允許將一串次目錄系統(如圖12-5-1-(b)) 或檔案(File)，移動穿梭於主目錄系統，如此作為是謂 “檔案系統掛載(File System Mounting)。

圖12-5-1

圖12-5-2

12-6 檔案分享(File Sharing) 一個檔案的價值，與其被分享的程度是成正比的，因此作業系統對檔案分享的管理，亦是影響工作效率的一環。 依區域範圍，檔案分享可概分為本機範圍分享(Local File Sharing) 與網路範圍分享(Remote File Sharing)，前者是由本機系統的多個使用者，依被允許的權限分享檔案；後者是由網路上的多個使用者，依被允許的權限分享檔案，有關網路方面的問題，本書將爾後詳細討論。 無論是何種範圍，檔案分享能提昇檔案的價值，但也是非常危險的作為，系統須非常謹慎地作安全措施管理。

12-7 檔案保護(File Protection) 對於儲存於電腦系統中之資料(Information)，我們應確保其無實體損壞(Physical Damage)、與確保其適當存取(Proper Access)。 無實體損壞是指確保可信度(Reliability)，目前最完整的方法是定期複製檔案備存(Back up)；適當存取是指檔案保護(Protection)，如果是單人單工系統，將無存取保護的問題，如果是多人多工系統即需考量檔案保護如下： 1、存取類型(Type of Access)： 2、存取控制(Access Control)： 3、其他保護(Other Protection)：

12-8 習題(Exercises) 1、檔案屬性特徵項目有那些？ 2、經常執行的操作操作有那些？ 3、當行程關閉檔案時，系統應執行那些步驟？ 4、何謂委託鎖住(Mandatory Lock)？ 5、何謂建議鎖住(Advisory Lock)？ 6、檔案存取方法有那些？ 7、樹狀目錄的特徵有那些？ 8、綜合圖形目錄(General Graph Directories) 之缺點為何？ 9、造成綜合圖形目錄的原因為何？ 10、何謂 “掛載點(Mount Point)”？ 11、掛載可類分為那三種型態？ 12、檔案存取類型(Type of Access) 有那些？

第十三章檔案系統運作 (File System Implementation) 13-1 簡介 13-2 檔案系統結構(File System Structure) 13-3 檔案系統運作(File System Implementation) 13-3-1 檔案系統概念(Concept of File System) 13-3-2 分割區與掛載(Partitions and Mounting) 13-3-3 虛擬檔案系統(Virtual File System) 13-4 目錄運作(Directory Implementation) 13-5 空間分配方法(Allocation Methods) 13-5-1連續空間分配(Contiguous Allocation) 13-5-2鏈接空間分配(Linked Allocation) 13-5-3索引空間分配(Indexed Allocation) 13-5-4運作性能(Performance) 13-6 空白空間之管理(Free Space Management) 13-7 網路檔案系統(NFS Network File System) 13-8 習題(Exercises)

13-1 簡介 於前章我們已了解，檔案系統提供了線上(On Line Storage) 儲存裝置(Storage) 與檔案存取(Access Files) 機制。 本章將探討磁碟儲存裝置(Disk)、與在磁碟上如何執行檔案存取(File Access)，內容含及檔案系統結構(File System Structure)、磁碟空間分配(Allocate Disk Space)、標定資料位置(Track Data Location)、及提供儲存裝置與作業系統之執行介面(Interface)。

13-2 檔案系統結構(File System Structure) 在輔助記憶體(Secondary Storage) 種類中，磁碟(Disk) 是很重要的儲存裝置(Device)，且已為今日大多數電腦系統所採用，其原因是磁碟具有：(1) 重寫性(Rewritable)：寫入磁碟的資料，刪除後，相同的位置可再寫入其他資料。(2) 區塊性(Blocking)：可作區塊性資料之存取，以致可輕易執行檔案之直接存取(如12-3節所述)。 檔案系統(File System) 最重要的兩項工作為：(1) 如何定義(Define) 一個檔案及其屬性特徵(Attributes)？(2) 如何將邏輯檔案系統(Logical File System) 對映至實體檔案系統(Physical File System)？檔案系統是為多層設計(Layer Design)，如圖13-2，上端為邏輯空間(Logical Space)，下端為實體空間(Physical Space)。

圖13-2

13-3 檔案系統運作 (File System Implementation) 於前章12-2-2節，我們曾探討單純的檔案操作(File Operations)，於本節，我們將探討整體性的檔案運作(File System Implementation)。 檔案系統概念(Concept of File System) 分割區與掛載(Partitions and Mounting)

圖13-3-3

13-4 目錄運作(Directory Implementation) 選擇適當的目錄管理演算法(Directory Management Algorithms) 與空間分配(Directory Allocation)，對檔案的執行效率(Efficiency) 有其一定程度的影響。使用者(Users) 於目錄(Directory) 搜尋檔案的方法有： 1、線性串列(Linear List) 2、雜湊表(Hash Table)

13-5 空間分配方法 (Allocation Methods) 無可避免地，總是有多個檔案儲存在一個磁碟內，此時如何將磁碟的空間適當地分配給予各檔案，將影響磁碟空間之有效使用(Space Utilizing Efficiency)、與檔案存取(Access Files) 的速率。磁碟空間之主要分配方法有：連續空間分配(Contiguous Allocation)、鏈接空間分配(Linked Allocation)、索引空間分配(Indexed Allocation)。

圖13-5-1

圖13-5-2-1

圖13-5-2-2

圖13-5-3

13-6 空白空間之管理 (Free Space Management) 磁碟的空間是有限的(Limited)，當新檔案建立時，系統要搜尋空白空間(Free Space)來安置該新檔案；當檔案被刪除(Delete) 時，系統要管理這些被釋出(Released) 的空間。今日電腦系統，對空白空間的管理方法有： 1、位元記錄(Bit Vector) 2、連接串列(Linked List) 3、群組串列(Group List)

13-7 網路檔案系統 (NFS Network File System) 於前述13-3-3節，我們曾述及，虛擬檔案系統之組成架構有三層，本節所述的虛擬網路檔案系統亦是如此，如圖13-7：

圖13-7

13-8 習題(Exercises) 1、今日大多數電腦系統採用磁碟的原因為何？ 2、檔案系統(File System) 最重要的兩項工作為何？ 3、檔案系統是為多層設計(Layer Design)，可分為那幾習？ 4、虛擬檔案系統有那三層(Layers)？ 5、使用者(Users) 於目錄(Directory) 搜尋檔案的方法有那些？ 6、磁碟空間之主要分配方法有那些？ 7、連續空間分配之優缺點為何？ 8、鏈接空間分配的缺點為何？ 9、空白空間的管理方法那些？

輸入輸出(Input and Output) 第四篇 輸入輸出(Input and Output)

第十四章 輸入輸出系統(I/O Systems) 14-1 簡介 14-2 概念(Overview) 14-3 I/O硬體(I/O Hardware) 14-3-1 匯流排(Bus) 14-3-2 連接埠(Port) 14-3-4 中斷(Interrupts) 14-3-5 直接記憶體存取(Direct Memory Access) 14-4 I/O介面應用(Application I/O Interface) 14-5 核心I/O次系統(Kernel I/O Subsystem) 14-6硬體I/O操作(Transforming I/O to Hardware Operation) 14-7串流(Streams) 14-8執行效率(Performance) 14-9習題(Exercises) 14-10 範例系統程式(Programming) 14-10-1資料串流FileInputStream與FileOutStream(模擬14-7節) 14-10-2資料串流DataInputStream與DataOutStream(模擬14-7節)

14-1 簡介 電腦的兩大主要工作(Jobs)，一是前數章所探討的工作處理(Job Processing)，另一個即是I/O。因I/O的執行速率較慢，比較上系統似用較多的時間在處理I/O事宜。 作業系統用於I/O的部份，是在管理(Manage) 與控制(Control) 周邊裝置與I/O運作，本章將探討：(1) I/O硬體操作(Hardware)、(2) I/O服務(Service)、(3) I/O介面(Interface)、(4) I/O運作(Implement)、與 (5) 設計改善(Design) 等內容。

14-2 概念(Overview) 作業系統的主要設計考量，是在如何導引控制(Control) 與電腦連通的各個裝置。各I/O裝置無論是在功能上，或是在速度上都是各不相同，因此電腦系統也應以廣泛的能力來面對。為了慎重處理，作業系統於其核心(Kernel) 另設I/O次系統(Subsystem)。 在力求改善I/O技術的今日，時而出現兩個相互矛盾的方向：(1) 我們竭盡努力將I/O裝置標準化，期使I/O控制能統一且簡化；(2) 另一方面，我們又竭盡努力地開發與眾不同的I/O方法，以因應新的裝置與技術。

14-3 I/O硬體(I/O Hardware) 我們常用的周邊裝置(Devices) 有：(1) 儲存裝置(Storage Devices) 如磁碟(Disks)、磁帶(Tapes) 等；(2) 傳輸裝置(Transmission Devices) 如網路(Network)、數據機(Modems)、讀卡機(Cards) 等；(3) 人機介面(Human Interface) 如螢幕(Screen)、鍵盤(Keyboard)、滑鼠(Mouse)、搖桿(Joystick) 等。 無論電腦周邊設備有多廣，在概念上我們努力解決 (1) 如何將這些裝置與電腦掛載連接(Attached)？ (2) 如何以軟體程式(Software) 來控制這些硬體裝置(Hardware)？

14-3-1 匯流排(Bus) 周邊裝置以匯流排(Bus) 與電腦系統互通訊息(Signals) 和資料(Data)，裝置連線與匯流排之接點稱為連接埠(Connection Ports)，匯流排(Bus) 架構有三類：

圖14-3-1-1

圖14-3-1-2

圖14-3-1-3

圖14-3-1-4

14-3-2 連接埠(Port) 裝置與連線的接點之間設置 “連接埠(Port)”，通常是由4個暫存器所組成，狀態暫存器(Status)、控制暫存器(Control)、資料輸入暫存器(Data In)、資料輸出暫存器(Data Out)。內容如下： 狀態暫存器(Status) 控制暫存器(Control) 資料輸入暫存器(Data In) 資料輸出暫存器(Data Out)

14-3-3 握手與協定(Handshaking and Protocol) 為了容易解說，我們以前述14-3-1節之輪詢型(Pulling) 為例，本機系統(Host) 與裝置控制器D1之間，如何互通訊息？如圖14-3-3-1：

圖14-3-3-1

14-3-4 中斷(Interrupts) 如圖14-3-4-1，在硬體機制上，CPU與各裝置控制器之間，設有一中斷需求線(Interrupt Request Line)。系統執行中斷之步驟如下：

圖14-3-4-1

圖4-3-4-2

14-3-5 直接記憶體存取 (Direct Memory Access) 為了資料傳遞的靈活性與方便性，如果當時：(1) CPU非常忙碌；(2) 傳送大量資料；(3) 確定無傷害系統的資料，資料可不經過CPU之帶領，直接從儲存裝置(如磁碟) 傳遞至主記憶體(Main Memory) 之指定位置，如是之資料傳遞是謂 “直接記憶體存取(DMA Direct Memory Access)”。依圖14-3-5-1，直接記憶體之執行步驟如下：

圖14-3-5-1

14-4 I/O介面應用 (Application I/O Interface) I/O裝置種類繁多，如果要每種均兼顧，系統必將龐大且不易管理；如果不每種兼顧，則又將無法有效執行。為了解決如是問題，我們將作業系統之I/O部份，如圖14-4-1作分層設計(Multi−Level Design)。

圖14-4-1

圖14-4-2

14-5 核心I/O次系統 (Kernel I/O Subsystem) I/O工作範圍廣泛，作業系統於其核心(Kernel) 另設置核心I/O次系統(Kernel I/O Subsystem)，以方便管理排程(Scheduling)、緩衝(Buffering)、快取(Caching)、串置執行(Spooling) 等I/O事項。

14-6硬體I/O操作 (Transforming I/O to Hardware Operation) 從應用程式(Application) 提出I/O需求(I/O Request)，到從磁碟(Disk) 讀取檔案，其間過程如前述圖14-4-1，穿過I/O次系統層(I/O Subsystem Level)、裝置驅動程式層(Device Driver Level)、裝置控制器層(Device Controller Level)、到硬體裝置。如圖14-6，我們可觀查一個I/O需求(I/O Request) 的執行週期(Life Cycle)：

圖14-6

14-7串流(Streams) 當使用者行程(User’s Process) 與裝置(如磁碟) 作資料傳遞時，系統將資料安排成串流形態，如圖14-7，由三部份組成： (1) 串流頂前端(Stream Head) (2) 驅動尾後端(Driver End) (3) 串流模型(Stream Modules)

圖14-7

14-8執行效率(Performance) 系統之執行效率，對I/O有其深重的影響，CPU擔負著執行裝置驅動程式碼(Device Driver Codes)、與I/O排程(Schedule)；今日新型的電腦雖然在一秒內可同時執行上千個中斷常式(Interrupt Routines)，中斷仍然是電腦系統的一項重大負擔；網路資料之傳遞是I/O項目之一，其是否傳遞流暢亦影響執行效率。為了改善I/O執行效率，系統應： 1、如5-3-3節，減少內文切換次數(Context Switches)。 2、減少在記憶體中複製資料的次數。 3、降低中斷執行頻率(Frequency)，盡量執行大量資料傳遞(Large Transfer)、靈巧控制器(Controller)、聰明輪詢(Polling)。 4、使用DMA，增加同步傳遞資料的機會。 5、盡可能將行程關鍵資訊(Processing Primitives) 推向硬體，使裝置控制器(Device Controller) 更能配合CPU與匯流排(Bus) 之操作。 6、平衡CPU、記憶體、匯流排、I/O之執行，如果其中有一項特別熱烈，均將導致其他項目的怠惰(Idleness)，亦即降低系統效率。

圖14-8

14-9習題(Exercises) 1、在力求改善I/O技術的今日，出現那兩個相互矛盾的方向？ 2、何謂匯流排(Bus)之雛菊鏈型(Daisy Chaining) 架構？其優缺點為何？ 3、何謂匯流排(Bus)之輪詢型(Pulling) 架構？其優缺點為何？ 4、何謂匯流排(Bus)之獨立型(Independent) 架構？其優缺點為何？ 5、連接埠(Port) 是由那4個暫存器所組成？ 6、何謂不可遮罩中斷(Nonmaskable Interrupt) /遮罩中斷(Maskable Interrupt)？ 7、使用直接記憶體存取(DMA) 的時機為何？ 8、何謂I/O快取(Caching)？ 9、試請列出I/O需求(I/O Request) 的執行週期(Life Cycle)。 10、系統如何改善I/O執行效率？

第十五章 大量儲存結構(Mass Storage Structure) 15-1 簡介 15-2 磁碟結構(Disk Structure) 15-3 磁碟排程(Disk Scheduling) 15-4 磁碟管理(Disk Management) 15-5 置換空間管理(Swap Space Management) 15-6 磁碟矩陣結構 15-7 磁碟掛載應用(Disk Attachment) 15-8 穩定儲存應用(Stable Storage Implementation) 15-9 習題(Exercises)

15-1 簡介 就檔案系統(File System) 來言，我們曾於第十二章探討過使用者與檔案系統間之關係，於十三章探討過作業系統與檔案間之運作關係，於本章，我們將討論檔案與儲存裝置的問題，特別是磁碟(Disk) 之管理。

15-2 磁碟結構(Disk Structure) 新型磁碟機猶如是一個大型的一維資料矩陣(One Dimensional Array)，矩陣元素由邏輯區塊(Logical Block) 組成，亦即最小的傳輸單位(Unit of Transfer)。一個邏輯區塊通常有512個位元組(Bytes)，少數電腦系統採用1,024個位元組。 在實體(Physical) 上，如圖15-2，磁碟以磁區(Sector)、磁軌(Track)、磁柱(Cylinder) 為儲存位置單元。磁區0在最外圈磁軌之起點，多個磁片之相對磁軌組成磁柱。

圖15-2 (a) (b)

15-3 磁碟排程(Disk Scheduling) 作業系統如何安排存取磁碟之資料，將影響系統之執行效率。如圖15-3，通常存取磁碟資料可分4個時間步驟： (1) 磁軌搜尋時間(Seek Time) (2) 旋轉延遲時間(Rotational Latency) (3) 資料傳輸時間(Transfer Time) (4) 綜合執行時間(Bandwidth Scheduling)

圖15-3

15-3-1 先到先執行(FCFS Scheduling) 設有一範例，磁頭當時位置在50，磁碟等待佇列(Waiting Queue) 內之資料磁柱(Cylinder) 次序(Order) 為(或稱資料點次序)： 95, 155, 30, 120, 10, 125, 65, 70 若以先到先執行排程(FCFS First−Come−First−Serve Scheduling) 執行，磁頭(Disk Head) 掃過磁碟資料點的過程將如圖15-3-1：

圖15-3-1

15-3-2 最短搜尋時間先執行 (SSTF Scheduling) 每當磁頭存取一個磁柱資料點之後，立刻評估下一個資料點，選擇最近距離之資料點執行之，此為 “最短搜尋時間先執行排程(SSTF Shortest−Seek−Time−First Scheduling)”。圖15-3-2為SSTF之執行範例：

圖15-3-2

15-3-3 掃瞄排程(Scan Scheduling) 將磁頭從當時位置向磁碟的一端掃瞄，再向另一端掃瞄，當經過各資料點時，執行資料存取，此為 “掃瞄排程(Scan Scheduling)”。圖15-3-3為Scan之執行範例：

圖15-3-3

15-3-4 C−掃瞄排程(C−Scan Scheduling) 將磁頭從當時位置向磁碟的一端掃瞄，再從另一端開始掃瞄，避開重複資料區，當經過各資料點時，執行資料存取，此為 “C−掃瞄排程(C−Scan Scheduling)”。圖15-3-4為C−Scan之執行範例：

圖15-3-4

15-3-5 掃瞄判斷排程(Look Scheduling) 與 C−掃瞄判斷排程(C−Look Scheduling) 為了避免無謂的端點掃瞄，我們將Scan Scheduling改善為Look Scheduling，將C−Scan Scheduling改善為C−Look Scheduling(如圖15-3-5)：

圖15-3-5

15-3-6 磁碟排程分析 (Disk Scheduling Selection) 任何事均不可能完美無缺，電腦系統的各項措施也是一樣，一定有其優點與缺點，我們可選擇適當的時機，盡可能利用其優點屏棄其缺點。 當磁碟資料點之密度與存取頻率均高(Heavy Load) 時，我們採用FCFS，以避免有餓死(Starvation) 情況產生。 如果存取頻率很低，許久才有一個資料點出現，此時不論有多少排程方法，其作為均如FCFS排程。 檔案空間分配(File Allocation) 也是影響執行效率之一項因素(如13-5節)，如果是連續空間分配(Contiguous Allocation)，即多是鄰近資料點，將節省磁頭掃除的時間；如果是鏈接空間分配(Linked Allocation) 或是索引空間分配(Index Allocation)，資料點分散各個角落，將增加磁頭掃瞄的時間。

15-4 磁碟管理(Disk Management) 於前數章節，我們已探討許多關於磁碟的問題，本節將再繼續討論磁碟的管理事項，如磁碟格式化(Disk Formatting)、起動區塊(Boot Block)、與損壞區塊(Bad Blocks)等之管理。

15-4-1磁碟格式化(Disk Formatting) 一個全新的磁碟，除了佈滿磁性物質(Magnetic Material) 外，尚無法作為儲存記憶體(Memory)，必須要劃分出儲存單元磁區(Sectors)，才可配合磁碟控制器(Disk Controller) 讀寫資料，如此劃分之作為是謂 “低階格式化(Low Level Formatting)” 或稱 “實體格式化(Physical Formatting)”。

15-4-2起動區塊(Boot Blocks) 當開啟電源(Power Up) 啟動電腦、或重新啟動(Reboot) 電腦時，開機程式(Bootstrap Program) 亦隨之起動，由開機程式初始(Initializing) 作業系統，包括CPU的各暫存器(Registers)、裝置控制器(Device Controllers)、與主記憶體(Main Memory) 等。

15-4-3損壞區塊(Bad Blocks) 一個磁碟會因雜質或刮傷而損壞，遭受損壞的區塊稱為 “損壞區塊(Bad Block)”。如果損壞過於嚴重，整個磁碟應棄換不用；如果是非常輕微的損壞，則可跳過損壞區塊，繼續使用其他良好區塊。

15-5 置換空間管理 (Swap Space Management) 置換空間可設置於磁碟的檔案系統內(File System)、或設置於磁碟的獨立分割內(Partition)。(1) 若設置於檔案系統內，可將置換資料以檔案形態處理，其優點是簡單且易執行；缺點是要依檔案方式處理(如目錄、空間分配等)，將降低執行速率。(2) 若設置於獨立分割內，其優點是因無檔案系統牽拌，執行迅速；缺點是內部碎片(Internal Fragmentation) 將漸漸擴大，影響執行效率。

15-6 磁碟矩陣結構 今日磁碟之開發，體積愈來愈精巧，價格愈來愈便宜，電腦系統使用多個磁碟並不會付出特別的代價。將多個磁碟組織成 “磁碟矩陣(RAID Redundant Arrays of Inexpensive Disks)”，一則可增加儲存資料的安全可信度(Reliability)，一則可以並行方式(Parallelism) 增加執行速率。

15-6-1安全可信度(Reliability) 我們可以多個磁碟執行鏡影(Mirroring) 操作，同時將資料寫入兩個磁碟，亦即一個邏輯磁碟(Logical Disk) 由兩個實體磁碟(Physical Disk) 組成。當一個磁碟受損，另一個磁碟可將資料重新補救。

15-6-2並行方式(Parallelism) 既然電腦系統已經使用多個磁碟，我們可將其安排成並行處理(Parallelizing)，以節省執行時間，理論上，假設1個資料1個磁碟的存取時間為t；則1個資料n個磁碟的並行存取時間將為t / n。 如果資料是以位元組(Byte) 為單位，每一個位元組有8個位元(Bits)，我們可以八個磁碟對應分置這些資料，第1個位元分置於第1個磁碟，第2個位元分置於第2個磁碟，以此類推。當八個磁碟同時並行存取資料時，其速度將較一個磁碟快8倍。以位元(Bit) 為分置單位者是謂 “位元階層分置(Bit Level Striping)”，以區塊(Block) 為分置單位者是謂 “區塊階層分置(Block Level Striping)”。

15-6-3磁碟矩陣階層(RAID Level) 於15-6-1節，我們談到鏡影(Mirroring) 操作，將資料同時寫入兩個磁碟，雖然有極佳的安全可信度，但也付出了相當的代價。除此之外，還可使用其他我們熟悉的偵錯方式，如檢查碼(Parity Check Codes)、漢明碼(Hamming Codes) 等，將這些方式應用在磁碟矩陣(RAID)，可類分成數個如下之使用階層：

圖15-6-3-0 圖15-6-3-1 圖15-6-3-2

圖15-6-3-4 圖15-6-3-5 圖15-6-3-6

16-6-4磁碟矩陣階層分析(Selecting a RAID Level) RAID 0將所有的磁碟都用於儲存資料，優點是使用效率最高，又因是分置(Striping)儲存，可執行同步存取，增加執行速率；缺點是一旦有磁碟損壞，即無補救之途徑。 RAID 1將資料鏡影(Mirroring) 兩個磁碟，優點是當有磁碟損壞時，可立刻以另一個磁碟的資料修補之，安全可靠性最高；缺點是以兩倍數量的磁碟儲存資料，使用效率最低，又因未安排分置儲存，無法執行同步存取。 RAID 0+1將資料先分置於一組磁碟，再鏡影複製於另一組磁碟，優點是因是分置(Striping) 儲存，可執行同步存取，且當有磁碟損壞時，可立刻以另一個磁碟的資料修補之，安全可靠性最高；缺點是以兩倍數量的磁碟儲存資料，使用效率最低。 RAID 1+0將資料鏡影寫入兩組磁碟，再將第一組資料分置(Striping)，優點是以第一組磁碟執行同步存取，以第二組磁碟作原始資料修補；缺點是以兩倍數量的磁碟儲存資料，使用效率最低。理論上RAID 1+0 較RAID 0+1更安全可靠。 RAID 2使用漢明碼概念，優點是可在能力範圍內自動修補錯誤，安全可靠性與RAID 1相等，且使用數量較少的磁碟執行修補任務。 RAID 3使用單一檢查碼概念，優點是僅以一個磁碟執行偵錯任務，節省資源；缺點是僅能偵錯，無法修補錯誤。 RAID 4與RAID 3的意義相同，不同者是以區塊(Block) 為分置單位，可用於大量資料的傳遞。 RAID 5與RAID 4的意義相同，不同者是將資料與檢查碼依序分置(Striping) 於各磁碟，以免一個磁碟損壞，所有檢查碼均遺失。 RAID 6採用Reed−Solomon Codes方法，目前已少有電腦系統採用。

15-7 磁碟掛載應用(Disk Attachment) 電腦系統與磁碟間之掛載用可類分為：(1) 本機掛載儲存裝置(Host Attached Storage)、(2) 網路掛載儲存裝置(Net Work Attacked Storage)、(3) 儲區網路(Storage Area Network)。

15-7-1本機掛載儲存裝置 (Host Attached Storage) 系統經過I/O，對掛載於本機的裝置執行資料存取，依RAID概念，今日微電腦系列常使用的磁碟組織有IDE與SCSI，其結構如圖15-7-1。

圖15-7-1

15-7-2網路掛載儲存裝置 (Network Attacked Storage) 電腦系統可經過網路，對儲存裝置存取資料，如此作為是謂 “網路掛載儲存裝置(NAS Network Attached Storage)”，如圖15-7-2，Servers對NAS存取資料，Clients對NAS存取資料。

圖15-7-2

15-7-3儲區網路 (Storage Area Network) 網域是否暢通，是影響網路操作效率的重要因素，網域資源非常珍貴，盡可能要屏除不必要的浪費，如前節所述之NAS，在使用上將與Server−Client競爭網域頻寬，影響網路傳輸效率。

圖15-7-3

15-8 穩定儲存應用 (Stable Storage Implementation) 一個良好的電腦系統應具有穩定的儲存裝置，亦即有一個不會產生錯誤的儲存系統。當一個磁碟有錯誤發生時，系統立即安排： (1) 將另一個儲存相同資料的鏡影磁碟取代該受損磁碟； (2) 使用除錯碼技術(如漢明碼等) 將錯誤修補之。 前述15-6-3節所描述之RAID即是維護穩定儲存的良好儲存裝置。

15-9 習題(Exercises) 1、於磁碟運用，何謂等角速率(CAV Constant Angle Velocity)？ 2、於磁碟運用，何謂等線性速率(CLV Constant Linear Velocity？ 3、通常存取磁碟資料有那4個時間步驟？ 4、一個I/O需求(I/O Request) 內容應包含那些資訊？ 5、FCFS的優缺點為何？ 6、FCFS的優缺點為何？ 7、Scan的優缺點為何？ 8、C−Scan的優缺點為何？ 9、掃瞄判斷排程(Look Scheduling) 與C−掃瞄判斷排程(C−Look Scheduling) 的優缺點為何？ 10、置換空間設置於磁碟的檔案系統內(File System)、或設置於磁碟的獨立分割內(Partition)。兩者有何差別？ 11、試請分析RAID各階層。 12、何謂IDE？ 13、何謂SCSI？

分散式系統(Distributed System) 第五篇 分散式系統(Distributed System)

第十六章 分散式系統結構(Distributed System Structures) 16-1 簡介 16-2 概念(Background) 16-2-1 分散式系統之優點(Advantages of Distributed Systems) 16-2-2 分散式作業系統之類型(Types of Distributed Operating System) 16-3 節點連接(Topology) 16-4 網路通訊(Communication) 16-4-1 名稱解析(Naming Resolution) 16-4-2 路由策略(Routing Strategies) 16-4-3 連接策略(Connection Strategies) 16-4-4 衝突避免(Contention) 16-5 網路通訊協定(Communication Protocols) 16-6 網路故障處理(Robustness) 16-7 習題(Exercises) 16-8範例系統程式(Programming) 16-8-1網路節點連接(模擬16-3節) 16-8-2網路節點連接(模擬16-4-1節) 16-8-3 網路線路/資料交換(模擬16-4-3節)

16-1 簡介 分散式系統(Distributed System) 是多個處理器(Processors) 的組合，各處理器散置於各不同地區，彼此間互不共享記憶體，各有其自己的記憶體(Memory)，以地區網路(LAN Local Area Network) 或廣域網路(WAN Wide Area Network) 互通訊息。本章將探討分散式系統之結構、及使用之網路。

16-2 概念(Background) 分散式系統(Distributed System) 是多個處理器(Processors) 的組合，從小型的手持微電腦、個人電腦、到大型的工作站，散置於各不同地區(Sites)，由網路互相連通。

16-2-1 分散式系統之優點 (Advantages of Distributed Systems) 建置分散式系統至少有四個理由：資源分享(Resource Sharing)、計算迅速(Computation Speedup)、可靠性佳(Reliability)、與便利通訊(Communication)。 1、資源分享(Resource Sharing) 2、計算迅速(Computation Speedup) 3、可靠性佳(Reliability) 4、便利通訊(Communication)

16-2-2 分散式作業系統之類型 (Types of Distributed Operating System) 本節將介紹兩類網路導向作業系統(Network Oriented Operation System)：(1) 網路作業系統(Network Operating System) 與 (2) 分散式作業系統(Distributed Operation System)。在網路運用上，前者較後者容易操作；在存取儲存裝置上，後者較前者容易操作。 1、網路作業系統(Network Operating System) 2、分散式作業系統(Distributed Operation System)

16-3 節點連接(Topology) 分散式系統是將散置於各處的處理器(Processors) 以網路連接，互通訊息。其中有許多連接方式，各有其優缺點，我們考量的重點有： (1) 實體安裝代價(Installation Cost) (2) 通訊時間代價(Communication Cost) (3) 執行方便考量(Availability)

圖16-3-1

圖16-3-2

圖16-3-3

圖16-3-4

圖16-3-5

16-4 網路通訊(Communication) 當探討網路通訊，我們須考量：(1) 名稱解析(Naming Resolution)，兩個行程(Processes) 如何在廣大的網域中互相定址對方？ (2) 路由策略(Routing Strategies)，如何在網域中選擇傳遞資料之途徑？ (3) 連接策略(Connection Strategies)，網路中如何安排多個行程同時傳遞資料？ (4) 衝突避免(Contention)，當發生網路上爭議的問題時，如何解決？

16-4-1 名稱解析(Naming Resolution) 網路上兩個行程(Processes) 若要互通訊息，首先須定址對方，知道對方的位置之後，才能將資料傳遞給對方，或從對方下載資料。網路上電腦節點之名稱即是該節點的地址，通常有兩種表示方式：識別地址碼(Host Identifier)、與識別名稱(Host Name)。

16-4-2 路由策略(Routing Strategies) 當網路中兩節點相互通訊，其間安排資料傳遞的途徑是謂 “路由策略(Routing Strategies)”。每一個網路地區均設有路由表(Routing Table)，詳載資料可傳送的各種途徑(Alternative Paths)、及傳遞之時間代價(Cost) 等資訊(Information)，表中內容隨周遭環境之變化而自動更新。資料傳遞方式可概分為：(1) 固定路徑(Fixing Routing)、(2) 虛擬路徑(Virtual Routing)、(3) 機動路徑(Dynamic Routing)。

圖16-4-2

16-4-3 連接策略(Connection Strategies) 當網路上兩個行程(Processes) 相互通訊時，兩行程間建立起通訊管道(Communications Sessions)，在此時段期間，該兩行程佔用連通線(Connection Lines) 以交換資料(Switching Data)，資料交換完畢後，再釋出連通線供其他行程使用。交換資料的方式可類分為：線路交換(Circuit Switching)、資料交換(Message Switching)，與封包交換(Packet Switching)。 1、線路交換(Circuit Switching) 2、資料交換(Message Switching) 3、封包交換(Packet Switching)

16-4-4 衝突避免(Contention) 網路上電腦節點眾多，每條連線總有多個節點同時使用，因此傳遞的資料時有衝突混亂，如果不設立防範機制，將無法順利傳遞資料。目前網路上常用的防範機制有：載體偵測法(CSMA Carrier Sense with Multiple Access)、衝突警告法(CD Collision Detection)、與輪序傳遞法(Token Passing)。 1、衝突偵測法(CSMA) 2、衝突警告法(CD Collision Detection) 3、令牌傳遞法(Token Passing)

16-5 網路通訊協定 (Communication Protocols) 網路通訊協定(Communication Protocols) 是以多階層(Multiple Layers) 方式設計，網域網路採用國際標準組織(ISO International Standards Organization) 所提出的協定(Protocol)，其模型如圖16-5-1：

圖16-5-1

圖16-5-2

圖16-5-3

16-6 網路故障處理(Robustness) 網路節點眾多，發生故障的機會更是稀鬆平常，如連線故障(Failure of Link)、電腦節點故障(Failure of Site)、資料遺失(Loss of Message) 等。 為了維護網路隨時保持良好狀態，網路應有能力執行：偵測故障(Detect Failure)、重組系統(Reconfiguration)、與修補故障(Recovery from Failure)。 1、偵測故障(Detect Failure) 2、重組系統(Reconfiguration) 3、修複故障(Recovery from Failure)

16-7 習題(Exercises) 1、分散式系統有那些優點？ 2、試請比較網路作業系統(Network Operating System) 與分散式作業系統(Distributed Operation System) 之優缺點？ 3、常用的連線形式有那些？ 4、當某地區電腦節點A要定址另一節點B時，其作業系統要求網址解析的執行步驟為何？ 5、於區域網路內，各節點與閘道節點(Gateway) 之間以何種方式連接？ 6、何謂線路交換(Circuit Switching) ？ 7、何謂資料交換(Message Switching) ？ 8、何謂封包交換(Packet Switching) ？ 9、試請敘述國際標準組織(ISO International Standards Organization) 所提出的網路協定(Protocol) 各層之內容。 10、UDP與TCP有何差異？ 11、當網路某裝置發生故障時，我們如何偵測故障？

第十七章 分散式檔案系統 (Distributed File System) 17-1 簡介 17-2 概念(Background) 17-3 名稱與通透性(Naming and Transparency) 17-3-1 名稱結構(Naming Structure) 17-3-2 名稱方案(Naming Schemes) 17-4 遠端檔案存取(Remote File Access) 17-4-1 快取方案(Caching Scheme) 17-4-2 快取位置(Cache Location) 17-4-3 更新快取資料(Cache Update) 17-4-4 一致性(Consistency) 17-4-5 快取與遠端服務之比較( 17-5 檔案複製(File Replication) 17-6 習題(Exercises) 17-7範例系統程式 17-7-1遠端檔案儲存(模擬17-4節) 17-7-2遠端檔案複製(模擬17-5節)

17-1 簡介 於前一章我們曾討論網路結構(Distributed System Structure) 與通訊協定(Communication Protocols)，於13章我們曾討論檔案系統運作(File System Implement)，本章我們將結合此兩章之內容，探討檔案系統如何在網路上運作，亦即如何執行分散式檔案系統(DFS Distributed File Systems)？

17-2 概念(Background) 網路上蘊藏著許多服務項目(Services)，電腦節點亦各有其不同之工作地位，伺服端電腦節點(Server) 提供軟體服務機制(Software Service)；客戶端電腦節點(Clients) 連通服務機制，以網路作業系統作為服務介面(Interface)，執行有關之服務項目。

17-3 名稱與通透性(Naming and Transparency) 使用者(Users) 存取邏輯資料(Logical Data) 的切入點是檔案名稱(File Name)，在單機應用上，檔案名稱即是儲存檔案資料的起始地址，如12-2-1節曾述，使用者(Users) 使用檔案名稱(File Name)，例如testFile.java；電腦系統使用檔案識別碼(File Identifier)，例如1234。在網路應用上，檔案儲存於網路某個電腦節點，故檔案名稱應包括電腦節點名稱、與檔案本身名稱，如16-4-1節曾述，使用者(Users) 使用檔案名稱(File Name)，例如chia.tf.edu.tw / testFile.java；電腦系統使用檔案識別碼(File Identifier)，例如163.15.40.243 / testFile.java。 讀者有經驗，在單機應用上，當編輯完成一個檔案後，我們設定檔案名稱再將其存檔，此時我們知道的是一個已建立的檔案，我們不知道檔案的儲存地址，也沒必要知道，只要有名稱我們即可對該檔案執行資料存取。以此類推網路檔案系統，我們不必知道檔案儲存在那一個節點，只要知道檔案名稱，即可對該檔案執行存取資料，如此作為是謂DFS之 “透通性(Transparency)”。

17-4 遠端檔案存取(Remote File Access) 假設DFS以前節所述之名稱方案(Naming Scheme) 定名，使用者透過遠端服務機制(Remote Service Mechanism) 存取遠端檔案，提出之存取需求(Request) 在DFS之導引下抵達伺服端(Server)，DFS將需求結果從伺服端傳回至客戶端之使用者，如此作為是謂 “遠端檔案存取(Remote File Access)”。其中使用的遠端程序呼叫(RPC Remote Procedure Call) 與4-4節存取磁碟資料(Access Disk) 之系統呼叫(System Call) 類似，不同者前者須經過網域節點之定位。

圖17-4

17-5 檔案複製(File Replication) 為了方便使用者(User) 使用，如17-3-1節曾述及之名稱透通性(Naming Transparency)，作業系統安排檔案複製透通性(Replication Transparency)，使用者只關心檔案名稱，不必知道複製檔案的位置(Location)；複製檔案的位置由系統導引安排。 檔案複製的優點是增加可靠性(Reliability)，不會因硬體損壞而遺失資料；其缺點是一旦更新(Update) 資料時，需連絡所有的複製檔案同步更新，系統將付出可觀之代價。

17-6 習題(Exercises) 1、檔案系統之軟體本質服務項目有那些？ 2、何謂檔案名稱之透通性(Transparency)？ 3、何謂位置透通性(Location Transparency) ？ 4、何謂位置獨立性(Location Independency) ？ 5、DFS設定檔案名稱有那三種定名方案？ 6、快取資料的儲存位置可從那四個觀點來考量？ 7、客戶端將更新資料傳送給伺服端的時機有那三種？ 8、試述檔案複製的缺點。

第十八章 分散式系統之整合 (Distributed Coordination) 18-1 簡介 18-2 事件序列(Event Ordering) 18-3 互斥(Mutual Exclusion) 18-4緊密聚合(Atomicity) 18-5死結處理(Deadlock Handling) 18-6習題(Exercises) 18-7範例程式 18-7-1網路集中/協調(模擬18-3-1節)

18-1 簡介 於第八章我們曾討論在單機系統環境(Computer System Environment) 下，一個行程(Process) 之執行流程，也討論多個行程之並行流程，其中如並行條件(Concurrency Conditions)、臨界區(Critical Section)、信號(Semaphores) 等問題，本章將以同樣的問題觀點，在分散式系統環境(Distributed System Environment)下，討論多個行程之並行流程。 於第九章我們曾討論在單機系統環境(Computer System Environment) 下，死結定義(Deadlock Definition)、死結預防(Deadlock Prevention)、死結避免(Deadlock Avoidance)、死結偵測(Deadlock Detection)、死結消弭(Recovery from Deadlock) 等問題，本章亦將以同樣的問題觀點，在分散式系統環境(Distributed System Environment)下，討論死結的問題。

18-2 事件序列(Event Ordering) 於4-2-1節曾述及，我們在編輯器上寫的程式碼是謂 “程式(Program)”；當程式上的指令被CPU讀取執行時是謂 “行程(Process)”；行程流程中執行的事項是謂 “事件(Event)”。如圖18-2，行程P依序執行p1、p2、…、pn等事件(Events)。

圖18-2

18-2-1先後關係式(Happened−Before Relation) 一個執行於集合(Sets) S之關式元(Relation) R 被稱為 “偏序(Partial Order)”，如果該R滿足： (1) 反身律(Reflexive)：即 aRa，其中a是S之任一元素(Element)； (2) 反對稱律(Anti-Symmetric)：即 當有 aRb 且 bRa 時，則有 a = b； (3) 遞移律(Transitive)：即 當有 aRb 且 bRc 時，則有 aRc。

圖18-2-1-1

圖18-2-1-2

18-2-2應用(Implementation) 在電腦系統操作中，有許多執行項目需要事件之序列資料，如資料更新與複製、資源佔用與釋放、資料輸出與接收等。於單機系統可以輕易地辨識先後次序，但於網路多機系統却不易辨識。 於前節我們己粗略探討事件序列，本節將作更進一步的實用探討。我們記錄每一事件的發生時間，如圖18-2-2-(a)，p1為100、q1為100、q2為200，此為 “時間戳記(TS Timestamp)。

圖18-2-2

18-3 互斥(Mutual Exclusion) 我們曾於第八章探討單機之互斥操作，本節將探討在分散式系統環境(Distributed System Environment) 下，多個行程之互斥操作。 在分散式系統環境(Distributed System Environment) 下，互斥(Mutual Exclusion) 之定義(Definition) 是不允許有兩個行程(Processes) 同時在臨界區(Critical Section) 操作。在執行上，可類分為集中式執行(Centralized Approach)、與分散式執行(Distributed Approach)。

圖18-3-1

圖18-3-2

圖18-4

18-4緊密聚合(Atomicity) 有些工作必須緊密聚合(Atomicity) 連續地執行，在單機系統(Computer System) 上並不困難，例如執行批次工作(Batch)。但在分散式系統(Distributed System) 上，却不易整合執行。假設有一個工作(Transaction) T，具有兩個特性：(1) 龐大複雜，必須由多個電腦分擔處理；(2) 因內容需要，必須緊密聚合連續地執行。此時我們必須安排分散式之緊密聚合執行(Distributed Atomicity)。

圖18-4-1

18-5死結處理(Deadlock Handling) 我們曾於第九章詳細探討單機系統(Computer System) 之死結處理，其中之死結預防(Deadlock Prevention)、死結避免(Deadlock Avoidance)、死結偵測(Deadlock Detection)、死結消弭(Recovery from Deadlock) 等之觀點仍可用於分散式系統(Distributed System)。

圖18-5-2-1

圖18-5-2-2

圖18-5-2-3

圖18-5-2-1-1

圖18-5-2-1-2

圖18-5-2-2-1

圖18-5-2-2-2

18-6習題(Exercises) 1、何謂偏序(Partial Order) 關係？ 2、試述 “先後關係式” 之特性。 3、在分散式臨界區互斥之操作流程中，其執行困擾處為何？ 4、在執行互斥流程中，何謂令牌傳遞執行(Token Passing Approach)？ 5、令牌傳遞法(Token Passing Approach) 須注意那些事項？ 6、何謂兩階段協定(2PC Two−Phase Commit Protocol)？ 7、2PC故障處理之方式為何？ 8、於時間戳記優先演算法(Timestamp Priority Algorithm) 中，何謂消極方式(Wait−die Scheme)？ 9、死結處理之時間戳記優先演算法中，何謂積極方式(Wound Wait Scheme)？ 10、死結處理之集中式執行(Centralized Approach) 有那三種檢視時間點？

保護與安全(Protection and Security) 第六篇 保護與安全(Protection and Security)

第十九章 保護(Protection) 19-1 簡介 19-2 保護的目的(Goal of Protection) 19-3 保護之定義域 (Protection Domain) 19-3-1 定義域結構(Domain Structure) 19-3-2 定義域代表(Domain Representations) 19-4 矩陣執行(Access Matrix) 19-4-1複製功能(Copy) 19-4-2擁有者功能(Owner) 19-4-3控制功能(Control) 19-5 矩陣應用(Implementation Matrix) 19-5-1 全域表格(Global Table) 19-5-2 物件權限串列(Access Lists for Objects) 19-5-3 定義域能力串列(Capability Lists for Objects) 19-6 習題(Exercises) 19-7範例系統程式(Programming) 19-7-1矩陣應用(模擬19-5節)

19-1 簡介 系統中、通常都有多個行程(Processes) 正在執行，為了讓這些行程得以在不受干擾的環境下執行工作，系統應有一些保護措施(Protections)。只有系統允許(Proper Authorization) 的行程，才能使用特定的檔案(File)、記憶體(Memory)、CPU、或系統資源(Resource)。 系統保護機制控制(Controlling) 程式(Programs)、行程(Processes)、或使用者(Users)等對資源的使用，其中可類分為保護(Protection) 與安全(Security)。保護是維護行程不受干擾地使用特定資源；安全是維護資料或資源不被外力侵入而改變原有之意義。

19-2 保護的目的(Goal of Protection) 隨著電腦的精進發展，系統保護的需求也隨之更為重要，如同前數章曾述及之多程式作業系統(Multiprogramming Operating System)，其中最重要的管理是： “只有系統認可的權限使用者(Users)，才可依該權限使用特定的系統資源(Resources) ”。 電腦系統之保護策略(Protection Policy) 是提供保護機制(Protection Mechanism) 以管理(Governing) 系統各項資源(Resources) 之使用。此項保護策略有三個時機建立保護機制：(1) 硬體固定保護機制，系統出廠時已建立，(2) 作業系統因應執行環境，建立管理機制，(3) 使用者因應執行要求，建立管理機制。

19-3 保護之定義域 (Protection Domain) 電腦系統(Computer System) 是行程(Processes) 與物件(Objects) 的組合，物件包括硬體物件(Hardware Objects) 與軟體物件(Software Objects)，前者如CPU、記憶體、磁碟、印表機等，後者如檔案、程式等。 不同的物件對應不同型態(Types) 的操作(Operation)，記憶體引導存取操作；CPU引導執行操作；檔案引導存取、建立、刪除等操作。

圖19-3-1-1

圖19-3-1-2

圖19-3-1-3

19-4 矩陣執行(Access Matrix) 為了方便設計程式(Programming)，我們可將前述之集合(Sets) 型式改以矩陣(Matrix) 表示，如圖19-3-1-3，當行程(Process) P代表定義域(Domain) D2時，P有讀取(Read) 物件(Object) O2的權限，以 “read = access(D2, O2)” 表示。

圖19-4-1

圖19-4-2

圖19-4-1-1

圖19-4-2-1

圖19-4-3-1

19-5 矩陣應用(Implementation Matrix) 如圖19-5，我們發現圖中有許多空白入口(Entries)，如果將矩陣圖儲存於記憶體，這些空白入口所佔有的空間(Space) 將是一種嚴重的記憶體浪費，我們可以表格(Table) 或串列(Lists) 作適當的取代。

圖19-5

19-6 習題(Exercises) 1、保護(Protection) 與安全(Security) 有何區別？ 2、保護策略有那三個時機建立保護機制？ 3、於離散數學中曾定義(Define) 之序對關係(Ordered Pair) 為何？ 4、如何表示 “保護定義域(Protection Domain)”？ 5、定義域(Domain) 之具體代表為何？ 6、複製(Copy) 有那幾種？ 7、全域表格(Global Table) 之優缺點為何？ 8、物件權限串列(Access Lists for Objects) 之優缺點為何？ 9、定義域能力串列(Capability Lists for Objects) 之優缺點為何？

第二十章 安全(Security) 20-1 簡介 20-2 安全問題(Security Problem) 20-3 使用者確認(User Authentication) 20-4 程式安全之威脅(Program Threats) 20-5 系統安全之威脅(System Threats) 20-6 加解密(Cryptography) 20-6-1傳統加密法 20-6-2近代公開金匙加密法 20-6-2-1公開金匙原理 20-6-2-2 金匙設計方法 20-6-2-3金匙設計執行法則 20-6-2-4 金匙設計實例(Java 範例程式設計) 20-7 習題(Exercises) 20-8範例系統程式(Programming) 20-8-1傳統加解密法(模擬20-6-1節) 20-8-2近代加解密法(模擬20-6-2節)

20-1 簡介 於前章我們述及系統之保護(Protection)，本章將再進一步探討系統之安全(Security)。保護是維護行程不受干擾地使用特定資源；安全是維護資料或資源不被外力侵入而改變原有之意義。 具體來言，保護是處理系統內部環境(Internal Environment) 之問題，如檔案權限(File Authority) 等；安全是處理系統外部環境(External Environment) 之侵入問題，如病毒、資料攔截等。

20-2 安全問題(Security Problem) 軟體資料(Data) 或硬體資源(Resource) 遭到不當之使用是謂 “安全問題(Security Problem)”。所謂 “不當使用(Violations或Misuse)” 是指意外(Accidental) 不當使用、或蓄意(Intentional或Malicious) 不當使用兩種。 電腦之安全問題可由四個觀點來處理：實體觀點(Physical)、使用者觀點(Users)、網路觀點(Network)、作業系統觀點(Operating System)。

20-3 使用者確認(User Authentication) 當使用者(User) 要存取某檔案資料、或使用某資源裝置之前，必須先經過使用者確認(User Authentication)，確認的項目通常有三類： (1) 使用者物件(User Possession)，如使用者之卡片(Card)、使用者之鎖匙(key) 等； (2) 使用者資料(User Knowledge)，如使用者帳號(ID)、使用者名稱(Name)、使用者密碼(Password) 等； (3) 使用者特性(User Attributes)，如指紋(Fingerprint)、視網膜(Retina)、簽名(Signature) 等。

20-4 程式安全之威脅(Program Threats) 當使用者(User) 設計完成一個程式(Program)，除了設計者外，也提供其他使用者使用，程式安全之威脅因而由此產生，如木馬程式(Trojan Horses)、陷阱口(Trap Doors) 等。

20-5 系統安全之威脅(System Threats) 作業系統(Operating System) 提供行程可產生另一行程的機制，當一個行程有瑕疵時，即可能產生有瑕疵的其他行程，而將瑕疵擴散出去。如分裂程式(Worms) 與病毒(Viruses) 等。

20-6 加解密(Cryptography) 當兩個工作站台傳遞資料時，資料也隨即暴露在人人可攔截的空曠網路上，資料的安全性面對極大的挑戰。我們無法避免資料不被攔截，但我們可將資料加密，使被攔截的資料無意義。本節將探討：(1) 傳統加密法 與 (2) 近代公開金匙加密法。

20-6-1傳統加密法 所謂 “傳統加解密” 即是發射端(Client端) 與接收端(Server端) 均有相同對應之密碼匙，發射端依密碼匙將資料加密，接收端再依對應的密碼匙將資料解密，如此方法行之自古至今，其優點是簡易方便；缺點是不週嚴，有極大洩密之缺口，問題在發射端與接收端於交換對應密碼匙時，無法百分之百保密。

20-6-2近代公開金匙加密法 傳統密碼加密法，有其一定的不可靠風險，接收工作程序於設定加解密金匙後，自己保留解密金匙，還必須將加密金匙，通知發射工作程序。在通知的過程中，即已有了不可避免的洩密風險。近代密碼加密法，針對此項洩密風險，加以改進。接收工作程序於設定加解密金匙後，自己保留解密金匙，另將加密金匙公告大眾。

20-6-2-1公開金匙原理 接收工作程序於設定加解密金匙後，自己保留解密金匙，另將加密金匙不僅不須隱密通知對方，甚至將加密金匙公告大眾，其中神妙之處令人驚嘆。 1、暗門單向函數 2、單向函數常例 3、餘數同餘觀念 4、縮剩餘系(Reduced Set of Residues) 5、尤拉商數(Euler’s Totient Function) 6、尤拉定理(Euler’s Theorem) 7、費瑪定理(Fermat’s Theorem)

20-6-2-2 金匙設計方法 在初步了解上述觀念與理論後，即可著手設計RSA之公開加密金匙及私密解密金匙如下： 1、首先考量金匙之可逆性 2、由尤拉—費瑪 定理可得 3、若設定公開加密金匙(ex, N)、如何求得私密解密金匙dx？

20-6-2-3金匙設計執行法則 我們己清礎了解近代加密法RSA，如何設定其公開加密金匙、及又如何求取私密解密金匙。現在，我們將其執行過程整理詳述如下： (1) 受文者(接收端工作程序) 為乙方，任意選取兩個大質數p與q，其積 N=pq。 (2) 乙方任意選擇一整數ex，且ex與N互質。將 (ex, N) 設定為公開加密金匙，並公佈之。 (3) 乙方以 20-6-2-2之3 -(3) dx = (kT + 1) / ex， 求得其中之整數dx。 T如 20-6-2-2之2，T = Φ(N) = (p-1)(q-1)； k如 20-6-2-2之3 -(2) k為常數(0, 1, 2, …)。以 dx為乙方之私密解密金匙，妥善保管，不得洩漏。 (4) 發文者(發射工作程序) 為甲方、要秘密傳送明文m給乙方。甲方首先由公開檔案找到乙方公佈的公開加密金匙(ex, N)。然後以該公開金匙將明文m加密成密文n。 如 33-2-(一)(1)： mex = n mod N (5) 受文者(接收工作程序) 乙方收到密文n後，以其私密解密金匙dx解密。將密文n還原成m。 如 20-6-2-2之3 -(1)： ndx = m mod N

圖20-6-2-4

20-7 習題(Exercises) 1、電腦之安全問題可由那四個觀點來處理？ 2、使用者確認(User Authentication) 通常有那三類？ 3、何謂木馬程式(Trojan Horses)？ 4、何論陷阱口(Trap Doors)？ 5、何謂病毒(Viruses)？ 6、何謂謂 “傳統加解密”？ 7、“傳統加解密” 之優缺點為何？ 8、“近代公開金匙加密法” 與 “傳統密碼加密法” 有何不同？ 9、試設計一組 “傳統密碼加密法” 網路程式實例。 10、試設計一組 “近代公開金匙加密法” 網路程式實例。