OS

Go back

OS Review
Device Driver
NS Tools

Home
Papers
Daily Link

To Main

6. 씨피유 스케줄링 (CPU Scheduling)

씨피유 스케줄링은 멀티프로그램을 지원하는 오에스의 근본과도 같습니다. 멀티프로그래밍의 목적은 전에도 언급했듯 씨피유의 사용률을 극대화 시킴으로써 언제나 시스템 내부에서 프로세스들이 활개를 치도록 만들어주는 것이죠. 스케줄링은 오에스의 가장 기초적인 기능이기도 한데, 엎친데 덮친격으로 그중 씨피유 는 시스템의 가장 기초적인 리소스이기때문에 앞으로 다룰 주제는 오에스의 기초에 있어서 서 왕중요하다는 사실을 느낄수가 있으시겄습니다.

먼저 모든 일에는 순환이 있듯이 프로세스가 처리되는 과정을 가만이 지켜보면 또한 일종의 싸이클을 가지고 있음을 알게되지요. 바로 씨피유 버스트(CPU burst)와 I/O 버스트(I/O burst)가 이루는 사이클입니다. 이것을 씨피유 입장에서 보면 그림 5.1과 같이 나타낼수 있는데(아직도 책 안샀냐? 독한것,,,) 먼저 처음 프로세스가 실행이 되기 위하여 일련의 인스트럭션을 씨피유에서 실행(이때를 씨피유 버스트라고 해요)하는데 몇가지 인스트럭션을 수행하다가 문득 I/O가 불가피하게 필요하게 됩니다. 그때 일어나는 것이 I/O 작업이죠(이때가 I/O 버스트로써 프로세스에게 점령당한 씨피유 입장에서는 I/O가 끝나기를 기다리고 있어요). 이렇게 프로세스가 뭔가를 할때에는 두 버스트가 사이클을 이루면서 일어납니다. 씨피유 버스트의 지속시간을 나름대로 방대한 양으로 재본결과 프로세스의 종류에 따라 그 차이가 꽤 남에도 불구하고 그림 5.2와 같은 그래프를 얻을수 있었다고 합니다. 그림 5.2는 0~4밀리초정도 지속되는 씨피유 버스트들이 가장 많이 일어났음을 알려주는 그래프인데, 씨피유 버스트가 끝나는 즉시, I/O 버스트동안은 해당 프로세스를 쫏아내고, 씨피유 버스트르 요구하는 또다른 프로세스를 얼렁 씨피유에 불러들이는 기준이 약 1~2밀리초정도가 되야하는 이유를 그래프는 암시하고하고 있지요. 왜 씨피유 스케줄링이 숏텀 스케줄링이라고 불리는지에 대한 의미 또한 알수 있겄죠? 이러한 일종의 패턴을 컴퓨터 내부에서는 종종 찾아볼수 있는데, 이러한 패턴을 분석하고 그 규칙성을 규명하거나 활용하는 것도 좋은 논문거리들 같아요. 패턴을 이용한 좋은 활용예를 나중에 메모리에서 다시 언급하겠습니다.

보통 프로그램을 위의 기준에서 바라볼때에는 I/O 바운드(bound)프로그램, 또는 씨피유 바운드 프로그램으로 나누는데, 전자는 I/O작업을 많이필요로하고, 후자는 씨피유내부에서의 인스트럭션 실행을 많이필요로 합니다. 고로 전자는 평균적으로 무척 짧은 씨피유 버스트를 나타내주고, 후자는 평균적으로 긴 씨피유 버스트를 나타내므로 각각의 시스템에대한 씨피유 스케줄링이 똑같다가는 당연히 피봅니다.

자, 그럼 본격적으로 씨피유 스케줄러를 살펴봅시다. 씨피유가 아이들(idle:널널)한 상태로 있으면 오에스는 재빨리 레디큐에서 실행될 준비가 되어있는 프로세스를 골라야 합니다. 그리고 씨피유에게 고른 녀석을 떠밀죠. 전에 언급하기를 큐(queue)란 FIFO(First In First Out)의 규칙을 따른다고 했지만, 엄밀하게 레디큐는 그냥 평범한 큐뿐만 아니라 프라이오티큐(prioty queue-큐내부에 우선순위가 따로 있어요), 트리구조(tree), 또는 정렬되지 않은 링크드리스트등으로 만들기도 합니다. 큐내부의 레코드들은 일반적으로 PCB(Process Control Block)들입니다.

