2022. 11. 18. 00:10ㆍ카테고리 없음
알고리즘 주가 끝나고, C언어에 대한 습득도 끝나고, 대망의 Pintos 프로젝트에 들어와서 첫 주차 알람 / 스케쥴링 부분을 공부하고 난 후, 내가 깨달은 것들을 여기에 남기고자 한다.
1. Round-Robin 방식 및 기존의 timer_sleep()함수
처음에 Round-Robin 방식에 대해 이해가 잘 안 되어서, 여러 블로그와 자료를 찾아봤는데 pintos에서의 Round-Robin 방식과 timer_sleep()함수를 제대로 설명한 곳이 없어서 난감했다. 여러 고찰(???) 끝에 제대로 이해한 것은 아래와 같다. ㅜㅜ
1) thread 구조체에서 status가 THREAD_READY인 스레드들은 ready_list라고 부르는 큐에 들어가있다. 하드웨어타이머에서 발생되는 타임 인터럽트가 도달하면, 이 인터럽트에 따라 timer_interrupt()를 통해서 ticks를 1씩 늘려주고 카운트를 해주게 된다. 또한, TIME_SLICE는 4틱으로 정의되어있는데, thread_tick()에서는 이러한 4틱마다 한 번씩 현재 스레드 (CPU를 점유하고 있는 스레드)가 CPU를 포기하게 만든다. 또한 ready_list의 가장 앞에 있던 (head 다음) 스레드가 CPU를 갖게 된다. CPU를 포기한 스레드는 ready_list의 맨 뒤 (tail) 앞으로 들어가게 된다.
예를 들면, 1번 스레드가 30틱 만큼을 일해야되는데, 4틱만 일하고 26틱을 남긴 상태로, 2번 스레드에 양보한다. 그리고 ready_list 맨 뒤로 들어가게 된다.
2번 스레드는 40틱 만큼 일해야한다고 치면 또 4틱만 일하고 36틱을 남긴 상태로 또 교체되어 레디리스트 맨 뒤로 들어가는 식이다. 계속 CPU 선점 스레드를 교체해줘야되기 때문에 전력소모도 심하고, 스레드들의 중요도에 상관 없이 공평하게 돌아가면서 배분하는 방식이라 어느 측면에서는 비효율 적이다.
2) 여기에서 timer_sleep(ticks) 함수는 어떻게 구현되어 있을까?
일단 여기에서 들어가는 parameter는 CPU를 재우고 싶은 ticks이다.
while (timer_elapsed (start) < ticks)
thread_yield ();
위의 코드를 보면, 스타트로부터 경과한 ticks( = timer_elapsed(start) ) 만큼, 반복하여 현재 스레드(CPU를 점유한 스레드) 를 계속 ready_list의 맨 앞 스레드에게 양보하고, ready_list 맨 뒤로 들어간다. 만약에 while문의 한 cycle이 0.1 tick 걸린다고 생각해본다면, 40ticks가 변수로 들어왔을 때, 1 tick에 10번 씩, 40 ticks 동안 400번 CPU를 선점한 스레드의 교체가 일어나게 된다. 당연히 CPU는 일을 제대로 할 수 있는 상태가 아닌 것인데, 스레드를 계속 교체하느라 전력소모는 발생하는 상황인 것이다. 스레드들도 유휴 상태인 idle이 아니라, kernal 상태 (일하는 상태)이다.
이것을 해결하기 위해서 sleep-queue를 도입하고, 우선 순위에 따른 queue 정렬 방식도 도입, 그리고 우선순위가 높으면 낮은 스레드가 점유한 CPU를 뺏을 수 있게 한 것임을 제대로 이해할 수 있었다.
2. Donation은 왜 도입되었는가?
우선순위 31짜리 스레드(1)가 자원 A를 점유한 상태로 CPU를 원한다고 생각해보자.
(여기에서 부연설명을 하자면, 자원 A를 사용해서 CPU를 돌린다고 생각하면 편하다.
자원 A를 점유하고 CPU를 점유하지 못한다면, 자원을 점유한 상태로 ready_list에 있게 되고,
자원 A를 점유하지 못하고, CPU를 점유한다면, 여전히 CPU를 돌리지 못하고 (이 때 semaphore의 value 값은 0) sema_down()함수에 의해서 waiters 리스트에 넣어지고, 블락된 상태로 멈춰버리게 된다. )
여기에서 우선순위 33짜리 스레드(2)또한 자원A를 필요로하는 스레드라고 해보자. 여기에서 스레드(2)는 우선순위가 스레드(1)보다 크므로 CPU를 차지하게 된다. 여기에서 스레드(1)은 자동적으로 ready_list의 맨 뒤로 들어가게 된다. 여기에서 스레드(2)가 CPU를 무사히 돌릴 수 있을까? 자원 A가 있어야 CPU를 돌릴 수 있으므로, 자원 A에 대한 lock을 요청하게 되며 이미 스레드(1)가 lock을 걸어둔 상태이므로, lock_acquire() 함수의 sema_down()에서 세마 값이 0인 상태에서 block이 되며 waiters에 대기하게 된다. 따라서 CPU를 양보한 상황이 된다.
이 때 자원 B를 필요로 하거나, 자원이 필요없는 스레드(3)이 있고 우선순위가 32라고 해보자. 이 스레드가 CPU를 차지하게 된다면, 우선순위가 33인 스레드(2)보다 먼저 CPU를 차지한 것이기 때문에 우선순위 원칙이 위배되게 된다. 우선순위 32짜리의 스레드가 100개가 더 있다고 하면 스레드(3)은 계속 CPU를 다 쓰고 난 후, 스레드(1)에게 양보하지 않고 우선순위 32짜리 스레드들에게만 양보할 것이다. (여기에서 스레드 (1)의 작업이 다 끝나고 자원 A를 반납해야 스레드 (2)가 자원 A를 획득하여 CPU를 돌릴 수 있다.) 이에 따라서 스레드(2)가 컴퓨터 종료 시까지 계속 CPU를 차지 못하는 상황이 발생할 수도 있기 때문에, 도네이션의 방법이 나오게 된 것이다!
아래는 이번주에 느꼈던 부분들을 정리하고 발표했던 내용으로 첨부하며 글을 마친다!
