kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

内核抢占实现机制分析

1 内核抢占概述

2.6新的可抢占式内核是指内核抢占,即当进程位于内核空间时,有一个更高优先级的任务出现时,如果当前内核允许抢占,则可以将当前任务挂起,执行优先级更高的进程。

在2.5.4版本之前,Linux内核是不可抢占的,高优先级的进程不能中止正在内核中运行的低优先级的进程而抢占CPU运行。进程一旦处于核心态(例如 用户进程执行系统调用),则除非进程自愿放弃CPU,否则该进程将一直运行下去,直至完成或退出内核。与此相反,一个可抢占的Linux内核可以让 Linux内核如同用户空间一样允许被抢占。当一个高优先级的进程到达时,不管当前进程处于用户态还是核心态,如果当前允许抢占,可抢占内核的Linux 都会调度高优先级的进程运行。

2 用户抢占

内核即将返回用户空间的时候,如果need resched标志被设置,会导致schedule()被调用,此时就会发生用户抢占。在内核返回用户空间的时候,它知道自己是安全的。所以,内核无论是 在从中断处理程序还是在系统调用后返回,都会检查need resched标志。如果它被设置了,那么,内核会选择一个其他(更合适的)进程投入运行。

简而言之,用户抢占在以下情况时产生: 从系统调返回用户空间。
从中断处理程序返回用户空间。

3 不可抢占内核的特点

在不支持内核抢占的内核中,内核代码可以一直执行,到它完成为止。也就是说,调度程序没有办法在一个内核级的任务正在执行的时候重新调度—内核中的各任务是协作方式调度的,不具备抢占性。当然,运行于内核态 的进程可以主动放弃CPU,比如,在系统调用服务例程中,由于内核代码由于等待资源而放弃CPU,这种情况叫做计划性进程切换(planned process switch)。内核代码一直要执行到完成(返回用户空间)或明显的阻塞为止, 在单CPU情况下,这样的设定大大简化了内核的同步和保护机制。可以分两步对此加以分析:
首先,不考虑进程在内核中自愿放弃CPU的情况(也即在内核中不发生进程的切换)。一个进程一旦进入内核就将一直运行下去,直到完成或退出内核。在其没有 完成或退出内核之前,不会有另外一个进程进入内核,即进程在内核中的执行是串行的,不可能有多个进程同时在内核中运行,这样内核代码设计时就不用考虑多个 进程同时执行所带来的并发问题。Linux的内核开发人员就不用考虑复杂的进程并发执行互斥访问临界资源的问题。当进程在访问、修改内核的数据结构时就不 需要加锁来防止多个进程同时进入临界区。这时只需再考虑一下中断的情况,若有中断处理例程也有可能访问进程正在访问的数据结构,那么进程只要在进入临界区 前先进行关中断操作,退出临界区时进行开中断操作就可以了。
再考虑一下进程自愿放弃CPU的情况。因为对CPU的放弃是自愿的、主动的,也就意味着进程在内核中的切换是预先知道的,不会出现在不知道的情况下发生进 程的切换。这样就只需在发生进程切换的地方考虑一下多个进程同时执行所可能带来的并发问题,而不必在整个内核范围内都要考虑进程并发执行问题。

4 为什么需要内核抢占?

实现内核的可抢占对Linux具有重要意义。首先,这是将Linux应用于实时系统所必需的。实时系统对响应时间有严格的限定,当一个实时进程被实时设备 的硬件中断唤醒后,它应在限定的时间内被调度执行。而Linux不能满足这一要求,因为Linux的内核是不可抢占的,不能确定系统在内核中的停留时间。 事实上当内核执行长的系统调用时,实时进程要等到内核中运行的进程退出内核才能被调度,由此产生的响应延迟,在如今的硬件条件下,会长达100ms级。

这对于那些要求高实时响应的系统是不能接受的。而可抢占的内核不仅对Linux的实时应用至关重要,而且能解决Linux对多媒体(video, audio)等要求低延迟的应用支持不够好的缺陷。

由于可抢占内核的重要性,在Linux2.5.4版本发布时,可抢占被并入内核,同SMP一样作为内核的一项标准可选配置。

5 什么情况不允许内核抢占

有几种情况Linux内核不应该被抢占,除此之外Linux内核在任意一点都可被抢占。这几种情况是:
? 内核正进行中断处理。在Linux内核中进程不能抢占中断(中断只能被其他中断中止、抢占,进程不能中止、抢占中断),在中断例程中不允许进行进程调度。进程调度函数schedule()会对此作出判断,如果是在中断中调用,会打印出错信息。
? 内核正在进行中断上下文的Bottom Half(中断的底半部)处理。硬件中断返回前会执行软中断,此时仍然处于中断上下文中。
? 内核的代码段正持有spinlock自旋锁、writelock/readlock读写锁等锁,处干这些锁的保护状态中。内核中的这些锁是为了在SMP系 统中短时间内保证不同CPU上运行的进程并发执行的正确性。当持有这些锁时,内核不应该被抢占,否则由于抢占将导致其他CPU长期不能获得锁而死等。
? 内核正在执行调度程序Scheduler。抢占的原因就是为了进行新的调度,没有理由将调度程序抢占掉再运行调度程序。
? 内核正在对每个CPU“私有”的数据结构操作(Per-CPU date structures)。在SMP中,对于per-CPU数据结构未用spinlocks保护,因为这些数据结构隐含地被保护了(不同的CPU有不一样的 per-CPU数据,其他CPU上运行的进程不会用到另一个CPU的per-CPU数据)。但是如果允许抢占,但一个进程被抢占后重新调度,有可能调度到 其他的CPU上去,这时定义的Per-CPU变量就会有问题,这时应禁抢占。

为保证Linux内核在以上情况下不会被抢占,抢占式内核使用了一个变量preempt count,称为内核抢占锁。这一变量被设置在进程的PCB结构task_struct中。每当内核要进入以上几种状态时,变量preempt count就加1,指示内核不允许抢占。每当内核从以上几种状态退出时,变量preempt_ count就减1,同时进行可抢占的判断与调度。

从中断返回内核空间的时候,内核会检查need_resched和preempt_count的值。如果need resched被设置,并且preempt count为0的话,这说明可能有一个更为重要的任务需要执行并且可以安全地抢占,此时,调度程序就会被调用。如果preempt-count不为0,则 说明内核现在处干不可抢占状态,不能进行重新调度。这时,就会像通常那样直接从中断返回当前执行进程。如果当前进程持有的所有的锁都被释放了,那么 preempt count就会重新为0。此时,释放锁的代码会检查need_ resched是否被设置。如果是的话,就会调用调度程序。

6 内核抢占时机

在2.6版的内核中,内核引入了抢占能力;现在,只要重新调度是安全的,那么内核就可以在任何时间抢占正在执行的任务。
那么,什么时候重新调度才是安全的呢?只要premptcount为0,内核就可以进行抢占。通常锁和中断是非抢占区域的标志。由于内核是支持SMP的,所以,如果没有持有锁,那么正在执行的代码就是可重新导人的,也就是可以抢占的。
如果内核中的进程被阻塞了,或它显式地调用了schedule(),内核抢占也会显式地发生。这种形式的内核抢占从来都是受支持的(实际上是主动让出 CPU),因为根本无需额外的逻辑来保证内核可以安全地被抢占。如果代码显式的调用了schedule(),那么它应该清楚自己是可以安全地被抢占的。

