운영체제의 CPU 스케줄링

스케줄링이란?

• 운영체제가 CPU 자원을 어떤 프로세스에게 할당해 줄지 그 일정을 짜는 것

사용 이유

• Context Switching 과정은 많은 자원 손실을 발생시킨다. 따라서 이 일정을 어떻게 짰는지에 따라 CPU의 자원을 얼마나 효율적으로 사용하게 되는지가 결정된다.

Context Switching

먼저 Context Switching에 대해 알아가도록 하자

• Context : CPU가 프로세스를 실행하기 위한(프로세스에 대한) 정보
• 더 자세히 말하면! Context는 현재 프로세스의 상태, 즉 프로세스가 다음에 실행할 명령어, 레지스터 값, 프로세스 번호 등의 정보를 담고 있다.
• 이는 PCB(Process Control Block)에 저장된다.

그럼! 멀티 프로세스 환경에서는 여러 프로세스가 동시에(?) 실행되고, 이 환경에서는 필연적으로 프로세스 간 CPU 자원 할당 이동이 일어날 수밖에 없다! 이 과정을 Context Switching이라고 한다. CPU는 기존 할당된 프로세스의 Context를 저장하고, 새로 자원을 할당할 프로세스의 Context로 교체하는 과정을 거치면서 자원을 새로운 프로세스에게 할당하게 된다. 

여기서 주의사항!! -> Context Switching 중에는 CPU의 자원이 어떤 프로세스에게 할당된 상태가 아니기 때문에 CPU가 아무 일도 하지 못한다. 따라서 Context Switching과정이 너무 자주 발생하면 오히려 CPU 성능이 떨어진다.

★ 좀 더 정확히 하자면 할당이라는 단어를 썼지만 정확히는 프로세스가 점유 중이지만 사용 중은 아닌 상태다. 특정 프로세스에 의해 CPU 자원이 점유되고 있다. Context Switching 중이기 때문에 실제로 사용되는 프로세스가 없는 상태인 것이다. CPU가 아무 일도 하지 못한다는 것은 결국 CPU 자원을 아무 프로세스도 사용하지 못한다는 말이고 이는 오버헤드가 발생되었다는 뜻이다.

---

위의 설명처럼 컴퓨터가 효율적으로 일을 하기 만들기 위해선 Context Switching 과정을 쓸데없이 자주 반복하지 않도록 하고, 필요한 순간에 적절하게 하도록하는 알고리즘이 필요하다! 그리고 이 알고리즘을 사용하는 주체가 바로 운영체제 스케줄러다

 

스케줄링 알고리즘의 종류

Context Switching을 할 때 우선순위가 가장 높은 프로세스에게 CPU 자원을 할당해주는 것인데, 이 우선순위를 결정하는 방법은 크게 두 가지로 비선점 스케줄링과 선점 스케줄링이다. 

비선점 스케줄링

• 어떤 프로세스가 CPU를 점유하고 있다면 해당 프로세스의 작업이 완료될 때까지 다른 프로세스는 CPU를 사용할 수 없다.
• 프로세스가 CPU를 놓아주는 시점까지 스케줄링이 일어나지 않는다.
• 장점 : 프로세스 일괄처리에 적합하고 Context Switching을 최소화할 수 있다
• 문제점 : 다만 긴급히 처리되어야 할 프로세스가 처리되지 못할 수 있다.

FCFS (First Come First Service)

 

• 프로세스가 Ready Queue에 도착한 순서대로 CPU에 할당하는 방식
• 장점 : 작업 완료 시간을 예측하기 용이하다.
• 문제점 : CPU 처리 시간이 길지만 덜 중요한 작업이, CPU 처리 시간이 짧고 더 중요한 작업을 기다리게 할 수도 있다. 이 상태를 호위 상태(Convoy Effect)

SJF (Shortest Job First)

• 프로세스를 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식
• 장점 : 모든 방식을 통틀어 평균 대기 시간을 가장 짧게 만드는 방식이다.
• 문제점 : CPU 처리 시간이 긴 프로세스는 전체 시스템 성능 향상을 위해 희생하며 계속 Ready Queue의 뒤로 밀려나기 때문에 무한정 기다려야 하는 상황이 발생할 수 있다. 이 상태를 기아상태 (Starvation)

HRN (Highest Response Ratio Next)

• SJF 스케줄링 방식에서 발생할 수 있는 기아 상태를 해결하기 위해 고안된 방식
• 우선순위를 단순히 CPU 처리 시간으로 결정하지 않고, Ready Queue에서 대기한 시간까지 고려한다.
• 대부분 우선순위를 ((대기 시간 + CPU 처리 시간) / CPU 처리 시간)으로 결정한다.
• 기다린 시간에 비례하여 우선순위를 높이는 기법을 에이징(Aging)기법이라고 한다.

 

→ 지금까지의 알고리즘을 보면 SJF, HRN 등의 방식이 좋다고 느끼지만 사용하기 어려운 이유가 있다. 현실적인 상황에서는 프로세스마다 CPU 처리시간이 얼마나 걸릴지 알 수 있는 방법이 없기 때문이다. 

우선순위 (Priority)

