# 作業系統筆記
## chapter 1
電腦的基本架構:

作業系統核心概念:
* 資源分配器
* Manages all resources
* Decides between conflicting requests for efficient and fair resource use
* 控制程式
* Controls execution of programs to prevent errors and improper use of the computer
* interupt base : 呼叫才會做處理
* 作業系統中永遠運行的程式就是kernel，除了kernel以外的，都叫system program或application program

* CPU會把資料從memory裡丟到local buffer，然後memory會直接跟buffer做溝通
* interrupt比喻:櫃台叫你去填表單，填完後再告訴他，你填東西的這段時間，櫃台還可以服務其他人
* device drive(hardware)或application(software)做完後，會發出interrupt告訴CPU任務做完了

* interrupt handling
* polling:一個一個檢查誰需要interrupt
* vector:回傳一個值告訴作業系統誰需要interrupt，較有效率，OS大多採用這個
* Storage-Device Hierarchy 越往下越慢，容量越大

* bootstrap program:把kernel load進去
* timesharing:透過很短暫的時間快速切換工作，讓user有種OS只服務他一人的感覺(時間管理大師)
* Memory Layout for Multiprogrammed System
* dual mode : 有些東西不能讓使用者直接碰觸到，所以要有區分
* user mode : user可以直接存取呼叫
* kernel mode : user要透過system call來存取呼叫
* system call : 讓user存取system program的介面，user呼叫interrup，讓kernel去存取受到限制的資源(kernel mode)
## chapter 2
* Operating System Services
* User interface
* Program execution
* I/O operations
* File-system manipulation
* Communications
* Error detection
* Resource allocation
* Accounting
* Protection and security
* 作業系統為甚麼不採取完全沒有錯誤的方法:會運行的很慢，找出問題並解決，才是重點
* 作業系統架構:
* API:再對system call做一層包裝，因為sys call會隨版本更新變動，透過一個共用介面來簡化程式
* 一個sys call後會做非常多事
* 只服務一個user single tasking，memory只有一個process:
* 單晶片，沒有作業系統，用bootloader載入程式，更簡單基本
* 多人多工OS，memory有多個process
* link and load
* link:把函式庫link進二進位檔
* load:把執行檔從disk載入到memory
* monolithic structure:UNIX使用，不把系統分太細，主要分為兩大塊:
* system programs
* the kernel
* system call interface
* file sys、CPU scheduling、memory management...
* UNIX的架構，沒有layer的概念:
* linux structure:在unix加入modular design
* 原先的設計是有新的裝置controller要加入，整個系統就要重新compile
* modular:可以把一些功能load到kernel裡，不用重新compile
* layer approach:
* 每一層depend on上一層
* 沒效率，因為底下operation都會做到
* 中間的層難以排序，沒有一定的相依性
* micro kernel:減少kernel大小，需要用到時再從user space載入到kernel
## chapter 3
* process:執行檔load到memory後就稱為process
* memory layout
* 程式 to 程序
* 程式檔案的頭部會存放資訊告訴OS怎麼把它放到記憶體裡，程式進入點在哪
* windows: PE(Portable Executable) Header
* Linux:ELF(Executable and Linkable Format)
* process state
* 前面的layout沒有儲存process state的資訊，所以要有PCB(process control block)
* 一個process對應一個PCB
* PCB內會有pointer指向真實在memory的位址
* CPU Switch From Process to Process
* context snapshot:將被switch out的process的資訊(register、IO、進度)存回PCB，讓下一次再選到這支process執行時，可以重新載入
* process內可能會有很多thread，可以假想成有很多program counter在跑
* process含有兩大部分，PCB與process真實存放的記憶體位址
* PCB與PCB之間會用雙向linked list連接
* process scheduling
* 為了避免去檢查整個list，所以用queue存放，增加效率
* ready queue : 存已經可以執行的process的PCB
* wait queues : 存還不能馬上執行(等待IO、...)的process的PCB
* 
* schedulers
* long term/job scheduler : 每幾秒甚至每幾分鐘才執行一次，挑一批process進入ready queue，限制多少process可以進入ready queue
* 會盡量讓I/O 與 CPU bound process各佔一半比例，避免太多人排隊給CPU執行
* 隨著電腦越來越強，這種機制已漸漸被淘汰
* short term/CPU scheduler : 幾ms執行一次，挑一個process執行，限制每個process可以執行的時間
* medium term scheduler : 因為某些原因導致ready queue內放的不是想要的，這時候就用swapping
* swapping : 把process直接從memory丟到disk去(並非丟執行檔，而是記憶體原封不動的丟)
* 比喻:long term->會議室外的等待空間，short term->每個人可以報告的時間
* context switch
* context就是PCB
* context switch的時間，CPU無法做任何事
* context switch時間減少，CPU效率提升
* process creation
* 用parent產生children的概念
* 會用parent process來產生新process是因為這樣會更方便複製process的資料結構也就是直接把parent複製一份fork，然後改pid即可
* 父子process可以share記憶體，所以設計可以非常靈活
* 
* process在fork完後才會將執行檔load進memory，然後存指標到PCB
* 父process會等待子process結束後才能結束
* 執行一個程式 : 父process執行fork -> 子process執行exec
* fork，假設child的pid都為0
* fork回傳的是自己的pid，並非child process的pid
* fork完後產生child，parent與child除了pid之外都一模一樣
* 當CPU選中child去執行時，就會跑到case pid==0裡，然後執行exec把這段程式碼蓋掉成想要的
* process termination : process結束後釋放記憶體
* parent process有權限把child process終止，以避免沒有把記憶體釋放乾淨
* thread概念:一個process裡有不同的program counter，所以一個process裡可能有多個TCB(thread control block)
* chrome記憶體用量大原因:每開一個分頁就是一個process，會這樣做是為了避免某個分頁掛掉，其他分頁也跟著掛掉
* interprocess communication(IPC)
* shared memory : 兩個process共用一塊記憶體，存取快速便利，但不安全
* 問題:要如何解決寫入到一半時被interrupt後，造成其他人讀取到不正確的值?(同步問題)
* message passing : process之間透過類似system call的方式從kernel讀取共用的記憶體，較安全
* 
* communication
* direct : 直接發送接收資訊，1對1
* indirect : 放到mailbox，別人再從mailbox拿出來
* synchronization
* blocking : 等到receive完後才能結束send，等到send完所有message後才能receive
* non-blocking : 丟完後就可以結束send，接受訊息也不管有沒有正確
* pipe : 用父子process的關係讓溝通變簡單(約定某塊記憶體收發訊息)
* remote procedure call(RPC):執行遠端電腦的system call或程式
## chapter 4
* Single and Multithreaded Processes
* 一個PCB可能指向多個TCB(依實作而定)
* 為何要用thread : 不用每次都複製一大堆相同程式碼，節省記憶體
* Responsiveness
* Resource Sharing
* Economy
* Scalability
* concurrency : 快速切換來同時運行多個task，但實際上同時只執行一個
* parallelism : 用multicore來同時執行多個task，真正意義上的同時執行多個
* data parallelism : 資料分成不同core來執行，某段只由一個core執行
* task parallelism : 同一段資料可能有多個core來執行
* user and kernel threads
* 
* many to one : 有一個thread call system call後就interrupt process，造成其他thread也跟著被暫停
* one to one : user thread自動產生或對應到一個kernel thread，library與kernel息息相關
* many to many : 可以提供1對1，也可以提供多對多，自動判斷如何對應(檢查thread pool)
* two level : kernel thread被綁定在user thread
* implicit threading : compiler自動幫你multithread，但並沒有在程式碼裡實作multithread，顯性則反之
* fork-join parallelism : compiler自動把task切割fork出去執行，然後把結果join起來
* grand central dispatch : runtime時才變成multithread
* serial queue: 序列化執行，無法平行化的程式會丟到這個queue
* concurrent queue: 平行化執行
* multithread process執行exec後會將所有thread覆蓋掉
* multithread下的fork有兩種
* 複製所有thread
* 只複製執行到fork的thread : 通常會用後fork後馬上exec
* signal handling : 其他process對發生例外狀況的process發出通知，做後續處理(關閉某個或某些thread)
* thread cancellation
* asynchronous : 立即cancel thread
* deferred : 檢查現在是否可以被cancel，不行的話就等待thread做完後才cancel
* off : 無法被cancel
* thread-local storage(TLS) : 存一些function與function之間的information，thread特有的資訊
* scheduler activations : user thread與kernel thread之間溝通的流程
* light weight process(LWP) : 存user thread與kernel thread之間的關聯對應資訊的資料結構，位於kernel space
* 讓user thread以為LWP是一個virtual process
* 
* 每個user thread都會對應到一個LWP，LWP也只會對應到一個user thread，但可能對應到多個kernel thread
* upcall : kernel thread通知user thread訊息
* 可以是kernel thread產生多個LWP，也可以是多個LWP assign到不同的kernel thread，有很多種做法
* LWP就是user thread在kernel的代理人
## chapter 5
* CPU scheduler : 在ready queue中尋找下一個適合的process執行，雖然真正的最小執行單位是thread，但是存放的資訊還是在process裡，所以scheluder是選擇process而不是thread，process選完後才近一步選thread，thread再去選用哪個CPU來執行。
* preemptive vs non-preemptive
* preemptive : 執行到一半時可能因scheduler而被強制交出CPU使用權，有效率
* non-preemptive : 會等到該process離開running state後才執行scheduler，running自己主動呼叫scheduler的情形就屬於non-preemptive，沒效率
* 呼叫scheduler時機 #必考
* running state to waiting state (做IO) => non-preemptive
* running to ready state (interrupt occurs、時間用光了) => preemptive
* waiting to ready (IO完成)，比喻:填完表單的人可以讓櫃台決定要不要先服務你，而不用從頭開始排隊 => preemptive
* running terminate (執行結束) => non-preemptive
* dispatcher : scheduler選好下個process後，就交給dispatcher，做以下處理:
* context switch
* 把現在的process存回PCB
* 把選定的下個process的PCB資訊載入到CPU register
* switching to user mode
* user mode之間的轉換
* jumping to the proper location in the user program to restart that programjum
* program counter指到接下來要執行的process的程式碼
* dispatch latency : 執行dispatch的時間
* 沒有人可以打斷dispatch，比喻:皇帝旁的太監
* scheduling criteria
* CPU utilization : CPU越忙越好，榨乾時間
* throughput : 單位時間處理越多process越好
* turnaround time : 每個process從開始處理到結束的時間越短越好
* waiting time : process在ready queue裡等待時間越短越好
* response time : 從request到response的時間越短越好
* 不可能全部都同時優化
* First Come First Served(FCFS) : 依據進來的順序去執行，也就是直接拿ready queue的第一個element
* 
* 但average waiting time是17，如果先做P2、P3，可以讓average waiting time減少
* 
* convoy effect : 讓short process先做，就可以降低waiting time
* 為了降低waiting time，所以有了SJF
* Shortest Job First (SJF)
* 但問題是還沒執行前都不知道burst time是多少，所以通常用預估的方式來決定burst time
* 預估方法:
* EX: 下一次預估 = 本次預估\*0.5 + 實際時間\*0.5
* shortest remaining time first : FCFS與SJF結合
* 看剩多少時間要執行，先選最少的，此方法為preemtive，如果出現一個更少剩餘時間的process，就會強制切換
* 
* priority scheduling
* 選低priority值的process執行
* Round Robin
* 每個process執行一段時間(time quantum q)就換人，一直輪流下去
* time quantum q usually 10-100 ms,context switch < 10us
* quantum 通常設計為 80% of CPU bursts should be shorter than q
* 在現實中很少見，因為人腦無法快速切換工作
* Multilevel queue : 把不同種類的process丟到不同的queue，現在OS大多用這種方法
* 用不同排程演算法處理不同queue
* queue之間也有priority
* Multilevel Feedback queue : process可以在不同queue之間移動，會有一些機制來把process丟到其他queue，避免等太久
* 各種排程的比較
* 期中必考1
* 期中必考2


