Обедающие философы

В книге Язык программирования Rust в главе 4.3 Обедающие философы в Arch Linux на ядре 4.10.3-1-ARCH выполнение кода, скомпилированного в rustc 1.16.0

use std::thread;
use std::time::Duration;
use std::sync::{Mutex, Arc};

struct Philosopher {
    name:  String,
    left:  usize,
    right: usize,
}

impl Philosopher {
    fn new(name: &str, left: usize, right: usize) -> Philosopher {
        Philosopher {
            name: name.to_string(),
            left: left,
            right: right,
        }
    }

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        thread::sleep(Duration::from_millis(150));
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} начала есть.", self.name);
        
        thread::sleep(Duration::from_millis(1000));
        
        println!("{} закончила есть.", self.name);
    }
}

struct Table {
    forks: Vec<Mutex<()>>,
}

fn main() {
    let table = Arc::new(Table { forks: vec![
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
    ]});

    let philosophers = vec![
        Philosopher::new("Джудит Батлер", 0, 1),
        Philosopher::new("Рая Дунаевская", 1, 2),
        Philosopher::new("Зарубина Наталья", 2, 3),
        Philosopher::new("Эмма Гольдман", 3, 4),
        Philosopher::new("Анна Шмидт", 0, 4),
    ];

    let handles: Vec<_> = philosophers.into_iter().map(|p| {
        let table = table.clone();

        thread::spawn(move || {
            p.eat(&table);
        })
    }).collect();

    for h in handles {
        h.join().unwrap();
    }
}

даёт результат

Эмма Гольдман начала есть.
Эмма Гольдман закончила есть.
Зарубина Наталья начала есть.
Зарубина Наталья закончила есть.
Рая Дунаевская начала есть.
Рая Дунаевская закончила есть.
Джудит Батлер начала есть.
Джудит Батлер закончила есть.
Анна Шмидт начала есть.
Анна Шмидт закончила есть.

вместо

Рая Дунаевская начала есть.
Эмма Гольдман начала есть.
Эмма Гольдман закончила есть.
Рая Дунаевская закончила есть.
Джудит Батлер начала есть.
Зарубина Наталья начала есть.
Джудит Батлер закончила есть.
Анна Шмидт начала есть.
Зарубина Наталья закончила есть.
Анна Шмидт закончила есть.

Ожидаемого параллелизма не наблюдается. В чём может быть проблема?

На самом деле параллелизм никуда не делся. Чтобы прояснить сложные взаимоотношения философов и вилок, сделаем сообщения в функции eat() более информативными:

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        
        println!("{} взяла вилку № {} слева.", self.name, self.left);
        
        thread::sleep(Duration::from_millis(150));
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} взяла вилку № {} справа и начала есть.", self.name, self.right);
        
        thread::sleep(Duration::from_millis(1000));
        
        println!("{} закончила есть и положила вилки № {} и № {}.", self.name, self.left, self.right);
    }

Получим:

Джудит Батлер взяла вилку № 0 слева.
Рая Дунаевская взяла вилку № 1 слева.
Эмма Гольдман взяла вилку № 3 слева.
Зарубина Наталья взяла вилку № 2 слева.
Эмма Гольдман взяла вилку № 4 справа и начала есть.
Эмма Гольдман закончила есть и положила вилки № 3 и № 4.
Зарубина Наталья взяла вилку № 3 справа и начала есть.
Зарубина Наталья закончила есть и положила вилки № 2 и № 3.
Рая Дунаевская взяла вилку № 2 справа и начала есть.
Рая Дунаевская закончила есть и положила вилки № 1 и № 2.
Джудит Батлер взяла вилку № 1 справа и начала есть.
Джудит Батлер закончила есть и положила вилки № 0 и № 1.
Анна Шмидт взяла вилку № 0 слева.
Анна Шмидт взяла вилку № 4 справа и начала есть.
Анна Шмидт закончила есть и положила вилки № 0 и № 4.

Первое, что делают философы - расхватывают левые вилки. Благодаря своей леворукости Анна Шмидт осталась без вилки (вилка 0 у Джудит) она не пытается захватить вилку 4 и та достается Эмме, которая собрала полный набор и начинает есть. Так как у философов не хватает сообразительности вернуть ненужную левую вилку на стол, то получается что они едят по одному.

Проще всего добиться того чтобы одновременно ели два философа - убрать задержку после взятия левой вилки:

//thread::sleep(Duration::from_millis(150));

Получим:

