Project 1. Alarm Clock 구현

➡️ 과제 설명(Gitbook)

Alarm Clock

🎯 Goal
- 'devices/timer.c' 에 정의된 'timer_sleep()' 을 재구현하라.
- busy wait(현재 방식)를 피하는 방식으로 다시 구현하라

• 이미 작동되는 구현 형태가 존재하지만 해당 형태는 busy waits 이다.
• 많은 시간이 흐른 뒤에야 현재 시간을 체킹하고 thread_yield() 를 호출한다.

 

 

---

void timer_sleep(int64_t ticks);

• 최소 x 시간 타이머 tick만큼 진행될 때까지 스레드 호출을 중단한다.
• 시스템이 유휴상태가 아닌 한 스레드는 정확히 x 타이머 tick 후에 깨어날 필요가 없다.
• 적절한 시간 동안 대기한 후, 레디 큐에 넣으면 된다.

 

 

---

• timer_sleep 은 실시간으로 작동하는 스레드이다.
  ex. 초당 한 번의 커서 깜박임
• timer_sleep 의 인자는 밀리초와 같은 단위가 아닌 타이머 틱이다.

 

• TIMER_FREQ : 초당 타이머 틱 (by. devices/timer.h) → 기본값 100
  ⚠️ 값 변경하지 말기!!!

 

• 추가 함수
  • timer_msleep(), timer_usleep(), timer_nsleep() : 특정한 시간동안의 sleep을 위해 존재한다. (milli sec, micro sec, nano sec)
  • But, timer_sleep() 에 의해서 필요할 때 자동으로 호출된다.
    ⚠️ 값 변경할 필요 없음!
  • 프로젝트 4에는 유용할 수도 있다.

 

 

---

➡️ 구현

 

📌 코드부분은 한글 주석을 달아놓은 부분이 추가된 부분입니다!

 

🎯 Goal

• Functions to modify
  • thread_init : ‘sleep_list’를 초기화하는 코드를 추가한다.
  • timer_sleep : ‘sleep_list’에 스레드를 삽입하는 코드를 추가한다.
  • timer_interrupt : 몇몇 스레드에서 스레드를 깨워야하는지 확인한다.
• Functions to add
  • get_global_ticks : ‘global_ticks’의 값을 가져온다.
  • set_global_ticks : ‘global_ticks’의 값을 설정한다.

 

 

---

• Modified files
  • include/threads/thread.h
  • threads/thread.c
  • devices/timer.c

 

 

---

📝 Functions List

1. thread_init
2. timer_sleep
3. thread_sleep
4. get_global_ticks
5. set_global_ticks
6. timer_interrupt
7. thread_awake

 

 

---

1. thread_init

 

<구현 사항>

1. ‘sleep_list’를 초기화한다.
   (’ready_list’의 반대)
2. thread.h
   - 스레드 구조체에 깨어나야하는 시간을 의미하는 wakeup_tick 멤버를 추가한다.
   → Kaist PintOS 영상에서 얘기하는 ‘local tick’을 의미한다.

 

1. thread_init

• threads/thread.c

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

    /* 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 ();
}

 

• threads/thread.h

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. */
    int64_t wakeup_tick; // 해당 스레드를 깨워야하는 시간(local ticks)

    /* Shared between thread.c and synch.c. */
    struct list_elem elem;              /* List 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. */
};

• 생성된 스레드는 스택의 아래 쪽에 배치된다.
• 실행 큐와 해당 스레드에 대한 락 상태를 초기화 한다.

 

• 해당 함수를 호출하고 나서의 작업으로, tread_create() 함수를 이용해 스레드를 생성하기 전에 페이지 할당을 먼저해야한다.
• ⚠️ 해당 함수가 종료되기 전에 thread_current() 를 호출하는 건 안전하지 않다.

 

• thread 구조체

1. elem 멤버의 목적
   1. 실행 중 관리되는 리스트의 요소
   2. 세마포 대기 리스트의 요소
2. struct list_elem

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

🙋‍♂️ 해당 스레드에 대한 연결 관계를 포함하기 위한 이중 연결 리스트를 표현하기 위해 사용한다고 생각하자!

 

---

2. timer_sleep

<구현 사항>

1. global ticks(’sleep_list’에서의 min 값)를 선언해야한다.

