[OS]CH5. 프로세스 스케쥴링

 

본 글은 HPC Lab의 youtube 강의를 듣고 요약한 것입니다. 모든 이미지 출처 역시 HPC Lab의 pdf 수업자료입니다.

 

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

---

스케쥴링이 필요한 이유는 다중프로그래밍 때문이다. 시스템 내에 여러 개의 프로세스가 존재하기에 이들을 효율적으로 스케쥴링 해주어야 하는 것이다. 여기서 자원을 할당할 프로세스를 선택하는 것이 스케줄링이다.

 

스케줄링의 목적

---

주된 목적은 시스템의 성능(performance) 향상 -> 효율성 증대이다.

그럼 대표적인 시스템의 성능 지표는 무엇이 있을까?

• 응답시간(response time) : 작업요청으로부터 응답 받을때까지의 시간(interactive or real-time system에서 중요)
• 처리량(throughput) : 단위 시간 동안 완료된 작업 수(batch system에서 중요)

성능 지표는 다양하기 때문에 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택해야 한다.

 

waiting time, response time, burst time, turn-around time

---

 

스케줄링 기준

---

• 프로세스의 특성 : I/O bounded or compute-bounded
• 시스템 특성 : Batch system or interactive system
• 프로세스 우선순위(priority)
• 프로세스의 긴급성(urgency) : real-time, non-real time

이 외에도 여러가지가 있다.

 

CPU burst vs. I/O burst

---

프로세스의 수행이라하면 CPU사용 + I/O 대기이다.

• CPU burst : CPU 사용 시간 -> CPU burst가 더 길면 compute-bounded process
• I/O burst : I/O 대기 시간 -> I/O burst가 더 길면 I/O-bounded process

burst time은 스케줄링의 중요한 기준 중 하나이다.

 

스케줄링 단계(level)

---

발생하는 빈도에 따라 long-term, mid-term, short-term scheduling으로 나뉜다. long-term scheduling은 말 그대로 긴 시간 동안 한 번씩 일어나는 스케줄링이다. 

• long-term scheduling : job scheduling
• mid-term scheduling : memory allocation
• short-term scheduling : process scheduling

 

Long-term scheduling

---

Long-term scheduling에서 하는 Job scheduling은 시스템(kernel)에 등록할 작업(Job)을 결정한다. 바꿔말하면, 시스템 내의 프로세스 수를 조절해 다중프로그래밍 정도(degree)를 조절하는 것이다. 이 때, 시스템을 효율적으로 사용하기 위해선 I/O-bounded와 compute-bounded 프로세스를 적절히 섞어서 선택해야 한다. 예컨대, I/O-bounded만 넣어주면 I/O device만 일을 하고 CPU는 쉬게 되어 비효율적이다.

 

Mid-term scheduling

---

메모리 할당 결정(memory allocation)

• Swapping(swap-in/swap-out)

 

Short-term scheduling

---

Process scheduling

• 프로세서를 할당할 프로세스 결정(dispatcher, scheduler)

가장 빈번하게 발생

• 매우 빨라야 한다.
• EX) average CPU burst = 100ms, scheduling decision = 10ms 라면 10/(100+10) = 9%가 scheduling에 쓰이는 것이다. 즉, scheduling 시간이 짧을수록 효율적이다.

 

스케줄링의 단계 개괄

---

 

스케줄링 정책(policy)

---

1. 선점(preemption) vs. 비선점(non-preemption)
2. 우선순위(priority)

 

선점(preemption) vs. 비선점(non-preemption)

---

Non-preemptive scheduling

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

Preemptive scheduling

• 타의에 의해 자원을 빼앗길 수 있음
• 예) 자원 할당시간 종료, 우선순위가 높은 프로세스 등장
• 단점 : context switch overhead가 큼
• 높은 응답성을 필요로 하는 time-sharing, real-time system에 적합

 

스케줄링 알고리즘

---

• FCFS(First-Come-First-Served)
• RR(Round-Robin)
• SJF(Shortest-Job-First) = SPN(Shortest-Process-Next)
• SRJF(Shortest-Remaining-Job-First) = SRTN(Shortest-Remaining-Time-Next)
• HRRN(High-Response-Ratio-Next)
• MLQ(Multi-level Queue)
• MFQ(Multi-level Feedback Queue)

 

