检索调度策略和优先级

1. sched_getscheduler() 和 sched_getparam() 系统调用：
   • 这两个系统调用可以检索进程的调度策略和优先级。

1
2
3
4
5

#include <sched.h>
int sched_getscheduler(pid_t pid);
//返回调度策略，成功时返回调度策略标识符，出错时返回 -1。
int sched_getparam(pid_t pid, struct sched_param *param);
//成功时返回 0，出错时返回 -1。

调度参数和优先级获取的系统调用说明

对于这两个系统调用（sched_getscheduler 和 sched_getparam），pid 指定了要获取信息的进程 ID。如果 pid 为 0，则获取调用进程的信息。
不论是否具有特权，这两个系统调用都可用于非特权进程，以获取任何进程的信息，无需凭证。

sched_getparam() 系统调用在 sched_param 结构体中的 sched_priority 字段中返回指定进程的实时优先级。

示例用法

成功执行后，sched_getscheduler() 返回表 35-1 中列出的策略之一。
Listing 35-3 中的程序使用 sched_getscheduler() 和 sched_getparam() 来获取命令行参数指定的所有进程的调度策略和优先级。
下面的 shell 会话演示了该程序和 Listing 35-2 中的程序的使用方法：

1
2
3
4
5
6
7
8
9

$ su  
Password:  
# sleep 100 &    # 创建一个进程
[1] 2006  
# ./sched_view 2006    # 查看 sleep 进程的初始调度策略和优先级
2006: OTHER 0  
# ./sched_set f 25 2006    # 将进程 2006 切换为 SCHED_FIFO 策略，优先级为 25
# ./sched_view 2006        # 验证修改
2006: FIFO 25  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <sched.h>
#include "tlpi_hdr.h"

int main(int argc, char *argv[])
{
    int j, pol;
    struct sched_param sp;

    for (j = 1; j < argc; j++) {
        pol = sched_getscheduler(getLong(argv[j], 0, "pid")); // 获取调度策略
        if (pol == -1)
            errExit("sched_getscheduler");

        if (sched_getparam(getLong(argv[j], 0, "pid"), &sp) == -1) // 获取调度参数
            errExit("sched_getparam");

        printf("%s: %-5s %2d\n", argv[j],
            (pol == SCHED_OTHER) ? "OTHER" :     // 普通调度策略
            (pol == SCHED_RR) ? "RR" :          // 轮转调度策略
            (pol == SCHED_FIFO) ? "FIFO" :      // 先进先出调度策略
#ifdef SCHED_BATCH                            // Linux特定调度策略
            (pol == SCHED_BATCH) ? "BATCH" :
#endif
#ifdef SCHED_IDLE                             // Linux特定空闲调度策略
            (pol == SCHED_IDLE) ? "IDLE" :
#endif
            "???",                             // 未知调度策略
            sp.sched_priority);                // 优先级
    }

    exit(EXIT_SUCCESS);
}

防止实时进程锁死系统

由于 SCHED_RR 和 SCHED_FIFO 进程会抢占任何低优先级的进程（例如运行程序的shell），在开发使用这些策略的应用程序时，我们需要注意一个可能的风险：一个失控的实时进程可能会通过占用CPU导致系统锁死。为避免这种情况，可以采用以下几种方法：

• 设置一个足够低的软CPU时间资源限制（RLIMIT_CPU）
  使用 setrlimit() 函数（参考第36.3节）来设置。如果进程消耗了过多的CPU时间，将会被发送一个 SIGXCPU 信号，该信号默认会杀死进程。

• 使用 alarm() 设置报警计时器
  如果进程运行的实际时间超过了 alarm() 调用中指定的秒数，则会被发送一个 SIGALRM 信号并被终止。

• 创建一个具有高实时优先级的守护进程
  该进程可以循环运行，按照指定的间隔睡眠，然后唤醒并监视其他进程的状态。此类监视可以包括：

  • 检查每个进程的CPU时间时钟值（参考23.5.3节中的 clock_getcpuclockid() 函数）；
  • 使用 sched_getscheduler() 和 sched_getparam() 检查其调度策略和优先级。
    如果某个进程被认为行为异常，守护线程可以通过降低其优先级或发送适当的信号终止该进程来控制它。

• 从Linux内核2.6.25开始，提供了非标准的资源限制 RLIMIT_RTTIME
  该限制用于控制实时调度策略进程在单次连续运行中可以消耗的CPU时间，单位为微秒。

  • RLIMIT_RTTIME 限制了进程在不执行阻塞系统调用时所能消耗的CPU时间总量。
  • 当进程执行阻塞系统调用时，消耗的CPU时间计数会被重置为0。
  • 如果进程被更高优先级的进程抢占、由于时间片到期（SCHED_RR 进程）或调用 sched_yield()（第35.3.3节）而被调度出CPU，则计数也会被重置。
  • 如果进程达到 RLIMIT_CPU 限制，将收到一个 SIGXCPU 信号，默认情况下会杀死进程。

注意

内核2.6.25中的改动也有助于防止失控的实时进程锁死系统。有关详细信息，请参阅内核源代码文档：scheduler/sched-rt-group.txt。

