스케줄링 알고리즘
단기 스케줄링 평가 기준들
단기 스케줄링의 주된 목적
-> 시스템의 전체 성능을 높이기 위해 처리기 시간을 프로세스들에게 효율적으로 분배
- 사용자 중심의 관점/시스템 중심의 관점에서 평가
- 성능 중심의 관점에서/성능과 관련 없는 다른 척도로 평가
사용자 중심의 성능 관련 평가척도
개별 사용자/프로세스의 입장에서 긍정적으로 영향을 미치는 스케줄러인지 평가
- 반환 시간(turnaround time)
- 프로세스가 시스템으로 진입한 후부터 종료할 때까지 걸린 시간
- 실제 실행 시간 뿐만 아니라 CPU나 다른 자원들을 사용하기 위해 대기한 시간까지 모두 포함 - 응답시간(response time)
- 대화형 프로세스가 시스템에 요구를 한 후 이에 대한 시스템으로부터의 첫 번째 응답이 올 때까지의 시간 - 완료 기한(deadline)
- 프로세스가 완료되어야 하는 시점에 기한이 있다면, 스케줄러는 다른 평가척도가 희생당하더라도 완료 기한을 만족시킬 수 있는 프로세스의 수를 최대화해야함
사용자 중심의 성능 관련 평가척도
- 예측 가능성(Predictability)
- 같은 작업이라면 실행될 때마다 동일한 기간 동안 실행되어야 하고, 시스템의 부하 정도에 상관없이 동일한 비용으로 실행되어야 함
- 성능이 불안정한 경우 시스템 튜닝(tuning)을 통해 해소
시스템 중심의 성능 관련 평가척도
스케줄러가 처리기를 얼마나 효율적이고도 효과적으로 활용했는지 평가
- 처리량(throughout)
- 단위 시간 내에 완료될 수 있는 프로세스의 수를 최대화하는 정책 사용 - 처리기 이용률(processor utilization)
- 전체 시간 중에 처리기가 바쁘게 실행을 한 시간의 비율
- 단일-사용자 시스템이나 실시간 시스템에서는 처리기 이용률이 중요한 성능 척도로 사용 X
시스템 중심의 기타 평가척도
- 공정성(fairness)
- 시스템이 어떤 특정 목적을 위해 미리 공표하지 않은 이상 어떤 프로세스도 스케줄러로부터 차별을 받아선 안됨
- 차별이 심하면 기아(starvation) 상태 발생 가능 - 우선순위의 부여(enforcing priority)
- 프로세스들에게 우선순위가 부여되고 나면 스케줄러는 높은 우선순위의 프로세스를 우대 - 균형 있는 자원(balancing resources)
- 활용 스케줄러는 시스템 내의 자원들이 가능한 한 최대한 활용되도록 해야함
- 중기/장기 스케줄러 차원에서 시행하는 것이 바람직함
우선순위-기반 스케줄링
모든 프로세스에 우선순위를 부여하고 스케줄러는 항상 우선순위가 가장 높은 프로세스를 다음번 프로세스로 선택
우선순위[] > 우선순위[] ()에 대해
단점
- 낮은 우선순위의 프로세스가 계속 실행되지 못함
=> 기아(starvation) 발생 가능성
다양한 스케줄링 정책들
| 구분 | 선택함수 | 결정모드 | 처리량 | 응답시간 | 문맥 교환 비용 | 프로세스들에게 미치는 영향 | 기아 발생 여부 |
|---|---|---|---|---|---|---|---|
| FCFS | max | 비선점 모드 | 상조 안됨 | 길어질 수 있음. 프로세스의 총 실행 시간 편차가 클 경우 안 좋을 수 있음 | 최소 | 짧은 프로세스들에게 불리 입출력 중심 프로세스들에게 불리 | 가능성 없음 |
| Round Robin | 상수 | 선점 모드(시간 할당량 만료 시점) | 시간 할당량이 아주 작을면 처리량이 아주 낮을 수 있음 | 짧은 프로세스에게 좋은 응답 시간 | 최소 | 모든 프로세스들에게 송정 | 가능성 없음 |
| SPN | min | 비선점 모드 | 높음 | 짧은 프로세스에게 좋은 응답시간 | 커질 수 있음 | 긴 프로세스들에게 불리 | 가능성 있음 |
| SRT | min | 선점 모드(새 작업 도착 시점) | 높음 | 짧은 프로세스들에게 좋은 응답 시간 제공 | 커질 수 있음 | 긴 프로세스들에게 불리 | 가능성 있음 |
| HRRN | max | 비선점 모드 | 높음 | 좋은 응답 시간 제공 | 커질 수 있음 | 어느정도 공정한 편 | 가능성 없음 |
| Feedback | 선점 모드(시간 할당량 만료 시점) | 고려 안함 | 고려 안함 | 커질 수 있음 | 입출력 중심 프로세스를 우대하는 경향이 있음 | 가능성 있음 |
= 지금까지 실행 또는 대기하면서 시스템 내에 머문 시간
= 지금까지 실행하는 데에 소요한 시간
= 를 포함하여 프로세스가 요구한 총 서비스 시간
선택 함수(selection function)
다음번 실행을 위해 준비 큐에서 대기 중인 프로세스 중 하나를 고를 때 사용하는 알고리즘을 함수 형태로 표현한 것
결정 모드(decision mode)
선택 함수가 호출되는 시점이 언제인가 하는 것결정 모드 - 비선점 모드(Nonpreemptive)
프로세스가 일단 실행 상태(Running state)에 진입하면 종료되거나 자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않음결점 모드 - 선점 모드(Preemptive)
현재 실행 중인 프로세스라 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있음🚨 선점 모드 스케줄링에서는 비선점 모드 스케줄링에 비해 프로세스 간 문맥 교환이 자주 발생하기 때문에 이로 인한 오버헤드가 큼
🚨 하지만 한 프로세스가 처리기를 오랫동안 독점하는 현상을 방지하여 비선점 모드보다 나은 서비스 제공
스케줄링 예를 위한 프로세스 집합
- 서비스 시간의 의미
- 프로세스들의 일괄 작업으로 가정
- 시작부터 종료까지 소요되는 총 실행 시간의 의미
- 이미 실행되고 있는 계산/입출력 교행 프로세스들로 가정
- 다음번 사이클 동안에 실행할 시간
>큐잉 분석 - 정규화된 반환 시간
>어떤 프로세스가 시스템에 진입한 후 대기하느라 실행이 지연된 시간의 비율
> $$\frac{Tr}{Ts} = \frac1{1-p}$$
>
> $r$ = 상주시간(residence Time)
> $Tr$ = 반환 시간 또는 시스템에 머문 시간; 시스템 내에 총 머문 시간(대기 시간 + 실행 시간)
> $Ts$ = 평균 서비스 시간; 실행 상태에 머물렀던 평균 시간
> $p$ = 처리기 이용률
>
>✔️ 정규화된 반환 시간이 1.0 => 시스템에 진입한 후 한 번도 대기한 적이 X
>✔️ 아무리 훌륭한 스케줄러라도 정규화된 반환 시간을 1.0 밑으로 떨어뜨릴 수는 없으며, 이 값의 크기와 스케줄링 서비스의 질은 반비례함
FCFS(First-Come-First-Served)
가장 단순한 형태의 스케줄링 정책으로 FIFO(First-In-First-Out)라고도 함
- 큐잉 정책을 엄격하게 지키고 있는 형태
- 실행 중인 프로세스가 종료되면 준비 큐에서 대기중이던 프로세스 중 가장 오랫동안 기다렸던 프로세스가 다음번 실행할 프로세스로 선정
- 짧은 프로세스보다는 긴 프로세스에 유리 (짧은 프로세스가 피해를 봄)
- 짧은 Y프로세스가 순서대로 실행되면서 오래 기다려야 함(정규화된 반환시간이 긺)
- Z 프로세스 또한 짧은 프로세스에 비해 상대적으로 피해가 적을 뿐 피해는 있음 - 입출력 중심의 프로세스보다 처리기 중심 프로세스 우대
- 비선점으로 동작하므로 문맥 교환이 안 일어남 - 처리기 및 입출력장치 모두에게 비효율적인 스케줄링 정책
Round-Robin
시간할당량(time sclicing, 또는 quantum)기법을 통해 일정 시간이 지나면 클록(Clock) 인터럽트(타이머 인터럽트)를 실행시켜 CPU를 뺏음
- 시간 할당량이 짧으면 문맥교환 오버헤드 / 길면 FCFS와 같은 효과를 얻음
=> 시간 할당량의 길이 설계가 중요 - 처리기 중심 프로세스가 입출력 중심 프로세스보다 CPU를 더 사용하게 됨
- 단위시간이 짧은 프로세스가 혜택을 봄(E)
- 공평성이 뛰어남
- 범용 시분할 시스템
- 트랜잭션 처리 시스템에 효과적인 스케줄링
가상 라운드 로빈(Virtual Round Robin)
개선된 라운드 로빈 스케줄링 정책
- 기존 라운드 로빈의 경우
- 원하는 입출력이 완료된 프로세스는 준비 큐의 끝으로 이동 - 가상 라운드 로빈의 경우
- 입출력이 완료된 프로세스는 보조 큐라고 하는 별도의 FCFS 큐로 들어감.
- 다음 프로세스를 고르는 시점에서 스케줄러는 보조 큐에서 대기 중인 프로세스를 준비 큐보다 먼저 실행 - 저번 실행 때 못 채우고 반납한 시간 할당량만큼만 실행
- 공평성의 측면에서 기존 라운드 로빈보다 우수
Shortest Process Next(SPN)
가장 짧은 프로세스를 먼저 실행시키는 정책
- 비선점 모드로 작동
- 종료 시까지 남아 있는 실행시간이 가장 짧은 프로세스를 다음 프로세스로 선택 - 응답시간의 개선
- 문제점
- 각 프로세스가 요구하는 총 실행 시간을 미리 알거나 추측할 수 있어야 함
- 만약 실제 총 실행 시간이 프로그래머가 알려준 총 실행시간보다 현격히 초과하면 OS는 해당 프로세스를 강제로 종료
- 각 프로세스가 CPU를 잡고 한 번의 시간할당량 중 얼마나 오랫동안 실행하는지에 대한 평균값
- 모든 스케줄링 순번에서의 실행 시간에 동일한 가정치를 둠
- 과거의 데이터를 그 시간에 따라 다른 가중치를 두어 활용하는 방식(시계열 방식(time series) -> 지수적 평균(Exponential averaging))
- 모든 과거 측정치들을 다 활용하면서도 현재로부터 먼 과거에 있는 측정치일수록 미래의 예측에 미치는 영향은 줄어듦
- 짧은 프로세스들이 지속적으로 시스템에 진입한다면 상대적으로 긴 프로세스가 기아 상태에 빠질 수 있음
- 비선점 모드로 작동하기 때문
Shortest Remaining Time(SRT)
SPN의 선점 모드 버전
- 예상되는 남아 있는 실행시간이 가장 짧은 프로세스가 다음번 프로세스로 선택됨(SPN과 달리 예상되는 전체 실행 시간X)
- 새로 도착한 프로세스의 예상되는 남아있는 실행 시간이 현재 실행중인 다른 모든 프로세스들보다 짧다면 실행 중인 프로세스를 선점하고 곧장 선택됨
- 단점
- 매 스케줄링 때마다 프로세스들의 남아있는 실행시간을 평가해야 함
- 긴 프로세스가 기아에 빠질 위험이 있음
- 각 프로세스의 전체 서비스 요구 시간 중 지금까지 얼마나 서비스 받았는지 기억하고 있어야 하는 오버헤드 존재(남아있는 실행시간 계산용) - 선점을 통해 반환시간이 SPN보다 월등히 우수함
Hightest Response Ration Next(HRRN)
전체 프로세스들에 대해서 정규화된 반환시간의 평균값을 최소화하는 방향의 스케줄링 정책
정규화된 반환시간 : 서비스 시간 대비 반환 시간의 비율
정규화된 반환 시간을 일반화한 일종의 응답 비율을 계산할 때 사용할 수 있는 계산식
✔️ R(response rate)의 값도 1.0 이하로는 내려갈 수 없음
해당 응답시간을 활용한 스케줄링 정책
=> 스케줄러는 준비 큐에 있는 프로세스 중 R값이 가장 큰 프로세스를 다음번 프로세스로 선택
- 프로세스가 시스템 내에서 머문 시간을 고려하고 있다는 점에서 매력적인 편
- 하지만 s(예상되는 서비스 시간)을 알기 어려움(위의 지수평균)
- 과거의 서비스 시간 기록
- 사용자가 직접 제공한 정보
- 설정 파일 관리자
피드백(Feedback)
프로세스들의 예상되는 서비스 시간을 미리 알아낼 수 없는 경우
=> SPN, SRT, HRRN 모두 불가능
다른 짧은 프로세스에 대한 선호도를 높일 수 있는 방법
=> 오랫동안 실행하고 있는 작업들이 단계적으로 불이익을 받도록 만듦
다단계 피드백 방식(multilevel feedback)
시간 할당량이 있는 선점 모드로 운영하면서 동시에 동적인 우선순위 정책을 병행 사용
새로 도착한 프로세스일수록, 짧은 프로세스일수록 오래된 프로세스나 긴 프로세스보다 우대받는 정책
- 프로세스가 최초로 시스템에 진입하면 RQ0으로 진입
- 첫 번째 선점점에 도달하면 다시 준비상태로 돌아가면서 RQ1로 들어감
- 계속해서 선점점에 도달할 때마다 한 단계 낮은 우선순위위 준비 큐로 강등되어 진입
- 각 큐 내에서는 가장 낮은 우선순위 큐만 제외하고 모두 FCFS 방식으로 다음번 프로세스 선택
- 가장 낮은 우선순위까지 가면 다시 선점점에 도달해도 같은 큐의 맨 뒤로 들어감
다단계 피드백 스케줄링 정책의 변형
- 모든 큐에서 시간할당량이 있는 FCFS 방식의 라운드 로빈 방식으로 만듦
- 시간 할당량을 큐 별로 다르게 줌
🚨 근데 잘못하다 기아 상태까지 갈 수 있음
스케줄링 정책들의 성능 비교
시스템의 상황에 따라 성능이 좌우됨
- 프로세스 서비스 시간들의 확률 분포
- 스케줄링 자체의 효율성
- 문맥 교환 메커니즘
- 입출력 요구 패턴
- 입출력 서브시스템의 성능
=> 스케줄러의 성능을 명확하게 비교하는 것은 불가능하지만 일반론적인 결론을 위한 성능 비교 기법들을 통해 측정
큐잉 분석(Queuing Analysis)
프로세스들의 도착률은 포아송(Poisson) 분포/서비스 시간은 지수적(exponential) 분포를 보인다고 가정
= 상주시간(residence Time)
= 반환 시간 또는 시스템에 머문 시간; 시스템 내에 총 머문 시간(대기 시간 + 실행 시간)
= 평균 서비스 시간; 실행 상태에 머물렀던 평균 시간
= 처리기 이용률
예상되는 서비스 시간에 근거한 스케줄링 정책들을 세밀하게 관찰하기 불가능
=> 우선순위에 고려하는 여러 정책들의 성능을 그렇지 않은 정책과 비교함으로써 상대적인 선은 평가
✔️ 짧은 작업을 우대함으로써 처리기 이용률이 높아짐에 따라 평균 정규화된 반환 시간을 개선시킬 수 있음
✔️ 하지만 평균 정규화된 반환시간의 개선에도 불구하고 전체 성능의 차이가 확연하지 않음
✔️ 각 우선순위 등급을 따로 분리하여 생각하는 경우 큰 차이를 볼 수 있음
✔️ 시스템이 빈선점 모드의 우선순위 기반 스케줄링 기법을 사용했을 때 짧은 프로세스들에 대해서 큰 성능 향상을 보임
✔️ 긴 프로세스들에 대한 경우 우선순위를 사용한 경우 더 안좋은 성능을 보임
시뮬레이션 모델링
- 큐잉 분석 기법의 경우 사용하기 까다롭지만 시뮬레이션 기법을 통해 다양한 스케줄링을 모델링 가능
- 결과를 일반화시킬 수는 없지만 각 스케줄링 기법이 왜 그런 성능을 보이는지에 대한 직관을 높이기 좋음
- 프로세스 도착률 = 0.8, 평균 서비스 시간() = 1 처리기 이용률(도착률 x 평균 서비스 시간) = 1 * 0.8 = 0.8
- 100개의 그룹 -> 서비스시간 1 요구 프로세스 500개, 서비스시간 2 요구 프로세스 500개.. 서비스시간 100 요구 프로세스 500개로 분류하여 시뮬레이션
대기 시간에 대한 시뮬레이션 결과의 경우
✔️ FCFS -> 전체 프로세스 수의 1/3 이상에서 자기 서비스 시간의 10배가 넘는 정규화된 반환 시간으로 피해가 크지만 대기시간은 서비스 시간에 관계없이 일정 -> 서비스 시간을 고려하지 않아서 + 긴 프로세스 선호
✔️ 라운드 로빈 -> 시간 할당량이 1보다 작은 짧은 프로세스들을 제외하고 5정도로 균일한 성능
✔️ SPN -> 아주 짧은 프로세스들만 빼면 라운드 로빈보다 좋은 성능 + 짧은 프로세스 우대
✔️ SRT -> 서비스 시간이 긴 상위 7%정도를 제외하고 SPN보다 전반적으로 나은 성능
✔️ HRRN -> FCFS와 SPN 각각의 단점을 상호 보완하는 결과
✔️ 피드백 -> 짧은 프로세스들에 대해 꽤 좋은 성능
Fair-Share 스케줄링
프로세스 집합 단위의 스케줄링 방식
- 다중사용자 시스템의 경우 사용자 응용프로그램이 여러 개의 프로세스들로 구성된 경우도 있음
=> 스케줄링의 단위를 개별 프로세스가 아닌 프로세스 집합 단위로 하는 것이 공정성 측면에서 더 유리함 - 각 사용자에게 가중치 부여 -> 시스템 전체 자원 중에 이 사용자가 사용할 수 있는 지분을 정하여 자원 사용율을 지분에 맞게 통제
- 우선순위에 기반한 스케줄링
- 프로세스별 우선순위 뿐만 아니라 최근 처리기 사용 시간이나 프로세스가 소속된 그룹이 최근 소비한 처리기 시간 등을 모두 고려한 복합 우선순위 - 복합 우선순위를 구하는 공식
- 각 프로세스는 처음에 기본 우선순위를 갖고 프로세스가 처리기를 사용할 때마다, 그 프로세스가 속한 그룹이 처리기를 사용할 때마다 프로세스의 우선순위는 점차 낮아짐(값은 커짐)
- 그룹 사용률(GCPU)이 복합 우선순위에 반영될 때에는 해당 그룹의 가중치로 나누어져 정규화된 후 반영
