Windows preemptive priority based round-robin scheduling

안녕하세요 대학생 개발자입니다

이전 글에서는 싱글 스레드로 구현할 수 있는 간단한 mmo타입의 게임을 만들어봤습니다.

이번 글에서는 게임 서버 개발자가 되면 주로 접하게될 Windows Server, 즉 Windows OS에 대한 얘기를 해보려고합니다.

os에 따라 내용이 다른 부분이 있을 수 있으니, 미리 Windows를 상정하고 말씀드린다는 부분 양해부탁드립니다.

 

preemptive

우선 선점에 대한 개념부터 정리를 하고 넘어가겠습니다.

우선 우리가 일반적으로 사용하는 windows os는 선점형이냐 비선점형이냐 라는 부분인데요.

하지만 이 전에 우리가 먼저 따져봐야할 부분이 있습니다.

선점의 주체가 누가 되는것인가 입니다.

OS가 선점의 주체가 된다면 스레드들은 OS의 관리를 받는 주체가 될 것입니다.

반대로 스레드가 선점의 주체가 된다면 스스로 작동을 하고 멈추는것을 관리하게 될겁니다.

OS는 스케쥴링에 관여를 할 수 없다는 것이겠죠.

 

위에서 언급이 되었듯 선점의 주체는 당연히도 OS입니다.

그리고 이번 글에서 언급할 Windows또한 OS 선점형 방식을 채택하고 있습니다.

아직 인터럽트에 대한 언급이 나오지는 않았습니다만 스레드 선점형인 상태로 존재하게 된다면 다음과 같은 문제가 있을 수 있을 것 같습니다.

스레드가 cpu 사용권 반환을 직접하게 될테니 인터럽트 상황이 되었을 때 OS가 스레드가 사용중인 cpu를 멈추고 우선 인터럽트 핸들러를 호출할 수 없을것입니다.

그럼 우선 OS는 어떻게 스레드들을 관리하는지 알아보도록 하겠습니다.

 

우선 스레드 관리이전에 레지스터에 대한 간단한 이해를 위해 콜스택이라는 부분을 짚고 넘어가보겠습니다.

여러분들은 콜 스택이란걸 어떻게 이해하고 계실지 모르겠습니다만 vs에서 콜스택을 보게되면 말 그대로 어떤 함수를 호출을 했고에 대한 모든 정보가 들어있는 창입니다.

그럼 vs는 이 호출 스택이란걸 어떻게 알고 있는걸까 입니다.

바로 스택입니다.

함수를 호출할 때 마다 스택에다가 정보를 쌓아놓고 왔기 때문에 그 정보를 알 수 있고 vs는 그저 우리가 봤을때 보기 편하게 보여주는 것 밖에 없습니다.

콜 스택이란건 그냥 bp와 sp, 이런 레지스터가 스택이라고 불리는 메모리 주소를 가지고 있고 cpu는 이 bp와 sp레지스터를 읽어서 가져올 뿐입니다.

당연히 이 모든 함수에 대한 정보는 레지스터에 들어가지 않겠죠.

우리가 익히 알고있는 코드 세그먼트 영역의 코드 또한 레지스터를 통해서 읽히게 됩니다.

그럼 레지스터를 바꾸게 되면 전혀 다른 함수를 참조 할 수 있을것 같습니다.

 

Context Switching

그렇다면 앞의 문장에서 컨텍스트 스위칭을 추론해 볼 수 있을 것 같습니다.

cpu는 그저 레지스터에 얹어진 정보들을 바탕으로 작업만 실행하는 주체일 뿐이고, 컨텍스트 스위칭은 OS에 의해서 일어나고 컨텍스트 스위칭이라는 것은 그저 cpu에 있는 레지스터값을 세팅하는 일입니다.

 

OS는 IP 레지스터, 그리고 SP같은 레지스터를 세팅해주면 cpu는 그저 있는 값을 가지고 처리한다 정도가 되겠습니다.

