[Pintos] Project 1 Threads

 

드디어 대망의 핀토스다..! 프로젝트 1은 스레드에 관한 내용이다. 좀 더 정확히 짚어서 말하자면 스케줄링 알고리즘 구현이라고 볼 수 있겠다. 

 

CPU Scheduling 

우리가 사용하는 컴퓨터에서는 여러 개의 프로그램들이 동시에 돌아가고 있다. 좀 더 엄밀히 말하면 동시에 돌아가는 것처럼 보이는 것이다. 사실은 한개의 프로그램만이 하나의 CPU 코어를 사용할 수 있고, 사용 주기가 굉장히 빠르게 교체되기 때문에 우리 눈에는 프로그램들이 동시에 돌아가는 것처럼 보이는 것이다. 

여기까지는 우리가 컴퓨터를 보는 입장에서의 설명이었고, 프로그램의 입장에서는 CPU를 마치 자기 자신만이 소유한 것처럼 사용할 수 있게 하는 것이 CPU Scheduling의 목표이다. 현재 프로그램이 디스크에 접근하거나, 키보드의 입력을 기다리는 등의 시간이 오래 걸리는 작업을 하는 동안에는 다른 프로그램이 CPU를 사용할 수 있게 하고, I/O 작업이 끝나 자신의 차례가 되면 빠르게 CPU를 사용할 수 있게 하여 마치 CPU를 나만 쓰는 것처럼 추상화를 시킨 것이다. 즉, 프로그램 A가 CPU를 사용할 때 CPU의 레지스터 값들은 프로그램 A에 대한 정보만을 담고 있어야 한다. 이는 동시에 여러 개의 프로그램이 CPU를 사용하지 않는 것을 뜻한다. 또한 프로그램 A가 뒤로 밀린 이후 다시 CPU를 사용하기까지 대기 시간이 짧아야 하므로, 이를 위해 scheduling policy를 구현하게 된다. 기본적으로 핀토스는 busy waiting 방식으로 구현되어 있다. 

 

 

Busy waiting

busy waiting 방식은 스레드가 CPU에 대한 권한을 얻을 때까지 계속해서 확인하는 방식을 뜻한다. 스레드가 깨어날 수 있는 시점까지 계속해서 반복문을 돌며 깨어날 수 있는지 체크하기 때문에, CPU 사용 효율이  나빠질 수 있다. 물론 항상 나쁘기만 한 방식은 아니며 스레드가 CPU에 대한 권한을 획득할 수 있는 시점이 빠를수록 유리한 방식이다. 핀토스에서도 잠든 스레드가 계속해서 반복문을 돌며 깨어날 시간인지 확인하는 방식으로 구현되어 있다. 

 

 

 

Block & Wake up(Sleep Lock)

우리의 1차적인 목표는 기본적으로 구현되어 있는 busy waiting 방식을 block & wake up 방식으로 바꾸는 것이다! 이 방식은 sleep lock이라고도 부른다. 이 방식에서는 스레드가 잠에 들면 반복문을 돌며 상태를 체크하는 것이 아니라, 말 그대로 스레드를 block 시켜두고 시간이 되면 스레드를 깨워 ready list에 옮겨주는 작업을 해준다. 

 

여기에서 busy waiting과 가장 큰 차이를 보이는 점을 짚고 넘어가자. busy waiting에서는 스레드가 CPU를 점유하기 위해 현재 점유할 수 있는 상태인지를 반복문을 돌며 자신이 체크했다. 반면 우리가 구현할 block & wake up 방식은 스레드가 깨어날 시간인지 체크하는 것이 자신이 아니다! 

 

그렇다면 스레드를 깨우는 작업은 언제 진행될까? 

CPU에는 타이머라는 장치가 존재한다. 이 타이머는 CPU에게 시간 정보를 제공하는 역할을 한다. CPU는 일정 속도의 클럭에 따라 동작한다. 타이머는 이 클럭이 얼마나 발생하였는지를 카운트하는 장치이다. 우리는 이 타이머를 통해 일정한 주기마다 신호를 보낼 수 있다. 이를 타이머 인터럽트라고 한다. 핀토스 프로젝트에서는 매초마다 100번의 타이머 인터럽트가 발생하도록 설정해두었다. 따라서 우리가 잠든 스레드를 깨우기 위해 타이머 인터럽트가 발생할 때마다 잠들어있는 녀석들을 검사해 이제 깰 시간이 된 스레드는 다시 ready list에 옮겨주는 방식으로 구현하면 될 것이다! 

 

