concurrency - que - Los filósofos gastronómicos de la documentación de Rust no comen al mismo tiempo

filosofos que hablen de la alimentacion

Question

Intento seguir el ejemplo de los filósofos de la comida de la documentación de Rust. Código final del enlace:

use std::thread;
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_ms(150);
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", 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("Judith Butler", 0, 1),
        Philosopher::new("Gilles Deleuze", 1, 2),
        Philosopher::new("Karl Marx", 2, 3),
        Philosopher::new("Emma Goldman", 3, 4),
        Philosopher::new("Michel Foucault", 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();
    }
}

Ejecutando esto produce el siguiente resultado:

Michel Foucault is eating.
Michel Foucault is done eating.
Emma Goldman is eating.
Emma Goldman is done eating.
Karl Marx is eating.
Karl Marx is done eating.
Gilles Deleuze is eating.
Gilles Deleuze is done eating.
Judith Butler is eating.
Judith Butler is done eating.

Según la documentación, los filósofos deberían poder comer al mismo tiempo. El resultado deseado es algo como esto:

Gilles Deleuze is eating.
Emma Goldman is eating.
Emma Goldman is done eating.
Gilles Deleuze is done eating.
Judith Butler is eating.
Karl Marx is eating.
Judith Butler is done eating.
Michel Foucault is eating.
Karl Marx is done eating.
Michel Foucault is done eating.

Desafortunadamente, esto no sucede sin importar la frecuencia con la que se ejecuta el código.

Actualmente uso rustc 1.5.0 (3d7cd77e4 2015-12-04) en Windows, pero el problema también ocurre en el patio de juegos de Rust. Siéntase libre de probarlo usted mismo .

Answer 1

Esta es una pregunta semi-común para este ejemplo. Los programadores tienden a pensar en los subprocesos como "aleatorios" porque los subprocesos generalmente tienen diferentes tiempos de inicio y duración de ejecución. La mayoría de los usos de los hilos tampoco bloquean un recurso compartido durante toda la vida del hilo. Recuerde que los hilos son de tipo determinista, porque están programados por un algoritmo.

En este ejemplo, el hilo principal crea un montón de hilos y los agrega a una cola administrada por el sistema operativo. Eventualmente, el hilo principal es bloqueado o interrumpido por el programador. El planificador mira a través de la fila de hilos y le pregunta al "primero" si puede ejecutarse. Si es ejecutable, entonces se ejecuta por un segmento de tiempo o hasta que se bloquee.

El "primer" hilo corresponde al sistema operativo. Linux, por ejemplo, tiene múltiples planificadores ajustables que le permiten priorizar qué subprocesos se ejecutan. El planificador también puede elegir interrumpir un hilo antes o después

Si agrega una impresión al principio del hilo, puede ver que los hilos comienzan en un orden diferente. Aquí hay una tabla cuyo hilo comienza primero, basado en 100 carreras:

| Position | Emma Goldman | Gilles Deleuze | Judith Butler | Karl Marx | Michel Foucault |
|----------+--------------+----------------+---------------+-----------+-----------------|
|        1 |            4 |              9 |            81 |         5 |               1 |
|        2 |            5 |             66 |             9 |        17 |               3 |
|        3 |           19 |             14 |             5 |        49 |              13 |
|        4 |           46 |              9 |             3 |        20 |              22 |
|        5 |           26 |              2 |             2 |         9 |              61 |

Si estoy haciendo mis estadísticas correctamente, la orden de inicio más común es:

1. Judith Butler
2. Gilles Deleuze
3. Karl Marx
4. Emma Goldman
5. Michel Foucault

Tenga en cuenta que esto coincide con la secuencia de filósofos definidos en el código.

También tenga en cuenta que el algoritmo en sí impone un orden. Todos menos uno filósofo toma el tenedor con la mano izquierda primero, luego espera un poco. Si los hilos se ejecutan en orden, cada uno a su vez está esperando al anterior. La mayoría de los hilos dependen del hilo sentado a la "izquierda". Si nos imaginamos una mesa circular con todos sosteniendo un tenedor izquierdo (un punto muerto), y elegimos a una persona para darle un tenedor adicional (rompiendo el punto muerto), entonces se puede ver que habría una cascada de personas capaces de comer.

