Re: Rate Monotonic Scheduling (RMS) vs. OS Scheduling

ran.levy1@xxxxxxxxx wrote:

Background:
==========
The company I work for develop Carrier Ethernet Switch (both HW and
SW). I am facing a major decision I have to take about using RMS (or
anothe in house scheduler algorithm) or using the OS scheduling.

Requirements (the most relevant functional and non-functional
requirements):
=========================================================
1. Support various networking protocols (IGMP, STP, PBB-TE, ....)
2. High availability - achieved also by redundant HW.
3. Predictability - I would like to have performance predictability
prior to actual development.
4. Performance - achieving high performance and low system resources
usage.
5. Usability - allowing distributed development around the world.
6. Integration with 3rd party - allowing "buy" and easy integration
with them.
7. Portability - loose coupling with OS/HW.

Solution Alternatives:
================
The layered based with asynchronous messages between them. The
"dynamic control" layer is responsible for handling protocols' control
packets.

Alternative 1 - Rate Monotonic Scheduler (or other in-house
scheduler):
In the RMS concept there is a single task that schedules all
protocols. Each protocol must not exceed limited time quota and must
not perform any CPU blocking operation. Blocking operations should be
performed by services tasks that serve all protocols.

Hmmmm.... except that is not what Rate Monotonic Scheduling is.
RMS is a design technique that assigns static priorities to
known amounts of work and shows you whether all tasks meet their
deadlines. It requires you to you know the task frequency and
duration and deadlines in advance. If a deadline is missed,
the system has, by definition, failed.

If the tasks you are describing are not deadline based,
then it is not really a real time scheduling issue.

Alternative 2 - OS Scheduling
In this approach every protocol has task (or more than one - for
example to support Pipes & Filtering). The scheduling between the
protocols is done by the OS (with or without time slicing).

I would be happy to have comments/observations or some other
alternatives.

Thanks,
Ran

Ok, I can mutter some thoughts out loud if you like...

You seem to be mixing a number of issues together.
One is software architecture: a single task processing a work queue
into which to-do items are posted .vs. multiple tasks
(or a combination of these two).
The other is the manner in which multiple tasks are scheduled
and the priorities you assign to each task.

How are you going to ensure that you know the amount of work
in advance? It seems to me there are two alternatives:

1) Assume that each network packet takes a worst case path
through the protocol stack. The total amount of load
is proportional to the packet arrival rate and therefore
the total bandwidth of the network connections.

If you are over budget, install slower network cards.

Of course this only applies after packets have been received.
The system cannot make any assurance that a packet will arrive.
If the network connection is shared (ethernet) this delay
is probabilistic (well... more probabilistic).

2) Accept that there is no guaranteed upper time limit.
Pre-allocate a fixed amount of time for each of the various
protocol tasks.

And do what when the time budget is exhausted?

Assuming packets arrive at the highest rate possible for
the bandwidth, and assuming the bandwidth is high enough,
then your work queues are going to get longer and longer.
How are you going to deal with this?

You could shed load at critical points in the protocol stack,
equivalent to simply truncating the input queue.
In doing so you create a predicable worst case work load for
the remainder of the stack, and ideally a single control point
that throttles the externally generated load.

In effect this ensures you meet the task deadlines by tossing away
work. I'm not sure that qualifies as a strict real time design.

Eric

.

Relevant Pages

  • Re: Energy constraints was Re: Androids & Strong AI in the Future
    ... acts like a PC running windows with a wifi internet connection. ... handle, in good modular fashion, all packet level assembly protocols, ... "radio sense" than you or I have a radio sense when we jack in at some ... radio data, it has a radio sense, if you send wifi packets, it has "wifi ...
    (comp.ai.philosophy)
  • Re: XP SP2 seems to cause unwanted traffic to printer
    ... There were 1220 packets between the printer and this PC in 60sec. ... It just seems odd that this wasnt a problem till SP2 was loaded. ... even when it's supposed to be disabled it really isn't, especially at startup, and to get around some of its limitations we've had to write ..reg files to modify the firewall behaviour in order to pass some Netware protocols fluidly from SP2 boxes by specifying ports, packet types and service names, and even then it's sometimes hit and miss. ... What I suspect is the activity you're seeing could be the result of timeouts and retries of the printer protocols trying to communicate with between the printer and PCs through the kludgey XP firewall. ...
    (microsoft.public.windowsxp.general)
  • Re: Rate Monotonic Scheduling (RMS) vs. OS Scheduling
    ... The company I work for develop Carrier Ethernet Switch (both HW and ... anothe in house scheduler algorithm) or using the OS scheduling. ... "dynamic control" layer is responsible for handling protocols' control ... not perform any CPU blocking operation. ...
    (comp.arch)
  • RE: [fw-wiz] tests about latency
    ... > to other protocols? ... ICMP handling is generally a special case for most ... most devices with minor changes to the packets you're generating. ... different sized buffer, will it affect overall performance for the other ...
    (Firewall-Wizards)
  • Re: Cause of Dropped HS ISO Packets?
    ... I am going to try tomorrow to switch back to ASAP for all scheduling and see if that improves anything. ... because of your restriction to 8packets and not adventuring to ... I have done this in the past and I was actually pretty impressed with how consistently the completion routines were called. ... One thing that did occur to me regarding URB scheduling and so-forth is that scheduling a URB with the HC driver is not the same as actually having it scheduled with the HC. ...
    (microsoft.public.development.device.drivers)