在实时程序的应用场景中，为了代码运行的低延迟和确定性，针对栈区，也是有一定的优化小技巧的。

# 栈预热
程序可能因为分配栈区内存的响应延迟导致的性能颠簸，从而导致实时任务的延迟抖动。

针对此问题，在实时程序关键任务未运行之前，提前访问栈区地址空间，从而触发缺页异常，分配物理页面，并函数返回。然后当实时程序在运行关键任务的函数调用和栈区变量分配时，由于之前栈区已经被预热过了，再次访问时，无需触发缺页异常，也就不会出现因为分配内存导致的性能颠簸了。

# 实施栈预热
对于栈区内存，预热的办法可以提供一个栈预热函数，函数内完成如下三个步骤
1. 分配一个很大的临时变量，占领栈区
2. 访问这个临时变量，触发页面申请
3. 函数返回

经过这三步，相当于强行访问了栈区的内存，提前进行了内存申请，此时如果后面的函数为实时程序关键任务，那么其再进行函数调用或者栈区变量访问时，不会触发缺页异常。从而不会产生性能颠簸。

# 测试程序
我们编写一个测试程序验证和说明这一点。
```
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

#define ITERATIONS 10000
#define STACK_SIZE 1024 * 1024

static long long get_time() {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ((long long)ts.tv_sec * 1000000000LL + (long long)(ts.tv_nsec)) / 1000;
}

void test_stack_prefetch() {
    char stack[STACK_SIZE];
    memset(stack, 0x0, STACK_SIZE);
    return ;
}

void test_stack(int use_warmup) {
    double times[ITERATIONS];
    double start, elapsed;
    char stack[STACK_SIZE];

    if(use_warmup)
        test_stack_prefetch();

    for (int i = 0; i < ITERATIONS; i++) {
        start = get_time();
        test_stack_prefetch();
        times[i] = get_time() - start;
    }

    double max, min;
    max = min = times[0];
    for (int i = 1; i < ITERATIONS; i++) {
        if (times[i] < min) min = times[i]; // Min
        if (times[i] > max) max = times[i]; // Max
    }

    printf("  Min time: %.2f us\n", min);
    printf("  Max time: %.2f us\n\n", max);

    return ;
}

int main(int argc, char *argv[]) {
    int use_warmup = 0;

    if (argc == 2) {
        use_warmup = atoi(argv[1]);;
    }

    printf("Stack size: %d bytes, Iterations: %d Warmup: %d\n", STACK_SIZE, ITERATIONS, use_warmup);

    test_stack(use_warmup);

    return 0;
}
```
这里函数test_stack_prefetch通过stack申请了STACK_SIZE大小的局部变量，这个变量存放在栈区，用来实施和模拟栈区的使用。

然后再通过memset将其全部设置为0，相当于全部访问了STACK_SIZE内的栈区内存，触发了缺页异常。

最后函数返回。

经过此函数的运行，从test_stack_prefetch函数的开始栈区sp 到 stack 变量地址 加上 STACK_SIZE 大小的栈区，都被访问过。

因为 test_stack_prefetch 函数会返回，栈指针会缩小，下次运行函数时，其访问的栈区地址 在上述 栈区地址范围内，因为上述 栈区地址已经提前访问过了，所以代码不会因为内存产生性能颠簸。

下面查看运行日志
```
# ./stack_prefetch 0
Stack size: 1048576 bytes, Iterations: 2 Warmup: 0
  Min time: 79.00 us
  Max time: 692.00 us
```
可以看到，对于申请1M的栈空间，如果不经过预热，那么首次申请的时间是 692 us。
如果使用预热，那么根据上面的日志分析，应该是100us左右，下面运行验证
```
# ./stack_prefetch 1
Stack size: 1048576 bytes, Iterations: 2 Warmup: 1
  Min time: 102.00 us
  Max time: 103.00 us
```

# 总结
至此，我们通过这么一个小技巧，可以保证在实时程序处理关键任务时，不会因为栈的内存分配问题导致实时任务抖动。此方法通常可以用于在实时任务运行之前进行预热，或者定期对整个栈区范围进行定期预热。


栈预热优化实时程序

配置glibc优化实时程序

mlock系统调用可以将进程的虚拟内存页面锁定在物理内存中，这个锁定会触发两个事情

* 第一个事情就是立马为内存区域申请物理内存。  
* 第二个事情就是设置标志位，将其放到不可回收的lru链表，防止swap。

