Chinaunix首页 | 论坛 | 博客

OS

  • 博客访问: 2280160
  • 博文数量: 691
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2660
  • 用 户 组: 普通用户
  • 注册时间: 2014-04-05 12:49
个人简介

不浮躁

文章分类

全部博文(691)

文章存档

2019年(1)

2017年(12)

2016年(99)

2015年(207)

2014年(372)

分类: LINUX

2014-11-15 12:54:53

Linux调度主要是在一个runqueue结构体上操作。runqueue结构体有一个prio_array结构体数组,该数组中有个两个prio_array结构体。prio_array结构体的定义如下:

struct prio_array 

  int nr_active /* number of tasks in the queue */; 
  unsigned long bitmap[BITMAP_SIZE]; /* priority bitmap */ 
  struct list_head queue[MAX_PRIO]; /* priority queue */ 
}

这两个prio_array,一个挂着expired task(时间片已经用完的task),另一个挂着active task(时间片尚未用完的task)。当active task为空时,就交换这两个prio_array的指针值就OK了。

接下来讲解prio_array中的成员

nr_active:就不用多说了,就表示该prio_array结构体上挂着多少个任务。

struct list_head queue[MAX_PRIO]:这是一个指针数组,每个数组标记一个链表头,每个链表头上挂着一串相同优先级的task。

unsigned long bitmap[BITMAP_SIZE]:这个成员的每一个表示对应的优先级的task链表上是否为空。

有了上面的基础,接下来就讲解如何实现O(1)调度,当要调度程序时,

1)首先找到bitmap成员上第一个为 1 的bit位置,比如说bitmap的第8位为1,则表示前面0~7高优先级的task链表上没有task。

2)然后访问struct list_head queue[MAX_PRIO]数组的第八个成员,该成员是优先级为8的task链表的表头,

3)最后通过表头取下第一个task,再将其调度上CPU,这样就实现了O(1)调度。


阅读(745) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~