Transcript CycKernel

RTS: Kernel Design and Cyclic
Executives
1
CHAPTER 4
Amrita-UB-MSES-2013-4
6/1/2013
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
Amrita-UB-MSES-2013-4
6/1/2013
Task characteristics of real workload
3
 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.
Amrita-UB-MSES-2013-4
6/1/2013
Simple kernels
4
 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
Amrita-UB-MSES-2013-4
6/1/2013
Simple kernels: cyclic executives
5
 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();
}
Amrita-UB-MSES-2013-4
6/1/2013
Cyclic Executives: Example: Interactive games
6
 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.
Amrita-UB-MSES-2013-4
6/1/2013
Finite state automata and Co-routine based kernels
7
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();}}}
Amrita-UB-MSES-2013-4
6/1/2013
Interrupt driven systems
8
 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)
Amrita-UB-MSES-2013-4
6/1/2013
Interrupt driven systems: code example
9
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);}
Amrita-UB-MSES-2013-4
6/1/2013
Process scheduling
10
 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.
Amrita-UB-MSES-2013-4
6/1/2013
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.
11
Amrita-UB-MSES-2013-4
11
6/1/2013
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.
12
Amrita-UB-MSES-2013-4
12
6/1/2013
Cyclic Executive Design 1 (pages 81-87)
13
 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
Amrita-UB-MSES-2013-4
6/1/2013
Cyclic executive
14
 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
Amrita-UB-MSES-2013-4
6/1/2013
RT Cyclic Executive Program
15
 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
Amrita-UB-MSES-2013-4
6/1/2013
Implementation of a cyclic executive
16
#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); }
Amrita-UB-MSES-2013-4
6/1/2013
Implementation (contd.)
17
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);
}
Amrita-UB-MSES-2013-4
6/1/2013
Implementation (contd.)
18
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;
}
Amrita-UB-MSES-2013-4
6/1/2013
Implementation (contd.)
19
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])();
}}
Amrita-UB-MSES-2013-4
6/1/2013
Summary
20
 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.
Amrita-UB-MSES-2013-4
6/1/2013