이번 글은 정보를 전달한다. 그러니, "PintOS 내용은 됐고~ 일기나 줍쇼!"라는 생각이 든다면?
여기를 가보자.
내가 가장 잘 참고했던 블로그는 여기다. 하지만 코드가 다 나와있어 스포가 되니 코드를 안보고 싶은 사람들은 실눈으로 보면 된다.
이번에는 내가 PintOS를 진행하며 생각한 것들에 대해 정리를 해보려고 한다.
PROJECT 1 : THREADS
<< Alarm clock. Priority Scheduling >>
이번주에는 thread와 관련된 부분을 구현하면 되는 것이었다.
조금더 세부적으로 단계를 나눠보자면
1. Alarm clock
2. priority 기반 shceduling
3. priority scheduling - synchronization
4. priority inversion problem
이렇게 진행된다.
나는 해당 부분을 설명하기보다는 왜 이런게 나왔나?에 초점을 두었다.
Alarm clock
Alarm이란 "호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수" 이다.
Alarm에는 두가지 방식이 존재한다. busy-waiting방식과 sleep/wakeup 방식.
현재 PintOS는 busy waiting 방식으로 구현되어있고, 우리는 sleep/wakeup 방식으로 바꾸는 것이 목표이다.
괜히 바꾸는 것이 아닐 것이다. 무언가 좋은 점이 있기 때문에 바꾼다는 것을 인지해야 하고 그 좋은점이 무엇인지부터 알아보는 것이 코드를 구현하기 전에 선행되어야 하는 작업이라고 생각한다.
busy waiting VS sleep/wakeup
busy waiting이 무엇인지부터 알아보자.
ready list에 3개의 스레드가 있다고 해보자.
첫번째 스레드는 10초부터 일을 시작하고,
두번째 스레드는 8초부터 일을 시작하고,
세번째 스레드는 15초부터 일을 시작한다고 해보자.
ready-list에 있는 스레드에는 cpu가 할당된다.
지금은 3초라고 생각하자. 첫번째 스레드를 두들겼는데 아직 실행되는 시간이 아니므로 두번째 스레드에게 cpu가 양보가 된다. 근데 아직 8초도 안돼서 세번째 스레드에게 cpu가 양보된다. 근데 세번째 스레드도 아직 실행될 시간이 아니라 다시 첫번째 스레드에게 cpu가 양보된다. 이렇게 계속 반복하다보면 어느 순간 일을 시작할 수 있는 스레드가 발견될 것이다. cpu가 바쁘게 문을 두들기고 다닌다. 할일이 많은 애인데 어짜피 아무일도 못하는 스레드 문을 두들기고 있는 상태 인것이다. 언뜻 봐도 비효율적이어 보인다.
한줄 요약
아무것도 안하는 애인데 cpu를 잡고 있다. -> 비효율적
cpu 비싸!!! 효율적이게 만들어보자! 어떻게?
한줄 요약
아무것도 안하는 애는 cpu를 잡지 못하게 하자! -> 그 사이에 cup가 다른 일을 할 수 있다.
아무일도 일안하는 애들이 ready_list에 있어서 문제인것이다. 그럼 ready_list말고 다른 list를 만들어서 거기에 넣자!
여기서 다른 list가 sleep_list이다.
가장 빨리 일을 시작하는(가장 빨리 일어나는) 스레드의 시작시간을 알아낸후 저장해두고, 현재 시간이 그 시간과 일치하면 그 스레드를 ready_list로 옮기면된다!
참고로 나는 여기서 busy-waiting이 spin-lock과 같다고 생각해서 큰 고난을 겪었다... spin-lock이 busy-waiting 방법은 맞지만 busy-waiting이 spin-lock은 아니다.
priority 기반 scheduling
cpu가 다음에 어떤일을 할지 결정해주는 것이 scheduling이다. scheduling 방식에는 여러가지가 존재한다.
FCFS(First Come First Served), SJF(Shortest Job Fisrt), Shortedst reamaining time first, Round-robin, Priority Scheduling 등등등...
이러한 방식들엔 각각의 장단점이 다 존재한다.
예를들어 FCFS는 도착한 순서대로 처리하는 것인데 앞에 엄청 오래걸리는 애가 있고 뒤에 잠깐이면 되는애가 도착하면 매우 비효율적일 것이다.
SJF는 가장 짧은 스레드를 우선처리하는 것인데 이렇게 되면 기아 상태가 발생될 수 있다.
Round-robin은 주어진 타임슬라이스 주기로 스레드들은 선택하는 방식인데, 타임 슬라이스가 작을때 스케줄링 오버헤드가 커진다.
우선순위는 각 스레드들마다 우선순위를 정해두고 우선순위가 높은 순서대로 스레드를 선택하는 방법인데, 우선순위가 낮은 스레드에 한해 기아현상이 발생할 가능성이 있다.
pintOS에서는 지금 round-robin방식을 priority로 구현하는 것을 목표로 한다.
지금 단계(priority 기반 scheduling)에서는 일단 우선순위가 높은 스레드부터 처리한다.
우선순위 필드를 thread 구조체에 만들어주고, ready_list에 넣을때 우선순위가 높은 순서대로 저장한 다음, 항상 제일 앞 스레드에게 cpu를 할당하면 된다.
priority scheduling - synchronization
이 부분은 그냥 동기화 해주는 부분이다. 코드를 이해하기 힘들지 개념 자체는 어렵지 않았다.
priority inversion problem
priority inverssion problem은 multiple/nested의 경우 높은 priority의 thread가 낮은 priority의 thread보다 늦게 실행될 수 있는 문제점을 말한다.
이러한 문제를 해결하기 위해 나온것이 donation, 우선순위를 기부하는 개념이다.
이것도 개념 자체는 쉽다. 근데 알고리즘 적인 내용이 조금 추가 되어있는 느낌이다.
