Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 53
Текст из файла (страница 53)
Event-triggered messages. The messages are produced sporadically whenever asignificant event occurs at the sender. There is no minimum time betweenmessages established. No temporal guarantees about the delay between sendinga message and receiving a message can be given. In case the sender producesmore messages than the BMTS can handle, either back-pressure is exercised onthe sender or messages are lost.2. Rate-constrained messages. The messages are produced sporadically, howeverthe sender guarantees not to exceed a maximum message rate. Within thegiven fault-hypothesis, the BMTS guarantees not to exceed a maximum worstcase transport latency.
The jitter depends on the load of the network and isbounded by the worst-case transport latency minus the minimum transportlatency.3. Time-triggered messages. Sender and receiver agree a priori on the exactinstants when messages are sent and received.
Within the given fault-hypothesis, the BMTS guarantees that the messages will be delivered at the specified instants with a jitter that is determined by the precision of the globaltime.There are many different means how to implement the BMTS on wire-bound orwireless channels by low-level protocols. A given BMTS is characterized by thetransport latency, the jitter, and the reliability of transporting a single message unidirectionally form a sender to the set of destined receivers.The BMTS provides the basis for building high-level protocols, such as arequest-reply protocol, a file-transport protocol, or any other rule-based exchangeof message sequences that is captured in a higher-level concept.Example: A simple high-level protocol is the mentioned request-reply protocol thatconsists of two BMTS messages, one from the sender to the receiver and a second related(but from the point of view of the BMTS independent) BMTS message from the receiverback to the sender.1747.2.27 Real-Time CommunicationPhysical Performance LimitationAny physical communication channel is characterized by its bandwidth and itspropagation delay.
The bandwidth denotes the number of bits that can traverse achannel in unit time. The length of the channel and the transmission speed of thewave (electromagnetic, optical) within the channel determine the propagation delaywhich is the duration it takes for a single bit to travel from one end of the channelto the other end. Because the transmission speed of a wave in a cable is approximately2/3 of the transmission speed of light in vacuum (about 300,000 km/s), it takes asignal about 5 ms to travel across a cable of 1 km length.
The term bit length of achannel is used to denote the number of bits that can traverse the channel within onepropagation delay.Example: If the channel bandwidth is 100 Mbit/s and the channel is 200 m long, the bitlength of the channel is 100 bits, since the propagation delay of this channel is 1 ms.In a bus system, the data efficiency of any media access protocol on a shared channelis limited by the need to maintain a minimum time interval of one propagation delaybetween two successive messages. Assume the bit length of a channel to be bl bitsand the message length to be m bits. Then an upper bound for the data efficiency ofany media access protocol in a bus system is given by:data efficiency < m=ðm þ blÞExample: Consider a 1 km bus with a bandwidth equal to 100 Mbits/s.
The message lengththat is transmitted over this channel is 100 bits. It follows that the bit length of the channel is500 bits, and the limit to the best achievable data efficiency is 100/(100 + 500) ¼ 16.6%.If the message length is less than the bit length of the channel, then the bestchannel utilization that can be realized with any media access protocol is less than50%. This physical limit has implications for the design of protocols. If a channelis long and supports a high bandwidth, it is wasteful to send short messages.Table 7.1 contains the bit length of a channel as a function of its bandwidth and itslength.Example: From Table 7.1, we can deduce that if we want to achieve a channel utilizationbetter than 50% for a 100 m long channel with 1 Gbit/s bandwidth, then the minimummessage length must be larger than 500 bits.
In such a scenario, it is waste of bandwidth tosend BMTS messages that are only a few bits long.7.2.3Flow ControlFlow control is concerned with the control of the speed of information flow betweena sender and a receiver (or the communication system, in this case the term congestion control is sometimes used) in such a manner that the communication system andthe receiver can keep up with the sender.
In any communication scenario, it is the7.2 Design Issues175Table 7.1 Bit-length of a channel as a function of channel length and bandwidthBandwidth of the channel in bits per second and bit length in secondsChannel lengthand propagation10 kbit 100 kbits 1 Mbit 10 Mbit 100 Mbit 1 Gbit 10 Gbitdelay in seconds100 ms10 m1m100 ns10 ns1 ns100 ps1 cm – 50 ps<1<1<1<1<1<1<110 cm – 500 ps<1<1<1<1<1<151 m – 5 ns<1<1<1<1<155010 m – 50 ns<1<1<1<1550500100 m – 500 ns<1<1<15505005k1 km – 5 ms<1<15505005k50 k10 km – 50 ms<15505005k50 k500 kreceiver or the limited capacity of the communication system rather than the senderthat determines the maximum speed of communication. We distinguish between thefollowing types of flow control:Back-pressure flow control. In case the communication system or the sendercannot accept any further messages the sender is forced to delay the sending offurther messages until the overload condition has disappeared.
We say that backpressure is exercised on the sender.Example: In a CAN system a node cannot access the bus if a transmission by anothersender is in progress, i.e., the access protocol at the sender exerts backpressure on the nodethat intends to send a message.Explicit flow control. In explicit flow control (a form of back-pressure flow control)the receiver sends an explicit acknowledgment message back to thesender, informing the sender that the sender’s previous message arrived correctly,and that the receiver is now ready to accept the next message.
The most importantprotocol with explicit flow control is the well-known Positive-Acknowledgment-orRetransmission (PAR) protocol, described in the example of Sect. 7.1.2.Backpressure flow control and explicit flow control are based on the sometimesoverlooked assumption that the sender is within the sphere of control (SOC) of thereceiver, i.e., that the receiver can control the transmission speed of the sender (seeFig. 7.3). This is not the case in many real-time scenarios, since the progress of thephysical process cannot be influenced by the communication protocol.Example: On August 8, 1993 a prototype of a fly-by-wire fighter plane crashed, becausethe plane responded too slowly to the pilot’s commands [Neu95, p.37].Best-effort flow control.
In best effort flow control, the communication systemprovides intermediate buffer-storage for messages in case the link for the furthertransport of messages to the final receiver is not available. If a buffer overflows,messages are dropped.Example: In switched Ethernet, the Ethernet switch contains a buffer storage before thelink to a final receiver. In case this buffer overflows, backpressure is exercised or furthermessages are dropped. The duration during which a message has to reside in this buffer isdifficult to predict.1767 Real-Time CommunicationComputer to Pilot:“Please fly more slowly, I cannotfollow your commands”Fig. 7.3 Explicit flow control in a real-time systemBest-effort flow control cannot be used in hard real-time systems, since theuncontrollable delay or the throw away of messages is not acceptable.Rate-constrained flow control.
In rate-constrained flow control, the sender, thecommunication system and the receiver agree a priori, i.e., before the communication starts, on the maximum message rate. The communication system and thereceiver will accept all messages sent by the sender, as long as the sender rateremains below the agreed maximum.Implicit flow-control. In implicit flow control, the sender and receiver agree a priori,i.e., before the communication starts, on the instants when messages are sent andreceived. This requires the availability of a global time-base.
The sender commitsitself to send a message only at the agreed instants, and the receiver commits itselfto accept all messages sent by the sender, as long as the sender fulfills its obligation.No acknowledgment messages are exchanged during run time. Error detection is theresponsibility of the receiver that can determine (by looking at its global clock) whenan expected message fails to arrive.
Error detection latency is short, since it isdetermined by the precision of the clock synchronization. Implicit flow-control isthe most appropriate flow-control strategy for the exchange of real-time data.7.2.4ThrashingThe often-observed phenomenon of the throughput of a system decreasing abruptlywith increasing load is called thrashing. Thrashing can be observed in manysystems and is not limited to computer systems.Example: Consider the example of a traffic system in a large city. The throughput of theroad system increases with increasing traffic up to a certain critical point. When this criticalpoint is reached, further increase in traffic can lead to a reduction in throughput, or in otherwords, a traffic jam.Many systems can be characterized by a throughput-load dependency as shown inFig.
7.4. An ideal system exhibits the load throughput curve labeled ideal inFig. 7.4. The throughput increases with increasing load until the saturation pointhas been reached. From thereon, the throughput remains constant. A system has acontrolled load-throughput characteristic if the throughput increases monotonically7.2 Design Issues177100%Saturation PointThroughput(handled load)IdealControlledThrashing Point100 %Offered LoadFig.
7.4 Throughput-load characteristicwith the load and reaches the maximum throughput asymptotically. If the throughput increases up to a certain point, the thrashing point, and thereafter decreasesabruptly, we say the system is thrashing.Real-time systems must be free of the thrashing phenomena. If a real-timesystem contains a mechanism that can cause thrashing, then, it is likely that thesystem fails in the important rare-event scenarios discussed in Sect. 1.5.Mechanisms that can cause thrashing. Mechanisms that require a more thanproportional increase in resources as the load increases are prone to cause thrashing.Two examples of such mechanisms are:1.
A time-monitored retry mechanism (a type of PAR protocol) in a request-replyprotocol: If a communication system slows down because it can barely handlethe offered load, a request-reply protocol reaches its time-outs, and generatesadditional load.2. Operating system services: In a dynamic scheduling environment, the timeneeded to find a feasible schedule increases more than linearly as the requestedload reaches the capacity limit.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
