CPU 스케줄링

‘운영체제와 정보기술의 원리’ 6장을 학습한 내용을 정리한 포스팅입니다

CPU

CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리 장치이다. 프로그램이 시작되어 메모리에 올라가면, 프로그램 카운터(PC)라는 이름의 레지스터에 현재 CPU가 수행할 코드의 메모리 주소값을 가지게 되고, CPU는 PC가 가르키는 주소의 기계어 명령을 수행하게 된다.

기계어 명령

CPU 내에서 수행하는 명령
- Add - CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령
메모리 접근을 필요로 하는 명령
- Load - 메모리에 있는 데이터를 CPU로 읽어 들이는 명령
- Store - CPU에서 계산된 결과값을 메모리에 저장하는 명령
입출력을 동반하는 명령
- CPU와 메모리 접근을 필요로 하는 명령보다 많이 느리다
- 키보드로부터 입력을 받는 경우 / 처리된 결과를 화면에 출력하는 경우
- 디스크에서 파일 데이터를 읽는 경우 / 파일로 저장하는 경우

사용자 프로그램

CPU burst과 I/O burst의 반복으로 구성되며, 각 프로그램마다 burst가 차지하는 비율이 균일하지는 않다.

I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스를 I/O 바운드 프로세스라 하고,

I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스를 CPU 바운드 프로세스라 한다.

I/O 바운드 프로세스의 예로는 대화형 프로그램이 이에 해당하고, 프로세스의 상당 시간을 입출력 작업 없이 CPU 작업에 사용하는 프로세스는 CPU 바운드 프로세스에 속한다.

CPU burst
- 프로그램이 I/O를 한 번 수행한 후 다음번 I/O를 수행하기 까지 직접 CPU를 가지고 명령을 수행하는 작업
I/O burst
- I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업

CPU 스케줄링의 필요성

컴퓨터 시스템의 수행되는 프로세스들의 대부분은 짧은 CPU를 버스트를 가지며, 극히 일부분만 긴 CPU 버스트를 가진다. CPU 버스트가 짧은 프로세스는 대부분 대화형 작업이므로 사용자와 인터액션을 해가며 프로그램을 수행시키므로 반응속도가 중요하다. 따라서 CPU 스케줄링을 할 때 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다

CPU 스케줄링이 발생하는 경우

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

CPU 스케줄링 방식

비선점형 방식
- CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법을 말한다
선점형 방식
- 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법을 말한다
- 대표적인 방법으로는 할당 시간을 부여한 후 타이머 인터럽트를 발생시키는 방법이 있다
(1), (4)가 비선점형 스케줄링의 예가 되며, (2), (3)은 선점형 스케줄링 방식에 해당한다

디스패처

CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지를 결정하고나면 선택된 프로세스에게 실제로 CPU를 이양하 는 작업이 필요하다. 이와 같이 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 커 널 모듈을 디스패처라고 부른다.

디스패처는 현재 수행중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB 로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다. 새로운 프로세스의 문맥을 복원시킨 후에는 사용자 모 드로 시스템의 상태를 전환해 사용자 프로그램에게 CPU의 제어권을 넘기게 된다.

스케줄링 성능 평가

시스템 관점의 지표로는 CPU 활동도와 처리량 등이 있으며,

사용자 관점의 지표로는 소요시간, 대기시간, 응답시간 등이 있다

CPU 활용도
- 전체 시간 중 CPU가 명령을 수행한 시간의 비율
- CPU가 휴면 상태에 머무리는 시간을 최소화 하는 것이 좋다
처리량
- 주어진 시간동안 CPU 버스트를 완료한 프로세스의 개수
- 주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스에게 CPU를 우선할당 하는 것이 유리하다
소요시간
- 프로세스가 CPU 요청 시점부터 CPU 버스트가 끝날 때 까지 걸린 시간
- 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합
- 프로그램이 시작해서 종료하는 데까지 걸리는 시간이 아니다 (프로세스에 CPU 버스트는 여러 차례 존재할 수 있다)
대기 시간
- 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
- 시분할 시스템에서 대기 시간이란 이번 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합을 의미한다
응답 시간
- 프로세스가 CPU 요청 시점부터 처음으로 CPU를 얻을 때까지 기다린 시간

metaphor

