Try   HackMD

Linux 核心實作上課筆記與疑惑

第二週

C 語言: 數值系統

運用 bit-wise operator

  • x & (x - 1) == 0 在 C 語言中表示：

    • power of two
      e.g.
      410=1 0 02       ,
      310=0 1 12       ,
      1 0 02       &
      0 1 12=0 0 02
    • signed v.s. unsigned

  • 將字元轉成小寫: 免除使用分支

    • ' '(空格)的 ASCII碼 為
      3210=1 0 0 0 0 02
    • A =
      0 1 0 0 0 0 0 12       , a =
      0 1 1 0 0 0 0 12
    • 英文大寫和小寫的 ASCII 剛好差 32 ，因此利用\ ' ' 即可讓代表 32 的位元設為 1 ，達到大寫轉小寫的作用。
    • 同理，也可利用 & '_' （ _ =
      0 1 0 1 1 1 1 1 12      ）, ^ ' ' 來分別達到將字元轉為大寫和大小寫互轉
('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'
  • Count Leading Zero 疑問

不明白為何 lookup table 的內容是這樣設計，也不了解為何是乘上0x07C4ACDD 並向右位移 27 位元，想請老師幫忙解惑

const int tab32[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31
};
int log2_32 (uint32_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}

Linux 核心的 hash table 實作

常見雜湊函數作法：

  1. Division method
  2. Mid-square
  3. Folding addition
  4. Multiplication Method

TODO
想比照比較同頁面下方 "golden ratio 與非 golden ratio" 的實驗方法，觀察這四值種 hash function 在輸入為亂數時發生碰撞的情形

第三週

你所不知道的 C 語言：遞迴呼叫篇

  • C 語言命名慣例
    • 大寫結構體: 和作業系統、所屬環境有關
    • 小寫結構體: 在文件中有定義的話就可以將它的成員取出來做特定操作

你所不知道的 C 語言：技巧篇

  • C 語言中會將程式模組化，將程式分為 .h 檔 (header file) 和 .c 檔
  • 編譯器一次只編譯一個檔案，每個檔案都是一個編譯單元，會有個別對應的 scope ，若 function 前面加上 static 表示該 function 的有效範圍僅在同一個檔案內，避免到時候 linking 的時候有多個檔案擁有相同的函式名稱，造成重複定義。

第七週

Linux 核心設計: 不僅是個執行單元的 Process

Threads

  • 建立 threads 的成本比建立 process 更低

  • multitasking

  • 切換成本較 process 低

  • Linux Thread State Transition

    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

Linux 核心設計: 淺談同步機制

  • mutex 和 semophore 的比較
    • mutex 確保數個 process 在一個時間點上，只能有一個 process 存取單項資源
    • semaphore 讓數個 producer 與數個 consumer 在計數器的基礎上進行合作
mutex semophore
出現時間 較晚 (2.6.16版) 較早
解鎖 只能由上鎖的 thread 解鎖 可由原本的 thread 或是另外一個 thread 解開
可進入 critical section 之 thread 數量 1個 多個
應用場景 常使用在 critical section 只能有一個 thread 進入，而且要避免 priority inversion 的時候 常用在同步兩個 thread 或功能上面，因為 Semaphore 實際上使用的是 signal 的 up 與 down，讓 Semaphore 可以變成是一種 notification 的作用，例如 A thread 執行到某個地方時 B thread 才能繼續下去
priority inversion 無 有

並行和多執行緒程式設計-POSIX Thread

  • thread-local storage (tls): 給 thread 一個專屬的空間 (不和其他 thread 共享)

    • 例如可記錄 errno (error number)
    • 硬體協助
    • 無硬體協助

  • Native POSIX Thread Library (NPTL): 一對一

  • semophore

    • sysv semaphore
    • posix semaphore (現在系統, sem_ 開頭)

  • 用 semaphore 控制總量、 mutex 控制 mutual exclusion

  • 利用 Atomic Compare and Exchange 指令來實作 semaphore 和 mutex

    • atomic functions 分為 strong 和 weak : strong guarantee the success or failure while weak may fail

  • condition variables 範例

    • Threads sleeping inside a condition variable are woken up by calling pthread_cond_broadcast (wake up all) or pthread_cond_signal (wake up one)
    • Condition variables are always used with a mutex lock.

Before calling wait, the mutex lock must be locked and wait must be wrapped with a loop.

Tips: 如果 N 為二的冪， i % N 可以改成 (i++) & (N-1) bitwise 操作

2024q1 第 9 週測驗題

測驗 1

如何確保 fork 程式有東西可以合併?
mmap: 作業系統中讓多個行程存取同一個記憶體空間

int main(int argc, char **argv)
{
    rand_context_t r;
    rand_init(&r, (uintptr_t) &main ^ getpid());

    /* shared by forked processes */
    int *arr = mmap(NULL, N_ITEMS * sizeof(int), PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS, 0, 0);

    for (int i = 0; i < N_ITEMS; ++i)
        arr[i] = iabs((int) rand_next(&r));

    merge_sort(arr, N_ITEMS);

    for (int i = 1; i < N_ITEMS; ++i) {
        if (arr[i] < arr[i - 1]) {
            fprintf(stderr, "Ascending order is expected.\n");
            exit(1);
        }
    }
    printf("OK!\n");

    return 0;
}
  • sudo sysctl -w kernel.sched_child_runs_first=1，以便要求 Linux 排程器 (CFS) 讓 child process 優先於 parent process 執行
  • 遞迴時呼叫 fork 會更耗費成本
  • 如何改進此程式?
    • 避免使用遞迴，降低 fork 成本
    • 預先 fork (pre-forking)
  • copy_form_user 會有 cpu mode switch

測驗 2

  • ioctl : 和核心內裝置溝通
  • if page 太大， page fault 的成本會太大 (可參考 CS:APP ch9)

第十二周 5/9

多核處理器

  • 手機開機只先開一核作為管理者
  • WFI、WFE指令
  • work load 計算，會有 decay，因為最重要的資訊是當下資訊，越久之前的資料重要性越低
  • CPU Isolation: 開機時指定某一核不主動參與排程，除非使用 set affinity 將任務指定給該核

Pthread barrier: 讓快的 thread 等慢的 thread
time stamp counter (TSC): 可接露 CPU 週期數，只要 CPU 開著，周期數必為單調遞增

第 13 週

增加取餘數效率的小技巧:
如果是對 2 的冪取餘數， 等於對 2 的冪 - 1 做 &

  • 如: X % 16 = X & (16 - 1)
  • 所以可以將 ring buffer 的大小設定為 2 的冪

zero-copy

alignof c11

page alignment: 因為 page 是記憶體操作的最小單元，必須保證有 align，才能避免非預期結果

FUTEX_WAIT
FUTEX_WAKE

第十六周

在現代查表可能比 CPU 運算還慢約 50 倍，因此要避免查表
要學會懷疑、推理並做實驗驗證

面試要展現對公司的利益!

為何需要 boot loader?
因為 Linux kernel 太大，需要先初始化 DRAM。所以需要在 ROM 中初始化 SRAM，之後才能初始化 DRAM

image

millaker

SD/MMC

6/13

  • mmap 和 mmap2其實功能差不多，只是 mmap2是給系統實作用

  • 編譯器最佳化

    • constant propagation: 傳遞常數
    • constant folding: 先計算常數再展開
    • Static Single Assignment (SSA): 靜態單賦值，讓每個變數都只有出現過一次
      image

  • bitwise AND 和 logical AND比較
    logical AND 左側的 operator 是 false，右側的 operator 不會 evaluate (left-to-right evaluation)
    biteise AND 則會左、右側 operator都會 evaluate

  • Redis

    • 適合寫入少但讀取多的情境
    • in-memory cache
    • RCU
      • 讀多寫少的情境，可以做到 lock-free (只要執行足夠長的時間，至少會有一個執行緒會有進展)
Last changed by 
 
yuuu
0
89
Published on HackMD