🍝 Philosophers

    _____ _     _ _                 _                     
   |  __ \ |   (_) |               | |                    
   | |__) | |__  _| | ___  ___  ___| |__   ___ _ __ ___  
   |  ___/| '_ \| | |/ _ \/ __|/ _ \ '_ \ / _ \ '__/ __| 
   | |    | | | | | |  __/\__ \  __/ |_) |  __/ |  \__ \ 
   |_|    |_| |_|_|_|\___||___/\___|_.__/ \___|_|  |___/ 

42 Kocaeli | syanak@student.42kocaeli.com.tr | 2025

---

📖 İçindekiler

• Proje Hakkında
• Dining Philosophers Problemi
• Teknik Mimari
• Kullanım
• Algoritma Detayları
• Kod Yapısı
• Test Senaryoları

---

🎯 Proje Hakkında

Philosophers, klasik eşzamanlılık problemi olan "Dining Philosophers Problem" çözümünün C dilinde POSIX threads (pthread) kullanılarak implementasyonudur.

🎓 Öğrenme Hedefleri

• ✅ Multithreading: POSIX threads (pthread) ile paralel programlama
• ✅ Mutex Senkronizasyonu: Thread-safe veri erişimi ve kritik bölge yönetimi
• ✅ Deadlock Prevention: Çatal kilitleme sıralaması ile deadlock önleme
• ✅ Race Condition: Paylaşımlı değişkenlerin mutex ile korunması
• ✅ Circular Doubly Linked List: Yuvarlak masa simülasyonu için optimal veri yapısı
• ✅ Memory Management: Valgrind ile doğrulanmış leak-free bellek yönetimi

---

🧠 Dining Philosophers Problemi

Problem Tanımı

Yuvarlak bir masada N filozof oturur. Her filozofun önünde bir tabak makarna bulunur ve filozoflar arasında N adet çatal paylaşılır (her filozofun sağında ve solunda birer çatal).

Filozoflar sürekli olarak üç aktivite arasında geçiş yapar:

┌─────────┐
│  THINK  │ ──► Filozof düşünür
└─────────┘
     │
     ▼
┌─────────┐
│   EAT   │ ──► İki çatal alıp yemek yer
└─────────┘
     │
     ▼
┌─────────┐
│  SLEEP  │ ──► Uyur
└─────────┘
     │
     └──► (Tekrar başa dön)

🔴 Klasik Problemler

1. Deadlock

Tüm filozoflar aynı anda sol çatalı alırsa, kimse sağ çatalı alamaz ve sistem kilitlenir.

