프로세스 스케줄링 (Process Scheduling)

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

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

• 여러 개의 프로세스가 시스템 내 존재
• 자원을 할당할 프로세스를 선택해야 함 -> 스케줄링 (Scheduling)
• 자원 관리
  • 시간 분할 관리 (Time Sharing)
    • 하나의 자원을 여러 스레드들이 번갈아 사용 
    • 예) 프로세서(processor)
    • 프로세스 스케줄링, 프로세서 사용시간을 프로세스들에게 분배 
  • 공간 분할 관리 (Space Sharing)
    • 하나의 자원을 분할하여 동시에 사용 
    • 예) 메모리 (memory)

 

스케줄링의 목적

• 시스템의 성능 (Performance) 향상
• 대표적 시스템 성능 지표 (index)
  • 응답 시간(Responce time)
    • 작업 요청으로부터 응답을 받을 때까지의 시간
  • 작업 처리량 (Throughput)
    
    • 단위 시간 동안 완료된 작업의 수
  • 자원 활용도 (Resource utilization)
    • 주어진 시간동안 자원이 활용된 시간
  • 공평성 (fairness)
    • 에) FIFO
  • 실행 대기 방지
    • 무기한 대기 방지( = 기아(Starvation) 방지)
  • 예측 가능성
    • 적절한 시간 안에 응답을 보장하는가 
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

이미지 출처: 운영체제, 한빛미디어

 

스케줄링의 기준 (Criteria)

• 스케줄링 기법이 고려하는 항목들
  • 프로세스(process)의 특성
    • I/O bounded 
    • compute-bounded
  • 시스템 특성
    • 일괄처리 시스템 (Batch system)
    • 대화형 시스템 (interactive system)
  • 프로세스의 긴급성 (urgency)
    • Hard / Soft - real time
    • non-real time
  • 프로세스 우선순위 (priority)
  • 프로세스 총 실행 시간 

CPU burst vs I/O burst

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

CPU burst는 CPU 사용 시간이다. 즉, 프로세서(processor)가 프로세스(process)를 처리하는 시간이다.

I/O burst는 입출력 대기 시간이다. 프로세스 처리 도중, 입출력 요청이 발생하면 I/O burst가 발생한다.

 

 

스케줄링의 단계 (Level)

• 발생하는 빈도 및 할당 자원에 따른 구분
  • 장기 스케줄링 (Job scheduling)
  • 중기 스케줄링 (Memory scheduling)
  • 단기 스케줄링 (Process scheduling)

장기 스케줄링 (Long-term Scheduling)

• Job scheduling
  • 시스템에 제출할 (=Kernel에 등록할) 작업 결정 
• 다중 프로그래밍 정도 조절
• 시스템 내 프로세스 수 조절
• 시분할 시스템에서는 모든 작업을 시스템이 등록
  • 결국, 장기 스케줄링 자체가 불필요하다. 

중기 스케줄링 (Mid-term Scheduling)

• 메모리 할당 결정 (Mermory allocation)
  • intermediate-level scheduling
  • Swapping (swap-in/swap out)

단기 스케줄링 (Short-term Scheduling)

• Process Scheduling
  • Low-level scheduling
  • 프로세서(processor)를 할당할 프로세스(process) 결정
• 가장 빈번하게 발생 
  • Interrupt
  • I/O (=block)
  • time-out
  • *매우 빨라야 함!

 

스케줄링 정책 (Policy)

• 선점 vs 비선점

선점이란? 어떤 프로세서가 프로세스를 처리 중일 때, 우선 순위 등의 이슈로 현재 처리중인 프로세스를 내쫓고 다른 프로세스가 프로세서를 할당받는 것. 

비선점 스케줄링

• 할당 받을 자원을 스스로 반납할 때까지 사용
  • 시스템 호출(System Call), I/O 등의 이유로 반납
  • 장점: Context switch overhead가 적음
  • 단점: 잦은 우선순위 역전, 평균 응답 시간 증가 

선점 스케줄링

• 타의에 의해 자원을 빼앗길 수 있음
  • 예) 할당 시간 종료, 우선순위가 높은 프로세스 등장
  • Context switch overhead가 큼
  • 시분할 시스템, 실시간 시스템에 적합

 

