# 作業系統(Operating system)

> 2017/10/17 AndyLee

## 作業系統的主要目的：
- Government：提供一個使用者與硬體間的服務介面，讓使用者方便執行程式。
- Resource allocator：有效的管理電腦硬體並適當的資源分配給使用者。
- Control Program：控制使用者程式，防止非法使用資源或是破壞系統。
- Efficiency：作業系統必須負責提高系統整體的效率。

## 作業系統種類之介紹：
- Batch Processing System：將同類的工作集合起來一起執行，以減少重複且瑣碎的動作，並減少工作切換的時間，以提升系統效率。

- Interactive system：在terminal的使用者送出指令後，系統必須立即作出回應，並將結果送回使用者的系統。

- Timesharing System：利用CPU scheduling 和multiprogramming技術將一份程式分配一個time quantum，即使沒有執行完，時間一到還是要交出控制權給其他使用者。
- 需要條件：要有interrupt的機制和timer來控制每個process的時間。

- Multiprocessing System：(Tightly Coupled的多處理機系統)

- 各processor共用一個Memory與Clock cycle。
- 通常受同一個作業系統管理且利用Shared Memory的方式溝通訊息。
- 主要優點：提升產量，可靠度佳，節省經費。缺點：設計上較為複雜。

- Distributed System：(Loosely Coupled的多處理機系統)
- 各processor有自己的Memory與Clock cycle。
- 各processor有自己的作業系統且利用Networking的方式來溝通訊息。
- 主要優點：提升產量，可靠度佳，通訊方便。缺點：設計上較為複雜。

- Real-time System：
- 通常用在專業應用系統，必須在有限的時間內作出正確的反應。
- 主要特徵：處理程序必須儲存在memory中，在限時內作出的反應必須是精確且準時的

- 系統必須支援"Priority scheduling"，real-time之process必須具有最高的priority，且不隨時間改變
- 由於page fault會造成不可預期的延遲，故不採用virtual memory

- Hard real-time system：考慮某些工作在限期內完成具有很高的價值，反之則毫無用處，而用戶也願意付出較高的費用。

- Soft real-time system：使用priority scheduling，重要的工作priority較高，且priority是固定的，不隨時間而改變。

- Monolithic system：

- 優點：系統單純，設計上簡單，適合小型系統或embedded system。
- 缺點：對各使用者與硬體的並行運作不確定，無法適時有效的處理。
- 系統結構不明確，要修改或增加功能較為不易。


- Micro-kernel system：
- 優點：
- kernel只負責最基本的服務，而由user-level的sever提供大部分服務。
- server不直接存取硬體，因此某個server有問題不會影響整個系統。
- 高模組化，設計上彈性較大。

- 缺點：overhead較大。


## System call
允許使用者向系統要求kernel mode下的服務的一個介面，若是user需要系統提供kernel mode下的服務就呼叫system call，利用此軟體中斷並從user mode切換到kernel mode，然後系統會執行對應的system call routine，將結果傳回給user。

OS中的參數如何傳遞：
- 傳入register中
- 存入stack中
- 參數以block或table的方式存在memory中，而此block的位址是以register中的參數傳遞。

## DMA(Directed Memory Access)
主要用於資料的大量傳輸，負責I/O devices和memory間的資料傳輸，不須CPU的監督，使CPU可以同時運作，增進效率。

cycle stealing：當DMA controller存取記憶庫時，CPU只能存取cache的資料，因此DMA可盜取CPU的存取週期。

## Command interpreter：

將讀到的command解譯成procedure及參數，確定命令無誤則交由系統呼叫對應的程式來執行命令。

與kernel分開的原因：
- 怕user輸入指令後經由kernel mode來破壞系統，所以通常把它當成一程式，系統初始化時就載入，若有問題可由kernel結束掉

## Virtual machine：

- 優點：(1)系統安全性佳，且debug較為容易 (2)提供user一個好平台，可以安裝各種不同的os，對於新系統的研究與發展相當適合。

- 缺點：(1)製作困難且資源共享不易 (2)利用模擬方式執行，performance較差

