'운영체제와 정보기술의 원리' 책을 바탕으로 정리한 내용입니다.

06. CPU 스케줄링

CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치이다.
기계어 명령은 크게 CPU 내에서 수행되는 명령, 메모리 접근을 필요로 하는 명령, 입출력을 동반하는 명령으로 나뉜다.

CPU 내에서 수행되는 명령

• add 명령 : CPU 내에 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령

메모리 접근을 필요로 하는 명령

• load 명령 : 메모리에 있는 데이터를 CPU로 읽어들이는 명령
• store 명령 : CPU에서 계산된 결괏값을 메모리에 저장하는 명령
  → CPU내에서 수행되는 명령보다는 시간이 오래 소요되지만 비교적 짧은 시간에 수행할 수 있는 명령

두 명령은 사용자 프로그램이 직접 수행할 수 있는 일반명령이다.

입출력을 동반하는 명령

다른 두 명령에 비해 오랜 시간이 소요된다.

모든 입출력 명령을 특권명령으로 규정해 사용자 프로그램이 직접 수행할 수 없도록 하고 운영체제를 통해 서비스를 대행한다

사용자 프로그램이 수행되는 과정은 CPU작업과 I/O 작업의 반복

서로 다른 두 단계의 조합으로 프로그램 수행은 이뤄진다.

• CPU 버스트
  : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 단계
  • 프로그램이 I/O를 한 번 수행한 후 다음 번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행
• I/O 버스트
  : I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
  • I/O 작업이 요청 된 후 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업

각 프로그램 마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지 않다.

• I/O 바운드 프로세스
  : I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
  • 인터렉션을 계속 받는 대화형 프로그램
  • 짧은 CPU 버스트를 많이 가짐
• CPU 바운드 프로세스
  : I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
  • 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램
  • 소수의 긴 CPU 버스트로 구성

→ 시분할 시스템에서는 CPU 버스트가 균일하지 않은 다양한 프로그램들이 공존하므로 효율적인 CPU 스케줄링 기법이 필요
: CPU 스케줄링 시 I/O 바운드 프로세스의 우선순위를 높여주는 것이 바람직

CPU 스케줄러

CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제.
프로세스가 CPU를 할당받고 기계어 명령을 수행하다가 타이머 인터럽트가 발생하면 CPU 스케줄러가 호출된다.

CPU 스케줄러가 필요한 경우

1. 실행 상태에 있던 프로세스가 I/O 요청으로 봉쇄 상태로 바뀌는 경우
2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 프로세스의 상태가 준비 상태로 바뀌는 경우
4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우

CPU 스케줄링 방식

• 비선점형 방식
  : CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
• 선점형 방식
  : 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 방식
  • 할당시간을 부여해 타이머 인터럽트를 발생

디스패처

새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제 코드

• 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장
• 새롭게 선택된 프로세스의 문맥을 PCB로 부터 복원
• 해당 프로스세에게 CPU를 넘기는 과정을 수행
• 복원 후 시스템의 상태를 사용자모드로 전환해 사용자 프로그램에게 CPU의 제어권을 넘긴다.

스케줄링의 성능 평가

• 시스템 관점의 지표
  • CPU 이용률
    : 전체 시간 중 CPU가 일을 한 시간의 비율
  • 처리량
    : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇개를 끝마쳤는지 나타내는 것
• 사용자 관점의 지표
  • 소요시간
    : 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
  • 대기시간
    : CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
  • 응답시간
    : 프로세스가 준비 큐에 들어온 후 첫번째 CPU를 획득하기까지 기다린 시간

스케줄링 알고리즘

1. 선입선출 스케줄링

프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식.

• 먼저 도착한 프로셋의 성격에 따라 평균 대기시간이 크게 달라진다.

2. 최단작업 우선 스케줄링

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식

• 평균 대기시간을 가장 짧게 하는 최적 알고리즘
• 비선점형 방식
  : 현재 CPU를 점유하고 있는 프로세스가 CPu 버스트를 모두 수행하고 스스로 CPU 버스트를 내어놓을 때까지 스케줄링 하지 않는다.
• 선점형 방식
  : CPU 버스트 시간이 더 짧은 프로세스가 도착하면 현재 수행 중인 프로세스에게서 CPU를 선점해 CPU 버스트 시간이 더 짧은 프로세스에게 할당
  → 현실적으로 어려운 점은 CPU 버스트 시간을 미리 알 수 없음

