• 스터디 설명 : 에이블스쿨 교육생들과 CS 공부를 위해 자발적으로 개설 및 참여한 스터디입니다.
• 혼자 공부하는 컴퓨터 구조+운영체제를 교재로 사용하였고, 일부 내용은 별도의 자료로 공부하였습니다.

11-1 CPU 스케줄링 개요

• 프로세스에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라 한다. 컴퓨터 성능에 있어 대단히 중요한 문제이다.

프로세스 우선순위 (priority)

• 프로세스에는 우선순위가 존재한다.
• 우선순위가 높은 프로세스란 빨리 처리해야하는 프로세스로, 대표적으로 입출력 작업이 많은 프로세스가 있다.
  • 입출력 장치가 우선순위가 높은 이유는 입출력이 이루어질 때 마다 프로세스가 대기상태로 전환되기 때문이다.
  • 때문에 높은 우선순위를 부여하면 실행시간이 짧아 CPU를 많이 사용하지 않으면서도, 입출력에 필요한 처리를 빨리 끝낼 수 있다.
  • 이러한 프로세스를 입출력 집중 프로세스(I/O bound process)라고 한다.
• 반대로 입출력은 적지만 복잡한 연산, 컴파일 등 CPU작업이 많은 프로세스가 있는데, 이를 CPU 집중 프로세스(CPU bound process)라고 한다.
  • 한번에 많은 CPU를 사용하기 때문에 입출력 프로세스와 동일한 빈도로 실행되는 것은 비합리적이다.
  • 때문에 입출력 집중 프로세스의 처리가 끝날 때까지 대기하게 된다. (낮은 우선순위)
• 우선순위 처리를 위해 운영체제는 각 프로세스의 PCB에 우선순위를 명시한다.
  • 운영체제별로 프로세스 우선순위를 직접 확인해 볼 수 있는 방법이 있다.

스케줄링 큐

• 사실 CPU가 우선순위를 확인하기 위해 일일히 PCB를 확인하는 것은 비효율적이다.
• 때문에 운영체제는 각 프로세스의 목적별로 프로세스들을 모두 줄 세운다. 이러한 줄을 스케줄링 큐로 구현하고 관리한다.
  • 큐는 보통 선입선출 구조의 자료형을 말하지만 스케줄링에서 말하는 큐는 반드시 선입선출 할 필요는 없다.
• 큐에는 여러가지 종류가 있는데, 대표적으로 준비 큐(ready queue)와 대기 큐(waiting queue)가 있다.
  • 준비 큐는 CPU를 이용하려는 프로세스들의 큐이며, 대기 큐는 입출력 장치를 이용하기 위해 대기상태가 된 프로세스들의 큐이다.
  • 대기 큐에 있는 프로세스는 입출력 완료 인터럽트를 받으면 준비 큐로 이동한다.
• 기본적으로 운영체제는 큐에 PCB가 삽입 된 순서대로 실행하되, 우선순위가 높은 프로세스를 먼저 실행한다.

• 최종적으로 프로세스 상태 다이어그램을 위와 같이 그릴 수 있다.

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

• 선점형 스케줄링(preemptive scheduling)은 다른 프로세스가 CPU를 사용하고 있더라도 운영체제가 자원을 강제로 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미한다.
  • 타이머 인터럽트가 발생하면 CPU 자원이 강제로 반납되고 다음 프로세스에 할당되는 것 역시 선점형 스케줄링의 일종이다.
• 비선점형 스케줄링(non-preemptive scheduling)은 CPU를 사용하는 프로세스가 종료되거나 스스로 대기 상태로 전환되기 전까지는 다른 프로세스에 자원을 할당할 수 없는 스케줄링 방식이다. 즉 한 프로세스가 자원 사용을 독점할 수 있다.
• 대부분의 현대 운영체제는 선점형 스케줄링 방식을 차용하고 있지만, 비선점형 스케줄링도 문맥 교환에서 발생하는 오버헤드가 적다는 장점이 있다.

11-2 CPU 스케줄링 알고리즘

• CPU 스케줄링 알고리즘의 종류는 운영체제 별로 모두 다르고, 용어도 다르기 때문에 특정 용어보다는 ‘아이디어’를 이해하는 것에 집중하자.

