[CS] PintOS - Thread(Alarm Clock and Priority Scheduling) 구현

Alarm Clock

---

💡 요구사항

timer_sleep() , defined in devices/timer.c

• 현재 작동하는 구현 방식은 busy wating 방식, busy waitng 방식을 개선한다.

 

기존 Busy Waiting 방식

현재 시간을 확인하고, thread_yield() 함수를 호출하며 일정 시간이 지날 때 까지 while 루프를 돈다.

/* Suspends execution for approximately TICKS timer ticks. */
void timer_sleep (int64_t ticks) {
    int64_t start = timer_ticks (); // 현재 시간 구하기

    ASSERT (intr_get_level () == INTR_ON); 
    while (timer_elapsed (start) < ticks)
        thread_yield (); 
}

• timer_ticks() - OS가 부팅된 이후 타이머 틱 수를 반환.
• intr_get_level() - 현재 인터럽트 상태 반환.
• timer_elasped() - start 이후 경과된 타이머 틱 수를 반환.
• thread_yield() - 현재 스레드의 cpu 점유 양보.

busy waiting 방식

 

thread_yield 함수

현재 CPU점유를 다른 스레드에게 양보하고, thread를 ready_list 제일 뒤로 이동시킨다.

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
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)
        list_push_back (&ready_list, &curr->elem);
    do_schedule (THREAD_READY);
    intr_set_level (old_level);
}

• thread_current() - 현재 스레드를 반환.
• intr_disable() - 인터럽트의 상태를 disabled로 변경하고 이전 인터럽트 상태를 반환.
• intr_set_level() - 파라미터로 넘겨진 인터럽트에 상태에 따라 인터럽트 상태를 변경하고 이전 인터럽트 상태 반환.
• list_push_back() - 현재 스레드를 read_list 마지막에 삽입한다.

 

do_schedule 함수

현재 스레드의 상태를 인자로 받은 status 로 수정한 후, 실행할 다른 스레드를 찾아 해당 스레드로 전환

/* Schedules a new process. At entry, interrupts must be off.
 * This function modify current thread's status to status and then
 * finds another thread to run and switches to it.
 * It's not safe to call printf() in the schedule(). */
static void
do_schedule(int status) {
    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 ();
}

