proc.c

#include "types.h"
#include "defs.h"
#include "param.h"
#include "memlayout.h"
#include "mmu.h"
#include "x86.h"
#include "proc.h"
#include "spinlock.h"

#define TICKS_TO_PROMOTE 40
#define Budget 25


static char *states[] = {
  [UNUSED]    "unused",
  [EMBRYO]    "embryo",
  [SLEEPING]  "sleep ",
  [RUNNABLE]  "runble",
  [RUNNING]   "run   ",
  [ZOMBIE]    "zombie"
};

struct StateLists {
  struct proc* ready[MAX+1];
  struct proc* free;
  struct proc* sleep;
  struct proc* zombie;
  struct proc* running;
  struct proc* embryo;
};

struct {
  struct spinlock lock;
  struct proc proc[NPROC];
  struct StateLists pLists;
  uint PromoteAtTime;
} ptable;


static struct proc *initproc;

int nextpid = 1;
extern void forkret(void);
extern void trapret(void);

static void wakeup1(void *chan);

static void
assertState(struct proc* p, enum procstate state)
{

  char *statee;
  if(p->state == state) {
    return;
  } else {
    statee = states[p->state];
    cprintf("process state = %s, target state = %s\n", statee, states[state]);
    panic(statee);
    return;
  }
}

int
removeFromStateList(struct proc** sList, struct proc* p)
{
  struct proc* temp;
  struct proc* current = *sList;

  if( current != 0 && current == p) {
    temp = current;
    current = current->next;
    temp = 0;
    *sList = current;
    return 1;
  } else {
    while(current != 0) {
      if(current->next != 0 && current->next == p) {
        temp = current->next;
        current->next = temp->next;
        temp = 0;
        break;
      }
      current = current->next;
    }
    return 1;
  }
  return -1;
}

void
addToFrontOfStateList (struct proc** sList, struct proc* p)
{
  p->next = (*sList);    
  (*sList)    = p;
  return;
}

void
addToEndOfStateList(struct proc** sList, struct proc* p)
{
  if(!*sList) {
    *sList = p;
    p->next = 0;
    return;
  } else {
    struct proc *temp = *sList;
    while(temp->next)
      temp = temp->next;
    temp->next = p;
    p->next = 0;
    return;
  }

}

int
removeFromFrontOfStateList(struct proc** sList)
{
  if(!*sList) {
    cprintf("List empty, cannot remove element");
    return -1;
  } else {
    struct proc *temp = *sList;
    *sList = temp->next;
    return 1;
   }
}

int
removeFromEndOfStateList(struct proc** sList)
{
  if(!*sList) {
    cprintf("List empty, cannot remove element");
    return -1;
  } else {
    struct proc *temp;
    struct proc *current = *sList;
    temp = current->next;
    while(temp->next){
      current = temp;
      temp = temp->next;
    }
    current->next = 0;
    return 1;
   }
}

void
resetProcessBudget(struct proc* p)
{

  p->budget = Budget;
  return;
}

int
setpriority(int pid, int priority)
{

  struct proc *p;
  int locked = 0;
  int count = 0;
  struct proc *procStateList[MAX+6];

  if (!holding(&ptable.lock)) { 
     acquire(&ptable.lock);
     locked = 1;
  } 
  
  for(int i = 0; i <= MAX; i++) {
    procStateList[count] = ptable.pLists.ready[count];
    count += 1;
  }
  procStateList[count] = ptable.pLists.sleep;
  count +=1;
  procStateList[count] = ptable.pLists.running;
  count +=1;
  procStateList[count] = ptable.pLists.embryo;
  count +=1;
  procStateList[count] = ptable.pLists.free;
  count +=1;
  procStateList[count] = ptable.pLists.zombie;

  for(int i = 0; i <= count; i++) {
    p = procStateList[i];
    while(p) {
      if (pid == p->pid) {
        if (p->state == RUNNABLE) {
          if (removeFromFrontOfStateList(&ptable.pLists.ready[p->priority]) > 0) {
            p->priority = priority;
            addToEndOfStateList(&ptable.pLists.ready[p->priority], p);
            if(locked == 1) release(&ptable.lock);
            return 1;
          } else {
            panic("In setpriority, cannot remove from ready");
          }
        } else {
          p->priority = priority;
          if(locked == 1) release(&ptable.lock);
          return 1;
        }
      }
      p = p->next;
    }
  }
  if(locked == 1) release(&ptable.lock);
  return -1;
}

