[PINTOS] Project 1 - Threads 정리

생산성 code_snippet

1. (수정 필요. main thread만 구할 수 있음) 현재 돌고 있는 thread를 gdb에서 확인할 수 있는 방법은?
   • (gdb) p (struct thread )($rsp & ~(((1ul << 12 - 1) << 0)))

과제 logic flow 요약

Alarm Clock

1. reimplemented alarm clock 작동 시나리오(시간 순)
   • thread가 timer_sleep 함수를 호출해서 sleep_list에 삽입되어 깨어주기 전까지 더이상 ready_list에 들어가지 않게 된다.
   • 이후 ready_list에 들어있던 다른 thread들이 running 하다가, timer interrupt가 발생하면, timer interrupt handler 함수가 작동된다.
   • timer interrupt handler에서 sleep_list에 깨울 시간이 될 thread들이 있다고 판단하면 thread_awake 함수를 호출한다.
   • thread_awake 함수에서 sleep_list를 순회하며 깨울 시간이 된 thread들을 sleep_list에서 제거해주고, thread_unblock 함수를 통해 다시 ready_list에 삽입해줘서 scheduler의 고려 대상에 넣어준다.

Priority Scheduling

1. Overview(확실하지 않음. 이해가 개선되는 대로 업데이트 중)

   • 한양대 자료 기준 첫 번째 과제의 의미는 우선순위가 높은 thread가 cpu를 점유할 수 있도록 해줌
   • 한양대 자료 기준 두 번째 과제의 의미는 우선순위가 높은 thread가 synch primitive를 먼저 얻을 수 있게 해줌
   • 한양 대 자료 기준 세 번째 과제의 의미는 ????

2. Priority preemption(한양대 자료 기준 첫 번째 priority scheduling)

   • 다음은 semantic tree를 그리기 위한 가설설정이다. 우선순위 대로 scheduling 해준다는 것의 범위가 어디인가? 뭔가 소극적 스케줄링, 적극적 스케줄링 방법이 있을 것 같다. 예를 들어, 소극적 스케줄링이라고 하면, 지금 돌고 있는 thread가 원래 끝날 때까지 다 기다렸다가 그 다음 돌릴 thread를 고를 떄 우선순위가 높은 thread를 돌려주는 걸 생각해볼 수 있을 것 같다. 적극적 스케줄이라고 한다면, 지금 돌리고 있는 thread보다 우선순위가 높은 thread가 나타나면(혹은 삽입되면) 지금 돌아가고 있는 thread로 하여금 thread_yield를 하게 하고, 우선순위가 높은 thread를 running하게 하는 방법을 생각해볼 수 있을 것 같다.
   • 그렇다면 중요해지는 건 이 thread간의 우선순위를 비교하는 logic이 돌아가게 할 시점을 언제로 잡는가이다. 예를 들어, thread가 생성돼서 ready_list에 들어가는 시점이 trigger가 될 수도 있고, 아니면 기본적으로 scheduling하는 시점이 될 수도 있다.
     • thread가 ready_list에 들어가는 시점에는 언제언제가 있을까?
       • thread를 새로 생성해줄 때
       • BLOKCED인 thread를 unblocked 해줄 때
       • thread yiled를 하면서 기존 running thread가 다시 ready_list로 들어갈 때
     • 또 다른 중요 포인트는 ready_list를 우선순위에 따라 어떻게 정렬할 것인가? 어떻게 구현할 것인가? (개념은 쉽다. 우선순위 정렬.)

