CSIE--NachOS-HW2

這次的作業是要求讓 NachOS 能實現 multi-programming，還有完成

  • 先進先出排程 (First-Come-First-Service, FCFS)
  • 最短工作優先排程 (Shortest-Job-First, SJF)
  • 最短剩餘時間排程 (shortest remaining time first ,SRTF)

multi-programming 上次測試 Sleep 時遇到記憶體互相覆蓋的問題以後就已經改好了，所以賺到 XD，這次作業主要就是實現以上的那些排程法。

SelfTest

在作業說明中就有提到很多 class 裡面都有這個東西，可以讓我們不用利用 /test 底下的程式來測我們的成果，而且助教也有在 github 上更新了一部分的 code

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
40
41
42
/code/threads/thread.cc

...

// 印出現在正在跑的 thread 的 [Name: BurstTime]
static void
SimpleThread()
{
    Thread *thread = kernel->currentThread;
    while (thread->getBurstTime() > 0) {
        thread->setBurstTime(thread->getBurstTime() - 1);
        printf("%s: %d\n", kernel->currentThread->getName(), 
                kernel->currentThread->getBurstTime());
        kernel->interrupt->OneTick();
    }
}

// 會初始化 thread 的資訊，然後還會 Call 到 SimpleThread()
void
Thread::SelfTest()
{
    DEBUG(dbgThread, "Entering Thread::SelfTest");

    const int number     = 3;
    char *name[number]   = {"A", "B", "C"};
    int burst[number]    = {3, 10, 4};
    int priority[number] = {4, 5, 3};
    int arrive[number] = {3, 0, 5};

    Thread *t;
    for (int i = 0; i < number; i ++) {
        t = new Thread(name[i]);
        t->setPriority(priority[i]);
        t->setBurstTime(burst[i]);
        t->Fork((VoidFunctionPtr) SimpleThread, (void *)NULL);
        // SRTF 的部分，直接把還沒 arrive 的 thread 丟去 sleep 直到他 arrive 的時間到
        if(kernel->scheduler->getSchedulerType() == SRTF){
            kernel->alarm->sleepList.PutToSleep(t,arrive[i]);
        }
    }
    kernel->currentThread->Yield();
}

在 h 檔裡面也要加上我們用到的那幾個 function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/code/threads/thread.h

void CheckOverflow();   	// Check if thread stack has overflowed
void setStatus(ThreadStatus st) { status = st; }
char* getName() { return (name); }
void Print() { cout << name; }
void SelfTest();		// test whether thread impl is working

// 加上下面四個
void setBurstTime(int t)	{burstTime = t;}
int getBurstTime()		{return burstTime;}
void setPriority(int t)	{priority = t;}
int getPriority()		{return priority;}

...

ThreadStatus status;	// ready, running or blocked
char* name;

// 加上這兩個
int burstTime;
int priority;

void StackAllocate(VoidFunctionPtr func, void *arg);

看網路上也有做法是另外寫一個 function，再到 /code/threads/kernel.cc 裡頭的 SelfTest 裡面加上執行這個 function，不過是一樣的意思。
Morris’ blog就是用這個做法。

完成之後，就能直接在 /code/threads 資料夾裡面下 ./nachos
就會跑 SelfTest 裡面的東西了。

接著還做了這一段好讓我們可以選擇使用的方法

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
40
41
42
43
44
45
46
/code/threads/kernel.cc

ThreadedKernel::ThreadedKernel(int argc, char **argv)
{
    randomSlice = FALSE; 
    // 加這一行
    type = RR;
    
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "-rs") == 0) {
 	    ASSERT(i + 1 < argc);
	    RandomInit(atoi(argv[i + 1]));// initialize pseudo-random
					                  // number generator
	    randomSlice = TRUE;
	    i++;
        } else if (strcmp(argv[i], "-u") == 0) {
            cout << "Partial usage: nachos [-rs randomSeed]\n";
	    }
    ////// 加上這一段，讀參數用的 ////////////
        else if(strcmp(argv[i], "RR") == 0) {
            type = RR;
        } else if (strcmp(argv[i], "FCFS") == 0) {
            type = FIFO;
        } else if (strcmp(argv[i], "PRIORITY") == 0) {
            type = Priority;
        } else if (strcmp(argv[i], "SJF") == 0) {
            type = SJF;
        } else if (strcmp(argv[i], "SRTF") == 0) {
            type = SRTF;
        }
    ////////////////////////////////////////
    }
}

...

