악명이 자자했던 Pintos 주차의 시작...
처음엔 뭐부터 어떻게 해야 할 지 막막했지만, 일단 키워드부터 공부한 후에 과제 git book 찔끔찔끔 봤다.
(키워드는 일단 추후에 더 추가 공부하면서 정리해서 업로드 해야겠다 🥹...)
그러다가 옆 분반 분께서 kaist 교수님께서 과제 설명해주시는 강의 영상 보시냐는 말을 해주셔서 냉큼 어떤 영상이냐 묻고 사람들에게 전파하라고 해주셔서 고대로 단톡방에 보냈다.
근데 한 번에 정리된 링크가 있더라 (〃⌒▽⌒〃)ゝ
그 링크를 동료 분께서 단톡방에 올려주셔서 강의 자료 ppt도 다운 받을 수 있었다.
참고 링크 -> 이걸 올려도 되는지 모르겠지만, 구글링하면 나오는 링크니까 첨부해도 되겠지?
📍Project(1)의 첫 과제, Alarm-Clock 구현
main goal은 tick 시간 단위로 프로세스를 wakeup하는 시스템 호출을 구현하는 것.
Alarm Clock?
: 실행중인 스레드를 잠시 재웠다가 일정 시간이 지나면 다시 깨우도록 하는 OS의 기능Pintos 과제를 처음 clone 받아 실행하면 7개의 test case는 이미 passed 일 것이다.
(아마 alarm-priorty를 제외한 나머지 alarm case들과 mlfqs 중 2개가 passed 였던 걸로 기억한다.)
이 말은 이미 alarm-clock은 잘 동작한다. 그럼 우리가 풀어야 할 숙제는?
device/timer.c에 구현되어 있는 timer_sleep()은 busy-wait 방식이다.
sleep 명령을 받은 스레드는 계속 호출해 반복문을 돌며 현재 시간을 확인하고, 충분한 시간이 경과될 때까지 thread_yield()를 호출해 cpu를 양보하고 본인은 다시 ready_list의 끝으로 삽입된다.
즉, running state에서 sleep 명령을 받은 스레드는 ready state가 되어 ready_list에 추가되고, ready_list에 있는 스레드들은 자신의 차례가 되면 '일어날 시간이 됐는지'에 상관없이 깨워져서 running state가 된다.
이 때, running state가 된 스레드는 자신이 일어날 시간이 되었는지 확인하고 아직 일어날 시간이 안 됐다면
-> 다시 ready state으로 전환되어 ready_list로 들어간다.
이 말을 좀 더 쉽게 풀어 설명하면, 각각의 스레드가 sleep을 통해
'잠들고 - 깨어남 - 시간 확인 - 아직 일어날 시간 아님 - 다시 잠 - 깨어남 - ... - 시간 확인 - 일어날 시간 - 깨어남' 이런 식으로 스레드의 상태가 running <-> ready를 반복한다.
이를 그림으로 표현하자면 다음과 같다.
이와 같은 busy_wait 방식을 피하도록 수정해야 한다.
- How? 🤔
잠이 들 때 ready state가 아닌 blocked state로 sleep_list에 보내서 잠을 재운다. 그러다가 깨어날 시간이 될 때 해당 스레드를 깨워 ready state로 전환해 ready_list에 넣어준다.
그러니까 시간을 확인해 일 할 시간이 아직 안 된 스레드들은 깨어나야 할 시간(local tick)을 갖고, block state로 전환되어 잠에 든다. (sleep_list에 추가)
그러다 깨어나야 할 시간이 됐을 때 awake를 시켜 ready state로 전환하고 ready_list에 삽입해준다.
이를 그림으로 표현하자면 다음과 같다.
✨ Alarm-Clock을 구현할 때 많이 헷갈리는 점: local tick과 global tick
- local tick
: 각각의 스레드가 일어나야 할 시간으로, 변경되지 않는 값- global tick
: sleep_list에 들어있는 스레드들이 가진 local tick 중 가장 최솟값, 즉 가장 먼저 깨어나야 할 스레드의 local tick으로 sleep_list에 스레드가 push/pop 될 때마다 갱신된다.
사실 global tick이라는 이름 때문에, 현재 시간이라는 오해를 했는데 사실 이 global tick은 sleep_list를 scan해서 일어날 스레드를 찾는 시간을 save하기 위해 추가하는 개념이다. 그래서 sleep_list의 스레드들 중 가장 최솟값의 local tick으로 갱신해주는 것이다.
그렇기 때문에 global tick을 굳이 안 쓰고도 sleep_list에 local tick을 기준으로 오름차순 정렬이 되도록 구현을 한다면, global tick을 대입하지 않아도 된다.
🛠️최종적으로 우리가 busy-wait을 block-wakeup으로 수정하기 위해 건드려야 할 목록?
<수정사항>
1. thread_init(): sleep_list 구조체 선언/초기화 2. timer_sleep(): sleep_list에 스레드 삽입 3. timer_interrupt(): 모든 tick에서 일부 스레드가 sleeplist에서 awake 할 애 있는 지 확인 & 있다면 awake 호출해 깨우기 알아야 할 사항: timer_interrupt는 매 tick마다 호출된다.<추가사항>
1. 스레드 상태를 blocked로 설정하고 sleep_list에 삽입한 후 대기하도록 하는 함수 (thread_sleep()) 2. sleep_list에서 깨어날 스레드를 찾아 깨우는 함수(thread_awake()) 3. 스레드가 가지고 있는 최소 local tick값 저장하는 변수(global_t) 4. global_t 갱신/반환해주는 함수(update_global_tick() / get_global_tick())
사실 기본 구현&제공되는 함수/변수들은 git_book에 다 설명되어 있기 때문에 생략한다.
Pintos 구현 git Link
기존에 적혀있는 주석은 영어/내가 단 주석은 한글
alarm-clock으로 인해 수정된 파일 목록
-thread.c
-thread.h
-timer.c
+) 추가로 이렇게 busy-wait 방식을 block-wakeup 방식으로 수정 후 make check를 돌려도 똑같이 27개 중 7개만 통과될 것이다. 당연하다. 원래도 통과되던 것들을 수정한 거니까.
근데 무엇이 바뀌었냐? 그건 pintos -- -q run alarm-'testcase명' 으로 각각 돌리면 수정하기 전 과 후의 결과에서 idle tick이 늘어난 것을 알 수 있다.
idle thread란, 실행할 thread가 없으면 실행할 스레드다.
그러니까 그만큼 cpu가 촘촘히 일을 하고 놀 시간이 있었다는 의미로 받아들였다.
더해서 각 케이스에 대한 조건? 내용?을 정확하진 않지만 파악한 바로는,
- alarm-single: 5개 스레드가 각각 1번 깨야 만족(즉, 1번 tick 울리고 할 일 종료)
- alarm-multiple: 5개 스레드가 각각 7번 깨야 만족( 즉, 7번 tick 울리고 할 일 종료)
- alarm-simultaneous: 3개의 스레드가 각각 5번 깨야 만족하는데, 각각 10ticks를 잔다. 즉 모든 thread가 같은 tick에서 일어난다 (동시에 tick을 울리는 거지)
- alarm-priority: 우선순위 순으로 실행되도록
- alarm-zero: 실행시킬 스레드가 없을 경우
- alarm-negative: t=-100으로, 근데 t는 unsigned int라 비음수여야 함?? 아무튼 의미없는 값을 넣었을 경우