[운영체제] 4. CPU 스케줄링

본 글은 '이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접' 책을 읽고 정리한 글입니다.

 

 

한정적인 CPU 자원 내에서 모든 프로세스를 공평하게 실행하는 것은 OS의 주요 목적이다. 

 

스케줄링의 목적 

멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행하기 위해 스케줄링 기법을 활용한다. schedule이라는 의미에 맞게, 어떠한 작업의 순서를 계획한다고 생각하면 된다. 스케줄링은 세부적으로 다음 5가지의 목적이 있다. 

 

• 공평성 : 특정 프로세스가 실행되지 않는 경우가 없어야 한다. 
• 효율성 : 자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없어야 한다. 
• 안정성 : 높은 우선순위의 프로세스를 먼저 처리한다. 
• 반응 시간 보장 : 프로세스가 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으로 보기 때문에, 일정 시간 내에 응답할 수 있도록 해야 한다. 
• 무한 연기 방지 : 특정 프로세스에 대한 처리가 무한히 연기되지 않아야 한다. 

 

✔️ CPU 스케줄링 

운영체제는 프로세스와 스레드에 CPU를 할당함으로써 CPU 자원을 관리한다. 여기서 운영체제가 CPU를 배분하는 방법이 CPU 스케줄링이다. 

 

운영체제는 프로세스 별 우선순위를 판단 후 높은 프로세스에 CPU의 자원을 더 빨리, 많이 할당한다. 그럼 운영체제는 프로세스의 우선순위를 어떻게 정할까?? 

 

프로세스 우선순위

가장 대표적인 고려 요소는 CPU 활용률이다. 운영체제는 CPU 활용률을 유지하기 위해 기본적으로 입출력 작업이 많은 프로세스의 우선순위를 높게 유지한다. 이외에 아래의 기준이 있다. 

• CPU 활용률 : 전체 CPU의 가동 시간 중 작업을 처리하는 시간의 비율
• 처리량 : 단위 시간 당 실행한 프로세스 수 (처리를 얼마나 했는가?)
• 응답 시간 : 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간 
• 반환 시간 : 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간 
• 대기 시간 : 프로세스가 대기 큐에서 대기하는 시간의 총합 

 

 

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용해 실행과 대기 상태를 오가며 실행된다. 예를 들어, 이미지를 다운로드하는 I/O 작업과 받은 이미지를 렌더링하는 CPU 작업처럼 말이다. 

이때 프로세스가 CPU를 이용하는 작업을 CPU 버스트라 하고, 입출력장치를 기다리는 작업을 입출력 버스트라고 한다. 

 

CPU 버스트 시간이 더 긴 프로세스를 CPU 집중 프로세스, 입출력 버스트 시간이 더 긴 프로세스를 입출력 집중 프로세스라고 한다. 

CPU 집중 프로세스(위), 입출력 집중 프로세스(아래)

위 그림을 보면 CPU 버스트가 짧은 프로세스가 대기 상태가 더 많은 것을 확인할 수 있다. 계속 언급했듯이 CPU 자원을 효율적으로 사용하기 위해서는 CPU가 대기하는 시간이 길면 안된다. 따라서 위 두 가지 종류의 프로세스가 동시에 CPU 자원을 요구한다면, 입출력 집중 프로세스를 먼저 실행시켜서 I/O 상태로 보내놓은 후, 그 시간 동안 CPU 집중 프로세스에 CPU를 할당하는 것이 좋을 것이다. 

 

이런 이유로 입출력 집중 프로세스가 일반적으로 CPU 집중 프로세스보다 우선순위가 높다. 이처럼 CPU를 효율적으로 배분하기 위해 운영체제는 프로세스마다 우선순위를 부여하여 CPU를 할당한다. 

 

스케줄링 큐 

자원을 이용하기 위해 프로세스들은 대기를 해야하는데, 스케줄링 큐에 프로세스의 PCB를 넣어 줄을 세운다. 

 

준비 큐 

CPU를 배정받기 위해 기다리는 프로세스들이 모인 큐로, 실행이 가능한 상태이다. 

 

대기 큐

입출력 등의 외부 작업이 끝나기를 기다리는 프로세스들이 모인 큐로, 실행이 불가능한 상태이다. 

 

 

✔️ 스케줄링 알고리즘 

스케줄링은 기본적으로 프로세스의 실행이 끝나면 이루어지지만, 실행 도중 스케줄링이 수행되는 2가지 경우가 있다.