static void
schedule (void) {
    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;

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

 

Sleep / Wake up 방식

💡 목표

sleep()를 호출하여 스레드를 blocked state로 만들고, 일정 시간 후에 wakeup()을 호출하여 스레드를 ready state로 만든다.

 

프로세스 상태 전이

 

busy waiting 방식을 개선한 sleep & wakeup 방식

 

구현 방식

1. Sleep Queue define하고(어디서?) initialize하기 (언제?)
2. 커널(timer_interrupt())는 스레드가 wake up 할 시간을 체크해야 한다.
3. 각각의 스레드가 the time to wakup이 필요하기 때문에 thread struct 변경 필요
4. “tick” (global variable) ⇒ sleep_list 탐색시간을 줄여줄 수 있다. (스레드의 local tick의 minmum값과 비교)
5. sleep ⇒ 만일 timer_sleep()이 호출되었을 때, 만약 wakeup 시간이 되지 않았다면 현재의 스레드를 sleep_list에 넣는다.
6. wakeup ⇒ timer interrupt가 발생 시 어떤 스레드가 wakeup할지 결정한다. wakeup할 스레드는 sleep_list에서 제거하고 ready_list에 넣는다.

 

💡 design tips for modularization

• thread state를 blocked로 변경하고 sleep_list에 삽입 후 기다리는 함수
• sleep_list에서 wakeup할 thread를 찾아 깨우는하는 함수
• thread의 minimum value를 저장하는 함수
• thread의 minimum value를 리턴하는 함수

 

Priority Scheduling and Synchronization

---

구현 방식

1. 현재 실행 중인 스레드보다 우선 순위가 높은 스레드가 ready_list에 추가되면, 현재 스레드는 즉시 CPU를 다른 스레드에 양보한다.
2. 스레드가 lock, semaphore, condition variable에 의해 wating 상태가 되면, 우선순위가 가장 높은 대기 스레드가 먼저 깨어 나야한다.
3. 스레드는 언제든지 자신의 우선 순위를 높이거나 낮출 수 있지만, 더 이상 가장 높은 우선 순위를 가지지 않으면 CPU를 양보해야 한다.
4. 우선순위는 PRI_MIN(=0) 부터 PRI_MAX(=63)까지의 범위를 가지며 숫자가 클수록 우선순위가 높다.
5. thread_create() 함수로 thread를 생성할 때 인자로 초기 우선순위를 전달(기본 값으로 PRI_DEFAULT(=31))

 

구현 사항

1. Priority Donation

낮은 우선순위의 스레드에게 자신의 우선순위를 기부한다.

💡 우선순위가 높은 쓰레드가 우선순위 낮은 스레드를 기다리는 현상인 'priority inversion'을 방지하기 위한 방법

 

priority inversion

 

priority donation

 

고려사항

multiple donation - 여러 우선 순위가 단일 스레드에 기부된다.

lock을 기다리는 스레드들 중 스레드를 선택할 경우, '우선순위가 높은 스레드'를 선택해야 한다.

 

 

nested donation - T4가 T3가 보유하고 있는 잠금을 기다리고 있고, T3가 T2가 보유하고 있는 잠금을 기다리고 있고, T2가 T1이 보유하고 있는 잠금을 기다리고 있다면 T1, T2, T3 모두 T4의 우선순위로 높아져야 한다. 필요한 경우 중첩된 우선순위 기부의 깊이에 대해 (8레벨)과 같은 제한을 부과할 수 있다.

 

 

2. thread_set_priority 함수

현재 스레드의 우선순위를 파라미터로 받은 새로운 우선순위로 변경하는 함수

void thread_set_priority (int new_priority);

 

3. thread_get_priority 함수

현재 스레드의 우선순위를 반환하는 함수

int thread_get_priority (void);

 

function to modify

---

• static void init_thread(struct thread *t, const char *name, int priority)
  • Initializes data structure for priority donation.
• void lock_acquire(struct lock *lock)
  • If the lock is not available, store address of the lock.
  • Store the current priority and maintain donated threads on list (multiple donation).
  • Donate priority.
• void lock_release(struct lock *lock)
  • When the lock is released, remove the thread that holds the lock on donation list and set priority properly.
• void thread_set_priority(int new_priority)
  • Set priority considering the donation

 

• 우선순위를 무시하고 waiters list에 삽입대는 순서대로 lock을 획득

• Semaphore를 요청 할때 대기 리스트를 우선순위로 정렬
• sema_down() 함수, cond_wait() 함수 수정

 

 

Sturct 정리

---

Thread

struct thread {
    /* Owned by thread.c. */
    tid_t tid;                          /* Thread identifier. */
    enum thread_status status;          /* Thread state. */
    char name[16];                      /* Name (for debugging purposes). */
    int priority;                       /* Priority. */
    int init_priority;                    /* Init Priority. */
    int64_t wakeup_tick;                 /* 스레드가 꺠어나야할 tick */
    /* Shared between thread.c and synch.c. */
    struct list_elem elem;              /* List element. */
    struct lock *wait_on_lock;          /* 해당 스레드가 대기하는 lock*/
    struct list donations;              /* 해당 스레드의 priority donation 정보 */
    struct list_elem d_elem;            /* donation element */
#ifdef USERPROG
    /* Owned by userprog/process.c. */
    uint64_t *pml4;                     /* Page map level 4 */
#endif
#ifdef VM
    /* Table for whole virtual memory owned by thread. */
    struct supplemental_page_table spt;
#endif

    /* Owned by thread.c. */
    struct intr_frame tf;               /* Information for switching */
    unsigned magic;                     /* Detects stack overflow. */
};

 

List

/* List. */
struct list {
    struct list_elem head;      /* List head. */
    struct list_elem tail;      /* List tail. */
};

struct list_elem {
    struct list_elem *prev;     /* Previous list element. */
    struct list_elem *next;     /* Next list element. */
};

 

Synchronization

/* A counting semaphore. */
struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

/* Lock. */
struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

/* Condition variable. */
struct condition {
	struct list waiters;        /* List of waiting threads. */
};