CPU 스케줄링
CPU 스케줄링
개요
프로세스는 생성, 준비, 실행, 대기와 같은 여러 상태를 거치며 작업이 이루어진다. CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.
위의 사진의 빨간 동그라미가 스케줄러가 하는 일인데 이는 CPU가 놀지 않도록 프로세스를 선택해주는 역할을 한다. 중요한건 선택하는 역할을 한다는 것이다. 예를들면 러닝하던 프로세스가 다른 상태로 변경될 경우 CPU가 놀기 되는데 이 때 CPU가 다시 일을 하도록 어떤 프로세스를 CPU가 쓸지 선택해줘야 한다. 이 때 선택을 스케줄러가 해주게 되는 것이다.
즉 위에서 모든 상태 변화를 조정하는 역할을 한다고 했는데 정확히는 CPU Scheduler는 CPU에서 실행될 프로세스를 선택하는 역할을 한다.
ready상태에선 ready상태에 있는 프로세스들을 모아놓는 ready queue가 존재한다. 이 ready queue에 앞으로 cpu에 실행될 프로세스들이 대기하는데 여기서 어떤 프로세스가 실행될지를 스케줄러가 선택해주게 된다.
Dispatcher
여기서 잠깐 Dispatcher에 대해 알고 넘어가자.
위에선 CPU Scheduler, 즉 Scheduler에 대해 다뤘다면 이제 dispatcher를 알아보자. 위에 Scheduler Dispatcher가 Ready상태의 Process를 Running상태로 만들어주는걸 볼 수 있다. Scheduler는 어떤 프로세스를 실행할지 선택해주었다. 그
러면 선택된 프로세스를 실제로 실행상태로 만들어줘야 하는데 이를 dispatcher가 하게되는 것이다. 이전에 이야기한 Context Switching을 Dispatcher가 하게 된다. 이 Context Switching은 OS에서 민감하게 다뤄야 하기 때문에 커널모드에서 실행된다.
그런데 새로운 프로세스가 실행될 때 유저모드로 넘어가 새로운 프로세스를 선택하게 된다. 즉 컨트롤을 넘겨주게 된다. 이 유저모드의 프로세스를 OS 커널로 넘겨줘야 하는데 이를 전환하는 역할을 하는 것도 dispatcher가 하게 된다.
그리고 위에서 넘어간 프로세스가 실행되어야 할 위치로 이동시켜주는 역할도 dispatcher가 하게 된다.
즉 위의 기능을 요약하면 선택된 프로세스에게 CPU를 할당하는 역할을 한다.
CPU 스케줄러는 관리의 범주를 나누어 스케줄링을 한다. CPU 스케줄링은 규모에 따라 고수준 스케줄링, 중간 수준 스케줄링, 저수준 스케줄링으로 구분된다.
선점형 스케줄링과 비선점형 스케줄링
선점은 빼앗을 수 있음을 뜻하고 비선점은 빼앗을 수 없음을 뜻한다.
비선점 스케쥴링
위에서 아까 사진을 다시 보면 running에서 exit로 넘어가는 경우, I/O작업을 하는 경우 그리고 자발적으로 ready상태로 넘어가는 경우 총 3가지 경우에 대해서만 OS에서 개입을 하여 스케쥴링을 하는 것을 Nonpreemptive scheduling, 즉 비선점 스케줄링이라고 한다.
이렇게 불리는 이유는 프로세스가 자발적으로 running상태로 빠져나가기 때문이다. 운영체제가 강제적으로 개입하는 것이 없기 떄문에 비선점 스케쥴링이라고 한다.
비선점형 스케줄링은 선점형 스케줄링보다 스케줄러의 작업량이 적고 문맥 교환에 의한 낭비도 적다.그러나 CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다. 과거 일괄 작업 시스템에서 사용하던 방식이다.
즉 신사적이고 협력적(cooperative)하다. 반면 응답성이 느리다. trade off 관계니까 당연한 것이다. 강제로 뺏지 않고 프로세스가 자발적으로 양보하여 협력하기 때문에 느리다. 즉 그 프로세스가 CPU를 오래 선점하고 있으면 사용자 입장에서는 응답성이 느리게 느껴지게 된다.
선점 스케쥴링
선점 스케쥴링은 위의 경우를 모두 포함하며 이에 더해 강제로 running상태의 프로세스를 os가 개입을 하여 ready상태로 바꾸는 기능이 있다.
즉 이름 그대로 CPU를 충분히 다 쓰지 않았음에도 강제로 Ready 상태로 바꿀는 스케줄링 방식을 말한다. 대표적인 예로 인터럽트 처리가 있다.
선점형 스케줄링은 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생기는 것이 단점이다. 그러나 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다. 대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용한다.
따라서 적극적, 강제적이며 빠른 응답성을 가지고 있지만 데이터 일관성 문제가 발생할 수 있다.
선점형 스케줄링 방식의 스케줄러에도 비선점형 프로세스가 있을 수 있다. 예를 들어 시스템을 백업하는 프로세스는 비선점형으로 작동한다. 비선점형과 선점형 프로세스가 혼재하는 경우 비선점형 프로세스의 중요도를 매우 낮게 설정하여 선점형 프로세스에 영향을 덜 미치게 한다.
요약 및 정리
- 선점형 스케줄링 : 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.
- 비선점형 스케줄링 : 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.
| 구분 | 선점형 | 비선점형 |
|---|---|---|
| 작업 방식 | 실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행 가능 | 실행 상태에 있는 작업이 완료되기 전까지 다른 작업 실행 불가 |
| 장점 | 프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합 | CPU 스케줄러의 작업량이 적고 문맥 교환의 오버 헤드가 적음 |
| 단점 | 문맥 교환의 오버헤드가 많음 | 기다리는 프로세스가 많아 처리율이 떨어짐 |
| 사용 | 시분할 방식 스케줄러에 사용 | 일괄 작업 방식 스케줄러에 사용 |
| 중요도 | 높음 | 낮음 |
고수준 스케줄링
가장 큰 틀에서 이루어지는 CPU 스케줄링을 고수준 스케줄링(high level scheduling) 또는 장기 스케줄링(long-term scheduling), 작업 스케줄링(job scheduling)라고 한다. 많은 작업을 동시에 하면 시스템에 과부하가 걸려 작업이 원활하게 이루어지지 않는다.
고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것을 말한다. 여기서 작업은 운영체제에서 다루는 일의 가장 큰 단위로, 1개 또는 여러 개의 프로세스로 이루어진다.
고수준 스케줄링은 작업 요청이 오면 스케줄러가 시스템의 상황을 고려하여 작업을 승인할지, 거부할지를 결정하므로 고수준 스케줄링을 승인 스케줄링(admission scheduling)라고도 한다. 고수준 스케쥴링에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 총개수가 정해진다.
저수준 스케줄링
고수준과 반대로 가장 작은 단위의 스케줄링을 저수준 스케쥴링(low level scheduling)이라고 한다.
CPU 스케줄러 입장에서 저수준 스케줄링은 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다. 준비 상태에 있는 프로세스 중 하나를 골라 실행 상태로 보내고, 실행 상태에 있는 프로세스를 대기 상태로 보내며, 대기 상태를 준비 상태로 보내는 것이 그 예이다. 프로세스 상태에 관한 내용은 대부분 저수준 스케줄링에 해당한다.저수준 스케줄링은 아주 짧은 시간에 일어나기 때문에 단기 스케줄링(short-term scheduling)리고 부른다.
중간 수준 스케줄링
중간 수준 스케줄링(middle level scheduling)은 고수준 스케줄링과 저수준 스케줄링 사이에 일어나는 스케줄링이다. 고수준 스케줄링은 프로세스를 활성화할지 말지를 결정하며 전체 프로세스의 수를 조절하는 방식이지만, 프로세스가 활성화된 후에도 여러가지 사정으로 시스템에 과부화가 걸릴 수 있다.
중간 수준 스케줄링은 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는다. 즉 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스가 잘 돌아가도록 한다. 이는 프로세스의 상태 중 보류 상태에 해당하며, 저수준 스케줄링이 원만하게 이루어지도록 완충하는(buffer) 역할을 한다.
정리
작업 대기 -> 보류 프로세스 (고수준 스케줄링)
보류 프로세스 <-> 활성 프로세스 (중간 수준 스케줄링)
활성 프로세스 <-> 실행 프로세스 (저수준 스케줄링)
-> 작업 종료
고수준 스케줄링
고수준 스케줄링에서는 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정한다. 이 결정에 따라 전체 프로세스 수가 결정되는데 이를 멀티프로그래밍 정도(degree of multiprogramming)라고 한다.
중간 수준 스케줄링
시스템의 부하를 조절하려면 고수준 스케줄링 대신 중간 수준 스케줄링을 고려한다. 과부화가 걸리면 활성화된 프로세스를 보류 상태로, 여유가 생기면 다시 활성화한다.
저수준 스케줄링
실제로 작업이 이루어지는 스케줄링 단계이다. 오늘날의 CPU 스케줄러는 대부분 중간 수준 스케줄링과 저수준 스케줄링으로 구성되어 있다. 어떤 기준에 따라 타임 슬라이스를 정할지 등은 시스템의 성능에 많은 영향을 미친다. CPU 스케줄러는 특별한 명시가 없는 한 저수준 스케줄러를 의미한다.
스케줄러의 목적
CPU 스케줄링의 원래 목적은 모든 프로세스가 공평하게 작업하도록 하는 것이다. 즉 특정 프로세스가 시스템 자원을 독점하거나 파괴하는 것을 막기 위해 중요도에 따라 우선순위를 배정해야 한다. 또한 시스템 자원을 효율적으로 배분하여 전체적인 시스템의 성능도 높여야 한다.확장성도 고려해야 하는데, 확장성은 프로세스의 개수가 증가해도 성능에 갑작스러운 변화가 없어야 함을 의미한다.
CPU 스케줄링의 목적
- 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안 된다.
- 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
- 안정성 : 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
- 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
- 반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
- 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.
보통은 모든 프로세스가 공평하게 CPU를 받는다. 그러나 시스템의 안정성과 효율성을 높이기 위해 다른 프로세스보다 먼저 처리해야 하는 프로세스가 있으므로 CPU 스케줄러는 일정 부분 공평성을 희생한다.일반적으로 운영체제 프로세스는 일반 프로세스보다 우선적으로 CPU를 배정받는다. 또한 일반 프로세스 간에도 우선순위에 따라 CPU 배정 순서가 달라진다.
다중 큐
우선 순위에 따라 여러개의 큐를 만들어 관리하는 큐이다.
준비 상태의 다중 큐
프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막(tail)에 삽입된다. 프로세스의 우선순위를 배정하는 방식에는 고정 우선순위(static priority)방식과 변동 우선순위(dynamic priority)방식이 있다.
- 고정 우선순위 방식 : 운영체제가 프로세스에 우선순위를 부여하면 끝날 때까지 바뀌지 않는 방식
- 변동 우선순위 방식 : 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식
대기 상태의 다중 큐
대기 상태에도 다중 큐를 사용한다. 대기 상태는 입출력이 완료되기를 기다리는 프로세스가 모여 있는 곳이다. 시스템 내에는 다양한 입출력장치가 있기 때문에 대기 상태의 프로세스를 한 곳에 모아놓으면 관리하기 어렵다.
스케줄링 알고리즘
선택 기준
- CPU 사용률 - 이상적인 수치는 100이지만 90%가 보통 최대이다.
- 처리량 - 작업을 마친 프로세스의 수로, 클수록 좋은 알고리즘이다.
- 대기 시간 - 요청시 대기하는 시간, 이 시간이 짧을수록 좋다.
- 응답 시간 - 프로세스 시작 후 출력 또는 반응이 나올때까지 걸리는 시간, 짧을수록 좋음
- 반환 시간 - 생성 이후 종료하고 자원 반환까지 걸린 시간, 즉 프로세스 시작부터 끝
비선점형 스케줄링
FCFS(First Come Firset Served) 스케줄링의 동작 방식
준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식. 단점은 비선점형과 똑같다. 실행시간마다 프로세스 점유 시간 차이가 심하다.
SJF(Shortest job First) 스키줄링의 동작 방식
실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식, 최단 작업 스케줄링이라고도 한다. 시스스템의 효율성은 좋아지지만 공평하지 못하고 프로세스 종료 시간을 정확하게 예측하기가 어렵다.
HRN(Highest Response Ratio Next) 스케줄링의 동작 방식
SJF 스케줄링에서 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘, 최고 응답률 우선 스케줄링이라고 한다. 서비스 대기시간과 CPU 사용 시간을 같이 고려한 방식이다. SJF보단 좋지만 여전히 공평성이 위배되어 사용하지 않는다.
선점형 스케줄링
라운드 로빈 스케줄링의 동작 방식
순환 순서 방식으로 한 프로세스가 할당받은 타임 슬라이스동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. 선점형중 가장 단순하고 대표적인 방식, 완료할때까지 계속 순환한다. 타임 슬라이스를 적절히 하도록 하는것이 중요하다.
SRT(Shortest Remaining Time) 스케줄링의 동작 방식
SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로, 최소 잔류 시간 우선 스케줄링이라고도한다. 즉 SJF스케줄링을 선점형으로 바꾼것이다. 기본적으로는 라운드로빈을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택하는 방식이다. 대기시간은 짧지만 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에 없는 작업이 추가된다. 또한 아사 현상과 , 종료시간 예측이 어렵다는 점에서 좋지 않다.
우선순위 스케줄링의 동작 방식
우선순위를 가지고 스케줄링 하는 방식이다. 이 방식은 선점형과 비선점형 둘 다 가능하다. SJF, HRN, SRT에 각각 우선순위를 적용한다. 하지만 아사현상 문제는 그대로 있다.
다단계 큐(multilevel queue) 스케줄링
우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 우선 순위에 따라 다양한 스케줄링이 가능한 선점형 방식이다. 다단계 큐 스케줄링은 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다.이러한 문제로 낮은 프로세스의 작업이 연기되는데, 이런 문제를 해결하기 위해 나온 것이 다단계 피드백 큐 스케줄링이다.
다단계 피드백 큐(mulitlevel feedback queue) 스케줄링
우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다. 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 기본적인 형태가 같아 우선순위를 가진 여러 개의 큐를 사용한다. 다단계 큐 스케줄링은 각 단계의 큐에 라운드 로빈 방식을 사용하지만, 다단계 피드백 큐 스케줄링은 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. 하지만 마지막 우선순위로 가면 CPU를 빼앗기지 않고 끝까지 작업을 마치게 된다. 즉 마지막 큐는 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작한다.
다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 예이다.
TMI + 알면 좋은 것들
프로세스 우선순위
- 프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉘는데 커널 프로세스의 우선순위가 일반 프로세스보다 높다.
- 비디오 프로세서와 워드프로세서의 경우 비디오 프로세스가 우선순위가 더 높다.
- 일반 프로세스의 우선순위는 사용자가 조절할 수 있다.
- 대기상태에서 CPU를 할당받아 실행하는 작업을 CPU 버스트(CPU burst), 입출력 작업을 입출력 버스트(I/O burst)라고 부른다.
- 프로세스는 CPU 집중 프로세스(CPU bound process)와 입출력 집중 프로세스가 있습니다.
- CPU 집중 프로세스는 수학 연산과 같이 CPU를 많이 사용하는 프로세스를 말한다.
- 입출력 집중 프로세스는 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스를 말한다.
