[운영체제] CPU 스케줄링 알고리즘 - 3/5

CPU 스케줄링이란?

운영체제가 프로세스들에게 CPU 자원을 배분하는 과정입니다. 

 

그럼 어떤 기준으로 CPU 스케줄링을 해야 할까요?

프로세스는 우선순위가 존재합니다. 이는 사용자가 설정할 수도 있고 운영체제가 정할 수도 있습니다. 

 

예를들어)

입출력 작업이 많은 프로세스 (= 입출력 집중 프로세스)의 우선순위는 

CPU 작업이 많은 프로세스 (= CPU 집중 프로세스)의 우선순위보다 높습니다. 

왜 그럴까요?

입출력 집중 프로세스는 CPU 집중 프로세스보다 대기하는 시간이 많습니다. 대기상태엔 CPU를 사용하지 않는 상태이므로 입출력 집중 프로세스의 우선순위를 높여서 빨리 처리를 해버림으로써 CPU 집중 프로세스에 CPU를 집중적으로 할당할 수 있게 됩니다.

 

즉, 입출력 집중 프로세스한테 먼저 CPU를 할당해 주고, 빨리 작업을 끝내서 대기 상태로 보내놓고

CPU 집중 프로세스에게 CPU를 몰빵 해서 실행합니다.

 

프로세스 우선순위

프로세스 우선순위는 프로세스의 PCB에 저장이 됩니다. 

 

그런데 운영체제가 매번 프로세스들의 PCB를 확인해서 자원 이용 순서를 적용하는 건 비효율적입니다.

이때 이용하는 방법이 스케줄링 큐입니다.

 

스케줄링 큐

쉽게 말해 운영체제가 특정 자원을 이용하고 싶은 프로세스들에게 줄을 서라고 요구하는 것입니다. 같은 큐 내에서도 우선순위 별로 처리합니다.

[참고] 큐 자료구조는 선입선출이나, 스케줄링 큐에서 큐는 반드시 선입선출일 필요는 없습니다. 

 

스케줄링 큐의 대표적인 두 종류

• 준비 큐
  • 준비 상태의 프로세스가 CPU를 이용하기 위해 기다리는 줄
• 대기 큐
  • 대기 상태의 프로세스가 입출력장치를 이용하기 위해 기다리는 줄
  • 같은 장치를 요구한 프로세스들은 같은 큐에서 대기합니다.

 

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

상황 예시를 들어보겠습니다. 프로세스 A가 자기 차례가 되어서 CPU를 할당받아 실행 중에 있습니다. 이때 프로세스 B가 나타나서 '너무 급한 상황이라 그런데(= 우선순위 높음), CPU를 잠깐 써도 될까요?'라고 물어보는 상황입니다. 

 

이럴 때 해결하는 방법에는 두 가지가 있습니다. 

1. 현재 CPU를 사용 중인 프로세스 A로부터 CPU자원을 빼앗아 다른 프로세스 B에게 할당

➡ 선점형 스케줄링 (preemptive scheduling)

2. 현재 CPU를 사용 중인 프로세스 A의 작업이 끝날 때까지 프로세스 B는 기다리게 하기

➡ 비선점형 스케줄링 (non-preemptive scheduling)

 

하나씩 알아보겠습니다.

선점형 스케줄링

• 장점
  • 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다.
• 단점
  • 그만큼 문맥 교환이 자주 발생해서 문맥 교환 시 오버헤드 발생 가능성이 있다.

비선점형 스케줄링

• 장점
  • 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다.
• 단점
  • 모든 프로세스가 골고루 자원을 이용하기 어렵다.

CPU 스케줄링 알고리즘

스케줄링 알고리즘 중 대표적인 7가지를 배울 것입니다.  알고리즘 종류와 내용을 달달 외우는 것이 아닌

아이디어, 동작 방식, 장단점 위주로 체크하시는 것을 권장합니다. 

 

대표적인 스케줄링 알고리즘 7가지

• 선입 선처리 스케줄링
• 최단 작업 우선 스케줄링
• 라운드 로빈 스케줄링
• 최소 잔여 시간 우선 스케줄링
• 우선순위 스케줄링
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링 :  CPU 스케줄링 방식의 가장 일반적인 형태

선입 선처리 스케줄링 (First Come First Served)

준비 큐에 삽입된 순서대로 처리합니다. 먼저 CPU를 요청한 프로세스부터 CPU를 할당하는 비선점 스케줄링입니다. 

