#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/switch.h"
#include "threads/synch.h"
#include "threads/vaddr.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
/* List of processes in THREAD_READY state, that is, processes
that are ready to run but not actually running. */
static struct list ready_list;
/* List of all processes. Processes are added to this list
when they are first scheduled and removed when they exit. */
static struct list all_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;
/* Stack frame for kernel_thread(). */
struct kernel_thread_frame
{
void *eip; /* Return address. */
thread_func *function; /* Function to call. */
void *aux; /* Auxiliary data for function. */
};
/* 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 *running_thread (void);
static struct thread *next_thread_to_run (void);
static void init_thread (struct thread *, const char *name, int priority);
static bool is_thread (struct thread *) UNUSED;
static void *alloc_frame (struct thread *, size_t size);
static void schedule (void);
void thread_schedule_tail (struct thread *prev);
static tid_t allocate_tid (void);
/* Initializes the threading system by transforming the code
that's currently running into a thread. This can't work in
general and it is possible in this case only because loader.S
was careful to put the bottom of the stack at a page boundary.
Also initializes the run queue and the tid lock.
After calling this function, be sure to initialize the page
allocator before trying to create any threads with
thread_create().
It is not safe to call thread_current() until this function
finishes. */
void
thread_init (void)
{
ASSERT (intr_get_level () == INTR_OFF);
lock_init (&tid_lock);
list_init (&ready_list);
list_init (&all_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 ();
}
/* Starts preemptive thread scheduling by enabling interrupts.
Also creates the idle thread. */
void
thread_start (void)
{
/* Create the idle thread. */
struct semaphore idle_started;
sema_init (&idle_started, 0);
thread_create ("idle", PRI_MIN, idle, &idle_started);
/* Start preemptive thread scheduling. */
intr_enable ();
/* Wait for the idle thread to initialize idle_thread. */
sema_down (&idle_started);
}
/* Called by the timer interrupt handler at each timer tick.
Thus, this function runs in an external interrupt context. */
void
thread_tick (void)
{
struct thread *t = thread_current ();
/* Update statistics. */
if (t == idle_thread)
idle_ticks++;
#ifdef USERPROG
else if (t->pagedir != NULL)
user_ticks++;
#endif
else
kernel_ticks++;
/* Enforce preemption. */
if (++thread_ticks >= TIME_SLICE)
intr_yield_on_return ();
}
/* Prints thread statistics. */
void
thread_print_stats (void)
{
printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
idle_ticks, kernel_ticks, user_ticks);
}
/* Creates a new kernel thread named NAME with the given initial
PRIORITY, which executes FUNCTION passing AUX as the argument,
and adds it to the ready queue. Returns the thread identifier
for the new thread, or TID_ERROR if creation fails.
If thread_start() has been called, then the new thread may be
scheduled before thread_create() returns. It could even exit
before thread_create() returns. Contrariwise, the original
thread may run for any amount of time before the new thread is
scheduled. Use a semaphore or some other form of
synchronization if you need to ensure ordering.
The code provided sets the new thread's `priority' member to
PRIORITY, but no actual priority scheduling is implemented.
Priority scheduling is the goal of Problem 1-3. */
tid_t
thread_create (const char *name, int priority,
thread_func *function, void *aux)
{
struct thread *t;
struct kernel_thread_frame *kf;
struct switch_entry_frame *ef;
struct switch_threads_frame *sf;
tid_t tid;
enum intr_level old_level;
ASSERT (function != NULL);
/* Allocate thread. */
t = palloc_get_page (PAL_ZERO);
if (t == NULL)
return TID_ERROR;
/* Initialize thread. */
init_thread (t, name, priority);
tid = t->tid = allocate_tid ();
/* Prepare thread for first run by initializing its stack.
Do this atomically so intermediate values for the 'stack'
member cannot be observed. */
old_level = intr_disable ();
/* Stack frame for kernel_thread(). */
kf = alloc_frame (t, sizeof *kf);
kf->eip = NULL;
kf->function = function;
kf->aux = aux;
/* Stack frame for switch_entry(). */
ef = alloc_frame (t, sizeof *ef);
ef->eip = (void (*) (void)) kernel_thread;
/* Stack frame for switch_threads(). */
sf = alloc_frame (t, sizeof *sf);
sf->eip = switch_entry;
sf->ebp = 0;
intr_set_level (old_level);
/* Add to run queue. */
thread_unblock (t);
if (priority > thread_current ()->priority)
thread_yield();
return tid;
}
/* Puts the current thread to sleep. It will not be scheduled
again until awoken by thread_unblock().
This function must be called with interrupts turned off. It
is usually a better idea to use one of the synchronization
primitives in synch.h. */
void
thread_block (void)
{
ASSERT (!intr_context ());
ASSERT (intr_get_level () == INTR_OFF);
thread_current ()->status = THREAD_BLOCKED;
schedule ();
}
/* Transitions a blocked thread T to the ready-to-run state.
This is an error if T is not blocked. (Use thread_yield() to
make the running thread ready.)
This function does not preempt the running thread. This can
be important: if the caller had disabled interrupts itself,
it may expect that it can atomically unblock a thread and
update other data. */
void
thread_unblock (struct thread *t)
{
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
/*list_push_back (&ready_list, &t->elem);*/
list_insert_ordered(&ready_list, &t->elem, priority_less, NULL);
t->status = THREAD_READY;
intr_set_level (old_level);
}
/* Returns the name of the running thread. */
const char *
thread_name (void)
{
return thread_current ()->name;
}
/* Returns the running thread.
This is runnin