3. 우선순위 스케줄링

준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식

• 우선순위값
  : 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정
• 비선점형 방식
  : 일단 CPU를 얻었으면 비록 우선순위가 더 높은 프로세스더라도 CPU를 자진 반납하기 전까지 선점하지 않는다
• 선점형 방식
  : CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 도착하여 CPU를 선점해 새롭게 도착한 프로세스에게 할당하는 경우

기아현상

우선순위가 높은 프로세스가 계속 도착하는 상황에서 우선순위가 낮은 프로세스는 CPU를 얻지 못한 채 계속 기다리게 되는 현상

• 노화기법
  : 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 높은 우선순위가 되어 CPU를 할당 받을 수 있게 하는 방법

4. 라운드 로빈 스케줄링

시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식

• 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당
• 이 프로세스의 준비 큐의 제일 뒤에 가서 줄을 서 다음번 차례가 오기를 기다림
• 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당시간이라고 한다.
  → 여러 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다.
  모든 프로세스는 (n-1)q시간 내에 적어도 한 번은 CPU를 할당받을 수 있다.
• SJF 방식보다 평균 대기 시간은 길지만 응답시간은 더 짧다.
• 할당시간이 만료되어 CPU를 회수하는 방법으로 쓰인다.

라운드 로빈의 목적

: CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에 CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것

• 할당시간을 너무 짧게 설정하면 문맥교환의 오버헤드가 증가해 전체 시스템의 성능을 저하시킬 수 있다.
• 프로세스를 하나씩 끝내는 식으로 시간이 흐름에 따라 적어도 하나씩은 처리가 완료된 프로세스가 발생해 평균대기시간이나 소요시간 측면에서 좋은 결과를 얻을 수 있다.

5. 멀티레벨 큐

준비 큐를 여러개로 분할해 관리하는 스케줄링 기법

• 한 줄이 아닌 여러 줄로 서는 것
• 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 된다.
• 전위 큐
  : 대화형 작업을 담기 위한 것
  • 응답시간을 짧게 하기 위해 라운드로빈 스케줄링을 사용
• 후위 큐
  : 계산 위주의 작업을 담기 위한 것
  • 응답시간이 큰 의미가 없기 때문에 FCFS 스케줄링기법을 사용해 문맥교환 오버헤드를 줄인다.
• 고정 우선순위 방식
  : 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때만 서비스
• 타임 슬라이스 방식
  : 큐에 대한 기아 현상을 해소할 수 있는 방식으로, 각 큐에 CPU 시간을 적절할 비율로 할당

6. 멀티레벨 피드백 큐

CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.

멀티레벨 피드백 큐 정의 요소

• 큐의 수
• 큐의 스케줄링 알고리즘
• 프로세스를 상위 큐로 승격시키는 기준
• 프로세스를 하위 큐로 강등시키는 기준
• 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준

• 스케줄링 방식으로 최상위 큐가 우선적으로 CPU를 배당받고, 상위 큐가 비었을 때 하위 큐에 프로세스들이 CPU를 할당 받을 수 있게 한다.

7. 다중처리기 스케줄링

CPU가 여러 개인 시스템을 다중처리기 시스템이라하고 이런 환경에서 프로세스를 준비 큐에 한 줄로 세워 각 CPU가 알아서 다음 프로세스를 꺼내가도록 한다.

• 반드시 특정 CPU에서 수행되어야하는 프로세스가 있는 경우 한 줄 이 아니라 각 CPU 별로 줄세우기를 할 수도 있다.
• 부하균형 메커니즘 필요
  : CPU 별 부하가 적절히 분산되도록 한다.
• 대칭형 다중처리
  : 각 CPU가 알아서 스케줄링을 결정
• 비대칭형 다중처리
  : 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직임

8. 실시간 스케줄링

• 경성 실시간 시스템
  : 정확히 시간을 지켜야하는 시스템
• 연성 실시간 시스템
  : 데드라인이 존재하지만 못지켰다고 큰일이 나지는 않는 시스템

스케줄링 알고리즘의 평가

• 큐잉모델
  : 이론가들이 수행하는 방식으로 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 성능지표인 CPU의 처리량과 대기시간을 구하는 것
• 시뮬레이션
  : 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 결과값을 확인 하는 것
• 규현 및 실측
  : 운영체제 커널의 소스 코드 중 CPU스케줄링을 수행하는 코드를 수정해 컴파일 후 시스템에 설치하는 과정