CPU Scheduling
무엇인가?
시스템에 존재하는 여러 프로세스들의 작업 우선순위를 결정하는 행위이다.
왜 하나?
CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 실행되기 때문이다.
작업의 종류
CPU Burst
사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행
CPU Bound process
I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
I/O Burst
I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
I/O bound process
I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
바람직한 스케줄링
I/O bound process는 대부분 대화형 작업으로 사용자에 대한 빠른 응답이 중요하다. 따라서 CPU Busrst가 짧은 프로세스인 I/O bound process에 우선적으로 CPU를 사용할 수 있게 하는 스케줄링이 필요하다.
I/O bound process 우선순위 > CPU bound process 우선순위
CPU Scheduling 방식
비선점형(nonpreemptive)
프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
선점형(proeemptive)
프로세스가 CPU를 계속 사용하기 원하더라도 강제로 빼앗을 수 있는 방법
선점 방법
할당 시간(time quantum)을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적이다.
Dispatcher
무엇인가?
새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
왜 필요한가?
CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하기 때문이다.
과정
- 디스패처는 수행중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘긴다.
- 시스템의 상태를 사용자모드로 전환해 사용자 프로그램에게 CPU 제어권을 넘긴다.
- 사용자 프로그램은 복원된 문맥 중 PC로부터 현재 수행할 주소를 찾을 수 있다.
디스패치 지연시간(dispatch latency)
디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간이다. 대부분 Context Switching의 오버헤드에 해당한다.
성능 평가
시스템 관점
CPU 이용률(CPU utilization)
전체 시간 중에서 CPU가 일을 한 시간의 비율
처리량(throughput)
주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지(CPU Burst를 완료한 프로세스의 개수)
사용자 관점
소요시간(turnaround time)
프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU Burst가 끝날 때까지 걸린 시간, 즉 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합
대기시간(waiting time)
CPU Burst 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
응답시간(response time)
프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
알고리즘
선입선출(FCFS: First-Come First-Served)
무엇인가?
프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식이다. 비선점형이다.
단점
콘보이 현상(Convoy effect): CPU Burst가 짧은 프로세스가 CPU Burst가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상
최단작업 우선 스케줄링(SJF: Shortest-Job First)
무엇인가?
CPU Burst가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.
구현 방식
선점형: SRTF(Shortest Remaining Time First)비선점형
장점
평균 대기시간을 가장 짧게 하는 최적 알고리즘이다.
단점
기아 현상(Starvation): CPU Burst가 짧은 프로세스가 계속 도착할 경우 CPU Burst가 긴 프로세스는 영원피 CPU를 할당받지 못하는 현상
우선순위 스케줄링(Priority Scheduling)
무엇인가?
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.
구현 방식
선점형비선점형
단점
기아 현상 발생 가능 -> 노화(aging)기법을 사용한다.
노화(aging): 기다리는 시간이 길어지면 우선순위를 높인다.
라운드 로빈 스케줄링(Round Robin Scheduling)
무엇인가?
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서있는 다른 프로세스에게 CPU를 할당한다.
할당시간(time quantum): 각 프로세스마다 한 번에 CPU를 연속으로 사용할 수 있는 최대 시간CPU 회수 방법: 타이머 인터럽트를 사용한다.
왜 쓰는가?
CPU Burst 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU Burst 시간이 긴 프로세스가 불이익을 당하지 않도록 하기 위해.
장점
- 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다.
- 콘보이, 기아 현상 예방 가능
멀티레벨 큐(Multi-level queue)
무엇인가?
준비 큐를 여러 개로 분할해 관리하는 방식이다. 일반적으로 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영한다.
전위 큐(foreground queue)
응답 시간을 짧게 하기 위해 Round Robin 스케줄링 사용
후위 큐(background queue)
응답 시간이 큰 의미를 가지지 않으므로 FCFS 스케줄링을 사용해 Context Switching Overhead를 줄인다.
단점
- `큐 자체에 대한 스케줄링 필요
고정 우선순위 방식(fixed priority scheduling): 전위 큐가 빈 경우에만 후위 큐에 있는 프로세스에 CPU 할당타임 슬라이스 방식(time slice): 각 큐에 CPU 시간을 적절한 비율로 할당
멀티레벨 피드백 큐(MFQ: Multi-level Feedback Queue)
무엇인가?
멀티레벨 큐를 사용하고 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다.
장점
Round Robin 스케줄링 방식을 발전시켜 프로세스의 CPU 작업시간을 다단계로 분류하여 작업시간이 짧은 프로세스일수록 빠른 서비스가 가능하도록 하고, 작업시간이 긴 프로세스에 대해서는 문맥 교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 채택할 수 있도록 한다.
참고
