首页 > 代码库 > hdu-4302-Holedox Eating-线段树-单点更新,有策略的单点查询

hdu-4302-Holedox Eating-线段树-单点更新,有策略的单点查询

软中断

软中断的分配时静态的(即在编译时定义),而tasklet的分配和初始化可以在运行时进行。

软中断(即便是同一种类型的软中断)可以并发地运行在多个CPU上。因此,软中断是可重入函数而且必须明确地使用自旋锁保护其数据结构。tasklet不必担心这些问题,因为内核对tasklet的执行进行了更加严格的控制。相同类型的tasklet总是被串行执行。

换句话说就是:不能在两个CPU上同时运行相同类型的tasklet。但是,类型不同的tasklet可以在几个CPU上并发执行。tasklet的串行化使tasklet函数不必是可重入的

软中断           下标    说明

HI_SOFTIRQ      0      处理高优先级的tasklet

TIMER_SOFTIRQ   1      和时钟中断相关的tasklet

NET_TX_SOFTIRQ  2      把数据包传送到网卡

NET_RX_SOFTIRQ  3      从网卡接收数据包

SCSI_SOFTIRQ    4      SCSI命令的后台中断处理

TASKLET_SOFTIRQ 5      处理常规tasklet


thread_info->preempt_count

preempt_count字段

位              描述

