Personal tools

Difference between revisions of "Non-blocking Algorithms in Real-Time Operating Systems"

From iis-projects

Jump to: navigation, search
(Created page with "<!-- Core-Local Interrupt Controller for the CVA6 --> Category:Digital Category:Computer Architecture Category:SW/HW Predictability and Security Category:2021...")
 
Line 22: Line 22:
 
= Introduction =
 
= Introduction =
  
CVA6 (formerly Ariane), 6-stage, 64-bit, in-order RISC-V core developed at IIS [1]. It is capable of booting Linux and it is widely used both in academia and industry. The CVA 6 is currently using a basic interrupt controller (often called CLINT) to handle timer, external and software interrupts. This interrupt controller is designed for generic UNIX workloads, but fails to deliver when interrupt latency, interrupt nesting and fine grained control over interrupt priorities/levels is more critical. A new specification outlines The Core-Local Interrupt Controller (CLIC)[2] promising low-latency, vectored, pre-emptive interrupts that tries to fill this gap.
+
Interrupt latency and jitter is an important criterion for real-time schedulability. There are various ways to keep interrupt latency low. On the hardware-level, you can make sure that they can quickly propagate to the processor by moving parts that are slow such as the handshaking into hardware and provide features such as efficient interrupt nesting to allow high priority interrupts to get the highest attention. On the software-level you try to keep interrupt handling routines and critical sections as short as possible. In fact, the maximum interrupt latency (the worst-case) is largely determined by the method the OS uses for interrupt handling. For example, you usually disable interrupts to protect critical sections. This is necessary, because the interrupt could cause the interrupt handler or another task that might get scheduled to modify the same data structure protected by the critical section. Effectively, the critical section extends the worst-case interrupt latency by the number of cycles it takes to execute said piece of code. Non-blocking algorithms [1] [2] [3] do away with critical sections and instead use atomic read-modify-write primitives directly. This consequently reduces the worst-case interrupt latency.
  
 
= Project =
 
= Project =

Revision as of 19:30, 19 November 2021


Overview

Status: Available

Introduction

Interrupt latency and jitter is an important criterion for real-time schedulability. There are various ways to keep interrupt latency low. On the hardware-level, you can make sure that they can quickly propagate to the processor by moving parts that are slow such as the handshaking into hardware and provide features such as efficient interrupt nesting to allow high priority interrupts to get the highest attention. On the software-level you try to keep interrupt handling routines and critical sections as short as possible. In fact, the maximum interrupt latency (the worst-case) is largely determined by the method the OS uses for interrupt handling. For example, you usually disable interrupts to protect critical sections. This is necessary, because the interrupt could cause the interrupt handler or another task that might get scheduled to modify the same data structure protected by the critical section. Effectively, the critical section extends the worst-case interrupt latency by the number of cycles it takes to execute said piece of code. Non-blocking algorithms [1] [2] [3] do away with critical sections and instead use atomic read-modify-write primitives directly. This consequently reduces the worst-case interrupt latency.

Project

The goal of this project is to look at data structures and task communication primitives used in FreeRTOS [4], an open-source real-time operating system (RTOS) used by Amazon, and determine how they use critical sections. Turn these algorithms into non-blocking versions.

We have some algorithms such as a non-blocking queue already available which can serve as a starting point. As development platform ControlPULP, a version of PULP [5] compromising a single RISC-V controller core and eigh RISC-V accelerator cores extended to support real-time applications, can be used. Programs can be run either on an FPGA implementation thereof or in RTL simulations.

Measure the performance impact, interrupt latency and jitter.

Character

  • 20% Literature / architecture review
  • 60% Low-level C programming
  • 20% Evaluation

Prerequisites

  • Strong interest in computer architecture
  • Experience with low-level programming in C
  • Experience with Operating Systems


References

[1] Non-blocking Algorithms

[2] On the nature of progress

[3] The Art of Multiprocessor Programming

[4] FreeRTOS

[5] Energy-Efficient Near-Threshold Parallel Computing: The PULPv2 Cluster