前言

在PHP7生命周期中会涉及信号的处理在第7.1基础知识中，作者提到了信号处理，并得出结论：

• 可靠信号(>=34)不会丢失，N个可靠信号经过排队，在信号处理的时候仍然是N个。
• 非可靠信号(<34)会丢失，N个非可靠信号经过排队，在信号处理的时候是1个
• sigprocmask系统调用是设置进程的信号掩码(掩码中的信号会进入队列排队处理)的。
• 对于3中进入队列的信号，进程可以通过sigsuspend(&newMask)从队列中取出阻塞信号

在这一小节的学习过程，大家对信号处理都不是很熟悉，理解起来比较费劲，故在这里对该小节中的示例代码进行剖析

知识拓展

在讲解代码之前，先拓展一下信号的相关知识

UNIX信号有1~63个

• 1~31的信号为传统UNIX支持的信号，是不可靠信号(非实时信号)
• 34~63信号是后来扩容的可靠信号(实时信号)

注意：32和33信号是不存在，应该是想区分开这两类信号吧

不可靠信号不支持排队，可能会造成信号丢失

可靠信号支持排队，不会造成信号丢失

可以采用多次发送来进行排队测试

发送信号到进程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

kill [-s signal|-p] [--] pid… 向某一进程发送信号
     kill -2 6389
kill -l [signal]                    信号列表
     
1) SIGHUP   2) SIGINT   3) SIGQUIT  4) SIGILL   5) SIGTRAP
 6) SIGABRT  7) SIGBUS   8) SIGFPE   9) SIGKILL 10) SIGUSR1
11) SIGSEGV 12) SIGUSR2 13) SIGPIPE 14) SIGALRM 15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD 18) SIGCONT 19) SIGSTOP 20) SIGTSTP
21) SIGTTIN 22) SIGTTOU 23) SIGURG  24) SIGXCPU 25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF 28) SIGWINCH    29) SIGIO   30) SIGPWR
31) SIGSYS  34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

需要理解的三个函数

• sigaction()：用来查询或设置信号处理方式
• sigprocmask()：用于改变进程的当前阻塞信号集，也可以用来检测当前进程的信号掩码
• sigsuspend():在接收到某个信号之前，临时用mask替换进程的信号掩码，并暂停进程执行，直到收到信号为止

实战

我们要验证的就是可靠信号(>=34)不丢失，非可靠信号会丢失这一结论，并理解上述三个函数
我们需要检测到当前进程接收到的信号，并且能根据不同的信号设定不同的响应

首先自定义一个信号处理函数

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include<stdio.h>
#include<signal.h>
#include<unistd.h>
#include<stdlib.h>
#include<string.h>
 
/*自定义信号处理函数*/
void signal_handler(int signo);
 
void signal_handler(int signo) {
    if (signo == SIGINT) {
        printf("catch signal SIGINT:%d\n", signo);
    } else if (signo == SIGRTMIN) {
        printf("catch signal SIGRTMIN:%d\n", signo);
    } else if (signo == SIGQUIT) {
        printf("catch signal SIGQUIT:%d\n", signo);
        exit(0);
    } else {
        printf("catch signal: %d\n", signo);
    }
}
 
/*程序主函数*/
int main(void) {
    // 声明一个信号集
    sigset_t set;
    // 清空信号集
    sigemptyset(&set);
    // 向信号集添加信号
    sigaddset(&set, SIGINT);// 添加一个不可靠信号 2
    sigaddset(&set, SIGRTMIN);// 添加一个可靠信号 34
    // 屏蔽信号集中的信号
    sigprocmask(SIG_BLOCK, &set, NULL);
 
    // 声明一个sigaction结构体
    struct sigaction sa;
    // 为结构体申请内存空间
    memset(&sa, 0, sizeof(struct sigaction));
 
    // 安装信号处理器
    sa.sa_handler = signal_handler;
    sigemptyset(&sa.sa_mask);
    // 设置信号处理方式
    sigaction(SIGINT, &sa, NULL);
    sigaction(SIGRTMIN, &sa, NULL);
    sigaction(SIGQUIT, &sa, NULL);
 
    int count = 0;
    while(1) {
        if (count >= 100) {
            break;
}
        printf("sleep...\n");
        sleep(1);
        if (count > 0 && count % 10 == 0) {
            // 每10s接收并处理处理一次信号，处理完后继续屏蔽信号SIGINT, SIGRTMIN
            printf("等待信号..\n");
            sigemptyset(&set);
            sigsuspend(&set);
        }
        count ++;
}
}

