系统级编程总结.doc

(完整word版)系统级编程总结复习提纲第一章概念、选择题第二章Data lab(lab 2)10个函数+注释位相关内容1. 位，字节，字，进制相关内容（常识）2. %X 16进制形式输出整数，忽略03. 大端小端：例如0x9A0477F3 小端从低地址到高地址存储依次是（F3 77 04 9A）4. 6种位操作运算符：1补码，移位，&与，|或，异或数据的表示1. 整数：原码1001 0010 反码(1s)：0110 1101 补码(2s 反码+1)：0110 1110负数等于正数的2s （记住这句，就记住了整数表达方式，符号位只是标记）C语言是算数右移，保留符号位数据类型转换：大-小会丢失一部分，从而也可能引起符号的转变，小-大符号位会延展从而保留溢出overflow：危害是不会被检测,处理方法：判断sum是否小于其中某个值2. 非整数：定点数（fixed point）：用小数点分割二进制数，小数点的位置决定数大小BCD：十进制数用二进制表示IEEE Floating point： (1)s M 2ES:符号位 M：小数点移动至最左的1后面的位置后的小数部分 E(真值) = Exp(机器表示(移码) Bias(偏移量) Bias = 2(e-1) - 1, where e is number of exponent bits在float下e是8，即1位S，8位EXP，23位M第三章编译器（记录员）与汇编器（翻译）的异同相同：将一种语言翻译成另一种不同：编译器是将高级语言翻译成机器语言，在此过程中需要分析和选择，高级语言往往和机器语言不是一一对应的，一条高级语言可能被翻译成多条低级语言 而汇编器仅仅是将汇编语言翻译成机器语言，汇编语言往往和机器语言是一一对应的对齐（Alignment）（解释为什么？什么是？/给一段代码让你对齐）什么是：为了使CPU能够对变量进行快速的访问,变量的起始地址应该具有某些特性,即所谓的”对齐”. 比如4字节的int型,其起始地址应该位于4字节的边界上,即起始地址能够被4整除.为什么：字节对齐的作用不仅是便于cpu快速访问，同时合理的利用字节对齐可以有效地节省存储空间。对齐的例子：结构，算sizeof活动记录（code-画图，填空）stack pointer R -espframe pointer R -ebp什么是活动记录：The chunk of memory allocated for each function invocation活动记录创建过程：When a function is called, the compiler and hardware:caller ：save contextpush parameters and the return address into the stack callee: construct own Stack Frame push the frame pointer into the stack set the frame pointer equal to the stack pointerAllocate a chunk of memory to store the local state by decrement the stack pointer with an uncertain integer（Estimated by compiler according to the function content）Buffer overflow缓冲区溢出缓存：连续的一段内存空间缓存溢出：使用超出了缓存区的承载量，从而造成边界的覆盖6.2,6.3概念题，函数调用规范（参数，活动记录构造和析构）定义：常见类型及其区别：参数压栈顺序清理栈中参数_cdecl从右到左caller_stdcall / WINAPI从右到左calleePascal从左到右caller_fastcallPPT上没写PPT上没写_thiscallPPT上没写PPT上没写一些C的函数调用规范：动态内存分配：在程序运行时进行的内存分配，堆，栈九、 十章后memory layout，动态，静态，栈，堆动态内存分配：在程序运行时进行的内存分配，堆，栈memory bug（四类），在code找错误Making and Using Bad References1. 指针不初始化 2.修改指针要传指针的指针 3.只free没赋值NULL的野指针总之是指针的错误使用Overwriting Memory 1.数组访问越界 2.分配空间不够sizeof没考虑数据类型大小 3.字符串有04.很隐秘的问题：Twice free两次free没啥说的Memory Leaks：the failure to deallocate (free) a block of memory when it is no longer neededMalloc（）/free（）匹配问题（一一对应），只有malloc没有free-内存泄漏（lab 8 practice 1)注意分支语句要每个分支都能free，同时结构体里如果有指针用完也要记得先free里面另外需要注意的程序错误：1.Malloc之后应该判断是否分配了空间If(str = NULL)2.Malloc出来的指针是空类型的，要转换成相应的类型如： (char *) malloc(size1+1);垃圾回收的概念（什么是？回收的四种方法）什么是垃圾回收：垃圾是指使用而没有free就将指向该内存块的指针赋值为NULL的内存单元，这些单元既是无用的又无法继续使用。垃圾回收就是在可分配内存空间不够的时候，检测并回收那些垃圾内存块，使得这些内存单元能够重新被使用（从图的角度理解，能够使用的内存块一定是从根节点可以到达（通过指针）的内存块节点，而垃圾就是那些无法到达的节点）四种方法：Mark and Sweep Collecting 标记清除法：用内存块额外的位来作为标记位，在没有可用内存块使，对所有可以到达的内存块进行一次标记，之后清扫所有heap内存块，将那些没有被标记的（就是垃圾）内存块free，将已标记的内存块的标记清除（便于下次再执行算法）Copying Collection 复制法：维护两个堆，一个是正在使用的，另一个是垃圾回收时用的，在没空间时，将正在使用的堆上，可以到达的内存块，都复制到另一个堆上，然后清空正在使用的堆，转换角色，其实我觉得这个方法很智障。Reference Counting 引用计数法：在每个块内，维护能够到达每个块的指针的数量，如果这个计数是0则代表是垃圾。但存在的问题是开销大，并且无法解决循环引用的问题Generational GC 分代式垃圾回收法：基于经验来看，一些长期能够到达的内存块往往不易出现垃圾，而一些刚被使用的内存块容易变成垃圾，因此将内存块根据使用的时间来分代，较频繁的检测那些新分配的内存单元，较少的检测已经安全使用很久的内存单元，这样提高了效率不用过多访问所有内存单元Profiling设计思想（概念题），依据（拿空间换时间）程序优化的黄金法则是算法优化，但也不是复杂度小的算法就一定好于复杂度大的算法80/20原则：It means 80% of the CPU time is spent in 20% of the program.阿姆达尔定律：系统优化某部件所获得的系统性能的改善程度，取决于该部件被使用的频率，或所占总执行时间的比例。加速比（老执行时间除以新执行时间）的计算：其中S应当是性能与原来相比的倍数Performance/measure-定时器（use timer+wall timer）工作原理，工具帮你加的timerWall time：最一般意义的时间，现实生活中的一段时间User Time: time spent executing instructions in the user processSystem Time: time spent executing instructions in the kernel on behalf of the user processall other time：either idle or else executing instructions unrelated to the user processCPU time = user CPU time + system CPU time硬件的时间：TSC: Time stamp counter统计抽样时间：In this approach, a timer periodically interrupts the program and records the program counter Optimization blocker编译器优化瓶颈（给你段代码问你是什么blocker，或者利用书上的四种方法优化for循环）存储器变量别名（memory aliasing）：编译器必需假设不同的指针可能会指向存储器的同一位置，造成了妨碍优化的因素。下面的高效，但是xp = yp时，结果不同函数副作用or代码副作用（procedure side-effects）：编译器不会判断一个函数是否有副作用，它会假设最糟的情况，并保持所有的函数调用不变For 循环优化四种方法：名词解释：什么叫memory hierarchies？依据，locality？存储器层次：For each k, the faster, smaller device at level k serves as a cache for the larger, slower device at level k+1.第k层作为第k+1层的缓存局部性原理：Memory addresses that have been accessed recently are likely to be accessed again.时间局部性：Addresses that are referenced are soon referenced repeatedly.空间局部性：Addresses near a referenced address will soon be accessed.Memory mountain lab（看图说话，cache多大，为什么下降？书的封面/写段代码（）二重循环），存储器山存储器山核心代码：for (i = 0; i = MINBYTES; size = 1) for (stride = 1; stride 1Eg：Cache的大小：28 （组数）* 4（每组4个） * 4B（每个4字节）整个cache的位数：（1+22+32）* 28 * 4其中1:valid，22:tag，32:data全关联只有一个组，cache line个数 = cache大小 block 个数三种cache的例子：Cache miss种类：Cold (compulsary) miss，Conflict miss，Capacity miss计算cache miss rate（PPT上的例题）：缓存：2048B（总大小）、直接映射、32bytes/块每块大小32bytes，一个结构体大小4*4=16bytes，一个块能装2个结构体总共写操作：16*16*4 =1024Cache Miss =16*8 =128 Miss Rate = (16*8) / (16*16*4) = 1/8 = 0.125Cache line的大小：一般是16或32个字节Link：3步工作流程，什么功能，汇编（全0000），符号解析+重定位，tinylinker lab（找输出，考重定位）3步工作流程:1. Symbol Resolution 符号解析2. Combination/Alignment 组合3. Relocation 重定位执行linking：1. static linking：在源码被译为机器码时执行静态链接2. load-time dynamic linking：在程序被加载到内存中时执行动态链接3. run-time dynamic linking：在应用程序运行时执行动态链接Linker的功能：takes one or more objects generated by a compiler and combines them into a single executable program 符号解析：三种链接器符号：由模块m定义可以被其他模块引用的全局符号，由其他模块定义可以被模块m引用的全局符号，只能被模块m定义和引用的局部符号重定位： Exception：流程，什么是，控制流，异常，80行“hello world”回调关系，消息循环控制流：概念：An exception is an abrupt change in the control flow in response to some change in the processors state.就是控制流中的突变，用来响应处理器状态中的某些变化。一部分由硬件实现，一部分由软件实现。处理流程中断interrupt：陷阱trap故障fault终止abort异常分类：回调函数callback function：由程序员设计却由windows系统呼叫的函数WndProc通过windows kernel实现回调消息循环：PPT总结Unit 2. Representation of Data位相关内容5. 位，字节，字，进制相关内容（常识）6. %X 16进制形式输出整数，忽略07. 大端小端：例如0x9A0477F3 小端从低地址到高地址存储依次是（F3 77 04 9A）8. 6种位操作运算符：1补码，移位，&与，|或，异或数据的表示3. 整数：原码1001 0010 反码(1s)：0110 1101 补码(2s 反码+1)：0110 1110负数等于正数的2s （记住这句，就记住了整数表达方式，符号位只是标记）C语言是算数右移，保留符号位数据类型转换：大-小会丢失一部分，从而也可能引起符号的转变，小-大符号位会延展从而保留溢出overflow：危害是不会被检测,处理方法：判断sum是否小于其中某个值4. 非整数：定点数（fixed point）：用小数点分割二进制数，小数点的位置决定数大小BCD：十进制数用二进制表示IEEE Floating point： (1)s M 2ES:符号位 M：小数点移动至最左的1后面的位置后的小数部分 E(真值) = Exp(机器表示(移码) Bias(偏移量) Bias = 2(e-1) - 1, where e is number of exponent bits在float下e是8，即1位S，8位EXP，23位MUnit 3. Representation of Code Unit 4. Structured Data Representation