프로세스 스케줄링
자원의 관리
프로세스 스케줄링은 여러개의 프로세스가 하나의 시스템안에 존재하는 다중프로그래밍에서 필요한 것입니다. 자원을 어떤 프로세스에게 할당해줄지 선택해주는 과정이라고 보면됩니다. 자원은 크게 두가지 방법으로 분할할 수 있습니다.
첫 번째는 시간분할 관리방법입니다. 하나의 자원을 번갈아 가며 사용하는 것인데요. CPU는 이런식으로 관리됩니다. 두 번째는 공간분할 관리방법입니다. 이는 하나의 자원을 분할하여 동시에 사용하게 됩니다. 메모리는 이런식으로 관리가 되는 자원입니다.
스케줄링의 목적
이러한 스케줄링은 결국 시스템의 성능을 향상하기 위한 목적을 가지고있습니다. 그리고 이 시스템 향상을 판단할 지표는 응답시간, 작업처리량, 자원활용도등 다양합니다. 따라서 각 지표에 맞게 목적을 달성할 수 있는 스케줄링이 필요합니다.
용어
아래는 프로세스가 작업을 수행하고 끝내는 과정동안 특정 구간을 칭하는 용어들입니다.
이는 나중에 각 스케줄링의 성능을 계산할 때 쓰이기도 하기때문에 명확히 알아두는 것이 좋습니다.
스케줄링의 종류
1. 장기스케줄링(Long Term)
스케줄링중 가장 낮은 빈도로 수행되는 장기스케줄링에는 어떤 프로그램을 시스템에 등록할지 결정하는 스케줄링입니다. 프로세스의 생명주기로 보면 created에 해당합니다. 이는 시스템안에 프로세스의 수를 조절하기 위한 목적을 가지고 있습니다. 이때는 I/O bounded와 CPU bounded 프로세스를 잘 섞어서 선택하는 등 여러가지의 고려사항들이 있습니다.
하지만 시분할 시스템, 즉 CPU를 번갈아가며 사용하는 시스템에서는 모든 작업을 시스템에 등록해도 되기 때문에 장기스케줄링이 불필요해집니다.
2. 중기스케줄링(Mid Term)
중기스케줄링은 메모리의 할당을 결정하는 스케줄링입니다. 프로세스의 생명주기에서는 swapping과정이 이에 해당합니다.
3. 단기스케줄링(Short Term)
가장 빈번하게 일어나는 스케줄링으로 프로세서를 할당할 프로세스를 결정하는 것입니다. 프로세스의 생명주기로 보자면 dispatch에 해당합니다. 자주일어나는 만큼 빨라야합니다.
스케줄링의 정책
1. 선점 vs 비선점
스케줄링의 정책중 선점과 비선점은 Preemptive, Non-preemptive라고 불리며 중간에 자원을 뺏길 수 있는지에 따라 나뉩니다. 선점은 중간에 쓰고있던 자원을 우선순위나, 할당시간이 종료됐다는 이유로 빼앗길 수 있습니다. 하지만 비선점은 한번 자원을 할당받으면 스스로 반납할 때 까지 계속해서 사용합니다.
2. 우선순위
우선순위는 프로세스의 중요도를 의미합니다. 스케줄링에 영향을 미치며 프로세스 생성시에 결정되어 유지되는 정적 우선순위와 프로세스의 상태 변화에 따라 계속해서 변하는 동적 우선순위가 있습니다.
스케줄링 알고리즘
1. FCFS(First Come First Service)
- 비선점
도착시간기준으로 먼저 처리- Batch System에 적합
Convoy Effect: 중간에 실행시간이 긴 프로세스가 있다면 뒤에 다른 프로세스가 긴 대기시간을 갖게되는 문제
2. RR(Round Robin)
- 선점
도착시간기준으로 먼저 처리- 사용제한시간(Quantum)을 둬서 할당 시간 이상 자원을 쓰지 못하게 함 -> 적절한 Quantum길이가 중요함
- 자원 독점을 방지
- Context Switch Overhead가 큼
- 대화형 시스템에 적합
3. SPN(Shortest Process Next)
- 비선점
실행시간이 짧은 프로세스부터 처리- 평균 대기시간 최소화
- 빠른응답가능
Starvation발생- 실행시간을
예측해야함
4. SRTN(Shortest Remaning Time Next)
- 선점
- SPN의 변형
잔여시간이 더 적은 프로세스 순으로 처리- 총 실행시간에 대한
예측필요 - 잔여시간을 계속해서
추적 - 비현실적
5. HRRN(High Response Ratio Next)
- 비선점
- SPN +
Aging - 프로세스의
대기시간을 고려한 기회 제공 response ratio가 높은 프로세스 순으로 처리Starvation 방지- 실행시간
예측필요
여기까지의 알고리즘은 Basic 스케줄링 알고리즘입니다. 특히 3-5번 알고리즘은 실행시간을 예측해야하는 문제점이 있었습니다. 이런 문제점을 해결하기 위한 알고리즘을 소개하겠습니다.
6. MLQ(Multi Level Queue)
- 별도의
ready queue를 가지고 여기에 프로세스를 배정 - 최초의 배정된 queue를
벗어날 수 없음 - queue들 간에는
우선순위기반 스케줄링 사용 - 여러개의 queue를 관리해야하는 overhead
- 우선순위가 낮은 queue는
Starvation발생
7. MFQ(Multi Level Feedback Queue)
- 프로세스가 queue간
이동이 허용-> I/O bounded, Aging등을 기준으로 - queue간에 우선순위가 조정
- 설계가
복잡
