# 作業系統
## Ch.01 作業系統簡介 與 常見系統類型
### OS 簡介
作業系統是**管理電腦**與**軟體管理**的電腦程式，同時也是系統的核心與基石。OS 主要有兩個功能 :
- 資源分配者
- 監控系統執行，防止不正常的運作造成系統危害

一個標準的PC的OS應該要有以下功能:
- 行程管理
- 記憶體管理
- 檔案系統
- 網路通訊
- 安全機制
- UI
- 驅動程式

OS按照系統大小區分:
- 大型電腦 : IBM OS/360
- PC : Windows, Linux, BSD, MacOS
- 嵌入式 : VxWorks, eCos, Symbian OS. Palm OS

### 常見的OS類型
#### **Multiprogramming System**
系統中存在多組行程同時(concurrent)執行，避免CPU閒置，提升CPU利用度。 (不是執行 Parallel)
Multiprogramming Degree 說的是系統中存在等待執行proccess的數目，Multiprogramming Degree越高，CPU的使用度也就越高。(可能會產生Trashing的問題)

#### **Time Sharing System**
Multiprogramming System的一種，OS透過資源分享，讓每位使用者都有一套專屬的系統存在，Response Time通常都在一秒之內。

常見的配置 ; 採用RR行程安排、記憶體空間與所有使用者共享、使用虛擬記憶體、I/O device 透過 Spooling 技術(把硬碟當成一個巨大的緩衝區做使用)共享。

#### **Distributed System**
須符合兩條件，硬體上每台電腦都是自主的，軟體上用戶將整個系統看成是一台電腦。一般分為兩類，Client-Server-System、Peer-to-Peer。

EX. 志願計算。使用志願者的閒置計算能力，透過網路進行傳輸。

建構分散式系統的好處有: 資源共享、加快計算速度、可靠性、通訊需求

(Multiprocessor System and Parallel System)
- Symmetric Multiprocessing : 對稱式多元處裡。每一個處理器具有相同的功能，可靠度高，強調負載平衡。
- Asymmetric Multiprocessing : 非對稱式多元處裡。 Master/Slave 架構。

#### **Real Time System**
定義嚴謹的固定時間限制，電腦在處理工作時必須在這個定義的時間範圍內完成工作，否則工作算是失敗。

硬性時間系統(Hard Real Time System):對於完成工作的時間有極度嚴苛的限制。若process不能在規定時間內完成，則process算是失敗。

- 工廠自動化系統、軍事系統、核能安控
- Application Program 設計上非常重要
- Data and Program 都存在 ROM 與 RAM 中
- 不須使用虛擬記憶體。因為 page fault 處理時間過長。
- 減少 OS 的干預 以降低 Data Latency

軟性時間系統(Soft Real Time System): 保證高優先權的process必須先於所有低優先權的process完成。
- Multimedia System、 Virtual Reality
- CPU的排程應能支援Priority Scheduling 且不能提供類似的Aging技術。
- 可和分時系統、virtual memory並存

#### **Clustered System**
叢集系統共享儲存裝置，集合許多CPU並經由LAN連線緊密的完成工作。叢集系統主要是利用多台電腦系統或是工作站來共同完成大型數值的平行運算。

---
## Ch.02 中斷、I/O、系統呼叫、OS 結構設計 和 虛擬機
基本知識的大雜燴，好好享受。
### 中斷(Interrupt)
當處理器接收到了外圍硬體或軟體的訊號，導致處理器的執行需要通過context switch處理該事件。

Interrupt的處理流程 :
- 暫停當前的process，執行並保存當前的process當前的執行狀況。
- OS 根據 Interrupt ID 查詢 Interrupt Vector，並取得ISR(Interrupt Service Routine)起始位置
- ISR 執行
- 執行完成，恢復當前process執行狀況
- 回到原先中斷的執行

中斷的種類 :
- 外部中斷 (External Interrupt):
CPU 外的周邊元件所引起的。(I/O Complete Interrupt、I/O Device Error)
- 內部中斷 (Internal Interrupt):
不合法的使用所引起，CPU本身所引發。(Debug、Divide-By-Zero、overflow)
- 軟體中斷 (Software Interrupt):
使用者程式執行時，若需要OS服務時，會藉由System Call來呼叫 OS執行對應的ISR，完成服務請求後，再將結果回傳給使用者程式。

