CPU 스케줄링

http://www.kocw.net/home/search/kemView.do?kemId=1046323 의 강의를 정리한 글입니다.

CPU burst와 I/O burst

• 프로세스는 CPU burst와 I/O burst가 왔다갔다 번갈아가면서 프로그램을 실행한다.
  • CPU burst : CPU 명령을 실행하는 것
  • I/O burst : I/O를 요청하고 기다리는 것
• 프로그램의 종류에 따라서 CPU burst와 I/O burst의 빈도나 길이가 다를 수 있다.
• CPU burst time의 분포 그래프
• I/O bound job : CPU burst가 짧고 빈도수가 많은 즉, I/O burst가 많이 끼어드는 작업을 말한다.(burst duration 0-8의 치솟는 구간)
• CPU bound job : I/O burst의 방해없이 CPU만 진득하게 사용하는 작업을 말한다.(burst duration 16부터의 평온한 구간)

➡️ I/O bound job은 보통 사용자에게 요청과 응답을 주고 받거나 하는 작업들인데 CPU bound job이 CPU를 계속 잡고 사용하게 되면 사용자는 CPU bound job이 끝날 때까지 기다려야 하는 상황이 생긴다. 공평하게 나눠 쓰는 것도 좋지만 우리는 기다리는 것을 싫어하기 때문에 CPU 스케줄링을 통해서 I/O bound job에게 우선권을 준다.

• CPU 스케줄링 : 컴퓨터의 자원을 '효율적'으로 관리하기 위해서 프로세스들 사이에 CPU 할당을 위한 우선순위를 관리하는 일을 뜻한다.
  • CPU를 사용하려고 줄 서있는 대기줄(Ready Queue)에 있는 프로세스들이 CPU 스케줄링의 대상들이다.
• 아래와 같이 프로세스의 상태 변화가 있는 경우 CPU 스케줄링이 필요하다.
  • Running -> Blocked(예: I/O를 요청하는 시스템 콜)
  • Running -> Ready(예: 할당된 CPU사용시간 만료 - timer interrupt)
  • Blocked -> Ready(예 : I/O가 완료된 후 interrupt)
  • Terminate
  • 위의 4개를 제외한 나머지 스케줄링은 CPU를 강제로 빼앗는다(preemptive = 선점), 위의 4개는 자진 반납하는 경우(nonpreemptive = 비선점)
• CPU 스케줄러 : ready상태의 프로세스 중에서 이번에는 어떤 프로세스에게 CPU를 줄 지를 정한다.
• Dispatcher : CPU 스케줄러에게 간택된 프로세스에게 CPU의 제어권을 넘겨준다. 이를 context switch(문맥 교환)이라고 한다.
• Dispatch latency : 한 프로세스를 멈추고 다른 프로세스를 실행하는 데까지 걸리는 시간을 말한다.

Scheduling Criteria(스케줄링 성능척도)

• 시스템 입장에서의 성능척도 : CPU 하나 가지고 최대한 일을 많이 시키는 게 최고
  • 이용률(CPU Utilization) : 전체 시간 중 CPU가 일한 시간의 비율(CPU는 제일 비싸고 효율 좋은 자원이니까 쉬지 말고 일 시켜!)
  • 처리량(Throughput) : 주어진 시간 동안 얼마나 많은 일을 처리했는가(단위 시간 당 처리양)
• 프로그램(프로세스) 입장에서의 성능척도 : 내가 CPU를 빨리 얻어서 빨리 일을 끝내는 게 최고
  • 소요시간(Turnaround time) : CPU를 쓰려고 들어온 시간부터 다 쓰고 나간 시간 ➡️ CPU를 사용하려고 Ready Queue에 기다린 시간부터 작업 완료 시간
  • 대기시간(Waiting time) : CPU를 사용하려고 Ready Queue에 기다린 시간
  • 응답시간(Response time) : Ready Queue에 들어와서 처음으로 CPU를 얻기까지 걸린 시간

CPU 스케줄링 알고리즘

1) FCFS(First-Come First-Serve) : 선입선출