• 단점
  • 프로세스들이 기다리는 시간이 매우 길어질 수 있습니다. (= 호위 효과)

최단 작업 우선 스케줄링 (Shortest Job First)

호위 효과를 방지하기 위해 CPU 사용 시간이 긴 프로세스는 나중에, CPU 사용 시간이 짧은 프로세스는 먼저 실행하는 스케줄링 방식입니다. 

작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘

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

선입 선처리 스케줄링 + 타임 슬라이스(time slice) 

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

 

큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용 가능한 선점형 스케줄링입니다. 정해진 시간을 모두 사용했지만 아직 프로세스가 완료되지 않았다면 큐의 맨 뒤에 삽입(문맥교환)합니다. 

여기서는 타임 슬라이스 크기가 중요합니다.

• 타임 슬라이스 크기가 너무 크면 호위 효과가 생길 수 있고
• 타임 슬라이스 크기가 너무 작으면 문맥 교환 시 오버헤드가 발생 할 수 있습니다.

정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘

최소 잔여 시간 우선 스케줄링 (Shortest Remaining Time)

= 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링

정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스를 선택하는 스케줄링 알고리즘

우선순위 스케줄링

프로세스들에 우선순위를 부여하고 우선순위가 높은 프로세스부터 실행합니다. 

• 우선순위가 같은 프로세스들이 있다면 선입 선처리로 스케줄링합니다.
• 최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링 ⊂ 우선순위 스케줄링

우선순위 스케줄링은 근본적인 문제점이 존재하는데 이는 기아(starvation) 현상입니다.

• 우선순위가 높은 프로세스만 실행되므로 우선 순위가 낮은 프로세스는 실행이 계속해서 연기될 수 있는 현상입니다. 

 

기아현상을 해결할 대표적인 방법에는 에이징(aging)이 있습니다. 

• 오랫동안 대기한 프로세스의 우선순위를 점차 증가시키는 방법입니다. 우선 순위가 낮아도 시간이 지나면 언젠가는 우선순위가 높아질 수 있습니다.

다단계 큐 스케줄링 (Multilevel queue)

우선순위 스케줄링의 발전된 형태로 우선순위별 준비 큐(A, B, C)를 여러 개 사용하는 스케줄링 방식입니다.

• 우선순위가 가장 높은 큐(A)에 있는 프로세스들 먼저 쭉 처리
• 우선 순위가 가장 높은 큐가 비어있으면 그다음 우선순위 큐(B)에 있는 프로세스들을 처리합니다.

• 장점
  • 큐 별로 스케줄링을 달리 적용해서 프로세스를 유형별로 처리할 수 있습니다.
• 단점
  • 큐 간의 이동이 불가해서 기아 현상이 발생할 수 있습니다. 

 

이러한 단점을 해결하기 위해 등장한 스케줄링이 다음 방식입니다. 

다단계 피드백 큐 스케줄링 (Multilevel feedback queue)

다단계 큐 스케줄링 단점을 보완한 방식으로 큐 간의 이동이 가능한 스케줄링 방식입니다.

 

동작방식

• 우선순위대로 처리를 하면서 만약 할당된 시간 내 끝내지 못한 프로세스가 있다면, 다음으로 높은 우선순위 큐에 삽입해서 처리합니다.
• 이렇게 하면 CPU를 많이 사용해야 하는 프로세스의 우선순위가 낮아지게 됩니다.
• [정리] CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고, 입출력 집중 프로세스의 우선순위는 상대적으로 높아지게 됩니다. 

에이징 기법 적용

• 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다렸다면, 점차 우선순위를 높일 수 있습니다.

➡ 다단계 피드백 큐 스케줄링은 CPU 스케줄링 방식의 가장 일반적인 형태로 알려져 있습니다.

 

 

 

 

 

 

 

 

---

 

관련 포스팅:

1. [운영체제] 운영체제는 프로그램이다?! - 1/5

2. [운영체제] 프로세스와 스레드 - 2/5

3. [운영체제] CPU 스케줄링 알고리즘 - 3/5

4. [운영체제] 프로세스와 스레드의 동기화 - 4/5

5. [운영체제] 교착 상태(데드락, Deadlock) - 5/5

 

 

 

 

출처:

혼자 공부하는 컴퓨터구조+운영체제 도서

혼자 공부하는 컴퓨터구조+운영체제 강의