Linear Programming Revisited

初次接触线性规划好像还是初中的时候。那时还不知道原来LP是一个这么NB的东西，可以用来解生活中如此多的问题。
在运筹学、优化、算法中都能见到它的身影。关于它，我重新认识到了几点东西：

1.LP有多项式的算法。因此，如果一个问题被形式化为一个多项式规模的LP，则它可以用椭圆法或内点法在多项式时间内解决。
并且可以使用一些LP的软件包（CPLEX,glpk等）高校地解决问题。

2.LP不是灵丹妙药。算法导论说：为一个特别问题设计的一个有效的算法，
譬如用于单源最短路问题的Dijkstra算法，或者最大流的push-relabel方法，经常在理论和实践中都比LP更有效。

3.线性规划的真正力量在于其求解新问题的能力。真实世界中，充满了LP可解的各种问题。LP同时也对各种我们没有已知有效算法的问题特别有用。

4.我的命题与暂时的理解（证明）
命题：如果一个问题能formalize成多项式个限制的LP，则它必然不是NPC问题。（不知道这个是不是证明NP=P的一个途径之一……）

后来查阅资料得知，现在解决LP的多项式方法，包括椭圆法和内点法，都是weakly polynomial time的，即算法执行时间依赖输入的值的大小，如k=input value，复杂度是O(nk)。当k的值是指数级，O(nk)是指数级的。以上论断不正确。

另外，平时解的很多问题，是整数规划（包括0-1规划）或者混合规划，它们都是NP-hard的，而普通的线性规划却有有效的多项式解法（即上述所提的椭圆法，内点法。

最纯粹的数学美:对角化方法(diagonal method)

一、前言
对角化方法是由数学家康托于1873年提出的，当时关心的是测量无限集合的规模问题。
假如有两个集合，我们可以比较它们的大小吗？

对于其中一个是有限的集合，答案是trivial的。
但假如对于两个集合都是infinite的，直观上也许会觉得，是无法比较的。
然而，康托尔提出的对角化方法，非常优雅地解决了这个问题。

他注意到，对于两个有限集合，如果其中一个的元素能与另一个集合的元素一一对应（可以理解为双射），则它们规模相同。
而不管这两个集合究竟元素有多少个。
这个思想直接比较两个元素，打破了比较两个集合大小传统的思想框框：通过集合元素个数来比较。

二、一个例子
N是自然数集，E是偶自然数的集合。N={1,2,3,...}，E={2,4,6...}
直观上，E属于N，因为E是N的一个真子集。但根据康托尔的理论，N与E具有相同的规模。
显然对于N中每一个元素，使用f(x)=2*x来映射到E中的每一个元素即可。

三、可数的集合(countable set)
定义1：称一个集合是可数的，如果它的元素个数有限，或它与自然数集N有相同的规模。
一个有无限元素的集合可能是可数的，也可能是不可数的。
再来一个例子。设Q是正有理数集合，即Q={m/n| m,n 属于 N}。
Q看起来似乎比N大得多，但是，Q与N规模相同，即Q是可数的。
证明如下：

思路：通过排列Q的元素，得到一个序列，该序列的元素"下标"与N的自然序列（1,2,3...）一一对应。
构造Q的一个矩阵如下：
    1    2    3     4    ...
1  1/1 1/2  1/3  1/4 ...
2  2/1 2/2  2/3  2/4 ...
3  3/1 3/2  3/3  3/4 ...
4  4/1 4/2  4/3  4/4 ...
... ...

从1/1开始，按对角线从西南到东北方向，排列所有的矩阵元素。则得到一个序列 1/1,2/1,1/2,3/1,1/3,4/1,3/2,2/3,1/4 ...
注意每次我们都舍弃掉重复的元素(如1/1, 2/2, 3/3以及 2/1, 4/2 ...)
这样就得到了Q与N的一个一一对应。


四、不可数的集合(uncountable set)
定理1：实数集R是不可数的。
要证明R是不可数的，必须证明不存在到N的一一对应。使用反证法。
假设f是R到N的对应，则必须找到一个x属于R，使得x与N中的任何元素都不能配对。
证明的思路非常巧妙：使用构造方法，来构造出这个不能配对的x。
设f存在且f(1) = 3.14159.... f(2) = 55.5555.... f(3)=....
即R中的3.14159对应到N中的1，55.5555对应到2等等。
假设x是0到1之间的一个数，只关注其小数点后的数字。为使任意f(n)都不存在x=f(n)
只要保证x的第k位小数不等于f(k)的第k位小数即可。
即，对于以上给定的f(1),f(2)，x的小数第一位不等于1，任意地，使其为4；第二位不等于5，任意地，使其为6，则x=0.46....
显然x不等于f(1),f(2).因此，沿着小数点的对角线，即可构造出这样一个x，使得x不与任何f(n)相等。

n    f(n)
1    3.14159....   x!=f(1)
2    55.5555...    x!=f(2)
3    0.123456...  x!=f(3)
4    0.500000.... x!=f(4)
....
令x=0.4641....
          1530...

以这种方法下去，就能得到x的所有数字。因此不论n取到多大的值，总能找到这样一个x，使得f(n)中找不到匹配。
注意其中的一个问题：实数的十进制表示法中，有些数是相等的，如 0.999....=1.0000
因此只要在构造过程中总是不选择9与0，即可避免这个问题。

五、对角化方法的应用与意义
对角化方法在计算理论中发挥着重要的作用。
它可以用来证明图灵机的停机问题、图铃不可识别语言等。
即：有些语言是不可判定的（图灵机的停机问题），甚至是图铃不可识别的（图灵机的计算能力）
原因是：根据定理1可以证明，设A={所有语言的集合}，B={所有图灵机的集合}，A是不可数的，但是B却是可数的。
或者说：有不可数的语言（问题），但是却只有可数的图灵机。


