📢 본 글은 혼공학습단 미션과 함께 정리해보는 글 입니다.
CPU 스케줄링 개요
CPU 스케줄링은 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 뜻한다.
컴퓨터 전체 성능과 직결되기도 하는 요소이다. 프로세스들에게 CPU를 제대로 분배하지 못한다면 반드시 실행되어야 할 프로세스가 실행이 되지 않거나, 급하지 않은 프로세스들만 계속 실행되는 무질서 상태가 반복될 수도 있다.
프로세스 우선순위
어떻게 해야 가장 공정하게 CPU 스케줄링을 할 수 있을까?
차례대로의 방식
단순히 생각해보면 CPU를 사용하고 싶어하는 프로세스들이 차례로 돌아가면 될 것이다.
⇒ 그러나 이 방식은 좋은 방식이 아니다. 빨리 처리해야 하는 프로세스, 즉 프로세스마다 우선순위가 다르기 때문이다. 우선순위는 사용자가 설정할 수도 있고, 운영체제가 내부적으로 정할 수도 있다.
단적인 예로, 입출력 작업이 많은 프로세스 (= I/O bound process, 입출력 집중 프로세스)의 우선순위는 CPU 작업이 많은 프로세스 (= CPU bound process, CPU 집중 프로세스)의 우선순위보다 높다.
입출력 집중 프로세스는 CPU를 사용하는 시간이 짧고, CPU를 사용하고 나면 대기 상태에 접어들기 때문에 CPU 입장에서는 이 프로세스를 먼저 진행시켜 주는 것이 효율적이다. 따라서
입출력 집중 프로세스의 우선순위가 CPU 집중 프로세스의 우선순위보다 높다!
우선순위에 따른 방식
- 프로세스의 우선순위는 프로세스의
PCB (Process Control Block, 프로세스 제어 블록)에 저장된다. 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 운영체제가 부여하는 것이 우선순위이다.- 운영체제는
PCB를 기반으로 어떤 프로세스가 CPU를 얼마나 사용하게 될 것인지 등을 결정한다. - 프로세스 우선순위는 간단한 명령어, 프로그램 등으로 확인이 가능하다. 일부 우선순위의 경우에는 사용자가 직접 설정 가능하다.
스케줄링 큐
운영체제는 PCB를 기반으로 어떤 프로세스가 CPU를 얼마나 사용하게 될 것인지 등을 결정한다고 하였다. 그러나 프로세스가 여러 개일 경우, 다음 CPU 자원을 이용할 프로세스를 선택하기 위해 매번 모든 프로세스들의 PCB를 다 뒤져보는 것은 비효율적일 것이다. 메모리, 입출력 장치를 사용하고자 하는 프로세스를 선택할 때도 비슷한 상황을 겪을 것이다.
때문에 운영체제는 스케줄링 큐를 활용한다. 스케줄링 큐는 어떤 자원을 이용하고자 하는 프로세스들이 서는 줄이다.
이때, 스케줄링에서의 큐는 반드시 선입선출 (FIFO, First-In-First-Out) 방식일 필요는 없다.
준비 큐와 대기 큐
준비 큐와 대기 큐는 가장 대표적인 스케줄링 큐의 종류이다.
준비 큐 (ready queue)는 CPU를 이용하고자 하는 프로세스들이 서는 줄, 대기 큐 (wait queue)는 입출력 장치를 이용하고자 하는 프로세스들이 서는 줄을 뜻한다.
더 얘기하자면, 준비 큐는 언제든지 CPU를 할당 받아 실행할 수 있지만, 아직 자신의 상태가 되지 않아 기다리고 있는 프로세스들의 줄이라고 할 수 있고, 대기 큐는 입출력 작업을 해야 할 게 있어서 지금 당장 CPU를 쓸 필요가 없어 대기하고 있는 프로세스들의 줄이다.
과정 예시
- 동시에 실행 중인 프로세스가 여러 개 있다고 가정한다.
- CPU 자원은 한정되어 있기 때문에 프로세스들끼리 CPU를 돌아가면서 사용한다.
- 각 프로세스들은 준비 상태에 접어들어 CPU의 할당을 기다리게 된다.
- 준비 상태에 접어든 프로세스가 자신의 차례가 되면 CPU를 할당 받아 실행하게 된다.
- 자신의 실행 상태가 끝나면 타이머 인터럽트를 호출하고, 다시 준비 큐에 들어가게 된다.
- 입출력 작업을 해야 될 때가 되면 이 때는 CPU를 쓸 필요가 없기 때문에 대기 큐에 들어가서 대기 상태에 들어가게 된다.
- 자신의 입출력 작업이 끝나면 입출력 완료 인터럽트를 호출한다.
- 다시 CPU의 할당을 기다리기 위해 준비 큐로 넘어간다.
대기 큐는 여러 개가 있다. 이 대기 큐는 보통 입출력 장치 별로 있는 경우가 많다. 즉, 같은 장치를 요구한 프로세스들은 같은 큐에서 대기하게 된다.
예를 들어 프린터를 두 개의 프로세스가 동시에 요청할 수도 있고, 하드 디스크를 세 개의 프로세스가 동시에 요청할 수도 있다. 이럴 때 각각의 자원 별로, 각각의 입출력 장치 별로 큐를 따로 만들어두면 같은 장치를 요구한 프로세스들은 같은 큐에서 대기를 할 수 있게 된다.
입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB의 상태를 대기 상태에서 준비 상태로 변경한 다음 대기 큐에서 제거하고 준비 큐로 넣어주게 된다.
선점형/비선점형
선점형/비선점형에 대한 개념은 운영체제에서의 커널을 공부할 때 중요한 내용이다.
선점형 스케줄링
선점형 스케줄링 (preemptive scheduling): 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 요청한 프로세스에 할당한다.
- 어느 한 프로세스의 자원 독점을 막고
프로세스에 골고루 자원을 배분할 수 있다. - 그만큼
문맥 교환 (context switching) 과정에서 오버헤드가 발생할 수 있다.
비선점형 스케줄링
비선점형 스케줄링 (non-preemptive scheduling): 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때 까지 기다린다.
- 선점형 스케줄링에 비해
문맥 교환에서 발생하는 오버헤드가 적다. - 모든 프로세스가
골고루 자원을 이용하기 어렵다.
CPU 스케줄링 알고리즘
이번 내용에서는 운영체제가 CPU 자원을 배분하는 7가지의 CPU 스케줄링 알고리즘에 대해 학습하게 된다.
중요한 것은 용어가 아니라 각 스케줄링 알고리즘에서 사용된 알고리즘이다. 각 스케줄링 알고리즘들의 작동 방식과 장단점을 이해하는 데에만 집중하도록 하자.
스케줄링 알고리즘의 종류
선입 선처리 스케줄링
FCFS (First Come First Served)스케줄링준비 큐에 삽입된 순서대로 처리하는비선점 스케줄링방식먼저 CPU를 요청한 프로세스부터 CPU를 할당한다.- 이로 인해
프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있다. (convoy effect, 호위 효과)
최단 작업 우선 스케줄링
SJF (Shortest Job First)스케줄링사용 시간이 긴 프로세스를 나중에 실행하고, 시간이 짧은 프로세스를 먼저 실행함으로써 평균 대기 시간을 줄일 수 있다.- 선점형/비선점형 방식으로 구현될 수 있다.
기본적으로는 비선점형방식으로 된다.
라운드 로빈 스케줄링
RR (Round Robin)스케줄링선입 선처리 스케줄링과타임 슬라이스 (time slice)가 결합된 형태이다.- 타임 슬라이스: 각 프로세스가
CPU를 사용할 수 있는 정해진 시간
- 타임 슬라이스: 각 프로세스가
정해진 타임 슬라이스 만큼의 시간 동안 돌아가며 CPU를 이용하는선점형 스케줄링이다.- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되
정해진 시간만큼 이용한다. 정해진 시간을 모두 사용했음에도 아직 프로세스가 완료되지 않았다면, 다시 큐의 맨 뒤에 삽입한다. (context switching- 문맥 교환)- 타임 슬라이스의 크기가 지나치게 클 경우 사실상 선입 선처리 스케줄링과 다를 바 없어
호위 효과 (convoy effect)가 생길 여지가 있다. - 타임 슬라이스의 크기가 지나치게 작을 경우에는 문맥 교환 (context switching)에 발생하는 비용이 커
CPU는 프로세스를 처리하는 일 보다 프로세스를 전환하는 데 힘을 더 쓰게 될 수 있다.
- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되
최소 잔여 시간 우선 스케줄링
SRT (Shortest Remaining Time)스케줄링최단 작업 우선 스케줄링과라운드 로빈 스케줄링이 결합된 형태이다.정해진 시간만큼 CPU를 이용하되,다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택한다.
우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고,
우선순위가 높은 프로세스부터 실행된다. 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링된다.최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링은 좀 더 넓은 의미에서 우선순위 스케줄링에 속한다고 할 수 있다.
기아 (starvation) 현상
- 우선순위 스케줄링의
근본적인 문제점이다. 우선순위가 높은 스케줄링만 계속 실행될 수 있다.- 때문에
우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었다 하더라도실행이 계속해서 연기된다.
에이징 (aging)
- 기아 현상을 방지하기 위한 방법이다.
- 오랫동안 대기한
프로세스의 우선순위를 점차 높인다. - 이를 통해,
처음에 우선순위가 낮아도 언젠가는 우선순위가 높아져 기아 현상을 막을 수 있다.
다단계 큐 스케줄링
Multilevel queue스케줄링- 우선순위 스케줄링의 발전된 형태이다.
우선순위 별로 준비 큐를 여러 개 사용한다.우선순위가 높은 큐에 있는 프로세스를 먼저 실행한다.우선순위가 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스를 처리한다.프로세스 유형별로 우선순위를 구별하는 것이 쉬워진다.큐별로 타임 슬라이스를 여러 개 지정할 수도 있고,큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.- 기본적으로
큐 간 이동이 불가능하기 때문에우선순위가 낮은 프로세스는 계속해서 우선순위가 낮을 수 밖에 없고, 그로 인해기아 현상을 겪을 수 있다.
다단계 피드백 큐 스케줄링
Multilevel feedback queue스케줄링- 다단계 큐 스케줄링의 발전된 형태이다.
큐 간의 이동이 가능하다.새로 준비 상태로 된 프로세스가 있으면 가장 우선순위가 높은 큐에 삽입한다.일정 시간 (타임 슬라이스) 만큼 CPU를 사용할 수 있도록 한다.- 만약 작업이 끝나지 않았다면 그 때 우선순위가 다음으로 높은 곳에 삽입`을 한다.
- 작업이 많이 있는 프로세스일수록 우선순위가 점점 낮아진다.`
- 따라서
CPU 집중 프로세스는상대적으로 우선순위가 낮아지고, 입출력 집중 프로세스는 높아진다.
- 따라서
- 일정 시간 이상 낮은 우선순위에서 기다리고 있던 프로세스가 있었다면 이 프로세스의 우선순위를 점차 높임으로써 (에이징) 기아 현상을 예방할 수 있다. 이것이 가능한 이유는 큐 간의 이동이 가능하기 때문이다.
- 정리하자면 다단계 피드백 큐 스케줄링은
CPU 사용 시간이 길면 우선순위가 점점 낮아지고, 동시에 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높일 수 있다. - 다단계 피드백 큐 스케줄링은 복잡하지만,
CPU 스케줄링의 가장 일반적인 형태로 알려져 있다.
미션
- 준비 큐에 A, B, C, D 순으로 삽입되었다고 가정했을 때, 선입 선처리 스케줄링 알고리즘을 적용하면 어떤 프로세스 순서대로 CPU를 할당받는가?
⇒선입 선처리 스케줄링은준비 큐에 삽입된 순서대로 처리하는비선점 스케줄링 방식이다. 따라서A - B - C - D순서대로 CPU를 할당받게 된다.
부족하거나 보완할 점이 있다면 댓글 부탁드립니다 😃