内核抢占可能发生在:
当从中断处理程序正在执行,且返回内核空间之前。
当内核代码再一次具有可抢占性的时候,如解锁及使能软中断(local_bh_enable)等。
如果内核中的任务显式的调用schedule()
如果内核中的任务阻塞(这同样也会导致调用schedule())

7 如何支持抢占内核

抢占式Linux内核的修改主要有两点:一是对中断的入口代码和返回代码进行修改。在中断的入口内核抢占锁preempt_count加1,以禁止内核抢占;在中断的返回处,内核抢占锁preempt_count减1,使内核有可能被抢占。

我们说可抢占Linux内核在内核的任一点可被抢占,主要就是因为在任意一点中断都有可能发生,每当中断发生,Linux可抢占内核在处理完中断返回时都 会进行内核的可抢占判断。若内核当前所处状态允许被抢占,内核都会重新进行调度选取高优先级的进程运行。这一点是与非可抢占的内核不一样的。在非可抢占的 Linux内核中,从硬件中断返回时,只有当前被中断进程是用户态进程时才会重新调度,若当前被中断进程是核心态进程,则不进行调度,而是恢复被中断的进 程继续运行。

另一基本修改是重新定义了自旋锁、读、写锁,在锁操作时增加了对preempt count变量的操作。在对这些锁进行加锁操作时preemptcount变量加1,以禁止内核抢占;在释放锁时preemptcount变量减1,并在 内核的抢占条件满足且需要重新调度时进行抢占调度。下面以spin_lock(), spin_unlock()操作为例说明:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/////////////////////////////////////////////////////////////////////////
/linux+v2.6.19/kernel/spinlock.c
 320void __lockfunc _spin_unlock(spinlock_t *lock)
 321{
 322        spin_release(&lock->dep_map, 1, _RET_IP_);
 323        _raw_spin_unlock(lock);
 324        preempt_enable();
 325}
 326EXPORT_SYMBOL(_spin_unlock);
 178void __lockfunc _spin_lock(spinlock_t *lock)
 179{
 180        preempt_disable();
 181        spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
 182        _raw_spin_lock(lock);
 183}
 184
 185EXPORT_SYMBOL(_spin_lock);
/////////////////////////////////////////////////////////////////////////
  29#define preempt_disable() /
  30do { /
  31        inc_preempt_count(); /
  32        barrier(); /
  33} while (0)
  34
  35#define preempt_enable_no_resched() /
  36do { /
  37        barrier(); /
  38        dec_preempt_count(); /
  39} while (0)
  40
  41#define preempt_check_resched() /
  42do { /
  43        if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) /
  44                preempt_schedule(); /
  45} while (0)
  46
  47#define preempt_enable() /
  48do { /
  49        preempt_enable_no_resched(); /
  50        barrier(); /
  51        preempt_check_resched(); /
  52} while (0)
  53

另外一种可抢占内核实现方案是在内核代码段中插入抢占点(preemption point)的方案。在这一方案中,首先要找出内核中产生长延迟的代码段,然后在这一内核代码段的适当位置插入抢占点,使得系统不必等到这段代码执行完就 可重新调度。这样对于需要快速响应的事件,系统就可以尽快地将服务进程调度到CPU运行。抢占点实际上是对进程调度函数的调用,代码如下:
if (current->need_ resched) schedule();
通常这样的代码段是一个循环体,插入抢占点的方案就是在这一循环体中不断检测need_ resched的值,在必要的时候调用schedule()令当前进程强行放弃CPU

8 何时需要重新调度

内核必须知道在什么时候调用schedule()。如果仅靠用户程序代码显式地调用schedule(),它们可能就会永远地执行下去。相反,内核提供了 一个need_resched标志来表明是否需要重新执行一次调度。当某个进程耗尽它的时间片时,scheduler tick()就会设置这个标志;当一个优先级高的进程进入可执行状态的时候,try_to_wake_up也会设置这个标志。
set tsk_need_resched:设置指定进程中的need resched标志
clear tsk need_resched:清除指定进程中的need resched标志
need_resched():检查need
resched标志的值;如果被设置就返回真,否则返回假信号量、等到队列、completion等机制唤醒时都是基于waitqueue的,而waitqueue的唤醒函数为default_wake_function,其调用try_to_wake_up将进程更改为可运行状态并置待调度标志。

在返回用户空间以及从中断返回的时候,内核也会检查need_resched标志。如果已被设置,内核会在继续执行之前调用调度程序。
每个进程都包含一个need_resched标志,这是因为访问进程描述符内的数值要比访问一个全局变量快(因为current宏速度很快并且描述符通常 都在高速缓存中)。在2.2以前的内核版本中,该标志曾经是一个全局变量。2.2到2.4版内核中它在task_struct中。而在2.6版中,它被移 到thread_info结构体里,用一个特别的标志变量中的一位来表示。可见,内核开发者总是在不断改进。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/linux+v2.6.19/include/linux/sched.h
1503static inline void set_tsk_need_resched(struct task_struct *tsk)
1504{
1505        set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
1506}
1507
1508static inline void clear_tsk_need_resched(struct task_struct *tsk)
1509{
1510        clear_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
1511}
1512
1513static inline int signal_pending(struct task_struct *p)
1514{
1515        return unlikely(test_tsk_thread_flag(p,TIF_SIGPENDING));
1516}
1517 
1518static inline int need_resched(void)
1519{
1520        return unlikely(test_thread_flag(TIF_NEED_RESCHED));
1521}
///////////////////////////////////////////////////////////////////////////////
/linux+v2.6.19/kernel/sched.c
 991/*
 992 * resched_task - mark a task 'to be rescheduled now'.
 993 *
 994 * On UP this means the setting of the need_resched flag, on SMP it
 995 * might also involve a cross-CPU call to trigger the scheduler on
 996 * the target CPU.
 997 */
 998#ifdef CONFIG_SMP
 999
