프로세스 스케쥴링(Process Scheduling) - (1 / 4)

 

아래 글은 CS(컴퓨터 과학) 관련 개념 정리 및 작성자 공부를 위해 작성되었습니다.

 

 

📃 참고자료

• https://youtu.be/_gNeoGQx-Tc

 

 

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

 

• 여러개의 프로세스가 시스템 내 존재
• 자원을 할당 할 프로세스를 선택 해야 함
  - 스케쥴링 (Scheduling)
  
  

* 자원 관리

• 시간 분할 (time sharing) 관리
  - 하나의 자원을 여러 스레드들이 번갈아 가며 사용
  - 예) 프레세서 (Processor)
  - 프로세스 스케쥴링 (Process scheduling) -> 프로세서 사용 시간을 프로세스들에게 분배
• 공간 분할 (space sharing) 관리
  - 하나의 자원을 분할하여 동시에 사용
  - 예) 메모리 (memory)

 

 

-  스케줄링 (Scheduling)의 목적

• 시스템의 성능(performance) 향상

 

대표적 시스템 성능 지표 (index)

• 응답시간 (response time)
  - 작업 요청 (submission)으로부터 응답을 받을때까지의 시간
• 작업 처리량 (throughput)
  - 단위 시간 동안 완료된 작업의 수
• 자원 활용도 (resource utilization)
  - 주어진 시간 동안 자원이 활용된 시간

 

* 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

 

 

 

-  시스템 성능 지표들

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

 

 

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

 

 

 

 

- 스케줄링 기준 (Criteria)

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

 

 

- 스케줄링 기준 (Criteria)

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

 

 

- 스케줄링의 단계 (Level)

• 발생하는 빈도 및 할당 자원에 따른 구분
  
  
• Logn-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 프로세스들을 잘 섞어서 선택해야 함
  - Why?
• 시분할 시스템에서 모든 작업을 시스템에 등록
  - Logn 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 curst = 100ms
    scheduling decision = 10ms
  - 10 x (100+10) = 9%
     of the CPU is being used simply for scheduling

 

 

 

# 스케줄링의 단계 (Level)

 

 

 

# 스케줄링 정책 (Policy)

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

 

- Preemptive / Non-preemptive scheduling

1. Non-preemptive scheduling

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

 

2. Non-preemptive scheduling

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

 

- Priority (우선순위, 프로세스의 중요도)

1. Static Priority (정적 우선순위)

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

 

2. Dynamic priority (동적 우선순위)

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