[운영체제] CPU 스케줄링

JSCODE 모의면접 스터디
운영체제 6기 3주차

목차

 

1. CPU 스케줄링

CPU 스케줄링은 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 말한다.

운영체제는 준비큐에 있는 프로세스들 중 어떤 프로세스에 CPU를 할당할지 결정한다.

 

프로세스의 특성와 우선순위

• 입출력 집중 프로세스 (I/O Bound Process): 입출력 작업이 많은 프로세스로 대기 상태에 더 많이 머무름.
• CPU 집중 프로세스(CPU Bound Process): 계산 위주의 CPU 작업이 많은 프로세스로 실행 상태에 더 많이 머무름.

두 프로세스가 동시에 CPU 자원을 요구한 경우

입출력 집중 프로세스를 먼저 실행하여 입출력장치를 지속적으로 활용하고, 그 다음 CPU 집중 프로세스에 CPU를 집중적으로 할당하는 것이 더 효율적이다.

=> 운영체제는 프로세스마다 우선순위를 부여하고, 각 프로세스의 PCB에 이를 명시하여 관리한다.

 

스케줄링 큐

운영체제는 프로세스들을 효율적으로 관리하기 위해 스케줄링 큐를 사용한다.

• 준비 큐(Ready Queue): CPU 할당을 기다리는 프로세스들의 대기열
• 대기 큐(Waiting Queue): 입출력장치를 사용을 기다리는 프로세스들의 대기열

 

CPU 스케줄링 목적

CPU 스케줄링의 목적은 CPU 이용률을 최대화하고, 처리량을 증가시키며, 대기 시간과 응답 시간을 최소화하는 것이다.

=> 각 프로세스의 특성에 맞는 효율적인 자원 분배를 할 수 있다.

 

2. CPU 스케줄링 방식

CPU 스케줄링은 CPU를 강제로 회수할 수 있는지에 따라 선점형 스케줄링과 비선점형 스케줄링으로 나뉜다.

선점형 스케줄링

프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식이다.어느 하나의 프로세스가 자원 사용을 독점할 수 없다.

 

ex) 프로세스마다 정해진 시간만큼 CPU를 사용하고, 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식 -> 라운드 로빈 스케줄링

 

장점

• 한 프로세스가 CPU를 독점하는 것을 방지
• 자원을 골고루 배분 가능
• 우선순위가 높은 프로세스의 빠른 처리 가능

 

단점

• 잦은 문맥 교환으로 오버헤드 발생
• 시스템 부하 증가

 

해당 CPU 스케줄링 알고리즘

• 최소 잔류 시간 우선 스케줄링 (SRTF)
• 라운드 로빈 스케줄링 (Round Robin)
• 우선순위 스케줄링의 선점형 방식

 

 

비선점형 스케줄링

하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태로 전환되기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식이다. 하나의 프로세스가 자원 사용을 독점할 수 있다.

 

장점

• 프로세스 간 문맥 교환이 적음 (오버헤드 감소)
• 실행 시간 에측이 용이함

 

단점

• 자원을 골고루 배분할 수 없음 (자원을 독점)
• 긴급한 작업 처리가 어려움

 

해당 CPU 스케줄링 알고리즘

• 선입선출 스케줄링 (FCFS)
• 최단 작업 우선 스케줄링 (SJF)
• 우선순위 스케줄링의 비선점형 방식

 

3. CPU 스케줄링 알고리즘

선입선출 스케줄링 (FCFS, First Come First Scheduling)

준비 큐에 삽입된 순서대로 프로세스에 CPU를 할당하는 비선점형 스케줄링 방식이다.

CPU를 할당받은 프로세스는 작업이 완료되거나 입출력 처리를 요구하여 CPU를 방출할 때까지 CPU를 점유한다.

 

단점

• 호위 효과(convoy effect) 발생: CPU 사용 시간이 긴 프로세스에 의해 CPU 사용 시간이 짧은 프로세스들이 오래 대기하는 현상
• 대화형 시스템에 부적합

 

 

최단 작업 우선 스케줄링 (SJF, Shortest Job First Scheduling )

준비 큐에 삽입된 프로세스들 중 CPU 이용 시간이 가장 짧은 프로세스부터 CPU를 할당하는 스케줄링 방식이다.

CPU 사용 시간이 짧은 프로세스를 먼저 실행하여 준비 큐의 프로세스들에 대해 최소의 평균 대기 시간을 가지며, 이는 호위 효과를 방지할 수 있다.

 

기본적으로 비선점형이지만, 선점형으로 구현 시 최소 잔류 우선 스케줄링(SRTF)이 된다.

 

단점

• CPU 사용 시간이 긴 프로세스의 기아 현상 발생 가능
• 프로세스의 실행 시간 예측이 어려움

 

 

라운드 로빈 스케줄링 (RR, Round Robin Scheduling)

각 프로세스가 정해진 시간인 타임 슬라이스(시간 할당량)만큼 CPU를 순차적으로 할당받는 선점형 스케줄링 방식이다.

준비 큐에 있는 프로세스들은 삽입된 순서대로 정해진 시간만큼 CPU를 할당받고, 할당된 시간을 모두 사용하면 다시 큐의 맨 뒤에 삽입된다.

 

장점

응답 시간이 빠르고, CPU 독점을 방지하여 공평한 CPU 할당이 가능하다.

 

타임 슬라이스

각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. Time Quantum(시간 할당량)이라고도 한다.

• 너무 큰 경우: 선입선출 스케줄링과 같이 호위 효과 발생 가능
• 너무 작은 경우: 잦은 문맥 교환으로 오버헤드 증가

 

 

