scheduler.cpp

LINUX 下的 NACHOS 系统 实现系统调度的算法功能

// scheduler.cc 
//  Routines to choose the next thread to run, and to dispatch to
//  that thread.
//
//  These routines assume that interrupts are already disabled.
//  If interrupts are disabled, we can assume mutual exclusion
//  (since we are on a uniprocessor).
//
//  NOTE: We can't use Locks to provide mutual exclusion here, since
//  if we needed to wait for a lock, and the lock was busy, we would 
//  end up calling FindNextToRun(), and that would put us in an 
//  infinite loop.
//
//  Very simple implementation -- no priorities, straight FIFO.
//  Might need to be improved in later assignments.
//
// 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.

#include "copyright.h"
#include "scheduler.h"
#include "system.h"
#include <stdio.h>

// this is a function prototype for the actual interrupt handler
void SchedInterruptHandler(int dummy);

//----------------------------------------------------------------------
// Scheduler::Scheduler
//  Initialize the list of ready but not running threads to empty.
//----------------------------------------------------------------------

Scheduler::Scheduler()
{ 
  readyList = new List<Thread *>(); 
  suspendedList = new List<Thread *>();
  ptimer = NULL;
} 

//----------------------------------------------------------------------
// Scheduler::~Scheduler
//  De-allocate the list of ready threads.
//----------------------------------------------------------------------

Scheduler::~Scheduler()
{ 
  delete readyList; 
} 

//----------------------------------------------------------------------
// Scheduler::ReadyToRun
//  Mark a thread as ready, but not running.
//  Put it on the ready list, for later scheduling onto the CPU.
//
//  "thread" is the thread to be put on the ready list.
//----------------------------------------------------------------------

