CPU 스케줄링

스케줄링의 개요

스케줄링은 크게 3단계로 나뉜다.

시스템의 부하를 고려하여 작업을 시작할지 말지,

즉, 시스템 내의 전체 작접 수를 조절하는 고수준 스케줄링

중지와 활성화로 활성화된 프로세스의 수를 조절하여 과부화를 막는 중간 수준 스케줄링

어떤 프로세스를 CPU에 할당하고 대기 상태로 보낼지 결정하는,

즉, 실제 스케줄링 작업을 수행하는 저수준 스케줄링으로 나뉜다.

 

이런 스케줄링의 목적은 다음과 같다.

 

• 공평성
  모든 프로세스가 공평하게 CPU를 할당받도록 하기 위함
• 효율성
  시스템 자원이 유휴시간 없이 사용되도록 하기 위함
• 안정성
  우선순위를 사용하여 중요 프로세스가 먼저 작동하게 하거나,
  시스템 자원을 점유하거나 파괴하려는 프로세스로 부터 자원을 보호하기 위함
• 확장성
  프로세스가 증가해도 시스템이 안정적으로 작동하게 하기 위함
• 반응 시간 보장
  적절한 시간 내에 프로세스가 응답할 수 있도록 하기 위함
• 무한 연기 방지
  특정 프로세스가 무한히 연기됨을 방지하기 위함

 

 

스케줄링 시 고려 사항

다음과 같은 프로세스를 우선순위를 높여 처리하는게 시스템 성능 향상에 도움이 된다.

그러기 위해 선점형 스케줄링을 사용해야 한다.

 

• 커널 프로세스
  커널이 생성한 프로세스를 뜻한다.
  (일반 프로세스보다 우선시)
• 전면 프로세스
  GUI상 화면 맨 앞에 놓인 프로세스로 현재 사용자와 상호작용 하는 프로세스를 뜻한다.
  (후면 프로세스보다 우선시)
• 대화형 프로세스
  (일괄 처리 프로세스보다 우선시)
• 입출력 집중 프로세스
  입출력을 많이 사용하는 프로세스로 입출력 버스트가 많은 프로세스를 뜻한다.
  (CPU 집중 프로세스보다 우선시)

 

 

다중 큐

준비 상태의 다중 큐에서는 우선순위에 맞는 큐에 프로세스가 등록된다.

또한 한 번에 하나의 프로세스를 꺼내어 CPU에 할당하게 된다.

반면 대기 상태의 다중 큐에서는 같은 입출력을 요구한 프로세스끼리 모아 등록한다.

또한 여러 개의 프로세스를 꺼내어 준비 상태로 옮기는데,

이 때 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터를 사용한다.

 

 

스케줄링 알고리즘

스케줄링 알고리즘의 평가 기준은 평균 대기 시간이 얼마나 적은가로 평가된다.

 

- 비선점형 알고리즘

* FCFS 스케줄링 (First Come First Service)

준비 큐에 도착한 순서대로 CPU를 할당하는 방식

평균 대기 시간은 (0 + 27  + 42)/3 = 23

처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 하염없이 기다려야 하기 때문에

시스템의 효율성이 떨어지는 좋지 못한 방식이다.

 

* SJF 스케줄링 (Shortest Job First)

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU에 할당하는 방식

평균 대기 시간은 (0 + 24  + 36)/3 = 20

운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵기 때문에 부정확한 순서가 결정될 수 있고,

작업 시간이 길다는 이유만으로 뒤로 밀려 공평성이 현저하게 떨어진다는 단점이 있다. (아사 현상)

이를 해결하기 위해 Aging 방법이 있긴 하다.

(한 번 양보시 나이를 1살 올리고 최대 n살이 되면 다음엔 반드시 실행)

 

* HRN 스케줄링 (Highest Response ratio Next)

SJF 방식에서 아사 현상을 해결하기 위한 방식으로

기다린 시간과 CPU 사용 시간을 고려하여 우선 순위를 결정한다.

평균 대기 시간은 (0 + 24  + 36)/3 = 20

SJF 에서 아사 현상을 개선했지만, 여전히 공평성이 위배되는 방식이다.

 

- 선점형 알고리즘

* Round-Robin 스케줄링

시분할 처리 방법으로 타임 슬라이스 동안 작업하다가,

작업을 완료하지 못하면 큐의 맨 뒤로 돌아가 자기 차례를 다시 기다리는 방식

평균 대기 시간은 (0 + 7+ 14+ 19 + 19 + 8)/3 = 22.33

선점형 알고리즘의 대표적인 예다.

하지만, 문맥 교환시의 오버헤드를 고려하여 타임 슬라이스를 적절하게 설정해야 한다.

현재 유닉스 운영체제는 100ms로 설정하고 있다.

 

* SRT 스케줄링 (Shortest Remaining Time)

기본적인 방식은 round robin 방식과 유사하지만,

CPU를 할당할 때 남은 작업 시간이 가장 적은 프로세스를 우선 할당하는 방식

평균 대기 시간은 (0 +4 + 16 + 27)/3 = 15.66

프로세스의 동작 시간을 주기적으로 계산해야 하고, 문맥 교환까지 해야 하기 때문에

round robin, SJF 보다 오버헤드가 크다.

뿐만 아니라, 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵고, 아사 현상이 일어나기에 잘 안쓰인다.

 

* 다단계 큐 스케줄링

우선 순위에 따라 준비 큐를 여러개 사용하는 방식

고정형 우선 순위를 사용하고, 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위의 큐의 작업이 시작된다.

 

* 다단계 피드백 큐 스케줄링

프로세스가 CPU를 한 번씩 할당받아 실행될 때 마다 프로세스의 우선 순위를 낮추는 방식

단, 우선순위가 낮아져도 커널 프로세스가 일반 프로세스 큐에 삽입되지는 않는다.

 

우선 순위가 낮아질수록 CPU를 얻을 확률이 적어지지만, 대신 타임 슬라이스를 많이 준다.

마지막 큐는 FCFS 스케줄링 방식을 따라가게 된다.

(근데 실제로는 무한의 시간을 주진 않는다)

 

- 우선순위 스케줄링 (선점 + 비선점)

프로세스의 중요도에 따른 우선순위를 반영한 방식 (SJF, HRN, SRT에 적용 가능)

한 번 우선순위를 부여받으면 종료시까지 우선순위가 고정되는 고정 우선순위 알고리즘과

시스템의 상황을 반영하여 우선순위가 변하는 변동 우선순위 알고리즘, 두 가지로 분류된다.

 

어느 쪽이든, 우선 순위가 높은 프로세스가 우선적으로 CPU를 할당 받기에 공평성을 위배하고 아사 현상을 이르킨다.

또한, 준비 큐의 순서를 무시하고 우선 순위를 매기는 과정에서 오버헤드가 발생해 시스템의 효율성을 떨어뜨린다.

 

인터럽트 처리

- Polling

입출력 요청시 운영체제가 주기적으로 입출력장치를 직접 확인해서 처리하는 방식

 

- Interrupt

이벤트 드리븐 방식처럼 입출력을 요청하고 입출력 완료시 이벤트를 발생시켜 알림받는 방식

 

* 동기적 인터럽트

프로세스가 실행 중인 명령어로 인해 발생하는 인터럽트

런타임 중 메모리 영역 침범, 오버플로, 산술연산 문제 등 프로그램 상 문제 때문에 발생하는 인터럽트,

의도적으로 프로세스를 중지하기 위해 발생시킨 인터럽트,

주변 장치의 조작에 의한 인터럽트 가 이에 해당한다.

 

* 비동기적 인터럽트

디스크 읽기 오류, 메모리 불량 등 하드웨어적인 오류로 발생하는 인터럽트,

사용자가 직접 작동하는 키보드, 마우스 인터럽트 가 이에 해당.

 

인터럽트는 다음과 같은 방식으로 처리된다.

1. 인터럽트 발생 시 실행 중인 프로세스가 일시 정지되며, 임시 레지스터에 프로세스 관련 정보를 저장
2. 인터럽트 컨트롤러가 실행되어 인터럽트의 처리 순서를 결정
3. 순서에 맞게 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행
4. 인터럽트 처리 후 프로세스 다시 실행 또는 종료