Excellent work, Dr. Zaitsev. The benchmark results are very impressive, and your explanation of wait-for-all semaphore semantics provides valuable insight into synchronization in modern operating systems. I’m looking forward to reading the full paper and exploring the details of your research.
I primarily work in Ubuntu/Linux, so studies related to kernel synchronization and operating system performance are especially interesting to me. While reading about your work, a few questions came to mind:
Is the benchmark based on a single machine, or does it involve multiple interconnected systems working together?
How many separate tasks or processes can the system handle at the same time?
Which type of users or applications is this computing approach primarily designed for—for example, high-performance computing, large-scale distributed enterprise systems, small and medium-sized server environments, or desktop systems?
Thank you for sharing your research. I look forward to learning more from the published paper.
So 5,000x gap between your PVZ VM and native semop() doesn’t surprise me much once you look at what sem.c is actually doing like a single per array lock sem_per_op, sequential twopass checking of the sops queue, no batching, no lock-free fast path for the common case. I think thats a design from a very different era of core counts and a real bottleneck, but its a known one meanwhile kernel folks steer high throughput sync work toward futex, eventfd, or io_uring precisely because system V IPC was never built for this workload class
So in that case the honest framing isn’t Linux is 5000x slower than a VM, it’s System V semaphores are a bad fit for a workload built around 8192 fine grained processes hammering semop() Different claim, and one I think is actually more interesting for kernel devs to engage with
On the wider question youre raising indirectly = do we just trust Linus, or is there real benchmark infrastructure behind kernel efficiency claims and the point is theres more than people assume. and KernelCI and the 0 day/kernel test robot run perf regression checks on every merge, schbench and lmbench cover scheduler and syscall latency, Phoronix Test Suite gets used for cross-release comparisons. It’s not rigorous the way your PTN approach is formal, but it’s not blind faith either
Would be curious whether your wait-for-all semantics idea could be prototyped as a syscall extension rather than a new semaphore family smaller patch surface, easier to get real benchmark numbers against mainline
Thank you for your interest in my R&D and for your kind words of appreciation. I am especially pleased to respond to your inspiring question.
At present, the benchmark is based on a single machine.
The benchmark available on my GitHub repository (SNCtools/bm5000x) uses a number of processes equal to the number of transitions (the second parameter in the MCC file). For the largest benchmark, gm32x32-b6.mcc , the PVZ machine launches 8,192 child processes.
Sleptsov Net Computing is designed as an efficient general-purpose architecture based on the computing memory concept and the Sleptsov net as a graphical concurrent programming language. The connection with semaphores, developed in my recent paper, provides asynchronous control mechanisms that enable significant energy savings.
I would be delighted if you joined our R&D efforts. A good starting point would be to run the benchmark and then consider a personal research direction that aligns with your interests.
Thank you for your deep professional analysis integrated with surveys of the adjacent area, which is very useful and enlightens a reader. Possibly you could recommend a procedure to submit my benchmark to the Linux kernel benchmark infrastructure. I also think about the OS work optimization. In my PhD (https://dimazaitsev.github.io/pdf/daze-phd-1991.pdf) I optimized manufacturing and develped Opera-Topaz ~100k lines of C code. For such big systems formal optimization does not work, though it helps to produce a set of efficient one- or few-step (combined with mini-max) strategies.
My version is that people were averted by slow implementation of wait-for-all semantics and because of it abandoned System V semaphores, though the wait-for-all concept resolves a good deal of deadlocks induced by sequential acquisition of resources.
Multithread programming has born futexes, though with futex_waitv, they implemented just wait-for-any semantics. Now people are using clumsy loops of futex_waitv to implement wait-for-all. An efficient algorithm is a big challenge. I offered to think about dedicated hardware units (accelerators) as a part of processor architecture, similar to page registers, with parallel associative memory search with constant time complexity.
Recently, I offered a few PhD topics in LinkedIn post (#phd #linux | Dmitry Zaitsev), “the first ring”—efficient synchronization and on-the-fly deadlock recognition. As for the synchronization, we plan to cover both kernel and user space, working in the futex idea—synchronize fast with runtime code; otherwise, call the kernel.
Also, I issued a teaser for potential PhD students: (1) just copy sem.c, add a personal prefix for routine and data structure names, and add the corresponding new system calls; test; (2) extend semaphore size to 4 bytes; test; (4) implement greedy semaphores; test and benchmark. No considerable changes to the current sem.c, only bigger size (to compute realistic values) and greediness (to compute fast). Greedy semaphores (Sleptsov-Salwicki rule for PTNs) require just computing the greatest common divisor instead of a conjunction of comparisons.
Please help to attract talented folk. We are open for joint projects as well.