防止子进程继承特权调度策略

Linux 2.6.32 引入了 SCHED_RESET_ON_FORK 作为可以在调用 sched_setscheduler() 时指定的策略值之一。
这是一个标志值，它会与表35-1中的策略之一进行位或操作。如果设置了此标志，则由此进程通过 fork() 创建的子进程不会继承特权调度策略和优先级。规则如下：

• 如果调用进程具有实时调度策略（SCHED_RR 或 SCHED_FIFO），那么子进程的调度策略将被重置为标准的时间片轮转策略，SCHED_OTHER。
• 如果进程具有负的（即较高的）nice 值，则子进程的 nice 值将被重置为0。

SCHED_RESET_ON_FORK 的作用

SCHED_RESET_ON_FORK 标志旨在用于媒体播放等应用场景。它允许创建具有实时调度策略的单个进程，而这些策略不会传递给子进程。
使用 SCHED_RESET_ON_FORK 标志可以防止通过创建多个运行在实时调度策略下的子进程来试图规避 RLIMIT_RTTIME 资源限制的 fork 炸弹攻击。

一旦为一个进程启用了 SCHED_RESET_ON_FORK 标志，只有具备特权的进程（即具有 CAP_SYS_NICE 权限的进程）可以禁用它。 此时当创建子进程时，其 reset-on-fork 标志会被禁用。

让出 CPU

一个实时进程可以通过以下两种方式主动让出 CPU：

1. 调用一个会阻塞进程的系统调用（例如，从终端执行 read()）。
2. 调用 sched_yield()。

   1 2 3

   #include <sched.h> int sched_yield(void); //成功时返回 0，出错时返回 -1。

   sched_yield() 的操作

sched_yield() 的操作非常简单。如果有其他与调用进程处于相同优先级队列中的可运行进程，则调用进程会被放到队列的末尾，并由队列头部的进程被调度使用 CPU。
如果在此优先级上没有其他可运行进程排队，那么 sched_yield() 什么都不做；调用进程将继续使用 CPU。

尽管 SUSv3 允许 sched_yield() 返回可能的错误，但在 Linux 以及许多其他 UNIX 实现中，此系统调用始终成功。
然而，可移植的应用程序仍应始终检查是否有错误返回。

对于非实时进程使用 sched_yield() 的行为是未定义的。

SCHED_RR 时间片

sched_rr_get_interval() 系统调用使我们能够确定为 SCHED_RR 进程每次被分配使用 CPU 时的时间片长度。

1
2
3

#include <sched.h>
int sched_rr_get_interval(pid_t pid, struct timespec *tp);
//成功时返回 0，出错时返回 -1。

与其他进程调度系统调用一样，pid 用于标识我们希望获取信息的进程。指定 pid 为 0 表示当前调用进程。
时间片的长度通过指向 tp 的 timespec 结构返回：

1
2
3
4

struct timespec {
    time_t tv_sec;   /* 秒 */
    long   tv_nsec;  /* 纳秒 */
};

在最近的 2.6 内核中，实时轮转调度（SCHED_RR）的时间片为 0.1 秒。

总结

默认的内核调度算法采用的是轮转时间共享策略。在这种策略下，所有进程默认可以平等地访问 CPU。不过，我们可以通过将进程的 nice 值设置为 -20（高优先级）到 +19（低优先级）的范围内的数字，从而使调度器偏爱或减少对该进程的调度。然而，即使我们将进程设置为最低优先级，它也不会完全失去对 CPU 的访问。

Linux 还实现了 POSIX 实时调度扩展，这允许应用程序精确控制进程对 CPU 的分配。在实时调度的两种策略下运行的进程，SCHED_RR（轮转调度）和 SCHED_FIFO（先进先出），总是优先于运行在非实时策略下的进程。实时进程的优先级范围是 1（低优先级）到 99（高优先级）。只要高优先级进程可运行，它就会完全排除低优先级进程对 CPU 的访问。

在 SCHED_FIFO 策略下运行的进程会独占 CPU，直到进程终止、自愿释放 CPU，或者被一个更高优先级的进程抢占。同样的规则适用于 SCHED_RR 策略，不同之处在于，如果多个进程具有相同的优先级，则 CPU 在这些进程之间以轮转方式共享。

此外，可以使用进程的 CPU 亲和性掩码（CPU affinity mask）来限制进程仅运行在多处理器系统的某些 CPU 上。这有助于提高某些应用程序类型的性能。

实时进程调度 API

我们现在来看一下组成实时进程调度 API 的各种系统调用。这些系统调用允许我们控制进程的调度策略和优先级。

实时优先级范围

sched_get_priority_min() 和 sched_get_priority_max() 系统调用返回特定调度策略的可用优先级范围。

1
2
3
4

#include <sched.h>
int sched_get_priority_min(int policy);
int sched_get_priority_max(int policy);
//返回值：成功时返回非负整数优先级，出错时返回 -1。