# mlock实现原理
mlock的调用意味着，后续代码操作这块内存，无需触发缺页异常，并且如果系统在运行过程中，即使触发主动或被动内存回收，都不会迁移这段内存到swap空间上。从而保证了实时程序在内存访问时得低时延和高可靠性。下面简单理解一下上述两个步骤的具体实现。
## 主动分配内存，避免缺页异常
当系统调用mlock后，该函数通过系统调用下发到内核，其代码如下
```
SYSCALL_DEFINE2(mlock, unsigned long, start, size_t, len)
{
    return do_mlock(start, len, VM_LOCKED);
}
```
do_mlock函数进行参数检查和权限检查，并检查RLIMIT_MEMLOCK的值，如一切正常，则调用`__mm_populate`进行内存的填充。
```
static __must_check int do_mlock(unsigned long start, size_t len, vm_flags_t flags)
{
......
    error = __mm_populate(start, len, 0);
    if (error)
        return __mlock_posix_error_return(error);
......
    return 0;
}
```
`__mm_populate` 会通过`find_vma`找到start到start+len的vma区域，然后调用 `populate_vma_page_range` 来实际分配内存
```
int __mm_populate(unsigned long start, unsigned long len, int ignore_errors)
{
......
    for (nstart = start; nstart < end; nstart = nend) {
        if (!locked) {
            locked = 1;
            down_read(&mm->mmap_sem);
            vma = find_vma(mm, nstart);
        } else if (nstart >= vma->vm_end)
            vma = vma->vm_next;
......
        ret = populate_vma_page_range(vma, nstart, nend, &locked);
    }
    nend = nstart + ret * PAGE_SIZE;
}
```
`populate_vma_page_range` 会根据传入的vma结构体和页面的起始地址和结束地址，设置页面属性为FOLL_TOUCH(标记已访问)，FOLL_POPULATE(触发缺页异常)，FOLL_MLOCK(锁定防止swap)，最终调用页面分配函数`__get_user_pages`。
```
long populate_vma_page_range(struct vm_area_struct *vma,
        unsigned long start, unsigned long end, int *nonblocking)
{
......
gup_flags = FOLL_TOUCH | FOLL_POPULATE | FOLL_MLOCK;
......
return __get_user_pages(current, mm, start, nr_pages, gup_flags,
                NULL, NULL, nonblocking);
}
```
这里`__get_user_pages`是内核默认页面申请函数，本文不讨论内存申请原理，故简化其调用流程如下

`__get_user_pages ---> faultin_page ---> handle_mm_fault`

至此，我们可以清楚的了解了mlock在设置了之后，会立马触发物理页面的分配。这样在后续使用这些页面的时候，无需再触发缺页异常，。

## 防止swap
下面继续讨论mlock的第二个事情，防止swap换出。
在讨论swap换出时，我们需要了解内核内存的回收机制，如下

![image.png](/static/img/3a3d0fb0e91af9712e46ad213fb16ed7.image.webp)

可以知道，内核的内存回收主要回收两个lru list，一个是active list，一个是inactive list。下面逐一介绍。  

### 活跃链表
首先是shrink_active_list，其主要目的是处理活跃的lru链表，然后让其加入非活跃链表，主要通过反向映射机制查找这个物理页面对应的所有vma，然后确定mm flag，如果设置VM_LOCKED的vma 则退出反向映射，这样就不会被rmap统计上。

其代码如下，首先从shrink_active_list开始统计并回收active 链表的内存，如下
```
static void shrink_active_list(unsigned long nr_to_scan,
                   struct lruvec *lruvec,
                   struct scan_control *sc,
                   enum lru_list lru)
{
......
    while (!list_empty(&l_hold)) {
      if (page_referenced(page, 0, sc->target_mem_cgroup,
                    &vm_flags)) {
        list_add(&page->lru, &l_active);
        continue;
      }
    list_add(&page->lru, &l_inactive);
    }
......
}
```
可以看到，shrink_active_list的作用是将一些可以迁移的页面移动到inactive 链表上，这样尽可能的回收一些页面来释放内存，此时我们进一步关注page_referenced的实现，如下
```
int page_referenced(struct page *page,
            int is_locked,
            struct mem_cgroup *memcg,
            unsigned long *vm_flags)
{
......
    struct rmap_walk_control rwc = {
        .rmap_one = page_referenced_one,
        .arg = (void *)&pra,
        .anon_lock = page_lock_anon_vma_read,
    };
    rmap_walk(page, &rwc);
......
    return pra.referenced;
}
```
这里page_referenced使用了rmap机制来查询每个页面的vma结构，其rmap的代码调用路径如下
```
.rmap_one = page_referenced_one,
  rmap_walk(page, &rwc); 
    rmap_walk_ksm/rmap_walk_anon/rmap_walk_file
      rwc->rmap_one(page, vma, address, rwc->arg) == page_referenced_one
        page_vma_mapped_walk
```
此时我们关注page_referenced_one函数的处理，它会直接退出反向映射的统计，如下
```
static bool page_referenced_one(struct page *page, struct vm_area_struct *vma,
            unsigned long address, void *arg)
{
......
    while (page_vma_mapped_walk(&pvmw)) {
        address = pvmw.address;

        if (vma->vm_flags & VM_LOCKED) {
            page_vma_mapped_walk_done(&pvmw);
            pra->vm_flags |= VM_LOCKED;
            return false; /* To break the loop */
        }
    }
......
}
```
可以看到，在处理活跃链表的时候，如果带有VM_LOCKED的vma，则直接退出反向映射，不再将其从活跃链表迁移到非活跃链表上。