물론 제가 OS가 세팅한다고 말씀을 드려서 OS가 직접 cpu에있는 레지스터 값을 세팅한다고 생각하실 수 있기 때문에 조금뒤에 언급을 드리겠지만 컨텍스트 스위칭은 cpu가 직접하는 작업이라는 점만 우선 말씀드리고 계속 이어가겠습니다.

 

우선은 공통적으로 언급하고 있는 부분에 대해서 먼저 정리를 하고 넘어가도록 하겠습니다.

cpu는 OS가 세팅해 준 레지스터에 의해서 작동이 되는 것이고, 컨텍스트 스위칭은 OS가 레지스터를 새로 세팅하는 과정이라고 먼저 정리하겠습니다.

당연히 컨텍스트 스위칭은 인터럽트에 의해서만 실행되기 때문에 이 모든 정보는 NPPool에 저장이 되어있어야 할 것입니다.

NPPool에 대한 내용은 이전 글에서 언급하고 있으니 이전글을 참고해 주시기 바랍니다.

방금 언급한 내용처럼 컨텍스트 스위칭은 인터럽트에 의해서 일어나게되고 인터럽트는 최소단위가 보장된 operation, 즉 MOV CMP와 같은 cpu입장에서 무조건 이 기능은 한큐에 이뤄져야한다고 정해진 그런 기능과 기능 사이에 발생할 수 있습니다.

 

우선 컨텍스트 스위칭이 무엇인지 정의를 했으니, 이로인해서 우리가 일반적으로 겪는 문제를 한가지 짚고 넘어가 보겠습니다.

컨텍스트 스위칭은 현재 cpu에 저장되어있는 레지스터의 상태(스레드의 컨텍스트)를 저장하고 다음번 스레드의 컨텍스트를 레지스터에 셋 해주는 것이라고 했습니다.

그래서 우리가 멀티 스레드 환경에서 a++이라는 코드를 10만번 실행하는 스레드가 2개라면 실행후 a가 20만이길 희망하지만 20만보다 작은값이 나오는 이유가 이런 이유 때문이 되겠습니다.

 

a++ 이라는 c코드를 x86 asm으로 가져와 보겠습니다.

MOV eax dword ptr [a]
여기서 context swtiching 가능
ADD eax 1
여기서도 context switching 가능
MOV dowrd ptr[a] eax

a++이라는 연산자는 c에서는 한줄에 적혀있는 연산일 지 모르지만 어셈블리 즉 cpu단까지 내려가버리면 한번에 행동이 보장되는 연산자가 아니게 됩니다.

그렇기 때문에 a++이라는 연산은 보장을 받지 못하게 됩니다.

 

첫줄을 실행한 뒤에 컨텍스트 스위칭이 발생한다고 가정하면 이 컨텍스트의 eax 레지스터에는 a의 값이 들어있을 것입니다.

이 상황에서 컨텍스트 스위칭이 일어나게 되어서 다른 스레드가 a++이라는 연산을 풀로 수행하고 나서 다시 이전에 작동하던 스레드가 컨텍스트 스위칭으로 다시 작동한다고 가정한다면 이 스레드 컨텍스트에는 eax가 과거의 a값일 것입니다.

왜냐면 컨텍스트 스위칭은 현재 cpu에 있는 스레드의 컨텍스트를 저장하기 때문에 과거의 값이 그대로 들어가 있기 때문입니다.

 

추가로 아직 크게 생각을 안해도 될 부분이긴 합니다만 동일 프로세스간 컨텍스트 스위칭의 경우에는 cr3 레지스터에 동일한 페이지 테이블이 저장되어 있을 것입니다.

그렇기 때문에 cr3 레지스터 플러시로 인한 TLB miss, cache miss 발생이 다른 프로세스간 컨텍스트 스위칭 발생시보다 적을 것입니다.

 

