workload : 일련의 프로세스들이 실행되는 상황이다.

개념을 위해 다소 비현실적인 가정이 들어간다.

  • 각 작업은 동일한 시간 동안 실행
  • 모든 작업은 같은 시간에 도착
  • 각 작업은 시작되면 완료될 때까지 실행
  • 모든 작업은 CPU 만 사용 (IO 는 없다고 가정)
  • 각 작업의 실행 시간은 알려져 있다고 가정

Scheduling Metrics

스케줄링? OS가 여러 작업(프로세스/스레드) 중, 어느 것을 언제 CPU에 할당할지 결정하는 과정

스케줄링 평가 기준

OS를 평가하는 기준이다.

  • Turn around time 반환시간 = 작업 완료 시간 - 작업 도착 시간

    이때 도착시간은 대기 큐에 프로세스가 도착한 시간을 뜻한다. 따라서 반환시간은 프로세스가 다른 프로세스가 끝나길 기다리는 시간까지 포함된다

    그럼 불공평한 거 아닌가? 생각이 들었는데, 프로세스 실행 순서에 따른 총 반환시간 평균을 계산하기 위한 과정이라고 생각하면 된다.

  • Fairness 공정성 : 모두에게 최소한의 기회를 보장하는 것, 어떤 프로세스도 무한히 기다리게 하지 않는 것

    이는 성능과 상충된다.

  • Response Time 프로세스가 도착한 후, 처음으로 CPU를 할당받을 때까지 걸린 시간

    프로세스가 많이 쌓여 있으면 응답 시간이 길어질 수 있다.

  • Deadline 작업이 반드시 끝나야 하는 절대적인 시각

    지켰는가/ 못 지켰는가가 평가지표다.

스케줄링 기법의 성능은 시스템 전체에 큰 영향을 미친다.

  • 스케줄링 기법이 다음 번에 실행할 프로세스, 대기할 프로세스를 정하는 방법론이다.
  • 스케줄링의 효율은 프로세스들의 대기 큐에서의 대기 시간 감소에 결정적이다.
    • 따라서 대기 큐의 구조를 최적화하는 것도 스케줄링 성능의 중요한 요소이다.

장기, 중기, 단기 스케줄링 Long term vs Medium term vs Short term

운영체제는

  1. 어떤 프로세스를 시스템에 들일지,
  2. 메모리에 둘지 말지,
  3. 지금 당장 CPU를 줄지를

서로 다른 스케줄러가 다른 시점에 결정한다.

  1. 장기 스케줄링 새로 생성된 프로세스를 시스템에 받아줄지, 아니면 대기시킬지 결정

    즉, 이 프로세스를 Ready Queue에 넣을지 말지

  2. 중기 스케줄링 메모리가 부족할 때 프로세스를 잠시 쫓아내거나, 다시 불러올지 결정한다.

  3. 단기 스케줄링 레디 큐에 있는 프로세스 중에서 지금 당장 cpu를 누구한테 줄지

    얘가 메인이다

Preemption(선점) vs Non-Preemption(비선점)

  • Preemption(선점형)
    → 실행 중인 프로세스를 강제로 중단시키고 다른 프로세스로 교체할 수 있음

  • Non-Preemption(비선점형)
    → 실행을 시작한 프로세스는 자발적으로 CPU를 놓을 때까지 계속 실행

다음은 프로세스들에게 cpu를 주는 방법론들이다. => 단기 스케줄링 기법들이다.

FIFO (First In First Out / First Come First Service, FCFS …) 선입 선출 - 철저히 먼저 도착한 프로세스 먼저 실행한다.

  • Non-Preemption(비선점형)

  • 구현이 쉽고, 간단하다

  • 단점 - Convoy effect cpu 사용 시간이 긴 프로세스 하나 때문에 모든 프로세스 지연 -> 평균 성능을 크게 악화시킨다.

SJF (Shortest Job First / Shortest Process Next, SPN …) 짧은 작업 우선

  • Non-Preemption(비선점형)

  • 짧은 작업의 불리한 점인 convoy effect 해결

STCF (Shortest Time-to-Completion First / Shortest Remaining Time) 최소 잔여 시간 우선

  • Preemption(선점형)

HRRN (Highest Response Raito Next) 대기 시간을 고려한 수식에 따름

프로세스를 고르는 순간, 대기 중인 프로세스들의 Response Ratio를 계산하여 가장 높은 프로세스에게 cpu를 할당함

  • Non-Preemption(비선점형)

RR (Round Robin / Time Slicing) 고정된 시간(Time Quantum) 만큼씩 CPU를 순환하며 나누어 줌

  • Preemption(선점형)

Time slicing = Scheduling Quantum

  • Time slicing: CPU를 잘라서 나누는 방식
  • Scheduling Quantum (Time Quantum): 한 프로세스가 최대로 사용할 수 있는 CPU 시간

I/O를 고려할 때

프로세스가 I/O를 요청하면, I/O 응답을 받기 전까지 해당 프로세스는 CPU 작업을 할 수 없음.

이때 I/O를 요청한 프로세스가 계속 CPU를 점유하고 있다면, 해당 프로세스는 실행할 수 없으므로 CPU는 유휴 상태가 된다. 놀게 된다.

따라서 I/O 요청이 있으면, I/O를 마칠 때까지 해당 프로세스는 Sleep(Block)되고 다른 프로세스에게 CPU를 할당시켜주고, I/O 요청이 끝나면 인터럽트를 통해 block 에서 ready 상태로 전환하면 낭비를 막을 수 있다.

그러면 ready queue에서 다음 스케줄링을 기다리게 될 것

2.6.23 버전 이후 리눅스(Linux CFS)는 레드 블랙 트리에 기반을 둔다. 모든 경로는 다르 모든 경로보다 두 배 이상 길어지지 않고, 트리의 삽입/삭제 작업 속도가 O(log n)으로 효율적임