Pintos Project - Thread

Pintos Project

• 1주차 : Thread
• 2주차 : User programs
• 3주차 : Virtual memory
• 4주차 : File system

Jungle OS프로젝트가 시작되고 1주일이 지났다.

한 주간 Thread scheduling에 대해 공부하고, 함수들을 수정하며, donate priority까지 구현을 직접 해보았다. 시작할 때만 하더라도, 도통 무슨 소리인지 모르겠고 막막했는데 1주일이 지난 지금 다시 정리하며 많은 것들을 이해하고 있는 나 자신을 볼 수 있었다. 그동안 컴퓨터 시스템 책을 공부하며 동시성 프로그래밍을 가능하게 해주는 thread가 번갈아가며 실행된다고 막연히 알고 있었는데, priority를 고려하고, lock과 함께 사용될때 donation 방식으로(실제 사용되는 방식과는 차이점이 많지만)작동된다는 것을 이해하게 되었다.

한 주 동안 아쉬운 점도 많이 남지만, 아직 4주가 남았으니 열심히 달려보자!

reference

• https://casys-kaist.github.io/pintos-kaist/project1/alarm_clock.html
• https://oslab.kaist.ac.kr/ee415-spring-2020/

Busy waiting

pintos의 thread scheduling에서 timer_sleep()함수는 busy waiting으로 구현되어 있다. Busy waiting은 timer_sleep()함수가 호출되어 일정 ticks동안 멈춰있어야 할 thread들도 running 상태로 이동해 현재 자신이 sleeping 상태를 벗어날 수 있는지 확인한다. 따라서, sleep 상태인 thread들도 running상태로 전이되어 CPU자원을 낭비하게 된다.

Alarm Clock

이 Busy waiting을 개선한 것이 Alarm Clock이다.

Alarm함수가 실행되면, Thread를 정해진 시간 이후 깨우게 된다. Busy waiting에서는 실행되지 않아야 할 thread들도 running상태로 이동해 자신이 현재 깨야 하는지 확인했다면, Alarm Clock에서는 sleep함수가 실행되면, 해당 thread는 sleep_list에 추가되고, 현재 ready_list에서 대기하고 있는 것이 아니기 때문에, interrupt가 발생하기 전까지 running상태로 이동하지 않는다. 따라서, Busy waiting처럼 CPU자원을 낭비하지 않는다.

timer_interrupt가 Thread들을 unblock 시키고, unblock된 thread들은 ready_list에 추가되어 자신의 차례에 다시 실행되게 된다.

Priority Scheduling

Alarm Clock 단계까지는 Thread Scheduling이 Round Robin방식으로 실행된다. Round Robin 방식은 프로세스들 간에 우선순위를 따지지 않고, 순차적으로 실행하는 방식이다. 이전까지는 priority에 일정한 값을 넣어주어 모든 Thread의 priority가 같았다면, Priority Scheduling에서는 ready_list에 우선순위 기준으로 내림차순 정렬되어 가장 우선순위가 높은 Thread부터 실행되게 된다. ready_list에 추가된 Thread의 priority가 running중인 thread의 priority보다 높다면, 새로운 thread가 running상태에 있었던 thread를 선점(preemption)하게 된다.

Priority Donation

위의 Priority Scheduling에는 문제점이 존재한다.

바로 Priority inversion problem이다. 이는 priority가 높은 thread가 임계 영역에 접근하기 위한 lock을 가지기 위해 자신보다 낮은 priority를 가지는 thread들을 기다리는 문제이다.

임계 영역에 접근하기 위해서는 lock이 필요한데, Low priority를 가지는 thread_L이 lock을 가지고 있다고 생각해보자. High priority를 가지는 thread_H는 lock을 요청하지만 현재 thread_L이 사용중이기 때문에 lock의 waiting list에 추가되어 대기한다. 그런데 이때, thread_M이 ready_list에 추가되어 실행되게 된다면, 우선순위에서 thread_L이 thread_M에게 밀린다. 따라서, thread_H도 자신보다 낮은 priority를 가지는 thread들을 기다리게 된다. 이것이 priority inversion이다.

이때, thread_H는 자신의 priority를 lock을 소유하고 있는 thread_L에게 넘겨주어 thread_L이 thread_H의 priority를 가지고 thread_M보다 먼저 실행될 수 있게 한다. thread_L이 먼저 실행되고 lock을 반환하면, thread_H가 실행가능해져 priority inversion problem을 해결할 수 있다.

Priority donation을 구현할 때 몇가지 주의해야 하는 상황이 존재한다.

첫 번째로, multiple donation 상황에서의 주의사항이다.

Thread_L은 임계영역에 접근하기 위한 lock_A와 lock_B를 모두 소유하고 있고, Thread_M은 lock_A가 필요하며, Thread_L은 lock_B가 필요하다. 이런 상황에서 Thread_L은 thread_M과 thread_H의 priority를 전달받아 33의 priority가 된다. 이때, thread_L이 lock_B를 사용하고 반환한 상황을 상상해보자. 현재 lock_B는 반환하고, lock_A는 사용중이다. 그렇다면, thread_H에게 받았던 priority 33을 반납하고, priority가 32가 되어야 한다. 이후 lock_A도 다 쓰고 반납하면 본래의 priority 31로 돌아와야 한다. 따라서, 어떤 thread들이 나에게 priority를 전달하고 있는지에 대한 정보를 기억하고 있는 것이 중요하다.

이때, 어떤 Thread들이 자신에게 priority를 전달해주었는지 기억하기 위해 donations라는 list를 thread구조체에 추가하고, donations에 priority를 전달하는 thread의 donation_elem을 추가했다.

다음으로, nested donation상황에서의 문제를 살펴보자.

Thread_L은 lock_A를 가지고 있고, thread_M은 lock_B를 가지고 있고, lock_A를 필요로 한다. Thread_H는 lock_B가 필요한 상황에서, lock_B를 소유하고 있는 thread_M에게만 priority를 donation해준다면, 문제가 발생한다. Lock_B를 소유하고 있는 thread_M의 priority는 high가 되었지만, thread_M은 lock_A가 필요하고 lock_A를 소유하고 있는 thread의 priority는 여전히 low이기 때문이다.

따라서, donation을 할 때는 단순히 lock을 소유하고 있는 thread가 존재할 때 소유하고 있는 thread에만 priority를 전달하는 것이 아니라, 소유하고 있는 thread가 다른 lock을 필요로 하면, 해당 lock의 holder로 타고 들어가서 해당 lock을 hold중인 thread에게도 priority를 전달해야 한다.(while문으로 lock을 필요로 하지 않는 holder가 나타날 때 까지 탐색하자.) Thread가 다른 lock을 필요로 하는지는 wait_on_lock에 저장된다. lock구조체에는 lock을 소유중인 thread가 holder에 저장된다.

Function

priority donation을 위한 대표적인 함수 몇 가지를 살펴보자.

void lock_acquire (struct lock *lock)

lock을 얻기위해 실행하는 함수이다.

먼저 lock이 유효한 lock인지 확인하고, lock구조체의 holder를 확인한다. holder가 NULL이 아니라면, lock을 누가 선점하고 있다는 의미이고, 현재 thread가 당장 사용할 수 없다.

curr->wait_on_lock = lock : lock을 사용하기 위해서 기다리고 있음으로, wait_on_lock의 값을 lock으로 지정한다.

list_insert_ordered(&(lock_holder->donations), &curr->donation_elem, &cmp_priority, NULL) : donations리스트에 donation_elem을 추가한다. multiple donation에서 발생하는 문제를 해결하기 위해 사용된다.

스레드가 두 개 이상의 lock 보유 시, 각 lock에 의해 도네이션이 발생 가능 이전 상태의 우선순위를 기억하고 있어야 한다.

[example]

 스레드 L(priority: 31)이 lock A와 lock B를 점유

 스레드 M(priority: 32)이 lock A를 요청, 우선순위 도네이션 발생 (스레드 L, priority = 32)

 스레드 H(priority: 33)이 lock B를 요청, 다시 우선순위 도네이션 발생 (스레 드 L, priority = 33)

 스레드 L이 lock B를 해지하여 스레드 L의 우선순위를 초기화(priority: 31)

 아직 lock A를 해지 하지 않았지만 우선순위가 31로 변경

 이전 상태의 우선순위 (스레드 M에 의해 도네이션 받은 priority: 32) 를 기억 하 고 있다가 스레드 L의 우선순위를 32로 변경 해야 한다.

sema_down (&lock->semaphore) : sema_down함수를 실행하다가, scheduling당해 잠시 waiting리스트에서 대기하게 된다. lock 구조체 내의 semaphore의 waiting list에 추가되어 기다리고 있다가, 현재 thread의 차례가 되면 다시 실행된다. sema_down이 끝난 시점엔 현재 thread가 lock을 보유하고 있는 상황이다.

lock->holder = curr : sema_down이 끝난 시점엔 현재 thread가 lock을 보유하고 있는 상황임으로 현재 lock의 holder로 curr현재 thread를 저장하자.

/* 해당 lock 의 holder가 존재 한다면 아래 작업을 수행한다. */
/* 현재 스레드의 wait_on_lock 변수에 획득 하기를 기다리는 lock의 주소를 저장 */
/* multiple donation 을 고려하기 위해 이전상태의 우선순위를 기억,
donation 을 받은 스레드의 thread 구조체를 list로 관리한다. */
/* priority donation 수행하기 위해 donate_priority() 함수 호출 */
void
lock_acquire (struct lock *lock) {
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));

  struct thread* curr = thread_current(); 
  struct thread* lock_holder = lock->holder; 

  if(lock_holder != NULL){
    curr->wait_on_lock = lock;    
    list_insert_ordered(&(lock_holder->donations), &curr->donation_elem, &cmp_priority, NULL);
    donate_priority(); 
  }

  sema_down (&lock->semaphore);
  curr->wait_on_lock = NULL;

  lock->holder = curr;
}

void donate_priority(void)

nested donation상황을 고려하기 위해서 lock->holder의 wait_on_lock이 NULL인 thread가 등장하기 전까지 타고 들어가며 자신보다 낮은 priority를 가진 thread에게 priority를 기부한다.

while (next != NULL) : holder가 존재하지 않을 때 까지 while문을 돌며 priority를 기부한다.

next->priority = curr->priority : holder의 priority가 자신의 priority보다 작을 때 priority를 기부한다.

next = next->wait_on_lock->holder : while문을 돌 때 마다 next를 다음 lock의 holder로 업데이트 해준다.

/* priority donation 을 수행하는 함수를 구현한다.
현재 스레드가 기다리고 있는 lock 과 연결 된 모든 스레드들을 순회하며
현재 스레드의 우선순위를 lock 을 보유하고 있는 스레드에게 기부 한다.
(Nested donation 그림 참고, nested depth 는 8로 제한한다. ) */
void donate_priority(void){
  struct thread* curr = thread_current();
  if(curr->wait_on_lock == NULL){
      return;
  }
  struct thread* next = curr->wait_on_lock->holder; 
  int nested_depth = 0;

  while (next != NULL){
        if(next->priority < curr->priority)
        next->priority = curr->priority;
      if(next->wait_on_lock == NULL)
        break;
      next = next->wait_on_lock->holder;
    }
}

void lock_release (struct lock *lock)

remove_with_lock(lock) : lock을 해지했을 때, donations list에서 wait_on_lock이 lock과 동일한 thread들을 donations list에서 제거해준다. Thread_1이 lock_a와 lock_b를 쥐고 있다가, lock_a를 해지할 때, priority를 refresh하기 전에 donations list에서 lock_a가 필요해서 Thread_1에게 priority를 기부해 주었던 Thread들을 제거해 주어야 한다.

refresh_priority() : donations list에서 현재 해지한 lock과 관련된 Thread들을 모두 제거하고, 남은 Thread들의 priority 중 가장 큰 값을 현재 Thread의 priority로 refresh한다.

sema_up (&lock->semaphore) : lock의 semaphore의 waiting list에서 대기중이던 thread가 존재하면, 그 중 한개의 thread를 깨우고 semaphore의 value를 1높인다.

void
lock_release (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (lock_held_by_current_thread (lock));

    lock->holder = NULL;

    remove_with_lock(lock);
    refresh_priority();

    sema_up (&lock->semaphore);
}

void remove_with_lock(struct lock *lock)

lock을 해지했을 때, donations list에서 wait_on_lock이 lock과 동일한 thread들을 donations list에서 제거해준다.

Thread_1이 lock_a와 lock_b를 쥐고 있다가, lock_a를 해지할 때, priority를 refresh하기 전에 donations list에서 lock_a가 필요해서 Thread_1에게 priority를 기부해 주었던 Thread들을 제거해 주어야 한다. for문을 통해 각 donation_elem이 속해있는 thread의 wait_on_lock이 현재 해지한 lock과 같은지 확인한 후, 같다면 donations list에서 제가한다.

t = list_entry(e, struct thread, donation_elem) :

#define list_entry(LIST_ELEM, STRUCT, MEMBER) ((STRUCT *) ((uint8_t *) (LIST_ELEM) - offsetof (STRUCT, MEMBER)))

#define offsetof(s,m) ((size_t)&(((s*)0)->m))

list_entry매크로를 사용해 thread의 주소를 알아낼 수 있다. offsetof(s,m)에서 주소가 0인 포인터를 구조체 포인터로 캐스팅한 후, m의 주소값을 받아온다. donation_elem의 주소에서 해당 offset을 빼면 donation_elem이 속해있는 thread의 주소를 얻을 수 있다.

