Sterling has too many projects Blogging about Raku programming, microcontrollers & electronics, 3D printing, and whatever else...

Semaphores

| 603 words | 3 minutes | raku advent-2019
Crewman holding semaphore flags

A semaphore is a system of sending messages using flags. Oh wait, that’s what a semaphore is outside of computing. Among computers, a semaphore is like a kind of lock that locks after being acquired N times. This is useful for situations where you have a resource of N items, want to quickly distribute them when you know they are available, and then immediately block until a resource has been released. Raku provides a built-in Semaphore class for this reason:

class ConnectionPool {
    has @.connections;
    has Semaphore $!lock;

    submethod BUILD(:@!connections) {
        $!lock .= new(@!connections.elems);
    }

    method use-connection() {
        $!lock.acquire;
        pop @!connections;
    }

    method return-connection($connection) {
        push @!connections, $connection;
        $!lock.release;
    }
}

Here we have a connection pool where we can quickly and safely pull entries out of the stack of connections. However, as soon as the last connection has been pulled, the .use-connection method will block until a connection is returned using the .return-connection.

There is an additional .try_acquire method that can be used instead of .acquire, which returns a Bool that determines success or failure. For example, we might have a buffer for key presses that we want to fail if it fills up, rather than continuing to store key events:

class KeyBuffer {
    has UInt $.size;
    has UInt $!read-cursor = 0;
    has UInt $!write-cursor = 0;
    has byte @!key-buffer;
    has Semaphore $!buffer-space;
    has Semaphore $!lock .= new(1);

    submethod BUILD(UInt :$!size) {
        @!key-buffer = 0 xx $!size;
        $!buffer-free .= new($!size);
    }

    method !increment-cursor($cursor is rw) {
        $cursor++;
        $cursor %= $!size;
    }

    method store(byte $key) {
        $!buffer-space.try_acquire or die "buffer is full!"

        $!lock.acquire;
        LEAVE $!lock.free;

        @!key-buffer[ $!write-cursor ] = $key;
        self!increment-cursor($!write-cursor);
    }

    method getc(--> byte) {
        my $result = 0;

        $!lock.acquire;
        LEAVE $!lock.release;

        if $!read-cursor != $!write-cursor {
            $result = @!key-buffer[ $!read-cursor ];
            self!increment-cursor($!read-cursor);

            $!buffer-space.release;
        }
        
        $result;
    }
}

This data structure uses two Semaphores. One, named $!lock, is used in the same way a Lock works to guard the critical sections and make sure they are atomic. The other, $!buffer-space, is used to make sure the write operations fail when the buffer fills up.

As you can see, we use .try_acquire to acquire a resource from the Semaphore. If that method returns False, we throw an exception to let the caller know the operation failed. If the method returns True, then we have acquired permission to add another entry to the buffer. When we read from the buffer, we still use .release to mark the space available again.

I’ve used Semaphore for the mutual exclusion lock because it can be use that way and that’s what we’re talking about. However, the protect method of Lock or Lock::Async may be a better choice here as you don’t need to be careful to make sure .release gets called as the .protect block takes care of that for you. With that said, a LEAVE phaser is a good way to make sure .release is called as LEAVE phasers will be called no matter how the block exits (i.e., it runs even on an exception).

It should be noted that if an exception happens in the .getc method above after the $!read-cursor is incremented, but before $!buffer-space.release is called, you could end up with the buffer in a bad state where it no longer has as much space. As such, an improvement that might be worth doing is making sure that exceptions in that if-block are caught and dealt with if such an exception is possible.

A general thing to keep in mind is that whenever dealing with concurrency, the seemingly trivial edge cases can easily become important. Sometimes it becomes important in unforeseen ways.

Cheers.

The content of this site is licensed under Attribution 4.0 International (CC BY 4.0).