上面程序中每10s才去处理一次信号，可以通过10s内连续发送多个不可靠信号2和10s内连续发送多个可靠信号34

来看程序运行结果

1
2

gcc signal.c -o signal
./signal

以下是两种信号的执行结果

• 发送可靠信号
  
• 发送不可靠信号
  

前言

GDB是一个由GNU开源组织发布的、UNIX/Linux操作系统下的、基于命令行的、功能强大的程序调试工具。当程序发生coredump，通过GDB可以从core文件中复现场景，定位问题。

GDB调试常用命令

• file <文件名>

  加载被调试的可执行程序文件。因为一般都在被调试程序所在目录下执行GDB，因而文本名不需要带路径。

(gdb) file gdb-sample

• r

  Run的简写，运行被调试的程序。如果此前没有下过断点，则执行完整个程序；如果有断点，则程序暂停在第一个可用断点处。

(gdb) r

• c

  Continue的简写，继续执行被调试程序，直至下一个断点或程序结束.

(gdb) c

• b 设置断点
  • b <行号>
  • b <函数名称>
  • b *<函数名称>
  • b *<代码地址>

    b: Breakpoint的简写，设置断点。两可以使用“行号”“函数名称”“执行地址”等方式指定断点位置。
    其中在函数名称前面加“*”符号表示将断点设置在“由编译器生成的prolog代码处”。如果不了解汇编，可以不予理会此用法。

1
2
3
4
5

(gdb) b 8
(gdb) b main
(gdb) b *main
(gdb) b *0x804835c  
(gdb) d

• d

  Delete breakpoint的简写，删除指定编号的某个断点，或删除所有断点。断点编号从1开始递增。

• s

  s 相当于其它调试器中的“Step Into (单步跟踪进入)。 执行一行源程序代码，如果此行代码中有函数调用，则进入该函数；

• n

  执行一行源程序代码，此行代码中的函数调用也一并执行。相当于其它调试器中的“Step Over (单步跟踪)”。
  这两个命令必须在有源代码调试信息的情况下才可以使用（GCC编译时使用“-g”参数）。

si, ni si命令类似于s命令，ni命令类似于n命令。所不同的是，这两个命令（si/ni）所针对的是汇编指令，而s/n针对的是源代码。

1 2	(gdb) si (gdb) ni

• p <变量名称>

  Print的简写，显示指定变量（临时变量或全局变量）的值。

1
2

(gdb) p i
(gdb) p nGlobalVar

• display …

  display，设置程序中断后欲显示的数据及其格式。
  例如，如果希望每次程序中断后可以看到即将被执行的下一条汇编指令，可以使用命令"display /i $pc"其中 $pc 代表当前汇编指令，/i 表示以十六进行显示。当需要关心汇编代码时，此命令相当有用。

• undisplay <编号>

  undispaly，取消先前的display设置，编号从1开始递增。

  1 2	(gdb) display /i $pc (gdb) undisplay 1

• i

  Info的简写，用于显示各类信息，详情请查阅“help i”。

(gdb) i r

• q

  Quit的简写，退出GDB调试环境。 (gdb) q

• help [命令名称]

  GDB帮助命令，提供对GDB名种命令的解释说明。
  如果指定了“命令名称”参数，则显示该命令的详细说明；如果没有指定参数，则分类显示所有GDB命令，供用户进一步浏览和查询。

(gdb) help display

实战

GDB调试php

我们在使用GDB调试的时候经常会查看某个变量的信息，如果你的php是开启了编译器优化的，那么是看不到变量信息的，显示<value optimized out>你需要修改MakeFile禁止编译器优化

####修改方法：

vim MakeFile

88 CFLAGS_CLEAN = -I/usr/include -g -O0 -fvisibility=hidden -DZEND_SIGNALS $(PROF_FLAGS)// 将-O0 修改为-O2

保存修改文件执行make clean && make && make install 来重新编译安装PHP

准备代码test.php

1
2
3