void
Scheduler::ReadyToRun (Thread *thread)
{
  DEBUG('t', "Putting thread %s on ready list.\n", thread->getName());
  
  thread->setStatus(READY);
  
  // MP1 - don't forget the usefulness of the break statement
  switch (policy)
  { 
    case SCHED_PRIO:     readyList->SortedInsert(thread,thread->MAX_PRIORITY-thread->getPriority());break;// Priority
    case SCHED_MQ:    readyList->SortedInsert(thread,thread->MAX_PRIORITY-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:     // 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;
  }
}
//----------------------------------------------------------------------
// Scheduler::FindNextToRun
//----------------------------------------------------------------------

Thread *Scheduler::FindNextToRun ()
{
  // MP1
  return(readyList->Remove());
}


//----------------------------------------------------------------------
// Scheduler::ShouldISwitch
//   This function uses the policy information to tell a thread::fork
// to preempt the current thread or to not.  The answer is the domain of
// the scheduler, so it is a member function call.
//----------------------------------------------------------------------
bool Scheduler::ShouldISwitch (Thread  * oldThread, Thread * newThread)
{
  bool answer;

  // MP1 - don't forget the break statements
  switch( policy )
  {
    case SCHED_FCFS:     // First-come first-served scheduling
    case SCHED_MQ:    if((oldThread->getPriority())>=(newThread->getPriority()))answer = false;

                      else   answer = true;break;
   // Multiple Queues
   
    case SCHED_RR:    break;   // Round Robin scheduling
    case SCHED_PRIO:    if (oldThread->getPriority() < newThread->getPriority())
                           answer = true ;
     break;
                            // Priority scheduling
    case SCHED_SRTN:    if (oldThread->getTimeLeft() >newThread->getTimeLeft())
                           answer = true ;
         break;   // Shortest Remaining Time Next
 case SCHED_SJF:   answer=false;   break;// Shortest Job First
                      
    default:
  answer = false;
      break;
  }
  
  return answer;
}

//----------------------------------------------------------------------
// Scheduler::Run
//  Dispatch the CPU to nextThread.  Save the state of the old thread,
//  and load the state of the new thread, by calling the machine
//  dependent context switch routine, SWITCH.
//
//      Note: we assume the state of the previously running thread has
//      already been changed from running to blocked or ready (depending).
// Side effect:
//  The global variable currentThread becomes nextThread.
//
//  "nextThread" is the thread to be put into the CPU.
//----------------------------------------------------------------------

void
Scheduler::Run (Thread *nextThread)
{
  Thread *oldThread = currentThread;
  
#ifdef USER_PROGRAM                     // ignore until running user programs 
  if (currentThread->space != NULL) {   // if this thread is a user program,
    currentThread->SaveUserState();     // save the user's CPU registers
    currentThread->space->SaveState();
  }
#endif
  
  oldThread->CheckOverflow();      // check if the old thread
                                            // had an undetected stack overflow
  
  currentThread = nextThread;      // switch to the next thread
  currentThread->setStatus(RUNNING);        // nextThread is now running
  

  // MP1 - put any processing before the SWITCH() statement
  
  DEBUG('t', "Switching from thread \"%s\" to thread \"%s\"\n",
    oldThread->getName(), 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".
  
//RR
if(policy==SCHED_RR&&currentThread->getTimeLeft()>=3&&!readyList->IsEmpty())
interrupt->Schedule(SchedInterruptHandler, (int) this, 40, TimerInt);


  SWITCH(oldThread, nextThread);

  DEBUG('t', "Now in thread \"%s\"\n", currentThread->getName());
  
  // If the old thread gave up the processor because it was finishing,
  // we need to delete its carcass.  Note we cannot delete the thread
  // before now (for example, in Thread::Finish()), because up to this
  // point, we were still running on the old thread's stack!
  if (threadToBeDestroyed != NULL) {
    delete threadToBeDestroyed;
    threadToBeDestroyed = NULL;
  }
  
#ifdef USER_PROGRAM
  if (currentThread->space != NULL) {    // if there is an address space
    currentThread->RestoreUserState();     // to restore, do it.
    currentThread->space->RestoreState();
  }
#endif
}

//---------------------------------------------------------------------
// Suspends a thread from execution. The suspended thread is removed
// from ready list and added to suspended list. The suspended thread 
// remains there until it is resumed by some other thread. Note that
// it is not an error to suspend an thread which is already in the 
// suspended state.
//
// NOTE: This method assumes that interrupts have been turned off.
//---------------------------------------------------------------------
void Scheduler::Suspend(Thread *thread) {
  List<Thread *> *tmp = new List<Thread *>();
  Thread *t;
  
  // Remove the thread from ready list.
  while (!readyList->IsEmpty()) {
    t = readyList->Remove();
    if (t == thread)
      break;
    else
      tmp->Prepend(t);
  }
  
  // Add the suspended thread to the suspended list
  if (t == thread) {
    t->setStatus(SUSPENDED);
    suspendedList->Append(t);
  }
  
  // Now all threads before the suspended thread in the ready list
  // are in the suspended list. Add them back to the ready list.
  while (!tmp->IsEmpty()) {
    t = tmp->Remove();
    readyList->Prepend(t);
  }
}

//---------------------------------------------------------------------
// Resumes execution of a suspended thread. The thread is removed
// from suspended list and added to ready list. Note that it is not an
// error to resume a thread which has not been suspended.
//
// NOTE: This method assumes that interrupts have been turned off.
//---------------------------------------------------------------------
void Scheduler::Resume(Thread *thread) {
  List<Thread *> *tmp = new List<Thread *>();
  Thread *t;
  
  // Remove the thread from suspended list.
  while (!suspendedList->IsEmpty()) {
    t = suspendedList->Remove();
    if (t == thread)
      break;
    else
      tmp->Prepend(t);
  }
  
  // Add the resumed thread to the ready list
  if (t == thread) {
    t->setStatus(READY);
    readyList->Append(t);
  }
  
  // Now all threads before the suspended thread in the ready list
  // are in the suspended list. Add them back to the ready list.
  while (!tmp->IsEmpty()) {
    t = tmp->Remove();
    suspendedList->Prepend(t);
  }
}

//----------------------------------------------------------------------
// Scheduler::Print
//  Print the scheduler state -- in other words, the contents of
//  the ready list.  For debugging.
//----------------------------------------------------------------------
void
Scheduler::Print()
{
  printf("Ready list contents:\n");
  readyList->Mapcar((VoidFunctionPtr) ThreadPrint);
}

//----------------------------------------------------------------------
// Scheduler::InterruptHandler
//   Handles timer interrupts for the Round Robin scheduling algorithm.  
//   Since this is called while the system is an interrupt handler, 
//   use YieldOnReturn.
//----------------------------------------------------------------------

void
Scheduler::InterruptHandler( int dummy )
{
  // MP1 --

  // dont switch out the "main" task
  if (strcmp(currentThread->getName(), "main"))
  {
//RR    
if (interrupt->getStatus() != IdleMode)
       interrupt->YieldOnReturn();// MP1 - this runs if the name of the current thread is not main
    //       if there is only one thread left to run don't stop it
  }
}

// THUNK
void SchedInterruptHandler( int dummy )
{
  scheduler->InterruptHandler( dummy );
}

//----------------------------------------------------------------------
// Scheduler::SetSchedPolicy
//      Set the scheduling policy to one of SCHED_FCFS, SCHED_SJF,
//      SCHED_MQ, SCHED_PRIO, SCHED_MQ or SCHED_RR 
//----------------------------------------------------------------------
void 
Scheduler::SetSchedPolicy(SchedPolicy pol)
{
  SchedPolicy oldPolicy = policy;
  policy = pol;
  if( oldPolicy == policy ) 
    return;  // No change!
  switch (policy) {
    case SCHED_SJF:
      //printf("Shortest Job First (SJF) scheduling\n");
      break;
    case SCHED_SRTN:
      printf("Shortest Remaining Time Next (SRTN) scheduling\n");
      break;   
    case SCHED_PRIO:
      printf("Priority scheduling\n");
      break;
    case SCHED_MQ:
      printf("Multiple Queues scheduling\n");
      break;
    case SCHED_RR:
      printf("Round robin scheduling\n");
      break;
    case SCHED_FCFS:
    default:
      printf("First-Come First-Served (FCFS) scheduling\n");
      break;
  }
}