BUAA OS Lab3 Exam

struct Env *env_create_edf(const void *binary, size_t size, int runtime, int period);

struct Env *env_create_edf(const void *binary, size_t size, int runtime, int period);
...

// diff --git a/kern/env.c b/kern/env.c
@@ -15,6 +15,9 @@ static struct Env_list env_free_list; // Free list
  // Invariant: 'env' in 'env_sched_list' iff. 'env->env_status' is 'RUNNABLE'.
  struct Env_sched_list env_sched_list; // Runnable list
 
+ // 注：由於 EDF 演算法不需要在隊尾插入或取出的操作，因此我們推薦使用 LIST 結構實現 EDF 排程佇列。
+ struct Env_edf_sched_list env_edf_sched_list; // EDF 排程佇列
+ 
  static Pde *base_pgdir;
  
  static uint32_t asid_bitmap[NASID / 32] = {0};
@@ -402,6 +405,31 @@ struct Env *env_create(const void *binary, size_t size, int priority) {
  	return e;
  }
 
+ struct Env *env_create_edf(
+     // 其中，引數 binary、size 與 env_create 函式中的定義相同
+     const void *binary, size_t size,
+     // runtime、period 為 EDF 排程引數，以時間片為單位：
+     // runtime 表示程序在每個週期內需要執行的時間
+     int runtime,
+     // period 表示程序的執行週期。
+     int period) {
+   struct Env *e;
+   /* ... */
+   env_alloc(&e, 0);
+ 
+   e->env_edf_runtime = runtime;
+   e->env_edf_period = period;
+   e->env_period_deadline = 0; // 初始化為 0，使程序在首次呼叫 schedule
+                               // 函式時觸發條件判斷，進入首個執行週期
+   e->env_status = ENV_RUNNABLE;
+ 
+   /* ... */
+ 	load_icode(e, binary, size);
+ 	LIST_INSERT_HEAD(&env_edf_sched_list, e, env_edf_sched_link);
+ 
+ 	return e;
+ }
+ 

  #include <pmap.h>
  #include <printk.h>
 
