[컴퓨터개론] - CPU 스케줄러

안녕하세요

이전시간에는 PCB와 문맥교환에 대해서 알아보았는데요. 두 개념을 설명하는 과정에서 잠깐 등장했던 CPU스케줄러를 기억하시나요??

오늘은 그 CPU 스케줄러에 대해서 자세하게 이야기해보려고 합니다.

 

스케줄러란?

우리가 아는 스케줄의 뜻과 같습니다. 작업의 일정을 계획하고 수립하는 것이 바로 스케줄러입니다.

 

 스케줄러의 목표

• CPU 이용률 최대화: CPU가 항상 작업을 하고 있어 자원이 낭비되지 않도록 합니다.
• 처리량 최대화: 단위 시간당 완료된 프로세스 수를 늘리는 것이 목표입니다.
• 대기 시간 최소화: 프로세스가 준비 큐에서 대기하는 시간을 최소화합니다.
• 응답 시간 최소화: 프로세스가 요청된 후 첫 번째 응답을 받을 때까지의 시간을 줄이는 것이 중요합니다.
• 공정성: 모든 프로세스가 균등하게 CPU 자원을 받을 수 있도록 보장하는 것입니다.

 

역할에 따른 스케줄러의 종류

스케줄러는 역할에 따라 장기, 중기, 단기 총 세가지로 나뉩니다.

1. 장기 스케줄러 

: 프로세스가 디스크에서 메모리로 이동하여 실행되도록 선택하는 스케줄러

이 스케줄러는 실행해야 할 여러 개의 프로세스 중에서 어떤 것을 준비상태로 옮길지를 경정해줍니다. 이 스케줄러는 CPU할당할 프로세스를 전체적으로 관리하기 때문에 장기라는 이름을 지니고 있으며, 이를 통해 프로세스 부하를 조절해줍니다.

프로세스라는 큰 단위를 관리하고 있기때문에 다른 스케줄러에 비해서 상대적으로 드물게 실행됩니다.

2. 중기 스케줄러 

: 스왑을 통해 메모리에서 일부 프로세스를 일시적으로 내보내거나 다시 가져오는 스케줄러

메모리의 사용량을 조절하기 위해서 프로세스를 중단시켜 아웃시키거나, 나중에 다시 실행시키기 위해 가져오는 역할을 합니다. 

여기서 스왑이라는 개념이 사용되는데, 이건 말 그대로 교체작업을 진행한다는 뜻으로, 프로세스를 잠시 중단시키고 swap out하여 내보내기, 프로세스를 다시 실행시키기 위해 디스크에 내보냈던 프로세스를 다시 swap in하여 가져오는 작업입니다.

 

3. 단기 스케줄러 

: 준비 상태에 있는 프로세스들 중, 어떤 프로세스를 CPU에 할당해야할지 즉각적으로 결정하는 스케줄러

장기, 중기 작업으로 인해 대기중인 여러 프로세스들 중에서 어떤 것이 우선순위인지 파악하여 CPU에 할당합니다.

이 작업은 실행할 프로세스를 빠르게 선택하고 할당해야하기 때문에 실시간으로 자주 실행되는 스케줄러로 단기 스케줄러입니다. 

이 단기 스케줄러가 직접적으로 CPU 할당을 맡고 있기에 가장 자주 사용되면서도 가장 중요한 스케줄러라고 할 수 있으며, 다른 말로 CPU 스케줄러라고도 불립니다.

 

이 세가지의 스케줄러 중, 우리는 단기 스케줄러에 대해서 집중적으로 알아봅니다.

---

CPU 스케줄러

역할은 위에서 이야기 한 바와 같고, 정확한 역할을 나누어 서술하자면 아래 세가지로 분류할 수 있습니다.

• 프로세스 선택: 실행 가능한 여러 프로세스 중에서 어느 프로세스를 CPU에 할당할지를 결정합니다.
• CPU 할당: 선택된 프로세스를 CPU에서 실행하도록 할당합니다.
• 프로세스 전환: 할당된 시간이 끝나거나, 입출력 대기 등으로 프로세스가 중단될 때 다른 프로세스로 교체하여 CPU를 효율적으로 사용합니다.

 

