/* Sleeps for approximately TICKS timer ticks.  Interrupts must
   be turned on. */
void
timer_sleep (int64_t ticks)
{
  int64_t start = timer_ticks ();
  ASSERT (intr_get_level () == INTR_ON);
  int old_level = intr_set_level(INTR_OFF);
  list_push_back(&dormidos, &(thread_current()->elem));
  (thread_current()->por_dormir) = ticks;
  thread_block();
  intr_set_level(old_level);
  
} //PRACTICA1

/* Writes C to the VGA text display, interpreting control
   characters in the conventional ways.  */
void
vga_putc (int c)
{
  /* Disable interrupts to lock out interrupt handlers
     that might write to the console. */
  enum intr_level old_level = intr_disable ();

  init ();
  
  switch (c) 
    {
    case '\n':
      newline ();
      break;

    case '\f':
      cls ();
      break;

    case '\b':
      if (cx > 0)
        cx--;
      break;
      
    case '\r':
      cx = 0;
      break;

    case '\t':
      cx = ROUND_UP (cx + 1, 8);
      if (cx >= COL_CNT)
        newline ();
      break;

    case '\a':
      intr_set_level (old_level);
      speaker_beep ();
      intr_disable ();
      break;
      
    default:
      fb[cy][cx][0] = c;
      fb[cy][cx][1] = GRAY_ON_BLACK;
      if (++cx >= COL_CNT)
        newline ();
      break;
    }

  /* Update cursor position. */
  move_cursor ();

  intr_set_level (old_level);
}

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);

  old_level = intr_disable ();
  if (!list_empty (&sema->waiters)) 
  {  
				
			struct list_elem * sema_waitlist_p = list_begin(&sema->waiters);
			struct list_elem * high = list_begin(&sema->waiters);
			for(;
			sema_waitlist_p != NULL && sema_waitlist_p->next != NULL && sema_waitlist_p->prev != NULL;)
			{
				if(list_entry(sema_waitlist_p, struct thread, elem)->priority >
				list_entry(high, struct thread, elem)->priority)
						high = sema_waitlist_p;
				sema_waitlist_p = list_next(sema_waitlist_p);
			}
			sema->current_holder = NULL;
			struct thread * t = list_entry(high, struct thread, elem);
			list_remove(high);
			thread_unblock (t);
	}
	sema->value++;
  intr_set_level (old_level);
}

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
void
lock_acquire (struct lock *lock)
{
  enum intr_level old_level;

  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));

  old_level = intr_disable ();

  if (lock->holder != NULL) 
    {
      /* Donate our priority to the thread holding the lock.
         First, update the data structures. */
      struct thread *donor = thread_current ();
      donor->want_lock = lock;
      donor->donee = lock->holder;
      list_push_back (&lock->holder->donors, &donor->donor_elem);
      
      /* Now implement the priority donation itself
         by recomputing the donee's priority
         and cascading the donation as far as necessary. */
      if (donor->donee != NULL)
        thread_recompute_priority (donor->donee);
    }

  sema_down (&lock->semaphore);
  lock->holder = thread_current ();
  intr_set_level (old_level);
}

/* Down or "P" operation on a semaphore.  Waits for SEMA's value
 *  to become positive and then atomically decrements it.
 *
 *  This function may sleep, so it must not be called within an
 *  interrupt handler.  This function may be called with
 *  interrupts disabled, but if it sleeps then the next scheduled
 *  thread will probably turn interrupts back on. */
void sema_down(struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT(sema != NULL);
    ASSERT(!intr_context());

    old_level = intr_disable();
    while (sema -> value == 0) {
        /*
         * 注释掉原有的代码
         * list_push_back(&sema -> waiters, &thread_current() -> elem);
         * thread_block();
         */

        if (!thread_mlfqs) {
            donate_priority();
        }

        list_insert_ordered(
                &sema -> waiters,
                &thread_current() -> elem,
                (list_less_func *) &cmp_priority,
                NULL
        );
        thread_block();
    }

    sema -> value--;
    intr_set_level(old_level);
}

