[운영체제] CPU 스케줄링

이 글은 패스트캠퍼스의 현실 세상의 컴퓨터공학 지식 with 30가지 실무 시나리오 초격차 패키지 Online.를 보고 공부한 내용을 정리한 글입니다. 이해한 내용을 바탕으로 작성했기에 틀린 내용이 있을 수 있습니다.

CPU 스케줄링

모든 프로세스(및 스레드)는 실행되기 위해 자원을 필요로한다.

이때 운영체제가 공정하고 합리적으로 자원을 배분하는 방법을 스케줄링이라고 한다. 자원이 CPU자원인 경우 똑같이, CPU자원을 배분하는 방법을 CPU 스케줄링이라고 한다.

프로세스 우선순위

일반적으로 그냥 CPU 자원을 차례대로 번갈아가면서 사용하면 되지 않나 싶다. 하지만 이것은 틀리다. 중요한 프로세스일 수록 자원 할당에 있어 유리해야하기 때문이다. 이를 위해 사용하는것이 프로세스 우선순위이고 , 이러한 우선순위를 토대로 자원을 할당해준다.

스케줄링 큐

운영체제는 자원들을 프로세스에 할당할 때 스케줄링 큐라는 방식을 사용하여 할당한다.

스케줄링 큐란 것 자원을 필요로 하는 프로세스들을 모아놓은 자료구조이다.

스케줄링 큐 상태들

스케줄링 큐는 프로세스 상태에 따라 여러가지로 분류될 수 있다.

• 준비 큐 : CPU 이용을 기다리는 프로세스들의 큐
• 실행 큐 : CPU를 할당받아 실행 중인 프로세스가 있는 큐
• 대기 큐 : 대기 상태 프로세스들의 큐(입출력 요청이나 특정 이벤트를 기다리는 중)

이러한 큐 상태들을 프로세스의 상태와 함께 묶어 다음과 같이 볼 수 있다.

선점형 스케줄링과 비선점형 스케줄링

한 프로세스가 실행 도중 다른 급한 프로세스가 실행되어야 할 때 처리되는 방식은 두 가지가 있다.

1. 현재 실행 중인 프로세스의 자원을 빼앗아 해당 프로세스에게 할당 -> 선점형 스케줄링
2. 현재 실행 중인 프로세스 실행이 끝날 때 까지 해당 프로세스 대기 -> 비선점형 스케줄링

선점형, 비선점형 스케줄링 장단점

선점형 스케줄링

• 타임아웃 기반의 문맥교환
• 프로세스 자원을 고루 할당 가능
• 문맥 교환 과정의 오버헤드(문맥교환 자체도 비용 발생)

비선점형 스케줄링

• 고르지 않은 자원 분배
• 문맥 교환 과정에서의 오버헤드 적음

CPU 스케줄링 알고리즘

CPU 자원이 어떤식으로 프로세스들에게 배분 되는지를 다루는 것이 CPU 스케줄링 알고리즘이다.

CPU 스케줄링 알고리즘들은 다음과 같다.

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

선입 선처리 스케줄링 (FIFO 스케줄링)

• CPU를 먼저 요청한 프로세스부터 CPU 할당
• 준비 큐에 삽입된 순서대로 실행되는 비선점형 스케줄링
• 부작용 호위 효과(convoy effect) : 대기시간이 긴 앞에있는 프로세스 때문에 평균 대기시간이 길어짐

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

• 준비 큐 프로세스 중 CPU 이용 시간이 짧은 프로세스부터 실행
• 호위 효과 방지

라운드 로빈 스케줄링 (Round Robin 스케줄링)

• 들어온 순서대로 처리하지만 일정 시간 이상(타임 슬라이드) 작업시 다른 프로세스로 자원이 넘어감
• 선입 선처리 스케줄링 + 타임 슬라이드
• 준비 큐에 삽입된 순서로 실행하되, 타임 슬라이스만큼 실행
• 선점형 스케줄링

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

• 최단 작업 우선 스케줄링 + 라인드 로빈 스케줄링
• 작업 시간이 짧은 프로세스부터 처리하되, 타임 슬라이스만큼 돌아가며 처리

우선순위 스케줄링

• 프로세스마다 우선순위 부여, 우선순위 높은 순으로 스케줄링 앞에서 본 스케줄링 알고리즘도 여기에 해당된다 볼 수 있음
• 최단 작업 우선 스케줄링 - 작업 시간 짧은 순으로 우선순위 부여

• 최소 잔여 시간 스케줄링 - 남은 시간 짧은 순으로 우선순위 부여

• 부작용 아사(starvation) 현상
  • 모든 우선순위 스케줄링 알고리즘의 근본적인 문제
  • 우선순위가 낮은 프로세스의 실행이 계속 연기될 수 있음
  • 에이징 기법(대기 시간이 길어질 수록 우선순위를 높임)을 통해 해결할 수 있음

다단계 큐 스케줄링

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

큐를 여러개 사용하므로 여러 장점이 있음

• 프로세스 유형 별로 큐 구분 가능 ex) CPU 바운드, I/O 바운드, 백그라운드, 포그라운드, 실시간 프로세스…
• 큐 별로 다른 스케줄링 알고리즘 적용 가능 ex) 선입 선처리큐, 라운드 로빈 큐 …
• 큐 별로 다른 타임 슬라이스 적용 가능

단점으로는 프로세스가 큐 간 이동이 불가능함. 그로인해 역시 아사현상이 발생하기도 함. 이러한 문제를 해결한 다단계 큐 방식이 바로 다단계 피드백 큐 스케줄링임.

다단계 피드백 큐 스케줄링

• 프로세스가 큐 간의 이동 가능
• 높은 우선순위 큐에 삽입, 실행이 끝나지 않을 경우 낮은 우선순위 큐에 삽입
• 에이징 적용
• CPU bound, I/O bound 프로세스 구분 가능(CPU를 많이사용하는 프로세스와 그렇지 않은 프로세스)