基于当时刚刚接触NACHOS时无从下手的窘迫，现在贴出一份自己的实验报告，跟大家交流下
操作系统实验3
关于调度算法的实现
我们实现的是Shortest Job First ,Shortest Remaining Next & Priority,Round-Robin 和Multiple Queues这5个调度的算法。
经过我一个多星期对文档的阅读和与同学的讨论，初步弄明白了Nachos的线程调度的基本的概念和流程。
本次的实验，Nachos用了一个叫List的模板类来维护进程的链表以及其他的链表，所有的链表操作都可以通过里面定义的函数来操作，里面有很关键的SortedInsert函数，确保可以按照一定的顺序来插入数据。另外通过对线程类型的阅读，也发现了里面有timeLeft,priority等的私有成员，可以记录剩余时间和优先级。对于其他的成员函数就不是十分熟悉他们的整个执行的流程了。
对于进程的调度，是由一个叫做scheduler的类来控制整个线程的调度，包括执行队列，线程间切换，线程的运行，处理机的时间分块运行。本次实验通过对两个函数， ReadyToRun()和ShouldISwitch()来实现我们的调度策略。
Void Scheduler::ReadyToRun (Thread *thread)
{
DEBUG('t', "Putting thread %s on ready list./n", thread->getName());
thread->setStatus(READY);
switch (policy)
{
case SCHED_PRIO:
readyList->SortedInsert(thread,20-thread->getPriority());break; // Priority
case SCHED_MQ:
readyList->SortedInsert(thread,20-thread->getPriority());break;
// Multiple Queues
case SCHED_SJF:
readyList->SortedInsert(thread,thread->getTimeLeft());
break;// Shortest Job First
case SCHED_SRTN:
readyList->SortedInsert(thread,thread->getTimeLeft());
break; // Shortest Remaining Time Next
case SCHED_FCFS:
readyList->Append(thread);
break;// First Come First Served (FCFS) scheduling
// FCFS is the NachOS default
case SCHED_RR:
readyList->Append(thread);
break;// Round Robin scheduling
default:
readyList->Append(thread);
break;
}
}
bool Scheduler::ShouldISwitch (Thread * oldThread, Thread * newThread)
{
bool answer;
switch( policy )
{
case SCHED_FCFS: break; // First-come first-served scheduling
case SCHED_MQ:
if((oldThread->getPriority())>=(newThread->getPriority()))
answer = false;
else
answer = true;
break; // Multiple Queues
case SCHED_SJF: break;// Shortest Job First
case SCHED_RR:
break;
// Round Robin scheduling
case SCHED_PRIO:
if((oldThread->getPriority())>=(newThread->getPriority()))
answer = false;
else
answer = true;
break;// Priority scheduling
case SCHED_SRTN:
if((oldThread->getTimeLeft())>=(newThread->getTimeLeft()))
answer = true;
else
answer = false;break;// Shortest Remaining Time Next
default:
answer = false;
break;
}
return answer;
}
Void Scheduler::Run (Thread *nextThread)
{
．．．．．．
if(policy==SCHED_RR&¤tThread->getTimeLeft()>=3&&!readyList->IsEmpty())
interrupt->Schedule(SchedInterruptHandler, (int) this, 40, TimerInt);
if(!readyList->IsEmpty()&&(4*(currentThread->getNumOfExec()+1)-1)<(currentThread->getTimeLeft())&&policy==SCHED_MQ)
interrupt->Schedule(SchedInterruptHandler, (int) this,currentThread->NumOfExec()*40,TimerInt);
SWITCH(oldThread, nextThread);
．．．．．．．
Void Scheduler::InterruptHandler( int dummy )
{
if (strcmp(currentThread->getName(), "main"))
{
if(policy==SCHED_MQ)
currentThread->setPriority(currentThread->getPriority()-1);
if (interrupt->getStatus() != IdleMode)
interrupt->YieldOnReturn();
}
}
加红色标记的是我最近修改的代码。
对Shortest Job First策略的实现是：
在void Scheduler::ReadyToRun (Thread *thread)函数里面的case语句里面添加了
case SCHED_SJF:
readyList->SortedInsert(thread,thread->getTimeLeft());
break;
因为在这个策略里面不涉及抢占的要求，只是简单的将readyList中的项目按照顺序执行完，但是只是在当前进程执行完后才会去执行当前的就绪进程列表中的执行时间最短的那个，因此我们称其为不抢占式的最短时间作业。
对Shortest Remaining Next策略的实现是：
在void Scheduler::ReadyToRun (Thread *thread)函数里面的case语句里面添加了
case SCHED_SRTN:
readyList->SortedInsert(thread,thread->getTimeLeft());break;
以及在bool Scheduler::ShouldISwitch (Thread * oldThread, Thread * newThread)中添加了
case SCHED_SRTN:
if((oldThread->getTimeLeft())>=(newThread->getTimeLeft()))
answer = true;
else
answer = false;break;
因为这个策略涉及到抢占，另外还涉及到进程切换，所以必须添加进程切换的策略。首先在就绪进程列表的添加的时候必须按照作业的长度来添加，方便进程的一个个的执行下去，，所以是按照其需要执行的时间作为一个参数添加队列。对于添加的进程是否可以抢占资源就取决于他的timeLeft和当前的进程的timeLeft，如果新进程的时间需求少就马上执行新的进程。因此对answer变量的控制就可以控制，进程的切换策略。
对于Priority策略的实现：
在void Scheduler::ReadyToRun (Thread *thread)函数里面的case语句里面添加了
case SCHED_PRIO:
readyList->SortedInsert(thread,20-thread->getPriority());break;
以及在bool Scheduler::ShouldISwitch (Thread * oldThread, Thread * newThread)中添加了
case SCHED_PRIO:
if((oldThread->getPriority())>=(newThread->getPriority()))
answer = false;
else
answer = true;
break;
这个策略的实现是通过一方面在就绪队列的插入的时候，以他的优先级作为参数插入队列，因为这个队列的顺序是升序的，对于我们的优先级策略来说是越高的优先级的应该越早被执行，因此应该排在队列的头，所以我们对插入参数做了一些变动，添加了符号，可以使我们的队列可以以降序来排列。在进程的切换的控制中采取优先级的比较，高优先级的先执行，就是将answer参数设置为真，让他们交换。
对Round-Robin的策略的实现：
在void Scheduler::ReadyToRun (Thread *thread)函数里面的case语句里面添加了
case SCHED_RR:
readyList->Append(thread);break;
以及在void Scheduler::Run (Thread *nextThread)里面
SWITCH(oldThread, nextThread);的前面加上一句
if(policy==SCHED_RR&¤tThread->getTimeLeft()>=3&&!readyList->IsEmpty())
interrupt->Schedule(SchedInterruptHandler, (int) this, 40, TimerInt);
最后在
void Scheduler::InterruptHandler( int dummy )
里面的
if (strcmp(currentThread->getName(), "main"))
里面加上一句
if (interrupt->getStatus() != IdleMode)
interrupt->YieldOnReturn();
整个策略就已经实现，这个策略是给每个进程一定的时间，让他们去执行自己的任务，当时间片耗尽的时候，如果就绪队列有线程在等待的话，就把当前的线程插到队尾，取出队列前头的线程来执行，一直轮换直到所有的任务都结束．在我们的这个实验里面，是模拟线程来实现的，另外就是在０时刻同时进入５个进程，所以模拟的其实是正式实际应用的一个情形．另外对比TIMER和ONRSHOT的实现，就是TIMER是对整个系统的执行做定时的中断，譬如如果默认开启一个定时长的TIMER的话，系统每运行一个这个时长，他就作一次中断，并插入下一次中断，然后通过中断的函数句柄来调用相关的中断函数．对于ONESHOT来说他可以让用户自己插入自己需要的时间去中断，不想TIMER那样固定时长而且只是关注系统执行而不是线程的执行．究其本质就是调用了一句函数
Void Interrupt::Schedule(VoidFunctionPtr handler, int arg, int fromNow, IntType type)
因为整个系统只是维护一个中断列表，所有的中断的调度都是通过这个函数，然后去产生一个中断表项，就是
PendingInterrupt *toOccur = new PendingInterrupt(handler, arg, when, type);
pending->SortedInsert(toOccur, when);
这个就是整个中断的实质，通过对handle和fromNow的控制就可以控制中断时调用的有关函数，和想插入的系统中断的时间．另外在我们的实验的时间片的定义，并非象发饼干一样的将时间片授发给每个线程而是告诉线程，你在什么时刻会遇到中断，提前预测了时间．
我们的整个系统的中断是通过调用中断的Void Interrupt::YieldOnReturn()函数将中断的yieldOnReturn变量设置为真值，就象一个中断的开关，通过跟踪这个开关变量发现是在void
Interrupt::OneTick()中有相关的代码，通过调用当前的线程的currentThread->Yield()成员函数来实现上下文的切换，以及有关线程的切换，
if (nextThread) {
scheduler->ReadyToRun(this);
scheduler->Run(nextThread);
}
所以我们选择在Run函数里面增加有关的代码，来插入和控制我们的中断．
同时我们发现有一个问题，如果我们控制三个TICKS就４０个系统时间，那么对于不足三个TICKS的线程，我们是不是每少了一个TICK的时候，就少去１０个系统时间呢？这样做我们测试的结果就是会导致中断列表的混乱，因为当一个进程做完了之后，系统会自动的调入下一个就绪列表中的进程，不需要产生中断，而调入的线程本身也会产生中断，因此可能就会导致连续几个TICKS都产生中断，而进程一调入就中断，所以导致了整个系统的混乱．因此我们认为，只有当前的线程的剩余时间比我的时间片大的时候我才需要插入时间片让他中断，否则就让他自己运行然后通过系统自动跳转进程，那个时候才考虑加入时间片，就可以解决了所有的问题．另外对于当前的就绪列表为空的时候不发生中断，因为中断会浪费１个TICKS从而也让CPU空闲了．因此我们的控制条件是
if(policy==SCHED_RR&¤tThread->getTimeLeft()>=3&&!readyList->IsEmpty())
对于Multiple Queues调度的实现：
先在Thread.h里面增加一个私有成员numOfExec来记录当前的线程已经被执行了多少次了，还有相关的int NumOfExec()实现调用自增当前运行的次数，并返回自增后的值， int getNumOfExec()可以返回当前的这个记录的值．方便多级的使用．
在void Scheduler::ReadyToRun (Thread *thread)函数里面的case语句里面添加了
case SCHED_MQ:
readyList->SortedInsert(thread,20-thread->getPriority());break;
以及在bool Scheduler::ShouldISwitch (Thread * oldThread, Thread * newThread)里面加上一句
case SCHED_MQ:
if((oldThread->getPriority())>=(newThread->getPriority()))
answer = false;
else
answer = true;
break;
然后在
void Scheduler::Run (Thread *nextThread)中
在SWITCH(oldThread, nextThread);之前加上
if(!readyList->IsEmpty()&&(4*(currentThread->getNumOfExec()+1)-1)<(currentThread->getTimeLeft())&&policy==SCHED_MQ)
interrupt->Schedule(SchedInterruptHandler, (int) this,currentThread->NumOfExec()*40,TimerInt);
void Scheduler::InterruptHandler( int dummy )
里面的
if (strcmp(currentThread->getName(), "main"))
里面加上一句
if(policy==SCHED_MQ)
currentThread->setPriority(currentThread->getPriority()-1);
就可以实现整个策略了．
虽然这些代码的结果和给出的对比结果有出入，但是已经是满足了本策略的要求，需要划分时间片，一次比一次多，时间片翻倍的给予，另外优先级降低，并插入相关的就绪队列中去，在发生中断的时候在中断函数里面已经完成．
