系統(tǒng)級(jí)編程總結(jié)

1、復(fù)習(xí)提綱第1章概念、選擇題第2章Data lab(lab 2)10個(gè)函數(shù)+注釋位相關(guān)內(nèi)容1. 位，字節(jié)，字，進(jìn)制相關(guān)內(nèi)容（常識(shí)）2. %X 16進(jìn)制形式輸出整數(shù)，忽略03. 大端小端：例如0x9A0477F3 小端從低地址到高地址存儲(chǔ)依次是（F3 77 04 9A）4. 6種位操作運(yùn)算符：1補(bǔ)碼，<<>>移位，&與，|或，異或數(shù)據(jù)的表示1. 整數(shù)：原碼1001 0010 反碼(1s)：0110 1101 補(bǔ)碼(2s 反碼+1)：0110 1110負(fù)數(shù)等于正數(shù)的2s （記住這句，就記住了整數(shù)表達(dá)方式，符號(hào)位只是標(biāo)記）C語(yǔ)言是算數(shù)右移，保留符號(hào)位數(shù)據(jù)類型轉(zhuǎn)換：大-&

2、gt;小會(huì)丟失一部分，從而也可能引起符號(hào)的轉(zhuǎn)變，小->大符號(hào)位會(huì)延展從而保留溢出overflow：危害是不會(huì)被檢測(cè),處理方法：判斷sum是否小于其中某個(gè)值2. 非整數(shù)：定點(diǎn)數(shù)（fixed point）：用小數(shù)點(diǎn)分割二進(jìn)制數(shù)，小數(shù)點(diǎn)的位置決定數(shù)大小BCD：十進(jìn)制數(shù)用二進(jìn)制表示IEEE Floating point： (1)s M 2ES:符號(hào)位 M：小數(shù)點(diǎn)移動(dòng)至最左的1后面的位置后的小數(shù)部分 E(真值) = Exp(機(jī)器表示(移碼) Bias(偏移量) Bias = 2(e-1) - 1, where e is number of exponent bits在float下e是8，即1位S，

3、8位EXP，23位M第3章編譯器（記錄員）與匯編器（翻譯）的異同相同：將一種語(yǔ)言翻譯成另一種不同：編譯器是將高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言，在此過(guò)程中需要分析和選擇，高級(jí)語(yǔ)言往往和機(jī)器語(yǔ)言不是一一對(duì)應(yīng)的，一條高級(jí)語(yǔ)言可能被翻譯成多條低級(jí)語(yǔ)言 而匯編器僅僅是將匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言，匯編語(yǔ)言往往和機(jī)器語(yǔ)言是一一對(duì)應(yīng)的對(duì)齊（Alignment）（解釋為什么？什么是？/給一段代碼讓你對(duì)齊）什么是：為了使CPU能夠?qū)ψ兞窟M(jìn)行快速的訪問(wèn),變量的起始地址應(yīng)該具有某些特性,即所謂的”對(duì)齊”. 比如4字節(jié)的int型,其起始地址應(yīng)該位于4字節(jié)的邊界上,即起始地址能夠被4整除.為什么：字節(jié)對(duì)齊的作用不僅是便于cpu快速訪

4、問(wèn)，同時(shí)合理的利用字節(jié)對(duì)齊可以有效地節(jié)省存儲(chǔ)空間。對(duì)齊的例子：結(jié)構(gòu)，算sizeof活動(dòng)記錄（code->畫圖，填空）stack pointer R -espframe pointer R -ebp什么是活動(dòng)記錄：The chunk of memory allocated for each function invocation活動(dòng)記錄創(chuàng)建過(guò)程：When a function is called, the compiler and hardware:caller ：save contextpush parameters and the return address into the sta

5、ck 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 overf

