参考博客：https://zhuanlan.zhihu.com/p/653809910

前言

  • 在学习CSAPP之前先寻找一下网上的相关资源。

  • 首先是AIChatGPT

  • 在开始看教学视频之前，先看一下b站fengmuzi2003–CSAPP重点导读

  • CSAPP教学视频，这边看的是CSAPP作者的上课录制视频

  • CSAPP电子书或者纸质书，看完CSAPP教学视频后就直接将书籍阅读一遍，然后再写博客进行归纳，进一步加深理解

  • 国外CSAPP的课程网站http://www.cs.cmu.edu/~213/，这里有实验和作业可以进行课后研究和探讨

  • 国外CSAPP官方网站http://csapp.cs.cmu.edu/，这里有课程、课间等提供使用

  • github上关于CSAPP的一些资料Repository search results (github.com)

  • https://www.coursehero.com/可以找到关于CSAPP的一些相关资料

  • 讨论问题的两个网站https://www.reddit.com/r/csapp/和https://stackoverflow.com/search?q=csapp，不过这两个需要谷歌或者其他账号才能进入

操作系统漫游

  • 这一章没啥重点，就随便写了写笔记
操作系统概述

计算机系统概述

计算机系统的组成

  • 计算机系统是由硬件和软件所组成的，而操作系统是一个软件，是直接与硬件交互的，在操作系统之上运行的软件，才是我们一般说的软件

硬件

  • 中央处理器（CPU）：
    • 早期CPU包括：执行程序指令的核心组件，包括算术逻辑单元（ALU）、控制单元（CU）和寄存器
    • 后来CPU里面又加入了：缓存（Cache）、中断处理单元

  • 内存（Memory）：存储数据和程序的区域，包括RAM（随机存取内存）和缓存
  • 存储设备（storage）：持久性存储数据的设备，如硬盘驱动器（HDD）、固态硬盘（SSD）。注：很多初学者都会将存储设备和内存混为一谈
  • 输入输出设备（I/O Devices）：用于与计算机交互的设备，如键盘、鼠标、显示器、打印机，甚至还有网络等。

image-20240719233340264

软件

  • 软件包括以下几种类型：操作系统、应用程序、编译器、库等。

计算机系统的工作原理

程序的基本概念

  • 程序：存储在磁盘上的静态代码文件
  • 进程：程序在运行时的动态实例，包括程序代码、数据、堆栈和寄存器等。

内存布局

  • 代码段：存放程序代码的区域。
  • 数据段：存放静态数据（如全局变量）的区域。
  • 堆：动态分配的内存区域，由程序运行时管理。
  • 栈：存储局部变量、函数调用信息的区域。

image-20240721184617663

程序计数器

  • 程序计数器（Program Counter,PC）：位于CPU的内部
    • 作用：指示下一条要执行的指令地址。
    • 变化：每次指令执行后，PC会更新到下一条指令的地址。

image-20240721184942627

机器级程序

机器语言和汇编语言

  • 机器语言：计算机能够直接执行的二进制代码。
  • 汇编语言：与机器语言对应的低级编程语言，用助记符代替二进制代码。

指令集架构(ISA)

  • 作用：定义了CPU支持的指令集及语法。（具体了解还需要细读计算机组成原理）
  • 示例：常见的ISA包括x86、ARM等

C语言的机器表示

C语言与机器语言的关系

  • 编译过程：C语言源代码通过编译器转换成机器码，在不同系统上根据不同的编译器进行编译。编译的过程如下图

image-20240721185706857

  • 变量存储：C语言中的变量在内存中如何表示，包括整型、浮点型。

函数调用与返回

  • 调用约定：函数调用时，参数如何传递，返回值如何处理。常见的有Linux的32位传参 64位传参 和Windows下的参数调用

  • 调用栈：函数调用时栈帧的创建和销毁。

  • 详细过程了解：PWN基础 | iyheart的博客2.5函数调用规则

计算机系统中的抽象

抽象层次

  • 硬件抽象：计算机硬件的抽象层次，通过操作系统对硬件进行管理和控制。如：设备驱动程序、虚拟内存、文件系统等
  • 软件抽象：应用程序如何通过操作系统提供的接口进行操作。如：系统调用、进程和线程、库和框架

常见抽象

  • 文件系统：提供对文件的抽象，允许程序以文件的形式存取数据。文件系统是一个计算机中程序数据交互的方式，文件系统是Linux系统的一个核心。
  • 网络协议：网络通信的抽象，允许不同计算机之间进行数据交换。网络协议是计算机与计算机之间数据之间的交互。

计算机系统中的数据表示