<?php
$a = 'hello';
echo $a;

开始进行GDB调试

gdb php

1
2
3
4
5
6
7
8
9
10
11
12

gdb php
GNU gdb (GDB) Red Hat Enterprise Linux (7.2-56.el6)
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/php7internal/php7/output/bin/php...done.
(gdb)

在main函数处设置断点

1

(gdb) b mainBreakpoint 1 at 0xa4e894: file /home/php7internal/soft/php-7.1.0/sapi/cli/php_cli.c, line 1195. // 断点位置

运行test.php

1
2
3
4
5
6
7

(gdb) r test.php

Starting program: /home/php7internal/php7/output/bin/php
[Thread debugging using libthread_db enabled]
Breakpoint 1, main (argc=1, argv=0x7fffffffe448)
 at /home/php7internal/soft/php-7.1.0/sapi/cli/php_cli.c:1195
1195 int exit_status = SUCCESS;

从上面的输出我们看到代码在main函数处停止下来，然后使用n命令执行下一步

1
2
3
4
5
6
7
8

(gdb) n
1196		int module_started = 0, sapi_started = 0;
(gdb) n
1197		char *php_optarg = NULL;
(gdb) n
1198		int php_optind = 1, use_extended_info = 0;
(gdb) n
1199		char *ini_path_override = NULL;

使用p查看变量信息

1
2
3
4
5
6

(gdb) p php_optind
$1 = 1
(gdb) p ini_path_override
$2 = 0x0
(gdb) p ini_entries
$3 = 0x0

使用c命令执行到下一个断点，如果没有其余断点则执行到程序结束

1
2
3
4
5

(gdb) c
Continuing.
string(10) "hello php7"
123
Program exited normally.

DBD调试C程序

准备代码文件test.c

1
2
3
4
5

#include <stdio.h>
int main(int argc, const char * argv[]) {
  printf("hello world");
  return 0;
}

gcc编译

使用gdb调试，要使用-g参数保留代码的文字信息，便于调试 输出到test可执行文件

1. 创建符号表，符号表包含了程序中使用的变量名称的列表。
2. 关闭所有的优化机制，以便程序执行过程中严格按照原来的C代码进行。

gcc -g test.c -o test

gdb 调试

1
2
3
4
5
6
7
8
9
10
11
12

gdb test
NU gdb (GDB) Red Hat Enterprise Linux (7.2-56.el6)
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/php7internal/members/zhaoyunfeng/test...done.
(gdb)

然后就可以愉快的调试啦

扩展阅读

gcc -o 优化等级

-O设置一共有五种：-O0、-O1、-O2、-O3和-Os。
除了-O0以外，每一个-O设置都会多启用几个选项

各个优化等级：

• -O0：这个等级（字母“O”后面跟个零）关闭所有优化选项，也是CFLAGS或CXXFLAGS中没有设置-O等级时的默认等级。这样就不会优化代码，这通常不是我们想要的。
• -O1：这是最基本的优化等级。编译器会在不花费太多编译时间的同时试图生成更快更小的代码。这些优化是非常基础的，但一般这些任务肯定能顺利完成。
• -O2：-O1的进阶。这是推荐的优化等级，除非你有特殊的需求。-O2会比-O1启用多一些标记。设置了-O2后，编译器会试图提高代码性能而不会增大体积和大量占用的编译时间。
• -O3：这是最高最危险的优化等级。用这个选项会延长编译代码的时间，并且在使用gcc4.x的系统里不应全局启用。自从3.x版本以来gcc的行为已经有了极大地改变。在3.x，-O3生成的代码也只是比-O2快一点点而已，而gcc4.x中还未必更快。用-O3来编译所有的软件包将产生更大体积更耗内存的二进制文件，大大增加编译失败的机会或不可预知的程序行为（包括错误）。这样做将得不偿失，记住过犹不及。在gcc 4.x.中使用-O3是不推荐的。
• -Os：这个等级用来优化代码尺寸。其中启用了-O2中不会增加磁盘空间占用的代码生成选项。这对于磁盘空间极其紧张或者CPU缓存较小的机器非常有用。但也可能产生些许问题，因此软件树中的大部分ebuild都过滤掉这个等级的优化。使用-Os是不推荐的。

PHP脚本的执行

