[CareerCup] 16.2 Measure Time in a Context Switch 測量上下文轉換的時間

16.2 How would you measure the time spent in a context switch?

上下文轉換發生在兩個程序之間，比如讓一個等待程序進入執行和讓一個運作程序進入等待，這些在多任務中發生。作業系統需要把等待程序的資訊放入記憶體和把目前運作的程序資訊儲存下來。為了解決這個問題，我們記錄在切換程序時的最後和第一個指令的時間點，比如我們有兩個程序P1和P2，P1在執行P2在等待，當我們切換P1和P2時，假設發生在P1的第N個指令，我們用tx,k來表示程序x的第k個指令的時間點，那麼切換的時間為t2,1-t1,n。

那麼問題是我們怎麼知道什麼時候轉換發生，我們又不能記錄程序的每個指令的時間點。另外還有轉換是由作業系統的安排算法管理的，而且有很多核心線程也要用上下文轉換。其他程序也可能競争CPU或核心進行中斷。使用者不能控制外部的上下文轉換，比如在時間t1,n，核心決定進行中斷，那麼上下文轉換的時間就會延長。為了克服這些困難，我們需要建立一個上下文使得P1執行完，P2馬上就能運作。我們可以建立一個資料通道Data Chanel，例如管道Pipe，在P1和P2之間，就像兩個程序在打乒乓球，使用資料權标Data Token。

我們讓P1當發送者，P2當接受者。開始時，P2在等待，當P1執行了，它發送了資料權标給P2，然後等着讀取一個回執。但是由于P2還沒能執行，是以P1沒有回執，進行被阻礙了，釋放了CPU。上下文轉換發生了，任務配置設定器必須選另一個程序執行，且P2處于準備執行狀态。當P2運作了，P1和P2的角色互換了，P2現在是發送者而P1是接受者，當P2發回執給P1，整個過程就完成了：

1. P2等待P1發送消息。

2. P1記錄時間點。

3. P1給P2發送消息。

4. P1試圖讀取回執，這包括了一個上下文轉換。

5. P2準備就緒并接到了消息。

6. P2發送回執給P1。

7. P2嘗試讀取P1的回執，這包括了一個上下文轉換。

8. P1準備就緒且接到了消息。

9. P1記錄時間點。

那麼步驟2到9之間的時間差T，表示為T = 2 * (Td + Tc + Tr)，其中Td和Tr表示發送和接受消息時間，Tc表示狀态轉換的時間。那麼現在問題是要求Td + Tr的值，即為P1發送資訊給自己到接受到消息的時間，這不包括狀态轉換的時間因為是發給自己。由于可能存在的未知中斷，是以我們需要重複多次，取最小的Tc當做結果。

這也隻是一個近似結果，因為我們這麼做有個假設就是當P2接到消息後馬上就開始運作，這得根據任務配置設定器的實作方法，是以隻是個近似值。