contributed by < Rispolyv0n
>
認真看作業要求,除了提及如何逐步達到要求,還需要進行:
還未達成符合預期目標,請繼續付出!
根據C Programming Lab in CMU,此作業需修改 queue.c, queue.h 兩個檔案,實作以下七個函式:
q_new()
: 建立一個新的空佇列q_free()
: 清空一個佇列所用到的空間q_insert_head()
: 試圖在佇列頭端插入一個節點 (用於LIFO)q_insert_tail()
: 試圖在佇列尾端插入一個節點 (用於FIFO)q_remove_head()
: 試圖刪除佇列頭端的第一個節點q_size()
: 計算佇列所含的節點數量q_reverse()
: 將佇列中的節點做倒序,並且不得 free 或 allocate 佇列中的節點,只能做重新排列。不能對佇列中所儲存的字串長度設上限。
q_insert_tail()
及 q_size()
兩個函式需為 。
測試檔會測試超過 1,000,000 個節點的佇列,作業分數會利用15個 trace 檔做計算(自動評分系統)。
作業要求 q_insert_tail()
及 q_size()
兩個函式需為 ,因此修改 struct queue_t
如下 (註解標示處):
有了以上的結構,就可以在必要的地方對 queue.h 中所定義的各個 field 做適當的操作,如下 (註解標示處):
q_new()
第 5 ~ 7 行將 structure 中 各 field 初始化,包括將 q->head, q->tail 初始化為 NULL, 以及將 q->size 初始化為 0 :
q_insert_head()
第 14 ~ 17 行,在確定插入節點時將 q->size 加 1, 並調整 q->tail :
q_remove_head()
第 12 ~ 14 行,在確定移除節點時將 q->size 減 1, 並調整 q->tail :
有了以上適當的操作後,即可將 q_insert_tail()
及 q_size()
兩個函式修改為如下,以達到 :
q_insert_tail()
中可直接找到 queue 的 tail 位置,對其插入節點,不用從頭遍歷整個 queue ,因此執行時間就不會受 queue 長度影響:
q_size()
函式中可直接 return structure queue_t
中的 field size
,不用每次都遍歷 queue 中所有節點,邊計算節點數,因此執行時間就不會受 queue 長度影響:
執行 $make test
時,會去呼叫 scripts/driver.py ,而 scripts/driver.py 中紀錄著所有測試檔的檔名 (traceDict
) 及測試檔所在的資料夾位置 (traceDirectory
)。若執行時無特別指定測試檔編號,則會依序利用所有 traceDict
中的測試檔做測試。可於 runTrace()
函式中看到利用 subprocess.call()
執行了 $./qtest
,同時指定用某測試檔去做測試。 (如以下程式碼的第 7, 9 行) :
首先 console.h 中定義了 cmd_ele
的 struct
,用來紀錄各個 command 及其相關資訊。如下:
qtest.c 的 main()
中呼叫 init_cmd()
及 console_init()
定義了各種 command 、有關 command 的描述、以及讀取該 command 後要呼叫的函式,並將這些 command element 用 console.c 中的 add_cmd()
以 linked list 的方式紀錄於 cmd_list
。如下:
而測試檔中所寫的就是這些 command ,qtest.c 中的 run_console()
會去一行行讀取測試檔中的 command ,並在 interpret_cmda()
中從 cmd_list
找到對應的 cmd_ele
,呼叫對應函式。
qtest.c 中的 main()
接完參數後,會呼叫 queue_init()
,其中將 SIGSEGV
及 SIGALRM
兩個訊號各利用 signal()
設定了各自的 signal handler ,以便處理「 access 到不合法的記憶體」與「超時操作」兩種情況,如下:
而兩個 signal handler 中皆會傳各自的 message 給 harness.c 中的 trigger_exception()
。其中 jmp_ready
為一 volatile
變量,是為了防止編譯器完全根據程式碼中的上下文去優化,導致執行時的值可能與實際上 jmp_ready
記憶體中的值不一樣而產生不可預期的執行結果,這樣可以強迫編譯器每次用到 jmp_ready
時都要乖乖的去記憶體中重新讀取它當下的值。此處為了防止讀取 jmp_ready
值時,值又被意外更動的可能,用了 type sig_atomic_t
,確保讀取的動作不會被中斷。
由以上程式碼可知,當 jmp_ready
為真時,就跳到上次做 sigsetjump()
時所存的 env
下。而 sigsetjump()
會在每次讀取新 command 時要呼叫大家自己實作的函式前,在 exception_setup()
中被呼叫,因此若執行自己實作的函式時發生「超時操作」與「 access 到不合法的記憶體」兩種情況,即可回溯記憶體環境至執行自己實作的函式前,並且跳過已知執行後會出錯的函式,結束整個執行 command 的包裝函式。
由 linux man page 可知若是從 siglongjmp()
返回,則 segsetjump()
會返回非零,因此 exception_setup()
中即可對「初始程式回溯點」與「console指令函式後續操作發生錯誤而啟動 trigger_exception()
返回回溯點」兩種情況做對應處理。
而 jmp_ready
的值在準備要呼叫大家自己寫的 queue.c 中的 function 前會被設為 true
,若安全執行完沒有出錯,或者中途執行時出錯了返回程式回溯點,都會將 jmp_ready
設回 false
。
由以上程式碼可知,若為「初始程式回溯點」,則 exception_setup()
會返回 true
。而若為「 console 指令函式後續操作發生錯誤而啟動 trigger_exception()
返回回溯點」,則 exception_setup()
會返回 false
。因此只要像其它 console 指令函式一樣,將可能引起錯誤的程式碼片段用 if (exception_setup())
包起來,第一次執行時,初始程式回溯點完,就會繼續執行 if
中有風險的程式碼。萬一執行過程中發生錯誤,就會跳回到 if (exception_setup())
,這時 exception_setup()
會返回 false
,即可安全的跳過會引起錯誤的程式碼,繼續完成 console 指令函式。以下拿 do_new()
函式為範例:
1498 114) A volatile declaration may be used to describe an object corresponding to a memory-mapped input/output port or an object accessed by an asynchronously interrupting function.
—— The New C Standard
被宣告 volatile
的變數,會防止編譯器根據程式碼上下文對該變數做過度優化。以下為一編譯器優化後卻導致非預期的執行結果範例:
則以上程式碼可能因編譯器不知道變數 status
的值可能意外被改變,只根據程式碼判定變數 status
從頭到尾並未被更動,因此直接將迴圈改為一個無限迴圈如 while(1)
,減少訪問變數 status
值的次數,以達到優化目的。而這樣的編譯結果卻與我們所預期的不一樣,導致執行結果錯誤。因此我們需要 volatile
這個 qualifier,去防止編譯器過度優化,每次都去重新讀取變數 status
的值。
被宣告為 volatile
的變數代表它可能有著以下特性:
也就是此變數的值可能被硬體更新,或者被其它同時執行中的線程更新,不是完全根據當下執行中程式碼上下文的操作去做更動。讓編譯器知道變數具有這樣的特性,編譯器就不會對被宣告為 volatile
的變數做過度的優化了。