logo
Published on

OS : 프로세스 스케줄링

Authors
  • avatar
    Name
    Bora Choi
    Twitter

프로세스 스케줄링

📝 스케줄링의 목적

다중 프로그래밍(multi-programming)

  • 여러개의 프로세스가 시스템 내 존재
  • 자원을 할당 할 프로세스를 선택해야 함 ⇒ 스케줄링(scheduling)
  • 자원 관리
    • 시간 분할(time sharing) 관리
      • 하나의 자원을 여러 스레드들이 번가아 가며 사용 : 프로세서(processor)
      • 프로세스 스케줄링(process scheduling) : 프로세서 사용 시간을 프로세스들에게 분배
  • 공간 분할(space sharing)관리
    • 하나의 자원을 분할하여 동시에 사용 : 메모리(memory)

스케줄링(scheduling)의 목적

  • 시스템 성능(performance) 향상
  • 대표적 시스템 성능 지표(index)
    • 응답시간(response time) : 작업 요청(submission)으로부터 응답을 받을때까지의 시간
    • 작업 처리량(throughput) : 단위 시간 동안 완료된 작업의 수
    • 자원 활용도(resource utilization) : 주어진 시간(Tc)동안 활용된 시간(Tr) : U= Tr/Tc
  • 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

시스템 성능 지표들

  • 평균 응답시간(mean response time) : 사용자 지향적
  • 처리량(throughput) : 시스템 지향적
  • 자원 활용도(resource utilization)
  • 공평성(fairness)
  • 실행 대기 방지 : 무기한 대기 방지
  • 예측 가능성(predictablity) : 적절한 시간 안에 응답을 보장하는 가

대기시간, 응답시간, 반환시간

  • 대기시간 (wating time) : 프로세스가 도착해서 실행 시작전까지 기다리는 시간
  • 응답시간 (response time) : 프로세스가 도착해서 첫번째 응답을 받을때까지 시간
  • 실행시간 (burst time) : 실제로 프로세스가 실행된 시간
  • 반환 시간 (turn-around time) : 도착을해서 종료까지의 시간

🎢 스케줄링 기준 및 단계

스케줄링 기준(criteria)

스케줄링 기법이 고려하는 항목들

  • 프로세스(process)의 특성
  • 시스템 특성
  • 프로세스의 긴급성 (urgency)
  • 프로세스 우선순위 (priority)
  • 프로세스 총 실행 시간 (total service time)

CPU burst vs I/O burst

  • 프로세스 수행 = CPU 상용 + I/O 대기

  • CPU burst : CPU 사용 시간

  • I/O burst : I/O 대기 시간

  • Burst time은 스케줄링의 중요한 기준 중 하나

    compute-bonded process : CPU burst > I/O busrst
    I/O-bonded process : I/O busrst > CPU burst

스케줄링의 단계 (Level)

발생하는 빈도 및 할당 자원에 따른 구분 Long-term scheduling

  • job scheduling : 시스템에 제출 할(kernel에 등록 할) 작업 결정
    • Admission scheduling, High-levle scheduling
  • 다중 프로그래밍 정도(degree) 조절 : 시스템 내에 프로세스 수 조절
  • I/O-bounded와 compute-bouded 프로세스들을 잘 섞어서 선택해야 함
    • 왜? 시스템의 효율을 높이기 위해
  • 시분할 시스템에서는 모든 작업을 시스템에 등록
    • Long-term scheduling이 불필요

Mid-term scheduling

  • 메모리 할당(memory allocation)
    • Intermediate-level scheduling
    • Swapping(swap-in/swap-out)

Short-term scheduling

  • ✴️ Process scheduling : CPU 할당
    • low-level scheduling
    • 프로세서(processor)를 할당할 프로세스(process)를 결정 : Processor scheduler, dispatcher
  • 가장 빈번하게 발생
    • interrupt, block(I/O), time-out, etc.
    • 매우 빨라야 함

👨‍⚖️ 스케줄링 정책

선점 / 비선점 (Preemptive/Non-Preemptive scheduling)

