Linux 进程调度算法经历了以下几个版本的发展： 基于时间片轮询调度算法。(2.6之前的版本) O(1) 调度算法。(2.6.23之前的版本) 完全公平调度算法。...(2.6.23以及之后的版本) 之前我写过一篇分析 O(1)调度算法 的文章：O(1)调度算法，而这篇主要分析 Linux 现在所使用的 完全公平调度算法。...为了解决上面两个问题，Linux内核的开发者创造了 完全公平调度算法。...完全公平调度的两个对象 Linux 内核为了实现 完全公平调度算法，定义两个对象：cfs_rq (可运行进程队列) 和 sched_entity (调度实体)。...完全公平调度算法实现 有了上面的基础，现在可以开始分析 Linux 内核中怎么实现 完全公平调度算法 了。 我们先来看看怎么更新一个进程的虚拟运行时间。 1.
Day 31, Linux知识点走起~ 1 编程题 【剑指Offer】二叉搜索树的第k个结点 给定一棵二叉搜索树，请找出其中的第k小的结点。...ssh命令用于Linux机器的远程登录，格式如下： ssh [-l login_name][-p port][user@]hostname scp是Linux系统基于ssh登录后进行远程文件拷贝的命令...scp file_source file_target ssh user@被监控主机ip "uptime" ：可以查看远程Linux系统运行了多长时间，uptime表示当前Linux机器运行了多长时间...【Linux】路由和网络连接方面的指令汇总 ping命令用来检测两部主机之间的信道是否畅通； route命令用来显示目前本机路由表的内容，并对路由表作相应的修改； traceroute命令用来探测路由的经过...； ifconfig命令用来检测和设置本机的网络接口； netstat命令用于显示与IP、TCP、UDP和ICMP协议相关的统计数据，一般用于检验本机各端口的网络连接情况； 【Linux】bash配置文件
作者：TeddyZhang，公众号：算法工程师之路 Day 17, Linux知识点走起~ 1 编程题 【剑指Offer】丑数 把只包含质因子2、3和5的数称作丑数（Ugly Number）。...[str[i]] == ){ return i; } } return -1; } }; 2 概念题 【Linux...】top命令常用操作 top 命令是 Linux 下常用的性能分析工具，能够实时显示系统中各个进程的资源占用状况，默认5秒刷新一下进程列表.当输入top命令后会得到下图的界面： ?...】linux哪些命令可以判断ip可达不可达？...【Linux】命令解释: more, less, cat命令 more 命令：可以让屏幕在显示满一屏幕时，此时可按空格健继续显示下一个画面，或按q 键停止显示。
Buddy 分配算法 在看函数前，我们先看下算法，因为我一直认为有了“道”的理解才好进一步理解“术”。 ? 假设这是一段连续的页框，阴影部分表示已经被使用的页框，现在需要申请一个连续的5个页框。...为了避免出现这种情况，Linux内核中引入了伙伴系统算法(Buddy system)。...从上面可以知道Buddy算法一直在对页框做拆开合并拆开合并的动作。Buddy算法牛逼就牛逼在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。
并且，优先级一共就那么几个优先级，实际运行的时候，进程可不止有那么多个，所以优先级并不能真正代替进程是否先运行，并且nice值也是影响进程的运行，这一切，构成了一个新的专题，即Linux中的O(1)调度算法...O(1)调度算法 正式开始之前，我们不妨整理一下，有多少个问题： 1. 随着进程的增多，进程排队的时间是否会越来越多，甚至导致运行不了？ 2. 优先级一定是越小就一定会先运行吗？...3. nice值影响优先级的区间为什么只有40个值 这么多问题的切入点只有一个，即Linux源码中的一个结构：runqueue 这是解决问题的关键。...根据上图，array[0]中有一个140个空间的queue，还有一个bitmap[5]，因为这两个变量的存在，所以Linux的调度是分时操作的，保证了一定的公平性，还有一种操作是实时操作，实时操作的例子比如出租车...当某个队列中一个进程都没有了，比如active中没有进程了，那么active和expired交换队列，此时acitve指向的即活跃，即原来过期的进程变成了活跃进程，活跃的进程变成了过期的进程，这个过程，就被成为O(1)调度算法
*摘要：本文将探讨Linux系统中常用的压缩算法，如gzip、bzip2、xz等，并提供相关的代码示例和使用场景。1. gzip算法gzip是Linux中最常用的压缩工具之一。...它使用DEFLATE算法，结合了LZ77和哈夫曼编码来达到较高的压缩比。...代码示例：压缩文件：gzip filename解压文件：gunzip filename.gz2. bzip2算法bzip2是另一个流行的压缩工具，它使用Burrows-Wheeler块排序文本压缩算法和哈夫曼编码...代码示例：压缩文件：bzip2 filename解压文件：bunzip2 filename.bz23. xz算法xz是一个较新的压缩工具，使用LZMA2算法。...结论Linux提供了多种压缩算法和工具，每种都有其优缺点。选择哪种工具取决于您的特定需求，如压缩比、速度和兼容性。通过理解这些算法的基本原理和使用方法，您可以更有效地管理和处理压缩文件。
时间轮实现 Linux定时器分为低精度定时器和高精度定时器两种类型，内核对其均有实现。本文讨论的是我们在应用程序开发中比较常见的低精度定时器。...本文讲解的是时间复杂度最优，也是linux内核采用的基于时间轮的实现方式。...时间轮算法的核心思路是将定时器散列到多条链上，是典型的空间换时间的策略。下文从单个时间轮出发讲解，逐步扩展至linux实现定时器所采用的多级时间轮算法。...Linux所实现的多时间轮算法，借鉴了日常生活中水表的度量方法，通过低刻度走得快的轮子带动高一级刻度轮子走动的方法，达到了仅使用较少刻度即可表示很大范围度量值的效果。 ?...Linux时间轮定时器算法的关键在于添加定时器操作和时间轮进位迁移链表操作。先来说添加定时器。添加定时器的关键又在于知道每个时间轮每一个刻度所能表示的到期时间的范围。
从多个可用的可运行任务中一次选择一个任务的算法称为调度器，选择下一个任务的过程称为调度。 调度程序是任何操作系统最重要的组件之一。由于几个原因，实现调度算法很困难。...调度算法必须在所有这些相互竞争的需求之间取得平衡。 像大多数现代操作系统一样，Linux 是一个多任务操作系统，因此它有一个调度程序。 Linux 调度程序随着时间的推移而发展。 1....O(1) 调度器 随着内核 2.6 的发布，Linux 调度程序被彻底改革。这个新的调度器被称为 O(1) 调度器——O(…) 被称为“大 O 表示法”。...选择这个名称是因为调度程序的算法需要恒定的时间来做出调度决策，而不管任务数量如何。 O(1) 调度器使用的算法依赖于活动和过期的进程数组来实现恒定的调度时间。...该算法的主要问题是用于将任务标记为交互式或非交互式的复杂启发式方法。该算法试图通过分析平均睡眠时间（进程等待输入所花费的时间）来识别交互式进程。
那么，当可用内存不足时，Linux 内核是怎么处理的呢？ 本文将会介绍，当可用内存不足时，Linux 内核的处理方式。...为了解决这个问题，Linux 内核引入了 LRU内存淘汰算法，用过 Memcached 或者 Redis 的同学应该都了解过 LRU算法。...当系统内存不足时，Memcached 和 Redis 都是使用 LRU算法 来淘汰内存的。...在 Linux 内核中，每个 内存区(zone) 都会维护着一个 active_list 和一个 inactive_list。...LRU算法状态流转 我们最后以一张状态流转图来描述 LRU 算法的过程： 三、总结 本文主要介绍了 Linux 内核内存回收过程中使用的 LRU 算法的原理，在下一篇文章中，我们将会介绍 Linux
Linux 内核包含4个IO调度器，分别是 Noop IO scheduler、Anticipatory IO scheduler、Deadline IO scheduler 与 CFQ IO scheduler...从Linux 2.6.18起，CFQ作为默认的IO调度算法。对于通用的服务器来说，CFQ是较好的选择。...为了满足随机IO和顺序IO混合的场景，Linux还支持ANTICIPATORY调度算法。ANTICIPATORY的在DEADLINE的基础上，为每个读IO都设置了6ms的等待时间窗口。...番外篇 SUSE Linux Enterprise Server 11 SP1 provides a number of I/O scheduler alternatives to optimize for...Queuing (CFQ) scheduler The Completely Fair Queuing (CFQ) scheduler is the default I/O scheduler for SUSE Linux
Linux是一个支持多任务的操作系统，而多个任务之间的切换是通过 调度器 来完成，调度器 使用不同的调度算法会有不同的效果。...Linux2.4版本使用的调度算法的时间复杂度为O(n)，其主要原理是通过轮询所有可运行任务列表，然后挑选一个最合适的任务运行，所以其时间复杂度与可运行任务队列的长度成正比。...而Linux2.6开始替换成名为 O(1)调度算法，顾名思义，其时间复杂度为O(1)。...虽然在后面的版本开始使用 CFS调度算法（完全公平调度算法），但了解 O(1)调度算法 对学习Linux调度器还是有很大帮助的，所以本文主要介绍 O(1)调度算法 的原理与实现。...由于在 Linux 内核中，任务和进程是相同的概念，所以在本文混用了任务和进程这两个名词。
Buddy分配算法 ? 假设这是一段连续的页框，阴影部分表示已经被使用的页框，现在需要申请一个连续的5个页框。...为了避免出现这种情况，Linux内核中引入了伙伴系统算法(Buddy system)。...从上面可以知道Buddy算法一直在对页框做拆开合并拆开合并的动作。Buddy算法牛逼就牛逼在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。...Slab 在Linux中，伙伴系统（buddy system）是以页为单位管理和分配内存。但是现实的需求却以字节为单位，假如我们需要申请20Bytes，总不能分配一页吧！那岂不是严重浪费内存。...总结 从内存DDR分为不同的ZONE，到CPU访问的Page通过页表来映射ZONE，再到通过Buddy算法和Slab算法对这些Page进行管理，我们应该可以从感官的角度理解了下图： ?
前面已经分析了伙伴管理算法的释放实现，接着分析一下伙伴管理算法的内存申请实现。...于是选择了alloc_pages()宏定义作为分析切入口： 【file:/include/linux/gfp.h】 #define alloc_pages(gfp_mask, order) \...alloc_pages_node(numa_node_id(), gfp_mask, order) 而alloc_pages_node()的实现： 【file:/include/linux/gfp.h】...这部分的功能实现将在后面详细分析，当前主要聚焦在伙伴管理算法的实现。...毕了，至此伙伴管理算法的分配部分暂时分析完毕。
内核在微观上，把CPU的运行时间分成许多分，然后安排给各个进程轮流运行，造成宏观上所有的进程仿佛同时在执行。双核CPU，实际上最多只能有两个进程在同时运行，大家...
Linux内核是如何在多核间调度进程的呢？又是内核又是CPU核，两个核有点绕，下面称CPU处理器来代替CPU核。...实际上，如果你没有对你的进程做过特殊处理的话，LINUX内核是有可能把它放到多个CPU处理器上运行的，这是内核的负载均衡。...当然，多核CPU也有许多种，例如INTEL的超线程技术，而LINUX内核对一个INTEL超线程CPU会看成多个不同的CPU处理器。...上面说过，如果你没有对你的进程做过特殊处理的话，LINUX内核是有可能把它放到多个CPU处理器上运行的，但是，有时我们如果希望我们的进程一直运行在某个CPU处理器上，可以做到吗？
业余时间写的玩具操作系统，准备把内存管理部分加强一下，伙伴系统分配页面算法已经完成，下面就要开始写更加细粒度的内存分配，毕竟伙伴系统是按照页为基本单位分配的，参考内核版本linux2.6.30，没分析高版本的源码...，算法基本思想应该差不多。 ...slab算法是一个高效的内存分配算法，它通过把经常使用的内存块比如32字节，64字节大小或者某个常用结构体大小的类型组织成一个kmem_cache结构，经常分配和释放的内存会保存在一个array_cache...源码分析：为了较好的理解算法核心思想，内核各种锁和bug检查代码先不去分析，kmem_cache初始化，先看几个重要的结构体 /* * struct kmem_cache * * manages
首先参考 Linux下编译并使用miracl密码库 该博文在linux下编译Miracl库。 编译完了，自然是要用的，下面介绍两种在C程序中使用miracl库的方法。...linux64编译代码如下： rm *.exe rm miracl.a cp mirdef.h64 mirdef.h gcc -c -m64 -O2 mrcore.c gcc -c -m64 -O2 mrarth0
kmem_cache是slab的核心结构体，主要描述slab的各种信息和链接空闲slab，还保存高速缓存的指针数组。所以要想使用slab分配得先创建kmem_c...
前面已经分析了linux内存管理算法（伙伴管理算法）的准备工作。...managed_pages则是记录管理区的管理页面数，totalhigh_pages则是记录高端内存的页面总数； 具体看一下__free_reserved_page()： 【file:/include/linux...ClearPageReserved(page); init_page_count(page); __free_page(page); } 其中ClearPageReserved定义在/include/linux...最后的__free_page()，该函数既是初始化伙伴管理算法，同时也是伙伴管理算法释放页面的操作函数。暂且搁置分析__free_page()的实现，后面再详细深入。...至此，伙伴管理算法初始化完毕。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