최소 잔류 시간 우선 스케줄링 (SRTF, Shortest Remaining Time First)

최단 작업 우선 스케줄링(SJF)의 선점형 버전이다.

새로운 프로세스가 도착할 때마다 현재 실행 중인 프로세스의 남은 CPU 사용 시간과 준비 큐에 있는 모든 프로세스들의 CPU 사용 시간을 비교하여 가장 짧은 시간을 가진 프로세스에게 CPU를 할당하는 방식이다.

 

장점

• SJF보다 평균 대기 시간이 더 짧음
• 긴급한 작업의 빠른 처리 가능

 

단점

• 잦은 문맥 교환으로 오버헤드 증가
• CPU 사용 시간이 긴 프로세스의 기아 현상 발생 가능
• 프로세스의 실행 시간 예측이 어려움

 

 

우선순위 스케줄링 (Priority Scheduling)

다양한 기준으로 우선순위가 결정되며, CPU는 가장 높은 우선순위를 가진 프로세스에 할당되는 방식이다. 우선순위가 같은 프로세스들은 FCFS 순서로 스케줄된다.

 

우선순위는 내부적(CPU 사용량, 메모리 요구량 등) 또는 외부적(프로세스 중요도, 사용자 지정 등)으로 결정될 수 있다.

 

선점형과 비선점형 모두 가능하다.

• 선점형: 더 높은 우선순위 프로세스가 도착하면, 현재 실행 중인 프로세스의 CPU를 빼앗음
• 비선점형: 더 높은 우선순위 프로세스가 도착하면, 준비 큐에 삽입하여 다음 순서로 실행함

 

단점

• 무한 봉쇄(indefinite blocking) 발생 가능: 높은 우선순위 프로세스가 특정 자원을 기다리며 봉쇄되어 있는 동안, 해당 프로세스보다 우선순위가 낮은 프로세스들은 CPU를 할당받지 못하고 무기한으로 대기하는 현상
• 우선순위가 낮은 프로세스의 기아 현상 발생 가능 (에이징으로 해결 가능)

 

 

멀티 레벨 큐 스케줄링 (MLQ, Multilevel Queue Scheduling)

프로세스의 특성에 따라 여러 개의 준비 큐로 분류하여 관리하는 스케줄링 방식이다.

각 큐는 서로 다른 우선순위를 가지며, 높은 우선순위의 큐가 비어있을 때만 다음 우선순위 큐의 프로세스를 실행한다. 높은 우선순위 큐에 프로세스가 도착하면 즉시 실행된다. (선점형)

각 큐마다 프로세스 특성에 맞는 다른 스케줄링 알고리즘을 적용할 수 있고, 프로세스는 한 번 배정된 큐를 변경할 수 없다.

 

예시) 프로세스의 특성에 따른 큐 구분

• 입출력 집중 프로세스를 위한 큐 -> 높은 우선순위 큐, RR 스케줄링
• CPU 집중 프로세스를 위한 큐 -> 낮은 우선순위 큐, FCFS 스케줄링

 

단점

• 프로세스의 큐 간 이동이 불가능하여 유연성이 떨어짐
• 낮은 우선순위 큐의 프로세스의 기아 현상 발생 가능

 

 

멀티 레벨 피드백 큐 스케줄링 (MLFQ, Multilevel Feedback Queue Scheduling)

여러 개의 준비 큐를 사용하며, 멀티 레벨 큐 스케줄링과 달리 프로세스가 CPU 사용 패턴에 따라 큐 간 이동이 가능한 스케줄링 방식이다.

새로운 프로세스는 가장 높은 우선순위 큐에 삽입되어 실행되고, CPU 사용 시간이 길어지면 점차 낮은 우선순위 큐로 이동한다.

 

각 큐마다 다른 CPU 할당 시간(타임 슬라이스)을 가진다. 상위 큐에서는 짧은 CPU 할당 시간을 주어 입출력 중심 프로세스를 빠르게 처리하고, 하위 큐에서는 긴 CPU 할당 시간을 주어 계산 중심 프로세스를 효율적으로 처리한다. 최하위 큐는 FCFS 방식을 사용할 수 있다.

 

장점

• 프로세스의 CPU 사용 패턴 에 맞게 동적으로 큐 이동
• 에이징을 통한 기아 현상 예방

 

단점

• 구현이 복잡함
• 프로세스의 이동과 추적으로 인한 스케줄링 오버헤드 발생

 

 

4. CPU 스케줄링의 주요 문제점

기아 현상 (Starvation)

우선순위 기반 스케줄링(SJF, SRTF, Priority)에서 발생할 수 있는 문제이다.

우선순위가 낮은 프로세스가 우선순위가 높은 프로세스들에 의해 CPU 할당(실행)이 계속 연기되어, 무한정 대기하게 되는 현상을 말한다. 준비 큐에 먼저 도착했음에도 불구하고 우선순위가 높은 프로세스들이 계속 먼저 실행되어 실행 시점이 계속 뒤로 밀리는 것이다. 

 

해결 방법 - 에이징 (Aging)

프로세스의 대기 시간이 길어질수록 우선순위를 점차 높이는 방식이다. (나이 먹듯이)

오래 대기한 프로세스가 결국 높은 우선순위를 얻어 CPU를 할당받을 수 있게 한다.

우선순위 스케줄링의 대표적인 기아현상 해결 방법이다.

 

---

REF

https://velog.io/@yoonuk/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html

https://velog.io/@jeongopo/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98