CPU 스케줄링
CPU 스케줄링은 여러 프로세스가 동시에 실행될 때, 각 프로세스에 CPU 자원을 적절하게 할당하여 성능을 최적화하는 기술이다.
개요
프로세스 우선순위
프로세스의 특성과 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 우선순위를 부여한다. 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.
입출력 집중 프로세스 (I/O Bound Process)
CPU를 거의 사용하지 않고, 대부분의 시간을 입출력 작업에 사용하는 프로세스. 입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다. 입출력장치를 기다리는 작업인 입출력 버스트가 많은 프로세스이다.
CPU 집중 프로세스 (CPU Bound Process)
CPU 작업(CPU 버스트)이 많은 프로세스. 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.
스케줄링 큐
스케줄링 큐는 CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스 등을 줄세워 놓은 큐이다. 큐는 선입선출(FIFO) 방식으로 관리되거나, 우선순위 기반으로 관리될 수 있다.
운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다.
준비 큐 (Ready Queue)
CPU를 사용하고 싶은 프로세스들이 기다리는 큐이다.
대기 큐 (Waiting Queue)
입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 기다리는 큐이다. 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 해당 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거한다. 해당 PCB는 준비 큐로 이동된다.
선점형과 비선점형 스케줄링
선점형 스케줄링 (Preemptive Scheduling)
프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식이다.
비선점형 스케줄링 (Non-Preemptive Scheduling)
하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식
스케줄링 알고리즘
선입 선처리 스케줄링 (FCFS, First-Come First-Served)
준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다. 즉, CPU를 먼저 요청한 프로세스부터 CPU를 할당한다. 직관적이고 간단하지만, 대기 시간이 길어지는 호위 효과(Convoy Effect)가 발생할 수 있다. 긴 프로세스가 CPU를 차지하면 뒤따라오는 짧은 프로세스들이 오랫동안 대기해야 하는 단점이 있다.
프로세스가 P1(24ms), P2(3ms), P3(3ms) 순서로 도착하면, P1이 먼저 처리되어 P2와 P3는 대기 시간이 길어질 수 있다.
최단 작업 우선 스케줄링 (SJF, Shortest Job First)
준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식이다. 기본적으로 비스선점형 스케줄링 알고리즘으로 분류되지만, 최소 잔여 시간 우선 스케줄링처럼 선점형으로 구현될 수도 있다.
P1(6ms), P2(8ms), P3(2ms)의 프로세스가 있으면, P3이 먼저 실행되고 그 다음에 P1, P2가 실행된다.
라운드 로빈 스케줄링 (Round Robin)
선입 선처리 스케줄링에 타임 슬라이스라는 개념을 부여한 스케줄링 방식이다. 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.
큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. 타임 슬라이스가 지나치케 크면 호위 효과가 생길 여지가 있고, 지나치게 작으면 컨텍스트 스위칭 비용이 커진다.
P1, P2, P3가 각각 10ms의 작업을 수행할 때, 타임 슬라이스가 4ms라면 P1이 4ms, P2가 4ms, P3이 4ms 순서로 CPU를 점유하고 반복적으로 처리된다.
최소 잔여 시간 우선 스케줄링 (SRT, Shortest Remaining Time)
최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식이다. 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.
우선순위 스케줄링 (Priority Scheduling)
프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식이다. (우선순위가 같은 프로세스들은 선입 선처리로 스케줄링 된다.)
우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 실행이 계속해서 연기될 수 있다. 이를 기아(starvation) 현상이라고 한다. 이를 방지하기 위한 기법으로, 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식인 에이징(aging)이 있다.
다단계 큐 스케줄링 (Multilevel Queue Scheduling)
우선순위 스케줄링의 발전된 형태로 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 다음 우선순위 큐에 있는 프로세스들을 처리한다.
다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)
다단계 큐 스케줄링에서 프로세스가 다른 큐로 이동할 수 있는 스케줄링 방식이다. 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.
참조
https://www.hanbit.co.kr/store/books/look.php?p_code=B9177037040&utm_source=hongong