CPU 스케줄링과 Realtime 스케줄링

이 포스팅은 숙명여자대학교 김주균 교수님의 운영체제 강의를 바탕으로 작성되었습니다. 자세한 내용은 OS? Oh Yes! 누워서 보는 운영체제 이야기를 참고하세요. (누워서 볼 만한 책은 아닙니다 하지만 쉽게 쓰여진 책은 맞음)

스케줄링이란?

• 스케줄링 : 여러 프로세스가 번갈아 사용하는 자원이 있을 때, 어떤 프로세스가 이 자원을 사용할 수 있도록 해줄 것인가를 결정한다.
• CPU 스케줄링 : 해당 자원이 CPU를 의미하는 경우. 다른 프로세스로 CPU를 전해줄 때, 기다리는 프로세스 중에 누구를 선택해야 할지에 대한 방식이나 기준을 제시한다.대부분의 스케줄링은 CPU 스케줄링이다. CPU 스케줄링은 스케줄링의 종류 중 Ready 상태의 어떤 프로세스를 골라 CPU를 할당해줄지 정하는 단기 스케줄링 방식이다.

스케줄링의 목적과 기준

스케줄링의 목적

• CPU를 할당받을 프로세스를 잘 골라 실행시켜주어 전체적으로 시스템의 성능을 높이는 것이다.

시스템 성능을 평가하는 기준

• 사용자 관점

  • 요청한 결과가 나오는데까지 걸리는 시간이 척도이다.
  • Response Time(응답 시간) : Interactive 시스템에서 중요하다. 프로세스의 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간을 말한다.
  • Turn-around Time : 일괄 처리 시스템에서 중요하다. 요청으로부터 결과를 돌려받는 데까지 걸린 시간을 말한다.

• 시스템 관점

  • 스케줄링을 통해 CPU가 얼마나 잘 활용됐는가가 척도이다.
  • Throughput(처리량) : 일괄 처리 시스템에서 중요하다. 단위 시간에 완료되어진 프로세스의 개수를 말한다.
  • Utilization(활용도) : 주어진 시간 동안 특정 자원이 실제로 가동된 시간의 비율을 말한다.

• 그외

  • Predictability : 요청한 일이 얼마 후쯤에는 완료될 수 있을 것
  • Fairness : 특정 P가 장기간 CPU를 받지 못하게 되는 경우를 최대한 피함

참고로 성능 지표 중 응답 시간과 처리량은 상충된다.

• 빠른 응답 시간을 주기 위해 스케줄링을 자주 하면 스위칭에 필요한 문맥교환이 발생하고, 결국 사용자 프로세스를 실행할 시간이 줄어들어 처리량은 감소한다.
• 처리량을 높이기 위해 수행 시간이 짧은 프로세스를 위주로 처리하면 수행 시간이 긴 프로세스는 처리가 낮아져 응답 시간이 길어진다.

스케줄링 정책의 우선순위

스케줄링 정책을 만들 때 고려해야 하는 기준을 알아보자. 설계하고자 하는 시스템 환경에 따라 스케줄링 정책의 기준이 되는 우선순위가 다르다.

• 프로세스의 성격
  • CPU-bound : 연산 위주 시스템
  • I/O-bound : 입출력 위주 시스템
• 응답 시간, 처리량
  • 대화형 시스템 : 응답 시간
  • 일괄처리 시스템 : 처리량
• 프로세스 크기
  • 크기 : 완료 때까지 요구되는 CPU 실행 시간
  • 주로 크기가 작을수록 평균 응답 시간은 줄지만, 큰 프로세스의 무한 대기가 발생하는 경향이 있다.

스케줄링 기법의 분류와 가동 시점

스케줄링 기법의 분류

• 비선점 : Nonpreemptive
  CPU를 스스로 반납할 때까지 계속 사용하도록 허용하는 방법
