프로세스 스케줄링[OS]

04 프로세스 스케줄링

다중 프로그래밍\(_{multiprogramming}\)

• 컴퓨터 시스템에서 여러 개의 프로세스들을 동시에 운영하여 자원의 이용률을 향상시키는 기법
• CPU가 쉬는 시간을 갖지 않도록 하는 것
• 자원 관리
  • 시간 분할\(_{time \ sharing}\) 기법
    • 하나의 자원을 여러 프로세스들이 번갈아 사용하는 기법
    • 대표적인 예 : 프로세서
    • 프로세스 스케줄링\(_{process \ scheduling}\) 기법
      • 프로세스들에게 프로세서 자원을 할당해 주는 일
      • 자원을 할당하는 순서를 결정
  • 공간 분할\(_{space \ sharing}\) 기법
    • 하나의 자원을 분할하여 동시에 같이 사용하는 기법
    • 대표적인 예 : 주기억장치

    

CPU - I/O 버스트 사이클

• 프로세스 실행은 CPU 실행과 입출력(I/O) 대기의 순환으로 구성
• 프로세스 실행은 CPU 버스트로 시작하여 CPU 버스트로 종료
• 프로세스의 종류
  • I/O-bound process
    • 대부분의 시간을 연산보다는 입출력을 하는 데 소비
    • 많은 짧은 CPU 버스트를 가짐
  • CPU-bound process
    • 대부분의 시간을 연산하는데 소비
    • 매우 긴 CPU 버스트를 가짐

• 좌측은 CPU와 I/O 버스트 교대를, 우측은 CPU 버스트 시간 히스토그램이다.
• 긴 CPU 버스트는 발생하지 않는다는걸 알 수 있음
• 주로 I/O 버스트의 빈도가 많다는걸 알 수 있음

프로세스 스케줄링

• 멀티프로그래밍의 목적
  • CPU 활용성 극대화를 위해 항상 어떤 프로세스가 실행되도록 유지
  • 따라서 CPU에서 실행되는 프로세스를 자주 교환
• 프로세스 스케줄러\(_{Process \ scheduler}\)
  • CPU에서 실행 가능한 프로세스를 선택
  • 프로세서에서 동작할 수 있는 프로세스는 단 한 개 싱글 CPU에 해당하는 내용 (멀티 CPU는 X)
  • 나머지 프로세스들은 대기
• 스케줄링 발생 시기
  1. 실행 상태 → 대기 상태 (입출력 요구, wait)
  2. 실행 상태 → 준비 상태 (인터럽트)
  3. 대기 상태 → 준비 상태 (입출력 완료)
  4. 프로세스 종료 시
• 1, 4의 경우에서만 스케줄링이 일어나는 시스템: 비선점적\(_{nonpremptive}\)
  • 스케줄된 프로세스는 프로세스 종료나 대기 상태로 변하면서 CPU를 놓칠 때까지 CPU를 계속 사용
• 이외의 경우: 선점적\(_{preemptive}\) 스케줄링
  • 우선 순위가 더 높은 프로세스가 도착할 때 실행중인 프로세스의 실행을 멈추고 CPU 사용을 넘겨준다.

디스패처\(_{Dispatcher}\)

• CPU의 제어를 프로세스(단기 스케줄러가 선택한)에게 넘겨주는 역할
  1. 문맥 교환 수행
  2. 사용자 모드로 변환
  3. 프로그램 카운터의 주소로 이동\(_{jump}\)
• Dispatch Latency
  • 디스패처가 어떤 프로세스를 멈추고 다른 프로세서를 실행시키는 데 걸리는 시간

스케줄링\(_{Schedulers}\)

• 스케줄링의 종류
  • 수행 단계(프로세스의 실행 시점 기준 프로세스의 상태)에 따라 분류
  • 장기, 중기, 단기 스케줄링으로 구분
  • 각 단계마다 서로 다른 스케줄링 정책 이용 → 시스템 효율성 증대
