程式扎記: [ Nachos 4.0 ] Nachos System : Round-Robin Scheduling

標籤

2013年6月11日 星期二

[ Nachos 4.0 ] Nachos System : Round-Robin Scheduling

Preface: 
在原始的 Nachos 中的 short term scheduling 採用的是 First­ Come, First ­Served (FCFS) 的機制, 在這個 Project 我們要修改這個機制成 "priority-FIFO with round-robin". 在這個機制中會有多個 Priority Queue, 每個 task 會給定 priority (0~255), priority 的數字越小說明越優先; 每次都會從 priority 較高的 queue 開始取 task 出來處理, 優先權較低的 queue 要等優先權較高的 queue 都處理完後才會輪到它們; 每個 queue 都使用 round-robin 機制來取出 task; 在這個機制中還有一個屬性 time splice, 每個 task 最多只會執行 time splice 的時間. 底下為範例: 
 
* P1 為 Priority1 的 task
* P2 與 P3 為 Priority2 的 tasks
* P4 為 Priority3 的 tasks
* P1~P4 的長度為 5ms
* Time slice 為 2ms -> 每 2ms 就進行 Round-robin

接著運行說明如下: 
1. 因為 Priority1 的 priority 最高, 且只有 P1, 故取出 P1 每次執行 2ms 一直到 P1 結束.
2. 當 Priority1 為空, 接著從 Priority2 依序取出 P2 與 P3 進行 Round-robin , 每次執行 2ms.
3. 因為 P3 後執行, Priority2 最後一個執行的為 P3, 當 P3 執行完畢後 Priority2 為空.
4. 接著從 Priority3 取出 P4 執行, 因為只有一個, 故每次執行 2ms 一直到 P4 結束.

Implementation: 
這邊我的做法是在 ~/code/threads/thread.h 中的 class Thread (即上面的 Task) 新增了下面的屬性與方法: 
- ~/code/threads/thread.h: 
  1. class Thread {  
  2.   private:  
  3.     ...  
  4.     int priority; // New: priority to run. 0 is the highest.  
  5.   public:  
  6.     int RemainingExecutionTicks; // New: remaining execution ticks of the thread  
  7.     ...  
  8.     void MyScheduling(char*ParameterFile); // New: Parse the content of “ParameterFile”and schedule the threads defined in “ParameterFile.”  
  9.   
  10.     void SetPriority(int p); // New: set priority  
  11.     int GetPriority(); // New: get priority  
  12.     void SetRemainingExecutionTicks(int t); // New: Set remaining execution ticks  
  13.     int GetRemainingExecutionTicks(); // New: Get the remaining execution ticks of the thread  
  14.     ...  
  15.     bool forceYield=false// New: Force to yield no matter the priority  
  16.     int ext_time; // New: Execution time  
  17.     ...  
  18. };  
上面的屬性 priority 是用來記錄某個 task 的 priority; 而 ext_time 則是記錄它目前共執行了多少時間; RemainingExecutionTicks 則是記錄該 task 需要執行多少時間. 除此之外需要作如下設定: 
* 設定 SystemTick 與 TimerTick 為 1, 設定可以在 ~/code/machine/stats.h 找到:
  1. const int UserTick =       1;   // advance for each user-level instruction  
  2. const int SystemTick =     1;   // advance each time interrupts are enabled  
  3. const int RotationTime = 500;   // time disk takes to rotate one sector  
  4. const int SeekTime =     500;   // time disk takes to seek past one track  
  5. const int ConsoleTime =  100;   // time to read or write one character  
  6. const int NetworkTime =  100;   // time to send or receive one packet  
  7. const int TimerTicks =     1;   // (average) time between timer interrupts  