### 非活跃链表
接下来看非活跃链表上关于VM_LOCKED的页面处理方式。也就是`shrink_inactive_list`函数，其做法就是从unactive 链表上取出一些 page 出来，然后尝试进行 回收，其代码如下
```
static noinline_for_stack unsigned long
shrink_inactive_list(unsigned long nr_to_scan, struct lruvec *lruvec,
             struct scan_control *sc, enum lru_list lru)
{
......
    nr_taken = isolate_lru_pages(nr_to_scan, lruvec, &page_list,
                     &nr_scanned, sc, lru);
    nr_reclaimed = shrink_page_list(&page_list, pgdat, sc, 0,
                &stat, false);
    free_unref_page_list(&page_list);
......
}
```
这里`shrink_page_list` 会调用 `page_check_references` 继而调用 `page_referenced` 进行rmap检查统计pte的引用，并同时检查VM_LOCKED。`page_check_references`的代码如下
```
static enum page_references page_check_references(struct page *page,
                          struct scan_control *sc)
{
    referenced_ptes = page_referenced(page, 1, sc->target_mem_cgroup, &vm_flags);
    if (vm_flags & VM_LOCKED)
      return PAGEREF_RECLAIM;
......
}
```
page_referenced 上面分析过了，会通过rmap机制找到每个vma，然后检查到有VM_LOCKED则跳出不统计。其简单流程如下
```
page_referenced ---> rmap_walk ---> rmap_walk_xxx ---> page_referenced_one
```
在`page_referenced` 之后，如果判断vma设置了VM_LOCKED标志位，则直接返回PAGEREF_RECLAIM，会由`try_to_unmap` 将其移动到 unevictable 链表

函数 `shrink_page_list` 会在 最后调用 `try_to_unmap` 

下面先跟踪`try_to_unmap`的代码路径。
```
try_to_unmap ---> rmap_walk ---> rmap_walk_xxx ---> try_to_unmap_one
```
在 try_to_unmap_one 中会判断VM_LOCKED，然后调用mlock_vma_page，代码如下
```
static bool try_to_unmap_one(struct page *page, struct vm_area_struct *vma,
             unsigned long address, void *arg)
{
......
if (vma->vm_flags & VM_LOCKED) {
                /* PTE-mapped THP are never mlocked */
                if (!PageTransCompound(page)) {
                    /*
                     * Holding pte lock, we do *not* need
                     * mmap_sem here
                     */
                    mlock_vma_page(page);
                }
ret = false;
                page_vma_mapped_walk_done(&pvmw);
                break;
            }
        }
......
}
```
mlock_vma_page 会设置page的PG_mlocked标志，然后隔离页面后将其放入不可移动链表，其代码如下
```
void mlock_vma_page(struct page *page)
{
    if (!TestSetPageMlocked(page)) {
        count_vm_event(UNEVICTABLE_PGMLOCKED);
        if (!isolate_lru_page(page))
            putback_lru_page(page);
    }
}
```
到这里，mlock的第二个作用也介绍清楚了，操作系统在进行页面回收的过程中，分为两大部分，`shrink_active_list`和`shrink_inactive_list`。如果页面带有给VM_LOCKED标志，那么会主动退出回收流程，并将其加入到不可移动链表上，这样后续的所有swap流程都不会处理带有VM_LOCKED标志的页面。从而避免了内存回收。

