[OS] Chapter 4 CPU 스케줄링

• 이 장에서는 CPU 스케줄링 알고리즘의 종류와 각각의 특성을 살펴본다.

1. 스케줄링의 개요

• CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.

1.1 식당 관리자의 스케줄링

• 스케줄링은 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일을 말한다.

1.2 스케줄링의 단계

• CPU 스케줄러도 관리의 범주를 나누어 스케줄링 한다. 규모에 따라 고수준 스케줄링, 중간 수준 스케줄링, 저수준 스케줄링으로 구분된다.

1.2.1 고수준 스케줄링

• 시스템 내의 전체 작업 수를 조절하는 것을 말한다.
• 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정한다.

1.2.2 저수준 스케줄링

• 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다.
• 3장에서 학습한 프로세스 상태에 관한 내용은 대부분 저수준 스케줄링에 해당한다.

1.2.3 중간 수준 스케줄링

• 고수준 스케줄링과 저수준 스케줄링 사이에서 일어나는 스케줄링이다.
• 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다.
• 완충하는 역할을 한다.

1.2.4 스케줄링의 단계 정리

• 고수준 스케줄링 - 작업을 시작할지 말지를 결정한다.
• 중간 수준 스케줄링 - 시스템이 부하가 걸리는 경우 활성화된 프로세스 중 일부를 보류 상태로 보낸다. 여유가 생기면 다시 활성화된다.
• 저수준 스케줄링 - 실제로 작업이 이루어진다. 다음 부분에서는 저수준 스케줄링에 대해서 다룬다.

1.3 스케줄링의 목적

• CPU 스케줄링의 원래 목적은 모든 프로세스가 공평하게 작업하도록 하는 것이다. 중요도에 따라 우선순위를 배정한다.
• 정리 - 공평성, 효율성, 안전성, 확장성, 반응 시간 보장, 무한 연기 방지
• 안전성과 효율성을 높이기 위해 어떠한 경우는 일정 부분 공평성을 희생한다.
• 일반적으로 운영체제 프로세스는 일반 프로세스보다 우선적으로 CPU를 배정받는다.

2. 스케줄링 시 고려사항

• 이 절에서는 스케줄러의 다양한 고려 사항을 살펴본다.

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

• 정의
  • 선점형 스케줄링 - 어떤 프로세스가 CPU를 할당받아 실행중이어도 OS가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
  • 비선점형 스케줄링 - 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
• 선점형 스케줄링
  • 인터럽트처리가 있다. CPU가 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 커널이 인터럽트를 처리하고 원래 작업으로 돌아간다.
  • 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생기는 것이 단점
  • 대화형 시스템이나 시분할 시스템에 적합
  • 대부분의 저수준 스케줄러는 이 방식을 사용
• 비선점형 스케줄링
  • 스케줄러의 작업량이 적고 문맥 교환에 의한 낭비도 적다.
  • 사용시간이 긴 프로세스 때문에 짧은 프로세스가 기다려야 한다 → 전체 시스템 처리율이 낮다.
  • 일괄 작업 시스템에서 사용하던 방식이다.
• 선점형 스케줄링 안 비선점형 스케줄링
  • 비선점형 스케줄링의 중요도를 매우 낮게 설정하여 선점형 프로세스에 영향을 덜 미치도록 한다.

2.2 프로세스 우선순위

• 대부분의 CPU 스케줄러의 우선순위를 사용한다. ← 프로세스의 중요도가 다르다는 의미
• 프로세스는 커널 프로세스와 일반 프로세스로 나뉜다. 커널 프로세스의 우선순위가 일반 프로세스보다 높다.
• 우선순위가 높다는 것은 더 빨리 자주 실행된다는 의미이다.
• 일반 프로세스의 우선순위는 사용자가 조절할 수 있다.

2.3 CPU 집중 프로세스와 입출력 집중 프로세스

• 프로세는 생성된 후 준비, 실행, 대기 상태를 거쳐완료된다.
• CPU를 할당받아 실행하는 작업을 CPU 버스트, 입출력 작업을 입출력 버스트라고 한다.
• 프로세스는 CPU 집중 프로세스, 입출력 집중 프로세스로 나눌 수 있다.
  • CPU 집중 프로세스 - 수학 연산과 같이 CPU를 많이 사용하는 프로세스를 말한다. 즉 CPU 버스트가 많은 프로세스이다.
  • 입출력 집중 프로세스 – 입출력을 많이 사용하는 프로세스를 말한다. 입출력 버스트가 많은 프로세스이다.
