linux 内核 hrtimer,Linux hrtimer分析（一）

本文分析了Linux2.6.29中hrtimer的实现。

Linux2.6中实现了一种新的定时器hrtimer。与传统定时器使用时间轮算法不同，hrtimer使用了红黑树算法。hrtimer本身可以配置成高精度和普通精度两种，在单CPU系统和多CPU系统中的实现也有区别。这里先分析最简单的配置成普通精度、单CPU的情况。配置成高精度的情况见后续文章。

1. 时钟源的定义

为了实现hrtimer，Linux为系统中每一个CPU定义了一个hrtimer_cpu_base，这个结构体的定义如下：

struct hrtimer_cpu_base {

spinlock_t                     lock;                                          // 自旋锁

// 时钟源

struct hrtimer_clock_base     clock_base[HRTIMER_MAX_CLOCK_BASES];

// 所有到期的且配置为软中断的定时器，见下文

struct list_head              cb_pending;

#ifdef CONFIG_HIGH_RES_TIMERS        // 高精度配置，这里暂不考虑

ktime_t                         expires_next;

int                         hres_active;

unsigned long                nr_events;

#endif

};

在hrtimer.c中，有为每个CPU具体定义hrtimer_cpu_base的代码：

DEFINE_PER_CPU(struct hrtimer_cpu_base, hrtimer_bases) =

{

.clock_base =

{

{

.index = CLOCK_REALTIME,

.get_time = &ktime_get_real,

.resolution = KTIME_LOW_RES,

},

{

.index = CLOCK_MONOTONIC,

.get_time = &ktime_get,

.resolution = KTIME_LOW_RES,

},

}

};

可以看出，每个CPU都必须定义两个时钟源：REAL和MONOTONIC。

REAL代表实时时钟，MONOTONIC代表单调递增时钟。两者的区别在于，当用户更改计算机时间时，REAL时钟会收到影响，但MONOTONIC不受影响。这可以从它们两个的get_time函数指针看出来，REAL时钟指向的是ktime_get_real，MONOTONIC指向的是ktime_get。

时钟源的结构体定义为struct hrtimer_clock_base，其中有两个域struct rb_node       *first和struct rb_root   active，这两个域维护了hrtimer的红黑树。也就是说，每一个hrtimer_clock_base都维护了自己的一个红黑树。

hrtimer在初始化时，都需要加入到某一个时钟源的红黑树中，这个时钟源要么是REAL，要么是MONOTONIC，这个关联通过struct hrtimer的base域实现。

2. hrtimer的基本操作

Linux的传统定时器通过时间轮算法实现(timer.c)，但hrtimer通过红黑树算法实现。在struct hrtimer里面有一个node域，类型为struct rb_node，这个域代表了hrtimer在红黑树中的位置。

hrtimer_start

hrtimer_start函数将一个hrtimer加入到一个按照到期时间排序的红黑树中，其主要流程为：

int hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode);

//根据time和mode参数的值计算hrtimer的超时时间，并设置到timer->expire域。

// expire设置的是绝对时间，所以如果参数mode的值为HRTIMER_MODE_REL(即参数tim的值为相对时间)，那么需要将tim的值修正为绝对时间：

//     expire = tim + timer->base->get_time()。(注意本文只研究单CPU的情况)

//调用enqueue_hrtimer，将hrtimer加入到红黑树中。

hrtimer的到期

hrtimer在hrtimer_run_queues函数中判断是否到期执行。hrtimer_run_queues的调用链为：Linux的系统时钟函数->update_process_times->run_local_timers->hrtimer_run_queues。

void hrtimer_run_queues(void)

// 判断是否是高精度模式，如果是高精度模式，立即返回。本文暂不考虑这种情况。

// 对每一个时钟源(REAL和MONOTONIC)的红黑树，按到期先后顺序检查hrtimer，看它们是否到期(将定时器与时钟源的softirq_time比较)。如果到期，就把这个到期的定时器取出，然后按照定时器的具体模式执行相应的操作：

l 如果定时器模式为HRTIMER_CB_SOFTIRQ，那么将定时器搬到hrtimer_cpu_base的cb_pending队列

l 调用__run_hrtimer，在__run_hrtimer中执行定时器的回调函数。

在没有配置高精度模式时，cb_pending队列中的定时器会在T_SOFTIRQ软中断中执行。调用链为

run_timer_softirq-> hrtimer_run_pending-> run_hrtimer_pending-> run_hrtimer_pending

hrtimer_cancel

hrtimer_cancel函数的作用是删除一个正在排队的定时器。这里分三种情况，一种是定时器已到期，并且设置了软中断模式；第二种是没有到期，还在红黑树中；第三种是定时器正在执行。

l 第一种情况，定时器被挂在hrtimer_cpu_base的cb_pending队列中，所以需要把它从pending队列中移出。

l 第二种情况，定时器还在红黑树中，那么把它从红黑树中移出。由于本文暂时只考虑高精度没有打开的情况，所以先不研究定时器正好排在红黑树第一个时的情况(即代码中调用hrtimer_force_reprogram函数的部分)。

l 第三种情况删除失败，hrtimer_cancel函数会循环重试，等到定时器执行完的时候再删除。(这在多CPU系统中可能会发生)

3. 未使能高精度模式时与传统timer的区别

