Transcript Cyclic Executive

RTS: Kernel Design and Cyclic
Executives
1
CHAPTER 4
CE321-fall2013
4/9/2016
Kernel & Device drivers
Servers (application ~, web ~, component
~)
2
Shell
XWin
Thread lib
ftp
User applications
System call interface
Process, memory, file system, network managers.
Kernel
Device drivers
Hardware/controller
Devices
CE321-fall2013
4/9/2016
Operating System Models
3
I.
II.
III.
IV.
V.
Full-blown operating system like Windows or
Linux
Kernels with core functions (eg. Xinu)
Small systems with dedicated functions (eg. wii),
xbox)
Devices with systems optimized for one or more
functions (eg. mp3 player)
Cyclic executive (simple task loops.. Repeating:
heart pace maker, handheld games, whole new
area called “serious games/gamification”)
CE321-fall2013
4/9/2016
Task characteristics of real workload
4
 Each 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 task
 Phase Φi: release time of first instant of ith task
 Response time: time between activation and completion
 Absolute deadline: instant by which task must complete
 Relative 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.
CE321-fall2013
4/9/2016
Simple kernels
5
 Polled 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 bursts
CE321-fall2013
4/9/2016
Simple kernels: cyclic executives
6
 Illusion 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();
}
CE321-fall2013
4/9/2016
Cyclic Executives: Example: Interactive games
7
 Space 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.
CE321-fall2013
4/9/2016
Finite state automata and Co-routine based kernels
8
void process_a(void){
for(;;) {
switch (state_a) {
case 1: phase_a1(); |
case 2: phase_a2(); |
….
case n: phase_an();}}}
state_a and state_b are state
counters;
 Communication between coroutines
thru’ global variables;
 Example: the famous CICS from IBM
: Customer Information Control
System
 IBM’s OS/2 uses this in Windows
presentation management.

void process_b(void){
for(;;) {
switch (state_b) {
case 1: phase_b1(); |
case 2: phase_b2(); |
….
case n: phase_bn();}}}
CE321-fall2013
4/9/2016
Interrupt driven systems
9
 Main 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: asynchronous
Software: typically synchronous
 Executing process is suspended, state and context saved
and control is transferred to ISR (interrupt service routine)
CE321-fall2013
4/9/2016
Interrupt driven systems: code example
10
void main() {
init();
while(TRUE);
}
 Foreground/background systems
is a variation of this where main
does some useful task in the
background;
void int1(void){
save (context);
task1();
retore (context);}
void int1(void){
save (context);
task1();
restore (context);}
CE321-fall2013
4/9/2016
Process scheduling
11
 Scheduling is a very important function in a real-time
operating system.
 Two types: pre-run-time and run-time
 Pre-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 runtime mechanisms to meet time constraints.
CE321-fall2013
4/9/2016
More on Cyclic Executives
 Simple loop cyclic executive
 Frame/slots
 Table-based predetermined schedule cyclic
executive
 Periodic, aperiodic and interrupt-based task
 Lets design a cyclic-executive with multiple
periodic tasks.
12
CE321-fall2013
12
4/9/2016
The basic systems
 Several functions are called in a prearranged




sequence
Some kind of cooperative scheduling
You a have a set of tasks and a scheduler that
schedules these tasks
Types of tasks: base tasks (background),
interrupt tasks, clock tasks
Frame of slots, slots of cycles, each task taking a
cycle, burn tasks to fill up the left over cycles in
a frame.
13
CE321-fall2013
13
4/9/2016
Blind Bingo ( A Simple Example)
A
c
b
g
V
n
m
L
s
E
t
y
w
f
D
v
z
x
e
Display();
Read input();
Loop:
update display();
If all done exit();
Read input();
End Loop;
k
14
CE321-fall2013
14
4/9/2016
Cyclic Executive Design 1 (pages 81-87)
15
 Base tasks, clock tasks, interrupt tasks
 Base: no strict requirements, background activity
 Clock: periodic with fixed runtime
 Interrupt: event-driven preemption, rapid response but little
processing
 Design the slots
 Table-driven cyclic executive
CE321-fall2013
4/9/2016
Cyclic executive
16
 Each task implemented as a function
 All tasks see global data and share them
 Cyclic executive for three priority level
 The 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 task
 Study the figures in pages 83-86 of your text
CE321-fall2013
4/9/2016
RT Cyclic Executive Program
17
 Lets examine the code:
 Identify the tasks
 Identify the cyclic schedule specified in the form of a
table
 Observe how the functions are specified as table
entry
 Understand the scheduler is built-in
 Learn how the function in the table are dispatched
CE321-fall2013
4/9/2016
Implementation of a cyclic executive
18
#include <stdio.h>
#include <ctype.h>
#include <unistd.h>
#include <sys/times.h>
#define SLOTX 4
#define CYCLEX 5
#define SLOT_T 5000
int tps,cycle=0,slot=0;
clock_t now, then;
struct tms n;
void one() {
printf("Task 1 running\n");
sleep(1);
}
void two() {
printf("Task 2 running\n");
sleep(1); }
CE321-fall2013
4/9/2016
Implementation (contd.)
19
void three() {
printf("Task 3 running\n");
sleep(1);
}
void four() {
printf("Task 4 running\n");
sleep(1);
}
void five() {
printf("Task 5 running\n");
sleep(1);
}
CE321-fall2013
4/9/2016
Implementation (contd.)
20
void burn() {
clock_t bstart = times(&n);
while ((( now = times(&n)) - then) < SLOT_T * tps /
1000) { }
printf (" brn time = %2.2dms\n\n", (times(&n)bstart)*1000/tps);
then = now;
cycle = CYCLEX;
}
CE321-fall2013
4/9/2016
Implementation (contd.)
21
void (*ttable[SLOTX][CYCLEX])() = {
{one, two, burn, burn, burn},
{one, three, four, burn, burn},
{one, two, burn, burn, burn},
{one, five, four, burn, burn}};
main() {
tps = sysconf(_SC_CLK_TCK);
printf("clock ticks/sec = %d\n\n", tps);
then = times(&n);
while (1) {
for (slot=0; slot <SLOTX; slot++)
for (cycle=0; cycle<CYCLEX; cycle++)
(*ttable[slot][cycle])();
}}
CE321-fall2013
4/9/2016
Summary
22
 The cyclic executive discussed the scheduler is built-
in. You can also use clock ticks RTC etc to schedule
the tasks
 In order use the cyclic executive discussed here in
other applications simply change table configuration,
and rewrite the dummy functions we used.
CE321-fall2013
4/9/2016