(Trap = Internal Interrupt + Software Interrupt)

### I/O 的運行方式

資料在I/O中傳遞的方式有三種:
- Polling :
最簡單的方式。 I/O 裝置只要將資訊放到暫存器中，CPU會週期性的檢查並取得資訊來得知需要服務的裝置。
- Interrupt Driven I/O :
利用Interrupt的機制，當一個I/O裝置需要服務時，會發出Interrupt來通知CPU (非同步I/O)
- DMA (Direct Memory Access):
提供一個裝置控制器，讓I/O裝置可以直接地在記憶體做資料的傳輸，不需要CPU的參與。
-- Cycle Stealing: DMA 向 CPU 竊用機器週期，直接向記憶體存取資料，因此cpu可與周邊的裝置的工作同時進行，萬一CPU與DMA在記憶體存取時發生衝突，則給DMA較高的優先權。

I/O 架構:
- 同步I/O架構 : :accept:
一段時間，只有一個I/O請求產生。
- 非同步I/O架構 :negative_squared_cross_mark:
必須有一個表以記錄個種裝置的I/O的位址與使用狀況。

### Dual-Mode
OS 會把影響重大的指令設為**特權指令(Privileged Instruction)**，用以保護重要的資源，需要kenel-mode才可以執行。Dual-Mode需要硬體的額外支援，用一個Mode BIT紀錄權限。
- User Mode(Mode Bit == 1) : 一般樣式
- Kernel Mode(Mode Bit == 0) : 此模式下才有權力執行特權指令。

特權指令的種類:
- I/O指令
- 與記憶體有關的暫存器的修改指令
- 與 Timer有關的指令
- Enable and Disable指令
- 系統停止指令
- 從User mode改到 kernel mode的指令

### 虛擬機
虛擬機是透過軟體模擬機制，創造一個底層硬體一模一樣的功能介面，對真正的系統而言，VM上的OS相當於一個執行中的User Program，開發OS時較為安全且方便。

PROS:
- 對於OS的測試是一個很好的開發平台
- VM 具安全性
- 同一台電腦可以安裝多套不同的OS，適時做time-sharing system 的最好方法
CONS:
- 製作極為困難
- VM之間非常孤立，所以不易溝通或分享
- 效能並沒有比較好

---
## Ch.03 行程 Process

### Process 的簡介
行程 (process)是電腦中執行program的實體。行程本身不是基本執行單位，而是執行續的容器。行程需要資源才能完成工作，像是CPU的使用時間、記憶體、檔案位置。以及I/O位置。

名詞解釋 :
- 分批系統環境，行程稱為工作(jobs)。
- 分時系統環境，行程稱為使用者程式(user programs)或任務(tasks)
- 在多數情況，工作與行程是同義詞。

行程在執行時，狀態(state)會改變。所謂狀態，指的就是目前的動作。
- new : 行程產生中。
- running : 行程正在執行。
- waiting : 等待某事發生，ex.等待使用者輸入完成。也稱作為「阻塞」(blocked)。
- ready : 排班中，等待CPU。
- terminated : 完成執行。

process 在記憶體中的配置。
- stack : 存放函數的參數、區域變數等等。(會稱作stack是因為，他遵守LIFO。)
- heap : 一般由程式設計師分配釋放，執行時才會知道配置的大小。(如malloc/new 和 free/delete)。
(其實就是Data Structure中的link-list)
- BSS : 尚未初始化的參數。

### Context Switch
讓多個process可以分享單一一個CPU的計算過程。當CPU context switch 到另一個 process，系統就會儲存舊的process，載入新的process的狀態。Context Switch 的時間是overhead，耗時會因為硬體配置不同而不同。

交換的時機有以下幾種。
- 多工
- 中斷處理
- 用戶態或內核態的交換

**Process Control Block (PCB) :**
作業系統中的一種資料結構，在切換process時，會將未做完的process紀錄狀態存入PCB中。

### Scheduler
#### **Long-Term Scheduler** (New -> Ready)
- 從job queue中挑選出合適的jobs，並載入到記憶體中準備執行。
- 適用於Batch System(大型機房)，但不適用於 Time-Sharing System.
- 可以用來調控 multi-programming degree.
- 可調和CPU bound 與 I/O bound 的比例。
- 執行頻率**最低**。

