第二章 计算机的语言

1、Chapter 2Chapter 2指令: 计算机的语言Chapter 2 Instructions: Language of the Computer 2指令集指令集n一台计算机的全部指令n不同计算机有不同的指令集n但有许多共同的方面n早期计算机有很简单的指令集n实现简单n许多现代计算机也有简单指令集n例如：ARM系列计算机（RSIC）2.1 IntroductionChapter 2 Instructions: Language of the Computer 3MIPS指令集指令集n用于编写书中的例子使用的是MIPS语言n斯坦福大学的MIPS来自MIPS公司 ()n在嵌入式处理机市场中占

2、有很大的份额n广泛地应用在家用电器、网络/存储设备，照相机，打印机n许多现代指令集的代表n参见MIPS参考数据卡和附录B和E。Chapter 2 Instructions: Language of the Computer 4算术运算操作算术运算操作n加法和减法，都是三操作数n两个源操作数，一个目的操作数add a, b, c # a = b + cn注释用#开头n所有的算术运算都是这样的形式n设计原则一：简单源于规整规整n规整使实现简单n简单能获得低成本高性能2.2 Operations of the Computer HardwareChapter 2 Instructions: Lang

3、uage of the Computer 5算术操作例子算术操作例子nC 语言的语句:f = (g + h) - (i + j);n编译成MIPS代码:add t0, g, h #临时变量临时变量t0 = g + hadd t1, i, j #临时变量临时变量t1 = i + jsub f, t0, t1 # f = t0 - t1Chapter 2 Instructions: Language of the Computer 6寄存器操作数寄存器操作数n算术运算指令使用寄存器操作nMIPS有32个32位 寄存器n用于存储频繁使用的数据n编号0 到31n32位数码称为一个字n编译时名称的约定n

4、$t0, $t1, , $t9 表示临时寄存器临时寄存器n$s0, $s1, , $s7 用于存储变量n设计原则二：越少越快越少越快n对照主存：数以百万计的存储位置2.3 Operands of the Computer HardwareChapter 2 Instructions: Language of the Computer 7寄存器操作数举例寄存器操作数举例nC 语言编写的代码:f = (g + h) - (i + j);nf, , j in $s0, , $s4n编译成MIPS代码:add $t0, $s1, $s2add $t1, $s3, $s4sub $s0, $t0, $t

5、1Chapter 2 Instructions: Language of the Computer 8存储器操作数存储器操作数n主存可以存储复杂数据n数组，结构，动态数据n使用算术运算操作数n从主存把数读入到寄存器n把结果从寄存器存储到主存n存储器按字节编址n每个地址表示一个8位字节n按字存放在内存n每个地址必须是4个字节nMIPS按大端编址n高位存放在低地址n对照小端模式：低位放到低地址地址偏移大端模式小端模式0 x0012（OP0）34（OP1）0 x0134（OP1）12（OP0）如果将一个16位的整数0 x1234存放到一个短整型变量（short）中。这个短整型变量在内存中的存储在大小

6、端模式由下表所示。Chapter 2 Instructions: Language of the Computer 9存储器操作数举例存储器操作数举例1nC code:g = h + A8;ng 在 $s1, h 在 $s2, A的基址在 $s3n编译成MIPS代码:n小标8（数组第8个分量）需要32的偏移n每个字对应4个字节lw $t0, 32($s3) # load wordadd $s1, $s2, $t0偏移量offset基址寄存器Base register Chapter 2 Instructions: Language of the Computer 10存储器操作数举例存储器操作

7、数举例2nC code:A12 = h + A8;nh in $s2, base address of A in $s3nCompiled MIPS code:nIndex 8 requires offset of 32lw $t0, 32($s3) # load wordadd $t0, $s2, $t0sw $t0, 48($s3) # store wordChapter 2 Instructions: Language of the Computer 11寄存器和主存储器寄存器和主存储器n寄存器的访问速度比主存快得多n对主存储器数据的操作要用n取数指令lw (load word)n存数指

