💡 스레드를 잠시 재웠다가 일정 시간이 지나면 깨우는 기능인
Alarm Clock을 Busy-waiting 방식에서 Sleep-Awake 방식으로 변경하자!
Busy waiting은 특정 조건이 매우 빠르게 충족될 것으로 예상될 때 사용되는 것이 적합하며,
Alarm clock은 일정 시간 이후에 수행해야 하는 작업이 있을 때 사용된다.
Busy waiting
Alarm Clock
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_sleep() 함수는 스레드를 ticks만큼 일시 중지하는 함수이다.
현재 구현된 방식으로는, 현재 타이머 시간과 ticks를 비교해서 아직 ticks에 도달하지 않았으면 thread_yield() 함수를 호출하여 다른 스레드에게 CPU를 양보한다.
하지만 CPU를 양보 받은 스레드도 아직 ticks에 도달하지 않은 경우에는, CPU를 양보 받자마자 바로 다시 다른 스레드에게 양보를 해야 한다. (즉, 불필요한 Context switching이 많이 일어날 수 있다.)
따라서 아직 ticks에 도달하지 않은 스레드가 깨워지는 것이 큰 비효율을 발생시키고, 이것을 해결하는 것이 이번 과제의 목적이다.
- 🤔 tick이란?
- tick은 일정 시간 간격으로 발생하는 시스템의 기본적인 시간 단위이다.
- 시스템 타이머는 이러한 틱을 생성하며, 일반적으로 운영 체제는 이러한 틱을 사용하여 시스템 상태를 유지하고 다양한 작업을 스케줄링한다.
- 예를 들어, 시스템 타이머가 100번의 틱을 초당 생성한다면, 운영 체제는 1초를 100개의 틱으로 나누어 시스템 상태를 업데이트하고 작업을 스케줄링한다.
- 이러한 방식으로 시스템이 일관된 방식으로 동작할 수 있도록 한다.
- tick을 사용하는 이유
1) 틱은 고정된 간격으로 발생하기 때문에, 운영 체제가 특정 작업을 실행하기 위해 기다리는 시간을 정확히 계산할 수 있다.
- 예를 들어, 운영 체제가 특정 작업을 5초 후에 실행하도록 스케줄링했다면, 운영 체제는 틱이 발생하는 시간을 이용하여 정확한 시간을 측정한다. 이를 통해 운영 체제는 특정 작업이 정확히 5초 후에 실행될 것임을 보장할 수 있다.
2) 시간 단위를 사용하는 경우, 시스템이 다른 작업을 수행하면서 시간이 흐를 때마다 시간을 업데이트해야 하기 때문에 부하가 커질 수 있다.
- 따라서, 틱 단위로 시간을 추적함으로써 시스템의 부하를 줄이고 일관성을 유지할 수 있다.
- 틱을 업데이트하는 것도 일정한 부하를 발생시키지만, 이 부하는 대부분 무시할 수준이다. 틱은 하드웨어에서 매우 빠르게 처리될 수 있는 단위이기 때문이다.
3) 틱을 사용하여 CPU 사용률을 조절할 수 있다.
- 틱의 간격을 더 작게 조정하면, 시스템은 더 자주 인터럽트를 처리하여 작업을 스케줄링할 수 있게 된다.
- 이는 우선순위가 높은 작업이 더 빠르게 실행될 수 있도록 하여 시스템의 반응성을 향상시키는 데 도움이 된다.
현재
스레드가 잠들면 모두 스케줄링 대기열인 ready_list에 추가하고 있어서,
아직 깰 시간이 되지 않은 (ticks에 도달하지 않은) 스레드가 깨워지는 일이 발생한다!
변경안
새로운 방식에서는 잠든 스레드가 깰 시간(ticks에 도달할 때)까지는 ready_list에 추가하지 않고,
깰 시간(ticks)에 도달한 경우에만 ready_list에 추가하는 방식으로
아직 ticks에 도달하지 않은 스레드가 깨워지는 일을 없게 만들 것이다!
/* thread.c */
// 1. sleep_list 선언
static struct list sleep_list;
...
// 2. sleep_list 초기화
void thread_init (void) {
...
list_init (&sleep_list); // sleep_list 초기화
...
}
/* 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_ticks; // 일어날 시각 추가**
...
};
timer_sleep
/* timer.c */
void timer_sleep(int64_t ticks)
{
int64_t start = timer_ticks(); // 현재 시각
ASSERT(intr_get_level() == INTR_ON);
thread_sleep(start + ticks); // 현재 시각 (start) + 잠들 시간 (ticks)
}
thread_sleep
/* thread.h */
void thread_sleep (int64_t ticks);
/* thread.c */
void thread_sleep(int64_t ticks)
{
struct thread *curr;
enum intr_level old_level;
old_level = intr_disable(); // 인터럽트 비활성
curr = thread_current(); // 현재 스레드
ASSERT(curr != idle_thread); // 현재 스레드가 idle이 아닐 때만
curr->wakeup_ticks = ticks; // 일어날 시각 저장
list_insert_ordered(&sleep_list, &curr->elem, cmp_thread_ticks, NULL); // sleep_list에 추가
thread_block(); // 현재 스레드 재우기
intr_set_level(old_level); // 인터럽트 상태를 원래 상태로 변경
}
cmp_thread_ticks
/* thread.h */
bool cmp_thread_ticks(const struct list_elem *a, const struct list_elem *b, void *aux);
/* thread.c */
// 두 스레드의 wakeup_ticks를 비교해서 작으면 true를 반환하는 함수
bool cmp_thread_ticks(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
struct thread *st_a = list_entry(a, struct thread, elem);
struct thread *st_b = list_entry(b, struct thread, elem);
return st_a->wakeup_ticks < st_b->wakeup_ticks;
}
timer_interrupt
/* timer.c */
static void timer_interrupt(struct intr_frame *args UNUSED)
{
ticks++;
thread_tick();
thread_wakeup(ticks);
}
thread_wakeup
/* thread.h */
void thread_wakeup (int64_t global_ticks);
/* thread.c */
void thread_wakeup(int64_t current_ticks)
{
enum intr_level old_level;
old_level = intr_disable(); // 인터럽트 비활성
struct list_elem *curr_elem = list_begin(&sleep_list);
while (curr_elem != list_end(&sleep_list))
{
struct thread *curr_thread = list_entry(curr_elem, struct thread, elem); // 현재 검사중인 elem의 스레드
if (current_ticks >= curr_thread->wakeup_ticks) // 깰 시간이 됐으면
{
curr_elem = list_remove(curr_elem); // sleep_list에서 제거, curr_elem에는 다음 elem이 담김
thread_unblock(curr_thread); // ready_list로 이동
}
else
break;
}
intr_set_level(old_level); // 인터럽트 상태를 원래 상태로 변경
}
방식의 구현 끝 ~ 💖
/* Test: /threads/build에서 입력 */
pintos -- -q run alarm-multiple
👇🏻 구현 전
👇🏻 구현 후
0이었던 idle tick이 550으로 증가했다!