### VM如何利用硬體來保護OS：
1. I/O protection：必須把I/O的指令變成privileged instruction，防止使用者任意操控I/O，要執行I/O的話必須向系統發出interrupt切換成kernel mode才能處理。
2. Memory protection：利用base register和limit register來限制user存取的位置，防止user任意更改中斷向量表和其他的的程式。
3. CPU protection：把使用CPU的權利變成privileged instruction，防止使用者一直取得CPU的使用權，進入無窮迴圈吃掉CPU資源。

### 特權指令(Privileged Instruction)：
set timer，turn off interrupt，change to kernel mode，clear memory，read / write to kernel memory。

### 非特權指令：
turn on interrupt，change to user mode，read the clock，increase value of register，Fetch an instruction from kernel memory。

### 三項支援operating system實作的硬體特徵：
(1) Mode bit：用來區分user mode和kernel mode。
(2) Timer：用來控制process的執行時間，保護系統資源不被獨占。
(3) Register set：用來存取process的資訊或小型的page table等。

## Interrupt 重點整理
### Interrupt 的種類介紹

- Software：program interrupt(trap)，system/supervisor call interrupt。
- Hardware：external interrupt，I/O interrupt，machine check interrupt。

### 遇到 Interrupt 時的處理方式

- Step1 : 暫停目前的process，切換成kernel mode並將CPU控制權交還給系統。
- Step2 : 若是I/O interrupt，由polling的方式找出哪個device發出的interrupt。
- 若是Trap interrupt，將process目前執行的state及register存入stack。
- Step3 : 由中斷向量找出ISR的起始位址並且執行ISR。
- Step4 : ISR執行完後，將系統還原到中斷之前執行的程式。

### Interrupt 與 Trap 的比較：
- 相異處：
- (1) Interrupt由**硬體**產生，被用來當作I/O complete的訊號。
- (2)Trap由**軟體**產生，被用來call os. routine或是catch arithmetic error。

- 相似處：
- (1)都會發生context switch from user mode to kernel mode。
- (2)一個向量記錄了interrupt handle address的起始位址，而os可利用它來尋找適合的interrupt service routine(ISR)。
- (3)都是interrupt的一種。

### Process在執行I/O工作的期間有兩種方式。
- asynchronous I/O：CPU使用權會先交給user，不必等待I/O的結束。
- synchronous I/O：user若要取得CPU使用權，要等到I/O的結束才行。

## System Programming目的
提供一些系統已寫好的procedure 和 system call，讓使用者不須浪費額外的時間去寫 I/O 或 開檔讀檔 等常用的基本指令，可節省使用者開發程式的時間，若是許多使用者在系統中更可節省memory。

## PCB (Process Control Block)
用來儲存process相關狀態，資訊的資料結構，每個process都有一個PCB。
- Process state
- program counter (PC)
- CPU registers
- CPU scheduling information
- memory management information
- accounting information
- I/O status information

## I/O bound v.s CPU-bound
- I/O-bound program：一個程式受限於I/O device的速度，在做I/O動作的時間比運算的時間要多，使的CPU大部分時間仍然處於idle的狀態。
- CPU-bound program：一個程式受限於CPU的速度，在做運算的時間也比I/O的時間多的多，使的整個程式的運行速度受限於CPU。
- 若是program在執行期間有很多很短的CPU-burst則為I/O-bound。
- 若是program在執行期間有很多很長的CPU-burst則為CPU-bound。

## Thread與Process的比較：
- process是一群無關的tasks可能由不同的users所創造，也必須進行protection的措施 。
- 每個process都有自己的memory address。
- thread是一群相關的tasks，以一種合作的關係，不需進行protection。具有獨立的**program counter (PC)，register set，stack state**
- Thread若是在同一個process下可以共用一個memory address同,但這些Thread各自擁有其Stack。換句話說,Thread能透過reference存取到相同的Object,但是local variable卻是各自獨立的。

### Threads優點：
- create，destroy容易，context switch較快速，和Processes具有相同的執行狀態。

### Threads缺點：
- 由於共用一個memory address，而且沒有protection，所以必須作synchronize的動作，不然有可能會破壞memory中的資料。

### User-Level Threads
create，destroy，switch都不需透過kernel的處理，所以速度較快。
- 優點：context switch的速度快，overhead較小。
- 缺點：若kernel是single-thread型態，則process中任一個thread進行system call而blocking住，整個process都會被blocking而無法繼續其他threads。

### Kernel-Level Threads
create，destroy，switch都必須經由system call來透過kernel處理，所以速度較慢。
- 優點：所有threads之間可以平均獲得processor的使用。
- 缺點：context switch的時間比較長。

## Procss State

## Java Thread
Java以java.lang.Thread這個類別來表示Thread。

Class Thread有兩個Constructor:
- Thread()

public class ThreadExample1 extends Thread {
    public void run() { // override Thread's run()
        System.out.println("Here is the starting point of Thread.");
        for (;;) { // infinite loop to print message
            System.out.println("User Created Thread");
        }
    }
    public static void main(String[] argv) {
        Thread t = new ThreadExample1(); // 產生Thread物件
        t.start(); // 開始執行t.run()
        for (;;) {
            System.out.println("Main Thread");
        }
    }
}

- Thread(Runnable)

public class ThreadExample2 implements Runnable {
    public void run() { // implements Runnable run()
        System.out.println("Here is the starting point of Thread.");
        for (;;) { // infinite loop to print message
            System.out.println("User Created Thread");
        }
    }
    public static void main(String[] argv) {
        Thread t = new Thread(new ThreadExample2()); // 產生Thread物件
        t.start(); // 開始執行Runnable.run();
        for (;;) {
            System.out.println("Main Thread");
        }
    }
}

### Long-term scheduling (job scheduler)：
目的：決定哪些job可以從hold state進入ready state。當一個工作結束時，此排程就會啟動。

### Short-term scheduling (CPU scheduler)：
目的：從ready queue中挑選一個process來獲得CPU的使用權。

### Medium-term scheduling：
目的：為了提升系統效能及降低系統負荷，將一些process swap到disk中，等系統負荷較低的時候再載入到memory執行。
- 特徵：
- (1)降低degree of multiprogramming來降低系統負荷。
- (2)可用在time sharing system中，減少系統對使用者的response time。

## Preemptive scheduling v.s Non-Preemptive scheduling
### Preemptive scheduling
允許priority較高的process進入ready queue後可以作context switch將priority較低的process置換掉，並取得CPU的使用權。

preemptive優點
- 較有彈性。
- 適用於real-time system和time-sharing system。

preemptive缺點
- context-switch的次數頻繁，增加系統的負荷。
- 容易使priority低的process發生starvation。

### Non-preemptive scheduling
除非是process自己放棄CPU使用權或是已經執行完畢，不然不允許系統作context switch把它的CPU使用權交給其它的process。

Non-preemptive優點
- 對每個process來說較公平。
- 每個process的工作時間較能預測。

Non-preemptive缺點
- 容易發生convoy effect：工作時間短的process必須等待時間長的。
- 系統較沒有效率。

## 在CPU排班中一些時間的名詞和計算

1. Turnaround Time：從工作load到memory後一直到工作結束的時間長度。
2. Wait Time：工作在系統中(或在memory中)等待的總時間。
3. Server Time：工作有使用到CPU的總時間。
4. Reaction Time：一個process在分時系統中,第一次被執行之前的等候時間。

## 各種CPU-Scheduling以及比較他們的優缺點。

1. FCFS (First Come First Serve)：最先進入queue的process先執行。
2. SJF (non-preemptive SJF)：Serve Time最短的process優先執行。
3. SRTN (preemptive SJF) ：下一個CPU-burst最短的job先執行。
4. Priority：優先權最高的優先執行。
5. RR(Round-Robin)：每一次使用CPU的時間為一個constant的time quantum，time quantum使用完後必須重新排隊循環執行。
6. MLQ(Multi-level Queue)：依工作性質將工作分成好幾層，每層分配一個queue，每個queue都有自己的排班法則，process固定在某個queue上工作。
7. MLFQ(Multi-level-Feedback Queue)：與MLQ類似，但是允許process可以在queue間移動，所以CPU burst較長的工作將會往下層移動。

## 五個演算法測量準則(criteria)：
- wait time
- turnaround time
- response time
- CPU utilization
- throughout。

