# 作業系統期末筆記
<font color="#f00">會考表示老師說有機率會考的，並不代表一定會考，沒標的也可能會考</font>
---
:::success
:::spoiler click to open TOC
[TOC]
:::
## Chapter 5 CPU Scheduling
### Little’s Formula
### Simulations

## Chapter 6 Synchronization Tools
* 同時執行多個Processes時，可能導致存取shared data時資料不同步
* 所以需要同步工具來讓Process執行時可以有一個順序，確保資料可以同步
### Consumer and Producer Problem
* 加入counter的改良版可以解決部分同步問題，但還是會有像Race condition的問題存在
#### Producer

While(1){
    /* produce an item in next produced */
    while(counter == buffer_size){
        // Do nothing, because the buffer is full.
    }
    buffer[in] = next_produced;
    in = (in+1)% buffer_size;
    counter++;
}

#### Consumer

While(1){
    /* consume an item in next consumed */
    while(counter == 0){
        // Do nothing, because the buffer is empty.
    }
    next_consumed = buffer[out];
    out = (out+1)% buffer_size;
    counter--;
}

#### Race Condition
* 最後的結果取決於於兩個Processes的執行順序與時機
### Critical Section Problem
* 指的是一個存取共用資源的程式區塊，而這些共用資源有無法同時被多個Process存取的特性。
* Common variable
* Update table
* Writing file
* 同時間只允許一個Process存取共用資源的程式區塊，這段程式稱為CS（Critical section）
* 不在CS（Critical section）執行的程式，稱為RS(remainder section)
### Solution to Critical-Section Problem <font color="#f00">會考</font>
#### Mutual Exclusion
* 若Process在執行「critical section」，其它Process都不該進入它們的「critical section」(並不是其它Process不能進入CPU哦，只是其他Process在CS外面等待)
#### Progress
* 如果有Process想要進入critical section，並且沒有人在critical section，不想進入critical section的Process不可以阻礙其它Process進入critical section，即不可參與進入critical section的決策過程。
* 必須在有限的時間從想進入critical section的process中，挑選其中一個process進入critical section，隱含No Deadlock。
#### Bounded Waiting
* 若一個Process想執行CS，等待的次數必須是有限的，不能無限被插隊。即若有 n 個Process，則任一 Process 至多等待 n-1 次(n-1個Process)即可進入，隱含 No starvation (沒有人餓肚子，每個Process都要吃東西)。

### Peterson's Solution (軟體解) <font color="#f00">會考</font>
* Solution for two processes
* int turn // 輪到誰進入CS
* Boolean flag[2] // 若value為true代表準備好要進去CS

do {
    flag[i] = true;
    turn = j; //禮讓的概念
    while(flag[j] &&turn == j){
        //Busy waiting
    }
    //CS
    flag[i] = false //代表CS的區塊做完了，所以要退出才能讓其他Process進去CS
    //RS   
}while(1)

* Mutual Exclusion: 如果P_i要執行，那flag[j]=false或是turn=i (這代表j不想執行，或是優先權在i的手上)
* Progress: 以P_j要執行為前提，有三種情況可能發生
* P_i不想執行Pj直接進入
* P_i、P_j同時想執行，優先權在i的手上，P_i先執行
* P_i、P_j同時想執行，優先權在j的手上，P_j先執行
* Bounded Waiting：當P_i執行完後又想執行，但這時P_j也想執行，這時優先權在j的手上，所以P_j先執行(P_i最多等一次就可以進去)

### Synchronization Hardware (硬體解) <font color="#f00">會考</font>
* 用lock的方式保護critical section
#### Test_and_set <font color="#f00">會考</font>

boolean test_and_set(boolean *target){
    boolean rv = *target; //儲存原本的值
    *target = True; //把值設成True
    return rv; //回傳原本的值
}

do{
    while(test_and_set(&lock)){
        // Busy waiting
    }
    //CS
    lock = false //做完CS讓給其他Process做
    //RS
}while(true)

#### Compare_and_swap

int compare_and_swap(int *value,int expected,int new_value){
    int temp = *value;
    //如果value等於預期的值就設成新的值
    if(*value == expected){
        *value = new_value;
    }
    return temp; //回傳原本的值
}

do{
    while(compare_and_swap(&lock, 0, 1)!=0){
        //Busy waiting
    }
    //CS
    lock = 0 //解開鎖讓其他Process進去CS
    //RS
}while(1)

#### [Bounded-Waiting Mutual Exclusion](https://www.youtube.com/watch?v=CFm_F3OhHGQ&ab_channel=TechGuiders) <font color="#f00">會考</font>

do{
    waiting[i] = true;
    key = true;
    //waiting==false也會解開
    while(waiting[i]&&key){
        key = test_and_set(&lock); //當lock解開的時候，key變false會跳脫迴圈，但又會把lock鎖上
    }
    waiting[i] = false; //因為可以進入CS所以就不是在等待了
    //CS
    j = (i+1)%n; //下一個process
    //檢查有沒有process在等待
    while((j!=i)&&!waiting[j]){
        j = (j+1)%n;
    }
    if(j==i){
        lock = false; //沒有process在等待了
    }
    else{
        waiting[j] = false; //找到有在等待的process，換這個process進去CS
    }
    //RS
}while(1)


### Mutex Locks (互斥鎖)
* 這是一種programmer可以用的方式，利用acquire()和release()取用lock，但是如果取不到lock的話，就會進入busy waiting
* Busy waiting 又稱 spinlock

acquire(){
    //當available為1時不會進入迴圈，當available為0的時候就會進入迴圈等待
    while(!available){
        //Busy waiting
    }
    //跳脫迴圈就代表程式進入CS了，所以又要把available設成0
    available = false;
}
release(){
    available = true;
}
do{
    acquire lock
    //CS
    release lock
    //RS
}

### Semaphore implement with busy waiting
* S 是一個整數變數，數值代表有幾個resource是可用的
* Binary semaphore S = 0 or 1，如果是Binary那就跟Mutex lock一樣
* Counting semaphore S: integer範圍大於 2

wait(S){
    //if S > 0 means there is available resource
    while(S<=0){
        //Busy wait
    }
    S--;
}
//Add more resource
signal(S){
    S++;
}

//確定P2可以在P1後執行
synch = 0;
P1:
    S1;
    signal(synch); //signal之後P2就可以執行了
P2:
    wait(synch); //在等signal
    S2;

### Semaphore implement with no busy waiting
* Block - 把Process放進去waiting queue
* Wakeup - 把一個Process從waiting queue放到ready queue
* The negative value indicates a number of processes waiting, and if the value is positive, it can use resource directly.

typedef struct{
    int value;
    struct process *list;
}semaphore;

wait(semaphore *S){
    S->value--;
    if(S->value < 0){
        //add this process to S->list
        block();
    }
}
signal(semaphore *S){
    S->value++; //釋放一個可以用的資源
    //若有process在等待的話就可以wakeup
    if(S->value <= 0){
        //remove a process P from S->list
        wakeup(P);
    }
}

### Deadlock and Starvation
#### Deadlock
* 兩個processes在互相等待被對方占住的資源。
#### Starvation
* 無限期的blocking，有一個Process可能永遠不會從semaphore waiting queue中移出來。
#### Priority Inversion
* 低優先權的process佔住了高優先權process的資源，如果想要解決這個問題的話，就要透過priority-inheritance protocol解決。

### Problem with Semaphore
* signal (mutex).......wait(mutex) -> 順序錯誤沒有效
* wait(mutex)........wait(mutex) -> Lock住
* 遺漏wait(mutex)或是signal(mutex)，亦或是兩個一起遺漏掉。

### [Monitors](https://www.youtube.com/watch?v=ufdQ0GR855M&ab_channel=NesoAcademy)
* 一次只能有一個process可以在monitor內執行。
* Processes share data in the monitor
* Can only access locally variable that is mean define in the monitor

monitor name{
    //Shared variable declarations
    int x;
    int y;
    //Processes
    function P1(){
    
    }
        ....
    function Pn(){
    
    }
    //Init
    initialization_code(){
    
    }
}


#### Condition Variables
* 只有Monitor無法做到syhronization，所以需要conditon
* x.wait()：process要invoke一個operation時，要一直等到x.singal()可以使用，不然就是suspended。
* x.signal()：如果任何的x.wait()被invoked的話，其中一個process就會回復執行。
* 但如果沒有任何x.wait()的話，對variable就不會有任何影響。

#### Condition Variables Choices <font color="#f00">會考</font>
* If process P invokes x.signal(), and process Q is suspended in x.wait(), what should happen next? Ans:理論上因為P.signal() Q會開始執行，P也在正在執行，但是兩個Process不能同時執行，所以有下列幾種可能
* Signal and wait：Ｐ必須等待Ｑ，直到Ｑ離開monitor或是等待其他condition。
* Signal and continue：Ｑ必須等待Ｐ，直到Ｐ離開monitor或是等待其他的condition。
* Both have pros and cons：執行者可以自行決定要使用哪種語言。

## Chapter 8 Deadlock
### Deadlock Characterization <font color="#f00">必考</font>
* 四個條件同時滿足會產生Deadlock
* Mutual Exclusion: Resource同時只能被一個Process使用
* Hold and wait: Hold至少一個Resource，並且在等待其他被占用的Resource
* No preemption: 不能搶奪其他人的Resource，要等其他Process釋放
* Circular wait: 形成一個Waiting迴圈
* Deadlock with Mutex Locks
* First在等Second，同時Second也在等First

### Resource-Allocation Graph
* Process
* Resource with 4 instances
* Request edge – P_i->R_j
* Assignment edge – R_j->P_i
* 沒有cycle一定不會Deadlock
* 有cycle
* Resource只有一個instance會deadlock
* Resource有多個instance，不一定會deadlock
* <font color="#f00">不一定會deadlock!</font>
#### Example of a Resource Allocation Graph
#### Resource Allocation Graph with a Deadlock
#### Graph with a Cycle but No Deadlock
* T₂或T₄做完就可以解開了

### Methods for Handling Deadlocks
#### Deadlock prevention <font color="#f00">可能會考連連看</font>
* 讓它至少一個條件不成立就不會deadlock了
* Mutual Exclusion: 對於不共用資源，必會互斥(但這通常不可能可以預防，因為有的還是會需要運用到共用資源)。
* Hold and wait: Process必須保證必須保證在要求一項資源時，不能佔用其他資源
* No preemption: 只要Process握著一些資源，但得不到其他的，就要先全部釋放，再重新請求。 (但可能造成Starvation，因為低優先度的佔走高優先度的Resource)
* Circular wait: 對Resources強制安排線性順序，不讓circular wait的條件達成
#### Deadlock Avoidance <font color="#f00">(確保系統不會進入unsafe state)</font>
* 每個Process要知道對不同resource type需要多少
* 用deadlock-avoidance演算法(Bank algorithm)檢查，確保系統於Safe state。
##### Safe state
* 存在≥1組"Safe Sequence"使得processes依此順序執行，皆可完成工作就是安全的狀態，如果找不出一組Safe Sequence就是在不安全的狀態。
* System在safe state不會產生deadlock
* 系統在unsafe state可能會產生deadlock

##### Resource-allocation grap (Single instance)
* 當process要向resource產生要求時，claim edge會出現
* 當process要求resource時，claim edge就會變成request edge
* 當resource要給process時，request edge就會變成assignment edge
* 當process釋放resource時，assignment edge就會變成claim edge

##### [Banker’s algorithm (Multiple instance)](https://www.youtube.com/watch?v=2V2FfP_olaA&ab_channel=Scholarlythings) <font color="#f00">會考</font>
* Need = Max - Allocation
* 變化題 <font color="#f00">高機率考</font>