8、令sw (store word)。n需要执行更多的指令n编译器必须尽量使用寄存器访问变量必须尽量使用寄存器访问变量n仅当寄存器不够用时才把不经常使用的变量放到内存；n寄存器的高效利用对系统优化非常重要。Chapter 2 Instructions: Language of the Computer 12常数或立即数操作数常数或立即数操作数n指令中使用常数addi $s3, $s3, 4（immediate）n没有减去立即数的减法指令n可以使用负常数，即“加负数”实现减法addi $s2, $s1, -1n设计规则三：加速执行常用操作n小常数操作出现的频率高n立即数操作不用到内存取数Chapte

9、r 2 Instructions: Language of the Computer 13常数零常数零nMIPS寄存器0（$zero）表示常数0n不能被改写n在常用的操作中，很有用n例如，可在寄存器之间传送数据add $t2, $s1, $zero常用的寻址方式常用的寻址方式n寄存器型：直接、间接；n存储器型：直接、间接；n计算型：相对、基址、变址；n立即数型；Chapter 2 Instructions: Language of the Computer 15二进制无符号整数二进制无符号整数n给定一个n位数00112n2n1n1n2x2x2x2xxn范围: 0 to +2n 1n举例n000

10、0 0000 0000 0000 0000 0000 0000 10112= 0 + + 123 + 022 +121 +120= 0 + + 8 + 0 + 2 + 1 = 1110n32位数n0 to +4,294,967,2952.4 Signed and Unsigned NumbersChapter 2 Instructions: Language of the Computer 16二进制补码表示有符号整数二进制补码表示有符号整数nx是一个n位数00112n2n1n1n2x2x2x2xxn范围: 2n 1 to +2n 1 1n举例n1111 1111 1111 1111 1111

11、 1111 1111 11002= 1231 + 1230 + + 122 +021 +020= 2,147,483,648 + 2,147,483,644 = 410n32位数n2,147,483,648 to +2,147,483,647Chapter 2 Instructions: Language of the Computer 17二进制补码表示有符号整数二进制补码表示有符号整数n31位是符号位n1表示负数n0表示非负n(2n 1) 不能表示n非负数的无符号数和二进制补码是相同的n一些特殊的数n 0: 0000 0000 0000n1: 1111 1111 1111n绝对值最大负数:

12、1000 0000 0000n最大正数:0111 1111 1111Chapter 2 Instructions: Language of the Computer 18有符号数（二进制补码）的取反有符号数（二进制补码）的取反n取反加1n取反的含义1 0, 0 1x1x11111.111xx2n举例：对+2的求反n+2 = 0000 0000 00102n2 = 1111 1111 11012 + 1 = 1111 1111 11102Chapter 2 Instructions: Language of the Computer 19符号扩展符号扩展n使用更多的位表示一个数n数值保持不变n在

13、MIPS指令集中naddi: extend immediate value扩展到立即数nlb, lh: extend loaded byte/halfword 扩展到取字节/半字nbeq, bne: 扩展到跳转后的位置extend the displacement 相等/不相等跳转n复制符号位到左侧n对照无符号数：用0扩充n举例: 8-bit to 16-bitn+2: 0000 0010 = 0000 0000 0000 0010n2: 1111 1110 = 1111 1111 1111 1110Chapter 2 Instructions: Language of the Compute

14、r 20指令表示指令表示n指令用二进制编码n称为机器代码nMIPS 指令n32位指令字编码n指令格式中若干字段分别用于表示操作码, 寄存器编号, n非常规整n寄存器编号【参考教材71页图2-14】n$t0 $t7 are regs 8 15n$t8 $t9 are regs 24 25n$s0 $s7 are regs 16 232.5 Representing Instructions in the Computer指令格式的演变指令格式的演变n肆地址指令；n三地址指令；n二地址指令；n一地址指令；n零地址指令。n地址的显式和隐含式Chapter 2 Instructions: Langua

