本文为对计算机科学相关领域的总体性介绍。

本文为作者「计算机基础系列」文章的首篇。系列文章的编写目的是能让拥有本科基础的读者了解计算机各领域的基础知识和常用应用，达到能从事多数计算机领域基础工作的能力（面试和考研还需额外复习八股文）。系列不涉及较深入或细节的内容，希望在某部分继续精进的读者还需自行深入学习。作者研究领域为人工智能，其他方向不算精通，不能面面俱到，难免有遗漏和错误，若有描述不严谨或错误的地方，还望读者不吝赐教。

本章从原始计算机（算盘）开始，解析计算机硬件的各阶段发展，直至现代计算机。

本章涉及课程：计算机组成原理（CPU的各种基础设计）、微机原理（CPU设计的实例化）。感兴趣的读者可继续学习计算机体系结构（CPU的指令流水、调度、并行等的设计）。本章的进一步深入可参考「深入理解计算机系统」一书。

本章知识点：MOS、晶体管、锁存器、寄存器、位、字节、内存、RAM、DRAM、地址总线、缓存、SRAM、汇编器、编译器、高级语言、ROM、半导体存储器、EPROM、EEPROM、闪存、块、扇区、页、寻址空间、常规内存、保留内存、DOS、BIOS、代码段寄存器、指令指针寄存器、POST、主引导扇区、主引导记录、操作系统引导记录区、同步时序电路、时钟周期、机器周期、指令周期。

1.1 从机械继电器到运算电路

最早的计算机为算盘等用于表示和辅助计算的设备。

第二次工业革命前，计算设备主要基于机械逻辑。第二次工业革命后，1890年，打孔计算机出现，其使用电力驱动的机械继电器。以数据分类统计为例，纸带上的孔代表各分类的数据，机械针扫描到孔接通继电器，改变统计数据，完成计算任务。至此，电力代替人力，成为驱动运算逻辑的动力。

机械继电器的使用持续到20世纪中旬（约），其缺点是机械结构耐久较低和时间滞后较长。1904年，真空管出现，它的一个电极会释放电子到真空中，然后另一个电极来接收电子形成电流。在此情况下，电子穿过真空需要另一电极带正电场吸引电子，否则无法形成电流，于是具有了二极管的单向导电特性。由此，人们想到，通过在真空管内加入控制电极用于控制接收电极的正负电场，即可实现机械继电器的作用，这种设备被称为三极管。

人们发现，多个三极管（或二极管）以某些方式连接后能够实现一些有意思的逻辑功能。比如与门电路，这种电路具有多种设计，其使用多个三极管以某种方式连接，然后对外提供四条连线，其中两个用于接收输入，一个用于输出，一个用于接收工作所需的电源（比如要完成低电平输入高电平输出的逻辑，需要电源提供能量，其他逻辑也需要电源补充运算中的能量损耗）。

基于三极管的电路逻辑构成了现代电子计算机的基石，多个基本门电路的连接可构成更复杂的电路，更改这些电路的导线连接成为了最早期编程的方式。与此同时，基于半导体材料的晶体管出现，其相比三极管更快更可靠，常用金属氧化物半导体（Metal-Oxide-Semiconductor，MOS）。晶体管构建的运算电路构成了中央处理器（Central Processing

运算单元接收外部代表数据和代表具体操作的电平输入，输出运算结果和一些标志信息。然而，要完成复杂的计算任务，至少需要有能存储数据和操作指令的存储器存在，运算电路除运算单元外还需存储单元。

存储单元也可依靠门电路的特定连接构建，该设计令单元在收到重置信号前，电路输出仅依赖第一次输入，称为锁存器（latch），存储一位（bit，也称比特）。一组锁存器可组成CPU的内部寄存器（register），存储某个带宽下的数字以及是否允许写入的控制信号。寄存器按锁存器的个数分为8位寄存器、64位寄存器等，扩展为64位CPU、64位操作系统等概念。

为减少定位锁存器所需的线路数，通常使用矩阵访问方式。比如4位锁存器地址可定位2^4个锁存器，由此需要16条数据写入线和16条数据输出线以及一条控制线，若采用矩阵定位则可以4x4定位，由此降低线路数量。将地址转化为具体的线路选择的电路为多路复用器，这是CPU组件操作控制器的组件之一，我们在后文详述。

通常定义8位为1字节（byte，单位为B），即1B=8 bits。一般我们以1字节为存储的最小单位，即8个锁存器并行，每个地址指示一个字节的位置，确定存储位置后由8位的数据线输入或输出数据。

基于锁存器的思想可以构建现代计算机的内存，其通常使用随机访问存储器（Random Access Memory，RAM）中的动态随机存储器（Dynamic RAM，DRAM）。DRAM 由一电容和一晶体管构成其每一存储单元，通电后需要周期性充电来保持存储。CPU能寻址的内存空间主要取决于它的地址总线位数，以20位地址总线为例，其寻址空间即为 2^20B=1MB。

存储单元由CPU片内缓存和寄存器组构成。缓存一般是访问速度比内存更快的一种高速存储器，其先于内存与CPU的寄存器交换数据。通常CPU有三级缓存，其先访问一级缓存，无目标数据时则访问二级缓存。缓存一般使用静态随机存储器（Static RAM，SRAM），其能持续保持数据而无需像 DRAM 一样反复充电。SRAM 由6个晶体管存储1位信息，其结构复杂，功耗较大，成本和集成难度较高，通常只用于缓存。

对于支持多种运算的运算单元，除了接收存储单元的数据外，其还需要输入控制其执行何种运算的指令。由此，CPU 还需取指令、将指令翻译为运算控制信息、且要管理这个流程。于是，我们为 CPU 加入控制单元。

控制单元负责管理和运行输入的控制信息，其包括指令寄存器、指令译码器、操作控制器。其中，指令寄存器负责读取指令暂存，指令译码器将读取的控制信息转化为内部选择具体逻辑运算电路的操作，操作控制器负责生成时钟脉冲、实现启停复位等功能。

开始通电时，CPU内部寄存器置0，内存中的锁存器也没有数据，CPU无法根据指令地址寄存器获取到内存中的任何数据。所以在CPU执行指令前，我们需要先将指令存入内存。

早期我们只能先人工把代表操作的电平一个一个锁存器输入，规模较大的程序我们则用打孔卡和扫描继电器来输入。这种方式在1980年以前被广泛使用，成为那个年代最主要的编程手段。此时的计算机已具有冯诺依曼结构，即算术逻辑单元、数据寄存器、指令地址寄存器、指令寄存器、以及存储数据和程序的内存。

01形式的指令显然不便记忆，程序员需要先写英文指令，再对照翻译本翻译。人们想到如果能写一个翻译程序，那就可以直接输入英文指令的ASCII码，计算机执行翻译程序即可得到指令。由于翻译程序是固定的，可以写在特定的纸带上，那么每次只需把翻译程序和英文指令键入内存，计算机便可得出最终应该执行的二进制序列。

这种思想导致了汇编器（Assembler）的出现。人们键入内存的英文程序经汇编器程序执行后即可得到二进制指令。随着技术进步，汇编器功能越来越强大，能够实现一些自动化的功能了。基于汇编器编写程序的语言即汇编语言。然而，汇编语言与CPU操作的对应性很强，很多算法的汇编编写都非常复杂，导致开发的低效。由此，高级语言的概念诞生。

高级语言的特点就是一条语句能够实现更多的功能，为此其一条语句可能对应十几条甚至更多的机器指令。为实现这种转换，人们设计了编译器，其专门负责将高级语言转化为汇编代码。FORTRAN（Formula Transition）语言是第一个流行的高级语言，于1957年发布。随后20世纪60年代出现了如LISP、BASIC语言，70年代Pascal、C语言，80年代C++、Perl，90年代Python、Java、Ruby等语言。我们会在后文详细描述几种主流语言。

使用打孔纸带等向通电的内存中写入程序的效率较低，最好有不依赖机械结构的，断电后依旧能保存程序的存储介质。磁介质存储器在早期广泛使用，其利用电磁化后磁介质保持其磁极的特性存储信息，随后发展为磁带和软硬介质磁盘。同时发展的还有光盘，其在盘面刻大量小孔通过光反射读取信息，然而这些存储依旧需要扫描机械转动的介质读取信息。对于只可读取不可写入数据的存储器，我们称为只读存储器（Read-Only

人们发现，半导体的电子特性能够支持电读写，其通电能够改变材料的性质（临限电压），并且断电后能够保持，类似于磁结构，称为半导体存储器。半导体存储器由于其可修改数据的特性，常用于作为可擦写可编程只读存储器（Erasable Programmable ROM，EPROM），可用紫外光或高压电删除数据，其中基于电删除的 EPROM 称为EEPROM（Electrically EPROM）。后期的 EEPROM 可按字节删除数据而无需删除所有数据再写入。

