OS - CPU 스케줄링

CPU 스케줄링

os_5_1

프로세스의 일생은 아래 2 단계에서 모두 처리된다.

  • CPU burst: CPU에서 기계어가 실행되는 단계
  • I/O burst: I/O작업을 하는 단계

물론 프로세스 종류에 따라 두개 단계의 할당량이 다르다.

프로세스의 I/O빈도는 지수함수 형식으로 나타나는데 I/O와 CPU작업이 비례하는 프로세스는 적다는 뜻이다.

os_5_2

I/O 작업 빈도수에 따라 프로세스를 다르게 부르는데

  • I/O bound job: I/O빈도가 많은 프로세스, 짧고 많이 CPU사용
  • CPU bound job: I/O빈도가 낮고 CPU를 오래 사용하는 프로세스, 길게 몇 번만 CPU 사용

사람과 interaction이 많은 프로세스는 I/O작업이 중간중간 많은 I/O bound job
수학연산이나 과학연산이 많이 필요한 프로세스는 CPU사용이 긴 CPU bound job

그렇다면 2종류의 프로세스가 CPU를 기다리고 있다면 누구에게 먼저 CPU를 줘야할까?

일반적으로 CPU를 조금만 쓰고 바로 I/O작업을 하러갈 I/O bound job에 주는 것이 효율적이다.

사람이 많이 사용하는 프로세스이기 때문에 사용자의 답답함도 줄여주고 I/O 장치가 노는 시간도 줄어든다.

이 두 종류의 프로세스들에게 가장 효율적으로 CPU를 주기위해 CPU scheduler, Dispatcher 가 필요하다.

  • CPU Scheduler: Ready 상태 프로세스 중 CPU 를 줄 프로세스를 고르는 OS코드
  • Dispatcher: CPU사용이 결정된 프로세스에게 실제로 CPU를 넘기는 OS코드
    (문맥교환 해주는 코드)

Nonpreemptive, Preemptive(비선점, 선점 스케줄링)

CPU스케줄링방법은 Nonpreemptive, Preemptive 로 나뉜다.

CPU 를 받으면 중간에 뺏기지 않고 가는 스케줄링방법이 Nonpreemptive,
CPU 를 계속 쓰고 싶더라도 Timer 로 인해 CPU를 뺏기는 스케줄링방법이 Preemptive이다.

이전에 보앗듯이 프로레스의 상태변화 4단계인데

  1. Running -> Blocked (I/O요청 시스템콜)
  2. Running -> Ready (Timer인터럽트)
  3. Blocked -> Ready (I/O작업이 끝난후 인터럽트)
  4. Terminate

이중 1과 4의 경우는 CPU를 자진 반납하는 Nonpreemptive,
2와 3은 강제로 빼앗은 Preemptive이다.

Scheduling Criteria(스케줄링 성능척도)

스케줄링 방법 여러 가지다. FCFS, SJF, SRTF, Round Robin 등등.
이 중 어느 스케줄링 방법이 가장 효율적인지 판단할 수 있는 방법을 성능척도라 한다. 성능척도는 다음 내용에 따라 결정된다.

  • CPU Utilization (CPU이용률)
    CPU가 놀지 않고 일한 비율. CPU가 100%로 일한 것이 좋다고 보면 된다.

  • Throughput (처리량)
    단위 시간당 처리량, 해당 시간 안에 CPU가 얼마나 많은 프로세스를 처리했는지

  • Response Time (응답시간)
    어떤 프로세스가 I/O가 끝나고, CPU를 쓰러 들어와서(Ready, CPU burst상태서) 최초로 CPU를 얻기까지의 시간. (중국집에서 단무지가 나올 때까지 시간)

  • Waiting Time (대기시간)
    CPU burst에서 최초 CPU를 얻기까지의 시간뿐만 아니라 기다린 시간의 총합. CPU burst에서 I/O이외의 이유로 CPU를 뺏기면 다시 queue에서 기다릴 것인데 이 시간의 총합.
    (단무지 + 짜장면 + 탕수육 기다린 시간)

  • Turnaround Time (소요시간, 반환시간)
    CPU burst상태에 들어와서 I/O작업을 하러 다시 나갈 때까지의 시간, queue에서 CPU를 기다린 시간과 CPU를 사용한 시간의 총합. (탕수육까지 다 먹고 나갈 때까지의 시간)

