/****************************************************************************/
/*                                                                          */
/* 			     Module CPU                                                     */
/* 			External Declarations 				                                      */
/*                                                                          */
/****************************************************************************/

#define NULL (void*)0

/* OSP constant      */

#define   MAX_PAGE                   16 /* max size of page tables          */

/* OSP enumeration constants */

typedef enum {
    false, true                         /* the boolean data type            */
} BOOL;

typedef enum {
    running, ready, waiting, done       /* types of status                  */
} STATUS;



/* external type definitions */

typedef struct page_entry_node PAGE_ENTRY;
typedef struct page_tbl_node PAGE_TBL;
typedef struct event_node EVENT;
typedef struct pcb_node PCB;



/* external data structures */

struct page_entry_node {
    int    frame_id;    /* frame id holding this page                       */
    BOOL   valid;       /* page in main memory : valid = true; not : false  */
    int    *hook;       /* can hook up anything here                        */
};

struct page_tbl_node {
    PCB    *pcb;        /* PCB of the process in question                   */
    PAGE_ENTRY page_entry[MAX_PAGE];
    int    *hook;       /* can hook up anything here                        */
};

struct pcb_node {
    int    pcb_id;         /* PCB id                                        */
    int    size;           /* process size in bytes; assigned by SIMCORE    */
    int    creation_time;  /* assigned by SIMCORE                           */
    int    last_dispatch;  /* last time the process was dispatched          */
    int    last_cpuburst;  /* length of the previous cpu burst              */
    int    accumulated_cpu;/* accumulated CPU time                          */
    PAGE_TBL *page_tbl;    /* page table associated with the PCB            */
    STATUS status;         /* status of process                             */
    EVENT  *event;         /* event upon which process may be suspended     */
    int    priority;       /* user-defined priority; used for scheduling    */
    PCB    *next;          /* next pcb in whatever queue                    */
    PCB    *prev;          /* previous pcb in whatever queue                */
    int    *hook;          /* can hook up anything here                     */
};


/* external variables */

extern PAGE_TBL *PTBR;		/* page table base register */

extern int    Quantum;		/* global time quantum; contains the value
				   entered at the beginning or changed 
				   at snapshot. Has no effect on timer
				   interrupts, unless passed to set_timer() */



/* external routines */

extern prepage(/* pcb */);
extern int start_cost(/* pcb */);
/*  PCB    *pcb; */    

extern set_timer(/* time_quantum */);
/*  int    time_quantum; */

extern int get_clock();





/****************************************************************************/
/*                                                                          */
/*           Module CPU                                                     */
/*           Internal Routines                                              */
/*                                                                          */
/****************************************************************************/


/* Global variables for internal use */
PCB *high_head, *high_tail, *low_head, *low_tail;
int next_low_check;
float acceptable_fraction = 0.9, acceptable_ratio = 0.25;


/* Function declarations */
void cpu_init();
void dispatch();
void insert_ready(PCB *pcb);
void check_low_queue();
int high_priority(PCB *pcb);
void add_high(PCB *pcb);
void add_low(PCB *pcb);
void rm_high(PCB *pcb);
void rm_low(PCB *pcb);
void reset_low_check();
PCB *next_process();

void cpu_init()
{
  high_head = high_tail = low_head = low_tail = NULL;
  reset_low_check();
}

void dispatch()
{
  PCB *pcb;

  if(PTBR && (PTBR->pcb->status == running))
    insert_ready(PTBR->pcb);

  pcb = next_process();
  if(pcb)
  {
    PTBR = pcb->page_tbl;
    prepage(pcb);
    pcb->status = running;
    pcb->last_dispatch = get_clock();
    set_timer(Quantum);
  } else {
    PTBR = NULL;
  }
}

void insert_ready(PCB *pcb)
{
  if(get_clock() > next_low_check)
  {
    check_low_queue();
    reset_low_check();
  }
  pcb->status = ready;
  if(pcb->accumulated_cpu == 0)
  {
    add_high(pcb);
  } else {
    if(high_priority(pcb))
    {
      add_high(pcb);
    } else {
      add_low(pcb);
    }
  }
}

void check_low_queue()
{
  /* Go thru the low-priority queue and promote as needed */
  PCB *cur=low_head;
  while(cur)
    if(high_priority(cur))
    {
      rm_low(cur);
      add_high(cur);
    }
}

int high_priority(PCB *pcb)
{
  if(( (float)pcb->last_cpuburst / (float)Quantum ) > acceptable_fraction)
    return 0;
  
  if(( (float)pcb->accumulated_cpu / (float)(get_clock() - pcb->creation_time) ) < acceptable_ratio)
    return 1;

  return 0;
}

void add_high(PCB *pcb)
{
  if(high_tail)
  {
    high_tail->next = pcb;
    pcb->prev = high_tail;
    high_tail = pcb;
  } else {
    high_head = high_tail = pcb;
    pcb->prev = pcb->next = NULL;
  }
}

void add_low(PCB *pcb)
{
  if(low_tail)
  {
    low_tail->next = pcb;
    pcb->prev = low_tail;
    low_tail = pcb;
  } else {
    low_head = low_tail = pcb;
    pcb->prev = pcb->next = NULL;
  }
}

void rm_high(PCB *pcb)
{
  if(high_head == pcb)
    high_head = pcb->next;

  if(high_tail == pcb)
    high_tail = pcb->prev;

  pcb->prev = pcb->next = NULL;
}

void rm_low(PCB *pcb)
{
  if(low_head == pcb)
    low_head = pcb->next;

  if(low_tail == pcb)
    low_tail = pcb->prev;

  pcb->prev = pcb->next = NULL;
}

void reset_low_check()
{
  next_low_check = get_clock() + (10 * Quantum); /* Check again in 10 Quantums */
}

PCB *next_process()
{
  PCB *pcb;
  if(pcb = high_head)
  {
    rm_high(pcb);
  } else if(pcb = low_head) {
    rm_low(pcb);
  }
  return pcb;
}

/* end of module */