- 스케줄링
> 프로세스들이 작업을 수행하기 위해서는 프로세스 스케줄러들로 부터 CPU를 할당 받아야 한다. 이런 작업은 OS에 의해 구현되고 CPU를 언제, 어떤 프로세스에게 할당 되는지 결정하는 작업을 프로세스 스케줄링이라 한다.
- 스케줄링의 목적
> 공정한 스케줄링
> 처리량 극대화
> 응답시간 최소화
> 반환 시간 예측 가능
> 균형 있는 자원 사용
> 응답시간과 자원 이용간의 조화
> 우선 순위제를 실시
> 페이지 부재를 적게 발생시키는 프로세스에게 더 좋은 서비스를 해줌
- 선점 스케줄링
> 어떤 프로세스가 CPU를 점유하고 있을 때, 다른 프로세스가 현재 프로세스를 중지하고 자신이 CPU를 점유할 수 있는 방식
> 우선 순위가 높은 프로세스가 먼저 수행 될 때 유리하고, 빠른 응답시간을 요구하는 시분할 시스템에 유용
> 선점 때문에 오버헤드 발생
Round Robin 스케줄링 (Time Slice)
- FCFS(First Come First Service) 방식으로 각 프로세스는 같은 크기의 타임 슬라이스를 할당 받는다
- 프로세스가 할당 받은 시간동안 작업을 완료하지 못하면 다음 프로세스로 넘어가고 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내진다.
- 시분할 방식의 시스템에서 효과적이다.
- 할당 시간의 크기는 시스템의 효과적인 동작에 절대적인 영향을 미친다.
- 할당 시간이 크면 FCFS 방식과 같다.
- 할당 시간이 작으면 자주 컨텍스트 스위칭이 일어나므로 오버헤드가 커진다.
SRT(Shortest remaining time) 스케줄링
- 준비 큐에 있는 프로세스들 중에서 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행 시킨다.
- SJF 방식에 선점 방식을 도입한 방식이라고 생각하면 편함.
- 현재 프로세스가 CPU를 할당 받아 사용중이더라도 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 실행 중인 프로세스는 선점될 수 있다.
- 수행 중인 각각의 작업들의 실행 시간을 추적 보유하고 있어야 한다.
MLQ(Multi level queue) 스케줄링
- 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 스케줄링 기법.
- 그룹화된 작업들은 각각의 준비 큐에 넣어서 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당 받음.
- 다단계 큐 알고리즘은 준비 상태 큐를 여러 종류로 분할해 둔다.
- 각 큐는 자신만의 독자적인 스케줄링을 가지고 있다.
- 각각의 서로 다른 작업들이 다른 묶음으로 분류될 수 있을 때 사용되는 알고리즘.
- 일괄 처리 작업이 실행 중 일지라도 상위 단계 큐에 작업이 들어오면 일괄 처리 작업은 선점 당한다.
- 한 큐에서 다른 큐로 의 작업 이동은 불가능
MFQ(Multi level feedback queue) 스케줄링
- 새로운 프로세스가 들어오면 높은 우선순위를 할당해 주어 단계 1에서 즉시 수행해 주고 점차 낮은 우선순위를 부여하며 단계 n쯤 되는 나중에는 그 작업이 완료될 때까지 라운드 로빈으로 순환된다.
- 하나의 준비 큐를 통해 여러 피드백 큐를 걸치며 작업을 수행하는 방법
- CPU에 대한 요구량에 따라 프로세스들을 분류할 때 이상적임
- 짧은 작업에 유리
- 입출력 장치를 효과적으로 이용하려고 입출력 위주의 작업들에 우선권을 줌
- 가능한 빨리 작업의 특성을 알고 그것에 맞게 해당 작업을 스케줄링
- 프로세스가 보다 하위 단계의 큐로 옮겨갈수록 주어진 할당 시간은 점차 크게 설정
- 비선점 스케줄링
> 어떤 프로세스가 CPU를 점유하고 있을 때, 다른 프로세스는 할당 받은 프로세스가 작업 종료할 때까지 CPU를 점유를 할 수 없는 방식
> 모든 프로세스 요구를 공정하게 처리 가능
> 응답 시간 예측 가능
> 짧은 작업이 긴 작업을 기다리는 경우가 발생할 수 있음
우선순위 스케줄링
- 각 프로세스에게 우선 순위를 부여하여 순위가 높은 순서대로 처리하는 방법
- 우선 순위는 보통 프로세스의 특성과 종류에 따라 각각 다르게 부여될 수 있음
- 우선 순위 스케줄링은 정적 우선 방법과 동적 우선 방법이 있음.
- 정적 우선순위 방법 : 실행이 쉽고 상대적으로 오버 헤드는 적지만 주위 여건의 변화에 적응하지 못하고 우선순위를 바꾸지 않음
- 동적 우선순위 방법 : 항상 변화에 잘 적응. 구현하기가 복잡하고 오버헤드가 많으나 시스템 응답도를 증가시켜 주므로 효율성이 있음.
기한부 스케줄링
- 작업들이 명시된 시간이나 기한 내에 완료되게 계획을 짠다.
- 작업들의 결과가 시간내에 구해지면 유용하고 마감 시간이 지난 후에 결과가 구해지면 쓸모 없어짐
- 사용자는 사전에 작업이 요구하는 정확한 자원을 제시해야만 함. 만약 기한 시간 내에 일을 끝내지 못하면 막대한 손해를 초래
- 시스템은 다른 사용자들에 대한 서비스를 감소시키지 않으면서 기한부 작업을 실행 할 수 있어야 함.
- 시스템은 기한까지 일을 끝내기 위해서 자원 안배를 주의 깊게 계획해야 함.
- 만약 많은 기한부 작업들이 동시에 실해오딘다면 스케줄링이 너무 복잡하게 됨
- 기한부 스케줄링으로 요구되는 집중적인 자원 운영은 많은 오버헤드가 뒤따름
FCFO(FIFO) 스케줄링
- 가장 단순한 방식으로 프로세스들이 대기 큐에 도착한 순서에 따라 CPU를 할당 받는 방식
- 일단 프로세스가 CPU를 차지하면 완료될 때까지 수행.
- 다른 방식에 비하여 작업 완료 시간을 예측하기 쉬움.
- 선점이 불가능하기 때문에 수행 시간이 긴 프로세스가 할당 받은 상태라면 수행시간이 짧은 프로그램이 대기할 경우가 생기고 중요한 작업이 대기하는 상황이 있을 수 있음.
- 대화식 사용자들에게는 부적합
SJF(Shortestjob first) 스케줄링
- 준비큐에서 기다리는 작업중 수행시간이 가장 짧다고 판단되는 것을 가장 먼저 수행하는 스케줄링 방법
- FCFS보다 평균 대기 시간을 감소시키지만 큰 작업일수록 FCFS에 비해 예측이 어렵다.
- 긴 작업보다 짧은 작업일 수록 오버헤드 면에서 볼 때 유리하다.
- 수행할 작업이 얼마나 긴 것인지를 정확이 판단 해서 수행해야 하는 데 수행시간을 정확히 얻는다는 것이 어렵다.
HRN(Hightest response ratio next) 스케줄링
- SJF의 약점, 긴 작업과 짧은 작업 간의 불평등을 어느 정도 보완한 방법
- 비선점 스케줄링 방식이므로 한 작업이 CPU를 차지하면 그 작업은 완성될 때까지 실행
- 우선 순위는 '(대기 시간 + 버스트 시간) / 버스트 시간' 으로 정함
< 정리 >
- 선점 알고리즘 : CPU 점유를 뺏어서 다른 프로세스에게 줄 수 있다.
- 비선점 알고리즘 : CPU가 처리 중 인 프로세스를 기다려야 한다.
선점 알고리즘 |
방법 |
특징 |
Round Robin |
FCFS 방식의 변형으로 일정한 시간(Time Slice)을 부여 |
- 시분할 방식에 효과적 - 할당 시간이 크면 FCFS와 동일 - 할당 시간이 작으면 컨텍스트 스위칭이 자주 발생 |
SRT |
작업 도중 나머지 작업 시간이 적은 작업을 우선적으로 처리하는 방법 |
- 처리는 SJF와 같으나 이론적으로 가장 작은 대기 시간이 걸림 |
MLQ |
서로 다른 작업을 각각의 큐에서 타음 슬라이스로 처리 |
- 각각의 큐는 독자적인 스케줄링 알고리즘을 사용 |
MFQ |
하나의 준비 상태 큐를 통해서 여러 개의 피드백 큐를 걸쳐 일을 처리 |
- CPU와 I/O 장치의 효율을 높일 수 있음 |
비선점 알고리즘 |
방법 |
특징 |
우선순위 |
우선순위를 할당해 우선순위가 높은 순서대로 처리하는 방법 |
- 정적 우선 순위 - 동적 우선 순위 |
기한부 |
프로세스가 주어진 시간 내에 작업이 끝나게 계획하는 방법 |
- 마감 시간을 계산해야 하므로 막대한 오버헤드와 복잡성이 발생 |
FCFS |
작업이 시스템에 들어온 순서대로 수행하는 방법 |
- 대화형에 부적합 - 간단하고 공평함 - 반응 속도를 예측 가능 |
SJF |
수행 시간이 적은 작업을 우선적으로 처리하는 방법 |
- 작은 작업에 유리 - 큰 작업은 시간이 많이 걸림 |
HRN |
SJT의 큰 작업 시간이 많이 걸리는 점을 보완한 방법 |
- 우선순위 = (대기시간 + 서비스 시간) / 서비스 시간 |
