Jump to:
Navigation

12. Process Scheduling

in Study / Computer Science / Operating System on Blog

Process Scheduling Types

  • Long Term Scheduling (job scheduler)

    New 상태의 Process 중 어떤 Process를 Ready Queue로 보낼 것인가

  • Mid Term Scheduling (swapper)

    어떤 Process를 Swap 할 것인가

    공간이 없으면 Swap Out(Memory에서 Disk의 Swap 영역으로 이동) 해서 공간 확보 할 수 있도록 함

    공간이 많으면 Swap In(Disk의 Swap 영역에서 Memory로 이동)

    (Suspend Queue에서 Ready Queue 이동 판단)

  • Short term Scheduling

    CPU 스케쥴러 ( Processor에 올릴 것인가 판단, 어떤 Process를 실행 시킬 것인가 )

    • IO Scheduling

      Pending된 IO 요청들을 관리

Schedule 함수 종류

  • Selection function

    Ready Process에 있는 것 중 어떤 것이 다음 번에 실행될 지 결정

    • 기준

      • w : 시스템에 상주해 있던 시간
      • e : 실행을 위해 쓴 시간
      • s : 예상되는 처리 시간

    • Decesion mode

      Selection 함수가 실행되는 시간적 순간을 지정

      • 종류
        • Non Preemptive

          종료되거나 블럭될 때까지 내버려둠

        • Preemptive

          블럭된 Process의 Interrupt가 생기거나, 시간이 다 되는 등의 이슈가 생기면 Process Switch 발생

  • FIFO (FCFS)

    가장 오래 기다린 것 먼저 실행

    First-Come-First-Served

    • Selection Function

      MAX[W] : 가장 오래 System에 상주해 있는 Process

    • Decesion Mode

      Non-Preemption

    • 장점

      • 간단한 Schedule 정책

    • 단점

      • 오래된 프로세스 위주
      • Convoy Effect 발생

    • Convoy Effect

      별로 안 걸리는 새 작업이 있지만 CPU 사용 시간이 긴 무거운 긴 작업을 처리하느라 응답이 느려짐

  • Shortest-Process-Next (SPN)

    예상 처리 시간이 가장 짧은 Process 먼저 선택

    • Selection Function

      MIN[S] : 최소로 예상되는 처리 시간의 Process

    • Decision Mode

      Non-Preemption

    • 장점

      • Turn Around Time 개선

    • 단점

      • 오래 걸리는 Process는 계속해서 선택받지 못할 수 있음 (Starvation)
      • 구현하기 어려움 (예상 처리 시간 계산 등)

    • Turn Around Time

      프로세스가 완료된 시각 - 프로세스가 도착한 시간

  • Round-Robin

    Time Slicing

    Running 중이던 Process가 Ready Queue로 들어가게 됐을 때, FCFS를 기반으로 동작

    Quantum Time을 기반으로 Process 별 Time Slice를 할당해서, 주기적으로 Process Switch가 일어나 Convoy Effect를 해결해보고자 함

    • Selection Function

      Constant

    • Decision Mode

      Preemption

    • 주의점

      Quantum Time을 어떻게 설정하는지가 중요함

      너무 길게 설정하면 FIFO랑 다를 것이 없고

      너무 짧게 설정하면 SPN과 유사하며, Context Switch가 많아져 Overhead가 많이 생김

  • Shortest-Remaning-Time (SRT)

    SPN과 유사, Decision Mode가 Preemption

    예상되는 처리 시간에서 현재까지 실행된 시간을 뺀 나머지 시간이 최소인 프로세스

    => 금방 종료될 것이라 기대되는 프로세스

    • Selection Function

      MIN[S-E]

    • Decision Mode

      Preemption

    • 장점

      • SPN 보다 Turn Around 시간 짧음

    • 단점

      • OverHead가 높음

  • Highest-Response-Ratio-Next (HRRN)

    Response Ratio ( R ) 가 높은 Process를 선택하는 것

    • Response Ratio

      q는 기다린 시간 R = (q + s)/s

    • Selection Function

      MAX[(q+s)/s]

    • Decision Mode

      Non-Preemption

    • 장점

      오래 걸리는 Process도 대기 시간에 따라 선택 받을 수 있는 기회가 있음 (Starvation 방지)

    • 단점

      프로세스 총 실행 시간 추정 필요

Burst

  • CPU Burst

    CPU가 Operation을 실행하기 위한 시간

  • I/O Burst

    CPU가 I/O를 기다리는 시간