• FCFS는 어떤 프로세스가 먼저 오냐에 따라 기다리는 시간에 엄청난 영향을 끼친다.

• Convoy Effect : CPU를 오래 점유하는 프로세스가 먼저 도착해서 짧은 프로세스들이 지나치게 오래 기다려야 하는 현상(좋지않은 현상임)

  프로세스	시간
  P1	24
  P2	3
  P3	3

◆ CPU를 오래 쓰는 프로세스(P1)이 먼저 도착해서 CPU를 선점하면 비교적 CPU를 짧게 쓰는 P2, P3(예: I/O)는 P1이 끝날 때까지 기다려야 한다.

• Waiting time : P1 = 0, P2 = 24, P3 = 27

• Average waiting time :(0 + 24 + 27) / 3 = 17

  ◆ CPU를 짧게 쓰는 P2나 P3가 먼저 도착 후 P1이 도착한다면

• Waiting time : P1 = 6, P2 = 0, P3 = 3
• Average waiting time :(6 + 0 + 3) / 3 = 3

2) SJF(Shortest-Job-First) : CPU 사용시간이 짧은 놈 먼저

• 각 프로세스의 다음번 CPU burst time 을 가지고 스케줄링에 활용하는데 CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄한다.

• Nonpreemptive : 온 프로세스 중에 CPU burst time이 가장 짧은 애에게 CPU를 먼저 주고 난 후, 더 짧은 애가 도착해도 CPU를 빼앗지 않는다.

• Preemptive : 가장 짧은 애에게 줬더라도 더 짧은 애가 오면 CPU를 빼앗아 더 짧은 애에게 CPU를 넘겨준다.(SRTF : Shortest-Remaining-Time-First)

• 주어진 프로세스에 대해 minimum average waiting time을 보장한다.(SJF is optimal -> preemtive)

  ◆ Nonpreemtive의 경우

  프로세스	도착시간	실행시간(burst time)
  P1	0.0	7
  P2	2.0	4
  P3	4.0	1
  P4	5.0	4

• CPU를 다 쓰고 나가는 시점에 스케줄링을 할 지 안할 지 결정

• Average waiting time = (0 + 6 + 3 + 7) /4 = 4

  ◆Preemtive의 경우

  프로세스	도착시간	실행시간(burst time)
  P1	0.0	7
  P2	2.0	4
  P3	4.0	1
  P4	5.0	4

• 새로운 프로세스가 도착하면 언제든지 스케줄링이 이루어짐

• Average waiting time = (9 + 1 + 0 + 2) / 4 = 3

  ◆SJF의 문제점

  • 기아현상(Starvation) : SJF은 CPU 사용시간이 짧은 애들을 먼저 보내는데 그렇게 되면 CPU 사용시간이 긴 애들은 죽을 때까지 CPU를 얻지 못할 수도 있다.
  • CPU 사용시간을 미리 알 수 없다. 그럼 어떻게 다음번 CPU burst time을 알 수 있을까?
    • 정확하진 않지만 과거의 CPU burst time을 통해서 추정한다.
    • exponential averaging

3) Priority(우선순위) : 우선순위가 제일 높은 프로세스에게 CPU를 준다.

• Nonpreemptive : 우선순위가 더 높은 애가 왔을 때 CPU를 빼앗지 않는다.
• Preemptive : 우선순위가 더 높은 애가 오면 CPU를 빼앗아서 더 높은 애에게 준다.
• 정수값으로 우선순위를 표현하는 숫자가 주어진다.(높을수록 숫자가 작음)
• SJF스케줄링도 Priority스케줄링의 일종이다.
• SJF와 같이 Starvation문제가 발생하는데 이를 해결하기 위해서 Aging이라는 기법을 사용한다.
  • Aging : 아무리 우선순위가 낮아도 오래 기다리면 우선순위를 조금씩 높여주자.

4) Round Robin

