Cha-Ji

[공룡책] CPU 스케줄링

July 03, 2022

운영체제는 CPU를 프로세스 간 교환함으로써 보다 생산적으로 동작합니다.

코어가 하나인 시스템에선 한순간에 오직 하나의 프로세스만이 실행될 수 있습니다.

나머지 프로세스는 CPU의 코어가 가용 상태가 되어야 실행시킬 수 있으며

다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행중인 프로세스를 가지게 하는 데 있습니다.

이 때 프로세스 또는 스레드 바쁘게 사용하기 위한 스케줄링에 대해 알아보겠습니다.

스케줄링

그냥 선착순으로 실행하고 끝내면 공평할텐데 왜 스케줄링 알고리즘이 필요할까요?

은행에 사람이 7명 줄을 섭니다.

맨 앞사람은 3시간짜리 업무를 보러 왔습니다. 그 뒤에 6사람은 모두 5분이 걸립니다.

6사람은 다들 3시간 이상의 대기시간을 갖습니다. 총 대기시간은 20시간 정도 되네요.

사람” 걸리는 시간” 대기 시간”
가 3시간 0분
나 5분 3시간
다 5분 3시간 5분
라 5분 3시간 10분
마 5분 3시간 15분
바 5분 3시간 20분
사 5분 3시간 25분

물론 먼저온 사람이 먼저 업무를 보는것이 공평하지만

프로세스에게 공평함이 필요할까요? 총 대기시간만 적으면 될 것 같은데..

오래 걸리는 사람이 제일 늦게 업무를 본다면 어떨까요? 대기시간은 2시간조차 되지 않네요.

사람” 걸리는 시간” 대기 시간”
나 5분 0분
다 5분 5분
라 5분 10분
마 5분 15분
바 5분 20분
사 5분 25분
가 3시간 30분

이처럼, 큰 프로그램이 메모리를 점거해 전체적인 성능 저하를 불러일으키는 것 때문에
스케줄링 알고리즘이 필요합니다.

스케줄링에는 크게 선점 스케줄링과 비선점 스케줄링이 있습니다.

선점 스케줄링은 스케줄링이 발생할 때 기존 실행중인 프로세스를 선점하는 기법입니다.

데드락을 방지할 필요가 있는 기법입니다.

  • new process → running
  • running process → waiting

비선점 스케줄링은 context switching 전에 실행이 완료되고 프로세스가 봉쇄되기를 기다립니다.

  • running process ~~~ running

스케줄링 기법

선입선처리 스케줄링(FCFS)

First-Come First-Served

비선점형 기법입니다.

먼저 실행된 프로세스부터 처리하며 CPU 버스트가 완료될 때까지 CPU를 반환하지 않습니다.

단점으로는 긴 프로세스가 CPU를 양도하길 기다리는 호위 효과가 발생합니다.

최단작업우선 스케줄링(SJF)

Shortest-Job-First

평균 대기시간이 최소인 스케줄링 기법입니다.

이상적이지만 문제점이 있습니다. 실제로 실행되지도 않은 CPU 버스트의 길이를 예언하는건 불가능합니다.

때문에 이전 버스트의 길이와 비슷하다고 기대하고 예측하여 사용합니다.

단점으로는 긴 프로세스는 평생 실행시킬 수 없는 효과가 발생합니다.

라운드 로빈 스케줄링(RR)

Round-Robin

FCFS에서 선점이 추가된 방식입니다.

각 프로세스는 동일한 크기의 할당 시간을 갖게됩니다.

할당시간이 끝나면 선점당하며 준비 큐의 맨 뒤로 가게됩니다.

할당 시간이 너무 크면 FCFS와 같아져서 문제가 되지만 문맥 교환 시간에 비해서는 커야합니다.

우선순위 스케줄링

Priority

우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링입니다.

선점과 비선점 모두 가능합니다.

선점형에서는 더 높은 우선순위의 프로세스가 도착하면 선점하며,

비선점형에서는 준비 큐의 head에 넣게 됩니다.

단점으로는 실행준비는 되어있지만 CPU를 사용할 수 없는 프로세스를 CPU가 무한히 대기하는 상태가 존재합니다.

하지만 해결책으로 대기시간에 따라 우선순위를 보정하는 aging이 존재합니다.

References

Written by@Cha-Ji
Android developer

InstagramGitHub