4. CPU 스케줄링
CPU는 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리 장치이다.
프로그램이 시작되어 메모리에 올라가면, 프로그램 카운터라는 이름의 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있게 된다. 그러면 CPU는 프로그램 카운터가 기리키는 주소의 기계어 명령을 하나씩 수행하게 된다.
I/O 버스트
I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업
CPU 버스트
I/O를 한번 수행한후 다음 I/O를 수행하기까지 적접 CPU를 가지고 명령을 수행하는 일련의 작업
시스템 내에서 수행되는 프로세스들의 CPU버스트를 분석해보면 대부분 짧은 CPU버스트를 가지며, 극히 일부분만 긴 CPU 버스트를 가진다.
주로 대화형 작업이 CPU 버스트가 짧다. 이러한 작업은 빠른 CPU 서비스를 필요로하기 때문에 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다.
I/O 바운드 프로세스에게 먼저 CPU를 할당할 경우 CPU를 잠깐만 수행한 후 곧바로 I/O작업을 수행할 수 있으므로 I/O장치의 이용률이 높아진다. 만약 CPU 바운드 프로세스에게 먼저 CPU를 할당할 경우 그 프로세스가 CPU를 다 사용할 때까지 I/O바운드 프로세스는 응답 기간이 길어질 뿐만 아니라 해당 I/O장치도 그 시간동안 작업을 수행하지 않는 휴면 상태가 되기 때문에 비효율적이다.
CPU 스케줄러
CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영 체제 코드이다.
주로 타이머 인터럽트가 발생하면 CPU 스케줄러가 호출된다.
이 밖에도 CPU 스케줄링이 필요한 경우가 있다.
실행 상태에 있는 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우 -- 비선점
실행 상태에 있는 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우 -- 선점
I/O 요청으로 봉쇄 상태에 있든 프로세스의 I/O작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우 -- 비선점
CPU에서 실행 상태에 있는 프로세스가 종료되는 경우 -- 선점
디스패처
프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 커널 모듈
현재 수행중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로 부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행
스케줄링의 성능 평가
CPU 활용도 (CPU Utilization) : 전체 시간중 CPU가 명령을 수행한 시간의 비율
처리량 ( Throughput) : 주어진 시간 동안 CPU 버스트를 완료한 프로세스의 개수
소요 시간 ( Turn around Time) : 프로세스가 CPU 요청 시점부터 CPU 버스트가 끝날 때까지 걸린 시간
대기 시간 ( Wating Time) : 프로세스가 CPU 버스트 기간 중 준비 큐에서 기다린 시간의 합
응답 시간 (Response Time) : 프로세스가 CPU 요청 시점부터 처음으로 CPU를 얻을 때까지 기다린 시간
스케줄링 알고리즘
FCFS (First Come First Served)
프로세스가 준비큐에 도착한 시간 순서대로 CPU를 할당하는 방식
CPU버스트가 긴 프로세스가 먼저 도착하게 되면 평균 대기 시간이 길어지게 된다.
SJF (Shortest Job First)
CPU버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
평균 대기 시간을 가장 짧게 하는 최적의 알고리즘으로 알려져 있다.
비선점형과 선점형으로 나누어져 있다.
선점형은 CPU를 할당했다고 하더라도 CPU 버스트가 더 짧은 프로세스가 도착하면 CPU를 빼앗아 더 짧은 프로세스에게 할당한다.
실제로 CPU 버스트 시간을 알 수 없으므로 Tn + 1 = aTn + (1-a)Tn으로 계산하여 예측한다.
기아 현상 발생 가능
우선순위 스케줄링
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
우선순위 값을 통해 표시하며 우선순위값이 작을 수록 높은 우선순위를 가지게 된다.
CPU버스트를 기준으로 하면 SJF 와 같은 의미이다.
비선점형과 선점형이 있다.
기아현상이 발생할 수 있다. 이 점을 해결하기 위해 Aging 기법을 사용한다. 기다리는 시간이 길어지면 우선순위를 높인다.
라운드 로빈 스케줄링
시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식이다.
프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며 이 시간이 경과하면 이 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 달느 프로세스에게 CPU를 할당한다.
공정한 스케줄링이라고 할 수 있다. CPU를 쓰고하 하는 양과 대기시간이 비례하기 때문이다.
평균 소요시간과 평균 대기시간이 길어진다.
멀티레벨 큐
준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법
대화형 작업을 담기 위한 전위 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할하여 운옇나다. 전위 큐는 응답 시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용한다. 계산 위주의 작업을 하기 위한 후위 큐에서는 응답 시간이 큰 의미를 가지지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥 교환 오버헤드를 줄이도록 한다.
큐 자체에 대한 스케줄링도 필요하다. 고정 우선순위 방식은 전위큐에 우선적으로 CPU를 할당하고 전위 큐가 비어 있을 경우에만 후위 큐에 있는 프로세스에게 CPU가 할당된다.
멀티 레벨 큐와 전체적으로는 같으나 프로세스가 하나의 큐에서 달느 큐로 이동 가능한 점이 차이점이다. Aging 기법을 사용해 우선순위가 낮은 큐에서 높은 큐로 이동이 가능하다.