* Multiple Processor scheduling
* Homogeneous processors : processor之間的運算能力是一樣的
* Asymmetric multiprocessing : 有一個專門負責scheduling的processor
* Symmetric multiprocessing(SMP) : 現代OS常用，每個processor自己決定CPU scheduling
* 所有thread存在common ready queue
* 所以多個processor有可能選到同一個thread，產生大問題
* 因此現在改變為每個processor都有一個ready queue
* 每個thread會被分配到不同的ready queue裡
* 把所有multiple processor放到同一個chip就叫multicore processor
* Multithreaded Multicore System
* 趁其他thread在存取記憶體時切換到另一個thread執行
* Chip-multithreading : 每個core裡都有2條hardware thread，完全由硬體實現，會多一套register來存另一個thread的register值
* hyperthreading in Intel
* two level of schduling
* kernel thread對應到hardware thread就會用前面提到的排程演算法
* load balancing : 不讓每個CPU上面放的task太多
* push migration : 把overloaded CPU的task push到其他CPU
* pull migration : 閒置的CPU把task從overloaded CPU拉過來
* Processor Affinity : 盡量讓task留在同一個CPU，讓快取起到作用
* soft affinity : OS想辦法讓task只在一個CPU上執行，但不保證
* hard affinity : 保證task只在某幾個CPU上執行
* Non-uniform memory access (NUMA) :
* 移動task後，CPU就要存取到其他CPU的memory，這樣的速度很慢
* 因此盡量避免移動task到其他CPU
* 
* 一個core同時只能處理一個hardware thread，這是concurrency而非parallelism
* Real time CPU scheduling : 要求在很準確時間執行的task(EX火箭)，不能被其他process影響
* soft real-time : priority高的先處理，但無法保證高priority一定可以被schedule
* hard real-time : 一定滿足條件，重點放在執行的時間
* event latency : event發生到被serve的這段時間
* interrupt latency : interrupt進來後直到執行完interrupt的時間
* dispatch latency : 選好下個process到執行完dispatch的時間
* 
* dispatch有可能conflict，也就是要等別人處理完資料，花額外時間去處理conflict
* preemptive,priority based scheduling : 一個更緊急的事件出現後，要把現在的process換掉
* 每個thread會periodic的出現，每p秒出現一次，執行t秒(event latency)，deadline是d
* 需求 : 0 ≤ t ≤ d ≤ p
* 
* Rate Montonic Scheduling
* 給每個thread或process一個period或priority，週期越長，priority越低，週期越短，表示常常執行，priority越高
* missed deadline
* 公式算出來是83%小於2個utilization相加的0.94，因此會miss
* Earliest Deadline First Scheduling(EDF) : 依據離deadline的時間來排程
* 最佳theoretically optimal solution 比rate montonic好
* 但經常切換，所以要考慮到context switch的時間，所以不一定適用所有狀況
* Proportional Share Scheduling
* 所有process有T個share
* 現在已經有N個share
* 
* 判斷D進來後是否有辦法分配下去，無法的話就拒絕
* linux scheduling
* version 2.4
* global runqueue/expired queue
* 把所有thread丟到runqueue
* runqueue的process執行完後丟到expired，直到runqueue都被執行完後，就開始執行expired queue
* 高priority得到更大的quantum
* version 2.5
* priority從0~140，用140個queue的array存放所有thread
* CPU可以直接從priority最高的queue內拿出thread
* 有thread存於queue的priority就會把該priority的bit變為1，使搜尋時間達到O(1)
* 高priority得到更大的quantum
* version 2.6.23
* completely fair scheduler(CFS) : 值的部分重新設計
* 
* virual run time : 記錄每個thread用了多少時間
* 根據virual run time來決定下個選誰，不只考慮priority
## chapter 6 & 7
* race condition : 多個process在同時競爭(使用)相同的資源，結果與存取資源的順序性有關連時，race condition就會發生
* Synchronization : 避免race condition的發生
* critical section problem
* critical section : 會動到與其他人share data的程式碼段落，簡稱CS
* critical section protocol : 在執行到critical section之前與之後去做一些措施保證critical section執行期間不會被schedule out
* entry section
* exit section