编程语言的作用就是将语言的特定符号和处理规则进行翻译，由编程语言来处理这些规则，目前有非常多的编程语言，不管是静态语言还是动态语言都有固定的工作要做：将代码编译为目标指令，而编译过程就是根据语言的语法规则来进行翻译，我们可以选择手动对代码进行解析，但这是一个非常枯燥而容易出错的工作，因此就出现了像lex/yacc这类的编译器生成器

编程语言的编译器或解释器一般包含两大部分：

• 读取源程序，并处理语言结构
• 处理语言结构并生成目标程序

Lex和Yacc可以解决第一个问题，第一部分也可以分成两个部分：

• 将代码分为一个个的标记
• 处理程序的层级结构

很多编程语言都使用lex/yacc或者他们的变体来作为语言的词法语法分析生成器，比如PHP，Ruby,Python以及MySQL的SQL语言实现

Lex和Yacc是Unix下的两个文本处理工具，主要用于编写编译器，也可以做其他用途

• Lex 词法分析生成器 A Lexiacal Analyzer Generator
• Yacc Yet Another Complier-Complier

Lex/Fex

Lex读取词法规则文件，生成词法分析器。目前通常是会用Flex以及Bison来完成同样的工作。

词法规则文件一般以.l作为扩展名，flex文件由三个部分组成，三部分之间用%%分割

1
2
3
4
5

定义段
%%
规则段
%%
用户代码段

例如一下一个用于统计文件字符、词以及行数的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

%option noyywrap
%{
int chars = 0
int words = 0
int lines = 0;
%}

%%
[a-zA-Z]+ {words++; chars+= strlen(yytext);}
{chars++; lines++;}
{chars ++;}
%%

main(int argc, char **argv)
{
    if (argc > 1) {
        if(!(yyin=fopen(argv[1], "r"))) {
            perror(argv[1]);
            return (1);
        }
        yylex();
        printf("%8d%8d%8d\n", lines, words, chars);
    }
}

该解释器读取文件内容， 根据规则段定义的规则进行处理， 规则后面大括号中包含的是动作， 也就是匹配到该规则程序执行的动作， 这个例子中的匹配动作时记录下文件的字符，词以及行数信息并打印出来。其中的规则使用正则表达式描述。

PHP以前使用的是flex，后来PHP的词法解析改为使用re2c， $PHP_SRC/Zend/zend_language_scanner.l 文件是re2c的规则文件， 所以如果修改该规则文件需要安装re2c才能重新编译

Yacc/Bison

PHP在后续的版本中可能会使用Lemon作为语法分析器， Lemon是SQLite作者为SQLite中SQL所编写的词法分析器。 Lemon具有线程安全以及可重入等特点，也能提供更直观的错误提示信息。

下面是以PHP中echo语句的编译为例：echo可以接受多个参数，这几个参数之间可以使用逗号分隔，在PHP的羽凡规则如下：

1
2
3
4

echo_expr_list:
    echo_expr_list ',' expr { zend_do_echo(&$3 TSRMLS_CC); } 
    |                  expr { zend_do_echo(&$1 TSRMLS_CC); }
;

其中echo_expr_list规则为一个递归规则，这样就允许接受多个表达式作为参数。 在上例中当匹配到echo时会执行zend_do_echo函数， 函数中的参数可能看起来比较奇怪， 其中的$3 表示前面规则的第三个定义，也就是expr这个表达式的值， zend_do_echo函数则根据表达式的信息编译opcode，其他的语法规则也类似。 这和C语言或者Java的编译器类似，不过GCC等编译器时将代码编译为机器码，Java编译器将代码编译为字节码。

##opcode

opcode是计算机指令中的一个部分，用于指定要执行的操作，指令的格式和规范由处理器的指令规范执行。除了指令本身以外通常还有指令所需要的操作数，可能有的指令不需要显示的操作数。这些操作数可能是寄存器中的值，堆栈中的值，某块内存的值或者IO端口中的值等等。

通常opcode还有另外一种称为：字节码(byte codes)

#####PHP的opcode

PHP是构建在Zend虚拟机Zend VM之上的，PHP 的opcode就是Zend虚拟机中的指令。

在PHP实现内部，opcode由如下的结构体表示:

1
2
3
4
5
6
7
8
9

