xv6 进程及调度

xv6 进程

数据结构

struct context

struct context {uint64 ra;uint64 sp;// callee-saveduint64 s0;uint64 s1;uint64 s2;uint64 s3;uint64 s4;uint64 s5;uint64 s6;uint64 s7;uint64 s8;uint64 s9;uint64 s10;uint64 s11;
};

• 作用：保存内核态的上下文，用于在内核中切换进程或切换到调度器。

• 字段含义

  • ra：返回地址，保存调用 swtch() 时的返回点。
  • sp：栈指针，指向当前内核栈的位置。
  • s0-s11：RISC-V 的被调用者保存寄存器（callee-saved），按照 ABI 约定，由被调用函数保存。
  • 大小：14 个 64 位字段，共 112 字节。

• 使用场景

  • 内核上下文切换：
    • 当进程让出 CPU（例如调用 yield() 或睡眠），swtch()（kernel/swtch.S）保存当前进程的 context，然后加载调度器的 context。
    • 调度器（scheduler()）选择新进程后，swtch() 恢复新进程的 context。
  • 存储位置：
    • 每个进程的 struct proc 中有 struct context context。
    • 每个 CPU 的 struct cpu 中有 struct context context，用于切换到调度器。

• 特点

  • 只保存内核态必要的寄存器，不涉及用户态。
  • 不包括临时寄存器（如 t0-t6），因为它们是调用者保存的（caller-saved）。

struct trapframe

struct trapframe {/*   0 */ uint64 kernel_satp;   // kernel page table/*   8 */ uint64 kernel_sp;     // top of process's kernel stack/*  16 */ uint64 kernel_trap;   // usertrap()/*  24 */ uint64 epc;           // saved user program counter/*  32 */ uint64 kernel_hartid; // saved kernel tp/*  40 */ uint64 ra;/*  48 */ uint64 sp;/*  56 */ uint64 gp;/*  64 */ uint64 tp;/*  72 */ uint64 t0;/*  80 */ uint64 t1;/*  88 */ uint64 t2;/*  96 */ uint64 s0;/* 104 */ uint64 s1;/* 112 */ uint64 a0;/* 120 */ uint64 a1;/* 128 */ uint64 a2;/* 136 */ uint64 a3;/* 144 */ uint64 a4;/* 152 */ uint64 a5;/* 160 */ uint64 a6;/* 168 */ uint64 a7;/* 176 */ uint64 s2;/* 184 */ uint64 s3;/* 192 */ uint64 s4;/* 200 */ uint64 s5;/* 208 */ uint64 s6;/* 216 */ uint64 s7;/* 224 */ uint64 s8;/* 232 */ uint64 s9;/* 240 */ uint64 s10;/* 248 */ uint64 s11;/* 256 */ uint64 t3;/* 264 */ uint64 t4;/* 272 */ uint64 t5;/* 280 */ uint64 t6;
};

• 作用：保存用户态的完整上下文，并在用户态和内核态切换时传递必要信息。

• 字段含义

  • 内核相关字段（用于返回内核态）：
    • kernel_satp：内核页表的 satp 值。
    • kernel_sp：进程的内核栈顶地址。
    • kernel_trap：陷阱处理函数地址（usertrap()）。
    • kernel_hartid：当前 CPU 的 ID（保存 tp）。
  • 用户相关字段：
    • epc：用户程序计数器（sepc），保存陷阱发生时的指令地址。
    • ra, sp, gp, tp, t0-t6, s0-s11, a0-a7：用户态的全套通用寄存器。
  • 大小：35 个 64 位字段，共 280 字节。

• 使用场景

  • 用户到内核切换：
    • 发生陷阱（系统调用、中断、异常）时，trampoline.S 的 uservec 保存用户寄存器到 trapframe，加载内核字段，跳转到 usertrap()。
  • 内核到用户切换：
    • usertrapret() 设置 trapframe 的内核字段，userret 恢复用户寄存器，切换页表，返回用户态。
  • 存储位置：
    • 每个进程的 struct proc 中有 struct trapframe *trapframe，指向用户页表中的固定页面（TRAMPOLINE - PGSIZE）。

• 特点

  • 保存用户态所有寄存器，包括临时寄存器（t0-t6）和参数寄存器（a0-a7）。
  • 包含内核切换所需的信息。

struct context 和 struct trapframe 区别

