스케줄링 알고리즘 #3: SRTN

• Shortest Remaining Time Next

  • 각 job의 남아있는 시간을 기준으로 스케줄링

  • ex1. 아래 작업은 A → A → B → C → D → E → B → B → B 순서로 진행.

    (2 + 9 + 1 + 2 + 3) / 5

    	작업 크기	들어오는 시간
    A	2	0
    B	4	0
    C	1	3
    D	1	3
    E	1	3

    ex2. A → A → B → B → C → D → E → B → B

    (2 + 9 + 2 + 3 + 4) / 5

    즉 ex1이 더 좋음

스케줄링 알고리즘 #4: Round Robin

• FIFO
• 모든 job에는 퀀텀이라고 불리는 타임 슬라이스가 주어짐
• 퀀텀만큼만 job이 실행됨

• ex1. 퀀텀이 1유닛일 때 A → B → A → B → C → D → E → B → B

  	작업 크기	들어오는 시간
  A	2	0
  B	4	0
  C	1	3
  D	1	3
  E	1	3

  ex2. 퀀텀이 2유닛일 때

  A → A → B → B → C → D → E → B → B

  ++ 작업 크기가 퀀텀보다 작으면 남은 CPU는 다음 작업이

• 장점) starvation 없음

• 문제점) 퀀텀을 얼마로 정해야 최적인가를 알기 어렵다

  • 너무 짧으면 컨텍스트 스위칭 많이 일어남
  • 너무 길면 짧은 job들이 한참 대기해야 할 수도 있음

스케줄링 알고리즘 #5: Priority Scheduling

• 우선순위 할당
  • Static: 시작할 때 우선순위 할당, 끝날 때까지 변하지 않음
  • Dynamic: 프로세스가 진행하면서 우선순위가 바뀜. I/O-bound와 같이 CPU를 짧게 쓰는 job들을 먼저 처리
  • ex. 퀀텀 100초일 때 A는 10초 사용, B는 50초 사용. A는 10/100 = 1/10 B는 50/100 = 1/2. 역수 취하면 A는 10, B는 2. 이걸로 우선순위 정함 (퀀텀을 더 효율적으로 이용하는 job에게 우선순위)
• 문제점) starvation
• 해결방법) age - 오래 기다릴수록 우선순위 높여줌

스케줄링 알고리즘 #6: Multiple Queues

• 각각의 큐마다 다른 알고리즘 적용 가능
• 큐 사이에서 프로세스가 이동 가능