计算机系统I第10章详解.pptx

计算机系统 I 第十章：栈 Problem Specification Algorithm Program ISA (Instruction Set Architecture) microArchitecture Logic Transistors Physics/Chemistry compute the fibonacci sequence for(i=2; i100; i++) { a[i] = a[i-1]+a[i-2];} load r1, a[i]; add r2, r2, r1; 计算机系统的抽象层次 C/C++编译的程序中两个重要的内存区域： 栈区（stack）— 由编译器自动分配释放 ，存放函数的参数名，局部变量的名等。 堆区（heap）— 由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收。 Stack(栈): 由系统自动分配：int b; //系统自动在栈中为b开辟空间 Heap（堆）:需要程序员自己申请，并指明大小 p1 = (char *)malloc(10); //C p2 = new char[10]; //C++ p1, p2本身在栈中，分配的空间在堆中。 高级语言C/C++的内存管理 栈是一种存储机制，具有特有的访问规则 栈的重要作用： 中断驱动I/O 算数运算机制：基于栈的算术运算，用栈来存储中间结果，取代寄存器 数据类型转换：二进制补码与ASCII字符串之间的转换算法 后续数据结构和操作系统课程还会深入学习 栈: 一种抽象数据类型 定义：栈是一种具有LIFO (last-in first-out: 后进先出)访问特性的存储结构 第一个放进去的，最后一个取出来 最后一个放进去的，第一个取出来 因而栈特殊的地方在于它的访问方式，而不是它的实现。 栈的两个主要操作： PUSH（压入）: 在栈中插入一个元素 POP（弹出）: 在栈中删除一个元素 栈的基本结构 汽车上的硬币盒 弹出来的第一个硬币是最后进去的。 栈的实例-1 1995 1996 1998 1982 1995 1998 1982 1995 初始状态 压入一个硬币 再压入三个硬币 弹出一个硬币 硬件栈：在寄存器间移动数据 每压入或一个栈元素，栈中所有元素都将一起‘移动’ 栈的访问总是针对第一个元素，该寄存器标识为‘TOP’ 栈的实例-2 / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / Yes 空标志: TOP #18 / / / / / / / / / / / / / / / / / / / / / / / / No 空标志: TOP #12 #5 #31 #18 / / / / / / No 空标志: TOP #31 #18 / / / / / / / / / / / / / / / / / / No 空标志: TOP 初始状态 压入一次后 再压入三次后 弹出两次后 栈向下生长，数据在内存单元之间不需要移动 通过修改栈指针（TOP），使得总是指向最近压入的数据 在内存中的实现：软件机制 / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / TOP / / / / / / / / / / / / / / / / / / #18 / / / / / / TOP #31 #18 / / / / / / / / / / / / #5 #31 #18 / / / / / / 初始状态 压入一次后 压入两次后 压入三次后 x4000 x3FFF x3FFE x3FFD R6 R6 R6 R6 假定用R6寄存器保存TOP指针 TOP TOP / / / / / / / / / / / / TOP=x4000 TOP=TOP-1 M[TOP]=#18 TOP=TOP-1 M[TOP]=#31 TOP=TOP-1 M[TOP]=#5 弹出过程 在内存中的实现：软件机制 / / / / / / #5 #31 #18 / / / / / / / / / / / / #5 #31 #18 / / / / / / #31 #18 / / / / / / / / / / / / #5 #23 #18 / / / / / / 初始状态 弹出一次后 弹出两次后 再压入一次 x3FFD x3FFE x3FFF x3FFE R6 R6 R6 R6 假定用R6寄存器保存TOP指针，R0保存读出数据 TOP #5 / / / / / / TOP=x3FFD R0=M[TOP]=31 TOP=TOP+1 R6=X3FFF TOP=TOP-1 R6=X3FFE M[TOP]=#23 TOP TOP R