* Don’t advance system tick after re-enable Interrupt: 註解 OneTick() in ~/code/machine/interrupt.cc, on Interrupt::SetLevel().
  1. IntStatus  
  2. Interrupt::SetLevel(IntStatus now)  
  3. {  
  4.     ...  
  5.     ChangeLevel(old, now);          // change to new state  
  6.     if ((now == IntOn) && (old == IntOff)) {  
  7.             //OneTick();                // advance simulated time <-- here="" mark="" span="">  
  8.     }  
  9.     return old;  
  10. }  

接著我們來看在 class Thread 新增的方法的實作, 首先直覺的 SetPriority, GetPriority, SetRemainingExecutionTicks 與 GetRemainingExecutionTicks 只是對屬性讀寫操作: 
  1. //----------------------------------------------------------------------  
  2. // Thread::SetPriority  
  3. //     Set priority of thread.  
  4. //----------------------------------------------------------------------  
  5. void  
  6. Thread::SetPriority(int p)  
  7. {  
  8.         priority = p;  
  9. }  
  10.   
  11.   
  12. //----------------------------------------------------------------------  
  13. // Thread::GetPriority  
  14. //     Get priority of thread.  
  15. //----------------------------------------------------------------------  
  16. int  
  17. Thread::GetPriority()  
  18. {  
  19.         return priority;  
  20. }  
  21. // Thread::SetRemainingExecutionTicks(int t)  
  22. //     Set remaining execution ticks  
  23. //----------------------------------------------------------------------  
  24. void  
  25. Thread::SetRemainingExecutionTicks(int t)  
  26. {  
  27.         RemainingExecutionTicks = t;  
  28. }  
  29.   
  30. //----------------------------------------------------------------------  
  31. // int Thread::GetRemainingExecutionTicks()  
  32. //     Get remaining execution ticks  
  33. //----------------------------------------------------------------------  
  34. int  
  35. Thread::GetRemainingExecutionTicks()  
  36. {  
  37.         return RemainingExecutionTicks;  
  38. }  
比較需要注意的是方法 MyScheduling(char*ParameterFile), 他會從命令列讀入一個檔案的路徑, 而該檔案說明我們測試的輸入. 格式如下: 
 
第一行說明 Round-Robin 的 timeslice; 第二行說明有多少個 Task 會被輸入; 接著就是那些 Task 的描述包含 名稱, priority 與 執行時間. 

所以也就是說在方法 MyScheduling 需要解析檔案並生成對應的 Thread 物件後開始執行這些 Tasks. 在 Thread 物件中我們透過該物件的方法 Fork 開始工作, 事實上就是把工作放到 ready queue 裡面然後讓 Schedule 物件處理後續的工作. 而原先的機制是 FCFS, 也就是先來的就先做並做到完. 而整個的工作流程如下: 
 

而在 Fork 方法中我們需要傳入一個方法指標, 該方法指標也就是我們的 Task. 而在這個 Project 要求我們在這個方法需要做如下的動作: 
  1. static void MyScheduleFun(int value) {  
  2.     while(kernel->currentThread->GetRemainingExecutionTicks()>0) {  
  3.         <1. Output current thread name and it’s remaining execution ticks  
  4.             e.g. Name  RemainingExecutionTicks  
  5.         <2. Decrease the remaining execution ticks of the calling thread by one  
  6.             e.g. currentThread->RemainingExecutionTicks -- ;  
  7.         <3. Invoke kernel->interrupt->OneTick()   
  8.     }  
  9. }  
完整實作如下: 
  1. //----------------------------------------------------------------------  
  2. // MyScheduleFun  
  3. //   For testing of Thread::MyScheduling  
  4. //----------------------------------------------------------------------  
  5. static void  
  6. MyScheduleFun(char *which)  
  7. {  
  8.         // Testing here  
  9.         while(kernel->currentThread->GetRemainingExecutionTicks()>0) {  
  10.                 cout << which << " " << kernel->currentThread->GetRemainingExecutionTicks() <<"\n";  
  11.                 kernel->currentThread->RemainingExecutionTicks--;  
  12.                 kernel->interrupt->OneTick();  
  13.                 //kernel->currentThread->Yield();  
  14.         }  
  15. }  
