data structures - studio - Bloqueo manual con Rust

visual studio installer

Question

Estoy tratando de escribir una implementación de union-find en Rust. Esto es muy fácil de implementar en lenguajes como C, y aún tiene un complejo análisis de tiempo de ejecución.

Tengo problemas para obtener la semántica de mutex de Rust para permitir el bloqueo iterativo mano a mano.

Así es como llegué a donde estoy ahora.

Primero, esta es una implementación muy simple de parte de la estructura que quiero en C:

#include <stdlib.h>

struct node {
  struct node * parent;
};

struct node * create(struct node * parent) {
  struct node * ans = malloc(sizeof(struct node));
  ans->parent = parent;
  return ans;
}

struct node * find_root(struct node * x) {
  while (x->parent) {
    x = x->parent;
  }
  return x;
}

int main() {
  struct node * foo = create(NULL);
  struct node * bar = create(foo);
  struct node * baz = create(bar);
  baz->parent = find_root(bar);
}

Tenga en cuenta que la estructura de los punteros es la de un árbol invertido ; punteros múltiples pueden apuntar a una sola ubicación, y no hay ciclos.

En este punto, no hay compresión de ruta.

Aquí hay una traducción de Rust. Elegí usar el tipo de puntero contado de referencia de Rust para admitir el tipo de árbol invertido al que hice referencia anteriormente.

Tenga en cuenta que esta implementación es mucho más detallada, posiblemente debido a la mayor seguridad que ofrece Rust, pero posiblemente debido a mi inexperiencia con Rust.

use std::rc::Rc;

struct Node {
    parent: Option<Rc<Node>>
}

fn create(parent: Option<Rc<Node>>) -> Node {
    Node {parent: parent.clone()}
}

fn find_root(x: Rc<Node>) -> Rc<Node> {
    let mut ans = x.clone();
    while ans.parent.is_some() {
        ans = ans.parent.clone().unwrap();
    }
    ans
}

fn main() {
    let foo = Rc::new(create(None));
    let bar = Rc::new(create(Some(foo.clone())));
    let mut prebaz = create(Some(bar.clone()));
    prebaz.parent = Some(find_root(bar.clone()));
}

La compresión de ruta vuelve a find_root cada nodo a lo largo de una ruta a la raíz cada vez que se llama a find_root . Para agregar esta característica al código C, solo se necesitan dos nuevas funciones pequeñas:

void change_root(struct node * x, struct node * root) {
  while (x) {
    struct node * tmp = x->parent;
    x->parent = root;
    x = tmp;
  }
}

struct node * root(struct node * x) {
  struct node * ans = find_root(x);
  change_root(x, ans);
  return ans;
}

La función change_root hace todo el re-parenting, mientras que la root la función es simplemente un wrapper para usar los resultados de find_root para reaparecer los nodos en la ruta a la raíz.

Para hacer esto en Rust, decidí que tendría que usar un Mutex lugar de solo un puntero contado de referencia, ya que la interfaz Rc solo permite el acceso mutable mediante copy-on-write cuando hay más de un puntero al elemento en vivo. Como resultado, todo el código debería cambiar. Antes de llegar a la parte de compresión de ruta, me colgué en find_root :

use std::sync::{Mutex,Arc};

struct Node {
    parent: Option<Arc<Mutex<Node>>>
}

fn create(parent: Option<Arc<Mutex<Node>>>) -> Node {
    Node {parent: parent.clone()}
}

fn find_root(x: Arc<Mutex<Node>>) -> Arc<Mutex<Node>> {
    let mut ans = x.clone();
    let mut inner = ans.lock();
    while inner.parent.is_some() {
        ans = inner.parent.clone().unwrap();
        inner = ans.lock();
    }
    ans.clone()
}

Esto produce el error (con 0.12.0)

error: cannot assign to `ans` because it is borrowed
ans = inner.parent.clone().unwrap();

note: borrow of `ans` occurs here
let mut inner = ans.lock();

Lo que creo que necesito aquí es el bloqueo manual. Para el camino A -> B -> C -> ..., necesito bloquear A, bloquear B, desbloquear A, bloquear C, desbloquear B, ... Por supuesto, podría mantener todos los bloqueos abiertos: bloqueo A, bloquear B, bloquear C, ... desbloquear C, desbloquear B, desbloquear A, pero esto parece ineficaz.

Sin embargo, Mutex no ofrece desbloqueo, y usa RAII en su lugar. ¿Cómo puedo lograr el bloqueo manual en Rust sin poder invocar directamente el unlock ?

