CPU 스케줄링 - 운영체제

 

스케줄러는  왜 필요할까?

CPU에서는 프로세스를 수행하는데, 최대 효율과 반응성을 높여야 한다는 목표가 있습니다.

이를 위해서는 스케줄링을 잘해야 합니다.

 

프로세스의 비용을 추상화 하면, Process Cost = CPU Brust + IO Brust 라는 식이 나옵니다. 여기서 Brust는 실행을 의미합니다.

CPU Brust는 CPU가 직접 계산하는 Cost을 의미하고, IO Brust는 인터럽트 발생 Cost을 의미합니다.

 

어떤 프로세스는 CPU Brust가 클것이고 어떤 프로세스는 IO Brust 부분이 더 클 것입니다. 

운영체제는 프로세스의 이러한 점을 고려하여 스케줄링을 행해야 합니다. 

 

CPU Brust가 큰 프로세스는 CPU Bounded Process라고 부르고, IO Brust가 큰 부분은 IO Bounded Process라고 부릅니다. 

스케줄러는 CPU-Bounded와 IO-Bounded을 잘 섞어서 우선순위를 만들어 실행해야 합니다.

그래야 CPU와 IO-Device 양쪽다 일을 하게 되고 최대 효율을 달성하기 때문입니다. 

 

 

 

스케줄링의 단계

스케줄링의 단계는 Term(스케줄링 일어나는 주기)을 기준으로 3가지로 나뉩니다.

1. Long Term 스케줄링:

말 그대로 스케줄링이 일어나는 주기가 느립니다.

 

아래의 그림을 살펴보면 Batch Jobs 큐에서 Ready Queue로 넘어가는 것을 롱텀 스케줄링이 조절하고 있습니다.

Batch Jobs 큐에서는 프로세스가 생성되고 있거나 생성후 대기를 하고 있는 곳 입니다.  

Job Scheduling이라고 부릅니다.

 

롱텀은 왜 중요할까?

시스템에 제출할(kernal에 등록할) 작업을 결정할수 있음:

Ready 큐에 들어온다는 의미는 이 프로세스를 당장 실행해도 문제가 없다는 의미입니다. (물론 우선순위 때문에 바로 실행 안될 가능성이 큼.)

다중프로그래밍의 정도(degree) 조절 :

시스탬내의 프로세스 수 조절할 수 있습니다. 시스탬 즉 커널 내에 프로세스의 수가 많다는 것은 그만큼 차지하는 커널 메모리의 용량과 CPU에 부담을 줄수 있다고 볼수 있습니다. 반대로 너무 적을시에는 CPU와 IO Device가 놀수 있기 때문에 효율성이 저하될수 있습니다. 롱텀 스케줄링은 이런면에서 중요하다고 볼수있습니다.

 

2. Midium-Term(intermdeiate) 스케줄링:

말그대로 스케줄링이 일어나는 주기가 중간입니다.

아래의 그림과 같이 Suspend, Blocked Queue들을 스케줄링 합니다.

 

프로세스가 Ready Queue에서 Suspend나 Blocked (두가지 상태를 Waiting으로 통일해서 부르기도 함.)상태로 들어가게 되면, 그 프로세스는 메모리에서 다른 곳으로 옮겨져야 합니다. 이 때문에 메모리 할당에 영향이 생기는 것입니다.(디스크로 이동..)

따라서, 미디엄-텀 스케줄링은 프로세스의 상태 변화(Suspend, Blocked 등)에 따른 메모리 할당을 결정하고, 이를 통해 시스템의 전반적인 성능과 효율성을 높이는 역할을 합니다. 

 

Midium-Term 스케줄링은 메모리 할당 결정과 연관이 있습니다. 

 

3. Short-Term 스케줄링:

말그대로 자주 스케줄링이 일어납니다.

 

프로세스를 Ready에서 Running으로 Dispatch하는 역할입니다. CPU에게 프로세스를 할당 시켜주는 역할입니다.

인터럽트나 여러가지 IO등에 따라 매우 자주 일어나므로 빨라야 합니다. 

 

일반적으로 CPU 스케줄링이라고 한다면 Short-Term 스케줄링을 의미합니다. 프로세스 스케줄링이라고 부릅니다.

 

 

Preemptive와 NonPreemptive

 

스케줄링에는 2가지 방법이 존재한다.

 

Preemptive:

프로세스가 Running상태에 있을 때, 프로세스가 아닌 외부에서 할당을 해제할수 있습니다. 

 

context switch overhead가 상대적으로 크고 time-sharing system과 real-time system등에 적합합니다.

 

NonPreemptive:

프로세스가 할당받은 자원을 스스로 반납할때까지 사용합니다.

system call i/o등이 예시입니다.

context switch overhead가 적고 잦은 우선순위 역전과, 평균 응답시간증가가 발생합니다.

(우선순위 높은애를 늦게 처리하므로 빠르게 처리못하게 됩니다. Starvation 위험)

 

 

스케줄링이 일어나는 상황 4가지

• IO 요청 (Running -> Waiting)
• 멀티프로그래밍 환경에서 TimeOut이 일어나 Ready로 바뀌는 경우 (Time Run Out)
• IO가 끝났다는 요청 (IO Finished Interrupt, Waiting -> Running)
• 종료 (Running -> Terminated)

1번과 4번은 NonPremitive입니다.

2번과 3번은 Preemitive입니다.

 

스케줄링 측정 기준 5가지

• CPU Utilization:
  • 말그대로 CPU을 최대한 일하게 하는 것을 의미합니다.
• Throughput:
  • 단위시간동안 완료된 작업의 수. Batch System이 클수록 좋습니다.
