3089:爬楼梯

总时间限定: 
1000ms

内部存款和储蓄器限制: 
65536kB

描述
树老师爬楼梯,他得以每一回走一级或许贰级,输入楼梯的级数,求差异的走法数
比如:楼梯一共有叁级,他得以每一回都走一流,只怕第壹次走一流,第叁遍走两级
也足以率先次走两级,第一回走拔尖,一共三种方式。

输入
输入包含若干行,每行包涵二个正整数N,代表楼梯级数,一 <= N <= 30

输出
不等的走法数,每1行输入相应1行输出

样例输入
5
8
10

样例输出
8
34
89

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cmath>
 5 using namespace std;
 6 int tot=0;
 7 int find(int n)
 8 {
 9     if(n==1)return 1;
10     else if(n==2) return 2;
11     else return find(n-2)+find(n-1);
12 }
13 int main() {
14     int a,b;
15     while(cin>>a)
16     {
17         cout<<find(a)<<endl;
18     }
19     return 0;
20 }

 

系统中有众多与时光相关的顺序(比如定期执行的天职,某临时间执行的天职,推迟一段时间执行的职责),因而,时间的军管对于linux来说相当主要。

 

首要内容:

  • 系统时间
  • 定时器
  • 定时器相关概念
  • 定时器执行流程
  • 贯彻程序延迟的主意
  • 定时器和延期的例证

 

一. 系统时间

系统中管理的岁月有二种:实际时间和定时器。

一.一  实际时间

其实时间正是切实可行中钟表上显示的时光,其实基础中并不常用那些时刻,首尽管用户空间的先后有时须求获得当前岁月,

为此基本中也管理着那个日子。

 

其实时间的收获是在开机后,内核起先化时从RTC读取的。

水源读取这一个小时后就将其放入内核中的 xtime
变量中,并且在系统的运作中不断更新这一个值。

注:EscortTC正是实时机械钟的缩写,它是用来存放在系统时间的装备。一般和BIOS壹样,由主板上的电池供电的,所以就算关机也可将时刻保存。

 

事实上时间存放的变量 xtime 在文件 kernel/time/timekeeping.c中。

/* 按照16位对齐,其实就是2个long型的数据 */
struct timespec xtime __attribute__ ((aligned (16)));

/* timespec结构体的定义如下, 参考 <linux/time.h>  */
struct timespec {
    __kernel_time_t    tv_sec;            /* seconds */
    long        tv_nsec;        /* nanoseconds */
};

/* _kernel_time_t 定义如下 */
typedef long        __kernel_time_t;

 

系统读写 xtime 时用的正是各类锁。

/* 写入 xtime 参考 do_sometimeofday 方法 */
int do_settimeofday(struct timespec *tv)
{
/* 省略 。。。。 */
    write_seqlock_irqsave(&xtime_lock, flags); /* 获取写锁 */
/* 更新 xtime */
    write_sequnlock_irqrestore(&xtime_lock, flags); /* 释放写锁 */
/* 省略 。。。。 */
    return 0;
}

/* 读取 xtime 参考 do_gettimeofday 方法 */
void do_gettimeofday(struct timeval *tv)
{
    struct timespec now;

    getnstimeofday(&now); /* 就是在这个方法中获取读锁,并读取 xtime */
    tv->tv_sec = now.tv_sec;
    tv->tv_usec = now.tv_nsec/1000;
}

void getnstimeofday(struct timespec *ts)
{
/* 省略 。。。。 */

/* 顺序锁中读锁来循环获取 xtime,直至读取过程中 xtime 没有被改变过 */
    do {
        seq = read_seqbegin(&xtime_lock);

        *ts = xtime;
        nsecs = timekeeping_get_ns();

        /* If arch requires, add in gettimeoffset() */
        nsecs += arch_gettimeoffset();

    } while (read_seqretry(&xtime_lock, seq));
/* 省略 。。。。 */
}

上述情景中,写锁必供给事先于读锁(因为 xtime
必须登时更新),而且写锁的使用者很少(一般唯有系统定期更新xtime的线程要求具有那一个锁)。

那多亏 顺序锁的行使场景。

 

1.2 定时器

