计算机系统基础(一):程序的表示、转换与链接笔记 第一周

用”系统思维”分析问题:C语言程序举例

// 在ISO C90标准,32位系统上
-2147483648 < 2147483647 // false,与事实不符
int i = -2147483648;
i < 2147483647 // true
-2147483647-1 < 2147483647 // true

要理解这个问题,必须知道:
①编译器如何处理字面量
②高级语言中运算规则
③高级语言与指令之间的对应关系
④机器指令的执行过程
⑤机器级数据的表示和运算

int sum(int a[], unsigned len)
{
int i, sum = 0;
for (i=0; i<=len-1; i++)
sum += a[i];
return sum;
}
// 当len=0时,调用sum函数,报错Segmentation fault
// 当len为int型时正常

要理解这个问题,必须知道:
①高级语言中运算规则:当又有unsigned,又有int时是如何处理的
②机器指令的含义和执行
③计算机内部的运算电路
④异常的检测和处理
⑤虚拟地址空间

// 若x和y为int型,当x=65535时,y=x*x; y的值为多少?
#include <stdio.h>
int main(int argc, char const *argv[])
{
int x = 65535;
int y = x*x;
printf("%d", y); // 输出-131071
return 0;
}
// 对于任何int型变量x和y,(x>y)==(-x<-y)总成立吗?
// 当x=-2147483648,y任意(除-2147483648外)时不成立
#include <stdio.h>
int main(int argc, char const *argv[])
{
int x = -2147483648;
int y = 0;
printf("%d", (x>y)==(-x<-y)); // 0
return 0;
}

要理解这个问题,必须知道:
①机器级数据的表示
②机器指令的执行
③计算机内部的运算电路

// main.c
int d = 100;
int x = 200;
int main(int argc, char const *argv[])
{
p1();
printf("d=%d, x=%d\n", d, x); // d=0, x=1072693248
return 0;
}
// p1.c
double d;
void p1()
{
d = 1.0;
}

要理解这个问题,必须知道:
①机器级数据的表示
②变量的存储空间分配
③数据的大端/小端储存方式
④链接器的符号解析规则

int copy_array(int* array, int count) {
int i;
int* myarray = (int*)malloc(count*sizeof(int));
if (myarray == NULL)
return -1;
for (i=0; i<count; i++)
myarray[i] = array[i];
return count;
}
// 当参数count很大时,count*sizeof(int)会溢出。
// 如count=2^30+1时,count*sizeof(int)=4。而使得堆中大量数据被破坏。

要理解这个问题,必须知道:
①乘法运算及溢出
②虚拟地址空间
③存储空间映射

int a = 0x80000000;
int b = a/-1;
printf("%d", b);
// 运行结果:-2147483648
// *注:在LLVM version 9.0.0 (clang-900.0.39.2)运行结果为Floating point exception
int a = 0x80000000;
int b = -1;
int c = a/b;
printf("%d", c);
// Floating point exception

反汇编得知,第一段代码异常是因为除以-1被优化成取负指令neg,故未发生除法溢出。第二段代码因为a/b只能用带符号的除法指令IDIV实现,而这个除法指令是不能生产OF(溢出)标志的。能够判断出溢出异常实际上是因为在做除法计算是会对被除数和除数进行判断,这段代码里对是“除法错”异常#DE(类型0)发出的SIGFPE信号。

要理解这个问题,必须知道:
①编译器如何优化
②机器级数据的表示
③机器指令的含义和执行
④计算机内部的运算电路
⑤除法错异常的处理

#include <stdio.h>
int main(int argc, char const *argv[])
{
double a = 10;
printf("a=%d", a);
return 0;
}
// 在IA-32上运行时,打印结果为a=0
// 在x86-64上运行,打印出来的a是一个不确定值
// *注:warning: format specifies type 'int' but the argument has type 'double'

要理解这个问题,必须知道:
①IEEE 754的表示
②X87 FPU的体系结构
③IA-32和x86-64中过程调用的参数传递
④计算机内部的运算电路

