前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >Linux O(n)调度器

Linux O(n)调度器

作者头像
DragonKingZhu
发布于 2020-03-24 09:11:59
发布于 2020-03-24 09:11:59
3.4K00
代码可运行
举报
运行总次数:0
代码可运行

前面我们学习了调度器的设计需要关注的几个点,在这里复习下:

  1. 吞吐量(对应的是CPU消耗型进程)
  2. 响应速度(对应的是IO消耗型进程)
  3. 公平性,确保每个进程都可以有机会运行到
  4. 移动设备的功耗

Linux中调度器的设计,引入的概念

  1. 普通进程和实时进程使用优先级区分,0-99表示实时进程,100-139表示普通进程
  2. 实时进程采用两种调度策略SCHED_RR或者SCHED_FIFO
  3. 普通进程采用nice值进行动态调整普通进程的优先级
  4. 经常睡眠的进程尝试增大下优先级,经常长占CPU的适当减少优先级

本节我们先来学习Linux早期的调度算法的设计,先从最早的调度器算法开始,此调度器时间复杂度是O(n),所以也可以称为O(n)调度算法。我们选择的内核版本是linux-2.4.19。

O(n)调度器的实现原理

O(n)代表的是寻找一个合适的进程的时间复杂度。调度器定义了个runqueue的运行队列,将进程的状态变为Running的都会添加到此运行队列中,当然了不管是实时进程,还是普通进程都会添加到这个运行队列中。当需要从运行队列中需要一个合适的进程运行时,则就需要从队列的头遍历到尾部,所以说寻找一个合适进程的时间复杂度是O(n),当运行队列中的进程数目逐渐增大,则调度器的效率就会出现明显的下降。

运行队列中的进程是没有次序的,实时进程和普通进程是杂乱无章的在里面排序的。当需要调度器选择下一个进程的时候,则就需要从头遍历,比较每个进程的优先级,优先级高的先运行。当然了只有当实时进程运行完毕才可能轮到普通进程运行的。

struct task_struct结构

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
struct task_struct {

    long counter;
    long nice;
    unsigned long policy;
    int processor;

    unsigned long cpus_runnable, cpus_allowed;
}
  • counter代表的是进程的时间片,就是进程在一个调度周期中可与运行的时间。
  • nice代表这个进程的静态优先级。通过宏NICE_TO_TICKS,可以将对应的nice值转化为对应的时间片,存储在counter中
  • policy就是进程的调度策略,实时进程采用的是SCHED_RR或者SCHED_FIFO。普通进程采用的是SCHED_OTHER
    • SCHED_RR:同等优先级采用轮转的方式,不同优先级还是高优先级先调度
    • SCHED_FIFO:同等优先级采用先来后到的次序,就是先调度的进程如果没运行完毕,后面的只能排队。不同优先级还是高优先级的优先。如果高优先级的实时进程没运行完,低优先级的也是不能运行的。
  • pocessor: 代表当前进程运行在那个处理器上,会在SMP系统中使用
  • cpu_allowed:代表当前进程允许在那些CPU上可以运行。

时间片的计算

O(n)调度器采用的是TICK的方式,根据对应进程的nice值来计算对应的时间片的。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#if HZ < 200
#define TICK_SCALE(x)	((x) >> 2)
#elif HZ < 400
#define TICK_SCALE(x)	((x) >> 1)
#elif HZ < 800
#define TICK_SCALE(x)	(x)
#elif HZ < 1600
#define TICK_SCALE(x)	((x) << 1)
#else
#define TICK_SCALE(x)	((x) << 2)
#endif

#define NICE_TO_TICKS(nice)	(TICK_SCALE(20-(nice))+1)

nice值的取值范围是-20 ~ +19, 取值越小优先级越高。进程的默认nice值是0,则进程默认的静态优先级就等于20.

我们以100HZ来计算下,各个nice值下一个进程可以占用的时间片。

nice值

-20

-10

0

+10

+19

100HZ

11tick

8tick

6tick

3tick

1tick

时间片

110ms

80ms

60ms

30ms

10ms

当然了这些时间片是根据静态的优先级计算出来的,当进程运行起来后会对睡眠的进程做一个补偿的。

O(n)调度器算法核心

从运行队列中选择一个优先级最高的进程

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
	list_for_each(tmp, &runqueue_head) {
		p = list_entry(tmp, struct task_struct, run_list);
		if (can_schedule(p, this_cpu)) {
			int weight = goodness(p, this_cpu, prev->active_mm);
			if (weight > c)
				c = weight, next = p;
		}
	}

