Posts

题目： Given a binary tree, return the inorder traversal of its nodes\’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 解题： 树的中序遍历： 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。 a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。 b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。 重复以上1、2直到当前节点为空。 实现： 递归方式： 对左子结点调用递归函数，根节点访问值，右子节点再调用递归函数 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector <int> res; inorder(root, res); return res; } void inorder(TreeNode *root, vector<int> &res){ if (!root) { return; } if (root->left) { inorder(root->left, res); } res.push_back(root->val); if (root->right){ inorder(root->right, res); } } }; 空间复杂度：O(n)， 时间复杂度：O(n)。 使用栈实现 从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右， ...

这篇文章 CFS Scheduler是Linux Kernel文档 1.概述 CFS - “Completely Fair Scheduler”，是新的交互式流程调度算法,由Ingo Molnar实现，并在Linux 2.6.23中合并。它是替换以前的Vanilla Kernel的SCHED_OTHER调度策略对应的调度算法。 SCHED_OTHER是老版本中的调度策略后续成为SCHED_NORMAL Vanilla Kernel是指http://www.kernel.org/的上Linux的发布版本 What is Vanilla kernel Debian wiki vanilla CFS 80%的设计可以用一句话来概括：CFS基本上是模型真实硬件上的“理想，精确的多任务CPU”。 理想的多任务CPU是一种（不存在的 :-) ）具有100％物理性能的CPU 功率和每个任务可以以精确的相等速度并行运行每个任务 1 / nr_running速度。例如：如果有2个任务在运行，那么它就会运行每个物理功率为50％, 即实际上并联。 在真正的硬件上，我们一次只能运行一个任务，所以我们必须这样做 介绍虚拟运行时(vruntime))的概念。任务的虚拟运行时 指定下一个时间片何时开始执行理想 上面描述的多任务CPU。在实践中，任务的虚拟运行时是它的实际运行时间标准化为正在运行的任务总数。 2.部分实现细节 在CFS中，通过每个任务task的虚拟运行时(vruntime)通过 p->se.vruntime（纳秒为单位）值体现。这样，就可以任务可以等到准确时间戳并测量应该得到的预期CPU时间。 [小细节：在理想硬件上，任何时候所有任务都会相同 p-> se.vruntime — 任务将同时执行, 没有任务将从CPU时间等到一样的份额。] CFS的任务选择逻辑基于此p->se.vruntime值，因此非常简单：它总是尝试以最小的p->se.vruntime运行任务值（即至少执行到目前为止的任务）。 CFS总是试图拆分 可运行任务之间的CPU时间接近理想的多任务硬件 可能。 CFS的其余大部分设计都脱离了这个非常简单的概念， 有一些附加的装饰，如nice值,多处理和各种算法变体去识别睡眠者。 3. 红黑树 CFS的设计非常激进：它没有使用旧的数据结构 runqueues，但它使用按时间排序的rbtree来构建未来执行任务的时间轴 ，因此不涉及数组切换（以前的Vanilla Kernel调度器O(1)和RSDL/SD涉及到）。 Linux 2.4调度使用时间片epoch,类似多路复用模式,使用runqueue调度方法与进程个数有关 array switch:O(1)为每个CPU维护了两个数组active与expire数组,随着时钟中断发生，1.调度器判断当前进程类型交互进程或者实时进程，重置其时间片重新插入active数组，不是交互实时进程、时间片使用完毕的放入expired数组, 当所有active为空,active与expired交换 RSDL/SD是对O(1)改进 Linux 调度器发展简述 CFS还维护rq->cfs.min_vruntime值，这是一个单调递增值，用于跟踪runqueue中所有任务中的最小vruntime。使用min_vruntime跟踪系统完成的工作总量; 该值用于尽可能多地将新激活的实体放置在树的左侧。 每一个cpu维护一个min_vruntime,每一个子进程创建时被初始化为这个值，如果schedule_feature 设置了SCHED_DEBIT，vruntime还会再增大一些 从几个问题开始理解CFS调度器 runqueue中运行任务的总数通过rq->cfs.load值计算，该值是在runqueue上排队的任务的权重之和。 ...