定时器是根本中首要性利用的时日管理章程,通过定时器,能够使得的调度程序的举行。

动态定时器是根本中动用相比多的定时器,下边重点谈论的也是动态定时器。

 

统计,2. 定时器

基本中的定时器有二种,静态定时器和动态定时器。

静态定时器一般实施了有个别周期性的固化学工业作:

  • 履新系统运维时刻
  • 创新实际时间
  • 在SMP系统上,平衡各种处理器上的周转队列
  • 检查当前经过是或不是用尽了本身的时间片,即使用尽,必要再行调度。
  • 立异财富消耗和处理器时间计算值

 

动态定时器顾名思义,是在急需时(一般是推迟程序执行)动态成立的定时器,使用后绝迹(一般都以只用3遍)。

貌似大家在基本代码中利用的定时器基本都以动态定时器,上面重点谈论动态定时器相关的定义和平运动用方法。

 

叁. 定时器相关概念

定时器的使用中,上边2个概念充足主要:

  1. HZ
  2. jiffies
  3. 时间暂停处理程序

 

3.1 HZ

节拍率(HZ)是石英钟中断的效能,表示的1秒内石英钟中断的次数。

例如 HZ=100 表示1秒内触发九十七次机械钟中断程序。

 

HZ的值1般与系统布局有关,x八陆 种类布局相似定义为 100,参考文件
include/asm-generic/param.h

HZ值的尺寸的安装进程实际上正是平衡 精度和属性 的经过,并不是HZ值越高越好。

HZ值

优势

劣势

高HZ 时钟中断程序运行的更加频繁,依赖时间执行的程序更加精确,
对资源消耗和系统运行时间的统计更加精确。
时钟中断执行的频繁,增加系统负担
时钟中断占用的CPU时间过多

 

除此以外,有一些亟需小心,内核中接纳的HZ大概和用户空间中定义的HZ值分歧,为了制止用户空间获得错误的小时,

水源中也定义了 USEOdyssey_HZ,即用户空间利用的HZ值。

诚如的话,USECRUISER_HZ 和 HZ 都是离开整数倍,内核中通过函数
jiffies_to_clock_t 来将根本来将根本中的 jiffies转为 用户空间
jiffies

/* 参见文件: kernel/time.c  *
//*
 * Convert jiffies/jiffies_64 to clock_t and back.
 */
clock_t jiffies_to_clock_t(unsigned long x)
{
#if (TICK_NSEC % (NSEC_PER_SEC / USER_HZ)) == 0
# if HZ < USER_HZ
    return x * (USER_HZ / HZ);
# else
    return x / (HZ / USER_HZ);
# endif
#else
    return div_u64((u64)x * TICK_NSEC, NSEC_PER_SEC / USER_HZ);
#endif
}
EXPORT_SYMBOL(jiffies_to_clock_t);

 

3.2 jiffies

jiffies用来记录自系统运转以来发出的总节拍数。比如系统运营了 N 秒,那么
jiffies就为 N×HZ

jiffies的相干定义参考头文件 <linux/jiffies.h> 
include/linux/jiffies.h

/* 64bit和32bit的jiffies定义如下 */
extern u64 __jiffy_data jiffies_64;
extern unsigned long volatile __jiffy_data jiffies;

 

行使定时器时一般都是以jiffies为单位来延缓程序执行的,比如延迟八个点子后举行的话,执行时间就是jiffies+五

三11人的jiffies的最大值为 2^32-一,在选择时有望会产出回绕的难点。

比如说下边包车型客车代码:

unsigned long timeout = jiffies + HZ/2; /* 设置超时时间为 0.5秒 */

while (timeout < jiffies)
{
    /* 还没有超时,继续执行任务 */
}

/* 执行超时后的任务 */

平常情状下,上面包车型大巴代码没不平日。当jiffies接近最大值的时候,就会产出回绕难题。

由于是unsinged
long
花色,所以jiffies达到最大值后会变成0然后再逐步变大,如下图所示:

统计 1

 

从而在上述的循环代码中,会产出如下情状:

统计 2

  1. 巡回中第三回相比较时,jiffies = J一,没有过期
  2. 巡回中第四回相比时,jiffies =
    J二,实际已经过期了,不过出于jiffies超越的最大值后又从0开端,所以J二不以万里为远低于timeout
  3. while循环会执行相当长日子(> 二^3二-1个点子)不会完成,大约相当于死循环了

 

为了规避回扰的标题,能够应用<linux/jiffies.h>头文件中提供的
time_aftertime_before等宏

#define time_after(a,b)        \
    (typecheck(unsigned long, a) && \
     typecheck(unsigned long, b) && \
     ((long)(b) - (long)(a) < 0))
#define time_before(a,b)    time_after(b,a)

#define time_after_eq(a,b)    \
    (typecheck(unsigned long, a) && \
     typecheck(unsigned long, b) && \
     ((long)(a) - (long)(b) >= 0))
#define time_before_eq(a,b)    time_after_eq(b,a)

上述代码的原理其实就是将 unsigned long 类型转换为 long
类型来制止回扰带来的错误,

long 类型超越最大值时变化趋势如下:

统计 3

 

long 型的多寡的转体晤面世在 二^3一-一 变为 -二^3二 的时候,如下图所示:

统计 4

  1. 率先次比较时,jiffies = J1,没有过期
  2. 第叁次相比时,jiffies = J二,1般 J二 是负数
    理论上 (long)timeout – (long)J2 = 正数 – 负数 = 正数(result)
    可是,这些正数(result)1般会当先 二^3一 –
    1,所以long型的result又发生了三回回绕,变成了负数。
    除非timeout和J二之间的间隔 > 2^3六个点子,result的值才会为正数(注1)。

注1:result的值为正数时,必须是在result的值
小于 二^3一-一 的情形下,大于 2^31-壹 会爆发回绕。

统计 5

上航海用教室中 X + Y 表示timeout 和 J2之间通过的节拍数。

result 小于 2^31-1 ,也就是 timeout – J2 < 2^31 – 1

timeout 和 -J二表示的节拍数如上海体育地方所示。(因为J2是负数,全部-J2象征上图所示范围的值)

因为 timeout + X + Y – J2 = 2^31-1 + 2^32

所以 timeout – J2 < 2^31 – 1 时, X + Y > 2^32

也正是说,当timeout和J二之间通过至少 二^三十八个点子后,result才或许成为正数。

timeout和J二之间相差这么多节拍是不可能的(不信能够用HZ将那个点子换算成秒就清楚了。。。)

 

利用time_after宏就可以巧妙的幸免回绕带来的过期判断难题,将事先的代码改成如下代码即可:

unsigned long timeout = jiffies + HZ/2; /* 设置超时时间为 0.5秒 */

while (time_after(jiffies, timeout))
{
    /* 还没有超时,继续执行任务 */
}

/* 执行超时后的任务 */

 

三.三 机械钟中断处理程序

钟表中断处理程序作为系统定时器而注册到根本中,连串布局的不等,或许石英钟中断处理程序中拍卖的剧情不1。

不过以下这一个骨干的行事都会进行:

  • 获得 xtime_lock 锁,以便对走访 jiffies_6四 和墙上时间 xtime
    进行珍重
  • 亟待时回答或另行设置系统机械钟
  • 周期性的运用墙上时间更新实时石英钟
  • 调用 tick_periodic()

 

tick_periodic函数位于: kernel/time/tick-common.c

static void tick_periodic(int cpu)
{
    if (tick_do_timer_cpu == cpu) {
        write_seqlock(&xtime_lock);

        /* Keep track of the next tick event */
        tick_next_period = ktime_add(tick_next_period, tick_period);

        do_timer(1);
        write_sequnlock(&xtime_lock);
    }

    update_process_times(user_mode(get_irq_regs()));
    profile_tick(CPU_PROFILING);
}

其间最要紧的是 do_timer 和 update_process_times 函数。

自笔者通晓的手续实行了简易的注释。

void do_timer(unsigned long ticks)
{
    /* jiffies_64 增加指定ticks */
    jiffies_64 += ticks;
    /* 更新实际时间 */
    update_wall_time();
    /* 更新系统的平均负载值 */
    calc_global_load();
}

