C 언어로 멀티레벨 큐 스케줄링 구현하기

멀티레벨 큐 스케줄링(Multi-level Queue Scheduling)은 운영 체제의 프로세스 스케줄링에서 사용되는 효율적인 알고리즘 중 하나입니다. 프로세스를 여러 개의 큐로 나누고, 각 큐에 우선순위를 부여해 프로세스를 처리합니다. 본 기사에서는 멀티레벨 큐 스케줄링의 기본 개념부터 C 언어를 활용한 구현 방법, 그리고 실제 응용 사례까지 다루어 독자가 알고리즘을 이해하고 직접 구현할 수 있도록 돕습니다.

멀티레벨 큐 스케줄링의 개요

멀티레벨 큐 스케줄링은 프로세스를 우선순위 또는 특성에 따라 여러 개의 큐로 나누고 각 큐를 독립적으로 관리하는 스케줄링 방식입니다. 운영 체제의 CPU 스케줄링에서 사용되며, 다양한 작업 유형에 대해 최적의 성능을 제공합니다.

작동 원리

멀티레벨 큐 스케줄링은 다음과 같은 방식으로 작동합니다.

1. 큐 분리: 시스템은 프로세스를 특성(예: I/O 중심, CPU 중심)이나 우선순위에 따라 여러 개의 큐로 분리합니다.
2. 큐 간 우선순위: 각 큐는 고유한 우선순위를 가지며, 높은 우선순위의 큐가 먼저 실행됩니다.
3. 큐 내부 스케줄링: 각 큐는 독립적인 스케줄링 알고리즘(예: FCFS, Round Robin)을 사용할 수 있습니다.

적용 예시

• 실시간 시스템: 실시간 프로세스는 높은 우선순위 큐에 배치되고 즉각 실행됩니다.
• 일반 프로세스: 백그라운드 작업은 낮은 우선순위 큐로 할당되어 CPU가 유휴 상태일 때 실행됩니다.

이 알고리즘은 다양한 프로세스의 특성을 반영해 자원을 효과적으로 배분할 수 있는 강력한 도구입니다.

멀티레벨 큐 스케줄링의 장점과 단점

장점

1. 효율적인 자원 배분: 프로세스를 특성에 따라 분리하여, CPU와 같은 자원을 효율적으로 사용할 수 있습니다.
2. 유연성: 각 큐가 독립적인 스케줄링 알고리즘을 사용하므로 다양한 프로세스 요구사항에 대응할 수 있습니다.
3. 응답 시간 향상: 높은 우선순위의 큐가 먼저 처리되기 때문에 실시간 작업이나 중요한 프로세스의 응답 시간이 단축됩니다.

단점

1. 기아 문제(Starvation): 낮은 우선순위의 큐에 있는 프로세스가 높은 우선순위의 큐가 계속 바쁘면 실행되지 못하는 상황이 발생할 수 있습니다.
2. 복잡성 증가: 큐의 수와 각 큐의 스케줄링 알고리즘을 설계하는 데 추가적인 복잡성이 요구됩니다.
3. 유휴 시간 발생 가능성: 특정 큐가 비어 있는 동안 다른 큐가 프로세스를 대기 중이라면 CPU가 유휴 상태가 될 수 있습니다.

사용 시 주의사항

• 각 큐의 우선순위 설정과 작업 분류 기준을 명확히 정의해야 합니다.
• 기아 문제를 방지하기 위해 낮은 우선순위 프로세스에도 실행 기회를 주는 메커니즘(예: Aging)을 도입할 수 있습니다.

멀티레벨 큐 스케줄링은 장점이 많은 알고리즘이지만, 단점과 한계를 명확히 이해하고 적절히 설계해야 효과적으로 활용할 수 있습니다.

구현을 위한 필수 개념

프로세스

프로세스는 실행 중인 프로그램의 인스턴스를 의미하며, 멀티레벨 큐 스케줄링에서 프로세스는 스케줄링 대상이 됩니다. 프로세스는 다음과 같은 주요 속성을 가집니다:

• 프로세스 ID: 각 프로세스를 식별하는 고유한 값.
• 우선순위: 프로세스가 배치될 큐를 결정하는 기준.
• 상태: 실행 중, 대기 중, 준비 상태 등의 현재 상태.

큐

큐는 프로세스가 정렬되어 처리되는 데이터 구조로, 멀티레벨 큐 스케줄링에서 중요한 역할을 합니다.