15、ge of the Computer 22MIPS中寄存器指令中寄存器指令n指令字段nop: 操作码(opcode)nrs: 第一个源寄存器编号nrt: 第二个源寄存器编号nrd: 目的寄存器编号nshamt: 移位位数(00000 表示不移位) nfunct: 功能码（扩展操作码） (extends opcode)oprsrtrdshamtfunct6 bits6 bits5 bits5 bits5 bits5 bitsChapter 2 Instructions: Language of the Computer 23R-型（寄存器）操作举例型（寄存器）操作举例add $t0, $s1,

16、$s2special$s1$s2$t00add01718803200000010001100100100000000100000000000100011001001000000001000002 = 0232402016oprsrtrdshamtfunct6 bits6 bits5 bits5 bits5 bits5 bitsChapter 2 Instructions: Language of the Computer 24十六进制十六进制n基底是16n二进制串的压缩表示（使用16进制的原因）n四位二进制组成一个十六进制数000004010081000c1100100015010191001

17、d11012001060110a1010e11103001170111b1011f1111nExample: eca8 6420n1110 1100 1010 1000 0110 0100 0010 0000Chapter 2 Instructions: Language of the Computer 25MIPS I型（立即数指令）型（立即数指令）n立即数的算术和读数/存数指令nrt: 目的或源寄存器编号n常数的取值范围: 215 to +215 1n地址：偏移加上rs中的基址n设计原则4：优秀的设计需要适宜的折中方案n不同类型指令采用不同的解码方式，但都是32位相同的指令长度n尽可能保持

18、相似的指令格式oprsrtconstant or address6 bits5 bits5 bits16 bits指令格式举例指令格式举例1n如果数组A的基址放在$t1中，h存放在$s2中，这C语言写的语句：nA300=h+A300编译成汇编语言，则为：nlw $t0, 1200($t1) # $t0=A300nAdd $t0, $s2, $t0 # $t0=h+A300nSw $t0, 1200($t1) #把h+A300存到原来A300所在的单元。指令格式举例指令格式举例1-2oprsrtrdAddress/shamdfunct359812000188803243981200汇编语言编写的

19、程序汇编语言编写的程序：lw $t0, 1200($t1) Add $t0, $s2, $t0Sw $t0,1200($t1)变成机器语言变成机器语言，如下，如下：寄存器编号$t0 $t7 are regs 8 15$t8 $t9 are regs 24 25$s0 $s7 are regs 16 23指令格式举例指令格式举例1-3oprsrtrdAddress/shamdfunct359812000188803243981200存在存储器中的形式为上表的存在存储器中的形式为上表的2进制进制：oprsrtrdAddress/shamdfunct100011 01001010000000 010

20、0 1011 0000000000 100100100001000 00000100000101011 01001010000000 0100 1011 0000汇编语言编写的程序汇编语言编写的程序：lw $t0, 1200($t1) Add $t0, $s2, $t0Sw $t0,1200($t1)Chapter 2 Instructions: Language of the Computer 29存储程序存储程序n指令用二进制表示，像数一样n指令和数据存储在存储器中n程序可以被其他程序操作n例如，编译，连接，n“二进制兼容”可以让编译后的程序运行在不同的计算机上n标准的ISAs（软件编程的

21、标准）The BIG PictureThe BIG PictureChapter 2 Instructions: Language of the Computer 30逻辑操作逻辑操作n对位进行处理的指令逻辑操作CJavaMIPS左移srl按位与&and, andi按位或|or, ori按位取反norn用于对字中的若干 “位位” n打包和拆包的操作2.6 Logical OperationsChapter 2 Instructions: Language of the Computer 31移位操作移位操作nshamt: 移多少位n逻辑左移sllslln左移空位填0n逻辑左移i位相当于