#### Deadlock detection
* 容許發生deadlock，但要能偵測到且恢復
##### Single Instance of Each Resource Type
* 檢查是否有Cycle在graph裡有的話就是deadlock
##### Several Instances of a Resource Type
* 如果找不出一組Safe Sequence就是deadlock
##### Recovery from Deadlock
* Process Termination:
* 丟棄所有deadlock Process
* 一次丟一Process直到不再deadlock了
* [Resource Preemption](https://www.geeksforgeeks.org/drawback-of-resource-preemption/)
* Selecting a victim – minimize cost
* Rollback – roll back the process and place it on some safe state and restart it
* Starvation – same process may always be picked as victim, include number of rollback in cost factor

## Chapter 9 Main Memory
### Base and Limit Registers
* Base跟limit是一對的
* CPU在存取記憶體會檢查存取的記憶體是否在合法的範圍內
### Address Binding
* Compile time(編譯時間)：在編譯的時候就決定好記憶體位置，則須產生絕對(Absolute)位址目的碼(程式碼)，且如果需要重新換一個記憶體位置只能透過重新編譯(recompile)。
* Load time(載入時間)：在程式啟動成為Process的時候決定好記憶體位置。在compile的時候先不配置記憶體位置，生成relocatable code，在loading的時候才依照記憶體的空閒空間去配置。比起compile time來說較有彈性，因為程式可能先被compile後過了一段時間才被執行，缺點依然是當需要重新換記憶體位置的時候，需要呼叫loader去重新載入Process。
* Execution time(執行時間)：在程式執行中決定記憶體位置，若process在執行期間需要從記憶體的某一段移到另一段，則定位必須在執行時期完成。
### Logical vs. Physical Address
* Logical Address：CPU所產生的虛擬位置，又叫做virtual address
* Physical Address:記憶體看到的位置(經過memory unit處理過)

### MMU (Memory Management Unit)
* Base register maps virtual to physical
* Base register now called relocation register

### [Dynamic Linking and Shared Libraries](https://ithelp.ithome.com.tw/articles/10225833)
* Dynamically linked libraries (DLLs):System libraries在程式執行時link
* Static linking:直接把全部的函式庫一起塞進去程式裡，變成一大包，並且在loading的時候也是整包一起Loading
* Dynamic linking:要用到時再link
#### 優點 <font color="#f00">考優缺點</font>
* 優點
* 更省記憶體，多個Process可以同時存取，DLL只需要一個實體在Main Memory
* 擴充性好，更新時只需要覆蓋新的DLL檔就好
* 缺點
* 比較吃效能
* 速度沒有static linking快

### Swapping
* 在程式執行時，process有時會需要暫時離開記憶體，之後會再搬回來執行，這就叫做swapping
* 搬上搬下的動作我們稱為roll out跟roll in。
* 而在這裡的硬碟(disk)我們會將它稱作backing store
#### Swap還會遇到一個問題，如果他要移除正在執行的Ｉ/Ｏ呢？
* 不把它swap out讓他繼續執行
* 就把它swap out，不做I/O了
* 交給kernel來做(在記憶體內搬來搬去)，但是會造成double buffering，有overhead的可能性存在(這是最常用的方法)

### Contiguous Allocation
* 因為資源有限，所以需要有效率的進行分配。
* 此方法是一種早期的方法。
* Relocation registers是用來保護Process互相引響，還有防止操作系统的程式和資料。
* Base register: contains value of smallest physical address
* Limit register: contains range of logical addresses each logical address must be less than the limit register

### Multiple-partition allocation
* Variable-partition的尺寸是要有效率的，也就是說尺寸是合Process的需求。
* Hole：是可用的記憶體區塊，各個hole的大小是分散在記憶體中。
* 當一個process到達，便會從一個足夠大的hole中分配記憶體以容納它。
* process退出後會free掉它使用的partition，鄰近free partition做結合。
### Dynamic Storage-Allocation Problem
* First-fit：分配夠大的第一個hole。
* Best-fit：分配足夠大的最小hole，必須搜尋整個列表，除非是按尺寸搜尋，產生最小的剩餘hole。
* Worst-fit：分配最大的hole，也需要搜尋整個列表，產生最大的剩餘hole。

### Fragmentation <font color="#f00">考差別</font>
* External Fragmentation:Hole的記憶體加起來可以給Process用，但不是連續的無法使用
* Internal Fragmentation:分配的記憶體size大於Process實際使用到的
* 藉由壓實(compaction)來減少External Fragmentation：
* 將記憶體內所有可用記憶體放在一起。
* 壓實只可能發在relocation是dynamic，在execution time時完成。

### Segmentation
* 程式是由很多Segmentation組成的
* Function
* Stack
* Array
* Variable
* Main Program

#### Segmentation Architecture
* Logical address consists of a two tuple:[segment-number, offset]
* Segment table
* base: segment實體記憶體位置的起始點
* limit: segment的長度
* Segment-table base register (STBR): 指出segment table在記憶體中的位置
* Segment-table length register (STLR): 指示程式使用segment的數量。
* Validation bit = 0 ⇒ illegal segment

### Paging
* Process的physical address space可以是不連續的狀態，且只要後者可用，process就會被分配到記憶體。
* physical address space被切成一塊塊的frame，要用就從frame分配，避免外部碎片的產生。
* 避免memory chunks有不同尺吋的問題。
* 劃分physical memory到固定大小區塊的稱作為「frames」要是2的指數
* 劃分logical memory到相同大小區塊的稱作為「pages」。
* 追蹤所有的free frames。
* 執行依大小為N pages的程式，需要去找到N個free frames和下載程式。
* 設置一個page table，將logical address轉換至physical address
* Backing store同樣被分為pages。
* 依然會有內部碎片的存在，分配一個frame給process用，但可能不會用完整個frame
#### Address Translation Scheme
* Page number ( p )：用類似於page table的索引表，起該表包含physical memory中每個page的base address。
* Page offset ( d )：和base address連結、定義並發送到memory unit的physical memory address。
##### Paging Hardware
##### Paging Model of Logical and Physical Memory
##### Paging Example
##### Free Frames

#### Implementation of Page Table
* Page table是留在主記憶體中。
* Page-table base register(PTBR)：指向page table。
* Page-table length register(PTLR)：指示page table的大小。
* 記憶體存取問題可以使用Associate Memory或是Translation Look-aside Buffers(TLBs)來解決。
* 一些TLBs在每個TLB entry中，儲存address-space identifies(ASIDs)，且每個process都有獨特的識別碼去提供address-space保護process。
##### Paging Hardware with TLB(translation look-aside buffers)
* TLB 只需要一個access time
* 若沒找到會多一次access time
* TLB miss的話會加到TLB，下次存取就會變快
##### Effective Access Time(EAT)
* α - 代表在TLBs內找到的機率

##### Valid-invalid
* valid: indicates that the associated page is in the process’ logical address space, and is a legal page
* invalid: indicates that the page is not in the process’ logical address space

###### Shared Pages

#### Structure of the Page Table
* Page的尺寸大小為4KB。
* 一個Page table擁有1百萬個entries(2¹²/2³²)。
* 如果每個entry是4B，則4MB的physical address for each page

#### Hierarchical Page Tables
* 分割logical address空間到multiple page tables。
* 可以節省記憶體使用量
#### [Two-Level Page-Table](https://www.youtube.com/watch?v=iZVMaEaJrm8&ab_channel=TechGuiders)
#### 64-bit Logical Address Space
#### Hashed Page Tables
* Each element contains
* Common in address spaces > 32 bits
* The virtual page number
* The value of the mapped page frame
* A pointer to the next element
* Virtual page numbers are compared in this chain searching for a match -> If a match is found, the corresponding physical frame is extracted
#### [Inverted Page Table](https://www.youtube.com/watch?v=R-WgaQQHSPw&ab_channel=TutorialsPoint%28India%29Ltd.) <font color="#f00">會考</font>
* 所有Process使用同一個page table但是需要多一個pid來搜尋
* 這樣就不用每個process都有一個自己的page table，可以減少記憶體需求但是增加搜尋時間
* 可以利用TLB加速

## Chapter 10 Virtual Memory
* 只需要載入部分的程式就好，程式受限於physical memory大小
* Logical address space可以大於physical address space
* 同時可以執行更多Program

### Demand Paging

* 只有需要的時候才會載入到記憶體
* Lazy Swap:只需要用到的時候才會swap到記憶體裡
* 優點
* Less I/O need
* Less memory need
* Faster response
* More users
#### Valid-Invalid Bit
* V: In memory
* I: Not in memory, it will be "page fault", if MMU address translate

#### Page Fault
1. 當參考的page是invaild
2. 觸發trap
3. 去硬碟找要的資料
4. 找到資料後放到frame裡
5. reset page table
6. 重新執行指令

#### Performance of Demand Paging <font color="#f00">會考</font>

### Copy-on-Write
* Allows both parent and child processes to initially share the same pages in memory
* Modify pages will create a copy
#### Before Process 1 Modifies Page C
#### After Process 1 Modifies Page C

### Page Replacement
* Due to there is no Free Frame
* 用<font color="#346bff">Modify (dirty) bit</font>檢查要不要寫回Disk
* Find free frame
* If there is a free frame, use it
* If there is not free frame, find <font color="#346bff">victim frame</font>
* Restart instruction
#### Frame-allocate Algorithms <font color="#f00">會考</font>
* 決定每個process要分配幾個frame
* 決定哪些frame要被replace

#### Page and Frame Replacement Algorithms <font color="#f00">會考</font>
* Use Reference string to evalue algorithms
* Belady’s Anomaly:Page fault的次數沒有因為number of frame增加而變少 <font color="#f00">重要觀念</font>
* First-In-First-Out (FIFO) Algorithm
* 先進先出
* Optimal Algorithm (Best solution)
* 未來最久沒用到的會被replace
* 理想化的解，因為無法預知未來所以無法真的使用此演算法，僅用來評估其他演算法效能
* Least Recently Used (LRU) Algorithm
* 之前最久沒用到的會被replace
* Implement with stack <font color="#f00">會考</font>
* 由後往前看
* [LRU Approximation Algorithms](https://www.youtube.com/watch?v=voiL2-nQmlU&ab_channel=BBarters)
* Additional-Reference-Bits Algorithm
* 加入Reference-Bit，初始值為0，參考後會變成1
* Replace Reference-Bit為0的page
* Second-Chance Algorithm
* 把Reference bit為1的設成0
* Replace Reference-Bit為0的page
* Enhanced Second-Chance Algorithm
* 除了Reference-Bit之外還加入Modify bit
* (0,0)還沒被修改、使用，最佳的取代選擇
* (0,1)還沒被使用但是被修改過，在取代之前要寫回disk
* (1,0)還沒被修改，但有被使用過
* (1,1)被修改過、也被使用過，也需要寫回disk
* Counting Algorithm <font color="#f00">會考</font>
* Lease Frequently Used (LFU) Algorithm
* 取代count值最小的
* Most Frequently Used (MFU) Algorithm
* 取代count值最大的，將次數最少的page認為是剛被帶入不久、很快就需要用到的類型。
* Page-Buffering Algorithms
* When a page fault occurs, a victim frame is chosen as before.
* 在victim is written out之前可以先從pool裡面找一個free frame先拿來用，就不用等victim寫完
* 可以用來加速，不用等下面的步驟1做完

### Allocation of Frames
* Minimum:程式最少需要的frame數量
* Maximum:程式最多可以使用的frame大小
* Fixed allocation
* Equal allocation:For example, if there are 100 frames (after allocating frames for the OS) and 5 processes, give each process 20 frames
* Proportional allocation:Allocate according to the size of process
* Priority allocation
* Use a proportional allocation scheme using priorities rather than size
* Select for replacement from its frame or low priorty process frame
### Global vs. Local Replacement
#### Global replacement (More common)
* 從記憶體中所有的frames中選一個替換
* Execution time很浮動
* Troughput is better
#### Local replacement
* Process從自己的frames中選一個替換。
* 使用率可能比較低但比較平均

### Non-Uniform Memory Access
* 記憶體存取時間取決於記憶體相對於處理器的位置。在NUMA下，處理器存取它自己的本地記憶體的速度比非本地記憶體（記憶體位於另一個處理器，或者是處理器之間共享的記憶體）快一些
* Solved by Solaris by creating lgroups (for “locality groups”)

### Thrashing <font color="#f00">會考</font>
* 當沒有足夠的pages時，page-fault會非常高
* Process在swapping in跟out之間在忙碌的轉換著
* 導致CPU使用率降低 -> CPU以為是需要更多工作 -> 加入更多Process

### Locality model <font color="#f00">會考名詞解釋</font>
* Locality: A set of pages that are actively used together.
* Locality model: As a process executes, it moves from one locality to another. A program is generally composed of several different localities which may overlap.

### Working-Set
* 預估process在不同時間內所需要的frame數量，並提供足夠的frame防止thrashing
* working-set window：取樣值，例如每10000個instruction為一個範圍
* 太小會無法包含整個locality
* 太大就會重複很多locality
* 在∆等於無限大時就等於整個program
* 而將Ｄ代表process對frame的總需求量，如果Ｄ> m(可用量時)，就會發生thrashing
### Page fault frequency
* 一開始先建立一個「可接受」的page-fault frequency(PFF) rate，並使用logical replacement策略，然後就是察看最後的rate大小如何
* 如果actual rate很低，表示process有太多的frame，需要剃除一些走。
* 如果actual rate很高，就表示process需要更多的frame，因此分配更多的frame給process使用
### Working Sets and Page Fault Rates <font color="#f00">會考判斷Work set區間</font>

### Memory-mapped files(記憶體映射檔)
* Memory-mapped file會讓一段虛擬記憶體對應於一個檔案，將檔案I/O視為經常性記憶體，不同於open()等標準系統存取。藉由memory-mapped file相關程式，直接從virtual memory讀取檔案內容，加速I/O效能。
* 高速檔案存取(主要目的)：傳統讀取檔案需要system call和disk存取
* 將大檔案載入記憶體
* 可讓多個程式共享記憶體
### Shared Memory in Windows API
1. 產生一個file mapping
2. Producer用CreateFile()開啟被對應檔，歸HANDLE
3. 用CreateFileMapping()產生named shared-memory object
4. consumer以MapViewFile()在virtual address space建立mapped file的view
### Allocating Kernel Memory
#### Buddy System
* 是由physical-contiguous pages所組成的固定尺寸segment來分配記憶體到kernel中。
* Memory allocated using power-of-2 allocator
* 當記憶體大小大於需要的就會分裂成兩個chunk直到剛剛好為止
* Coalesce: 合併成比較大的記憶體
* 容易產生fragmentation，例如只需要33KB但必須分配64KB給它
#### Slab Allocator
* Slab是由一或多個physically contiguous page組成
* Cache由一或多個slab組成
* Cache會被objects填滿，objects是資料的實體
* Cache創建時會mark為free，如果被使用會mark為used
* 優點是不會有fragmentation，size都剛剛好大小
### Prepaging
* 為了減少page fault，先prepage部分或全部process會用到的pages
* s pages are prepaged and α of the pages is used (0 ≤ α ≤ 1) α為prepage的使用率
* If α near zero -> prepaging loses
### Other Issues – TLB Reach
* TLB Reach:可以從TLB存取的總量
* TLB Reach = (TLB Size) × (Page Size)
* 在理想中，每個process的working set可以被儲存在TLB中，但也等於說有很大的機率會產生page fault。
* 因此要增加page size跟提供multiple page size。

### Other Issues – Program Structure
* 要一直切換frame
* Program structure
* int\[128,128\] data;
* Each row is stored in one page
* Program 1

     for (j = 0; j <128; j++)
        for (i = 0; i < 128; i++)
            data[i,j] = 0;

→ 128 × 128 = 16,384 page faults

* Program 2

    for (i = 0; i < 128; i++)
        for (j = 0; j < 128; j++)
            data[i,j] = 0;

→ 128 page faults

### Other Issues – I/O Interlock
* 有時Page需要被lock住
* 在考慮I/O時，必須要locked從裝置複製檔案的page，以便通過page replacement algorithm

## Chapter 11 Mass-Storage Systems
### Overview of Mass Storage Structure
* Transfer rate: is rate at which data flow between drive and computer
* Positioning time (random-access time): 存取資料時，磁頭轉到要存取資料的區塊所花費的時間
* Head crash: 讀寫頭觸碰到磁盤

### Hard Disk Performance <font color="#f00">會考</font>
* Latency based on spindle speed $\dfrac{1}{(\dfrac{RPM}{60})}$ = $\dfrac{60}{RPM}$
* Average latency = $\dfrac{1}{2}$ latency
| Spindle [RPM] | Average latency [ms] |
| -------- | -------- |
| 4200 | 7.14 |
| 5400 | 5.56 |
| 7200 | 4.17 |
| 10000 | 3 |
| 15000 | 2 |
* Access Latency(Average access time) = averageseek time + average latency
* Average I/O time = average access time + (amount to transfer / transfer rate) + controller overhead
* Example: Suppose we want to transfer a 4KB block on a 7200 RPM disk with a 5ms average seek time, 1Gb/sec transfer rate, and a 0.1ms controller overhead. What is the Average I/O time for 4KB block?
5ms + $\dfrac{60}{7200}$ x $\dfrac{1}{2}$ + $\dfrac{4\times10^3\times8 }{10^9}$+ 0.1ms
= 5ms + 4.16ms + 0.032ms + 0.1ms
$\approx$ 9.3ms
### Solid-State Disks
* 優點
* 可靠性高
* 更快速
* 沒有seek time and rotational latency
* 缺點
* 比較貴
* 壽命比較短
* 容量比較小
### Network-Attached Storage
* 透過網路來存取資料

### Disk Scheduling
#### FCFS
* 先來的先做
#### SSTF(Shortest Seek Time First)
* 每次都找距離最短的做，但可能導致starvation
#### SCAN
* 先從一邊做到底，再做到另外一邊直到最後一個被做完
#### C-SCAN (C stand for cycle)
* 跟Scan概念差不多，但它是一個循環的結構
#### C-Look
* 跟Scan的差別是，不會做到底，只會做到最底的queue

### Disk Management
* Low-level formatting或稱physical formatting: 建立硬碟磁區（sector）使硬碟具備儲存能力的操作
* Partition: 磁碟分割，Ex: C、D槽
* Logical formatting(making a file system): 要使用硬碟保存文件，作業系統仍然需要在硬碟上記錄自己的資料結構。將硬碟分成一或多組柱面
* Boot lock initialize system:用boot block初始化系統，而bootstrap 是儲存在ROM中，開機時才可以啟動，boot block(是個作業系統)就需要bootstrap把他載下來。

### Swap space management
* Swap-space: 使用虛擬記憶體來擴充主記憶體，因為現代記憶體空間比較充足，比較少用了
* 4.3BSD在process 啟動時，分配swap space來儲存program文字和數據
* Kernel使用swap map來追蹤swap space的使用
* 僅當頁面被強制退出physical memory 時，Solaris 2才會分配swap space，而不是在首次創建virtual memory page時。

### RAID(Redundant Array of Independent Disks) Structure <font color="#f00">會考</font>
* Multiple disk drives provides reliability via redundancy
* Increases the mean time between failure (MTBF)，同時出錯的機率變小，可靠性增加
* Mean time to repair: the time it takes (on average) to replace a failed drive and to restore the data on it
* Mean time to data loss based on above factors
- If mirrored disks fail independently, consider disk with 100,000 MTBF and 10 hour mean time to repair
→ Mean time to data loss is $\dfrac{100,000^2}{(2\times 10)}$
= $500 \times 10^6$ hours, or 57,000 years!
* Disk striping: uses a group of disks as one storage unit

### RAID Levels
#### RAID level 0
* 只做striping

#### RAID level 1
* 只做mirror

#### RAID level 4
* 而且必須使用額外的一部同位磁碟機 (parity disk) 來儲存同位位元資訊 (parity information

#### RAID level 5
* 將parity information分散在各個disk，還有另外一個parity disk

#### RAID level 6

#### RAID levels 0 + 1 and 1 + 0 <font color="#f00">可能考怎麼畫</font>
* RAID 0 + 1:先striping再mirror
* RAID 1 + 0:先mirror再striping
* RAID 1 + 0會比RAID 0 + 1還可靠
* 通常不會有人使用RAID 0+1，它的缺點只要其中一台硬碟機故障，整組 RAID 0+1 便無法讀取，相當危險，所以依然選擇 RAID 1+0 的人仍占多數。

### Other Features
* Snapshot: 可將任一時間點的系統狀態與資料記錄下來作為將來還原的備份
* Replication: 自動複製一份資料到其他地方
* Hot spare disk: 當作備用的硬碟，平常不會被使用，但當有故障的硬碟的時候會被使用