// 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.

// Modified 9/19/2005 by Jacob Lee and Soumi Sinha for CS423ug MP1.

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

void SchedInterruptHandler(int);

//----------------------------------------------------------------------
// 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;
    if (ptimer != NULL)
      delete ptimer;
} 

//----------------------------------------------------------------------
// 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);
    // For waiting metric calculation
    //thread->startWait = stats->GetElapsedTicks();

    // TODO MP1
    // Correctly maintain ready list.

    switch( policy ) {
    case SCHED_PRIO_RR:
    case SCHED_PRIO_P:
      // Negate the priority to cause higher-priority processes
      // to be placed at the front of the list
      readyList->SortedInsert(thread, -thread->getPriority());
      break;
    case SCHED_FCFS:
    case SCHED_RR:
      readyList->Append(thread);
      break;
    }
}

//----------------------------------------------------------------------
// Scheduler::FindNextToRun
//----------------------------------------------------------------------

Thread *
Scheduler::FindNextToRun ()
{
  Thread *t;
  // TODO MP1
  // Choose the best thread to run next.
  DEBUG('t', "FindNextToRun, time left = %d\n", currentThread->getTimeLeft());
  switch( policy ) {
    case SCHED_PRIO_RR:
    case SCHED_PRIO_P:
      t = readyList->SortedRemove(NULL);
      //DEBUG('t', "FindNextToRun chose %s\n", t->getName());
      //return t;
      break;
    case SCHED_FCFS:
    case SCHED_RR:
      t = readyList->Remove();
      break;
  }
  
  /* Calculate thread wait time
  if (t)
    t->totalWaiting = stats->GetElapsedTicks() - t->startWait; */
  return t;
}


//----------------------------------------------------------------------
// 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;

  // TODO MP1
  // Return the correct answer based on the algorithm.

  switch( policy ) {
  case SCHED_PRIO_P:
    // Switch immediately to forked thread if it is of higher priority
    if (oldThread->getPriority() < newThread->getPriority())
      answer = true;
    else
      answer = false;
    break;
  case SCHED_PRIO_RR:
  case SCHED_FCFS:
  case SCHED_RR:
    answer = false;
    break;
  }

  DEBUG('t', "ShouldISwitch from %s to %s: %s \n",
	oldThread->getName(), newThread->getName(), (answer? "yes" : "no"));
  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

    // TODO MP1
    // Put any processing before the SWITCH statement.

    // Request an interrupt only if the next thread will not finish
    // its work during this quantum.
    if ((policy == SCHED_RR || policy == SCHED_PRIO_RR)
	&& (currentThread->getTimeLeft() >= 4)) {
      DEBUG('t', "Requesting interrupt\n");
      if (ptimer != NULL)
	delete ptimer;
      // N.B. ptimer is now a OneShot*, not a Timer*
      ptimer = new OneShot(SchedInterruptHandler, 0, TimerTicks);
    }
    
    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".
    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
}

//---------------------------------------------------------------------
// NEW
// 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()
{
    readyList->Mapcar((VoidFunctionPtr) ThreadPrint);
}

//----------------------------------------------------------------------
// Scheduler::InterruptHandler
//   Handles timer interrupts for Round-robin scheduling.  Since this 
//   is called while the system is an interrupt handler, use YieldOnReturn.
//   Be sure that your scheduling policy is still Round Robin.
//----------------------------------------------------------------------
void
Scheduler::InterruptHandler( int dummy )
{
  //TODO MP1
  DEBUG('t', "InterruptHandler");
  DEBUG('t', "InterruptHandler, currentThread=%s, timeLeft=%d,",
	currentThread->getName(), currentThread->getTimeLeft(), dummy);
  //DEBUG('t', "elapsed ticks = ");

  // Don't switch out the main thread.
  if (strcmp(currentThread->getName(), "main") != 0) {
    switch(policy) {
    case SCHED_RR:
      // Only yield if there is another process to yield to
      if (readyList->SortedPeek(NULL))
	interrupt->YieldOnReturn();
      break;
    case SCHED_PRIO_RR:
      // Only yield if there is another process to yield to, and that process
      // is not of lower priority than us.
      Thread *next = readyList->SortedPeek(NULL);
      if (next && next->getPriority() >= currentThread->getPriority())
	interrupt->YieldOnReturn();
      break;
    }
  }
}

// Needed because of how C++ handled member functions.
void SchedInterruptHandler( int dummy )
{
  scheduler->InterruptHandler( dummy );
}


//----------------------------------------------------------------------
// Scheduler::SetSchedPolicy
//      Set the scheduling policy to one of SCHED_FCFS, SCHED_RR,
//      SCHED_PRIO_P, or SCHED_PRIO_RR
//----------------------------------------------------------------------
void 
Scheduler::SetSchedPolicy(SchedPolicy pol)
{
    SchedPolicy oldPolicy = policy;
    policy = pol;
    if( oldPolicy == policy ) 
        return;  // No change!

    switch (policy)
    {
    case SCHED_PRIO_RR:
      printf("Priority round robin scheduling\n");
      break;

    case SCHED_PRIO_P:
      printf("Preemptive Priority scheduling\n");
      break;

    case SCHED_RR:
      printf("Round robin scheduling\n");
      break;

    case SCHED_FCFS:
    default:
      printf("First-come first-served scheduling\n");
      break;
    }
}

SchedPolicy Scheduler::getPolicy() {
  return policy;
}