六、总结
以上证明、思路是对计算理论导引的归纳与总结。可以说，对角化方法以及对图灵机不可识别、不可判定问题的证明，
是至今为止，我所看到的最优美的数学证明，其意义是哲学性的：
虽然现代计算机异常强大，并且似乎计算能力在不断地增强，但是由于它只是一个有限能力的图灵机模型，
因此无论它如何发展，也不能跨越可计算性的限制。

算法导论：“易处理问题”的定义是哲学方面的，而不是数学方面的

1.虽然把所需运行时间Θ(n^100)的问题作为难处理问题也是合理的，但实际中需要如此高次的多项式时间的问题是非常少的。在实际中，所遇到的典型多项式时间可解问题所需要的时间要少得多。经验表明：一旦一个问题的多项式算法被发现，往往就能发现一些更为有效的算法。

2.对很多合理的计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以在多项式时间内获得解决。我们讨论的大多数使用串行随机存取计算机在多项式时间内能解决的问题类，与抽象的图灵机在多项式时间内可求解的问题是相同的，它与利用并行计算机在多项式时间内可求解的问题类相同。即使处理器数目随输入规模以多项式增加也是这样。

3.多项式时间可解问题类是封闭的。在加法、乘法的组合运算下，多项式是封闭的。例如：一个多项式时间的算法作为另一个多项式时间算法的输入，得到的算法也是多项式时间算法。（O(n^x)+O(n^y) = O(n^x), x>y ）如果另外一个多项式算法对一个多项式时间的子程序进行常数次调用，那么组合算法的运行时间也是多项式的。（O(n^x)*O(n^y)=O(n^(x+y))）

[转载][原创评论]计算机科学经典论文

http://www.tianya.cn/New/PublicForum/Content.asp?strItem=itinfo&idArticle=61295
从Jao的Programming Musing (http://jaortega.wordpress.com/)看到的：Babar Kazar(http://www.zafar.se/bkz/Articles/ClassicCompScienceTexts) 整理了一堆经典论文。Jao强烈建议每个严肃的程序员读每篇论文，说它们都或多或少有意思。粗粗扫了一下，很多论文都没读过。挑了些俺多少知道一点的介 绍。
　　
　　・ An axiomatic basis for computer programming C. A. R. Hoare
　 　Tony Hoare名下的公理化语义（Axiomatic Semantics）。著名的Hoare Triples, P{C}Q, 就是从这里来的。论文不长，双列6页。前辈们就是这样的，6页纸就能开宗立派。不像俺，6页纸连介绍部分都写不周全。哪位老大想知道怎么证明程序正确。前 置条件，不变条件，后置条件的妙用，可以用这篇论文开牙。
　　
　　・ Communicating Sequential Processes (CSP) C. A. R. Hoare
　　Hoare, 又见Hoare。其实也正常。牛人之牛，就在于成就深广。链接的文档应该不算论文，而算专著。260页。从1985年推出到现在20多年过去，这本书的引用率在CS历史上排名第三，可见其影响之深。对并发编程有强烈兴趣的老大可以去钻研一把。我没读过。
　　
　 　・ Call-by-name, call-by-value, and the lambda calculus Gordon Plotkin没读过。只见LtU介绍过。Gordon老大这篇论文的要点之一是要想顺利地对程序进行推导，就需要有合适的lambda理论。想深入理解 call-by-name，call-by-value，和lambda算子的老大们可以上了。
　　
　　・ Towards a theory of type structure John C. Reynolds
　 　号称经典中的经典。不过也没读过。类型系统一直是编程语言研发的热点，也是非常有趣的方向��类型系统的编程好比让机器证明一系列定理。 Reynolds在论文里讨论了什么才是正确的类型结构，和句法正确必须独立于任何具体的类型表达形式，并且给出了带类型的lambda算子的一种扩展， 允许他描述用户自定义类型和多态函数。满篇公式，有勇气去读的老大要有心理准备。
　　
　　・ Structured Programming with go to Statements Donald E. Knuth
　 　这篇论文详细结构化编程时讨论了什么时候用goto，什么时候不用goto。高爷爷精细务实的态度非常值得学习。高老太爷用了一辈子goto(MIX和 MMIX程序里没了Goto怎么玩儿得转嗫？)，岂能轻易被Dijkstra对goto的批评吓退？他仔细探讨了几种不同的程序，考察goto用在那些程 序里的利弊。最后得出结论，goto在某些程序里仍然高效实用。虽然论文是30年前的，但里面的分析手法和利用goto的优化技术至今可用。
　　
　　・ Definitional interpreters for higher-order programming languages John C. Reynolds
　　这篇文章俺喜欢。"Metacircular"这个性感的概念就是在这篇论文里首次提出的。想深入了解用一门语言写出的解释器定义这门语言自身的神奇理念，这篇论文是必读材料。有兴趣的老大可以先读SICP的第四章。
　　
　　・ An APL Machine 1970 Philip S. Abrams
　　只知道APL是门有历史意义的语言。顺便说一句，APL这个名字太土了。A Programming Language ＝＝APL。象什么话嘛。
　　
　　・ The Anatomy of a Large-Scale Hypertextual Web Search Engine Sergey Brin and Lawrence Page
　　网络是个大的矩阵(transition probability matrix of Markov Chain)。网页的声誉(page rank)就是这个巨大矩阵的principle eigenvector的某个元素。嗯，反正我只有佩服的份儿。
　　
　　・ No Silver Bullet: Essence and Accidents of Software Engineering Frederic P. Brooks, Jr.
　　地球银都知道。不用俺多嘴了。
　　
　　・ A Mathematical Theory of Communication Claude Shannon
　 　Bell实验室当年辉煌一时。出了名的叫人做A，结果发明了B。香农老大就是其中杰出代表。香农进了Bell实验室后，居然没人吩咐他干嘛。香农老大转 念一想，自己喜欢数学，Bell的生意尽在通讯，干嘛不看看把数学应用到通讯上有什么结果呢？于是1948年这篇论文问世乐。搞通讯的人崩溃乐。现代信息 理论就诞生乐。
　　
　　・ Bayesian Networks without Tears
　　贝叶斯理论热了好几年了。估计 还会继续热下去。现在信息越来越多，我们已经审美疲劳。大家渴望的不是信息，而是知识。靠个人的力量把信息提炼成知识太慢，我们需要机器的帮忙。机器学习 不热都难，而贝叶斯理论在机器学习里有很好的应用。这篇文章行为浅显，可以轻松读完。对了，那个人人喝骂的微软回形针的智能引擎就是用贝叶斯网络实现的。
　　
　　・ A Universal Algorithm for Sequential Data Compression
　　没读过。无耻地找个借口：我们系开信息理论课的时候，俺刚好毕业。
　　
　　・ A Relational Model of Data for Large Shared Data Banks 1970 Edgar F. Codd
　 　没有关系代数，人类将会怎样？Codd划时代的论文奠定了现代数据库的基础。嘿嘿，其实俺也没有读过这篇论文。顺便说一句，现在的ORM试图把data schema和对象系统映射起来。问题是，data schema只是对关系的一种表达方式而已，还和具体的系统实现有关。也许把对象间的结构和关系映射起来才是正道。
　　
　　・ Let's Build a Compiler 1988-1995
　　教你一步一步写出一坨编译器。不算论文吧。一篇相当不错的指南。
　　
　　・ Gauging Similarity via N-Grams: Language-Independent Sorting... Marc Damashek
　　第一次听说
　　
　　・ Worse Is Better Richard P. Gabriel
　　网上脍炙人口的文章。很有教育意义。简单说，worse is better包括下面几点：
　　-- 简单：设计要简单。但如果接口和实现不能两全，追求实现的简单。文章里给出的Unix vs Multics的例子非常有意思。
　　-- 正确：程序必须在所有可见的方面正确。其它地方，如果简单和正确不能两全，追求简单。
　　-- 一致性：程序不能太不一致。但为了简单，可以在少数地方不一致。
　　-- 完备性：程序应该尽可能照顾到重要的地方，但是不能牺牲简洁。
　　强烈推荐。
　　
　　・ Hints on Programming Language Design C.A.R. Hoare
　　Hoare对设计语言的经验总结。这些经验至今有效。文章很容易读，读后绝对增长程序设计的功力。
　　
　　・ Why Functional Programming Matters John Hughes
　 　为普通程序员准备的大餐，所以写得通俗。没有公式，也没有拗口的术语。着重展示了Fold和Map的强大抽象能力。不由想到我在大学里修的一门课，编程 语言。课是好课，老师是一流老师。课上我们学习了浅显的程序语言理论，重点学习了函数编程（用Common Lisp）和逻辑编程（用Prolog）。这门课彻底改变我对编程的理解，明白了imperative programming和OO programming外还有精彩世界。至今想来都觉得幸运。那门课的作业也很有意思，实现一个驻留内存的数据库，支持关系代数里的常见操作。
　　
　　・ On the Expressive Power of Programming Languages Matthias Felleisen
　　没读过。待读。
　　
　　・ The Early History Of Smalltalk Alan Kay
　 　还有什么好说的呢？Alan Kay这个名字说明一切。30年前Alan Kay就做出来Smalltalk，现在想来仍然让人惊叹。引一段文章Alan Kay评述Smalltalk的话：In computer terms, Smalltalk is a recursion on the notion of computer itself. Instead of dividing "computer stuff" into things each less strong than the whole--like data structures, procedures, and functions which are the usual paraphernalia of programming languages--each Smalltalk object is a recursion on the entire possibilities of the computer. Thus its semantics are a bit like having thousands and thousands of computer all hooked together by a very fast network. Questions of concrete representation can thus be postponed almost indefinitely because we are mainly concerned that the computers behave appropriately, and are interested in particular strategies only if the results are off or come back too slowly.
　　
　　・ Computer Programming as an Art Donald E. Knuth
　 　高老太爷在1974年图灵奖仪式上的致词。真是顶尖geek的风范啊。高太爷在文章里解释了问什么他的书取名为《编程的艺术》。明显他对人们谈到编程时 把科学置于艺术之上很不了然。高爷爷追溯"艺术"的词源，说艺术的本意就是技能，也是技术和技巧两次的起源。从这里开始，他开始讨论艺术和科学的关联，讨 论艺术在编程里的表现形式和意义。用他的话说，他作为教育者和作者的毕生目标就是叫人写美妙的程序。读起来让人心潮彭湃的说。
　　
　　・ The next 700 programming languages Peter J. Landin
　　42年前的论文，影响深远。Peter在论文里描述的函数语言ISWIM（If You See What I Mean）现在没有几个人知道了。但他对lambda算子的推崇和对函数语言的论述影响了后来的函数语言设计。
　　・ Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I) 1960 John McCarthy
　　47年前提出LISP的那篇著名论文。没读过。动态类型检查，Garbage Collection, 递归函数，S-expression, 程序及数据。。。可谓贡献辉煌。
　　
　　
　　・ FORTH - A Language for Interactive Computing Charles H.Moore
　　只知道Forth是一门stack oriented的编程语言，影响了后来的一些语言，比如CAT。其它的就不知道了。
　　
　　・ Teach Yourself Programming in Ten Years 2001 Peter Norvig
　　大牛之所以为大牛，原因之一就是目光深远。这篇文章批评那些《24秒学会C＋＋》之类教材的无稽，讨论了学习编程，从菜鸟变成鲲鹏的方法。中文版已经传得满世界都是，赶快找来看吧。Peter Norvig的网站上还有很多高质量的文章。强烈推荐一读。
　　
　　・ The Definition and Implementation of a Computer Language based on constraints Guy Lewis Steele Jr.
　　好像是Guy Steels的硕士论文。没读过。
　　
　　・ Growing a Language Guy Lewis Steele Jr.
　 　好文！G老大在OOPSLA 98上的主题演讲。G老大主张应该采取渐进的方式设计一门可以被自由扩展的语言（LISP圈子里的牛人们多半都持这种观点吧？）。这篇演讲稿针对该观点做 了精练地论述。说起进化的观点，可以参看另外一篇好文章，SICP作者之一，Jay Sussman的近作。
　　
　　・ Epigrams on Programming Alan J. Perlis
　　A老大发表的一系列关于编程的格言。幽默而深刻。每读必笑。笑后必哭。嗯嗯嗯，夸张一下。不要当真。
　　
　　・ The Complexity of Theorem Proving Procedures Stephen A. Cook
　 　仙风道骨的库克爷爷的成名作。这篇文章一出，好比有人在加州荒漠里发现第一块狗头金，立刻掀起开发加州的狂潮。计算复杂性理论迅速遍地开花。相比这篇论 文开创性的贡献，库克因此得到图灵奖不过小小点缀。NP-Complete在这篇论文里被严格定义。更重要的是，库克证明了第一个NP-Complete 的问题，SAT(Boolean Satisfiability Problem)。有了SAT，再加上折磨了无数学生的Polynomial Reducibility，无数的NPC问题就出现乐。。。别看俺在这里唾沫横飞，当年做有关计算理论的证明题还是相当吃力的，没有少熬夜。奇怪的是，某 一天我给同学讲解我的解法，NPC的相关定义突然变得清晰起来。当初让我绞尽脑汁的证明竟然变得相当机械。后来知道，给人讲解（包括写作）是非常有效地学 习方法。怀着备课的目标读文章，假设自己给别人讲解正在读的文章，有助快速理解所读内容。SAT的证明相当复杂，我反正没有耐心读完。
　　
　　・ Steps Toward Artificial Intelligence Marvin Minsky
　　AI的奠基论文。不过我没读过。
　　
　　・ The Original 'Lambda Papers' Guy Steele and Gerald Sussman
　　一系列讲解lambda算子和scheme设计的经典论文。学scheme时读过，对理解scheme的设计理念很有帮助。
　　
　　
　　・ The UNIX Time-Sharing System Dennis Ritchie and Ken Thompson
　　作者不用介绍了吧？这篇文章里介绍的Unix特性早为人熟知。不过第八部分(VIII Perspective)讨论了作者的设计理念，仍然值得一读。

象棋与我

前几个星期，在师兄的实验室里面，看到他们在下象棋。
因为有问题向他们请教，于是便静静地坐了下来观看。
两位似乎都是新手，我也稍稍有机会锻炼一下自己的大脑，回忆了一下以往的招数。
回来后，突然心血来潮地想下一盘，便下载了个象棋软件，发觉还是一如既往地烂。

不由得回想起，下象棋，还是很小的时候的事情了。
那时大概小学五、六年级吧，也不知怎的，突然在年级里面，就兴起了下象棋。
一群小家伙随身带着一副象棋，饶有兴致地，下课开战，放学开战，许多人甚至中午也不回家了。
还记得当时下得比较好的，都是属于IQ很高的那种――显然我就是属于下得烂的了。
下得好的人总是喜欢在将军时狠狠地用棋子一拍棋盘，大喝一声"将军"，往往还带着个抽马，抽�之类的。
也在那时，第一次接触到什么是将军，抽�，重炮，飞象，死棋等好玩的术语。

那时候，外公也是很喜欢下象棋的。整天去老干局和人对弈，甚至还专门买了部红白机跟电脑下。
还记得不久前在家整理旧书籍，外公送我的那本《象棋入门》是我不舍得扔的几本书之一。
但是我做事一向三分钟热度，为人也浮躁，没有好好钻研过，开局、残局完全都没有自己的分析法。
外公给我的书一直没看过，更别提什么《橘中秘》、《梅花谱》了。
因此，从来没有下赢过外公一盘。可惜，外公不久前了离开我们，至今已经大半年之久了。
再也没有机会听到他那吃我子后，帮我分析时那乐呵呵的大笑了。每每想到这，不禁泪涌眼眶。

后来，不知怎的，象棋，就像它进入我的生活一般，不知怎的，就悄然退去了。
只是偶尔我表弟也会心血来潮跟我来一盘，而大家也半斤八两，不亦悦乎。

高中宿舍里，象棋也流行过一段时间。
刘某人应该是最厉害的人之一。可惜，虽然我与他经常在学习上进行切磋，
也虽然他高三一整年是跟我住一起的，我们却竟然没有在棋局上切磋过一次（不过量我也切磋不过他）。
上大学后，大家同在一个校区四年，不是同一个专业，见面也少了，不知他是否还有下象棋了。
如今，他已在华工，我则背井离乡，不知是否有机会再见。

忽然想起爸爸以前似乎也是个挺厉害的棋手，隐约记得，曾几何时，父子俩好像切磋过那么两盘。
不知什么能再回去，也不知回去后能不能想起，更不知能不能在哪个角落翻出尘封的象棋，两人泡壶好茶，对弈一番。

关于理论计算机的很好几篇介绍

作者是清华大学的研究生，研究方向为理论计算机，曾作为姚期智的助教。
他的blog有几篇关于理论计算机的很好的介绍，看他的自述似乎是要出一个系列的，可惜只看到了几篇。
不过也许只是入门、介绍的话，已经够了。

理论计算机初步：前言
理论计算机初步：P vs NP - 问题概述
理论计算机初步：P vs NP - 历史，现状和未来
理论计算机初步：概率算法和近似算法
理论计算机初步：从hash函数到王小云的MD5破解

另外还有一篇有趣的：

What if P = NP?

[zz]Upstart: Ubuntu 的基于事件的启动进程

转载前言：这篇文章写得太好了，不得不转载。
地址：http://blog.csdn.net/onlyzhangqin/archive/2008/06/02/2502798.aspx
另外一篇不错的文章：并行启动应用程序从而加速 Linux 的引导

By Mark Sobell on February 08, 2008 (9:00:00 AM)
原文链接：http://www.linux.com/feature/125977
翻译时间：2008年3月7日
译者：王旭（gnawux at gmail.com）

译 注：尽管译者是一位铁杆的Debian粉丝，但也注意 upstart 很久了，就译者本人观点，upstart 应该说是 Ubuntu 所做的众多工作中最为杰出的一个，它将可以极大地加快 Linux 系统启动的过程。尽管它不是惟一的下一代 init 程序，但它已经作为 Ubuntu 的缺省 init 进程工作了相当长的时间，这点将极大有助于程序的成熟；而且，upstart 使用了基于事件的模型，而不是简单的将各个 daemon 并行化，这个架构上的突破也是具有革命性的，下面我们来看这篇文章吧。
因为传统的System V 的 init daemon (Sysvinit)无法很好地处理现代硬件，如热插拔设备、USB硬盘或山村、网络文件系统等，Ubuntu 使用了Upstart init daemon。

本文抽取自最近出版的 A Practical Guide to Ubuntu Linux.

目前已经有多种 sysvinit 的替代产品了，这其中最为著名的一个就是 initng， 它已经可以用于 Debian 了，并且在 Ubuntu 上也能工作。在同一位置上，Solaris 使用 SMF (Service Management Facility)，而 Mac OS 则使用 launchd。而 Ubuntu 则更倾向于集这些软件的优点于一身。
Sysvinit daemon 是一个基于运行级别的初始化程序，它使用了运行级别（如单用户、多用户等）并通过从 /etc/rc?.d 目录到 /etc/init.d 目录的初始化脚本的链接来启动与终止系统服务。自从 Feisty 开始，Ubuntu 转向了 Upstart init daemon，并开始将Sysvinit 设置转换为 Upstart 的设置。本文探讨 Upstart 和残存的部分 Sysvinit 遗迹：/etc/rc?.d 和 /etc/init.d 目录以及运行级别的概念。
Upstart init daemon 是基于事件的，当系统中的什么情况发生变化时，它会运行某个特定的程序。这里被运行的程序多半是用来启动或终止服务的脚本。这个配置方式和systemv 在系统进入某个运行级别的时候运行init脚本的链接的概念实际上是非常类似的，只不过 upstart 更加灵活一些。Upstart 不仅能在运行级别改变的时候启动或终止服务，也能在接收到系统发生其他改变的信息的时候启动或终止服务。这些系统的改变被称为"事件"。例如，当 upstart 从 udev 接收到运行时文件系统加载、打印机安装或其他类似的设备添加或删除的信息，并采取相应的行动。Upstart 也可以在系统启动、关闭或某个任务状态改变的时候启动或关闭服务。
Upstart由五个包组成，（Ubuntu 中）它们都会被缺省安装：

• upstart 提供Upstart init daemon 和 initctl 工具。
• upstart-logd 提供 logd daemon 和 logd 服务的工作定义文件。
• upstart-compat-sysv 提供了 rc 任务的工作定义文件，并提供了 reboot, runlevel, shutdown, telinit 等工具，以便与 sysvinit 相兼容。
• startup-tasks 提供了系统启动任务的工作定义文件。
• system-services 提供了 tty 服务的工作定义文件。

定义

有 几个名词帮助我们理解 init 相关的东西。事件（event）是 init 可以得到的状态变更信息。几乎系统所有的内部或外部状态变更都可以触发一个事件。比如，引导程序会触发启动（startup）事件，系统进入运行级别2会 触发运行级别2（runlevel 2）事件，而文件系统加载则会触发路径加载（path-mounted）事件，拔掉或安装一个热插拔或USB设备（如打印机）也会触发一个时间。用户还可 以通过 initctl emit 命令来手动触发一个事件。
一个工作（job）是 init 可以理解的一系列指令。典型的指令包括一个程序（二进制文件或是脚本）和事件的名称。Upstart init daemon 会在事件触发的时候运行相应的程序。用户可以分别用 initctl start 和 stop 命令手动启动或终止一项工作。工作又可以分为任务和服务。
任务是运行、并在执行结束后返回到等待状态的工作。
服务是那些通常不会自己结束的工作。比如，logd daemon 和 gettys 就被实现为服务。init daemon 会监测每个服务的状态，如果服务出现问题会重启服务，在某些事件触发时或手工停止时会杀死服务。
/etc/event.d 目录下包含着一系列的工作定义文件（定义了 upstart init daemon 运行的工作的文件）。最初，这个目录由 Upstart 包来生成。在 Feisty 之后的 Ubuntu 中，被安装的服务会向这个目录中添加控制服务的文件，替代哪些安装到 /etc/rc?.d 和 /etc/init.d 目录的文件。
Upstart init daemon 的核心是一个状态机。它持续跟踪各个工作的状态，当有事件触发的时候，跟踪工作的状态改变。当 init 跟踪到一个工作的状态从一个转变到了另一个的时候，就可能会执行工作的命令或是终止工作。
system V 的 init daemon 通过改变运行级别来启动或停止服务。而使用 Upstart init daemon 的 Ubuntu 系统没有运行级别的概念。为了将基于运行级别的系统平滑移植到基于事件的系统，并为面向其他发布版的软件提供一定的兼容性，Ubuntu 使用 Upstart 模拟了运行级别。
在 /etc/event.d/rc? 文件中定义的 rc? 工作会运行 /etc/init.d/rc 脚本， 这个脚本会运行链接到 /etc/rc?.d 目录中的 /etc/init.d 中的启动脚本，以模拟 SysVinit 的行为。当系统进入一个运行级别的时候，rc? 工作就会运行这些脚本。同时，Upstart 提供了 runlevel 和 telinit 工具以提供与 SysVinit 的兼容性。
使用 initctl (init control) 工具，具有 root 权限的管理员可以和 Upstart init daemon 通信。这个工具可以用来启动、停止或报告(report)一项工作。 比如，initctl list 命令会列出所有的工作和它们的状态：

$ sudo initctl list 
logd (stop) waiting
rc-default (stop) waiting
rc0 (stop) waiting
…
tty5 (start) running, process 4720
tty6 (start) running, process 4727

要 获得更详细的信息，可以参考 initctl 的 man page 或本节的例子。使用 initctl help 命令 （help 前没有横杠）可以列出 initctl 的命令列表。此外，也可以用 initctl list �help 来列出 list 命令的帮助信息，当然，将 list 换乘其它的 initctl 命令会得到该命令对应的信息。start, stop 和 status 工具是 initctl 的链接，会直接运行 initctl 的对应命令。

工作（Job）

/etc/event.d 目录下的每个文件都定义了一个工作，其中至少应该包含一个事件和一个命令。当事件被触发的时候，init 执行对应的命令。本节将介绍管理员自定义的工作和 Upstart 包中包含的工作。

下面的管理员自定义的工作使用 exec 关键字执行了一条 shell 命令。实际上，也可以用这个关键字执行一个 shell 脚本或一个二进制可执行文件。

$ cat /etc/event.d/mudat 
start on runlevel 2
exec echo "Entering multiuser mode on " $(date) > /tmp/mudat.out

这 个文件定义了一个任务：当系统进入到多用户模式（运行级2）的时候执行 echo 命令。这个命令会向 /tmp/mudat.out 文件写出一条包含日期时间消息。shell 会运行 date 命令替换其中的内容。在任务结束后， mudat 任务会停止并进入等待状态。
在下一个的例子中，cat 命令展示了 /tmp/mudat.out 文件的内容和 initctl list 命令关于这个任务的输出（status 工具也可以得到同样的信息）:

$ cat /tmp/mudat.out 
Entering multiuser mode on Tue Jul 10 17:34:39 PDT 2007 
 
$ sudo initctl list mudat
mudat (stop) waiting

如 果 exec 命令行中包含 shell 的特殊字符， init 会运行 /bin/sh（dash 的符号链接）并把命令行交给它来处理。否则，exec 会直接运行命令行。如果要执行多个 shell 命令，可以把他们放到脚本文件中并运行脚本，或是使用 script….end script （下面会介绍）。
Upstart initdaemon  只能监测哪些使用 exec 运行的工作（服务），无法监测使用 script…end script 运行的工作。换句话说，服务应该使用 exec 运行，而任务则可以使用任意的方法。

myjob 示例

用户也可以自己定义一个事件，并让一个工作被这个事件触发。如下的 myjob 工作定义文件定义了一个被 hithere 事件触发的工作：

$ cat /etc/event.d/myjob 
start on hithere
script
	echo "Hi there, here I am!" > /tmp/myjob.out
 	date >> /tmp/myjob.out
	end script

myjob 文件提供了另一种运行命令的方法：在 script 和 end script 关键字之间包含了两行命令。这两个关键字常常导致 init 去运行 /bin/sh。例中的命令将一条消息和日期输出到了 /tmp/myjob.out 文件。现在可以使用 initctl emit 命令触发这个工作。如下，init 展示了 myjobs 在我们的触发下所经历的各个状态：

$ sudo initctl emit hithere
hithere
myjob (start) waiting
myjob (start) starting
myjob (start) pre-start
myjob (start) spawned, process 6064
 myjob (start) post-start, (main) process 6064
myjob (start) running, process 6064
myjob (stop) running
myjob (stop) stopping
myjob (stop) killed
myjob (stop) post-stop
myjob (stop) waiting 

$ cat /tmp/myjob.out 
 Hi there, here I am!
Sat Jul 7 20:19:13 PDT 2007 
 
$ sudo initctl list myjob 
myjob (stop) waiting

在 上面的例子里，cat 展示了 myjob 产生的输出，initctl 展示了工作的状态。同样也可以用 initctl start myjob（或直接用 start myjob）来运行它。initctl start 十个非常有用的命令，这样你就可以在没有事件的情况下启动一个工作。比如，你可以用 initctl start mudat 来直接运行前面例子中的 mudat 工作而不会触发 runlevel 2 事件。

指定带参数的事件

telinit 和 shutdown 工具发送带有参数的 runlevel 事件。比如，shutdown 发送 runlevel 0，telinit 2 会发送 runlevel 2 事件。你可以在工作定义中用如下格式匹配这些事件：
start | stop on event [arg]

其 中 event 是一个事件，而 arg 是一个可选参数。要在系统进入 runlevel 2 的时候停止一个工作，可以指定 stop on runlevle 2，也可以指定 runlevel [235] 来匹配运行级 2, 3 和 5，或用 runlevel [!2] 来匹配 2 之外的运行级。
尽管 Upstart 会忽略掉多余的事件参数，但工作定义文件中的事件名称里的参数必须在事件中存在。比如，没有参数的 runlevel 可以匹配所有的 runlevel 事件，不论是否有参数，但 runlevel S arg2 将不会匹配任何事件，因为 runlevel 事件只会带有一个参数。

/etc/event.d 中的工作定义文件

随着 Ubuntu 从 SysVinit 向 Upstart 的迁移，更多地工作会在 /etc/event.d 文件中定义。本节介绍一些 Upstart 包放在这个目录中的工作定义文件。

/etc/event.d/rc2 工作定义文件定义了 rc2 任务，这和其他的 rc? 任务没什么区别。rc2 任务在系统进入到多用户模式的时候会被触发（事件名称是 runlevel 2）；当系统进入到其它任意运行级的时候（runlevel [!2]）会结束。脚本的第一个部分调用 runlevel 工具，它会让系统显示自己在运行级2 （当然，实际上已经没有运行级这个玩意儿了）并给两个变量赋值。接下来的工作由 exec 命令完成，它会使用参数 2 运行 /etc/init.d/rc 脚本。这个脚本使用相应的参数调用 /etc/rc?.d 目录中的那些链接。这里 rc2 任务会运行 /etc/rc2.d 下的符号链接对应的 init 脚本。

$ cat /etc/event.d/rc2 
# rc2 - runlevel 2 compatibility
#
# This task runs the old sysv-rc runlevel 2 ("multi-user") scripts. It
# is usually started by the telinit compatibility wrapper.
 
start on runlevel 2 

stop on runlevel [!2] 

console output
script
	set $(runlevel �set 2 || true)
	if [ "$1″ != "unknown" ]; then
		PREVLEVEL=$1
 		RUNLEVEL=$2
		export PREVLEVEL RUNLEVEL
 	fi 

	exec /etc/init.d/rc 2
end script

tty 服务

如下是一个在 tty1 上启动并监视 getty 进程的服务的工作定义文件：

$ cat /etc/event.d/tty1 
# tty1 � getty
#
# This service maintains a getty on tty1 from the point when
# the system is started until it is shut down again. 
 
start on runlevel 2
start on runlevel 3
start on runlevel 4
start on runlevel 5 

stop on runlevel 0
stop on runlevel 1
stop on runlevel 6 

respawn
exec /sbin/getty 38400 tty1

这 个服务由 runlevel 2 到 5 （多用户模式）来触发，启动 getty 进程，并在系统关闭、重启或进入单用户模式，即运行级 0，1 和 6 时触发来关闭该服务。respawn关键字告诉 init 在服务终止后重启服务，而 exec 命令是让 getty 进程以 38400 波特率运行在 tty1。如下，initctl 工具显示该服务处于启动状态，进程ID 4747，ps 命令显示该服务的进程：

$ sudo initctl list tty1 
tty1 (start) running, process 4747

$ ps -ef | grep 4747 
root   4747   1 0 Jul02 tty1   00:00:00 /sbin/getty 38400 tty1

rc-default 任务和 inittab

在 SysVinit 中，/etc/inittab 文件通过 initdefault 项告诉 init 在系统启动的时候进入哪个运行级，而 Ubuntu 没有 inittab 文件，缺省的，Upstart init daemon （使用 rc-default 任务）引导系统进入多用户模式（缺省运行级为2）。如果希望系统启动进入其他运行级别，那么就创建一个 inittab 文件。如下会让系统缺省进入单用户模式 （runlevel S）：

$ cat /etc/inittab 
:id:S:initdefault:

当系统进入到单用户（修复）模式，如果系统的root帐号没有被锁定，init 会在显示 root 提示符之前要求输入 root 密码。否则，它会不要求输入密码而直接显示 root 提示符。

注意：不要将系统设置启动到运行级别 0 或 6，这样系统将永远无法正常启动。要直接进入多用户模式（运行级 2），如果有 inittab 删除这个文件，或者用上述的例子，将里面的 S 替换成 2.

Upstart的未来

从 SysVinit 到 Upstart 的迁移涉及到了 Linux 系统的很多部分。要让这个转换尽量平滑并且引入尽量少的问题，Upstart 团队决定通过多个 release 来完成这个迁移。

Ubuntu 从 Feisty 开始使用 Upstart init daemon。在 Feisty 和 Gutsy+2 之间，Ubuntu 将完成 SysVinit 到更加干净、更加灵活的 Upstart 的迁移。随着越来越多的服务被放到 Upstart 的控制之下，/etc/event.d 目录下的内容将会替代 /etc/init.d 和 /etc/rc?.d 目录下的内容。运行级将不再作为 Ubuntu 正式支持的特征，虽然它们可能为了保持与第三方软件的兼容性而继续保留。最终 Upstart 将会替换掉 crond。

中秋到了，随便写点什么吧

0.专业习惯……记事总喜欢写完1后，之前再补个0.
虽然自己的blog由于太过"技术性"，本人交友不广，本人不够帅等客观因素影响，
才发现还是有读者的，比如埋怨"555留言了不给我回复"的sherlly姐姐
以及最近跟我拿了地址的gcc和fr同学。另外似乎还有通过阅读器订阅我的串烧的大兵同学。
如果见到的话，祝你们中秋快乐～
另外，估计也有一点点童鞋是无意中会逛到我的blog的，这里也祝你们快乐～

1.今天坐车回了家，整个过程有点�。首先，早上约了8：45见面一起走的，但某人竟然睡过头，老夫等了20分钟。
然后一起去地铁刚到时，刚好有部车来，某同学急着要上于是我就顺从她意思冲上去，结果发觉她自己没上……
更糟的是，俺的手机没钱了……好在旁边有位大姐慷慨地借给我打……
然后到了罗湖，几经周折才碰面，二人也免不了牢骚一番，结果后来都没心情说话了。
这里要感谢wuya帮我们买票，kissssssssssssss
回家途中，旁边做了几家的hk people，4－5个小时内小朋友们精力超级旺盛，吵得老子睡都睡不着……
anyway，4：45顺利到家，狠狠地灌了3碗汤后，心情马上好了起来 :)


2.到中大1个多月了，总算安定下来。
宿舍基本上习惯了，导师也定了，现在要开始修身养性努力做research了！

3.最后restate一下自己渴望的blog拥有的功能:
1) 国内读者访问顺畅（这基本上决定了blog必须是国内的）
2）完整、标准的rss全文输出
3）email提示新回复
4）email发文(现在非常依赖email，became a heavy email user)

以上几点，暂时只有blogspot能做到（ 除了该死的1) )
不过我还是很喜欢blogspot的，大家有目共睹这个blog提供商做了这么久还在不断努力提供更新的功能。


4.这里再给某些同学阐明一下：
1) my blog address is always iveney.blogspot.com, however, because its limited access quality for mainland users,
I have to post my articles to some other place SIMULTANEOUSLY(now, I use windows live)
2) there is one thing called "rss"/"feed" in your blog, you may use some kind of "reader" to read articles, which means that
if you want to read many other's blog, you don't bothered to open bunch of windows but just finish the task in the reader window.
that thing is my daily tool.
3) if you reply me in windows live space, I am sorry that I will not reply you soon because I seldom go there.
but it you reply me in iveney.blogspot.com, I will really  appreciate it and reply you ASAP(coz' I will get email notification)
4) sometimes if I am free, I will just copy the article to my blog in Xiaonei.com

衬线字(serif)，无衬线字(sans-serif)，等宽字(monospaced)；字形(glyphs)，字样(typeface)，字体(font)；

这些概念非常confusing，是时候梳理一下了。
首先，给出一些资料，这里做的总结基本上来自这些资料。
[1] LaTeX Notes v1.20, Alpha Huang,http://www.dralpha.com/
[2] wikipedia.org 上 关于以上名词的解释
[3] [教程] 谈谈网页设计中的字体应用 (2) serif 和 sans-serif, http://www.cnblogs.com/ruxpinsp1/archive/2008/05/06/font-in-front-end-development-2.html
[4] Serif和Sans Serif的区别, http://www.bloghome.cn/posts/34304.html

衬线字：即字的开始，边缘有装饰的字体，如Times New Roman, 中文的有宋体。适合用于阅读文章，因为棱角分明，比较不易导致1，|与l，O与0等的混淆。
"因为衬线字体的可读性非常好，所以它应用的最多的地方也正是出版物或者印刷品的正文内容等以大段文字作为表现形式的作品上。"

无衬线字：即的开始，边缘无装饰的字体，如Tahoma，Arial，中文的有黑体(中文的黑体其实是衬线字体。见[3])。适合用于显示小字体。因为比较规范。
"无衬线字体比较圆滑，线条一般粗细均匀。比较适合用作艺术字、标题等。因为无衬线字体通常粗细比较均匀，所以在小字体显示的时候，可读性会降低，容易引起视觉疲劳。"

等宽字：即每个字的宽度相等的字体。如Monospace（注意区别monospaced与monospace）,Consolas,Courier等。这种字体由于其宽度相等，很容易对齐、规范代码，因此适合用于代码阅读。
"因为字符宽度一致，所以特别容易对齐，能快速精确的定位到某行某列，因此经常用来显示代码。"
要注意的是，一个等宽字体同时也可以是一个衬线（或者非衬线）字体。比如 Courier New 这个字体也可以看作是一个serif（严格的说是gothic）字体。

另外，以上说的几类都统称为"通用字体族"，即font-family。其实不止以上几种字体族，类似的还有：
scripts 手写体（比如花体）
blackletter 铅字体（也叫 gothic 哥特体）
cursive 书写体：相当于印刷学中的手写体。中文的华文行草就是这样的一个字体。
fantasy 梦幻体：相当于印刷学中的装饰体。非常少见的一种字体，基本没有参考价值。

印刷式样：粗体(bold)、斜体(italic)（错！）、倾斜(oblique)。
我们经常以为，bold就是对原来的字体进行加粗，而斜体就是把它写斜。
斜体其实是一种书写方式，往往是另外的一种字体。
而oblique才是把它写斜。


字形：即字的表现形式。也理解为"同一个字的不同写法"，如"回"的六种写法……简体、繁体的强、�。
字样：即一组具有相同风格的字形的集合，如中文字体有宋、仿、楷、黑、隶、篆等。其实就是上面提到的font-family
字体：字样的具体实现。如对于宋体可能有不同公司的实现（方正、文泉驿、微软等）