[운영체제] 1. CPU 스케줄링(개념, 알고리즘)

 

 

💡 CPU 스케쥴링(CPU Scheduling)이란?
: OS가 CPU를 사용하는 프로세스들 사이의 우선순위를 관리하는 작업이다. 즉 한정된 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것이다.

 

1. 스케쥴링 기준(Scheduling Criteria)

스케쥴링 기준은 최선의 알고리즘을 결정하는 데에 사용되는 기준이다.

 

중국집을 예를 들어 스케쥴링 기준에 대해 알아보자.

1. CPU 이용률 (CPU Utilization)
   • CPU를 가능한한 바쁘게 유지
   • 주방장 - 돈을 주고 고용했는데, 주방장에게 최대한 일을 많이 줘야 돈이 아깝지 않다.
2. 처리량 (Throughput)
   • 단위 시간당 완료된 프로세스의 개수
   • 회전율 - 식당에서 단위 시간당 손님을 몇명이나 내보낼 수 있는지에 대한 척도
3. 총 처리 시간 (Turnaround Time)
   
   • 프로세스의 제출 시간과 완료 시간간의 간격
   • 손님들이 중국집에서 들어오고 나서부터 밥 다 먹고 나가는 데까지 걸리는 시간을 일컫는다.
4. 대기 시간 (Waiting Time)
   • ready queue에서 대기하면서 보낸 시간의 합
   • 식사가 나오는 시간
5. 응답 시간 (Response Time)
   • 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지 걸리는 시간
   • 단무지라도 나오는 시간

CPU 이용률	처리량	총 처리 시간	대기 시간	응답 시간
높을수록	많을수록	짧을수록	짧을수록	짧을수록

위와 같은 특징을 가질 수록 바람직한 CPU 알고리즘을 가질 수 있다.

 

2. 알고리즘

FCFS (First-Come-First-Served)

• FIFO (First-In-First-Out) 과 동치
• 말그대로, 먼저 준비된 프로세서를 먼저 처리

먼저 CPU를 점유한 프로세스가 먼저 처리가 되기 때문에, 나중에 들어온 프로세스는 우선순위가 후순위로 미뤄진다.

가장 간단하고 공정한 알고리즘이다.

 

하지만 만약 실행시간이 긴 프로세스가 먼저 실행된다면, 뒤에 있는 프로세스들은 대기시간(Waiting Time)이 길어질 수밖에 없다.

이러한 특징 때문에 FCFS 알고리즘은 Convoy Effect(호위효과)가 발생한다.

호위효과란 앞선 프로세스가 실행시간이 길다면 실행시간이 짧은 프로세스들이 실행되지 못해 마치 부하처럼 뒤따라서 기다리고 있다는 것을 가리키는 효과이다. 

 

SJF (Shortest-Job-First)

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴링

이때 CPU Burst time이란 CPU 명령을 실행하는 것을 뜻한다.

SFJ는 각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 활용하는 알고리즘이다.

 

예를 들어, 화장실이 한 칸만 있는데, 변비가 있는 사람이 2시간동안 화장실을 쓰면, 1분만에 볼 일을 보는 사람은 2시간이나 기다려야 한다.

매번 화장실에 줄 서 있는 사람들 중에서 제일 볼 일을 빨리 볼 수 있는 사람에게 우선적으로 사용권을 준다.

그렇게 되면, 큐가 줄어들고 평균적인 대기시간(waiting time은) 줄어든다

 

따라서 SJF 알고리즘은 minimum average waiting time을 보장한다.

 

SFJ 알고리즘에는 두 가지 스케쥴링 방식이 존재한다.

1. 비선점형 (non-preemptive) 
   • CPU를 먼저 선점한다면 CPU burst가 완료될 때까지 다른 프로세스에게 선점(preemption)당하지 않는다.
   • 프로세스가 CPU를 다 쓰고 나가는 시점에 스케쥴 여부를 정한다.
   • SJF

 

 

