프로세스 스케줄링이 필요한 이유?
우리는 보통 여러개의 프로세스가 시스템 내에 존재하는 다중 프로그래밍을 사용한다.
따라서 자원을 할당 할 프로세스를 선택해야하는데 이게 바로 스케줄링!!
자원 관리
시간 분할 관리
- 하나의 자원을 여러 스레드들이 번갈아 가면서 사용 / 예시) 프로세서
- 프로세스 스케줄링 - 프로세서 사용시간을 프로세스들에게 분배
공간 분할 관리
- 하나의 자원을 분할하여 동시에 사용 / 예시) 메모리
스케줄링의 목적
시스템의 성능 향상을 위해 사용한다.
성능
- 응답 시간 : 작업 요청으로부터 응답을 받을때까지의 시간
- 작업 처리량 : 단위 시간 동안 완료된 작업의 수
- 자원 활용도 : 주어진 시간동안 자원이 활용된 시간
...
대기 시간, 응답 시간, 반환 시간
도착에서 실행 시작 전까지 대기시간
도착부터 작업 진행중 처음 응답이 도착할때까지의 시간 응답시간
실제로 프로세스가 실행된 시간 실행시간
처음부터 종료까지의 시간 반환시간
스케줄링 기준
스케줄링 기법이 고려하는 항목들
- 프로세스의 특성
- 시스템 특성
- 프로세스의 긴급성
- 프로세스 우선순위
- 프로세스 총 실행 시간
...
스케줄링 단계
Long-term Scheduling (장기 스케줄링)
큐에 넣을 프로세스를 결정
- 시스템에 제출 할(커널에 등록 할) 작업 결정
다중 프로그래밍 정도 조절
- 메모리에 올라가 있는 프로세스 수 조절
가끔 호출되기 때문에 느려도 괜찮아
시분할 시스템에서는 모든 작업을 시스템에 등록해야하기 때문에 Long-term Scheduling이 불필요
Mid-term Scheduling (중기 스케줄링)
메모리에 적재된 프로세스 수 관리
너무 많은 프로세스에게 메모리를 할당해 시스템의 성능이 저하되는 경우,
메모리에 적재된 프로세스의 수를 동적으로 조절하기 위해 추가된 스케줄러
Short-term Scheduling (단기 스케줄링)
프로세스를 할당할 프로세스를 결정
준비 상태의 프로세스 중에서 어떤 프로세스를 다음번에 실행 상태로 만들것인지 결정한다.
단기 스케줄러는 가장 빈번하게 발생하기 때문에 매우 빨라야한다.
스케줄링 정책 (Policy)
- 선점 / 비선점
- 우선순위
선점(Preemptive) / 비선점(Non-Preemptive) Scheduling
쉽게 말해 선점은 누가 빼앗을 수 있다. 비선점은 뺏을 수 없다.
Preemptive
타의에 의해 자원을 빼앗길 수 있음 예를들어 더 급한 프로세스가 등장하면 빼앗을 수 있다.
장점 : 응답성이 증가 (Time-sharing system, real-time system에 적합)
단점 : Context Switch overhead가 큼
Non-Preemptive
할당받은 자원을 스스로 반납할 때까지 사용
장점 : Context Switch overhead가 적음
단점 : 잦은 우선순위 역전, 평균 응답시간 증가
우선순위(Priority)
정적 우선순위
프로세스 생성시 결정된 우선순위가 유지됨
장점 : 구현이 쉽고, 오버헤드가 적음
단점 : 시스템 환경변화에 대한 대응이 어려움
동적 우선순위
프로세스의 상태변화에 따라 우선순위 변경
장점 : 시스템 환경변화에 대한 유연한 대응 가능
단점 : 구현이 복잡하고 우선순위 재계산 오버헤드가 큼
스케줄링 알고리즘
FCFS, RR, SPN, SRTN, HRRN ...
FCFS (First Come First Service)
쉽게 말해 선착순!!
도착 시간을 기준으로 먼저 레디 큐에 도착한 프로세스를 먼저 처리
Batch system에 적합, interactive system에 부적합
단점은 긴 평균 응답시간
예를 들어 60초 짜리가 먼저오고 2초짜리가 뒤에오면 2초만 쓰면 되는데도 불구하고 계속 기다려야한다.
RR (Round Robin)
쉽게 말해 돌아가면서 쓰자!!
먼저 도착한 프로세스를 먼저 처리하는데 자원 사용 제한 시간(time quantum)이 있음
프로세스는 할당된 시간이 지나면 자원을 반납해야함
장점은 특정 프로세스의 자원 독점을 방지 단점은 Context switch overhead가 크다
대화형, 시분할 시스템에 적합
SPN (Shortest Process Next)
= SJF (Shortest Job First)
Burst time이 가장 작은 프로세스를 먼저 처리
장점 : 평균 대기시간 최소화, 시스템 내 프로세스 최소화, 많은 프로세스들에게 빠른 응답 시간 제공
단점 : 무한 대기 현상 발생 -> 뒤에 온 프로세스의 BT이 더 짧다면.. 먼저와도 엄청 기다려야 할 수도 있음
정확한 실행 시간을 알 수 없음
SRTN (Shortest Remaining Time Next)
SPN의 변형
잔여 실행 시간이 더 적은 프로세스가 등장하면 선점
장점 : SPN의 장점 극대화
단점 : 잔여 실행을 계속 추적해야함 = Overhead
HRN(High Response Ratio Next)
SPN의 변형
프로세스의 대기시간을 고려하여 기회를 제공
Response Ratio = 대기시간 + 서비스(실행)시간 / 서비스(실행)시간
SPN / SRTN / HRN은 효율성은 좋지만 실행 시간 예측 부하라는 단점이 있음
그래서 MLQ / MFQ가 등장!
MLQ (Multi Level Queue)
작업별 별도의 레디 큐를 가짐 (앞에 나온 스케줄링 기법은 레디큐가 하나)
큐 사이에는 우선순위 기반의 스케줄링 사용
빠른 응답시간(?) -> 중요한 프로세스는 빠르지만.. 우선순위가 낮다면 starvation 현상 발생..
MFQ (Multi Level Feedback Queue)
프로세스의 큐간 이동이 허용된 MLQ
피드백을 통해 우선 순위 조정
장점 : BT를 예상하지 않고 앞서 나온 스케줄링 기법(SPN / SRTN / HRN)의 효과를 볼수있음
단점 : 설계, 구현이 복잡하고 스케줄링 오버헤드가 크다. Starvation문제도 여전하다..