스케줄링 알고리즘의 종류

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

• 단순하게 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식
• 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 단점이 있다.
• 가령 A가 실행에 17ms, B가 8ms, C가 1ms 걸린다고 했을 때, C는 1ms를 실행하기 위해서 25ms를 기다려야한다. 이런 현상을 호위 효과(convoy effect)라고 한다.
• B역시 17ms를 기다려야 하므로 A,B,C의 평균 대기시간은 14ms가 된다.

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

• SJF는 Shortest Job First Scheduling이다.
• CPU를 가장 짧게 사용하는 프로세스를 먼저 처리하는 비선점형 스케줄링 방식이다.
• 예시에서 C→B→A 순서로 실행되며 평균 대기 시간은 (1 + 8) / 3 = 3ms이다.

라운드 로빈 스케줄링

• 기존의 FCFS 스케줄링에 타임 슬라이스라는 개념이 더해진 방식이다.
• 타임 슬라이스는 CPU를 사용할 수 있는 정해진 시간을 의미하며, 각 프로세스는 정해진 타임 슬라이스만큼만 한 번에 CPU를 사용할 수 있다.
• 라운드 로빈 스케줄링의 핵심은 타임 슬라이스의 크기인데, 너무 크면 FCFS 스케줄링과 같이 호위 효과가 발생할 가능성이 크고, 너무 작으면 잦은 문맥교환으로 인한 오버헤드가 발생한다.

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

• 선점형 스케줄링 알고리즘으로, SJF 스케줄링과 라운드 로빈 스케줄링을 합친 방식이다.
• 정해진 타임 슬라이스 만큼의 CPU 사용시간을 부여받아 돌아가며 사용한다는 점은 동일하지만, 가장 잔여 실행시간이 적은 프로세스가 다음 순서로 선택된다.

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

• 프로세스에 우선순위를 부여하여 가장 높은 프로세스부터 실행하는 알고리즘이다.
• SJF 스케줄링이나, SRT 스케줄링의 경우 실행시간이 짧은 프로세스가 계속 실행될 경우 실행시간이 긴 프로세스가 계속 실행되지 못하는 기아(starvation) 현상이 발생할 수 있다.
• 기아 현상을 방지하기 위해 대기하고 있는 프로세스의 우선순위를 점차 높이는 방식인 에이징(aging) 기법을 적용할 수 있다. 우선순위 스케줄링이 바로 에이징 기법을 이용한다.

다단계 큐 스케줄링 (multilevel queue scheduling)

• 우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식이다.
• 우선순위가 가장 높은 큐의 프로세스들을 먼저 실행하고, 해당 큐가 비면 그 다음 우선순위 큐의 프로세스를 실행하는 식이다.
• 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다는 장점이 있으며, 각 큐 별로 타임 슬라이스나 스케줄링 알고리즘을 다르게 적용할 수 있다.

다단계 피드백 큐 스케줄링 (multilevel feedback queue scheduling)

• 다단계 큐 스케줄링에서는 프로세스가 큐 사이를 이동할 수 없었다. 즉 기아 현상이 발생할 가능성이 있다.
• 다단계 피드백 큐 스케줄링은 새로운 프로세스가 준비 상태가 되었을 때, 가장 높은 우선순위 큐에 삽입한다.
  • 타임슬라이스 동안 CPU를 사용한 후에도 실행이 끝나지 않았다면, 처음 삽입된 것 보다 한단계 낮은 우선순위 큐에 삽입된다. 이렇게 실행될 때마다 큐의 우선순위가 점점 낮아지게 된다.
  • 즉 CPU를 오래 사용해야하는 CPU 집중 프로세스는 점차 우선순위가 낮아지게 되고, 입출력 집중 프로세스는 높은 우선순위를 받아 빠르게 실행을 처리할 수 있다.
• 또한 에이징 기법 또한 적용하여, 오래 기다리고 있는 프로세스를 우선순위가 높은 큐로 이동시킨다.
• 현재 가장 일반적인 CPU 스케줄링 알고리즘으로 사용되고 있다.