程序员新手的大麻烦-堆栈

语言: CN / TW / HK

我正在参与掘金技术社区创作者签约计划招募活动,点击链接报名投稿

堆栈对我来说让我迷惑了很久,搞不清堆、堆栈、栈,它们三个究竟是什么东西?

概念

有一天当我在看汇编语言的AT&T语法中针对popl和pushl介绍的时候,再次看到了堆栈。可能过去的多次碰面是为了这一次的心血来潮做准备的吧。

在不少书上涉及到堆栈(stack)、堆(heap)、栈(stack或者stacks)。堆(heap)这个概念很容易排除出去。至于堆栈和栈,它同样使用stack表示就会让人迷惑。

在去merriam-webster上看了一下,结果得到了令人意外的发现。如下:

image-20220630145327444.png (图片来自:https://www.merriam-webster.com/dictionary/stack

英译英的词典上尝试找到英语语种环境下的本源的含义(避免中文翻译过程中对于意思的曲解给中文群体的人带来的困惑),它的翻译究竟是什么?在stack的名词性解释下的第7条的a解释,如下:

a: memory or a section of memory in a computer for temporary storage in which the last item stored is the first retrieved also : a data structure that simulates a stack a push-down stack

在also之前的含义重点是memory in a computer,在also之后的重点是data structure

也就是说stack一种表示的是计算机内存的一种先进先出设计的存储方式。而另一种是栈数据结构。这样的描述让我茅塞顿开。

对比

为了印证这个观点,我在去中文博客上翻了翻。得到了如下两种说法,一种观点是:堆栈就是栈,另一种观点是堆栈在内存中是堆栈,在数据结构中是栈。

image-20220701055429344.png

当我中文博客的解释还不能完全说服自己的时候,我又去找了两本数据结构的书和一个《Intel® 64 and IA-32 Architectures Software Developer’s Manual》文档对上面的内容进行佐证。

在《Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A:System Programming Guide, Part 1》找到如下一段带有stack单词的描述:

image-20220701060845957.png 因为在操作系统中根据全局描述符表(GDT)和局部描述附表(LDT),通过对数据段、代码段和内存段这种不同类型的段,也就是segments来进行操作和虚拟地址空间的分配。通过虚拟地址空间映射到物理地址空间。而这些空间最终运行的地方都是“内存”。所以就能推测出。这里所描述的 stack space、stack address ,也就是像汇编语言、C语言以及操作系统这一类翻译教材上所说的“堆栈”,往回追溯的话它就是上图中的“stack”。

从上面的内容中可以看到对于Intel官方给出的IA-32 Architectures的针对stack的操作实际上就是我们常说的“堆栈”的概念。

紧接着,再去找两本英文原版的数据结构上去看一看,stack究竟是不是数据结构中的栈。

第一本是《DATA STURCTURES and ALGORITHMS in C++》的第4版。在如下目录中就可以看到:

image-20220701061948731.png 第二本是《A Practical Introduction to Data Structures and Algorithm Analysis Third Edition (C++ Version)》

image-20220701062148572.png 从上面两本书对于Stack的描述就能够说明,在数据结构中,同样存在Stack、Stacks,从这就能够明确,栈是数据结构中的栈。

到这里,基本上就能够对于堆栈、栈的概念有非常清晰的定位和区分。在英特尔32位微处理器的体系架构、操作系统中内存操作,汇编语言利用堆栈传递参数等等这种基于内存的说明的stack是指堆栈。在内存中强调的是基于内存的堆栈结构对于内存的使用和分配方式。

在数据结构中描述的数据stack,也就是栈,它是和散列表、队列等常常凑在一起比较的一种的存储数据的方式或者说是设计思路。在数据结构中强调的是数据的排列方式对于存取等操作的效率的影响。

上面的内容整体描述的内容只是堆栈的概念层面的说明,也就是说通过堆栈和栈的描述,以及而这的对照对比,明确说明了,堆栈“是什么”的问题。

用途

我们经常看到关于栈和队列的数据结构的说明。那么针对内存上的堆栈呢?它有什么用呢?在计算机从插上电源的那一刻起,堆栈参与了具体的哪些工作呢?如果这类问题不知道,可能会在多地方又会遇到令人苦恼的障碍。

假设当你在看在阅读学习汇编指令的时候看到pop和push的时候,如果不自觉中你提出了一个这样的一个疑问:”pop和push,出栈和压栈的栈究竟在哪儿?“,那么你能回答自己的问题吗?如果你不知道它是什么的情况下,那何谈做到跟踪数据和正确的获得数据。

在计算机插上电以后基本上会在以下方面有”堆栈“的身影。如图:

image-20220701070502408.png

①开机初始化过程中用到的堆栈

②fork分叉出新的进程后的任务堆栈

扩展

这里的fork是内核代码中的fork对系统调用函数的调用来创建新的进程或者说是任务。其实这里你去查fork的英文含义的时候,你会发现它其实是”分叉、叉子“的意思。其实这样更形象。它是在第0个进程的基础上长出来的分支进程。是对0进程的copy,如下:

image-20220701071735315.png 这个暂时不拓展了。

在fork出的任务中,它对应的有:

  • 内核态堆栈
  • 用户态堆栈

暂且为了简单理解可以理解为,在每个任务创建的时候,为它分配的一块内存空间中,在其内存区域的末端。堆栈指针指向它,用来处理有关堆栈的业务。