• Turnaround time:
  • 특정 프로세스를 시작하고 난뒤 끝날때까지의 시간.(처음 Running상태가 일어나고 Terminated상태가 되기까지의 시간.) 일반적으로 짧을수록 좋다. 
• Waiting time:
  •  Ready Queue에서 대기하는 총 시간을 의미합니다. 이를 통해서 Starvation을 예방하는 스케줄링 기법을 개발합니다.
• Response time:
  • 작업요청으로부터 응답을 받을때까지의 시간 => interface system real-timeRequest가 주어졌을 때 얼마나 걸리는지의 시간. 카톡대화같은 것을 의미합니다.
  • 끝났을때가아닌 응답이 나올때까지의 시간.

1,2는 클수록 좋고 3,4,5는 작을수록 좋습니다.

 

 

스케줄링 기법들

여러가지 스케줄링 기법들이 존재한다.

FCFS(First Come First Start)

선착순 알고리즘으로서 Ready Queue에 도착한 시간을 기준으로 스케줄링이 일어납니다.(NonPremitive)

자원을 효율적으로 활용할 수 있고 일괄처리 시스템(Batch System)에 적합하여 CPU Utilization과 ThroughPut측면에서 매우 유리합니다. 단점은 반응형 시스템에 부적합하며 Response Time과 Waititng Time이 길어지게 됩니다.

 

CPU 스케줄링뿐만 아니라 스케줄링이라는 단어가 나오면 FCFS는 공평하기 때문에, 항상 나오는 알고리즘입니다.(Like FIFO, 이름은 다르지만 같은 형태로 등장한다.) 시스템에서 공평하다는 의미는 쉽게 예측이 가능하다는 의미로 직결되므로 공평성 또한 중요한 요소입니다.

SJF(Shortest Job First)

FCFS는 빠르게 처리할수 있는 것 조차 Ready Queue에 늦게 들어왔다는 이유로 늦게 처리될수 있습니다.

이러한 단점을 보완하기 위해 Burst-Time이 가장 적은 프로세스먼저 처리하자는 SJF가 등장했습니다.(NonPremitive)

 

평균적인 Waiting Time을 낮출수 있으며 시스템내 프로세스 수를 최소화 할 수 있습니다.

이는 많은 프로세스들에게 빠른 응답시간을 제공합니다.

 

(시스템내 프소세스 수 최소화 =>스케줄링 부하 감소 -> 메모리 절약 -> 시스템 효율 향상 -> 많은 프로세스들에게 빠른 응답시간 제공)

 

반면 단점으로  Brust Time이 긴 프로세스는 영원히 대기할수도 있습니다.(Starvation)

 

(aging이라는 개념을 더한, hrrn이라는 스케줄링 기법도 있음. 대기시간을 고려함.)

SRTF(Shortest-Remaining-Time-First)

SJF에서 Brust Time이 아닌 Remaining-Time을 기준으로 스케줄링합니다.(Preemptive)

 

장점 SJF의 장점을 극대화 가능합니다.(waiting time을 더욱 최소화 할 수 있음. Context Switiching 고려 안했을 경우)

단점 : context switching이 커지고 잔여실행을 계속 추적해야해서 오버헤드가 커지고 예측도 힘들어서 사실 현실적으론 쉽지않다고 합니다.

RR(Round Robin)

자원 활용에 제한시간이 존재하며 할당된 시간(Time Quantum)이 지나면 자원을 반납하는 스케줄링 기법입니다.

예시: "각 프로세스마다 2초씩 사용하자."

 

라운드 로빈도 FCFS처럼 공평성을 갖고있기 때문에 자주 등장하는 개념입니다.

(대기시간이 q이고 앞에 존재하는 프로세스의 수가 n-1이라면, 대기시간의 upper bound는 (n-1) * q가 될수있으므로 예측이 가능합니다.)

 

응답이 빨라야 하는 시스템에 적합합니다.

 

성능을 결정하는 애는 Time Quantum인데, 애를 어떻게 설정하느냐에 따라 성능이 달라집니다. 

(만약 무한대라면 FCFS와 같고, 0에 가깝다면 Time Sharing System같이 느껴질 것임. 체감 프로세서의 속도 = 실제 프로세서 성능의 1/n)

 

Multilevel Queue

ready queue을 여러개를 갖는것.

한번 배정받은 큐를 못벗어납니다. (이것도 단점 이를 극복하기위해 mfq가 생김.) 

각각의 큐는 자신만의 스케쥴링 기법을 사용합니다. = fixed priority preemptive scheduling

 

각 큐에는 CPU 이용률에 대한 가중치를 받습니다. (예시: Q1 30%, Q2: 50%, Q3: 20%, 가중치를 정하는 방식 또한 우선순위입니다.)

각 큐에는 다른 스케줄링 기법이 적용되어 있습니다.

 

장점: 빠른응답시간(?) => 이것도 말의 어폐가 있는게 우선순위가 빠른 큐만 빠르게 응답하고 아닌큐들은 느립니다.

 

단점: 우선순위가 낮은 큐는 starvation현상 발생할수 있고, 큐관리로 인한 오버헤드 발생합니다.

Multilevel Feedback Queue

 

MQ의 변형입니다.

위에서 나온 단점인 Starvation과 배정받은 큐를 벗어날수 있게 변형되었습니다.

 

변형 :

1. 각큐마다 시간(timequantm)다르게 배정하기. (라운드로빈)

2. 입출력위주로 상위로 올리기(i/o bounded):  IO가 많이 일어나는 프로세스를 상위로 올림 -> 많은 프로세스를 CPU을 적게 사용하면서 해결 -> 결과적으로  시스템 전체의 평균응답시간이 줄어지고 입출력 작업을 분산시킵니다.

3. 해당 시간안에 못끝낼시 하위의 큐로 넘김.