---
# System prepended metadata

title: 2020_OS_Fall_HW2

---

# 2020_OS_Fall_HW2

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

[TOC]

## 開發環境：

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

## 程式執行時間

### CPU Time

- 針對每個不同 pthread 的數量，重複執行 5 次程式並量測 cpu time，單位為秒
- cpu time 為程式佔用 cpu 的時間

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

將上表以 thread 數量為 x 軸、耗費時間為 y 軸畫成分佈圖:

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


### Wall-Clock Time

- 針對每個不同 pthread 的數量，重複執行 5 次程式並量測 wall-clock time，單位為秒
- wall-clock time 為程式開始到結束的系統時間

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

將上表以 thread 數量為 x 軸、耗費時間為 y 軸畫成分佈圖:

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

## 程式開發與使用說明

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

```bash
$ tree
.
├── Makefile
└── source_code
    ├── bench.h
    ├── deprecated_main.h
    ├── gen_input.cpp
    ├── main.cpp
    └── main.h

1 directory, 6 files
```

### 使用說明: 編譯

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

```bash
$ make
g++ source_code/gen_input.cpp -o gen
g++ source_code/main.cpp -o main -lpthread
```

### 使用說明: 執行

編譯完成之後，會產生兩個執行檔: `gen` 、 `main`。
- 在專案目錄輸入 `./gen` 可以在專案目錄生成一個 1 GiB 的 input.csv:
  ```bash
  $ ./gen
  # generate a 1 GiB input file
  ```
- input.csv 一定要放在專案目錄裡，並且在專案目錄執行 `main` ，否則程式無法正確執行。
  在專案目錄輸入 `./main` 或 `./main 1` 即可執行**單執行緒 ETL**。

  ```bash
  $ ./main
  # execute single thread ETL
  ```
   在專案目錄輸入 `./main [thread num]` 即可執行**多執行緒 ETL**。
  ```bash
  $ ./main 4
  # execute 4-thread ETL
  ```

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

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

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

### 程式開發: single thread ETL

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

1. 將 input.csv 的資料以行為單位，用 `fgets()` 讀入 buffer ，再利用 `strdup()` 將 buffer 內的字串值存入指標陣列 `line[i]` ， (`line` 的型態為 `char**`)
2. 用 `fpritf()` 將 `line[i]` 的資料組合成 json 格式，印到 output.json

### 程式開發: multithread ETL

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

1. 將 input.csv 的資料以行為單位，用 `fgets()` 讀入 buffer ，再利用 `strdup()` 將 buffer 內的字串值存入陣列 `line[i]`
2. 將 line 陣列的元素平均分配給所有 p_thread ，舉例：假設 input.txt 有 205 行， thread 的數量為 6 ，則第 1 到第 5 個 thread 處理 $\lfloor{\frac{205}{6}}\rfloor = 34$ 行，第 6 個 thread 處理其餘行數，也就是 35 行。創建完所有執行緒後，使用 `pthread_join()` 等待所有執行緒完成工作。
3. 待所有執行緒將字串轉換成 json 格式並把字串存回 `line` ，主程式再將所有字串依序輸出到 output.json

## 效能分析報告

### 時間分析方法

- 使用 c++ 內建的 `clock()` 記錄程式的 cpu time
- 使用 `time.h` 的 `clock_gettime()` 紀錄 wall-clock time
- 撰寫一份自動測試的批次檔 `test.sh` 重複執行程式，並將執行時間輸出到 `dump.txt` 
    :::spoiler *批次檔原始碼*
    ```bash
    for (( t = 1; t <= 20; t++ ))
    do
        echo "testing for $t thread(s)"
        for (( i = 0; i < 5; i++))
        do
            ./main "$t" >> dump.txt
            echo "finish $i time"
            rm output.json
        done
    done
    ```
    :::
    ::: spoiler *dump txt  格式*
    ```
    running single thread...
    cpu time: 17.303421 sec
    wall-clock time: 18.672616 sec
    running single thread...
    cpu time: 17.155201 sec
    wall-clock time: 17.173728 sec
    ```
    :::