# 测试mlock
下面通过测试程序来验证通过mlock加强实时程序的高确定性问题。
```
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <time.h>
#include <math.h>

#define ARRAY_SIZE (1024 * 1024 * 100)
#define ITERATIONS 1000
#define ACCESS_COUNT 10000

int* prepare_memory(int use_mlock) {
    int *array = (int *)malloc(ARRAY_SIZE * sizeof(int));
    if (!array) {
        printf("malloc failed");
        exit(EXIT_FAILURE);
    }

    int mlock_success = 0;

    if (use_mlock) {
        if (mlock(array, ARRAY_SIZE * sizeof(int)) != 0) {
            printf("Warning: mlock failed (may not be root or RLIMIT exceeded)\n");
        } else {
            mlock_success = 1;
        }
    }

    return array;
}

double run_access_test(int *array) {
    struct timespec start, end;

    clock_gettime(CLOCK_MONOTONIC, &start);

    for (int i = 0; i < ACCESS_COUNT; i++) {
        array[(i * 1024) % ARRAY_SIZE] += i;
    }

    clock_gettime(CLOCK_MONOTONIC, &end);

    long long elapsed_ns = (end.tv_sec - start.tv_sec) * 1000000000LL +
                           (end.tv_nsec - start.tv_nsec);
    return (double)elapsed_ns / 1000.0;
}
void calculate_stats(double *times, int count, double *min, double *max, double *avg, double *stddev) {
    *min = times[0];
    *max = times[0];
    double sum = 0.0;

    for (int i = 0; i < count; i++) {
        sum += times[i];
        if (times[i] < *min) *min = times[i];
        if (times[i] > *max) *max = times[i];
    }

    *avg = sum / count;

    double variance_sum = 0.0;
    for (int i = 0; i < count; i++) {
        variance_sum += pow(times[i] - *avg, 2);
    }
    *stddev = sqrt(variance_sum / count);
}

int main() {
    double times_mlock[ITERATIONS];
    double times_nomlock[ITERATIONS];

#define MLOCK 1
#define NOMLOCK 0
    int *array_mlock = prepare_memory(MLOCK);
    int *array_nomlock = prepare_memory(NOMLOCK);

    for (int i = 0; i < ITERATIONS; i++) {
        times_mlock[i] = run_access_test(array_mlock);
    }

    for (int i = 0; i < ITERATIONS; i++) {
        times_nomlock[i] = run_access_test(array_nomlock);
    }

    free(array_mlock);
    free(array_nomlock);

    double min_mlock, max_mlock, avg_mlock, stddev_mlock;
    double min_nomlock, max_nomlock, avg_nomlock, stddev_nomlock;

    calculate_stats(times_mlock, ITERATIONS, &min_mlock, &max_mlock, &avg_mlock, &stddev_mlock);
    calculate_stats(times_nomlock, ITERATIONS, &min_nomlock, &max_nomlock, &avg_nomlock, &stddev_nomlock);

    printf("With mlock:\n");
    printf("  Min: %.2f μs | Max: %.2f μs | Avg: %.2f μs | StdDev: %.2f μs\n",
           min_mlock, max_mlock, avg_mlock, stddev_mlock);
    printf("Without mlock:\n");
    printf("  Min: %.2f μs | Max: %.2f μs | Avg: %.2f μs | StdDev: %.2f μs\n",
           min_nomlock, max_nomlock, avg_nomlock, stddev_nomlock);

    return 0;
}
```
将代码命令为mlock_test.c，编译后运行如下
```
gcc mlock_test.c -lm -o mlock_test
./mlock_test
With mlock:
  Min: 436.62 μs | Max: 534.95 μs | Avg: 509.69 μs | StdDev: 22.37 μs
Without mlock:
  Min: 491.31 μs | Max: 55170.11 μs | Avg: 585.05 μs | StdDev: 1410.62 μs
```

可以看到，通过测试，使用mlock的内存区域，Min和Max的数组访问时延非常稳定，其标准差非常小，而不使用mlock的内存区域，因为收到缺页异常和交换内存的影响，其最大延迟可以达到55170.11us，导致其标准差非常大。

# 总结
通过分析内核的实现，可以了解了mlock的基本原理，再通过一个测试程序，清楚的了解了mlock对实时程序的影响。  
根据上述信息，可以发现使用mlock能够极大的提高程序的运行确定性，这对实时程序而言是非常有意义的。

处理mlock，通过madvise也能够辅助的提供程序的运行性能，这个有空分享一下。





使用mlock优化实时程序

之前通过sdkmanager已经可以烧录内核并启动了，但是进入系统中后发现，浏览器chromium和firefox都不可用。本文以此实际问题作为引子，介绍一下nano的内核编译工作。同时，本文章提供了解决jetson系列无法使用浏览器的解决办法

# 具体问题
我的主板当前烧录的是JetPack 6.2.1，其系统是基于ubuntu2204的，所以第一步我的想法是安装chromium和firefox，如下
```
apt install chromium firefox
```
但是，安装完成之后并不像其他发行版本一样，能够直接运行。其解决方案如下
## snap
默认的snap存在问题，需要如下修复
```
snap download snapd --revision=24724
sudo snap ack snapd_24724.assert
sudo snap install snapd_24724.snap
sudo sudo snap refresh --hold snapd
```
这里给出的方案是回退了snap的版本
## 内核配置
对于此问题，需要打开两个配置，如下
```
CONFIG_SQUASHFS_XATTR=y
CONFIG_SECURITY_APPARMOR=y
```
完成上述两个步骤之后，jetson系列的板子就能正常使用浏览器开发咯。 下面开始介绍本文的目标：如何定制修改一个orin内核
# 修改内核
我们拿到了具体的问题，就是需要给内核添加两个配置。接下来介绍如何修改内核
## 安装依赖
```
apt install git build-essential bc flex bison libssl-dev zstd
```
## 安装交叉编译工具链
打开如下网址
> https://developer.nvidia.com/embedded/jetson-linux-r3644

