How to handle orphaned semaphores?

[robfinch]

Currently in the OS if a semaphore does not unlock within 500,000 tries, then it is forced to the unlocked state. I am wondering if this is a reasonable approach, or is there something better?

The idea is that there must have been something that crashed or failed and orphaned the locked semaphore.

There is a pool of 2048 hardware semaphores.

Another thought is to track the start tick a semaphore was locked on and have a thread that scans the semaphores unlocking ones that were locked too long ago.

[Octocontrabass]

Currently in the OS if a semaphore does not unlock within 500,000 tries, then it is forced to the unlocked state. I am wondering if this is a reasonable approach, or is there something better?

That's a terrible approach. How do you know that whatever task locked the semaphore will always finish within that fixed amount of time? What will happen if the second task tries to access the shared resource while the first task is still using it? If a task does crash, why don't you know which semaphores it held so you can unlock them?

There is a pool of 2048 hardware semaphores.

Most CPUs can use ordinary RAM for semaphores. What makes your hardware semaphores better than ordinary RAM?

[thewrongchristian]

Currently in the OS if a semaphore does not unlock within 500,000 tries, then it is forced to the unlocked state. I am wondering if this is a reasonable approach, or is there something better?

The idea is that there must have been something that crashed or failed and orphaned the locked semaphore.

There is a pool of 2048 hardware semaphores.

Another thought is to track the start tick a semaphore was locked on and have a thread that scans the semaphores unlocking ones that were locked too long ago.

Don't orphan semaphores.

It's as simple as that.

It is not correct to put in heuristics to manage failure. If your kernel has failed to the point of orphaning lock structures, it is best to panic.

Thread failures should result in something you can detect, such as a CPU trap, and your thread should be able to fail gracefully.

[robfinch]

That's a terrible approach. How do you know that whatever task locked the semaphore will always finish within that fixed amount of time? What will happen if the second task tries to access the shared resource while the first task is still using it? If a task does crash, why don't you know which semaphores it held so you can unlock them?

Thanks, I did not think it was a very good approach. The semaphores are being used by the OS to lock resources for short periods of time. I guessed the 500,000 retries would be a lot longer than any lock should be. The semaphore lock/unlock is a BIOS function. It will panic instead.

Most CPUs can use ordinary RAM for semaphores. What makes your hardware semaphores better than ordinary RAM?

It is not better (it is worse), it is an alternative because the system does not support atomic memory operations like TAS. It splits read-modify-write into two bus cycles, and a second CPU could intervene. The CPU's atomics do not make it through all the bus bridges. Also, this is a 68k implementation, it does not send enough information out on the bus to perform an atomic operation in a single bus cycle. The hardware semaphores can be used to build atomic primitives. It only takes a couple of hardware semaphores. But it is much slower than having atomic instructions available. Much faster than software semaphores.

It is not correct to put in heuristics to manage failure. If your kernel has failed to the point of orphaning lock structures, it is best to panic.

Was not sure about that.

Thread failures should result in something you can detect, such as a CPU trap, and your thread should be able to fail gracefully.

Have not reached the graceful failures yet.

[Octocontrabass]

It splits read-modify-write into two bus cycles, and a second CPU could intervene. The CPU's atomics do not make it through all the bus bridges.

The CPU's atomics only need to work with RAM. That might make it a simple enough problem that you can solve it by modifying some of the bridges (which I assume are also implemented in your FPGA).

Also, this is a 68k implementation, it does not send enough information out on the bus to perform an atomic operation in a single bus cycle.

But it does keep the address strobe asserted for the duration of the atomic operation, which is enough information to prevent another CPU from accessing the same address. I see how that would be inconvenient with bridges, though. The x86 local bus has a dedicated lock signal that gets asserted at the beginning of the read cycle, so bridges know as soon as the read begins that it's part of an atomic operation. (Modern x86 also uses the cache coherency protocol for atomic operations, which allows locking to occur on individual cache lines instead of the entire local bus.)

[robfinch]

The CPU's atomics only need to work with RAM. That might make it a simple enough problem that you can solve it by modifying some of the bridges (which I assume are also implemented in your FPGA).

But it does keep the address strobe asserted for the duration of the atomic operation, which is enough information to prevent another CPU from accessing the same address. I see how that would be inconvenient with bridges, though. The x86 local bus has a dedicated lock signal that gets asserted at the beginning of the read cycle, so bridges know as soon as the read begins that it's part of an atomic operation. (Modern x86 also uses the cache coherency protocol for atomic operations, which allows locking to occur on individual cache lines instead of the entire local bus.)

A brief system description:

The bus in the test system is pipelined for performance and cannot really be modified to support a lock signal operating across multiple cycles.

Requests go out on the bus every clock cycle looking like:

|CPU1|CPU2|CPU3|CPU4|CPU5|CPU6|…

Responses come back after a delay(varies) looking like:

|---|---|---|---|---|RSP1|RSP2|RSP3|RSP4|RSP5|RSP6|

The responses may come back out of order.

Locking the bus would adversely affect performance as no other CPU could use the bus while it is locked, even though there may be no conflict with the addresses.

The SoC network interface converts the 68000’s semi-asynchronous bus into a fully asynchronous one. Each bus operation is converted into a request and has an associated response. The request is placed on the network bus as a single clock cycle request, the response comes back as a single clock cycle response numerous cycles after the request. There may be multiple requests (time multiplexed) by multiple CPUs before a response comes back. It is made to look like a normal bus request with an address strobe and data acknowledge to the 68000.

