博客

4.4.1


进程内核

栈

每个进程都有自己的内核

栈

。当进程从用户

态进入

内核态时，

CPU

就自动地设置该进程的内核

栈

，也就是说，

CPU

从任务状态段

TSS

中装入内核栈指针

esp

（参见下一章的进程切换一节）。

X86


内核

栈

的分布如图

4.2

所示：

图

4.2

内核

栈

的分布图

在


Intel


系统中，

栈

起始于末端，并朝这个内存区开始的方向增长。从

用户态刚切换到

内核态以后，进程的内核

栈

总是空的，因此，


esp


寄存器直接指向这个内存区的顶端。


在图

4.2

中，从用户态切换到内核态后，

esp

寄存器包含的地址为

0x018fc00

。进程描述符存放在从

0x015fa00

开始的地址。只要把数据写进

栈

中，

esp

的值就递减。

在／

include/linux/sched.h

中定义了如下一个联合结构：

union

task_union {

struct

task_struct task;

unsigned

long stack[2408];

};

从这个结构可以看出，内核

栈

占

8kb

的内存区。实际上，进程的

task_struct

结构所占的内存是由内核动态分配的，更确切地说，内核根本不给

task_struct

分配内存，而仅仅给内核

栈

分配

8K

的内存，并把其中的一部分给

task_struct

使用。

task_struct


结构大约占

1K

字节左右，其具体数字与内核版本有关，因为不同的

版本其域稍有

不同。因此，内核

栈

的大小不能超过

7K

，否则，内核

栈

会覆盖

task_struct

结构，从而导致内核崩溃。不过，

7K

大小对内核

栈

已足够。

把

task_struct

结构与内核

栈

放在一起具有以下好处：

·




内核可以方便而快速地找到这个结构，用伪代码描述如下：

task_struct = (struct task_struct *) STACK_POINTER & 0xffffe000

·




避免在创建进程时动态分配额外的内存

·




task_struct


结构的起始地址总是开始于页大小（

PAGE_SIZE

）的边界。

4.




5.1


哈希表

哈希表是进行快速查找的一种有效的组织方式。

Linu

在进程中引入的哈希表叫做

pidhash

，在

include/linux/sched.h

中定义如下：

#define PIDHASH_SZ (4096 >> 2)

extern



struct task_struct *pidhash[PIDHASH_SZ];

#define pid_hashfn(x)  ((((x) >> 8) ^ (x)) & (PIDHASH_SZ – 1))

其中，

PIDHASH_SZ

为表中元素的个数，表中的元素是指向

task_struct

结构的指针。

pid_hashfn

为哈希函数，

把进程

的

PID

转换为表的索引。通过这个函数，可以

把进程

的

PID

均匀地散列在它们的域（

0

到

PID_MAX-1

）中。

在数据结构课程中我们已经了解到，哈希函数并不总能确保

PID

与表的索引一一对应，两个不同的

PID

散列到相同的索引称为冲突。

Linux


利用链地址法来处理冲突的

PID

：也就是说，每一表项是由冲突的

PID

组成的双向链表，这种链表是由

task_struct





结构中的


pidhash_next


和


pidhash_pprev



域实现



的，同一链表中


pid


的大小由小到大排列。如图


4.3


所示。

图


4.3


链地址法处理冲突时的哈希表

在哈希表


pidhash


中


插入和删除一个进程时可以调用


hash_ pid( )


和


unhash_ pid( )


函数。对于一个给定的


pid


，可以通过


find_task_by_pid()


函数快速地找到对应的进程：

static



inline struct task_struct *find_task_by_pid(int pid)

{

struct

task_struct *p, **htable =& pidhash[pid_hashfn(pid)];

for(

p = *htable; p && p->pid != pid; p = p->pidhash_next)

;

return

p;

}

4.




5.2


双向循环链表

哈希表的主要作用是根据进程的

pid

可以快速地找到对应的进程，但它没有反映进程创建的顺序，也无法反映进程之间的亲属关系，因此引入双向循环链表。每个进程

task_struct

结构中的


prev_task


和


next_task


域用来实现这种链表，如图


4.4


所示

图


4.4


双向循环链表

宏


SET_LINK


用来在该链表中插入一个元素：

#define SET_