3. Priority Scheduling-Synchronization(한양대 자료 기준 두 번쨰)

   • 목적: 다음을 충족시키기 위한 구현:
     • gitbook: when threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be awakened first.
     • 즉, synchronization을 위해 block 중이던 thread들 중 synch 대기 줄에 먼저 선 thread들이 unblock 되는 게 아니라 우선순위가 높은 thread들이 먼저 unblock될 수 있도록 한다. 이와 더불어 unblock 되자마자 만약 current running thread보다 우선순위가 높다면 thread preemption을 할 수 있도록 한다.
   • 배경 지식 없이 문제를 보자마자 드는 생각: waiter_list가 semaphore별로 있을텐데, 모든 semaphore waiter list를 다 뒤져서 각각에 존재하는 최우선순위 thread들의 priority를 비교한다음에 가장 높은 thread로 하여금 CPU를 점유하게 해야 하나?
   • 질문
     • semaphore-elem이 왜 필요한가?
     • condvar는 semaphore랑 lock과 monitor 사이의 관계가 어떻게 되는거지?
       • condvar는 monitor의 구성요소이고, monitor에 대한 자세한 설명은 본 페이지 개념 정리에서 서술
     • interrupt handler가 lock을 얻을 수 없는 구체적 이유는 뭐지?
   • 솔루션 high-level 정리(test_priority_condvar 기준)
     • main thread가 서로 다른 priority를 가진 thread 10개를 차례 대로 생성하게 됨. 우선 한 개 thread가 생성되는 과정을 자세히 살펴보도록 하자.
     • 생성된 thread가 lock_acuqire를 하고, 이 테스트 케이스에는 딱히 access나 modify할 protected data가 없어서 곧바로 cond_wait을 함. 해당 thread는 자신 전용 semaphore_elem을 만들고 condition의 waiters에 자료형이 list_elem인 semaphore_elme.elem을 push_back(어짜피 cond_signal 때 sort 해줄 거라서 priority scheduling에 상관 없음)으로 집어넣음.
     • 그리고 sema_down을 통해 sema_elem에 들어 있는 semaphore의 waiters에 해당 thread의 list_elem이 들어가게 됨.
     • 이런 식으로 thread 10개가 모두 condition의 waiters_list에 들어가게 됨
     • 이후 main thread가 10번에 걸쳐 cond_signal을 날려주게 됨.
     • 우선 cond.waiters에 들어 있는 모든 semaphore_elem들을 priority 기준으로 내림차순 정렬해줌. 이때 cmp_sem_priority라는 무시무시한 정렬용 함수가 실행 됨. 이게 골 때리는 함수였어서 잠깐 자세히 설명하고 넘어가도록 함.
       • 자료형이 list인 cond.waiters에는 자료형이 list_elem인 semaphore_elem.elem이 저장되어 있다. 이 정보를 가지고 semaphore_elem을 도출해낸다. 도출해낸 semaphore_elem의 waiters 구조체에 들어있던 thread의 list_elem을 도출해낸다. 여기가 헷갈릴 수 있는데, cond_wait 함수에서 sema_down을 할 때 thread의 list_elem이 semaphore.waiters에 들어갔었다. 마지막으로 thread의 list_elem을 가지고 thread 구조체를 도출해내면 된다.
     • 다음으로 cond.waiters에 들어있던 semaphore_elem 중 주인 thread의 priority가 가장 큰 semaphore_elem의 semaphore에 대해서 sema_up을 해준다. sema_up을 해주면 과거 작성해둔 test_max_priority 함수에 의해, 만약 sema_up해서 ready_list에 들어가게 된 thread의 prirority가 현재 돌아가고 있는 thread보다 priority가 높다면 priority preemption이 이뤄지게 된다.

