學校課程/作業系統

向 NachOS 4.0 作業進發 (2)

contents

  1. 1. 接續
  2. 2. 目標 Scheduler
  3. 3. 開始
    1. 3.1. 第一步 - 測試
    2. 3.2. 第二步 - 撰寫
  4. 4. 最後
  5. 5. 致網路資源

接續

接續上一篇的 向 NachOS 4.0 作業進發 (1)，我們繼續完成排程處理，在原始的 NachOS 4.0 中，基礎排程是 Round-robin，它的運作方式藉由定時呼叫 threads/alarm.h 中的 Alarm::CallBack()，而呼叫的時脈來源設定為 machine/stats.h 中的 const int TimerTicks = 100; 決定，數值越小表示呼叫頻率越高，置換的次數就會上升。

目標 Scheduler

  • FIFO (FCFS) 先來先服務
  • SJF 最短工作優先
  • Priority 最小優先權優先
  • RR (Round-robin)
  • multi-level queue 最後的大魔王

開始

第一步 - 測試

先來說說怎麼測試自己的寫的代碼正確性，不然怎麼寫都只是理論腦補，雖然會動，但是不知道是否寫對。

  • 第一種方式為下達 

    $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個

    這樣必須自己設置優先權、Burst Time，這方面撰寫方式有兩種，其一是來亂，其二是較為正式，而在 Burst Time 的計算又分成兩種，一是執行前已知、二是執行時猜測。

    • 其一來亂寫法，

      $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個

      不改變原本的的執行方式，直接在代碼中決策 thread fork 出來時所擁有的優先權和 Burst Time。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      static int testPriority = 0;
      void 
      Thread::Fork(VoidFunctionPtr func, void *arg)
      {
      // morris add
          testPriority++;
          if(testPriority == 1)
              setPriority(64);
          else if(testPriority == 2)
              setPriority(128);
          else
              setPriority(64);
      // end morris add

      因此，您可能會寫出以上的代碼，當然我不建議這麼寫，雖然是一種測試方式，但這並不好，一開始就這麼錯得相當離譜。

    • 其二寫法，增加下達參數，不過這些參數格式要去查閱一下他們的參數傳遞建造，我想會寫成大概的樣子為

      $ ./nachos -e ../test/test1 -pw 64 -e ../test/test2  -pw 128 ...

      多個為了不增加工作量，這裡就沒有親自去實作。某方面來說，可能要寫很多 small program 進行測試，並且撰寫時還要預測會跑多久，這難度會稍微提高。

  • 第二種方式按照軟工的寫法
    來寫 test code 吧！如果細心一點，就會看到相關的 Class::SelfTest() 在很多 class 都有的，因此我們需要把 test code 寫到 SelfTest 中被呼叫。因此，不需要有實體的 process 運行，只是單純地測試我們寫的 scheduler 的排程順序是否正確。

    threads/thread.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void
    threadBody() {
        Thread *thread = kernel->currentThread;
        while (thread->getBurstTime() > 0) {
            thread->setBurstTime(thread->getBurstTime() - 1);
            kernel->interrupt->OneTick();
            printf("%s: remaining %d\n", kernel->currentThread->getName(), kernel->currentThread->getBurstTime());
        }
    }
    void
    Thread::SchedulingTest()
    {
        const int thread_num = 4;
        char *name[thread_num] = {"A", "B", "C", "D"};
        int thread_priority[thread_num] = {5, 1, 3, 2};
        int thread_burst[thread_num] = {3, 9, 7, 3};
        
        Thread *t;
        for (int i = 0; i < thread_num; i ++) {
            t = new Thread(name[i]);
            t->setPriority(thread_priority[i]);
            t->setBurstTime(thread_burst[i]);
            t->Fork((VoidFunctionPtr) threadBody, (void *)NULL);
        }
        kernel->currentThread->Yield();
    }

    請自行在 class Thread 增加 setPriority(), setBurstTime(), SchedulingTest() … 等 method header and body。
    threads/thread.h
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Thread {
      private:
       ...
      public:
       ...
        // morris add
        void setBurstTime(int t)	{burstTime = t;}
        int getBurstTime()		{return burstTime;}
        void setStartTime(int t)	{startTime = t;}
        int getStartTime()		{return startTime;}
        void setPriority(int t)	{execPriority = t;}
        int getPriority()		{return execPriority;}
        static void SchedulingTest();
      private:
        // some of the private data for this class is listed above
        // morris add
        int burstTime;	// predicted burst time
        int startTime;	// the start time of the thread
        int execPriority;	// the execute priority of the thread
        ...
    };

    接著是需要 call testcode 加入到 ThreadedKernel 中。
    threads/kernel.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void
    ThreadedKernel::SelfTest() {
       Semaphore *semaphore;
       SynchList<int> *synchList;
       
       LibSelfTest();		// test library routines
       
       currentThread->SelfTest();	// test thread switching
       Thread::SchedulingTest();   
       				// test semaphore operation
       semaphore = new Semaphore("test", 0);
        ...
    }

    因此我們可以利用單一 module 就能進行檢查。

    $ cd code/threads
$ ./nachos

    但是這種方式，並沒有決定我們要測試哪一種類型的 scheduler，額外需要設定參數，讓其選擇建造哪一種的 readyList(Thread*)

    $ cd code/threads
$ ./nachos FCFS
$ ./nachos SJF
$ ./nachos Priority
$ ./nachos RR

    預計要修成如上述的測試方式。

    threads/main.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int
    main(int argc, char **argv)
    {
        ...
        debug = new Debug(debugArg);
        
        DEBUG(dbgThread, "Entering main");
    //
        SchedulerType type = RR;
        if(strcmp(argv[1], "FCFS") == 0) {
        type = FIFO;
        } else if (strcmp(argv[1], "SJF") == 0) {
        type = SJF;
        } else if (strcmp(argv[1], "PRIORITY") == 0) {
        type = Priority;
        } else if (strcmp(argv[1], "RR") == 0) {
        type = RR;
        }
    //
        kernel = new KernelType(argc, argv);
        kernel->Initialize(type);
        
        CallOnUserAbort(Cleanup);		// if user hits ctl-C
        kernel->SelfTest();
        kernel->Run();
        
        return 0;
    }

第一步測試撰寫就這麼結束，比起撰寫新的 code，不會進行測試也是徒勞。

雖然這麼說，實際運作也是先寫 code 再寫 test code，因為當時還不太懂這些，所以如果已經先寫了一些也不用難過，大家都是這麼走過來的。

如果不知道怎麼執行，哪還有什麼撰寫的欲望，如果不知道怎麼測試，那就是在黑暗中漫步。

第二步 - 撰寫

在撰寫開始前，如果使用走第一種測試方式的人，需要將實體記憶體用大一點，否則需要實作虛擬記憶體的 context-swith。

machine/machine.h
1
2
3
const unsigned int NumPhysPages = 64;  // morris modify, old value=32
const int MemorySize = (NumPhysPages * PageSize);
const int TLBSize = 4;			// if there is a TLB, make it small

若完成以上的修改，在 /userprog 下，執行

1
$ ./nachos -e ../test/test1 -e ../test/test2 -e ../test/test1

就不會跑出 segment fault 。

threads/scheduler.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
enum SchedulerType {
        RR,     // Round Robin
        SJF,
        Priority,
        FIFO
};
...
class Scheduler {
  public:
    Scheduler();
    Scheduler(SchedulerType type);		// Initialize list of ready threads 
    ...
    	// morris add
    SchedulerType getSchedulerType() {return schedulerType;}
    void setSchedulerType(SchedulerType t) {schedulerType = t;}
  private:
    ...
};

如果有機會查閱其他代碼，很常見會把 List<Thread *> *readyList; 改成 SortedList<Thread *> *readyList; 但是其實不用的，可以利用多形來完成，畢竟 SortedList 繼承 List。因此是不需要更動的。

接著，我們使用多形，在建構子中決定要用哪一種類型的排程，並且宣告相對應的 compare function，參照如下。

threads/scheduler.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int SJFCompare(Thread *a, Thread *b) {
    if(a->getBurstTime() == b->getBurstTime())
        return 0;
    return a->getBurstTime() > b->getBurstTime() ? 1 : -1;
}
int PriorityCompare(Thread *a, Thread *b) {
    if(a->getPriority() == b->getPriority())
        return 0;
    return a->getPriority() > b->getPriority() ? 1 : -1;
}
int FIFOCompare(Thread *a, Thread *b) {
    return 1;
}
//----------------------------------------------------------------------
// Scheduler::Scheduler
// 	Initialize the list of ready but not running threads.
//	Initially, no ready threads.
//----------------------------------------------------------------------
Scheduler::Scheduler() {
    Scheduler(RR);
}
Scheduler::Scheduler(SchedulerType type)
{
    schedulerType = type;
    switch(schedulerType) {
    case RR:
        readyList = new List<Thread *>;
        break;
    case SJF:
        readyList = new SortedList<Thread *>(SJFCompare);
        break;
    case Priority:
        readyList = new SortedList<Thread *>(PriorityCompare);
        break;
    case FIFO:
        readyList = new SortedList<Thread *>(FIFOCompare);
    }
    toBeDestroyed = NULL;
}

上述的寫法是因為沒有辦法宣告 default argument value for class。

如果需要搶先 (Preemptive) 設計，則在 Alarm::CallBack() 決定是否要呼叫 interrupt->YieldOnReturn() 查看是否有更需要優先的 process 要執行。

threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void 
Alarm::CallBack() 
{
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = _bedroom.MorningCall();
    kernel->currentThread->setPriority(kernel->currentThread->getPriority() - 1);
    if (status == IdleMode && !woken && _bedroom.IsEmpty()) {// is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
        timer->Disable();	// turn off the timer
    }
    } else {			// there's someone to preempt
    if(kernel->scheduler->getSchedulerType() == RR ||
        kernel->scheduler->getSchedulerType() == Priority ) {
//		interrupt->YieldOnReturn();
        cout << "=== interrupt->YieldOnReturn ===" << endl;
        interrupt->YieldOnReturn();
        }
    }
}

