程式扎記: [ 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:

view plaincopy to clipboardprint?
class Thread {  
  private:  
    ...  
    int priority; // New: priority to run. 0 is the highest.  
  public:  
    int RemainingExecutionTicks; // New: remaining execution ticks of the thread  
    ...  
    void MyScheduling(char*ParameterFile); // New: Parse the content of “ParameterFile”and schedule the threads defined in “ParameterFile.”  
  
    void SetPriority(int p); // New: set priority  
    int GetPriority(); // New: get priority  
    void SetRemainingExecutionTicks(int t); // New: Set remaining execution ticks  
    int GetRemainingExecutionTicks(); // New: Get the remaining execution ticks of the thread  
    ...  
    bool forceYield=false; // New: Force to yield no matter the priority  
    int ext_time; // New: Execution time  
    ...  
};  

上面的屬性 priority 是用來記錄某個 task 的 priority; 而 ext_time 則是記錄它目前共執行了多少時間; RemainingExecutionTicks 則是記錄該 task 需要執行多少時間. 除此之外需要作如下設定:

* 設定 SystemTick 與 TimerTick 為 1, 設定可以在 ~/code/machine/stats.h 找到:

view plain copy to clipboard print ?

const int UserTick =       1;   // advance for each user-level instruction

const int SystemTick =     1;   // advance each time interrupts are enabled

const int RotationTime = 500;   // time disk takes to rotate one sector

const int SeekTime =     500;   // time disk takes to seek past one track

const int ConsoleTime =  100;   // time to read or write one character

const int NetworkTime =  100;   // time to send or receive one packet

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().

view plain copy to clipboard print ?

IntStatus

Interrupt::SetLevel(IntStatus now)

{

    ...

    ChangeLevel(old, now);          // change to new state

    if ((now == IntOn) && (old == IntOff)) {

            //OneTick();                // advance simulated time <-- here="" mark="" span="">

    }

    return old;

}

接著我們來看在 class Thread 新增的方法的實作, 首先直覺的 SetPriority, GetPriority, SetRemainingExecutionTicks 與 GetRemainingExecutionTicks 只是對屬性讀寫操作:

view plaincopy to clipboardprint?
//----------------------------------------------------------------------  
// Thread::SetPriority  
//     Set priority of thread.  
//----------------------------------------------------------------------  
void  
Thread::SetPriority(int p)  
{  
        priority = p;  
}  
  
  
//----------------------------------------------------------------------  
// Thread::GetPriority  
//     Get priority of thread.  
//----------------------------------------------------------------------  
int  
Thread::GetPriority()  
{  
        return priority;  
}  
// Thread::SetRemainingExecutionTicks(int t)  
//     Set remaining execution ticks  
//----------------------------------------------------------------------  
void  
Thread::SetRemainingExecutionTicks(int t)  
{  
        RemainingExecutionTicks = t;  
}  
  
//----------------------------------------------------------------------  
// int Thread::GetRemainingExecutionTicks()  
//     Get remaining execution ticks  
//----------------------------------------------------------------------  
int  
Thread::GetRemainingExecutionTicks()  
{  
        return RemainingExecutionTicks;  
}  

比較需要注意的是方法 MyScheduling(char*ParameterFile), 他會從命令列讀入一個檔案的路徑, 而該檔案說明我們測試的輸入. 格式如下:

第一行說明 Round-Robin 的 timeslice; 第二行說明有多少個 Task 會被輸入; 接著就是那些 Task 的描述包含名稱, priority 與執行時間.

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

而在 Fork 方法中我們需要傳入一個方法指標, 該方法指標也就是我們的 Task. 而在這個 Project 要求我們在這個方法需要做如下的動作:

view plaincopy to clipboardprint?
static void MyScheduleFun(int value) {  
    while(kernel->currentThread->GetRemainingExecutionTicks()>0) {  
        <1. Output current thread name and it’s remaining execution ticks  
            e.g. Name  RemainingExecutionTicks  
        <2. Decrease the remaining execution ticks of the calling thread by one  
            e.g. currentThread->RemainingExecutionTicks -- ;  
        <3. Invoke kernel->interrupt->OneTick()   
    }  
}  

完整實作如下:

view plaincopy to clipboardprint?
//----------------------------------------------------------------------  
// MyScheduleFun  
//   For testing of Thread::MyScheduling  
//----------------------------------------------------------------------  
static void  
MyScheduleFun(char *which)  
{  
        // Testing here  
        while(kernel->currentThread->GetRemainingExecutionTicks()>0) {  
                cout << which << " " << kernel->currentThread->GetRemainingExecutionTicks() <<"\n";  
                kernel->currentThread->RemainingExecutionTicks--;  
                kernel->interrupt->OneTick();  
                //kernel->currentThread->Yield();  
        }  
}  

在每次工作執行後執行 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

view plaincopy to clipboardprint?
class Scheduler {  
  public:  
    ...  
    Thread* TouchNextToRun();   // New: Return first thread of the ready list, if any. But not remove it from the ready list.  
    ...  
  private:  
    //List *readyList; // Mark to be replaced   
    SortedList *readyList;  // Update: queue of threads that are ready to run, but not running  
    ...  
};  

除了改變 ready list 的類別外, 我也新增一個方法 TouchNextToRun 來得到下一個要執行的 Thread 但不把它從 ready list 移除. 接著下面是對應需要改動的實作部分:
- ~/code/threads/scheduler.cc

view plaincopy to clipboardprint?
...  
//----------------------------------------------------------------------  
// ThreadCompare  
//  Compare to pickup higher priority thread.  
//----------------------------------------------------------------------  
  
static int  
ThreadCompare (Thread *x, Thread *y)  
{  
        if (x->GetPriority() < y->GetPriority()) { return -1; }  
        else if (x->GetPriority() > y->GetPriority()) { return 1; }  
        else { return 0; }  
}  
  
//----------------------------------------------------------------------  
// Scheduler::Scheduler  
//  Initialize the list of ready but not running threads.  
//  Initially, no ready threads.  
//----------------------------------------------------------------------  
  
Scheduler::Scheduler()  
{  
        readyList = new SortedList(ThreadCompare);  // ThreadCompare 讓我們每次從 ready queue 取出來都是 priority 最高的!  
        //readyList = new List();  
        toBeDestroyed = NULL;  
}  
...  
//----------------------------------------------------------------------  
// Scheduler::ReadyToRun  
//  Mark a thread as ready, but not running.  
//  Put it on the ready list, for later scheduling onto the CPU.  
//  
//  "thread" is the thread to be put on the ready list.  
//----------------------------------------------------------------------  
  
void  
Scheduler::ReadyToRun (Thread *thread)  
{  
    ASSERT(kernel->interrupt->getLevel() == IntOff);  
    DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName());  
  
    thread->setStatus(READY);  
    readyList->Insert(thread);  // SortedList 改使用 Insert 取代 Append!  
    //readyList->Append(thread);  
}  
...  