* solution
* mutual exclusion : 在執行critical section期間，只有該process可以做，沒有其他process可以中途插入，一定會等critical section做完
* 晚到的entry會被block起來
* 執行結束後知會其他process可以進入critical section了
* progress : 要持續進展，否則其他人會被卡死，無法執行下去
* 在多個entry中決定下個進入的entry
* bounded waiting : 要保證不會無限地等下去，遲早有天會輪到你去存取
* 不能根據速度去決定下個entry否則會不符合bounded waiting，可能有人無限等下去，永遠選不到他
* EX 
* 只判斷是不是輪到自己
* 無法滿足progress與bounded waiting條件，因為如果只有一個process，而且turn又不符合條件，就會無限等下去
* EX 
* 只判斷對方要不要做，對方要做，就等對方
* 也無法滿足progress與bounded waiting條件，如果同時執行到while，則兩邊會互相等待，無限等下去
* peterson's combined solution
* LOAD與STORE都不可被中斷
* 同時判斷 是不是輪到自己 與 對方要不要做
* 
* 滿足所有條件
* Prove the validity of a critical section?
* Mutual exclusion
– 假設兩個（以上） 的processes可以同時進出CS，找出其矛盾
* Progress
– 沒有process在CS中，一個process要進去CS，一定可以進去
– 多個process要進CS，在有限的時間內做出決定
* Bounded waiting
– 找出次數的上限
* peterson's solution
* comiler或硬體可能把`x = 100;`與`flag = true`調換順序，使Mutual exclusion條件無法符合
* 所以需要有hardware支援才能真正解決Synchronization問題
* Synchronization Hardware
* Memory barriers : 實現某些單位的memory之更改可以馬上被別人知道
* memory model
* strongly ordered : 一個processor對memory做任何動作會馬上讓其他processor知道
* weakly ordered : 以上反之
* 
* Hardware instructions : 透過硬體確保不會在執行過程中被interrupt，不滿足bounded waiting，有機會永遠等不到
* Test and Set Instruction
* 
* Compare and Swap Instruction
* 至少確保不會有多個人去使用
* 實作出lock的概念