void
demoteProcessPriority(struct proc* p)
{

  if (p->priority < MAX) {
    if (setpriority(p->pid, p->priority+1) > 0)
      return;
  } else {
    return;
  }
}


void
promoteProcessPriority(struct proc* p)
{
  if (p->priority > 0) {
    if (setpriority(p->pid, p->priority-1) > 0)
      return;
  } else {
    return;
  }
}

void
adjustPriority(void)
{  
  struct proc* p;
  int count = 0;
  struct proc *procStateList[MAX+3];

  for(int i = 0; i <= MAX; i++) {
    procStateList[count] = ptable.pLists.ready[count];
    count += 1;
  }
  procStateList[count] = ptable.pLists.sleep;
  count +=1;
  procStateList[count] = ptable.pLists.running;


  for(int i = 0; i <= count; i++) {
    for(p = procStateList[i]; p; p = p->next) {
      promoteProcessPriority(p);
    }
  }
  return;
}


static int 
fromToStateList(struct proc *p, int fromState, int toState, struct proc **from, struct proc **to) { 
 
  if (!holding(&ptable.lock)) { 
    panic("In fromToStateList without ptable.lock held\n"); 
  } 
 
  assertState(p, fromState); 
 
  if (fromState == RUNNABLE && toState == RUNNING) {
    if(removeFromFrontOfStateList(from) > 0) {
      p->state = toState;
      addToEndOfStateList(to, p);
      return 1;
    } else {
      return -1;
    }
  } else if ((fromState == RUNNING && toState == RUNNABLE) || (fromState == EMBRYO && toState == RUNNABLE) || (fromState == SLEEPING && toState == RUNNABLE)) {
    if (fromState == RUNNING) {
      p->budget = (p->budget - (ticks-p->cpu_ticks_in));
      if (p->budget <= 0) {
        demoteProcessPriority(p);
        resetProcessBudget(p);
      }
    }
    if (removeFromStateList(from, p) > 0){
      p->state = toState;
      addToEndOfStateList(to, p);
      return 1;
    } else {
      return -1;
    }
  } else if ((fromState == RUNNING && toState == SLEEPING) || (fromState == RUNNING && toState == ZOMBIE) || 
             (fromState == UNUSED && toState == EMBRYO) || (fromState == EMBRYO && toState == UNUSED) || (fromState == ZOMBIE && toState == UNUSED)) {
    if (fromState == RUNNING) {
      p->budget = (p->budget - (ticks-p->cpu_ticks_in));
      if (p->budget <= 0) {
        demoteProcessPriority(p);
        resetProcessBudget(p);
      }
    }
    if(removeFromStateList(from, p) > 0){
      p->state = toState;
      addToFrontOfStateList(to, p);
      return 1;
    } else {
      return -1;
    }
  } 
  return -1; 
}

void
checkZombie(struct proc *p)
{

  if(p->parent == proc) {
    p->parent = initproc;
    if(p->state == ZOMBIE){
       wakeup1(initproc);
    } else {
       wakeup1(p);
    }
  }
  return;
}

int
listSize(struct proc** sList)
{
  int count = 0;
  struct proc *p = *sList;
  while(p) {
   count += 1;
   p = p->next;
  }
  return count;
}

void
printFreeListSize(void)
{
  acquire(&ptable.lock);
  cprintf("Free List Size: %d processes\n", listSize(&ptable.pLists.free));
  release(&ptable.lock);
  return;
}

void
printReadyList(void)
{
  struct proc *p;
  int count;

  cprintf("Ready List Processes:\n");
  acquire(&ptable.lock);
  for (int i = 0; i <= MAX; i++) {
    count = 0;
    if (ptable.pLists.ready[i]) {
      cprintf("%d: ", i);
      for (p = ptable.pLists.ready[i]; p; p=p->next) {
        if (count > 1) cprintf("-> ");
        cprintf("(%d, %d) ", p->pid, p->budget);
        count += 1;
      }
    cprintf("\n");
    }
  }
  release(&ptable.lock);
  return;
}