数据表示的基本概念

  • 整数表示：
    • 补码表示：用于表示正数和负数，计算机通过补码进行算术运算
    • 溢出：整数运算超出表示范围时发生
  • 浮点数表示：
    • IEEE 754标准：定义浮点数的格式和运算
    • 组成部分：符号位、指数位和尾数（有效数字）
  • 字符编码：
    • ASCII：7位字符编码，支持英文和基本符号
    • Unicode：支持多语言字符集，包括非英文字符。

线程和并发

线程

  • 定义：线程是进程中的一个执行单元，每个线程都有自己的执行栈和程序计数器，但线程间共享进程的资源（如内存）。
  • 多线程编程：
    • 创建线程：使用系统调用或语言提供的线程库创建新线程
    • 同步机制：用于线程间的协调和数据共享，防止数据竞争和同步问题，包括互斥锁、条件变量
    • 线程的生命周期：包括创建、就绪、运行、阻塞、终止转态。

并发

  • 定义：并发是指系统能够同时处理多个任务或线程。通过上下文切换实现伪并行。
  • 上下文切换：操作系统在多个线程间切换执行，为用户程序提供并行处理的感觉。
  • 线程安全：编写正确的并发程序需要确保对共享数据的访问是安全的，防止竞态条件和死锁。

文件

  • 定义：文件系统是操作系统用于管理文件和目录的机制，提供对文件的抽象
  • 文件操作：打开文件：通过系统调用如open打开文件，并获得文件描述符

Amdahl定律

  • 定义：Amdahl定律用于预测通过并行计算提升系统性能的潜力
  • 公式：

image-20240721195226983

image-20240721195703716

  • α：程序中可并行化的部分所占比例。
  • k：并行部分的加速倍数（即处理器数量）。
  • 含义：
    • 非并行部分限制：即使并行化部分加速无限大，整体加速仍受限于串行部分
    • 并行化收益递减：随着处理器数量增加，收益逐渐减少
  • 应用：
    • 设计系统：帮助确定投资并行化是否有效。
    • 性能评估：分析并行化对特定程序的影响。

信息的表示和处理

位运算

整数

  • C语言支持多种整型数据类型——表示有限范围的整数。每种类型都能用关键字来指定大小，这些关键字包括char、short、long，同时还可以指示被表示的数字是非负数或者可能是负数
  • 有符号整型的取值具有不对称性：负数的范围比正数的范围大1
  • 以下为32位机器和64位机器C语言整型数据类型的典型取值范围：
image-20240906172844746 image-20240906172919347

无符号数编码

  • 对于一串二进制的0、1串，都有一个与之对应的无符号10进制数。
  • 对于二进制转换成无符号数的10进制具有如下过程：（都只使用4位二进制进行讲解）
1
2
对于无符号整数最小值0，可以使用二进制：0000表示
对于无符号整数最大值15，可以使用二进制：1111表示

对于二进制转换成10进制的无符号整数对于二进制转换成10进制的无符号整数

二进制的每一位都可以与等比数列an=2n−1一一对应二进制的每一位都可以与等比数列a_n = 2^{n-1}一一对应

（然后在每一位前面加个系数，将加上系数的每一位相加即可得到无符号整数）（然后在每一位前面加个系数，将加上系数的每一位相加即可得到无符号整数）

  • 例如（默认左边高位右边低位）：
1
2
3
4
5
6
7
8
1111：      1          1           1          1 
		1×2的3次方  1×2的2次方   1×2的1次方    1×2的0次方
则转换成无符号10进制数：1*8+1*4+1*2+1*1=15

再例如：
0101：        0                1                 0             1
		  0×2的3次方         1×2的2次方         0×2的1次方      1×2的0次方
转换成无符号10进制数：0*8+1*4+0*2+1*1=5

image-20240906174728070

有符号数编码

  • 二进制转换成有符号数使用的是补码。之前都是简单的说最高位做为符号位，这种表述感觉会不好理解。

最高位应该理解成−2n−1最高位应该理解成-2^{n-1}

  • 这样在计算的时候就可以直接计算了，就不要什么取反+1绕来绕去的

    • 所以有符号整数最小值的二进制表示为1000
    • 最大值表示为0111

  • 剩下的也就和无符号数的编码大差不差了

  • 下面是几个二进制转换成有符号整数的例子：

image-20240906191151732

  • 对于补码编码以下几点需要注意一下：
    • 补码的范围是不对称的：|Tmin| = |Tmax| + 1，即Tmin没有与之对应的正数
    • 最大的无符号数值刚好比补码的最大值的两倍多1，Umax = 2Tmax+1
    • -1与Umax有同样的表示，是全1串
    • 数值0在两种表示方式中都是全0串
  • C语言标准并没有要求用补码表示有符号整数，但是所有机器都这么做。
  • 有符号数还有另外两种编码，但是这两种编码都出现了正负0，所以使用补码才避免了出现两个0

