프로세스 스케쥴링
CPU를 사용하고자 하는 프로세스들 사이에서 우선순위를 관리하는 것
스케쥴링의 목적은 다음과 같다.
- 처리율, CPU 이용율을 증가시킨다.
- 오버헤드/응답시간/반환시간/대기시간을 최소화시킨다.
→ CPU를 쉬지 않고 굴리는 것이 목표다.
스케쥴링 방식
선점형 스케쥴링과 비선점형 스케쥴링이 있다.
비선점형
하나의 프로세스가 끝날 때 까지 다른 프로세스는 기다려야 한다.
장점
- 스케쥴러 호출 빈도가 낮아 문맥 교환에 의한 오버헤드도 덜 발생
- 일을 순차적으로 처리하는 배치처리(일괄처리) 시스템에 적합
단점
- 긴 프로세스 하나가 짧은 여러 프로세스들을 대기시킬 수도 있다.
- 그러므로 처리율이 떨어진다.
선점형
하나의 프로세스가 다른 프로세스 대신 CPU(프로세서)를 차지할 수 있다.
장점
- 스케쥴링 방식이나 우선순위 등으로 인해 CPU가 실행하는 프로세스를 바꿀 수 있다.
- 빠른 응답이 요구되는 시분할 시스템에 적합
- 여러 프로세스들을 "적절한 스케쥴링 알고리즘"을 이용한다면 효과적인 처리 가능
단점
- 프로세스의 잦은 전환으로 오버헤드가 발생할 수 있음
- "적절하지 않은 스케쥴링 알고리즘" 선정시 기아현상 발생
비선점형 스케쥴링 알고리즘
기본적으로 비선점형 알고리즘 이기 때문에, 프로세스가 끝날 때 까지 CPU를 점유한다.
FIFO, SJF, HRN 등이 있다.
FIFO - First In First Out
선입 선출 방식.
- 작업이 들어온 순서대로 처리한다.
- 긴 시간을 요구하는 작업이 먼저 들어온다면, 효율성이 떨어진다.
SJF - Shortest Job First
프로세스의 도착 순서와는 관계 없이, CPU 점유 시간이 가장 짧은 프로세스가 먼저 CPU를 점유한다.
- Starvation(기아) 현상이 일어날 수 있다.
- 프로세스의 점유 시간만을 생각하므로, 사용 시간이 긴 프로세스는 무한히 대기할 수도 있다.
Priority
각 프로세스 별 우선순위 부여, 우선순위 순서대로 처리하는 기법
- 우선순위가 모두 같다면 FCFS와 같다.
- 가장 낮은 우선순위의 프로세스 역시 기아현상 발생 가능
HRN - Highest Response-ratio Next
SJF를 보완하기 위한 방법
대기시간 + 서비스시간을 이용하는 방식.
SJF에 "에이징 기법"을 적용시킨 것.
- 우선순위 : (대기시간 + 서비스시간) / 서비스시간 의 공식을 이용해 우선순위 계산.
- 긴 작업과 짧은 작업간 불합리함을 해소시켜준다.
에이징 기법)
에이징 기법이란?)
starvation을 막기 위한 방법.
- 실행되지 않은 프로세스는, 1초가 지날 때 마다 우선순위를 1 증가시킬 수 있다.
이와 같이 작동하면 우선순위가 낮은 프로세스는 우선순위를 높일 수 있다.
얼마나 오랫동안 실행이 되지 않았는지에 따라 계속 우선순위가 증가하므로
언젠가는 실행될 것임을 알 수 있다.
→ 계속 실행되지 못해 기아현상이 발생하는 프로세스보단 낫다.
선점형 스케쥴링 알고리즘
선점형 스케쥴링에 이용되는 알고리즘이다.
SRT, RR, MQ, MFQ 등이 있다.
SRT(Shortest Remaining Time)
SJF 기법을 선점형으로 변경한 기법
CPU 점유 시간이 가장 짧은 프로세스를 CPU에 먼저 할당한다.
- SJF와 유사하나 선점형에서 작동하기 때문에, 작업 도중 다른 더 중요한 작업이 CPU를 차지할 수 있다.
RR(Round Robin)
프로세스에 우선순위를 두지 않고, 순서대로 시간단위로 CPU 할당
- 임의로 할당 시간을 정하는데, 할당 시간이 클수록 FIFO와 유사해 질 수 있음.
- 시간 내 처리하지 못한 프로세스는 queue의 맨 뒤로 보내짐
- 잦은 프로세스 교체로 오버헤드가 크지만, 응답시간이 짧아지는 장점
MQ(Multilevel Queue)
프로세스가 여러 그룹으로 나눠질 때, 여러 큐에 다양한 알고리즘을 적용하는 방식
예를 들면)
Ready Queue를 여러 개 형성할 수 있는데,
우선순위가 높은 프로세스들은 foreground
우선순위가 낮은 프로세스들은 background에 대기시킬 수 있겠다.
- 이렇게 큐에 위치한 프로세스들은, 다른 큐로 이동할 수 없다.
여기서 foreground에서는 선점형 스케쥴링 방식,
background에서는 비선점형 스케쥴링 방식을 쓰는 등 각기 다른 방식을 사용할 수 있다.
- 또한 background에 있는 작업을 수행중일 때, CPU 점유를 foreground에 뺏길 수도 있다.
- 이 경우, background에서 starvation이 일어날 수 있다.
이외에도 Muti Feedback Queue, EDF 등 다른 스케쥴링 알고리즘도 존재한다.
참고한 사이트
https://maxpulse.tistory.com/208