---
# System prepended metadata

title: OS lab 2
tags: [os]

---

# a. Trace code

## main.cc
entry point
```cpp=
kernel = new Kernel(argc, argv);
kernel->Initialize();
```
```cpp=
// finally, run an initial user program if requested to do so

		kernel->ExecAll();
```
## Kernel::ExecAll()
* **execfileNum** represent the file need to be executed.
* call **Exec** function to execute every file in execfile table.
* call **Finish()** to terminate current thread.
```cpp=
void Kernel::ExecAll()
{
	for (int i=1;i<=execfileNum;i++) {
		int a = Exec(execfile[i]);
	}
	currentThread->Finish();
    //Kernel::Exec();	
}
```

## Kernel::Exec()
* return the id of executing thread.
* create new thread.
* Because creating a new thread,the thread number increment by 1.
* create address space for new thread.
* call **Thread::Fork()**.
```cpp=
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;
/*
    cout << "Total threads number is " << execfileNum << endl;
    for (int n=1;n<=execfileNum;n++) {
		t[n] = new Thread(execfile[n]);
		t[n]->space = new AddrSpace();
		t[n]->Fork((VoidFunctionPtr) &ForkExecute, (void *)t[n]);
		cout << "Thread " << execfile[n] << " is executing." << endl;
	}
	cout << "debug Kernel::Run finished.\n";	
*/
//  Thread *t1 = new Thread(execfile[1]);
//  Thread *t1 = new Thread("../test/test1");
//  Thread *t2 = new Thread("../test/test2");

//    AddrSpace *halt = new AddrSpace();
//  t1->space = new AddrSpace();
//  t2->space = new AddrSpace();

//    halt->Execute("../test/halt");
//  t1->Fork((VoidFunctionPtr) &ForkExecute, (void *)t1);
//  t2->Fork((VoidFunctionPtr) &ForkExecute, (void *)t2);

//	currentThread->Finish();
//    Kernel::Run();
//  cout << "after ThreadedKernel:Run();" << endl;  // unreachable
}
```

## Thread::Fork(VoidFunctionPtr func, void *arg)
* **func** store the function pointer.
* call **StackAllocate(func, arg)** to allocate stack size.
* call **interrupt->SetLevel()** to disable interrupt before calling scheduler.
* Calling ReadyToRun to fork.
* Enable interrupt.
```cpp=
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);
    scheduler->ReadyToRun(this);	// ReadyToRun assumes that interrupts 
					// are disabled!
    (void) interrupt->SetLevel(oldLevel);
}    
```

## Thread::StackAllocate()
* call AllocBoundedArray system call to assign stack
* initalizing all registers in thread depending on the instruction set.
```cpp=
void
Thread::StackAllocate (VoidFunctionPtr func, void *arg)
{
    stack = (int *) AllocBoundedArray(StackSize * sizeof(int));

#ifdef PARISC
    // HP stack works from low addresses to high addresses
    // everyone else works the other way: from high addresses to low addresses
    stackTop = stack + 16;	// HP requires 64-byte frame marker
    stack[StackSize - 1] = STACK_FENCEPOST;
#endif

#ifdef SPARC
    stackTop = stack + StackSize - 96; 	// SPARC stack must contains at 
					// least 1 activation record 
					// to start with.
    *stack = STACK_FENCEPOST;
#endif 

#ifdef PowerPC // RS6000
    stackTop = stack + StackSize - 16; 	// RS6000 requires 64-byte frame marker
    *stack = STACK_FENCEPOST;
#endif 

#ifdef DECMIPS
    stackTop = stack + StackSize - 4;	// -4 to be on the safe side!
    *stack = STACK_FENCEPOST;
#endif

#ifdef ALPHA
    stackTop = stack + StackSize - 8;	// -8 to be on the safe side!
    *stack = STACK_FENCEPOST;
#endif


#ifdef x86
    // the x86 passes the return address on the stack.  In order for SWITCH() 
    // to go to ThreadRoot when we switch to this thread, the return addres 
    // used in SWITCH() must be the starting address of ThreadRoot.
    stackTop = stack + StackSize - 4;	// -4 to be on the safe side!
    *(--stackTop) = (int) ThreadRoot;
    *stack = STACK_FENCEPOST;
#endif
    
#ifdef PARISC
    machineState[PCState] = PLabelToAddr(ThreadRoot);
    machineState[StartupPCState] = PLabelToAddr(ThreadBegin);
    machineState[InitialPCState] = PLabelToAddr(func);
    machineState[InitialArgState] = arg;
    machineState[WhenDonePCState] = PLabelToAddr(ThreadFinish);
#else
    machineState[PCState] = (void*)ThreadRoot;
    machineState[StartupPCState] = (void*)ThreadBegin;
    machineState[InitialPCState] = (void*)func;
    machineState[InitialArgState] = (void*)arg;
    machineState[WhenDonePCState] = (void*)ThreadFinish;
#endif
}
```

