6. CPU 스케줄링

CPU 스케줄링

CPU란?

→ CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치임.

• 프로그램이 시작되어 메모리에 올라가면 프로그램 카운터 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있음.
• CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행.
• CPU는 일반적으로 한 시스템 내의 하나씩 밖에 없음 → 여러 프로그램이 동시에 수행되는 시분할 환경에서 매우 효율적으로 관리되어야함.

 

프로그램 실행과 관련된 기계여 명령어

1. CPU 내에서 수행되는 기계어 명령.
2. 메모리 접근을 필요로 하는 기계어 명령.
3. 입출력을 동반하는 기계어 명령.

 

CPU 내에서 수행되는 명령

→ Add 명령.

→ 일반 명령임.

• CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저정하는 명령.
• CPU 내에서만 수행되므로 명령의 수행 속도가 매우 빠름.

 

메모리 접근을 수행하는 명령

→ Load 명령, Store 명령

→ CPU 내에서 수행되는 명령보다 시간이 오래 소요됨 but 비교적 짧은 시간에 수행할 수 있는 명령에 해당됨.

→ 일반 명령임.

Load 명령

• 메모리에 있는 데이터를 CPU로 읽어들이는 명령.

Store 명령

• CPU에서 계산된 결과값을 메모리에게 저장하는 명령.

 

입출력 작업이 필요한 경우

ex) 키보드로부터 입력을 받는다든지 컴퓨터에서 처리된 결과를 화면에 출력, 디스크에서 파일 데이터 읽어오기, 컴퓨터에서 처리된 결과 디스크에 파일 형태로 저장

→ 입출력을 수반하는 명령은 CPU나 메모리 접근 명령에 비해 대단히 오랜 시간 소요됨.

• 컴퓨터 시스템에서는 모든 입출력 명령을 특권명령으로 규정.
• 사용자 프로그램이 직접 수행할 수 없도록 하고 운영체제를 통해 서비스를 대행하도록 함.

 

사용자 프로그램이 수행되는 과정

1. CPU 작업
2. I/O 작업

이 2가지 작업의 반복으로 구성됨.

→ 일종의 사이클처럼 CPU와 I/O 장치라는 상이한 자원을 번갈아 사용하면서 프로그램이 수행됨.

• 레지스터 간의 연산으로 구성되는 ADD 명령이나 메로리를 접근하는 Load 명령, Store 명령 등은 사용자 프로그램이 직접 CPU를 가지고 수행하는 비교적 빠른 명령.
• I/O를 요청하는 것은 CPU의 제어권이 운영체제 커널로 넘어갈 뿐 아니라 상대적으로 매우 느린 입출력 장치의 접근이 필요.

프로그램의 수행은 서로 다른 두 단계의 조합으로 이루어짐.!!!

1. 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계 == CPU 버스트(burst)
2. I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계 == I/O 버스트(burst)

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

CPU 버스트, I/O 버스트 차지하는 비율

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

• 어떤 프로세스 I/O 버스트 빈번해 CPU 버스트가 매우 짧음.
• 다른 프로세스 I/O를 거의 하지 않아 CPU 버스트가 매우 길게 나타남.

이 기준으로 프로세스를 크게 I/O 바운드 프로세스, CPU 바운드 프로세스로 나누어볼 수 있음.

 

I/O 바운드 프로세스, CPU 바운드 프로세스

• I/O 바운드 프로세스 == I/O 요청이 빈번해 CPU 버스트가 짤게 나타나는 프로세스
  • I/O 바운드 프로세스는 주로 사용자로부터 인터랙션(interaction)을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램(interactive program)에 해당.
• CPU 바운드 프로세스 == I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스.
  • CPU 바운드 프로세스는 프로세스 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램이 해당.

프로그램이 수행되는 구조를 보면 I/O 바운드 프로세스는 짧은 CPU 버스트를 많이 가지고 있는 반면, CPU 바운드 프로세스는 소수의 긴 CPU 버스트로 구성됨.

 

CPU 스케줄링

→ 이와 같이 CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 CPU 스케줄링이 필요한 것임.

