Multilevel Queue
멀티레벨 큐란 레디 큐를 여러 개로 분할해 관리하는 스케줄링 기법을 말한다.
멀티레벨 큐는 성격이 다른 프로세스들을 별도로 관리하고 성격에 맞는 스케줄링을 적용하기 위해 레디 큐를 별도로 둔다.
- foreground: 대화형 작업, 라운드 로빈 스케줄링
- background: 배치, 계산 위주의 작업, FCFS 스케줄링
두개의 큐를 위한 스케줄링도 별도로 필요하다. 즉, 여러 개의 준비 큐에 대해 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링이 필요하다는 것이다.
- Fixed priority scheduling: 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때에만 서비스하게 된다. 기아 현상의 가능성이 있다.
(전위 큐가 우선시, 전위 큐가 비어있을 경우 후위 큐에 할당) - Time slice: 큐에 대한 기아 현상을 해소할 수 있는 방식이다. 각 큐에 CPU 시간을 적절한 비율로 할당한다.
- 예를 들어, 전위 큐에 20%, 후위 큐에 80%
Multilevel Feedback Queue
멀티레벨 피드백 큐는 CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하지만, 프로세스가 하나의 큐에서 다른 큐로 이동이 가능하다는 점이 다르다.
- 우선순위 스케줄링에서 기아 현상을 해결하기 위한 방법으로 노화 기법을 멀티레벨 피드백 큐 방식으로 구현이 가능하다.
멀티레벨 피드백 큐를 정의하는 요소들
- 큐의 수
- 각 큐의 스케줄링 알고리즘
- 프로세스를 상위 큐로 승격시키는 기준
- 프로세스를 하위 큐로 강등시키는 기준
- 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준
예시
세개의 큐, q가 8인 , q가 16인 ,FCFS 스케줄링을 사용하는 가 있다. 상위에 있는 큐일수록 우선순위가 높다.
스케줄링
- 프로세스가 준비 큐에 도착하면 우선순위가 높은 에 삽입된다.
- 작업은 8만큼의 시간동안 CPU를 사용해야한다.
- 8만큼 작업을 끝내지 못한다면 작업은 그 다음 큐인 으로 이동한다.
- 에서 16밀리 초안에 작업을 끝내야 한다.
- 작업이 완료되지 않으면 CPU를 오래사용하는 계산 위주의 프로세스로 간주되어 최하위 큐인 로 이동하게 된다.
큐에 대한 스케줄링은 상위 큐가 우선적으로 CPU를 할당받고 상위 큐가 비었을 때에만 하위 큐에 있는 프로세스들이 CPU를 할당받을 수 있게 된다. RR 스케줄링을 더 발전시켜 프로세스의 CPU 작업시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 더욱 더 빠른 서비스가 가능하게 되고 작업시간이 긴 프로세스에 대해서는 문맥교환없이 CPU 작업에만 집중할 수 있는 FCFS 스케줄링을 선택하였다.
Real-Time Scheduling
실시간 시스템에서는 다른 시스템과 달리 각 작업마다 주어진 데드라인이 있어 정해진 데드라인까지 반드시 작업을 끝마쳐야 한다.
- Hard real-time system: 미사일 발사, 원자로 제어등과 같이 정확성이 필요로하는 시스템을 말한다. 반드시 데드라인을 지켜야한다.
- Soft real-time system: 데드라인이 있긴 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지 않는다. 멀티미디어 스트리밍 시스템이 그 예이다.
우선순위 할당 스케줄링
- Static: Rate-Monotoic algorithm
- Dynamic: EDF(Earlist Deadline First) algorithm
스케줄링 알고리즘 평가
- deterministic modeling: 미리 결정된 특정 workload를 사용하고 해당 워크로드에 대한 각 알고리즘의 성능을 정의한다.
- queueing model: 수학적 모델을 통해 CPU 처리량, 평균 대기시간을 구한다.
- simulation: 가상의 CPU 스케줄링 프로그램에 입력값을 넣어 결과를 확인하는 방법이다.
- implementation & measurement: 커널의 CPU 스케줄링 수행 코드를 수정해 커널을 컴파일하고 시스템에 설치해 수행하고 그 결과로 평가한다.
