Shell脚本经典之Fork炸弹

Posted by 夏泽民

众所周知,bash是一款极其强大的shell,提供了强大的交互与编程功能。这样的一款shell中自然不会缺少“函数”这个元素来帮助程序进行模块化的高效开发与管理。于是产生了由于其特殊的特性,bash拥有了fork炸弹。Jaromil在2002年设计了最为精简的一个fork炸弹的实现。



fork

Posted by 夏泽民

一、fork入门知识一个进程,包括代码、数据和分配给进程的资源。fork()函数通过系统调用创建一个与原来进程几乎完全相同的进程,也就是两个进程可以做完全相同的事,但如果初始参数或者传入的变量不同,两个进程也可以做不同的事。 一个进程调用fork()函数后,系统先给新的进程分配资源,例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的新进程中,只有少数值与原来的进程的值不同。相当于克隆了一个自己。 我们来看一个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 
*  fork_test.c 
*  version 1 
*/  
#include <unistd.h>  
#include <stdio.h>   
int main ()   
{   
pid_t fpid; //fpid表示fork函数返回的值  
int count=0;  
fpid=fork();   
if (fpid < 0)   
printf("error in fork!");   
else if (fpid == 0) {  
printf("i am the child process, my process id is %d/n",getpid());   
printf("我是爹的儿子/n");//对某些人来说中文看着更直白。  
count++;  
}  
else {  
printf("i am the parent process, my process id is %d/n",getpid());   
printf("我是孩子他爹/n");  
count++;  
}  
printf("统计结果是: %d/n",count);  
return 0;  
}  

运行结果是: i am the child process, my process id is 5574 我是爹的儿子 统计结果是: 1 i am the parent process, my process id is 5573 我是孩子他爹 统计结果是: 1 在语句fpid=fork()之前,只有一个进程在执行这段代码,但在这条语句之后,就变成两个进程在执行了,这两个进程的几乎完全相同,将要执行的下一条语句都是if(fpid<0)…… 为什么两个进程的fpid不同呢,这与fork函数的特性有关。fork调用的一个奇妙之处就是它仅仅被调用一次,却能够返回两次,它可能有三种不同的返回值: 1)在父进程中,fork返回新创建子进程的进程ID; 2)在子进程中,fork返回0; 3)如果出现错误,fork返回一个负值; 在fork函数执行完毕后,如果创建新进程成功,则出现两个进程,一个是子进程,一个是父进程。在子进程中,fork函数返回0,在父进程中,fork返回新创建子进程的进程ID。我们可以通过fork返回的值来判断当前进程是子进程还是父进程。引用一位网友的话来解释fpid的值为什么在父子进程中不同。“其实就相当于链表,进程形成了链表,父进程的fpid(p 意味point)指向子进程的进程id, 因为子进程没有子进程,所以其fpid为0. fork出错可能有两种原因: 1)当前的进程数已经达到了系统规定的上限,这时errno的值被设置为EAGAIN。 2)系统内存不足,这时errno的值被设置为ENOMEM。 创建新进程成功后,系统中出现两个基本完全相同的进程,这两个进程执行没有固定的先后顺序,哪个进程先执行要看系统的进程调度策略。 每个进程都有一个独特(互不相同)的进程标识符(process ID),可以通过getpid()函数获得,还有一个记录父进程pid的变量,可以通过getppid()函数获得变量的值。 fork执行完毕后,出现两个进程, 有人说两个进程的内容完全一样啊,怎么打印的结果不一样啊,那是因为判断条件的原因,上面列举的只是进程的代码和指令,还有变量啊。 执行完fork后,进程1的变量为count=0,fpid!=0(父进程)。进程2的变量为count=0,fpid=0(子进程),这两个进程的变量都是独立的,存在不同的地址中,不是共用的,这点要注意。可以说,我们就是通过fpid来识别和操作父子进程的。 还有人可能疑惑为什么不是从#include处开始复制代码的,这是因为fork是把进程当前的情况拷贝一份,执行fork时,进程已经执行完了int count=0;fork只拷贝下一个要执行的代码到新的进程。二、fork进阶知识先看一份代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
*  fork_test.c 
*  version 2 
*/  
#include <unistd.h>  
#include <stdio.h>  
int main(void)  
{  
int i=0;  
printf("i son/pa ppid pid  fpid/n");  
//ppid指当前进程的父进程pid  
//pid指当前进程的pid,  
//fpid指fork返回给当前进程的值  
for(i=0;i<2;i++){  
pid_t fpid=fork();  
if(fpid==0)  
printf("%d child  %4d %4d %4d/n",i,getppid(),getpid(),fpid);  
else  
printf("%d parent %4d %4d %4d/n",i,getppid(),getpid(),fpid);  
}  
return 0;  
}  

运行结果是: i son/pa ppid pid fpid 0 parent 2043 3224 3225 0 child 3224 3225 0 1 parent 2043 3224 3226 1 parent 3224 3225 3227 1 child 1 3227 0 1 child 1 3226 0 这份代码比较有意思,我们来认真分析一下: 第一步:在父进程中,指令执行到for循环中,i=0,接着执行fork,fork执行完后,系统中出现两个进程,分别是p3224和p3225(后面我都用pxxxx表示进程id为xxxx的进程)。可以看到父进程p3224的父进程是p2043,子进程p3225的父进程正好是p3224。我们用一个链表来表示这个关系: p2043->p3224->p3225 第一次fork后,p3224(父进程)的变量为i=0,fpid=3225(fork函数在父进程中返向子进程id),代码内容为:

1
2
3
4
5
6
7
8
for(i=0;i<2;i++){  
pid_t fpid=fork();//执行完毕,i=0,fpid=3225  
if(fpid==0)  
printf("%d child  %4d %4d %4d/n",i,getppid(),getpid(),fpid);  
else  
printf("%d parent %4d %4d %4d/n",i,getppid(),getpid(),fpid);  
}  
return 0;  

p3225(子进程)的变量为i=0,fpid=0(fork函数在子进程中返回0),代码内容为:

1
2
3
4
5
6
7
8
for(i=0;i<2;i++){  
pid_t fpid=fork();//执行完毕,i=0,fpid=0  
if(fpid==0)  
printf("%d child  %4d %4d %4d/n",i,getppid(),getpid(),fpid);  
else  
printf("%d parent %4d %4d %4d/n",i,getppid(),getpid(),fpid);  
}  
return 0;  

所以打印出结果: 0 parent 2043 3224 3225 0 child 3224 3225 0 第二步:假设父进程p3224先执行,当进入下一个循环时,i=1,接着执行fork,系统中又新增一个进程p3226,对于此时的父进程,p2043->p3224(当前进程)->p3226(被创建的子进程)。 对于子进程p3225,执行完第一次循环后,i=1,接着执行fork,系统中新增一个进程p3227,对于此进程,p3224->p3225(当前进程)->p3227(被创建的子进程)。从输出可以看到p3225原来是p3224的子进程,现在变成p3227的父进程。父子是相对的,这个大家应该容易理解。只要当前进程执行了fork,该进程就变成了父进程了,就打印出了parent。 所以打印出结果是: 1 parent 2043 3224 3226 1 parent 3224 3225 3227 第三步:第二步创建了两个进程p3226,p3227,这两个进程执行完printf函数后就结束了,因为这两个进程无法进入第三次循环,无法fork,该执行return 0;了,其他进程也是如此。 以下是p3226,p3227打印出的结果: 1 child 1 3227 0 1 child 1 3226 0 细心的读者可能注意到p3226,p3227的父进程难道不该是p3224和p3225吗,怎么会是1呢?这里得讲到进程的创建和死亡的过程,在p3224和p3225执行完第二个循环后,main函数就该退出了,也即进程该死亡了,因为它已经做完所有事情了。p3224和p3225死亡后,p3226,p3227就没有父进程了,这在操作系统是不被允许的,所以p3226,p3227的父进程就被置为p1了,p1是永远不会死亡的,至于为什么,这里先不介绍,留到“三、fork高阶知识”讲。 总结一下,这个程序执行的流程如下:这个程序最终产生了3个子进程,执行过6次printf()函数。 我们再来看一份代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
*  fork_test.c 
*  version 3 
*/  
#include <unistd.h>  
#include <stdio.h>  
int main(void)  
{  
int i=0;  
for(i=0;i<3;i++){  
pid_t fpid=fork();  
if(fpid==0)  
printf("son/n");  
else  
printf("father/n");  
}  
return 0;  }

它的执行结果是: father son father father father father son son father son son son father son 这里就不做详细解释了,只做一个大概的分析。 for i=0 1 2 father father father son son father son son father father son son father son 其中每一行分别代表一个进程的运行打印结果。 总结一下规律,对于这种N次循环的情况,执行printf函数的次数为2(1+2+4+……+2N-1)次,创建的子进程数为1+2+4+……+2N-1个。(感谢gao_jiawei网友指出的错误,原本我的结论是“执行printf函数的次数为2(1+2+4+……+2N)次,创建的子进程数为1+2+4+……+2N ”,这是错的) 网上有人说N次循环产生2*(1+2+4+……+2N)个进程,这个说法是不对的,希望大家需要注意。数学推理见http://202.117.3.13/wordpress/?p=81(该博文的最后)。 同时,大家如果想测一下一个程序中到底创建了几个子进程,最好的方法就是调用printf函数打印该进程的pid,也即调用printf(“%d/n”,getpid());或者通过printf(“+/n”);来判断产生了几个进程。有人想通过调用printf(“+”);来统计创建了几个进程,这是不妥当的。具体原因我来分析。 老规矩,大家看一下下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 
*  fork_test.c 
*  version 4
*/  
#include <unistd.h>  
#include <stdio.h>  
int main() {  
pid_t fpid;//fpid表示fork函数返回的值  
//printf("fork!");  
printf("fork!/n");  
fpid = fork();  
if (fpid < 0)  
printf("error in fork!");  
else if (fpid == 0)  
printf("I am the child process, my process id is %d/n", getpid());  
else  
printf("I am the parent process, my process id is %d/n", getpid());  
return 0;  
}  

