Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #84245 > unrolled thread

A thread-queue

Back to article view | Back to comp.lang.c++

Contents

  A thread-queue Bonita Montero <Bonita.Montero@gmail.com> - 2022-05-24 04:07 +0200
    Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-25 13:58 -0700
      Re: A thread-queue Bo Persson <bo@bo-persson.se> - 2022-05-26 01:04 +0200
        Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-25 20:58 -0700
        Re: A thread-queue Bonita Montero <Bonita.Montero@gmail.com> - 2022-05-26 16:20 +0200
          Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-26 22:40 -0700
            Re: A thread-queue Bonita Montero <Bonita.Montero@gmail.com> - 2022-05-27 11:33 +0200
              Re: A thread-queue Bonita Montero <Bonita.Montero@gmail.com> - 2022-05-27 14:26 +0200
                Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-27 14:18 -0700
                  Re: A thread-queue scott@slp53.sl.home (Scott Lurndal) - 2022-05-27 21:53 +0000
                    Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-27 15:43 -0700
                      Re: A thread-queue scott@slp53.sl.home (Scott Lurndal) - 2022-05-28 14:51 +0000
                    Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-27 18:24 -0700
                      Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-27 18:26 -0700
                      Re: A thread-queue scott@slp53.sl.home (Scott Lurndal) - 2022-05-28 14:56 +0000
                        Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-28 16:49 -0700
                          Re: A thread-queue red floyd <no.spam.here@its.invalid> - 2022-05-28 17:16 -0700
                            Re: A thread-queue "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-30 16:00 -0700
                  Re: A thread-queue Bonita Montero <Bonita.Montero@gmail.com> - 2022-05-28 07:16 +0200
      Re: A thread-queue Bonita Montero <Bonita.Montero@gmail.com> - 2022-05-26 16:15 +0200

#84245 — A thread-queue

This is a thread-queue I've written:

#pragma once
#include <deque>
#include <mutex>
#include <condition_variable>
#include <utility>
#include <concepts>
#include <list>

template<typename QueueType>
concept thread_queue_concept =
	std::same_as<QueueType, std::deque<typename QueueType::value_type, 
typename QueueType::allocator_type>>
	|| std::same_as<QueueType, std::list<typename QueueType::value_type, 
typename QueueType::allocator_type>>;

template<typename QueueType>
	requires thread_queue_concept<QueueType>
struct thread_queue
{
	using value_type = typename QueueType::value_type;
	thread_queue();
	explicit thread_queue( typename QueueType::allocator_type const &alloc );
	thread_queue( thread_queue &&other );
	thread_queue &operator =( thread_queue const &other );
	thread_queue &operator =( thread_queue &&other );
	bool empty() const;
	std::size_t size() const;
	void shrink_to_fit();
	void clear();
	template<typename ... Args>
		requires std::is_constructible_v<typename QueueType::value_type, Args ...>
	void enque( Args &&... args );
	template<typename Producer>
		requires requires( Producer producer ) { { producer() } -> 
std::same_as<std::pair<bool, typename QueueType::value_type>>; }
	void enqueue_multiple( Producer producer );
	template<typename Consumer>
		requires requires( Consumer consumer, typename QueueType::value_type 
value ) { { consumer( std::move( value ) ) } -> std::same_as<bool>; }
	void dequeue_multiple( Consumer consumer );
	typename QueueType::value_type dequeue();
	void swap( thread_queue &other );
private:
	mutable std::mutex m_mtx;
	mutable std::condition_variable m_cv;
	QueueType m_queue;
};

template<typename QueueType>
	requires thread_queue_concept<QueueType>
