정글[Week_09]: Pintos의 스레드 알고리즘을 설계하다

정글에서 꽃이라 불리는 과정, pintOS에글에서 꽃이라 불리는 과정, Pintos에 입문하게 되었다. 기대와 우려가 반반 섞이면서.. 팀원들과 함께, 빠진 로직을 하나하나 보강해 나가는 프로젝트이다. 카이스트에서 제공한 깃 페이지와, 미완성된 pintos 프로그램을 바탕으로, 빠른 학습력을 바탕으로 빈 곳을 메워야 한다.

 

 

Pintos는 4개의 프로젝트로 나눠져 있다

Pintos는 운영체제에 대한 이해를 목적으로 만든 프로젝트라고 한다. 팀원들은 Pintos가 분명 단계적인 수행 과정이 있을 것이라 생각하였고, 그분들의 서칭 능력 덕분에, 4개의 프로젝트로 나눠진다는 것을 확인할 수 있었다. 4개의 프로젝트는 다음과 같다:

1. Threads: 스레드 알고리즘을 설계하여 테스트를 통과해야 한다.
2. User Programs: 스레드가 들어간 프로세스를 다루는 과정.
3. Virtual Memory: 가상 메모리를 관리하는 알고리즘을 구현해야 한다고...
4. File System: 저장소에 접근하고 읽기/쓰기 로직을 구현하는 것으로 보인다.

여기서 우리가 수행해야 하는 프로젝트는 1 ... Threads이다. 프로그램의 업무 단위인 스레드, 이들이 어떻게 사용되고 교체되는지 학습하고 구현하는 것이 목표라 하겠다.

 

 

Thread의 생명주기를 바탕으로 구현하자

 

스레드의 생명주기

스레드는 처음부터 컴퓨터에서 생성되고 꺼질 때 까지 지속되지 않는다. 하나의 프로그램이 실행되는 와중에도 각 업무를 수행하는 스레드가 생성되고 종료되기를 반복한다.이 과정을 스레드의 생명주기라고 하는데... Pintos에서 이 주기에 맞춰 구현해야 하는 영역이 구석구석이 포진하고 있다. 다만, Pintos에서는 조금 차이가 있는데, 전반적인 내용을 짧게 기술을 하자면 다음과 같다:

Running: CPU 코어를 점유하고 있는 상황이다. 경우에 따라서는 강제로 yield .. 즉 타 스레드에게 양보를 해야 할 때도 있다.
Ready_list: CPU 코어에 들어가기 전 대기를 타는 스레드가 여기에 큐 형태로 쌓여있다. Schedular에서 호출하여 코어로 옮긴다.
Sleep_list:말 그대로 잠드는 스레드이다. 필요에 따라 Ready_list에 옮긴다.
Wating: 세마포어라는 객체에 들어가 있는 list 자료구조이다. 스레드가 Blocked 될 경우, 여기로 들어간다.

 

 

Thread의 생명주기를 결정하는 요소: Lock & Priority

스레드가 선점하고 양보를 하려면 무언가의 기준이 필요하다. 이 기준은 다양하겠으나, 대표적으로 Lock과 Priority가 있다. Priority는 말 그대로 "우선권"을 의미한다. 만약 현 코어를 점유하는 스레드보다 Ready_list의 스레드가 우선권이 높다면, 높은 스레드에게 즉시 yield.. 양보하는 로직이 가동된다. 

Lock의 경우 좀 다르게 작용을 한다. Lock은 우선권을 넘어 일종의 "독점권"이라고 생각을 하면 편한데, 만약 이 Lock을 획득한 스레드라면.. 타 스레드가 그 Lock을 획득하기 전 까지는 코어를 점유하고 있게 된다. 다만, Lock은 공유자원을 함께 사용하는 스레드에게 한정이 되는데, 스레드에 따라 본인이 코어에서 연산과정을 수행하면서 사용할 데이터들(예를 들어 힙 영역)이 겹칠 경우에는 그 스레드들 사이에서 Lock이 발동된다고 이해를 하였다.

이 뜻은, Lock의 독점권 또한 Lock을 공유하는 일부 스레드들 사이에서만 일어난다는 것이다. Lock을 사용하지 않는, priority가 높은 스레드가 만약 선점을 요청한다면? CPU의 흐름은 생각보다 복잡해진다. 대표적인 예시로 Priority Inversion(우선순위 역전)이 있는데, 아래에서 살펴보자.

 

 