在tool栏找到bootlin toolchain gcc 并下载`aarch64--glibc--stable-2022.08-1.tar.bz2`，如下

![image.png](/static/img/5e6b5bd7499300847307225bf063bf8c.image.webp)

下载到本地之后，解压并设置path，如下
```
tar xvjf aarch64--glibc--stable-2022.08-1.tar.bz2
export CROSS_COMPILE=/home/kylin/nvidia/sdk/JetPack_6.2.1_Linux_JETSON_AGX_ORIN_TARGETS/toolchain/aarch64--glibc--stable-2022.08-1/bin/aarch64-buildroot-linux-gnu-
```
## 下载内核源码
在sdk目录有一个`Linux_for_Tegra/source/source_sync.sh`脚本，其就是git clone代码，我们在运行之前，需要找到自己的release版本号，从如下网址查看
> https://docs.nvidia.com/jetson/archives/

我们找到对应jetpack 6.2.1 版本的git branch 是jetson_36.4.4。

所以可以直接运行如下拉取内核代码
```
./source_sync.sh -k -t jetson_36.4.4
```
值得注意的是，这里每运行一次会给你新建一个当前时间戳的分支，所以建议只拉一次，后面每次同步的时候再运行即可。

如果上述方法找自己想要的分支不方便，那么直接从 git 仓库里面翻是最方便最直接的。稍微阅读一下`source_sync.sh` 可以发现如下
```
:kernel/kernel-jammy-src:nv-tegra.nvidia.com/3rdparty/canonical/linux-jammy.git:
```
根据此，可以推理出nvidia的git repo地址在如下
```
https://nv-tegra.nvidia.com/r/admin/repos/3rdparty/canonical/linux-jammy
```
我们寻找tags，如下图

![image.png](/static/img/74b48728e61db17b3e37f75979dbfb21.image.webp)

选择自己想要的分支即可。

这里下载内核源码需要点时间，等内核下载完毕之后，执行如下编译构建

## 编译内核
```
make -C kernel
```
如果需要安装到根文件系统中，则指定rootfs位置，make install即可，如下
```
export INSTALL_MOD_PATH=/home/kylin/nvidia/sdk/JetPack_6.2.1_Linux_JETSON_AGX_ORIN_TARGETS/Linux_for_Tegra/rootfs/
make install -C kernel
cp kernel/kernel-jammy-src/arch/arm64/boot/Image \
  /home/kylin/nvidia/sdk/JetPack_6.2.1_Linux_JETSON_AGX_ORIN_TARGETS/Linux_for_Tegra/kernel/Image
```
这里稍微观察一下安装的内容，可以发现其安装如下
```
# find ../../out/ -maxdepth 3
../../out/
../../out/boot
../../out/boot/Image
../../out/lib
../../out/lib/modules
../../out/lib/modules/5.15.148-tegra
```
这里了解linux发行版的就很熟悉了，安装了module和Image。这里更新的方式可以不用更新rootfs的方式了，直接复制文件覆盖即可。可以如下
```
scp kernel/kernel-jammy-src/arch/arm64/boot/Image root@192.168.55.1:/boot/
```
同理，更新ko也一样。

## 修改配置
我的目的是增加
```
CONFIG_SQUASHFS_XATTR=y
CONFIG_SECURITY_APPARMOR=y
```
nvidia的defconfig由如下变量指定
```
KERNEL_DEF_CONFIG="defconfig"
```
故直接修改
```
vim kernel/kernel-jammy-src/arch/arm64/configs/defconfig
```
修改完毕之后，编译，安装即可
```
make install -C kernel
scp kernel/kernel-jammy-src/arch/arm64/boot/Image root@192.168.55.1:/boot/
```
重启，jetson nano上的浏览器可以正常启动了

# 编译模块
编译模块的命令也是通用的，如下
```
export KERNEL_HEADERS=$PWD/kernel/kernel-jammy-src
make modules
```
安装如下
```
export INSTALL_MOD_PATH=/home/kylin/nvidia/sdk/JetPack_6.2.1_Linux_JETSON_AGX_ORIN_TARGETS/Linux_for_Tegra/rootfs/
make modules_install
```
安装完成之后，可以将其更新到initrd.img中。  如下运行
```
cd ../ && ./tools/l4t_update_initrd.sh
```
稍微翻阅一下代码，其实可以如下操作更方便
```
scp -r ../../out/* root@192.168.55.1:/
ssh root@192.168.55.1
nv-update-initrd
```

