程序的机器级表示

调用者保存与被调用者保存

调用者保存：在函数执行前将寄存器内容进行保存，执行完毕后将寄存器内容恢复

被调用者保存：函数执行开始时将寄存器内容保存，函数执行到最后将寄存器内容恢复调用者保存与被调用者保存

磁盘相关计算

磁盘对扇区的访问有三个主要的部分：寻道时间、旋转时间、传送时间。

寻道时间:传送臂将读写头定位到目标扇区上移动的时间

旋转时间：驱动器等待目标扇区的第一个位旋转到读写头下。最大延迟是Tmax rotation=1/RPM*60s/1min（旋转速率通常给的是每分钟转多少圈），平均旋转时间为最大旋转时间的一半。

传送时间：一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目

Cache（高速缓冲存储器）

解决CPU和主存间出现的空等问题。

程序访问的局部性原理：（1）时间的局部性：当前使用的数据，将来可能再次被使用（2）空间的局部性：当前使用的指令和数据，之后相邻的指令和数据可能会被用到。

工作原理

主存和缓存按块存储，块的大小相等。

（2）命中和不命中：缓存有C块，主存共有M块 M>>C

命中：主存块调入缓存

主存块与缓存块建立了对应关系

用标记记录与某缓存块建立了对应关系的主存块号

当程序需要k+1层的某个数据对象d是，首先在当前存储在第k层的一个块中查找d。如果d刚好缓存在第k层中，那么就称为缓存命中。该程序直接从第k层读取d，更具存储器层次结构的性质。

未命中：主存块未调入缓存

主存块与缓存块未建立了对应关系

如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中。当发生缓存不命中是，第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块。

（3）命中率：CPU想访问的信息在Cache中的比率，与Cache的容量与块长有关（容量成正相关，块长要适中），

块长取一个存取周期内从主存调出的信息长度。

（4）主存系统的效率

效率与命中率有关

e=访问Cache的时间/平均访问时间

最小值为tc/tm,最大值为1。访问Cache和主存是并行的。

读写操作

读

步骤：cpu发出访问地址，如果命中，访问Cache取出信息送cpu里，如果没有命中，将要访问主存，取出信息送cpu里，同时还要确认Cache是否已经满了（系统允许放的Cache空间），如果没满，将新的主存块调入Cache中，如果满了，进行替换（替换算法）。

写

要同时写Cache和主存，Cache和主存的一致性。

（1）写直达法：写操作时数据既写入Cache又写入主存，写操作时间就是访问主存的时间，Cache块退出时，不需要对主存执行写操作，更新策略比较容易实现。（缺点：会反复从Cache写入主存，耗费时间）

（2）写回法：写操作时只把数据写入Cache而不写入主存，当Cache数据被替换出去时才写回主存。（缺点：可能造成Cache和主存数据内容不一致，多处理器下，可能造成多个处理器Cache副本不一致）

对Cache改进

（1）增加Cache的级数

片载Cache

片外Cache

（2）统一缓存和分立缓存

指令Cache 数据Cache

主存的地址映射

（1）直接映射

主存块只能放入一个Cache块中

（2）全相联映射

主存块可以放入任意一个Cache块中

（3）组相联映射

给Cache分区，主存块映射到对应区进行操作

替换算法

（1）先进先出算法

（2）近期最少使用算法

Cache计算相关

一般而言。高速缓存的结构可以用元组（S,E,B,m）来描述。高速缓存的大小C指的是所有块的大小的和。因此，C=SEB，m是存储器地址的位数，S为高速缓存组，每个组包含E个高速缓存行，每个行是有一个B字节的数据块组成的。

高速缓存存储结构

在代码中，循环是 for (i = 0; i < N; i++)，这意味着程序是按顺序访问数组的：先访问 v[0]，然后 v[1]，接着 v[2]，以此类推。这种顺序访问的方式，在计算机科学中被称为“步长为 1”的引用模式。它是最“高速缓存友好”的，因为它充分利用了空间局部性（Spatial Locality）。

计算机并不是一次只从内存里取一个整数，而是每次取一个块（Block）。