## Kernel::ForkExecute()
* call **AddrSpace::Load()** to detect whether the thread is executable.
* call **AddrSpace::Execute()**
```cpp=
void ForkExecute(Thread *t)
{
	if ( !t->space->Load(t->getName()) ) {
    	return;             // executable not found
    }
	
    t->space->Execute(t->getName());

}
```

## AddrSpace::Execute() 
* assgin current address space to kernel->currentThread
* call **InitRegisters()** to initalize the register.
* call **RestoreState()**.
* call **kernel->machine->Run()**.
```cpp=
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"
}
```

## AddrSpace::InitRegisters()
* assgin 0 to every register.
* assgin 0 to program counter,we start with 0.
* assgin 4 to **NextPCReg** to record next instruction.
* assign the upperbound to **StackReg**.
```cpp=
void
AddrSpace::InitRegisters()
{
    Machine *machine = kernel->machine;
    int i;

    for (i = 0; i < NumTotalRegs; i++)
	machine->WriteRegister(i, 0);

    // Initial program counter -- must be location of "Start", which
    //  is assumed to be virtual address zero
    machine->WriteRegister(PCReg, 0);	

    // Need to also tell MIPS where next instruction is, because
    // of branch delay possibility
    // Since instructions occupy four bytes each, the next instruction
    // after start will be at virtual address four.
    machine->WriteRegister(NextPCReg, 4);

   // Set the stack register to the end of the address space, where we
   // allocated the stack; but subtract off a bit, to make sure we don't
   // accidentally reference off the end!
    machine->WriteRegister(StackReg, numPages * PageSize - 16);
    DEBUG(dbgAddr, "Initializing stack pointer: " << numPages * PageSize - 16);
}
```

## AddrSpace::RestoreState()
* 
```cpp=
void AddrSpace::RestoreState() 
{
    kernel->machine->pageTable = pageTable;
    kernel->machine->pageTableSize = numPages;
}
```

## Kernel::Kernel()
* argc: number of strings pointed by argv.
* argv: strings to store every argument.
* using **strcmp** in c standard libaray to handle argument type,if the argument need second parameter,it will use **ASSERT** to check.
```cpp=
Kernel::Kernel(int argc, char **argv)
{
    randomSlice = FALSE; 
    debugUserProg = FALSE;
    consoleIn = NULL;          // default is stdin
    consoleOut = NULL;         // default is stdout
#ifndef FILESYS_STUB
    formatFlag = FALSE;
#endif
    reliability = 1;            // network reliability, default is 1.0
    hostName = 0;               // machine id, also UNIX socket name
                                // 0 is the default machine id
    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], "-s") == 0) {
            debugUserProg = TRUE;
		} else if (strcmp(argv[i], "-e") == 0) {
        	execfile[++execfileNum]= argv[++i];
			cout << execfile[execfileNum] << "\n";
		} else if (strcmp(argv[i], "-ci") == 0) {
	    	ASSERT(i + 1 < argc);
	    	consoleIn = argv[i + 1];
	    	i++;
		} else if (strcmp(argv[i], "-co") == 0) {
	    	ASSERT(i + 1 < argc);
	    	consoleOut = argv[i + 1];
	    	i++;
#ifndef FILESYS_STUB
		} else if (strcmp(argv[i], "-f") == 0) {
	    	formatFlag = TRUE;
#endif
        } else if (strcmp(argv[i], "-n") == 0) {
            ASSERT(i + 1 < argc);   // next argument is float
            reliability = atof(argv[i + 1]);
            i++;
        } else if (strcmp(argv[i], "-m") == 0) {
            ASSERT(i + 1 < argc);   // next argument is int
            hostName = atoi(argv[i + 1]);
            i++;
        } else if (strcmp(argv[i], "-u") == 0) {
            cout << "Partial usage: nachos [-rs randomSeed]\n";
	   		cout << "Partial usage: nachos [-s]\n";
            cout << "Partial usage: nachos [-ci consoleIn] [-co consoleOut]\n";
#ifndef FILESYS_STUB
	    	cout << "Partial usage: nachos [-nf]\n";
#endif
            cout << "Partial usage: nachos [-n #] [-m #]\n";
		}
    }
}
```



