CS:APP Lab 3 解题报告 - 64位

CSAPP 的 Lab 3 在第三版之前都是所谓的 Buffer Lab,而 CSAPP 第三版的配套 Lab 3 则是 Attack Lab。因为我们学校新开的计算机系统基础课可能要以此为实验,故再来重新感受一番。该 Lab 的实验流程与 Buffer Lab 基本相同,我们直接开始。本次实验笔者使用的环境为 Ubuntu 18.04。

阅读全文

数字逻辑 - 组合电路:小型设计 笔记

这一章介绍的是设计小的组合电路时候的设计方法。

信号命名标准

对于一个信号,如果逻辑 1 表示有效,逻辑 0 表示无效,不活跃或者禁止的话,我们称此信号为高电平有效的,通常我们使用不带任何前缀或者后缀的名称来表示一个高电平有效的信号;如果逻辑 0 表示有效,逻辑 1 表示无效,不活跃或者禁止的话,该信号就是低电平有效的,我们一般使用带有下划线的名称来表示低电平有效信号。

阅读全文

手撸调试器(1) —— 载入 inferior

近几天放假无事可做,便开始翻 Linux 中国的微信公众号找乐子,在他们的推送里,我发现了这篇文章,看完后有了想要自己写一个玩具调试器玩玩的想法。于是就有了这个系列的文章。

阅读全文

当你 malloc(0) 时会发生什么

故事要从今天中午一位同学提到了这个问题开始……

5b572595b42f1

这个问题看起来十分刁钻,不过稍有常识的人都知道,制定 C 标准的那帮语言律师也不是吃白饭的,对这种奇奇怪怪的问题一定会有定义。我们翻阅 C17 标准 草案 N2176,在 7.22.3 节里,有如下说法:

阅读全文

使用正则表达式匹配 3 的倍数

北邮的考试周,与别处是不同的。都是近两周的时间,经常穿插着空挡,预备着可以随时抱佛脚。复习的人,傍午傍晚复习崩溃,每每花四十分钟,拿出手机 —— 这是十年前的事情,现在根本没有这么多时间。 —— 在教室做着,热热的玩了休息;倘肯多花一小时,便可以水一水群,或者看一看知乎,做精神娱乐了,如果歇到八九个小时,那就能回一趟宿舍,但这些学生,多是害怕考试挂科的,大抵没有这样阔绰。只有做学霸的,才踱进教室西边的宿舍里,拿起电脑,慢慢地玩游戏。

阅读全文

CS:APP Lab 4 解题报告

CSAPP 的第四章《处理器体系结构》大多讲述的是 CPU 的实现,比较偏硬件。大约也是这个原因,很多高校在选用此教材讲述计算机系统导论课程时会直接跳过这一章。与之配套的 Lab 4,Architecture Lab 则更是无人问津。我趁着考完期中的空闲时间,花了近一天时间啃了下第四章,并顺便做了个下这个 Architecture Lab。

阅读全文

详解并查集(基础篇)

简介

并查集是一种树型的数据结构,用于处理一些不相交集(Disjoint Sets)的合并及查询问题。不相交集,顾名思义,就是交集为空集的一些集合。比如集合 {1,3,5} 和集合 {2,4,6} 就是不相交集。 {2,3,5} 和 {1,3,5} 就不是,因为他们的交集不是空集。该数据结构由Bernard A. Galler和Michael J. Fischer于1964年提出。

阅读全文

使用 C/C++ 模拟 defer 关键字

笔者在翻译完 这篇文章 以及同系列的下一篇文章(尚未发布…)后,受到了 ESR 大神的鼓舞,遂决定在寒假学习一下 Go 语言。在学习 Go 语言的过程中,觉着这语言和之前学到的 C/C++ ,Scheme 相比有着无法比较的简洁感。笔者尤其喜欢 defer 这一关键字的设计。于是就在今天尝试使用 C/C++ 模拟了下 defer 关键字。

阅读全文

详解二叉堆(基础篇)

堆(heap),又称为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。在队列中,我们可以进行的操作是向队列中添加元素和按照元素进入队列的选后顺序取出元素。而在堆中,我们不是按照元素进入队列的先后顺序,而是按照元素的优先级取出元素。

Linux 内核中的调度器会根据各个进程的优先级对程序的执行进行调度。在操作系统运行时,通常会有很多个不同的进程,优先级各不相同。在调度器的作用下,优先级高的进程被有限执行,优先级靠后的就只能等待。堆是实现这种调度器的一种很合适的数据结构(顺便提一下,现在的 Linux 内核的调度器使用的是基于红黑树的 CFS ,笔者以后会专门介绍)。

阅读全文

详解 AVL 树(基础篇)

AVL 树是一种平衡二叉搜索树,得名于其发明者的名字( Adelson-Velskii 以及 Landis)。(可见名字长的好处,命名都能多占一个字母出来)。其递归定义如下:

  1. 左右子树的高度差小于等于 1。

  2. 其每一个子树均为 AVL 树。

阅读全文