+ struct Env *last_rr_env;
 
  /* Overview:
   *   Implement a round-robin scheduling to select a runnable env and schedule it
   * using 'env_run'.
   * 'noreturn'.
   */
  void schedule(int yield) {
    static int count = 0; // remaining time slices of current env
-   struct Env *e = curenv;
 
    static int clock = -1; // 當前時間片，從 0 開始計數
+   clock++;
+   /* 在本題中，我們將 MOS 系統兩次時鐘中斷之間的間隔定義為一個時間片，
+    * 將 MOS 首次呼叫 schedule 函式直至下次時鐘中斷前的間隔作為第 0 個時間片，
+    * 再次呼叫 schedule 函式直至下次時鐘中斷前的間隔作為第 1 個時間片，以此類推。
+    */
+ 
+   /* (1) 遍歷 env_edf_sched_list，
+    * 如果程序進入了新的執行週期（可透過 clock == env_period_deadline 判斷），
+    * 則更新 env_period_deadline，
+    * 並將 env_runtime_left 設定為 env_edf_runtime。 */
+   /* 在此實現你的程式碼 */
+   struct Env *env; // 迴圈變數
+   LIST_FOREACH(env, &env_edf_sched_list, env_edf_sched_link) {
+     // 在這裡對 env 進行操作
+     // 此外，如果在某個週期內，
+     // 使用 EDF 演算法未能保證某程序執行完 runtime 個時間片，
+     // 則剩餘的時間片不會被保留至下一週期，而是直接作廢。
+     if (env->env_period_deadline == clock) {
+       env->env_period_deadline = clock + env->env_edf_period;
+       env->env_runtime_left = env->env_edf_runtime;
+     }
+   }
+ 
+   /* (2) 遍歷 env_edf_sched_list，
+    * 選取 env_runtime_left 大於 0 且 env_period_deadline 最小的程序排程
+    * （若相同，則選擇 env_id 最小的程序）。
+    * 如果不存在這樣的程序，則不進行排程。 */
+   /* 在此實現你的程式碼 */
+   u_int min_deadline = 11451419;
+   u_int curr_deadline;
+   struct Env *selected_env = NULL;
+   LIST_FOREACH(env, &env_edf_sched_list, env_edf_sched_link) {
+     // 在這裡對 env 進行操作
+     if (env->env_runtime_left > 0) {
+       curr_deadline = env->env_period_deadline;
+       if (curr_deadline < min_deadline) {
+         selected_env = env;
+       } else if (curr_deadline == min_deadline) {
+         // then selected_env is not NULL
+         if (selected_env->env_id > env->env_id)
+           selected_env = env;
+       }
+     }
+   }
+   /* printk("min_deadline %u\n", min_deadline); */
 
+   struct Env *e = last_rr_env;
+   struct Env *e_to_run;
+   // 請根據提示修改這行程式碼
+   /* We always decrease the 'count' by 1.
+    *
+    * If 'yield' is set, or 'count' has been decreased to 0, or 'e' (previous
+    * You may want to use macros below:
+    *   'TAILQ_FIRST', 'TAILQ_REMOVE', 'TAILQ_INSERT_TAIL'
+    */
+   /* 請將 Exercise 3.12 中的程式碼貼上至此 */
+   // 如果 EDF 排程佇列為空，或其中的所有程序均已執行完當前週期的時間片，
+   // 則使用課下實現的 RR 演算法排程 RR 排程佇列中的程序。
+   // 需要注意的是，EDF 排程的程序可以在任何時刻搶佔 RR 排程的程序，
+   // 且 RR 排程的程序執行的時間片在被 EDF 搶佔後不發生變化。
+   // 例如，如果 RR 演算法選擇排程一個優先順序為 5 的程序 A，
+   // 並已經使其執行了 3 個時間片，此時 EDF 佇列中產生了
+   // 可以被排程的程序 B，則程序 B 會搶佔程序 A 的執行，
+   // 直至程序 B 執行完當前週期的時間片後，程序 A 繼續執行剩餘的 2 個時間片。
+   if (selected_env != NULL) {
+     /* printk("b1: selected! \n"); */
+     /* printk("selected_env %u\n", selected_env->env_id); */
+     // 從 EDF 排程佇列選取程序後，你僅需使其執行一個時間片，
+     // 並在下個時鐘中斷產生時使用第二條規則，重新選擇程序排程。
+     // 本題中要實現的 EDF 排程演算法不受 yield 引數和程序優先順序的影響，
+     // 只與程序的截止時間有關。
+     e_to_run = selected_env;
+     selected_env->env_runtime_left -= 1;
+   }
    /* Exercise 3.12: Your code here. */
    // 判斷是否需要切換程序：
+   else {
     /* if (e != NULL) { */
     /* printk("b2: last rr is not NULL! \n"); */
     /* e_to_run = e; */
     /* count--; */
     /* ran_last = 1; */
     if (yield != 0 ||
         //     顯式請求讓出
         count == 0 ||
         //     時間片耗盡、
         e == NULL ||
         //     歷史沒有程序執行過、
         e->env_status != ENV_RUNNABLE
         //     當前程序已經不處於就緒狀態
     ) {
       /* printk("b3/n"); */
       // （4）如果當前程序 e 仍然“就緒”，則把它從佇列頭移到佇列尾，實現“輪轉”
       if (e != NULL && e->env_status == ENV_RUNNABLE) {
         TAILQ_REMOVE(&env_sched_list, e, env_sched_link);
         TAILQ_INSERT_TAIL(&env_sched_list, e, env_sched_link);
       }
       // （5）從排程佇列頭取下一個就緒程序
       e = TAILQ_FIRST(&env_sched_list);
       // （6）如果佇列為空，則沒有可執行的程序，直接 panic
       if (e == NULL) {
         panic("schedule: no runnable envs\n");
       }
       // （7）將新選中程序的時間片數初始化為其優先順序值
       count = e->env_pri;
       last_rr_env = e;
     }
     // （5）從排程佇列頭取下一個就緒程序
     e = TAILQ_FIRST(&env_sched_list);
     // （6）如果佇列為空，則沒有可執行的程序，直接 panic
     if (e == NULL) {
       panic("schedule: no runnable envs\n");
     }
     // （7）將新選中程序的時間片數初始化為其優先順序值
+    count = e->env_pri;
+    count--;
+    e_to_run = e;
   }
   // （8）消費一個時間片
   count--;
 
   // （9）真正切換執行到程序 e（這個呼叫不會返回）
-   env_run(e);
+   env_run(e_to_run);
  }