• 선점 : Preemptive
  실행 중인 프로세스로부터 CPU를 빼앗아 다른 프로세스에 할당하는 방법

스케줄링이 가동되어야 하는 시점

• 실행 → 대기 : 입출력 요청, Nonpreemptive (CPU 반납)
• 실행 → 준비 : 시간 종료 인터럽트, Preemptive (Time out으로 뺏김)
• 대기 → 준비 : 입출력 종료, Preemptive
• 프로세스 종료 Nonpreemptive (CPU 반납)

스케줄링 기법들

스케줄링 기법들을 하나씩 살펴보자. 이 포스팅에서 살펴볼 스케줄링 기법은 아래와 같다.

• FCFS(First Come First Service)
• SPN(Shortest Process Next) / SJF(Shortest Job First)
• SRT(Shortest Remaining Time)
• HRRN(Highest Response Ratio Next)
• Round-Robin
• Multi-level Queue
• MFQ(Multi-level Feedback Queue)
• Fair-share

FCFS(First Come First Service)

• 현재 프로세스가 CPU를 독점하는 비선점 방식
• 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당

단점

• 아주 긴 프로세스가 실행되는 경우 뒤에 있는 프로세스들은 오래 기다려야 하므로 대화식 시스템에 적합하지 않음.
• 평균 응답 시간이 길어진다.

장점

• 준비 상태 프로세스의 개수와 크기를 짐작할 수 있다면, 실행 시점을 예측 가능
• 도착 순서만이 실행 순서를 결정짓는다는 관점에서 공평하다

사용

• 가장 단순한 형태로 실제 시스템에 바로 적용되기는 어려움
• 보조 장치 - 우선순위가 동일할 경우의 차선책으로 활용

SPN(Shortest Process Next) / SJF(Shortest Job First)

• 준비 큐에서 기다리고 있는 프로세스 중에서 가장 짧은 것을 실행
• 비선점 방식
  

장점

• 평균 응답 시간 최소화
• 실행할 프로세스가 충분하면, 처리량에 관해 훌륭한 성능을 보임
• FCFS보다 빠른 응답 시간 기대

단점

• 실행 시간이 긴 프로세스가 CPU를 할당받지 못하고 계속 대기하는 무한 대기 현상
  • Aging : 기다린 시간만큼 우선순위를 높인다 (HRRN)
• 긴 프로세스일 수록 처리량에 편차가 커져 예측가능성이 떨어짐
• 각 프로세스의 크기를 실행 전에 정확히 알 수 없음에도 불구하고, 그 크기를 가지고 스케줄을 해야함

SRT(Shortest Remaining Time)

• SPN 선점 방식
• 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행
• 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어오면, 새 프로세스에게 CPU를 할당한다

장점

• SPN보다 빠른 반환 시간

단점

• 잦은 선점으로 인한 문맥 교환의 부담
• 무한 대기 현상 방지

• 0.5 : P2 도착. P1은 9.5 남았고 P2는 5 남았으므로 P2로 스위칭
• 1 : P3 도착. P2는 4.5 남았고 P3는 2 남았으므로 P3로 스위칭
• 3 : P3 종료. P1은 9.5 남았고 P2는 4.5 남았으므로 P2 실행
• 7.5 : P2 종료. 남은 P1 실행
• 평균 응답 시간 = 8.67
  • P1 : 17
  • P2 : 7.5-0.5
  • P3 : 3-1
• 하지만 더 많은 문맥 교환이 요구되어 실제 평균 응답 시간은 좀 더 길어진다

문맥 교환 줄이기 (Future-knowledge 스케줄링)

• 가까운 미래에 도착할 프로레스의 정보를 알 수 있다면
• 바로 CPU를 할당하지 말고 기다렸다가 SPN을 적용한다.

HRRN(Highest Response Ratio Next)