제일먼저 여러분들이 귀에 못이 박히도록 들어온 선점형(preemptive) 스케줄링을 알아보죠. 씨피유 스케줄링의 선택이 일어나는 순간은 다음 네가지 경우일겁니다. (전에 프로세스에게는 총 5가지 상태가 존재할수 있다고 혔죠?)

1. 프로세스가 실행상태에서 대기상태로 전환될때 2. 프로세스가 실행상태에서 준비상태로 전환될때 3. 프로세스가 대기상태에서 준비상태로 전환될때 4. 프로세스가 종료될때

위의 경우중 1번과 4번에는 사실 새로운 프로세스를 고른는것 외에는 특별하게 스케줄링이 취할수 있는 행위가 없습니다. 바로 비선점형이란 말이 이에 해당됩니다. M$의 윈도우즈 3.1과 매킨토시 오에스가 여기에 해당된다고 허네요. 허허,,,비선점형 스케줄링하에서는 프로세스가 씨피유를 일단 점유하게 되면 이놈이 독하게도 대기상태로 전환되거나 종료되기 전까지는 절대로 씨피유를 물고 안놔주죠. 허나, 2번과 3번에서도 스케줄링이 개입될때가 바로 선점형 스케줄링입니다. 선량한 프로세스가 3번처럼 슬슬 실행을 준비하고 있는데 사악한 엉뚱한 프로세스가 낼름~! 씨피유를 선점해버리는 경우가 발생하지요. 유저입장에서는 뭔가 빠른 인터액션을 요구하는 작업을 수행할시 선점형 스케줄링을 이용하면 어쭈구리~ 빠른걸~이라는 느낌이 그래서 들게 되지요. 선점형 스케줄링은 또한 비싼댓가를 요구합니다. 하드웨어적(씨피유의 디자인이죠)으로 지원이 되야함은 물론이고, 다음의 경우를 한번 생각해봅시다.

두개의 프로세스가 한개의 데이타를 서로 공유하고 있었다고 가정해보죠. 한 프로세스가 그 데이터를 한참 신나게 업데이트하고 있는 중간!에 갑자기 선점을 당합니다(preempted). 이때 선점을 (가)한 또한개의 프로세스가 데이터를 읽으려는 시도를 할테고 그 데이타는 지금 일관성을 잃어버린 순간이기때문에 앞으로 펼쳐질 불행한 사태를 그 둘은 절대 눈치채지 못하는 불쌍한 존재가 되어버립니다. 그럼 결국 선점형은 구현을 못하는가하면 또 그게 아니죠. 현실적으로 완벽! 하지는 못하지만 꽤 효과적으로 이를 해결하는 방법이 있습니다. 이 문제를 정의하고 해결법에 대한 제시를 다음 장부터 다룰 예정이니 기대해줍쇼.

씨피유 스케줄링과 관련된 또하나의 중요한 요소는 바로 디스패쳐(dispatcher)입니다. 디스패쳐는 수문장과도 같이 스케줄러가 골라준 프로세스에게 직접 컨트롤을 건네주는 역할을 수행하는데 이에는 컨텍스트 스위칭, 유저모드로의 스위칭, 그리고 특정 프로그램을 재시작하기위해 알맞은 주소값으로 점프하는등의 기능을 포함하지요. 디스패처로 하여금 돌아가던 한 프로세스를 정지시키고 또다른 프로세스의 실행을 시작하는데에 걸리는 시간적 차이를 우리는 디스패치레이턴시(dispatch latency)라고 부릅니다.

CPU스케줄링이 잘되고 있는지 안되고 있는지를 판별하려면 몇가지 정량적인 측정이 필수적이겠죠? 여러가지의 측정가능한 값들이 있겠으나, 몇가지 대표적인 값들을 제시해보면 다음과도 같습니다. 일종의 벤치마킹 기준이라고 생각하시면 돼요.

CPU Utilizaetion : 씨피유가 일하는시간/흐른시간 으로써, 0에서 100까지의 %수치로 나타내줍니다. 현실적으로 40~90정도가 된다고 하는군요.

Throughput : 단위 시간당 처리된 프로세스의 수를 의미하지요. 정말로 긴 프로세스는 시간당 1이 되는 경우까지 있다는군요. 짧은 경우는 초당 10정도,,,

Turnaround Time : 이것은 프로세스의 기준에서 바라보는 측정값으로 한 프로세스가 등장해서 이것이 완전히 끝날때까지 걸리는 시간을 의미합니다. 결국 이 값은 프로세스가 메모리에 올려지기까지 기둘리는 시간+레디큐에서 씨피유로 진입하기 까지 기둘리는 시간+씨피유에서 실행되는 시간+I/O를 처리하는 시간 이 되겠죠.

Waiting Time : 씨피유 스케줄링 알고리즘은 한 프로세스가 I/O를 처리하는 시간이나 씨피유 내에서 실행되는 시간등에는 전혀! 영향을 주지 않습니다. 단지 프로세스가 레디큐에서 얼마나 오래 기다리는지를 결정하기 때문에 이 것은 레디큐에서 기다리는 시간을 의미하게 되지요.

Response Time : 인터액티브한 실시간 시스템에서는 Turnaround Time보다는 이 수치가 오히려 좋은 벤치마킹의 기준이 됩니다. 즉, 한 프로세스가 생성되고 나서 그것의 첫번째 처리에 대한 반응이 오는데 걸리는 시간을 의미하게 되지요.

위의 기준들을 잘보면 좋은 씨피유 스케줄링은 CPU Utilization과 Throughput은 극대화시키고 나머지는 극소화 시키는 알고리즘이라는것을 감잡을수 있으시겄죠? 몇가지 추가적으로 부과되는 패러미터들로써는 인터액티브 시스템은 각각의 수치를 최대화 및 최소화 시키는 것도 중요하지만 더욱 중요한 요소로써 통계적으로 위의 수치들의 분산이 작어야 합니다. 측정된 최대, 최소값이 각각 크고 작지만 그 값들이 매번 실행할때마다 왔다리 갔다리 거리다가는 죽도 밥도 안된다는 소리죠.

자! 이젠 본격적인 스케줄링 알고리즘 몸체를 살펴보는 순간이 왔군요. 여기서의 알고리즘은 그리 어려운게 절대 아니고, 개념위주로 간략하게만 살펴보니 만큼 긴장들 끄시길.

1. First-Come First-Served(FCFS) 스케줄링 말그대로 입니다. 첫번째로 레디큐에 도착하는 프로세스를 첫번째로 처리해버리는 철저한 FIFO 규칙을 적용한 예이죠. 이것은 순리에 맞는 원리를 알고리즘화 한것이겠으나 안타깝게도 전혀 효과적이지를 못합니다. 3개의 프로세스가 도착을 했다고 가정을 해보지요. 이때 처음 시작하자 마자 등치가 큰(씨피유 버스트가 큰!) 프로세스가 레디큐에서 또아리를 틀고 있게 될경우 평균 Waiting Time을 측정해보면 처음 두개가 작은 크기의 프로세스였을때와 비교하여 엄청나게 커졌음을 알게되지요. 책의 p.129에 이에대한 설명 및 그림들이 시작되니 참고하시면 많은 도움이 될듯. 이 알고리즘은 소위말해 컨베이어벨트 효과(convoy effect)를 보여주는데, 이말은 초반에 큰 프로세스가 들어올경우 전체적으로 분위기 조져버리는 경우를 뜻하게 됩니다. 또한 주지할점은 이 스케줄링 기법은 비선점형!이라는 사실입니다. 먼저온 녀석에게 먼저 기득권을 준다는 사실이 철칙이니 만큼 예외란 있을수 없는것이죠. 예외가 생기면 더이상 FSFC가 아니겠죠?

2. Shortest-Job-First (SJF) 스케줄링 위에서 언급된 스케줄링에 문제점을 극복하기 위하여 이번에는 Waiting Time을 최소화 시키기 위하여 등치가 작은! 프로세스 순으로 처리를 해주는 알고리즘을 의미합니다. 이것을 이론적으로 고찰해보니 꽤 효과가 있어요! 단지 문제가 있다면 다음 실행될 프로세스의 씨피유 버스트 크기를 전혀 예측할수 없다는 현실적인 문제이겠죠. 똥누러 들어가는놈이 얼마나 오래 변기에 앉아있을 것인지 예측할수 있는 사람있으면 나와봐,,, 씨피유 버스트의 크기는 워낙 프로세스마다 다양하고 예측이 불가능하기에 이방법이 최소한의 Waiting Time을 제공해주는 최적화(optimal)된 방법임에도 불구하고 이론적으로만 존재하는 알고리즘이랍니다. 고로 자신이 설계한 씨피유 스케줄링 알고리즘이 뛰어나다는 사실을 증명하기 위하여 대부분 SJF와의 이론적 비교결과를 제시하는 기준으로 사용됩니다. 이 방법에는 선점형의 개념의 도입이 가능하죠. 알고리즘 자체가 현재 실행중인 프로세스를 가차없이 끌어내리고 새로 등장한(씨피유 버스트가 가장 작은) 녀석을 그냥 씨피유로 보내버립니다. 물론 비선점형 알고리즘도 가능하고요. 선점형의 개념을 도입할시에는 이 알고리즘의 이름이 조금 바뀌게 되지요. 바로 Shortest-remaining-time-first로요. 말되죠?

3. Prioty 스케줄링 위에서 언급된 SJF는 사실 따지고 보면 프라이오티 스케줄링의 한 특수한 경우일 뿐이죠. 프라이오티 스케줄링은 일반적으로 각 프로세스에 특정한 기준으로 우선순위를 따로 주는 기법이고 만일 똑같은 프라이오티를 가진 프로세스가 등장할시에는 해결사로 FCFS로 다시 우선순위를 정하게 됩니다. 프라이오티 스케줄링은 또한 선점형, 그리고 비선섬형 두가지 모두 적용이 가능한데 제경우는 우선순위를 가진다는 사실과 와 선점한다는 사실 이 두가지의 개념이 아리까리 했었죠. 그 차이점을 간단하게 언급하면 우선순위로 프로세스중 일단 다음번 씨피유에 보낼녀석을 결정하되, 결정된 프로세스가 멀쩡하게 씨피유에서 즐겁게 일처리를 하는 와중에도 선점한 프로세스가 등장할시 그냥 끌어 내려버리는것이 선점형입니다. 그렇기에 프라이어티라는 깡패를 씹어버리는것이 선점형이라는 조폭입니다. 프라이어티 스케줄링은 그런데 아주 고질적인 문제점을 안고 있어요. 예상하셨다 싶이 무한 블로킹(infinite blocking)또는 고사(starvation)문제입니다. 즉, 프라이어티가 낮은 프로세스는 높은 프로세스들에게 눌려서 영영 씨피유 맛조차 못보고 평생 기다리기만 하는 경우가 발생할 수 있다는 사실이죠. 스타베이션 문제는 특정 알고리즘을 승인할때 요구되는 매우 중요한 문제입니다. 책에 언급된 루머에 의하면, 1973년에 셧다운 한 IBM7094라는 대형 컴퓨터에서는 1967년에 생성되었으나 결국 처리되지 못한 낮은 우선순위의 프로세스가 발견되었다더군요. 7년간 처리되길 기다렸으나 결국 넋이되버린 불쌍한 프로세스,,,믿거나 말거나,,,

무한 블로킹을 해결하는 방법이 또 있지요. 그것은 바로 각 프로세스에게 나이를 부여(aging)하는 방법입니다. 즉, 나이가 들수록(시간이 지날수록) 점점 그 프로세스의 우선순위는 높아져 가는것이죠. 근사한 방법이죠? 점점 인간사회의 모델을 오에스에조차 적용하고 있는 순간을 우리는 보게됩니다. 그만큼 알고리즘이 점점 복잡해 져간다는 뜻이기도 하고요.

4. Round-Robin(RR) 스케줄링. 타임 쉐어링 시스템에서는 꽤 유명한 스케줄링입니다. 이것은 FCFS와 비슷하지만 프로세스간의 전환을 위해서 여기에다가 선점형 개념을 도입한 것이죠. 먼저 룰렛을 생각해보시길. 알록달록한 룰렛은 각각의 슬롯이 존재하지요. 각 번호대신 프로세스가 거기서 기다리고, 슬롯은 동일한 간격으로 이루어진 시간을 상징하게 됩니다. 한 슬롯의 크기를 우리는 타임퀀텀(time quantum)이라고 부릅니다. 이것을 한 방향으로 한 슬롯씩 돌려가면서 대응되는 프로세스를 씨피유에 보내되, 시간이 흘러 다음 타임 퀀텀이 도래하면(틱~하고 룰렛을 한슬롯 돌리는거죠) 아직 일처리가 끝나지 않은 프로세스일지라도 다음 슬롯의 프로세스에게 선점을 당하게 됩니다. 즉, 기냥 끌려내려와서 레디큐의 꼬리에 가서 붙게되죠. 만일 주어진 타임 퀀텀 내에 일이 다 끝나면 타임 퀀텀을 채우지 않은 상태에서조차 룰렛은 돌아가고 당근 다음 프로세스가 씨피유를 점유하게 됩니다. RR 스케줄링은 매우 세련된 스케줄링이며, 그 성능은 타임 퀀텀의 크기에 의존하게 됩니다. 만일 타임퀀텀을 무한대로 설정하면? 바로 FCFS 스케줄링이 되어버립니다. 너무 짧게 설정하면? 컨텍스트 스위칭 하다가 볼장 다 보죠. 일반적으로 한 타임 퀀텀은 컨텍스트 스위칭에 걸리는 시간의 10배로 설정하고 사용됩니다. 라운드 로빈 알고리즘,,,이 원리는 상식적으로 알고있어도 잘난척하기에 아주 좋은 알고리즘이니 잘 이해해두시길 바랍니다.

그밖에 멀티레벨 큐(Multilevel Queue), 멀티레벨 피드백 큐(Multilevel Feedback Queue)들이 있어요. 전자는 각 프로세스의 카테고리를 몇가지 레벨로 나누고 알맞는 큐에다 대기시키되, 각 큐가 독립적인 씨피유 알고리즘을 사용합니다. 후자는 전자와 비슷한데 차임점은 프로세스들끼리 지정된 큐 이외의 큐를 를 서로 변신해가며 들낙날락 거린다는데에 있지만, 둘다 많이 사용되지는 않습니다. 너무 복잡하거든요.

마지막으로 멀티플 프로세서가 달린 시스템의 스케줄링은 어떤지 짧게 언급해 보죠. 일반적으로 단일 씨피유 스케줄링보다 훨씬 복잡하겄죠? 고려해야 할 문제점의 좋은 예로써 동일한 씨피유를 여럿 사용하는 시스템에서 I/O장비를 사용하고자 할때, 대개의 경우 I/O장비는 한개의 프로세서의 버스와 연결이 되기 때문에 특정 I/O장비를 사용하기 위해서는 반드시 특정 씨피유내에서 프로세스가 실행되야 한다는 존건에 부합되어야 합니다. 또한 load sharing(멀티플 씨피유를 사용할때 얻는 강점중 하나로써 부하를 여러개의 씨피유에 분산시키는 것이죠)을 위해서는 대개의경우 한개의 공동 레디큐를 사용하여야 하는데, 이때 또 데이타의 일관성을 유지하는 문제는 매우 골치아픈 주제가 될수도 있겠죠? 이러한 면에서는 특정 마스터 씨피유가 일관성있게 레디큐를 관리하는 비대칭형 시스템의 구현이 훨씬 용이하다는 사실을 알수 있을것입니다.

이상으로 씨피유 스케줄링을 간단하게 살펴보았습니다. 사실, 이런 이론들이 우리가 프로그래밍을 하는데에는 직접 요구되는 지식은 아니지만, 이해를 하고 프로그래밍을 하는것과 그렇지 못하고 프로그래밍을 하는것의 차이점은 어떠한 형태로든지 티가 나는 모양입니다. 그러니 이해가 되지 않으신분들은 다시한번 천천히 읽어보시거나 질문을 던져주시면 아는한 정성껏 답해드릴테니 언제든지 질문해주셔요.

다음장에서는,,,음,,,-_-;;; 정말 땀이 나는군요. 그 이름도 무셔운 크리티컬 섹션 문제(Critical Section Problem)을 한번 다루어볼 예정입니다. 정말 오에스를 공부함에 있어서도 말그대로 크리티컬 한 부분이니 만큼 이것을 어떻게 다루어야 할지 저로써도 무척 긴장이 됩니다. 하지만, 여기까지 따라오신 분들이라면야, 충분히 이해가 가능한 부분이니만큼 기대해 주셔도 좋으리라 생각되는 군요. 그럼 다음 장에서 뵙죠.

-duffer 경준 (http://vorlon.cwru.edu/~kxm73)