Each CPU node has its own local ROM and SRAM. Most of the OS uses variables stored in the local SRAM which can be protected by enabling/disabling interrupts. There is also a global SRAM used to store OS variables that needs semaphores. The goal is to use DRAM to store some OS variables, but the DRAM is not working reliably enough ATM. Also, the 68000 CPU will be substituted with a different CPU eventually.

[Octocontrabass]

Locking the bus would adversely affect performance as no other CPU could use the bus while it is locked, even though there may be no conflict with the addresses.

In theory, atomic operations don't have to lock the entire bus. As long as other CPUs are prevented from accessing the same memory as an atomic operation in progress, there's no problem.

But it's a lot easier to tell programmers to add delays when using atomic instructions in a loop.

Also, the 68000 CPU will be substituted with a different CPU eventually.

Won't you have to redesign the bus interface for the new CPU?

[robfinch]

In theory, atomic operations don't have to lock the entire bus. As long as other CPUs are prevented from accessing the same memory as an atomic operation in progress, there's no problem.

A bus lock/unlock signal could be passed along the bus. Then a record kept at the memory of locked addresses (address reservations). If the CPU had locked loads and conditional stores it would work great. Otherwise, the CPU locking the memory could be recorded and other CPUs would be blocked from accessing the locked memory. The list would not need to be very large, eight entries might do. A lock/unlock plus a read-write signal turns into a two-bit command bus, which is tempting to just expand to a full-blown command bus.
The CPU would need to be modified and a component tracking the bus locks on memory would need to be developed. I was trying to avoid these changes.
Another project, uses a five-bit command bus to indicate the memory op. (About a dozen AMO ops, plus load and store).

Won't you have to redesign the bus interface for the new CPU?

There may be some re-design, but it is mostly just implementation details. Adjusting bus widths. There are three or four bus standards which may be used. WISHBONE (the 68k was designed using a WISHBONE bus). Something I called FTA bus (an asynchronous bus), and AXI4/Amba which I have not used a lot. There is also the system-on-chip network packet bus. Changes in the CPU bus must be reflected to all the components along the way. I figured wrapping up the semaphore access in a library call would help isolate changes.

[Octocontrabass]

The CPU would need to be modified and a component tracking the bus locks on memory would need to be developed. I was trying to avoid these changes.

You could avoid modifying the CPU if you can find one that asserts a dedicated lock signal at the beginning of an atomic operation (like x86). That would also make it easier to try whole-bus locks first, to see if the overhead is really enough to justify more granular locks.

There are three or four bus standards which may be used.

Do any of those offer a way to detect atomic operations at the beginning of the cycle? (WISHBONE apparently doesn't; you're expected to connect all of your CPUs to the same WISHBONE bus instead of giving each CPU its own bridge to some other bus.)

Actually, that brings up another question I should have asked earlier: why aren't your CPUs sharing the same local bus?

[robfinch]

Actually, that brings up another question I should have asked earlier: why aren't your CPUs sharing the same local bus?

CPUs are connected using a network ring topology. They do have access to local resources in another node via a special address range ($F8Nxxxxx). The ring may be less overhead and faster timing wise than using a large crossbar to connect the CPUs. It is okay for a small number of CPUs (it definitely would not scale). It takes about 10 clocks for a request / response to go around the ring.

The CPUs are connected in pairs in network nodes. Both CPUs in the pair have direct access to the same local RAM / ROM via the use of multi-ported memory. Outside of that, the CPUs have access to local RAM / ROM in other pairs node but with some number of clock cycles latency. A special node connects to the rest of the system (DRAM, audio / video, keyboard, shared ROM / RAM, sdcard, etc.). There are potentially four compute nodes (eight CPUs) but I usually just test with one to speed up build times. Four nodes is about the max that will fit in the FPGA.

Local RAM/ROM is very limited in size. 32kB RAM, and 128kB ROM. Not really large enough to run the OS. The OS kernel and BIOS is in the local ROM. Most of the OS vars are in a globally shared 256kB RAM. The OS is pared down so it will fit in the RAM. Just 128 threads supported ATM.
*****
The OS is task switching between two threads and sending a message from one to another, but after WaitMsg() is called about three times it crashes with a panic. It is trying to move a thread between lists and the next, prev handles are not zero. That indicates the thread is still on a list. The same next, prev handles are used for different lists. Every time a thread is removed from a list the next, prev is set to zero. When added to a list they are set to non-zero values. Scratching my head over this one.

The lists are: the free list, the ready list, and the timeout-list. A thread can only be on one of these at a time so the handles are reused to conserve memory.

The OS uses handles instead of pointers to conserve memory as the handles are only 16-bits. But it results in a lot of pointer<->handle conversions.

[Octocontrabass]

Scratching my head over this one.

Are semaphore accesses ordered with respect to memory accesses?

[robfinch]

Are semaphore accesses ordered with respect to memory accesses?

They are by CPU. All accesses for a CPU are in order. One access must complete before the next one can begin. The semaphore is a memory access. Between CPUs access may not be in order. If the global resource is not available the request will loop around the ring, which may make it out of order with respect to other CPUs and its original request order.

Testing is with just one CPU active ATM. The second CPU in the node is stuck in an infinite loop until is sees a go signal.