## Context Switch：
當process被強迫離開CPU時，必須將現在process information儲存起來，並載入新的process information，這種額外的負擔稱之context swith。

### 讓context switch加快的方法：
(1) 替每個process準備一獨立的register set，即若是register的數目夠多，則OS只要改變register的point即可。

(2) 利用thread可降低context switch的負擔，由於同一個process下的thread可以共享memory，所以需要的independent register數目較少，使負擔較輕。

(3) Dispatcher：
可以把CPU的控制權交給經由short-term scheduling所選出來的process。

## Virtual Memory：
優點：

(1) program size大於physical memory size時仍可執行。

(2) 提高 memory utilization，degree of multiprogramming。

(3) 降低programmer overhead。

缺點：

(1) 增加memory access time。

(2) 需要硬體的支援。

(3) 有可能會發生Trashing的現象。

設計一個critical section的Algorithm須符合三個條件：
- Mutual Exclusion：同一時間內只有一個process在critical section。
- Progress：若是有process想進入critical section則最終必可以進入，必須由留在entry，critical，exit section中的process來決定哪一個進入。
- Bounded Waiting：每個process等待進入critical section的時間必須有上限，換言之，不可以發生starvation。

## Synchronization

### Semaphore：
一個**整數變數**，允許Ｎ個thread同時存取，提供兩種atomic運作：wait與signal，用來完成critical section設計及解決同步問題的機制。

定義如下：

wait(S)

    while S<= 0 do no-op ;

    S = S-1 ;

signal(S)

    S = S+1 ;

Semaphore的兩種製作方式：
(1) Spin-lock：對於多處理機系統很有用，優點是可以省去process進入critical section時的context switch時間，使process可以用極短的時間進入c.s.。

(2)Suspend-lock：可以用來解決busy waiting的現象，充分的利用CPU資源。

Semaphore 與 Monitor的比較：使用monitor可以輕易地模仿出semaphore的效果，可是使用semaphore來模擬monitor卻會十分複雜。

## Busy Waiting
忙碌等待就是在一個迴圈裡，不斷等待某個條件的成立，必須等該條件成立之後，才會離開該迴圈。例如：

while( eventFlag == false )
;

- 若eventFlag為false，那麼迴圈就會持續執行，直至同一個程序中的另一個執行緒，將eventFlag值改為非false時，才會離開迴圈。
- 這在邏輯上一點問題也沒有，但因為多工作業系統的特性，因而衍生出效能的問題，佔據了CPU可供執行的時間，讓其他程式無法分配到足夠的CPU時間，使得其他程式呈現反應遲滯的現象。就像上面的程式片段中，該迴圈不斷持續地忙著檢查eventFlag的值，所以被稱為是一個忙碌的迴圈。

- critical section造成的busy waiting是因為waiting process佔用CPU time執行迴圈卻沒有真正進行運算，浪費CPU time。

- I/O造成的busy waiting是因為CPU必須不斷去檢查I/O是否完成，而造成在等待I/O的運作完成過程中，CPU雖然busy ，但實際上沒有增加 throughout。

Rendezvous：
- 在message passing下，當兩個process要溝通，則會執行send及receive指令，如果link buffer已滿，則sender送出的訊息無法在link中停留，所以sender必須等待直到receive那端收到訊息，造成雙方在此同步稱為rendezvous。

- Swap：為了提升memory utilization，而利用medium-term scheduler將某些process暫時swap out到disk，等memory空間足夠的時候在重新載入。

## Critical Section：
數個process之間採用shared-memory的方式溝通，每個process都有一段稱為critical section的code，process要存取必須滿足mutual exclusion。

## DeadLock 定義
> https://zh.wikipedia.org/wiki/%E5%93%B2%E5%AD%A6%E5%AE%B6%E5%B0%B1%E9%A4%90%E9%97%AE%E9%A2%98

在系統中存在一組processes互相等待對方資源，使得process無法皆無法繼續執行，使得CPU執行效率大幅下降。