double fun(int i)
{
volatile double d[1] = {3.14};
volatile long int a[2];
a[i] = 1073741824;
return d[0];
}
/* 后面的部分为LLVM version 9.0.0 (clang-900.0.39.2)运行结果
fun(0): 3.14 // 3.14
fun(1): 3.14 // 3.14
fun(2): 3.1399998664856 // 0.00
fun(3): 2.00000061035156 // Abort trap
fun(4): 3.14, 然后存储保护错 // Abort trap
*/

要理解这个问题,必须知道:
①机器级数据的表示
②过程调用机制
③栈帧中数据的布局

// 行优先复制
void copyij (int src[2048][2048], int dst[2048][2048])
{
int i, j;
for (i=0; i<2048; i++)
for (j=0; j<2048; j++)
dst[i][j] = src[i][j];
}
// 列优先复制
void copyij (int src[2048][2048], int dst[2048][2048])
{
int i, j;
for (j=0; j<2048; j++)
for (i=0; i<2048; i++)
dst[i][j] = src[i][j];
}
// 上面两个程序功能完全一样,算法完全一样,时间和空间复杂度完全一样,但执行时间行优先比列优先快21倍

要理解这个问题,必须知道:
①数组的存放方式
②Cache机制
③访问局限性

#include <stdio.h>
int main(int argc, char const *argv[])
{
int a = 10;
double* p = (double*) &a;
printf("%f\n", *p);
printf("%f\n", (double)a);
return 0;
}
// -124611659368806372889759754720407547307460851250672333601793485342599952830680188745055200175431562344736125964380568777588649699734133946133318828765925290491625969102012218896410637436116313047040.000000
// 10.000000

这两条打印语句在汇编代码中是fldl和fildl指令的差别。i的意思是先作为int,强制转换为double再打印,没有i则直接把0/1序列当做double打印。

要理解这个问题,必须知道:
①数据的表示
②编译(程序的转换)
③局部变量在栈中的位置

计算机系统

计算机系统的抽象层的转换

应用(问题)->算法->编程(语言)->操作系统/虚拟机->指令集体系结构(ISA)->微体系结构->功能部件->电路->器件

程序执行结果不仅取决于算法、程序编写,而且取决于语言处理系统、操作系统、ISA、微体系结构。

第一台通用计算机ENIAC(Electronic Numberical Integrator And Computer)是1946年由美国宾夕法尼亚大学研制,由电子真空管组成,用于二战时期解决复杂弹道计算问题,运行速度5000次加法/s,可以计算平方、立方、sin、cos等,用十进制表示信息并运算,采用手动编程,通过设置开关和插拔电缆来实现。

冯诺依曼于1944年被邀请加入ENIAC团队。1945年,他在共同讨论基础上,以“关于EDVAC的报告草案”为题,发表了全新的“存储程序通用电子计算机方案”,普林斯顿高等研究院一句这份报告批准冯诺依曼建造计算机。

1946年,普林斯顿高等研究院(IAS)开始设计“存储程序”计算机,他们设计的在1051年完成,被称为IAS计算机。(第一台存储程序计算机EDSAC在1949年由英国剑桥大学完成。)

那份报告中提出的计算机结构,被称为“冯诺依曼结构”,其中最重要的思想是“储存程序(Stored-program)”。它的工作方式是:任何计算机要完成的工作都要先被编写成程序,然后将程序和原始数据送入主存并启动执行。一旦程序被启动,计算机应能在不许操作人员干预的情况下,自动完成逐条取出指令和执行指令的任务。早期,部件之间用分散方式相连,现在大多用总线方式。

冯诺依曼结构的主要思想

  1. 计算机应由运算器、控制器、储存器、输入设备和输出设备五个基本部件组成。
  2. 各部件的功能是:
    • 存储器不仅能存放数据,而且也能存放指令,形式上两者没有区别,但计算机应能区分数据还是指令。
    • 控制器应能自动取出指令来执行。
    • 运算器应能进行加、减、乘、除四种基本算术运算,并且也能进行一些逻辑运算和附加运算;
    • 操作人员可以通过输入设备、输出设备和主机进行通信。
  3. 内部以二进制表示指令和数据。每条指令由操作码和地址码两部分组成。操作码指出操作类型,地址码指出操作数的地址。由一串指令组成程序。
  4. 采用“存储程序”工作方式。

计算机是如何工作的