• 단기 스케줄러\(_{Short-term \ Scheduling}\) (실행상태로 진입)
  • 스케줄링 알고리즘
    • CPU에 프로세스를 얼마나 할당할지 시간을 정하는 단위 = \(_{Milliseconds}\)
  • 준비 상태의 프로세스들에 대해 프로세서 할당 순서 결정
  • 프로세스(단기) 스케줄링을 발생시키는 사건
    • 인터럽트가 발생:
      • 입출력 인터럽트\(_{I/O \ interrupt}\)
      • 클럭 인터럽트\(_{Clock \ Interrupt}\)
    • 실행중인 프로세스에 의해 시스템 콜이 발생
• 중기 스케줄러\(_{Medium-term \ Scheduling}\) (활성상태로 진입)
  • 메모리 공간을 확보하거나 또는 프로세스의 혼합을 개선하기 위해서 디스크로 교체
  • Swap-in or swap-out
  • 교체된 프로세스를 다시 메모리로 적재

  

• 장기 (작업) 스케줄러\(_{Long-term \ Scheduling}\) (프로세스 등록)
  • 프로세스를 준비 상태로 만든다.
    • 프로세스를 준비 상태로 만들 때 사용되는 시간 단위 = \(_{seconds, \ minutes}\)
    • 시스템에 입력되는 작업이나 명령 중 커널에 등록(프로세스) 순서 결정
  • 다중 프로그래밍의 정도
    • 임의의 시간에 시스템에 존재할 수 있는 프로세스의 전체 수를 결정
  • 입출력과 계산 작업의 혼합
    • 자원 활용의 균형

  

스케줄링 알고리즘의 기준

• CPU 이용률\(_{Utilization}\)
  • CPU의 지속적 활용 정도
• 작업 처리율\(_{Throughput}\)
  • 단위 시간당 완료된 프로세스의 수
• 반환/총처리 시간\(_{Turnaround \ Time}\)
  • 한 프로세스가 실행되는 시간
  • 기계에 진입한 시간과 완료한 시간의 차이
• 대기 시간\(_{Waiting \ Time}\)
  • 준비 큐에서 대기하는 시간
• 응답 시간\(_{Response \ Time}\)
  • 요청을 제출하고부터 첫 번째 응답이 나올 때까지의 시간
• 스케줄링 알고리즘 최적화 기준
  • 최대 CPU 이용률, 최대 처리량
    • CPU를 오래 사용하고, 단위 시간당 처리하는 작업의 수가 많을수록 좋음
  • 최소 반환 시간, 최소 대기 시간, 최소 응답 시간
    • 프로세스가 작업 완료 후 종료까지의 시간이 짧고, 준비 상태에서 CPU를 기다리는 시간이 짧으며, 사용자가 작업을 요청한 후 시스템의 응답까지의 시간이 짧을수록 좋다.

스케줄링 기법

• 스케줄링 기법에 영향을 주는 정책
  • 선점/비선점 정책
  • 우선순위
• 선점/비선점 정책
  • 비선점 스케줄링\(_{Nonpreemptive \ Scheduling}\)
    • 프로세스가 할당 받은 자원을 스스로 반납할 때까지 사용 (작업 완료 또는 반납)
    • no preemption, 대표적 예: FIFO
    • 장점
      • 프로세스의 종료 시간에 대해 비교적 정확한 예측 가능
    • 단점
      • 일시적으로 우선순위가 지켜지지 않을 수 있음
      • 평균 응답 시간 길어질 수도 있음
  • 선점 스케줄링\(_{Preemptive \ Scheduling}\)
    • 운영체제가 자원을 할당 받은 프로세서의 자원을 선점하여 다른 프로세스에 할당
    • 대화형의 시분할 시스템, 실시간 시스템 등에 적합
    • 문맥 교환을 위한 오버헤드 증가
