Crane
Table_bottom

Search
Loading
Table_bottom

分类
Table_bottom

随机文章
Table_bottom

标签云
Table_bottom

最新评论
Table_bottom

链接
Table_bottom

功能
Table_bottom

从nginx说cpu affinity

众所周知,nginx是高性能web server的代表,看nginx的代码,随处可以发现对性能的考究,像建立数据结构考虑到cpu的cache line size,比较字符串4个字节转换成整数比较等,这里我们说一下cpu affinity(或cpu亲和)。nginx一般推荐是有几个cpu核,就设置几个worker,这样可以减少进程调度的开销,从而充分地利用cpu。再设置下worker_cpu_affinity,则会把worker绑定在相应的cpu上,从而让worker进程固定在一个cpu上执行,减少切换cpu的cache miss,能获得更好的性能。
 
这是nginx文档中介绍 worker_cpu_affinity 的部分
syntax: worker_cpu_affinity cpumask ...;
default: —
context: main
 
Binds worker processes to the sets of CPUs. Each CPU set is represented by a bitmask of allowed CPUs. There should be a separate set defined for each of the worker processes. By default, worker processes are not bound to any specific CPUs.
 
For example,
 
    worker_processes    4;
    worker_cpu_affinity 0001 0010 0100 1000;
 
binds each worker process to a separate CPU, while
 
    worker_processes    2;
    worker_cpu_affinity 0101 1010;
 
binds the first worker process to CPU0/CPU2, and the second worker process to CPU1/CPU3. The second example is suitable for hyper-threading. 
 
The directive is only available on FreeBSD and Linux. 
 
看nginx的实现,相关内容在源文件os/unix/ngx_setaffinity.c中
void
ngx_setaffinity(uint64_t cpu_affinity, ngx_log_t *log)
{
    cpu_set_t   mask;
    ngx_uint_t  i; 

    ngx_log_error(NGX_LOG_NOTICE, log, 0,
                  "sched_setaffinity(0x%08Xl)", cpu_affinity);

    CPU_ZERO(&mask);
    i = 0;
    do {
        if (cpu_affinity & 1) {
            CPU_SET(i, &mask);
        }  
        i++;
        cpu_affinity >>= 1;
    } while (cpu_affinity);

    if (sched_setaffinity(0, sizeof(cpu_set_t), &mask) == -1) {
        ngx_log_error(NGX_LOG_ALERT, log, ngx_errno,
                      "sched_setaffinity() failed");
    }
}
 
略去上面代码中的nginx_log_t等其它不相关内容,这里主要的操作就是sched_setaffinity。上面nginx文档中有说这个特性仅在FreeBSD和linux上有效,如果系统是FreeBSD,调用的是cpuset_setaffinity;如果系统是linux,调用的是sched_setaffinity(就是上面代码中展示的)。
以linux为例,man sched_setaffinity看一下,系统调用原型是
int sched_setaffinity(pid_t pid, size_t cpusetsize,cpu_set_t *mask);
 
pid是进程id,一般填0,表示改变当前进程的cpu affinity。
cpu_set_t,指示要设置的cpu affinity,类似select中的fd_set和FD系列宏,这个cpu_set_t的操作也有操作宏,具体可参见man CPU_SET。

cpu_set_t的定义见/usr/include/bits/sched.h
/* Size definition for CPU sets.  */
# define __CPU_SETSIZE  1024
# define __NCPUBITS (8 * sizeof (__cpu_mask))
/* Type for array elements in 'cpu_set_t'.  */
typedef unsigned long int __cpu_mask;
/* Data structure to describe CPU mask.  */
typedef struct
{
  __cpu_mask __bits[__CPU_SETSIZE / __NCPUBITS];
} cpu_set_t;
 
可以看到是用bit位来表示cpu的状态的,宏定义写了支持1024个cpu,一般应该是足够使用了。另外对cpu_set_t的操作宏CPU_SET实际的定义也在/usr/include/bits/sched.h中,也就是对__cpu_mask的一些位操作。