LINKS(

p) do { \

(p)->next_task =& init_task; \

(p)->prev_task = init_task.prev_task; \

init_task.prev_task->next_task = (p); \

init_task.prev_task = (p); \

(p)->p_ysptr = NULL; \

if

(((p)->p_osptr = (p)->p_pptr->p_cptr) != NULL) \

(p)->p_osptr->p_ysptr = p; \

(p)->p_pptr->p_cptr = p; \

} while (0)

从这段代码可以看出，链表的头和

尾都

为

init_task

，它对应的是进程

0

（

pid

为

0

），也就是所谓的空进程，它是所有进程的祖先。这个宏

把进程

之间的亲属关系也链接起来。另外，还有一个宏

for_each_task()

：

#define for_each_

task(

p) \

for

(p = &init_task ; (p = p->next_task) !=& init_task ; )

这个宏是循环控制语句

,

注意

init_task

的作用

,

因为

空进程

是一个永远不存在的进程

,

因此用它做链表的头和

尾是

安全的。

因为进程的双向循环链表是一个临界资源

,

因此在使用这个宏时一定要加锁

,

使用完后开锁。

4.5.3





运行队列

当内核要寻找一个新的进程在

CPU

上运行时，必须只考虑处于可运行状态的进程，（


即在


TASK_RUNNING


状态的进程），因为扫描整个进程链表是相当低效的，所以引入了可运行状态进程的双向循环链表，也叫运行队列（


runqueue


）。

运行队列容纳了系统中所有可以运行的进程，它是一个双向循环队列，其结构如下：

图

4. 5





进程的运行队列链表

该队列通过

task_struct

结构中的两个指针

run_list

链表来维持。队列的标志有两个：一个是“空进程”

idle_task

、一个是队列的长度。

有两个特殊的进程永远在运行队列中待着：当前进程和空进程。前面我们讨论过，当前进程就是由

cureent

指针所指向的进程，也就是当前运行着的进程，但是请注意，

current

指针在调度过程中（调度程序执行时）是没有意义的，为什么这么说呢？调度前，当前进程正在运行，当出现某种调度时机引发了进程调度，先前运行着的进程处于什么状态是不可知的，多数情况下处于等待状态，所以这时候

current

是没有意义的，直到调度程序选定某个进程投入运行后，

current

才真正指向了当前运行进程；

空进程

是个比较特殊的进程，只有系统中没有进程可运行时它才会被执行，

Linux

将它看作运行队列的头，当调度程序遍历运行队列，是从

idle_task

开始、至

idle_task

结束的，在调度程序运行过程中，允许队列中加入新出现的可运行进程，新出现的可运行进程插入到队尾，这样的好处是不会影响到调度程序所要遍历的队列成员，可见，

idle_task

是运行队列很重要的标志。

另一个重要标志是队列长度，也就是系统中处于可运行状态（

TASK_RUNNING

）的进程数目，用全局整型变量

nr_running

表示，在

/kernel/fork.c

中定义如下：

int nr_running=1


；

若

nr_running

为

0

，就表示队列中只有空进程。在这里要说明一下：若

nr_running

为

0

，则系统中的当前进程和

空进程

就是同一个进程。但是

Linux

会充分利用

CPU

而尽量避免出现这种情况。

4.5.4


等待队列

在

2.4

版本中，引入了一种特殊的链表

–

通用双向链表，它是内核中实现其它链表的基础，也是面向对象的思想在

C

语言中的应用。在等待队列的实现中多次涉及与此链表相关的内容。

1


．通用双向链表

在

include/linux/list.h

中定义了这种链表：

struct



list_head {

struct

list_head *next, *prev;

};

这是双向链表的一个基本框架，在其它使用链表的地方就可以使用它来定义任意一个双向链表，例如：

struct



foo_list {

int

data;

struct

list_head list;

};

对于

list_head

类型的链表，

Linux

定义了五个宏：

#define LIST_HEAD_

INIT(

name) { &(name), &(name) }

#define LIST_

HEAD(

name) \

struct

list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_

HEAD(

ptr) do { \

(

ptr

)->next = (ptr); (ptr

)-

>prev = (ptr); \

} while (0)

#define list_

entry(

ptr, type, member) \

((type *

)(

(char *)(ptr)-(unsigned long)(&((type *)0)->member)))

#define list_for_

each(

pos, head) \

for

(pos = (head)->next; pos != (head); pos = pos->next)

前三个

