# NCU Linux2024 Final Project Group 4

## 組員

李倬安 110403516
林晉宇 110403518
陳　立 110502552
許峻維 110504007

## 環境

Ubuntu 版本：

lsb_release -a
Distributor ID: Ubuntu
Description:    Ubuntu 24.04.1 LTS
Release:        24.04
Codename:       noble

kernel版本：

uname -a
Linux xxxx 6.12.5 #37 SMP PREEMPT_DYNAMIC Thu Dec 26 00:15:40 CST 2024 x86_64 x86_64 x86_64 GNU/Linux

核心數：

nproc
32

## wait queue實現

### 實現

#### system call 定義

使用 `SYSCALL_DEFINE1` 定義了一個新的 system call ：

SYSCALL_DEFINE1(wait_queue, int, id)
{
    switch (id){
    case 1:
        enter_wait_queue();
        break;
    case 2:
        clean_wait_queue();
        break;
    }
    return 0;
}

根據 `id` 的值， system call 要麼將 thread 添加到 wait queue，要麼喚醒 thread 。

#### 資料結構

- **wait queue head**：使用 `DECLARE_WAIT_QUEUE_HEAD` 宣告了一個 wait queue：

  wait_queue_head_t my_wait_queue;
  DECLARE_WAIT_QUEUE_HEAD(my_wait_queue);

- **spin lock**：用於保護變數 `cnt` 和 `condition`：

  static spinlock_t my_spinlock;

- **計數器**：

- `int cnt;` - 計算已進入 wait queue的 thread 數量。Initialized to be 0.
- `int condition;` - 用於控制何時喚醒 thread 。Initialized to be 0.

#### 函數：`enter_wait_queue`

此函數將 thread 添加到 wait queue：

static int enter_wait_queue(void)
{
    int id;
    spin_lock(&my_spinlock);
    id = cnt++;
    spin_unlock(&my_spinlock);

    printk(KERN_INFO "Thread %d is entering  wait queue\n", id);

    wait_event_interruptible(my_wait_queue, ({
        int ret;
        spin_lock(&my_spinlock);
        ret = (condition > id);
        spin_unlock(&my_spinlock);
        ret;
    }));

    printk(KERN_INFO "Thread %d is exiting  wait queue\n", id);

    return 0;
}

- **flow**：
1. 獲取 spin lock，以安全地增加 `cnt` 並為 thread 分配一個 `id`。
2. 釋放 spin lock。
3. 使用 `wait_event_interruptible` 使 thread 休眠，直到條件 `(condition > id)` 為真。
- 該條件確保 thread 按 FIFO 順序被喚醒。

#### 函數：`clean_wait_queue`

此函數喚醒 wait queue中的 thread ：

static int clean_wait_queue(void)
{
    printk(KERN_INFO "Starting to wake up threads...\n");
    
    while(condition < cnt){
        spin_lock(&my_spinlock);
        condition++;
        spin_unlock(&my_spinlock);

        wake_up_interruptible(&my_wait_queue);
        mdelay(50);
    }
    return 0;
}

- **流程**：
1. 印出一條訊息，喚醒過程的開始。
2. 在迴圈中，當 `condition` 小於 `cnt` 時，增加 `condition`。
- 這確保每個 thread 的等待條件 `(condition > id)` 按其 `id` 的順序依次為真。
3. 使用 `wake_up_interruptible` 喚醒 thread 。
4. 使用 `mdelay(50)` 引入一個小的延遲來控制喚醒的時間間隔。

### 使用者空間程式碼

在使用者空間程式中，使用 `syscall` 呼叫 `wait_queue` system call ：

void *enter_wait_queue(void *thread_id)
{
    int tid = *(int *)thread_id;
    printf("enter wait queue thread_id: %d\n", tid);
    syscall(wait_queue_syscall_number, 1);
    printf("exit wait queue thread_id: %d\n", tid);
    return NULL;
}

void clean_wait_queue()
{
    // printf("start clean queue ...\n");
    syscall(wait_queue_syscall_number, 2);
}

- **thread**：
- 每個 thread 呼叫 `enter_wait_queue`，它以 `id == 1` 呼叫 system call ，使其進入 wait queue。
- **主函數**：
- 建立多個 thread （例如，10 個 thread ）。
- 延遲一段時間後，呼叫 `clean_wait_queue` 喚醒 thread 。

### 執行結果

**樣本輸出：**


- thread 以與進入順序相同的順序退出 wait queue，驗證了 FIFO 行為。

## 解釋

### 確保 FIFO 順序

透過在 thread 進入 wait queue時為其分配一個遞增的 `id`，可以確保 thread 按相同的順序被喚醒。條件 `(condition > id)` 是一個判斷，使每個 thread 依次通過。

### 同步機制

- **spin lock**：
- 用於保護變數 `cnt` 和 `condition`。
- 確保atomic，防止多個 thread 同時存取共享資源時發生競爭。

- **wait queue**：
- `wait_event_interruptible` 使 thread 休眠，直到指定條件為真。
- `wake_up_interruptible` 喚醒在 wait queue上等待的 thread 。

### 其他考慮

- **競爭**：
- 如果沒有適當的同步，多個 thread 可能同時增加 `cnt`，導致 `id` 分配錯誤。
- 使用spin lock確保一次只有一個 thread 修改 `cnt` 或 `condition`。

- **喚醒時機**：
- 透過使用 `mdelay(50)` 在喚醒 thread 之間引入延遲，有助於輸出 FIFO 行為。

## 附錄

### 完整程式碼列表

#### 內核模組（`wait_queue.c`）

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/syscalls.h>
#include <linux/wait.h>
#include <linux/sched.h>
#include <linux/delay.h>
#include <linux/spinlock.h>

wait_queue_head_t my_wait_queue;
DECLARE_WAIT_QUEUE_HEAD(my_wait_queue);

static spinlock_t my_spinlock;
static int cnt = 0;
static int condition = 0;

SYSCALL_DEFINE1(wait_queue, int, id)
{
    switch (id){
    case 1:
        enter_wait_queue();
        break;
    case 2:
        clean_wait_queue();
        break;
    }
    return 0;
}

static int enter_wait_queue(void)
{
    int id;
    spin_lock(&my_spinlock);
    id = cnt++;
    spin_unlock(&my_spinlock);

    printk(KERN_INFO "Thread %d is entering wait queue\n", id);

    wait_event_interruptible(my_wait_queue, ({
        int ret;
        spin_lock(&my_spinlock);
        ret = (condition > id);
        spin_unlock(&my_spinlock);
        ret;
    }));

    printk(KERN_INFO "Thread %d is exiting wait queue\n", id);

    return 0;
}

static int clean_wait_queue(void)
{
    printk(KERN_INFO "Starting to wake up threads...\n");
    
    while(condition < cnt){
        spin_lock(&my_spinlock);
        condition++;
        spin_unlock(&my_spinlock);

        wake_up_interruptible(&my_wait_queue);
        mdelay(50);
    }
    return 0;
}

static int __init init_wait_queue_module(void)
{
    spin_lock_init(&my_spinlock);
    printk(KERN_INFO "wait queue Module Initialized\n");
    return 0;
}

static void __exit exit_wait_queue_module(void)
{
    printk(KERN_INFO "wait queue Module Exited\n");
}

module_init(init_wait_queue_module);
module_exit(exit_wait_queue_module);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("G4");
MODULE_DESCRIPTION("Custom wait queue Implementation");