执行结果如下: fork! I am the parent process, my process id is 3361 I am the child process, my process id is 3362 如果把语句printf(“fork!/n”);注释掉,执行printf(“fork!”); 则新的程序的执行结果是: fork!I am the parent process, my process id is 3298 fork!I am the child process, my process id is 3299 程序的唯一的区别就在于一个/n回车符号,为什么结果会相差这么大呢? 这就跟printf的缓冲机制有关了,printf某些内容时,操作系统仅仅是把该内容放到了stdout的缓冲队列里了,并没有实际的写到屏幕上。但是,只要看到有/n 则会立即刷新stdout,因此就马上能够打印了。 运行了printf(“fork!”)后,“fork!”仅仅被放到了缓冲里,程序运行到fork时缓冲里面的“fork!” 被子进程复制过去了。因此在子进程度stdout缓冲里面就也有了fork! 。所以,你最终看到的会是fork! 被printf了2次!!!! 而运行printf(“fork! /n”)后,“fork!”被立即打印到了屏幕上,之后fork到的子进程里的stdout缓冲里不会有fork! 内容。因此你看到的结果会是fork! 被printf了1次!!!! 所以说printf(“+”);不能正确地反应进程的数量。 大家看了这么多可能有点疲倦吧,不过我还得贴最后一份代码来进一步分析fork函数。

1
2
3
4
5
6
7
8
9
10
 
#include <stdio.h>  
#include <unistd.h>  
int main(int argc, char* argv[])  
{  
fork();  
fork() && fork() || fork();  
fork();  
return 0;  
}  

