[RTEMS Project] #2273: One Step Towards Fine Grained Locking

[RTEMS trac]

#2273: One Step Towards Fine Grained Locking
-----------------------------+-----------------------------
 Reporter:  sebastian.huber  |      Owner:  sebastian.huber
     Type:  enhancement      |     Status:  new
 Priority:  normal           |  Milestone:  4.11.1
Component:  SMP              |    Version:  4.11
 Severity:  normal           |   Keywords:
-----------------------------+-----------------------------
 = Benefit =

 Improved average-case performance.  Uni-processor configurations will also
 benefit from some changes since calls to the thread dispatch function are
 reduced.

 = Problem Description =

 The Giant lock is a major performance bottleneck.  SMP aware applications
 tend to use fine grained locking at the application level.  So it is
 important that the semaphore obtain/release sequence for the uncontested
 case is as fast as possible, as an example see also
 [http://lists.rtems.org/pipermail/devel/2014-September/008275.html
 performance tests with new network stack].

 = Problem Solution =

 Remove the Giant lock.  This is a very complex task.  As a first step a
 redesign of the semaphore obtain/release sequence should be done.  The
 semaphore objects should use an object specific SMP lock for the non-
 blocking case and only resort to the Giant lock if a thread must
 block/unblock or in case of priority inheritance.

 The [wiki:Developer/SMP#LockingProtocolAnalysis analysis of the current
 locking protocol] shows that it is not compatible with fine grained
 locking since it uses the executing thread on several places.  On SMP
 systems more than one executing thread exists in contrast to uni-processor
 systems.  The semaphore manager provides the following semaphore object
 flavours in RTEMS

 * counting semaphores (no owner),
 * simple binary semaphores (no owner, no protocols),
 * binary semaphores,
 * binary semaphores with priority ceiling protocol,
 * binary semaphores with priority inheritance protocol, and
 * binary semaphores with multiprocessor resource sharing protocol (MrsP).

 For fine grained locking each flavour must be looked at individually.

 == Example: Binary Semaphore with Priority Inheritance Protocol ==

 A binary semaphore with priority inheritance protocol has at most one
 owner at a time.  In case an owner is present, then other threads (the
 rivals) must block and wait for ownership.  The highest priority rival
 will be the new owner once the current owner releases the semaphore.
 Rivals may use a watchdog to limit the time waiting for ownership.  The
 owner will inherit the priority of the highest priority rival.  In the
 next two images, coloured boxes represent the critical section of the
 corresponding protection mechanism.

 The following image depicts the structure of a binary semaphore of the
 current implementation with a Giant lock only.  The complete operation is
 protected by the Giant lock with thread dispatching disabled.  The
 interrupts are enabled in general.  Some critical sections use disabled
 interrupts.  So interrupts on a processor owning the Giant lock will delay
 other processors waiting for the Giant lock.

 Structure of a binary semaphore with priority inheritance protocol and
 Giant lock only:
 [[Image(ticket:giant.png)]]

 The following image depicts the structure of a binary semaphore with a
 semaphore specific SMP lock.  The state of the semaphore object is
 protected by this lock.  Other state changes like a thread priority change
 or a thread blocking operation is protected by the Giant lock.  The
 watchdog uses a dedicated lock here, see #2271.

 Structure of a binary semaphore with priority inheritance protocol and
 semaphore specific lock:
 [[Image(ticket:fine.png)]]

 In case no owner is present, then the semaphore obtain operation uses only
 the semaphore object specific SMP lock and there is no interference with
 the rest of the system.

--
Ticket URL: <http://devel.rtems.org/ticket/2273>
RTEMS Project <http://www.rtems.org/>
RTEMS Project