22、乘2 2i in逻辑右移srln逻辑右移空位填0n逻辑右移i位相当于除2i（仅对无符号数）oprsrtrdshamtfunct6 bits6 bits5 bits5 bits5 bits5 bitsChapter 2 Instructions: Language of the Computer 32“与与”操作操作n可用于一个字中的掩码操作n选择某些位，其他位清零and $t0, $t1, $t20000 0000 0000 0000 0000 1101 1100 00000000 0000 0000 0000 0011 1100 0000 0000$t2$t10000 0000 0000 0

23、000 0000 1100 0000 0000$t0Chapter 2 Instructions: Language of the Computer 33“或或” 操作操作n用于把包含字中的一些位置1，其他位不变or $t0, $t1, $t20000 0000 0000 0000 0000 1101 1100 00000000 0000 0000 0000 0011 1100 0000 0000$t2$t10000 0000 0000 0000 0011 1101 1100 0000$t0Chapter 2 Instructions: Language of the Computer 34按

24、位按位“取反取反”操作操作n用于改变字中的一些位n0变成1,1变成0nMIPS 3-操作数指令NORna NOR b = NOT ( a OR b ) “或非”nor $t0, $t1, $zero0000 0000 0000 0000 0011 1100 0000 0000$t11111 1111 1111 1111 1100 0011 1111 1111$t0Register 0: always read as zeroChapter 2 Instructions: Language of the Computer 35决策指令决策指令n如果条件为真，跳转到被标签的指令执行n否则，继续执行

25、nbeq rs, rt, L1nif (rs = rt)转到标签为L1的指令执行nbne rs, rt, L1nif (rs != rt)转到标签为L1的指令执行;nj L1n无条件跳转到标签为L1的指令执行2.7 Instructions for Making DecisionsChapter 2 Instructions: Language of the Computer 36编译编译IF语句语句nC code:if (i=j) f = g+h; else f = g-h;nf, g, in $s0, $s1, n编译成MIPS 代码: bne $s3, $s4, Else add $s0

26、, $s1, $s2 j ExitElse: sub $s0, $s1, $s2Exit: Assembler calculates addressesChapter 2 Instructions: Language of the Computer 37编译循环语句编译循环语句nC code:while (savei = k) while (savei = k) i += 1; i += 1;ni in $s3, k in $s5, address of save in $s6nCompiled MIPS code:Loop: sll $t1, $s3, 2Loop: sll $t1, $s3

27、, 2 add $t1, $t1, $s6 add $t1, $t1, $s6 lw $t0, 0($t1) lw $t0, 0($t1) bne $t0, $s5, Exit bne $t0, $s5, Exit addi $s3, $s3, 1 addi $s3, $s3, 1 j Loop j LoopExit: Exit: Chapter 2 Instructions: Language of the Computer 38基本块基本块n一个基本块是一个指令序列，其中n内部没有跳出的指令（结束指令除外）n也没有被跳转到的指令（开始指令除外）n编译器标识基本快用于优化n高级处理机能够加速

28、基本块的执行Chapter 2 Instructions: Language of the Computer 39更多的条件操作更多的条件操作n如果条件为真置1，否则置0nslt rd, rs, rt；小于则置位nif (rs rt) rd = 1; else rd = 0;nslti rt, rs, constantnif (rs constant) rt = 1; else rt = 0;nbeq，bne可以和其他指令结合使用slt $t0, $s1, $s2 # if ($s1 $s2)$t0=1;bne $t0, $zero, L # $t0 not equal to zero bra

29、nch to LChapter 2 Instructions: Language of the Computer 40分支指令设计分支指令设计n为什么没有blt，bge等指令？n硬件执行, , 比=, 慢n指令中结合分支指令包含更多工作，需要更慢的时钟n所有指令都受到了影响nBeq和bne是较常用的n这是一个很好的设计折中方案Chapter 2 Instructions: Language of the Computer 41有符号有符号数和数和无符号数无符号数对比对比n有符号数比较: slt, sltin无符号数比较: sltu, sltuin举例n$s0 = 1111 1111 1111