1000#ifndef tsk_is_polling
1001#define tsk_is_polling(t) test_tsk_thread_flag(t, TIF_POLLING_NRFLAG)
1002#endif
1003
1004static void resched_task(struct task_struct *p)
1005{
1006        int cpu;
1007
1008        assert_spin_locked(&task_rq(p)->lock);
1009
1010        if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
1011                return;
1012
1013        set_tsk_thread_flag(p, TIF_NEED_RESCHED);
1014
1015        cpu = task_cpu(p);
1016        if (cpu == smp_processor_id())
1017                return;
1018
1019        /* NEED_RESCHED must be visible before we test polling */
1020        smp_mb();
1021        if (!tsk_is_polling(p))
1022                smp_send_reschedule(cpu);
1023}
1024#else
1025static inline void resched_task(struct task_struct *p)
1026{
1027        assert_spin_locked(&task_rq(p)->lock);
1028        set_tsk_need_resched(p);
1029}
1030#endif
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
1366/***
1367 * try_to_wake_up - wake up a thread
1368 * @p: the to-be-woken-up thread
1369 * @state: the mask of task states that can be woken
1370 * @sync: do a synchronous wakeup?
1371 *
1372 * Put it on the run-queue if it's not already there. The "current"
1373 * thread is always on the run-queue (except when the actual
1374 * re-schedule is in progress), and as such you're allowed to do
1375 * the simpler "current->state = TASK_RUNNING" to mark yourself
1376 * runnable without the overhead of this.
1377 *
1378 * returns failure only if the task is already active.
1379 */
1380static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
1538int fastcall wake_up_process(struct task_struct *p)
1539{
1540        return try_to_wake_up(p, TASK_STOPPED | TASK_TRACED |
1541                                 TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE, 0);
1542}
1543EXPORT_SYMBOL(wake_up_process);
1545int fastcall wake_up_state(struct task_struct *p, unsigned int state)
1546{
1547        return try_to_wake_up(p, state, 0);
1548}
1616/*
1617 * wake_up_new_task - wake up a newly created task for the first time.
1618 *
1619 * This function will do some initial scheduler statistics housekeeping
1620 * that must be done for every newly created context, then puts the task
1621 * on the runqueue and wakes it.
1622 */
1623void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
3571/*
3572 * The core wakeup function.  Non-exclusive wakeups (nr_exclusive == 0) just
3573 * wake everything up.  If it's an exclusive wakeup (nr_exclusive == small +ve
3574 * number) then we wake all the non-exclusive tasks and one exclusive task.
3575 *
3576 * There are circumstances in which we can try to wake a task which has already
3577 * started to run but is not in state TASK_RUNNING.  try_to_wake_up() returns
3578 * zero in this (rare) case, and we handle it by continuing to scan the queue.
3579 */
3580static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
3581                             int nr_exclusive, int sync, void *key)
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
3595/**
3596 * __wake_up - wake up threads blocked on a waitqueue.
3597 * @q: the waitqueue
3598 * @mode: which threads
3599 * @nr_exclusive: how many wake-one or wake-many threads to wake up
3600 * @key: is directly passed to the wakeup function
3601 */
3602void fastcall __wake_up(wait_queue_head_t *q, unsigned int mode,
3603                        int nr_exclusive, void *key)
3604{
3605        unsigned long flags;
3606
3607        spin_lock_irqsave(&q->lock, flags);
3608        __wake_up_common(q, mode, nr_exclusive, 0, key);
3609        spin_unlock_irqrestore(&q->lock, flags);
3610}
3611EXPORT_SYMBOL(__wake_up);
3564int default_wake_function(wait_queue_t *curr, unsigned mode, int sync,
3565                          void *key)
3566{
3567        return try_to_wake_up(curr->private, mode, sync);
3568}
3569EXPORT_SYMBOL(default_wake_function);
3652void fastcall complete(struct completion *x)
3653{
3654        unsigned long flags;
3655
3656        spin_lock_irqsave(&x->wait.lock, flags);
3657        x->done++;
3658        __wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE,
3659                         1, 0, NULL);
3660        spin_unlock_irqrestore(&x->wait.lock, flags);
3661}
3662EXPORT_SYMBOL(complete);

9 参考资料

请解释抢占式内核与非抢占式内核的区别联系,http://oldlinux.org/oldlinux/viewthread.php?tid=3024

抢占式内核中的锁问题,http://hi.baidu.com/juventus/blog/item/a71c8701960454d2277fb5f0.html

http://www.linuxforum.net/forum/showflat.php?Cat=&Board=linuxK&Number=610932&page=

http://linux.chinaunix.net/bbs/viewthread.php?tid=912039

Linux kernel design and development

Linux抢占式内核就是由Robert Love修改实现的。在他的书中有如下描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
User Preemption
User preemption occurs when the kernel is about to return to user-space, 
need_resched is set, and therefore, the scheduler is invoked. 
If the kernel is returning to user-space, it knows it is in a safe quiescent state. 
In other words, if it is safe to continue executing the current task, 
it is also safe to pick a new task to execute. Consequently, 
whenever the kernel is preparing to return to user-space either on return from 
an interrupt or after a system call, the value of need_resched is checked. 
If it is set, the scheduler is invoked to select a new (more fit) process to execute. 
Both the return paths for return from interrupt and return from system call 
are architecture dependent and typically implemented in assembly in entry.S 
(which, aside from kernel entry code, also contains kernel exit code).
In short, user preemption can occur
When returning to user-space from a system call
When returning to user-space from an interrupt handler
Kernel Preemption

The Linux kernel, unlike most other Unix variants and many other operating systems, 
is a fully preemptive kernel. In non-preemptive kernels, kernel code runs until completion. 
That is, the scheduler is not capable of rescheduling a task while it is in the kernel. 
kernel code is scheduled cooperatively, not preemptively. 

Kernel code runs until it finishes (returns to user-space) or explicitly blocks. 
In the 2.6 kernel, however, the Linux kernel became preemptive: 
It is now possible to preempt a task at any point, so long as the kernel is in a state in which it is safe to reschedule.

So when is it safe to reschedule? The kernel is capable of preempting a task 
running in the kernel so long as it does not hold a lock. That is, locks are used as 
markers of regions of non-preemptibility. Because the kernel is SMP-safe, 
if a lock is not held, the current code is reentrant and capable of being preempted.

The first change in supporting kernel preemption was the addition of a preemption counter, 
preempt_count, to each process's thread_info. This counter begins at zero and increments 
once for each lock that is acquired and decrements once for each lock that is released. 
When the counter is zero, the kernel is preemptible. Upon return from interrupt, 
if returning to kernel-space, the kernel checks the values of need_resched and preempt_count. 

If need_resched is set and preempt_count is zero, then a more important task is runnable and 
it is safe to preempt. Thus, the scheduler is invoked. If preempt_count is nonzero, 
a lock is held and it is unsafe to reschedule. In that case, the interrupt returns 
as usual to the currently executing task. When all the locks that the current task is holding are released, 
preempt_count returns to zero. At that time, the unlock code checks whether need_resched is set. 
If so, the scheduler is invoked. Enabling and disabling kernel preemption is sometimes 
required in kernel code and is discussed in Chapter 9
.
Kernel preemption can also occur explicitly, when a task in the kernel blocks or explicitly calls schedule(). 
This form of kernel preemption has always been supported because no additional logic is 
required to ensure that the kernel is in a state that is safe to preempt. 
It is assumed that the code that explicitly calls schedule() knows it is safe to reschedule.

Kernel preemption can occur
When an interrupt handler exits, before returning to kernel-space
When kernel code becomes preemptible again
If a task in the kernel explicitly calls schedule()
If a task in the kernel blocks (which results in a call to schedule())

利用kexec快速切换内核

kexec是一个用于在当前系统下快速切换到另一个内核的一种办法,它采用了一定的机制略过了硬件的初始化,所以切换速度会很快。

自2.6.13以后,Linux内核就已经自置了kexec,而Debian采用的内核已经是2.6.26,而且默认就支持kexec,所以在Debian下我们只要安装kexec-tools就行了。

1
2
$ yum install kexec-tools
$ sudo apt-get install kexec-tools

安装好以后,就可以开始加载其他的内核了。
先看看我有哪些内核可以用:

1
2
3
$ ls /boot/vmlinuz-2.6.26-1-*
/boot/vmlinuz-2.6.26-1-amd64         
/boot/vmlinuz-2.6.26-1-vserver-amd64

好多好多,再看看当前的内核

1
2
$ uname -r
2.6.26-1-vserver-amd64

好了,现在我打算切换到2.6.26-1-amd64去:
记得,需要root权限的

1
$ sudo -s

先要用kexec加载它,先看看该追加哪些参数