* 在entry與exit section內都有可能發生race condition，所以其實這些解法都只是將複雜的大問題(critical section)轉化成小問題(entry與exit section)，但問題本身還是存在，在讀寫lock變數時還是有機會被interrupt。
* Bounded-waiting Mutual Exclusion with compare-and-swap
* Atomic variables : 確保寫入變數時不會被interrupt
* Bakery Algorithm
* [麵包店算法](https://zh.wikipedia.org/wiki/Lamport%E9%9D%A2%E5%8C%85%E5%BA%97%E7%AE%97%E6%B3%95)
* 為何不使用hardware解決Synchronization就好?
* 因為hardware較適用於實作entry section的single且簡單的資料結構(int、bool...)，而無法處理CS內複雜的資料結構(buffer、array...)
* 無法達成Bounded waiting條件，無法確保所有人都會被選中，可能一直等下去
* 解法 : 軟硬兼施，改用mutex lock或semaphore
* busy waiting : 不context switch，而是一直不斷檢查，用於context switch cost 很高的情形
* mutex lock : 在OS層面實作lock的library
* (mutual exclusion) lock
* lock變數都是使用Atomic variables
* 可以滿足三大條件
* busy waiting
* 
* Semaphore
* busy waiting
* user可以確保哪個process先執行
* 
* 
* 
* 等到P1跑完`signal(synch);`後，P2才可以進入`S2;`
* 不用busy waiting的方法?
* 改用waiting queue(list指標)

* Four Typical Uses of Semaphores
* Mutual exclusion
* Force suspend : 強制某個process先執行， Keep the execution in a particular order
* Count-down lock : 限制可以進入的process數量
* Notification : Indicate that an event has occurred
* deadlock and starvation
* starvation
* indefinite blocking
* A process may never be removed from the semaphore queue in which it is suspended.
* 
* priority inversion
* 高priority因為lock的關係導致必須等待低priority的人
* Priority Inheritance : 低priority的task卡住要高priority的task，就要把priority繼承過去，避免之後被其他較低priority的task(Task2(M)) preempt
* Monitor : 自己定義資料結構(ADT)，OS會自動保證Mutual exclusion，不會有deadlock的狀況
* signal and wait : 離開去等待，通知下一個人
* signal and continue : 繼續做完剩下的事才離開
* 針對每筆資料都可以有一個condition
* 用Semaphore實作出Monitor
* What’s the different between semaphore and monitor?
* 比喻 : monitor像公廁，一個人進去其他人就不行進去
* 比喻 : semaphore像bicycle hire，大家共用某幾台bicycle
* Classical Problems of Synchronization
* Bounded-Buffer Problem
* 
* 
* 如果`wait (mutex);`與`wait (empty);`寫反，則可能造成deadlock的狀況
* Readers and Writers Problem
* 有一shared data set
* reader : 只會讀取，不會寫入data set
* writer : 可讀可寫
* problem
* 多個reader同時讀取
* 同時只能有一個writer存取
* writer寫入時，reader不能讀取
* 如果有reader在讀，writer必須等待
* Dining-Philosophers Problem

## 期中考古題