6、low緩沖區(qū)溢出緩存：連續(xù)的一段內(nèi)存空間緩存溢出：使用超出了緩存區(qū)的承載量，從而造成邊界的覆蓋6.2,6.3概念題，函數(shù)調(diào)用規(guī)范（參數(shù)，活動(dòng)記錄構(gòu)造和析構(gòu)）定義：常見(jiàn)類型及其區(qū)別：參數(shù)壓棧順序清理?xiàng)Ｖ袇?shù)_cdecl從右到左caller_stdcall / WINAPI從右到左calleePascal從左到右caller_fastcallPPT上沒(méi)寫PPT上沒(méi)寫_thiscallPPT上沒(méi)寫PPT上沒(méi)寫一些C的函數(shù)調(diào)用規(guī)范：動(dòng)態(tài)內(nèi)存分配：在程序運(yùn)行時(shí)進(jìn)行的內(nèi)存分配，堆，棧9、 十章后memory layout，動(dòng)態(tài)，靜態(tài)，棧，堆動(dòng)態(tài)內(nèi)存分配：在程序運(yùn)行時(shí)進(jìn)行的內(nèi)存分配，堆，棧memory bu

7、g（四類），在code找錯(cuò)誤Making and Using Bad References1. 指針不初始化 2.修改指針要傳指針的指針 3.只free沒(méi)賦值NULL的野指針總之是指針的錯(cuò)誤使用Overwriting Memory 1.數(shù)組訪問(wèn)越界 2.分配空間不夠sizeof沒(méi)考慮數(shù)據(jù)類型大小 3.字符串有04.很隱秘的問(wèn)題：Twice free兩次free沒(méi)啥說(shuō)的Memory Leaks：the failure to deallocate (free) a block of memory when it is no longer neededMalloc（）/free（）匹配問(wèn)題（一一對(duì)應(yīng)

8、），只有malloc沒(méi)有free->內(nèi)存泄漏（lab 8 practice 1)注意分支語(yǔ)句要每個(gè)分支都能free，同時(shí)結(jié)構(gòu)體里如果有指針用完也要記得先f(wàn)ree里面另外需要注意的程序錯(cuò)誤：1.Malloc之后應(yīng)該判斷是否分配了空間If(str = NULL)2.Malloc出來(lái)的指針是空類型的，要轉(zhuǎn)換成相應(yīng)的類型如： (char *) malloc(size1+1);垃圾回收的概念（什么是？回收的四種方法）什么是垃圾回收：垃圾是指使用而沒(méi)有free就將指向該內(nèi)存塊的指針賦值為NULL的內(nèi)存單元，這些單元既是無(wú)用的又無(wú)法繼續(xù)使用。垃圾回收就是在可分配內(nèi)存空間不夠的時(shí)候，檢測(cè)并回收那些垃圾內(nèi)

9、存塊，使得這些內(nèi)存單元能夠重新被使用（從圖的角度理解，能夠使用的內(nèi)存塊一定是從根節(jié)點(diǎn)可以到達(dá)（通過(guò)指針）的內(nèi)存塊節(jié)點(diǎn)，而垃圾就是那些無(wú)法到達(dá)的節(jié)點(diǎn)）四種方法：Mark and Sweep Collecting 標(biāo)記清除法：用內(nèi)存塊額外的位來(lái)作為標(biāo)記位，在沒(méi)有可用內(nèi)存塊使，對(duì)所有可以到達(dá)的內(nèi)存塊進(jìn)行一次標(biāo)記，之后清掃所有heap內(nèi)存塊，將那些沒(méi)有被標(biāo)記的（就是垃圾）內(nèi)存塊free，將已標(biāo)記的內(nèi)存塊的標(biāo)記清除（便于下次再執(zhí)行算法）Copying Collection 復(fù)制法：維護(hù)兩個(gè)堆，一個(gè)是正在使用的，另一個(gè)是垃圾回收時(shí)用的，在沒(méi)空間時(shí)，將正在使用的堆上，可以到達(dá)的內(nèi)存塊，都復(fù)制到另一個(gè)堆上，然

