Chapter.11 - CPU 스케줄링

모든 이미지의 저작권은 [혼자 공부하는 컴퓨터 구조 + 운영체제] 도서의 저자 강민철님에게 있습니다.

CPU 스케줄링

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

어떤 프로세스 먼저 CPU 를 사용하도록 하는 것이 좋을까?

프로세스 우선순위

입출력 작업 (입출력 버스트) 이 많은 프로세스 = 입출력 집중 프로세스

CPU 작업 (CPU 버스트) 이 많은 프로세스 = CPU 집중 프로세스

우선 순위 : 입출력 집중 프로세스 > CPU 집중 프로세스

입출력 완료까지 대기하는 시간이 많은 입출력 집중 프로세스를 먼저 처리해야 CPU 집중 프로세스가 CPU를 최대한 오래 사용할 수 있기 때문

우선 순위는 각 프로세스의 PCB 에 저장되어 있다.

스케줄링 큐

운영체제가 모든 PCB를 스캔하여 먼저 자원을 이용할 프로세스를 결정하는 것은 비효율적이기 때문에 스케줄링을 큐로 구현하고 관리한다.

운영체제가 관리하는 대표적인 큐

• 준비 큐 : CPU 를 이용하기를 기다리는 프로세스 큐
• 대기 큐 : 입출력 작업의 완료를 기다리는 프로세스 큐

선점형과 비선점형 스케줄링

선점형 스케줄링

• 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
• 일정 시간을 두고 자원을 사용하는 것도 선점형 스케줄링의 일종
• 컨텍스트 스위칭이 빈번하여 오버헤드가 발생할 수 있다.

비선점형 스케줄링

• 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식
• 컨텍스트 스위칭이 적다.

CPU 스케줄링 알고리즘

스케줄링 알고리즘은 굉장히 다양하기 때문에 각 스케줄링의 동작방식만 이해하면 된다.

* 선입 선처리 스케줄링 (FirstComeFirstServed 스케줄링)

준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식

이 때, 실행시간 보다 대기시간 이 더 긴 것을 호위 효과라고 한다.

* 최단 작업 우선 스케줄링 (Shortest Job First 스케줄링)

준비 큐에 삽입된 프로세스 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 비선점형 스케줄링 방식

스케줄링에서의 큐는 반드시 선입선출일 필요는 없다.

* 라운드 로빈 스케줄링

정해진 타임 슬라이스 만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

타임 슬라이스가 지나치게 크면 호위 효과가 생길 수 있고, 타임 슬라이스가 지나치게 작으면 컨텍스트 스위칭이 번번해진다.

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

최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합친 방식

* 우선순위 스케줄링

가장 높은 우선순위를 가진 프로세스부터 처리하는 스케줄링 알고리즘

단, 우선순위가 같은 프로세스는 선입 선처리 방식으로 처리한다.

기아 현상 : 우선순위가 높은 프로세스들에 의해 우선순위가 낮은 프로세스가 계속해서 처리되지 못하는 현상

에이징 : 기아 현상을 방지하기 위해 프로세스의 우선순위를 점차 증가시키는 방법

* 다단계 큐 스케줄링

우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

큐마다 다른 타임 슬라이스 와 스케줄링 알고리즘을 적용할 수 있다.

프로세스가 큐 사이를 이동할 수 없어서 기아 현상이 발생할 수 있다.

* 다단계 피드백 큐 스케줄링

프로세스가 큐 사이를 이동할 수 있는 스케줄링 방식

기아 현상을 방지하는 에이징 기법이 적용되어 있어 구현이 복잡하지만 가장 일반적인 CPU 스케줄링 알고리즘