对于一个步长为k的引用模式，平均每次循环迭代会有min(1,(wordsize*k)/B)此缓存不命中。当k=1时，取最小值，步长为1的引用是高速缓存友好的。假设v是对齐的，字为4个字节，高速缓存快为4个字，而高速缓存初始为空，无论是什么样的高速缓存结构偶，对v的引用都会得到下面的命中和不命中模式：

引用模式

访问 i=0 时： 缓存里啥也没有。不命中 [m]。CPU 于是去内存抓取一个块，这个块不仅包含了 $v[0]$，还顺便把相邻的 v[1], v[2], v[3] 都带进缓存了。

访问 i=1, 2, 3 时： 发现已经在缓存里了！命中 [h]。速度极快。

访问 i=4 时： 刚才那个块用完了，缓存里没有 v[4]。不命中 [m]。CPU 再次去内存抓取下一个块（包含v[4], v[5], v[6], v[7]）。

访问 i=5, 6, 7 时： 又是一波命中 [h]。

对一个N*N矩阵求和：

模式A：行优先访问

for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        sum += a[i][j]; // 步长为 1 (Stride-1)
    }
}

模式B：列优先访问

for (j = 0; j < N; j++) {
    for (i = 0; i < N; i++) {
        sum += a[i][j]; // 步长为 N (Stride-N)
    }
}

行优先的话步长为1，列优先的话步长为N，如果N足够大，不命中率为100%，空间局部性行优先的模式远高于列有先。

控制流相关

异常

异常控制流的一种形式，一部分由硬件实现，一部分由操作系统实现。异常就是控制流中的突变，响应处理器状态中的某些变化。

异常处理

异常都分配了一个唯一的非负整数的异常号。运行时，处理器检测到事件，确定了异常号，随后触发异常，通过异常表的条目，跳转到相应的处理程序。
异常号是异常表中的索引。异常表的起始地址放在了一个叫异常表基址寄存器的特殊CPU寄存器中。

异常的类别

异常的类别：中断、陷阱、故障、终止四类
中断：唯一一个异步发生的异常，是来自处理器外部IO设备的型号的结果，硬件中断的异常处理程序常常称为中断处理程序。
同步发生的异常类型是执行当前指令的结果。叫做故障指令。
陷阱和系统调用：陷阱最重要的用途是给用户程序和内核之间提供一个想过程一样的接口，叫做系统调用。

用户需要向内核请求服务，比如read，fork，execve（加载一个新的程序），exit（终止当前进程）,为了允许对这些内核服务的受控的访问，处理器提供了一条特殊的syscall n指令,
当用户想要请求服务n时，可以执行这条指令。这条指令会导致一个到异常处理程序的陷阱，这个处理程序解析参数，并调用适当的内核程序。系统调用和函数调用的区别：普通函数运行在用户模式中，可执行的指令类型有所限制，只能访问与调用函数相同的栈。系统调用运行在内核模式中，内核模式允许系统调用执行特权指令，并访问定义在内核中的栈。

故障：错误情况引起，可能被故障处理程序修正。如果程序能修正，就将空置房回到引起故障的指令，否则处理程序返回到内河中的abort历程，abort例程会终止引起故障的应用程序。经典的故障示例就是缺页异常，一个页面就是虚拟内存的一个连续的块，缺页处理程序从磁盘加载适当的页面，然后将控制返回给引起故障的指令。当指令再次执行时，相应的物理页面已经驻留在内存中了，指令就可以没有故障地运行完成了。

终止：是致命错误造成的结果，通常是硬件错误，处理程序将控制返回到一个abort例程，abort终止应用。

进程

执行中程序的实例。系统中的每个程序都运行在某个进程的上下文中。

逻辑控制流
并发流
私有地址空间

用户模式和内核模式

处理器提供了一种机制，限制一个应用可以执行的指令以及它可以访问的地址空间范围。处理器用了某个控制寄存器中的一个模式位来提供这种功能。该寄存器描述了进程当前享用的特权。设置了模式位时，进程就运行在内核模式中（超级用户模式）。一个运行在内核模式的进程可以执行指令集中的任意指令，并且可以访问系统中任意内存位置。
没设置模式位时，进程就运行在用户模式中，用户模式中的进程不允许执行特权指令。

进程控制

获取进程ID

使用getpid获取进程的id，getppid获取当前进程父进程的id