10、后清空正在使用的堆，轉(zhuǎn)換角色，其實(shí)我覺(jué)得這個(gè)方法很智障。Reference Counting 引用計(jì)數(shù)法：在每個(gè)塊內(nèi)，維護(hù)能夠到達(dá)每個(gè)塊的指針的數(shù)量，如果這個(gè)計(jì)數(shù)是0則代表是垃圾。但存在的問(wèn)題是開(kāi)銷大，并且無(wú)法解決循環(huán)引用的問(wèn)題Generational GC 分代式垃圾回收法：基于經(jīng)驗(yàn)來(lái)看，一些長(zhǎng)期能夠到達(dá)的內(nèi)存塊往往不易出現(xiàn)垃圾，而一些剛被使用的內(nèi)存塊容易變成垃圾，因此將內(nèi)存塊根據(jù)使用的時(shí)間來(lái)分代，較頻繁的檢測(cè)那些新分配的內(nèi)存單元，較少的檢測(cè)已經(jīng)安全使用很久的內(nèi)存單元，這樣提高了效率不用過(guò)多訪問(wèn)所有內(nèi)存單元Profiling設(shè)計(jì)思想（概念題），依據(jù)（拿空間換時(shí)間）程序優(yōu)化的黃金法則是算法優(yōu)化

11、，但也不是復(fù)雜度小的算法就一定好于復(fù)雜度大的算法80/20原則：It means 80% of the CPU time is spent in 20% of the program.阿姆達(dá)爾定律：系統(tǒng)優(yōu)化某部件所獲得的系統(tǒng)性能的改善程度，取決于該部件被使用的頻率，或所占總執(zhí)行時(shí)間的比例。加速比（老執(zhí)行時(shí)間除以新執(zhí)行時(shí)間）的計(jì)算：其中S應(yīng)當(dāng)是性能與原來(lái)相比的倍數(shù)Performance/measure->定時(shí)器（use timer+wall timer）工作原理，工具幫你加的timerWall time：最一般意義的時(shí)間，現(xiàn)實(shí)生活中的一段時(shí)間User Time: time spent ex

12、ecuting 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硬件的時(shí)間：TSC: Time stamp counter統(tǒng)計(jì)抽樣時(shí)間：In th

13、is approach, a timer periodically interrupts the program and records the program counter Optimization blocker編譯器優(yōu)化瓶頸（給你段代碼問(wèn)你是什么blocker，或者利用書上的四種方法優(yōu)化for循環(huán)）存儲(chǔ)器變量別名（memory aliasing）：編譯器必需假設(shè)不同的指針可能會(huì)指向存儲(chǔ)器的同一位置，造成了妨礙優(yōu)化的因素。下面的高效，但是xp = yp時(shí)，結(jié)果不同函數(shù)副作用or代碼副作用（procedure side-effects）：編譯器不會(huì)判斷一個(gè)函數(shù)是否有副作用，它會(huì)假設(shè)最糟的情

14、況，并保持所有的函數(shù)調(diào)用不變For 循環(huán)優(yōu)化四種方法：名詞解釋：什么叫memory hierarchies？依據(jù)，locality？存儲(chǔ)器層次：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.時(shí)間局部性：Addresses

