Вступ

Задача "Філософи за обіднім столом", що виникла як експеримент уяви Едсгера Дейкстри в 1965 році, є однією з найбільш довготривалих проблем комп'ютерних наук. Вона часто використовується для ілюстрації складнощів розподілу обмежених ресурсів серед кількох процесів у паралельних системах. Це яскравий приклад для вивчення основ синхронізації процесів і паралелізму в комп'ютерних науках.

Розуміння проблеми

Опис: X кількість філософів сидять за круглим столом із тарілкою їжі. Вилки розташовані перед кожним філософом. Їх стільки ж, скільки і філософів. Упродовж дня філософи по черзі їдять, сплять і думають. Щоб поїсти, філософу потрібно дві вилки, і кожну вилку може використовувати лише один філософ за раз. У будь-який момент філософ може підняти або покласти вилку, але не може почати їсти, поки не підніме обидві вилки. Філософи по черзі їдять, сплять або думають. Коли вони їдять, вони не думають і не сплять, коли думають — не їдять і не сплять, а коли сплять — не їдять і не думають.

Складнощі: Завдання полягає в тому, щоб розробити систему, де кожен філософ може думати, їсти та спати без голодування. Основні труднощі включають блокування, коли філософи чекають один на одного нескінченно, чекаючи на вилки, та голодування, коли філософ ніколи не отримує достатньо ресурсів для того, щоб поїсти. Можуть також виникати умови змагання, що ускладнює синхронізацію операцій потоків.

Технічне налаштування

Інструменти та технології: Це рішення було реалізоване на мові C у рамках 42 Projects, з використанням POSIX потоків (pthreads) для обробки кількох філософів одночасно та мютексів для керування доступом до виделок.

Налаштування середовища: Рішення розроблене на системі Linux, використовуючи GCC для компіляції з прапорцями для забезпечення безпеки потоків та оптимізації продуктивності.

Перед тим, як перейти до деталей реалізації, давайте розглянемо основи програмування, щоб зрозуміти, що таке процес і потік.

Процес vs Потік

Будівництво будинку — це процес, але люди, які працюють над прокладкою труб, фарбуванням стін і виконанням електричних робіт, — це робочі потоки в процесі будівництва будинку.

Я звик використовувати потоки як синоніми "одиниці роботи" або "речі, які виконують конкретну частину роботи / дію для того, щоб процес завершився успішно".

Отже, якщо я запускаю Chrome і маю відкритих 10 вкладок, я маю 10 процесів. У кожному процесі є 1 або більше одиниць роботи (які називаються потоками), що відповідають за керування пам'яттю, доступ, логіку тощо.

Кредити до зображення: https://www.youtube.com/watch?v=4rLW7zg21gI&abchannel=ByteByteGo_

Процеси — це ізольовані виконувані файли в пам'яті, тоді як потоки — це одиниці виконання в межах цих процесів, які використовують спільний простір пам'яті.

Підсумок

🖥️ Визначення програми: Програма — це виконуваний файл, що містить інструкції для процесора.
Визначення того, що програма є просто файлом до моменту виконання, допомагає краще зрозуміти перехід до процесів, підкреслюючи важливість контексту виконання.

🚀 Створення процесу: Коли програма виконується, вона стає процесом і потребує ресурсів, які управляються операційною системою.

🔒 Ізоляція процесів: Кожен процес має свою власну область пам'яті, що запобігає її пошкодженню іншими процесами.

🧵 Функція потоку: Потік — це одиниця виконання в межах процесу, з власним стеком, але з спільним використанням пам'яті з іншими потоками.

⚙️ Перемикання контексту: Операційна система використовує перемикання контексту для керування виконанням процесів і потоків на процесорі, що є ресурсозатратним процесом.

⏩ Ефективність потоків: Перемикання контексту між потоками є швидшим, ніж між процесами, завдяки спільній пам'яті, що зменшує накладні витрати.

