---
# System prepended metadata

title: 2020_OS_Fall_HW1

---

# 2020_OS_Fall_HW1

學號： F74076027
姓名： 林政傑
系級： 資訊 111

[TOC]

## 開發環境：

- OS: Ubuntu 20.04.1 (Oracle VM Virtual Machine)
- CPU: Intel® Core™ i7-10750H CPU @ 2.60GHz × 4
- Ｍemory: 4GB
- Programming Language: g++ (Ubuntu 9.3.0-10ubuntu2) 9.3.0

## 程式執行時間

- 生成 8GiB 檔案所消耗的時間:

  |實驗次數|秒數|
  |------|----|
  |1     |123 |
  |2     |119 |
  |3     |122 |
  |4     |105 |
  |5     |105 |
  |平均   |115 |
- 排序 8 GiB 檔案所消耗的時間:

  * 2-way merge sort

    |實驗次數|8GiB|16GiB |24GiB|
    |------|----|------|------|
    |1     |515 |1592  |2155  |
    |2     |505 |1523  |2183  |
    |3     |505 |1547  |2150  |
    |4     |517 |1360  |2177  |
    |5     |498 |1323  |2170  |
    |平均   |508 |1469  |2167  |
  
  * k-way merge sort
    
    |實驗次數|8GiB|16GiB |24GiB|
    |------|----|------|-----|
    |1     |572 |1368  |1814 |
    |2     |584 |1360  |1845 |
    |3     |578 |1322  |1887 |
    |4     |579 |1349  |1913 |
    |5     |595 |1229  |1985 |
    |平均   |582 |1326  |1889 |

## 程式開發與使用說明

### 使用說明: 專案目錄

```bash
$ tree
.
├── Makefile
└── source_code
    ├── benchmark.cpp
    ├── gen_input.h
    ├── help.h
    └── sort.h

1 directory, 5 files
```

### 使用說明: 編譯

在專案目錄輸入 `make` 即可編譯:

```bash
$ make
g++ source_code/prompt.cpp -o prompt
g++ source_code/gen_input.cpp -o gen
g++ source_code/sort.cpp -o sort
g++ source_code/ksort.cpp -o ksort
```

### 使用說明: 執行

編譯完成之後，會產生三個執行檔: `prompt` 、 `gen` 、 `sort`。
- 在專案目錄輸入 `./gen` 可以在專案目錄生成一個 8GiB 的 input.txt:
  ```bash
  $ ./gen
  # generate a 8 GiB input file
  ```
- 若 input.txt 在專案錄下，在專案目錄輸入 `./sort` 即可執行 **2-way merge sort** 

  ```bash
  $ ./sort
  # sort input.txt
  ```
  請盡量把 input.txt 放在專案目錄，並且在專案目錄執行`sort` ，如果要在其他目錄執行 `sort`，需要指定 input.txt 的位置:
  ```bash
  somepath$ path_to/sort path_to/input.txt
  #example: benchmark1/sort benchmark1/input.txt
  ```
  除了指定 input.txt 外，output.txt 的位置也可以指定:
  ```bash
  somepath$ path_to/sort path_to/input.txt path_to/output.txt
  #example: benchmark2/sort benchmark2/input.txt benchmark2/output.txt
  ```
  在 sort 的過程中，當前目錄會產生 tmp 目錄，待 `sort` 結束會將其刪除

- 若 input.txt 在專案錄下，在專案目錄輸入 `./ksort` 即可執行 **k-way merge sort**
  ```bash
  $ ./ksort
  # sort input.txt
  ```
  請盡量把 input.txt 放在專案目錄，並且在專案目錄執行 `ksort` ，如果要在其他目錄執行 `ksort`，需要指定 input.txt 的位置:
  ```bash
  somepath$ path_to/ksort path_to/input.txt
  #example: benchmark1/ksort benchmark1/input.txt
  ```
  除了指定 input.txt 外，output.txt 的位置也可以指定:
  ```bash
  somepath$ path_to/ksort path_to/input.txt path_to/output.txt
  #example: benchmark2/ksort benchmark2/input.txt benchmark2/output.txt
  ```
  在 sort 的過程中，當前目錄會產生 tmp 目錄，待 `ksort` 結束會將其刪除