• SPN, SRT의 약점인 긴 프로세스의 무한 대기 현상을 방지
• 응답률이 가장 높은 프로세스에게 높은 우선 순위를 준다
  • 응답률 : (대기시간+CPU 요구량)/CPU 요구량
  • 스케줄링 할때마다 준비 큐의 모든 프로세스들에 대해 응답률을 계산하여 CPU를 줄 프로세스를 선정한다.
• 비선점 방식

응답률

• 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아진다. (Aging)
• 분모 - 큰 프로세스일수록 우선순위가 낮으므로, 평균 응답 시간의 단축도 기대

Round-Robin

• FCFS 기반 선점 방식
  • CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가고
  • 준비 큐의 맨 앞에 있는 프로세스가 CPU를 할당 받는다
• 시간 종료 인터럽트에 의해 CPU를 뺏긴다

일반 라운드 로빈

도착 순서 : 1-2-3-4, 시간 할당량 : 10밀리 초

장점

• FCFS처럼 한 프로세스가 CPU를 독점하는 단점 방지

단점

• CPU 선점에 따른 오버헤드 감수

사용

• 대화식 시스템이나 시분할 시스템에 적합
• 시간 할당량의 크기에 따라 시스템의 성능이 크게 달라진다
  • 크면 : FCFS 스케줄링 방식과 같음
  • 작으면 : 문맥교환의 오버헤드 커짐
  • 일반적으로 10~100밀리 초가 적당함

참고 : 입출력 프로세스의 보상

• 문제 : 연산 프로세스가 입출력 프로세스보다 CPU 사용에서 우대
  • 연산 위주 : 주어진 시간 할당량을 모두 소진하고 큐의 맨 뒤로 들어감
  • 입출력 : 시간 할당량을 남긴 채 입출력을 발생시키고, 시간 할당량이 끝나면 당시 남겨진 시간 할당량은 아무것도 못하고 보상받지 못한 채 큐의 맨 뒤로 들어감
• 해결 : Virtual Round-robin
  • 입출력을 마친 프로세스가 들어가는 준비 큐
  • 우선순위가 더 높다
  • 이 큐에서 CPU를 받을 때는 이전 입출력이 발생했을 때 쓰지 못하고 남긴 시간 할당량만큼만 준다

우선순위 스케줄링이란?

• 여러 가지를 고려하여 계산된 값을 프로세스가 생성될 때까지 부여하는 방식
• 대부분 선점 방식이다
• 정적 우선 순위 : 프로세스가 생성될 때 부여된 우선순위가 완료 때까지 변하지 않음
• 동적 우선 순위 : 시스템에 있는 동안 조정됨

Multi-level Queue

• 정적 우선순위를 사용하는 스케줄링을 구현하는 가장 적합한 자료구조
• 우선순위의 개수만큼 큐가 필요하다
  • 같은 우선순위 값을 가지는 프로세스를 위한 큐
  • 서로 다른 우선순위의 프로세스들을 구별하고 관리
• 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어간다
• 우선순위가 낮은 하위 단계 큐의 작업은 실행중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏긴다.
• 정적 우선순위이므로 큐들 간에 프로세스의 이동이 불가능하다

Multi-level Feedback Queue

• CPU 요구량을 몰라도 짧은 프로세스들에게 유리하면서 (SPN의 단점 극복)
  • 완료까지 남은 시간은 몰라도 지금까지 실행된 시간을 잘 활용
• 입출력 프로세스를 우대할 수 있는 스케줄링 기법 (가상 Round-Robin처럼)
  • CPU를 포함한 전체 자원들의 활용도를 높임

⇒ 프로세스의 성격에 맞도록 우선순위를 조정하여 적응성 있는 스케줄링이 가능하다.

• 동적 우선순위를 기반으로 하는 선점 방식
• 큐의 우선순위
  • 높음 : 시간 할당량 작음
