OS | CPU 스케줄러, CPU 스케줄링 알고리즘

 

 

CPU스케줄링이란?

 

 

 

프로그램을 실행시키면 메모리는 프로세스를 생성하고 각 프로세스는 쓰레드가 생깁니다. CPU를 차지하기 위해 모든 프로세스등은 운영체제의 명령을 기다립니다. 운영체제가 모든 프로세스에게 CPU를 할당/해제 하는데 이를 CPU스케줄러라고 부릅니다. 운영체제의 목표는 컴퓨터 자원, 특히 cpu를 얼마나 효율적으로 쓰는 지에 있습니다. 프로세스들이 얼마나 빠르게 반응하고, 그에 따라 자원들이 적재적소로 활용되는 것. 이 목표가 중요하기 때문에 cpu스케줄링의 최적화도 매우 중요합니다. 

 

CPU스케줄링의 최적화 목표에는, 

 

 1. 어떤 프로세스에게 cpu리소스를 주어야 하는지?

 2. cpu를 할당받은 프로세스가 얼마의 시간동안 사용되는가?

 

 

이 두개가 있습니다.

 

프로그램을 가동시켜 프로세스가 되면 <생성-준비-대기-실행-완료>의 다섯가지 과정을 거치게 됩니다. 이 때 여러개의 프로세스가 가동될 시에는 운영체제는 cpu를 프로세스들에게 번갈아서 할당해줍니다. 실행에 있는 프로세스는 할당이 끝나면 준비단계로, i/o요청이 있다면 대기 상태로 가게 됩니다. 

 

참고로 준비, 대기 상태는 큐 자료 구조로 관리됩니다. *큐 자료구조는 마트 계산대다. 먼저 온 사람이 먼저, 나중에 온 사람은 나중에. 

 

 

프로세스들이 cpu를 받는 대기 상태로 들어왔을 때, 어떤 프로세스가 우선순위를 갖게 될까요? 저번에 다룬 주제에서 프로세스 별로 우선순위가 있다고 언급했습니다. 그 우선순위는 빠르게 들어왔거나, 자주 많이 쓰거나, 그 외의 이유 등등이 있습니다. 준비, 대기 상태가 큐 자료 구조로 관리되기 때문에 주로 먼저 들어온 프로세스가 실행이 먼저되지만 우선순위라는 것은 항상 존재합니다. 우선순위가 높으면 더 빨리 들어온 프로세스보다도 더 빨리, 더 많이 cpu가 할당되곤 합니다.

cpu스케줄러가 매번 프로세스 제어 블록을 뒤져 우선순위를 검색하는 것은 효율적이지 않습니다. 그러므로 프로세스의 우선순위 별로 정리 되어있는 준비상태의 다중 큐로 프로세스의 정보가 들어있는 pcb가 들어갑니다. 이 pcb의 정보에 따라 cpu스케줄링의 프로세스 관리가 정해집니다.

 

 정리하자면, 운영체제는 프로세스들을 실행할 때, cpu를 할당해주는데, cpu할당을 하는 것은 다양한 조건을 가지며, 프로세스의 정보를 가지고 있는 pcb가 준비상태의 다중큐에 들어가고, cpu스케줄러는 준비상태의 다중큐를 보고 어떤 것을 작동시킬지 결정합니다.

 

cpu스케줄링은 빠르고 정확한 것이 중요하겠지요? 이럴 땐 항상 알고리즘을 세워 어떻게 하면 효율적이게 작동하는 지 보는 것이 중요합니다. cpu스케줄링을 빠르게 하는 시도는 컴퓨터가 빠르게 작동하고 발전하기 위해 필연적이였습니다. 다양한 cpu스케줄링 알고리즘이 있으며, 이에 따른 평가 기준을 알아보겠습니다.

 

 

---

 

CPU스케줄링 알고리즘 평가기준

 

cpu스케줄링 알고리즘 평가 기준

1. 리소스 사용률 

    a. cpu 사용률 높이기 가만 있는 cpu 절대 못봐! cpu가 무조건 많이 쓰여야 합니다.

    b. i/o 디바이스 사용률 높이기

2. 오버헤드 최소화 (overhead: 과부화)

    스케줄링 계산이 너무 복잡하거나 문맥교환 context switch가 빈번하면 오버헤드가 일어납니다.

3. 공평성

    모든 프로세스에게 공평한 cpu할당이 이뤄져야 합니다.

4. 처리량

    같은 시간 내에 더 많이 처리할 수 있는 방법이 목표가 됩니다.

5. 대기 시간 

    작업 요청, 처리 시 대기시간이 짧은 것이 중요합니다.

6. 응답 시간 

    얼마나 빠르게 반응이 오는 지가 중요하기 때문에 응답시간이 매우 매우 중요합니다.

