Re: [ECOS] Scheduler lock in Doug Lea's malloc implementation - be real careful

Re: [ECOS] Scheduler lock in Doug Lea's malloc implementation - be real careful

[bob.koninckx]

>>
>>    Bob> Can someone explain me why the default memory allocator locks
>>    Bob> the scheduler ? I would expect it to be legitimate for a low
>>    Bob> priority thread with no real time constraints to do dynamic
>>    Bob> memory allocation without influencing the real-time behaviour
>>    Bob> of threads with real-time constraints, as long as they have a
>>    Bob> higher priority.
>>
>> I was not involved in the initial implementation of the memory
>> allocators, so this is not gospel. I do remember that the uITRON
>> compatibility layer imposed various requirements.
>>
>> I believe the theory is that the memory allocators should be very
>> fast. If you use an alternative locking mechanism like a mutex, both
>> the lock and unlock functions will themselves lock and unlock the
>> scheduler. When you have a memory allocator that takes a comparable
>> amount of time to a mutex operation, you are better off locking the
>> scheduler around the memory allocation rather than going through mutex
>> lock and unlock calls.
>>
>> If you are using a fixed block memory pool as per mfiximpl.hxx then
>> that theory may well be correct. If you are using some other allocator
>> such as dlmalloc then I suspect the theory is wrong and for such
>> allocators the code should use a mutex instead, but I have not done
>> any measurements. There are going to be complications, e.g.
>> average vs. maximum times.
>>
>> Bart
>>
>> --
>> Bart Veer                       eCos Configuration Architect
>> http://www.ecoscentric.com/     The eCos and RedBoot experts
>>
>> --
>
>The data that describes what portion(s) of the pool is common to all threads
>accessing the pool.
>Each successful allocate/deallocate request results at least 1 instance of a
>read of a portion of that common data,
>a varying quantifty of instructions to evaluate, and finally updates to the
>affected data value(s).
>
>The above "read/process/write" sequence is commonly referred to as a
>"critical instruction sequence" that requires
>a guaratee that absolutely precludes any potential of a 2nd operation from
>occurring while a prior one is in progress.
>To not do so allows for sporatic, unpredictable timing errors that are
>extremely difficult to recognize, let alone identify and correct.

Obviously, you need protection there. What I do not understand is why it is implemented using scheduler lock/unlock instead of using mutexes or semaphores. Also the proposed use of memory pools is not really clear to me (and it certainly raises portability issues when moving from one OS to another). As a general rule, I _always_ consider dynamic memory allocation an undeterministic process, so I _never_ use it in time critical code. It nevertheless seems odd to me that you shouldn't be allowed to use dynamic memory allocation in low priority threads with no real-time requirements at all, just because of timing requirements in higher priority threads. I see no reason why scanning the heap could not be interrupted (put on hold for a while) to give a real-time thread time to finish its job. This is not possible if you protect things with a big kernel lock, but would be if searching for memory would be protected by a mutex.

Any comments ? Am I making a fundamental reasoning error here ? If not, I am going to try to change the implementation and see if it solves our problem and propose a patch.

Thanks,

Bob




--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] Scheduler lock in Doug Lea's malloc implementation - be real careful

[Bart Veer]

>>>>> "Bob" == bob koninckx <bob.koninckx@o-3s.com> writes:

    Bob> Obviously, you need protection there. What I do not
    Bob> understand is why it is implemented using scheduler
    Bob> lock/unlock instead of using mutexes or semaphores. Also the
    Bob> proposed use of memory pools is not really clear to me (and
    Bob> it certainly raises portability issues when moving from one
    Bob> OS to another). As a general rule, I _always_ consider
    Bob> dynamic memory allocation an undeterministic process, so I
    Bob> _never_ use it in time critical code. It nevertheless seems
    Bob> odd to me that you shouldn't be allowed to use dynamic memory
    Bob> allocation in low priority threads with no real-time
    Bob> requirements at all, just because of timing requirements in
    Bob> higher priority threads. I see no reason why scanning the
    Bob> heap could not be interrupted (put on hold for a while) to
    Bob> give a real-time thread time to finish its job. This is not
    Bob> possible if you protect things with a big kernel lock, but
    Bob> would be if searching for memory would be protected by a
    Bob> mutex.

    Bob> Any comments ? Am I making a fundamental reasoning error here
    Bob> ? If not, I am going to try to change the implementation
    Bob> and see if it solves our problem and propose a patch.

