首页
学习
活动
专区
圈层
工具
发布

Linux进程调度之 - O(1)调度算法

Linux是一个支持多任务的操作系统,而多个任务之间的切换是通过 调度器 来完成,调度器 使用不同的调度算法会有不同的效果。...Linux2.4版本使用的调度算法的时间复杂度为O(n),其主要原理是通过轮询所有可运行任务列表,然后挑选一个最合适的任务运行,所以其时间复杂度与可运行任务队列的长度成正比。...而Linux2.6开始替换成名为 O(1)调度算法,顾名思义,其时间复杂度为O(1)。...虽然在后面的版本开始使用 CFS调度算法(完全公平调度算法),但了解 O(1)调度算法 对学习Linux调度器还是有很大帮助的,所以本文主要介绍 O(1)调度算法 的原理与实现。...O(1)调度算法原理 prio_array 结构 O(1)调度算法 通过优先级来对任务进行分组,可分为140个优先级(0 ~ 139,数值越小优先级越高),每个优先级的任务由一个队列来维护。

5.4K81

进程调度的原理和算法探析

用户与其交互这之间所产生的消耗时间越少,响应越好;就是一句话,进程越快越短越好;进程调度算法调度算法基本分为两类:非抢占式调度算法、抢占式的调度算法;非抢占式调度算法:这个算法就是之前说的所有进程都进行排队等待...接下来我们详细看下各个调度算法的优劣:先来先服务这个是一种最简单的进程调度算法,所有进程按照到达时间的先后顺序排队,先到达的进程先被调度执行。...这种调度算法类似于Java中的队列,采用先进先出(FIFO)的原则。这种调度算法存在一个明显的问题,即如果一个进程执行时间较长,后面的进程就必须等待。...最短作业优先最短作业优先调度算法是一种非抢占式的调度算法,它根据进程的执行时间长短进行排队,将作业时间短的进程排在前面先执行。我都不知道进程的执行时间长短的,系统咋知道的?...最短剩余时间优先他是抢占式的调度算法,可以利用CPU的时间片机制,是基于最短作业优先算法的改进版本。该算法会根据进程的剩余执行时间进行排队,将剩余执行时间最短的进程优先执行。