1
2
3
4
$ cat /boot/grub/menu.lst | grep 2.6.26-1-amd64
title Debian GNU/Linux, kernel 2.6.26-1-amd64
kernel /vmlinuz-2.6.26-1-amd64 root=/dev/sda1 ro
initrd /initrd.img-2.6.26-1-amd64

找到了,对照上面开始用kexec加载了

1
$ kexec -l /boot/vmlinuz-2.6.26-1-amd64 --initrd=/boot/initrd.img-2.6.26-1-amd64 --append="root=/dev/sda1 ro"

加载以后并不直接执行哦,所以我们要执行一下才会切换

1
$ kexec -e

不要紧张,等一下下就好了,起来以后还会提示登录的
看看我的效果:

1
2
$ uname -r
2.6.26-1-amd64

切换到我想要的内核了

内核抢占与中断返回

1、上下文

一般来说,CPU在任何时刻都处于以下三种情况之一:
(1)运行于用户空间,执行用户进程;
(2)运行于内核空间,处于进程上下文;
(3)运行于内核空间,处于中断上下文。
应用程序通过系统调用陷入内核,此时处于进程上下文。现代几乎所有的CPU体系结构都支持中断。当外部设备产生中断,向CPU发送一个异步信号,CPU调用相应的中断处理程序来处理该中断,此时CPU处于中断上下文。

在进程上下文中,可以通过current关联相应的任务。进程以进程上下文的形式运行在内核空间,可以发生睡眠,所以在进程上下文中,可以使作信号量(semaphore)。实际上,内核经常在进程上下文中使用信号量来完成任务之间的同步,当然也可以使用锁。

中断上下文不属于任何进程,它与current没有任何关系(尽管此时current指向被中断的进程)。由于没有进程背景,在中断上下文中不能发生睡眠,否则又如何对它进行调度。所以在中断上下文中只能使用锁进行同步,正是因为这个原因,中断上下文也叫做原子上下文(atomic context)(关于同步以后再详细讨论)。在中断处理程序中,通常会禁止同一中断,甚至会禁止整个本地中断,所以中断处理程序应该尽可能迅速,所以又把中断处理分成上部和下部(关于中断以后再详细讨论)。

2、上下文切换