#### **Short-Term Scheduler** (Ready -> Running)
- 從Ready Queue中挑選高優先度的Process，使他獲的CPU的控制權。
- Batch System 與 Time-Sharing System 都需要。
- 執行頻率**最高**。

#### **Medium-Term Scheduler** (Virtual Memory)
- 當記憶體空間不足，又有其他process想進入記憶體中執行時，此時的Scheduler必須挑選某些process將其Swap out到磁碟中為了空出記憶體空間，等到記憶體中有足夠空間在把它Swap in 記憶體中繼續執行。
- 通常在Time Sharing System中。
- 減少 Multi-programming Degree。
- 可調和CPU bound 與 I/O bound 的比例。

#### (粉重要) I/O Bound vs CPU Bound
- I/O Bound Process :
Spend more time doing I/O than computations, many short CPU burst, such as waiting keyboard enter programs.
- CPU Bound Process :
Spend more time doing computations, few very long CPU burst, such as zip programs.

---
## Ch.04 多執行緒 Multithread Programming
### 一、thread 簡介
Thread 是 OS 進行運算排成的最小單位，被包含在process中，是process的實際單位。
- thread 是 OS 分配 CPU 的時間對象。
- process 是 OS 分配資源的對象。

Thread 的內容包括:
- Thread ID
- Thread State
- Program Counter
- Register Counter
- Register Set
- Stack

Process 中的 thread 共享 :
- code Section
- data Section
- OS Resource

(Code section + Data Section = Memory space、 Address space、Heap Memory)

Process中multi-thread 的好處 :
- **應答:** 允許程式某部分或被中斷或執行太久時，可以繼續執行。
- **資源共享:** 分享code、data、OS resource
- **經濟效益:** 輕量化的process
- **可使用多個核心**

### Multi-thread的介紹
#### User threads
在user mode下進行，OS不知道有這些threads，因此不需要進入OS介入管理。
- Pros : 生產管理成本低。
- Cons : process 可能被鎖住，因為process 的 user thread 發出鎖定的system call 且 kernel 是 single thread.
- ex. Pthreads、 Win32 threads、Java threads
#### Kernel Threads
在kernel mode下進行，OS知道這些thread的存在，藉由OS進入介面管理。
- Windows XP/2000
- Solaris
- Linux
- Tru64 UNIX

---
## Ch.05 CPU Scheduling
### CPU Scheduling 簡介
利用multi-processing 達到CPU最大效率。一般，process都是CPU burst。接著是I/O burst，做I/O的資料傳送。正常狀況下，Process就在這兩者之間做循環，最後system call 終止執行作為結束。

CPU 從 ready queue 的 process中挑選process進入CPU中作執行。CPU scheduling 的 process 選擇會在以下情況下轉變。
- Switches from running state to waiting state.
- Switches from running to ready state. (因為timeout回到ready)
- Switches from waiting to ready
- Terminates

### Preemptive vs Cooperative
#### Preemptive Scheduling
- Higher Responsiveness
- Hard to share resources
- Higher overhead

#### Cooperative Scheduling
- Simpler in Design
- Poor responsive
- Potential hazards

#### Dispatcher
負責將CPU控制權交給經由Short-term scheduler 挑選出的process。
- Switching context
- Switching to user mode
- Jumping to proper location in the user program to restart that program.

### Scheduling Criteria
- turnaround time :
完成的時間(完成-到達)，進入process到出來的時間。
- Waiting time :
Waiting in ready queue.
- Response time :
自從使用者命令交付到系統第一個回應所需要的時間。

## Ch.06 Synchronization 同步
### 同步問題 Introduction
- Entry Section
- Critical Section
- Exit Section
- Remainter Section

Solution to Critical-Section Problem
- Mutual Exclusion
在任意時間點，只允許一個process進入自己的critical section 活動。
- Progress (必須同時達成以下條件)
a. 不想進入critical section的process不可以阻礙其他的process進入critical section，不可參與進入critical section 的決策過程。
b. 在有限的時間範圍內從critical section的process中，挑選一個process進入critical section，隱含no deadlock。

- bound waiting
從process提出申請進入critical section的申請獲准時間是有限的。隱含 no starvation。
---
## Ch.07 死結 Deadlock
### Intro.
Deadlock 意思就是系統中存在一組process陷入互相等待對方所擁有的資源的情況，導致所有的process無法繼續執行，CPU利用幅度大幅降低。

