mit6.828筆記 - lab4 Part C:搶占式多任務和進程間通信（IPC）

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 完成