image-20240907122902442

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

  • 有符号数和无符号数的转换需要从内存中看，即从位的角度进行分析和解释

    • 当我们定义一个有符号整数（32位）int tu = -1这时我们的内存中tu的位级表示为0XFFFF FFFF
    • 但是当将其转换为无符号数unsigned u = tu，此时u的位级表示仍为0XFFFF FFFF
    • 而tu的值为-1，u的值为4294967295
    • 所以相同位数的有符号数和无符号数的转换，内存是不会变化的，只是编码方式该变了

  • 这里给出有符号数与无符号数之间转换的公式

image-20240909115117904

image-20240909115145542

整数的位扩展

  • 有时需要将整数扩展（增大存储整数的位数，即增大取值范围），但是要保证原来的整数值不变，这就要进行位扩展。
  • 位扩展有：零扩展、符号扩展

零扩展

  • 零扩展比较简单，即扩展位都是0，原来的位保持不变，这里给出书上公式
    • 即将扩展的高位全部置为0，然后原来的低位保持不变
    • 例如：将原来16位无符号数2，位扩展到32位
      • 16位的无符号数这样表示0x0002，扩展到32位后这样表示0x0000 0002

image-20240909115616062

符号扩展

  • 符号扩展，先了解其过程：在汇编里面的算术位移运算就与符号扩展很类似
    • 要扩展的数符号位是0，则扩展的位使用0，原来的位不变
    • 要扩展的数符号位是1，则扩展的位全部置1，原来的位保持不变
    • 例1：扩展4位有符号数-8为8位
      • 4位有符号数-8补码表示为1000，由于符号位是1，扩展的高位全部置1，即1111 1000
    • 例2：扩展4位有符号数2为8位
      • 4位有符号数2补码表示为0010，由于符号位是0，扩展的高位全部置0，即0000 0010
  • 这里给出公式

image-20240909120101101

  • 下面给出数学证明（需要理解一下）

整数的位截断

  • 整数的位截断与整数的位扩展，都要以位的角度来看。

无符号整数的截断

  • 当一个m位的无符号数x被截断为n位（m>n），得到的结果为x mod 2^n。使用模运算即可得到相关结果。
  • 例如：先从位的角度进行分析，再从模的角度进行分析
1
2
3
4
5
6
7
8
9
10
// 当一个8位的无符号整数254，它的位级表示如下
1111 1110
// 当其被截断，高4位被除去，结果的位级表示如下
1110 
// 无符号整数的截断比较容易(无论是从数学角度还是位的角度来看)
// 下面从模的角度看
x = 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1  
// 当x mod 2^4时，高位的能被2^4整除，但是低位的2^4是除不尽的
// 所以就会有如下等式
(2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1) mod 2^4  = (2^3 + 2^2 + 2^1) mod 2^4
  • 书上给了具体的公式

image-20240912092125729

有符号数的截断

  • 有符号数的截断，从位级角度上看是比较容易的，但是在从数学角度上看就比较抽象(主要是很绕)。
  • 这里先通过具体的例子对无符号数进行简单的分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int x = 53191;		  /*int类型32位*/
short sx = (short) x; /*-12345*/
int y = sx;			  /*-12345*/

// 位级角度先进行分析，53191的32位补码表示为
0000 0000 0000 0000 1100 1111 1100 0111
// 然后进行截断，由32位变成16位
1100 1111 1100 0111
// 由于是补码表示，最高位是1，所以转化为十进制就为
-12345

// 如果从数学角度上看
1. 先将这个数转换成无符号整数
2. 对这个无符号整数进行取模运算，得到结果
3. 将模运算的结果转换成有符号整数
// 分析好这个过程后再来看下面的抽象的数学公式，就会变得比较容易了
// 其实从位级角度上看也经历了这几步骤，只是有些步骤直接被我们忽略了
  • 这里给出书上的有符号整数的截断

image-20240912095001249

整数运算

  • 整数运算大致结构如下

整数运算

无符号数加法

  • 无符号加法较为简单与溢出都是比较简单的运算

  • 这里直接给出公式

image-20240917170742566

  • 这里再附上解释，稍微理解一下即可

image-20240917170841416

  • 所以在检查是否有溢出，我们可以从俩个角度判断：
    • 第一个角度是从flag寄存器中判断，该寄存器被称为标志寄存器，其中有一位就是专门用来判断整数是否有溢出
    • 第二个角度比较结果与俩个加数中的其中一个，如果结果大就没溢出，反之就溢出。

无符号数求反