上下文切换,也就是从一个可执行进程切换到另一个可执行进程。上下文切换由函数context_switch()函数完成,该函数位于kernel/sched.c中,它由进程调度函数schedule()调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static inline
task_t * context_switch(runqueue_t *rq, task_t *prev, task_t *next)
{
	struct mm_struct *mm = next->mm;
	struct mm_struct *oldmm = prev->active_mm;

	if (unlikely(!mm)) {
		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm(oldmm, mm, next);

	if (unlikely(!prev->mm)) {
		prev->active_mm = NULL;
		WARN_ON(rq->prev_mm);
		rq->prev_mm = oldmm;
	}

	/* Here we just switch the register state and the stack. */
	switch_to(prev, next, prev);

	return prev;
}

其中,switch_mm()将虚拟内存映射到新的进程;switch_to完成最终的进程切换,它保存原进程的所有寄存器信息,恢复新进程的所有寄存器信息,并执行新的进程。无论何时,内核想要进行任务切换,都通过调用schedule()完成任务切换。

2.2、用户抢占

当内核即将返回用户空间时,内核会检查need_resched是否设置,如果设置,则调用schedule(),此时,发生用户抢占。一般来说,用户抢占发生几下情况:
(1)从系统调用返回用户空间;
(2)从中断(异常)处理程序返回用户空间。

2.3、内核抢占

内核从2.6开始就支持内核抢占,对于非内核抢占系统,内核代码可以一直执行,直到完成,也就是说当进程处于内核态时,是不能被抢占的(当然,运行于内核态的进程可以主动放弃CPU,比如,在系统调用服务例程中,由于内核代码由于等待资源而放弃CPU,这种情况叫做计划性进程切换(planned process switch))。但是,对于由异步事件(比如中断)引起的进程切换,抢占式内核与非抢占式是有区别的,对于前者叫做强制性进程切换(forced process switch)。

为了支持内核抢占,内核引入了preempt_count字段,该计数初始值为0,每当使用锁时加1,释放锁时减1。当preempt_count为0时,表示内核可以被安全的抢占,大于0时,则禁止内核抢占。该字段对应三个不同的计数器(见软中断一节),也就是说在以下三种任何一种情况,该字段的值都会大于0。

(1) 内核执行中断处理程序时,通过irq_enter增加中断计数器的值;
#define irq_enter() (preempt_count() += HARDIRQ_OFFSET)
(2) 可延迟函数被禁止(执行软中断和tasklet时经常如此,由local_bh_disable完成;
(3) 通过把抢占计数器设置为正而显式禁止内核抢占,由preempt_disable完成。

当从中断返回内核空间时,内核会检preempt_count和need_resched的值(返回用户空间时只需要检查need_resched),如查preempt_count为0且need_resched设置,则调用schedule(),完成任务抢占。一般来说,内核抢占发生以下情况:
(1) 从中断(异常)返回时,preempt_count为0且need_resched置位(见从中断返回);
(2) 在异常处理程序中(特别是系统调用)调用preempt_enable()来允许内核抢占发生;

1
2
3
4
5
6
7
8
//incude/linux/preempt.h
#define preempt_enable() \
do { \
	//抢占计数器值减1
	preempt_enable_no_resched(); \
	//检查是否需要进行内核抢占调度,见(3)
	preempt_check_resched(); \
} while (0)

(3) 启用可延迟函数时,即调用local_bh_enable()时发生;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//kernel/softirq.c
void local_bh_enable(void)
{
	WARN_ON(irqs_disabled());
	/*
	 * Keep preemption disabled until we are done with
	 * softirq processing:
	 */
	//软中断计数器值减1
	preempt_count() -= SOFTIRQ_OFFSET - 1;

	if (unlikely(!in_interrupt() && local_softirq_pending()))
		do_softirq(); //软中断处理
	//抢占计数据器值减1
	dec_preempt_count();
	
	//检查是否需要进行内核抢占调度
	preempt_check_resched();
}

//include/linux/preempt.h
#define preempt_check_resched() \
do { \
	//检查need_resched
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) \
		//抢占调度
		preempt_schedule(); \
} while (0)

//kernel/sched.c
asmlinkage void __sched preempt_schedule(void)
{
	struct thread_info *ti = current_thread_info();

	/*
	 * If there is a non-zero preempt_count or interrupts are disabled,
	 * we do not want to preempt the current task.  Just return..
	 */
	 //检查是否允许抢占,本地中断关闭,或者抢占计数器值不为0时不允许抢占
	if (unlikely(ti->preempt_count || irqs_disabled()))
		return;

need_resched:
	ti->preempt_count = PREEMPT_ACTIVE;
	//发生调度
	schedule();
	ti->preempt_count = 0;

	/* we could miss a preemption opportunity between schedule and now */
	barrier();
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
		goto need_resched;
}

(4) 内核任务显示调用schedule(),例如内核任务阻塞时,就会显示调用schedule(),该情况属于内核自动放弃CPU。

5、从中断返回

当内核从中断返回时,应当考虑以下几种情况:
(1) 内核控制路径并发执行的数量:如果为1,则CPU返回用户态。
(2) 挂起进程的切换请求:如果有挂起请求,则进行进程调度;否则,返回被中断的进程。
(3) 待处理信号:如果有信号发送给当前进程,则必须进行信号处理。
(4) 单步调试模式:如果调试器正在跟踪当前进程,在返回用户态时必须恢复单步模式。
(5) Virtual-8086模式:如果中断时CPU处于虚拟8086模式,则进行特殊的处理。

4.1从中断返回

中断返回点为ret_from-intr: // 从中断返回

1
2
3
4
5
6
7
ret_from_intr:
	GET_THREAD_INFO(%ebp)
	movl EFLAGS(%esp), %eax        # mix EFLAGS and CS
	movb CS(%esp), %al
	testl $(VM_MASK | 3), %eax #是否运行在VM86模式或者用户态
	/*中断或异常发生时,处于内核空间,则返回内核空间;否则返回用户空间*/
	jz resume_kernel        # returning to kernel or vm86-space

从中断返回时,有两种情况,一是返回内核态,二是返回用户态。

5.1.1、返回内核态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifdef CONFIG_PREEMPT 
/*返回内核空间,先检查preempt_count,再检查need_resched*/
ENTRY(resume_kernel)
	/*是否可以抢占,即preempt_count是否为0*/
	cmpl $0,TI_preempt_count(%ebp)    # non-zero preempt_count ?
	jnz restore_all #不能抢占,则恢复被中断时处理器状态
	
need_resched:
	movl TI_flags(%ebp), %ecx    # need_resched set ?
	testb $_TIF_NEED_RESCHED, %cl #是否需要重新调度
	jz restore_all #不需要重新调度
	testl $IF_MASK,EFLAGS(%esp)     # 发生异常则不调度
	jz restore_all
	#将最大值赋值给preempt_count,表示不允许再次被抢占
	movl $PREEMPT_ACTIVE,TI_preempt_count(%ebp)
	sti
	call schedule #调度函数
	cli
	movl $0,TI_preempt_count(%ebp) #preempt_count还原为0
	#跳转到need_resched,判断是否又需要发生被调度
	jmp need_resched
#endif
5.1.2、返回用户态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*返回用户空间,只需要检查need_resched*/
ENTRY(resume_userspace)  #返回用户空间,中断或异常发生时,任务处于用户空间
	 cli                # make sure we don't miss an interrupt
		            # setting need_resched or sigpending
		            # between sampling and the iret
	movl TI_flags(%ebp), %ecx
	andl $_TIF_WORK_MASK, %ecx    # is there any work to be done on
		            # int/exception return?
	jne work_pending #还有其它工作要做
	jmp restore_all #所有工作都做完,则恢复处理器状态

#恢复处理器状态
restore_all:
	RESTORE_ALL

	# perform work that needs to be done immediately before resumption
	ALIGN
	
	#完成其它工作
work_pending:
	testb $_TIF_NEED_RESCHED, %cl #检查是否需要重新调度
	jz work_notifysig #不需要重新调度
 #需要重新调度
work_resched:
	call schedule #调度进程
	cli                # make sure we don't miss an interrupt
		            # setting need_resched or sigpending
		            # between sampling and the iret
	movl TI_flags(%ebp), %ecx
	/*检查是否还有其它的事要做*/
	andl $_TIF_WORK_MASK, %ecx    # is there any work to be done other
		            # than syscall tracing?
	jz restore_all #没有其它的事,则恢复处理器状态
	testb $_TIF_NEED_RESCHED, %cl
	jnz work_resched #如果need_resched再次置位,则继续调度
#VM和信号检测
work_notifysig:                # deal with pending signals and
		            # notify-resume requests
	testl $VM_MASK, EFLAGS(%esp) #检查是否是VM模式
	movl %esp, %eax
	jne work_notifysig_v86        # returning to kernel-space or
		            # vm86-space
	xorl %edx, %edx
	#进行信号处理
	call do_notify_resume
	jmp restore_all

	ALIGN
work_notifysig_v86:
	pushl %ecx            # save ti_flags for do_notify_resume
	call save_v86_state        # %eax contains pt_regs pointer
	popl %ecx
	movl %eax, %esp
	xorl %edx, %edx
	call do_notify_resume #信号处理
	jmp restore_all
5.2、从异常返回

异常返回点为ret_from_exception: #从异常返回
ALIGN
ret_from_exception:
preempt_stop /相当于cli,从中断返回时,在handle_IRQ_event已经关中断,不需要这步/

6、从系统调用返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
	#系统调用入口
ENTRY(system_call)
	pushl %eax            # save orig_eax
	SAVE_ALL
	GET_THREAD_INFO(%ebp)
		            # system call tracing in operation
	testb $(_TIF_SYSCALL_TRACE|_TIF_SYSCALL_AUDIT),TI_flags(%ebp)
	jnz syscall_trace_entry
	cmpl $(nr_syscalls), %eax
	jae syscall_badsys
syscall_call:
	#调用相应的函数
	call *sys_call_table(,%eax,4)
	movl %eax,EAX(%esp)        # store the return value,返回值保存到eax
#系统调用返回
syscall_exit:
	cli                # make sure we don't miss an interrupt
		            # setting need_resched or sigpending
		            # between sampling and the iret
	movl TI_flags(%ebp), %ecx
	testw $_TIF_ALLWORK_MASK, %cx    # current->work,检查是否还有其它工作要完成
	jne syscall_exit_work
#恢复处理器状态
restore_all:
	RESTORE_ALL

#做其它工作
syscall_exit_work:
	 #检查是否系统调用跟踪,审计,单步执行,不需要则跳到work_pending(进行调度,信号处理)
	testb $(_TIF_SYSCALL_TRACE|_TIF_SYSCALL_AUDIT|_TIF_SINGLESTEP), %cl
	jz work_pending
	sti                # could let do_syscall_trace() call
		            # schedule() instead
	movl %esp, %eax
	movl $1, %edx
	#系统调用跟踪
	call do_syscall_trace
	#返回用户空间
	jmp resume_userspace

整个中断、异常和系统调用返回流程如下:

kmalloc 函数详解

1
2
#include <linux/slab.h>
void *kmalloc(size_t size, int flags);

给 kmalloc 的第一个参数是要分配的块的大小. 第 2 个参数, 分配标志, 非常有趣, 因为它以几个方式控制 kmalloc 的行为.

最一般使用的标志, GFP_KERNEL, 意思是这个分配((内部最终通过调用 _get_free_pages 来进行, 它是 GFP 前缀的来源) 代表运行在内核空间的进程而进行的. 换句话说, 这意味着调用函数是代表一个进程在执行一个系统调用. 使用 GFP_KENRL 意味着 kmalloc 能够使当前进程在少内存的情况下睡眠来等待一页.

一个使用 GFP_KERNEL 来分配内存的函数必须, 因此, 是可重入的并且不能在原子上下文中运行. 当当前进程睡眠, 内核采取正确的动作来定位一些空闲内存, 或者通过刷新缓存到磁盘或者交换出去一个用户进程的内存.

GFP_KERNEL 不一直是使用的正确分配标志; 有时 kmalloc 从一个进程的上下文的外部调用. 例如, 这类的调用可能发生在中断处理, tasklet, 和内核定时器中. 在这个情况下, 当前进程不应当被置为睡眠, 并且驱动应当使用一个 GFP_ATOMIC 标志来代替. 内核正常地试图保持一些空闲页以便来满足原子的分配. 当使用 GFP_ATOMIC 时, kmalloc 能够使用甚至最后一个空闲页. 如果这最后一个空闲页不存在, 但是, 分配失败.

其他用来代替或者增添 GFP_KERNEL 和 GFP_ATOMIC 的标志, 尽管它们 2 个涵盖大部分设备驱动的需要. 所有的标志定义在 <linux/gfp.h>, 并且每个标志用一个双下划线做前缀, 例如 __GFP_DMA. 另外, 有符号代表常常使用的标志组合; 这些缺乏前缀并且有时被称为分配优先级. 后者包括:

1
2
3
4
5
6
7
GFP_ATOMIC   用来从中断处理和进程上下文之外的其他代码中分配内存. 从不睡眠.  
GFP_KERNEL    内核内存的正常分配. 可能睡眠.  
GFP_USER  用来为用户空间页来分配内存; 它可能睡眠.  
GFP_HIGHUSER  如同 GFP_USER, 但是从高端内存分配, 如果有. 高端内存在下一个子节描述.  
GFP_NOIO  
GFP_NOFS  
这个标志功能如同 GFP_KERNEL, 但是它们增加限制到内核能做的来满足请求. 一个 GFP_NOFS 分配不允许进行任何文件系统调用, 而 GFP_NOIO 根本不允许任何 I/O 初始化. 它们主要地用在文件系统和虚拟内存代码, 那里允许一个分配睡眠, 但是递归的文件系统调用会是一个坏注意.
上面列出的这些分配标志可以是下列标志的相或来作为参数, 这些标志改变这些分配如何进行:
1
2
3
4
5
6
7
8
9
__GFP_DMA    这个标志要求分配在能够 DMA 的内存区. 确切的含义是平台依赖的并且在下面章节来解释.  
__GFP_HIGHMEM 这个标志指示分配的内存可以位于高端内存.  
__GFP_COLD    正常地, 内存分配器尽力返回"缓冲热"的页 -- 可能在处理器缓冲中找到的页. 相反, 这个标志请求一个"冷"页, 它在一段时间没被使用. 它对分配页作 DMA 读是有用的, 此时在处理器缓冲中出现是无用的.  
__GFP_NOWARN  这个很少用到的标志阻止内核来发出警告(使用 printk ), 当一个分配无法满足.  
__GFP_HIGH    这个标志标识了一个高优先级请求, 它被允许来消耗甚至被内核保留给紧急状况的最后的内存页.  
__GFP_REPEAT  
__GFP_NOFAIL  
__GFP_NORETRY  
这些标志修改分配器如何动作, 当它有困难满足一个分配. __GFP_REPEAT 意思是" 更尽力些尝试" 通过重复尝试 -- 但是分配可能仍然失败. __GFP_NOFAIL 标志告诉分配器不要失败; 它尽最大努力来满足要求. 使用 __GFP_NOFAIL 是强烈不推荐的; 可能从不会有有效的理由在一个设备驱动中使用它. 最后, __GFP_NORETRY 告知分配器立即放弃如果得不到请求的内存.

kmalloc 能够分配的内存块的大小有一个上限. 这个限制随着体系和内核配置选项而变化. 如果你的代码是要完全可移植, 它不能指望可以分配任何大于 128 KB. 如果你需要多于几个 KB

这方面的原因:
kmalloc并不直接从分页机制中获得空闲页面而是从slab页面分配器那儿获得需要的页面,slab的实现代码限制了最大分配的大小为128k,即 131072bytes,理论上你可以通过更改slab.c中的 cache_sizes数组中的最大值使得kmalloc可以获得更大的页面数,不知道有没有甚么副效应或者没有必要这样做,因为获取较大内存的方法有很 多,想必128k是经验总结后的合适值。

alloc_page( )可以分配的最大连续页面是4K

1
2
3
4
5
6
7
8
9
static inline struct page * alloc_pages(unsigned int gfp_mask, unsigned int order) 
{ 
	/*
	 * Gets optimized away by the compiler. 
	 */ 
	if (order >= MAX_ORDER) 
	return NULL; 
	return _alloc_pages(gfp_mask, order); 
} 

alloc_pages最大分配页面数为512个,则可用内存数最大为29*4K=2M

[大牛的]后缀数组总结

双关键字的基数排序

先对关键字2进行排序,然后再对关键字1进行稳定排序。 后缀数组中用到了这点。


大牛在这里

后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也并不逊色,而且它比后缀树所占用的内存空间小很多。可以说,后缀数组比后缀树要更为实用。自从拜读了罗穗骞大牛的WC2009论文《后缀数组——处理字符串的有力工具》后,经过若干星期的努力(中间有因某些原因而缓下来),终于把论文上面的练习题全部完成了,现在写写自己对后缀数组的理解和感悟。在看本笔记时,请不要忘记了,这是笔记,而教材是《后缀数组——处理字符串的有力工具》。

一:后缀数组的实现

  1. 定义:Suffix Array数组(SA数组)用于保存从小到大排好序之后的后缀。RANK名次数组用来保存后缀S[i..n]在所有后缀中是第几小的后缀。简单来说,SA数组表示的是“排第几的是谁”,RANK数组表示的是“你的排名是多少”。
  2. 求SA数组以及RANK数组的方法:详细的请转到罗穗骞大牛的论文,我的学习笔记重点不是要介绍这个。
  3. 对DA(倍增算法)的一些个人理解:由于我只学习了倍增算法,所以我只能谈谈我对它的理解。DC3算法我没有去研究….

DA算法我是根据罗穗骞的模板写的,根据自己的理解做了些许的小优化。我们现在来看看罗穗骞大牛的模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<m;i++) ws[i]=0;
	for(i=0;i<n;i++) ws[x[i]=r[i]]++;
	for(i=1;i<m;i++) ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
	for(j=1,p=1;p<n;j*=2,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<n;i++) wv[i]=x[y[i]];
		for(i=0;i<m;i++) ws[i]=0;
		for(i=0;i<n;i++) ws[wv[i]]++;
		for(i=1;i<m;i++) ws[i]+=ws[i-1];
		for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
	return;
}

