Fast resizable golang semaphore primitive

Overview

semaphore

Awesome Build Status Go Report Card Coverage Status GoDoc License

Fast resizable golang semaphore based on CAS

  • allows weighted acquire/release;
  • supports cancellation via context;
  • allows change semaphore limit after creation;
  • faster than channel based semaphores.

Usage

Initiate

import "github.com/marusama/semaphore/v2"
...
sem := semaphore.New(5) // new semaphore with limit = 5

Acquire

sem.Acquire(ctx, n)     // acquire n with context
sem.TryAcquire(n)       // try acquire n without blocking 
...
ctx := context.WithTimeout(context.Background(), time.Second)
sem.Acquire(ctx, n)     // acquire n with timeout

Release

sem.Release(n)          // release n

Change semaphore limit

sem.SetLimit(new_limit) // set new semaphore limit

Some benchmarks

Run on MacBook Pro (2017) with 3,1GHz Core i5 cpu and 8GB DDR3 ram, macOS High Sierra, go version go1.11.4 darwin/amd64:

// this semaphore:
BenchmarkSemaphore_Acquire_Release_under_limit_simple-4                   	20000000	        98.6 ns/op	      96 B/op	       1 allocs/op
BenchmarkSemaphore_Acquire_Release_under_limit-4                          	 1000000	      1593 ns/op	     960 B/op	      10 allocs/op
BenchmarkSemaphore_Acquire_Release_over_limit-4                           	  100000	     20760 ns/op	    9600 B/op	     100 allocs/op


// some other implementations:

// golang.org/x/sync/semaphore:
BenchmarkXSyncSemaphore_Acquire_Release_under_limit_simple-4              	50000000	        34.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkXSyncSemaphore_Acquire_Release_under_limit-4                     	 1000000	      1103 ns/op	       0 B/op	       0 allocs/op
BenchmarkXSyncSemaphore_Acquire_Release_over_limit-4                      	   30000	     65927 ns/op	   15985 B/op	     299 allocs/op

// github.com/abiosoft/semaphore:
BenchmarkAbiosoftSemaphore_Acquire_Release_under_limit_simple-4           	10000000	       208 ns/op	       0 B/op	       0 allocs/op
BenchmarkAbiosoftSemaphore_Acquire_Release_under_limit-4                  	  500000	      3147 ns/op	       0 B/op	       0 allocs/op
BenchmarkAbiosoftSemaphore_Acquire_Release_over_limit-4                   	   50000	     37148 ns/op	       0 B/op	       0 allocs/op

// github.com/dropbox/godropbox
BenchmarkDropboxBoundedSemaphore_Acquire_Release_under_limit_simple-4     	20000000	        75.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkDropboxBoundedSemaphore_Acquire_Release_under_limit-4            	 2000000	       629 ns/op	       0 B/op	       0 allocs/op
BenchmarkDropboxBoundedSemaphore_Acquire_Release_over_limit-4             	  200000	     27308 ns/op	       0 B/op	       0 allocs/op
BenchmarkDropboxUnboundedSemaphore_Acquire_Release_under_limit_simple-4   	50000000	        39.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkDropboxUnboundedSemaphore_Acquire_Release_under_limit-4          	 1000000	      1170 ns/op	       0 B/op	       0 allocs/op
BenchmarkDropboxUnboundedSemaphore_Acquire_Release_over_limit-4           	  100000	     21013 ns/op	       0 B/op	       0 allocs/op

// github.com/kamilsk/semaphore
BenchmarkKamilskSemaphore_Acquire_Release_under_limit_simple-4            	20000000	       110 ns/op	      16 B/op	       1 allocs/op
BenchmarkKamilskSemaphore_Acquire_Release_under_limit-4                   	 1000000	      1520 ns/op	     160 B/op	      10 allocs/op
BenchmarkKamilskSemaphore_Acquire_Release_over_limit-4                    	   50000	     42693 ns/op	    1600 B/op	     100 allocs/op

// github.com/pivotal-golang/semaphore
BenchmarkPivotalGolangSemaphore_Acquire_Release_under_limit_simple-4      	 3000000	       558 ns/op	     136 B/op	       2 allocs/op
BenchmarkPivotalGolangSemaphore_Acquire_Release_under_limit-4             	  200000	      9530 ns/op	    1280 B/op	      20 allocs/op
BenchmarkPivotalGolangSemaphore_Acquire_Release_over_limit-4              	   10000	    111264 ns/op	   12801 B/op	     200 allocs/op