void update_process_times(int user_tick)
{
    struct task_struct *p = current;
    int cpu = smp_processor_id();

    /* 更新当前进程占用CPU的时间 */
    account_process_tick(p, user_tick);
    /* 同时触发软中断,处理所有到期的定时器 */
    run_local_timers();
    rcu_check_callbacks(cpu, user_tick);
    printk_tick();
    /* 减少当前进程的时间片数 */
    scheduler_tick();
    run_posix_cpu_timers(p);
}

 

4. 定时器执行流程

此地斟酌的定时器执行流程是动态定时器的履行流程。

 

四.一 定时器的定义

定时器在根本中用三个链表来保存的,链表的各样节点都以2个定时器。

参见头文件 <linux/timer.h>

struct timer_list {
    struct list_head entry;
    unsigned long expires;

    void (*function)(unsigned long);
    unsigned long data;

    struct tvec_base *base;
#ifdef CONFIG_TIMER_STATS
    void *start_site;
    char start_comm[16];
    int start_pid;
#endif
#ifdef CONFIG_LOCKDEP
    struct lockdep_map lockdep_map;
#endif
};

经过投入条件编写翻译的参数,能够扩充1些调节和测试音信。

 

四.二 定时器的生命周期

3个动态定时器的生命周期中,一般会因此上面包车型客车几个步骤:

统计 6

  1. 开头化定时器:

    struct timer_list my_timer; / 定义定时器 /
    init_timer(&my_timer); / 初叶化定时器 /

 

  1. 填充定时器:

    my_timer.expires = jiffies + delay; / 定义超时的旋律数 /
    my_timer.data = 0; / 给定时器函数字传送入的参数 /
    my_timer.function = my_function; / 定时器超时时,执行的自定义函数 /

    / 从定时器结构体中,我们得以看来那几个函数的原型应该如下所示: /
    void my_function(unsigned long data);

 

  1. 激活定时器和改动定时器:

激活定时器之后才会被触发,不然定时器不会实施。

修改定时器重尽管修改定时器的延迟时间,修改定时器后,不管原先定时器有未有被激活,都会处于激活状态。

 

填充定时器结构从此,能够只激活定时器,也可以只修改定时器,也得以激活定时器后再修改定时器。

故此填充定时器结构和接触定时器之间的步调,也正是虚线框中的步骤是不显明的。

add_timer(&my_timer);  /* 激活定时器 */
mod_timer(&my_timer, jiffies + new_delay);  /* 修改定时器,设置新的延迟时间 */

 

  1. 接触定时器:

每便石英钟中断处理程序会检讨已经激活的定时器是还是不是过期,假诺超时就实施定时器结构中的自定义函数。

 

  1. 删去定时器:

激活和未被激活的定时器都得以被删除,已经过期的定时器会自行删除,不用尤其去删除。

/*
 * 删除激活的定时器时,此函数返回1
 * 删除未激活的定时器时,此函数返回0
 */
del_timer(&my_timer);

在多核处理器上用 del_timer
函数删除定时器时,或许在剔除时刚刚另1个CPU核上的石英钟中断处理程序正在进行这些定时器,于是就形成了竞争条件。

为了幸免竞争条件,提出使用 del_timer_sync 函数来删除定时器。

del_timer_sync
函数会等待别的总括机上的定时器处理程序全部终了后,才删除内定的定时器。

/*
 * 和del_timer 不同,del_timer_sync 不能在中断上下文中执行
 */
del_timer_sync(&my_timer);

 

5. 落到实处程序延迟的办法

基本中有个利用定时器达成延迟的函数 schedule_timeout

其一函数会将眼下的职务睡眠到钦定时间后提醒,所以等待时不会占有CPU时间。

/* 将任务设置为可中断睡眠状态 */
set_current_state(TASK_INTERRUPTIBLE);

/* 小睡一会儿,“s“秒后唤醒 */
schedule_timeout(s*HZ);

 

查看 schedule_timeout 函数的兑现格局,能够见到是哪些运用定时器的。

