Embedded Systems Introduction to Real-Time SystemsReal-Time SystemsSlide 3Real-Time ProgrammingLogical ConcurrencyProcessesInteractive C - MultitaskingHandyBoard Process ControlExample: MultitaskingSlide 10SchedulingSlide 12Scheduling-Problem FormulationPriority-Based Preemptive SchedulingPriorities and SchedulingSlide 16SchedulabilitySlide 18Slide 19Slide 20Slide 21Slide 22Rate Monotonic SchedulingExtensions to Rate Monotonic SchedulingOther Scheduling AlgorithmsSlide 26Periodic Tasks RevisitedSlide 28Laboratory for Perceptual Robotics – Department of Computer ScienceEmbedded Systems Introduction to Real-Time Systems2Laboratory for Perceptual Robotics – Department of Computer ScienceReal-Time SystemsDefinition: Real-time systems are those in which the correctness of the system depends not only on the logical results of the computation but also on the time at which the results are produced.Hard real-time systems: time critical - it is imperative that the system respond within a specified time period.Soft real-time systems: the system will function correctly, although at a lower overall utility if deadline are occasionally missed.3Laboratory for Perceptual Robotics – Department of Computer ScienceReal-Time Systemstiming constraints:periodic --- once per period T, precisely T units apartaperiodic --- start time, finish time, or both4Laboratory for Perceptual Robotics – Department of Computer ScienceReal-Time ProgrammingConcurrent, task-based approach• multi-tasking RTOS (VxWorks)• scheduling theory• industrial state-of-the-artSynchronous approach• reactive kernel represented as an automata• formal properties• special-purpose programming languages - Esterel• Discrete-Event Dynamic Systems5Laboratory for Perceptual Robotics – Department of Computer ScienceLogical ConcurrencyA concurrent program can be viewed as a collection of autonomous sequential processes executing (logically) in parallel. Each process has a single thread of control.multiplex on a single processor;• multiplex on a multi-processor with shared memory; or• multiplex on several processors without share memory (distributed systems)6Laboratory for Perceptual Robotics – Department of Computer ScienceProcessesA process (task) can be in one of the following process states:Ready: Processes that are ready to execute. Stored in a ReadyQueue (a linked list)Running: The currently executing process (the first process in the ReadyQueue)Blocked: Processes waiting for an event, e.g., an external event (Temp < Tmin)The switch from one running process to another is called a context switchThe process state consists of:• program counter,• process status information (priority, enabled interrupts), and• the contents of the programmable registers.Process administration is handled by the RT kernel7Laboratory for Perceptual Robotics – Department of Computer ScienceInteractive C - Multitaskingprocess - a function with a unique pid, local program stack (256 bytes default) for return addresses, local variables, arguments, etc, and a processor allocation in milliseconds---processes communicate via global variablesprocess table - a set of processes that are logically concurrent8Laboratory for Perceptual Robotics – Department of Computer ScienceHandyBoard Process Control• int start_process(function-call(…), [TICKS],[STACK-SIZE]) returns the process id• int kill_process(int pid)returns 0 if successfully killed, 1 otherwise (process not found)• kill_all()stops all running processes• psprocessor status• void hog_processor()allocates an additional 256 msec to the function currently running-called repeatedly, system will wedge requiring reset• void defer()Forces a context shift9Laboratory for Perceptual Robotics – Department of Computer ScienceExample: Multitaskingvoid check_sensor(int n) {while(1) printf(“sensor %d is %d\n”, n, digital(n));}void main() {int pid;pid = start_process(check_sensor(2));sleep(1.0);kill_process(pid);}starts check_sensor()and then kills it1 second laterQ: how often does check_sensor() actually run?10Laboratory for Perceptual Robotics – Department of Computer ScienceExample: Multitaskingvoid check_sensor(int n) {while(1) printf(“sensor %d is %d\n”, n, digital(n));}void main() {int pid;pid = start_process(check_sensor(2));sleep(1.0);kill_process(pid);}starts check_sensor()and then kills it1 second laterQ: how often does check_sensor() actually run?A: assuming nothing else is in the process table, thisprocess runs ~continuously in about 200 consecutive 5 msec chunks.11Laboratory for Perceptual Robotics – Department of Computer ScienceScheduling...to ensure that the run-time scheduler dispatches the runnableprocesses in an order that will result in all deadlines being met…orders the ReadyQueue allocates priorities BOTH STATIC AND DYNAMIC PRIORITY ALLOCATIONS ARE POSSIBLE12Laboratory for Perceptual Robotics – Department of Computer ScienceSchedulingOperations Research• job shop scheduling and shop-flow problems• schedule physical devices and processes - machines, workcells, maintenance, orders, batches, projects• mostly (not exclusively) static schedulesComputer Science• schedule tasks in a uni- or multiprocessor environment• mostly (not exclusively) dynamic schedules13Laboratory for Perceptual Robotics – Department of Computer ScienceScheduling-Problem FormulationEvents - anything that requires a response in the system---computation, work, communication• periodic, aperiodic, sporadic, and stochastic events• interruptsTime - execution times for event handling---how much time will it take to handle an event?• How much CPU time does a periodic process require?• How much time will it take to change a bearing on the milling machine?Deadline• upper bound on the time required to service an eventScheduling • reflects decisions about which event to process at a given time14Laboratory for Perceptual Robotics – Department of Computer SciencePriority-Based Preemptive SchedulingHow should processes be scheduled in order to maximize the utilization of the system while guaranteeing deadlines? priority reflects the severity of the time demands high low 0 255 The ReadyQueue is sorted by priority:A blocked process that becomes ready and has higher priority than the currently running process causes a context shift. This task preempts the running task.15Laboratory for Perceptual Robotics – Department