EDITAR : Como se señaló en los comentarios, podría usar Rc<RefCell<Node>> lugar de Arc<Mutex<Node>> . Hacerlo conduce al mismo error de compilación.

Para mayor claridad sobre lo que trato de evitar usando el bloqueo manual, aquí hay una versión de RefCell que compila pero usa el espacio lineal en la longitud de la ruta.

fn find_root(x: Rc<RefCell<Node>>) -> Rc<RefCell<Node>> {
    let mut inner : RefMut<Node> = x.borrow_mut();
    if inner.parent.is_some() {
        find_root(inner.parent.clone().unwrap())
    } else {
        x.clone()
    }
}

Answer 1

Aunque no es la respuesta a su pregunta literal (bloqueo de transferencia), union-find con unión ponderada y compresión de ruta puede ser muy simple en Rust:

fn unionfind<I: Iterator<(uint, uint)>>(mut iterator: I, nodes: uint) -> Vec<uint>
{
    let mut root = Vec::from_fn(nodes, |x| x);
    let mut rank = Vec::from_elem(nodes, 0u8);

    for (mut x, mut y) in iterator
    {
        // find roots for x and y; do path compression on look-ups
        while (x != root[x]) { root[x] = root[root[x]]; x = root[x]; }
        while (y != root[y]) { root[y] = root[root[y]]; y = root[y]; }

        if x != y
        {
            // weighted union swings roots
            match rank[x].cmp(&rank[y])
            {
                Less    => root[x] = y,
                Greater => root[y] = x,
                Equal   =>
                {
                    root[y] = x; 
                    rank[x] += 1 
                },
            }
        }
    }
}

Tal vez el meta-punto es que el algoritmo union-find puede no ser el mejor lugar para manejar la propiedad del nodo, y al usar referencias a la memoria existente (en este caso, simplemente usando uint identificadores para los nodos) sin afectar el ciclo de vida del nodos hace una implementación mucho más simple, si puede salirse con la suya, por supuesto.

Answer 2

Creo que esto se ajusta al criterio del bloqueo manual .

use std::sync::Mutex;

fn main() {
    // Create a set of mutexes to lock hand-over-hand
    let mutexes = Vec::from_fn(4, |_| Mutex::new(false));

    // Lock the first one
    let val_0 = mutexes[0].lock();
    if !*val_0 {
        // Lock the second one
        let mut val_1 = mutexes[1].lock();
        // Unlock the first one
        drop(val_0);
        // Do logic
        *val_1 = true;
    }

    for mutex in mutexes.iter() {
        println!("{}" , *mutex.lock());
    }
}

Editar # 1

¿Funciona cuando el bloqueo n + 1 protege el acceso al bloqueo n?

Si te refieres a algo que podría tener la forma siguiente, entonces creo que la respuesta es no.

struct Level {
  data: bool,
  child: Option<Mutex<Box<Level>>>,
}

Sin embargo, es sensato que esto no debería funcionar . Cuando envuelve un objeto en un mutex, entonces está diciendo "Todo el objeto está a salvo". No puede decir que "todo el pastel es seguro" y "estoy comiendo las cosas debajo de la corteza" al mismo tiempo. Tal vez descartas la seguridad creando un Mutex<()> y bloqueas eso?

Answer 3

En IRC, Jonathan Reem señaló que inner está tomando prestado hasta el final de su alcance léxico, que está demasiado lejos para lo que estaba preguntando. Inlinea produce lo siguiente, que compila sin error:

fn find_root(x: Arc<Mutex<Node>>) -> Arc<Mutex<Node>> {
    let mut ans = x.clone();
    while ans.lock().parent.is_some() {
        ans = ans.lock().parent.clone().unwrap();
    }
    ans
}

EDITAR: Como señala Francis Gagné, esto tiene una condición de carrera, ya que la cerradura no se extiende lo suficiente. Aquí hay una versión modificada que solo tiene una llamada lock() ; tal vez no es vulnerable al mismo problema.

fn find_root(x: Arc<Mutex<Node>>) -> Arc<Mutex<Node>> {
    let mut ans = x.clone();
    loop {
        ans = {
            let tmp = ans.lock();
            match tmp.parent.clone() {
               None => break,
               Some(z) => z
            }
        }
    }
    ans
}

EDIT 2 : Esto solo tiene un bloqueo a la vez, y también lo es el ritmo. Todavía no sé cómo hacer el bloqueo manual.

Answer 4

