# OS HW1: Benchmark Your Computer Black Box
- **學號: F74076124**
- **姓名: 向景亘**
- **系級: 資訊 111**
## 開發環境
- OS: Ubuntu 20.04
- CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
- CPU cores: 4
- Memory: 16 GB
- Programming Language: C11, gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
## 編譯與測試說明
本作業有兩個部分， `generator` 與 `sort`。可以使用 `Makefile` 來產生程式檔
在本次作業中，我使用 `Makefile` 來編寫自動編譯與測試的流程，並支援以下的功能
### `make`: 編譯所有程式
使用的方法如下：
```shell
$ make
gcc -c sort.c -std=c11 -g -pthread
gcc -o sort sort.o -std=c11 -g -pthread
gcc -c generator.c -std=c11 -g -pthread
gcc -o generator generator.o -std=c11 -g -pthread
```
### `test`: 自動化測試流程
因為在測試程式的時候會使用 `chunk` 這個目錄來暫時存放相關檔案，所以為了自動化整個測試流程，我們可以使用 `Makefile` 的指令來進行測試
```shell
$ make test
./sort -i input.txt -o output.txt
```
### `format`: 根據 `.clang-format` 的設定進行 Coding Style 的更改
我在這個作業中加入以 `clang-formater` 來維持 coding style 的一致，可以呼叫以下的指令將所有的 `*.c` 與 `*.h` 檔修改為 `.clang-format` 中所指定的格式
```shell
$ make format
```
:::warning
:warning: 需要透過 `sudo apt install clang-format` 來安裝 `clang-format` 這個套件
:::
### `clean`: 清除編譯時產生的 `*.o` 檔與執行檔
為了強制編譯或避免舊的輸出檔造成的問題，可以透過呼叫指令刪除所有相關資料
```shell
$ make clean
```
## 程式使用說明
### `generator`
`generator` 負責產生測資，並支援 commandline arguments 的輸入
可以使用的指令如下：
- `-n` : 指定要生成的檔案大小，後面需要接上指定的檔案大小，大小單位為 1 G
- `-o` : 指定輸出檔案的檔名，預設輸出到 `input.txt`
執行的範例如下
```shell
$ ./generator -n 1 -o output.txt
```
表示我們指定要產生一個含有 1 GB 容量大小的 `int` 數值檔案 (因為 一個 `int` 的大小是 4 byte，所以若 `-n` 給定 `1` 的話，就會產生 $2^{28}$ 個 `int` 數值)，並輸出到檔名為 `output.txt` 的檔案中。
而使用 `generator` 產生出來的格式如下，且數值介於 $-2^{31} \sim 2^{31} - 1$ 之間
```
1016805454
1475107312
-773922153
-1631946082
-2117758124
1441150487
...
```
### `sort`
用來將給定的資料執行 external sort 後輸出到指定的檔案名稱中。
`sort` 支援以下的 commandline arguments:
- `-i`: 指定輸入檔案的名稱，預設為 `input.txt`
- `-o`: 指定輸出檔案的名稱，預設為 `output.txt`
使用的範例如下：
```shell
$ ./sort -i input.txt -o output.txt
```
:::info
:bulb: 為了簡化測試流程，在 `Makefile` 中有針對測試程式設計的自動化流程，可以使用 `make test` 來呼叫
:::
## 程式開發
### generator
因為這個程式的目的就是要產生特定數量的測試資料，所以在邏輯上相當簡單，就是產生多個 `int` 的資料，並寫入到給定的檔名中
但是因為我們的測試資料的數值範圍需要介於 $-2^{31} \sim 2^{31}$ 之間，所以我使用的方式是呼叫 Linux 中內建的 random device 來產生對應的資料
這個部分的實作在 `generator.c:randombytes` 的部分，主要的操作流程就是依照呼叫函式時給定的 byte 數向 `dev/urandom` 讀取相同大小的數值，並寫入對應的變數中。
因為一個 `int` 的大小是 4 byte，所以呼叫函式的時候就只需要取得 4 byte 的隨機數即可產生一個介於區間內的數值資料，呼叫函式的範例如下：
```cpp
randombytes((uint8_t *) &a, sizeof(int32_t));
```
接著我嘗試實作多執行緒的版本
為了能讓各個 thread 各自產生隨機數值並寫入同一個檔案中，我設計一個函式 `worker` 來定義每個 thread 應該要進行的行為
```cpp
void *worker(void *arg)
{
int32_t a;
while (1) {
/* output random number into the file */
randombytes((uint8_t *) &a, sizeof(int32_t));
/* protect the file from output interleaving */
pthread_mutex_lock(&mutex);
fprintf(fout, "%d\n", a);
pthread_mutex_unlock(&mutex);
size_t m = atomic_fetch_add(&cnt, 1);
printf("generating test data... (%lu / %lu)\r", m, num);
if (m >= num)
return NULL;
}
}
```
在寫入檔案的部分因為每個 thread 寫入的檔案都是同一個，為了避免測試資料被交錯輸出，所以我使用 `mutex_lock` 來保護 `fprintf` 的部分，確保在同一時間內只會有一個 thread 參與檔案的輸出。
接著為了記錄總共輸出了多少筆資料，我使用 C11 中定義的 `<stdatomic.h>` 來定義一個 Atomic 的變數 `cnt` 來記錄，並透過 `atomic_fetch_add` 來做遞增並檢查是否已產生足夠的測資，如果測資數量 `m` 大於要產生的數量 `num` 時就結束 thread 的操作。
並呼叫 `fclose` 強制將 buffer 中的資料寫入檔案。
### sort
在 `sort` 的部分因為考慮到我們要處理的檔案大小可能遠遠大於我們的 memory 的大小，所以不能一次將所有資料讀到記憶體中，並進行排序。因此，我將 `sort` 的操作拆成兩個階段來進行
#### split
在這個階段我們專注部分是將我們的檔案拆成若干部分，利用一個我們的 memory 可以負擔的大小來存取輸入的部分資料，透過 `<stdlib>` 的 `qsort` 進行排序，並存到 `./chunk/` 目錄底下保存，以便在下一個階段將這些檔案拿出來做合併
#### merge
進入到 merge 的部分就需要考慮比較多的議題。因為在上個階段分割檔案的過程中，我們可以知道我們總共切割出多少的檔案，假設總共有 `chunk_cnt` 個分割檔案，我們就需要先 `malloc` 一個總共有 `chunk_cnt` 個元素的陣列 `chunks`，讓我們在後續正式進行檔案合併的過程中可以追蹤哪些檔案還沒有被合併。
接著因為我們利用 `chunks` 來記錄我們目前還剩下多少資料需要合併，接著我採取一次合併 `n` 個檔案的策略。因為在所有的檔案中，我們不確定最小值會發生在哪個檔案中，所以我們需要透過逐一將檔案合併的操作，才能確保合併後的檔案內部的資料還是依照遞增的排序方式存在。
因此我使用 `find_index` 這個函式取得在目前要合併的檔案中具有最小值的檔案索引數值，並將該檔案寫到合併後的檔案中，最後將 merge 過後的檔案以系統呼叫 `remove` 刪除。
重複這樣的過程直到合併到剩下一個檔案為止，而這個檔案在我的程式中的命名規則應該會產生一個叫做 `data0` 的檔案，最後我透過 `rename` 呼叫修改並移動該檔案到指定的位置，完成 merge 的操作。
### 時間測量
在時間測量的部分我使用的是定義在 `<time.h>` 中的 `clock()` 函式來進行，並將兩個不同的階段拆開分別測量其執行的時間。
## 效能分析
在效能分析的部分我分成兩個部分來進行觀察，分別是記憶體用量與執行時間
### 記憶體用量
這個部分我使用的是 Valgrind 來分析記憶體的使用情形，並檢查是否有 memory leak 的情況產生
可看到在這張圖中
### perf
### 執行時間
#### 修改分割大小與合併個數
我首先將輸入檔案以每 512 個 `int` 的個數就進行分割與 2-way merge 的方式來做對照組的測量結果
測量結果如下
```shell
$ make test
./sort -i input.txt -o output.txt
split time: 79.858818
merge time: 946.410207
```
接著我依序修改 `CHUNK_SIZE` (每幾筆資料進行分割) 與 `MERGE_NUM` (N-way merge) 來觀察執行時間的差異
---
以下呈現的是將每 512 個 `int` 分割成單一檔案，改以每 $2^{19}$ 個才進行排序並儲存成單一檔案的執行時間
```
$ make test
./sort -i input.txt -o output.txt
split time: 85.215827
merge time: 442.076259
```
可以看到因為我們將 `CHUNK_SIZE` 調高，所以在 `split` 階段執行完成後分割出來的檔案甚至不到 1000 個，因此在合併的時候就可以大幅提高效率。
而在分割的執行時間上不會因為單次分割大小的改變而有太大的差異。
---
若我們將 `MERGE_NUM` 從 2 調高到 5 時候，表示我們每次合併 5 個檔案，因此執行時間可以再得到一定程度的優化
```
$ make test
./sort -i input.txt -o output.txt
split time: 83.574670
merge time: 213.526187
```
---
如果我們將每次 merge 的數量再調高
```
$ make test
./sort -i input.txt -o output.txt
split time: 84.975789
merge time: 247.652912
```
因為我在決定哪筆資料要先被寫入的部分採取的是 for 迴圈遍尋的手法，所以在 merge ways 增加的情況下並不會因此提升效率，而是受制於演算法本身的極限。
從上述的幾個實驗中，我們可以看到，`CHUNK_SIZE` 的改變，影響到分割檔案的數量，將直接影響到後續合併檔案的效率，因為越多的檔案，需要更加頻繁的使用 Disk I/O 來讀取與操作存在硬碟中的檔案，從而拖累執行的速度。
而在 n-way merge 的考量上，如果一次可以 merge 更多的檔案，相當於在 CPU 執行時的 pipeline 的操作，透過事先將檔案讀入，可以讓後續我們在將各個資料寫入到合併後的檔案時，因為省去了 Disk I/O 的時間，所以在相當程度上縮短執行的時間。
#### 設計 buffer 暫存部分輸出結果
因為如果一次只輸出一筆合併過後的資料效率並不會太好，所以我嘗試使用輸出 buffer 的方式保存部分的輸出結果，等到累積到一個數量再一起到檔案中，以觀察其與原本的輸出方式在執行時間上有何差異
```shell
$ sudo fdisk -l
Disk /dev/sdb: 931.53 GiB, 1000204886016 bytes, 1953525168 sectors
Disk model: ST1000LM035-1RK1
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: gpt
Disk identifier: 6A1A8B30-9A54-4D67-8377-3267FA8EC97F
Device Start End Sectors Size Type
/dev/sdb1 2048 1757814547 1757812500 838.2G Microsoft basic data
/dev/sdb2 1757814784 1758314495 499712 244M EFI System
/dev/sdb3 1758314496 1953523480 195208985 93.1G Linux filesystem
```
從上方的資訊可以知道我所使用的這顆硬碟在讀寫的時候是以 4096 byte 為單位在進行的，所以我在 `sort.c` 中加入一個 buffer 來儲存我們合併好的部分檔案。
因為資料數值的最大的範圍到 $2^{31}$ 次方，因此一個數字若以字串的形式來表示最高會有 $log_2{\ 2^{31}}$ 也就是大概 10 個字元來表示，所以考慮換行字元以及負號的影響，我設計讓他在儲存 380 個數字的輸出結果後，就將 buffer 中輸出到硬碟之中，希望可以利用這樣的方式來優化整個執行的效率
```shell
$ make test
./sort -i input.txt -o output.txt
split time: 86.883784
merge time: 240.967719
```
而就如同上面這個執行時間測量的結果所述，`split` 階段因為沒有使用 buffer 的技巧，所以執行的時間沒有太大的變化，但在使用 buffer 進行修改的 merge 階段也沒有太大的改善，與未使用 buffer 版本的差異其實大約只有 5 秒左右的差距。
若以 `perf` 的角度來觀察改以 buffer 來實作的版本可以發現我們為了減少的 `fprintf` 的使用實際則造成了 `sprintf` 的使用次數增加，所以在執行效能上的表現比較無法被凸顯出來。
而透過編譯器優化參數 `-O2` 進行優化的版本的執行結果如下
```
$ make test
./sort -i input.txt -o output.txt
split time: 70.666644
merge time: 200.622693
```
可以看到即使在 buffer 的版本中加入編譯器參數來優化，還是無法達到系統 buffer 自己判斷寫入時機的執行效果好。
#### 加入優化參數
考慮到我們寫的程式有可能因為編譯器參數的不同而有不同的效能表現，所以我嘗試使用編譯器優化參數 `-O2` 來編譯我們的程式，並進行執行時間的測量。
```
$ make test
./sort -i input.txt -o output.txt
split time: 70.563255
merge time: 183.378275
```
可以看到編譯器優化的版本在執行時間上較未優化少 60 秒左右的時間。
### 同時執行多個程式
因為我的程式在執行的過程中會修改與增加自身目錄中的 `chunk` 這個目錄底下的資料，所以為了避免每個 `sort` 在運行的過程中互相干擾，我將 `Makefile`, `sort` 這兩個檔案分別複製 8 份，存放在 `1` ~ `8` 資料夾中，並利用 shell script 將所有的執行檔打開並執行
我利用 `htop` 來觀察各個 `sort` 與 CPU 核心佔用率之間的關係
並設計以下幾種實驗的方式來進行
1. **單一程式執行的情形**
在只有單一一個程式在運行的情況下，因為系統在服務電腦週邊的各項服務之餘，還有 idle 的核心可以使用，所以系統排程器就會將 `sort` 這種需要大量運算與 I/O 的程式分配在其中一個 CPU 核心來執行，但因為有 data migration 的情況存在，所以 `sort` 並不會被固定在特定 CPU 核心上進行執行，而是執行到一半會被分配到其他的 CPU 核心上進行。
2. **多個程式同時執行 (但不等於或大於系統核心數量)**
與第一個實驗的狀況類似，因為在這個時候 CPU 的核心數還足以負荷這樣數量的程式，且其他的周邊服務在執行上不會花 CPU 太多的時間與運算量，所以這時排程器就會將這些需要大量運算的程式，也就是 `sort` 分配到 idle 的 CPU 核心上進行運算。
且因為排程以及 content switch 的影響，所以這些程式不會固定在特定幾個 CPU 的核心上進行，而是會在不同的核心間跳動。
3. **多個程式同時執行 (等於系統核心數量)**
因為在這個情況下，若按照前兩個實驗的情況的話，所有系統的核心應該都要是被佔用的情況，但是如果是這樣的情況，那我們系統的其他服務，例如 GUI 的介面就沒有辦法被執行到，而造成當機或是無法回應的情況。
因此系統排程器為了避免這樣的問題，他會盡量減少所有核心佔用率都是 100 % 的情況產生，他會將 CPU 預算與 Disk I/O 的執行切得更開，用較少的時間執行大量 CPU 的運算，其他在 CPU 無法進行大量運算的時候執行 Disk I/O 並處理其他系統服務，避免系統周邊服務停擺的情況產生。
CPU 佔有率較低的情況，這時候 Disk I/O 會較為頻繁
CPU 佔有率較高的情況，這時候會執行需要大量 CPU 運算的函式
###### tags: `os`
Sign in with Wallet
Connect another wallet