问题是不算main这个进程自身,程序到底创建了多少个进程。 为了解答这个问题,我们先做一下弊,先用程序验证一下,到此有多少个进程。 [c-sharp] view plain copy #include int main(int argc, char* argv[]) { fork(); fork() && fork() || fork(); fork(); printf("+/n"); } 答案是总共20个进程,除去main进程,还有19个进程。 我们再来仔细分析一下,为什么是还有19个进程。 第一个fork和最后一个fork肯定是会执行的。 主要在中间3个fork上,可以画一个图进行描述。 这里就需要注意&&和||运算符。 A&&B,如果A=0,就没有必要继续执行&&B了;A非0,就需要继续执行&&B。 A||B,如果A非0,就没有必要继续执行||B了,A=0,就需要继续执行||B。 fork()对于父进程和子进程的返回值是不同的,按照上面的A&&B和A||B的分支进行画图,可以得出5个分支。加上前面的fork和最后的fork,总共4*5=20个进程,除去main主进程,就是19个进程了。一、fork()函数 在操作系统的基本概念中进程是程序的一次执行,且是拥有资源的最小单位和调度单位(在引入线程的操作系统中,线程是最小的调度单位)。在Linux系统中创建进程有两种方式:一是由操作系统创建,二是由父进程创建进程(通常为子进程)。系统调用函数fork()是创建一个新进程的唯一方式,当然vfork()也可以创建进程,但是实际上其还是调用了fork()函数。fork()函数是Linux系统中一个比较特殊的函数,其一次调用会有两个返回值,下面是fork()函数的声明: #include // On success, The PID of the process is returned in the parent, and 0 is returned in the child. On failure, // -1 is returned in the parent, no child process is created, and errno is set appropriately. pid_t fork (void);当程序调用fork()函数并返回成功之后,程序就将变成两个进程,调用fork()者为父进程,后来生成者为子进程。这两个进程将执行相同的程序文本,但却各自拥有不同的栈段、数据段以及堆栈拷贝。子进程的栈、数据以及栈段开始时是父进程内存相应各部分的完全拷贝,因此它们互不影响。从性能方面考虑,父进程到子进程的数据拷贝并不是创建时就拷贝了的,而是采用了写时拷贝(copy-on -write)技术来处理。调用fork()之后,父进程与子进程的执行顺序是我们无法确定的(即调度进程使用CPU),意识到这一点极为重要,因为在一些设计不好的程序中会导致资源竞争,从而出现不可预知的问题。下图为写时拷贝技术处理前后的示意图: 在Linux系统中,常常存在许多对文件的操作,fork()的执行将会对文件操作带来一些小麻烦。由于子进程会将父进程的大多数数据拷贝一份,这样在文件操作中就意味着子进程会获得父进程所有文件描述符的副本,这些副本的创建方式类似于dup()函数调用,因此父、子进程中对应的文件描述符均指向相同的打开的文件句柄,而且打开的文件句柄包含着当前文件的偏移量以及文件状态标志,所以在父子进程中处理文件时要考虑这种情况,以避免文件内容出现混乱或者别的问题。下图为执行fork()调用后文件描述符的相关处理及其变化:二、线程 与进程类似,线程(thread)是允许应用程序并发执行多个任务的一种机制。一个进程中可以包含多个线程,同一个程序中的所有线程均会独立执行,且共享同一份全局内存区域,其中包括初始化数据段(initialized data),未初始化数据段(uninitialized data),以及堆内存段(heap segment)。在多处理器环境下,多个线程可以同时执行,如果线程数超过了CPU的个数,那么每个线程的执行顺序将是无法确定的,因此对于一些全局共享数据据需要使用同步机制来确保其的正确性。 在系统中,线程也是稀缺资源,一个进程能同时创建多少个线程这取决于地址空间的大小和内核参数,一台机器可以同时并发运行多少个线程也受限于CPU的数目。在进行程序设计时,我们应该精心规划线程的个数,特别是根据机器CPU的数目来设置工作线程的数目,并为关键任务保留足够的计算资源。如果你设计的程序在背地里启动了额外的线程来执行任务,那这也属于资源规划漏算的情况,从而影响关键任务的执行,最终导致无法达到预期的性能。很多程序中都存在全局对象,这些全局对象的初始化工作都是在进入main()函数之前进行的,为了能保证全局对象的安全初始化(按顺序的),因此在程序进入main()函数之前应该避免线程的创建,从而杜绝未知错误的发生。三、fork()与多线程 在程序中fork()与多线程的协作性很差,这是POSIX系列操作系统的历史包袱。因为长期以来程序都是单线程的,fork()运转正常。当20世纪90年代初期引入线程之后,fork()的适用范围就大为缩小了。 在多线程执行的情况下调用fork()函数,仅会将发起调用的线程复制到子进程中。(子进程中该线程的ID与父进程中发起fork()调用的线程ID是一样的,因此,线程ID相同的情况有时我们需要做特殊的处理。)也就是说不能同时创建出于父进程一样多线程的子进程。其他线程均在子进程中立即停止并消失,并且不会为这些线程调用清理函数以及针对线程局部存储变量的析构函数。这将导致下列一些问题:

  1. 虽然只将发起fork()调用的线程复制到子进程中,但全局变量的状态以及所有的pthreads对象(如互斥量、条件变量等)都会在子进程中得以保留,这就造成一个危险的局面。例如:一个线程在fork()被调用前锁定了某个互斥量,且对某个全局变量的更新也做到了一半,此时fork()被调用,所有数据及状态被拷贝到子进程中,那么子进程中对该互斥量就无法解锁(因为其并非该互斥量的属主),如果再试图锁定该互斥量就会导致死锁,这是多线程编程中最不愿意看到的情况。同时,全局变量的状态也可能处于不一致的状态,因为对其更新的操作只做到了一半对应的线程就消失了。fork()函数被调用之后,子进程就相当于处于signal handler之中,此时就不能调用线程安全的函数(用锁机制实现安全的函数),除非函数是可重入的,而只能调用异步信号安全(async-signal-safe)的函数。fork()之后,子进程不能调用: malloc(3)。因为malloc()在访问全局状态时会加锁。 任何可能分配或释放内存的函数,包括new、map::insert()、snprintf() …… 任何pthreads函数。你不能用pthread_cond_signal()去通知父进程,只能通过读写pipe(2)来同步。 printf()系列函数,因为其他线程可能恰好持有stdout/stderr的锁。 除了man 7 signal中明确列出的“signal安全”函数之外的任何函数。
  2. 因为并未执行清理函数和针对线程局部存储数据的析构函数,所以多线程情况下可能会导致子进程的内存泄露。另外,子进程中的线程可能无法访问(父进程中)由其他线程所创建的线程局部存储变量,因为(子进程)没有任何相应的引用指针。由于这些问题,推荐在多线程程序中调用fork()的唯一情况是:其后立即调用exec()函数执行另一个程序,彻底隔断子进程与父进程的关系。由新的进程覆盖掉原有的内存,使得子进程中的所有pthreads对象消失。 对于那些必须执行fork(),而其后又无exec()紧随其后的程序来说,pthreads API提供了一种机制:fork()处理函数。利用函数pthread_atfork()来创建fork()处理函数。当一个多线程程序 fork(2) 之后 fork(2) 程序 创建了当前进程的副本,包括所有的内存页,还有打开文件的句柄等。所有这些工作对于一个 UNIX 程序员来说,都不陌生。子进程和父进程之间一个非常重要的区别是,子进程只有一个线程。 一个程序员也许不希望复制包括所有线程在内的整个进程,而且,这也容易出问题。想想:所有的线程都因为一个系统调用(这里指的是 fork(2))而被暂停(Suspended)。所以,fork(2) 仅仅会复制调用它的那个线程。那么(当前的实现方式)会遇到什么问题呢?关键部分,互斥锁(mutex) 这种做法一个潜在的问题是,当 fork(2) 被调用的时候,某些线程可以正在执行关键部分的代码,在互斥锁的保护下对数据进行非原子操作。在子进程里,这些线程消失了,只留下一些修改到一半却没有可能“修正”的数据,不可能去确定 “其他线程正在做什么”和“怎么做可以保持数据一致”。此外,那些(复制过来的互斥锁)的状态是未定义,他们也许不能用(unusable),除非子进程调用 pthread_mutex_init() 去重置他们的状态为一个可用的值。它( pthread_mutex_init() )的实现取决于互斥锁在 fork(2) 执行之后的具体行为。在我的 Linux 机器上,被锁定(locked)的互斥锁的状态(重置之后)在子进程中仍是(locked)。库函数 上面关于互斥锁和关键代码的问题,又引出了另一个潜在的问题。理论上,写一些在多线程上运行并且在调用 fork(2) 之后不会出错的代码,是可行的。但是,实践中,却有一个问题──库函数。你不能确认你正在用的库函数不会使用到全局数据。即使它(用到的库函数)是线程安全的,它也可能是通过在内部使用互斥锁来达到目的。你永远无法确认。即使系统的线程安全的库函数,也可能使用了互斥锁。一个潜在的例子是,malloc() 函数,至少在我的多线程程序里,内部使用了锁。所以,在其他线程调用 malloc() 的时候调用 fork(2) 是不安全的!一般来说,我们应该怎么做呢?在一个多线程程序调用 fork(2) 之后,你只应该调用异步安全(async-safe)的函数(在signal(7) http://www.kernel.org/doc/man-pages/online/pages/man7/signal.7.html 列出)。这个列表与你在一个消息回调函数(signal hanlder)里面可以调用的函数的列表是相似的,而原因也相似:在两种情况下,在调用一个函数时,线程会被终止(原文为带引号的interrupted,由于该线程在新的子进程里已经不存在,所以翻译为终止)。这里是几个在我的系统里,使用类内部锁的函数,仅仅是想让你知道,几乎没有东西是安全的:* malloc()* stdio的函数,比如printf() - 这是标准要求的* syslog()execve() 和文件句柄 似乎使用 execve(2) 来启动一个需要调用fork(2)的多线程程序,是你唯一明智的选择。但即使这样做,也还有一点不足。当调用execve(2) 时,需要注意的是,打开的文件句柄还将维持打开的状态(在新的子进程中 —— 译者Xorcerer),可以继续被读取和写入数据。你在调用 execve(2) 之前打开了一个你不希望在新的子进程里被使用的文件,问题就出现了。这甚至会产生安全方便的问题。对此,有一个解决方案,你必须使用 fcntl(2) 来对每一个打开的文件句柄设施 FD_CLOEXEC 标记,这样,它们会在新的进程中被自动关闭。不幸的是,在多线程程序里,这没那么简单。当我们使用 fcntl(2) 去设置 FD_CLOEXEC 时,会有一个间隙: fd = open (“file”, O_RDWR | O_CREAT | O_TRUNC,0600); if(fd <0){
    perror (“open()”); return0;
    } fcntl (fd, F_SETFD, FD_CLOEXEC);
    如果另一个线程正好在当前线程执行 open(2) 之后 fcntl(2) 之前调用 fork(2) 和 execve(2) ,那么得到的新进程将获得这个文件句柄的副本。这不是我们想要的。一个解决方案已经随着新标准(如:POSIX.1-2008)和新的 Linux 内核(2.6.23以及之后的版本)到来了。我们现在可以在 open(2) 使用 O_CLOEXEC 标记,所以,“开打文件与设置 FD_CLOEXEC” 已经成为了一个原子操作。除了使用 open(2) 之外,还有其他的创建文件句柄的方法:使用 dup(2) 复制它们,使用 socket(2) 创建socket,等。所有这些函数现在都有一个相似的标记如O_CLOEXEC或者其他更新的版本(其中某些函数,如dup2(2)没有一个用于标记位的参数,所以dup3(2)为此产生了)。值得提到的一点是同样的东西在单线程程序里也可能发生,如果它在同一个消息处理函数(singal handler)中使用 fork(2) 和 execve(2) 。这个操作是完全合法的,因为这两个函数是异步安全并且允许在消息处理函数中被调用,但是问题是这个程序也许会在调用 open(2) 和 fcntl(2) 之间时,被中断。想知道更多关于设置 FD_CLOEXEC 新API的信息,请参考 《Ulrich Drepper’s blog: Secure File Descriptor Handling》。一个有用的系统函数:pthread_atfork() 其中一个尝试解决多线程程序中使用 fork(2) 的问题的函数是 pthread_atfork()。它拥有如下原型: int pthread_atfork(void (prepare)(void), void (parent)(void), void (*child)(void)); 它允许指定在 fork 被调用时的处理函数:prepare 新进程产生之前被调用。 parent 新进程产生之后在父进程被调用。 child 新进程产生之后,在子进程被调用。 调用的目的是在 fork(2) 被调用时,处理多线程程序的关键部分(本文开始部分提及)。一个常见的场景时在 prepare 处理函数中加锁,在 parent 处理函数解锁和在 child 处理函数重新初始化锁。