• 对于这两个系统调用，policy 指定我们想要获取信息的调度策略。我们可以指定 SCHED_RR 或 SCHED_FIFO。
• sched_get_priority_min() 系统调用返回指定策略的最小优先级，sched_get_priority_max() 返回最大优先级。
• 在 Linux 系统中，这两个系统调用分别返回数字 1 和 99，适用于 SCHED_RR 和 SCHED_FIFO 策略。
• 换句话说，SCHED_RR 和 SCHED_FIFO 的优先级范围完全相同，SCHED_RR 和 SCHED_FIFO 的进程在同一优先级时是同样有资格被调度的。首先调度哪个进程取决于它们在该优先级队列中的顺序。

实时优先级范围的差异

• 实时优先级范围在不同的 UNIX 实现中有所不同。因此，在应用程序中避免硬编码优先级值时，我们应该根据从这些函数返回的值来指定优先级。
• 例如，最低的 SCHED_RR 优先级可以指定为 sched_get_priority_min(SCHED_RR)，下一个较高的优先级可以指定为 sched_get_priority_min(SCHED_RR) + 1，以此类推。

SUSv3 和 UNIX 实现的差异

• SUSv3 并不要求 SCHED_RR 和 SCHED_FIFO 策略使用相同的优先级范围，但在大多数 UNIX 实现中，它们是相同的。
• 例如，在 Solaris 8 中，两个策略的优先级范围为 0 到 59，而在 FreeBSD 6.1 中为 0 到 31。

修改和检索调度策略及优先级

修改调度策略和优先级

sched_setscheduler() 系统调用可以更改指定进程（通过 pid 参数指定）的调度策略和优先级。

• 参数说明：
  • 如果 pid 参数被设置为 0，则更改的是调用该系统调用的当前进程的属性。

1
2

#include <sched.h>
int sched_setscheduler(pid_t pid, int policy, const struct sched_param *param);

成功时返回 0。出错时返回 -1。

param：指向如下包含调度优先级信息的结构体的指针。

1
2
3

struct sched_param {
    int sched_priority;  /* 调度优先级 */
};

SUSv3 定义了 param 参数为一个结构体，以允许实现包括特定于实现的额外字段，这在提供额外的调度策略时可能很有用。然而，与大多数 UNIX 实现一样，Linux 仅提供了 sched_priority 字段，用于指定调度优先级。

对于 SCHED_RR 和 SCHED_FIFO 策略，该字段的值必须位于由 sched_get_priority_min() 和 sched_get_priority_max() 确定的范围内；对于其他策略，该优先级必须为 0。

policy 参数决定了进程的调度策略。它可以是以下策略之一（如表 35-1 所示）：

表 35-1：Linux 的实时和非实时调度策略

sched_setscheduler() 系统调用

• 成功的 sched_setscheduler() 调用会将指定的进程（由 pid 参数指定）移动到其优先级队列的末尾。

SUSv3 指定，成功的 sched_setscheduler() 调用应返回之前的调度策略。然而，Linux 与标准不同，成功调用时返回值为 0。
便携式应用程序应通过检查返回值是否为 -1 来判断是否成功。

• 子进程通过 fork() 继承其父进程的调度策略和优先级，并在调用 exec() 时保留这些属性。

sched_setparam() 系统调用

• sched_setparam() 系统调用提供了 sched_setscheduler() 功能的子集：

  • 它可以修改进程的调度优先级，但不会更改其调度策略。

    1 2	#include <sched.h> int sched_setparam(pid_t pid, const struct sched_param *param);

    成功时返回 0。出错时返回 -1。
    pid 和 param 参数的含义与 sched_setscheduler() 中的相同。

• 成功的 sched_setparam() 调用：
  成功调用 sched_setparam() 后，指定的进程（通过 pid 参数指定）会被移动到其优先级队列的队尾。

• 代码示例：
  以下程序使用 sched_setscheduler() 来根据命令行参数设置指定进程的调度策略和优先级。

  • 参数说明：
    1. 第一个参数是一个字母，用于指定调度策略（如 SCHED_RR 或 SCHED_FIFO）。
    2. 第二个参数是一个整数，用于指定调度优先级。
    3. 剩余参数是需要更改调度属性的进程 ID 列表。

       1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

       #include <sched.h> #include "tlpi_hdr.h"//自定义的头文件，提供错误处理和辅助函数 int main(int argc, char *argv[]) { int j, pol; struct sched_param sp; if (argc < 3 || strchr("rfobi", argv[1][0]) == NULL) usageErr("%s policy priority [pid...]\n" " policy is 'r' (RR), 'f' (FIFO), " #ifdef SCHED_BATCH " 'b' (BATCH), " /* Linux-specific */ #endif #ifdef SCHED_IDLE " 'i' (IDLE), " /* Linux-specific */ #endif "or 'o' (OTHER)\n", argv[0]); // 解析调度策略 pol = (argv[1][0] == 'r') ? SCHED_RR : (argv[1][0] == 'f') ? SCHED_FIFO : #ifdef SCHED_BATCH (argv[1][0] == 'b') ? SCHED_BATCH : #endif #ifdef SCHED_IDLE (argv[1][0] == 'i') ? SCHED_IDLE : #endif SCHED_OTHER; // 解析优先级 sp.sched_priority = getInt(argv[2], 0, "priority"); // 设置每个指定进程的调度策略和优先级 for (j = 3; j < argc; j++) if (sched_setscheduler(getLong(argv[j], 0, "pid"), pol, &sp) == -1) errExit("sched_setscheduler"); exit(EXIT_SUCCESS); }

       权限和资源限制对调度参数更改的影响

