/**
 * 進程式控制制塊結構（ucore進程和執行緒都使用proc_struct進行管理）
 * */
struct proc_struct {
    。。。 只列出了lab6中新增加的屬性項

    // 包含該執行緒的就緒隊列(多級多列調度時，系統中存在多個就緒隊列)
    struct run_queue *rq;                       // running queue contains Process
    // 就緒隊列節點
    list_entry_t run_link;                      // the entry linked in run queue
    // 執行緒能夠佔有的CPU時間片
    int time_slice;                             // time slice for occupying the CPU
    // lab6中支援stride演算法的斜堆節點
    skew_heap_entry_t lab6_run_pool;            // FOR LAB6 ONLY: the entry in the run pool
    // lab6中支援stride演算法的當前執行緒stride步長
    uint32_t lab6_stride;                       // FOR LAB6 ONLY: the current stride of the process 
    // 執行緒的特權級
    uint32_t lab6_priority;                     // FOR LAB6 ONLY: the priority of process, set by lab6_set_priority(uint32_t)
};

// The introduction of scheduling classes is borrrowed from Linux, and makes the 
// core scheduler quite extensible. These classes (the scheduler modules) encapsulate 
// the scheduling policies. 
struct sched_class {
    // the name of sched_class
    // 調度類的名字
    const char *name;
    // Init the run queue
    // 初始化就緒隊列
    void (*init)(struct run_queue *rq);
    // put the proc into runqueue, and this function must be called with rq_lock
    // 將一個執行緒加入就緒隊列(調用此方法一定要使用隊列鎖調用(lab6中直接關中斷來避免並發))
    void (*enqueue)(struct run_queue *rq, struct proc_struct *proc);
    // get the proc out runqueue, and this function must be called with rq_lock
    // 將一個執行緒從就緒隊列中移除(調用此方法一定要使用隊列鎖調用(lab6中直接關中斷來避免並發))
    void (*dequeue)(struct run_queue *rq, struct proc_struct *proc);
    // choose the next runnable task
    // 調度框架從就緒隊列中選擇出下一個可運行的執行緒
    struct proc_struct *(*pick_next)(struct run_queue *rq);
    // dealer of the time-tick
    // 發生時鐘中斷時，調度器的處理邏輯
    void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc);
};

/**
 * 初始化任務調度器
 * */
void
sched_init(void) {
    // 清空定時器隊列
    list_init(&timer_list);

    // 令當前的調度框架為default_sched_class(stride_schedule)
    sched_class = &default_sched_class;

    rq = &__rq;
    // 設置最大的時間片
    rq->max_time_slice = MAX_TIME_SLICE;
    // 初始化全局就緒隊列
    sched_class->init(rq);

    cprintf("sched class: %s\n", sched_class->name);
}

/**
 * 就緒執行緒進行CPU調度
 * */
void
schedule(void) {
    bool intr_flag;
    struct proc_struct *next;
    // 暫時關閉中斷，避免被中斷打斷，引起並發問題
    local_intr_save(intr_flag);
    {
        // 令current執行緒處於不需要調度的狀態
        current->need_resched = 0;
        if (current->state == PROC_RUNNABLE) {
            // 如果當前執行緒依然是就緒態，將其置入就緒隊列(有機會再被調度演算法選出來)
            sched_class_enqueue(current);
        }

        // 通過調度演算法篩選出下一個需要被調度的執行緒
        if ((next = sched_class_pick_next()) != NULL) {
            // 如果選出來了，將其從就緒隊列中出隊
            sched_class_dequeue(next);
        }
        if (next == NULL) {
            // 沒有找到任何一個就緒執行緒，則由idleproc獲得CPU
            next = idleproc;
        }
        // 被選中進行調度執行的執行緒，被調度執行次數+1
        next->runs ++;
        if (next != current) {
            // 如果被選出來的執行緒不是current當前正在執行的執行緒，進行執行緒上下文切換，令被選中的next執行緒獲得CPU
            proc_run(next);
        }
    }
    local_intr_restore(intr_flag);
}

static inline void
sched_class_enqueue(struct proc_struct *proc) {
    if (proc != idleproc) {
        // 如果不是idleproc，令proc執行緒加入就緒隊列
        sched_class->enqueue(rq, proc);
    }
}