在 xv6 中，struct context 和 struct trapframe 是两个关键的数据结构，用于保存寄存器状态以支持上下文切换。它们分别服务于不同的场景：context 用于内核态的上下文切换，而 trapframe 用于用户态和内核态之间的切换。以下我会详细对比它们的定义、作用、字段含义和使用场景，帮助你理解它们的区别和联系。

方面	struct context	struct trapframe
作用	内核态上下文切换	用户态到内核态切换
保存内容	内核寄存器（ra, sp, s0-s11）	用户寄存器 + 内核切换信息
寄存器范围	只保存被调用者保存寄存器	保存所有通用寄存器 + epc 等
大小	112 字节（14 个字段）	280 字节（35 个字段）
使用位置	proc->context, cpu->context	proc->trapframe（固定页面）
切换场景	进程间切换或切换到调度器	用户态和内核态之间的陷阱处理
代码实现	swtch.S	trampoline.S

struct cpu

// Per-CPU state.
struct cpu {struct proc *proc;          // The process running on this cpu, or null.struct context context;     // swtch() here to enter scheduler().int noff;                   // Depth of push_off() nesting.int intena;                 // Were interrupts enabled before push_off()?
};extern struct cpu cpus[NCPU];

• 字段含义

  • proc：指向当前 CPU 上运行的进程（struct proc），若为空则无进程运行。
  • context：保存 CPU 当前的内核上下文，用于切换到调度器。
  • noff：记录 push_off()（关闭中断）的嵌套层数。
  • intena：记录 push_off() 前中断是否启用，用于恢复时判断是否重新打开中断。

• 使用场景

  • 多核支持：cpus[NCPU] 是一个数组，每个 CPU 有独立的状态。
  • 调度器使用 context 切换到 scheduler()。
  • noff 和 intena 用于安全管理中断。

struct proc

enum procstate { UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };// Per-process state
struct proc {struct spinlock lock;// p->lock must be held when using these:enum procstate state;        // Process statevoid *chan;                  // If non-zero, sleeping on chan 用于进程的阻塞和唤醒int killed;                  // If non-zero, have been killed int xstate;                  // Exit status to be returned to parent's waitint pid;                     // Process ID// wait_lock must be held when using this:struct proc *parent;         // Parent process// these are private to the process, so p->lock need not be held.uint64 kstack;               // Virtual address of kernel stackuint64 sz;                   // Size of process memory (bytes) 用户程序大小pagetable_t pagetable;       // User page table 用户页表struct trapframe *trapframe; // data page for trampoline.S 用户态/内核态切换上下文trapframestruct context context;      // swtch() here to run process 进程之间的切换上下文contextstruct file *ofile[NOFILE];  // Open files 文件描述符表struct inode *cwd;           // Current directory char name[16];               // Process name (debugging)
};

字段含义

• 同步与状态（需持有 lock）：
  • lock：保护进程数据的自旋锁。
  • state：进程状态。
  • chan：睡眠时的等待通道。
  • killed：是否被杀死。
  • xstate：退出状态，传给父进程的 wait。
  • pid：进程 ID。
• 父进程（需持有 wait_lock）：
  • parent：指向父进程。
• 私有数据（无需锁）：
  • kstack：内核栈的虚拟地址。
  • sz：进程内存大小（字节）。
  • pagetable：用户页表。
  • trapframe：指向陷阱框架页面。
  • context：内核上下文。
  • ofile[NOFILE]：打开的文件描述符数组。
  • cwd：当前工作目录的 inode。
  • name[16]：进程名（调试用）。

给进程分配资源就是把资源记录在 PCB 中（比如文件描述符），进程的状态转移就是修改 PCB 的 state 字段。也就是说，管理进程就是管理 PCB。

进程状态

• UNUSED：表示该任务结构体未使用处于空闲状态，当要创建进程的时候就可以将这个结构体分配出去
• EMBRYO -> USED：该任务结构体刚分配出去，几乎什么资源都还没分配给该进程，所以设置为 USED 萌芽状态。使用这个状态是为了和 RUNNABLE 进行区分，表示 OS 正在进行进程初始化工作，初始化完毕后才会转设为 RUNNABLE。
• RUNNABLE：当进程需要的一切准备齐全之后就可以上 CPU 执行了，此时为 RUNNABLE 状态，表示就绪，能够上 CPU 执行。
• RUNNING：表示该进程正在 CPU 上执行，如果该时间片到了，则退下 CPU 变为 RUNNABLE 状态，如果运行过程中因为某些事件阻塞比如 IO 也退下 CPU 变为 SLEEPING 状态。
• SLEEPING：通常因为进程执行的过程中遇到某些事件阻塞通常就是 IO 操作，这时候调用 sleep 休眠使得进程处于 SLEEPING 状态，当事件结束比如 IO 结束之后调用 wakeup 就恢复到 RUNNABLE 状态，表明又可以上 CPU 执行了。还有一种情况是用户进程自己系统调用了 sleep，这个时候就要等待足够的时钟嘀嗒数才会 wakeup 唤醒用户进程。
• ZOMBIE：进程该干的活儿干完之后就会执行 exit 函数，也就是从 main 函数返回之后，由于进程是 shell 创建的，返回后会让他调用 exit。期间状态变为 ZOMBIE，这个状态一直持续到父进程调用 wait 来回收子进程资源。

