// 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. structsched_class { // the name of sched_class constchar *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 void (*enqueue)(struct run_queue *rq, struct proc_struct *proc); // get the proc out runqueue, and this function must be called with rq_lock void (*dequeue)(struct run_queue *rq, struct proc_struct *proc); // choose the next runnable task structproc_struct *(*pick_next)(structrun_queue *rq); // dealer of the time-tick void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc); /* for SMP support in the future * load_balance * void (*load_balance)(struct rq* rq); * get some proc from this rq, used in load_balance, * return value is the num of gotten proc * int (*get_proc)(struct rq* rq, struct proc* procs_moved[]); */ };
/* * 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 libs/list.h for routines of the list structures. */ staticvoid stride_init(struct run_queue *rq) { /* LAB6: YOUR CODE * (1) init the ready process list: rq->run_list * (2) init the run pool: rq->lab6_run_pool * (3) set number of process: rq->proc_num to 0 */ rq->lab6_run_pool = NULL; rq->proc_num = 0; }
/* * 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 libs/skew_heap.h for routines of the priority * queue structures. */ staticvoid stride_enqueue(struct run_queue *rq, struct proc_struct *proc) { /* LAB6: YOUR CODE * (1) insert the proc into rq correctly * NOTICE: you can use skew_heap or list. Important functions * skew_heap_insert: insert a entry into skew_heap * list_add_before: insert a entry into the last of list * (2) recalculate proc->time_slice * (3) set proc->rq pointer to rq * (4) increase rq->proc_num */ rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &proc->lab6_run_pool, proc_stride_comp_f); if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) { proc->time_slice = rq->max_time_slice; } proc->rq = rq; ++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 libs/skew_heap.h for routines of the priority * queue structures. */ staticvoid stride_dequeue(struct run_queue *rq, struct proc_struct *proc) { /* LAB6: YOUR CODE * (1) remove the proc from rq correctly * NOTICE: you can use skew_heap or list. Important functions * skew_heap_remove: remove a entry from skew_heap * list_del_init: remove a entry from the list */ rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &proc->lab6_run_pool, proc_stride_comp_f); // list_del_init(&proc->run_link); // proc->rq = NULL; 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 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 libs/skew_heap.h for routines of the priority * queue structures. */ staticstruct proc_struct * stride_pick_next(struct run_queue *rq) { /* LAB6: YOUR CODE * (1) get a proc_struct pointer p with the minimum value of stride (1.1) If using skew_heap, we can use le2proc get the p from rq->lab6_run_pool (1.2) If using list, we have to search list to find the p with minimum stride value * (2) update p;s stride value: p->lab6_stride * (3) return p */ if (rq->proc_num == 0) returnNULL; structproc_struct* proc = le2proc(rq->lab6_run_pool, lab6_run_pool); rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &proc->lab6_run_pool, proc_stride_comp_f); proc->lab6_stride += BIG_STRIDE / (proc->lab6_priority == 0 ? 1 : proc->lab6_priority); rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &proc->lab6_run_pool, proc_stride_comp_f); return proc; }
时钟中断函数和 Round Robin 算法一样：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/* * 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. */ staticvoid stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) { /* LAB6: YOUR CODE */ if (proc->time_slice > 0) { proc->time_slice --; } if (proc->time_slice == 0) { proc->need_resched = 1; } }
__alltraps: # push registers to build a trap frame # therefore make the stack look like a struct trapframe pushl %ds pushl %es pushl %fs pushl %gs pushal
# load GD_KDATA into %ds and %es to set up data segments for kernel movl $GD_KDATA, %eax movw %ax, %ds movw %ax, %es
# push %esp to pass a pointer to the trapframe as an argument to trap() pushl %esp
# call trap(tf), where tf=%esp call trap
# pop the pushed stack pointer popl %esp __trapret: # restore registers from stack popal
