프로세스 스케줄링 #1 - 목적, 기준, 단계, 정책

목차

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

 

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

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

 

스케줄링(Scheduling)의 목적

• 시스템의 성능(performance) 향상
• 대표적 시스템 성능 지표 (index)
  • 응답시간 (response time)
    -> 작업 요청(submission)으로부터 응답을 받을때까지의 시간
  • 작업 처리량 (throughput)
    -> 단위 시간 동안 완료된 작업의 수
  • 자원 활용도 (resource utilization)
    -> 주어진 시간(Tc) 동안 자원이 활용된 시간(Tr) : Utilization = Tr / Tc
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택
  • Interective system(대화형 시스템) , Real-time system : 응답시간이 중요
  • Batch system : 작업 처리량이 중요
  • 비싼 장비나 프로그램 등 을 사용한다면 자원 활용도가 중요

 

시스템 성능 지표들

• 평균 응답 시간 (mean response time)
  • 사용자 지향적, 예) interactive systems
• 처리량 (throughput)
  • 시스템 지향적, 예) batch systems
• 자원 활용도 (resource utilization)
• 공평성(fairness), 예) FIFO
• 실행 대기 방지
  • 무기한 대기 방지
• 예측 가능성(predictability)
  • 적절한 시간안에 응답을 보장하는가
• 자원 할당의 공정성 보장
• 단위시간당 처리량 최대화
• 적절한 반환시간 보장
• 예측 가능성 보장
• 오버헤드 최소화
• 자원 사용의 균형 유지
• 반환시간과 자원의 활용 간에 균형 유지
• 실행 대기 방지
• 우선순위
• 서비스 사용 기회 확대
• 서비스 수 감소 방지

 

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

반환시간, 대기시간, 응답시간의 관계

• 대기시간 : 프로세스가 실행 까지 걸리는 시간
• 응답시간 : 요청한 프로세스가 실행되어 응답을 받을 때 까지 걸리는 시간
• 실행시간 : 프로세스 실행 부터 종료까지 걸린 시간
• 반환시간 : 대기시간 + 실행시간

 

스케줄링 기준 (Criteria)

• 스케줄링 기법이 고려하는 항목들
• 프로세스(process)의 특성
  • I/O-bounded process : I/O burst > CPU burst
  • Compute-bounded process : CPU burst > I/O burst
• 시스템 특성
  • Batch system or interactive system
• 프로세스의 긴급성(urgency)
  • Hard- or soft- real time, non-real time systems
• 프로세스 우선순위 (priority)
• 프로세스 총 실행 시간 (total service time)

 

CPU burst vs I/O burst

• 프로세스 수행 = CPU 사용 + I/O 대기
• CPU burst : CPU 사용 시간
• I/O burst : I/O 대기 시간
• 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 프로세스들을 잘 섞어서 선택해야 함
• 시분할 시스템에서는 모든 작업을 시스템에 등록
  • 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.
  • 매우 빨라야 함
    • average CPU burst = 100ms
      scheduling decision = 10ms
    • 10 x (100+10) = 9%
      of the CPU is being used simply for scheduling

 

스케줄링 정책 (Policy)

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

Preemptive/Non-preemptive scheduling

• Non-preemptive scheduling
  • 할당 받을 자원을 스스로 반납할 때까지 사용(뺏을 수X)
    • 예) 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가 큼
  • 시스템 환경 변화에 유연한 대응 가능

 

 

 

강의

www.youtube.com/watch?v=_gNeoGQx-Tc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=8