/**
 * 进程控制块结构（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();
            }
        }
    }
}