闪存（Flash）是基于 EEPROM 的一种改进，其以块（Bank）而非字节来删除数据，由此降低了 EEPROM 的成本。闪存按照设计可分为NOR型闪存和NAND型闪存。NOR型闪存的数据线与地址线分离，可做到按地址读取字节，其基于并联门电路，集成度较低。NAND型闪存则复用了数据线和地址线，使得读取只能按页（Page，通常是256B或2KB等大小，根据其总容量）来读，其基于串联门电路，由于其操作快被广泛使用。

不同的闪存最小删除的存储块大小也不一样，比如按扇区（Sector，通常是2的指数次页）删除或按页删除。扇区最早是磁盘的最小读写单位，由磁盘盘面磁道上的一段弧形区域构成。由于历史原因，扇区大小通常被定义为512B（也有4KB）。操作系统中的块（Block，在 NTFS 文件系统中称为簇， NTFS 指 New Technology File System，为Windows的一种磁盘文件系统）则是指系统对磁盘多扇区（2的指数次）的虚拟，以简化寻址。

以进一步降低成本和提升性能。

基于永久（非易失性）存储，计算机所有组件便以集齐，可以开始启动运行了。

在进入具体CPU如何寻址并执行指令的介绍前，我们需要说明寻址空间。CPU的经典架构是Intel于1978年设计的8086型16位微处理器芯片，为x86架构的鼻祖，拥有一个20位的地址总线、一个16位的数据总线、以及复杂的寄存器架构。32位CPU（如80386型）则对应于32位地址总线，可寻址 2^32B=4GB 的存储空间。

其中，8086的1MB空间为所有CPU的基础，其划分为常规内存（640KB，0-A0000H）和保留内存（384KB，常用作上位内存，又称高端内存），x86架构（32位）扩展的空间（4GB减去1MB）称为扩展内存，这些地址指向的内存存储特定的程序。

常规内存预留给用户的DOS（Disk Operating System，磁盘操作系统，一种原始的操作系统）和DOS程序使用。由于DOS在未来的发展中集成了诸多功能（如各种外设的驱动、病毒软件、字库软件等），640KB不足以支持，人们设计了一些扩展DOS内存的方法，感兴趣的读者可参见和这两篇文章。

保留内存则为系统所用，划分为低128KB和高64KB，中间192KB空间保留。实际上，CPU指令地址寄存器可寻址的地址空间并非全部在内存上，它还可以寻址一些特殊而重要的ROM。最主要地，启动程序（Basic Input Output System，BIOS，基本输入输出系统）存储在主板的 EPROM（通常使用闪存）上。保留内存的低128KB作为显示缓冲区，用于指向显卡的BIOS ROM，因为显卡初始化程序需要在操作系统启动之前启动。而高64KB则指向系统 BIOS 的 ROM 存储。

1.5 操作系统的启动

首先，电脑通电，电压初始不稳定，主板控制芯片组通电后首先向CPU发送一个RESET（重置）信号，使CPU进入复位状态。此时，CPU 首先要运行启动程序（BIOS）。CPU 的指令地址寄存器会从其存储的地址中取址来执行，由于初始应该为0，CPU应该会取内存中地址为0的指令过来，但内存刚通电时不会有BIOS的指令。所以，硬件层面上我们要令通电后CPU指令地址寄存器接收到一个非0的初始地址的输出，去读闪存芯片上的指令。

以8086（16位）计算机为例（x86在其基础上仅有小的修改），Intel设计CPU接收重置信号后其指令地址寄存器的硬件设计会导致其首条指令地址为 0xFFFF0H（其中0x和H表示16进制的前后缀，之后省略，注意8086地址总线为20位而非16位，32位为FFFFFFF0）。该地址在硬件上由 CPU 众多寄存器中的代码段寄存器（Code

CPU通过地址总线和数据总线获得指令后，将其存入片内大小为6字节的指令队列中，通过片内8位的队列总线进入指令执行单元，开始译码和执行指令。16位CPU时，BIOS ROM 映射（对应）于保留地址的 F0000 至 FFFFF 的 64KB 空间内（即16位CPU 1MB寻址空间的末端）。32位 CPU 会将 BIOS 映射于 FFFFFFFF 向下扩充的64KB空间，BIOS的第一条指令即置于 FFFFFFF0 指向的 ROM 位置上。

BIOS常见的设计是将这条指令设计为一条跳转指令： JMP F000:E05B，同样 CS 左移4位后相加得 000FE05B，依旧对应于BIOS的地址区。注意到我们前文提过，32位CPU首条指令的地址是基于特殊的硬件设计得到的 FFFFFFF0 ，此后的地址计算则回归正常。在其他设计中，也存在一种不跳转且保持CPU首次的地址计算方式直接执行完BIOS中 RAM 等重要硬件初始化工作的设计。

跳转后，CPU首先执行一系列硬件检查指令，称为 POST（Power On Self Test，上电自检）。初始化完成后，BIOS将剩余程序复制到从 A0000 开始的物理内存中并令CPU去执行内存中的代码。

此时，BIOS通常会指定启动硬盘（即可引导的存储设备）。BIOS首先会将硬盘的主引导扇区读入到CPU寻址空间常规内存区的 7C00 位置。以磁盘为例，如前文所述，扇区大小通常设定为512字节，其前446字节称为主引导记录（Master Boot Record，MBR），存储硬盘的参数和一段引导程序，其后是4个16字节的分区表（Disk Partition Table，DPT，也称分区记录），存储硬盘的分区记录（最多4个），最后则是2字节的结束标志，用于检查主引导记录是否有效。

BIOS加载主引导扇区后首先检测结束标识，以确定该硬盘可引导系统。若有效，BIOS执行MBR中的引导程序，其用于检查硬盘的分区表，并运行分区内被标记的操作系统启动程序。首先MBR会复制自身程序到 600 处，然后执行该处指令。活动分区的第一扇区即操作系统启动程序所在，称为操作系统引导记录区（DOS Boot Recorder，DBR）。MBR据此检查主分区中的活动分区，将其第一扇区复制到 7C00 处，将执行权交于 DBR。同样 DBR 也有结束标志，检查该标志，若有效，则启动操作系统。

要准确完成复杂繁多的指令，显然，如果没有严格设计的CPU，程序一定会到处出错。

CPU内部属于时序逻辑电路，即输出不单与输入相关，还与电路的原始状态相关。各电路的状态极其复杂，运算单元和寄存器有着各种各样的输入和输出，对输入的反应时间也不一致。如果上一条指令执行完的电路直接接收了下一条指令，可想而知CPU在复杂内部逻辑中可能出现混乱的中途输出。

为解决这个问题，现代CPU设计中普遍采用了同步时序电路的设计。它在基本的锁存器结构上加上了某种基于与非门的设计，称为触发器。触发器本质上也是锁存器，它相比多了一个控制极，这个控制极同样是用于保持输出，在锁存器因第二条指令的计算而改变了其输出后，这个控制极会依旧保持旧的输出，直到这个控制极收到特殊的控制信号电平。

于是，CPU设计中出现了时钟的概念。时钟会在高低电平上来回切换，并在每个电平上均保持一定时间，这样，寄存器的输出在时钟信号（如高电平）到来之前都会保持不变，也就是说在一个时钟电平中逻辑门无需关心传播时延，可以放心利用寄存器的结果执行计算，然后在下一个时钟电平时完成此次运算的输出和寄存器的整理。

一个时钟周期表示一次时钟高低电平的总时长（注意不是单电平时长），显然这就是CPU最基本动作（运算和输出存储）至少所需的时间。视操作复杂度，一个CPU基本操作可能涵盖多个时钟周期，称为机器周期或CPU周期。一个指令可能涵盖多个机器周期，称为指令周期，时间最长。有了时钟后，CPU就以一定节律完成取址译码执行再取址等一系列流程，实现计算机的机能了。

操作系统启动后，首先会将操作系统的内核加载到内存中。内核是操作系统对底层的封装，通常运行在最高特权级，管理硬件（如处理器、内存、硬盘、网卡、外设等）。内核底层负责与硬件交互（如驱动、处理器管理等），也称为微内核。在此之上内核还会实现一些功能模块，整体也称为大内核。以 Linux 内核为例，其可分为五个子系统分别实现不同的功能，包括进程管理系统、内存管理系统、虚拟文件系统、网络系统、进程间通信系统。

操作系统在内核的基础上还会提供了一些便于用户使用的服务和软件，如提供给高级语言调用的系统库函数。用户的程序不能直接操作CPU等硬件，需要通过操作系统协调，用户需要通过库函数调用操作系统的内核完成指令。此时即称用户程序运行在系统的用户态，而内核操作运行在系统的核心态。操作系统的核心就是内核。

本章知识点：进程、PCB、阻塞、线程、进程调度策略、死锁、临界资源、临界区、互斥、同步、自旋锁、信号量、管程、事件、管道、消息队列、共享内存、套接字、分页存储管理、分段存储管理、局部性原理、虚拟内存、页面置换算法、颠簸。

