어떤 프로세스를 선점한다는 것의 의미는 무엇인가

안녕하세요! 개발자 배씨입니다:) 

자 오늘은 드디어 ~~~~ 스케줄링에 대해서 알아보려고 해요

내용이 많으니까 천천히 잘 따라오셨으면 해요. 저도 쉽게 설명하기 위해 노력할테니까!! 크흠.

제 목표는 "글을 읽는 모두를 이해 시키는 것" 입니다 ㅎㅎ 가봅시다 !!

지금까지 Context Switching(문맥교환) 이라는 말을 많이 썼어요. 

CPU가 어떠한 프로세스의 명령어를 수행중이다가 타이머 인터럽트에 의해서 다른 프로세스로 교체를 하잖아요?

이때 수행중이던 프로세스의 정보를 PCB에 담고 다른 프로세스의 PCB 정보를 꺼집어내서 그 프로세스를 수행시킨다고 "한 100번 정도 말씀 드렸어요" 

그렇다면 이 문맥교환을 할 때 어떤 프로세스를 선택해서 교체작업이 시작될까요?? 

이것이 스케줄링 입니다~ CPU가 수행중이던 프로세스가 끝나면 다음 프로세스로 어떤 것을 고를지에 대한 방법!!

그것을 스케쥴링이라고 해요!  쉽죠?? 

자~ 여기서  스케쥴링 방식에는 크게 두가지로 분류돼요 비선점형 스케줄링과 선점형 스케줄링입니다!!

단어를 유추해보면 아시겠지만 비선점은 선점 당하지 않는것이고 선점은 말 그대로 뭔가 가로채는 느낌인거 같죠??

네 맞아요! 일단 이렇게 두개로 나뉘구나! 생각을 하시고 하나하나 들어가봅시다!!

비선점형 스케줄링

해당 스케줄링에는 FCFS(first-come first-served) 스케쥴링 방식과 SJF 스케쥴링 방식이 있습니다. 

1. FCFS (first-come first-served)

자료구조 중에 Queue 라고 들어보셨나요?? 선입선출 방식이잖아요? 

즉, 먼저 들어온 놈이 먼저 나가는 방식이 이 스케쥴링 방식인거에요~ 

자! 지금 여러분이 마트에 갔다고 상상해보세요~ 그리고 마트에는 계산대가 하나밖에 없어요. 

사고싶은 것들을 사고 계산을 하려고 계산대에 갔는데 아주머니 두분이 서계셔요. 여러분들은 어떻게 하나요??

맨 앞에 가서 줄 서나요?? 그런사람은 없겠죠? 맨 뒤에 가서 줄서야죠!!! 이 방식인거에요 먼저 온 사람이 먼저 계산하는 방식인거죠. 

근데 앞에 아주머니 두분은 쇼핑카트에 온갖 물품들로 가득채워져 있는데 여러분들은 껌 하나만 들고 있어요. 

그렇다면 어떻게 계산하는게 전체적으로 봤을 때 효율적이라고 생각되시나요?? 

아주머니께 "죄송한데,, 껌 한통인데 계산 먼저 하면 안될까요??" 하고 싶은 마음이 솟구치지않나요??

하지만 그렇게 할 수 없어요. 왜냐! 먼저 줄 선 사람아 먼저 계산을 해야하는 규칙이 FCFS 방식인거죠.

FCFS 방법은 먼저 온 요청을 먼저 처리하기 때문에 대단히 합리적인 스케줄링 방식인 것 같지만 경우에 따라 비효율적인 결과를 초래하기도 합니다. 

2. SJF (Shortest-Job First)

이 방법은 CPU 버스트 시간이 더 짧은 프로세스를 수행합니다. CPU burst time이 무슨말이냐면 프로세스가 작업을 완료할 수 있는 CPU의 할당 시간이라고 생각하시면 돼요.

만약 물건 하나를 계산하는데 걸리는 시간이 1초라면 물건이 10개면 10초 , 100개면 100초!

즉, 많을수록 CPU burst time은 길어지는거에요~  

자! 만약 A 아주머니가 계산을 하고 있는 도중에 B 아주머니랑 제가 도착했어요~ 그러면 계산할 게 별로 없는 제가 A 아주머니 뒤에 바로 기다리는 거에요. 왜냐! 난 껌 하나만 들고 있으니까 CPU burst time이 짧으니깐요!

근데 만약 A 아주머니가 만약 물건이 1000개를 들고있고 아직 2개밖에 계산을 안한거에요.

이건 좀 문제 되겠죠.. 뭔가 입이 근질근질 거려서 뭔가 먼저 계산하고 싶다고 말하고 싶지만 SJF 방식도 비선점형 방식이기 때문에 계산 하고 있다면 중간에 교체가 안된답니다.

즉, B 아주머니와 여러분의 위치만 순서를 정할 수 있는거지, A 아주머니가 계산대를 이용하고 있으면 끝날때까지 기다리는거죠.

선점형 스케줄링

비선점형 방식에서는 뭔가 비효율적인 문제가 생기는거 같죠? 