30、1111 1111 1111 1111 1111n$s1 = 0000 0000 0000 0000 0000 0000 0000 0001nslt $t0, $s0, $s1 # signedn1 +1 $t0 = 0Chapter 2 Instructions: Language of the Computer 42过程调用过程调用n遵循步骤n将参数放在过程可以访问的寄存器里n将控制转移给过程n获得过程所需要的存储资源n执行过程的操作（请求的任务）n将结果的值放在调用程序可以访问到的寄存器1.将控制返回到调用点2.8 Supporting Procedures in Computer Ha

31、rdwareChapter 2 Instructions: Language of the Computer 43寄存器的使用寄存器的使用n$a0 $a3: 传递参数 (regs 4 7)n$v0, $v1: 返回结果值 (regs 2 and 3)n$t0 $t9: 临时寄存器n可以被调用者改写n$s0 $s7: 保存参数n必须被调用者保存和恢复n$gp: 静态数据的全局指针寄存器(reg 28)nglobal pointer for static data (reg 28)n$sp: 堆栈指针寄存器stack pointer (reg 29)n$fp: 帧指针寄存器(frame point

32、er) ，n 保存过程帧的第一个字 (reg 30)n$ra:返回地址寄存器 return address (reg 31)Chapter 2 Instructions: Language of the Computer 44过程调用指令过程调用指令n过程调用：跳转和链接jal ProcedureLabeln下一条指令的地址在寄存器$ra中n跳转到目标地址n过程返回:寄存器跳转 jump registerjr $ran拷贝$ra到程序计数器n也被用于运算后跳转n例如用于case/switcg分支语句e.gChapter 2 Instructions: Language of the Compu

33、ter 45不调用其他过程（叶过程）例子不调用其他过程（叶过程）例子nC code:int leaf_example (int g, h, i, j) int f; f = (g + h) - (i + j); return f;n参数 g, , j 在 $a0, , $a3中nf 在 $s0 (因此，需要存储$s0到堆栈)n结果在$v0Chapter 2 Instructions: Language of the Computer 46不调用其他过程的例子不调用其他过程的例子nMIPS code:leaf_example: addi $sp, $sp, -4 sw $s0, 0($sp) a

34、dd $t0, $a0, $a1 add $t1, $a2, $a3 sub $s0, $t0, $t1 add $v0, $s0, $zero lw $s0, 0($sp) addi $sp, $sp, 4 jr $ra存储 $s0 到堆栈i+j-t1 过程体(g + h) - (i + j)恢复 $s0结果 (s0-v0)返回参数 g, , j 在 $a0, , $a3中;f 在 $s0 (因此，需要存储$s0到堆栈);结果在$v0g+h-t0Chapter 2 Instructions: Language of the Computer 47嵌套过程嵌套过程非叶过程非叶过程( (Non-

35、LeafNon-Leaf Procedures) Procedures)n过程调用其他过程n对于嵌套调用，调用者需要存储到堆栈的信息:n它的返回地址n调用后还需要用的任何参数寄存器和临时寄存器n调用后返回，寄存器会从堆栈中恢复Chapter 2 Instructions: Language of the Computer 48嵌套过程举例嵌套过程举例 Non-Leaf Procedure ExampleNon-Leaf Procedure ExamplenC code:int fact (int n) if (n 1) return f; else return n * fact(n - 1)

36、;n参数n放在 $a0n结果放在 $v0Chapter 2 Instructions: Language of the Computer 49嵌套过程举例嵌套过程举例 Non-LeafNon-Leaf Procedure Example Procedure ExamplenMIPS code:fact: addi $sp, $sp, -8 # adjust stack for 2 items sw $ra, 4($sp) # save return address sw $a0, 0($sp) # save argument（存参数） slti $t0, $a0, 1 # test for n

37、 1 beq $t0, $zero, L1 addi $v0, $zero, 1 # if so, result is 1 addi $sp, $sp, 8 # pop 2 items from stack jr $ra # and returnL1: addi $a0, $a0, -1 # else decrement n jal fact # recursive call(递归调用) lw $a0, 0($sp) # restore original n lw $ra, 4($sp) # and return address addi $sp, $sp, 8 # pop 2 items f

