## Linux Project 2
<!-- [toc] -->
:::info
#### 組長：
- 111504512 賴詠文
#### 組員：
- 111504507 黃子銘
- 109401553 楊雲杰
- 111504008 郭奕宏
:::
### 題目
#### Wait Queue
- A Wait Queue is a synchronization mechanism in the Linux kernel used to put processes to sleep while waiting for a specific condition to be met. Once the condition is satisfied, the processes are awakened. It is commonly used to avoid busy-waiting, thereby improving system efficiency.
Under normal circumstances, a function using a wait queue must know the name or the pointer of the wait queue. This is because a wait queue is represented as a variable (usually of type wait_queue_head_t ), and the function needs the address of this variable to perform operations.
> In this lab, you need to implement a custom wait queue-like functionality in kernel space, allowing user applications to operate through the system call.
#### output example
The target output is as follows: threads exit the wait queue in FIFO order.
```
enter wait queue thread_id: 0
enter wait queue thread_id: 1
enter wait queue thread_id: 2
enter wait queue thread_id: 6
enter wait queue thread_id: 7
enter wait queue thread_id: 8
enter wait queue thread_id: 9
enter wait queue thread_id: 5
enter wait queue thread_id: 3
enter wait queue thread_id: 4
start clean queue ...
exit wait queue thread_id: 0
exit wait queue thread_id: 1
exit wait queue thread_id: 2
exit wait queue thread_id: 6
exit wait queue thread_id: 7
exit wait queue thread_id: 8
exit wait queue thread_id: 9
exit wait queue thread_id: 5
exit wait queue thread_id: 3
exit wait queue thread_id: 4
```
### 助教給的 Base Code
:::spoiler User Space
```c
// Except for syscall(xxx, 1); and syscall(yyy, 2); , please do not modify any other parts of the code.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/syscall.h>
#define NUM_THREADS 10
void *enter_wait_queue(void *thread_id)
{
fprintf(stderr, "enter wait queue thread_id: %d\n",
*(int *)thread_id);
/*
// your syscall here
syscall( xxx , 1);
*/
fprintf(stderr, "exit wait queue thread_id: %d\n",
*(int *)thread_id);
}
void *clean_wait_queue()
{
/*
// your syscall here
syscall( xxx , 2);
*/
}
int main()
{
void *ret;
pthread_t id[NUM_THREADS];
int thread_args[NUM_THREADS];
for (int i = 0; i < NUM_THREADS; i++)
{
thread_args[i] = i;
pthread_create(&id[i], NULL, enter_wait_queue,
(void *)&thread_args[i]);
}
sleep(1);
fprintf(stderr, "start clean queue ...\n");
clean_wait_queue();
for (int i = 0; i < NUM_THREADS; i++)
{
pthread_join(id[i], &ret);
}
return 0;
}
```
:::
:::spoiler Kernel Space
```c
// Here is a program example. You are free to modify the contents of this file as needed.
static int enter_wait_queue(void)
{
return 0;
}
static int clean_wait_queue(void)
{
return 0;
}
SYSCALL_DEFINE1(call_wait_queue, int, id)
{
switch (id){
case 1:
enter_wait_queue()
break;
case 2:
clean_wait_queue();
break;
}
return 0;
}
```
:::
### 環境
### 目標
- 實作一個自定義 wait queue，讓 user 可以透過呼叫 system call 時，帶不同參數決定是要把當前 thread 丟進 自定義 wait queue 中還是把自定義 wait queue 中的全部 thread 喚醒
- 喚醒的順序需要是 FIFO
<!-- > 因為 linux 中沒有 thread 概念，是用 process 透過相同 id 以及共享記憶體等方式模擬 thread，所以本篇不會特別區分 thread 和 process -->
### 觀念介紹
- 以下是 wait queue 在 linux kernel 中的結構
- 使用 circular doubly linked list 結構儲存每個在 wait queue 中的 thread
- 第一個 node 是 wait queue 的 head，不代表任何 thread
- 當 wait queue 為空時，`next` 和 `prev` 會指向自己
- flags
- 0 (non-exclusive)：被喚醒時會繼續喚醒 queue 中的下一個 node
- 1 (exclusive)：被喚醒時不會順便叫下一個一起起床
- 通常同一個 queue 每個 node 的 flag 都會一樣
### 實作 (Kernel Space)
1. 定義一個 wait queue head 名稱為 `my_wait_queue`
```c
DECLARE_WAIT_QUEUE_HEAD(my_wait_queue);
```
- DECLARE_WAIT_QUEUE_HEAD 在 linux kernel 中的定義如下，會幫我們初始化好一個 wait queue 的 head，我們只需要提供變數名稱即可
2. 定義 enter_wait_queue()
- 把 thread 加入 wait queue
```c
no_wait = 0; // resource 沒拿到 (全域變數)
ret = wait_event_interruptible_exclusive(my_wait_queue, no_wait);
```
- 把 no_wait 設為 0，表示 resource 還沒拿到，我要睡覺。即使被叫起，`no_wait=0` 依然會繼續睡（起床重睡！，`___wait_event` for 迴圈在做的事）
- 0 表示資源尚未取得，執行緒需要進入等待。
1 表示資源已經取得，可以喚醒所有等待的執行緒。
- `wait_event_interruptible_exclusive` 定義如下，最終會呼叫 `___wait_event`
- exclusive 會將 node enqueue 到最後面；non-exclusive 則相反。dequeue 時則固定會從第一個開始取出，所以用 exclusive 才會有 FIFO 的效果
- interruptible 則不影響結果，因為我們不會用 signal 去喚醒他 (我覺得，還沒驗證)
- condition 代表要 wait 的資源是否取得，因為我們要讓他一直待在 wait queue 中直到我們把它叫醒(`___wait_event` for 迴圈會一直檢查)，所以設為 0 (false)
- 
- 
3. 定義 clean_wait_queue()
- 把 wait queue 中的 node 依照 FIFO 取出
- 透過 while 迴圈檢查 wait queue 是否為空 (head 有沒有指向自己)，然後就一直 dequeue wait queue 中最前面的 node 直到沒有其他 node
- no_wait 設為 1，表示不會再起床重睡了
- msleep：linux kernel 中使用的 sleep，因為在執行這個 syscall 的時候可能會在同一個 CPU 時間片段同時 wake up queue 中的很多 thread 進入 run queue 競爭 CPU 時間片段，這樣執行的順序可能會變，所以應該用 sleep 確保 wake up 的 thread 會先在 CPU 執行，再 wake 下一個 thread。
<!-- - msleep：linux kernel 中使用的 sleep，確保 user mode 有足夠的時間輸出 `exit wait queue thread_id: ?` 再叫醒下一個 node。 -->
```c
no_wait = 1; // resource 拿到了
while(my_wait_queue.head.next != &my_wait_queue.head)
{
wake_up_interruptible(&my_wait_queue);
msleep(100);
}
```
- `wake_up_interruptible` 定義如下，對應到 `enter_wait_queue()` 中的 `wait_event_interruptible_exclusive` 就是喚醒 node
- 
- 
- 
- 
### 實作 (User Space)
- 助教給的 sample code 裡面的 syscall number 改成你在 `/usr/src/linux-5.15.137/arch/x86/entry/syscalls/syscall_64.tbl` 中設定的數字即可，以我自己為例是 `451`
- 
### final code (Kernel Space)
```c
#include <linux/kernel.h>
#include <linux/syscalls.h>
#include <linux/wait.h>
#include <linux/delay.h>
DECLARE_WAIT_QUEUE_HEAD(my_wait_queue);
int no_wait = 0;
static int enter_wait_queue(void)
{
int ret;
no_wait = 0; // resource 沒拿到 (全域變數)
ret = wait_event_interruptible_exclusive(my_wait_queue, no_wait);
printk("enter wait queue return = %d\n", ret);
if(ret) return 0;
return 1;
}
static int clean_wait_queue(void)
{
no_wait = 1; // resource 拿到了
while(my_wait_queue.head.next != &my_wait_queue.head)
{
wake_up_interruptible(&my_wait_queue);
msleep(100);
}
return 1;
}
SYSCALL_DEFINE1(call_my_wait_queue, int, id)
{
switch (id){
case 1:
enter_wait_queue();
break;
case 2:
clean_wait_queue();
break;
}
return 0;
}
```
### final code (User Space)
```c
// Except for syscall(xxx, 1); and syscall(yyy, 2); , please do not modify any other parts of the code.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/syscall.h>
#define NUM_THREADS 10
void *enter_wait_queue(void *thread_id)
{
fprintf(stderr, "enter wait queue thread_id: %d\n", *(int *)thread_id);
syscall(451 , 1);
fprintf(stderr, "exit wait queue thread_id: %d\n", *(int *)thread_id);
}
void *clean_wait_queue()
{
syscall(451 , 2);
}
int main()
{
void *ret;
pthread_t id[NUM_THREADS];
int thread_args[NUM_THREADS];
for (int i = 0; i < NUM_THREADS; i++)
{
thread_args[i] = i;
pthread_create(&id[i], NULL, enter_wait_queue,
(void *)&thread_args[i]);
}
sleep(1);
fprintf(stderr, "start clean queue ...\n");
clean_wait_queue();
for (int i = 0; i < NUM_THREADS; i++)
{
pthread_join(id[i], &ret);
}
return 0;
}
```
### 設定syscall相關檔案 & 編譯 kernel
- 我是參考這邊的教學 https://hackmd.io/aist49C9R46-vaBIlP3LDA
<!-- 1. `cd /usr/src/linux-5.15.137/`
2. `sudo make localmodconfig`
- 這邊會跳出一大堆問你要不要裝的套件,全部按enter跳過就好
- 抓 kernel 需要編譯的部分(有更動的部分)進去 config 檔中，以減少編譯需要的時間，動的東西越多，需要編譯越久
3. `nproc`
- 查看虛擬機中有多少核可以用
4. `sudo make -jn`
- n替換為你想用多少核一起編譯，通常抓 1/2~3/4
5. 懶得寫 -->
### 輸出結果
完成！！因為是多執行緒所以 enter 的順序會是 random，但是因為是 FIFO 加上我 dequeue 有 sleep，所以 exit 會是跟 enter 一樣的順序
### 參考資料
- [許富皓教授的 wait queue 投影片](https://view.officeapps.live.com/op/view.aspx?src=https%3A%2F%2Fstaff.csie.ncu.edu.tw%2Fhsufh%2FCOURSES%2FFALL2024%2FlinuxLecture_3_9-8.ppt&wdOrigin=BROWSELINK)
- [bootlin linux source code](https://elixir.bootlin.com/linux/v5.15.137/source/kernel/sched/wait.h)
- [設定&編譯 linux kernel](https://hackmd.io/aist49C9R46-vaBIlP3LDA)
- [sleep in linux kernel](https://blog.csdn.net/q28292929/article/details/127665877)
Sign in with Wallet
Connect another wallet