- 使用 `./prompt` 整合功能:
  ```bash
  $ ./prompt
  enter "h" to get help
  enter "q" or "ctrl + c" to quit
  > h
  # show every command's usage
  > gen
  # generate a 8 GiB input file
  > sort
  # sort input.txt
  > q
  # quit prompt
  ```

**如果要同時執行多個排序，必須多次編譯，把每個執行檔 sort.h 中的 tmp 目錄換成不一樣的名字，否則排序時會互相衝突**

### 程式開發: 產生 input 的方法

使用 `srand(time(NULL))` 初始化亂數表，接下來先用變數 `num` 儲存 `rand()` 的回傳值，然而 ubuntu20 的 `RAND_MAX` 為 2147483647 ，為了產生出負值，若下一個亂數是奇數，則將 `num` 乘上 -1 並且減 1。

每次產生出數字，會去計算這些數字化為字串之後的長度，並根據所有字串的長度來確認 input.txt 的大小，若剛好超過 8 GiB (預設) ，則結束生成亂數。

### 程式開發: 2-way merge sort

第一個排序演算法使用 2-way merge sort ，流程如下圖:
![](https://slideplayer.com/slide/5033624/16/images/5/Two-Way+External+Merge+Sort.jpg)
*圖片來源 https://slideplayer.com/slide/5033624/*

在 `sort.h` 裡，`two_way_merge_sort()` 會實作此排序，流程如下:

1. 在 `sort.h` 中定義變數 `chunk_size` ，代表 PASS 0 時單次抓取的數字數量，預設為 200000000 個，換算為 `int` 的大小 (4 byte)，約為 763 MiB 。將這些數字抓進記憶體後，使用 c++ 內建的 `sort()` 排序，並且儲存成拆分過後的 page (如上圖 PASS 0 的橘色方框)。
2. 在接下來的 PASS ，每次都讀取前一個 PASS 產生的兩個 page，從 page[n] 和 page[n+1] 依序抓取最小的數字來比較。如果 page[n] 的數字較小，就將該數字寫入新的 page ，然後再從 page[n] 抓取下個數字；如果 page[n + 1] 的數字較小，就將該數字寫入新的 page ，然後再從 page[n + 1] 抓取下個數字。
3. 假設待排序的數字為 $N$ 個，經過 $log_2 \dfrac{N}{chunk\_size} + 1$ 個 PASS 即完成排序。每個數字在每個 PASS 中需要一次的讀取和一次寫入，總共花費 $2N(log_2 \dfrac{N}{chunk\_size} + 1)$ 次 I/O。

### 程式開發: k-way merge sort

```graphviz
digraph g {
    node [shape=record]
    in[label="input.txt" fixedsize=true width=4.8]
    in->page1
    in->page2
    in->page3
    in->x
    in->pageK[label="PASS 0"]
    minq[shape=plaintext label="min-priority queue"]
    q[label="<front> 1 | 2 | 3 | ... | K"]
    page1->q
    page2->q
    page3->q
    x [label = "..."]
    x->q
    pageK->q[label="PASS 1"]
    {rank=same q minq}
    out[label="output.txt" fixedsize=true width = 3.4]
    q:front->out[label="     pop-front" fontcolor="blue"]
}
```

在 `sort.h` 裡，`k_way_merge_sort()` 會實作此排序，流程如下:

1. 在 `sort.h` 中定義變數 `chunk_size` ，代表 PASS 0 時單次抓取的數字數量，預設為 200000000 個，換算為 `int` 的大小 (4 byte)，約為 763 MiB 。將這些數字抓進記憶體後，使用 c++ 內建的 `sort()` 排序，並且儲存成拆分過後的 page。
2. 接下來，從每個 page 中抓出最小的數字存入 min-priority queue，接下來重複執行 pop-front ，將 front 元素寫入 output.txt 中，然後從原本 front 的數字的 page 再讀取最小數字放入 min-priority queue 。在實作中，我是以 STL list 來當作 min-priority queue ，每當有新元素插入時，會實施 insertion sort 來找出該元素正確的位置。
3. 假設待排序的數字為 $N$ 個，經過 2 個 PASS 即完成排序，每個數字在每個 PASS 中需要一次的讀取和一次寫入，總共花費 $4N$ 次 I/O 。然而更新 min-priority 消耗的時間有可能比 I/O 還要多，所以有些情況 k-way merge sort 效能不如 2-way merge sort，下面的實驗會提到。
## 效能分析報告

### 效能分析方法

- 使用 c++ 內建的 `clock()` 記錄程式執行時間，在執行生成 input.txt 以及 sort 前後測量時間並將其相減。

- 使用 `top` 指令分析 cpu 及記憶體用量，將檔案輸出至文字檔案如下:

  `$ top -1 -i -b > perf.txt`

  將 `top` 開啟後，開始執行 `sort` 或 `ksort` ，待排序結束，終止 `top` 指令，我們可以得到以下格式的文檔:

  ```
  $ cat perf.txt
  
  . . .

  top - 01:29:12 up 10:23,  1 user,  load average: 0.35, 0.15, 0.34
  Tasks: 216 total,   3 running, 213 sleeping,   0 stopped,   0 zombie
  %Cpu0  : 88.9 us,  6.1 sy,  0.0 ni,  5.1 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
  %Cpu1  :  1.0 us,  0.0 sy,  0.0 ni, 99.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
  %Cpu2  :  0.3 us,  0.0 sy,  0.0 ni, 99.3 id,  0.3 wa,  0.0 hi,  0.0 si,  0.0 st
  %Cpu3  :  0.7 us,  0.3 sy,  0.0 ni, 98.3 id,  0.3 wa,  0.0 hi,  0.3 si,  0.0 st
  MiB Mem :   3935.8 total,    543.0 free,   1319.6 used,   2073.2 buff/cache
  MiB Swap:   2048.0 total,   1995.0 free,     53.0 used.   2315.8 avail Mem 
  
      PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
    17235 lin       20   0    5884   1672   1520 R  94.3   0.0   0:02.83 gen
     1245 lin       20   0 5066132 395596  86624 S   1.7   9.8  12:28.80 gnome-shell
    17024 root      20   0       0      0      0 R   0.7   0.0   0:00.04 kworker/u8:1-events_power_efficient
    17137 lin       20   0 1127212  68036  45948 S   0.7   1.7   0:01.38 nautilus
      950 lin       20   0  901528  80688  42620 S   0.3   2.0  18:23.59 Xorg
  . . .
  ```

   文檔中，我所關注的是 4 個核心 `%Cpu0` 、 `%Cpu1` 、 `%Cpu2` 、 `%Cpu3` 在城市執行間的使用率，以及 `gen` 、 `sort` 程序的 `%CPU` 、 `%MEM` 占用率。為了快速抽取這些資訊，我寫了一個 python 腳本去讀取檔案，並且用 pandas 的 dataframe 儲存資訊，萃取後的資料如下:

  ```
         TIME    CPU   Mem  CPU0  CPU1  CPU2  CPU3  Total CPU Usage  \
  0    0:02.00   66.7   2.6   2.4   6.7   2.7  62.5        96.102429   
  1    0:05.00  100.0   6.3   3.1   9.7   3.4  92.3       134.027212   
  ..       ...    ...   ...   ...   ...   ...   ...              ...   
  175  8:40.76   98.3   0.1  56.0   0.0   6.0   0.0        81.091417   
  176  8:43.53   92.0   0.1  52.8   0.0   5.7   0.0        77.599040   

       Total Mem Usage  
  0          21.802429  
  1          25.527212  
  ..               ...  
  175        19.091417  
  176        19.099040  
  [177 rows x 9 columns]
  ```



:::spoiler **產生以上 dataframe 的 python 原始碼**
```python=
import pandas as pd

def getdf(filepath, target):
    file = open(filepath, 'r')
    cpu0 = []
    cpu1 = []
    cpu2 = []
    cpu3 = []
    totalcpu = []
    time = []
    cpu = []
    mem = []
    totalmem = []
    tmp = [0,0,0,0,0]
    i = -1
    while True:
        i = i + 1
        line = file.readline()
        if not line:
            break
        chunks = line.split(' ')
        chunks = list(filter(None, chunks))
        if chunks[-1] == 'st\n':
            if chunks[2] == 'us,':
                tmp[int(chunks[0][4])] = 100.0
            else:
                tmp[int(chunks[0][4])] = float(chunks[2])
            continue
        if chunks[0] == 'MiB' and chunks[1] == 'Mem':
            tmp[4] = float(chunks[7]) * 100 / float(chunks[3])
            continue
        if chunks[-1] == target:
            cpu.append(float(chunks[8]) / 4)
            mem.append(float(chunks[9]))
            time.append(chunks[10])
            cpu0.append(tmp[0])
            cpu1.append(tmp[1])
            cpu2.append(tmp[2])
            cpu3.append(tmp[3])
            totalcpu.append(sum(tmp) / 4)
            totalmem.append(tmp[4])
    data = {'TIME':time, 'CPU':cpu, 'Mem':mem, 'CPU0':cpu0, 'CPU1':cpu1, 'CPU2':cpu2,
            'CPU3':cpu3, 'Total CPU Usage': totalcpu, 'Total Mem Usage': totalmem}
    return pd.DataFrame(data)    
sort = getdf('perf.txt', 'sort\n')
print(sort)
```
:::

彙整出這些資訊之後，我使用 plotly 將資源占用率的圖畫出來，如以下 3 個範例:

- 第一張圖是總體 CPU 使用率， %Total CPU Usage (藍色) 為整個系統占用的 CPU 百分比，%CPU (紅色) 為 `sort` 占用的百分比，照理來說 %Total CPU Usage 一定要比 %CPU 高，因為它有包含 %CPU 的佔用量，但偶爾會有 %CPU 較高的情況，目前不知道原因，但是大部分時候顯示的數據是合理的。
  ![](https://i.imgur.com/qVjny0m.png)

- 第二張圖是每個虛擬核心的使用率，我的虛擬機配置了 2 核 4 緒，所以有 4 個虛擬核心，也就是 %CPU0 到 %CPU4
  ![](https://i.imgur.com/Nc2C9rR.png)

- 第三張圖是記憶體使用率，%Total Mem Usage (藍色) 為整個系統占用的 記憶體百分比，%Mem (紅色) 為 `sort` 占用的百分比。我配置給虛擬機的記憶體總共 4 GB 。
![](https://i.imgur.com/GVyFpvj.png)


:::spoiler **產生以上三張圖的 python 原始碼**
```python=
import plotly.express as px
import plotly.graph_objs as go

def drawpic(data, title, ydata):
    fig = go.Figure()
    fig.update_layout(
        title=title,
        xaxis_title="Time (mm:ss)",
        yaxis_title="Usage (%)",
        template="plotly_dark"
    )
    color = ['red', 'yellow', 'orange', 'green']
    for i in range(len(ydata)):
        fig.add_trace(go.Scatter(x=data['TIME'], y=data[ydata[i]], mode='lines',
                                 name='%' + ydata[i]))
    fig.show()
    
drawpic(sort, 'CPU Usage', ['Total CPU Usage', 'CPU'])
drawpic(sort, 'Every Single CPU Usage', ['CPU0', 'CPU1', 'CPU2', 'CPU3'])
drawpic(sort, 'Memory Usage', ['Total Mem Usage', 'Mem'])
```
:::

- 接下來使用 `sudo iotop -o -b > iotop.txt` 來查看硬碟讀寫的狀況，一樣將檔案輸出到一份文字檔，格式如下:

  ```
  ...
  Total DISK READ:       130.67 M/s | Total DISK WRITE:         7.90 K/s
  Current DISK READ:     130.67 M/s | Current DISK WRITE:       3.95 K/s
      TID  PRIO  USER     DISK READ  DISK WRITE  SWAPIN      IO    COMMAND
     7794 be/4 lin        64.16 M/s    0.00 B/s  0.00 %  0.64 % benchmark1/sort1 input.txt benchmark1/output.txt
     7795 be/4 lin        66.51 M/s    0.00 B/s  0.00 %  0.57 % benchmark2/sort2 input.txt benchmark2/output.txt
     7137 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.01 % [kworker/u8:0-events_power_efficient]
     7763 be/4 lin         0.00 B/s    7.90 K/s  0.00 %  0.00 % top -1 -i -b
  ...
  ```

  和前面雷同，用 dataframe 紀錄 Total DISK READ 、 Total DISK WRITE 、 DISK READ 、 DISK WRITE，再用 plotly 畫出圖表，這裡就不放 code 跟範例圖表了。

成功計時和畫出圖表後，接下來我開始分析 `sort` 的效能，以及嘗試優化。

### 效能分析: 運行 1 個 2-way merge sort 排序 8 GiB 以及 16 GiB

我總共排序同樣的 8 GiB 以及 16 GiB 資料 5 次，耗費的秒數如下:

|實驗次數|8GiB|16GiB |24GiB|
|------|----|------|------|
|1     |515 |1592  |2155  |
|2     |505 |1523  |2183  |
|3     |505 |1547  |2150  |
|4     |517 |1360  |2177  |
|5     |498 |1323  |2170  |
|平均   |508 |1469  |2167  |

**擷取第一次實驗排序 8 GiB 的數據:**

- 下圖紅色線為 `sort` 占用的 CPU 資源，其一直維持在 25 % 上下，表示 `sort` 程序全程都有吃滿一顆核心，而藍色線則是系統整體占用的 CPU 資源，換句話說，藍色線的值減紅色線的值就是 `sort` 以外其他程序消耗的資源，包括 `gnome-shell` 、 `Xorg` 、 `code` 等等。
  ![](https://i.imgur.com/rKnsO6X.png)

- 下圖是每個虛擬核心的使用率，可以發現前期 %CPU3 (紫色)和 %CPU0 (藍色)輪流呈現滿載的狀態，我推測其原因為當時正在執行 2-way merge sort 的 PASS 0 ，該階段需要抓取大量數字進行 C++ 內建的 `sort()` 運算，所以消耗大量運算，讓 %CPU3 和 %CPU0 都呈現 100% 負載。
  而接下來進入 merge 階段不需要一次性的排序大量數字，而是需要反覆讀寫 page ，所以對 CPU 的消耗較低，但仍然讓 %CPU3 占用率衝到 80% 以上。 
  ![](https://i.imgur.com/QSkcMop.png)

- 下圖藍色為系統整體佔用的記憶體，紅色為 `sort` 佔用的記憶體，很明顯看到紅色線有四塊明顯的凸起，此為 PASS 0 時 `sort()` 處理的資料，總共調用 `sort()` 4 次並產生 4 個 page。
  在此程式中每次 `sort()` 處理的資料量為 200000000 個 `int` ，所以記憶體消耗為 $200000000 \times 4 \div 1000000 = 800$ MB 剛好為記憶體 (4GB) 的 20%，符合紅線的高峰值，由此可以知道 `top` 指令的記憶體資訊是足夠準確的。最後一個 page 沒有吃滿 20% 記憶體是因為生成 4 個 page 後， input.txt 剩下的數字不滿 200000000 個。
  在 merge 階段只需重複從兩兩 page 讀取最小值，存入 merged page ，所以不需要配置大量記憶體，紅色線在此階段的記憶體消耗趨近於 0% 。
  ![](https://i.imgur.com/6Coaoad.png)

**分析完此實驗的效能後，我產生以下想法:**
>1. 由 CPU Usage 的圖可以發現運行一個 `sort` 下的系統整體佔用(藍色線)為 40% 左右，且 `sort` 佔用(紅色線)為 25% ，由此推測: 如果同時運行 3 個 sort，則系統整體佔用約為 40% + 25% + 25% = 90% ，約可以將這台虛擬機的 CPU 吃滿。
   如果同時執行 4 個或以上 `sort` ，則 CPU 運算能力會不夠。也許作業系統會讓其中一個 sort 暫停執行，讓其他三個先執行；抑或是讓 4 個 sort 同時執行?
>2. 由 Memory Usage 的圖可以發現運行一個 `sort` 的 PASS 0 的記憶體佔用 (藍色線) 為 40% 到 50% 不等，且 `sort` 佔用(紅色線)為 20%，由此推測: 如果同時運行 3 個 `sort`，則系統記憶體佔用約為 30% + 3 * 20% = 90% ，快要可以將這台虛擬機的記憶體吃滿。
   如果同時執行 4 個或以上 sort ，則記憶體空間不夠。也許作業系統會開始大量使用 swap 機制，將記憶體的資料暫時搬到硬碟?
>3. sort 在 PASS 0 之後便沒有大量利用記憶體，也許可以善用記憶體來改善 `merge` 的效能? 或是利用 multithread 在 PASS 0 的 page 生成後馬上進行 merge?

在之後的實驗我會探討以上議題。

### 效能分析: 同時運行 3 個 2-way merge sort 排序 8 GiB

接下來我嘗試一次執行多個 `sort` ，我將專案目錄複製為 3 份，分別命名為 benchmark1 、 benchmark2 、 benchmark3 。為了方便區隔每個目錄執行的程式，目錄中的 `sort` 也被重新命名為 `sort1` 、 `sort2` 、 `sort3` ，然後使用 shell script 一次執行 3 個 `sort` :

```bash
$ cat many.sh
benchmark1/sort1 input.txt benchmark1/output.txt &
benchmark2/sort2 input.txt benchmark2/output.txt &
benchmark3/sort3 input.txt benchmark3/output.txt   
$ chmod 700 many.sh
$ ./many.sh
```

三個同時執行的 `sort` 程式分別花了 553 、 555 、 557 秒 (約莫 9 分鐘，但實際上三個程式跑完需要 9 分半) 完成排序，可以發現較執行單一個程式平均 508 秒慢了 10% 左右，但他們大致上是同步執行的。

**實驗數據:**
- CPU 占用率上 90% 了
  ![](https://i.imgur.com/Qamdjbz.png)
  
- 閒置的核心變少了
  ![](https://i.imgur.com/oLQELtx.png)

- 記憶體占用率變高了，但是還沒吃滿記憶體。這一次實驗中，非 `sort` 的程序佔用的記憶體只有 20% 左右，三個 `sort` 各自佔用的記憶體也都是 20% 左右，所以記憶體的總佔用量約為 20% + 3 * 20% = 80% 左右。我分析了 SWAP 的使用率(紅色折線)，SWAP 的大小為 2GB 。在這次實驗中，有稍微使用 SWAP 。
  ![](https://i.imgur.com/mPIDpLF.png)

- 下面這張白底圖是硬碟讀取的速度，單位為 MB/S，其中藍色折線是整個系統的讀取速度，可以看到 PASS 0 時，在調用 c++ 內建的 `sort()` 前，會大量從 input.txt 讀取資料，總共讀取 4 次；後面的 PASS 則是不斷從 page 讀取資料。
  ![](https://i.imgur.com/Kr8Kh9I.png)
- 下面這張白底圖是硬碟寫入的速度，單位為 MB/S，其中藍色折線是整個系統的寫入速度， PASS 0 時，在 c++ 內建的 `sort()` 結束後有大量寫入的工作。
  ![](https://i.imgur.com/qHrVWFO.png)

感覺這次實驗還沒辦法讓虛擬機遇到瓶頸，所以我決定再同時執行更多 `sort` ，看作業系統會如何處理這些程式。

### 效能分析: 同時運行 6 個 2-way merge sort 排序 8 GiB

執行 6 個 `sort` ，消耗的時間分別為 617、616、606、608、610、614 秒，然而所有程式跑完卻需要 20 分鐘左右，與 600 多秒相差甚遠，後來發現我所使用的 `clock()` 是用來量測 CPU time，非 wall-clock time。所以我量測到的是程式佔據 cpu 的時間，非程式開始執行到結束的系統時間。

- 同時執行 6 個 `sort` 時，總體 CPU 使用率沒有一直維持在 80% 以上，每次接近 100% 時就迅速掉落，每個 `sort` 也不是全程都佔用滿 1 顆核心，推測其原因為作業系統工作量太大，一直切換執行程序，CPU 佔用高時，正在執行 `sort` ； CPU 佔用低時，執行 gui 、 top 之類的背景程序。
  ![](https://i.imgur.com/5iMO9G1.png)

- 每個核心的占用率
  ![](https://i.imgur.com/nE26pBR.png)

- 這次我分析了 SWAP 的使用率(紅色折線)，SWAP 的大小為 2GB 。在這次實驗中， PASS 0 使用的記憶體超過 95% ，記憶體空間已不敷使用，所以大量使用 SWAP 來暫存資料。但是 SWAP 在 PASS 0 時也幾乎都是滿載的狀態，不知道作業系統用甚麼機制去處理記憶體跟 SWAP 都滿載的情況。
  ![](https://i.imgur.com/YD5cugS.png)

  ![](https://i.imgur.com/M9gmkJY.png)

  ![](https://i.imgur.com/w5bF47S.png)


**根據這次實驗，我歸納以下結論:**

>1. 從這次實驗可以發現在排序程式超過 CPU 可以負荷的程式的量時，作業系統會想辦法讓每個 `sort` 輪流使用 4 顆核心，並且每個 `sort` 在差不多的時間結束執行 (在此次實驗是約莫 23 分鐘)，代表作業系統分配的資源很平均，沒有發生一個程式執行完，另一個程式才執行到一半的狀況。
>2. 這次實驗可以看到記憶體跟 SWAP 都完全被吃滿，這次實驗過大的記憶體需求也導致這次實驗所花的時間變多，因為 SWAP 的速度跟硬碟一樣慢。
>3. 和前一次實驗 (同時運行 3 個 2-way merge sort) 相比，我發現同時執行 6 個會比較沒效率。假設我需要排序 6 個檔案，同時運行 3 個 2-way merge sort 兩次總共會花 9.5 * 2 = 19 分鐘；同時運行 6 個 2-way merge sort 一次總共會花 19 分 48 秒，慢了 48 秒左右。
>我猜測這些時間應該是耗費在系統排程和 SWAP 上，系統希望平均分配每個程式 (包括背景執行的程式) 佔用 CPU 的時間，雖然可以讓這些程式在差不多的時間結束，但反而降低每個程式的效率。
>但我覺得降低效率不一定是壞的，如果不平均分配資源的話，有些重要的功能會無法正常運行，比如 gui 介面可能會直接卡住不能動，或是想關掉 `sort` 時，會連 `kill` 都無法執行。所以這也許是資源有限的情況下作業系統的取捨吧!

之後的實驗，我將排序程式優化，並觀察效能。

### 效能分析: 運行 1 個 k-way merge sort

我總共排序同樣的 8 GiB 以及 16 GiB 資料 5 次，耗費的秒數如下:

|實驗次數|8GiB|16GiB |24GiB|
|------|----|------|-----|
|1     |572 |1368  |1814 |
|2     |584 |1360  |1845 |
|3     |578 |1322  |1887 |
|4     |579 |1349  |1913 |
|5     |595 |1229  |1985 |
|平均   |582 |1326  |1889 |

**擷取第一次實驗排序 8 GiB 的數據:**

![](https://i.imgur.com/ArLZfZA.png)

![](https://i.imgur.com/DhfpVX3.png)

![](https://i.imgur.com/qjX0xmJ.png)

![](https://i.imgur.com/OXwhw1M.png)

![](https://i.imgur.com/f8W6fQu.png)

>1. 我起初認為 k-way merge sort 一定會比 2-way merge sort 快，然而在排序 8 GiB 的檔案時， 2-way merge sort 反而會比較快。 2-way merge sort 平均花費 508 秒，而 k-way merge sort 平均花費 582 秒，整整多消耗 14% 的時間。我推測是因為我的機器上的 SSD 速度不算太慢，在 PASS 0 的 page 數量太少的情況下，更新 min-priority queue 的成本反而比 2-way 的比大小還要高，造成了明明 I/O 次數多，但排序速度較快的現象。
>排序 16 GiB 時，k-way merge sort 的速度就比 2-way merge sort 快了，前者平均花費 1326 秒，後者 1469 秒，約為 10% 差距。
>3. 我覺得 k-way merge sort 使用系統資源的模式跟 2-way merge sort 幾乎一模一樣，我無法從中分析有用的資訊。

### 效能分析: 同時運行 6 個 k-way merge sort 排序 8 GiB

![](https://i.imgur.com/jbmT461.png)
![](https://i.imgur.com/hVgyKye.png)
![](https://i.imgur.com/zd7e8JP.png)
![](https://i.imgur.com/vJMP5We.png)
![](https://i.imgur.com/65dxHnf.png)

這次執行 k-way merge sort ，消耗的時間分別為 802、805、798、792、793、789 秒， 6 個程式跑完總共耗時 26 分鐘。感覺效能優化並沒有成功，尤其是排序 8 GiB 資料時，雖然硬碟重複讀取較少次，但速度就是比 2-way merge sort 慢! 也許是我的 min-priority queue 實作效能太差，拖慢 k-way merge sort 的速度。但是總體上來說，當資料量越來越龐大， k-way merge sort 的優勢會更明顯。

## 結論

1. 作業系統分配的資源很平均，沒有發生一個程式執行完，另一個程式才執行到一半的狀況。系統希望平均分配每個程式 (包括背景執行的程式) 佔用 CPU 的時間，雖然可以讓這些程式在差不多的時間結束，但反而降低每個程式的效率。但若是不平均分配資源的話，有些重要的功能會無法正常運行，如 gui 服務，這算是有限資源下的取捨。
2. 程式執行時，並不是由一顆核心從頭跑到尾，而是系統不定時重新分配每顆核心的工作，所以在 Every Single CPU Usage 圖中可以看到每個核心輪流吃到 100% 然後又降下去。
3. 當記憶體快要滿時，作業系統被迫大量使用 swap，這也許是同時執行多個程式效率差的原因之一。
4. k-way merge sort 並不是所有情況下都比 2-way merge sort 快，因為需要考慮更新 min-priority queue 的成本，以前面實驗的結果來說，用 2-way merge sort 排序 8 GiB 的檔案比較快，但是當資料量更大時， k-way merge sort 的速度會比較快。以下是一張排序 8、16、24 GiB 的比較圖:

  ![](https://i.imgur.com/Fyhnahv.png)