Esta no es todavía la respuesta a su pregunta literal de cómo hacer el bloqueo manual, que solo debería ser importante en una configuración concurrente (o si alguien más lo forzó a usar referencias Mutex a nodos). En cambio, es cómo hacer esto con Rc y RefCell , que pareces estar interesado.

RefCell solo permite escrituras mutables cuando se mantiene una referencia mutable. Es importante destacar que los objetos Rc<RefCell<Node>> no son referencias mutables. Las referencias mutables de las que habla son los resultados de llamar a borrow_mut() en el objeto Rc<RefCell<Node>> , y siempre que lo haga en un ámbito limitado (por ejemplo, el cuerpo del bucle while), lo hará estar bien.

Lo importante que ocurre en la compresión de rutas es que el next objeto Rc mantendrá vivo el resto de la cadena mientras gira el puntero principal para que el node apunte a la root . Sin embargo, no es una referencia en el sentido de Rust de la palabra.

struct Node
{
    parent: Option<Rc<RefCell<Node>>>
}

fn find_root(mut node: Rc<RefCell<Node>>) -> Rc<RefCell<Node>>
{
    while let Some(parent) = node.borrow().parent.clone()
    {
        node = parent;
    }

    return node;
}

fn path_compress(mut node: Rc<RefCell<Node>>, root: Rc<RefCell<Node>>)
{
    while node.borrow().parent.is_some()
    {
        let next = node.borrow().parent.clone().unwrap();
        node.borrow_mut().parent = Some(root.clone());
        node = next;
    }
}

Esto funciona bien para mí con el arnés de prueba que usé, aunque todavía puede haber errores. ¡Ciertamente compila y funciona sin panic! debido a tratar de borrow_mut() algo que ya está prestado. En realidad, puede producir la respuesta correcta, eso depende de usted.

Answer 5

Podemos atravesar fácilmente esta lista con un poco de unsafe , lo que es necesario para decirle al prestamista una pequeña idea que conocemos, pero que no puede saberlo. .

Pero primero, formulemos claramente el problema:

• Queremos atravesar una lista vinculada cuyos nodos se almacenan como Arc<Mutex<Node>> para obtener el último nodo de la lista
• Necesitamos bloquear cada nodo en la lista a medida que avanzamos en el camino de tal forma que otro recorrido simultáneo tenga que seguir estrictamente detrás de nosotros y no pueda ensuciar nuestro progreso.

Antes de entrar en los detalles esenciales, intentemos escribir la firma para esta función:

fn find_root(node: Arc<Mutex<Node>>) -> Arc<Mutex<Node>> ;

Ahora que conocemos nuestro objetivo, podemos comenzar a implementarlo; aquí hay un primer intento:

fn find_root(incoming: Arc<Mutex<Node>>) -> Arc<Mutex<Node>> {
    // We have to separate this from incoming since the lock must
    // be borrowed from incoming, not this local node.  
    let mut node = incoming.clone();
    let mut lock = incoming.lock();

    // Could use while let but that leads to borrowing issues.
    while lock.parent.is_some() {
       node = lock.parent.as_ref().unwrap().clone(); // !! uh-oh !!
       lock = node.lock();
    }

    node
} 

Si intentamos compilar esto, ¡rustc mostrará un error en la línea marcada !! uh-oh !! !! uh-oh !! , diciéndonos que no podemos salir del nodo mientras el lock aún existe, ya que el lock es un node préstamo. ¡Este no es un error espurio! Los datos en el lock pueden desaparecer tan pronto como lo haga el node ; es solo porque sabemos que podemos mantener el lock datos apuntando a la ubicación válida y en la misma memoria, incluso si movemos el node , podemos solucionarlo.

La idea clave aquí es que la vida útil de los datos contenidos en un Arc es dinámica, y es difícil para el corrector de préstamos hacer las inferencias que podamos sobre exactamente cuánto tiempo son válidos los datos dentro de un Arc .

Esto sucede de vez en cuando al escribir óxido; usted tiene más conocimiento sobre la vida y la organización de sus datos que rustc, y desea poder expresar ese conocimiento al compilador, diciendo "confía en mí". Entrar: unsafe - nuestra forma de decirle al compilador que sabemos más que eso, y debería permitirnos informarle de las garantías que conocemos, pero no es así.

En este caso, la garantía es bastante simple: vamos a reemplazar el nodo mientras el bloqueo aún existe, pero no vamos a garantizar que los datos dentro del bloqueo sigan siendo válidos aunque el nodo desaparezca. Para expresar esta garantía, podemos usar mem::transmute , una función que nos permite reinterpretar el tipo de cualquier variable, simplemente utilizándola para cambiar la vida útil del bloqueo devuelto por el nodo para que sea un poco más larga de lo que realmente es.

