C언어로 배우는 프로세스 스케줄링과 큐 활용법

C언어에서 프로세스 스케줄링 알고리즘을 구현하는 것은 운영 체제의 핵심 개념을 이해하는 데 중요한 역할을 합니다. 특히, 큐 자료구조는 FCFS(First-Come, First-Served)와 같은 기본 스케줄링 방식뿐만 아니라 Round Robin과 같은 복잡한 알고리즘에서도 필수적으로 사용됩니다. 본 기사에서는 C언어를 활용하여 큐 자료구조를 구현하고, 이를 바탕으로 프로세스 스케줄링 알고리즘을 설계하고 디버깅하는 방법을 단계별로 설명합니다. 이를 통해 독자들이 큐의 활용성을 이해하고, 스케줄링 알고리즘의 작동 원리를 깊이 파악할 수 있도록 돕겠습니다.

큐 자료구조의 기본 개념

큐(Queue)는 데이터를 순차적으로 처리하기 위한 자료구조로, FIFO(First-In, First-Out) 원칙을 따릅니다. 이는 가장 먼저 들어온 데이터가 가장 먼저 처리되는 구조를 의미합니다. 큐는 프로세스 스케줄링과 같은 상황에서 작업 순서를 효율적으로 관리하는 데 유용합니다.

큐의 특징

삽입(Enqueue): 큐의 끝에서 데이터를 추가합니다.
삭제(Dequeue): 큐의 앞에서 데이터를 제거합니다.
순서 유지: 들어온 순서대로 처리합니다.

큐의 종류

선형 큐: 단순 배열 형태로 구현되며, 기본 큐의 개념을 충실히 따릅니다.
원형 큐: 배열의 끝이 다시 처음으로 연결되어 공간 낭비를 줄이는 큐입니다.
우선순위 큐: 각 데이터가 우선순위를 가지며, 우선순위에 따라 처리 순서가 결정됩니다.

활용 사례

큐는 운영 체제에서 프로세스 스케줄링뿐만 아니라, 네트워크 패킷 처리, 데이터 버퍼 관리 등 다양한 영역에서 활용됩니다. 이를 통해 작업 순서를 체계적으로 관리하고 효율성을 높일 수 있습니다.

프로세스 스케줄링이란 무엇인가

프로세스 스케줄링은 운영 체제가 CPU와 같은 시스템 자원을 여러 프로세스 간에 효율적으로 분배하는 메커니즘입니다. 이는 시스템 성능을 극대화하고, 사용자 경험을 향상시키는 데 핵심적인 역할을 합니다.

스케줄링의 주요 목표

효율성: CPU와 메모리 자원을 최대한 활용합니다.
공정성: 모든 프로세스가 자원을 균등하게 사용할 수 있도록 보장합니다.
응답 시간 최소화: 사용자 요청에 대한 반응 시간을 줄입니다.
처리량 최대화: 단위 시간 내 최대한 많은 작업을 완료합니다.

스케줄링의 유형

선점형 스케줄링: 프로세스가 실행 중일 때 더 높은 우선순위의 프로세스가 자원을 가져갈 수 있습니다.

예: Round Robin, Shortest Remaining Time First(SRTF)

비선점형 스케줄링: 프로세스가 자원을 다 사용한 후에야 다른 프로세스로 전환됩니다.

예: FCFS(First-Come, First-Served), SJF(Shortest Job First)

프로세스 스케줄링의 역할

운영 체제는 프로세스를 관리하기 위해 스케줄링 큐를 사용합니다. 이 큐는 준비 상태의 프로세스, 대기 상태의 프로세스 등을 관리하며, 스케줄링 알고리즘은 각 프로세스가 언제 실행될지를 결정합니다.

프로세스 스케줄링은 시스템 자원의 효율성을 극대화하고, 동시에 다양한 작업 간의 균형을 맞추는 중요한 도구입니다. C언어를 통해 스케줄링 알고리즘을 구현함으로써 이 개념을 실질적으로 이해할 수 있습니다.