우선순위 (Priority)

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

 

기본 스케줄링 알고리즘들

FCFS (First-Come-First-Service)

• 비선점 스케줄링
• 스케줄링 기준: 도착 시간 (Ready Queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리 
• 자원을 효율적으로 사용 가능 
• 일괄처리 시스템에 적합 / 대화형 시스템에는 부적합
• 단점
  • Convoy effect
    • 한 프로세스가 긴 수행시간을 가지고 있다면, 그만큼 다른 프로세스들이 더 기다려야 하는 현상
  • 긴 평균 응답시간

 

RR (Round-Robin)

• 선점 스케줄링
• 스케줄링 기준: 도착 시간 (Ready Queue 기준)
• 자원 사용 제한 시간(time quantum)이 있음
  • 시스템 파라미터(변수)
  • 프로세스는 제한된 시간이 지나면 자원 반납
  • 특정 프로세스의 독점 방지
  • Context switch overhead가 큼
• 체감 프로세서 속도  = 실제 프로세서 성능의 1/n
• 대화형 시스템 / 시분할 시스템에 적합 

 

SPN (Shortest-Process-Next)

• 비선점 스케줄링
• 스케줄링 기준: 실행시간(burst time) 기준
  • 실행 시간이 가장 작은 프로세스를 먼저 처리
• 장점
  • 평균 대기시간(WT) 최소화
  • 시스템 내 프로세스 수 최소화
    • 스케줄링 부하 감소, 메모리 절약 -> 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답 시간 제공
• 단점
  • Starvation (무한대기) 현상 발생
    • Burst time이 긴 프로세스는 자원을 할당 받지 못할 수도 있음
      • Aging 등으로 해결
  • 정확한 실행 시간을 알 수 없음

        

SRTN (Shortest Remaining Time Next)

• SPN의 변형
• 선점 스케줄링
  • 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
• 장점
  • SPN의 장점 극대화
• 단점
  • 프로세스 생성 시, 총 실행 시간 예측이 필요함
  • 잔여 실행을 계속 추적해야함 = overhead
  • Context switching overhead
• 구현 및 사용이 비현실적

 

HRRN (High Response Ratio Next)

• SPN의 변형
  • SPN + Aging concepts
  • 비선점 스케줄링
• Aging Concepts
  • 프로세스의 대기 시간(WT)을 고려하여 기회를 제공
  • 스케줄링 기준: 응답률
  • 응답률 (Response ratio)
    • WT + BT / BT = 응답률
  • SPN의 장점 + 기아(Starvation) 방지
  • 실행 시간 예측 기법 필요 (overhead)

기본적인 스케줄링 기법들

MLQ (Multi-Level Queue)

• 작업(or 우선순위)별 별도의 ready queue를 가짐
  • 최초 배정된 queue를 벗어나지 못함
  • 각각의 queue는 자신만의 스케줄링 기법 사용
• Queue 사이에는 우선순위 기반의 스케줄링 사용
• 장점
  • 빠른 응답시간
• 단점
  • 여러 개의 Queue 관리 등 스케줄링 overhead
  • 우선순위가 낮은 queue는 starvation 현상 발생 가능 

MFQ (Multi-Level Feedback Queue)

• 프로세스의 Queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정 
• 특징
  • 동적 우선순위
  • 선점 스케줄링
  • 실행 시간 짧은 프로세스 우선
  • 입출력 위주 프로세스 우선
  • 적응성 향상
• 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음
• 단점
  • 설계 및 구현이 복잡, 스케줄링 overhead가 큼
  • Starvation 문제 등
• 변형 
  • 각 준비 큐마다 시간 할당량을 다르게 배정
    • 프로세스의 특성에 맞는 형태로 시스템 운영 가능
  • 입출력 위주 프로세스들을 상위 단계 큐로 이동
    • 프로세스가 block될 때 상위의 준비 큐로 진입하게 함 
    • 시스템 전체의 평균 응답 시간 줄임, 입출력 작업 분산시킴
  • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
    • Aging 기법
• MFQ 스케줄링의 변수들
  • Queue의 수
  • Queue별 스케줄링 알고리즘
  • 우선 순위 조정 기준
  • 최초 queue 배정 방법