중국집에 주방장이 있고 손님이 있다고 하자. 이 때, 활용도와 처리량은 중국집 입장에서의 척도이고 소요시간, 대기시간, 응답시간은 손님 입장에서의 척도라 할 수 있다. 활용도는 전체 시간 중 주방장이 일한 시간의 비율을 나타내고, 처리량은 주방장이 주어진 시간 동안 몇 명의 손님에게 요리를 만들어 주었는지를 나타낸다. 중국집 입장에서는 주방장을 고용해서 가능한 일을 많이 시키는 것이 좋으므로 활용도가 높은 것을 선호한다. 또한, 많은 손님에게 요리를 판매하는 것이 이익이므로 처리량이 많은 것이 중요한 지표가 된다. 소요 시간은 손님이 중국집에 들어와서 주문한 음식을 다 먹고 나가기까지 소요된 총 시간을 말한다. 대기 시간은 음식을 먹은 시간을 제외한 순수하게 음식을 기다린 시간을 의미한다. 이 때 음식이 조금씩 여러 번에 걸쳐 나왔다면 음식을 먹은 시간을 제외하고 각각의 음식이 나오기까지 기다린 시간을 합한 것이 대기시간이 된다. 응답 시간은 최초의 음식이 나오기까지 기다린 시간을 뜻한다.

스케줄링 알고리즘

FCFS ( First-Come First-Served)

선입선출 방법으로서, 준비 큐에 도착한 프로세스 순서대로 CPU를 할당하고 그 프로세스가 자발적으로 CPU를 반납할 때 까지 CPU를 선점하지 않는다
CPU 버스트가 긴 프로세스가 먼저 도착한 경우 CPU 버스트가 짧은 프로세스 여러 개의 대기 시간이 증가하는 것은 물론 I/O 장치들의 활용도까지도 동반 하락하게 된다 (콘보이 현상)

SJF ( Shortest-Job First)

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
선점형 방식과 비선점형 방식으로 나뉜다
- SJF의 선점형 방식을 SRTF (Shortest Remaining Time First)라고도 부른다
- 프로세스들이 준비 큐에 도착하는 시간이 불규칙한 환경에서 선점형 방식이 프로세스 평균 대기시간을 최소화 하는 최적의 알고리즘이 된다
- 일반적인 시분할 환경에서는 중간중간에 새로운 프로세스가 도착하는 경우가 발생하므로 선점형 방식이 평균 대기 시간을 가장 많이 줄일 수 있는 방식이 된다
계속 CPU 버스트가 짧은 프로세스에만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 문제가 발생할 수 있다 (기아 현상)

우선순위 스케줄링

준비 큐에서 기다리는 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말한다
SJF 방식과 마찬가지로 선점형 방식과 비선점형 방식으로 나뉘며 선점형 방식의 경우 기아현상이 발생할 수 있다
이러한 문제점을 해결하기 위해 노화 기법을 사용할 수 있다

노화 기법

기다리는 시간이 길어지면 우선 순위를 조금씩 높여 CPU를 할당 받을 수 있게 해주는 방법

라운드 로빈 스케줄링

시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 이 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당하게 된다
할당 시간이 너무 길면 FCFS와 같은 결과를 나타내고, 할당 시간이 너무 짧으면 컨텍스트 스위칭의 오버헤드가 커지게 된다
여러 종류의 이질적인 프로세스가 같이 실행되는 환경에 효과적이다
빠른 응답시간을 보장할 수 있는 장점이 있다

멀티 레벨 큐

준비 큐를 여러 개로 분할 해 관리하는 스케줄링 기법
큐 자체에 대한 스케줄링은 고정 우선 순위 방식, 시분할 방식을 사용한다.
- 고정 우선 순위 방식
  - 높은 우선 순위의 큐가 비었을 때 낮은 우선 순위의 큐의 작업에 CPU를 할당한다
- 시분할 방식
  - 각 큐에 CPU 시간을 적절한 비율로 할당한다
  - 고정 우선 순위 방식에서 발생할 수 있는 기아현상을 해소할 수 있다
상위 큐에서는 라운드 로빈 스케줄링을, 하위 큐에서는 FCFS 스케줄링 기법을 주로 사용한다

멀티 레벨 피드백 큐

CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티 레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동가능하다는 점이 다르다
그림의 경우 상위에 있는 큐일 수록 우선순위가 높으며, 상위 두 개의 큐는 라운드 로빈 스케줄링을 사용하고 세 번째 큐는 FCFS 스케줄링 기법을 사용한다

다중 처리기 스케줄링

프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내 가도록 할 수 있다
대칭형 다중처리
- 각 CPU가 각자 알아서 스케줄링을 결정하는 방식
비대칭형 다중 처리
- 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터의 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식

실시간 스케줄링

실시간 시스템에서는 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다
실시간 시스템 분류
- hard real-time system
  - 미사일 발사, 원자로 제어 등 시간을 정확히 지켜야 하는 시스템을 말한다
  - 이러한 시스템에서는 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링 해야한다
- soft real-time system
  - 데드라인이 존재하긴 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지는 않는 시스템을 말한다
  - VOD 방식으로 영화를 볼 경우 시간당 정해진 프레임 수 만큼의 서비스가 이루어지지 않으면 화면 중간에 끊기는 현상이 발생한다. 그러나, 끊긴다고 해서 시스템이 붕괴되거나 치명적인 결과를 초래하지는 않는다
데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 사용한다