큐를 이용한 스케줄링 방식

큐 자료구조는 프로세스 스케줄링에서 핵심적인 역할을 하며, 작업 순서를 효율적으로 관리합니다. 특히, FCFS(First-Come, First-Served)와 RR(Round Robin) 알고리즘은 큐의 FIFO 특성을 활용하여 구현됩니다.

FCFS(First-Come, First-Served) 스케줄링

원리: 가장 먼저 큐에 들어온 프로세스를 먼저 실행합니다.
특징:
단순하고 구현이 쉽습니다.
공정성은 보장되지만, 긴 작업이 먼저 들어올 경우 다음 작업이 지연되는 Convoy Effect가 발생할 수 있습니다.
큐 활용: 준비 큐에 프로세스를 삽입하고, 큐의 앞에서 프로세스를 하나씩 제거하며 실행합니다.

Round Robin(RR) 스케줄링

원리: 각 프로세스가 고정된 시간 간격(타임 슬라이스) 동안 CPU를 할당받습니다.
특징:
공정성이 높으며, 사용자 응답 시간이 향상됩니다.
타임 슬라이스 크기에 따라 성능이 달라질 수 있습니다.
큐 활용:
프로세스는 큐의 끝에 추가되며, 타임 슬라이스가 끝나면 다시 큐의 끝으로 이동합니다.

큐 자료구조의 스케줄링 적용 예시

프로세스가 도착하면 준비 큐에 삽입됩니다.
스케줄링 알고리즘은 큐의 앞에서 프로세스를 선택하여 실행합니다.
실행이 완료되거나 타임 슬라이스가 종료되면, 해당 프로세스를 큐에서 제거하거나 재삽입합니다.

큐를 활용한 스케줄링 방식은 간결한 논리 구조로 구현할 수 있어 학습과 실무 모두에서 널리 사용됩니다.

C언어에서 큐 자료구조 구현하기

C언어를 사용하여 큐 자료구조를 구현하면 프로세스 스케줄링 알고리즘을 더 잘 이해할 수 있습니다. 아래는 배열을 사용한 큐의 기본 구현 예시입니다.

큐 구현의 주요 구성 요소

배열: 큐의 데이터를 저장합니다.
전단(front): 큐에서 데이터를 제거하는 위치를 가리킵니다.
후단(rear): 큐에 데이터를 추가하는 위치를 가리킵니다.
크기 제한(size): 큐가 사용할 수 있는 최대 공간을 설정합니다.

배열 기반 큐 구현

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

#define MAX_SIZE 100  // 큐의 최대 크기

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

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

// 큐가 비어 있는지 확인
int isEmpty(Queue* q) {
    return q->front > q->rear;
}

// 큐가 가득 찼는지 확인
int isFull(Queue* q) {
    return q->rear == MAX_SIZE - 1;
}

// 데이터 삽입
void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    q->data[++(q->rear)] = value;
}

// 데이터 제거
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->data[(q->front)++];
}

// 큐의 맨 앞 데이터 확인
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->data[q->front];
}

// 큐 상태 출력
void displayQueue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Queue elements: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->data[i]);
    }
    printf("\n");
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    displayQueue(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    displayQueue(&q);

    printf("Peek: %d\n", peek(&q));
    return 0;
}

구현 코드 설명

initQueue: 큐를 초기화합니다.
isEmpty 및 isFull: 큐 상태를 확인합니다.
enqueue: 큐에 데이터를 추가하며, 후단(rear)을 업데이트합니다.
dequeue: 데이터를 제거하며, 전단(front)을 업데이트합니다.
peek 및 displayQueue: 큐의 현재 상태를 확인하고 출력합니다.

이 코드는 기본적인 선형 큐의 동작 원리를 이해하고, 이를 활용하여 다양한 스케줄링 알고리즘을 구현하는 데 도움을 줍니다.

FCFS 스케줄링 알고리즘 구현