除为用户和硬件交互提供便利外，操作系统一个很重要的功能就是对多任务的支持。CPU是按序执行计算的，但用户可能希望同时进行着几项任务，此时操作系统就需要分配和调度CPU的计算资源给各项任务，并让它们看起来是同步执行的，称为并发。注意区分并行的概念，并行指的是各任务实际同步地执行，如多核CPU每个核上单独负责一个任务。

操作系统进行CPU资源分配和调度的基本单位通常称为进程（Process），但进程更多是描述一段运行过程，精确描述时会用进程实体来指代进程过程的具体内容。具体上，进程通常包含四部分内容。第一是使用分配给该进程资源的程序代码，其通常是程序或程序中相对独立的一段代码。第二是系统为进程分配的私有内存，包括文本区（text）、数据区（data）、堆区（heap）和栈区（stack），其中文本区也称代码区，存储可执行代码，数据区存储初始化和还未初始化的静态数据，堆区存储代码运行时的中间数据，栈区存储子进程和某些事件的信息。第三是处理器上下文（context），主要是CPU寄存器内容，用于切换进程。第四是进程权限和描述符等信息。

操作系统初始化进程时会将对应程序代码放到内存中，并将大部分进程的信息保存在进程控制块（Process Control Block，PCB，也称进程描述符）中以管理进程。PCB 根据系统的不同存储不同的进程信息，但均会包括进程的标识数据（如唯一标识符和设备占用信息）、内存描述表（如内存的分配信息）、状态信息（进程挂起时的信息，如CPU寄存器和堆栈区内容）、控制信息（如调度状态、子进程信息、权限、CPU调度信息等）。

进程初始化后有可能处于三种状态。第一是就绪状态，即除CPU外其余资源已分配，等待CPU，第二是运行状态，此时进程占用CPU，第三是阻塞状态，此时进程需在某种条件满足时才可继续执行，当进程主动进入阻塞状态时，也称睡眠或挂起，阻塞、挂起和睡眠通常视为同一种状态。

在进程运行状态时，为更好利用CPU资源，实现程序层面的并发，进程会使用线程（Thread）来使用CPU。线程是进程进行CPU资源分配和调度的基本单位。一个进程至少具有一个线程，多个线程共享进程的信息，但其自身仅包括很少的信息，如一个栈和CPU的一组寄存器信息。线程共有5种状态：新建状态、可执行状态、运行状态、阻塞状态、死亡状态。我们在系列三介绍 Java 语言时会介绍 Java 语言如何管理线程的5种状态。

进程管理系统负责管理CPU的资源，主要就是将CPU资源调度给应用程序使用，可视为处理器管理系统。当多个应用程度请求CPU资源时，进程管理系统能管理各进程对CPU的访问，实现操作系统上的并发。

queue）。前三种顾名思义，轮转策略即每个进程轮流占用时间片，多级队列即进程分配到不同队列中服从队列内调度策略，其队列则按优先级。

在进程的并发调度中，若有两进程互相等待对方占用的公共资源（如打印机）才可继续运行，这两进程将无法继续执行，称为死锁。显然，死锁有四个条件：互斥（至少一个资源不是共享的）、占有并等待、非抢占（即进程不会被抢占资源）、循环等待（即多进程并发时存在前依赖后后依赖前的情况）。要解决死锁也很直观，即预防死锁（令其四条件之一不可能成立）、避免死锁（运行时尽量避免其条件成立）、解除死锁（强行结束进程或抢占资源）。

要预防死锁，第一是不互斥，但很多资源属性上就不可共享，通常无法实现。第二是占有不等待，此时要求进程一次性就锁定其所有要用的资源，或是进程进入等待时先释放所有资源再做请求，但进程是动态执行的，锁定资源会降低资源的利用率。第三是允许抢占，但难以实现，系统性能会降低。第四是避免循环等待，资源会被预先编好序号保证按序的调用不会出现互相依赖的情况，进程请求时严格按照该顺序调用。

若各进程开始运行，避免死锁主要依赖于避免循环等待条件。系统可以动态检测资源分配的状态，预测某请求是否会死锁。典型的判断算法有资源分配图算法和银行家算法。资源分配图算法将资源和进程以某种方式连成图，以某种算法判断死锁，当进程请求资源时，若资源分配图可行则允许请求。资源分配图算法仅用于各类资源均只有一个的情况，银行家算法则允许多个，其主要基于完全性算法，本文不详述了。若已进入死锁则需解除，如终止所有进程或逐个终止进程直到死锁解除，或回滚某进程到未占用某资源的状态。

一次只允许一个进程使用的资源称为临界资源，进程访问临界资源的代码称为临界区。进程中的线程执行临界区（代码）时，需要保证进程中的其他线程按序请求临界区，而不是竞争。反直觉地，这种类似互斥的概念被称为同步（也称直接制约关系），其强调的是线程或进程按序访问临界资源，而互斥（也称间接制约关系）则不强调顺序。与同步相对的则是异步，即线程以不确定的顺序执行。

同步是很常见的需求。首先我们处理进程并发时的同步问题，即进程同步，其主要有三种机制：自旋锁、信号量机制、管程、事件。最直观地，自旋锁即直接加锁，请求资源时循环判断资源锁是否被释放，其与进程互斥问题中加锁的互斥锁不同的是，自旋锁需要一直等待以保证顺序获取资源，而互斥锁获取锁失败后则进程进入睡眠，无法保证顺序。

自旋锁进程等待会浪费CPU的计算资源，考虑令进程睡眠时仍能按顺序获取资源。我们通过信号量实现，其表示资源允许的访问进程数等信息，通常包含锁、计数值、等待队列三个实体。进程可对信号量执行 wait 原语和 signal 原语，其中，原语指需完整执行的程序，这种类似不可分割的特性称为原子性。wait 原语和 signal 原语也称 P 操作和 V 操作，源于其对应荷兰语 prohegen 和 verhogen 的缩写。P 操作即加锁方法，其首先判断信号量条件是否满足，不满足则进入等待队列，进程进入睡眠状态，满足则修改信号量，如减一资源数量。V 操作则是对应的释放锁方法。显然，信号量需要位于多进程可用的公共内存内，而这难以用于分布式系统。分布式锁的实现通常要利用分布式通信机制。

管程则是模块化信号量，将分散于进程中的 PV 操作和其临界区集中管理。事件即在进程占用资源时向其他进程通知，据此其他进程根据顺序判断是否能占用资源。线程并发的同步问题（线程同步）可用除管程以外的进程同步方式。

当进程间要传输不只是信号的大量数据时，我们需要用到进程间通信（Inter-Process Communication，IPC）。信号量和信号也属于IPC 的方法，用于通知其他进程一些标志信息。当涉及较大的数据传输时，IPC 主要有四种方法：管道、消息队列、共享内存、套接字。

管道（pipe）用于小规模数据的传输，不赋予名字的管道进用于父子进程间的通信，命名管道还可允许无亲缘关系的进程间通信。消息队列可支持更大规模的数据传输，具有写权限的进程可以按照一定的规则向消息队列中添加新信息，具有读权限的进程可从消息队列中读取信息。共享内存令多个进程均可访问一块内存空间，但需要注意同步问题。套接字（socket）则是网络进程通信的方法，其遵循网络协议，也可用于本机内的

线程间通信由于共享进程的内存，通常利用线程同步的方法，也可用管道通信。

内存管理系统主要负责程序逻辑内存地址与物理内存地址转换、内存的分配与回收、内存虚拟化扩充、内存读写保护等功能。

内存分配主要解决内存的利用率问题，如分配时如何减少内存碎片。连续分配方式要求将整个进程放入内存，往往碎片较多或内存利用率较低，通常我们使用非连续的内存分配方式，其主要有两种：段式内存分配和页式内存分配。

页式内存分配（或称页式存储管理）将进程分为固定大小的页（page），而物理内存划分为同样大小的帧（frame），进程载入内存时，可以将任意一页放入任意一内存帧，帧不必连续。由于物理内存按帧分隔，所以没有进程外部的碎片（外碎片），但由于一个页可能填充不满，页内可能产生碎片（内碎片）。段式内存分配将进程分为不定大小的段（segment），如代码段、数据段、堆栈段。段大小通过调整可以消除内碎片，但无法管控外碎片。

分页是操作系统管理内存的简单方式，用户并不可知，分页方式不便于用户底层编程，而分段由于是按程序逻辑分的，对用户可知，用户编程会更简单。

内存虚拟化扩充同样考虑内存的利用率问题。可执行程序可能非常巨大，运行它时可能占用大量内存，但每一时刻实际执行的代码可能非常少，这导致了内存空间的浪费。