• 우선 순위
  • 프로세스의 중요도를 숫자로 표현
  • 분류
    • 정적 우선 순위\(_{Static \ Priority}\)
      • 프로세스 생성 당시에 부여되고, 실행 중 불변
      • 구현 단순, 적은 오버헤드
      • 시스템 환경의 변화에 적절한 대응 곤란
    • 동적 우선 순위\(_{Dynamic \ Priority}\)
      • 프로세스 생성 당시에 초기 우선순위 부여
      • 시스템과 프로세스의 상태 변화에 따라 우선순위 변경
      • 구현 복잡, 우선순위의 수시 계산으로 오버헤드 큼
      • 환경 변화에 유연한 대응 가능

스케줄링 알고리즘

• FIFO\(_{First-In \ First-Out}\) 스케줄링
  • 특징
    • 비선점 스케줄링
    • FCFS\(_{First \ Come \ First \ Served}\)
    • 준비 상태에 먼저 도착한 프로세스에게 먼저 프로세서 할당
    • 자원의 효율성 높음
    • 일괄 처리 시스템 등에 적합
    • 대화형 시스템에 부적합
  • 단점
    • 프로세서를 장시간 독점하는 경우 다른 프로세스들이 장시간 대기함
    • 평균 응답 시간이 길어질 수 있음

  • FIFO 스케줄링 예시

    

    • 종료 시간, 응답 시간, 평균 응답 시간?
• 우선순위 스케줄링
  • 우선순위 스케줄링 알고리즘
    • 우선순위가 각 프로세스에 주어지고 CPU를 최고 우선순위를 가진 프로세스에 할당
    • 우선순위가 같은 프로세스들은 FCFS 스케줄링
  • 우선순위: 내부 요인과 외부 요인
    • 내부 (실행 시간, 메모리 사용 공간, 사용 파일의 수)
    • 외부 (요금, 사용 부서 등)
  • 무한 정지\(_{Indefinite \ Blocking}\) 상태, 기아 상태
    • 낮은 우선순위 작업들이 CPU를 사용하지 못하는 경우
      • 해결 방법: 시스템에 대기하는 시간이 증가함에 따라 우선순위를 높인다 ⇒ 에이징\(_{aging}\) 이라고 불림

  • 예시

    

    • 평균 대기 시간 = \(\frac6{5} = 8.2\)

RR\(_{Round-Robin}\) 스케줄링

• 선점 스케줄링
• 준비 상태에 먼저 도착한 프로세스에게 먼저 프로세서 할당 (FIFO)
• 각 프로세스들에게 시간 할당량\(_{Time \ Quantum}\) 지정 (10~100msec)
• 시간 할당량을 소모한 프로세스는 프로세서를 반납하고 준비 상태로 전이
• 한 프로세스에 대한 프로세서 독점 방지
• 프로세서 선점에 따른 문맥 교환 오버헤드 증가
• 대화형 시스템, 시분할 시스템에 적합
• 시간 할당량의 결정이 시스템 성능에 영향을 끼침

SPN\(_{Shortest-Process-\ Next}\) 스케줄링

• SPF\(_{Shortest \ Process \ First}\) scheduling
• SJF\(_{Shortest \ Job \ First}\) scheduling
• 총 실행 시간이 가장 짧은 프로세스부터 스케줄링 하는 기법
• 비선점 스케줄링
• 장점
  • 평균 대기 시간, 평균 응답시간 최소화
  • 시스템 내의 대기 프로세스 수를 최소화
  • 많은 프로세스들에게 빠른 응답 시간 제공
  • 준비 큐의 크기 감소, 저장 공간 오버헤드 줄임
• 단점
  • 무기한 연기\(_{Indefinite \ Postponement}\) 현상 발생 가능
    • 실행 시간이 긴 프로세스들의 무한 대기 가능
    • 에이징 기법으로 해결 가능 (HRRN 방법)
  • 프로세스 생성시 총 실행 시간에 대한 정확한 계산 불가능
    • 각 프로세스의 실행 시간에 대한 추정 필요

