1.2 程序的开发与运行
现代通用计算机都采用“存储程序”工作方式，需要计算机完成的任何任务都应先表示为一个程序。首先，应将应用问题（任务）转化为算法（algorithm）描述，使得应用问题的求解变成流程化的清晰步骤，并能确保步骤是有限的。任何一个问题可能有多个求解算法，需要进行算法分析以确定哪种算法在时间和空间上能够得到优化。其次，将算法转换为用编程语言描述的程序，这个转换通常是手工进行的，也就是说，需要程序员进行程序设计。程序设计语言（programming language）与自然语言不同，它有严格的执行顺序，不存在二义性，能够唯一地确定计算机执行指令的顺序。
1.2.1 程序设计语言和翻译程序
程序设计语言可以分成各类不同抽象层的、适用于不同领域的、采用不同描述结构的，等等。目前大约有上千种。从抽象层次上来分，可以分成高级语言和低级语言两类。
使用特定计算机规定的指令格式而形成的0/1序列称为机器语言，计算机能理解和执行的程序称为机器代码或机器语言程序，其中的每条指令都由0和1组成，称为机器指令。如图1.3中所示，主存单元0～4中存放的0/1序列就是机器指令。
最早人们采用机器语言编写程序。但机器语言程序的可读性很差，也不易记忆，给程序员的编写和阅读带来极大的困难。因此，人们引入了一种机器语言的符号表示语言，通过用简短的英文符号和机器指令建立对应关系，以方便程序员编写和阅读程序。这种语言称为汇编语言（assembly language），机器指令对应的符号表示称为汇编指令。如图1.3中所示，机器指令“1110 0110”对应的汇编指令为“load r0, 6#”。显然，使用汇编指令编写程序比使用机器指令编写程序要方便得多。但是，因为计算机只能执行用0和1表示的机器指令，而无法理解和执行汇编指令，因而用汇编语言编写的汇编语言源程序必须先转换为机器语言程序，才能被计算机执行。
每条汇编指令表示的功能与其对应的机器指令的功能是一样的，汇编指令和机器指令都与特定的机器结构相关，因此，汇编语言和机器语言都属于低级语言，它们统称为机器级语言。
因为指令描述的是最基本的原子操作，其功能非常简单，所以使用机器级语言描述程序功能时，需描述的细节很多，不仅程序设计工作效率很低，而且同一个程序不能在不同结构的机器上运行。为此，程序员多采用高级程序设计语言编写程序。
高级程序设计语言（High Level Programming Language）简称高级编程语言，是指面向算法设计的、较接近于日常英语书面语言的程序设计语言，如BASIC、C/C++、Fortran、Java、Python等。这些高级编程语言与具体的机器结构无关，可读性比机器级语言好，描述能力更强，一条语句可对应几条或几十条指令。例如，对于图1.3中所示的程序，机器级语言表示需5条指令，而用高级编程语言表示只需一条赋值语句“z=x+y;”即可。
不过，因为计算机无法直接理解和执行高级编程语言程序，因而需要将高级语言程序转换成机器语言程序。这个转换过程是由计算机执行相应的转换程序而自动完成的，进行这种转换的软件统称为翻译程序（translator）。通常，程序员借助软件开发工具软件来开发软件，各种软件开发工具软件统称为程序设计语言处理系统。
在任何一个语言处理系统中，都包含翻译程序，它能把一种编程语言表示的程序转换为等价的另一种编程语言程序。被翻译的语言和程序分别称为源语言和源程序，翻译生成的语言和程序分别称为目标语言和目标程序。通常，翻译程序有以下三类。
1）汇编程序（assembler）：也称汇编器，实现将汇编语言源程序翻译成机器语言目标程序。
2）解释程序（interpreter）：也称解释器，实现将源程序中的语句按其执行顺序逐条翻译成机器指令并立即执行。
3）编译程序（compiler）：也称编译器，实现将高级语言源程序翻译成汇编语言或机器语言目标程序。
图1.6给出了实现两个相邻数组元素交换功能的不同层次语言之间的等价转换过程。
图1.6 不同层次语言之间的等价转换过程
如图1.6所示，交换数组元素v[k]和v[k+1]的功能可以在高级语言源程序（如C语言程序）中直观地用三条赋值语句实现。编译程序将对应的高级语言源程序翻译为汇编语言程序后，三条赋值语句被转换为汇编语言程序中的4条汇编指令，其中两条是取数指令lw(load word)，另外两条是存数指令sw(store word)。因为计算机无法直接执行汇编语言程序，因此，还需要通过汇编程序将汇编语言源程序中的4条汇编指令翻译成机器语言目标程序中的机器指令。
在机器语言程序中，对应的机器指令是特定格式的二进制代码，例如，第一条lw指令对应的机器代码为“1000 1100 0100 1111 0000 0000 0000 0000”，这是一条MIPS指令集系统结构中的指令，其中，高6位“100011”为操作码，随后5位“00010”为通用寄存器编号2，再后面5位“01111”为另一个通用寄存器编号15，最后16位为立即数0。如前所述，计算机能够通过CPU中的控制部件直接控制执行这种二进制表示的机器指令。指令执行时通过控制部件将指令操作码进行译码，以解释成控制信号来控制数据的流动和运算，例如，控制信号ALUop=add可以控制ALU进行加法操作，RegWr=1可以控制将结果数据写入某个通用寄存器中。
小贴士
本书中多处提到MIPS架构或MIPS指令集系统结构，这里的MIPS是指在20世纪80年代初期由斯坦福大学Hennessy教授领导的研究小组研制出来的一种RISC处理器。MIPS来源于“Microcomputer without Interlocked Pipeline Stages”的缩写。在通用计算方面，MIPS R系列微处理器曾经用于构建高性能工作站、服务器和超级计算机系统。在嵌入式方面，MIPS K系列微处理器也曾经是占有量仅次于ARM的处理器之一（1999年以前MIPS是世界上用得最多的处理器），其应用领域覆盖游戏机、路由器、激光打印机、掌上电脑等各个方面。我国自主研制的龙芯CPU芯片的指令集系统结构最早是与MIPS架构兼容的，而与ARM和Intel x86指令系统结构互不兼容。
历史上还曾用MIPS（Million Instructions Per Second）作为指令执行速度所用的计量单位，其含义是平均每秒钟执行多少百万条指令。
因此，请注意MIPS这个缩写具有两个不同的内涵，应根据上下文进行区别。
1.2.2 从源程序到可执行文件
程序的开发和运行涉及计算机系统的各个不同层面，因而计算机系统层次结构的思想体现在程序开发和运行的各个环节。下面以简单的hello程序为例，简要介绍程序的开发与执行过程，以便加深大家对计算机系统层次结构概念的认识。
以下是“hello.c”的C语言源程序代码。
为了让计算机能执行上述应用程序，程序员应按照以下步骤进行处理。
1）通过程序编辑软件得到hello.c文件。hello.c在计算机中以ASCII字符方式存放，如图1.7所示，图中给出了每个字符对应的ASCII码的十进制值，例如，第一个字节的值是35，代表字符“#”；第二个字节的值是105，代表字符“i”，最后一个字节的值为125，代表字符“}”。通常把用ASCII码字符或汉字字符表示的文件称为文本文件（text file），源程序文件都是文本文件，是可显示和可读的。
图1.7 hello.c源程序文件的表示
2）将hello.c进行预处理、编译、汇编和链接，最终生成可执行目标文件。例如，在UNIX系统中，可用GCC编译驱动程序进行处理，命令如下：
上述命令中，最前面的unix＞为shell命令行解释器的命令行提示符，gcc为GCC编译驱动程序名，-o表示后面为输出文件名，hello.c为要处理的源程序。从hello.c到可执行目标文件hello的转换过程如图1.8所示。
图1.8 从hello.c到可执行目标文件hello的转换过程
● 预处理程序：预处理程序（cpp）对源程序中以字符#开头的命令进行处理，例如，将#include命令后面的.h文件内容嵌入到源程序文件中。预处理程序的输出结果还是一个源程序文件，以.i为扩展名。
● 编译程序：编译程序（cc1）对预处理后的源程序进行编译，生成一个汇编语言源程序文件，以.s为扩展名，例如，hello.s是一个汇编语言程序文件。因为汇编语言与具体的机器结构有关，所以，对同一台机器来说，不管什么高级语言，编译转换后的输出结果都是同一种机器语言对应的汇编语言源程序。
● 汇编程序：汇编程序（as）对汇编语言源程序进行汇编，生成一个可重定位目标文件（relocatable object file），以.o为扩展名，例如，hello.o是一个可重定位目标文件。它是一种二进制文件（binary file），因为其中的代码已经是机器指令，数据以及其他信息也都是用二进制表示的，所以它是不可读的，也即打开显示出来的是乱码。
● 链接程序：链接程序（ld）将多个可重定位目标文件和标准函数库中的可重定位目标文件合并成为一个可执行目标文件（executable object file），可执行目标文件简称为可执行文件。本例中，链接器将hello.o和标准库函数printf对应的可重定位目标模块printf.o进行合并，生成可执行文件hello。
最终生成的可执行文件被保存在硬盘上，可通过某种方式启动运行。
1.2.3 可执行文件的启动和执行
对于一个存放在硬盘上的可执行文件，可以在操作系统提供的用户操作环境中采用双击对应图标或在命令行中输入可执行文件名等多种方式来启动执行。在UNIX系统中，可以通过shell命令行解释器来执行一个可执行文件。例如，对于上述可执行文件hello，通过shell命令行解释器启动执行的结果如下：
shell命令行解释器会显示提示符unix＞，告知用户它准备接收用户的输入，此时，用户可以在提示符后面输入需要执行的命令名，它可以是一个可执行文件在硬盘上的路径名，例如，上述“./hello”就是可执行文件hello的路径名，其中“./”表示当前目录。在命令后用户需按下[Enter]键表示结束。图1.9显示了在计算机中执行hello程序的整个过程。
图1.9 启动和执行hello程序的整个过程
如图1.9所示，shell程序会将用户从键盘输入的每个字符逐一读入CPU寄存器中（对应线①），然后再保存到主存储器中，在主存的缓冲区形成字符串“./hello”（对应线②）。等接收到[Enter]按键时，shell将调出操作系统内核中相应的服务例程，由内核来加载硬盘上的可执行文件hello到存储器（对应线③）。内核加载完可执行文件中的代码及其所要处理的数据（这里是字符串“hello, world\n”）后，将hello第一条指令的地址送到程序计数器（PC）中，CPU永远都是将PC的内容作为将要执行的指令的地址，因此，处理器随后开始执行hello程序，它将加载到主存的字符串“hello, world\n”中的每一个字符从主存取到CPU的寄存器中（对应线④），然后将CPU寄存器中的字符送到显示器上显示出来（对应线⑤）。
从上述过程可以看出，一个用户程序被启动执行，必须依靠操作系统的支持，包括提供人机接口环境（如外壳程序）和内核服务例程。例如，shell命令行解释器是操作系统外壳程序，它为用户提供了一个启动程序执行的环境，用来对用户从键盘输入的命令进行解释，并调出操作系统内核来加载用户程序（用户从键盘输入的命令所对应的程序）。显然，用来加载用户程序并使其从第一条指令开始执行的操作系统内核服务例程也是必不可少的。
此外，在上述过程中，还涉及键盘、磁盘和显示器等外部设备的操作，这些底层硬件是不能由用户程序直接访问的，此时，也需要依靠操作系统内核服务例程的支持，例如，用户程序需要调用内核的read系统调用服务例程来读取磁盘文件，或调用内核的write系统调用服务例程把字符串“写”到显示器上等。
键盘和显示器等外部设备简称为外设，也称为I/O设备，其中，I/O是输入/输出（Input/Output）的缩写。外设通常由机械部分和电子部分组成，并且两部分通常是可以分开的。机械部分是外部设备本身，而电子部分则是控制外部设备工作的I/O控制器或I/O适配器。外设通过I/O控制器或I/O适配器连接到主机上，I/O控制器或I/O适配器统称为设备控制器。例如，键盘接口、打印机适配器、显示控制卡（简称显卡）、网络控制卡（简称网卡）等都是设备控制器，属于I/O模块。
从图1.9可以看出，程序的执行过程就是数据在CPU、主存储器和I/O模块之间流动的过程，所有数据的流动都是通过总线、I/O桥接器等进行的。数据在总线上传输之前，需要先缓存在存储部件中，因此，除了主存本身是存储部件以外，在CPU、I/O桥接器、设备控制器中也有存放数据的缓冲存储部件，例如，CPU中的通用寄存器、设备控制器中的数据缓冲寄存器等。