[운영체제] CPU 스케줄링

프로세스 우선순위와 스케줄링 큐

운영체제가 프로세스(및 스레드)에 어떻게 자원을 할당할까?

운영체제가 자원(CPU, 디스크,..)을 공정하고 합리적으로 배분하는 방법이 스케줄링 이다. 

 

CPU 자원은 한정되어 있고 실행 중인 프로세스는 여러 개인데, 어떻게 나눠서 사용할 수 있을까?

정해진 시간 동안 돌아가면서 CPU를 사용하는 것이 좋을까? -> NO, 프로세스마다 우선순위가 다르다. 우선순위는 PCB에 명시되어 있다. 

 

그렇다면 우선순위의 차이를 보이는 프로세스 유형은 무엇이 있을까? 

I/O bound process, CPU bound process 로 예시를 들 수 있다. I/O bound process가 CPU bound process 보다 우선순위가 높다. 

 I/O bound process는 I/O 작업이 많은 프로세스, CPU bound process는 CPU 작업이 많은 프로세스(ex. 컴파일러)이다.

보통 I/O 작업은 CPU 작업보다 훨씬 느리기 때문에, 우선순위를 높게 잡아서 먼저 작업하도록 하는 것이다. 

 

그리고 프로세스 마다 필요로 하는 자원이 다를 수 있다. (누구는 CPU, 누구는 메모리, 누구는 하드디스크,.. )

폭주하는 프로세스들

이 때, 프로세스들의 요구사항을 효율적으로 관리하기 위해 스케줄링 큐 를 사용한다. 

 

스케줄링 큐

스케줄링 큐

자료구조에서 큐는 FIFO 방식이지만, 프로세스에는 '우선순위'가 있기 때문에 FIFO 방식으로 스케줄링 되지는 않는다 !

 

대표적인 스케줄링 큐

• 준비 큐: CPU 이용을 기다리는 프로세스들의 큐
• 대기 큐: 대기 상태 프로세스들의 큐 (입출력 요청)

스케줄링 큐

입출력을 기다리는 대기 큐들

스케줄링 큐까지 반영한 프로세스 상태 다이어그램

 

 

만약 한 프로세스 실행 도중 다른 급한 프로세스가 실행되어야 한다면 어떻게 할까?

새치기하려는 급한 프로세스

1. 현재 실행 중인 프로세스의 자원을 빼앗아 해당 프로세스에게 할당 -> 선점형 스케줄링 (타임아웃 기반 문맥 교환) 
   1. 프로세스에 자원을 고루 할당 가능
   2. 문맥 교환 과정의 오버헤드
2. 현재 실행 중인 프로세스 실행이 끝날 때까지 해당 프로세스 대기 -> 비선점형 스케줄링
   1. 고르지 않은 자원 분배
   2. 문맥 교환 과정에서의 오버헤드 적음

CPU 스케줄링 알고리즘

전공서 기준 CPU 스케줄링 알고리즘
1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

-> 운영체제마다 스케줄링 방식이 다르다. 

 

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

• CPU를 먼저 요청한 프로세스부터 CPU 할당
• 준비 큐에 삽입된 순서대로 실행되는 비선점형 스케줄링
• 부작용: 호위 효과 (convoy effect)
  • 호위 효과: 만약 앞에 있는 프로세스 실행시간이 길다면, 짧은 실행시간인 프로세스가 그만큼 오래 기다려야 한다.

FIFO 스케줄링

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

• 준비 큐 프로세스 중 CPU 이용 시간이 짧은 프로세스부터 실행
• 호위효과 방지

SJF 스케줄링

 

라운드 로빈 스케줄링

• 선입 선처리 스케줄링 + 타임 슬라이스(정해진 시간만큼만 실행)
• 준비 큐에 삽입된 순서로 실행하되, 타임 슬라이스만큼 실행
• 선점형 스케줄링

RR 스케줄링

 

최소 잔여 시간 우선 스케줄링 (SRT 스케줄링)

• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 작업 시간 짧은 프로세스부터 처리하되, 타임 슬라이스만큼 돌아가며

우선순위 스케줄링

• 프로세스마다 우선순위 부여, 우선순위 높은 순으로 스케줄링
  • 최단 작업 우선 스케줄링 – 작업 시간 짧은 순으로 우선순위 부여
  • 최소 잔여 시간 스케줄링 – 남은 시간 짧은 순으로 우선순위 부여
• 위에서 언급된 스케줄링도 결국 우선순위 스케줄링으로 볼 수 있기 때문에, 굉장히 범용적인 스케줄링으로 볼 수 있다.
• 아사(starvation) 현상
  • 모든 우선순위 스케줄링 알고리즘의 근본적인 문제
  • 우선순위 낮은 프로세스의 실행이 계속 연기되는 현상
  • 우선순위 높은 프로세스 실행하느라 우선순위 낮은 프로세스 실행을 못한다.
  • 해결책: 에이징(aging) -> 대기 시간이 길어지면 점차 우선순위를 높이는 방식

다단계 큐 스케줄링

• 우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링
  • 우선순위가 높은 프로세스 처리
  • 다음으로 우선순위 높은 프로세스 처리
  • 다음으로 우선순위 높은 프로세스 처리
• 프로세스 유형 별로 큐 구분 가능
  e.g.) CPU 바운드, I/O 바운드, 백그라운드, 포그라운드, 실시간 프로세스 ...
• 큐 별로 다른 스케줄링 알고리즘 적용 가능
  e.g.) 선입 선처리 큐, 라운드 로빈 큐, ...
• 큐 별로 다른 타임 슬라이스 적용 가능
• 기본적으로 프로세스는 큐 간의 이동 불가능
  • 한 번 큐에 적재되면 이동이 불가능하기 때문에 우선순위 낮은 큐에 배정되면 아사 현상 발생할 수 있다.
  • 해결: 다단계 피드백 큐 스케줄링

다단계 큐 스케줄링

 

다단계 피드백 큐 스케줄링

• 프로세스가 큐 간의 이동 가능
• 최초에는 높은 우선순위 큐에 삽입, 실행이 끝나지 않을 경우 낮은 우선순위 큐에 삽입
• 에이징 적용 (너무 오래 기다렸으면 다시 우선순위를 높인다. )
• CPU bound, I/O bound 프로세스 구분 가능

다단계 피드백 큐 스케줄링