在每次工作執行後執行 kernel->currentThread->RemainingExecutionTicks--; 會讓目前工作需要的時間減少; 而 kernel->interrupt->OneTick(); 則會讓系統時間往前一個 TimeTick 來模擬時間往前的行為, 而同時在 OneTick() 執行時也會呼叫系統目前的工作 Thread 上的方法 Yield(). 因為我們希望是 Priority 越高的 (priority 越小) 越先取出來, 而且要等相同 Priority queue 的 task 執行完才會輪到下一個較低的 Priority queue 的 task. 因此我這邊改寫了 class Scheduler 的 ready queue 從 class List 物件改為 class SortedList
- ~/code/threads/scheduler.h 
  1. class Scheduler {  
  2.   public:  
  3.     ...  
  4.     Thread* TouchNextToRun();   // New: Return first thread of the ready list, if any. But not remove it from the ready list.  
  5.     ...  
  6.   private:  
  7.     //List *readyList; // Mark to be replaced   
  8.     SortedList *readyList;  // Update: queue of threads that are ready to run, but not running  
  9.     ...  
  10. };  
除了改變 ready list 的類別外, 我也新增一個方法 TouchNextToRun 來得到下一個要執行的 Thread 但不把它從 ready list 移除. 接著下面是對應需要改動的實作部分: 
- ~/code/threads/scheduler.cc 
  1. ...  
  2. //----------------------------------------------------------------------  
  3. // ThreadCompare  
  4. //  Compare to pickup higher priority thread.  
  5. //----------------------------------------------------------------------  
  6.   
  7. static int  
  8. ThreadCompare (Thread *x, Thread *y)  
  9. {  
  10.         if (x->GetPriority() < y->GetPriority()) { return -1; }  
  11.         else if (x->GetPriority() > y->GetPriority()) { return 1; }  
  12.         else { return 0; }  
  13. }  
  14.   
  15. //----------------------------------------------------------------------  
  16. // Scheduler::Scheduler  
  17. //  Initialize the list of ready but not running threads.  
  18. //  Initially, no ready threads.  
  19. //----------------------------------------------------------------------  
  20.   
  21. Scheduler::Scheduler()  
  22. {  
  23.         readyList = new SortedList(ThreadCompare);  // ThreadCompare 讓我們每次從 ready queue 取出來都是 priority 最高的!  
  24.         //readyList = new List();  
  25.         toBeDestroyed = NULL;  
  26. }  
  27. ...  
  28. //----------------------------------------------------------------------  
  29. // Scheduler::ReadyToRun  
  30. //  Mark a thread as ready, but not running.  
  31. //  Put it on the ready list, for later scheduling onto the CPU.  
  32. //  
  33. //  "thread" is the thread to be put on the ready list.  
  34. //----------------------------------------------------------------------  
  35.   
  36. void  
  37. Scheduler::ReadyToRun (Thread *thread)  
  38. {  
  39.     ASSERT(kernel->interrupt->getLevel() == IntOff);  
  40.     DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName());  
  41.   
  42.     thread->setStatus(READY);  
  43.     readyList->Insert(thread);  // SortedList 改使用 Insert 取代 Append!  
  44.     //readyList->Append(thread);  
  45. }  
  46. ...  
到目前為止我們已經能: 
* 從 ready list 中取出 priority 較高的 task
* 執行 task 會將剩下時間減一
* 執行 task 後會輸出正確格式.
* 解析測試輸入檔案?
* Round-Robin 的 switch among each priority queue each time slice?

