[운영체제 정리] 7.멀티레벨 큐

멀티레벨 큐

레디큐를 여러개로 분한다. cpu를 기다리는 여러 큐가 존재한다 위로 갈수록 우선순위가 높다. 준비 큐를 여러개로 분할해 관리하는 스케줄링 기법을 말한다. 즉, 프로세스들이 cpu를 기다리기 위해 한줄로 서는 것이 아니라 여러줄로 서는 것을 말한다. 멀티레벨큐는 일반적으로 성격이 다른 프로세스들을 별도로 관리하고 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 별도의 큐를 두게 된다.

 

여러개의큐

 

포그라운드 큐: 사용자와 소통 중심

백그라운드 큐: 배치 프로그램

 

 

큐 자체에 대한 스케쥴링

- 고정 우선순위 방식

고정적인 우선순위를 부여해 우선 순위가 높은 큐를 먼저 서비스 하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비었을때 서비스하게 된다.즉, 전위 큐와 후위큐를 사용하는 방식에서는 전위 큐에 있는 프로세스에게 우선적으로 cpu가 할당되고, 전위 큐가 비어 있을 경우에만 후위 큐에 있는 프로세스에게 cpu가 할당될 수 있다.

 

- 타임 슬라이스

큐에 대한 기아현상을 해소할 수 있는 방식으로 각 큐에 cpu 시간을 적절한 비율로 할당하게 된다.

큐별 스케쥴링법

포그라운드(전위큐): 라운드로빈(응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용한다.)

백그라운드(후위큐):계산위주의 작업을 위한 후위큐에서는 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥 교환 오버헤드를 줄인다.

 

줄이 여러개이지만,  cpu는 하나기때문에 고려할 점이 있다.

1.프로세서를 어느 줄에 넣을 것인가?

2.우선순위가 높은 줄이 계속 차있으면 아래 줄은 cpu을 못받는다..(기아현상)

 

해결

각 큐에 cpu할당시간을 적절한 비율로 할당.(멀티레벨 피드백큐)

 

멀티레벨 피드백 큐

 

멀티 레벨 피드백 큐는 cpu를 기다리는 프로세스를 여러 큐에 줄세운다는 측면에서 멀티 레벨 큐와 동일하나 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다. 

 

예) 우선순위 스케줄링에서 기아현상을 해결하기 위해 등장 했던 노화 기법을 멀티레벨 피드백 큐 방식으로 구현 할 수 있다. 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식이 그것이다.

 

특징

- 프로세스들의 다양한 성격을 반영해 구현할 수 있다.

- 프로세스가 다른큐로 이동가능하다.

- 에이징을 이와같은 방식으로 구현할 수 있다.

 

- 멀티 피드백 큐를 정의하는 파라미터들

1.큐의 수

2.각 큐의 스케쥴 알고리즘

3.프로세스를 상위 큐로 보내는 기준

4.프로세스를 하위 큐로 내쫓는 기준

5.프로세스가 cpu서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

 

세계의 큐 시나리오

처음 들어오는 프로세서는 우선순위가 가장 높은 큐에 넣는다. 그리고 라운드 로빈 시간을 아주 조금 준다. 그리고 만약 처리가 그 큐에서 안끝났다면 아래 큐로 보내고 아래 큐로 갈수록 라운드 로빈 할당 시간을 조금씩 늘린다. 그리고 아래로 갈 수록 fcfs로 스케쥴링을 한다.

 

특이한 케이스의 cpu스케쥴(cpu가 여러개일때)

cpu가 여러개인 시스템을 다중처리기 시스템이라고 부른다. 다중 처리기 환경에서의 cpu 스케쥴링은 cpu가 하나인 시스템에서 보다 더욱 복잡하다. 프로세스를 준비 큐에 한 줄로 세워서 각 cpu가 알아서 다음 프로세스를 꺼내어 가도록 할 수 있다.

한편, 여러줄로 줄 세우기를 하는 경우 일부 cpu에 작업이 편중되는 현상이 발생할 수 있다.

다중처리기 스케줄링에서는 이와 같은 현상을 방지해 각 cpu별 부하를 적절히 분산되도록 하는 부하 균형 메커니즘이 필요하다. 

 

- 대칭형 다중처리 : 각 cpu가 각자 알아서 스케줄링을 결정하는 방식

- 비대칭형 다중처리 : 하나의 cpu가 다른 모든 cpu의 스케줄링 및 데이터의 접근을 책임지고 나머지 cpu는 거기에 따라 움직이는 방식을 말한다.

리얼타임 스케쥴링

- 하드리얼타임 시스템: 반드시 시간내에 처리되도록 스케쥴링 해야함.데드라인 보장.데드라인이 존재하는 스케줄링 기법. 데드라인이 존재하는 프로세스에게 우선순위 할당하는 기법.

예) 원자력 발전소 등.

 

- 소프트리얼타임 컴퓨팅: 높은 우선순위만 부여.데드라인이 존재 하지 않는 스케줄링 기법

예) 스트리밍 등

 

스레드 스케쥴링

프로세스 하나에 cpu수행단위가 여러개있다.

로컬 스케쥴링 : 프로세스 내부에서 어떤 스레드에게 cpu를 줄지 결정.(커널은 모름)

커널 스케쥴링 : 운영체제(커널)가 알고리즘에 근거해서 어떤 스레드에게 cpu줄지 결정.

 

 

알고리즘을 평가하는 방법

-큐잉모델: 큐에 잡들이 쌓이고, cpu에서 처리되고 빠져나가는 상황에서의 값을 계산.(도착률과 처리률)(이론적으로 사용한다)

-구현/성능측정: 직접 cpu스케쥴링 알고리즘을 커널에 소스코드로 구현해서 컴파일해서 비교한다.

 

 

참고: 이화여대 반효경 교수님 운영체제 강의정리