[CS] 운영체제 - CPU 스케줄링

CPU Scheduler: Ready 상태의 프로세스 중에서 CPU를 줄 프로세스를 고른다.
Dispatcher: CPU의 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘긴다. 이 과정을 context switch라고 한다. (실제로 CPU를 주는 과정이다.)
CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.

1. Running에서 Blocked로 갈 때 (ex) I/O 요청하는 시스템 콜이 일어날 때)
2. Running에서 Ready로 갈 때 (ex) 할당 시간 만료로 timer interrupt가 발생할 때)
3. Blocked에서 Ready로 갈 때 (ex) 1번 완료후 인터럽트)
4. terminate될 때

• nonpreemptive: 비 선점형, 강제로 빼앗지 않고 자진해서 CPU를 반납하는걸 말한다.
• preemptive: 선점형, 강제로 CPU를 회수하는걸 말한다.

 

성능 척도

시스템 입장에서의 성능 척도

• CPU utilization(이용료): 전체 시간중에서 CPU가 놀지 않고 일한 비율이다. CPU는 비싼 자원이기 때문에 최대한 일을 시켜야 한다.
• Throughput(처리량): 주어진 시간 동안에 몇개의 작업을 처리했는지를 나타낸다.

프로그램 입장에서의 성능 척도

• Turnaround time(소요시간, 반환시간): CPU를 쓰기 위해 들어온 시간부터 CPU를 다 사용하고 난 후 빠져나간 시간을 말한다.
• Waiting time (대기 시간): Ready queue에서 CPU를 쓰기위해 기다린 시간만을 말한다.
• Response time (응답 시간): Ready queue에서 처음으로 CPU를 얻기까지 걸린 시간을 말한다.

 

스케줄링 알고리즘

CPU가 하나있는 경우의 알고리즘은 다음과 같다.

1. FCFS(First-Come First-Served)
   • 먼저 온 순서대로 먼저 처리하는 알고리즘이다.
   • 비 선점형이다.
   • 효율적이지는 않다.
   • 앞에 오래 걸리는 프로세스가 있을 수록 waiting time이 늘어난다.
2. SJF(Shortest-Job-First)
   • CPU를 사용하는 시간이 가장 짧은 프로세스부터 제일 먼저 스케줄링하는 알고리즘이다.
   • waiting time의 평균이 짧아진다.
   • 2가지 방식이 존재한다.
   • 비 선점형인 경우에 일단 CPU를 사용중이면 CPU 사용시간이 더 짧은 프로세스가 도착하더라도 기존에 쓰던 프로세스가 CPU를 사용한다.
   • 선점형인 경우에는 CPU를 줬다고 하더라도 CPU 사용시간이 더 짧은 프로세스가 존재하면 더 짧은 프로세스에 CPU를 준다. 이러한 방법을 Shortest-Remaining-Time-First (SRTF) 라고 부른다.
   • 문제점
     • CPU 사용시간이 긴 프로세스는 영원히 작업을 못 할수도 있다. ex) 10초가 걸리는 프로세스가 있는데 앞에 1초짜리 프로세스가 계속 들어오는 경우
     • CPU 사용시간을 미리 알 수 없다. -> 실제 시스템에서는 사용할 수 없진 않고 과거에 CPU를 얼마나 사용했는지를 예측해서 사용한다.(exponential averaging)
3. 우선순위 스케줄링(Priority Scheduling)
   • 우선순위가 제일 높은 순서대로 CPU를 할당한다. SJF는 일종의 우선순위 스케줄이다.
   • 문제점
     • CPU 우선순위가 낮은 프로세스는 영원히 작업을 못 할수도 있다. ex) 우선순위가 낮은 프로세스 앞에 우선순위가 높은 프로세스가 계속 들어올 때
     • aging이라는 기법을 도입해서 해결할 수 있다. aging은 우선순위가 낮은 프로세스라도 오래 기다렸다면 우선순위를 높여주는 방법이다.
4. Round Robin (RR)
   • 각 프로세스는 동일한 크기의 할당 시간을 가진다.
   • 선점형이다.
   • 할당 시간이 끝나면 timer interrupt에 의해 CPU할당을 뺏기고 Ready queue 맨 뒤로 보낸다.
   • 응답 시간이 빨라진다.
   • 할당시간을 크게 잡으면 FCFS랑 같은 알고리즘이 되고, 할당시간을 많이 작게 자르면 context switch때문에 오버헤드가 커진다.
5. Multilevel Queue
   • Ready Queue를 여러개로 분할한다.
   • foreground: foreground에는 interactive한 작업을 넣어준다.
   • background: 사람과의 작업이 없는 프로세스는 background에 들어간다.
   • 각 큐는 독립적인 스케줄링 알고리즘을 가진다. foreground는 RR 알고리즘을 사용하고 background는 FCFS를 사용한다.
   • 큐에 대한 스케줄링도 필요하다. (fixed priority 스케줄링, time slice: 각 큐에 CPU time을 적절한 비율로 할당한다.)
   • 프로세스의 우선순위대로 줄을 세워두고 우선순위가 높은것부터 순차적으로 실행한다.
             
6. Multilevel feedback queue
   • 프로세스가 다른 큐로 이동할 수 있다.
   • aging을 이와 같은 방식으로 구현할 수 있다.
   • 아래와 같은 파라미터들로 정의된다.
     • Queue의 수
     • 각 큐의 스케줄링 알고리즘
     • Process를 상위 큐로 보내는 기준
     • Process를 하위 큐로 내쫓는 기준
     • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

CPU가 여러개 있는 경우의 알고리즘은 다음과 같다.

1. Multiple-Processor 스케줄링
   
   • CPU가 여러 개인 경우 스케줄링은 더 복잡해진다. 
   • Homogeneous processor인 경우
     
     • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
     • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해진다.
   • Load sharing
     
     • 일부 프로세서에 일이 몰리지 않도록 부하를 적절히 공유하는 매커니즘이 필요하다.
     • 별개의 큐를 두는 방법과 공동 큐를 사용하는 방법이 있다.
   • Symmetric Multiprocessing (SMP): 각 프로세서가 알아서 스케줄링을 결정한다.
   • Asymmetric multiprocessing: 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다.
2. Real-Time 스케줄링
   
   • Hard real-time systems: 정해진 시간 안에 반드시 끝내도록 스케줄링해야한다. 데드라인을 반드시 지킨다.
   • Soft real-time computing: Soft real-time task는 일반 프로세스에 비해 높은 우선순위를 갖게 한다. 데드라인을 반드시 지키지는 못한다.
3. Thread Scheduling
   
   • Local Scheduling
     
     • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정한다.
     • 사용자 프로세스가 직접 어떤 thread에 CPU를 줄지 결정한다.
   • Global Scheduling
     
     • Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다.
     • OS가 알고리즘에 의거해서 어떤 thread에 CPU를 줄지 결정한다.

Algorithm evaluation

Queueing models: 확률 분포로 주어지는 arrival rate와 service rate를 통해서 각종 performance index 값을 계산한다.
implementation & measurement(구현과 성능 측정): 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정하고 비교한다.
Simulation(모의 실험): 알고리즘을 모의 프로그램으로 작성후 trace(Inupt data)를 입력해서 결과를 비교한다.