아무래로 빠른 것이 좋은 것이기에 시간과 관련된 밑의 3가지가 빠르면 성능이 좋다고 보면 된다.

기타 스케줄링 기법

Thread Scheduling
Thread 스케줄링은 커널이 할 수도 있고 프로세스가 할 수도 있다.

Local Scheduling
커널이 프로세스의 User level thread 존재를 모르기 때문에 관여하지 않고
프로세스가 알아서 thread library 에 의해 자신의 Thread 를 스케줄링 하는 경우를 말함.

Global Scheduling
Kernel level thread 의 경우 이미 프로세스에 몇 개의 Thread가 있는지 알기 때문에
커널의 단기 스케줄러가 직접 Thread를 스케줄링 하는 것을 말함.

스케줄링 알고리즘

I/O bound job, CPU bound job 에 CPU를 효율적으로 사용할 수 있게하는 스케줄링 알고리즘에 대해 알아본다.

FCFS (Frist Come First Served) Scheduling

Nonpreemptive 알고리즘. 은행창구와 비슷한 원리.

선착순으로 먼저 온 고객이 2시간 걸리면 뒤의 고객은 2시간 기다려야 한다.
인간에겐 공평하지만 CPU에겐 비효율적이다.

os_5_3

CPU사용시간이 24, 3, 3인 Process P1, P2, P3 간발의 차로 위처럼 도착하였다면
P2와 P3는 24초를 그대로 기다려야 한다.

이 경우 각 프로세스별 Waiting Time 평균은 17초이다.

os_5_4

만약 CPU사용량이 짧은 P2와 P3가 먼저 도착했다면 Waiting Time 평균이 3초.

FCFS 는 경우에 따라서 CPU 성능척도가 많이 달라지는데 P2, P3가 기다리는 안 좋은 경우에 발생하는 효과를 Convoy Effect(후송효과)라 한다.

SJF (Shortest Job First) Scheduling

CPU를 가장 짧게 쓰는 프로세스에게 제일 먼저 CPU를 주는 스케줄링.

SJF를 Optimal 스케줄링 이라 하는데 주어진 프로세스들에게 최적의 Waiting Time 평균을 보장하기 때문이다.

SJF는 Preemptive버전과 Nonpreemptive버전이 있다.

SJF 의 Preemptive 버전을 SRTF(Shortest Remaining Time First) 이라 부름

os_5_5

os_5_6

Preemptive 경우 현재 수행중인 프로세스의 남은 CPU사용시간(burst time)이 새로 도착한 프로세스의 CPU사용시간보다 길 경우 CPU를 뺏어서 새로운 프로세스에게 준다.

당연히 Preemptive 버전이 Nonpreemptive 버전보다 더 Optimal이다.
그렇다고 SJF가 제일 좋은 스케줄링 알고리즘은 아니다. 문제가 몇개 있다.

Starvation(굶는)현상
계속해서 queue에 Short Time프로세스가 나타나면 Long Time프로세스는 영원이 CPU를 얻지 못할 수 있다. 해결법은 Priority Scheduling에서보자.

CPU Burst Time 오차 문제
짧다고 해서 CPU줬는데 알고보니 길어서 CPU못받으면 문제다.
문제를 해결하기 위해 과거의 CPU Burst Time 과 I/O Burst Time 을 사용해 근사치 추측을 해야한다.
os_5_7

  • tn은 과거의 n번째 CPU burst 시간이 얼마였는지
  • Tn+1은 n+1번째 CPU burst 예측 값이다.
  • a는 0~1 사이값인 연산에 사용할 가중치 값이다.

os_5_8

첫 번째 수식의 tn+1에 아래 tn을 대입하고 아래 tn-1에 또 3번째 수식을 대입하고 이를 반복하면 아래 수식으로 변한다.

os_5_9

a가 1이면 바로 직전 CPU burst만 사용하여 예측하고
a가 0이면 바로 직전 CPU burst는 사용 안한다.

즉 1에 가까울수록 직전 것은 많이 반영, 뒤로 갈수록 적게 반영한다. 0에 가까우면 반대로.

Priority Scheduling

우선순위가 높은 프로세스에게 CPU를 먼저 주는 알고리즘
SJF 도 CPU busrt time을 Priority 로 사용한 Priority Scheduling 의 일종.