void
printSleepList(void)
{

  struct proc *p;
  int listSz;

  cprintf("Sleep List Processes:\n");
  acquire(&ptable.lock);
  listSz = listSize(&ptable.pLists.sleep);
  while(listSz > 0) {
    p = &ptable.pLists.sleep[listSz-1];
    cprintf("%d ", p->pid);
    listSz -= 1;
    if (listSz > 0) {
      cprintf("-> ");
    }
  }
  cprintf("\n");
  release(&ptable.lock);
  return;
}

void
printZombieList(void)
{

  struct proc *p;
  int count = 0;
  int listSz;

  cprintf("Zombie List Processes:\n");
  acquire(&ptable.lock);
  listSz = listSize(&ptable.pLists.zombie);
  while(listSz > 0) {
    p = &ptable.pLists.zombie[listSz-1];
    cprintf("(%d, %dPPID) ", p->pid, p->parent->pid);
    count += 1;
    if (count >= 1 && count < listSz) {
      cprintf("-> ");
    }
  listSz -= 1;
  }
  cprintf("\n");
  release(&ptable.lock);
  return;
}

void
pinit(void)
{
  initlock(&ptable.lock, "ptable");
}

// Look in the process table for an UNUSED proc.
// If found, change state to EMBRYO and initialize
// state required to run in the kernel.
// Otherwise return 0.
static struct proc*
allocproc(void)
{
  char *sp;
  struct proc *p;

  acquire(&ptable.lock);
  p = ptable.pLists.free;
  if(p)
    goto found;
  release(&ptable.lock);
  return 0;

found:
  // State transition from UNUSED to EMBRYO
  p->parent = proc;
  if (fromToStateList(p, UNUSED, EMBRYO, &ptable.pLists.free, &ptable.pLists.embryo) < 0){
    panic("In allocproc(), transition from UNUSED to EMBRYO failed\n");
  }

  p->pid = nextpid++;
  release(&ptable.lock);

  // Allocate kernel stack.
  if((p->kstack = kalloc()) == 0){
    acquire(&ptable.lock);
    // State transition from EMBRYO to UNUSED
    if (fromToStateList(p, EMBRYO, UNUSED, &ptable.pLists.embryo, &ptable.pLists.free) < 0) {
      panic("In allocproc(), transition from EMBRYO to UNUSED failed\n");
    }
    release(&ptable.lock);
    return 0;
  }
  sp = p->kstack + KSTACKSIZE;

  // Leave room for trap frame.
  sp -= sizeof *p->tf;
  p->tf = (struct trapframe*)sp;

  // Set up new context to start executing at forkret,
  // which returns to trapret.
  sp -= 4;
  *(uint*)sp = (uint)trapret;

  sp -= sizeof *p->context;
  p->context = (struct context*)sp;
  memset(p->context, 0, sizeof *p->context);
  p->context->eip = (uint)forkret;

  // Add initialize cpu_ticks_total and cpu_ticks_in to 0
  p->cpu_ticks_total = 0;
  p->cpu_ticks_in = 0;
  p->budget = Budget;

  return p;
}