上面紅色部分是我們還沒做的, 其中 Round-Robin 要求我們必須在指定 Time slice 一到就切換同 priority queue 中的 task. 切換的動作在剛剛我們改變 Scheduler 的 ready list 便可達成, 但是如何在 "指定 Time slice" 切換? 因此我們需要知道某個 task 總共執行多少時間, 這邊我們用 Thread 上面屬性 ext_time 來記錄, 但怎麼 update 這個屬性呢? 於是我寫了一個 Timer 在每一個 TimeTick 就去更新目前正在執行 Thread 的執行時間, 我在 alarm.h 新增該 SchedulerRoundRobin 類別: 
- ~/code/threads/alarm.h 
  1. ...  
  2. class SchedulerRoundRobin: public CallBackObj{  
  3. public:  
  4.         SchedulerRoundRobin(int ts);  
  5.         ~SchedulerRoundRobin(){delete timer;};  
  6.         Thread *monitorThd = NULL;  
  7.         int timeSlice = 1;  
  8. private:  
  9.         Timer *timer; // the hardware timer device  
  10.         void CallBack();  // called when the hardware timer generates an interrupt  
  11. };  
接著是實作部分: 
- ~/code/threads/alarm.cc 
  1. ...  
  2. SchedulerRoundRobin::SchedulerRoundRobin(int ts)  
  3. {  
  4.         timer = new Timer(falsethis, ts);  
  5.         timeSlice = ts;  
  6. }  
  7.   
  8.   
  9. void  
  10. SchedulerRoundRobin::CallBack()  
  11. {  
  12.         Thread *curThd = kernel->currentThread;  
  13.         curThd->ext_time++;  
  14.         DEBUG(dbJohn, "\t[Test] SchedulerRR CallBack: Current Thread=" << curThd->name << " (" << curThd->ext_time << ")...\n");  
  15.         if(monitorThd==NULL || monitorThd!=curThd)  
  16.         {  
  17.                 monitorThd = curThd;  
  18.                 monitorThd->forceYield = true;  
  19.         }  
  20.         else if(monitorThd == curThd)  
  21.         {  
  22.                 monitorThd->forceYield = true;  
  23.                 //monitorThd->Yield();  
  24.         }  
  25. }  
如此你能知道每個 task 執行多久, 因此接下來便是修改 Thread 的 Yield 方法讓你在下面兩個情況發生時再進行工作的切換: 
1. ready list 有 priority 更高的 task
2. 目前執行的 task 的執行時間已經超過 time slice 且 ready list 有相同 priority 的 task.

就上面需求改寫如下: 
- ~/code/threads/thread.cc 
  1. void  
  2. Thread::Yield ()  
  3. {  
  4.     Thread *nextThread;  
  5.     IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);  
  6.   
  7.     ASSERT(this == kernel->currentThread);  
  8.   
  9.     DEBUG(dbgThread, "Yielding thread: " << name);  
  10.     nextThread = kernel->scheduler->TouchNextToRun();  
  11.     if (nextThread != NULL) {  
  12.             if(nextThread->GetPriority()<this->GetPriority() ||  
  13.                (this->ext_time >= this->TIME_SLICE && nextThread->GetPriority()==this->GetPriority()))  
  14.             {  
  15.                     this->ext_time = 0;  
  16.                     kernel->scheduler->FindNextToRun();  
  17.                     DEBUG(dbJohn, "\t[Test] Yielding thread=" << name << "(" << this->GetRemainingExecutionTicks() << "/"  
  18.                           << this->GetPriority() <<"); Switch to thread=" << nextThread->name<< "(" << nextThread->GetRemainingExecutionTicks()  
  19.                           <<"/" << nextThread->GetPriority()<<")...");  
  20.                     kernel->scheduler->ReadyToRun(this);  
  21.                     kernel->scheduler->Run(nextThread, FALSE);  
  22.             }  
  23.     }  
  24.     else  
  25.     {  
  26.             DEBUG(dbJohn, "\t[Test] Yielding thread=" << name <<"(" <<this->GetRemainingExecutionTicks()  << "/"  
  27.                   << this->GetPriority() <<")...");  
  28.     }  
  29.     (void) kernel->interrupt->SetLevel(oldLevel);  
  30. }  