static inline void
sched_class_dequeue(struct proc_struct *proc) {
    // 將proc執行緒從就緒隊列中移除
    sched_class->dequeue(rq, proc);
}

static inline struct proc_struct *
sched_class_pick_next(void) {
    // 有調度框架從就緒隊列中挑選出下一個進行調度的執行緒
    return sched_class->pick_next(rq);
}

static void
trap_dispatch(struct trapframe *tf) {
    char c;

    int ret=0;

    switch (tf->tf_trapno) { 
        。。。 省略其它中斷處理邏輯
        case IRQ_OFFSET + IRQ_TIMER:

            ticks ++;
            assert(current != NULL);
            // 令調度框架得以監聽到時鐘中斷，修改對應的調度狀態
            sched_class_proc_tick(current);
            break;
        。。。 省略其它中斷處理邏輯
    ｝
｝

void
sched_class_proc_tick(struct proc_struct *proc) {
    if (proc != idleproc) {
        // 處理時鐘中斷，令調度框架更新對應的調度參數
        sched_class->proc_tick(rq, proc);
    }
    else {
        // idleproc處理時鐘中斷，需要進行調度
        proc->need_resched = 1;
    }
}

/*
 * stride_init initializes the run-queue rq with correct assignment for
 * member variables, including:
 *
 *   - run_list: should be a empty list after initialization.
 *   - lab6_run_pool: NULL
 *   - proc_num: 0
 *   - max_time_slice: no need here, the variable would be assigned by the caller.
 *
 * hint: see proj13.1/libs/list.h for routines of the list structures.
 */
static void
stride_init(struct run_queue *rq) {
    /* LAB6: YOUR CODE */

    // 初始化就緒隊列
    list_init(&(rq->run_list));
    rq->lab6_run_pool = NULL;
    rq->proc_num = 0;
}

/**
 * 就緒隊列
 * */
struct run_queue {
    list_entry_t run_list;
    unsigned int proc_num;
    int max_time_slice;
    // For LAB6 ONLY 斜堆堆頂節點
    skew_heap_entry_t *lab6_run_pool;
};

/*
 * stride_enqueue inserts the process ``proc'' into the run-queue
 * ``rq''. The procedure should verify/initialize the relevant members
 * of ``proc'', and then put the ``lab6_run_pool'' node into the
 * queue(since we use priority queue here). The procedure should also
 * update the meta date in ``rq'' structure.
 *
 * proc->time_slice denotes the time slices allocation for the
 * process, which should set to rq->max_time_slice.
 * 
 * hint: see proj13.1/libs/skew_heap.h for routines of the priority
 * queue structures.
 */
static void
stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {
    /* LAB6: YOUR CODE */
#if USE_SKEW_HEAP
    // 使用斜堆實現就緒隊列(lab6中默認USE_SKEW_HEAP為真)
    // 將proc插入就緒隊列，並且更新就緒隊列的頭元素
    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)));
    // 將proc插入就緒隊列
    list_add_before(&(rq->run_list), &(proc->run_link));
#endif
     if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) {
         // 入隊時，如果執行緒之前時間片被用完進行過調度則time_slice會為0，再次入隊時需要重置時間片(或者時間片未正確設置，大於了就緒隊列的max_time_slice)
         // 令其time_slice=rq->max_time_slice(最大分配的時間片)
         proc->time_slice = rq->max_time_slice;
     }
     // 令執行緒和就緒隊列進行關聯
     proc->rq = rq;
     // 就緒隊列中的就緒執行緒數加1
     rq->proc_num ++;
}

/*
 * stride_dequeue removes the process ``proc'' from the run-queue
 * ``rq'', the operation would be finished by the skew_heap_remove
 * operations. Remember to update the ``rq'' structure.
 *
 * hint: see proj13.1/libs/skew_heap.h for routines of the priority
 * queue structures.
 */
static void
stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {
     /* LAB6: YOUR CODE */
#if USE_SKEW_HEAP
    // 使用斜堆實現就緒隊列(lab6中默認USE_SKEW_HEAP為真)
    // 將proc移除出就緒隊列，並且更新就緒隊列的頭元素
    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);
    // 將proc移除出就緒隊列，並且更新就緒隊列的頭元素
    list_del_init(&(proc->run_link));