/* 
 --------------------------------------------------------------------
 Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. 
 NOTE: if we cannot aquire the lock and we are in regular priority
    donation scheduling, then we invoke the call to donate our
    priority. Once we move past the semaphore, we have aquired the 
    lock, and thus add it to our list of locks_held, so that this
    thread can properly recieve priortity donations. 
 --------------------------------------------------------------------
 */
void
lock_acquire (struct lock *lock)
{
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));
    
    enum intr_level old_level = intr_disable();
    
    if (!thread_mlfqs) { 
        if (lock->holder != NULL) {
            thread_current()->lock_waiting_on = lock;
            //donate_priority();
        }
    }
    
    sema_down (&lock->semaphore);
    
    if (!thread_mlfqs) {
        lock->priority = PRI_MIN;
        list_push_front(&(thread_current()->locks_held), &(lock->elem));
        thread_current()->lock_waiting_on = NULL;
    }
    lock->holder = thread_current ();
    
    intr_set_level(old_level);
}

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
void
lock_acquire (struct lock *lock)
{
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));
  
  struct thread *cur_thread = thread_current ();

  /* If we are not in the multi-level feedback queue scheduler
     then use priority donation */
  if(!thread_mlfqs)
  {
    /* donate priority if someone holds the lock we want */
    enum intr_level old_level = intr_disable ();
     
    if (lock->holder != NULL) {
      cur_thread->lock_waiting_for = lock;
      cur_thread->t_donating_to = lock->holder;
      thread_donate_priority(cur_thread);
    }
    intr_set_level (old_level);
  }  

  sema_down (&lock->semaphore);
  lock->holder = cur_thread;
}

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);

  old_level = intr_disable ();
  bool should_yield = false;
  if (!list_empty (&sema->waiters)) 
  {
    struct thread* t = list_entry (list_pop_front (&sema->waiters),
        struct thread, elem);
    should_yield = t->priority >= thread_current ()->priority;
    thread_unblock (t);
  }
  sema->value++;
  intr_set_level (old_level);

  /* Yield if higher priority thread in ready list */
  if (should_yield)
  {
    thread_yield ();
  }
}

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
void
lock_acquire (struct lock *lock)
{
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));

  enum intr_level old_level = intr_disable ();

  if (lock->holder != NULL) /* If the lock is being held. */
  {
    /* Updates current thread's lock_to_acquire attribute,
       adds itself to the lock holder's donors list and
       donates priority. */
    thread_current ()->lock_to_acquire = lock;
    list_push_front (&lock->holder->priority_donors,
                     &thread_current ()->donor);
    priority_donation ();
  }

  sema_down (&lock->semaphore);

  /* The lock has been acquired: current thread is not waiting
     for it anymore. */
  thread_current ()->lock_to_acquire = NULL;
  lock->holder = thread_current ();

  intr_set_level (old_level);
}

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
void
lock_acquire (struct lock *lock)
{
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));
  ASSERT (thread_current ()->waiting_on == NULL);

  enum intr_level old_level;
  old_level = intr_disable ();
  
  /* If the lock is currently held by someone, then we need to invoke
     thread_donate_priority to donate our priority to that special
     someone. */  
  if (!thread_mlfqs && lock->holder != NULL)
    {
      thread_current ()->waiting_on = lock;
      thread_donate_priority (thread_current ());
    }

  sema_down (&lock->semaphore);

  lock->holder = thread_current ();
  thread_current ()->waiting_on = NULL;

  intr_set_level (old_level);
}

/* Releases LOCK, which must be owned by the current thread.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to release a lock within an interrupt
   handler. */
void
lock_release (struct lock *lock) 
{
  ASSERT (lock != NULL);
  ASSERT (lock_held_by_current_thread (lock));

  enum intr_level old_level = intr_disable ();
  lock->holder = NULL;

  /* If we're using the priority scheduler, loop through all threads
     that were waiting on this lock and notify them to remove their
     priority donations. */
  if (!thread_mlfqs)
    {
      struct list_elem *e;
      for (e = list_begin (&lock->semaphore.waiters);
           e != list_end (&lock->semaphore.waiters);
           e = list_next (e))
       {
    	   struct thread *t = list_entry (e, struct thread, elem);
    	   thread_recall_donation (t);
    	 }
  
      /* Recompute my effective priority, since I may have just lost
         some donations. */
      thread_calculate_priority (thread_current ());
    }
  
  lock->holder = NULL;
  /* NOTE : It's possible that we will be preempted by sema_up. */
  sema_up (&lock->semaphore);
  intr_set_level (old_level);
}

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);

  old_level = intr_disable ();

  /* If the list of waiters isn't empty, retrieve and unblock the highest-
     priority waiter on the list. */
  if (!list_empty (&sema->waiters))
  {
    /* NOTE : The "highest priority" waiter will actually be the minimal
              list element, since priority_cmp is >, but list_min expects <. */
    struct list_elem *highest_waiter = list_min (&sema->waiters,
                                                 thread_priority_cmp, NULL);
    list_remove (highest_waiter);
    thread_unblock (list_entry (highest_waiter, struct thread, elem));
  }
  sema->value++;
  intr_set_level (old_level);
  
  /* We may have just unblocked a thread with a higher priority than us,
     in which case we need to yield to it. */
  thread_yield_to_max ();
}

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);

  old_level = intr_disable ();
  sema->value++;
  struct list_elem *next;
  if (list_empty (&sema->waiters))
  {
    next = NULL;
  }
  else
  {
    next = list_max(&sema->waiters, thread_priority_compare, NULL);
    list_remove (next);
    thread_unblock (list_entry (next, struct thread, elem));
  }
  
  if (next && thread_priority_compare(&thread_current()->elem, next, NULL))
  {
    thread_yield();
  }
  intr_set_level (old_level);
}

/* Runs the executable given in cmd_line. cmd_line includes the arguments as
   well. Returns the new process' pid. Returns -1 if the process could not
   load or run for some reason. After this function is called in
   syscall_handler(), the new process' id is sent to the kernel. Parent/Child
   relationship is set in process_execute(). */
static pid_t
sys_exec(const char *cmd_line) 
{
  check_mem_ptr(cmd_line);
  lock_acquire(&secure_file);

  /* Identity mapping between thread id and process id, because
     Pintos is not multithreaded. */
  pid_t pid = (pid_t)process_execute(cmd_line);

  /* We want to wait until the child has definitely loaded, and then check to
     see whether it has loaded or not (e.g. whether the filename was invalid).
     load_sema is initialised to 0 for a thread. We use load_sema of the child
     to make this function wait, by doing sema_down on the child's exec_sema. We
     will have to wait until sema_up has been called on this sema in
     start_process (after load has been called). Just before sema_up has been
     called, start_process will set the threads loaded bool to true, so we can
     then read this bool to decide whether to return -1.  */
  enum intr_level old_level = intr_disable();
  struct thread *child = tid_to_thread((tid_t)pid);
  intr_set_level(old_level);

  sema_down(&child->load_sema);
  lock_release(&secure_file);

  if (!(child->loaded))
    return PID_ERROR;

  return pid;
}

/* Sleeps for approximately TICKS timer ticks.  Interrupts must
   be turned on. */
void
timer_sleep (int64_t ticks) 
{
  int64_t start = timer_ticks ();

  ASSERT (intr_get_level () == INTR_ON);
#if 0 /* pj1 */
  while (timer_elapsed (start) < ticks) 
    thread_yield ();
#endif

#if 1 /* pj1 */
  if (ticks <= 0)
	  return;
  /* add current thread to sleep thread list in order, 
   * and set its wake up time. Then schedule a new thread.
   */
  struct thread *cur = thread_current();
  enum intr_level old_level;
  lock_acquire(&sleep_list_lock);
  old_level = intr_disable();
  cur->wake_up_ticks = start + ticks; 
  list_insert_ordered(&sleep_list, &cur->elem, (list_less_func *)cmp_thread_wake_ticks, NULL);
  lock_release(&sleep_list_lock);
  thread_block();
  intr_set_level(old_level);
#endif
}

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
void
lock_acquire (struct lock *lock)
{
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));
  
  enum intr_level old_state = intr_disable();
  // If there is lock holder
  // Add this thread to donorList of lock holder
  if (lock->holder != NULL)
  {
    // Save lock to this thread 
    thread_current()->tLock = lock;
    list_push_back(&lock->holder->donorList,&thread_current()->donorElem);
  }
  intr_set_level(old_state);

  sema_down (&lock->semaphore);
  // This thread is now the holder
  // Not waiting on any lock
  thread_current()->tLock = NULL;
  lock->holder = thread_current ();
  //intr_set_level(old_state);
}