Non-Preemptive scheduling

  • 할당 받은 자원을 스스로 반납할 때까지 사용
    장점 context switch overhead가 적음
    단점 잦은 우선순위 역전, 평균 응답 시간 증가

Preemptive scheduling

  • 타의에 의해 자원을 빼앗길 수 있음

장점 응답성이 높음

  • Time-sharing system, real-time system 등에 적합

단점 context switch overhead가 큼

Priority

프로세스의 중요도

  • static priority(정적 우선순위)
    • 프로세스 생성시 결정된 priority가 유지 됨
    • 구현이 쉽고, overhead가 적음
    • 시스템 환경 변화에 대한 대응이 어려움
  • Dynamic priority(동적 우선순위)
    • 프로세스의 상태 변화에 따라 priority 변경
    • 구현이 복잡, priority 재계산 overhead가 큼
    • 시스템 환경 변화에 유연한 대응 가능

📅 기본 스케줄링 알고리즘들

FCFS(First-Come-First-Service)

  • Non-preemptive scheduling
  • 스케줄링 기준(criteria)
    • 도착시간(ready queue 기준)
    • 먼저 도착한 프로세스를 먼저 처리
  • 자원을 효율적으로 사용 가능
    • High resource utilization / 왜? 스케줄링 오버해드가 적다
  • Batch system에 적합, interactive system에 부적합
  • 단점
    • convoy effect : 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상(대기시간>>실행시간)
    • 긴 평균 응답시간(response time)

RR(Round-Robin)

  • Preemptive scheduling
  • 스케줄링 기준(criteria)
    • 도착시간(ready queue 기준)
    • 먼저 도착한 프로세스를 먼저 처리
  • 자원 사용 제한 시간(time quantum)이 있음
    • system parameter(δ)
    • 프로세스는 할당된 시간이 지나면 자원 반납 : timer-runout
    • 장점 특정 프로세스의 자원 독점(monopoly) 방지
    • 단점 context siwtch overhead가 큼
  • 대화형, 시분할 시스템에 적합
  • Time quantum (제한시간)(δ) 이 시스템 성능을 결정하는 핵심 요소
    • Very large (infinite) δ → FCFS
    • Very small time quantum → processor sharing
      • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것 처럼 느낌 : 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
      • High context switch overhead

SPN(Shrtest-Process-Next)

  • Non-preemptive scheduling

  • 스케줄링 기준 (Criteria)

    • 실행시간 (burst time 기준)
    • Burst time 가장 작은 프로세스를 먼저 처리 : SJF(Shortest Job First) scheduling

    장점

  • 평균 대기시간(WT) 최소화

  • 시스템 내 프로세스 수 최소화

    • 스케줄링 부하 감소 , 메모리 절약 → 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답 시간 제공

단점

  • Starvation (무한대기) 현상 발생
    • BT가 긴 프로세스는 자원을 할당받지 못할 수 있음 : Aging 등으로 해결 (e.g., HRRN)
  • 정확한 실행 시간을 알 수 없음 : 실행 시간 예측 기법이 필요

SRTN(Shortest Remaining Time Next)

  • SPN의 변형
  • Preemptive scheduling
    • 잔여 실행 시간이 더 적은 프로세스가 ready상태가 되면 선점됨

장점

  • SPN의 장점 극대화

단점

  • 프로세스 생성시, 총 실행 시간 예측이 필요함
  • 잔여 실행을 계속 추적해야 함 = overhead
  • Context switching overhead

⇒ 구현 및 사용이 비현실적

HRRN(High-Response-Ratio-Next)

  • SPN의 변형
    • SPN + Aging concepts, Non-preemptive scheduling
  • Aging concepts
    • 프로세스의 대기 시간(WT)을 고려하여 기회를 제공
  • 스케줄링 기준 (Criteria)
    • Response ratio가 높은 프로세스 우선
  • 𝑹𝒆𝒔𝒑𝒐𝒏𝒔𝒆 𝒓𝒂𝒕𝒊𝒐 = (𝑾𝑻+𝑩𝑻)/𝑩𝑻 (응답률)
    • SPN의 장점 + Starvation 방지
    • 실행 시간 예측 기법 필요 (overhead)