## Scheduler::ReadyToRun() 
* Using **ASSERT** to check whether kernel disable interrrupt.
* set thread status to ready.
* append this thread to readyList.
```cpp=
void
Scheduler::ReadyToRun (Thread *thread)
{
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName());
	//cout << "Putting thread on ready list: " << thread->getName() << endl ;
    thread->setStatus(READY);
    readyList->Append(thread);
}
```

## CheckToBeDestroyed()
* If **toBeDestroyed** contains threads,we will delete it and set **toBeDestroyed** to NULL.
```cpp=
void
Scheduler::CheckToBeDestroyed()
{
    if (toBeDestroyed != NULL) {
        delete toBeDestroyed;
	toBeDestroyed = NULL;
    }
}
```
## AddrSpace::AddrSpace()
* **NumPhysPages**:number of physical pages available in the machime.
* create a pagetable and initalize data.
* 
* calling bzero to clean the memory space.
```cpp=
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);
}
```


## Thread::Finish ()
* disable interrupt.
* call **Thread::Sleep()** to current thread.
```cpp=
void
Thread::Finish ()
{
    (void) kernel->interrupt->SetLevel(IntOff);		
    ASSERT(this == kernel->currentThread);
    
    DEBUG(dbgThread, "Finishing thread: " << name);
    Sleep(TRUE);				// invokes SWITCH
    // not reached
}
```
## Thread::Sleep ()
* When entering this function ,interrupt should be disable,we use **ASSERT** to check that.
* set thread status to BLOCKED
* If the scheduler find out the ready queue is empty,it will let machine idle.
* call **Scheduler::Run()**.
```cpp=
void
Thread::Sleep (bool finishing)
{
    Thread *nextThread;
    
    ASSERT(this == kernel->currentThread);
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    
    DEBUG(dbgThread, "Sleeping thread: " << name);
    DEBUG(dbgTraCode, "In Thread::Sleep, Sleeping thread: " << name << ", " << kernel->stats->totalTicks);

    status = BLOCKED;
	//cout << "debug Thread::Sleep " << name << "wait for Idle\n";
    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); 
}
```

## Scheduler::Run ()
* **oldThread**: represents current runing thread.
* if oldThread space does not equal to null,call **SaveUserState()** and **SaveState()** to save current memory content.
* check whether **oldThread** is overflow.
* updating current running thread to **nextThread**,**nextThread** is the upcoming thread to execute.
* call SWITCH ...
* set the nextThread to status of running.
* call **CheckToBeDestroyed()** to delete oldThread.
```cpp=
void
Scheduler::Run ()
{
    Thread *oldThread = kernel->currentThread;
    
    ASSERT(kernel->interrupt->getLevel() == IntOff);

    if (finishing) {	// mark that we need to delete current thread
         ASSERT(toBeDestroyed == NULL);
	 toBeDestroyed = oldThread;
    }
    
    if (oldThread->space != NULL) {	// if this thread is a user program,
        oldThread->SaveUserState(); 	// save the user's CPU registers
	oldThread->space->SaveState();
    }
    
    oldThread->CheckOverflow();		    // check if the old thread
					    // had an undetected stack overflow

    kernel->currentThread = nextThread;  // switch to the next thread
    nextThread->setStatus(RUNNING);      // nextThread is now running
    
    DEBUG(dbgThread, "Switching from: " << oldThread->getName() << " to: " << nextThread->getName());
    
    // This is a machine-dependent assembly language routine defined 
    // in switch.s.  You may have to think
    // a bit to figure out what happens after this, both from the point
    // of view of the thread and from the perspective of the "outside world".

    SWITCH(oldThread, nextThread);

    // we're back, running oldThread
      
    // interrupts are off when we return from switch!
    ASSERT(kernel->interrupt->getLevel() == IntOff);

    DEBUG(dbgThread, "Now in thread: " << oldThread->getName());

    CheckToBeDestroyed();		// check if thread we were running
					// before this one has finished
					// and needs to be cleaned up
    
    if (oldThread->space != NULL) {	    // if there is an address space
        oldThread->RestoreUserState();     // to restore, do it.
	oldThread->space->RestoreState();
    }
}
```

