Some notes on lock-free and wait-free algorithms

http://www.audiomulch.com/~rossb/code/lockfree/

NOBLE - a library of non-blocking synchronization protocols

http://www.cs.chalmers.se/~noble/

An optimistic approach to lock-free FIFO queues (Distributed Computing 2008)

http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

High performance dynamic lock-free hash tables and list-based sets

http://portal.acm.org/citation.cfm?id=564870.564881

Concurrent Programming Without Locks

http://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf

Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

http://www.research.ibm.com/people/m/michael/podc-1996.pdf

1. On the criteria to be used in decomposing systems into modules – David Parnas
2. A Note On Distributed Computing – Jim Waldo, Geoff Wyant, Ann Wollrath, Sam Kendall
3. The Next 700 Programming Languages – P. J. Landin
4. Can Programming Be Liberated from the von Neumann Style? – John Backus
5. Reflections on Trusting Trust – Ken Thompson
6. Lisp: Good News, Bad News, How to Win Big – Richard Gabriel
7. An experimental evaluation of the assumption of independence in multiversion programming – John Knight and Nancy Leveson
8. Arguments and Results – James Noble
9. A Laboratory For Teaching Object-Oriented Thinking – Kent Beck, Ward Cunningham
10. Programming as an Experience: the inspiration for Self – David Ungar, Randall B. Smith

今年的ASPLOS '09上zhou yuanyuan也有一篇关于如何concurrent program中发现隐藏的atomicity violation bugs的paper，里面提到了这篇paper

2008-11-30

OSDI '08上MSR发的paper，针对并发编程中难以发现的bug问题。

paper的内容主要分两大块。

一是如何在发现bug的时候记录下线程的运行先后(thread interleaving)，途径是在线程API和用户程序多写一层wrapper functions，这里还有一些其他的问题，比如只记录下了thread interleaving的话出现data race怎么解决等。

另外一块内容是如何遍历出给定程序运行后所能产生的结果的集合，加入这个能实现的话那就能把所有隐藏的bug都找出来了。但是这个搜索空间很大，是 指数级的，的一个结论就是：给定一个程序有n个的线程，所有线程共完成k条指令，那么c次占先调度后线程的排列情况数的复杂度是的，所以在实现遍历代码的时候必须有效的降低k和c的值。

Bruce Eckel的一篇日志建议把self从方法的参数列表中移除，并把它作为一个关键字使用。
http://www.artima.com/weblogs/viewpost.jsp?thread=239003

Guido的这篇日志说明了self作为参数是必不可少的。
http://neopythonic.blogspot.com/2008/10/why-explicit-self-has-to-stay.html

第一个原因是保证foo.meth(arg)和C.meth(foo, arg)这两种方法调用的等价（foo是C的一个实例)，关于后者可以参见Python Reference Manual 3.4.2.3。这个原因理论上的意义比较大。

第二个原因在于通过self参数我们可以动态修改一个类的行为：

这样类C就新增了一个meth方法，并且所有C的实例都可以通过c.meth(newval)调用这个方法。

前面两个原因或许都可以通过一些workaround使得不使用self参数时实现同样的效果，但是在存在decorator的代码中Bruce的方法存在致命的缺陷。(关于decorator的介绍可以参见http://www.python.org/dev/peps/pep-0318/)

根据修饰对象，decorator分两种，类方法和静态方法。两者在语法上没有什么区别，但前者需要self参数，后者不需要。而Python在实 现上也没有对这两种方法加以区分。Bruce日志评论中有一些试图解决decorator问题的方法，但这些方法都需要修改大量底层的实现。

最后提到了另一种语法糖实现，新增一个名为classmethod的decorator，为每个方法加上一个self参数，当然这种实现也没必要把self作为关键字使用了。不过我觉得这么做还不如每次写类方法时手工加个self =_=

2008年评出了1998年最具影响力的PLDI论文，获奖论文的作者将分摊1000美元的奖金（还没一等奖学金多 -_-b）

2008 (for 1998): The Implementation of the Cilk-5 Multithreaded Language, Matteo Frigo, Charles E. Leiserson, and Keith H. Randall

Citation

“The 1998 PLDI paper “Implementation of the Cilk-5 Multithreaded Language” by Matteo Frigo, Charles E. Leiserson, and Keith H. Randall introduced an efficient form of thread-local deques to control scheduling of multithreaded programs. This innovation not only opened the way to faster and simpler runtimes for fine-grained parallelism, but also provided a basis for simpler parallel recursive programming techniques that elegantly extend those of sequential programming. The stack-like side of a deque acts just like a standard procedure stack, while the queue side enables breadth-first work-stealing by other threads. The work-stealing techniques introduced in this paper are beginning to influence common practice, such as the Intel Threading Building Blocks project, an upcoming standardized fork-join framework for Java, and a variety of projects at Microsoft.”

另外前几年的获奖paper有：
2007 (for 1997): Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling, Glenn Ammons, Thomas Ball, and James R. Larus

2006 (for 1996): TIL: A Type-Directed Optimizing Compiler for ML, David Tarditi, Greg Morrisett, Perry Cheng, Christopher Stone, Robert Harper, and Peter Lee

2005 (for 1995): Selective Specialization for Object-Oriented Languages, Jeffrey Dean, Craig Chambers, and David Grove

2004 (for 1994): ATOM: a system for building customized program analysis tools, Amitabh Srivastava and Alan Eustace

2003 (for 1993): Space Efficient Conservative Garbage Collection, Hans Boehm

2002 (for 1992): Lazy Code Motion, Jens Knoop, Oliver Rüthing, Bernhard Steffen.

2001 (for 1991): A data locality optimizing algorithm, Michael E. Wolf and Monica S. Lam.

2000 (for 1990): Profile guided code positioning, Karl Pettis and Robert C. Hansen.

运行a()会报UnboundLocalError: local variable ‘x’ referenced before assignment
但是运行c()会正确地显示3和4。

原因在于原因在于CPython实现closure的方式和常见的functional language不同，采用了flat closures实现。

“If a name is bound anywhere within a code block, all uses of the name within the block are treated as references to the current block.”

在第一个例子中，b函数x += 1对x进行赋值，rebind了这个对象，于是Python查找x的时候只会在local environment中搜索，于是就有了UnboundLocalError。

换句话说，如果没有修改这个值，比如b中仅仅简单的输出了x，程序是可以正常运行的，因为此时搜索的范围是nearest enclosing function region。

而d方法并没有rebind x变量，只是修改了x指向的对象的值而已。如果把赋值语句改成x = [4]，那么结果就和原来不一样了，因为此时发生了x的rebind。

所以Python中的closure可以理解为是只读的。

另外第二个例子也是这篇文章中提到的一种workaround：把要通过inner function修改的变量包装到数组里，然后在inner function中访问这个数组。

至于为什么Python中enclosed function不能修改enclosing function的binding，文中提到了主要原因还是在于Guido反对这么做。因为这样会导致本应该作为类的实例保存的对象被声明了本地变量。

参考网站：http://www.python.org/dev/peps/pep-0227/

-module(sequence1).
-export([make_sequence/0, get_next/1, reset/1]).
 
% Create a new shared counter.
make_sequence() ->
spawn(fun() -> sequence_loop(0)end).
 
sequence_loop(N) ->
receive
{From, get_next} ->
From!{self(), N},
            sequence_loop(N + 1)<SEMI>
        reset ->
sequence_loop(0)
end.
 
% Retrieve counter and increment.
get_next(Sequence) ->
Sequence!{self(), get_next},
receive
{Sequence, N} -> N
end.
 
% Re-initialize counter to zero.
reset(Sequence) ->
Sequence! reset.

初看这个程序自然是一头雾水，不过程序的函数式风格味还是很浓的。

前面提到，Erlang是基于message的，或者说message sending机制是包含在语言系统内部的，语法就是 pid ! message

接下来再来分析这个简单的程序。开头两行是模块和函数声明，略去。make_sequence开始这个进程，spawn/1内置函数创建一个新的进程，并返回pid到调用者。

初始时运行的函数是sequence_loop(0)，这个函数接收两种信息，用receive表达式声明：如果收到形式是{From, get_next}的信息，就返回当前的N并调用sequence_loop(N+1)，这样下一次收到同样的信息时就能返回N+1了；reset则等价 于Java版本中的n=0语句。

get_next/1则是发送给pid为Sequence的进程 {self(), get_next} 这样一个信息，上面解释的sequence_loop/1函数收到这个信息后会返回一个 {self(), N} 的tuple给get_next/1，收到这个信息后get_next/1就能返回N这个值了。

最后reset/1函数则是发送给Sequence一个reset信息。

这个简单的程序里能大致窥见一些Erlang的特点，尤其是它基于信息发送的本质。

依然是内网日志的汇总

1. sysenter的介绍
http://www.codeguru.com/cpp/w-p/system/devicedriverdevelopment/article.php/c8223

System Call Optimization with the SYSENTER Instruction
by John Gulbrandsen
Windows下的

2. The SLUB allocator
slab的改进版本

http://lwn.net/Articles/229984/

http://lwn.net/Articles/229096/

Christoph’s response is the SLUB allocator, a drop-in replacement for the slab code. SLUB promises better performance and scalability by dropping most of the queues and related overhead and simplifying the slab structure in general, while retaining the current slab allocator interface.

Wider use may be in the cards: the SLUB allocator is in the -mm tree now and could hit the mainline as soon as 2.6.22. The simplified code is attractive, as is the claimed 5-10% performance increase. If merged, SLUB is likely to coexist with the current slab allocator (and the SLOB allocator intended for small systems) for some time. In the longer term, the current slab code may be approaching the end of its life.

3. Compilers and More: Parallel Programming Made Easy?
http://www.hpcwire.com/features/Compilers_and_More_Parallel_Programming_Made_Easy.html

by Michael Wolfe, Compiler Engineer, The Portland Group, Inc.

4. OpenCL slides, SIGGRAPH '08
发信人: jjgod (while(!asleep()) sheep++;), 信区: CSArch
标  题: SIGGRAPH 08 上的 OpenCL slides
发信站: 水木社区 (Mon Sep 15 01:32:03 2008), 站内

※ 来源:·水木社区 newsmth.net·[FROM: 125.33.176.*]

附件: munshi-opencl.pdf (1338 KB) 链接:
http://att.newsmth.net/att.php?p.272.35430.226.pdf
全文链接：http://www.newsmth.net/bbscon.php?bid=272&id=35430

5. linux-gate.so
http://www.trilithium.com/johan/2005/08/linux-gate/
linux下使用sysenter的机制

Linux 2.4.18的linux/linkage.h文件定义了若干相关的宏

#define SYMBOL_NAME(X) X
#ifdef __STDC__
#define SYMBOL_NAME_LABEL(X) X##:
#else
#define SYMBOL_NAME_LABEL(X) X/**/:
#endif
 
#define __ALIGN .align 16,0x90
#define __ALIGN_STR ".align 16,0x90"
 
#define ALIGN __ALIGN
#define ALIGN_STR __ALIGN_STR
 
#define ENTRY(name) \
  .globl SYMBOL_NAME(name); \
  ALIGN; \
  SYMBOL_NAME_LABEL(name)

用ENTRY(name)就能定义函数了。后来发现Flux OSKit中本来就提供了类似功能的宏，定义在inc/asm.h中。
使用的时候需要再写一个c语言的wrapper function（至少2.4.18里面是这么做的）
asmlinkage void ret_from_fork(void) __asm__("ret_from_fork");

Time : 2008-08-22 15:56
OS Lab 4 debugging notes [1]
系统调用 fork()

用Simics跟踪一条条汇编分析页表映射、寄存器值还真是体力活啊。。

1. 实现Copy On Write时，如果某一个用户态页面有多个进程共享，其中一个进程修改该页面时需要创建一个新的页面。一开始偶忘了把原来页面的内容复制到新的页面了 =_= 另外由于新的页面要代替老的页面，或者说它们的物理地址不同，但虚拟地址相同，我的方法是在内核态开辟一个大小为一个页面的空间作为中转。

2. do_fork函数中，子进程复制父进程的页表的同时会把父进程页表项置为不可写，注意最后要flush tlb。因为一开始没有flush tlb，导致最后用户态fork返回以后读取的信息来自于tlb，直接改写了共享页面中fork的返回地址，导致切换到子进程时fork的返回地址丢失。这个bug让我郁闷了两三个小时。。

3. 使用两次fork时，第二次fork返回的pid会被改掉。查了下发现为用户空间分配物理页面的代码里居然在分配好以后没有把对应的struct置为已使用，结果导致第二个子进程COW创建新页面时得到了原来的父进程页面，改写了父进程页面内容。

Time : 2008-08-23 19:41
OS Lab4 debugging notes [2] 
系统调用 exec()

1. 清空页表的用户空间映射的函数一开始写得yts，bug到处都是，比如free的时候没使用指向内存块首地址的指针，记录内存地址的变量没有累加。

2. exec传递给内核态的两个参数必须先在内核态保存一个副本，否则清空用户态页表后就无法得到这两个参数信息了。

3. 分配给用户态的页面必须先清零，一方面考虑到安全性，另一方面不清零会隐藏一些潜在的bug。一开始我没有在内核执行exec的时候完整的复制所有的参数，而是直接指向了原进程的内存空间，由于清空页表后再次申请新页表时得到了原来的页面，结果正好原来那个保存参数的页面和新进程的该页面重合了 =_= 于是浪费了不少时间在这个bug上

Time : 2008-08-31 1:18
OS Lab5 debugging notes
还算顺利，不过这个lab蛮无聊的，等有空了把syscall改成类似linux的做法，单一中断号+寄存器选择syscall。

1. 最花时间的一个bug是ls返回值没有改成应用程序数，结果一开始一直以为是brk系统调用没写好，最后才发现问题出在这么小的地方。

2. brk的逻辑还不是很清楚，尽管通过了简单的测试，但是debug输出的信息显示brk增长的很快，经常是一个页一个页涨的，看来还得查下brk的具体行为。

3. 写了个比MAGIC_BREAK好用一点的宏，因为用户态的程序都是按二进制读入的，Simics无法得到函数信息（函数名、当前行数等），利用C99的宏写了个新的INFO_BREAK

#define INFO_BREAK \
    do {  \
        lprintf_kern("break in %s:%d", __FUNCTION__, __LINE__); \
        MAGIC_BREAK; \
    } while (0) \

没心思看离散，也不准备坚持看没有荷兰的欧洲杯决赛。闲着点好友的Q-Zone，原来Q-Zone首先会判断你的浏览器，如果是Firefox它会重定向到RSS阅读界面。

安然在开学后2个月写的一篇日志，“记忆里的名单”，惊喜的看到有我。也列出了一张属于我的名单。好，等待时间的遴选。

“于是想 如果有个妹妹 我要告诉她 好好放肆猖狂 做不可思议的事情 为友情和少年青涩的爱情花心思 做只是喜欢没有功利目的的事情 这么好的年华 就是用来这样浪费 和珍惜的~”

可惜我只保持了四五个月的这种疯狂，现在依然纠结于功利的选择。有时候曾想，或许那次失败更适合我，或许我终将把这么一条平淡无奇的路走到尽头。“表面强者”，或许还是很有道理的。

看到fofo的博的文字，“我要去杭州，把所有的事情抛掉，不管后果。这个地方太让人压抑，尽管有很玩得来的室友，有很好的足球队的队友，可以看很多以前爸妈不让看的喜欢的书还有过米的比赛，吃的东西也都很习惯，还是会在天气很好的星期天下午突然想起曾经在冬日的阳光照射下一家人在阳台上围着一张桌子吃饭的情景，还是会在一个人骑在去计算机协会的路上很难过地想着再也不会有那么四个或者五个人在一起吃完小炒放肆地在铺满夕阳的校园小路上勾肩搭背地行走了，还是会在一百多个人的课堂上怀念起那些艰苦却简单的日子里所有的笑声，还是会在网吧包夜的时候想起初中时捏着饭钱偷偷摸摸地去电脑房玩星际……想找找朋友们，调整一下自己的心情。”

真的找不回来了。在写这篇博文时也找不到以前写字的感觉了。

明天离散考试，某个记录或许将要因此打破。

不枉我周末练了那么多ZvP

不过总比分太惨了。。

#define sLog MaNGOS::Singleton<Log>::Instance()
#define sMaster MaNGOS::Singleton<Master>::Instance()

namespace MaNGOS
{
    template
        <
        typename T,
        class ThreadingModel = MaNGOS::SingleThreaded<T>,
        class CreatePolicy = MaNGOS::OperatorNew<T>,
        class LifeTimePolicy = MaNGOS::ObjectLifeTime<T>
        >
        class MANGOS_DLL_DECL Singleton
    {
        public:
            static T& Instance();

        protected:
            Singleton() {};

        private:

            // Prohibited actionsthis does not prevent hijacking.
            Singleton(const Singleton &);
            Singleton& operator=(const Singleton &);

            // Singleton Helpers
            static void DestroySingleton();

            // data structure
            typedef typename ThreadingModel::Lock Guard;
            static T *si_instance;
            static bool si_destroyed;
    };
}
#endif

不知道这里的注释Prohibited actions...this does not prevent hijacking.是什么意思，copy constructor和hijacking有什么关系呢？

另外注意这行typedef typename ThreadingModel::Lock Guard;，原来typedef还可以用在函数上。

Singleton的Instance方法用的是标准的double-checked lock方法，关于DCL可以参考这篇博文http://www.blogjava.net/zellux/archive/2008/04/07/191365.html

2. Explicit Constructors
game/WorkPacket.h中看到的语法，防止构造函数中参数的隐式转型
比如explicit String(int n); 用String('c')声明时就会报错

水木上有人贴了个有趣的程序

#include  < stdlib.h >
#include  < stdio.h >

void  print_forever( int  n)
{
    printf( " %d\n " , n);
    print_forever(n  +   1 );
}

int  main( int  argc,  char   * argv[])
{
    print_forever( 0 );
     return   0 ;
}

.L6:
        movl    %ebx, 4(%esp)
        addl    $1, %ebx
        movl    $.LC0, (%esp)
        call    printf
        jmp     .L6

<   -falign-loops                               [enabled]
>   -falign-jumps                               [enabled]
>   -falign-labels                              [enabled]
>   -fcaller-saves                              [enabled]
>   -fcrossjumping                              [enabled]
>   -fcse-follow-jumps                          [enabled]
>   -fdelete-null-pointer-checks                [enabled]
>   -fexpensive-optimizations                   [enabled]
>   -fforward-propagate                         [enabled]
>   -fgcse                                      [enabled]
>   -finline-small-functions                    [enabled]
>   -foptimize-register-move                    [enabled]
>   -foptimize-sibling-calls                    [enabled]
>   -fpeephole2                                 [enabled]
>   -fregmove                                   [enabled]
>   -freorder-blocks                            [enabled]
>   -freorder-functions                         [enabled]
>   -fschedule-insns2                           [enabled]
>   -fstrict-aliasing                           [enabled]
>   -fthread-jumps                              [enabled]
>   -ftree-pre                                  [enabled]
>   -ftree-store-ccp                            [enabled]
>   -ftree-vrp                                  [enabled]

Problem

Every bus in the Ekaterinburg city has a special man (or woman) called conductor. When you ride the bus, you have to give money to the conductor. We know that there are more then P% conductors and less then Q% conductors. Your task is to determine a minimal possible number of Ekaterinburg citizens.

 1 #include <iostream>
 2 #include <cmath>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     double dp, dq;
 9     cin >> dp >> dq;
10     int p = floor(dp * 100 + 0.5);
11     int q = floor(dq * 100 + 0.5);
12     for (int i = 1; ; i++) {
13         int a = p * i / 10000;
14         int b = q * i / 10000;
15         if ((a < b) && (q * i % 10000 > 0)) {
16             cout << i << endl;
17             return 0;
18         }
19     }
20     return 0;
21 }
22 

下午打球直到体力极限，一路淋雨跑回寝室，洗澡，感冒，低落。想回家。

有时候会想，几年后，真的就要在上海这个地方工作立足吗？

我想看一堆电影 想读一堆书 想学C# Lisp Python 想上ACM OJ网站切题 想参加一次TopCoder比赛 想学埙 想学钢琴 想睡觉 想看微经 想练英语 想看内核 想到处旅游

终会和现实冲突。于是我想退实验室。几个小时后又放弃这个决定。

终究是怕这怕那保守着缓慢前进的人。

计算机科学论坛最近举办了一个阅读样章，提交书评的活动，具体内容请见http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162。

这里我想针对样章上的一个问题谈谈自己的理解。

问题很简单，求二进制中1的个数。对于一个字节（8bit）的变量，求其二进制表示中"1"的个数，要求算法的执行效率尽可能的高。

先来看看样章上给出的几个算法：

解法一，每次除二，看是否为奇数，是的话就累计加一，最后这个结果就是二进制表示中1的个数。

解法二，同样用到一个循环，只是里面的操作用位移操作简化了。

   1:  int Count(int v)  
   2:  {  
   3:      int num = 0;
   4:      while (v) {  
   5:          num += v & 0x01;  
   6:          v >>= 1;  
   7:      }  
   8:      return num;  
   9:  }

解法三，用到一个巧妙的与操作，v & (v -1 )每次能消去二进制表示中最后一位1，利用这个技巧可以减少一定的循环次数。

解法四，查表法，因为只有数据8bit，直接建一张表，包含各个数中1的个数，然后查表就行。复杂度O(1)。

   1:  int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };  
   2:     
   3:  int Count(int v) {  
   4:      return countTable[v];  
   5:  }
  
好了，这就是样章上给出的四种方案，下面谈谈我的看法。

首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。

查表法的复杂度为O(1)，我用解法一，循环八次固定，复杂度也是O(1)。至于数据规模变大，变成32位整型，那查表法自然也不合适了。

其次，我觉得既然是这样一个很小的操作，衡量的尺度也必然要小，CPU时钟周期可以作为一个参考。

解法一里有若干次整数加法，若干次整数除法（一般的编译器都能把它优化成位移），还有几个循环分支判断，几个奇偶性判断（这个比较耗时间，根据CSAPP上的数据，一般一个branch penalty得耗掉14个左右的cycle），加起来大概几十个cycle吧。

再看解法四，查表法看似一次地址计算就能解决，但实际上这里用到一个访存操作，而且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle（因为要访问内存）。所以对于这种“小操作”，这个算法的性能其实是很差的。

这里我再推荐几个解决这个问题的算法，以32位无符号整型为例。

   1:  int Count(unsigned x) {  
   2:     x = x - ((x >> 1) & 0x55555555);   
   3:     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);   
   4:     x = (x + (x >> 4)) & 0x0F0F0F0F;   
   5:     x = x + (x >> 8);   
   6:     x = x + (x >> 16);   
   7:     return x & 0x0000003F;   
   8:  }
  
这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。

还有一个更巧妙的HAKMEM算法

   1:  int Count(unsigned x) {
   2:     unsigned n;   
   3:     
   4:     n = (x >> 1) & 033333333333;   
   5:     x = x - n;  
   6:     n = (n >> 1) & 033333333333;  
   7:     x = x - n;   
   8:     x = (x + (x >> 3)) & 030707070707;  
   9:     x = modu(x, 63); 
   10:     return x;  
   11:  }
  
首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。

因为2^6 = 64，也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，这里的等号表示同余。

这个程序只需要十条左右指令，而且不访存，速度很快。

由此可见，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。

关于后面的两道扩展问题，问题一是问32位整型如何处理，这个上面已经讲了。

问题二是给定两个整数A和B，问A和B有多少位是不同的。

这个问题其实就是数1问题多了一个步骤，只要先算出A和B的异或结果，然后求这个值中1的个数就行了。

总体看来这本书还是很不错的，比较喜欢里面针对一个问题提出不同算法并不断改进的风格。这里提出一点个人的理解，望大家指正 ;-)

(by ZelluX   http://www.blogjava.net/zellux)

转载请注明 作者 ZelluX    http://www.blogjava.net/zellux

看OOP教材时，提到了一个双检测锁定(Double-Checked Lock, DCL)的问题，但是书上没有多介绍，只是说这是一个和底层内存机制有关的漏洞。查阅了下相关资料，对这个问题大致有了点了解。

从头开始说吧。

在多线程的情况下Singleton模式会遇到不少问题，一个简单的例子

   1:  class Singleton {     
   2:      private static Singleton instance = null;     
   3:        
   4:      public static Singleton instance() {     
   5:          if (instance == null) {     
   6:              instance = new Singleton();     
   7:          }     
   8:          return instance;    
   9:      }    
   10:  }
  
假设这样一个场景，有两个线程调用Singleton.instance()，首先线程一判断instance是否等于null，判断完后一瞬间虚拟机把线程二调度为运行线程，线程二再次判断instance是否为null，然后创建一个Singleton实例，线程二的时间片用完后，线程一被唤醒，接下来它执行的代码依然是instance = new Singleton();
两次调用返回了不同的对象，出现问题了。

最简单的方法自然是在类被载入时就初始化这个对象：private static Singleton instance = new Singleton();

JLS(Java Language Specification)中规定了一个类只会被初始化一次，所以这样做肯定是没问题的。

但是如果要实现延迟初始化(Lazy initialization)，比如这个实例初始化时的参数要在运行期才能确定，应该怎么做呢？

依然有最简单的方法：使用synchronized关键字修饰初始化方法：

    public synchronized static Singleton instance() {       
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
   
这里有一个性能问题：多个线程同时访问这个方法时，会因为同步而导致每次只有一个线程运行，影响程序性能。而事实上初始化完毕后只需要简单的返回instance的引用就行了。

DCL是一个“看似”有效的解决方法，先把对应代码放上来吧：

    1 :   class Singleton {  
    2 :       private static Singleton instance = null ;  
    3 :     
    4 :       public static Singleton instance() {  
    5 :           if (instance == null ) {
    6 :               synchronized (this) {  
    7 :                   if (instance == null)
    8 :                      instance = new Singleton();
    9 :              }
    10 :          }
    11 :          return instance;
    12 :      }
    13 :  }

用JavaWorld上对应文章的标题来评论这种做法就是smart, but broken。来看原因：

Java编译器为了提高程序性能会进行指令调度，CPU在执行指令时同样出于性能会乱序执行（至少现在用的大多数通用处理器都是out-of-order的），另外cache的存在也会改变数据回写内存时的顺序[2]。JMM(Java Memory Model, 见[1])指出所有的这些优化都是允许的，只要运行结果和严格按顺序执行所得的结果一样即可。

Java假设每个线程都跑在自己的处理器上，享有自己的内存，和共享的主存交互。注意即使在单核上这种模型也是有意义的，考虑到cache和寄存器会保存部分临时变量。理论上每个线程修改自己的内存后，必须立即更新对应的主存内容。但是Java设计师们认为这种约束会影响程序性能，他们试着创造了一套让程序跑得更快、但又保证线程之间的交互与预期一致的内存模型。

synchronized关键字便是其中一把利器。事实上，synchronized块的实现和Linux中的信号量(semaphore)还是有区别的，前者过程中锁的获得和释放都会都会引发一次Memory Barrier来强制线程本地内存和主存之间的同步。通过这个机制，Java中的同步机制保证了synchronized块中指令的原子性(atomic)。

好了，回过头来看DCL问题。看起来访问一个未同步的instance字段不会产生什么问题，我们再次来假设一个场景：

线程一进入同步块，执行instance = new Singleton(); 线程二刚开始执行getResource();

按照顺序的话，接下来应该执行的步骤是 1) 分配新的Singleton对象的内存 2) 调用Singleton的构造器，初始化成员字段 3) instance被赋为指向新的对象的引用。

前面说过，编译器或处理器都为了提高性能都有可能进行指令的乱序执行，线程一的真正执行步骤可能是1) 分配内存 2) instance指向新对象 3) 初始化新实例。如果线程二在2完成后3执行前被唤醒，它看到了一个不为null的instance，跳出方法体走了，带着一个还没初始化的Singleton对象。

错误发生的一种情形就是这样，关于更详细的编译器指令调度导致的问题，可以参看这个网页 [4]。

[3] 中提供了一个编译器指令调度的证据

instance = new Singleton(); 这条命令在Symantec JIT中被编译成

0206106A   mov         eax,0F97E78h
0206106F   call        01F6B210                  ; 分配空间
02061074   mov         dword ptr [ebp],eax       ; EBP中保存了instance的地址

02061077   mov         ecx,dword ptr [eax]       ; 解引用，获得新的指针地址

02061079   mov         dword ptr [ecx],100h      ; 接下来四行是inline后的构造器
0206107F   mov         dword ptr [ecx+4],200h   
02061086   mov         dword ptr [ecx+8],400h
0206108D   mov         dword ptr [ecx+0Ch],0F84030h

可以看到，赋值完成在初始化之前，而这是JLS允许的。
 
另一种情形是，假设线程一安稳地完成Singleton对象的初始化，退出了同步块，并同步了和本地内存和主存。线程二来了，看到一个非空的引用，拿走。注意线程二没有执行一个Read Barrier，因为它根本就没进后面的同步块。所以很有可能此时它看到的数据是陈旧的。

还有很多人根据已知的几种提出了一个又一个fix的方法，但最终还是出现了更多的问题。可以参阅[3]中的介绍。

[5]中还说明了即使把instance字段声明为volatile还是无法避免错误的原因。

由此可见，安全的Singleton的构造一般只有两种方法，一是在类载入时就创建该实例，二是使用性能较差的synchronized方法。

(by ZelluX  http://www.blogjava.net/zellux )

参考资料：

[1] Java Language Specification, Second Edition, 第17章介绍了Java中线程和内存交互关系的具体细节。
[2] out-of-order与cache的介绍可以参阅Computer System, A Programmer's Perspective的第四、五章。
[3] The "Double-Checked Locking is Broken" Declaration, http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[4] Synchronization and the Java Memory Model, http://gee.cs.oswego.edu/dl/cpj/jmm.html
[5] Double-checked locking: Clever, but broken, http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html?page=1
[6] Holub on Patterns, Learning Design Patterns by Looking at Code

翘课大半，作业一半不交一半抄，总之太不像学生了。
搞得现在Super Scalar都只知道个大概，tableaux也知其然而不知所以然。
下星期好好参与一次，上课、作业一个都不能少，恩。
至于之后么，再说咯。

(define (reverse items)
  (define (reverse-iter i k)
    (if (null? i)
        k
        (reverse-iter (cdr i)
                      (cons (car i) k))))
 
  (reverse-iter items ()))

(define (filter predicate sequence)
  (cond ((null? sequence) null)
        ((predicate (car sequence))
         (cons (car sequence) 
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (enumerate-interval low high)
  (if (> low high)
      null
      (cons low (enumerate-interval (+ low 1) high))))

(define (enumerate-tree tree)
  (cond ((null? tree) null)
        ((pair? tree)
         (append (enumerate-tree (car tree))
                 (enumerate-tree (cdr tree))))
        (else (list tree))))

(define (hornel-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))

Ex 2.35
数出一棵树中的叶子数。这题我的做法比较土，没想到map-reduce操作上的递归，而是把叶子节点的值都改成1然后一个累加。

(define (count-leave tree)
  (accumulate +
              0
              (map (lambda (x) 1)
                   (enumerate-tree tree))))

其实只要递归调用主函数就行了

(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) (if (pair? x) (count-leaves x) 1)) t)))

Ex 2.36
可以理解为计算矩阵各列之和吧

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      null
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

    火车缓缓地开着，混杂的人群。此时的我不属于两边世界中的任何一个，孤立于这种空间和从属感的交界处。理下思路，趁着记忆的新鲜，在手机上敲下这四天的感受，以弥补将来的某天可能发生的对这次旅行的淡忘。

Zijingang Campus: A Fudaner's Perspective

1. Abstract
一次课堂电影(话剧《暗恋桃花源》[5])
旁听两节课，图形学和线性代数。图形学课上回答一次问题 =_=
一场越剧，小百花越剧团的《春琴传》
一场话剧，黑白剧社[1]的《我在天堂等你》[2]
半天图书馆自修，读了半章SICP[4]和一篇paper
半天机房灌水，水木C版版主上任后的第一个操作居然是在浙大完成的
半天在“风雨操场”打球
一晚上在浙大战网打了十盘星际，九胜一负

2. Introduction
    K900到车管所，一站的路程后到达正门。紫金港的正门没有试图制造一种空间隔离感，宽敞的道路上横躺着一块刻有“浙江大学”的石块，构成了形式上的正门。步行百余部后，回头才意识到原来百余步前的所处位置竟是一个入口。
    这个入口给人一种宽广、松驰的感觉，与复旦的正门放置伟人像不同，紫金港的封面很平坦。除了草坪就无其他，可以望到天际。整个紫金港都给我这样的感觉：草坪、树、湖的世界中，点缀着几幢风格各异的建筑。

3. Details
3.1 上课
    其实到浙大吃完饭后做的第一件事就是旁听了一节数媒专业的图形学，上的是三维空间的坐标变换。老师上课进度偏慢，绝大部分学生上课都很认真。感到那么一点点的压力 >,<

3.2 图书馆
    一直觉得图书馆是大学的灵魂组成部分之一。甚至大一的时候觉得有个好的图书馆和一套优秀的借阅制度就足以成为一个好的大学了。也因此新到一个大学后总是特别关注那里的图书馆。
    紫金港图书馆依傍在高耸的行政楼旁，可以把它比成计算中心，行政楼对应于光华主楼，较之后者它们靠得更紧密些。浙大同学说外校同学来看图书馆时，第一反应总是误把行政楼当图书馆。喜欢图书馆的这种低调。
    图书馆的书架分类很笼统，所有的理工类书橱都被贴上了“自然科学”的标签，恐怕找书的时候要很依赖电脑。抽样调查了计算机类书籍，书目较小，重复率较大，甚至会有十几册同本书罢占一层书架的情况。阅读环境很不错，落地窗，明亮。窗外便是那片湖，一如图书馆般地平静。若是把座椅换成摇椅，再加上一杯咖啡，最愉悦的享受莫过于此。
    离开图书馆时还让同学代借了本SICP[4]，本想带回上海以此要胁该同学五一来复旦，到时候再还的。无奈多带本书太麻烦，回来之前还是还掉了。

3.3 付费
    住宿楼旁有几家小吃店，其中不少店都是设置了一个单独的付费窗，而这个付费机制里没有任何凭证，或者说点了吃的却不付钱是很容易做到。别的不多说，这样一种店与客之间的信任给人一种亲切感。当然这也和紫金港地理位置较偏远，外人较少有关。

3.4 话剧
    看了黑白剧社[1]的《我在天堂等你》[2]。话剧在一个可容纳百人左右的小书屋里进行。由于一个月前刚看过人艺的《榆树下的欲望》[3]，相比之下学生的功底自然略逊一筹，尤其是对老年人的刻划上。不过总体还是很不错的。
    记忆最深的是社员的那份激情，话剧结束后，演员和工作人员挨个自我介绍完毕，然后跑出书屋，站在门口等待出来的观众，齐喊“再见”“谢谢”。下楼走出百余米后，听到后面三声击掌，接着是社员们高喊“谢谢你们”，如此重复几遍，一阵高过一阵。被这种热情所震撼。

3.5 肆
    一位同学的寝室门口贴着一张记录着这个班级同学的奋斗目标之类的墙纸，中间是一个硕大的草体“肆”。奋斗目标都很直接，譬如要被Stanford商学院录取，要进入某某大公司云云。不怎么喜欢这种过于外露的上进心，更欣赏复旦略带散漫的风格。

3.6 还是课
    浙大课比较多。上下午各5节，每节45分钟，中间休息5/15分。同时周末有课也是很常见的现象，为了提高绩点而重修的同学通常周末的课表也很满。个人不喜欢这种课多的生活，喜欢兴趣驱动的学习，不喜欢自己的学习方向太受外力的牵引。

4. The End
    总是有一种声音提醒自己，我不属于这里，注定不属于。太多的不应该出现的巧合，太多的主观的或是客观的借口。我有自己的天地，那里与浙大没有交集，即便我希望会有。

5. Acknowledgements
    感谢浙大那些被我折腾、蹭吃蹭喝的同学。
    感谢版主的m或b。

6. References
[1] 黑白剧社 http://www.qsc.zju.edu.cn/heibai/
[2] 我在天堂等你 http://www.douban.com/subject/1310322/
[3] 榆树下的欲望 Desire Under the Elms, http://www.douban.com/subject/1297393/
[4] Structure and Interpretation of Computer Programs, http://www.douban.com/subject/1451622/
[5] 暗恋桃花源，富含搞笑因素却又错综复杂值得深深体味的一部话剧，推荐一看 http://www.douban.com/subject/1299889/
[6] 春琴传，较传统的日本爱情故事 http://www.douban.com/subject/1949657/

其实理解了 Regular Expression -> NFA -> DFA 这个过程，大致的复杂度确定也不难

发信人: styc (styc), 信区: Algorithm
标  题: Re: 请问一下大家正则表达式的时间复杂度
发信站: 水木社区 (Wed Mar 26 20:37:02 2008), 站内

NFA构造O(n)，匹配O(nm)
DFA构造O(2^n)，最小化O(kn'logn')（N'=O(2^n)），匹配O(m)
n=regex长度，m=串长，k=字母表大小，n'=原始的dfa大小
大概是这样子吧

本来想看完pagefault的处理的，不过实验室有事情了，只能先把这一半放上来了。

页面的分配与回收使用了一个叫做buddy allocator的机制，kernelnewbies上的解释
The memory allocation scheme used in the kernel. A vector of lists of free pages is kept, ordered by the size of the chunk (in powers of two). When a chunk is allocated, it is removed from the relevant list. When a chunk is freed back to the free pages pool, it is placed in the relevant list, starting from the top. If it is physically contiguous with a present chunk, they are merged and placed in the list above (i.e. where the chunks are twice the size), and this operation percolates up the vector. As regions are merged whenever possible, this design helps to reduce memory fragmentation.

首先在zone_struct{} 中保存了一个free_area_t数组，这个数组记录了各种大小的空闲内存块的信息。
include/linux/mmzone.h:

/**/ /*
 * On machines where it is needed (eg PCs) we divide physical memory
 * into multiple physical zones. On a PC we have 3 zones:
 *
 * ZONE_DMA      < 16 MB    ISA DMA capable memory
 * ZONE_NORMAL    16-896 MB    direct mapped by the kernel
 * ZONE_HIGHMEM     > 896 MB    only page cache and user processes
  */
typedef  struct  zone_struct  {
     /**/ /*
     * Commonly accessed fields:
      */
    spinlock_t         lock ;
    unsigned  long         free_pages;
    unsigned  long         pages_min, pages_low, pages_high;
     int             need_balance;

     /**/ /*
     * free areas of different sizes
      */
     //  数组中每个元素依次维护1个pagesize，2个pagesize，4个pagesize……的空闲块的链表
    free_area_t        free_area[MAX_ORDER];  

     /**/ /*
     * Discontig memory support fields.
      */
     struct  pglist_data     * zone_pgdat;
     struct  page         * zone_mem_map;
    unsigned  long         zone_start_paddr;
    unsigned  long         zone_start_mapnr;

     /**/ /*
     * rarely used fields:
      */
     char              * name;
    unsigned  long         size;
}  zone_t;

typedef struct free_area_struct {
    struct list_head    free_list;
    unsigned long        *map;       // 某个特定大小的页面块分配情况的位图
} free_area_t;

Welcome to Microsoft DreamSpark

Professional Developer and Designer tools

• Sign In with your Windows Live ID. If you don't have one, go get one here. Pretty basic stuff.
  
  
• Get verified as a student. The system is linked to schools and organizations around the world that can confirm student status. Simply choose your country and school, enter your info and hit submit.
  
  
• Download your products. Now remember these are professional tools. This means they are pretty big files so make sure you have the bandwidth and space to bring them to your machine. We support the latest versions of both Internet Explorer and Firefox for your download.

#include <unistd.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <errno.h>
#include <stdio.h>
#include <string.h>

#define KEY 1234
#define SIZE 1024

int main()
{
    int shmid;
    char *shmaddr;
    struct shmid_ds buf;

    shmid = shmget(KEY, SIZE, IPC_CREAT | 0600);
    if (shmid == -1) {
        printf("Failed in creating shared memory: %s\n", strerror(errno));
        return 0;
    }

    if (fork() == 0) {
        shmaddr = (char *) shmat(shmid, NULL, 0);

        if (shmaddr == (void *) -1) {
            printf("Failed in connecting to the shared memory: %s\n", strerror(errno));
            return 0;
        }
        
        strcpy(shmaddr, "Hello, this is child process!\n");
        shmdt(shmaddr);
        return 0;
    } else {
        sleep(3);
        shmctl(shmid, IPC_STAT, &buf);
        
        printf("Size of the shared memory: ");
        printf("shm_segsz = %d bytes\n", buf.shm_segsz);
        printf("Process id of the creator: ");
        printf("shm_cpid = %d\n", buf.shm_cpid);
        printf("Process id of the last operator: ");
        printf("shm_lpid = %d\n", buf.shm_lpid);

        shmaddr = (char *) shmat(shmid, NULL, 0);

        if (shmaddr == (void *) -1) {
            printf("Failed in connecting the shared memory: %s\n", strerror(errno));
            return 0;
        }

        printf("The content of the shared memory: %s\n", shmaddr);

        shmdt(shmaddr);
        shmctl(shmid, IPC_RMID, NULL);
    }
}

/**//* Obsolete, used only for backwards compatibility and libc5 compiles */
struct shmid_ds {
    struct ipc_perm        shm_perm;    /**//* operation perms */
    int            shm_segsz;    /**//* size of segment (bytes) */
    __kernel_time_t        shm_atime;    /**//* last attach time */
    __kernel_time_t        shm_dtime;    /**//* last detach time */
    __kernel_time_t        shm_ctime;    /**//* last change time */
    __kernel_ipc_pid_t    shm_cpid;    /**//* pid of creator */
    __kernel_ipc_pid_t    shm_lpid;    /**//* pid of last operator */
    unsigned short        shm_nattch;    /**//* no. of current attaches */
    unsigned short         shm_unused;    /**//* compatibility */
    void             *shm_unused2;    /**//* ditto - used by DIPC */
    void            *shm_unused3;    /**//* unused */
};

/**//* Obsolete, used only for backwards compatibility and libc5 compiles */
struct ipc_perm
{
    __kernel_key_t    key;
    __kernel_uid_t    uid;
    __kernel_gid_t    gid;
    __kernel_uid_t    cuid;
    __kernel_gid_t    cgid;
    __kernel_mode_t    mode; 
    unsigned short    seq;
};

mode为该共享的内存的读写权限，和chmod的参数有点像。mode低九位定义了访问许可，解释如下：
0400 用户可读  0200用户可写  0040 组成员可读  0020 组成员可写  0004 其他用户可读  0002 其他用户可写
没有执行位 0100 0010 和 0001

不想一天到晚呆坐电脑前，灌灌水，聊聊天

还是读点村上的

《挪威的森林》估计是因为太喜欢，带到学校里了

那就先重读《国境以南，太阳以西》

当时应该是一行推荐我看安妮的书，然后我看到99的书单上安妮推荐了这本书，于是我就没买安妮的，买了这本 =_=

从此就迷上村上的小说了。尽管这本和《挪威的森林》与村上其他作品的风格还是有一定出入的。

让Python支持true closure有多难？
只需修改11行代码。

如果你不知道什么是true closure，这里简单解释一下。Python支持lexicalscope：

>>> def add_n(n):
...     def f(m):
...             return n+m
...     return f
>>> add_2 = add_n(2)
>>> add_2(0)
2
>>> add_2(2)
4

f引用了外层函数add_n的局部变量n。有趣的是，f引用n的时候，add_n已经结束，n似乎不存在了。f所以能正常工作，是因为创建它的时候就把n作为f的上下文(closure)保存了下来，并不随add_n结束而消失。
但是，Python的lexical scope和Scheme/Smalltalk/Ruby还有一点区别：不能在内层函数中rebind外层函数的局部变量。
>>> def f():
...     def g():
...             n=1
...     n=0
...     g()
...     return n
...
>>> f()
0

这是因为Python没有变量声明， n=1 自动使n成为g的局部变量，也就无法rebind f中的n了。可以说Python的closure是只读的。如果你听到有人说"Python不支持true closure"，就是指这个。其实，Python VM能够支持true closure。因为，Python支持内层函数看见外层函数的name rebinding:

>>> def f():
...     def g():
...             yield n
...             yield n
...     x = g()
...     n = 0
...     print x.next()
...     n = 1
...     print x.next()
...
>>> f()
0
1

对于Python的closure实现(flat closure)，"外层函数rebind name"和"内层函数rebind name"其实没有区别。我们知道用global关键字可以rebind module scopename。如果增加一个类似的outer关键字，就可以支持rebind outer scope name。真正的限制是Guido不愿意为支持true closure增加关键字。

也可以不增加关键字，而是把global n的语义改为"如果outer scope定义了n，rebind outer scope n；否则rebind module scope n"。简单起见，我没有修改Python的built-in compiler，而是修改了compiler module(用Python实现的Python compiler)。你只需把下面这个patch打到compiler/symbols.py(Python 2.5.1)就可以体验true closure了：

C:\Python\Lib>diff -u compiler/symbols.py.orig compiler/symbols.py
--- compiler/symbols.py.orig    Thu Aug 17 10:28:56 2006
+++ compiler/symbols.py Mon Feb 11 12:03:01 2008
@@ -21,6 +21,7 @@
         self.params = {}
         self.frees = {}
         self.cells = {}
+        self.outers = {}
         self.children = []
         # nested is true if the class could contain free variables,
         # i.e. if it is nested within another function.
@@ -54,8 +55,10 @@
         if self.params.has_key(name):
             raise SyntaxError, "%s in %s is global and parameter" % \
                   (name, self.name)
-        self.globals[name] = 1
-        self.module.add_def(name)
+        if self.nested:
+            self.outers[name] = 1
+        else:
+            self.globals[name] = 1

     def add_param(self, name):
         name = self.mangle(name)
@@ -90,6 +93,8 @@
         """
         if self.globals.has_key(name):
             return SC_GLOBAL
+        if self.outers.has_key(name):
+            return SC_FREE
         if self.cells.has_key(name):
             return SC_CELL
         if self.defs.has_key(name):
@@ -107,6 +112,7 @@
             return ()
         free = {}
         free.update(self.frees)
+        free.update(self.outers)
         for name in self.uses.keys():
             if not (self.defs.has_key(name) or
                     self.globals.has_key(name)):
@@ -134,6 +140,9 @@
         free.
         """
         self.globals[name] = 1
+        if self.outers.has_key(name):
+            self.module.add_def(name)
+            del self.outers[name]
         if self.frees.has_key(name):
             del self.frees[name]
         for child in self.children:

因为我们没有修改built-in compiler，所以程序要写在字符串里，用compiler.compile编译，用exec执行：
>>> from compiler import compile
>>> s = '''
... def counter():
...     n = 0
...     def inc():
...             global n
...             n += 1
...     def dec():
...             global n
...             n -= 1
...     def get():
...             return n
...     return inc, dec, get
... '''
>>> exec compile(s, '', 'exec')
>>> inc, dec, get = counter()
>>> get()
0
>>> inc()
>>> get()
1
>>> dec()
>>> get()
0

后记

1 搞这个东西的缘起是Selfless Python(http://www.voidspace.org.uk/python/weblog/arch_d7_2006_12_16.shtml#e583)。很有趣的bytecode hack，给一个类中的所有函数补上self参数。既然PythonVM支持true closure，能不能用类似的手法让Python支持true closure呢？不过很快就明白这个在bytecode层面不好弄，还是得修改编译器。不过改起来还真是出乎意料地简单。

2 Guido早已明确表示不能改变global的语义（因为会影响现有代码），所以这个只是玩玩而已，不用指望成为现实。当然你可以只发布bytecode，大概还能把反编译器搞挂掉。:-)
3 我可以理解Guido的决定。除非你之前一直在用Scheme，否则我觉得像上面counter例子那种一组共享状态的函数还是写成class为好，至少共享状态是什么一目了然。Lexical scope太implicit，用在开头add_n那种地方挺方便，再复杂就不好了。

又：很抱歉"幕后的故事"拖了这么久。写起来才发现自己还是不懂descriptor。
不过我肯定不会让它烂尾的。

新绝代双骄的插曲，当时蛮有感觉的，突然想起来我还没听过完整的。
http://www.whjsr.com/dc.mp3

我的双脚陷进爱中
等了已好久好久
你的手从指间经过
只能碰却不能握
心里好多话对你说
你却看着我沉默
这样的相爱那儿有错
连云也难说服我
我不是个稻草人
不能动不能说
已把爱紧紧绑心中
我不是个稻草人
没人爱没人懂
再难再疯我要结果
我不是个稻草人
看天亮看日落
就等你给我一双手
我不是个稻草人
不做梦不还手
别用泪水逼我放手

就算全界都笑我
爱个人谁敢说错
就算全世界都怪我
我只要你跟我走

作者：晏渭川
随着Linux2.6的发布，由于2.6内核做了新的改动，各个设备的驱动程序在不同程度上要进行改写。为了方便各位Linux爱好者我把自己整理的这分 文档share出来。该文当列举了2.6内核同以前版本的绝大多数变化，可惜的是由于时间和精力有限没有详细列出各个函数的用法。

1、 使用新的入口
必须包含 <linux/init.h>
module_init(your_init_func);
module_exit(your_exit_func);
老版本：int init_module(void);
void cleanup_module(voi);
2.4中两种都可以用，对如后面的入口函数不必要显示包含任何头文件。

2、 GPL
MODULE_LICENSE("Dual BSD/GPL");
老版本：MODULE_LICENSE("GPL");

3、 模块参数
必须显式包含<linux/moduleparam.h>
module_param(name, type, perm);
module_param_named(name, value, type, perm);
参数定义
module_param_string(name, string, len, perm);
module_param_array(name, type, num, perm);
老版本：MODULE_PARM(variable,type);
MODULE_PARM_DESC(variable,type);

4、 模块别名
MODULE_ALIAS("alias-name");
这是新增的，在老版本中需在/etc/modules.conf配置，现在在代码中就可以实现。

5、 模块计数
int try_module_get(&module);
module_put();
老版本：MOD_INC_USE_COUNT 和 MOD_DEC_USE_COUNT

http://www.fsl.cs.sunysb.edu/~sean/parser.cgi?modules

In 2.4 modules, the MOD_INC_USE_COUNT macro is used to prevent unloading of the module while there is an open file. The 2.6 kernel, however, knows not to unload a module that owns a character device that's currently open.
However, this requires that the module be explicit in specifying ownership of character devices, using the THIS_MODULE macro.

You also have to take out all calls to MOD_INC_USE_COUNT and MOD_DEC_USE_COUNT.
       
    static struct file_operations fops =
{
         .owner = THIS_MODULE,
         .read = device_read,
         .write = device_write,
         .open = device_open,
         .release = device_release
}    
       

The 2.6 kernel considers modules that use the deprecated facility to be unsafe, and does not permit their unloading, even with rmmod -f.

2.6,2.5的kbuild不需要到处加上MOD_INC_USE_COUNT来消除模块卸载竞争（module unload race）

6、 符号导出
只有显示的导出符号才能被其他模块使用，默认不导出所有的符号，不必使用EXPORT_NO_SYMBOLS
老板本：默认导出所有的符号，除非使用EXPORT_NO_SYMBOLS

7、 内核版本检查
需要在多个文件中包含<linux/module.h>时，不必定义__NO_VERSION__
老版本：在多个文件中包含<linux/module.h>时，除在主文件外的其他文件中必须定义__NO_VERSION__，防止版本重复定义。

8、 设备号
kdev_t被废除不可用，新的dev_t拓展到了32位，12位主设备号，20位次设备号。
unsigned int iminor(struct inode *inode);
unsigned int imajor(struct inode *inode);
老版本：8位主设备号，8位次设备号
int MAJOR(kdev_t dev);
int MINOR(kdev_t dev);

9、 内存分配头文件变更
所有的内存分配函数包含在头文件<linux/slab.h>，而原来的<linux/malloc.h>不存在
老版本：内存分配函数包含在头文件<linux/malloc.h>

10、 结构体的初试化
gcc开始采用ANSI C的struct结构体的初始化形式：
static struct some_structure = {
.field1 = value,
.field2 = value,
..
};
老版本：非标准的初试化形式
static struct some_structure = {
field1: value,
field2: value,
..
};

11、 用户模式帮助器
int call_usermodehelper(char *path, char **argv, char **envp, int wait);
新增wait参数

12、 request_module()
request_module("foo-device-%d", number);
老版本：
char module_name[32];
printf(module_name, "foo-device-%d", number);
request_module(module_name);

13、 dev_t引发的字符设备的变化
1、取主次设备号为
unsigned iminor(struct inode *inode);
unsigned imajor(struct inode *inode);
2、老的register_chrdev()用法没变，保持向后兼容，但不能访问设备号大于256的设备。
3、新的接口为
a)注册字符设备范围
int register_chrdev_region(dev_t from, unsigned count, char *name);
b)动态申请主设备号
int alloc_chrdev_region(dev_t *dev, unsigned baseminor, unsigned count, char *name);
看了这两个函数郁闷吧^_^！怎么和file_operations结构联系起来啊？别急！
c)包含 <linux/cdev.h>，利用struct cdev和file_operations连接
struct cdev *cdev_alloc(void);
void cdev_init(struct cdev *cdev, struct file_operations *fops);
int cdev_add(struct cdev *cdev, dev_t dev, unsigned count);
（分别为，申请cdev结构，和fops连接，将设备加入到系统中！好复杂啊！）
d)void cdev_del(struct cdev *cdev);
只有在cdev_add执行成功才可运行。
e)辅助函数
kobject_put(&cdev->kobj);
struct kobject *cdev_get(struct cdev *cdev);
void cdev_put(struct cdev *cdev);
这一部分变化和新增的/sys/dev有一定的关联。

14、 新增对/proc的访问操作
<linux/seq_file.h>
以前的/proc中只能得到string, seq_file操作能得到如long等多种数据。
相关函数：
static struct seq_operations 必须实现这个类似file_operations得数据中得各个成员函数。
seq_printf()；
int seq_putc(struct seq_file *m, char c);
int seq_puts(struct seq_file *m, const char *s);
int seq_escape(struct seq_file *m, const char *s, const char *esc);
int seq_path(struct seq_file *m, struct vfsmount *mnt,
struct dentry *dentry, char *esc);
seq_open(file, &ct_seq_ops);
等等

15、 底层内存分配
1、<linux/malloc.h>头文件改为<linux/slab.h>
2、分配标志GFP_BUFFER被取消，取而代之的是GFP_NOIO 和 GFP_NOFS
3、新增__GFP_REPEAT，__GFP_NOFAIL，__GFP_NORETRY分配标志
4、页面分配函数alloc_pages()，get_free_page()被包含在<linux/gfp.h>中
5、对NUMA系统新增了几个函数：
a) struct page *alloc_pages_node(int node_id, unsigned int gfp_mask, unsigned int order);
b) void free_hot_page(struct page *page);
c) void free_cold_page(struct page *page);
6、 新增Memory pools
<linux/mempool.h>
mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn, mempool_free_t *free_fn, void *pool_data);
void *mempool_alloc(mempool_t *pool, int gfp_mask);
void mempool_free(void *element, mempool_t *pool);
int mempool_resize(mempool_t *pool, int new_min_nr, int gfp_mask);

16、 per-CPU变量
get_cpu_var();
put_cpu_var();
void *alloc_percpu(type);
void free_percpu(const void *);
per_cpu_ptr(void *ptr, int cpu)
get_cpu_ptr(ptr)
put_cpu_ptr(ptr)
老版本使用
DEFINE_PER_CPU(type, name);
EXPORT_PER_CPU_SYMBOL(name);
EXPORT_PER_CPU_SYMBOL_GPL(name);
DECLARE_PER_CPU(type, name);
DEFINE_PER_CPU(int, mypcint);
2.6内核采用了可剥夺得调度方式这些宏都不安全。

17、 内核时间变化
1、现在的各个平台的HZ为
Alpha: 1024/1200; ARM: 100/128/200/1000; CRIS: 100; i386: 1000; IA-64: 1024; M68K: 100; M68K-nommu: 50-1000; MIPS: 100/128/1000; MIPS64: 100; PA-RISC: 100/1000; PowerPC32: 100; PowerPC64: 1000; S/390: 100; SPARC32: 100; SPARC64: 100; SuperH: 100/1000; UML: 100; v850: 24-100; x86-64: 1000.
2、由于HZ的变化，原来的jiffies计数器很快就溢出了，引入了新的计数器jiffies_64
3、#include <linux/jiffies.h>
u64 my_time = get_jiffies_64();
4、新的时间结构增加了纳秒成员变量
struct timespec current_kernel_time(void);
5、他的timer函数没变，新增
void add_timer_on(struct timer_list *timer, int cpu);
6、新增纳秒级延时函数
ndelay()；
7、POSIX clocks 参考kernel/posix-timers.c

18、 工作队列（workqueue）
1、任务队列（task queue ）接口函数都被取消，新增了workqueue接口函数
struct workqueue_struct *create_workqueue(const char *name);
DECLARE_WORK(name, void (*function)(void *), void *data);
INIT_WORK(struct work_struct *work,
void (*function)(void *), void *data);
PREPARE_WORK(struct work_struct *work,
void (*function)(void *), void *data);
2、申明struct work_struct结构
int queue_work(struct workqueue_struct *queue, struct work_struct *work);
int queue_delayed_work(struct workqueue_struct *queue, struct work_struct *work,
unsigned long delay);
int cancel_delayed_work(struct work_struct *work);
void flush_workqueue(struct workqueue_struct *queue);
void destroy_workqueue(struct workqueue_struct *queue);
int schedule_work(struct work_struct *work);
int schedule_delayed_work(struct work_struct *work, unsigned long delay);

19、 新增创建VFS的"libfs"
libfs给创建一个新的文件系统提供了大量的API.
主要是对struct file_system_type的实现。
参考源代码：
drivers/hotplug/pci_hotplug_core.c
drivers/usb/core/inode.c
drivers/oprofile/oprofilefs.c
fs/ramfs/inode.c
fs/nfsd/nfsctl.c (simple_fill_super() example)

20、 DMA的变化
未变化的有：
void *pci_alloc_consistent(struct pci_dev *dev, size_t size, dma_addr_t *dma_handle);
void pci_free_consistent(struct pci_dev *dev, size_t size, void *cpu_addr, dma_addr_t dma_handle);
变化的有：
1、 void *dma_alloc_coherent(struct device *dev, size_t size, dma_addr_t *dma_handle, int flag);
void dma_free_coherent(struct device *dev, size_t size, void *cpu_addr, dma_addr_t dma_handle);
2、列举了映射方向：
enum dma_data_direction {
DMA_BIDIRECTIONAL = 0,
DMA_TO_DEVICE = 1,
DMA_FROM_DEVICE = 2,
DMA_NONE = 3,
};
3、单映射
dma_addr_t dma_map_single(struct device *dev, void *addr, size_t size, enum dma_data_direction direction);
void dma_unmap_single(struct device *dev, dma_addr_t dma_addr, size_t size, enum dma_data_direction direction);
4、页面映射
dma_addr_t dma_map_page(struct device *dev, struct page *page, unsigned long offset, size_t size, enum dma_data_direction direction);
void dma_unmap_page(struct device *dev, dma_addr_t dma_addr, size_t size, enum dma_data_direction direction);
5、有关scatter/gather的函数：
int dma_map_sg(struct device *dev, struct scatterlist *sg, int nents, enum dma_data_direction direction);
void dma_unmap_sg(struct device *dev, struct scatterlist *sg, int nhwentries, enum dma_data_direction direction);
6、非一致性映射（Noncoherent DMA mappings）
void *dma_alloc_noncoherent(struct device *dev, size_t size, dma_addr_t *dma_handle, int flag);
void dma_sync_single_range(struct device *dev, dma_addr_t dma_handle, unsigned long offset, size_t size,
enum dma_data_direction direction);
void dma_free_noncoherent(struct device *dev, size_t size, void *cpu_addr, dma_addr_t dma_handle);
7、DAC (double address cycle)
int pci_dac_set_dma_mask(struct pci_dev *dev, u64 mask);
void pci_dac_dma_sync_single(struct pci_dev *dev, dma64_addr_t dma_addr, size_t len, int direction);

21、 互斥
新增seqlock主要用于：
1、少量的数据保护
2、数据比较简单(没有指针)，并且使用频率很高
3、对不产生任何副作用的数据的访问
4、访问时写者不被饿死
<linux/seqlock.h>
初始化
seqlock_t lock1 = SEQLOCK_UNLOCKED;
或seqlock_t lock2; seqlock_init(&lock2);
void write_seqlock(seqlock_t *sl);
void write_sequnlock(seqlock_t *sl);
int write_tryseqlock(seqlock_t *sl);
void write_seqlock_irqsave(seqlock_t *sl, long flags);
void write_sequnlock_irqrestore(seqlock_t *sl, long flags);
void write_seqlock_irq(seqlock_t *sl);
void write_sequnlock_irq(seqlock_t *sl);
void write_seqlock_bh(seqlock_t *sl);
void write_sequnlock_bh(seqlock_t *sl);
unsigned int read_seqbegin(seqlock_t *sl);
int read_seqretry(seqlock_t *sl, unsigned int iv);
unsigned int read_seqbegin_irqsave(seqlock_t *sl, long flags);
int read_seqretry_irqrestore(seqlock_t *sl, unsigned int iv, long flags);

22、 内核可剥夺
<linux/preempt.h>
preempt_disable()；
preempt_enable_no_resched()；
preempt_enable_noresched()；
preempt_check_resched()；

23、 眠和唤醒
1、原来的函数可用，新增下列函数：
prepare_to_wait_exclusive()；
prepare_to_wait()；
2、等待队列的变化
typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int sync);
void init_waitqueue_func_entry(wait_queue_t *queue, wait_queue_func_t func);

24、 新增完成事件（completion events）
<linux/completion.h>
init_completion(&my_comp);
void wait_for_completion(struct completion *comp);
void complete(struct completion *comp);
void complete_all(struct completion *comp);

25、 RCU（Read-copy-update）
rcu_read_lock();
void call_rcu(struct rcu_head *head, void (*func)(void *arg),
void *arg);

26、 中断处理
1、中断处理有返回值了。
IRQ_RETVAL(handled)；
2、cli(), sti(), save_flags(), 和 restore_flags()不再有效，应该使用local_save
_flags() 或local_irq_disable()。
3、synchronize_irq()函数有改动
4、新增int can_request_irq(unsigned int irq, unsigned long flags);
5、 request_irq() 和free_irq() 从 <linux/sched.h>改到了 <linux/interrupt.h>

27、 异步I/O(AIO)
<linux/aio.h>
ssize_t (*aio_read) (struct kiocb *iocb, char __user *buffer, size_t count, loff_t pos);
ssize_t (*aio_write) (struct kiocb *iocb, const char __user *buffer, size_t count, loff_t pos);
int (*aio_fsync) (struct kiocb *, int datasync);
新增到了file_operation结构中。
is_sync_kiocb(struct kiocb *iocb)；
int aio_complete(struct kiocb *iocb, long res, long res2);

28、 网络驱动
1、struct net_device *alloc_netdev(int sizeof_priv, const char *name, void (*setup)(struct net_device *));
struct net_device *alloc_etherdev(int sizeof_priv);
2、新增NAPI(New API)
void netif_rx_schedule(struct net_device *dev);
void netif_rx_complete(struct net_device *dev);
int netif_rx_ni(struct sk_buff *skb);
(老版本为netif_rx())

29、 USB驱动
老版本struct usb_driver取消了，新的结构体为
struct usb_class_driver {
char *name;
struct file_operations *fops;
mode_t mode;
int minor_base;
};
int usb_submit_urb(struct urb *urb, int mem_flags);
int (*probe) (struct usb_interface *intf,
const struct usb_device_id *id);

30、 block I/O 层
这一部分做的改动最大。不祥叙。

31、 mmap()
int remap_page_range(struct vm_area_struct *vma, unsigned long from, unsigned long to, unsigned long size, pgprot_t prot);
int io_remap_page_range(struct vm_area_struct *vma, unsigned long from, unsigned long to, unsigned long size, pgprot_t prot);
struct page *(*nopage)(struct vm_area_struct *area, unsigned long address, int *type);
int (*populate)(struct vm_area_struct *area, unsigned long address, unsigned long len, pgprot_t prot, unsigned long pgoff, int nonblock);
int install_page(struct mm_struct *mm, struct vm_area_struct *vma, unsigned long addr, struct page *page, pgprot_t prot);
struct page *vmalloc_to_page(void *address);

32、 零拷贝块I/O(Zero-copy block I/O)
struct bio *bio_map_user(struct block_device *bdev, unsigned long uaddr, unsigned int len, int write_to_vm);
void bio_unmap_user(struct bio *bio, int write_to_vm);
int get_user_pages(struct task_struct *task, struct mm_struct *mm, unsigned long start, int len, int write, int force, struct page **pages, struct vm_area_struct **vmas);

33、 高端内存操作kmaps
void *kmap_atomic(struct page *page, enum km_type type);
void kunmap_atomic(void *address, enum km_type type);
struct page *kmap_atomic_to_page(void *address);
老版本：kmap() 和 kunmap()。

34、 驱动模型
主要用于设备管理。
1、 sysfs
2、 Kobjects

推荐文章：
http:/www-900.ibm.com/developerWorks/cn/linux/kernel/l-kernel26/index.shtml
http:/www-900.ibm.com/developerWorks/cn/linux/l-inside/index.shtml

2.6里不需要再定义“__KERNEL__”和“MODULE”了。
用下面的Makefile文件编译：

代码:

    obj-m   := hello.o

    KDIR   := /lib/modules/$(shell uname -r)/build
    PWD      := $(shell pwd)
    default:
              $(MAKE) -C $(KDIR) M=$(PWD) modules

4.2. Data Structures

The GPU Memory Model
通常使用二维的texture保存，一是因为一维texture能存放的东西很少，二是因为现在的GPU很难高效地写入一列3维texture。
Iteration
stream编程模型包含了一种隐式的流的并行遍历。    
Generalized Arrays via Address Translation
在GPGPU编程中主要使用的数据结构是随机访问的多位容器，包括稀疏/稠密数组等。每个结构定义了一个虚拟域virual grid domain和一个物理域physical grid domaiin，以及之间相互转换的address translator。

4.2.1. Dense Arrays
多维数组通常先映射到一维，然后再到二维。
4.2.2. Sparse Arrays
根据非零元素的位置和数量是否变化分两种，静态和动态。
4.2.3. Adaptive Structures