2024 Fall NCU Linux OS Project 2
Link : Project2.pdf , github , hackmd , DEMO
Environment
以下為kernel space code
wait queue node
my_wait_queue
中的一個節點,每個節點對應一個process,裡面存了:
list_head list
:使用 list_head
(Circular doubly linked list)將所有等待的process接在一起。task_struct *task
: 每個process 指向自己的 process descriptorglobal var.
my_wait_queue
: 使用 LIST_HEAD
定義了一個空的circularly doubly linked list,作為head node of wait queue。queue_lock
:使用 spinlock_t
定義一個spin lock,用於保護multi-threads對 my_wait_queue
的操作,防止race condition。
my_wait_queue
,同時間只會有一個thread 在操作,包含 delete, add 都不能同時間執行enter_wait_queue
spin_lock
保護list_add_tail
,同時間只會有一個node 加入 my_wait_queue
,確保不會出現race condition。list_add_tail
將節點加入queue尾部。TASK_INTERRUPTIBLE
,並使用 schedule()
將當前process 設為睡眠,直到呼叫 wake_up_process
才可以離開wait queue。記得 schedule();
要加在spinlock之外,
否則在 critical region 中使用 schedule();
會使 process 占用 lock 不放,導致deadlock 發生
clean_wait_queue
list_for_each_entry_safe
遍歷wait queue
list_del
從queue中移除節點。wake_up_process
喚醒process。這邊加入 msleep(100)
因為在user space 中印出的順序受到multi-thread的影響可能會亂掉
因此即使kernel space 的wait queue已經確保是FIFO的順序移除,但是在User space I/O 卻無法保證照順序印出,
所以在wake_up_process
之後加上睡眠100ms,讓user space 有時間可以印出資訊而不被多執行緒打亂
list_head
可以看到這是一個 Circular doubly linked list , 也就是我們要用來儲存wait queue的資料結構,
將linked list的 next 和 prev 都指向變數 name 本身,形成一個空的環狀雙向鏈表。
也就是說,使用 LIST_HEAD
就定義了一個空的雙向鏈表,作為等待Queue的head節點。
list_add_tail
head
是circular linked list的 head節點head->prev
獲取尾節點,並將新節點插入到尾節點和頭節點之間,也就是加入linked list最後面。__list_add
中,其實就是將new
插入到prev
和next
當中,透過4個操作:
next->prev = new
和 new->next = next
new->prev = prev
和 prev->next = new
圖例:
list_del
list_head
)中刪除指定的節點。
next->prev = prev
及 prev->next = next
達到delete nodeLIST_POISON1
及 LIST_POISON2
明確標記已刪除的節點,便於檢測誤用圖例:
list_for_each_entry_safe
pos
保存當前節點,n
保存pos
的下一個節點(通常用存放在tmp
)。n
確保當前節點(pos
)刪除後,仍然能獲取下一個節點的地址。pos
後,會透過 pos=n
及 n=list_next_entry()
一棟到下一個node,因此可以確保刪除的正確性.wait_queue.c
User space result:
透過原本的User space code for迴圈中 i
值以及真正的thread id來檢查,
進入wait queue以及離開wait queue的順序是保持FIFO
Kernel space result:
此區塊會初始化變數
6:
首先將用於wait_event()
判斷process是否擁有所需的資源的condition
變數設為0(告訴wait_event目前process無法取得所需資源,需要進行wait)。
7:
透過DECLARE_WAIT_QUEUE_HEAD()
來建立一個作為全域變數的wait queue head實例:my_wait_queue
。
8:
DEFINE一個static的Mutex lock實例:my_wait_queue_lock
。
11:
將condition
設回0以確保想加入wait queue的process能夠正確進入wait狀態。
12:
透過wait.h
中的DECLARE_WAITQUEUE()
macro來建立一個新的wait queue entry。
13:
加鎖以確保進行add_wait_queue()
操作時不會有競爭條件 (Race Condition)的情況發生。
14:
透過wait.h
中的function add_wait_queue_exclusive()
來將process加入wait queue。之所以會選擇exclusive加入的原因一方面是讓之後可以直接使用wake_up()
就可以每次叫醒一個process進行執行(減少規定不能改動的user space code中printf順序出錯的機率),另一方面是考量add_wait_queue_exclusive()
本身會將要進入wait_queue的process串接在wait_queue最後方的性質,正好符合這次題目FIFO的需求。
17:
透過同樣於wait.h
中的functionwait_event_exclusive_cmd()
來讓process進入wait狀態(因為沒有所需資源(condition=0),故讓process wait),而最後面的兩個cmd分別會於process開始wait前;process被叫醒時執行,這裡設定於開始wait前將mutex lock解鎖,並於被叫醒後嘗試獲得mutex lock。 當process進入wait狀態後實際上被暫停在這行
18:
當process被叫醒後會由這行繼續執行(得到mutex lock後)。
19:
透過wait.h
中的function remove_wait_queue()
將process由wait queue中移除。
20~23:
讓此process檢查,假設waitqueue中還有其他在wait的process,就將其叫醒(同樣是應對題目不可修改的Userspace code中printf順續亂掉的問題)。
24:
在此被叫醒的process返回userspace繼續執行前將mutex lock解鎖讓剛剛wake_up()的其他process可以開始執行。
此function內的實作與上方enter_wait_queue()
中負責叫醒其他process的19~24
行相同,主要用於叫醒第一個process。