5장 CPU scheduling

 

reference: kocw의 반효경 교수님 강의와 권진욱 교수님 강의(대학 정규 수업)
수업을 듣고나서 강의 교재를 타이핑하고 필기한 부분을 추가적으로 정리하였습니다.
웹뷰에서 toc를 제공합니다.
github의 md 파일로 보는 게 편하시다면, 여기로 이동해주시면 됩니다.

---

1. CPU scheduling이 필요한 이유

CPU-burst Time의 분포

여러 종류의 job (=process)가 섞여 있기 때문에 CPU scheduling이 필요하다.

interactive job에게 적절한 response 제공해야 하고 cpu와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용해야 한다.

Q. 빨간색 부분과 같이 cpu를 짧게 프로그램과 파란색 부분과 같이 cpu를 길게 쓰는 프로그램 중 CPU를 누구한테 먼저 주어야 할까요? (= cpu scheduling)

A. 이질적인 작업이 섞여있을 때, I/O bound job에 먼저 주는 것이 좋음. 이유는 오래 걸리는 작업을 먼저 요청하는 게 좋고 I/O 작업은 보통 사용자와 interaction하는 작업이기 때문이다.

2. 프로세스의 특성 분류

• I/O-bound process
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
  • many short CPU bursts
  •  

    

    즉, 중간중간 I/O가 많이 끼어들어서 CPU bursts가 잘려 짧아짐. 대신 수는 많아짐
  • CPU burst: cpu를 한 번에 얼마나 길게 쓰느냐
  • 주로 사람과 interaction하는 게 많음.
• CPU-bound process
  • 계산 위주의 job
  • few, very long CPU bursts

3. CPU Scheduler & Dispatcher

CPU Scheduler 와 Dispatcher 모두 운영체제의 특성 코드의 일부이다. 하드웨어나 단독의 응용 프로그램을 말하는 것이 아니다.

• Cpu Scheduler
  • ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다. 결정한다.
• Dispatcher
  • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
  • 이 과정을 context switch(문맥 교환)이라고 한다.
• CPU scheduling이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
  1. Running ㅡ> Blocked
  2. Running ㅡ> Ready
  3. Blocked ㅡ> Ready
  4. Terminate

1, 4 에서 스케줄링은 nonpreemptive (- 걍제로 빼앗지 않고 자진 반납)

이외의 모든 스케줄링은 preemptive (- 강제로 cpu를 빼앗김)

4. Scheduling Criteria

= Performance Index ( = Performance Measure, 성능 척도) 스케줄링 알고리즘 중 무엇이 좋은가 판단할 수 있는 척도, 방법

• CPU utilization (이용률)
  • keep the CPU as busy as possible
  • 비유: 주방장이 놀지 않고 일한 시간의 비율
  • 높을수록 좋음
• Throughput (처리량)
  • the number of processes that complete their execution per time unit
  • 비유: 주방장이 손님 몇 명을 받았냐
  • 높을수록 좋음
• Turnaround time (소요 시간, 반환 시간)
  • amount of time to execute a particular process
  • 비유: 중국집 들어와서 다 먹고 나간 시간
  • 짧을수록 좋음
• Waiting time (대기 시간)
  • amount of time a process has been waiting in the ready queue
  • cpu 쓰러 와서 기다린 시간의 합
  • 비유: 단무지 기다리는 시간, 이후에 짜장면 기다린 시간, 이후에 탕수육 기다린 시간의 합
  • 짧을수록 좋음
• Response time (응답 시간)
  • amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
  • 프로세스가 cpu를 쓰러 들어와서 처음 cpu를 쓰기까지 걸린 시간. 프로세스가 처음 시작해서 처음으로 cpu를 얻은 시간이 아님
  • 비유: 단무지 기다리는 시간
  • 짧을수록 좋음

5. Scheduling Algorithms

5-1. FCFS (First-Come First-Service)

예를 들면, 화장실에서, 은행에서 온 순서대로 처리되고 앞 사람을 내쫓을 수 없다.

CPU 입장에서 보면 빼앗을 수 없다는 뜻이다. (nonpreemptive)

 

예시를 봐보자.

프로세스의 도착 순서를 Burst Time이 짧은 순서로 바꿨더니 waiting time(대기 시간)이 현저히 줄어들었다.

*Burst Time: CPU 사용 시간

Convey effect(호위 효과): short process behind long process 전쟁 시 좋은 효과로, 예를 들면 잘 싸우는 사람이 앞에서 오래 버텨주면 뒤 사람들은 오래 사는 것으로 비유할 수 있다. 하지만 CPU 관점에서는 대기 시간이 길어지므로 부정적인 효과이다.

