thread.c File Reference

#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"

Include dependency graph for thread.c:

Macros
#define	THREAD_MAGIC   0xcd6abf4b
#define	THREAD_BASIC   0xd42df210
#define	TIME_SLICE   4 /* # of timer ticks to give each thread. */
#define	is_thread(t)   ((t) != NULL && (t)->magic == THREAD_MAGIC)
#define	running_thread()   ((struct thread *) (pg_round_down (rrsp ())))

Functions
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)
int64_t	get_global_ticks (void)
void	set_global_ticks (int64_t ticks)
void	thread_awake (int64_t ticks)
void	thread_sleep (int64_t ticks)
bool	cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
void	thread_init (void)
void	thread_start (void)
void	thread_tick (void)
void	thread_print_stats (void)
tid_t	thread_create (const char *name, int priority, thread_func *function, void *aux)
void	thread_block (void)
void	thread_unblock (struct thread *t)
const char *	thread_name (void)
struct thread *	thread_current (void)
tid_t	thread_tid (void)
void	thread_exit (void)
void	thread_yield (void)
void	thread_set_priority (int new_priority)
int	thread_get_priority (void)
void	thread_set_nice (int nice UNUSED)
int	thread_get_nice (void)
int	thread_get_load_avg (void)
int	thread_get_recent_cpu (void)
static void	idle (void *idle_started_ UNUSED)
void	do_iret (struct intr_frame *tf)
static void	thread_launch (struct thread *th)

Variables
static struct list	ready_list
static struct list	sleep_list
static struct thread *	idle_thread
static struct thread *	initial_thread
static struct lock	tid_lock
static struct list	destruction_req
static int64_t	global_ticks = INT64_MAX
static long long	idle_ticks
static long long	kernel_ticks
static long long	user_ticks
static unsigned	thread_ticks
bool	thread_mlfqs
static uint64_t	gdt [3] = { 0, 0x00af9a000000ffff, 0x00cf92000000ffff }

Macro Definition Documentation

is_thread

#define is_thread

(

t

)

((t) != NULL && (t)->magic == THREAD_MAGIC)

running_thread

#define running_thread

(

)

((struct thread *) (pg_round_down (rrsp ())))

THREAD_BASIC

#define THREAD_BASIC   0xd42df210

THREAD_MAGIC

#define THREAD_MAGIC   0xcd6abf4b

TIME_SLICE

#define TIME_SLICE   4 /* # of timer ticks to give each thread. */

Function Documentation

allocate_tid()

static tid_t allocate_tid ( void  )

