普林斯顿 COS217 C 语言系统编程笔记（二）
动态内存
迄今为止，我们程序的变量大小都是在编译时确定的。动态内存管理允许我们在程序运行时按需分配和释放内存，这解决了处理未知数量数据的问题。
程序的内存布局通常包含几个部分：
-
文本段：存放程序代码。
-
栈：存放函数参数和局部变量。
-
堆：用于动态内存分配的区域。
我们通过栈上的指针来访问在堆上动态分配的内存。
分配内存：malloc 和 calloc
malloc 函数分配指定字节数的未初始化内存块。
int *arr = malloc(3 * sizeof(int)); // 分配3个int的空间
if (arr == NULL) {
// 处理分配失败
}
calloc 函数分配指定数量和大小的内存块，并将所有位初始化为零。
int *arr = calloc(3, sizeof(int)); // 分配并初始化为0
关键点：必须检查 malloc 或 calloc 的返回值是否为 NULL，这表示内存分配失败。直接使用返回的 NULL 指针会导致程序崩溃（段错误）。
释放内存：free
使用 free 函数释放之前动态分配的内存。忘记释放内存会导致“内存泄漏”。
free(arr);
注意事项：
-
只能对由
malloc,calloc或realloc返回的指针调用free。 -
free之后，指针变成了“悬空指针”。最佳实践是立即将其设为NULL，以防止后续误用。 -
对同一个指针调用两次
free（双释放）可能导致堆损坏，是严重的错误。
调整内存：realloc
realloc 函数用于调整之前分配的内存块大小（可以增大或缩小）。
int *new_arr = realloc(arr, 5 * sizeof(int));
if (new_arr == NULL) {
// 调整失败，原指针arr仍然有效
} else {
arr = new_arr; // 调整成功，更新指针
}
关键点：
-
realloc可能返回一个新的指针地址（如果无法在原地扩展）。 -
必须将
realloc的返回值保存到一个临时变量中，检查是否为NULL后再决定是否更新原指针。直接覆盖原指针，若realloc失败，会导致原内存块丢失（内存泄漏）。
常见错误示例
以下是两个常见的动态内存错误：
-
分配字符串空间时忘记为终止符
\0预留位置：char *new = malloc(strlen(old)); // 错误！少了一个字节 strcpy(new, old);正确做法是
malloc(strlen(old) + 1)。 -
将
malloc调用直接嵌套为函数参数，未检查是否失败：strcpy(malloc(strlen(old) + 1), old); // 危险！如果
malloc失败返回NULL，strcpy会尝试向空地址写入数据，导致崩溃。
本节课中我们一起学习了C语言的结构体、命令行参数和动态内存管理。结构体帮助我们组织异构数据；命令行参数提供了程序交互的入口；而动态内存管理（malloc/calloc, free, realloc）则赋予了程序在运行时灵活管理内存的能力，但同时也要求程序员谨慎处理分配失败、内存释放和指针有效性等问题。理解并正确运用这些概念是进行C语言系统编程的关键。
012：测试 🧪
在本节课中，我们将要学习软件工程中至关重要的一环：测试。我们将探讨测试的重要性、不同角色的职责、以及如何构建结构化的测试策略，包括外部测试、内部测试、单元测试和测试覆盖率等核心概念。
概述
在编写软件时，除了掌握特定语言的细节，还需要掌握大规模编程所需的技能和技巧。本周的第二次辅导课和下周的第一次讲座将讨论调试。但除非首先知道程序存在问题，否则你甚至不知道需要调试什么。而要做到这一点，就需要了解测试。
对于足够复杂的程序，很难一开始就知道自己做的事情是否正确。以我们的decomment程序和作业1为例，就有很多边界情况。对于一个像shell这样的程序，边界情况会更多；对于一个操作系统，其复杂性几乎是难以想象的。此外，即使你知道一个算法是正确的，这也与保证该算法的特定实现是正确的完全不同。
Dijkstra在其关于Van Emde Boas树的笔记中的名言在这里很贴切。更进一步，在一般情况下，你甚至无法编写一个程序检查器来确保任何给定程序会终止，更不用说确保它做你想做的事情了。这就是你在126课程中学到的图灵停机问题。
尽管停机问题是不可判定的，但我们确实知道如何进行一些程序验证。实际上，在形式逻辑和编程语言领域有一个丰富的研究领域，致力于为程序规范构建和应用证明辅助工具。不过坦白说，大多数软件工程师并没有在他们的代码中使用证明辅助工具，这当然也超出了这门系统编程入门课程的范围。
尽管如此，如果你对此感兴趣，我鼓励你去选修Co 326，在那里你将学习函数式语言。函数式语言的一个关键原则是，不可变状态的缺失使得推理程序变得更加容易。在326之后，还有两门研究生课程，本科生也可以选修，它们涉及编程语言理论和软件的自动推理。
另一方面，通过测试，我们并没有一个证明。我们只有一些至少是部分正确性的证据，我们甚至可能对自己的正确性有相当合理的信心。但对于一个足够大的程序，很难说服自己对于输入的每一种可能排列都做了正确的事情。
不过，不要认为测试完全不提供任何保证。如果你有一个失败的测试，那么有一个绝对确定的事实：存在一个错误。但并不能确定错误具体在哪里。错误可能在你的程序中，也可能在测试本身中。
因此，我们希望在软件设计过程中关注测试，并希望采取结构化的方法来构建测试基础设施和探索规范空间以设计测试用例。
测试的重要性与职责
这就是为什么测试很重要，但这是谁的工作呢？虽然软件工程师、软件设计师会进行大量的自我测试，这有好有坏。好处是他们最直接地接触代码，并且在实现时了解规范的所有细节，知道哪些是棘手的部分，哪些地方做了不寻常的事情。但坏处是没有人会故意编写错误。这意味着如果存在错误，那么一定有某些地方被忽视了。可能对规范有隐藏的假设，可能对输入有隐藏的假设，这些假设泄露到了代码中，然后如果编写代码的同一个人也在编写测试，那么这些假设也可能泄露到测试中。
另一方面，质量保证人员（QA）能对实现有一个全新的视角，因此他们对开发过程中的假设没有偏见。他们不受实现偏好的影响，无论是实现起来最容易的部分，还是最新的部分，或是个人偏好。但相应地，他们对代码也没有完整的了解。此外，因为开发人员和QA往往在同一个团队、同一个组织工作，他们也往往受制于相同的规范及其缺陷。
这就把我们带到了客户面前。客户不受相同规范的约束。客户倾向于以非常有创意的方式使用程序。但让客户成为测试基础设施的支柱也很困难，因为仅通过错误报告很难实现系统或系统的覆盖。此外，如果太多错误流入实际使用环境，肯定会疏远客户。
尽管如此，尤其是在当今的网络编程中，将现场测试作为测试策略的核心组成部分变得越来越普遍。
对于你在我们课程中的程序，客户就是评分脚本，所以你绝对不想依赖现场测试。相反，让我们看看作为开发者，你如何构建你的测试。
外部测试
我们将从外部测试开始，这是在程序本身之外进行的测试，但稍后我们将讨论程序内部的内部测试。
手动测试与自动化
我知道这是大多数人在他们短暂的编程生涯中迄今为止最常用的测试方式。但坦白说，我很惊讶你的手还没有掉下来。我在普林斯顿大学基于大约1000小时的证据得出的假设是，你的手之所以没有掉下来，主要是因为你懒得回去检查，在修复一个错误或添加一个新功能后，所有以前能工作的东西是否仍然能工作。
所以，让我们看看如何让这件事变得更容易，而不是在合理的测试纪律和不得腕管综合征之间做出选择。
第一个改进是将所有测试放入文件中，包括输入和正确的输出。现在我们可以一遍又一遍地运行它们，而无需重新输入。通过很好地使用历史记录或命令行快捷方式，你可以相当高效地完成这项工作。
但是，如果有很多测试，多到你甚至不想一次运行一个呢？这时Shell脚本就派上用场了。坦白说，这应该是课程的一部分，但某种程度上它不是。这是333课程中一些讲师教授的内容，作为成熟计算机科学家应该知道的东西，但你从未在任何地方学过，所以我们不妨在这里提一下。简而言之，Shell脚本只是一系列Shell命令，它们会像在命令行执行一样运行。
因此，我们可以将一堆原本要在bash提示符下输入的东西打包成一个命令。我们可以比这里展示的更复杂、更系统化。正如你在学期初的Linux讲座中简要看到的，Shell脚本可以包含变量、循环和各种好东西。也许你不知道，但你实际上已经用过一些了。你在作业1中使用的test_decomment程序就是一个Shell脚本。第一行#!/bin/bash表示使用bash shell来解释这个脚本，所以每一行都像在bash提示符下输入一样执行。
这个程序的核心在于它遍历当前目录中匹配某个模式的所有文件，即以.txt结尾的任何文件。它对每个文件做什么呢？它运行命令test_diff。而test_diff，你猜对了，是另一个bash脚本。
所以很容易让人想：我永远编写超棒的测试脚本，我就永远不会再有错误了。但首先，编写自动化软件并非易事。其次，你怎么知道脚本里没有错误呢？当然，一个选择是说递归，然后你为你的测试脚本写一个测试脚本。不过说实话，这实际上是我们为像这样的课程和作业扩展到数百人规模而做的准备工作的一部分。我们会说，好吧，我们现在有一个脚本，我们如何测试它呢？我们会用完全相同的操作集来测试它。但总的来说，你知道测试只能做到这一步。
回归测试
一个常见的工作流程是编写一个自动遍历一系列测试的脚本。这就是回归测试的总体思路。这有助于实现一个目标：当我编写新代码时，以前能工作的东西仍然能工作。当我发现一个错误时，我需要添加一个测试，以便将来可以测试我修复的错误是否仍然被修复。当我修复那个错误时，如果我有新测试和旧测试，那么现在它能工作了，以前能工作的东西也能工作，我可以从现在开始一直测试它们，直到未来的任何开发。
否则，你最终会陷入这个梗图所描述的情况。或者如果你觉得我太老了不应该在幻灯片上放梗图，我就默认回到我通常做的XKCD漫画。所以这里，回归测试对于确保你不会因为修复而无意中使情况变得更糟很重要。在大型代码库中，回归测试可能会在后台持续运行，以确保代码的实时版本和仓库版本仍然通过测试。在某些情况下，回归测试甚至被内置到代码提交过程中，这样推送到仓库的操作实际上不会发生，除非自动回归测试通过。
但回归测试只能测试我们已经知道要寻找的东西。我们如何添加新的测试呢？一种方法是有机地发现错误：有人注意到某些地方不对，提交错误报告，QA或开发人员添加一个能重现该错误的新测试用例。这就是错误驱动开发或错误驱动测试，它相当被动。
不过，也有一个主动的版本，叫做故障注入。它在原则上很有意义，对于测试测试本身很有用。但它对开发过程有帮助吗？它的实用性不那么明显。很难预测未来某个程序员可能会犯什么错误，因此很难基于故障注入为这些错误预先编写测试。
尽管如此，应用于本课程的作业一和作业二，多年来我们某种程度上采取了这种方法。参与本课程工作的各位教职员工以非常被动的模式设计了数据文件：评分员手动检查代码，他们发现一个现有测试文件没有捕获的错误，我们改进测试文件，在未来的年份里，我们将能够为所有未来的学生测试之前遗漏的相同情况。从这个意义上说，把这门课作为一门已经存在一段时间的成熟课程对你来说有些不利，因为评分可能更难一些。但另一方面，希望我们在许多其他方面已经做得更好了。
不过，我鼓励你期待作业4，它对学生有一个主动模式：我们将给你一些程序的有错误版本，然后最终测试你捕获错误的设计。
测试驱动开发
另一种有趣的形式是测试驱动开发。它基本上是自底向上的：你写一个会失败的测试，然后写代码让它不再失败，然后重构你的代码。所以在这里，“我要写代码”和“我要写测试”这两个步骤是交织在一起的。这是一个有趣的想法，原则上我喜欢它，即测试应该是一个早期集成的一等公民。但也许说“在实现新功能之前，必须先写一个会失败的测试，直到它工作为止”有点太极端了。
内部测试
到目前为止，所有讨论都集中在端到端的整个程序测试上。对于像作业1这样的东西，这很容易。但对于许多程序，没有明确的解决方案。也许总体答案是未知的，或者这是一个非常大的问题，我们无法在端到端的基础上进行测试，因为耗时太长，或者也许规范本身就不清楚。正如本课程中一贯的答案：模块化。我们已经在217课程中频繁使用了模块化这个关键词，而且频率不会随着时间的推移而降低，我保证。这是我们的核心理念之一。因此，如果核心理念之一是我们应该将大型系统分解为更小、更简单、更容易理解的原子组件，那么将同样的理念应用于测试它们以及构建它们，也就顺理成章了。
回到谁来做测试的问题，到目前为止我们讨论的所有测试都可以由幻灯片上的三方中的任何一方完成。但现在，随着将程序分解为更易于理解的部分的目标，我们将深入程序内部。因此，程序员是了解模块、边界、结构的人，从而可以设计测试，以最大限度地利用这种对结构的了解。
不过，在继续之前，我应该指出，模块之间的接口和边界可能是最常见的误解所在，因此也是最常见的错误点，所以我们确实仍然需要一些端到端的测试。
断言
好了，让我们来谈谈内部测试。我们将从C语言中的断言开始。C语言有一个名为assert的库，允许程序员将测试写入他们的代码中。
该库定义了一个宏assert，它会像函数调用一样被处理。这个宏，如果参数表达式求值为真，它什么都不做。但如果参数表达式求值为假，它会终止你的程序。你可能会想，等等，这是一件好事吗？为什么我希望我的程序死掉？这是一个相当强硬的测试结果，不是吗？但至少一般来说，带着关于哪个断言在哪里失败的信息明确地终止，比在未知情况下在其他点任意崩溃要好。此外，带着关于哪个断言在哪里失败的信息明确地终止，比带着错误答案运行到完成要好得多。
因此，通常程序员选择在问题不是我们这个特定模块的程序员的错误，并且我们对此无能为力时，通过失败的断言中止程序。或者当问题是我们自己的错误，并且是我们应该尽快捕获和修复的时候。
更一般地说，我们将讨论使用assert来处理编程错误，这些错误要么来自作者，要么来自调用者，而不是来自输入的用户错误。但让我们看一些例子。
我们可以使用断言来验证我们的参数，你已经在作业2中看到了这一点。我们不允许坏数据进入。有一个原则叫做“垃圾进，垃圾出”，而这有点相反，这是“垃圾进，程序死”。这在编写模块化代码时尤其重要。你编写了函数，但你可能不是编写调用它的函数的人。事实上，对于一个足够大的程序，你几乎肯定不是。所以一个合理的问题可能是：为什么要让程序死掉？为什么不返回一个错误状态？但这里的问题不是我们的错。我写了一个完美的gcd函数，但有人调用它时没有遵守我在头文件注释中规定的契约。
所以在gcd中我们无法修复这个问题。如果调用者传递了坏数据，我们凭什么认为调用者会查看我们信息丰富的错误返回并对此做出合理的处理呢？此外，错误返回可能很难维护，回想一下getchar返回int所带来的复杂性和混淆。如果几乎每个函数都开始返回某个有效值或某个错误状态，这种情况就会变得普遍。
因此，在缺乏像C语言所没有的异常机制的情况下，一个选择是：直接说不，你没有遵守我的契约，我不会做任何事情，事实上我会终止程序。
下一步是，如果我们说不让坏输入进门，那么我们也不让坏输出出门。你知道你的函数应该做什么。它做到了吗？也许我们不知道确切的正确答案应该是什么，但我们可以找出一些后置条件。在这个例子中，gcd显然必须小于或等于每个输入且大于零。再次，为什么用断言？为什么不返回一个错误状态？在这种情况下，我们得到了好的输入，这就是为什么我们没有死掉。如果我们返回了错误的东西，这意味着错误是我们的错，我们希望尽快注意到并修复它，最好是在发布之前。如果我们这里有断言，那么只要我们进行任何测试，无论是我们作为开发者，还是开启断言的QA运行它，都会注意到我们的程序死了，我们会说，嘿，去修复这个。这给了我们一个机会，避免因为发布错误代码而尴尬。
第三件事，我们可以测试程序的一些假设或不变量。在C语言的情况下，也许我们没有像Java语言那样免费获得数组访问的边界检查，如果违反，Java会用数组索引越界异常终止你的程序。在C语言中，没有这样的保护。但你可以合理地编写自己的检查。对于下界来说很容易。在这种情况下，如果数组大小已知，检查上界也可以，但作为参数传入时更难，因为正如我们所见，除非我们通过另一个参数或类似的东西得到一些信号，否则不可能确切知道传入的数组参数有多长。
所以再次，我们问在这种情况下为什么用断言？嗯，这里是我们自己的错。如果我们越界了，那是我们的错，我们必须注意到并修复它。
表示不变性
当我们检查值的有效性时，我们还应该确保我们调用的任何外部函数行为正确，并给我们留下我们知道如何处理的后置条件。例如，当我们从标准输入读取时，我们最好检查我们是否真的能够读取我们想要的东西。
所以再次，这里我们要检查这个，但现在我们要用断言以外的东西来检查，因为这不是一个编程错误。如果我们只得到有效的输入，这段代码会正常工作。因此，如果scanf没有返回2，这意味着我们没有得到我们期望的输入。这是一个输入错误，一个用户错误。在这种情况下，我们可以尽力获取新的输入，打印错误信息，尝试各种其他方式让用户配合我们，因为这个错误可能是可以修复的。不像当它是一个内置的编程错误，无论是调用者还是我们的程序本身坏了，在运行时我们对此无能为力。
好了，沿着同样的思路，但更深入一点，我们有表示不变性。这是我程序的内部状态。问题是，它是否处于我所知道的应有的有效状态？这对于数据结构特别有用，我们下周会讲到数据结构，但你已经从126课程中了解了它们的要点。所以这些是抽象，数据结构是抽象，因此它们具有与构成它们的底层原始类型不同的有效性。
例如，如果一个对象仅使用一个int来表示217作业成绩，那么不变性可能是它是非负的。尽管C语言中的int当然可以是负数。是的，我知道，在这种情况下，我们应该直接使用unsigned int。另一个例子，如果它代表一个学生，表示不变性可能是学生的姓名非空且不是空字符串。
那么我们如何使用表示不变性呢？一个创建数据结构的函数可能会在继续之前确保数据结构是正常的。因此，如果传入一个数据结构，它会说，你给我的东西有效吗？否则我对此无能为力。一个创建或修改数据结构的函数可能会在返回之前确保数据结构仍然是正常的。所以如果我从头开始创建东西，我们最好从有效状态开始。如果我接收一个东西，改变它，然后继续，那么再次我应该检查，在我完成了函数所做的任何修改之后，它是否仍然有效。
需要注意的是，如果我们检查数据结构的整个状态，这可能会很昂贵，你可以想象数据结构是一棵树或一个很长的列表。因此，这里一个常见的技术是将检查代码包装在断言中，我们稍后会看到为什么这是一个灵活的解决方案。
单元测试
好了，一旦我们有了一些内部测试，我们需要一个结构化的方法来继续。单元测试是与其他部分隔离地测试各个部分。考虑一个模块，例如作业2。你从一个接口开始，这是实现与其客户端之间的契约规范。你构建实现，试图匹配接口的契约。然后你或其他人编写一个客户端程序，再次试图匹配接口的契约。
但如果我们运行端到端测试，发现程序得到了错误的答案。我们知道存在一个错误，但我们没有任何关于其位置或如何修复它的提示。例如，如果replace不工作，嗯，也许错误就在replace里。但也可能是在str_copy里。如果我们在这些底层函数中存在根本问题，我们最好早点发现，而不是现在当它影响到客户端代码时才被发现。
然而，测试每个部分很棘手，因为我们需要能够单独调用它们。但这些部分在构造上是相互关联的。增量测试通常涉及创建脚手架和桩。
脚手架是一个临时的或不完整的函数甚至程序，它调用被测试的函数。像Python这样的语言允许任何函数被交互式调用，因此它们消除了对脚手架的许多需求。但在C语言中，要测试一个函数，例如这里的函数2，你可能需要编写一个调用它的脚手架，也就是一个包含main函数的东西。
桩位于我们关心的函数的另一侧。它是一个临时的、虚拟的或不完整的函数，我们实际测试的函数会调用它。为了测试函数2，我们可能需要编写一个它所调用的函数的最小版本。有几种方法可以做到这一点。我们可以硬编码它应该返回的值。我们可以做一个“绿野仙踪”式的解决方案，即幕后有人，不从函数计算返回值，而是从标准输入或文件读取，类似这样的东西。这有点像硬编码，但它是数据，而不是在程序本身中。然后还有另一个选择，可能是我们可以生成正确答案，但速度很慢，假设我们还没有为那个聪明的快速算法编写代码，而是用暴力方法。
我们在这些框里用斜体标出了“临时”，因为它往往不是临时的。Ellen Cooper在90年代中期写了一篇非常有影响力的论文《原型设计的危险》，其中说到，当你编写了非常好的脚手架和非常好的桩时，你会说，哇，这真的很好。我不想扔掉我努力工作的成果，它结果真的很好。所以你倾向于保留一些你的代码，通过扩展它成为更完整的版本，即使实际上你应该从头开始构建更完整的版本，而不是围绕那个桩添加一些原本并非为此设计的额外部分。所以这里有点棘手。我们想编写非常好的桩，我们想编写非常好的脚手架。但你不应该屈服于诱惑，让那些桩和脚手架成为应该从头开始结构化设计的东西的原型。
这是一个单元测试框架的例子。它隔离一个函数，并在各种参数上测试，但框架本身有点像脚手架。它当然不是真正的客户端代码，但它充当了足够小的客户端，以访问我们感兴趣的模块。
测试覆盖率
我们今天倒数第二个主题是测试覆盖率。我们编写的测试应该单独和集体具有哪些不同的属性？
首先是语句测试。总的来说，所有测试应该至少执行程序中的每个语句一次。这很有道理，如果你没有测试导致某段代码运行，你怎么可能知道那段代码是否工作呢？所以这里有一个例子，一段伪代码。语句测试应确保在测试套件中至少有一个测试执行了所有四个语句。
确实存在开源和商业工具来测量语句测试，测量测试套件对给定代码的覆盖率。这样，当你的代码比我们在这里看到的要复杂得多时，尤其是比这两个连续的if-else复杂时，你就不必太费脑筋去手动计算你的代码有多少被覆盖了。
也就是说，对于简单的例子，自己推理是完全合理的，所以尝试一下前一页幻灯片中的相同代码。这里的答案是B。给定的伪代码需要两次通过代码才能实现最小的语句测试。一个最小的两次通过的例子是：条件1为真且条件2为真，这将执行语句1和语句3；然后在另一个测试中，条件1为假且条件2为假，这将执行语句2和语句4。无法在一次通过中完成，因为语句1和语句2是互斥的，语句3和语句4也是。
语句测试之后的下一种代码覆盖率是路径测试。路径测试类似于语句测试，但更彻底，现在每个可能的语句序列都必须出现在一个测试中。正如你可能想象的那样，这比语句测试要密集得多。与本课程相关的是，坦白说，这太多了，我们没有尝试为你的作业做路径测试，我们也不会要求你为你的作业做路径测试。
但再次，在简单情况下是可行的，所以再看一下这段代码，试一试。这里的正确答案是D。给定代码的路径测试需要四次通过代码：条件1为真且条件2为真；条件1为真且条件2为假；条件1为假且条件2为真；条件1为假且条件2为假。
边界测试
测试的第三个标准是边界测试，即程序行为以某种方式改变的边界情况。几乎所有的错误都发生在边界条件下。如果你的程序仅对边界条件有效，它很可能对所有其他情况也有效。如果你的程序对所有边界条件和至少一个非边界条件都有效，它很可能对所有其他情况都有效。请注意，可能有多个轴来衡量边界，因此可能有多个轴来进行测试。
考虑以下函数声明，你应该考虑哪些边界测试？再次，把它当作一个点击器问题，花点时间写下跳入你脑海的边界情况或阶段转换。
我们当然应该检查当我们找到元素并且它作为数组的第一个项目返回时，那是我们的下边界。还有我们的上边界，当我们找到元素并且它作为数组的最后一个项目返回时。但也应该检查边界的另一侧。我们应该检查当它刚好超出边界一个位置时。所以我们有一个测试说，哦，它刚好超出数组起始位置一个。我们还有一个检查，当它刚好超出数组末尾一个位置时。我们想要测试这个的原因不是我们想要检查声明范围之外的任意内存位置，而是为了测试边界，测试差一错误。
压力测试
除了语句、路径和边界测试，我们还应该考虑压力测试。这是当事情在数量、种类或其他因素上达到最极端的时候。这些测试可能看起来不像你的典型输入，但这是一件好事。开发人员倾向于关注典型输入，可能会完全忽略输入空间中的大片区域。系统地遍历输入空间或从中均匀随机选择，是获取开发人员或QA可能想不到自己编写的测试数据的合理方法。
所以这里有一个合理的压力测试：我们选择10个长度为10000的字符串，并用随机数据填充这些字符串。我们假设random_string函数就是做这个的。然后至于测试本身，我们与一个参考解决方案进行比较。这可能会让你觉得有些虚假。如果我们已经有这个函数了，为什么还要写一个新的？但我认为这实际上相当合理。我们可能正在改变算法，我们有旧版本，它慢或占用太多内存等等。我们可能正在新环境中重新实现算法，而我们在旧环境中已经有它工作了。或者我们可能正在内部化一个标准工具。例如，可能有一个Linux命令，但我们不想总是去请求操作系统或shell来做这件事，所以我们将在我们的程序中编写自己的函数。
当然，也有时候你没有参考实现。所以测试确实涉及检查合理的输出属性，即使确切答案不可用。我们在gcd的例子中看到了这一点。所以这里是另一个例子。再次暂停幻灯片，思考一下我们在这里可以检查哪些属性。花一两分钟头脑风暴一下。
结果必须是非负的。结果必须小于基于我们与random_string假定的接口的最大字符串大小。并且直到字符串长度为止的字符都不能是空字符。否则，至少就字符串长度而言，那将结束字符串。并且索引处的字符必须是空字符，这是我们定义的字符串结尾。
测试实践与总结
我真心相信测试是人们应该开始使用的东西。我主张编写测试，至少是基于接口的基本测试。是的，甚至在实现本身之前，当然也在你的外部客户端之前。事实上，当事情不像作业2和3那样有不可违反的标准时，我甚至主张编写测试作为接口本身的健全性检查。当然，作为本课程和许多其他课程的实际情况，我们的评分系统中有比我们在仓库中给你的或在ti文件中展示的更多的测试。测试你自己的代码是你自己的工作，但至少现在，你知道了一些结构化的方法。
好了，现在你已经迭代地编写了测试，编写了软件，运行了测试，调试，编写了更多测试，等等。现在你准备好发布你的代码了。那么现在怎么办？
不要扔掉你的单元测试框架。记住关于原型设计的担忧，它存在的时间比它应该的长，这并不意味着你的单元测试框架应该成为你实际的发布代码。但这也不意味着你应该扔掉它们。不要扔掉你的断言。不要扔掉你的表示不变性检查。你投入了时间和精力来制作它们。此外，即使你可能正在发布代码，这也不是软件生命周期的结束。在某些方面，这只是开始。对于大多数项目，我们当然希望其有用寿命远远长于开发阶段。因此，维护阶段也要长得多。现在你已经发布了，你将开始收到错误报告或新功能请求，而回归测试的整个理念需要现有的基础设施仍然存在。
但仅仅因为你不应该扔掉所有东西，并不意味着它仍然必须在发布版本中运行。彻底的测试基础设施可能很昂贵。对内部表示和不变性的测试可能会遍历大型数据结构或长列表。每个函数中的前置条件和后置条件检查，如果我们经常调用这些函数，会变得非常昂贵。
所以我们需要一种方法来禁用测试代码，而不是丢弃它。但在我们学习那是什么之前，请注意不要移除测试代码和不要移除调试代码是有区别的。良好的结构化测试基础设施是有价值的。到处打印“我到这里了，X的值是D”的调试代码，价值较低。那些应该完全移除，除非它们结构特别好，并且可以以类似于测试代码的方式被禁用，但这不常见，几乎闻所未闻。
禁用测试代码
好了，现在让我们谈谈禁用测试代码。如果断言很昂贵，我们可以在程序中关闭它们。我们可以通过更改代码来实现。宏NDEBUG被assert库用作条件，以检查我们是否应该将assert视为一个函数式宏来执行语句，然后要么继续要么终止，或者是否应该将其视为一个完全不执行任何操作的空操作，它甚至不计算语句。更好的是，我们可以在不更改代码本身的情况下，仅通过构建命令来触发assert的这种行为。GCC接受一个构建选项-D，这相当于在我们程序顶部的一个#define。
应用于本课程，你经常会想说，我必须写我的断言，但也许我正在测试一些密集的东西，例如在作业4中，你将编写自己的is_valid表示不变性检查。所以在你的最终版本中，你将构建它以禁用它们，这样程序就快了。但在你开发它时，或者在你用它来测试我们给你的有错误版本时，你会希望它们开启，以便获得测试的全部好处。
请注意，我们可以为自己设置与assert库相同的东西。我们已经看到用于防止多重包含的#ifndef和#endif配对，我们可以使用它的正版，#ifdef，来测试是否给出了#define以启用我们的测试功能。这正是assert库用上面的NDEBUG所做的。事实上，我们可以完全按照assert的做法，直接使用NDEBUG本身，但这意味着你无法将你的自定义功能测试与程序中的其他断言解耦。所以前一页幻灯片的方法更通用。
总结
本节课中我们一起学习了软件测试的核心概念与实践方法。我们探讨了测试的重要性，了解了不同角色（开发者、QA、客户）在测试中的职责。我们学习了外部测试，包括手动测试、自动化脚本和回归测试，以及如何利用Shell脚本提高测试效率。我们深入探讨了内部测试，特别是C语言中的断言机制，用于验证前置条件、后置条件和表示不变性。我们介绍了单元测试的概念，包括如何通过脚手架和桩来隔离测试模块。我们还讨论了测试覆盖率，包括语句测试、路径测试、边界测试和压力测试，这些都是设计全面测试套件的重要考虑因素。最后，我们强调了在发布代码时不应丢弃测试基础设施，但可以通过条件编译（如NDEBUG宏）来禁用昂贵的测试代码，以平衡运行时性能与可维护性。
测试很容易被忽视，调试可能被视为某种终极的逻辑谜题挑战。但我确实希望你能考虑一个全面测试套件的价值。特别是，你在测试上花费的时间，可能会为你节省同样多甚至更多的时间，相比于你似乎无法摆脱的一个接一个的错误打地鼠游戏。
下次我们将讨论数据结构，然后下周的第一讲也是唯一一讲将再次讨论调试，就像今天的测试一样，旨在给你一个结构化的方法，以取代新手程序员常用的低效技术。然后下周四开始期中考试期，详情请查看课程网站。
013：数据结构 📚
在本节课中，我们将学习数据结构，特别是链表和哈希表。我们将探讨它们如何作为抽象概念，帮助我们更高效地组织和操作数据。课程内容将直接关联到即将到来的作业3。
概述
数据结构是关于数据的抽象。它们不仅仅是执行操作，更是代表了一组数据及其操作的“本质”。在COS 126中，我们学习了面向对象编程和对象。数据结构就是一组数据以及可以对这些数据执行的操作的集合。我们可以将它们视为构建模块，帮助我们解决其他问题。我们构建链表不是为了链表本身，而是为了用它来解决问题。这就是抽象的本质：隐藏底层的复杂细节，提供最高级别的接口来帮助我们解决问题。
为什么现在学习数据结构？
现在学习数据结构有几个原因。首先，这与作业3直接相关。链表可能有些棘手，更多的接触对理解它们有好处。其次，在C语言中，链表是动态内存的一个很好的中级介绍，它不仅仅是玩具示例，而是有实际用途的动态内存分配。我们已经看到，C语言中的动态内存与Java中的非常不同。一旦我们了解了链表，我们就可以继续学习其他更有趣的链表结构。对于作业3，你需要了解链表和哈希表。有些COS 217的学生可能对链表了解不多，许多COS 217的学生对哈希表了解甚少。因此，这里提供一个概述。
顺便提一下，作业3已经发布。但绝对不期望你现在就开始做。请先专注于期中考试，然后尽可能享受为期四天的秋假。如果你在秋假后才开始做作业3，那完全没问题。你仍然有将近两周的时间来完成它。事实上，第10、12、13次甚至第14次的部分课前辅导课都会讨论与作业相关的材料。你不必等到所有这些都完成，但当然可以等到我们开始涉及这些材料时再开始做作业，而不是现在就开始做，结果因为我们对相关内容了解太少而感到困惑。
作业3：符号表
作业3要求你用两种不同的方式实现一个符号表。但在深入探讨之前，我们首先应该弄清楚什么是符号表。你可能在另一种编程语言中见过它，可能被称为字典、关联数组或键值存储。但如果你没见过，那也没问题。你熟悉这个概念。它是一组键值对，一个查找表，就像一本真实的实体书字典。现在，让我们具体化，假设键是字符串，值是整数。
以下是一些例子：
-
它可能是一个名字和他们的毕业年份。
-
它也可能是一个棒球运动员和他们的球衣号码。
-
由于本课程开始学习系统编程，它可能是编译器内部的一个实现，其中我们有一个从变量到其初始值的查找表。
我们将研究两种不同的方式来实现这些键值对集合。链表实现相对简单，但效率较低。然后，我们将研究哈希表作为一种更可扩展和高效的解决方案，但代价是理解和实现起来更复杂。最后，我们将讨论在所有键值对集合的实现中都会遇到的一个共同问题。
链表实现 🔗
也许不足为奇，数据结构通常用结构体来表示。这些是你在C语言中可能用来实现链表的结构类型定义。课前辅导课在完整程序（一个栈ADT）的上下文中展示了这样的数据结构，该栈是用链表实现的。但现在，让我们单独看看链表。
一个节点的结构体包含键、值以及指向链表中下一个节点的指针的字段。在我们的示例中，键是一个常量字符指针（字符串），节点的键不能被更改。我们目前假设值是整数类型。指针是指向另一个节点的指针。乍一看，这看起来很奇怪。似乎数据类型将自身作为一个字段，这会有问题，但事实并非如此。一个节点可以有一个指向另一个节点的指针，这没有问题。编译器知道如何处理这个问题，并且知道如何分配足够的空间，因为，嗯，它是一个指针。编译器知道所有指针都是8字节。所以这不是问题。
为了节省空间，我们将每个节点画出来，使其键完全包含在结构体内部，因为键实际上是一个字符串，所以它实际上是一个内存地址，因此它指向其他地方，如上一张幻灯片所示。但为了在幻灯片上减少交叉线等，我们假设它就在结构体本身中。
列表的结构体包含一个字段。我们称之为first，它只是头指针，指向列表中的第一个节点。这样的结构体，只有一个字段且该字段只是对另一种类型的引用，有时被称为管理器或包装器结构体。我们将看到，为了封装我们的数据结构，这非常重要。这样，没有客户端能够在不使用API的情况下乱动内部结构。事实上，没有客户端甚至能够知道我们的实现是什么，因为他们只能看到一个指向这个结构体的指针，也就是管理器，而不是实现的实际复杂细节。
回顾：结构体、指针和动态内存
在继续之前，快速回顾一下最近关于结构体、指针和动态内存的讲座内容。我们可以使用calloc在堆上分配空间，它会将内存清零。这意味着每个指针的值都是0，这意味着它们指向地址0。我们称这些为空指针。我们可以使用点符号访问结构体的字段。我们可以使用地址运算符获取内存中变量的地址。通常，我们只有一个指针来访问结构体，而不是将结构体本身作为变量。这很自然，因为我们经常动态分配结构体，因此我们只有指针来表示它。我们可以解引用指针，然后使用点符号。但更常见的是使用箭头符号直接进行此操作，这更符合习惯用法。
链表API设计
我们使用链表来实现符号表。在作业3中，我们给了你符号表的API，但没有给你链表的API。不过，我们当然鼓励你设计你的链表，使其具有良好的功能模块化。那么，让我们思考一下，什么是合理的链表API？也就是说，我们可能想为链表定义哪些操作。
我们需要创建一个链表。创建链表就是分配列表结构体并将其初始化为空列表，也就是说，头指针应该指向NULL。这是一个快速操作，只是一个分配和一个指针赋值。
向链表中添加一个节点。这变得有点复杂。现在，如果我们允许重复，这很容易。只需分配一个新节点，把它放在列表的前面。但如果我们不允许重复，现在我们必须遍历整个列表以确保没有重复。我们可能遍历整个列表，然后在前面添加一个新节点；或者我们可能维护一个顺序，这样我们只需要检查一部分，直到找到节点应该插入的位置。但无论哪种情况，这都是一个线性操作。
我们还需要能够执行搜索以检查键是否存在。那么这个操作的性能如何？花点时间想一想，在链表中搜索一个键的增长阶是什么？实际上，这里的答案并不是很明确，它取决于工作负载，取决于插入算法。例如，如果我们的工作负载是我们通常对我们最近添加的东西进行大量搜索，并且我们选择将最近添加的项放在列表的前面。平均来说，这很快。但如果我们插入在前面并随机查找项目，那么平均来说，我们很慢。如果我们按顺序插入并随机查找项目，平均来说仍然很慢，但也许根据具体情况我们稍微好一点，因为我们只需要搜索一部分来查找重复项。我们的搜索结果将是O(n)。所以，是的，这是O(n)。除非我们对工作负载有非常强的假设，认为它不是任意的，不是随机的，否则它就是O(n)。
我们应该考虑的另一个操作是有一个从链表中删除的方法。这也会很慢。删除本身只是几个指针操作。但找到执行这些操作的位置是O(n)。同样，我们必须遍历列表以找到要删除的东西。当然，如果我们想删除并释放所有内容以销毁链表，我们必须删除n个项目。这里没有搜索。所以是O(1)乘以n，但那仍然是O(n)。
因此，链表的特点是大量线性操作。如果我们有一个存储大量不同键值对的符号表，它会变得相当慢。所以让我们探索一个更复杂的数据结构，并希望增加的复杂性实际上意味着更少的计算复杂性。
哈希表实现 🗂️
哈希表是一组键值对的列表，我们希望每个集合都很小。实现哈希表的一种方式是使用链表数组。我们希望每个列表的长度为0、1或2。在这种情况下，我们对链表的线性操作就不是问题了。遍历仍然是非常少量的工作。但要做到这一点，我们需要一个足够大的数组来使这成为可能，以及一种将数据拆分到不同列表的有效方法，以便我们在数组的所有元素中获得大致均匀的分布。
这些是你在C语言中可能用来实现哈希表的结构类型定义。你的会更好。值不会只是int，桶的大小可能能够改变。这里的绑定包含一个键、一个值以及指向列表中下一个绑定的地址。我们称之为绑定，因为它将一个键绑定到它的值。但你也可以称之为映射、键值对，甚至只是一个节点，因为它基本上与我们在链表中作为节点的东西相同。
我们的管理器结构体在这里包含一个名为buckets的数组。它有bucket_count个元素，每个元素的类型是binding*，即每个元素指向一个绑定。绑定与链表结构中的节点完全相同。现在，我们只是有一大堆链表，而不是只有一个。
哈希表示例
让我们看一个具体的例子。这里我们将使用一个较小的数组大小，7。让我们离开棒球运动员的主题，为我们的键主题转向俄罗斯风格。稍后我们将讨论我们希望哈希函数具有哪些属性。我提到过确定性，但在整个表中要均匀。通常，我们会选择一个具有一些一般数论性质的算法，然后通过取模来约束它，如前所述。但现在，让我们假设我们有一个函数，它会产生我们在幻灯片上看到的数字。
我们从一个数组开始，其中每个桶都是空指针，也就是说，没有一个桶有任何绑定。我们哈希“the”并得到一个巨大的数字。我们对7取模得到一个有效的数组索引0到6，结果是1。我们查看以buckets[1]为头的列表，发现什么都没有。buckets[1]是NULL。所以那个键不可能已经在表中。如果它在，它就会在那个桶里。所以我们必须插入一个具有该键的新绑定。我们添加绑定“the”。我们没有指定这里的值是什么，因为它们对于描述哈希表的基本原理并不重要。所以我将忽略那个字段。但如果绑定是calloc分配的，它将是0；如果是malloc分配的，它将是未确定的垃圾，直到我们显式地给它赋值。在实际实现中，你将把值设置为put函数中作为value参数传递的任何值。指向下一个绑定的指针将是NULL，因为在这个桶中只有一个绑定。
下一个我们要添加的键是“cat”，所以我们哈希它并得到2。我们检查buckets[2]，发现它是空的，于是插入。现在我们有了一个数据结构，在桶1中有一个绑定，在桶2中有一个绑定。下一个我们要添加的键是“in”。我们哈希它并得到5。我们检查buckets[5]，发现它是空的并插入。现在我们有了一个数据结构，在桶1中有一个绑定，在桶2中有一个绑定，在桶5中有一个绑定。
现在让我们让事情变得更有趣。下一个我们要添加的键是“the”。我们哈希它并得到1。我们检查buckets[1]，它不是空的。所以我们遍历，直到要么找到一个键为“the”的绑定，要么到达NULL。我们确实找到了“the”，这意味着“the”是一个重复项。在作业3中，将重复键放入符号表应该失败，而不改变表。所以我们在这里不做任何更改。
下一个我们要添加的键是“hat”。我们哈希它并得到2。我们检查buckets[2]，它又不是空的。所以我们遍历这个列表，直到要么找到所需的键“hat”，要么到达NULL。在桶2中，我们看到一个带有“cat”的绑定，这不是“hat”。而next指向NULL。所以“hat”不在那里。我们可以插入。插入时，我们应该插入前面还是后面？坦率地说，这并不重要。回想一下，无论如何我们都必须搜索整个列表。所以是O(n)，排序与否。我们不妨把它加在前面，因为在一般情况下更容易。另一方面，根据你如何进行遍历，你可能仍然留有指向最后一项的指针，在这种情况下，我们当然可以同样容易地在前面或后面插入。此外，这里的重点是，我们有一个具有良好哈希函数的大表。这些冲突应该很少见。每个列表应该非常短。所以把它放在前面、后面还是中间并不重要。这更有理由选择更容易的解决方案。所以，什么最方便就选什么。总的来说，我们看起来很不错。很多长度为0和1的列表，只有一个不幸的桶长度为2。
哈希表复杂度分析
有了这个例子，让我们回到我们的复杂度分析。现在创建是常数时间工作。它独立于表中的项目数量，尽管它是一个更重量级的操作，因为我们必须分配桶数组。向表中添加一个项目需要一个哈希操作。如果我们的键很大，哈希可能是一个不小的操作。我们必须取模以找到桶，并且我们必须通过遍历整个桶列表来确保没有重复，然后进行插入。那么这里的复杂度是多少？看看这些选项。暂停视频，做一个决定，然后准备好时重新开始。
我认为B是一个合理的答案，因为如果键的数量远远多于桶的数量，即使是一个完美分布键的哈希算法仍然会产生许多绑定的桶。但我认为C是最好的答案。因为即使桶列表足够大，仍然存在线性最坏情况。如果所有键都哈希到同一个桶，那就只是一个单链表。所以我们最好选择一个好的哈希函数。同样，稍后再详细讨论，对于这个作业不用担心，我们会给你一个具有这些良好属性的函数。
哈希表设计考虑
哈希表，我们有哈希函数来找到一个桶，然后它只是同样长度的列表，但那个链表应该是一个小的常数长度。不过，我们顺便提到了另外两个问题。一个是桶数组可能太小。这意味着即使完美分布，所有列表都会很长；或者哈希函数可能不好。所以如果键没有完美分布，一些列表会不成比例地长。
那么我们应该选择多少个桶？一方面，我们说我们想选择很多桶，因为桶太少是个问题。但不要太多，因为这在内存上是一个巨大的前期成本，如果我们分配太多，就会浪费内存。我们的总体目标是，我们希望在我们的最终表中，列表的长度是0、1或2。所以我们希望能够对我们将要添加的绑定总数有一个概念。这并不总是可能的，这就是为什么如果你快速浏览一下作业3的挑战部分，你会发现它扩展了哈希表。所以你开始时有一定数量的桶，然后最终当它变得太满时，你说我要创建一个新的更大的数组，以便更好地分布，你这样做直到一个合理的次数，在这一点上，如果你有非常大量的绑定，你真的无能为力。
哈希函数设计
在哈希函数方面，我们提到最差的哈希函数会为每个元素生成相同的哈希码。那将退化为一个链表。但这不必是一个稻草人论点。考虑字符串长度。这不会为每个可能的键生成相同的哈希码。起初听起来还不错。但对于名字来说，这根本不是随机的。大多数人的名字长度在1到20个字符之间，对于几乎任何自然语言键来说都是类似的。
那么，什么通常构成一个好的哈希函数？这实际上是数值分析中的一个开放问题，但我们确实有一些想法。我们刚刚看到字符串长度不是一个好的哈希函数。实际上，它们的ASCII值之和同样被压缩，因为它严重依赖于长度。然而，如果我们开始真正区分字符串中的不同位置，那么结合ASCII值，我们可以得到一些分布。在实践中，如果我们的加权因子与桶计数互质，效果最好。如果两个整数没有大于1的公因数，则它们是互质的。也就是说，它们的最大公约数是1。例如，12和13是互质的，但12和14不是。
所以这实际上是一个相当好的、简单的启发式方法，计算起来很容易，在实践中效果很好。
哈希函数代码实现
这是该哈希算法转换为代码的形式。请注意，这实际上是以与字符相反的顺序进行加权和的加权，但它仍然具有相同的属性，并且比上一张幻灯片上的求和计算效率更高。在上一张幻灯片上，我们有a^i * s[i]。但在这里，我们每次只有一个额外的乘法因子a，而不是为每个i计算a^i，所以我们通过每次只进行一次额外的乘法而不是计算乘积来节省大量乘法。
你可能还会看这个，即使我们这里有一个size_t，你可能会说，这最终会溢出，我们在这里做大幂运算。我们做乘法。如果我们有一个足够长的字符串，这将会溢出。你完全正确。但回想一下我们之前关于溢出的讲座，在存在溢出的情况下，操作的值与没有溢出时的值相同，只是模2^k，其中k是位数。所以数值属性在很大程度上得以保留。此外，在最后进行取模以获得桶数组索引时，会丢弃数字高位的大部分内容。当我们进行取模运算时，我们只查看数字的低位。因为数字模2^k是相同的，并且我们取模的值小于2^k（我们几乎肯定是这样，否则那将是一个巨大的数组），所以无论我们是否溢出，我们的计算都会产生相同的桶索引。因此，这是一个相当不错的算法，具有一些良好的属性，并且不关心我们如何在系统上表示整数的细节。
这或多或少是我们在作业3中将要给你的函数。
符号表中的键管理 🔑
最后，让我们讨论一下符号表。无论是链表还是哈希表实现，让我们谈谈我们的键。
为了与我们一直在看的相同实现保持一致，让我们继续看哈希表。考虑这个用于任意哈希表（任意符号表）的add方法。该函数创建一个新绑定，并将一个键（一个内存地址）分配给该绑定的key字段。这似乎很合理。我们想接收键并将其作为我们新绑定的键，所以让我们继续。
这是调用我们add函数的客户端代码。它将k和表传递给table_add函数。table_add函数创建一个新绑定并将k分配给它。现在一切似乎都还好。但是等等。k是k[0]的地址。它是一个地址。具体来说，它是客户端拥有的一个地址。客户端分配了变量k。因此，客户端可以对这个地址做任何它想做的事情。客户端完全有权利说，哦，现在我想让这是另一个字符串，“Gerig”，而不是“Ruth”。这将在哈希表中引起麻烦。现有节点的键已从“Ruth”更改为“Gerig”。这破坏了哈希表。如果我们搜索“Ruth”，它将失败。键“Ruth”不再存在于内存中的任何地方。如果我们搜索“Gerig”，很可能也会失败，至少在哈希表实现中是这样，因为“Gerig”很可能在错误的桶中。同样，在链表中，这可能不一样，但它仍然是一个问题，因为当我们为“Ruth”插入时，“Ruth”不存在，而当我们从未为“Gerig”插入时，“Gerig”却存在。所以在任何一种实现中这都是一个问题。只是在哈希表中更加明显。
解决方案：防御性复制
那么我们该怎么办？我们如何避免这场灾难？我们不能阻止客户端使用它自己的内存。所以我们必须制作我们自己的符号表键的副本。我们必须确保我们的符号表不引用客户端内存中的副本。换句话说，我们将确保我们的表拥有自己的键。
所以在我们的插入函数内部，它将为表的键副本分配足够的空间。记住在strlen的结果上加1，以考虑空终止字节。现在，该函数将新内存的地址分配给绑定。所以绑定不指向客户端的内存，它指向实现的内存。最后，该函数将给定键的字符复制到新分配的内存中。
那么这里缺少什么？在幻灯片上，一切都很好。但回想一下上周的讲座，在我们进行strcpy之前，我们真的应该确保new_key不指向NULL。也就是说，分配成功了。否则，我们的程序将通过解引用空指针和段错误以一种不优雅的方式崩溃。相反，我们应该以另一种方式处理它，在赋值和strcpy之间使用条件语句。值得注意的是，如果你查看作业3的符号表API，你会发现put返回一个表示成功或失败的int。所以不像在这个简单代码中我们有一个void，除了可能抛出断言外，我们做不了什么。在你的作业代码中，你将能够做一些合理的事情。
防御性复制示例
让我们回到我们的例子，客户端在将k传递给add函数后更改了自己的k。这是我们进行防御性复制之前的内存布局。但现在有了防御性副本，我们的key不指向来自我们内部的k变量。这意味着我们的实现不引用客户端的内存，而是引用它自己的内存，其中包含字符串“Ruth”的自己的副本。该副本由数据结构拥有。因此，当客户端用“Gerig”覆盖k中的“Ruth”时，我们的哈希表不会受到影响。这是一个胜利。
内存管理责任
保护表的键的胜利。现在，既然表拥有自己的键，那也意味着它负责释放它们。当一个绑定被销毁时，我们总是想，好吧，如果我已经为绑定分配了内存，我将不得不释放它。但现在，在那个绑定内部是内存，它是对一个字符串的引用，这个字符串也是在实现中分配的。所以我们也必须释放它。
总结
本节课到此结束。今天的讲座相对较短，因为我不想用作业3让你不知所措，知道你可能大约两周后才会开始。下次我们将讨论调试，特别是动态内存错误，这些错误非常棘手，并且再次与作业3密切相关。然后在周四之后，没有讲座，因为你将在美国东部时间周四上午9点开始期中考试，考试将持续48小时，然后你将迎来期待已久的秋假。
014：调试 🐛
在本节课中，我们将学习如何系统性地查找和修复程序中的错误（即“调试”）。我们将从理解编译错误信息开始，逐步探讨一系列调试策略和常见错误模式，特别是针对动态内存管理中的问题。掌握这些技巧将帮助你更高效地定位和解决代码中的缺陷。
理解错误信息 📝
上一节我们介绍了调试的重要性，本节中我们来看看调试的第一步：理解编译器给出的错误和警告信息。
当构建程序时，编译器或链接器可能会报告错误或警告。错误意味着程序不符合C语言规范，无法生成可执行文件。警告则提示代码中可能存在潜在问题，但程序仍可编译。
以下是几个常见的构建时错误示例及其分析：
-
错误：
#include <stdio,h>：预处理器报告致命错误，因为头文件名中的逗号应为点号。正确的写法是#include <stdio.h>。 -
错误：未终止的注释：预处理器发现
/*注释没有对应的*/来结束。 -
错误与警告的误导：有时编译器报告的错误位置可能因代码格式而偏移。例如，某行缺少分号，但编译器可能在下一条语句（如
return）处报告错误，并附带一个关于函数可能未返回值的误导性警告。修复原始错误（加上分号）通常能使警告消失。 -
警告与链接器错误：如果函数名拼写错误（如
printf拼成prntf），编译器会给出“隐式声明”警告，而链接器则会报告“未定义的引用”错误，明确指出找不到哪个标识符。 -
不清晰的错误信息：对于某些语法错误（如
enum定义后缺少分号），编译器可能只给出晦涩的错误信息，提示“某处期望某个符号”。这通常意味着存在语法错误，需要仔细检查指示区域附近的代码。
调试建议：
-
善用编辑器的自动缩进功能（如在我们的Emacs设置中使用
Ctrl+X P）。错误的缩进往往能直观地提示语法错误的位置。 -
一次只修复一个错误。后续的某些错误可能是前一个错误引发的假象，修复前者后，它们可能会自动消失。
先思考，再修改 🤔
在尝试修复错误之前，进行系统的思考至关重要。盲目地修改代码通常会使问题复杂化。
有效的方法包括：
-
逐行朗读代码：向自己、同学甚至一个玩偶解释你的代码。这个过程能迫使你放慢速度，仔细审视每一行，常常能发现之前忽略的错误。
-
形成假设，再验证：不要进行无目的的随机修改。首先，根据观察和分析，形成一个关于错误根源的假设。然后，设计一个代码修改来验证这个假设。如果修改后问题解决或变化，说明假设可能是正确的。
如果你发现自己开始进行无纪律的修改，这通常意味着你对问题缺乏清晰的理解。此时应该暂停，并寻求帮助。
识别常见错误模式 🎯
许多错误都属于常见的模式。了解这些模式可以帮助你快速定位问题。
以下是C语言中一些频繁出现的错误：
-
switch语句贯穿：在case分支后忘记写break;，导致执行意外地流入下一个分支。 -
遗漏取址运算符
&：在需要指针的地方（如scanf的参数）使用了变量本身，而不是其地址。 -
变量类型过小：例如，用
char类型变量接收getchar()的返回值，无法正确处理EOF（它是一个int值）。 -
运算符优先级错误：因省略括号而导致表达式求值顺序与预期不符。
-
误用赋值运算符
=：在条件判断中错误地使用了=（赋值）而非==（比较）。 -
误用逻辑与位运算符：在条件判断中错误地使用了位运算符（
&,|）而非逻辑运算符（&&,||）。 -
链式比较错误：表达式如
5 < i < 10在C语言中是合法的，但其含义并非判断i是否在5和10之间。它实际等价于(5 < i) < 10，而(5 < i)的结果是0或1，它们都小于10，因此整个表达式恒为真。
注意：使用 -Wall 编译选项可以让编译器对其中一些错误发出警告。
关于“整体性错误”：在编写嵌套循环等模式化代码时，大脑容易忽略细节。例如，内层循环错误地使用了外层循环的计数器变量。这种错误在复制粘贴代码时尤其常见，需要格外小心。
关于作用域：C语言允许在内部代码块中定义同名变量，这会遮蔽外部变量。例如，在函数内定义的变量会遮蔽全局变量，在更内层的块中定义的变量会遮蔽函数内的变量。这与Java中局部变量遮蔽实例变量类似，但C语言允许更多的遮蔽情况。
分而治之：简化问题 🔍
面对一个复杂且出错的测试用例或庞大的代码库时，采用“分而治之”的策略非常有效。
简化输入：
-
如果一个大测试用例失败，尝试不断裁剪输入数据，直到找到一个最小的、仍能触发错误的输入。最后被移除的那部分内容很可能就是触发错误的关键。
-
反之，也可以从一个能成功运行的简单输入开始，逐步添加内容，直到错误出现。最后添加的部分就是问题所在。
简化代码：
-
如果一个大程序失败，可以尝试注释掉部分函数调用。当注释掉某些代码后错误消失，那么被注释的部分很可能就是问题的根源。
-
同样，也可以从一个极简的、能正确运行的程序开始，逐步添加功能模块，直到错误重现。
重要提示：在注释或移除代码时，请保留原始代码（例如使用注释或 #if 0），以便在需要时恢复。
聚焦于最近的更改 💾
这条建议有两层含义：一是要在开发过程中持续测试和调试（即“聚焦于最近的代码”）；二是一旦出现问题，应首先检查最近所做的修改。
这体现了回归测试的原则：确保新的更改不会破坏之前正常的功能。为了实现这一点，你需要有可靠的版本控制。
使用版本控制（如Git）：定期提交代码，即使它还不完美或存在已知问题。这为你创建了一个个“安全点”。当你后续的修改陷入混乱时，可以轻松地回退到之前一个已知的状态进行比较，或者重新开始。这远比在未版本控制的代码中迷失方向要高效得多。
增加测试以定位错误 🧪
有时，解决测试失败的最佳方法是增加更多、更细粒度的测试。
内部测试（如断言、参数验证）能帮助你：
-
主动定位错误：通过添加更多检查点，可以精确缩小错误发生的范围。
-
被动排除嫌疑：如果代码的某个部分通过了严格的内部测试，那么你就可以更有信心地暂时将其从怀疑列表中排除，将调试重点转向其他区域。
使用打印语句进行调试 🖨️
对于简单的调试，在代码中插入针对性的打印语句（printf）是一种直接有效的方法。它可以帮助你了解程序执行到哪一步，或者特定变量的值在何时发生了变化。
注意事项：
-
输出缓冲：标准输出（
stdout）通常是缓冲的，这意味着printf的内容可能不会立即显示在终端上。如果程序在缓冲区刷新前崩溃，你将看不到这些调试信息。- 解决方法：在格式字符串末尾添加换行符
\n通常可以刷新缓冲区。更可靠的方法是调用fflush(stdout)强制刷新。或者，将调试信息输出到无缓冲的标准错误流（stderr）上。
- 解决方法：在格式字符串末尾添加换行符
-
输出到文件：对于长时间运行的程序，将调试日志写入文件非常有用。这提供了一个持久的记录，便于事后分析，也避免了与程序正常输出混在一起。
示例代码：
fprintf(stderr, "调试信息: 变量 x = %d\n", x); // 输出到 stderr
// 或
printf("状态: 进入函数 foo\n");
fflush(stdout); // 确保立即输出
使用调试器 🐛➡️🔍
作为打印语句的替代，使用调试器（如GDB）能提供更强大、更交互式的调试体验。它允许你：
-
逐行执行程序。
-
随时查看任何变量或内存位置的值。
-
设置断点，在特定条件满足时暂停执行。
-
无需修改代码即可获得所有这些信息。
强烈建议：花30分钟到1小时认真练习GDB的基本用法。这将在未来的调试工作中为你节省数十小时的时间，也能让你在寻求帮助时更高效地与助教协作。
动态内存调试专题 💥
动态内存管理是C语言中常见的错误来源。错误通常围绕几个核心操作（malloc, realloc, free, 指针解引用）和几种错误模式（悬空指针、越界访问、内存泄漏、重复释放）。
以下是几个动态内存错误的例子：
-
解引用未初始化的指针：指针变量未赋值，其值是随机的。解引用它可能导致修改任意内存位置或引发段错误（Segmentation Fault）。
int *p; // 未初始化 *p = 5; // 错误：解引用未初始化的指针 -
解引用已释放的指针（悬空指针）：指针指向的内存已被
free，但后续仍通过该指针访问内存。int *p = malloc(sizeof(int)); free(p); *p = 10; // 错误：解引用已释放的指针 -
未检查
malloc返回值：如果malloc失败并返回NULL，解引用这个空指针会导致段错误。int *p = malloc(sizeof(int)); *p = 5; // 如果 malloc 失败，p 为 NULL，此处错误 -
内存泄漏：分配了内存，但在程序结束前丢失了所有指向它的指针，导致无法释放。
int *p = malloc(100 * sizeof(int)); p = malloc(200 * sizeof(int)); // 错误：第一块内存的指针丢失，发生泄漏 -
重复释放：对同一块内存调用
free超过一次，这会破坏堆的结构。int *p = malloc(sizeof(int)); free(p); free(p); // 错误：重复释放
利用段错误进行调试 💡
段错误（Segmentation Fault）通常由解引用无效指针（如空指针、悬空指针或越界指针）引起。虽然它导致程序崩溃，但这是一个好消息，因为它明确地指出了错误发生的位置，远比程序静默地产生错误结果要好。
如何利用GDB定位段错误：
-
使用
-g选项编译程序：gcc -g -o program program.c -
在GDB中运行程序：
gdb ./program -
输入
run命令，让程序运行直至崩溃。 -
程序崩溃后，输入
where（或bt）命令。这将显示程序崩溃时的调用栈，即导致崩溃的一系列函数调用。 -
调用栈最顶部的行就是崩溃发生的位置。检查该行代码中涉及的指针变量，然后沿着调用栈向下回溯，分析这个指针是如何被赋值和使用的，从而找到错误的根源。
诊断内存分配大小错误 📏
分配不足的内存是一个常见错误。可以通过以下方法诊断：
手动检查：使用搜索工具查找代码中所有的 malloc、calloc、realloc 调用，逐一核对分配的大小是否正确。
常见的大小错误示例：
-
字符串分配少一个字节：为字符串分配内存时，必须为结尾的
\0空字符预留空间。strlen(s)返回的是字符串长度，不包括\0。char *str = malloc(strlen(s)); // 错误：少1字节 char *str = malloc(strlen(s) + 1); // 正确 -
对指针使用
sizeof：sizeof(pointer)返回的是指针本身的大小（通常是8字节），而不是它指向的数据类型的大小。long double *arr = malloc(10 * sizeof(long double*)); // 错误：分配了指针的大小 long double *arr = malloc(10 * sizeof(long double)); // 正确 // 或者更佳： long double *arr = malloc(10 * sizeof(*arr)); // 正确：使用解引用指针的类型
系统化测试法：如果手动检查无效，可以尝试一个系统化的方法：
-
临时将所有
malloc调用替换为分配一个非常大的固定值（例如malloc(1000000)）。 -
运行程序。如果错误消失，说明问题很可能出在某个分配大小不足的
malloc上。 -
逐个将
malloc调用恢复原状，每次恢复后都测试一次。当错误再次出现时，最后恢复的那个malloc就是有问题的。
类似地，对于 free 相关错误：如果怀疑是双重释放或悬空指针访问，可以尝试注释掉所有 free 调用。如果错误消失，再逐个恢复 free 调用以定位问题所在。
使用内存分析工具 🛠️
最后，可以利用专门的内存分析工具来检测动态内存错误。
-
Meminfo：由普林斯顿大学的教员编写，专门为COS 217课程设计，用于检测内存泄漏和堆损坏。
-
Valgrind：一个功能强大且广泛使用的免费工具套件。其中的
memcheck工具可以在程序运行时检测多种内存错误，包括内存泄漏、越界访问、使用未初始化的内存、重复释放等。
在课程作业中，通常会要求你提交干净的Meminfo报告。但在自己调试时，强烈建议尝试使用Valgrind，它能提供极其详细和有用的错误信息。
本节课中我们一起学习了系统性的调试方法。我们从理解编译器信息开始，探讨了思考策略、常见错误模式、分而治之的技巧、版本控制的重要性，以及针对动态内存错误的专门调试技术，包括使用打印语句、调试器（GDB）和内存分析工具（如Valgrind）。掌握这些技能将极大地提升你诊断和修复程序缺陷的效率。
015：模块化与接口设计 🧩
在本节课中，我们将学习模块化设计与接口设计的基本原则。我们将探讨C语言中如何实现信息隐藏和封装，以及如何设计清晰、健壮的模块接口。课程将涵盖良好模块设计的八个关键特征，并通过具体示例进行说明。
抽象与模块化
正如本课程一贯强调的，一切最终都回归到抽象。模块化是抽象的具体表现。我们将实现的细节隐藏在接口之后，无论是像字符串模块那样的无状态模块，还是像ADT（抽象数据类型）那样的抽象对象。
在创建这些抽象时，我们限制了客户端对模块的操作。这乍听起来像是坏事，但最终却为模块的实现者提供了强大的保证：他们受到契约的保护，无需处理不合理的客户端操作。因此，只要自身没有错误，他们可以确信对象的内部状态在没有客户端干预的情况下将保持一致。
在创建这些抽象时，我们确实限制了客户端的操作，但我们也有机会向客户端传达他们可以且应该如何使用该模块。
良好模块设计的八个特征
在本节中，我们将讨论一个设计良好的模块应具备的八个特征。我们将从你在126课程中已经熟悉的面向对象概念开始，即封装和信息隐藏。
1. 封装与信息隐藏 🔒
信息隐藏是限制客户端直接访问和操作模块状态的原则。封装则是将模块的状态与其功能绑定在一起，这既促进了信息隐藏，又提供了让客户端以受控方式访问内部状态的能力。
这些目标之所以重要，有几个原因：
-
安全性：如果客户端可以侵入模块并更改内部数据，那么模块的开发者就无法保护模块的状态，也无法保证其行为或正确性。
-
解耦与维护：即使客户端不更改模块的数据，一个能看到模块内部数据的客户端很可能会依赖于此。这意味着底层表示的任何更改都会破坏该客户端的代码。
2008年图灵奖得主芭芭拉·利斯科夫是数据抽象领域的先驱。她在70年代中期撰写了一篇关于该主题的基础性论文，精确地阐述了我们对ADT的期望：ADT应仅由其操作定义。客户端无需知道或关心底层表示是什么。
示例：列表ADT
让我们看一个具体的例子，这是我们在准备作业3时已经见过一点的列表ADT。以下是一个合理的列表数据类型实现：
struct node {
int payload;
struct node *next;
};
<https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-cos217-c-sys-prog/img/f8bbffc81a7a5701200691e3d856cb09_13.png>
struct list {
struct node *first;
};
列表是一个结构体，包含一个指向其第一个节点的指针。节点包含一个有效载荷（为简单起见，这里只是一个int）和一个指向链中下一个节点的指针。
我们有一些想要执行的自然操作，例如创建新列表或将项目插入列表。我们在此过程中做出一些设计决策。也许我们会发现这些决策不明智，但稍后会讨论。目前，我们说这是一个合理的列表起点。
那么，整个接口应该是什么样子？我们在这里看到的函数与数据的底层表示交互。这在一开始看起来没问题。但是，类型本身需要对客户端隐藏。如果函数接受该类型的参数并返回该类型的值，这就产生了冲突，因为我们至少需要揭示这些结构需要多少内存。
相反，如果我们在接口中只使用指针，大小是明确定义的，因为所有指针的大小都相同。客户端只需要知道struct存在即可。
让我们探讨一下“客户端只需要知道结构体存在，而不需要知道其细节”这个想法。请看以下接口：
// list.h
struct node {
int payload;
struct node *next;
};
<https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-cos217-c-sys-prog/img/f8bbffc81a7a5701200691e3d856cb09_15.png>
struct list {
struct node *first;
};
struct list *list_new(void);
void list_insert(struct list *list, int value);
这个接口有什么问题？在这个接口中，我们提供了struct的完整定义。这意味着客户端知道底层表示。客户端可能不会利用这些知识做任何事情，但没有什么能阻止他们在自己的代码中使用内部状态的知识，或者更糟的是，直接篡改内部状态本身。
即使所有客户端代码都不是恶意的，这也意味着如果我们更改实现，客户端代码将会崩溃。此外，即使客户端代码根本不使用内部表示，假设我们有一个行为良好的客户端只通过接口交互，该客户端仍然必须重新编译其.c文件，因为表示的任何更改都会改变客户端代码所依赖的.h文件。
如果只有我们的.c文件更改，而不是.h文件，他们只需要重新链接新的.o文件并构建新的可执行文件，而无需重新编译自己的代码。
因此，接口文件应该提供状态结构的声明，而不是定义。
// list.h
struct list; // 不透明指针声明
struct list *list_new(void);
void list_insert(struct list *list, int value);
这行代码告诉编译器：“嘿，编译器，struct list是一个东西。但是，我不能告诉你关于它的任何信息。” 客户端程序员看不到实现，因此不会被诱惑直接操作列表对象的字段。更好的是，编译器在编译客户端时也看不到实现。因此，编译器实际上会禁止客户端直接操作列表对象的字段。这不仅仅是一种纪律，实际上是一种禁止。
2. 清晰的规范与契约 📜
但是，如果客户端看不到内部结构，它怎么知道该做什么呢？接口可以作为模块的规范。我们稍后会更多地讨论如何向客户端传达此规范的细节，但你已经知道基础知识：接口中的函数注释，就像你在作业中一直在做的那样。
我们如何正式指定我们的接口？首先，我们需要指定关于类型本身的一些信息。例如，它是一个列表，而该列表只是一个整数序列。
对于我们的插入函数，规范明确了行为，但命名可能还有改进空间。在开发规范时，我们应该停下来思考是否选择了正确的名称。也许我们应该称之为prepend，以明确它是在前面插入。另一方面，我们还没有看到任何表明它是有序的东西，所以prepend可能走得太远。最终，我们稍后会看到顺序确实很重要，所以也许prepend会更好。然而，insert是通用的，所以可能更现实的做法是让客户端理解这意味着什么，或者它可能更通用，因此可以更好地与现有接口配合，或者在我们更改底层实现时更不容易出错。
接下来是concat，这向我们表明，有时规范既关乎函数做什么，也关乎它不做什么。同样，在这里我们看到了更好命名的机会。没有规范，就无法判断p和q哪个是源，哪个是目标，因此我们真的应该命名参数以匹配。
nth_key再次在我们编写规范时给我们带来了问题。如果n超出了列表的长度，我们该怎么办？如果C语言有可选类型就好了。如果存在，则返回它；否则返回None。也许可以将nth_key改为返回一个int*指针，指向NULL作为一种选项，这有点像Java的想法：我们返回一个引用，该引用要么是null，要么是指向对象的引用。也许还有更好的选择，我们稍后会讨论。
你可能会认为这个规范很荒谬。如果我返回一个任意的int，这会产生各种不良副作用。特别是，我无法判断它是第n个值还是根本不存在第n个值。你说得完全正确。但我可以提供一些小小的支持：客户端不应该请求无效的项目。此外，这并非完全陌生。这基本上是C语言对数组越界访问的处理方式，而我们容忍了这一点。
规范很重要，因为它们允许在不运行代码的情况下推理代码的效果。例如，在这里，如果不记得关于列表的任何规范（它是在数组中、链表中，还是更高级的结构中？谁知道，谁在乎？），如果我们有规范，我们就可以追踪客户端代码的行为。
此外，在实际的软件工程中，这至关重要。多个团队设计项目的多个部分，每个团队都依赖于其他团队正在构建的东西，而这些东西尚未完成，这种情况并不少见。如果我们必须以某种方式序列化整个开发过程，让团队1必须在团队2完成之前完成，团队3甚至才能开始，那将是灾难性的，这还没有考虑到循环依赖。这将是一场灾难。因此，这种具有契约保证的形式化规范接口的想法是一个非常强大的概念，它不仅理论上很好，而且在实际中促进了现实世界的软件工程。
在惯用的C语言中，通常比之前的接口更进一步。C语言中的typedef关键字为类型创建一个新的别名。通常用它来为指向结构体的指针命名，而该结构体再次仅作为声明给出，而不是定义，就像我们见过的那样。
这并没有为我们的模块增加任何功能，也没有改变封装或信息隐藏的属性，但为我们用来传递ADT实例的句柄命名，使其感觉更像一个对象，从而可以鼓励封装向面向对象思维发展。
此外，出于某种原因，看到神秘的_T类型会使程序员不太可能尝试去做他们知道在其他情况下可以对struct或指向struct的指针使用.或->运算符的事情。如果我们正确设计了模块，并且在接口中只有声明而没有定义，他们将无法这样做。编译器不会允许，但这是一种诱惑，会浪费他们的时间，而且他们还会被关于“不完整类型”的错误所困惑，这不是我们经常使用的自然术语，但如果你尝试对只有声明而没有定义的东西使用.或->运算符，就会出现这种情况。因此，我们可以通过说“不，你不需要知道它是一个结构体，就把它当作一个list_t或stack_t或simtable_t。把它当作一个对象，就假装它是Java”来避免整个混乱。
3. 一致的内存与资源管理 💾
一个连贯模块的下一个特征是，它应该以结构化和一致的方式管理内存和其他资源。
具体来说，我们期望分配内存的模块默认也应该是释放它的模块。对于其他持久状态（如打开的文件）也是如此。
这里的理由很简单：分配资源的模块是知道它已被分配的模块。任何模块或客户端都不应负责预测其他模块的底层分配行为。即使我们期望如此，这对于调试来说也是有问题的。如果一个模块分配了内存，期望客户端会释放它，而客户端没有释放，我们会归咎于该模块。meminfo或Valgrind会指出在模块内分配内存的位置，然后说“嘿，它从未被释放”。我们除了查看该模块之外别无他法，会说“你没有释放内存”，但这不是模块的错，是客户端的错。
在某种程度上，如果客户端从不调用free函数，情况已经如此，但如果我们说客户端必须使用free函数调用显式释放指针，那么打破这种现状会使情况更糟。
让我们看看作业3中simtable的设计决策。每个绑定都有一个键和一个值。我们现在讨论的良好模块特征说，如果simtable分配了它，simtable就应该释放它。但这没问题。它仍然没有回答：应该是simtable分配还是客户端分配？
首先看键。如果simtable分配，会增加模块的复杂性。我们不仅要设置一个引用，还必须分配内存，将数据复制到该内存中，并记住在完成后释放它。但另一方面，如果客户端分配，我们会遇到之前讲座中提到的问题：客户端可能通过更改自己的内存来破坏数据结构的内部，而这是它应该被允许做的。因此，我们在作业3中选择让simtable制作一个保护性副本。
那么值呢？在这种情况下，客户端分配键的风险消失了。值是表中搜索的结果，而不是搜索目标。因此，如果客户端更改了表引用的值，这会更改绑定，但不会更改表本身的操作，例如其搜索完整性。搜索已放入表中的键将会成功，它返回的值可能不同，但搜索会成功。同样，搜索未插入表中的键将会失败。
因此，如果simtable拥有每个绑定中的值，它还必须知道每个值有多大，这需要更改接口。此外，它还将负责值的分配、复制和最终释放，这再次增加了模块的复杂性。因此，客户端所有权确实让simtable做的工作更少，而且没有我们在选择键时的决定性因素——那个巨大的风险因素。这听起来像是赢家。事实上，作业3规范中simtable接口部分的底部指出，simtable对象不得拥有其值。
关于资源管理的最后一点说明。有些情况下，函数分配内存然后将其传递回客户端，由该客户端永久拥有，这是有意义的。字符串模块就有这样的函数。strdup是一个函数，它为给定字符串的副本分配内存，将给定字符串的内容复制到新分配的内存中，并将字符串返回给调用者，并明确理解调用者现在对其负责。毕竟，没有str_free这样的函数。当我们遇到这种情况时，由于它们是相对罕见的例外，通过模块接口中的注释作为契约的规范必须明确指出内存现在是调用者的责任。这是一个例子。
4. 一致性 ✨
我们连贯模块的第三个特征是它应该具有一致性。
这可以体现在行为上，例如，让所有函数做出相同的资源管理决策，或者让所有函数都是线程安全的。但我们也应该追求风格和组成的一致性。
例如，模块中的每个函数都应遵循命名约定。如果函数是strlen但copy_string，那会很奇怪。通常，我们选择将模块名称作为非静态函数（即可能从模块外部调用的函数）的前缀。这减少了名称空间冲突的机会。考虑一下，大约每个ADT都会有一个new和一个free方法，以及在整个标准库的所有模块中必须有多少不同的insert和compare。由于C语言不允许函数重载，每个程序中最多只能有一个。我们通过命名约定来解决这个问题，通常将模块名称作为函数名的前缀。
字符串库基本上就是这样做的，诚然它使用str，并且没有用下划线将前缀与函数名分开，但这是一个合理的初步尝试。此外，这样做可以更容易地找到代码库中使用模块的位置。如果你可以在所有文件中搜索唯一的前缀，你可以比单独搜索每个命名不一致的函数更快地找到调用函数的所有位置。
API设计的另一个风格元素是函数应使用一致的参数顺序、约定或语义。在最简单的例子中，你难道不讨厌使用一个ADT模块，其中一些函数将ADT实例作为第一个参数，而另一些将其作为最后一个参数吗？你将永远需要回头查看API，说这次是哪一个。或者，如果一个函数接受一个指针和该void*指针指向的对象的大小，哪个先出现，指针还是大小？但这不仅仅是让编译器满意和获得正确顺序的问题。它还可以是关于理解函数做什么。例如，如果一个函数接受两个相同类型的参数，是第一个作用于第二个，还是反之亦然？
让我们看看我们的字符串模块。函数名一致吗？嗯，大多数都以str开头。不过，有些名称以mem开头。它们是命名错误，还是暗示它们应该在一个完全不同的模块中？它们没有命名错误，因为它们实际上并不处理字符串。所以也许它们应该是分开的。但另一方面，它们在这里似乎很合适。memcmp和memcpy对数组进行逐字节的比较或复制，就像strcmp和strcpy一样。所以我们不必在这里追求完美，但我们有一个好的开始。
在参数顺序方面，这实际上绝对是一致的：目标字符串参数在整个字符串函数（strcpy和strcat）以及mem函数中都位于源字符串参数之前。当然，有人可能会争论这是否是正确的顺序。当然，第一次看到字符串接口时，可能需要一些时间来适应。等等，源在第二个，目标在第一个？我们不是至少在我的母语中从左到右阅读吗？但它模仿了赋值：我们说x = y，它也模仿了汇编语言的顺序，所以至少是合理的，并且再次，就我们在这里讨论的这个特征而言，它肯定是一致的。
看看simtable，所有函数都以simtable_开头。所以这是一致性的优点。缺点方面，它确实使其有些冗长。随着我们的模块名称变得越来越复杂，我们最终看起来有点像Java，你知道，BufferedInputStreamReader等等这些长长的类名。但为了再次强调一致性，这就是我们在这里关注的重点。这是一个优点。
同样，在参数顺序和语义方面，总是simtable对象作为第一个参数，然后是键，然后是值，目标字符串参数位于源字符串参数之前，这与字符串模块的情况相同。所以至少我们在这里“吃自己的狗粮”：我们为这门课程编写的模块符合我们提出的建议。
回到我们的列表ADT。我们肯定没有使用list前缀，所以这是我们应该改变的地方。但现在，尽管在一个小小的接口中，事情看起来不错：一致的前缀，一致的参数顺序。我认为我们可以继续前进，说我们在一致性方面做得很好。
5. 极简主义 📦
因此，我们特征的第四个是：一个好的模块应该是极简的。
如果一个模块的接口尽可能小，那么它就易于学习、易于使用和易于维护。函数应该只做一件事，并且做好；函数应该有明确不同的工作，不重叠；并且只包含客户端实际需要的函数。
希望这能减少整体函数的数量，但至少要在它们之间有清晰的可区分性。这使得它更易于使用，因为更易于学习，因为你只需要记住更少的函数；更易于使用，因为你不会最终交换一个函数而使用了错误的那个；并且更易于维护，因为它们是可区分的，但它们是原子的：它们做一件事，并且做好。没有这种重叠，你说如果我改变一个函数的功能，它是否会改变其他东西，或者如果我改变一个函数的功能，我是否必须对其他东西进行更改以使其仍然保持一致？
因此，这不仅仅是整体函数数量更少的问题，尽管这可能是其中的一部分，而且因为它实际上也与封装有关。斯科特·迈耶斯是领先的C++专家之一，他提供了一种方便的方式来思考模块的封装程度：如果我们更改底层数据表示，有多少函数需要更改。
这很有道理，我们谈论封装和信息隐藏时说“这意味着你可以更改它”，嗯，这就是衡量标准：如果你更改它，你需要更改多少？在完全没有封装的情况下，我想这看起来像是在接口文件中定义了一个没有任何方法的struct。这个数字是无限的。如果我们更改底层表示，任何客户端的任何函数都可能需要更改，因为任何客户端编写的任何代码最终都可能访问struct的字段。事实上，如果没有方法，我们就必须这样做。
在一个合理封装的模块中，我们可以将其限制为仅属于模块成员的函数：API和静态辅助方法。这个定义支持最小化接口的想法，因为如果我们说通过需要更改的方法更少来衡量封装程度更高，那就意味着模块本身的方法越少，封装程度就越高，而这是我们的主要目标之一。
那么simtable_contains是必要的还是冗余的？花点时间思考一下。如果simtable_get返回NULL，可能是因为具有指定键的绑定不存在，或者绑定确实存在，但值恰好是NULL。simtable_contains允许我们区分这两种情况。前者将返回false，后者返回true，而simtable_get在两种情况下都返回NULL。
因此，再次快速提问，只是为了评估理解并让你思考我们刚刚讨论的内容。暂停视频，看看你是否能解决这个问题。好吧，答案是C。客户端没有理由知道哈希函数。哈希函数仅在模块内部使用。客户端永远不需要看到它。哈希函数可能会更改。此外，实现可能会更改。它可能是一个链表，根本没有哈希表，因此首先就没有哈希函数。所以它应该是内部的，不应该是接口的一部分。C语言有一个可见性机制，在这种情况下是static，它指定函数在文件外部不可见。可以将其视为类似于Java中的private。你将在下周的第二次辅导课中讨论可见性和持续时间，但我只想再次提到，我认为我之前提到过，static是令人困惑的，它可能是语言中最令人困惑的关键字，因为对于函数或全局变量与局部变量，它的含义不同，而这两者的含义又与它在Java中的含义不同。
6. 健壮的错误处理 ⚠️
好了，现在转向不幸的是我最不喜欢谈论的事情之一，只是因为有很多好问题，但在C语言中几乎没有好的答案，那就是错误处理。
毫不奇怪，一个模块应该检测其函数内发生的错误，并且函数应该尽可能处理这些错误，并将错误报告回调用客户端。
但通常并不清楚什么是正确的做法，而且语言提供的处理和报告错误的功能很少。
我们已经看到了如何检测错误。你写过带有assert宏的条件语句。也许你记得as宏。如果你深入研究过作业2的测试客户端，后两者相当有效，但它们实际上只是带有花哨响应（要么崩溃程序，要么打印错误消息）的if语句。此外，我们知道assert可以完全关闭，所以它们可能是无操作，而不是实际的检测检查。然而，尽管如此，也许这至少是检测的合理选项集合的开始。
但当然，在发现错误后，我们需要能够做得比崩溃程序或打印一条消息更好，对吧？确实，仅仅打印一条消息通常是不够的。许多程序自动运行，它们的输出或错误流没有被例行监控或完全丢弃；一些嵌入式设备可能根本没有输出和错误流。所以打印消息在某些情况下很好，但在其他情况下不相关。
因此，在某些情况下，也许我们可以尝试恢复，要么调用替代过程，要么立即重试，或者等待一会儿再重试，但同样，这肯定不适合所有情况。一个更激进的选择，总是可用但很少可取，就是直接说：“是的，如果我看到错误，我总是终止程序。”这是一个相当有限的选择范围，那么我们还能如何将责任推回给调用者，让它做它认为正确的事情，而不是必须在模块本身内决定呢？
将错误通知传播回调用者的自然方式是通过返回值。毕竟，这是函数向调用者发送数据的主要接口。我们已经看到过这样的例子，比如getchar，当它无法读取字符时返回特殊的EOF值；或者scanf，它根据格式说明符返回它能够填充的变量数量，它实际上根本不返回读取的数据。
但这并不理想，因为函数的返回值更常用于其他目的，而不仅仅是传达错误状态。就像我们看到的getchar，它把责任放在了调用者身上，要求他们真正理解返回值的两种不同模式：如果返回期望的结果，或者返回指示某种错误状态的值，然后正确解释它们。
由于返回值在许多情况下已经用于其他目的，另一个自然的想法是让函数设置一个全局错误变量。但我们已经知道全局变量通常存在缺点，例如并发执行。此外，这属于“眼不见，心不烦”：调用者很容易完全忘记检查它，此时一些错误状态持续存在，而客户端认为一切正常，可能会陷入越来越大的麻烦。
介于返回值和全局变量之间的折衷方案是函数的一个输出参数，通过指针在调用者中设置一个值。但尽管这又是一种折衷，实际上并没有解决任何问题。客户端仍然需要检查返回值以外的其他东西，而且还有传递参数的首要负担。
因此，就像我开始本节时所说的，这里确实没有很多好的解决方案。这是Java以比C更复杂的方式处理的事情。Java提供了异常作为表示代码中出现问题的第一类对象。它提供了throw语句来生成此类异常，以及try-catch语句来识别和选择如何处理异常。
但尽管缺乏好的选择，我们至少可以提供建议，以在不利情况下尽力而为，这归结为区分用户错误和程序员错误。
这里的命名有意义，但不完全如此。命名不一定意味着用户的错误，尽管那些通常是用户错误。相反，我们指的是最好由用户处理的错误。同样，程序员错误不一定意味着程序员的错误，尽管程序员的错误往往是程序员错误。我们指的是最好由程序员处理的错误，尽管是间接的，因为程序员在程序执行期间并不交互式存在，但就我们必须修复程序中的错误而言，无论是客户端报告的还是开发过程中发现的。
用户错误是那些归根结底不是程序员过错的事情。它们可能在运行时发生，要么是由于最终用户做错了什么，要么是由于系统限制。这些错误提供了尽可能温和地让最终用户恢复的机会。例如，标准输入上有错误数据、错误的命令行参数、内存或磁盘空间不足等可能预期会发生但仍然是错误的情况。应该给用户修复的机会，无论是通过使用更好的命令行参数重新运行程序，还是在运行时进行纠正，例如刷新标准输入然后提示输入更正。
另一方面，程序员错误是那些根本不应该发生的事情，表明程序存在问题或以前未考虑过的错误状态需要解决。对于这些，我们假设用户无法做出任何合理的选择。因此，我们使用assert来检测和处理它。这是让程序员纠正问题的最直接方式。
例如，表示不变式检查失败，进入函数时一切有效，但离开函数时不再有效。嗯，这是函数的问题。只有程序员可以深入调试它。同样，如果一个模块违反了另一个模块的契约，例如将空指针发送给需要传递非空参数的参数，用户在这里无能为力。这需要更改代码来纠正调用者与被调用者之间行为期望的不匹配。
但这并不总是那么明确。由于用户输入导致的契约违规呢？那些听起来更像是用户错误。同样，如果程序内存不足或磁盘已满，那些似乎是程序员不一定知道正确做法的事情，而且首先就不是程序员的错。因此，我们可以报告给用户来决定做什么。用户可能会选择主动清理一些资源，或者被动等待一会儿再试，或者可能只是中止，但用户有一些合理的选择，而程序员没有。因此，我们再次倾向于将这些视为用户错误，而不是直接中止程序并假设程序员会修复它。
因此，回想一下我们在list_insert中的错误处理。如果内存分配失败，我们使程序崩溃。但我们刚刚说过，我们应该倾向于用户错误，那么我们还能如何处理呢？我们可以使用两种可能的接口更改，也许是一个输出参数，或者由于这个函数不返回任何东西，可以添加一个返回值作为成功状态。
同样，我们还没有尝试处理程序员错误。现在对你来说已经是老生常谈了，我们知道可以而且应该验证传递给函数的输入，所以我们不会过多讨论这一点。
但我们将回到这个list_nth_key规范，我们之前说过这是一个错误参数的情况，即要求获取列表中少于n个项目的第n项。我们之前讨论的是，它只会返回一个任意数字，这并不令人满意。但现在我们知道了更好的方法。我们可以使用一个输出参数来指示错误状态或缺乏错误状态，例如，如果success设置为1，则返回值是第n个键；否则，忽略返回值，因为操作不可能。
或者，在良好模块特征一致性的前提下，我们可以以处理其他问题参数的相同方式处理此错误。因此，我们可以以在接口中增加一个函数为代价，毕竟每个特征都是与其他特征平衡的结果，我们可以有这个额外的接口函数来获取列表的长度。然后，在输入验证一致性前提下，我们可以合理地断言，如果程序员在没有首先验证键N存在的情况下调用了nth_key，我们可以自由地使该断言失败，我们可以使程序崩溃。
7. 清晰的文档与注释 📝
我们在作业1和作业2中深入讨论了函数注释，所以你对接口注释和与调用者的契约的想法非常熟悉，但这无疑是我们清晰或连贯模块特征列表中的一个关键元素，所以让我们再多谈一点。
模块的全部目的是促进比任何一个程序员都能构建或理解的更大的程序。因此，我们需要建立一种能力，让程序某一部分的专家能够与程序另一部分的专家沟通他或她的程序应如何使用。同样重要的是，如果对方使用错误，可以归咎于对方。如果我遵循了契约而函数做了错误的事情，责任必须在那段代码中。另一方面，如果我制定了契约并履行了它，任何客户端都不应该来找我，指责他们的程序有错误。
但再次强调，以免你认为这只是关于自我保护或推卸责任，这实际上是一个重要的后盾。对于最小化我们必须查找错误的搜索空间非常重要，再次强调，所有这一切的根源是关于促进更大程序的开发。这意味着错误更难找到。我们越是能限制搜索空间，就越好。因此，这种沟通正是我们一直要求你做的：参数是什么，函数做什么，它对持久状态的副作用，以及在哪些条件下它可能返回哪些值。
这是一个具体的例子，展示了我们重新设计后的nth_key函数。它列出了契约的组成部分，包括调用者的义务，以及如果调用方式无效，函数行为将终止程序的承诺或公平警告。这是另一个例子，将越界查询视为用户错误而非程序员错误。同样，我们根据函数参数的值以及其他必需的契约组成部分，建立了函数行为的契约。
8. 高内聚与低耦合 🔗
我们列表中的最后两个元素是内聚和耦合，它们相关但不同。内聚是模块的方法和数据之间关系的特征，即模块成员属于一起的程度。
强内聚或高内聚意味着它们更属于一起。这符合我们现有的原则，因为其中之一是最小接口。因此，如果没有高内聚，它们应该放在单独的模块中。
但为什么强内聚是可取的，除了最小接口通常允许进一步抽象这一想法之外？它还与一些其他积极属性相关，例如更易于理解。模块不是无关函数的散乱数组，而是一组自然相关的连贯函数，这将更易于理解，更易于理解这个模块到底是关于什么的。此外，它更易于重用。任何只需要其中一个函数的东西实际上最终可能需要其他函数，而对于内聚性较低的模块来说，这种情况的可能性较小。想象一个模块只是因为一个客户端恰好需要那组无关函数而组合在一起。不能保证未来的某个客户端或所有客户端会需要这些函数组合在一起。因此，重用模块更困难。
但内聚存在于一个谱系中，从微不足道的低内聚（这是一个模块，因为我们把所有不在其他模块中的函数都放了进来，彼此之间没有关系，它们只是碰巧在同一个模块中）到不合理的高内聚（这些是执行此任务对此对象所做的任何事情的完整且不可分割的集合）。大多数模块介于两者之间。例如，这些数据和函数被分组在一起，因为它们都具有共同的属性，比如它们都进行I/O。即使函数本身不相似，并且有永远不会一起使用的子集，它们确实具有这个共同属性。或者，这些函数被分组在一起，因为它们都对相同的数据进行操作。同样，它们不做相同的事情，可能不以相同的方式做，但它们对相同的数据进行操作。
我们在本讲座中一直使用的模块都具有相当强的内聚性。有一些例外，例如字符串库中的非字符串函数。但如前所述，那些确实通过数组逐字节工作，所以它相当符合其他内聚元素。同样，I/O库中的字符串格式化函数实际上并不进行I/O，但它们就像printf和scanf一样，只是针对字符串。从客户端的角度来看，人们可能会争论它们是否应该与其他打印和扫描函数在一起，或者是否应该与字符串函数在一起。它们是字符串函数，它们属于那里，但从程序员的角度来看，它们几乎肯定看起来就像printf和scanf的其他变体。因此，最终它们将内容放入字符串而不是打印出来这一事实是次要的。从这个意义上说，从开发人员的角度来看，与字符串库的相似性可能不如最终用户那样有说服力。
如前所述，还有另一个与内聚密切相关的特征，那就是耦合。这两个指标有着共同的历史，它们都是在结构化设计发展的时代（大约是60年代末到70年代中期）发明的，而内聚是衡量模块内归属感的指标，耦合则处理模块之间的连接。因此，强内聚或高内聚是可取的，而弱耦合或低耦合是可取的。低耦合意味着模块之间的相互依赖性更少，模块之间的信息流更少。
这对于维护是有利的，因为如果没有相互依赖关系，或者模块之间的数据流不多，我们可以在不破坏它们之间连接风险的情况下修改模块。这对于重用也很有用：如果模块没有紧密绑定在一起，它们更有可能能够与其他模块独立重用。
因此，让我们考虑几个例子，偏离我们一直运行的列表、字符串和符号表，因为我知道你已经厌倦了它们。考虑所有好的面向对象类型的东西都归结为交通工具，所以考虑一个飞机模块和一个飞机模拟器。模拟器方法move调用了飞机模块的一大堆函数。模拟器和飞机之间存在紧密耦合，主要体现在这个move函数上。因此，作为一个潜在的设计变更，我们可以考虑move本身是否应该在飞机模块内部。答案可能是肯定的，但让我们以这种方式重新绘制图表，看看现在是什么样子。确实，左右之间立即出现了视觉上的区别：右侧是耦合更弱的设计。编写客户端更容易，我们只需调用move；编写move更容易，因为我们可以使用内部结构，我们不需要调用其他接口函数；它更易于维护、重用，由于所有与内聚相同的原因，现在应用于耦合，所以错误更少。也许这对你来说太模糊了，但我也认为这在本体论上是匹配的。飞机是移动的东西。模拟器不是移动的东西，所以move应该是飞机的函数，而不是模拟器的函数。再次强调，如果这对你来说太模糊，没关系，但我认为它至少在哲学上是一致的。
现在我们有一个客户端，在其执行过程中多次调用模块中的函数。因此在运行时，它们是强耦合的。排序函数应该是集合模块的一部分吗？让我们再看一下，重新绘制图表，看看有什么变化。这里的右侧结构可能更易于维护，更易于重用，错误更少，同样出于所有相同的原因。再次强调，如果你愿意跟我一起进行本体论思考，我认为你可以论证排序是集合存在状态固有的东西，而不是对集合的外部操作固有的东西。但我不确定这是否像模拟器-飞机-移动例子那样明确。
但在这两个例子中，我们都看到了将函数移入模块的趋势。这向我们展示了一个趋势：削弱耦合与最小接口原则相冲突。再次强调，也许并不奇怪，我们几个理想特征可能相互冲突。
第三个例子根本不考虑函数调用，而是考虑代码更新。如果在维护期间或通过维护阶段，更改一个模块通常意味着另一个也必须更改，那么两个模块在维护时是强耦合的。这是一种强耦合，可能表明X和Y可能属于同一个模块，无论是在客户端还是在模块中都无关紧要。或者，在这种情况下，F3的接口在其他方面存在缺陷，以体现这种非常强的互连性，这将是一个缺陷，因为毕竟封装说更改内部表示不应该要求更改客户端，或者更糟的是，更改客户端真的不应该要求更改底层表示。
因此，这里的右侧客户端再次我们认为更易于维护或重用，并且所有这些例子中，模块之间移动到更弱的耦合最终会增加至少一个模块内的内聚，所以这两个特征再次相关。我们将每个例子都展示为一种神奇的一步修复，但实际上设计的这个元素是一个迭代过程，是随着你对代码和预期客户端集的体验（要么你变得更熟悉它，要么它确实在演变）而不断重构的过程。
因此，频繁的客户端操作可以被拉入模块。从未使用过的模块操作可以被踢出模块，也许踢到偶尔使用它们的客户端，或者踢到以太中，因为它们从未被使用过。同时更改的东西被放在客户端-模块屏障的同一侧，因此要么被拉入，要么被踢出。彼此相关但与客户端或模块的其余部分无关的东西分离出来形成一个新的独立模块。
最后一点是，随着软件工程超越结构化设计的初期，面向对象设计范式出现，像这样的指标也在不断发展，所以你可能有兴趣了解内聚性，它有点像是封装内聚和耦合的下一维度。
总结与后续安排 🎯
本节课中，我们一起学习了模块化设计与接口设计的核心原则。我们探讨了良好模块的八个关键特征：封装与信息隐藏、清晰的规范与契约、一致的内存与资源管理、一致性、极简主义、健壮的错误处理、清晰的文档与注释以及高内聚与低耦合。我们通过列表ADT等具体示例，理解了如何在C语言中应用这些原则来构建更健壮、更易维护的软件。
这几乎结束了我们的软件工程基础主题。我们将在第21讲最后一次回来讨论性能分析和优化。
下周的第一讲是对一些低级系统主题的快速调查，这些主题过去在本课程的后半部分广泛涉及，所以你可以将其视为一些有趣的主题，现在你凭借新获得的C语言知识以及即将学习的汇编语言知识，可以接触到这些主题；或者，你可以将其视为你在一些系统系课程中将看到的低级系统内容类型的预览。
下周的第二讲是作业4的概念和规范介绍。
但现在，祝你在作业3上工作顺利。下周的辅导课将继续涵盖与该作业相关的材料，秋假后我们都将恢复运行。因此，办公时间将重新开放，以帮助理解作业的概念或进行调试。所以请不要犹豫，利用所有可用的资源。不要感到害羞或觉得你过度依赖它们。它们的存在是有原因的。
更进一步，如果出现任何现有资源不足的情况，请尽量不要感到不舒服而不敢联系，我们确实希望尽我们所能确保每个人都能保持正轨，在世界仍然陷入困境的不利情况下坚持下去。所以再次强调，保持参与，保持联系，祝你好运。
016：进程抽象介绍 🖥️
在本节课中，我们将快速了解进程抽象。通过本次学习，你将更好地理解程序运行时发生了什么。同时，这也可以作为对系统课程（如3.16或3.18）中重要主题和材料风格的一次预览。
在本系列讲座中，我们将从进程抽象开始，许多其他底层系统概念都围绕它展开。然后，我们将不仅探讨进程本身，还会学习如何编写管理进程的C程序，以及如何通过信号进行有限形式的进程间通信来控制其他进程。
程序与进程 📁
上一节我们介绍了课程的整体目标，本节中我们来看看程序和进程这两个核心概念的具体定义。
你的程序是我们反复讨论的构建过程的最终产物。当链接器最终构建出可执行文件时，它就定义了你的程序。如果你修改了某些内容并重新构建，这本质上就是一个不同的程序，即使你给它相同的名字。它更像是一个全新的程序，而非旧程序的更新版本。
一个进程，则是该程序实际执行的一个实例。更专业的说法是，进程是你的程序在时间上的积分，是该特定程序执行过程中所有状态的总和。这包括寄存器的状态、内存的状态、执行条件分支时的控制流等。
当进程运行时，它与机器上的许多其他进程共享计算机资源。例如，当你运行你的进程时，你的代码编辑器可能也在运行。无论如何，至少还有一个运行着你的shell的进程在运行。因为全班170名同学都不可避免地会在作业截止日期前的最后48小时工作，所以不仅你的进程在运行，你所有同学的进程也在运行。
进程标识符（PID） 🔢
每个同时运行的进程都有自己的标识符，即进程ID，通常缩写为PID。例如，上图中的10882或92684。
当一个进程开始运行时，操作系统会为其分配一个PID。该PID在所有同时运行的进程中必须是唯一的，但如果某个PID不再使用，它可以被重用。通常，PID会按顺序分配，直到达到最大进程ID后溢出回较小的数字。在我们的系统上，这个最大值是98304（即2^15）。最开始的几百个PID通常为操作系统内核保留，实际上，内核会使用前几千个PID，因为操作系统会在任何其他程序有机会执行之前启动许多长期运行的进程。
当我们开始讨论运行一个会调用多个进程的程序时，这个PID将成为一个重要的属性。
进程抽象的强大之处 ✨
进程抽象非常强大。尽管可能有成千上万个进程在运行，但每个进程都可以（如果它愿意）在一种假象下运行，即它是机器上唯一的进程，并且拥有所有可能的资源，甚至比实际存在的资源还要多。
让我们简要看看在底层实现这种假象的两种主要方式。
私有地址空间的假象 🗺️
首先，是它们拥有私有地址空间的假象。一个进程感觉它拥有机器上的所有内存，实际上，它感觉拥有的内存甚至比运行它的机器或任何机器可能拥有的内存还要多。
其次，进程可以认为它们始终独占处理器。这当然是错误的，但它提供了一个很好的抽象，这种抽象一直渗透到栈的底层，甚至到机器语言代码层面。在课程中，我们即将向下探索语言层级，从C语言开始，接下来会看到汇编甚至机器语言。我们会感觉自己在深入到非常底层的世界，然而，所有这些的基础仍然是我们在一个虚拟世界中工作。这是系统呈现的一种假象，旨在使我们的编程环境和我们的推理更加容易。
内存管理的假象 💾
接下来，我们快速概述第一种假象，但这只是一个非常粗略的介绍。在应用程序层面编程时，你将内存视为一个巨大的字节数组，并且认为你是唯一使用它的人，用于你的栈、堆和所有其他内存段。
但现实中，机器拥有的内存可能更少。实际上，它肯定比我们想象的要少。我们把这个数组想象成从0到0xFFFFFFFFFFFFFFFF（16个F）的可寻址字节。但我录制此视频的笔记本电脑有16GB内存，这已经很多了，但2^64可寻址字节是它的数十亿倍以上。
此外，你的进程正在使用的内存中，只有一部分会实际驻留在物理内存中，即物理处理器的内存以及芯片和硬件上的物理RAM中。实际上，你的地址空间中有很大一部分根本没有被使用。如果你有一个叫做“Hello World”的小程序，它做不了多少事情，你真的会使用2^64字节吗？当然不会。
即使是你正在使用的内存，也可能不在物理内存中。例如，你可能还不需要它，所以程序还没有必要把它放入物理内存；或者它最近没有被使用过。实际上，有许多进程同时在运行，它们都在竞争这些资源。
因此，在应用程序层面编程时，硬件和操作系统完全将你与这些细节隔离开来。你在一种假象下操作，即你的地址0到0xFFFFFFFFFFFFFFFF是真实的，但它们不是。它们是虚拟的，并且在操作系统的帮助下，通过硬件几乎无缝地转换为物理内存位置。此外，该位置甚至可能根本不在物理内存中，它可能被存储在磁盘的某个地方。
再者，我们将内存视为一个巨大的数组。实际上，它是一个由不同内存组成的层次结构。我们将在下周详细讨论这一点，但简单来说，存在一个硬件层次结构，范围从速度极快但容量极小，到容量几乎无限但速度极慢。系统和内存管理中的一个核心主题就是如何利用层次结构中的所有不同存储级别，以同时提供大容量和高速的假象。
私有控制流的假象 ⏱️
好的，我说过关于内存的部分只是一个快速的旁白，到此为止。进程抽象提供的第二个假象是，每个进程都有其私有的控制流。
如今许多计算机都有多个CPU，例如每台ARM实验室计算机有96个CPU，但这仍然不足以让每个进程始终拥有处理器。为了简化问题，我们在单独和交互地推理进程时，通常假设只有一个CPU，许多结论仍然可以推广到多个CPU的情况。
因此，对于那个单一处理器，我们感知到我们的进程一直在运行，但这当然不可能是真的。实际上，它必须与机器上运行的所有其他进程在极短的时间片内进行时间共享。所以，进程X的一些指令会运行，然后是进程Y的一些指令。有时发生这种情况是因为一个进程暂时不需要CPU，例如，它正在等待操作系统返回，因为它查找了被发送到磁盘的内存，或者它建立了一个网络连接，正在等待实际的物理连接从世界另一端发送字节。其他时候，是因为操作系统主动介入并说：“嘿，友好点，分享是关爱，你应该与其他进程分享。”
然而，特别是对于交互式进程，每个进程必须定期获得其应得的CPU份额，以维持这种私有控制流的假象。当你正在某个进程中操作，突然发现：“等等，我应该能在这里输入，但它不接受我的输入”，或者“它应该立即给我一个答案。这是一个非常简单的函数。为什么它什么都没打印？”这时，这种假象的维持就变得非常明显。
因此，我们必须让时间片相对较快，以便我们仍然能感知到这一点。我们经常在这里谈论并发执行，但英语单词“concurrent”在这里并不完全合适。从技术上讲，如果只有一个CPU，X和Y不能同时在CPU上运行。在系统中，如果X在Y的生命周期内开始，或者Y在X的生命周期内开始，我们就说X和Y被设置为并发运行。这与我们通常认为的“并发”并不完全相同。
进程状态与转换 🔄
在任意给定时间，一个进程可能处于以下几种状态之一：
-
运行中：CPU正在主动执行该进程的指令。
-
就绪：进程有可以运行的指令，但CPU尚未选择让它运行，它正在与其他进程共享。
-
阻塞：进程正在等待其控制范围之外的某些事情发生。例如，操作系统可能正在为它做某事，或者像I/O这样的操作。
这些状态之间的转换实际上是本课程中确定性有限自动机出现的又一个实例。一个进程进入就绪状态后，它唯一能转换到的状态是运行状态，因为它不能在运行状态之外请求阻塞操作来实际发出该请求。操作系统最终会决定轮到该进程运行，并将其转换到运行状态。它会运行一段时间，然后要么执行一个再次阻塞的操作（如I/O或需要操作系统干预的操作）并转换到阻塞状态，要么操作系统介入并说：“你已经得到了公平的份额，让出来吧，其他进程需要运行”，于是它又回到就绪状态。在阻塞状态，最终无论它等待的是什么——操作系统、输入/输出等——都会完成，因此现在只要下次轮到它，它就能运行，于是它转换到就绪状态。
在简要描述了进程状态的DFA概念并看过状态图后，我们可以看一个更详细的、加入了时间元素的先前图表版本。如果进程之间的切换在足够小的时间尺度上进行，每个进程都可以维持独占机器的假象，但在进程数量足够多时，这是一场微妙的舞蹈。
上下文切换的代价 ⚖️
此外，上下文切换并非没有代价。它涉及保存进程X的内容。这个内容或上下文就是我们通常所说的“上下文切换”中的上下文。但它实际上是内存的内容、处理器的内容，以及该进程在被抢占时发生的一切。它必须被保存起来。然后，进程Y在被抢占时的上下文必须被加载回来。
因此，如果切换过于频繁，这听起来对维持感知上的隔离和完全控制的假象是件好事，但切换本身会产生大量开销。实际上，上下文切换每秒发生50到数千次不等，具体取决于系统规格和负载，这可能相当频繁。
这是一个经典的例子，说明了系统领域一切问题的答案通常是：“嗯，这要看情况”，或者说这是一种权衡。如果我们给进程分配大的时间片，我们可能会让其他进程因得不到处理器而“饥饿”，从而打破我们私有控制流的假象。但如果我们使用太小时的时间片，我们会在保存和恢复上下文上浪费大量时间，而这些时间本可以用来做有用的工作。在这种情况下，我们所有的程序都会因此运行得更慢。
总结 📝
本节课中我们一起学习了进程抽象的核心概念。我们明确了程序（静态的可执行代码）与进程（动态的执行实例）的区别，并认识了进程的唯一标识符PID。我们深入探讨了操作系统为每个进程营造的两个关键假象：私有地址空间（感觉拥有全部内存）和私有控制流（感觉独占CPU）。为了实现这些假象，进程在运行、就绪和阻塞状态间转换，并通过上下文切换在CPU上分时运行。最后，我们了解到系统设计需要在给予进程足够长的运行时间以维持假象和频繁切换以避免其他进程“饥饿” 之间进行权衡，因为上下文切换本身存在开销。
下一节，我们将讨论进程管理。
017：流程管理 🚀
在本节课中，我们将深入学习进程管理。我们将打破一个贯穿整个学期的假设，即一个程序只对应一个进程。实际上，程序可以创建并与其自身的额外进程进行交互。这是构建像Shell这样的程序的基础，Shell能够根据用户请求执行其他程序。
系统级函数与进程管理
如果把Linux操作系统看作一个大型模块，那么系统级函数就是进入该模块的接口。这些特殊函数会进入操作系统内核，并请求操作系统代表用户进程执行工作。用户进程自身无法完成这些工作，可能是因为工作需要特殊权限、访问权，或者需要与某些硬件（如I/O）交互。
就像动态内存管理有四个核心函数（malloc、calloc、realloc、free）一样，进程管理也有四个核心函数：fork、exec家族、wait和exit。
创建子进程：fork函数
Shell是一个典型的例子，当用户请求执行一个程序时，它必须创建新进程。另一个例子是Web服务器，它在收到请求时，会将该请求的处理委托给一个新进程，以便服务器可以继续监听其他请求。
那么如何实现呢？我们使用“父进程”和“子进程”这种通用的层级术语来描述。
创建新进程的机制可能并不直观：父进程创建一个新进程，这个新进程实际上是父进程自身的精确副本。然后，子进程会发出一个命令，表示它不再想成为父进程，而是希望变成另一个程序。这就像是进程家族中的“青春期叛逆”。
fork的工作原理
系统级函数fork用于创建一个新的、重复的进程。fork会创建一个父进程的精确副本，包括处理器状态、内存状态等，但有一个例外（稍后讨论）。这个副本是在父进程调用fork的那一刻创建的。
这意味着fork会返回两次：一次返回到调用它的父进程中，另一次返回到这个新创建的子进程中，子进程从fork返回处开始执行。
区分父进程与子进程
父进程和子进程之间唯一的区别在于fork的返回值。fork被调用一次但返回两次，因此可以有两个返回值：
-
子进程得到的返回值是 0。
-
父进程得到的返回值是 子进程的PID。
这个关键区别允许我们在程序中通过条件判断来区分当前代码是在父进程还是子进程中执行。
多进程并发执行
当有多个进程运行时，处理器会在它们之间频繁地进行上下文切换，给每个进程一种拥有自己私有控制流的错觉。在现代多核机器上，这些进程实际上可以并行运行。
现在，我们有多个进程并发地运行我们的程序。它们相互竞争资源，最显著的就是处理器的运行状态。让我们通过一个初始例子来观察。
示例分析：不确定的执行顺序
考虑以下程序：
int main() {
printf("1\n");
fork();
printf("2\n");
return 0;
}
这个程序会向标准输出打印什么？我们来追踪一下。
程序开始时只有一个进程（父进程）。它打印“1”，然后调用fork。现在有两个进程（父进程和子进程），它们都位于程序中fork调用之后的位置。由于上下文切换是不确定的，我们无法预测哪个进程会先执行printf("2\n")。
-
情况A：如果子进程先运行，则输出顺序为：
1（父进程）、2（子进程）、2（父进程）。 -
情况B：如果父进程先运行，则输出顺序为：
1（父进程）、2（父进程）、2（子进程）。
两种情况的输出都是“1”后面跟着两个“2”，但两个“2”的顺序可能不同。在这个简单例子中，顺序无关紧要，因为输出内容相同。
然而，当代码根据fork的返回值进行不同操作时，执行顺序就变得至关重要了。在一般情况下，两个进程指令的所有可能交错顺序都是可能的执行路径，这使得预测程序行为变得复杂。
示例分析：数据独立性与写时复制
看另一个例子：
int main() {
int x = 1;
pid_t pid = fork();
if (pid == 0) {
x--;
printf("child: %d\n", x);
exit(0);
} else {
x++;
printf("parent: %d\n", x);
exit(0);
}
}
这个程序会打印什么？答案是：可能是“child: 0”然后“parent: 2”，也可能是“parent: 2”然后“child: 0”。顺序不确定。
这里引入了一个重要概念：写时复制。在fork发生时，父进程和子进程拥有完全相同的数据。只有当其中一个进程试图修改数据（如这里的x）时，操作系统才会为它们创建独立的数据副本。因此，子进程中对x的递减操作不会影响父进程中的x，反之亦然。从fork的那一刻起，它们就是独立的进程。
关于exit的说明：在子进程分支中，我们使用exit(0)而不是return 0。这是正确的，并且通常是更好的做法。如果使用return，且代码不在main函数中而是在深层调用栈里，子进程可能会意外地继续执行父进程的代码，导致两个程序副本同时运行，引发严重错误。使用exit可以确保进程立即终止。
控制执行顺序：wait函数
在上一个例子中，哪个进程先运行会影响输出顺序。如果我们受制于操作系统和CPU的调度，如何编写代码来满足程序对顺序的要求呢？
wait系统级函数可以挂起（暂停）一个进程的运行，直到它的一个子进程终止。一旦有子进程终止，父进程就会被唤醒并继续执行。这允许我们强制规定执行顺序。
使用wait的示例
考虑以下程序：
int main() {
pid_t pid = fork();
if (pid == 0) {
printf("child\n");
exit(0);
}
wait(NULL);
printf("parent\n");
return 0;
}
无论操作系统选择让父进程还是子进程先运行，wait调用都保证了输出顺序永远是：
child
parent
-
如果父进程先运行，它会立即调用
wait并进入等待状态，让子进程得以运行和打印。子进程退出后，父进程才被唤醒并打印。 -
如果子进程先运行，它会打印并退出。当父进程随后运行时，
wait会立即返回（因为已有一个终止的子进程未被等待），然后父进程打印。
通过wait，我们成功地控制了进程的执行顺序。
孤儿进程与僵尸进程
即使不需要控制顺序，让父进程等待其所有子进程也被认为是良好的实践。如果父进程不等待，子进程可能会进入两种状态：孤儿进程或僵尸进程。
-
孤儿进程：一个仍在运行的进程，其父进程已经终止。父进程显然没有等待它。
-
僵尸进程：一个已经终止但尚未被父进程
wait（或“收割”）的进程。
僵尸进程会一直存在，等待父进程来“收割”它们，这会占用系统资源。为了避免孤儿进程变成永久的僵尸进程，操作系统会安排一个“收养”进程（传统上是init进程，PID为1；现代Linux中可以是任何声明为“子收割者”的进程）来最终等待它们。
因此，良好的编程习惯是：父进程应该适时调用wait来回收其终止的子进程，避免产生僵尸进程。
改变程序身份：exec家族函数
如前所述，fork创建的子进程是父进程的副本。子进程可以通过调用exec家族的系统调用来“改变自己”，用另一个完全不同的程序替换当前正在运行的程序。这就像是进程的“快速换装”。
exec函数用新程序替换当前进程的代码段、数据段等。如果exec调用成功，它永远不会返回——进程从此开始执行新程序的代码。如果失败（例如指定的命令不存在），则会返回-1，程序应处理这种错误情况（通常调用exit）。
exec示例
int main() {
char *cmd = "cat";
char *argv[] = {"cat", "readme.txt", NULL};
execvp(cmd, argv);
// 如果execvp成功，下面的代码永远不会执行
perror("execvp failed");
exit(EXIT_FAILURE);
}
这个程序会尝试将自身转变为cat程序，并执行cat readme.txt命令。如果cat程序存在且可执行，原程序的后续代码将不会运行。
经典组合：fork + exec + wait
fork（创建子进程）、子进程中exec（执行新程序）、父进程中wait（等待子进程结束）这三者的组合极为常见，以至于有一个快捷函数system将它们封装起来。
实现一个简单Shell的核心逻辑
现在我们可以理解Shell（如bash）的内部工作原理了。Shell本质上就是一个大循环：
-
读取并解析用户输入的命令。
-
fork创建一个子进程。 -
在子进程中：调用
exec执行用户指定的命令。 -
在父进程中：调用
wait等待子进程结束。 -
清理（如果需要），然后回到第1步，开始新的循环。
以下是一个简化的伪代码/C代码混合示例：
while (1) {
// 1. 读取并解析命令
char *cmd = read_command();
char **argv = parse_arguments(cmd);
// 2. 创建子进程
pid_t pid = fork();
if (pid == -1) {
// 处理fork错误
perror("fork");
continue;
}
if (pid == 0) {
// 3. 在子进程中：执行命令
execvp(argv[0], argv);
// 如果execvp失败
perror("execvp");
exit(EXIT_FAILURE);
} else {
// 4. 在父进程中：等待子进程
wait(NULL);
// 5. （可选）清理，然后循环继续
}
}
关于后台进程：当我们在命令后加上&（如ls &）时，Shell不会等待该命令完成就立即返回提示符。这可以通过在fork后，父进程不立即调用wait来实现。父进程需要记录这些后台作业，并可能通过非阻塞的wait变体（如waitpid with WNOHANG）或通过处理SIGCHLD信号来定期检查并回收已终止的后台子进程。
总结 🎯
本节课我们一起深入学习了进程管理。我们首先打破了“一个程序一个进程”的假设，引入了父进程与子进程的概念。我们详细探讨了四个核心系统调用：
-
fork：创建当前进程的副本，是区分父子进程的基础。 -
exec：用新程序替换当前进程，实现“变身”。 -
wait：父进程等待子进程终止，用于控制执行顺序和回收资源。 -
exit：终止进程。
我们了解了写时复制机制如何保证fork后进程内存的独立性，以及不恰当管理子进程可能导致的孤儿进程和僵尸进程问题。最后，我们看到了如何将这些调用组合起来，实现像Shell这样的复杂程序的核心循环逻辑。掌握这些知识是理解操作系统多任务处理和构建高级应用程序的基础。
018：信号 📡
在本节课中，我们将学习进程间通信的一种新机制——信号。信号是操作系统向进程发送的一种异步通知，用于告知进程发生了某些需要处理的事件，例如用户按下中断键（Ctrl+C）或程序出现非法内存访问。
信号是什么？🤔
上一节我们介绍了进程的基本概念，本节中我们来看看信号。信号是操作系统注入到进程正常执行流程中的一种通知。当发生异常事件（如键盘中断或内存访问错误）时，操作系统会获得CPU控制权，并向目标进程发送一个信号。这个信号本质上是在进程的状态位中设置一个标志位。
例如，当你运行一个无限循环的程序并按下 Ctrl+C 时，键盘控制器会向CPU发起一个中断。操作系统注意到这个中断，读取键盘数据，并将其解释为一个请求：中断当前正在运行的进程。操作系统随后向该进程发送信号2，即 SIGINT（中断信号）。该信号的默认处理行为是终止进程。
以下是几个常见的用户触发信号及其默认行为：
-
SIGINT(信号 2)：由Ctrl+C触发。默认行为是终止进程。 -
SIGTSTP(信号 20)：由Ctrl+Z触发。默认行为是停止（挂起）进程。 -
SIGQUIT(信号 3)：由Ctrl+\触发。默认行为是终止进程。
另一个常见的信号例子是 SIGSEGV（信号11，段错误信号）。当我们执行一条导致非法内存访问的指令时，会触发一个中断，操作系统获得控制权并向进程发送 SIGSEGV 信号，其默认行为同样是终止进程。
信号的生命周期 🔄
现在我们已经了解了信号的来源，让我们深入看看信号从发送到处理的完整过程。
-
异常发生：进程P正在执行时，发生了一个打破程序标准控制流的异常事件。这可能是键盘中断、内存访问错误，或者其他进程请求操作系统发送信号。
-
OS介入：操作系统获得CPU控制权来处理这个异常。
-
发送信号：操作系统通过设置进程P状态位中的一个标志位，向其发送信号。
-
接收信号：稍后（通常是立即），进程P恢复执行。操作系统通知P有信号待处理，并清除相应的状态位。
-
处理信号：进程P触发其信号处理器。这可能是默认处理器，也可能是程序自定义的处理器。
-
恢复执行：如果信号处理没有导致进程终止（例如，自定义处理器选择忽略信号），那么进程将在信号处理器完成后，从被中断的地方继续正常执行。
你可以将信号处理（在进程不终止的情况下）视为正常控制流中的一个临时分支。
如何发送信号？📤
除了键盘快捷键，还有其他方式可以向进程发送信号。
一种方式是通过名为 kill 的命令。尽管名字叫“杀死”，但它可以发送任何信号，而不仅仅是终止信号。你需要指定一个信号和接收该信号的进程ID（PID）。
命令格式：
kill -<信号编号> <进程ID>
例如，kill -9 1234 会向PID为1234的进程发送无法被捕获或忽略的 SIGKILL 信号，强制终止它。
kill 命令通过向操作系统发起一个陷阱来工作，因为发送信号需要提升的权限。
一个实用的场景是管理后台作业。假设你启动了一个长时间运行的前台命令，想把它放到后台。你可以：
-
按
Ctrl+Z发送SIGTSTP信号，挂起该进程。 -
输入
bg命令，将该作业放入后台。 -
系统会自动向该进程发送
SIGCONT信号，使其在后台继续运行。
这样避免了杀死进程并从头开始的浪费。
要查看系统上所有预定义的信号，可以使用命令：
kill -l
此外，程序自身也可以通过 raise() 函数向自己发送信号。虽然这听起来有些奇怪，但它可以用于程序内部的逻辑跟踪或清理工作。更常见的是，程序使用 kill() 函数（注意：这是一个C库函数，不是shell命令）向其他进程发送信号，作为一种简单的进程间通信方式，例如实现“心跳”机制来确认另一个进程是否存活。
信号处理器：自定义反应 🛠️
我们已经多次提到信号的默认处理器，现在让我们看看如何自定义它。如果说 raise() 或信号发送类似于Java中的 throw，那么信号处理器就类似于 catch 块。
每个信号都有一个默认反应（终止、停止、继续或忽略）。程序也可以安装一个自定义处理器，即一个在接收到特定信号时运行的函数，以替代默认行为。这可以用于避免在特定条件下终止，或者在进程必须终止前执行清理工作（如关闭网络连接、保存文件）。
安装信号处理器的函数是 signal()。它接收两个参数：信号编号和作为处理器的函数指针。成功时返回旧的处理函数指针，方便后续恢复。
函数原型：
void (*signal(int sig, void (*handler)(int)))(int);
为了简化，通常使用 typedef 定义的类型 sighandler_t。
有两个特殊的预定义处理器值：
-
SIG_DFL：恢复信号的默认处理器。 -
SIG_IGN：忽略该信号。
需要注意的是，有些信号不能被自定义处理器捕获或忽略，最著名的两个是：
-
SIGKILL(信号 9)：强制终止。这就是kill -9如此有效的原因。 -
SIGSTOP(信号 19)：强制停止（挂起）。
实践示例：捕获 Ctrl+C 🚫
理论介绍完毕，让我们通过代码来实践。以下是一个简单的程序，它安装了一个自定义的 SIGINT 处理器，使得 Ctrl+C 无法终止程序，而是打印一条消息。
#define _GNU_SOURCE
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
void handle_sigint(int sig) {
printf("\nCaught signal %d (SIGINT). I won't terminate!\n", sig);
}
<https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-cos217-c-sys-prog/img/1205394fb9aa43f4ce919e147e1d0445_17.png>
int main() {
// 安装 SIGINT 的信号处理器
signal(SIGINT, handle_sigint);
printf("Try pressing Ctrl+C...\n");
while(1) {
pause(); // 等待任何信号
}
return 0;
}
在这个程序中，handle_sigint 函数是自定义处理器。安装后，按下 Ctrl+C 将触发这个函数，打印消息，而进程会继续运行（因为处理器没有调用 exit）。要终止它，你需要使用其他信号，例如在另一个终端使用 kill 命令。
实践示例：资源清理 🧹
让我们看一个更实际的例子。假设一个程序生成大量数据并写入一个临时日志文件，程序结束时再删除它。如果用户在程序运行中按下 Ctrl+C，默认情况下进程会立即终止，导致 remove() 函数没有被调用，临时文件残留。
为了解决这个问题，我们可以安装一个 SIGINT 处理器来执行清理工作。
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>
FILE *logfile;
void cleanup(int sig) {
if (logfile) {
fclose(logfile);
logfile = NULL;
}
// 可以在这里删除临时文件
printf("Cleaned up before exit.\n");
exit(sig); // 退出，使用信号编号作为退出状态
}
<https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-cos217-c-sys-prog/img/1205394fb9aa43f4ce919e147e1d0445_19.png>
int main() {
// 安装信号处理器
signal(SIGINT, cleanup);
logfile = fopen("temp.log", "w");
if (!logfile) {
perror("fopen");
return 1;
}
// 模拟写入大量数据
for (int i = 0; i < 1000000; ++i) {
fprintf(logfile, "Data line %d\n", i);
// 长时间操作中，用户可能按下 Ctrl+C
}
// 正常结束时的清理
cleanup(0);
return 0; // 这行实际上不会执行，因为 cleanup 调用了 exit
}
这样，无论程序是正常结束还是被 Ctrl+C 中断，cleanup 函数都会被调用，确保文件被正确关闭。注意，SIGKILL (kill -9) 仍然无法被捕获，因此是强制终止的最终手段。
闹钟信号：实现超时功能 ⏰
最后一个系统级函数是 alarm()。它请求操作系统开始一个倒计时，倒计时结束后向调用进程发送 SIGALRM（信号14）。这非常有用，可以用来实现超时功能。
SIGALRM 的默认行为也是终止进程，因此通常需要为其安装自定义处理器。
示例1：周期性提醒
#define _GNU_SOURCE
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
void handle_alarm(int sig) {
printf("Timer fired! (%d)\n", sig);
alarm(2); // 重新设置一个2秒后的闹钟
}
int main() {
signal(SIGALRM, handle_alarm);
alarm(2); // 设置第一个2秒闹钟
while(1) {
pause(); // 主程序无限等待
}
return 0;
}
这个程序会每2秒打印一次“Timer fired!”，形成一个简单的定时器。
示例2：输入超时
#define _GNU_SOURCE
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
void handle_alarm(int sig) {
printf("\nSorry, you took too long. Exiting.\n");
exit(1);
}
int main() {
char name[100];
signal(SIGALRM, handle_alarm);
printf("Enter your name (you have 5 seconds): ");
fflush(stdout);
alarm(5); // 设置5秒超时
if (scanf("%99s", name) == 1) {
alarm(0); // 取消闹钟
printf("Hello, %s!\n", name);
} else {
// scanf 失败或超时发生
printf("Failed to get input.\n");
}
return 0;
}
这个程序给用户5秒时间输入名字。如果用户超时，SIGALRM 处理器会触发并退出程序。如果用户在5秒内完成输入，则用 alarm(0) 取消闹钟。这解决了像 scanf 这样的阻塞调用可能无限期等待用户输入的问题。
总结 📝
本节课中我们一起深入学习了信号这一重要的进程间通信和异常处理机制。
我们首先了解了信号是什么：它是操作系统异步通知进程发生特定事件的方式。我们探讨了信号的完整生命周期，从触发、发送到接收和处理。
接着，我们学习了多种发送信号的方法，包括键盘快捷键、kill 命令以及C语言中的 raise() 和 kill() 函数。
然后，我们掌握了信号处理的核心——如何通过 signal() 函数为信号安装自定义处理器，以改变其默认行为，并了解了 SIG_DFL 和 SIG_IGN 这两个特殊值。我们也知道了 SIGKILL 和 SIGSTOP 是无法被捕获或忽略的。
最后，我们通过几个实践示例巩固了知识：如何捕获 Ctrl+C 来防止程序被意外中断，如何在程序退出（包括被信号中断时）进行资源清理，以及如何使用 alarm() 和 SIGALRM 来实现超时功能，这为处理可能阻塞的操作提供了强大工具。
信号是理解操作系统如何与进程交互、如何构建健壮应用程序的关键概念。希望本讲能帮助你更好地理解并运用这一机制。
019：作业4概述与数据结构详解 🚀
在本节课中，我们将详细介绍第四次作业（Assignment 4）的目标、结构以及核心数据结构。本次作业是课程中第一个合作项目，旨在通过实践提升代码阅读、数据结构应用、调试、测试以及模块化设计的能力。
作业目标与结构 🎯
上一节我们回顾了课程进度，本节中我们来看看第四次作业的具体目标。本次作业包含五个主要目标：
-
阅读大量非自写代码：在实际工作中，工程师经常需要理解和维护庞大的现有代码库。本次作业将模拟这一场景。
-
深入理解抽象对象范式：与作业3中的抽象数据类型不同，本次作业将接触类似Java单例模式的抽象对象模型。其状态由文件作用域的静态变量维护，方法无需接收实例参数。
-
提升GDB调试技能：作业的第一部分不涉及编码，而是使用GDB分析有缺陷的代码实现，定位其中的错误。
-
编写内部测试套件：您需要编写一个检查器程序，在每次API调用前后验证数据结构的内部状态是否保持正确。
-
实践模块化与程序设计：作业仅规定接口和客户端行为，具体实现方案（如模块划分、底层数据结构）完全由您自主设计，这是发挥创造力的好机会。
作业三部曲 📚
作业内容围绕模拟文件系统展开，分为三个循序渐进的部分。
第一部分：二叉目录树 (BDT)
在第一部分，我们将实现一个简化的文件系统模型——二叉目录树。它有两个关键约束：
-
二叉：每个目录最多只能有两个子节点。
-
目录：树中只包含目录，没有文件。
以下是BDT模块的核心接口函数：
BDT_init(); // 初始化数据结构
BDT_destroy(); // 销毁数据结构
BDT_insert_path(path); // 插入路径（类似 mkdir -p）
BDT_contains_path(path); // 检查路径是否存在
BDT_remove_path(path); // 移除路径（类似 rm -r）
BDT_to_string(); // 获取树的字符串表示
其数据结构包含三个字段：
-
bool initialized： 标记是否已初始化。 -
Node* root： 指向树根节点的指针。 -
size_t count： 树中节点的总数。
每个节点（Node）包含四个字段：
-
char* path： 从根目录到该节点的完整路径字符串。 -
Node* parent： 指向父节点的指针。 -
Node* child1： 指向第一个子节点的指针。 -
Node* child2： 指向第二个子节点的指针。
操作示例：插入路径 “/A/B/C”。
-
检查根节点。若为空，则创建路径为
“A”的根节点。 -
解析剩余路径
“B”。检查根节点是否有匹配的子节点。若child1为空，则在此创建路径为“A/B”的新节点，并建立链接。 -
解析剩余路径
“C”。重复步骤2，在“A/B”节点下创建路径为“A/B/C”的节点。
重要不变量：如果一个节点只有一个子节点，那么它必须是 child1。在删除操作后，可能需要将 child2 的子节点移动到 child1 以维持此不变量。
在本部分，您无需编写实现代码，主要任务是使用GDB分析我们提供的、包含错误的实现，并找出缺陷所在。
第二部分：目录树 (DT)
在第二部分，我们移除“二叉”限制，实现一个支持任意数量子节点的通用目录树。
其接口与BDT类似，但节点结构变得更复杂。节点（Node ADT）包含：
-
char* path： 路径字符串。 -
Node* parent： 父节点指针。 -
DArray* children： 指向一个动态数组对象的指针，该数组存储其所有子节点。
动态数组（DArray ADT）内部通常包含：
-
size_t length： 当前存储的元素数量。 -
size_t capacity： 数组的当前容量。 -
void** array： 指向指针数组的指针，用于实际存储元素（此处为子节点指针）。
操作示例：插入路径 “/A/B”。
-
从根节点开始。若根节点不存在，则创建路径为
“A”的根节点，并为其初始化一个空的childrenDArray。 -
解析子路径
“B”。在根节点的childrenDArray 中查找“B”。 -
若未找到，则在DArray的合适位置（保持子节点按路径名字典序排列）插入新的节点
“A/B”。
重要不变量：每个节点的子节点在其 children DArray 中必须按路径名保持字典序。
在本部分，您同样无需编写树的核心实现代码。主要任务是深入理解此数据结构，并基于我们提供的代码框架，编写一个完整的检查器（Checker），用于验证所有操作前后数据结构的不变量是否被保持。
第三部分：文件树 (FT)
第三部分是作业的核心编码部分，您将扩展目录树，使其支持文件和目录两种类型，构建一个完整的文件树。
接口在目录树的基础上进行了扩展，主要变化包括：
-
路径类型分离：针对目录和文件有独立的操作接口。
// 目录操作 FT_insert_dir(path); FT_contains_dir(path); FT_remove_dir(path); // 文件操作 FT_insert_file(path, contents, length); FT_contains_file(path); FT_remove_file(path); FT_get_file_contents(path, contents, length); FT_replace_file_contents(path, new_contents, new_length); -
文件内容管理：文件节点需要存储内容（
void*指针）和内容长度。 -
Stat操作：新增
FT_stat(path, &type, &length)函数，用于查询路径对应的是文件还是目录，如果是文件则返回其长度。// 使用示例：读取文件内容 FileType type; size_t len; FT_stat("/path/to/item", &type, &len); if (type == FILE_TYPE) { char* buffer = malloc(len); FT_get_file_contents("/path/to/item", buffer, len); // 处理 buffer free(buffer); }
关键设计点：
-
文件是叶节点，不能拥有子节点。
-
目录可以是内部节点或叶节点，拥有子节点（可以是文件或其他目录）。
-
您需要基于第二部分我们提供的、正确的目录树（DT）实现代码进行扩展，以完成文件树的构建。
客户端与测试 🧪
每个部分（BDT， DT， FT）我们都提供了一个客户端程序（client.c）。该程序使用一系列 assert 语句和打印输出来验证您的实现是否符合接口规范。
例如，在未初始化时调用插入函数，应返回 INITIALIZATION_ERROR。客户端会断言此行为。对于 to_string 等函数，客户端会打印结果，您可以与预期的标准输出进行比对。我们会在作业说明中提供正确的客户端运行样例。
总结与后续 🏁
本节课中我们一起学习了第四次作业的完整蓝图。我们明确了作业的五大核心目标：代码阅读、抽象对象模型、GDB调试、内部测试和模块化设计。我们详细剖析了作业三个部分（二叉目录树、目录树、文件树）的数据结构演变、接口定义和关键操作。
请记住：
-
第一部分：使用GDB调试，无编码任务。
-
第二部分：理解数据结构，编写检查器模块，无核心编码任务（但提供正确实现供参考和扩展）。
-
第三部分：基于第二部分的代码，实现完整的文件树系统，这是主要的编码挑战。
详细的作业规范将于下周初发布，相关的概念（如字符串路径解析、AO细节）也会在接下来的课程和辅导课中深入讲解。建议尽快寻找合作伙伴，共同开启这次系统编程的深入实践之旅。
020：存储层级、缓存与局部性 🏗️💾
在本节课中，我们将学习计算机系统中的存储层级结构、缓存的工作原理以及程序局部性的概念。理解这些内容对于编写高效的程序至关重要。
概述 📋
上一讲我们介绍了虚拟内存，它让进程以为自己拥有完整的64位地址空间。在讲解过程中，我们多次提到了不同类型的存储硬件，如寄存器、数据缓存、主内存和磁盘。现在，我们将深入探讨这些概念，特别是当我们开始学习更底层的语言时，这些知识将变得更加重要。
存储层级结构 🗂️
处理器运行速度极快，例如一个3GHz的处理器每秒可以执行30亿个周期。为了跟上处理器的速度，存储设备也需要足够快。如果存储速度慢于指令执行速度，指令就会等待数据的读取或写入，从而降低整体性能。
以下是典型的存储层级结构，从快到慢，从小到大：
-
寄存器：位于处理器芯片上，速度最快，容量最小（通常只有几十个，总容量约1000字节）。
-
缓存：位于处理器和主内存之间，通常分为L1、L2、L3三级。L1缓存最小最快，L3缓存最大最慢。
-
主内存：即RAM，速度比缓存慢得多，但容量大。
-
二级存储：本地磁盘。
-
远程存储：云端存储，容量近乎无限，但通过网络访问，延迟极高。
在评估存储设备时，我们关心三个因素：
-
容量：能存储多少数据。
-
延迟：开始读取或写入操作所需的时间。
-
带宽：开始传输后，单位时间内能传输的数据量。
延迟和带宽的区别解释了为什么有时系统会预读大量数据（例如从磁盘）。虽然启动读取的延迟很高，但一旦开始，后续数据的传输成本相对较低。
此外，我们还需考虑易失性。寄存器中的数据可能在几条指令后就丢失；内存中的数据在断电后会丢失；而磁盘和云端存储的数据是持久化的。
性能数据对比 📊
为了更直观地理解各级存储的速度差异，我们来看一些具体的数字对比。
以下是各级存储的典型延迟和容量对比（数据基于约10年前的处理器，但比例关系依然成立）：
| 存储级别 | 延迟 (周期数) | 容量 |
| :— | :— | :— |
| 寄存器 | ~0 | ~1 KB |
| L1 缓存 | ~4 | ~64 KB |
| L2 缓存 | ~10 | ~256 KB |
| L3 缓存 | ~40 | ~8 MB |
| 主内存 | ~200 | ~8 GB |
| SSD 磁盘 | ~100,000 | ~1 TB |
| 网络存储 | ~100,000,000+ | ~无限 |
从图表中可以清晰地看到，从寄存器到网络存储，延迟呈指数级增长。这就是缓存技术至关重要的原因。
局部性原理 🎯
要求程序始终使用最快最小缓存中的数据，在实践中是可行的。这是因为大多数程序都具有局部性，即它们在一段时间内只访问一小部分数据，并且一旦访问了某些数据，很可能很快会再次访问。
局部性主要分为两类：
-
时间局部性：如果现在访问了某个数据项，很可能在不久的将来会再次访问它。这在循环中很常见，例如循环控制变量和循环体内的指令会被反复访问。
-
空间局部性：如果现在访问了某个数据项，很可能在不久的将来会访问其相邻位置的数据。这在顺序访问数组或顺序执行指令时很常见。
大多数程序都表现出良好的时间和空间局部性。
局部性示例
计算数组元素之和是一个具有极佳局部性的例子：
-
时间局部性：循环变量
i和sum在每次迭代中被反复访问，循环指令本身也被重复执行。 -
空间局部性：数组元素被顺序访问（
a[0],a[1],a[2]…），指令也是顺序执行。
缓存的工作原理 ⚙️
缓存利用了程序的局部性原理，将近期可能用到的数据保存在更快的存储层级中，从而提升性能。
存储层级通常按级别编号，数字越小表示越快、越小。每一级缓存都存储了下一级存储中数据的一个子集。
缓存的工作机制如下：
-
当需要访问数据时，首先在最快的缓存（如L1）中查找。
-
缓存命中：如果数据在缓存中找到，则直接使用，速度最快。
-
缓存未命中：如果数据不在当前缓存中，则需要到下一级（更慢、更大）的存储中查找。
-
在下一级找到数据后，会将其载入当前缓存，以备后续使用。
-
由于缓存容量有限，载入新数据时可能需要驱逐旧数据。如果被驱逐的数据已被修改，还需要将其写回下一级存储以保持数据一致性。
目标是最大化缓存命中率，最小化未命中率。
缓存替换策略 🔄
当缓存已满且需要载入新数据时，必须决定驱逐哪一项旧数据。理想的策略是驱逐未来最长时间不会被访问的数据，但这需要预知未来，无法实现。
一个合理且常用的策略是 LRU：
-
LRU：驱逐最近最少使用的数据项。
-
其原理是：如果过去很长时间没被访问，那么未来很长时间也可能不会被访问。
-
LRU通常效果很好，但精确实现需要记录每个数据项的访问时间戳，开销较大。因此，实际系统中常使用近似的LRU算法。
一个极端的反例是：如果一个循环需要11条指令，而缓存只能容纳10条，使用LRU策略会导致每次访问第11条指令时，都驱逐即将用到的第1条指令，造成持续的缓存未命中。
局部性对性能的影响：矩阵乘法案例 🧮
局部性对程序性能有巨大影响。一个经典例子是矩阵乘法。
C语言以行主序存储多维数组。这意味着在内存中，矩阵的一行元素是连续存放的。
考虑计算 C = A * B 的三种三重循环实现（i, j, k 为循环变量）：
-
i, j, k顺序：这是较自然的写法。对A和C的访问具有良好的空间局部性（按行访问），对B的访问是按列的，局部性较差。性能尚可。 -
j, i, k顺序：这种写法导致对A和C的访问都是按列进行的，空间局部性极差。性能比第一种慢两倍以上。 -
k, i, j顺序：这种写法经过优化，对A、B、C三个矩阵的访问都实现了按行访问，最大化利用了空间局部性。性能比第一种快约10%。
这个例子表明，即使算法（计算逻辑）完全相同，不同的数据访问顺序（由循环嵌套顺序决定）会因局部性好坏而产生显著的性能差异。虽然聪明的编译器有时能进行此类优化，但程序员了解局部性原理并据此编写代码至关重要。
思考题
如果C语言使用列主序存储数组，那么为了获得良好的性能，矩阵乘法的循环顺序应如何调整？
答案：应该使用性能最差的第二种顺序（j, i, k）。因为在列主序下，按列访问才具有空间局部性，而这正是第二种顺序所做的。
缓存设计考量 🤔
在设计或使用缓存时，有几个关键考量：
-
块大小：一次从下一级存储中读取多少数据。
-
大块：能更好地利用空间局部性（一次读取相邻的多个数据），但传输时间更长，且会占用更多缓存空间，可能削弱时间局部性的效果（因为能缓存的不同数据项变少了）。
-
小块：反之。
-
-
缓存管理方：不同层级的缓存由不同角色管理。
-
寄存器：由汇编程序员或编译器管理。
-
L1-L3缓存：由硬件管理，要求速度极快。
-
主内存：由操作系统和硬件共同管理，涉及更复杂的算法（如虚拟内存管理）。
-
二级/远程存储：可能由硬件RAID控制器、文件系统软件（如Dropbox）甚至最终用户管理。
-
总结 📝
本节课我们一起学习了计算机系统中的存储层级结构。我们了解到，从寄存器到云端存储，速度和容量之间存在巨大的权衡。为了弥合快速处理器和慢速大容量存储之间的差距，系统采用了缓存技术。
缓存的有效性依赖于程序的局部性原理，包括时间局部性和空间局部性。我们通过数组求和和矩阵乘法的例子，看到了局部性如何显著影响程序性能。此外，我们还探讨了缓存的基本工作流程、LRU等缓存替换策略，以及缓存设计中的块大小和管理方等考量因素。
理解这些底层概念，将帮助我们在未来编写更高效的系统程序。
下节预告：下一讲我们将开始学习ARM64架构和汇编语言，为接下来的作业和课程内容做准备。请务必及时完成当前的作业。祝你好运！
021：汇编语言 part1 🖥️
在本节课中，我们将要学习汇编语言的基础知识，了解高级语言（如C）如何被转换为处理器能够直接执行的底层指令。我们将从C语言出发，向下探索汇编语言和机器语言，理解程序在计算机硬件层面的工作原理。
课程概述与学习方法 📚
到目前为止，本课程的重点一直是C编程语言以及大型软件工程。现在，我们将转向一个完全不同的领域。我们将开始深入探究，当我们调用那个我们讨论过很多次的、闪亮的四阶段GCC编译命令时，底层究竟发生了什么。这是一次从C编程语言向下到汇编语言，并最终到达处理器实际运行的机器语言指令的旅程。
我们的方法类似于之前在课程中为C语言所做的。我们将使用部分汇编语言程序。这些程序没有前向引用，至少我们尽可能避免。但这意味着，仅使用课程材料，在完成最终的汇编语言讲座之前，你将无法编写完整的程序。
另一方面，实验课将从一开始就使用完整的汇编语言程序。但这必然会有一些前向引用，需要在讲解时即时解释，或者暂时略过，稍后再进行补充。
从这个意义上说，讲座和实验课确实是互补的。我希望两者都能对你有所帮助，即使你可能自然更喜欢其中一种。
语言层级与抽象概念 🔄
在这次语言层级的探索中，我们将看到一些大型编程的主题，即抽象性和模块化，它们并非高级语言或C语言特有的编程方面，而是任何层级程序设计中普遍存在的基本概念。
因此，从多个层级查看完整语言有助于强化这一理念：完整的系统建立在其他完整的系统之上，这些系统逐渐变得更加抽象、更加模块化、更加用户友好。首先，让我们概述一下我们所说的高级语言和低级语言的含义。
高级语言 vs. 低级语言 ⚖️
此时，你可以自信地说，你对两种不同的语言——Java和C——已经有了相当扎实的入门知识。但这两种都是高级语言，它们在某种程度上共享几个共同特征。它们是可移植的，尽管不完全，正如我们在C语言中看到的那样。它们是复杂的。考虑这行代码：n = n * 3 + 1。这一行包含变量读取、乘法、加法和变量写入。或者while循环，它是C编程的基本构建块，但包含多个不同部分：要检查的条件、要执行的任意循环体、在结束时返回并再次检查条件的逻辑，以及当条件最终失败时跳过循环体的逻辑。
C和Java在很大程度上也是人类可读的。有些语言比其他语言更易读。对于没有编程经验的人来说，C语言可能有些晦涩，但你仍然可以用英语读出这个程序，一个结构思维强的非程序员可能会理解它的意思。至少除了位运算之外的一切。
在截然相反的一端，是机器语言。它们完全不可移植。主导台式机和笔记本电脑市场的X86-64处理器的机器语言，与SPARC处理器、MIPS处理器，或者我们将在本课程中使用的ARM处理器的机器语言完全不同。ARM处理器倾向于主导移动设备和嵌入式系统市场。
它们不那么复杂，因为每条指令执行非常简单的、基础的任务。同样，不同架构之间程度不同。但通常，没有像基础但多步骤的循环那样的东西。在可读性方面，这在任何真实意义上都不是人类可读的。
汇编语言介于两者之间。可以说，凡事皆有度。它不可移植。它是机器语言之上的一层薄薄的人类可读层。因此，如果它只是建立在机器语言之上，那么它的可移植性并不比机器语言强。X86-64、SPARC、MIPS和ARM的汇编语言完全不同。如果你打算用汇编语言编程，你就放弃了所有可移植性的希望，就像你用机器语言本身编程一样。
但像机器语言一样，它很简单。坦率地说，学习像汇编语言这样的语言比学习C语言更容易。它有许多相对较小、紧凑的原则，你可以将它们组合在一起。没有那么多高级的复杂逻辑被塞进一个操作中，就像你在C语言中看到的那样。至少，这是一种推动。但另一方面，它的表达能力不强。这是同一枚硬币的另一面：每条汇编语言指令都如此简单，以至于完成任何给定的工作都需要许多指令。
在可读性方面，我说过，汇编语言是机器语言之上的人类可读外壳。但此刻你可能会对此提出异议。你可能会说，这看起来不太像人类可读的。但请继续关注，我们会解决这个问题。
学习汇编语言的动机 💡
现在我们来谈谈动机。我知道你们中的许多人在这门课程之后可能再也不会编写汇编语言了，这没关系。尽管如此，我真诚地相信，了解程序内部真正发生的事情可以帮助你发现错误，可以帮助你提高时间或空间性能，并且可以改进你的程序设计，或者至少为你的程序设计提供信息。
了解汇编语言可以帮助你知道底层运行的是什么，这样你就可以实际编写汇编语言来编写更快的代码，或者为应用程序编写更优化的代码。例如，GCC编译器甚至不知道一些指令，但如果你知道它们并且发现它们适合你的应用程序，你可以使用这些有效的指令。
此外，了解汇编语言也可以帮助你在高级语言中编写更好的代码。如果你了解汇编语言以及高级语言代码如何映射到汇编语言，那么你将能够使用快速的高级语言结构，并避免那些慢速的结构。
因此，即使你再也不会用汇编语言编程，至少了解一点汇编语言也是值得的。此外，所有这些都基于一个论点，即你不想再用汇编语言编程。实际上，你可能想继续这样做。当然，许多甚至大多数计算机科学家终其职业生涯都在为他人需求开发计算应用程序。
但一些计算机科学家必须设计计算机，必须设计架构，必须设计其他计算机科学家使用的编译器。也许你想走这条路。如果你决定走这条路，你将需要用汇编语言编程，或者至少能与那些用汇编语言编程的人交流。
为什么选择ARM架构？ 🤔
以上是关于汇编语言的一般情况。那么ARM呢？通常人们不会为高级系统编写汇编语言。因此，选择一个在嵌入式系统中典型的架构，一个在嵌入式系统中典型的架构，是一个自然的选择。ARM是嵌入式系统、移动设备和其他你可能实际想为其编写汇编语言的低级硬件的主导硬件集。所以我认为这是一个很好的选择。此外，它更简单，当我们很快进入其指令集时，我们会谈到这一点。
有了这个动机，让我们看看底层架构，包括快速回顾一下CO 126课程中的一些计算组件材料。
冯·诺依曼架构基础 🏗️
从根本上说，本课程中使用的ARM架构及其替代品X86架构，都可以追溯到约翰·冯·诺依曼的工作。让我在这里简单介绍一下他。他在普林斯顿大学和IAS（镇上的研究机构）工作了大半生。你可能只是从校园里有一栋以他命名的建筑而听说过他。这栋建筑在校园的最东边，甚至连工程师都会说：“真的，那是霍尔吗？”对于福布斯来说，这几乎是一次跨大陆的航行。是的，他是一个令人恐惧的天才。六岁时，他就能在脑子里进行八位数的乘法和除法。他有一种孩子般的天真，当他看到其他人凝视着太空时，他会问他的母亲：“我想知道他们现在在计算什么复杂的事情。”好像每个孩子，甚至每个人，都会这样做。
他是匈牙利黄金智力一代的一员，这一代产生了许多诺贝尔奖得主和其他在各个领域（包括计算机科学）具有根本重要性的人。但他可能是那一代人的领导者。但当物理诺贝尔奖得主尤金·维格纳被问及匈牙利如何产生了这一代天才时，他实际上拒绝回答。他首先不同意这个前提。他说，经历过冯·诺依曼之后，他可以自信地说，这群人中只有一个天才。而这又是氢弹之父、核链式反应之父以及这一群体中的其他诺贝尔奖得主。
更进一步，另一位诺贝尔奖得主汉斯·贝特推测：“我有时想知道，像冯·诺依曼这样的大脑是否表明存在一种优于人类的物种。”所以我们谈论的是真正的天才之一，类似于爱因斯坦、高斯、欧拉那种类型。
但抛开地理因素，让我们跳入他出现在幻灯片上的实际原因。在他工作的时代，这些新奇的计算机的实验性架构是一种程序与其操作的数据有独立物理内存的架构。这后来被称为哈佛架构。
冯·诺依曼是开发不同范式首批实现之一的先驱。在这种范式中，程序和数据共享相同的内存。与哈佛架构相比，这被称为普林斯顿架构。当然，必须指出，普林斯顿架构被证明比哈佛架构更成功。
话虽如此，EDVAC作为一个整体，这台机器是其中的一部分，是与宾夕法尼亚大学的埃克特和莫奇利合作的项目，它实际上是一项工程壮举，而非核心科学。这个想法本身至少可以追溯到十年前，追溯到你在126课程中学到的图灵通用机的变体。但尽管如此，我们永远不会错过任何一个吹嘘普林斯顿并抨击哈佛的机会。
冯·诺依曼架构详解 🧩
在冯·诺依曼架构中，从根本上说，有两个硬件单元：处理器和内存。实际上，可能有几个不同类型的CPU，无论是传统CPU、多核CPU，还是像GPU这样的专用处理器。此外，可能有多块RAM芯片。然后，正如我们上次看到的，处理器和RAM之间有多个不同级别的缓存。还有其他硬件，磁盘、网络设备等等。所以这当然是一个简化，但一个处理器和一个内存的抽象视图对我们来说就足够了。
在物理领域的硬件中，CPU和RAM实际上只是两种不同类型的集成电路或芯片。它们通过主板上的电线进行通信。这条电线称为数据总线。所以有RAM随机存取存储器芯片和CPU或中央处理单元芯片。
我们进一步将CPU分解为三个结构，这与我们在126课程中讨论的三个相同：控制单元、ALU和寄存器。这里的ALU是算术逻辑单元。
控制单元是CPU的操作控制，可以说是经理。它解释ALU将要计算的指令，并控制CPU和内存之间的数据传输。ALU是大脑或计算器；它实际处理指令和指令所需的数据。大型数学模块。
最后，寄存器，正如我们上次讨论的，是小的、非常快的、在CPU芯片上的存储。你可以把它们看作芯片上的一系列小箱子。它们提供极快的访问速度。我们上次说过，延迟不到一纳秒，但它们非常小。处理器上所有寄存器的总容量不到512字节。
一个程序能用这么小的内存做什么呢？在程序中，这些可以分配来存储变量、指向程序中某个位置的指针、指向内存某部分的指针，甚至只是在多步计算期间用作暂存空间。尽管如此，尽管数量少、容量小，这些寄存器是至关重要的资源。
因此，当控制单元获取要处理的指令时，ALU实际执行处理本身。例如，在算术运算中，我们将从两个源寄存器获取数据，完成操作，并将结果放回指定的目标寄存器。所以控制单元决定数据来自哪个寄存器，或者如何首先将数据放入这些寄存器，而ALU实际进行数学运算。
显然，如果寄存器这么小，总共不到1K字节，那么我们的程序显然需要比这多得多的空间，这就是RAM的用武之地。在大多数普通笔记本电脑中，RAM的容量大约在十亿到数百亿字节之间，这肯定比512字节多得多，但同样，延迟在100纳秒以上，所以慢了100倍。RAM是我们程序运行时使用的所有数据的主要存储位置，正如我们在冯·诺依曼架构中讨论的，这包括程序本身，即实际的指令本身。
从TOY架构到ARM架构的过渡 🚀
现在我们已经看到了将要处理的结构基础，但在深入ARM架构和AArch64的ARM指令集细节之前，让我请你记住你在126课程中学到的关于TOY的内容。处理器，我们说过有ALU和控制单元，正如我们所见。指令集，如果你回想一下，由操作码和一个地址及一个寄存器，或一对寄存器组成。总共有16个寄存器，命名为0到F，其中一个特殊寄存器始终只包含零，那就是零寄存器。有一个额外的寄存器，它不是这个数字运算的可能存储数据的地方，而是始终包含要执行的下一条指令的位置。那就是程序计数器。主内存中有256个字，每个都有自己的地址。通常，我们用十六进制表示它们。内存可以存储数字，这就是它的功能。我们可以将这些解释为无符号整数、有符号整数、内存地址或指令本身。
关键是，ARM几乎完全相同。我们所要做的就是改变数字，扩大规模。我们有更多的指令，需要更多样化的指令格式，但核心仍然是相同的：操作码、一些目标和一些源。ARM有32个寄存器，每个存储64位。但同样，其中一个始终为零。我们有两个额外的寄存器，包含指向内存重要部分的指针：一个程序计数器，就像在TOY中一样，还有一个指向栈顶的指针，即我们当前正在执行的栈帧。有一个主内存的表示，同样，每个位置都有自己的地址，通常用十六进制表示，内存可以再次存储数字、无符号整数、内存地址或指令，无论我们选择如何解释它们。这实际上非常熟悉。这不是什么全新的东西。
加载-存储架构与RISC理念 🧠
让我们再深入一步。在TOY中，有一个相当严格的加载-操作-存储范式。如果数据在内存中，我们必须首先将其加载到寄存器中，然后我们可以在寄存器内操作它，将每个操作的结果依次放入新寄存器，然后在完成所有计算后，将最终结果存储回内存。ARM也是如此。同样是完全相同的加载-存储架构。
在TOY中，指令集非常有限。如果你想做任何复杂的事情，你必须将几条甚至许多条指令组合在一起。但好处是，记住所有存在的指令超级容易，并且能相当深入地理解它们。好吧，也许除了分支链接指令。但同样，ARM也是如此。在本课程中，我们将要担心的指令相对较少。你会对它们有相当深入的了解。
选择拥有一个小指令集是RISC理念的象征，即精简指令集计算机，与CISC或复杂指令集计算机相对。因此，RISC有一个简单的集合，涵盖了所有你需要做的事情，但你可能需要将它们组合在一起来做任何有实质内容的事情。另一方面，CISC有一个复杂的集合，它有一个扩展的操作集，包括一些执行非常特定操作的东西，甚至包括一些不遵循标准加载-操作-存储范式的东西。但为了充分利用这一点，你必须知道它能做什么，它们是什么，并且更难内化整个指令集的范围。此外，在硬件层面，如果我们有这些复杂的指令，我们需要复杂的硬件来使其工作。RISC机器的实际硬件架构往往更简单。
ARM寄存器详解 📊
好的，现在我希望我已经说服了你，这又不是一个你完全没见过的新东西。你学到的关于TOY的知识确实与我们用ARM要做的事情相关，至少在高层次上是这样。所以让我们深入探讨，但作为系里的安置官，我必须承认，你们中有些人没有上过126课程，你们可能会想：“等等，这是什么？我完全不知道你在说什么，你声称我知道这个，我发誓我不知道。”如果这听起来完全是新的，那没关系。我鼓励你去看看126的材料，浏览一些TOY材料、TOY程序。阅读简单的东西。我不是说去花整整一个月学习126，但这是一个合理的事情。在跳入ARM之前，先去浏览一下材料，看看一个更简单的版本。
那么，ARM有——我们现在就开始——ARM有31个通用寄存器。这里的“通用”有点用词不当。实际上，其中几个在整个程序中扮演着非常专业、非常具体的角色。但当我们说通用时，我们指的是这些寄存器，我们可以（在采取一些预防措施的情况下）操作它们。我们通过编号来寻址它们，寄存器0到寄存器30。请注意，这是十进制，不是十六进制，所以寄存器10是第11个寄存器，而不是第17个。
这些寄存器中的每一个都是64位。我们在程序中引用它的方式是使用X加上寄存器编号。有时我们只想使用寄存器的一部分，例如，如果我们存储一个int，在我们的系统中int是4字节，所以我们只需要32位。在这种情况下，我们可以通过W而不是X来寻址寄存器的低32位。再次注意，虽然我们称这些为通用寄存器，但其中一些实际上在硬件或软件约定中具有特定的用途。因此，我们不能随意选择任何我们想要的寄存器，我们必须承认有些寄存器已经在执行任务，即使我们没有特别指定它们。
特殊寄存器：SP、PC与PSTATE 🎯
这些是通用寄存器，现在谈谈这些特殊寄存器。每当一个函数被调用时，它会将其参数和局部变量的内存压入栈顶，我们知道这个，内存被称为函数栈帧，就像我们在C语言中讨论的那样。因此，在AArch64架构中有一个叫做SP的寄存器，它指向当前正在执行的函数栈帧的最高地址（最低地址）。所以这就是我们最终如何进行函数调用和局部变量的方式，但这要到几节课之后才会涉及。
与TOY一样，我们有一个程序计数器。它指向内存中将要执行的下一条指令的位置。我们知道这意味着我们指向文本段，因为那是我们指令所在的地方。控制单元负责在处理指令时自动更改PC；如果存在顺序控制流，它可能从一条指令递增到下一条指令；或者如果存在更复杂的流，如条件循环或函数调用，它可能跳转到文本段的完全新部分。
最后一个特殊寄存器是我们在TOY中没有看到的。在TOY中，我们的两条分支指令以寄存器作为参数；在ARM中，它们不是。相反，在我们进行条件分支之前，我们观察一些先前指令的特征，通常是比较操作。例如，我们可能会说，它是否设置了结果为零的标志，或者是否设置了发生溢出的标志？这些条件作为位存储在处理器状态寄存器中。因此，PSTATE是我们需要关心的最后一个特殊寄存器。我们通常不会直接访问PSTATE，而是通过执行条件操作、条件分支来间接访问。
ARM指令格式与算术运算 ➕
好了，有了这些关于架构、关于指令集（或至少它必须有什么）的基本概念，让我们继续讨论指令集、汇编语言，并看一些程序片段。
回想一下之前ALU对算术指令的看法。现在，如果你对之前的图表感到困惑，你知道标志是干什么用的了。那么，让我们看看，如果它是这些算术操作之一，一条指令实际上是什么样子的。
每条指令至少有一个在语义上有意义的名字。通常，然后是目标寄存器，接着是源寄存器。所以，如果你还没有学会爱上“目标-源-源”的参数顺序，这里是你更多机会爱上它的地方。在某些情况下，第二个源可能不是一个寄存器，而是一个称为立即数的常量值。
第一个汇编程序示例：计算矩形周长 📐
这是我们的第一段汇编代码。矩形的周长是其所有边的总和，所以是宽度和高度之和的两倍。这是一个实现此功能的C程序。请注意，我们在这里假设了全局变量，原因是我们要到很久以后才会看到如何处理局部变量，这涉及到整个函数调用和栈的部分。
有了这些映射到这些寄存器的变量，我们需要一条加法指令和一条乘法指令。哇，等等。LSL，那是乘法吗？不应该是MUL之类的吗？实际上，LSL是左移，但回想一下，左移一位实际上是乘以2。
这里还要注意一件事，书中在立即值前使用井号（即数字符号或标签符号），这对读者来说是一个有用的信号，表明注意这不是X1，这不是W1，这不是某个寄存器1，这实际上是数字1。同样，书中使用了这个。总的来说，我们不会在幻灯片上这样做，这不是必需的，但如果你愿意，你可以在代码中使用它。
更多算术运算与指令别名 🔧
好的，现在来看C语言中更多的算术运算以及它们在汇编语言中的样子。这里只是操作的演示，甚至没有假装有一个程序或应用程序；这只是关于ARM内容的纯粹数据转储。大多数名字都很直观，但有些需要解析，特别是异或操作使用EOR而不是XOR，这是学生容易出错的地方。另外，回想一下我们在上一张幻灯片上讨论的移位操作。C语言对于右移操作没有标准规定，是保持有符号整数的符号位，还是总是在左边填充零。但汇编语言有。对于算术右移和逻辑右移，有单独的指令。
一些类似的指令并不完全是它们看起来的样子。虽然我们已经深入底层，首先讨论汇编语言，但让我们再深入一点底层，讨论一下别名或快捷方式。你可能认为将一个变量从一个寄存器移动到另一个寄存器对于汇编语言来说是一个非常原始的操作，但实际上在硬件中是通过与零寄存器进行按位或操作来实现的。这是因为任何数与0进行或运算都是它本身。类似地，我们可能认为一元取反是乘以-1，但实际上在硬件中是通过从零寄存器减去来实现的。这是一件好事，因为减法通常比乘法快。
还有其他这样的例子，语言给我们一条在语义上有意义的指令，但实际上在底层将其实现为另一条指令的别名或快捷方式。
有符号与无符号运算及寄存器大小 📏
我们还没有提到的一件事是，在讨论C语言中的算术运算时，我们必须担心有符号与无符号。但有了二进制补码，我们得到了一个很好的好处，即大多数操作的底层位操作算法是相同的，无论我们讨论的是有符号还是无符号算术。只是我们如何解释最终结果。因此，我们得到了一个优势，即在ARM中，这些算术运算的指令是相同的，只有少数例外。我们将在未来的讲座中看到，当我们讨论控制流时，有符号/无符号的差异通常不会出现在值本身或我们用来操作这些值的算术指令本身中，而是出现在我们稍后决定条件分支的比较指令中。
好的，继续我们的内容，我们已经看到了一些东西，但我们遗漏了一些我们在C语言中知道的东西。到目前为止，我们只处理了64位算术，这说得通，因为我们设置的寄存器是64位的。但是，如果我们想像之前的周长程序那样使用int而不是long呢？我们可以使用W命名来寻址寄存器的下半部分，而不是完整的寄存器。我们看到这是一个特性，这里展示了它与我们程序的相关性。当我们使用long时，这些是64位或8字节的结构，使用X寄存器来寻址我们知道是8字节的地址是有意义的。但是当我们的程序中有int时，我们应该使用寄存器的W版本。当然，在C语言中还有更小的数据类型，但没有更小的、有自己名称的可寻址寄存器部分，所以我们将使用W寄存器来处理short或char。但这实际上没问题，因为与C语言匹配，因为在算术运算中，char或short会隐式提升为int。你可能不记得在很早的一节课上提到过，但确实，你对short或char进行的所有算术运算实际上都是int运算。这与硬件和汇编语言匹配，我们将使用W寄存器和完全相同的实际指令。
这是针对算术运算的。在几张幻灯片之后，我们将看到有特定大小的加载和存储操作，用于在这些寄存器和内存之间获取数据，这说得通。你不能很好地将完整的4字节寄存器写入内存的单个字节，或者从内存的单个字节读入4字节寄存器。当然，我们必须有某种方法来实现这一点，而不是说：“哦，我要读入我从未初始化的内存。”
加载与存储操作：内存访问 🚚
所以，就加载-操作-存储范式而言，那是操作部分。现在让我们继续讨论如何将数据移入和移出寄存器以及移回内存。
与TOY不同，在TOY中我们可以将字面内存地址放入指令中，而在ARM中，延续其非常纯粹的基于寄存器的加载-存储架构，甚至比TOY更进一步，我们必须首先将该内存地址放入寄存器，以使该寄存器有效地成为指针。你以为你已经学完指针了？还差得远呢。然后，一旦我们有了这个指针，我们解引用该指针以获取用于加载或存储的内存位置本身。
我们在ARM中表示这一点的方式是将寄存器名称放在括号内。我认为这非常漂亮，因为括号是内存的解引用操作符，我们将内存视为一个大数据数组。这与C语言完美匹配，在C语言中，数组索引使用括号操作符完成，我们看到这实际上是对数组起始位置的隐式解引用。因此，在C语言的语法和这种汇编语言的语法之间存在着完美的对称性。
再次注意这里的顺序：对于加载字指令，从第二个操作数引用的内存地址加载到第一个操作数寄存器。对于存储指令，我们从第一个操作数寄存器存储到第二个操作数寄存器引用的内存地址。所以内存操作数总是排在第二位。这是记住这一点的最简单方法。但很容易陷入困惑：“等等，数据流的方向是哪个？”但如果你想到内存操作数总是排在第二位，你就会得到正确答案。
不同大小的加载与存储操作 🔄
如前所述，有一些特定的指令用于读取一个字节或两个字节，包括有符号和无符号，以及一些额外的语义指令，用于说明在读取小于8字节的内容时如何填充寄存器内容。不过，现在让我们坚持使用4字节和8字节的量，以使事情更容易。
完整示例：周长程序的汇编实现 🧩
好的。我们差不多准备好看一个完整的例子了。但有一件事要注意。我们提到，在加载和存储中，我们将使用包含内存地址的寄存器作为指针。这意味着我们首先需要将该内存地址放入该寄存器中，以充当指针。这将取决于地址位于内存的哪个段，但现在让我们考虑文件作用域和进程持续时间的变量，以便它始终位于数据段或BSS段。这听起来让它变得更复杂，因为数据段和BSS段对我们来说只是几个实验课之前才接触的新概念，但在汇编语言中，实际上最初会让它更容易。
好的，这是稍微扩展了一点的周长程序。这是它的汇编代码。此时，它对我们来说似乎是人类可读的。但如果仍然觉得难以理解，那完全可以理解。所以让我们一步一步来。
我们可以用标签标记或命名内存中的一个位置。例如，length: 这是程序将存储length变量的内存位置。.word指令告诉汇编器在当前内存位置分配四个字节的内存，并将后面的值存储在那里。所以这就是标签和该标签处的.word指令。这就是我们在数据段或BSS段分配内存的方式。
但首先，我们需要看看如何定义位于这些段中的数据。我们需要首先进入那个段。所以，让我们不要跳过太多，一次看一个。.section指令告诉汇编器我们现在处于正确的内存段。所以在这种情况下，数据段或文本段。这适用于RO数据段、数据段、BSS段和文本段。我们将在未来的讲座中看到如何使用栈，并且在本课程中不会使用堆进行动态分配，所以堆中完全没有东西。
所以我们说过，我们讨论了标签，这是我们标记内存位置以便以后引用的方式。标签名称是有意义的。它们在程序本身中按名称引用，并且希望具有语义意义。通常，如果我们从C语言翻译到汇编，希望这是一个变量名或字符串提示符的名称等等。
同样，.word指令只是告诉汇编器：“请为4个字节分配内存，并把这个值放进去。”请注意，这里的.word声明的是数据段中的一个int。其他数据类型将有不同的尺寸说明符，其他段实际上将使用不同的指令。例如，BSS段使用不同的指令，因为它不需要初始化值。我们将在本讲座接近结束时讨论这些。
现在我们开始进入文本段，我们从哪里开始呢？当然是main。我们知道main是一个从_start调用的函数，我们知道我们没有编写_start。所以这一定意味着main必须在其自身文件之外可见。在C语言中，我们默认实现这一点。我们隐式地实现它，因为外部链接是默认的。所以只要我们不意外地在main前面加上static这个词，一切都没问题。但在ARM中，内部链接是默认的。因此，在C语言中，我们必须为内部链接指定static，而在ARM中，我们必须用.global指令明确指定全局可见的符号。
所以main得到一个.global。现在，一旦我们前进到main开始的内存位置，即main指向的位置，我们终于可以回答如何将内存地址放入寄存器以用作加载/存储的指针的问题了。有一个叫做ADR的伪指令。地址指令获取标签的内存地址并将其指向一个寄存器。所以ADR X0, length表示：找到length被标记的地址，并将其放入X0寄存器。
有了这些地址，我们就可以进行加载和存储操作，这些操作我们之前孤立地见过。我们在上一行做了ADR，所以我们有一个包含地址的X0。这意味着我们应该将X0视为一个指针。毕竟，这正是C语言中的指针：一个内容为内存地址的变量。我们使用括号表示法作为加载的源或第二个操作数，以及作为存储的目标或第二个操作数来解引用指针。
最后，我们可以使用寄存器0来完成函数。这里使用W0是因为它是一个int来存储返回值。请注意，我们在这里一直使用寄存器0。所以与TOY不同，始终为零的寄存器实际上不是寄存器0。在我们的ARM中，它将是WZR或XZR。所以这里的W0或X0在语义上是返回值，是我们将要放入返回值以便返回的地方。
然后RET指令是实际导致程序计数器跳转到文本段中新位置而不是继续执行下一条指令的指令，这是我们从一个函数返回的方式。我们将在后面更详细地讨论函数返回、函数以及程序控制。
最后，在逐步讲解了代码中的每条单独指令之后，让我们来跟踪一下。在执行开始时，所有数据段都已填充。main开始，第一个操作是建立X0作为指向length的指针。我们这样做，X0现在我们可以把它画成一个漂亮的小箭头，所以我们想解引用那个指向length的指针，并通过跟随箭头加载我们得到的值，我们将其加载到W1中。我们这样做，现在我们将把X0改为指向width的指针。所以我们有寄存器W1的值为1，X0现在指向width变量。所以再次，我们解引用指针，我们跟随箭头，这次加载到W2中，所以W2得到值2。接下来，我们将W1和W2相加，得到3，所以1加2是3，我们覆盖W1。所以就像在TOY中一样，源寄存器和目标寄存器实际上可以是同一个。它将对旧值进行操作，然后将新值写回以覆盖寄存器。
我们的下一个操作是左移，我们将值3左移一位。所以之前是30个零后面跟着11，变成了29个零后面跟着110，因为当我们左移时，我们用零填充，所以我们得到。此时，值为6，因为我们有110，那是4和2，0是4加2等于6，但我们真正做的是得到值3，然后乘以2，这就是我们得到6的方式。
接下来，我们将做另一个ADR来再次更改指针X0。然后我们再次解引用指针。但这次是在存储中。所以这就像在C语言赋值的左侧解引用，而不是右侧。我们将存储到我们跟随箭头得到的那个位置。按照惯例，返回值被放入寄存器零，所以因为我们的程序在成功时返回零，并且因为我们的C程序在这里返回零，我们必须将零放入寄存器。它是W0，因为同样main返回一个int，所以它是一个4字节的量，是一个W寄存器，而不是X寄存器。现在我们返回到调用，我们的程序就完成了。
附录：数据段定义与字节序问题 📝
好的，本讲座有两个附录部分，我将快速浏览一下，但我鼓励你花点时间更详细地浏览它们，因为同样，我不想信息过载。但考虑一下这里的C代码。每一个都是文件作用域的进程持续时间变量，并且每一个都给出了显式初始化。这意味着它们属于数据段，就像我们之前看到的那样，i完全像我们之前看到的那样，使用数据段变量的.word指令，该变量是一个int。.short用于2个字节。这与C类型名称匹配。.quad用于8个字节。那里的命名是一个时代错误，但它一直沿用下来。嗯，它没有显示在这张幻灯片上，但它实际上是一个有效的标签吗？因为它不是一个有效的标签。因为在C89中，我们没有它的类型，没有整数类型，但ARM也支持.octa用于16字节变量，这相当于C99的long long int。有人会指出来，所以我现在就坦白。我们在这里有点不一致。.short实际上是.hword（半个字）的别名，这是标准的ARM指令。但我们停在那里使用别名是有充分理由的，因为使用与C类型匹配的别名可能会给ARM程序员带来麻烦。是的，有一个.int指令，它实际上与.word做完全相同的事情。还有一个.long别名，它与.word做完全相同的事情。.int和.long都给我们4字节的量。这就是为什么我们区分.word和.quad，这样你就不会被诱惑使用.int和.long并灾难性地出错。
还有几点说明，我们在上一张幻灯片上展示给你的别名。它们，对不起，我们展示了标签放在上一行，但它们可以放在同一行，这完全没问题。嗯，基本上，无论对你来说看起来更好，这可能取决于上下文。还要注意，我们在main的上下文中看到了.global，表示main是外部可见的，但是为了声明变量的相同属性，我们也可以对变量使用.global，在这种情况下，对一个变量，我们说它是一个恰好位于特定标签处的内存量，所以对标签使用.global，完全没问题，即使那不是函数，即使它是一个变量。
我提到BSS将是特殊的。它不使用.word或.quad等，因为它不需要指定初始值。这就是变量最终进入BSS段的原因。在C程序中，它们没有获得初始值，所以它们进入BSS段，在那里它们可以被假定为0。因此，BSS段不使用.word、.quad，而是使用.skip，它是.space的别名，这是一个指令，用于指定标签之间要跳过的字节数，即为该符号（标签）分配的字节数。
最后，RO数据段，我们从本课程最早的日子就注意到，编译器将字符串字面量放入RO数据段。但如果你此时没有使用编译器，并且你希望一个字符串字面量在RO数据段中，你需要自己把它放在那里。.string指令正是这样做的。它为字符串分配足够的内存，包括末尾的空字节（\0），并将该字符串存储到分配的内存中。
这些幻灯片中的第二个附录讨论了字节序问题。如果你以前没有遇到过这个概念，我鼓励你仔细看看这些幻灯片，以及Pit和Newgeta的第27和28页，我认为King的第520页也有，但那将是在不同的指令集中。因此，当我们有多字节结构时，比如说一个占用4个字节的int，我们可能有两种自然的方式在内存中表示它们。一种是从最高有效字节开始写，直到写完。如果我们考虑一个四字节结构，最高有效位在左边，这是我们通常思考数字的方式，这似乎有些道理。这将导致最高有效字节存储在最低内存地址，因为我们考虑从上到下写内存。我们称之为大端序，因为是的，这是对乔纳森·斯威夫特的讽刺作品《格列佛游记》的引用，但大端序的意思是“大端”在前。
相反的就是小端序。小端序说，多字节实体的最低有效字节首先存储，这实际上是ARM所做的，A64架构所做的，因此ARM指令集必须做的。但请注意，这不是反向存储。不要认为所有位都从最低有效位一直翻转到最高有效位。这是一个字节一个字节的。所以是按字节，最低有效字节先存储，然后是下一个最低有效字节，一直到最后一个存储的是最高有效字节。但在字节内部，位是按你期望的顺序排列的。
字节序对程序的影响 ⚠️
这对一些程序有影响，例如这里的C代码是不可移植的。它在大端序计算机上会有不同的输出，因为它一个字节一个字节地遍历，但这些字节根据字节序以不同的顺序存储。因此，我们一个接一个地访问它们的顺序会改变。
同样，当我们处理多字节数据结构的单个字节时，它也会延续到我们的汇编代码中。在Arlab上的这段代码中，程序返回7，因为A64是小端序，所以获取字中的最低地址会获取包含7的字节。另一方面，大端序机器将返回0。字中的最低地址将导致其最高有效字节，即0。
课程总结与后续安排 🎓
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
0
0- 0
已为社区贡献51条内容
所有评论(0)