1) 실행 중 입출력 작업을 위해 대기 상태로 전환될 때

2) 실행 중 타이머 인터럽트가 발생해 준비 상태로 전환될 때 

 

이런 상황은 사용 중인 CPU를 다른 프로세스가 빼앗아갈 수 있다고 해서 선점형 스케줄링이라고 한다. 반대로 비선점형 스케줄링은 일단 한 번 실행을 시작하면 종료될 때까지 다른 프로세스가 끼어들 수 없다. 

 

비선점형 스케줄링 

비선점형 스케줄링은 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미한다. 비선점형 스케줄링은 선점형 스케줄링보다 문맥 교환의 횟수가 적어 상대적으로 오버헤드의 발생이 적다는 장점이 있다. 그 종류로는 FCFS, SJF가 있다. 

 

1. FCFS (First Come First Served) 

FCFS(선입 선처리) 스케줄링은 준비 큐에 삽입된 순서대로 먼저 CPU를 할당하는 방식이다. 앞의 프로세스가 종료되어야 다음 프로세스를 실행할 수 있기 때문에 기다리는 시간이 매우 길어질 수 있다는 단점이 있다. 이런 경우 나중에 삽입된 프로세스의 실행이 지연되는 문제를 호위 효과라고 한다. 

 

2. SJF (Shortest Job First) 

SJF(최단 작업 우선) 스케줄링은 준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간이 가장 짧은 프로세스부터 실행하는 방식이다. 

 

3. 우선순위 (Priority) 스케줄링

우선순위 스케줄링은 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 방식이다. 이 방식은 우선순위가 낮은 프로세스는 계속해서 실행이 연기되는 기아 상태가 될 수 있다. 이를 방지하기 위해 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식을 사용하는데, 이걸 에이징이라고 한다. 

 

선점형 스케줄링

선점형 스케줄링은 스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있음을 의미한다. 한 프로세스의 CPU 독점을 막고 여러 프로세스에 골고루 CPU 자원을 배분할 수 있다는 장점이 있지만, 문맥 교환 과정에서 오버헤드가 발생할 수 있다. 

1. RR (Round Robin)

라운드 로빈 스케줄링은 프로세스 간 우선순위가 따로 없고, 모든 프로세스를 순서대로 일정 시간 동안 실행하며 일정 시간이 초과하면 다른 프로세스를 실행하는 방식이다. 이때 일정 시간을 타임 슬라이스라고 한다. 프로세스가 일정 시간을 모두 사용해도 완료하지 못하면 다시 큐의 맨 뒤에 삽입된다. 

 

2. SRT (Shortest Remaining Time)

SRT(최소 잔여 시간 우선) 스케줄링은 준비 큐에서 남은 실행 시간이 가장 짧게 남은 프로세스를 우선 수행하는 방식이다. 즉, 새로운 프로세스가 준비 큐에 들어왔을 때 현재 실행 중인 프로세스의 남은 실행 시간과 새로운 프로세스의 실행 시간을 비교하여 더 짧은 것을 선택한다. 

 

3. 다단계 큐 (Multilevel Queue) 스케줄링

다단계(멀티 레벨) 큐 스케줄링은 준비 큐를 목적에 따라 여러 개로 분리해 사용하는 방식이다. 분리한 큐는 각각의 우선순위가 있고, 각자 다른 스케줄링 알고리즘을 적용할 수 있다. 우선순위가 가장 높은 큐에 있는 프로세스부터 처리한다. 

프로세스들이 큐 사이를 이동할 수 없어서 우선순위가 낮은 프로세스의 작업이 계속해서 연기될 수 있다. 이를 보완한 것이 다단계 피드백 큐 스케줄링이다. 

 

4. 다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링 방식에서 프로세스들이 큐 사이를 이동할 수 있게 된 방식이다. 새롭게 진입하는 프로세스는 우선순위가 가장 높은 큐에 삽입되고, 타임 슬라이스 동안 실행된다. 해당 큐에서 실행이 끝나지 않으면 다음 우선순위 큐로 삽입되어 실행된다. CPU를 오래 사용해야 하는 프로세스는 우선순위가 점차 낮아지게 되고 이로 인해 발생하는 기아 상태를 방지하기 위해 낮은 우선순위 큐에서 오래 기다리고 있는 프로세스들은 높은 우선순위 큐로 이동시키는 에이징 기법을 적용할 수 있다.