Nachos用线程模拟操作系统的进程，因此本文中的进程与线程在Nachos意思一致
关键函数
进程状态相关
Fork()函数创建新进程，它将一个函数作为参数传入，然后为其分配栈空间。调用scheduler->ReadyToRun(this)将该进程放入就绪态队列。
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);
}ReadyToRun()函数将进程状态设为就绪态，然后使用Append()函数将其放入就绪态队列。
void Scheduler::ReadyToRun(Thread *thread)
{
ASSERT(kernel->interrupt->getLevel() == IntOff);
DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName());
thread->setStatus(READY);
readyList->Append(thread);
}Sleep()函数用于阻塞当前进程并从就绪态队列中寻找可以运行的进程。找到之后调用Run()函数，参数bool finishing是表示当前进程是否结束的标识符，关于Run()函数在后文会讲到。
void Thread::Sleep(bool finishing)
{
Thread *nextThread;
ASSERT(this == kernel->currentThread);
ASSERT(kernel->interrupt->getLevel() == IntOff);
DEBUG(dbgThread, "Sleeping thread: " << name);
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);
}Finish()表示进程执行完毕，调用Sleep()，并传入参数为TRUE，前面我们提到了，Sleep(TRUE)这一段就是销毁当前进程的内存空间并将CPU交给就绪态队列中的某一个进程。
void Thread::Finish()
{
(void)kernel->interrupt->SetLevel(IntOff);
ASSERT(this == kernel->currentThread);
DEBUG(dbgThread, "Finishing thread: " << name);
Sleep(TRUE); // invokes SWITCH
// not reached
}进程调度相关
Yield()函数实现进程的切换。kernel->scheduler->FindNextToRun()寻找接下来需要运行的进程，然后将当前进程放入就绪态队列，之后运行新的进程。
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);
}Run()函数接受两个参数，第一个是要运行的进程，第二个是当前的进程是否执行完毕。下面函数首先获取当前运行的进程为oldThread，当finishing参数为TRUE时，将该进程销毁，否则保存当前进程的运行状态放入就绪态队列等待下次运行。最后再将当前运行的进程由oldThread切换为nextThread，并将其状态设置为运行态。
void Scheduler::Run(Thread *nextThread, bool finishing)
{
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();
}
}FindNextToRun()函数返回CPU将要运行的下一个进程。readyList->RemoveFront()返回就绪态队列的最前面的进程。
Thread *
Scheduler::FindNextToRun()
{
ASSERT(kernel->interrupt->getLevel() == IntOff);
if (readyList->IsEmpty())
{
return NULL;
}
else
{
return readyList->RemoveFront();
}
}RemoveFront()函数如下，取出当前链表的第一个元素，然后移动头指针并释放该元素内存。
template <class T>
T List<T>::RemoveFront()
{
ListElement<T> *element = first;
T thing;
ASSERT(!IsEmpty());
thing = first->item;
if (first == last)
{ // list had one item, now has none
first = NULL;
last = NULL;
}
else
{
first = element->next;
}
numInList--;
delete element;
return thing;
}通过这两个函数我们就能明白，Nachos的进程调度是FCFS（先到先得）的算法。
增加进程属性以及修改最大进程数量
给线程类增加两个成员，usrID与ThreadID，用于记录线程所属用户进程和线程自身ID。
在Thread.h文件中的private内声明新的私有属性usrid、threadid、flag、priority。分别表示用户进程id、线程自身的id、创建是否成功以及进程的优先级。
private:
// some of the private data for this class is listed above
int *stack; // Bottom of the stack
// NULL if this is the main thread
// (If NULL, don't deallocate stack)
ThreadStatus status; // ready, running or blocked
char *name;
// 用户进程id
int usrid;
// 线程id
int threadid;
// 标识符，标识是否创建成功
int flag;
// 优先级
int priority;然后在`public`中声明公有方法`getUid()`和`getTid()`等，用户获取usrid和threadid等私有属性。
代码语言：javascript复制public:
/*略*/
// 返回用户进程id
int getUid();
// 返回线程id
int getTid();
// 是否创建成功
int getFlag();
// 获取优先级
int getPriority();然后在Thread.cc当中全局定义如下内容，定义一个数组用于分配线程id号。
代码语言：javascript复制// 最大线程数量
static int MAX = 128;
// 获取用户进程id
#include "unistd.h"
// 线程id
int TidSet[128] = {0};
// 用于记录线程id分配情况
int cnt = 0;并修改Thread的构造函数，用于限制最大进程数量、获取用户进程id和分配线程id。使用随机数和取模计算，为每个线程随机分配优先级。
如果线程数量超过了MAX限制的数量，则标识符flag为0，表示创建失败。
代码语言：javascript复制Thread::Thread(char *threadName)
{
// 如果创建线程后数量大于最大线程数量
if ( NumofThread > MAX)
{
NumofThread--;
// 标识符为0，表示创建失败
flag = 0;
return;
}
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
// 用户进程id
usrid = getuid();
// 寻找可用的线程id
for (; cnt < MAX; cnt )
{
if (TidSet[cnt] == 0)
{
// 标识符为1，表示创建成功
flag = 1;
TidSet[cnt] = 1;
threadid = cnt;
// 优先级
priority = rand() % 128;
// cout << "create thread " << threadName << " successfully, the id is " << threadid << " the priority is " << priority << "n";
break;
}
}
for (int i = 0; i < MachineStateSize; i )
{
machineState[i] = NULL; // not strictly necessary, since
// new thread ignores contents
// of machine registers
}
space = NULL;
}实现在Thread.h中声明几个获取私有属性的函数
代码语言：javascript复制// 获取用户进程id
int Thread::getUid()
{
return usrid;
}
// 获取线程id
int Thread::getTid()
{
return threadid;
}
// 获取flag标识
int Thread::getFlag()
{
return flag;
}
// 获取优先级
int Thread::getPriority()
{
return priority;
}Thread.cc中为我们提供了一个简单的函数SimpleThread()便于我们测试进程，接下来修改SelfTest()函数，让其创建200个SimpleThread()函数的新进程。如下所示，t->getFlag()返回进程创建是否成功，如果成功调用Fork()函数复制一个SimpleThread()函数的进程。然后调用Yield()函数，表明主函数将CPU资源让出进入就绪态，从就绪态队列中取出一个进程执行。
void Thread::SelfTest()
{
DEBUG(dbgThread, "Entering Thread::SelfTest");
for (size_t i = 0; i < 130; i )
{
Thread *t = new Thread("forked thread");
if (t->getFlag())
{
t->Fork((VoidFunctionPtr)SimpleThread, (void *)i);
}
else
{
cout << "create thread fail!!!n";
}
}
kernel->currentThread->Yield();
}为了更直观的验证实现的效果，修改一下SimpleThread()函数，如下所示。每个进程loop5次，每loop一次就将CPU资源让出。
代码语言：javascript复制static void
SimpleThread(int which)
{
int num;
for (num = 0; num < 5; num )
{
cout << "*** thread " << which
<< "t looped " << num << "t times "
<< "tpri t" << kernel->currentThread->getPriority()
<< "tuid t" << kernel->currentThread->getUid()
<< "ttid t" << kernel->currentThread->getTid() << "n";
kernel->currentThread->Yield();
}
}重新编译，并运行下面的命令
代码语言：javascript复制./nachos -K > res部分运行截图如下所示，统计一下loop的次数，发现总共loop了630次，因此我们一共创建了126个SimpleThread()进程。我们的进程的数量限制是128个，这里应该是640个才对啊，为什么是630呢。其实是因为这128个进程还包括了一个main进程和postal worker（用于网络）进程，因此可知实现了对线程数量的限制。
将调度算法由FCFS改为基于优先级
我在这里提供两种解决方案，一种是修改将进程塞入就绪态队列的方式，另一种是修改从就绪态队列取出进程的方式。第一种方法没问题，第二种方式思路正确但是有bug。
修改将进程塞入就绪态队列的方式
要明白进程是怎么调度的，我们需要再深入分析一下Yield函数。关于FindNextToRun()函数我们前面已经讲过了，修改这里也就是修改从就绪态队列取出进程的方式，这个方法我们之后在讲。我们看看ReadyToRun()函数是如何将进程塞进就绪态队列的。
代码语言：javascript复制void Thread::Yield()
{
Thread *nextThread;
IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
ASSERT(this == kernel->currentThread);
DEBUG(dbgThread, "Yielding thread: " << name);
// FindNextToRun()寻找下一个运行的线程，如果有则返回，没有则返回null
nextThread = kernel->scheduler->FindNextToRun();
// 当返回值非空
if (nextThread != NULL)
{
// 将该线程放在就绪态
kernel->scheduler->ReadyToRun(this);
// 启动更改找到的进程
kernel->scheduler->Run(nextThread, FALSE);
}
(void)kernel->interrupt->SetLevel(oldLevel);
}下面是ReadyToRun()函数，代码非常清晰，用Append()函数直接将将thread塞进就绪态队列。
代码语言：javascript复制void Scheduler::ReadyToRun(Thread *thread)
{
ASSERT(kernel->interrupt->getLevel() == IntOff);
DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName());
thread->setStatus(READY);
readyList->Append(thread);
}Append()这个方法再list.cc当中，直接将一个元素塞进链表尾部，然后我们前面讲了从中取出进程是从头部取，所以这两个放、取函数共同实现了FCFS的进程调度算法。
知道了这些，我们修改的思路就非常明确了，修改其中的一个函数来实现基于优先级的调度算法。我们通过在把进程塞入就绪态队列时就根据优先级确定插入的位置，实现从大到小的排序。
在list.h中定义下面的函数
代码语言：javascript复制void Insert(T item, int priority);然后在list.cc中实现一个简单的按照优先级大小的插入排序算法，如下
代码语言：javascript复制template <class T>
void List<T>::Insert(T item, int priority) // 将一个线程的指针和优先级作为参数
{
ListElement<T> *element = new ListElement<T>(item);
ASSERT(!IsInList(item));
if (IsEmpty())
{
first = element;
last = element;
}
else
{
ListElement<T> *cur = first;
ListElement<T> *precur = NULL;
while (cur != NULL)
{
if (priority > cur->item->getPriority())
{
element->next = cur;
if (precur == NULL)
first = element;
else
precur->next = element;
numInList ;
break;
}
precur = cur;
cur = cur->next;
}
if (precur == last)
{
Append(item);
}
}
}修改scheduler.cc中的ReadyToRun()函数，将放入的方式由Append改为Insert，修改后的函数如下
代码语言：javascript复制void Scheduler::ReadyToRun(Thread *thread)
{
ASSERT(kernel->interrupt->getLevel() == IntOff);
DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName());
thread->setStatus(READY);
if (readyList->IsEmpty())
{
readyList->Append(thread);
return;
}
readyList->Insert(thread, thread->getPriority());
}为了便于测试，我们将将创建的进程数量减少一些，减到四五个左右，然后修改优先级生成部分的模运算改为模5。我自己为了方便验证每次进程切换之前都遍历了就绪态队列中所有进程的优先级。最后重新编译运行，结果如下。能够明确看到就绪态队列中的进程时按照优先级从大到小排列的，调度也是按照优先级调度的。
通过修改从就绪队列取出的方式
此方法有bug，欢迎指正
前面我们提到了FindNextToRun()函数实现了FCFS的进程调度算法，所以要将调度算法由FCFS改为基于优先级，就需要从这里入手。
这里使用RemoveFront()函数取出就绪队列中的第一个元素作为即将运行的进程。我们新定义一个RemoveHighestPriority()函数将就绪队列中优先级最高的进程取出。在list.h中声明该函数。和之前一样的步骤，就不再赘述了。
然后再list.cc中实现该函数，如下所示。这段代码遍历就绪态队列，取出其中优先级最高的进程（优先级相同则遵循FCFS），然后更新链表并将优先级最高的进程返回。
代码语言：javascript复制template <class T>
T List<T>::RemoveHighestPriority()
{
ASSERT(!IsEmpty());
// 记录前一元素
ListElement<T> *pre = first;
// 用于遍历
ListElement<T> *cur = first->next;
// 记录最高优先级节点
ListElement<T> *maxNode = first;
// 遍历链表
while (cur != NULL)
{
if (cur->item->getPriority() > maxNode->item->getPriority())
{
maxNode = cur;
pre = cur;
}
cur = cur->next;
}
// 如果最高优先级为第一个节点
if (maxNode == first)
{
first = first->next;
}
else
{
pre->next = maxNode->next;
}
// 取出最高优先级节点
T thing = maxNode->item;
delete maxNode;
return thing;
}最后将FindNextToRun()函数中的RemoveFront()改为RemoveHighestPriority()，然后编译运行。
这段代码有bug，我找不出来，不过思路没问题，从就绪态进程队列中取出优先级最高的进程。欢迎指正。