FCFS(First-Come, First-Served) 스케줄링은 큐 자료구조를 활용하여 가장 먼저 도착한 프로세스를 먼저 실행하는 방식으로 작동합니다. 아래는 C언어를 사용하여 FCFS 스케줄링 알고리즘을 구현하는 방법을 보여줍니다.

FCFS 스케줄링 알고리즘 코드

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

// 프로세스 구조체 정의
typedef struct {
    int pid;      // 프로세스 ID
    int arrival;  // 도착 시간
    int burst;    // 실행 시간
} Process;

// 프로세스를 정렬하기 위한 비교 함수 (도착 시간 기준)
int compare(const void* a, const void* b) {
    Process* p1 = (Process*)a;
    Process* p2 = (Process*)b;
    return p1->arrival - p2->arrival;
}

// FCFS 스케줄링 알고리즘 구현
void fcfsScheduling(Process processes[], int n) {
    int waitTime[n], turnaroundTime[n];
    int totalWait = 0, totalTurnaround = 0;

    // 첫 번째 프로세스 처리
    waitTime[0] = 0;  // 첫 프로세스는 대기 시간이 0
    turnaroundTime[0] = processes[0].burst;

    // 나머지 프로세스 처리
    for (int i = 1; i < n; i++) {
        waitTime[i] = waitTime[i - 1] + processes[i - 1].burst;
        turnaroundTime[i] = waitTime[i] + processes[i].burst;
    }

    // 결과 출력
    printf("\nFCFS Scheduling Results:\n");
    printf("PID\tArrival\tBurst\tWait\tTurnaround\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\t%d\t%d\n", processes[i].pid, processes[i].arrival,
               processes[i].burst, waitTime[i], turnaroundTime[i]);
        totalWait += waitTime[i];
        totalTurnaround += turnaroundTime[i];
    }

    printf("\nAverage Waiting Time: %.2f\n", (float)totalWait / n);
    printf("Average Turnaround Time: %.2f\n", (float)totalTurnaround / n);
}

int main() {
    int n;

    printf("Enter the number of processes: ");
    scanf("%d", &n);

    Process processes[n];
    for (int i = 0; i < n; i++) {
        printf("Enter arrival time and burst time for process %d: ", i + 1);
        processes[i].pid = i + 1;
        scanf("%d %d", &processes[i].arrival, &processes[i].burst);
    }

    // 도착 시간 기준으로 정렬
    qsort(processes, n, sizeof(Process), compare);

    // FCFS 스케줄링 수행
    fcfsScheduling(processes, n);

    return 0;
}

코드 실행 흐름

프로세스 입력: 프로세스 ID, 도착 시간, 실행 시간을 사용자로부터 입력받습니다.
정렬: 도착 시간 기준으로 프로세스를 정렬합니다.
대기 시간 계산: 이전 프로세스의 실행 시간 합계를 사용하여 각 프로세스의 대기 시간을 계산합니다.
반환 시간 계산: 대기 시간과 실행 시간을 더하여 반환 시간을 계산합니다.
결과 출력: 각 프로세스의 대기 시간, 반환 시간, 평균 시간 등을 출력합니다.

FCFS의 장단점

장점:
구현이 간단하고 직관적입니다.
선점이 없으므로 프로세스가 중단되지 않습니다.
단점:
긴 프로세스가 먼저 도착하면 짧은 프로세스가 지연되는 Convoy Effect가 발생합니다.

이 코드는 FCFS의 원리를 이해하는 데 도움을 주며, 큐를 사용하여 효율적으로 구현된 프로세스 스케줄링 알고리즘의 기본 형태를 보여줍니다.

Round Robin 알고리즘 구현

Round Robin(RR) 스케줄링은 각 프로세스가 고정된 시간 간격(타임 슬라이스) 동안 CPU를 사용하도록 하는 방식으로, 선점형 스케줄링의 대표적인 알고리즘입니다. 큐 자료구조를 활용하여 구현되며, 공정성과 응답성을 높이는 데 주로 사용됩니다.