1. 2.6.12 版本之前的内核行为

• 在 Linux 2.6.12 内核之前，进程通常需要具有特权（CAP_SYS_NICE）才能更改调度策略和优先级。
• 唯一的例外是：如果调用者的有效用户 ID 与目标进程的真实或有效用户 ID 匹配，则非特权进程可以将目标进程的调度策略更改为 SCHED_OTHER。

2. 2.6.12 版本及之后的内核行为

• 自 Linux 2.6.12 起，引入了一个新的非标准资源限制 RLIMIT_RTPRIO，调整了实时调度策略和优先级的设置规则：
  • 拥有特权的进程（CAP_SYS_NICE）可以对任意进程的调度策略和优先级进行更改。
  • 非特权进程也可以根据以下规则更改调度策略和优先级：

1. RLIMIT_RTPRIO 的非零软限制：

   • 如果进程具有非零的 RLIMIT_RTPRIO 软限制，则可以任意更改其调度策略和优先级。
   • 但有以下限制：
     • 实时优先级的最大值不能超过当前实时优先级和 RLIMIT_RTPRIO 软限制中的较大值。

2. 如果RLIMIT_RTPRIO 的软限制为零：

   • 唯一可以进行的更改是：
     • 将实时优先级降低。
     • 或从实时调度策略切换到非实时调度策略。

3. SCHED_IDLE 策略的特殊性：

   • 运行在 SCHED_IDLE 策略下的进程无法更改其调度策略，无论 RLIMIT_RTPRIO 的值如何。

4. 从其他非特权进程进行更改：

   • 如果调用者的有效用户 ID 与目标进程的真实或有效用户 ID 匹配，则可以更改目标进程的调度策略和优先级。

5. RLIMIT_RTPRIO 软限制的作用：

   • 仅决定进程对自身或其它非特权进程对该进程调度策略和优先级的更改。
   • 一个非零限制并不赋予非特权进程对其他进程的调度策略和优先级进行更改的能力。

特殊说明

• 自 Linux 2.6.25 起，添加了实时调度组（Realtime Scheduling Groups）的概念：
  • 可通过 CONFIG_RT_GROUP_SCHED 内核选项进行配置。
  • 这一选项影响设置实时调度策略时可以进行的更改。
  • 详情请参阅内核源码文档 Documentation/scheduler/sched-rt-group.txt。

实时进程调度概述

标准调度与实时调度的差异

标准内核调度算法通常可以为交互式和后台进程的混合提供足够的性能和响应能力。然而，实时应用程序对调度器的需求更加严格

1. 提供外部输入的最大响应时间保证

• 实时应用程序必须保证对外部输入的最大响应时间。在许多情况下，这些最大响应时间需要非常短，例如在毫秒或几分之一秒的级别。

附加措施

• 一些时间关键型的应用可能需要采取其他措施来避免不可接受的延迟。例如：
  • 使用 mlock() 或 mlockall() 将应用程序的所有虚拟内存锁定到 RAM 中，避免页面错误造成的延迟。

2. 保持对 CPU 的独占访问权

• 高优先级进程在完成任务或自愿放弃 CPU 之前，应该能够独占地使用 CPU，确保任务的顺利执行。

  3. 进程顺序控制

• 实时应用程序需要对其成员进程精确顺序的调度权。

实时调度的 POSIX API

SUSv3 的实时调度 API

SUSv3 定义了一个实时进程调度 API，部分满足了实时应用的严格需求：

• 提供两种实时调度策略：
  • SCHED_FIFO（先进先出）
  • SCHED_RR（轮转）
• 使用这些策略的进程优先级总是高于采用 SCHED_OTHER（普通时间共享）的进程。

实时优先级范围

• 每种实时调度策略至少需要支持 32 个离散优先级。
• 高优先级的进程总是优先于低优先级的进程。

多处理器系统中的调度行为

在多处理器系统（包括超线程系统）中，调度行为有一些特殊性：

1. 每个 CPU 维护一个独立的运行队列。这种设计优于单一的系统级运行队列，可以提高性能。
2. 进程只能在其所属 CPU 的运行队列中被调度。
3. 举例：
   • 在一个双处理器系统中，如果有三个进程：
     • 进程 A：实时优先级为 20；
     • 进程 B：实时优先级为 30；
     • 进程 C：实时优先级为 10；
   • 如果当前 CPU0 正在运行 B，A 只能等待 CPU0 空闲，即使 A 的优先级高于 CPU1 上正在运行的 C。

Linux 提供了 99 个实时优先级，从 1（最低）到 99（最高）。这一区间适用于两种实时调度策略（SCHED_RR 和 SCHED_FIFO）。两种策略中的优先级是等效的。

这意味着：

• 如果两个进程具有相同的优先级，一个使用 SCHED_RR 策略，另一个使用 SCHED_FIFO 策略，那么哪个进程会被调度取决于它们被放入队列的顺序。