0~7             抢占计数器(max value=http://www.mamicode.com/255)

8~15            软中断计数器(max value=http://www.mamicode.com/255)

16~27           硬中断计数器(max value=http://www.mamicode.com/255)

28              PREEMPT_ACTIVE标志

第一个计数器记录显式禁用本地CPU内核抢占的次数,值等于0表示允许内核抢占。

第二个计数器表示可延迟函数被禁用的程度(值为0表示可延迟函数处于激活状态)。

第三个计数器表示在本地CPU上中断处理程序的嵌套数。

处理软中断

open_softirq()     函数处理软中断的初始化

raise_softirq()    函数用来激活软中断

inline void raise_softirq_irqoff(unsigned int nr)
{
	__raise_softirq_irqoff(nr);

	/*
	 * If we're in an interrupt or softirq, we're done
	 * (this also catches softirq-disabled code). We will
	 * actually run the softirq once we return from
	 * the irq or softirq.
	 *
	 * Otherwise we wake up ksoftirqd to make sure we
	 * schedule the softirq soon.
	 */
	if (!in_interrupt())
		wakeup_softirqd();
}

void raise_softirq(unsigned int nr)
{
	unsigned long flags;

	local_irq_save(flags);
	raise_softirq_irqoff(nr);
	local_irq_restore(flags);
}

raise_softirq()函数执行下面的操作:

1、执行local_irq_save宏以保存eflags寄存器IF标志状态并禁用本地CPU上的中断。

2、把软中断标记为挂起状态,这是通过设置本地CPU的软中断掩码中与下标nr相关的位来实现的

3、如果in_interrupt()产生为1的值,则跳转到5。这种情况说明:要么已经在中断上下文中调用了raise_softirq(),要么当前禁用了软中断。

4、否则,就在需要的时候去调用wakeup_softirqd()以唤醒本地CPU的ksoftirqd内核线程。

5、执行local_irq_restore宏,恢复在第1步保存的IF标志的状态。

在以下几种情况周期性地检查是否有软中断要执行:

a、当内核调用local_bh_enable()函数激活本地CPU的软中断时

b、当do_IRQ()完成了I/O中断的处理时或调用irq_exit()宏时

c、如果系统使用I/O APIC,则当smp_apic_timer_interrupt()函数处理完本地定时器中断时

d、在多处理器系统中,当CPU处理完被CALL_FUNCTION_VECTOR处理器间中断所触发的函数时

e、当一个特殊的ksoftirqd/n内核线程被唤醒时

ksoftirqd内核线程

每个ksoftirqd/n内核线程都运行ksoftirqd()函数,该函数实际上执行下列的循环:

static int ksoftirqd(void * __bind_cpu)
{
	set_user_nice(current, 19);
	current->flags |= PF_NOFREEZE;

	set_current_state(TASK_INTERRUPTIBLE);

	while (!kthread_should_stop()) {
		if (!local_softirq_pending())
			schedule();

		__set_current_state(TASK_RUNNING);

		while (local_softirq_pending()) {
			/* Preempt disable stops cpu going offline.
			   If already offline, we'll be on wrong CPU:
			   don't process */
			preempt_disable();
			if (cpu_is_offline((long)__bind_cpu))
				goto wait_to_die;
			do_softirq();
			preempt_enable();
			cond_resched();
		}

		set_current_state(TASK_INTERRUPTIBLE);
	}
	__set_current_state(TASK_RUNNING);
	return 0;

wait_to_die:
	preempt_enable();
	/* Wait for kthread_stop */
	set_current_state(TASK_INTERRUPTIBLE);
	while (!kthread_should_stop()) {
		schedule();
		set_current_state(TASK_INTERRUPTIBLE);
	}
	__set_current_state(TASK_RUNNING);
	return 0;
}
当内核线程被唤醒时,就检查local_softirq_pending()中的软中断位掩码并在必要时调用do_softirq()。如果没有挂起的软中断,函数把当前进程状态置为TASK_INTERRUPTIBLE,随后,如果当前进程需要(当前thread_info的TIF_NEED_RESCHED标志被设置)就调用con_resched()函数来实现进程切换。

tasklet

tasklet是I/O驱动程序中实现可延迟函数的首选方法。tasklet建立在两个叫做HI_SOFTIRQ和TASKLET_SOFTIRQ的软中断之上。几个tasklet可以与同一个软中断相关联,每个tasklet执行自己的函数。

struct tasklet_struct
{
	struct tasklet_struct *next;
	unsigned long state;
	atomic_t count;
	void (*func)(unsigned long);
	unsigned long data;
};
struct tasklet_head
{
	struct tasklet_struct *head;
	struct tasklet_struct **tail;
};
static DEFINE_PER_CPU(struct tasklet_head, tasklet_vec);
static DEFINE_PER_CPU(struct tasklet_head, tasklet_hi_vec);
tasklet描述符的字段

next     指向链表中下一个描述符的指针

state    tasklet的状态

count    锁计数器

func     指向tasklet函数的指针

data     一个无符号长整数,可以由tasklet函数使用

tasklet描述的state字段含有两个标志:

TASKLET_STATE_SCHED

该标志被设置时,表示tasklet是挂起的;也意味着tasklet描述符被插入到tasklet_vec和tasklet_hi_vec数组的其中一个链表

TASKLET_STATE_RUN

该标志被设置时,表示tasklet正在被执行;在单处理器系统上不使用这个标志,因为没有必要检查特定的tasklet是否在运行

为了激活tasklet,根据tasklet的优先级,调用tasklet_schedule()或tasklet_hi_schedule()函数。

inline void raise_softirq_irqoff(unsigned int nr)
{
	__raise_softirq_irqoff(nr);

	/*
	 * If we're in an interrupt or softirq, we're done
	 * (this also catches softirq-disabled code). We will
	 * actually run the softirq once we return from
	 * the irq or softirq.
	 *
	 * Otherwise we wake up ksoftirqd to make sure we
	 * schedule the softirq soon.
	 */
	if (!in_interrupt())
		wakeup_softirqd();
}

void __tasklet_schedule(struct tasklet_struct *t)
{
	unsigned long flags;

	local_irq_save(flags);
	t->next = NULL;
	*__get_cpu_var(tasklet_vec).tail = t;
	__get_cpu_var(tasklet_vec).tail = &(t->next);
	raise_softirq_irqoff(TASKLET_SOFTIRQ);
	local_irq_restore(flags);
}
static inline void tasklet_schedule(struct tasklet_struct *t)
{
	if (!test_and_set_bit(TASKLET_STATE_SCHED, &t->state))
		__tasklet_schedule(t);
}
这两个函数非常类似,其中每个执行下列操作:

1、检查TASKLET_STATE_SCHED标志;如果设置则返回

2、调用local_irq_save保存IF标志的状态并禁用本地中断

3、在tasklet_vec或者tasklet_hi_vec指向的链表的起始处增加tasklet描述符

4、调用raise_softirq_irqoff()激活TASKLET_SOFTIRQ或HI_SOFTIRQ类型的软中断

5、调用local_irq_restore恢复IF标志的状态

工作队列

可延迟函数和工作队列非常相似,它们的区别在于:可延迟函数运行在中断上下文,而工作队列中的函数运行在进程上下文中。执行可阻塞函数(例如:需要访问磁盘数据块的函数)的唯一方式是在进程上下文中运行。因为,在中断上下文中不可能发生进程切换。可延迟函数和工作队列中的函数都不能访问进程的用户态地址空间。

struct cpu_workqueue_struct {

	spinlock_t lock;

	long remove_sequence;	/* Least-recently added (next to run) */
	long insert_sequence;	/* Next to add */

	struct list_head worklist;
	wait_queue_head_t more_work;
	wait_queue_head_t work_done;

	struct workqueue_struct *wq;
	task_t *thread;

	int run_depth;		/* Detect run_workqueue() recursion depth */
} ____cacheline_aligned;

/*
 * The externally visible workqueue abstraction is an array of
 * per-CPU workqueues:
 */
struct workqueue_struct {
	struct cpu_workqueue_struct cpu_wq[NR_CPUS];
	const char *name;
	struct list_head list; 	/* Empty if single thread */
};
cpu_workqueue_struct类型的描述符,字段描述如下:

lock             保护该数据结构的自旋锁

remove_sequence  flush_workqueue()使用的序列号

insert_sequence  flush_workqueue()使用的序列号

worklist         挂起链表的头节点

more_work        等待队列,其中的工作者线程因等待更多的工作而处于睡眠状态

work_done        等待队列,其中的进程由于等待工作队列被刷新而处于睡眠状态

wq               指向workqueue_struct结构的指针,其中包含该描述符

thread           指向结构中工作线程的进程描述符指针

run_depth        run_workqueue()当前的执行深度

struct work_struct {
	unsigned long pending;
	struct list_head entry;
	void (*func)(void *);
	void *data;
	void *wq_data;
	struct timer_list timer;
};
pending       如果函数已经在工作队列链表中,该字段值设为1,否则设为0

entry         指向挂起函数链表前一个或后一个元素的指针

func          挂起函数的地址

data          传递给挂起函数的参数,是一个指针

wq_data       通常是指向cpu_workqueue_struct描述符的父节点的指针

timer         用于延迟挂起函数执行的软定时器

工作队列函数

create_workqueue()  函数接收一个字符串作为参数,返回新创建工作队列的workqueue_struct描述符的地址。该函数还创建n个工作者线程,并根                     据传递给函数的字符串为工作者线程命名,如foo/0,foo/1等等

destory_workqueue() 函数撤销工作队列

queue_work()        把函数插入工作队列,该函数主要执行下面步骤:

1、检查要插入的函数是否已经在工作队列中,如果是就结束

2、把work_struct描述符加到工作队列链表中,然后把work->pending置为1

3、如果工作者线程在本地CPU的cpu_workqueue_struct描述符的more_work等待队列上睡眠,该函数唤醒这个线程

每个工作线程在worker_thread()函数内部不断地执行循环操作,因而,线程在绝大多数时间里处于睡眠状态并等待某些工作被插入队列。工作线程一旦被唤醒就调用run_workqueue()函数,该函数从工作者线程的工作队列链表中删除所有work_struct描述符并执行相应的挂起函数。

由于工作队列函数可以阻塞,因此,可以让工作者线程睡眠,甚至可以让它迁移到另一个CPU上恢复执行

flush_workqueue()函数接收workqueue_struct描述符的地址,并且在工作队列中的所有挂起函数结束之前使调用进程一直处于阻塞状态。