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

Groups > comp.programming.threads > #6317 > unrolled thread

More precision about my new inventions of scalable algorithms..

Back to article view | Back to comp.programming.threads

Contents

  More precision about my new inventions of scalable algorithms.. Amine Moulay Ramdane <aminer68@gmail.com> - 2021-02-18 11:07 -0800
    Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-19 23:27 +0100
      Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 14:48 -0800
        Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-20 00:01 +0100
          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:17 -0800
            Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-20 08:50 +0100
              Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-20 12:46 -0800
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-20 12:52 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-21 17:16 +0100
                  Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-21 13:15 -0500
                    Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-21 19:58 +0100
                      Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-21 15:58 -0500
                        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 14:35 -0800
                          Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:54 +0100
                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:00 -0800
                              Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 07:40 +0100
                              Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 09:20 +0100
                                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-22 14:54 -0800
                                  Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-23 08:38 +0100
                                    Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 00:25 -0800
                                      Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-23 20:17 +0100
                                        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 11:29 -0800
                                          Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-24 18:20 +0100
                                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 01:49 -0800
                                        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 14:13 -0800
                                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 14:14 -0800
                                    Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-23 16:51 -0500
                                      Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-24 18:22 +0100
                                        Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-24 13:28 -0500
                                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 17:16 -0800
                                          Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 07:08 +0100
                                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 23:39 -0800
                                              Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 09:49 +0100
                                                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 01:05 -0800
                                                  Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 11:43 +0100
                                                    Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 03:09 -0800
                                                      Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 03:10 -0800
                                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 23:43 -0800
                        Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:52 +0100
                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:10 -0800
                      Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 21:47 -0800
                        Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:51 +0100
                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:01 -0800
          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:32 -0800
            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:37 -0800
        Re: More precision about my new inventions of scalable algorithms.. Amine Moulay Ramdane <aminer68@gmail.com> - 2021-02-19 15:14 -0800

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#6348

>>> My version of "fairness", or being "starvation free", is when readers 
>>> cannot starve out writers, and vise versa. Oh well. :^)

>> That's impossible to implement.
>> Readers or writers can hold the mutex as long as they want.

> We just have radically different versions of what it means to be 
> starvation free. :^)

The fairness of a lock doesn't depend on the implementation of the
lock but how it is used.

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

#6349

On 2/23/2021 11:17 AM, Bonita Montero wrote:
>>>> My version of "fairness", or being "starvation free", is when 
>>>> readers cannot starve out writers, and vise versa. Oh well. :^)
> 
>>> That's impossible to implement.
>>> Readers or writers can hold the mutex as long as they want.
> 
>> We just have radically different versions of what it means to be 
>> starvation free. :^)
> 
> The fairness of a lock doesn't depend on the implementation of the
> lock but how it is used.

It does depend on the implementation if frequent reads can starve out 
writers.

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

#6353

> It does depend on the implementation if frequent reads can starve out 
> writers.

But if this happens is a matter of the lock-behaviour.

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

#6362

On 2/24/2021 9:20 AM, Bonita Montero wrote:
>> It does depend on the implementation if frequent reads can starve out 
>> writers.
> 
> But if this happens is a matter of the lock-behaviour.

The way the user actually uses a rwmutex should be read heavy, writes, 
not so frequent. However, frequent sustained reads should not have the 
ability to starve out writers; lots of rwmutex impls allow just that. 
Some even have so-called reader/writer priorities. Bakery algorithms 
cannot suffer from these conditions... They just go in order.

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

#6351

On 2/23/2021 11:17 AM, Bonita Montero wrote:
>>>> My version of "fairness", or being "starvation free", is when 
>>>> readers cannot starve out writers, and vise versa. Oh well. :^)
> 
>>> That's impossible to implement.
>>> Readers or writers can hold the mutex as long as they want.
> 
>> We just have radically different versions of what it means to be 
>> starvation free. :^)
> 
> The fairness of a lock doesn't depend on the implementation of the
> lock but how it is used.

Are you familiar with bakery algorihtms?

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

#6352