5-2. SJF (Shortest-Job-First)

각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용한다.

CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄한다.

두 종류로 나뉜다.

• Nonpreemptive

  

  그런데 이 방법에 치명적인 문제점이 있다. 영원히 내 차례가 오지 않을 수 있다는 것이다.
• 나는 화장실을 10분 쓸거라서 짧게 쓰는 사람에게 양보한다고 했을 때, 5분 1분을 사용하려는 사람들이 계속 온다면 난 평생 화장실을 사용할 수 없을 것이다. 이것을 Starvation이라고 한다.
• *Arrival Time: Ready Queue에 도착하는 시점.
• 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않는다. 쉽게 말해, 다 수행될 때까지 기다려준다는 뜻이다.
• Preemptive
• 현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗긴다. 이 방법을 SRTF라고 부른다. 이에 대한 예시는 아래에서 따로 다룬다.

SJF is optimal

왜? 주어진 프로세스들에 대해 minimum average waiting time을 보장하기 때문이다. 대기 시간을 더 짧게 스케줄링할 수는 없다.

5-3. SRTF (Shortest-Remaining-Time-First)

여기서 문제점은 CPU를 기다리는 큐에 들어오는 시점에 CPU burst time을 미리 알 수 없다는 점이다. 프로그램은 복잡하고 상황에 따라 다르기 때문에 과거를 보고 예측한다.

Q. 그러다면 다음번 CPU burst time을 어떻게 예측할 수 있을까?

A. (운영체제에서 딱 한 번 나오는 수식)

점화식을 풀면,

α와 1-α 가 둘 다 1 이하이므로 후속 term은 선행 term보다 적은 가중치의 값을 가지는 것을 볼 수 있다. 즉 최근(직전)의 값을 더 많이 반영하고 있다.

5-4. Priority Scheduling

• highest priority 를 가진 프로세스에게 CPU를 할당한다.
• 가장 작은 정수가 가장 높은 우선순위이다.
• preempitive와 nonpreemptive로 나눌 수 있다.
• SJF는 일종의 priority scheduling이다. predicted next cpu burst time을 우선 순위로 갖는다.
• 그런데 심각한 문제는, Starvation - low priority processes may never execute 해결방법은 Aging - as time progresses increase the priority of the process

5-5. RR (Round Robin)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다. (일반적으로 10~100 ms)
• 할당 시간이 지나면 프로세스는 선점(preempted-cpu를 빼앗김)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. 따라서 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음을 보장한다.
• q (할당 시간)이 길어지면 그냥 FIFO가 되고, 반대로 짧아지면 빈번한 문맥 교환으로 오버헤드가 커진다.
•  

  

• 일반적으로 SJF보다 average turnaround time(총 소요 시간)은 길지만 response time(첫 응답 시간)는 더 짧다.

heterogeneous할 때, 즉 long job과 short job이 섞여있을 때 RR이 진가를 발휘한다.

homogeneous, 즉 동일한 job만 있을 때는 큰 효과가 없다. 예를 들어 은행에서 10분 정도 볼 일을 봐야하는 사람들이 왔는데 1분이 할당 시간이라고 하면 결국 나중에 모든 사람이 같이 집에 가게되는 비효율적인 상황이 벌어질 수 있다. 응답 속도는 빠르긴 한데 총 소요 시간은 길다.

5-6. Multilevel Queue

CPU는 1개인데 줄(큐)을 여러 줄로 서는 방법이다.

