컴퓨터 과학에 대한 지식을 습득하고 정리하는 기록용 포스팅입니다.
예외를 판단하는 사고를 기르고, 효율적인 코드를 작성하기 위해
컴퓨터 과학 지식을 활용하는 것을 목표로 합니다.
✅ CPU 스케줄링 개요
📌 기본 개념
다수의 프로세스가 준비 상태에 있을 때, CPU가 어느 프로세스를 먼저 처리하도록 할 것인가를 결정하기 위한 작업. 이를 CPU 스케줄링이라 한다. 또한 Dispatcher는 CPU 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘깁니다. 이를 문맥 교환(Context Switch)라고 합니다.
디스패처(Dispatcher)는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이다.
📌 스케줄링의 단계
1. 장기 스케줄링(Long-term Scheduling)
- 장기 스케줄링은 고수준 스케줄링, 작업 스케줄링이라고도 한다.
- 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정한다.
- 가장 큰 틀에서 이루어지는 CPU 스케줄링으로 시스템 내의 전체 작업 수를 조절한다.
2. 중기 스케줄링(Medium-term Scheduling)
- 중기 스케줄링은 중간 수준 스케줄링이라고도 불린다.
- 중기 스케줄링은 이미 활성화가 된 프로세스들에 대한 관리를 한다. 이미 활성화된 프로세스들의 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는다.
- 운영체제는 처리가 보류된 프로세스들을 처리 재개가 가능할 때까지 주기억장치에서 하드 디스크로 옮기는데, 이 과정을 스왑 아웃(Swap out)이라고 부르고, 반대를 스왑 인(Swap In)이라 한다.
3. 단기 스케줄링(Short-term Scheduling)
- 단기 스케줄링은 가장 작은 단위의 스케줄링으로 저수준 스케줄링이라고도 불린다.
- 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다. 보통 CPU 스케줄링이라고 하면 바로 이 단계를 말한다.
📌 스케줄링의 목적
- 공평성 : 모든 프로세스가 자원을 공평하게 배정 받아야하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안된다.
- 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
- 안정성 : 우선 순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하는 프로세스로부터 보호해야 한다.
- 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야한다.
- 반응 시간 보장 : 응답이 없는 사용자는 시간이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야한다.
- 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다.
✅ 스케줄링 시 고려 사항
📌 선점형 스케줄링과 비선점형 스케줄링
1. 선점형 스케줄링(PreemptiveScheduling)
- '선점'은 빼앗을 수 있음을 뜻한다.
- 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.
- Timeout 상황, I/O Interrupt, System call 등.
- 문맥 교환 같은 부가적인 작업으로 인해 오버헤드가 발생한다.
2. 비선점형 스케줄링(Non-PreemptiveScheduling)
- 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.
- 문맥교환에 의한 낭비가 적지만, CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 될 수 있다.
📌 프로세스 우선순위
대부분의 CPU 스케줄러는 우선순위를 사용한다. 우선순위가 있다는 것은 프로세스의 중요도가 다르다는 의미이다.
프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉜다. CPU 스케줄러는 보통 커널 프로세스를 높은 우선순위에 둡니다.
📌 CPU bound process와 IO bound process
프로세스가 대기 상태에 있다가 CPU를 할당받아 실행하면 CPU burst, 입출력 작업을 하면 I/O burst라고 한다.
1. CPU bound process(CPU 집중 프로세스) : 수학 연산과 같이 CPU를 많이 사용하여 CPU burst가 많은 프로세스
2. I/O bound process(입출력 집중 프로세스) : 입출력을 많이 사용해 I/O burst가 많은 프로세스
두 프로세스 간에는 IO bound process를 먼저 실행상태로 옮기는 것이 효율적이다.
IO bound process의 경우 CPU를 할당받아도 금방 대기 상태로 빠지는 반면 CPU bound process의 경우 할당받은 CPU 시간을 전부 사용하는 경우가 많기 때문이다.
📌 전면 프로세스와 후면 프로세스
1. 전면 프로세스 : GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스. 사용자와 상호작용이 가능해 상호작용 프로세스라고도 불린다.
2. 후면 프로세스 : 사용자와 상호작용이 없는 프로세스이며, 사용자의 입력 없이 작동하여 일괄 작업 프로세스라고 불린다.
✅ CPU 스케줄링 알고리즘
📌 스케줄링 알고리즘의 선택 기준
- CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정.
- 처리량 : 단위 시간 당 작업을 마친 프로세스의 수.
- 대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기한 시간.
- 응답 시간 : 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸린 시간.
- 변환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두두 반환하는 데까지 걸리는 시간.
📌 선입 선처리(FCFS: First-Come First-Served) 스케줄링
- 프로세스들이 준비 대기열에 도착하는 순서에 따라 CPU를 할당하는 방식이다.
- 단순하고 공평하지만 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있다. 이를 호위 효과(Convoy effect)라고 한다.
📌 최단 작업 우선(SJF: Shortest Job First) 스케줄링
- 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU에 할당하는 방식이다.
- 작업 시간이 긴 프로세스의 처리가 계속해서 뒤로 밀리는 아사(starvation) 현상이 발생할 수 있다.
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다. 때문에 SJF 스케줄링을 사용하기 힘들다.
📌 라운드 로빈(RR: Round Robin) 스케줄링
- 각 프로세스에 동일한 크기의 시간(time slice)을 할당받은 후, 해당 시간 동안 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.
- 프로세스가 CPU를 일정 시간 동안 사용한 후 다른 프로세스에 주어야 하기 때문에 앞의 긴 작업을 무작정 기다리는 콘베이 효과가 줄어든다.
- 타임 슬라이스가 너무 큰 경우 FCFS 스케줄링과 다를게 없어진다.
- 타임 슬라이스가 너무 작은 경우 문맥 교환이 너무 자주 일어나 전반적인 성능이 떨어진다.
- 결론적으로 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요하다.
📌 최소 잔류 시간 우선(SRT: Shortest Remaining Time) 스케줄링
- SJF 스케줄링과 RR 스케줄링을 혼합한 방식이다. 기본적으로 RR 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.
- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 추가 작업 시간이 발생한다.
📌 우선순위(Priority Scheduling) 스케줄링
- 정수로 우선순위 값을 설정하여 스케줄링하는 방식이다. 즉, 우선순위가 높은 프로세스를 먼저 처리해주는 방식이다.
- 비선점형 방식과 선점형 방식에 모두 적용할 수 있다.
- 우선순위 스케줄링 역시 SJF처럼 Starvation 문제가 있을 수 있지만, Aging 기법을 사용하여 이를 해결할 수 있다. Aging이란 프로세스가 기다리는 시간이 길어질수록 우선순위를 높여 한 프로세스가 무한정 기다리지는 않도록 해주는 방법이다.
📌 다단계큐(MQ: Multilevel Queue) 스케줄링
- 프로세스 특성별로 준비 큐를 여러 개 두어 우선순위를 부여하고, 높은 우선순위 큐들이 모두 비었을 때만 다음 단계의 낮은 우선순위의 큐 프로세스들에게 CPU를 할당하는 방식이다.
- 한 번 우선순위가 매겨저 준비 큐에 들어가면 이 우선순위는 바뀌지 않는다.
- 각 큐에는 자체 스케줄링 알고리즘을 구현할 수 있다.
📌 다단계 피드백 큐(MFQ: Multi-level Feedback Queue) 스케줄링
- 현대 사용되는 CPU 스케줄링 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘이다.
- Multilevel Feedback Queue 역시 큐를 여러 개로 분할했다는 점에서는 Multilevel Queue와 동일하지만, 다른 점은 바로 프로세스가 다른 큐로 이동이 가능하다는 것이다.
- 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
- 반대로, 실행 중인 프로세스가 주어진 타임 퀀텀을 모두 소진한 후 CPU를 강제로 회수당하면, 이 프로세스는 계산 성향이 강해진 것으로 인식하여 이 프로세스를 입/출력 성향 기준 한 단계 낮은 준비 큐로 이동시킨다.
- 우선 순위가 낮은 프로세스가 낮은 프로세스가 우선 순위가 높은 프로세스보다 CPU를 얻을 확률이 여전히 낮다. 따라서 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정한다. 맨 마지막 큐는 FCFS 방식으로 처리된다.
✅ 참고
도서 : 쉽게 배우는 운영체제
https://kjhoon0330.tistory.com/m/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
https://kjhoon0330.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-2-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://boycoding.tistory.com/258
https://runa-nam.tistory.com/88
