系统级编程总结.doc

(完整word版)系统级编程总结
复习提纲
第一章
概念、选择题

第二章
Data lab(lab 2)10个函数+注释
位相关内容
1. 位，字节，字，进制相关内容（常识）
2. %X 16进制形式输出整数，忽略0
3. 大端小端：例如0x9A0477F3 小端从低地址到高地址存储依次是（F3 77 04 9A）
4. 6种位操作运算符：~1补码，<<>>移位，&与，|或，^异或
数据的表示
1. 整数：
原码1001 0010 反码(1’s)：0110 1101 补码(2’s 反码+1)：0110 1110
负数等于正数的2’s （记住这句，就记住了整数表达方式，符号位只是标记）
C语言是算数右移，保留符号位
数据类型转换：大-->小会丢失一部分，从而也可能引起符号的转变，小-->大符号位会延展从而保留
溢出overflow：危害是不会被检测,处理方法：判断sum是否小于其中某个值
2. 非整数：
定点数（fixed point）：用小数点分割二进制数，小数点的位置决定数大小
BCD：十进制数用二进制表示
IEEE Floating point： (–1)^s M 2^E
S:符号位 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 --esp
frame pointer R --ebp

什么是活动记录：
The chunk of memory allocated for each function invocation
活动记录创建过程：
When a function is called, the compiler and hardware:
caller ：save context
push 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 pointer
Allocate 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
从右到左
callee
Pascal
从左到右
caller
_fastcall
PPT上没写
PPT上没写
_thiscall
PPT上没写
PPT上没写

一些C的函数调用规范：

动态内存分配：
在程序运行时进行的内存分配，堆，栈

九、 十章后
memory layout，动态，静态，栈，堆
动态内存分配：
在程序运行时进行的内存分配，堆，栈

memory bug（四类），在code找错误
Making and Using Bad References
1. 指针不初始化 2.修改指针要传指针的指针 3.只free没赋值NULL的野指针
总之是指针的错误使用
Overwriting Memory
1.数组访问越界 2.分配空间不够sizeof没考虑数据类型大小 3.字符串有\0
4.很隐秘的问题：
Twice free
两次free没啥说的
Memory Leaks：the failure to deallocate (free) a block of memory when it is no longer needed
Malloc（）/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）工作原理，工具帮你加的timer
Wall time：最一般意义的时间，现实生活中的一段时间
User Time: time spent executing instructions in the user process
System Time: time spent executing instructions in the kernel on behalf of the user process
all other time：either idle or else executing instructions unrelated to the user process
CPU 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 < elems; i += stride)
result += data[i];
二重循环代码：
for (size = MAXBYTES; size >= MINBYTES; size >>= 1) {
for (stride = 1; stride <= MAXSTRIDE; stride++)
printf("%.1f\t", run(size, stride, Mhz));
printf("\n");
山脊：时间局部性

由图看出L1cache=16k，L2cache=512k
下降的原因：不大于16k的工作集存放在L1cache里，读速率最高；介于16k和8m的工作集不能完全存放在L1cache里，但可以存放在L2cache里，因此读速率明显降低；工作集尺寸大于8m，读速率最低。
斜坡：空间局部性

由图看出L1cache的cache line为8个字
下降的原因：固定工作集尺寸大于L1cache容量时，L1cache缺失需要在L2cache中读数据，随着步长从1增加到8，读速率逐渐下降；步长大于8个字的时候，每一次读操作都会缺失，所有的数据都需要从L2cache中读取，读速率就稳定等于L2cache的读速率。

Cache：类型，概念，计算题cache miss rate（给段代码），cache整个多大，cache line多大
概念：

类型：
直接映射

每组一个cache line
Eg：
Cache set 大小：N=2^s
Cache line 大小：L=2^b
组关联
每组cache line个数>1
Eg：
Cache的大小：2^8 （组数）* 4（每组4个） * 4B（每个4字节）
整个cache的位数：（1+22+32）* 2^8 * 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 =1024

Cache Miss =16*8 =128
Miss Rate = (16*8) / (16*16*4) = 1/8 = 0.125
Cache 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 processor’s state.就是控制流中的突变，用来响应处理器状态中的某些变化。一部分由硬件实现，一部分由软件实现。
处理流程
中断interrupt：

陷阱trap

故障fault

终止abort

异常分类：

回调函数callback function：由程序员设计却由windows系统呼叫的函数
WndProc通过windows kernel实现回调

消息循环：

PPT总结
Unit 2. Representation of Data
位相关内容
5. 位，字节，字，进制相关内容（常识）
6. %X 16进制形式输出整数，忽略0
7. 大端小端：例如0x9A0477F3 小端从低地址到高地址存储依次是（F3 77 04 9A）
8. 6种位操作运算符：~1补码，<<>>移位，&与，|或，^异或
数据的表示
3. 整数：
原码1001 0010 反码(1’s)：0110 1101 补码(2’s 反码+1)：0110 1110
负数等于正数的2’s （记住这句，就记住了整数表达方式，符号位只是标记）
C语言是算数右移，保留符号位
数据类型转换：大-->小会丢失一部分，从而也可能引起符号的转变，小-->大符号位会延展从而保留
溢出overflow：危害是不会被检测,处理方法：判断sum是否小于其中某个值
4. 非整数：
定点数（fixed point）：用小数点分割二进制数，小数点的位置决定数大小
BCD：十进制数用二进制表示
IEEE Floating point： (–1)^s M 2^E
S:符号位 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

Unit 3. Representation of Code
Unit 4. Structured Data Representation