CS 452/652 Winter 2024 - Kernel Description

(Version: 2)

Kernel Programming Interface

A minimum kernel specification is given. You are permitted to add to this specification when done sparingly and with good justification. Do not just simply circumvent and re-implement the functionality specified here by your own set of interfaces!

Task Creation

Message Passing

Interrupt Processing

Only one generic primitive is required for interrupt processing.

Name Server Interface

This section comprises the interface of the name server. Knowing how and where to start name resolution is generally referred to as closure mechanism and must be implicit. Therefore this interface does not include a task id.

These interface functions can be implemented as wrappers covering a Send to the name server.

Clock Server Interface

The size of a clock tick is normally application dependent. In CS 452/652 it is 10 milliseconds, the time in which a train at top speed travels about 5-6 millimetres.

These interface functions can be implemented as wrappers covering Sends to a time server (specified by tid).

Input/Output Server Interface

Input/Output server interface. tid identifies an input/output server, and these calls can be implemented as Send to that server.

Algorithms and Data Structures

All algorithms must be fast in the sense that you can bound execution time at a reasonable level. 'Reasonable' means on a time scale appropriate for a train application. All data must be either static or on the stack. There is no heap and thus no dynamic memory allocation.

Task Descriptors

Basics

The most important data structure in the kernel is the array of task descriptors (TDs), which is allocated in kernel memory during kernel initialization. Every existing task has a TD allocated to it. A TD normally includes at least
  1. a task identifier (tid), which is unique among all active tasks,
  2. a pointer to the TD of the task that created it, its parent,
  3. the task's priority,
  4. a pointer to the TD of the next task in the task's ready queue,
  5. a point to the TD of the next task on the task's send queue,
  6. the task's current run state, and
  7. the task's current stack pointer.
The remainder of the task's state is saved either in the TD or on the stack. This includes

Comments

  1. A task is in one of the following run states.
    1. Active. The task that has just run, is running, or is about to run. Scheduling, which happens near the end of kernel processing, changes the active task. On a single processor only one task can be active at a time.
    2. Ready. The task is ready to be activated.
    3. Exited. The task will never again run. It may still retain some resources if resource re-use is not fully implemented.
    4. Send-blocked. The task has executed Receive(), and is waiting for a task to sent to it.
    5. Receive-blocked. The task has executed Send(), and is waiting for the message to be received.
    6. Reply-blocked. The task has executed Send() and its message has been received, but it has not received a reply.
    7. Event-blocked. The task has executed AwaitEvent(), but the event on which it is waiting has not occurred.
  2. The first three of these states are needed for task creation; the next three are needed for message passing; and the seventh is needed for hardware interrupts.
  3. The parent is the active task when a task is being created. This entails that the variable storing the active task is written only by the scheduler.
  4. A task has memory reserved for it when it is created, which it uses for its stack. The values of its registers are placed on the stack (or in the TD) when it is not executing.
  5. Each task has, when it is running, a program status register (CPSR), which is saved when it is interrupted and re-installed when the task is next activated.
  6. The task context switch also needs to save and restore other registers. These can be saved on the stack or in the TD.
  7. Tasks usually enter the kernel with requests for service. Many tasks must be provided with return values that indicate the result of the request. Because a task may not be rescheduled immediately the return value must be saved.

Scheduling

The kernel uses preemptive scheduling, that is, whenever an exception returns from the kernel (following a system call or a hardware interrupt), task scheduling is invoked to determine the next task to execute.

Priorities

Scheduling is done using static priorities: higher priority tasks that are ready to execute are guaranteed to execute before lower priority ones.
  1. The number of priorities is implementation-dependent.
  2. There can be more than one task at any priority. As tasks become ready to run, they are put on the end of their ready queue. The next task to run is always the highest priority task that is ready. If more than one task is ready at the highest priority, then the one at the head of the ready queue runs.
  3. A task instance may not be at more than one priority.

Round-Robin

While a task can have only a single priority; several tasks may have the same priority. They are scheduled round-robin. Each time scheduling occurs at a priority, the least recently readied task is scheduled, requiring something like a first-in, first-out queue.

No Ready Tasks

Occasionally, or even frequently, all ready queues are empty with one or more tasks being Event-blocked. In this case there are two things you want to do.
  1. You can have an idle task at the lowest priority, which does anything you want while it waits to be interrupted, and/or
  2. You can put the CPU into the halt state to reduce power consumption.

Context Switching

Those context switches into the kernel that occur when a running task requests a kernel service must be implemented using the ARM SWI instruction. Context switches generated by interrupts are defined by the architecture. The ARM architecture offers a variety of methods for exiting the kernel into a task. Choose whichever suits you.

Interrupts

The kernel should run with interrupts disabled. Thus, as little as possible should be done by the kernel because the time of the slowest kernel primitive must be added to the worst case response time of every action.

AwaitEvent() requires a table of event ids, which is, in essence a catalogue of hardware events to which the kernel and servers are able to provide a response. This is an awkward intrusion of hardware configuration into an otherwise clean operating system abstraction. There are many different ways of handling this issue within operating system design. Fortunately for you, the hardware environment in which you work is circumscribed and well-defined, so that you can create a small registry of events, provide a reasonably consistent set of responses, and not think too much about the general problem.

Message Formats

Messages are character arrays containing the contents of a struct. In distributed systems, a common message representation must be agreed upon by different participants. This is not an issue for CS 452/652. Type-checking might be handy, but can only be performed at run-time because there is no compile-time restriction on which task can send to which other task. You can get pretty close to run-time type checking by giving every structure a field, the value of which is its type. What you do when you discover a mismatch is the hard part. Can you recover at run-time? Or do you need to stop and reprogram?

You will, no doubt, find that early design of a set of message structures, combined with discipline in your task structure, is important in defending you from bugs that can take a long time to find.