到目前為止我們已經能:

* 從 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

view plaincopy to clipboardprint?
...  
class SchedulerRoundRobin: public CallBackObj{  
public:  
        SchedulerRoundRobin(int ts);  
        ~SchedulerRoundRobin(){delete timer;};  
        Thread *monitorThd = NULL;  
        int timeSlice = 1;  
private:  
        Timer *timer; // the hardware timer device  
        void CallBack();  // called when the hardware timer generates an interrupt  
};  

接著是實作部分:
- ~/code/threads/alarm.cc

view plaincopy to clipboardprint?
...  
SchedulerRoundRobin::SchedulerRoundRobin(int ts)  
{  
        timer = new Timer(false, this, ts);  
        timeSlice = ts;  
}  
  
  
void  
SchedulerRoundRobin::CallBack()  
{  
        Thread *curThd = kernel->currentThread;  
        curThd->ext_time++;  
        DEBUG(dbJohn, "\t[Test] SchedulerRR CallBack: Current Thread=" << curThd->name << " (" << curThd->ext_time << ")...\n");  
        if(monitorThd==NULL || monitorThd!=curThd)  
        {  
                monitorThd = curThd;  
                monitorThd->forceYield = true;  
        }  
        else if(monitorThd == curThd)  
        {  
                monitorThd->forceYield = true;  
                //monitorThd->Yield();  
        }  
}  

如此你能知道每個 task 執行多久, 因此接下來便是修改 Thread 的 Yield 方法讓你在下面兩個情況發生時再進行工作的切換:

1. ready list 有 priority 更高的 task
2. 目前執行的 task 的執行時間已經超過 time slice 且 ready list 有相同 priority 的 task.

就上面需求改寫如下:
- ~/code/threads/thread.cc