CPU 스케줄링 알고리즘

CPU 스케줄러는 다양한 스케줄링 알고리즘을 사용하여 프로세스를 선택합니다. 

스케줄링 알고리즘은 총 4가지의 기준에 따라 성능이 평가되며, 운영체제는 프로세스 관리와 시스템 성능의 요구에 따라 적절한 알고리즘을 선택하여 실행하는 방법으로 진행됩니다.

4가지의 기준은 아래와 같습니다.

 

• CPU 이용률: CPU가 작업에 얼마나 많이 사용되는지를 나타내는 지표-> 적을수록 좋음
• 처리량: 단위 시간당 얼마나 많은 프로세스를 완료했는지에 대한 지표-> 많을수록 좋음
• 대기 시간: 프로세스가 CPU를 할당받기 위해 대기하는 평균 시간-> 빠를수록 좋음
• 응답 시간: 프로세스가 처음으로 응답을 받는 데 걸리는 시간-> 빠를수록 좋음

그리고 이러한 알고리즘은 선점형, 비선점형 두가지로 나뉠 수 있습니다.

상태에 따른 CPU 스케줄러 알고리즘의 분류

1. 선점형 스케줄러

: 프로세스가 CPU를 사용 중이라도, 더 높은 우선순위를 가진 프로세스가 등장하면 현재 프로세스를 중단하고 CPU를 빼앗아 다른 프로세스에게 할당합니다.

 

현재 사용되는 대부분의 운영체제는 선점형으로 통해 진행됩니다.

추가로, 이 선점형 스케줄러를 사용하게 된다면 race condition이 발생할 수 있다고 합니다. 

 

예: 라운드 로빈(Round Robin), SRTF(Shortest Remaining Time First), 다단계 큐, 다단계 피드백 큐

2. 비선점형 스케줄러

: 한 번 CPU를 할당받은 프로세스는 스스로 종료되거나, I/O 작업을 위해 스스로 CPU를 반납하기 전까지 계속 CPU를 사용합니다. 

CPU가 반납될 때까지 기다려야 하기 때문에 선점형에 비해 문맥교환의 빈도가 적기 때문에 오버헤드가 적습니다.

하지만 새로운 작업이 들어오더라도 자신의 순서를 하염없이 기다려야 하기 때문에 대기시간이 길 수 밖에 없어 즉각적으로 반응해야하는 프로그램들에는 치명적인 방식입니다.

 

예: FCFS(First-Come, First-Served), SJF(Shortest Job First), 우선순위(Priority), HRN(Heighest Response Next)

 

이제 스케줄링 알고리즘의 종류에 대해서 상세히 설명해보도록 하겠습니다

 

1) FCFS (First-come, First-Served)

: 먼저 도착한 프로세스가 먼저 실행되는 방식으로, 큐(Queue) 와 비슷한 구조입니다.

 

구현이 간단하지만, 긴 프로세스가 먼저 오게되면 뒤에 있는 짧은 프로세스들이 오랫동안 기다려야 하기에 시간을 효율적으로 활용하지 못하는 콘보이 효과(Convoy Effect) 가 발생할 가능성이 큽니다

2) SJF (Shortest-Job-First)

: 짧은 것부터 실행하는 방식입니다.

 

위의 FCFS의 콘보이 효과를 보완할 수 있습니다. 대기시간을 줄인다는 가장 큰 장점이 있어 모든 알고리즘들 중 평균 대기시간이 가장 짧습니다. 또한 짧게 끝낼 수 있는 프로세스들을 먼저 실행시키기 때문에 프로세스의 수 또한 최소화할 수 있습니다.

여기서 프로세스의 시간은 과거 실행 시간을 기반으로 Exponential Averaging 기법을 사용해 다음 실행 시간을 예측할 수 있습니다.

