# 初階 Process State 觀念


調度器可以切換Process狀態(Process State)。一個Linux Process從被建立到死亡，可能會經過多種狀態，如執行、暫停、可中斷睡眠、不可中斷睡眠、退出等。我們可以把Linux下眾多的 Process 狀態，歸納為三種基本狀態:

* 就緒(Ready) : Process 已經獲得了CPU以外的所有必要資源，如 Process 空間、網路連接等。一旦 Ready 狀態的 Prcess 等到 CPU ， 便可以立刻執行

* 執行(Running) : Process 獲得 CPU ，執行程序

* 阻塞(Blocked) : 當Process由於等待某事件而無法執行時，便會放棄CPU，進入阻塞狀態

:::spoiler {state="open"} 簡易版 Process state 過程
當Process被建立後，會自動變成就緒(Ready)狀態。如果 kernel 把 CPU 時間分配給該Process，則此Process會從就緒狀態轉換成執行狀態(Running)。在執行狀態下，Process執行指令。正在執行的Process可以主動進入阻塞狀態(Blocked)。

假設Process(執行狀態)需要將一部份硬碟中的資料讀取到內存(隨機存取記憶體:RAM)中。在這段讀取時間內，此Process不需要使用到CPU，便主動進入阻塞狀態(Blocked)，讓出CPU。當讀取結束後，計算機硬體發出信號，Process再從阻塞狀態恢復為就緒狀態。此外，Process也可能被迫進入阻塞狀態，例如接收到SIGSTOP信號。

排程器是CPU時間的管理員。Linux排程器主要負責兩件事 :

1. 選擇某些就緒的Process來執行

2. 打斷某些正在執行中的Process，讓他們變回就緒狀態

然而並不是所有的排程器都有第二個功能。有的排程器的狀態切換是單向的，只能讓就緒狀態的Process變為執行狀態，而不能把正在執行中的Process變回就緒狀態。支持雙向切換的排程器被稱為 preemptive 排程器。

當排程器讓一個Process變回就緒狀態時，就會立刻讓另一個就緒狀態的Procss開始執行。多個Process接替使用 CPU ，最大效率使用 CPU time。而當執行中的Process主動進入阻塞狀態，則排程器會選擇另一個就緒狀態的Process來利用 CPU time。

所謂的上下文交換(context switch)，又稱為環境切換，指 Process 在 CPU 中切換執行的過程。而Kernel承擔了上下文交換的任務，負責儲存和重建Process被切換掉之前的 CPU 狀態，進而讓 Process 感覺不到自己的執行被中斷。進而讓應用程序的開發者在編寫計算機程序時，不用專門寫代碼處理上下文交換!!

:::

# 完整 Process State 觀念
## 圖1 :

## 圖2 :


1. Linux 系統透過 ==fork()== 這個 system call 建立新的 process，當 process 被生出來後，他的狀態就是「執行中狀態」，也就是 ==TASK_RUNNING==(亦即上方的就緒狀態)

2. process 產生後，並不是馬上就能執行，必須被排程器(有的書會稱之為調度器)挑選後做 context switch 的動作，才能是「正在執行中」的 process

3. 我們以 ==current== 代表「正在執行中」的那一個 process，前面所謂的執行中狀態指的是被放在 task queue / run queue（OS 叫 **ready queue**）中的 process

4. 當 ==current== 正在執行時，很可能被其他 priority 更高的 process 搶奪執行權，這時 ==current== 就會被放回 **ready queue** 裡，這是因為 Linux 是一個可搶先（preemptive）排程的作業系統

5. 假設今天 ==current== 要存取硬體時，如果硬體裝置出現問題，發生無法讀寫資料的狀況，此時「Linux 驅動程式必須從 ==current== (狀態)轉換到 ==wait queue== (狀態)裡睡覺（等待）」

6. ==wait queue== 就是用來讓 ==current== 睡覺的 kernel API

7. Process 被放到 ==wait queue== 時的狀態為 **TASK_INTERRUPTIBLE** 或是 **TASK_UNINTERRUPTIBLE**

8. 這個時候因為我們的 process 在睡覺了（被放到 ==wait queue==），所以 scheduler 就會再由 **ready queue** 裡挑一個 process 來執行

9. ==wait queue== 裡的 process 怎麼辦？

:::spoiler {state="open"} wait queue 裡的 process 過程

9-1. 睡著的 process 必須被叫醒（**wake up**），這個動作一般是在 interrupt handler 裡做的

9-2. 當 process 被叫起來後，狀態再度切換成 ==TASK_RUNNING== 了，於是，又得到被 scheduler 挑選執行的權力了