# 参考链接
> https://forums.developer.nvidia.com/t/chromium-other-browsers-not-working-after-flashing-or-updating-heres-why-and-quick-fix/338891
> https://docs.nvidia.com/jetson/archives/r36.4.4/DeveloperGuide/SD/Kernel/KernelCustomization.html

# 总结
这里初步的修改了jetson的内核，目前看下来整体配置用起来挺舒服，开发方式都是很通用的内容。

Jetson-Orin-Nano-Super(2)修改内核

在实时系统中，经常要讨论优先级反转问题带来的影响，本文主要讨论这个。
# 什么是优先级反转问题
当两个进程在竞争同一个共享资源时，高优先级的任务可能因为低优先级任务正在持有此共享资源从而放弃CPU，这种情况下，必须等到低优先级先运行，而高优先级等到低优先级释放此共享资源之后才得以运行，这种情况下说发生了优先级反转问题。  

在其他非实时要求的系统中，如通用Linux内核，这种优先级反转经常发生，因为任务总会得到响应，所以它并不会视为对系统有害的。

# 有界优先级反转和无界优先级反转
在讨论优先级反转时，我们需要先了解有界优先级反转(通常无害)和无界优先级反转(可能有害)两个问题。
## 解释含义
场景一：  
> 当系统存在两个优先级任务L和H，低优先级任务L获取了共享资源锁，而高优先级任务H在执行时必须被迫等待任务L完成关键任务并释放共享资源锁之后才能得以运行。

此时高优先级任务H的最坏等待时间实际上是等于低优先级任务L的持有锁时间。
* 高优先级任务H最坏等待时间 = 低优先级任务L的持有锁时间

因为只要任务L在有限的时间完成，这种有限优先级反转其实不会影响和损害应用程序。我们将这种情况称之为`有界优先级反转`。

场景二：  
> 当系统存在两个优先级任务L和H，任务L获取了共享资源的锁，而任务H必须等到任务L释放锁才得以运行，假设此时出现优先级高于任务L并低于任务H的任务M，它能够有效的抢占任务L，使得任务M运行，直到它放弃对CPU的控制。只有当任务M完成任务时间后，任务L才能得以运行持有锁内的任务。而当任务L完成持有锁内的所有任务，任务H才得以条件获取资源并恢复执行。

此时任务H的最坏等待时间实际上是等于任务M抢占L的运行时间与任务L的持有锁时间之和。
* 高优先级任务H最坏等待时间 = 低优先级任务L的持有锁时间 + 中优先级任务M抢占L后运行的时间

这里可能任务M可能会无限期运行，也有可能会有多个任务M一直抢占任务L的运行，从而导致任务L和任务H都没有机会恢复运行。那么此时任务H的最坏等待时间是不确定的，这种情况下我们称之为`无界优先级反转`。  

在具有实时性要求的系统中，有界优先级反转通常不会产生任何影响，因为其执行时间是固定的，但无界优先级反转可能会给实时任务带来致命错误。

所以需要采取一定的措施解决无界优先级反转问题。

## 无界优先级反转无害举例
下面举例说明无害的无界优先级反转问题，此例子中可能发生在通用linux中，所以是不会产生实际危害的：

![image.png](/static/img/917a0aa57a7e30a39dc3b944c5531cd0.image.webp)

* T0时刻，优先级为10的Task10开始运行；
* T1时刻，Task10申请并获得了锁M，进入临界区；
* T2时刻，优先级为90的任务Task90抢占Task10，开始运行；
* T3时刻，Task90也要申请锁M，准备进入临界区操作，但由于该锁被Task10所持有，Task90被迫放弃CPU，Task10继续运行；
* T4时刻，优先级为50的任务Task50抢占了Task10的CPU，开始运行，此时的状况是，Task90在等Task10，而Task10在等Task50；
* T5时刻，Task50完成任务，释放CPU，Task10继续运行；
* T6时刻，Task10释放锁M，离开临界区，Task90立刻抢占，继续运行。

可以看到，Task90和Task10造成了资源竞争，而Task90与Task50没有竞争关系，但Task50和Task10在这种情况下比Task90优先得到调度，其最坏影响时间是Task10的持有锁时间加上Task50完成抢占的任务时间，因为Task50的任务实际上是不确定的，这就发生了无界优先级反转问题，但如果Task50没有明确的实时确定性要求(deadline)，那么此时的优先级反转问题是无害的，因为它必将完成，只是推迟。

## 无界优先级反转有害举例
这里再举一个例子，其无界优先级反转导致实时任务错过了deadline，这种情况在实时系统中是有害的。

![image.png](/static/img/b51e28e629fcd1a37815c76854777dcf.image.webp)

如上图所示，条件如下：
1. 优先级排序如下  T2 < T1 < T0
2. T0,T1,T2都是实时任务，其确定性由Deadline决定  

