ucore lab 6

OS ucore lab 6

練習零： 填寫已有實驗：

<pre mdtype="fences" cid="n88" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">復制以下文件 其中 proc.c 和 trap.c 需要進行修正
vmm.c trap.c default_pmm.c pmm.c proc.c swap_fifo.c
proc.c:
static struct proc_struct *alloc_proc(void) {
//初始化進程所屬就緒隊列
proc->rq = NULL;
//初始化就緒隊列指針
list_init(&(proc->run_link));
//初始化時間片
proc->time_slice = 0;
}
trap.c:
static void trap_dispatch(struct trapframe *tf) {
// 在時鐘中斷下添加以下幾行并去掉之前設置 進程需要調度標記
// 這個標記現(xiàn)在已經(jīng)被調度程序所使用了，不再需要自己控制
++ticks;
sched_class_proc_tick(current);
// current->need_resched = 1;
}</pre>

練習一：使用 Round Robin 調度算法（不需要編碼）

完成練習0后，建議大家比較一下（可用kdiff3等文件比較軟件）個人完成的lab5和練習0完成后的剛修改的lab6之間的區(qū)別，分析了解lab6采用RR調度算法后的執(zhí)行過程。執(zhí)行make grade，大部分測試用例應該通過。但執(zhí)行priority.c應該過不去。

請在實驗報告中完成

  • Q1： 請理解并分析sched_calss中各個函數(shù)指針的用法，并接合Round Robin 調度算法描ucore的調度執(zhí)行過程
  • Q2：請在實驗報告中簡要說明如何設計實現(xiàn)”多級反饋隊列調度算法“，給出概要設計，鼓勵給出詳細設計
  • Q1:

<pre mdtype="fences" cid="n76" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">// 初始化算法所需要的數(shù)據(jù)結構
static void RR_init(struct run_queue rq) {
list_init(&(rq->run_list));
rq->proc_num = 0;
}
/** 進程入隊:
將進程加入就緒隊列(不同的就緒隊列的時間片不同 也就是說有不同優(yōu)先級的就緒隊列)
在RR調度中,當進程時間片為0或因某種情況被阻塞，則將其加入到就緒隊列并將其時間片進行重置
***/
?
static void RR_enqueue(struct run_queue *rq, struct proc_struct proc) {
assert(list_empty(&(proc->run_link)));
list_add_before(&(rq->run_list), &(proc->run_link));
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 ++;
}
?
// 進程出隊：將進程從就緒隊列中刪去
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 --;
}
/挑選出下一個進程
占用處理機去運行
在 RR調度中 直接按照就緒隊列的順序輪詢
***/
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;
}
// 時鐘中斷時調用此函數(shù)
// 在RR調度中，每次調用都會減少當前進程時間片
static void RR_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
if (proc->time_slice > 0) {
proc->time_slice --;
}
if (proc->time_slice == 0) {
proc->need_resched = 1;
}
}
?</pre>

Round Robin 調度執(zhí)行過程：

