CPU Scheduling

다중프로그래밍

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

스케줄링 목적

• 시스템 성능 향상
• 대표적 시스템 성능 지표 : 성능에 대한 정의
  • 응답시간
    • 작업 요청으로부터 응답을 받을때까지 시간
  • 작업 처리량
    • 단위 시간동안 완료된 작업 수
  • 자원 활용도
    • 주어진 시간동안 자원이 활용된 시간
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

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

• 대기시간(Waiting time) : 도착해서 실행 시작하기 전까지 대기시간
• 응답시간(Response time) : 도착해서 첫 번째 출력까지 걸린 시간
• 실행시간(Burst time) : 실행시작부터 실행종료까지 시간
• 반환시간(turn-around time) : 도착부터 실행종료까지 시간

스케줄링 기준

• 스케줄링 기법이 고려하는 항목
• 프로세스의 특성
  • I/O bounded or Compute-bounded
• 시스템 특성
  • batch system or interactive system
• 프로세스의 긴급성(urgency)
• 프로세스 우선순위

CPU burst vs I/O burst

• 프로세스 수행 = CPU 사용 + I/O 대기
• CPU burst
  • cpu 사용 시간
  • cpu burst 시간이 더 많은 경우 compute-bounded process라 한다
• I/O burst
  • I/O 대기 시간
  • I/O 대기 시간이 더 많은 경우 I/O bounded process라 한다

스케줄링의 단계

발생하는 빈도 및 할당 자원에 따라 구별한다.

• Long-term scheduling
• Mid-term scheduling
• short-term scheduling

Long-term Scheduling

가끔 발생하는 작업

• Job scheduling
  • 시스템에 제출 할(kernel에 등록 할) 작업(job) 결정
• 다중프로그래밍 정도(degree) 조절
  • 시스템 내에 프로세스 수 조절
• I/O-bounded 와 compute-bounded 프로세스들을 잘 섞어서 선택해야 함
  • 하나를 놀리지 않기 위함
• 시분할 시스템에서는 모든 작업을 시스템에 등록
  • Long-term scheduling 덜 중요

Mid-term Scheduling

• 메모리 할당 결정(memory allocation)

Short-term Scheduling

가장 자주 일어나는 스케줄링

• Process scheduling
  • 프로세서를 할당할 프로세스를 결정
• 가장 빈번히 발생
  • 매우 빨라야 함

스케줄링 정책

• 선점 vs 비선점
• 우선순위

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

• Non-preemptive scheduling
  • 할당 받을 자원을 스스로 반납할 때까지 사용
    • sys call, I/O 등
  • 장점
    • Context switch overhead 적음
  • 단점
    • 잦은 우선순위 역전, 평균 응답 시간 증가
• preemptive scheduling
  • 타의에 의해 자원을 빼앗길 수 있음
    • 할당 시간 종료, 우선순위 높은 프로세스 등장 등
  • 응답성이 높아진다
  • context switch overhead가 큼
  • 시분할, 실시간 시스템 등에 적합

Priority

프로세스의 중요도

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

기본 스케줄링 알고리즘

FCFS(First-come-First-Service)

• Non-preemptive scheduling
• 스케줄링 기준
  • 도착 시간
  • 먼저 도작한 프로세스를 먼저 처리
• 자원을 효율적으로 사용 가능
  • scheduling overhead가 적어진다
• Batch system에 적합하다, interactive system에는 부적합하다
• 단점
  • Convoy effect
    • 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상(대기시간 >> 실행 시간)
  • 긴 평균 응답 시간

RR(Round-Robin)

• preemptive scheduling
• 스케줄링 기준(Criteria)
  • 도착 시간(ready queue) 기준
  • 먼저 도착한 프로세스를 먼저 처리
• 자원 사용 제한 시간(time quantum)이 있다
  • System parameter
  • 프로세스는 할당된 시간이 지나면 자원 반납
    • timer-runout
    • 큐의 가장 뒤로 간다
  • 특정 프로세스의 자원 독점 방지
  • Context switch overhead가 큼
• 대화형, 시분할 시스템에 적합
• Time quantum 이 시스템성능을 결정하는 핵심 요소
  • 매우 크면 FCFS와 같아진다
  • 제한시간이 매우 작으면 -> 프로세서를 공유하는 듯한 느낌이다
    • 체감 프로세서 속도 = 실제 프로세서 성능의 1 / n
  • High context switch overhead

SPN(Shortest-Processing-Next)

• Non-preemptive scheduling
• 스케줄링 기준
  • 실행시간 기준(burst time 기준)
  • Burst time 가장 작은 프로세스를 먼저 처리
  • 실행시간 가장 짧은 것 부터 처리
• 장점
  • 평균 대기시간 최소화
  • 시스템 내 프로세스 수 최소화
    • 스케줄링 부하 감소, 메모리 절약 -> 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답 시간 제공
• 단점
  • Starvation 현상 발생
    • BT가 긴 프로세스는 자원을 할당 받지 못할 수 있음
      • Aging 등으로 해결 (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가 높은 프로세스 우선
• Response ratio = (WT + BT) / BT
  • SPN 장점 + Starvation 방지
  • 실행 시간 예측 기법 필요(overhead)

MLQ, MFQ

FCFS나 RR은 공평하고 SPN SRTN HRRN 은 효율성과 성능이 좋지만 실행시간 예측에 부하가 걸린다. 또 정확하지도 않다.

그래서 MLQ와 MFQ를 쓴다.

MLQ

• 작업별 별도의 ready queue를 가짐
  • 최초 배정 된 queue를 벗어나지 못함
  • 각각의 queue는 자신만의 스케줄링 기볍 사용
• Queue 사이에는 우선순위 기반의 스케줄링 사용
  • 우선순위 높은 큐에 있는거 먼저 처리하는 거
• 장점
  • 빠른 응답시간??
  • 우선순위가 높은 경우 빨라질 수 있기는 하지만 아무래도 여러 문제가 많다
• 단점
  • 여러 개의 queue 관리 등 스케줄링 overhead
  • 우선순위가 낮은 queue는 starvation 현상 발생 가능
  • 유연하지도 않다

MFQ(Multi level Feedback Queue)

• 프로세스간의 Queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정
  • 현재까지의 프로세서 사용 정보 활용
• 특성
  • dynamic priority
  • preemptive scheduling
  • favor short burst-time processes
  • favor I/O bounded processes
  • improve adaptability
• 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음
• 단점
  • 설계 및 구현이 복잡, 스케줄링 overhead가 큼
  • starvation 문제
• 변형
  • 각 준비 큐마다 시간 할당량을 다르게 배정
  • 입출력 위주 프로세스들을 상위 단계의 큐로 할당, 우선순위 높임
    • 프로세스가 block될 때 상위의 큐로 진입하게 함
    • 시스템 전체의 평균 응답 시간 줄임, 입출력 작업 분산 시킴
  • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
    • 에이징 기법