• 대기 중인 프로게스들에게 우선순위를 부여, 높은 순서대로 처리
• 여기서도 에이징 기법이 사용되는데 우선순위가 낮은 프로세스에게 기아 상태가 생길 수 있기 때문이다.
• 우선순위는 정적 혹은 동적으로 부여될 수 있다.
• 동적 : 구현이 복잡하고 오버헤드가 많다. BUT 시스템의 응답속도를 증가시킨다.
• 정적 : 동적의 반대

 

선점 스케줄링

• 어떤 프로세스가 CPU를 점유하고 있을 때 우선순위가 높은 다른 프로세스가 점유를 빼앗아 CPU를 점유할 수 있다.
• 프로세스의 I/O 요청, I/O 응답, Interrupt 발생, 작업 완료 등의 특별한 상황에서 스케줄링이 발생한다.
• 장점 : 긴급히 처리되어야 할 프로세스를 처리할 수 있다.
• 문제점 : 비선점 스케줄링 방식에 비해 Context Switching이 자주 일어날 수 있다.

SRT (Shortest Remaining Time)

• SJF 스케줄링 방식을 선점 스케줄링 방식으로 변경한 기법
• SJF와 마찬가지로 프로세스를 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식
• 선점 스케줄링 방식이기 때문에 CPU를 점유 중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 Ready Queue에 들어올 경우 새로 들어온 프로세스가 기존 프로세스의 CPU 점유를 빼앗아 점유할 수 있다.

라운드 로빈 (Round-Robin)

• FCFS 스케줄링 방식에 선점 스케줄링 방식과 Time Quantum 개념을 추가한 방식
• 각 프로세스마다 CPU를 연속적으로 사용할 수 있는 시간에 제한을 둔다. ( 이 시간이 Time Quantum)
• 어떤 프로세스가 CPU를 사용한 시간이 Time Quantum만큼 지나면 이 프로세스로부터 CPU 자원을 회수하고, 이 프레서를 Ready Queue의 가장 뒤로 보내버린다.
• 라운도로빈 방식에선 Time Quantum을 얼마로 둘지 잘 결정해야 된다.
• 만약 크다면? -> CPU 처리 시간이 긴 프로세스가 CPU를 오래 점유하며 다른 프로세들은 작업이 끝날 때까지 기다려해서 결국 FCFS 스케줄링 방식에서 발생하던 호위 상태가 또 발생한다.
• 작게 둔다면? -> Contexgt Switching이 너무 자주 발생하기 때문에 오버헤드가 커진다.

다단계 큐 (Multi-Level Queue)

• 프로세스를 어떤 프로세스냐에 따라서 여러 종류의 그룹으로 나누고, 그룹마다 Queue를 두는 방식
• 한 마디로! Ready Queue를 여러 개로 나누어 사용하는 방식
• 각각의 Queue마다 서로 다른 스케줄링 방식을 적용할 수 있다.
• 사용자와 직접 상호작용하는 프로세스가 모인 Foreground Queue에는 응답 시간을 줄이기 위해 라운드 로빈 스케줄링 방식을 적용하고
• 백그라운드에서 돌아가는 프로세스가 모인 Background Queue에는 응답 시간이 큰 의미가 없이 때문에 FCFS 스케줄링 방식으로 적용하는 등 각 Queue마다 운영체제가 가장 적절하다고 판단하는 방식을 사용한다

• 다만! 다단계 큐 스케줄링 방식은 여러 개의 Queue를 사용하기 때문에 고려해야 할 점이 하나 있다.
• 바로 Queue에 얼마나 CPU를 오래 할당할지 결정하는 스케줄링이 필요! 크게 두 가지가 있다.

1. 고정 우선순위 (Fixed Priority)

• Queue마다 우선순위를 두는 방식
• 우선순위가 높은 Queue에 처리해야 할 프로세스가 남아 있다면! 무조건 그 Queue를 처리한 뒤에 다음 우선순위의 Queue를 서비스한다.
• 문제점 : 이 방식은 사용자가 직접 원하는 프로세스에 CPU 자원을 우선 할당하기 때문에 좋아 보이지만 SJF 스케줄링 방식처럼 결국 우선순위가 낮은 Queue에 있는 프로세스가 무한정 기다려야 하는 상황이 발생할 수 있다.

2. 타임 슬라이스 (Time Slice)

• 고정 우선순위 스케줄링 방식에서 기아 상태가 발생할 수 있기에 해결하고자 생긴 스케줄링 방식이다.
• 운영체제가 Time Slice를 두고, 이 시간 비율에 따라서 각각의 Queue를 서비스하게 된다. 
• 예를 들자면 CPU 자원의 75%는 Foreground Queue, 25%는 Backgoround Queue를 서비스하는데 할당할 수 있음

 

결론

우리는 컴퓨터를 사용할 때 수많은 프로세스를 동시에 실행하게 된다. CPU는 한 번에 한 가지 작업만 처리할 수 있기 때문에, 이 프로세스들을 동시에 처리하(는 것처럼)기 위해 CPU는 어떤 프로세스에게 얼마나 많은 자원, 시간 할당을 결정해야 된다. 이를 결정하는 CPU 스케줄링 방식에 비선점, 선점 방식으로 분류하고 수많은 방식이 존재한다.

 

 

출처

• cornswrold.tistory.com/127
• preamtree.tistory.com/19
• velog.io/@raejoonee/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%9D%98-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
•