CSIE--NachOS-HW1

第一次碰 OS 相關的東西，超級不熟，怕之後會忘記所以紀錄一下
參考了很多學長的 blog 一邊試才寫出來的第一次作業 orz 要再花時間把架構搞清楚一點才行
主要參考這兩個 blog :

Terry Nini OS::NachOS::HW1

Morris Blog 向 NachOS 4.0 作業進發 (1)

初始作業

Install

說是要跑在 ubuntu 14.04 (32 bit) 或更舊的版本才行，不然就要另外去 patch，真的是比 14.04 新一點都會出問題，我一開始載到 14.04.1 就卡關到不行

1
2
3
4
5
6
$ sudo apt install git csh g++
$ git clone https://github.com/connlabtw/NachOS.git
$ cd NachOS
$ sudo cp -r usr /
$ cd code
$ make

Test

然後就能來測試能不能正常運行了
進到 NachOS/code/userprog 裡面

1
$ ./nachos –e ../test/test1

如果正常就應該能看到這樣的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Total threads number is 1
Thread ../test/test1 is executing.
Print integer:9
Print integer:8
Print integer:7
Print integer:6
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!

Ticks: total 200, idle 66, system 40, user 94
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

我照網路上也去試試同時跑兩個 process (要記得先去 Makefile 裡面加上 test2 再 make test2)

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

MultiProgramming

看了很多 blog 都有提到這問題，我一開始卻沒遇到，我才剛慶幸我沒有遇到這問題結果在測試我的 Sleep() 就遇到了，有夠…

反正當我想同時跑兩個不同時間的 Sleep() 並交互使用 PrintInt 時發現這兩個 thread 竟然互相干擾，我只想印十遍的內容竟然重複了近三十遍，每到記數變數 i 快要接近終結的 10 時，都會跳掉，很明顯就是兩個 thread 用到同一塊記憶體了，所以以下就是根據 Morris 的 blog 改的

code/userprog/addrspace.h

1
2
3
4
5
6
7
8
class AddrSpace {
  public:
    ...
    //加上這一行
    static bool usedPhyPage[NumPhysPages];
  private:
    ...
};

code/usrprog/addrspace.cc
加上這一行宣告+初始化

1
bool AddrSpace::usedPhyPage[NumPhysPages] = {0};

釋放資源

1
2
3
4
5
6
AddrSpace::~AddrSpace()
{
    for(int i = 0; i < numPages; i++)
        AddrSpace::usedPhyPage[pageTable[i].physicalPage] = false;
   delete pageTable;
}

也是在 code/userprog/addrspace.cc 改上這一部分
主要就是找到能用的 page、算出進入點。

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
57
58
59
60
61
62
63
64
bool AddrSpace::Load(char *fileName) {
    OpenFile *executable = kernel->fileSystem->Open(fileName);
    NoffHeader noffH;
    unsigned int size;
    if (executable == NULL) {
    cerr << "Unable to open file " << fileName << "\n";
    return FALSE;
    }
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
        (WordToHost(noffH.noffMagic) == NOFFMAGIC))
     SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);
// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
            + UserStackSize; // we need to increase the size
                        // to leave room for the stack
    numPages = divRoundUp(size, PageSize);
// cout << "number of pages of " << fileName<< " is "<< numPages << endl;
/////////////////////////加上這一段////////////////////////////////////////
    pageTable = new TranslationEntry[numPages];
    for(unsigned int i = 0, j = 0; i < numPages; i++) {
        pageTable[i].virtualPage = i;
        
        // 這裡是指一直往下找到沒有被用過的page為止
        while(j < NumPhysPages && AddrSpace::usedPhyPage[j] == true)
            j++;
        // 找到以後就用這個沒被用過的page了
        AddrSpace::usedPhyPage[j] = true;
        pageTable[i].physicalPage = j;
        pageTable[i].valid = true;
        pageTable[i].use = false;
        pageTable[i].dirty = false;
        pageTable[i].readOnly = false;
    }
////////////////////////////////////////////////////////////////////////
    size = numPages * PageSize;
    ASSERT(numPages <= NumPhysPages);  // check we're not trying
                        // to run anything too big --
                        // at least until we have
                        // virtual memory
    DEBUG(dbgAddr, "Initializing address space: " << numPages << ", " << size);
