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

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

• 여러 개의 프로세스가 시스템 내 존재

• 자원을 할당 할 프로세스를 선택 해야 함
  - 스케줄링(Scheduling)

• 자원 관리

  	시간 분할 관리(time sharing)	공간 분할 관리(space sharing)
  개념	하나의 자원을 여러 스레드들이 번갈아 가며 사용	하나의 자원을 분할하여 동시에 사용
  예시	프로세서 (Processor)	메모리 (Memory)
  	프로세스 스케줄링1

---

- 스케줄링의 목적

1. 시스템의 성능(Performance) 향상
2. 대표적 시스템 성능 지표(index)
   • 응답시간 (Response time)
     - 작업 요청(Submission)으로부터 응답을 받을때까지의 시간
   • 작업 처리량 (Throughput)
     - 단위 시간 동안 완료된 작업의 수
   • 자원 활용도 (Resource Utilization)
     - 주어진 시간(Tc)동안 자원이 활용된 시간(Tr) -> (Tr / Tc)
3. 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

- 기타 시스템 성능 지표들

• 공평성 (Fairness)
• 실행 대기 방지
• 예측 가능성 (Predictability)
• 우선 순위
• 서비스 사용 기회 확대
• 서비스 수 감소 방지
• 오버헤드 최소화
• ...

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

• 대기시간 : 대기열에 들어와 CPU를 할당받기까지 기다린 시간
• 응답시간 : 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
• 반환시간 : 프로세스가 CPU요청을 한 시점부터 작업을 모두 마친 후까지 걸리는 시간

---

- 스케줄링 기준 및 단계

1. 스케줄링 기준 (Criteria) : 스케줄링 기법이 고려하는 항목들

- 프로세스의 특성
	- I/O-bounded or compute-bounded
- 시스템 특성
	-- Batch system or interactive system
    
- 프로세스의 긴급성 (Urgency)
	- Hard- or soft- real time, non-real time systems
- 프로세스 우선순위 (Prioirty)
- 프로세스 총 실행 시간 (Total Service Time)

- CPU burst vs I/O burst

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

2. 스케줄링의 단계 (Level) : 발생하는 빈도 및 할당 자원에 따른 구분

• 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 scheduler, dispatcher)
    
    

• 스케줄링의 단계
  

---

- 스케줄링 정책 (Policy)

• 선점 vs. 비선점
• 우선순위 (Priority)

1. Preemptive scheduling (선점)
   • 타의에 의해 자원을 빼앗길 수 있음
     - 예) 할당 시간 종료, 우선 순위가 높은 프로세스 등장
   • Context switch overhead가 큼
   • Time-sharing system, real-time system 등에 적합

2. Non-preemptive scheduling

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

3. Priority : 프로세스의 중요도

   3.1. Static priority (정적 우선순위)

   • 프로세스 생성시 결정된 priority가 유지 됨
   • 구현이 쉽고 overhead가 적음
   • 시스템 환경 변화에 대한 대응이 어려움
     

   3.2. Dynamic priorty (동적 우선순위)

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

---

1. 프로세스 스케줄링(Process Scheduling) : CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 일