🔄 Альтернативне планування: Механізми, як фібри та корутини, мінімізують витрати на перемикання контексту, дозволяючи додаткам керувати плануванням.

🔗 Захист пам'яті: Ізоляція процесів є важливою для стабільності системи, особливо в багатопроцесних додатках, таких як веб-браузери, що використовують це для покращення досвіду користувача.

🧩 Потоки vs Процеси: Розуміння того, що потоки ділять пам'ять, а процеси — ні, є важливим для розробників при створенні ефективних додатків і управлінні даними.

Загальні проблеми програмування з потоками

При роботі з потоками в C існує кілька поширених проблем, з якими можуть зіткнутися програмісти. До них відносяться:

• Умови змагання: Умова змагання виникає, коли два або більше потоків можуть одночасно отримувати доступ до спільних даних і намагатися змінити їх. Оскільки алгоритм планування потоків може перемикатися між потоками в будь-який час, невідомо, в якому порядку потоки намагатимуться отримати доступ до спільних даних. Тому результат зміни даних залежить від алгоритму планування потоків, тобто обидва потоки "змагаються" за доступ до даних.
• Блокування: Неправильне управління отриманням та звільненням ресурсів може призвести до блокувань, коли потоки застрягають у нескінченному очікуванні один на одного. Блокування відбувається, коли ми двічі чи більше разів заблокуємо один і той самий мютекс або частіше через порядок, в якому мютекси блокуються та розблоковуються.
• Управління ресурсами: Управління спільними ресурсами, такими як пам'ять або дескриптори файлів, серед кількох потоків вимагає ретельної координації для уникнення конфліктів і пошкодження даних.
• Синхронізація: Координація виконання кількох потоків для забезпечення коректної роботи програми часто вимагає використання синхронізаційних примітивів, таких як мютекси, семафори та змінні стану (condition variables).
• Накладні витрати на продуктивність: Створення та управління потоками може призвести до накладних витрат на пам'ять і використання процесора, що впливає на загальну продуктивність додатку, якщо не керувати ними ефективно.
• Складнощі відлагодження: Відлагодження багатопотокових програм може бути складним через недетермінований характер виконання потоків та помилки, залежні від часу.
• Залежність від платформи: Поведінка потоків може змінюватися в залежності від операційної системи та платформи, що вимагає врахування специфіки платформи при програмуванні з потоками.

Основні деталі реалізації

1. Управління потоками: Кожен філософ представлений як потік. Це паралелізм, що моделює одночасні дії: думання, їжу та сон.
2. Використання мютексів: Мютекси є ключовими. Кожна вилка має пов'язаний з нею мютекс, щоб забезпечити, що два філософи не можуть одночасно тримати одну й ту ж вилку, що запобігає блокуванню.
3. Управління станом: Я підтримував стан кожного філософа (їсть, думає, спить) за допомогою спільних змінних, захищених мютексами, щоб зміни стану були взаємно виключними серед потоків.
   4.
   Моніторинг та контроль: Окремий потік моніторингу постійно перевіряє, щоб жоден філософ не голодував, і щоб програма могла коректно завершитись, коли всі філософи достатньо поїли або коли один з філософів помирає.

🔑 Моделювання блокувань: Введення затримок може допомогти продемонструвати блокування в контрольованому середовищі, що корисно для навчальних цілей та відлагодження.

🔑 Запобіжні заходи: Стандартизація порядку отримання блокувань між потоками може значно знизити ризик блокувань у складних додатках.

Основні функції

1. Перевірка стану філософів

char control_simu(t_rcs *data)  
{  
 int i;  
 i = 0;  
 pthread_create(&data->monitor, NULL, monitor_routine, (void *)data);  
 while (i < data->num_philo)  
 {  
 if (pthread_create(&data->philos[i].thread, NULL, philo_routine,   
 (void *)&data->philos[i]) != 0)  
 {  
 printf("\\033[0;31mНе вдалося створити потік філософа\\033[0m \\n");  
 return (0);  
 }  
 i++;  
 }  
 join_threads(data);  
 return (1);  
}

