or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
2023q1 Homework1 (lab0)
contributed by < LiChiiiii >
開發環境
完成 queue.c
TOTAL SCORE : 100/100
注意書寫規範:中英文間用一個半形空白字元區隔。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_new
利用
malloc()
配置記憶體空間,若記憶體配置失敗回傳NULL
,成功則使用list.h
中的INIT_LIST_HEAD()
來初始化head
。q_free
使用
list.h
中的list_for_each_entry_safe()
走訪佇列中每個節點,並使用q_release_element()
釋放每一個元素,迴圈做完只會剩下指向佇列的l
,最後free(l)
完成此功能。list_for_each_entry_safe()
會額外使用一個指標safe
來暫存下一次循環的 entry,使得每次在執行q_release_element()
時不會影響迴圈的執行。q_insert_head
先替
new_itm
(欲新增至佇列的元素)配置一個資料結構為element_t
的記憶體空間。計算
s
(欲新增至new_itm->value
的字元)大小,並依據計算出的大小配置記憶體空間至new_itm->value
,透過條件式確認配置成功後,利用memcpy()
將s
複製到new_itm->value
中,最後呼叫list_add()
將new_itm
元素加入佇列的第一個。剛開始忘記在判斷配置失敗後要執行
free(new_itm)
(第11行),導致報錯error: Memory leak: new_itm [memleak]
。q_insert_tail
與
q_insert_head
的思路一樣,將第15行改成list_add_tail()
。q_remove_head
使用
list_first_entry()
找到佇列中第一個元素,並透過list_del()
刪除此元素。使用
strncpy()
來複製字串至sp
以避免 buffer overflow 的問題,但會產生以下狀況,若來源字元數小於限制複製字元的個數,剩下未填滿的部分會全部補上 '\0',反之則要手動補 '\0'(第9行)。q_remove_tail
與
q_remove_head
的思路一樣,將第5行改成list_last_entry()
。q_size
使用
list.h
中的list_for_each()
走訪佇列,紀錄佇列長度。q_delete_mid
利用 doubly-linked list 的特性,宣告兩個指標
front
和rear
分別從前向後和從後到前同時移動,直到重疊即可找到mid
並刪除。利用front!=rear->prev
條件式來尋找含偶數個元素的佇列之mid
,利用front!=rear
條件式來尋找含奇數個元素的佇列之mid
(第6行)。原本的寫法是先寫
q_release_element(mid)
,才接著寫list_del(front)
,這樣會先把front
指向的元素之記憶體空間釋放掉,導致報錯:Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
q_delete_dup
flag
:決定當前元素是否為應被刪除的元素利用迴圈比較當前元素
cur_el
以及前一個元素cur_prev_el
之值是否相同,若相同則刪除cur_prev_el
並設定flag=1
,若不相同但flag=1
則代表當前元素cur_el
為重複元素中最後一個元素,也就是應被刪除的元素。q_swap
flag
:決定當前元素是否與前一個元素交換若
flag=0
則設定flag=1
並跳過此元素,若flag=1
則當前元素與前一個元素交換(前一個元素移到當前元素後面)並設定flag=0
。q_reverse
list_move()
會先執行list_del()
將當前指向的元素刪除,在執行list_add()
將元素新增至佇列最前端。第 7 行使用list_for_each_safe()
可以允許當前節點從佇列中移除,用list_for_each()
會導致 infinite loop 。q_reverseK
讓指標邊走邊數 k 個元素,到第 k 個元素進行 reverse 。
cur_prev_k
存放top
為 1 的元素之記憶體位址,也就是記錄當前元素要進行 reverse時的前 k 個元素之記憶體位址。宣告改成
*cur_prev_k = head->next
會出現無限迴圈,因為cur_prev_k
會跟著指向的元素做移動,導致cur_prev_k
永遠不會等於tmp
,也就是離不開 while 迴圈。q_sort
參考你所不知道的 c 語言: linked list 和非連續記憶體、 Linked List Sort 中提到的 Merge Sort 以及 seasonwang0905 的程式碼實作。
避免張貼完整程式碼,列出關鍵程式碼並闡述你的觀察、推論,和考慮議題。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →排序實作總共用到三個函式:
merge_two_list()
:將兩個佇列合併成一個已完成排序的佇列mergesort()
:將未排序的佇列進行不斷的分割,直到剩一個節點即開始執行merge_two_list()
,直到遞迴結束。q_sort()
:先將尚未排序的佇列變成 singly-linked list ,這樣排序過程中就不用維持 doubly-linked list 。等到執行完mergesort()
排序完畢後,再重新連結 prev 即可。q_descend
從 list 尾端向前比較大小,比從 list 前端向後比較大小來的簡單。前者只要反向比較下一個元素小於當前元素即可刪除,後者則是順向比較當前元素之前的所有元素是否小於當前元素。
q_merge
使用
queue.h
中定義的資料結構queue_contex_t
來表示每一個queue。透過
list_for_each_entry()
查看所有的佇列,並將佇列合併,最後將合併起來的queue做排序。改進
web
命令原始程式碼執行
web
命令可開啟網頁伺服器,一旦 web_fd > 0 表示成功開啟 web server 。在
web.c
可以看到已經寫好在 web 接收訊息和傳送訊息的處理方式。問題在於網頁伺服器開啟後,處理命令列的
linenoise
套件無法使用,因此嘗試改寫linenoise.c
用 select() 同時處理 stdin 及 socket。在
line_edit
新增參數web_fd
,當 web_fd != 0 就使用select()
監聽。若從 web 輸入訊息(第33行),則將訊息複製到 buf 中並透過 linenoise 處理命令,同時也傳送 HTTP 回應的 header 訊息給客戶端,表示回應成功,並關閉 socket 。若從命令列輸入訊息(第43行),則保持原本做法處理。實作
shuffle
命令利用 Fisher–Yates shuffle 演算法來實作洗牌。
原本 swap 的寫法是透過
list_move()
來移動兩個節點位置,但執行 shuffle 時偶爾會失敗,後來才改成交換 value 的方法。除了實作程式碼,還需要在
qtest.c
新增命令和執行函式。Address Sanitizer
在
Makefile
中發現已定義一個變數稱SANITIZER
,當SANITIZER
變數設置為 1,即可啟用 address sanitizer。執行下列命令開啟 address sanitizer ,並重新編譯,沒有出現任何關於記憶體之錯誤。
執行結果
Valgrind
執行
make valgrind
沒有出現相關問題執行結果
使用 Massif 查看記憶體的狀況
以下是

