Algorithm Bakery – 온더텍

Contents

베이커리 알고리즘(Bakery Algorithm)란?

베이커리 알고리즘은 다익스트라(Edsger W. Dijkstra)가 제안한 상호 배제(Mutual Exclusion) 알고리즘으로, 여러 개의 프로세스가 임계 구역(Critical Section)에 진입할 때 공정하게 경쟁하도록 보장하는 알고리즘입니다.

이 알고리즘은 “베이커리 빵집에서 번호표를 받아 대기하는 방식” 을 모방하여 설계되었습니다.

📌 베이커리 알고리즘의 핵심 원리

각 프로세스는 자신만의 번호(Ticket)를 가져야 함.
프로세스가 임계 구역에 들어가려면 가장 작은 번호를 가진 프로세스가 먼저 들어감.
동일한 번호를 가진 경우 프로세스 ID(PID)가 작은 순서대로 우선권을 가짐.
한 번에 하나의 프로세스만 임계 구역을 실행할 수 있도록 보장.
데드락(Deadlock) 및 기아 상태(Starvation)를 방지.

📌 베이커리 알고리즘의 동작 과정

번호표를 받음:
- 프로세스는 다른 프로세스가 사용하는 번호 중 가장 큰 번호를 찾고, 그보다 1 큰 번호를 자신의 번호로 설정.
번호표 비교 후 대기:
- 모든 다른 프로세스와 비교하여 자신보다 번호가 낮은 프로세스가 있으면 대기.
- 같은 번호면 프로세스 ID가 작은 순서대로 우선순위 부여.
임계 구역 실행:
- 기다린 후 자신의 차례가 되면 임계 구역을 실행.
번호표 반납:
- 실행이 끝나면 자신의 번호를 0으로 설정하여 다른 프로세스가 진입할 수 있도록 함.

📌 C 언어로 구현된 베이커리 알고리즘

다음은 베이커리 알고리즘을 C 언어로 구현한 코드입니다.

✅ 구현 코드

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

#define NUM_THREADS 3  // 실행할 스레드 개수

int choosing[NUM_THREADS];  // 번호표를 선택하는 중인지 여부
int ticket[NUM_THREADS];    // 각 스레드의 번호표

void lock(int thread_id) {
    choosing[thread_id] = 1;

    // 현재 사용 중인 티켓 중 최대값을 찾아 1 증가시킴
    int max_ticket = 0;
    for (int i = 0; i < NUM_THREADS; i++) {
        if (ticket[i] > max_ticket) {
            max_ticket = ticket[i];
        }
    }
    ticket[thread_id] = max_ticket + 1;
    choosing[thread_id] = 0;

    // 다른 모든 스레드와 비교하여 순서를 기다림
    for (int i = 0; i < NUM_THREADS; i++) {
        if (i == thread_id) continue;

        // 상대방이 번호를 고르는 중이면 기다림
        while (choosing[i]);

        // 상대방이 나보다 번호가 작거나, 번호가 같지만 ID가 나보다 작으면 기다림
        while (ticket[i] != 0 && 
              (ticket[i] < ticket[thread_id] || 
              (ticket[i] == ticket[thread_id] && i < thread_id)));
    }
}

void unlock(int thread_id) {
    ticket[thread_id] = 0;  // 임계 구역을 빠져나오면 티켓 반납
}

void *thread_function(void *arg) {
    int thread_id = *((int *)arg);

    lock(thread_id);  // 잠금 (임계 구역 진입)

    // 임계 구역 (Critical Section)
    printf("Thread %d is in the critical section.\n", thread_id);
    sleep(1);
    printf("Thread %d is leaving the critical section.\n", thread_id);

    unlock(thread_id);  // 잠금 해제 (임계 구역 나감)

    return NULL;
}

int main() {
    pthread_t threads[NUM_THREADS];
    int thread_ids[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++) {
        choosing[i] = 0;
        ticket[i] = 0;
    }

    // 스레드 생성
    for (int i = 0; i < NUM_THREADS; i++) {
        thread_ids[i] = i;
        pthread_create(&threads[i], NULL, thread_function, &thread_ids[i]);
    }

    // 스레드 종료 대기
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    return 0;
}

📌 코드 설명

choosing[] 배열: 각 프로세스(스레드)가 번호표를 선택 중인지 여부를 저장.
ticket[] 배열: 각 프로세스(스레드)의 번호표 값을 저장.
lock(int thread_id) 함수:
- 번호표를 받고, 다른 스레드의 번호표와 비교하여 대기.
unlock(int thread_id) 함수:
- 임계 구역을 벗어나면서 번호표를 0으로 설정.
thread_function(void *arg) 함수:
- 각 스레드가 실행되면서 lock → 임계 구역 실행 → unlock 단계를 거침.
main() 함수:
- 3개의 스레드를 생성하고 베이커리 알고리즘을 적용.

📌 실행 방법

위 코드를 Linux 또는 macOS 터미널에서 컴파일하고 실행할 수 있습니다.

🔹 컴파일 명령어

gcc bakery_algorithm.c -o bakery -pthread

-pthread 옵션은 POSIX 스레드(pthread) 라이브러리를 포함하기 위한 옵션입니다.

🔹 실행 명령어

./bakery

📌 온라인 컴파일 사이트

C 코드를 실행할 수 있는 대표적인 사이트:

OnlineGDB
- C, C++ 및 여러 언어 지원.
JDoodle
- 빠른 실행 및 입력 기능 지원.
Ideone
- 간단한 코드 실행 가능.

📌 정리

✅ 베이커리 알고리즘은 다중 프로세스가 공정하게 임계 구역(Critical Section)에 접근하도록 보장하는 알고리즘입니다.
✅ 티켓 번호를 이용한 대기 방식으로 구현되며, 기아 상태(Starvation)와 데드락(Deadlock)을 방지할 수 있습니다.
✅ C 언어에서 pthread를 활용해 스레드 기반으로 구현 가능하며, 여러 개의 스레드가 안전하게 실행됩니다.

🚀 직접 코드를 컴파일하고 실행해 보면서 동작 원리를 이해해 보세요!

Post Views: 50