uCore作業系統程式設計實驗手記（六）
- 實驗uCore程序排程的有關準備
-
- 排程時機和系統排程架構
- Round Robin時間片輪轉算法
- 程序切換的過程
- Lab6
-
- 使用 Round Robin 排程算法
- 實作 Stride Scheduling 排程算法
實驗uCore程序排程的有關準備
實驗四、實驗五是uCore作業系統與核心線程、使用者程序建立有關的内容。其實在前兩個實驗中，已經或多或少地接觸到了程序排程的内容，隻不過遇到時沒怎麼深究。實驗六的内容就是探索uCore作業系統的排程器，了解排程器的原理、實作，徹底弄懂程序切換的過程。首先還是先進行有關的準備，看有什麼資料結構和接口可用，然後看RR排程算法的實作機制，最後理清switch_to()函數的實作過程。
排程時機和系統排程架構
欲清除排程器的實作，首先要弄懂排程的時機。即什麼時候要/可以執行程序排程？系統核心可以被排程、搶占嗎？在uCore中，系統核心是不能被搶占的。但是這與響應中斷、甚至嵌套中斷并不沖突。這個系統核心不能被搶占的意思是，執行核心代碼時，不能排程去執行其他程序。但有的系統卻可以被搶占，這與要同步機制的支援。
話說回來，什麼時候要/可以執行程序排程？這裡列舉幾個：
1.中斷傳回時。這是比較典型的，是我記住的第一個程序排程時機。
2.請求的服務不能立刻得到而阻塞時。
3.程序主動放棄CPU使用權。
4.和排程算法有關，如被高優先級搶占、時間片用完時…
注意，在uCore中隻有使用者程序是可以在任意點被搶占的。
wakup_proc()函數、schedule()函數、run_timer_list()函數是uCore系統完成程序排程的3個核心函數，最重要的是schedule()函數。實驗指導書中指出，如果我們能夠讓這三個排程相關函數的實作與具體排程算法無關，那麼就可以認為ucore實作了一個與排程算法無關的排程架構。實際上，uCore系統定義排程器接口時，也是這麼考慮的。
wakeup_proc()函數其實完成了把一個就緒程序放入到就緒程序隊列中的工作，為此還調用了一個排程類接口函數sched_class_enqueue()，這使得wakeup_proc()的實作與具體排程算法無關。
run_timer_list()函數在每次timer中斷處理過程中被調用，進而可用來調用排程算法所需的timer時間事件感覺操作，調整相關程序的程序排程相關的屬性值。通過調用排程類接口函數sched_class_proc_tick()，使得此操作與具體排程算法無關。
schedule()函數完成了與排程架構和排程算法相關三件事情:把目前繼續占用CPU執行的運作程序放放入到就緒程序隊列中，從就緒程序隊列中選擇一個“合适”就緒程序，把這個“合适”的就緒程序從就緒程序隊列中摘除。通過調用三個排程類接口函數sched_class_enqueue()、sched_class_pick_next()、sched_class_enqueue() 來使得完成這三件事情與具體的排程算法無關。
可見，實作排程算法，最核心的就是實作以下的幾個函數（sched.c）：
sched_class_enqueue()
sched_class_dequeue()
sched_class_pick_next()
sched_class_proc_tick()
是以uCore系統定義了如下排程接口類，一目了然，上述“關鍵函數”最終都對應調用下述類中的函數（sched.h）：
struct sched_class {
// 排程器的名字
const char *name;
// 初始化運作隊列
void (*init) (struct run_queue *rq);
// 将程序 p 插入隊列 rq
void (*enqueue) (struct run_queue *rq, struct proc_struct *p);
// 将程序 p 從隊列 rq 中删除
void (*dequeue) (struct run_queue *rq, struct proc_struct *p);
// 傳回 運作隊列 中下一個可執行的程序
struct proc_struct* (*pick_next) (struct run_queue *rq);
// timetick 處理函數
void (*proc_tick)(struct run_queue* rq, struct proc_struct* p);
};
為與相應的接口配套，需要有合适的資料結構。在引入排程功能後，需要對程序描述符做适當的改進（proc.h）：
struct proc_struct {
// . . .
// 該程序是否需要排程，隻對目前程序有效
volatile bool need_resched;
// 該程序的排程連結清單結構，該結構内部的連接配接組成了 運作隊列 清單，見後說明
list_entry_t run_link;
// 該程序剩餘的時間片，隻對目前程序有效
int time_slice;
// 指向程序所在的運作隊列
struct run_queue *rq;
// round-robin 排程器并不會用到以下成員，實作stride算法時候用到
// 該程序在優先隊列中的節點，僅在 LAB6 使用，斜堆
skew_heap_entry_t lab6_run_pool;
// 該程序的排程優先級，僅在 LAB6 使用
uint32_t lab6_priority;
// 該程序的排程步進值，僅在 LAB6 使用
uint32_t lab6_stride;
};
通過資料結構 struct run_queue 來描述完整的 run_queue運作隊列（sched.h）：
struct run_queue {
//其運作隊列的哨兵結構，可以看作是隊列頭和尾
list_entry_t run_list;
//優先隊列形式的程序容器，隻在 LAB6 練習2中使用
skew_heap_entry_t *lab6_run_pool;
//表示其内部的程序總數
unsigned int proc_num;
//每個程序一輪占用的最多時間片
int max_time_slice;
};
在 ucore 架構中，運作隊列存儲的是目前可以排程的程序，是以，隻有狀态為runnable的程序才能夠進入運作隊列。目前正在運作的程序并不會在運作隊列中。
Round Robin時間片輪轉算法
關于RR算法的理論性的知識、優劣等，這裡不贅述。
這部分重點是看在系統代碼層面，如何實作了RR算法。上一小節，熟悉了系統定義的排程器接口。要實作RR排程算法，首先要執行個體化接口類：
struct sched_class default_sched_class = {
.name = "RR_scheduler",
.init = RR_init,
.enqueue = RR_enqueue,
.dequeue = RR_dequeue,
.pick_next = RR_pick_next,
.proc_tick = RR_proc_tick,
};
在sched.c的void sched_init(void)函數中，有：
static struct sched_class *sched_class;
sched_class = &default_sched_class;
當執行過初始化函數之後，系統排程類指針指向了RR算法的排程結構，RR算法開始生效。下面把上面提出的4個核心函數列出來看看RR是怎麼實作的。（default_sched.c）
//被sched_class_enqueue()所調用，執行“入隊”的功能
static void RR_enqueue(struct run_queue *rq, struct proc_struct *proc) {
assert(list_empty(&(proc->run_link)));
//rq->run_list是RR運作隊列的雙向鍊頭結點，proc->run_link是插入程序描述符的連結結構
list_add_before(&(rq->run_list), &(proc->run_link));
//time_slice是目前程序剩餘時間片，如果它為0或者超過了系統定義的最大值
if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) {
proc->time_slice = rq->max_time_slice;//目前時間片設定為時間片最大值
}
proc->rq = rq;//指向該程序所在的運作隊列
rq->proc_num ++;//運作隊列計數器的值+1
}
//被sched_class_dequeue()所調用，執行“出隊”的功能
static void RR_dequeue(struct run_queue *rq, struct proc_struct *proc) {
assert(!list_empty(&(proc->run_link)) && proc->rq == rq);
list_del_init(&(proc->run_link));//把程序在所在隊列中删除
rq->proc_num --;//運作隊列計數器的值-1
}
//被sched_class_pick_next()所調用，執行“選擇”的功能
static struct proc_struct * RR_pick_next(struct run_queue *rq) {
list_entry_t *le = list_next(&(rq->run_list));//選擇頭結點的下一個結點
if (le != &(rq->run_list)) {//如果這個下個結點不是頭結點，也就是運作隊列非空
return le2proc(le, run_link);//傳回該節點程序控制塊的指針
}
return NULL;//如果程序運作隊列為空，則傳回NULL
}
//被sched_class_proc_tick()所調用，執行“時間響應”的功能
static void RR_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
if (proc->time_slice > 0) {
proc->time_slice --;//如果時間片還大于0，則剩餘時間片-1
}
if (proc->time_slice == 0) {
proc->need_resched = 1;//如果時間片等于0，則需要排程标志位置1
}
}
以上即是RR時間片輪轉算法的基本實作。
程序切換的過程
這裡面不是讨論排程算法，而是弄懂把一個程序從處理機取下，換上另一個程序的實作細節，換句話說，就是弄懂switch_to()函數的細節。
其位于kern/process/switch.S：
.globl switch_to
switch_to: # switch_to(from, to)
//switch_to函數的原型是switch_to(from, to)
//from是原程序的PCB中的context指針，to是新程序的PCB中的上下文結構的指針
# save from's registers
//把原程序的context指針儲存在EAX中
movl 4(%esp), %eax # eax points to from
//調用switch_to()函數時，會把下一條指令位址EIP壓入棧中，現在把它彈出存在上下文中
popl 0(%eax) # save eip !popl
movl %esp, 4(%eax)//ESP入棧
movl %ebx, 8(%eax)//EBX入棧
movl %ecx, 12(%eax)//ECX入棧
movl %edx, 16(%eax)//EDX入棧
movl %esi, 20(%eax)//ESI入棧
movl %edi, 24(%eax)//EDI入棧
movl %ebp, 28(%eax)//EBP入棧
# restore to's registers
//把新程序的context指針儲存在EAX中，思考調用switch_to(from, to)時參數入棧順序
movl 4(%esp), %eax # not 8(%esp): popped return address already
# eax now points to to
movl 28(%eax), %ebp//按照自高址向低址順序逐個恢複上下文中的寄存器
movl 24(%eax), %edi
movl 20(%eax), %esi
movl 16(%eax), %edx
movl 12(%eax), %ecx
movl 8(%eax), %ebx
movl 4(%eax), %esp
//上下文context結構中的EIP存放着新程序即将要執行的下一指令的位址，先壓棧
pushl 0(%eax) # push eip
//伴随着一條ret指令，棧頂儲存的EIP值被傳入EIP寄存器，開始新程序執行
ret
以上就是switch_to(from, to)函數的具體工作過程。
那麼問題來了：
1.原程序在執行時那麼多寄存器怎麼切換時就儲存了這麼幾個寄存器？
答案是，原程序在被中斷後，進入排程程式。這個中斷的中斷幀儲存了目前現場幾乎的所有資訊（儲存于原程序的核心棧）。當下一次再被排程到時，它實行層層函數調用傳回，當傳回到中斷時，再把所有寄存器的内容恢複出來。
2.考慮新老程序的核心棧是怎樣切換的？
切換核心棧，就是正确切換新老程序的ESP。由上面的過程可以看出，ESP是被正确切換的，切換到新程序的ESP應該能夠正确執行新程序的中斷傳回，進而正确執行新程序的代碼。那問題又來了，程序切換了，程序頁目錄切換了沒有？新的ESP值能否正确尋址新程序的核心棧？答案是，當然切換了！在執行switch_to(from, to)函數之前剛好切換過。多說無益，看關鍵代碼（proc.c）：
void proc_run(struct proc_struct *proc) {
if (proc != current) {//如果下一個要排程上的程序不是目前程序，說明合法
bool intr_flag;
struct proc_struct *prev = current, *next = proc;//設定prev/next指針
local_intr_save(intr_flag);
{
current = proc;//設定current指針為新程序
//在任務狀态段中裝載新程序核心棧指針ESP0，注意不是ESP
load_esp0(next->kstack + KSTACKSIZE);
lcr3(next->cr3);//加載新程序的頁目錄CR3！！！此時，切換了頁表
switch_to(&(prev->context), &(next->context));//執行切換函數
}
local_intr_restore(intr_flag);
}
}
3.為什麼加載新程序的頁目錄不會影響到後面switch_to(from, to)函數的運作？不會導緻原程序prev -> context尋址失敗嗎？顯然不會，不同程序不同的地方在于使用者程序的位址空間。而程序控制塊PCB位于系統核心空間，使用虛位址可以在任何使用者程序頁目錄中正确對他們尋址。
Lab6
終于進入程序管理的最後一個實驗了，回想起來還是弄清楚了很多東西，先高興3秒…
下面開始實驗六。從這個實驗開始，我不能再手動合并實驗代碼了，否則能累死。看來，無論幹什麼，都得效率放在最前頭！為提升效率而學習新東西都不是無用的。
我選擇用meld。這個軟體還沒有完全使用順手。。。待繼續熟悉。
還有一個老師在視訊中用到的，查找關鍵字在檔案夾的檔案中的位置（shell指令）：
使用 Round Robin 排程算法
由于RR時間片輪轉的算法實作在前面已經結合源碼做了分析，這裡就不重複。
下面回答問題：簡要說明如何設計實作”多級回報隊列排程算法“。
答：從原理上出發，該算法是有多個隊列，每個隊列都有不同的優先級。高優先級的隊列，時間片比較短，低優先級的隊列時間片比較長，不同的隊列時間片成2^n關系。當一個程序處于所在的優先級，并且被排程後：如果在所配置設定的時間片内執行完，那麼程序正常結束；如果在時間片内沒有執行完，那麼就在該隊列取下程序，放在更低一優先級的隊尾；最後一個隊列采用FCFS方法。任務到來時，首先進入高優先級隊列等待排程。同時，新任務可以搶占目前執行的低優先級任務。
可見，不同優先級之間采取優先級排程，同一優先級采取先來先服務、時間片輪轉的排程政策。其好處是，兼顧了優先級和時間片輪轉的優點，既能使高優先級的程序得到響應又可使短程序任務迅速完成。當隻有一個隊列時，算法退化為FCFS算法。
從實作上看，運作隊列是一個含有多個不同優先級的隊列的集合。可以用向量實作給定數目的優先級，向量中的元素是指定優先級隊列的頭結點（指針）。然後實作出隊、入隊、選擇和時間響應等4個“核心函數”。這裡PCB中的priority優先級随着被排程動态修改。
實作 Stride Scheduling 排程算法
這是本次實驗的重點内容。Stride Scheduling排程算法原理略。
首先，需要對程序PCB做什麼改進？其實系統已經為我們明确了。
struct proc_struct {
// . . .
// round-robin 排程器并不會用到以下成員，實作stride算法時候用到
// 該程序在優先隊列中的節點，僅在 LAB6 使用，斜堆
skew_heap_entry_t lab6_run_pool;
// 該程序的排程優先級，僅在 LAB6 使用
uint32_t lab6_priority;
// 該程序的排程步進值，僅在 LAB6 使用
uint32_t lab6_stride;
其次，運作隊列run_queue怎麼改進？
struct run_queue {
//其運作隊列的哨兵結構，可以看作是隊列頭和尾，本算法中不用
list_entry_t run_list;
//優先隊列形式的程序容器，隻在 LAB6 練習2中使用，本算法中使用
skew_heap_entry_t *lab6_run_pool;
//表示其内部的程序總數
unsigned int proc_num;
//每個程序一輪占用的最多時間片
int max_time_slice;
};
最後，就是實作Stride Scheduling排程算法的“核心函數”了。先執行個體化一個排程類：
//kern/process/default_sched.c
struct sched_class default_sched_class = {
.name = "stride_scheduler",
.init = stride_init,
.enqueue = stride_enqueue,
.dequeue = stride_dequeue,
.pick_next = stride_pick_next,
.proc_tick = stride_proc_tick,
};
然後針對新算法初始化運作隊列run_queue，重寫stride_init()函數：
static void stride_init(struct run_queue *rq) {
/* LAB6: YOUR CODE */
list_init(&(rq->run_list));//針對連結清單組織方式的初始化
rq->lab6_run_pool = NULL;//針對斜堆組織方式的初始化
//如果優先隊列為空，則其指向空指針（NULL）
rq->proc_num = 0;//程序計數初始化為0
}
最後是，4個“核心函數”，如下：
//被sched_class_enqueue()所調用，執行“入隊”的功能
static void stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {
/* LAB6: YOUR CODE */
//下面是參考答案的代碼，我先把它貼出來了，因為這個代碼充分考慮了兩種情況
//即使用連結清單實作運作隊列和斜堆實作運作隊列，具體使用哪一個，在編譯時
//使用條件編譯可以自由選擇，這種編譯時多選的情況很關鍵，應該掌握并運用
#if USE_SKEW_HEAP//如果定義了USE_SKEW_HEAP宏，就使用斜堆的代碼
rq->lab6_run_pool =
skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);//調用預定義的斜堆插入函數，向斜堆運作隊列中插入一個節點
#else//否則，就使用連結清單實作運作隊列的代碼
assert(list_empty(&(proc->run_link)));
list_add_before(&(rq->run_list), &(proc->run_link));//向連結清單最後插入一個節點
#endif//條件編譯結束
//如果目前程序剩餘時間片為0，或者大于系統最大時間片的值
if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) {
proc->time_slice = rq->max_time_slice;//就把目前程序的時間片重設為最大時間片
}
proc->rq = rq;//設定目前程序所在的優先隊列指針指向rq
rq->proc_num ++;//運作隊列中程序計數器+1
}
//被sched_class_dequeue()所調用，執行“出隊”的功能
static void stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {
/* LAB6: YOUR CODE */
#if USE_SKEW_HEAP//如果定義了USE_SKEW_HEAP宏，就使用斜堆的代碼
rq->lab6_run_pool =
skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);//調用預定義的斜堆删除函數，從斜堆運作隊列中删除指定節點
#else//否則，就使用連結清單實作運作隊列的代碼
assert(!list_empty(&(proc->run_link)) && proc->rq == rq);
list_del_init(&(proc->run_link));//從連結清單運作隊列中删除該節點（即取消指針的連結）
#endif//條件編譯結束
rq->proc_num --;//運作隊列中程序計數器-1
}
//被sched_class_pick_next()所調用，執行“選擇”的功能
static struct proc_struct * stride_pick_next(struct run_queue *rq) {
/* LAB6: YOUR CODE */
#if USE_SKEW_HEAP//如果定義了USE_SKEW_HEAP宏，就使用斜堆的代碼，從這裡可以看出斜堆優勢
if (rq->lab6_run_pool == NULL) return NULL;//如果斜堆為空，則傳回NULL
//否則，斜堆頂端的元素就是要取的元素，反查其PCB指針，并用指針p傳回
struct proc_struct *p = le2proc(rq->lab6_run_pool, lab6_run_pool);
#else//否則，就使用連結清單實作運作隊列的代碼
list_entry_t *le = list_next(&(rq->run_list));//首先擷取連結清單的第一個節點
if (le == &rq->run_list)//如果，該節點指向了rq->run_list，說明連結清單是空的，傳回NULL
return NULL;
//以下到endif實際上是一個通過周遊實作的簡單比較算法
struct proc_struct *p = le2proc(le, run_link);//讓p指向連結清單的第一個節點的PCB
le = list_next(le);//le指針後移一個節點
while (le != &rq->run_list)//隻要沒有到哨兵節點rq->run_list，就循環
{
struct proc_struct *q = le2proc(le, run_link);//讓q指向連結清單的第2個節點的PCB
if ((int32_t)(p->lab6_stride - q->lab6_stride) > 0)//若p所指程序步長大于q的
p = q;//p就指向q的程序
le = list_next(le);//然後，q後移一位，重新指向一個PCB
//可以看出，q是一個遊标，向後周遊所有PCB，而p始終指向目前的最小步長程序
}
#endif
if (p->lab6_priority == 0)//優先級如果為0，則程序步長+BIG_STRIDE
p->lab6_stride += BIG_STRIDE;
//否則程序步長+BIG_STRIDE / p->lab6_priority;
else p->lab6_stride += BIG_STRIDE / p->lab6_priority;
return p;//傳回標明的p（程序PCB指針）
}
//被sched_class_proc_tick()所調用，執行“時間響應”的功能
static void stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
/* LAB6: YOUR CODE */
if (proc->time_slice > 0) {//如果程序剩餘時間片還沒用完，則-1即可
proc->time_slice --;
}
if (proc->time_slice == 0) {//如果程序剩餘時間片用完，則需要排程标志位置1
proc->need_resched = 1;
}
}
以上就是4個所謂的“關鍵核心函數”，我幾乎照着答案搬過來了。
另外，uCore中BIG_STRIDE是這樣定義的：
為什麼這樣定義呢？保證stride屬性的不會溢出，或者說讓計算的結果仍然反應正确的值。在uCore中，stride用32位無符号整數表示。計算比較時，計算結果用帶符号整數表示仍得到正确的值。要達到這個目的，需要正确設定BIG_STRIDE的範圍。我們要保證任意兩個 Stride 之差都會在機器整數表示的範圍之内：因為stride單次加的值不超過BIG_STRIDE（規定優先權大于1），是以比較時計算兩個stride的差也不會超過BIG_STRIDE的範圍。在32位整數中，把最高一位做符号位，其餘31位表示BIG_STRIDE，當他們全1時是BIG_STRIDE可以的最大值。假設按照無符号加法，某一數值較大的stride發生了回卷，變成了0x000000FE，而原來stride較小的還沒有達到上限0xFFFFFFFF，現在是0xFFFFFCDE。想在把他們看作是帶符号減法比較，一個正數減去一個負數，仍然為整數，這個符号結果仍是正确的。但是，如果單次加減的stride值超過了0x7FFFFFFF，就會導緻所謂的數值較大的stride在有符号數表示下為負數，進而得出相反的結果！是以，32位下，這個BIG_STRIDE不能超過0x7FFFFFFF。
本次實驗六結束。
2019-07-29 09:05
![Win10系統怎麼開啟Linux Bash指令行？[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)