Task 1: Alarm Clock

Reimplement timer_sleep(), defined in devices/timer.c.

Although a working implementation is provided, it busy waits, that is, it spins in a loop checking the current time and calling thread_yield() until enough time has gone by. Reimplement it to avoid busy waiting.

void timer_sleep (int64_t ticks);

This function suspends execution of the calling thread until time has advanced by at least x timer ticks. Unless the system is otherwise idle, the thread need not wake up after exactly x ticks. Just put it on the ready queue after they have waited for the right amount of time.

timer_sleep() is useful for threads that operate in real-time (e.g. for blinking the cursor once per second). The argument to timer_sleep() is expressed in timer ticks, not in milliseconds or any another unit. There are TIMER_FREQ timer ticks per second, where TIMER_FREQ is a macro defined in devices/timer.h. The default value is 100. We don't recommend changing this value, because any change is likely to cause many of the tests to fail.

Separate functions timer_msleep(), timer_usleep(), and timer_nsleep() do exist for sleeping a specific number of milliseconds, microseconds, or nanoseconds, respectively, but these will call timer_sleep() automatically when necessary. You do not need to modify them. The alarm clock implementation is not needed for later projects, although it could be useful for project 4.

코드 구현

#include "threads/thread.h"
#include <debug.h>
#include <stddef.h>
#include <random.h>
#include <stdio.h>
#include <string.h>
#include "threads/flags.h"
#include "threads/interrupt.h"
#include "threads/intr-stubs.h"
#include "threads/palloc.h"
#include "threads/synch.h"
#include "threads/vaddr.h"
#include "intrinsic.h"
#ifdef USERPROG
#include "userprog/process.h"
#endif

/* Random value for struct thread's `magic' member.
   Used to detect stack overflow.  See the big comment at the top
   of thread.h for details. */
#define THREAD_MAGIC 0xcd6abf4b

/* Random value for basic thread
   Do not modify this value. */
#define THREAD_BASIC 0xd42df210

/* List of processes in THREAD_READY state, that is, processes
   that are ready to run but not actually running. */
static struct list ready_list;

/* Idle thread. */
static struct thread *idle_thread;

/* Initial thread, the thread running init.c:main(). */
static struct thread *initial_thread;

/* Lock used by allocate_tid(). */
static struct lock tid_lock;

/* Thread destruction requests */
static struct list destruction_req;

/* Statistics. */
static long long idle_ticks;    /* # of timer ticks spent idle. */
static long long kernel_ticks;  /* # of timer ticks in kernel threads. */
static long long user_ticks;    /* # of timer ticks in user programs. */

/* Scheduling. */
#define TIME_SLICE 4            /* # of timer ticks to give each thread. */
static unsigned thread_ticks;   /* # of timer ticks since last yield. */

/* If false (default), use round-robin scheduler.
   If true, use multi-level feedback queue scheduler.
   Controlled by kernel command-line option "-o mlfqs". */
bool thread_mlfqs;

static void kernel_thread(thread_func *, void *aux);

static void idle(void *aux UNUSED);
static struct thread *next_thread_to_run(void);
static void init_thread(struct thread *, const char *name, int priority);
static void do_schedule(int status);
static void schedule(void);
static tid_t allocate_tid (void);

static struct list sleep_list;
static int64_t next_wakeup;

/* pintos-kaist/threads/thread.c */
void thread_sleep(int64_t ticks) {
	struct thread *curr;
	enum intr_level old_level;
	
	old_level = intr_disable();

	curr = thread_current();
	ASSERT (curr != idle_thread);
	update_next_wakeup(curr -> wakeup_time = ticks);

	list_push_back(&sleep_list, &curr -> elem);

	thread_block();

	intr_set_level(old_level);
}

/* pintos-kaist/threads/thread.c */
void thread_wakeup(int64_t wakeup_time) {
	struct list_elem *e;

	next_wakeup = INT64_MAX;
	e = list_begin(&sleep_list);

	while (e != list_end(&sleep_list)) {
		struct thread *t = list_entry(e, struct thread, elem);

		if (wakeup_time >= t -> wakeup_time) {
			e = list_remove(&t -> elem);
			thread_unblock(t);
		}

		else {
			e = list_next(e);
			update_next_wakeup(t -> wakeup_time);
		}
	}
}