题目： You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Note: ...

这篇文章 Timers and time management in the Linux kernel. Part 2. 是出自 linux-insides一书中 Timers and time management 章节 Introduction to the clocksource framework Linux内核中的定时器和时间管理.Part 2. clocksource框架简介 上一节Part 1是Timer的第一部分,描述了Linux内核中与计时器和时间管理相关的东西。我们在前一部分中了解了两个概念： jiffies clocksource 第一个全局变量定义在include/linux/jiffies.h头文件中，代表在每个定时器中断期间增加的计数器。因此，如果我们可以访问这个全局变量并且我们知道定时器中断率，我们可以将jiffies转换为人类时间单位。我们已经知道在Linux内核中由编译时常量（称为“HZ”）表示的定时器中断速率。HZ的值等于CONFIG_HZ内核配置选项的值，如果我们通过文件arch/x86/configs/x86_64_defconfig查找到内核相关配置: CONFIG_HZ_1000 = Y 设置内核配置选项后. x86_64 体系架构下 CONFIG_HZ值默认是 1000 , 如果我们将jiffies除以HZ: jiffies / HZ 我们将获得自Linux内核开始工作之后经过的秒数，换句话说，我们将获得系统uptime. 由于HZ代表一秒钟内的定时器中断量，我们可以在未来的某个时间设置一个值。例如： /* one minute from now */ unsigned long later = jiffies + 60*HZ; /* five minutes from now */ unsigned long later = jiffies + 5*60*HZ; 这是Linux内核中非常常见的做法。例如，如果您将查看 arch/x86/kernel/smpboot.c 源代码文件，你会发现do_boot_cpu函数。此功能启动除引导处理器之外的所有处理器。您可以找到等待十秒钟的应用程序处理器响应的代码段： if (!boot_error) { timeout = jiffies + 10*HZ; while (time_before(jiffies, timeout)) { ... ... ... schedule(); } ... ... ... } 备注： 原书udelay(100)后修改为schedule() 详见x86/smpboot: Remove udelay(100) when polling cpu_initialized_map ...

大多数早期windows版本创建的应用可以在win10下正常运行，但也有部分程序无法正常运行, 可以尝试通过兼容性设置解决. 修改高DPI设置 在使用一款windows客户端产品时，由于机器分辨率较高导致其中某一个可执行文件无法运行, 通过修改高DPI设置解决，下面是具体的解决方法: 环境说明: 操作环境： win10， 屏幕分辨路1920*1080 应用环境： 双琦弱视治疗系统v4.0.2 解决方式: 右击属性， 选择高优先级设置 弹出新对话框后，勾选替代高DPI缩放行为缩放执行, 并选择应用程序 Microsoft 帮助文档中整理设置兼容性的方法 设置 说明 兼容性模式 使用早期版本的 Windows 中的设置运行程序。如果你确信此程序是为某个特定版本的 Windows 设计（或用于该版本）的，请尝试使用此设置。 降低颜色模式 在程序中使用数量有限的一组颜色。某些旧版程序在设计时所用的颜色较少。 使用 640 × 480 的屏幕分辨率运行 如果此程序的图形出现锯齿或显示不正确，请尝试使用此设置。 更改高 DPI 设置 如果你的程序无法在具有高 DPI 显示屏的电脑上正常显示（其功能显得模糊或太大或太小），请选择“更改高 DPI 设置”，然后再尝试使用“属性”对话框中的以下选项之一: 选择要使用的 DPI 1. 在“程序 DPI”部分中，选中“使用此设置修复此程序的缩放问题，而不是‘设置’中的缩放问题”，以使用想要用于此程序的 DPI 设置。 注意 此操作只会更改你正在调整的应用的 DPI。如果你想要为所有应用调整此设置，请选择“开始”菜单 >“设置” >“高级缩放设置”，然后按照说明进行操作。 有关更改所有应用的设置的详细信息，请参阅修复显示模糊的应用。 若要“使用主显示器默认的 DPI” 请选择以下选项之一： - 已登录到 Windows -登录到 Windows 时使用为主显示器设置的 DPI。这是默认设置。 - 打开此程序 - 打开特定程序时使用为主显示器设置的 DPI。 更改应用程序的高 DPI 缩放模式 在“高 DPI 缩放替代”区域中，选中“覆盖高 DPI 缩放行为”，然后再尝试使用以下选项之一： - 应用程序 > - 禁用所有的 Windows 缩放设置，并仅使用应用开发人员的设置。在先前版本的 Windows 中，此选项被称为“高 DPI 设置时禁用显示缩放”。 - 系统 - 覆盖程序的 DPI 设置，让该程序像在低 DPI 显示屏上一样运行。在高 DPI 显示屏上，这将导致程序显示模糊。 - 系统(增强) >- Windows 将尝试对此程序使用增强的 DPI 缩放。因此，某些程序将以清晰的文本显示在高 DPI 显示屏上。这不适用于所有程序。 以管理员身份运行此程序 某些程序需要管理员权限才能正常运行。以管理员身份登录电脑以使用此选项。 更改所有用户的设置 将该程序的设置应用到电脑上的所有帐户，然后选择 需要管理员权限“更改所有用户的设置”。系统可能会提示你提供管理员密码或确认你的选择。 参考 使旧版应用或程序与 Windows 10 兼容

