CPU 스케줄링 개념과 알고리즘

 

 

CPU 스케줄링 개념

CPU 스케줄링은 여러 프로세스가 CPU를 공유하는 환경에서 프로세스들을 어떤 순서로 CPU에 할당할지 결정하는 작업을 말합니다. 이는 컴퓨터 시스템의 성능, 응답 시간, 처리량 등을 최적화하는 데 중요한 역할을 합니다. 다양한 CPU 스케줄링 알고리즘이 개발되어왔고, 각 알고리즘은 특정 상황이나 요구사항에 적합한 장단점을 가지고 있습니다. 

 

여기서 핵심은 운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것입니다. CPU 스케줄링은 컴퓨터 성능과도 직결되는 중대한 문제입니다.

 

 

스케줄링 큐

CPU입장에서 CPU를 사용하고 싶은 프로세스들이 많을 때, 먼저 CPU를 사용하겠다는 프로세스한테 CPU자원을 할당하는 단순한 방법이 있습니다. 하지만 프로세스마다 우선순위가 다르기 때문에 효율적이지 못한 방법입니다. 또한 입출력장치를 사용할 때는 프로세스 CPU작업을 하지 못하기 때문에 입출력장치 사용 빈도가 많으면 또다른 방법을 고안해내야 할 것입니다.

 

 

프로세스 우선순위는 ps -el 명령어를 통해 확인이 가능합니다. nice 명령어를 통해 일부 프로세스의 우선순위를 변경할 수 있습니다. 윈도우에서는 작업관리자에서 프로세스의 우선순위 확인과 변경이 가능합니다.

 

프로세스의 우선순위는 커널영역의 PCB에 담겨있습니다. CPU입장에서는 CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 프로세스의 PCB를 뒤지는 것은 비효율적입니다. 그래서 운영체제는 프로세스들에 줄을 서서 기다릴 것을 요구합니다. 운영체제는 이 줄을 스케줄링 큐로 구현하고 관리합니다.

 

 

운영체제가 관리하는 대부분의 자원은 큐로 관리됩니다. 큐의 특성상 선입선출이기 때문이죠. 대표적으로 준비 큐와 대기 큐가 있습니다. 준비 큐는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미하고, 대기 큐는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미합니다. 하지만 큐를 사용한다고 해서 모든 프로세스들이 선입선출은 아니며 우선순위가 높은 프로세스가 먼저 실행되는 구조입니다. 우선순위 큐라고 봐도 무방할 것 같습니다.

 

 

 

 

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

선점형(Preemptive) 스케줄링과 비선점형(Non-preemptive) 스케줄링은 CPU 스케줄링 알고리즘에서 프로세스의 CPU 할당 방식을 나타내는 두 가지 주요한 카테고리입니다.

 

1. 선점형(Preemptive) 스케줄링
   선점형 스케줄링은 현재 CPU를 사용하고 있는 프로세스를 다른 프로세스로 대체할 수 있습니다. 다시 말해, 다른 프로세스가 CPU를 사용하도록 선점할 수 있는 스케줄링 방식입니다. 선점형 스케줄링은 우선순위가 높은 프로세스가 도착했을 때 현재 실행 중인 프로세스를 멈추고 새로운 프로세스에 CPU를 할당합니다. 선점형 스케줄링은 우선순위 기반 스케줄링, 라운드 로빈(Round Robin) 스케줄링 등이 포함됩니다.

   예를 들어, 현재 실행 중인 프로세스 A가 있을 때 우선순위가 더 높은 프로세스 B가 도착하면 선점형 스케줄러는 프로세스 A를 멈추고 CPU를 프로세스 B에게 할당합니다.

 

선점형 스케줄링의 장점은 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다는 것입니다. 현재 사용하고 있는 프로세스가 긴 시간을 소모했을 때, 다른 프로세스가 이를 대체하지 못한다면 CPU자원을 독점할 수 있는 여지가 있습니다. 단점으로는 비선점 스케줄링보다 프로세스 대체가 많으므로 문맥 교환이 많아지면서 발생하는 오버헤드입니다.

 

2. 비선점형(Non-preemptive) 스케줄링
   비선점형 스케줄링은 현재 CPU를 사용하고 있는 프로세스가 끝날 때까지 다른 프로세스로 CPU를 대체하지 않습니다. 즉, 프로세스가 CPU를 스스로 반납할 때까지 CPU를 유지하는 스케줄링 방식입니다. 비선점형 스케줄링은 FCFS(First Come First Serve), SJF(Shortest Job First), 우선순위 기반 스케줄링(우선순위가 동일한 경우) 등이 포함됩니다.

 

   예를 들어, 현재 실행 중인 프로세스 A가 끝나기를 기다리고 있을 때 다른 프로세스 B가 도착하더라도 프로세스 A가 CPU를 스스로 반납하기 전까지 B는 CPU를 할당받을 수 없습니다.

 

비선점형 스케줄링의 장점으로는 선점형과 반대입니다. 오버헤드가 적지만 독점을 막을 수 없습니다.

 

 

 

CPU 스케줄링 알고리즘

 

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

선입 선처리(First Come First Served) 스케줄링은 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링입니다. 가장 직관적이고 언뜻 보기에는 공정해 보이나, 가끔은 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 단점이 있습니다.

 

예를 들어 17ms 동안 CPU를 이용하는 프로세스 A, 5ms 동안 CPU를 이용하는 프로세스 B, 2ms 동안 CPU를 이용하는 프로세스 C가 차례로 준비 큐에 삽입된다면 프로세스 c의 대기시간은 22ms입니다. 평균 대기 시간은 13ms입니다.

 

 

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

최단 작업 우선 스케줄링(Shortest Job First)는 CPU 사용 시간이 짧은 프로세스가 먼저 실행되는 알고리즘입니다.

앞서 얘기했던 FCFS 알고리즘에 비해 평균 대기시간이 3ms로 짧아진 것을 볼 수 있습니다. 언뜻 보면 가장 최고의 스케줄링 방식일 것 같지만, 최단 작업 알고리즘을 사용하기 위해서는 각 프로세스의 실행 시간을 미리 알고 있어야 합니다. 현실적으로 모든 프로세스의 실행 시간을 미리 예측하기는 어려울 수 있습니다. 예측이 부정확할 경우 스케줄링 성능이 저하될 수 있습니다. 또한 실행시간이 긴 프로세스는 계속해서 대기해야하는 단점이 있습니다.

 

 

라운드 로빈 스케줄링(RR)

라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해졌습니다. 타임 슬라이스는 프로세스가 CPU를 사용할 수 있는 시간으로 정해진 시간만큼만 사용하는 방식입니다. 즉 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링입니다. 만약 정해진 시간을 모두 사용했음에도 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입됩니다.

 

 

CPU 사용시간이 11ms, 3ms, 7ms이고 타임 슬라이스가 4ms인 라운드로빈 스케줄링을 한다면 위와 같은 형태입니다. 라운드 로빈 스케줄링에서는 타임 슬라이스의 크기가 매우 중요합니다. 타임 슬라이스가 크면 사실상 선입 선처리 스케줄링과 다를 바 없으며, 작으면 지나치게 많은 문맥 교환이 발생하기 때문입니다. 

 

 

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

최소 잔여 시간 우선 스케줄링(Shortest Remaining Time)은 최단 작업 우선 스케줄링(SJF)에 타임 슬라이스라는 개념이 더해졌습니다. 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택합니다.

 

 

우선순위 스케줄링(Priority)

우선순위 스케줄링은 프로세스에 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 알고리즘입니다. 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링합니다. 최단 작업 우선 스케줄링(SJF)와 최소 잔여 시간 우선 스케줄링(SRT)는 우선순위 스케줄링에 포함된다고 볼 수 있습니다.

 

 

우선순위 스케줄링의 근본적인 문제점이 있습니다. 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있습니다. 이를 기아(starvation) 현상이라고 합니다. 이를 해결하기 위해 에이징(aging) 기법을 도입합니다. 오랫동안 대기한 프로세스의 우선순위를 점차 올리는 방식입니다.

 

그렇게 되면 우선순위가 낮아도 언젠가는 우선순위가 높아지기 때문에 실행이 무기한 연기되는 것을 막을 수 있습니다.

 

 

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

다단계 큐는 우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 방식입니다. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고 그 큐가 비면 그 다음 우선순위 큐에 있는 프로세스를 처리합니다.

 

 

다단계 큐 스케줄링의 장점은 큐 별로 그룹을 묶어서 타임 슬라이스를 여러 개 지정할 수도 있고, 스케줄링 방식을 다르게 할 수도 있습니다. 우선순위 0은 최소 잔여 시간 우선 스케줄링을 적용하고, 우선순위 1은 라운드로빈 방식을 지정하고...이런 식으로요. 단점으로는 우선순위가 낮은 큐에 있는 프로세스들은 또한번 기아(starving)현상을 겪게 됩니다. 기본적으로 다단계 큐 스케줄링은 프로세스의 큐간 이동이 안되기 때문에 발생하는 문제입니다. 이 문제를 해결하기 위해 다단계 피드백 큐 스케줄링이 등장합니다.

 

 

다단계 피드백 큐 스케줄링(Multilevel Feedback Queue)

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태로서 큐 간의 이동이 가능한 다단계 큐 스케줄링입니다. 새롭게 준비 상태에 들어온 프로세스는 가장 높은 우선순위에 할당됩니다. 이 프로세스가 타임 슬라이스동안 실행이 끝나지 않으면 다음 우선순위 큐에 삽입되어 실행됩니다. 

 

정리하면 다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있는 방식이기 때문에 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 통해 기아 현상을 예방합니다. 또한 우선순위가 높은 큐에서 실행이 오래걸린다면 점차 우선순위가 낮은 큐로 이동시켜서 프로세스 우선순위의 밸런스를 맞춰갑니다.

 

다단계 피드백 큐 스케줄링은 구현이 조금 복잡할 수 있지만 효율적인 알고리즘이기 때문에 가장 보편적으로 쓰이는 CPU 스케줄링 방식으로 알려져 있습니다.

 

 

 

---

 

출처: 혼자공부하는 컴퓨터구조 + 운영체제