在 Burst Time 計算上，如果採用運行時估計，可以在以下代碼中進行計算。kernel->stats->userTicks 是執行 user program 的時間累加器 (也存有一個 system program 的時間累加器，運行 thread context-free, thread scheduling … 等時間用途。)

threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
void 
Alarm::WaitUntil(int x) {
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    // burst time
    int worktime = kernel->stats->userTicks - t->getStartTime();
    t->setBurstTime(t->getBurstTime() + worktime);
    t->setStartTime(kernel->stats->userTicks);
    cout << "Alarm::WaitUntil go sleep" << endl;
    _bedroom.PutToBed(t, x);
    kernel->interrupt->SetLevel(oldLevel);
}

其實到這裡已經完成，接下來就放幾張測試結果。

multi-programming

FCFS(1)
FCFS(2)

RR(1)
RR(2)

SJF(1)
SJF(2)

Priority(1)
Priority(1)

最後

如果在

1
2
$ cd code
$ make

編譯時發生錯誤，想必是兩個地方的 Initialize() 發生錯誤，所以請參照以下代碼進行修改。這問題是發生於我們在 /threads 下修改 main.cc 的關係，所以必須在每一個 kernel 宣告地方都給一個決定 scheduler 類型的參數。

其一,

userprog/userkernel.h
1
2
3
4
5
6
7
8
9
#include "../threads/scheduler.h"
class SynchDisk;
class UserProgKernel : public ThreadedKernel {
  public:
  	...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType type);
    ...