thread_queue<QueueType>::thread_queue()
{
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
thread_queue<QueueType>::thread_queue( typename 
QueueType::allocator_type const &alloc ) :
	m_queue( alloc )
{
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
thread_queue<QueueType>::thread_queue( thread_queue &&other )
{
	using namespace std;
	lock_guard lock( other.m_mtx );
	m_queue = move( other.m_queue );
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
thread_queue<QueueType> &thread_queue<QueueType>::thread_queue::operator 
=( thread_queue const &other )
{
	std::lock_guard
		ourLock( m_mtx ),
		otherLock( other.m_mtx );
	m_queue = other.m_queue;
	return *this;
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
thread_queue<QueueType> &thread_queue<QueueType>::thread_queue::operator 
=( thread_queue &&other )
{
	using namespace std;
	lock_guard
		ourLock( m_mtx ),
		otherLock( other.m_mtx );
	m_queue = move( other.m_queue );
	return *this;
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
bool thread_queue<QueueType>::thread_queue::empty() const
{
	std::lock_guard lock( m_mtx );
	return m_queue.empty();
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
std::size_t thread_queue<QueueType>::thread_queue::size() const
{
	std::lock_guard lock( m_mtx );
	return m_queue.size();
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
void thread_queue<QueueType>::thread_queue::shrink_to_fit()
{
	std::lock_guard lock( m_mtx );
	return m_queue.shrink_to_fit();
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
void thread_queue<QueueType>::thread_queue::clear()
{
	std::lock_guard lock( m_mtx );
	m_queue.clear();
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
template<typename ... Args>
	requires std::is_constructible_v<typename QueueType::value_type, Args ...>
void thread_queue<QueueType>::thread_queue::enque( Args &&... args )
{
	using namespace std;
	unique_lock lock( m_mtx );
	m_queue.emplace_front( forward<Args>( args ) ... );
	m_cv.notify_one();
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
typename QueueType::value_type 
thread_queue<QueueType>::thread_queue::dequeue()
{
	using namespace std;
	unique_lock lock( m_mtx );
	while( m_queue.empty() )
		m_cv.wait( lock );
	value_type value = move( m_queue.back() );
	m_queue.pop_back();
	return value;
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
template<typename Producer>
	requires requires( Producer producer ) { { producer() } -> 
std::same_as<std::pair<bool, typename QueueType::value_type>>; }
void thread_queue<QueueType>::enqueue_multiple( Producer producer )
{
	using namespace std;
	lock_guard lock( m_mtx );
	for( std::pair<bool, value_type> ret; (ret = move( producer() )).first; )
		m_queue.emplace_front( move( ret.second ) ),
		m_cv.notify_one();
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
template<typename Consumer>
	requires requires( Consumer consumer, typename QueueType::value_type 
value ) { { consumer( std::move( value ) ) } -> std::same_as<bool>; }
void thread_queue<QueueType>::dequeue_multiple( Consumer consumer )
{
	using namespace std;
	unique_lock lock( m_mtx );
	for( ; ; )
	{
		while( m_queue.empty() )
			m_cv.wait( lock );
		try
		{
			bool cont = consumer( move( m_queue.back() ) );
			m_queue.pop_back();
			if( !cont )
				return;
		}
		catch( ... )
		{
			m_queue.pop_back();
			throw;
		}
	}
}

template<typename QueueType>
	requires thread_queue_concept<QueueType>
void thread_queue<QueueType>::thread_queue::swap( thread_queue &other )
{
	std::lock_guard
		ourLock( m_mtx ),
		otherLock( other.m_mtx );
	m_queue.swap( other.m_queue );
}


The only template-parameter is BaseType, which can be a std::deque type
or std::list type, restricted with thread_queue_concept. This class uses
this type as the internal queue type. Chose that BaseType that is most
efficient for your application. I might have restricted the class on a
more differentiated thread_queue_concepts that checks for all the used
parts of BaseType so that this class might apply for other types
compatible to std::list<> or std::deque<> but I was too lazy to imple-
ment that for the unlikely case that someone implements something like
that on his own. One advantage of this code are enqueue_multiple and
dequeue_multiple. These functions are given a function-object, usually
a lambda, which can enqueue or dequeue multiple items with only one
locking step. For enqueue this always holds true, for dequeue this
depends on if the queue has elements to fetch or not.
enqueue_multiple usually makes sense if you have one producer and
multiple consumers. It results in longer periods holding the lock and
therefore it makes sense only if the items can be produced or move fast.
dequeue_multiple usually makes sense if you have multiple producers and
one consumer. Here we also have longer locking periods, but as objects
are usually only have fast moves here, this normally doesn't hurt.
If the consumer function object of the dequeue_multiple throws an
exception while consuming, the exception is caugt and the element
provided to the consumer (rvalue-refernce inside the underlying queue
types object) is removed.
If you like to use this class with C++11 you have to remove the concepts
or disable them with #if defined(__cpp_concepts).

[toc] | [next] | [standalone]

#84262

On 5/23/2022 7:07 PM, Bonita Montero wrote:
> This is a thread-queue I've written:
[...]
> template<typename QueueType>
>      requires thread_queue_concept<QueueType>
> thread_queue<QueueType> &thread_queue<QueueType>::thread_queue::operator 
> =( thread_queue const &other )
> {
>      std::lock_guard
>          ourLock( m_mtx ),
>          otherLock( other.m_mtx );
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This is a little scary. lock ordering issues come to mind. Fwiw, this is 
why I created multimutex:

https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ


>      m_queue = other.m_queue;
>      return *this;
> }
[...]

[toc] | [prev] | [next] | [standalone]

#84263

On 2022-05-25 at 22:58, Chris M. Thomasson wrote:
> On 5/23/2022 7:07 PM, Bonita Montero wrote:
>> This is a thread-queue I've written:
> [...]
>> template<typename QueueType>
>>      requires thread_queue_concept<QueueType>
>> thread_queue<QueueType> 
>> &thread_queue<QueueType>::thread_queue::operator =( thread_queue const 
>> &other )
>> {
>>      std::lock_guard
>>          ourLock( m_mtx ),
>>          otherLock( other.m_mtx );
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> 
> This is a little scary. lock ordering issues come to mind. Fwiw, this is 
> why I created multimutex:
> 
> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
> 

The standard library version is scoped_lock that should handle lock ordering

std::scoped_lock locks(m_mtx, other.m_mtx);


https://en.cppreference.com/w/cpp/thread/scoped_lock

[toc] | [prev] | [next] | [standalone]

#84264

On 5/25/2022 4:04 PM, Bo Persson wrote:
> On 2022-05-25 at 22:58, Chris M. Thomasson wrote:
>> On 5/23/2022 7:07 PM, Bonita Montero wrote:
>>> This is a thread-queue I've written:
>> [...]
>>> template<typename QueueType>
>>>      requires thread_queue_concept<QueueType>
>>> thread_queue<QueueType> 
>>> &thread_queue<QueueType>::thread_queue::operator =( thread_queue 
>>> const &other )
>>> {
>>>      std::lock_guard
>>>          ourLock( m_mtx ),
>>>          otherLock( other.m_mtx );
>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>
>> This is a little scary. lock ordering issues come to mind. Fwiw, this 
>> is why I created multimutex:
>>
>> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
>>
> 
> The standard library version is scoped_lock that should handle lock 
> ordering
> 
> std::scoped_lock locks(m_mtx, other.m_mtx);
> 
> 
> https://en.cppreference.com/w/cpp/thread/scoped_lock

Ahhh, I have never used it before. Thanks for the heads up Bo. I see 
that it uses the traditional try_lock method. The multimutex I did 
simply hashes pointers into an index of a table of locks; sorts and 
removes duplicates of the resulting indexes; and takes the locks. The 
sorting always avoids deadlock. I remove duplicates in order to get 
around having to use recursive locks.
..

[toc] | [prev] | [next] | [standalone]

#84270

Am 26.05.2022 um 01:04 schrieb Bo Persson:
> On 2022-05-25 at 22:58, Chris M. Thomasson wrote:
>> On 5/23/2022 7:07 PM, Bonita Montero wrote:
>>> This is a thread-queue I've written:
>> [...]
>>> template<typename QueueType>
>>>      requires thread_queue_concept<QueueType>
>>> thread_queue<QueueType> 
>>> &thread_queue<QueueType>::thread_queue::operator =( thread_queue 
>>> const &other )
>>> {
>>>      std::lock_guard
>>>          ourLock( m_mtx ),
>>>          otherLock( other.m_mtx );
>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>
>> This is a little scary. lock ordering issues come to mind. Fwiw, this 
>> is why I created multimutex:
>>
>> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
>>
> 
> The standard library version is scoped_lock that should handle lock 
> ordering
> std::scoped_lock locks(m_mtx, other.m_mtx);

I wouldn't have a deadlock if I'd use scoped lock here. But I'd have
a race condition. Does the first thread first opy the queue from the
second or vice versa ? As this situaton is generally avoided I don't
neeed a scoped lock.

[toc] | [prev] | [next] | [standalone]

#84276

On 5/26/2022 7:20 AM, Bonita Montero wrote:
> Am 26.05.2022 um 01:04 schrieb Bo Persson:
>> On 2022-05-25 at 22:58, Chris M. Thomasson wrote:
>>> On 5/23/2022 7:07 PM, Bonita Montero wrote:
>>>> This is a thread-queue I've written:
>>> [...]
>>>> template<typename QueueType>
>>>>      requires thread_queue_concept<QueueType>
>>>> thread_queue<QueueType> 
>>>> &thread_queue<QueueType>::thread_queue::operator =( thread_queue 
>>>> const &other )
>>>> {
>>>>      std::lock_guard
>>>>          ourLock( m_mtx ),
>>>>          otherLock( other.m_mtx );
>>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>>
>>> This is a little scary. lock ordering issues come to mind. Fwiw, this 
>>> is why I created multimutex:
>>>
>>> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
>>>
>>
>> The standard library version is scoped_lock that should handle lock 
>> ordering
>> std::scoped_lock locks(m_mtx, other.m_mtx);
> 
> I wouldn't have a deadlock if I'd use scoped lock here. But I'd have
> a race condition. Does the first thread first opy the queue from the
> second or vice versa ? As this situaton is generally avoided I don't
> neeed a scoped lock.
> 

The calling thread would acquire both queue locks in a way that avoids 
deadlock (hashed mutexes, std::scoped_lock, ect...). Once it does that, 
it owns both of them. All other threads are locked out.

[toc] | [prev] | [next] | [standalone]

#84280

Am 27.05.2022 um 07:40 schrieb Chris M. Thomasson:
> On 5/26/2022 7:20 AM, Bonita Montero wrote:
>> Am 26.05.2022 um 01:04 schrieb Bo Persson:
>>> On 2022-05-25 at 22:58, Chris M. Thomasson wrote:
>>>> On 5/23/2022 7:07 PM, Bonita Montero wrote:
>>>>> This is a thread-queue I've written:
>>>> [...]
>>>>> template<typename QueueType>
>>>>>      requires thread_queue_concept<QueueType>
>>>>> thread_queue<QueueType> 
>>>>> &thread_queue<QueueType>::thread_queue::operator =( thread_queue 
>>>>> const &other )
>>>>> {
>>>>>      std::lock_guard
>>>>>          ourLock( m_mtx ),
>>>>>          otherLock( other.m_mtx );
>>>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>>>
>>>> This is a little scary. lock ordering issues come to mind. Fwiw, 
>>>> this is why I created multimutex:
>>>>
>>>> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
>>>>
>>>
>>> The standard library version is scoped_lock that should handle lock 
>>> ordering
>>> std::scoped_lock locks(m_mtx, other.m_mtx);
>>
>> I wouldn't have a deadlock if I'd use scoped lock here. But I'd have
>> a race condition. Does the first thread first opy the queue from the
>> second or vice versa ? As this situaton is generally avoided I don't
>> neeed a scoped lock.
>>
> 
> The calling thread would acquire both queue locks in a way that avoids 
> deadlock (hashed mutexes, std::scoped_lock, ect...). Once it does that, 
> it owns both of them. All other threads are locked out.

As I said there would be a deadlock.
But it woudln't make sense to copy the queue vom two sides at once
because this would result in a race-condition and the contents of
both queues aren't garanteed to look like what you would expect,
even with a scoped lock.
So copying the queue from two sides at once should be generally
avoided. As this situaton wouldn't practically happen there's no
need for a scoped lock.

[toc] | [prev] | [next] | [standalone]

#84281

On one side the situation Chis and others are afraid of doesn't
actually happen. On the other side _copying_ the contents of a
thread queue without consuming them isn't a requirement to a
thread queue. So I removed the copy-constructor and left the
move constructor which does everthing that's needed.

[toc] | [prev] | [next] | [standalone]

#84296

On 5/27/2022 5:26 AM, Bonita Montero wrote:
> On one side the situation Chis and others are afraid of doesn't
> actually happen. On the other side _copying_ the contents of a
> thread queue without consuming them isn't a requirement to a
> thread queue. So I removed the copy-constructor and left the
> move constructor which does everthing that's needed.

Okay. However, it still makes me a bit nervous when I see code acquiring 
more than one lock at a time. I have had some horror shows trying to 
debug code written by others... One of the authors said, no need to 
worry because the locks are recursive (yuck) without a care in the world 
about lock ordering... Argh!

[toc] | [prev] | [next] | [standalone]

#84300

"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>On 5/27/2022 5:26 AM, Bonita Montero wrote:
>> On one side the situation Chis and others are afraid of doesn't
>> actually happen. On the other side _copying_ the contents of a
>> thread queue without consuming them isn't a requirement to a
>> thread queue. So I removed the copy-constructor and left the
>> move constructor which does everthing that's needed.
>
>Okay. However, it still makes me a bit nervous when I see code acquiring 
>more than one lock at a time. I have had some horror shows trying to 
>debug code written by others... One of the authors said, no need to 
>worry because the locks are recursive (yuck) without a care in the world 
>about lock ordering... Argh!

Back in the early 1980s we were updating the architecture
of the Burroughs B3500/B4700/B4900 to support SMP and a larger
physical memory space.   One of the features added to support
SMP was hardware instructions providing capabilities similar to mutexes and posix
condition variables.

To prevent deadlock, every lock has a 'canonical lock number' (CLN) that
ranges from 1 to 9999.  The hardware will not allow the LOCK
instruction to complete successfully if there has already
been a lock acquired with a equal or higher CLN; the instruction
will fault instead.   Likewise the UNLK instruction would fault
of the lock was equal to the highest CLN stored in the hardware
task data structure.

This prevented A-B deadlocks, circular
locking paths and out-of-order unlocks.

Similarly, the 'event' instruction provided wait, signal and
broadcast variants.

As all these instructions were used by the kernel (MCP) as well
as user-mode applications, there was a microkernel that handled
thread (task) scheduling.  MCP functions were always invoked on
behalf of either a user task or an operating system Independent
Runner (modern thread), and the microkernel would handle scheduling
for LOCK/UNLK events and WAIT/CAUS instructions.

[toc] | [prev] | [next] | [standalone]

#84301

On 5/27/2022 2:53 PM, Scott Lurndal wrote:
> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>> On 5/27/2022 5:26 AM, Bonita Montero wrote:
>>> On one side the situation Chis and others are afraid of doesn't
>>> actually happen. On the other side _copying_ the contents of a
>>> thread queue without consuming them isn't a requirement to a
>>> thread queue. So I removed the copy-constructor and left the
>>> move constructor which does everthing that's needed.
>>
>> Okay. However, it still makes me a bit nervous when I see code acquiring
>> more than one lock at a time. I have had some horror shows trying to
>> debug code written by others... One of the authors said, no need to
>> worry because the locks are recursive (yuck) without a care in the world
>> about lock ordering... Argh!
> 
> Back in the early 1980s we were updating the architecture
> of the Burroughs B3500/B4700/B4900 to support SMP and a larger
> physical memory space.   One of the features added to support
> SMP was hardware instructions providing capabilities similar to mutexes and posix
> condition variables.
> 
> To prevent deadlock, every lock has a 'canonical lock number' (CLN) that
> ranges from 1 to 9999.  The hardware will not allow the LOCK
> instruction to complete successfully if there has already
> been a lock acquired with a equal or higher CLN; the instruction
> will fault instead.   Likewise the UNLK instruction would fault
> of the lock was equal to the highest CLN stored in the hardware
> task data structure.
> 
> This prevented A-B deadlocks, circular
> locking paths and out-of-order unlocks.
> 
> Similarly, the 'event' instruction provided wait, signal and
> broadcast variants.
> 
> As all these instructions were used by the kernel (MCP) as well
> as user-mode applications, there was a microkernel that handled
> thread (task) scheduling.  MCP functions were always invoked on
> behalf of either a user task or an operating system Independent
> Runner (modern thread), and the microkernel would handle scheduling
> for LOCK/UNLK events and WAIT/CAUS instructions.

Nice! For some reason it kind of reminds me of:

https://patents.google.com/patent/US4709326A/en

[toc] | [prev] | [next] | [standalone]

#84312

"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>On 5/27/2022 2:53 PM, Scott Lurndal wrote:
>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>>> On 5/27/2022 5:26 AM, Bonita Montero wrote:
>>>> On one side the situation Chis and others are afraid of doesn't
>>>> actually happen. On the other side _copying_ the contents of a
>>>> thread queue without consuming them isn't a requirement to a
>>>> thread queue. So I removed the copy-constructor and left the
>>>> move constructor which does everthing that's needed.
>>>
>>> Okay. However, it still makes me a bit nervous when I see code acquiring
>>> more than one lock at a time. I have had some horror shows trying to
>>> debug code written by others... One of the authors said, no need to
>>> worry because the locks are recursive (yuck) without a care in the world
>>> about lock ordering... Argh!
>> 
>> Back in the early 1980s we were updating the architecture
>> of the Burroughs B3500/B4700/B4900 to support SMP and a larger
>> physical memory space.   One of the features added to support
>> SMP was hardware instructions providing capabilities similar to mutexes and posix
>> condition variables.
>> 
>> To prevent deadlock, every lock has a 'canonical lock number' (CLN) that
>> ranges from 1 to 9999.  The hardware will not allow the LOCK
>> instruction to complete successfully if there has already
>> been a lock acquired with a equal or higher CLN; the instruction
>> will fault instead.   Likewise the UNLK instruction would fault
>> of the lock was equal to the highest CLN stored in the hardware
>> task data structure.
>> 
>> This prevented A-B deadlocks, circular
>> locking paths and out-of-order unlocks.
>> 
>> Similarly, the 'event' instruction provided wait, signal and
>> broadcast variants.
>> 
>> As all these instructions were used by the kernel (MCP) as well
>> as user-mode applications, there was a microkernel that handled
>> thread (task) scheduling.  MCP functions were always invoked on
>> behalf of either a user task or an operating system Independent
>> Runner (modern thread), and the microkernel would handle scheduling
>> for LOCK/UNLK events and WAIT/CAUS instructions.
>
>Nice! For some reason it kind of reminds me of:
>
>https://patents.google.com/patent/US4709326A/en

That sounds more like what Burroughs called "File Protect Memory"
in the 1970's (replaced by the Shared Systems Processor around
1980).

Before SMP was supported in that line of Burroughs mainframes,
the MCP supported loosely coupled shared systems (up to four
systems could share peripherals).  Unit record and tape peripherals
could be accessed from any of the systems, but the MCP or operator ensured
that only one system owned the peripheral at any one time.

Disk peripherals were (optionally) shared by all four systems in the cluster
(disk (100-byte sectors) and pack (180-byte sectors)).  Originally
part of the disk controller, File Protect Memory allowed each
of the shared hosts to lock access to blocks on the disk.  This allowed
shared access to disk files (and the directory and free-space
structures) from all four hosts.   Later, a
separate peripheral (SSP) was designed that recorded the unit/block tuples
for locked accesses to all shared disk devices.

[toc] | [prev] | [next] | [standalone]

#84302

On 5/27/2022 2:53 PM, Scott Lurndal wrote:
> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>> On 5/27/2022 5:26 AM, Bonita Montero wrote:
>>> On one side the situation Chis and others are afraid of doesn't
>>> actually happen. On the other side _copying_ the contents of a
>>> thread queue without consuming them isn't a requirement to a
>>> thread queue. So I removed the copy-constructor and left the
>>> move constructor which does everthing that's needed.
>>
>> Okay. However, it still makes me a bit nervous when I see code acquiring
>> more than one lock at a time. I have had some horror shows trying to
>> debug code written by others... One of the authors said, no need to
>> worry because the locks are recursive (yuck) without a care in the world
>> about lock ordering... Argh!
> 
> Back in the early 1980s we were updating the architecture
> of the Burroughs B3500/B4700/B4900 to support SMP and a larger
> physical memory space.   One of the features added to support
> SMP was hardware instructions providing capabilities similar to mutexes and posix
> condition variables.
> 
> To prevent deadlock, every lock has a 'canonical lock number' (CLN) that
> ranges from 1 to 9999.  The hardware will not allow the LOCK
> instruction to complete successfully if there has already
> been a lock acquired with a equal or higher CLN; the instruction
> will fault instead.   Likewise the UNLK instruction would fault
> of the lock was equal to the highest CLN stored in the hardware
> task data structure.
[...]

For some reason this makes me think of my pointer hash to mutex index 
thing I did a while back. It works quite well when the resulting array 
of indices is sorted and duplicates are removed. Locking order is solid 
and removing duplicates gets around using recursive locks.

[toc] | [prev] | [next] | [standalone]

#84303

On 5/27/2022 6:24 PM, Chris M. Thomasson wrote:
> On 5/27/2022 2:53 PM, Scott Lurndal wrote:
>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>>> On 5/27/2022 5:26 AM, Bonita Montero wrote:
>>>> On one side the situation Chis and others are afraid of doesn't
>>>> actually happen. On the other side _copying_ the contents of a
>>>> thread queue without consuming them isn't a requirement to a
>>>> thread queue. So I removed the copy-constructor and left the
>>>> move constructor which does everthing that's needed.
>>>
>>> Okay. However, it still makes me a bit nervous when I see code acquiring
>>> more than one lock at a time. I have had some horror shows trying to
>>> debug code written by others... One of the authors said, no need to
>>> worry because the locks are recursive (yuck) without a care in the world
>>> about lock ordering... Argh!
>>
>> Back in the early 1980s we were updating the architecture
>> of the Burroughs B3500/B4700/B4900 to support SMP and a larger
>> physical memory space.   One of the features added to support
>> SMP was hardware instructions providing capabilities similar to 
>> mutexes and posix
>> condition variables.
>>
>> To prevent deadlock, every lock has a 'canonical lock number' (CLN) that
>> ranges from 1 to 9999.  The hardware will not allow the LOCK
>> instruction to complete successfully if there has already
>> been a lock acquired with a equal or higher CLN; the instruction
>> will fault instead.   Likewise the UNLK instruction would fault
>> of the lock was equal to the highest CLN stored in the hardware
>> task data structure.
> [...]
> 
> For some reason this makes me think of my pointer hash to mutex index 
> thing I did a while back. It works quite well when the resulting array 
> of indices is sorted and duplicates are removed. Locking order is solid 
> and removing duplicates gets around using recursive locks.

Basically, once everything is sorted and duplicates are removed, the 
calling thread can take all of the locks without using any try_lock type 
of algorithm. 100% deadlock free.

[toc] | [prev] | [next] | [standalone]

#84313

"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>On 5/27/2022 2:53 PM, Scott Lurndal wrote:
>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>>> On 5/27/2022 5:26 AM, Bonita Montero wrote:
>>>> On one side the situation Chis and others are afraid of doesn't
>>>> actually happen. On the other side _copying_ the contents of a
>>>> thread queue without consuming them isn't a requirement to a
>>>> thread queue. So I removed the copy-constructor and left the
>>>> move constructor which does everthing that's needed.
>>>
>>> Okay. However, it still makes me a bit nervous when I see code acquiring
>>> more than one lock at a time. I have had some horror shows trying to
>>> debug code written by others... One of the authors said, no need to
>>> worry because the locks are recursive (yuck) without a care in the world
>>> about lock ordering... Argh!
>> 
>> Back in the early 1980s we were updating the architecture
>> of the Burroughs B3500/B4700/B4900 to support SMP and a larger
>> physical memory space.   One of the features added to support
>> SMP was hardware instructions providing capabilities similar to mutexes and posix
>> condition variables.
>> 
>> To prevent deadlock, every lock has a 'canonical lock number' (CLN) that
>> ranges from 1 to 9999.  The hardware will not allow the LOCK
>> instruction to complete successfully if there has already
>> been a lock acquired with a equal or higher CLN; the instruction
>> will fault instead.   Likewise the UNLK instruction would fault
>> of the lock was equal to the highest CLN stored in the hardware
>> task data structure.
>[...]
>
>For some reason this makes me think of my pointer hash to mutex index 
>thing I did a while back. It works quite well when the resulting array 
>of indices is sorted and duplicates are removed. Locking order is solid 
>and removing duplicates gets around using recursive locks.

There are a couple of minor downsides.

1) If you have a large number of small critical regions in a
   large code project (e.g. an OS), assigning CLN values to
   each lock gets tricky.

2) While the Medium Systems MCP didn't have a concept of shared
   libraries, if it did, it would be tricky to deconflict
   the CLN values between a threaded application and multiple shared
   thread-safe libraries if the libraries invoke external libraries
   or application callbacks with locks held.  Fortunately, that kind
   of lock nesting should be discouraged and is rare.

[toc] | [prev] | [next] | [standalone]

#84319

On 5/28/2022 7:56 AM, Scott Lurndal wrote:
> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>> On 5/27/2022 2:53 PM, Scott Lurndal wrote:
>>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>>>> On 5/27/2022 5:26 AM, Bonita Montero wrote:
>>>>> On one side the situation Chis and others are afraid of doesn't
>>>>> actually happen. On the other side _copying_ the contents of a
>>>>> thread queue without consuming them isn't a requirement to a
>>>>> thread queue. So I removed the copy-constructor and left the
>>>>> move constructor which does everthing that's needed.
>>>>
>>>> Okay. However, it still makes me a bit nervous when I see code acquiring
>>>> more than one lock at a time. I have had some horror shows trying to
>>>> debug code written by others... One of the authors said, no need to
>>>> worry because the locks are recursive (yuck) without a care in the world
>>>> about lock ordering... Argh!
>>>
>>> Back in the early 1980s we were updating the architecture
>>> of the Burroughs B3500/B4700/B4900 to support SMP and a larger
>>> physical memory space.   One of the features added to support
>>> SMP was hardware instructions providing capabilities similar to mutexes and posix
>>> condition variables.
>>>
>>> To prevent deadlock, every lock has a 'canonical lock number' (CLN) that
>>> ranges from 1 to 9999.  The hardware will not allow the LOCK
>>> instruction to complete successfully if there has already
>>> been a lock acquired with a equal or higher CLN; the instruction
>>> will fault instead.   Likewise the UNLK instruction would fault
>>> of the lock was equal to the highest CLN stored in the hardware
>>> task data structure.
>> [...]
>>
>> For some reason this makes me think of my pointer hash to mutex index
>> thing I did a while back. It works quite well when the resulting array
>> of indices is sorted and duplicates are removed. Locking order is solid
>> and removing duplicates gets around using recursive locks.
> 
> There are a couple of minor downsides.
> 
> 1) If you have a large number of small critical regions in a
>     large code project (e.g. an OS), assigning CLN values to
>     each lock gets tricky.

Agreed. The pointer hash in my multimutex has to be a good one. Any 
collisions would make two unrelated objects share the same index, which 
means they share the same mutex.



> 2) While the Medium Systems MCP didn't have a concept of shared
>     libraries, if it did, it would be tricky to deconflict
>     the CLN values between a threaded application and multiple shared
>     thread-safe libraries if the libraries invoke external libraries
>     or application callbacks with locks held.  Fortunately, that kind
>     of lock nesting should be discouraged and is rare.

I hope its rare... Yikes! I have had to debug some nightmare code in a 
server that received a request, locked a mutex on the request object, 
then called into user code. Oh shit. Gotta be very careful here. Try to 
avoid!

[toc] | [prev] | [next] | [standalone]

#84321

On 5/28/2022 4:49 PM, Chris M. Thomasson wrote:
> 
> Agreed. The pointer hash in my multimutex has to be a good one. Any 
> collisions would make two unrelated objects share the same index, which 
> means they share the same mutex.
> 

For something as small as a pointer, wouldn't a CRC-32 be sufficient?

[toc] | [prev] | [next] | [standalone]

#84382

On 5/28/2022 5:16 PM, red floyd wrote:
> On 5/28/2022 4:49 PM, Chris M. Thomasson wrote:
>>
>> Agreed. The pointer hash in my multimutex has to be a good one. Any 
>> collisions would make two unrelated objects share the same index, 
>> which means they share the same mutex.
>>
> 
> For something as small as a pointer, wouldn't a CRC-32 be sufficient?
> 

I think so. It's basically a trade off between the performance of the 
hash and the penalty of having a collision where more than one thread is 
locking the same mapped mutex to more than one unrelated object.

Using the try_lock method to avoid deadlock, ala std::scoped_lock, 
works, but it can get into some live lock like scenarios under load. It 
has to resort to some exotic backoff techniques...

[toc] | [prev] | [next] | [standalone]

#84304

Am 27.05.2022 um 23:18 schrieb Chris M. Thomasson:
> On 5/27/2022 5:26 AM, Bonita Montero wrote:
>> On one side the situation Chis and others are afraid of doesn't
>> actually happen. On the other side _copying_ the contents of a
>> thread queue without consuming them isn't a requirement to a
>> thread queue. So I removed the copy-constructor and left the
>> move constructor which does everthing that's needed.
> 
> Okay. However, it still makes me a bit nervous when I see code acquiring 
> more than one lock at a time. ...

As the situation in which a deadlock could occur doesn't make
any sense aside from the deadlock issue that doesn't matter.

[toc] | [prev] | [next] | [standalone]

#84269

Am 25.05.2022 um 22:58 schrieb Chris M. Thomasson:
> On 5/23/2022 7:07 PM, Bonita Montero wrote:
>> This is a thread-queue I've written:
> [...]
>> template<typename QueueType>
>>      requires thread_queue_concept<QueueType>
>> thread_queue<QueueType> 
>> &thread_queue<QueueType>::thread_queue::operator =( thread_queue const 
>> &other )
>> {
>>      std::lock_guard
>>          ourLock( m_mtx ),
>>          otherLock( other.m_mtx );
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> 
> This is a little scary. lock ordering issues come to mind. Fwiw, this is 
> why I created multimutex:

This absolutely isn't scary.
You just might not copy the queue from two sides at once.
But that's a extremely unlikely scenario anyway.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web