使用内核线程的Linux内核的Netlink服务器

• 代码仓库
• ./client下是客户目录
• 根目录下执行make可以编译模块，执行./remake.sh可以一键编译安装
• 此服务器运行在Ubuntu系统，内核版本为6.5.0-27-generic，基于NETLINK协议
• 主要实现了基于netlink的通信响应，每次响应的时候都创建一个内核线程（kthread）来执行操作，执行完之后线程自动结束
  • 在内核中，不需要手动的执行wait或者是join等负责回收工作，内核会自动回收内核线程
  • 可以在需要强行停止的时候执行kthread_stop() 函数。该函数会向内核线程发送一个停止请求,并等待线程完全退出。在内核线程函数中,我们可以使用 kthread_should_stop() 函数来检查是否收到了停止请求, 检测到该函数返回值为真的时候退出内核线程的工作函数。

    netlink

• 内核创建netlink服务端

  nl_sk = netlink_kernel_create(&init_net, NETLINK_USER, &cfg);

• 上面注意NETLINK_USER协议号必须跟用户态的程序设置的相同，否则无法通信
• 发送数据使用nlmsg_new, nlmsg_put两个函数构造信息，使用nlmsg_unicast发送数据（不区分多播组）
• 接收数据使用回调函数实现

  // 创建netlink socket struct netlink_kernel_cfg cfg = { .input = <call back function>, }; nl_sk = netlink_kernel_create(&init_net, NETLINK_USER, &cfg);

• 回调函数会自动传入此时接收到的数据，使用内核提供的宏NLMSG_DATA和NLMSG_PAYLOAD等可以提取到信息和长度

  用户端的相关操作

• 创建socksock_fd = socket(PF_NETLINK, SOCK_RAW, NETLINK_USER);
• 绑定后可以通信bind(sock_fd, (struct sockaddr*)&src_addr, sizeof(src_addr))
• 发送sendmsg(sock_fd, &msg, 0)
• 接收recvmsg(sock_fd, &msg_recv, 0)

  /proc下的文件

• 在/proc下创建一个文件用于读取内核模块的信息

  proc_entry = proc_create("netlink_stats", 0666, NULL, &proc_file_fops);

• 处理用户的读取操作

  // proc文件的读取操作 static ssize_t proc_read(struct file *file, char __user *user_buf, size_t count, loff_t *ppos) { char buffer[128]; int len; len = sprintf(buffer, "Messages received: %d\nTotal bytes: %d\n", message_count, total_bytes); return simple_read_from_buffer(user_buf, count, ppos, buffer, len); }

  内核线程

• kthread_run(threadfn, data, namefmt, ...)
• 第一个函数是一个int(*)(void*)的函数，接收一个void*的参数，返回一个返回码
• 第二个是传入的参数
• 第三个是名称

  执行结果

• 
• 
• 

什么是无栈协程

• 无栈协程是一种轻量级的协程实现方式，相比有栈协程，它们不拥有独立的调用栈。这种设计让无栈协程更加轻量，因为它们不需要为每个协程分配独立的栈空间，从而减少了内存的使用量。
• 全程都在使用系统自动分配的栈空间，只不过是将一次调用和下一次调用之间所需要的数据利用某种数据结构（比如类的局部变量）手动保存了下来
• 无栈协程的核心原理是将协程中的代码转换成一个或多个状态机。每当执行到协程内的一个异步调用时，协程会保存当前的状态（例如局部变量的值、程序执行到哪一行等），然后暂停执行，将控制权交回给协程的调度器或事件循环。当异步调用完成后，协程根据保存的状态恢复执行
• 实际上就是利用系统的数据结构（比如类的成员）保存状态，外界需要其重新执行的时候读取该状态再执行
• 例子

  #include <iostream> // 协程状态 enum class CoroutineState { BeforeStart = 0, AfterHello, AfterWorld, Completed }; class HelloWorldCoroutine { public: // 协程当前状态 CoroutineState state = CoroutineState::BeforeStart; // 协程的执行函数 void resume() { switch (state) { case CoroutineState::BeforeStart: // 第一个操作：打印"Hello" std::cout << "Hello, "; // 更新状态到下一步 state = CoroutineState::AfterHello; // 退出当前执行，模拟异步操作的暂停 return; case CoroutineState::AfterHello: // 第二个操作：打印"World" std::cout << "World!" << std::endl; // 更新状态到完成 state = CoroutineState::AfterWorld; // 退出当前执行 return; case CoroutineState::AfterWorld: // 协程已完成，不做任何操作 return; default: // 非法状态 std::cerr << "Invalid state" << std::endl; return; } } // 检查协程是否完成 bool isCompleted() const { return state == CoroutineState::AfterWorld; } }; int main() { HelloWorldCoroutine coroutine; // 循环执行，直到协程状态表示完成 while (!coroutine.isCompleted()) { coroutine.resume(); } return 0; }

• 实际上就是将需要的状态手动保存了下来，在被外界调用的时候手动的恢复，是一种比较间接的协程实现方法

Windows系统如何创建一个定时任务

• 使用管理员权限打开一个控制台
  • 
• 在其中输入taskschd.msc
  • 
• 打开的管理器中点击创建基本任务
  • 
• 选择每日
  • 
• 指定的开始时间就是每天的开始时间
• 执行的操作选择执行程序
• 选择自己需要执行的脚本(.bat)文件或者直接在输入框里输入自己需要在命令行执行的命令也可以
• 完成即可

流程

• 内核交叉编译参考

• 工具链的位置在工具链

• 先按照这个

  • 下载好内核源码之后，在kernel目录下输入命令./kernel-5.10/scripts/rt-patch.sh apply-patches
  • 执行结束后会输出The PREEMPT RT patches have been successfully applied!

• 然后在内核目录下执行make menuconfig

  • 在General Setup下找到抢占的设置preemption model
  • 
  • 设置为Real Time

• 然后可能遇到报错，根据提示在内核源码目录下执行make ARCH=arm64 mrproper

• 然后在kernel目录的根目录下执行./nvbuild.sh -o $HOME/kernel_output

  • 输出到用户目录下的kernel_output目录下

• 

  • 注意这一步编译的驱动所需要的SYSSRC是之前编译的内核源码的位置，而不是jetpack SDK下载的内核源码的位置

• 但是又遇到报错

  • 

• 暂时跳过这一步，先进行后面的rootfs构造

• 使用sudo ./flash.sh jetson-agx-orin-devkit internal刷机的时候，可以看到提示

  • 
  • 可以看出内核已经是rt内核了

• 正在烧录中

  • 

• 然后小盒会自动重启

  • 

• 遇到无法连接WiFi的情况，先链接eth0等跳过这个界面，遇到DHCP失败直接选择之后再配置即可

• 然后重启几次开发板，使用sudo nmtui命令在命令行UI界面配网即可

遇到刷机后因为SSH链接过而无法链接的问题

• windows一般在用户/用户名/.ssh/known_hosts文件，根据目标设备的IP地址查找到对应的条目，删除即可

手动启动/停止某个CPU核心的运行

• sudo sh -c 'echo 1 > /sys/devices/system/cpu/cpu11/online'启动
• sudo sh -c 'echo 1 > /sys/devices/system/cpu/cpu11/online'停止

  某些实时内核下的CPU时序问题

• 这个小盒在部分CPU开启部分CPU关闭的时候，可能导致向量计算出错，推测是simd指令的问题，此时使用torch的时候，需要手动指定torch.tensor的设备device="cpu"，同时使用上面的指令手动启动所有CPU核心

使用epoll和协程处理信息的socket通信库

• github链接
• 详细文档见readme
• 底层是ucontext和epoll
• 提供一个EpollServer类
• 基于上一个协程库进行了面向对象的重构实现

  结构

• 创建一个服务器socket
• 使用epoll检测每个事件
• 检测到新的客户端连接的时候，给对应的线程置一个flag，提示这个线程需要创建一个新的协程处理客户端链接的问题
• 新的协程自己在线程内创建协程（最好在同一个线程内创建和使用协程，否则会导致容易产生segmentation fault
• 创建之后将协程状态设置为suspend
• 等待epoll接收到信号之后，通过一个哈希映射将对应的协程状态设置为runnable提示该协程的调度器可以上处理机运行
• 然后对应的线程将协程调度上处理及，协程处理完之后会继续将自己设置为suspend状态并且下处理机，等待epoll激活自己
• 增加了定时器的功能，防止协程在睡眠的时候阻塞，提高时间利用率
• 

在命令行输出有颜色和格式的字符