// Set up first user process.
void
userinit(void)
{

  struct proc *p;
  extern char _binary_initcode_start[], _binary_initcode_size[];

  ptable.PromoteAtTime = ticks + TICKS_TO_PROMOTE; 
  ptable.pLists.zombie = 0;
  ptable.pLists.sleep = 0;
  ptable.pLists.running = 0;
  ptable.pLists.embryo = 0;
  ptable.pLists.free = 0;
  for(int i = 0; i <= MAX; i++) {
    ptable.pLists.ready[i] = 0;
  }

  // Initialize free list
  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
    p->state = UNUSED;
    addToFrontOfStateList(&ptable.pLists.free, p);
  }
  release(&ptable.lock);
  
  p = allocproc();

  p->uid = UID;
  p->gid = GID;
  p->start_ticks = ticks;

  initproc = p;
  if((p->pgdir = setupkvm()) == 0){
    acquire(&ptable.lock);
    // State transition from EMBRYO to UNUSED
    if (fromToStateList(p, EMBRYO, UNUSED, &ptable.pLists.embryo, &ptable.pLists.free) < 0){
      panic("In userinit(), state transition from EMBRYO to UNUSED unsuccessful");
    }
    release(&ptable.lock);
    panic("userinit: out of memory?");
  }
  inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
  p->sz = PGSIZE;
  memset(p->tf, 0, sizeof(*p->tf));
  p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
  p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
  p->tf->es = p->tf->ds;
  p->tf->ss = p->tf->ds;
  p->tf->eflags = FL_IF;
  p->tf->esp = PGSIZE;
  p->tf->eip = 0;  // beginning of initcode.S

  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");

  acquire(&ptable.lock);
  p->budget = Budget;
  p->priority = 0;
  // State transition from EMBRYO to RUNNABLE
  if (fromToStateList(p, EMBRYO, RUNNABLE, &ptable.pLists.embryo, &ptable.pLists.ready[p->priority]) < 0){
    panic("In userint(), state transition from EMBRYO to RUNNABLE unsuccessful");
  }
  release(&ptable.lock);
}


