CS452/652 Winter 2020 - Kernel Description

(Version: Jan 12 19:47:29)

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

int Create(int priority, void (*function)())

allocates and initializes a task descriptor, using the given priority, and the given function pointer as a pointer to the entry point of executable code, essentially a function with no arguments and no return value. When Create returns, the task descriptor has all the state needed to run the task, the task’s stack has been suitably initialized, and the task has been entered into its ready queue so that it will run the next time it is scheduled.

Return Value

tid the positive integer task id of the newly created task. The task id must be unique, in the sense that no other active task has the same task id.
-1 invalid priority.
-2 kernel is out of task descriptors.
Comment: If newly created tasks need to receive configuration parameters, these generally need to be provided via message passing. However, if the configuration value is a primitive type, implementing a shortcut via another argument to Create() and function() is permissible.

```
int MyTid()
```
returns the task id of the calling task.
Return Value

tid the positive integer task id of the task that calls it.
Comment: Errors should be impossible!
```
int MyParentTid( )
```
returns the task id of the task that created the calling task. This will be problematic only if the task has exited or been destroyed, in which case the return value is implementation-dependent.
Return Value

tid the task id of the task that created the calling task.
Comment: The return value is implementation-dependent, if the parent has exited, has been de- stroyed, or is in the process of being destroyed.
```
void Yield()
```
causes a task to pause executing. The task is moved to the end of its priority queue, and will resume executing when next scheduled.
Comment: Like every entry to the kernel, Yield() reschedules.
```
void Exit()
```
causes a task to cease execution permanently. It is removed from all priority queues, send queues, receive queues and event queues. Resources owned by the task, primarily its memory and task descriptor, are not reclaimed.
Comment: Exit does not return at all. If a point occurs where all tasks have exited, the kernel should return cleanly to RedBoot.
```
void Destroy()
```
imples Exit(), but also releases the task's memory and task descriptor.
Comment: This functionality is not necessarily needed. Re-using resources is complicated. This will be discussed in class.

Message Passing

int Send(int tid, const char *msg, int msglen, char *reply, int rplen)

sends a message to another task and receives a reply. The message, in a buffer in the sending task’s memory, is copied to the memory of the task to which it is sent by the kernel. Send() supplies a buffer into which the reply is to be copied, and the size of the reply buffer, so that the kernel can detect overflow. When Send() returns without error it is guaranteed that the message has been received, and that a reply has been sent, not necessarily by the same task. The kernel will not overflow the reply buffer. If the size of the reply set exceeds rplen, the reply is truncated and the buffer contains the first rplen characters of the reply. The caller is expected to check the return value and to act accordingly. There is no guarantee that Send() will return. If, for example, the task to which the message is directed never calls Receive(), Send() never returns and the sending task remains blocked forever. Send() has a passing resemblance, and no more, to a remote procedure call.

Return Value

>-1 the size of the message returned by the replying task. The actual reply is less than or equal to the size of the reply buffer provided for it. Longer replies are truncated.
-1 tid is not the task id of an existing task.
-2 send-receive-reply transaction could not be completed.

```
int Receive(int *tid, char *msg, int msglen)
```
blocks until a message is sent to the caller, then returns with the message in its message buffer and tid set to the task id of the task that sent the message. Messages sent before Receive() is called are retained in a send queue, from which they are received in first-come, first-served order. The argument msg must point to a buffer at least as large as msglen. The kernel will not overflow the message buffer. If the size of the message set exceeds msglen, the message is truncated and the buffer contains the first msglen characters of the message sent. The caller is expected to check the return value and to act accordingly.
Return Value

>-1 the size of the message sent by the sender (stored in tid). The actual message is less than or equal to the size of the message buffer supplied. Longer messages are truncated.

int Reply(int tid, const char *reply, int rplen)

sends a reply to a task that previously sent a message. When it returns without error, the reply has been copied into the sender’s memory. The calling task and the sender return at the same logical time, so whichever is of higher priority runs first. If they are of the same priority, the sender runs first.

Return Value

>-1 the size of the reply message transmitted to the original sender task. If this is less than the size of the reply message, the message has been truncated.
-1 tid is not the task id of an existing task.
-2 tid is not the task id of a reply-blocked task.

Name Server

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.

```
int RegisterAs(const char *name)
```
registers the task id of the caller under the given name. On return without error it is guaranteed that all WhoIs() calls by any task will return the task id of the caller until the registration is overwritten. If another task has already registered with the given name, its registration is overwritten. RegisterAs() is actually a wrapper covering a send to the name server.
Return Value

0 success.
-1 invalid name server task id inside wrapper.
```
int WhoIs(const char *name)
```
asks the name server for the task id of the task that is registered under the given name. Whether WhoIs() blocks waiting for a registration or returns with an error, if no task is registered under the given name, is implementation-dependent. There is guaranteed to be a unique task id associated with each registered name, but the registered task may change at any time after a call to WhoIs(). WhoIs() is actually a wrapper covering a send to the name server.
Return Value

