|
|
|
# 调度
|
|
|
|
|
|
|
|
任何操作系统都可能碰到进程数多于处理器数的情况，这样就需要考虑如何分享处理器资源。理想的做法是让分享机制对进
|
|
|
|
程透明。通常我们对进程造成一个自己独占处理器的假象，然后让操作系统的 多路复用机制（multiplex） 将单独的一个物理处
|
|
|
|
理器模拟为多个虚拟处理器。
|
|
|
|
|
|
|
|
## 多路复用
|
|
|
|
|
|
|
|
xv6 中 多路复用 的实现如下：当一个进程等待磁盘请求时，xv6 使之进入睡眠状态，然后调度执行另一个进程。另外，当一个
|
|
|
|
进程耗尽了它在处理器上运行的时间片（100毫秒）后，xv6 使用时钟中断强制它停止运行，这样调度器才能调度运行其他进
|
|
|
|
程。这样的多路复用机制为进程提供了独占处理器的假象，类似于 xv6 使用内存分配器和页表硬件为进程提供了独占内存的
|
|
|
|
假象。
|
|
|
|
|
|
|
|
实现多路复用有几个难点。首先，应该如何从运行中的一个进程切换到另一个进程？xv6 采用了普通的上下文切换机制；虽
|
|
|
|
然这里的思想是非常简洁明了的，但是其代码实现是操作系统中最晦涩难懂的一部分。第二，如何让上下文切换透明化？xv6
|
|
|
|
只是简单地使用时钟中断处理程序来驱动上下文切换。第三，可能出现多个 CPU 同时切换进程的情况，那么我们必须使用
|
|
|
|
一个带锁的方案来避免竞争。第四，进程退出时必须释放其占用内存与资源，但由于它本身在使用自己的资源（譬如其内核
|
|
|
|
栈），所以不能由该进程本身释放其占有的所有资源。xv6 希望能够简洁明了地处理这些难点，不过最后其代码实现还是比
|
|
|
|
较“巧妙”。
|
|
|
|
|
|
|
|
## 上下文切换
|
|
|
|
|
|
|
|
xv6 在低层次中实现了两种上下文切换：从进程的内核线程切换到当前 CPU 的调度器线程，从调度器线程
|
|
|
|
到进程的内核线程。xv6 永远不会直接从用户态进程切换到另一个用户态进程；这种切换是通过用户态-内核态切换（系统调
|
|
|
|
用或中断）、切换到调度器、切换到新进程的内核线程、最后这个陷入返回实现的。本节我们将以内核线程与调度器线程的
|
|
|
|
切换作为例子来说明。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
每个 xv6 进程都有自己的内核栈以及寄存器集合。每个 CPU 都有一个单独的调度器线程，这样调度就不会发生在进程的内核线程中，而是在此调度器线程中。线程的切换涉及到了保存旧线程的 CPU 寄存器，恢复新线程之
|
|
|
|
前保存的寄存器；其中 %esp 和 %eip 的变换意味着 CPU 会切换运行栈与运行代码。
|
|
|
|
|
|
|
|
我们来看swtch
|
|
|
|
|
|
|
|
```c
|
|
|
|
# Context switch
|
|
|
|
#
|
|
|
|
# void swtch(struct context *old, struct context *new);
|
|
|
|
#
|
|
|
|
# Save current registers in old. Load from new.
|
|
|
|
.globl swtch
|
|
|
|
swtch:
|
|
|
|
st.d $ra, $a0, 0
|
|
|
|
st.d $sp, $a0, 8
|
|
|
|
st.d $s0, $a0, 16
|
|
|
|
st.d $s1, $a0, 24
|
|
|
|
st.d $s2, $a0, 32
|
|
|
|
st.d $s3, $a0, 40
|
|
|
|
st.d $s4, $a0, 48
|
|
|
|
st.d $s5, $a0, 56
|
|
|
|
st.d $s6, $a0, 64
|
|
|
|
st.d $s7, $a0, 72
|
|
|
|
st.d $s8, $a0, 80
|
|
|
|
st.d $fp, $a0, 88
|
|
|
|
|
|
|
|
ld.d $ra, $a1, 0
|
|
|
|
ld.d $sp, $a1, 8
|
|
|
|
ld.d $s0, $a1, 16
|
|
|
|
ld.d $s1, $a1, 24
|
|
|
|
ld.d $s2, $a1, 32
|
|
|
|
ld.d $s3, $a1, 40
|
|
|
|
ld.d $s4, $a1, 48
|
|
|
|
ld.d $s5, $a1, 56
|
|
|
|
ld.d $s6, $a1, 64
|
|
|
|
ld.d $s7, $a1, 72
|
|
|
|
ld.d $s8, $a1, 80
|
|
|
|
ld.d $fp, $a1, 88
|
|
|
|
|
|
|
|
jirl $zero, $ra, 0
|
|
|
|
```
|
|
|
|
|
|
|
|
可以看到 `swtch` 把当前的寄存器保存到 `old` 中，然后从 `new` 中恢复寄存器，最后跳转到 `new` 中保存的 `ra` 寄存器指向的地址。这样就完成了上下文切换。
|
|
|
|
|
|
|
|
还记的什么时候调度器会调用 `swtch` 吗，我们在 `scheduler` 中可以看到，当调度器发现有进程处于 `RUNNABLE` 状态时，就会调用 `swtch` 进行上下文切换。
|
|
|
|
|
|
|
|
```c
|
|
|
|
// Scheduler never returns. It loops, doing:
|
|
|
|
// - choose a process to run.
|
|
|
|
// - swtch to start running that process.
|
|
|
|
// - eventually that process transfers control
|
|
|
|
// via swtch back to the scheduler.
|
|
|
|
void
|
|
|
|
scheduler(void)
|
|
|
|
{
|
|
|
|
struct proc *p;
|
|
|
|
struct cpu *c = mycpu();
|
|
|
|
|
|
|
|
c->proc = 0;
|
|
|
|
for(;;){
|
|
|
|
// Avoid deadlock by ensuring that devices can interrupt.
|
|
|
|
intr_on();
|
|
|
|
|
|
|
|
for(p = proc; p < &proc[NPROC]; p++) {
|
|
|
|
acquire(&p->lock);
|
|
|
|
if(p->state == RUNNABLE) {
|
|
|
|
// Switch to chosen process. It is the process's job
|
|
|
|
// to release its lock and then reacquire it
|
|
|
|
// before jumping back to us.
|
|
|
|
p->state = RUNNING;
|
|
|
|
c->proc = p;
|
|
|
|
swtch(&c->context, &p->context);
|
|
|
|
// Process is done running for now.
|
|
|
|
// It should have changed its p->state before coming back.
|
|
|
|
c->proc = 0;
|
|
|
|
}
|
|
|
|
release(&p->lock);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
我们现在看到了完整的调度器的调用进程的过程，我们来总结一下这个过程。
|
|
|
|
|
|
|
|
**从 `main` 进到 `scheduler` 之后， CPU的上下文是运行 `scheduler` 中的死循环，**
|
|
|
|
**当调度器发现有进程处于 `RUNNABLE` 状态时，就会调用 `swtch` 进行上下文切换，这样 CPU 的上下文就变成了运行 `RUNNABLE` 进程的内核线程，开始运行这个进程。**
|
|
|
|
|
|
|
|
那CPU是如何放弃这个进程的呢？
|
|
|
|
|
|
|
|
我们来看 `usertrap`
|
|
|
|
|
|
|
|
```c
|
|
|
|
//
|
|
|
|
// handle an interrupt, exception, or system call from user space.
|
|
|
|
// called from trampoline.S
|
|
|
|
//
|
|
|
|
void
|
|
|
|
usertrap(void)
|
|
|
|
{
|
|
|
|
int which_dev = 0;
|
|
|
|
|
|
|
|
if((r_csr_prmd() & PRMD_PPLV) == 0)
|
|
|
|
panic("usertrap: not from user mode");
|
|
|
|
|
|
|
|
struct proc *p = myproc();
|
|
|
|
|
|
|
|
// save user program counter.
|
|
|
|
p->trapframe->era = r_csr_era();
|
|
|
|
|
|
|
|
if(((r_csr_estat()& CSR_ESTAT_ECODE) >> 16) == 0xb){
|
|
|
|
// system call
|
|
|
|
|
|
|
|
if(p->killed)
|
|
|
|
exit(-1);
|
|
|
|
|
|
|
|
// sepc points to the ecall instruction,
|
|
|
|
// but we want to return to the next instruction.
|
|
|
|
p->trapframe->era += 4;
|
|
|
|
|
|
|
|
// an interrupt will change sstatus &c registers,
|
|
|
|
// so don't enable until done with those registers.
|
|
|
|
intr_on();
|
|
|
|
|
|
|
|
syscall();
|
|
|
|
} else if((which_dev = devintr()) != 0){
|
|
|
|
// ok
|
|
|
|
}
|
|
|
|
else if((r_csr_estat() >> 16) == PIL || (r_csr_estat() >> 16) == PIS) {
|
|
|
|
// printf("=== trap ===\n");
|
|
|
|
uint64 addr = r_csr_badv();
|
|
|
|
struct VMA* vp = 0;
|
|
|
|
//to fina the target vma
|
|
|
|
for( int i=0 ; i<VMA_MAX ; i++ ) {
|
|
|
|
if( p->vma[i].addr <= addr && addr < p->vma[i].addr + p->vma[i].len && p->vma[i].valid == 1 )
|
|
|
|
{
|
|
|
|
vp = &p->vma[i];
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
if( vp != 0 )
|
|
|
|
{
|
|
|
|
uint64 mem = (uint64)allocpage();
|
|
|
|
memset( (void*)mem , 0 , PGSIZE );
|
|
|
|
if( -1 == mappages( p->pagetable , addr, PGSIZE , mem , PTE_U | PTE_V | ( vp->prot << 1 ) ) )
|
|
|
|
panic("pagefault map error");
|
|
|
|
|
|
|
|
vp->mapcnt += PGSIZE; //maintain the mapcnt
|
|
|
|
ilock( vp->f->ip );
|
|
|
|
vp->f->ip->fop->read( vp->f->ip , 1 , addr , addr-vp->addr , PGSIZE); //copy a page of the file from the disk
|
|
|
|
iunlock( vp->f->ip );
|
|
|
|
}
|
|
|
|
}
|
|
|
|
else {
|
|
|
|
printf("usertrap(): unexpected trapcause %p pid=%d\n", r_csr_estat(), p->pid);
|
|
|
|
printf(" era=%p badi=%p\n", r_csr_era(), r_csr_badi());
|
|
|
|
p->killed = 1;
|
|
|
|
}
|
|
|
|
|
|
|
|
if(p->killed)
|
|
|
|
exit(-1);
|
|
|
|
|
|
|
|
// give up the CPU if this is a timer interrupt.
|
|
|
|
if(which_dev == 2)
|
|
|
|
{
|
|
|
|
myproc()->user_time++;
|
|
|
|
yield();
|
|
|
|
}
|
|
|
|
|
|
|
|
usertrapret();
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
注意其中的这段代码：
|
|
|
|
|
|
|
|
```c
|
|
|
|
// give up the CPU if this is a timer interrupt.
|
|
|
|
if(which_dev == 2)
|
|
|
|
{
|
|
|
|
myproc()->user_time++;
|
|
|
|
yield();
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
当CPU上的进程线程运行了这个时间片后，会触发时间中断，然后进入这个if中，调用函数 `yield`。
|
|
|
|
|
|
|
|
我们来看 `yield` 的代码：
|
|
|
|
|
|
|
|
```c
|
|
|
|
// Give up the CPU for one scheduling round.
|
|
|
|
void
|
|
|
|
yield(void)
|
|
|
|
{
|
|
|
|
struct proc *p = myproc();
|
|
|
|
acquire(&p->lock);
|
|
|
|
p->state = RUNNABLE;
|
|
|
|
sched();
|
|
|
|
release(&p->lock);
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
代码把当前进程的状态设置为 `RUNNABLE` ，也就是可运行态后，调用 `sched` 函数，我们再来看
|
|
|
|
`sched` 的代码
|
|
|
|
|
|
|
|
```c
|
|
|
|
// Switch to scheduler. Must hold only p->lock
|
|
|
|
// and have changed proc->state. Saves and restores
|
|
|
|
// intena because intena is a property of this
|
|
|
|
// kernel thread, not this CPU. It should
|
|
|
|
// be proc->intena and proc->noff, but that would
|
|
|
|
// break in the few places where a lock is held but
|
|
|
|
// there's no process.
|
|
|
|
void
|
|
|
|
sched(void)
|
|
|
|
{
|
|
|
|
int intena;
|
|
|
|
struct proc *p = myproc();
|
|
|
|
|
|
|
|
if(!holding(&p->lock))
|
|
|
|
panic("sched p->lock");
|
|
|
|
if(mycpu()->noff != 1)
|
|
|
|
panic("sched locks");
|
|
|
|
if(p->state == RUNNING)
|
|
|
|
panic("sched running");
|
|
|
|
if(intr_get())
|
|
|
|
panic("sched interruptible");
|
|
|
|
|
|
|
|
intena = mycpu()->intena;
|
|
|
|
swtch(&p->context, &mycpu()->context);
|
|
|
|
mycpu()->intena = intena;
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
可以看到， `sched` 在经过一系列检查后，调用 `swtch` 把当前进程的context 保存起来，然后
|
|
|
|
加载了 CPU的上下文，也就是上面提到过的 `scheduler` 的死循环。
|
|
|
|
|
|
|
|
所以我们现在对进程的退出做一个总结：
|
|
|
|
|
|
|
|
**当这个进程的时间片用完后，进程通过调用 `yield`，将CPU 的上下文又变成了运行 `scheduler` 的死循环，这样就完成了一次进程的调度。**
|
|
|
|
|
|
|
|
这也是我们的OS的调用流程。 |
|
|
\ No newline at end of file |