• 우리가 사용하는 시분할 시스템에서는 이와 같이 CPU 버스트가 균일하지 않은 다양한 프로그램이 공존하므로 효율적인 CPU 스케줄링 기법이 반드시 필요.

컴퓨터 시스템 내에서 수행되는 프로세스들의 CPU 버스트 분석 ㄱ

→ 대부분의 경우 짧은 CPU 버스트를 가지며, 극히 일부분만 긴 CPU 버스트를 가짐.

• 프로세스들의 CPU 버스트 분포는 다수의 짧은 CPU 버스트와 소수의 긴 CPU 버스트로 구성됨. → CPU를 한 번에 오래 사용하기보다 잠깐 사용하고 I/O 작업을 수행하는 프로세스들이 많다는 것.
• CPU 버스트가 짧은 프로세스는 대부분 대화혈 작업으로 사용자와 인터랙션을 해가며 프로그램 수행 → 사용자에게 입력을 받아 CPU 연산을 수행하고 그 결과를 다시 출력하는 작업 수행. → 이 작업을 수행하는 프로세스는 CPU의 빠른 서비스 필요 → CPU 스케줄링을 할 때 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링 필요.

즉 CPU 스케줄링 시 I/O 바운드 프로세스의 우선순위를 높여주는 것이 바람직하다는 의미가 됨.

이러한 스케줄링은 대화형 프로세스의 빠른 응답성 제공 외에 I/O 장치 효율성을 높이는 효과도 얻을 수 있음. I/O 바운드 프로세스에게 먼저 CPU를 할당할 경우 CPU를 잠깐만 사용한 후 곧바로 I/O 작업을 수행할 수 있으므로 I/O 장치의 이용률이 높아지기 때문.

 

CPU 바운드 프로세스에게 먼저 CPU 할당한다면?

→ 그 프로세스가 CPU를 다 사용할 때까지 I/O 바운드 프로세스는 응답시간이 길어질 뿐만 아니라 해당 I/O 장치도 그 시간 동안 작업을 수행하지 않는 휴면 상태가 되기 때문에 비효율적임

 

1. CPU 스케줄러

→ 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드가 CPU 스케줄러임.

프로세스 CPU 할당 받음 → 기계어 명령을 수행 → 타이머 인터럽트 발생 → CPU 스케줄러 호출.

• CPU 스케줄러는 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당하게 됨.

 

이 밖에도 CPU 스케줄링이 필요한 경우 더 있음

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

 

스케줄링 방식

1. 비선점형(nonpreemptive) 방식
   1. CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법을 말함.
2. 선점형(preemptive) 방식
   1. 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법.
   2. CPU를 빼앗는 방법으로는 할당시간(time quantum)을 부여한 후 타이머 인터럽트를 발생시키는 것이 대표적인 방법.

위에서 말한 4가지

→ 1번, 4번 비선점형 스케줄링의 예

→ 2, 3번 섬점형 스케줄링 방식

• 3번은 I/O 작업이 완료된 프로세스가 인터럽트 당한 프로세스 보다 우선순위가 높아, 인터럽트 처리 후 직전에 수행되던 프로세스에게 CPU를 다시 할당 하는 것이 아니라 문맥교환을 통해 I/O가 완료된 프로세스에게 CPU를 할당하는 경우

 

2. 디스패처

→ CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고나면 선택된 프로세스에게 실제로 CPU를 이양하는 작업 필요!

새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처(dispatcher)라고 함.

 

디스패처 상세 설명

• 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정 수행.

새로운 프로세스의 문맥 복원 후 시스템의 상태를 사용자 모드로 전환해 사용자 프로그램에게 CPU의 제어권 넘김 → 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소 찾음.

 

디스패치 지연시간

디스패처가 하나의 프로세스를 정지 시키고 다른 프로세스에게 CPU를 전달하기 까지 걸리는 시간을 디스패치 지연시간(dispatch latency)라고 함. 지연시간의 대부분은 문맥교환 오버헤드에 해당

 

3. 스케줄링의 성능 평가

→ 스케줄링 기법의 성능을 평가하기 위해 여러 지표들이 사용됨.

지표들을 크게 시스템 관점의 지표와 사용자 관점의 지표로 나누어 볼 수 있음

 

시스템 관점의 지표

→ CPU 이용률과 처리량이 있음.

사용자 관점의 지표

→ 소요시간, 대기시간, 응답시간 등 기다린 시간과 관련된 지표.

 

1. CPU 이용률

• 전체 시간 중에서 CPU가 일을 한 시간의 비율을 나타냄
• CPU는 시스템에 하나만 존재하는 고비용의 자원 → CPU의 이용률은 시스템 전체의 성능과 밀접하게 관련됨.

CPU가 일을 하지 않고 휴면 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표

 

2. 처리량(throughput)

• 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝 마쳤는지(CPU 버스트를 완료한 프로세스의 개수)를 나타냄.

즉, CPU의 서비스를 원하는 프로세스 중 몇 개가 원하는 만큼의 CPU를 사용하고 이번 CPU 버스트를 끝내어 준비 큐를 떠났는지 측정하는 것이 처리량의 개념

여러 프로세스가 CPU를 기다리고 있는 상황에서 주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스 에게 우선적으로 CPU를 할당하는 것이 유리.

 

3. 소요시간(turnaround time)

• 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간.

즉, 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합.

주의할 점

→ CPU 버스타가 완료될 때까지 소요된 시간으로, 프로그램이 시작해 종료하는 데까지 걸리는 시간 아님!!! 소요시간은 CPU 버스트이 수만큼 각각 별도로 측정됨.

ex) CPU를 사용 → I/O 연산을 위해 CPU를 자진 반납 → CPU를 사용하기 위해 준비큐에 들어왔을 때부터 CPU를 자진 반납하기까지 걸린 시간이 소요시간이 됨.

 

4. 대기 시간(waiting time)

• CPU 버스트 시간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합.

시분할 시스템에서 타이머를 사용하는데 하나의 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 제한 → 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있음.

쉽게 말해서

대기시간이란 CPU버스트가 끝나기까지 준비 큐에서 기다린 시간의 합.

 

5. 응답시간(response time)

• 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간을 뜻함.

대기 시간 → 준비 큐에 들어온 직후부터 이번 CPU 버스트가 끝날 때까지 준비 큐에서 기다린 시간의 합

응답 시간 → 준비 큐에 들어온 직후부터 첫 번째 CPU를 얻기까지 걸린 시간.

 

타이머 인터럽트 빈번히 발생 → 각 프로세스 CPU를 연속적으로 사용할 수 있는 시간 짧아짐 → 처음 CPU를 얻기까지 걸리는 시간은 줄어들게 되므로 응답시간 향상

대화형 시스템에 적합한 성능 척도로서 사용자 입장에서 가장 중요한 성능 척도

 

비유를 통해서 성능 척도들의 의미 생각해보쟈

중국집에 주방장, 손님 있음

1. 이용률, 처리량 → 중국집 입장에서에서의 척도
2. 소요시간, 대기시간, 응답시간 → 손님 입장의 척도

이용률 → 전체 시간 중 주방장이 일한 시간의 비율

처리량 → 주방장이 주어진 시간 동안 몇 명의 손님에게 요리를 만들어주었는지

중국집 입장에서는 주방장을 고용해서 가능한 많은 일을 시키는 것이 좋으므로 이용률이 높은 것을 선호 또한 손님에게 요리를 판매하는 것이 이익이므로 처리량이 많은 것이 중요한 지표가 됨.

 

소요 시간 → 손님이 중국집에 들어와서 주문한 음식을 다 먹고 나가기까지 소요된 총 시간.

대기 시간 → 음식을 먹은 시간을 제외한 순수하게 기다린 시간을 의미.

if 음식이 조금씩 여러 번에 걸쳐 나왔다면

음식을 먹은 시간을 제외하고 각각의 음식이 나오기까지 기다린 시간을 합한 것.

응답 시간 → 최초의 읨식이 나오기까지 기다린 시간.

 

4. 스케줄링 알고리즘

→ 다양한 CPU 스케줄링 알고리즘을 살펴보자

1. 선입선출 스케줄링

