기출 mlq mlf

문제: 다단계 큐(Multilevel Queue) 스케줄링 알고리즘의 목적, 개념, 작동 원리, 종류, 장단점에 대해 설명하세요.

답변:

1. 목적

다단계 큐 스케줄링(Multilevel Queue Scheduling) 알고리즘은 프로세스들이 서로 다른 우선순위를 갖고 다양한 요구 사항을 충족할 수 있도록 설계되었습니다. 이 방식은 프로세스를 우선순위와 특성에 따라 여러 개의 큐로 분류하고 각 큐별로 다른 스케줄링 알고리즘을 적용해, 다양한 응답성과 처리 요구를 만족하려는 목적을 가집니다.

2. 개념

다단계 큐 스케줄링은 시스템 내의 프로세스를 성격이나 우선순위에 따라 여러 개의 큐로 나누어 스케줄링을 수행하는 방식입니다. 각 큐는 독립적으로 스케줄링 규칙을 가질 수 있으며, 큐 간에도 우선순위가 있어서 높은 우선순위의 큐에 있는 프로세스가 먼저 실행됩니다.

3. 작동 원리

   1. 프로세스 분류: 먼저 프로세스는 우선순위나 성격에 따라 여러 개의 큐로 분류됩니다. 예를 들어, 시스템 프로세스는 높은 우선순위 큐에, 사용자 프로세스는 낮은 우선순위 큐에 배치될 수 있습니다.
   2. 각 큐에 독립적인 스케줄링 방식 적용: 큐마다 다른 스케줄링 알고리즘을 적용할 수 있습니다. 예를 들어, 높은 우선순위 큐는 Round-Robin(라운드로빈) 방식을 사용할 수 있고, 낮은 우선순위 큐는 FCFS(First-Come, First-Served; 선입선출) 방식을 사용할 수 있습니다.
   3. 큐 간 우선순위 적용: 높은 우선순위 큐의 프로세스가 먼저 실행됩니다. 만약 높은 우선순위 큐에 실행 대기 중인 프로세스가 있다면, 낮은 우선순위 큐의 프로세스는 대기해야 합니다.
   4. 계층적 접근: 일반적으로 시스템은 최상위 큐부터 순차적으로 탐색하여 실행할 프로세스를 선택합니다. 최상위 큐가 비어 있어야만 그다음 큐를 탐색하여 프로세스를 실행합니다.

4. 종류

   1. 정적 다단계 큐: 프로세스의 우선순위가 고정되어 있으며, 한 번 큐에 배정되면 다른 큐로 이동할 수 없습니다.
   2. 다단계 피드백 큐(Multilevel Feedback Queue): 프로세스가 다른 큐로 이동할 수 있는 방식입니다. 프로세스가 할당받은 CPU 시간을 다 사용하면 낮은 우선순위 큐로 이동하거나, 대기 시간이 길어지면 더 높은 우선순위 큐로 이동할 수 있습니다.

5. 장점

   1. 프로세스의 특성 반영: 다단계 큐는 각 큐에 서로 다른 스케줄링 방식을 적용해, 다양한 프로세스의 요구사항을 충족할 수 있습니다.
   2. 우선순위 제어: 높은 우선순위의 작업이 항상 먼저 실행되므로, 중요한 작업이 빠르게 처리됩니다.
   3. 다양한 스케줄링 전략 병합: 각 큐에 적합한 스케줄링 알고리즘을 설정해 최적의 성능을 도모할 수 있습니다.

6. 단점

   1. 유연성 부족: 정적 다단계 큐의 경우 프로세스가 다른 큐로 이동할 수 없으므로, 변화하는 프로세스의 우선순위 요구를 반영하기 어렵습니다.
   2. 기아 문제(Starvation): 낮은 우선순위 큐에 있는 프로세스가 높은 우선순위 큐의 프로세스에 의해 계속 대기하는 문제가 발생할 수 있습니다.
   3. 복잡성 증가: 각 큐의 스케줄링 정책을 독립적으로 관리해야 하므로, 관리가 복잡해질 수 있습니다.

7. 개선점 및 전망

다단계 큐 스케줄링의 경우 다단계 피드백 큐처럼 프로세스 이동을 허용하는 방식으로 개선하면, 보다 유연하게 변화하는 요구를 반영할 수 있습니다. 이러한 유연한 구조는 특히 멀티태스킹을 요구하는 현대의 시스템에서 더욱 중요한 요소가 되고 있습니다.

문제: 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링 알고리즘의 목적, 개념, 작동 원리, 장단점에 대해 설명하세요.