实际上，每个优先级都维护着一个可运行进程的队列。

• 调度时，系统会从最高优先级的非空队列中选择队列头部的进程来运行。

POSIX 实时 vs 硬实时

POSIX 实时（软实时）

POSIX 提供的是软实时调度功能，具体表现为：

• 可以控制进程何时被调度。
• 不能完全保证处理输入时的响应时间。
• 适用于绝大多数实时场景，但无法满足某些严格的硬实时需求。

硬实时

• 硬实时系统保证所有任务在规定的时限内完成。
• 实现硬实时通常需要操作系统支持额外的功能，而 Linux 默认不支持。
• Linux 内核自 2.6.18 版本以来添加了一些功能，目标是原生支持硬实时应用，但仍需配置和优化。

SCHED_RR 策略详解

基本规则

在 SCHED_RR 策略下：

• 同一优先级的任务按照轮转方式共享 CPU，每个任务在每次使用 CPU 时获得一个固定长度的时间片。

执行控制

任务保持对 CPU 的控制直到以下任一情况发生：

1. 时间片耗尽：
   • 任务被移至同一优先级队列的末尾，其他同优先级任务可以被调度。
2. 自愿放弃 CPU：
   • 例如，调用了 sched_yield() 或执行了阻塞操作。
3. 任务终止。
4. 被更高优先级的任务抢占。

对于前两个事件（时间片耗尽或主动放弃 CPU）中的情况，当运行在 SCHED_RR 策略下的进程失去对 CPU 的访问权限时，它会被移至其优先级队列的末尾。
在最后一种情况中（被更高优先级的进程抢占），当高优先级进程结束执行后，被抢占的进程会继续运行，使用其剩余的时间片（即被抢占的进程会回到其优先级队列的头部）。

SCHED_RR 和 SCHED_FIFO

在 SCHED_RR 和 SCHED_FIFO 策略中，当前运行中的进程可能因以下原因之一被抢占：

1. 一个更高优先级的进程从阻塞状态变为非阻塞状态（例如，I/O 操作完成）。
2. 另一个进程的优先级被提升到高于当前运行进程的优先级。
3. 当前运行进程的优先级被降低到低于某些其他可运行进程的优先级。

SCHED_RR 策略类似于标准的轮转时间共享调度算法（SCHED_OTHER），它允许一组相同优先级的进程共享 CPU。

两者的主要区别：

1. 优先级规则：

   • SCHED_RR 策略严格区分优先级，高优先级的进程总是优先于低优先级的进程。
   • 而 SCHED_OTHER 策略中，较低的 nice 值（即较高的优先级）虽然增加了调度权重，但不能保证独占 CPU。

2. 时间片保障：

   • 在 SCHED_OTHER 策略中，任何具有低优先级（高 nice 值）的进程始终可以获得一定的 CPU 时间。
   • SCHED_RR 策略允许我们更精确地控制进程的调度顺序和执行时间。

SCHED_FIFO 策略详解

基本规则

SCHED_FIFO（先进先出）策略与 SCHED_RR 类似，但没有时间片限制。

• 任务可以一直运行，直到以下任一情况发生：
  1. 主动放弃 CPU（例如阻塞操作）。
  2. 任务终止。
  3. 被更高优先级任务抢占。

在第一种情况下，进程会被放置到其优先级队列的末尾。
在最后一种情况下，当高优先级的进程停止执行（例如由于阻塞或终止）时，被抢占的进程会继续执行（即，被抢占的进程会保持在其优先级队列的队首）。

SCHED_BATCH 和 SCHED_IDLE 策略

SCHED_BATCH 策略

• 功能：用于批处理型任务。
• 特点：
  • 适用于 CPU 密集型任务。
  • 对调度延迟不敏感。
  • 调度器会根据任务的 nice 值决定优先级。
• 引入版本：Linux 2.6.16。

SCHED_IDLE 策略

• 功能：用于低优先级任务，仅在系统完全空闲时执行。
• 特点：
  • 优先级比所有其他任务都低（甚至低于 nice +19）。
  • nice 值对该策略没有影响。
• 引入版本：Linux 2.6.23。

实时调度策略及算法概述

Linux 提供了两种实时调度策略，SCHED_FIFO 和 SCHED_RR。非实时的普通调度策略是 SCHED_NORMAL。

通过调度类框架，这些实时调度策略并非由完全公平调度器（CFS）管理，而是由一个特殊的实时调度器管理，该调度器定义在 kernel/sched_rt.c 文件中。

1. SCHED_FIFO 策略

SCHED_FIFO 实现了一种简单的先进先出（FIFO）调度算法，没有时间片限制，可以无限期运行。

• 一个可运行的 SCHED_FIFO 任务始终优先于任何 SCHED_NORMAL 任务。
• 当 SCHED_FIFO 任务变为可运行状态时，它会一直运行，直到阻塞或显式放弃处理器。
• 抢占规则：只有更高优先级的 SCHED_FIFO 或 SCHED_RR 任务可以抢占当前的 SCHED_FIFO 任务。
• 如果多个 SCHED_FIFO 任务具有相同优先级，它们以轮转的方式运行。