Round Robin 스케줄링 알고리즘 코드

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

typedef struct {
    int pid;      // 프로세스 ID
    int arrival;  // 도착 시간
    int burst;    // 실행 시간
    int remaining; // 남은 실행 시간
} Process;

// Round Robin 스케줄링 알고리즘
void roundRobinScheduling(Process processes[], int n, int timeQuantum) {
    int currentTime = 0, completed = 0;
    int waitTime[n], turnaroundTime[n];
    int totalWait = 0, totalTurnaround = 0;
    int queue[n], front = 0, rear = 0;

    // 큐에 첫 프로세스 추가
    for (int i = 0; i < n; i++) {
        processes[i].remaining = processes[i].burst;
        queue[rear++] = i; // 프로세스 인덱스 삽입
    }

    while (completed < n) {
        int index = queue[front++];
        if (front == n) front = 0; // 원형 큐처럼 동작

        // 현재 프로세스 실행
        if (processes[index].remaining > 0) {
            if (processes[index].remaining > timeQuantum) {
                currentTime += timeQuantum;
                processes[index].remaining -= timeQuantum;
            } else {
                currentTime += processes[index].remaining;
                processes[index].remaining = 0;
                completed++;
                turnaroundTime[index] = currentTime - processes[index].arrival;
                waitTime[index] = turnaroundTime[index] - processes[index].burst;
            }

            // 아직 실행이 남은 경우 큐에 다시 삽입
            if (processes[index].remaining > 0) {
                queue[rear++] = index;
                if (rear == n) rear = 0; // 원형 큐처럼 동작
            }
        }
    }

    // 결과 출력
    printf("\nRound Robin Scheduling Results:\n");
    printf("PID\tArrival\tBurst\tWait\tTurnaround\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\t%d\t%d\n", processes[i].pid, processes[i].arrival,
               processes[i].burst, waitTime[i], turnaroundTime[i]);
        totalWait += waitTime[i];
        totalTurnaround += turnaroundTime[i];
    }

    printf("\nAverage Waiting Time: %.2f\n", (float)totalWait / n);
    printf("Average Turnaround Time: %.2f\n", (float)totalTurnaround / n);
}

int main() {
    int n, timeQuantum;

    printf("Enter the number of processes: ");
    scanf("%d", &n);

    Process processes[n];
    for (int i = 0; i < n; i++) {
        printf("Enter arrival time and burst time for process %d: ", i + 1);
        processes[i].pid = i + 1;
        scanf("%d %d", &processes[i].arrival, &processes[i].burst);
    }

    printf("Enter the time quantum: ");
    scanf("%d", &timeQuantum);

    roundRobinScheduling(processes, n, timeQuantum);

    return 0;
}

코드 실행 흐름

입력: 사용자로부터 프로세스 정보(도착 시간, 실행 시간)와 타임 슬라이스 값을 입력받습니다.
큐 초기화: 프로세스 인덱스를 큐에 삽입합니다.
타임 슬라이스 실행: 각 프로세스는 타임 슬라이스 동안 실행되고, 남은 시간이 있으면 큐의 끝으로 이동합니다.
대기 시간 및 반환 시간 계산: 프로세스가 종료될 때 대기 시간과 반환 시간을 계산합니다.
출력: 모든 프로세스의 결과와 평균 대기 시간, 반환 시간을 출력합니다.

Round Robin의 장단점

장점:
공정성: 모든 프로세스가 동일한 CPU 시간을 보장받습니다.
응답성 향상: 긴 작업도 짧은 주기로 계속 실행됩니다.
단점:
타임 슬라이스 크기 설정이 중요합니다.
- 너무 크면 FCFS와 유사해지고,
- 너무 작으면 오버헤드가 증가합니다.

이 코드는 Round Robin 스케줄링의 실질적인 동작을 보여주며, 큐 자료구조를 활용한 선점형 스케줄링의 구현 방식을 이해하는 데 도움을 줍니다.

