大头
Table_bottom

标签云
Table_bottom

分类
Table_bottom

日历
五月
2829301234
567891011
12131415161718
19202122232425
2627282930311
Table_bottom

评论
Table_bottom

留言
Table_bottom

微博
Table_bottom

热门文章
Table_bottom

随机文章
Table_bottom

豆瓣上谁关注这里
Table_bottom

链接
Table_bottom

搜索栏
Table_bottom

RSS
RSS Link
Table_bottom

功能
Table_bottom

页面
Table_bottom

计数器
473910
Table_bottom

访客统计
Table_bottom

存档
Table_bottom

书债

收到china-pub送来的《瞬间之美》《Don't Make Me Think》《写给大家看的设计书》。

《重构》还没看完。

书债,书债。

重构 - 090808

6.2 Inline Method

紧随Extract Method之后,作者也说了,间接层有其价值,但不是所有间接层都有价值。

6.4 Replace Temp with Query

说到性能问题,在重构时可以降低性能问题的优先级,因为很多情况下不会造成影响。如果性能真的出了问题,也可以在优化时期解决它。如果代码组织良好,往往能帮助发现更有效的优化方案。当然,如果性能真的是在受到了很大的影响,可以再恢复回去。

10.4 Separate Query from Modifier

任何有返回值的函数,都不应该有看得到的副作用。

重构 - 090807

6.1 Extract Method

提炼(extracting)代码,使每个函数的粒度变小,有着很多好处:函数复用的机会变大;可读性强;函数的override更容易等。

作者说:即使想要提炼的代码非常简单,简单到知识一条消息或一个函数调用,只要新函数的名称能够以更好的方式昭示代码意图,也应该提炼它。

在嵌入式环境里,尤其是空间资源有限的条件下,对Extract Method方法的运用可能需要做一点调整。

单纯使函数粒度变小的提炼需要慎重,除非实际已有复用的代码段。

由于编译器的优化,无法准确预估单纯的提炼一段代码对编译出的二进制代码体积有变大或是变小的影响,更难估计对运行期空间的影响和执行效率的影响。

我的体验是,如果想要提炼一段代码,先试一下,如果大大提高代码的可读性,又没有显著增加代码体积,可行;如果代码段已有“复用”,根据“事不过三,三则重构”的原则,可为,即便会增大代码体积,只要在可以接受的范围内;如果增加了代码体积,这个成本换取的可读性不合算,不为。

至于怎样才是显著增加代码体积,要根据不同工程的情况来判断了。

重构 - 090805

3.2

原文:
Since the early days of programming people have realized that the longer a procedure is, the more difficult it is to understand.
Older languages carried an overhead in subroutine calls, which deterred people from small methods.
Modern OO languages have pretty much eliminated that overhead for in-process calls.

翻译:
很久以前程序员就已认识到:程序愈长愈难理解。
早期的编程语言中,“子程序调用动作”需要额外开销这使得人们不太乐意使用small method。
现代OO语言几乎已经完全免除了进程内的“函数调用动作额外开销”。

现代OO语言里函数调用没有开销了么?

重构 - 090804

如果你发现自己需要为程序添加一个特性,而代码结构使你无法很方便地那么做,那就先重构那个程序,使特性的添加比较容易,然后再添加特性。

重构的第一个步骤:为即将修改的代码建立一组可靠的测试环境。

每次修改的幅度小,任何错误都很容易发现。重构以微小的步伐修改程序,如果犯下错误,很容易便可发现。

重构的一个重要方向是消除重复代码。

重构应该随时随地进行。

事不过三,三则重构。

GUI设计禁忌2.0 - 090712

不应当让用户通过排除法来发现软件是如何工作的。

读《项目管理艺术》

真正的进度表风险是那些没有被写下来的东西。

流程中最重要的部分就是众人应该扮演的角色。

每个人都应该知道中间点是什么。

读《项目管理艺术》

· 理论只有两种:错误的理论和不完整的理论。

· 不要把焦点放在流程和方法上。

· 对流程着迷就是领导才能有问题的警告信息。

代码之美 - 081104

《当你与世界的联系只有一个按钮时》,Arun Mehta讲的是给霍金教授设计写字和说话的软件。Mehta是一个印度人。

这一篇的翻译一般,也许是译者看原文看得很枯燥,译文让我读得也枯燥。

由于输入只能通过对一个按钮的点击,软件的设计煞费苦心。主要以树型结构为基础,用表实现预测,用缓存提高命中。

有兴趣的可以去这个讨论列表

P535有一个错误,“在界面的右下方显示了两个数字(参见图30-2)”,应该是图30-1。可我查了英文版,也错为30-2了。

代码之美 - 081022

《漂亮的调试》,Andreas Zellerddd的一个bug为引,介绍了增量调试(Delta Debugging),主要思想类同二分,算法好理解,可是程序看不大明白。

程序如下。

  1. def dd(c_pass, c_fail, test):
  2.     """Return a triple (DELTA, C_PASS', C_FAIL') such that
  3.        - C_PASS subseteq C_PASS' subset C_FAIL' subseteq C_FAIL holds
  4.        - DELTA = C_FAIL' - C_PASS' is a minimal difference
  5.          between C_PASS' and C_FAIL' that is relevant with respect
  6.          to TEST."""
  7.  
  8.     n = 2 # Number of subsets
  9.  
  10.     while 1:
  11.         assert test(c_pass) == PASS # Invariant
  12.         assert test(c_fail) == FAIL # Invariant
  13.         assert n >= 2
  14.  
  15.         delta = listminus(c_fail, c_pass)
  16.  
  17.         if n > len(delta):
  18.             # No further minimizing
  19.             return (delta, c_pass, c_fail)
  20.  
  21.         deltas = split(delta, n)
  22.         assert len(deltas) == n
  23.  
  24.         offset = 0
  25.         j = 0
  26.         while j < n:
  27.             i = (j + offset) % n
  28.             next_c_pass = listunion(c_pass, deltas[i])
  29.             next_c_fail = listminus(c_fail, deltas[i])
  30.  
  31.             if test(next_c_fail) == FAIL and n == 2:
  32.                 c_fail = next_c_fail
  33.                 n = 2; offset = 0; break
  34.             elif test(next_c_fail) == PASS:
  35.                 c_pass = next_c_fail
  36.                 n = 2; offset = 0; break
  37.             elif test(next_c_pass) == FAIL:
  38.                 c_fail = next_c_pass
  39.                 n = 2; offset = 0; break
  40.             elif test(next_c_fail) == FAIL:
  41.                 c_fail = next_c_fail
  42.                 n = max(n - 1, 2); offset = i; break
  43.             elif test(next_c_pass) == PASS:
  44.                 c_pass = next_c_pass
  45.                 n = max(n - 1, 2); offset = i; break
  46.             else:
  47.                 j = j + 1
  48.  
  49.         if j >= n:
  50.             if n >= len(delta):
  51.                 return (delta, c_pass, c_fail)
  52.             else:
  53.                 n = min(len(delta), n * 2)
  54.  

1,第三行注释翻译成:“C_PASS是C_PASS'的子集,C_FAIL'是C_FAIL的子集”。想了一想,没错,函数是逐步缩小c_pass和c_fail之间的差异,在书中例子里,也是通常情况下,c_pass是空的,c_fail是“失败全集”。

2,在 j < n 这个循环里,n = 2, i = 0, 把全集分成两部分,如果第一个 if 成立,c_fail等于其中一部分,n = 2, offset = 0, break是否是跳出这一堆if-elif-else?跳出的话回到循环开始,j 没有机会改变,i 也就仍然等于0。我尝试着模拟几种情况,n等于2、4、8,似乎程序跑步到 else 里,j = j + 1 没有机会被执行,i 的值也就得不到改变。也许我对 test 函数的返回理解有误。摇头叹息看不懂看不懂。

作者说在这本书的O'Reilly网页上也有这段代码,于是去下载,下载的代码和书上的不大一样,算法是一致的,清楚多了,一看就明白。再回头看上面这一段,还是觉得不大对。作罢作罢。

文中还提到Continuout Testing。作者说他开了一门课,专门讲授科学方法和增量调试,课程幻灯片和参考文献在:http://www.whyprogramsfail.com/,可是我打不开这个网页。还有增量调试的主页:http://www.st.cs.uni-sb.de/dd/

代码之美 - 081017

《代码如散文》。Yukihiro Matsumoto自然对Ruby大夸特夸。作者用简洁的一篇散文谈了谈漂亮代码的几个因素,简洁,保守,简单,灵活。

有两句话应该时时记住:

程序中不应该包含无用的信息。

不要重复代码,不要把相同的东西编写两次。

代码之美 - 081016

《优雅代码随硬件发展的演化》,因为题目的诱人,选择读这一章,开了头就发现上当。

磕磕巴巴把前面的问题描述读完,被示例程序14-1难倒了。且不说MATLAB的奇怪写法,LU因式分解我也没搞清楚,于是,这个30多行的程序,来来回回多少遍也看不明白。自然也就不明白作者说的这个代码如何地漂亮。

了解了一下LU因式分解,再去看程序,还是头晕。于是决定放弃看代码,包括后面的FORTRAN代码和C代码。

马马虎虎看完这一章的汉字,一知半解的,大约知道Jack DongarraPiotr Luszczek(他的主页上links提供了很多好看链接)在说漂亮的代码如何高效地利用存储器层次结构获得高性能。

代码之美 - 081008

《Linux内核驱动模型:协作的好处》这章篇幅不大,可读得费劲。

上来就有两句话没看懂:在2.4版本的内核中,每一个设备的物理部分都由一段总线特定的代码来控制。总线代码负责各种不同类型的任务,而每一种具体总线的代码之间则没有交互。

后一句的原文是:This bus code was responsible for a wide range of different tasks, and each individual bus code had no interaction with any other bus code.

这里,总线特定代码(bus-specific code)是什么意思?

然后,Greg Kroah-Hartman提出两个问题,1是在解决电源管理问题时,内核需要知道不同设备的连接关系;2是不论哪一台USB打印机先启动,两台打印机的名字永不变。

其他系统的一般解决方法,1是内核中放一个处理设备名的小数据库,2是通过文件系统中可以直接访问设备的devfs类型来导出设备的所有信息。

对Linux来说,内核里放数据库是不能接受的,同时,Linux的devfs文件系统实现中“存在一些众所周知的且难以消除的竞争条件,导致几乎所有的Linux发布的版本中都不能依赖它。”这句话怎么理解?

再然后,作者用一个“简单”的例子展现了,展现了什么呢,我觉得是展现了C语言的复杂用法。如作者所说:是的,非常强大,只要你清楚地知道你正在做什么。

不信就看看这个宏吧: 

  1. #define container_of(ptr, type, member)    ({    \
  2.     const typeof( ((type *)0) ->member ) * _mptr = (ptr);    \
  3.     (type *)( (char *)_mptr - offsetof(type, member) );})

作者通过介绍Linux内核中解决前面提到的两个问题所需的数据结构和支持函数的演变,来说明协作给Linux带来的好处,还好文末有个总结,否则我又要忘了他要说什么。

代码之美 - 081007

《漂亮的测试》这一章很容易阅读,Alberto Savoia介绍如何写测试用例,漂亮的。

他举例说明如何写漂亮的测试代码,这个过程又是如何使被测代码变得更好。其实,更加强调的是程序员本来就应该测试自己的代码。

有多少程序员像画家一样,常常放下笔,站远点,从不同角度,在不同光线下,审视自己的作品呢?

我很少编写程序去测试自己写的函数,我的同事也一样。我们更多依赖运行整个程序检查结果是否正确,依赖测试组的同事们。

作者介绍的是Java程序员常用的JUnit

不要给自己找借口,只要想做,办法总是有的。

挑了几个错误,填写到这里

代码之美 - 081003

收到了《代码之美》,把目录翻来翻去,在33章里找我最容易能看懂的,似乎并没有哪一章让我觉得可以顺畅阅读不用多加以思索的。

最后挑选了第24章《美丽的并发》,作者是Simon Peyton Jones,他用Haskell语言来介绍STM(Software transactional memory),看得我很头大。注意力几乎全被Haskell语言占据了,3、5行的程序段却费了不少脑筋去思量。以至于文章最后作者在总结的时候,我都没有感觉到他说的所有的好处到底在哪里。回头想想,似乎是那么回事,可一到细节,脑子里搅和的还是语言的细节。

反正我记住了,最大的好处是使并发程序的模块性更好。还避免了不少常犯的错误。

这一章里的代码有下载

我还想知道,Haskell多用在什么地方?记录下Haskell的官方网站,那里可以找到很多信息,下载很多东西。

再记下这本书的英文版勘误信息

 

PHP初学——字符串

PHP的语法也实在是搞,表示字符串可以用双引号",也可以用单引号'。

和C一样也是用'\'转义,如果串里要显示'\',双引号得这样'\\';单引号,'\'就可以了。

既然'\'表转义,如果要表达单引号',在使用单引号的情况下,这样写:

  1. 'this string has a \' quote.'

就是说,在单引号内的'\'是转义字符还是'\'它自己,取决于它后面的内容。

这不是找麻烦嘛。

外部变量申明的一个错误

C++中的外部变量不是类型安全的变量。

File: sub.cpp 

  1. // the string to print
  2. char str[] = "Hello World!\n";

 File: main.cpp 

  1. #include <iostream>
  2.  
  3. extern char *str; // the string to print
  4.  
  5. int main()
  6. {
  7.     std::cout<< str << std::endl;
  8.     return (0);
  9. }

 在这里,str被认为是一个指针,程序运行到那儿,读其地址前4位,而前4位是“Hell”,不是一个地址,所以出错。

MIPS处理器设计透视-080403

跳转指令:

  • 最小操作码字段是6位,跳转目标可以用26位来寻址,又因为指令是4字节对齐,最低两个有效位(least significant)不需要存储,所以地址空间是:228=256M。
  • 条件分支跳转只有一个带符号的16位PC相对偏移域,同样,跳转范围是218字节大小。

MIPS处理器设计透视-080402

为每条指令都分配MEM阶段(从数据缓存中读/写 内存变量)是为了保证同一时刻不会有两条指令都去访问数据缓存。

MIPS指令集的规定:

  • 所有指令都是32位的。—>条件转移限制在64KB(216)范围内。
                         —>装入任一32位值需两条连续指令。
                         —>跳转指令中的目标地址常数用26位编码(MIPS指令里,最小的操作码字段是6位)。
  • 指令操作必须符合流水线,必须在一个时钟周期内执行完。
  • 3操作数指令。
  • 32个寄存器。
  • 寄存器0($0)总是返回0。
  • 无条件标志的代码。 

编址及内存访问:

  • load/store必须对齐:字节在任何地址都可以被传送;半字必须按偶数字节对齐;字必须按4字节边界对齐。

信号量和同步互斥

进程的互斥与P、V操作

一、临界资源

什么是临界资源:任何时候只允许一个进程使用的资源为临界资源。

什么是临界区:访问临界资源的代码段为临界区。

例如:
代码段1 
 

  1. a = count;
  2. a--;
  3. count = a;

 代码段2   

  1. b = count;
  2. b++;
  3. count = b;

为临界区,count为临界资源。

对临界资源的访问必须满足以下条件:
一次只能有一个进程进入,其他进程等待。
进入者必须在有限时间内退出。
等待者应该有机会进入。

二、信号量

信号量的结构模型:(S,Q)
在2.4.x内核中,信号量数据结构定义为(include/asm/semaphore.h): 
 

  1. struct semaphore {
  2. atomic_t count;
  3. int sleepers;
  4. wait_queue_head_t wait;
  5. #if WAITQUEUE_DEBUG
  6. long __magic;
  7. #endif
  8. };

信号量操作:
1) 初始化
2) P操作
a) S--
b) if(S < 0) 在Q队列中睡眠
     else 进入
3) V操作
a) S++
b) if(S <= 0) 唤醒一睡眠进程(等待队列中有进程在睡眠)
     else 继续
P操作可以理解为申请资源,V操作可以理解为释放资源,在2.4.x内核semaphore结构中,count是资源计数,为正数或0时表示可用资源数,-1表示没有空闲资源且有等待进程,至于等待进程的数量并不关心,实现中依赖了sleepers,比较复杂,但好处是是up操作非常简单,只需汇编原子地将count加1,如果小于等于0表示有进程等待,调用__up_wakeup() --> __up(),否则返回。linux中的实现可以到arch/i386/kernel/semaphore.c中看到(2.4.x kernel),__down()和__up()。

信号量实现:
用ITRON的一个简单实现<An ITRON Implementation>做为例子。我粗略地看了一下代码,关于信号量(semaphore)的P/V操作,有计数器控制和等待队列。
SEMCB(semaphore control block)结构中有id,队列,计数器等成员。 

  1. OS_AcquireSemaphoreTimeOut()
  2. { ...
  3.         lock()
  4.         semcb->semcnt-- // counter --
  5.         if(semcb->semcnt < 0)
  6.         {
  7.                 make_wait() // make current task in wait state
  8.                 queue_insert_tpri() // insert by priority to the semaphore's
  9.                 //wait queue,which is a circular queue
  10.         }
  11.         unlock()
  12.         ...
  13. }
  14.  
  15. OS_FreeSemaphore()
  16. { ...
  17.         lock()
  18.         if(semcp->semcnt < 0)
  19.         {
  20.                 wait_release_ok()
  21.                 |
  22.                 -> wait_release() // release a task from wait state
  23.         }
  24.         semcb->semcnt++ // counter ++
  25.         unlock()
  26.         ...
  27. }

注:V操作中S先加1再判断是否小于等于0和先判断是否小于0再加1是等价的。
注:在这个实现中,semcnt值不仅正负分别表示资源空闲或有进程等待,其绝对值也是有意义的,为负时值代表等待的进程数,为正或零时值代表空闲的资源数。

三、同步互斥模型

S=1

  1. P(S)
  2. 临界区
  3. V(S)


  1. P(S)
  2. 临界区
  3. V(S)


生产者消费者问题
(生产者计算生成数,消费者打印之。)

1个生产者1个消费者,缓冲buf为1
2个信号量实现模型:put = 1 get = 0

  1. 计算x
  2. P(put)
  3. buf = x
  4. V(get)

  1. P(get)
  2. y = buf
  3. V(put)
  4. 打印y


1个生产者2个消费者,缓冲buf为1(2个消费者一个打印奇数一个打印偶数)
3个信号量实现模型:put = 1 getj = 0 geto = 0

  1. 计算x
  2. P(put)
  3. buf = x
  4. if(x为奇)
  5.     V(getj)
  6. else
  7.     V(geto)

  1. P(getj)
  2. y = buf
  3. V(put)
  4. 打印y

  1. P(geto)
  2. y = buf
  3. V(put)
  4. 打印y

这个模型比较直观,但是用了3个信号量。在计算出x后判断其奇偶再"V"不同的信号量。
如果只使用2个信号量如何实现,生产者计算出x后直接"V"一个信号量,2个消费者取出后判断是否打印还是不于理会。
2个信号量实现模型:put = 1 get = 0

  1. 计算x
  2. P(put)
  3. buf = x
  4. V(get)

  1. P(get)
  2. y = buf
  3. if(y为奇)
  4. {
  5.     V(put)
  6.     打印y
  7. }
  8. else
  9.     V(get)

 C

  1. P(get)
  2. y = buf
  3. if(y为偶)
  4. {
  5.     V(put)
  6.     打印y
  7. }
  8. else
  9.     V(get)


1个生产者1个消费者,缓冲buf为m
2个信号量实现模型:put = m get = 0

  1. 计算x
  2. P(put)
  3. buf[t] = x
  4. t = (++t) % m
  5. V(get)

 B 

  1. P(get)
  2. y = buf[k]
  3. k = (++k) % m
  4. V(put)
  5. 打印y


N个生产者M个消费者,缓冲buf为m
4个信号量实现模型:put = m get = 0 T = 1 K = 1

  1. 计算x
  2. P(put)
  3. P(T)
  4. buf[t] = x
  5. t = (++t) % m
  6. V(T)
  7. V(get)

  1. P(get)
  2. P(K)
  3. y = buf[k]
  4. k = (++k) % m
  5. V(K)
  6. V(put)
  7. 打印y

 
四、删除一个信号量

删除一个信号量,系统应该释放一些资源。如果无进程在等待此信号量,处理比较简单。
如果有进程在等待此信号量,如何处理这些进程,有人说kill,但我看到的一个实现是唤醒。
除进程之外,这个等待队列也需要释放,否则会造成内存泄露。
不仅是删除一个信号量,在系统中当删除某个资源时,会释放等待队列的所有task。

OS_DelFlag --|
OS_DelMessageBuffer --|--> call wait_delete(QUEUE *) --> OS_DelSemaphore --| 

  1. while()
  2. {wait_release();...} // release all tasks blocked on specified wait queue


五、由来

为什么敲打这么个东西。因为有个自主实现的基于ITRON的OS需要测试。在测试其信号量资源时我补充了一个测试用例,即当有进程在等待一个信号量时删除此信号量系统会有如何反应。基于此,先给测试人员做了presentation介绍信号量及同步互斥模型。然后粗略地看了看linux 2.4.x,ITRON和ucLinux三个系统的P/V操作和删除信号量的实现。因工作繁忙没有深入研究,简单整理一下用了两个小时边解bug边偷闲着输入完。然后steedhorse帮忙做了检查,经过了一个小时的讨论,改了一些错误,在此感谢。
有的问题我不是很清楚,希望看了后能提出来大家讨论。