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

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

• 여러개의 프로세스가 시스템 내 존재
• 자원을 할당 할 프로세스를 선택 해야 함
  cpu가 하나 존재한다고 하면 프로세스는 cpu를 번갈아 가면서 사용해야 한다.
  • 스케줄링(Scheduling)
• 자원 관리
  • 시간 분할 (time sharing) 관리
    • 하나의 자원을 여러 스레드들이 번갈아 가며 사용
    • 예) 프로세서(Processor)
    • 프로세스 스케줄링 (Process scheduling)
      • 프로세서 사용시간을 프로세스들에게 분배
  • 공간 분할 (space sharing) 관리
    • 하나의 자원을 분할하여 동시에 사용
    • 예) 메모리 (memory)

스케줄링 (Scheduling)의 목적

• 시스템 성능(performance) 향상
  • 시스템의 효율성을 위해 스케줄링 사용
• 대표적 시스템 성능 지표 (index)
  성능이란 것은 모호하기 때문에 성능의 지표로 나타낼 수 있음.
  • 응답시간 (response time)
    • 작업 요청 (submission)으로부터 응답을 받을 때까지의 시간
  • 작업 처리량 (throughput)
    • 단위 시간 동안 완료된 작업의 수
  • 자원 활용도 (resource utilization)
    • 주어진 시간동안 자원이 활용된 시간
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택
  • 응답시간 같은 경우는 interactive system나 real-time system에서 중요한 지표가 된다.
  • 작업 처리량은 batch system 처럼 응답시간보다 얼마나 많은 단위 시간 동안 많은 작업을 처리했느냐가 중요한 시스템에 이용된다.
  • 만약 비싼 장비를 사용할 시 그 장비를 얼마나 많이 활용하느냐가 중요하다. 그럴 때 자원 활용도 지표가 필요하다.

시스템 성능 지표들

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

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

사진 출처 - https://youtu.be/_gNeoGQx-Tc

• Waiting time : 프로세스가 도착하면 프로세스가 기다리고 있다가 실행을 시작한다.
• Response time : 작업이 수행되다 첫번째 출력이 일어납니다.
• Burst time : 실제로 프로세스가 실행된 시간
• Turn-around time : 프로세스가 최초로 도착한 시간부터 작업이 종료되기까지의 시간을 의미

스케줄링 기준 및 단계

스케줄링 기준 (Criteria)

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

프로세스가 어떤 프로세스를 프로세서에게 할당해줄지 정하는 기준

• 프로세스(process)의 특성
  • I/O-bounded or compute-bounded
• 시스템 특성
  • Batch system or interactive system
    시스템 마다 특성이 다르기 때문에 스케줄링 선택의 기준이 됨
• 프로세스의 긴급성(urgency)
  • Hard- or soft- real time, non-real systems
• 프로세스 우선순위 (priority)
• 프로세스 총 실행 시간 (total service time)

CPU burst VS I/O burst

사진출처 - https://zoomkoding.github.io/os/2019/04/28/os-5.html

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

• CPU burst
  • CPU 사용 시간
  • compute-bounded : CPU 사용 시간이 I/O 대기 시간보다 긴 것
• I/O burst
  • I/O 대기 시간
  • I/O bounded : I/O 대기 시간이 CPU 사용 시간 보다 긴 것
• Burst time은 스케줄링의 중요한 시준 중 하나

스케줄링 단계 (Level)

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

• Long-term scheduling
  • 장기 스케줄링
  • Job scheduling
• Mid-term scheduling
  • 중기 스케줄링
  • Memory allocation
• Short-term scheduling
  • 단기 스케줄링
  • Process scheduling

Long-term Scheduling

• Job scheduling
  • 시스템에 제출 할 (Kernel에 등록 할) 작업(Job) 결정
    • Admission scheduling, High-level scheduling
• 다중 프로그래밍 정도(degree) 조절
  • 시스템 내에 프로세스 수 조절
• I/O-bounded 와 compute-bounded 프로세스들을 잘 섞어서 선택해야 함
  • 시스템에는 cpu와 I/O device가 존재한다.
  • 만약 우리가 computed-bounded만 많이 올려놓는다면 cpu는 열심히 일을 할 것이지만 I/O device는 일을 하지 않는 상태가 된다. 반대로 I/O bounded만 많이 올려놓는다면
    cpu는 일을 하지 않는 상태가 된다. 이것은 굉장히 비효율적이다.
  • cpu와 I/0 device가 모두 일을 하게 만드는 것이 효율적일 것이다.
  • 그래서 둘을 적절하게 섞어서 올려준다.
• 시분할 시스템에서는 모든 작업을 시스템에 등록
  • Long-term scheduling이 상대적으로 덜 중요함

Mid-term Scheduling

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

Short-term Scheduling

• Process scheduling
  • Low-level scheduling
  • 프로세서(processor)를 할당할 프로세스(process)를 결정
    • Processor scheduler, dispatcher
• 가장 빈번하게 발생
  • Interrupt, block (I/O), time-out, Etc.
  • 매우 빨라야 함
    • E.g
      average CPU burst = 100ms
      scheduling decision = 10ms
    • 10 x (100+10) = 9%
      of the CPU is being used simply for scheduling

스케줄링 단계 (Level) 정리

사진 출처 - https://youtu.be/_gNeoGQx-Tc

스케줄링 정책 (Policy)

스케줄링을 수행하는 방법 또는 기준

• 선점 vs 비선점
  • Preemptive scheduling, Non-preemptive scheduling
• 우선순위
  • Priority

Non-Preemptive scheduling

• 할당 받을 자원을 스스로 반납할 때까지 사용 (자원을 뺏을 수 없다)
  • 예) system call, I/O, Etc.
• 장점
  • Context switch overhead가 적음
• 단점
  • 잦은 우선순위 역전, 평균 응답 시간 증가

Preemptive scheduling

• 타의에 의해 자원을 빼앗길 수 있음
  • 예) 할당 시간 종료, 우선순위가 높은 프로세스 등장
• Context switch overhead가 큼
• Time-sharing system, real-time system 등에 적합
  • 응답성이 높아지기 때문

우선순위 (Priority)

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

요약 : Scheduling Concepts

• 멀티프로그래밍 (멀티테스킹)
• 스케줄링 개념
  • 목적
  • 성능 지표 (index)
    • CPU burst VS I/O burst
  • 스케줄링 기준(Criteria)
• 스케줄링 레벨
  • Long-term, Mid-term, Short-term
• 스케줄링 정책
  • Preemptive/non-preemptive
  • Priority

<참고>

• HPC Lab. KOREATECH - [OS] Lecture 5. Process Scheduling (1/4) / 운영체제 강의