Джудит Батлер взяла вилку № 0 слева.
Джудит Батлер взяла вилку № 1 справа и начала есть.
Зарубина Наталья взяла вилку № 2 слева.
Зарубина Наталья взяла вилку № 3 справа и начала есть.
Зарубина Наталья закончила есть и положила вилки № 2 и № 3.
Джудит Батлер закончила есть и положила вилки № 0 и № 1.
Анна Шмидт взяла вилку № 0 слева.
Анна Шмидт взяла вилку № 4 справа и начала есть.
Эмма Гольдман взяла вилку № 3 слева.
Рая Дунаевская взяла вилку № 1 слева.
Рая Дунаевская взяла вилку № 2 справа и начала есть.
Анна Шмидт закончила есть и положила вилки № 0 и № 4.
Рая Дунаевская закончила есть и положила вилки № 1 и № 2.
Эмма Гольдман взяла вилку № 4 справа и начала есть.
Эмма Гольдман закончила есть и положила вилки № 3 и № 4.

Джудит и Наталья едят одновременно.

1 симпатия

Благодарю за содержательный и оперативный ответ. Под параллелизмом в этой задаче я подразумеваю ситуацию, когда одновременно ест больше одного философа, хотя это понятие имеет и другое значение: одновременная работа нескольких потоков. После того, как мы убрали задержку после взятия вилок, философы начали есть одновременно. В Вашем запуске экземпляра одновременно едят Джудит и Наталья, затем Анна и Рая. При разных запусках экземпляра ситуация меняется:

Зарубина Наталья взяла вилку № 2 слева.
Зарубина Наталья взяла вилку № 3 справа и начала есть.
Рая Дунаевская взяла вилку № 1 слева.
Джудит Батлер взяла вилку № 0 слева.
Зарубина Наталья закончила есть и положила вилки № 2 и № 3.
Эмма Гольдман взяла вилку № 3 слева.
Эмма Гольдман взяла вилку № 4 справа и начала есть.
Рая Дунаевская взяла вилку № 2 справа и начала есть.
Эмма Гольдман закончила есть и положила вилки № 3 и № 4.
Рая Дунаевская закончила есть и положила вилки № 1 и № 2.
Джудит Батлер взяла вилку № 1 справа и начала есть.
Джудит Батлер закончила есть и положила вилки № 0 и № 1.
Анна Шмидт взяла вилку № 0 слева.
Анна Шмидт взяла вилку № 4 справа и начала есть.
Анна Шмидт закончила есть и положила вилки № 0 и № 4.

Здесь одновременно едят только Эмма и Рая.

Рая Дунаевская взяла вилку № 1 слева.
Рая Дунаевская взяла вилку № 2 справа и начала есть.
Джудит Батлер взяла вилку № 0 слева.
Эмма Гольдман взяла вилку № 3 слева.
Эмма Гольдман взяла вилку № 4 справа и начала есть.
Рая Дунаевская закончила есть и положила вилки № 1 и № 2.
Джудит Батлер взяла вилку № 1 справа и начала есть.
Зарубина Наталья взяла вилку № 2 слева.
Эмма Гольдман закончила есть и положила вилки № 3 и № 4.
Зарубина Наталья взяла вилку № 3 справа и начала есть.
Джудит Батлер закончила есть и положила вилки № 0 и № 1.
Анна Шмидт взяла вилку № 0 слева.
Анна Шмидт взяла вилку № 4 справа и начала есть.
Зарубина Наталья закончила есть и положила вилки № 2 и № 3.
Анна Шмидт закончила есть и положила вилки № 0 и № 4.

Здесь одновременно едят Рая и Эмма, затем Эмма и Джудит, затем Джудит и Наталья, затем Наталья и Анна. Это значит, что разные запуски дают разное общее время обеда. Возникает два философских вопроса:

  1. Почему это происходит в нашем алгоритме?
  2. Какой алгоритм даёт минимальное время обеда?

Сколько потоков работает одновременно зависит от возможностей процессора и менеджера потоков ОС. Чтобы сделать все совсем наглядным можно добавить сообщение в самое начало функции eat() и убрать все остальные кроме последнего:

Джудит Батлер села за стол.
Рая Дунаевская села за стол.
Зарубина Наталья села за стол.
Эмма Гольдман села за стол.
Анна Шмидт села за стол.
Джудит Батлер закончила есть и положила вилки № 0 и № 1.
Зарубина Наталья закончила есть и положила вилки № 2 и № 3.
Анна Шмидт закончила есть и положила вилки № 0 и № 4.
Рая Дунаевская закончила есть и положила вилки № 1 и № 2.
Эмма Гольдман закончила есть и положила вилки № 3 и № 4.

Тут сначала запускаются все потоки в том порядке как они описаны в переменной philosophers. Заканчиваются они уже в другом порядке.

Насчет минимального времени трудно сказать. Можно попробовать задавать случайную задержку на старте, согласовывать действия философов, возвращать левую вилку если правая занята. Вариантов много.

1 симпатия

