#5 CPU 스케줄링 - 운영체제와 정보 기술의 원리
CPU
프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리 장치이다.
프로그램 카운터(PC : Program Counter)
현재 CPU에서 수행할 코드의 메모리 주소 값을 가지고 있는 레지스터이다.
프로그램의 수행을 서로 다른 두 단계의 조합으로 나누어 볼 수 있다. 첫 째는 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 단계, 둘 째는 I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계이다. 첫 번째 작업을 CPU 버스트, 두 번째 작업을 I/O 버스트라고 한다.
프로세스 또한 CPU 작업에 치중이 되어있는 CPU 바운드 프로세스와 I/O 작업에 치중이 되어있는 I/O 바운드 프로세스로 나누어 볼 수 있다 .
CPU 스케줄러
CPU 스케줄러는 준비 상태에 있는 프로세스들 중에서 어떤 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드입니다. 이와 같은 상황 외에도 CPU 스케줄링이 발생하는 경우가 있습니다.
1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우
디스패처(Dispatcher)
CPU를 할당받고 작업을 수행할 수 있도록 환경 설정을 하는 커널 모듈을 디스 패쳐라고 부릅니다. 디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 작업을 수행합니다.
디스패치 지연 시간(Dispatch Latency)
디스 패쳐가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지연 시간이라고 부르며, 디스패치 지연시간은 문맥 교환 오버헤드에 해당됩니다.
스케줄링 성능 평가
- CPU 활용도 : 전체 시간 중 CPU가 명령을 수행한 시간의 비율
- 처리량 : 주어진 시간 동안 CPU 버스트를 완료한 프로세스의 개수
- 소요 시간: 프로세스가 CPU 요청 시점부터 CPU 버스트가 끝날 때까지 걸린 시간
- 대기 시간: 프로세스가 CPU 버스트 기간 중 준비 큐에서 기다린 시간의 합
- 응답 시간 : 프로세스가 CPU 요청 시점부터 처음으로 CPU를 얻을 때까지 기다린 시간
스케줄링 알고리즘
FCFS(First-Come-First-Served)
- 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
SJF(Shotest-Job-First)
- CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식 SJF 방식은 두 가지로 분류된다.
- 비선점형 방식과 선점형 방식이다.
- 비선점형 방식은 일단 CPU를 획득하면 할당받은 프로세스가 작업을 완료하기 전까지 다른 프로세스에게 CPU를 뺏기지 안
는다.
- 선점형 방식의 경우 이미 CPU가 할당된 프로세스가 있더라도 CPU 버스트가 더 짧은 프로세스가 준비 큐에 들어오면 CPU를 빼앗기게 된다.
우선순위 스케줄링(Priority Schduling)
- 준비 큐에서 기다리는 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.
- 우선순위는 우선순위 값이 작을수록 높은 우선순위를 갖는다.
- 우선순위 스케줄링은 어떤 상황에 우선순위를 더 높게 두느냐에 따라 어떤 프로세스가 CPU를 차지할지 달라지게 된다.
* 우선순위 스케줄링의 문제점 : 우선순위가 높은 프로세스가 계속 들어올 경우 우선순위가 낮은 프로세스는 CPU를 차지하지 못하는 기아 현상이 발생할 수 있다. 이러한 문제를 해결하기 위해 프로세스의 대기시간이 길어지면 우선순위를 조금씩 높여가는 방식을 사용한다.
라운드 로빈 스케줄링(Round-Robin-Schduling)
- 이 방식은 각 프로세스가 CPU를 차지하는 시간이 동일하다.
- 프로세스는 일정 시간 CPU를 사용하고 사용시간이 끝나면 다른 프로세스에게 CPU를 넘겨준다.
- 하지만 할당 시간이 너무 길면 FCFS와 같은 결과를 나타내며 할당 시간이 너무 짧은 경우 문맥 교환(Context Switch)으로 인한 오버헤드가 발생한다.
멀티 레벨 큐(multi-level-queue)
- 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법이다. 즉, CPU를 기다리는 준비 큐가 여러 개이며 어떤 준비 큐를 우선적으로 사용할지, 각 준비 큐에는 어떤 프로세스를 먼저 앞에 세울지에 대한 전략이 필요하다.
- 멀티 레벨 큐의 준비 큐는 보통 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할한다
- 전위 큐에서는 응답 시간을 줄이기 위해 라운드 로빈 방식, 후위 큐에서는 FCFS 방식을 사용한다.
- 또한, 멀티 레벨 큐에는 큐들 자체에 대한 스케쥴링 또한 필요하다.
- 큐 마다 우선순위를 매겨 우선순위가 높은 큐부터 CPU가 할당되는 고정 우선순위 방식과 각 큐마다 사용 시간을 비율로 할당하는 타임 슬라이스 방식이 있다.
멀티 레벨 피드백 큐(multi-level-feedback queue)
- 프로세스를 여러 개의 큐에 나누어 줄 세운는 점이 멀티 레벨 큐와 비슷하나 프로세스가 여러개의 큐에 이동 가능하다는 점이 특징이다.
- 예를 들어 하나의 프로세스가 기아 현상을 일으키는 프로세스가 존재한다면 노화 기법을 통해 우선순위가 높은 큐로 이동시키는 방식을 사용하기도 한다.
다중 처리기 스케줄링
- CPU가 여러 개인 시스템을 다중 처리기 시스템(multi processor system)이라고 부른다.
- 다중 처리기 시스템은 프로세스를 한 줄로 세워 각 CPU가 알아서 프로세스를 가져가는 방식을 사용하거나 각 CPU 별로 줄을 세워 처리하는 방식을 사용한다.