1. 선점형 (preemptive)
   • CPU를 내줬다고 하더라도 더 짧은 프로세스가 도착하면, CPU를 뺏어서 넘겨주는 방식이다. 
   • 새로운 프로세스가 도착하면 언제든지 스케쥴링이 이뤄질 수 있다.
   • SRT(Shortest Remainig Time)

 

 

 

선점형(preemtive) 방식이 평균 대기시간이 짧다.

 

SJF 의 preemtive 방식의 average waiting time이 3초라는 것은 optimal이기 때문에 어떤 스케쥴의 알고리즘을 쓴다하더라도 3초보다 짧은 average waiting time은 얻을 수 없다는 의미가 있다.

 

평균 대기시간이 짧다고 모든 것이 좋은 알고리즘은 아니다. SFJ 알고리즘 방식에도 문제점이 존재한다.

1. starvation(기아현상)
   • SFJ 알고리즘은 극단적으로 짧은 job을 선호한다.
     따라서, CPU 사용시간이 긴 프로세스는 영원히 서비스를 못 받을 수도 있다.
   • 굶어 죽는다고 해서 기아현상이다.
2. CPU 사용시간을 예측할 수 없다.
   • 내가 CPU를 쓰러 들어와서 내가 얼마나 시간을 쓰고 나갈지를 알 수가 없다. (우선순위가 계속 밀릴 수 있음)
   • 그렇기 때문에 실제 서비스에서는 잘 사용하지 X
   • 과거의 데이터를 바탕으로 사용시간을 예측(estimate)할 수는 있어도, 정확한 사용시간 추정이 어렵다.

 

Priority Scheduling(우선순위 스케쥴링)

• 우선순위가 가장 높은 프로세스에게 CPU를 할당

Priority Scheduling도 SFJ와 마찬가지로 선점형 과 비선점형 스케쥴링 두 가지 방식이 존재한다.

 

1. 비선점형 (non-preemptive)
   • 선점된 프로세스의 CPU burst가 완료되면 스케쥴링
   • 우선순위가 높은 프로세스가 다음 차례가 된다.
2. 선점형 (preemptive)
   • CPU가 선점되었을지라도 현재의 프로세스보다 우선순위가 더 높은 프로세스가 도착한다면
     점유하고 있는 CPU를 빼앗을 수 있다.

각 프로세스마다 우선순위 스케쥴링에서는 priority number(int)가 주어지게 된다.

 

앞서 설명한 SJF는 우선순위 스케쥴링의 일종이다. 그렇기 때문에 SJF와 마찬가지로 starvation 현상이 발생할 수 있다.

컴퓨터 시스템적에서 효율성을 추구하는 것이 가장 중요하지만, 특정 프로세스가 지나치게 차별받는 것도 막을 필요가 있다.

 

이를 위한 해결법이 존재한다.

Aging(노화)이란? 

• 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 조금씩 높여준다.
• 아주 오래 기다리게 되면 우선 순위가 높아져서 언젠가는 CPU를 얻게 된다.
• 우리나라의 경로사상

 

RR (Round Robin)

• 할당된 시간을 미리 세팅해서 균등하게 일을 처리할 수 있도록하는 스케쥴링

현대적인 컴퓨터 시스템에서 사용하는 CPU 스케쥴링은 대개 Round Robin에 기반하고 있다.

또 대부분의 스케쥴링은 preemtive, 즉 선점형 스케쥴링 방법을 채택한다. timer interrupt와 같이 언제든 우선권을 빼앗길 수 있다. 

 

Round Robin 알고리즘은 다음과 같은 방식으로 동작한다.

1. 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다.
2. 할당 시간이 지나면 프로세스는 선점(preemted) 당한다.
3. 시간이 종료된 프로세스는 ready queue의 제일 뒤에 가서 다시 줄을 선다.

Round Robin은 응답시간이 빠르다는 장점을 가진다.

CPU를 줬다 뺐었다를 반복하기 때문에 누구든지 아주 짧은 시간만 기다리면 적어도 CPU를 한 번 맛 볼 수 있는 기회가 생기게 된다. 또 누가 CPU를 오래 쓸 지 모르는 상황에서 굳이 예측할 필요없이, CPU를 짧게 쓸 수 있는 프로세스가 빨리 CPU를 쓰고 나갈 수 있게 해준다.

 