기본적으로 처음 구현한 방식은 FIFO 방식이다. 물론 정확히는 FIFO와 Round Robin을 섞어둔 방식이지만.. 먼저 ready list에 올라온 스레드가 먼저 실행이 되고, TIME SLICE를 지나 사용한 스레드는 쫓겨나 다시 ready list로 돌아가는 방식이다. 

 

 

Priority Scheduling

다음으로 구현할 과제는 우선순위 스케줄링이다. 이 방식은 스레드에 우선순위를 정해주어 우선순위가 높은 스레드를 먼저 실행시키는 스케줄링 방식이다. 위에서 소개한 스케줄링 방식들과 가장 큰 차이점으로는 만약 현재 실행 중인 스레드보다 우선순위가 높은 스레드가 ready list에 올라오게 되면, 현재 실행중인 스레드는 TIME SLICE가 지나지 않아도 CPU에서 쫓겨나게 된다는 것이다. 이를 Preemption이라 하고 이러한 점이 앞의 nonpreemption 방식들과 가장 큰 차이점이다. 

 

위의 그림은 프로세스의 상태를 나타낸 그림이다. 우리의 핀토스에서는 스레드의 상태를 네 가지로 나누는데, 위의 그림에서 new를 뺐다고 생각하면 될 것이다. 그런데 thread_status에만 new가 없는 것이지 admitted 과정은 존재한다! 

 

갑자기 이 그림이 나온 이유는 우선순위 스케줄링 방식에서 어느 상황에 preemption이 발생하는지 알아보기 위함이다. 쉽게 생각하면 어떠한 스레드가 ready 상태로 변하면 preemption이 발생할 수 있는지 검사한 뒤, 현재 running 중인 스레드보다 방금 ready로 변한 스레드가 우선순위가 높다면 preemption이 발생한다. 이를 염두에 두고 코드에서 어떤 상황이 preemption이 발생할 수 있는 상황인지 인지하고 구현하면 좀 더 수월하게 프로젝트를 진행할 수 있을 것이다. 위의 프로세스 상태도를 항상 생각하며 모든 상황에서 스케줄러가 동작할지 고려해 보자! 

 

 

Synchronization

진행 상황 체크 표에는 나와있지 않았지만, 동시성 프로그램을 구현하기 위해서는 필수적으로 고려해야하는 부분이다. 핀토스 프로젝트에서는 락과 세마포어를 활용한다. 세마포어의 경우 초기값을 0이나 1로만 두어 뮤텍스 락처럼 사용한다. 

동기화에 대해 간략하게 정리하자면, 서로 다른 스레드가 같은 공유 자원에 접근하여 그 자원을 사용할 때, 자원에 대한 신뢰성을 보장하기 위해 규칙을 만든 것이다. 만약 아무런 규칙 없이 여러 스레드들이 한 개의 자원에 접근하게 되면, 그 자원은 일관성을 잃어버리게 된다. 

예를 들어 공유 변수 a가 있고, 스레드 A는 a에 100을 더하고, 스레드 B는 a에 200을 더한다고 생각해 보자. 그림과 같이 스레드 A와 스레드 B의 코드가 한 줄씩 번갈아가면서 실행된다고 생각하자. 먼저 스레드 A에서 변수 a를 읽어올 것이다. 다음으로 스레드 B도 a를 읽어오는데 두 시점에서 모두 a는 200이다. 

 

다음으로 스레드 A에서 a에 100을 더하는 작업을 한다. 이 시점에서 a는 300으로 바뀌게 된다.

 

다음으로 스레드 B에서는 a에 200을 더하는 연산을 진행하는데, 먼저 읽어온 a의 값이 200이었기 때문에 더한 뒤의 값은 400이다. 이렇게 공유 자원 a의 값은 최종적으로 400이 된다. 

위의 상황과 같은 경우에서 스레드 A와 스레드 B가 다 합쳐서 a를 총 300만큼 증가시켜야 했지만, 스레드 A의 진행 결과가 스레드 B의 진행 결과에 묻히게 되었고 이로 인해 a의 값은 200밖에 증가하지 않았다. 이렇게 공유 자원 a는 신뢰를 잃어버리게 되었고 이런 상황을 방지하기 위해서 동기화 작업이 필요하다. 

 

스케줄링 파트나 동기화 파트는 내용이 너무 많아서 따로 포스팅 할 계획이다. 1주 차 프로젝트가 빠듯하게 끝나서 2주 차 때 1주 차 내용을 쓰고 있는데 매 프로젝트마다 정리할 내용이 진짜 굉장히 많으니 핀토스 프로젝트를 진행할 독자분들은 내용 정리를 미리미리 해두시길...