11장 CPU 스케줄링

11-1. CPU 스케줄링 개요

• CPU 스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
• 프로세스들에게 현명하게 CPU를 배분하지 못하면 반드시 실행되어야 할 프로세스들이 실행되지 못하거나, 당장 급하지 않은 프로세스들만 주로 실행되는 등 무질서한 상태가 발생할 수 있기 때문에 중요한 문제이다.

프로세스 우선순위

• 프로세스를 순서대로 CPU를 이용하게 하는 방법은 좋은 방법이 아니다.
• 그 이유는 우선순위가 다르기 때문이다.
• 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있다.

• • 프로세스는 실행 상태와 대기 상태를 반복하며 실행된다.
  • 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스도 있고 (입출력 집중 프로세스),
  • 복잡한 수학 연산, 컴파일을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스도 있다 (CPU 집중 프로세스).
  • 입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르며 CPU를 덜 사용하기 때문에 우선순위가 높은 것이다.
• 프로세스의 중요도, 상황에 맞게 운영체제는 프로세스마다 우선순위를 부여하여 PCB에 명시하고, 먼저 처리할 프로세스를 결정한다.

스케줄링 큐

• PCB에 우선순위가 적혀는 있지만 일일이 뒤적거리는 것은 비효율적이다.
• 그래서 운영체제는 프로세스들에게 ‘줄을 서서 기다릴 것’을 요구한다. 이 줄을 스케줄링 큐로 구현하고 관리한다.
• 스케줄링에서 이야기하는 큐는 반드시 선입선출 방식일 필요는 없다.

• 즉, 운영체제는 새로 생성되는 프로세스들과 CPU를 이용하고 싶은 프로세스들, 특정 입출력장치를 이용하고 싶은 프로세스들을 큐에 삽입하여 줄을 세운다.

• 준비 큐: CPU를 이용하고 싶은 프로세스들이 서는 줄
• 대기 큐: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
• 우선순위가 낮은 프로세스들이 먼저 큐에 삽입되어 줄을 섰다고 하더라도 우선순위가 높은 프로세스가 먼저 처리될 수도 있다.

• 입출력이 완료되어 완료 인터럽트가 발생하면, 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 대기 큐에서 삭제한 뒤 준비 큐로 이동한다.

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

• CPU를 사용하는 도중 다른 급한 프로세스가 CPU를 지금 당장 사용하길 요청한다면 어떻게 해야할까?
• 선점형 스케줄링: 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식 (비켜! 내가 쓸 거야!)
  • 장점: 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다.
  • 단점: 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
• 비선점형 스케줄링: 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식 (기다려!)
  • 장점: 문맥 교환에서 발생하는 오버헤드가 적다.
  • 단점: 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서도 무작정 기다리는 수밖에 없다.
• 현재 대부분의 운영체제는 선점형 스케줄링 방식을 차용하고 있다.

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

스케줄링 알고리즘의 종류

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

• 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
• 공정해 보이지만, 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 점에서 부작용이 있다. 이를 호위 효과라고 한다.

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

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

라운드 로빈 스케줄링

• 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다.
  • 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 즉, 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.
• 라운드 로빈 스케줄링에서는 타임 슬라이스 크기가 매우 중요하다.
  • 타임 슬라이스가 지나치게 크면 사실상 선입 선처리 스케줄링과 다를 바가 없고,
  • 지나치게 작으면 문맥 교환에 발생하는 비용이 커질 수 있다.

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

• 최단 작업 우선 스케줄링 + 라운드 로빈 알고리즘
• 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.
• 우선순위 스케줄링의 문제점은 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다는 점이다. 이를 기아 현상이라고 한다.
• 이를 방지하기 위한 대표적인 기법으로 에이징이 있다.
  • 에이징: 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케줄링

• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.
• 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해지고, 큐 별로 타임 슬라이스를 여러 개 지정할 수도 있다는 장점이 있다.

다단계 피드백 큐 스케줄링

• 앞에서 본 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없다. 그래서 기아 현상이 발생할 수도 있다.
• 이를 보완한 것이 다단계 피드백 큐 스케줄링이다.
• 즉, 프로세스들이 큐 사이를 이동할 수 있는 방식이다.
• 낮은 우선순위 큐에 너무 오래 기다리고 있는 프로세스가 있다면 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방한다.