On 2/23/2021 2:13 PM, Chris M. Thomasson wrote:
> On 2/23/2021 11:17 AM, Bonita Montero wrote:
>>>>> My version of "fairness", or being "starvation free", is when 
>>>>> readers cannot starve out writers, and vise versa. Oh well. :^)
>>
>>>> That's impossible to implement.
>>>> Readers or writers can hold the mutex as long as they want.
>>
>>> We just have radically different versions of what it means to be 
>>> starvation free. :^)
>>
>> The fairness of a lock doesn't depend on the implementation of the
>> lock but how it is used.
> 
> Are you familiar with bakery algorithms?

bakery algorithms?

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

#6350

On 2/23/21 2:38 AM, Bonita Montero wrote:
>> My version of "fairness", or being "starvation free", is when readers
>> cannot starve out writers, and vise versa. Oh well. :^)
> 
> That's impossible to implement.
> Readers or writers can hold the mutex as long as they want.

And the standard definition of a 'fair locking' system is one that is
fair when the follow listed rules, like maximum hold time of a lock.

The only way to handle unruly clients is who hold their locks too long
is to have OS support to kill those clients and have it unlock the locks
it held on to. (It could not kill but just deny further access depending
on the resource).

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

#6354

> The only way to handle unruly clients is who hold their locks too long
> is to have OS support to kill those clients and have it unlock the locks
> it held on to. (It could not kill but just deny further access depending
> on the resource).

We're talking about locks which protect shared datastructures. In this
case it would be stupid to kill a process or thread holding such a lock.

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

#6355

On 2/24/21 12:22 PM, Bonita Montero wrote:
>> The only way to handle unruly clients is who hold their locks too long
>> is to have OS support to kill those clients and have it unlock the locks
>> it held on to. (It could not kill but just deny further access depending
>> on the resource).
> 
> We're talking about locks which protect shared datastructures. In this
> case it would be stupid to kill a process or thread holding such a lock.
> 

A lock that works with the OS to so the OS knows what locks the process
holds can kill a 'bad' process and force the release of the lock.

The only way to handle 'bad' processes, is for there to be some
mechanism to deny that process access to the resource that it has taken
the lock on, so it can be given to someone else. That capability is
typically reserved to the OS.

Yes, if you abort a process in the middle of its operation, you may need
to do some 'cleanup' on the resource, but if the process isn't releasing
the resource in the required time, can you really trust that it is doing
its job right?

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

#6356

On 2/24/2021 10:28 AM, Richard Damon wrote:
> On 2/24/21 12:22 PM, Bonita Montero wrote:
>>> The only way to handle unruly clients is who hold their locks too long
>>> is to have OS support to kill those clients and have it unlock the locks
>>> it held on to. (It could not kill but just deny further access depending
>>> on the resource).
>>
>> We're talking about locks which protect shared datastructures. In this
>> case it would be stupid to kill a process or thread holding such a lock.
>>
> 
> A lock that works with the OS to so the OS knows what locks the process
> holds can kill a 'bad' process and force the release of the lock.
> 
> The only way to handle 'bad' processes, is for there to be some
> mechanism to deny that process access to the resource that it has taken
> the lock on, so it can be given to someone else. That capability is
> typically reserved to the OS.
> 
> Yes, if you abort a process in the middle of its operation, you may need
> to do some 'cleanup' on the resource, but if the process isn't releasing
> the resource in the required time, can you really trust that it is doing
> its job right?
> 


Are you familiar with robust mutexes? They are designed to allow one to 
repair the shared data if a processes dies while holding the lock.

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

#6357

> A lock that works with the OS to so the OS knows what locks the process
> holds can kill a 'bad' process and force the release of the lock.

That's impossible because that what the lock guards is in inconsistent
state at this time.

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

#6358

On 2/24/2021 10:08 PM, Bonita Montero wrote:
>> A lock that works with the OS to so the OS knows what locks the process
>> holds can kill a 'bad' process and force the release of the lock.
> 
> That's impossible because that what the lock guards is in inconsistent
> state at this time.

Think of a "master" process, than can kill a process while its holding a 
process-wide mutex. This can be handled and corrected, the state can be 
repaired into a consistent state. Its tricky, yet can be done. Wrt 
Windows think of the WAIT_ABANDONDED state. POSIX has it with EOWNERDEAD.

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