宏都是

初始化一个空的链表，但用法不同，

LIST_HEAD_INIT()

在声明时使用，用来初始化结构元素，第二个宏用在静态变量初始化的声明中，而第三个宏用在函数内部。

其中，最难理解的宏为

list_entry

（），在内核代码的很多处都用到这个宏，例如，在调度程序中，从运行队列中选择一个最值得运行的进程，部分代码如下：

static



LIST_HEAD(runqueue_head);

struct



list_head *tmp;

struct



task_struct *p;

list_for_

each(

tmp,& runqueue_head) {

p = list_

entry(

tmp, struct task_struct, run_list);

if

(can_schedule(p)) {

int

weight = goodness(p, this_cpu, prev->active_mm);

if

(weight > c)

c = weight, next = p;

}

}

从这段代码可以分析出

list_entry(ptr, type, member)


宏及参数

的含义：

ptr

是指向

list_head

类型链表的指针，

type

为一个结构，而

member

为结构

type

中的一个域，类型为

list_head

，这个宏返回指向

type

结构的指针。在内核代码中大量引用了这个宏，因此，搞清楚这个宏的含义和用法非常重要。

另外，对

list_head

类型的链表进行删除和插入（头或尾）的宏为

list_del()/list_add()/list_add_tail()

，在内核的其它函数中可以调用这些宏。例如，从运行队列中删除、增加及移动一个任务的代码如下：

static



inline void del_from_runqueue(struct task_struct * p)

{

nr_running–

;

list_

del(

&p->run_list);

p

->run_list.next = NULL;

}

static



inline void add_to_runqueue(struct task_struct * p)

{

list_

add(

&p->run_list, &runqueue_head);

nr_running

++;

}

static



inline void move_last_runqueue(struct task_struct * p)

{

list_

del(

&p->run_list);

list_add_

tail(

&p->run_list,& runqueue_head);

}

static



inline void move_first_runqueue(struct task_struct * p)

{

list_

del(

&p->run_list);

list_

add(

&p->run_list,& runqueue_head);

}

2.


等待队列

运行队列链表把处于

TASK_RUNNING

状态的所有进程组织在一起。当要把其他状态的进程分组时，不同的状态要求不同的处理，

Linux

选择了下列方式之一：

·




TASK_STOPPED

或

TASK_ZOMBIE

状态的进程

不

链接在专门的链表中，也没必要把它们分组，因为父进程可以通过进程的

PID

，或进程间的亲属关系检索到子进程。

·



把

TASK_INTERRUPTIBLE

或

TASK_UNINTERRUPTIBLE

状态的进程再分成很多类，其每一类对应一个特定的事件。在这种情况下，进程状态提供的信息满足不了快速检索进程，因此，有必要引入另外的进程链表。这些链表叫等待队列。

等待队列在内核中有很多用途，尤其对中断处理、进程同步及定时用处更大。因为这些内容在以后的章节中讨论，我们只在这里说明，进程必须经常等待某些事件的发生，例如，等待一个磁盘操作的终止，等待释放系统资源，或等待时间走过固定的间隔。等待队列实现在事件上的条件等待，也就是说，希望等待特定事件的进程把自己放进合适的等待队列，并放弃控制权。因此，等待队列表示一组睡眠的进程，当某一条件变为真时，由内核唤醒它们。等待队列由循环链表实现。在


2.4


的版本中，关于等待队列的定义如下（为了描述方便，有所简化）：

struct



__wait_queue {

unsigned

int flags;

struct

task_struct * task;

struct

list_head task_list;

};

typedef



struct __wait_queue wait_queue_t;

另外，关于等待队列另一个重要的数据结构—等待队列首部的描述如下：

struct



__wait_queue_head {

wq_lock_t

lock;

struct

list_head task_list;

};

typedef



struct __wait_queue_head wait_queue_head_t;

在这两个数据结构的定义中，都涉及

到类型

为

list_head

的链表，这与

2.2

版定义是不同的，在

2.2

版中的定义为：

struct



wait_queue {

struct

task_struct * task;

struct

wait_queue * next;

};

typedef



struct wait_queue wait_queue_t;

typedef



struct wait_queue *wait_queue_head_t;

这里要特别强调的是，

2.4

版中对等待队列的操作函数和

宏比


2.2

版丰富了，而在你编写设备驱动程序时会用到这些函数和