7. 반환 시간

    대기시간 + 실행시간 더한 값

 

  스케줄링 알고리즘의 성능을 비교할 땐 평균 대기 시간을 측정합니다. 평균 대기 시간은 모든 프로세스의 대기 시간을 합한 후, 프로세스로 나눈 값입니다.

 

이런 평가 기준으로 그동안의 스케줄링 알고리즘이 발전했고 평가 받습니다. 

 

 

---

 

스케줄링 알고리즘 

 

 

1. FCFS (= FIFO First Come First Served, First In First Out)

   

말 그대로 먼저 온 사람이 먼저 나가는 선입선출 스케줄링입니다.

 

장점: 단순하며 직관적입니다.

 

단점: 프로세스가 끝나야 다름 프로세스가 진행됩니다. 실행 시간이 짧고 늦게 도착한 프로세스1이 실행 시간이 길고 빨리 도착한 프로세스2를 기다리니 비효율적입니다. 또, i/o작업을 할 땐 cpu가 쉬기 때문에 cpu사용률이 떨어집니다.

 

 

2. SJF (=Shortest Job First)

   

 

큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 cpu를 할당하는 방식이며, FCFS에서 짧은 시간의 프로세스가 먼저 실행되면 평균 대기 시간이 짧아지는 아이디어를 보완한 알고리즘입니다. 최단 작업 우선 스케줄링이라 부릅니다. 

 

장점: 실행시간(=burst time)이 작은 작업을 선 실행하기에 시스템의 효율성이 높아지는 장점이 있어 효율적입니다.

 

단점: 실제로 구현 시 문제가 많습니다. 일단 1번, 어떤 프로세스가 얼마나 실행될 지 예측할 수가 없습니다. 2번, burst time이 긴 프로세스는 자꾸 뒤로 밀려 아주 오랫동안 실행되지 않을 수 있습니다. 이는 cpu스케줄러 알고리즘의 공평성에 매우 위배되는 문제이기 때문에 잘 쓰지 않습니다.

 

3. HRN (=Highest Response Ratio Next)

     

 

 SJF 알고리즘을 보완해서 또 만든 알고리즘! 최고 응답률 우선 스케줄링입니다. HRN은 SJF의 공평성 문제를 해결하기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링하는 방식입니다. 평균 대기 시간을 계산하여 우선순위를 만들었지만 이 또한 공평성에 또 위배되기에 잘 쓰이지 않습니다.

 

4. RR (=Round Robin)

 

     

FCFS를 또 보완해서 만든 알고리즘입니다. 똑같이 FCFS처럼 순서대로 작업을 처리하지만, 프로세스1에게 일정시간 만큼 cpu를 할당하고 할당시간이 지나면 강제로 다른 프로세스2에게 cpu점유율권을 빼앗깁니다. 이 때 프로세스 1의 순서는 맨 뒤로 가며, 할당시간을 타임슬라이스, 타임퀀텀이라 부릅니다.

 

    

 

 *만약 타임슬라이스가 무한대라면?

   

 FCFS알고리즘과 다를 바가 없으며 프로세스1의 실행이 매우 길다면, 프로세스2를 동시에 실행할 시에 굉장히 끊기는 상황이 생길 것입니다.

 

*타임슬라이스가 굉장히 작은 단위 1ms가 된다면? (*1,000밀리초 = 1초)

     

프로세스1과 프로세스2가 동시에 작업하는 것처럼 느껴지겠지만, 문맥교환이 빈번해 프로세스 처리량보다 문맥교환 처리량이 더 커지면서 오버헤드가 생깁니다.

 

*그렇다면 최적의 타임슬라이스는? 

 

사용자가 동시에 프로세스가 실행되는 것처럼 느끼면서 오버헤드도 적당한 정도입니다.

유닉스 운영체제는 타임슬라이스를 100ms, 윈도우는 20ms를 유지하고 있으며 10~200ms가 평균입니다.

 

 

5. SRT (=Shortes Remaining Time)

 

 

SJF + RR의 혼합방식입니다. RR을 기본으로 하지만, CPU를 할당받을 프로세스를 선택할 땐 남아 있는 작업 시간이 가장 적은 프로세스를 선택합니다.

 

장점: SJF와 비교했을 땐 평균 대기 시간이 짧습니다.

 

단점: SJF의 단점이였던 운영체제의 종료시간을 예측하기 어렵다는 것과, 불공평하다는 단점이 있습니다. 또 남은 시간을 계산하고 남은 시간이 적은 프로세스와 문맥교환이 빈번히 이뤄지므로 복잡합니다.

 

 

6. MQ (=Multilevel Queue)

 

 