Интересно что вывод сообщений из потоков похоже тоже оказывает какое-то влияние на их поведение. Видимо из-за того что потокам приходится синхронизироваться для записи в общий ресурс - stdout.

Не похоже, что порядок философов совпадает с порядком в векторе philosophers:

   let philosophers = vec![
        Philosopher::new("Джудит Батлер", 0, 1),
        Philosopher::new("Рая Дунаевская", 1, 2),
        Philosopher::new("Наталья Зарубина", 2, 3),
        Philosopher::new("Эмма Гольдман", 3, 4),
        Philosopher::new("Анна Шмидт", 0, 4),
    ];

Реализация:

    fn eat(&self, table: &Table) {
        println!("{} села за стол.", self.name);

        let _left = table.forks[self.left].lock().unwrap();
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} взяла вилку № {} слева и вилку № {} справа и начала есть.",
            self.name, self.left, self.right);
                
        thread::sleep(Duration::from_millis(1000));
        
        println!("{} закончила есть.", self.name);
    }

Даёт результат:

Джудит Батлер села за стол.
Джудит Батлер взяла вилку № 0 слева и вилку № 1 справа и начала есть.
Рая Дунаевская села за стол.
Анна Шмидт села за стол.
Эмма Гольдман села за стол.
Эмма Гольдман взяла вилку № 3 слева и вилку № 4 справа и начала есть.
Наталья Зарубина села за стол.
Джудит Батлер закончила есть.
Эмма Гольдман закончила есть.
Наталья Зарубина взяла вилку № 2 слева и вилку № 3 справа и начала есть.
Анна Шмидт взяла вилку № 0 слева и вилку № 4 справа и начала есть.
Наталья Зарубина закончила есть.
Анна Шмидт закончила есть.
Рая Дунаевская взяла вилку № 1 слева и вилку № 2 справа и начала есть.
Рая Дунаевская закончила есть.

Анна и Эмма нарушили очередь и сели за стол раньше Натальи. У меня возник другой вопрос: как реализовать счётчик одновременно обедающих философов?

Если убрать второе сообщение, то начнет совпадать. println() внутри потока как то влияет на порядок их выполнения.

По хорошему надо убрать все println() и записывать в локальный вектор/массив системное время запуска/взятия вилок и т.п. А после завершения потока вернуть этот вектор в основной поток. В основном потоке можно сравнить эти времена и определить какие философы обедали одновременно.

Похоже, мой Arch Linux на Intel i7 по другому обрабатывает потоки, убрал второе сообщение:

    fn eat(&self, table: &Table) {
        println!("{} села за стол.", self.name);

        let _left = table.forks[self.left].lock().unwrap();
        let _right = table.forks[self.right].lock().unwrap();

        //println!("{} взяла вилку № {} слева и вилку № {} справа и начала есть.",
        //    self.name, self.left, self.right);
                
        thread::sleep(Duration::from_millis(1000));
        
        println!("{} закончила есть.", self.name);
    }

Но порядок посадки философов за стол отличается от порядка в векторе philosophers:

Рая Дунаевская села за стол.
Анна Шмидт села за стол.
Эмма Гольдман села за стол.
Джудит Батлер села за стол.
Наталья Зарубина села за стол.
Рая Дунаевская закончила есть.
Анна Шмидт закончила есть.
Эмма Гольдман закончила есть.
Джудит Батлер закончила есть.
Наталья Зарубина закончила есть.

А что если для подсчёта одновременно обедающих философов объявить разделяемую между потоками переменную типа i32 и внутри eat увеличивать и уменьшать её? Как это можно реализовать в Rust?

Хм, у меня на Win7 порядок был всегда одинаковый.

Можно, только нужно завернуть ее в Arc<Mutex<_>>. Навскидку как-то так:

let counter = Arc::new(Mutex::new(0i32));
//...
        let table = table.clone();
        let counter = counter.clone();

        thread::spawn(move || {
            p.eat(&table, counter);
        })

Но тут во-первых нужно захватывать доступ к переменной - потоки опять будут мешать друг другу. Во-вторых в конце она все равно будет равна 0, а если ее мониторить в основном потоке в цикле то это еще сильнее будет мешать вторичным потокам.

Еще есть atomic types. Думаю это лучше подойдет.

Для подсчёта количества одновременных едоков использовал тип AtomicUsize:

use std::thread;
use std::time::Duration;
use std::sync::{Mutex, Arc};
use std::sync::atomic::{AtomicUsize, Ordering};

struct Philosopher {
    name:  String,
    left:  usize,
    right: usize,
}

impl Philosopher {
    fn new(name: &str, left: usize, right: usize) -> Philosopher {
        Philosopher {
            name: name.to_string(),
            left: left,
            right: right,
        }
    }