struct _zend_op {
    opcode_handler_t handler; // 执行该opcode时调用的处理函数
    znode result;
    znode op1;
    znode op2;
    ulong extended_value;
    uint lineno;
    zend_uchar opcode; // opcode代码
}

和CPU指令类似，有一个标示指令的opcode字段，以及这个opcode所操作的操作数，PHP不像汇编那么底层，在脚本实际执行的时候可能还需要其他更多的信息，extended_value字段就保存了这类信息，其中的result域则是保存该指令执行完成后的结果

#FastCGI

简介

CGI全称是Common GateWay Interface 通用网关接口，它可以让一个客户端从网页浏览器向执行在Web服务器上的程序请求数据。
CGI描述了客户端和这个程序之间传输数据的一种标准。

CGI的一个目的是要独立于任何语言的，所有CGI可以使用任何一种语言编写，只要这种语言具有标准输入、输出和环境变量，如php、perl、tcl等

FastCGI是Web服务器和处理程序之间通信的一种协议，是CGI的一种改进方案。

FastCGI像是一个常驻型的CGI，可以一直执行，在请求到大时不会花费时间去fork一个进程来处理(这是CGI最为人诟病的fork-and-execute模式)。正式因为他只是一个通信协议，还只是分布式的运算，即FastCGI程序可以在网站服务器意外的主机上执行并且接受来自其他网站服务器的请求

FastCGI是语言无关的、可伸缩架构的CGI开放扩展，将CGI解释器进程保持在内存中，一次获得较高的性能。

CGI程序反复加载是CGI性能地下的主要原因，如果CGI程序保持在内存中并接受FastCGI进程管理器调度，则可以提供良好的性能、伸缩性、Fail-Over特性等

生命周期和Zend引擎

SAPI接口

Server Application Programming Interface指的是PHP具体应用的编程接口，就像PC一样，无论安装哪些操作系统，只要满足了PC的接口规范就可以在PC上正常运行

PHP脚本要执行有很多方式，通过Web服务器或者直接在命令行下，也可以嵌在其他程序中

• 使用Apache或者Nginx这类Web服务器来测试PHP脚本

  脚本执行完成后，Web服务器应答，浏览器显示应答信息，或者在命令行标准输出上显示内容

• 使用命令行下通过PHP解释器程序来执行

  命令行参数传递给PHP解释器要执行的脚本，相当于脚本通过url请求一个PHP页面，脚本执行完成后返回响应结果，只不过命令行的响应结果是显示在终端上

脚本执行的开始都是以SAPI接口实现开始的，知识不通的SAPI接口实现会完成他们特定的 工作

开始和结束

PHP开始执行以后会经过两个主要的阶段：