Linux进程控制——exec函数族

Posted by 夏泽民

在Linux中,并不存在exec()函数,exec指的是一组函数,一共有6个,分别是: #include extern char **environ; int execl(const char *path, const char *arg, ...); int execlp(const char *file, const char *arg, ...); int execle(const char *path, const char *arg, ..., char * const envp[]); int execv(const char *path, char *const argv[]); int execvp(const char *file, char *const argv[]); int execve(const char *path, char *const argv[], char *const envp[]); 其中只有execve是真正意义上的系统调用,其它都是在此基础上经过包装的库函数。 exec函数族的作用是根据指定的文件名找到可执行文件,并用它来取代调用进程的内容,换句话说,就是在调用进程内部执行一个可执行文件。这里的可执行文件既可以是二进制文件,也可以是任何Linux下可执行的脚本文件。 函数名与参数的关系: 细看一下,这6个函数都是以exec开头(表示属于exec函数组),前3个函数接着字母l的,后3个接着字母v的,我的理解是l表示list(列举参数),v表示vector(参数向量表) 。它们的区别在于,execv开头的函数是以"char *argv[]"(vector)形式传递命令行参数,而execl开头的函数采用了罗列(list)的方式,把参数一个一个列出来,然后以一个NULL表示结束。这里的NULL的作用和argv数组里的NULL作用是一样的。 字母p是指在环境变量PATH的目录里去查找要执行的可执行文件。2个以p结尾的函数execlp和execvp,看起来,和execl与execv的差别很小,事实也如此,它们的区别从第一个参数名可以看出:除 execlp和execvp之外的4个函数都要求,它们的第1个参数path必须是一个完整的路径,如"/bin/ls";而execlp和execvp 的第1个参数file可以仅仅只是一个文件名,如"ls",这两个函数可以自动到环境变量PATH指定的目录里去查找。 字母e是指给可执行文件指定环境变量。在全部6个函数中,只有execle和execve使用了char *envp[]传递环境变量,其它的4个函数都没有这个参数,这并不意味着它们不传递环境变量,这4个函数将把默认的环境变量不做任何修改地传给被执行的应用程序。而execle和execve用指定的环境变量去替代默认的那些。 返回值 与一般情况不同,exec函数族的函数执行成功后不会返回,因为调用进程的实体,包括代码段,数据段和堆栈等都已经被新的内容取代,只有进程ID等一些表面上的信息仍保持原样。调用失败时,会设置errno并返回-1,然后从原程序的调用点接着往下执行。 与其他系统调用比起来,exec很容易失败,被执行文件的位置,权限等很多因素都能导致调用失败。因此,使用exec函数族时,一定要加错误判断语句。最常见的错误: 找不到文件或路径,此时errno被设置为ENOENT; 数组argv和envp忘记用NULL结束,此时errno被设置为EFAULT; 没有对要执行文件的运行权限,此时errno被设置为EACCES。 2、应用 如果一个进程想执行另一个程序,它就可以fork或vfork出一个新进程,然后调用任何一个exec函数。 为此,Linux还专门对fork作了优化:通常fork会将调用进程的所有内容原封不动的拷贝到新产生的子进程中去,这些拷贝的动作很消耗时 间,而如果fork完之后我们马上就调用exec,那这些辛辛苦苦拷贝来的东西就会被立刻抹掉,这看起来非常不划算,于是人们设计了一种"写时复制(copy-on-write)" 技术,使得fork结束后并不立刻复制父进程的内容到子进程,而是到了真正使用时才复制,这样如果下一条语句是exec,它就不会作无用功了。其实"写时 复制"还是有复制,进程的mm结构、页表都还是被复制了("写时复制"也必须由这些信息来支撑。否则内核捕捉到CPU访存异常,怎么区分 这是“写时复制”引起的,还是真正的越权访问呢?)。 而vfork就把事情做绝了,所有有关于内存的东西都不复制了,父子进程的内存是完全共享的。 但是这样一来又有问题了,虽然用户程序可以设计很多方法来避免父子进程间的访存冲突。但是关键的一点,父子进程共用着栈,这可不由用户程序控制的。一个进 程进行了关于函数调用或返回的操作,则另一个进程的调用栈 (实际上就是同一个栈)也被影响了。这样的程序没法运行下去。所以,vfork有个限制,子进程生成后,父进程在vfork中被内核挂起,直到子进程有了 自己的内存空间(exec**)或退出(_exit)。并且, 在此之前,子进程不能从调用vfork的函数中返回(同时,不能修改栈上变量、不能继续调用除_exit或exec系列之外的函数,否则父进程的数据可能 被改写)。 尽管限制很多,vfork后马上exec效率会比fork高不少。 fork函数是用于创建一个子进程,该子进程几乎是父进程的副本,而有时我们希望子进程去执行另外的程序,exec函数族就提供了一个在进程中启动另一个程序执行的方法。它可以根据指定的文件名或目录名找到可执行文件,并用它来取代原调用进程的数据段、代码段和堆栈段,在执行完之后,原调用进程的内容除了进程号外,其他全部被新程序的内容替换了。另外,这里的可执行文件既可以是二进制文件,也可以是Linux下任何可执行脚本文件。 (2)在Linux中使用exec函数族主要有以下两种情况 a. 当进程认为自己不能再为系统和用户做出任何贡献时,就可以调用任何exec 函数族让自己重生。 b. 如果一个进程想执行另一个程序,那么它就可以调用fork函数新建一个进程,然后调用任何一个exec函数使子进程重生。 (3)exec函数族语法 实际上,在Linux中并没有exec函数,而是有6个以exec开头的函数族,下表列举了exec函数族的6个成员函数的语法。 所需头文件: #include 函数说明: 执行文件 函数原型: [plain] view plain copy int execl(const char *path, const char *arg, ...) int execv(const char *path, char *const argv[]) int execle(const char *path, const char *arg, ..., char *const envp[]) int execve(const char *path, char *const argv[], char *const envp[]) int execlp(const char *file, const char *arg, ...) int execvp(const char *file, char *const argv[])