### Process state 的定義可以在 include/linux/sched.h 裡找到（以下適用 2.6.24 版本以前）：

#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2

### Kernel 也提供了一個 API 可用來設定 current 的狀態：

set_current_state(state_value)

9-3. 在驅動程式裡手動變更 process state 的目的是為了將 process 放到 ==wait queue== 並達到 critical section 的效果

:::

# 初階 Wait Queue 觀念

* 可以使用Wait Queue來實現Process的阻塞(blocking)

* Wait Queue可以當成是保存Process的容器，當Process被blocking的時候，將該Process放入Wait Queue中

* 當Kernel喚醒Process時，從等待隊伍中取出Process

# 詳細 Wait Queue 觀念

* CPU 會調用就緒(Ready)隊伍，或者打斷執行(Running) Process，執行就緒隊伍

* 建立wait_queue_head與wait_queue，並使用wait event，當condition不滿足時，當前Proces進入wait queue裡

* 將當前Process加入至wait queue時，schedule會同時間去調用 CPU 去執行別的 Process ，使 CPU 不會再調用當前的Process

* 當收到wakeup後，將 wait queue 裡的 Process 加入至 run queue 或者就緒隊伍中，如果同時間內，某 condition 滿足時，下個阻塞狀態的Process將會被調用，反之，如 condition 未滿足時，則CPU繼續被調度走，不會執行當前的Process，並繼續阻塞!!

等待隊伍(wait queue)是一種基於資源狀態的Process管理機制，它可以使Process在資源不滿足的情況下處於休眠狀態，讓出 CPU 資源，而資源狀態滿足時叫醒Process，使其繼續進行業務的處理

等待隊伍(wait queue)用於==使Process等待某一特定的事件發生而不用頻繁的論詢==，Process 會在等待期間時處睡眠狀態，在等待的事件發生時，會由Kernel自動叫醒。

它是以雙向鏈接串列為基礎的資料結構，與 Process 的休眠喚醒機制緊密相連，是實現非同步事件通知、行程間通訊(IPC)、共享資源的訪問等技術的底層技術，雙向鏈接串列中的每一個節點都是類型為task_struct稱為進程描述福(Process descriptor)的結構。如完整版 wait queue 示意圖 :

:::spoiler {state="open"} 完整版 wait queue 示意圖
:::

:::spoiler {state="open"} 簡易版 wait queue 示意圖
簡易版 wait queue 示意圖 :

:::

:::spoiler {state="open"} 新增或移除wait queue 示意圖

新增或移除wait queue 示意圖 :


:::

# Wait Queue 步驟 :

## 可中斷與不可中斷阻塞函數
## wake_up_interruptible 與 wait_event_interruptible

# wait_event_interruptible 流程圖

### 等待队列的 定义 和 初始化 :

1. 定义等待队列

wait_queue_head_t my_queue

2. 初始化等待队列

init_waitqueue_head ( &my_queue )

3. 定义并初始化等待队列

DECLARE_WAIT_QUEUE_HEAD ( my_queue )

## 等待队列的 睡眠 wait_event_interruptible ：

* 有条件睡眠：

1. wait_event ( queue , condition ) :

当 condition ( 一个布尔表达式 ) 为真，立即返回；否则让进程进入 TASK_UNINTERRUPTIBLE 模式

睡眠，并挂在 queue 参数所指定的等待队列上

2. wait_event_interruptible ( queue , condition )

当 condition ( 一个布尔表达式 ) 为真，立即返回；否则让进程进入 TASK_INTERRUPTIBLE 模式

睡眠，并挂在 queue 参数所指定的等待队列上.

3. int wait_event_killable ( wait_queue_t queue , condition )

当 condition ( 一个布尔表达式 ) 为真，立即返回；否则让进程进入 TASK_KILLABLE 模式

睡眠，并挂在 queue 参数所指定的等待队列上.

* 無条件睡眠( 老版本，不建议使用 )：

1. sleep_on ( wait_queue_head_t *q )

让进程进入 不可中断 的睡眠，并把它放入等待队列 q.

2. interruptible_sleep_on ( wait_queue_head_t *q )

让进程进入 可中断 的睡眠，并把它放入等待队列 q.

## 等待队列中唤醒进程 wake_up ：

1. wake_up ( wait_queue_t *q )

从等待队列 q 中唤醒状态为 TASKUNINTERRUPTIBLE ，TASK_INTERRUPTIBLE ，TASK_KILLABLE

的所有进程.

2. wake_up_interruptible ( wait_queue_t *q )

从等待队列 q 中唤醒状态为 TASK_INTERRUPTIBLE 的进程.