// then, copy in the code and data segments into memory
    if (noffH.code.size > 0) {
        DEBUG(dbgAddr, "Initializing code segment.");
    DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);
// 這裡更改mainmemory中的項次
// 主要做的就是先算出第幾頁，然後乘上 PageSize 就是 page base，而 page offset 則是 code.address % PageSize
// offset + base 就是進入點了
         executable->ReadAt(
        &(kernel->machine->mainMemory[pageTable[noffH.code.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]), 
            noffH.code.size, noffH.code.inFileAddr);
    }
    if (noffH.initData.size > 0) {
        DEBUG(dbgAddr, "Initializing data segment.");
    DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);
// 這裡更改mainmemory中的項次
        executable->ReadAt(
        &(kernel->machine->mainMemory[pageTable[noffH.initData.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]),
            noffH.initData.size, noffH.initData.inFileAddr);
    }
    delete executable;   // close file
    return TRUE;   // success
}

System Call example

Slide 裡面有一個實作一個 system call 的 example，只要照著 slide 就能做出一個 system call，和 PrintInt 的功能一樣。
到 /code/userprog/syscall.h 加上 define 和宣告

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define SC_Example 12

void Example(int number); 
/code/userprog/ exception.cc

case SC_Example:
    val=kernel->machine->ReadRegister(4);
    cout << "Example value:" << val << endl;
    return;
/code/test/start.s 加上assembly

    .globl Example
    .ent Example
Example:
    addiu $2,$0,SC_Example
    syscall
    j $31
    .end Example

到/code/test裡面加上一個example.c的檔案

1
2
3
4
5
6
7
#include "syscall.h"
main()
{
    int n;
    for (n=1;n<5;n++)
    Example(n);
}

之後 recompile NachOS，然後和之前一樣到 test/Makefile 裡面加上 example 然後 make example 之後就能跑起來了
順便 Makefile 裡面的格式長這樣

1
2
3
example: example.o start.o
    $(LD) $(LDFLAGS) start.o example.o -o example.coff
    ../bin/coff2noff example.coff example

Implement Sleep()

一開始就先像製造出 Example 一樣的方法
到 /code/userprog/ syscall.h 加上 define 和宣告

1
2
3
#define SC_Sleep 12

void Sleep(int number);

slide 中有提到我們需要實作 WaitUntil，所以我們就用 WaitUntil 來達成 Sleep 的效果
/code/userprog/ exception.cc

1
2
3
4
5
case SC_Example:
    val=kernel->machine->ReadRegister(4);
    cout << "Sleep time:" << val << endl;
    kernel->alarm->WaitUntil(val);
    return;

/code/test/start.s 加上 assembly，根據理解這裡並不是什麼很底層的組語，只是把我們做的 system call 編號放進 $2 裡面在去 call 他而已

1
2
3
4
5
6
7
    .globl Sleep
    .ent Sleep
Sleep:
    addiu $2,$0,SC_Sleep
    syscall
    j $31
    .end Sleep

接著就要完成 WaitUntil 了，在 /code/threads/alarm.h 中已經有宣告這個 function 了，要在 /code/threads/alarm.cc 中完成他
不過因為還會需要加上一些東西所以還是有動到 /code/threads/alarm.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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 多 include 這兩個檔案
#ifndef ALARM_H
#define ALARM_H

#include "copyright.h"
#include "utility.h"
#include "callback.h"
#include "timer.h"
#include <list>
#include "thread.h"

class SleepList {
    public:
        SleepList():counter(0) {};
        void PutToSleep(Thread *t, int x);
 bool PutToReady();
 bool IsEmpty();
    private:
        // 包含這個 thread 的 sleep 結束時間的物件
        class SleepThread {
            public:
         SleepThread(Thread* t, int x):sleeper(t), when(x) {};
         Thread* sleeper;
         int when;    // 結束時間
        };
        int counter;    // 這個 counter 是不停累加上去的，每一次呼叫 PutToReady 都會增加
        std::list<sleepthread> threadlist;    // 存放 sleep 中的 thread
};

