[Bug 1912] Add Scheduler Documentation

[bugzilla-daemon at rtems.org]

https://www.rtems.org/bugzilla/show_bug.cgi?id=1912

--- Comment #3 from Joel Sherrill <joel.sherrill at oarcorp.com> 2011-10-05 14:29:17 CDT ---
(In reply to comment #2)
> (In reply to comment #1)
> > Created attachment 1347 [details]
> > Merge of my and Petr's doc changes
> > 
> > I had outstanding changes to reorganize the scheduler chapter when Petr sent me
> > a patch for his changes.  His changes were to the configuring a system chapter
> > and the scheduler chapter. The scheduler chapter changes largely fit into new
> > subsections I had added to the outline.  
> > 
> > Please review and comment.  Once we are both OK, I will commit.
> The content seems fine. Coupled with the sptests I think it is enough to get
> someone going at any rate.
> 
> My notes follow, most of which are grammatical.
> 
> > Moreover, multiple background tasks are scheduled according their priority
> s/according their/according to their/

I am not seeing this.  Line number or hint

> > extention of EDF scheduler. The goal of this scheduler is to ensure temporal
> s/extention/extension/

OK.

> > provides with an extensive API. This scheduler may be explicitly selected
> s/provides with an//

provides an?

> > When a task is added to the ready chain, it is placed behind all other tasks of the same priority.  T
> Add line breaks please! :)

Missed this.  I use a gvim macro to do this and it looks like
I missed this one.

OK.

> > There are a few common methods of accomplishing the mechanics of this
> > algorithm.  These ways involve a list or chain of tasks in the ready state.
> > 
> > @itemize @bullet
> > @item The least efficient method is to randomly place tasks in the ready
> > chain forcing the scheduler to scan the entire chain to determine which
> > task receives the processor.
> > 
> > @item A more efficient method is to schedule the task by placing it
> > in the proper place on the ready chain based on the designated scheduling
> > criteria at the time it enters the ready state.  Thus, when the processor
> > is free, the first task on the ready chain is allocated the processor.
> > 
> > @item Another mechanism is to maintain a list of FIFOs per priority.
> > When a task is readied, it is placed on the rear of the FIFO for its
> > priority.  This method is often used with a bitmap to assist in locating
> > which FIFOs have ready tasks on them.
> > 
> > @end itemize
> This seems like bloat to me.

It is trying to give the main data structure alternatives for
a scheduler in one place so the scheduler specific descriptions
can be lighter.

> > on different cores, this algorithm favors preemptible threads which have
> s/preemtible/preempting/

I really meant that but the sentence must not be clear.  Try this.

When given a choice of replacing one of two threads at equal priority
on different cores, this algorithm favors replacing threads which are
preemptible and have executed the longest.

We try not to place a higher priority thread in a situation where
it is heir to a non-preemptible thread.

> 
> > and adherence to the model of real-time theory where tasks have priorities
> > equal to deadlines.
> Cut this, it is not very precise. RT tasks may be priority-based,
> deadline-based, or both, and need not have priorities equal to deadlines.

How about?

This is an alternative scheduler in RTEMS for single core applications. 
The primary EDF advantage is high total CPU utilization (theoretically
up to 100%). It assumes that tasks have priorities equal to deadlines.


> > This implementation of EDF allows to schedule two different types of task
> s/allows to schedule/schedules/

OK.

> > task which priority in equal to priority assigned upon initialization in the
> s/which priority in equal to priority/with priority equal to that/

OK.

> > to claim deadline until which specific set of instructions has to be
> > executed. This is carried out using the Rate Monotonic manager which
> > is responsible for handling periodic execution. In RTEMS periods are
> > equal to deadlines, thus if a task announces a period, it has to be
> > finished until the end of this period. The call of
> Rewrite to:
> to claim a deadline. The Rate Monotonic manager is responsible for managing
> periodic and deadline-driven tasks. In RTEMS periods are equal to deadlines.

OK.

> > The CBS is a budget aware extention of EDF scheduler. The main goal of this
> s/extention/extension/

Think this is gone.

> > on task per server). The server is characterized by period (deadline) and
> s/on/one/

Done

> > computation time (budget). The ratio budget/period yields bandwidth, 
> s/bandwidth,/bandwidth, which is the/
> 
> > ensuring that deadline miss because of another task can not occur.
> s/can not/cannot/

OK.

> > In case a task breaks one of the rules, it's priority is pulled to background
> s/it's/its/

OK.

> > until the end of period and then restored again. The rules are:
> s/of period/of its period/

OK.

> > @item Task can not exceed it's registered budget, @item Task can not be
> s/can not/cannot/g
> s/it's/its/

OK.

> > The CBS provides with an extensive API. Unlike EDF, the
> s/with//

Think this is OK.

> > RTEMS provides four mechanisms which allow the user to impact the task
> > scheduling decision process:
> s/impact the task/change task/
> s/decision process:/decisions:/

change task -> alter task
OK on second.

-- 
Configure bugmail: https://www.rtems.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching all bug changes.