¡También recuerda que println! usa la salida estándar; un recurso global mutable que debe estar protegido por un mutex. Como tal, la impresión puede hacer que el hilo se bloquee y reprograme.

Estoy en OS X, lo que probablemente explica el orden que obtengo de forma semi-consistente que es diferente al tuyo.

Answer 2

La implementación del problema y la salida sugerida no coinciden debido a la suspensión entre los tenedores de recolección.

No estoy seguro de por qué Michel Foucault siempre comienza primero (probablemente la manera en que funciona el envío del hilo), pero el resto se explica fácilmente.

Debido a la pausa (*) entre agarrar la horquilla de la mano principal y la de la mano, hay dos fases:

• Fase 1: toma tu tenedor de mano principal
• Fase 2: toma tu tenedor de mano

Después de la fase 1:

• Fork 0 está en la mano de Michel Foucault o Judith Butler
• Tenedor 1 está en la mano de Gilles Deleuze
• Tenedor 2 está en la mano de Karl Marx
• Fork 3 está en la mano de Emma Goldman

¡Ahora, tenga en cuenta que solo Fork 4 está disponible para agarrar!

Tenemos dos casos en la Fase 2:

a) Judith agarró el Tenedor 0 b) Michel agarró el Tenedor 0

Comenzando con (a):

• Todos los filósofos están bloqueados excepto Emma, ​​quien agarra Fork 4
• Cuando Emma termina, libera Fork 3, que Karl toma de inmediato
• Cuando Karl termina ...
• Finalmente, Judith termina, libera Fork 0 y Michel come

En el caso (a), solo un filósofo puede comer en cualquier momento dado.

Nota: Forcé el caso deteniendo a Michel por 150ms antes de dejarlo agarrar su primer tenedor.

El caso (b) es más complicado ya que una vez más tenemos una carrera, esta vez entre Emma y Michel para agarrar el Tenedor 4. Somos caballeros, así que Emma irá primero y el caso de que Michel agarre el Tenedor 4 ahora se llama (c) :

• Emma agarra Fork 4, todos los otros filósofos están bloqueados
• Cuando Emma termina, lanza Fork 3 y 4, tanto Michel como Karl se lanzan sobre ellos
• Cuando Michel termina, lanza Forks 0 y 4, Judith lo agarra de inmediato ... y comienza a esperar; a nadie le importa Fork 4 ahora
• Cuando Karl termina, lanza Fork 2, que Gilles agarra de inmediato
• Cuando Gilles termina, libera Fork 1, que Judith inmediatamente toma
• Cuando Judith termina, los 5 han comido

Aquí observamos una concurrencia muy limitada: Emma golpea primero, y solo cuando termina, tenemos dos transmisiones paralelas, una con Michel y otra con Karl> Gilles> Judith.

Nota: Forcé el caso deteniendo a Michel durante 150ms antes de dejarle agarrar su segunda horquilla.

Finalmente, tenemos el caso (c):

• Michel agarra Fork 4, todos los otros filósofos están bloqueados
• Cuando Michel termina, lanza Fork 4 y 0, que son tomados respectivamente por Emma y Judith; Judith todavía está bloqueada (primero durmiendo, luego esperando el Tenedor 1) pero Emma comienza a comer
• Cuando Emma termina ...

Y aquí de nuevo, no concurrencia en absoluto.

(*) Esto no está garantizado en realidad, pero 150ms es un largo tiempo en computadoras, a menos que la máquina esté muy cargada, simplemente sucederá.

Si bien la solución propuesta por el libro funciona (no hay punto muerto en cualquier circunstancia), no muestra mucha concurrencia, por lo que es más una exhibición de Rust que una exhibición de concurrencia ... pero entonces, es el libro de Rust. ¡y no el de concurrencia!

No entiendo por qué el hilo de Michel se programa sistemáticamente primero en el parque infantil; pero puede contrarrestarse fácilmente haciéndole dormir específicamente.