Day-26 xv6 Switch Thread, yield, sched

2022 iThome 鐵人賽

DAY 27

Software Development

與作業系統的第一類接觸 : 探索 xv6系列第 27 篇

14th鐵人賽 xv6 risc-v 作業系統

吳他，惟手熟爾

團隊那團名要叫什麼？

2022-10-12 22:33:23

737 瀏覽

分享至

前言

昨天我們簡單的介紹了 Thread 的一些基本概念，以及 Thread 是如何進行切換的，最後通過一個簡單的實驗去證明 compute bound thread 會因為 Timer Interrupt 而被切換，而其實在切換的過程中，會涉及到 yield(), sched() 以及 swtch() 這三個函式的相關操作，這一些部分將會在本篇進行介紹。

Switch Thread

我們這邊先大致上看過整個 Thread 的切換流程

首先在 Process P 的 Thread 會發生 Trap (依照昨天的舉例，我們是因為 Timer Interrupt 所導致的 Trap)，接著我們會進入到 yield()
在 yield() 當中，我們會去獲得 Process P 的 lock，接著改變 Process P 的狀態，將狀態設置成 RUNNABLE，並將 CPU 的 intena 域儲存，也就是儲存 CPU 在先前是否允許 Interrupt 發生
在 swtch() 中，我們會將 CPU 指向的 Process 設置為 NULL，也就是 cpu->proc = NULL，表示目前 CPU 處於閒置狀態，沒有執行任何 Process，接著將先前 Process P 的 lock 釋放，接著我們會進行一些處理 (下面再將這一部分展開解釋)，之後我們會重新獲得 Process P 的 lock，並將 Process P 的狀態設置成 RUNNING，表示我們先前處於 RUNNABLE 的 Process P，現在 CPU 處理完一些資源後，回來執行 Process P，並將 CPU 指向的 Process 設置成 P
到這邊 swtch() 結束，我們要回復 CPU 的 intena 域，並且釋放 Process P 的 lock
接著執行 sret，結束整個 trap

`yield()`

昨天我們通過這個實驗，得到 devintr() 會回傳 2 到 usertrap() 中，接著這個 2 會被存放到 whitch_dev 中，接著會進入到以下程式碼片段

if(which_dev == 2)
    yield();

接著我們便會進入到 yield() 中，以下為 yield() 的程式碼

void
yield(void)
{
  struct proc *p = myproc();
  acquire(&p->lock);
  p->state = RUNNABLE;
  sched();
  release(&p->lock);
}

可以看到首先我們會獲得目前 Process 的 lock，可以看到接下來我們將 Process 的狀態變更為 RUNNABLE，但實際上目前 Process 還在執行 (在 Kernel space 中作為 Kernel Thread 執行)，由於我們目前獲得了 lock，因此其他 CPU 的 Scheduler 並沒辦法看到目前的 Process 處於 RUNNABLE 並且嘗試去執行他 (因為受到 lock 保護，Scheduler 並無法看到受到 lock 保護的 Process 狀態)，這裡如果我們沒有使用 lock 對 Process 進行保護，很有可能兩個 CPU 同時去嘗試去執行這個 RUNNABLE 的 Process。

目前 Process 處於 RUNNABLE 狀態，表示目前 Process 需要讓出 CPU 的資源，RUNNABLE 意味著之後這個 Process 會再度執行 (如果 CPU 空閒時)，接著 yield() 會去呼叫 sched()。

`sched()`

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() 只進行了一些檢查 (檢查 lock 的狀態，Process 的狀態，Interrupt 的狀態)，如果發現到錯誤，則發生 panic，如果沒有發生問題，則會進入到 swtch() 中 (swtch() 為組合語言程式，之所以為組合語言程式，是因為我們沒辦法在 C 語言中直接更改 sp, ra 暫存器，只能通過一些內聯組合語言的技巧，但這其實就等同於使用組合語言了)。在 swtch() 結束後，我們會將 intena 儲存到目前的 CPU 中，intena 表示 Interrupt Enable，也就是允許 Interrupt 發生。