## AddrSpace::Load() 
* calculate the size of address space.
* calling divRoundUp(size, PageSize) to get the number of pages.
* using **numPages** to store the result 
* calling kernel->fileSystem->Open(fileName) to open file.
* If we can oper file successfully,return true.Otherwise, return false.
```cpp=
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);

#ifdef RDATA
// how big is address space?
    size = noffH.code.size + noffH.readonlyData.size + noffH.initData.size +
           noffH.uninitData.size + UserStackSize;	
                                                // we need to increase the size
						// to leave room for the stack
#else
// 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
#endif
    numPages = divRoundUp(size, PageSize);
    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
// Note: this code assumes that virtual address = physical address
    if (noffH.code.size > 0) {
        DEBUG(dbgAddr, "Initializing code segment.");
	DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);
        executable->ReadAt(
		&(kernel->machine->mainMemory[noffH.code.virtualAddr]), 
			noffH.code.size, noffH.code.inFileAddr);
    }
    if (noffH.initData.size > 0) {
        DEBUG(dbgAddr, "Initializing data segment.");
	DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);
        executable->ReadAt(
		&(kernel->machine->mainMemory[noffH.initData.virtualAddr]),
			noffH.initData.size, noffH.initData.inFileAddr);
    }

#ifdef RDATA
    if (noffH.readonlyData.size > 0) {
        DEBUG(dbgAddr, "Initializing read only data segment.");
	DEBUG(dbgAddr, noffH.readonlyData.virtualAddr << ", " << noffH.readonlyData.size);
        executable->ReadAt(
		&(kernel->machine->mainMemory[noffH.readonlyData.virtualAddr]),
			noffH.readonlyData.size, noffH.readonlyData.inFileAddr);
    }
#endif

    delete executable;			// close file
    return TRUE;			// success
}
```
## 跟address space 有關的檔案
* RDATA represens read only data.
* segment defined in noff.h
### segment definition
```cpp=
typedef struct segment {
  int virtualAddr;		/* location of segment in virt addr space */
  int inFileAddr;		/* location of segment in this file */
  int size;			/* size of segment */
} Segment;

```
### noff header 
```cpp=
typedef struct noffHeader {
   int noffMagic;		/* should be NOFFMAGIC */
   Segment code;		/* executable code segment */ 
   Segment initData;		/* initialized data segment */
#ifdef RDATA
   Segment readonlyData;	/* read only data */
#endif
   Segment uninitData;		/* uninitialized data segment --
				 * should be zero'ed before use 
				 */
} NoffHeader;
```
## SwapHeader(NoffHeader *noffH)
* transform header bytes from little endian to big endian. 
```cpp=
static void
SwapHeader(NoffHeader *noffH)
{
    noffH->noffMagic = WordToHost(noffH->noffMagic);
    noffH->code.size = WordToHost(noffH->code.size);
    noffH->code.virtualAddr = WordToHost(noffH->code.virtualAddr);
    noffH->code.inFileAddr = WordToHost(noffH->code.inFileAddr);
#ifdef RDATA
    noffH->readonlyData.size = WordToHost(noffH->readonlyData.size);
    noffH->readonlyData.virtualAddr =
        WordToHost(noffH->readonlyData.virtualAddr);
    noffH->readonlyData.inFileAddr =
        WordToHost(noffH->readonlyData.inFileAddr);
#endif
    noffH->initData.size = WordToHost(noffH->initData.size);
    noffH->initData.virtualAddr = WordToHost(noffH->initData.virtualAddr);
    noffH->initData.inFileAddr = WordToHost(noffH->initData.inFileAddr);
    noffH->uninitData.size = WordToHost(noffH->uninitData.size);
    noffH->uninitData.virtualAddr = WordToHost(noffH->uninitData.virtualAddr);
    noffH->uninitData.inFileAddr = WordToHost(noffH->uninitData.inFileAddr);

#ifdef RDATA
    DEBUG(dbgAddr, "code = " << noffH->code.size << " readonly = " << noffH->readonlyData.size << " init = " << noffH->initData.size << " uninit = " << noffH->uninitData.size << "\n");
#endif
}
```
## OpenFile::ReadAt(char *into, int numBytes, int position)

```cpp=
int
OpenFile::ReadAt(char *into, int numBytes, int position)
{
    int fileLength = hdr->FileLength();
    int i, firstSector, lastSector, numSectors;
    char *buf;

    if ((numBytes <= 0) || (position >= fileLength))
    	return 0; 				// check request
    if ((position + numBytes) > fileLength)		
	numBytes = fileLength - position;
    DEBUG(dbgFile, "Reading " << numBytes << " bytes at " << position << " from file of length " << fileLength);

    firstSector = divRoundDown(position, SectorSize);
    lastSector = divRoundDown(position + numBytes - 1, SectorSize);
    numSectors = 1 + lastSector - firstSector;

    // read in all the full and partial sectors that we need
    buf = new char[numSectors * SectorSize];
    for (i = firstSector; i <= lastSector; i++)	
        kernel->synchDisk->ReadSector(hdr->ByteToSector(i * SectorSize), 
					&buf[(i - firstSector) * SectorSize]);

    // copy the part we want
    bcopy(&buf[position - (firstSector * SectorSize)], into, numBytes);
    delete [] buf;
    return numBytes;
}
```


