[PintOS] Project1: WIL

WIL

Project1 요약 정리

Pintos Project1이 끝났다. 첫 주차를 마치고서 정리하는글을 써보려고한다. 이 부분은 링크를 참고하길 바란다.

1. 시작 전 개념 정리

   • 운영체제란?
   • 프로세스와 스레드
   • 프로세스관리

2. 과제

   • Part1 Alarm clock
   • Part2 Priority Scheduling
   • Part2 Priority Scheduling and Synchronization
   • Part2 Priority Inversion Problem
   • Option MLFQ Scheduler
     

Project1 고민한 것들

• [PROJECT 1.1] Alarm Clock
  • 어떤 스레드가 sleep하게 되는가?
    • 공유 자원 A가 필요한 상황인데, 그 A를 다른 스레드가 사용중인 경우. (상호배제)
  • 언제 sema_up을 하는가? wake up을 하는가? (둘이 동일한 말인지 알아보기)
    • 의견 1: ready list가 비었을 때만 깨워야 한다.
      • starvation이 불가피함.
    • 의견 2: time slice로 설정된 4 ticks마다 깨워야 한다.
      • 현재 실행중인 스레드가 4 ticks보다 CPU 점유 시간이 짧을 때, 할 일 끝내자마자 바로 sleep list에 있는 다음 스레드를 ready로 올려줘도 되는데 굳이 4 ticks 까지 기다렸다가 깨우므로, cpu가 낭비됨.
    • 결론 :
      • 매 tick 마다 cpu를 넘겨줄지 말지를 확인해주는 것이 좋겠다고 판단.
  • 매 tick마다 sleep list를 모두 순회하는 것이 정말 최선인가?
    • 의견 1: 정렬해서 순회 필요 여부를 판단하자.
      1. sleep list를 순회할 때 알람 시간순으로 정렬
         • 한 스레드의 알람 시간 = sleep 호출 당시 ticks + sleep tick
      2. 맨 앞 스레드의 알람 시간 ≥ 현재 ticks 일 때만 sleep list를 순회하며, blocked → ready list로 올려준다.
      • 그러나 이 방법도 매 tick마다 정렬해야하므로 비효율적이다.
    • 의견 2: sleep list의 최소 알람시간으로 순회 필요 여부를 판단하자.
      1. 알람시간의 최솟값을 나타내는 전역변수 선언
         • int64_t MIN_alarm_time = INT64_MAX;
      2. 새로운 스레드를 sleep list로 넣을 때 알람시간의 최솟값을 갱신
      3. MIN_alarm_time ≥ 현재 ticks 일 때만 sleep list를 순회하며, blocked → ready list로 올려준다.
      4. 이 때 최소 알람시간을 가지고 있는 스레드는 무조건 삭제된다. 따라서 new_MIN 변수를 두고, list 순회와 동시에 남은 스레드들 중 최솟값을 저장한다.
      5. 순회를 마치면 MIN_alarm_time 을 new_MIN 으로 갱신한다.
      • 이 방법이 가장 효율적이라고 생각하고, 최적화 & 구현 완료!
  • list_begin 과 list_front의 차이로 인한 버그 해결
    • list_begin

      /* Returns the beginning of LIST.  */
      struct list_elem *
      list_begin (struct list *list) {
      	// 리스트가 초기화도 안 된 NULL일 경우 assert error
      	ASSERT (list != NULL);
      	return list->head.next;
      }

    • list_front

      /* Returns the front element in LIST.
         Undefined behavior if LIST is empty. */
      struct list_elem *
      list_front (struct list *list) {
      	// 빈 리스트(head & tail은 있음)일 경우 assert error
      	ASSERT (!list_empty (list));
      	return list->head.next;
      }

    • 위 코드를 보면 list_front는 list에 head와 tail만 있어도 에러를 일으키는데, 우리가 사용하고자 하는 함수는 head와 tail만 있는 빈 리스트일 때 에러가 나면 안된다.
    • 그래서 list_front → list_begin으로 변경하여 해결했다.