You can rerun these benchmarks, just checkout benchmarks branch and run go test -bench=. -benchmem ./bench/...

Issues
  • Deadlock when not using the same value for weights for acquiring and releasing across the entire semaphore .

    Deadlock when not using the same value for weights for acquiring and releasing across the entire semaphore .

    Hello, I encountered a bug that is causing a deadlock when I am using this weighted semaphore implementation. Acquire(N) by definition should block until there are enough N in the semaphore, then it should unblock after acquiring N from the semaphore. This is also the behavior of golang.org/x/sync/semaphore.

    Now the behavior I am facing is that Acquire(N) will Deadlock when not using the same value for N for acquiring and releasing across the entire semaphore.

    package main
    
    import (
    	"context"
    	"github.com/marusama/semaphore"
    	"runtime"
    	"time"
    )
    
    func main() {
    
    	limit := 10
    	GOMAXPROCS := 1
    	
    	runtime.GOMAXPROCS(GOMAXPROCS)
    	semp := semaphore.New(limit)
    
    	for i := 0; i < limit; i++ {
    		_ = semp.Acquire(context.TODO(), 1)
    		go func() {
    			time.Sleep(1000 * time.Millisecond)
    			semp.Release(1)
    		}()
    	}
    
    	/*	 
    	//  NO DEADLOCK
    	 _ = semp.Acquire(context.TODO(), 1)
     	*/
    	
    	//  DEADLOCK WHEN GOMAXPROCS < 2
    	 _ = semp.Acquire(context.TODO(), 2)
    	
    
    	//  DEADLOCK WHEN GOMAXPROCS < limit
    	// _ = semp.Acquire(context.TODO(), limit)
    }
    
    

    Output

    
    fatal error: all goroutines are asleep - deadlock!
    
    goroutine 1 [select]:
    github.com/marusama/semaphore.(*semaphore).Acquire(0xc00005e180, 0x10c3f80, 0xc000012078, 0x2, 0x0, 0x0)
    	/Users/sherifabdlnaby/go/pkg/mod/github.com/marusama/[email protected]/semaphore.go:120 +0x19d
    main.main()
    	/Users/sherifabdlnaby/awesomeProject1/Main.go:32 +0x13f
    
    

    Expected Output

    Process finished with exit code 0
    

    Acquire(N) should block until there is enough N.

    Deadlocking code

    https://github.com/marusama/semaphore/blob/edd5217b5829b6bfbb01fcff1c8b4b4335c3fca6/semaphore.go#L120-L126

    opened by sherifabdlnaby 4
  • New should accept a limit of 0

    New should accept a limit of 0

    It may not appear to be useful at first glance, but I think it would be reasonable for New and SetLimit to accept a limit of 0 in cases where the semaphore coordinates access to a number of resources that is changing. It's reasonable for the number of resources to drop to zero and then increase again, all while goroutines await an increase in resources. Thoughts?

    enhancement 
    opened by kylrth 3
  • Fix a possible deadlock when Acquiring/Releasing different weights.

    Fix a possible deadlock when Acquiring/Releasing different weights.

    Hello, so after further debugging for #3 I found out that it actually has nothing to do with GOMAXPROCS as I assumed, it is just that different valuesGOMAXPROCS was affecting when releases happen in my example which made deadlocks less common when their values is greater.

    The real issue happened when you don't use the same value for weights for acquiring and releasing across the entire semaphore .

    The deadlock happened because the Aquire function didn't receive any signal on the broadcast channel.

    Signal wasn't sent unless count(before release) >= limit, logically this assumes that a release of n will only notify waiters that are acquiring n too. the catch is if an Acquire of value (> n) is blocking it won't be notified by the releasing method because count(before release) < limit hence it assumes that no waiters are blocking. while in-fact an Acquire is blocking as ( count(before acquiring) + weight ) > limit.

    The downside of this approach is that now a release is broadcast-ed on every release and another broadcast channel is allocated which will negatively affect performance.

    Benchmarks:

    After:

    goos: darwin
    goarch: amd64
    pkg: github.com/marusama/semaphore/bench
    BenchmarkSemaphore_Acquire_Release_under_limit_simple-4   	20000000	       109 ns/op
    BenchmarkSemaphore_Acquire_Release_under_limit-4          	  500000	      2589 ns/op
    BenchmarkSemaphore_Acquire_Release_over_limit-4           	   50000	     27836 ns/op
    PASS
    

    Before:

    goos: darwin
    goarch: amd64
    pkg: github.com/marusama/semaphore/bench
    BenchmarkSemaphore_Acquire_Release_under_limit_simple-4   	50000000	        24.8 ns/op
    BenchmarkSemaphore_Acquire_Release_under_limit-4          	 1000000	      1371 ns/op
    BenchmarkSemaphore_Acquire_Release_over_limit-4           	  100000	     14299 ns/op
    PASS
    

    While this is unfortunate I think with the current implementation there is no way to avoid broadcasting releasing signal on every release unless weights is forced to be unified.

    I've also included a test to that case when using different values for acquiring and releasing.

    opened by sherifabdlnaby 2
  • Fix race condition resulting in hung Acquire()

    Fix race condition resulting in hung Acquire()

    We detected a race condition that can cause a call to Acquire() to hang indefinitely waiting on the wrong broadcast channel. The condition occured like this:

    1. T1 calls Acquire() and discovers the semaphore is full.
    2. T2 calls Release() and decrements the semaphore.
    3. T2 swaps the broadcast channel for a new broadcast channel, and closes the old broadcast channel.
    4. T1 grabs the broadcast channel, which is the new broadcast channel which will not be signalled.

    This condition is not permanent; the blocked thread will become unblocked as soon as the semaphore fills up again, and a Release() broadcasts on this channel. However, we were running into situations where relatiely rare events could cause very long hangs due to this condition.

    Commit adds a test case which reproduces this situation quite readily; as a race condition it does not reproduce 100% of the time, but it reproduces very rapidly under stress, at least 30% of the time.

    Commit also adds a fix; in Acquire(), after grabbing the old broadcast channel the thread checks that the state has not changed (or at least, that the semaphore is still full); this ensures that the broadcast channel that was taken will eventually be signalled by a currently active process.

    good first issue 
    opened by mrtracy 2
