Chapter5 프로세스 스케줄링

Chapter5 프로세스 스케줄링

1. 스케줄링이란?

• 여러 개의 프로세스가 시스템 내 존재하기 때문에 자원을 할당 할 프로세스를 선택하여, 자원을 효율적으로 이용해야 한다.
• → 스케줄링(Scheduling)
• 자원 관리
  • 시간 분할(time sharing) 관리 - 하나의 자원을 여러 스레드들이 번갈아 가며 사용
    • ex) 프로세서
  • 공간 분할(space sharing) 관리 - 하나의 자원을 분할하여 동시에 사용
    • ex) 메모리

 

1.1 스케줄링의 목적

• 시스템 성능 향상
• 성능 지표
  • 응답시간(response time) → 대화형, 실시간 시스템에서 중요
  • 작업 처리량(throughput) → 일괄처리(배치) 시스템에서 중요
  • 자원 활용도(resource utilization) : 자원이 활용된 시간 / 주어진 시간 (최대값 : 1)
    • 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택해야 한다

 

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

2. 스케줄링의 기준 및 단계

2.1 스케줄링의 기준(Criteria)

• 프로세스의 특성 : I/O bounded or Compute-bounded
• 시스템 특성 : Batch system or Interactive system
• 프로세스의 긴급성(urgerncy) : Hard-, Soft- real time, non-real time
• 프로세스의 우선순위(priority)
• 등등

 

2.2 Burst time이란?

• 실행시간을 의미
  • CPU burst : CPU 사용 시간
    • If) CPU burst > I/O burst이면 Compute bounded process
  • I/O burst : I/O 대기 시간
    • If) CPU burst < I/O burst이면 I/O bounded process

 

2.3 단계

• 발생하는 빈도 및 할당 자원에 따른 구분
• Long-term scheduling
  • ex) Job scheduling : 시스템에 제출(커널에 등록) 할 작업(Job) 결정
  • 다중프로그래밍 정도(degree) 조절 → 프로세스 수 조절
    • Compute-bounded와 I/O-bounded 프로세스를 적당히 섞어야 됨
  • 시분할 시스템에서는 덜 중요
• Mid-term scheduling
  • 메모리 할당 결정
• Short-term scheduling
  • ex) Process scheduling
  • 가장 비번하게 발생 하므로 매우 빨라야 함(ready → running)

 

3. 스케줄링 정책(Policy)

• Non-Preemptive(비선점) scheduling
  • 할당 받은 자원을 스스로 반납할 때까지 사용
  • 장점 : Context switch overhead ↓
  • 단점 : 평균 응답 시간 ↑
• Preemptive(선점) scheduling
  • 타의에 의해 자원을 빼앗길 수 있음
  • 장점 : 응답성이 좋다 → time-sharing, real-time system에서 적합
  • 단점 : Context switch overhead ↑
• Static priority(정적 우선 순위)
  • 프로세스 생성 시 결정된 우선순위가 유지 됨
  • 장점 : 구현이 쉽고, overhead가 적음
  • 단점 : 환경 변화에 대한 대응이 어려움
• Dynamic priority(동적 우선 순위)
  • 우선순위가 변경될 수 있음
  • 장점 : 유연한 대응 가능
  • 단점 : 구현이 복잡, overhead가 큼

4. 기본 스케줄링 알고리즘들

4.1 FCFS(First-Come-First-Service)

• 먼저 도착한 프로세스를 먼저 처리
  • 도착 시간 기준(ready queue 기준)
• Non-preemptive scheduling
• 자원을 효율적으로 사용 가능
• Batch-system에 적합
• 단점
  • Convoy Effect : 하나의 긴 수행시간을 가진 프로세스에 의해서 다른 프로세스의 대기시간이 실행시간보다 길어지는 현상
  • 긴 평균 응답 시간

 

4.2 RR(Round-Robin)

• 자원 사용 제한 시간(System parameter(δ))을 두어 처리
  • 프로세스는 할당된 시간이 지나면 자원 반납
  • 도착 시간 기준(ready queue 기준)
• Preemptive scheduling
• 대화형, 시분할 시스템에 적합
• δ → infinite : FCFS
• δ → 0 : processor sharing
  • 체감 프로세서 속도 = 실제 프로세서 성능의 1/n

 

4.3 SPN(Shortest-Process-Next)

• 실행 시간(burst time 기준)이 가장 작은 프로세스를 먼저 처리
• Non-preemptive scheduling
• 장점
  • 평균 대기시간 최소화
  • 시스템 내 프로세스의 수 최소화 → 효율 향상
  • 빠른 응답시간
• 단점
  • Starvation(무한 대기) 발생 → Aging 기법 도입해야 함
  • 정확한 실행시간을 알 수 없으므로 예측 기법 필요 → 자원이 추가로 소모 됨

 

4.4 SRTN(Shortest-Remaining Time Next)

• SPN의 변형 → 잔여 실행 시간이 더 적은 프로세스 먼저 실행
• Preemptive scheduling
• 장점
  • SPN의 장점 극대화
• 단점
  • 총 실행 시간 예측 필요
  • 잔여 실행 시간을 계속 추적해야 함
  • Context switching overhead ↑
• 비현실적

 

4.5 HRRN(Highest-Response-Ratio-Next)

• SPN + Aging concepts
  • 프로세스 대기 시간을 고려하여 기회를 제공
  • Response ratio(응답률)가 높은 프로세스 우선
    $$
    \dfrac{WT+BT}{BT}(응답률, WT : 대기 시간, BT : 실행 시간)
    $$
    • Starvation 방지
    • 실행 시간 예측 기법 칠요
• Non-preemptive scheduling

 

4.6 MLQ(Multi-Level Queue)

• 작업(or 우선순위)별 별도의 ready queue를 가짐
  • 최초 배정 된 queue를 벗어나지를 못함

 

4.7 MFQ(Multi-level Feedback Queue)

• 프로세스의 queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정
  • 현재까지의 프로세서 사용 정보 활용
• 동적 우선순위
• Preemptive scheduling
• 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN의 효과를 봄
• 설계 및 구현이 복잡, overhead가 큼
• starvation 존재

 

• 해결법
  1. 각 준비 큐 마다 시간 할당량을 다르게 배정
  2. 입출력 위주 프로세스들을 상위 단계의 큐로 이동시켜 우선 순위를 높임
  3. 대기 시간이 길어진 프로세스들을 상위 큐로 이동