• [PROJECT 1.2] priority scheduling
  • 우선순위가 높은 스레드를 어떻게 찾아서 먼저 ready 리스트로 올려줄 것인가?
    • 우선순위를 기준으로 정렬해서 맨 앞 스레드를 뽑으면 된다.
  • 그럼 정렬은 어떻게 해줄 것인가?
    • 의견 1: 최소 힙을 구현해서 정렬하자.
      • list.c에 이미 list 정렬 관련 함수가 구현되어 있으니 활용하기로!
    • 의견 2: unblock 시 ready list를 정렬해서, 맨 앞 스레드를 뽑자.
      • 활용할 함수 : list_sort()
      • 시간 복잡도 : Runs in O(n log n) average case
    • 의견 3: ready list 삽입 마다 정렬된 상태로 유지하고, 맨 앞 스레드를 뽑자.
      • 활용할 함수 : list_insert_ordered()
      • 시간 복잡도 : Runs in O(n) average case
    • 결론 : 시간 복잡도가 작은 방법인 의견 2로 최적화 & 구현 완료!
  • 정렬을 삽입 시에만 해줘도 될까? 중간에 우선순위가 바뀌는 경우가 있을까?
    • 처음에는 ‘이 과제까지는 우선순위가 변경되지 않으므로, 변경 시 재정렬 문제는 고려하지 않아도 된다.’ 고 판단
    • backtrace로 함수 호출 스택을 살펴보니, 테스트케이스에서 우선순위를 변경해주는 함수를 호출해서 확인하고 있었다.
    • 그래서 이상한 Priority 값이 자꾸 찍히는 이슈 발생
  • 디버깅에서 어려움을 겪은 부분
    • 이상한 Priority 값이 나오는 이유가 도대체 뭘까?
      • bug 1: list_entry 함수의 offset 설정 오류
        • list_entry
      • bug 2: 테스트케이스에서 사용하는 thread_set_priority() 함수
        • 이 함수는 강제로 스레드의 우선순위를 변경한다.
        • 우리의 문제 : priority 변경시 init_priority 를 함께 변경하지 않음
        • priority 변경이 이루어지면 init_priority도 당연히 변경되어야 한다. 단어 의미 그대로 초기 우선순위 값이고, donate 받아 priority가 임시로 바뀌었을 때, 원래 priority로 돌아가기 위한 변수가 init_priority이기 때문이다.
    • list가 비었을 때를 검사하는 방법의 문제

      // 틀린 코드
      if (&thread_current()->donations != NULL)
      
      // 옳은 코드
      if (!list_empty(&thread_current()->donations))

      • 틀린 코드에서는 빈 list의 의미가 NULL이다.
      • 옳은 코드에서는 빈 list의 의미가 head&tail만 가지고 있는 것이고,
      • 우리가 원하는 빈 리스트는 후자의 경우에 해당하기 때문에, 수정해서 해결했다.
  • Donation 대상을 찾아서, 실제 donate를 할 방법이 뭐가 있을까?
    • 현재 스레드가 lock_aquire(lock)한 lock→holder를 찾아가 donation한다. donation이 이루어지지 않으면 priority inversion 문제가 발생할 수 있다.
  • Donation 대상의 범위는 어디까지인가?
    • lock→holder 뿐만 아니라, lock→holder→donations 에 있는 모든 스레드까지 donation이 이루어져야 한다. 그렇지 않으면 starvation 문제가 발생할 수 있다.
  • condition 개념이 도대체 뭔가? Priority Scheduling-Synchronization 부분에서 lock, semaphore, condition variable 개념을 공부할 때 구조에 대해 이해하는 것
    • 모니터 : 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태, 고급 언어의 설계 구조물3. 우선순위 donation 스케줄링 : 우선순위가 낮은 스레드가 점유중인 lock을 우선순위가 높은 스레드가 호출하였을때, 우선순위 역전을 막기위해 우선순위 낮은 스레드에게 해당 높은 우선순위를 상속해주는 스케줄링
      
  • pid kill 관련 내용추가
  • 구조체와 포인터의 장점을 체감했다.
    • lock의 holder로 연쇄적으로 찾아가는 방법에서 특히!
    • python에 포인터가 없어서 불편하다는 말이 이제는 이해된다.
• [PROJECT 1.3] priority scheduling with MLFQ
  • 우선순위를 어떻게 정렬할 것인가?
    • 우선순위는 스레드 생성부터 종료까지, 스케줄링 정책에 따라 가변적이다.

어려웠던 점과 느낀점

처음엔 어떤식으로 접근해야 하는 것에 대한 어려움이 있었다. 다른 팀은 코드의 흐름을 먼저 파악한다던지 개념을 먼저 본다던지 각기 다른 방식으로 팀의 색깔에 맞게 진행되는 것 같았다.

우리 팀은 개념을 먼저 보고 난 후 코드를 보기로 했다. 개념을 보고 난 후 코드를 보니 막연했다. 개념으로 봤던 것이랑 아주 다른 세상(?)이였다. 코드를 보면서 이해하는 시간도 많은 시간을 할애한 것 같다.

1주일 동안의 Project1이 끝나고 엄청난 양의 내용이 지나갔다. 왜 Pintos가 어렵다고 하는지 알게되었던 1주일의 시간이였던 것 같다.

PintOS Project1 GIthub 주소 PintOS