MLQ(Multi-levelQueue)

  • 작업 (or 우선순위)별 별도의 ready queue를 가짐
    • 최초 배정 된 queue를 벗어나지 못함
    • 각각의 queue는 자신만의 스케줄링 기법 사용
  • Queue 사이에는 우선순위 기반의 스케줄링 사용
    • E.g., fixed-priority preemptive scheduling

장점

  • 빠른 응답시간 (?) : 중요도가 높은 일은 응답시간이 빠르다

단점

  • 여러 개의 Queue 관리 등 스케줄링 overhead
  • 우선순위가 낮은 queue는 starvation 현상 발생 가능

MFQ(Multi-level Feedback Queue)

  • 프로세스의 Queue간 이동이 허용된 MLQ
  • Feedback을 통해 우선 순위 조정
    • 현재까지의 프로세서 사용 정보(패턴) 활용
  • 특성
    • Dynamic priority
    • Preemptivescheduling
    • Favor short burst-time processes
    • Favor I/O bounded processes
    • Improveadaptability
  • 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의효과를볼수있음

단점

  • 설계 및 구현이 복잡, 스케줄링 overhead가 큼
  • Starvation문제등

변형

  • 각 준비 큐마다 시간 할당량을 다르게 배정

    • 프로세스의 특성에 맞는 형태로 시스템 운영 가능
  • 입출력 위주 프로세스들을 상위 단계의 큐로 이동,우선 순위 높임

    • 프로세스가 block될 때 상위의 준비 큐로 진입하게 함
    • 시스템 전체의 평균 응답 시간 줄임,입출력 작업 분산 시킴
  • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동

    • 에이징 (aging) 기법
  • Parameters for MFQ scheduling

    • Queue의 수
    • Queue별 스케줄링 알고리즘
    • 우선순위조정기준
    • 최초 Queue 배정 방법
    • ...

📖 Case Study : scheduling in OS

🐧 Scheduling in Unix Systems

  • Interactive system
    • Priority-based scheduling, preemptive scheduling
  • Priority
    • Kernel priority
      • 커널모드에있는프로세스
      • interruptible/uninterruptible priority
    • User priority
      • 사용자모드에있는프로세스
  • Clock handler
    • 주기적으로 인터럽트 발생
    • 모든 프로세스들의 우선순위 조정
  • 스게줄링 기법
    • 높은 우선순위 우선
      • 프로세서 사용량에 따라 우선순위가 주기적으로 변함
    • MFQ 스케줄링 기법
  • 우선순위 조정
    • 프로세서 사용 반영 (decay computation)
      • 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕 = 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕/ 𝟐
    • 우선순위 조정
      • 𝑷𝒓𝒊𝒐𝒓𝒊𝒕𝒚 = 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕 / 𝟐+ 𝒃𝒂𝒔𝒆𝑷𝒓𝒊𝒐𝒓𝒊𝒕𝒚 + 𝒏𝒊𝒄𝒆𝑽𝒂𝒍𝒖𝒆

🪟 Scheduling in windows

  • Thread scheduling
  • Priority-based, Preemptive scheduling
  • 32-level priority scheme
    • Variable class: 1-15
    • Real-time class: 16-32
  • MLQ scheduling
    • 각각의 우선순위 마다 큐(queue)를 가짐
    • 스케줄러(scheduler)는 높은 우선순위 큐부터 순차적 으로 방문하며, 실행할 준비가 된 스레드를 찾음
  • 스케줄링 기법
    • 스레드가 자신의 time quantum을 다 소비하고 나올때 →우선순위 하향 조정 (variable class의 경우)
    • Wake-up 시→우선순위 상향 조정 (variable class의 경우)
      • 상향 정도는 스레드가 대기중이었던 작업에 종속적
        • 예) 키보드/마우스 I/O→크게 상향 디스크 I/O → 약간 상향