마지막으로 위에서 언급드렸던 OS가 컨텍스트 스위칭을 한다 라는것은 cpu가 OS의 코드가 컨텍스트 스위칭을 수행한다는 의미입니다.

실제 컨텍스트 스위칭은 인터럽트에 의해서 컨텍스트 스위칭이 필요하다고 생각되는 경우에, 디스패쳐 로직을 작동시켜야 하는지에 대한 플래그만 세팅을 해두게 되고 인터럽트가 끝나기 직전 이 플래그가 세팅 되어있다면 그 때 디스패쳐라는 로직을 작동시키면서 발생하게 됩니다.

간단히 말해서 컨텍스트 스위칭은 OS가 직접하는게 아니라 그 컨텍스트, 즉 현재 컨텍스트 스위칭이 필요하다고 하는 cpu가 직접 수행하는 작업이고 현재 cpu에 저장되어있는 스레드의 컨텍스트 위에서 일어나는 작업입니다.

 

디스패쳐 로직이 작동 되게되면 현재 스레드의 컨텍스트를 TCB라고 불리는 커널 스레드에 저장을 하고 이 정보를 레디 큐에 삽입하는 과정을 거치게 됩니다.

그 후 우선순위가 가장 높은 큐에서 하나를 꺼내와 TCB 정보를 cpu에 셋하는 과정을 수행하게 됩니다.

이런 과정이 끝나고 나게되면 IRQL이 높은순서부터 낮은 순서로 모든 인터럽트를 처리하게 될것이고, 그뒤에 패싱레이어라고 불리는 유저 코드가 작동되게 될 경우 이미 컨텍스트 스위칭이 완료되었기 때문에 다음번 인스트럭션을 읽어오게 되면 변경된 컨텍스트의 인스트럭션을 읽어오게 되므로 컨텍스트 스위칭이 수행되었다라고 판단할 수 있습니다.

 

여기까지 선점형이란 무엇인지, 컨텍스트 스위칭은 어떤 방법으로 일어나는지, 컨텍스트 스위칭은 무엇인지 간략하게 정리를 해봤습니다.

이 부분만 이해하신다고 하셔도 충분히 cs면접에서 사용하기에는 충분할 것 같습니다.

 

그럼 아주잠깐 머리를 좀 식히면서 쉬운 내용을 언급하고 스케쥴링 방법에 대한 내용을 언급하겠습니다.

병렬 처리의 기본 조건에 대한 내용을 언급해보려고 합니다.

당연히도 병렬처리를 하려고하는 작업의 개수보다 실직적인 코어 개수가 더 적다면 작업이 직렬화처리 될것입니다.

이렇게 된다면 병렬처리라고 부르기도 참 애매한 상황입니다.

오히려 병렬보다는 동시성에 가까운 구조가 되어버리기 때문입니다.

 

그리고 공유자원의 존재또한 병렬성을 이루는데 방해가 되는 요인입니다.

공유자원이 존재한다면 동기화 문제를 처리해야되기 때문에 이 부분에서 결국 작업이 직렬화가 되어야합니다.

여기서 말하는 공유자원이랑 read만을 위한 공유자원은 제외하고 write가 포함되는 공유자원을 의미합니다.

이 부분은 추후에 동기화 객체를 언급하는 글에서 다루도록 하고 그럼 다음으로 넘어가도록 하겠습니다.

 

 

Windows의 스케쥴링

우리가 주로 사용하는 Windows라는 OS는 어떻게 스케쥴링을 하는지 정리 하도록 하겠습니다.

 

Windows는 우선순위 기반의 라운드 로빈 방식을 채택하고 있습니다.

우선 용어 정리를 간단히 하고 넘어간다면 우선순위 기반은 말 그대로 각 스레드별 우선순위가 존재하고 우선순위가 더 높은 스레드가 우선 처리된다는 것을 의미합니다.

라운드 로빈은 스레드가 cpu를 사용할 수 있는 시간(Quantum)을 배분하고 배분된 시간을 모두 소비하게되면 다음 스레드가 작동하게되고 기존에 작동하던 컨텍스트는 레디큐의 가장 마지막에 삽입되는 방식입니다.

위의 과정에서 OS의 스케쥴링 로직과 디스패칭 로직이 개입하기 때문에 Windows는 OS 선점형이라고 언급을 드렸습니다.

위에서는 간단히 용어 정리만 다뤄보았고 라운드 로빈과 우선순위라는것은 아래에서 조금더 상세하게 언급하겠습니다.

 

구글에 있는 그림들이 하나같이 다 어렵게 생겨서 그나마 제일 심플해보이는 그림으로 가져왔습니다.

 

스레드가 생성이 되었다면 최초 레디큐 라는 곳에 스레드의 컨텍스트 블록(TCB, 위에서 언급)을 넣게 됩니다.

디스패칭 로직은 레디큐에 있는 TCB중 가장 우선순위가 높은 큐에서 TCB를 꺼내와 퀀텀 할당을 받게되고 그 스레드는 cpu를 사용할 수 있게됩니다.

 

IO가 일어나게되면 이 스레드는 컨텍스트 스위칭 이후 IO완료까지 기다리게 될겁니다.

그런 경우에는 이 스레드는 Blocked상태에 들어가게 되며 위 그림에서는 Waiting 상태가 되겠습니다.

 

윈도우는 선점형 우선순위 기반의 라운드 로빈 방식을 채택하고있습니다.

우선... 라운드 로빈이란걸 확인해봐야 되겠는데요...

이름이 상당히 직관적입니다... 뭔가 그냥 빙글빙글 돌면서 수행할 것만같은 그런 느낌입니다.

말그대로입니다 순서가 따로 정해져있지 않으면서 os는 cpu를 물고있을 수 있는 적절한 시간 quantum이라고 불리는 시간을 각 TCB에게 배분합니다.

그 시간동안 하나의 쓰레드는 cpu를 자신의 코드를 돌리는데 사용할 수 있습니다.

quantum time은 os마다 좀 다르게 계산되긴 하는데 일반적으로 15ms~20ms 정도로 잡는걸로 알고있습니다... 하지만 우리가 사용할 서버의 경우에는 이보다 2배정도 더 길다고 들었습니다... 목적이 다르기 때문인데 이건 나중에 가서 말씀을 드리겠습니다.

그럼 라운드 로빈이라는 단어는 어느정도 감이 잡히셨을 겁니다.

어... 근데 여기서 좀 이상한게 있지 않나요??

당장 제 pc에서만 스레드가 4000개가 넘어가는데... 각 스레드의 quantum time이 20ms라면... 전부다 돌리는데 80000ms정도의 시간이 걸리게 될겁니다... 근데 라운드로빈 방식이라면... 지금 내가 글을보고 있는 크롬은 80초마다 한번씩 돌아야 되는데...? 어떻게 돌아가고 있는거지? 라고 이상하다고 생각하신 분들이 분명 계실겁니다... 저도 처음에 이부분이 궁금했었습니다.

일단은 이부분에 대한 내용은 다음 부분들을 정리하다 보면 이해가 되실겁니다.

 

그러면 우선순위 기반이라는 말은 무엇인가... 각 쓰레드가 우선순위가 정해져있나??

뭐...일단 쓰레드 작업에 우선순위가 있다는 말은 맞는 말인것 같습니다. 쓰레드의 우선순위가 정해져있기 때문에 ready queue라는 곳에서 하나의 쓰레드 작업이 뽑힐 때 우선순위가 가장 높은게 뽑힌다고 말하는 것 같습니다.

 

ready queue라는 것은... 사실 큐들을 모아놓은 하나의 테이블 같은 느낌입니다.

각 우선순위 별로 큐들이 존재하구요... 그 큐들은 각각 라운드 로빈 방식을 채택하고 있습니다. 뭐... 큐니까요? 방금 들어갔으면 그게 제일 마지막에 나오는게 맞겠죠 뭐 ㅋㅋㅋㅋ

 

그리고 저 그림에는 자세히 표현이 안되어있긴한데 blocking 상태가 되어버린 혹은 suspend 상태가 되어버린 스레드들은 ready queue에 들어있지도 않을 뿐더러 cpu를 물고 있을 이유도 없습니다... 이친구들은 논외구요... 그래서 4000개가 넘는 쓰레드가 돌고있지만 대부분 블로킹 상태로 특정 시그널을 기다리고 있는 상황이구요... 그러므로 내가 지금 켜놓은 프로그램이 문제없이 잘 돌고있는것이구요... 내가 지금 사용하고 있는 맨 앞에있는 녀석은 우선순위가 가장 높을거니까요...

즉 윈도우는 그냥 라운드로빈도 아니고... 우선순위 기반만 있는것도 아니라 그냥 둘을 적절히 잘 섞어서 만들어 놓은 것 같습니다.

 

자 그러면 ready queue에 대한 얘기를 조금더 이어가도록 할건데요...

ready queue라는 이미 이 cpu에 스케쥴링이 되어있다는 의미입니다. 만약 이전 작업의 quantum time이 끝나게 되어서 그 작업이 context switching으로 빠지게 된다면 자동으로 ready queue중 우선순위가 가장 높은 TCB가 cpu를 물게될 겁니다.

근데 만약 우선순위가 높은 녀석이 한코어를 계속 물고있다면 그 ready queue에 들어있는 다른 쓰레드들은 영원히 돌지 못하는 쓰레드 기아 현상이 발생하게 되는데요... windows에서는 dynamic priority boosting이라는 방식을 통해서 일정 시간동안 쓰레드가 돌지 못하면 임시적으로 우선순위를 높혀주는 방식으로 모든 쓰레드들을 돌려주고 있습니다.

 

자... 그럼 블로킹 되어있는 쓰레드들은 어떻게 관리되고 있는지 하나만 정리해놓은 상태로 끝내도록 하겠습니다...

아까 제컴퓨터에만 블로킹 되어있는 쓰레드가 몇천개가 되었는데요... 음... 이걸 일일이 모두다 돌면서 확인을 할까요? 아니면 뭐 특정 방법이 따로 있는걸까요?

 

음... 제가 처음에 생각했던 방식은 해시같은걸 생각했는데요...

사실은 힙을 사용하고 있습니다. 즉 blocking 걸리는 시간이 가장 짧은 녀석 하나만 보고 있으면 되지 않을까요?

만약 blocking 시간이 가장 적은 녀석만 확인이 된다면.. 굳이 그거보다 많은 애들은 확인을 일일이 할 필요가 없겠죠...

 

정렬이 확실하다면 굳이 모두 확인할 필요는 없다고 봅니다. 그냥 제일 작은거 하나만 보고 뽑을지 말지 결정하면 되는거니까요... 사실 모든 쓰레드들을 확인한다는 것 자체도 말이 안되는거긴했죠 ㅋㅋㅋ...

 

후... 사실 정리해야될 내용이 아직 산덤이처럼 많이 남아있긴한데요... 너무 글이 길어지면 제가 나중에 안읽어보게 될까봐 이정도에서 정리를 해야될 것 같습니다...

 

오랜만에 이론만으로 되어있는 글인데요. 사실 필기가 여기적었다 저기적었다 이런식으로 되어있어서 최대한 모아본다고 모은것인데도 불구하고... 좀 내용이 중구난방입니다. 

어째뜬간에 오늘도 긴 글 읽어주신 분들께 감사드리고 저는 다음에 스케쥴링에 대해서 좀더 깊은 내용을 가지고 돌아오도록 하겠습니다.

그럼 안녕히계세요