15、that are referenced are soon referenced repeatedly.空間局部性：Addresses near a referenced address will soon be accessed.Memory mountain lab（看圖說(shuō)話，cache多大，為什么下降？書的封面/寫段代碼（）二重循環(huán)），存儲(chǔ)器山存儲(chǔ)器山核心代碼：for (i = 0; i < elems; i += stride)result += datai;二重循環(huán)代碼：for (size = MAXBYTES; size >= MINBYTES; size >>

16、;= 1) for (stride = 1; stride <= MAXSTRIDE; stride+) printf("%.1ft", run(size, stride, Mhz);printf("n");山脊：時(shí)間局部性由圖看出L1cache=16k，L2cache=512k下降的原因：不大于16k的工作集存放在L1cache里，讀速率最高；介于16k和8m的工作集不能完全存放在L1cache里，但可以存放在L2cache里，因此讀速率明顯降低；工作集尺寸大于8m，讀速率最低。斜坡：空間局部性由圖看出L1cache的cache line為8個(gè)字

17、下降的原因：固定工作集尺寸大于L1cache容量時(shí)，L1cache缺失需要在L2cache中讀數(shù)據(jù)，隨著步長(zhǎng)從1增加到8，讀速率逐漸下降；步長(zhǎng)大于8個(gè)字的時(shí)候，每一次讀操作都會(huì)缺失，所有的數(shù)據(jù)都需要從L2cache中讀取，讀速率就穩(wěn)定等于L2cache的讀速率。Cache：類型，概念，計(jì)算題cache miss rate（給段代碼），cache整個(gè)多大，cache line多大概念：類型：直接映射每組一個(gè)cache lineEg：Cache set 大小：N=2sCache line 大?。篖=2b組關(guān)聯(lián)每組cache line個(gè)數(shù)>1Eg：Cache的大?。?8 （組數(shù)）* 4（每組4

18、個(gè)） * 4B（每個(gè)4字節(jié)）整個(gè)cache的位數(shù)：（1+22+32）* 28 * 4其中1:valid，22:tag，32:data全關(guān)聯(lián)只有一個(gè)組，cache line個(gè)數(shù) = cache大小 ÷ block 個(gè)數(shù)三種cache的例子：Cache miss種類：Cold (compulsary) miss，Conflict miss，Capacity miss計(jì)算cache miss rate（PPT上的例題）：緩存：2048B（總大小）、直接映射、32bytes/塊每塊大小32bytes，一個(gè)結(jié)構(gòu)體大小4*4=16bytes，一個(gè)塊能裝2個(gè)結(jié)構(gòu)體總共寫操作：16*16*4 =10

19、24Cache Miss =16*8 =128 Miss Rate = (16*8) / (16*16*4) = 1/8 = 0.125Cache line的大?。阂话闶?6或32個(gè)字節(jié)Link：3步工作流程，什么功能，匯編（全0000），符號(hào)解析+重定位，tinylinker lab（找輸出，考重定位）3步工作流程:1. Symbol Resolution 符號(hào)解析2. Combination/Alignment 組合3. Relocation 重定位執(zhí)行l(wèi)inking：1. static linking：在源碼被譯為機(jī)器碼時(shí)執(zhí)行靜態(tài)鏈接2. load-time dynamic linkin

20、g：在程序被加載到內(nèi)存中時(shí)執(zhí)行動(dòng)態(tài)鏈接3. run-time dynamic linking：在應(yīng)用程序運(yùn)行時(shí)執(zhí)行動(dòng)態(tài)鏈接Linker的功能：takes one or more objects generated by a compiler and combines them into a single executable program 符號(hào)解析：三種鏈接器符號(hào)：由模塊m定義可以被其他模塊引用的全局符號(hào)，由其他模塊定義可以被模塊m引用的全局符號(hào)，只能被模塊m定義和引用的局部符號(hào)重定位： Exception：流程，什么是，控制流，異常，80行“hello world”回調(diào)關(guān)系，消息循環(huán)控制流：概念：An exception is an abrupt change in the control flow in response to some change in the processors state.就是控制流中的突變，用來(lái)響應(yīng)處理器狀態(tài)中的某些變化。一部分由硬件實(shí)現(xiàn)，一部分由軟件實(shí)現(xiàn)。處理流程中斷interrupt：陷阱trap故障fault終止abort異常分類：回調(diào)函數(shù)callback function：由程序員設(shè)計(jì)卻由windows系統(tǒng)呼叫的函數(shù)WndProc通過(guò)wind