F02: list

主講人: jserv / 課程討論區: 2019 年系統軟體課程

Image Not Showing Possible Reasons
  • 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 →
返回「Linux 核心設計」課程進度表

作業說明直播錄影

預期目標

  • 學習 Linux 核心原始程式碼的資料結構
  • 資料封裝和 C 語言程式設計技巧
  • 設計 unit test

Linux 風格的 linked list

閱讀 你所不知道的C語言: linked list 和非連續記憶體操作 共筆和觀看解說錄影。

$ git clone https://github.com/sysprog21/linux-list
$ cd linux-list
$ make

預期會得到以下輸出:

  CC   tests/containerof.o
  LD   tests/containerof
*** Validating tests/containerof ***
 [ Verified ]
...
  CC   tests/list_cut_position.o
  LD   tests/list_cut_position
*** Validating tests/list\_cut\_position ***
 [ Verified ]

其中 include/list.h 學習 Linux 核心原始程式碼的 linked list 資料結構實作程式碼。

  • 自我檢查事項:
  • 為何 Linux 採用 macro 來實作 linked list?一般的 function call 有何成本?
  • Linux 應用 linked list 在哪些場合?舉三個案例並附上對應程式碼,需要解說,以及揣摩對應的考量
  • GNU extension 的 typeof 有何作用?在程式碼中扮演什麼角色?
  • 解釋以下巨集的原理
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
  • 除了你熟悉的 add 和 delete 操作,list.h 還定義一系列操作,為什麼呢?這些有什麼益處?
  • LIST_POISONING 這樣的設計有何意義?
  • linked list 採用環狀是基於哪些考量?
  • 什麼情境會需要對 linked list 做排序呢?舉出真實世界的應用,最好在作業系統核心出現
  • 什麼情境會需要需要找到 第 k 大/小元素 呢?又,你打算如何實作?
  • list_for_each_safelist_for_each 的差異在哪?"safe" 在執行時期的影響為何?
  • for_each 風格的開發方式對程式開發者的影響為何?
    • 提示:對照其他程式語言,如 Perl 和 Python
  • 程式註解裡頭大量存在 @ 符號,這有何意義?你能否應用在後續的程式開發呢?
    • 提示: 對照看 Doxygen
  • tests/ 目錄底下的 unit test 的作用為何?就軟體工程來說的精神為何?
  • tests/ 目錄的 unit test 可如何持續精進和改善呢?

作業要求

  • 回答上述「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題,需要附上對應的參考資料和必要的程式碼
  • 在 GitHub 上 fork linux-list 並學習裡頭的技巧,包含裡頭 unit test 的設計,透過給定的 linked list 操作,進而實作出 merge sort
    • 附上你的修改過程,也需要讓 qtest 得以支援
    • 可將 dict 裡頭的測試資料拿來作效能分析的輸入
    • 思考提升排序效率的方法,需要做平均和最壞狀況的分析

繳交方式

  • 編輯 Homework1 作業區共筆,將你的觀察、上述要求的解說、應用場合探討,以及各式效能改善過程,善用 gnuplot 製圖,紀錄於新建立的共筆

截止日期

  • Mar 3, 2019 (含) 之前
  • 越早在 GitHub 上有動態、越早接受 code review,評分越高

參考資料