OS-實現一個RR調度算法

原理

RR調度相比于FCFS要公平一點，RR為每一個任務分配了一段固定的時間片（timeslice），當這個任務消耗完分配的時間片后，就會切換到下一個任務進行調度，這樣相同優先級的任務都能夠得倒相對公平的調度機會。在RR調度中就是timeslice的大小的劃分，太大就退化成了FCFS，太小會引起過多的上下文切換，無味的消耗CPU是很浪費的。

什么是timeslice？
OS會使用一個timer來定時發生中斷，timer的定時周期就是timeslice，比如說我們設定timer interval為1ms，也就是1ms會發生一次中斷，發生中斷后，調度器會切換到下一個任務去運行，那每個任務的timeslice就是1ms，也就是這個任務在一次調度循環中，最多只能運行1ms，就必須切換出去，當然你的任務也可能運行不到1ms就切換到下一個任務，這時候觸發切換就是可能是（放棄CPU資源/被更高優先級搶占）。

什么時候會發生調度？

• 主動放棄cpu資源（sleep/suspend）
• 被動放棄cpu資源（mutex/semaphore）
• 被更高優先級任務搶占
• 時間片耗盡

擴展數據結構

相比于FIFO我們增加了timeslice來作為任務切換的一個發起點

typedef struct tcb {struct list_head link_head;time64_t readytime;uint32_t timeslice; } tcb_t;

schedule流程

調度流程圖

相比于FIFO，我們只是增加了一個schedule的調用時機

線性查找法

偽代碼

void schedule(void) {tcb_t *cur_task = current();tcb_t *task = NULL;tcb_t *task_tmp = NULL;sched_queue_t *ready_queue = NULL;for (int i = 0; i < CONFIG_MAX_TASK_PRIORITY; i++){/* 按照優先級由高到低依次查找就緒隊列 */if (!list_empty(&g_readytorun[i].tasks_head)){/** 找到不為空的對應優先級隊列* 找到的第一個就是優先級最高的隊列（默認優先級數值越低優先級越高）*/ready_queue = &g_readytorun[i];int64_t remain = clock_systime_ticks() - task->readytime;/* 判斷任務是否到達了調度時間 */if (remain >= 0){list_for_each_entry_safe(task, task_tmp, &ready_queue->tasks_head, link_head){if (cur_task != task){list_del_init(&task->link_head);list_add_tail(&task->link_head, &ready_queue->tasks_head);task_switch(task);goto out;}}}}} out: }

時間復雜度

RR的時間復雜度和FIFO一樣，因為采用的都是線性查找算法，下一章我們將采用位圖查找來優化我們時間復雜度，使得最后可以達到O(1)

總結

以上是生活随笔為你收集整理的OS-实现一个RR调度算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。