Bound

  • CPU Bound

    CPU Burst 시간이 길고 I/O Burst 시간이 짧은 Cycle

  • I/O Bound

    I/O Burst 시간이 길고 CPU Burst 시간이 짧은 Cycle

  • Bound 파악하는 법

    Time Quantum을 다 쓰면 CPU Bound 프로세서

    아니면 I/O Bound 프로세서

Scheduling 기준

  • CPU Utilization

    시간당 CPU를 얼마나 활용하는가

  • Throughput

    시간당 Process를 몇개나 처리하는가

  • Turnaround Time

    Process가 들어와서 작업을 완료되기까지의 시간

  • Response Time

    Process가 들어와서 처음으로 응답되기까지 걸린 시간

  • Deadline

    Process가 특정 시간 내에는 끝내주길 바라는 Deadline을 제출했을 때 이것을 얼마나 만족시키는가

  • Fairness

    작업 처리 요구량에 비례해서 CPU 시간 할당을 얼마나 잘하는가

    요구량이 3:1이면 CPU 할당도 3:1로

    => 모든 것을 만족하기 힘들기에 상황에 맞춰 최적화 해야 함

Virtual Round Robin

CPU Bound Process의 유리함을 막음

I/O 리퀘스트가 있는 Process의 경우 지정된 quantum을 다 못쓰고 I/O 리퀘스트를 수행하러 Blocked Queue로 가면,

**처리가 끝난 뒤에 Ready Queue가 아니라 보조 Queue로 가서 Ready Queue보다 먼저 실행되며,

남은 Quantum Time 만큼을 보충해줌**

Multi Level Feedback Queue (MLFQ)

다단계의 Queue 존재

우선 순위 존재 및 우선순위가 높을수록 더 자주 실행

처음에는 Quantum Time이 짧은 SPN queue RR, 뒤로 갈 수록 Quantum Time이 긴 Round Robin이나 FIFO 방식을 사용

처음 단계에서 끝나지 않았다면 CPU Bound Process일 확룔이 높으므로 Overhead를 최소화하기 위해 Quantum Time이 높은 Queue로 보내서 처리

여러개의 Ready Queue로 나눠서 분할하는데, 우선적으로 작업이 짧은 Interactive한 Process에게 주며 시간이 오래 걸리는 Process는 QuantumTime을 늘려서 OverHead를 낮추는 방식

Foreground(높은 우선순위)는 Quantum Time이 짧은 Round Robin 방식

Background(낮은 우선순위)는 FIFO 방식 or Quantum Time을 크게

작업이 돌아가고 나서 결과를 보고 Time Slice를 다 쓰면 우선 순위가 낮아짐

  • Queue가 여러개가 있음
  • Queue마다 Scheduling 알고리즘이 다름
  • 승진, 강등 시키는 Method가 있음

시간에 따라서 Bound가 달라질 수 있으니 정확하지 않을 수 있음

interactive한게 많아지면 starvation 발생할 수 있음

=> 낮은 우선순위 큐에 오랫동안 머물러 있는 프로세스의 우선순위를 점진적으로 높여주는 노화(Aging) 기법을 통해 기아 문제를 해결할 수 있음

모든 작업이 처음부터 끝까지 CPU Bound, I/O Bound는 아니기 때문에 중간에 Process의 Bound가 변할 수 있기에 정확하지 않을 수 있음

=> Priority Boost로 일정 시간이 지나면 그 당시에 있던 모든 Job을 다시 최상위 Queue로 전부 옮겨서 실행하거나 하는 등의 보완책 존재

Multiprocessor Scheduling

  • Uniprocessor scheduling

    언제 어떤 Job을 실행시킬지 결정

  • Multiprocessor scheduling

    언제 어떤 Job을 어디서 실행 시킬 지 결정

    • 고려해야 할 점

      • 여러 개의 Queue를 유지
      • 캐쉬 활용
      • 어느 Processor에 할당할 것인지
      • 헤테로지니어스한 Processor 관리
      • Processor들 간 밸런스 관리

    • HW Issue : Cache Affinity

      • Cache Affinity (캐쉬 친화성)

        이전에 실행 시켰던 프로세서에서 수행하게 하면 캐쉬 성능을 통해 좀 더 성능을 향상 시킬 수 있음

        가능하다면 같은 프로세서에서 실행하게 하는 것이 좋음

        캐쉬 일관성이라는 것도 있음 캐쉬가 물리적으로 분리되어 있어서 어느 한 쪽에 있는 cache에 있는 값이 변경되면 다른 곳에 있는 cache도 수정되어야 함 => bus snooping

    • SW Issue : Concurrency

      • Concurrency

        병행성

        Queue는 Memory에 적재되고 공유됨

        이를 동시에 접근해서 처리할 때 결과가 실행 순서에 따라 올바르지 않는 문제 발생 (Race Condition)

        한번에 하나의 실행만 될 수 있도록 보장해줘야 함 -> Mutual Exclusion (상호배제)