2. SCHED_RR 策略

SCHED_RR 与 SCHED_FIFO 类似，但有时间片限制。

• 每个任务运行到时间片耗尽时，会被切换到同一优先级队列中的下一个任务。
• 只有更高优先级的任务可以抢占当前任务，即使 SCHED_RR 任务的时间片耗尽，低优先级的进程也无法抢占它的执行。
• 时间片的作用：仅用于同优先级进程之间的调度。

3. 静态优先级

• 两种实时调度策略都实现了静态优先级。
• 内核不会为实时任务计算动态优先级。
• 给定优先级的实时任务总是会抢占低优先级的任务。

4. 软实时与硬实时

• Linux 的实时调度策略提供的是软实时行为：内核会尽力在时限内调度应用程序，但不保证一定达成。
• 硬实时系统则保证严格的时限要求，而 Linux 并不原生支持。

实时优先级范围

• 实时优先级范围为 0 到 MAX_RT_PRIO - 1，默认情况下 MAX_RT_PRIO 为 100。99为最高实时优先级。
• 普通任务（SCHED_NORMAL）与实时任务共享优先级空间：
  • -20 到 +19 的 nice 值映射到优先级范围 100 到 139。这是用户空间的进程评级，-20为最高优先级。

与调度器相关的系统调用

以下是管理调度参数的系统调用列表：

刷了有快一周leetcode题目了，感觉算法这块进度偏慢，一天可能刷一两道题就是极限了。

刷的是leetcode学习栏里的初级算法选题。有时候感觉自己的记忆力真是差到一定程度了，有好两道题刷完后才发现自己在算法竞赛入门里看过，就是记不起来，结果还是用了最笨的方法…

可以预感到自己学了有些方法，例如双指针，之后还需要适应…太难了！一步一步来吧

(以下所有题目来源力扣cn官网)

2/25-3/1

LC26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int a=0;
        int b=nums.size();
        if(b<=1) return b;
        for(int i=0;i<(b-1);i++){
            if(nums[i]!=nums[i+1]){
                nums[a]=nums[i];
                a++;
            }
        }
        nums[a]=nums[b-1];
        return a+1;
    }
};

这里（重新）学到了双指针的思想，熟悉了下许久未见的cpp。选cpp语言来学其实只是因为自己以前选的好几本（算法跟opencv）教程都是cpp的，虽然听说cpp面试在语言特性上挺严格的，但是感觉比起另一个我学过一点的python，这个更能展现一些语言内部的设定吧，python总感觉隐去了不少细节，对我之后代码风格不是太有利。

这道题其实还好，后面有在原值上修改的题，就一定要用vector<int>& nums这种传引用的方式。

在写这道题的时候发现自己各种函数都快忘完了，.size()/memset()/.length() 都不记得了，哎。

122. 买卖股票的最佳时机 II

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int day=0;
        int count=0;
        bool st=false;
        if(prices.size()==1)return 0;
        for(int i=0;i<prices.size()-1;i++){
            if(prices[i]<prices[i+1]&&i+1!=prices.size()-1&&st==false){
                day=i;
                st=true;
            }
            if(prices[i]>prices[i+1]&&st==true){
                count+=prices[i]-prices[day];
                st=false;
            }
            if(prices[i]<=prices[i+1]&&i+1==prices.size()-1){
                if(st==true)count+=prices[i+1]-prices[day];
                if(st==false)count+=prices[i+1]-prices[i];
            }
        }
        return count;
    }
};

做这道题的时候我想到了要在下降的最低日买，上升的最高日卖，然后就捅了if窝……不过这几个条件想合并确实有点难吧。

然后我一想到这个解决方法就乐起来了，完全没想到自己之前在教程里看过一个更简单的解法，就是求每一个前后两日差，然后求其中正数的和。其实我思考题目的时候想到了是不是可以利用每一段买入到卖出可以拆解成这段时间每天都买入卖出，但是没想到啥好的利用方法。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        for(int i=0;i<prices.size()-1;i++){
            prices[i]=prices[i+1]-prices[i];
        }
        int pf=0;
        for(int j=0;j<prices.size()-1;j++){
            if(prices[j]>0)pf+=prices[j];
        }
        return pf;
    }
};

哦对，还可以代码复用一下

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int pf=0;
        for(int i=0;i<prices.size()-1;i++){
            prices[i]=prices[i+1]-prices[i];
            if(prices[i]>0)pf+=prices[i];
        }
        return pf;
    }
};

这样看起来就简洁多了！需要注意的是最后一天没有别的天数来减（买了不卖也是亏），在第二个循环中不用加上。

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

这题显然是有一定的规律可以利用的，否则一边一边写旋转，代码有点太多了。看到题目强调矩阵这个概念，我就想到了可以把矩阵操作一下，比如转置之类的。

第一次做这题时，我想到可以先转置，再看看怎么调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int tri = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0+tri; j < n; j++) {
                int tr=matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tr;
            }
            tri++;
        }
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};

果然，转置过后，每一行reverse一下就行了。不过需要注意的是转置时遍历一个三角即可，不然是转置两次。