初始化进程表

struct proc proc[NPROC];// initialize the proc table at boot time.
void
procinit(void)
{// 声明一个指向`struct proc`的指针，用于遍历进程表。struct proc *p;initlock(&pid_lock, "nextpid");initlock(&wait_lock, "wait_lock");for(p = proc; p < &proc[NPROC]; p++) {initlock(&p->lock, "proc");p->kstack = KSTACK((int) (p - proc));}
}

分配进程

// Look in the process table for an UNUSED proc.
// If found, initialize state required to run in the kernel,
// and return with p->lock held.
// If there are no free procs, or a memory allocation fails, return 0.
static struct proc*
allocproc(void)
{struct proc *p;for(p = proc; p < &proc[NPROC]; p++) {acquire(&p->lock);if(p->state == UNUSED) {goto found;} else {release(&p->lock);}}return 0;found:p->pid = allocpid();p->state = USED;// Allocate a trapframe page.if((p->trapframe = (struct trapframe *)kalloc()) == 0){freeproc(p);release(&p->lock);return 0;}// An empty user page table.p->pagetable = proc_pagetable(p);if(p->pagetable == 0){freeproc(p);release(&p->lock);return 0;}// Set up new context to start executing at forkret,// which returns to user space.memset(&p->context, 0, sizeof(p->context));p->context.ra = (uint64)forkret;p->context.sp = p->kstack + PGSIZE;return p;
}

进程的创建、退出、回收

进程创建：主要就是将 parent 进程的各种信息（用户地址空间内存及页表、用户上下文 trapframe、文件描述符等）复制给新进程。parent 进程会通过修改子进程 PCB 中的 trapframe→a0 来使子进程的 fork 系统调用返回 0。

// Create a new process, copying the parent.
// Sets up child kernel stack to return as if from fork() system call.
int
fork(void)
{int i, pid;struct proc *np;struct proc *p = myproc();// Allocate process.if((np = allocproc()) == 0){return -1;}// Copy user memory from parent to child.if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){freeproc(np);release(&np->lock);return -1;}np->sz = p->sz;// copy saved user registers.*(np->trapframe) = *(p->trapframe);// Cause fork to return 0 in the child.np->trapframe->a0 = 0;// increment reference counts on open file descriptors.for(i = 0; i < NOFILE; i++)if(p->ofile[i])np->ofile[i] = filedup(p->ofile[i]);np->cwd = idup(p->cwd);safestrcpy(np->name, p->name, sizeof(p->name));pid = np->pid;release(&np->lock);acquire(&wait_lock);np->parent = p;release(&wait_lock);acquire(&np->lock);np->state = RUNNABLE;release(&np->lock);return pid;
}

进程退出：xv6 进程 exit 时只是关闭了文件，并且设置退出码 xstate。调用 reparent 将该退出进程的子进程交给初始进程收养。其它资源的回收是由父进程负责的。

// Exit the current process.  Does not return.
// An exited process remains in the zombie state
// until its parent calls wait().
void
exit(int status)
{struct proc *p = myproc();if(p == initproc)panic("init exiting");// Close all open files.for(int fd = 0; fd < NOFILE; fd++){if(p->ofile[fd]){struct file *f = p->ofile[fd];fileclose(f);p->ofile[fd] = 0;}}begin_op();iput(p->cwd);end_op();p->cwd = 0;acquire(&wait_lock);// Give any children to init.reparent(p);// Parent might be sleeping in wait().wakeup(p->parent);acquire(&p->lock);p->xstate = status;p->state = ZOMBIE;release(&wait_lock);// Jump into the scheduler, never to return.sched();panic("zombie exit");
}

回收进程：