traces/trace-17-complexity.cmd
的記憶體使用狀況在 trace-17 執行了
q_insert_head()
、q_insert_tail()
、q_remove_head()
以及q_remove_tail()
四個函式,在圖中的最右邊可以看到,執行結束後記憶體並沒有釋放完全,此部分待確認。Linux 核心原始程式碼的
lib/list_sort.c
比較
lib/list_sort.c
與自行實作的合併排序演算法差異由於無法新增
queue.h
的定義,所以就把lib_sort.c
的程式放進qtest.c
,新增一個 option 來切換 sort 的實作,這樣很快就可以看看自己實作的效能跟 Linux 核心程式碼的差距。在
qtest.c
當中把do_sort()
函式的部分改為這樣:參考 komark06 對
list_sort.c
的修改方法,將程式放入qtest.c
執行。接著利用以下的 command 來比較排序時間:
執行
list_sort.c
會出現Segmentation fault occurred.
,應是引入程式碼時有錯誤,待處理。研讀論文〈Dude, is my code constant time?〉
論文中提出了工具 dudect ,可以用來檢測一段程式是否 constant time 執行。
測試方式主要分成三個步驟:
t-test
(採用 Welch's t-test ) 和Non-parametric tests
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →t-test 是一個常用來協助判斷比較兩組資料是否具有顯著差異的統計方法之一。在這裡我們試圖反證兩組資料時間分佈相等,也就是說當 t-test 拒絕假說(無法證明平均值的差異),表示執行時間為 constant time。
程式實作原理
在 lab0-c 中,當
simulation
開啟後會將is_xx_xx_const()
作為目標函式進行時間複雜度測試test_const()
\(\rightarrow\)doit()
,並根據論文中的三個步驟實作:measure()
和differentiate()
:計算目標函式執行時間update_statistics()
:處理取得的資料report()
:利用 Welch's t-test 驗證目標函式是否為 constant time在
measure()
函式發現計算過程中直接減掉要做刪除的次數(第10行),但測試流程應該要是紀錄所有資料再去做第二步驟的資料處理。因此將該部分改成做完
N_MEASURES
次的紀錄後進行排序再刪除前後各DROP_SIZE
個資料點,即可每次皆通過trace-17-complexity
的測試。Debug 紀錄