FCFS

---

• Non-preemptive scheduling
• 스케줄링 기준 : 도착시간(먼저 도착한 프로세스 먼저 처리)
• Batch system에 적합, interactive system에 부적합
• 장점
  • Low scheduling overhead(단순하게 도착한대로 처리하면 되므로)
  • High resource utilization
• 단점
  
  • Convoy effect에 의한 긴 평균 응답시간
  • Convoy effect : 실행시간이 긴 하나의 프로세스에 위해 다른 프로세스들의 대기시간이 길어지는 현상

 

RR(Round-robin)

---

• Preemptive scheduling
• 스케줄링 기준 : 도착시간
• FCFS와 차이점 : 자원 사용 제한 시간(time quantum, δ)이 있음
  • 프로세스는 할당된 시간이 지나면 자원 반납(timer-runout)
• 장점 : time quantum으로 특정 프로세스의 자원 독점(monopoly) 방지
• 단점 : context switch overhead가 큼
• interactive or time-sharing system에 적합
• time quantum이 시스템 성능을 결정하는 핵심요소
  • too large -> FCFS
  • too small -> 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌(체감 프로세서 속도=실제 프로세서 성능의 1/n) + high context switch overhead

 

SJF(Shortest-Job-First) = SPN(Shortest-Process-Next)

---

• Non-preemptive scheduling
• 스케줄링 기준 : 실행시간(burst time)
  • burst time이 가장 작은 프로세스 먼저 처리
• 장점
  • 평균 대기시간 최소화
  • 빠른 응답시간 제공
• 단점
  • starvation 발생(burst time이 긴 프로세스는 계속해서 자원 할당 못받을 수도 있다.->aging으로 해결)

  • 정확한 실행시간을 알 수 없다(실행시간은 끝나고나서야 알 수 있으므로)->예측기법이 필요

 

SRJF(Shortest-Remaining-Job-First) = SRTN(Shortest-Remaining-Time-Next)

---

• SJF의 변형 -> 잔여 실행시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
• Preemptive scheduling
• 스케줄링 기준 : 잔여 실행시간
• 장점 : SJF의 장점 극대화
• 단점
  • 잔여 실행 시간을 계속 추적해야 함(overhead)
  • context switching overhead

 

HRRN(High-Response-Ratio-Next)

---

• SJF의 변형 : SJF + Aging + Non-preemptive
• Aging : 대기시간(WT)을 고려해 기회 제공
• 스케줄링 기준 : response ratio가 높은 프로세스 우선
• Response ration = (WT + BT) / BT (응답률, 필요한 BT대비 얼마나 걸렸는가를 나타냄)
  • SJF의 장점 + Starvation 방지 + 평균 대기시간 최소화
  • 여전히 실행시간 예측 기법 필요

 

Basic scheduling algorithm

---

 

MLQ(Multi-level Queue)

---

• 작업(or 우선순위)별 별도의 ready queue를 가짐(지금껏 1개의 ready queue만 사용했던 것과 다름)
  • 최초 배정된 queue를 벗어나지 못함
  • 각각의 queue는 자신만의 스케줄링 기법 사용
• Queue 사이에는 우선순위 기반 스케줄링 사용
• 장점 : 우선순위가 높은 queue의 경우엔 빠른 응답시간 제공 가능
• 단점
  • 여러 개의 queue 관리 등 스케줄링 overhead
  • 우선순위 낮은 queue는 starvation 발생 가능

 

MFQ(Multi-level Feedback Queue)

---

• Queue간 이동이 허용된 MLQ
• Feedback을 통해 우선순위 조정
• 프로세스에 대한 사전정보 없이 SJF, SRJF, HRRN 기법의 효과를 낼 수 있음
• 단점
  • 스케줄링 overhead가 큼
  • starvation 문제
• 변형
  • 각 ready queue마다 시간 할당량을 다르게 배정
  • I/O 위주 프로세스들 상위 큐로 이동, 우선순위 높임(시스템 전체 평균 응답시간 최소화)
  • 대기 시간이 지정된 시간을 초과한 프로세스들 상위 큐로 이동(aging)