各种树的应用场景

Posted by 夏泽民

AVL树:平衡二叉树,一般是用平衡因子差值决定并通过旋转来实现,左右子树树高差不超过1,那么和红黑树比较它是严格的平衡二叉树,平衡条件非常严格(树高差只有1),只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少,但查找多的情况。



sbt

Posted by 夏泽民

SBT = (not so) Simple Build Tool,是scala的构建工具,与java的maven地位相同。其设计宗旨是让简单的项目可以简单的配置,而复杂的项目可以复杂的配置。。。 sbt项目的目录规约 和maven一样,sbt有约定了一个通用的目录结构,使用约定的结构会使后面的工作简单很多。 base/
build.sbt //构建配置文件 /project //也是构建配置的一部分 /build.scala //高级配置,可选 /src/ /main /scala /java /resources /test /scala /java /resources base代表项目的根目录 项目配置可以在build.sbt文件里定义,也可以在base/project/build.scala文件里定义,一般情况下build.sbt就已经足够,除非多工程项目或者需要很多特殊定义的项目 常用命令 在我读完sbt的getting started文档之前,我也经常有疑问:为什么scala不沿用maven,而要搞出sbt这么个(not so simple) Simple Build Tool ? 在读完文档,并实际操作后,我现在感觉确实是物有所值的。 checkout 我的sbtTemple项目后,进入命令行,进入到项目根目录,输入sbt回车进入sbt交互模式 sbt有哪些命令可用?输入help命令查询,即会列出一堆可用的命令,比如exit,reload等,不知道某个命令的作用?help 命令名,比如输入help exit显示exit命令的作用。 列出的命令里并没有compile,test等常用的命令?因为那些不是sbt的命令而是当前工程的task. 输入 tasks命令,就可以看见 compile,test,package等等任务的说明了。 想查看项目的配置?用show命令,输入show name,看当前项目的名字,输入show libraryDependencies看当前项目依赖的库,libraryDependencies太长记不住?输入lib后按tab键! 交互窗口是有tab提示的!输入help show,你可以看到show命令的作用是显示配置的值,如果show之后跟的是任务,则执行该任务并显示任务执行的结果。 你可以试试show compile看什么结果,如果你不想执行compile,而是想看命令的说明,请用inspect命令,inspect命令比较复杂,执行后输出的结果也比较复杂,具体这个命令的作用是什么请help inspect, 不过得等理解了build definition的含义后才能看懂help说的是什么。。。 常用的任务则有compile, test, run,package,doc等,请顾名思义或自行help之。另外这些任务常常还有些变种,比如package-doc,package-src等,用tasks命令查看任务的列表,必有一款适合您 有一个强大的任务不得不特别拎出来说一下:console 输入console回车,会在当前会话内启动一个REPL,不要告诉我你不知道REPL是scala解释器的意思。。。就是你在命令行下输入scala回车后进入的那个交互界面。 强大的是,sbt会加载你的项目依赖的全部jar包和你自己的代码! 你可以在这个解释器里实验你的半成品。 我的模板工程里有一个sample/Account.scala文件,十几行很简单的代码,你可以看一下,然后在console窗口里玩弄Account类和Account伴生对象. 不过别忘了先import sample._ 因为依赖的jar包也都被加载了,所以对于那些你可能还不熟悉的第三方库,你有可以在console里玩个痛快!这功能很给力,谁用谁知道。 顺便在提一下,sbt命令有3种执行模式: 1、交互式,即上文所描述的 2、批处理式,即在命令行下输入sbt 命令名来执行,比如sbt compile就会编译代码,而不进入交互模式 3、连绵不绝式,在命令名前加上~号,即会进入连绵不绝模式,比如~compile,会编译当前代码,然后监听代码改变,每当你编辑了代码并保存后,sbt就会自动编译代码,~test也一样,当你修改代码后自动编译并运行单元测试。按回车键可退出此模式。 build definition释义 你前面应该试过show name和show libraryDependencies了吧?show出来的结果就是来自你的build.sbt文件,也就是build definition了。打开build.sbt就可以看到name := “sbt11template” 还有其他的一堆xxx := xxxx,很显然的,这就是个key-value pair, sbt就是读取配置文件并构建一个key-value的map. 但是在build.sbt里面并非key := value, 而是key := expression. 文件里的每一行其实是一句scala语句,不行你可以试试把 name := “sbt11template” 改成 name := {“sbt11template”.toUpperCase} 然后reload, 再show name,你会看到变成大写的SBT11TEMPLATE :=是最常用的方法,其作用就是将key设置成expression的值,相同的key如果被多次赋值,则后面的值会覆盖掉前面的值。适用于简单类型的key,比如name,version等。 其他的常用方法有 +=,将值添加进现有值里,适用于集合类型的key,比如libraryDependencies ++=,将一个集合值加入当前集合里.~=将key的当前值传给你的函数,然后将函数结果作为新值,比如你可以在name := xxx后面再来一句 name ~= { _. toUpperCase },一样是把name变成大写 «= 将另一个key的值赋给当前key,比如auther «= name ,这个方法还有个高级用法,你可以组合多个其他key的值,赋给当前key,用文档里的例子 name «= (name, organization, version) { (n, o, v) => “project “ + n + “ from “ + o + “ version “ + v } 还有适用于集合类型的版本 <+= 和 <++= 这些语法的官方文档在此https://github.com/harrah/xsbt/wiki/Getting-Started-More-About-Settings 依赖管理 对于不打算通过官方repository管理的第三方库,在项目目录下建个lib目录,把jar包扔进去就行了。 希望sbt待为管理的则在build.sbt里用下面的语法加入 libraryDependencies += groupID % artifactID % revision % configuration % configuration是可选的,表示某依赖库只在特定配置中需要,比如模板项目里的”org.specs2” %% “specs2” % “1.7.1” % “test” 是单元测试框架,只在测试时需要。 如果你视力好,会看到其中有个 %%,而不是一个%,这表示要求sbt寻找用当前你配置的scala版本编译出来的jar包,这是因为scala不同版本编译出来的结果会不兼容(悲剧),希望以后scala社区会解决这不兼容的问题。。。 对于依赖的java语言写的库的jar包,就没这问题了,比如libraryDependencies += “org.slf4j” % “slf4j-api” % “1.6.4” 就不需要%%了 配置好依赖后,运行sbt update,sbt会自动到maven库和scala官方库里去找这些jar包并下载到你的用户目录的.ivy2目录里面,如果你不同的项目用了相同的库,则sbt下载一次就够了。 如果你希望sbt从你自己配置的repository里下载,使用这个语法: resolvers += name at location 比如 resolvers += “Scala-Tools Maven2 Snapshots Repository” at “http://scala-tools.org/repo-snapshots” 所有的一切都是通过key类配置的,key 的列表在http://harrah.github.com/xsbt/latest/sxr/Keys.scala.html 慢慢看吧。。。 sbt插件 现有的sbt插件的列表在https://github.com/harrah/xsbt/wiki/sbt-0.10-plugins-list 安装的方法各有不同,请自己查阅 我的项目模板里已经配置了sbteclipse插件,运行sbt eclipse或在交互模式下输入eclipse回车即会生成相应的eclipse项目文件,然后你就可以在eclipse里用import / existing projects into workspace来导入了。 添加依赖这个简单的解析器对于这点输入内容是可以正常工作的,但是我们还需要加入测试代码并且对它进行一些改造。首先要做的就是把specs测试库以及一个真正的JSON解析器加入到我们的工程里来。为了达到这个目标,我们需要在默认的工程结构上进行改造,然后创建项目。把下面的内容添加到project/build/SampleProject.scala里:import sbt._class SampleProject(info: ProjectInfo) extends DefaultProject(info) { val jackson = “org.codehaus.jackson” % “jackson-core-asl” % “1.6.1” val specs = “org.scala-tools.testing” % “specs_2.8.0” % “1.6.5” % “test” } 常用命令actions – 显示对当前工程可用的命令 update – 下载依赖 compile – 编译代码 test – 运行测试代码 package – 创建一个可发布的jar包 publish-local – 把构建出来的jar包安装到本地的ivy缓存 publish – 把jar包发布到远程仓库(如果配置了的话) 更多命令test-failed – 运行失败的spec test-quick – 运行所有失败的以及/或者是由依赖更新的spec clean-cache – 清除所有的sbt缓存。类似于sbt的clean命令 clean-lib – 删除lib_managed下的所有内容sbt结构说明基础目录 在 sbt 的术语里,“基础目录”是包含项目的目录。所以,如果你创建了一个和 Hello, World 一样的项目hello ,包含 hello/build.sbt 和 hello/hw.scala, hello 就是基础目录。源代码 源代码可以像 hello/hw.scala 一样的放在项目的基础目录中。然而,大多数人不会在真实的项目中这样做,因为太杂乱了。 sbt 和 Maven 的默认的源文件的目录结构是一样的(所有的路径都是相对于基础目录的):src/ main/ resources/

