CPU 스케줄링
1. CPU스케줄링이란?
-
운영체제가 준비 상태(ready)인 프로세스 중 우선순위가 높은 프로세스에게 CPU 자원을 할당하는 과정
-
CPU스케줄링은 컴퓨터 성능과 직결되는 대단히 중요한 문제
-
잘못된 CPU스케줄링은 반드시 실행되어야 할 프로세스들이 실행되지 못하거나, 급하지 않는 프로세스들이 우선으로 실행되는 등 무질서한 상태가 발생할 수 있다.
2. 프로세스 우선순위
-
프로세스마다 우선순위가 다르다.
-
우선순위가 높은 프로세스는 빨리 처리해야 하는 프로세스라는 의미이다.
-
운영체제는 각 프로세스의 PCB에 우선 순위를 명시하고, 이를 기준으로 프로세스의 처리 순서를 결정한다.
-
일반적으로 CPU 집중 프로세스보다 입출력 집중 프로세스의 우선순위가 더 높다.
-
입출력 집중 프로세스를 가능한 빨리 실행시켜 입출력장치를 끊임 없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이다.
-
또한 입출력 집중 프로세스는 입출력장치가 작업을 완료하기 전까지 대기 상태(blocked)가 되기 때문에 입출력 집중 프로세스를 먼저 처리하면 다른 프로세스가 CPU를 집중적으로 사용할 수 있어 효율적이다.
2.1. CPU 집중 프로세스
-
CPU 작업이 더 많은 프로세스
-
대기 상태(blocked)보다 실행 상태(running)에 더 많이 머무른다.
-
복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스들이 CPU 집중 프로세스이다.
2.2 입출력 집중 프로세스
-
입출력 작업이 더 많은 프로세스
-
실행 상태(running)보다 입출력을 위한 대기 상태(blocked)에 더 많이 머무른다.
-
비디오 재생, 디스크 백업 작업을 담당하는 프로세스들이 입출력 집중 프로세스이다.
3. 스케줄링 큐
-
준비 상태(ready)인 프로세스들의 PCB를 저장하는 큐 (아마도 우선순위큐?)
-
운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 실행하되, 그 중 우선순위가 높은 프로세스를 먼저 실행한다.
-
운영체제가 관리하는 큐에는 대표적으로 준비 큐와 대기 큐가 있다.
3.1. 준비 큐
- CPU를 이용하고 싶은 프로세스들이 저장되어 있는 큐
3.2. 대기 큐
-
입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 저장되어 있는 큐
-
입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 준비 상태로 변경한 뒤, 준비 큐로 이동시킨다.
3.3. 프로세스 상태 다이어그램 with 스케줄링큐
4. 선점형과 비선점형 스케줄링
- CPU스케줄링은 선점형 스케줄링과 비선점형 스케줄링으로 나뉜다.
4.1. 선점형 스케줄링
-
프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
-
다시 말해 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
-
프로세스마다 정해진 시간만큼 CPU를 사용하고, 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식도 선점형 스케줄링의 일종
-
장점
- 특정 프로세스가 과도하게 CPU를 독점하지 않음
- 긴급한 작업이 빨리 처리되어 응답속도가 빨라짐
- 입출력 작업이 많은 프로세스를 빠르게 다른 작업과 교체할 수 있어 CPU를 효율적으로 사용
-
단점
- 문맥 교환 과정에서 오버헤드 발생
4.2. 비선점형 스케줄링
-
하나의 프로세스가 자원을 사용하고 있다면 해당 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식
-
다시 말해 어느 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식
-
다른 프로세스들은 자원을 독점 중인 프로세스의 사용이 끝날 때까지 기다려야 한다.
-
장점
- 문맥 교환의 횟수가 상대적으로 적어 오버헤드가 적다.
-
단점
- 긴급한 작업이 와도 현재 작업이 끝날 때까지 대기해야 하므로 응답속도가 느려짐
- 입출력 작업이 많은 프로세스가 CPU를 오래 점유할 경우, CPU가 비효율적으로 사용될 수 있다.
- 특정 프로세스가 오랫동안 자원을 독점할 가능성이 있어 다중 사용자 환경에 부적합
5. CPU 스케줄링 알고리즘
5.1. FCFS 스케줄링 (First Come First Served)
- 선입선출(FIFO)
- 비선점형 스케줄링 알고리즘
- 준비 큐에 삽입된 순서대로 프로세스를 실행
- 언뜻 보기에는 가장 공정해 보이지만, 때때로 프로세스들이 기다르는 시간이 매우 기다리는 부작용인 호위 효과가 발생할 수 있다.
5.2. SJF 스케줄링 (Shortest Job First)
- 최단 작업 우선 스케줄링
- 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형 알고리즘으로 구현될 수도 있다.
- 준비 큐에 삽입된 프로세스들 중 CPU 이용시간의 길이가 가장 짧은 프로세스부터 실행
5.3. 라운드 로빈 스케줄링
- FCFS + 타임슬라이스 스케줄링 방식
- 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼 돌아가며 CPU를 이용하는 선점형 스케줄링 알고리즘
- 정해진 시간만큼 CPU를 사용하고, 정해진 시간 내에 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 -> 이 과정에서 문맥교환 발생
- 타임슬라이스가 너무 크면 FCFS와 똑같이 호위효과 발생
- 타임슬라이스가 너무 작으면 문맥교환에 발생하는 비용 증가
5.4. SRT 스케줄링 (Shortest Remaining Time)
- 최소 잔여 시간 우선 스케줄링
- SJF + 라운드 로빈 스케줄링 방식
- 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용해되, CPU를 사용할 다음 프로세스는 남아있는 작업 시간이 가장 적은 프로세스를 선택하는 선점형 알고리즘
5.5. 우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위가 가장 높은 프로세스부터 실행하는 스케줄링 알고리즘
- 우선순위가 낮은 프로세스는 실행이 계속해서 연기되는 기아 현상이 발생할 수 있다.
- 기아 현상을 방지하기 위한 대표적인 기법으로 에이징이 있다.
※우선순위가 같은 프로세스들은 FCFS로 스케줄링
5.5.1. 에이징 (aging)
- 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
- 대기 중인 프로세스의 우선순위가 마치 나이를 먹듯 점차 증가한다.
5.6. 다단계 큐 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
- 우선순위가 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 다 다음 우선순위 큐에 있는 프로세스들을 처리
- 큐마다 다른 알고리즘을 적용할 수 있다. ex) 우선순위0 큐는 FCFS, 우선순위1 큐는 라운드 로빈 ....
- 문제점: 프로세스들이 큐 사이를 이동할 수 없다 -> 기아 발생
5.7. 다단계 피드백 큐 스케줄링
- 다단계 큐 스케줄링의 발전된 형태
- 프로세스들이 큐 사이를 이동할 수 있다.
- 타임슬라이스 이내에 작업을 끝내지 못한 프로세스는 우선순위가 낮은 큐로 이동 -> CPU 집중 프로세스들은 자연스럽게 우선순위가 낮아짐
- 낮은 우선순위 큐에서 오래 기다리는 프로세스는 에이징을 적용하여 우선순위가 높은 큐로 이동 -> 기아 현상 예방
- 가장 일반적인 CPU 알고리즘
