来源:http://portableapps.com/node/12561下载http://zer0dev.com/dld/download.php?id=27头文件使用:1. !include "ProcFunc.nsh"2. 可使用范围:$var为返回值[Section|Function]${ProcFunction} "参数1" "参数2" "..." $var[SectionEnd|FunctionEnd]${ProcessExists} "[process]" "[process]" ; Name or PID Use with a LogicLib conditional command like If or Unless. Evaluates to true if the process exists or false if it does not or the CreateToolhelp32Snapshot fails.${GetProcessPID} "[process]" $var "[process]" ; Name or PID $var(output) ; -2 - CreateToolhelp32Snapshot failed ; 0 - process does not exist ; >0 - PID${GetProcessPath} "[process]" $var "[process]" ; Name or PID $var(output) ; -2 - CreateToolhelp32Snapshot failed ; -1 - OpenProcess failed ; 0 - process does not exist ; Or path to process${GetProcessParent} "[process]" $var "[process]" ; Name or PID $var(output) ; -2 - CreateToolhelp32Snapshot failed ; 0 - process does not exist ; Or PPID${GetProcessName} "[PID]" $var "[PID]" ; PID $var(output) ; -2 - CreateToolhelp32Snapshot failed ; 0 - process does not exist ; Or process name${EnumProcessPaths} "Function" $var "Function" ; Callback function $var(output) ; -2 - EnumProcesses failed ; 1 - success Function "Function" Pop $var1 ; matching path string Pop $var2 ; matching process PID ...user commands Push [1/0] ; must return 1 on the stack to continue ; must return some value or corrupt the stack ; DO NOT save data in $0-$9 FunctionEnd${ProcessWait} "[process]" "[timeout]" $var "[process]" ; Name "[timeout]" ; -1 - do not timeout ; >0 - timeout in milliseconds $var(output) ; -2 - CreateToolhelp32Snapshot failed ; -1 - operation timed out ; Or PID${ProcessWait2} "[process]" "[timeout]" $var "[process]" ; Name "[timeout]" ; -1 - do not timeout ; >0 - timeout in milliseconds $var(output) ; -1 - operation timed out ; Or PID${ProcessWaitClose} "[process]" "[timeout]" $var "[process]" ; Name "[timeout]" ; -1 - do not timeout ; >0 - timeout in milliseconds $var(output) ; -1 - operation timed out ; 0 - process does not exist ; Or PID of ended process${CloseProcess} "[process]" $var "[process]" ; Name or PID $var(output) ; 0 - process does not exist ; Or PID of ended process${TerminateProcess} "[process]" $var "[process]" ; Name or PID $var(output) ; -1 - operation failed ; 0 - process does not exist ; Or PID of ended process${Execute} "[command]" "[working_dir]" $var "[command]" ; '"X:\path\to\prog.exe" arg1 arg2 "arg3 with space"' "[working_dir]" ; Working directory ("X:\path\to\dir") or nothing ("") $var(output) ; 0 - failed to create process ; Or PID*/本文转自:http://www.dreams8.com/forum.php?mod=viewthread&tid=17067&fromuid=1
posted @
2012-10-18 14:09 王海光 阅读(836) |
评论 (0) |
编辑 收藏
posted @
2012-10-18 14:02 王海光 阅读(640) |
评论 (0) |
编辑 收藏
1 CString sTempIPs;
2 sTempIPs.Format("%s%s", CCommonFun::GetTmpPath(), "TempIPs.txt");
3
4 ::DeleteFile(sTempIPs);
5 CString sPara;
6 sPara.Format("/c ipconfig.exe | findstr \"IP Address\" > \"%s\"", sTempIPs);
7 CCommonFun::WinExecAndWait32("cmd.exe", sPara, CCommonFun::GetExecutablePath(), INFINITE);
8
9 if (CFileFind().FindFile(sTempIPs))
10 {
11 CString sLine, sIP;
12 CString sFlag = ": ";
13 CStdioFile stdFile;
14 if (stdFile.Open(sTempIPs, CFile::modeRead))
15 {
16 while (stdFile.ReadString(sLine))
17 {
18 int nPos = sLine.Find(sFlag);
19 if (nPos != -1)
20 {
21 sIP = sLine.Mid(nPos+sFlag.GetLength(), sLine.GetLength()-(nPos+sFlag.GetLength()));
22 sIP.TrimLeft();
23 sIP.TrimRight();
24 arsLocalIPs.Add(sIP);
25 }
26 }
27 }
28 }
posted @
2012-09-29 14:33 王海光 阅读(553) |
评论 (0) |
编辑 收藏
摘要: 在开机启动应用程序时,可能会碰到权限不够而启动失败或者一些其他问题,所以在开机启动程序时可能会使用SYSTEM权限,但由于后来的操作不需要高权限来完成,就需要降低应用程序的权限。可以通过获取explorer.exe进程ID来实现。
Code highlighting produced by Actipro CodeHigh...
阅读全文
posted @
2012-09-29 14:22 王海光 阅读(1179) |
评论 (0) |
编辑 收藏
半个月前在豆瓣上看到了一本新书《数学之美》,评价很高。而因为在半年前看了《什么是数学》就对数学产生浓厚兴趣,但苦于水平不足的我便立马买了一本,希望能对数学多一些了解,并认真阅读起来。
令我意外并欣喜的是,这本书里边的数学内容并不晦涩难懂,而且作者为了讲述数学之美而搭配的一些工程实例都是和我学习并感兴趣的模式识别,目标分类相关算法相关联的。这让我觉得捡到了意外的宝藏。
书中每一个章节都或多或少是作者亲身经历过的,比如世界级教授的小故事,或者Google的搜索引擎原理,又或者是Google的云计算等。作者用其行云流水般的语言将各个知识点像讲故事一样有趣的叙述出来。
这本书着实让我印象深刻,所以我把笔记分享出来,希望更多和我学习研究领域一样的人会喜欢并亲自阅读这本书,并能支持作者。毕竟国内这种书实在是太少了,也希望能有更多领域内的大牛能再写出一些这种书籍来让我们共同提高。
1. 因为需要传播信息量的增加,不同的声音并不能完全表达信息,语言便产生了。
2. 当文字增加到没有人能完全记住所有文字时,聚类和归类就开始了。例如日代表太阳或者代表一天。
3. 聚类会带来歧义性,但上下文可以消除歧义。信息冗余是信息安全的保障。例如罗塞塔石碑上同一信息重复三次。
4. 最短编码原理即常用信息短编码,生僻信息长编码。
5. 因为文字只是信息的载体而非信息本身,所以翻译是可以实现的。
6. 2012,其实是玛雅文明采用二十进制,即四百年是一个太阳纪,而2012年恰巧是当前太阳纪的最后一年,2013年是新的太阳纪的开始,故被误传为世界末日。
7. 字母可以看为是一维编码,而汉字可以看为二维编码。
8. 基于统计的自然语言处理方法,在数学模型上和通信是相通的,甚至是相同的。
9. 让计算机处理自然语言的基本问题就是为自然语言这种上下文相关的特性建立数学模型,即统计语言模型(Statistical Language Modal)。
10. 根据大数定理(Law of Large Numbers),只要统计量足够,相对频度就等于概率。
11. 二元模型。对于p(w1,w2,…,wn)=p(w1)p(w2|w1)p(w3|w1,w2)…p(wn|w1,w2,…,wn-1)的展开问题,因为p(w3|w1,w2)难计算,p(wn|w1,w2,…,wn-1)更难计算,马尔科夫给出了一个偷懒但是颇为有效的方法,也就是每当遇到这种情况时,就假设任意wi出现的概率只与它前面的wi-1有关,即p(s)=p(w1)p(w2|w1)p(w3|w2)…p(wi|wi-1)…p(wn|wn-1)。现在这个概率就变的简单了。对应的语言模型为2元模型(Bigram Model)。
12. *N元模型。wi只与前一个wi-1有关近似的过头了,所以N-1阶马尔科夫假设为p(wi|w1,w2,…,wi-1)=p(wi|wi-N+1,wi-N+2,…,wi-1),对应的语言模型成为N元模型(N-Gram Model)。一元模型就是上下文无关模型,实际应用中更多实用的是三元模型。Google的罗塞塔翻译系统和语言搜索系统实用的是四元模型,存储于500台以上的Google服务器中。
13. *卡兹退避法(Katz backoff),对于频率超过一定阈值的词,它们的概率估计就是它们在语料库中的相对频度,对于频率小于这个阈值的词,它们的概率估计就小于他们的相对频度,出现次数越少,频率下调越多。对于未看见的词,也给予一个比较小的概率(即下调得到的频率总和),这样所有词的概率估计都平滑了。这就是卡兹退避法(Katz backoff)。
14. 训练数据通常是越多越好,通过平滑过渡的方法可以解决零概率和很小概率的问题,毕竟在数据量多的时候概率模型的参数可以估计的比较准确。
15. 利用统计语言模型进行分词,即最好的分词方法应该保证分完词后这个句子出现的概率最大。根据不同应用,汉语分词的颗粒度大小应该不同。
16. 符合马尔科夫假设(各个状态st的概率分布只与它前一个状态st-1有关)的随即过程即成为马尔科夫过程,也称为马尔科夫链。
17. 隐含马尔科夫模型是马尔科夫链的扩展,任意时刻t的状态st是不可见的,所以观察者没法通过观察到一个状态序列s1,s2,s3,…,sT来推测转移概率等参数。但是隐马尔科夫模型在每个时刻t会输出一个符号ot,而且ot和st相关且仅和ot相关。这个被称为独立输出假设。其中隐含的状态s1,s2,s3,…是一个典型的马尔科夫链。
18. 隐含马尔科夫模型是机器学习主要工具之一,和几乎所有机器学习的模型工具一样,它需要一个训练算法(鲍姆-韦尔奇算法)和使用时的解码算法(维特比算法)。掌握了这两类算法,就基本上可以使用隐含马尔科夫模型这个工具了。
19. 鲍姆-韦尔奇算法(Baum-Welch Algorithm),首先找到一组能够产生输出序列O的模型参数,这个初始模型成为Mtheta0,需要在此基础上找到一个更好的模型,假定不但可以算出这个模型产生O的概率P(O|Mtheta0),而且能够找到这个模型产生O的所有可能的路径以及这些路径的概率。并算出一组新的模型参数theta1,从Mtheta0到Mtheta1的过程称为一次迭代。接下来从Mtheta1出发寻找更好的模型Mtheta2,并一直找下去,直到模型的质量没有明显提高为止。这样一直估计(Expectation)新的模型参数,使得输出的概率达到最大化(Maximization)的过程被称为期望值最大化(Expectation-Maximization)简称EM过程。EM过程能保证一定能收敛到一个局部最优点,但不能保证找到全局最优点。因此,在一些自然语言处理的应用中,这种无监督的鲍姆-韦尔奇算法训练处的模型比有监督的训练得到的模型效果略差。
20. 熵,信息熵的定义为H(X)=-SumP(x)logP(x),变量的不确定性越大,熵也越大。
21. 一个事物内部会存在随机性,也就是不确定性,假定为U,而从外部消除这个不确定性唯一的办法是引入信息I,而需要引入的信息量取决于这个不确定性的大小,即I>U才行。当I<U时,这些信息可以消除一部分不确定性,U'=U-I。反之,如果没有信息,任何公示或者数字的游戏都无法排除不确定性。
22. 信息的作用在于消除不确定性。
23. 互信息,对两个随机事件相关性的量化度量,即随机事件X的不确定性或者说熵H(X),在知道随机事件Y条件下的不确定性,或者说条件熵H(X|Y)之间的差异,即I(X;Y)=H(X)-H(X|Y)。所谓两个事件相关性的量化度量,即在了解了其中一个Y的前提下,对消除另一个X不确定性所提供的信息量。
24. 相对熵(Kullback-Leibler Divergence)也叫交叉熵,对两个完全相同的函数,他们的相对熵为零;相对熵越大,两个函数差异越大,反之,相对熵越小,两个函数差异越小;对于概率分布或者概率密度函数,如果取值均大于零,相对熵可以度量两个随机分布的差异性。
25. 弗里德里克·贾里尼克(Frederek Jelinek)是自然语言处理真谛的先驱者。
26. 技术分为术和道两种,具体的做事方法是术,做事的原理和原则是道。术会从独门绝技到普及再到落伍,追求术的人会很辛苦,只有掌握了道的本质和精髓才能永远游刃有余。
27. 真理在形式上从来是简单的,而不是复杂和含混的。
28. 搜索引擎不过是一张大表,表的每一行对应一个关键字,而每一个关键字后面跟着一组数字,是包含该关键词的文献序号。但当索引变的非常大的时候,这些索引需要通过分布式的方式存储到不同的服务器上。
29. 网络爬虫(Web Crawlers),图论的遍历算法和搜索引擎的关系。互联网虽然复杂,但是说穿了其实就是一张大图……可以把每一个网页当做一个节点,把那些超链接当做连接网页的弧。有了超链接,可以从任何一个网页出发,用图的遍历算法,自动访问到每一个网页并且把他们存储起来。完成这个功能的程序叫网络爬虫。
30. 哥尼斯堡七桥,如果一个图能从一个顶点出发,每条边不重复的遍历一遍回到这个顶点,那么每一个顶点的度必须为偶数。
31. 构建网络爬虫的工程要点:1.用BFS(广度优先搜索)还是DFS(深度优先搜索),一般是先下载完一个网站,再进入下一个网站,即BFS的成分多一些。2.页面的分析和URL的提取,如果有些网页明明存在,但搜索引擎并没有收录,可能的原因之一是网络爬虫中的解析程序没能成功解析网页中不规范的脚本程序。3.记录哪些网页已经下载过的URL表,可以用哈希表。最终,好的方法一般都采用了这样两个技术:首先明确每台下载服务器的分工,也就是在调度时,一看到某个URL就知道要交给哪台服务器去下载,这样就避免了很多服务器对同一个URL做出是否需要下载的判断。然后,在明确分工的基础上,判断URL是否下载就可以批处理了,比如每次向哈希表(一组独立的服务器)发送一大批询问,或者每次更新一大批哈希表的内容,这样通信的次数就大大减少了。
32. PageRank衡量网页质量的核心思想,在互联网上,如果一个网页被很多其他网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。同时,对于来自不同网页的链接区别对待,因为网页排名高的那些网页的链接更可靠,于是要给这些链接比较大的权重。
33. TF-IDF(Term Frequency / Inverse Document Frequency) ,关键词频率-逆文本频率值,其中,TF为某个网页上出现关键词的频率,IDF为假定一个关键词w在Dw个网页中出现过,那么Dw越大,w的权重越小,反之亦然,公式为log(D/Dw)。1.一个词预测主题的能力越强,权重越大,反之,权重越小。2.停止词的权重为零。
34. 动态规划(Dynamic Programming)的原理,将一个寻找全程最优的问题分解成一个个寻找局部最优的小问题。
35. 一个好的算法应该像轻武器中最有名的AK-47冲锋枪那样:简单、有效、可靠性好而且容易读懂(易操作)而不应该故弄玄虚。选择简单方案可以容易解释每个步骤和方法背后的道理,这样不仅便于出问题时的查错,也容易找到今后改进的目标。
36. 在实际的分类中,可以先进行奇异值分解(得到分类结果略显粗糙但能较快得到结果),在粗分类结果的基础上,利用计算向量余弦的方法(对范围内的分类做两两计算),在粗分类结果的基础上,进行几次迭代,得到比较精确的结果。
37. 奇异值分解(Singular Value Decomposition),在需要用一个大矩阵A来描述成千上万文章和几十上百万词的关联性时,计算量非常大,可以将A奇异值分解为X、B和Y三个矩阵,Amn=Xmm*Bmn*Ynn,X表示词和词类的相关性,Y表示文本和主题的相关性,B表示词类和主题的相关性,其中B对角线上的元素很多值相对其他的非常小,或者为零,可以省略。对关联矩阵A进行一次奇异值分解,就可以同时完成近义词分类和文章的分类,同时能得到每个主题和每个词义类之间的相关性,这个结果非常漂亮。
38. 信息指纹。如果能够找到一种函数,将5000亿网址随即地映射到128位二进制,也就是16字节的整数空间,就称这16字节的随机数做该网址的信息指纹。信息指纹可以理解为将一段信息映射到一个多维二进制空间中的一个点,只要这个随即函数做的好,那么不同信息对应的点不会重合,因此这个二进制的数字就变成了原来信息所具有的独一无二的指纹。
39. 判断两个集合是否相同,最笨的方法是这个集合中的元素一一比较,复杂度O(squareN),稍好的是将元素排序后顺序比较,复杂度O(NlogN),最完美的方法是计算这两个集合的指纹,然后直接进行比较,计算复杂度O(N)。
40. 伪随机数产生器算法(Pseudo-Random Number Generator,PRNG),这是产生信息指纹的关键算法,通过他可以将任意长的整数转换成特定长度的伪随机数。最早的PRNG是将一个数的平方掐头去尾取中间,当然这种方法不是很随即,现在常用的是梅森旋转算法(Mersenne Twister)。
41. 在互联网上加密要使用基于加密的伪随机数产生器(Cryptography Secure Pseudo-Random Number Generator,CSPRNG),常用的算法有MD5或者SHA-1等标准,可以将不定长的信息变成定长的128位或者160位二进制随机数。
42. 最大熵模型(Maximum Entropy)的原理就是保留全部的不确定性,将风险降到最小。最大熵原理指出,需要对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设。在这种情况下,概率分布最均匀,预测的风险最小。I.Csiszar证明,对任何一组不自相矛盾的信息,这个最大熵模型不仅存在,而且是唯一的,此外,他们都有同一个非常简单的形式-指数函数。
43. 通用迭代算法(Generalized Iterative Scaling,GIS)是最原始的最大熵模型的训练方法。1.假定第零次迭代的初始模型为等概率的均匀分布。2.用第N次迭代的模型来估算每种信息特征在训练数据中的分布。如果超过了实际的,就把相应的模型参数变小,反之变大。3.重复步骤2直至收敛。这是一种典型的期望值最大化(Expectation Maximization,EM)算法。IIS(Improved Iterative Scaling)比GIS缩短了一到两个数量级。
44. 布隆过滤器实际上是一个很长的二进制向量和一系列随机映射的函数。
45. 贝叶斯网络从数学的层面讲是一个加权的有向图,是马尔科夫链的扩展,而从知识论的层面看,贝叶斯网络克服了马尔科夫那种机械的线性的约束,它可以把任何有关联的事件统一到它的框架下面。在网络中,假定马尔科夫假设成立,即每一个状态只与和它直接相连的状态有关,而和他间接相连的状态没有直接关系,那么它就是贝叶斯网络。在网络中每个节点概率的计算,都可以用贝叶斯公式来进行,贝叶斯网络也因此得名。由于网络的每个弧都有一个可信度,贝叶斯网络也被称作信念网络(Belief Networks)。
46. 条件随机场是计算联合概率分布的有效模型。在一个隐含马尔科夫模型中,以x1,x2,...,xn表示观测值序列,以y1,y2,...,yn表示隐含的状态序列,那么xi只取决于产生它们的状态yi,和前后的状态yi-1和yi+1都无关。显然很多应用里观察值xi可能和前后的状态都有关,如果把xi和yi-1,yi,yi+1都考虑进来,这样的模型就是条件随机场。它是一种特殊的概率图模型(Probablistic Graph Model),它的特殊性在于,变量之间要遵守马尔科夫假设,即每个状态的转移概率只取决于相邻的状态,这一点和另一种概率图模型贝叶斯网络相同,它们的不同之处在于条件随机场是无向图,而贝叶斯网络是有向图。
47. 维特比算法(Viterbi Algoritm)是一个特殊但应用最广的动态规划算法,利用动态规划,可以解决任何一个图中的最短路径问题。它之所以重要,是因为凡是使用隐含马尔科夫模型描述的问题都可以用它来解码。1.从点S出发,对于第一个状态x1的各个节点,不妨假定有n1个,计算出S到他们的距离d(S,x1i),其中x1i代表任意状态1的节点。因为只有一步,所以这些距离都是S到他们各自的最短距离。2.对于第二个状态x2的所有节点,要计算出从S到他们的最短距离。d(S,x2i)=min_I=1,n1_d(S,x1j)+d(x1j,x2i),由于j有n1种可能性,需要一一计算,然后找到最小值。这样对于第二个状态的每个节点,需要n1次乘法计算。假定这个状态有n2个节点,把S这些节点的距离都算一遍,就有O(n1*n2)次运算。3.按照上述方法从第二个状态走到第三个状态一直走到最后一个状态,这样就得到整个网络从头到尾的最短路径。
48. 扩频传输(Spread-Spectrum Transmission)和固定频率的传输相比,有三点明显的好处:1.抗干扰能力强。2.信号能量非常低,很难获取。3.扩频传输利用带宽更充分。
49. Google针对云计算给出的解决工具是MapReduce,其根本原理就是计算机算法上常见的分治算法(Divide-and-Conquer)。将一个大任务拆分成小的子任务,并完成子任务的计算,这个过程叫Map,将中间结果合并成最终结果,这个过程叫Reduce。
50. 逻辑回归模型(Logistic Regression)是将一个事件出现的概率适应到一条逻辑曲线(Logistic Curve)上。典型的逻辑回归函数:f(z)=e`z/e`z+1=1/1+e`-z。逻辑曲线是一条S型曲线,其特点是开始变化快,逐渐减慢,最后饱和。逻辑自回归的好处是它的变量范围从负无穷到正无穷,而值域范围限制在0-1之间。因为值域的范围在0-1之间,这样逻辑回归函数就可以和一个概率分别联系起来了。因为自变量范围在负无穷到正无穷之间,它就可以把信号组合起来,不论组合成多大或者多小的值,最后依然能得到一个概率分布。
51. 期望最大化算法(Expectation Maximization Algorithm),根据现有的模型,计算各个观测数据输入到模型中的计算结果,这个过程称为期望值计算过程(Expectation),或E过程;接下来,重新计算模型参数,以最大化期望值,这个过程称为最大化的过程(Maximization),或M过程。这一类算法都称为EM算法,比如隐含马尔科夫模型的训练方法Baum-Welch算法,以及最大熵模型的训练方法GIS算法。
本文转自:http://www.cppblog.com/humanchao
posted @
2012-09-21 17:50 王海光 阅读(1248) |
评论 (0) |
编辑 收藏
摘要: 一、预备知识—程序的内存分配
一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。
3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
4、文字常量区—常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。
阅读全文
posted @
2012-09-21 13:04 王海光 阅读(497) |
评论 (0) |
编辑 收藏
author : Kevin Lynx
什么是完成包?
完成包,即IO Completion Packet,是指异步IO操作完毕后OS提交给应用层的通知包。IOCP维护了一个IO操作结果队列,里面
保存着各种完成包。应用层调用GQCS(也就是GetQueueCompletionStatus)函数获取这些完成包。
最大并发线程数
在一个典型的IOCP程序里,会有一些线程调用GQCS去获取IO操作结果。最大并发线程数指定在同一时刻处理完成包的线程数目。
该参数在调用CreateIoCompletionPort时由NumberOfConcurrentThreads指定。
工作者线程
工作者线程一般指的就是调用GQCS函数的线程。要注意的是,工作者线程数和最大并发线程数并不是同一回事(见下文)。工作者
线程由应用层显示创建(_beginthreadex 之类)。工作者线程通常是一个循环,会不断地GQCS到完成包,然后处理完成包。
调度过程
工作者线程以是否阻塞分为两种状态:运行状态和等待状态。当线程做一些阻塞操作时(线程同步,甚至GQCS空的完成队列),线程
处于等待状态;否则,线程处于运行状态。
另一方面,OS会始终保持某一时刻处于运行状态的线程数小于最大并发线程数。每一个调用GQCS函数的线程OS实际上都会进行记录,
当完成队列里有完成包时,OS会首先检查当前处于运行状态的工作线程数是否小于最大并发线程数,如果小于,OS会按照LIFO的顺
序让某个工作者线程从GQCS返回(此工作者线程转换为运行状态)。如何决定这个LIFO?这是简单地通过调用GQCS函数的顺序决定的。
从这里可以看出,这里涉及到线程唤醒和睡眠的操作。如果两个线程被放置于同一个CPU上,就会有线程切换的开销。因此,为了消
除这个开销,最大并发线程数被建议为设置成CPU数量。
从以上调度过程还可以看出,如果某个处于运行状态的工作者线程在处理完成包时阻塞了(例如线程同步、其他IO操作),那么就有
CPU资源处于空闲状态。因此,我们也看到很多文档里建议,工作者线程数为(CPU数*2+2)。
在一个等待线程转换到运行状态时,有可能会出现短暂的时间运行线程数超过最大并发线程数,这个时候OS会迅速地让这个新转换
的线程阻塞,从而减少这个数量。(关于这个观点,MSDN上只说:by not allowing any new active threads,却没说明not allowing
what)
调度原理
这个知道了其实没什么意义,都是内核做的事,大致上都是操作线程control block,直接摘录<Inside IO Completion Ports>:
The list of threads hangs off the queue object. A thread's control block data structure has a pointer in it that
references the queue object of a queue that it is associated with; if the pointer is NULL then the thread is not
associated with a queue.
So how does NT keep track of threads that become inactive because they block on something other than the completion
port" The answer lies in the queue pointer in a thread's control block. The scheduler routines that are executed
in response to a thread blocking (KeWaitForSingleObject, KeDelayExecutionThread, etc.) check the thread's queue
pointer and if its not NULL they will call KiActivateWaiterQueue, a queue-related function. KiActivateWaiterQueue
decrements the count of active threads associated with the queue, and if the result is less than the maximum and
there is at least one completion packet in the queue then the thread at the front of the queue's thread list is
woken and given the oldest packet. Conversely, whenever a thread that is associated with a queue wakes up after
blocking the scheduler executes the function KiUnwaitThread, which increments the queue's active count.
参考资料
<Inside I/O Completion Ports>:
http://technet.microsoft.com/en-us/sysinternals/bb963891.aspx
<I/O Completion Ports>:
http://msdn.microsoft.com/en-us/library/aa365198(VS.85).aspx
<INFO: Design Issues When Using IOCP in a Winsock Server>:
http://support.microsoft.com/kb/192800/en-us/
本文转自:http://www.cppblog.com/kevinlynx/archive/2008/06/23/54390.html
posted @
2012-09-20 13:12 王海光 阅读(482) |
评论 (0) |
编辑 收藏
Author : Kevin Lynx
主要部分,四次握手:
断开连接其实从我的角度看不区分客户端和服务器端,任何一方都可以调用close(or closesocket)之类
的函数开始主动终止一个连接。这里先暂时说正常情况。当调用close函数断开一个连接时,主动断开的
一方发送FIN(finish报文给对方。有了之前的经验,我想你应该明白我说的FIN报文时什么东西。也就是
一个设置了FIN标志位的报文段。FIN报文也可能附加用户数据,如果这一方还有数据要发送时,将数据附
加到这个FIN报文时完全正常的。之后你会看到,这种附加报文还会有很多,例如ACK报文。我们所要把握
的原则是,TCP肯定会力所能及地达到最大效率,所以你能够想到的优化方法,我想TCP都会想到。
当被动关闭的一方收到FIN报文时,它会发送ACK确认报文(对于ACK这个东西你应该很熟悉了)。这里有个
东西要注意,因为TCP是双工的,也就是说,你可以想象一对TCP连接上有两条数据通路。当发送FIN报文
时,意思是说,发送FIN的一端就不能发送数据,也就是关闭了其中一条数据通路。被动关闭的一端发送
了ACK后,应用层通常就会检测到这个连接即将断开,然后被动断开的应用层调用close关闭连接。
我可以告诉你,一旦当你调用close(or closesocket),这一端就会发送FIN报文。也就是说,现在被动
关闭的一端也发送FIN给主动关闭端。有时候,被动关闭端会将ACK和FIN两个报文合在一起发送。主动
关闭端收到FIN后也发送ACK,然后整个连接关闭(事实上还没完全关闭,只是关闭需要交换的报文发送
完毕),四次握手完成。如你所见,因为被动关闭端可能会将ACK和FIN合到一起发送,所以这也算不上
严格的四次握手---四个报文段。
在前面的文章中,我一直没提TCP的状态转换。在这里我还是在犹豫是不是该将那张四处通用的图拿出来,
不过,这里我只给出断开连接时的状态转换图,摘自<The TCP/IP Guide>:
给出一个正常关闭时的windump信息:
14:00:38.819856 IP cd-zhangmin.1748 > 220.181.37.55.80: F 1:1(0) ack 1 win 65535
14:00:38.863989 IP 220.181.37.55.80 > cd-zhangmin.1748: F 1:1(0) ack 2 win 2920
14:00:38.864412 IP cd-zhangmin.1748 > 220.181.37.55.80: . ack 2 win 65535
补充细节:
关于以上的四次握手,我补充下细节:
1. 默认情况下(不改变socket选项),当你调用close( or closesocket,以下说close不再重复)时,如果
发送缓冲中还有数据,TCP会继续把数据发送完。
2. 发送了FIN只是表示这端不能继续发送数据(应用层不能再调用send发送),但是还可以接收数据。
3. 应用层如何知道对端关闭?通常,在最简单的阻塞模型中,当你调用recv时,如果返回0,则表示对端
关闭。在这个时候通常的做法就是也调用close,那么TCP层就发送FIN,继续完成四次握手。如果你不调用
close,那么对端就会处于FIN_WAIT_2状态,而本端则会处于CLOSE_WAIT状态。这个可以写代码试试。
4. 在很多时候,TCP连接的断开都会由TCP层自动进行,例如你CTRL+C终止你的程序,TCP连接依然会正常关
闭,你可以写代码试试。
特别的TIME_WAIT状态:
从以上TCP连接关闭的状态转换图可以看出,主动关闭的一方在发送完对对方FIN报文的确认(ACK)报文后,
会进入TIME_WAIT状态。TIME_WAIT状态也称为2MSL状态。
什么是2MSL?MSL即Maximum Segment Lifetime,也就是报文最大生存时间,引用<TCP/IP详解>中的话:“
它(MSL)是任何报文段被丢弃前在网络内的最长时间。”那么,2MSL也就是这个时间的2倍。其实我觉得没
必要把这个MSL的确切含义搞明白,你所需要明白的是,当TCP连接完成四个报文段的交换时,主动关闭的
一方将继续等待一定时间(2-4分钟),即使两端的应用程序结束。你可以写代码试试,然后用netstat查看下。
为什么需要2MSL?根据<TCP/IP详解>和<The TCP/IP Guide>中的说法,有两个原因:
其一,保证发送的ACK会成功发送到对方,如何保证?我觉得可能是通过超时计时器发送。这个就很难用
代码演示了。
其二,报文可能会被混淆,意思是说,其他时候的连接可能会被当作本次的连接。直接引用<The TCP/IP Guide>
的说法:The second is to provide a “buffering period” between the end of this connection
and any subsequent ones. If not for this period, it is possible that packets from different
connections could be mixed, creating confusion.
TIME_WAIT状态所带来的影响:
当某个连接的一端处于TIME_WAIT状态时,该连接将不能再被使用。事实上,对于我们比较有现实意义的
是,这个端口将不能再被使用。某个端口处于TIME_WAIT状态(其实应该是这个连接)时,这意味着这个TCP
连接并没有断开(完全断开),那么,如果你bind这个端口,就会失败。
对于服务器而言,如果服务器突然crash掉了,那么它将无法再2MSL内重新启动,因为bind会失败。解决这
个问题的一个方法就是设置socket的SO_REUSEADDR选项。这个选项意味着你可以重用一个地址。
对于TIME_WAIT的插曲:
当建立一个TCP连接时,服务器端会继续用原有端口监听,同时用这个端口与客户端通信。而客户端默认情况
下会使用一个随机端口与服务器端的监听端口通信。有时候,为了服务器端的安全性,我们需要对客户端进行
验证,即限定某个IP某个特定端口的客户端。客户端可以使用bind来使用特定的端口。
对于服务器端,当设置了SO_REUSEADDR选项时,它可以在2MSL内启动并listen成功。但是对于客户端,当使
用bind并设置SO_REUSEADDR时,如果在2MSL内启动,虽然bind会成功,但是在windows平台上connect会失败。
而在linux上则不存在这个问题。(我的实验平台:winxp, ubuntu7.10)
要解决windows平台的这个问题,可以设置SO_LINGER选项。SO_LINGER选项决定调用close时,TCP的行为。
SO_LINGER涉及到linger结构体,如果设置结构体中l_onoff为非0,l_linger为0,那么调用close时TCP连接
会立刻断开,TCP不会将发送缓冲中未发送的数据发送,而是立即发送一个RST报文给对方,这个时候TCP连
接就不会进入TIME_WAIT状态。
如你所见,这样做虽然解决了问题,但是并不安全。通过以上方式设置SO_LINGER状态,等同于设置SO_DONTLINGER
状态。
断开连接时的意外:
这个算不上断开连接时的意外,当TCP连接发生一些物理上的意外情况时,例如网线断开,linux上的TCP实现
会依然认为该连接有效,而windows则会在一定时间后返回错误信息。
这似乎可以通过设置SO_KEEPALIVE选项来解决,不过不知道这个选项是否对于所有平台都有效。
总结:
个人感觉,越写越烂。接下来会讲到TCP的数据发送,这会涉及到滑动窗口各种定时器之类的东西。我真诚
希望各位能够多提意见。对于TCP连接的断开,我们只要清楚:
1. 在默认情况下,调用close时TCP会继续将数据发送完毕;
2. TIME_WAIT状态会导致的问题;
3. 连接意外断开时可能会出现的问题。
4. maybe more...
本文转自:http://www.cppblog.com/kevinlynx/archive/2008/05/14/49825.html
posted @
2012-09-20 13:00 王海光 阅读(487) |
评论 (0) |
编辑 收藏
Author : Kevin Lynx
准备:
在这里本文将遵循上一篇文章的风格,只提TCP协议中的要点,这样我觉得可以更容易地掌握TCP。或者
根本谈不上掌握,对于这种纯理论的东西,即使你现在掌握了再多的细节,一段时间后也会淡忘。
在以后各种细节中,因为我们会涉及到分析一些TCP中的数据报,因此一个协议包截获工具必不可少。在
<TCP/IP详解>中一直使用tcpdump。这里因为我的系统是windows,所以只好使用windows平台的tcpdump,
也就是WinDump。在使用WinDump之前,你需要安装该程序使用的库WinpCap。
关于WinDump的具体用法你可以从网上其他地方获取,这里我只稍微提一下。要让WinDump开始监听数据,
首先需要确定让其监听哪一个网络设备(或者说是网络接口)。你可以:
windump -D
获取当前机器上的网络接口。然后使用:
windump -i 2
开始对网络接口2的数据监听。windump如同tcpdump(其实就是tcpdump)一样支持过滤表达式,windump
将会根据你提供的过滤表达式过滤不需要的网络数据包,例如:
windump -i 2 port 4000
那么windump只会显示端口号为4000的网络数据。
序号和确认号:
要讲解TCP的建立过程,也就是那个所谓的三次握手,就会涉及到序号和确认号这两个东西。翻书到TCP
的报文头,有两个很重要的域(都是32位)就是序号域和确认号域。可能有些同学会对TCP那个报文头有所
疑惑(能看懂我在讲什么的会产生这样的疑惑么?),这里我可以告诉你,你可以假想TCP的报文头就是个
C语言结构体(假想而已,去翻翻bsd对TCP的实现,肯定没这么简单),那么大致上,所谓的TCP报文头就是:
typedef struct _tcp_header
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 16位源端口号
unsigned short src_port;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 16位目的端口号
unsigned short dst_port;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 32位序号
unsigned long seq_num;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 32位确认号
unsigned long ack_num;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 16位标志位[4位首部长度,保留6位,ACK、SYN之类的标志位]
unsigned short flag;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 16位窗口大小
unsigned short win_size;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 16位校验和
short crc_sum;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 16位紧急指针
short ptr;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//// 可选选项
/// how to implement this ?
} tcp_header;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
那么,这个序号和确认号是什么?TCP报文为每一个字节都设置一个序号,觉得很奇怪?这里并不是为每一
字节附加一个序号(那会是多么可笑的编程手法?),而是为一个TCP报文附加一个序号,这个序号表示报文
中数据的第一个字节的序号,而其他数据则是根据离第一个数据的偏移来决定序号的,例如,现在有数据:
abcd。如果这段数据的序号为1200,那么a的序号就是1200,b的序号就是1201。而TCP发送的下一个数据包
的序号就会是上一个数据包最后一个字节的序号加一。例如efghi是abcd的下一个数据包,那么它的序号就
是1204。通过这种看似简单的方法,TCP就实现了为每一个字节设置序号的功能(终于明白为什么书上要告诉
我们‘为每一个字节设置一个序号’了吧?)。注意,设置序号是一种可以让TCP成为’可靠协议‘的手段。
TCP中各种乱七八糟的东西都是有目的的,大部分目的还是为了’可靠‘两个字。别把TCP看高深了,如果
让你来设计一个网络协议,目的需要告诉你是’可靠的‘,你就会明白为什么会产生那些乱七八糟的东西了。
接着看,确认号是什么?因为TCP会对接收到的数据包进行确认,发送确认数据包时,就会设置这个确认号,
确认号通常表示接收方希望接收到的下一段报文的序号。例如某一次接收方收到序号为1200的4字节数举报,
那么它发送确认报文给发送方时,就会设置确认号为1204。
大部分书上在讲确认号和序号时,都会说确认号是序号加一。这其实有点误解人,所以我才在这里废话了
半天(高手宽容下:D)。
开始三次握手:
如果你还不会简单的tcp socket编程,我建议你先去学学,这就好比你不会C++基本语法,就别去研究vtable
之类。
三次握手开始于客户端试图连接服务器端。当你调用诸如connect的函数时,正常情况下就会开始三次握手。
随便在网上找张三次握手的图:
如前文所述,三次握手也就是产生了三个数据包。客户端主动连接,发送SYN被设置了的报文(注意序号和
确认号,因为这里不包含用户数据,所以序号和确认号就是加一减一的关系)。服务器端收到该报文时,正
常情况下就发送SYN和ACK被设置了的报文作为确认,以及告诉客户端:我想打开我这边的连接(双工)。客户
端于是再对服务器端的SYN进行确认,于是再发送ACK报文。然后连接建立完毕。对于阻塞式socket而言,你
的connect可能就返回成功给你。
在进行了铺天盖地的罗利巴索的基础概念的讲解后,看看这个连接建立的过程,是不是简单得几近无聊?
我们来实际点,写个最简单的客户端代码:
sockaddr_in addr;
memset( &addr, 0, sizeof( addr ) );
addr.sin_family = AF_INET;
addr.sin_port = htons( 80 );
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//// 220.181.37.55
addr.sin_addr.s_addr = inet_addr( "220.181.37.55" );
printf( "%s : connecting to server.\n", _str_time() );
int err = connect( s, (sockaddr*) &addr, sizeof( addr ) );
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
主要就是connect。运行程序前我们运行windump:
windump -i 2 host 220.181.37.55
00:38:22.979229 IP noname.domain.4397 > 220.181.37.55.80: S 2523219966:2523219966(0) win 65535 <mss 1460,nop,nop,sackOK>
00:38:23.024254 IP 220.181.37.55.80 > noname.domain.4397: S 1277008647:1277008647(0) ack 2523219967 win 2920 <mss 1440,nop,nop,sackOK>
00:38:23.024338 IP noname.domain.4397 > 220.181.37.55.80: . ack 1 win 65535
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
如何分析windump的结果,建议参看<tcp/ip详解>中对于tcpdump的描述。
建立连接的附加信息:
虽然SYN、ACK之类的报文没有用户数据,但是TCP还是附加了其他信息。最为重要的就是附加的MSS值。这个
可以被协商的MSS值基本上就只在建立连接时协商。如以上数据表示,MSS为1460字节。
连接的意外:
连接的意外我大致分为两种情况(也许还有更多情况):目的主机不可达、目的主机并没有在指定端口监听。
当目的主机不可达时,也就是说,SYN报文段根本无法到达对方(如果你的机器根本没插网线,你就不可达),
那么TCP收不到任何回复报文。这个时候,你会看到TCP中的定时器机制出现了。TCP对发出的SYN报文进行
计时,当在指定时间内没有得到回复报文时,TCP就会重传刚才的SYN报文。通常,各种不同的TCP实现对于
这个超时值都不同,但是据我观察,重传次数基本上都是3次。例如,我连接一个不可达的主机:
12:39:50.560690 IP cd-zhangmin.1573 > 220.181.37.55.1024: S 3117975575:3117975575(0) win 65535 <mss 1460,nop,nop,sackOK>
12:39:53.538734 IP cd-zhangmin.1573 > 220.181.37.55.1024: S 3117975575:3117975575(0) win 65535 <mss 1460,nop,nop,sackOK>
12:39:59.663726 IP cd-zhangmin.1573 > 220.181.37.55.1024: S 3117975575:3117975575(0) win 65535 <mss 1460,nop,nop,sackOK>
发出了三个序号一样的SYN报文,但是没有得到一个回复报文(废话)。每一个SYN报文之间的间隔时间都是
有规律的,在windows上是3秒6秒9秒12秒。上面的数据你看不到12秒这个数据,因为这是第三个报文发出的
时间和connect返回错误信息时的时间之差。另一方面,如果连接同一个网络,这个间隔时间又不同。例如
直接连局域网,间隔时间就差不多为500ms。
(我强烈建议你能运行windump去试验这里提到的每一个现象,如果你在ubuntu下使用tcpdump,记住sudo :D)
出现意外的第二种情况是如果主机数据包可达,但是试图连接的端口根本没有监听,那么发送SYN报文的这
方会收到RST被设置的报文(connect也会返回相应的信息给你),例如:
13:37:22.202532 IP cd-zhangmin.1658 > 7AURORA-CCTEST.7100: S 2417354281:2417354281(0) win 65535 <mss 1460,nop,nop,sackOK>
13:37:22.202627 IP 7AURORA-CCTEST.7100 > cd-zhangmin.1658: R 0:0(0) ack 2417354282 win 0
13:37:22.711415 IP cd-zhangmin.1658 > 7AURORA-CCTEST.7100: S 2417354281:2417354281(0) win 65535 <mss 1460,nop,nop,sackOK>
13:37:22.711498 IP 7AURORA-CCTEST.7100 > cd-zhangmin.1658: R 0:0(0) ack 1 win 0
13:37:23.367733 IP cd-zhangmin.1658 > 7AURORA-CCTEST.7100: S 2417354281:2417354281(0) win 65535 <mss 1460,nop,nop,sackOK>
13:37:23.367826 IP 7AURORA-CCTEST.7100 > cd-zhangmin.1658: R 0:0(0) ack 1 win 0
可以看出,7AURORA-CCTEST.7100返回了RST报文给我,但是我这边根本不在乎这个报文,继续发送SYN报文。
三次过后connect就返回了。(数据反映的事实是这样)
关于listen:
TCP服务器端会维护一个新连接的队列。当新连接上的客户端三次握手完成时,就会将其放入这个队列。这个队
列的大小是通过listen设置的。当这个队列满时,如果有新的客户端试图连接(发送SYN),服务器端丢弃报文,
同时不做任何回复。
总结:
TCP连接的建立的相关要点就是这些(or more?)。正常情况下就是三次握手,非正常情况下就是SYN三次超时,
以及收到RST报文却被忽略。
本文转自:http://www.cppblog.com/kevinlynx/archive/2008/05/11/49482.html
posted @
2012-09-20 12:56 王海光 阅读(401) |
评论 (0) |
编辑 收藏
摘要: 考虑一下多线程代码,在设计上,App为了获取更多的功能,从Window派生,而App同时为了获取某个模块的回调(所谓的Listener),App同时派生Listener,并将自己的指针交给另一个模块,另一个模块通过该指针多态回调到App的实现(对Listener规定的接口的implemention)。设计上只是一个很简单的Listener回调,在单线程模式下一切都很正常(后面我会罗列代码),但是换...
阅读全文
posted @
2012-09-14 16:16 王海光 阅读(694) |
评论 (0) |
编辑 收藏