Process Switch Flow via Timer Interrupt in xv6

sequenceDiagram
    participant P1 as Process 1 (Running)
    participant T as Trampoline (trampoline.S)
    participant Trap as Trap Handler
    participant K as Kernel
    participant S as Scheduler
    participant P2 as Process 2 (Runnable)

    Note over P1: Running in user space
    
    Note over P1: Timer Interrupt!
    P1->>T: Vector through trampoline.S
    Note over T: uservec (kernel/trampoline.S)<br/>Save user registers<br/>Switch to kernel page table
    
    T->>Trap: usertrap() (kernel/trap.c)
    Note over Trap: Save user PC<br/>Handle interrupt
    
    Trap->>Trap: devintr() (kernel/trap.c)
    Note over Trap: Identify timer interrupt<br/>(which_dev = 2)
    
    Trap->>K: yield() (kernel/proc.c)
    Note over K: acquire(p->lock)
    Note over K: Set state = RUNNABLE
    
    K->>K: sched() (kernel/proc.c)
    Note over K: Verify locks & state
    
    K->>S: swtch() (kernel/swtch.S)
    Note over K,S: Save P1's registers<br/>Load scheduler's registers
    
    Note over S: scheduler() (kernel/proc.c)
    S->>S: Find RUNNABLE process
    
    S->>P2: swtch() (kernel/swtch.S)
    Note over S,P2: Save scheduler's registers<br/>Load P2's registers
    
    Note over P2: Set state = RUNNING
    Note over P2: release(p->lock)
    
    P2->>T: usertrapret() (kernel/trap.c)
    Note over T: userret (kernel/trampoline.S)<br/>Setup trapframe<br/>Switch to user page table
    
    T->>P2: Return to user space
    Note over P2: Running in user space

Flow Description with File Locations

1. Timer Interrupt and Trap Entry
   • Initial vector through trampoline.S (kernel/trampoline.S)
   • Trap handling setup in uservec (kernel/trampoline.S)
   • Switches to kernel page table and saves registers
2. Trap Handling (kernel/trap.c)
   • usertrap(): Main trap handler for user space interrupts
   • devintr(): Identifies interrupt source
   • For timer interrupt (which_dev = 2), proceeds to yield
3. Process Yield (kernel/proc.c)
   • yield(): Prepares process for switching

     // kernel/proc.c, line ~510
     void yield(void) {
     struct proc *p = myproc();
     acquire(&p->lock);
     p->state = RUNNABLE;
     sched();
     release(&p->lock);
     }
     

4. Scheduler Entry (kernel/proc.c)
   • sched(): Verifies conditions and initiates context switch

     // kernel/proc.c, line ~490
     void sched(void) {
     struct proc *p = myproc();
     if(!holding(&p->lock))
       panic("sched p->lock");
     // ... more checks ...
     swtch(&p->context, &mycpu()->context);
     }
     

5. Context Switch (kernel/swtch.S)
   • swtch: Assembly routine that saves and restores register contexts

     # kernel/swtch.S
     # void swtch(struct context *old, struct context *new);
     # Save current registers in old. Load from new.
     

6. Scheduler Operation (kernel/proc.c)
   • scheduler(): CPU scheduler that selects next process

     // kernel/proc.c, line ~440
     void scheduler(void) {
     // ... loop finding RUNNABLE processes ...
     swtch(&c->context, &p->context);
     }
     

7. Return to User Space (kernel/trap.c, kernel/trampoline.S)
   • usertrapret(): Sets up return to user space
   • Returns through userret in trampoline.S back to Process 2’s user context

Key Data Structures

• struct proc (kernel/proc.h): Process structure containing state, context, and other process information
• struct context (kernel/proc.h): Register save area for context switches
• struct trapframe (kernel/proc.h): Saved user registers during trap handling

The timer interrupt provides the preemption mechanism that enables xv6 to switch between processes automatically, even if processes don’t voluntarily give up the CPU. This is crucial for implementing time-sharing and preventing any single process from monopolizing the CPU.