我們可以來看一下，在進入到 swtch() 之前的一些暫存器資訊，如 stack pointer

這邊可以看到在進入到 swtch() 之前，我們的 stack pointer 是在 0x3fffff7f80 的位置，可以通過這個位置知道，我們目前是在 kernel space 中。

`swtch()` 從 Process p 切換到 Scheduler Thread (context switch)

swtch() 完成的事情為將目前 CPU 的暫存器內容儲存到目前的 Process 底下，並且將新的 Process (要切換到的 Process 或是 Thread 或是 Scheduler Thread) 的暫存器內容寫入到目前的 CPU 中，以便後續執行新的 Thread。

Scheduler Thread:
指的是我們即將要切換到的 Thread，假設我們目前在 Thread A，要切換到 Thread B，則 Thread B 在這裡就是 Scheduler Thread。

.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

在 CPU 中存在 context 這個記憶體區域，用來儲存暫存器資訊，而在 proc 中也存在 context 這個記憶體區域。

這裡的概念正如同 trap from user space 中所提及的 uservec()，在 trap 中是將 User sapce 上的 Process (或是 User Thread) 的內容儲存到 proc 中的 trapframe 中，而這邊我們可以看到 swtch 實際上傳了兩個參數進來 (p 和 mycpu)，分別為 process 的 context 區域以及 mycpu 的 context 區域，這邊 swtch() 會將目前 CPU 的暫存器狀態儲存到 Process P 的 context 區域中。

可以看到 ra 暫存器儲存在 a0 暫存器的地址，回憶到 RISC-V 的 function call，a0 暫存器裡面存放的是 swtch() 的第一個參數，在這裡為 &p->context，a1 暫存器對應到第二個參數，在這裡為 &mycpu()->context。上半部的部分是將目前的暫存器內容儲存到目前 Process 底下的，也就是 &p->context 指向的 context 中，而下半部的部分是將 Scheduler Thread 的暫存器，也就是我們要切換到的 Thread 的暫存器內容回復到 CPU 的暫存器中 (也就是將 Scheduler Thread 的內容儲存在目前的 CPU 的 context 區域中)。接著函式結束，回到 ra 指向的記憶體地址。

這裡我們可以特別注意到 ra，也就是 return address 的部分，注意到這邊的 ra，指的是我們等一下要切換到的 Thread (Process) 的 context 區域中的 ra。

我們這邊把 cpus[0] 的 context 給印出來，得到 return address 為以下

可以看到 return address 為 0x8000149c，我們可以通過 kernel.asm 來看這是指向到何處

可以看到 return address 是指向到 scheduler() 這個 function，因此我們判斷等一下在 swtch() 結束之後會回到 scheduler() 當中 (注意到，這邊的 ra 指的是 cpus[0]->context->ra)。

在上方 swtch() 中我們可以發現到，相比於 trap from user space 中看到的 usertrap()，swtch() 短了許多，仔細看可以看到 swtch() 並沒有將所有 32 個暫存器的內容全部儲存下來，而是只儲存當中 14 個暫存器內容，且沒有儲存 Program counter，而這裡不儲存 Program counter 的原因為我們目前是在 swtch() 這個函式呼叫底下，Program counter 會隨著函式的進行，不斷的改變，因此我們不需要儲存 Program counter。

而只儲存 14 個暫存器內容，原因為 swtch() 為一個函式呼叫，在swtch()的呼叫者會預設 swtch() 會將暫存器的內容進行修改，正如同我們前面在許多地方可以看到，我們會先保存目前狀態的暫存器內容 (會先儲存在自己的 stack 當中)，接著進入到函式中，在函式回傳的時候再恢復暫存器內容，而同樣的道理，我們在 swtch() 結束之後，回到 Caller，也就是呼叫者時，他會恢復先前狀態的暫存器內容，所以在swtch()，也就是 Callee 只需要儲存自己暫存器的內容就可以了，也就是 Callee Saved Register，回顧 RISC-V 介紹的部分，我們可以看到 Callee Saved Register 為 s0 到 s11，這部分也就對應到上方 swtch() 的內容。