其实,我个人认为,对于这个算法以及代码,无需过分深入地理解,只需记忆即可,理解只是为了帮助记忆罢了。先解释变量:n为字符串长度,m为字符的取值范围,r为字符串。后面的j为每次排序时子串的长度。

1
2
3
4
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[x[i]=r[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;

这四行代码,进行的是对R中长度为1的子串进行基数排序。x数组在后面需要用到,所以先复制r数组的值。特别需要注意的是,第四行的for语句,初始化语句为i=n-1,如果写得不太熟练,很容易习惯性地写成i=0,我一开始就是。理解这是基数排序的最好方法,找个例子,自己推推….

1
2
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

这两行代码,利用了上一次基数排序的结果,对待排序的子串的第二关键字进行了一次高效地基数排序。我们可以结合下面的图来理解:

不难发现,除了第一次基数排序以外,之后的每次双关键字排序,设此次排序子串长度为j,则从第n-j位开始的子串,其第二关键字均为0,所以得到第一个for语句:for(p=0,i=n-j;i<n;i++) y[p++]=i;使用pascal的朋友们注意了,这里之所以是n-j位,是因为c++的字符串是从第0位开始表示的。这里,p暂时成为了一个计数变量。第二个语句的意义,分析上图也不难理解,这里留给朋友们你们自行思考啦。(不如说我懒…)

1
2
3
4
5
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];

与一开始的4个for语句意义相同,基数排序。至于为什么wv[i]=x[y[i]],这个我想了蛮久没想通…硬记算了- -哪位朋友理解的希望能告诉我一声…

1
2
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
	x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

这个for语句中的初始化语句里,完成了x数组和y数组的交换,用了指针的交换节约时间,简化代码。这里需要注意的是p和i的初始值都是1,不是0.其实如果记得后面的语句,不难看出它们的初始值不能为0,因为后面有i-1和p-1嘛。这个for语句的意义要结合cmp函数来理解。反正,你知道这里p的值表示的是此时关键字不同的串的数量就对了。当 p=n 的时候,说明所有串都已经排好序了(它们的排名都唯一确定)。所以,一开始的循环语句中,循环条件是(p<n)。

另外,在使用倍增算法前,需要保证r数组的值均大于0。然后要在原字符串后添加一个0号字符,具体原因参见罗穗骞的论文。这时候,若原串的长度为n,则实际要进行后缀数组构建的r数组的长度应该为n+1.所以调用da函数时,对应的n应为n+1.

二、后缀数组的应用–height数组

在介绍后缀数组的应用前,先介绍后缀数组的一个重要附属数组:height数组。 1、height 数组:定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公 共前缀,也就是排名相邻的两个后缀的最长公共前缀。 height数组是应用后缀数组解题是的核心,基本上使用后缀数组解决的题目都是依赖height数组完成的。

2、height数组的求法:具体的求法参见罗穗骞的论文。对于height数组的求法,我并没有去深刻理解,单纯地记忆了而已…有兴趣的朋友可以去钻研钻研再和我交流交流 这里给出代码:

1
2
3
4
5
6
7
8
9
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rank[sa[i]]=i;
	for(i=0;i<n;height[rank[i++]]=k)
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
	return;
}