// Grow current process's memory by n bytes.
// Return 0 on success, -1 on failure.
int
growproc(int n)
{
  uint sz;

  sz = proc->sz;
  if(n > 0){
    if((sz = allocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  } else if(n < 0){
    if((sz = deallocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  }
  proc->sz = sz;
  switchuvm(proc);
  return 0;
}

// Create a new process copying p as the parent.
// Sets up stack to return as if from system call.
// Caller must set state of returned proc to RUNNABLE.
int
fork(void)
{
  int i, pid;
  struct proc *np;

  // Allocate process.
  if((np = allocproc()) == 0)
    return -1;

  // Copy process state from p.
  if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){
    kfree(np->kstack);
    np->kstack = 0;

    acquire(&ptable.lock);
    // State transition from EMBRYO to UNUSED
    if (fromToStateList(np, EMBRYO, UNUSED, &ptable.pLists.embryo, &ptable.pLists.free) < 0){
      panic("In fork(), state transition from EMBRYO to UNUSED unsuccessful");
    }
    release(&ptable.lock);
    return -1;
  }
  np->sz = proc->sz;
  np->parent = proc;
  *np->tf = *proc->tf;

  // Clear %eax so that fork returns 0 in the child.
  np->tf->eax = 0;

  for(i = 0; i < NOFILE; i++)
    if(proc->ofile[i])
      np->ofile[i] = filedup(proc->ofile[i]);
  np->cwd = idup(proc->cwd);

  safestrcpy(np->name, proc->name, sizeof(proc->name));

  pid = np->pid;

  np->start_ticks = ticks;

  np->uid = proc->uid; // Copy uid to child
  np->gid = proc->gid; // Copy gid to child

  np->budget = Budget;
  np->priority = proc->priority;

  acquire(&ptable.lock);
  // State transition from EMBRYO to RUNNABLE
  if (fromToStateList(np, EMBRYO, RUNNABLE, &ptable.pLists.embryo, &ptable.pLists.ready[np->priority]) < 0){
      panic("In fork(), state transition from EMBRYO to RUNNABLE unsuccessful");
  }
  release(&ptable.lock);

  return pid;
}

// Exit the current process.  Does not return.
// An exited process remains in the zombie state
// until its parent calls wait() to find out it exited.
void
exit(void)
{
  struct proc *procStateList[MAX+6];
  struct proc *p;
  int fd;
  int count = 0;

  if(proc == initproc)
    panic("init exiting");

  // Close all open files.
  for(fd = 0; fd < NOFILE; fd++){
    if(proc->ofile[fd]){
      fileclose(proc->ofile[fd]);
      proc->ofile[fd] = 0;
    }
  }

  begin_op();
  iput(proc->cwd);
  end_op();
  proc->cwd = 0;

  acquire(&ptable.lock);
  for(int i = 0; i <= MAX; i++) {
    procStateList[count] = ptable.pLists.ready[count];
    count += 1;
  }

  procStateList[count] = ptable.pLists.sleep;
  count +=1;
  procStateList[count] = ptable.pLists.running;
  count +=1;
  procStateList[count] = ptable.pLists.embryo;
  count +=1;
  procStateList[count] = ptable.pLists.zombie;
  count +=1;
  procStateList[count] = ptable.pLists.free;

  // Parent might be sleeping in wait().
  wakeup1(proc->parent);

  for(int i = 0; i <= count; i++) {
    for(p = procStateList[i]; p; p = p->next) {
       checkZombie(p);
    }
  }
 

 // State transition from RUNNING to ZOMBIE
  if (fromToStateList(proc, RUNNING, ZOMBIE, &ptable.pLists.running, &ptable.pLists.zombie) < 0){
    panic("In exit(), state transition from RUNNING to ZOMBIE unsuccessful");
  }
  sched();
  panic("zombie exit");
}

// Wait for a child process to exit and return its pid.
// Return -1 if this process has no children.
int
wait(void)
{
  struct proc *p;
  int havekids, pid;
  int count = 0;

  struct proc *procStateList[MAX+5];


  for(int i = 0; i <= MAX; i++) {
    procStateList[count] = ptable.pLists.ready[count];
    count += 1;
  }
  procStateList[count] = ptable.pLists.sleep;
  count +=1;
  procStateList[count] = ptable.pLists.running;
  count +=1;
  procStateList[count] = ptable.pLists.embryo;
  count +=1;
  procStateList[count] = ptable.pLists.zombie;

  acquire(&ptable.lock);
  for(;;){
    // Scan through table looking for zombie children.
    havekids = 0;
    for(int i = 0; i <= count; i++) {
      for(p = procStateList[i]; p; p = p->next) {
         if(p->parent != proc)
           continue;
         havekids = 1;
         if(p->state == ZOMBIE){
           // Found one.
           pid = p->pid;
           kfree(p->kstack);
           p->kstack = 0;
           freevm(p->pgdir);
           // State transition from ZOMBIE to UNUSED
           if (fromToStateList(p, ZOMBIE, UNUSED, &ptable.pLists.zombie, &ptable.pLists.free) < 0){
             panic("In wait(), state transition from ZOMBIE to UNUSED unsuccessful");
           }
           p->pid = 0;
           p->parent = 0;
           p->name[0] = 0;
           p->killed = 0;
           release(&ptable.lock);
          return pid;
        }
      }
    }
    // No point waiting if we don't have any children.
    if(!havekids || proc->killed){
      release(&ptable.lock);
      return -1;
    }
    // Wait for children to exit.  (See wakeup1 call in proc_exit.)
    sleep(proc, &ptable.lock);  //DOC: wait-sleep
  }
}

// Per-CPU process scheduler.
// Each CPU calls scheduler() after setting itself up.
// Scheduler never returns.  It loops, doing:
//  - choose a process to run
//  - swtch to start running that process
//  - eventually that process transfers control
//      via swtch back to the scheduler.
void
scheduler(void)
{

  struct proc *p;
  int idle;  // for checking if processor is idle

  for(;;){

    sti();
    idle = 1;  // assume idle unless we schedule a process

    acquire(&ptable.lock);
    if (ptable.PromoteAtTime <= ticks) {
      adjustPriority();
      ptable.PromoteAtTime = ticks + TICKS_TO_PROMOTE;
    }
 
    for (int i = 0; i <= MAX; i++) { 
      while(ptable.pLists.ready[i]) {

        p = ptable.pLists.ready[i];

        if(p->state != RUNNABLE)
          continue;

        idle = 0;  // not idle this timeslice
        proc = p;
        switchuvm(p);
        
        if (fromToStateList(p, RUNNABLE, RUNNING, &ptable.pLists.ready[i], &ptable.pLists.running) < 0){
          panic("In scheduler(), state transition from RUNNABLE to RUNNING unsuccessful");
        }

        p->cpu_ticks_in = ticks;

        swtch(&cpu->scheduler, proc->context);
        switchkvm();

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        proc = 0;
      }
    }
    release(&ptable.lock);

    // if idle, wait for next interrupt
    if (idle) {
      sti();
      hlt();
    }
  }
}


// Enter scheduler.  Must hold only ptable.lock
// and have changed proc->state.
void
sched(void)
{
  int intena;

  if(!holding(&ptable.lock))
    panic("sched ptable.lock");
  if(cpu->ncli != 1)
    panic("sched locks");
  if(proc->state == RUNNING)
    panic("sched running");
  if(readeflags()&FL_IF)
    panic("sched interruptible");
  intena = cpu->intena;
  proc->cpu_ticks_total += (ticks - proc->cpu_ticks_in);
  swtch(&proc->context, cpu->scheduler);
  cpu->intena = intena;
}

// Give up the CPU for one scheduling round.
void
yield(void)
{
  acquire(&ptable.lock);  //DOC: yieldlock

  //State transition from RUNNING to RUNNABLE
  if (fromToStateList(proc, RUNNING, RUNNABLE, &ptable.pLists.running, &ptable.pLists.ready[proc->priority]) < 0) {
    panic("In yield(), transition from RUNNING to RUNNABLE unsuccessful");
  }
  sched();
  release(&ptable.lock);
}

// A fork child's very first scheduling by scheduler()
// will swtch here.  "Return" to user space.
void
forkret(void)
{
  static int first = 1;
  // Still holding ptable.lock from scheduler.
  release(&ptable.lock);

  if (first) {
    // Some initialization functions must be run in the context
    // of a regular process (e.g., they call sleep), and thus cannot
    // be run from main().
    first = 0;
    iinit(ROOTDEV);
    initlog(ROOTDEV);
  }

  // Return to "caller", actually trapret (see allocproc).
}

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
// 2016/12/28: ticklock removed from xv6. sleep() changed to
// accept a NULL lock to accommodate.
void
sleep(void *chan, struct spinlock *lk)
{

  if(proc == 0)
    panic("sleep");

  // Must acquire ptable.lock in order to
  // change p->state and then call sched.
  // Once we hold ptable.lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup runs with ptable.lock locked),
  // so it's okay to release lk.
  if(lk != &ptable.lock){
    acquire(&ptable.lock);
    if (lk) release(lk);
  }

  // Go to sleep.
  proc->chan = chan;

  // State transition from RUNNING to SLEEPING
  if (fromToStateList(proc, RUNNING, SLEEPING, &ptable.pLists.running, &ptable.pLists.sleep) < 0){
    panic("In sleep(), transition from RUNNING to SLEEPING unsuccessful");
  }
  sched();

  // Tidy up.
  proc->chan = 0;

  // Reacquire original lock.
  if(lk != &ptable.lock){
    release(&ptable.lock);
    if (lk) acquire(lk);
  }
}

// Wake up all processes sleeping on chan.
// The ptable lock must be held.
static void
wakeup1(void *chan)
{
  struct proc *p;

  for(p = ptable.pLists.sleep; p; p = p->next) {
    if(p->chan == chan && p->state == SLEEPING) {
      // State transition from SLEEPING to RUNNABLE
      if (fromToStateList(p, SLEEPING, RUNNABLE, &ptable.pLists.sleep, &ptable.pLists.ready[p->priority]) < 0) {
        panic("In wakeup1(), transition from SLEEPING to RUNNABLE unsuccessful");
      }
    }
  }
}

// Wake up all processes sleeping on chan.
void
wakeup(void *chan)
{
  acquire(&ptable.lock);
  wakeup1(chan);
  release(&ptable.lock);
}

// Kill the process with the given pid.
// Process won't exit until it returns
// to user space (see trap in trap.c).
int
kill(int pid)
{
  struct proc *p;
  int count = 0;

  struct proc *procStateList[MAX+6];


  acquire(&ptable.lock);
  for(int i = 0; i <= MAX; i++) {
    procStateList[count] = ptable.pLists.ready[count];
    count += 1;
  }
  procStateList[count] = ptable.pLists.sleep;
  count +=1;
  procStateList[count] = ptable.pLists.running;
  count +=1;
  procStateList[count] = ptable.pLists.embryo;
  count +=1;
  procStateList[count] = ptable.pLists.zombie;
  count +=1;
  procStateList[count] = ptable.pLists.free;


  for(int i = 0; i <= count; i++) {
    for(p = procStateList[i]; p; p = p->next) {
      if(p->pid == pid){
        p->killed = 1;
        // Wake process from sleep if necessary.
        if(p->state == SLEEPING){
          if (fromToStateList(p, SLEEPING, RUNNABLE, &ptable.pLists.sleep, &ptable.pLists.ready[p->priority]) < 0){
            panic("In kill(), transition from SLEEPING to RUNNABLE unsuccessful");
          }
        }
        release(&ptable.lock);
        return 0;
      }
    }
  }
  release(&ptable.lock);
  return -1;
}


int
getprocs(int max, struct uproc * table){

  struct proc *p;
  int i;

  // Iterate over proc table to extract info for each process,
  // assigning the values to the uproc struct along the way
  acquire(&ptable.lock);
  for(i = 0, p = ptable.proc; p < &ptable.proc[NPROC] && i<max; p++)
    // check for unused and embryo
    if (p->state != UNUSED && p->state != EMBRYO) {
      // Set process pid
      table[i].pid = p->pid;
      table[i].priority = p->priority;
      // Set process uid
      table[i].uid = p->uid;
      // Set process gid
      table[i].gid = p->gid;
      // Fix for top level pid not having parent
      if (p->pid > 1) {
        table[i].ppid = p->parent->pid;
      } else {
        table[i].ppid = 0;
      }
      // Set process size
      table[i].size = p->sz;
      // Set process elapsed ticks
      table[i].elapsed_ticks = (ticks-p->start_ticks);
      // Set process total ticks
      table[i].CPU_total_ticks = p->cpu_ticks_total;
      // safestrcpy process name
      safestrcpy(table[i].name, p->name, sizeof(p->name));
      // safestrcpy process state
      safestrcpy(table[i].state, states[p->state], 20);
      // increment process counter
      i++;
    }
  release(&ptable.lock);
  return i;
}

void
printProcDumpVals(char *state, struct proc *p)
{
  uint ppid;

  // Check that the pid is greater then 1
  // such that the process will actually have a parent
  // otherwise, we know we are the parent, so assign pid = 0
  if (p->pid > 1) {
    ppid = p->parent->pid;
  } else {
    ppid = 0;
  }

  cprintf("%d\t%s\t", p->pid, p->name);

  if (strlen(p->name) < 8) cprintf("\t");

  cprintf("%d\t%d\t%d\t%d\t%d.", p->uid, p->gid, ppid, p->priority,
          ((ticks-p->start_ticks) / 100));

  if (((ticks-p->start_ticks) % 100) < 10) cprintf("0");
  cprintf("%d\t", ((ticks-p->start_ticks) % 100));

  cprintf("%d.", (p->cpu_ticks_total / 100));
  if ((p->cpu_ticks_total % 100) < 10) cprintf("0");

  cprintf("%d\t%s\t%d \t", (p->cpu_ticks_total % 100), state, p->sz);
}

//// Print a process listing to console.  For debugging.
//// Runs when user types ^P on console.
//// No lock to avoid wedging a stuck machine further.
void
procdump(void)
{
  struct proc *p;
  char *state;
  uint pc[10];

  int count = 0;
  struct proc *procStateList[MAX+5];

  for(int i = 0; i <= MAX; i++) {
    procStateList[count] = ptable.pLists.ready[count];
    count += 1;
  }
  procStateList[count] = ptable.pLists.sleep;
  count +=1;
  procStateList[count] = ptable.pLists.running;
  count +=1;
  procStateList[count] = ptable.pLists.embryo;
  count +=1;
  procStateList[count] = ptable.pLists.zombie;


  cprintf("PID\tNAME\t\tUID\tGID\tPPID\tPrio\tElapsed\tCPU\tState\tSize\t PCs\n");

  while(count >= 0) {
    if (procStateList[count]) {
      p = procStateList[count];
      while(p) {
        if(p->state == UNUSED)
          continue;
        if(p->state >= 0 && p->state < NELEM(states) && states[p->state]) {
          state = states[p->state];
        } else {
          state = "???";
        }
        // print procdump vals
        printProcDumpVals(state, p);
  
        if(p->state == SLEEPING){
          getcallerpcs((uint*)p->context->ebp+2, pc);
          for(int i=0; i<10 && pc[i] != 0; i++)
            cprintf(" %p", pc[i]);
        }
        cprintf("\n");
        p = p->next;
      }
    }
    count -= 1;
  }
}