[운영체제] 4. CPU Scheduling (2)

키워드

scheduling algorithms, 성능 척도, fcfs, sjf, priority scheduling, round robin, multilevel queue, multilevel feedback queue

 

Scheduling Algorithms

성능 척도

(Scheduling Criteria = Performance Index = Performance Measure)

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

• CPU utilization(이용률)
  • 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율
  • 최대한 일 시키기
• Throughput(처리량)
  
  • 주어진 시간 동안 몇 개의 작업을 완료했나

프로세스 입장에서의 성능 척도

• Turnaround time(소요 시간, 반환 시간)
  • 프로세스가 CPU를 쓰러 들어와서 다 쓰고 I/O 하러  나갈 때 까지의 걸린 시간
  • 프로세스가 시작해서 종료되기까지의 시간이 아님
• Waiting time(대기 시간)
  • ready queue에 들어와서 순서를 기다린 시간
• Response time(응답 시간)
  • ready queue에 들어와서 최초로 CPU를 얻기까지 걸린 시간
  • time-sharing 환경을 위해 필요

성능 척도를 중국집에 비유하면

중국집 주인 입장

• CPU utilization(이용률)
  • 오픈 시간 중 주방장이 놀지 않고 일한 시간 비율
• Throughput(처리량)
  • (중국집에 비유하면) 단위 시간 당 몇명이나 밥을 먹여 내보냈나

손님 입장

• Turnaround time(소요 시간)
  • 중국집에 밥 먹으러 들어와서 주문을 하고 밥이 나오면 다 먹고 나갈 때 까지의 걸린 시간
  • 코스 요리 같은 경우를 생각하면 각 메뉴마다 기다린 시간 + 먹는 시간들까지 다 합쳐야되는걸 생각
• Waiting time(대기 시간)
  • 손님이 기다린 시간
• Response time(응답 시간)
  • 첫 번째 음식이 나올 때 까지의 기다린 시간

 

FCFS

(=First-Come First-Served)

• 먼저 온 고객을 먼저 서비스 해주는 스케줄링 방법
• 말 그대로 먼저 온 순서대로 처리
• 비선점형 스케줄링
• CPU를 짧게 쓰는 프로그램들이 오더라도 기다려야해서 효율적이진 않음
• 앞에 오는 프로세스에 따라 average waiting time(평균 대기 시간)이 달라짐
• 긴 프로세스가 먼저 도착해서 짧은 프로세스가 지나치게 오래 기다리는 현상을
  Convoy effect라고 한다.

 

SJF

(=Shortest-Job-First)

• 짧게 쓰는 프로세스에게 먼저 CPU를 쓰게 해줌
• minimum average waiting time을 보장
• Nonpreemptive
  
  • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음
  • 제일 짧게 쓰는 프로세스라 CPU를 줬는데 더 짧은 프로세스가 들어와 중간에 뺏기않게끔
    CPU 사용권을 보장해주는 방식
• Preemptive
  • 현재 수행중인 프로세스의 남은 burst time보다
    더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏어감
  • 이 방법을 SRTF(=Shortest-Remaining-Time-First)라고도 부른다.
  • minimum average waiting time을 보장하는 방법은 preemptive에 해당

 

문제점

Starvation 문제(기아 상태)

• SJF는 극단적으로 CPU 사용이 짧은 프로세스를 선호하기 때문에
  CPU 사용이 긴 프로세스는 영원히 서비스를 못 받을 가능성 존재

CPU 사용 시간을 미리 알 수 없는 문제

• 하지만 과거에 얼마나 썼는가를 통해 추정(estimate)은 가능 (대개 프로그램들이 비슷한 패턴을 나타내기 때문)
  -> exponential averaging

 

Priority Scheduling

(=우선순위 스케줄링)

• 우선순위가 제일 높은 프로세스에게 CPU를 주는 개념
• 이것도 Preemptive, Nonpreemptive 두가지 버전 존재
  • SJF와 마찬가지로 우선순위가 높은 프로세스 사용중 더 높은 우선순위 프로세스가 오는 경우
    CPU를 빼앗는다면 Preemptive, 사용을 보장해준다면 Nonpreemptive
• 우선순위를 나타내는 숫자(정수값)가 주어짐
  (smallest integer = highest priority)
• SJF는 일종의 priority scheduling
  (priority = predicted next CPU burst time. 즉, CPU 사용 시간이 적은 프로세스가 우선순위가 높아짐)
• 동일하게 Starvation(기아 현상) 문제 존재
  -> Aging(노화): 오래 기다리는만큼 우선순위를 높이는 방법을 통해 해결을 꾀함

 

Round Robin(RR)

