- 프로그램 실행과 관련된 기계어 명령은 다음과 같이 나눌 수 있다.
CPU 내에서 수행되는 명령
ex) Add 명령 : CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령
- CPU 내에서만 수행되기 때문에 속도가 매우 빠르다.
메모리 접근을 필요로 하는 명령
ex) Load 명령 : 메모리에 있는 데이터를 CPU로 읽어들이는 명령
Store 명령 : CPU에서 계산된 결괏값을 메모리에 저장하는 명령
- 1의 경우보다는 오랜 시간이 소요되지만, 비교적 짧은 시간에 수행 가능한 명령이다.입출력을 동반하는 명령
ex) 키보드 입력 받기, 모니터 출력하기, 디스크에서 파일을 읽어오거나 저장하기
- 1과 2에 비해 대단히 오랜 시간이 소요되며, 입출력 명령은 특권 명령이다. 즉, 사용자 프로그램이 직접 수행할 수 없고 운영체제를 통해 서비스를 대행하도록 하고 있음.
- 사용자 프로그램이 수행되는 과정은 CPU 작업과 I/O 작업의 반복으로 구성된다.
- CPU 버스트
- 사용자 프로그램이 직접 CPU를 가지고 빠른 명령을 수행하는 일련의 단계
- 프로그램이 I/O를 한 번 수행한 후 다음 번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 일련의 작업
- I/O 버스트
- I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
- I/O 작업 요청이 된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업
각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지는 않다. 이 비율을 기준으로 프로세스를 크게 CPU 바운드 프로세스 와 I/O 바운드 프로세스 로 나누어볼 수 있다.
- CPU 바운드 프로세스
- I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스 ex) 계산 위주의 프로그램
- 소수의 긴 CPU 버스트로 구성됨 - I/O 바운드 프로세스
- I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스 ex) 대화형 프로그램
- 짧은 CPU 버스트를 많이 가지고 있음
CPU 스케줄링은 이와 같이 CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 필요한 것이다.
컴퓨터 시스템 내에서 수행되는 프로세스들의 CPU 버스트를 분석해보면 대부분의 경우 짧은 CPU 버스트 를 가지며, 극히 일부분만 긴 CPU 버스트를 가진다.
짧은 CPU 버스트== CPU를 잠깐 사용하고 I/O 작업을 수행CPU 버스트가 짧은 프로세스== 대부분 대화형 작업(사용자와 인터랙션을 해가며 프로그램을 수행)
대화형 작업은 사용자에 대한 빠른 응답이 중요하기 때문에 이러한 작업을 수행하는 프로세스는 CPU의 빠른 서비스를 필요로 한다.
=> 따라서, CPU 스케줄링을 할 때 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할수 있도록 하는 스케줄링이 필요하다.
(= CPU 스케줄링 시 I/O 바운드 프로세스의 우선순위를 높여주는 것이 바람직)
=> 이러한 스케줄링을 통해서 대화형 프로세스의 빠른 응답성 제공 외에 I/O 장치 효율성을 높이는 효과도 얻을 수 있다.
1. CPU 스케줄러
CPU 스케줄러 : 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드
-
CPU 스케줄링이 필요한 경우들
(1) 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄(blocked) 상태로 바뀌는 경우
(2) 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
(3) I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
(4) CPU에서 실행 상태에 있는 프로세스가 종료되는 경우 -
CPU 스케줄링 방식
비선점형(nonpreemptive)
- CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
- (1) 과 (4)
선점형(preemptive)
- 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는(ex_할당시간 부여 후 타이머 인터럽트 발생시키기) 스케줄링 방법
- (2) 와 (3)
+ (3) 은 이번에 I/O 작업이 완료된 프로세스가 인터럽트 당한 프로세스보다 우선순위가 높아, 인터럽트 처리 후 직전에 수행되던 프로세스에게 CPU를 다시 할당하는 것이 아니라 문맥교환을 통해 I/O가 완료된 프로세스에게 CPU를 할당하는 경우가 해당된다.
2. 디스패처
디스패처(dispatcher) : 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.
- 디스패치 지연시간(dispatch latency)
디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간
3. 스케줄링의 성능 평가
- 시스템 관점의 지표
CPU 이용률(CPU utilization): 전체 시간 중에서 CPU가 일을 한 시간의 비율(휴면상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 목표)처리량(throughput): 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지(CPU 버스트를 완료한 프로세스의 개수)
- 사용자 관점의 지표
소요시간(!= 프로그램 시작~종료 시간)
- 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
- 준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간대기시간: CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
- 시분할 시스템에서는 일반적으로 타이머를 사용해서 하나의 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 제한한다.
- 따라서, 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다.응답시간: 프로세스가 준비 큐에 들어온 후 첫번째 CPU를 획득하기까지 기다린 시간
- 타이머 인터럽트가 빈번히 발생할수록, 준비 큐에 있는 프로세스들이 처음 CPU를 얻기까지 걸리는 시간은 줄어들게 되어 응답시간이 향상된다.
- 대화형 시스템에 적합한 성능 척도. 사용자 입장에서 가장 중요한 척도
4. 스케줄링 알고리즘
1) 선입선출(FCFS) 스케줄링 First-Come First-Served : FCFS
- 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
- CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않는다.
- 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라진다.
i ) CPU 버스트가 긴 프로세스가 먼저 도착 -> 평균 대기시간 길어짐
ii ) CPU 버스트가 짧은 프로세스가 먼저 도착 -> 평균 대기시간 짧아짐
- Convoy effect : CPU 버스트가 짧은 프로세스가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상
2) 최단작업 우선 스케줄링 Shortest-Job First : SJF
- CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
- 평균 대기시간을 가장 짧게하는 최적 알고리즘으로 알려져 있다.
- 비선점형 방식과 선점형 방식 두 가지로 구현될 수 있다.
- 기아현상(starvation) : SJF 알고리즘의 심각한 문제점
CPU 버스트가 짧은 프로세스가 계속 도착할 경우, CPU 버스트가 긴 프로세스는 영원히 CPU를 할당받지 못할 수 있다.
3) 우선순위 스케줄링
- 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
- 우선순위는 '우선순위값(priority number)'을 통해 표시하며, 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정한다.
- 비선점형 방식과 선점형 방식으로 각각 구현이 가능하다.
- 기아 현상이 발생할 수 있다.
aging 기법: 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법(기아 현상의 해결방안)
4) 라운드 로빈 스케줄링 (Round Robin)
-
시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식
-
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간(할당시간 : time quantum)으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수(how :
타이머 인터럽트 사용)해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다. -
사용시간이 경과한 프로세스는 준비 큐의 제일 뒤에 가서 줄을 서 다음번 차례를 기다린다.
-
할당시간을 수십 밀리초 정도의 규모로 적절하게 설정하는 것이 중요하다.
i) 할당시간이 너무 짧으면 -> CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커짐
ii) 할당시간이 너무 길면 -> FCFS와 같은 결과 -
라운드 로빈 스케줄링에서, 각 프로세스의 대기시간이 그 프로세스의 CPU 버스트 시간에
비례한다
라운드 로빈 스케줄링의 기본적인 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것이다.
5) 멀티레벨 큐
- 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법(프로세스들이 CPU를 기다리기 위해 여러 줄로 섬)
일반적으로 멀티레벨 큐에서는 대화형 작업을 담기 위한 전위큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다.
- 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용
- 후위 큐에서는 응답시간이 큰 의미가 없기 때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄이도록 함
멀티레벨 큐에서는, 큐 자체에 대한 스케줄링도 필요하다.
- 고정 우선순위 방식
우선순위가 높은 큐를 먼저 서비스하고, 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때에만 서비스 하게 된다. - 타임 슬라이스(time slice) 방식
각 큐에 CPU 시간을 적절한 비율로 할당하여 큐에 대한 기아 현상을 해소하는 방식이다.
6) 멀티레벨 피드백 큐
- 프로세스를 여러 줄로 세운다 + 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다.
- 멀티레벨 피드백 큐를 정의하는 요소들
: 큐의 수, 각 큐의 스케줄링 알고리즘, 프로세스를 상위 큐로 승격시키는 기준, 프로세스를 하위 큐로 강등시키는 기준, 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준 등
멀티레벨 피드백 큐의 대표적인 방식은 다음과 같다.
- 그림에서 상위에 있는 큐일수록 우선순위가 높다.
- 프로세스가 준비 큐에 도착하면 우선순위가 가장 높은 큐에 줄을 선다.
CPU 사용 시간이 짧은 대화형 프로세스들은 우선순위가 가장 높은 큐에서 빨리 서비스 받고 작업을 완료할 수 있다. - CPU 버스트 시간이 긴 프로세스들은 5만큼의 시간 동안 CPU를 가지고 작업을 완료할 수 없기 때문에 할당시간이 10인 하위큐로 내려가서 줄을 서게 된다.
- 만약 할당시간 10을 추가로 사용하고도 작업이 완료되지 않으면, 해당 프로세스는 CPU를 오래 사용하는 계산 위주의 프로세스로 간주되어 최하위 큐로 이동하게 된다.
- (큐에 대한 스케줄링은 고정 우선순위 방식 적용)
7) 다중처리기 스케줄링
다중처리 스케줄링 방식은 대칭형 다중처리와 비대칭형 다중처리로 나누어볼 수 있다.
- 대칭형 다중처리 : 각 CPU가 알아서 스케줄링을 결정하는 방식
- 비대칭형 다중처리 : 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식
8) 실시간 스케줄링
(앞서 살펴본) 시분할 환경에서의 스케줄링 방식은 데드라인 개념이 존재하지 않는다. 반면, 실시간 환경에서의 스케줄링은 빠른 서비스도 중요하지만 데드라인을 지키는 서비스가 더욱 중요하다.
=> 따라서, 실시간 환경에서는 데드라인이 얼마남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 널리 사용하게 된다.
5. 스케줄링 알고리즘의 평가
큐잉모델(queueing model), 시뮬레이션(simulation), 구현 및 실측 방식 등
