Bikeshed - Lock free hierarchical work scheduler

Branch OSX / Linux / Windows
master Build Status
master Codacy Badge

bikeshed

Lock free hierarchical work scheduler Builds with MSVC, Clang and GCC, header only, C99 compliant, MIT license.

See github for latest version: https://github.com/DanEngelbrecht/bikeshed

See design blogs at: https://danengelbrecht.github.io

Version history

Version v1.0 29/5 2019

Release 1.0

Fixes

  • Use explicit int32_t for instead of long to ensure 32-bit values on GCC/Clang x64-builds
  • Corrected URL to blog in README.md
  • Added sample code for performance tests (in examples folder)

Version v0.4 18/5 2019

Pre-release 4

API changes

  • Bikeshed_AddDependencies to take array of parent task task_ids
  • Bikeshed_ReadyCallback now gets called per channel range

API additions

  • Bikeshed_FreeTasks
  • BIKESHED_L1CACHE_SIZE to control ready head alignement - no padding/alignement added by default
  • BIKESHED_CPU_YIELD to control yielding in high-contention scenarios

Fixes

  • Added default (non-atomic) implementations for helper for unsupported platforms/compilers
  • Codacy analisys and badge
  • More input validation on public apis when BIKESHED_ASSERTS is enabled
  • Batch allocation of task indexes
  • Batch allocation of dependency indexes
  • Batch free of task indexes
  • Batch free of dependency indexes
  • Fixed broken channel range detection when resolving dependencies

Version v0.3 1/5 2019

Pre-release 3

Fixes

  • Ready callback is now called when a task is readied via dependency resolve
  • Tasks are readied in batch when possible

Version v0.2 29/4 2019

Pre-release 2

Fixes

  • Internal cleanups
  • Fixed warnings and removed clang warning suppressions
    • -Wno-sign-conversion
    • -Wno-unused-macros
    • -Wno-c++98-compat
    • -Wno-implicit-fallthrough
  • Made it compile cleanly with clang++ on Windows

Version v0.1 26/4 2019

Pre-release 1

Features

  • Generic tasks scheduling with dependecies between tasks
    • Each task has zero or many dependecies (as defined by user)
    • User should Ready any tasks that can execute (has zero dependencies)
    • Automatic ready of tasks that reaches zero dependecies
    • Automatic free of tasks that has completed
  • A task can have many parents and many child dependecies
  • Task channels - execute tasks based on task channel
  • No memory allocations once shed is created
  • Minimal dependencies
  • Memory allocation and threading are users responsability
  • Lifetime of data associated with tasks is users responsability
  • Configurable and optional assert (fatal error) behavior
  • Configurable platform dependant functions with default implementation provided
  • Header only - define BIKESHED_IMPLEMENTATION in one compilation unit and include bikeshed.h

Non-features

  • Cyclic dependency detection and resolving
    • API is designed to help user avoid cyclic dependecies but does not do any analisys
  • Built in threading or syncronization code - API to add it is available
  • Unlimited number of active tasks - currently limited to 8 388 607 active tasks
  • Cancelling of tasks
  • Tagging of tasks

Dependencies

Minimal dependecies with default overridable method for atomic operations.

  • <stdint.h>
  • <string.h>
  • The default (optional) MSVC implementation depends on <Windows.h>.

Optional default methods

The default implementations for the atomic and CPU yield functions can be overridden with your own implementation by overriding the macros:

  • BIKESHED_ATOMICADD Atomically adds a 32-bit signed integer to another 32-bit signed integer and returns the result
  • BIKESHED_ATOMICCAS Atomically exchange a 32-bit signed integer with another 32-bit signed integer if the value to be swapped matches the provided compare value, returns the old value.
  • BIKESHED_CPU_YIELD Yield CPU (mm_pause() / YieldProcessor()).

Test code dependecies

Test code has dependencies added as drop-in headers from

Test code has dependencies added as git sub-modules from

Owner
Dan Engelbrecht
Ericsson Radio Systems AB, Propellerheads AB, Aphelion AB, Autodesk, Frostbite, King, Embark Studios
Dan Engelbrecht
Similar Resources

GECOS: A lock-free synchronization mechanism

GECOS GECOS is a lock-free synchronization mechanism, and this repository compares various well-known mechanisms such as RCU and HP (Hazard Pointers).

Sep 9, 2021

Rpmalloc - Public domain cross platform lock free thread caching 16-byte aligned memory allocator implemented in C

Rpmalloc - Public domain cross platform lock free thread caching 16-byte aligned memory allocator implemented in C

rpmalloc - General Purpose Memory Allocator This library provides a public domain cross platform lock free thread caching 16-byte aligned memory alloc

Jun 14, 2022

A hybrid thread / fiber task scheduler written in C++ 11

Marl Marl is a hybrid thread / fiber task scheduler written in C++ 11. About Marl is a C++ 11 library that provides a fluent interface for running tas

Jun 16, 2022

Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin

Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin

A CPU scheduler determines an order for the execution of its scheduled processes; it decides which process will run according to a certain data structure that keeps track of the processes in the system and their status.

Jul 14, 2021

EnkiTS - A permissively licensed C and C++ Task Scheduler for creating parallel programs. Requires C++11 support.

EnkiTS - A permissively licensed C and C++ Task Scheduler for creating parallel programs. Requires C++11 support.

Support development of enkiTS through Github Sponsors or Patreon enkiTS Master branch Dev branch enki Task Scheduler A permissively licensed C and C++

Jun 20, 2022

Scheduler - Modern C++ Scheduling Library