#6360

> Think of a "master" process, than can kill a process while its holding a 
> process-wide mutex. This can be handled and corrected, the state can be 
> repaired into a consistent state. Its tricky, yet can be done. Wrt 
> Windows think of the WAIT_ABANDONDED state. POSIX has it with EOWNERDEAD.

If you have shared memory modified while holding the lock there's
nothing to fix.

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

#6361

On 2/25/2021 12:49 AM, Bonita Montero wrote:
>> Think of a "master" process, than can kill a process while its holding 
>> a process-wide mutex. This can be handled and corrected, the state can 
>> be repaired into a consistent state. Its tricky, yet can be done. Wrt 
>> Windows think of the WAIT_ABANDONDED state. POSIX has it with EOWNERDEAD.
> 
> If you have shared memory modified while holding the lock there's
> nothing to fix.

have you ever had to encounter and deal with EOWNERDEAD, or 
WAIT_ABANDONDED ?

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

#6363

>> If you have shared memory modified while holding the lock there's
>> nothing to fix.

> have you ever had to encounter and deal with EOWNERDEAD, or 
> WAIT_ABANDONDED ?

Boy, you're stupid. If you're modifying memory while holding a lock
and the lock is deleted meanwhile, WAIT_ABANDONNED or whatever doesn't
help.

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

#6364

On 2/25/2021 2:43 AM, Bonita Montero wrote:
>>> If you have shared memory modified while holding the lock there's
>>> nothing to fix.
> 
>> have you ever had to encounter and deal with EOWNERDEAD, or 
>> WAIT_ABANDONDED ?
> 
> Boy, you're stupid. If you're modifying memory while holding a lock
> and the lock is deleted meanwhile, WAIT_ABANDONNED or whatever doesn't
> help.

You have never had to clean up after a process dies while holding a mutex?

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

#6365

On 2/25/2021 3:09 AM, Chris M. Thomasson wrote:
> On 2/25/2021 2:43 AM, Bonita Montero wrote:
>>>> If you have shared memory modified while holding the lock there's
>>>> nothing to fix.
>>
>>> have you ever had to encounter and deal with EOWNERDEAD, or 
>>> WAIT_ABANDONDED ?
>>
>> Boy, you're stupid. If you're modifying memory while holding a lock
>> and the lock is deleted meanwhile, WAIT_ABANDONNED or whatever doesn't
>> help.

I am not referring to deleting a mutex, I am talking about a process 
crashing in the middle of a critical section.

> 
> You have never had to clean up after a process dies while holding a mutex?

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

#6359

On 2/24/2021 10:08 PM, Bonita Montero wrote:
>> A lock that works with the OS to so the OS knows what locks the process
>> holds can kill a 'bad' process and force the release of the lock.
> 
> That's impossible because that what the lock guards is in inconsistent
> state at this time.

Wrt WAIT_ABANDONED, read the docs:

https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitforsingleobject
_____________
WAIT_ABANDONED:

The specified object is a mutex object that was not released by the 
thread that owned the mutex object before the owning thread terminated. 
Ownership of the mutex object is granted to the calling thread and the 
mutex state is set to nonsignaled.
If the mutex was protecting persistent state information, you should 
check it for consistency.
_____________

POSIX has, EOWNERDEAD:

https://man7.org/linux/man-pages/man3/pthread_mutex_consistent.3.html

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

#6338

> The key point isn't what resource was being managed, but how do we
> really define 'fair'. ...

But with an example that doesn't fit with the discussion.
Chris does know what I mean, you don't.

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

#6342

On 2/21/2021 9:52 PM, Bonita Montero wrote:
>> The key point isn't what resource was being managed, but how do we
>> really define 'fair'. ...
> 
> But with an example that doesn't fit with the discussion.
> Chris does know what I mean, you don't.

I do know what you mean, its just not the classic way of thinking about 
starvation. You are 100% correct that a batch of readers, or a single 
writer can hold the lock for hours. It can happen, well, its not 
advised, but it still can occur.

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.programming.threads

csiph-web