3、一些注意事项:height数组的值应该是从height[1]开始的,而且height[1]应该是等于0的。原因是,因为我们在字符串后面添加了一个0号字符,所以它必然是最小的一个后缀。而字符串中的其他字符都应该是大于0的(前面有提到,使用倍增算法前需要确保这点),所以排名第二的字符串和0号字符的公共前缀(即height[1])应当为0.在调用calheight函数时,要注意height数组的范围应该是[1..n]。所以调用时应该是calheight(r,sa,n)而不是calheight(r,sa,n+1)。要理解清楚这里的n的含义是什么。

calheight过程中,对rank数组求值的for语句的初始语句是i=1 而不是i=0 的原因,和上面说的类似,因为sa[0]总是等于那个已经失去作用的0号字符,所以没必要求出其rank值。当然你错写成for (i=0 ..),也不会有什么问题。

三、后缀数组解题总结:

1、求单个子串的不重复子串个数。SPOJ 694、SPOJ 705.

这个问题是一个特殊求值问题。要认识到这样一个事实:一个字符串中的所有子串都必然是它的后缀的前缀。(这句话稍微有点绕…)对于每一个sa[i]后缀,它的起始位置sa[i],那么它最多能得到该后缀长度个子串(n-sa[i]个),而其中有height[i]个是与前一个后缀相同的,所以它能产生的实际后缀个数便是n-sa[i]-height[i]。遍历一次所有的后缀,将它产生的后缀数加起来便是答案。
代码及题解:http://hi.baidu.com/fhnstephen/blog/item/68f919f849748668024f56fb.html

2、后缀的最长公共前缀。(记为lcp(x,y))

这是height数组的最基本性质之一。具体的可以参看罗穗骞的论文。后缀i和后缀j的最长公共前缀的长度为它们在sa数组中所在排位之间的height值中的最小值。这个描述可能有点乱,正规的说,令x=rank[i],y=rank[j],x<y,那么lcp(i,j)=min(height[x+1],height[x+2]…height[y])。lcp(i,i)=n-sa[i]。解决这个问题,用RMQ的ST算法即可(我只会这个,或者用最近公共祖先那个转化的做法)。

3、最长重复子串(可重叠)

要看到,任何一个重复子串,都必然是某两个后缀的最长公共前缀。因为,两个后缀的公共前缀,它出现在这两个后缀中,并且起始位置时不同的,所以这个公共前缀必然重复出现两次以上(可重叠)。而任何两个后缀的最长公共前缀为某一段height值中的最小值,所以最大为height值中的最大值(即某个lcp(sa[i],sa[i+1]))。所以只要算出height数组,然后输出最大值就可以了。
一道题目和代码:http://hi.baidu.com/fhnstephen/blog/item/4ed09dffdec0a78eb801a0ba.html

4、最长重复不重叠子串 PKU1743

这个问题和3的唯一区别在于能否重叠。加上不能重叠这个限制后,直接求解比较困难,所以我们选择二分枚举答案,将问题转换为判定性问题。假设当时枚举的长度为k,那么要怎样判断是否存在长度为k的重复不重叠子串呢?

首先,根据height数组,将后缀分成若干组,使得每组后缀中,后缀之间的height值不小于k。这样分组之后,不难看出,如果某组后缀数量大于1,那么它们之中存在一个公共前缀,其长度为它们之间的height值的最小值。而我们分组之后,每组后缀之间height值的最小值大于等于k。所以,后缀数大于1的分组中,有可能存在满足题目限制条件的长度不小于k的子串。只要判断满足题目限制条件成立,那么说明存在长度至少为k的合法子串。

对于本题,限制条件是不重叠,判断的方法是,一组后缀中,起始位置最大的后缀的起始位置减去起始位置最小的后缀的起始位置>=k。满足这个条件的话,那么这两个后缀的公共前缀不但出现两次,而且出现两次的起始位置间隔大于等于k,所以不会重叠。

深刻理解这种height分组方法以及判断重叠与否的方法,在后面的问题中起到举足轻重的作用。
练习及题解:http://hi.baidu.com/fhnstephen/blog/item/85a25b208263794293580759.html

5、最长的出现k次的重复(可重叠)子串。 PKU3261

使用后缀数组解题时,遇到“最长”,除了特殊情况外(如问题3),一般需要二分答案,利用height值进行分组。本题的限制条件为出现k次。只需判断,有没有哪一组后缀数量不少于k就可以了。相信有了我前面问题的分析作为基础,这个应该不难理解。注意理解“不少于k次”而不是“等于k次”的原因。如果理解不了,可以找个具体的例子来分析分析。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/be7d15133ccbe7f0c2ce79bb.html

6、最长回文子串 ural1297

这个问题没有很直接的方法可以解决,但可以采用枚举的方法。具体的就是枚举回文子串的中心所在位置i。注意要分回文子串的长度为奇数还是偶数两种情况分析。然后,我们要做的,是要求出以i为中心的回文子串最长为多长。利用后缀数组,可以设计出这样一种求法:求i往后的后缀与i往前的前缀的最长公共前缀。我这里的表述有些问题,不过不影响理解。

要快速地求这个最长前缀,可以将原串反写之后接在原串后面。在使用后缀数组的题目中,连接两个(n个)字符串时,中间要用不可能会出现在原串中,不一样的非0号的字符将它们隔开。这样可以做到不影响后缀数组的性质。然后,问题就可以转化为求两个后缀的最长公共前缀了。具体的细节,留给大家自己思考…(懒…原谅我吧,都打这么多字了..一个多小时了啊TOT )
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/68342f1d5f9e3cf81ad576ef.html

7、求一个串最多由哪个串复制若干次得到 PKU2406

