[OS] CPU 스케줄링

스케줄링???

• 스케줄링? ready큐에 있는 프로세스들중 어떤 프로세스를 선택할지(효율적으로)를 결정하는것
• Preemptive(선점형) : 프로세스가 cpu를 선점할 수 있음(cpu를 선점하고있는 프로세스를 쫓아낼 수 있음)
• Non-preemptive(비선점형) : 프로세스가 cpu를 점유하면 그 프로세스가 종료되거나 자발적으로(I/O작업으로 인한 wait) 점유를 포기할때까지 계속 cpu를 점유함
• dispatcher : 문맥교환, user mode로 스위칭, 사용자 프로그램을 적당한 위치로 resume해주는 모듈
• dispatcher latency(디스패치 지연시간) : 문맥교환에 걸리는 시간 P0 -> p1로 갈때 PCB0의 내용을 저장하고 PCB1의 내용을 로드하는 시간, 가급적이면 짧아야됨
  • 참고 : 리눅스에 vmstat로 문맥교환이 얼마나 자주일어나는지 볼 수 있음 (1초씩 3번 확인)
    

스케줄링의 목표

• CPU utilization 최대화 : cpu를 가능한한 busy하게 사용하는것(cpu노는 시간 최대한 줄이기)
• Throughput 최대화 : 어떤 단위 시간내에 완료되는 프로세스의 갯수를 늘리는것
• Turnaround time 최소화 : 프로세스의 반환시간을 최소화하는것 (프로세스 종료시간 - 프로세스가 들어온시간)
• Waiting time 최소화 : 각 프로세스가 ready큐에서 대기하는 시간의 합을 최소화시키는것
• Response time 최소화 : 프로세스의 응답시간을 최소화하는거 (프로세스가 ready큐에 들어오고 처음 cpu를 점유하는 시간)

스케줄링의 알고리즘

• FCFS(FIFO) : 먼저 ready상태가된 프로세스를 먼저 실행시키는것
• SJF(최단 작업 우선) : 가장 짧은 실행시간을 가진 프로세스를 먼저 실행시키는것
• STCF(PSJF)(최단 잔여시간 우선) : 가장 적은 잔여 실행 시간을 가진 작업을 실행시키는것
• RR(라운드 로빈) : 일정시간(타이머 인터럽트 주기의 배수)동안 실행한 후 ready큐에 다음 작업을 전환하는것
• MLFQ(멀티레벨피드백 큐) : 여러개의 큐로 구성하여 각각 다른 우선순위에따라 프로세스를 각 큐에 배정하는것

FCFS(FIFO)

가장 단순한 알고리즘으로 먼저 CPU를 요청한 프로세스부터 작업을 비선점형 방식으로 진행함

• P1 -> p2 -> p3 순으로 실행이됨 (거의 동시에 들어왔지만 간발의 차이로 p1~p3순으로 들어왔고, 각프로세스는 IO작업이 없다 가정)

• 대기 시간 : P1 = 0, p2 = 24, p3 = 27 평균 대기 시간 51/3 = 17초

• 반환 시간 : p1 = 24, p2 = 27, p3 = 30 평균 반환 시간 81/3 = 27초

• 장점

  • 가장 단순하고 구현이 쉬움
  • 준비 큐에 있는 모든 프로세스가 결국 실행되므로 기아 상태(starvation)이 되는 프로세스가 없음
  • 프로세서가 지속적으로 유용한 프로세스를 수행하여 처리율이 높다

• 단점

  • 비선점 방식이므로 대화식 프로세스(I/O작업을 자주하는 프로세스)에는 부적합
  • 위의 예시처럼 장기 실행 프로세스가 있으면 뒤에 있는 모든 프로세스를 대기시켜 평균 대기 시간이 길어지며 최악의 대기시간이 될 수 있음
  • convoy effect(호송 효과) : 짧은 실행 시간을 가지는 프로세스가 긴 실행 시간을 가지는 프로세스의 종료를 기다리는 현상이 발생함

SJF(최단 작업 우선)

현재 ready상태인 프로세스들 중 실행 시간이 짧은 프로세스를 먼저 실행시키는 알고리즘
모든 작업이 동시에 들어온다 가정하면 SJF가 Optimal(최적)의 알고리즘이 됨

• P1~p4가 동시에 들어왔음(이 역시 IO작업이 없는 비대화형 프로세스)

• 대기 시간 : p1 = 3, p2 = 16, p3 = 9, p4 = 0 평균 대기 시간 28/4 = 7초

• 반환 시간 : p1 = 9, p2 = 24, p3 = 16, p1 = 3 평균 반환 시간 52/4 = 13초

• 장점

  • 모든 작업이 동시에 들어올때 최적의 알고리즘

• 단점

  • 이역시 비선점형이라서 대화식 프로세스에는 부적합함..
  • 사실 프로세스의 실행시간을 cpu가 알 방법이 없어서 사실상 불가능,,
  • 수행시간이 긴 작업은 짧은 작업에 밀려 기아상태가 될 수 있음(계속 짧은 실행시간을 가진 프로세스가 들어오면)
  • 짧은 작업이 먼저 실행되므로 공정하지 못한 정책

STCF(최소 잔여시간 우선)

SJF에 선점 기능을 추가한 알고리즘(프로세스가 cpu를 점유하고있는 프로세스를 내쫓고 cpu를 선점할 수 있는 기능)

• 대기 시간: (10 − 1) + (1 − 1) + (17 − 2) + (5 − 3) = 26 평균 대기시간 26/4 = 6.5

