Dining Philosophers

04.11.2019 21:39

Bữa tối của các triết gia (dining philosophers problem) là một ví dụ nổi tiếng khi nhắc đến các vấn đề trong bài toán xử lý concurrent.

Vấn đề được phát biểu như sau: Cho 5 triết gia ngồi chung một bàn tròn với 5 chiếc đũa xếp xem kẽ giữa 2 người ngồi cạnh nhau như hình

Dining Philosophers

img: sphof.readthedocs.io

Mỗi triết gia tìm cách để ăn được thức ăn từ đĩa của mình với điều kiện: “chỉ ai có 2 chiếc đũa cạnh mình mới được phép ăn”, do đó họ lần lượt đổi trạng thái giữa ăn (eating) và đợi (thinking) :)) Mỗi người sau khi giữa đôi đũa để ăn sau 1 khoảng thời gian phải bỏ lại 2 chiếc đũa về vị trí cũ để tiếp tục quá trình này. Yêu cầu: tìm một phương pháp đảm bảo để các triết gia đều có thể đk ăn / đợi đổi lượt để không ai bị chết đói (chỉ đợi chứ không được ăn).

Dựng môi trường thí nghiệm với Rust

Trong bài toán này, có 2 chủ thể chính cần quan tâm là triết gia (philosopher) và đũa (chopstick).

struct Chopstick {
    id: usize,
    by: Option<usize>, // philosopher's id, None in case of no owner
}

struct Philosopher {
    id: usize,
    left: Arc<Mutex<Chopstick>>,
    right: Arc<Mutex<Chopstick>>,
}

Sử dụng Mutex và smart pointer Arc ta có struct đại diện cho philosopher và chopstick như trên.

Với chopstick, có 2 methods cơ bản cần thực thi trên nó là lấy đũa và trả đũa về vị trí ban đầu (hay từ bỏ quyền sở hữu).

impl Chopstick {
    fn get(&mut self, p: &Philosopher) {
        if self.by != None {
            panic!(); // Invalid state. Since chopstick should not belong to anyone when a philosopher gets it
        }

        println!("Chopstick {}: Picked up by Philosopher {}", self.id, p.id);
        self.by = Some(p.id);
    }

    fn put(&mut self, p: &Philosopher) {
        if self.by != Some(p.id) {
            panic!(); // Invalid state. Since chopstick should belong to philosopher who trying to put it back
        }

        println!("Chopstick {}: Released by Philosopher {}", self.id, p.id);
        self.by = None;
    }
}

Với philosopher, cũng có 2 methods cơ bản cần được thực hiện trên nó như đã nêu trong vấn đề, đó là: ăn (khi có đũa) (eating) và đợi (vì là philosopher nên sẽ nghĩ lúc đợi :) )

impl Philosopher {
    fn think(&self) {
        println!("Philosopher {}: Thinking...", self.id);
        thread::sleep(Duration::from_secs(2));
    }

    fn eat(&self) {
        // Get left chopstick if available
        let mut left_cs = if let Ok(chopstick) = self.left.try_lock() {
            chopstick
        } else {
            println!("Philosopher {}: OOPS! Left chopstick not available. Waiting...", self.id);
            self.left.lock().unwrap()
        };
        left_cs.get(self);

        // Get right chopstick if available
        let mut right_cs = if let Ok(chopstick) = self.right.try_lock() {
            chopstick
        } else {
            println!("Philosopher {}: OOPS! Right chopstick not available. Waiting...", self.id);
            self.right.lock().unwrap()
        };
        right_cs.get(self);

        // Eat!
        println!("Philosopher {}: Eating...", self.id);
        thread::sleep(Duration::from_secs(4));

        // Put back both chopsticks
        right_cs.put(self);
        left_cs.put(self);
    }
}

Hàm eating là cần quan tâm đến ở bài toán này. Trong phiên bản trên, mỗi triết gia tìm cách lấy lần lượt đũa bên trái và phải của mình và trả lại vị trí sau khi đã ăn xong.

fn main() {
    let cs1 = Arc::new(Mutex::new(Chopstick::new(1)));
    let cs2 = Arc::new(Mutex::new(Chopstick::new(2)));
    let cs3 = Arc::new(Mutex::new(Chopstick::new(3)));
    let cs4 = Arc::new(Mutex::new(Chopstick::new(4)));
    let cs5 = Arc::new(Mutex::new(Chopstick::new(5)));

    let mut handles = vec![];
    handles.push(deploy(1, cs1.clone(), cs2.clone()));
    handles.push(deploy(2, cs2.clone(), cs3.clone()));
    handles.push(deploy(3, cs3.clone(), cs4.clone()));
    handles.push(deploy(4, cs4.clone(), cs5.clone()));
    handles.push(deploy(5, cs5.clone(), cs1.clone()));

    for handle in handles {
        let _ = handle.join();
    }
}