/* lock 을 해지 했을때 donations 리스트에서 해당 엔트리를
삭제 하기 위한 함수를 구현한다. */
void remove_with_lock(struct lock *lock){
    struct thread* curr = thread_current();
    struct thread* t;

    if(list_empty(&curr->donations)){
      return;
    }

    for (struct list_elem* e = list_begin(&curr->donations); e != list_end(&curr->donations) ;) {
        t = list_entry(e, struct thread, donation_elem);
        ASSERT (is_thread (t));
        if (t->wait_on_lock == lock){
            e = list_remove(&t->donation_elem);
        }
        else{
            e = list_next(e);
        }
    }
}

void refresh_priority(void)

curr->priority = curr->init_priority : donations list를 순회하며, priority를 갱신하기 전에 먼저, 현재 priority를 init_priority로 먼저 변경한다. 특정 lock을 해지했을 때, 해당 lock을 기다리는 다른 높은 priority를 가지는 thread로부터 받은 priority를 가지고 있을 수 있기 때문에 이 문장을 반드시 먼저 실행해주어야 한다.

list_sort(&curr->donations, &cmp_priority, NULL) : donations list가 비어있지 않다면, donations list를 내림차순으로 정렬한다.

list_priority = list_entry(list_begin(&curr->donations), struct thread, donation_elem)->priority : list_priority에 donations list에 존재하는 thread 중, 가장 큰 priority를 저장한다. 현재 thread의 priority가 list_priority보다 작다면, 현재 thread의 priority를 갱신한다.

void refresh_priority(void){
/* 현재 스레드의 우선순위를 기부받기 전의 우선순위로 변경 */
/* 가장 우선수위가 높은 donations 리스트의 스레드와
현재 스레드의 우선순위를 비교하여 높은 값을 현재 스레드의
우선순위로 설정한다. */
  struct thread* curr = thread_current();
  struct thread* t;

  curr->priority = curr->init_priority;

  if(!list_empty(&curr->donations)){
      list_sort(&curr->donations, &cmp_priority, NULL);
    int list_priority = list_entry(list_begin(&curr->donations), struct thread, donation_elem)->priority;
    if (list_priority > curr->priority)
      curr->priority = list_priority;
  }
}

void sema_up (struct semaphore *sema)

semaphore의 waiters list가 비어있지 않다면, 도중에 priority가 바뀐 경우를 대비해 waiters를 다시 한 번 정렬해준다.

thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem)) : sema의 waiters list는 오름차순 정렬되어 있다. 가장 큰 값을 가지는 thread의 elem을 waiters에서 pop한 후에 해당 thread를 unblock시킨다.(ready_list에 추가한다.)

sema->value++ : semaphore의 value를 1 증가시킨다. 다른 Thread가 접근할 수 있다는 신호이다! (sema_down함수에서 while문을 탈출하는데 사용된다.)

test_max_priority() : semaphore의 waiters list에서 pop하고, ready_list에 추가한 thread의 우선순위가 현재 running중인 thread의 우선순위보다 높다면 thread_yield함수를 실행해 running thread를 변경해줘야 한다.

void sema_up (struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT (sema != NULL);

    old_level = intr_disable ();
    if (!list_empty (&sema->waiters))
  { 
    list_sort(&sema->waiters, &cmp_priority, NULL);
    thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
  }
  sema->value++;
  test_max_priority();

    intr_set_level (old_level);
}

void sema_down (struct semaphore *sema)

현재 thread의 elem을 sema의 waiters list에 추가한다. 이때, priority를 기준으로 내림차순 정렬이 되게 삽입한다. 이후, thread_block()함수를 실행해 ready_list에 존재하는 다른 thread로 context switching이 일어난다. 따라서, 현재 thread는 thread_block()을 마지막으로 실행하고 실행을 멈추게 된다. 다른 thread가 sema_up을 통해 waiters list에 있던 thread를 깨우고(ready_list에 추가하고), semaphore의 value를 1증가하면 다시 thread_block()다음 줄을 실행하게 된다. 현재 while문 내에서 코드가 실행되고 있음으로, sema->value == 0해당 조건을 만족하는지 확인할 것이다. semaphore의 value가 1 증가되었음으로 while문을 탈출할 수 있고, while문을 탈출한 직후 semaphore의 value를 1 감소시켜, 자신이 사용중임을 알린다.

** 현재 각각의 thread가 sema_down()함수와 sema_up()함수를 실행하고 있다는 사실을 명심하고 코드를 읽어야 한다.

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_insert_ordered(&sema->waiters, &thread_current ()->elem, &cmp_priority, NULL);
        thread_block ();
    }
    sema->value--;
    intr_set_level (old_level);
}