Releases(v2.5.0)
Owner
Bator Tsyrendylykov
Bator Tsyrendylykov
🚦 Semaphore pattern implementation with timeout of lock/unlock operations.

?? semaphore Semaphore pattern implementation with timeout of lock/unlock operations. ?? Idea The semaphore provides API to control access to a shared

Kamil Samigullin 89 May 11, 2022
Simple in-memory job queue for Golang using worker-based dispatching

artifex Simple in-memory job queue for Golang using worker-based dispatching Documentation here: https://godoc.org/github.com/mborders/artifex Cron jo

Matthew Borders 135 Jul 4, 2022
CyclicBarrier golang implementation

cyclicbarrier CyclicBarrier is a synchronizer that allows a set of goroutines to wait for each other to reach a common execution point, also called a

Bator Tsyrendylykov 97 May 28, 2022
TryLock support on read-write lock for Golang

go-trylock TryLock support on read-write lock for Golang Interface go-trylock implements sync.Locker. Have same interfaces with sync.RWMutex Documenta

Guoqiang Chen 28 Mar 24, 2022
golang worker pool , Concurrency limiting goroutine pool

golang worker pool δΈ­ζ–‡θ―΄ζ˜Ž Concurrency limiting goroutine pool. Limits the concurrency of task execution, not the number of tasks queued. Never blocks su

xxj 398 Jun 21, 2022
Golang simple thread pool implementation

Golang Threadpool implementation Scalable threadpool implementation using Go to handle the huge network trafic. Install go get github.com/shettyh/thre

Manjunath Shetty 71 May 4, 2022
Off heap golang memory pool

Stealthpool stealthpool provides a memory pool that allocates blocks off-heap that will NOT be tracked by the garbage collector. The name stealthpool

null 56 Jul 3, 2022
Queue is a Golang library for spawning and managing a Goroutine pool

Queue is a Golang library for spawning and managing a Goroutine pool, Alloowing you to create multiple worker according to limit CPU number of machine.

Bo-Yi Wu 193 Jul 6, 2022
Queue is a Golang library for spawning and managing a Goroutine pool

Queue is a Golang library for spawning and managing a Goroutine pool, Alloowing you to create multiple worker according to limit CPU number of machine.

