OS가 하는 일은 여러가지 있다. 프로세스 관리, 메모리 관리, 파일 시스템 관리, IO 기타 등등.. 다 중요하지만, 그 중에서도 중요한 것은 프로세스 관리인 것 같다.
컨텍스트 스위칭에 관해 공부를 할 때, 하나의 프로세스가 실행 중인 상태에서 다음 프로세스가 실행하려고 할 때 기존 프로세스와 관련된 상태의 값을 저장하고, 새로운 프로세스가 실행하도록 상태를 넘겨준다고 했다. 그럼 여기서, 어떤 기준으로 다음 프로세스를 선택하는걸까? 그 해답은 CPU 스케줄링 기법에 있었다.
CPU 스케줄링
멀티 프로그래밍에서 CPU의 효율성을 극대화하기 위해 사용된다. 이 과정에서 CPU 자원을 어느 프로세스에게 줄 것인지와, 얼마만큼 오래 CPU를 점유할 것인지를 결정한다. 대기 시간은 최소화하고 최대한 공평하게 처리하는 것을 목적으로 한다.
CPU내 프로세스 상태 변화
- ready -> running : dispatching
- running -> ready : 하드웨어 인터럽트, OS의 스케줄러가 개입됨(선점형 스케줄링)
- running -> waiting : CPU yield (비선점형 스케줄링)
- running -> terminating : 비선점형 스케줄링
- waiting -> ready : 선점형 스케줄링
단계별 처리 스케줄링
장기 스케줄링 : 어떤 프로세스를 준비 큐에 넣을 것인가
- 어떤 프로세스가 시스템의 자원을 차지 할 수 있도록 할 것인가를 결정해 준비(ready) 상태의 큐로 보내는 작업을 말한다.
- 상위 스케줄링이라고 하며, 작업(Job) 스케줄러에 의해 수행된다.
- 수행 빈도가 적고 느리다.
중기 스케줄링 : 메모리에 적재된 프로세스 수 관리
- 컴퓨터 자원 고갈등의 이유로, 적재된 프로세스 중 일부에 대해 상당 기간 처리를 보류해야 할 때, 여러가지 요인을 고려하여 보류 대상 프로세스를 선정한다.
- Swap Out : 처리가 보류된 프로세스를 처리 재개가 가능할 때 까지 CPU에서 디스크의 스왑 영역에 저장해둠
- Swap In : Swap Out가 완전 반대 상태라고 볼 수 있음
단기 스케줄링 : 어떤 프로세스에게 CPU를 할당할 것인가
- CPU 스케줄러라고도 하며, 준비 상태의 프로세수 중 어떤 프로세스를 다음 번에 실행 상태로 만들 것인지 결정한다.
- 이러한 CPU 스케줄러는 결국 프로세스들에 CPU를 배분하는 역할도 하기 때문에 디스패처라고도 부른다
여기서 디스패처란 ?
새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경을 설정하는 커널 모듈. 수행중이던 프로세스의 Context를 PCB에 저장하고, 새롭게 선택된 프로세스의 Context를 PCB로부터 복원한 후, 그 프로세스에게 CPU를 넘기는 과정을 수행한다.
CPU 스케줄링의 성능 평가 방식
스케줄링 성능 기법을 평가하기 위해 여러 지표들이 사용되는데, 이 지표들은 크게 시스템 관점과 사용자 관점으로 나누어 볼 수 있다.
- 시스템 관점 :
- CPU 활용도 : 전체 시간 중, CPU가 일 한 시간의 비율
- 처리량 : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇개를 끝마쳤는지 나타내는 지표
- 사용자 관점 :
- 소요시간 : 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
- 대기 시간 : 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
- 응답 시간 : 준비 큐에 들어온 후 첫번째 CPU를 획득하기까지 기다린 시간
CPU 스케줄링의 방식
- 선점 스케줄링 :
- CPU가 어떤 프로세스에 의해 점유중일 때, 우선 순위가 높은 프로세스가 CPU를 차지할 수 있다.
- 장점 : 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
- 단점 : 우선순위가 높은 프로세스가 생길 때 마다 계속 context switching이 발생해 오버헤드가 크다.
- 비선점 스케줄링
- 프로세스가 스스로 CPU를 놓아주는 시점(작업이 완료됨) 혹은 IO에만 스케줄링이 발생
- 일괄처리 방식에 적합하다
- 장점 : 프로세스 응답 시간을 예측하기 쉽다.
- 단점 : 중요한 작업(짧은작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있다
CPU 스케줄링 알고리즘
FCFS(First Come First Served) : 비선점형
프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식. 이 방식은 CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 CPU는 선점하지 않는다.
CPU버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어지고, CPU 버스트가 짧은 프로세스가 먼저 도착할 경우 평균 대기시간은 짧아진다. 이렇게 다른 모든 프로세스들이 커다란 한 프로세스가 끝날 때 까지 기다리는 현상(convey effect)가 발생할 수 있다.
SJF(Shortest Job First) : 비선점형
CPU 버스트가 가장 짧은 프로세스를 CPU에 먼저 할당하는 방식이다. SJF의 경우 비선점형으로 계산 위주의 긴 프로세스에 CPU가 할당 된 상태에서 다수의 입/출력 위주 짧은 프로세스들이 도착한다면 위와 같이 convey effect현상이 발생할 수 있다.
또한, 짧은 프로세스들이 지속적으로 도착한다면, 상대적으로 긴 프로세스는 계속해서 지연되는 기아상태(Starvation State)가 발생할 수 있다.
HRRF(Highest Response Ratio First) : 비선점형
각 프로세스별 응답률을 계산하여 응답률이 가장 큰 프로세스를 먼저 처리한다.
응답률 = (준비큐 대기시간 + CPU 버스트 시간) / (CPU 버스트 시간) = 1 + ((준비 큐 대기시간) / (CPU 버스트 시간))
SJF스케줄링의 문제점인 기아현상을 보완하기 위해 나온 알고리즘이다.
SRTF(Shortest Remaining Time First) : 선점형
준비 대기열에 새로운 프로세스가 도착하면, 현재 진행중인 프로세스의 잔여 실행시간과 새로운 프로세스의 CPU 버스트 시간을 비교해 새 프로세스의 실행 시간이 더 짧으면 CPU를 강제 회수해 새로운 프로세스에 할당하는 방식이다. SJF의 단점을 개선한 방식이다. 하지만 CPU 버스트 시간을 미리 알 기 어렵고, 기아상태 발생 가능성이 더 커질 수 있다.
우선순위 스케줄링 : 선점형 + 비선점형
준비 큐에 기다리는 프로세스 중, 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식. 우선순위가 같을 경우 FCFS방식으로 할당한다.
우선순위 스케줄링 역시, 우선순위가 높은 프로세스가 계속 들어오면 우선순위가 낮은 프로세스가 기아 현상이 발생할 수 있는데, 이는 노화기법으로 해결 할 수 있다.
노화기법은, 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 높은 우선순위를 가지는 방법을 말한다.
라운드 로빈 스케줄링 : 선점형
모든 프로세스에 동일한 CPU 점유시간(타임 퀀텀)을 주고, 처리 중인 프로세스의 CPU 실행 시간이 타임 퀀텀을 초과하면 CPU를 강제 회수하여 다음 프로세스에 할당하는 방식이다.
타임퀀텀이 너무 길면, FCFS와 동일하게 되고, 타임퀀텀이 너무 짦으면 컨텍스트 스위칭이 잦아져 오버헤드가 커진다.
멀티 레벨 큐 : 선점형
일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 여러개로 분할해 관리하는 스케줄링 기법이다. 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 선다.
멀티 레벨 큐 내 준비 큐는 보통 대화형(반응형) 작업을 담기 위한 전위 큐(우선순위 높음)와 계산 위주(우선순위 낮음) 후위 큐로 분할하여 운영한다.
- 전위 큐 : 라운드로빈(응답시간을 짧게 가지기 위함)
- 후위 큐 : 계산위주의 작업을 위한 후위 큐이기에 응답시간이 큰 의미를 가지지 않아 FCFS를 주로 사용
각각의 준비 큐 프로세스 간에 다른 스케줄링 전략을 적용할 수 있으며, 프로세스 도착시 어느 큐에 삽입할지에 대한 매커니즘도 필요하다.
보통 고정적인 우선순위 방식을 부여해 우선 순위 높은 큐가 먼저 서비스 하고 낮은 큐는 우선순위 높은 큐가 비었을 때 서비스 한다. 여기서 기아현상을 해소하기 위해 각 큐에 CPU 시간을 적절한 비율로 할당한다.
멀티 레벨 피드백 큐 : 선점형
기본 멀티 레벨 큐에서 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 추가되었다. 이 방식은 노화기법을 극복하기 위해 착안되어는데, 우선순위 낮은 큐가 오래 기다렸으면 우선 순위가 높은 큐로 승격시키는 방법을 사용한다.
스케줄링 알고리즘을 사용하는 케이스
이런 스케줄링 알고리즘은, 준비 큐에 있는 프로세스 중 하나를 선택할 때 사용되지만 그 외에도 CPU 스케줄링이 필요한 상황이 있다 :
- 실행 상태에 있던 프로세스가 I/O에 의해 대기 상태로 바뀌는 경우(비선점)
- 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우(선점)
- I/O요청으로 대기상태에 있던 프로세스의 I/O작업이 완료되어 준비 상태로 바뀌는 경우(선점)
- CPU에서 실행 상태에 있는 프로세스가 종료되는 경우(비선점)
이미지 출처 및 참고자료 :