• timer.c 와 thread.c 둘 다에서 써야하므로 전역으로 구현해야한다.
  1. timer.c에는 "threads/thread.h" 가 포함되어 있으므로 thread.c 에 global ticks를 구현하고 getter, setter로 불러온다.
  2. ⭐ thread.h에 선언해주는 거 잊지 말기!

 

🏃‍♂️ Try

• global_ticks를 서로 다른 소스 파일 timer.c와 thread.c에서 쓰기 위해 처음엔 직관적으로 extern으로 구현하는 아이디어를 생각했다.
• But, “한양대 ver. PintOS” 자료와 Project 3 부터의 다른 팀과의 호환성을 위해 일반적인 방법을 적용했다. → timer가 이후 프로젝트에 사용되지는 않지만 코드를 합치는 과정에서 변경사항이 많으면 불편할 거라 판단

 

2. timer_sleep

 

• devices/timer.c

// 현재 실행 중인 스레드를 ticks 만큼의 시간이 지나기 이전까지 해당 스레드의 호출을 중단한다.
void
timer_sleep (int64_t ticks) { // ticks 시간 만큼 뒤에 꺠어난다.(상대 시간 (eg. 5분))
    int64_t start = timer_ticks (); // 현재 시간(프로그램 부트 이후 시간 (eg. 12시))

    ASSERT (intr_get_level () == INTR_ON);
    /* 기존 코드 : busy waiting 방식
        while (timer_elapsed (start) < ticks)
            thread_yield (); 
    */
    if (timer_elapsed (start) < ticks) // 현재 시간부터의 경과 시간이 ticks 보다 작으면(깨울 때가 아님)
        thread_sleep(start + ticks); // 해당 스레드를 sleep(BLOCKED)시킨다.
        // ↳ 해당 스레드가 깨어나야할 절대 시간인 (start + ticks)를 인자로 넘긴다.
}

⭐ thread_sleep 의 인자로는 새로 만든 깨어나야 할 시간이 들어간다.

 

3. thread_sleep

• threads/thread.c

// 해당 스레드를 sleep시킨다.
// ↳ 스레드 상태를 blocked로 만들고 sleep_list에 삽입, 새 스레드를 running상태로 만든다.(컨텍스트 스위치)
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); // 이후 다시 인터럽터를 활성화한다.
}

 

3-1. thread_block() 🆚 do_schedule() ?

• ‘thread_block’은 현재 스레드를 BLOCKED 상태로 만든다.
• ‘do_schedule’은 현재 스레드를 해당 함수의 인자로 받은 상태로 만든다.
  • do_schedule에는 ‘dying thread’를 제거해주는 과정도 포함되어 있다.
  • dying thread는 본인 자신을 해제할 수 x
  • 💡 dying thread? :
    실행을 완료했지만 여전히 프로세스 테이블에 항목이 있는 프로세스
    ⭐ PintOS 에서는 프로세스당 하나의 스레드로 구성되어있기 때문에 ‘프로세스=스레드’로 봐도 무방하다.
    (ref. https://en.wikipedia.org/wiki/Zombie_process)

 

• thread_block()

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

 

• do_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 ();
}

 

 

4. get_global_ticks

• Define global_ticks
• threads/thread.c

/* Define global ticks */
static int64_t global_ticks = INT64_MAX; // 초기 global_ticks 비교를 위해서 최대값을 설정해준다.

• timer.c 와 thread.c 에서 사용하기 위한 전역 변수 ‘global_ticks’를 선언한다.
• 이후 getter, setter 를 이용해 ‘global_ticks’ 값을 다룬다.

 

• threads/thread.c

// global ticks를 가져온다.
// Hanyang Univ's func : get_next_tick_to_awake
int64_t 
get_global_ticks(){
    return global_ticks;
}

 

 

5. set_global_ticks

• threads/thread.c

// local tick(각 스레드 wakeup_tick)가 global ticks보다 작을 때, global ticks을 갱신한다.
// Hanyang Univ's func : update_next_tick_to_awake
void 
set_global_ticks(int64_t ticks){
    if (ticks < global_ticks) {
        global_ticks = ticks;
    }
}

 

 

---

3. timer_interrupt

1. 타이머 인터럽트가 발생할 때 깨울 스레드를 결정한다.
2. ‘sleep_list’에서 깨울 스레드를 제거하고 해당 스레드를 ‘ready_list’로 삽입한다.
3. ⭐ 스레드의 상태를 바꿔주는 걸 잊지말자! SLEEP → READY

 