Thử nghiệm với phiên bản trên, kết quả như sau:

Philosopher 1: Thinking...
Philosopher 2: Thinking...
Philosopher 3: Thinking...
Philosopher 4: Thinking...
Philosopher 5: Thinking...
Chopstick 1: Picked up by Philosopher 1
Chopstick 4: Picked up by Philosopher 4
Chopstick 2: Picked up by Philosopher 2
Philosopher 2: OOPS! Right chopstick not available. Waiting...
Philosopher 4: OOPS! Right chopstick not available. Waiting...
Philosopher 1: OOPS! Right chopstick not available. Waiting...
Chopstick 5: Picked up by Philosopher 5
Philosopher 5: OOPS! Right chopstick not available. Waiting...
Chopstick 3: Picked up by Philosopher 3
Philosopher 3: OOPS! Right chopstick not available. Waiting...

Chết đứng :)) Trạng thái hiện tại của bàn ăn như trong kết quả: mỗi triết gia giữ 1 chiếc đũa (lock) và đợi vô hạn thời gian vì không ai đủ đũa để thực hiện ăn và trả lại đũa về vị trí.

Giải pháp

Nhìn vào kết quả trên, ta có thể nhận thấy mỗi triết gia trong lần lấy đũa đầu tiên chỉ có thể lấy đúng 1 đũa và số đũa đúng bằng số triết gia! Từ đó đưa đến cách thứ nhất để giải quyết vấn đề.

Cho số đũa tối thiểu bằng với số triết gia + 1

fn main() {
    ...
    let mut handles = vec![];
    handles.push(deploy(1, cs1.clone(), cs2.clone()));
    handles.push(deploy(2, cs2.clone(), cs3.clone()));
    handles.push(deploy(3, cs3.clone(), cs4.clone()));
    handles.push(deploy(4, cs4.clone(), cs5.clone()));
    // handles.push(deploy(5, cs5.clone(), cs1.clone()));

    for handle in handles {
        let _ = handle.join();
    }
}

Như vậy ở lần lấy đũa đầu tiên; triết gia cuối cùng (thứ 4) sẽ lấy được đôi đũa có id (4, 5) do không có tranh chấp quyền sử dụng đũa thứ 5 :))

Cách trên có thể đã giải quyết đk vấn đề tuy nhiên đã vi phạm điều kiện đề bài về số lượng triết gia và đũa. Nhìn lại vấn đề ta thấy: mỗi triết gia cố gắng tranh chấp quyền sở hữu 2 đũa với 2 người ngồi cạnh mình và mỗi người chỉ kịp lấy được (thắng) trong một trong 2 lần tranh chấp => lock. Từ đó dẫn đến hướng thứ 2 để giải quết

Giảm số lần tranh chấp để giành đũa của ít nhất 1 triết gia để đảm bảo có ít nhất 1 người có thể ăn.

Có 2 cách cơ bản để đạt được điều kiện này:

2.1. Yêu cầu mỗi triết gia ưu tiên giành đũa có id nhỏ hơn trong 2 chiếc cần giành (triết gia thứ 1 ưu tiên chiếc 1, triết gia thứ 2 ưu tiên chiếc 2,…)

Như vậy ở vị trí cuối cùng, triết gia thứ 5 sẽ ưu tiên chiếc đũa 1 thay vì chiếc đũa có id = 5, tránh tranh chấp với triết gia ngay trước mình (triết gia thứ 4) => triết gia thứ 4 có thể bắt đầu ăn.

2.2. Yêu cầu triết gia ở vị trí lẻ ưu tiên chiếc đũa phải, triết gia ở vị trí chẵn ưu tiên giành đũa ở bên trái (triết gia 1 ưu tiên chiếc 1, triết gia 2 ưu tiên chiếc 3,…)

Với cách này, các chiếc đũa 2, 4 có độ ưu tiên thấp hơn đối với tất cả các triết gia, do đó triết gia đã có trong tay 1 chiếc đũa có thể dễ dàng lấy chúng mà không gặp phải tranh chấp. Với bài toán 5 triết gia, ở lượt đầu tiên triết gia thứ nhất (đôi đũa 1,2) và thứ tư (đôi đũa 4,5) có thể bắt đầu ăn.