宏，

因此，要注意

2.2

到

2.4

函数的移植问题。下面给出

2.4

版中的一些主要函数及其功能：

init_waitqueue_head


（）—对等待队列首部进行初始化

init_waitqueue_entry


（）－对要加入等待队列的元素进行初始化

waitqueue_active


（）

—判断

等待队列中已经没有等待的进程

add_wait_queue


（）—给等待队列中增加一个元素

remove_wait_queue


（）—从等待队列中删除一个元素

注意，在以上函数的实现中，都调用了对

list_head

类型链表的操作函数（

list_del()/list_add()/list_add_tail()

），因此说，

list_head

类型相当于

C++

中的基类型，这也是对

2.2

版的极大改进。

希望等待一个特定事件的进程能调用下列函数中的任一

个

：

·




sleep_on(  )

函数对当前的进程起作用，我们把当前进程叫做

P

：

sleep_

on(

wait_queue_head_t *q)

{

SLEEP_ON_VAR

／＊宏定义，用来初始化要插入到等待队列中的元素＊／

current

->state = TASK_UNINTERRUPTIBLE;

SLEEP_ON_HEAD

／＊宏定义，把

P

插入到等待队列 ＊／

schedule(

);

SLEEP_ON_TAIL

／＊宏定义， 把

P

从等待队列中删除 ＊／

}

这个函数把

P

的状态设置为

TASK_UNINTERRUPTIBLE

，并把

P

插入等待队列。然后，它调用调度程序恢复另一个程序的执行。当

P

被唤醒时，调度程序恢复

sleep_on( )

函数的执行，把

P

从等待队列中删除。

·




interruptible_sleep_on(  )

与

sleep_on(  )

函数是一样的，但稍有不同，前者

把进程


P

的状态设置为

TASK_INTERRUPTIBLE

而不是

TASK_UNINTERRUPTIBLE

，因此，通过接受一个信号可以唤醒

P

。

·




sleep_on_timeout(  )

和

interruptible_sleep_on_timeout(  )

与前面情况类似，但它们允许调用者定义一个时间间隔，过了这个间隔以后，内核唤醒进程。为了做到这点，它们调用

schedule_timeout( )

函数而不是

schedule(  )

函数。

利用


wake_up


或者


wake_up_interruptible


宏，让插入等待队列中的进程进入


TASK_RUNNING


状态，这两个

宏最终

都调用了


try_to_wake_up( )


函数：

static

inline int try_to_wake_up(struct task_struct * p, int synchronous)

{

unsigned

long flags;

int

success = 0;

spin_lock_irqsave(&runqueue_lock, flags); /


＊加锁＊／

p

->state = TASK_RUNNING;

if (task_on_runqueue(p))


／＊判断


p


是否已经在运行队列＊／

goto

out;

add_to_runqueue(p);


／＊不在，则把


p


插入到运行队列＊／

if

(!synchronous || !(p->cpus_allowed & (1 << smp_processor_id())))


／

reschedule_

idle(

p);

success

= 1;

out

:

spin_unlock_irqrestore(&runqueue_lock, flags);


／＊开锁＊／

return

success;

}

在这个函数中，


p


为要唤醒的进程。如果


p


不在运行队列中，则把它放入运行队列。如果重新调度正在进行的过程中，则调用


reschedule_idle


（）函数，这个函数决定进程


p


是否应该抢占某一


CPU


上的当前进程（参见下一章）。

实际上，在内核的其它部分，最常用的还是


wake_up


或者


wake_up_interruptible


宏，也就是说，如果你要在

内核级

进行编程，只需调用其中的一个宏。例如一个简单的实时时钟（


RTC


）中断程序如下：

static DECLARE_WAIT_QUEUE_HEAD(rtc_wait);


／＊初始化等待队列首部＊／

void



rtc_interrupt(int irq, void *dev_id, struct pt_regs *regs)

{

spin_

lock(

&rtc_lock);

rtc_irq_data = CMOS_

READ(

RTC_INTR_FLAGS);

spin_

unlock(

&rtc_lock);

wake_up_

interruptible(

&rtc_wait);

}

这个中断处理程序通过从实时时钟的

I/O

端口（


CMOS_READ



宏产生



一对


outb/inb


）读取数据，然后唤醒在


rtc_wait


等待队列上睡眠的任务。