# OS lab 3
[TOC]
## 1-1. New→Ready
### 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
}
```
## 1-2. Running→Ready
### Machine::Run()
* set mode to user mode
* execute one instrucion once a time
* call **OneTick()** to advance timer
```cpp
void
Machine::Run()
{
Instruction *instr = new Instruction; // storage for decoded instruction
if (debug->IsEnabled('m')) {
cout << "Starting program in thread: " << kernel->currentThread->getName();
cout << ", at time: " << kernel->stats->totalTicks << "\n";
}
kernel->interrupt->setStatus(UserMode);
for (;;) {
DEBUG(dbgTraCode, "In Machine::Run(), into OneInstruction " << "== Tick " << kernel->stats->totalTicks << " ==");
OneInstruction(instr);
DEBUG(dbgTraCode, "In Machine::Run(), return from OneInstruction " << "== Tick " << kernel->stats->totalTicks << " ==");
DEBUG(dbgTraCode, "In Machine::Run(), into OneTick " << "== Tick " << kernel->stats->totalTicks << " ==");
kernel->interrupt->OneTick();
DEBUG(dbgTraCode, "In Machine::Run(), return from OneTick " << "== Tick " << kernel->stats->totalTicks << " ==");
if (singleStep && (runUntilTime <= kernel->stats->totalTicks))
Debugger();
}
}
```
### Interrupt::OneTick()
* get the needed statistics from kernel
* update total ticks,system tick and user ticks
* disable interrupt
* check any pending interrupts are ready to execute
* enable interrupt
* if **yieldOnReturn** is true,it means we need to context switch,then we call **Yield()**。
```cpp=
//----------------------------------------------------------------------
// Interrupt::OneTick
// Advance simulated time and check if there are any pending
// interrupts to be called.
//
// Two things can cause OneTick to be called:
// interrupts are re-enabled
// a user instruction is executed
//----------------------------------------------------------------------
void Interrupt::OneTick()
{
MachineStatus oldStatus = status;
Statistics *stats = kernel->stats;
// advance simulated time
if (status == SystemMode)
{
stats->totalTicks += SystemTick;
stats->systemTicks += SystemTick;
}
else
{
stats->totalTicks += UserTick;
stats->userTicks += UserTick;
}
DEBUG(dbgInt, "== Tick " << stats->totalTicks << " ==");
// check any pending interrupts are now ready to fire
ChangeLevel(IntOn, IntOff); // first, turn off interrupts
// (interrupt handlers run with
// interrupts disabled)
CheckIfDue(FALSE); // check for pending interrupts
ChangeLevel(IntOff, IntOn); // re-enable interrupts
if (yieldOnReturn)
{ // if the timer device handler asked
// for a context switch, ok to do it now
yieldOnReturn = FALSE;
status = SystemMode; // yield is a kernel routine
kernel->currentThread->Yield();
status = oldStatus;
}
}
```
### Thread::Yield()
* disable interrupt
* call **FindNextToRun()** to get next thread to execute
* put current thread to ready queue and execute next thread
* enable interrupt
```cpp=
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)
{
kernel->scheduler->ReadyToRun(this);
kernel->scheduler->Run(nextThread, FALSE);
}
(void)kernel->interrupt->SetLevel(oldLevel);
}
```
### Scheduler::FindNextToRun ()
* If ready list is empty ,return NULL
* Otherwise,remove the first element in the list and return it。
```cpp=
Thread *
Scheduler::FindNextToRun ()
{
ASSERT(kernel->interrupt->getLevel() == IntOff);
if (readyList->IsEmpty()) {
return NULL;
} else {
return readyList->RemoveFront();
}
}
```
### 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);
}
```
### 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** to do context switch.
* set the nextThread to status of running.
* call **CheckToBeDestroyed()** to delete oldThread if the thread had finished its job.
```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();
}
}
```
## 1-3. Running→Waiting (Note: only need to consider console output as an example)
### SynchConsoleOutput::PutChar(char)
*
```cpp=
void
SynchConsoleOutput::PutChar(char ch)
{
lock->Acquire();
consoleOutput->PutChar(ch);
waitFor->P();
lock->Release();
}
```
### Semaphore::P()
* If semaphore is available,kernel will consumes its value
*
```cpp=
void
Semaphore::P()
{
DEBUG(dbgTraCode, "In Semaphore::P(), " << kernel->stats->totalTicks);
Interrupt *interrupt = kernel->interrupt;
Thread *currentThread = kernel->currentThread;
// disable interrupts
IntStatus oldLevel = interrupt->SetLevel(IntOff);
while (value == 0) { // semaphore not available
queue->Append(currentThread); // so go to sleep
currentThread->Sleep(FALSE);
}
value--; // semaphore available, consume its value
// re-enable interrupts
(void) interrupt->SetLevel(oldLevel);
}
```
### Append(T)
* insert item to the end of list
```cpp=
template <class T>
void List<T>::Append(T item)
{
ListElement<T> *element = new ListElement<T>(item);
ASSERT(!IsInList(item));
if (IsEmpty())
{ // list is empty
first = element;
last = element;
}
else
{ // else put it after last
last->next = element;
last = element;
}
numInList++;
ASSERT(IsInList(item));
}
```
### Thread::Sleep(bool)
* When entering this function ,interrupt should be disable,we use ASSERT to check that.
* set thread status to **BLOCKED**
* If the scheduler find out that the ready queue is empty,it will let machine idle.
* Otherwise ,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::FindNextToRun()
omitted。
### 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();
}
}
```
## 1-4. Waiting→Ready (Note: only need to consider console output as an example)
### Semaphore::V()
* increase the value of semaphore。
* if waiting queue of semaphore is not empty,call **ReadyToRun** to execute first element in the queue and remove it from the queue.
```cpp=
void
Semaphore::V()
{
DEBUG(dbgTraCode, "In Semaphore::V(), " << kernel->stats->totalTicks);
Interrupt *interrupt = kernel->interrupt;
// disable interrupts
IntStatus oldLevel = interrupt->SetLevel(IntOff);
if (!queue->IsEmpty()) { // make thread ready.
kernel->scheduler->ReadyToRun(queue->RemoveFront());
}
value++;
// re-enable interrupts
(void) interrupt->SetLevel(oldLevel);
}
```
## Scheduler::ReadyToRun(Thread*)
omitted.
## 1-5. Running→Terminated (Note: start from the Exit system call is called)
* call thread->Finish()
### SC_Exit:
```cpp=
case SC_Exit:
DEBUG(dbgAddr, "Program exit\n");
val = kernel->machine->ReadRegister(4);
cout << "return value:" << val << endl;
kernel->currentThread->Finish();
break;
```
### 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(bool)
as above mentioned.
### Scheduler::FindNextToRun()
as above mentioned.
### Scheduler::Run()
as above mentioned.
## 1-6. Ready→Running
### Scheduler::FindNextToRun()
as above mentioned.
### SWITCH(Thread*, Thread*)
*
## 附錄
### stats.h
```cpp=
// stats.h
// Data structures for gathering statistics about Nachos performance.
//
// DO NOT CHANGE -- these stats are maintained by the machine emulation
//
//
// Copyright (c) 1992-1993 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 STATS_H
#define STATS_H
#include "copyright.h"
// The following class defines the statistics that are to be kept
// about Nachos behavior -- how much time (ticks) elapsed, how
// many user instructions executed, etc.
//
// The fields in this class are public to make it easier to update.
class Statistics {
public:
int totalTicks; // Total time running Nachos
int idleTicks; // Time spent idle (no threads to run)
int systemTicks; // Time spent executing system code
int userTicks; // Time spent executing user code
// (this is also equal to # of
// user instructions executed)
int numDiskReads; // number of disk read requests
int numDiskWrites; // number of disk write requests
int numConsoleCharsRead; // number of characters read from the keyboard
int numConsoleCharsWritten; // number of characters written to the display
int numPageFaults; // number of virtual memory page faults
int numPacketsSent; // number of packets sent over the network
int numPacketsRecvd; // number of packets received over the network
Statistics(); // initialize everything to zero
void Print(); // print collected statistics
};
// Constants used to reflect the relative time an operation would
// take in a real system. A "tick" is a just a unit of time -- if you
// like, a microsecond.
//
// Since Nachos kernel code is directly executed, and the time spent
// in the kernel measured by the number of calls to enable interrupts,
// these time constants are none too exact.
const int UserTick = 1; // advance for each user-level instruction
const int SystemTick = 10; // advance each time interrupts are enabled
const int RotationTime = 500; // time disk takes to rotate one sector
const int SeekTime = 500; // time disk takes to seek past one track
const int ConsoleTime = 100; // time to read or write one character
const int NetworkTime = 100; // time to send or receive one packet
const int TimerTicks = 100; // (average) time between timer interrupts
#endif // STATS_H
```
Sign in with Wallet
Connect another wallet