• wait 会遍历进程表，找到状态为 ZOMBIE 的子进程。
• 如果找到 ZOMBIE 子进程，会通过 freeproc 回收子进程占用资源,完成wait系统调用。
• 如果没有找到 ZOMBIE 子进程，父进程就会阻塞，等待某个子进程 exit 时唤醒自己，唤醒后重复上述过程（所以 wait 是阻塞的）

// Wait for a child process to exit and return its pid.
// Return -1 if this process has no children.
int
wait(uint64 addr)
{struct proc *np;int havekids, pid;struct proc *p = myproc();acquire(&wait_lock);for(;;){// Scan through table looking for exited children.havekids = 0;for(np = proc; np < &proc[NPROC]; np++){if(np->parent == p){// make sure the child isn't still in exit() or swtch().acquire(&np->lock);havekids = 1;if(np->state == ZOMBIE){// Found one.pid = np->pid;if(addr != 0 && copyout(p->pagetable, addr, (char *)&np->xstate,sizeof(np->xstate)) < 0) {release(&np->lock);release(&wait_lock);return -1;}freeproc(np);release(&np->lock);release(&wait_lock);return pid;}release(&np->lock);}}// No point waiting if we don't have any children.if(!havekids || p->killed){release(&wait_lock);return -1;}// Wait for a child to exit.sleep(p, &wait_lock);  //DOC: wait-sleep}
}

kill 进程

• kill 会遍历进程表，通过 pid 找到目标进程。
• 将目标进程 PCB 的 killed 字段置 1，如果目标进程被阻塞了，就将其 state 强制改为 RUNNABLE（就绪）
• 进程并不会被立刻杀死，进程在内核态返回用户态时（即发生在 usertrap 函数内部，比如系统调用返回）会检查自己的 killed 字段是否被置为 1，如果是，就主动执行 exit。

int
kill(int pid)
{struct proc *p;for(p = proc; p < &proc[NPROC]; p++){acquire(&p->lock);if(p->pid == pid){p->killed = 1;if(p->state == SLEEPING){// Wake process from sleep().p->state = RUNNABLE;}release(&p->lock);return 0;}release(&p->lock);}return -1;
}

CPU

进程调用的本质是该进程占用 CPU，因此我们需要获取 CPU 当前的进程 PCB。如果要获取 CPU 正在运行的进程 PCB，就需要借助 CPU 表了。

struct cpu cpus[NCPU];struct cpu {struct proc *proc;          // The process running on this cpu, or null.struct context context;     // swtch() here to enter scheduler().int noff;                   // Depth of push_off() nesting.int intena;                 // Were interrupts enabled before push_off()?
};

CPU 表中包含着各个 CPU 的运行信息（包含正在运行的进程）。在 OS 启动时，会将 CPU 号存储到寄存器里（kernel/start.c:50），编译器会保证内核代码不会乱动 tp 寄存器。所以在内核中，我们可以通过 tp 寄存器的值作为下标访问 CPU 表来获得当前 CPU 的信息，进而获取当前正在执行的进程（详见 myproc 函数）。

调度

操作系统通过进程调度使得各进程分时共享 CPU。进程被调度的原因有很多，比如时钟中断、被阻塞、主动让出 CPU（调用 yield 函数）等等。

调度的本质是将当前运行进程 A 的上下文保存至其进程控制块（PCB）中的 context 结构，随后从即将执行的进程 B 的 PCB 中的 context 加载其上下文，以实现进程间的无缝切换。：

• 保存当前进程的上下文：将当前运行进程（例如进程 A）的 CPU 寄存器状态保存到其 PCB 中。
• 加载新进程的上下文：从下一个要运行的进程（例如进程 B）的 PCB 中加载寄存器状态到 CPU。
• 结果：CPU 从进程 A 的执行点切换到进程 B 的执行点，看起来像是多个进程“同时”运行。

因此，进程的调度需要解决几个问题：

• 怎么选择下一个要执行的进程 => 调度算法。
• 进程调度应该由谁执行? => 调度器线程
• 怎么从当前进程切换到要执行进程 => 进程间上下文的切换

这涉及到几个重要函数：

• swtch：直接操作寄存器，完成上下文切换；是 scheduler 和 sched 的核心工具。
• sched：进程主动调用 swtch 返回调度器，表示进程的协作行为。
• scheduler：调度器，选择进程并调用 swtch 启动进程，表示 CPU 的主动调度行为。

进程 A (RUNNING)|v
sched() ----> 检查条件|           |v           v
swtch() ----> 保存 p_A->context|           |v           v
调度器 <---- 加载 c->context|v
循环 + intr_on()|v
找到进程 B (RUNNABLE)|v
状态 = RUNNING, c->proc = B|v
swtch() ----> 保存 c->context|           |v           v
进程 B <---- 加载 p_B->context|v
进程 B (RUNNING)

swtch

swtch 函数是由汇编语言编写的。它会将当前CPU的寄存器保存到context old中，并将 context new 加载到当前 CPU 的寄存器中。通过保存和恢复寄存器实现了上下文切换。

// 将将通用寄存器 ra 到 s11 的值保存到old->context
// 从new->context上下文结构中加载新任务的寄存器值到相应的通用寄存器中
void swtch(struct context *old, struct context *new);

# Context switch
#
#   void swtch(struct context *old, struct context *new);
# 
# Save current registers in old. Load from new.	.globl swtch
swtch:sd ra, 0(a0)sd sp, 8(a0)sd s0, 16(a0)sd s1, 24(a0)sd s2, 32(a0)sd s3, 40(a0)sd s4, 48(a0)sd s5, 56(a0)sd s6, 64(a0)sd s7, 72(a0)sd s8, 80(a0)sd s9, 88(a0)sd s10, 96(a0)sd s11, 104(a0)ld ra, 0(a1)ld sp, 8(a1)ld s0, 16(a1)ld s1, 24(a1)ld s2, 32(a1)ld s3, 40(a1)ld s4, 48(a1)ld s5, 56(a1)ld s6, 64(a1)ld s7, 72(a1)ld s8, 80(a1)ld s9, 88(a1)ld s10, 96(a1)ld s11, 104(a1)ret

进程 p 通过如下调用切换到调度器线程，即上图中的步骤 2：

swtch(&p->context, &mycpu()->context);

调度器线程通过如下调用切换到进程 p，即上图中的步骤 3：

swtch(&c->context, &p->context);

sched

// 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");// 检查当前 CPU 是否已经关闭了中断。如果没有，同样调用 panic 函数，因为 sched 函数不应该在中断未关闭的情况下被调用。if(mycpu()->noff != 1)panic("sched locks");// 检查当前进程的状态是否为 RUNNINGif(p->state == RUNNING)panic("sched running");if(intr_get())panic("sched interruptible");// 保存当前 CPU 的中断状态到变量 intena 中intena = mycpu()->intena;// 将将通用寄存器 ra 到 s11 的值保存到p->context// 从mycpu()->context上下文结构中加载新任务的寄存器值到相应的通用寄存器中swtch(&p->context, &mycpu()->context);// 恢复当前 CPU 的中断状态，使用之前保存的 intena 值mycpu()->intena = intena;
}

作用

• sched 是进程主动切换回调度器的函数，用于让当前进程交出 CPU。
• 它在进程状态改变后调用，确保安全切换。

使用场景：在 yield、sleep、exit 等函数中调用，让进程返回调度器。

进程调度：scheduler

OS 启动后，每个 CPU 完成初始化后就进入 scheduler 函数，这个过程的控制流不属于任何进程。为了方便。可以称这些控制流属于调度器线程（scheduler thread），调度器线程进入 scheduler 后就一直在 for 循环里面不断进行进程调度。

如前文所述，当进行进程调度的时候（比如时间片用完），要先由旧进程切换到 scheduler 线程上下文，由 scheduler 线程执行进程调度算法找到新进程，再切换到新进程。

// Per-CPU process scheduler.
// Each CPU calls scheduler() after setting itself up.
// 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);}}
}

上下文切换

下面介绍一下进程调度的整体流程，即上图中的过程：

进程 A 时间片用完，被时钟中断打断，进入内核。在内核中，进程 A 通过 swtch 切换到调度器控制流，调度器通过 swtch 切换到进程 B，完成了两个进程间的上下文切换。进程 B 切换到进程 A 同理。

时间片约 0.1 秒，即每 0.1 秒触发时钟中断。时钟中断强制当前用户进程调用 yield 函数，让出CPU。yield 将进行上下文切换，并回到调度函数 scheduler。

//
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
//
void
usertrap(void)
{int which_dev = 0;......// give up the CPU if this is a timer interrupt.if(which_dev == 2)yield();usertrapret();
}

// 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);
}

// 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;
}

参考

• xv6 book risc-v 第七章 调度 - yudoge - 博客园 (cnblogs.com)
• xv6-riscv-book-Chinese/Chapter-7.md at main · FrankZn/xv6-riscv-book-Chinese (github.com)