分析数据的执行可能性可以用局部性原理，即近期使用过的部分可能会再次使用（时间局部性）和使用部分的附近空间可能会被使用（空间局部性）。操作系统根据局部性原理可将内存中暂时用不到的数据移到外存，降低内存的压力，由此虚拟出的一个可能比物理内存更大的内存称为虚拟内存。

操作系统会使用页面置换算法将不用的数据（页）放到外存，通常基于4种算法：先进先出（First In First Out，FIFO）、最近最少使用（Least Recently Use，LRU）、最少使用频率（Least Frequently Use，LFU）、最优置换（Optimal Replacement，OPT，置换预期未来最长时间不用的数据，只是理论上的算法）。

当进程出现缺页中断时，操作系统需要置换内存的某一页，但若此时其他页都在使用，置换任意一页都会引发缺页中断，导致系统效率下降，这种情况称为颠簸（抖动）。产生颠簸的原因通常有页面置换策略问题、程序数量过多、以及物理内存太小。

操作系统在内核中封装了网络系统，计算机网络负责实现计算机间的通信。网络传输的数据只是01电平信号，要解析这些信号，我们就需要遵循协议，协议即是计算机网络的核心。计网协议的内容太多，我们只在本章简单介绍下计算机网络的总体架构，具体的协议内容我们在系列二「计算机网络中的协议」一文中详述。

本章知识点：交换机（多端口网桥）、路由、因特网、互联网、TCP/IP协议体系、有线和无线连接、时分复用、频分复用、码分多址、分组交换、点对点链路、存储转发、模拟调制、GSM、GPRS、WCDMA、LTE、WLAN、TD-LTE、调制解调器、IEEE802.11系列协议（WiFi）、IEEE802.3系列协议簇、串行通信协议、HDLC、PPP、以太网协议、介质访问控制（MAC）、网关、IP、ARP、UDP、TCP、DNS、网络套接字、HTTP。

网络发展的脉络较为清晰。首先，部分计算机间要进行数据通信，于是相互有线或无线连接形成小网络。随着入网计算机的增加，为减少复杂混乱的连接，交换机出现并负责所有数据的交换，所以交换机也称为多端口网桥。随着规模更进一步地扩大，一个交换机无法承担数据交换任务，此时考虑分割不同区域的计算机来构成多个子网络，然后在需要子网间通信时才令子网交换机发送数据到另一子网交换机。

交换机只有自身子网络的信息，要在上层网络中定位到另一子网需要依赖于被称为路由（Route）的设备。路由分隔不同区域的子网，各级区域的互联最终形成了遍布全球的因特网。在定义上，计算机互联通信的网络我们都可以称之为互联网，在英文中通常用internet（首字母小写）与表示全球互联的网络因特网（Internet）区分。

传输数据的解析需要依赖于协议。数据在网络中要经过物理连接、交换机数据分发、路由子网间通信、接收方的应用程序的进程端口监听获取数据、应用程序解析传来的数据，共5个过程，由此构成 TCP/IP 协议体系的五层协议。

TCP/IP协议体系是计算机网络主要采用的分层体系，其将网络自下而上分为物理层、数据链路层、网络层、传输层、应用层五层，其中应用层在OSI（Open System Interconnection Reference Model）网络模型中还分为会话层、表示层、应用层。分层的标准是尽可能保证上层可使用下层提供的服务而无需知道其如何实现。

首先，我们介绍计算机间如何建立起最基本的通信。

建立通信连接只有两种手段：有线或无线。目前有线连接能使用的线路包括导线、电缆、光纤、纳米材料等，无线连接包括微波、短波等。传输的信号除了01形式的数字信号外，也可以选用不定值的模拟信号。模拟信号直观且实时性很好，但一条线路只能被一路信号独占，所以更易处理的数字信号成为当代互联网通信的主要方式。

数字信号可以将多路信号混在一起传输，由接收端负责解析。通信领域一般称发送、传输、接收三端为信源、信道、信宿。多路通信的主要技术分为三种：时分复用、频分复用、码分复用，对应不同地址发送方在单信道上的混合（复用）通信技术即称为：时分多址（Time Division Multiple Access，TDMA）、频分多址（Frequency DMA，FDMA）、码分多址（Code

时分复用指各路信号占据信道的不同时间段（以时隙为最小单位）进行通信；频分复用指信号使用信道带宽中的不同频率（载波）进行传输，其基于多载波调制解调技术；码分复用指各信号使用不同的编码（称为地址码）传输，接收方使用发送方的地址码解码（通常是求规格化内积）得到属于多路信号中发送方的信号，由于内积解码方式，地址码要求尽可能正交以减少干扰。

在发送方式上，信道可分为：单工信道（一方固定发送一方固定接收）、半双工信道（都可发送但同一时间只允许一方发送）、全双工信道（双方任意发送）。信道类型与复用方式构成通信核心技术，如时分双工（Time Division Duplex，TDD）。

连接建立后，发送方和接收方便会持续占用这条信道的一部分（基于复用技术）。比如以前的电话网络需要使用拨号连接到网络提供商进行数据交换，称为电路交换。但通常发送方和接收方并非一直在传输数据，这就会导致信道资源的浪费。于是人们提出了切分数据，然后把数据切片以任意形式发送到接收方，接收方再自行组合数据，由此发送方和接收方无需维持一条信道，这种方式称为分组交换。

具体而言，发送方网卡会把数据切分成数据包，称为分组。分组遵循数据链路层协议，将接收方的地址（以太网中即指的是MAC地址，我们在后文详述）封装到数据包内。若是点对点链路，则分组直接发送到端口另一端，局域网则发送到交换机。交换机若发现接收方地址不在子网内，就将分组上传到路由，否则在自己的本地存储映射表内找到地址对应的交换机端口，并从端口发送分组。若初次连接交换机的计算机还未建立其接入端口和其地址的映射表，则对所有端口广播以获取其地址。一般家庭的路由器都包含了交换机功能（体现为LAN口，Local

当分组来到交换机（TCP/IP体系第二层）和路由（TCP/IP体系第三层）处时，两者使用了存储转发技术。具体而言，由于各分组均具有地址信息，交换机路由会存储分组直到一个完整分组传输完毕，在传输完毕后即直接转发。若需要上层网络转发，则由路由根据路由算法选择其他路由转发分组。于是，发送方和接收方无需建立实际的连接，只需要将数据发送给直连的交换机和路由即可，二者根据发送方网卡封装的信息自行决定如何将数据发送至接收方。路由转发涉及IP协议相关的内容，我们在后文详述。

无线通信技术按代际分为：1G（Generation）、2G、3G、4G、5G。1G时代主要使用模拟调制技术，只能传播语音信号。2G时代采用了数字通信，其采用了GSM标准（Global System for Mobile Communications，全球移动通信系统）。GSM包含了当时许多先进的通信技术，如时分多址，但与有线网络通信体系依旧是相对独立的。

3G时代首先是过渡性技术GPRS（General Packet Radio Service）。GPRS引入了分组交换和存储转发等通信技术，并引入了TCP/IP协议体系。以往GSM在基站以下的传输中使用GSM协议体系，GPRS将网络层以上的通信协议统一到了TCP/IP协议体系，增强了移动端访问网络的能力。基于GPRS和CDMA的思想，欧日首先开创了WCDMA通信技术（Wideband CDMA），正式跨入3G时代。

4G也称LTE技术（Long Term Evolution）原本设计为对3G技术的长期改进，但由于发展太快，使得LTE技术独立为第四代无线通信技术。LTE主要是在3G技术的基础上引进了WLAN（Wireless LAN，无线局域网，相应WWAN为无线广域网）技术。国内运营商主流的4G制式均为LTE-TDD（TDD为前文提到的时分双工），简称TD-LTE。

5G技术主要是4G技术的进一步优化、规模上的扩大，还在发展和成熟的过程中。

TCP/IP协议体系内容较多，主要的协议我们均在系列二文章中介绍，本节只介绍些基本概念。TCP/IP 协议簇一般不包含物理层和数据链路层的内容，为完整起见，我们一并介绍。

物理层协议主要用于表示入网方式的不同。协议内容包括机械、电气、功能、规程等方面特性，定义了接口外形和特征、线路电气信号传输规范、线缆中各线的功能、传输启动与暂停相关的时序过程等。设备上主要为：通信接口、通信线路、以及调制解调器（MODEM，Modulator调制器、Demodulator解调器）。

由于入网接口和方式的复杂繁多，物理层协议非常多。典型的包括IEEE802.11系列（用于WLAN，也称WiFi）、IEEE802.3系列协议簇物理层部分（以太网协议的IEEE版，后文介绍）等。

信号传输可通过物理层的调制、信道传输、解调完成，信号解析则需要规范信号形式，数据链路层即主要负责初步规范01信号（数据帧封装）和保证局域网多路信号的正确传输。

