[운영체제- 김덕수 교수님] 프로세스 스케줄링 (1/4)

다중 프로그래밍 환경

• 여러개의 프로세스가 시스탬 내 존재
• 자원을 할당 할 프로세스를 선택해야 함
  • 스케쥴링(Scheduling)
• 자원 관리
  • 시간 분할 관리(time sharing)
    • 하나의 자원을 여러 스레드들이 번갈아 가며 사용
    • 예) 프로세서
  • 공간 분할 관리(space sharing)
    • 예) 메모리

‏‏‎ ‎

스케쥴링의 목적

• 시스템의 성능 향상(모호한 표현)
• 대표적 시스템 성능 지표(index)
  • 응답 시간(response time)
    • 작업 요청으로부터 응답을 받을 때까지의 시간
    • 대화형 시스템, 실시간 시스템
  • 작업 처리량(throughput)
    • 단위 시간 동안 완료된 작업의 수
    • batch 시스템
  • 자원 활용도(resource utilization)
    • 주어진 시간(Tc) 동안 자원이 활용된 시간(Tr)
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

‏‏‎ ‎

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

• 대기시간(Waiting time)
  • 프로세서가 작업을 시작하기 전 까지의 시간
• 응답시간(Response time)
  • 프로세스가 할당되고 프로세서가 작업을 해서 첫번째 출력이 이뤄질 때 까지의 시간
• 실행시간(Burst time)
  • 작업의 실행 시작부터 실행 종료시까지를 이루는 말로 실제 작업이 실행된 시간
• 반환시간(Turn-around time)
  • 프로세서가 할당되고 모든 작업을 끝마치고 다시 반환이 될 때까지 걸린 시간

‏‏‎ ‎

‏‏‎ ‎

스케줄링 기준(criteria)

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

‏‏‎ ‎

CPU burst vs I/O burst

• 프로세스 수행
  • = CPU 사용 + I/O 대기
• CPU burst(compute-bounded)
  • CPU 사용 시간
• I/O burst(I/O bounded)
  • I/O 대기 시간
• Burst time은 스케줄링의 중요한 기준 중 하나

‏‏‎ ‎

스케줄링의 단계(level)

‏‏‎ ‎

‏‏‎ ‎

Long-term 스케줄링

• Job schduling
  • 시스템에 제출할 (Kernel에 등록할) 작업(Job) 결정
• 다중 프로그래밍 정도(degree) 조절
  • 시스템 내에 프로세스 수 조절
• I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야함
  • 잘 섞어서
  • I/O 작업만 하면 cpu는 놀게 되고
  • compute 작업만 하면 반응성이 떨어지게 된다.
• 시분할 시스템에서는 모든 작업을 시스템에 등록
  • Long-term 스케줄링 덜 중요

‏‏‎ ‎

‏‏‎ ‎

Mid-term 스케줄링

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

‏‏‎ ‎

Short-term scheduling

• Process scheduling
  • low-level scheduling
  • 프로세서(processer)를 할당할 프로세스(process) 결정
• 가장 빈번하게 발생
  • interrupt, block(I/O), time-out Etc.
  • 매우 빨라야 함

‏‏‎ ‎

스케줄링의 단계

‏‏‎ ‎

스케줄링 정책(policy)

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

‏‏‎ ‎

Preemptive/Non-preemptive scheduling

• 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(동적 우선순위)
  • 프로세스의 상태 변화에 따라 우선순위 변경
  • [장]시스템 환경 변화에 유연한 대응 가능

‏‏‎ ‎

• [단]구현이 복잡, 우선순위 재계산 overhead 가 큼

‏‏‎ ‎

‏‏‎ ‎

요약

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

‏‏‎ ‎