signed long __sched schedule_timeout(signed long timeout)
{
    /* 定义一个定时器 */
    struct timer_list timer;
    unsigned long expire;

    switch (timeout)
    {
    case MAX_SCHEDULE_TIMEOUT:
        /*
         * These two special cases are useful to be comfortable
         * in the caller. Nothing more. We could take
         * MAX_SCHEDULE_TIMEOUT from one of the negative value
         * but I' d like to return a valid offset (>=0) to allow
         * the caller to do everything it want with the retval.
         */
        schedule();
        goto out;
    default:
        /*
         * Another bit of PARANOID. Note that the retval will be
         * 0 since no piece of kernel is supposed to do a check
         * for a negative retval of schedule_timeout() (since it
         * should never happens anyway). You just have the printk()
         * that will tell you if something is gone wrong and where.
         */
        if (timeout < 0) {
            printk(KERN_ERR "schedule_timeout: wrong timeout "
                "value %lx\n", timeout);
            dump_stack();
            current->state = TASK_RUNNING;
            goto out;
        }
    }

    /* 设置超时时间 */
    expire = timeout + jiffies;

    /* 初始化定时器,超时处理函数是 process_timeout,后面再补充说明一下这个函数 */
    setup_timer_on_stack(&timer, process_timeout, (unsigned long)current);
    /* 修改定时器,同时会激活定时器 */
    __mod_timer(&timer, expire, false, TIMER_NOT_PINNED);
    /* 将本任务睡眠,调度其他任务 */
    schedule();
    /* 删除定时器,其实就是 del_timer_sync 的宏
    del_singleshot_timer_sync(&timer);

    /* Remove the timer from the object tracker */
    destroy_timer_on_stack(&timer);

    timeout = expire - jiffies;

 out:
    return timeout < 0 ? 0 : timeout;
}
EXPORT_SYMBOL(schedule_timeout);

/* 
 * 超时处理函数 process_timeout 里面只有一步操作,唤醒当前任务。
 * process_timeout 的参数其实就是 当前任务的地址
 */
static void process_timeout(unsigned long __data)
{
    wake_up_process((struct task_struct *)__data);
}

schedule_timeout 一般用于延迟时间较长的次序。

此地的延迟时间较长是对此电脑而言的,其实也正是延迟大于 三个点子(jiffies)。

 

对于壹些极其短暂的推迟,比如只有1ms,甚至一us,一ns的延迟,必须选用特殊的延期方法。

1s = 1000ms = 1000000us = 1000000000ns
(1秒=1000毫秒=1000000微秒=1000000000纳秒)

假定 HZ=100,那么 1个点子的时光距离是 百分之十0秒,大致10ms左右。

之所以对于那几个极端短暂的延迟,schedule_timeout 函数是心有余而力不足选取的。

万幸根本对于这个短暂,精确的延期供给也提供了相应的宏。

/* 具体实现参见 include/linux/delay.h
 * 以及 arch/x86/include/asm/delay.h
 */
#define mdelay(n) ...
#define udelay(n) ...
#define ndelay(n) ...

经过那个宏,能够简简单单的贯彻延迟,比如延迟 五ns,只需 ndelay(伍); 即可。

 

那些短延迟的兑现原理并不复杂,

首先,内核在运行时就计算出了当下电脑一秒能履行多少次巡回,即
loops_per_jiffy

(loops_per_jiffy 的乘除方法参见 init/main.c 文件中的
calibrate_delay 方法)。

下一场算出延迟 五ns 须求循环多少次,执行那么多次空循环即可直达延迟的意义。

 

loops_per_jiffy 的值能够在运维消息中来看:

[root@vbox ~]# dmesg | grep delay
Calibrating delay loop (skipped), value calculated using timer frequency.. 6387.58 BogoMIPS (lpj=3193792)

自身的虚拟机中看到 (lpj=3一9三七九二)

 

陆. 定时器和推迟的例子

下边包车型客车事例测试了短延迟,自定义定时器以及 schedule_timeout 的使用:

#include <linux/sched.h>
#include <linux/timer.h>
#include <linux/jiffies.h>
#include <asm/param.h>
#include <linux/delay.h>
#include "kn_common.h"

MODULE_LICENSE("Dual BSD/GPL");

static void test_short_delay(void);
static void test_delay(void);
static void test_schedule_timeout(void);
static void my_delay_function(unsigned long);