디버깅 및 문제 해결 팁

큐를 기반으로 한 프로세스 스케줄링 알고리즘을 구현할 때, 예상치 못한 문제나 오류가 발생할 수 있습니다. 아래는 주요 문제와 이를 해결하기 위한 디버깅 팁을 소개합니다.

1. 큐 오버플로우 및 언더플로우

문제: 큐의 크기를 초과하여 데이터를 삽입하거나, 비어 있는 큐에서 데이터를 제거하려는 경우 발생합니다.
해결 방법:

큐의 상태를 확인하는 함수를 사용해 오버플로우와 언더플로우를 방지합니다.
예: isFull 및 isEmpty 함수를 적절히 활용합니다.

예시 코드

if (isFull(&queue)) {
    printf("Queue overflow error!\n");
} else {
    enqueue(&queue, process);
}

if (isEmpty(&queue)) {
    printf("Queue underflow error!\n");
} else {
    dequeue(&queue);
}

2. 타임 슬라이스 계산 오류

문제: Round Robin 알고리즘에서 남은 실행 시간과 타임 슬라이스를 정확히 처리하지 않으면 잘못된 결과가 발생합니다.
해결 방법:

타임 슬라이스가 프로세스의 남은 실행 시간보다 크거나 작은 경우를 정확히 처리합니다.
조건문으로 타임 슬라이스와 남은 시간을 비교하여 계산합니다.

예시 코드

if (remainingTime > timeQuantum) {
    currentTime += timeQuantum;
    remainingTime -= timeQuantum;
} else {
    currentTime += remainingTime;
    remainingTime = 0;
}

3. 큐 인덱스 관리 문제

문제: 큐의 전단(front)과 후단(rear)이 동기화되지 않거나, 원형 큐에서 인덱스가 초과 또는 부족할 경우 발생합니다.
해결 방법:

원형 큐를 사용할 경우, 인덱스를 큐의 크기로 나눈 나머지 값으로 관리합니다.
큐의 상태를 적절히 업데이트합니다.

예시 코드

rear = (rear + 1) % MAX_SIZE;
front = (front + 1) % MAX_SIZE;

4. 결과 계산 오류

문제: 대기 시간 및 반환 시간 계산이 잘못되면 잘못된 평균 값이 출력됩니다.
해결 방법:

각 프로세스의 도착 시간, 실행 시간, 종료 시간을 기반으로 계산합니다.
계산 수식을 명확히 확인하고, 디버깅 로그를 추가합니다.

예시 디버깅 로그

printf("Process %d - Wait: %d, Turnaround: %d\n", process.pid, waitTime, turnaroundTime);

5. 코드 유지보수성 문제

문제: 스케줄링 알고리즘 코드가 복잡해지고, 다른 알고리즘과 혼동될 수 있습니다.
해결 방법:

큐 관리 코드와 스케줄링 로직을 별도 함수로 분리합니다.
명확한 함수 이름과 주석을 사용하여 코드 가독성을 향상시킵니다.

추가 팁

디버깅 도구 사용: GDB와 같은 디버거를 활용하여 단계별로 프로그램의 상태를 확인합니다.
테스트 케이스 작성: 다양한 프로세스 도착 시간 및 실행 시간을 포함하는 테스트 케이스를 작성하여 코드의 신뢰성을 높입니다.
로그 파일 저장: 프로그램의 실행 로그를 파일에 저장해 문제 발생 시 참조합니다.

이 디버깅 및 문제 해결 팁은 스케줄링 알고리즘 구현 과정에서 발생할 수 있는 오류를 방지하고, 보다 안정적인 코드를 작성하는 데 도움이 됩니다.

응용 예시 및 연습 문제

프로세스 스케줄링과 큐 자료구조를 실무에 활용하려면 다양한 상황에 대한 응용과 연습이 필요합니다. 아래는 큐 기반 스케줄링의 실질적인 응용 사례와 독자가 도전할 수 있는 연습 문제를 소개합니다.