其二,
userprog/userkernel.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
UserProgKernel::Initialize()
{
    Initialize(RR);
}
void
UserProgKernel::Initialize(SchedulerType type)
{
    ThreadedKernel::Initialize(type);	// init multithreading
    machine = new Machine(debugUserProg);
    fileSystem = new FileSystem();
#ifdef FILESYS
    synchDisk = new SynchDisk("New SynchDisk");
#endif // FILESYS
}

其三,
network/netkernel.h
1
2
3
4
5
6
7
8
9
10
11
#include "../threads/scheduler.h"
class PostOfficeInput;
class PostOfficeOutput;
class NetKernel : public UserProgKernel {
  public:
    ...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType);
    ...

其四,
network/netkernel.cc
1
2
3
4
5
6
7
8
9
10
11
12
void 
NetKernel::Initialize() {
    Initialize(RR);
}
void
NetKernel::Initialize(SchedulerType type)
{
    UserProgKernel::Initialize(type);	// init other kernel data structs
    postOfficeIn = new PostOfficeInput(10);
    postOfficeOut = new PostOfficeOutput(reliability, 10);
}

致網路資源

感謝網路上前人們所遺留的遺產。雖然在看不懂的文字中摸索，但仍抓到了一點線索。

我一無所有，直到見到了你們。