1
\$\begingroup\$

I've been studying the Banker's Algorithm and was curious if I could implement a similar resource management system using only Mutex and Condvar. The code I wrote is a synchronization program that allows multiple threads to request and use three types of resources (A, B, and C). Each resource has a certain quantity, and the threads request in order and use the resources, then return them. To manage synchronization, it uses Mutex and Condvar.

Key Operation Details

  1. Resource Initialization: Each resource (A, B, C) has an initial quantity (3, 4, 5), and Mutex and Condvar are used to manage them.
  2. Thread Creation: Three threads are created, and each thread requests resources within an infinite loop.
  3. Resource Request and Usage:
  • Each thread requests resources and waits using Condvar if the required quantity is not available.
  • The threads acquire the necessary amount of resources and immediately unlock them.
  • At the end of the loop, threads lock the resources again and increase the quantities.
  • When returning resources, Condvar is used to notify other waiting threads.

Here's my code:

use std::sync::{Arc, Mutex, Condvar};
use std::thread;
use rand::Rng;

fn main() {
    let resources = Arc::new((
        (Mutex::new(3), Condvar::new()),  // Amount of Resource A
        (Mutex::new(4), Condvar::new()),  // Amount of Resource B
        (Mutex::new(5), Condvar::new()),  // Amount of Resource C
    ));

    let mut handles = vec![];

    for _ in 0..3 {
        let res = Arc::clone(&resources);
        let handle = thread::spawn(move || {
            let mut rng = rand::thread_rng();

            loop {
                let a_amount = rng.gen_range(0..4);
                let b_amount = rng.gen_range(0..5);
                let c_amount = rng.gen_range(0..6);

                // Request and wait for resource A
                {
                    let mut a = res.0.0.lock().unwrap();
                    while *a < a_amount {
                        a = res.0.1.wait(a).unwrap();
                    }
                    *a -= a_amount;
                } // Drop the lock on resource A

                // Request and wait for resource B
                {
                    let mut b = res.1.0.lock().unwrap();
                    while *b < b_amount {
                        b = res.1.1.wait(b).unwrap();
                    }
                    *b -= b_amount;
                } // Drop the lock on resource B

                // Request and wait for resource C
                {
                    let mut c = res.2.0.lock().unwrap();
                    while *c < c_amount {
                        c = res.2.1.wait(c).unwrap();
                    }
                    *c -= c_amount;
                } // Drop the lock on resource C

                println!("Thread {:?} borrowed A:{}, B:{}, C:{}", thread::current().id(), a_amount, b_amount, c_amount);

                thread::sleep(std::time::Duration::from_millis(rng.gen_range(100..500)));

                // Return resources and notify waiting threads
                {
                    let mut a = res.0.0.lock().unwrap();
                    *a += a_amount;
                    res.0.1.notify_one();
                }

                {
                    let mut b = res.1.0.lock().unwrap();
                    *b += b_amount;
                    res.1.1.notify_one();
                }

                {
                    let mut c = res.2.0.lock().unwrap();
                    *c += c_amount;
                    res.2.1.notify_one();
                }
            }
        });

        handles.push(handle);
    }

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

Questions:

  1. Can this approach replace the Banker's Algorithm?

  2. While I believe there are no deadlock issues, could there be starvation or fairness problems? For example:

    Resource A has 10 units. The first thread constantly needs 5 units of Resource A in each loop. The second thread constantly needs 3 units of Resource A in each loop. The third thread constantly needs 9 units of Resource A in each loop.

    The third thread will forever sleep.

  3. Are there any other potential issues with this implementation?

\$\endgroup\$
2
  • \$\begingroup\$ Your code is apparently deadlock-free, but... it is not a banker's algorithm: there is no banker here. The code works only because all clients acquire resources in the same order. The whole point of the banker's algorithm is that the banker can see the worst case future when the order of request is not guaranteed. Consider process 1 requests resource A, and process 2 requests resource B - how do you know (without a banker) that the second request is safe? \$\endgroup\$
    – vnp
    Commented May 18 at 21:10
  • \$\begingroup\$ @vnp Thank you for your response. I realized that I misunderstood the banker's algorithm. I posted my question hastily without fully understanding the algorithm. \$\endgroup\$
    – ybjeon01
    Commented May 19 at 6:53

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.