其运行情况如下：
* t1时刻，任务T2得以运行，此时它获取共享资源锁
* t2时刻，任务T0得以运行，但是因为任务T2持有共享资源锁，所以阻塞
* t4时刻，任务T2恢复执行
* t5时刻，任务T1因为其优先级高于T2，抢占任务T2，任务T1开始运行。
* t9时刻，任务T0错过了截止时间
* t11时刻，任务T1完成，但此时任务T0已经错过了截止时间，任务T2恢复执行
* t12时刻，任务T2执行完成，释放共享资源锁，任务T0得以执行

可以看到，这种场景下，高优先级任务T0出现了延期执行(错过deadline)，而任务T0本身是实时任务，它需要具备确定性的特点。延期执行明显违反了实时任务的确定性特点，所以可能会给实际任务带来致命影响，假设是一次导弹的发射，那么可能就炸膛了~

# 优先级继承
优先级继承是解决无界优先级反转的一种办法，它的基本思路是：
> 当低优先级任务获取共享资源后，如果高优先级任务请求同一个共享资源时，此时动态的将低优先级任务的优先级提升到此高优先级任务优先级上。这样，低优先级任务就不容易被其他任务抢占，从而运行持有共享资源的关键部分，直到运行完成并释放资源。当共享资源得到释放之后，低优先级任务会自动回到原始低优先级上，从而系统正常运行其他高优先级任务。

举一个例子，它通过优先级继承解决了优先级反转问题：

![image.png](/static/img/472079574d6edb0042f47f5341753d39.image.webp)

如上图所示，其运行情况如下：
* t1时刻，任务T2得以运行，此时它获取共享资源锁
* t2时刻，任务T0得以运行，但是因为任务T2持有共享资源锁，所以阻塞
* t4时刻，任务T2恢复执行，此时会继承T0的优先级
* t5时刻，任务T1因为其优先级低于此时任务T2，不能抢占任务T2，任务T2继续运行。
* t6时刻，任务T2完成运行，并释放资源，并恢复优先级为原始优先级，此时任务T0优先级最高，得以执行
* t9时刻，任务T0得以在截止时间内完成，此时任务T1得以运行

可以看到，这种场景下，任务T2在恢复运行时将优先级继承了同样持有锁的高优先级任务T0，使得任务T2能够优于任务T1运行，从而快速释放共享资源，保证了T0任务在截止时间之前完成。它解决了无界优先级反转导致高优先级错过截止时间的问题。

但是没有这么简单，如果存在嵌套的共享资源锁，那么优先级继承会明显的增加高优先级的等待时间，如果等待时间过长，或截止时间太短。就仍会导致实时任务错过截止时间，从而破坏了实时任务的确定性。

下面举一个例子，它表述了共享资源嵌套导致实时任务仍错过了截止时间的问题：

![image.png](/static/img/51490ab7663276bcaafd70a118af8c29.image.webp)

如上图所示，其运行情况如下：
* t1时刻，任务T2得以运行，此时它获取共享资源锁2
* t2时刻，任务T1得以运行，它抢占了任务T2，此时T1获取了共享资源锁1
* t3时刻，任务T0得以运行，但是其依赖共享资源锁1，但任务T1持有共享资源锁1，所以任务T1继承任务T0的优先级。同时，任务T1依赖共享资源锁2，但任务T2持有共享资源锁2，所以任务T2继承了任务T0的优先级。此时任务T0，T1，T2的优先级都是任务T0的最高优先级。因为资源嵌套问题，任务T2得到执行
* t4时刻，任务T2完成持有锁2的关键任务，释放共享资源锁2，此时任为任务T2优先级返回原始优先级，同时任务T1因共享资源锁2释放，得以占用共享资源锁2执行持有锁2的关键任务
* t6时刻，任务T1完成持有锁2的关键任务，释放共享资源锁2，此时因为任务T0需要等待共享资源锁1，而任务T1正持有共享资源1，故任务T1继续运行。
* t7时刻，任务T1完成持有锁1的关键任务，释放共享资源1，此时任务T1优先级返回原始优先级，同时任务T0因共享资源锁1释放，得以占用共享资源锁1执行持有锁1的关键任务
* t11时刻，任务T0的截止时间到达，但任务T0正在运行
* t13时刻，任务T0完成，但已经错过了截止时间

可以看到，这种场景下，任务T2占用锁2，任务T1占用锁1，而任务T0需要等待锁1才能运行，所以需要等待任务T1释放锁1，而任务T1需要等待锁2才能运行，所以需要等待任务T2释放锁2。此时，即使通过优先级继承能够缓解优先级反转的等待时间，但最后任务T0仍错过了截止时间。

