pcp-mutex

A Priority Ceiling Protocol (PCP) mutex, based on Linux PI futex. Allows efficient and deadlock free execution.

How it Works

Linux kernel does not natively support Priority Ceiling Protocol (PCP), which is essential for real-time systems to both ensure good schedulability and deadlock free execution. This crate emulates Original Priority Ceiling Protocol (OPCP) using Priority Inheritance (PI) futexes.

Under the hood each PcpMutex belongs to some PcpGroup, which contains atomic pointer to the highest locker. Any attempt to lock a PcpMutex is firstly checked against this highest locker if PCP conditions for locking are met. On success, futex is locked by an atomic operation involving zero syscalls. On failure, current thread calls futex LOCK_PI syscall on the highest locker and kernel raises the priority of the locker.

By default PcpMutex::new() uses the default global group. Multiple groups can be used for isolated parts of the program.

This is different from POSIX PTHREAD_PRIO_PROTECT mutexes in two ways: - POSIX mutex calls sched_setparam syscall on each lock/unlock, which is much slower. This library has only atomic operations in the fast path. - POSIX mutexes are individual (no system ceiling) and do not prevent deadlocks. It is not a 'real' PCP.

Example

Locking 2 mutexes in different order would result in deadlock, but PCP prevents that:

```rust let priority = ThreadState::from_sys();

let a = Arc::new(PcpMutex::new(0, 3)); let b = Arc::new(PcpMutex::new(0, 3));

{ let a = a.clone(); let b = b.clone(); thread::spawn(move || { let priority = ThreadState::from_sys();

    println!("Thread 1 tries a lock");
    a.lock(&priority, |a| {
        println!("Thread 1 holds a lock");
        *a += 1;
        thread::sleep(std::time::Duration::from_millis(100));
        println!("Thread 1 tries b lock");
        b.lock(&priority, |b| {
            println!("Thread 1 holds b lock");
            *b += 1;
        });
        println!("Thread 1 released b lock");
    });
    println!("Thread 1 released a lock");
});

}

{ let a = a.clone(); let b = b.clone(); thread::spawn(move || { let priority = ThreadState::from_sys();

    println!("Thread 2 tries b lock");
    b.lock(&priority, |b| {
        println!("Thread 2 holds b lock");
        *b += 1;
        thread::sleep(std::time::Duration::from_millis(100));
        println!("Thread 2 tries a lock");
        a.lock(&priority, |a| {
            println!("Thread 2 holds a lock");
            *a += 1;
        });
        println!("Thread 2 released a lock");
    });
    println!("Thread 2 released b lock");
});

} ```

Output: Thread 1 tries a lock Thread 1 holds a lock Thread 2 tries b lock <--- thread 2 is prevented from taking a lock here by PCP Thread 1 tries b lock Thread 1 holds b lock Thread 1 released b lock Thread 1 released a lock Thread 2 holds b lock Thread 2 tries a lock Thread 2 holds a lock Thread 2 released a lock Thread 2 released b lock

Credits

This work was done as a part of my Thesis at University of Twente.