/* Access functions for CPU masks.  */
#  define __CPU_ZERO_S(setsize, cpusetp) \
  do {                                        \
    size_t __i;                                   \
    size_t __imax = (setsize) / sizeof (__cpu_mask);                  \
    __cpu_mask *__bits = (cpusetp)->__bits;                   \
    for (__i = 0; __i < __imax; ++__i)                        \
      __bits[__i] = 0;                                \
  } while (0)
# endif
# define __CPU_SET_S(cpu, setsize, cpusetp) \
  (__extension__                                  \
   ({ size_t __cpu = (cpu);                           \
      __cpu / 8 < (setsize)                           \
      ? (((__cpu_mask *) ((cpusetp)->__bits))[__CPUELT (__cpu)]           \
     |= __CPUMASK (__cpu))                            \
      : 0; }))
# define __CPU_CLR_S(cpu, setsize, cpusetp) \
  (__extension__                                  \
   ({ size_t __cpu = (cpu);                           \
      __cpu / 8 < (setsize)                           \
      ? (((__cpu_mask *) ((cpusetp)->__bits))[__CPUELT (__cpu)]           \
     &= ~__CPUMASK (__cpu))                           \
      : 0; }))
# define __CPU_ISSET_S(cpu, setsize, cpusetp) \
  (__extension__                                  \
   ({ size_t __cpu = (cpu);                           \
      __cpu / 8 < (setsize)                           \
      ? ((((const __cpu_mask *) ((cpusetp)->__bits))[__CPUELT (__cpu)]        \
      & __CPUMASK (__cpu))) != 0                          \
      : 0; }))
 
再结合nginx文档中的例子和nginx的源码来看
    worker_processes    4;
    worker_cpu_affinity 0001 0010 0100 1000;
如果这个内容写的nginx的配置文件中,然后nginx启动或者重新加载配置的时候,看到worker_process是4,就会起4个worker,然后把worker_cpu_affinity后面的四个值当作四个cpu affinity mask,分别调用ngx_setaffinity,然后就把四个worker进程分别绑定到cpu 0-3上。
 
如果手头没有nginx,上面的代码就不能在nginx上直观的看到,我们可以自己写个代码来验证一下。
#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>

int print_cpu_affinity()
{
     int i = 0;
     cpu_set_t cpu_mask;

     if(sched_getaffinity(0, sizeof(cpu_set_t), &cpu_mask) == -1)
     {
          printf("get_cpu_affinity fail, %s\n", strerror(errno));
          return -1;
     }

     printf("cpu affinity: ");
     for(i = 0; i < CPU_SETSIZE; i++)
     {
          if(CPU_ISSET(i, &cpu_mask))
               printf("%d ", i);
     }
     printf("\n");
     return 0;
}

int set_cpu_affinity(uint32_t cpu_affinity)
{
     int i = 0;
     cpu_set_t cpu_mask;

     CPU_ZERO(&cpu_mask);
     for(i = 0;cpu_affinity; i++, cpu_affinity >>= 1)
     {
          if(cpu_affinity & 1)
          {
               CPU_SET(i, &cpu_mask);
          }
     }
     if(sched_setaffinity(0, sizeof(cpu_set_t), &cpu_mask) == -1)
     {
          printf("set_cpu_affinity fail, %s\n", strerror(errno));
          return -1;
     }

     return 0;
}

void hold()
{
     while(1)
     {
          ;
     }
}

int main(int argc, char **argv)
{
     uint32_t cpu_affinity = 10;

     if( argc < 2 )
     {
          printf("no affinity given, use cpu_affinity = 10\n");
     }
     else
     {
          cpu_affinity = strtoul(argv[1], NULL, 2);
     }

     print_cpu_affinity();

     set_cpu_affinity(cpu_affinity);

     print_cpu_affinity();

     hold();

     return 0;
}

编译运行