• FIFO 구조: 큐는 일반적으로 선입선출(FIFO) 방식으로 작동합니다.
• 다중 큐: 프로세스 특성에 따라 여러 개의 큐가 존재하며, 각 큐는 독립적으로 관리됩니다.

우선순위

우선순위는 프로세스를 어떤 큐에 배치할지 결정하는 기준입니다.

• 높은 우선순위의 프로세스는 빠르게 처리됩니다.
• 우선순위는 프로세스 유형(예: 실시간, 백그라운드)이나 중요도에 따라 설정됩니다.

스케줄링 알고리즘

멀티레벨 큐 스케줄링에서는 각 큐가 서로 다른 스케줄링 알고리즘을 사용할 수 있습니다.

• FCFS(First-Come, First-Served): 큐에 들어온 순서대로 프로세스를 처리합니다.
• Round Robin: 시간 할당량에 따라 프로세스를 순환하며 처리합니다.
• 우선순위 기반 스케줄링: 프로세스의 우선순위에 따라 실행 순서를 결정합니다.

필수 고려사항

• 큐 간 스케줄링: 각 큐 간 우선순위를 설정하여 실행 순서를 조정해야 합니다.
• 기아 문제 방지: 낮은 우선순위 프로세스에도 실행 기회를 부여하는 Aging 등의 기술을 고려해야 합니다.

이러한 개념은 멀티레벨 큐 스케줄링 알고리즘을 구현하는 데 필수적이며, 효율적인 설계를 위해 반드시 숙지해야 합니다.

구현에 필요한 데이터 구조

프로세스 구조체

멀티레벨 큐 스케줄링을 구현하려면 프로세스를 표현하는 데이터 구조가 필요합니다. 일반적으로 C 언어에서는 struct를 사용하여 프로세스를 나타냅니다.

typedef struct {
    int id;           // 프로세스 ID
    int priority;     // 우선순위
    int burstTime;    // 실행 시간
    int arrivalTime;  // 도착 시간
} Process;

큐

프로세스를 저장하고 관리하는 큐는 선입선출(FIFO) 방식으로 작동하는 데이터 구조입니다. C 언어에서는 배열과 관련된 인덱스를 사용하여 큐를 구현하거나, 동적 메모리를 사용한 연결 리스트로 큐를 구현할 수 있습니다.

배열을 사용한 간단한 큐 구조 예제:

typedef struct {
    Process processes[100]; // 프로세스를 저장하는 배열
    int front;              // 큐의 시작 인덱스
    int rear;               // 큐의 끝 인덱스
} Queue;

다중 큐

멀티레벨 큐 스케줄링에서는 각 우선순위에 해당하는 여러 개의 큐가 필요합니다. 이를 구현하기 위해 큐 배열 또는 동적 메모리를 활용할 수 있습니다.

Queue multiLevelQueue[3]; // 우선순위별로 3개의 큐를 관리

스케줄링을 위한 헬퍼 함수

멀티레벨 큐의 작동을 위해 다음과 같은 함수들이 필요합니다:

1. 큐 초기화

   void initializeQueue(Queue* q) {
       q->front = -1;
       q->rear = -1;
   }

2. 프로세스 삽입

   void enqueue(Queue* q, Process p) {
       if (q->rear == 99) {
           printf("Queue is full\n");
           return;
       }
       if (q->front == -1) q->front = 0;
       q->processes[++q->rear] = p;
   }

3. 프로세스 삭제

   Process dequeue(Queue* q) {
       if (q->front == -1 || q->front > q->rear) {
           printf("Queue is empty\n");
           Process nullProcess = {-1, -1, -1, -1};
           return nullProcess;
       }
       return q->processes[q->front++];
   }

스케줄러

스케줄러는 다중 큐에서 프로세스를 선택하고 CPU에 할당하는 역할을 합니다.

• 큐 간 우선순위를 기반으로 프로세스를 선택합니다.
• 선택한 프로세스를 실행하거나 대기 상태로 전환합니다.

예제 스케줄러 함수:

void schedule(Queue queues[], int numQueues) {
    for (int i = 0; i < numQueues; i++) {
        while (queues[i].front <= queues[i].rear) {
            Process p = dequeue(&queues[i]);
            printf("Executing process %d from queue %d\n", p.id, i);
            // 실행 로직 구현
        }
    }
}

이 데이터 구조와 헬퍼 함수들은 멀티레벨 큐 스케줄링 알고리즘의 기반을 제공합니다.

C 코드로 구현하기

