2025q1 Homework1 (ideas)

contributed by < chensheep >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

運用並行處理來強化網站資料存取的效率 : yeh-sudo

• 本質上還是一個 single threaded 的資料庫，大量並行處理的情況下會有效能瓶頸。

• Redis 2024 年修改授權條款，ValKey 是從舊版本 Redis fork 出來的專案。

• 開發環境

  • Linux andyyeh-ubuntu 6.5.0-21-generic
  • gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
  • AMD Ryzen 7 4800HS

• RCU：一種同步機制，允許多個 reader 讀取資料，同時一個 writer 更新資料

• Linux kernel 的各種鎖，透過鎖的機制保護 critical section 就會有效能損失，所以後來出現 lock-free programming 跟 RCU

  • Spinlock 與 Semaphore 一次只能讓一個執行緒進入 critical section，有可能造成效能瓶頸
  • Ticket Spinlock：每個執行緒獲取各自的 ticket 判斷能不能進入 critical section，缺點是必須更新每個 CPU 裡面的 ticket，更新方式是透過廣播，會損失非常多的效能
  • MCS Spinlock：解決 Ticket Spinlock cache coherence 的問題，但本質上還是只能讓一個執行緒進入 critical section
  • Read-Write Lock：允與多個 reader 同時讀取資料，當有 reader 讀取資料時 writer 不可以進行更新，需等到所有 reader 都退出 critical section

• User-space RCU

  • 類似 Linux kernel 的 RCU 但實做在 user-space
  • 5 種 flavor 目的是支援不同的作業系統和版本

• URCU Flavors

  • RCU using sys_membarrier() system call (liburcu) 預設
  • Memory-barrier-based RCU (liburcu-mb) 與上面那種的差別在於沒有使用系統呼叫
  • Signal-based RCU (linurcu-signal) 透過 writer 向 reader 發送訊號來同步
  • Bullet-proof RCU (liburcu-bp) 使用上最簡單，效能最差
  • QSBR (liburcu-qsbr) 最特別，需手動讓執行緒進出 quiescent-state (待確認)，執行緒不處理 critical section 時就處於這個狀態，官方範例是每 1024 個讀取就退出，讓一個 writer 進去更新資料，效能理論上最好，reader 端幾乎沒有成本。

• 測試方式透過 memtier_benchmark 有三個場景，

  • Cache 10:1
  • Cache 100:1
  • Session store 1:1

20:14

建構 RISC-V 相容處理器並運作 Linux 核心 : millaker

• 要如何驗證我們開發的 RISC-V 處理器能運作呢？利用 Linux 來驗證。