Ця функція починається з створення потоку моніторингу, який контролює всю симуляцію, забезпечуючи, щоб умови, такі як голодування чи завершення завдання, оброблялися коректно. Потім створюються окремі потоки для кожного філософа, кожен з яких виконує рутину, що моделює діяльність філософа, таку як їжа, роздуми та сон. Якщо будь-який потік не вдається запустити, виводиться повідомлення про помилку, і функція завершується з помилкою. Після ініціалізації всіх потоків філософів та потоку моніторингу викликається join_threads(data), щоб основний потік (зазвичай той, що виконує main()) чекав завершення всіх інших потоків перед тим, як продовжити. Це важливо для запобігання передчасному завершенню програми та для правильного звільнення ресурсів.

2. Дія: Їжа

void eating(t_philo *philo)  
{  
 if (philo->id % 2)  
 {  
 pthread_mutex_lock(philo->right_fork);  
 log_action("взяла вилку", philo->id, philo->s_data, "\\033[0;32m");  
 pthread_mutex_lock(philo->left_fork);  
 log_action("взяла вилку", philo->id, philo->s_data, "\\033[0;32m");  
 }  
 else  
 {  
 pthread_mutex_lock(philo->left_fork);  
 log_action("033[0;32m");  
 pthread_mutex_lock(philo->right_fork);  
 log_action("взяла вилку", philo->id, philo->s_data, "\\033[0;32m");  
 }  
 ft_start_eating(philo);  
 log_action("їсть", philo->id, philo->s_data, "\\033[0;34m");  
 precise_sleep(philo->eat_time);  
 pthread_mutex_unlock(philo->left_fork);  
 pthread_mutex_unlock(philo->right_fork);  
 pthread_mutex_lock(&philo->s_data->meal_lock);  
 philo->eating = 0;  
 philo->meals_eaten++;  
 pthread_mutex_unlock(&philo->s_data->meal_lock);  
}

Філософи з непарними ідентифікаторами спочатку беруть праву вилку, а потім ліву, тоді як філософи з парними ідентифікаторами роблять навпаки, запобігаючи виникненню умов очікування, які можуть призвести до блокування. Як тільки обидві вилки захоплені, філософ реєструється як той, хто їсть, і дія часується, щоб змоделювати тривалість їжі. Після їжі вилки відпускаються в зворотному порядку, ніж вони були захоплені, щоб додатково мінімізувати потенційне блокування. Нарешті, завершення прийому їжі реєструється під захистом мютекса meal_lock, щоб безпечно оновити спільні змінні стану eating та meals_eaten, що забезпечує, щоб ці критичні секції не були доступні одночасно іншими потоками, підтримуючи цілісність даних протягом усієї симуляції.

3.
**Логування дій

void log_action(char *action, int i, t_rcs *data, char *color)  
{  
 unsigned long timestamp;   
 pthread_mutex_lock(&data->logging);  
 timestamp = get_time_ms() - data->philos[i -1].start_time;  
 pthread_mutex_lock(&data->death_lock);  
 if (data->dead != n", timestamp, color, i, action);  
 }  
 pthread_mutex_unlock(&data->death_lock);  
 pthread_mutex_unlock(&data->logging);  
}

Ця функція спочатку блокує мютекс logging, щоб запобігти одночасному запису інших потоків, що гарантує, що записи журналу не переплітаються і залишаються читабельними. Потім обчислюється час, що пройшов від початку симуляції для конкретного філософа. Ще один мютекс, death_lock, використовується для перевірки, чи активна ще симуляція перед тим, як логувати дію. Цей подвійний механізм блокування гарантує, що дії реєструються лише тоді, коли філософ активний, і симуляція ще не завершена.

4. Точний таймінг