아래는 멀티레벨 큐 스케줄링을 구현한 C 코드의 예제입니다. 이 코드는 프로세스를 우선순위별로 나누어 큐에 삽입하고, 각 큐의 우선순위에 따라 프로세스를 실행합니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESSES 100
#define NUM_QUEUES 3 // 큐의 수 (우선순위 레벨)

typedef struct {
    int id;           // 프로세스 ID
    int priority;     // 우선순위 (0: 높음, 1: 중간, 2: 낮음)
    int burstTime;    // 실행 시간
} Process;

typedef struct {
    Process processes[MAX_PROCESSES];
    int front;
    int rear;
} Queue;

// 큐 초기화
void initializeQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// 큐에 프로세스 삽입
void enqueue(Queue* q, Process p) {
    if (q->rear == MAX_PROCESSES - 1) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) q->front = 0;
    q->processes[++q->rear] = p;
}

// 큐에서 프로세스 제거
Process dequeue(Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue is empty\n");
        Process nullProcess = {-1, -1, -1};
        return nullProcess;
    }
    return q->processes[q->front++];
}

// 프로세스 실행 시뮬레이션
void executeProcess(Process p) {
    printf("Executing Process ID: %d, Priority: %d, Burst Time: %d\n", p.id, p.priority, p.burstTime);
    for (int i = 0; i < p.burstTime; i++) {
        printf(".");
    }
    printf("\nProcess %d completed.\n", p.id);
}

// 스케줄링 함수
void schedule(Queue queues[], int numQueues) {
    for (int i = 0; i < numQueues; i++) {
        printf("\nScheduling queue with priority %d:\n", i);
        while (queues[i].front <= queues[i].rear) {
            Process p = dequeue(&queues[i]);
            executeProcess(p);
        }
    }
}

int main() {
    Queue queues[NUM_QUEUES];
    for (int i = 0; i < NUM_QUEUES; i++) {
        initializeQueue(&queues[i]);
    }

    // 프로세스 생성
    Process processes[] = {
        {1, 0, 5}, // ID 1, 우선순위 0, 실행 시간 5
        {2, 1, 3}, // ID 2, 우선순위 1, 실행 시간 3
        {3, 2, 2}, // ID 3, 우선순위 2, 실행 시간 2
        {4, 0, 4}, // ID 4, 우선순위 0, 실행 시간 4
        {5, 1, 6}  // ID 5, 우선순위 1, 실행 시간 6
    };

    // 프로세스를 우선순위별 큐에 삽입
    for (int i = 0; i < 5; i++) {
        enqueue(&queues[processes[i].priority], processes[i]);
    }

    // 스케줄링 실행
    schedule(queues, NUM_QUEUES);

    return 0;
}

코드 설명

1. Process 구조체

• 프로세스를 표현하며 ID, 우선순위, 실행 시간을 포함합니다.

1. Queue 구조체

• 프로세스를 저장하며 FIFO 방식으로 작동합니다.

1. enqueue() 및 dequeue()

• 프로세스를 큐에 삽입하고 제거하는 함수입니다.

1. schedule()

• 높은 우선순위 큐부터 프로세스를 실행하며 각 프로세스를 시뮬레이션합니다.

1. main()

• 프로세스를 생성하고 큐에 삽입한 후, 스케줄링을 실행합니다.

실행 결과 예시

Scheduling queue with priority 0:
Executing Process ID: 1, Priority: 0, Burst Time: 5
.....
Process 1 completed.
Executing Process ID: 4, Priority: 0, Burst Time: 4
....

Scheduling queue with priority 1:
Executing Process ID: 2, Priority: 1, Burst Time: 3
...
Executing Process ID: 5, Priority: 1, Burst Time: 6
......

Scheduling queue with priority 2:
Executing Process ID: 3, Priority: 2, Burst Time: 2
..
Process 3 completed.

이 코드는 멀티레벨 큐 스케줄링의 기본 구조를 보여주며, 이를 확장해 다양한 요구사항에 맞게 커스터마이징할 수 있습니다.

코드 분석과 실행 결과

코드 분석

1. 프로세스 및 큐 데이터 구조

• Process 구조체는 각 프로세스의 정보를 저장하며, 프로세스 ID, 우선순위, 실행 시간을 포함합니다.
• Queue 구조체는 프로세스를 FIFO 방식으로 관리하며, 각 우선순위에 해당하는 프로세스를 저장합니다.

1. 헬퍼 함수

• enqueue(): 큐에 프로세스를 추가합니다. 큐가 꽉 찼는지 검사하고, 그렇지 않다면 프로세스를 삽입합니다.
• dequeue(): 큐에서 프로세스를 제거합니다. 큐가 비어 있는지 확인하고, 비어 있지 않으면 프로세스를 반환합니다.
• executeProcess(): 프로세스를 시뮬레이션하며 실행 과정을 콘솔에 출력합니다.