Scheduler Modern C++ Header-Only Scheduling Library. Tasks run in thread pool. Requires C++11 and ctpl_stl.h in the path. Inspired by the Rufus-Schedu

Jun 21, 2022

Work Stealing Thread Pool

wstpool Work Stealing Thread Pool, Header Only, C++ Threads Consistent with the C++ async/future programming model. Drop-in replacement for 'async' fo

Jul 20, 2021

DwThreadPool - A simple, header-only, dependency-free, C++ 11 based ThreadPool library.

DwThreadPool - A simple, header-only, dependency-free, C++ 11 based ThreadPool library.

dwThreadPool A simple, header-only, dependency-free, C++ 11 based ThreadPool library. Features C++ 11 Minimal Source Code Header-only No external depe

May 29, 2022

Forkpool - A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20

riften::Forkpool A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20. This project uses C++20's coroutines to implement c

Jun 20, 2022

afl/afl++ with a hierarchical seed scheduler

This is developed based on AFLplusplus (2.68c, Qemu mode), thanks to its amazing maintainers and community Build and Run Please follow the instruction

May 18, 2022

A easy to use multithreading thread pool library for C. It is a handy stream like job scheduler with an automatic garbage collector. This is a multithreaded job scheduler for non I/O bound computation.

A easy to use multithreading thread pool library for C. It is a handy stream-like job scheduler with an automatic garbage collector for non I/O bound computation.

Jun 4, 2022

Fast, generalized, implementation of the Chase-Lev lock-free work-stealing deque for C++17

riften::Deque A bleeding-edge lock-free, single-producer multi-consumer, Chase-Lev work stealing deque as presented in the paper "Dynamic Circular Wor

May 29, 2022

Concurrent-deque - Lock-free concurrent work stealing deque in C++

A lock-free work-stealing deque This is a C++ implementation of the Chase-Lev deque, a concurrent single-producer, multi-consumer queue presented in t

Mar 13, 2022

A bounded single-producer single-consumer wait-free and lock-free queue written in C++11

A bounded single-producer single-consumer wait-free and lock-free queue written in C++11

SPSCQueue.h A single producer single consumer wait-free and lock-free fixed size queue written in C++11. Example SPSCQueueint q(2); auto t = std::th

Jun 21, 2022

Awesome-lockfree - A collection of resources on wait-free and lock-free programming

Awesome Lock-Free A collection of resources on wait-free and lock-free programming. 🔥 🔥 🔥 Even better resource from MattPD: C++ links: atomics, loc

Jun 14, 2022

A collection of hash tables for parallel programming, including lock-free, wait-free tables.

Hatrack Hash tables for parallel programming This project consisists of fast hash tables suitable for parallel programming, including multiple lock-fr

Jun 10, 2022

Use an esp32 as gateway for the Eqiva Bluetooth smart lock to integrate it in Home Assistant as MQTT lock

esp32-keyble-homeassistant Use an esp32 as gateway for the Eqiva Bluetooth smart lock to integrate it in Home Assistant as MQTT lock Based on the grea

Apr 28, 2022

A modern-day Boss Key software tool. Switch instantly from work to play & play to work with Bosky.

Bosky By: Seanpm2001, Bosky-dev Et; Al. Top README.md Read this article in a different language Sorted by: A-Z Sorting options unavailable ( af Afrika

Nov 11, 2021

Hexagonal hierarchical geospatial indexing system

H3: A Hexagonal Hierarchical Geospatial Indexing System H3 is a geospatial indexing system using a hexagonal grid that can be (approximately) subdivid

Jun 17, 2022
afl/afl++ with a hierarchical seed scheduler

This is developed based on AFLplusplus (2.68c, Qemu mode), thanks to its amazing maintainers and community Build and Run Please follow the instruction

May 18, 2022
A easy to use multithreading thread pool library for C. It is a handy stream like job scheduler with an automatic garbage collector. This is a multithreaded job scheduler for non I/O bound computation.

A easy to use multithreading thread pool library for C. It is a handy stream-like job scheduler with an automatic garbage collector for non I/O bound computation.

Jun 4, 2022
Fast, generalized, implementation of the Chase-Lev lock-free work-stealing deque for C++17

riften::Deque A bleeding-edge lock-free, single-producer multi-consumer, Chase-Lev work stealing deque as presented in the paper "Dynamic Circular Wor

May 29, 2022
Concurrent-deque - Lock-free concurrent work stealing deque in C++

A lock-free work-stealing deque This is a C++ implementation of the Chase-Lev deque, a concurrent single-producer, multi-consumer queue presented in t

Mar 13, 2022
A bounded single-producer single-consumer wait-free and lock-free queue written in C++11
A bounded single-producer single-consumer wait-free and lock-free queue written in C++11

SPSCQueue.h A single producer single consumer wait-free and lock-free fixed size queue written in C++11. Example SPSCQueue<int> q(2); auto t = std::th

Jun 21, 2022
Awesome-lockfree - A collection of resources on wait-free and lock-free programming

Awesome Lock-Free A collection of resources on wait-free and lock-free programming. ?? ?? ?? Even better resource from MattPD: C++ links: atomics, loc

Jun 14, 2022
Jun 18, 2022
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Jun 24, 2022
A fast single-producer, single-consumer lock-free queue for C++

A single-producer, single-consumer lock-free queue for C++ This mini-repository has my very own implementation of a lock-free queue (that I designed f

Jun 23, 2022
Simple and fast C library implementing a thread-safe API to manage hash-tables, linked lists, lock-free ring buffers and queues

libhl C library implementing a set of APIs to efficiently manage some basic data structures such as : hashtables, linked lists, queues, trees, ringbuf

Jun 15, 2022