우선순위에 따라 준비 큐를 여러 개 사용하는 방식입니다. 프로세스는 운영체제로 받은 우선순위로 해당 우선순위의 큐에 삽입됩니다. RR로 운영되는 큐며, 우선순위에 따라 다단계로 나뉘어져 있고, 상단의 큐에 있는 모든 프로세스 작업이 끝나야 다음 우선순위의 큐로 작업이 진행됩니다.

 

장점: 우선순위가 높은 프로세스가 우선순위 낮은 프로세스보다 먼저 작동하며, 우선순위와 작업 형태에 따라 타임슬라이스를 조절해 작업 효율을 높입니다.

 

단점: 우선순위가 높은 프로세스 때문에 비교적 낮은 프로세스의 작업이 연기됩니다.

 

 

7. MLFQ (=Multi Level Feedback Queue) 운영체제에서 가장 일반적으로 쓰이는 알고리즘

 

 

rr, mq의 업그레이드된 알고리즘입니다. 우선 순위를 가진 큐를 여러개 준비해서 우선 순위가 높으면 타임슬라이스를 적게 배치합니다. 우선 순위가 낮을 수록 타임 슬라이스의 크기는 커집니다. 프로세스 p1이 큐에 들어갔다가 첫 타임슬라이스 10초 후엔 20초인 큐에 들어가고, 계속 반복되면 최종적으로 타임 슬라이스가 무한초로 할당 받게 됩니다. 마지막 큐는 FCFS 스케줄링 방식으로 작동하니, 작업 속도가 제일 효율적입니다.

 

---

 

*cpu처리가 우선인 p1과 i/o작업이 병행되는 p2가 있다면? 

 

cpu처리가 우선인 작업을 cpu bound , i/o처리가 우선인 작업을 i/o bound라고 하는데,  cpu bound는 컴퓨터 내의 설치, 수학 계산, 과학 수치 계산을 주로 쓰며 i/o bound는 우리가 컴퓨터에 글을 쓰는 등의 행위이기 때문에 i/o  bound는 응답속도가 제일 중요하며 cpu bound는 cpu사용률과 처리량이 가장 중요합니다. 이를 병행했을 시에, 타임 슬라이스가 길다면 cpu사용률이 좋을지는 몰라도 i.o bound의 응답속도는 매우 느려서 답답할 것입니다. 이 때 타임슬라이가 적다면 문맥교환, 컨텍스트 스위칭은 자주 일어나지만 i/o사용률이 높아져서 사용자가 느끼기엔 매우 쾌적한 컴퓨터 환경일 것입니다. 이득을 크게 하고 손해를 보지 않는 작업을 MLFQ알고리즘은 계속 진행합니다.

 

*CPU바운드 프로세스와 i/o bound 구분을 어떻게 할까?

 

 cpu를 사용하는 프로세스가 실행하다가 스스로 cpu를 반납하면 cpu 사용률이 적은 i/o일 확률이 높고 반대로 cpu를 사용하는 프로세스가 타임슬라이스 크기를 오버해서 cpu스케줄러에 의해 강제로 cpu를 빼앗기면 Cpu bound일 확률이 높기 때문에 이를 계산해서 구분을 할 수 있습니다.

 

 

 

우리가 컴퓨터를 켜서 어떤 앱을 실행할 때, 그 앱은 프로그램이라고 부르며 실행 시 메모리에 올라가게 되므로써 프로세스가 됩니다. 프로세스들은 cpu의 할당을 받아야 제대로 실행이 됩니다. 프로세스들은 pcb를 생성하고, 쓰레드도 생성합니다. 프로세스pcb는 앱이 켜졌다가 종료될 때 까지  생성-준비-대기(입출력)-실행-완료의 단계를 거칩니다. 준비상태에서는 다중 큐라는 작업대에서 기다리게 되는데, 이 작업대는 대체적으로 순서대로 들어가는 곳입니다. 하지만 우선순위라는 것이 pcb정보 내에 존재하기 때문에 우선순위가 높은 것이 더 빨리 실행되곤 합니다. cpu스케줄러는 실행한 앱들, 프로세스들이 잘 실행되는 것이 중요하기 때문에 순서대로 작업을 받긴 하지만 우선순위를 갖는 것을 먼저 실행시킵니다. 한 프로세스만 실행시키면 매우 불공평하기 때문에 cpu스케줄러는 번갈아 cpu를 할당해주는데, 이 할당 방법이 매우 중요하므로 정교한 알고리즘이 필요합니다. 그 알고리즘은 꾸준히 발전하였으며 평가 기준이 있습니다. 지금 쓰는 알고리즘은 우선순위대로 타임퀀텀을 배당해주는 것입니다. 

 

이를 보면 cpu의 할당 방법과 기준을 잡는 것이 운영체제에게 얼마나 중요한 지 알 수 있습니다.