Ở một hướng khác, có thể phát triển hướng tiếp cận giảm thiểu tránh chấp trên bằng việc:

Đảm bảo khi bất cứ triết gia nào có đũa, đó sẽ là một đôi thay vì một chiếc.

Như vậy mỗi triết gia sẽ: hoặc là có 1 đôi đũa và bắt đầu ăn, hoặc là không có chiếc nào và ngồi nghĩ :))

Việc này đảm bảo khi đang ở trạng thái nghĩ, không có triết gia nào giữ đũa khi nghĩ gây cản trở cho những triết gia khác. Có 2 cách để thực hiện điều kiện này:

3.1. Thêm vào bữa tối một bồi bàn, bất cứ triết gia muốn sở hữu đũa phải hỏi bồi bàn và người này sẽ giao cho người yêu cầu đôi đũa để bắt đầu ăn hoặc trả lời đũa đã được mượn và triết gia đó ngồi đợi trước khi tiếp tục hỏi đũa.

Việc thực thi của bồi bàn cũng khá đơn giản: quản lý trạng thái của các đôi đũa xem chúng đang thuộc về ai và giao cho người yêu cầu khi đôi đũa đang free, khi đám đông hỗn loạn, thêm một người quản lý để điều phố là cách nghĩ thông dụng và khá hiệu quả :)) Tuy nhiên cách này yêu cầu sửa đổi khá nhiều: mỗi triết gia thay vì yêu cầu 1 chiếc đũa cần yêu cầu 1 đôi đũa; và bản thân bồi bàn cũng yêu cầu resource để thực thi (chạy trong 1 thread giống như các triết gia), đồng thời vai trò tập trung của bồi bàn khiến cho chương trình có thể crash hoặc trở lại treo trong trường hợp lỗi ở thread bồi bàn.

3.2. Yêu cầu mỗi triết gia sẽ tìm cách giành lấy một đôi đũa thay vì giành từng chiếc một của một đôi.

Cùng một hướng tiếp cận tránh lock khi triết gia giữ 1 chiếc đũa cản trở các triết gia khác bằng việc giành 1 đôi thay vì một chiếc; ta có thể implement một cách đơn giản như sau:

fn eat(&self) {
    // check left chopstick, wait if unavailable
    let mut left_cs = if let Ok(chopstick) = self.left.try_lock() {
        chopstick
    } else {
        println!("Philosopher {}: OOPS! Left chopstick not available. Waiting...", self.id);
        self.left.lock().unwrap()
    };

    // check right chopstick, wait if unavailable
    let mut right_cs = if let Ok(chopstick) = self.right.try_lock() {
        chopstick
    } else {
        println!("Philosopher {}: OOPS! Right chopstick not available. Waiting...", self.id);
        self.right.lock().unwrap()
    };

    // get both chopsticks if available
    left_cs.get(self);
    right_cs.get(self);

    println!("Philosopher {}: Eating...", self.id);
    thread::sleep(Duration::from_secs(4));

    right_cs.put(self);
    left_cs.put(self);
}

DONE! Với điều kiện này, ở lượt đầu tiên, triết gia thứ nhất (đôi đũa 1,2) và thứ ba (đôi đũa 3,4) giật được đôi đũa của mình và có thể bắt đầu ăn :))

Philosopher 1: Thinking...
Philosopher 3: Thinking...
Philosopher 4: Thinking...
Philosopher 2: Thinking...
Philosopher 5: Thinking...
Chopstick 1: Picked up by Philosopher 1
Philosopher 2: OOPS! Left chopstick not available. Waiting...
Philosopher 4: OOPS! Left chopstick not available. Waiting...
Chopstick 2: Picked up by Philosopher 1
Philosopher 1: Eating...
Philosopher 5: OOPS! Right chopstick not available. Waiting...
Chopstick 3: Picked up by Philosopher 3
Chopstick 4: Picked up by Philosopher 3
Philosopher 3: Eating...
Chopstick 2: Released by Philosopher 1
Chopstick 1: Released by Philosopher 1
Chopstick 4: Released by Philosopher 3
Chopstick 3: Released by Philosopher 3
Philosopher 3: Thinking...
Philosopher 1: Thinking...
Philosopher 4: OOPS! Right chopstick not available. Waiting...
...

Một cách khác là Chandy/Misra solution có thể tìm thấy ở đây.

Ref: