[운영체제] CPU 스케줄링

• CPU : 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치
• 프로그램 카운터(PC) : 레지스터의 일종으로 프로그램이 메모리에 올라가면 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있게 된다. CPU는 이 PC를 보고 기계어 명령을 수행한다.

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

① CPU 내에서 수행되는 명령

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

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

• Load 명령 : 메모리에 있는 데이터를 CPU로 읽어들이는 명령
• Store 명령 : CPU에서 계산된 결과값을 메모리에 저장하는 명령
• CPU 내에서 수행되는 명령보다는 아니지만 속도가 빠른 편

③ 입출력을 동반하는 명령

• 키보드로부터 입력을 받는다거나 컴퓨터에서 처리된 결과를 화면에 출력하는 등의 작업
• 대단히 오랜 시간이 소요되며, 컴퓨터 시스템에서는 이를 특권 명령으로 규정시켜 사용자 프로그램이 직접 수행하지 못하도록 하였다. (입출력 서비스가 필요하면 OS에 요청해야함)

• 사용자 프로그램이 수행되는 과정은 CPU 작업과 I/O 작업의 반복으로 구성된다.
• Add 명령이나 메모리 접근 명령은 사용자 프로그램이 직접 CPU를 가지고 수행하는 명령이라 빠르지만, 프로그램이 수행되는 도중 I/O를 요청하면 CPU의 제어권이 OS 커널로 넘어갈 뿐 아니라 상대적으로 매우 느린 입출력 장치의 접근이 필요해진다.
• 위 그림처럼 프로그램의 수행은 사용자 프로그램이 CPU를 가지고 빠른 명령을 수행하는 일련의 단계인 CPU 버스트(burst, 주기)와 I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 I/O 버스트의 조합으로 이루어진다.
• 프로그램마다 CPU 버스트와 I/O 버스트의 비율이 균일하지 않은데, 입출력 작업 없이 CPU 버스트가 길게 나타나는 프로세스를 CPU 바운드 프로세스라고 하고 I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스를 I/O 바운드 프로세스라고 한다.
• CPU 버스트가 짧은 프로세스는 대부분 대화형 작업으로 사용자와 인터랙션해가며 프로그램을 수행시킨다. 이러한 작업을 수행하는 프로세스는 대화형 작업이므로 사용자에 대한 빠른 응답이 중요하기에 CPU의 빠른 서비스를 요구한다.
• 따라서 CPU 스케줄링을 할 때 CPU 버스트가 짧은 프로세스(I/O 바운드 프로세스)에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다. 이러한 스케줄링은 대화형 프로세스의 빠른 응답성 제공 외에도 I/O 장치의 효용성을 높이는 효과를 가져온다.

---

1. CPU 스케줄러

• CPU 스케줄러 : 준비 상태의 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 OS의 코드

※ CPU 스케줄러가 필요한 경우

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

※ CPU 스케줄링 방식의 종류

▷ 비선점형(nonpreemptive) 방식

• CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 빼앗기지 않는 방식

▷ 선점형(preemptive) 방식

• 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 방식
• 빼앗는 방법에는 할당시간을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적임.

---

2. 디스패처

• 디스패처(dispatcher) : 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있게 환경설정하는 OS의 코드
• 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에 CPU 권한을 넘기는 과정을 수행한다.
• 새로운 프로세스의 문맥을 복원하고 시스템 상태를 사용자모드로 전환하여 사용자 프로그램에 CPU 제어권을 넘기면 사용자 프로그램은 복원된 문맥 중 PC로부터 현재 어디부터 수행하면 될지 주소를 찾을 수 있다.
• 디스패처 지연시간 : 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에 CPU를 전달하기까지 걸리는 시간, 대부분이 컨텍스트 스위칭 오버헤드에 해당된다.

---

3. 스케줄링의 성능 평가

• 시스템 관점의 지표 : CPU 이용률과 처리량
• 사용자 관점의 지표 : 소요시간, 대기시간, 응답시간 (기다린 시간과 관련된 지표)

① CPU 이용률 (CPU utilization)

• 전체 시간 중 CPU가 일을 한 시간의 비율
• CPU가 일을 하지 않고 휴면(idle) 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표 중 하나

② 처리량 (throughput)

• 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지 (CPU 버스트를 완료한 프로세스의 개수) 나타낸다.
• 여러 프로세스가 CPU를 기다리고 있는 상황에서 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 중요하다.

③ 소요시간 (turnaround time)

• 프로세스가 CPU를 요청한 시점부터 자신이 원하는만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
• 준비큐에서 기다린 시간 + 실제로 CPU를 사용한 시간
• 주의해야 할 것은 해당 CPU 버스트가 완료될 때까지 소요된 시간이지 프로그램이 시작하여 종료되는 시간과는 관련이 없다.

