Real-Time Systems - Chapter 1: Basic Real-time concepts

Nội dung text: Real-Time Systems - Chapter 1: Basic Real-time concepts

1. REAL-TIME SYSTEMS Chapter 1: Basic Real-time concepts Computer Science Program
2. FUNDAMENTAL EXAMPLES Real-time systems (c) Cuong Pham-Quoc
3. Examples 1. Systems process data at a regular and timely rate – Aircraft positioning system 2. Systems rapid response to irregular events – Over-temperature failure in a nuclear plant 3. Airline reservation counter • All three systems are real-time: – process information within a specified interval – system failure 4. COVID-19 detector systems??? Not real-time Real-time systems (c) Cuong Pham-Quoc 3
4. TERMINOLOGY Real-time systems (c) Cuong Pham-Quoc
5. System concepts Software = Systems programs + Application programs • What does “system” mean? A system is a mapping of a set of inputs into a set of outputs Real-time systems (c) Cuong Pham-Quoc 5
6. Real-time systems • Typical real-time control system – inputs: sensors + image device • analog => digital – outputs: control signals + display • digital => analog • A classic representation of a real-time system – sequence of jobs to be scheduled – hidden hardware complexity Real-time systems (c) Cuong Pham-Quoc 6
7. Real-time systems A real-time system is a system that must satisfy explicit response-time constraints or risk severe consequences, including failure • “failure” ??? – Space shuttle or nuclear plant vs. automatic bank teller machine • “failure”: inability of the system to perform according to system specification Question: Does a system have to process data in μs to be considered real-time? Real-time systems (c) Cuong Pham-Quoc 7
8. Real-time systems • Reactive systems – scheduling is driven by ongoing interaction with their environment • e.g. fire-control • Embedded systems – inside a system (not itself a computer) • e.g. embedded computers in an automobile: fuel injection, airbag deployment, Real-time systems (c) Cuong Pham-Quoc 8
9. Real-time systems • Block diagram of a generic real-time control system Computer Science Computer Engineering (sensors) (actuators) Real-time systems (c) Cuong Pham-Quoc 9
10. When is a system real-time? Question: are all practical systems real-time systems? • e.g. ATM, grade processing, or word-processing program Real-time systems (c) Cuong Pham-Quoc 10
11. Soft vs. Hard A soft real-time system is one in which performance is degraded but not destroyed by failure to meet response- time constraints A hard real-time system is one in which failure to meet a single deadline may lead to complete and catastrophic system failure Real-time systems (c) Cuong Pham-Quoc 11
12. Example • Which systems can be considered as hard or soft real-time systems? Why?s – Automated teller machine – Embedded navigation controller for autonomous robot weed killer – Avionics weapons delivery system in which pressing a button launches an air-to-air missile A firm real-time system is one in which a few missed deadlines will not lead to total failure, but missing more than a few may lead to complete and catastrophic system failure Real-time systems (c) Cuong Pham-Quoc 12
13. Where do deadlines come from? • Underlying physical phenomena of the system under control – Images updated at approximately 30 frames/second – Accelerations must be read at a rate based on the velocity of the vehicle Real-time systems (c) Cuong Pham-Quoc 13
14. Response time & Punctuality The time between the presentation of a set of inputs to a system and the realization of the required behavior, including the availability of all associated outputs, is called the response time of the system Every response time has an average value, , with upper • tR and lower bounds of and , respectively tR + ϵU tR − ϵL + – ϵU, ϵL → 0 jitter: – t ∈ [−ϵL, + ϵU] Real-time systems (c) Cuong Pham-Quoc 14
15. Example • An elevator door is automatically operated and it may have a capacitive safety edge for sensing possible passengers between the closing door blades. Thus, the door blades can be quickly reopened before they touch the passenger and cause discomfort or even threaten the passenger’s safety • What is the required system response time from when it recognizes that a passenger is between the closing door blades and starting to reopen the door? Real-time systems (c) Cuong Pham-Quoc 15
16. Example • This response time consists of five independent latency components: Sensor: = 5 ms; = 15 ms – tSEmin tSEmax Hardware: = 1 μs; = 2 μs – tHWmin tHWmax System software: = 16 μs; = 48 μs – tSSmin tSSmax Application software: = 0.5 μs; = 0.5 μs – tASmin tASmax Door drive: = 300 ms; = 500 ms – tDDmin tDDmax • Now, we can calculate the minimum and maximum values of the composite response time: ≈ 305 ms; ≈ 515 ms tmin tmax Real-time systems (c) Cuong Pham-Quoc 16
17. Common misconceptions 1. Real-time systems are synonymous with “fast” systems – Many (but not all) hard real-time systems deal with deadlines in the tens of milliseconds; e.g. airline reservation system 2. There are universal, widely accepted methodologies for real-time systems specification and design – There is still no methodology available that answers all of the challenges of real-time specification and design all the time and for all applications Real-time systems (c) Cuong Pham-Quoc 17
18. Common misconceptions 3. There is no more a need to build a real-time operating system, because many commercial products exist – Commercial solutions have certainly their place, but choosing when to use an off-the-shelf solution and choosing the right one are continuing challenges Real-time systems (c) Cuong Pham-Quoc 18
19. Real-time system design issues • Complex sub-discipline of computer systems engineering Programming Languages Operating Algorithms Systems Data Software Structures Engineering Real-Time Systems Operations Control Research Theory Queuing Systems Theory Theory Computer Architecture Real-time systems (c) Cuong Pham-Quoc 19
20. Real-time system • Mars Exploration Rover: a solar-powered, autonomous real-time system with radio-communication links and a variety of sensors and actuators Real-time systems (c) Cuong Pham-Quoc 20
21. Practical Real-time systems • Aerospace • Industrial – Flight control – Crane – Navigation – Paper machine – Pilot interface – Welding robot • Automotive • Multimedia – Airbag deployment – Console game – Antilock braking – Home theater – Fuel injection – Simulator • Household • Medical Intensive care monitor – Microwave oven – Magnetic resonance imaging – Rice cooker – Remote surgery – Washing machine – Real-time systems (c) Cuong Pham-Quoc 21
22. Example: informal description • Consider the inertial measurement system for an aircraft: – receive x, y, and z accelerometer pulses at a 10ms rate to determine the accelerations in each direction and the roll, pitch, and yaw of the aircraft – receive information such as temperature at a 1s rate, and orientation, accelerometer readings, and various compensation factors at rate 40ms to compute actual velocity – output true acceleration, velocity, and position vectors to a pilot’s display every 40ms Real-time systems (c) Cuong Pham-Quoc 22
23. a bit more formal Accelerators Inertial Acceleration, from x, y, z 10ms measurement velocity, Temperature system and position sensors 1s 40ms The tasks execute at different rates and need to communicate and synchronize Real-time systems (c) Cuong Pham-Quoc 23
24. A REFERENCE MODEL Real-time systems (c) Cuong Pham-Quoc
25. Why and What? • When we study how given • Our reference model is applications should be characterized by: scheduled – A workload model – Only need to know whether • describes the applications the system meets all its supported by the system timing requirements – A resource model – Don’t need to know many • describes resources specific details: available to the applications – Scheduling algorithms • C-based implementation define how the application • Kalman filter • system uses the resources • ARM-based processor, at all times Real-time systems (c) Cuong Pham-Quoc 25
26. Jobs and Tasks • A job is a unit of work that is scheduled and executed by a system – e.g. computation of a control-law, computation of an FFT on sensor data, transmission of a data packet, retrieval of a file • A task is a set of related jobs which jointly provide some function – e.g. the set of jobs that constitute the “maintain constant altitude” task, keeping an airplane flying at a constant altitude Real-time systems (c) Cuong Pham-Quoc 26
27. Execution time A job will execute for time • Ji ei – This is the amount of time required to complete the execution of when it executes alone and has all the Ji resources it needs Value of depends upon complexity of the job and speed of – ei the processor on which it is scheduled; may change for a variety of reasons: • Conditional branches • Cache memories and/or pipelines • Compression (e.g. MPEG video frames) Real-time systems (c) Cuong Pham-Quoc 27
28. Execution time Execution times fall into an interval − + ; assume that • [ei , ei ] we know this interval for every hard real-time job, but not necessarily the actual ei – Terminology: (x, y] is an interval starting immediately after x, continuing up to and including Often, we can validate a system using + for each job; we • ei assume + and ignore the interval lower bound ei = ei – Inefficient, but safe bound on execution time Real-time systems (c) Cuong Pham-Quoc 28
29. Release and Response time • Release time: the instant in time when a job becomes available for execution May not be exact: release time jitter so is in the interval − + – ri [ri , ri ] – A job can be scheduled and executed at any time at, or after, its release time • Response time: the length of time from the release time of the job to the time instant when it completes – Not the same as execution time, why? Real-time systems (c) Cuong Pham-Quoc 29
30. Deadlines and Timing constraints • Completion time: the instant at which a job completes execution Relative deadline ( ): the maximum allowable job response time • Di Absolute deadline ( ): the instant of time by which a job is required to be • di completed (often called simply the deadline) – absolute deadline = release time + relative deadline Feasible interval for a job is the interval – Ji (ri, di] • Deadlines are examples of timing constraints Real-time systems (c) Cuong Pham-Quoc 30
31. Task • Unit of computation is a task – A task can be executed multiple times – An instance of task is a job – The functionality of the job is defined in the task • A processor executes a task T1 T2 Timeline 0 1 2 3 Real-time systems (c) Cuong Pham-Quoc 31
32. Types of task • There are various types of task – Periodic: set of jobs that are executed repeatedly at regular time intervals can be modelled as a periodic task • The most common type of task used in real-time systems – Aperiodic – Sporadic • Different execution time patterns for the jobs in the task • Must be modelled differently – Differing scheduling algorithms – Differing impact on system performance – Differing constraints on scheduling Real-time systems (c) Cuong Pham-Quoc 32
33. Periodic tasks: parameters Each periodic task is a sequence of jobs (instances) • Ti Ji,1, Ji,2, . . . , Ji,n The release time ( ): time instant at which the first job ( ) is ready – ri Ji,1 for execution The period ( ): the minimum length of all time intervals between – pi release times of consecutive jobs The execution time ( ): the maximum execution time of all jobs in the – ei periodic task The relative deadline ( ): the interval of time by which a job is – Di required to be completed from released In case no deadline specified • Di = pi Real-time systems (c) Cuong Pham-Quoc 33
34. Example 1 • A system to monitor and control a heating furnace – The system takes 20 ms to initialize when turned on – After initialization, every 100 ms, the system execute the following behavior: • Samples and reads the temperature sensor • Computes the control-law for the furnace to process temperature readings, determine the correct flow rates of fuel, air and coolant • Adjusts flow rates to match computed values • How can we model the system? Real-time systems (c) Cuong Pham-Quoc 34
35. Example 1 • The system consists of 1 task T (performing all behaviors) • The periodic task T is executed n time (J0, J2, . . . , Jn−1): – The periodic of T: 100 ms – The release time of Jk (0 ≤ k < n): 20 + (k × 100) ms – Each job must complete before the release of the next job: D = p = 100 ms : ms • Absolute deadline for Jk(0 ≤ k < n) 20 + [(k + 1) + 100] – Suppose each control-law computation may be required to finish sooner – i.e. the relative deadline is smaller than the time between jobs, allowing some slack time for other jobs Real-time systems (c) Cuong Pham-Quoc 35
36. Example 2 Execution time T1 r1 = 0, p1 = 3, D1 = 4 T2 r2 = 1, p2 = 10, D2 = 9 T 3 r3 = 5, p3 = 5, D3 = 2 r1 r2 d1,1 r3 d3,1 d2,1 r1 r2 d1,1r3 d3,1 d2,1 T T1 T2 T1 T1 T1 3 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Real-time systems (c) Cuong Pham-Quoc 36
37. Further (alternative) terminology • Feasibility interval: between release time and deadline (r, r + D] The release time of the first job (release time of the • r1,i task) is also called phase of task denoted by (“phi”) ϕi Feasibility interval deadline r1 D1 period phase T T1(5,1,4) 1 Execution time 0 1 2 3 4 5 6 7 8 9 10 Real-time systems (c) Cuong Pham-Quoc 37
38. Modelling periodic tasks • Hyper-period (H) of a set of periodic task (Ti) is the Least ) Common Multiple (LCM) of their periods (pi for H = LCM(pi) i = 1,2, ,n – Time after which the pattern of job release/execution times starts to repeat, limiting analysis needed • Example: Another example: – : - T1 p1 = 3; e1 = 1 T1 : p1 = 2 - – : T2 : p2 = 4 T2 p2 = 5; e2 = 2 - T3 : p3 = 10 Real-time systems (c) Cuong Pham-Quoc 38
39. Utilization e The ratio i is the utilization of task • ui = Ti pi The fraction of time of a periodic task with period and execution time keeps a – pi ei processor busy • The total utilization of a system is the sum of the utilizations of all tasks in a system: U = ∑ ui • We will usually assume the relative deadline for the jobs in a task is equal to the period of the task – It can sometimes be shorter than the period, to allow slack time • => Many useful, real-world, systems fit this model; and it is easy to reason about such periodic tasks • Question: what happen if U > 1.0? Real-time systems (c) Cuong Pham-Quoc 39
40. Sporadic & Aperiodic job • Many real-time systems are required to respond to external events • The jobs resulting from such events are sporadic or aperiodic jobs – A sporadic job has a hard deadlines – An aperiodic job has either a soft deadline or no deadline • The release time for sporadic or aperiodic jobs can be modelled as a random variable with some probability distribution, A(x) – A(x) gives the probability that the release time of the job is not later than x Real-time systems (c) Cuong Pham-Quoc 40
41. Precedence constraints and Dependencies • The jobs in a task, whether periodic, aperiodic or sporadic, may be constrained to execute in a particular order – This is known as a precedence constraint is – A job Ji is a predecessor of another job Jk (and Jk a successor of Ji) if Jk cannot begin execution until the execution of Ji completes • Denote this by saying Ji < Jk – Ji is an immediate predecessor of Jk if Ji < Jk and there is no other job Jl such that Ji < Jl < Jk – Ji and Jk are independent when neither Ji < Jk nor Jk < Ji • A job with a precedence constraint becomes ready for execution once when its release time has passed and when all predecessors have completed Real-time systems (c) Cuong Pham-Quoc 41
42. Task graphs • Can represent the precedence constraints among jobs in a set J using a directed graph G = (J, < ); each node represents a job; a directed edge goes from Ji to Jk if Ji is an immediate predecessor of Jk Real-time systems (c) Cuong Pham-Quoc 42
43. Task graphs: dependencies & constraints • Normally a job must wait for the completion of all immediate predecessors; an AND constraint • An OR constraint indicates that a job may begin after its release time if only some of the immediate predecessors have completed – Unfilled squares in the task graph • Represent conditional branches and joins by filled in circles • Use to visualize structure of real time systems Real-time systems (c) Cuong Pham-Quoc 43
44. Processor • A job executes – or is executed by the operating system – on a processor and may depend on some resources – A processor, P, is an active component on which jobs scheduled – Examples: • Threads scheduled on a CPU • Data scheduled on a transmission link • Read/write requests scheduled to a disk • Transactions scheduled on a database server – Each processor has a speed attribute which determines the rate of progress a job makes toward completion • May represent instructions-per-second for a CPU, bandwidth of a network, etc. – Two processors are of the same type if they are functionally identical and can be used interchangeably Real-time systems (c) Cuong Pham-Quoc 44
45. Resource • A resource, R, is a passive entity upon which jobs may depend – Examples: • memory • sequence numbers • mutexes • database locks – Resources have different types and sizes, but do not have a speed attribute – Resources are usually reusable, and are not consumed by use Real-time systems (c) Cuong Pham-Quoc 45
46. The use of resources • If the system contains ρ (“rho”) types of resource, this means: – There are ρ different types of serially reusable resources – There are one or more units of each type of resource, only one job can use each unit at once (mutually exclusive access) – A job must obtain a unit of a needed resource, use it, then release it • A resource is plentiful if no job is ever prevented from executing by the unavailability of units of the resource – Jobs never block when attempting to obtain a unit of a plentiful resource – We typically omit such resources from our discussion, since they don’t impact performance or correctness Real-time systems (c) Cuong Pham-Quoc 46
47. Functional parameters • Jobs may have priority, and in some cases may be interrupted by a higher priority job – A job is preemptable if its execution can be interrupted in this manner – A job is non-preemptable if it must run to completion once started • Many preemptable jobs have periods during which they cannot be preempted; for example when accessing certain resources – The ability to preempt a job (or not) impacts the scheduling algorithm – The context switch time is the time taken to switch between jobs • Forms an overhead that must be accounted for when scheduling jobs • Response to missing a deadline can vary – Some jobs have optional parts, that can be omitted to save time (at the expense of a poorer quality result) – Usefulness of late results varies; some applications tolerate some delay, others do not Real-time systems (c) Cuong Pham-Quoc 47
48. Scheduling • Jobs scheduled and allocated resources according to a chosen set of scheduling algorithms and resource access-control protocols – Scheduler implements these algorithms • A scheduler specifically assigns jobs to processors • A schedule is an assignment of all jobs in the system on the available processors. • A valid schedule satisfies the following conditions: – Every processor is assigned to at most one job at any time – Every job is assigned at most one processor at any time – No job is scheduled before its release time – The total amount of processor time assigned to every job is equal to its maximum or actual execution time – All the precedence and resource usage constraints are satisfied Real-time systems (c) Cuong Pham-Quoc 48
49. Scheduling • A valid schedule is also a feasible schedule if every job meets its timing constraints. – Miss rate is the percentage of jobs that are executed but completed too late – Loss rate is the percentage of jobs that are not executed at all • A hard real time scheduling algorithm is optimal if the algorithm always produces a feasible schedule if the given set of jobs has feasible schedules • Many scheduling algorithms exist: main focus of this module is understanding real-time scheduling Real-time systems (c) Cuong Pham-Quoc 49
50. Summary • Outline of terminology and a reference model: – Jobs and tasks – Processors and resources – Time and timing constraints • Hard real-time • Soft real-time – Periodic, aperiodic and sporadic tasks – Precedence constraints and dependencies – Scheduling Real-time systems (c) Cuong Pham-Quoc 50
51. Review questions 1. Because sporadic jobs may have varying release times and execution times, the periodic task model may be too inaccurate and can lead to unduly underutilization of the processor even when the inter-release times of jobs are bounded from below and their executions are bounded from above. As an example, suppose we have a stream of sporadic jobs whose inter-release times are uniformly distributed from 9 to 11. Their execution times are uniformly distributed from 1 to 3. A. What are the parameters of the periodic task if we were to use such a task to model the stream? B. Compare the utilization of the periodic task in part (A) with the average utilization of the sporadic job stream Real-time systems (c) Cuong Pham-Quoc 51
52. Review questions 2. Consider the real-time program described by the psuedo-code below. Names of jobs are in italic and green At 9AM, start: have breakfast Else, read; and Else go to office; write in office; At 10AM, When seminar is over, attend If there is class, social hour; teach; discuss; Else, help students; jog; When teach or help is done, eat eat dinner; lunch; work a little more; Until 2PM, sleep; end the day; If there is a seminar, If topic is interesting, listen; A. Draw a task graph to capture the dependencies among jobs. B. Use as many precedence graphs as needed to represent all the possible paths of the program Real-time systems (c) Cuong Pham-Quoc 52