static int testdelay_init(void)
{
    printk(KERN_ALERT "HZ in current system: %dHz\n", HZ);

    /* test short delay */
    test_short_delay();

    /* test delay */
    test_delay();

    /* test schedule timeout */
    test_schedule_timeout();

    return 0;
}

static void testdelay_exit(void)
{
    printk(KERN_ALERT "*************************\n");
    print_current_time(0);
    printk(KERN_ALERT "testdelay is exited!\n");
    printk(KERN_ALERT "*************************\n");
}

static void test_short_delay()
{
    printk(KERN_ALERT "jiffies [b e f o r e] short delay: %lu", jiffies);
    ndelay(5);
    printk(KERN_ALERT "jiffies [a f t e r] short delay: %lu", jiffies);
}

static void test_delay()
{
    /* 初始化定时器 */
    struct timer_list my_timer;
    init_timer(&my_timer);

    /* 填充定时器 */
    my_timer.expires = jiffies + 1*HZ; /* 2秒后超时函数执行 */
    my_timer.data = jiffies;
    my_timer.function = my_delay_function;

    /* 激活定时器 */
    add_timer(&my_timer);
}

static void my_delay_function(unsigned long data)
{
    printk(KERN_ALERT "This is my delay function start......\n");
    printk(KERN_ALERT "The jiffies when init timer: %lu\n", data);
    printk(KERN_ALERT "The jiffies when timer is running: %lu\n", jiffies);
    printk(KERN_ALERT "This is my delay function end........\n");
}

static void test_schedule_timeout()
{
    printk(KERN_ALERT "This sample start at : %lu", jiffies);

    /* 睡眠2秒 */
    set_current_state(TASK_INTERRUPTIBLE);
    printk(KERN_ALERT "sleep 2s ....\n");
    schedule_timeout(2*HZ);

    printk(KERN_ALERT "This sample end at : %lu", jiffies);
}

module_init(testdelay_init);
module_exit(testdelay_exit);

在那之中使用的 kn_common.h 和 kn_common.c 参见在此以前的博客
《Linux内核设计与落成》读书笔记(6)-
内核数据结构

Makefile如下:

# must complile on customize kernel
obj-m += mydelay.o
mydelay-objs := testdelay.o kn_common.o

#generate the path
CURRENT_PATH:=$(shell pwd)
#the current kernel version number
LINUX_KERNEL:=$(shell uname -r)
#the absolute path
LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
#complie object
all:
    make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
    rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
#clean
clean:
    rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned

 

实行测试命令及查看结果的不2秘籍如下:(作者的测试系统是 CentOS 陆.3 x6四)

[root@vbox chap11]# make
[root@vbox chap11]# insmod mydelay.ko 
[root@vbox chap11]# rmmod mydelay.ko 
[root@vbox chap11]# dmesg | tail -14
HZ in current system: 1000Hz
jiffies [b e f o r e] short delay: 4296079617
jiffies [a f t e r] short delay: 4296079617
This sample start at : 4296079619
sleep 2s ....
This is my delay function start......
The jiffies when init timer: 4296079619
The jiffies when timer is running: 4296080621
This is my delay function end........
This sample end at : 4296081622
*************************
2013-5-9 23:7:20
testdelay is exited!
*************************

 

结果注明:

  1. 短延迟只延迟了 5ns,所以进行前后的jiffies是平等的。

    jiffies [b e f o r e] short delay: 4296079617
    jiffies [a f t e r] short delay: 4296079617

 

  1. 自定义定时器延迟了一秒后执行自定义函数,由于本身的种类HZ=一千,所以jiffies应该相差一千

    The jiffies when init timer: 4296079619
    The jiffies when timer is running: 4296080621

实际上jiffies相差了 1002,多了2个节拍

 

  1. schedule_timeout 延迟了2秒,jiffies应该相差 三千

    This sample start at : 4296079619
    This sample end at : 4296081622

实际上jiffies相差了 2003,多了3个节拍

 

上述结果也印证了定时器的延迟并不是那么纯粹,差了2,三个点子其实正是截断误差二,3阿秒(因为HZ=一千)

倘若HZ=100的话,3个旋律是10飞秒,那么定时器的固有误差大概就发现不了了(误差唯有2,三微秒,未有超多三个点子)。