# Team10
## Team member:李侑庭(110062172), 盧思樺(110062272)

| 部分 | 李侑庭 | 盧思樺 |
| -------- | -------- | -------- |
| Trace code | 50% | 50% |
| Implement | 60% | 40% |
| Report | 70% | 30% |
| Testing | 30% | 70% |
# Part 1:Trace code
## 1-1 threads/thread.cc
### (1) Sleep(bool finishing)
* this thread will relinquish CPU.
* Use **ASSERT** to check whether interrupt is disable and currrentThread is this thread.
* Set thread status to BLOCKED.
* If the ready queue of the scheduler is empty, call kernel->interrupt->Idle() function to advance simulated time until the next scheduled hardware interrupt.
* call **Scheduler::Run()** with parameters nextThread and finishing.

void Thread::Sleep (bool finishing)
{
    Thread *nextThread;
    ASSERT(this == kernel->currentThread);
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    status = BLOCKED;
    while ((nextThread = kernel->scheduler->FindNextToRun()) == NULL) {
        kernel->interrupt->Idle();	// no one to run, wait for an interrupt
    }    
    // returns when it's time for us to run
    kernel->scheduler->Run(nextThread, finishing); 
}

### (2) StackAllocate(VoidFunctionPtr func, void *arg)
* Call **AllocBoundedArray** function to allocate and initialize stack.
* Change stack pointer by the instruction set.
### (3) Finish()
* Disable interrupt.
* Use **ASSERT** to check whether currrentThread is this thread.
* Call **Sleep()** to current thread.

void Thread::Finish ()
{
    (void) kernel->interrupt->SetLevel(IntOff);		
    ASSERT(this == kernel->currentThread);
    Sleep(TRUE);				
}

### (4) Fork(VoidFunctionPtr func, void *arg)
* **func** store the function pointer.
* Call **StackAllocate(func, arg)** to allocate stack.
* Call **interrupt->SetLevel()** to disable interrupt before calling scheduler.
* Call **scheduler->ReadyToRun(this)** to make this thread ready and put it into ready queue.
* Restore the interrupt level to its previous state.

void Thread::Fork(VoidFunctionPtr func, void *arg)
{
    Interrupt *interrupt = kernel->interrupt;
    Scheduler *scheduler = kernel->scheduler;
    IntStatus oldLevel;
    StackAllocate(func, arg);
    oldLevel = interrupt->SetLevel(IntOff);
    scheduler->ReadyToRun(this);	// ReadyToRun assumes that interrupts 
					// are disabled!
    (void) interrupt->SetLevel(oldLevel);
}    

## 1-2 userprog/addrspace.cc
### (1) AddrSpace()
* **NumPhysPages** : number of physical pages available in the machine.
* Create a pagetable and initalize data(**virtualPage == physicalPage, valid = TRUE, use = FALSE, dirty = FALSE, readOnly = FALSE**).
* Call bzero to set memory space to 0.

AddrSpace::AddrSpace()
{
    pageTable = new TranslationEntry[NumPhysPages];
    for (int i = 0; i < NumPhysPages; i++) {
	pageTable[i].virtualPage = i;	// for now, virt page # = phys page #
	pageTable[i].physicalPage = i;
	pageTable[i].valid = TRUE;
	pageTable[i].use = FALSE;
	pageTable[i].dirty = FALSE;
	pageTable[i].readOnly = FALSE;  
    }
    // zero out the entire address space
    bzero(kernel->machine->mainMemory, MemorySize);
}

### (2) Execute(char *fileName)
* assgin current address space to **kernel->currentThread**.
* call **InitRegisters()** to set program counter to 0 and set next program counter to 4.
* call **RestoreState()** to load pageTable.
* call **kernel->machine->Run()** to run the user progam.

void AddrSpace::Execute(char* fileName) 
{
    kernel->currentThread->space = this;
    this->InitRegisters();		// set the initial register values
    this->RestoreState();		// load page table register
    kernel->machine->Run();		// jump to the user progam
    ASSERTNOTREACHED();			// machine->Run never returns;
    // the address space exits
    // by doing the syscall "exit"
}

### (3) Load(char *fileName)
* Open file by filename(and check if the file is opened)
* Call **ReadAt()** function to read NoffHeader. If **NoffHeader.noffMagic** doesn't match **NOFFMAGIC** change file from little endian to big endian.
* Calculate the size of address space.
* Call **divRoundUp(size, PageSize)** to get the number of pages and store in **numPages**.
* Change size to numPages * PageSize.
* If code segment size > 0, place the code segment in the main memory at the virtual address of code.
* If initData segment size > 0, place the initData segment in the main memory at the virtual address of initData.
* Close the file.
## 1-3 threads/kernel.cc
### (1) Kernel(int argc, char **argv)
* argc: number of strings pointed by argv.
* argv: strings to store every argument.
* Use **strcmp** in c standard libaray to handle argument type,if the argument need second parameter,it will use **ASSERT** to check.

