Part C:搶占式多任務和進程間通信(IPC lab4到目前為止,我們能夠啟動多個CPU,讓多個CPU同時處理多個進程。實現了中斷處理,並且實現了用戶級頁面故障機制以及寫時複製fork。 但是,我們的進程調度不是搶占式的,現在每個進程只有在發生中斷的時候,才會被調度(調用shed_yeild),這 ...
Part C:搶占式多任務和進程間通信(IPC
lab4到目前為止,我們能夠啟動多個CPU,讓多個CPU同時處理多個進程。實現了中斷處理,並且實現了用戶級頁面故障機制以及寫時複製fork。
但是,我們的進程調度不是搶占式的,現在每個進程只有在發生中斷的時候,才會被調度(調用shed_yeild),這樣就有可能會有進程一直占用CPU不放。我們希望能夠讓各個進程平分CPU,在各個時間片上處理自己的任務。
於是實驗室 4 的最後一部分,我們的任務就是修改內核,實現搶占式多進程調度,並實現進程間通信機制(IPC)。
1. 時鐘中斷和搶占
我們為什麼需要搶占式的進程調度?如果有進程一直占用CPU會是什麼情況,user/spin.c就是個例子。看看 user/spin.c
嘗試在命令行跑 make run-spin 會發現,父進程fork之後再也無法執行了。這是因為我們的內核目前還沒有從未完成的進程中搶回控制的能力。
那時鐘中斷去哪了呢?
手冊:
與 xv6 Unix 相比,我們在 JOS 中做了一個關鍵的簡化。在內核中,外部設備中斷始終處於禁用狀態(與 xv6 一樣,在用戶空間中處於啟用狀態)。外部中斷由 %eflags 寄存器(參見 inc/mmu.h)的 FL_IF 標誌位控制。該位被設置時,外部中斷被啟用。 雖然可以通過多種方式修改該位,但為了簡化操作,我們將僅通過在進入和離開用戶模式時保存和恢復 %eflags 寄存器的過程來處理它。您必須確保在用戶環境中運行時設置 FL_IF 標誌,以便在中斷發生時將其傳遞給處理器,並由您的中斷代碼進行處理。 否則,中斷將被屏蔽或忽略,直到中斷被重新啟用。我們在啟動載入程式的第一條指令中就屏蔽了中斷,到目前為止,我們還從未重新啟用過中斷。
我們在啟動載入程式的第一條指令中就屏蔽了中斷,到目前為止,我們還從未重新啟用過中斷。
接下來的任務,我們要完善外部中斷的管理,
1.1 中斷管理
外部中斷(即設備中斷)稱為 IRQ。有 16 個可能的 IRQ,編號從 0 到 15。從 IRQ 編號到 IDT 條目之間的映射關係並不固定。picirq.c 中的 pic_init 將 IRQ 0-15 映射到 IDT 條目 IRQ_OFFSET 至 IRQ_OFFSET+15。
在 inc/trap.h 中,IRQ_OFFSET 被定義為十進位 32。因此,IDT 項 32-47 對應 IRQ 0-15。例如,時鐘中斷是 IRQ 0,因此 IDT[IRQ_OFFSET+0](即 IDT[32])包含內核中時鐘中斷處理程式常式的地址。選擇這個 IRQ_OFFSET,是為了避免設備中斷與處理器異常重疊,以免造成混淆。(事實上,在早期運行 MS-DOS 的 PC 中,IRQ_OFFSET 實際上為 0,這確實造成了處理硬體中斷和處理處理器異常之間的大量混淆!)。
與 xv6 Unix 相比,我們在 JOS 中做了一個關鍵的簡化。在內核中,外部設備中斷始終處於禁用狀態(與 xv6 一樣,在用戶空間中處於啟用狀態)。外部中斷由 %eflags 寄存器(參見 inc/mmu.h)的 FL_IF 標誌位控制。該位被設置時,外部中斷被啟用。 雖然可以通過多種方式修改該位,但為了簡化操作,我們將僅通過在進入和離開用戶模式時保存和恢復 %eflags 寄存器的過程來處理它。
您必須確保在用戶環境中運行時設置 FL_IF 標誌,以便在中斷發生時將其傳遞給處理器,並由您的中斷代碼進行處理。 否則,中斷將被屏蔽或忽略,直到中斷被重新啟用。我們在啟動載入程式的第一條指令中就屏蔽了中斷,到目前為止,我們還從未重新啟用過中斷。
Exercise 13
練習 13. 修改 kern/trapentry.S 和 kern/trap.c,初始化 IDT 中的相應條目,併為 IRQ 0 至 15 提供處理程式。然後修改 kern/env.c 中 env_alloc() 的代碼,以確保用戶環境始終在啟用中斷的情況下運行。
同時取消對 sched_halt() 中 sti 指令的註釋,以便空閑的 CPU 能解除中斷屏蔽。
在調用硬體中斷處理程式時,處理器絕不會推送錯誤代碼。此時,您可能需要重新閱讀《80386 參考手冊》第 9.2 節或《IA-32 英特爾體繫結構軟體開發人員手冊》第 3 捲第 5.8 節。
完成此練習後,如果使用任何運行時間較長(如自旋)的測試程式運行內核,就會看到內核列印硬體中斷的陷阱幀。雖然中斷已在處理器中啟用,但 JOS 還沒有處理它們,所以你會看到它將每個中斷錯誤地歸屬於當前運行的用戶環境,並將其銷毀。最終,它應該會用完要銷毀的環境,並將其放入監視器中。
在 trapentry.S
設置外部中斷處理函數的入口點:
# 外部中斷的入口點
TRAPHANDLER_NOEC(irq_error_handler, IRQ_OFFSET+IRQ_ERROR)
TRAPHANDLER_NOEC(irq_ide_handler, IRQ_OFFSET+IRQ_IDE)
TRAPHANDLER_NOEC(irq_kbd_handler, IRQ_OFFSET+IRQ_KBD)
TRAPHANDLER_NOEC(irq_serial_handler, IRQ_OFFSET+IRQ_SERIAL)
TRAPHANDLER_NOEC(irq_spurious_handler, IRQ_OFFSET+IRQ_SPURIOUS)
TRAPHANDLER_NOEC(irq_timer_handler, IRQ_OFFSET+IRQ_TIMER)
在 trap.c:trap_init()
中定義外部設備中斷的handler
//初始化外部中斷的中斷向量
void irq_error_handler();
void irq_kbd_handler();
void irq_ide_handler();
void irq_timer_handler();
void irq_spurious_handler();
void irq_serial_handler();
SETGATE(idt[IRQ_OFFSET + IRQ_ERROR], 0, GD_KT, irq_error_handler, 3);
SETGATE(idt[IRQ_OFFSET + IRQ_IDE], 0, GD_KT, irq_ide_handler, 3);
SETGATE(idt[IRQ_OFFSET + IRQ_KBD], 0, GD_KT, irq_kbd_handler, 3);
SETGATE(idt[IRQ_OFFSET + IRQ_SERIAL], 0, GD_KT, irq_serial_handler, 3);
SETGATE(idt[IRQ_OFFSET + IRQ_SPURIOUS], 0, GD_KT, irq_spurious_handler, 3);
SETGATE(idt[IRQ_OFFSET + IRQ_TIMER], 0, GD_KT, irq_timer_handler, 3);
修改 env.c:env_alloc
,在用戶環境運行前開啟外部設備中斷,在註釋提示處添加語句:
// Enable interrupts while in user mode.
// LAB 4: Your code here.
// 開啟用戶環境的外部設備中斷
e->env_tf.tf_eflags |= FL_IF;
修改 kern/sched.c:sched_halt,將提示處的sti語句註釋取消掉,sti 指令是開中斷,如手冊中所述,我們在 bootloader 中第一條指令 cli 就屏蔽了外部中斷,到目前為止還沒有重新開啟外部中斷。
sched_halt 這個讓CPU陷入自旋,等待被timer打斷。不開外部中斷是不可能做到被搶斷的。
完成了這些我們再次嘗試 make run-spin
1.2 處理時鐘中斷
在 user/spin
程式中,子環境首次運行後,只是在迴圈中 spin,內核再也無法控制。
我們需要對硬體進行編程,使其周期性地產生時鐘中斷,從而迫使控制權回到內核,在內核中我們可以將控制權切換到不同的用戶環境。
lapic_init
和 pic_init
中設置了時鐘和中斷控制器以產生中斷。現在我們需要編寫代碼來處理這些中斷。
Exercise 14
練習 14. 修改內核的 `trap_dispatch()` 函數,使其在發生時鐘中斷時調用 `sched_yield()`,查找並運行不同的環境。
現在您應該可以讓用戶/自旋測試正常工作了:父環境應該分叉子環境,向其執行幾次 `sys_yield()`,但每次都會在一個時間片後重新獲得 CPU 的控制權,最後殺死子環境並優雅地終止。
目前我們已經在中斷向量表中添加了接受timer信號的中斷描述符,timer中斷發生後,控制流會來到trap,然後發往 trap_dispatch,但是 trap_dispatch 中還沒有對應的hander接應,所以現在要在 trap_dispatch 中處理timer的中斷信號。
// Handle clock interrupts. Don't forget to acknowledge the
// interrupt using lapic_eoi() before calling the scheduler!
// LAB 4: Your code here.
if(tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER)
{
cprintf("Timer interrupt on irq 0\n");
lapic_eoi();
sched_yield();
}
lapic_eoi()
函數的作用是開啟IF標誌位,接收外部中斷,具體原理:
在接收到中斷請求並處理完成後,向本地高級可編程中斷控制器(Local Advanced Programmable Interrupt Controller, LAPIC)發送一個 EOI 命令,通知 LAPIC 中斷處理已完成。這是為了釋放中斷控制器的資源,以便處理下一個中斷。
但是好奇怪,進入trapentry.S 時候,從來沒見過我們主動清零IF啊,為什麼CPU自動關閉接收外部中斷了呢?
翻了一下386手冊,其中提到
中斷門和陷阱門的區別在於對 IF(中斷啟用標誌)的影響。矢量通過中斷門的中斷會重置 IF,從而防止其他中斷干擾當前中斷處理程式。隨後的 IRET 指令將 IF 恢復為堆棧上 EFLAGS 映像中的值。通過陷阱門的中斷不會改變 IF。
功能上的區別是這樣,那格式上呢?
我們在trap_init 設置的全是中斷門
這個時候我們再次嘗試 make run-spin ,會發現程式可以正常執行了:
2. 進程間通信(IPC)
我們一直在關註操作系統的隔離功能,即它能讓人產生一種錯覺,以為每個程式都擁有一臺獨享的機器。操作系統的另一項重要功能是允許程式在需要時相互通信。讓程式與其他程式進行交互是一項非常強大的功能。Unix 管道模型就是一個典型的例子。
進程間通信有許多模型。時至今日,人們仍在爭論哪種模式最好。我們不討論這個問題。相反,我們將實現一個簡單的 IPC 機制,然後進行嘗試。
2.1 JOS 的進程間通信
JOS已經實現了幾個額外的JOS內核系統調用,它們共同提供了一個簡單的進程間通信機制。
用戶需要實現兩個系統調用, sys_ipc_recv
和 sys_ipc_try_send
。
然後我們將實現兩個庫包裝器 ipc_recv
和 ipc_send
。(話說,我們已經見識過了這種包裝器,比如 set_pgfault_handler
是 sys_env_set_pgfault_upcall
的包裝器,在其包裝下,為我們簡化了用戶異常棧的清理和 trap-time 狀態的恢復工作)
用戶環境可以使用JOS的IPC機制相互發送的“消息”由兩個部分組成:單個32位值
和可選的單個頁映射
。允許進程以消息的形式傳遞頁映射,這提供了一種高效的方式來傳輸比單個32位整數所能容納的更多的數據,還允許進程輕鬆地建立共用記憶體。
2.2 發送和接收消息
為接收消息,進程調用 sys_ipc_recv
。該系統調用會掛起當前進程,直到收到消息後才再次運行。
當一個進程等待接收消息時,任何其他進程都可以向它發送消息——不僅僅是特定的進程,也不僅僅是與接收進程有父/子關係的進程。
換句話說,我們在 Part A 實現的許可權檢查不適用於IPC,因為IPC系統調用經過了精心設計,是“安全的”:一個進程不會僅僅通過向它發送消息就導致另一個進程故障(除非目標進程也有bug)。
要嘗試發送一個值,進程會調用 sys_ipc_try_send
,指定接受者的進程ID和要發送的值。
如果目標進程上正在接收(它調用了 sys_ipc_recv
,但還沒有得到值),那麼調用者這邊的 send 就會發送信息,並返回 0。否則,send 返回 -E_IPC_NOT_RECV
表示目標進程當前不希望收到值。
用戶空間中的庫函數 ipc_recv
負責調用 sys_ipc_recv
,然後在當前環境的 struct Env
中查找接收到的值的信息。
類似地,庫函數 ipc_send
將負責重覆調用 sys_ipc_try_send
,直到發送成功。
2.3 發送記憶體頁
當進程使用有效的 dstva
參數(低於 UTOP)調用 sys_ipc_recv
,即表明進程願意接收頁面映射。
如果發送方發送了一個頁面,那麼該頁面應映射到接收方地址空間中的 dstva
處。
如果接收方已經在 dstva 處映射了一個頁面,那麼之前的頁面將被取消映射。
當環境以有效的 srcva
(低於 UTOP)調用 sys_ipc_try_send
,這意味著發送方希望將當前映射在 srcva
上的頁面發送給接收方,並且許可權為 perm
。IPC 成功後,發送方在其地址空間中保留了位於 srcva 的頁面的原始映射,但接收方也在其地址空間中獲得了位於接收方最初指定的 dstva 的同一物理頁面的映射。因此,該頁面成為發送方和接收方共用的頁面。
如果發送方或接收方都沒有表示應該傳輸頁面,那麼就不會傳輸頁面。在任何 IPC 之後,內核都會將接收方 Env 結構中的新欄位 env_ipc_perm
設置為所接收頁面的許可權,如果沒有接收頁面,則設置為 0。
Exercise 15 實現IPC
練習 15. 執行 `kern/syscall.c` 中的 `sys_ipc_recv` 和 `sys_ipc_try_send`。
在執行之前,請閱讀有關這兩個常式的註釋,因為它們必須協同工作。
在這些常式中調用 `envid2env` 時,應將 `checkperm` 標誌設置為 0,這意味著任何環境都可以向任何其他環境發送 IPC 消息,內核除了驗證目標 `envid` 是否有效外,不會進行任何特殊的許可權檢查。
然後在 `lib/ipc.c` 中實現 `ipc_recv` 和 `ipc_send` 函數。
使用 `user/pingpong` 和 `user/primes` 函數測試你的 IPC 機制。`user/primes` 會為每個質數生成一個新環境,直到 JOS 用完環境為止。閱讀 user/primes.c,瞭解所有分叉和 IPC 的幕後工作,你可能會覺得很有趣。
在 kern/syscall.c 中實現 sys_ipc_try_send
。
按照註釋進行一系列檢查後將 srcva 所在的 pg ,映射到 dstva 所在的地址。
// 嘗試將 “value ”發送到目標環境 “envid”。
// 如果 srcva < UTOP,則同時發送當前映射到 “srcva ”的頁面,以便接收者獲得同一頁面的重覆映射。
// 如果目標沒有被阻塞,正在等待 IPC,則發送失敗,返回值為 -E_IPC_NOT_RECV。
// 發送失敗的原因還包括下麵列出的其他原因。
// 否則,發送成功,目標的 ipc 欄位更新如下:
// env_ipc_recving 設置為 0 以阻止今後的發送;
// env_ipc_from 設置為發送的 envid;
// env_ipc_value 設置為參數 “value”;
// 如果傳輸了頁面,env_ipc_perm 設置為 “perm”,否則為 0。
// 目標環境再次被標記為可運行,返回 0。
// 從暫停的 sys_ipc_recv 系統調用中返回 0。 (提示:如果
// sys_ipc_recv 函數真的會返回嗎?)
//
// 如果發送方想發送頁面,但接收方沒有要求發送,則不會傳輸頁面映射,但也不會發生錯誤。
// 只有在沒有錯誤發生時,ipc 才會發生。
//
// 成功時返回 0,錯誤時返回 <0。
// 錯誤是
// -E_BAD_ENV 如果環境 envid 當前不存在。
// (無需檢查許可權。)
// -E_IPC_NOT_RECV 如果 envid 當前未在 sys_IPC_recv 中阻塞、
// 或其他環境先發送。
// -E_INVAL 如果 srcva < UTOP 但 srcva 不是頁面對齊的。
// -E_INVAL 如果 srcva < UTOP 並且 perm 不合適
// (參見 sys_page_alloc)。
// -E_INVAL 如果 srcva < UTOP 但 srcva 沒有映射到調用者的 // 地址空間。
// 地址空間。
// -E_INVAL 如果(perm & PTE_W),但 srcva 在 // 當前環境的地址空間中是只讀的。
// 當前環境的地址空間中是只讀的。
// -E_NO_MEM 如果沒有足夠的記憶體將 srcva 映射到 envid 的 // 地址空間。
// 地址空間。
static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
// LAB 4: Your code here.
// panic("sys_ipc_try_send not implemented");
int r;
struct Env * env;
if((r = envid2env(envid, &env, 0))< 0){
return -E_BAD_ENV;
}
if(env->env_ipc_recving == 0){
return -E_IPC_NOT_RECV;
}
if (srcva < (void*)UTOP) {
// 獲取物理頁
pte_t *pte;
struct PageInfo *pg = page_lookup(curenv->env_pgdir, srcva, &pte);
// 檢查 srcva 是否 page-aligned.
if(srcva != ROUNDDOWN(srcva, PGSIZE)){
return -E_INVAL;
}
// 檢查 perm 是否合規
if((*pte & perm & PTE_SYSCALL)!= (perm & PTE_SYSCALL)){
return -E_INVAL;
}
// 如果來源環境沒有映射pg頁
if(!pg){
return -E_INVAL;
}
// 如果perm要求寫許可權,但是srcva沒有寫許可權
if ((perm & PTE_W) && !(*pte & PTE_W)){
return -E_INVAL;
}
// 如果目標環境以有效dstva參數調用 sys_ipc_recv,說明目標環境願意接受頁面映射
if (env->env_ipc_dstva < (void*)UTOP) {
// 將當前環境的 pg 頁 映射到目標環境的dstva上
r = page_insert(env->env_pgdir, pg, env->env_ipc_dstva, perm);
if(r<0){
return -E_NO_MEM;
}
env->env_ipc_perm = perm;
}
}
// 標記目標環境為 未準備接收
env->env_ipc_recving = 0;
// 將目標環境的 IPC發送方 設置為當前環境
env->env_ipc_from = curenv->env_id;
// 發送 message 的 value
env->env_ipc_value = value;
// 設置目標環境為可運行
env->env_status = ENV_RUNNABLE;
// 設置目標環境的eax
env->env_tf.tf_regs.reg_eax = 0;
return 0;
}
sys_ipc_recv 則是設置env的與IPC相關的成員,關鍵是env_ipc_recving=1,標記為準備接受數據。
然後調用 sched_yield 交出cpu,等待sender發送數據
// 阻塞,直到值準備就緒。
// 使用 struct Env 的 env_ipc_recving 和 env_ipc_dstva 欄位記錄要接收的信息,
// 標記自己不可運行,然後放棄 CPU。
//
// 如果'dstva'<UTOP,則表示願意接收一頁數據。
// 'dstva'是虛擬地址,發送的頁面應映射到該地址。
//
// 該函數僅在出錯時返回,但系統調用最終會在成功時返回 0。
// 出錯時返回 <0。 錯誤包括
// -E_INVAL 如果 dstva < UTOP 但 dstva 不是頁面對齊的。
static int
sys_ipc_recv(void *dstva)
{
// LAB 4: Your code here.
// panic("sys_ipc_recv not implemented");
if ((uintptr_t)dstva < UTOP && PGOFF(dstva) != 0){
return -E_INVAL;
}
// 標識正在等待接收消息
curenv->env_ipc_recving = 1;
// 記錄想要映射頁的虛擬地址
curenv->env_ipc_dstva = dstva;
// 清空記錄的發送者信息
curenv->env_ipc_value = 0;
curenv->env_ipc_from = 0;
curenv->env_ipc_perm = 0;
// 設置 Env 狀態,在env_ipc_recving被改變之前,不再被喚醒
curenv->env_status = ENV_NOT_RUNNABLE;
// 交出控制權,等待數據輸入
sched_yield();
return 0;
}
然後不要忘了在 syscall 的 switch 中加上相關調用的分支:
case SYS_ipc_try_send:
ret = sys_ipc_try_send((envid_t) a1, (uint32_t) a2, (void *) a3, (unsigned int) a4);
return ret;
case SYS_ipc_recv:
ret = sys_ipc_recv((void*)(a1));
return ret;
接著去用戶的lib/ipc.c 中實現相應庫函數。
// 通過 IPC 接收並返回值。
// 如果 “pg ”為非空,則發送方發送的任何頁面都將映射到該地址。
// 如果 “from_env_store ”為非空,則將 IPC 發送方的 envid 保存在 *from_env_store 中。
// 如果 “perm_store ”為非空,則在 *perm_store 中存儲 IPC 發送方的頁面許可權(如果頁面已成功傳輸到 “pg”,則該值為非零)。
// 如果系統調用失敗,則在 *fromenv 和 *perm(如果它們非空)中存儲 0,並返回錯誤信息。
// 否則,返回發送者發送的值
//
// 提示
// 使用 “thisenv ”發現值和發送者。
// 如果'pg'為空,則向 sys_ipc_recv 傳遞一個它可以理解為 “無頁面 ”的值。
// 表示 “無頁面”。 (零不是正確的值,因為這是
// 一個完全有效的頁面映射位置)。
int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
// LAB 4: Your code here.
// panic("ipc_recv not implemented");
// 檢查pg是否為空
if(pg == NULL)
{
pg=(void *) -1;
}
//接收 message
int r = sys_ipc_recv(pg);
if(r<0)
{
if(from_env_store) *from_env_store = 0;
if(perm_store) *perm_store = 0;
return r;
}
// 保存發送者的envid
if(from_env_store) *from_env_store = thisenv->env_ipc_from;
// 保存發送來的頁面的許可權
if(perm_store) *perm_store = thisenv->env_ipc_perm;
// 返回message的value
return thisenv->env_ipc_value;
}
// 將'val'(如果'pg'非空,則將'pg'與'perm'一起)發送到'toenv'。
// 該函數會不斷嘗試,直到成功為止。
// 如果出現除 -E_IPC_NOT_RECV 以外的任何錯誤,它都會 panic()。
//
// 提示
// 使用 sys_yield()對 CPU 更友好。
// 如果 “pg ”為空,則向 sys_ipc_try_send 傳遞一個它能理解為 “無頁面 ”的值。
// 表示 “無頁面”。 (零值並不合適)。
void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
// LAB 4: Your code here.
// panic("ipc_send not implemented");
// 如果pg為NULL, 要提供給sys_ipc_try_send一個能表達“no page”的值,0是有效的地址
if(pg==NULL)
{
pg = (void *)-1;
}
int r;
//不停嘗試發送消息直到成功
while(1)
{
r = sys_ipc_try_send(to_env, val, pg, perm);
if (r == 0) { //發送成功
return;
} else if (r == -E_IPC_NOT_RECV) { //接收環境未準備接收
sys_yield();
}else{
panic("ipc_send() fault:%e\n", r);
}
}
}
lab4 完成