38、rom stack mul $v0, $a0, $v0 # multiply to get result jr $ra # and returnChapter 2 Instructions: Language of the Computer 50堆栈中的局部数据堆栈中的局部数据 Local Data on the StackLocal Data on the Stackn局部数据有调用者分配ne.g., C 自动分配变量n过程帧（活动记录）n被一些编译器使用控制堆栈存储Chapter 2 Instructions: Language of the Computer 51内存布局内存布局Memo

39、ry Layoutn正文：程序代码n静态数据：全局变量ne.g., C语言静态变量，常数数组和字符串n$gp 初始化地址，允许段内的 偏移n动态数据：堆n堆栈：自动存储Chapter 2 Instructions: Language of the Computer 52字符数据字符数据 （包括汉字）（包括汉字）n字节编码的字符集nASCII: 128 个n95 graphic, 33 controlnLatin-1: 256 个nASCII, +96 more graphic charactersnUnicode: 32位字符集nUsed in Java, C+ wide characters

40、, n宽字符世界上大多数字母表nUTF-8, UTF-16: 可变长度编码2.9 Communicating with PeopleChapter 2 Instructions: Language of the Computer 53字节字节/ /半字操作半字操作 Byte/Halfword OperationsByte/Halfword Operationsn使用位操作nMIPS字节/半字 读取/存储 n字符串处理是较常用的方式lb rt, offset(rs) lh rt, offset(rs)nSign extend to 32 bits in rtlbu rt, offset(rs)

41、lhu rt, offset(rs)nZero extend to 32 bits in rtsb rt, offset(rs) sh rt, offset(rs)n存储恰恰是字节或半子的形式Chapter 2 Instructions: Language of the Computer 54字符串拷贝举例字符串拷贝举例 String Copy ExampleString Copy ExamplenC code (nave):n非终止字符串Null-terminated stringvoid strcpy (char x, char y) int i; i = 0; while (xi=yi)

42、!=0) i += 1; n假定x, y 基地址在 $a0, $a1中；ni 在 $s0 中。Chapter 2 Instructions: Language of the Computer 55字符串拷贝字符串拷贝String Copy ExamplenMIPS code:strcpy: addi $sp, $sp, -4 # 为保存i调整堆栈指针， sw $s0, 0($sp) # 把i送栈中【i在 $s0 中】 add $s0, $zero, $zero # 将i置“0”， 【i = 0+0】 L1: add $t1, $s0, $a1 # addr of yi in $t1 lbu $

43、t2, 0($t1) # $t2 = yi add $t3, $s0, $a0 # addr of xi in $t3 sb $t2, 0($t3) # xi = yi beq $t2, $zero, L2 # exit loop if yi = 0 addi $s0, $s0, 1 # i = i + 1 j L1 # next iteration of loopL2: lw $s0, 0($sp) # restore saved $s0 addi $sp, $sp, 4 # pop 1 item from stack jr $ra # and return假定x, y 基地址在 $a0,

44、$a1中, i 在 $s0 中Chapter 2 Instructions: Language of the Computer 560000 0000 0011 1101 0000 0000 0000 000032位常数位常数 32-bit Constantsn大部分常数都比较小，16位表示立即数足够了，偶尔使用32位常数。nlui rt, constantn取立即数并放到高16位lui $s0, 610000 0000 0111 1101 0000 1001 0000 0000ori $s0, $s0, 23042.10 MIPS Addressing for 32-Bit Immediat

45、es and AddressesOri立即数或， $s0与常数2304“或”，结果放在$s0形成一个32位的常数Chapter 2 Instructions: Language of the Computer 57分支地址分支地址 Branch Addressingn分支指令说明n操作吗，两个寄存器，两个地址n大多数跳转目标离跳出的位置较近n向前或向后oprsrtconstant or address6 bits5 bits5 bits16 bitsnPC相对寻址n目标地址 = PC + offset 4n此时PC的增加量是4的倍数Chapter 2 Instructions: Languag