程序在执行前:数据和指令先存放在存储器中,每条指令和每个数据都有地址,指令按序存放,指令由OP、ADDR字段组成,程序起始地址置PC。
开始执行程序:根据PC取指令->指令译码->取操作数->指令执行->回写结果->修改PC的值->继续执行下一条指令。

程序开发和执行过程

汇编语言由汇编指令构成,用助记符和标号来表示指令(与机器指令一一对应)。
指令包含操作码和操作数(或其地址码),其中机器指令用二进制表示,汇编指令用符号表示。指令只能描述①取(或存一个数);②两个数的计算(加减乘除即逻辑与、或等);③根据运算结果判断是否转移执行。

高级语言具有以下特点:
①与具体机器结构无关;
②面向算法编程,比机器语言的描述能力强的多;
③高级语言中的一条语句可以对应几条,甚至几百条指令;
④有“面向过程”和“面向对象”的语言之分;
⑤处理逻辑分为三种结构:顺序结构、选择结构、循环结构;
⑥有两种转换方式:“编译”和“解释”。“编译程序”(Complier):将高级语言源程序转换为机器级目标程序,执行时只要启动目标程序即可。“解释程序”(Interpreter):将高级语言语句逐条翻译成机器指令并立即执行,不生成目标文件。

GCC + Linux平台中的处理流程:
hello.c(源程序)经过预处理变为hello.i,再经过编译为hello.s(汇编语言程序),再经过汇编为hello.o(二进制的可重定位目标程序),与其他目标程序进行链接形成hello(二进制的可执行目标程序)。

最早的程序开发是直接输入指令和数据,启动后把第一条指令地址送PC开始执行。

高级语言开发程序需要更复杂的支持环境,包括①编辑器编写源程序;②一套翻译转换软件处理各种源程序(编译方式:预处理程序、编译器、汇编器、链接器;解释方式:解释程序);③一个可执行程序界面,包括GUI(图形界面)、CUI(命令行界面)。

支撑程序开发和运行的环境由系统软件提供,最重要的系统软件是操作系统和语言处理系统。语言处理系统运行在操作系统之上,操作系统利用指令管理硬件。

计算机系统层次结构

①第一代程序设计语言:机器语言。应用程序->指令集体系结构->计算机硬件
②第二代程序设计语言:汇编语言。应用程序->汇编程序->操作系统->指令集体系结构->计算机硬件
③第三代程序设计语言:过程式语言,编码时需要描述实现过程。应用程序->语言处理系统->操作系统->指令集体系结构->计算机硬件
④第四代程序设计语言:非过程化语言,编码时只需要说明“做什么”,不需要描述具体的算法实现细节

语言处理系统包括:各种语言处理程序(如编译、汇编、链接)、运行时的系统(如库函数、调试、优化等功能)
操作系统包括人机交互界面、提供服务功能的内核例程。

计算机系统的不同用户:
①最终用户:工作由应用程序提供的最上面的抽象层
②系统管理员:工作在由操作系统提供的抽象层
③应用程序员:工作在由语言处理系统(主要有编译器和汇编器)的抽象层
④系统程序员(实现系统软件):工作在ISA层次,必须对ISA非常了解

编译器和汇编器的目标程序有机器级代码组成,操作系统通过指令直接对硬件进行编程控制。

指令集体系结构(ISA)

ISA处于软件和硬件的交界面,是两者的接口,它规定了如何使用硬件。
①可执行的指令集合包括指令格式、操作种类以及每种操作对应的操作数的相应规定;
②指令可以接受的操作数类型;
③操作数所能存放的寄存器组的结构,包括每个寄存器的名称、编号、长度和用途;
④操作数所能存放的存储空间的大小和编址方式;
⑤操作数在存储空间存放时按照大端还是小端的方式存放;
⑥指令获取操作数的方式,即寻址方式;
⑦指令执行过程中的控制方式,包括程序计数器(PC)、条件码定义等。

不同的ISA规定的指令集不同,如IA-32、MIPS、ARM等。计算机组成必须能够实现ISA规定的功能,如提供GPRs(通用寄存器组)、标志、运算电路等。同一种ISA可以由不同的计算机组成,如乘法指令可用ALU(算术逻辑部件)或乘法器实现。