创建和终止进程

利用fork函数创建一个新的运行的进程，fork函数特点：调用一次，返回两次。一次是在父进程中，一次是在子进程中，父进程中会返回子进程的pid，而子进程中会返回0，如果创建子进程失败则返回负数（-1），子进程得到与父进程用户级虚拟地址空间相同的一份副本，，子进程可以读写父进程中打开的任何文件，子进程会从父进程创建它的地方开始继续执行。父进程于子进程之间的最大区别在于他们的pid不同。

两者是并发执行的，内核能够以任意方式交替执行他们的逻辑控制流中的指令。但是不同的系统中二者的执行顺序可能有所不同，也就是说无法判断二者具体的执行顺序。

相同但是独立的地址空间。二者的都有私密的地址空间，对变量的操作不会反映在另一个进程中。

共享文件。

回收子进程

当一个进程由于某种原因终止时，内核并不是立即把他从系统中清除。进程会保持在终止的状态下，直到被他的父进程回收。一个终止但还未被回收的进程称为僵死进程（zombie）。

父进程如果没回收子进程就终止了的话，内核会安排init进程去回收，init是所有进程的祖先，pid=1，永远不会终止，进程回收可以调用waitpid函数进行终止。

wait函数：waitpid的简单版本，用wait相当于回收父进程的所有子进程，也就是waitpid第一个参数为-1。

程序不会按照特定的顺序去回收子进程。子进程回收的顺序是这台特定的计算机系统的属性。

进程休眠

sleep函数实现

加载并运行程序

execve调用一次从不返回，加载文件路径。

信号

常见的SIGINT(来自键盘的中断) SIGILL（非法指令） SIGSEGV（非法内存引用） SIGKILL（杀死进程） SIGCHLD(子进程终止时发送给父进程)

发送信号

进程组：每个进程只属于一个进程组，进程组是有一个正整数ID来表示的，getpgrp函数返回当前进程的进程组ID

1 2	#include<unistd.h> pid _t getpgrp(void);

默认一个子进程和他的父进程属于一个进程组，一个进程可以通过set-pgid函数来改变自己或者其他进程的进程组，将pid加入pigd的进程组中

1 2	#include<unistd.h> int setpgid(pid_t pid,pid_t pigd);

用/bin/kill发送信号。

从键盘发送信号。

用kill函数发送信号

#include<sys/types.h>
#include<signal.h>

int kill(pid_t pid,int sig);

如果pid>0，就将sig信号码发送到pid对应的进程，如果pid=0，就将信号码发送到该进程所在进程组中所有进程，包括调用进程本身，如果pid<0，kill发送sig给进程组|pid|中的每个进程。

用alarm发送信号

1 2	#include<unistd.h> unsigned int alarm(unsigned int secs);

接收信号

当内核把进程p从内核模式切换到用户模式时，会检查进程p的未被阻塞的待处理信号的集合。

进程可以通过signal函数修改和信号相关联的默认行为。SIGSTOP和SIGKILL的默认行为不能被修改。

1
2
3

#include<signal.h>
typedef void (*sighandler_t)(int);
sighandler_t signal(int signum,sighander_t handler);

如果handler使SIG_IGN，那么忽略类型为signum的信号。

如果handler使SIG_DFL，类型为signum的信号行为恢复为默认行为。

否则，handler就是用户定义的函数的地址，在这个函数被称为信号处理程序，只要进程接收到一个类型为signum的信号，就会调用这个程序，通过把处理程序的地址传递到signal函数从而改变默认行为，这称为设置信号处理程序。调用信号处理程序被称为捕获信号，执行这个程序称为处理信号。

阻塞和解除阻塞信号

隐式阻塞机制。内核默认阻塞任何当前处理程序正在处理信号类型的待处理信号。

信号不能拿来记录进程发生的事件次数

不可用信号来对其他进程中发生的事件计数，因为当进程在处理第一个信号，如果其他进程发送信号就添加到了待处理信号集合里，但是之后的信号是直接会被丢弃的，所以其他进程中的事件运行速度很快的话，我们计数用的进程能接收到的信号是有限的，不能够正确地计数。

链接

将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载到内存并执行。现代系统中，链接时又叫做链接器的程序自动执行的。