• 处理请求之前的开始阶段

  • 模块初始化阶段(MINIT Moudle Init)

    在整个SAPI生命周期内，该过程只进行一次，例如PHP注册了一些扩展模块，则在MINIT阶段会回调所有模块的MINIT函数

    1 2 3 4 5

    PHP_MINIT_FUNCTION(myphpextension) { // 注册常量或者类等初始化操作 return SUCCESS }

  • 模块激活阶段(RINIT Request Init， 请求初始化阶段)

    例如通过url请求某个页面，则在每次请求之前都会进行模块激活

    1 2 3 4 5 6

    PHP_RINIT_FUNCTION(myphpextension) { //例如记录请求开始时间 // 随后在请求结束的时候记录结束时间，这样我们就能够记录下处理请求所花费的时间到了 return SUCCESS; }

模块在这个阶段可以进行一些初始化工作，例如注册常量，定义模块使用的类等等

TIPI:深入理解PHP内核

常用代码

在PHP源码中经常会看到一些很常见的宏，这些代码在PHP的源码中出现的频率极高

• ‘##’ 和 ‘#’

宏是C/C++非常强大，使用也很多的一个功能，有时用来实现类似函数内联的效果，或者将复杂的代码进行简单封装，提高可读性或者可移植性。

在PHP的宏定义中经常使用双井号

双井号’##’:

编译器编译源代码后生成的文件叫做目标文件。

3.1 目标文件的格式是什么

可执行文件格式：

- PE Portable Executable (windows)
- ELF Executable Linkable Format (Linux)

目标文件：源代码编译后但未进行链接的哪些中间文件windows下的.obj和linux下的.o

1
2

# 使用file命令查看响应的文件格式
file filename.o

2.1 被隐藏了的过程

4个步骤：预处理、编译、汇编、链接

2.1.1 预编译

gcc -E hello.c -o hello.i 或者 cpp hello.c > hello.i

预编译过程主要处理那些源代码文件中以#开始的预编译指令，比如#include、#define等主要处理规则如下

• 将所有的#define删除，并展开所有宏定义
• 处理所有条件编译指令，比如#if #ifdef #elif #else #endif
• 处理#include预编译指令，将被包含的文件插入到该预编译指令的位置，这个过程是递归进行的，就是说被包含的文件可能还包含其他文件
• 删除所有的注释
• 添加行号额文件标识，比如#2 hello.c 2， 以便于编译时编译器产生调试用的行号信息及用于编译时产生编译错误或警告时能够显示的行号
• 保留所有的#pragma编译器指令，因为编译器须要使用它们

经过编译处理后的.i文件不包含任何宏定义，因为所有的宏已经被展开，并且包含的文件也已经被插入到i文件中

算法的概念

一个问题可以有多种算法，每种算法都有不同的效率
算法评定从时间复杂度和空间复杂度计算

时间复杂度和空间复杂度

时间复杂度： 执行算法所需要的计算工作量，一般来说，计算机算法是问题规模N的函数f(n),算法的时间复杂度也因此记作T（n）= O(f(n))

计算方式：

• 得出算法的计算次数

  1 2 3 4 5

  #1+2+3+4+...+n for(i=1;i<=n; i++){ $sum += i; } #总共循环了n次，所以时间复杂度为O(n)

• 用常数1来取代所有时间中的加法常数

• 在修改后的运行次数函数中，只保留最高阶
• 如果最高阶存在且不是1，则去除与这个数相乘的常数

  举例

  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 27 28 29 30 31 32 33

  function test($n) { echo $n; echo $n; echo $n; } #计算3次，O(3)--记作->O(1) for($i = 1; $i<= $n;$i++) { for ($j = 1;$j<=$n;$j++) { $sum += $j; } } #n * n 次 时间复杂度为O(n^2) for($i = 1; $i<= $n;$i++) { for ($j = 1;$j<=$n;$j++) { $sum += $j; } } for () { n次 } echo $a + b #n^2 + n + 1 --->忽略 --> O(n^2) while($n>=1) { $n = $n/2; } #n执行次数 n/(2^m) = 1 #m = log2n,所以时间复杂度O(log2n)

效率排名：O(1)>O(log2n)>O(n)>O(nlog2n)>O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)

最坏的情况：最坏情况时的运行时间，一种保证，如果没有特别说明，说明时间复杂度为最坏的时间复杂度

第1部分 简介

1.1 从Hello World说起

1.2 万变不离其宗

对于系统程序开发者来说，计算机多如牛毛的硬件设备中，有三个部件最为关键，他们分别是中央处理器CPU、内存和I/O控制芯片，这三个部件几乎就是计算机的核心

早期的计算机没有很复杂的图形功能，CPU的核心频率也不高，跟内存的频率一样，他们都是直接连接在同一个总线上。

由于I/O设备诸如显示设备、键盘、软盘和磁盘等速度与CPU和内存相比还是慢很多，当时也没有复杂的图形设备，显示设备大多是只能输出字符的终端，为了协调I/O设备与总线之间的速度，也为了能够让CPU能够和I/O设备进行通信，一般每个设备都会有一个相应的I/O控制器。

后来由于CPU核心频率的提升，导致内存跟不上CPU的速度，于是产生了与内存频率一致的系统总线，而CPU采用倍频的方式与系统总线进行通信。

为了协调CPU、内存和高速的图形设备，人们专门设计了一个高速的北桥芯片，以便他们之间能够高速地交换数据。

由于北桥的运行速度非常高，所有相对低速的设备如果全部连接在北桥上，北桥既需要处理高速设备有需要处理低速设备，设计就会十分复杂，于是设计了专门处理低速设备的南桥芯片。

磁盘、USB、键盘、鼠标等设备都连接在南桥上，由南桥将它们汇总后连接在北桥上。