第一，点对点链路的数据帧封装。最初计算机两两相连的时代，数据链路层对01信号的规范采用字符型或比特（byte，即字节）型，如现在很少用的比特型串行（串口）通信协议：高级数据链路控制（High-Level Data Link Control，HDLC）。目前因特网中用的比较多的串行通信协议是点对点协议（Point to Point Protocol，PPP）。

第二，局域网数据帧封装。因特网是由一个个局域网通过路由组成的，最广泛的局域网技术则是以太网（Ethernet），其分为两种典型协议：DIX Ethernet 和 IEEE 802.3 系列协议簇的链路层部分。以太网协议对电信号进行了分组，定义为帧，其在切分好的数据段前后加入了发送和接收计算机的地址和校检信息的数据段。

第三，局域网多路信号的正确传输。数据链路层为此叠加了两个子层：第一是在信道层面管理多路信号的介质访问控制（Medium/Media Access Control，MAC）子层，网卡物理地址在该层定义，称为MAC地址；第二是对MAC子层进行逻辑抽象和进一步管理面向更高一层网络层的逻辑链路控制（Logical Link Control，LLC）子层。我们在系列二文章中详述。

链路实现通信后，我们即需要考虑链路之上的组网问题了。

构成因特网的一个个局域网均为子网，子网间的数据传输需要一个代理，称为网关（Gateway），而各种网络传输路径即称为路由（Routing）。目的主机若不在发送方的同一个子网络里，数据就需要通过网关。显然，依靠出厂就唯一确定的MAC地址不可能知道接收方的子网所在，更常见的是我们只知道对方服务器提供的网址，连MAC地址都不知道。

互联网协议（Internet Protocol，IP）即负责定位子网。每台主机联网后，网络的管理端（一般是网关）会遵循IP协议为每台主机分配一个地址，分为网络地址和主机地址。网络地址表示其属于互联网中的哪一个网络，主机地址表示其属于该网络中的哪一台主机。IP协议即是在更上层传来数据的基础上加上IP字段，网关即可按此解析。

数据包根据IP协议找到网络中的主机后，源主机和目的主机依旧需要在链路层基于MAC地址构建链路，显然IP地址最终需要转换为MAC地址。地址解析协议（Address Resolution Protocol，ARP）即负责此项转换，IP地址可能会周期性变化，ARP通过动态更新自己的IP地址与MAC地址映射表实现动态转换。

数据经网络抵达主机后，操作系统即将其分配到需要它的应用程序，这个过程即遵循传输层协议。

源主机和目的主机的通信本质上是相应主机上应用程序的通信。在操作系统中，应用程序运行在系统分配的进程上，所以应用程序间的通信即进程间通信。不同进程对网络资源的访问是通过逻辑意义上的网络端口来区分的。网络层连接好主机后，传输层即负责定位主机上发送和接收数据的应用程序。

Protocol，TCP）。UDP是最基本的端口协议，其仅仅在网络层传输来的数据上加上进程的端口信息和校检信息。UDP下通信就是一方端口不停输出数据，另一方端口不停接收数据，源和目的主机是没有对话的。显然在复杂的网络环境中，这种方法容易产生数据丢失，所以UDP也被称为不可靠协议。为建立可靠的通信，TCP加入了应答机制和校检机制，我们在系列二文章中详述。

随着端口将对方应用程序的数据送来，应用程序最终即可按照双方定下的规则来解析其数据，这就是应用层协议。

最典型地，我们使用网址访问网页时是我们浏览器的应用程序访问对方服务器的过程，负责将便于人类理解的网址转换为传输层能理解的地址的即是域名系统（Domain Name System，DNS），该地址被称为网络套接字（network socket），由IP地址和进程端口组成，如192.168.0.100:80，代表进程发送和接收和数据端口的抽象节点。操作系统中，DNS 程序默认运行在53端口。

浏览器将对方传输来的数据段解析成网页依据的则是超文本传输协议（Hypertext Transfer Protocol，HTTP），其由请求规范和响应规范构成，HTTP请求和响应的应用程序默认运行在80端口。我们在系列二文章中详述。

套接字（socket）在网络编程中的含义是进程网络端口获取网络数据的操作系统接口（Application Programming Interface，API），英文 socket 也可指CPU等设备的插槽。Berkeley socket 是最基本的套接字，Berkeley表明该套接字源于加州大学伯克利分校的设计，现代操作系统套接字的实现也都遵循Berkeley

操作系统和网络已经完善，基于阴极射线管（Cathode Ray Tube，CRT）和液晶显示原理发展的显示技术让我们能在图形界面开发众多的应用。此时，高级语言便成为我们各种软件应用的开发工具。本章主要介绍最主流的三种语言：C/C++、Java、Python。

本章知识点：源文件、隐式函数声明、编译工具链、预处理器、链接器、GCC、Visual C、Visual C Studio、头文件、库文件、构建系统、make、makefile、元构建系统、CMake、IDE、脚本语言、解释器、预编译、字节码、动态编译、JIT、JVM、HotSpot VM、自适应动态编译器、Java SE、JRE、JDK。

高级语言（high level language）需要编译成汇编语言，再通过汇编器转化为机器码。

C++是C语言发展而来的，其很多特性都有很多历史原因。早期计算机内存很小，一个项目的源文件如果很多，那么将这些文件全部放到内存中使用编译器一并编译会得到大量的汇编代码导致内存溢出，所以编译器需要先分别编译各个源文件，生成多个目标文件，再将这些文件按照它们间的引用关系链接起来，CPU去一个个执行，以避免内存溢出。

一个源文件可能要用到另一个源文件中的函数定义，为了实现分别编译，C语言采用了隐式函数声明的做法，可直接编译未定义的函数，这样，编译器可以不考虑源文件间的链接问题，能够先逐个编译完所有源文件。

由此，C程序的编译工具链即包含预处理器（preprocessor）、编译器（compiler）、汇编器（assembler）、链接器（linker）。预处理器主要处理 #include 和 #define 等语句，编译器用于翻译汇编代码，汇编器将汇编代码翻译成机器码，最后链接器将所有得到的目标文件以及其调用的函数根据依赖关系链接起来，得到可执行程序。

主流的编译器（一般即指编译工具链）有：

GCC 为开源编译器，在 GPL 协议（GNU General Public License） 下，用户可以自定义自己的版本，而 Visual C/C++ 编译器仅有一项版本是免费的。基于跨平台（主要考虑类Unix系统）、高效、和开放性的考虑，GCC编译器更为主流。Windows系统也可以通过 Cygwin 和 MinGW 实现对类 Unix 的支持。

典型的C或C++程序通常由几个源文件（后缀为 .c/.cpp/.cc 等，GCC编译器不会明确区分）和头文件（.h）组成，某些程序可能会调用库文件（.lib，编译完成的程序），如C++标准库。头文件主要用于分离出函数声明等内容，编译器首先将源文件中的 #include xxx.h 替换为 xxx.h 头文件的内容，并依据 #ifndef #define #endif 语句防止重复导入。头文件存在不少弊病，如头文件包含具有传递性，引入不必要的依赖；头文件在编译时即访问，而动态库文件却在运行时才访问，二者时间差可能带来不匹配，导致二进制兼容方面的问题。

对于较大的工程项目，修改代码需要考虑重新编译的问题，比如更改头文件代码时需要重新编译所有含此头文件的源代码，重新编译后还可能需要重新链接。每次更改都重新全部编译将是十分耗时的事。

构建系统（build system）可以减少重新编译的工作量。典型地，GNU Make即是一种构建系统，其基于makefile文件中定义的C项目的编译和链接规则，使用 make 工具调用 GCC 编译和链接多个源文件，更新仅仅修改过的源文件和其依赖，减少编译量。这种通过自动化脚本负责项目编译的思想称为构建自动化（build automation）。

makefile 文件通常要指定操作系统，在多平台、多编译器、多方案的情况下，构建系统文件难以维护。元构建系统（generator of build system）使构建系统文件不再需要手工编写，而是自动生成。典型工具有 CMake 和 Autotools。CMake为构建系统生成 makefile 文件，其基于跨平台的 CMakeList.txt 文件生成特定于平台的 makefile

启动一个 CMake 项目，我们首先需要配置 CMakeList.txt 文件来指定需要编译的文件等信息。构建项目的核心语句为：

# 指定最低要求的CMake版本，默认设置为CLion中捆绑的CMake版本
 

add_executable 命令会指定项目的可执行文件（源文件），add_library 命令可以包含库文件，CMakeList 还有许多默认参数和命令，更多的请参考官方文档。

由于头文件、全局变量和函数、预处理器等机制使得 C++ 较为复杂，但也赋予了其高效的机能和较强的内存管理能力。

与C语言不同，Python 属于脚本语言，即可以不通过编译直接依赖解释器（interpretor）运行。解释器本身是一个完整的程序，其功能类似于编译器和汇编器的组合。解释器会逐条读取 Python 指令，然后根据指令逻辑翻译为其认为效率最优的机器码。运行C程序需要先编译程序为机器码，再运行机器码，而运行 Python 程序则是直接启动解释器程序读取 Python