- 使用 python 擷取每次實驗的 cpu time 和 wall-clock time ，並且儲存為 csv 檔
  ::: spoiler *擷取資料原始碼*
    ```python
    import pandas as pd
    file = open('dump.txt', 'r')
    cpu = []
    wall = []
    while True:
        line = file.readline()
        if not line:
            break
        chunks = line.split(' ')
        chunks = list(filter(None, chunks))
        if chunks[0] == 'cpu':
            cpu.append(float(chunks[2]))
        elif chunks[0] == 'wall-clock':
            wall.append(float(chunks[2]))
    cpus = []
    walls = []
    begin = 0
    end = 5
    while True:
        cpus.append(cpu[begin:end])
        walls.append(wall[begin:end])
        begin = begin + 5
        end = end + 5
        if begin >= len(cpu):
            break
    
    cpudf = pd.DataFrame();
    walldf = pd.DataFrame();
    for i in range(20):
        name = str(i + 1) + '-thread'
        cpudf[name] = cpus[i]
        walldf[name] = walls[i]
    cpudf.to_csv('cputime.csv')
    walldf.to_csv('walltime.csv')
    ```
  :::
- 用 libreoffice 讀取 csv 檔，再適當排版，然後計算平均即可完成[表格](#CPU-Time)
- 使用 `plotly` 可根據執行緒數及執行時間畫出[分佈圖](https://i.imgur.com/quXXDNM.png)
  ::: spoiler *畫分佈圖原始碼 (接續擷取資料原始碼)*
    ```python
    fig = go.Figure()
    fig.update_layout(
        title="Wall-Clock Time Scatter of ETL With 1-20 Threads",
        xaxis_title="Thread Number",
        yaxis_title="Wall-Clock Time (sec)",
        template="plotly"
    )
    xtick = []
    ytick = []
    for i in range(1,21):
        for j in range(5):
            xtick.append(i)
            ytick.append(walls[i - 1][j])
    fig.add_trace(go.Scatter(x=xtick, y=ytick, mode='markers',
                             marker_symbol='cross', marker_color = 'red'))
    fig.update_layout(
        xaxis = dict(
            tickmode = 'array',
            tickvals = list(range(1, 21)),
        )
    )
    fig.update_layout(
        yaxis = dict(
            tickmode = 'array',
            tickvals = list(range(3, 15)),
        )
    )
    fig.show()
    ```
  :::
### 效能分析方法

使用 `top` 指令分析 cpu 及記憶體用量，每 0.1 秒擷取一次並輸出至文字檔案，程式結束後等待 0.2 秒再停止執行 `top` ，指令如下:
```
$ su -
# sync; echo 2 > /proc/sys/vm/drop_caches
# iotop -d 0.1 -o -b > ioperf.txt & top -d 0.1 -1 -i -b > perf.txt & ./main \
&& sleep 0.2 && killall top iotop
# rm output.json
```
待指令結束，我們可以得到以下格式文檔:
:::spoiler *perf txt 格式*
```
top - 02:24:58 up  2:11,  1 user,  load average: 0.80, 0.95, 0.96
Tasks: 361 total,   2 running, 358 sleeping,   0 stopped,   1 zombie
%Cpu0  :  0.0 us,  0.0 sy,  0.0 ni, 94.1 id,  0.0 wa,  0.0 hi,  5.9 si,  0.0 st
%Cpu1  :  5.9 us,  5.9 sy,  0.0 ni, 88.2 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu2  : 17.6 us,  0.0 sy,  0.0 ni, 82.4 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu3  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu4  :  5.9 us,  0.0 sy,  0.0 ni, 94.1 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu5  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu6  :  6.2 us,  6.2 sy,  0.0 ni, 87.5 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu7  :  0.0 us,100.0 sy,  0.0 ni,  0.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu8  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu9  :  6.2 us,  0.0 sy,  0.0 ni, 93.8 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu10 :  6.2 us,  0.0 sy,  0.0 ni, 93.8 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu11 :  0.0 us,  6.2 sy,  0.0 ni, 93.8 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
MiB Mem :  31946.5 total,  23871.9 free,   4054.2 used,   4020.4 buff/cache
MiB Swap:   2048.0 total,   2048.0 free,      0.0 used.  27090.3 avail Mem 

    PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
  14950 lin       20   0   92184  19224   3100 R  93.8   0.1   0:00.15 main
   2445 lin       20   0 5313152 509480 269568 S  25.0   1.6  33:40.57 chrome
   1186 root      20   0  362056 134720  79268 S  12.5   0.4   6:39.09 Xorg
     54 root      20   0       0      0      0 S   6.2   0.0   0:00.01 ksoftirqd/7
   1175 lin        9 -11 2269140  19696  15372 S   6.2   0.1   5:01.57 pulseaudio
   2726 lin       20   0 4467356  70548  47880 S   6.2   0.2   0:12.85 code
   7643 lin       20   0 4771516 202772 101468 S   6.2   0.6   0:26.69 chrome
```
:::
:::spoiler *ioperf txt 格式*
```
Total DISK READ:         0.00 B/s | Total DISK WRITE:       132.31 M/s
Current DISK READ:       0.00 B/s | Current DISK WRITE:       0.00 B/s
    TID  PRIO  USER     DISK READ  DISK WRITE  SWAPIN      IO    COMMAND
  24101 be/4 root        0.00 B/s   31.05 K/s  0.00 %  0.00 % top -d 0.1 -1 -i -b
  24102 be/4 root        0.00 B/s  132.28 M/s  0.00 %  0.00 % ./main
```
:::
文檔中，我所關注的是 12 個核心 `%Cpu0` - `%Cpu11` 在程式執行期間的使用率，以及 `main` 程序的 `%CPU` 、 `%MEM` 占用率。為了快速抽取這些資訊，我使用 python 讀取檔案，並且用 `pandas` 的 `DataFrame` 儲存資訊，萃取後的資料如下:

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

:::spoiler *產生 perf Dataframe 原始碼*
```python
import pandas as pd
file = open('perf.txt', 'r')
cpu = []
mem = []
time = []
core = []
tmp = []
for i in range(12):
    core.append([])
    tmp.append(0)
t = 0
while True:
    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])
    if chunks[-1] == target:
        for i in range(12):
            core[i].append(tmp[i])
        cpu.append(float(chunks[8]))
        mem.append(round(float(chunks[9]) * 319.4, 2))
        time.append(round(t,1))
        t = t + 0.1

df = pd.DataFrame()
df['TIME'] = time
df['%CPU'] = cpu
df['MEM'] = mem
for i in range(12):
    name = '%Cpu' + str(i)
    df[name] = core[i]
```
:::

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

::: spoiler *產生 ioperf DataFrame 的原始碼*
```python
file = open('ioperf.txt', 'r')
idx = 0;
main_r = []
main_w= []
time = []
total_r = []
total_w = []
while True:
    line = file.readline()
    if not line:
        break
    chunks = line.split(' ')
    chunks = list(filter(None, chunks))
    if chunks[0] == 'Total':
        time.append(round(float(idx) / 10, 1))
        main_r.append(0.0)
        main_w.append(0.0)
        idx = idx + 1
        if chunks[4][0] == 'K':
            total_r.append(float(chunks[3]) /1000)
        elif chunks[4][0] == 'M':
            total_r.append(float(chunks[3]))
        else:
            total_r.append(0.0)
        if chunks[10][0] == 'K':
            total_w.append(float(chunks[9]) /1000)
        elif chunks[10][0] == 'M':
            total_w.append(float(chunks[9]))
        else:
            total_w.append(0.0)
        continue
    if len(chunks) >= 12 and chunks[11] == './main\n':
        if chunks[4][0] == 'K':
            main_r[idx - 1] = float(chunks[3]) /1000
        elif chunks[4][0] == 'M':
            main_r[idx - 1] = float(chunks[3])
        if chunks[6][0] == 'K':
            main_w[idx - 1] = float(chunks[5]) /1000
        elif chunks[6][0] == 'M':
            main_w[idx - 1] = float(chunks[5])
data = {"TIME": time, "Total Read": total_r, "Total Write": total_w}
df = pd.DataFrame(data)
df['main read'] = main_r
df['main write'] = main_w
```
:::
(程式執行時，最後若干秒沒有 disk I/O 所以 `ioperf` 的 `TIME` (15.0) 會比 `perf` 的少 (17.3) )

---

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

- 第一張圖是 CPU 使用率， `%CPU` (藍色) 為 `main` 占用的 CPU 百分比，其餘 `%Cpu#` 為每個虛擬核心的使用率，我的電腦為 6 核心 12 執行緒，所以總共有 `%Cpu0` - `%Cpu11` 。此外， `%CPU` 的上限為 1200 、 `%Cpu#` 的上限為 100 。
  ![](https://i.imgur.com/EDMdZiW.png)
  :::spoiler 畫出上圖的 python 腳本
    ```python
    def drawcpu(data, title, ydata):
        fig = go.Figure()
        fig.update_layout(
            title=title,
            xaxis_title="Time (sec)",
            yaxis_title="Usage (%)",
            template="plotly_dark"
        )
        fig.update_layout(
            xaxis = dict(
                tickmode = 'array',
                tickvals = list(range(1, 20)),
            )
        )
        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()
    
    df = getdf('perf.txt', 'main\n')
    datanames = ['%CPU']
    for i in range(12):
        dataname.append('%Cpu' + str(i))
    drawcpu(df, 'CPU Usage of Single Thread ETL', datanames)
    ```
  :::

- 第二張圖是記憶體使用率，`Mem` (紅色) 為 `main` 使用的記憶體，單位為 MB 。
  ![](https://i.imgur.com/s4FUqCd.png)
  :::spoiler 畫出上圖的 python 腳本
    ```python
    fig = go.Figure()
    fig.update_layout(
        title="Memory Usage of Single Thread ETL",
        xaxis_title="Time (sec)",
        yaxis_title="Memory Usage (MB)",
        template="plotly_dark"
    )
    fig.update_layout(
        xaxis = dict(
            tickmode = 'array',
            tickvals = list(range(1, 20)),
        )
    )
    fig.add_trace(go.Scatter(x=df['TIME'], y=df['MEM'], mode='lines'))
    fig.show()
    ```
  :::
- 關於硬碟讀寫監測，我發現雙系統環境下的 I/O 監測有些問題，例如: 
  1. 使用 `iotop` 時，經常發生 IO 99% 但是 DISK READ 和 DISK WRITE 都是 0.00 B/s ，無法確定程式是否正在執行讀寫。
  2. 偵測不到 DISK READ ，這個問題似乎跟 Linux 的 clear cache 機制有關，閱讀[這個文章](https://www.tecmint.com/clear-ram-memory-cache-buffer-and-swap-space-on-linux/)後，我在每次使用 `iotop` 前輸入以下指令:
      ```
      # sync; echo 2 > /proc/sys/vm/drop_caches
      ```
      強制釋放 pagecache 和 inode 的暫存，如此一來就可以正確監測 DISK READ 。
  3. 在 `dstat` 、`iostat` 、 `htop` 等硬碟監測工具都有偵測不到 DISK READ 的問題，但是都可以透過 `# sync; echo 2 > /proc/sys/vm/drop_caches` 解決。

- 解決問題後，我畫出第三張圖， `main read` (藍色折線) 為硬碟讀取速度、 `main read` 為硬碟寫入速度，單位皆為 MB/s 。
  ![](https://i.imgur.com/9hxlKtS.png)
  :::spoiler 畫出上圖的 python 腳本
    ```python 
    def getdf(filepath):
        file = open(filepath, 'r')
        idx = 0;
        main_r = []
        main_w= []
        time = []
        total_r = []
        total_w = []
        while True:
            line = file.readline()
            if not line:
                break
            chunks = line.split(' ')
            chunks = list(filter(None, chunks))
            if chunks[0] == 'Total':
                time.append(round(float(idx) / 10, 1))
                main_r.append(0.0)
                main_w.append(0.0)
                idx = idx + 1
                if chunks[4][0] == 'K':
                    total_r.append(float(chunks[3]) /1000)
                elif chunks[4][0] == 'M':
                    total_r.append(float(chunks[3]))
                else:
                    total_r.append(0.0)
                if chunks[10][0] == 'K':
                    total_w.append(float(chunks[9]) /1000)
                elif chunks[10][0] == 'M':
                    total_w.append(float(chunks[9]))
                else:
                    total_w.append(0.0)
                continue
            if len(chunks) >= 12 and chunks[11] == './main':
                if chunks[4][0] == 'K':
                    main_r[idx - 1] = float(chunks[3]) /1000
                elif chunks[4][0] == 'M':
                    main_r[idx - 1] = float(chunks[3])
                if chunks[6][0] == 'K':
                    main_w[idx - 1] = float(chunks[5]) /1000
                elif chunks[6][0] == 'M':
                    main_w[idx - 1] = float(chunks[5])
        data = {"TIME": time, "Total Read": total_r, "Total Write": total_w}
        df = pd.DataFrame(data)
        df['main read'] = main_r
        df['main write'] = main_w
        return df
    
    df = getdf("ioperf.txt")
    fig = go.Figure()
    fig.update_layout(
        title="Single Thread ETL Disk Usage",
        xaxis_title="Time (sec)",
        yaxis_title="Usage (MB/s)",
        template="plotly_white"
    )
    fig.update_layout(
        xaxis = dict(
            tickmode = 'array',
            tickvals = list(range(1, 20)),
        )
    )
    fig.add_trace(go.Scatter(x = df['TIME'], y=df['main read'], mode='lines', name='main read'))
    fig.add_trace(go.Scatter(x = df['TIME'], y=df['main write'], mode='lines', name='main write'))
    fig.show()
    ```
  :::
成功畫出圖表後，接下來我開始分析 `main` 的效能。

### 效能分析: 單執行緒

- 下圖籃色線為 `main` 占用的 CPU 資源，在 0 至 14 秒時一直維持在 100 % 上下，表示 `main` 有吃滿一顆虛擬核心
  ![](https://i.imgur.com/p9N8Nak.png)

- 下為 `main` 占用的記憶體，單位為 MB ，轉換 1 GiB 的 csv 大概需要配置 1150 MB 的記憶體。 
  ![](https://i.imgur.com/TnHAN1c.png)

- 藍色線為硬碟讀取速度，紅色線為寫入速度。前兩秒讀取 input.csv 所以有大量讀取，後面邊轉換邊寫入，所以寫入速度比較慢。
  ![](https://i.imgur.com/52sDIA0.png)

### 效能分析: 2 執行緒

- 由下圖可以看到 `main` 佔用 200% CPU ，表示作業系統有分配兩個虛擬核心給 thread ，而且可以觀察到 `%Cpu2` 和 `%Cpu11` 處理這兩個 thread 。 0-2 秒和 10 到 12 秒都在主程式處理硬碟讀寫，所以 CPU 佔用小於等於 100%。
  ![](https://i.imgur.com/2S4TcVM.png)

- 配置大約 2000 MB 的記憶體，因為 thread 將 csv 轉成 json 格式後要暫存在記憶體，最後再統一輸出到硬碟，所以此次測試配置的記憶體大小比 Single Thread 大
  ![](https://i.imgur.com/guNE28O.png)

- 使用 2 執行緒輸出 output.json 時，因為是連續寫入，所以速度得到巨大的增幅，可以達到 1600 MB/s 的寫入速度。大約前 2 秒讀取，最後 1 秒輸出
  ![](https://i.imgur.com/SUJMmDa.png)

### 效能分析: 3 執行緒

- CPU 佔用 300%
  ![](https://i.imgur.com/Tx3Alyy.png)

- 記憶體佔用 2000 MB
  ![](https://i.imgur.com/oEO0tLl.png)

- 大約前 2 秒讀取、最後 1 秒輸出
  ![](https://i.imgur.com/ytsDSLW.png)

### 效能分析: 4 執行緒

- CPU 佔用 400%
  ![](https://i.imgur.com/Dt1iUqM.png)

- 記憶體佔用 2000 MB
  ![](https://i.imgur.com/QQnnXJ8.png)

- 跟前面的數據差不多
  ![](https://i.imgur.com/97qOeVn.png)

### n 執行緒

由於 2 到 4 執行緒分別的行為太相似，沒有分析的點，我決定將每個執行緒的 CPU 使用率放在一起觀察:

- 下圖為 1 到 10 執行緒的 CPU 佔用率，可以發現 pthread 越多 CPU 暫佔用率越高，執行時間也會比較少，但是執行序數超過 6 之後執行時間就沒有顯著降低了
  ![](https://i.imgur.com/yOiOokH.png)

- 11 到 20 執行緒都會吃滿 CPU ，但是執行時間都差不多
![](https://i.imgur.com/i6qW4xz.png)


### 結論

1. 在我的電腦上，執行緒數量小於等於 12 時，系統會盡量分配足夠的虛擬核心來處理執行緒。大於 12 時仍然會平均分配核心給所有執行緒。
2. pthread 大於 6 時， `main` 的執行時間就沒有顯著改善，我個人推論原因為: 效能好壞跟實體 ALU 數量有關，雖然我的虛擬核心有 12 個，但實體 ALU 只有 6 個，所以執行緒數 6 個以上對效能沒有幫助。
3. 再回到 Wall-Clock Time 的圖表:
   ![](https://i.imgur.com/ehrY3JH.png)
   
   根據每個執行緒的平均執行時間 (average 欄位)，可以把單執行緒的時間跟每個多執行緒的時間相除，繪製效能圖表:
   ![](https://i.imgur.com/1VbJdAG.png)
   
   可以看到 6 執行緒時，為 `main` 的單執行緒速度的 2.8 倍，是我的系統中效能最好的配置。雖然 12 執行緒也同樣能將 `main` 的提升為 2.8 倍但是卻要耗費更大量的 cpu time ，浪費更多運算資源。