• 반환 시간 : (17 - 0) + (5 - 1) + (26 - 2) + (10 -3) = 52 평균 반환시간 52/4 = 16

• 장점 : 프로세스들이 각기 다른시간에 들어왔을때, 최적의 스케줄링이됨 (반환시간 기준)

• 단점 : SJF나 STCF나 반환시간 기준 최적이되나 응답시간기준이면 좋은 스케줄링이라고는 보기 힘듦.

RR(Round-Robin)

평가 기준이 반환 시간이면 SJF나 STCF가 좋은 스케줄링 기법이지만,
응답 시간 = 첫실행시간 - 도착시간 기준에서는 좋은 스케줄링 기법이아님.
현대 os는 batching system이 아닌 Interactive System이기 때문에 응답시간도 반환시간만큼 중요한 평가항목이됨

• 라운드 로빈
  • 일정 시간(타임 슬라이스, 스케줄링 퀀텀) 동안 실행한 후 ready큐의 다음 작업으로 전환함
  • 일정 시간은 타이머 인터럽트 주기의 배수여야함 (타이머가 10ms마다 인터럽트를 발생시키면 타임 슬라이스는 20,30ms 등이 돼야함)
  • 타임 슬라이스의 길이는 짧을 수록 응답 시간이 좋아지지만, 너무 짧게 지정하면 문맥 교환의 오버헤드때문에 전체 성능에 영향을 끼치게됨

• SJF 일때. 응답시간이 좋지 않음
  • A는 0초에 도착해서 0초에 시작했기 때문에 Response Time은 0초
  • B는 0초에 도착해서 5초에 시작했기 때문에 Response Time은 5초
  • C는 0초에 도착해서 10초에 시작했기 때문에 Response Time은 10초
  • 평균 Response Time은 5초

• RR 응답시간이 좋음
  • 평균 응답 시간이 (0 + 1 + 2) / 3 = 1초

• 장점
  • 응답시간에서 최적의 알고리즘이 됨
  • 공정한 정책임
• 단점
  • 반환시간은 완료 시간을 고려하기 때문에 반환 시간기준 거의 최악..
  • 문맥 교환의 오버헤드와 응답 시간이 반비례적이라 적절한 타임슬라이스를 찾기가 힘듦

멀티 레벨 피드백 큐(multi-level-feedback-Q)

반환 시간을 최적화하면(STCF) 응답시간이 안좋아지고, 응답시간을 최적화하면(RR) 반환시간이 안좋아지는 두 마리 토끼를 모두 못잡는 상황임
또 각 프로세스들의 작업시간을 알고있다는 전제, 그리고 각 프로세스들은 대화형 프로세스(IO작업 X)라는 전제를 포함한 스케줄링 기법이였음
실제 CPU는 각 프로세스들이 얼만큼 CPU를 점유해야 종료되는지도 모르고, I/O작업까지도함 이걸 해결하는게 멀티 레벨 피드백 큐로 현재 스케줄러는 대부분 이걸 씀

• MLFQ : 여러 개의 큐로 구성되며, 각 큐는 다른 우선순위를 가지고 있어서 각 프로세스들은 우선순위에 따라 배정됨 즉 높은 우선순위를 가진 프로세스는 높은 우선순위 큐에 존재함
• 규칙 1 : 우선순위A > 우선순위B 이면 A가 실행됨(B는 x)
• 규칙 2 : A == B 이면, A B는 RR 방식으로 실행됨
• 규칙 3 : 프로세스가 새로 도착하면, 가장 높은 우선순위큐에 배정됨
• 규칙 4 : 작업이 지정된 단계에서 배정받은 시간을 소진하면(CPU를 포기한 횟수와 상관없이) 작업의 우선순위는 감소함(한 단계 낮은 큐로 이동)
  • CPU를 포기한 횟수와 상관없다는 부분은 프로세스가 타임 퀀텀직전에 의도적으로 의미없는 I/O작업을 하면서 CPU를 부적절하게 독점하는것을 방지함
• 규칙 5 : 일정주기 S가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킴(Boost)
  • Boost작업이 없게되면 규칙 4로 인해 맨 아래 큐로 떨어진 프로세스가 기아 상태가 될 수 있음(새로운 프로세스가 지속적으로 들어오게될 경우)

왼쪽은 규칙 5가 적용 안될 경우, 오른쪽은 규칙 5를 적용해 priority boost가 행해진 경우임 왼쪽에 경우 A프로세스는 100초 이후 기아 상태에 빠지지면 오른쪽의 경우 일정 주기마다 실행이됨
이때 일정 주기 S는 부두 상수(값을 정확히 결정하려면 흑마술이라도 필요 할 정도로 정하기 힘들다는뜻) 너무 크면 긴 실행 시간을 가진 프로세스는 기아 상태가 될 수 있고,
너무 작으면 대화형 작업이 적절한 양의 CPU점유를 가질 수 없게됨

성능 측정

• Queueing model : 확률 분포로 주어지는 arrival rate, service rate 등을 통해 각종 성능값을 계산, os 경우는 arrival rate는 응답시간이고, service rate는 반환시간에 해당함
• 구현과 측정 : 실제 시스템에 알고리즘을 직접 구현하여 실제 워크로드에 대해서 성능을 측정 비교
• 시뮬레이션 : 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 해서 결과를 비교함(테스트랑 비슷함)

Reference
주니온 교수님 유튜브 채널
반효경 교수님 KOCW 운영체제
운영체제 아주 쉬운 세 가지 이야기(OSTEP 번역서)