在语言性能优化方面，Python使用了预编译+解释的方法，源代码会先转化为更有效率的字节码（class，非二进制码），再进入解释器，常见的解释器为CPython。Python也可以采用 JIT（just-in-time compilation，即时编译）技术，如使用 PyPy 解释器时。狭义的 JIT 指在源代码在第一次运行时执行编译以寻求加速。JIT 由于是运行时编译，所以属于动态编译的一种方式。由于PyPy解释器对C语言的支持不如CPython，所以未能广泛运用。

Python语言目前广泛用于人工智能相关领域，其语法十分简单，系列文章中仅会介绍 Java 的语法，Python 语法可视为 Java 语法的简化，其具体实践课参见系列五「计算机算法基础」一文。

由于编译器和解释器的差别，C/C++就像精密组装后严阵以待的高性能机器，而Python就像灵活的多功能工具。然而实际应用中，我们更多会既需要一定的性能，又需要保持灵活性。C/C++语言意味着每次更新都需要编译，而且限定平台不便于迁移，而Python显然在效率上有所牺牲。于是我们想到在解释器的基础上强化预编译，Java 即是专注于此的高级语言。

Java 语言使用复杂的动态编译方法。首先，与 Python 类似，源码通过编译器编译为字节码，再通过解释器翻译为机器码执行，Java 解释器由 JVM（Java Virtual Machine）实现，也就是说 JVM 决定了 Java 动态编译的方式。JVM 有多种实现，目前官方 Oracle 的主要 JVM 是 HotSpot VM，它的编译器使用的是自适应动态编译器，其与 JIT 不同在于其会先让程序跑起来，在途中收集一些信息，然后根据这些信息来执行优化。

Java 通常使用的平台版本有三个：

• Micro Edition（ME）：用于移动设备和嵌入式设备。

当我们初次接触 Java 语言时往往都会被告知首先需要安装 JDK，其与 JVM 关系是：

• JDK（Java Development Kit）：继续集成了 JRE 和另外一些工具（如 Java 编译器），故称为开发工具包，为 Java 开发所需的基本环境。

从工程角度考虑，项目内部区分度较大的逻辑应该是相对独立的，这样修改部分逻辑可以不影响其他部分，逻辑与逻辑之间的交互通过接口来完成，Java 语法由此设计为完全面向对象。

关于 Java 语言的语法和应用我们会在系列三「Java Web工程实践」一文中详述。

生活中我们与计算机交互最多的行为就是浏览网页和手机APP，这些应用被称为Web技术。Web技术主要指人们上网访问网页和与联网软件交互时，用户发送的访问请求数据经过网络传输到对方服务器后，对方对此请求进行处理和回应的一系列技术。

数据传输到目的主机后被监听相应端口的应用程序接收，称为Web服务器。Web服务器不是物理的服务器，而是一种应用程序。在Web语境中，服务器表示的是服务（或响应）客户端请求的程序，其分为两类：Web服务器和应用服务器。实际生产环境中可能也有专门搭载相应程序的物理硬件。

服务器对请求的响应分为静态和动态。Web服务器即负责静态响应，而应用服务器则负责动态响应。静态响应是指请求的是直接的数据，服务器查找定位后可直接返回。而动态响应是指请求不能被直接的数据满足，需要服务器执行一些逻辑运算或数据处理才能返回相应数据。

以浏览器访问为例，其流程为：客户端浏览器发送请求建立连接，服务端的Web服务器接收请求 >> Web服务器处理静态响应，将动态响应相关的请求转发给应用服务器 >> 应用服务器处理请求，与数据库数据存取相关的请求则访问数据库，返回处理后的数据给 Web 服务器发送回去。

Web服务器主要遵从HTTP协议，处理依据HTTP协议定义的格式所传输的数据，故也称HTTP服务器，其基本功能就是从操作系统提供的 TCP socket 中获取数据，分析请求，返回请求对应的 HTTP 响应。Web服务器可以用多种编程语言来写，通常用Java。若读者对其实现感兴趣，可参考文章 ，不过其未实现动态响应转发。动态响应可参考文章 ，其以500行左右的代码实现了一个含动态响应处理的Web服务器。

HTTPd 服务器的基础上开发与维护了一个叫 Apache 的 HTTP 服务器（HTTP server）。这些开发者不断将其完善壮大，并以 Apache HTTP 服务器为中心，启动了更多的与Apache项目并行的项目，比如mod perl、PHP、Java Apache等等，由Apache软件基金会进行管理。

应用服务器则承担与动态响应相关请求的处理，其通常涉及复杂的数据读写和逻辑计算。在 Java Web 工程中，应用服务器常被称为 Web 容器、应用容器、动态容器等。应用服务器最著名的就是 Tomcat，也是隶属于Apache的子项目。著名的 Java Web 框架 Spring Boot 就使用 Tomcat 作为内嵌的默认应用服务器。我们在后文 Java Web

等，hostname 指服务器 DNS 或 IP，可加端口（Web 服务器默认为 80 端口），由分号引导特殊参数，由问号引导动态网页的传参，格式为 key=value&key=value，井号引导页面的名词定位，如百科里的跳转。浏览器解析URL，找到IP地址后浏览器尝试与对方服务器建立连接（以TCP连接为例）。

HTML 用标签格式化网页文字和图像等的显示，CSS文件修饰 HTML 标签的属性，JavaScript 通过网页动作改变标签的属性（JavaScript 是 HTML 中的默认脚本语言，由浏览器执行）。这些负责页面展示的技术被称为前端技术，相应地，为页面展示提供所需数据的技术即称为后端技术。

除此之外，静态响应还包含一些隐式的数据，如文档类型、缓存参数、Cookies 等，其中 Cookies 指提供给客户端浏览器本地保存的一些便于Web访问的信息块，由于可能被恶意获取和编辑，常被认为具有安全风险。

通常服务端可能会不断更新页面数据，客户端要获取最新数据，可采用轮询的技术，也就是客户端每间隔一定时间（如1秒）请求一次数据。每次重新请求页面全部数据（或利用浏览器缓存减少部分数据的获取）的效率显然不高。多数响应并不需要客户端重新请求网页，只需要更新局部数据即可（如社交软件更新消息），所以此时浏览器与服务器交互的格式主体不是页面，而应该是更新的数据。

Notation，JS对象标记）格式，由此更新页面。JavaScript 中的对象格式上与 JSON类型的数据一致，JSON 由此成为了 Web 中主流的数据交换的格式。同时，要保证这种数据传输的持续性，就需要有能保持 TCP 连接的应用层协议，如 WebSocket 协议。

当客户端请求需要服务端运行相应逻辑时（如修改服务端上的数据），该请求即为动态请求，服务端即需要负责动态响应。动态响应的流程大致是：

1. 用户输入URL发出请求，浏览器解码URL的第一部分以连接到Web服务器，并将剩余部分作为参数传递给Web服务器；
2. Web服务器在启动状态，通过 TCP socket 组件监听相应网络端口，此时端口接收到客户端数据，Web服务器识别请求为静态请求，即根据URL指示的文件名，读取对应的 HTML 文件（或别的组成请求页面的文件）并返回，传送完毕后断开 TCP 连接；
3. 用户在客户端页面发出新的请求，浏览器请求 Web 服务器建立一个新的连接，并传输URL信息；
4. 若该 URL 属于动态请求，则Web服务器调用操作系统提供的方法启动负责动态响应的应用程序进程，即应用服务器，应用服务器会把动态响应以某些方式返回给Web服务器，然后Web服务器通过 TCP 连接将响应传回。

动态请求包括 CGI、JSP、Servlets、ASP、服务器端的JavaScript等，由应用服务器负责响应，我们分别说明。

CGI（Common Gateway Interface），即公共网关接口。更准确地说，CGI是一种接口协议，在网页开发的初期时代，CGI提供了最为基础的动态响应方式，它是Web服务器与外部应用程序交互的标准接口。

CGI 并非一种特定的程序，而是一种规范，多数语言都可以用于编写CGI程序，如早期的 Perl 语言和最常用的C/C++等，事实上基本所有支持标准输入输出的语言都能用来写 CGI 程序，所以像主要使用 Servlet 的 Java 和 WCGI 的Python，以及快没人用了的 VB（Visual Basic）语言都可以写 CGI

CGI 程序的调用源于客户端 URL 请求中明确请求了 xxx.cgi 程序，后面可能跟上一些参数，Web服务器收到后对请求信息的字符串进行解析（通过正则表达式），得知客户端请求服务端提供的某个 CGI 程序，然后 Web 服务器便会通过调用操作系统方法启动 CGI 程序进程，并将请求信息传给它。

请求信息即 URL 参数，通常其会以两种方式传递给 CGI 程序：环境变量和标准输入（stdin）。客户端使用 HTTP 协议的 GET 方式的请求会将 URL 参数写入 CGI 程序所在系统的环境变量中，CGI 程序通过操作系统方法即可获取到 URL 参数。客户端使用 HTTP 协议的 POST 方式的请求则会直接将参数以标准输入的方式提供给CGI程序。

CGI 程序运行完后一般通过标准输出（stdout）返回遵循 HTTP 协议的响应，包括 HTTP 主体和 HTTP 响应报头。也就是说，CGI的标准输出除含有响应的数据外，还需要写好 HTTP 响应所需的报头。输出时由于 HTTP 协议是一个字符协议，需要一个空行区分报头和实体。

Web服务器利用操作系统方法监听 CGI 程序的标准输出得到动态响应，类似 stdout=os.run(xxx.cgi)。引用自外网资料，Web服务器在这里的核心机能就是：

CGI 程序通常放在 CGI-BIN（或cgi-bin）目录下。CGI 的缺陷在于其每次访问都会令操作系统开启一个独立的进程，大量访问时进程负担过大。另外，不同操作系统支持的 CGI 语言也不太一致。FastCGI 技术用于缓解高并发问题，其本质就是令多个CGI进程常驻在内存中，CGI请求由调度器来分配处理。请求处理完成后进程不销毁，继续等待请求。

相比 CGI 程序要把复杂的 HTTP 响应报头也写好，我们更希望直接返回一个HTML，动态响应只负责修改HTML实体即可。由此，部分脚本语言试图使用以这样的方式实现动态响应。

早期为代替 CGI，微软设计了 ASP（Active Server Pages）脚本语言，较为难用，微软已经不再更新。由于 ASP 程序需要运行在 Windows 专属的 PWS 和 IIS 服务中（只需知道 PWS 是比 IIS 还古老的 Web 服务器即可），所以不支持跨平台。在 IIS Web服务器下，.asp 的请求能通过 ASP 的配置文件搜索到 ASP 解释程序，由该程序生成并返回完整HTML页面。

我们也可以使用 Java 程序负责动态响应。比如著名的应用服务器 Tomcat，其本质上就是一个 Java 运行环境。我们写好 Java 程序后放入 Tomcat，Tomcat 启动后默认监听操作系统的8080端口，端口传来请求后，Java 程序即可进行解析并最终返回响应。对于8080端口的静态请求，Tomcat 也可设计逻辑满足静态响应，所以 Tomcat 也兼有 Web服务器的功能。

实际上，Tomcat 除运行环境外还为我们提供了主函数和一些请求响应调度的解决逻辑，我们只需关心 HTML 的返回。负责该任务的 Java 对象被称为 Servlet，所以类似 Tomcat 这种应用服务器也被称为 Servlet 容器（container）。此时，每个请求在 Tomcat 中即交由一个 Servlet 对象负责，由此由于 Java 对多线程的支持，在 CGI 中出现的进程负担问题即可得以解决。

本章我们简单分析了 Web 的一些简单流程和概念，但要实际开发一个应用则远为复杂，我们将在下一章中讲解Web 应用通常是如何开发的。

Web工程分为前端和后端两个方向，前端主要是页面展示技术，我们主要讨论后端技术。Web工程主要包括：Web请求分发、对象管理、事务管理、数据库连接等，大型项目的开发和维护还需要考虑代码复用、标准化、可维护性、开发成本等因素。

Java Web项目相对比较复杂。首先，项目通常需要很多依赖包，这些依赖包需要引入工程目录。其次，大量的 Java 程序还需要我们用 javac 工具一个个文件编译成字节码。最后，我们还要测试项目，并把各种所需资源和配置文件打包来上传到服务器。

为简化上述流程，我们可以使用项目管理工具 Maven。类似于构建系统，Maven通过配置文件 pom.xml 配置项目，POM表示项目对象模型（Project Object Model），其包含了项目的基本信息、项目的构建信息、项目的依赖等等。使用 Maven 负责依赖导入、编译、打包等任务的工程称为Maven工程。

本章我们介绍Java Web工程的一些基本概念，具体实践我们在系列三「Java Web工程实践」一文中详述，部分概念可能结合系列三文章会更易理解。

项目的合作开发要求不同逻辑模块间的解耦合，即模块内部的修改不会影响其他模块，模块间的交互通过接口完成。最早期的解耦思想就是三层模式：MVC（model、view、control）。MVC 是 Java EE（Java 2 Platform Enterprise Edition，早期也称 J2EE）中的三层架构，其在 Java EE

• Model层：使用 JavaBean（遵循一种规范写法的用于封装数据的Java类）封装最底层的数据；
• Control层：Controller 向上通过 Servlet 接收用户的请求，向下自定义方法获取 Model 层封装的数据，并编写好合适的视图（页面）返回用于显示；
• View层：使用 JSP 将 Control 层返回的页面数据渲染成页面。

Model 层存放的类一般称为实体类，JavaBean 是典型的一种实体类模式，其只有内部成员属性和类属性读写的 get 和 set 方法，必须公共且只可以有无参构造，在分层架构中通常放在代表 Model 层的 entity（或 pojo）包中（此处涉及 Java的一些语法，若读者不熟悉可先阅读系列三文章的第一章）。

初期被广泛使用，其存在大量代码重复和定义过于严格的问题，其后的 JNDI（Java Naming and Directory Interface）对象也有操作较为单调繁琐的问题。pojo与 entity 不同的是它可以只对应数据表的一部分字段，而无需一一对应。

MVC 本质上只负责了将底层数据返回并展示，完整的 Java Web 工程还包含与数据库的交互和业务逻辑，在整体上被分为三层。以著名架构 ssh（Struts+Spring+Hibernate）为例，该三层为：

• 表示层（MVC层），即MVC的机能，由Struts执行，用于接收和分发用户请求、将封装的数据显示在界面上，不再深入涉及到任何业务和数据库交互逻辑；
• 业务层（Service层），用于处理业务逻辑，对应ssh中的Spring，实际上用到的是 Spring 中的 IoC 容器，用来管理对象，减少对象耦合，我们在后文详解；
• 持久层（DAO层），持久的意义是将内存（易失）的数据存储到硬盘（非易失）中，硬盘通常指数据库。持久层常表示为DAO（Data Access Objects）层，即数据访问对象所在的层。显然，该层主要目的就是和数据库建立起连接并封装好建立连接的方法，以便其他程序调用。

Mapping）框架完成，其属于中间件的一种，基于将关系型数据（即数据库表）映射为对象来使用的思想，后文提到的 Hibernate、MyBatis、SpringDAO 等框架均属于 ORM 框架。

Spring 框架体系是 Java 后端领域的王者，其主要思想为更多使用接口、更多面向对象、更好地配置JavaBean。使用 Spring 框架开发的项目典型情况下分为四层：View、Control、Service（业务层）、DAO（持久层），这里的V 和 C 即表示层的拆分。

ssm 中的 Spring 对应于 Service 层，其管理业务逻辑，核心为两大思想：

Java 在业务逻辑中常常需要创建（new）对象，对象可能会依赖其他多个对象。比如业务层提供用户服务类和商品服务类，用户购买商品即需要创建用户对象和商品对象存储相关信息，而两个对象显然都需要访问数据库，于是要创建两个 DAO 类的对象，而 DAO 类一般还需要读取数据库配置信息，而这又是一个类的对象。

我们发现，服务类对象依赖于 DAO 类对象依赖于配置类对象，当项目很大时，复杂的依赖会导致 JVM 中存在大量的对象，并且可能大量重复，销毁对象时也难以保证销毁的正确顺序。另外由于依赖，对部分类的改动可能导致一系列改动。如果我们依赖的类对象可以直接传入而无需把全部依赖的对象都创建出来，这将极大减少我们的开发压力。

文件中预先配置类间的依赖关系，其使用标签和标签定义类和类的依赖。当类对象依赖某类时，只需 new 一个 IoC 容器类，通过 IoC 类的方法即可得到依赖类的引用。读者可结合系列三文章理解本部分。

此时，依赖对象不再由代码逻辑控制，而是交于容器程序来管理，对某类的依赖不再需要由类自己主动请求创建，而是交由 IoC 容器来向其注入依赖类的引用，控制权由主动创建变为了被动注入，所以称为控制反转。

业务代码中通常含有与具体业务逻辑无关的部分，如安全检查、日志、事务等，这些部分会重复出现在各个业务方法中。面向切面编程（Aspect Oriented Programming，AOP）即是将这些共通的业务抽象成一个个切面，通过预编译、类加载期或运行期将这些切面再植入到原本的代码中以简化编程。Spring 的 AOP 即是运行期利用 JVM 的动态代理能力实现。动态代理我们会在系列三文章中详解。AOP也被视为OOP（Object Oriented Programming，面向对象）的延续。

在具体应用和操作系统内核间的程序我们都可以理解其为中间件，如静动态服务器、消息队列等，主要有：

• 消息队列（Message Queue，MQ）：负责数据队列式寄存的程序，具有解耦、异步、限峰、削流的作用，常用的消息队列有 ActiveMQ、Kafka 等；
• 远程过程调用（Remote Procedure Call，RPC）：负责网络服务器间进程通信的工具；
• Docker：一种应用容器，其仅封装需要的应用和依赖包就可以依赖当前操作系统启动独立服务，类似于虚拟机；
• Kubernetes：用于部署和管理云平台中多个主机上的容器化的应用。

中间件的实践主要是API的调用，在实际需求中学习即可，也可以看网上的专门教程，轻型的中间件相对语言和后端框架而言简单很多。我们会在系列三文章中介绍部分中间件。

我们在互联网获取想要的信息时通常使用搜索，但对海量的互联网数据建立索引极其困难。首先是读取问题，串行的数据读取是十分耗时的，如1TB磁盘数据的读取最短也需要200s，由此需要分布式存储和并行读取。其次，数据从存储服务器传输到计算服务器中将面临巨大的数据传输开销，由此最好能本地化数据的计算任务，通过子计算结果得到统一结果。

所以，大数据工程主要思想即是两点：第一，分发计算任务到分布式数据存储服务器；第二，收集计算结果统一处理。

数据库系统）。三篇论文分别对应三种问题的解决方案：分布式文件存储方法、分布式计算方法、数据库结构化方法。其中，GFS用于存储大量数据，BigTable将数据结构化为众多大表，优化查询数据的消耗。

分布式计算方法是大数据处理的核心。MapReduce 用于处理大量半结构化数据，类似于 SQL 对数据库的操作，其将分布式相关的操作封装起来，使得用户只需关注自己的任务。具体用户需要做的仅有两步：Map（将大量数据先处理成自己想要的相关数据的键值对集合），Reduce（整合这些相关数据中自己想要的值的集合）。

作为 key，food 作为 value 来处理数据，这种实现用户感兴趣数据的键值对映射操作称为 Map 操作。然后用户从键值对中取某 key，比如分析女性的食物倾向，那么 key(sex)=女性即可得到对应的 list(food)，限定 key 得到对应 value 的操作称为 Reduce操作。一项 MapReduce 任务即完成。

MapReduce 常用于创建索引，如计数 URL 访问次数，Map根据页面请求日志生成 URL - 访问次数键值对，Reduce得到各 URL 访问次数总和。又如反向索引任务，如某搜索关键字在哪个页面出现，Map 为每个页面生成单词 - 页面ID键值对，Reduce 整合某关键字得到 list(页面ID)。MapReduce 操作还需考虑分布式执行的问题，本文不详述了。

主要目的是支持以流的形式访问和写入大型文件，帮助数据存储在大量不同的机器上而用户无需关心存储的具体机器，只需使用 HDFS 路径调用即可。

• 分布式文件存储系统：HDFS 对应于GFS；
• 分布式数据批处理系统：Hive 对应于基于 MapReduce 算法的系统；

由于 Hive 使用 Hive SQL（HQL） 处理计算数据，我们也常常使用关系型数据库 MySQL 来组织数据。通常元数据（一些标记数据）存储在 MySQL 上，而数据文本（实际数据）存储在 HDFS 上，因此，HBase 在 Hive 体系中的使用就不是很多了。

MapReduce 的实现包括了一个资源调度框架和一个执行引擎，2012年，Apache 发布了 Hadoop Yarn 作为专门的通用资源管理系统，为上层应用提供统一的资源管理和调度。同年，伯克利为弥补基于 MapReduce 处理数据速度上的缺陷，开发了基于 Scala 语言的 Spark，可用 Java 操作。

DataSet，弹性分布式数据集）为核心的计算框架，虽然其主流的存储模式也是 HDFS，但其通过将 Map 过程统一起来，计算基于内存，达到加速10倍到100倍的效果，有替代整个 Hadoop 系的趋势。

然而，Spark 由于发展时间短，且对其关键优势的需求不大，所以发展不快，但其基于 RDD 的计算组件 Spark SQL 受到了较大认可，突出体现在性能、稳定性、标准兼容性上。而 Hive 较为成熟，所以 Spark SQL（RDD）常用于代替 Hive 的计算引擎 MapReduce，MapReduce 适合离线非实时数据的处理，而高实时性高速度场景的数据处理则常选用 Spark

分布式系统还需要一些基本组件。ZooKeeper 软件负责协调分布式系统中子节点 Workers 对主机 Master 的连接，比如 Master 故障时 ZooKeeper 可以切换备用 Master 来保证分布式系统的高可用。分布式通信则用消息队列完成，常用 Kafka，用于接收数据流，发送消息方称为生产者（Producers），接收方称为消费者（Consumers） ，队列以代理（Brokers）的形式，生产者按主题（Topic）写入消息，消费者按指定主题获取消息。

类似于 MapReduce 和 Spark 这种都属于批处理计算，这种计算处理的是历史数据，数据量较大、花费时间长，也被称为离线计算。针对的实时数据进行的计算称为流式计算，即把批处理计算的时间单元缩小到数据产生的间隔，这其中目前又分为处理时间段内事件流的 Spark Streaming 和处理每个事件的 Storm。Spark Streaming 在Spark 中，较为易用，延迟在秒级，而 Storm 是 Twitter 开源的，底层由 Clojure 语言实现，不好修改，能做到亚秒级的延迟。Storm、Spark Streaming 加上 Flink 即是当今主流的流式计算框架。

我们将在系列四文章中介绍大数据工程的一些基本实践。

字面上的人工智能指的是通用人工智能（Artificial general intelligence，AGI），现今语境下的人工智能是一个很大的领域，很少研究 AGI，其主要指的是机器学习以及其细分领域的深度学习和强化学习。

本章知识点：监督学习、无监督学习、强化学习、回归、分类、聚类、线性回归、多元线性回归、最大熵模型、逻辑回归、朴素贝叶斯、支持向量机、K-means、高斯混合模型、神经网络、计算机视觉、自然语言处理、序列决策问题。

机器学习看似是赋予机器学习的能力，本质上是统计学习的分支。机器学习主要用于数据分类或数据聚类，其算法主要分为三类：监督学习、无监督学习、强化学习，对应有标记、无标记、以及半标记。强化学习我们在后文详述。

监督学习接收样本和样本的标签或特征。这些标签或特征称为监督信息，与样本本身具有联系，计算机依靠一些优化算法将其规律近似拟合。无监督学习接收无标记的样本，无监督学习算法会隐式地描述如何衡量样本间的区别（如样本间距离），然后计算机根据算法按需求处理这些数据（如聚类或生成新的数据）。监督学习任务可分为两类：回归和分类。

回归指对规律散落的样本点，尽可能用一条直线或曲线让这些点尽量在这条线上或附近，根据这条线即可执行一些预测任务。回归被视为监督学习的原因是我们把样本点的一轴视为了自变量，而样本的其他轴视为了标签，它形式上更像是无监督学习中的聚类。典型算法有线性回归（Linear Regression）和多元线性回归（Linear Regression with Multiple

分类接收样本和样本的类别标签，计算机依据优化算法拟合样本和其标签的关系，根据该关系可对新样本进行分类。典型算法有基于概率的最大熵模型（Maximum Entropy Model）、逻辑回归（Logistic Regression）、朴素贝叶斯（Naive Bayes）等，和基于距离的支持向量机（Support Vector

8.2 深度学习与强化学习

Network）理论和近年算力突破得以发展。神经网络是构造一种复杂的非线性函数的方法，它通过每个神经元本身的非线性计算和海量神经元的组合使它足以表达极其复杂的映射关系，多层神经元的叠加即可获得一定深度的神经网络，基于这种神经网络的算法和应用称为深度学习。深度学习通过足量数据可以拟合几乎任何映射函数，因此刺激了计算机视觉（Computer

计算机视觉本质上即是令计算机识别图像中的信息，显然利用深度学习的类别映射能力可以提取图像信息，由此衍生出一些扩展。自然语言处理即是对语言数据的一些处理算法，如机器翻译需要建立一些复杂的映射，那么显然可以考虑使用深度学习强大的函数映射能力。深度学习的发展主要指各种模型结构（CNN、LSTM等）和算法（ResNet、BERT等）的发展，但与人类理解的智能有一定差距，其所谓的学习是指通过数学优化算法从数据中得出近似的拟合函数。

强化学习是机器学习中最接近 AGI 研究的领域。强化学习起源于控制论，用于处理序列决策问题，如著名的 AlphaGo。强化学习算法一般称为智能体，其依赖于一个环境运行，智能体与环境交互，获得环境的观测，根据自己的算法逻辑执行行为，并在一定程度的学习后使自己的行为朝着实现自己的目标改进。

我们在系列六和系列七文章中会详细描述强化学习完成序列决策任务的方式。