// The following class defines a software alarm clock. 
class Alarm : public CallBackObj {
  public:
    Alarm(bool doRandomYield); // Initialize the timer, and callback 
    // to "toCall" every time slice.
    ~Alarm() { delete timer; }
    
    void WaitUntil(int x); // suspend execution until time > now + x
    SleepList sleepList; // for implementing Sleep() function.

  private:
    Timer *timer;  // the hardware timer device

    void CallBack();  // called when the hardware
    // timer generates an interrupt
};

#endif // ALARM_H

/code/threads/alarm.cc
根據 Morris’ Blog，每隔一段時間每隔一段時間 kernal 就會去呼叫一次 Alarm::CallBack()，所以把 PutToReady() 放進去，變成說每次呼叫 CallBack() 都會去檢查有沒有該醒來的 thread，如果有就把他從 sleeplist 裡面踢掉，並丟去 ReadyToRun 裡面

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void 
Alarm::CallBack() 
{
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = sleepList.PutToReady();

    // 多加上兩個條件，一個是檢查是否 woken，一個是檢查還有沒有正在 sleep 的 thread
    // 若是都沒有就可以關掉 timer 了
    if (status == IdleMode && !woken && sleepList.IsEmpty()) { // is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
     timer->Disable(); // turn off the timer
 }
    } else {   // there's someone to preempt
 interrupt->YieldOnReturn();
    }
}

// implement WaitUntil function.
void 
Alarm::WaitUntil(int x)
{
    // save previous setting as oldLevel and disable interrupt.
    // SetLevel 是決定這個 thread 能不能被 interrupt
    // 這裡是把原本的 level 存起來然後把當前設定成不能被 interrupt
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    sleepList.PutToSleep(t, x);               // put current thread to sleep list.
    kernel->interrupt->SetLevel(oldLevel);    // recover old interrupt state.
}

// check if there is still thread sleeping
bool SleepList::IsEmpty()
{
    return threadlist.size() == 0;
}

// put the thread into sleep list
void SleepList::PutToSleep(Thread*t, int x)
{
    // check if it cannot be interrupt.
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    threadlist.push_back(SleepThread(t, counter + x));  // put into the list
    t->Sleep(false);
}

// will be call in callback
bool SleepList::PutToReady()
{
    bool woken = false;
    counter ++;

    // check all thread in the list if there are thread already finish sleeping
    for(std::list<sleepthread>::iterator it = threadlist.begin();
        it != threadlist.end(); )
    {
        // 'when' 就是被創造時的 counter 加上他要 sleep 的時間，也就是他應該醒來的時間
        // 所以我們檢查 when 跟 counter 來判斷他該不該醒來
        // 'when' is time the thread should wake up
        // if counter >= when, this thread will be ready to run.
        if(counter >= it->when)
        {
            // 若是他該醒來就把從睡覺 list 中去掉，然後把他叫醒 (用 ReadyToRun)
            woken = true;
            kernel->scheduler->ReadyToRun(it->sleeper);
            it = threadlist.erase(it);
        }
        // if the thread is not ready to run, keep checking next thread in the list.
        else
        {
            it++;
        }
    }
    return woken;
}

最後在 test 中寫兩個 .c 檔，讓他們一起跑來看看 sleep 有沒有正確運作。

1
2
3
4
5
6
7
// /code/test/sleep1.c
#include "syscall.h"
main()
{
    Sleep(1000000);
    PrintInt(123);
}

這樣跑十次 sleep2 才會跑一次 sleep1 才對

1
2
3
4
5
6
7
8
9
// /code/test/sleep2.c
#include "syscall.h"
main()
{
    for(int i = 0; i < 20; i++) {
        Sleep(100000);
        PrintInt(i);
    }
}

到這裡作業就完成了，大部分內容參考上面那兩個 blog 的，花了很多時間去看懂他們的 code 和追原有的 code，才去自己寫寫看，只是給自己做個紀錄，還是要花點時間對系統架構更深的理解才會比較得心應手吧，另外還有 Nini 學長的 blog 中提到檢查該醒來的 thread 那邊可以進行的優化有試著去做做看，之後有時間再補上，嗯。

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