形成DeadLock必須四要素，缺一不可
1. **Mutual Exclusion (互斥)**：同一個時間內只有一個process使用該資源，其他processes都必須等待，直到資源釋放掉。
2. **Hold and Wait (持有並等待)**：Process持有部分資源，且正在等待其他資源使用
3. **No Preemption (不可搶先)**：process不可以任意搶奪其他process的資源，必須等待其他process自願釋放掉才可以用。
4. **Circular Wait (循環式等候)**：P~0~等待P~1~釋放，P~1~等待P~2~釋放，..P~n~等待P~0~釋放如此造成循環式等待。


*哲學家就餐問題*

:::info
假設有五位哲學家圍坐在一張圓形餐桌旁，做以下兩件事情之一：吃飯，或者思考。吃東西的時候，他們就停止思考，思考的時候也停止吃東西。

餐桌中間有一大碗義大利麵，每兩個哲學家之間有一隻餐叉。因為用一隻餐叉很難吃到義大利麵，所以假設哲學家必須用兩隻餐叉吃東西。他們只能使用自己左右手邊的那兩隻餐叉。

哲學家從來不交談，這就很危險，==可能產生死結==，每個哲學家都拿著左手的餐叉，永遠都在等右邊的餐叉（或者相反）。

即使沒有死結，也有可能發生資源耗盡。例如，假設規定當哲學家等待另一隻餐叉超過五分鐘後就放下自己手裡的那一隻餐叉，並且再等五分鐘後進行下一次嘗試。這個策略消除了死結（系統總會進入到下一個狀態），但仍然有可能發生「活鎖」。如果五位哲學家在完全相同的時刻進入餐廳，並同時拿起左邊的餐叉，那麼這些哲學家就會等待五分鐘，同時放下手中的餐叉，再等五分鐘，又同時拿起這些餐叉。

一種常用的電腦技術是**資源加鎖，用來保證在某個時刻，資源只能被一個程式或一段代碼存取**。當一個程式想要使用的資源已經被另一個程式鎖定，它就等待資源解鎖。

當多個程式涉及到加鎖的資源時，在某些情況下就有可能發生死結。例如，某個程式需要存取兩個檔案，當兩個這樣的程式各鎖了一個檔案，那它們都在等待對方解鎖另一個檔案，而這永遠不會發生。
:::
## Deadlock Avoidance：

系統利用algorithm對於process的request進行評估，若可以找出一組safe sequence，使系統進入safe state就核准其要求，否則拒絕此process的request。

Bankers Algorithm：計算系統是否處於safe state，用在multiple instance。

優點：可以避免系統進入deadlock。

缺點：
(a)每次process提出資源要求，系統皆須要額外的花費去執行此algorithm。

(b)資源使用率不佳，因為unsafe state不代表一定會deadlock，但是會被拒絕。

### 處理Deadlock的綜合方法：

Internal Resource：可以使用resource ordering技術解決。

Job Resource：利用deadlock avoidance的方法。

Central Memory：利用preemption的方式。

Swappable space：事先配置最大需要空間。

### Starvation 和 Deadlock的比較：

Starvation 在沒有deadlock的狀態下，是指某些process因為一直分配不到執行所需要的資源，而發生indefinite postponement的現象。

Deadlock 則是一群process為了搶奪資源而造成全部的process都無法執行。

## Program v.s. Process
Program：尚未開始執行的程式。尚未載入主記憶體，不擁有計算機資源。沒有對應之PCB（process control block）。不是scheduler排程的對象。

Process ：正執行中的程式，有ready、run、blocked等process狀態。已載入主記憶體，擁有計算機資源，如I/O設備、CPU等。有對應之PCB（process control block），記載process之狀態、所擁有計算機之資源，I/O buffer之位址等。CPU排程的對象。

erlay：只保留執行時所需要的指令和資料在記憶體內，當需要其它指令時，再載入到已經不需要使用的指令空間中。

## 三種實做page table的方式：

(1) Register：優點：速度快。缺點：若page table太大則造價昂貴不適合。

(2) Memory：優點：允許較大的page table。缺點：memory access兩次造成有效存取時間太長。

(3) TLB(Translation look-aside buffers)：一般由associative register製成。

優點：在hit ratio高的情況下速度與register一樣高。

缺點：hit ratio低時，速度慢。