④ 대기시간(waiting time)

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

⑤ 응답시간 (response time)

• 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
• 타이머 인터럽트가 빈번히 발생할수록 이 응답시간은 줄어들게 된다. (각 프로세스가 CPU를 연속으로 사용할 수 있는 시간이 짧아짐)
• 대화형 시스템에 적합한 성능 척도이다. (사용자 입장에서 가장 중요한 성능 척도)

---

4. 스케줄링 알고리즘

※ 선입선출 스케줄링(First-Come First-Served, FCFS)

• 선입선출 스케줄링 : 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
• 먼저 도착한 프로세스의 상태에 따라 평균 대기시간이 크게 달라진다. CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어지는 반면, CPU 버스트가 짧은 프로세스가 먼저 도착한다면 평균 대기시간이 짧아진다.

프로세스	CPU 버스트 시간
P1	12
P2	3
P3	3

• 만일 준비 큐 도착 순서가 P1, P2, P3라고 가정하면(간발의 차이) 평균 대기시간은 다음과 같다.

대기시간 : 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

• 이렇게 도착 순서에 따라 평균 대기시간이 크게 차이가 남을 알 수 있다.
• 콘보이 현상(Convoy effect) : 전자의 경우처럼 CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상, FCFS 스케줄링의 대표적인 단점으로 꼽힌다.

 

※ 최단작업 우선 스케줄링(Shortest-Job First, SJF)

• 최단작업 우선 스케줄링 : CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식, 평균 대기시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다.
• 비선점형 방식과 선점형 방식으로 나눌 수 있는데, 비선점형 방식은 프로세스가 일단 CPU 제어권을 획득하면 그 프로세스가 자진 반납하기 전까지는 CPU를 빼앗지 않고, 선점형 방식은 CPU 버스트가 가장 짧은 프로세스에 CPU를 할당했다고 하더라도 이후에 CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼았는다. 이러한 SJF의 선점형 구현 방식을 SRTF(Shortest Remaining Time First)라고 한다.

▷ 예시

프로세스	도착 시간	CPU 버스트 시간
P1	0	7
P2	1	8
P3	2	3
P4	3	6

 

비선점형 SJF

대기시간 : P1 = 0, P2 = 7, P3 = 15, P4 = 9
평균 대기시간 : (0+7+15+9)/4 = 7.75

선점형 SJF

대기시간 : P1 = 9, P2 = 0, P3 = 15, P4 = 2
평균 대기시간 : (9+0+15+2)/4 = 6.5

• 위의 예시에서 볼 수 있듯, 선점형 방식이 평균 대기시간을 가장 많이 줄일 수 있는 방식이다.
• SJF 스케줄링 기법이 현실적으로 어려운 점은 CPU 버스트 시간을 미리 알 수 없다는 점이다. 이를 타개하기 위해 예측값을 사용한다. 이 예측값은 과거의 CPU 버스트 시간을 통해 이루어진다. (최근의 CPU 버스트 시간의 가중치를 과거의 CPU 버스트 시간보다 높인다.)
• SJF 알고리즘이 평균 대기시간을 최소화하는 알고리즘이기는 하나 이것이 마냥 좋다고만 할 수는 없다. CPU 버스트가 짧으 프로세스에만 CPU를 할당하다보면 CPU 버스트가 긴 프로세스는 준비 큐에서 무한정 기다려야 하는 문제가 발생할 수 있다. 이를 기아 현상(starvation)이라고 하며 SJF 알고리즘의 심각한 문제점이다.

 

※ 우선순위 스케줄링(Priority Scheduling)

• 우선순위 스케줄링 : 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스ㅇ게 CPU 할당
• 우선순위값이 따로 있으며 이 값이 작을수록 높은 우선순위를 가진다. CPU 버스트 시간을 우선순위값으로 정의하면 SJF 알고리즘과 동일한 의미를 갖는다.
• 이것 또한 선점형 방식과 비선점형 방식으로 나눌 수 있다.
• 문제점 또한 SJF 알고리즘에서 보았던 것처럼 기아 현상을 들 수 있다. 우선순위가 계속해서 높은 프로세스들이 준비 큐로 들어오면 우선순위가 낮은 기존의 프로세스들은 자꾸 뒤로 밀리므로, 이를 해결하기 위해 노화 기법(aging)을 사용한다.
• 노화 기법 : OS가 준비 큐를 지속적으로 체크하여 오래 기다리는 프로세스의 우선순위를 점진적으로 높여준다.

 

※ 라운드 로빈 스케줄링(Round Robin Scheduling)

• 라운드 로빈 스케줄링 : 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한된다. 이 시간이 경과했을 경우 해당 프로세스로부터 CPU를 회수해 준비 큐에 있는 다른 프로세스에 CPU를 할당한다.

할당 시간(time quantum) : 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대 시간

• 할당시간이 너무 길면 FCFS 스케줄링 기법과 다를 것이 없게 된다.
  할당시간이 너무 짧다면 CPU를 사용하는 프로세스가 빈번히 교체되어 컨텍스트 스위칭의 overhead가 커진다.
• 할당시간이 만료되어 CPU를 회수하는 방법은 타이머 인터럽트를 사용하며, CPU 버스트 시간이 할당 시간보다 짧다면 버스트 시간만큼 CPU 사용 후 스스로 반납하면 된다.
• 라운드 로빈 스케줄링의 기본적인 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있음과 동시에 CPU 버스트 시간이 긴 프로세스도 불이익을 당하지 않는 것이다. → 합리적이라고 할 수 있음

 

※ 멀티레벨 큐 (multi-level queue)

• 멀티레벨 큐 : 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법, 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아닌 여러 줄로 서게 된다.
• 어떤 줄의 프로세스를 우선적으로 스케줄링할 것인지와 프로세스가 도착했을 때 어느 줄에 세워야 할지 결정하는 메커니즘이 요구된다.

• 대화형 작업을 담기 위한 전위 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할하여 운영
• 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하고 후위 큐에서는 응답시간이 큰 의미를 가지지 않기에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄인다.

 

★ 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링

▷ 고정 우선순위 방식 

• 우선순위가 높은 큐를 먼저 서비스하고 높은 큐가 비어있을 때만 우선순위가 낮은 큐 서비스
• 전위 큐가 우선순위가 높고 후위 큐는 우선순위가 낮아 전위 큐가 비어있을 때만 CPU가 할당될 수 있다.

▷ 타임 슬라이스 방식

• 큐의 기아 현상을 해소할 수 있음
• 각 큐에 CPU 시간을 적절한 비율로 할당하는데, 전체 CPU 시간 중 전위 큐에는 80, 후위 큐에는 20을 할당하는 식이다.

 

※ 멀티레벨 피드백 큐 (Multilevel Feedback Queue)

• CPU를 기다리는 프로세스를 여러 큐에 줄세운다는 점에서 멀티레벨 큐와 비슷하나, 결정적으로 다른 점은 프로세스가 속한 큐에서 다른 큐로 이동할 수 있다는 점이다.
• 프로세스가 준비 큐에 도달하면 우선순위가 가장 높은 큐(quantum = 8)에 줄을 서고, CPU 사용시간이 짧은 대화형 프로세스들은 우선순위가 가장 높은 큐에서 빠르게 서비스를 받고 작업을 완료할 수 있다.
• 그러나, CPU 버스트 기간이 긴 프로세스는 가장 우선순위가 높은 큐에서 CPU를 사용하고 작업을 완료할 수 없으므로 할당시간이 16인 하위 큐로 내려가 줄을 서게 된다. 이후에도 작업이 완료되지 않으면 이 프로세스를 CPU를 오래 사용하는 계산 위주의 프로세스로 간주하고 최하위 큐로 이동되어 FCFS 스케줄링을 적용받는다.
• 이러한 방식은 라운드 로빈에서 한 층 더 발달한 방식이라고 볼 수 있다.

 

※ 다중처리기 스케줄링(Multi-processor system)

• 다중처리기 시스템 : CPU가 여러 개인 시스템
• 각 CPU 별로 줄을 세우는 경우 일부 CPU에 작업이 편중되는 현상이 발생할 수 있고, 이를 방지하기 위해 각 CPU별 부하가 적절히 분산되도록 하는 부하균형 매커니즘을 필요로 한다.
• 대칭형 다중처리 : 각 CPU가 각자 알아서 스케줄링 결정하는 방식, 비대칭형 다중처리 : 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식

 

※ 실시간 스케줄링

• 실시간 시스템에서는 각 작업마다 주어진 데드라인이 있고, 이 데드라인 안에 반드시 작업을 처리해야 한다.
• 경성 실시간 시스템 : 미사일 발사, 원자로 제어 등 (시간을 정확히 지켜야 함)
• 연성 실시간 시스템 : 데드라인이 존재하기는 하나 이를 지키지 못했다고 해서 위험한 상황 X

---

5. 스케줄링 알고리즘의 평가

• 큐잉모델, 시뮬레이션, 구현 및 실측 방식이 존재한다.