https://www.youtube.com/playlist?list=PLcQU3vbfgCc9sVAiHf5761UUApjZ3ZD3x
计算机使用有限比特来表示数字。这就导致整数运算可能会有下溢和上溢,产生意想不到的结果:
计算50000的平方,结果为负数。这是因为32位整数在这次运算中发生了上溢。
将300、400、500、600相乘,结果也不如预期。同样由于整数上溢导致。
然而,整数运算仍保留了結合律和交换律。
浮点数运算同样会有舍入误差。一个大数减去自身后加上3.14,是否得到3.14取决于运算顺序。这是因为在有限精度下,一个大数对最后结果的影响远大于3.14。
本课程旨在使学生能够:
更深入地理解程序在计算机中的执行情况
获取实用的程序设计技巧和方法
为深入掌握系统领域的后续专业课 laying 奠基
帮助学生成为更优秀的软件工程师
主要从以下几个“现实”角度进行:
通过深入解剖计算机系统的运行机制,帮助学生 deeper 理解程序如何在计算机上运行。
计算机中所有的数字都是通过一系列0和1来表示的,这些0和1称为比特(bit)。多个比特可以形成一个字节(byte)。
整数使用定位表示法来表示,每个不同位置的值代表不同的权值。最低位代表1,下一位代表2,然后4,8,16等2的幂次方。我们可以通过把对应的比特置1来表示该位置所代表的数。
浮点数使用类似的定位表示法来表示小数。小数点左边表示整数部分,右边表示小数部分。最低位代表0.5,然后0.25,0.125等negatives幂次方。
计算机内存中数字的存储顺序可以分为大端格式和小端格式。大端格式从高位字节开始存储,小端格式从低位字节开始存储。Intel处理器采用小端格式。
C语言中的基本数值类型包括:
C语言支持直接对位进行运算,常用操作符包括:
| :按位或 |
我们可以利用位操作来表示集合。每个位置的1与0可以表示该元素是否属于该集合。常用集合运算也可以利用对应的位操作来实现。
| 布尔逻辑使用 | && !进行逻辑运算。与位操作不同,它针对的是一个boolean值是否为true,而非比特的结构。0表示false,非0表示true。 |
| 位操作使用& | ^ ~进行按位运算,它考虑比特的真值结构。 |
不能把这两种操作混为一谈,否则会导致错误。
溢出也可以用坐标系表示,有正确区域和两种溢出区域。
计算机系统中使用浮点数表示法来表示实数。浮点表示法与科学计数法类似,使用以下格式:
-1^s × m × 2^e
其中:
IEEE754标准定义了32位和64位浮点数格式:
32位单精度:1位符号位,8位指数字段,23位尾数字段
64位双精度:1位符号位,11位指数字段,52位尾数字段
指数字段使用偏移编码,实际指数e等于指数字段值exp减去偏移量。单精度偏移量为127,双精度为1023。
尾数字段的值m与实际有效数字之间存在偏差。通过指数可以获得准确的值:
m × 2^e
尾数大于1小于2,采用此范围可以保证数值的唯一性。
IEEE754标准统一了浮点格式,使不同平台运算结果一致。
本课将介绍机器级编程的概念。机器级编程指考虑单个机器指令的执行,以及对机器响应程序的理解。机器级程序主要有两个形式:
对象码:运行在计算机上的二进制机器码序列。
汇编语言:人类可读的文本形式机器指令。
由于直接查看机器码难以理解,汇编语言被用于使机器码更易理解。
本课程将以X86(英特尔)为例研究机器级编程。不同于过去需要学习汇编编程的课程,本课程主要从编译器生成的汇编中学习,理解高级语言如C到机器码的转换过程。
X86指英特尔早期8086、286、386等微处理器系列。1980年代80386引入32位处理能力,使X86成为Unix/Linux系统的主流平台。目前主流64位处理器可以运行32位代码。2004年后,英特尔不能再通过提升时钟频率提高单核性能,转而采用多核CPU设计。
本次课将介绍X86指令集架构历史、 C代码如何转换为汇编与机器码、汇编语言基础知识以及通过示例学习算术运算在机器级的实现。
x86处理器有四个1位条件标志寄存器,分别是:
条件码通过比较指令(CMP)和测试指令(TEST)设置。CMP实现两个操作数相减但不保存结果,只设置条件码。TEST实现一个操作数与自己进行与操作(结果不变),也只设置条件码。
通过读取条件码完成条件跳转:
通过条件跳转实现if语句内的语句块:
通过重复设置条件码和条件跳转实现while循环:
以上实现了机器指令级while循环的基本框架。
调用过程时,程序需要跳转到过程代码执行。结束后需要返回调用位置。为此需要记录返回地址信息。
调用过程需要传递参数,过程内也可能返回值。需要记录参数值供过程使用,并返回值给调用者。
过程可能需要额外存储空间保存本地变量值。需要分配和释放该存储区域。
C语言常见地以小函数划分任务。但是过程调用成本不应过高。x86架构尽可能降低过程调用开销,仅实现必要操作,减少不必要操作带来的额外步骤。
过程调用使用栈管理信息。栈并非特殊内存,是普通内存的一块区域。栈指针寄存器rsp指向当前栈顶。增加栈使用减小rsp,以LIFO方式管理信息。
栈长按低地址到高地址编号。但是习惯上以低地址为顶部展示栈。增长栈使用减小指针值。
call指令实现过程调用,跳转到过程代码执行。return指令从过程返回。push和pop操作数入栈/出栈。其它指令模拟也可实现,但调用/返回需专门指令支持。
函数调用遵循应用二进制接口规范,详细定义各操作系统下函数调用细节。实现最小开销调用。
过程调用涉及控制流变迁、参数传值、本地存储分配等问题。x86架构通过栈implicit函数调用,实现高效函数接口。
如果一个数组包含n个元素,其类型为t,那么该数组需要的内存大小就是元素数量n乘以单个元素类型t的大小。
例如:
数组在内存中以连续的内存块的形式存储,可以通过基地址(数组名)加偏移量的方式访问单个元素。
结构体让多个不同类型的数据组合在一起,每个成员通过其名称或标签进行访问。
结构体在内存中也只是一段连续的内存块,各成员按声明次序存储。访问结构体成员时,编译器会自动计算相对基地址的偏移来获取正确值。
结构体定义也可以递归,可以有数组结构体或者结构体数组成员。
在C语言中,数组名称实际上等价于指向数组首元素的指针。
可以用数组下标或 pointer arithmetic 两种方式访问数组元素:
在机器级别,数组和结构体都只是一段连续的内存块。C编译器生成的代码负责正确分配内存和计算偏移获取各元素。这 fully 使用了指针算术的特性,让数组和结构体得以实现。
在计算机内存中,从机器层次来看,内存就是一个字节数组。这种看法对机器级编程来说是最直接的。但是实际内存的实现机制比这复杂得多,包括磁盘存储、固态硬盘和DRAM等不同类型的内存,以及虚拟内存等管理机制。
x86_64体系结构支持64位地址空间,理论上可以支持2^64字节的地址,约为16万亿亿亿字节。但是实际硬件限制只支持47位地址,约为128TB范围内。这已经是一个非常大的地址空间了。随着技术发展,地址范围能够扩大。
Linux系统中,栈通常设置在地址最高的位置。栈向下增长,最大限制为8MB。代码和数据会设置在地址较低的位置。代码区域称为text段,数据分为已初始化数据段和堆内存两部分。堆内存在运行时动态分配。静态库和动态链接库代码也会加载到内存中。
缓冲区溢出是一种常见的安全漏洞。当向缓冲区写入数据超过其范围时,会覆盖相邻的内存单元,可能会影响程序执行。攻击软件可能利用这一点写入恶意代码,以实现代码执行或提升权限。
union可以将相同内存空间定义为不同类型,不同成员会共用同一内存块。修改一个成员可影响另一个成员的值。它可以用于数据打包或类型转换,但需谨慎使用,容易产生隐含行为。
新的攻击实验室实验将在今天午夜开放。它会要求学生利用缓冲区溢出漏洞来进行攻击。这对课程是一次重要的更新。鉴于大规模学生参与,实验过程中可能会出现各种问题,需要密切关注。实验只有一个半周的时间限制,所以尽早着手是非常重要的。
现代编译器通过优化策略和各种优化手段,可以帮助程序运行更快,无需编写汇编代码。
GCC是开源且免费的优化编译器,可以达到很好的优化效果。Intel编译器性能可能更好,但需要授权费用。
编译器优化原理是采用 cookbook 中的各种优化策略尝试,如果觉得代码难以优化,就不进行优化保守执行。
程序员可以通过观察源代码是否优化,协助编译器进行优化,比如重写更友好的代码。
对多维数组做索引时,可以将计算行或列数乘上数组大小的操作提出循环外 prest。
乘常数也可以转成移位和加法规避乘法开销,例如乘以数组大小 n 可以转成加n。
将相似但不同的计算表达式合并,比如四个方向站点计算只需一个乘法而不是三个。
将表达式计算结果缓存避免重复计算。
减弱算术,将乘法转化成加法运算等。
识别程序中的模式规避冗余计算。
调整数据结构和算法提高局部性,减少缓存失效。
考虑特定硬件指令集优势进行代码转换,但不宜过于针对单一平台。
适度重写更简洁高效的源代码给编译器提供优化空间。
存储技术的特性如成本、大小、速度决定其应用场景。程序的局部性原理使CPU与不同层次存储器建立等级结构,充分利用各层存储器优点,缓解速度差异带来的性能损失。
记忆体的等级结构包括不同的存储设备,从上到下逐步减小速度和增加容量。每个级别的存储器都存储着下一个级别存储器的一部分数据块,作为上一级别存储器的缓存。
将主存 arbitrarily 分割成多个数据块,缓存则存储其中的一部分块。当 CPU 访问某个数据时,缓存首先检测是否包含该块,如果包含则命中(hit),否则未包含则缺失(miss)需要从主存中搬入该块。
所有缓存都采用同样的组织结构:
CPU 向缓存发送地址,缓存将地址分解为块偏移、集索引和标签。根据集索引定位集,然后结合标签和有效位判断是否命中。如果命中则基于块偏移返回数据,否则发起磁盘读操作。
简单情况下每个集只包含一个线,即 E = 1。地址分解后,集索引直接定位集,然后判断标签和有效位是否匹配。如果匹配返回数据,否则发起读操作。
缓存利用局部性原理,在 CPU 中加入小容量高速缓存,缓解主存访问延迟。缓存采用固定组织结构,通过地址分解快速定位数据。读操作先从缓存查找,如果未命中则向主存请求数据。这实现了高速访问常用数据的目的。
现今的计算机处理器芯片上通常会集成多个独立的 CPU 核心。每个核心上都有私有的高速缓存,同时还共享较慢的主存。
处理器上不同核心的运行基本互不影响。但为充分利用多核资源,需要把一个程序切分成多个线程,分别运行在不同核心上,实现并行计算。
超线程技术(Hyper-threading)旨在更充分利用每一个核心资源。它允许同时运行多个线程,共享核心的控制逻辑和执行单元。
每个核心实质上模拟成两个逻辑核心运行。两个线程互不影响,但通过时间分片实现资源共享,从而提高利用率。不过实际效果并不明显。
要利用多核环境实现程序并行加速,需要每个线程分解独立的计算任务,互不干扰。
比如,整体求和可以分解成不同区间求和的子任务,分配给每个线程计算,然后汇总结果。但写出高效并行程序往往非常困难。
还需要注意多线程访问共享内存时可能产生的混乱问题,如冲突、阻塞等。正确管理共享资源尤为重要。
视频给出一个利用多线程求0到n-1之间所有数和的简单案例。
把求和范围均匀分割成多个区间,分配给多个线程同时计算。每个线程运行独立,最后再汇总各个线程结果即可得到总和。
这个例子理论上可以发挥多核系统并行计算能力,但对实际性能提升贡献有限。它仅用于演示多线程并行思想。
程序可以用多个源文件(.c文件)编写,每个源文件代表一个模块。这样可以把相关的函数组织到同一个源文件中,形成更好的结构。
分离编译能使编译效率更高。如果只改动了一个源文件,只需重新编译这个源文件而不是全部源文件。
每个源文件(.c文件)通过预处理器、编译器和汇编器三个阶段编译为可重定位对象文件(.o文件)。
链接器主要完成两个任务:
符号解析:将程序中定义和引用的符号(如函数、变量)匹配关联起来。
重定位:将所有的模块合并为单个可执行文件,并确定每个符号最终在内存中的位置。
对象文件采用ELF二进制格式,包含头部、节表、代码节(.text)、只读数据节(.rodata)等结构。
可重定位对象文件(.o文件):输出自汇编器,需要链接器处理。
可执行对象文件:链接完成后的文件,可以直接加载运行。
共享对象文件(.so文件):创建动态链接库。
所有对象文件都采用ELF结构,包含头部信息和定义各种结构如代码、数据等节的结构。
异常控制流是系统状态变更导致的控制流变化。它存在于系统的各个层面:
硬件层面,通过异常机制改变控制流来响应系统事件。
操作系统层面,如进程上下文切换改变了正在执行的进程。
软件层面,如信号机制和C语言的非局部跳转。
异常控制流机制允许系统适应系统状态的变化,如I/O完成、用户输入、非法指令等。
异常是控制流从用户代码转移到内核代码的事件。内核包含异常处理程序来响应系统事件。常见事件包括:
中断:由处理器外部的事件引起,如定时器、I/O完成。
陷阱:由程序主动引起,如系统调用。
错误:如页错误,保护错误等。
异常通过硬件和操作系统软件实现:
硬件通过异常号索引异常表,转到对应异常处理程序。
操作系统设置异常表和处理程序。
异常处理后可能重新执行当前指令、跳到下一个指令,或终止程序。
异步异常源于处理器外部事件,如定时器中断。
同步异常有三类:
陷阱:由程序主动引发,如系统调用。
错误:如页错误,可能可恢复。
终止:如非法指令,不可恢复。
异常机制实现了系统在各个层面响应状态变更的异常控制流。
在Linux系统中,唯一创建新进程的方法是使用fork系统调用。当系统初始化时,会创建init进程,其进程ID为1。init进程会再创建一些长期运行的守护进程,例如Web服务器等。之后会创建登录Shell,为用户提供命令行界面。当用户登录后,得到的就是一个登录Shell。
Shell是一种应用程序,收到用户输入命令后,会解析命令行,将命令和参数分离。如果命令是内置命令,Shell本身就会执行;如果不是,Shell会fork一个子进程来执行该命令。子进程通过execve系统调用执行命令,execve返回后,子进程被替换为指定命令。如果命令在前台运行,Shell会调用waitpid等待子进程结束后再继续;如果在后台运行加&符号,Shell直接继续下一循环而不等待。
但是,这样做存在问题:后台任务完成后,Shell不会等待和回收它,可能导致内存泄漏崩溃。
信号是Linux内核为通知某个进程发生事件而发送的一小消息,它只包含一个唯一ID号。内核可能在自己观察到事件时发出,也可能由其他进程请求内核发送给某个进程。
SIGINT:控制台发送中断信号,如Ctrl+C,默认终止进程。SIGKILL:强制终止任何进程,无法捕获。SIGSEGV:段错误,访问非法内存时发送。SIGALRM:设置定时器,超时后自己发送。SIGCHLD:子进程结束时内核发送给父进程。
当子进程结束时,内核会向父Shell发送SIGCHLD信号。Shell收到这个信号后,知道有子进程结束了,于是调用waitpid()系统调用回收子进程资源。这样就解决了Shell不等待后台job的问题。
通过setjmp和longjmp函数,C程序可以实现类似异常的非局部跳转功能。我们不详细介绍它,有兴趣的同学可以参考课件和教材。
文件在操作系统中是一组二进制流,无论是文本文件还是二进制文件在系统中都是同样的数据结构。文件可以存储在硬盘上,也可以用于网络通信或连接设备等。
文件主要操作包括:打开、关闭、读写。打开文件后会关联一个文件位置指针记录已经读写了多少字节。大多数文件都支持文件位置指针,但终端和网络套接字不支持。
文件类型主要有:
输入输出的最低级操作直接与操作系统交互,主要包括如下:
标准输入输出(stdin、stdout、stderr)本质上也是文件,但处理方式不同。
buffered I/O 是更高级的输入输出方式,通过内存缓冲提高效率。例如printf、scanf都依赖于buffered I/O。
RIO(Robust I/O)库提供更高可靠性的输入输出功能。它封装了低级I/O操作,增加了错误处理等机制。此库源代码结构清晰, Worth学习。
FUTURE 课程后期的网络代理小工程会使用到RIO库。学习本节内容有助于理解系统编程模型与接口。
虚拟内存是计算机系统中一种重要的概念。它通过MMU(内存管理单元)对CPU产生的虚拟地址进行地址转换,将虚拟地址转换为物理地址。这使得系统可以在主存和次存之间实现数据缓存,提高系统资源利用率。
虚拟内存的主要优点:
可以将磁盘作为内存的缓存使用。程序运行时,频繁访问的数据被缓存在内存中,这就像CPU缓存一样提高了性能。
简化内存管理。每个进程都有一个标准的、相对固定的虚拟地址空间布局,这样管理就更简单了。
实现地址空间的隔离保护。每个进程都有独立的虚拟地址空间,互不影响。
地址空间:其实是一个地址的集合,包含所有可能访问的数据地址。
虚拟地址空间:所有进程共用的线性地址空间,范围为2的N次方个虚拟地址。
物理地址空间:与系统主存大小对应,范围为2的M次方个物理地址。一般M小于N。
页面:虚拟内存使用页面作为基本缓存单位,一般4KB。
将整个虚拟内存看作一个连续的字节序列,保存在磁盘中。这些虚拟页面根据访问情况缓存在主存中。MMU会将虚拟地址转换为对应的物理地址。
主要流程:
CPU执行指令产生虚拟地址。
虚拟地址通过MMU地址转换成对应的物理地址。
内存根据物理地址访问数据,返回CPU。
主存中的虚拟页面实际上可以映射到任何物理地址位置。
未访问的虚拟页面仍在磁盘,访问时需要带来较大开销。
如此,利用局部性原理,可以高效利用有限的主存资源。
本次课程将介绍虚拟存储系统及地址翻译工作原理。
虚拟存储系统通过将物理地址空间分割成页面,并将虚拟地址空间映射到物理地址空间实现,可以将读写操作从物理硬件层抽象到虚拟层,进而实现进程隔离和内存空间共享。
地址翻译通过TLB和页表实现。TLB用于缓存页面表项,提高访问效率。
页表由页面表项构成,每个页面表项都包含物理页面号和有效位。当虚拟地址未在TLB中命中时,需通过虚拟页号查找页表获取相应页面表项。
将虚拟地址中的偏置位不变,将虚拟页号对应页表项中的物理页号拼接即得到物理地址。
假设CPU执行指令生成虚拟地址0x03d4:
假设CPU执行指令生成虚拟地址0x0020:
以上两个例子详细说明了地址翻译的工作流程。
操作系统使用虚拟存储器机制向进程提供一个大型连续字节数组作为程序的地址空间。但是,程序在运行时才能知道实际需要分配多大内存。这就需要动态内存分配机制。
动态内存分配机制让应用程序在运行时动态地分配和释放内存块。在C语言中使用malloc()函数分配内存,使用free()函数释放内存。其他语言如Java也支持new等函数分配内存。
分配的内存存放在一个叫做堆的虚拟内存区域。堆上管理着一系列可分配和可释放的内存块。应用程序可以通过malloc函数分配块,通过free函数释放块。
内存分配器维护堆作为一系列连续的内存块。块可以处于分配状态或可用状态。分配表示程序正在使用该块,可用表示该块可以供程序使用。
内存分配器根据应用程序的malloc和free请求进行内存块的分配和回收。由于无法预测应用程序的需求,分配器必须尽快响应请求。同时也要高效利用内存空间。
分配器操作时遵循若干约束:只能从空闲块中分配,不能移动或压缩已分配块,块需对齐等。这使得分配器的设计需要平衡速度与空间利用率两方面。
以C中malloc和free为例。malloc根据大小返回可用内存块的指针。free根据指针回收对应块。
通常采用First Fit、Best Fit或Worst Fit等策略分配内存。First Fit检查可用块列表第一个是否足够,以下类推。Best Fit选用刚刚足够的块,Worst Fit选最大的块。
当没有足够大的可用块时,需要通过sbrk系统调用增加堆的大小,然后找到一个可用块分配。这往往是分配速度的一个瓶颈。
使用空闲列表跟踪可用块可以提高分配效率。同时要考虑内碎片问题,多次分配释放可能导致许多小块,降低利用率。高效的内存分配器需要在速度和利用率上取得平衡。
在动态内存分配中,可以使用显式双链表来管理空闲块,为每个空闲块设置前后指针链接成链表。
空闲块内部可以设置这些链表指针,而非像隐式方式那样需要扫描整个堆找空闲块。
这样管理方式下,空闲块可以分散在内存任意位置,被分配出去的块和空闲块外观上没有区别,只有在内部设置了不同的链表指针。
定义峰值内存利用率uk来测量动态内存分配效率。
uk是指到第k+1个请求结束时,所有请求产生的总负载块最大值与堆大小的比值。
其中,总负载块是从第一个请求开始,累加所有负载块的大小。假设有无限优化能力,这个值就是理论最小需要的堆大小。
uk取所有历史请求的最大总负载块与当前堆大小的比值,用来评估分配效率。
如果在两个空闲块之间释放一个块,需要合并这三个相邻块成为一个更大的空闲块。
尽量保持被分配出去的块及空闲块列表被放在同一内存页,以提高缓存局部性。不过动态内存分配困难保证这一点。
如果程序能向分配器提供一些使用模式提示,比如即将大量分配多个小块,分配器可能会优化分配策略,从而提高利用率。但这不是通用分配方式。
本节介绍了用显式双链表实现更高效的空闲块管理,以及利用峰值内存利用率uk来评估分配效率,并简要讨论了如何提高缓存局部性和利用程序使用提示来优化分配。
网络系统的设计理念主要是基于客服模式。客户端向服务器发出请求,服务器处理请求并返回结果。典型的例子包括我们在亚马逊下订单,通过浏览器向亚马逊服务器发起请求,服务器处理交易并返回商品图片等信息。电话也可以看成是一种客服模式,打电话的一方是客户端,接电话的一方是服务器。
计算机与网络的连接口称为网络接口卡(NIC),即使它不一定是物理卡形式。从计算机的角度看,网络就像一个IO设备,写入的数据视为发往网络,读取的数据视为从网络接收。这与硬盘IO读写类似。
网络系统通过IP地址识别主机。IP包通过多个路由器从源地址传输到目的地址。路由器根据IP地址进行转发,实现不同网络之间的通信。这使得世界各地主机都能相互连接,形成一个庞大的网络结构。
以太网是低层网络传输的主流技术。但以太网概念已经扩展很广,实际上它实现了不同网络之间的连接。以太网最初通过同轴电缆实现广播式网络传输。现在则经常通过交换机实现定向传输。通过交换机和多层路由可以构建更大规模的局域网。
因特网指的是一个网络相互连接形成的更大网络结构。为了让各种不同系统互相通信,必须采用公认的网络协议。协议规定了消息格式、传输机制、错误处理等规则,使得任何遵守该协议的系统都能在同一网络结构中运行。网络协议的标准化实现了不同系统之间的交互。
本节讲解域名到IP地址的转换。域名是用来表示计算机的友好名称,如www.cmu.edu。而IP地址是网络中的唯一标识,用于定位计算机,IPv4地址是一个32位数字,通常用十进制点分式表示,如192.168.1.1。
域名到IP地址的转换是通过DNS系统实现的,运营商部署了DNS服务器,用户查询域名时,DNS服务器根据域名数据库返回对应的IP地址。
上节介绍了Host info程序,用于通过命令行输入域名,打印其IP地址。本节修改程序可以支持IPv4和IPv6地址。
Host info程序使用getaddrinfo()函数实现域名到地址的转换。getaddrinfo()是获取地址信息的统一接口,支持IPv4和IPv6,通过输入域名字符串或IP地址字符串即可获取对应的socket地址结构。
socket地址使用struct sockaddr表示,根据地址类型不同有IPv4和IPv6版本。获取地址信息后会返回一个链表,因为一个域名可能对应多个IP地址。程序使用结果后需要调用freeaddrinfo()释放内存。
getaddrinfo()函数有多个参数:
hints可以指定条件,如是否支持IPV6。结果链表每个节点是struct addrinfo结构,包含地址长度、类型、通用socket地址等字段。
程序从结果链表中遍历节点,打印对应类型的IP地址字符串。这样可以同时支持域名到IPv4/IPv6地址的转换。
本节主要介绍了如何通过修改Host info程序支持IPv4和IPv6地址,利用getaddrinfo()统一接口实现域名到地址的转换。getaddrinfo()可以根据输入条件返回符合条件的所有结构,支持同时查找IPv4和IPv6地址。程序需要释放结果链表内存。
这周我们将学习如何将并发性纳入程序设计。我们之前已经在进程和信号处理程序中看到过并发性。进程可以作为运行多个独立应用程序的机制。
并发也存在于应用程序中。我们在学习信号处理程序时也看到了一些应用。信号处理程序是一个与主程序并行运行的并发流。
我们已经看到,当引入并发时会带来困难。即使是一个简单的信号处理程序,我们也很难推理其行为,因为我们的大脑更习惯顺序推理。而处理多个流同时进行的交织行为就更难推理了。
当多个流访问共享资源时,很容易出现问题:
竞争发生:程序的结果取决于一个随机的调度决定。
死锁:多个流等待一个永远不会发生的事件。例如在信号处理程序中使用printf。
活命问题:完成工作的进程受阻,无法完成任务。
公平性问题:系统资源不公平分配。
可能出现无限等待或饥饿现象。
这些问题历史already been extensively studied in computer science due to their complexity in reasoning about all possible interleavings of concurrent flows.
我们用服务器作为示例来研究应用级并发。任何一个服务器都必须采用并发来实现。
之前我们看过的服务器都是迭代的:处理一个客户端请求后再处理下一个。但是这会出现问题:
如果一个客户端长时间阻塞服务器的读操作,那么其他客户端都无法得到服务。这对其他客户端是不公平的,也可能导致系统僵死。
为解决这个问题,我们需要使用并发来处理多个客户端请求。服务器可以:
在接收新的连接请求时创建一个新的线程或进程处理这个请求。
主循环可以专注于监听连接,接受请求后通过通道发送给工作线程进行处理。
工作线程负责读取数据,处理请求并返回结果。主循环再接着监听连接。
这样每个客户端连接都有独立的线程进行数据读写,一个长时间阻塞的请求将不会影响其他客户端。这才是可靠高效的并发服务器的设计。
总之,理解并发仍然很困难,但我们会学习一些原则来正确地使用它。服务器设计是一个很好的用例,可以帮助我们理解应用级并发的设计思路。
信号量是一个非负的全局同步变量,通过P和V操作来操作。P操作如果信号量的值不为0就减1,否则阻塞。V操作增加信号量的值,并唤醒阻塞在P操作的线程。
互斥锁保护临界区内的共享变量,通过P和V操作信号量来实现保护。初始化互斥锁信号量为1,然后用P和V把临界区包围起来。
同步机制保证信号量的值永远大于或等于0。
包含一个有限缓冲区作为共享资源。生产者线程产生对象放入缓冲区,消费者线程从缓冲区取出对象并处理。
使用两个计数信号量来跟踪缓冲区空slot和已产生对象的个数。生产者等待slot,消费者等待对象。
生产者放入对象后将对象信号量加1通知消费者,消费者取出对象后将slot信号量加1通知生产者。
GUI事件处理也可以用这个模式,鼠标/键盘事件通过队列传给界面绘制线程处理。
使用数组实现有界缓冲区,前后指针表示队首队尾
初始化互斥� genpyhon来保护共享缓冲区
初始化slot和item计数信号量
生产者插入对象前P slot等待,放入后V item通知
消费者取出对象前P item等待,取出后V slot通知
保证任意时刻slot和item之和不超过总缓冲区大小