# b. Implementattion
我有修改的部分
```cpp=

// kernel.cc
//	Initialization and cleanup routines for the Nachos kernel.
//
// Copyright (c) 1992-1996 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "debug.h"
#include "main.h"
#include "kernel.h"
#include "sysdep.h"
#include "synch.h"
#include "synchlist.h"
#include "libtest.h"
#include "string.h"
#include "synchdisk.h"
#include "post.h"
#include "synchconsole.h"

//----------------------------------------------------------------------
// Kernel::Kernel
// 	Interpret command line arguments in order to determine flags
//	for the initialization (see also comments in main.cc)
//----------------------------------------------------------------------

Kernel::Kernel(int argc, char **argv)
{
    randomSlice = FALSE;
    debugUserProg = FALSE;
    consoleIn = NULL;  // default is stdin
    consoleOut = NULL; // default is stdout
#ifndef FILESYS_STUB
    formatFlag = FALSE;
#endif
    reliability = 1; // network reliability, default is 1.0
    hostName = 0;    // machine id, also UNIX socket name
                     // 0 is the default machine id
    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], "-s") == 0)
        {
            debugUserProg = TRUE;
        }
        else if (strcmp(argv[i], "-e") == 0)
        {
            execfile[++execfileNum] = argv[++i];
            cout << execfile[execfileNum] << "\n";
        }
        else if (strcmp(argv[i], "-ci") == 0)
        {
            ASSERT(i + 1 < argc);
            consoleIn = argv[i + 1];
            i++;
        }
        else if (strcmp(argv[i], "-co") == 0)
        {
            ASSERT(i + 1 < argc);
            consoleOut = argv[i + 1];
            i++;
#ifndef FILESYS_STUB
        }
        else if (strcmp(argv[i], "-f") == 0)
        {
            formatFlag = TRUE;
#endif
        }
        else if (strcmp(argv[i], "-n") == 0)
        {
            ASSERT(i + 1 < argc); // next argument is float
            reliability = atof(argv[i + 1]);
            i++;
        }
        else if (strcmp(argv[i], "-m") == 0)
        {
            ASSERT(i + 1 < argc); // next argument is int
            hostName = atoi(argv[i + 1]);
            i++;
        }
        else if (strcmp(argv[i], "-u") == 0)
        {
            cout << "Partial usage: nachos [-rs randomSeed]\n";
            cout << "Partial usage: nachos [-s]\n";
            cout << "Partial usage: nachos [-ci consoleIn] [-co consoleOut]\n";
#ifndef FILESYS_STUB
            cout << "Partial usage: nachos [-nf]\n";
#endif
            cout << "Partial usage: nachos [-n #] [-m #]\n";
        }
    }
}

//----------------------------------------------------------------------
// Kernel::Initialize
// 	Initialize Nachos global data structures.  Separate from the
//	constructor because some of these refer to earlier initialized
//	data via the "kernel" global variable.
//----------------------------------------------------------------------

void Kernel::Initialize()
{
    // We didn't explicitly allocate the current thread we are running in.
    // But if it ever tries to give up the CPU, we better have a Thread
    // object to save its state.

    currentThread = new Thread("main", threadNum++);
    currentThread->setStatus(RUNNING);
    // 0 : means unused
    // 1 : means used
    availFrameTable = new int[NumPhysPages];
    for (int i = 0; i < NumPhysPages; i++)
        availFrameTable[i] = 0;
    stats = new Statistics();       // collect statistics
    interrupt = new Interrupt;      // start up interrupt handling
    scheduler = new Scheduler();    // initialize the ready queue
    alarm = new Alarm(randomSlice); // start up time slicing
    machine = new Machine(debugUserProg);
    synchConsoleIn = new SynchConsoleInput(consoleIn);    // input from stdin
    synchConsoleOut = new SynchConsoleOutput(consoleOut); // output to stdout
    synchDisk = new SynchDisk();                          //
#ifdef FILESYS_STUB
    fileSystem = new FileSystem();
#else
    fileSystem = new FileSystem(formatFlag);
#endif // FILESYS_STUB
    postOfficeIn = new PostOfficeInput(10);
    postOfficeOut = new PostOfficeOutput(reliability);

    interrupt->Enable();
}

//----------------------------------------------------------------------
// Kernel::~Kernel
// 	Nachos is halting.  De-allocate global data structures.
//----------------------------------------------------------------------

Kernel::~Kernel()
{
    delete stats;
    delete interrupt;
    delete scheduler;
    delete alarm;
    delete machine;
    delete synchConsoleIn;
    delete synchConsoleOut;
    delete synchDisk;
    delete fileSystem;
    delete postOfficeIn;
    delete postOfficeOut;
    delete availFrameTable;
    Exit(0);
}

//----------------------------------------------------------------------
// Kernel::ThreadSelfTest
//      Test threads, semaphores, synchlists
//----------------------------------------------------------------------

void Kernel::ThreadSelfTest()
{
    Semaphore *semaphore;
    SynchList<int> *synchList;

    LibSelfTest(); // test library routines

    currentThread->SelfTest(); // test thread switching

    // test semaphore operation
    semaphore = new Semaphore("test", 0);
    semaphore->SelfTest();
    delete semaphore;

    // test locks, condition variables
    // using synchronized lists
    synchList = new SynchList<int>;
    synchList->SelfTest(9);
    delete synchList;
}

//----------------------------------------------------------------------
// Kernel::ConsoleTest
//      Test the synchconsole
//----------------------------------------------------------------------

void Kernel::ConsoleTest()
{
    char ch;

    cout << "Testing the console device.\n"
         << "Typed characters will be echoed, until ^D is typed.\n"
         << "Note newlines are needed to flush input through UNIX.\n";
    cout.flush();

    do
    {
        ch = synchConsoleIn->GetChar();
        if (ch != EOF)
            synchConsoleOut->PutChar(ch); // echo it!
    } while (ch != EOF);

    cout << "\n";
}

//----------------------------------------------------------------------
// Kernel::NetworkTest
//      Test whether the post office is working. On machines #0 and #1, do:
//
//      1. send a message to the other machine at mail box #0
//      2. wait for the other machine's message to arrive (in our mailbox #0)
//      3. send an acknowledgment for the other machine's message
//      4. wait for an acknowledgement from the other machine to our
//          original message
//
//  This test works best if each Nachos machine has its own window
//----------------------------------------------------------------------

void Kernel::NetworkTest()
{

    if (hostName == 0 || hostName == 1)
    {
        // if we're machine 1, send to 0 and vice versa
        int farHost = (hostName == 0 ? 1 : 0);
        PacketHeader outPktHdr, inPktHdr;
        MailHeader outMailHdr, inMailHdr;
        char *data = "Hello there!";
        char *ack = "Got it!";
        char buffer[MaxMailSize];

        // construct packet, mail header for original message
        // To: destination machine, mailbox 0
        // From: our machine, reply to: mailbox 1
        outPktHdr.to = farHost;
        outMailHdr.to = 0;
        outMailHdr.from = 1;
        outMailHdr.length = strlen(data) + 1;

        // Send the first message
        postOfficeOut->Send(outPktHdr, outMailHdr, data);

        // Wait for the first message from the other machine
        postOfficeIn->Receive(0, &inPktHdr, &inMailHdr, buffer);
        cout << "Got: " << buffer << " : from " << inPktHdr.from << ", box "
             << inMailHdr.from << "\n";
        cout.flush();

        // Send acknowledgement to the other machine (using "reply to" mailbox
        // in the message that just arrived
        outPktHdr.to = inPktHdr.from;
        outMailHdr.to = inMailHdr.from;
        outMailHdr.length = strlen(ack) + 1;
        postOfficeOut->Send(outPktHdr, outMailHdr, ack);

        // Wait for the ack from the other machine to the first message we sent
        postOfficeIn->Receive(1, &inPktHdr, &inMailHdr, buffer);
        cout << "Got: " << buffer << " : from " << inPktHdr.from << ", box "
             << inMailHdr.from << "\n";
        cout.flush();
    }

    // Then we're done!
}

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

    t->space->Execute(t->getName());
}

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

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;
    /*
        cout << "Total threads number is " << execfileNum << endl;
        for (int n=1;n<=execfileNum;n++) {
            t[n] = new Thread(execfile[n]);
            t[n]->space = new AddrSpace();
            t[n]->Fork((VoidFunctionPtr) &ForkExecute, (void *)t[n]);
            cout << "Thread " << execfile[n] << " is executing." << endl;
        }
        cout << "debug Kernel::Run finished.\n";
    */
    //  Thread *t1 = new Thread(execfile[1]);
    //  Thread *t1 = new Thread("../test/test1");
    //  Thread *t2 = new Thread("../test/test2");

    //    AddrSpace *halt = new AddrSpace();
    //  t1->space = new AddrSpace();
    //  t2->space = new AddrSpace();

    //    halt->Execute("../test/halt");
    //  t1->Fork((VoidFunctionPtr) &ForkExecute, (void *)t1);
    //  t2->Fork((VoidFunctionPtr) &ForkExecute, (void *)t2);

    //	currentThread->Finish();
    //    Kernel::Run();
    //  cout << "after ThreadedKernel:Run();" << endl;  // unreachable
}

int Kernel::allocateFrame()
{
    for (int frame = 0; frame < NumPhysPages; frame++)
    {
        if (!availFrameTable[frame])
        {
            availFrameTable[frame] = 1;
            return frame;
        }
    }
    return -1;
}
```
## kernel.h
```cpp=
// kernel.h
//	Global variables for the Nachos kernel.
//
// Copyright (c) 1992-1996 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#ifndef KERNEL_H
#define KERNEL_H

#include "copyright.h"
#include "debug.h"
#include "utility.h"
#include "thread.h"
#include "scheduler.h"
#include "interrupt.h"
#include "stats.h"
#include "alarm.h"
#include "filesys.h"
#include "machine.h"

class PostOfficeInput;
class PostOfficeOutput;
class SynchConsoleInput;
class SynchConsoleOutput;
class SynchDisk;

typedef int OpenFileId;

class Kernel {
  public:
    Kernel(int argc, char **argv);
    				// Interpret command line arguments
    ~Kernel();		        // deallocate the kernel
    
    void Initialize(); 		// initialize the kernel -- separated
				// from constructor because 
				// refers to "kernel" as a global
    void ExecAll();
    int Exec(char* name);
    void ThreadSelfTest();	// self test of threads and synchronization
	
    void ConsoleTest();         // interactive console self test
    void NetworkTest();         // interactive 2-machine network test
    Thread* getThread(int threadID){return t[threadID];}    

    int allocateFrame();
    void PrintInt(int number); 	
    int CreateFile(char* filename); // fileSystem call
    
    OpenFileId OpenFile(char* name); // fileSystem call
    int WriteFile(char* buffer, int size, OpenFileId id); // fileSystem call
    int ReadFile(char* buffer, int size, OpenFileId id); // fileSystem call
    int CloseFile(OpenFileId id); // fileSystem call

// These are public for notational convenience; really, 
// they're global variables used everywhere.

    Thread *currentThread;	// the thread holding the CPU
    Scheduler *scheduler;	// the ready list
    Interrupt *interrupt;	// interrupt status
    Statistics *stats;		// performance metrics
    Alarm *alarm;		// the software alarm clock    
    Machine *machine;           // the simulated CPU
    SynchConsoleInput *synchConsoleIn;
    SynchConsoleOutput *synchConsoleOut;
    SynchDisk *synchDisk;
    FileSystem *fileSystem;     
    PostOfficeInput *postOfficeIn;
    PostOfficeOutput *postOfficeOut;

    int hostName;               // machine identifier
    int *availFrameTable;
  private:
  
	Thread* t[10];
	char*   execfile[10];
	int execfileNum;
	int threadNum;
    bool randomSlice;		// enable pseudo-random time slicing
    bool debugUserProg;         // single step user program
    double reliability;         // likelihood messages are dropped
    char *consoleIn;            // file to read console input from
    char *consoleOut;           // file to send console output to
#ifndef FILESYS_STUB
    bool formatFlag;          // format the disk if this is true
#endif
};


#endif // KERNEL_H



```

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