Priority Inversion(우선순위 역전)

우선순위 역전은 단어 그대로.. 높은 우선순위(priority)를 가진 스레드가 먼저 코어를 점유하지 못하고, 계속 뒤로 밀려나는 현상을 말한다. 이해를 돕기 위해, 아래 이미지를 가져와보았다.

우선순위 역전 현상

여기 그림에서 L 스레드와 H 스레드는 같은 Lock을 공유하는 스레드임을 알 필요가 있다. Lock을 공유할 경우, H 스레드가 우선순위가 높더라도... L이 획득한 Lock을 넘겨받지 못하면 block상태가 되어 waiting 리스트에 대기하게 된다. 그러나 Lock을 공유하지 않는 M 스레드는 단순히 L 스레드 보다 우선순위가 높다는 이유로 코어 선점이 허용이 된다. 결과적으로 가장 우선순위가 높은 H 스레드가 가장 뒤늦게 실행되는 모순이 발생하게 된다.

 

Priority Donation(우선순위 기부)
이러한 모순을 해결하기 위한 방안이 있는데, 바로 우선순위 기부이다. "왜 우선순위를 어떻게 기부를 하지?"와 같은 의문이 처음에는 생겼다. 그러나, 스레드 고유라고 여겼던 priority 또한 경우에 따라서 타 스레드의 priority를 획득하고 반납하는 것이 가능함을 알고 이를 바탕으로 이해해 나갔다.

우선순위 기부 시나리오

위의 그림은 H 스레드의 우선순위가 L 스레드에게 기부되었을 경우의 시나리오 이다. H 스레드가 락 획득을 요청하는 시점에, L 스레드의 우선순위는 H 스레드 만큼 높아진다. 이렇게 될 경우, M 스레드의 선점을 방지할 수 있으며, H 스레드 뒤늦게 실행되는 것을 방지할 수 있다.

 

위 과정은 lock_acquire, lock_release에서 일어난다
Thread를 처리하는 파일에는 Lock을 획득/놓아주는 함수가 존재한다. 초기에는 바닐라 상태로 기초적인 것만 구현이 되어있다. 여기서 우리는 락을 획득할 때 우선순위를 기부를 하고, 다시 우선순위를 반납하는 로직을 작성을 해야 했다. 함수 자체가 상당히 복잡해지는 만큼, 한글로 로직을 간략하게 작성한 것으로 설명을 하고자 한다.

락 획득/반환 함수 서술

기본적으로 각 함수는 위에 방어코드가 존재한다. 이 코드는 건들 필요는 없다고 판단을 하였고, 획득할 때에는 priority를 비교를 한 다음 우선순위를 기부하고, 반대로 반환할 때에는 원래 우선순위로 돌아와야 한다.

어떻게 비교를 해야 할까? 다행이도 pintos에는 current_thread()라는 함수로 현재 호출된 스레드와, lock->hold를 통해 락을 획득한 상태의 스레드를 각각 불러올 수 있다. 이들은 priority 속성을 가지고 있으므로... 비교를 통해 로직 구현이 가능하다.

 

 

Pintos 1주차를 마치며...

입문 초기에 어렵다는 소문을 들은 만큼, 실제로 체감 난이도는 매우 높았다. 이제 막 git에서 pull 받은 pintos 코드를 맨 처음 어디서 보야 할 지, 대략적인 흐름이 어떤지 파악하는데 상당한 시간을 소비한 것 같다. 흐름을 파악해야 각각 구현할 것을 구체화 하고, 예측을 할 수 있다고 생각한다. 그러나 이 흐름은 몇몇 국소적인 내용을 파악했다고 머릿속에 그려지는 것이 아니며, 무엇을 학습해야 그려지는지 예측하기도 어렵다.

나는 이 흐름을 파악하기 위해, AI에게 코드 리뷰 전반을 해달라고 하기 보다는, 코드 전반과 카이스트 강의 자료를 살펴보며, 내 추정 시나리오를 되묻는 방식으로 그림을 하나하나 그려 나갔다. 아직은 부족한 점이 많았지만, 나에게 있어서는 하나의 큰 성과였고, 이후 프로젝트에서 이를 활용하고 발전해 나가길 기대한다.