后来重做了一遍，我是倒过来想的，先reverse列，再转置。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
	void rotate(vector<vector<int>>& matrix) {
		reverse(matrix.begin(), matrix.end());
		for (int i = 0; i < matrix.size(); i++) {
			for (int j = i; j < matrix[i].size(); j++) {
				int ori = matrix[i][j];
				matrix[i][j] = matrix[j][i];
				matrix[j][i] = ori;
			}
		}
	}
};

这次我学聪明了，知道遍历三角可以j = i，少几行代码。不过这样写使用内存居然比第一次多！我把这个想法也改成用j = 0+tri的形式（其他没变），内存使用变成和第一次一样了。这是为什么呢？

我想去stackoverflow上问问，就去了leetcode英文站看看英文题目描述，顺手再提交了两次题目，发现内存占用又一样了…但是我用最开始的写法时间更快。好吧，看来这或许不是我现阶段能了解的问题。

虽然遇到了一些问题，不过都很快找到方法解决了。看来之前安装VS和openCV的坑不是白踩的。

Maxw终于有了自己的博客啦！有点激动，也有点犹豫跟纠结，虽然理由已经充分到说服自己无数遍，但我仍无法预测自己毅然走出专业的圈走进写代码的坑是不是更加正确的选择…

2/23-2/24

git初试

follow 枫叶的教程
problem occur:
can’ t clone existing repostory with git bash reports timeout
or OpenSSL SSL_read: Connection was reset, errno 10054

从GitHub上clone仓库的时候，试了几次，有时git bash报错10054，有时timeout。

我先是按网上教程改了git的global config，还是报错

想到自己上GitHub都要科学方法，就觉得应该是代理的问题。git应该并非使用系统代理设置，而是需要自行设置，果不其然。

solve:
setup proxy for git, following git设置代理

博客搭建

follow 枫叶的教程合集

感谢枫叶大佬的教程，有时间一定上知乎评论区里发个反馈。

安装node.js与插件的过程中报错属于node.js本地的文件夹无法访问。一开始觉得很奇怪，明明特意从c盘卸载了安别的盘，后来我想起来那个盘是我从c盘分出去的了，草（感叹词）。所以应该是因为也需要管理员权限（也可能是我把git安到c盘了？）。果然管理员启动bash之后，安装就顺畅了。

枫叶的教程里面设置npm的环境变量那里可能有点问题，设置好之后应该是不需要像网上一些教程说的那样安装两遍npm的。npm所在目录需要保留而不是更改，再按教程添加node的目录。在系统变量里添加node的路径后，path里需要添加对应的%NODE_PATH%，这也是教程里未提及的。

其他问题应该就只是跟版本有关了，比如GitHub把主分支从master改成main，创建个人网页的setting单独分页了等等。以及博客更新后无需删除.git重新上传，hexo的操作估计是有延迟的。

我跳过了教程里设置自己的域名的部分。（以后博客里内容多了再为它花钱吧）

在菜单中增加新页面需要同时hexo new page以及在主题的config文件中设置（参考枫叶的教程）

一些感叹

虽然我对于文件系统和权限的理解仅限一鳞半爪，但在配置网站的过程中，这些知识还是帮了我不少忙。不愧是程序员的基本功。

一些bug

git报错the remote end hung up unexpectedly：照此教程解决了：
https://jingyan.baidu.com/article/afd8f4de38d87174e386e967.html

一些bug 2.0

。。。又给git的proxy摆了一道没办法deploy博客，不想用的时候一定要记得git config --global --unset http.proxy 重置啊！设置回来则是git config --global http.proxy proxyaddress:port

最近总感觉自己记性有点差，这是写完博客后如何deploy:
在博客的根文件夹（那个有.deploy_git的文件夹）打开git bash，输入：

1
2
3

hexo clean
hexo generate
hexo deploy

设置apt源

检查Ubuntu的系统版本和代号是否与要安装的源一致
在终端中输入：

1

lsb_release -a

source APT源：

1

sudo bash -c 'echo "deb http://mirrors.aliyun.com/ubuntu/ jammy main restricted universe multiverse" > /etc/apt/sources.list'

检查source list：

1

cat /etc/apt/sources.list

从源获取包信息：

1

sudo apt-get update

vim技巧

虚拟块模式（选择一块代码）：ctrl + q
在虚拟块模式中删除选中：d

设置vim

生成并打开设置文件：

1
2
3
4

cp /etc/vim/vimrc ~/.vimrc
cd ~
ls -a
vim .vimrc

具体设置更改：

1
2
3
4
5
6
7
8

syntax on   " 语法高亮
set background=dark
filetype plugin indent on
set showmatch          " Show matching brackets.
set ignorecase         " Do case insensitive matching
set smartcase          " Do smart case matching
set incsearch          " Incremental search
set hidden             " Hide buffers when they are abandoned

这两天感觉做题的速度快起来了！可以一到一个半小时做完一道题（当然是比较简单的题目啦）。

试着做了一点牛客网上的面试题库，发现数据结构这块果然不能一点书不看（之前我是不是飘了？），准备看数据结构书了。

