Adaptive Partitioning

• What are partitions?
• Why adaptive?
• Benefits of adaptive partitioning
• Adaptive partitioning thread scheduler

What are partitions?

In many computer systems, it's important to protect different applications or groups of applications from others. You don't want one application — whether defective or malicious — to corrupt another or prevent it from running.

To address this issue, some systems use virtual walls, called partitions, around a set of applications to ensure that each partition is given an engineered set of resources. The primary resource considered is CPU time, but can also include any shared resource, such as memory and file space (disk or flash).

Static partitions guarantee that processes get the resources specified by the system designer.

Typically, the main objective of competing resource partitioning systems is to divide a computer into a set of smaller computers that interact as little as possible; however, this approach is not very flexible. Adaptive partitioning takes a much more flexible view.

QNX Neutrino partitions are adaptive because:

• you can change configurations at run time
• they're typically fixed at one configuration time
• the partition behavior auto-adapts to conditions at run time. For example:
  • free time is redistributed to other scheduler partitions
  • filesystems can bill time to clients with a mechanism that temporarily moves threads between time partitions

As a result, adaptive partitions are less restrictive and much more powerful. In addition to being adaptive, time partitions allow you to easily model the fundamentally different behavior of CPU time when viewed as a resource. The separation of scheduler partitions also allows you to create a highly tuned implementation for each.

Because adaptive partitions are not “boxes” what are they?

An adaptive partition is a named set of rules. The rules are selected to control the global resource behavior of the system. When a process or thread is associated with a particular partition (scheduler), then its actions are governed by the rules of that partition at that time.

For example, adaptive partitioning is similar to people who belong to clubs. Each person can join several different clubs. They can even move from club to club at times. But while they are at a particular club, they agree to abide by the rules of that particular club.

Partitions provide:

• memory protection — each partition is discrete and controlled by the Memory Management Unit (MMU)
• overload protection — each partition is guaranteed a slice of execution time, as specified by the system designer

By using multiple partitions, you can avoid having a single point of failure. For example, a runaway process can't occupy the entire system's resources; processes in other partitions still receive their allocated share of system resources.

Currently, QNX Neutrino's process model provides significantly more protection than some other operating systems do, including:

• full memory protection between processes
• message-passing to provide uniform and controlled IPC
• priority inheritance with a clean client-server model
• hard realtime deterministic scheduling
• a detailed permission model for devices, files, and memory
• memory, file-descriptor, CPU, and priority limits, using the POSIX setrlimit() function to constrain runaway processes

Why adaptive?

To provide realtime performance with guarantees against overloading, QNX Neutrino introduced adaptive partitioning. Rigid partitions work best in fairly static systems with little or no dynamic deployment of software. In dynamic systems, static partitions can be inefficient. For example, the static division of execution time between partitions can waste CPU time and introduce delays:

• If most of the partitions are idle, and one is very busy, the busy partition doesn't receive any additional execution time, while background threads in the other partitions waste CPU time.
• If an interrupt is scheduled for a partition, it has to wait until the partition runs. This can cause unacceptable latency, especially if bursts of interrupts occur.

---

You can introduce adaptive partitioning without changing — or even recompiling — your application code, although you do have to rebuild your system's OS image.

---

An adaptive partition is a set of threads that work on a common or related goal or activity. Like a static partition, an adaptive partition has a budget allocated to it that guarantees its minimum share of the CPU's resources. Unlike a static partition, an adaptive partition:

• isn't locked to a fixed set of code in a static partition; you can dynamically add and configure adaptive partitions, as required

  ---

  There's a limit to the number of partitions. For the thread scheduler, there's a maximum of eight scheduler partitions because for every scheduling operation, the thread scheduler must examine every partition before it can pick a thread on which to run. That may occur 50000 times per second on a 700 MHz x86 (i.e. a slow machine). So it's important to limit the number of scheduler partitions to keep the scheduler overhead to a minimum.

  ---

• behaves as a global hard realtime thread scheduler under normal load, but can still provide minimal interrupt latencies even under overload conditions
• maximizes the usage of the CPU's resources. In the case of the thread scheduler, it distributes a partition's unused budget among partitions that require extra resources when the system isn't loaded.

Benefits of adaptive partitioning

Adaptive partitioning provides a number of benefits to the design, development, running, and debugging of your system, as described in these areas:

• Engineering product performance
• Dealing with design complexity
• Providing security
• Debugging

Engineering product performance

Partitioning

Partitions divide resources so that they can be used by a collection of programs. A partition represents a fraction of a resource and includes few rules that define the resource usage. The resources include basic objects, such as processor cycles, program store or high-level objects, such as buffers, page tables, or file descriptors.