Round Robin 알고리즘은 퀀텀타임을 얼마나 할당할 것인지가 가장 중요하다.

CPU를 길게 쓰는 프로세스는 기다리는 시간도 길어지고, CPU를 짧게 쓰는 프로세스는 프로세스를 기다리는 시간도 짧아진다.

즉 기다리는 시간, 대기 시간이 본인이 CPU를 사용하는 시간과 비례하게 된다.

q ⬆️	FCFS와 비슷해지기 때문에, Round Robin의 장점을 누리기 힘들다.
q ⬇️	타임퀀텀이 지나치게 작아지면, RR의 철학 측면에선 이상적이나, context switch가 너무 빈번하게 발생해 오버헤드가 커지게 된다.

그렇기 때문에 적당한 길이의 타임퀀텀을 주는 것이 바람직하며, 보통은 그 시간이 10~100m/s이다.

홍대 앞 화장실이 RR 알고리즘(5분 제한시간 있음;)

 

MLQ (Multilevel Queue)

• 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당
• 우선순위가 낮은 큐에서 작업 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는 선점형 스케줄링

이전까지는 ready queue에 한 줄로 서서 CPU를 기다렸다.

지금 Multilevel Queue나 뒤에 있을 Multilevel Feedback Queue는 여러 줄에 서서 CPU를 기다리게 된다.

1. system process
2. interactive process
3. interactive editing process
4. batch process
5. student process

 

태어난 출신에 따라서 영원히 우선순위를 극복할 수 없는 스케쥴링이다. (노비는 진골, 성골을 이길 수 없음)

MLQ는 다음과 같은 방식으로 동작한다.

• 레디큐를 여러 개로 분할되어 있으며, 각 큐는 독립적인 스케쥴링 알고리즘을 가진다.
  • foreground(interactive) → RR
  • background(batch - human interaction) → FCFS
• 각각의 큐에 대한 스케쥴링도 필요하다.
  • 우선 순위가 높은 스케쥴링 우선적으로 CPU를 사용할 수 있게 배치
  • 하지만 starvation 현상이 생길 수 있음
  • → 각 큐에 대한 CPU time을 적절한 비율로 할당한다.

 

Multilevel Feedback Queue

• 다 단계 큐 + 동적인 프로세스 우선 순위 변화 적용

Multilevel Feedback Queue는 다음과 같은 방식으로 동작한다.

1. 우선적으로 들어온 프로세스는 첫 번째 큐에 들어간다. 첫 번째 큐는 타임퀀텀을 짧게 준다.
2. 두 번째 큐는 첫 번째 큐보다 타임퀀텀을 길게 주지만, 우선 순위가 낮아진다.
3. 그 다음 큐들은 FCFS 방식을 채택한다. (타임퀀텀이 길어지기 때문)

 

프로세스가 다른 큐로 이동할 수 있기 때문에, Multilevel Queue와는 다르게 우선순위를 극복할 수 있다.

앞서, starvation 단점을 극복하기 위한 Aging 방식을 다단계 피드백큐와 같은 방식으로 구현할 수 있다.

 

다단계 피드백 큐 스케줄링의 경우 큐의 수, 각 큐에 대한 알고리즘, 우선순위 격상 또는 격하 시기 결정, 처음 프로세스들이 진입해야 할 큐 등등 매우 복잡한 판단을 요구한다.

 

3. 예상 면접 문제 🧑‍🏫

1. 선점형 스케쥴링과 비선점 스케쥴링의 차이는 무엇인가요?
   • 선점 스케줄링: 한 프로세스가 CPU를 차지하고 있을 때 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 차지하는 기법이다. 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에 유용하지만 선점으로 인해 오버헤드가 발생한다.
   • 비선점 스케줄링: 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 차지할 수 없는 기법이다.
     모든 프로세스에 대한 요구를 공정히 처리해 응답 시간의 예측이 가능하지만 짧은 작업이 긴 작업을 기다리는 경우가 발생한다.