Ця функція позначає час початку і постійно перевіряє його проти поточного часу, поки не мине бажаний проміжок часу, затримуючи виконання на дуже короткі інтервали (0,5 мілісекунди), щоб не забирати всі ресурси процесора.

void precise_sleep(unsigned long duration)  
{  
 unsigned long start;  
 start = get_time_ms();  
 while (get_time_ms() - start < duration)  
 {  
 usleep(500);  
 }  
}

Візуалізація симуляції дляInput : ./philo 5 610 200 200 9

Виклики та рішення

Виклик 1: Умова циклічного очікування

• Проблема: Умова циклічного очікування виникала, коли кожен філософ намагався взяти ліву та праву вилки в будь-якому порядку. Це могло призвести до блокування, коли всі філософи тримають одну вилку і чекають безкінечно на іншу, що перешкоджає їм їсти.
• Впроваджене рішення: Для запобігання цьому сценарію було введено суворий порядок, у якому філософи беруть свої вилки. Філософи з непарними ідентифікаторами спочатку беруть праву вилку, а потім ліву, в той час як філософи з парними ідентифікаторами роблять навпаки. Ця стратегія порушує цикл циклічного очікування і ефективно запобігає блокуванню.

Виклик 2: Упередженість у захопленні виделок

• Проблема: Деякі філософи мали перевагу в доступі до виделок через своє місце за столом чи послідовність дій, що призводило до несправедливого розподілу ресурсів: деякі філософи завжди брали вилку першими, завершували їсти і знову брали вилку, щоб почати їсти знову.
• Впроваджене рішення: Рішення полягало у впровадженні алгоритму, який враховує справедливість; кожен філософ повинен покласти свої вилки та почекати випадкову мінімальну затримку перед тим, як знову намагатися їх взяти, якщо не вдалося це зробити з першого разу. Ця випадкова затримка знижує ймовірність упередженості та забезпечує, щоб усі філософи мали рівні можливості поїсти.

Виклик 3: Затримка в логуванні смерті

• Проблема: У симуляції була проблема, коли смерть філософа реєструвалась лише після того, як він завершив свій повний цикл сну або їжі, що могло помилково свідчити про те, що філософ був живий довше, ніж це насправді було.
• Впроваджене рішення: Для вирішення цієї проблеми система моніторингу була вдосконалена, щоб перевіряти статус філософів частіше та незалежно від їх циклів їжі чи сну.
  Реалізація спеціалізованого потоку моніторингу дозволила негайно розпізнати та зафіксувати смерть філософа, що забезпечує своєчасне та точне оброблення подій смерті.

Запуск програми

Перевірте та запустіть код

git clone  
make  
./philo 5 610 200 200 3  
або   
valgrind --tool=helgrind ./philo 5 610 200 200

*Усі часи в мілісекундах

./philo [кількість_філософів] [часдосмерті] [час_їжі] [чассну] [кількістьразівкоженфілософповиненїсти (необов'язково)]

Helgrind — це інструмент Valgrind для виявлення помилок синхронізації у програмах на C, C++ та Fortran, які використовують примітиви потоків POSIX pthreads.

Перевірка настрою

• Що таке потік (thread)?😲
• Блокування! 😣
• Нарешті вони слідують за рутиною 😴🍽️🤔

Роздуми

Справжнє застосування такого рішення є надзвичайно широким, особливо в операційних системах та системах транзакцій баз даних, де необхідно ретельно управляти виділенням ресурсів, щоб запобігти блокуванням і забезпечити справедливість.

Не соромтеся поділитися своїми думками, досвідом або будь-якими питаннями в коментарях нижче! Незалежно від того, чи є ви студентом, який стикається з подібними проблемами, чи досвідченим розробником, який має досвід для обміну, я з нетерпінням чекаю на ваші відгуки та обговорення.

Посилання та інструменти

Грайте та спробуйте: Інтерактивне пояснення

Візуалізатор : visualizer

Перекладено з: Solving the Dining Philosophers Problem with Mutex Locks and C Programming