<구현 사항>

1. ‘sleep_list’ 전체를 순회한다. (처음부터 끝까지)
2. 타깃 스레드가 현재 깨어나야하는 시간이 ticks(타임 인터럽트가 발생한 시스템 시각)보다 작을 때, 해당 스레드를 SLEEP → READY 상태를 바꾼다.
3. ‘sleep_list’에서 현재 깨어나야하는 시간(wakeup_tick [= local tick])이 ticks 보다 클 때, 다음 루틴을 위해 ‘global_ticks’를 재설정한다.

 

⚠️ timer interrupt : 일정 시간마다 발동한다.

• PintOS 에선 4 tick(Time Slice)
• RR(Round Robin) 방식이다.

 

6. timer_interrupt

• devices/timer.c

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick (); // update the cpu usage for running process

	if (get_global_ticks() <= ticks){ // 현재 시각이 글로벌 틱보다 크면 스레드 깨우기
		thread_awake(ticks);
	}
}

• ‘global_ticks’는 해당 부분에서 인터럽트 발생 시, 깨워야할 스레드가 있는지 검사하기 위한 용도로만 쓰인다.

 

7. thread_awake

• threads/thread.c

// time_interrupt가 발생한 시각(ticks (eg. 12시))보다 깨워야할 시각이 작은 스레드를 깨운다.
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;
        }
    }
}

• set_global_ticks(INT64_MAX);
  • else 문을 한번도 안들어가는 경우(’sleep_list’의 모든 스레드를 깨워야할 때)에는 ‘global ticks’가 초기화되지않는 경우를 방지하기 위해 ‘global ticks’를 INT64_MAX로 초기화한다.
• ‘sleep_list’는 정렬되지 않은 상태이므로 전체 순회를 진행한다.

 

• list_entry(curr, struct thread, elem);
  • elem으로 부터 스레드의 주소를 얻을 수 있다.
  • 여기서 elem은 list_elem을 가리키며, list_elem은 prev와 next 요소를 갖는 Linked List의 요소 중 하나이다.

 

 

---

✨ Summary

• ticks 🆚 thread_ticks
• global_ticks 🆚 local tick

 

ticks

• 시스템 상에서 지금도 흐르고 있는 현재 시간(eg. 세계 표준시)과 같은 역할

• 시스템 상 시간을 ‘tick’ 이라는 단위로 본다면, 프로그램이 실행되고 총 591 ticks가 발생했다는 것이다.
• 그 중 유휴 스레드가 CPU를 점유한 횟수가 550번이다.

 

• 관련 함수 threads/thread.c -> thread_tick

void
thread_tick (void) {
	struct thread *t = thread_current (); // 현재 CPU를 점유중인 스레드(RUNNING)

	/* 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 ();
}

 

---

thread_ticks

• threads/thread.c

static unsigned thread_ticks;   /* # of timer ticks since last yield. */

• 현재 실행중인 스레드가 어느 정도의 ticks 만큼 실행되었는가
• PiintOS의 기본 time slice(4 ticks)가 지나면 자동으로 타이머가 발생하고 스레드간 컨텍스트 스위칭이 발생한다.
  ↳ 그 다음으로 실행되는 스레드의 thread_ticks는 0부터 시작한다.

 

• 관련 함수 threads/thread.c -> 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;

#ifdef USERPROG
    /* Activate the new address space. */
    process_activate (next);
#endif

    if (curr != next) {
        // dying 스레드 처리
        if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
            ASSERT (curr != next);
            list_push_back (&destruction_req, &curr->elem);
        }

        thread_launch (next); // 현재 실행중인 스레드의 정보를 레지스터에 저장한다.
    }
}

 

---

global_ticks

• ‘sleep_list’의 local tick들의 최솟값을 나타낸다.
• devices/timer.c -> timer_interrup 에서만 사용되며, 단순히 스레드를 깨울 때 모든 ‘sleep_list’ 를 반복 순회하는 것을 막고 한번만 체크하기 위함이다.

 

---

local tick

• 각 스레드들의 wakeup_tick 필드에 저장되는 값을 말한다.

 

 

---

🎉 Test Result

>>> cd ./pintos-kaist/threads/build
>>> make
>>> pintos -- -q run alarm-multiple

 

 

>>> cd ./pintos-kaist/threads
>>> make check