68670
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    linux进程调度算法-Completely Fair Scheduler

    从多个可用的可运行任务中一次选择一个任务的算法称为调度器,选择下一个任务的过程称为调度。 调度程序是任何操作系统最重要的组件之一。由于几个原因,实现调度算法很困难。...像大多数现代操作系统一样,Linux 是一个多任务操作系统,因此它有一个调度程序。 Linux 调度程序随着时间的推移而发展。 1....O(1) 调度器 随着内核 2.6 的发布,Linux 调度程序被彻底改革。这个新的调度器被称为 O(1) 调度器——O(…) 被称为“大 O 表示法”。...选择这个名称是因为调度程序的算法需要恒定的时间来做出调度决策,而不管任务数量如何。 O(1) 调度器使用的算法依赖于活动和过期的进程数组来实现恒定的调度时间。...该算法的主要问题是用于将任务标记为交互式或非交互式的复杂启发式方法。该算法试图通过分析平均睡眠时间(进程等待输入所花费的时间)来识别交互式进程。

    1.4K10

    常用进程调度算法_进程调度算法例题

    调度的基本评价准则 2.先来先服务调度算法(FCFS) 3.短进程优先调度算法(SPF) 4.优先级调度算法 5.时间片轮转调度算法 6.高响应比优先调度算法 7.多级反馈队列调度算法 正文开始 1...2.先来先服务调度算法(FCFS) FCFS 调度算法是一种最简单的调度算法,它既可用于作业调度,又可用于进程调度。...3.短进程优先调度算法(SPF) 短作业(进程)优先调度算法是指对短作业(进程)优先调度的算法。...【注意】 SPF调度算法的平均等待时间、平均周转时间最少。 4.优先级调度算法 在进程调度中,优先级调度算法每次从就绪队列中选择优先级最高的进程,将处理机分配给它,使之投入运行。...根据新的更高优先级进程能否抢占正在执行的进程,可将该调度算法分为如下两种: 非剥夺式优先级调度算法。

    1.7K11

    Linux进程调度_linux进程的查看和调度

    Linux 系统为了提升响应的速度,倾向于优先调度 I/O 消耗型。...进程的优先级 ---- 调度算法中比较基本的就是靠进程的优先级来进行进程的调度,比如 FreeRTOS,靠 task 的优先级来进行进程的抢占。...—— 小结 实时进程优先级:value 越高,优先级越大 普通进程优先级:nice值越高,普通进程的优先级越小 任何实时进程的优先级 > 普通进程 Linux 调度算法 ---- Linux 中有一个总的调度结构...,称之为 调度器类(scheduler class),它允许不同的可动态添加的调度算法并存,总调度器根据调度器类的优先顺序,依次去进行调度器类的中的进程进行调度,挑选了调度器类,再在这个调度器内,使用这个调度器类的算法...Linux 调度时机 ---- 一、进程切换 从进程的角度看,CPU是共享资源,由所有的进程按特定的策略轮番使用。

    22.9K10

    进程调度算法

    先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度, 也可用于进程调度。FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。...由此可知,本算法适合于CPU繁忙型作业, 而不利于I/O繁忙型的作业(进程)。 2. 短进程优先调度算法 2. 短作业(进程)优先调度算法。...短作业(进程)优先调度算法(SJ/PF)是指对短作业或短进程优先调度的算法,该算法既可用于作业调度, 也可用于进程调度。...基于时间片的轮转调度算法 1. 时间片轮转法。时间片轮转法一般用于进程调度,每次调度,把CPU分配队首进程,并令其执行一个时间片。...多级反馈队列调度算法 多级反馈队列调度算法多级反馈队列调度算法,不必事先知道各种进程所需要执行的时间,它是目前被公认的一种较好的进程调度算法。

    1.3K20

    进程调度算法

    处理机调度是对处理机进行分配,即从就绪队列中按照一定的算法(公平、高效)选择一个进程并将处理机分配给它运行,以实现进程并发执行。...在 Linux 中,有多种进程调度算法,以下是一些常见的调度算法: 先来先服务(FCFS,First - Come - First - Served) 基本原理:按照进程到达就绪队列的先后顺序来分配 CPU...常见使用场景: 批处理系统中的简单任务序列;打印机等独占设备的任务排队;简单的人工操作流程; 短作业优先(SJF,Short - Job - First) 基本原理:优先调度估计运行时间最短的进程。...4、时间片轮转与其他调度算法的比较 与先来先服务(FCFS)算法相比,时间片轮转更加公平。...多级反馈队列调度(Multilevel Feedback Queue Scheduling) 1、基本原理 多队列设置:该算法设置了多个就绪队列,每个队列具有不同的优先级,一般来说,优先级从高到低依次排列

    54010

    进程调度算法

    算法思想 算法规则 这种调度算法是用于**作业调度**还是**进程调度**?...短作业优先(SJF) 短作业/进程优先调度算法:每次调度时选择**当前已到达**且**运行时间最短**的作业/进程。...\*\*\*如果时间片太大\*\*\*,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法\*\*退化为先来先服务\*\*调度算法,并且会\*\*增大进程响应时间\*\*。...优先级调度算法 \*\*\*算法规则:\*\*\*每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程 \*\*\*抢占式的优先级调度算法:\*\*\*每次调度时选择\*\*当前已到达...\*\*\*非抢占的优先级调度算法:\*\*\*每次调度时选择\*\*当前已到达\*\*且\*\*优先级最高\*\*的进程。仅在当前进程\*\*主动放弃处理机时\*\*发生调度。

    2.1K00

    linux 操作系统的进程调度(上) -- 进程调度算法的演进

    引言 上一篇文章中,我们介绍了内核调度的基本概念,知道了调度器设计中最核心的两个指标 -- 周转时间与响应时间: linux 操作系统的进程调度(上) -- 进程调度的基本概念 本文,我们就继续顺着上文的思路...,来看看在操作系统的进程调度设计中,都有哪些调度算法,他们的思路和优劣又分别体现在哪些方面。...CPU,实现了调度算法的公平性。...如果进程是 IO 密集型,那么就频繁调度,但每次调度给与少量时间片。 如果进程是 CPU 密集型,那么就降低调度频率,但每次调度过于多个时间片。...结语 正是有了多级反馈队列算法,现代生产级操作系统中的进程调度器才得以真正建立起来。 下一篇文章,我们就来深入 linux,来了解具体的 linux 进程调度器的发展历史和实现机制,敬请期待。

    2.2K10

    linux进程调度

    进程提供了两种优先级,一种是普通的进程优先级,第二个是实时优先级。前者适用SCHED_NORMAL调度策略,后者可选SCHED_FIFO或SCHED_RR调度策略。...总而言之,对于实时进程,高优先级的进程先执行,它执行到没法执行了,才轮到低优先级的进程执行。 2.非实时进程的调度 Linux对普通的进程,根据动态优先级进行调度。...Linux下,静态优先级是用户不可见的,隐藏在内核中。...因为,不仅要考虑静态优先级,也要考虑进程的属性。例如如果进程属于交互式进程,那么可以适当的调高它的优先级,使得界面反应地更加迅速,从而使用户得到更好的体验。Linux2.6 在这方面有了较大的提高。...Linux2.6认为,交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多,则越有可能属于交互式进程。

    3.6K140

    linux进程调度

    调度策略 进程可以分为实时进程和普通进程,对于这两种不同类型的进程肯定有不同的调度策略,task_struct中的policy就用来表示调度策略。...stop_sched_class:优先级最高的进程使用该策略,可以打断所有其他进程,并且该进程不会被抢占 rt_sched_class:RR算法或者FIFO算法的调度策略,具体由该进程的task_struct...fair_sched_class:普通进程的调度策略 CFS调度算法 CFS(completed fair Schedule)完全公平调度,适用于普通进程调度。...vruntime = 实际运行时间 * NICE_0_LOAD / 权重 使用调度算法首先得有包含vruntime的调度实体,task_struct中有如下调度实体的成员变量: struct sched_entity...se; //完全调度实体 struct sched_rt_entity rt; // 实时调度实体 struct sched_dl_entity dl; // deadline调度实体 CFS算法中将

    8.4K20

    Linux:进程调度

    优先级的极值问题 nice[-20,19]默认优先级80 所以Linux优先级范围是[60,99],因为要考虑公平性,所以调整范围太大。...进程的一些补充 竞争性: 系统进程数⽬众多,⽽CPU资源只有少量,甚⾄1个,所以进程之间是具有竞争属性的。...并发: 多个进程在⼀个CPU下采⽤进程切换的⽅式,在⼀段时间之内,让多个进程都得以推进,称之为并发 单cpu单核只能一个一个cpu,一个进程 多核可以多个进程, 操作系统服务器有的有多个cpu...操作系统是分为分时操作系统,基于时间片公平调度 实时操作系统,来了一个进程要立马调度完,这里工业重要领域最多 我们在电脑里基本上分时操作系统最多。...我们在数组里规定优先级的时候前100个是别的操作系统的优先级 后40个是分时操作系统,这里的40个下标正好映射实时操作系统的优先级 这里queque本质是hash表,算法用hash算法 bitmap

    18610

    进程调度说说吧?讲讲进程调度算法?

    当前运行线程结束,即运行完 run()方法里面的任务 二、进程调度算法 解释:根据系统的资源分配策略所规定的资源分配算法。...1、先来先服务 当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。...在进程调度中采用 FCFS 算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。...3、最短进程优先 最短进程优先是一个非抢占策略,他的原则是下一次选择预计处理时间最短的进程,因此短进程将会越过长作业,跳至队列头。该算法即可用于作业调度,也可用于进程调度。...人话: 多个班级排成一个长队伍上厕所,每个人只给上10s,没上完就排到下个班末尾接着上…… 7、多级反馈队列调度算法 多级反馈队列算法,不必事先知道各种进程所需要执行的时间,他是当前被公认的一种较好的进程调度算法

    1.3K10

    Linux内核调度分析(进程调度)

    Linux进程调度 发展历史 Linux从2.5版本开始引入一种名为的调度器,后在2.6版本中将公平的的调度概念引入了调度程序,代替之前的调度器,称为算法(完全公平调度算法)。...为了保证交互式应用和桌面系统的性能,一般Linux更倾向于优先调度I/O消耗型进程。 进程优先级 Linux采用了两种不同的优先级范围。 使用nice值:越大的nice值意味着更低的优先级。...Linux调度算法 调度器类 Linux的调度器是以模块的方式提供的,这样使得不同类型的进程按照自己的需要来选择不同的调度算法。...上面说讲到的CFS算法就是一个针对普通进程的调度器类,基础的调度器会按照优先级顺序遍历调度类,拥有一个可执行进程的最高优先级的调度器类胜出,由它来选择下一个要执行的进程。...进程选择 这里便是调度的核心部分,用一句话来梗概CFS算法的核心就是选择具有最小vruntime的进程作为下一个需要调度的进程。

    15.6K113

    常用进程调度算法

    基本原理FCFS 是一种最简单的进程调度算法,它遵循 “先到先服务” 的原则。...二、短作业优先调度算法(Shortest Job First,SJF)1. 基本原理SJF 算法以作业(进程)预计执行时间的长短为依据进行调度。...三、优先级调度算法(Priority Scheduling)1. 基本原理每个进程都被赋予一个优先级,优先级高的进程优先获得 CPU 资源进行执行。...四、时间片轮转调度算法(Round Robin,RR)1. 基本原理将 CPU 时间划分成固定大小的时间片(例如 10 毫秒、20 毫秒等),每个就绪进程轮流获得一个时间片在 CPU 上执行。...五、多级反馈队列调度算法(Multilevel Feedback Queue,MLFQ)1. 基本原理这是一种综合了多种调度算法特点的复杂调度算法。

    1.3K12

    Linux进程调度(三)

    一、抢占式调度和主动调度: 前面我们说过,进程的切换总是通过 shedule 函数发生的,而 schedule 函数可以是在系统调用返回、中断返回等时机被调用,也可以进程在驱动程序中主动调用 我们把在系统调用返回等时机调用...schedule 函数的这种非进程自愿情况称为抢占式调度。...把进程在驱动程序中主动调用 schedule 函数来发生进程切换的这种情况称为主动调度 本文将讨论主动调度,抢占式调度将在下一篇文章中讲解: 二、主动调度的发生的情况: 主动调度一般在应用程序读取某个设备时...,设备此时数据还没有准备好,进程就进入睡眠,发生进程调度切换到其它进程运行 例如应用想从网卡读取数据,但是此时网卡没有数据,那么驱动程序就会让进程睡眠,然后发生进程调度。...四、总结: 进程发生切换总是调用 schedule 函数进行的,进程调度分抢占式调度和主动调度,主动调度表示的是进程主动调用 schedule 函数发生进程切换 schedule 函数主要做了两件事,

    2.8K10

    Linux进程调度分析

    而进程调度究竟有多重要呢? 首先,我们需要明确一点:进程调度是对TASK_RUNNING状态的进程进行调度(参见《linux进程状态浅析》)。...普通进程具体的调度算法非常复杂,并且随linux内核版本的演变也在不断更替(不仅仅是简单的调整),所以本文就不继续深入了。...有兴趣的朋友可以参考下面的链接: 《Linux 调度器发展简述》 《鼠眼看Linux调度器》 《鼠眼再看Linux调度器[1]》 《鼠眼再看Linux调度器[2]》 调度程序的效率 “优先级”明确了哪个进程应该被调度执行...每次调度,调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。 那么,为什么从linux 2.6早期到近期linux 2.6版本,调度程序选择进程时的复杂度反而增加了呢?...而O(1)的算法是基于一组数目不大的 链表来实现的,按我的理解,这使得优先级的取值范围很小(区分度很低),不能满足公平性的需求。

    2.8K31

    进程调度算法c语言实现_进程调度算法有哪些

    对一个非抢占式多道批处理系统采用以下算法的任意两种,实现进程调度,并计算进程的开始执行时间,周转时间,带权周转时间,平均周转时间,平均带权周转时间 1.先来先服务算法 2.短进程优先算法 *3.高响应比优先算法...进程的运行时间以时间片为单位进行计算 1、先来先到算法:优先运行先到达的进程,后达到的进程后运行,类似数据结构中的队列,先进先出,对于先来先服务算法,我们只需要队进程进行排序即可; 2、短进程优先算法...数据结构: 先来先服务排序部分算法: 短进程优先部分算法: 将所有的进程信息存入数组里,本程序通过随机赋值赋予进程到达时间、服务时间等,然后通过计算计算出周转时间、带权周转时间、平均周转时间以及平均带权周转时间...system("cls"); printf("\n\n\t\t进程调度算法\n\n"); printf("\t\t 程序清单\n"); printf("\t\t1.......先来先服务算法 \n"); printf("\t\t2.... 短进程优先算法 \n"); printf("\t\t3....

    2K30

    Linux进程调度学习!

    而调度器的任务就是: 1、分配时间给进程 2、上下文切换 所以具体而言,调度器的任务就明确了:用一句话表述就是在恰当的实际,按照合理的调度算法,选择进程,让进程运行到它应该运行的时间,切换两个进程的上下文...Linux 系统为了提升响应的速度,倾向于优先调度 I/O 消耗型。...1、进程的优先级 调度算法中比较基本的就是靠进程的优先级来进行进程的调度,比如 FreeRTOS,靠 task 的优先级来进行进程的抢占。...Linux 调度算法: Linux 中有一个总的调度结构,称之为 调度器类(scheduler class),它允许不同的可动态添加的调度算法并存,总调度器根据调度器类的优先顺序,依次去进行调度器类的中的进程进行调度...Linux 调度时机: 1、进程切换: 从进程的角度看,CPU是共享资源,由所有的进程按特定的策略轮番使用。

    2.2K30

    【Linux内核】进程调度

    文章目录 前言 I/O消耗型与处理器消耗性 进程优先级 时间片 进程抢占 前言 调度程序没有太复杂的原理。最大限度地利用处理器时间的原则是,只要有可以执行的进程,那么就总会有进程正在执行。...Linux 提供了抢占式的多任务模式。在此模式下,由调度程序来决定什么时候停止一个进程的运行以便其他进程能够得到执行机会。这个强制的挂起动作就叫抢占(preemption)。...进程优先级 调度算法中最基本的类就是基于优先级的调度。 这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法。...优先级高的进程先运行,低的后运行,相同优先级的进程按轮转方式进行调度(一个接一个,重复进行)。在包括Linux在内的某些系统中,优先级高的进程使用的时间片也较长。...进程抢占 像前面所说的,Linux 系统是抢占式的。当-个进程进入TASK_RUNNING状态,内核会检查它的优先级是否高于当前正在执行的进程。

    3.2K20
    领券