2021/01/31 - [Pintos Project/Project 1] - [PintOS, Project 1] 1/30 : 공부 노트 - 각종 관련 함수들
1. Thread 자료 구조 수정
@/include/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. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
// 깨어나야할 tick 저장 (wakeup_tick)
int64_t wakeup_tick;깨어나야 할 변수를 추가했다. 스레드가 sleep_list에서 대기하고 있을 때, 이 tick을 체크해서 어떤 스레드를 깨울지 결정한다.
이 tick은 현재 tick (tick은 현재 시간이라고 이해하면 된다.)에 으로부터 몇 tick 후에 깨어날지를 말해주는 것이다.
2. 전역변수 추가
Sleep queue 자료구조를 추가해야한다. 이미 있는 ready_list와 같은 구조로 만들면 된다. 그리고 전역 변수로 next_tick_to_awake를 추가하자.
@/threads/thread.c
static struct list ready_list;
/* ------------------------------ project1 --------------------- */
// THREAD_BLOCKED 상태의 스레드를 관리하기 위한 리스트 자료구조 추가
static struct list sleep_list;
// sleep_list에서 대기중인 스레드들의 wakeup_tick값 중 최소값을 저장
static int64_t next_tick_to_awake;
/* ------------------------------ project1 --------------------- */
/* Idle thread. */
static struct thread *idle_thread;
그리고 init할 때, sleep_list와 next_tick_to_awake를 초기화하자. (next_tick_to_awake는 비교하면서 최솟값을 찾아가야하므로 초기화할때는 정수 최댓값을 넣어주자.
@/threads/thread.c
/* Init the globla thread context */
lock_init(&tid_lock);
list_init(&ready_list);
list_init(&destruction_req);
/*-------------------------- project.1 -----------------------------*/
// sleep_list 초기화
list_init(&sleep_list);
next_tick_to_awake = INT64_MAX;
/*-------------------------- project.1 -----------------------------*/
sleep_list에서 대기중이 스레드들의 wakeup_tick 값 중 최소값을 저장하는 전역 변수;next_tick_to_wake 추가한다.
next_tick_to_awake 는 sleep_list 있는 스레드들 중에서 가장 빨리 일어나야하는 스레드의 wakeup_tick을 나타낸다.
그래서 tick이 증가하면서 tick >= next_tick_to_awake 가 되면, 해당 wakeup_tick을 가진 친구를 깨운다.
@/threads/thread.c
/* 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. */
/* ------------------------------ project1 --------------------- */
// sleep_list에서 대기중인 스레드들의 wakeup_tick값 중 최소값을 저장
static long long next_tick_to_awake;
/* ------------------------------ project1 --------------------- */
3. 구현할 함수 선언
일단 헤더에 함수를 선언해야한다.
void thread_sleep(int64_t ticks)ㆍ실행 중인 스레드를 sleep으로 만든다.
ㆍ기본적인 뼈대는 thread_yield()를 기본으로 만든다.
ㆍticks는 sleep_list에 넣는 thread가 깨어날 tick을 말한다. (ticks = sleep했을 당시의 tick + 사용자가 지정한 tick (몇 tick 뒤에 깨어날지) 로 구성된다.)
void thread_awake(int64_t ticks)ㆍsleep_list에 있던 스레드를 깨운다.
ㆍsleep_list를 순회하면서, 스레드의 wakeup_ticks가 ticks보다 작다면 깨울 것이다.
void update_next_tick_to_awake(int64_t ticks)ㆍsleep_list에서 가장 작은 wakeup_ticks를 갱신한다.
int64_t get_next_tick_to_awake(void)ㆍnext_tick_to_awake를 반환하는 함수이다.
그러면 thread.h에 선언해보자.
@/include/threads/thread.h
void do_iret (struct intr_frame *tf);
/*-------------------------- project.1 -----------------------------*/
void thread_sleep(int64_t ticks);
void thread_awake(int64_t ticks);
void update_next_tick_to_awake(int64_t ticks);
int64_t get_next_tick_to_awake(void);
/*-------------------------- project.1 -----------------------------*/
4. thread_init() 함수 수정
list_init 함수로 sleep_init을 초기화하자.
함수는 다음과 같다.
@threads/thread.c
/* Init the globla thread context */
lock_init (&tid_lock);
list_init (&ready_list);
list_init (&destruction_req);
/*-------------------------- project.1 -----------------------------*/
// sleep_list 초기화
list_init(&sleep_list);
/*-------------------------- project.1 -----------------------------*/
5. timer_sleep() 함수 수정
timer_sleep()을 수정한다. 기존 함수는 다음과 같다.
@/devices/timer.c
/* 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_elapsed 는 현재 시간이 특정 시간(start) 으로부터 얼마나 지났는지 알려준다. time_sleep의 목적은 이렇다.
'특정 시간(start)로부터 일정 tick이 지나기 전에는 thread를 활성화시키지 않는다.(thread_yield())'
하지만 위와 같은 코드를 사용하면 매 틱마다 thread가 run에 올라왔다가 바로 ready로 돌아가는(thread_yield()) 작업을 반복한다. 그래서 이것을 busy_waiting (대기하면서 CPU를 사용하고 있는 것)이라고 한다.
이를 sleep_list과 block, unblock을 사용하여 CPU를 사용하지 않도록 한다. 그래서 다음과 같이 바꾼다.
@ /devices/timer.c
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
thread_sleep(start+ticks);
}
이렇게 하면 thread를 원할 때까지 비활성화할 수 있고, 그 사이에 다른 스레드가 CPU를 사용하는 것이 가능해진다.
thread_sleep(start+ticks)는 위에서 말한 것과 같이 스레드를 현재시간(start)으로부터 몇 tick 뒤에(ticks) 깨어나게 하고 싶은지 설정한다.
그러면 이제 thread_sleep을 설정해보자.
6. thread_sleep() 함수 구현
void thread_sleep(int64_t ticks)
{
struct thread *curr = thread_current();
enum intr_level old_level;
ASSERT(!intr_context());
old_level = intr_disable();
curr->wakeup_tick = ticks;
if (curr != idle_thread)
{
list_push_back(&sleep_list, &curr->elem);
}
update_next_tick_to_awake(ticks);
do_schedule(THREAD_BLOCKED);
intr_set_level(old_level);
}thread_sleep은 thread_yield()를 뼈대로하여 재구성하였다.
단지, 비활성화할 때, ready_list로 보내는 것이 아니라 sleep_list로 보내는 것이 달라진다.
그리고 새로운 sleep thread가 만들어졌으므로, 다음 깨워야 할 스레드가 바뀔 가능성이 생기므로 update_next_tick_to_awake를 해서 next_tick_to_awake를 갱신해준다.
do_schedule에서 스레드의 status를 바꿔주는데, 이번에는 ready가 아닌 blocked (sleep상태) 를 지정해주므로 바꾼다.
7. timer_interrupt() 함수 수정
timer_interrupt가 들어올 때 (즉, 시간이 증가할 때), 현재 ticks보다 작은 wakeup_tick이 있는지 판단한다. 만약 있다면 thread_awake()를 호출하여 sleep_list에서 꺼낸다.
※ thread_tick() 은 코드를 제출했을 때, 검사를 위한 함수이다. 신경쓸 필요 없다.
time_interrupt()는 다음처럼 바뀐다.
/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
int64_t next_tick;
next_tick = get_next_tick_to_awake();
/*-------------------- Project1 -------------------------------------*/
if (ticks >= next_tick)
{
thread_awake(ticks);
}
/*-------------------- Project1 -------------------------------------*/
}
8. thread_awake() 함수 구현
thread_awake()는 두가지 역할을 수행해야한다.
ticks는 현재 시각이라고 생각하면 편하다. 그래서 sleep_list의 스레드를 모두 순회하면서 스레드의 wakeup_tick(일어나야할 시각) 이 ticks보다 작으면 깨워야한다. 이것이 첫번째 역할이다.
만약, thread가 일어난다면, sleep_list가 변했으므로 next_tick_to_awake가 바뀔 것이다. 그래서 현재 ticks에서 일어나지 않은 thread 중에서 가장 작은 wakeup_tick이 next_tick_to_awake가 될 것이다. 이것을 갱신해주는 것이 두번째 역할이다.
@ /threads/thread.c
void thread_awake(int64_t ticks)
{
next_tick_to_awake = INT64_MAX;
struct list_elem *e= list_begin(&sleep_list);
struct thread *t;
for (e ; e != list_end(&sleep_list);)
{
t = list_entry(e, struct thread, elem);
if (t->wakeup_tick <= ticks)
{
e = list_remove(&t->elem);
thread_unblock(t);
}
else
{
update_next_tick_to_awake(t->wakeup_tick);
e = list_next(e);
}
}
}
위에서 말한 대로 sleep_list에 변화가 있을 것이므로 next_tick_to_awake는 새로 갱신되어야한다. 그래서 thread_awake() 를 시작할 때 최대값으로 초기화해준다.
그 다음에는 list_begin으로 sleep_list의 첫번째 ELEM을 불러준다. ELEM은 thread를 불러오기 위한 일종의 인덱스이다. 사실 sleep_list 등의 list 구조에는 thread가 직접적으로 들어가있지 않고 thread안의 elem을 가리킨다. elem은 앞 elem과 뒤 elem이 있다. 말로만 하면 어려우므로 아래 도식도를 보자.
@/include/lib/kernal/list.h
/* List element. */
struct list_elem {
struct list_elem *prev; /* Previous list element. */
struct list_elem *next; /* Next list element. */
};
/* List. */
struct list {
struct list_elem head; /* List head. */
struct list_elem tail; /* List tail. */
};
head와 tail은 list (이중연결 리스트) 를 가리키고, elem은 이 list와 thread에 동시에 소속되어있다. 이런 구조를 가짐으로서 list는 스레드가 아닌 elem만 가지고있으면서도 스레드를 찾아갈 수 있다. head와 tail은 리스트의 처음과 끝만 가리키는 역할을 할 뿐, 다른 elem처럼 스레드를 가리키고 있지 않다. (head, tail을 가지고 있으면 스레드를 가리키는 elem을 삽입/삭제할 때 예외처리를 할 필요없이 간단하게 할 수 있다.)
이제 이 elem을 가지고 스레드들을 순회해보자. 처음 e는 list_begin()함수로 가져온다.
@/lib/kernal/list.c
/* Returns the beginning of LIST. */
struct list_elem *
list_begin(struct list *list)
{
ASSERT(list != NULL);
return list->head.next;
}
list_begin()을 사용하면, head가 아닌 첫번째 인자(그림에서 1번 elem)을 가져온다. for문의 종결 조건으로는 e가 리스트의 tail이 아니라는 것이다. list_end()는 다음과 같다.
@/lib/kernal/list.c
/* Returns LIST's tail.
list_end() is often used in iterating through a list from
front to back. See the big comment at the top of list.h for
an example. */
struct list_elem *
list_end(struct list *list)
{
ASSERT(list != NULL);
return &list->tail;
}이제, 우리는 e가 head도 taile도 아닌, 스레드를 가진 elem이라는 것을 알았다. 이 e로 스레드(t)를 가져오자. 이는 list_entry()로 가져올 수 있다.
@/include/lib/kernal/list.h
/* Converts pointer to list element LIST_ELEM into a pointer to
the structure that LIST_ELEM is embedded inside. Supply the
name of the outer structure STRUCT and the member name MEMBER
of the list element. See the big comment at the top of the
file for an example. */
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
- offsetof (STRUCT, MEMBER.next)))솔직히 정확한 메커니즘은 잘 모르겠다. 나중에 공부해봐야지. 흥미로운 구조인 것같다.
이제 t(elem의 스레드)의 wakeup_tick이 ticks (thread_awake()를 실행하기 직전의 next_tick_to_awake이다.) 보다 작다면 깨워야한다. 추상적으로 깨운다, 깨운다했는데 실제 깨우는 로직은 sleep_list에서 제거하고, read_list로 올리는 것을 말한다.
list_remove()는 elem을 해당 list에서 제거하기 위해서 prev elem과 next elem을 이어주는 것이다. return이 다음 elem을 가리키는 것에 유의하자.
@/lib/kernal/list.c
struct list_elem *
list_remove(struct list_elem *elem)
{
ASSERT(is_interior(elem));
elem->prev->next = elem->next;
elem->next->prev = elem->prev;
return elem->next;
}
위와 같이 2번에서 remove_list()를 실행하면, 1번과 2번 / 2번과 3번의 연결을 끊고 1번과 3번을 이어준다.
그리고 thread_unblock()을 실행한다. 이 함수는 이미 thread.c에 존재한다. 해당 스레드를 ready_list에 넣고, status도 THREAD_READY로 바꿔준다.
@/threads/thread.c
/* 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);
t->status = THREAD_READY;
intr_set_level(old_level);
}
그리고 위에서 말했듯이 일어날 스레드가 아니라면, update_next_tick_to_awake()를 실행해준다. 그리고 모든 작업이 끝났다면 list_next()로 넘어가자. (if문에서는 remove_list() 자체가 다음 elem을 반환하기때문에 list_next()가 필요없다.)
@/lib/kernel/list.c
/* Returns the element after ELEM in its list. If ELEM is the
last element in its list, returns the list tail. Results are
undefined if ELEM is itself a list tail. */
struct list_elem *
list_next(struct list_elem *elem)
{
ASSERT(is_head(elem) || is_interior(elem));
return elem->next;
}
9. update_next_tick_to_awake() / get_next_tick_to_awake 함수 추가
@/threads/thread.c
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
(...)
/* ticks와 next_tick_to_awake를 비교하여 작은 값을 넣는다.*/
void update_next_tick_to_awake(int64_t ticks)
{
next_tick_to_awake = MIN(next_tick_to_awake, ticks);
}간단하게 주어진 ticks과 현재 next_tick_to_awake를 비교하여 작은 값을 next_tick_to_awake로 한다.
@/threads/thread.c
int64_t get_next_tick_to_awake(void)
{
return next_tick_to_awake;
}
이로서 모든 구현이 끝났다. 실행해보자
idle tick이 저정도로 나오면 잘된 것이다.
'Pintos Project > Project 1' 카테고리의 다른 글
| [PintOS, Project1] Priority_Scheduling and Synchronization (semaphore 관련) (0) | 2021.02.04 |
|---|---|
| [PintOS, Project1] Condition Variable을 이용한 Monitor System (0) | 2021.02.04 |
| [PintOS, Project1] Priority_Scheduling (1) | 2021.02.03 |
| [PintOS, Project 1] 1/30 : 공부 노트 - 각종 관련 함수들 (0) | 2021.01.31 |
| [PintOS, Appendix ] Threads (0) | 2021.01.30 |
댓글