Deadlock 發生須符合以下四大條件。
- Mutual Extension
資源在同一時間點，只能被一個process所使用。
- Hold and wait
某process持有部分資源，其他部分正在持有的資源。
- No preemption
process不可以強奪其他process的資源。
- Circular waiting
系統中的process，其中每個process之間互相等待，形成循環式等待。

### Deadlock vs Starvation

### Deadlock 處理方式
Deadlock 處理方法 :
- Deadlock Prevention
- Deadlock Avoidance
- Deadlock Recovery & Recovery

Prevention and Avoidance 的資源利用率極低。
#### Deadlock Prevention
打破以下原則，可以保證Deadlock不再發生。
- Mutual exclusion
- Hold and wait
- Preemption
- Circular waiting

#### Deadlock Avoidance
利用Banker's Algorithm 來判斷是否處於Safe State。

### Banker's Algorithm

---
## Ch.08 Memory Management
### Binding
決定程式的初始位置，也就是程式應該從哪個地方開始執行。Binding 分為三個時期，**compile time、load time、execution time**。

#### Compile Time
- 交給compiler做決定。之後程式執行的位置不得變更。
- cons: 若決定的位址有其他程式在執行，或是要變更執行的位址時，則需重新編譯，hen麻煩。
### Load Time
- 交給link loader決定，不一定都從固定位址開始，可以重新定位。
- cons: 因為執行時間沒有被呼叫到模組中，必須要先linking、allocation、loading。因此耗時，且浪費記憶體。除此之外，執行時不能改變記憶體位址。
### Execution Time
- 交給OS做決定，又稱為dynamic binding，在程式執行時間才決定執行的初始位址。但需要額外的硬體支援 (MMU，Memory Management Unit)。
- Base Register : 紀錄當前程式初始位址。
- Local Address : 必須與 base register 相加，才會得出 physical address。
- cons: 程式執行慢、效能差。

### Swapping
A process that can be swapped temporarily out of memory to a backing storage (such as disk), and then brought back into the memory for continued execution.
- Swapping is a midterm scheduler.
- Most of the time is spent of transferring

### Contiguous Memory Allocation
OS根據每個process的大小，找到一塊連續、夠大、能用的記憶體，配置給記憶體做使用。OS會利用link-list管理這些FREE BLOCKS，稱為Available list。

### Fragmentation
#### External Fragmentation
系統中，所有空間總和大於process所需要，但因為這些空間不連續，因此無法分配給process使用，造成記憶體空間閒置。解決方式有 :
- Compaction
- Page memory management

#### Internal Fragmentation
OS配置給process的記憶體大於process所需，這些空間用不到，也沒辦法給其他process使用。

### Paging
OS將Disk中的記憶體分割成固定大小的區塊，稱為pages。當不需要時，將記憶體移轉到disk中。需要時，再將資料載回到記憶體中。Page 是disk和memory中傳輸的最小單位量。

- Physical Memory
可以看成是一組Frame的集合。大小相等。
- Logical Memory
也就是User Program。視為一組頁面的集合。頁面大小等同於頁框之大小。

Pros:
- 解決 external fragmentation 問題。
- 可以支援Dynamic Loading 與 Virtual Memory

Cons:
- 有 internal fragmentation 問題
-

---
## Ch.XX Final Exam Compilation
### Ch.09
#### Page Fault 9.17
#### Issue a read from disk to a free frame
- 1. Wait in a queue for this device until the read request is serviced
- 2. Wait for the device seek and/or latency time
- 3. Begin the transfer of the page to a free frame
#### Demand Paging
#### Page Replacement
### Ch.08
#### Fragmentation
- External Fragmentation
total memory space exists to satisfy a request, but it is not contiguous.
- Internal Fragmentation
allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used.

First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to fragmentation.
1/3 may be unusable -> 50-percent rule
#### Address Translation Scheme
Address generated by CPU is divided into
- Page Fault ( p ) -- used as an index into a **page table** which contains base address of each page physical memory.
- Page offset ( t ) -- combined with base address to define the physical memory address that is sent to the memory unit.
- For given logical address space 2^m and page size 2^n.

#### Paging Hardware With TLB

#### Effective Access Time

### Ch.07
#### Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.

#### Deadlock Avoidance
Requires that the system has some additional **a priori** information available.

#### Banker's Algorithm
(會了吧)
### Ch.06
#### Dining Philosophers Problem