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

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;
    ostimer = NULL;
} 

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

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

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

    // TODO MP1
    // Correctly maintain ready list.

    switch( policy ) {
    case SCHED_PRIO_RR: // -priority puts threads in correct order
    case SCHED_PRIO_P:
      readyList->SortedInsert(thread, -thread->getPriority());
      break;
    case SCHED_FCFS: // no priority for these algorithms
    case SCHED_RR:
      readyList->Append(thread);
      break;
    default:
      break;
    }
}

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

Thread *
Scheduler::FindNextToRun ()
{
  // TODO MP1
  // Choose the best thread to run next.
  Thread *nextThread;
  // nextThread always at head of readyList due to proper insertion order
  nextThread = readyList->Remove();

  return nextThread;
}


//----------------------------------------------------------------------
// 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: // preempt for higher priority only
    answer = oldThread->getPriority() < newThread->getPriority();
    break;
  case SCHED_PRIO_RR: // no premption
  case SCHED_FCFS:
  case SCHED_RR:
    answer = false;
    break;
  default:
    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

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

    // start oneshot for RR algorithms.
    if (policy == SCHED_RR || policy == SCHED_PRIO_RR)
       ostimer = new OneShot(SchedInterruptHandler,
                      (int) currentThread, 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
  // Don't switch out the main thread.
  if( strcmp(currentThread->getName(), "main") != 0) {
     if (dummy == (int) currentThread) { // ignore interrupts for old processes

        Thread *nextThread = readyList->Peek();
        if (nextThread) { // only yield if there is a process in the readyList
           switch (policy) {
           case SCHED_RR: // RR always yields 
              interrupt->YieldOnReturn();
              break;
           case SCHED_PRIO_RR: // yields to greater or equal priority
              if (currentThread->getPriority() <= nextThread->getPriority())
                 interrupt->YieldOnReturn();
              break;
           default:
              break;
           }
        } // end if (nextThread)
        else { // schedule next interrupt
           ostimer = new OneShot(SchedInterruptHandler,
                    (int) currentThread, TimerTicks);
        }

     }
  }
}

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