--- # System prepended metadata title: shed.c 註解 --- # shed.c 註解 ## 一些define #define _GNU_SOURCE #include #include #include #include #include #include "rbtree.h" #include "context.h" #include "coroutine.h" #include "coroutine_int.h" ## FIFO Scheduler ![](https://i.imgur.com/agOZCZi.png) FIFO是先進先出的縮寫。 ### fifo_schedule函式 * 目的： 它是一種處理數據結構的方法，其中第一個元素是首先處理，最後處理最新的元素。 * 使用 calloc 為 new_task 分配內存 如果任務為空則返回 ENOMEM 如果隊列為空則返回 ENOMEM * 如果沒有錯誤則啟動調度程序: 將 new_task->cr 分配為 cr 分配 new_task->tfd 作為 cr 的大小 將 new_task 的工作分配為 func 將 new_task->args 分配為 argos 將 new_task context.label 分配為 NULL 將 context.wait_yield 分配給 1 將 context.blocked 分配給 1 最後返回 new_task->tfd ### fifo_pick_next_task函式 * 目的：在 FIFO 調度器中選擇下一個任務 * 返回 rq_dequeue（出隊） 刪除並返回隊列前面的元素 ### fifo_put_prev_task函式 * 目的：將上一個任務放入 FIFO 調度器 * 返回 rq_enqueue（入隊） 將任務放入隊列（在隊列末尾插入元素） ## Default Scheduler ![](https://i.imgur.com/BOak36T.png) * Default scheduler 是 CFS 或 Completely Fair Scheduler * 調度器維護一個red black tree，其中節點根據接收到的虛擬執行時間排序 接下來選擇具有最小虛擬接收執行時間的node 優先級決定虛擬執行時間的累積率 * Higher priority -> slower accumulation rate ### RBTREE_CMP_INSERT_DEFINE函式 * 將 task_struct n1 分配為 container_of(n1, struct task_struct, node); 將 task_struct n2 分配為 container_of(n2, struct task_struct, node); * container_of的實現是先將地址0轉為結構體指針， 然後獲取成員（節點）的地址。 因為是從0開始，所以會得到這個成員在結構體中的偏移量。 最後將原來的成員內存地址減去這個偏移量，就得到了容器結構體的地址。 * 如果 `n1 runtime` 小於 `n2 runtime` 則返回 1， 否則如果 `n1 runtime` 等於 `n2 runtime` 而不是 n1 runtime 加 1 然後返回0； ### RBTREE_CMP_SEARCH_DEFINE函式 * 目的：在RBTREE中查找一個key * 將 task_struct n1 分配為 (n1,struct task_struct,node) 的容器 * 如果 n1 runtime 等於 key 則返回 RB_EQUAL 否則，如果 n1 運行時大於密鑰本身， 則返回 RB_RIGHT 否則返回 RB_LEFT ### time_diff函式 * 目的：在開始和結束之間找到不同的時間 * 如果差異小於 0，則差異將增加 10000000000 否則end減start ### default_schedule函式 * 將指針 new_task 聲明為struct 將 exec_base 聲明為 static long 使用 calloc 為 new_task 分配內存 如果沒有 new_task 則返回 -ENOMEM * 分配new_task-> sum_exec_runtime 作為 exec_base 調用rbtree_insert插入到red black tree * 返回 new_task->tfd ### default_pick_next_task函式 * 目的：選擇調度中的下一個任務，選擇下一個進程，調度程序選擇具有最小 vruntime 的任務。 即，運行最少的進程。 * 將節點聲明為紅黑樹內運行時的最小值 (rbtree_min(&cr->root)) 將 task_struct 任務聲明為 (node ,struct task_struct,node) 的容器 聲明結構 timespec start； * 如果節點為空則返回 NULL * 如果沒有錯誤： 刪除具有最小運行時間的紅黑樹 使用clock_gettime()獲取CLOCK_MONOTONIC指定時鐘的當前時間，並將其放入&start指向的緩衝區。 將 task->exec_start 分配為 start.tv_nsec * 返回task ### default_put_prev_task函式 * 目的：將上一個任務插入red black tree * 聲明struct timespec end * 使用clock_gettime()獲取CLOCK_MONOTONIC指定時鐘的當前時間，並將其放入&end指向的緩衝區。 計算開始和結束之間的時間差 * 然後將任務插入到red black tree中 ### sched_init函式 * 目的：在 default_scheduler 或 fifo_scheduler 之間進行選擇 * 如果選擇 default_scheduler 那麼它將初始化red black tree 將schedule分配為 default_schedule 將next task分配為 default_pick_next_task 將previous task 分配為 default_put_prev_task * 如果選擇了 fifo_scheduler 將schedule分配為 fifo_schedule 將next task分配為 fifo_pick_next_task 將prev task分配為 fifo_put_prev_task