그닥 자랑스럽진 않은 8 failed
정글 들어와서 가장 머리를 많이 굴려야했던.. 그런 프로젝트 였던 것 같다. 잔뜩 엮여있는 락 관계를 코드로 풀어내야 하는 게 챌린지였다. 우선순위 기부까지는 OK, 근데 회수할려면 어떻게 해야할까를 많이 고민했던 것 같다. 실체가 없는 코드 덩어리를 상상하느라 힘들었다. 코드를 하나하나 따라가면서 그림으로 그려보는 게 많이 도움이 됐다.
Alarm Clock
Busy Wait
Busy Wait는 CPU가 계속 돌면서 원하는 일을 할 수 있는지 계속 체크하는 방식이다. 일반적으로 공유자원에 권한을 획득하고자 하는 동기화 상황에서 while문으로 아무것도 안하면서 대기하는 식이다. 이번 과제에서는 스레드가 일정 시간 동안 멈추는 sleep() 함수를 Busy Wait 방식이 아닌 다른 방식으로 구현하는 게 목표였다.
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
while (timer_elapsed (start) < ticks)
thread_yield ();
}
기본적으로 제공된 코드를 보면 sleep()함수가 호출될 때 while문을 돌면서 주어진 시간이 지났는지 계속 확인하는 방식이다. 이런식으로 구현되어 있으면 sleep()을 부르는 스레드가 그 시간 동안 실제로 sleep하는 게 아니라 계속 깨어있고 여러 스레드가 sleep()상태라고 해도 계속 문맥교환이 발생한다. 계속 CPU 자원을 낭비한다. 우리는 sleep()을 부르는 애를 ready 상태가 아닌 block(대기) 상태로 만들어서 CPU에서 쉴 시간을 줘야 한다.
8254 Timer
스레드를 진짜로 재우기 위해서는 시간을 재야한다. 우리는 tick이라는 cpu시간 단위를 이용해서 시간을 측정할건데 컴퓨터 하드웨어 중에서 8254 타이머라는 놈이 도와줄 것이다.
void
timer_init (void) {
/* 8254 input frequency divided by TIMER_FREQ, rounded to
nearest. */
uint16_t count = (1193180 + TIMER_FREQ / 2) / TIMER_FREQ;
outb (0x43, 0x34); /* CW: counter 0, LSB then MSB, mode 2, binary. */
outb (0x40, count & 0xff);
outb (0x40, count >> 8);
intr_register_ext (0x20, timer_interrupt, "8254 Timer");
}8254 타이머를 설정하고 실행하는 코드이다. 이제 cpu 주파수에 맞춰서 (cpu 클럭마다?) 타이머 인터럽트가 발생할 것이다. 매 틱마다 타이머 인터럽트가 발생하면 timer_interrupt()라는 함수가 실행될 것이다.
타이머 하드웨어가 있어야 스레드가 존재할 수 있다. 타이머 인터럽트를 잘 핸들해서 스레드간 문맥을 교환한다.
구현
-
sleep() 하려는 스레드들을 언제 깨어날지 적어놓고 block 시킨다.
-
자는 놈들은 깨어나는 시간이 빠른 순서대로 정렬시켜 놓는다
void insert_blockList(int64_t endtick)
{
struct thread *curr = thread_current();
enum intr_level old_level;
curr->endTick = endtick;
old_level = intr_disable();
if (curr != idle_thread)
{
list_insert_ordered(&block_list, &(curr->elem), compare_tick, NULL);
do_schedule(THREAD_BLOCKED);
}
intr_set_level(old_level);
}- 틱마다 리스트 맨 앞의 놈이 깨어날 시간인지 확인하고 스레드를 다시 unblock 시킨다.
void wake_up(int64_t ticks)
{
while (!list_empty(&block_list))
{
struct thread *thread = list_entry(list_front(&block_list), struct thread, elem);
if (thread->endTick > ticks)
{
break;
}
else
{
struct thread *enterThread = list_entry(list_pop_front(&block_list), struct thread, elem);
thread_unblock(enterThread);
}
}
}
Priority Scheduling
교착상태
컴퓨터가 암것도 안하고 멈추는 상황이다.
이론상으론 아래 네가지 조건이 모두 참이 될 때 발생한다.
- 상호 배제
- 점유 대기
- 비선점
- 순환 대기
그러니까.. 어떤 공유 자원이 있다. 이 자원은 마구잡이로 쓰면 안되고 한 번에 한놈만 쓸 수 있고 그 자원을 내가 가진다면 내가 반납을 할 때까지 뺏을 수 없다. 근데 내가 어떤 자원을 든 상태에서 다른 자원을 기다리게 된다. 다른 스레드는 내가 가지고 싶어 하는 자원을 가지고 있고 내가 가지고 있는 자원을 얻고 싶어할 때 교착상태가 발생한다.
운영체제는 이런 상황이 발생하게 둬서는 안된다. 핀토스 운영체제는 우선순위 기부를 이용해서 교착상태를 예방할 것이다.
해결책 : 우선순위 기부
우선순위 기부는 교착상태 발생 조건 네가지 중 2번 조건인 점유 대기를 거짓으로 만들어서 교착상태를 해결한다.
내가 어떤 락(자원)을 가지고 싶어하는데 그 락은 이미 어떤 놈이 쓰고 있다. 쓰는 놈이 나보다 우선순위가 낮은 놈일 경우 내 우선순위를 걔가 락을 해제 할때까지 빌려주는 것이다. 락을 해제하면 다시 원래 우선순위를 가지게 해야한다.
/* Lock. */
struct lock {
struct thread *holder; /* Thread holding lock (for debugging). */
struct semaphore semaphore; /* Binary semaphore controlling access. */
};/* A counting semaphore. */
struct semaphore {
unsigned value; /* Current value. */
struct list waiters; /* List of waiting threads. */
};이렇게 미리 구조체들이 잘 준비되어있다. lock의 holder가 있고 걔가 나보다 우선순위가 낮으면 holder의 우선순위를 올려주고 나는 waiter 리스트에 들어간다. 원래 우선순위는 따로 구조체에 적어놨다가 락을 반납할 때 원래상태로 돌려주면 된다. 굉장히 간단하다.
구현
쉬운데.. 분명 쉬웠는데.. multiple, nest, chain을 만나면서 겸손 장착돼버렸다. 락이 얽히면 얽힐수록 혼란에 빠졌다.
일단 donation 해주는 놈이 많아지니까 thread 구조체에 나한테 기부해준 놈들을 기록하는 donations 리스트를 만들어 줘야한다. 그리고 내가 어떤 donation 리스트의 인자로 들어갈 수 있기 때문에 donation_elem도 만들어 준다. 이것만 해도 multiple 까지는 돌아갔던 것 같은데 그 이후로는 내가 기다리고 있는 락의 소유자가 다른 락을 기다리고 있는지(체인)도 확인해야 한다. 그래서 wait_on_lock까지 추가해줬다.
struct thread {
int priority_origin;
struct lock* wait_on_lock;
struct list donations;
struct list_elem donation_elem;
};insert_order() vs list_max()
timer_sleep()을 구현할 때 insert_order()로 sleep_list를 관리했었다. 자연스럽게 우선순위를 관리할 때도 insert_order()로 리스트를 정렬했었는데 여기선 이렇게 쓰면 안된다. 왜냐면 우선순위가 중간에 변경되는 경우가 생기기 때문에! 그래서 push_back()으로 넣고 list_max()로 빼는 식으로 구현.
sema_down()
void sema_down(struct semaphore *sema)
{
enum intr_level old_level;
ASSERT(sema != NULL);
ASSERT(!intr_context());
old_level = intr_disable();
while (sema->value == 0)
{
list_push_back(&sema->waiters, &thread_current()->elem);
thread_block();
}
thread_current()->wait_on_lock = NULL;
sema->value--;
intr_set_level(old_level);
}이 코드만 보고 나는 while()문이 계속 도는건가? 잠깐 생각했던 적이 있다. 역시 알고나면 당연하지만 sema 값이 0이면 스레드는 block이 되고 내가 깨어나는 경우는 sema 값이 올려지고 난 후여서 while이 계속 돌진 않는다.
sema_up()
void sema_up(struct semaphore *sema)
{
enum intr_level old_level;
ASSERT(sema != NULL);
old_level = intr_disable();
if (!list_empty(&sema->waiters))
{
struct list_elem *max_elem = list_max(&sema->waiters, compare, NULL);
struct thread *next_holder = list_entry(max_elem, struct thread, elem);
struct thread *curr = thread_current();
for (struct list_elem *waiter_elem = list_begin(&sema->waiters); waiter_elem != list_end(&sema->waiters); waiter_elem = list_next(waiter_elem))
{
struct thread *waiter_thread = list_entry(waiter_elem, struct thread, elem);
if (list_find(&curr->donations, &waiter_thread->donation_elem))
{
list_remove(&waiter_thread->donation_elem);
if (list_empty(&curr->donations))
{
curr->priority = curr->priority_origin;
break;
}
struct list_elem *donation_max_elem = list_max(&curr->donations, compare, NULL);
struct thread *donation_max_thread = list_entry(donation_max_elem, struct thread, donation_elem);
curr->priority = donation_max_thread->priority;
}
}
list_remove(max_elem);
thread_unblock(next_holder);
}
sema->value++;
thread_yield();
intr_set_level(old_level);
}
처음엔 반복문 대신 그냥 If를 썼었다. sema->waiter를 순회하면서 지운다고 생각해서 if를 썼었는데 자세히 보면 결국 donetion_elem을 지우는 거라 반복문으로 내가 가진 락에 대해 우선순위 기부를 해준놈들을 전부 취소해줘야 했다.
+) 순서에 유의할 것
sema->value++;
thread_yield();sema 테스트 실패했던 이유. 역시 알고나면 당연한 건데 당연히 sema 값을 올리고 양보해야해야한다.
끝.
안일했던 1.5주였다. 시간이 꽤 많았는데 MLFQS는 무슨.. 우선순위 스케줄링도 꾸역꾸역 했던 것 같다. 코드 자체도 생각하고 설계하면서 짜지 않고 테스트 코드를 통과하기 위해 덧붙이는 식으로 짰다. 옳지 않다. 이번주에 위가 안좋아서 소식했는데 공부도 소식해버렸다. 이번주를 기억하면서 다음주는 좀 더 몰입해봐야겠다.