• CPU 집중 프로세스와 입출력 집중 프로세스가 같이 있을 때는 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다.
• 스케줄링 할 때 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템의 효율이 향상된다.
• 사이클 훔치기 - 입출력 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우

2.4 전면 프로세스와 후면 프로세스

• 전면 프로세스 - 현재 입력과 출력을 상요하는 프로세스이며, 사용자와의 상호작용이 가능하며 상호작용 프로세스라고도 한다.
• 후면 프로세스 - 사용자와 상호작용이 없는 프로세스이다. 일괄 작업 프로세스라고도 한다.
• 우선순위는 전면 프로세스가 후면 프로세스보다 높다.

2.5 정리

• 프로세스의 종류를 정확히 구분할 수 없을 때가 있다.

3. 다중 큐

3.1 준비 상태의 다중 큐

• 우선순위에 따라 여러 개의 큐를 만들어서 프로세스를 관리하면 좋다.
• 프로세스의 우선순위를 배정하는 방식의 종류
  • 고정 우선순위 - 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다. 구현이 쉽지만 작업 효율이 떨어진다.
  • 변동 우선순위 - 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식이다. 구현이 어렵지만 효울적이다.
• 반전 순위 - 프로세스의 낮은 우선순위를 높은 우선순위로 바꾸는 것

3.2 대기 상태의 다중 큐

• 대기 상태도 다중 큐를 사용한다. ← 대기 상태는 입출력이 완료되기를 기다리는 프로세스가 모여있는 곳이다.
• 같은 입출력을 요구한 프로세스끼리 모아놓는다.
• 준비 큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다.
• 대기큐의 경우 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료구조를 사용한다.

4. 스케줄링 알고리즘 - 229

• 스케줄링 알고리즘
  • 비선점형 알고리즘 - 프로세스가 CPU를 할당받으면 작업이 끝날 때까지 CPU를 놓지 않기 때문에 효율이 떨어져서 지금은 사용 거의 안함
  • 선점형 알고리즘 - 시분할 시스템을 고려하여 만들어진 알고리즘으로, 운영체제가 CPU를 강제로 빼앗을 수 있다.

4.1 스케줄링 알고리즘의 선택 기준

• 스케줄링 알고리즘 평가 기준
  • CPU 사용률 - 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
  • 처리량 - 단위 시간당 작업을 마친 프로세스의 수
  • 대기 시간 - 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간이다
  • 응답 시간 - 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간이다.
  • 반환 시간 - 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간 = 대기 시간 + 실행 시간
• 주로 대기 시간, 응답 시간, 반환 시간을 계산한다.
• 스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다. 하지만 작업 패턴에 따라 바뀔 수 있어서 절대적인 지표로 볼 수는 없다.

4.2 FCFS 스케줄링

4.2.1 FCFS 스케줄링의 동작 방식

• FCFS 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, FIFO 스케줄링 이라고도 한다.

4.2.2 FCFS 스케줄링의 성능

• 구하면 된다. 책 예시는 23ms이다.

4.2.3 FCFS 스케줄링의 평가

• 공평하지만 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있다. → 콘보이 효과 또는 호위 효과라고 한다.
• 프로세스가 입출력을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다는 것이다. ← 프로세스 상태 변화가 없어서 작업 효율이 떨어진다.

4.3 SJF 스케줄링

4.3.1 SJF 스케줄링의 동작 방식

• SJF 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 한다.
• 콘보이 효과를 완화하여 시스템의 효율성을 높이는 것이다.

4.3.2 SJF 스케줄링의 성능

• 구하면 된다. 책 예시는 20ms이라고 한다.

4.3.3 SJF 스케줄링의 평가

• 평균 대기 시간이 줄어들어 시스템의 효유성이 높아진다.
• 다음과 같은 단점이 있어 사용하기 어렵다.
  • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다. 사용자와의 상호작용이 빈번히 발생하기 때문에 파악하기 어렵다.
  • 공평하지 못하다. 만약 A보다 짧은 작업이 계속 들어오면 A는 작업이 계속 연기 된다. → 아사 현상 또는 무한 봉쇄 현상이라고 한다.