• 선입선출(First-Come First-Serverd: FCFS) == (First-In First-out) 스케줄링
  • 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식.
  • CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않는다.

 

비효율적인 부분

→ CPU 버스트가 긴 프로세스 하나가 CPU 버스트가 짧은 프로세스 여러 개보다 먼저 도착했다고 가정.

• CPU를 잠깐만 사용하면 준비 큐를 떠나 I/O 작업을 수행할 수 있는 다수의 프로세스들이 앞의 긴 작업 하나 때문에 계속 기다려야 하는 상황 발생 → 평균 대기 시간이 길어지게 됨.
• CPU 버스트 긴 프로세스 하나 때문에 대기시간은 물론 I/O 장치들의 이용률까지도 동반 하락하게 됨.

FCPS 스케줄링 알고리즘 → 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라짐.

→ CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균대기시간이 길어지는 반면, CPU 버스트가 짧은 프로세스가 먼저 도착하게 되면 평균 대기시간이 짧아지게 됨.

 

계산을 해보면서 하쟈

프로세스 도착 순서 P1, P2, P3 모두 시각 0에 도착했으나 간발의 차이로 P1이 제일 먼저 그리고 P3이 제일 나중에 도착했다고 가정

P1 : 0 ~ 12, P2 : 12 ~ 15, P3: 15 ~ 18

대기시간 : P1 = 0, P2 =12, P3 = 15

평균 대기 시간 : (0 + 12 + 15)/3 = 9

 

프로세스 도착 순서 바꿔보기

P2, P3, P1

대기시간 : P1 = 6, P2 = 0, P3 = 3

평균 대기 시간 : (6 + 0 + 3)/3 = 3

CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기달야 하는 현상 == 콘보이 현상(Convoy effect)

FCFS 스케줄링의 대표적인 단점

 

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

• SJF 비선점형 스케줄링

P1 도착 0~14 사이에

p2,p3,p4 도착

p2 = 14 - 4 = 10 + (p3 CPU 버스트 시간) = 2 == 12

p3 = 14 - 8(자기 도착 시각) = 6

p4 = 14 - 10 = 4 + (p3 cpu 버스트 2) + (p2 CPU 버스트 8) =14

평균 대기 시간 = (0+12+6+14)/4 = 8

 

• SJF 선점형 스케줄링

p1 = 8 + 2 + 8 (p2, p3, p4 CPU 버스트 시간) = 18

p2 = 2 (p3 CPU 버스트 시간)

p3 = 0

p4 = 4 (p4 의 도착 시간 부터 p2의 프로세스 시간)

평균 대기 시간 = (18 + 2 + 0 + 4)/4 = 6

 

SJF 스케줄링 기법의 구현에서 현실적으로 어려운 부분은 프로세스의 CPU 버스트 시간을 미리 알 수 없다는 점.

→ 예측을 통해 버스트 시간을 구한 후 예측치가 가장 짧은 프로세스에게 CPU를 할당하게 됨.

 

CPU 버스트 시간의 예측

• 과거의 CPU 버스트 시간의 예측은 과거의 CPU 버스트 시간을 통해 이루어지는데 다음과 같은 방법 사용.

t_n과 T_n ⇒ 각각 n번째 실제 CPU 버스트 시간과 n번째 CPU 버스트의 예측 시간을 뜻함

a ⇒ 0과 1 사이의 상수로 두 요소를 어느 정도씩 반영할지 조절하는 매개변수

a = 0인 경우 T_n+1 = T_n이 되어 고정된 값이 예측값으로 계속 사용됨.

a = 1인 경우 T_n+1 = t_n이 되어 바로 전에 사용한 CPU 버스트 시간을 예측값으로 사용하게 됨.

 

a값을 0과 1 사이의 값으로 세팅하면 n번째 실제 CPU 버스트 시간과 n번째 버스트 시간의 예측값을 적당히 가중 평균해 n+1 번째 CPU 버스트 시간을 예측하게 됨.

 

이를 다른 각도에서 보면 과거의 CPU 버스트 시간들을 통해 미래의 CPU 버스트 시간을 예측하게 되며, 최근의 CPU 버스트 시간일수록 오래전의 CPU 버스트 시간에 비해 가중치를 높이는 방식이 됨.

 

위 식에서 n대신 n-1을 대입한 식 T_n = at_n-1 + (1-a)T_n-1을 식의 T_n 자리에 넣어서 풀고, 다시 n 대신 n-2를 대입한 식 T_n-1 = at_n-2 + (1 - a)T_n-2를 식의 T_n-1자리에 넣어서 푸는 방식을 반복하면 아래와 같은 식 얻어짐.

 

$$ T_{n+1} = at_n + (1-a)at_{n-1} + +(1-a)^{\int}at_{n-\int}+ $$

 

위 식에서 a와 (1-ㅁ)는 모두 0과 1 사이의 값이므로 이들이 계속 곱해질수록 그 값은 더욱 작아지게됨. 따라서 t_n-1의 계수가 t_n의 계수보다 작은 값이 되고, t_n-2의 계수는 t_n-1의 계수보다 작은 값이 된다. 즉 과거를 통해 미래를 예측하는 데 있어서 더 오래된 과거일수록 그 영향력이 적어지도록 반영하는 방식인 것임.

 

SJF 알고리즘 평균 대기시간을 최소화하는 알고리즘이기는 하지만 시스템에서 평균을 줄이는 것이 항상 좋은 방식이라고는 말할 수 없다.!!!

 

CPU버스터가 짧은 프로세스에게만 CPU를 할당하는 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야하는 문제 발생

 

ex) 프로세스 A의 CPU 버스트 시간이 1000인데 현재 준비 큐에 CPU 버스트가 10,20,30인 프로세스가 있다고 가정. → 프로세스 A는 위 프로세스가 모두 CPU를 사용한 후에 CPU를 할당받을 수 있음.

• CPU 버스트가 10,20인 프로세스가 CPU 사용을 끝마치고 현재 CPU 버스트가 30인 프로세스가 CPU를 사용하고 있는 상황이라고 할 때, 프로세스 A는 이 프로세스만 CPU 사용을 마치면 마침내 CPU를 할당 받을 수 있게됨.
• BUT CPU 버스트가 30인 프로세스 수행 끝나기 직전 CPU 버스트 100, 200, 300이 들어오면 프로세스 A 보다 CPU 버스트가 짧기 때문에 프로세스 A는 또다시 기다려야함.
• 이렇게 되면 프로세스 A가 영원히 CPU 할당 못 받을 수도 있음 == 기아(starvartion) 현상
• 이건 심각한 문제점임.

 

3. 우선순위 스케줄링

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

우선순위

→ 우선순위값(priority number)을 통해 표시, 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정함.

 

우선순위 결정 방식은 여러가지

1. CPU 버스트 시간을 우선순위값 정의
   1. 우선순위 스케줄링은 SJF 알고리즘과 동일한 의미를 가짐.
2. 시스템과 관련된 중요한 작업을 수행하는 프로세스의 우선순위를 높게 부여하면 이러한 프로세스가 CPU를 빨리 할당받을 수 있게 가능.

 

우선순위 스케줄링 비선점형 방식, 선점형 방식 각각 구현 가능

1. 선점형 == CPU에서 수행 중인 프로세스 보다 우선순위가 높은 프로세스가 도착하여 CPU를 선점해서 새롭게 도착한 프로세스에게 할당할 경우 선점형
2. 비선점형 == CPU를 얻었으면 비록 우선순위가 더 높은 프로세스가 도착하더라도 CPU를 자진 반납하기 전까지 선점하지 않음.

 

문제점 == 기아 현상 발생 가능.

→ 높은 프로세스가 계속 도착하는 상황에서 우선순위가 낮은 프로세스는 CPU는 얻지 못한 채 계속 기다려야할 수 있음.

 

문제점 해결 == 노화(aging) 기법

⇒ 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법.

일상생활에서 흔히 볼 수 있는 경로사상이 컴퓨터의 세계에 반영된 형태.

→ 버스, 지하철 자리 양보 == 프로세스가 오래 기다려서 나이를 먹게 되면 우선순위를 높여 CPU 먼저 할당.