```

## bool AddrSpace::Load(char *fileName)
```cpp=
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); // change file from little endian to big endian
    ASSERT(noffH.noffMagic == NOFFMAGIC);

#ifdef RDATA
    // how big is address space?
    size = noffH.code.size + noffH.readonlyData.size + noffH.initData.size +
           noffH.uninitData.size + UserStackSize;
    // we need to increase the size
    // to leave room for the stack
#else
    // 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
#endif
    numPages = divRoundUp(size, PageSize);
    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);

    pageTable = new TranslationEntry[numPages];
    for (int i = 0; i < numPages; i++)
    {
        // physical address!=virtual address
        int frame = kernel->allocateFrame();
        DEBUG(dbgAddr, "Frame number" << frame);
        if (frame == -1)
        {
            kernel->interrupt->setStatus(SystemMode);
            ExceptionHandler(MemoryLimitException);
            kernel->interrupt->setStatus(UserMode);
        }
        pageTable[i].virtualPage = i;
        pageTable[i].physicalPage = frame;
        pageTable[i].valid = TRUE;
        pageTable[i].use = FALSE;
        pageTable[i].dirty = FALSE;
        pageTable[i].readOnly = FALSE;
        bzero(kernel->machine->mainMemory + frame * PageSize, PageSize);
    }

    unsigned int physical_address;
    if (noffH.code.size > 0)
    {
        DEBUG(dbgAddr, "Initializing code segment.");
        DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);

        for (int capacity = noffH.code.size, offset = 0; capacity > 0; capacity -= PageSize, offset += PageSize)
        {
            unsigned int loadsize;
            if (capacity < PageSize)
            {
                loadsize = capacity;
            }
            else
            {
                loadsize = PageSize;
            }
            // translate : virtual address,physical address, int isReadWrite
            ExceptionType result = Translate(noffH.code.virtualAddr, &physical_address, 1);
            // get physcial address
            DEBUG(dbgAddr, physical_address << "\n");
            if (result != NoException)
            {
                kernel->interrupt->setStatus(SystemMode);
                ExceptionHandler(result);
                kernel->interrupt->setStatus(UserMode);
            }
            executable->ReadAt(
                &(kernel->machine->mainMemory[physical_address]),
                loadsize, noffH.code.inFileAddr + offset);
        }
    }
    if (noffH.initData.size > 0)
    {
        DEBUG(dbgAddr, "Initializing data segment.");
        DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);
        for (int capacity = noffH.initData.size, offset = 0; capacity > 0; capacity -= PageSize, offset += PageSize)
        {
            unsigned int loadsize;
            if (capacity < PageSize)
            {
                loadsize = capacity;
            }
            else
            {
                loadsize = PageSize;
            }
            // translate : virtual address,physical address, int isReadWrite
            ExceptionType result = Translate(noffH.initData.virtualAddr, &physical_address, 1);
            // get physcial address
            DEBUG(dbgAddr, physical_address << "\n");
            if (result != NoException)
            {
                kernel->interrupt->setStatus(SystemMode);
                ExceptionHandler(result);
                kernel->interrupt->setStatus(UserMode);
            }
            executable->ReadAt(
                &(kernel->machine->mainMemory[physical_address]),
                loadsize, noffH.initData.inFileAddr + offset);
        }
    }