scala/
java/
test/ resources scala/ java/ src/ 中其他的目录将被忽略。而且,所有的隐藏目录也会被忽略。构建产品 构建出来的文件(编译的 classes,打包的 jars,托管文件,caches 和文档)默认写在 target 目录中。交互模式 在你的项目目录下运行 sbt 不跟任何参数:$ sbt 执行 sbt 不跟任何命令行参数将会进入交互模式。交互模式有一个命令行(含有 tab 自动补全功能和历史记录)。例如,在 sbt 命令行里输入 compile:> compile 再次 compile,只需要按向上的方向键,然后回车。 输入 run 来启动程序。 输入 exit 或者 Ctrl+D (Unix)或者 Ctrl+Z (Windows)可以退出交互模式。批处理模式 你也可以用批处理模式来运行 sbt,可以以空格为分隔符指定参数。对于接受参数的 sbt 命令,将命令和参数用引号引起来一起传给 sbt。例如:$ sbt clean compile "testOnly TestA TestB" 在这个例子中,testOnly 有两个参数 TestA 和 TestB。这个命令会按顺序执行(clean, compile, 然后 testOnly)。常用命令 下面是一些非常常用的的 sbt 命令。更加详细的列表请参见 命令行参考。clean 删除所有生成的文件 (在 target 目录下)。 compile 编译源文件(在 src/main/scala 和 src/main/java 目录下)。 test 编译和运行所有测试。 console 进入到一个包含所有编译的文件和所有依赖的 classpath 的 Scala 解析器。输入 :quit, Ctrl+D (Unix),或者 Ctrl+Z (Windows) 返回到 sbt。 run <参数>* 在和 sbt 所处的同一个虚拟机上执行项目的 main class。 package 将 src/main/resources 下的文件和 src/main/scala 以及 src/main/java 中编译出来的 class 文件打包成一个 jar 文件。 help <命令> 显示指定的命令的详细帮助信息。如果没有指定命令,会显示所有命令的简介。 reload 重新加载构建定义(build.sbt, project/*.scala, project/*.sbt 这些文件中定义的内容)。在修改了构建定义文件之后需要重新加载。 添加依赖库 有两种方式添加第三方的依赖。一种是将 jar 文件 放入 lib/(非托管的依赖)中,另一种是在build.sbt 中添加托管的依赖,像这样:val derby = "org.apache.derby" % "derby" % "10.4.1.3"lazy val commonSettings = Seq( organization := "com.example", version := "0.1.0", scalaVersion := "2.11.4" )lazy val root = (project in file(".")). settings(commonSettings: _*). settings( name := "hello", libraryDependencies += derby )


Search

Popular posts

Anything in here will be replaced on browsers that support the canvas element

Recent posts

This blog is maintained by 夏泽民

Get in touch with me at 465474307@qq.com

Subscribe to our mailing list

* indicates required