RTS: Kernel Design and Cyclic ExecutivesKernel & Device driversTask characteristics of real workloadSimple kernelsSimple kernels: cyclic executivesCyclic Executives: Example: Interactive gamesFinite state automata and Co-routine based kernelsInterrupt driven systemsInterrupt driven systems: code exampleProcess schedulingMore on Cyclic ExecutivesThe basic systemsBlind BingoCyclic Executive Design 1 (pages 83-87)Cyclic executiveRT Cyclic Executive ProgramCHAPTER 401/13/191RTS: Kernel Design and Cyclic ExecutivesKernel & Device drivers01/13/192Shell XWin Thread lib ftp User applicationsSystem call interface DevicesProcess, memory, file system, network managers.Device drivers KernelServers (application ~, web ~, component ~)Hardware/controllerTask characteristics of real workload01/13/193Each task Ti is characterized by the following temporal parameters:Precedence constraints: specify any tasks need to precede other tasks.Release or arrival time: ri,j: jth instance of ith taskPhase Φi: release time of first instant of ith taskResponse time: time between activation and completionAbsolute deadline: instant by which task must completeRelative deadline: maximum allowable response time Period Pi: maximum length of intervals between the release times of consecutive tasks.Execution time: the maximum amount of time required to complete a instance of the task assuming all the resources are available.Simple kernels01/13/194Polled loop: Say a kernel needs to process packets that are transferred into the DMA and a flag is set after transfer:for(;;) { if (packet_here) { process_data(); packet_here=0; }}Excellent for handling high-speed data channels, a processor is dedicated to handling the data channel.Disadvantage: cannot handle burstsSimple kernels: cyclic executives01/13/195Illusion of simultaneity by taking advantage of relatively short processes in a continuous loop:for(;;) { process_1(); process_2(); process_3(); … process_n();}Different rate structures can be achieved by repeating tasks in the list:for(;;) { process_1(); process_2(); process_3(); process_3();}Cyclic Executives: Example: Interactive games01/13/196Space invaders:for(;;) { check_for_keypressed(); move_aliens(); check_for_keypressed(); check_collision(); check_for_keypressed(); update_screen(); }}check_keypressed() checks for three button pressings: move tank left or right and fire missiles.If the schedule is carefully constructed we could achieve a very efficient game program with a simple kernel as shown above.Finite state automata and Co-routine based kernels01/13/197void process_a(void){for(;;) { switch (state_a) { case 1: phase_a1(); | case 2: phase_a2(); |…. case n: phase_an();}}}void process_b(void){for(;;) { switch (state_b) { case 1: phase_b1(); | case 2: phase_b2(); |…. case n: phase_bn();}}}state_a and state_b are state counters;Communication between coroutines thru’ global variables;Example: the famous CICS from IBM : Customer Information Control SystemIBM’s OS/2 uses this in Windows presentation management.Interrupt driven systems01/13/198Main program is a simple loop.Various tasks in the system are schedules via software or hardware interrupts;Dispatching performed by interrupt handling routines.Hardware and software interrupts.Hardware: asynchronousSoftware: typically synchronousExecuting process is suspended, state and context saved and control is transferred to ISR (interrupt service routine)Interrupt driven systems: code example01/13/199void main() { init(); while(TRUE);}void int1(void){ save (context); task1(); retore (context);}void int1(void){ save (context); task1(); restore (context);}Foreground/background systems is a variation of this where main does some useful task in the background;Process scheduling 01/13/1910Scheduling is a very important function in a real-time operating system.Two types: pre-run-time and run-timePre-run-time scheduling: create a feasible schedule offline to meet time constraints, guarantee execution order of processes, and prevents simultaneous accesses to shared resources.Run-time scheduling: allows events to interrupt processes, on demand allocation of resources , and used complex run-time mechanisms to meet time constraints.01/13/1911More on Cyclic ExecutivesSimple loop cyclic executiveFrame/slots Table-based predetermined schedule cyclic executivePeriodic, aperiodic and interrupt-based taskLets design a cyclic-executive with multiple periodic tasks. 1101/13/1912The basic systemsSeveral functions are called in a prearranged sequenceSome kind of cooperative schedulingYou a have a set of tasks and a scheduler that schedules these tasksTypes of tasks: base tasks (background), interrupt tasks, clock tasksFrame of slots, slots of cycles, each task taking a cycle, burn tasks to fill up the left over cycles in a frame.1201/13/1913Blind Bingo 13A c b g k V n m L sE t y w fD v z x eDisplay();Read input();Loop: update display(); If all done exit(); Read input();End Loop;Cyclic Executive Design 1 (pages 83-87)01/13/1914Base tasks, clock tasks, interrupt tasksBase: no strict requirements, background activityClock: periodic with fixed runtimeInterrupt: event-driven preemption, rapid response but little processingDesign the slotsTable-driven cyclic executiveCyclic executive01/13/1915Each task implemented as a functionAll tasks see global data and share themCyclic executive for three priority levelThe execution sequence of tasks within a cyclic executive will NOT vary in any unpredictable manner (such as in a regular fully featured Operating Systems)Clock tasks, clock sched, base tasks, base sched, interrupt tasks Each clock slot executes, clock tasks, at the end a burn task that is usually the base taskStudy the figures in pages 83-86 of your textRT Cyclic Executive Program01/13/1916Lets examine the code:Identify the tasksIdentify the cyclic schedule specified in the form of a tableObserve how the functions are specified as table entryLearn how the function in the table are
View Full Document
Unlocking...