하지만, 프로세스의 실행 시간을 미리 예측하기 어려운 경우들이 존재하기 때문에 실직적인 적용이 어려울 수 있습니다. 또, 짧은 프로세스들이 게속 들어오게 되는 상황인 경우, 결국 길이가 긴 프로세스는 계속해서 실행되지 못하고 무한한 기다림의 시간을 가지게 되는 Starvation 문제가 발생할 수 있습니다.

 

+ SJF 는 크게 Nonpreemptiver SJF, Preemptive SJF 두가지로 다시 나뉘게 되는데, 이는 프로세스가 종료되거나 새로운 프로세스가 들어올 때마다 어떤 프로세스의 실행시간이 가장 작은지 판별하여 가장 작은 프로세스를 문맥교환하는 방법이 존재하느냐의 여부로 갈립니다.

 

3) HRN (Hightest Response-ratio Next)

: SJF의 단점을 보완하여 우선순위를 계산하고, 우선순위에 다라 프로세스를 실행하는 방식입니다.

동적으로 대기 시간과 실행 시간을 기반으로 우선순위를 계산하여 SJF의 단점을 보완합니다.

 

우선순위 = (대기시간+실행시간)/(실행시간)

 

4) 라운드 로빈(Round Robin, RR)

: 각 프로세스에 동일한 CPU 할당 시간(Time Quantum)을 부여하며, 시간 초과 시 다음 프로세스로 전환하는 방식입니다.

 

평균적으로 SJF에 비해서는 대기시간이 긴 편이지만 이 방식은 공정하게 모든 프로세스가 CPU를 사용할 수 있게 해주기 때문에 starvation 또한 발생하지 않는다는 장점을 가지고 있습니다.

하지만 여기서 설정한 CPU 할당시간( Time Quantum)이 너무 길면 대기 시간이 FCFS와 비슷해지는 성능을 보이고, 길이가 비슷한 프로세스들을 수행시키는 과정에서 대기시간이 증가한다는 문제점이 있습니다.

CPU할당시간이 (Time Quantum) 또 너무 짧으면 선점형방식의 특징으로 인해 문맥 교환 오버헤드가 커질 수 있습니다.

 

때문에 일반적으로 타임 퀀텀은 프로세스 실행 시간의 평균보다 짧아야 하고, 문맥 교환 오버헤드가 지나치게 커지지 않도록 조정해야 합니다. 이 부분을 고려하는 것이 중요한 포인트입니다.

5) 우선순위 (Priority)

:우선순위가 높은 프로세스들부터 먼저 수행하는 방식

앞서 설명한 SJF또한 이 우선순위 스케줄링에 해당합니다. 중요한 작업을 빠르게 처리할 수 있다는 장점이 있지만 우선순위가 낮은 프로세스가 계속 실행되지 않는 기아(Starvation)현상이 발생할 수 잇습니다. 이에 대한 해결책으로는 Aging로, 각각의 프로세스마다 시간이 지날수록 우선순위를 높여주는 방식이 있습니다.

이 스케줄링 기법은 중기 스케줄러와 장기 스케줄러에서도 보편적으로 사용되는 스케줄링입니다.

 

6) 멀티레벨 큐(Multileve Queue)

: 멀티레벨이라는 이름에 걸맞게 여러 개의 큐를 가지고 있으며, 각 큐에 우선순위에 따라 프로세스를 분류하고 우선순위에 따라 각자의 알고리즘을 수행하여 스케줄링을 진행하는 방식

이 방식을 통해 우선순위가 낮은 큐들도 실행할 수 있게 되고, 각 큐마다 다양한 종류의 프로세스 요구를 반영할 수 있습니다.

효율적인 방법이라고 생각될 수 있지만, 이 방법의 경우 여러 개의 큐를 사용하는 만큼 큐 간의 전환과정이 복잡할 수 있다는 단점을 가지고 있기도 합니다.

 

7) 멀티레벨 피드백 큐 (Multilevel-Feedback-Queue)

: 위의 멀티레벨 큐의 발전형으로 멀티레벨 큐에서 CPU 할당 시간(Time Quantum) 을 다 채운 프로세스를 충분히 작동시켰닥 판단하여 하위 우선순위 큐로 내리는 방식