You seem to have missed my point. Let me try again.

The current code behaves as follows:

    lock scheduler
    alloc() or free() or realloc()
    unlock scheduler

Let T_alloc be the worst case time spent in the alloc(), free() or
realloc() routines, noting that the realloc() implementations in the
heap will fail if the chunk cannot be resized and the alternative
alloc()/memcpy()/free() implementation happens elsewhere. T_alloc will
depend on factors like heap fragmentation so ideally would be measured
in the context of a real application, but some of testcases in the
memalloc package probably come close enough.

What you are proposing is:

    lock_mutex
      lock scheduler
      mutex lock code
      unlock scheduler
    alloc() or free() or realloc()
    unlock_mutex
      lock scheduler
      mutex unlock code
      unlock scheduler

Let T_lock be the time spent in the mutex lock code and T_unlock the
time spent in the mutex unlock code. These should probably be measured
for the case where the mutex is contested, priority inversion
protection triggers, and there are threads blocked on the mutex, not
for the simple uncontested case. The other important number is T_max -
the maximum time the system will spend with the scheduler locked
because of other code. This is rather tricky to measure and will
depend in part on the application and its I/O behaviour.

If T_alloc is comparable to max(T_lock, T_unlock) then there is
nothing to be gained by using a mutex rather than the scheduler lock.
You are adding cpu cycle overhead to the memory allocation routines
for no improvement in real-time performance.

If T_alloc < T_max, then switching from a scheduler lock to a mutex
lock/unlock will not change the maximum dispatch latency and will not
affect the worst case real-time characteristics. It may still affect
the average dispatch latency.

If T_alloc == T_max, i.e. the worst case dispatch latency is caused by
the memory allocation code, then we have a problem that needs
addressing.


I believe the author of the original code assumed that T_alloc was
comparable to max(T_lock, T_unlock), or at least that (T_alloc < T_max).
Hence using a scheduler lock saved some cpu cycles for every memory
allocation operation without affecting real-time behaviour. I suspect
that assumption is false but do not have any numbers to prove it.

There are several memory allocators, but the ones we are interested in
are the fixed block, variable block and dlmalloc ones. If for all
three we have T_alloc >> MAX(T_lock, T_unlock) then we should probably
switch to using a mutex by default on the grounds of improving average
dispatch latency. If for all three we have T_alloc == T_max then we
must switch to using a mutex by default to reduce the maximum dispatch
latency. Unfortunately this requires measuring T_max.

If on the other hand we find that for say the fixed memory allocator
T_alloc is much the same as MAX(T_lock, T_unlock) but dlmalloc behaves
very differently then we would need to introduce new templates, with
the old ones still using the scheduler lock and the new ones using a
mutex. 


I do not have time right now to experiment and get some real numbers.
However I would very much like to see such numbers before or
accompanying any patch that changes the behaviour. Also it would be
important to run not just the memory allocation package's own tests
but also the uITRON ones.

Bart

-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

[ECOS] Re: Scheduler lock in Doug Lea's malloc implementation - be real careful

[Sergei Organov]

bob.koninckx@o-3s.com writes:
[...]

> Any comments ? Am I making a fundamental reasoning error here ? If
> not, I am going to try to change the implementation and see if it
> solves our problem and propose a patch.

I believe mutex is better choice for protection of the allocator. The
mutex code indeed disables scheduler, but for very short (and
deterministic) periods of time compared to the time required for
malloc(), so using mutex instead of scheduler lock should solve the
problem.

-- 
Sergei.


-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss