还有什么

asciidoc 是一个功能比较丰富的轻量级标记语言，可以直接生成 HTML 或 DocBook 格式文档，再经由 DocBook 可以支持更多格式输出。这里主要介绍 asciidoc 的 中文PDF 输出，在 asciidoc 中 PDF 输出支持两种方式： FOP 和 dblatex ，下面将分别予以介绍。

a2x -f pdf --xsl-file=fo.xsl --fop --fop-opts="-c fop.xconf" file.txt

\usepackage {xeCJK}

\setmainfont{Latin Modern Roman}
\setsansfont{Latin Modern Sans}
\setmonofont{Latin Modern Mono}

\setCJKmainfont[BoldFont={WenQuanYi Micro Hei}]{AR PL UMing CN}
\setCJKsansfont[BoldFont={WenQuanYi Micro Hei}]{AR PL UMing CN}
\setCJKmonofont{WenQuanYi Micro Hei Mono}

a2x -f pdf --dblatex-opts='-b xetex -s ./dblatex.sty' file.txt

分类：Linux | 没有评论 | 返回顶部

在daemon程序设计中，如果进行多进程处理，往往就需要考虑这样一个问题：如何在父进程中kill所有子进程。因为daemon的pid文件只保存了父进程的PID，所以外界只能通过信号与父进程通信，子进程的退出工作需要由父进程间接下达。

在 int kill(pid_t pid, int sig) 中如果pid参数为0，那么会向该进程所在进程组里的所有进程发送信号，可以通过它来实现父进程与子进程的通信。

但有一点需要注意，父进程在调用 kill(0, SIGTERM) 时，不单给子进程发送SIGTERM信号，同时还会给自己发送。所以在调用 kill() 之后，需要调用 exit() 直接退出。子进程在接收到SIGTERM之后也会相继退出。

分类：Linux， Python | 没有评论 | 返回顶部

对一个问题的求解，递归与递代是两个全然不同的思维方式，递归是自上而下的，而递代则是自下而上的。而两者的联系也是非常紧密，在将递归计算过程转化为递代时，可以以递归的调用过程作为基础进行递代结构设计。以下用几个例子加以说明。

以对2^n的求解说明线性递归转化为递代的思路。根据2^n = 2 * 2^(n-1)及2^0 = 1，用Scheme实现的递归代码如下：

(define (expt-2 n)
  (if (= n 0)
    1
    (* 2 (expt-2 (- n 1))))

比如计算(expt-2 3)的函数调用过程如下：

(expt-2 3)
(* 2 (expt-2 2))
(* 2 (* 2 (expt-2 1)))
(* 2 (* 2 (* 2 (expt-2 0))))
(* 2 (* 2 (* 2 1)))
(* 2 (* 2 2))
(* 2 4)
8

而当用自下而上的递代方式考虑这问题时，依然可以从递推公式2^n = 2 * 2^(n-1)中下手。

(expt-2 0) => 1
(expt-2 1) => 2 * (expt-2 0)
(expt-2 2) => 2 * (expt-2 1)
...

(define (expt-2 n)
  (define (iter product n)
    (if (= n 0)
      product
      (iter (* product 2) (- n 1))))
  (iter 1 n))

而明显的不同是，虽然从最终的运算顺序来看，都是先计算(expt-2 0)，再是(expt-2 1)，直到(expt-2 n)，但两者的函数调用顺序是不同的，递归在函数调用栈中临时保存了计算过程，所以它可以以自上而下的方式运算，下层调用的结果为上层调用使用，这里的中间值就可以用函数返回值来传递。而递代中，为解决递归中保存中间计算过程所带来的性能问题，需要以自下而上的方式组织运算，这样上层调用的结果被下层调用使用，这样中间值必需通过参数传递。

从以上的讨论中可以看出，设计递归和递代的出发点是相似的，都从问题的递推公式出发。递归更接近平时的思维逻辑，而将递归转为递代的一个关键是上一层调用需要准备好所有需要的值，通过参数和临时变量传递过下一层。

两者的另一点不同是，由于递归和递代都是嵌套调用，都需要考虑如何判定结束。递归中可以通过判定递推的起点。而递代中由于是从递推的起点开始计算，所以需要通过其它方式判定。

以下再以Fibonacci及Hanoi为例，说明对于较复杂递归转递代的处理。

以下是SICP中Fibonacci的递归与递代实现。

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2)))))

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

Fibonacci的递推公式为fib(n) = fib(n-1) + fib(n-2)，根据上面的讨论，设计递代，主要抓住两点，一是上层调用为下层调用准备好所有需要的值，也就是fib(n-1)和fib(n-2)，对应于代码中的a和b。第二点是如何判断递代结束，这里是通过count计数递代次数。