그래서 이러한 비효율적인 문제를 해결하기 위해 선점형 방식이 나오게 됩니다. 

선점형 방법은 여러가지가 있습니다! 하나하나 살펴봐요

1. SRTF (Shortest Remaining Time First) 

단어를 해석해보면 남아 있는 것 중 가장 짧은 시간을 가진 놈을 처리하라 라는 뜻 같네요?

 아까 위에서 예로 들었던 SJF 사례와 비슷하지만 계산하고 있는 사람을 포함한 모든 사람들 중 작업량이 가장 적은 사람을 먼저 처리하는 스케줄링 방식입니다! 

현재 A 아주머니가 1000개중에 2개만 계산했고 998개는 남아있어요. 그렇다면 어떻게 해야겠어요?

그쵸 그 아주머니한테 말해야죠. 이건 소심해도 말은 해야해요. 998개는 너무하잖아요.

"저...  A 아주머니 저 껌 한통..인데 ㅎ (머쓱) " 

그러면 A아주머니는 뒤로 가시겠죠. 그리고 B아주머니가 말해요.

"어머! 민수엄마 나 맛살 3개만 계산하면 되는디~  먼저 계산하면 안될까잉?"

그러고 A 아주머니는 또 뒤로 갑니다. 

근데 여기서 만약 껌만 사려고 하는 사람이 계속해서 줄을 서면 결국 A 아주머니는 계속 뒤로 밀려날겁니다.

결국 껌만 들고 있는 사람이 계속해서 들어오면 A 아주머니는 카트에 물건이 많다는 이유로 영원히 계산 못하는 현상이 발생할 수 있는 거죠. 이러한 현상을 기아현상이라고 합니다. 

이러한 현상을 해결하기 위해 우선순위 스케줄링이 도입됩니다.

2. 우선순위 스케줄링 (priority scheduling) 

말 그대로 우선순위가 가장 높은 프로세스에게 제일 먼저 cpu를 할당하는 방식이에요. (선점, 비선점 두방식 모두 사용할 수 있습니다! )

여기서 우선순위값이 작을수록 높은 우선 순위를 가지는것으로 가정해요.  

즉, 껌을 들고있는 사람은 우선순위값은 1 , B 아주머니는 우선순위값은 2, A 아주머니는 우선순위값이 3인거겟죠?

근데 여기서도 껌을 들고 친구들이 줄줄이 들어오면 결국 A 아주머니는 또 우선순위에서 가장 뒤로 밀려나겠죠?

이 방식도 기아현상이 발생할 수 있는거에요

그래서!  "노화(aging) 기법"을 사용합니다.

노화 기법이란 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당 받을 수 있게 해주는 방법이에요. 

버스나 지하철에서 나이 드신 분께 자리를 양보하듯이 프로세스가 오래 기다려서 나이를 계속 먹게 되면 우선순위를 높여 CPU를 먼저 할당받게 되는거죠. 

여기서 껌을 들고 있는 사람이 줄줄이 도착하면 처음엔 A 아주머니는 뒤로 밀려나겠죠.

하지만 기다리는 시간이 길어짐에 따라 A 아주머니의 우선순위도 점점 올라가겠죠? 그리고 언젠가는 계산할 수 있게 되는거죠. 

3. 라운드 로빈 스케줄링 (Round Robin Scheduling) 

다음 스케줄링은 시분할 시스템의 성질을 가장 잘 활용한 스케줄링입니다!! 

각 프로세스마다 CPU를 사용할 수 있는 최대시간을 time quantum이라고 합니다. 그냥 퀀텀이라고 전 부르겠습니다. 

이 퀀텀의 시간이 끝나버리면 해당 프로세스는 대기하고 있는 프로세스의 맨 뒤에 가서 줄을 서는거에요 

예를 들어, A아주머니, B아주머니 그리고 제가 있고 각자 계산할 물건이 100, 50, 30개가 있다고 가정을 해봅시다. 

여기서 퀀텀을 100으로 잡아버린다면  A 아주머니와 B 아주머니 모두 계산할 때까지 기다려야겠죠?

만약,  퀀텀을 1로 잡아버린다면 A -> B -> C -> A -> B -> C .....................................

계속 이런식으로 진행되는데 그렇다면 99-> 49 -> 29 ->98 -> 48 -> 28 ......................

이렇게 너무 짧은 퀀텀을 가지니까 Context switching이 너무 빈번히 일어나서 오버헤드가 커요. 

그래서 퀀텀을 적당한 시간으로 책정합니다. 만약 퀀텀을 30으로 잡는다면 

A : 70 -> B : 20 -> 나 : 0 -> A : 40 -> B : 0 -> A : 10 -> 0 이렇게 끝나겠네요!!  

퀀텀을 1로 잡았을 때보다 문맥교환이 덜 일어나고 모두 공평하게 처리되는것이 보일거에요 

그래서 공정한 스케줄링 방식이라고 할 수 있습니다! 

일반적으로 할당시간을 수십 밀리초 정도의 규모로 설정하게 됩니다.

이는 여러 프로세스가 동시에 수행되는 환경에서 CPU를 할당받기까지 지나치게 오래 기다리지 않을 정도의 시간 규모에 해당해요. 10 밀리초는 0.01초라고 생각하시면 됩니다!!