#ifdef RDATA
    if (noffH.readonlyData.size > 0)
    {
        DEBUG(dbgAddr, "Initializing read only data segment.");
        DEBUG(dbgAddr, noffH.readonlyData.virtualAddr << ", " << noffH.readonlyData.size);
        for (int i = noffH.readonlyData.size, pos = 0; i > 0; i -= PageSize, pos += PageSize)
        {
            unsigned loadsize;
            i < PageSize ? loadsize = i : loadsize = PageSize;
            unsigned int p = divRoundUp(noffH.readonlyData.size, PageSize);
            for (int j = 0; j < p; j++)
                pageTable[noffH.readonlyData.size / PageSize + j].readOnly = TRUE;
            ExceptionType result = Translate(noffH.readonlyData.virtualAddr, &physical_address, false);
            if (result != NoException)
            {
                kernel->interrupt->setStatus(SystemMode);
                ExceptionHandler(result);
                kernel->interrupt->setStatus(UserMode);
            }
            executable->ReadAt(
                &(kernel->machine->mainMemory[physical_address]),
                loadsize, noffH.readonlyData.inFileAddr + pos);
        }
    }
#endif
    delete executable; // close file
    return TRUE;       // success
}
```

## AddrSpace::Translate(unsigned int vaddr, unsigned int *paddr, int isReadWrite)
```cpp=
ExceptionType
AddrSpace::Translate(unsigned int vaddr, unsigned int *paddr, int isReadWrite)
{
    TranslationEntry *pte;
    int pfn;
    // virtual page number
    unsigned int vpn = vaddr / PageSize;
    unsigned int offset = vaddr % PageSize;

    if (vpn >= numPages)
    {
        return AddressErrorException;
    }

    pte = &pageTable[vpn];

    if (isReadWrite && pte->readOnly)
    {
        return ReadOnlyException;
    }

    pfn = pte->physicalPage;

    // if the pageFrame is too big, there is something really wrong!
    // An invalid translation was loaded into the page table or TLB.
    if (pfn >= NumPhysPages)
    {
        DEBUG(dbgAddr, "Illegal physical page " << pfn);
        return BusErrorException;
    }

    pte->use = TRUE; // set the use, dirty bits

    if (isReadWrite)
        pte->dirty = TRUE;

    *paddr = pfn * PageSize + offset;
    if ((*paddr >= MemorySize))
    {
        return MemoryLimitException;
    }
    // ASSERT((*paddr < MemorySize));
    // cerr << " -- AddrSpace::Translate(): vaddr: " << vaddr <<
    //   ", paddr: " << *paddr << "\n";

    return NoException;
}
```