1. 스케줄링 로직

• schedule() 함수는 우선순위가 높은 큐부터 순차적으로 프로세스를 실행합니다.
• 큐가 비어 있지 않은 동안 dequeue()를 호출하여 프로세스를 가져오고 실행합니다.

1. main 함수

• 초기화: 각 우선순위 큐를 초기화합니다.
• 프로세스 생성: 다양한 우선순위와 실행 시간을 가진 프로세스를 생성합니다.
• 프로세스 삽입: 프로세스를 해당 우선순위 큐에 삽입합니다.
• 스케줄링 실행: schedule() 함수를 호출하여 모든 프로세스를 실행합니다.

실행 결과

프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다:

Scheduling queue with priority 0:
Executing Process ID: 1, Priority: 0, Burst Time: 5
.....
Process 1 completed.
Executing Process ID: 4, Priority: 0, Burst Time: 4
....

Scheduling queue with priority 1:
Executing Process ID: 2, Priority: 1, Burst Time: 3
...
Executing Process ID: 5, Priority: 1, Burst Time: 6
......

Scheduling queue with priority 2:
Executing Process ID: 3, Priority: 2, Burst Time: 2
..
Process 3 completed.

• 우선순위별 처리: 높은 우선순위 큐의 프로세스가 먼저 처리됩니다.
• 큐 내부 처리 순서: 각 큐는 FIFO 순서에 따라 프로세스를 처리합니다.

결과 분석

1. 우선순위 기반 스케줄링 확인

• 높은 우선순위(0)에 있는 프로세스가 먼저 실행되었습니다.
• 동일한 우선순위의 프로세스는 도착 순서에 따라 실행되었습니다.

1. 다양한 우선순위와 실행 시간 시뮬레이션

• 프로세스별 실행 시간이 정확히 반영되었습니다.
• 각 큐의 프로세스가 순차적으로 실행되었습니다.

1. CPU 활용 최적화

• 각 큐의 프로세스가 모두 처리되며, CPU가 효율적으로 사용되었습니다.

이 코드는 멀티레벨 큐 스케줄링 알고리즘을 효과적으로 시뮬레이션하며, 추가적인 기능(예: Aging, 동적 우선순위 조정)을 구현하는 기반이 될 수 있습니다.

문제 해결 및 확장 아이디어

문제 해결

1. 기아 문제(Starvation)

• 문제: 낮은 우선순위 큐의 프로세스가 높은 우선순위 큐에 의해 계속 실행되지 못하는 상황이 발생할 수 있습니다.
• 해결 방법: Aging 기법을 도입하여 시간이 지남에 따라 낮은 우선순위 프로세스의 우선순위를 점진적으로 높이는 방식을 사용합니다.

   void applyAging(Queue queues[], int numQueues) {
       for (int i = numQueues - 1; i > 0; i--) { // 낮은 우선순위 큐부터 검사
           for (int j = queues[i].front; j <= queues[i].rear; j++) {
               queues[i].processes[j].priority--;
               if (queues[i].processes[j].priority < 0) {
                   Process agedProcess = dequeue(&queues[i]);
                   enqueue(&queues[i - 1], agedProcess); // 높은 우선순위 큐로 이동
               }
           }
       }
   }

2. 큐 오버플로우

• 문제: 큐의 크기를 초과하여 프로세스를 삽입하려고 하면 프로그램이 중단될 수 있습니다.
• 해결 방법: 큐 크기를 동적으로 확장하거나 큐가 가득 찬 경우 대기 목록을 별도로 두어 관리합니다.

2. CPU 유휴 시간

• 문제: 모든 큐가 비어 있는 경우 CPU가 유휴 상태가 됩니다.
• 해결 방법: 대기 상태에 있는 프로세스를 관리하여 CPU 유휴 시간을 최소화하는 로직을 추가합니다.
• 예: 일정 시간 동안 큐가 비어 있으면 낮은 우선순위 프로세스를 임시로 실행합니다.

확장 아이디어

1. 동적 우선순위 조정

• 프로세스의 실행 상황에 따라 우선순위를 실시간으로 조정하는 기능을 추가합니다.
• 예: 프로세스가 반복적으로 CPU를 사용하지 않거나 대기 시간이 길 경우 우선순위를 증가시킵니다.

1. I/O 대기 및 병렬 처리 지원