golang-queue 190 Jun 28, 2022
This repository collects common concurrency patterns in Golang

Go Concurrency Patterns This repository collects common concurrency patterns in Golang Materials Concurrency is not parallelism Go Concurrency Pattern

Kha Nguyen 1.7k Jul 3, 2022
goroutine pool in golang

goroutine pool in golang

wksw 1 Nov 1, 2021
Routine - ThreadLocal for golang

routine δΈ­ζ–‡η‰ˆ routine encapsulates and provides some easy-to-use, high-performance

Tim 35 Jun 17, 2022
Golang Implementation of Worker Pool/ Thread Pool

Golang Implementation of Worker Pool/ Thread Pool

Telkom DEV 1 Jun 18, 2022
Goworkers - Zero dependency Golang worker pool

Golang Worker Pool Zero dependency golang goroutines pool library. It is useful

Madhav Bhargava 0 Apr 28, 2022
Go-miningcore-pool - Miningcore Pool written in GOlang

Go-Miningcore-Pool (COMING SOON) Miningcore Pool written in GOlang 0x01 Configur

miningcore.com 2 Apr 24, 2022
Worker - A Golang library that provides worker pools

Worker A Golang library that provides worker pools. Usage See *_test.go files. T

Fatih Cetinkaya 2 Apr 15, 2022
gpool - a generic context-aware resizable goroutines pool to bound concurrency based on semaphore.

gpool - a generic context-aware resizable goroutines pool to bound concurrency. Installation $ go get github.com/sherifabdlnaby/gpool import "github.c

Sherif Abdel-Naby 84 Feb 21, 2022
🚦 Semaphore pattern implementation with timeout of lock/unlock operations.

?? semaphore Semaphore pattern implementation with timeout of lock/unlock operations. ?? Idea The semaphore provides API to control access to a shared

Kamil Samigullin 89 May 11, 2022
Null Types, Safe primitive type conversion and fetching value from complex structures.

Typ Typ is a library providing a powerful interface to impressive user experience with conversion and fetching data from built-in types in Golang Feat

Gurukami 32 Apr 21, 2022
MySQL Backed Locking Primitive

go-mysql-lock go-mysql-lock provides locking primitive based on MySQL's GET_LOCK Lock names are strings and MySQL enforces a maximum length on lock na

Sanket Patel 45 Jun 18, 2022
Scan database/sql rows directly to structs, slices, and primitive types

Scan Scan standard lib database rows directly to structs or slices. For the most comprehensive and up-to-date docs see the godoc Examples Multiple Row

Brett Jones 274 Jul 2, 2022
A faster RWLock primitive in Go, 2-3 times faster than RWMutex. A Go implementation of concurrency control algorithm in paper

Go Left Right Concurrency A Go implementation of the left-right concurrency control algorithm in paper <Left-Right - A Concurrency Control Technique w

wangyi 40 Apr 4, 2022
Simple & Primitive multi client communication system

What is this Simple & Primitive multi client communication system. e.g. chat system for larning Supported Broadcast message Unicast message Not Suppor

gamiken 0 Dec 3, 2021
Slice conversion between primitive types

sliceconv Sliceconv implements conversions to and from string representations of primitive types on entire slices. The package supports types int, flo

Henry Sarabia 8 Jan 24, 2022
Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transforming and consuming them.

iter Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transformi

Matthew Toohey 24 Jun 7, 2022
Go module that provides primitive functional programming utilities.

Functional Functional provides a small set of pure functions that are common in functional programming languages, such as Reduce, Map, Filter, etc. Wi

Liam Mueller 1 Jun 12, 2022
llb - It's a very simple but quick backend for proxy servers. Can be useful for fast redirection to predefined domain with zero memory allocation and fast response.

llb What the f--k it is? It's a very simple but quick backend for proxy servers. You can setup redirect to your main domain or just show HTTP/1.1 404

Kirill Danshin 12 Jan 23, 2022
moss - a simple, fast, ordered, persistable, key-val storage library for golang

moss moss provides a simple, fast, persistable, ordered key-val collection implementation as a 100% golang library. moss stands for "memory-oriented s

null 869 Jun 21, 2022
Simple, fast and scalable golang rpc library for high load

gorpc Simple, fast and scalable golang RPC library for high load and microservices. Gorpc provides the following features useful for highly loaded pro

Aliaksandr Valialkin 651 Jun 20, 2022