4. Priority Inversion Problem(한양대 자료 기준 세 번째)

   • 목적
     • priority scheduling에서 발생할 수 있는 priority inversion 문제를 해결하라
   • 문제 정의
     • priority inversion이 어떤 문제인가?: high priority thread가 medium priority에 밀려 장시간 동안 running을 할 수 없는 문제를 말한다. 이런 경우가 발생하는 상황을 보면 다음과 같다. high priority thread가 low priority thread가 선점한 lock을 요청해서 THREAD_BLOCKED인 상황이라고 하자. 이때 medium priority thread가 존재하고 오랫동안 실행이 필요한 thread라고 한다면, low priority thread가 cpu를 선점하지 못해 lock을 계속해서 release를 할 수 없게 되고, 그 결과로 high priority thread도 cpu를 선점하지 못하게 된다.
   • 솔루션 로직 흐름:
     • 위 문제를 해결하기 위해 priority donation을 한다. priority donation은 간단히 얘기해서, priority가 높은 thread가 priority가 낮은 thread에게 priority를 donate 함으로써 priority가 낮은 thread로 하여금 lock을 최대한 빠르게 release하게 하려는 전략이다. donate라고 하니 priority가 높은 thread가 자신의 priority를 잃게 되는 것 같이 보이지만, 사실 구현을 보면 priority가 낮은 thread의 priority를 donator의 priority로 일시적으로 격상시켜주는 것을 말한다. 당연하게도 low priority thread가 lock을 release하게 되면 더이상 high priority를 donate 받을 이유가 없어지기 때문에, 본래의 priority로 돌아간다.
     • 우리가 고려해줘야 할 donation의 방식은 2가지다: multiple donation과 nested donation. multiple donation은 쉽게 말해, low priority가 acquire한 lock을 acquire하려고 하는 higher priority thread들 모두가 lock의 소유자에게 자신의 priority를 donate하는 것을 말한다. 따라서 한 thread는 여러 priority donators를 가질 수 있다. 당연한게도 lock을 소유한 low priority thread는 priority donators 중 가장 높은 priority를 자신의 priority로 갱신한다. nested donation의 경우 lock의 관계가 chain처럼 이어져 있을 때, lock chain 상의 thread들 모두에게 higher priority thread가 자신의 priority를 donate 하는 것을 말한다. 다음과 같은 경우를 대비한다고 생각하면 된다. priority가 10인 Thread A가 lock A를 들고 있고, priority가 20인 thread B가 lock A를 acquire하려고 한다. 여기서 일단 priority donation이 한 번 발생해서 thread A의 priority는 20으로 격상됐다. 추가적으로 thread B가 lock B를 소유하고 있다고 하자. 이때 priority가 30인 thread C가 lock B를 acquire 하려고 한다. 이 경우 lock chain은 (lock A-lock B)이고, Thread C는 lock chain 상의 thread A와 thread B에게 자신의 priority인 30을 donate 한다. 이렇게 함으로써 lock chain 상의 최상위 lock인 lock A을 소유한 thread A가 최대한 빨리 lock release를 하고, 다음으로 thread B가 최대한 lock release를 하게 함으로써, 높은 priority인 thread C가 자신보다 낮은 priority를 가진 thread들 때문에 running할 수 없는 상황인 priority inversion을 피할 수 있게 된다.

미분류 질문

1. idle thread는 교육용 thread인가 아니면 실제 production-level OS에서도 쓰이는가?

   • 실제 winodws task manager에서도 idle thread가 있는 걸 확인함. idle thread가 없으면, CPU가 freeze 된다고 함.

2. system call이 비싼 이유가 뭐지? user thread간의 context switching보다 user thread와 kernel thread간의 context switching이 더 비싸기 때문인가?

3. list_remove 하고 나서 list_next 하면 undefined behavior가 나타날 수 있는 이유가 뭘까? list_remove가 앞 뒤로 연결

4. 각 종 tick(timer-tick, thread-tick) 들이 언제 increment하는지?

5. kernel stack은 어떻게 접근하는지 알겠는데(%rsp) local stack pointer는 어떻게 찾는거지?

6. thread 구조체를 보면 interrupt handler가 있는데 이거 중요한 것 같다. 어떤 역할을 하는거지?

7. thread가 뭐임? process랑 뭐가 다른거지?

8. thread를 scheduling 한다는 게 뭐지?

   • when a thread is created, you are creating a new context to be scheduled가 무슨 의미지?
   • thread_yield를 함수가 돌아가면서 interrupt가 꺼지게 되는데 어느 시점에 다시 interrupt가 켜지게 되는걸까? thread가 switch 되고 난 이후?

9. process state?

10. alarm-clock이 어떤 역할을 하는 거지?

    1. busy wait이 어떤 알고리즘이지?
    • busy wait이 왜 비효율적인거지? thread가 cpu를 점유하면서 대기한다고 하는데, 어떻게 cpu를 yield한 thread가 cpu를 점유할 수 있다는 거지?.
    • 우선 thread_yield()를 하게 되면 thread가 ready_list에 삽입된다고 함. 이게 큰 힌트가 될 듯.ready-state에 들어가는 거랑 sleep에 들어가는 거랑 다르고, 이게 CPU 점유 관련해서 어떤 큰 차이가 발생하는 듯
    • interrupt를 비활성화한다는 게 어떤 의미지?

11. interrupt level이 뭐지?

/* Interrupts on or off? */
enum intr_level {
	INTR_OFF,             /* Interrupts disabled. */
	INTR_ON               /* Interrupts enabled. */
};

1. threads 간에 resource share 시 발생할 수 있는 문제를 해결하기 위해 synchronization이 쓰인다고 함. threads 간에 resource를 share한다는 게 뭘 share 한다는 거지?

개념 정리 in my own words

