Cogs and Levers A blog full of technical stuff

Dining Philosophers

01 Nov 2024

Introduction

The dining philosophers problem is a classic synchronization and concurrency problem in computer science, illustrating the challenges of managing shared resources. In this post, I’ll walk through an implementation of the dining philosophers problem in Rust, explaining each part of the code to show how it tackles potential deadlocks and resource contention.

You can find the full code listing for this article here.

The Problem

Imagine five philosophers seated at a round table.

Between each philosopher is a fork, and to eat, each philosopher needs to hold the fork to their left and the fork to their right.

Philosophers

This setup leads to a potential deadlock if each philosopher picks up their left fork at the same time, preventing any of them from picking up their right fork.

To avoid this deadlock, our implementation uses randomized behavior to increase concurrency and reduce contention for resources.

Solving the Problem

The Philosopher

First of all, we need to define a Philosopher:

struct Philosopher {
    name: String,
    left: Arc<Mutex<i8>>,
    right: Arc<Mutex<i8>>,
    eaten: Arc<Mutex<i32>>
}
  • name gives this Philosopher a name on screen
  • left and right are the two forks that this Philosopher is allowed to eat with
  • eaten is a counter, so we can see if anyone starves!

Arc<Mutex<T>>

left, right, and eaten are all typed with Arc<Mutex<T>>.

We use Arc<Mutex<T>> to share resources safely across threads. Arc (atomic reference counting) allows multiple threads to own the same resource, and Mutex ensures that only one thread can access a resource at a time.

Implementing the Philosopher Struct

We can simplify building one of these structs with a new method:

impl Philosopher {
    fn new(name: &str, left: Arc<Mutex<i8>>, right: Arc<Mutex<i8>>) -> Self {
        Philosopher {
            name: name.to_string(),
            left,
            right,
            eaten: Arc::new(Mutex::new(0)),
        }
    }

Dining

We now want to simulate a Philosopher attempting to eat. This is where the Philosopher tries to acquire the forks needed.

We do this with the dine function.

fn dine(&self) {
    let mut rng = rand::thread_rng();

    loop {
        // Randomize the order in each dining attempt
        let reverse_order = rng.gen_bool(0.5);

Using a random number generator (rng), each philosopher randomly decides in which order to try to pick up forks. This randomness reduces the chances of all philosophers trying to grab the same forks simultaneously.

Finding a Fork

The philosopher selects which fork to pick up first based on the randomized reverse_order.

        let left_first = if reverse_order {
            &self.right
        } else {
            &self.left
        };

        let right_second = if reverse_order {
            &self.left
        } else {
            &self.right
        };

Here, if reverse_order is true, the philosopher picks up the right fork first; otherwise, they pick up the left fork first.

Attempting to Eat

To avoid deadlock, the philosopher only eats if they can successfully lock both forks. If both locks are acquired, they eat, increment their eaten counter, and release the locks after eating.

        if let Ok(_first) = left_first.try_lock() {
            if let Ok(_second) = right_second.try_lock() {
                println!("{} is eating ({})", self.name, *self.eaten.lock().unwrap());

                // Update eating counter
                if let Ok(mut count) = self.eaten.lock() {
                    *count += 1;
                }

                thread::sleep(Duration::from_millis(1000));
                println!("{} has finished eating", self.name);
            } else {
                println!("{} couldn't get both forks and is thinking", self.name);
            }
        } else {
            println!("{} couldn't get both forks and is thinking", self.name);
        }

If either lock fails, the philosopher “thinks” (retries later). The use of try_lock ensures that philosophers don’t wait indefinitely for forks, reducing the chance of deadlock.

After eating, a philosopher sleeps for a random time to avoid overlapping lock attempts with other philosophers.

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

Sitting Down to Eat

Now we set the table, and get the Philosophers to sit down.

fn main() {
    let forks: Vec<Arc<Mutex<i8>>> = (0..5)
            .map(|i| Arc::new(Mutex::new(i)))
            .collect();

    let philosophers = vec![
        Philosopher::new("Jane", forks[0].clone(), forks[1].clone()),
        Philosopher::new("Sally", forks[1].clone(), forks[2].clone()),
        Philosopher::new("Margaret", forks[2].clone(), forks[3].clone()),
        Philosopher::new("Kylie", forks[3].clone(), forks[4].clone()),
        Philosopher::new("Marie", forks[4].clone(), forks[0].clone()),
    ];

Each philosopher is created with the forks on their left and right. The Arc wrapper ensures each fork can be safely shared across threads.

    let handles: Vec<_> = philosophers.into_iter().map(|p| {
        thread::spawn(move || {
            p.dine();
        })
    }).collect();

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

Each philosopher’s dine function runs in its own thread, allowing them to operate concurrently. The main thread then waits for all philosopher threads to finish.

Results

Your mileage may vary due to the random number generator, but you can see even distribution between the Philosophers as the simulation runs. For brevity, I stripped all the other messages out of this output.

Jane is eating (0)
Kylie is eating (0)
Marie is eating (0)
Margaret is eating (0)
Kylie is eating (1)
Sally is eating (0)
Jane is eating (1)
Margaret is eating (1)
Sally is eating (1)
Marie is eating (1)
Margaret is eating (2)
Jane is eating (2)
Margaret is eating (3)
Marie is eating (2)
Margaret is eating (4)
Jane is eating (3)
Kylie is eating (2)
Sally is eating (2)

Conclusion

This implementation uses randomized fork-picking order and non-blocking try_lock calls to minimize the risk of deadlock and improve concurrency. Each philosopher tries to acquire forks in different orders and backs off to “think” if they can’t proceed, simulating a real-world attempt to handle resource contention without deadlock.

This approach highlights Rust’s power in building concurrent, safe programs where shared resources can be managed cleanly with Arc and Mutex. The dining philosophers problem is a great example of Rust’s capabilities in handling complex synchronization issues, ensuring a safe and efficient solution.

Revisiting SPR in Haskell

31 Oct 2024

Introduction

Quite some time ago, I wrote a post about a very simple Scissors, Paper, Rock implementation using Haskell. In today’s post, I’d like to revisit that code and clean it up with some tests now that I know a little more.

Avoiding so much do

One point is to avoid the use of do notation, when it’s not needed.

-- Map string to Move
str2Move :: String -> Move
str2Move "s" = Scissors
str2Move "p" = Paper
str2Move "r" = Rock
str2Move _   = Unknown

-- Determine the move that beats the given move
getWinner :: Move -> Move
getWinner Scissors = Rock
getWinner Rock     = Paper
getWinner Paper    = Scissors
getWinner Unknown  = Unknown

These functions were previously do notated, can be simplified back to these translations. The usage of pattern matching here also improves the readability of the code.

Improved randomness

What was being used before getStdGen has now been replaced with newStdGen, which gives us a new random generator per game, improving the randomness.

main :: IO ()
main = do
   gen <- newStdGen

Tests

To verify our game logic, some tests have been added using Hspec.

-- MainSpec.hs
module MainSpec where

import Test.Hspec
import System.Random (mkStdGen)
import Main  -- Import your module here

main :: IO ()
main = hspec $ do
    describe "str2Move" $ do
        it "converts 's' to Scissors" $
            str2Move "s" `shouldBe` Scissors
        it "converts 'p' to Paper" $
            str2Move "p" `shouldBe` Paper
        it "converts 'r' to Rock" $
            str2Move "r" `shouldBe` Rock
        it "returns Unknown for invalid input" $
            str2Move "x" `shouldBe` Unknown

    describe "getWinner" $ do
        it "Rock beats Scissors" $
            getWinner Scissors `shouldBe` Rock
        it "Paper beats Rock" $
            getWinner Rock `shouldBe` Paper
        it "Scissors beat Paper" $
            getWinner Paper `shouldBe` Scissors
        it "Unknown returns Unknown" $
            getWinner Unknown `shouldBe` Unknown

    describe "getOutcome" $ do
        it "returns Draw when both moves are the same" $
            getOutcome Rock Rock `shouldBe` Draw
        it "returns Winner when player beats CPU" $
            getOutcome Rock Scissors `shouldBe` Winner
        it "returns Loser when CPU beats player" $
            getOutcome Scissors Rock `shouldBe` Loser
        it "returns ND for Unknown player move" $
            getOutcome Unknown Rock `shouldBe` ND
        it "returns ND for Unknown CPU move" $
            getOutcome Rock Unknown `shouldBe` ND

    describe "getCpuMove" $ do
        it "returns Rock for seed 1" $
            getCpuMove (mkStdGen 1) `shouldBe` Rock
        it "returns Scissors for seed 2" $
            getCpuMove (mkStdGen 2) `shouldBe` Scissors
        it "returns Paper for seed 3" $
            getCpuMove (mkStdGen 3) `shouldBe` Paper

Here is the full code listing:

module Main where

import System.IO
import System.Random

data Move = Scissors | Paper | Rock | Unknown deriving (Eq, Show)
data Outcome = Winner | Draw | Loser | ND deriving (Show)

-- Map string to Move
str2Move :: String -> Move
str2Move "s" = Scissors
str2Move "p" = Paper
str2Move "r" = Rock
str2Move _   = Unknown

-- Determine the move that beats the given move
getWinner :: Move -> Move
getWinner Scissors = Rock
getWinner Rock     = Paper
getWinner Paper    = Scissors
getWinner Unknown  = Unknown

-- Calculate the outcome based on player and CPU moves
getOutcome :: Move -> Move -> Outcome
getOutcome player cpu
   | player == Unknown || cpu == Unknown = ND
   | player == cpu = Draw
   | cpu == getWinner player = Loser
   | otherwise = Winner

-- Generate a CPU move based on random number
getCpuMove :: StdGen -> Move
getCpuMove gen = case fst (randomR (1, 3) gen :: (Int, StdGen)) of
   1 -> Rock
   2 -> Scissors
   3 -> Paper
   _ -> Unknown  -- This case is unreachable but keeps pattern exhaustive

main :: IO ()
main = do
   gen <- newStdGen  -- Get a new generator each round for more randomness
   putStr "Enter your choice (s, p, or r): "
   hFlush stdout
   line <- getLine

   let player = str2Move line
   if player == Unknown
      then putStrLn "Invalid input! Please enter 's', 'p', or 'r'."
      else do
         let cpu = getCpuMove gen
         let outcome = getOutcome player cpu

         putStrLn $ "Player Chose: " ++ show player
         putStrLn $ "CPU Chose   : " ++ show cpu
         putStrLn $ "Outcome     : " ++ show outcome

Learning Rust

30 Oct 2024

Introduction

In an attempt to put myself on an accelerated learning course about Rust, I’ve produced a number of articles in a “Learn Rust” series.

Part 1-3: Core Concepts

These articles introduce you to Rust’s syntax, ownership model, and error handling, forming the essential foundation of Rust programming.

Part 4-9: Advanced Language Features

Learn about Rust’s advanced features that make it unique, including concurrency, macros, generics, and more. These tools help you write safe, efficient, and reusable code.

Part 10-13: Development Tools and Web Programming

This section explores Rust’s ecosystem for testing, package management, and web development, providing tools to help you maintain, extend, and deploy Rust applications.

Part 14-16: Specialized Topics

Dive into Rust’s applications in secure programming, systems development, and interoperability with other languages. These areas highlight Rust’s unique strengths and its use in performance-critical applications.

Dive in, start with Part 1

Learning Rust Part 9 - Files and I/O

30 Oct 2024

Introduction

Rust’s I/O capabilities provide a range of options for efficiently handling files, streams, and standard input/output. Rust’s std::fs module offers synchronous file handling, while libraries like tokio and async-std add support for asynchronous I/O, enabling non-blocking operations. In this post, we’ll explore Rust’s key I/O operations, including file reading, writing, metadata, streaming, and error handling.

Standard Input and Output

Rust provides convenient tools for interacting with the console, allowing programs to communicate with users or other processes.

Standard Output

Rust’s print!, println!, and eprintln! macros are used to display messages. println! sends output to standard output, while eprintln! sends output to standard error.

fn main() {
    println!("Hello, world!");      // Standard output
    eprintln!("This is an error");   // Standard error
}

Standard Input

To read user input, std::io::stdin provides a read_line method that stores console input into a String.

use std::io;

fn main() {
    let mut input = String::new();
    println!("Enter your name:");
    io::stdin().read_line(&mut input).expect("Failed to read input");
    println!("Hello, {}", input.trim());
}

Reading and Writing Files

Rust’s std::fs module makes file reading and writing straightforward, offering methods like File::open for reading and File::create for writing.

Reading Files

The read_to_string method reads the entire contents of a file into a String.

use std::fs;

fn main() -> std::io::Result<()> {
    let content = fs::read_to_string("example.txt")?;
    println!("{}", content);
    Ok(())
}

Writing Files

To write to a file, use File::create to open or create the file, and write_all to write bytes to it.

use std::fs::File;
use std::io::Write;

fn main() -> std::io::Result<()> {
    let mut file = File::create("output.txt")?;
    file.write_all(b"Hello, world!")?;
    Ok(())
}

Streaming I/O

Streaming I/O is efficient for reading or writing large files in chunks, especially when loading the entire file into memory is impractical. BufReader and BufWriter provide buffering for improved performance.

Buffered Reading

BufReader reads data in chunks, storing it in a buffer for efficient access.

use std::fs::File;
use std::io::{self, BufRead, BufReader};

fn main() -> io::Result<()> {
    let file = File::open("example.txt")?;
    let reader = BufReader::new(file);

    for line in reader.lines() {
        println!("{}", line?);
    }
    Ok(())
}

Buffered Writing

BufWriter buffers output, which is particularly useful when writing multiple small pieces of data.

use std::fs::File;
use std::io::{self, BufWriter, Write};

fn main() -> io::Result<()> {
    let file = File::create("buffered_output.txt")?;
    let mut writer = BufWriter::new(file);

    writer.write_all(b"Hello, world!")?;
    writer.flush()?; // Ensures all data is written
    Ok(())
}

File Metadata and Permissions

Rust allows access to and modification of file metadata, including permissions and timestamps, via the metadata method and the Permissions struct.

Retrieving Metadata

The metadata function provides details such as file size and permissions.

use std::fs;

fn main() -> std::io::Result<()> {
    let metadata = fs::metadata("example.txt")?;
    println!("File size: {}", metadata.len());
    println!("Is read-only: {}", metadata.permissions().readonly());
    Ok(())
}

Changing Permissions

You can modify file permissions with set_permissions, which can be particularly useful for restricting access to sensitive files.

use std::fs;
use std::os::unix::fs::PermissionsExt;

fn main() -> std::io::Result<()> {
    let mut perms = fs::metadata("example.txt")?.permissions();
    perms.set_readonly(true);
    fs::set_permissions("example.txt", perms)?;
    Ok(())
}

Asynchronous I/O

For non-blocking I/O, Rust offers asynchronous support through libraries like tokio and async-std. These libraries allow file and network operations to run without blocking the main thread, making them ideal for scalable applications.

Using Tokio for Async I/O

The tokio::fs module provides async counterparts to common file operations, like reading and writing.

use tokio::fs::File;
use tokio::io::AsyncWriteExt;

#[tokio::main]
async fn main() -> tokio::io::Result<()> {
    let mut file = File::create("async_output.txt").await?;
    file.write_all(b"Hello, async world!").await?;
    Ok(())
}

Async Streaming with Tokio

BufReader and BufWriter are also available in asynchronous forms with Tokio, enabling efficient non-blocking I/O.

use tokio::fs::File;
use tokio::io::{self, AsyncBufReadExt, BufReader};

#[tokio::main]
async fn main() -> io::Result<()> {
    let file = File::open("example.txt").await?;
    let reader = BufReader::new(file);

    let mut lines = reader.lines();
    while let Some(line) = lines.next_line().await? {
        println!("{}", line);
    }
    Ok(())
}

Error Handling in I/O Operations

Error handling is essential in I/O operations, as access to files can fail due to permissions, missing files, or storage limitations. Rust’s Result type and the ? operator streamline error handling in I/O tasks.

Using Result and ? for Concise Error Handling

Most I/O functions return Result, enabling explicit error handling or propagation with ?. We covered this syntax in part 3 of this series.

use std::fs;

fn read_file() -> std::io::Result<String> {
    let content = fs::read_to_string("example.txt")?;
    Ok(content)
}

fn main() {
    match read_file() {
        Ok(content) => println!("File content: {}", content),
        Err(e) => eprintln!("Error reading file: {}", e),
    }
}

Summary

Rust provides comprehensive tools for file handling and I/O, from basic read/write operations to asynchronous streaming and metadata management. With built-in error handling and async capabilities, Rust’s I/O tools allow for efficient, flexible, and reliable code, making it well-suited for building high-performance applications that handle complex I/O tasks with ease.

Learning Rust Part 8 - Unsafe

30 Oct 2024

Introduction

Rust is known for its strong safety guarantees, particularly around memory safety, achieved through strict ownership and borrowing rules. However, certain low-level operations—like raw pointer manipulation and foreign function interfaces—require bypassing these safety checks.

Rust’s unsafe code capabilities provide the necessary control for these cases, but they come with potential risks. In this post, we’ll explore unsafe Rust’s capabilities, including raw pointers, unsafe blocks, and FFI (Foreign Function Interface), and offer best practices for safe usage.

Raw Pointers

In Rust, raw pointers (*const T for immutable and *mut T for mutable) enable low-level memory manipulation similar to pointers in C. Unlike Rust references (& and &mut), raw pointers:

  • Don’t enforce Rust’s borrowing rules.
  • Can be null or dangling.
  • Are not automatically dereferenced.

Creating Raw Pointers

Raw pointers are created using the as keyword for casting or by using Box::into_raw for heap allocations.

fn main() {
    let x = 42;
    let r1 = &x as *const i32; // Immutable raw pointer
    let r2 = &x as *mut i32;   // Mutable raw pointer
}

Dereferencing and Pointer Arithmetic

With raw pointers, you can dereference or manipulate memory addresses directly. However, Rust requires an unsafe block to perform these actions due to the inherent risks.

Dereferencing Raw Pointers

Dereferencing a raw pointer retrieves the value it points to. This operation is only allowed in an unsafe block, as dereferencing invalid pointers can lead to crashes or undefined behavior.

fn main() {
    let x = 42;
    let r = &x as *const i32;

    unsafe {
        println!("Value at pointer: {}", *r); // Unsafe dereference
    }
}

Pointer Arithmetic

Raw pointers also support pointer arithmetic, allowing you to manually navigate memory addresses. This is especially useful for low-level data manipulation.

fn main() {
    let arr = [10, 20, 30];
    let ptr = arr.as_ptr();

    unsafe {
        println!("Second element: {}", *ptr.add(1)); // Accesses arr[1]
    }
}

Unsafe Blocks

Rust confines certain risky operations to unsafe blocks to help isolate potentially unsafe code from safe parts of the program. This provides flexibility while containing risks.

Operations Allowed in Unsafe Blocks

Only the following operations are allowed in unsafe blocks:

  • Dereferencing raw pointers.
  • Calling unsafe functions.
  • Accessing or modifying mutable static variables.
  • Implementing unsafe traits.
  • Accessing union fields.
unsafe fn dangerous() {
    println!("This function is unsafe to call.");
}

fn main() {
    unsafe {
        dangerous();
    }
}

FFI (Foreign Function Interface)

Rust’s Foreign Function Interface (FFI) lets you call functions from other languages, such as C, making it valuable for systems programming or integrating existing C libraries.

Declaring an External Function

To call a C function from Rust, use extern "C", which specifies the C calling convention. Here’s an example of calling C’s abs function to find the absolute value.

extern "C" {
    fn abs(input: i32) -> i32;
}

fn main() {
    unsafe {
        println!("Absolute value: {}", abs(-5));
    }
}

Defining Functions for C

You can also use extern "C" to make Rust functions callable from C by adding the #[no_mangle] attribute, which prevents Rust from renaming the function during compilation.

#[no_mangle]
pub extern "C" fn my_function() {
    println!("Called from C code!");
}

Working with C Libraries

To use external libraries, add the #[link] attribute, which specifies the library’s name. For example, here’s how to link to the math library (libm) for advanced mathematical functions.

Using C Libraries (Linking and Calling)

The following example demonstrates calling sqrt from the math library.

#[link(name = "m")]
extern "C" {
    fn sqrt(x: f64) -> f64;
}

fn main() {
    unsafe {
        println!("Square root of 9.0 is {}", sqrt(9.0));
    }
}

Note: You may need to configure linking in your Cargo.toml to include the library during compilation.

Undefined Behavior and Safety

Unsafe Rust allows for operations that, if misused, can lead to undefined behavior. Common causes of undefined behavior include:

  • Dereferencing null or dangling pointers.
  • Breaking Rust’s aliasing rules (e.g., multiple mutable references).
  • Accessing memory out of bounds.
  • Using uninitialized data.

Safety Tips for Using Unsafe Code

To minimize risks when using unsafe code, follow these best practices:

  • Limit unsafe code to small, well-defined sections to make it easier to review and understand.
  • Wrap unsafe code in safe abstractions to prevent direct access to risky operations.
  • Thoroughly review unsafe code, especially around pointer dereferencing and FFI calls.

By isolating and encapsulating unsafe operations within safe APIs, you can maintain Rust’s safety guarantees while still taking advantage of low-level control when necessary.

Summary

Unsafe Rust provides tools like raw pointers, unsafe blocks, and FFI to extend Rust’s capabilities in low-level programming, where direct memory access and foreign function calls are required. While these features offer powerful flexibility, they should be used sparingly and with caution to avoid undefined behavior. With proper handling, unsafe code can be an invaluable tool, enabling Rust developers to push the boundaries of Rust’s memory safety model without sacrificing control or performance.