void timer_sleep(int64_t ticks)
{
	int64_t start = timer_ticks();
    enum intr_level old_level;
    ASSERT(intr_get_level() == INTR_ON);
    while (timer_elapsed(start) < ticks)
		thread_yield();
}

static struct list sleep_list;

void thread_init(void)
{
    ASSERT(intr_get_level() == INTR_OFF);

    lock_init(&tid_lock);
    list_init(&ready_list);
    list_init(&all_list);
    // lab1 初始化休眠线程队列
    list_init(&sleep_list);

    /* Set up a thread structure for the running thread. */
    initial_thread = running_thread();
    init_thread(initial_thread, "main", PRI_DEFAULT);
    initial_thread->status = THREAD_RUNNING;
    initial_thread->tid = allocate_tid();
}

struct thread
{
    /* Owned by thread.c. */
    tid_t tid;                 /* Thread identifier. */
    enum thread_status status; /* Thread state. */
    char name[16];             /* Name (for debugging purposes). */
    uint8_t *stack;            /* Saved stack pointer. */
    int priority;              /* Priority. */
    struct list_elem allelem;  /* List element for all threads list. */

    int64_t wakeup_ticks; // lab1 添加苏醒时间刻

    /* Shared between thread.c and synch.c. */
    struct list_elem elem; /* List element. */

#ifdef USERPROG
    /* Owned by userprog/process.c. */
    uint32_t *pagedir; /* Page directory. */
#endif

    /* Owned by thread.c. */
    unsigned magic; /* Detects stack overflow. */
};

// 用来比较线程等待至目标时间刻的函数
bool thread_less_wakeup_tick(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
    struct thread *p_thread_a = list_entry(a, struct thread, elem);
    struct thread *p_thread_b = list_entry(b, struct thread, elem);
    return p_thread_a->wakeup_ticks < p_thread_b->wakeup_ticks;
}
// 这个记得在thread.h中声明，要在timer.c中用的
void thread_sleep(int64_t target_ticks)
{
    // 获取当前线程
    struct thread *cur = thread_current();;
    // 给当前线程添加苏醒时间刻
    cur->wakeup_ticks = target_ticks;
    // 按苏醒时间刻从小到大插入休眠队列
    list_insert_ordered(&sleep_list, &cur->elem, thread_less_wakeup_tick, NULL);
    // 当前线程进入阻塞态
    thread_block();
}

void timer_sleep(int64_t ticks)
{
    enum intr_level old_level;
    ASSERT(intr_get_level() == INTR_ON);
    old_level = intr_disable();

    thread_sleep(timer_ticks() + ticks);

    intr_set_level(old_level);
}

static void timer_interrupt(struct intr_frame *args UNUSED)
{
    ticks++;
    thread_tick();
    // lab1 将到达休眠时间将线程移出休眠队列
    thread_wakeup();
}

// 记得添加声明到thread.h中
void thread_wakeup(void)
{
    struct list_elem *p_elem;
    struct thread *p_thread;

    while (!list_empty(&sleep_list))
    {
        p_elem = list_front(&sleep_list);
        p_thread = list_entry(pe, struct thread, elem);
        // 休眠队列本身就是从小到大排序的，可以这样提前退出
        if (p_thread->wakeup_ticks > timer_ticks())
        {
            break;
        }
        // 移除出休眠队列
        list_remove(p_elem);
        // 让pt指向的线程退出阻塞态进入准备态
        thread_unblock(p_thread);
    }
}

// main函数，东西太多就不贴了
	// ...
    printf("Boot complete.\n");

    /* Run actions specified on kernel command line. */
    run_actions(argv);
    // 加上这句
    thread_print_stats();

    /* Finish up. */
    shutdown();
    thread_exit();
    // ...

// lab1 线程优先级比较函数
bool thread_more_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
    struct thread *p_thread_a = list_entry(a, struct thread, elem);
    struct thread *p_thread_b = list_entry(b, struct thread, elem);
    return p_thread_a->priority > p_thread_b->priority;
}

int thread_get_priority(void)
{
    return thread_current()->priority;
}

// lab1 当前线程是否持有锁
bool thread_is_holding_lock(void)
{
    struct thread *cur = thread_current();
    return !list_empty(&cur->lock_list);
}
void thread_set_priority(int new_priority)
{
    // 断言限制优先级范围
    ASSERT(PRI_MIN <= new_priority && new_priority <= PRI_MAX);

    struct thread *cur = thread_current();
    cur->base_priority = new_priority;
    if (!thread_is_holding_lock() || new_priority > cur->priority)
    {
        cur->priority = new_priority;
        thread_yield();
    }
}

void lock_acquire(struct lock *lock)
{
    ASSERT(lock != NULL);
    ASSERT(!intr_context());
    ASSERT(!lock_held_by_current_thread(lock));

    // lab1 高级调度不需要优先级借用
    if (!thread_mlfqs)
    {
        lock_acquire_priority_donation(lock);
    }

    sema_down(&lock->semaphore);
    lock->holder = thread_current();
}
void lock_release(struct lock *lock)
{
    ASSERT(lock != NULL);
    ASSERT(lock_held_by_current_thread(lock));

    // lab1 高级调度不需要优先级借用
    if (!thread_mlfqs)
    {
        lock_release_priority_donation(lock);
    }

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

// lab1 高级调度 niceness部分
#define NICENESS_MIN -20
#define NICENESS_DEFAULT 0
#define NICENESS_MAX 20

// lab1 高级调度 系统负载
extern fp thread_load_avg;

struct thread
{
    // ...
    int niceness;   // lab1 高级调度 线程的好心程度
    fp recent_cpu;  // lab1 高级调度 线程使用的cpu时间
	// ...
};

// lab1 高级调度 基于nice与recent_cpu计算线程优先级
void thread_mlfqs_refresh_priority(struct thread *t)
{
    if (t == idle_thread)
    {
        return;
    }
    fp f_priority = fp_convert_from(PRI_MAX);
    // 1/4 * recent_cpu
    fp f_a = fp_div_int(t->recent_cpu, 4);
    // 2*niceness
    fp f_b = fp_convert_from(t->niceness);
    f_b = fp_mul_int(f_b, 2);
    // PRI_MAX - 1/4 * recent_cpu - 2 * niceness
    fp f_ans = fp_sub_fp(f_priority, f_a);
    f_ans = fp_sub_fp(f_ans, f_b);

    t->priority = fp_toint_round(f_ans);
}

// lab1 高级调度 当前线程recent_cpu自增1
void thread_mlfqs_increase_recent_cpu(void)
{
    struct thread *cur = thread_current();
    if (cur == idle_thread)
    {
        return;
    }
    cur->recent_cpu = fp_add_int(cur->recent_cpu, 1);
}

// lab1 高级调度 计算线程最近cpu使用率
void thread_mlfqs_refresh_recent_cpu(struct thread *t)
{
    if (t == idle_thread)
    {
        return;
    }
    // (2 * load_avg) / (2 * laod_avg + 1) * recent_cpu
    fp f_a = fp_mul_int(thread_load_avg, 2);
    f_a = fp_div_fp(f_a, fp_add_int(f_a, 1));
    f_a = fp_mul_fp(f_a, t->recent_cpu);
    fp f_niceness = fp_convert_from(t->niceness);
    // (2 * load_avg) / (2 * laod_avg + 1) * recent_cpu + niceness
    t->recent_cpu = fp_add_fp(f_a, f_niceness);
}

// lab1 高级调度 计算系统使用负载
void thread_mlfqs_refresh_load_avg(void)
{
    // 59/60 * load_avg
    fp f_a = fp_convert_from(59);
    f_a = fp_div_int(f_a, 60);
    f_a = fp_mul_fp(f_a, thread_load_avg);
    // 1/60 * ready_threads
    fp f_b = fp_convert_from(1);
    f_b = fp_div_int(f_b, 60);
    f_b = fp_mul_int(f_b, list_size(&all_list) - list_size(&sleep_list) - 1);
    // 59/60 * load_avg + 1/60 * ready_threads
    thread_load_avg = fp_add_fp(f_a, f_b);
}

static void timer_interrupt(struct intr_frame *args UNUSED)
{
    ticks++;
    thread_tick();
    // lab1 将到达休眠时间将线程移出休眠队列
    thread_wakeup();

    // lab1 高级调度
    if (thread_mlfqs)
    {
	    // 每tick增加当前线程recent_cpu
        thread_mlfqs_increase_recent_cpu();
        if (timer_ticks() % TIMER_FREQ == 0)
        {
	        // 每1s重新计算系统负载和所有线程的recent_cpu
            thread_mlfqs_refresh_load_avg();
            thread_foreach(thread_mlfqs_refresh_recent_cpu, NULL);
        }
        if (timer_ticks() % 4 == 0)
        {
	        // 每4个tick重新计算所有线程的优先级
            thread_foreach(thread_mlfqs_refresh_priority, NULL);
        }
    }
}