# 半夜讀資料的問題

[TOC]

## Page fault
:::danger

1. Q : MMU 究竟是甚麼東西 ? 在作業系統恐龍書當中提到她說就是計算記憶體位置的硬體，但是在計組當中說MMU是所有管理記憶體且包含TLB都叫做MMU

A :

2. Q : [為何和以前在考試中學到的Page fault 為何看起來和現在這一個完全不是同一個東西](https://ithelp.ithome.com.tw/articles/10228975)
頂多看起來有點像是 Major + Invalid 的綜合體

A :

3.
> 需要標注「恐龍書」的分類，注意：「恐龍書」不能代表作業系統工程人員和研究員的觀點，只能當歷年論文的「懶人包」
> :notes: jserv
:::

### Minor
有兩種可能性

第一種可能性 : 是一塊實體記憶體被兩個或多個程式共享，作業系統已經為其中的一個裝載並註冊了相應的頁，但是沒有為另一個程式註冊。

第二種可能性 :　是該頁已被從CPU的工作集中移除，但是尚未被交換到磁碟上。

前導知識 : [OpenVMS](https://zh.wikipedia.org/wiki/OpenVMS)

e.g. : OpenVMS(Open Virtual Memory System)這樣的使用次級頁快取的系統，就有可能會在工作集過大的情況下，將某頁從工作集中去除，但是不寫入硬碟也不擦除

### Major
與Minor錯誤相反，Major錯誤是指相關的Page在Page fault發生時未被載入進記憶體的情況。
有些作業系統會將程式的一部分延遲到需要使用的時候再載入入記憶體執行，以此來提升效能。這一特性也是通過擷取硬性分頁錯誤達到的。

:::danger
1. Q : 如何做到在 Major 還提升效能的，一般來說產生Page fault 不是都要盡量避免嗎? (這邊的想法比較多的是恐龍的想法)
A :

:::

### Invalid
當程式存取的虛擬位址是不存在於虛擬位址空間內的時候，則發生Invalid錯誤。

考試版的 [Page fault](https://mropengate.blogspot.com/2015/01/operating-system-ch9-virtual-memory.html)

:::info
Thrashing :
1. 若 Process 分配到的 frame 不足，則會經常發生 page fault，此時必須執行 page replacement。
2. 若採用 global replacement policy，則此 process 會替換其它 process 的 page 以空出 frame，造成其它 process 也會發生 page fault，而這些 process 也會去搶其它 process 的 frame，造成所有 process 皆在處理 page fault。
3. 所有 process 皆忙於 swap in/out，造成 CPU idle。(CPU idle 時 OS 會企圖引進更多的 process 進入系統讓 Thrashing 現象更嚴重。)


:::

## Why is there a "V" in SIGSEGV Segmentation Fault ?
Looking deeper David found that PDP11 trap vector used wording "segmentation violation". This shows up in Research V4 Edition in the UNIX history repo, but it doesn't mean it was introduced in V4 - it's just because V4 is the first version with code still available.

1. 錯誤的訪問類型引起

#include <stdlib.h>
int main(){
     char *c = "hello world";
     c[1] = 'H';
}

2. 訪問了不屬於進程地址空間的內存

#include <stdio.h>
#include <stdlib.h>
int main(){
    int* p = (int*)0xC0000fff;
     *p = 10;
}　

或是 受到系統保護的內存地址寫數據，最常見就是給一個指針以0地址

int  i=0;
scanf ("%d", i);  /* should have used &i */
printf ("%d\n", i);
return 0;　

3. 訪問了不存在的內存

int p = null;
p = 1;

4. 內存越界，數組越界，變量類型不一致等

#include <stdio.h>
int  main(){
    char test[1];
    printf("%c", test[10]);
    return 0;
}　

5. 試圖把一個整數按照字串的方式輸出

   int  main(){
        int b = 10;
        printf("%s\n", b);
        return 0;
    }

自然也是存取了不該存取的主記憶體——segmentation fault。

:::danger
用字：
access 是「存取」，不是「訪問」
main memory 是「主記憶體」，不是「內 X」
string 是「字串」，不是「字符 X」

傳統中文用字追求精準達意，非文化斷層的簡體中文可比擬
:notes: jserv
:::

Q : 為何有時候我自己在測試的時候不會出現 ?
A :

## Pigeon hole principl 應用在資安上
[參考資料](https://coincentral.com/hashing-basics-history/#)

## Skip list
### 介紹
Skip List 是個概率性數據結構 ，多層次的 linked list 實現的。
### 想法
一開始時，演算法在最稀疏的層次進行搜尋，直至需要尋找的元素在該層兩個相鄰的元素中間。這時，演算法將跳轉到下一個層次，重複剛才的搜尋，直到找到需要尋找的元素為止。

:::danger
Q : 隨機 和 概率 都是一個超級大的議題為甚麼這一個資料結構可以直接這樣假設 ? (工程 和 科學的差別 ? )實際中它通常工作良好
:::
### 實作細節

## Bloom filter (布隆過濾器)
### 用途
布隆過濾器可以用於搜尋一個元素是否在一個集合中。

### 原理
當一個元素被加入集合時，通過K個雜湊函式將這個元素對映成一個位陣列中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

### 優劣比較
#### 優勢
1. 空間效率 $O(1)$
2. 查詢時間 $O(1)$
#### 劣勢
1. 有一定的誤辨識率
2. 刪除困難

### 強大能力，帶來的風險
- 如果 Bloom Filter 回傳沒有（negative）：代表資料 一定沒有 在 Bloom Filter 中
- 如果 Bloom Filter 回傳有（positive）：代表資料 可能有 在 Bloom Filter 中，並不是一定有在 Bloom Filter 中

### 實際應用
使用 Bloom Filter 情境，是要可以忍受 false positive 的發生，且發生之後不會造成太大的影響

:::danger

第二個缺點就是無法刪除已經加入的資料，關於這點可以參考 bloom filter 的各種變形版（Counting Filter / Cuckoo Filter…）。

:::
1. 搶票流量控制
2. Yahoo Email 確認收件者在不在連絡清單
3. Tinder Suggestion

### [實作](https://medium.com/@Kadai/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%A4%A7%E4%BE%BF%E7%95%B6-bloom-filter-58b0320a346d)

### 補充
Bloom Filter 改良版 Counting Filter
:::danger
Bloom Filter 有著不能刪除新資料的限制，因為你把原先為 1 的改成 0的時候，你不知道原先有多少個節點是對應該該位置．後來在資料欄位上新增了計數器 (counting) 就能夠解決不能刪除節點的問題．

透過新增計數單位可以記錄總共有幾個點是透過 Hashing Function Mapping 到該節點上面．到時候要刪除的時候也就可以確認是否所有對應到該節點的個數都有確切地被刪除．

運作方式為：

新增一個節點進( CBF: Counting Bloom Filter ) 就將該 Hashing 過的位置裡面數值加一
要刪除節點的時候就會把該數值減一．
Counting Bloom Filter 的缺點
為了要解決不能刪除節點而加入的計數欄位，就會變成讓資料量反而又變大了．
:::

## Worst-case execution time (WCET)

### 作用
用在可靠的實時系統之中(e.g. : 汽車系統)

### 系統化分析方法

1. WCET (最壞執行時間分析)
WCET分析考慮一個獨立任務的執行時間，此分析完全忽略了與任務無關的任何其他的活動，認為任務永遠不會阻塞。

https://en.wikipedia.org/wiki/Worst-case_execution_time#What_it_is_used_for

###### tags: `進階電腦實作補充資料`