static

                    {
    static tid_t next_tid = 1;
    tid_t tid;
 
    lock_acquire (&tid_lock);
    tid = next_tid++;
    lock_release (&tid_lock);
 
    return tid;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cmp_priority()

bool cmp_priority	(	const struct list_elem *	a,
		const struct list_elem *	b,
		void *aux	UNUSED
	)

                                                                                      {
    return list_entry(a, struct thread, elem) -> priority \
        > list_entry(b, struct thread, elem) -> priority ? \
        1 : 0; 
}

Here is the caller graph for this function:

do_iret()

void do_iret

(

struct intr_frame *

tf

)

                                {
    __asm __volatile(
            "movq %0, %%rsp\n"
            "movq 0(%%rsp),%%r15\n"
            "movq 8(%%rsp),%%r14\n"
            "movq 16(%%rsp),%%r13\n"
            "movq 24(%%rsp),%%r12\n"
            "movq 32(%%rsp),%%r11\n"
            "movq 40(%%rsp),%%r10\n"
            "movq 48(%%rsp),%%r9\n"
            "movq 56(%%rsp),%%r8\n"
            "movq 64(%%rsp),%%rsi\n"
            "movq 72(%%rsp),%%rdi\n"
            "movq 80(%%rsp),%%rbp\n"
            "movq 88(%%rsp),%%rdx\n"
            "movq 96(%%rsp),%%rcx\n"
            "movq 104(%%rsp),%%rbx\n"
            "movq 112(%%rsp),%%rax\n"
            "addq $120,%%rsp\n"
            "movw 8(%%rsp),%%ds\n"
            "movw (%%rsp),%%es\n"
            "addq $32, %%rsp\n"
            "iretq"
            : : "g" ((uint64_t) tf) : "memory");
}

Here is the call graph for this function:

Here is the caller graph for this function:

do_schedule()

static void do_schedule ( int  status )

static

                        {
    ASSERT (intr_get_level () == INTR_OFF);
    ASSERT (thread_current()->status == THREAD_RUNNING);
    while (!list_empty (&destruction_req)) { // 좀비 스레드 제거
        struct thread *victim =
            list_entry (list_pop_front (&destruction_req), struct thread, elem);
        palloc_free_page(victim);
    }
    thread_current ()->status = status;
    schedule ();
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_global_ticks()

int64_t get_global_ticks

(

void

)

                  {
    return global_ticks;
}

Here is the caller graph for this function:

idle() [1/2]

static void idle ( void *aux  UNUSED )

static

Here is the caller graph for this function:

idle() [2/2]

static void idle ( void *idle_started_  UNUSED )

static

                                  {
    struct semaphore *idle_started = idle_started_;
 
    idle_thread = thread_current ();
    sema_up (idle_started);
 
    for (;;) {
        /* Let someone else run. */
        intr_disable ();
        thread_block ();
 
        /* Re-enable interrupts and wait for the next one.
 
           The `sti' instruction disables interrupts until the
           completion of the next instruction, so these two
           instructions are executed atomically.  This atomicity is
           important; otherwise, an interrupt could be handled
           between re-enabling interrupts and waiting for the next
           one to occur, wasting as much as one clock tick worth of
           time.
 
           See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
           7.11.1 "HLT Instruction". */
        asm volatile ("sti; hlt" : : : "memory");
    }
}

Here is the call graph for this function:

init_thread()

static void init_thread ( struct thread *  t, const char *  name, int  priority  )

static

                                                               {
    ASSERT (t != NULL);
    ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
    ASSERT (name != NULL);
 
    memset (t, 0, sizeof *t);
    t->status = THREAD_BLOCKED;
    strlcpy (t->name, name, sizeof t->name);
    t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
    t->priority = priority;
    /*------------------------- [P1] Priority Scheduling --------------------------*/
    t->priority_base = priority; // 초기 priority 상태를 확인한다.
    t->wait_on_lock = NULL; // 스레드 생성시에는 기다리는 락이 없으니 NULL값으로 설정한다.
    list_init (&t->donations); // donations 초기화
    t->magic = THREAD_MAGIC;
 
/*------------------------- [P2] System Call --------------------------*/
    t->exit_status = 0;
    t->running = NULL;
 
    /* 자식 리스트 및 세마포어 초기화 */
    list_init(&t->child_list);
    sema_init(&t->wait_sema,0);
    sema_init(&t->fork_sema,0);
    sema_init(&t->free_sema,0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

kernel_thread()

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

static

                                                 {
    ASSERT (function != NULL);
 
    intr_enable ();       /* The scheduler runs with interrupts off. */
    function (aux);       /* Execute the thread function. */
    thread_exit ();       /* If function() returns, kill the thread. */
}

Here is the call graph for this function:

Here is the caller graph for this function:

next_thread_to_run()

static struct thread * next_thread_to_run ( void  )

static

                          {
    if (list_empty (&ready_list)){
        return idle_thread;
    }
    else
        return list_entry (list_pop_front (&ready_list), struct thread, elem);
}

Here is the call graph for this function:

Here is the caller graph for this function:

schedule()

static void schedule ( void  )

static

                            {
    struct thread *curr = running_thread ();
    struct thread *next = next_thread_to_run ();
 
    ASSERT (intr_get_level () == INTR_OFF);
    ASSERT (curr->status != THREAD_RUNNING);
    ASSERT (is_thread (next)); // 다음 스레드로 컨텍스트 스위칭
    /* Mark us as running. */
    next->status = THREAD_RUNNING;
 
    /* Start new time slice. */
    thread_ticks = 0;
 
#ifdef USERPROG
    /* Activate the new address space. */
    process_activate (next);
#endif
 
    if (curr != next) {
        /* If the thread we switched from is dying, destroy its struct
           thread. This must happen late so that thread_exit() doesn't
           pull out the rug under itself.
           We just queuing the page free reqeust here because the page is
           currently used bye the stack.
           The real destruction logic will be called at the beginning of the
           schedule(). */
        if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
            ASSERT (curr != next);
            list_push_back (&destruction_req, &curr->elem);
        }
 
        /* Before switching the thread, we first save the information
         * of current running. */
        thread_launch (next);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

set_global_ticks()

void set_global_ticks

(

int64_t

ticks

)

                               {
    if (ticks < global_ticks) {
        global_ticks = ticks;
    }
}

Here is the caller graph for this function:

thread_awake()

void thread_awake

(

int64_t

ticks

)

                           {
    struct list_elem *curr = list_begin(&sleep_list);
    set_global_ticks(INT64_MAX); // 기존 글로벌 틱으로 비교하면 초기화되지 않음 
    struct thread *curr_thread;
    while (curr != list_end(&sleep_list)){ // 전체 순회
        curr_thread = list_entry(curr, struct thread, elem);
        if (curr_thread -> wakeup_tick <= ticks) { 
            curr = list_remove(curr); // curr을 슬립 리스트에서 뻄
            thread_unblock(curr_thread); // curr을 레디 상태로 만듦(unblocked)
        } else {
            set_global_ticks(curr_thread -> wakeup_tick);
            // 슬립 리스트에서 현재 깨어나야하는 시간이 ticks 보다 클때, 디음 루틴을 위해 글로벌 틱을 재설정한다.
            curr = curr -> next;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_block()

void thread_block

(

void

)

                    {
    ASSERT (!intr_context ());
    ASSERT (intr_get_level () == INTR_OFF);
    thread_current ()->status = THREAD_BLOCKED;
    schedule ();
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_create()

tid_t thread_create	(	const char *	name,
		int	priority,
		thread_func *	function,
		void *	aux
	)

                                                                                 {
    struct thread *t;
    tid_t tid;
 
    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 ();
    
    /*------------------------- [P2] System Call --------------------------*/
    t->fdt = palloc_get_multiple(PAL_ZERO, FDT_PAGES);
    if (t->fdt == NULL) {
        return TID_ERROR;
    }
    t->next_fd = 2; // 0 : stdin, 1 : stdout
    t->fdt[0] = 1; // STDIN_FILENO -> dummy value
    t->fdt[1] = 2; // STDOUT_FILENO -> dummy value
 
/*------------------------- [P2] System Call - Thread --------------------------*/
    /* 현재 스레드의 자식 리스트에 새로 생성한 스레드 추가 */
    struct thread *curr = thread_current();
    list_push_back(&curr->child_list,&t->child_elem);
 
    /* Call the kernel_thread if it scheduled.
     * Note) rdi is 1st argument, and rsi is 2nd argument. */
    t->tf.rip = (uintptr_t) kernel_thread;
    t->tf.R.rdi = (uint64_t) function;
    t->tf.R.rsi = (uint64_t) aux;
    t->tf.ds = SEL_KDSEG;
    t->tf.es = SEL_KDSEG;
    t->tf.ss = SEL_KDSEG;
    t->tf.cs = SEL_KCSEG;
    t->tf.eflags = FLAG_IF;
 
    /*------------------------- [P1] Priority Scheduling --------------------------*/
    /* Add to run queue. */
    thread_unblock (t); // ready_list 에 새로 넣은 스레드 
 
    if (thread_get_priority() < priority) { //1. 현재 실행중인 스레드와 새로 추가하려는 스레드 비교
        if (intr_context())
            intr_yield_on_return();
        else
            thread_yield(); //2. 만약 새로 추가하려는 스레드가 현재 실행중인 스레드보다 우선순위가 높으면 CPU를 선점한다.
    }
    return tid;
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_current()

struct thread * thread_current

(

void

)

                      {
    struct thread *t = running_thread ();
 
    /* Make sure T is really a thread.
       If either of these assertions fire, then your thread may
       have overflowed its stack.  Each thread has less than 4 kB
       of stack, so a few big automatic arrays or moderate
       recursion can cause stack overflow. */
    ASSERT (is_thread (t));
    ASSERT (t->status == THREAD_RUNNING);
 
    return t;
}

thread_exit()

void thread_exit

(

void

)

                   {
    ASSERT (!intr_context ());
    struct thread *curr = thread_current (); // 현재 스레드의 포인터
 
#ifdef USERPROG
    process_exit ();
#endif
 
    /* Just set our status to dying and schedule another process.
       We will be destroyed during the call to schedule_tail(). */
    intr_disable ();
    do_schedule (THREAD_DYING);
    NOT_REACHED ();
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_get_load_avg()

int thread_get_load_avg

(

void

)

                           {
    /* TODO: Your implementation goes here */
    return 0;
}

thread_get_nice()

int thread_get_nice

(

void

)

                       {
    /* TODO: Your implementation goes here */
    return 0;
}

thread_get_priority()

int thread_get_priority

(

void

)

                           {
    return thread_current ()->priority;
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_get_recent_cpu()

int thread_get_recent_cpu

(

void

)

                             {
    /* TODO: Your implementation goes here */
    return 0;
}

thread_init()

void thread_init

(

void

)

                   {
    printf("thread init\n");
    ASSERT (intr_get_level () == INTR_OFF);
 
    /* Reload the temporal gdt for the kernel
     * This gdt does not include the user context.
     * The kernel will rebuild the gdt with user context, in gdt_init (). */
    struct desc_ptr gdt_ds = {
        .size = sizeof (gdt) - 1,
        .address = (uint64_t) gdt
    };
    lgdt (&gdt_ds);
 
    /*------------------------- [P1] Alarm Clock --------------------------*/
    /* Init the globla thread context */
    lock_init (&tid_lock);
    list_init (&ready_list);
    list_init (&sleep_list); // sleep_list를 초기화 한다.
    list_init (&destruction_req);
 
    /* 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 ();
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_launch()

static void thread_launch ( struct thread *  th )

static

                                  {
    uint64_t tf_cur = (uint64_t) &running_thread ()->tf;
    uint64_t tf = (uint64_t) &th->tf;
    ASSERT (intr_get_level () == INTR_OFF);
 
    /* The main switching logic.
     * We first restore the whole execution context into the intr_frame
     * and then switching to the next thread by calling do_iret.
     * Note that, we SHOULD NOT use any stack from here
     * until switching is done. */
    __asm __volatile (
            /* Store registers that will be used. */
            "push %%rax\n"
            "push %%rbx\n"
            "push %%rcx\n"
            /* Fetch input once */
            "movq %0, %%rax\n"
            "movq %1, %%rcx\n"
            "movq %%r15, 0(%%rax)\n"
            "movq %%r14, 8(%%rax)\n"
            "movq %%r13, 16(%%rax)\n"
            "movq %%r12, 24(%%rax)\n"
            "movq %%r11, 32(%%rax)\n"
            "movq %%r10, 40(%%rax)\n"
            "movq %%r9, 48(%%rax)\n"
            "movq %%r8, 56(%%rax)\n"
            "movq %%rsi, 64(%%rax)\n"
            "movq %%rdi, 72(%%rax)\n"
            "movq %%rbp, 80(%%rax)\n"
            "movq %%rdx, 88(%%rax)\n"
            "pop %%rbx\n"              // Saved rcx
            "movq %%rbx, 96(%%rax)\n"
            "pop %%rbx\n"              // Saved rbx
            "movq %%rbx, 104(%%rax)\n"
            "pop %%rbx\n"              // Saved rax
            "movq %%rbx, 112(%%rax)\n"
            "addq $120, %%rax\n"
            "movw %%es, (%%rax)\n"
            "movw %%ds, 8(%%rax)\n"
            "addq $32, %%rax\n"
            "call __next\n"         // read the current rip.
            "__next:\n"
            "pop %%rbx\n"
            "addq $(out_iret -  __next), %%rbx\n"
            "movq %%rbx, 0(%%rax)\n" // rip
            "movw %%cs, 8(%%rax)\n"  // cs
            "pushfq\n"
            "popq %%rbx\n"
            "mov %%rbx, 16(%%rax)\n" // eflags
            "mov %%rsp, 24(%%rax)\n" // rsp
            "movw %%ss, 32(%%rax)\n"
            "mov %%rcx, %%rdi\n"
            "call do_iret\n"
            "out_iret:\n"
            : : "g"(tf_cur), "g" (tf) : "memory"
            );
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_name()

const char * thread_name

(

void

)

                   {
    return thread_current ()->name;
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_print_stats()

void thread_print_stats

(

void

)

                          {
    printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
            idle_ticks, kernel_ticks, user_ticks);
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_set_nice()

void thread_set_nice

(

int nice

UNUSED

)

                                  {
    /* TODO: Your implementation goes here */
}

thread_set_priority()

void thread_set_priority

(

int

new_priority

)

                                       {
    thread_current ()->priority_base = new_priority;
    refresh_priority ();
 
    if (thread_get_priority () < list_entry (list_begin (&ready_list), struct thread, elem)->priority) {
        if (intr_context())
            intr_yield_on_return();
        else
            thread_yield ();
    }
}

Here is the call graph for this function:

thread_sleep()

void thread_sleep

(

int64_t

ticks

)

                           { // ticks : 해당 스레드가 깨어나야 할 절대적인 시간 (eg. 12:05)
    struct thread *curr = thread_current (); // 현재 스레드의 포인터
    enum intr_level old_level; // 이전 상태
 
    ASSERT (!intr_context ());
 
    old_level = intr_disable (); // 인터럽터를 비활성화 시킨다.
    if (curr != idle_thread) // 현재 스레드가 유휴 스레드가 아니면 sleep_list의 맨 뒤로 넣는다.
    {
        curr -> wakeup_tick = ticks; // 깨워야할 시간으로 새로 받은 인자를 넣는다.
        list_push_back (&sleep_list, &curr->elem); // 현재 스레드를 레디리스트의 맨 뒤로 삽입한다.
        // curr -> status = THREAD_BLOCKED; 
 
        set_global_ticks(ticks);
    }
    
    /* 스레드의 상태를 BLOCKED로 전환하고 컨텍스트 스위치(schedule())를 수행한다. */
    thread_block();
    // do_schedule (THREAD_BLOCKED); (= thread_block)
    intr_set_level (old_level); // 이후 다시 인터럽터를 활성화한다.
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_start()

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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_tick()

void thread_tick

(

void

)

                   {
    struct thread *t = thread_current ();
 
    /* Update statistics. */
    if (t == idle_thread)
        idle_ticks++;
#ifdef USERPROG
    else if (t->pml4 != NULL)
        user_ticks++;
#endif
    else
        kernel_ticks++;
 
    /* Enforce preemption. */
    if (++thread_ticks >= TIME_SLICE)
        intr_yield_on_return ();
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_tid()

tid_t thread_tid

(

void

)

                  {
    return thread_current ()->tid;
}

Here is the call graph for this function:

thread_unblock()

void thread_unblock

(

struct thread *

t

)

                                  {
    enum intr_level old_level;
 
    ASSERT (is_thread (t));
 
    old_level = intr_disable ();
    ASSERT (t->status == THREAD_BLOCKED);
    /*------------------------- [P1] Priority Scheduling --------------------------*/
    /* origin code
    list_push_back (&ready_list, &t->elem);
    */
    list_insert_ordered(&ready_list, &t -> elem, cmp_priority, NULL); // 정렬된 상태로 스레드가 삽입되도록 한다.
    t->status = THREAD_READY;
    intr_set_level (old_level);
}

Here is the call graph for this function:

Here is the caller graph for this function:

thread_yield()

void thread_yield

(

void

)

                    {
    struct thread *curr = thread_current (); // 현재 스레드의 포인터
    enum intr_level old_level;
 
    ASSERT (!intr_context ());
 
    old_level = intr_disable (); // 인터럽터를 비활성화한다.
    if (curr != idle_thread) { // 현재 스레드가 유휴 스레드가 아니면 리스트의 맨 뒤로 넣는다.
        /*------------------------- [P1] Alarm Clock --------------------------*/
        /* origin code
        list_push_back (&ready_list, &curr->elem); // 현재 스레드를 레디리스트의 맨 뒤로 삽입한다.
        */
        /*------------------------- [P1] Priority Scheduling --------------------------*/
        list_insert_ordered(&ready_list, &curr -> elem, cmp_priority, NULL); // 정렬된 상태로 스레드가 삽입되도록 한다.
    }
    do_schedule (THREAD_READY); // ready 상태로 전환하고 컨텍스트 스위칭을 한다.
    intr_set_level (old_level); // 이후 다시 이전 상태로 되돌린다.
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

destruction_req

struct list destruction_req

static

gdt

uint64_t gdt[3] = { 0, 0x00af9a000000ffff, 0x00cf92000000ffff }

static

global_ticks

int64_t global_ticks = INT64_MAX

static

idle_thread

struct thread* idle_thread

static

idle_ticks

long long idle_ticks

static

initial_thread

struct thread* initial_thread

static

kernel_ticks

long long kernel_ticks

static

ready_list

struct list ready_list

static

sleep_list

struct list sleep_list

static

thread_mlfqs

bool thread_mlfqs

thread_ticks

unsigned thread_ticks

static

tid_lock

struct lock tid_lock

static

user_ticks

long long user_ticks

static