## request_irq() : 申请使用IRQ並註冊中斷程序

int request_irq(unsigned int irq, irq_handler_t handler, unsigned long flags,
	    const char *devname, void *dev_id)

:::success
irq : 欲分配的中斷號碼(IRQ)

handler : 指向中斷處理函數的指標，該函數為callback function(回調函數)，當中斷發生時，系統會調用這個函數

flags : 中斷處理的標誌(bitmask)

:::info
#define IRQF_DISABLED 0x00000020 //中斷處理期間，禁止所有其他中斷
#define IRQF_SHARED 0x00000080
//多個設備共享一個中斷thread，共享的所有中斷都必須使用此標誌。如果使用共享中斷的話，request_irq函數的dev_id參數就是唯一區分他們的標誌
#define IRQF_PROBE_SHARED 0x00000100 //错序共享中断
#define __IRQF_TIMER 0x00000200 //作為定時器中斷
#define IRQF_PERCPU 0x00000400 //CPU中断
#define IRQF_NOBALANCING 0x00000800 //中断平衡使能
#define IRQF_IRQPOLL 0x00001000 //中断轮询检测，用于设备共享的中断
#define IRQF_ONESHOT 0x00002000 //将中断保持不可用状态，直到中断处理函数结束
#define IRQF_NO_SUSPEND 0x00004000 //挂起期间不让中断保持不可用状态

// 强制中断处于重新开始状态即使设置了IRQF_NO_SUSPEND状态
#define IRQF_FORCE_RESUME 0x00008000
#define IRQF_NO_THREAD 0x00010000 //不可中断线程状态
#define IRQF_EARLY_RESUME 0x00020000 //提前恢复IRQ而不是在设备恢复期间

#define IRQF_TIMER (__IRQF_TIMER | IRQF_NO_SUSPEND | IRQF_NO_THREAD) // 複合定義
:::
* IRQF_DISABLED : 中斷處理程序是快速處理程序，快速處理程序被調用時屏蔽所有中斷，慢速處理程序不屏蔽
* IRQF_SHARED : 多個設備共享中斷
* IRQF_SAMPLE_RANDOM: 對系統熵有貢獻，對系統獲取隨機數有好處。（這幾個flag是可以通過或的方式同時使用的）

dev_id: 被傳遞給handler function的參數
:::

irqflags是中斷處理的屬性，若設置了IRQF_DISABLED （老版本中的SA_INTERRUPT，本版zhon已經不支持了），則表示中斷處理程序是快速處理程序，快速處理程序被調用時屏蔽所有中斷，慢速處理程序不屏蔽；若設置了IRQF_SHARED （老版本中的SA_SHIRQ），則表示多個設備共享中斷，若設置了IRQF_SAMPLE_RANDOM（老版本中的SA_SAMPLE_RANDOM），表示對系統熵有貢獻，對系統獲取隨機數有好處。（這幾個flag是可以通過或的方式同時使用的）

devname設置中斷名稱，通常是設備驅動程序的名稱 在cat /proc/interrupts中可以看到此名稱。
dev_id在中斷共享時會用到，一般設置爲這個設備的設備結構體或者NULL。

request_irq()返回0表示成功，返回-INVAL表示中斷號無效或處理函數指針爲NULL，返回-EBUSY表示中斷已經被佔用且不能共享。

# 參考資料

> [调度器简介，以及Linux的调度策略](https://www.cnblogs.com/vamei/archive/2018/07/25/9364382.html)
> > [計算機概論(二)筆記1](https://blog.udn.com/ben168/131829806)
> > [Process State 與 Wait Queue](https://www.jollen.org/blog/2008/07/process_state_wait_queue.html)
> > [Preemptive Process Scheduling 觀念](https://www.jollen.org/blog/2006/11/_scheduler_running_process.html)
> > > [Linux驱动中的 wait_event_interruptible 与 wake_up_interruptible 深度理解](https://blog.pytool.com/language/clang/linux-wait_event_interruptible/)
> > > > [Linux内核之——等待队列wait queue](https://blog.csdn.net/weixin_44537992/article/details/105990158)
> > > > [Linux等待队列（Wait Queue）](https://www.cnblogs.com/hueyxu/p/13745029.html)
> > > > [Linux内核API request_threaded_irq](https://deepinout.com/linux-kernel-api/linux-kernel-api-irq-mechanism/linux-kernel-api-request_threaded_irq.html)
> > > > > > > > > > > [超詳細之 Process State 與 Wait Queue 概念](https://hackmd.io/@YiZjennnnn/process_scheduling)