## Demand paging
用來實現virtual memory的技術，不把整個process需要的page載入記憶體，而採用Lazy Swapper，只載入執行所需的頁面。

- Pure Demand Page：當process執行時需要某page才將其載入記憶體，不需要的page都不須載入(不預先猜測)。

- Copy on write bit：所有共用同page的process都會將其page table對應到此page的entry的copy-on-write-bit設定為1，表示對此page有write必須另行copy。

## 檔案系統整理

### File Space Management：
- Contiguous Allocation：檔案被分配在disk中連續的位址上，而目錄只需要記錄此檔案的第一個block位址即可。

- 優點：隨機存取容易可以直接計算出磁區之實際位址，速度最快。

- 缺點：
- a. 不適合大的檔案，且存在有External Fragmentation，可用Repack程式解決，可是cost很大。
- b. 檔案要事先告知需要多大的空間，之後則無法任意增加減少 。

- Linked Allocation：將分配給檔案的空間用pointer連起來，而目錄只需要記錄此檔案的第一個block位址即可。

- 優點：a. 沒有External Fragmentation的現象。 b. 配置空間給檔案很容易，也容易擴充。

- 缺點：a. 支援循序存取，但是不適用direct access b. 鏈結的指標需要佔用額外的空間。 c. 可靠度較差，發生link lose的時候較難處理。

- Index Allocation：每個檔案使用一個block當作index，來記錄檔案所使用的block位址(大部分系統採用)

- 優點：a. 沒有External Fragmentation的現象。 b. 支援direct access，空間容易擴充。

- 缺點：索引區的大小難以決定，太大浪費空間，太小怕不夠用。

解決索引區大小之方法：(1)Linked Index (2)Multilevel Index (3)Combination

### Disk scheduling algorithms的種類 ：

(1)FCFS (2)SSTF (3)SCAN Scheduling (4)C-SCAN Scheduling (5)Look Scheduling

- Disk cache：由OS所控制，disk cache內儲存最近曾被存取過的磁碟資料，當應用程式提出對磁碟存取要求，若disk cache 已有這筆資料，則從cache存取

- RAM Disk：為使用者控制，OS 將一部分的主記憶體作為RAM Disk，開機時，將磁碟資料全部載入此段空間並且在memory內執行這些作業，而不是在disk上執行，速度快，但僅能暫時儲存，關機時，則將資料存回磁碟。

- Difference：RAM disk內容完全由user控制，無hit/miss等問題，開始或結束時須將資料載入或回存於disk內，資料僅能暫時保存。

- Disk cache內容完全由O.S.控制，有hit/miss的問題，若miss則仍要到disk存取資料，資料可以永久保存並來自不同disk。

### File system存取方式：

(1)Sequential access method：檔案中的資訊是按記錄次序一筆接一筆處理的，為目前最通用的檔案存取方式。

(2)Direct access method：檔案由固定長度的邏輯記錄所組成，讓程式採用直接存取法，讀出或寫入檔案的任意區段，常用於大型資料庫。

(3)Indexed sequential access method：利用primary index file包含指向secondary index file的指標，而secondary index file則包含指向實際data block的指標。

### Cache Memory：
快取記憶體是界於cpu和主記憶體之間的高速記憶單元，通常較常用到的資料會被存放於快取記憶體中，以減少CPU存取主記憶體的次數，以提高處理速度。

Problem 1 : 在cache找不到需要的資料時則必須到主記憶體中讀取，造成大量資料再兩層記憶體中傳輸，使overhead過高，此問題和Hit Ratio有關，通常程式指令執行上都有固定形式，因此不需太大快取就有不錯的Hit Ratio了。

Problem 2 : 快取記憶體和主記憶體有可能會造成兩份資料一致性的問題。

### 解決方法
(a)write back資料寫回快取記憶體即可，將來釋放快取再存回主記憶體，這種方式資料有數個copy在存回主記憶體前容易造成不一致。

(b)write through資料不只寫回快取也同時寫到主記憶體，寫入速度慢。

Disk striping：利用一群disk來改善disk速度，每個data block被打散成數個sub-blocks存在每一個disk中，因為這些sun-blocks利用平行處理的方式transfer into memory，所以可以加快速度。