답변:

1. 목적

다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링 알고리즘은 다양한 프로세스 특성에 맞추어 유동적으로 우선순위를 조정함으로써 전체 시스템의 응답성과 효율성을 높이려는 목적을 가집니다. 특히, 긴 실행 시간을 요구하는 프로세스와 짧은 작업을 잘 구분하여 시스템 자원을 효율적으로 사용하고, 작업 간 공평성을 유지하는 것을 목표로 합니다.

2. 개념

다단계 피드백 큐 스케줄링은 프로세스를 여러 개의 우선순위 큐로 나누고, 프로세스의 실행 상황에 따라 큐 사이를 이동할 수 있도록 하는 유동적인 스케줄링 방식입니다. 각 큐에는 다른 우선순위와 CPU 할당 시간이 설정되며, 프로세스가 CPU 할당 시간을 다 사용하면 낮은 우선순위의 큐로 이동하게 됩니다. 이러한 방식은 짧은 작업을 신속하게 처리하고 긴 작업은 점차 낮은 우선순위에서 실행하도록 유도하여 시스템의 자원 분배를 최적화합니다.

3. 작동 원리

   1. 초기 배정: 프로세스는 처음에 높은 우선순위 큐에 배정됩니다. 높은 우선순위 큐일수록 짧은 타임 슬라이스(Time Slice)를 갖게 되며, 이는 빠르게 처리할 수 있는 짧은 작업이 빠르게 완료되도록 도와줍니다.
   2. CPU 할당 시간 사용 후 이동: 프로세스가 할당된 CPU 시간을 모두 사용하면, 다음 낮은 우선순위 큐로 이동합니다. 이로 인해 긴 작업은 점점 낮은 우선순위 큐에서 실행되고, 짧은 작업은 높은 우선순위 큐에서 빠르게 처리됩니다.
   3. 큐 사이 이동 규칙: 대기 시간이 너무 길어진 프로세스는 더 높은 우선순위 큐로 다시 이동해 처리 기회를 부여받을 수도 있습니다. 이로 인해 기아 현상(Starvation)을 방지하고 공평한 자원 배분이 가능해집니다.
   4. 다양한 큐의 스케줄링 적용: 각 큐에는 Round-Robin(라운드로빈) 같은 선점형 스케줄링이 주로 적용되지만, 낮은 우선순위 큐에는 FCFS(First-Come, First-Served; 선입선출) 같은 비선점형 방식이 적용될 수 있습니다. 이는 시스템 상황과 요구사항에 맞추어 다양한 스케줄링 방식을 조합하여 사용함을 의미합니다.

4. 장점

   1. 응답성 향상: 짧은 작업이 높은 우선순위 큐에서 빠르게 처리되므로 사용자 응답 시간이 개선됩니다.
   2. 효율적인 자원 분배: 긴 작업은 낮은 우선순위 큐로 밀려나고 짧은 작업이 우선 처리되어 전체 시스템 효율이 높아집니다.
   3. 기아 현상 방지: 오랫동안 대기한 프로세스는 다시 높은 우선순위 큐로 이동할 수 있으므로 기아 문제가 방지됩니다.
   4. 유연성: 프로세스가 큐 간 이동을 통해 각자의 요구사항에 맞는 적절한 우선순위를 부여받을 수 있어 변화하는 시스템 요구에 유연하게 대처할 수 있습니다.

5. 단점

   1. 설계 및 관리의 복잡성: 각 큐의 우선순위, 타임 슬라이스, 이동 규칙을 설정해야 하므로 관리가 복잡해집니다.
   2. 자원의 비효율적 사용 가능성: 모든 프로세스가 큐를 순차적으로 이동하게 되면 불필요한 이동이 발생할 수 있어 시스템 자원이 낭비될 수 있습니다.
   3. 응용의 어려움: 특정 작업에 대해 최적화된 큐 이동 규칙을 설정하기 어렵고, 다양한 작업 특성을 모두 만족시키기 어렵습니다.

6. 개선점 및 전망

다단계 피드백 큐 스케줄링은 작업의 특성에 맞는 유연한 우선순위 조정을 통해 시스템 효율을 높이지만, 복잡한 관리와 설정의 어려움이 단점으로 꼽힙니다. 이를 개선하기 위해 머신러닝 기반의 스케줄링 예측이나 동적 자원 할당 알고리즘과의 결합을 통해 복잡성을 줄이고 최적화된 큐 이동 규칙을 자동으로 설정하는 방안이 연구되고 있습니다.