就是从runqueue运行队列中逐个遍历,can_schedule函数用于判断当前进程是否可以在this_cpu上运行,是针对SMP系统的。

最主要的核心算法是在goodness函数中找出优先级最高的一个进程。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{

	/*
	 * Non-RT process - normal case first.
	 */
	if (p->policy == SCHED_OTHER) {
		
		weight = p->counter;
		if (!weight)
			goto out;
			
#ifdef CONFIG_SMP
		/* Give a largish advantage to the same processor...   */
		/* (this is equivalent to penalizing other processors) */
		if (p->processor == this_cpu)
			weight += PROC_CHANGE_PENALTY;
#endif

		/* .. and a slight advantage to the current MM */
		if (p->mm == this_mm || !p->mm)
			weight += 1;
		weight += 20 - p->nice;
		goto out;
	}

}
  • 上面的代码片段是针对普通进程的。如果调度策略是SCHED_OTHER,则对应的是普通进程。如果weigt=0代表的是此进程已经没有时间片了,则直接跳出
  • 在SMP系统中,如果此进程之前是在当前CPU上运行,因为Cache缓存的特性,会给此类CPU增加对应的时间片,相对应是给惩罚其他进程
  • 如果此进程和当前进程共享一个mm_struct结构,或者当前进程是是内核线程,则增加时间片。
  • 正常情况下普通进程的动态优先级=剩余的时间片+进程的静态优先级

实时进程则是简单粗暴,直接是在实时进程的静态优先级上加上1000,因为每个实时进程的静态优先级是不一样的。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
weight = 1000 + p->rt_priority;

进程时间片的初始化

随着时间的推移,所有的进程的时间片可能都会运行,这时候就需要对所有的进程进行一次时间片的初始化动作

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
	/* Do we need to re-calculate counters? */
	if (unlikely(!c)) {
		struct task_struct *p;

		spin_unlock_irq(&runqueue_lock);
		read_lock(&tasklist_lock);
		for_each_task(p)
			p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
		read_unlock(&tasklist_lock);
		spin_lock_irq(&runqueue_lock);
		goto repeat_schedule;
	}

也就是当从运行队列中没有找到可以运行的进程时,这时候会对所有的进程重新初始化counter。当然了一直的睡眠的进程可能时间片没有运行完,则需要将睡眠进程剩余的时间片加上。但是为了防止睡眠的IO消耗型进程优先级累计过高,则需要对半分。

时间片更新

系统中的tick中断会来更新当前进程的时间片的。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void update_process_times(int user_tick)
{
	struct task_struct *p = current;
	int cpu = smp_processor_id(), system = user_tick ^ 1;

	update_one_process(p, user_tick, system, cpu);
	if (p->pid) {
		if (--p->counter <= 0) {
			p->counter = 0;
			p->need_resched = 1;
		}
		if (p->nice > 0)
			kstat.per_cpu_nice[cpu] += user_tick;
		else
			kstat.per_cpu_user[cpu] += user_tick;
		kstat.per_cpu_system[cpu] += system;
	} else if (local_bh_count(cpu) || local_irq_count(cpu) > 1)
		kstat.per_cpu_system[cpu] += system;
}

当每次tick中断到来之时,会对counter减1的。如果counter的值为0,则表示时间片已经用光,则需要设置need_resced的标志,在调度点会去判断当前进程是否设置此值,如果设置则进行调度。