• I/O 작업 중인 프로세스를 대기 큐에 넣고, 다른 프로세스를 실행하는 기능을 추가합니다.
• 예: 별도의 I/O 큐를 추가하고, 멀티스레딩을 도입해 CPU와 I/O를 병렬 처리합니다.

1. 사용자 정의 스케줄링 정책 지원

• 사용자가 각 큐의 스케줄링 알고리즘(예: FCFS, Round Robin)을 동적으로 변경할 수 있도록 인터페이스를 제공합니다.
• 예: 사용자 입력에 따라 특정 큐에서 사용하는 알고리즘을 변경합니다.

1. 모니터링 및 디버깅 툴

• 각 큐와 프로세스의 상태를 실시간으로 출력하여 스케줄링 과정을 시각적으로 확인할 수 있는 기능을 추가합니다.
• 예: GUI 기반 프로세스 시뮬레이터를 개발하여 프로세스 이동과 실행 상태를 시각화합니다.

1. 다양한 환경 테스트

• 실시간 시스템이나 서버와 같은 실제 환경을 시뮬레이션하여 스케줄링 알고리즘의 성능을 측정합니다.
• 예: 대규모 프로세스를 생성하고 처리 시간, 대기 시간, CPU 사용률 등을 분석합니다.

예상 결과

이러한 문제 해결과 확장 아이디어를 적용하면 멀티레벨 큐 스케줄링의 효율성이 향상되고, 실제 시스템에서 발생할 수 있는 다양한 상황에 유연하게 대응할 수 있습니다. 이는 알고리즘을 학습하는 데에도 유용하며, 실전 프로젝트에서도 실질적인 가치를 제공합니다.

응용 예제와 연습 문제

응용 예제

멀티레벨 큐 스케줄링을 확장하여 실시간 및 비실시간 작업을 혼합한 환경에서의 스케줄링을 구현해 보세요. 아래는 기본 코드에 새로운 요구사항을 추가한 예입니다.

요구사항

1. 실시간 프로세스(우선순위 0)는 지정된 기한 내에 반드시 완료되어야 합니다.
2. 비실시간 프로세스(우선순위 1, 2)는 Round Robin 알고리즘을 사용하여 공정하게 처리됩니다.
3. 기한이 초과된 실시간 프로세스는 시스템 로그에 기록됩니다.

추가 코드 예제

void executeRealTimeProcess(Process p, int currentTime) {
    if (currentTime + p.burstTime <= p.arrivalTime + 10) { // 기한 10단위로 가정
        printf("Executing Real-Time Process ID: %d\n", p.id);
    } else {
        printf("Process ID %d missed its deadline!\n", p.id);
    }
}

이 코드를 멀티레벨 큐 스케줄링과 통합하여 실시간 프로세스와 비실시간 프로세스를 함께 처리하도록 설계해 보세요.

연습 문제

1. 큐 간 프로세스 이동

• Aging을 구현하여 낮은 우선순위 큐의 프로세스가 일정 시간 이후 높은 우선순위 큐로 이동하도록 코드를 작성하세요.

1. I/O 대기 처리

• I/O 작업을 수행하는 프로세스를 별도의 대기 큐에 저장하고, 완료 후 다시 적절한 우선순위 큐로 반환하는 기능을 구현하세요.

1. 성능 분석

• 100개의 프로세스를 생성하여 각 우선순위 큐에서의 평균 대기 시간과 처리 시간을 측정하고 분석하세요.

1. 커스터마이징 가능 스케줄링

• 사용자가 각 큐의 스케줄링 알고리즘을 선택할 수 있도록 인터페이스를 추가하세요.
• 예: 사용자가 Round Robin, FCFS, 또는 우선순위 기반 스케줄링 중 하나를 선택하도록 합니다.

1. 멀티스레드 환경 구현

• 멀티스레드를 사용하여 각 큐를 병렬로 실행하는 환경을 구현하세요. 이를 통해 멀티코어 CPU의 성능을 활용하도록 설계하세요.

도전 과제

• 동적 프로세스 생성: 프로그램 실행 중 임의의 시간에 새로운 프로세스를 생성하고 적절한 큐에 삽입하는 기능을 추가하세요.
• 통합 모니터링 시스템: 각 큐의 상태와 프로세스의 실행 상황을 시각적으로 표현하는 텍스트 기반 대시보드를 구현하세요.

이 응용 예제와 연습 문제를 통해 멀티레벨 큐 스케줄링 알고리즘의 원리를 깊이 이해하고 실제 구현 능력을 향상시킬 수 있습니다.