<pre mdtype="fences" cid="n116" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">* 在ucore中調用調度器的主體函數(shù)（不包括init，proc_tick）的代碼僅存在在wakeup_proc和schedule，前者的作用在于將某一個指定進程放入可執(zhí)行進程隊列中，后者在于將當前執(zhí)行的進程放入可執(zhí)行隊列中，然后將隊列中選擇的下一個執(zhí)行的進程取出執(zhí)行；
?

  • 當需要將某一個進程加入就緒進程隊列中，則需要將這個進程的能夠使用的時間片進行初始化，然后將其插入到使用鏈表組織的隊列的對尾；這就是具體的Round-Robin enqueue函數(shù)的實現(xiàn)；
    ?

  • 當需要將某一個進程從就緒隊列中取出的時候，只需要將其直接刪除即可；
    ?

  • 當需要取出執(zhí)行的下一個進程的時候，只需要將就緒隊列的隊頭取出即可；
    ?

  • 每當出現(xiàn)一個時鐘中斷，則會將當前執(zhí)行的進程的剩余可執(zhí)行時間減1，一旦減到了0，則將其標記為可以被調度的，這樣在ISR中的后續(xù)部分就會調用schedule函數(shù)將這個進程切換出去</pre>

  • Q2：

    <pre mdtype="fences" cid="n139" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit;">在proc_struct中添加總共N個多級反饋隊列的入口，每個隊列都有著各自的優(yōu)先級，編號越大的隊列優(yōu)先級約低，并且優(yōu)先級越低的隊列上時間片的長度越大，為其上一個優(yōu)先級隊列的兩倍；并且在PCB中記錄當前進程所處的隊列的優(yōu)先級；
    處理調度算法初始化的時候需要同時對N個隊列進行初始化；
    在處理將進程加入到就緒進程集合的時候，觀察這個進程的時間片有沒有使用完，如果使用完了，就將所在隊列的優(yōu)先級調低，加入到優(yōu)先級低1級的隊列中去，如果沒有使用完時間片，則加入到當前優(yōu)先級的隊列中去；
    在同一個優(yōu)先級的隊列內使用時間片輪轉算法；
    在選擇下一個執(zhí)行的進程的時候，有限考慮高優(yōu)先級的隊列中是否存在任務，如果不存在才轉而尋找較低優(yōu)先級的隊列；（有可能導致饑餓）
    從就緒進程集合中刪除某一個進程就只需要在對應隊列中刪除即可；
    處理時間中斷的函數(shù)不需要改變；
    至此完成了多級反饋隊列調度算法的具體設計；
    ?</pre>

練習二: 實現(xiàn) Stride Scheduling 調度算法（需要編碼）

首先需要換掉RR調度器的實現(xiàn)，即用default_sched_stride_c覆蓋default_sched.c。然后根據(jù)此文件和后續(xù)文檔對Stride度器的相關描述，完成Stride調度算法的實現(xiàn)。

<pre mdtype="fences" cid="n156" lang="c#" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">proc.c:
static struct proc_struct *alloc_proc(void) {
proc->rq = NULL;
list_init(&(proc->run_link));
proc->time_slice = 0;
// 斜堆實現(xiàn)的 Priority Queue
proc->lab6_run_pool.parent = proc->lab6_run_pool.left = proc->lab6_run_pool.right = NULL;
// 優(yōu)先級 (和步進成反比)
proc->lab6_priority = 0;
// 步進值
proc->lab6_stride = 0;
}</pre>

<pre mdtype="fences" cid="n157" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">// 就是32位系統(tǒng)下int的最大值 2147483647

define BIG_STRIDE (((uint32_t)-1) / 2)

?
static void stride_init(struct run_queue *rq) {
list_init(&rq->run_list);
rq->lab6_run_pool = NULL;
rq->proc_num = 0;
}
//在將指定進程加入就緒隊列的時候，需要調用斜堆的插入函數(shù)將其插入到斜堆中，然后對時間片等信息進行更新
static void stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {
rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
if (proc->lab6_priority == 0) {
proc->lab6_priority = 1;
}
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;// 維護就緒隊列中進程的數(shù)量
}
?
//stride_dequeue：將指定進程從就緒隊列中刪除，只需要將該進程從斜堆中刪除掉
static void stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {
rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
--rq->proc_num;// 維護就緒隊列中的進程總數(shù)
}
//stride_pick_next: 選擇下一個要執(zhí)行的進程，根據(jù)stride算法，只需要選擇stride值最小的進程，即斜堆的根節(jié)點對應的進程
static struct proc_struct * stride_pick_next(struct run_queue *rq) {
if (rq->lab6_run_pool == NULL) {
return NULL;
}
// 斜堆的頂就是 stride 值最小的進程
struct proc_struct *p = le2proc(rq->lab6_run_pool, lab6_run_pool);
// 提前增加 stride 的值 因為在之后調度別的進程之前一定會執(zhí)行這么多
p->lab6_stride += BIG_STRIDE / p->lab6_priority;
return p;
}
//stride_proc_tick：每次時鐘中斷需要調用的函數(shù)，與RR算法中的實現(xiàn)沒有區(qū)別
static void stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
if (proc->time_slice == 0) {
proc->need_resched = 1;
} else {
--proc->time_slice;// 維護就緒隊列中的進程總數(shù)
}
}</pre>

實驗結果：

圖

參考鏈接

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容