### (2) ExecAll()
* **execfileNum** represent the file number need to be executed.
* Call **Exec** function to execute every file in execfile table.
* Call **Finish()** to relinquish CPU.

void Kernel::ExecAll()
{
    for (int i=1;i<=execfileNum;i++) {
        int a = Exec(execfile[i]);
    }
    currentThread->Finish();	
}

### (3) Exec()
* Create new thread and maintain the thread table.
* Create address space for new thread.
* Call **fork()**.
* Return the id of executing thread.

int Kernel::Exec(char* name)
{
	t[threadNum] = new Thread(name, threadNum);
	t[threadNum]->space = new AddrSpace();
	t[threadNum]->Fork((VoidFunctionPtr) &ForkExecute, (void *)t[threadNum]);
	threadNum++;
	return threadNum-1;
}

### (4) ForkExecute()
* Call **AddrSpace::Load()** to check whether the user program can load and load the file into memory.
* Call **AddrSpace::Execute()** to run the user program.

void ForkExecute(Thread *t)
{
	if ( !t->space->Load(t->getName()) ) {
    	return;             // executable not found
    }
    t->space->Execute(t->getName());
}

## 1-4 threads/scheduler.cc
### (1) ReadyToRun(Thread *thread)
* Using **ASSERT** to check whether kernel disable interrrupt.
* set thread status to ready.
* append this thread to readyList.

void Scheduler::ReadyToRun (Thread *thread)
{
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    thread->setStatus(READY);
    readyList->Append(thread);
}

### (2) Run()
* **oldThread**: represents current runing thread.
* If oldThread is finishing, assign it to toBeDestroyed to destroy it.
* If oldThread space is not NULL,call **SaveUserState()** and **SaveState()** to save the CPU state.
* Check whether **oldThread** is stack overflow.
* Update current running thread to **nextThread**,**nextThread** is the upcoming thread to execute, and set **nextThread** status to running.
* Call SWITCH() to context switch.
* Call **CheckToBeDestroyed()** to delete oldThread if it is not NULL.
* If the space of the running thread is not NULL,call **RestoreUserState()** and **RestoreState()** to restore the CPU state.

void Scheduler::Run (Thread *nextThread, bool finishing)
{
    Thread *oldThread = kernel->currentThread;
    
    ASSERT(kernel->interrupt->getLevel() == IntOff);

    if (finishing) {
        ASSERT(toBeDestroyed == NULL);
        toBeDestroyed = oldThread;
    }
    
    if (oldThread->space != NULL) {	
        oldThread->SaveUserState(); 	
        oldThread->space->SaveState();
    }
    
    oldThread->CheckOverflow();	

    kernel->currentThread = nextThread;  
    nextThread->setStatus(RUNNING);      

    SWITCH(oldThread, nextThread);
    ASSERT(kernel->interrupt->getLevel() == IntOff);

    CheckToBeDestroyed();		
    
    if (oldThread->space != NULL) {	    
        oldThread->RestoreUserState();    
        oldThread->space->RestoreState();
    }
}

## 1-5 questions
* ### How does Nachos allocate the memory space for a new thread(process)?
Call StackAllocate() function to allocate space.
* ### How does Nachos initialize the memory content of a thread(process), including loading the user binary code in the memory?
AddrSpace::Load() function will load the memory content of the thread.
* ### How does Nachos create and manage the page table?
AddrSpace() constructor will create page table and initialize the value. After implement, the load() function manage the page table.
* ### How does Nachos translate addresses?
Translate() function will translate virtual address to a physical address.
* ### How Nachos initializes the machine status (registers, etc) before running a thread(process)
ForkExecute() function will call t->space->Execute() function. In Execute() function it will set the initial register values and load page table register.
* ### Which object in Nachos acts the role of process control block
Thread, it will store the id, status, stack and user code.

* ### When and how does a thread get added into the ReadyToRun queue of Nachos CPU scheduler?
When call Thread::Fork() function, it will be added into the ReadyToRun queue.
* ### Please look at the following code from urserprog/exception.cc and answer the question:

case SC_MSG:
    DEBUG(dbgSys, "Message received.\n");
    val = kernel->machine->ReadRegister(4);
    {
        char *msg = &(kernel->machine->mainMemory[val]);
        cout << msg << endl;
    }
    SysHalt();
    ASSERTNOTREACHED();
    break;

According to the code above, please explain under what circumstances an error will occur if the message size is larger than one page and why? (Hint: Consider the relationship between physical pages and virtual pages.)

When the number of free page less than 2, an error will occur. Because it can not accommodate all message in memory.
# Part 2:Implement page table in NachOS
## machine.h
We add MemoryLimitException in ExceptionType before NumExceptionTypes.