Priority Scheduling 도 Starvation 문제점 이 있다.

계속 높은 우선순위의 프로세스가 CPU를 기다리면 낮은 우선순위 프로세스는 평생 기다려야 한다.
해결법은 Aging이다.

Aging이란 CPU를 잡지 못하고 오래 기다리면 priority를 증가시켜주는 것이다. 일종의 경로우대라 보면 된다.

이 알고리즘도 Nonpreemptive와 Preemptive로 나뉜다.
도중에 우선순위 높은 프로세스가 오면 뻇어줌

RR (Round Robin) Scheduling

현대 시스템에 근간이 되는 알고리즘.
RR 은 Timer를 사용한 알고리즘이다.

각 프로세스는 동일한 크기의 할당시간(Time Quantum)을 가진다

일반적으로 10~100 milliseconds.

I/O bound job 은 대부분 이 시간 안에 쓰고 나가지만
CPU bound job 은 그러지 못하고 RR 스케줄링에 의해 CPU를 뺏긴다.

각 프로세스마다 할당된 시간을 q(time unit) 이라 한다면 어떤 프로세스도 $(n-1) \times q$ 이상 CPU를 기다리지 않는다.

q가 크면 FCFS 처럼 구동되고
q가 작으면 context switch 오버헤드가 커진다.

I/O bound job 프로세스가 한번에 처리해서 나갈 정도의 적당한 q 크기를 찾는것이 관건이다.

q=20 일 경우 그림

os_5_10

response time: 최초로 CPU를 얻기까지의 시간
turnaround time: 최초로 CPU를 얻어 종료까지 시간

프로세스 별로 CPU burst time 이 비슷한 상황에서

q 가 짧으면 모든 프로세스가 동시에 끝나게 되는 역효과가 발생한다.
q 가 크면 FCFS 와 별반 다를게 없어진다.

애매한 알고리즘임에도 불구하고 RR 은 I/O bound job, CPU bound job 상관없이 모두에게 공평한 스케줄링이다

작업시간에 비례해서 오래 일하는 프로세스는 많이, 짧게 일하는 프로세스는 적게 기다리기에 공평하다 보면 된다.

q에 따른 Turnaround Time 변화
os_5_11

Multilevel Queue

지금까지의 알고리즘은 하나의 Ready Queue 에 줄세우고 스케줄링 했다
Multilevel Queue 는 여러개의 Queue 에서 스케줄링하는 알고리즘이다.

일반적으로 Foreground와 Background 두 줄로 나눈다.

  • Foreground 에는 사람과 접점이 많은 I/O bound job
  • Background 에는 그렇지 않은 batch프로세스 CPU bound job

Foreground 는 RR스케줄링, Background 는 FCFS스케줄링을 적용한다.

Foreground 와 Background 의 Priority 다를수 밖에 없으며 Priority 가 높을수록 CPU 할당 받을 확률이 높다.

CPU는 하나기에 두 개 이상의 큐에서 프로세스가 동시에 돌아갈 순 없다.
각 큐에 대한 스케줄링이 필요하다.

Fixed Priority Scheduling
Foreground 의 Priority를 극단적으로 높여 Foreground Queue 가 비면 Background Queue 가 돌아가는 스케줄링.
Starvation이 발생할 확률이 매우 크다.

Time slice
Fixed Priority Scheduling 의 Starvation 을 방지하기위해 CPU time 을 적절한 비율로 각 큐에 할당한다

예로 Foreground에 80%, Background에 20%. 보통 Foreground에 더 많은 투자를 한다.

위에선 두 줄이라 했지만 사실 현대 OS 에선 Priority 에 따라 여러 개의 큐가 있는게 대부분이다.

os_6_1

Multilevel Queue 에선 프로세스가 한번 Queue 에 할당되면 종료될 때까지 다른 Queue 로는 이동할 수 없다. 따라서 Starvation이 발생해도 조치하기 힘들다.

Multilevel Feedback Queue

os_6_2

quantum은 CPU의 사용시간(RR)

Multilevel Feedback Queue 는 지금까지 사용한 CPU 시간에 따라 Queue 를 이동시킨다.
위의 큐가 우선순위가 가장 높고 아래로 갈수록 낮다.

