Changeset aaff696 in rtems-docs


Ignore:
Timestamp:
Jan 31, 2017, 10:15:56 AM (3 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
5, master
Children:
8add179
Parents:
938c49e
git-author:
Sebastian Huber <sebastian.huber@…> (01/31/17 10:15:56)
git-committer:
Sebastian Huber <sebastian.huber@…> (02/01/17 06:58:19)
Message:

c-user: Add key concept thread queues

Update #2556.

Location:
c-user
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • c-user/glossary.rst

    r938c49e raaff696  
    640640    The system on which the application will ultimately execute.
    641641
     642.. _task:
     643
    642644:dfn:`task`
    643645    A logically complete thread of execution.  It consists normally of a set of
    644     registers and a stack.  The terms :dfn:`task` and :dfn:`thread` are synonym
    645     in RTEMS.  The scheduler assigns processors to a subset of the ready tasks.
     646    registers and a stack.  The scheduler assigns processors to a subset of the
     647    ready tasks.  The terms :dfn:`task` and :dfn:`thread` are synonym in RTEMS.
     648    The term :dfn:`task` is used throughout the Classic API, however,
     649    internally in the operating system implementation and the POSIX API the
     650    term :dfn:`thread` is used.
    646651
    647652:dfn:`Task Control Block`
     
    662667:dfn:`TCB`
    663668    An acronym for Task Control Block.
     669
     670:dfn:`thread`
     671    See :ref:`task <task>`.
    664672
    665673:dfn:`thread dispatch`
  • c-user/key_concepts.rst

    r938c49e raaff696  
    239239synchronization mechanism.  The signal manager supports only asynchronous
    240240communication and is typically used for exception handling.
     241
     242Thread Queues
     243=============
     244.. index:: thread queues
     245
     246In case more than one :ref:`thread <task>` may wait on a synchronization
     247object, e.g. a semaphore or a message queue, then the waiting threads are added
     248to a data structure called the thread queue.  Thread queues are named task wait
     249queues in the Classic API.  There are two thread queuing disciplines available
     250which define the order of the threads on a particular thread queue.  Threads
     251can wait in FIFO or priority order.
     252
     253In uni-processor configurations, the priority queuing discipline just orders
     254the threads according to their current priority and in FIFO order in case of
     255equal priorities.  However, in SMP configurations, the situation is a bit more
     256difficult due to the support for clustered scheduling.  It makes no sense to
     257compare the priority values of two different scheduler instances.  Thus, it is
     258impossible to simply use one plain priority queue for threads of different
     259clusters.  Two levels of queues can be used as one way to solve the problem.
     260The top-level queue provides FIFO ordering and contains priority queues.  Each
     261priority queue is associated with a scheduler instance and contains only
     262threads of this scheduler instance.  Threads are enqueued in the priority
     263queues corresponding to their scheduler instances.  To dequeue a thread, the
     264highest priority thread of the first priority queue is selected.  Once this is
     265done, the first priority queue is appended to the top-level FIFO queue.  This
     266guarantees fairness with respect to the scheduler instances.
     267
     268Such a two-level queue needs a considerable amount of memory if fast enqueue
     269and dequeue operations are desired.  Providing this storage per thread queue
     270would waste a lot of memory in typical applications.  Instead, each thread has
     271a queue attached which resides in a dedicated memory space independent of other
     272memory used for the thread (this approach was borrowed from FreeBSD).  In case
     273a thread needs to block, there are two options
     274
     275* the object already has a queue, then the thread enqueues itself to this
     276  already present queue and the queue of the thread is added to a list of free
     277  queues for this object, or
     278
     279* otherwise, the queue of the thread is given to the object and the thread
     280  enqueues itself to this queue.
     281
     282In case the thread is dequeued, there are two options
     283
     284* the thread is the last thread in the queue, then it removes this queue
     285  from the object and reclaims it for its own purpose, or
     286
     287* otherwise, the thread removes one queue from the free list of the object
     288  and reclaims it for its own purpose.
     289
     290Since there are usually more objects than threads, this actually reduces the
     291memory demands.  In addition the objects only contain a pointer to the queue
     292structure.  This helps to hide implementation details.  Inter-cluster priority
     293queues are available since RTEMS 4.12.
     294
     295A doubly-linked list (chain) is used to implement the FIFO queues yielding a
     296:math:`O(1)` worst-case time complexity for enqueue and dequeue operations.
     297
     298A red-black tree is used to implement the priority queues yielding a
     299:math:`O(log(n))` worst-case time complexity for enqueue and dequeue operations
     300with :math:`n` being the count of threads already on the queue.
    241301
    242302Time
Note: See TracChangeset for help on using the changeset viewer.