CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리 장치이다.
프로그램이 시작되어 메모리에 올라가면 프로그램 카운터(Program Counter:PC) 라는 이름의 레지스터 가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있게 된다.
기계어 명령
기계어 명령은 크게 세 가지로 나뉜다.
- CPU 내에서 수행되는 명령
- 메모리 접근을 필요로 하는 명령
- 입출력을 동반하는 명령
CPU 내에서 수행되는 명령
Add 명령어
CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령어
메모리 접근을 필요로 하는 명령
Load 명령어
메모리에 있는 데이터를 CPU로 읽어들이는 명령어
Store 명령어
CPU에서 계산된 결괏값을 메모리에 저장하는 명령어
프로그램의 수행
프로그램의 수행은 서로 다른 두 단계의 조합으로 이루어진다.
- CPU 버스트(burst):
사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계 - I/O 버스트:
I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계이다.
프로세스
프로세스는 크게 두 가지로 나뉜다.
I/O 바운드 프로세스
I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
CPU 바운드 프로세스
I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스를 말한다.
CPU 스케줄링이 필요한 이유?
→ 시분할 시스템에서는 CPU버스트가 균일하지 않은 다양한 프로그램들이 공존하므로 효율적인 CPU 스케줄링 기법이 반드시 필요하다.
1. CPU 스케줄러
준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드이다.
CPU 스케줄링이 필요한 경우
- 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
- 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
- I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
- CPU에서 실행 상태에 있는 프로세스가 종료되는 경우
CPU 스케줄링 방식
두 가지 방식이 있다.
- 비선점형(nonpreemptive) 방식
- 선저형(preemptive) 방식
비선점형 방식
CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
선점형 방식
프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법
2. 디스패처
CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고나면,
선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다.
새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처(dispatcher)라고 한다.
디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고,
새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.
디스패처 지연시간(dispatcher latency)
디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간
디스패처 지연시간의 대부분은 문맥교환 오버헤드에 해당된다.
3. 스케줄링의 성능 평가
스케줄링의 성능을 평가하는 지표에는 크게 두 가지로 나누어 볼 수 있다.
- 시스템 관점의 지표
- 사용자 관점의 지표
시스템 관점의 지표
CPU 이용률과 처리량
CPU 이용률
전체시간 중에서 CPU가 일을 한 시간의 비율을 나타낸다.
CPU가 일을 하지 않고 휴면 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표가 된다.
처리량
주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지를 나타낸다.
사용자 관점의 지표
소요시간, 대기시간, 응답시간 등 기다린 시간과 관련된 지표들
소요시간
프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린시간,
준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합을 뜻한다.대기시간
CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합을 뜻한다.
응답시간
프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
4. 스케줄링 알고리즘
(1) 선입선출 스케줄링
선입선출(First-Come First-Served: FCFS) 스케줄링은 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식을 말한다.
(2) 최단작업 우선 스케줄링
최단작업 우선(Shortest-Job First: SJF) 스케줄링 알고리즘은 CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.
SRTF(Shortest Remaining Time First) : SJF의 선점형 구현 방식
(3) 우선순위 스케줄링
우선순위 스케줄링(priority scheduling)이란 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말한다.
노화(aging) 기법 을 사용해 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 높은 우선순위가 되어 CPU를 할당 받을 수 있게 해주는 방법이다.
(4) 라운드 로빈 스케줄링
라운드 로빈 스케줄링(Round Robin Shceduling)은 지금까지 소개한 스케줄링 방식과 달리 시분할 시스템의 성질을 가장 잘 이용한 새로운 의미의 스케주링 방식이다.
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정시간으로 제한되며,
이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다.
할당시간(time quantum)
각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
(5) 멀티레벨 큐
멀티레벨 큐(multi-level queue)란 준비 큐를 여러 개로 분할 해 관리하는 스케줄링 기법,
⇒ 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 서는 것
(6) 멀티레벨 피드백 큐
멀티레벨 피드백 큐(Multilevel Feedback Queue)는 CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나,
프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
멀티레벨 피드백 큐를 정의하는 요소
- 큐의 수
- 각 큐의 스케줄링 알고리즘
- 프로세스를 상위 큐로 승격시키는 기준
- 프로세스를 하위 큐로 강등시키는 기준
- 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준
(7) 다중처리기 스케줄링
다중처리기 시스템
CPU가 여러 개인 시스템
다중처리기 스케줄링(multiple-processor scheduling)에서는 이와 같은 현상을 방지하기 위해 각 CPU별 부하가 적절히 분산되도록 하는 부하 균형(load balancing) 메커니즘을 필요로 한다.
다중처리기 스케줄링의 방식은 두 가지로 나누어 볼 수 있다.
- 대칭형 다중처리
- 비대칭형 다중처리
(8) 실시간 스케줄링
실시간 시스템에는 두 가지로 나누어 볼 수 있다.
- 경성 실시간 시스템
- 연성 실시간 시스템
5. 스케줄링 알고리즘의 평가
스케줄링 알고리즘의 성능을 평가하는 방법으로는 3가지가 있다.
- 큐잉모델
- 시뮬레이션
- 구현 및 실측
큐잉모델
주로 아론가들이 수행하는 방식으로, 확률분포를 통해 프로세들의 도착률과 CPU 처리율을 입력값으로 주면 복잡한 수학적 계산을 통해 각종 성능지표인 CPU의 처리량, 프로세스의 평균 대기시간 등을 구하게 된다.
시뮬레이션
실제 시스템에 구현해 수행시켜보는 것이 아니라 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는지를 확인하는 방법이다.
구현 및 실측
이론가와 정반대인 구현가들이 수행할 수 있는 방식으로, 운영체제 커널의 소스 코드 중 CPU 스케줄링을 수행하는 코드를 수정해서 커널을 컴파일 한 후 시스템에 설치하는 과정을 필요로 한다.
그런 다음 동일한 프로그램을 원래의 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행시간을 측정하여 알고리즘의 성능을 평가한다.