With respect to the thread scheduler, adaptive partitioning ensures that any free time available in the system (i.e. CPU time in a partition's budget that the partition doesn't need) is made available to other partitions. This lets the system handle sudden processing demands that occur during normal system operation. With a cyclic thread scheduler, there's a “use it or lose it” approach where unused CPU time is spent running an idler thread in partitions that don't use their full budget.

Partition inheritance

Another important feature of adaptive partitioning is the concept of partition inheritance.

For the thread scheduler, this feature lets designers develop server processes that run with no (or minimal) budget. When the server performs requests from clients, the client partition is billed for the time. Without this feature, CPU budget would be allocated to a server regardless of how much or often it's used. The benefits of these features include:

• You don't have to over-engineer the system, so the overall cost decreases.
• If you add an application, you don't have to re-engineer the budget of common services, such as filesystems or servers.
• The system is faster and more responsive to the user.
• The system guarantees time for important tasks.
• You can use priorities to specify a process's urgency, and a partition's CPU budget to specify its importance.

Dealing with design complexity

Designing large-scale distributed systems is inherently complex. Typical systems have a large number of subsystems, processes, and threads developed in isolation from each other. The design is divided among groups with differing system performance goals, different schemes for determining priorities, and different approaches to runtime optimization.

This can be further compounded by product development in different geographic locations and time zones. Once all of these disparate subsystems are integrated into a common runtime environment, all parts of the system need to provide adequate response under all operating scenarios, such as:

• normal system loading
• peak periods
• failure conditions

Given the parallel development paths, system issues invariably arise when integrating the product. Typically, once a system is running, unforeseen interactions that cause serious performance degradations are uncovered. When situations such as this arise, there are usually very few designers or architects who can diagnose and solve these problems at a system level. Solutions often take considerable modifications (frequently, by trial and error) to get it right. This extends system integration, impacting the time to market.

Problems of this nature can take a week or more to troubleshoot, and several weeks to adjust priorities across the system, retest, and refine. If these problems can't be solved effectively, product scalability is limited.

This is largely due to the fact that there's no effective way to “budget” CPU use across these groups. Thread priorities provide a way to ensure that critical tasks run, but don't provide guaranteed CPU time for important, noncritical tasks, which can be starved in normal operations. In addition, a common approach to establishing thread priorities is difficult to scale across a large development team.

Adaptive partitioning using the thread scheduler lets architects maintain a reserve of resources for emergency purposes, such as a disaster-recovery system, or a field-debugging shell, and define high-level CPU budgets per subsystem, allowing development groups to implement their own priority schemes and optimizations within a given budget. This approach lets design groups develop subsystems independently and eases the integration effort. The net effect is to improve time-to-market and facilitate product scaling.

Providing security

Many systems are vulnerable to Denial of Service (DOS) attacks. For example, a malicious user could bombard a system with requests that need to be processed by one process. When under attack, this process overloads the CPU and effectively starves the rest of the system.

Without adaptive partitioning, a DOS attack on one process can starve other critical functions.

Some systems try to overcome this problem by implementing a monitor process that detects CPU utilization and invokes corrective actions when it deems that a process is using too much CPU. This approach has a number of drawbacks, including:

• Response time is typically slow.
• This approach caps the CPU usage in times when legitimate processing is required.
• It isn't infallible or reliable; it depends on appropriate thread priorities to ensure that the monitor process obtains sufficient CPU time.

The thread scheduler can solve this problem. The thread scheduler can provide separate budgets to the system's various functions. This ensures that the system always has some CPU capacity for important tasks. Threads can change their own priorities, which can be a security hole, but you can configure the thread scheduler to prevent code running in a partition from changing its own budget.

With scheduler partitions, a DOS attack is contained.

Since adaptive partitioning can allocate any unused CPU time to partitions that require it, it doesn't unnecessarily cap control-plane activity when there's a legitimate need for increased processing.

Debugging

Adaptive partitioning can even make debugging an embedded system easier—during development or deployment—by providing an “emergency door” into the system.

Simply create a partition that you can run diagnostic tools in; if you don't need to use the partition, the thread scheduler allocates its budget among the other partitions. This provides you with access to the system without compromising its performance. For more information, see the Testing and Debugging chapter of the Adaptive Partitioning User's Guide.

Adaptive partitioning thread scheduler

The thread scheduler is an optional scheduler that lets you guarantee minimum percentages of the CPU's throughput to groups of threads, processes, or applications. The percentage of the CPU time allotted to a partition is called a budget.

The thread scheduler has been designed on top of the core QNX Neutrino architecture primarily to solve these problems in embedded systems design:

• guaranteeing a specified minimum share of CPU time when the system is overloaded
• preventing unimportant or untrusted applications from monopolizing the system

For more information, see the Adaptive Partitioning User's Guide.