4. 다단계 큐 (Multilevel Queue)

아래 그림을 보시면 프로세스마다 종류가 있고 우선순위가 다릅니다.

우선순위가 높은 프로세스와 낮은 프로세스는 무슨 차이지 의문이 드실겁니다~ 

예를 들어, 여러분들이 구글을 켜서 구글링 할 때 바로바로 안튀어나오면 답답함을 느끼잖아요?

대신에 무언가를 다운을 받을 때는 해당 작업을 실행시켜놓고 신경 쓰지않는 프로세스들도 있을거에요. 

즉, 프로세스마다 사용자에게 우선적으로 먼저 처리되어야 하는 그룹으로 나누고 각 그룹에 따라서 처리 할 큐를 여러개 두어 사용하는 것이 Multilevel Queue라는 거에요 

foreground 프로세스처럼 반응 속도가 빨라야하는 프로세스에게는 타임퀀텀을 작게 하고, background 프로세스는 사용자와의 상호작용이 없으므로 타임퀀텀을 길게 함으로써 FCFS방식으로 처리합니다.

이렇게 큐를 분리하면 프로세스의 우선순위와 작업 형태를 고려하여 스케줄링을 할 수 있는거죠~ 

하지만 다단계 큐에서 단점이 있습니다. 이것 또한 우선순위가 높은 상위 큐 프로세스가 계속해서 들어온다면, 하위 큐 프로세스의 작업을 할 수 없게돼요~ 

우선 순위가 1번인 큐에 CPU 할당을 기다리는 프로세스가 있다면 우선순위가 2번인 큐의 프로세스는 1번 큐에 있는 프로세스의 작업이 끝날 때까지 기다려야한다는 겁니다. 

이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링입니다. 

5. 다단계 피드백 큐 (Multilevel Feedback Queue) 

바로 이전에 설명드렸던 다단계 큐 같은 경우에는 우선 순위가 낮은 프로세스는 CPU의 할당을 계속해서 기다려야 하는 상황이 생길 수가 있어요~ 이처럼 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완하기 위해 다단계 피드백 큐가 나오게 됩니다. 

다단계 피드백 큐는 다단계 큐와 기본적인 형태가 같아 우선순위를 가진 여러 개의 큐를 사용합니다.

하지만 피드백 큐의 특징은 CPU를 사용하고 난 프로세스는 우선순위가 낮아진다는 거에요.  이게 핵심이에요! 

CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어가게 돼요~

이렇게 되면 상위 큐의 작업 프로세스들이 우선 순위가 계속해서 낮춰지니까 언젠가는 하위 큐의 프로스세들과 같은 우선순위가 된다는 거죠! 그렇게 된다면 하위 큐의 프로세스들 또한 CPU를 할당 받을 수 있을거에요~

그런데, 기존에 있던 상위 큐의 프로세스들의 우선순위가 낮아지면 언젠가는 낮은 우선순위의 프로세스들도 CPU를 할당 받겠지만 만약 우선순위가 높은 프로세스들이 계속 들어오게 된다면 이것 또한 기아현상이 발생하지 않을까요??

피드백 큐는 큐 사이로 프로세스들의 이동이 가능하기 때문에 여기서도 aging 기법을 활용해서 오랜시간동안 할당 받지 못한 프로세스가 있다면 상위 큐로 격상시키면서 우선순위를 올려줄 수 있는거랍니다 ㅎㅎ

또한, 피드백 큐는 프로세스의 우선순위가 낮아질수록 해당 큐의 타임 퀀텀은 커지게 돼요.

피드백 큐에서는 우선순위가 낮은 프로세스의 실행 기회를 주려고 하지만, 그렇다고 해도 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스보다 CPU를 얻을 확률이 여전히 낮아요. 따라서 어렵게 얻은 CPU 를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임퀀텀을 크게 설정하는 거랍니다~ 

결국 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는 (우선순위가 가장 낮은) 프로세스는 무한대의 타임 슬라이스를 얻게 돼요. 무한대의 타임 퀀텀을 얻는다는 것은 프로세스가 실행상태가 들어가면 cpu 를 빼앗기지 않고 끝까지 작업을 마친다는 의미입니다.

그러므로 다단계 피드백 큐 스케줄링에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작합니다. 

다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식이라고 합니다 ㅎㅎ

이번 주제에서는 여러가지 스케줄링 방식을 포스팅 했습니다. 

이해를 최대한 쉽게 하려고 그림을 그렸는데 도움이 됐을지는 모르겠네요 :) 

다음 시간에는 무엇을 배울거냐! 

각각의 프로세스가 메모리에 상주할 때 어디까지가 A프로세스고, 또 어디까지가 B프로세스인지 어떻게 구별할까요??? 

혹여나 프로세스의 메모리 공간이 어떻게 안겹치고 메모리에 상주하게 되는지 궁금하지 않으신가요??

안궁금하실 거 같지만 배웁시다 ㅎㅎ

다음주에 뵙겠습니다!!! 감사합니다 :)