    fn eat(&self, table: &Table, n_eaters: &Arc<AtomicUsize>) {
        // Философ взял левую вилку
        let _left = table.forks[self.left].lock().unwrap();
        
        // Философ взял правую вилку
        let _right = table.forks[self.right].lock().unwrap();

        // Увеличилось количество одновременных едоков
        n_eaters.store(n_eaters.load(Ordering::SeqCst) + 1, Ordering::Release);
                
        println!("{} взял вилку № {} слева и вилку № {} справа и начал есть. Ест {}",
                 self.name, 
                 self.left, 
                 self.right, 
                 n_eaters.load(Ordering::SeqCst));
            
        // Философ немного поел
        thread::sleep(Duration::from_millis(100));
        
        // Уменьшилось количество одновременных едоков
        n_eaters.store(n_eaters.load(Ordering::SeqCst) - 1, Ordering::Release);
                        
        // Философ вернул обе вилки
        println!("{} закончил есть. Ест {}", 
                 self.name, 
                 n_eaters.load(Ordering::SeqCst));
    }
}

struct Table {
    forks: Vec<Mutex<()>>,
}

fn main() {
    // Вилки на столе - ценный разделяемый ресурс!
    let table = Arc::new(Table { forks: vec![
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
    ]});

    // Проголодавшиеся философы
    let philosophers = vec![
        Philosopher::new("Андрей",   0, 1),
        Philosopher::new("Борис",    1, 2),
        Philosopher::new("Владимир", 2, 3),
        Philosopher::new("Георгий",  3, 4),
        Philosopher::new("Дмитрий",  0, 4), // левша
    ];
    
    // Количество одновременно кушающих философов: пока никого
    let n_eaters = Arc::new(AtomicUsize::new(0));

    // Философы приготовились к обеду
    let handles: Vec<_> = philosophers.into_iter().map(|p| {
        let table = table.clone();
        let n_eaters = n_eaters.clone();

        thread::spawn(move || {
            p.eat(&table, &n_eaters);
        })
    }).collect();

    // Философы приступили к приёму пищи
    for h in handles {
        h.join().unwrap();
    }
}

Результат:

Борис взял вилку № 1 слева и вилку № 2 справа и начал есть. Ест 1
Георгий взял вилку № 3 слева и вилку № 4 справа и начал есть. Ест 2
Борис закончил есть. Ест 1
Андрей взял вилку № 0 слева и вилку № 1 справа и начал есть. Ест 2
Георгий закончил есть. Ест 1
Владимир взял вилку № 2 слева и вилку № 3 справа и начал есть. Ест 2
Андрей закончил есть. Ест 1
Дмитрий взял вилку № 0 слева и вилку № 4 справа и начал есть. Ест 2
Владимир закончил есть. Ест 1
Дмитрий закончил есть. Ест 0

Здорово получилось, благодарю за тандемные итерации :slight_smile:

А чем fetch_add() и fetch_sub() не понравились?

Еще один момент - передавать в функцию eat() ссылку на Arc нет смысла. Это по сути указатель на указатель. Лучше передавать либо сам Arc<AtomicUsize>, либо &AtomicUsize.

Если внимательно посмотреть, то функция eat() требует &Table, а ей дают &Arc<Table>:

    let table = table.clone();
    let n_eaters = n_eaters.clone();

    thread::spawn(move || {
        p.eat(&table, &n_eaters);
    })

&Arc<Table> автоматически преобразуется в &Table благодаря тому, что для Arc<T> реализован типаж Deref<Target=T>. Этот же типаж позволяет использовать методы типа завернутого в Arc<_> как бы напрямую:

let a:Arc<u32> = Arc::new(42);
println!("{}", a.count_ones());

Преобразования при разыменовании

Поправил функцию eat в соответствии с рекомендациями. Код получился читабельнее:

    fn eat(&self, table: &Table, n_eaters: &AtomicUsize) {
        // Увеличилось количество одновременных едоков
        n_eaters.fetch_add(1, Ordering::SeqCst);             
        // Уменьшилось количество одновременных едоков
        n_eaters.fetch_sub(1, Ordering::SeqCst);

Кстати, информация из серии “Курьезы Ржавчины”.
Несмотря на то, что во всех примерах в документации atomic types заворачивают в Arc для передачи в другие потоки, на самом деле это не нужно. Можно передавать просто по ссылке.
Но тут есть одно большое и толстое НО. :wink:
В стабильной ветке без внешних крэйтов такую ссылку создать невозможно. Если не пользоваться чем-то вроде crossbeam, то ссылка должна иметь время жизни 'static. А создать static экземпляр AtomicUsize не выйдет т.к. нужно вызвать функцию new(). Придется использовать nightly с фичей #![feature(const_fn)] или lazy_static.