我們在意的，是誰去呼叫了 swtch()，是從哪一個函式呼叫了 swtch()，當我們結束 swtch() 時，回到呼叫點時，我們會回到的地方為 ra 暫存器所保存的記憶體地址，這邊我們前面看到我們是從 sched() 進入的，因此，ra 暫存器內容為 sched()

`ra` 內容的實驗

綜合我們剛剛上面的推論，在 Process P 的時候，我們目前 CPU ra 暫存器的內容應該要是呼叫 swtch() 的函式，也就是 sched()，我們下面可以驗證看看，驗證的方法就是觀察我們還在 swtch() 上半部的 CPU ra 暫存器的狀態

可以看到目前我們執行到 swtch() 的上半部分，而在這個狀態底下，ra 的確為 sched()。

而對於 Scheduler Thread 的驗證，只要我們讓 swtch() 執行到下半部分，也就是成功將 Scheduler Thread 的 context 儲存到 CPU 的暫存器中，我們便可以得到 Scheduler Thread 的 ra 了。

可以看到目前我們執行到 swtch() 的下半部分，而在這個狀態底下，ra 的確是 scheduler()，到這裡我們便實驗完畢了。

整個 swtch() 執行完成之後，我們現在就在 Scheduler Thread 裡面了，並且通過 ra 準備執行 scheduler()

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

現在，我們在 Scheduler Thread 中，我們回顧下面這一張圖

可以看到 parent pid = 3，child pid = 4，我們現在切換到 Scheduler Thread 中，也就是 pid = 4 的 Process (Thread)，而我們現在的狀態為 pid = 3 的 Process (Thread) 同樣也在執行 swtch()，但是還沒有回傳並結束，而是切換到了 pid = 4 的 Process (Thread) 中，可以想像到 pid = 3 的 Process (Thread) 的 context 現在儲存的為切換到 pid = 4 的 Process (Thread) 之前的 CPU 狀態。

現在我們已經停止了 TThread 的執行，所以我們讓 cpu->proc = 0，這裡的 0 為 NULL 的概念，也就是 CPU 現在沒有執行任何 Process，處在閒置狀態，接著我們啟用 Interrupt，並遍歷整個 proc[]，首先我們會先去獲得 lock，接著查看 proc[] 中的每一個 Process 是否為 RUNNABLE 的狀態，如果是處於 RUNNABLE 的狀態，則我們會讓該 Process 獲取 CPU 的資源，也就是 c->proc = p，接著將該 Process 設置成 RUNNING 的狀態，接著我們便可以使用 swtch() 嘗試切換到該 Thread 中了。

而對於 pid = 3 的 Process (Thread)，他會執行 sret 並且回到 sched，接著回到 yield()，yield() 會將 lock 給釋放，這時候所有 CPU 就可以看到 pid = 3 的 Process (Thread) 為 RUNNABLE 的狀態了，也就是 pid = 3 的 Process (Thread) 可以獲得其他 CPU 的資源，並且進入到 RUNNING 的狀態。

而下面我們可以實驗看看，假設以下情況

我們接下來經過了 swtch()，進行 Thread 切換 (也就是我們在 scheduler() 中看到的 swtch())

經過切換之後，我們依然在 TThread 的 Process 當中 (可以看到在 TThread 中我們又多輸出了一個字元)，但是我們的 pid 已經從 5 改變成 4 了，這裡我們便看到 Thread Switch。

我們這裡可以看一下這時候的 ra 暫存器的狀態

可以看到 pid = 4 的 Process (Thread) 的 ra 為 sched()，而原因為我們在切換 Thread 之前，是因為 Timer Interrupt 所造成的，而 Timer Interrupt 會使用 yield() 去改變 Process 的狀態，這一點可以從 gdb 的 backtrace 中看到。