/*! Sends BYTE to the serial port. */
void serial_putc(uint8_t byte) {
    enum intr_level old_level = intr_disable();

    if (mode != QUEUE) {
        /* If we're not set up for interrupt-driven I/O yet,
           use dumb polling to transmit a byte. */
        if (mode == UNINIT)
            init_poll();
        putc_poll(byte); 
    }
    else {
        /* Otherwise, queue a byte and update the interrupt enable register. */
        if (old_level == INTR_OFF && intq_full(&txq)) {
            /* Interrupts are off and the transmit queue is full.
               If we wanted to wait for the queue to empty,
               we'd have to reenable interrupts.
               That's impolite, so we'll send a character via
               polling instead. */
            putc_poll(intq_getc (&txq)); 
        }

        intq_putc(&txq, byte); 
        write_ier();
    }

    intr_set_level(old_level);
}

/* Releases LOCK, which must be owned by the current thread.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to release a lock within an interrupt
   handler. */
void
lock_release (struct lock *lock) 
{
  ASSERT (lock != NULL);
  ASSERT (lock_held_by_current_thread (lock));
  
  enum intr_level old_state = intr_disable();
  // Remove all donors that hold this lock
  if (!list_empty(&thread_current()->donorList))
  {
    struct list_elem *e, *tmp;
    for (e = list_begin(&thread_current()->donorList);
         e != list_end(&thread_current()->donorList);
	 e = tmp)
    {
      struct thread *t = list_entry(e, struct thread, donorElem);
      tmp = list_next(e);
      if (t->tLock == lock) list_remove(e);
    }
  }
  intr_set_level(old_state);

  lock->holder = NULL;
  sema_up (&lock->semaphore);
  //intr_set_level(old_state);
}

/*! Up or "V" operation on a semaphore.  Increments SEMA's value
    and wakes up one thread of those waiting for SEMA, if any.

    This function may be called from an interrupt handler. */
void sema_up(struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT(sema != NULL);

    old_level = intr_disable();
    sema->value++;
    if (!list_empty(&sema->waiters)) {
        struct list_elem *e = list_begin(&sema->waiters);
        struct thread *wake_thread = list_entry(e, struct thread, elem);
        int max_priority = compute_priority(wake_thread);

        for (e = list_next(e); e != list_end(&sema->waiters); 
             e = list_next(e)) { 
            struct thread *t = list_entry(e, struct thread, elem);
            int priority = compute_priority(t);
            if (priority > max_priority) { 
                max_priority = priority;
                wake_thread = t;
            }
        }

        list_remove(&wake_thread->elem);
        thread_unblock(wake_thread);
        if (max_priority >= thread_get_priority()) {
            thread_yield();
        } 

    }
    intr_set_level(old_level);
}

/* Sleeps for approximately TICKS timer ticks.  Interrupts must
   be turned on. */
void
timer_sleep (int64_t ticks) 
{
//printf("SLEEP WAS CALLED!\n");
  int64_t start = timer_ticks ();
  if(ticks < 0)
	  ticks = start;
  struct thread *t = thread_current();
 

 
  t->awakeTime = (start + ticks);

  //printf("setting awaketime to ", t->awakeTime);

 // printf("set wake at %d \n" , t->awakeTime);
  ASSERT (intr_get_level () == INTR_ON);

  enum intr_level curState = intr_disable();
  list_insert_ordered(getWaitList(), &t->waitelem,COMPAREFUNC,NULL);
  //printf("print something----------------------------------------------------------");
  //add t to a list of sleeping threads in order...
  thread_block();
  // put thread to sleep
  intr_set_level(curState);

  //while (timer_elapsed (start) < ticks) 
  //  thread_yield ();
}