Single Queue Multi Processor Scheduling

다중 프로세서 단일 큐

프로세서들이 공유하는 하나의 Queue가 존재

Queue의 맨 앞에 있는 Job을 각자 가져가서 처리함

  • 장점

    단순함

  • 단점

    Cache Affinity 불만족

    CPU가 늘어날수록 연산이 느려지게 됨

    Cache Affinity를 만족하려면 할 수는 있으나 동시성을 해결하기 위해 Lock을 사용 => 확장성 저하

Multi Queue Multi Processor

멀티 프로세서 멀티 큐

각 CPU 마다 별도의 Queue 존재

Process는 하나의 Queue에만 들어가게 함

실행 끝나면 같은 Queue에서 대기

  • 장점

    • Cache Affinity 만족 ( 같은 Processor 에게 실행되므로 )
    • 확장성 향상
    • 각 Queue마다 별도의 Scheduling 기법 적용 가능

  • 단점

    • Load imbalance (부하 불균등) 프로세스 실행 시간 예측 어려워 한쪽은 비어서 놀고 있을 수 있음

      => Migration : 불균등할 때 작업을 다른 프로세서로 옮김

      => Cache Affinity와 Trade Off

    • Work Stealing

      바쁜 Queue에서 여유로운 Queue로 작업을 옮김

      부하를 검사해서 한쪽이 비어있다면, busy한 Queue에서 작업을 가져오는 것

      자주하면 Overhead, 너무 적으면 Load Imbalance 발생

      => Threshold를 넘으면 migration 진행

O(1) 스케쥴러

여러개의 Queue가 있고 각 Queue마다 우선순위를 가짐

각 Queue가 Priority를 가지고 있고, 작업들은 각 Queue에 Linked List로 연결됨

그래서 우선 순위가 가장 높은 Task를 먼저 선택

두개의 Queue가 존재

Active run Queue, Expired run Queue

Time Slice를 다 쓰면 Expired Queue로 이동함

다 안썼으면 유지 or 돌아옴

그렇게 다 Expired Queue로 가면 다시 Expired를 Active로 Active를 Expired로 바꿔서 반복

프로세스의 수와 상관없이 고정된 배열 크기 만큼 순회하면 되므로 O(1)의 시간을 가짐(탐색, 삽입, 삭제 모두)

코어마다 멀티Queue가 존재 (SMP)

  • 단점

    • 정확한 수행 시간 보장 어려움, 확장성 한계 (고정된 우선순위 존재)

Proportional Share Scheduling

프로세스의 weight value에 비례해서 CPU를 할당

  • 사용처

    • Fair Queueing(Network, packet scheduling)
    • Proportional share : Process Scheduling

  • 최적화 기준

    얼마나 공정하게 CPU 사용시간을 보장할 수 있을 지

  • 종류

    • Completely Fair Scheduler (CFS)

      가상 runtime이 가장 적은 일을 고름

    • Weighted Fair Queueing (WFQ)

    • Lottery Scheduling(정리 필요)

      각 프로세스의 우선순 등 기준에 따라서 일종의 티켓을 비율만큼 부여하고 Select시 복권을 뽑듯이 랜덤하게 뽑아서 실행

      Non Deterministic함

      • 장점

        구현이 간단하고 빠름

      • 단점

        확률이라는 특징 상 실행 시간이 짧을 때 불공정하게 실행될 수 있음 => Unfairness Matrix 참고

    • Stride Scheduling

      각 프로세스의 우선순위 등 기준에 따라서 Stride를 부여하고 Pass가 가장 적은 것을 실행

      Deterministic함

      Stride는 보폭(비율), Pass는 걸음량 정도로 생각하면 됨

      보폭이 클 수록 적은 횟수로 많은 Pass를 가지게 되어 잘 선택되지 않으므로 추첨권과 반비례적임

      => 낮은 우선순위일수록 Stride를 크게 부여

      초기에는 전부다 passvalue가 0이었다가 Scheduling이 실행될 때마다 가장 낮은 Pass Value를 가지는 Process를 선택하고, 선택된 Process의 Pass Value에 stride를 더하면서 진행,

      다만 중간에 새로운 Process가 들어왔을 때 해당 Process의 Pass Value를 0으로 해버리면 한동안 그 Process가 작업을 독점해버리는 문제 존재

      • 장점

        Lottery Schduling의 실행 시간에 따른 공정함의 차이를 해결

      • 단점
        + 중간에 들어오는 Process의 독점 문제 생길 수 있음

© 2025. Na2te All rights reserved.