이 방식을 사용하면 입출력과 같은 값을 작업들에게 우선순위를 줄 수 있으므로, 입출력시간이 빠르고, 평균 대기시간 또한 줄어든다는 장점이 잇습니다.

 

멀티레벨 큐와 멀티레벨피드백큐의 차이로는 멀티레벨 큐는 각 큐가 고정된 우선순위를 가지며, 프로세스가 하나의 큐에서만 처리됩니다. 반면, 다단계 피드백 큐는 프로세스가 하위 큐로 이동할 수 있도록 설계되어, 자원이 오래 걸리는 프로세스는 우선순위가 낮아지게 만들며 자주 실행되지 않는 프로세스를 적절히 처리할 수 있습니다.

 

8) 실제 시간? Real-time 

: 데드라인이 있는 프로세스를 지키기 위해 존재하는 방법

주로 주로 임베디드 시스템이나 제어 시스템, 로봇 공학에서 시간 내에 작업을 완료해야하는 경우 사용되는 방법입니다.

Rate Monotonic Scheduling (RMS)와 Earliest Deadline First (EDF) 두가지 방법으로 나뉘게 되며, 이 방법에 대한 자세한 내용은 다루지 않겠습니다.

궁금하면 아래 자료를 참고하면 좋을 것 같네요!

https://ddongwon.tistory.com/35

프로세스 스케줄링_4 (Real-time System)

 

너무 많은 소개를 했기 때문에 각 알고리즘에 대해서 짧게 요약해보겠습니다.

 

FCFS (First-Come, First-Served): 먼저 도착한 프로세스부터 순서대로 실행하는 방식으로, 긴 프로세스가 먼저 오면 짧은 프로세스들이 오래 기다릴 수 있는 콘보이 효과가 발생할 수 있습니다.

SJF (Shortest-Job-First):짧은 작업부터 먼저 실행하는 방식으로, 대기 시간을 최소화하지만 긴 작업은 기아 문제가 발생할 수 있습니다.

HRN (Highest Response-Ratio Next): SJF의 기아 문제를 해결하기 위해 대기 시간과 실행 시간을 고려한 동적 우선순위로 프로세스를 실행하는 방식입니다.

라운드 로빈 (Round Robin): 각 프로세스에 **동일한 CPU 할당 시간(Time Quantum)**을 부여하고 시간 초과 시 다음 프로세스로 전환하는 방식으로 공정성을 보장하지만 문맥 교환 오버헤드가 있을 수 있습니다.

우선순위 스케줄링 (Priority Scheduling): 프로세스에 미리 설정된 우선순위에 따라 실행하는 방식으로, 기아 문제를 해결하기 위해 Aging 기법을 사용할 수 있습니다.

멀티레벨 큐 (Multilevel Queue): 프로세스를 여러 큐로 분류하고 각 큐에서 서로 다른 스케줄링 알고리즘을 적용하는 방식으로, 큐 간 전환 과정이 복잡할 수 있습니다.

다단계 피드백 큐 (Multilevel Feedback Queue): 멀티레벨 큐에서 CPU 할당 시간을 다 채운 프로세스를 하위 큐로 이동시키는 방식으로, 입출력 시간을 줄이고 대기 시간을 최적화할 수 있습니다.

실시간 스케줄링 (Real-time Scheduling): 마감 시간(Deadline)을 맞추기 위해 RMS나 EDF 같은 실시간 스케줄링 알고리즘을 사용하여 시간 내에 작업을 완료하는 방식

 

---

여기까지 스케줄러에 대해서 간단하게 알아보았습니다.

양이 너무 많아!! 타쿠씨 나오세요 ..

아직도 어려워서 이해가 안가는 부분이 많네여 ,,ㅠ

그럼 다음 글로 찾아뵙도록 하것씁니다.

20000

 

---

https://github.com/Seongwon97/tech-interview/blob/main/Q&A/OS_Q&A.md