Linux进程创建 准备 以fork函数为例，看下Linux进程创建具体工作流程: 下面是使用fork函数创建进程的一段C代码: #include <sys/wait.h> #include <stdio.h> #include <stdlib.h> int main (int argc, char *argv[]) { pid_t pid; pid = fork (); if (pid < 0){ printf("fork() error\n"); }else if (pid == 0){ printf("child process \n"); }else { printf("parent process \n"); } exit(0); } 进程创建流程 trace跟踪 用户程序调用glibc中的提供fork函数，fork函数触发系统调用clone, 去创建一个进程, 下面通过strace跟踪下编译链接后的可执行文件: # strace ./fork ... open("/lib64/libc.so.6", O_RDONLY|O_CLOEXEC) = 3 .... clone(child_stack=0, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD ,child_tidptr=0x7fb0be0eca10) = 16273 ... 从trace日志可以看到,在fork()对应系统调用clone而非fork fork man(2) Since version 2.3.3, rather than invoking the kernel’s fork() system call, the glibc fork() wrapper that is provided as part of the NPTL threading implementation invokes clone(2) with flags that provide the same effect as the traditional system call. (A call to fork() is equivalent to a call to clone(2) specifying flags as just SIGCHLD.) The glibc wrapper invokes any fork handlers that have been established using pthread_atfork(3). ...

题目： Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1} Explanation: Node 1's value is 1, and it has two neighbors: Node 2 and 4. Node 2's value is 2, and it has two neighbors: Node 1 and 3. Node 3's value is 3, and it has two neighbors: Node 2 and 4. Node 4's value is 4, and it has two neighbors: Node 1 and 3. Note: ...

