首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

引言 上一篇文章中,我们介绍了内核调度的基本概念,知道了调度器设计中最核心的两个指标 -- 周转时间与响应时间: linux 操作系统进程调度(上) -- 进程调度的基本概念 本文,我们就继续顺着上文的思路...,来看看在操作系统进程调度设计中,都有哪些调度算法,他们的思路和优劣又分别体现在哪些方面。...先来先服务算法 FCFS “先来先服务”翻译自“First Come First Service”,所以缩写为 FCFS,顾名思义,就是让操作系统按照任务到来的顺序顺次执行,很显然,这是各种调度算法设计中最为简单的一个...时间片轮转算法 RR Round-Robin 算法是现代操作系统调度器诞生的基石。它按照 CPU 时钟芯片产生的若干个时钟脉冲为单位,将 CPU 时间进行切分,每个分片就是 CPU 调度的时间片。...结语 正是有了多级反馈队列算法,现代生产级操作系统中的进程调度器才得以真正建立起来。 下一篇文章,我们就来深入 linux,来了解具体的 linux 进程调度器的发展历史和实现机制,敬请期待。

1.8K10

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

Linux是一个支持多任务的操作系统,而多个任务之间的切换是通过 调度器 来完成,调度器 使用不同的调度算法会有不同的效果。...Linux2.4版本使用的调度算法的时间复杂度为O(n),其主要原理是通过轮询所有可运行任务列表,然后挑选一个最合适的任务运行,所以其时间复杂度与可运行任务队列的长度成正比。...而Linux2.6开始替换成名为 O(1)调度算法,顾名思义,其时间复杂度为O(1)。...虽然在后面的版本开始使用 CFS调度算法(完全公平调度算法),但了解 O(1)调度算法 对学习Linux调度器还是有很大帮助的,所以本文主要介绍 O(1)调度算法 的原理与实现。...实时进程调度 实时进程分为 FIFO(先进先出) 和 RR(时间轮询) 两种,其调度算法比较简单,如下: 先进先出的实时进程调度:如果调度器在执行某个先进先出的实时进程,那么调度器会一直运行这个进程,直至其主动放弃运行权

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

    操作系统实验一进程调度算法模拟_常用的进程调度算法

    今日闲来无聊,发现很早之前写的操作系统实验还没有整理,再加上有很多人问,索性就发成博客吧。...实验一 进程调度算法 一、实验目的   用高级语言编写和调试一个进程调度程序,以加深对进程的概念及进程调度算法的理解. 二、实验指导 设计一个有 N个进程共行的进程调度程序。   ...进程调度算法:分别采用先来先服务算法、短作业优先算法、高响应比优先算法实现。   每个进程用一个进程控制块( PCB)表示。...三、提示 1、在采用短作业优先算法和高响应比优先算法进行调度时应注意进程的到达时间,对于没有到达的进程不应参与调度。...2、注意在采用高响应比优先算法时计算优先权的时机,因为采用动态优先权,所以应在每次调度之前都重新计算优先权,高响应比优先算法采用下列公式计算优先权 进程调度算法流程图 #include<bits/

    1.6K30

    linux 操作系统进程调度(上) -- 进程调度的基本概念

    Linux 操作系统中,系统会为每个进程打一个分,这个分就是 PR 值,它是 Priority 的前两个字母。...但有时,用户可能会不认可操作系统的优先级数值,而是想要去手动调整进程的优先级。此时,如果让用户直接干预 PR 值,那风险就显得很大。Linux 为用户层设计了一个 Nice 值,翻译为“谦让值”。...操作系统调度策略 在调度进程时,操作系统有两种选择: 协作式调度 -- 进程一旦被调度运行,除非他运行结束或主动释放 CPU,否则它将一直占用 CPU。...而抢占式调度的模式下,操作系统尽管增加了进程切换的开销以及调度算法设计的复杂度,但却可以更加灵活地分配 CPU 的时间资源,所以常见的操作系统一般都采用抢占式调度的策略。 5....结语 本文,我们从操作系统的整体层面,了解了操作系统进程调度的基本概念和设计思想,但我们尚未触及核心部分,到底 linux 系统中的调度器是如何设计的,又有着怎样的历史沿革,出现了哪些算法

    1.1K10

    操作系统中常用的进程调度算法有_调度算法有哪些

    算法常被用于批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度算法,还可用于实时系统中。当把该算法用于作业调度时,系统将从后备队列中选择若干个优先权最高的作业装入内存。...6、Unix、Linux与Windows进程调度策略的比较 无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。...Linux 从整体上区分实时进程和普通进程,因为实时进程和普通进程调度是不同的,它们两者之间,实时进程应该先于普通进程而运行,然后,对于同一类型的不同进程,采用不同的标准来选择进程。...在同一优先级的各线程按时间片轮转算法进行调度。如果一个高优先级的线程进入就绪状态,当前运行的线程可能在用完它的时间片之前就被抢占处理机。 多任务、有线程优先级、多种中断级别这是现代操作系统的共同特点。...实时操作系统(Real-time operating system, RTOS)最大的特点是对响应时间有严格的要求,linux尚且不能称为完全的实时操作系统,USA的宇宙飞船常用的操作系统是VxWorks

    2.5K40

    操作系统-进程调度

    Hi~朋友,关注置顶防止错过消息 摘要 进程调度 调度原则 调度算法 线程调度 进程调度是指在进程之间选择一个进程将其送上CPU执行,通常这个是由操作系统中的调度程序执行。...周转时间:周转时间是运行时间和阻塞时间的总和,一个进程调度时间越小越好 等待时间:进程在就绪队列中等待时间尽可能的短 响应时间:在交互式较强的系统,调度算法需要尽可能的降低响应时间 调度算法 如果硬件提供某个频率的时钟中断...,根据如何处理时钟中断调度算法大致分为两类: 非抢占式调度算法:该算法挑选一个进程,让该进程运行直到被阻塞或者进程退出,才会调用另外一个进程,不会理会时钟中断 抢占式调度算法:该算法挑选一个进程,让该进程在某个时间段内运行...时间片轮转(RR)调度算法 每一个进程被分给一个时间段,称之为时间片,即允许该进程在该时间段中运行。...最高优先级(HPF)调度算法 从就绪队列中选择最高优先级的进程运行。

    1.4K20

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

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

    1.3K11

    linux进程调度算法-Completely Fair Scheduler

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

    1.3K10

    进程调度算法

    先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度, 也可用于进程调度。FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。...短作业(进程)优先调度算法(SJ/PF)是指对短作业或短进程优先调度算法,该算法既可用于作业调度, 也可用于进程调度。...为了照顾紧迫性作业,使之进入系统后便获得优先处理,引入了最高优先权优先(FPF)调度算法。 此算法常被用在批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度,还可以用于实时系统中。...当其用于进程调度时,把处理机分配给就绪队列中优先权最高的进程,此时, 又可以进一步把该算法分成以下两种: 1)非抢占式优先权算法 2)抢占式优先权调度算法(高性能计算机操作系统)...多级反馈队列调度算法 多级反馈队列调度算法多级反馈队列调度算法,不必事先知道各种进程所需要执行的时间,它是目前被公认的一种较好的进程调度算法

    1.1K20

    进程调度算法

    算法思想 算法规则 这种调度算法是用于**作业调度**还是**进程调度**?...短作业优先(SJF) 短作业/进程优先调度算法:每次调度时选择**当前已到达**且**运行时间最短**的作业/进程。...时间片轮转调度算法(RR)——常用于分时操作系统 \*\*\*算法规则:\*\*\*按照各进程到达就绪队列的顺序,轮流让各个进程执行一个\*\*时间片\*\*(如100ms)。...优先级调度算法 \*\*\*算法规则:\*\*\*每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程 \*\*\*抢占式的优先级调度算法:\*\*\*每次调度时选择\*\*当前已到达...+ 如果一个进程频繁地进行I/O操作,则可适当提升其优先级 操作系统更**偏好于I/O型进程(或称I/O繁忙型进程)** + I/O设备和CPU可以\*\*并行\*\*工作。

    1.9K00

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

    进程调度含义 ---- 进程调度决定了将哪个进程进行执行,以及执行的时间。操作系统进行合理的进程调度,使得资源得到最大化的利用。 在单片机上,常常使用的方式是:系统初始化—->while(1){}。...进程的优先级 ---- 调度算法中比较基本的就是靠进程的优先级来进行进程调度,比如 FreeRTOS,靠 task 的优先级来进行进程的抢占。...—— 小结 实时进程优先级:value 越高,优先级越大 普通进程优先级:nice值越高,普通进程的优先级越小 任何实时进程的优先级 > 普通进程 Linux 调度算法 ---- Linux 中有一个总的调度结构...,称之为 调度器类(scheduler class),它允许不同的可动态添加的调度算法并存,总调度器根据调度器类的优先顺序,依次去进行调度器类的中的进程进行调度,挑选了调度器类,再在这个调度器内,使用这个调度器类的算法...Linux 调度时机 ---- 一、进程切换 从进程的角度看,CPU是共享资源,由所有的进程按特定的策略轮番使用。

    20.6K10

    linux进程调度

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

    3.2K140

    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.1K20

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

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

    1.1K10

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

    多任务 并发和并行 Linux作为一个多任务操作系统,必须支持程序的并发执行。 分类 非抢占式多任务 除非任务自己结束,否则将会一直执行。...Linux进程调度 发展历史 Linux从2.5版本开始引入一种名为的调度器,后在2.6版本中将公平的的调度概念引入了调度程序,代替之前的调度器,称为算法(完全公平调度算法)。...Linux调度算法 调度器类 Linux调度器是以模块的方式提供的,这样使得不同类型的进程按照自己的需要来选择不同的调度算法。...上面说讲到的CFS算法就是一个针对普通进程调度器类,基础的调度器会按照优先级顺序遍历调度类,拥有一个可执行进程的最高优先级的调度器类胜出,由它来选择下一个要执行的进程。...进程选择 这里便是调度的核心部分,用一句话来梗概CFS算法的核心就是选择具有最小vruntime的进程作为下一个需要调度进程

    14.9K113

    操作系统 进程线程模型 进程线程调度

    调度是分层次的,在操作系统中,一般将调度分为高级调度、中级调度和低级调度。 高级调度也称作业调度,其主要任务是按一定的原则,对磁盘中的处于后备状态的作业进行选择并创建为进程。...进程(线程)调度算法 进程(线程)调度算法解决以何中次序对各就绪进程(线程)进程处理机的分配以及按何种时间比例让进程(线程)占用处理机。...如果不对优先级进行调整,则低优先级进程很有可能产生饥饿现象。 多级反馈队列算法 以最高优先级算法作为主要的调度模式,但对于具有相同优先数的进程(线程)按先进先出调度算法处理。...多级队列反馈法就是综合了先进先出调度算法、时间片轮转法和可抢占式最高优先级算法的一种进程(线程)调度算法。...速率单调调度算法:适用于可抢先的周期性进程的经典静态实时调度算法是速率单调调度RMS。 每个周期性进程必须在其周期内完成。 没有进程依赖于任何其他进程

    2K20

    进程调度算法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....

    1.7K30

    Linux进程调度分析

    尽管我们平常接触的很多计算机(如桌面系统、网络服务器、等)负载都比较低,但是linux作为一个通用操作系统,不能假设系统负载低,必须为应付高负载下的进程调度做精心的设计。...像linux这样的通用操作系统显然没法满足这样的要求,中断处理、虚拟内存、等机制的存在给处理时间带来了很大的不确定性。硬件的cache、磁盘寻道、总线争用、也会带来不确定性。...而中断处理程序的处理过程中又可能发生新的硬件中断,中断永远嵌套不止……; 等等…… 而像linux这样号称实现了“实时”的通用操作系统,其实只是实现了“软实时”,即尽可能地满足进程的实时需求。...普通进程具体的调度算法非常复杂,并且随linux内核版本的演变也在不断更替(不仅仅是简单的调整),所以本文就不继续深入了。...有兴趣的朋友可以参考下面的链接: 《Linux 调度器发展简述》 《鼠眼看Linux调度器》 《鼠眼再看Linux调度器[1]》 《鼠眼再看Linux调度器[2]》 调度程序的效率 “优先级”明确了哪个进程应该被调度执行

    2.4K31

    Linux进程调度(三)

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

    2.4K10

    Linux进程调度学习!

    进程调度含义: 进程调度决定了将哪个进程进行执行,以及执行的时间。操作系统进行合理的进程调度,使得资源得到最大化的利用。 在单片机上,常常使用的方式是:系统初始化---->while(1){}。...(当然,单片机也可以跑类似 FreeRTOS,也可以有进程切换) 在带操作系统的 CPU 上跑的逻辑是,允许多个进程(其实就是程序) ”同时” 跑。...1、进程的优先级 调度算法中比较基本的就是靠进程的优先级来进行进程调度,比如 FreeRTOS,靠 task 的优先级来进行进程的抢占。...Linux 调度算法Linux 中有一个总的调度结构,称之为 调度器类(scheduler class),它允许不同的可动态添加的调度算法并存,总调度器根据调度器类的优先顺序,依次去进行调度器类的中的进程进行调度...Linux 调度时机: 1、进程切换: 从进程的角度看,CPU是共享资源,由所有的进程按特定的策略轮番使用。

    1.9K30
    领券