• 프로세스의 큐 이동
  • 초기 : 새로운 프로세스는 최상위 단계의 준비 큐에 들어간다. 그 큐의 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어간다.
  • 마지막 단계 : 더 내려갈 단계가 없으므로 라운드 로빈 방식으로 실행된다.
  • 입출력 프로세스 우선 : 입출력으로 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐에 들어가서 우선순위가 높아진다.

Fair share

프로세스가 하나의 그룹일 때 문제점

• 위의 기법들은 모든 프로세스들을 하나의 그룹으로 취급하였다.
• 특정 프로세스에 CPU가 몰리면 나머지 프로세스가 불이익을 감수해야 한다.

Fair-share 방식

• 그룹별로 일정량의 CPU 시간을 할애했을 때, 특정 그룹에 속한 프로세스의 과도한 CPU 사용은 다른 프로세스에게만 불이익을 주고 다른 그룹으로 파급되지 않도록 한다.
• 1그룹 - AB, 2그룹 - CD, 3그룹 - FE이고 각각 50%, 25%, 25% 할애한다면, ACBEADBF의 순서대로 스케줄링한다.
• A에게 더 많은 CPU 시간을 주려면 ACAEADBF의 순서로 스케줄링한다.

실시간 시스템의 스케줄링

실시간 시스템이란?

• 실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템
• 경성(Hard Real-time)
  • 작업이 마감시한 내에 완료되지 않으면 시스템이 중지되는 등의 치명적인 결과를 초래한다.
  • 마감시한을 넘긴 후 완료되는 일은 아무런 가치가 없다
  • 일반적으로 실시간이라는 말은 경성을 일컫는다
• 연성(Soft Real-time)
  • 작업이 마감시한 내에 완료되지 않으면 데이터 손실 등의 피해가 발생
  • 마감시한을 넘긴 후 완료의 가치가 점점 떨어진다
  • 시스템은 계속해서 운영 가능

실시간 시스템에서의 스케줄링

• 정적
  • 프로세스들의 특징과 개수를 아는 경우
  • 실시간으로 운영되는 환경은 대부분 특수하므로, 할일의 성격이나 개수를 사전에 알 수 있는 경우가 많다
• 동적
  • 프로세스의 생성 시간이나 특성을 알 수 없는 경우

RM(Rate Monotonic)

• 정적 스케줄링 방식. 정적 환경에서 최적의 기법이다.
• 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용
• 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏는 선점 방식
• 주기(반복되는 마감시한)가 짧을 수록 높은 우선순위를 갖는다.

CPU 사용식을 만족하면, RM 기법으로 모든 프로세스의 마감 시한을 맞출 수 있다.

장점

• 스케줄링 비용이 적게 든다

단점

• 새로운 프로세스가 추가되면 전체 스케줄링을 다시 해야 한다

EDF(Earliest Deadline First)

• 동적 스케줄링 : 새로운 프로세스가 도착할 때 바로 대응할 수 있다
• 프로세스의 마감시한이 가까울수록 우선순위가 높다

CPU 사용식을 만족하면, EDF기법으로 모든 프로세스의 마감 시한을 맞출 수 있다.

장점

• 새로운 프로세스의 동적 수용이 허용된다

단점

• 그럴 때마다 가능한 스케줄을 찾기 위한 계산을 해야 한다

RM vs EDF

• 프로세스의 CPU 사용량은 실행해보기 전에는 알 수 없다.
• 정적 스케줄링 방식이 가능하다면 RM으로 스케줄링을 해본다. 만약 CPU 응답률 식을 만족하지 않는다면, 동적 스케줄링 방식을 실행하여 EDF 기법을 사용해본다. EDF는 RM보다 응답률 제한이 더 크기 때문에 해당 식을 만족할 가능성이 있다. 만약 CPU 응답률이 1을 벗어나면 컴퓨터 시스템의 능력을 벗어난 것이다.
• 만약 동적 스케줄링 방식만 사용 가능하다면 EDF를 사용한다. 정적 스케줄링 방식인 RM은 사용할 수 없다.