具体的问题描述请参考PKU2406.这个问题可以用KMP解决,而且效率比后缀数组好。 利用后缀数组直接解决本题也很困难(主要是,就算二分答案,也难以解决转变而成的判定性问题。上题也是),但可以同过枚举模板串的长度k(模板串指被复制的那个串)将问题变成一个后缀数组可以解决的判定性问题。首先判断k能否被n整除,然后只要看lcp(1,k+1)(实际在用c写程序时是lcp(0,k))是否为n-k就可以了。

为什么这样就行了呢?这要充分考虑到后缀的性质。当lcp(1,k+1)=n-k时,后缀k+1是后缀1(即整个字符串)的一个前缀。(因为后缀k+1的长度为n-k)那么,后缀1的前k个字符必然和后缀k+1的前k个字符对应相同。而后缀1的第k+1..2k个字符,又相当于后缀k+1的前k个字符,所以与后缀1的前k个字符对应相同,且和后缀k的k+1..2k又对应相同。依次类推,只要lcp(1,k+1)=n-k,那么s[1..k]就可以通过自复制n/k次得到整个字符串。找出k的最小值,就可以得到n/k的最大值了。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/5d79f2efe1c3623127979124.html

8、求两个字符串的最长公共子串。Pku2774、Ural1517

首先区分好“最长公共子串”和“最长公共子序列”。前者的子串是连续的,后者是可以不连续的。

对于两个字符串的问题,一般情况下均将它们连起来,构造height数组。然后,最长公共子串问题等价于后缀的最长公共前缀问题。只不过,并非所有的lcp值都能作为问题的答案。只有当两个后缀分属两个字符串时,它们的lcp值才能作为答案。与问题3一样,本题的答案必然是某个height值,因为lcp值是某段height值中的最小值。当区间长度为1时,lcp值等于某个height值。所以,本题只要扫描一遍后缀,找出后缀分属两个字符串的height值中的最大值就可以了。判断方法这里就不说明了,留给大家自己思考…
题目及题解:
http://hi.baidu.com/fhnstephen/blog/item/8666a400cd949d7b3812bb44.html
http://hi.baidu.com/fhnstephen/blog/item/b5c7585600cadfc8b645aebe.html

9、重复次数最多的重复子串 SPOJ 687,Pku3693

难度比较大的一个问题,主要是罗穗骞的论文里的题解写得有点含糊不清。题目的具体含义可以去参考Pku3693.

又是一题难以通过二分枚举答案解决的问题(因为要求的是重复次数),所以选择朴素枚举的方法。先枚举重复子串的长度k,再利用后缀数组来求长度为k的子串最多重复出现多少次。注意到一点,假如一个字符串它重复出现2次(这里不讨论一次的情况,因为那是必然的),那么它必然包含s[0],s[k],s[2k]…之中的相邻的两个。所以,我们可以枚举一个数i,然后判断从ik这个位置起的长度为k的字符串能重复出现多少次。判断方法和8中的相似,lcp(ik,(i+1)k)/k+1。但是,仅仅这样会忽略点一些特殊情况,即重复子串的起点不在[ik]位置上时的情况。这种情况应该怎么求解呢?
看下面这个例子:
aabababc
当k=2,i=1时,枚举到2的位置,此时的重复子串为ba(注意第一位是0),lcp(2,4)=3,所以ba重复出现了2次。但实际上,起始位置为1的字符串ab出现次数更多,为3次。我们注意到,这种情况下,lcp(2,4)=3,3不是2的整数倍。说明当前重复子串在最后没有多重复出现一次,而重复出现了部分(这里是多重复出现了一个b)。如果我这样说你没有看懂,那么更具体地:
sa[2]=bababc
sa[4]=babc
lcp=bab
现在注意到了吧,ba重复出现了两次之后,出现了一个b,而a没有出现。那么,不难想到,可以将枚举的位置往前挪一位,这样这个最后的b就能和前面的一个a构成一个重复子串了,而假如前挪的一位正好是a,那么答案可以多1。所以,我们需要求出a=lcp(i
k,(i+1)*k)%n,然后向前挪k-a位,再用同样的方法求其重复出现的长度。这里,令b=k-a,只需要lcp(b,b+k)>=k就可以了。实际上,lcp(b,b+k)>=k时,lcp(b,b+k)必然大于等于之前求得的lcp值,而此时答案的长度只加1。没有理解的朋友细细体会下上图吧。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/870da9ee3651404379f0555f.html

10.多个串的公共子串问题 PKU3294

首先将串连接起来,然后构造height数组,然后怎么办呢?
对,二分答案再判断是否可行就行了。可行条件很直观:有一组后缀,有超过题目要求的个数个不同的字符串中的后缀存在。即,假如题目要求要出现在至少k个串中,那么就得有一组后缀,在不同字符串中的后缀数大于等于k。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/49c3b7dec79ec5e377c638f1.html

11、出现或反转后出现所有字符串中的最长子串 PKU1226

http://hi.baidu.com/fhnstephen/blog/item/7fead5020a16d2da267fb5c0.html

12、不重叠地至少两次出现在所有字符串中的最长子串

spoj220 http://hi.baidu.com/fhnstephen/blog/item/1dffe1dda1c98754cdbf1a35.html

之所以把两题一起说,因为它们大同小异,方法在前面的题目均出现过。对于多个串,连起来;反转后出现,将每个字符串反写后和原串都连起来,将反写后的串和原串看成同一个串;求最长,二分答案后height分组;出现在所有字符串中(反写后的也行),判断方法和10一样,k=n而已;不重叠见问题4,只不过这里对于每个字符串都要进行检验而已。

13、两个字符串的重复子串个数。 Pku3415

我个人觉得颇有难度的一个问题。具体的题目描述参看Pku3415。
大家可以移步到这:http://hi.baidu.com/fhnstephen/blog/item/bf06d001de30fc034afb51c1.html

14、最后的总结

用后缀数组解题有着一定的规律可循,这是后缀的性质所决定的,具体归纳如下:
1、N个字符串的问题(N>1)
方法:将它们连接起来,中间用不会出现在原串中的,互不相同的,非0号字符分隔开。

2、无限制条件下的最长公共子串(重复子串算是后缀们的最长公共前缀)
方法:height的最大值。这里的无限制条件是对子串无限制条件。最多只能是两个串的最长公共子串,才可以直接是height的最大值。

3、特殊条件下的最长子串
方法:二分答案,再根据height数组进行分组,根据条件完成判定性问题。三个或以上的字符串的公共子串问题也需要二分答案。设此时要验证的串长度为len,特殊条件有:
3.1、出现在k个串中
条件:属于不同字符串的后缀个数不小于k。(在一组后缀中,下面省略)
3.2、不重叠
条件:出现在同一字符串中的后缀中,出现位置的最大值减最小值大于等于len。
3.3、可重叠出现k次
条件:出现在同一字符串中的后缀个数大于等于k。若对于每个字符串都需要满足,需要逐个字符串进行判断。

4、特殊计数
方法:根据后缀的性质,和题目的要求,通过自己的思考,看看用后缀数组能否实现。一般和“子串”有关的题目,用后缀数组应该是可以解决的。

5、重复问题
知道一点:lcp(i,i+k)可以判断,以i为起点,长度为k的一个字符串,它向后自复制的长度为多少,再根据具体题目具体分析,得出算法即可。