4. CPU Scheduling
지난 번에 프로세스들의 상태를 변화시켜 큐간의 이동을 시켜주는 것이 프로세스 스케줄링이라고 했다.
CPU 스케줄링은 이 프로세스 스케줄링과는 구분된다.
프로세스 스케줄링 안에서도 발생 빈도에 따라 Long-term, Short-term, Medium-term 스케줄링으로 나뉘는데 그 중에 Short-term Scheduling이 CPU Scheduling에 해당한다.
Histogram of CPU-burst Times
I/O bound job은 카카오톡과 같은 메신저나, hwp 프로그램 같이 사용자가 입력을 해야만 일을 할 수 있는 프로그램들을 말한다. 그렇기에 I/O가 매우 빈번하게 발생한다. 키보드 입력이 들어오면 입력을 처리하고 또 다음 입력을 기다리는 동작이 계속 반복된다. 때문에 한 번 CPU를 잡았을 때, CPU를 잡고 있는 시간은 짧지만 CPU를 잡는 빈도가 매우 높다.
반면 CPU bound job은 I/O가 거의 발생하지 않는 계산 위주의 프로그램들을 말하며, I/O가 발생하지 않기 때문에 CPU를 잡는 횟수는 적지만 한 번 CPU를 잡았을 때 오랫동안 사용한다.
왜 이렇게 프로세스를 두 종류로 나눌까?
지금 내가 CPU를 줘야하는데, I/O bound job에 주는 것이 좋을지 CPU bound job에 주는 것이 좋을지를 결정해야 하기 때문.
사용자와의 interact 없이 계산만 하는 프로그램(CPU bound job)의 경우에는 조금 늦어져도 사용자의 불만이 적다. 만약 1시간에 걸쳐 소인수 분해를 해주는 프로그램이 있다고 했을 때, 그 프로그램이 CPU를 조금 늦게 잡아서 1시간 10초에 걸쳐 소인수 분해를 마쳤다고 하자. 그래도 사용자는 큰 불편함을 느끼지 못할 것이다.
그런데 카카오톡 같은 사용자와의 Interact가 잦은 프로그램의 경우 조금만 늦어져도 사용자가 불만을 드러낼 것이다. 입력창에 'ㄱ'을 입력했는데 바로 화면에 나타나지 않는다면 사용자는 답답함을 느낄 것이다.
그래서 사용자와의 Interact가 적은 프로그램은 CPU를 좀 나중에 줘도 사용자의 불만이 그렇게 높아지지 않더라는 것.
이 점이 CPU 스케줄링의 가장 기본적인 원칙이다.
=> 즉, I/O bound job에 CPU를 우선적으로 주는 것이 기본 원칙.
=> CPU 스케줄링을 하는 알고리즘들은 모두 이 원칙을 기반으로 하여 만들어졌다.
처음 만들어진 new 상태의 프로세스들은 Long-term scheduler에 의해 CPU Sheduling 대상으로 편입되어, Ready Queue에 들어가게 된다.
Ready 상태의 프로세스들은 CPU를 받기를 기다리다가 CPU를 받아서 Running 상태가 되면 프로그램이 실행된다.
Running 상태에서 벗어나는 경우는 3가지가 있다.
1. I/O가 발생해서 waiting 상태로 변경
2. I/O는 발생하지 않았지만 할당된 시간이 모두 끝나서 Timeout Interrupt를 받은 경우 다시 Ready 상태로 이동
3. 모든 Instruction을 수행해서 종료되어 terminated 상태로 가는 경우
레디 큐에서 CPU를 줄 대상을 선정하고, Running 상태의 프로세스들의 상태를 변화시키고 큐를 이동시키는 것이 Short-term Scheduler의 역할이다.
새로운 프로세스가 올라올 메모리 공간이 부족하면 현재 메모리에 올라와 있는 프로세스들 중에서 하나를 디스크로 내리고 새로운 프로세스를 메모리에 올려줘야 한다. 이렇게 Swap out, Swap in 시킬 프로세스를 결정하고 이동시키는 것이 Medium-term Scheduler의 역할이다.
Running 상태의 프로세스를 메모리에서 Swap out 시킬 수는 없으니 Ready 또는 Waiting 상태의 프로세스들 중에서 하나를 골라 swap out 시키는데, 가장 좋은 대상이 Suspend 상태의 프로세스라고 했다.
Suspend 상태의 프로세스는 어짜피 CPU를 받을 일이 없으니 잠시 디스크로 내려도 상관이 없다. 나중에 Suspend 상태가 해제되고 CPU를 받을 차례가 됐을 때 메모리에 다시 올라와 있기만 하면 된다.
Suspend 상태의 프로세스들을 모아두는 큐가 따로 있는데, Ready, Suspend Queue와 Blocked, Suspend Queue 이다.
Ready, Suspend Queue에는 Ready 상태이지만 사용자가 suspend를 시켜서 CPU를 받을 수 없는 프로세스들이 모여있는 큐다.
=> 사용자가 Suspend를 해제하면 Medium term Scheduler에 의해 Ready 큐로 돌아가게 된다.
Blocked, Suspend Queue에는 waiting 상태에서 사용자가 suspend를 시킨 프로세스들이다. 이 프로세스들은 Interrupt를 받는다고 해도 CPU를 주면 안 되는 프로세스들이기 때문에 따로 관리해야 한다.
Blocked, Suspend Queue의 프로세스들 중에서 I/O가 끝나 Interrupt를 받은 프로세스들은 Ready, Suspend Queue로 넘어가게 된다.
Medium-term scheduler가 메모리에서 밀어낼 프로세스를 선택하는 역할을 하므로 Suspend된 프로세스들이 모여있는 Suspend Queue 역시 Medium-term Scheduler가 관리하는 것이 적절하다.
CPU Scheduler
: Ready 상태에 있는 프로세스들 중에 하나를 골라서 CPU를 주는 역할을 하는 것이 CPU Scheduler이다.
CPU 스케줄링은 언제 발생할까?
1. Running 상태의 프로세스에 I/O가 발생해서 waiting 상태로 변경되었을 때.
이때는 Running 상태의 프로세스가 CPU를 놓게 되므로, CPU를 받을 대상을 선정해야 한다.
2. Timeout Interrupt를 받아 Running 상태의 프로세스가 Ready 상태로 변경되었을 때.
Timeout이 발생해서 Running 상태의 프로세스가 CPU를 놓으면, CPU를 받을 대상을 선정해야 한다.
3. I/O Interrupt 처리가 끝나서 Waiting에서 Ready 상태로 변경되었을 때.
엥? 이때는 왜 CPU가 놀게 될까?
Waiting 상태의 프로세스는 CPU를 잡고 있지도 않았는데 이때는 왜 CPU가 놀게되는 상황이 발생할까.
이것 역시 멀티 프로그래밍 환경에서만 발생하는 경우인데, I/O가 끝나고 Interrupt가 발생하게 되면 Interrupt 핸들러가 수행되어야 한다. 이 Interrupt 핸들러 역시 CPU가 있어야 수행이 되는데, waiting 상태의 프로세스가 ready 상태로 갔다는 것은 Interrupt handler가 끝이 났다는 것이므로 Interrupt를 처리하던 CPU는 놀게 되는 것이다.
원래는 Interrupt 핸들러를 처리하기 이전의 프로세스로 돌아가는 것이 보통이지만, 멀티 프로그래밍 환경에서는 원래의 프로세스로 돌아가야 한다는 강제 조항이 없다.
그래서 CPU 스케줄링을 통해 새로운 프로세스에게 CPU를 할당해 주어야 한다.
=> 현재 수행 중인 프로세스와 무관한 프로세스에서 I/O가 발생한 탓에 CPU를 뺏겨서 Ready 큐로 가야하는 불공평해 보이는 일이 발생.
4. Terminates
Running 상태의 프로세스가 모든 Instruction 수행을 마치고 종료되면 CPU가 놀게 되므로, CPU 스케줄링이 발생.
여기서 1, 4번의 상황은 비강제적으로 CPU 스케줄링이 발생하는 경우이다. (nonpreemptive)
반대로 2, 3번의 상황은 일을 하다가 강제적으로 CPU를 뺏겨 CPU 스케줄링이 발생하는 경우이다. (preemptive)
Dispatcher
CPU 스케줄링이 발생하면 어떤 일이 일어날까?
기본적으로 Dispatcher 모듈이 동작한다.
레디 큐에 있는 프로세스들 중에 어떤 놈에게 CPU를 줄지 결정이 되면 그 놈에게 CPU를 주기 위한 과정이 수행되는데, 이 과정을 수행하는 애가 Dispatcher다.
즉, 선택된 프로세스에게 CPU를 넘겨주는 일을 한다.
이 과정에서 Context Switch가 발생.
현재 수행 중인 프로세스의 상태를 PCB로 저장해두고, CPU를 줘야할 대상인 프로세스의 예전 PCB 정보를 CPU 레지스터에 로드해서 다시 시작할 수 있도록 만들어 줌.
=> 이 과정이 제일 오래 걸린다.
Context Switching이 끝나고 나면, Mode Switching이 발생한다.
Context Switch를 하는 코드는 커널코드이기 때문에 끝나면 다시 유저 모드로 돌아가야 하기 때문.
그런 다음 아까 수행하다가 중단된 위치로 돌아가서 해당 부분을 수행할 수 있도록 해준다.
이렇게 디스패처가 한 프로세스에서 다른 프로세스로 CPU를 넘겨주기 위해 필요한 오버헤드를 Dispatch latency라고 한다.
그 중에서 대부분은 context switch overhead이다.
멀티 프로그래밍을 위해서는 불가피하게 감내해야 할 오버헤드이다.
CPU 스케줄링 알고리즘을 평가하는 성능 지표
Scheduling Algorithms
: 스케줄링을 하는 알고리즘
여기서 스케줄링은 CPU 스케줄링 뿐 아니라 컴퓨터 전체에서 일어나는 스케줄링에 해당한다.
1. FCFS(First Come First Served) Scheduling
들어오는 순서대로 처리하는 가장 기본적인 방법이다.
별로 효율적이지 않은 알고리즘처럼 보이지만 스케줄링 할 때 중요한 후보 중 하나로 고려되는 알고리즘이다.
FCFS 알고리즘이 가지는 강점인 Fairness( 공평성 ) 때문이다.
공평성이라는 큰 장점이 있지만, 단점이 너무 많다.
만약 P2, P3, P1 순으로 작업이 들어왔다면, Average waiting time이 3이 된다.
공평성을 얻지만, 순서에 따라 나쁜 Waiting time이 발생할 수도 있다는 단점이 있다.
이것을 우리는 Convoy effect( 호위병 효과) 라고 한다.
낼쌘 호위병이 느린 왕 때문에 같이 천천히 가게 된다는 효과이다.
앞 순서에 Burst time이 큰 프로세스가 있으면 뒤에 있는 프로세스들의 waiting time이 늘어나게 된다는 것이다.
그러면 여기서 우리는 작업의 수행 순서를 바꾸면 waiting time을 최적화 할 수 있겠다는 생각을 해야 한다.
2. SJF ( Shortest-Job-First ) Scheduling
CPU 사용 시간이 가장 짧은 프로세스부터 수행한다는 알고리즘이다.
각 프로세스들이 CPU를 얼마나 사용할지를 예측해서 가장 짧게 사용할 것 같은 프로세스를 먼저 수행한다.
여기서 정책에 따라 2가지의 방향으로 나뉘게 된다.
SJF 알고리즘을 사용해서 가장 짧게 CPU를 사용할 것 같은 프로세스에게 CPU를 줬는데, 그때 새로운 프로세스가 들어왔다. 그런데 그 프로세스의 수행 시간이 더 짧다면, CPU를 뺏어서 새로운 프로세스에 줘야할지 아니면 이미 CPU를 줬으니까 그냥 수행하고 끝난 다음에 줄지에 따라 Nonpreemptive와 Preemptive 방식으로 나뉜다.
여기서 Preemptive 방식은 CPU를 뺏어서 새로 들어온 프로세스에게 CPU를 넘겨준다는 정책인데
이 방식을 SRTF( Shortest-Remaining-Time-First ) Scheduling이라고 부른다.
SRTF 스케줄링은 SJF 알고리즘의 Preemptive한 방식이지만 그냥 별도의 알고리즘으로 생각하는 것이 좋다.
SJF 알고리즘은 average waiting time을 가장 작게 만들 수 있는 optimal한 알고리즘이다.
Nonpreemptive한 SJF의 예시를 보자.
SRTF( Preemptive한 SJF )의 예시를 보자.
SRTF를 사용했을 때는 Average waiting time이 3으로 Nonpreemptive한 SJF 스케줄링을 했을 때 보다도 작은 것을 알 수 있다.
=> SRTF 알고리즘이 waiting time 면에서 가장 optimal한 알고리즘인 것을 알 수 있다.
Determining Length of Next CPU Burst
그런데 SJF 계열의 알고리즘을 사용하기 위해서는 다음 번에 프로세스가 CPU를 잡았을 때
얼마나 오랫동안 CPU를 사용할지를 알아야 하는데, 어떻게 알 수 있을까?
=> 신이 아닌 이상 정확히는 알 수 없음.
그러면 SJF 계열의 알고리즘은 사용하지 못하는 것인가?
=> 알 수 없으면 예측이라도 해야지
미래를 예측하는 가장 좋은 데이터는 과거의 데이터이다.
과거에 한 프로세스가 CPU를 잡은 횟수가 여러 번일 것이다.
I/O가 발생해서 놓았다가 다시 잡고, Timeout이 발생해서 놓았다가 다시 잡고,, 이런 과정이 계속 반복되었을 것.
n번째로 CPU를 잡았을 때 실제로 사용했던 시간을 tn이라고 한다.
τn+1은 n+1번째로 CPU를 잡는다면 이 정도를 사용하지 않을까 하는 예측값
그리고 정의된 식을 통해 Burst time을 예측한다.
여기서 알파값이 0이면 이전의 실제값은 무시하게 되고, 매번 같은 값을 예측하게 된다.
=> 과거 데이터 전체의 평균을 보겠다는 뜻이다.
만약 알파값이 1이면 다음 예측값은 직전의 실제값이 된다.
=> 즉, 직전 값을 100% 신뢰하겠다는 뜻이 된다.
여기서 우리는 알파 값이 과거의 실제값에 대한 의존도를 결정한다는 것을 알 수 있다.
직전 예측값인 τn이 왜 다음 예측값인 τn+1을 예측하는 데에 사용될까??
위의 식을 쭉 풀어 써보면
이렇게 되는데, (1 - α)가 0과 1사이의 값이기 때문에 제곱할 수록 값이 작아진다.
따라서 과거의 데이터일수록 의존성이 떨어지게 된다.
=> 타우값 자체가 과거의 실제값을 자기의 인수로 포함하고 있고, 쭉 풀어쓰면 과거로 갈수록 가중치가 작아지는 식이 만들어지기 때문에 타우n을 타우n+1을 예측하는 것에 사용됨.
=> 직전 데이터에 대한 의존성이 가장 높고, 과거 데이터일수록 의존성이 점점 작아지는 우리가 원하는 방식의 예측을 할 수 있게 된다.
알파 값이 작아질 수록 과거의 데이터를 공평하게 반영
알파 값이 커질 수록 최근 데이터를 더 많이 반영(더 중요하게 생각)
=> Exponential Averaging을 사용하면 유연하게 타우 n+1 값을 예측할 수 있게 된다.
위의 그래프를 보면 알파값이 클수록 실제 값과 비슷한 예측을 하는 것을 보인다.
그러면 알파값을 무조건 1로 두면 제일 좋은 것 아닌가?
위의 예시는 알파 값이 클수록 좋은 경우이기 때문에 그런 것이고 그렇지 않은 경우도 있다.
CPU burst time이 자주 변하는 경우에는 과거의 데이터가 크게 의미가 없기 때문에 직전의 실제값이 제일 중요하다.
따라서 알파값이 클수록 좋긴 하지만,
CPU burst time이 너무 급격하게 자주 변하는 경우에는 직전 값에 대한 의존도를 높이는 것이 오히려 안 좋게 된다.
Priority Scheduling
우선순위 스케줄링 정책
=> 독자적인 알고리즘이라기 보다는 알고리즘을 만드는 틀로 사용한다.
각 프로세스마다 우선 순위를 부여하고, 우선순위가 높은 프로세스에게 CPU를 먼저 주겠다는 정책.
많은 운영체제에서는 각 프로세스마다 별도의 우선순위를 부여한다.
실시간성이 높은 프로세스에는 높은 우선순위를 주고, 일반적인 프로세스에는 낮은 우선순위를 주는 방식을 사용.
독자적으로 우선순위만 가지고 CPU 스케줄링을 하는 것 보다는 다른 방식과 혼합하여 우선순위까지 고려한 CPU 스케줄링 정책 이런 식으로 사용하는 경우가 많다.
우선순위를 정하는 방법이 다양하기 때문에 단순히 Priority Scheduling을 사용한다는 말로는 어떻게 우선순위를 정하는지 알 수가 없기 때문이다.
예를 들어 다음 번에 CPU를 잡았을 때 burst time이 가장 작은 프로세스에게 높은 우선순위를 주겠다 라고 하면 사실 SFJ scheduing이 되는 것임
Priority Scheduling 정책의 문제점과 해결 방안
문제점: Starvation
priority scheduling 방식의 가장 큰 문제점은, 우선 순위를 어떻게 정하느냐도 문제가 되지만
Priority가 낮은 프로세스들은 자기보다 우선 순위가 높은 프로세스가 계속 들어오기 때문에 계속해서 수행되지 못 한다는 문제가 있다.(Ready queue에 있는 프로세스 중에 우선 순위가 낮은 애들은 계속 뒤로 밀리게 됨)
해결책: Aging
시간이 지남에 따라 우선순위를 조금씩 높여줌으로써 Starvation 현상을 완화시킨다.
3. Round Robin(RR) Scheduling
돌아가면서 사용한다는 뜻으로 FCFS 방식을 기본 철학으로 하지만 각각의 프로세스가 CPU를 잡았을 때 CPU를 사용할 수 있는 시간의 범위(한계)를 지정
이러한 시간 제한을 time quantum이라고 한다.
time quantum을 초과하면 I/O가 발생하지 않더라도 CPU를 넘겨줘야 한다.
RR 방식의 장점은 time quantum을 q라 하고, Ready 큐 안의 프로세스 수를 n이라고 하면
waiting time이 최대 (n-1)q 시간이라는 것이 보장된다.
자신을 제외한 모든 프로세스가 q시간을 꽉 채워 사용하면 (n-1)q 시간이 걸림.
즉, 모든 프로세스가 못해도 (n-1)q 시간 안에는 CPU를 잡을 수 있다는 뜻이다.
레디 큐에 있는 프로세스들의 대기 시간의 Upper bound를 제공한다는 것은 엄청난 장점이다.
=> Waiting tme의 upper bound를 제공
Upper bound를 알 수 있다는 것은 뭐가 좋을까?
Upper bound가 존재하기 때문에 그에 맞춰서 일을 할 수 있게 된다. (n-1)q 시간 안에는 반드시 CPU를 잡을 수 있으니까 거기에 맞춰서 계획적으로 일을 할 수 있게 된다.
Round Robin은 멀티 프로그램을 위해 만들어진 알고리즘이다.
FCFS나 SJF를 사용하게 되면 I/O가 발생하거나 프로그램이 끝나기 전까지 CPU를 한 번 잡으면 계속 사용하게 된다. CPU bound job의 경우엔 걔가 끝날 때까진 다른 프로세스들은 진도를 전혀 나가지 못하게 되는 문제가 있다.
=> 멀티 프로그래밍의 효과가 없어짐.
Round Robin 방식을 사용하면 모든 프로그램이 조금씩 진도를 나갈 수 있다.
=> 그래서 요즘 멀티 프로그램을 지원하는 OS라면 Round Robin 방식을 사용하지 않을 수가 없다.
=> Round Robin을 기반으로 해서 우선 순위를 추가하거나 다른 방식을 결합시킨 CPU scheduling 알고리즘을 사용하고 있다.
Time Quantum이 20인 RR 스케줄링 예시
Multilevel Queue
앞에서 interactive한 Job에게는 CPU를 빨리 주는 것이 CPU 스케줄링의 원칙이라고 했다.
즉, I/O bound job에게 CPU를 빨리 줘야 한다고 했는데.
우리가 지금까지 본 알고리즘들은 그 원칙을 잘 반영하고 있을까?
FCFS는 전혀 반영하지 않음.
SJF, SRTF의 경우 burst time이 작은 I/O bound job에게 CPU를 먼저 주니까 원칙을 잘 반영하게 됨.
RR의 경우 burst time에 관계 없이 돌아가면서 CPU를 사용하기 때문에 그 원칙을 반영하고 있다고 할 수 없다.
=> RR의 경우 멀티 프로그래밍을 위해 반드시 필요하지만 이러한 이유로 그것 만으로 사용하기에는 부족하다. => RR 역시 FCFS를 기반으로 만들어졌기 때문에 어쩔 수 없음RR의 경우에서 I/O bound job의 우선 순위를 높여주기 위해서 나온 것이 Multilevel Queue이다.
멀티레벨 큐는 레디 큐를 여러 종류로 나눈 것이다. 예시에서는 foreground와 background 2개로 나눴지만 2개 이상으로 나눌 수도 있다.
그리고 foreground에는 I/O bound job을 넣고, background에는 CPU bound job을 넣겠다고 정한다.
그리고 각각의 큐는 Round Robin과 FCFS 방식을 사용한다.
foreground 큐에는 I/O bound job만 모여있기 때문에 Round Robin 방식을 사용해도 I/O bound job에게 먼저 CPU를 준다는 원칙을 지킬 수 있게 된다.
Fixed priority shceduling
foreground 큐에 있는 모든 작업을 수행한 다음에 background큐에 있는 작업을 수행.background 큐의 job들은 foreground 큐에 job이 하나라도 있으면 CPU를 잡지 못하게 되는 문제가 있다. (Starvation)
Time slice
foreground queue에게 대부분의 시간을 주되 background queue에도 CPU 시간의 일부를 주자. foreground queue에 전체 시간의 80%, background queue에 전체 시간의 20% 이런 식으로
=> background의 CPU bound job들도 조금씩은 진도를 나갈 수 있다.
그런데 Multilevel Queue 알고리즘을 사용했을 때 OS는 각각의 프로세스가 I/O bound job인지, CPU bound job인지 구분할 방법이 없다.
그래서 Multilevel Feedback Queue라는 것이 나왔다.
Multilevel Feedback Queue
multilevel feedback queue 알고리즘에서는 프로세스가 큐 간에 이동이 가능하다.
multilevel feedback queue 알고리즘을 사용하기 위해서는 위의 5가지 정책에 대해서 정의가 되어야 한다.
큐의 수를 정해야 하고,
각 큐에 적용되는 CPU 스케줄링 알고리즘을 정해야 하고,
상위큐 또는 하위큐로 이동하게 되는 조건을 정의해야 한다.
그리고 마지막으로 최초로 프로세스가 만들어지면 처음에 어느 큐에 넣을 것인지도 정의해야 한다.
처음에는 일단 아무 큐에 넣은 다음에 CPU를 사용하는 행태에 따라 어떤 Job인지 구분하게 되면 큐를 옮길 수있게 하는 방법이다.
Multilevel Queue 스케줄링의 예시
그렇게 복잡하지 않은 이 정도의 Multilevel Feedback Queue 알고리즘만 사용해도
I/O bound job에게 많은 기회를 주도록 할 수 있다.
Real-Time Scheduling
운영체제 수업에서는 실시간 스케줄링에 대해서는 다루지 않을 것이라고 하셨다.
하지만 간략하게 적어보자면
실시간 스케줄링에는 프로세스마다 종료되어야 할 deadline이 존재한다.
그 Deadline에 대한 유연성을 기준으로 2가지 방식으로 나뉜다.
Hard real-time systems
deadline안에 프로세스가 반드시 수행될 수 있도록 CPU Scheduling을 한다.
=> 엄청난 계산을 통해 스케줄링
미사일 발사와 같은 정교한 작업에 사용한다.
Soft real-time computing
deadline을 반드시 보장할 필요가 없지만 웬만하면 보장
*모든 내용은 한양대학교 강수용 교수님의 강의 내용을 참고하여 작성되었습니다.