Filozof 1: Sol çatal (1) ✓  Sağ çatal (2) ✗ (Filozof 2'de)
Filozof 2: Sol çatal (2) ✓  Sağ çatal (3) ✗ (Filozof 3'te)
Filozof 3: Sol çatal (3) ✓  Sağ çatal (4) ✗ (Filozof 4'te)
...
Filozof N: Sol çatal (N) ✓  Sağ çatal (1) ✗ (Filozof 1'de)

➜ Sonuç: Herkes birini bekler → Sistem kilitlenir

2. Starvation (Açlıktan Ölme)

Bir filozof hiç çatal alamazsa, time_to_die süresi dolduğunda ölür.

3. Race Condition

Paylaşımlı değişkenlere (örn: last_meal_time, meals_eaten) eşzamanlı erişim veri bozulmasına yol açar.

---

🏗️ Teknik Mimari

Veri Yapıları

t_data - Global Simülasyon Parametreleri

typedef struct s_data {
    int              num_philos;        // Filozof sayısı
    int              time_to_die;       // Ölüm süresi (ms)
    int              time_to_eat;       // Yemek yeme süresi (ms)
    int              time_to_sleep;     // Uyuma süresi (ms)
    int              must_eat_count;    // Minimum yemek sayısı (-1 = sınırsız)
    int              stop_simulation;   // Simülasyon durdurma flag'i
    int              all_ate_enough;    // Herkes yeterince yedi mi?
    int              start_flag;        // Thread başlangıç senkronizasyonu
    long long        start_time;        // Simülasyon başlangıç timestamp'i
    long long        end_time;          // Simülasyon bitiş timestamp'i
    pthread_mutex_t  print_mutex;       // printf() race condition koruması
    pthread_mutex_t  death_mutex;       // Ölüm flag'i koruması
    pthread_mutex_t  meal_mutex;        // Yemek verisi koruması
    pthread_mutex_t  start_mutex;       // Başlangıç senkronizasyonu
    pthread_mutex_t  *forks;            // Çatal mutex dizisi
} t_data;

t_philo - Filozof Node'u (Circular Doubly Linked List)

typedef struct s_philo {
    int              id;                // Filozof ID (1-indexed)
    int              meals_eaten;       // Toplam yenilen yemek sayısı
    long long        last_meal_time;    // Son yemek başlangıç zamanı
    pthread_t        thread;            // Thread handle
    pthread_mutex_t  *left_fork;        // Sol çatal mutex pointer
    pthread_mutex_t  *right_fork;       // Sağ çatal mutex pointer
    struct s_philo   *next;             // Sonraki filozof (circular)
    struct s_philo   *prev;             // Önceki filozof (circular)
    t_data           *data;             // Global data pointer
} t_philo;

🔄 Neden Circular Doubly Linked List?

Linked list yapısı, yuvarlak masayı mükemmel şekilde temsil eder:

     ┌─────────────────────────────────────┐
     │                                     │
     ▼                                     │
[Philo 1] ◄─► [Philo 2] ◄─► [Philo 3] ◄─►[Philo 4]
   │   │         │   │         │   │         │   │
   │   └─────────┼───┼─────────┼───┼─────────┘   │
   │            Fork1        Fork2        Fork3   │
   └──────────────────────────────────────────────┘
                         Fork4

Avantajları:

• ✅ Circular: Son filozof → İlk filozof (yuvarlak masa)
• ✅ Doubly: Her node hem prev hem next pointer'a sahip
• ✅ Flexible: N filozof için dinamik boyutlandırma
• ✅ Natural Fork Assignment: Her filozofun sol çatalı = prev->right_fork

---

🚀 Kullanım

Derleme

make

Çalıştırma

./philo <num_philos> <time_to_die> <time_to_eat> <time_to_sleep> [must_eat_count]

Parametreler

Parametre	Açıklama	Gerekli
num_philos	Filozof sayısı (1-200)	✅
time_to_die	Açlıktan ölme süresi (ms)	✅
time_to_eat	Yemek yeme süresi (ms)	✅
time_to_sleep	Uyuma süresi (ms)	✅
must_eat_count	Minimum yemek sayısı	❌

Örnek Kullanımlar

✅ Kimse Ölmemeli

./philo 5 800 200 200

✅ Herkes 7 Kez Yemeli

./philo 5 800 200 200 7

❌ Bir Filozof Ölmeli

./philo 4 310 200 100
# Zaman yetersiz → Filozof ölür

⚠️ Edge Case: Tek Filozof

./philo 1 800 200 200
# Sadece 1 çatal var → Yemek yiyemez → Ölür

---

⚙️ Algoritma Detayları

1️⃣ Deadlock Önleme Stratejisi

Problem: Tüm filozoflar aynı anda sol çatalı alırsa deadlock oluşur.

Çözüm: Çift ve tek ID'li filozoflar farklı sırada çatal alır:

void add_fork(pthread_mutex_t **first_fork, pthread_mutex_t **second_fork,
              t_philo *philo)
{
    if (philo->id % 2 == 0)  // ÇİFT ID
    {
        *first_fork = philo->left_fork;   // Önce sol
        *second_fork = philo->right_fork;  // Sonra sağ
    }
    else  // TEK ID
    {
        *first_fork = philo->right_fork;   // Önce sağ
        *second_fork = philo->left_fork;   // Sonra sol
    }
}

Neden Çalışır?

• Çift ID'liler: Sol → Sağ
• Tek ID'liler: Sağ → Sol
• En az bir filozof her zaman ikinci çatalı alabilir → Deadlock yok

2️⃣ Filozof Yaşam Döngüsü

void *philosopher_routine(void *arg)
{
    t_philo *philo = (t_philo *)arg;
    
    wait_for_all(philo);  // Senkronize başlangıç
    
    pthread_mutex_lock(&philo->data->meal_mutex);
    philo->last_meal_time = get_time();
    pthread_mutex_unlock(&philo->data->meal_mutex);
    
    if (philo->id % 2 == 0)
        ft_usleep(philo->data->time_to_eat);  // Çift ID'liler bekler
    
    while (!should_stop_simulation(philo))
    {
        eat_action(philo);    // Yemek ye
        sleep_action(philo);  // Uyu
        think_action(philo);  // Düşün
    }
    
    return (NULL);
}

Akış Diyagramı:

START
  │
  ├──► Wait for all threads (senkronizasyon)
  │
  ├──► Set initial last_meal_time
  │
  ├──► If EVEN ID → sleep(time_to_eat)  [Staggering]
  │
  └──► WHILE (!stop_simulation)
         │
         ├──► EAT   (take forks → eat → release)
         ├──► SLEEP
         └──► THINK

3️⃣ Yemek Yeme Aksionu

void eat_action(t_philo *philo)
{
    pthread_mutex_t *first_fork;
    pthread_mutex_t *second_fork;
    
    add_fork(&first_fork, &second_fork, philo);
    
    pthread_mutex_lock(first_fork);
    print_status(philo, "has taken a fork");
    
    if (handle_single_philosopher(philo, first_fork))
        return;  // Tek filozof özel durumu
    
    pthread_mutex_lock(second_fork);
    print_status(philo, "has taken a fork");
    print_status(philo, "is eating");
    
    pthread_mutex_lock(&philo->data->meal_mutex);
    philo->last_meal_time = get_time();
    philo->meals_eaten++;
    pthread_mutex_unlock(&philo->data->meal_mutex);
    
    ft_usleep(philo->data->time_to_eat);
    
    pthread_mutex_unlock(second_fork);
    pthread_mutex_unlock(first_fork);
}

Kritik Noktalar:

• ✅ Çatallar sırayla kilitlenir (deadlock önleme)
• ✅ last_meal_time mutex ile korunur (race condition önleme)
• ✅ Çatallar ters sırada açılır (LIFO - önce son alınan)

4️⃣ Monitor Thread (Ölüm Kontrolü)

Ayrı bir thread, tüm filozofları sürekli izler:

void *monitor_routine(void *arg)
{
    t_philo *first = (t_philo *)arg;
    
    while (1)
    {
        if (check_all_philosophers(first))  // Ölüm kontrolü
            return (NULL);
        
        if (handle_simulation_end(first))   // Herkes yeterince yedi mi?
            return (NULL);
        
        usleep(5);  // 5µs check interval (CPU-friendly)
    }
}

Ölüm Kontrolü:

int check_philosopher_death(t_philo *philo)
{
    long long current_time = get_time();
    
    pthread_mutex_lock(&philo->data->meal_mutex);
    long long time_since_meal = current_time - philo->last_meal_time;
    
    if (time_since_meal >= philo->data->time_to_die)
    {
        pthread_mutex_unlock(&philo->data->meal_mutex);
        
        pthread_mutex_lock(&philo->data->death_mutex);
        if (!philo->data->stop_simulation)
        {
            philo->data->stop_simulation = 1;
            printf("%lld %d died\n", 
                   current_time - philo->data->start_time, philo->id);
        }
        pthread_mutex_unlock(&philo->data->death_mutex);
        return (1);
    }
    
    pthread_mutex_unlock(&philo->data->meal_mutex);
    return (0);
}

---

🔒 Thread Senkronizasyonu

Mutex Kullanım Tablosu

Mutex	Koruma Alanı	Kullanım
forks[i]	i. çatal	Çatal paylaşımı (N adet)
print_mutex	printf() çağrıları	Karışık çıktı önleme
death_mutex	stop_simulation flag'i	Ölüm durumu kontrolü
meal_mutex	last_meal_time, meals_eaten	Yemek verileri
start_mutex	start_flag	Senkronize başlangıç

Senkronize Başlangıç

Tüm threadler aynı anda başlamalı (timing accuracy için):

void wait_for_all(t_philo *philo)
{
    pthread_mutex_lock(&philo->data->start_mutex);
    while (!philo->data->start_flag)
    {
        pthread_mutex_unlock(&philo->data->start_mutex);
        usleep(1);
        pthread_mutex_lock(&philo->data->start_mutex);
    }
    pthread_mutex_unlock(&philo->data->start_mutex);
}

Akış:

1. Main thread tüm philosopher threadleri oluşturur
2. Her thread wait_for_all() içinde bekler
3. Monitor thread oluşturulur
4. Main thread start_flag = 1 yapar
5. Tüm threadler aynı anda başlar

---

📁 Kod Yapısı

philosophers/
├── Makefile              # Derleme kuralları
├── philosophers.h        # Header dosyası (tüm struct ve prototip tanımları)
├── main.c               # Entry point ve argüman kontrolü
├── init.c               # Data ve linked list initialization
├── threads.c            # Thread oluşturma ve philosopher_routine
├── actions.c            # eat, sleep, think fonksiyonları
├── monitor.c            # Ölüm ve yemek kontrolü (monitor thread)
├── utils.c              # Yardımcı fonksiyonlar (time, print, atoi)
└── cleanup.c            # Mutex destroy ve memory free

Dosya İçerikleri

main.c

• main(): Program giriş noktası
• check_args(): Argüman validasyonu
• print_usage(): Kullanım mesajı

init.c

• init_data(): Global data struct initialization
• create_philo(): Tek bir filozof node'u oluştur
• init_philosophers(): Circular doubly linked list oluştur
• set_left_forks(): Her filozofa left_fork ata

threads.c

• start_threads(): Tüm filozof threadlerini oluştur
• philosopher_routine(): Her filozofun ana loop'u
• run_simulation(): Monitor thread + thread join
• join_threads(): Tüm threadleri bekle
• should_stop_simulation(): Stop flag kontrolü (thread-safe)

actions.c

• eat_action(): Çatal al → ye → bırak
• sleep_action(): Uyuma
• think_action(): Düşünme (tek ID + tek filozof sayısı için 1ms sleep)
• add_fork(): Deadlock önleme için çatal sırası
• handle_single_philosopher(): Tek filozof edge case

monitor.c

• monitor_routine(): Ana monitoring loop
• check_philosopher_death(): Her filozof için ölüm kontrolü
• check_all_ate_enough(): Herkes yeterince yedi mi?
• check_all_philosophers(): Tüm filozofları tara

utils.c

• get_time(): Milisaniye cinsinden timestamp
• ft_usleep(): Hassas sleep (busy-wait kullanır)
• print_status(): Thread-safe printf
• ft_atoi(): String → int dönüşümü
• check_args(): Argüman validasyonu

cleanup.c

• destroy_mutexes(): Tüm mutex'leri destroy et
• free_philosophers(): Linked list'i serbest bırak
• cleanup_all(): Komple temizlik (memory + mutex)
• wait_for_all(): Thread senkronizasyonu

---

🧪 Test Senaryoları

✅ Başarılı Senaryolar

# 1. Basit test - 5 filozof, kimse ölmemeli
./philo 5 800 200 200

# 2. Zorunlu yemek sayısı - herkes 7 kez yemeli
./philo 5 800 200 200 7

# 3. Çok sayıda filozof
./philo 200 800 200 200

# 4. Dar zamanlar (ama yeterli)
./philo 4 410 200 200

❌ Hata Senaryoları

# 1. Yetersiz zaman - filozof ölmeli
./philo 4 310 200 100
# time_to_die (310ms) < time_to_eat (200ms) + delay

# 2. Tek filozof - yemek yiyemez
./philo 1 800 200 200
# Sadece 1 çatal → İkinci çatal yok → Ölür

# 3. Çok dar margin
./philo 2 200 100 100
# Kritik timing - ölüm riski yüksek

🔍 Valgrind Memory Check

valgrind --leak-check=full --show-leak-kinds=all ./philo 5 800 200 200

Beklenen Çıktı:

==12345== HEAP SUMMARY:
==12345==     in use at exit: 0 bytes in 0 blocks
==12345==   total heap usage: X allocs, X frees, Y bytes allocated
==12345== 
==12345== All heap blocks were freed -- no leaks are possible

🧵 Thread Sanitizer

# Makefile'da -fsanitize=thread flag'i ekleyerek
make SANITIZE=thread
./philo 5 800 200 200

---

📊 Çıktı Formatı

Standart Log

[timestamp_ms] [philosopher_id] [action]

Eylemler:

• has taken a fork - Çatal aldı
• is eating - Yemek yiyor
• is sleeping - Uyuyor
• is thinking - Düşünüyor
• died - Öldü (simülasyon durur)

Örnek Çıktı

$ ./philo 5 800 200 200
0 1 has taken a fork
0 1 has taken a fork
0 1 is eating
0 3 has taken a fork
0 3 has taken a fork
0 3 is eating
0 5 has taken a fork
0 5 has taken a fork
0 5 is eating
200 1 is sleeping
200 3 is sleeping
200 5 is sleeping
200 2 has taken a fork
200 2 has taken a fork
200 2 is eating
200 4 has taken a fork
200 4 has taken a fork
200 4 is eating
400 1 is thinking
400 2 is sleeping
400 3 is thinking
400 4 is sleeping
400 5 is thinking
...

Ölüm Senaryosu

$ ./philo 4 310 200 100
0 1 has taken a fork
0 1 has taken a fork
0 1 is eating
0 3 has taken a fork
0 3 has taken a fork
0 3 is eating
200 1 is sleeping
200 3 is sleeping
200 2 has taken a fork
200 2 has taken a fork
200 2 is eating
200 4 has taken a fork
310 4 died    # ← 4 numaralı filozof öldü

---

🛡️ Edge Case'ler ve Özel Durumlar

1. Tek Filozof

int handle_single_philosopher(t_philo *philo, pthread_mutex_t *first_fork)
{
    if (philo->data->num_philos == 1)
    {
        while (!should_stop_simulation(philo))
            usleep(1000);
        
        pthread_mutex_unlock(first_fork);
        return (1);
    }
    return (0);
}

Mantık: Tek filozof bir çatal alır ama ikinci çatal yoktur → Yemek yiyemez → Monitor ölümü algılar

2. Tek Filozof Sayısı + Tek ID

Tek filozof sayısında (örn: 5), tek ID'li filozoflar birbirini bloklar:

void think_action(t_philo *philo)
{
    print_status(philo, "is thinking");
    if (philo->id % 2 == 1 && philo->data->num_philos % 2 != 0)
        ft_usleep(1);  // 1ms ekstra bekleme
}

Neden? Tek sayıda filozof → 3 filozof yiyor, 2 filozof bekliyor → İmbalance → 1ms delay dengeyi sağlar

3. Çift ID Thread Staggering

if (philo->id % 2 == 0)
    ft_usleep(philo->data->time_to_eat);

Çift ID'li filozoflar başlangıçta time_to_eat kadar bekler → Tüm filozoflar aynı anda çatal almaya çalışmaz

---

🧹 Bellek Yönetimi

Allokasyon Sırası

1. t_data struct (malloc)
2. Her filozof için t_philo node (N kez malloc)
3. Her filozof için right_fork mutex (N kez malloc)
4. Mutex init'ler

Temizlik Sırası (Ters LIFO)

void cleanup_all(t_philo *first, t_data *data)
{
    int num_philo = data->num_philos;
    
    if (data)
    {
        destroy_mutexes(data, first);  // 1. Mutex'leri destroy et
        free(data);                    // 2. Global data'yı free et
    }
    
    if (first)
        free_philosophers(first, num_philo);  // 3. Linked list free
}

Linked List Free:

void free_philosophers(t_philo *first, int count)
{
    t_philo *current = first;
    t_philo *next;
    int i = 0;
    
    while (i < count)
    {
        next = current->next;
        free(current->right_fork);  // Önce çatal mutex'i
        free(current);              // Sonra node
        current = next;
        i++;
    }
}

---

🎓 42 Norminette Uyumu

• ✅ 25 satır fonksiyon limiti (en uzun fonksiyon 24 satır)
• ✅ 80 karakter satır limiti (tüm satırlar ≤80)
• ✅ Maksimum 5 fonksiyon per file
• ✅ Global değişken kullanımı yok
• ✅ Yasak fonksiyon yok (sadece pthread.h, stdio.h, stdlib.h, sys/time.h, unistd.h)

Norminette Check

norminette *.c *.h

---

🚨 Yaygın Hatalar ve Çözümleri

❌ Data Race

Hata:

// YANLIŞ - Mutex yok
philo->last_meal_time = get_time();

Doğru:

pthread_mutex_lock(&philo->data->meal_mutex);
philo->last_meal_time = get_time();
pthread_mutex_unlock(&philo->data->meal_mutex);

❌ usleep() Hassasiyeti

Problem: usleep(200000) tam 200ms uyumaz (scheduler delay)

Çözüm: Busy-wait ile hassas timing:

void ft_usleep(long long time)
{
    long long start = get_time();
    
    while (get_time() - start < time)
        usleep(100);  // Kısa aralıklarla kontrol et
}

❌ Printf Race Condition

Hata:

// YANLIŞ - Karışık çıktı
printf("%lld %d is eating\n", timestamp, id);

Doğru:

pthread_mutex_lock(&data->print_mutex);
printf("%lld %d is eating\n", timestamp, id);
pthread_mutex_unlock(&data->print_mutex);

---

📚 Öğrenilen Kavramlar

Thread Senkronizasyonu

• ✅ Mutex: Kritik bölge koruması
• ✅ Deadlock: Circular wait prevention
• ✅ Race Condition: Atomic operations
• ✅ Starvation: Fair resource allocation

Veri Yapıları

• ✅ Circular Doubly Linked List: Natural representation of circular table
• ✅ Pointer Management: Next/prev navigation

Sistem Programlama

• ✅ POSIX Threads: pthread_create, pthread_join
• ✅ gettimeofday(): Microsecond precision timing
• ✅ Memory Management: malloc/free discipline

---

👨‍💻 Geliştirici

Said Yanak
📧 syanak@student.42kocaeli.com.tr
🏫 42 Kocaeli
📅 Ağustos 2025

---

📖 Kaynaklar

• POSIX Threads Programming (LLNL)
• Dining Philosophers Problem - Wikipedia
• Mutex Deadlocks - GeeksforGeeks
• 42 Philosophers Subject PDF

---

⭐ Bu projeyi beğendiyseniz yıldızlamayı unutmayın!

Made with ☕ at 42 Kocaeli