可视化函数调用

所需工具:

  1. GCC
  2. Graphviz
  3. 中间件pvtrace,下载
  4. addr2line 下载

过程:

  1. 编译/安装 pvtrace(make,make install 即可)
  2. 将 pvtrace 中instrument.c 拷贝到要进行编译的路径
  3. 按如下代码编译测试程序(注意第三行-finstrument-functions 是连起来的):
 1: $ ls
 2: instrument.c    test.c
 3: $ $ gcc -g -finstrument-functions test.c instrument.c -o test
 4: $ ./test
 5: $ ls
 6: instrument.c     test.c
 7: test             trace.txt
 8: $ pvtrace test
 9: $ ls
 10: graph.dot        test           trace.txt
 11: instrument.c     test.c
 12: $ dot -Tjpg graph.dot -o graph.jpg
 13: $ ls
 14: graph.dot        instrument.c   test.c
 15: graph.jpg        test           trace.txt
 16: $

我的源码:

 1: #include <stdlib.h>
 2:
 3: void step1(){
 4: printf(“I am step1 !\n”);
 5: }
 6:
 7: void step(){
 8: printf(“I am last step !\n”);
 9: }
 10:
 11: void step2(){
 12: printf(“I am step2 !\n”);
 13: step();
 14: }
 15:
 16: int main(void){
 17: step1();
 18: step2();
 19: return 1;
 20: }
 21:

 

编译生成的图片:

PS:在makefile 中添加中间件编译参考[2]。

参考:

[1].http://www.ibm.com/developerworks/cn/linux/l-graphvis/

[2].http://blog.csdn.net/seasonpplp/article/details/7399053

[3].http://blog.csdn.net/fisher_jiang/article/details/6828427

拜占庭将军问题

参考 The Byzantine Generals Problems

这个问题的最初描述是:n 个将军被分隔在不同的地方,忠诚的将军希望通过某种协议达成某个命令的一致(比如一起进攻或者一起后退)。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport 证明了在将军总数大于3m ,背叛者为m 或者更少时,忠诚的将军可以达成命令上的一致。

为了保证上面的需求,必须满足下面两个条件:

1. 每两个忠诚的将军必须收到相同的值 v(i)(v(i)是第i 个将军的命令)

2. 如果第i 个将军是忠诚的,那么他发送的命令和每个忠诚将军收到的v(i)相同

为了简化以上模型,我们使用一个将军发送命令给多个副官的形式来证明,发送命令的将军称为发令者,接收命令的将军为副官,那么上面的两个条件可以表述为:

IC1. 所有忠诚的副官遵守相同的命令

IC2. 如果发出命令的将军是忠诚的,那么所有忠诚的副官遵守相同的命令

特别提示:发送命令的每次只有一个将军,将其命令发送给n-1 个副官。m 代表叛国者的个数,因为将军总数为n,所以副官总数为n-1 个。IC2 中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。

一、通过口头消息

通过口头消息传递达到一致,如果有m 个叛国将军,则将军们的总数必须为3m+1 个以上。下面是口头消息传递过程中默认的一些条件:

A1. 每个被发送的消息都能够被正确的投递

A2. 信息接收者知道是谁发送的消息

A3. 能够知道缺少的消息

A1 和A2 假设了两个将军之间通信没有干扰,既不会有背叛者阻碍消息的发送(截断)也不会有背叛者伪造消息的情况(伪造)。即是每个将军都可以无误地将自己的消息发送给其他每个将军。(下一节中可以不需要这个必要条件)

我们定义口头消息算法OM(m) 。对于所有的非负整数m ,每个发令者通过OM(M) 算法发送命令给n-1 个副官。下面将说明OM(m) 算法在最多有m 个背叛者且总将军数为3m+1 或者更多的情况下可以解决拜占庭将军问题。(考虑到网络应用实际环境,原文使用了收到值代替收到命令,本文不做修改)

算法定义一个函数:$majority(com_1,com_2,\dots,com_n)$ 等于多数派命令。


OM(0)算法

(1)发令者将他的命令发送给每个副官。

(2)每个副官采用他从发令者发来的命令,或者默认使用撤退命令,如果没有收到任何命令。

OM(m)算法

(1)发令者将他的命令发送给每个副官。

(2)对于每个i ,vi 是每个副官i 从发令者收到的命令,如果没有收到命令则为撤退命令。副官i 在OM(m-1) 中作为发令者将vi 发送给另外n-2 个副官。

