다중프로그래밍 Multi-programming

• 여러 개의 프로세스가 시스템 내에 존재
• 한정된 자원을 할당 할 프로세스를 선택할 스케줄링 필요

자원 관리

• 시분할 Time Sharing 관리
  - 하나의 자원을 여러 스레드들이 번갈아 가며 사용
  • 예) 프로세서 스케줄링: 프로세서 사용시간을 프로세스들에게 분배
• 공간 분할 Space sharing 관리
  - 하나의 자원을 분할하여 동시에 사용
  • 예) 메모리

스케줄링의 목적

• 시스템의 성능(performance) 향상
• 대표적인 시스템 성능 지표(index)
  - 응답시간 response time: 작업 요청 submission부터 응답 response까지 걸리는 시간
  • 작업 처리량 throughput: 단위 시간 동안 완료된 작업의 수
  • 자원 활용도 resource utilization: 주어진 시간 동안 자원이 활용된 시간
• 목적에 맞는 지표를 고려하여 스케줄링 기법 선택해야 함

스케줄링의 기준

• 프로세스의 특성
  • I/O-bounded: I/O burst가 CPU burst보다 많은 시간이 쓰이는 프로세스
  • Compute-bounded: CPU burst가 I/O burst보다 많은 시간이 쓰이는 프로세스
  • CPU burst와 I/O burst
    • 프로세스 수행 = CPU 사용 + I/O 대기
    • CPU burst: CPU 사용 시간
    • I/O burst: I/O 대기시간
• 시스템 특성
  • Batch system
  • Interactive system
• 프로세스의 긴급성
  • Hard-real time
  • Soft-real time
  • Non-real time

스케줄링의 단계

• 발생하는 빈도 및 할당 자원에 따른 스케줄링의 구분
  

장기 스케줄링 Long-term scheduling

• 발생 빈도 적음
• Job scheduling
  • 시스템에 제출 할(커널에 등록 할) 작업(job) 결정
  • Create => Ready or Suspended ready
• 다중 프로그래밍 정도(degree of multiprogramming) 조절
  • degree of multiprogramming: 시스템 내 프로세스 수
• I/O-bounded와 Compute-bounded 프로세스 수의 균형을 맞춰 시스템에 제출
  • 균형을 맞추지 않으면 CPU와 I/O 어느 한 쪽은 잘 쓰이지 않아 효율 떨어짐
• 시분할 시스템은 모든 작업을 시스템에 등록하므로 job scheduling 불필요함

중기 스케줄링 Mid-term scheduling

• 메모리 할당 결정(memory allocation)
• intermediate-level scheduling
• Swapping(swap-in, swap-out)
  • Suspended => Active
  • Active => Suspended

단기 스케줄링 Short-term scheduling

• Process scheduling
  • Low-level scheduling
  • 프로세서를 할당할 프로세스를 결정
• 가장 빈번하게 발생
  • 인터럽트, 블럭, time-out 등의 상황에서 발생하므로 빈번함
  • 빈번하므로 효율을 위해 매우 빨라야함

스케줄링 정책

선점 Preemptive / 비선점 Non-preemptive

Non-preemptive scheduling

• 할당 받은 자원을 스스로 반납할 때가지 사용
  • 예) System call, I/O 등
• 장점
  • 컨텍스트 스위칭이 자주 발생하지 않아 오버헤드가 적음
• 단점
  • 잦은 우선순위 역전, 평균 응답시간 response time 증가

Preemptive scheduling

• 타의에 의해 자원을 빼앗길 수 있음
  • 예) 할당 시간 종료, 우선순위가 높은 프로세스 등장
• 단점
  • 컨텍스트 스위치 오버헤드가 큼
• Time-sharing, real-time system에 적합

우선순위 Priority

• 프로세스의 중요도

정적 우선순위 Static priority

• 프로세스 생성 시 결정된 priority 유지
• 장점
  • 구현이 쉬움
  • 오버헤드 적음
• 시스템 환경 변화 대응이 어려움

동적 우선순위 Dynamic priority

• 프로세스의 상태 변화에 따라 priority 변경
• 장점
  • 시스템 환경 변화에 유연한 대응 가능
• 단점
  • 구현이 복잡함
  • priority 재계산 overhead가 큼

한기대 김덕수 교수님 강의