응용 예시

1. 실시간 작업 스케줄링

실시간 시스템에서는 프로세스가 정해진 시간 안에 실행되어야 합니다. Round Robin 알고리즘은 이러한 환경에서 우선순위가 낮은 작업도 정기적으로 실행되도록 보장합니다.
예시: 네트워크 패킷 처리에서 패킷이 순차적으로 처리되며, 각 패킷이 정해진 시간 동안만 대기하도록 Round Robin을 사용합니다.

2. 다중 사용자 운영 체제

다중 사용자 환경에서 각 사용자의 프로세스가 CPU를 공정하게 할당받아야 합니다. Round Robin 알고리즘은 이를 효율적으로 지원하며, 큐를 사용하여 프로세스를 관리합니다.
예시: 온라인 학습 플랫폼에서 각 사용자의 요청이 처리 대기열을 통해 공정하게 관리됩니다.

3. 데이터 스트림 처리

연속적으로 도착하는 데이터 스트림을 큐를 통해 관리하며, 각 데이터 청크가 순차적으로 처리되도록 Round Robin 스케줄링이 사용됩니다.
예시: 비디오 스트리밍 서버에서 버퍼 큐를 활용하여 사용자 요청을 처리합니다.

연습 문제

1. 큐 기반 FCFS 구현

문제: FCFS 스케줄링을 구현하여 다음 프로세스의 대기 시간과 반환 시간을 계산하시오.

프로세스: P1(도착 시간: 0, 실행 시간: 5), P2(도착 시간: 1, 실행 시간: 3), P3(도착 시간: 2, 실행 시간: 8)

목표:

각 프로세스의 대기 시간과 반환 시간을 계산합니다.
평균 대기 시간과 반환 시간을 출력합니다.

2. 타임 슬라이스 조정 Round Robin

문제: 주어진 타임 슬라이스(2ms)를 사용하는 Round Robin 알고리즘을 구현하시오.

프로세스: P1(도착 시간: 0, 실행 시간: 6), P2(도착 시간: 2, 실행 시간: 4), P3(도착 시간: 4, 실행 시간: 9)

목표:

타임 슬라이스를 기준으로 각 프로세스의 상태 변화를 추적합니다.
각 프로세스의 대기 시간과 반환 시간을 계산하고 출력합니다.

3. 원형 큐로 우선순위 스케줄링 확장

문제: 원형 큐를 사용하여 우선순위 기반 스케줄링 알고리즘을 구현하시오.

프로세스는 우선순위를 가지며, 동일 우선순위의 경우 Round Robin 방식으로 처리됩니다.

목표:

큐에서 우선순위를 기준으로 프로세스를 관리합니다.
높은 우선순위의 프로세스가 먼저 실행되도록 구현합니다.

문제 풀이 방향

문제에서 제공된 프로세스 데이터를 사용하여 알고리즘을 단계별로 구현합니다.
결과를 출력하여 각 프로세스의 대기 시간 및 반환 시간을 확인합니다.
다양한 입력 데이터로 테스트하여 알고리즘의 안정성을 검증합니다.

응용 예시와 연습 문제를 통해 큐 자료구조와 프로세스 스케줄링 알고리즘의 실무 활용 능력을 강화할 수 있습니다.

요약

본 기사에서는 C언어를 활용한 프로세스 스케줄링 알고리즘과 큐 자료구조의 기본 개념 및 응용 방법을 다루었습니다. FCFS와 Round Robin 같은 대표적인 스케줄링 알고리즘을 큐를 사용해 구현하고, 디버깅 및 문제 해결 팁과 함께 실질적인 응용 사례를 제시했습니다. 이를 통해 큐 자료구조의 중요성과 스케줄링 알고리즘의 원리를 이해하고, 실제 프로젝트에 활용할 수 있는 실용적인 지식을 제공했습니다.