最近发现了力扣的笔记功能，虽然题目集的笔记和题目的笔记是分开的，有点坑，不过还是打算不写博客的时候先记在题目集笔记里，方便之后翻阅整理。

3/2-3/11

（累了，摸会🐟）

心血来潮想找几个javascript小游戏玩玩，github上找到了untrusted这个游戏。

3/18

想打开网页直接玩来着，结果网页显示一些资源无法访问。于是按issues里的问题换了源，还是没办法。看来只好搭个本地服务器了。

直接down zip文件到了本地（文件有点大 怕git拉到本地中途出问题），git bash安装了http-server，http-server可以这么启动：

http-server [path]

结果跟网页端一样无法显示…一看报错发现没有编译.js文件出来，这就网上搜一圈看看怎么弄。

下载git bash的时候就看到附带了mingw，结果不能直接用make命令，而是得用mingw32-make，好家伙，然而整完还报错：

Makefile:14: *** File mods/default/intro.js not found!. Stop.

本来以为是下载的时候出了问题，上github一看，人家的描述是会自动生成这个文件，那我这是哪里出了问题？

整了挺久累了，下次再更🕊~

对了！make不能用cmd，会报奇怪的错！git bash就不会。

3/18

在github的issues里找到了这个解决换源，虽然说的是网页问题，但也可以改下载下来的code解决404问题。

Here’s a solution:

1. Right click and click “Save As…”
2. Edit the html file that just saved, overwrite jQuery reference <script src="//ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script> as <script src="http://libs.baidu.com/jquery/1.11.3/jquery.min.js"></script> or other reference you trust.
3. run the html.

最后就是上面的file缺失问题了，我找到了一个较早的branch，copy了里面untrusted.js的代码并整到本地的对应文件夹

E:\works\untrusted-master\scripts\build

这样就不用make了，虽然感觉可能会出些错，但是我只是想玩个游戏，先这样啦~

对了，别忘了

http-server *:/.../untrusted-master

（*：code所在盘符，…：code所在目录）

终于可以玩了！

这个游戏里用setPhoneCallback蛮多次的，在这里存下这些代码，免得往回翻了。

1
2
3
4
5
6
7
8
9
10
11
12
13

map.getPlayer().setPhoneCallback(function () {
       var player = map.getPlayer();
       if(player.getColor() == "#0f0"){
       	return player.setColor("#f00");
       }
       else if(player.getColor() == "#f00"){
       	return player.setColor("#ff0");
       }
       else if(player.getColor() == "#ff0"){
       	return player.setColor("#0f0");
       }

   });

GCC编译

gcc编译hello.c，指定输出为hello：

1

gcc hello.c -o hello

运行可执行文件：

1

./hello

一个简单的Makefile示例

1
2
3
4
5

hello:hello.c   # 目标文件名:依赖文件列表
	gcc hello.c -o hello	# 用于生成目标文件的命令序列
.PHONY: clean   # 声明伪目标，使用make clean执行clean操作而不是生成clean文件
clean:
	rm hello

debug bash脚本

直接输出：

1

echo "function_name(): value of \\$var is ${var}"

可以在脚本shebang列设置需要使用的xtrace选项：

1

#!/bin/bash -x

仅在指定列设置xtrace选项：

1
2
3
4
5
6
7
8
9
10

#!/bin/bash
read -p "Path to be added: " $path
set -xv
if [ "$path" = "/home/mike/bin" ]; then
	echo $path >> $PATH
	echo "new path: $PATH"
else
	echo "did not modify PATH"
fi
set +xv

使用trap，EXIT模式仅检测退出时状态:

1
2
3
4
5
6
7
8
9
10
11
12
13

#!/bin/bash
trap 'echo score is $score, status is $status' EXIT
if [ -z $1 ]; then
	status="default"
else
	status=$1
fi
score=0
if [ ${USER} = 'superman' ]; then
	score=99
elif [ $# -gt 1 ]; then
	score=$2
fi

DEBUG模式可以检测每步状态：

1

trap 'echo "line ${LINENO}: score is $score"' DEBUG

GDB debug

使用友好的GDB debug会话：

1

gcc -ggdb test.c -o test.out

设置核心转储：

1
2
3
4
5

if ! grep -qi 'kernel.core_pattern' /etc/sysctl.conf; then
  sudo sh -c 'echo "kernel.core_pattern=core.%p.%u.%s.%e.%t" >> /etc/sysctl.conf'
  sudo sysctl -p
fi
ulimit -c unlimited # 使得当前会话解除核心文件大小限制

永久解除核心文件大小限制：

1
2
3
4

sudo bash -c "cat << EOF > /etc/security/limits.conf
* soft core unlimited
* hard core unlimited
EOF

检查核心文件元数据：

1

file core.1341870.1000.8.test.out.1598867712

使用GDB分析核心转储：

1

gdb ./test.out ./core.1341870.1000.8.test.out.1598867712

在GDB会话中，可以使用以下操作：

1
2
3
4

(gdb) bt	# 回溯
(gdb) f 2	# 转到特定帧
(gdb) list 	# 打印源代码
(gdb) p a/b 	# 打印变量或表达式