$ cc     cpu_affinity.c   -o cpu_affinity
$ ./cpu_affinity 100
cpu affinity: 0 1 2 3 4 5 6 7 
cpu affinity: 2
$ mpstat -P ALL 1 
Average:     CPU    %usr   %nice    %sys %iowait    %irq   %soft  %steal  %guest  %gnice   %idle
Average:     all   12.51    0.00    0.00    0.00    0.00    0.00    0.06    0.00    0.00   87.43
Average:       0    0.00    0.00    0.17    0.00    0.00    0.00    0.00    0.00    0.00   99.83
Average:       1    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
Average:       2   99.50    0.00    0.00    0.00    0.00    0.00    0.50    0.00    0.00    0.00
Average:       3    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
Average:       4    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
Average:       5    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
Average:       6    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
Average:       7    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
可以看到cpu affinity设置成功了,进程占用了整个cpu2。
 
设置cpu affinity还有对接口 pthread_getaffinity_np和pthread_setaffinity_np ,这是在 sched_setaffinity这个系统调用的基础上封装的,用线程的时候可以考虑用这个。
 
用fork产生的child会继承父进程的cpu affinity,进程中产生的也会继承主进程的cpu affinity。
taskset是一个单独的工具,可以设置cpu affinity,既可以在程序启动的时候指定,也可以设置正在运行的进程的cpu affinity。
用taskset来启动我们上面这个程序

# taskset -c 3,5-7 ./cpu_affinity 100
cpu affinity: 3 5 6 7
cpu affinity: 2
可以看到,程序启动的时候的cpu affinity就是-c参数设置的,然后又被我们改成2了。
 
对于正在运行的进程,可以这样,还是以上面的程序为例

# pgrep cpu_affinity
11353
# taskset -p  -c 3,5-7  11353
pid 11353's current affinity list: 2
pid 11353's new affinity list: 3,5-7
可以看到,这个程序之前被我们设置成在cpu2上运行,被taskset改成了3,5-7了。

继续阅读

那些优雅的代码