view plaincopy to clipboardprint?
void  
Thread::Yield ()  
{  
    Thread *nextThread;  
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);  
  
    ASSERT(this == kernel->currentThread);  
  
    DEBUG(dbgThread, "Yielding thread: " << name);  
    nextThread = kernel->scheduler->TouchNextToRun();  
    if (nextThread != NULL) {  
            if(nextThread->GetPriority()<this->GetPriority() ||  
               (this->ext_time >= this->TIME_SLICE && nextThread->GetPriority()==this->GetPriority()))  
            {  
                    this->ext_time = 0;  
                    kernel->scheduler->FindNextToRun();  
                    DEBUG(dbJohn, "\t[Test] Yielding thread=" << name << "(" << this->GetRemainingExecutionTicks() << "/"  
                          << this->GetPriority() <<"); Switch to thread=" << nextThread->name<< "(" << nextThread->GetRemainingExecutionTicks()  
                          <<"/" << nextThread->GetPriority()<<")...");  
                    kernel->scheduler->ReadyToRun(this);  
                    kernel->scheduler->Run(nextThread, FALSE);  
            }  
    }  
    else  
    {  
            DEBUG(dbJohn, "\t[Test] Yielding thread=" << name <<"(" <<this->GetRemainingExecutionTicks()  << "/"  
                  << this->GetPriority() <<")...");  
    }  
    (void) kernel->interrupt->SetLevel(oldLevel);  
}  

目前萬事俱備只差方法 MyScheduling! 完整代碼如下:
- ~/code/threads/thread.cc

view plaincopy to clipboardprint?
...  
void  
Thread::MyScheduling(char*ParameterFile)  
{  
        DEBUG(dbJohn, "\t[Info] Entering Thread::MyScheduling");  
        DEBUG(dbJohn, "\t[Info] Input test file=" << ParameterFile << "...");  
        FILE *pFile;  
        int timeSlice=1;  
        int thdNum=0;  
        pFile = fopen(ParameterFile, "r");  
        if(pFile != NULL)  
        {  
                /*1) Parsing intput file*/  
                fscanf(pFile, "%d", &timeSlice);  
                fscanf(pFile, "%d", &thdNum);  
                DEBUG(dbJohn, "\t[Info] Time slice=" << timeSlice << "...");  
                DEBUG(dbJohn, "\t[Info] Thread number=" << thdNum << "...");  
                Thread::TIME_SLICE = timeSlice;  
                char ThreadName[thdNum][10];  
                int ThreadPriority[thdNum];  
                int ThreadRemainingExecutionTicks[thdNum];  
                int i=0;  
                for(i; i
                {  
                        fscanf(pFile, "%s %d %d", &ThreadName[i], &ThreadPriority[i], &ThreadRemainingExecutionTicks[i]);  
                }  
  
                /*2) Initialize Threads to run tasks.*/  
                DEBUG(dbJohn, "\t[Info] Start testing...");  
                Thread *t;  
                for(i=0;i
                        t = new Thread(ThreadName[i]);  
                        t->SetPriority(ThreadPriority[i]);  
                        t->SetRemainingExecutionTicks(ThreadRemainingExecutionTicks[i]);  
                        t->Fork((VoidFunctionPtr)MyScheduleFun, (char *)ThreadName[i]);  
                }  
                SchedulerRoundRobin *srr = new SchedulerRoundRobin(1);  
                kernel->currentThread->Yield(); //* Give up CPU  
                fclose(pFile);  
        }  
        else  
        {  
                DEBUG(dbJohn, "\t[Error] Fail to open file=" << ParameterFile << "!");  
        }  
}  

最後我們新增一個 -S 參數讓我們可以從命令列餵進測試檔案:
- ~/code/threads/main.cc

view plaincopy to clipboardprint?
...  
int  
main(int argc, char **argv)  
{  
    ...  
    bool mySchedulingFlag = false; // New: flag of -S  
    char *ParameterFile = "";  // New: Record test file name  
    ...  
    else if (strcmp(argv[i], "-S") == 0) {  
            ASSERT(i + i < argc);  
            //DEBUG(dbJohn, "\t[Info] RR Scheduling testing!" << "\n");  
            ParameterFile = argv[i + 1];  
            mySchedulingFlag = true;  
            i++;  
    }  
    ...  
    if (mySchedulingFlag) {  
      kernel->currentThread->MyScheduling(ParameterFile);  
    }  
    ...  
}  

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

程式扎記

標籤

2013年6月11日星期二

[ Nachos 4.0 ] Nachos System : Round-Robin Scheduling

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2013年6月11日 星期二