再来看Hanoi的问题：

(define (hanoi n)
  (define (rec disk-num source-pole dest-pole spare-pole)
    (cond ((= disk-num 1) (list (list source-pole dest-pole)))
          (else (append
                  (rec (- disk-num 1)
                       source-pole
                       spare-pole
                       dest-pole)
                  (rec 1 source-pole dest-pole '())
                  (rec (- disk-num 1)
                       spare-pole
                       dest-pole
                       source-pole)))))
  (rec n 'a 'b 'c))

(define (hanoi-list num from to spare)
  (define (iter n table)
    (define (hash key)
      (let ((val (assoc key table)))
        (if val (cadr val) '())))
    (cond ((= n 0) table)
          (else (iter (- n 1)
                      (list (list (list from to)
                                  (append (hash (list from spare))
                                          (list (list from to))
                                          (hash (list spare to))))
                            (list (list from spare)
                                  (append (hash (list from to))
                                          (list (list from spare))
                                          (hash (list to spare))))
                            (list (list to from)
                                  (append (hash (list to spare))
                                          (list (list to from))
                                          (hash (list spare from))))
                            (list (list to spare)
                                  (append (hash (list to from))
                                          (list (list to spare))
                                          (hash (list from spare))))
                            (list (list spare from)
                                  (append (hash (list spare to))
                                          (list (list spare from))
                                          (hash (list to from))))
                            (list (list spare to)
                                  (append (hash (list spare from))
                                          (list (list spare to))
                                          (hash (list from to)))))))))
  (iter num '()))

(define (hanoi-2 n from to spare)
  (let ((lst (hanoi-list (- n 1) from to spare)))
    (append (cadr (assoc (list from spare) lst))
            (list (list from to))
            (cadr (assoc (list spare to) lst)))))

同样，对于Hanoi问题，关键还是两点，Hanoi的递推思路是先移到n-1个盘到spare柱，再移动最下面的盘到to柱，最后将spare中的n-1个盘移到to柱。这样对于下一层递代调用来说，需要上一层准备将n-1盘从from移动到spare及从spare移动到to的步骤。由于在不同层次，from, to, spare的角色会相互替换，所以上一层调用需要准备和将n-1个盘在3个柱之间移动的所有6种情况的步骤。而递代的结束通过n来计数递代调用层次。

分类：programming | 没有评论 | 返回顶部

相信但凡学习过编程的人，对于链表都不会陌生。而在C中，语言本身和标准库中都并没有针对链表的接口，这样，作为如些重要的一类数据结构，在编程实践中必然经常需要实现它。所以有必要稍作整理。

在BSD中的queue.h对各类链表提供了比较统一的宏接口，如单链表、双向链表等，可以作为参考。

以下主要总结单向链表的一些实现方式。

最为直接的方法是在需要组织为链表的结构体中添加指向本身的指针，比如在struct user中添加struct user *next成员。这一方法会导致数据抽象并不完美，因为对于struct user来说，*next与它实现的数据抽象无关，同样链表的整体结构要依赖与它的数据。

另一方式就是通过定义struct user_list_node，其中包含两个成员，一个是指向struct user的指针，另一个是指向struct user_list_node的指针。再定义一个struct uer_list指向链表头。这一方式的不足是对于使用struct user_list的代码，需要同时处理struct user_list及struct user_list_node两个结构，使得接口不大明朗。

最后，可以借鉴Lisp中list的思想，将第二种方法中的struct user_list及struct user_list_node合并，这样，任何这个链表结点的指针都是一个完整的链表结构，是原链表的一个子链表。这个方式的不足是在不另外包裹一层结构体的情况下，无法方便地实现向链表尾部追加数据，而这其实也是Lisp中list的一个特点。

分类：C | 没有评论 | 返回顶部

相信对Linux稍有了解的人对pipeline（管道）都会非常熟悉。而我对于下面描述的现象却一直没有足够重视。

当处理一个大文件时，比如tmp.log，cat tmp.log | head -10要比cat tmp.log >/dev/null快许多。这里哪个程序在起作用呢？是cat，head还是这个pipeline机制？

在浏览了cat和head的代码后，确认它们没有对这一块做特殊处理。应该是与pipeline有关。在翻阅pipe及write的manual之后，大致可以对这一现象作如下解释：

在执行cat tmp.log | head -10时，cat程序的标准输出与head的标准输入以pipe相连。head在读取完10行之后程序退出，导致pipe中的reading end被关闭，这时cat在继续写入pipe时会产生SIGPIPE信号，该信号的默认处理方式是终止程序。另外，pipe的缓存是有限的，所以即使cat运行快于head，由于缓存的限止，cat后续的写动作会被block，直到reader端读取了数据，缓存再次出现空闲。所以由于head只需要读取10行数据，cat不可能写入太多数据到pipe，从而也不会从tmp.log中读取大量数据。在Wikipedia中对此有比较详细的说明。

可以通过写两个简单的测试程序来证实。一个producer和一个consumer，两者由pipeline连接，producer不断写，而consumer不读取，这样在producer中的write会被block。在producer中捕捉SIGPIPE，让conumer先于producer退出，producer会出现SIGPIPE。

分类：Linux | 没有评论 | 返回顶部

如果在C程序中碰到文本处理，极有可能会涉及到临时文件的处理。

在不同情境下，可能对临时文件接口有不同的需求。比如有时只是将临时文件作为临时的数据存储空间，无需与其它进程共享，这时可以直接使用tmpfile()函数。tmpfile()返回的是一个FILE *句柄，由tmpfile()创建的临时文件没有实际的文件名，这样处理的好处是，当程序结束时，文件不需要程序手动删除。

但如果你需要与其它进程共享临时文件，或是需要以临时文件的文件名作为参数调用其它程序以传递数据，tmpfile()就不能胜任了，这时就需要用到mkstemp()。mkstemp()通过传入的模板字符串生成一个不存在的文件名，同时创建该文件，将文件句柄做为函数返回值返回，而文件名可以从被修改了的模板字符串中得到。

以上两个函数算是比较现代的了，如果对于历史感兴趣，可以看看下面三个函数。

mktemp()函数用于生成一个不存在的文件名。这个函数现在已经不提倡使用，在POSIX.1-2008中甚至已经将其删除了。从glibc mktemp(3)中可以了解到，不提倡使用mktemp()的主要原因是mktemp()只是生成一个当前不存在的文件名，而没有直接创建该文件。而如果需要创建这个文件，那么在mktemp()和creat()之间可能这个临时文件被其它进程创建，从而导致文件创建失败。

tmpnam()函数有与mktemp()一样的问题，同时，当传入参数为NULL时，由于需要用到static变量，所以不是线程安全的。在POSIX.1-2008中已经不建议使用。

tempnam()与tmpnam()相似，只是参数更多，可控性更高。同样，在POSIX.1-2008中已不建议使用。

分类：Linux | 没有评论 | 返回顶部

文本处理是脚本语言的一个重要应用，而修改文件某行或几行文本内容也是经常遇到的问题。由于类UNIX系统中的文件系统一般都不是结构化文件系统，在修改文件时并不是很方便，以下整理了一些比较常用的模式。由于一些接口只在特定语言中有，这里用主流的Python，Ruby和PHP三大脚本语言为例。

注意以下方法主要是从代码的可读性及实现的便捷性上考虑的，并没有考虑性能因素，所以只适用于对小文件的修改。

最为直接的一种方式是先建一临时文件，对原文件以行遍历，如果无需修改，直接写入文件，需要修改的行，将修改后的内容写入临时文件，最后关闭临时文件，覆盖原文件。Ruby中的Tempfile模块可以方便地创建临时文件。这一方法的一个不足是，无法保留文件的原有权限。在处理系统配置文件时需要特别注意。

Python中有一fileinput模块，如果以fileinput.input('foo.txt', inplace=True)形式打开文件，标准输出会被重定向到打开文件，原文件内容被移至一个临时文件，随后只需将需要写入新文件的内容打印到标准输出就可以了。另外，在调用fileinput.input()之后记得要fileinput.close()。这个相对于上面说的Ruby方式，主要是省去了临时文件的操作。可惜的是，可能是出于实现上的考虑，对原文件的处理不是先保留，最后用新文件覆盖。而是先移为临时文件了，这样在外理过程中，就会出现文件内容不完备的过程，但这一方式的优点是，保留了原有文件权限等属性。

也可以利用PHP中的file()及file_put_contents()函数方便的实现对文件的修改。file()函数读取文件全部内容以数组形式返回。在得到数组之后，可以对其以哈希数组方式foreach，以行号为键，行内容为值，如需要修改，替换数组中的该项。最后，通过file_put_contents()函数将数组内容写回文件。而在Ruby中与之对应的是IO#puts，Python则需要write(''.join(str_table))。

分类：Linux | 没有评论 | 返回顶部

pidfile一般用于daemon程序，主要作用是保证在系统中只存在该daemon的一个进程，同时也便于系统统一管理这些daemon程序。

那么程序在实现pidfile功能时具体需要做哪些处理呢？可以从这个纯Python实现中入手。

一般的daemon程序，不管最终接口是直接用C实现还是用SHELL包装，都需要提供start，stop及restart功能。

start过程需要处理的问题：

1.1 确保系统中没有该daemon的进程。如果有，则不能启动程序。
1.2 在daemon化之后，创建pidfile，写入pid。
1.3 注册atexit()，确保在程序退出时清除pidfile文件。

stop过程做的处理：

2.1 如果pidfile不存在，无需其它动作。
2.2 如果pidfile存在，kill原有进程，并确认进程不存在。在旧进程异常退出时，比如直接用_exit(2)退出程序时，可能pidfile不会被删除，所以在kill进程之后还要确认pidfile文件已被删除。

restart动作：

3.1 stop
3.2 start

下面再来看一下NetBSD，FreeBSD以及Debian对于pidfile的不同处理方式。

在NetBSD中，pidfile的创建工作是由daemon程序通过pidfile(3)库函数完成，而其它动作则是通过在/etc/rc.subr中的run_rc_command中执行。pidfile(3)函数主要完成1.2及1.3的动作。NetBSD相关代码可以在这里找到。

FreeBSD与NetBSD相似，也是主要通过run_rc_command实现对daemon程序的管理。只是1.1功能FreeBSD通过pidfile_open()实现，内部使用了flopen(3)，相当于用flock(2)实现进程间的互斥。而1.2在FreeBSD中则是以pidfile_write()实现。另外，对于pidfile的清理工作，FreeBSD提供了pidfile_remove()，由于FreeBSD是通过flock机制实现互斥，而不是单纯通过文件是否存在判断，所以不需要严格地考虑删除问题，也就不需要用到atexit()了。FreeBSD的代码可以看这里。

而在Debian中是通过start-stop-daemon程序实现对pidfile的处理。start-stop-daemon中的pidfile是可选的，如果不建pidfile的话，它会类似于killall用文本匹配的方式查找进程。start-stop-daemon中的pidfile可以是由程序创建，也可以由start-stop-daemon建立。具体关于start-stop-daemon的说明可以看这里。如是对具体实现感兴趣，可以在dbpkg源码包中找到。

分类：Linux | 没有评论 | 返回顶部

之前写过如何在SHELL中使用文件锁，这里对flock作更为详细的说明。

先说说advisory锁与mandatory锁的区别，从字面上理解，advisory是建议性的，而mandatory则是强制性的。advisory lock只是文件的一个属性，它并没有对文件的内容进行保护，程序在没有获得锁时仍然可以修改文件的内容。而mandatory lock则是对文件的内容进行保护。flock是一个advisory锁，所以文件的完整性是由程序保证的。这里对这两者有简单的说明。

在使用flock时，需要明确LOCK_SH和LOCK_EX的概念。在一个文件被锁的前提下，如果该锁是LOCK_EX，所有其它请求LOCK_SH或LOCK_EX的进程都将被block，当该锁是LOCK_SH时，进程请求LOCK_SH将被通过，而请求LOCK_EX将被block。

Linux中flock是基于file table实现的，所以在fork()或dup()之后，可以有多个fd共享锁，而解锁必须要显式地使用LOCK_UN或关闭所有与该file table entry相关联的fd。

最后，Wikipedia有对Linux及Windows中的文件锁比较详尽的说明，值得一读。

分类：Linux | 没有评论 | 返回顶部

在SHELL中实现文件锁，有两种简单的方式。

一是利用普通文件，在脚本启动时检查特定文件是否存在，如果存在，则等待一段时间后继续检查，直到文件不存时创建该文件，在脚本结束时删除文件。为确保脚本在异常退出时文件仍然能被删除，可以借助于trap "cmd" EXIT TERM INT命令。一般这类文件存放在/var/lock/目录下，操作系统在启动时会对该目录做清理。

另一种方法是是使用flock命令。使用方式如下，这个命令的好处是等待动作在flock命令中完成，无需另外添加代码。

(
flock 300
...cmd...
flock -u 300
) > /tmp/file.lock

但flock有个缺陷是，在打开flock之后fork()，子进程也会拥有锁，如果在flock其间有运行daemon的话，必需确保daemon在启动时已经关闭了所有的文件句柄，不然该文件会因为daemon一直将其置于打开状态而无法解锁。

分类：Linux | 没有评论 | 返回顶部