这篇文章 Timers and time management in the Linux kernel. Part 1. 是出自 linux-insides一书中 Timers and time management 章节 Introduction 内核版本比对5.3-rc 进行了相关调整, 增加相关备注 Linux内核中的定时器和时间管理. Part 1. 介绍 这是另一篇文章，它在linux-insides一书中开启了新的篇章。前面的部分描述了系统调用概念，现在是时候开始新篇章了。正如人们可能从标题中理解的那样，本章将专门讨论Linux内核中的“定时器”和“时间管理”。当前章节的主题选择并非偶然。定时器（通常是时间管理）非常重要，并且在Linux内核中广泛使用。 Linux内核使用计时器执行各种任务，例如TCP实现中的不同超时，内核知道当前时间，调度异步函数，下一个事件中断调度和还有更多。 因此，我们将开始学习本部分中不同时间管理相关内容的实现。我们将看到不同类型的计时器以及不同的Linux内核子系统如何使用它们。与往常一样，我们将从Linux内核的最早部分开始，并完成Linux内核的初始化过程。我们已经在特殊的章节-Kernel initialization process中完成了它，它描述了Linux内核的初始化过程，但是你可能还记得我们错过了那里有些东西。其中一个是定时器的初始化。 我们开始吧。 初始化非标准PC硬件时钟 Linux内核解压缩后（更多关于此内容，您可以在内核解压缩部分中阅读）非特定代码开始在init/main.c源代码文件中工作。初始化lock validator后，初始化cgroups并设置canary值，我们可以看到setup_arch函数的调用。 你可能还记得，这个函数（定义在arch/x86/kernel/setup.c)准备/初始化特定于体系结构的东西（例如它为bss部分保留一个位置，为initrd保留一个位置，解析内核命令行以及许多其他事情）。除此之外，我们还可以找到一些时间管理相关的功能。 首先是： x86_init.timers.wallclock_init(); 我们在描述Linux内核初始化的章节中已经看到了x86_init结构。此结构包含指向不同平台的默认设置功能的指针，如 Intel MID，Intel CE4100 等x86_init结构定义在arch/x86/kernel/x86_init.c，正如您所看到的，它默认确定标准PC硬件。 我们可以看到，x86_init结构具有x86_init_ops类型，它为平台特定的设置提供了一组函数，如保留标准资源，平台特定的内存设置，中断处理程序的初始化等。这种结构如下所示： struct x86_init_ops { struct x86_init_resources resources; struct x86_init_mpparse mpparse; struct x86_init_irqs irqs; struct x86_init_oem oem; struct x86_init_paging paging; struct x86_init_timers timers; struct x86_init_iommu iommu; struct x86_init_pci pci; struct x86_hyper_init hyper; struct x86_init_acpi acpi; }; 备注： 新增以下两个成员 ...

 sysctl命令可以_实时_（runtime）查看和修改linux 内核参数。这个命令可以在大多数发行版本找到， 另外内核参数，也可以通过procfs 文件系统，在 /proc/sys/kernel下 进行查看和修改。 查看指定参数 # sysctl kernel.sched_child_runs_firstkernel.sched_child_runs_first = 0 查看所有参数 # sysctl -a |moresysctl: reading key "net.ipv6.conf.all.stable_secret"sysctl: reading key "net.ipv6.conf.default.stable_secret"abi.vsyscall32 = 1crypto.fips_enabled = 0debug.exception-trace = 1debug.kprobes-optimization = 1 修改指定参数 # sysctl -w kernel.sched_child_runs_first=1 kernel.sched_child_runs_first = 1 注意等号前后不能有空格 修改含多个值的参数 # sysctl -w net.ipv4.ip_local_port_range="1025 60999"net.ipv4.ip_local_port_range = 1025 60999 通过修改procfs 文件系统实现 修改指定参数 # echo 1 > /proc/sys/kernel/sched_child_runs_first# sysctl kernel.sched_child_runs_firstkernel.sched_child_runs_first = 1 修改含多个值的参数 # echo "32768 60999" > /proc/sys/net/ipv4/ip_local_port_range# sysctl net.ipv4.ip_local_port_rangenet.ipv4.ip_local_port_range = 32768 60999 持久化设置 以上修改是临时性的，机器重启后失效，如果要持久化保存，可修改/etc/sysctl.conf # cat /etc/sysctl.confkernel.sched_child_runs_first=1 修改完毕后，使用以下命令使得参数立即生效 ...

asm-offset.h 文件 asm-offset.h 文件是在内核编译过程中生成的，生成过程 之前整理了一份笔记 TASK_threadsp的实现及asm-offsets.h， 其中涉及sed处理包含在内核代码 /scripts/Makefile.lib的sed-offsets中，工作是将生成的asm-offset.s转化为asm-offset.h。 /scripts/Makefile.lib ... # ASM offsets # --------------------------------------------------------------------------- # Default sed regexp - multiline due to syntax constraints # # Use [:space:] because LLVM's integrated assembler inserts <tab> around # the .ascii directive whereas GCC keeps the <space> as-is. define sed-offsets 's:^[[:space:]]*\.ascii[[:space:]]*"\(.*\)".*:\1:; \ /^->/{s:->#\(.*\):/* \1 */:; \ s:^->\([^ ]*\) [\$$#]*\([^ ]*\) \(.*\):#define \1 \2 /* \3 */:; \ s:->::; p;}' endef ...