#endif
    // 移除完成之後，就緒隊列所擁有的執行緒數減1
    rq->proc_num --;
}
/*
 * stride_pick_next pick the element from the ``run-queue'', with the
 * minimum value of stride, and returns the corresponding process
 * pointer. The process pointer would be calculated by macro le2proc,
 * see proj13.1/kern/process/proc.h for definition. Return NULL if
 * there is no process in the queue.
 *
 * When one proc structure is selected, remember to update the stride
 * property of the proc. (stride += BIG_STRIDE / priority)
 *
 * hint: see proj13.1/libs/skew_heap.h for routines of the priority
 * queue structures.
 */
static struct proc_struct *
stride_pick_next(struct run_queue *rq) {
     /* LAB6: YOUR CODE */
#if USE_SKEW_HEAP
    // 使用斜堆實現就緒隊列(lab6中默認USE_SKEW_HEAP為真)
    if (rq->lab6_run_pool == NULL) return NULL; // 就緒隊列為空代表沒找到，返回null
    // 獲取就緒隊列的頭結點，轉換為所關聯的執行緒返回
    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)
        // 雙向鏈表為空代表沒找到，返回null
        return NULL;
     
    struct proc_struct *p = le2proc(le, run_link);
    le = list_next(le);
    // 遍歷整個雙向鏈表，找到p->lab6_stride最小的那一個（p）
    while (le != &rq->run_list)
    {
        struct proc_struct *q = le2proc(le, run_link);
        if ((int32_t)(p->lab6_stride - q->lab6_stride) > 0){
            // 如果執行緒q的lab6_stride小於當前lab6_stride最小的執行緒p
            // 令p=q，即q成為當前找到的lab6_stride最小的那一個執行緒
            p = q;
        }
        // 指向雙向鏈表的下一個節點，進行遍歷
        le = list_next(le);
    }
#endif
    // 最終找到的執行緒指針p指向的是lab6_stride最小的那一個執行緒，即按照stride調度演算法被選中的那一個執行緒
    if (p->lab6_priority == 0){
        // 特權級為0比較特殊代表最低許可權，一次的步進為BIG_STRIDE
        p->lab6_stride += BIG_STRIDE;
    }else{
        // 否則一次的步進為BIG_STRIDE / p->lab6_priority
        // 即lab6_priority(正整數)越大，特權級越高，一次步進的就越小
        // 更容易被stride調度演算法選中，相對而言被執行的次數也就越多，因此滿足了執行緒特權級越高，被調度越頻繁的需求
        p->lab6_stride += BIG_STRIDE / p->lab6_priority;
    }
    return p;
}

/*
 * stride_proc_tick works with the tick event of current process. You
 * should check whether the time slices for current process is
 * exhausted and update the proc struct ``proc''. proc->time_slice
 * denotes the time slices left for current
 * process. proc->need_resched is the flag variable for process
 * switching.
 */
static void
stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
     /* LAB6: YOUR CODE */
     if (proc->time_slice > 0) {
         // 如果執行緒所分配的時間片還沒用完(time_slice大於0)，則將所擁有的的時間片減1
          proc->time_slice --;
     }
     if (proc->time_slice == 0) {
         // 當時間片減為0時，說明為當前執行緒分配的時間片已經用完，需要重新進行一次執行緒調度
         proc->need_resched = 1;
     }
}

/* *
 * trap - handles or dispatches an exception/interrupt. if and when trap() returns,
 * the code in kern/trap/trapentry.S restores the old CPU state saved in the
 * trapframe and then uses the iret instruction to return from the exception.
 * */
void
trap(struct trapframe *tf) {
    // dispatch based on what type of trap occurred
    // used for previous projects
    if (current == NULL) {
        trap_dispatch(tf);
    }
    else {
        // keep a trapframe chain in stack
        struct trapframe *otf = current->tf;
        current->tf = tf;
    
        bool in_kernel = trap_in_kernel(tf);
    
        trap_dispatch(tf);
    
        current->tf = otf;
        if (!in_kernel) {
            if (current->flags & PF_EXITING) {
                // 如果當前執行緒被殺了(do_kill),將自己退出（被喚醒之後發現自己已經被判了死刑，自我了斷）
                do_exit(-E_KILLED);
            }
            if (current->need_resched) {
                // 可能執行了阻塞的系統調用等情況，need_resched為真，進行執行緒調度切換
                schedule();
            }
        }
    }
}