tid task id of the registered task.
-1 invalid name server task id inside wrapper.

Interrupt Processing

Only one generic primitive is required for interrupt processing.

```
int AwaitEvent(int eventid)
```
blocks until the event identified by eventid occurs then returns with volatile data, if any.
Return Value

>-1 volatile data, in the form of a positive integer.
-1 invalid event.
-2 corrupted volatile data.

Clock Server

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.

```
int Time(int tid)
```
returns the number of ticks since the clock server was created and initialized. With a 10 millisecond tick and a 32-bit unsigned int for the time wraparound is almost 12,000 hours, plenty of time for your demo. Time is actually a wrapper for a send to the clock server. The argument is the tid of the clock server.
Return Value

>-1 time in ticks since the clock server initialized.
-1 tid is not a valid clock server task.
```
int Delay(int tid, int ticks)
```
returns after the given number of ticks has elapsed. How long after is not guaranteed because the caller may have to wait on higher priority tasks. Delay() is (almost) identical to Yield() if ticks is zero. Delay() is actually a wrapper for a send to the clock server.
Return Value

>-1 success. The current time returned (as in Time())
-1 tid is not a valid clock server task.
-2 negative delay.
```
int DelayUntil(int tid, int ticks)
```
returns when the time since clock server initialization is greater or equal than the given number of ticks. How long after is not guaranteed because the caller may have to wait on higher priority tasks. Also, DelayUntil(tid, Time(tid) + ticks) may differ from Delay(tid, ticks) by a small amount. DelayUntil is actually a wrapper for a send to the clock server.
Return Value

>-1 success. The current time returned (as in Time())
-1 tid is not a valid clock server task.
-2 negative delay.

Input/Output

```
int Getc(int tid, int uart)
```
returns next unreturned character from the given UART. The first argument is the task id of the appropriate server. How communication errors are handled is implementation-dependent. Getc() is actually a wrapper for a send to the appropriate server.
Return Value

>-1 new character from the given UART.
-1 tid is not a valid uart server task.
```
int Putc(int tid, int uart, char ch)
```
queues the given character for transmission by the given UART. On return the only guarantee is that the character has been queued. Whether it has been transmitted or received is not guaranteed. How communication errors are handled is implementation-dependent. Putc() is actually a wrapper for a send to the appropriate server.
Return Value

0 success.
-1 tid is not a valid uart server task.

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

a task identifier (tid), which is unique among all active tasks,
a pointer to the TD of the task that created it, its parent,
the task’s priority,
a pointer to the TD of the next task in the task’s ready queue,
a point to the TD of the next task on the task’s send queue,
the task’s current run state, and
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

the task’s return value, and
the task’s SPSR.

Comments

When Destroy() is not implemented the task id can be a simple array index because TDs are not re-used. When Destroy() is implemented a better task id model is needed.
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. Zombie. The task will never again run, but still retains it resources: memory, TD, etc.
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.
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.
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.
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.
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.
The task context switch also needs to save and restore other registers. These can be saved on the stack or in the TD.
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

Priorities

Scheduling is done using static priorities: higher priority tasks that are ready to execute are guaranteed to execute before lower priority ones.

The number of priorities is implementation-dependent.
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.
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.

You can have an idle task at the lowest priority, which does anything you want while it waits to be interrupted, and/or
You can put the CPU into the halt state to reduce power consumption.

Exiting from the Kernel

During the first two parts of kernel development the kernel should exit cleanly to RedBoot when there are no tasks in the ready queues. Once interrupts are introduced the kernel should exit cleanly to RedBoot when there are no Event-blocked tasks and no tasks in the ready queues. Kernels do not normally exit.

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.

`tid`	the positive integer task id of the newly created task. The task id must be unique, in the sense that no other active task has the same task id.
`-1`	invalid priority.
`-2`	kernel is out of task descriptors.

`>-1`	the size of the message returned by the replying task. The actual reply is less than or equal to the size of the reply buffer provided for it. Longer replies are truncated.
`-1`	`tid` is not the task id of an existing task.
`-2`	send-receive-reply transaction could not be completed.

`>-1`	the size of the reply message transmitted to the original sender task. If this is less than the size of the reply message, the message has been truncated.
`-1`	`tid` is not the task id of an existing task.
`-2`	`tid` is not the task id of a reply-blocked task.

`tid`	task id of the registered task.
`-1`	invalid name server task id inside wrapper.

`>-1`	volatile data, in the form of a positive integer.
`-1`	invalid event.
`-2`	corrupted volatile data.

`>-1`	time in ticks since the clock server initialized.
`-1`	`tid` is not a valid clock server task.

`>-1`	success. The current time returned (as in `Time()`)
`-1`	`tid` is not a valid clock server task.
`-2`	negative delay.

`>-1`	new character from the given UART.
`-1`	`tid` is not a valid uart server task.