[ 혼자 공부하는 컴퓨터구조 + 운영체제 ] Chapter11. CPU 스케줄링

11-1. CPU 스케줄링 개요

CPU 스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

 

(1) 프로세스 우선순위

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행되는데, 프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있다.

입출력 집중 프로세스(I/O bound process): 입출력 작업이 많은 프로세스 ex. 비디오 재성, 디스크 백업

- 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다.

CPU 집중 프로세스(CPU bound process): CPU 작업이 많은 프로세스 ex. 복잡한 수학 연산, 컴파일, 그래픽 처리 작업

- 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.

 

CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구한 경우, 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이다.

 

운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.

 

(2) 스케줄링 큐

운영체제가 매번 모든 PCB를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 일은 매우 번거로우며 오랜 시간이 걸린다.

그래서 각 자원을 사용하고 싶은 프로세스들을 줄을 세워, 이 줄을 스케줄링 큐(scheduling queue)로 구현하고 관리한다.

※ 큐는 자료 구조 관점에서 선입선출 구조이지만, 스케줄링에서 이야기하는 큐는 반드시 선입선출 방식일 필요는 없다.

 

준비 큐(ready queue): CPU를 이용하고 싶은 프로세스들이 서는 줄

대기 큐(waiting queue): 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

 

운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다.

 

(3) 선점형과 비선점형 스케줄링

선점형 스케줄링(preemptive scheduling): 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식

- 프로세스마다 정해진 시간만큼 CPU를 사용하고, 타이머 인터럽트가 발생하면 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식도 선점형 스케줄링의 일종으로 볼 수 있다.

- 더 급한 프로세스가 언제든 끼어들어 사용할 수 있는 스케줄링 방식이므로 어느 한 프로세스 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다.

- 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

 

비선점형 스케줄링(non-preemptve scheduling): 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식

- 문맥 교환에서 발생하는 오버헤드가 선점형 스케줄링보다 적다.

- 하나의 프로세스가 자원을 사용 중이라면, 당장 자원을 사용해야 하는 상황에서도 무작정 기다려야 하기 때문에 모든 프로세스가 골고루 자원을 사용할 수 없다.

 

 

11-2. CPU 스케줄링 알고리즘

(1) 스케줄링 알고리즘의 종류

선입 선처리 스케줄링(= FCFS 스케줄링)

: 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식

- 프로세스들이 기다리는 시간이 매우 길어질 수 있다.

- 호위 효과(convoy effort): CPU를 오래 사용하는 프로세스가 먼저 도착하여, 그 프로세스가 CPU를 사용하는 동안 실행 시간이 짧은 다른 프로세스가 오래 기다려야 하는 현상

 

최단 작업 우선 스케줄링(= SJF 스케줄링)

: 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

- 기본적으로 비선점형 스케줄링 알고리즘으로 분류된다.

 

라운드 로빈 스케줄링

: 선입 선처리 스케줄링에 타임슬라이스라는 개념이 더해진 스케줄링 방식

- 타임슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.

 

최소 잔여 시간 우선 스케줄링(= SRT 스케줄링)

: 선입 선처리 스케줄링에 타임슬라이스라는 개념이 더해진 스케줄링 방식

- 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식

- 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

 

우선순위 스케줄링

: 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘

- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링 된다.

- 기아(starvation) 현상: 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 우선순위가 높은 프로레스들에 의해 실행이 계속해서 연기되는 현상

- 에이징(aging): 기아 현상을 방지하기 위한 대표적인 기법으로, 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

 

다단계 큐 스케줄링

: 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

- 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리한다.

- 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.

 

다단계 피드백 큐 스케줄링

: 다단계 큐 스케줄링의 발전된 형태로, 프로세스들이 큐 사이를 이동할 수 있다.

- 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행된다.

- 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있다.