• monitor
  • 모니터의 구성요소는 lock(a.k.a. monitor lock), protected data, one or more condition variables.
  • monitor는 semaphore나 lock보다 더 추상화된 synch primitive이다.
  • monitor는 lock의 기능에 condition이 추가됐다고 생각하면 쉽다.
• lock
  • lock은 1로 initialize한 semaphore와 lock holder로 구성된다.
  • lock은 semaphore를 1로 initialize했기 때문에 0으로 initialize 하는 semaphore와 성격이 다르다. 0으로 initialize한 semaphore의 경우 sema_down을 하는 thread는 누군가가 sema_up을 해주기 전까지 thread_block이 된다. 그래서 보통 정확히 한 번 발생하는 이벤트가 발생할 때까지 기다릴 필요가 있을 떄 0으로 initialize한 semaphore를 사용한다.
  • semaphore를 1로 initialize를 하게 되면 sema_down을 먼저 한 thread가 protected data에 접근할 수 있게 되고, 다음으로 sema_down을 시도한 thread들은 먼저 sema_down을 한 thread가 sema_up을 하기 전까지 semaphore.waiters라는 list에 무한 대기하게 된다. 따라서 shared resource에 thread_safe하게 접근하고 싶을 때 1로 initialize한 semaphore를 쓰게 된다.
  • 1로 initialize한 semaphore에 semaphore holder 정보가 추가된 게 바로 lock이다. lock을 소유하게 된 thread만이 lock을 release할 수 있기 때문에 누구든지 release와 유사한 up을 해줄 수 있는 semaphore와 차별화된다. 만약 semaphore holder가 누군지 식별되어야만 한다면 lock을 그렇지 않다면 1로 initialize한 semaphore를 쓰는 게 적절할 것이다.
• semaphore
  • semaphore는 nonnegative integer이고 down(aka Probeer meaning try in Dutch) and up(aka Verhoog meaning increment).
  • 보통 semaphore를 0으로 initialize 해서 많이 사용한다. 용도는 어떤 한 번만 일어날 이벤트에 대해서 프로세스가 synchronization을 하게 하기 위함이다. 예를 들어, A라는 thread가 있고 B라는 thread가 있다고 했을 떄, B가 어떤 이벤트가 끝나는 걸 알려줄 때까지 A를 기다리게 하고 싶은 경우가 있다고 하자. 이때 A에 sema_down을 걸어놓으면, A는 semaphore가 positive integer가 될 때까지 waiting에 들어간다. semaphore를 0으로 initialize 했기 때문에 A는 계속 기다리게 된다. 이떄 B에서 어떤 event가 끝나고 나서 sema_up을 해주게 하면, semaphore 의 숫자가 1이 된다. 동시에 sema_up은 waiting list에 있는 thread를 꺠워주게 된다. waiting list에 있던 Thread A가 깨어나고 semaphore를 살펴봤더니 양수가 된 것을 확인하고 다시 0으로 decrement 해주고 return 하게 된다.
  • semaphore를 어떤 resource에 대한 access를 통제하기 위해 쓰기도 한다. 예를 들어 semaphore를 1로 initialize 한다고 하자. 그리고 어떤 resource를 쓰고 싶은 thread A가 있다고 했을 때, A는 해당 resource를 쓰기 전에 semaphore를 down해준다. semaphore가 이미 positive number이기 때문에 A는 waiting list에 들어가지 않고, 바로 semaphore의 숫자를 낮춰서 0으로 만든다. 이 직후 만약 thread B가 해당 resource에 접그하려고 한다면 A와 똑같이 semaphore를 down 해주는 것으로 시작할텐데, 이미 semaphore가 0이기 때문에 waiting list에 들어가게 된다. 아무튼 A는 해당 resource에 대한 일종의 lock을 획득했고, 자기 업무를 마친 후에 semaphore를 다시 up해주게 된다. 다시 semaphore가 1이 되면서, A가 resource에 접근해서 작업하고 있는 동안 resource에 접근하려고 하다가 waiting list에 들어갔던 B가 깨어나게 되고 다시 semaphore를 1만큼 decrement하고 A와 같은 절차를 돌입하게 된다. 하지만 이런 목적의 경우 lock을 주로 적합할 수 있다고 한다.
  • semaphore가 1보다 더 크게 initialize 될 수도 있지만 그런 경우는 극히 드물다고 한다.

1. Process, thread, main 등의 관계 등에 대하여
   • 내 머릿속에 이제 어느 정도 그림이 잡혀가는 것 같다. 이건 보조 그림이 필요한데 우선 글로 먼저 남긴다. kernel도 하나의 프로그램이다. 이 kernel을 실행하게 되면 하나의 process가 된다. 왜냐하면 process는 running instance of a program이니까. 이걸 kernel process라고 하자. 프로세스이기 때문에 자기만을 위한 별도의 virtual memory address space가 생성된다. 메모리 주소가 낮은 곳부터 차례대로, text segment, data segment, heap segment, stack segment가 배정된다. 이 중 text segment와 data segment만 file-backed memory 영역이고, heap과 stack segment는 anonymous memory 영역이다. 아무튼 최초 loader에 의해서 stack의 맨 상위 영역에 stack main 함수를 작동시키기 위한 정보들이 올라가고 cpu가 실행시킨다. 이떄 init_thread를 통해 최상위 stack 영역부터 4kb에 해당하는 영역을 구분짓고 struct thread로 말끔히 포장한다. 이후에 생성될 thread들은 page allocating을 통해 stack을 차곡차곡 쌓아나간다.
   • thread는 unit of execution이다. 한 프로세스 내에는 여러 개의 thread가 존재할 수 있다. user process와 kernel process 모두 마찬가지다. 우리 PINTOS에서는 각 kernel thread는 4kb를 차지한다. user process에서의 thread의 크기는 또 다를 수 있다. 아무튼 각 thread는 다른 thread들과 전혀 다른 control flow를 가지게 된다
   • 각 kernel thread 내에서는 kernel stack이라고 해서, thread 내 control flow 과정에서 발생하는 function call들이 쌓이게 된다.
   • 우리 Pintos에서 kernel thread 생성은 thread_create로 이뤄진다. 참고로 user process에서 thread를 생성하는 건 pthread라는 걸 쓰게 된다.
   • Fork랑 pthread create는 완전히 다르다. 나는 이게 같은 거라고 착각했었다. thread create은 동일 process virtual memory space 내에서 thread가 할당되는 거고, fork는 아예 새로운 자식 process를 만들고 그만의 독자적인 virtual memory space가 생성되게 된다.

해결된 질문

1. 언제 semaphore를 쓰고 언제 lock을 써야 하는가?
   • lock은 semaphore를 1로 initialize 했을 때와 유사하다. semaphore의 up과 lock의 release가 유사하고, semaphore의 down과 lock의 acquire가 유사하다. 한 가지 큰 차이점은 semaphore의 경우 누구라도 up을 해줄 수 있지만, lock의 경우 lock의 owner만 release가 가능하다. lock의 owner만 lock을 release하는 게 문제가 되는 상황이라면 semaphore를 고려해야 한다. 그런데 구체적 예시 상황은 아직 잘 모르겠다.
   • PINTOS에서 lock의 실제 구조체를 까보면, semaphore가 나온다. lock_init 함수를 보면, semaphore를 1로 initialize하는 것을 알 수 있다.