• 현대적인 컴퓨터에서 사용하는 CPU scheduling은 Round Robin에 기반하고 있다.
• CPU를 줄 때 할당 시간을 세팅해서 넘겨주는게 RR에 기반한 방법 (preemptive=선점)
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
  (일반적으로 10 ~ 100 ms)
• 할당 시간이 지나면 프로세스는 선점(preemptive)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• 응답 시간이 빨라진다는 장점이 존재
  줬다 뺏었다의 반복이기 때문에 어떤 프로세스든지 CPU를 사용할 기회가 있음
• n 개의 프로세스가 있고 할당 시간이 q인 경우
  적어도 n * q의 시간만 기다리면 CPU를 사용할 기회가 주어짐
  -> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다. (나 자신은 빼기 때문에 -1)
• CPU를 길게 쓰는 프로세스는 대기 시간도 길어지고 
  CPU를 짧게 쓰는 프로세스는 대기 시간도 짧아짐
  즉, 대기 시간이 본인의 CPU를 사용하는 시간과 비례
• Performance
  
  • 할당 시간을 지나치게 길게 잡는다면 -> FCFS
  • 할당 시간을 지나치게 작게 잡는다면 -> 무수히 많은 context switch가 발생하여 오버헤드가 커짐
    RR의 철학적인 측면에선 이상적이지만 오버헤드로 인해 시스템 전체 성능이 나빠짐
  • 이상적인 할당 시간을 주는게 중요
• RR의 장점은 turnaround time보다 response time이 빨라진다는 것

 

문제점

사용 시간이 동일한 프로세스 여러 개에 대해서는 사용이 끝날 때 모두 동시에 완료되는 상황이 있는데

이 경우 오히려 SJF가 더 나은 방법이 될 수 있다.
하지만 일반적인 경우에선 짧은 프로세스와 긴 프로세스가 섞여 있기 때문에 RR이 더 효과적

 

Multilevel Queue

위로 갈수록 높은 우선순위

• 태생에 따라 우선순위가 나뉨
• Ready queue를 여러 개로 분할(줄을 여러 줄로 세워 관리)
  • foreground (interactive)
  • background (batch - no human interaction)
• 각 줄 마다의 스케줄링 방식이 필요(각 큐는 독립적인 스케줄링 알고리즘을 가짐)
  • forground -> RR
  • background -> FCFS
• 어느 줄에 CPU를 줄지(큐에 대한 스케줄링이 필요)
  • Fixed priority scheduling
    -> starvation 발생
  • Time slice
    -> 각 큐에 CPU time을 적절한 비율로 할당
    -> ex) 80% to foreground in RR, 20% to background in FCFS

고려사항

• 프로세스를 어느 줄에 넣을 것인지
• 높은 우선순위의 줄이 비어있지 않으면 해당 줄에만 우선권을 줄건지?
  -> 우선순위가 낮은 줄은 starvation 문제 발생
• 신분을 영원히 극복하지 못하는 문제 발생

 

Multilevel Feedback Queue

• Multilevel Queue처럼 여러 줄로 관리하지만
  프로세스가 경우에 따라 줄(다른 큐) 간에 이동이 가능한 스케줄링 방법
• 보통은 처음 들어오는 큐는 우선순위가 가장 높은 큐에 집어넣음
  우선순위가 높은 큐는 RR에서 time quantum을 짧게 설정
• 밑에 큐로 갈수록 RR의 할당 시간을 점점 길게
• 제일 아래는 FCFS
• 맨 위의 할당 시간이 끝나면 아래 큐로 강등(아래 큐가 끝나면 더 아래로 ... 반복)
• burst가 짧은 프로세스는 도착하자마자 CPU를 얻어서 바로 빠져나가겠지만
  burst가 긴 프로세스는 맨 위의 큐에서 처리가 다 안끝나면 점점 아래 큐로 이동해서 할당 시간을 더 받지만
  보통은 큐 간의 우선순위에서 위의 큐가 비었을 때만 밑의 큐를 처리하는 방식을 사용
• CPU 사용 시간이 짧은 프로세스에게 우선순위를 많이 주는 방식
• RR 만으로도 부족하기 때문에 Multilevel Feedback Queue를 사용
• CPU 사용 시간에 대한 예측이 필요 없음
  처음에 들어올 땐 누구든지 할당 시간을 짧게 주기 때문에
  사용 시간이 짧은 프로세스가 우대를 받음

 

고려사항

• 큐를 몇 개 둘건지?
• 각 큐에서 어떤 스케줄링을 사용할건지?
• 우선순위가 높은 큐에서 낮은 큐로 떨어지는 기준?
• 우선순위가 낮은 큐에서 높은 큐로 승격되는 기준?
• 처음 프로세스가 들어갈 때 어느 큐로 들어가는지?