首页 > 代码库 > xv6/调度算法及并发程序设计
xv6/调度算法及并发程序设计
1 在proc.c的scheduler函数中,有两行:
if(setjmp(&cpus[cpu()].jmpbuf) == 0)
longjmp(&p->jmpbuf);
把它修改为:
cprintf("setjmp called in scheduler\n");
if(setjmp(&cpus[cpu()].jmpbuf) == 0){
cprintf("setjmp in scheduler returned 0; longjmp\n");
longjmp(&p->jmpbuf);
}else
cprintf("setjmp in scheduler returned 1\n");
修改后,重编译内核,在Bochs中运行编译后的内核,你将会看到有规律的六行输出在屏幕上。
要求:
- 1. 列出这有规律的六行。
- 2. 在这六行里面,每输出两行setjmp returned 才输出一行setjmp called. 试解释一下为什么
int setjmp(struct jmpbuf *jmp);
void longjmp(struct jmpbuf *jmp); 的函数解析!
# Setjmp saves its stack environment in jmp for later use by longjmp.
# It returns 0.
# Longjmp restores the environment saved by the last call of setjmp.
# It then causes execution to continue as if the call of setjmp
# had just returned 1.
# The caller of setjmp must not itself have returned in the interim.
# All accessible data have values as of the time longjmp was called.
# [Description, but not code, borrowed from Plan 9.]
这是setjmp和longjmp的函数解析。意思在于setjmp会保存当前环境,上下文。然后longjmp会回溯到最后一个setjmp所指向保存的环境。如图1所示
图1
cprintf("setjmp called in scheduler\n");
if(setjmp(&cpus[cpu()].jmpbuf) == 0){
cprintf("setjmp in scheduler returned 0; longjmp\n");
longjmp(&p->jmpbuf);
}else
cprintf("setjmp in scheduler returned 1\n");
一开始的时候没有longjmp的时候,setjmp返回的为0.
然后执行cprintf("setjmp in scheduler returned 0; longjmp\n");
接着到longjmp 于是跳回setjmp的位置。此时因为longjmp了于是setjpm返回1。
于是执行cprintf("setjmp in scheduler returned 1\n");
所以才有一次setjmp returned 才输出一行setjmp called。
- 3. 试解释一下scheduler函数和sched函数的用途。
可以从scheduler函数和sched函数的注释中看出.
对于scheduler函数
// Per-CPU process scheduler.
// Each CPU calls scheduler() after setting itself up.
// Scheduler never returns. It loops, doing:
// - choose a process to run
// - longjmp to start running that process
// - eventually that process transfers control back
// via longjmp back to the top of scheduler.
每一个CPU都有属于它自己的scheduler函数,当每一个CPU设置它本身的时候会调用scheduler函数的时候。Scheduler函数永远不会返回,它会不断的循环:(循环过程中)
1 选择一个进程,然后运行该进程。
2 使用longjmp跳到那个进程代码那,开始运行那个进程。
3 最后进程将控制权转移回来。
4 通过longjmp调到scheduler函数头。重新开始。
对于 sched函数
// Enter scheduler. Must already hold proc_table_lock
// and have changed curproc[cpu()]->state.
在进入scheduler 函数,而且会在持有 proc_table_lock
并且会改变 curproc[cpu()]的状态。
4. 阅读trap.c 第50行至第66行。Proc.c中的 yield函数、sched函数及scheduler函数,结合书本,确定xv6使用的是哪种调度算法。给出你的理由(通过分析代码证明你的观点)。
1先来先服务(FCFS)
2短作业优先(SF)
3高响应比优先
4时间片轮转(RR)
5多级队列调度算法
6多级反馈队列调度算法总共有6调度算法是XV6可能的选项。
前三种都是要安装进程的某个属性排序,比如进入时间,比如作业长短,响应比。并且选择进入时间最早,作业最短,响应比最高。
Scheduler 函数中的
for(i = 0; i < NPROC; i++){
p = &proc[i];
if(p->state != RUNNABLE)
continue;
这部分是调度算法的核心,证明了XV6是使用时间轮转(RR)。因为上面代码就是一个循环,在process数组里寻找可执行的进程。然后接下去的代码的意义才是跳到被选中的进程去进行执行。
// Switch to chosen process. It is the process‘s job
// to release proc_table_lock and then reacquire it
// before jumping back to us.
setupsegs(p);
curproc[cpu()] = p;
p->state = RUNNING;
if(setjmp(&cpus[cpu()].jmpbuf) == 0)
longjmp(&p->jmpbuf);
至于yield 函数 sched函数。当一个进程使用完时间片后,会中断调用yield函数来让出CPU给新的进程,yield调用sched函数,sched会切换:
void
sched(void)
{
struct proc *p = curproc[cpu()];
if(!holding(&proc_table_lock))
panic("sched");
if(cpus[cpu()].nlock != 1)
panic("sched locks");
if(setjmp(&p->jmpbuf) == 0)
longjmp(&cpus[cpu()].jmpbuf);
}
xv6/调度算法及并发程序设计