目前萬事俱備只差 方法 MyScheduling! 完整代碼如下: 
- ~/code/threads/thread.cc 
  1. ...  
  2. void  
  3. Thread::MyScheduling(char*ParameterFile)  
  4. {  
  5.         DEBUG(dbJohn, "\t[Info] Entering Thread::MyScheduling");  
  6.         DEBUG(dbJohn, "\t[Info] Input test file=" << ParameterFile << "...");  
  7.         FILE *pFile;  
  8.         int timeSlice=1;  
  9.         int thdNum=0;  
  10.         pFile = fopen(ParameterFile, "r");  
  11.         if(pFile != NULL)  
  12.         {  
  13.                 /*1) Parsing intput file*/  
  14.                 fscanf(pFile, "%d", &timeSlice);  
  15.                 fscanf(pFile, "%d", &thdNum);  
  16.                 DEBUG(dbJohn, "\t[Info] Time slice=" << timeSlice << "...");  
  17.                 DEBUG(dbJohn, "\t[Info] Thread number=" << thdNum << "...");  
  18.                 Thread::TIME_SLICE = timeSlice;  
  19.                 char ThreadName[thdNum][10];  
  20.                 int ThreadPriority[thdNum];  
  21.                 int ThreadRemainingExecutionTicks[thdNum];  
  22.                 int i=0;  
  23.                 for(i; i
  24.                 {  
  25.                         fscanf(pFile, "%s %d %d", &ThreadName[i], &ThreadPriority[i], &ThreadRemainingExecutionTicks[i]);  
  26.                 }  
  27.   
  28.                 /*2) Initialize Threads to run tasks.*/  
  29.                 DEBUG(dbJohn, "\t[Info] Start testing...");  
  30.                 Thread *t;  
  31.                 for(i=0;i
  32.                         t = new Thread(ThreadName[i]);  
  33.                         t->SetPriority(ThreadPriority[i]);  
  34.                         t->SetRemainingExecutionTicks(ThreadRemainingExecutionTicks[i]);  
  35.                         t->Fork((VoidFunctionPtr)MyScheduleFun, (char *)ThreadName[i]);  
  36.                 }  
  37.                 SchedulerRoundRobin *srr = new SchedulerRoundRobin(1);  
  38.                 kernel->currentThread->Yield(); //* Give up CPU  
  39.                 fclose(pFile);  
  40.         }  
  41.         else  
  42.         {  
  43.                 DEBUG(dbJohn, "\t[Error] Fail to open file=" << ParameterFile << "!");  
  44.         }  
  45. }  
最後我們新增一個 -S 參數讓我們可以從命令列餵進測試檔案: 
- ~/code/threads/main.cc 
  1. ...  
  2. int  
  3. main(int argc, char **argv)  
  4. {  
  5.     ...  
  6.     bool mySchedulingFlag = false// New: flag of -S  
  7.     char *ParameterFile = "";  // New: Record test file name  
  8.     ...  
  9.     else if (strcmp(argv[i], "-S") == 0) {  
  10.             ASSERT(i + i < argc);  
  11.             //DEBUG(dbJohn, "\t[Info] RR Scheduling testing!" << "\n");  
  12.             ParameterFile = argv[i + 1];  
  13.             mySchedulingFlag = true;  
  14.             i++;  
  15.     }  
  16.     ...  
  17.     if (mySchedulingFlag) {  
  18.       kernel->currentThread->MyScheduling(ParameterFile);  
  19.     }  
  20.     ...  
  21. }  
Experiment: 
考慮我們有測試輸入檔案內容如下: 
- test.txt 
2
4
D 2 3
A 1 5
B 1 3
C 3 4

接著執行下面命令: 
> nachos -S test.txt
A 5
A 4
B 3
B 2
A 3
A 2
B 1
A 1
D 3
D 2
D 1
C 4
C 3
C 2
C 1
Machine halting!

Supplement: 
NTU Operating Systems (902 36700), 2013 Spring 
Project2 specification

沒有留言:

張貼留言

網誌存檔