# shed.c 註解
## 一些define
#define _GNU_SOURCE
#include <stdint.h>
#include <stdlib.h>
#include <errno.h>
#include <time.h>
#include <sched.h>

#include "rbtree.h"
#include "context.h"
#include "coroutine.h"
#include "coroutine_int.h"

## FIFO Scheduler
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

* 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