O(n)调度器面临的问题

  • 时间复杂度问题,时间复杂度是O(n),当系统中的进程很少的时候性能还可以,但是当系统中的进程逐渐增多,选择下一个进程的时间则是逐渐增大。而且当系统中无可运行的进程时,重新初始化进程的时间片也是相当耗时,在系统中进程很多的情况系下。
  • SMP扩展问题。当需要picknext下一个进程时,需要对整个runqueue队列进行加锁的操作,spin_lock_irq(&runqueue_lock);当系统中进程数目比较多的时候,则在临界区的时间就比较长,导致其余的CPU自旋比较浪费
  • 实时进程的运行效率问题,因为实时进程和普通进程在一个列表中,每次查实时进程时,都需要全部扫描整个列表,导致实时进程不是很“实时”
  • CPU资源浪费问题:因为系统中只有一个runqueue,则当运行队列中的进程少于CPU的个数时,其余的CPU则几乎是idle状态,浪费资源
  • cache缓存问题:当系统中的进程逐渐减少时,原先在CPU1上运行的进程,不得不在CPU2上运行,导致在CPU2上运行时,cacheline则几乎是空白的,影响效率。
  • 总之O(n)调度器有很多问题,不过有问题肯定要解决的。所以在Linux2.6引入了O(1)的调度器。
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Linux O(1)调度器
O(n)调度器采用一个runqueue运行队列来管理所有可运行的进程,在主调度schedule函数中会选择一个优先级最高,也就是时间片最大的进程来运行,同时也会对喜欢睡眠的进程做一些补偿,去增加此类进程的时间片。当runqueue运行队列中无进程可选择时,则会对系统中所有的进程进行一次重新计算时间片的操作,同时也会对剩余时间片的进程做一次补偿。
DragonKingZhu
2020/03/24
3K0
Linux O(1)调度器
Linux Kernel调度器的过去,现在和未来
Linux Kernel Development 一书中,关于 Linux 的进程调度器并没有讲解的很全面,只是提到了 CFS 调度器的基本思想和一些实现细节;并没有 Linux 早期的调度器介绍,以及最近这些年新增的在内核源码树外维护的调度器思想。所以在经过一番搜寻后,看到了这篇论文 A complete guide to Linux process scheduling,对 Linux 的调度器历史进行了回顾,并且相对细致地讲解了 CFS 调度器。整体来说,虽然比较啰嗦,但是对于想要知道更多细节的我来说非常适合,所以就有了翻译它的冲动。当然,在学习过程也参考了其它论文。下面开启学习之旅吧,如有任何问题,欢迎指正~
刘盼
2020/04/20
2.7K0
Linux Kernel调度器的过去,现在和未来
Linux进程调度器的设计--Linux进程的管理与调度(十七)
调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换.
233333
2018/12/04
3.6K0
Linux进程调度器的设计--Linux进程的管理与调度(十七)
时间系统、进程的调度与切换
该文章介绍了Linux 系统中进程的调度、进程的优先级以及实时进程的调度策略。首先介绍了Linux 系统中的进程调度,包括不同的调度类型、调度算法和调度优先级。其次,讨论了Linux 系统中的实时进程调度,包括实时进程的定义、调度特性和实时进程的调度算法。最后,介绍了Linux 系统中进程调度的实现,包括内核中的进程管理、进程的地址空间、进程的调度和同步以及进程的内存管理。
s1mba
2017/12/28
2.5K0
时间系统、进程的调度与切换
Linux进程调度之 - O(1)调度算法
Linux是一个支持多任务的操作系统,而多个任务之间的切换是通过 调度器 来完成,调度器 使用不同的调度算法会有不同的效果。
用户7686797
2020/08/24
4.9K0
Linux进程调度之 - O(1)调度算法
吐血整理 | 肝翻 Linux 进程调度所有知识点
前面我们重点分析了如何通过 fork, vfork, pthread_create 去创建一个进程或者线程,以及后面说了它们共同调用 do_fork 的实现。现在已经知道一个进程是如何创建的,但是进程何时被执行,需要调度器来选择。所以这一节我们介绍下进程调度和进程切换的详情。
刘盼
2021/12/13
2K0
吐血整理 | 肝翻 Linux 进程调度所有知识点
Linux 进程管理
在内核层面,每个进程都是由task_struct 描述的,这个结构体非常大,可以粗略看下各主要内容:
一只小虾米
2023/03/09
10.2K0
Linux 进程管理
调度器及CFS调度器
调度:就是按照某种调度的算法设计,从进程的就绪队列中选择进程分配CPU,主要是协调进程对CPU等相关资源的使用。
laputa
2022/11/21
1.1K0
Linux内核调度分析(进程调度)
本文是《Linux内核设计与实现》第四章的阅读笔记,代码则是摘自最新的4.6版本linux源码(github),转载请注明出处。
Marky Lumin
2018/01/23
15K0
【Linux系统内核探索】进程调度
进程调度是操作系统内核的核心功能之一,负责在多个进程之间分配CPU时间,使得系统能够同时运行多个进程。因为计算机的CPU资源有限,操作系统需要决定在任何时刻哪个进程能够使用CPU执行任务,这个过程就是进程调度。 Linux进程调度经历了多个阶段的优化,目前主流的Linux内核使用的是完全公平调度器。CFS调度器的核心思想是通过精确计算每个进程的“虚拟运行时间”来决定调度的公平性。CFS调度器不会简单依赖于时间片,而是通过调度树来快速查找下一个应运行的进程。 现代的Linux调度主要依赖于Linux的CFS调度器,在2.6版本之前主要用的是Linux内核O(1)调度算法,这次我们的重点在于Linux内核O(1)调度算法。
用户11305458
2024/11/21
910
【Linux系统内核探索】进程调度
图解Linux进程调度(二)
在内核中,肯定不能对所有的进程一视同仁,有的进程需要优先运行,有的进程需要运行更长的时间
用户6280468
2022/06/09
1.7K0
图解Linux进程调度(二)
Linux调度原理介绍和应用(前篇)
提示:公众号展示代码会自动折行,建议横屏阅读 摘要 本文(有码慎入)主要介绍Linux任务调度相关的发展历史和基本原理。多年以来,内核界的黑客们一直着力于寻找既能满足高负载后台任务资源充分利用,又能满足桌面系统良好交互性的调度方法,尽管截至到目前为止仍然没有一个完美的解决方案。本文希望通过介绍调度算法的发展历程,因为任务调度本身不是一个局限于操作系统的话题,包括数据库,程序语言实现等,都会与调度相关。本文在介绍过程中,会引用Linux的代码实现作为说明,同时阐述其中的一些趣闻轶事。 调度实体 进程任务通常包
腾讯数据库技术
2018/07/26
1.4K0
CFS 调度器数据结构篇
在上一节我们了解了CFS的设计原理,包括CFS的引入,CFS是如何实现公平,CFS工作原理的。本小节我们重点在分析CFS调度器中涉及到的一些常见的数据结构,对这些数据结构做一个简单的概括,梳理各个数据结构之间的关系图出来。
DragonKingZhu
2020/03/24
1.3K0
CFS 调度器数据结构篇
实时调度类
按照POSIX标准的强制要求,除了“普通”进程之外, Linux还支持两种实时调度类。调度器结构使得实时进程可以平滑地集成到内核中,而无需修改核心调度器,这显然是调度类带来的好处。
233333
2018/12/14
8260
实时调度类
Linux核心调度器之周期性调度器scheduler_tick--Linux进程的管理与调度(十八)
因而内核提供了两个调度器主调度器,周期性调度器,分别实现如上工作, 两者合在一起就组成了核心调度器(core scheduler), 也叫通用调度器(generic scheduler).
233333
2018/12/04
2.8K0
Linux进程调度学习!
进程调度决定了将哪个进程进行执行,以及执行的时间。操作系统进行合理的进程调度,使得资源得到最大化的利用。
用户6280468
2022/04/18
1.9K0
Linux进程调度学习!
Linux 进程管理之调度和进程切换
每个CPU都有一个运行队列,每个运行队列中有三个调度队列,task作为调度实体加入到各自的调度队列中。
刘盼
2021/04/29
2K0
Linux 进程管理之调度和进程切换
CFS调度器(1)-基本原理
首先需要思考的问题是:什么是调度器(scheduler)?调度器的作用是什么?调度器是一个操作系统的核心部分。可以比作是CPU时间的管理员。调度器主要负责选择某些就绪的进程来执行。不同的调度器根据不同的方法挑选出最适合运行的进程。目前Linux支持的调度器就有RT scheduler、Deadline scheduler、CFS scheduler及Idle scheduler等。我想用一系列文章呈现Linux 调度器的设计原理。
233333
2022/05/10
9130
CFS调度器(1)-基本原理
Linux进程调度策略的发展和演变--Linux进程的管理与调度(十六)
调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换.
233333
2018/11/20
2.3K0
聊聊Linux内核进程调度下篇
进程优先级 Linux内核中进程优先级一般分为动态优先级和静态优先级,动态优先级是内核根据进程的nice值、IO密集行为或者计算密集行为以及等待时间等因素,设置给普通的进程;静态优先级是用户态应用设置给实时进程。在调度中静态优先级的进程优先级更高。 一般应用分为IO密集型和计算密集型;I/O密集型是进程执行I/O操作时候等待资源或者事件时候,数据读取到后恢复进程的运行,这样基本出于等待IO和运行之间进行交替,由于具有这样的特性,进程调度器通常会将短的CPU时间片分配给I/O密集型进程。计算密集型是进
用户4700054
2022/08/17
1.3K0
聊聊Linux内核进程调度下篇
相关推荐
Linux O(1)调度器
更多 >
领券
社区富文本编辑器全新改版!诚邀体验~
全新交互,全新视觉,新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能,全面提升创作效率和体验
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验