在Quora上看到一个问题,你见到的最优雅的代码是什么(http://www.quora.com/Elegant-Code/What-is-the-most-elegant-line-of-code-youve-seen),觉得挺有意思的,整理一下。

注:以下代码可能是各种五花八门的语言,但是关键不在语法,在语义,只要能明白意思就行了。

function gcd(a, b) { return b ? gcd(b, a % b) : a; }
while(a%=b^=a^=b^=a);
辗转相除法计算最大公约数,辗转相除法见这里(http://en.wikipedia.org/wiki/Binary_GCD_algorithm),wikipedia上更有各种版本的实现,递归的,效率高的。

main() {
  char c = getchar();
  (c == '+' || c == '-' || c == '*' || c == '/') ? main(), main() : 0;
  putchar(c);
}
前缀表达式转换成后缀表达式,概念参见这里这里

A=A+B-(B=A)
交换A和B的值,C语言才需要这样的技巧,python最直白,a, b = b, a


return (!(x & (x-1)));
判断x是否为2的幂数,位运算的技巧

for( c = 0; v; c++) v &= (v - 1);
计算hamming weight(wiki),二进制表示中有多少个1。之前也有一篇文章说这个,这里

while(*s++ = *t++);
拷贝字符串

:(){:|:&};:
bash 炸弹,定义了一个函数,名字就是冒号,这个函数会不断的fork自己,导致资源用完,系统挂掉

while( x --> 0){
//...
}
这个有趣,x --> 0,有种x趋近于0的错觉

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;          // evil floating point bit level hacking
  i = 0x5f3759df - (i >> 1);  // what the fuck?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}
有名的quake源码中的计算根号分之一的快速算法,原理是牛顿迭代法,神奇的是what the fuck那一行,选用了一个异常接近正常答案的值,使得只需要一次迭代就得到了答案。wiki有解释,http://en.wikipedia.org/wiki/Fast_inverse_square_root

def r(a):i=a.find('0');~i or exit(a);[min[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])
一行代码解数读,递归算法

这个python要写得再pythonic一些才优雅。

看了一会,有些代码就是trick并不优雅,还是就到这里吧!
 

冷血杀手OOM_Killer

 

前几天在折腾systemtap,其实我没想折腾来着,我就是想装个玩玩而已。需要有debug_info的内核,没问题啊,archlinux下这个easy,我从abs拉一个linux的PKGBUILD来改一下配置,按说立马就能make一个出来,我的linux实机上也确实没问题,一下子就出来一个,再装上systemtap,试两个命令,一切工作正常。但是我还有个windows下的虚拟机,有时在win下活动的时候偶尔也用用,就是在这货上装的时候出了问题,当开始编译的时候,我就关上屏幕睡觉去了,一觉起来,却发现没打好包,屏幕上提示什么链接vmlinuz的那个脚本报错,怪了,这脚本能有bug才怪。但是在公司的电脑上虚拟机却没问题,比了下是虚拟机设置的内存大小不一样,出问题的这个内存太小,于是我就去系统日志看了下,发现有句日志报了oom_killer启动把ld给杀掉了,我屮,就说链接的脚本报错,ld还没链完,就被干掉了,当然没结果了。知道问题就好办了,多开点swap让它干活去呗,也就啥事都没有了。
 
这个oom_killer就是Out Of Memory Killer,当系统的内存和交换区用尽的时候,系统为了保证可用性,会挑选出进程kill掉,为了证明是系统有意地行为,不是系统不稳定,不是系统bug,oom_killer会在干掉进程后,在系统日志里留下记录,大有此货是我杀,你能奈我何的风范。
 
一般系统日志中的输出类似这样(我当时的没留下来,从网上搜了一个)
python invoked oom-killer: gfp_mask=0x1200d2, order=0, oomkilladj=4
Pid: 13996, comm: python Not tainted 2.6.27-gentoo-r8cluster-e1000 #9

Call Trace:
 [<ffffffff8025ab6b>] oom_kill_process+0x57/0x1dc
 [<ffffffff802460c7>] getnstimeofday+0x53/0xb3
 [<ffffffff8025ae78>] badness+0x16a/0x1a9
 [<ffffffff8025b0a9>] out_of_memory+0x1f2/0x25c
 [<ffffffff8025e181>] __alloc_pages_internal+0x30f/0x3b2
 [<ffffffff8026fea0>] read_swap_cache_async+0x48/0xc0
 [<ffffffff8026ff6f>] swapin_readahead+0x57/0x98
 [<ffffffff80266d0e>] handle_mm_fault+0x408/0x706
 [<ffffffff8057da33>] do_page_fault+0x42c/0x7e7
 [<ffffffff8057baf9>] error_exit+0x0/0x51

Mem-Info:
Node 0 DMA per-cpu:
CPU    0: hi:    0, btch:   1 usd:   0
CPU    1: hi:    0, btch:   1 usd:   0
CPU    2: hi:    0, btch:   1 usd:   0
CPU    3: hi:    0, btch:   1 usd:   0
Node 0 DMA32 per-cpu:
CPU    0: hi:  186, btch:  31 usd: 103
CPU    1: hi:  186, btch:  31 usd:  48
CPU    2: hi:  186, btch:  31 usd: 136
CPU    3: hi:  186, btch:  31 usd: 183
Active:480346 inactive:483 dirty:0 writeback:10 unstable:0
 free:3408 slab:5146 mapped:1408 pagetables:2687 bounce:0
Node 0 DMA free:8024kB min:20kB low:24kB high:28kB active:1156kB inactive:0kB present:8364kB pages_scanned:3246 all_unreclaimable? yes
lowmem_reserve[]: 0 2003 2003 2003
Node 0 DMA32 free:5608kB min:5716kB low:7144kB high:8572kB active:1920228kB inactive:1932kB present:2051308kB pages_scanned:2941301 all_unreclaimable? yes
lowmem_reserve[]: 0 0 0 0
Node 0 DMA: 8*4kB 3*8kB 4*16kB 3*32kB 4*64kB 3*128kB 2*256kB 3*512kB 3*1024kB 1*2048kB 0*4096kB = 8024kB
Node 0 DMA32: 42*4kB 6*8kB 1*16kB 0*32kB 2*64kB 1*128kB 0*256kB 0*512kB 1*1024kB 0*2048kB 1*4096kB = 5608kB
325424 total pagecache pages
323900 pages in swap cache
Swap cache stats: add 20776604, delete 20452704, find 7856195/10744535
Free swap  = 151691424kB
Total swap = 156290896kB
524032 pages RAM
9003 pages reserved
331431 pages shared
186210 pages non-shared
Out of memory: kill process 12965 (bash) score 2236480 or a child
Killed process 13996 (python)
 
如果出现了这样的日志,就证明oom_killer已经干活完毕,不知哪个倒霉鬼进程已经挂在它手下了。要是生产环境中碰到这样的事情,生产进程被干掉了,就危险了,因此研究oom_killer挑选目标的方法也许就能帮助特别重要的进程逃过一劫。
 
当内存耗尽的时候,会触发oom_killer出来干活,oom_killer会遍历所有进程,并给每个进程打分,这里得分可不是什么好事,oom_killer扫完所有进程后会把得分最高的那个进程干掉。
 
oom_killer的评分会考虑很多因素,主要有这么几个方面(linux 3.7.10-1 mm/oom_kill.c),最低分0,最高1000.
  1. 进程的内存大小,包括RSS,页表,swap使用。1KB计一分,root进程减去3%的分
  2. proc/PID/oom_score_adj 参数的分数加上。这个值默认是0,范围[-1000,1000]
以前貌似评价标准有好多,现在只有简单的判断内存使用和sysctl参数了。比如这里的资料,评分标准就比较多:http://linux-mm.org/OOM_Killer
 
proc中有几个参数与oom killer有关系
  1. /proc/sys/vm/panic_on_oom 如果设置为1,那么oom killer启动的时候就会触发kernel panic。默认是0,咋一看设置为非0没啥用,但是kernel文档说的是集群中可以用来做failover,也可以设置为panic_on_oom=2+kdump,可以得到一个内核dump事后分析。
  2. /proc/sys/vm/oom_kill_allocating_task 设置为非0,则触发oom的进程会收到信号,不再对其他进程评分。默认是0。
  3. /proc/sys/vm/oom_dump_tasks 设置为非0,oom killer启动时就会输出进程列表,打印vm相关信息,rss,页表,swap使用,oom_score_adj,进程名字,pid,可以查看oom_killer选择的依据。默认是1。
  4. /proc/<PID>/oom_score_adj 评分的时候可以用来调整分数,负值可以减少评分,正值可以增加评分,取值-1000到1000,-1000可以完全禁止oom killer
  5. /proc/<PID>/oom_adj和/proc/<PID>/oom_score 兼容老的内核,oom_adj,取值从-16到15,-17可以禁止oom killer kill这个进程。oom_score显示oom killer评出来的分数。

程序员兵器之代码搜索工具

工欲善其事,必先利其器。对于程序员来说,除却编辑器,编译器这些引起N多纷争的神器不谈,代码搜索无疑是个很常见的事情,有个趁手的工具那自然是极好的。

说起这个话题,老前辈grep(wiki)自然必须要首先说一说,grep当仁不让的奉献了N多年,伴随Unix而生,更是在如今的*nix系统中必占一席之地。grep由Ken Thompson操刀写成,名字取自ed编辑器的g/re/p命令,自1973正式服役以来,赢得众多好评,为Unix-like系统的文本处理一大利器。grep功能强大在于支持regular expression(如果不知道regular expression为何物,作为一个程序员,你摊上事了,不过想要精通regular expression,你又摊上一个大事),模式匹配使用了Boyer-Moore算法,并且对Boyer-Moore算法做了相当的优化,有一个GNU grep为什么如此快的文章详细介绍了这一个(看这里

事实上,作为每一个*nix系统必备的工具,有了grep和regex(regular expression简写),在搜索文本方面,几乎没多少困难了,更何况还有egrep(支持扩展的regex),zgrep(支持从压缩包匹配)等等更为强大的武装。而且掌握了这两大玩意,随便来一个*nix的系统,要从一堆文本中找出需要的东西应该都足够了。

但是,这么一个历史悠久,功能强大的工具也不能满足码农们日益增长的代码搜索需求,说大一点,正则表达式可以支撑绝大部分的文本匹配需求,但是复杂的正则表达式带来的是速度上的损耗,码农们日复一日的码代码,现在随便抓个代码库,都一大把的代码,更不要说像linux kernel这种重量级的codebase了,千万级的代码,想要找点什么东西不够快怎么行。快是一个方面,更好用也是一个很重要的方面,用户体验好,生产效率才高嘛。

有人的地方就有江湖,有程序员的地方就有需求。江湖路上没有永远的高手,昨日的高手是明日的英雄成名的基础。程序员为了能早点写完代码,去找找妹子,那自然要尽可能地追求各种效率,于是就有代表更强生产力的工具陆续出现在江湖。

首先出场,ack,掌声。。。

ack  grep-like text finder(项目主页

为什么要使用ack,它有什么优点呢?

ack用纯perl写成的脚本,这意味着任何支持perl的环境里都可以使用,安装方便,拷个文件就完事了。ack使用了高度优化的perl正则表达式,并且只搜索需要搜索的文件,略过那些备份文件,版本控制目录,而且支持只在一种语言的源文件中查找,而且输出结果更美观,比grep的要好看,还可以高亮搜索条目,重要的一点是,ack的参数和grep差不多,习惯grep的人能无缝切换到ack。噢,还有一点,ack打起来比grep快,哈哈。官方列出的why ack

ack能忽略版本控制目录或者只搜索一种语言的源文件很好用,试比较一下这两个场景

在一个svn版本库中搜索代码

$ grep pattern $(find . -type f | grep -v '\.svn')

$ ack pattern

只搜索perl源码文件

$ grep pattern $(find . -name '*.pl' -or -name '*.pm' -or -name '*.pod' | grep -v .svn)

$ ack --perl pattern

比grep命令要节省时间,而且结果还更美观。

安装ack超级简单,有standalone版本(http://betterthangrep.com/ack-standalone),也可以使用发行版的包管理工具来搜索,或者参见这里(http://betterthangrep.com/install/)

ack是很强大(还有传说中的ack 2.0在开发中),但是江山代有才人出,一山更比一山高。一般情况下“但是”这个中国词一出,前面的都要悲剧。下一位选手the silver searcher更是力压ack大胜grep。

the silver searcher(后面简称ag,因为命令行是ag,哈哈,ag又比ack要好打),项目主页(https://github.com/ggreer/the_silver_searcher

ag的介绍语是

The Silver Searcher

  An attempt to make something better than ack (which itself is better than grep). 

据说比ack能快上3-5倍,还可以自定义忽略对象,而且,命令比ack要短33%,lol

为什么快?

1. 明文字符串使用Boyer-Moore-Horspool算法     

2. 使用mmap

3. 多线程

4. ……

具体可以参见:https://github.com/ggreer/the_silver_searcher/blob/master/README.md

ag是用C写的,需要pcre库的支持,源码可以从github的仓库获得。

这些都是说的,是骡子是马,还要拉出来溜溜才行,下面以kernel-3.6.11代码为例,来试试这几大武器。

$ time grep -r out_of_memory *

real    1m10.134s
user    0m0.153s
sys     0m8.576s

$ time grep  out_of_memory $(find . -type f | grep -v '\.git')

real    1m15.837s
user    0m0.557s
sys     0m9.379s

$ time ack out_of_memory

real    1m18.256s
user    0m4.870s
sys     0m12.683s

$ time ag out_of_memory

real    0m49.022s
user    0m0.550s
sys     0m10.309s

大致看一下,ack其实和grep差不多的,甚至grep还快一点,ack的优点就是使用方便,输出更直观,但是ag就是实打实的快很多了。so,the winner is ag。

PS:根据ag作者介绍,还有个git-grep,速度和ag差不多,但是只能在git仓库里面用。

update:更多类似工具,参见这里:http://betterthangrep.com/more-tools/

 

sed实现n++

sed,按其名字,也就是个stream editor,就做各种字符串操作很在行,至于要做运算什么的那得是awk的事了,没想一时看到sed官网上居然有个这样的例子,把一个数字加1,使用sed来做,挺有意思的,瞄了一下,注解一下。
sed本身没有处理运算的支持,所以这个例子也是实际上使用了处理字符串的方法来模拟数学操作。主要思想就是考虑这两种情况:

    1. 如果最后一位不是9,那么只需要动一位,做一个对应替换就OK。
    2. 如果最后一位或者几位有9,那么就需要做标记,因为同时要替换好几位数字。

继续阅读