Para asegurarnos de mantener nuestra promesa, vamos a usar otra variable de transferencia para mantener el nodo mientras reasignamos el bloqueo, aunque esto mueva el nodo (cambiando su dirección) y el prestamista se enojará con nosotros, sabemos que está bien desde el lock no apunta al nodo, apunta a los datos dentro del node , cuya dirección (en este caso, ya que está detrás de un Arc ) no cambiará.

Antes de llegar a la solución, es importante tener en cuenta que el truco que estamos utilizando aquí solo es válido porque estamos usando un Arc . El comprobador de préstamos nos advierte de un posible error grave: si el Mutex se mantuvo en línea y no en un Arc , este error sería una prevención correcta de un uso después de la MutexGuard , donde el MutexGuard mantenido en la lock intentaría desbloquear un Mutex que ya se ha eliminado, o al menos movido a otra ubicación de memoria.

use std::mem;
use std::sync::{Arc, Mutex};

fn find_root(incoming: Arc<Mutex<Node>>) -> Arc<Mutex<Node>> {
    let mut node = incoming.clone();
    let mut handoff_node;
    let mut lock = incoming.lock();

    // Could use while let but that leads to borrowing issues.
    while lock.parent.is_some() {
       // Keep the data in node around by holding on to this `Arc`.
       handoff_node = node;

       node = lock.parent.as_ref().unwrap().clone();

       // We are going to move out of node while this lock is still around,
       // but since we kept the data around it''s ok.
       lock = unsafe { mem::transmute(node.lock()) };
    }

    node
} 

Y, así de simple, rustc está contento y tenemos un bloqueo mano a mano, ya que el último bloqueo se libera solo después de haber adquirido el nuevo bloqueo.

Hay una pregunta no respondida en esta implementación que todavía no he recibido una respuesta, que es si la caída del valor anterior y la asignación de un nuevo valor a una variable es un atómico garantizado, si no, hay una carrera condición donde se libera el bloqueo anterior antes de que se adquiera el nuevo bloqueo en la asignación de lock . Es bastante trivial solucionar este problema simplemente teniendo otra variable holdover_lock y moviendo el antiguo bloqueo hacia él antes de reasignarlo, luego soltándolo después de reasignar el lock .

Esperemos que esto aborde completamente su pregunta y muestre qué tan unsafe se puede utilizar para solucionar las "deficiencias" en el comprobador de préstamos cuando realmente sabe más. Me gustaría desear que los casos en los que sabes más que el corrector de préstamos sean raros, y la transmutación de vidas no es un comportamiento "habitual".

Usar Mutex de esta manera, como puedes ver, es bastante complejo y tienes que lidiar con muchas , muchas , posibles fuentes de una condición de carrera y ¡es posible que ni siquiera las haya atrapado a todas! A menos que realmente necesite que esta estructura sea accesible desde muchos hilos, probablemente sería mejor usar Rc y RefCell , si lo necesita, ya que esto hace las cosas mucho más fáciles.

Answer 6

Como señalaron Frank Sherry y otros, no debería usar Arc / Mutex cuando tiene un solo hilo. Pero su código estaba desactualizado, así que aquí está el nuevo (para la versión 1.0.0alpha2). Esto tampoco requiere espacio lineal (como el código recursivo dado en la pregunta).

struct Node {
    parent: Option<Rc<RefCell<Node>>>
}

fn find_root(node: Rc<RefCell<Node>>) -> Rc<RefCell<Node>> {
    let mut ans = node.clone(); // Rc<RefCell<Node>>
    loop {
        ans = {
            let ans_ref = ans.borrow(); // std::cell::Ref<Node>
            match ans_ref.parent.clone() {
                None => break,
                Some(z) => z
            }
        } // ans_ref goes out of scope, and ans becomes mutable
    }
    ans
}

fn path_compress(mut node: Rc<RefCell<Node>>, root: Rc<RefCell<Node>>) {
    while node.borrow().parent.is_some() {
        let next = {
            let node_ref = node.borrow();
            node_ref.parent.clone().unwrap()
        };
        node.borrow_mut().parent = Some(root.clone());
        // RefMut<Node> from borrow_mut() is out of scope here...
        node = next; // therefore we can mutate node
    }
}

Nota para principiantes: los punteros son desreferenciados automáticamente por operador de puntos. ans.borrow() realidad significa (*ans).borrow() . Intencionalmente utilicé diferentes estilos para las dos funciones.