2. void thread_yield(void) 함수(thread.c:298) 안에서 do_schedule 함수를 호출하기 전에 intr_disable 함수를 통해 maskable interrupts를 끄는 걸 확인했습니다. do_schedule 함수의 description을 봐도 At entry, interrupts must be off 라고 기술하고 있습니다. 이와 유사한 방식으로 잠시 interrupts를 끄는 경우가 소스코드의 여러 군데서 확인되는데 interrupts를 안 끌 경우 어떤 side effects가 있을지 생각하기가 어렵습니다. casys-kaist.github.io에 Synchronization 부록의 Disabling interrupts 안에서 다음과 같이 기술하고 있지만 여전히 어떤 side effects를 해소시켜줄 수 있는지 생각하기 어렵습니다:The main reason to disable interrupts is to synchronize kernel threads with external interrupt handlers, which cannot sleep and thus cannot use most other forms of synchronization.
   • 조교님 답변
     • interrupt를 disable하는 것은 cpu의 제어권을 interrupt가 다시 enable될 때 까지 넘겨주지 않겠다는 의미와 흡사합니다. 이러한 interrupt는 scheduling에 중요한 timer interrupt나 입출력 장치에 의해 발생하는 I/O interrupt등이 포함될 수 있습니다. interrupt disable을 남발하는 행위는 OS 자체의 response time을 증가시키는 등의 이유로 좋지 않은 디자인으로 평가받습니다. 이에 일반적으로 interrupt disable 대신 semaphore나 lock과 같은 synchronization primitive를 주로 사용하지만, project 1에서 다루는 do_schedule 함수 등 scheduling에 직접적으로 연관된 함수들이나, lock/semaphore를 사용할 수 없을 때 (예를들면 lock/semaphore를 구현해야 할 때)는 interrupt disable로써 synchronization을 확보합니다.
     • interrupt disable/enable과 이에 관련된 assert가 전부 없을때 발생할 수 있는 bug case 중 하나를 들어보겠습니다. 현재 thread가 thread_yield 함수를 통해 다른 thread에게 cpu 제어권을 넘기려고 시도합니다. 이 thread는 ready_list에 삽입되어 다음 scheduling을 대기합니다. 이때 ready_list에 thread를 삽입하기 위한 함수 list_push_back 은 여러 instruction으로 구성되어 있습니다. (https://github.com/casys-kaist/pintos-kaist/blob/ee7443d7ae850c7cb704db6e8213c5cb67cacd0b/threads/thread.c#L306) timer interrupt가 발생합니다. scheduling을 위해 intr_handler -> timer_interrupt -> thread_tick 함수가 호출되고, scheduler가 현재 thread가 yield가 필요하다고 판단하여 intr_yield_on_return 함수를 통해 interrupt handler 종료와 함께 thread를 yield하려 시도합니다. thread_yield 가 다시한번 호출되고, 여기서부터 많은 문제가 발생할 수 있습니다. 우선 현재 thread가 ready_list에 두번 삽입되어 logical bug를 일으킬 수도 있고, 최악에는 thread가 ready_list에 완전히 삽입되지 않은상태에서 (즉 list의 fd/bk가 완전히 연결되어있지 않은상태에서) 다시 ready_list에 접근하여 invalid memory access에 의한 kernel panic등이 발생할 수 있습니다.
     • 앞선 document의 설명에 추가적으로 설명드리면, lock/semaphore와 같은 synch primitive들은 thread/thread 간의 race condition을 방지하기 위해서 사용될 수 있으나, 위에 예시로 든 것과 같이 thread/interrupt handler 간의 race condition은 방지할 수 없습니다. 이러한 경우에는 interrupt disable을 사용하여 synchronization을 확보할 수 밖에 없습니다.
   • 답변 보고 내 정리
     • Disable interrupts를 직접적으로 사용해야만 하는 경우에 관하여 우선 Response time을 낮추기 때문에 interrupts를 아예 꺼버리는 방법은 가능한 피해야 합니다. 따라서 thread와 thread 사이의 race condition 방지를 위해서는 보통 semaphore나 lock 등과 같은 synch primitives를 사용해야 합니다.
     • 참고로 synch primitives의 내부 구현을 보면 사실 interrupts를 disable 해주는 작업이 들어갑니다. interrupts를 직접적으로 끄는 게 아니라 semaphore나 lock이라는 기법으로 감싸서 interrupts를 간접적으로 끄는 방법을 사용하는 이유는 다음과 같습니다. interrupts를 끄는 작업은 매우 low-level 작업이어서 안전장치가 없기 때문입니다. 예를 들어, 코드 어딘가에서 interrupts를 껐다가 실수로 다시 키는 걸 깜빡하면 response time이 크게 증가하는데, 컴파일 에러 혹은 런타임 에러가 발생하는 게 아니라서 수많은 코드 중 어디에서 interrupts가 꺼졌는지 코드를 다 뒤져보지 않는 이상 알 수 있는 방법이 없습니다. synch primitives의 경우 interrupts를 변동해줬다가 다시 최초 상태로 돌아가게 하는 것을 보장하기 때문에 보다 안전합니다.
     • 그런데, thread(특히 kernel thread)와 외부 하드웨어 모듈에 의해 발생하는 external interrupt handler 간의 race condition 방지에는 synch primitives를 사용할 수 없습니다. 왜냐하면 synch primitives의 경우 한 thread를 sleep(혹은 block)하게 함으로써 다른 thread와 race condition 들어가는 것을 방지하는데, external interrupt handler의 경우 interrupt가 발생하면 무조건 작동돼야 하기 때문에 sleep/block 상태에 들어가는 것이 불가능하기 때문입니다. 따라서 interrupt 자체를 꺼놔서 external interrupt handler가 절대 동작이 될 수 없게 함으로써 synchronization을 달성해야 합니다.
   • 최초 busy waiting 방식의 alarm clock이 어떻게 종합적으로 작동하고 왜 비효율적인가? 그렇다면 어떻게 바꿔야 하는가?
     • timer-sleep에서 thread_yield를 하면 current_thread가 blocked 상태가 돼서 인자로 넣었던 ticks 넘어설 때까지 잠자고 있는게 아니라, ready_list에 들어가서 계속 running -> yiled -> running -> yield 하면서 cpu time을 낭비하는 비효율이 발생.

pintos 소스코드 이해에 도움되는 지식 파편

1. priority inversion 문제 풀다가, thread에 donation만을 위한 elem을 만드는 게 굳이 필요한가 해서 그냥 기존 elem 멤버변수 썼다가 디버깅에 거의 2시간 이상 허비함. 기존 thread의 elem 멤버 변수의 경우 ready_list에서도 쓰이고 sema에도 쓰이기 때문에 donation 관련해서 쓸 경우 완전히 예측 불가능한 일들이 벌어질 수 있다. 별도의 기능을 담당한다면 별도의 list_elem을 만들어두도록 해야 한다.
2. 구조체 복사는 조심해야 한다. 기존 구조체를 가리키려면 포인터로 가리켜야지, 별도의 struct를 선언해서 받으면 안 됨. (cmp_sem_priority 함수에서 semaphore_elem.semaphore.waiters list를 struc list *로 받아야지 struct list로 받으면 안 됨) ,
3. 어떤 구조체나 항목들을 링크드 리스트에 주렁주렁 연결시키고 싶다면, 그 구조체를 감싸는 또 다른 구조체를 만들고 그 안에 링크드 리스트에 연결용 노드가 될 멤버를 추가해준다. 예를 들어, semaphore들을 주렁주렁 연결한 링크드 리스트를 만들고 싶다고 하자. 그러면 semaphore라는 구조체에 next, prev용 포인터를 만들어서 집어넣고 싶을 수 있다. 하지만 이런 식으로 특정 구조체에 next, prev element를 넣게 된다면, 각 구조체를 위한 링크드 리스트와 그를 위한 함수들을 다 만들어야 할 것이다. 왜냐하면 traverse를 할 때 안의 노드들이 모두 자료형이 달라서 각 자료형을 커버하기 위한 함수들이 필요하기 때문이다. 따라서 semaphore 안에 링크드 리스트의 노드의 요소를 집어넣을 게 아니라, semaphore를 감싸는 새로운 구조체를 만들어서 semaphore 구조체를 포함시키고, 그와 더불어 링크드 리스트 내 노드의 역할을 할 list_elem 구조체를 또 하나의 멤버로 넣는다. 그러면 이제 링크드 리스트에 semaphore를 넣을 게 아니라 semaphore_elem의 list_elem 구조체를 넣고, 만약 list_elem으로부터 semaphore 구조체를 도출해내고 싶을 때는 별도의 매크로를 통해서(pintos에서는 list_entry 매크로) 끄집어 낼 수 있게 할 수 있다.
4. Main thread라고 특별할 것 없다. THREAD_BLOCKED 될 수도 있으며, THREAD_RUNNING일 수도 있고, THREAD_READY일 수도 있다. 나는 MAIN_TRHREAD는 뭔가 특별해서, 최초에 ready_list에 들어갔다가 그 이후에는 다시는 ready_list에 들어갈 일 없을 거라고 그냥 단정지었는데, 생각해보니 그러면 설명할 수 없는 현상들이 많아진다. 예를 들어, test를 진행하고 있던 main_thread가 priority preemption 이후 thread block 되고 더이상 ready list에 돌아올 수 없다면 나머지 test 코드가 진행될 수 없음. 왜 이런 오해를 했는지 모르겠네.
5. Timer_interrupts는 1초에 100번 발생하도록 세팅(#define TIMER_FREQ 100). 대략 10ms에 한 번 timer interrupt가 발생한다.
6. ticks(이하 구분 위해 timer_ticks)는 timer interrupt 발생할 때마다 1씩 올라간다. 이와 동시에 thread_ticks와 (idle_ticks or user_ticks or kernel_ticks) 중 한 개가 같이 올라간다. ticks의 경우 timer_interrupt함수에서 올라가고, 나머지들은 thread_tick함수에서 올라간다.
   • thread_ticks를 추적하는 이유는 한 thread가 최대 4 ticks 이상 CPU를 점유하는 것을 막기 위함이다(#define TIME_SLICE 4). 참고로, 특정 thread가 scheduling을 통해 current running thread가 되는 순간 thread_ticks는 0으로 초기화된다. 그리고 thread 본인이 thread_yield를 하지 않는 이상 계속해서 thread_ticks가 증가하게 된다. 이를 보다 못한 timer interrupt handler는 thread_ticks가 4가 되는 순간 yield_on_return 전역변수를 true로 변경시킴으로써 timer interrupt handler가 return 하는 순간 thread_yield를 호출해서 강제로 현재 thread의 CPU 점유권한을 빼앗는다.
   • timer interrupt는 timer 기계에 의해 발동되며, timer interrupt가 발동할 때마다 ticks가 올라간다. 매 틱마다 interrupt handler는 여러 일 처리를 한다. 예를 들어, sleep_list에서 자고 있어야 하는 애들을 깨워서 ready_list에 보내준다든지, 혹은 어떤 특정 thread가 너무 많은 ticks 동안 cpu를 점유하고 있던 건 아닌지 등을 체크한다.
   • idle_ticks와 user_ticks와 kernel_ticks로 나누는 이유는 TIMER_TICKS를 보다 세세하게 구분해서 파악하기 위함이다. 즉, 각 종류의 thread별로 CPU를 얼마나 점유하고 있나 대강 보기 위함이다. timer_interrupt가 발생한 시점에 CPU에서 kernel_thread가 돌아가고 있었다면 kernel_ticks가 올라고, user_thread가 돌아가고 있었다면 user_ticks가 올라간다. idle_thread이 경우도 사실 thread_kernel이지만 CPU가 idle한 상태인지를 별도로 체크하기 위해서 idle_ticks라는 전역 변수로 별도 관리한다.
7. thread_ticks는 가장 마지막 yield 때 schedule 함수가 호출되면서 0으로 초기화되고, timer_ticks가 올라갈 때마다 같이 올라간다. thread_ticks가 TIME_SLICE(여기서는 4) 이상이 되면, timer interrupt가 return 하면서 thread_yield가 호출된다. 이 호출로 cpu를 점유하고 있던 thread는 cpu 점유를 양보하게 된다.
8. 잠깐 용어 정리: kernel process의 virtual space에 존재하는 모든 thread는 kernel thread이다. 그 중 main thread와 idle thread 모두 kernel threads이다. 이외의 기타 kernel thread를 그냥 kernel thread라고 부르기로 한다.
9. idle_thread는 어떤 목적으로 존재하는 거지?
   • ready_list가 비어있을 때 idle_thread가 돌아가기 시작한다.
   • 만약 idle_thread가 없다고 가정하자. 그리고 현재 main thread와 main thread가 initiate한 kernel thread가 있다고 하자. kernel thread가 sleep 상태에 들어가면 CPU를 돌릴 또 다른 thread를 ready_list에서 구해와야 한다. 왜냐하면 CPU는 뭔가 계속 일을 하고 있어야 하고, 아무것도 할 일이 없을 때 지금 지식 수준으로는 무슨 unintended action이 벌어질지 모른다. 아무튼 만약 main thread를 돌려버린다면, thread_exit 함수를 호출하면서 커널이 꺼지게 될 것이다.
10. kernel.o로 대표되는 kernel process가 있고, 그 안에 낮은 메모리부터 시작해서 text, data, heap, stack이 있다. main이 stack의 최상단에 쌓이고 그 밑으로 idle thread가 쌓이기 시작한다.
11. intr_context 함수가 필요한 이유
    • external interrupt가 processing 중에는 다른 작업들이 이뤄져서는 안 된다. 예를 들어, external interrupt가 진행 중에는 interrupts가 disable되게 되는데, 이때 thread_yield 같은 상황이 발생하면, context switching이 강제로 일어나면서 interrupts가 영영 다시 안 켜지게 될 수 있다.
    • 따라서 에러를 막기 위한 목적으로 thread_yield 함수를 보면 ASSERT(!intr_context())와 같이 external interrupt context가 아닌 것을 확신한 이후 thread_yield 코드가 진행되게 된다.