void
ThreadedKernel::Initialize()
{
    stats = new Statistics();		// collect statistics
    interrupt = new Interrupt;		// start up interrupt handling

    // 這裡這建構子加上type參數
    scheduler = new Scheduler(type);	// initialize the ready queue
    alarm = new Alarm(randomSlice);	// start up time slicing
    ...

在 .h 檔

1
2
3
4
5
6
/code/threads/kernel.h

private:
    bool randomSlice;		// enable pseudo-random time slicing
    // 加上
    SchedulerType type;

這樣就可以利用多一個參數來決定要用的 schedule 方法

1
2
3
4
5
$ ./nachos RR
$ ./nachos FCFS
$ ./nachos PRIORITY
$ ./nachos SJF
$ ./nachos SRTF

接著就可以來實際做我們要實作的那幾個東東了~

Scheduler

先修改該修的 .h

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
/code/threads/scheduler.h

enum SchedulerType {
    RR,     // Round Robin
    SJF,
    Priority,
    FIFO,
    SRTF
};

class Scheduler {
  public:
	Scheduler();		        // Initialize list of ready threads 
	Scheduler(SchedulerType type); // 這個要改，加上參數
	~Scheduler();				// De-allocate ready list

	void ReadyToRun(Thread* thread);	
				                // Thread can be dispatched.
	Thread* FindNextToRun();	// Dequeue first thread on the ready 
					            // list, if any, and return thread.
	void Run(Thread* nextThread, bool finishing);
	    				        // Cause nextThread to start running
	void CheckToBeDestroyed();	// Check if thread that had been
    					        // running needs to be deleted
	void Print();			    // Print contents of ready list

    // 加上
    void setSchedulerType(SchedulerType t) {schedulerType = t;}
	SchedulerType getSchedulerType() {return schedulerType;}

最主要要動手腳的地方就在這裡 ! 根據不同的排程方法，造出不同的 ReadyList。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/code/threads/scheduler.cc

// 加上 compare function (做 sortlist 的時候要用的)
//----------------------------------------------------------------------
// Compare function
//----------------------------------------------------------------------
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;
}

int SJFCompare(Thread *a, Thread *b) {
    if(a->getBurstTime() == b->getBurstTime())
        return 0;
    return a->getBurstTime() > b->getBurstTime() ? 1 : -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);
            break;
        case SRTF:
            // 和SJF其實一樣，這兩個的差別本來就只有是不是preemptive而已
            readyList = new SortedList<Thread *>(SJFCompare);
            break;
   	}
	toBeDestroyed = NULL;
}

SRTF 有 preemptive，所以比較麻煩需要對原本已經完成的 Sleep 部分多做調整，讓他可以直接被我們的排程使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/code/threads/alarm.cc

// 對原本的PutToSleep多做調整
void SleepList::PutToSleep(Thread*t, int x)
{
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff); // 不讓其他 thread 可以中斷
    ASSERT(kernel->interrupt->getLevel() == IntOff);		  // check if it cannot be interrupt.
    threadlist.push_back(SleepThread(t, counter + x));        // put into the list
    if(kernel->scheduler->getSchedulerType() != SRTF){
    	t->Sleep(false);
    }
    kernel->interrupt->SetLevel(oldLevel);
}

// PutToReady 的最前和最後也做了關掉中斷的動作
bool SleepList::PutToReady()
{
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    ...
    ...
    kernel->interrupt->SetLevel(oldLevel);
    return woken;
}

Fork 裡面把 SRTF 的 ReadyToRun 關掉
Yield 裡面也要加上判斷下一個 thread 是誰、會不會被中斷換掉

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/code/threads/thread.cc

void 
Thread::Fork(VoidFunctionPtr func, void *arg)
{
    Interrupt *interrupt = kernel->interrupt;
    Scheduler *scheduler = kernel->scheduler;
    IntStatus oldLevel;
    
    DEBUG(dbgThread, "Forking thread: " << name << " f(a): " << (int) func << " " << arg);
    
    StackAllocate(func, arg);

    oldLevel = interrupt->SetLevel(IntOff);

    if(scheduler->getSchedulerType() != SRTF){ //因為他不一定一 fork 就可以 run
        scheduler->ReadyToRun(this);	// ReadyToRun assumes that interrupts are disabled!
    }
    (void) interrupt->SetLevel(oldLevel);
} 


void
Thread::Yield ()
{
    Thread *nextThread;
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    
    ASSERT(this == kernel->currentThread);
    
    DEBUG(dbgThread, "Yielding thread: " << name);

    nextThread = kernel->scheduler->FindNextToRun();
    // 更改這一段//////////////////////////////////////////////////
    if (nextThread != NULL) {
        // 因為是 preemtive 所以每次的 yield 都要判斷會不會被中斷
        // 有可能不會被中斷，所以不能像其他排程法一樣直接把 nextThread 丟到 ReadyToRun
        if(kernel->scheduler->getSchedulerType() == SRTF){	
            if(nextThread->getBurstTime() < this->getBurstTime()){
                kernel->scheduler->ReadyToRun(this);
                kernel->scheduler->Run(nextThread, FALSE);
            }
            else{
                kernel->scheduler->ReadyToRun(nextThread);
            }
	    }
	    else{
            kernel->scheduler->ReadyToRun(this);
            kernel->scheduler->Run(nextThread, FALSE);
	    }
    }
    ////////////////////////////////////////////////////////////////
    (void) kernel->interrupt->SetLevel(oldLevel);
}

完成 !

結果

用 SelfTest

  • SJF
  • SRTF

用 userprog

  • FCFS

homework
#OS
CSIE--NachOS-HW2
https://wiiwu959.github.io/2019/10/29/2019-10-29-OS_HW2-2019/
Author
Wii Wu
Posted on
October 29, 2019
Licensed under