[转]Linux中定时器的算法实现
Linux中定时器的算法实现
定时器的作用
定时器在操作系统中起到了举足轻重的作用。在做IO操作时,需要超时机制保证任务不处于无休止的等待状态;在延时处理时,可以通过“闹表”进行相对准点的唤醒操作。在多任务操作系统中,定时器是一种非常常用的资源。
对于熟悉硬件的工程师,定时器一般是芯片中的硬件定时器资源,实际上在操作系统中指的定时器资源并非局限于硬件资源,更重要的是软件定时器资源。硬件定时器资源通常实现操作系统的心跳,在uc/os中心跳频率默认值为200Hz,也就是5ms产生一次操作系统心跳。软件定时器是在操作系统心跳的基础上实现的。
下面对Linux中的定时器实现算法作详细分析。
Linux中定时器的实现
Linux中的定时器实现有点意思,在定时器较多的情况下实现效率较高,并且该算法思想可以在其它嵌入式系统中得以应用。
定时器实现的核心思想是采用了多级hash链表,并且每级hash的长度都不一样,多级hash链表可以类比为秒、分、时、天、月,每级的时间跨度都不一样。Linux中实现的五级hash链表关系如下图所示:
如上图所示为5级hash链表,V1为最低层的hash链表,V5为最顶层的hash链表。V1~V5 hash table的每一项为一条定时器链表,新添加的定时器会通过expire(定时时间值)和base->timer_jiffies(当前定时值)的差值expire_time来索引应该挂接到哪一层hash table中,并且索引到hash table中的具体项,然后将新增加的定时器加入到该项的timer list中。hash长度从V1到V5变得越来越大。V1的hash长度为1个jiffies,也就是说V1的hash table每一项为同一jiffies的定时器链表;V5的hash长度为64M jiffies,也就是hash table的每一项会链接连续64M jiffies定时长度的timer。不同层次的hash table具有不同的hash长度,离当前时间点越远的timer位于hash长度越长的table中,因为这些定时器还需要等待较长时间才能得以处理,所以可以采用大块分类的方法,离当前时间点越近的timer需要细粒度的切分,因为jiffies每变化一次都需要处理timer,所以最低层的table按一个jiffies进行切分。随着时间点的后移,不断的对最底层的hash table进行处理,并且通过当前时间点索引上层hash table,将定时器分配到下几级的hash table中。每
相关文档:
转载:
现在linux下有越来越多的优秀的播放软件,xmms,m-player,beep-media-player,totme,rhythmbox,等等等等,但是这些播放软件都不能很好的解决mp3文件中文信息乱码的问题。
究其原因,现在网上绝大多数(99%以上)的mp3都是网友在windows下压制的,文字信息编码方式自然是GBK,到了linux下面就没有lftp ......
/ 根目录
/bin 常用的命令 binary file 的目錄
/boot 存放系统启动时必须读取的档案,包括核心 (kernel) 在内
/boot/grub/menu.lst GRUB ......
看linux内核很容易被struct address_space 这个结构迷惑,它是代表某个地址空间吗?实际上不是的,它是用于管理文件(struct inode)映射到内存的页面(struct page)的;与之对应,address_space_operations 就是用来操作该文件映射到内存的页面,比如把内存中的修改写回文件、从文件中读入数据到页面缓冲等。
& ......
Linux + JDK + Tomcat + MySQL + JDBC 安装手记
一、Red Hat Linux
1.分区
| swap & ......
Linux是一套免费使用和自由传播的类Unix操作系统,它最先用于基于x86系列CPU的计算机上。这个系统是由世界各地的成千上万的程序员设计和实现的。其目的是建立不受任何商品化软件的版权制约的、全世界都能自由使用的Unix兼容产品。
我们不去介绍操作系统的历史了,也不管操作系统这门学科上对操作系统的分类了,闲话少说,L ......