enum ExceptionType {
    ...
    MemoryLimitException,
    NumExceptionTypes
};

## kernel.h
We add a pointer to a array availFrameTable to record the used frame.
We add a function to allocate a frame.

class Kernel {
public:
...
int allocateFrame();
int *availFrameTable;
...
}

## kernel.cc
In Initialize() function, we allocate space to availFrameTable and initialize all entry 0.

Kernel::Initialize()
{
    availFrameTable = new int[NumPhysPages];
    for (int i = 0; i < NumPhysPages; i++)
        availFrameTable[i] = 0;
    ...
}

We use allocateFrame() function to find the free frame index and set the index in availFrameTable to 1.
If no free frame, return -1.

int Kernel::allocateFrame()
{
    for (int frame = 0; frame < NumPhysPages; frame++)
    {
        if (!availFrameTable[frame])
        {
            availFrameTable[frame] = 1;
            return frame;
        }
    }
    return -1;
}

## addrspace.cc
In constructor of AddrSpace, we set virtualPage, physicalPage, valid, readOnly, use, and dirty field.
We set valid to false and set physicalPage to -1, because it don't load in memory.

AddrSpace::AddrSpace()
{
    pageTable = new TranslationEntry[NumPhysPages];
    for (int i = 0; i < NumPhysPages; i++)
    {
        pageTable[i].virtualPage = i; // for now, virt page # = phys page #
        pageTable[i].physicalPage = -1;
        pageTable[i].valid = FALSE;
        pageTable[i].use = FALSE;
        pageTable[i].dirty = FALSE;
        pageTable[i].readOnly = FALSE;
    }
}

In destructor of AddrSpace, we set the all used physicalPage the to 0.

AddrSpace::~AddrSpace()
{
    for (int i = 0; i < numPages; i++)
    {
        if(pageTable[i].physicalPage != -1){
            kernel->availFrameTable[pageTable[i].physicalPage] = 0;
        }
    }
    delete pageTable;
}

In Load function, we use a for loop to call kernel->allocateFrame() and get a frame and set pageTable vaild entry true.
In code segment and initData segment, we use translate() function to translate virtual address to physical address, check any error occur and read file into memory.

bool AddrSpace::Load(char *fileName){
    ...
    for (int i = 0; i < numPages; i++)
        {
            int frame = kernel->allocateFrame();
            if (frame == -1)
            {
                kernel->interrupt->setStatus(SystemMode);
                ExceptionHandler(MemoryLimitException);
                kernel->interrupt->setStatus(UserMode);
            }
            pageTable[i].physicalPage = frame;
            pageTable[i].valid = TRUE;
            bzero(kernel->machine->mainMemory + frame * PageSize, PageSize);
        }

        unsigned int physical_address;

        if (noffH.code.size > 0)
        {

            DEBUG(dbgAddr, "Initializing code segment.");
            DEBUG(dbgAddr, physical_address << ", " << noffH.code.size);

            ExceptionType result = Translate(noffH.code.virtualAddr, &physical_address, 1);
            if (result != NoException)
            {
                kernel->interrupt->setStatus(SystemMode);
                ExceptionHandler(result);
                kernel->interrupt->setStatus(UserMode);
            }
            executable->ReadAt(
                &(kernel->machine->mainMemory[physical_address]),
                noffH.code.size, noffH.code.inFileAddr);
        }

        if (noffH.initData.size > 0)
        {
            DEBUG(dbgAddr, "Initializing data segment.");
            DEBUG(dbgAddr, physical_address << ", " << noffH.initData.size);

            ExceptionType result = Translate(noffH.initData.virtualAddr, &physical_address, 1);
            if (result != NoException)
            {
                kernel->interrupt->setStatus(SystemMode);
                ExceptionHandler(result);
                kernel->interrupt->setStatus(UserMode);
            }
            executable->ReadAt(
                &(kernel->machine->mainMemory[physical_address]),
                noffH.initData.size, noffH.initData.inFileAddr);
        }
#ifdef RDATA
        unsigned int readonlyPhysicalAddr;
        if (noffH.readonlyData.size > 0)
        {
            DEBUG(dbgAddr, "Initializing read only data segment.");
            DEBUG(dbgAddr, readonlyPhysicalAddr << ", " << noffH.readonlyData.size);

            ExceptionType result = Translate(noffH.readonlyData.virtualAddr, &readonlyPhysicalAddr, 0);
            if (result != NoException)
            {
                kernel->interrupt->setStatus(SystemMode);
                ExceptionHandler(result);
                kernel->interrupt->setStatus(UserMode);
            }

            executable->ReadAt(
                &(kernel->machine->mainMemory[readonlyPhysicalAddr]),
                noffH.readonlyData.size, noffH.readonlyData.inFileAddr);
        }
#endif
}