../include/threads/thread.h
thread 구조체에 thread가 일어날 시간을 저장할 변수 wakeup_tick을 선언한다.
struct thread {
...
int64_t wakeup_tick; // thread가 깨어날 시간
...
struct list_elem elem; // thread가 가진 값?
};../devices/timer.c
timer_sleep: 타이머에서 스레드를 재우는 함수
시스템 부팅 후 지난 시간은 start로 확인하고
thread를 ticks 단위 시간 뒤에 깨운다면
시스템 부팅 후 start+ticks 단위 시간 뒤에 깨우면 된다.
void
timer_sleep (int64_t ticks) { // ticks: 스레드를 잠재울 시간
int64_t start = timer_ticks (); // start: os현재 시간
ASSERT (intr_get_level () == INTR_ON); // 인터럽트가 ON상태여야 실행
if (timer_elapsed (start) < ticks){
thread_sleep(start+ticks); // start+ticks까지 스레드를 재우기.
}
}timer_interrupt: 단위 시간마다 확인
ticks는 OS 부팅 후 지난 시간을 의미한다.
여기서 ticks = 1/100초를 의미한다.
즉 100ticks=1초를 의미한다.
check_thread_sleep_list(ticks)는 ticks일 때 깨울 스레드가 있는지
sleep_list에서 확인하겠다는 뜻이다.
/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
check_thread_sleep_list(ticks); // sleep_list에 깨울 스레드가 있는지 확인
}../threads/thread.c
스레드에 깨어날 시간 추가
- THREAD_BLOCKED된 스레드를 저장할 sleep_list를 선언한다.
- sleep_list에서 가장 일찍 일어나는 시간을 저장할 earliest_wakeup_time를 선언한다.
/* List of processes in THREAD_BLOCKED state, that is, processes
that are sleep to wait but */
static struct list sleep_list; // blocked된 스레드를 저장하는 리스트
static int64_t earliest_wakeup_time; // 가장 일찍 기상하는 시간sleep_list를 초기화
선언한 sleep_list를 초기화해준다.
void
thread_init (void) {
/* Init the globla thread context */
...
list_init (&sleep_list);
}wakeup_tick이 더 일찍인 함수 반환
두 스레드를 비교해서 wakeup_tick 더 작은, 즉 더 일찍 일어나는 스레드를 반환한다.
이 비교를 하는 스레드를 선언해준 이유는
기본 함수인 list_insert_ordered(...)와 list_min(...)는
특이하게도 "비교하는 함수의 이름"을 인자값으로 받는데
예를 들면 아래처럼 쓰인다.
- list_insert_ordered(&sleep_list, &curr->elem, get_earlier_time, NULL);
-> 리스트에 원소를 추가할 때 정렬된 위치에 넣어준다. - list_min(&sleep_list,get_earlier_time, NULL)
-> sleep_list의 thread중에서 wakeup_tick가 가장 작은 원소 elem를 반환한다.
이때 elem은 struct thread가 갖고 있는 값을 의미한다.
// get smaller value in list
static bool get_earlier_time(const struct list_elem *a_, const struct list_elem *b_, void *aux UNUSED){
const struct thread *a = list_entry(a_, struct thread, elem);
const struct thread *b = list_entry(b_, struct thread, elem);
return a->wakeup_tick < b->wakeup_tick;
}list_entry(...)
이 함수도 기본함수인데 좀 특이하다.
list_entry(구조체 멤버 포인터, 구조체, 구조체 멤버);
const struct listelem *a;
listentry(a, struct thread, elem);
구조체 멤버 포인터, 구조체, 구조체 멤버를 인자로 넣으면
구조체 멤버 포인터가 속한 구조체 포인터를 반환한다.
예를 들면 구조체 struct thread안에 멤버 struct list_elem elem이 있는데
list_entry(...)함수를 실행하면 struct *thread를 반환하겠다는 의미다.
check_thread_sleep_list
timer_interrupt에서 매 ticks마다 check_thread_sleep_list(...)가 실행되며
sleep_list에서 깨워야할 스레드가 있는지 확인하고 만약 있다면 깨운다.
시간을 절약하기 위한 아이디어가 들어가 있는데
sleep_list에 새로 재운 스레드를 넣을 때마다 깨어나는 시간 wakeup_tick을 확인하고
sleep_list에 들어간 시간 중
제일 일찍 일어나는 스레드의 기상시간 earliest_wakeup_time를 갱신해준다.
만약 시스템 부팅시간이 1ticks이고 제일 일찍 일어나는 스레드가 10ticks이라면
1~9ticks까지는 굳이 sleep_list를 일일이 확인할 필요가 없다.
그래서 check_thread_sleep_list(...)의 아래 부분에서 확인해준다.
if(os_ticks < earliest_wakeup_time){
return;
}sleep_list에 [10,10,20,30,40]으로 있고 현재 부팅시간 os_ticks가 10ticks라면
10ticks를 전부 깨우고 나면 sleep_list는 [20,30,40]이 된다.
이때 남은 sleep_list에서 가장 일찍 일어나는 스레드의 시간은 20ticks가 된다.
이때 제일 일찍 일어나는 스레드의 기상시간 earliest_wakeup_time를 20으로 갱신해주면
운영체제 입장에서 11~19ticks까지는 굳이 sleep_list를 보지 않아도 된다.
이런 식으로 커널의 스레드를 아낄 수 있다.
깨우고 남은 sleep_list의 제일 일찍 일어나는 시간은
list_entry(list_min(&sleep_list,get_earlier_time, NULL), struct thread, elem)->wakeup_tick로 구할 수 있다.
list_min(&sleep_list,get_earlier_time, NULL)은
wakeup_tick이 제일 작은 스레드의 elem 포인터를 반환하고
list_entry(...)는 그 thread 포인터를 반환한다.
// 깨울 스레드가 있는지 확인하고 있다면 깨운다.
void
check_thread_sleep_list(int64_t os_ticks){
// 스레드가 가장 일찍 일어나는 시간보다 운영체제 실행시간이 더 이른 경우 실행 종료를 한다.
if(os_ticks < earliest_wakeup_time){
return;
}
enum intr_level old_level=intr_disable(); // inturrupt 중단
// 깨어나야할 스레드를 탐색한다.
// 만약 두 스레드가 동시에 깨어나야한다면 어떻게 할까?
// -> 그냥 둘 다 깨워주면 될듯?
struct list_elem *cur;
// 쓰레드를 순회하며 깨어날 스레드인지 확인한다.
for(cur=list_begin(&sleep_list); cur!=list_end(&sleep_list); cur=list_next(cur)){
struct thread *curThread = list_entry(cur, struct thread, elem);
int64_t curWakeupTime = curThread->wakeup_tick;
// 깨어날 시간이 된 쓰레드인 경우
if(curWakeupTime <= os_ticks){
struct thread *before = list_entry(list_prev(cur), struct thread, elem);
list_remove(cur);
thread_unblock(curThread);
cur = &(before->elem); // 지워진 블록의 이전 블록으로 설정한다.
}
}
// sleep list에 남은 애들 중에서 가장 빠른 기상시간으로 갱신
if(!list_empty(&sleep_list)){
earliest_wakeup_time = list_entry(list_min(&sleep_list,get_earlier_time, NULL), struct thread, elem)->wakeup_tick;
}
// sleep list가 비어있다면
else{
earliest_wakeup_time = 9223372036854775807;
}
intr_set_level (old_level); // interrupt 다시 실행
}스레드를 재우는 함수
list_insert_ordered(&sleep_list, &curr->elem, get_earlier_time, NULL);
thread.c의 전역변수로 int64_t earliest_wakeup_time를 선언해주고
가장 일찍 일어나는 스레드의 기상시간을 갱신해줬다.
여기서 중요한 부분이 thread의 값을 바꾸는 행위를 한다면
예를 들어 스레드의 상태값 status를 THREAD_BLOCKED로 바꿔준다면
inturrupt를 중단한 상태에서만 실행해줘야한다.
그리고 값을 바꾸는 일이 끝나면 다시 inturrupt를 실행해줘야한다.
list_insert_ordered(...)
PintOS의 기본함수로 특이하게도 "원소값을 비교하는 함수의 이름"을 인자로 받아서 실행한다.
인자로 넣은 정렬함를 기준으로 정해진 위치에 요소를 삽입한다.
이때 정렬함수는 람다식과 비슷한데 만약 두 원소를 비교해서 더 작은 원소를 반환한다면 오름차순
두 원소를 비교해서 더 큰 원소를 반환한다면 내림차순으로 정렬된 위치에 원소를 삽입한다.
인자로 넣는 함수로 thread의 wakeup_tick을 비교해서 넣는다면
list에 새로운 원소를 넣을 때 wakeup_tick을 기준으로 오름차순/내림차순이 되도록 삽입된다.
아래에 리스트 원소 비교함수를 적었다.
이 함수는 wakeup_tick을 기준으로 더 작은 값을 반환하기 때문에
-> wakeup_tick을 기준으로 오름차순이 되도록 list에 삽입한다.
예를 들어 [1,3,4,5]인 리스트에 2를 새로 삽입한다면 [1,2,3,4,5]가 되는 셈이다.
// get smaller value in list
static bool get_earlier_time(const struct list_elem *a_, const struct list_elem *b_, void *aux UNUSED){
const struct thread *a = list_entry(a_, struct thread, elem);
const struct thread *b = list_entry(b_, struct thread, elem);
return a->wakeup_tick < b->wakeup_tick;
}list_insert_ordered(&sleep_list, &curr->elem, get_earlier_time, NULL);
-> sleep_list 리스트에 새로운 원소를 삽입할 때 get_earlier_time이라는
wakeup_tick 오름차순 정렬에 맞춰서 바꿔준다.
마지막 NULL은 추가옵션 인자로 지금은 NULL로 써도 괜찮다고 한다.
좀 더 자세한 활용법은 PintOS를 진행하며 알아보도록 하겠다.
void
thread_sleep(int64_t ticks){
ASSERT (!intr_context ()); // 외부 인터럽트가 실행 중이면 중단
enum intr_level old_level=intr_disable(); // inturrupt 중단
struct thread *curr = thread_current (); // 현재 실행 중인 스레드 구하기
ASSERT(curr!=idle_thread); // idle쓰레드면 중단
// idle쓰레드는 ReadyQueue에 대기하는 쓰레드로 바꿔준다.
if(curr!=idle_thread){
curr->wakeup_tick = ticks; // 일어날 시간을 정해주기
// 가장 일찍 일어나는 시간 갱신해주기
if(earliest_wakeup_time==NULL){
earliest_wakeup_time = ticks;
}
else{
// 더 일찍 일어나야하는 스레드가 추가된다면 갱신해주기
earliest_wakeup_time = (earliest_wakeup_time < ticks? earliest_wakeup_time: ticks);
}
// list_push_back (&sleep_list, &curr->elem); // 그냥 삽입
list_insert_ordered(&sleep_list, &curr->elem, get_earlier_time, NULL); // 정렬해서 sleep list에 삽입
thread_block(); // 쓰레드를 blocked
}
intr_set_level (old_level); // interrupt 다시 실행
}