모든 프로세스는 줄 설 때 가장 위의 큐에 줄선다.
quantum=8 안에 끝나면 큐에서 나가는 것이고 그 이상이 필요하면 우선순위가 낮은 큐로 이동한다.
quantum=16 안에도 끝나지 못한다면 우선순위가 더 낮은 큐로 이동하게 된다.

CPU는 하나기에 상위 큐가 끝나지 않으면 하위 큐는 진행되지 못한다.
지금까지 설명한 것은 Multilevel Feedback Queue 를 사용한 하나의 스케줄링 예 이다(일반적, 대표적 구현방법).

Multilevel Feedback Queue 의 스케줄링을 정의하는 파라미터는 다음과 같다.

  1. Queue 개수
  2. 각 Queue 별 스케줄링 알고리즘(RR, FCFS, SJF등)
  3. 프로세스의 Queue 할당 기준
  4. 프로세스가 첫 CPU를 받으려 할 때 어느 큐에 넣을지 기준

Multilevel Feedback Queue 는 Aging 과 같은 방식을 구성해 우선순위가 높은 큐로 프로세스를 이동시킬 수 있기 때문에 Starvation을 막을 수 있게 구현 가능하다.

Multi Processor Scheduling

CPU가 여러 개인 경우 스케줄링은 더욱 복잡하다.
다중 프로세서가 사용하는 기법을 알아보자.

Homogeneous processor Queue 에 한 줄로 세워 각 프로세서가 알아서 꺼내가는 기법.
특정 프로세서에서 실행돼야 하는 프로세스가 있는 경우 복잡해짐.

Load sharing(Load balancing) CPU 별 Queue 를 구성하거나 하나의 공동 Queue 를 구성한다.
한 CPU에 치우치지 않고 분배를 통해 부하를 공유하는 기법.
Homogeneous processor 의 경우 하나의 CPU 가 모든일을 처리할 수 있기 때문에
모든 CPU 에게 job 이 실행될수 있도록 별도의 메커니즘 필요.

Symmetric Multiprocessing(SMP) 모든CPU가 대등할 때 각 CPU들이 알아서 스케줄링을 결정.
굉장히 큰 작업이 한 CPU에 들어오면 다른 CPU는 도와주지 않아 비효율적으로 운영될 수 있다.

ASymmetric Multiprocessing 하나의 CPU가 대장 CPU가 돼서 스케줄링, 데이터 접근과 공유를 책임지고 나머지 프로세서들은 거기에 따르는 경우.

Real Time Scheduling

우리가 일반적으로 쓰는 컴퓨터는 Real time system 이 아니다.

Dead Line 이 있고 무조건 그 안에 처리돼야하는 시스템이 Real time system
데드라인이 생기면 그에 맞추기 위해 스케줄링도 복잡해 질 것이다.

Hard real time systems

Dead Line 을 어기면 큰일 나는 시스템.

프로세스가 많이 들어와서 어떤 스케줄링을 써도 Dead Line 을 넘기면 이미 큰일 난거다.
따라서 하드웨어를 그에 맞게 설정해 놓아야 한다.

이런 이유 때문에 사전에 어떤 프로세스들이 실행될지 미리 정하고(오프라인) 스케줄링 하는 경우도 있다.

Soft real time computing

Dead Line 을 넘기면 큰일까지는 나지 않는 시스템.
동영상 스트리밍 프로세스 예로 들 수 있다.

Dead Line 을 넘기면 불편하지만 문제가 되진 않는다.
Soft real time task 는 일반 프로세스에 비해 높은 우선순위를 가짐.

Algorithm Evaluation (알고리즘 평가 방법)

Queueing models
확률분포를 사용해 arrival rate 와 service rate 를 구하여 성능평가.
os_6_3

arrival rate: 단위 시간 안에 대기 행렬에 입력되는 작업 수
service rate: 처리율
둘다 클수록 좋음

Implementation(구현) & Measurement(성능측정)
오픈소스 OS(리눅스 같은) CPU 스케줄링 code 를 뜯어
새로 개발한 스케줄링 code 를 집어넣고 성능을 측정 비교.

Simulation (모의실험)
모의실험은 간단히 스케줄링 알고리즘만 프로그램 코드로 짜서 실행해보는 방법.
물론 실험 값들을 진짜 프로세스가 동작할 때와 같은 값들로 집어넣는 작업(trace작업)이 필요하다.

참고