l 传统timer使用时间轮算法，hrtimer使用红黑树算法。

l 传统timer在软中断中执行，hrtimer在硬中断中执行(update_process_times -> run_local_timers -> hrtimer_run_queues)。如果hrtimer设置了HRTIMER_CB_SOFTIRQ模式，那么timer会被移到pending队列，然后再由软中断执行。

Linux hrtimer分析(2)

http://blog.csdn.net/angle_birds/article/details/17375901 本文介绍Linux2.6.29中,配置高精度模式的hrtimer与未配置高精度模式时 ...

linux内核分析作业8：理解进程调度时机跟踪分析进程调度与进程切换的过程

1. 实验目的 选择一个系统调用(13号系统调用time除外),系统调用列表,使用库函数API和C代码中嵌入汇编代码两种方式使用同一个系统调用 分析汇编代码调用系统调用的工作过程,特别是参数的传递的方 ...

Linux内核分析作业7：Linux内核如何装载和启动一个可执行程序

1.可执行文件的格式 在 Linux 平台下主要有以下三种可执行文件格式: 1.a.out(assembler and link editor output 汇编器和链接编辑器的输出) ...

linux内核分析作业6：分析Linux内核创建一个新进程的过程

task_struct结构: struct task_struct {   volatile long state;进程状态  void *stack; 堆栈  pid_t pid; 进程标识符  u ...

linux内核分析作业5：分析system_call中断处理过程

1.增加 Menu 内核命令行 调试系统调用. 步骤:删除menu git clone        (tab) make rootfs 这就是我们将 fork 函数写入 Menu 系统内核后的效果, ...

linux内核分析作业：以一简单C程序为例，分析汇编代码理解计算机如何工作

一.实验 使用gcc –S –o main.s main.c -m32 命令编译成汇编代码,如下代码中的数字请自行修改以防与他人雷同 int g(int x) { return x + 3; } in ...

linux内核分析作业：操作系统是如何工作的进行:完成一个简单的时间片轮转多道程序内核代码

计算机如何工作 三个法宝:存储程序计算机.函数调用堆栈.中断机制. 堆栈 函数调用框架 传递参数 保存返回地址 提供局部变量空间 堆栈相关的寄存器 Esp 堆栈指针  (stack pointer) ...

linux内核分析作业3：跟踪分析Linux内核的启动过程

内核源码目录 1. arch:录下x86重点关注 2. init:目录下main.c中的start_kernel是启动内核的起点 3. ipc:进程间通信的目录 实验 使用实验楼的虚拟机打开shell ...

linux内核分析作业4：使用库函数API和C代码中嵌入汇编代码两种方式使用同一个系统调用

系统调用:库函数封装了系统调用,通过库函数和系统调用打交道 用户态:低级别执行状态,代码的掌控范围会受到限制. 内核态:高执行级别,代码可移植性特权指令,访问任意物理地址 为什么划分级别:如果全部特权 ...

随机推荐

清除PDF里的元数据和机密信息的方法

相信很多人都知道,PDF文档的表现形式可以大不相同,它们可能包含某些数据,乍一看根本看不见,那些数据可能是不适合共享的信息-比如元数据(作者.主题.关键词).书签.扫描文档里的文本层等,通过ABBYY ...

让java代码在Idea外面运行起来

今天在写聊天程序,终于写到双方通信的时候,发现idea只能开一个客户端.虽说可以开多线程来实现多开,但是懒得改动代码,所以我就试试能不能把jar包导出来运行.首先我用maven自带的工具打了jar包, ...

Linux下编译器的安装

一.Linux下gcc/g++/gfortran的安装 (1).gcc Linux下自带gcc编译器.可以通过“gcc -v”命令来查看是否安装. (2).g++安装g++编译器,可以通过命令“sud ...

CF1121C 模拟

恶心场恶心题,,round千万不能用库函数的.. /*枚举时间轴t,r是当前完成比例, 记录每个测试的开始时间si,如果有t-si等于r,那么这个测试就标记一下 优先队列存储每个测试,按照si+ai的 ...

Java学习过程

按照这个流程巩固自己学习的东西吧

记在Archlinux中安装python的pymssql模块过程中遇到的问题

为什么要安装这个模块?因为要连接SQLServer数据库. 看到可以使用pyodbc这个模块进行连接,但对odbc不熟悉,所以选用了看起来更简单的 pymssql. 直接执行: pip install ...

清理本地Maven仓库

目录 1.清理target 2.清理该项目依赖的本地仓库中的maven包 3.清理maven本地仓库中下载失败的包 参考: 1.清理target mvn clean -U 2.清理该项目依赖的本地仓库 ...

QtCreator中F1帮助不能使用的解决方法

环境:ubuntu11.04 在Qt中按F1跳转帮助是一个很方便的东东,点击左边的Help图标也是一样的功能.我今天遇到的问题是F1跳转出错,找不到文档: “No documentation avai ...

char型指针和字符串字面量和字符数组

1.当一个char型指针指向一个字符串字面量(也就是常量字符串)时,该指针必须由const修饰,否则,系统会给出deprecated(不赞成)的警告.原因是:字符串字面量不可改变,当它被一个非cons ...

pip第三方模块

在安装好pip的情况下,在cmd窗口调用命令:pip install package -i --trusted-host http://pypi.douban.com/simple(这是豆瓣的源)