(3)对于每个i,并且$j\neq i$,vj 是副官i 从第(2)步中的副官j 发送过来的命令(使用OM(m-1) 算法),如果没有收到第(2)步中的副官j 的命令则默认为撤退命令。最后副官i 使用majority(v_1,\dots,v_{n-1})得到命令。


继续阅读

为WordPress 博客添加分页功能

参考:脱离插件,实现WordPress主题分页功能

一直觉得WordPress 默认的Older Entries 不太友善,想改成分页功能,google 的分页的插件,wp-pagenavi 还是比较流行,安装之后发现主页响应非常慢,过了十多分钟还是以没有分页的方式显示出来了,感觉可能是主题与插件的兼容性,更可能是之前修改了页面的布局,wp-pagenavi 插件与我修改的布局不太兼容,于是参考了网上的一些方法,自己添加了一些分页的功能。再次提醒广大站长:要么不要对源WP 或者主题进行修改,一旦修改了以后都要做好自己动手改代码的觉悟。

继续阅读

【翻译】对lamport 的一段采访

源地址:http://research.microsoft.com/en-us/um/people/lamport/pubs/ds-interview.pdf

Dejan Milojicic: 你从事的许多具有想象力的问题都在实际应用中有成就,甚至在几十年之后仍有影响。你对研究方向的选择在时机上有什么特别么?

Leslie Lamport: 遇到一些问题是因为工程师们在构建系统时碰到了,需要算法来解决, fast mutual exclusion algorithm 和 disk Paxos 就是这类。还有一些,比如cache coherence,是我自己想出来的。我在选择这类问题的时候没有考虑到时机是否合适。

Dejan Milojicic: 你认为你的哪个贡献对现代计算机科学与产业具有最大的影响力?

Leslie Lamport: 我的引用量最多的文章是“Time, Clock, and Ordering of Events  in a Distributed System.”,我不知道这和你说的影响是不是一回事,因为我并不能从该文章直接指导出许多工作,但可能它影响了人们对思考分布式系统的方法。我认为我在工业界还没有太多影响,虽然我期望Paxos 和状态机方法将在分布式系统设计上有重要影响。这是在微软发现的(注:Lamport 加入了微软)。

继续阅读

SSD 并行的性能影响

原文: Performance Impact and Interplay of SSD Parallelism through Advanced Commands, Allocation Strategy and Data Granularity

文章是胡杨博士在2011 ICS 上发表的,通过他的模拟软件SSDsim 对SSD 的并行和高级命令(advanced commands)的分析得出了一些SSD 设计实现上的建议.之前都苦于没有SSD 比较详细的综述,于是自己凑了和了一篇(之前写过的综述),而这篇文章则似乎更适合作SSD 的综述,讲的很清晰。

Idea

通过多层次的SSD 仿真器SSDsim 分析了SSD 内部影响性能的因素(并行)。

总结

  1. large pages 在许多情况下对SSD 有比较大的负面影响
    1. 越大的pages 更易导致数据的迁移
  2. 不同physical-page allocation 可应用于不同环境中,对任意工作负载都会有一个最优方案
    1. Static allocation 读性能在所有情况下最优
  3. 高级命令在一些情况下能够改进SSD 性能,但是用不当会适得其反
    1. 使用高级命令必须带有约束条件才能够提升性能
  4. SSD 四种并行:channel 层、chip 层、die 层和plane 层并行,它们优先级对性能有影响并和2、3中physical-page allocation 与高级命令相互作用、影响。
    1. 并行的优先顺序应该为:1、channel-level  2、chip-level  3、die-level  4、plane-level

微软云存储架构(Azure Cloud Storage)

原文:Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency

 

IDEA

A cloud storage system that provides customers the ability to store seemingly limitless amounts of data with high availablity and strong consistency. 为用户提供高可用、高一致性并近乎无限空间的云存储。

 

System characteristics 系统特点:

  1. High availablity and strong consistency 高可用性和强一致性
  2. Global and scalable namespace/storage 全局可扩展的名字空间、存储
  3. Multiple data abstractions from a single stack 支持多种类型的数据
  4. Automatic load balancing 自动负载均衡
  5. Range Partition vs Hashing 使用动态区域划分,而没采用哈希
  6. Append-only system 存储系统只有append 操作。
  7. End-to-end checksum 端到端的校验和
  8. Separate log file per RangePartition 日志文件粒度为RangePartition

高可用通过多副本策略实现(默认三个),数据写入的原子性操作保证强一致性。Azure 支持blob(数据块)、Table(structured storage)和Queues(消息队列)三类数据。所有数据都是以添加的方式写入的。

继续阅读