所以，通过这种场景可以发现，优先级继承并不能完全解决优先级反转导致的实时任务被破坏的问题。

# 优先级天花板
为了解决上述因为嵌套的资源锁问题导致实时任务不确定的问题，另一种解决无界优先级反转的办法出现了，就是优先级天花板。其原理是先为每个共享资源预设优先级上限，当任务获取这个共享资源时，直接将该任务设置为优先级上限，从而确保拥有共享资源的任务不会被尝试访问同一资源的任何其他任务抢占，当提升的任务释放共享资源时，又将其恢复成原始优先级。这种方法能够很好的解决共享资源嵌套时出现的破坏实时任务确定性的问题。

下面举一个例子，它表述了优先级天花板良好处理共享资源嵌套的场景：

![image.png](/static/img/b14e058797276658234713645ae3e284.image.webp)

如上图所示，其运行情况如下：
* t1时刻，任务T2得以运行，此时它获取共享资源锁2，此时任务T2的优先级提升到资源的上限，即大于任务T1的优先级
* t2时刻，原计划运行的任务T1被任务T2阻止，任务T2继续运行，任务T1阻塞等待
* t3时刻，任务T0得以运行，此时它获取共享资源锁1，并持续运行直到释放资源锁1
* t9时刻，任务T1得以运行，此时共享资源锁1没有被占用，程序得以运行，同样的，共享资源锁2也没有被占用，程序同样得以运行

可以看到，这种场景下，任务T2在获取共享资源锁2的时候，立马改变优先级为最高，此时没有其他任务可以阻塞它运行，同样的任务T0在获取共享资源锁1的时候，也立马改变优先级为最高，此时没有其他任务阻塞它运行。其最终结果是任务T0不会错过其截止时间。

优先级天花板良好的解决了共享资源嵌套导致的破坏实时任务确定性的问题。

# 优先级继承和优先级天花板的优劣势
根据上面的分析，我们知道优先级天花板很好的解决共享资源嵌套问题，但其也是存在缺点的，那么它有哪些缺点呢。
## 优先级天花板的缺点
1. 无争用情况下开销大  

任务在获取共享资源锁的时候，会立马提升优先级为预设最高值，也就意味着，系统中即使是没有争用的情况下，也会错误的将任务优先级提升最高，其对整体系统来说，开销很大。  

2. 阻塞中等优先级任务运行  

立马提升优先级为预设最高值，那么意味着系统中低于此优先级的大量中等优先级任务会被错误的阻塞，从而带来整体性能的下降。

3. 平均情况响应时间变差  

每次获取共享资源时，都必须立即将该任务设置为优先级上限，而每次释放资源时，都必须立即将该任务降低至原始优先级。这种行为的开销会导致所有相关任务响应时间变差。

可以看到，如果使用优先级天花板协议，那么就将承受共享资源无争用时开销偏大(1)， 系统常规优先级任务整体性能偏低(2)， 所有需要访问共享资源的任务响应时间集体变差 (3) 三个性能问题。

## 优先级继承的缺点
那么我们如果选择优先级继承解决优先级反转问题，需要注意什么呢？

1. 上下文切换时间可能大于关键任务执行时间

因为优先级继承会将低优先级任务继承高优先级任务的优先级，如果在极端场景下，假设高优先级任务整体优先级并不高，而系统负载较高，那么就容易出现上下文切换时间大于关键任务执行时间的问题。此时上下文切换时间在极端情况下的优化至关重要。

2. 共享资源嵌套问题

优先级继承的共享资源嵌套问题无法从代码设计上解决，因为其最坏情况下的耗时比优先级天花板最坏情况下耗时差很多。同样的，优先级天花板的设计可能会将资源嵌套中可能死锁的场景更容易暴露出来。所以需要程序员自行去避免此问题的出现。

由于实时系统中，应用程序在实际场景下大多数共享资源时是没有争用的，因此优先级继承协议具备常规情况下的最好性能。故它成为了PREEMPT_RT的解决优先级反转的默认策略。

# 参考文献
> Implementation and Evaluation of the
Synchronization Protocol Immediate Priority
Ceiling in PREEMPT-RT Linux

# 总结
根据上面的讨论，我们可以知道，在实时系统中，我们需要关注优先级反转问题，它有两种解决办法，优先级天花板和优先级继承，这两种解决办法都有优缺点，如果系统共享资源争用强度高，那么优先级天花板能够非常良好的应用，如果更注重性能和普遍场景下，那么优先级天花板更适用。  
但是，如果使用优先级继承，那么共享资源嵌套的问题实际上是交给了程序员自己解决。

而支持PREEMPT_RT的linux内核，默认只支持优先级继承，也就意味着，在实际场景中，如果遇到优先级继承带来的死锁，错过deadline等问题，需要有经验的程序员自行解决。