• 각 프로세스는 동일한 크기의 할당시간(time quantum, 보통 10-100 milliseconds)을 가진다.
• CPU를 점유하고 있다가 할당된 시간이 끝나면 프로세스는 preempted되고 ready queue의 마지막에 가서 다시 줄을 선다.
• n개의 프로세스가 ready queue에 있고 할당시간이 q time unit인 경우, 각 프로세스는 최대 q time unit단위로 CPU 시간의 1/n을 얻는다.
  즉, 어떠한 프로세스도 (n-1)q time unit 이상은 기다리지 않는다.
• 가장 큰 장점 : 응답시간이 빨라진다.
• CPU를 길게 쓰는 프로세스는 기다리는 시간도 길어지고 짧게 쓰는 프로세스는 기다리는 시간도 짧아진다. 즉, 대기시간은 CPU를 사용하는 시간과 비례한다.
• 하지만 time quantum을 너무 길게 주면 FCFS와 같은 스케줄링 알고리즘이 되고, 그렇다고 너무 짧게 주면 context switch가 너무 빈번하게 발생하기 때문에 시스템 성능이 나빠진다.
• 일반적으로 SJF보다 average turnaround time이 길지만 reponse time은 더 짧다.

5) MultiLevel Queue

• Ready Queue를 여러개로 분할하고 각 큐들은 각자 독립적인 알고리즘을 가진다.

  • foreground : interactive job을 큐에 담고 Round Robin을 사용한다

  • background : batch를 큐에 담고 FCFS를 사용한다.

  • Fixed Priority Scheduling

  1. 자신이 해당하는 Ready Queue에 가서 줄 서서 차례를 기다린다.
  2. 큐의 우선순위에 따라서 CPU의 우선권을 가진다.
  3. 이 때 후순위의 큐는 Starvation문제가 발생할 수도 있다.
     따라서 큐에 대한 스케줄링이 필요하다
     ➡️ Time slice : 각 큐마다 CPU Time을 적절한 비율로 할당하여 이 문제를 해결한다.

6) MultiLevel Feedback Queue

• 다른 큐로 프로세스의 이동이 가능하다.

• aging이 이와 같은 방식이다.

• MultiLevel Feedback Queue를 정의하는 파라미터들

  • Queue의 수
  • 각 큐들의 독립적인 스케줄링 알고리즘
  • process들을 상위/하위 큐로 보내는 기준
  • 프로세스가 CPU서비스를 받으려고 할 때 들어갈 큐를 결정하는 기준

• 보통 처음 들어오는 프로세스는 우선 순위가 가장 높은 큐(A)에 넣는다. 이 때, 큐는 Round Robin을 사용하고 time quantum을 아주 짧게 설정함.

• 하위 큐로 갈수록 time quantum을 점점 길게 주고 마지막 큐는 Round Robin이 아닌 FCFS를 사용한다.

A큐에서 시간을 다 쓰면 B큐로 강등된 후 자신의 차례를 기다렸다가 CPU를 얻어서 작업을 하고 또 시간이 다되면 다음 하위 큐로 강등 .. 작업 .. 을 반복하다가 마지막 큐에서는 기다린 후 CPU를 얻어 쭉 작업을 진행한다.

B큐는 A큐가 비어야 우선권을 가지고 작업을 할 수 있다.

CPU 사용시간이 긴 프로세스는 점점 밑으로 쫓겨나고 CPU 사용시간이 짧은 프로세스는 빠르게 CPU를 사용하고 빠져나간다.
➡️ CPU 사용시간의 예측이 필요없고 CPU 사용시간이 짧은 프로세스가 우선순위를 많이 가지는 스케줄링 방식이다.

특이한 케이스의 CPU 스케줄링

1. Multiple Processor Scheduling(CPU가 여러개 있는 시스템)

1) Homogeneous Processor인 경우

• 큐에 한 줄로 세워서 작

  2) Load Sharing인 경우

  3) Symmetric Multiprocessing(SMP)

  4) Asymmetric Multiprocessing

2. Real Time Scheduling(시간에 대한 제약조건이 있는 경우)

1) Hard Real Time Systems

2) Soft Real Time Computing

3. Thread Scheduling(쓰레드가 여러개 있는 경우)

1) Local Scheduling

2) Global Scheduling