[SW_Jungle] OS 프로세스 스케줄링

우리가 사용하는 시스템은 다중프로그래밍 환경으로 여러개의 프로세스가 시스템 내 존재한다.
때문에 자원을 할당할 프로세스를 선택해야 하는데, 이 과정을 스케줄링이라고 한다.

자원 관리

시간 분할 관리

• 하나의 자원을 여러개의 스레드들이 번갈아 가며 사용 ex> 프로세서
• 프로세스 스케줄링 : 프로세서 사용시간을 프로세스들에게 분배

공간 분할 관리

• 하나의 자원을 분할하여 동시에 사용 ex> 메모리

스케줄링의 목적 : 시스템의 성능 향상
'성능' 이라는 단어는 모호한 부분이 있다. 이를 3가지로 나눠 보자

대표적 시스템 성능 지표

• 응답시간 : 작업요청으로 부터 응답을 받을 때 까지의 시간
• 작업 처리량 : 단위 시간 완료된 작업의 수
• 자원 활용도 : 주어진 시간 동안 자원이 활용된 시간

이 세가지중 무엇이 가장 중요할까? 이는 목적마다 달라진다. 사용자 대화형 시스템에서는 응답시간이, 일괄처리 시스템에게는 작업처리량이, 비싼 자원을 사용하는 경우 자원활용도가 중요 지표가 될 것

대기시간, 응답시간, 반환시간의 관계

스케줄링 기준(criteria) : 스케줄링 기법이 고려하는 항목

• 프로세스의 특성
• 시스템 특성
• 프로세스의 긴습성
• 프로세스 우선순위
• 프로세스 총 실행 시간

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

1. long-term scheduling : 장기 스케줄링, 빈도수 가끔
   • job scheduling : 시스템에 제출 할(커널에 등록할) 작업 결정
   • 다중 프로그래밍 정도 조절 : 시스템 내에 프로세스 수 조절
2. mid-term scheduling : 중기 스케줄링, 빈도수 종종
   • 메모리 할당 결정(memory allocation)
3. short-term scheduling : 가장 빈번하게 발생, 매우 빨라야 하며 이것을 프로세스 스케줄링이라고함
   • 프로세서를 할당할 프로세스를 결정

스케줄링 정책(policy)

1. 선점 vs 비선점
   • 비선점 : 할당 받은 자원을 스스로 반납할 때까지 사용, context switch overhead가 적은 장점이 있으나 잦은 우선순위 역전, 평균응답시간 증가의 단점을 가진다.
   • 선점 : 타의에 의해 자원 빼앗길 수 있음, 할당시간 종료나 우선 순위가 높은 프로세스의 등장시 context switch overhead가 큰 단점이 있으나 시분할 시스템이나 리얼타임 시스템에 적합한 장점이 있다.
2. 우선순위
   • 정적 우선순위 : 프로세스 생성시 결정된 우선순위 유지, 구현이 쉽고 오버헤드가 적음, 시스템 환경 변화에 대한 대응이 어렵다.
   • 동적 우선순위 : 프로세스의 상태 변화에 따라 우선순위가 변경되며, 구현이 복잡하고 우선순위를 재계산 해야 하기 때문에 오버헤드가 크다, 시스템 환경변화에 유연한 대처가 가능하다.

스케줄링 알고리즘

1. FCFS(First-Come-First_Service) : 쉽게 말해 선착순

   • 비선점 스케줄링
   • ready queue 도착시간을 기준으로 먼저 도착한 프로세스를 먼저 처리
   • 자원을 효율적으로 사용 가능(스케줄링 오버헤드가 낮다, CPU가 계속 일할 수 있다)
   • batch system(일괄 처리 시스템)에 적합, interactive system(대화형 시스템)에 부적합
   • 평균 응답시간이 길며 예측이 불가능
   • convey effect : 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상(대기시간 >> 실행시간)

2. RR(Round-Robin)

   • 선점 스케줄링
   • ready queue 도착시간을 기준으로 먼저 도착한 프로세스를 먼저 처리
   • 자원 사용에 제한시간(time quantum)이 있음
     - 자원 사용 제한시간이 시스템 성능을 결정하는 핵심 요소
   • 프로세스는 할당된 시간이 지나면 자원을 반납하여 특정 프로세스의 자원 독점 방지
   • context switch overhead가 큼
   • 대화형, 시분할 시스템에 적합

3. SPN(Shortest-Process-Next)

   • 비선점 스케줄링
   • 실행시간(burst time)을 스케줄링 기준으로 사용하여 burst time 이 가장 작은 순서대로 처리
   • 평균 대기시간 최소화
   • 시스템 내 프로세스 수 최소화 : 스케줄링 부하 , 메모리 절약 -> 시스템 효율 향상
   • 많은 프로세스들에게 빠른 응답시간 제공
   • 무한대기(starvation) 현상 발생 : 실행 시간이 긴 프로세스는 자원을 할당 받을 수 없을 수도있음
   • 정확한 실행시간을 알 수 없음, 예측할 수 없는 것을 기준으로 스케줄링을 해야 한다는 단점

4. SRPN(Shortest-Remaining-Process-Next)

   • 선점 스케줄링
   • SPN의 변형으로 SPN의 장점을 극대화 함
   • 잔여 실행 시간이 더 적은 프로세스가 등장(ready 상태)하면 선점됨
   • 프로세스 생성시, 총 실행 시간 예측이 필요하고 잔여실행 시간을 계속 추적해야 하는데 이는 시스템에 오버해드로 작용
   • 구현 및 사용이 비현실적

5. HRRN(High-Response-Ratio-Next)

   • SPN의 변형으로 aging concepts 사용 -> 프로세스의 대기시간을 고려하여 기회를 제공한다.
   • response ration가 높은 프로세스가 스케줄링 기준
   • response ration = (대기시간 + 실행시간) / 실행시간
   • SPN의 장점 + starvation 방지

6. MLQ(Multi-Level Queue)

   • 작업 or 우선순위 별 별도의 ready queue를 가짐
     - 최초 배정된 queue를 벗어나지 못하고 각각의 queue는 자신만의 스케줄링 기법 사용
   • queue 사이에는 우선순위 기반의 스케줄링 사용
   • 우선순위가 높은 작업은 빠른 응답시간을 가지나 우선순위가 낮은 queue는 starvation 현상 발생 가능
   • 여러개의 queue관리 등 스케줄링 오버헤드

7. MFQ(Multi-Level Feedback Queue)

   • 프로세스의 queue간 이동 허용된 MLQ
   • 현재까지 프로세서 사용 패턴을 활용하여 feedback을 통해 우선순위 조정
   • 동적 우선순위
   • 선점 스케줄링
   • 프로세스에 대한 실행시간 정보없이 SPN, SRTN, HRRN 기법 효과를 볼 수 있음
   • 구현이 복잡

ref)
1. https://www.youtube.com/watch?v=_gNeoGQx-Tc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=8