• ready queue를 여러 개로 분할
  • foreground (interactive)
  • background (batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
  • foreground - RR. interactive하니까 응답 시간이 빠른 게 좋음.
  • background - FCFS. long job이 많아서 context switch 없이 쭉 실행하는 게 좋음.
• 큐에 대한 스케줄링이 필요하다.
  • 첫번째 방법은, Fixed priority scheduling
    • serve all from foreground then from background fore 후에 back을 서비스하도록 고정
    • Possibility of starvation
  • 두번째 방법은, Time slice
    • 각 큐에 cpu time을 적절한 비율로 할당
    • 예를 들어, 현재 cpu time에 foreground에는 80%를 할당하고 background에는 20% 할당한다.
•  

  

  신분의 변화가 없다. 한 번 정해진 신분(큐)로 평생을 살게 된다.

5-7. Multilevel Feedback Queue

• 위(multilevel queue)와는 다르게 프로세스가 다른 큐로 이동이 가능하다.
• aging을 이와 같은 방식으로 구현할 수 있다.
• Multilevel-feedback-queue scheduler를 정의하는 파라미터들은 아래와 같다.
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • Process를 상위 큐로 보내는 기준 (승격)
  • Process를 하위 큐로 내쫓는 기준 (강등)
  • 프로세스가 cpu 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
• Multilevel Feedback Queue를 구현한 한 예시아래로 갈수록 우선순위가 낮아진다.동일하게 16ms을 더 썼는데 남으면 아래로 넘어가고 8+16ms에 끝내지 못한 경우 그 아래의 큐로 쫓겨나서 FCFS 으로 처리된다.
• 먼저 누구든 new job은 맨 윗 줄(queue)에 서는데 cpu 할당 시간이 8ms이다. 8ms 동안에 다 쓰고 나가면 그냥 오른쪽으로 나가게 되는 것이고 8ms 을 쓰고 남은 경우, 아래의 큐로 내려간다.
•  

  

5-8. 이 외의 스케줄링

위에서 살펴본 스케줄링 알고리즘은 한정된 자원(1개의 cpu)에서 여러 프로세스를 어떻게 스케줄링 할지에 관한 내용이었다. 아래는 이와는 좀 다른 내용이므로 이렇게 헤더를 잡아보았다.

Multiple-Processor Scheduling

CPU가 여러 개인 경우를 뜻한다. 이 경우, 스케줄링은 더욱 복잡해진다. 화장실에 칸이 1개가 아닌 여러 개, 은행에 창구가 1개가 아닌 여러 개인 것으로 확장되었다고 생각하면 된다. 이렇게 cpu가 여러 개인 경우는 예외적인 상황이다. 일반적인 컴퓨터에는 cpu가 1개 들어가니까.

• Homogeneous processor인 경우
  • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • 반드시 특성 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해진다.
  • 예를 들면, 미용실에서 미용사 여러 명인데 자리가 비었다고 바로 가지 않고 원하는 디자이너께 받기까지 기다릴 수 있다.
• Long sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
  • 화장실에서 각 칸 별로 줄을 설 것인지 한 줄 서기를 할 것인지 로 비유할 수 있다.
• Symmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케줄링을 결정한다.
  • 모든 프로세서가 대등한 관계에 있는 방법이다.
• Asymmetirc multiprocessing
  • 위와는 다르게 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따르는 방법이다.
  • 한 마디로, cpu 중에서도 대장 cpu가 있고 그의 명령을 따르는 방식이다.

5-9. Real-Time Scheduling

real time 이란 dead line이 있어서 주어진 시간 내에 처리가 되어야 하는 것을 말한다.

• Hard real-time systems
  • hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 하는 것
  • 그래서 오프라인이다. 즉 프로세스 도착 시간을 미리 알고 스케줄링 한다.
• Soft real-time computing
  • soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 한다.
  • 예시로 동영상 스트리밍을 생각해보면, 초당 24 frame을 반드시 decoding해서 내보내줘야한다. 데드라인을 지키지 못하면 동영상이 끊긴다. 하지만 일반적인 컴퓨터는 real-time 스케줄링을 쓰지 않는데 (비싸고 어려움), 동영상 처리를 우선순위를 높게 두어 처리한다.

5-10.Thread Scheduling

• Local Scheduling
  • User level thread의 경우, OS가 스레드의 존재를 모르기에, 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정한다. 즉 프로세스 내부에서 어느 thread에 cpu를 줄지 결정한다.
• Global Scheduling
  • Kernal level thread의 경우, OS가 스레드의 존재를 알기에, 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다. 즉 OS가 직접 결정한다.

6. Algorithm Evaluation

Q. 어떤 CPU 스케줄링 알고리즘이 좋은건지 어떻게 측정할까?

A. 아래 3개의 방법이 있어.

• Queueing models
  • 확률 분포로 주어지는 arrival rae와 service rate 등을 통해 각종 performance index 값을 계산하는 방식이다. 1960년 대에 쓰던 이론적 방법이다.
• Implementation(구현) & Measurement(성능 측정)
  • 실제 시스템에 알고리즘을 구현! 하여 실제 작업에 대해서 성능을 측정하여 비교하는 방법이다. 너무 어려운 방법이다.
• Simulation(모의 실험)
  • 알고리즘을 모의 프로그램으로 작성 후 trace (input이 되는 작업들)를 입력으로 하여 결과를 비교해본다. 그러므로 trace가 신빙성이 있어야 한다.