\033[0m  # 重置所有属性
\033[1m  # 加粗
\033[4m  # 下划线
\033[5m  # 闪烁
\033[7m  # 反显
\033[8m  # 隐藏
\033[30m # 黑色字体
\033[31m # 红色字体
\033[32m # 绿色字体
\033[33m # 黄色字体
\033[34m # 蓝色字体
\033[35m # 洋红色字体
\033[36m # 青色字体
\033[37m # 白色字体
\033[40m # 黑色背景
\033[41m # 红色背景
\033[42m # 绿色背景
\033[43m # 黄色背景
\033[44m # 蓝色背景
\033[45m # 洋红色背景
\033[46m # 青色背景
\033[47m # 白色背景
\033[100m # 灰色背景

• 红色字：echo -e "\033[31mHello, World!\033[0m"
• 加粗、下划线、红色字体echo -e "\033[1;4;31mHello, World!\033[0m"

  使用

  EpollServer ep(<线程数>, <端口号>);

• 头文件是epollServer.h
• 测试文件是client.cpp
• 编译指令g++ cothread.cpp main2.cpp epollServer.cpp -o test1 -lpthread -g

输出

Semaphone 信号量多进程同步

• 可以使用 POSIX 信号量（semaphore）来进行进程间的同步
• #include <semaphore.h>
• 然后可以在使用fork()创建新的进程的时候，使用semaphone控制进程同步，两个进程可以利用semaphore互相控制
• 主要的api是
  • int sem_init(sem_t *sem, int pshared, unsigned int value);创建
  • int sem_destroy(sem_t *sem);销毁
  • int sem_wait(sem_t *sem);阻塞等待
  • int sem_trywait(sem_t *sem);尝试等待，不阻塞
  • int sem_post(sem_t *sem);释放
  • int sem_getvalue(sem_t *sem, int *sval);获取信号量的值

    #include <iostream> #include <semaphore.h> #include <unistd.h> #include <sys/wait.h> int main() { // 创建信号量 sem_t mySemaphore; sem_init(&mySemaphore, 1, 1); // 参数 1 表示信号量在进程间共享，初始值为 1 // 创建子进程 pid_t childPid = fork(); if (childPid == -1) { // 错误处理 std::cerr << "Fork failed." << std::endl; return 1; } else if (childPid == 0) { // 子进程 sem_wait(&mySemaphore); // 等待信号量 std::cout << "Child process is executing." << std::endl; sleep(2); sem_post(&mySemaphore); // 释放信号量 } else { // 父进程 sem_wait(&mySemaphore); // 等待信号量 std::cout << "Parent process is executing." << std::endl; sem_post(&mySemaphore); // 释放信号量 // 等待子进程结束 wait(nullptr); } // 销毁信号量 sem_destroy(&mySemaphore); return 0; }

• 也可以在不同的线程之间用于同步

  #include <iostream> #include <thread> #include <semaphore.h> // 全局信号量 sem_t mySemaphore; void threadFunction(int threadId) { // 在线程内等待信号量 sem_wait(&mySemaphore); // 临界区代码 std::cout << "Thread " << threadId << " is in the critical section." << std::endl; // 离开临界区后释放信号量 sem_post(&mySemaphore); } int main() { // 初始化信号量 sem_init(&mySemaphore, 0, 1); // 在线程间共享，初始值为 1 // 创建两个线程 std::thread t1(threadFunction, 1); std::thread t2(threadFunction, 2); // 等待线程结束 t1.join(); t2.join(); // 销毁信号量 sem_destroy(&mySemaphore); return 0; }

比较的宏以及typeof()类型判断宏`

#define max(a,b) ((a)>(b)?(a):(b))
// 上述无法处理包含a++等的情况

• 使用typeof()类转换宏处理

  #define max(a, b) ({ \ typeof(a) _a = (a); \ typeof(b) _b = (b); \ (void) (&_a == &_b); \ _a > _b ? _a : _b; })

• typeof(a) _a = (a)定义一个a类型的变量，值等于a
• (void) (&_a == &_b)判断二者类型是否相同，不同的话会出现警告

  typeof(int *) a,b;//等价于：int *a,*b;

  零长数组（变长数组）

• 满足需要变长度的结构体，因此有时也习惯性地称为变长数组。
• 在一个结构体的最后, 申明一个长度为0的数组, 就可以使得这个结构体是可变长的

  struct line { int length; char contents[0]; }; struct line *thisline = malloc(sizeof(struct line) + this_length); thisline->length = this_length;

• 上述结构体本身的大小只有一个length的大小，不包括content
• 创建的时候人为分配空间给contents即可

switch case的条件指定范围

case low ... high:
case 'A' ...'Z':

• 还可以用整形数来表示范围，但是这里需要注意在“…”两边有空格

struct的指定成员初始化

#include <stdio.h>

// 三维点的结构体
struct Point3D {
    int x;
    int y;
    int z;
};

// 包含点操作的结构体
struct PointOperations {
    // 函数指针，用于计算两个点的距离
    double (*calculateDistance)(const struct Point3D* p1, const struct Point3D* p2);

    // 函数指针，用于打印点的坐标
    void (*printCoordinates)(const struct Point3D* point);
};

// 计算两个点的距离的具体实现
double calculateDistance(const struct Point3D* p1, const struct Point3D* p2) {
    int dx = p1->x - p2->x;
    int dy = p1->y - p2->y;
    int dz = p1->z - p2->z;
    return sqrt(dx*dx + dy*dy + dz*dz);
}

// 打印点的坐标的具体实现
void printCoordinates(const struct Point3D* point) {
    printf("(%d, %d, %d)\n", point->x, point->y, point->z);
}

int main() {
    // 定义一个三维点
    struct Point3D pointA = {1, 2, 3};

    // 实例化操作的结构体并初始化函数指针
    struct PointOperations pointOps = {
        .calculateDistance = calculateDistance,
        .printCoordinates = printCoordinates
    };

    // 使用结构体中的函数指针计算两个点的距离
    struct Point3D pointB = {4, 5, 6};
    double distance = pointOps.calculateDistance(&pointA, &pointB);
    printf("Distance between points: %f\n", distance);

    // 使用结构体中的函数指针打印点的坐标
    pointOps.printCoordinates(&pointA);

    return 0;
}

• 上文中的指定名称初始化是

  // 定义点操作的结构体并初始化函数指针 struct PointOperations pointOps = { .calculateDistance = calculateDistance, .printCoordinates = printCoordinates };

• 这里可以手动指定需要初始化的结构体成员的名字

可变参数宏

#include <linux/printk.h>

#define pr_debug(fmt, ...) \
    dynamic_pr_debug(fmt, ##__VA_ARGS__)

• dynamic_pr_debug 是 Linux 内核中用于动态调试打印的宏，而 fmt 和 __VA_ARGS__ 则是格式化字符串和可变参数列表。

• fmt：格式化字符串，类似于 printf 中的格式化字符串，包含要打印的文本和格式说明符。

• __VA_ARGS__：表示可变参数的宏，用于将额外的参数传递给 fmt 中的格式说明符。

• ##__VA_ARGS__ 是一个预处理器技巧，用于处理当可变参数列表为空时的情况，确保宏在没有额外参数时也能正确展开

函数属性 __attribute__

• __attribute__ ((attribute-list))

• attribute-list的定义有很多，如noreturn、format以及const等。此外，还可以定义一些和处理器体系结构相关的函数属性

  void __attribute__((noreturn)) die(void);

• 其他属性

  #define __pure __attribute__((pure)) #define __aligned(x) __attribute__((aligned(x))) #define __printf(a, b) __attribute__((format(printf, a, b))) #define __scanf(a, b) __attribute__((format(scanf, a, b))) #define noinline __attribute__((noinline)) #define __attribute_const__ __attribute__((__const__)) #define __maybe_unused __attribute__((unused)) #define __always_unused __attribute__((unused))

  变量属性和类属性

• 变量属性可以对变量或结构体成员进行属性设置。类型属性常见的属性有alignment、packed和sections等。

• alignment属性规定变量或者结构体成员的最小对齐格式，以字节为单位

  struct qib_user_info { __u32 spu_userversion; __u64 spu_base_info; } __aligned(8);

• 上述例子中结构体存储会以八字节对齐

  struct test{ char a; int x[2] __attribute__ ((packed)); };

• x成员使用了packed属性，它会存储在变量a后面，所以这个结构体一共占用9字节

  内建函数

• 内建函数以“_builtin_”作为函数名前缀。下面介绍Linux内核常用的一些内建函数

• __builtin_constant_p(x)：判断x是否在编译时就可以被确定为常量。如果x为常量，该函数返回1，否则返回0

• __builtin_expect(exp, c)：这里的意思是exp==c的概率很大，用来引导GCC编译器进行条件分支预测

  #define __swab16(x) \ (__builtin_constant_p((__u16)(x)) ? \ ___constant_swab16(x) : \ __fswab16(x))__builtin_expect(exp, c)

• __builtin_prefetch(const void *addr, int rw, int locality)：主动进行数据预取，在使用地址addr的值之前就把其值加载到cache中，减少读取的延迟，从而提高性能。

  • 该函数可以接受3个参数：

    • 第一个参数addr表示要预取数据的地址；
    • 第二个参数rw表示读写属性，1表示可写，0表示只读；
    • 第三个参数locality表示数据在cache中的时间局部性，其中0表示读取完addr的之后不用保留在cache中，而1～3表示时间局部性逐渐增强

asmlinkage

• 在标准C语言中，函数的形参在实际传入参数时会涉及参数存放问题
• 对于x86架构，函数参数和局部变量被一起分配到函数的局部堆栈里

  <arch/x86/include/asm/linkage.h> #define asmlinkage CPP_ASMLINKAGE __attribute__((regparm(0)))

• 告诉编译器一个声明了asmlinkage的函数不需要通过任何寄存器来传递参数，只通过堆栈来传递
• 用法

  asmlinkage void my_assembly_function(int arg1, int arg2) { // 汇编函数的实现 // ... }

• asmlinkage 用于标识 my_assembly_function 是一个汇编语言编写的函数，并且该函数使用堆栈而不是寄存器来传递参数
• 对于ARM来说，函数参数的传递有一套ATPCS标准，即通过寄存器来传递。ARM中的R0～R4寄存器存放传入参数，当参数超过5个时，多余的参数被存放在局部堆栈中
  • ARM平台没有定义asmlinkage

switch case和枚举类型配合使用

#define XX(name) \
    case LogLevel::name: \
        return #name; \
        break;

switch (level1) {
    XX(DEBUG);
    XX(INFO);
    XX(WARN);
    XX(ERROR);
    XX(FATAL);
#undef XX
    default:
        return "UNKNOWN";
}

• 此前包含一个枚举类型的定义包括DEBUG等
• 这个可以将枚举类型的数字逆向映射为字符串（通过#name转换为字符串）

std::enable_shared_from_this

• 安全的获取一个对象的this指针
  • 防止重复析构等情况
• 使用shared_from_this()函数返回当前函数的共享指针
• 使用例

  #include <iostream> #include <memory> class Widget : public std::enable_shared_from_this<Widget>{ public: Widget(){ std::cout << "Widget constructor run" << std::endl; } ~Widget(){ std::cout << "Widget destructor run" << std::endl; } std::shared_ptr<Widget> GetSharedObject(){ return shared_from_this(); } }; int main() { std::shared_ptr<Widget> p(new Widget()); std::shared_ptr<Widget> q = p->GetSharedObject(); std::cout << p.use_count() << std::endl; std::cout << q.use_count() << std::endl; return 0; }

thread_local关键字

• thread_local 是 C++11 标准引入的关键字，用于声明线程局部存储（Thread-local storage，TLS）变量。线程局部存储意味着每个线程都有自己独立的变量副本，这样可以避免线程间的竞争条件
• 使得每个线程都有自己独立的某个这个变量的副本而不是与其他线程共享

  #include <iostream> #include <thread> thread_local int threadSpecificValue = 0; void threadFunction() { // 每个线程都有独立的 threadSpecificValue threadSpecificValue += 1; std::cout << "Thread Specific Value: " << threadSpecificValue << std::endl; } int main() { // 创建两个线程，并在每个线程中调用 threadFunction std::thread t1(threadFunction); std::thread t2(threadFunction); // 等待线程执行完成 t1.join(); t2.join(); return 0; }

Leetcode 416. 分割等和子集

• 背包原理教程
• 此题实际上就是使用数组的元素作为物品，数组元素本身的大小就是价值，讨论是否能使用数组中的元素凑出数组大小一半的值
• 使用的是01背包，倒序遍历即可

  class Solution { public: bool canPartition(vector<int>& nums) { int n = nums.size(); if (n < 2) { return false; } int sum = 0, maxNum = 0; for (auto& num : nums) { sum += num; maxNum = max(maxNum, num); } if (sum & 1) { return false; } int target = sum / 2; if (maxNum > target) { return false; } vector<bool> dp(target + 1, 0); dp[0] = true; for (auto& num : nums) { // int num = nums[i]; for (int j = target; j >= num; --j) { dp[j] = dp[j]|dp[j - num]; } } return dp[target]; } };

Leetcode 1049. 最后一块石头重量 II

• 主要思路还是背包问题，只不过此时的背包容量和装的物品的价值都是石头的重量
• 注意内存循环必须从后往前遍历，否则会导致前面被添加过的物品被连续重复添加
• 外层循环的意思是使用到的石头是0-i个，内层的意思是石头总重不超过某个值的时候的最大总重是多少

  class Solution { public: int lastStoneWeightII(vector<int>& stones) { int sum = 0; for(auto& i:stones)sum+=i; int target = sum/2; vector<int> maxArr(target+1, 0); for(int i = 0; i<stones.size(); ++i) { int wi = stones[i]; for(int j = target; j>=wi; --j) { maxArr[j] = max(maxArr[j], maxArr[j-wi]+wi); } } return sum - (maxArr[target]*2); } };

139. 单词拆分

• 此题主要是将字符串视为一个背包，字典中的每个单词都是一个物品
• 从字符串的每个位置开始，如果这个位置已经可达，那么从这个位置开始枚举substring，如果这个substring在字典中，则这个substring的位置也可达，从前往后遍历（因为每个单词使用次数不限制）

  class Solution { public: unordered_set<string> us; vector<int> able; bool wordBreak(string s, vector<string>& wordDict) { vector<bool> able(s.size()+1, false); unordered_set<string> um; for(auto& w : wordDict) { um.insert(w); } able[0] = true; for(int i = 1; i<=s.size(); ++i) { if(!able[i-1])continue; for(int j = 1; i+j-1<=s.size(); ++j) { if(um.count(s.substr(i-1, j))) { able[i+j-1] = able[i+j-1]|able[i-1]; } } } return able[s.size()]; } };

Leetcode 474. 一和零

• 此题是一个递推问题，做题方式类似于背包法
• 遍历同样是外层循环指定此时能使用的字符串的最大index
• 内层循环从已经可达的位置往外递推，类似于广度优先搜索

  class Solution { public: // int maxLen; vector<vector<vector<int>>> lenMap; int findMaxForm(vector<string>& strs, int m, int n) { vector<pair<int, int>> arr; for(auto& i: strs) { int c0 = 0, c1 = 0; for(auto& a:i) { if(a == '0')++c0; else ++c1; } arr.push_back(pair<int, int>(c0, c1)); } vector<vector<int>> map(m+1, vector<int>(n+1, -1)); map[0][0] = 0; for(int i = 0; i<arr.size(); ++i) { int c0 = arr[i].first; int c1 = arr[i].second; // int s = q.size(); for(int j = m; j>=c0; --j) { for(int k = n; k>=c1; --k) { if(map[j-c0][k-c1]<0)continue; map[j][k] = max(map[j-c0][k-c1]+1, map[j][k]); map[m][n] = max(map[m][n], map[j][k]); } } } return map[m][n]<0?0:map[m][n]; } };

  Leetcode 518. 零钱兑换II

• 此题是一个完全背包类型的题参考链接
• 注意循环次序的变化，0 1背包循环一般内层递推循环都是倒序的，但是这种是正序的
• 完全背包遍历背包容量的时候是正序的，但是不完全背包遍历背包容量是倒序的

  class Solution { public: int change(int amount, vector<int>& coins) { vector<int> arr(amount+1, 0); arr[0] = 1; // queue<int> q; // q.push(0); for(int i = 0; i<coins.size(); ++i) { for(int j = coins[i]; j<=amount; ++j) { arr[j]+=arr[j-coins[i]]; } } return arr[amount]; } };

  Leetcode 377. 组合总和IV

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
• 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

  class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<unsigned long> arr(target+1, 0); arr[0] = 1; for(int j = 0; j<=target; ++j) { for(auto &i : nums) { if(j-i>=0) arr[j]+=arr[j-i]; } } return arr[target]; } };

Leetcode 279. 完全平方数

• 转化为一个完全背包问题即可

  class Solution { public: vector<int> minCnt; int numSquares(int n) { if(n == 0)return 0; else if(n == 1)return 1; minCnt = vector<int>(n+1, INT_MAX); minCnt[0] = 0; vector<int> nums; for(int i = 1; i*i<=n; ++i) { nums.push_back(i*i); } for(auto& i : nums) { for(int j = i; j<=n; ++j) { if(minCnt[j-i]!=INT_MAX)minCnt[j] = min(minCnt[j], minCnt[j-i]+1); } } return minCnt[n]; } };

卡码网 28. 子序列中的 k 种字母

• 链接
• 此题是一个背包问题，主要是先统计字符串中26个字母每个包含几个
• 因为顺序无所谓，因此直接开始找字母的种类
• 假设此时字符串已经有了k种字母，凑到k+1种字母的方式就是通过添加一个新的种类的字母，但是新的种类的字母可能有多个备选项比如n
• 那么最终的字符串中可以在这n的字母种选择小于等于n的任意个，选择方式共有 种，上述结果的求和是2^n-1
• 因此实际上在递推背包的时候，假如当前选择的字母的个数有n个，那么具有k种字母的字符串的种类是具有k-1种字母的字符串的种类*2^n-1

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;


int main()
{
    int n, k;
    cin>>n>>k;
    if(n<k)
    {
        cout<<0<<endl;
        return 0;
    }
    map<char, int> letters;
    char tmp;
    for(int i = 0; i<n; ++i)
    {
        cin >> tmp;
        letters[tmp]++;
    }
    vector<long long> combs(k+1, 0);
    combs[0] = 1;
    for(auto&i : letters)
    {
        long long sec = (long long)(pow(2, i.second)-1)%1000000007;
        for(int j = k; j>=1; --j)
        {
            combs[j]+=combs[j-1]*sec;
            combs[j]%=1000000007;
        }
    }

    cout<<combs[k]%1000000007<<endl;
}

nowcoder HJ16 购物单

• 链接
• 此题是一个分组背包问题，也就是每一组的物品只能买一个
• 主要是在遍历每一组的不同物品尝试的时候，不能修改本身的dp数组，要遍历完某一个分组之后再修改
• 此题因为一个物品最多有2个附属物品，因此每一组最多也就是4种组合，可以直接枚举

  #include <iostream> #include <sys/ucontext.h> #include <vector> #include <algorithm> #include <map> #include <cstdlib> using namespace std; int main() { int money, n; cin>>money>>n; vector<vector<vector<int>>> items(n); int a, b, c; for(int i = 0; i<n; ++i) { cin>>a>>b>>c; if(c == 0) { items[i].insert(items[i].begin(), {a, b, a*b}); } else { items[c-1].push_back({a, b, a*b}); } } for(int i = 0; i<n; ++i) { if(items[i].size() ==1)continue; else if(items[i].size() == 2) { items[i][1][0] += items[i][0][0]; items[i][1][1] += items[i][0][1]; items[i][1][2] += items[i][0][2]; } else if(items[i].size() == 3) { items[i].push_back({items[i][0][0]+items[i][1][0]+items[i][2][0], items[i][0][1]+items[i][1][1]+items[i][2][1], items[i][0][2]+items[i][1][2]+items[i][2][2]}); items[i][1][0] = items[i][0][0]+items[i][1][0]; items[i][1][1] = items[i][0][1]+items[i][1][1]; items[i][1][2] = items[i][0][2]+items[i][1][2]; items[i][2][0] = items[i][0][0]+items[i][2][0]; items[i][2][1] = items[i][0][1]+items[i][2][1]; items[i][2][2] = items[i][0][2]+items[i][2][2]; } } vector<int> dp(money+1, 0); for(int i = 0; i<n; ++i) { vector<int> dpRes = dp; for(int j = items[i].size()-1; j>=0; --j) { vector<int> dpTmp = dp; for(int k = money; k>=items[i][j][0]; --k) { dpTmp[k] = max(dpTmp[k], dpTmp[k-items[i][j][0]]+items[i][j][2]); } for(int b = 0; b<dp.size(); ++b) { dpRes[b] = max(dpTmp[b], dpRes[b]); } } dp = dpRes; } cout<<dp[money]; } // 64 位输出请用 printf("%lld")

  494. 目标和

• 此题不能用传统的背包理论做，因为是每个物品必须用到而不是可用可不用
• 使用了两个数组滚动进行更新，从上一次迭代能达到的位置出发，推算这一次迭代能达到的位置以及能达到的方式

  class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { unordered_map<int, int> arr; int maxAbs = 0; for(auto i : nums) { maxAbs+=i; } arr[0] = 1; unordered_map<int, int> tmp; for(int i = 0; i<nums.size(); ++i) { int n = nums[i]; tmp.clear(); for(auto p : arr) { tmp[p.first+n]+=p.second; tmp[p.first-n]+=p.second; } arr = tmp; } return arr[target]; } };

fork和vfork

• fork创建进程的时候，将父进程的所有资源拷贝给子进程
  • 写时复制的
  • 实际上是将内存地址设置为只读的
  • 假如任何一个进程试图写入的话，会触发page fault导致系统给他分配新的内存，也就是复制
• vfork的时候是直接将子进程的资源指向父进程的，二者是同时共有资源的，一个修改会影响另一个

  线程与进程的关系

• 通过pthread_create创建线程的时候，实际上是调用系统的clone（类似于vfork）方式创建了一个与父进程共享一切资源的子进程
• 
• 本来理论上父子进程之间的资源是写时复制的，但是这里直接共享了
• 每个线程都有一个独立的PID

  线程的真假ID

• 用户空间getpid()获得的PID是进程ID，并不是线程独立的PID
  • gettid()获得的才是真正线程PID，也就是内核的真正PID
  • 

进程的托孤

• 一个拥有子进程的进程终止的时候，会向init进程或者是自己最近一级的父进程中的subreaper进程托孤，将自己的子进程交给这些进程处理
  • subreaper需要一个进程自己声明自己是才可以

    深度睡眠和浅度睡眠

• 深度睡眠只能被资源唤醒
  • 甚至无法被信号杀死
• 浅度睡眠可以被资源或者是信号（signal）唤醒
• 比如程序因为内存没加载导致page fault
  • 此时如果因为接收到信号开始执行内容，会导致程序继而触发更多的page fault
  • 因此只有等到相关内存页面被分配了才可以

睡眠与唤醒

• 程序的睡眠是程序访问资源的时候发现需要等待，自己让出CPU使用权并且将状态设置为sleep
• 睡眠结束的时候需要判断自己是被什么唤醒的（如果是浅度睡眠的话）
  • 是被信号唤醒的？是什么信号
  • 是被资源唤醒的？继续执行

第一个进程是被谁创建出来的

• 1进程（也就是init）是被Linux的0进程创建出来的
• 但是Linux的0进程使用pstree看不到
• 退化为了IDLE进程
  • 所有进程停止或者睡眠之后，才会调度的进程
  • 它会把将CPU设置为省电状态，只有中断可以唤醒

    进程切换

• 进程切换的开销不只是上下文切换，主要还包括进程切换引起的内存cache 的cache miss
• 因为不同进程需要的内存空间不同，导致切换会极大增加miss概率

非实时进程的时间片分配

• 使用nice值分配
• nice越大，优先级越低
• 优先级高的相对于优先级低的可以在唤醒的一瞬间抢占，但是之后会一起轮转
• 优先级越高的在轮转中分配到的时间片越长
• 在整个循环过程中是所有优先级的进程一起轮转的，不会高优先级阻塞低优先级运行
• 系统会针对应用是IO类型还是CPU消耗类型来调整nice值
  • 越CPU占用，nice越低

    控制实时进程和非实时进程占用的CPU比例

• sched_rt_period_us和shced_rt_runtime_us
• 控制FIFO和RR最多占用的时间
• sudo sh -c 'echo CPU核心数*1000000 > /proc/sys/kernel/sched_rt_period_us'
  • 上面那个不能超过CPU核心数*1000000
• sudo sh -c 'echo 某个小于period的值 > /proc/sys/kernel/sched_rt_runtime_us'
• 不能超过sched_rt_period_us
  • 但是可能会导致系统崩溃
• 

CFS-完全公平调度

• 每次都调度到当前位置vruntime最小的进程
• 也就是考虑到优先级修正之后，运行时间最小的进程
• 完全公平，使得所有进程的vruntime尽可能公平分配
  • vruntime是实际运行时间进行一些权重和系数运算得出的
  • 物理runtime除以权重
  • 

设置进程的CPU亲和

• 使用taskset命令行工具
• 上文提到的sched_setaffinity()
• 或者单独设置线程的亲和力pthread_setaffinity_np()

  #include <pthread.h> int pthread_setaffinity_np(pthread_t thread, size_t cpusetsize, const cpu_set_t *cpuset);

• 或者创建新线程时，通过属性结构体，控制新线程的亲和性pthread_attr_setaffinity_np()

  #include <pthread.h> int pthread_attr_setaffinity_np(pthread_attr_t *attr, size_t cpusetsize, const cpu_set_t *cpuset);

进程组

• cgroup（Control Groups）是 Linux 内核提供的一个功能，用于限制、控制和监视一个或多个进程的资源使用。cgroup 允许你将进程组织在层次结构中，并为每个组分配特定的资源限制。
• 创建
  • sudo mkdir /sys/fs/cgroup/cpu/my_cgroup
• 添加进程
  • echo <PID> > /sys/fs/cgroup/cpu/my_cgroup/tasks
• 设置 cgroup 的资源限制
  • echo 1000000 > /sys/fs/cgroup/cpu/my_cgroup/cpu.cfs_quota_us
• 查看 cgroup 信息
  • cat /sys/fs/cgroup/cpu/my_cgroup/cpu.cfs_quota_us
• 删除 cgroup
  • sudo rmdir /sys/fs/cgroup/cpu/my_cgroup

如何使用sudo权限将echo的输出写入到文件中

sudo sh -c 'echo string > /path/to/file'
# 或者
echo "Hello, world" | sudo tee -a /path/to/file

Linux中进程可以抢占的部分

• 即使是在下面不可调度的部分唤醒了一个优先级再高的进程，也不允许抢占执行
• 一个核心上的进程拿到了spinlock，会直接关闭这个核心的调度器停止调度
• 一个程序的优先级改变（降低）的时候，别的优先级高的进程可以立即抢占

• 自旋锁的自旋一定发生在不同的核心之间
  • 如果同一个核心的两个进程争夺自旋锁，一个抢到之后就直接关闭了调度器，另一个进程根本上不来，不可能自旋
  • 只有可能是一个核心持有锁，另一个核心自旋

进程回收和僵尸进程

• 一个进程变成僵尸状态之后，进程的资源都消失了
• 但是进程的task_struct还没有消失
• 等待父进程使用waitpid回收并且查看进程的退出码，判断子进程的死因
• 只有父进程使用wait等待的时候他的task struct才会消失
• 这个进程无法使用系统的signal杀死

Linux进程状态

LeetCode 332. 重新安排行程

• 此题的大部分是按照回溯法标准套路进行
  • 也就是
  • 遍历尝试DFS
  • 满足条件的修改环境
  • 递归
  • 出现结果的话直接返回
  • 没出现的话将环境复原
  • 继续尝试下一种
• 但是注意需要一个排序（因为返回字典序最小的结果）快速的从一个string出发到一个string截止并且能处理重复情况的方式
  • 使用了unordered_map<string, map<string, int>>
  • 外层map将起点映射到终点
  • 内层map将终点映射到出现过的次数

    class Solution { public: // unordered_set<int> used; vector<string> ret; unordered_map<string, map<string, int>> to; bool flag; vector<string> findItinerary(vector<vector<string>>& tickets) { flag = false; for(auto& i:tickets) { ++to[i[0]][i[1]]; } vector<string> ans; // ans.resize(tickets.size()); recur(tickets, ans); return ans; } void recur(vector<vector<string>>& tickets, vector<string>& ans) { // cout<<tickets.size()<<endl; int cnt = tickets.size(); if(!ans.size()) { for(auto& i : to["JFK"]) { if(i.second>0) { --i.second; ans.push_back("JFK"); ans.push_back(i.first); recur(tickets, ans); if(flag)return; ans.pop_back(); ans.pop_back(); ++i.second; } } return; } if(ans.size() == cnt+1) { flag = true; return; } for(auto& i : to[ans[ans.size()-1]]) { if(i.second>0) { i.second--; ans.push_back(i.first); // cout<<i.first<<endl; recur(tickets, ans); if(flag)return; ans.pop_back(); i.second++; } } } };

Leetcode 47. 全排列II

• 关键是去重
• 还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了
  • 有两种去重的方式，其中一种是当目前循环的时候如果i大于起始位置而且数组中第i个的值等于第i-1个的话，则跳过i（这种去重的方式允许不同层级的回溯具有相同的元素值，因为允许在当前迭代的第一个元素的位置进入下一层）
  • 参考力扣子集II
  • 另一种方式是使用used数组来记录，跳过所有与上一个元素相同而且目前没有被使用的元素，也就是在这一层出现的重复元素。
  • 
  • 如果这个位置和上个位置相同，而且上个位置的数字在另外的分支里被使用过（也就是used[i-1] == false），那么跳过这个数字来去重
  • 在这个位置中被使用过的数字的used是true

    class Solution { private: vector<vector<int>> result; // vector<int> path; void backtracking (vector<int>& nums, vector<int>& seq, vector<bool>& used, int start) { seq.push_back(nums[start]); // 此时说明找到了一组 if (seq.size() == nums.size()) { result.push_back(seq); seq.pop_back(); return; } for (int i = 0; i < nums.size(); i++) { if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } if (used[i] == false) { used[i] = true; backtracking(nums, seq, used, i); used[i] = false; } } seq.pop_back(); } public: vector<vector<int>> permuteUnique(vector<int>& nums) { result.clear(); sort(nums.begin(), nums.end()); // 排序 for(int i = 0; i<nums.size(); ++i) { if(i>0 && nums[i-1] == nums[i]) continue; vector<int> seq; vector<bool> used(nums.size(), false); used[i] = true; backtracking(nums, seq, used, i); } return result; } };

Leetcode 90. 子集 II

• 此题不讲究顺序，所以可以使用先排序再相邻去重的方式

  class Solution { private: vector<vector<int>> ret; // vector<bool> used; void backtracking(vector<int>& nums, vector<int>& ans, int start) { ans.push_back(nums[start]); ret.push_back(ans); for(int i = start+1; i<nums.size(); ++i) { if(i>start+1 && nums[i] == nums[i-1])continue; // used[start] = true; backtracking(nums, ans, i); // used[start] = false; } ans.pop_back(); return; } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); ret.push_back({}); // used = vector<bool>(nums.size(), false); vector<int> tmp; for(int i = 0; i<nums.size(); ++i) { if(i > 0 && nums[i] == nums[i-1])continue; // used[i] = true; backtracking(nums, tmp, i); // used[i] = false; } return ret; } };

Leetcode 491. 非递减子序列

• 注意此题不能手动重新排序数组
• 因此需要防止同一层中出现重复的，使用set
• 每个递归函数自己定义自己的set，只考虑自己这一层是否出现过重复的

  class Solution { public: vector<bool> used; vector<vector<int>> ret; vector<vector<int>> findSubsequences(vector<int>& nums) { unordered_set<int> used; for(int i = 0; i<nums.size(); ++i) { if(used.count(nums[i]))continue; used.insert(nums[i]); vector<int> seq; recur(nums, seq, i); } return ret; } void recur(vector<int>& nums, vector<int>& seq, int start) { if(start>=nums.size()) { if(seq.size()>=2) ret.push_back(seq); return; } seq.push_back(nums[start]); if(seq.size()>=2) ret.push_back(seq); unordered_set<int> used; for(int i = start+1; i<nums.size(); ++i) { if(used.count(nums[i]) || nums[i]<seq.back())continue; used.insert(nums[i]); recur(nums, seq, i); // used.erase(i); } seq.pop_back(); } };

Leetcode 40. 组合总和 II

• 注意此题的去重方法，是放在循环中
• 如果上一个元素与这个元素相等而且上一个元素与这个元素没出现在同一个数组之中
• 则说明在之前的某个位置，上一个元素必定在这个位置已经出现过了
  • 因为没出现过，意味着上一个元素与当前的这个元素在不同的尝试中被遍历过一次了，再来一次必然会重复

    class Solution { public: vector<vector<int>> ret; // vector<bool> used; vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector<int> ans; // used = vector<bool>(candidates.size(), false); for(int i = 0; i<candidates.size(); ++i) { if(i>0 && candidates[i-1] == candidates[i])continue; // used[i] = true; traversal(candidates, target, i, ans); // used[i] = false; } return ret; } void traversal(vector<int>& c, int target, int start, vector<int>& ans) { ans.push_back(c[start]); if(target <= c[start]) { if(target == c[start]) { ret.push_back(ans); } ans.pop_back(); return; } for(int i = start+1; i<c.size(); ++i) { if(i>start+1 && c[i] == c[i-1])continue; traversal(c, target-c[start], i, ans); } ans.pop_back(); } };

    Leetcode 93. 复原IP地址

• 注意此题的去重方式，主要是决定在哪个位置结束
• 注意，必须是前面明确声明要结束了的地址才可以作为答案之一
• 否则会重复

  class Solution { public: vector<string> ret; vector<string> restoreIpAddresses(string s) { string ans; // ans+=s[0]; traversal(s, 0, 0, 4, ans); return ret; } void traversal(string& s, int start, int cnt, int remain, string ans) { if(start==s.size()&&cnt == 3) { if(remain == 0) { ret.push_back(ans.substr(1)); } return; } if(remain<0)return; if(start == s.size())return; if(cnt == 0 || cnt == 3) { ans+="."; ans+=s[start]; if(s[start] =='0') { // 结束本节 traversal(s, start+1, 3, remain-1, ans); } else { // 结束本节，1个数字 traversal(s, start+1, 3, remain-1, ans); // 继续本节，最少有2个数字 traversal(s, start+1, 1, remain-1, ans); } return; } else if(cnt == 1 || cnt == 2) { ans+=s[start]; // 如果超出限制 则提前结束 if(stoi(ans.substr(ans.size()-cnt-1))>255)return; if(cnt==1) { // 在只有2个数字的时候结束本节 traversal(s, start+1, 3, remain, ans); } // 继续本节cnt = 2(本节有3个数字)或者cnt = 3 traversal(s, start+1, cnt+1, remain, ans); return; } } };