静态链接

链接器的主要任务：

符号解析:目标文件定位和引用符号，每个符号对应于一个函数、一个全局变量或一个静态变量。符号解析的目的是将每个符号引用正好和一个符号定义关联起来。

重定位:编译器和汇编器生成从地址0开始的代码和数据节，连接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改所有对这些符号的引用，使他们指向这个内存位置。

目标文件

可重定位目标文件。包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。

可执行目标文件。包含二进制代码和数据，其形式可以被直接复制到内存并执行。

共享目标文件。一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态地加载进内存并链接。

编译器和汇编器生成可重定位目标文件。连接器生成可执行目标文件。从技术上来说，一个目标模块就是一个字节序列，而一个目标文件就是个以文件形式存放在磁盘中的目标模块。

目标文件是按照特定的目标文件来组织的，各个系统的目标文件格式都不相同。

可重定位目标文件

可重定义目标文件

ELF头以一个16字节的序列开始，这个序列描述了声称该文件的系统的字的大小和字节顺序。ELF头剩下的部分包含帮助连接器语法分析和解释目标文件的信息。其中包括了ELF头的大小、目标文件的类型、机器类型、节头部表的文件偏移，以及节头部表中条目的大小和数量。

夹在ELF头和节头部表之间的都是节。一个典型的ELF可重定位目标文件包含下面几个节。

.text：以编译程序的机器代码。

.rodata:只读数据，比如printf语句中的格式串和开关语句的跳转表。

.data:已初始化的全局和静态C变量。局部C变量在运行时被保存在栈中，不出心在.data中，也不出现在.bss节中。

.bss:未初始化的全局和静态C变量，以及所有初始化为0的全局或者静态变量。

symtab:一个符号表，存放在程序中定义和引用的函数和全局变量的信息。

COMMON和.bss条目的区别

符号和符号表

每个可重定义为目标模块都有一个符号表，在链接器的上下文中，有三种不同的符号

由模块m定义并能被其他模块引用的全局符号，对应的是非静态的C函数和全局变量。

由其他模块地定义并被模块m引用的全局符号，称为外部符号，对应的是其他模块中定义的非静态C函数和全局变量

只被模块m定义和引用的局部符号。对应的是带static属性的C函数和全局变量。这些符号在模块m中任何位置都可见，但是不能被其他模块引用。

符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。当遇到全局符号时，如果遇到的不是在当前模块中定义的符号，会假设是在某个模块中定义的，生成一个链接器符号表条目，如果连接器在任何输入模块中都找不到这个符号的定义，就输出一条错误信息并终止。

连接器如何解析多重定义的全局符号

链接器的输入是一组可重定位目标模块。每个模块定义一组符号，如果多个模块定义同名的全局符号，Linux系统采用的方法：

编译时，编译器向汇编器输出每个全局符号，或者是强或者是弱，函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。

规则一：不允许有多个同名的强符号

规则二：如果有一个强符号和多个弱符号同名，那么选择强符号

规则三：如果有多个弱符号同名，从弱符号中任意选择一个。

信息的表示和处理

进制转换

掌握十进制、二进制、十六进制的转换

布尔运算

包括位运算、逻辑运算、移位运算

位运算：&（与）、|（或）、~（取反）、^(异或)

逻辑运算：&&（逻辑与）、||（逻辑或）、!（逻辑取反）

移位运算：<<（左移）、>> （算术右移和逻辑右移）

算术右移：负数（也就是二进制中符号位为1的数）右移时左边补1，正数（也就是二进制中符号位为0的数）右移时补0

逻辑右移：右移时统一补0

整数表示

无符号数的编码

如果有一个整型数据类型有w位，将其写成位向量x，把x看成一个二进制数，就得到了x的无符号表示。运算方式就是将其看成一个二进制数再转成十进制数得到数值。

补码编码

对于一个位向量，最高有效位为符号位，是无符号表示中权重的负数。符号位设置为1时，表示值为负，设置为0时，值为非负。

有符号数和无符号数之间的转换

补码转为无符号数：当一个有符号数映射为相应的无符号数时，负数被转换为大的正数，非负数保持不变

无符号数转为补码：上述的逆运算