46、e of the Computer 58跳转地址跳转地址Jump Addressingn跳转（j和jal）的目标地址可以在代码段的任何位置n指令除op外，指令其它字段都是地址opaddress6 bits26 bitsn直接跳转到地址nTarget address = PC3128 : (address 4)28位4位Chapter 2 Instructions: Language of the Computer 59目标地址目标地址 Target Addressing Examplen早期例子的循环代码n设循环的起始地址是8000 Loop: sll $t1, $s3, 2800000019

47、920 add $t1, $t1, $s68000409229032 lw $t0, 0($t1)8000835980 bne $t0, $s5, Exit8001258212 addi $s3, $s3, 180016819191 j Loop80020220000Exit: 80024Chapter 2 Instructions: Language of the Computer 60远程分支远程分支Branching Far Awayn如果跳转对象地址太大无法用16位的偏移表示，汇编将重写代码n【把短跳转（216 范围）n 变成长跳转（2 22626 范围）】nExamplebeq $s

48、0,$s1, L1bne $s0,$s1, L2j L1L2: Chapter 2 Instructions: Language of the Computer 61地址模式总结地址模式总结 Addressing Mode SummaryAddressing Mode SummaryChapter 2 Instructions: Language of the Computer 622.11并行与指令：同步并行与指令：同步n处理器共享存储器同一区域nP1 写, P2 读n（任务1写的结果是任务2要读取得值）n如果P1和P2不同步，将发生数据竞争n结果由访问次序决定n依赖硬件提供同步指令n（例如

49、：lock和unlock指令，控制一个“互斥区”）n多核处理器的情况下：n任务1 Sw $t0,0($s0)n任务2 Lw $t1,0($s0)n此时，任务2和任务1必须同步，否则，无法判断$t1中读取的是$t0,还是0（$s0）单元以前的数值。2.11 Parallelism and Instructions: SynchronizationChapter 2 Instructions: Language of the Computer 632.11并行与指令：同步并行与指令：同步n原子读原子读/ /写内存操作写内存操作n在读和写之间，不再允许对该空间的其他操作n可以是单一的指令n例如寄存器

50、和内存之间的原子交换n或者指令的原子配对2.11 Parallelism and Instructions: SynchronizationChapter 2 Instructions: Language of the Computer 64MIPS中的同步中的同步Synchronization in MIPS n链接取数(Load linked) nll rt, offset(rs)n条件存数(Store conditional) nsc rt, offset(rs)n如果ll指令没改变该地址内容则成功，rt返回1；n如果被改变了，则失败，rt返回0；n例如：atomic swap (检测和

51、设置锁变量)try: add $t0,$zero,$s4 ;copy exchange value ll $t1,0($s1) ;load linked sc $t0,0($s1) ;store conditional beq $t0,$zero,try ;branch store fails add $s4,$zero,$t1 ;put load value in $s4Chapter 2 Instructions: Language of the Computer 65编译并执行程序编译并执行程序 Translation and StartupTranslation and Startup

52、许多编译器直接产生目标模块静态链接2.12 Translating and Starting a ProgramChapter 2 Instructions: Language of the Computer 66汇编伪指令汇编伪指令 Assembler Pseudo InstructionsAssembler Pseudo Instructionsn大多数汇编指令和机器指令是一对一的n特殊的是伪指令n伪指令：汇编指令的变种nmove $t0, $t1move $t0, $t1add $t0, $zero, $t1blt $t0, $t1, Lblt $t0, $t1, L slt $at,

53、$t0, $t1bne $at, $zero, Ln$at (register 1): 汇编程序的临时寄存器（使用汇编语言时候的硬件额外的开销）Chapter 2 Instructions: Language of the Computer 67生成目标模块生成目标模块Producing an Object ModuleProducing an Object Modulen汇编器（或编译器）把程序翻译成机器语言n提供从部分构建完整程序的信息n 目标文件头：描述目标文件其他部分的大小和位置n正文段：翻译后的指令，包含机器语言代码n静态数据段：包含在程序生命周期内分配的数据n重定位信息，标记了一些

54、程序加载进内存时依赖于绝对地址的指令和数据n符号表，全局定义和外部引用n调试信息：用于关联源文件Chapter 2 Instructions: Language of the Computer 68链接目标模块链接目标模块 Linking Object Modulesn产生一个可执行的映像1. 合并段（代码和数据数据库象征性放入内存）2. 决定数据和指令标签的地址3. 修补引用（内部和外部引用）n可以留下依靠重定位程序修复的部分n但虚拟内存，不需要做这些n虚拟内存空间，程序必须以绝对地址装入Chapter 2 Instructions: Language of the Computer 69加

55、载程序加载程序Loading a Programn把待执行的程序从硬盘的镜像文件读入内存1. 读取可执行文件头来确定正文段和数据段的大小2. 为正文和数据创建一个足够大的地址空间3. 把指令和初始数据拷贝到内存或者设置页表项,使它们可用4. 把主程序的参数复制到栈顶5. 初始化寄存器（包括堆栈指针$sp, 帧指针$fp, 全局指针$gp ）6. 跳转到启动进程n复制参数到寄存器并调用主函数mainn主函数返回时，通过系统调用exit终止程序Chapter 2 Instructions: Language of the Computer 70动态链接库动态链接库Dynamic LinkingDy

56、namic Linkingn调用时，只是连接或装入库文件n过程代码重定位；n避免所有程序中出现的链接库；但是这些库的信息是一次性代入内存，占用内存空间。只是在用到的时候才链接该库；n自动装入最新的编译器中的版本的动态库。Chapter 2 Instructions: Language of the Computer 71晚过程连接晚过程连接 Lazy Linkage（只是在用到的时候才链接该库只是在用到的时候才链接该库）Indirection tableStub: Loads routine ID,Jump to linker/loaderLinker/loader codeDynamical

57、lymapped codeChapter 2 Instructions: Language of the Computer 72启动一个启动一个Java程序程序 Starting Java ApplicationsSimple portable instruction set for the JVMInterprets bytecodesCompiles bytecodes of “hot” methods into native code for host machineChapter 2 Instructions: Language of the Computer 73C Sort Exa

58、mplen使用汇编指令的冒泡排序n（交换内存中两个位置所存的值）nSwap procedure (leaf)void swap(int v, int k) int temp; temp = vk; vk = vk+1; vk+1 = temp;nv in $a0, k in $a1, temp in $t02.13 A C Sort Example to Put It All TogetherChapter 2 Instructions: Language of the Computer 74SwapSwap过程过程 The Procedure SwapThe Procedure Swapsw

59、ap: sll $t1, $a1, 2 # $t1 = k * 4 （按照字节编址） add $t1, $a0, $t1 # $t1 = v+(k*4) # (address of vk) lw $t0, 0($t1) # $t0 (temp) = vk lw $t2, 4($t1) # $t2 = vk+1 sw $t2, 0($t1) # vk = $t2 (vk+1) sw $t0, 4($t1) # vk+1 = $t0 (temp) jr $ra # return to calling routineC代码 （按照字编址） MIPS代码（按照字节编址）1、为程序变量分配寄存器； 【v

60、 in $a0, k in $a1, temp in $t0】2、为过程体生成汇编代码；3、保存过程调用间的寄存器（本例中没有用到，因为本例是一个叶过程）；Chapter 2 Instructions: Language of the Computer 75编译优化的影响编译优化的影响 Effect of Compiler OptimizationEffect of Compiler Optimization1、编译时间2、指令数；3、时钟周期4、CPI5、算法执行时间是准确衡量程序性能的唯一标准Chapter 2 Instructions: Language of the Computer 76经验教训经验教训 Lessons Learntn单独的