• 해결법
  • 종료 시간 예측 어려움 → 프로세스가 자신의 작업 시간은 운영체제에 알려주어 해결할 수 있다. 하지만 악의적인 프로세스나 예측의 어려움이 있다.
  • 에이징(aging)으로 완화할 수 있다. 프로세스가 양보할 수 있는 상한선을 정하는 방식이다. 하지만 에이징 값을 어떤 기준으로 정할 것인지가 문제가 한계가 있다.

4.4 HRN 스케줄링

4.4.1 HRN 스케줄링의 동작 방식

• 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘으로, 최고 응답률 우선 스케줄링이라고도 한다. 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식이다.
• 우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간
• 스케줄링 방식에 에이징을 구현한 셈이다.

4.4.2 HRN 스케줄링의 평가

• 공평성이 위배되어 많이 사용되지 않는다.

4.5 라운드 로빈 스케줄링

4.5.1 라운드 로빈 스케줄링의 동작 방식

• 한 프로세스가 할당 받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.
• 선점형 알고리즘 중 가장 단순하고 대표적인 방식으로, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다.

4.5.2 라운드 로빈 스케줄링의 성능

• 구하면 된다. 책의 예시에서는 22.33ms라고 한다.
• 선점형 방식에서는 프로세스가 CPU를 일정 시간동안 사용한 후 다른 프로세스에 주어야 하기 때문에 앞의 긴 작업을 무작정 기다리는 콘베이 효과가 줄어든다.

4.5.3 타임 슬라이스의 크기와 문맥 교환

• 라운드 로빈 스케줄링과 FCFS 스케줄링의 평균 대기 시간이 같다면 라운드 로빈 스케줄링이 더 비효율적인 알고리즘이다. 문맥교환 시간이 추가되기 때문이다.
• 라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 한다.
  • 타임 슬라이스가 큰 경우 - 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다. → FCFS 스케줄링과 다를 게 없다.
  • 타임 슬라이스가 작은 경우 - 너무 작게 설정하면 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못 하는 문제가 발생한다.
  • ⇒ 적당하게 하는 것이 중요하다.

4.6 SRT 우선 스케줄링

• SRT 우선 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로, 최소 잔류 시간 우선 스케줄링이라고도 한다. → SJF 스케줄링의 선점형 버전이라고 할 수 있다.
• 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.

4.6.2 SRT 스케줄링의 성능

• 구하면 된다. 책의 예시는 15.66ms라고 한다.

4.6.3 SRT 스케줄링의 평가

• 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야하므로 SJF 스케줄링에는 없는 작업이 추가된다.
• 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다.

4.7 우선순위 스케줄링

4.7.1 우선순위 스케줄링의 동작 방식

• 프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다.
• 우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있다.
  • 비선점 - SJF 스케줄링 - 작업 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
  • 비선점 - HRN 스케줄링 - 작업 시간이 짧거나 대기 사간이 긴 프로세스에 높은 우선순위를 부여한다.
  • 선점 - SRT 스케줄링 - 남은 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
• 우선순위 알고리즘은 고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 나뉜다.
  • 고정 순위 일고리즘 - 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정된다. 효율성이 떨어진다.
  • 변동 우선순위 알고리즘 - 일정 시간마다 우선순위가 변한다. 일정 시간마다 우선순위를 새로 계산하고 반영하기 때문에 효율적인 운영이 가능하다.

4.7.2 우선순위 스케줄링의 평가

• 공평성을 위배하고 아사 현상을 일으킨다는 것이 문제이다.
• 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성이 떨어뜨린다.

4.8 다단계 큐 스케줄링

• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위이 큐에 삽입된다.
• 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정된다. 고정형 우선순위를 사용하며, 상단의 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.
• 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식이다. 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있다.
• 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다. → 우선순위가 높은 프로세스 때문에 낮은 프로세스의 작업이 연기되는 문제가 생긴다. → 이를 해결한 것이 다단계 피드백 큐 스케줄링이다.

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

• 다단계 큐 스케줄링과 비슷하지만 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 우선순위가 1 낮아진다. → 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
• 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.
• 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정한다.
• 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작한다.
• 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예이다.