SRTN\(_{Shortest-Remaining-Time-Next}\) 스케줄링

• SPN 스케줄링의 선점형 변형
• 준비 상태의 프로세스들 중에서 서비스 시간이 가장 적게 남은 프로세스에게 먼저 프로세서 할당
• 선점 스케줄링
  • 프로세스 실행 중 남은 실행 시간이 더 적은 프로세스가 준비 상태에 들어올 경우 선점됨
• 단점
  • 프로세스 생성시 총 실행 시간 추정 작업 필요 (SPN과 동일)
  • 잔여 실행 시간에 대한 계속적인 계산 오버헤드 증가
  • 실행 시간이 긴 프로세스들의 평균 응답 시간 길어짐
  • 실행시간이 짧은 프로세스가 많은 경우 잦은 선점으로 문맥 교환 오버헤드 증대

HRRN\(_{High \ Response \ Ratio \ Next}\) 스케줄링

• 실행 시간이 긴/짧은 프로세스들간의 불평등(SPN) 심화 방지 기법
• 비선점 스케줄링
• 응답률이 가장 높은 프로세스에게 우선권을 주는 방식 = 대기시간이 긴 프로세스는 응답률이 높다.

  • 응답률: 서비스 시간에 대한 대기 시간 비율

    \[응답률(우선순위) = \frac{대기시간 + 서비스 시간}{서비스 시간}\]
  • 특정 프로세스의 장시간 대기 방지
    • 준비상태에서 기다리는 시간이 길어질수록 우선 순위 향상됨
  • SPN 스케줄링 기법의 효과 얻음
    • 총 실행 시간이 짧은 프로세스가 긴 프로세스 보다 우선 스케줄링
  • 단점
    • 응답률 계산을 위해 프로세스의 총 실행시간 추정 오버헤드 발생

다단계 피드백 큐\(_{MFQ}\)

• Multi-level feedback queue scheduling
  • 프로세스들에 대한 사전 정보(실행시간)가 없는 경우
    • SPN, SRTN, HRRN을 사용할 수 없는 경우
  • 선점 정책, 동적 우선순위 스케줄링
  • 준비 상태의 큐를 여러 개 두어 스케줄링
    • 각각의 큐는 서로 다른 스케줄링 방법 사용
• MFQ 스케줄링 기법의 기본 목적
  • 짧은 실행 시간을 요구하는 프로세스 선호
  • 입출력 위주의 프로세스 선호 (짧은 프로세서 시간 사용)
  • 신속한 프로세스의 성격 분석으로 적응적으로 스케줄링
• MFQ를 위한 기본 개념
  • 피드백\(_{Feedback}\)

    • 프로세스의 실행 예상 시간을 모름

      → 현재까지 프로세서를 사용한 시간을 근거로 스케줄링

  • 다단계 피드백 큐\(_{multi-level \ feedback \ queue}\)
    • 다수의 준비 큐
    • 준비 상태로 들어오는 프로세스들이 이전의 디스패치 시기와는 다른 준비 큐로 진입할 수 있게 하는 경우

  • 큐잉 모델\(_{Queuing \ model}\)

    

• MFQ 스케줄링 기법
  • dynamic priority 사용
  • preemptive scheduling (프로세스 시간할당량 소모 후 선점됨)
  • I/O-bound process들을 선호 (우선순위 유지)
  • 연산 위주의 process는 시간할당량 소모 후 우선순위 낮아짐
  • 실행 시간이 짧은 프로세스들 선호 (총 실행시간이 짧은 프로세스는 조기 종료, 긴 경우는 우선순위가 낮아짐, SPN의 효과)
  • 장점
    • 매우 적응성 있는 기법임 (사전 정보를 사용하지 않고 실행 중의 프로세스 특성을 사용)
    • 프로세스들에 대한 사전 정보 없이도 SPN, SRTN, HRRN 등의 효과 보임

• 그림 해석
  • n+1개의 큐
    • 우선순위: RQ0 > RQ1…
  • 새로운 프로세스
    • 최고 큐에서 대기(높은 우선순위)
    • 낮은 큐에 실행되는 프로세스 존재해도 선점
  • 시간할당량을 모두 소비
    • 짧은 프로세스와 입출력 중심 프로세스에게 높은 우선순위 할당
    • 실행 시간이 긴 프로세스는 짧은 프로세스나 입출력 중심 프로세스의 종료 후에 실행
  • 시간할당량 미 소비
    • 같은 큐로 진입(입출력 등 프로세서반납)
  • 각 큐는 서로 다른 스케줄링 방식
    • 가장 낮은 수준의 큐: RR
    • 나머지 수준의 큐: FIFO
• MFQ 스케줄링 기법의 변형
  • MFQ 스케줄링 기법의 문제점
    • 시스템 부하 증가 시
      • 우선 순위가 낮아진 프로세스의 무기한연기 현상 발생 가능

• 다단계 피드백 큐의 예

  3개의 큐(0 ~ 2): Q0 – 규정 시간량 = 8 milliseconds Q1 – 규정 시간량 = 16 milliseconds Q2 – FCFS

  스케줄링 새로운 작업은 큐 Q0에 입력 시간량 8을 할당 받아 실행 만약 실행이 끝나지 않으면, 그 작업은 Q1의 끝으로 전달 Q1 에서 16을 할당 받아 실행 여기서도 끝나지 않으며 Q2로 전달 Q2 에 있는 작업들은 Q0 와 Q1 이 비어있는 경우에 FCFS 방식으로 실행

유닉스 운영체제의 스케줄링 기법

• Unix OS의 프로세스 스케줄링
  • 우선순위 기반 스케줄링 사용
• 우선순위 조정
  • 프로세스 테이블
    • 커널은 시스템에 존재하는 모든 프로세스에 대한 정보를 저장
  • 프로세스의 우선순위
    • 프로세서 시간할당량이 크면 → 우선순위 낮춤 (공평성)
    • 커널 우선순위\(_{kernel \ priority}\): high
      • 커널 모드에 있는 프로세스가 배정받는 우선순위
    • 사용자 우선순위\(_{user \ priority}\): low
      • 사용자 모드에 있는 프로세스가 배정받는 우선순위
  • 클럭 핸들러\(_{clock \ handler}\)
    • 주기적으로 인터럽트 발생, 모든 프로세스들의 우선순위 조정함

• 커널 모드가 사용자 모드보다 권한이 더 높음 ⇒ 우선순위가 높음
• 인터럽트를 허용하지 않는 프로세스가 허용하는 프로세스보다 우선순위가 더 높음

유닉스 운영체제의 스케줄링 기법

• 스케줄링 기법 개요
  • 우선순위가 높은 프로세스부터 디스패치하는 정책 사용
  • 프로세스의 우선순위
    • 프로세서 사용량에 따라 주기적으로 변함
  • Unix OS의 스케줄링 기법은 MFQ 기반임
• 스케줄링 기법
  • 우선 순위 조정 과정 (클럭 틱 발생 → 클럭 핸들러가 주기적으로 계산)

    • Decay 연산

      \[CPUCount = \frac{CPUCount}2\]

    • 우선순위 조정

      \[Priority = \frac{CPUCount}2 + basePriority + niceValue\]
      • basePriority: 미리 정해진 값, 초기 우선 순위
      • niceValue: 자신의 우선순위를 낮출 때 더하는 값

• 스케줄링 예시

  

  • 1초가 지날때마다 시간 할당량을 다 사용해서 Decay연산과 우선순위를 조정한다.
  • 때문에 시간이 지날때마다 우선순위는 증가하고 CPUCount는 줄어든다.
    • P1이 처음 실행하고 그 다음 클럭에는 우선순위가 P2에 밀려서 P2가 먼저 실행된다.
    • 이후에는 P2가 우선순위가 내려가 P3가 실행된다.
    • 위 순서가 반복된다.