forked from GHScan/TechNotes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path2.html
41 lines (39 loc) · 72.7 KB
/
2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
<head>
<meta http-equiv=Content-Type content="text/html; charset=utf-8">
</head>
<div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="ennote">
8. ACID: 数据库事务的属性
<div><ul><li>Atomicity: 原子性。all or nothing，要么全部完成，要么一点不做。外界看不见失败的事务</li><li>Consistancy: 一致性。数据库只会从一个合法状态迁移到另一个合法状态。向数据库写入的任何数据都必须是满足rules的，包括constraints, cascades, triggers等。应用层的正确性这里不care</li><li>Isolation: 隔离性。并发事务的执行结果应该跟串行事务的执行结果一致。依靠concurrency control，外界看不到incomplete transaction</li><li>Durability: 耐久性。一旦事务commited，哪怕遭受power loss, crashes, errors, 事务的结果都不会丢失</li></ul><div>8. awk: 将组织成行、列的table文本重新组织、统计分析等</div></div><div><ul><li>格式：pattern { actions; }</li><li>pattern：整型表达式，比如"NR%2"、"$1~/abc/"、"/abc/"（相当于"$0~/abc/"）；或者BEGIN、END；或者省略，表示匹配所有行</li><li>action: 类C语法，缺省为{print $0}</li><li>脚本作用于每一行。内置变量NR, $0；行分割符为RS</li><li>每行被自动分割：NF, $1~$NF；分隔符为FS</li><li>内置变量FILENAME</li><li style="text-align: left;">访问环境变量：ENVIRON[var]</li><li>变量不需要声明和初始化，会根据上下文被初始化为数字、字符串或者关联数组</li><li>内置数字函数log、atan2等</li><li>内置字符串函数match、sub、index、length(默认参数为$0)等</li><li>内置格式化函数print、printf等，支持重定向"print $0 > 1.txt"</li><li>支持if、while、for等控制流</li><li>常用选项：-Fxxx。作用相当于'BEGIN{FS=xxx;}'</li><li>例子：</li><li style="list-style: none; display: inline"><ul><li>输入反转：awk '{lines=$0 "\n" lines}END{print lines}'</li><li>输出奇数行: awk 'NR%2'</li><li>输出偶数行: awk 'NR%2==0'</li><li>输出%3==1的行: awk 'NR%3==1'</li><li>输出%3==0的行: awk 'NR%3==0'</li><li>给shell脚本的20~30行添加注释: awk 'NR>=20&&NR<=30{printf "#"}{print $0}'</li></ul></li></ul></div><div>8. sed：对文本行做简单翻译</div><div><ul><li>格式：[address_1, address_2] command</li><li>address可以使正则“/.../"或者行号"n"或者特殊行"^"、"$"</li><li>常用命令s,p,d,c,i,a,y,r，以及同时涉及pattern space和holding space的n, N, g, G, h, H, x</li><li>s命令的选项：g，替换所有；2，替换第2次出现；2g，替换第2次以后的出现；i，不区分大小写；</li><li>常用选项-n，用来禁用默认的pattern space输出</li><li>选项-i，直接替换输入文件</li><li>支持分别-e多个命令，或者用";"分割多个命令，也可以用{}包含嵌套命令</li><li>例子：</li><li style="list-style: none; display: inline"><ul><li>输入反转：sed 'G;h;$!d' 或者 sed -n 'G;h;$p'</li><li>输出奇数行: sed 'n;d'</li><li>输出偶数行: sed -n 'n;p'</li><li>输出%3==1的行: sed 'n;N;d'</li><li>输出%3==0的行: sed -n 'n;n;p'</li><li>给shell脚本的20~30行添加注释: sed '20,30s/^/#/'</li></ul></li></ul><div>9. Python project: SyncDir</div><div><br>
</div><div>10. 在C++中定义type_traits(出自Bjarne Stroustrup's C++ Style and Technique FAQ)： </div></div><div><ul><li><span style="background-color: rgb(255, 255, 255); font-size: 14px; line-height: 20.880001068115234px; white-space: pre-wrap;"><span style="line-height: 20.880001068115234px;">template<class T1, class T2> struct Can_copy {</span></span><pre style="margin-top: 0px; margin-bottom: 0px; padding: 0px; white-space: pre-wrap; word-wrap: break-word; line-height: 20.880001068115234px;" xml:space="preserve"> static void constraints(T1 a, T2 b) { T2 c = a; b = a; }
Can_copy() { void(*p)(T1,T2) = constraints; }
};
</pre></li></ul><div><span style="font-size: 14px; line-height: 20px; white-space: pre-wrap;">10.</span> Evaluation strategy</div><ul><li>Call by value: 拷贝实参值，callee无法修改实参。如C或Java的primitive类型。</li><li>Call by sharing: 拷贝实参值，callee可以修改实参的内容。如Java的各种class。广义上，这也算一种call by value</li><li>Call by reference: 如C++的引用</li><li>Call by name: 如C的宏</li><li>Call by need: 如haskell的lazy evaluation</li></ul><div>10. 用ssh执行远端命令</div><div><ul><li> "ssh username@host command"，整体可以看做一个命令，它的stdin将发到远端作为command的stdin，远端的stdout将返回本地作为命令整体的stdout</li><li>例子：</li><li style="list-style: none; display: inline"><ul><li>ssh username@host "cd ~ && ls -l"</li><li>cat main.py | ssh username@host python</li><li>cat main.sh | ssh username@host bash</li></ul></li></ul><div>10. C++ project: LazyValue</div></div></div><div><br>
</div><div>10. sort命令</div><div><ul><li>-t: 分隔符</li><li>-s: 稳定排序</li><li>-k: pos1[,pos2]，从pos1到pos2(包含pos2, 即总长度是pos2-pos1+1)，如果pos2省略，则到行尾。pos的格式是"fieldidx[.charidx]"，从1开始，如"1.1"表示第1个字段的第1个字符。</li><li>例子：</li><li style="list-style: none; display: inline"><ul><li>排序第2个字段："sort -k 2,2"</li><li>排序从第2个字段开始的整行："sort -k 2"</li><li>以第2列为主关键字，第1列为次关键字，排序："sort -k 1,1 | sort -s -k 2,2"</li></ul></li></ul><div>11. 网站架设</div></div><div><ul><li>在本机做好网站。因为是服务器，ip固定在公网，不涉及P2P那样双端都在内网的NAT穿透问题</li><li>购买空间</li><li style="list-style: none; display: inline"><ul><li>虚拟主机。主机商利用专用软件将机器的部分CPU资源、磁盘、内存划分出来给你用，如果资源占用过大进程会被kill掉，开发语言、数据库和技术方案都被限定，不能随意执行自己的程序</li><li>VPS。virtual private server。主机商利用vmware等手段虚拟主机出来，买家可以自由安装软件、重启系统</li><li>云主机。对买家来说类似VPS，但架构更先进</li><li>专用主机。一整台物理机</li></ul></li><li>购买域名并备案</li><li>绑定域名到空间</li></ul><div>11. python网站开发、维护</div></div><div><ul><li>fabric：远程部署、维护</li><li>virtualenv：建立私有环境（类似在普通目录新建一个linux用户目录），其中的python解释器会加载该环境下的包</li><li>gunicorn：WSGI（Python Web Server Gateway Interface），在http这个应用层以下进行请求路由等。和ningx/apache的关系？</li><li>supervisor：进程控制器。保证一个应用的一组进程能正常工作，crash、重启等参数、环境都正常 </li><li>django/<a href="http://web.py/bottle/web2py/flask/tornado：各种python的web框架" target="_blank">web.py/bottl<wbr>e/web2py/fla<wbr>sk/tornado：各<wbr>种python的web框<wbr>架</a></li></ul><div>11. libreadline</div><div><ul><li>libreadline中的两个c函数readline和add_history，提供了基本的历史补全、路径补全和vi/emacs键绑定</li><li>使用了libreadline的应用，默认会受~/.inputrc的影响</li><li>python的readline库是对libreadline的导入，而rlcompleter提供了对python关键字、对象属性的补全</li></ul></div><div><br>
</div><div>11. ipython：强化版的交互式命令行解释器</div></div><div><ul><li>xxx?：查看帮助。xxx可以是python对象、magic命令、alias等</li><li>obj.*field*?：查看obj的包含field的字段</li><li>magic命令：以%或者%%开头，如alias, unalias, itemit, pypy, cython, quickref, rehashx, ed等</li><li style="list-style: none; display: inline"><ul><li>line magic: magic_cmd line_content</li><li>cell magic: "%%magic_cmd\n lines"</li></ul></li><li>!shell cmd: 类似vim中的语法</li><li>py_var = %magic_cmd：将magic命令的结果保存到对象中</li><li>py_var = !cmd：将系统调用的结果保存到python对象中</li><li>identify：</li><li style="list-style: none; display: inline"><ul><li>是否是python全局变量(可以通过del销毁)</li><li>是否是magic_cmd（从这里开始的解释顺序不一定对）</li><li>是否是shell命令</li><li>是否是alias</li></ul></li><li>ipython notebook --ip='*'。开启notebook服务器，绑定本机所有ip。如果不带参数，则只绑定"127.0.0.1:8888"（只有本机的浏览器可以访问服务）</li><li>notebook包含code、markdown对象等，code对象都有输入、输出两个区</li><li>notebook中支持图片、laTex、表格的渲染</li></ul><div>12. C++ project: LuaConfig。以lua字符串初始化对象后，提供get(path), set(path, val), call(path)三个操作</div></div><div><br>
</div><div>12. 关于python的并发</div><div><ul><li>threading: 提供多线程，但受PIL限制，故IO密集的并发可以，但CPU密集的并发不行</li><li>multiprocessing: 多进程，不受PIL限制</li><li style="list-style: none; display: inline"><ul><li>multiprocessing.Pool</li><li style="list-style: none; display: inline"><ul><li>map：并行执行多个函数调用</li><li>map_async, join: 异步执行 </li></ul></li></ul></li><li>multiprocessing.dummy：接口同multiprocessing，只是是基于threading来实现</li><li style="list-style: none; display: inline"><ul><li>multiprocessing.dummy.Pool：用来做基于线程的并发，IO密集的时候很方便</li></ul></li></ul><div>12. Python project: MultiprocessingPoolMap。 利用multiprocessing.dummy.Pool的map+urllib2.urlopen，来并发请求多个url的html并提取内容和汇总。因为是IO密集的所以用dummy的多线程足矣，否则应该用multiprocessing.Pool</div></div><div><br>
</div><div>12. C++ project: 递归实现的通配符匹配和简单正则。算法仍然是《代码之美》里面的。这次更优雅的实现了?,*,+,??,*?,+?</div><div><br>
</div><div>13. python正则的扩展部分(.ne regex也是类似的)</div><div><ul><li>(?xxx)这样，在捕获后加个?表示扩展，具体效果依据xxx。(?xxx)和(pat)一起，叫grouping constructor</li><li style="list-style: none; display: inline"><ul><li>(?iLmsux)，这里的每个单字符都表示正则编译flag，和compile时的额外参数等价。比如i表示re.IGNORECASE, m表示re.MULTILINE<br>
</li><li>(?:pat)，表示这里的()只是必要的打包子表达式，不增加捕获计数。例：'(\w+\.(?:cpp|h))|\w+\.(?:java)'，其中\1表示C++文件名，\2表示Java文件名</li><li>(?P<name>pat)，相对于默认的1,2,3这样的捕获编号，这里使用name来引用捕获，正则内引用(?P=name)，python内引用group(namestr)。例：'(?P<id>\w+)|(?P<num>\d+)'，用来做分词，使用'(?P=id)'、'?P=num'或者m.group('id')、m.group('name')访问</li><li>(?#comment)，正则内的注释</li><li>(?=pat)，(?!pat)：lookahead和negative lookahead，向前看和反向向前看，表示应该有/无pat这样的后缀。例：'\w+(?=\.)'表示句尾的单词, '\w+(?!\.)'表示句中的单词</li><li>(?<=pat), (?<!pat)：lookbehind和negative lookbehind, 向后看和反向向后看，表示应该有/无pat这样的前缀。例：'(?<=i) \w+'表示i后面的单词，'(?<!i) \w+'，表示非i后面的单词i</li><li>(?(idx/name)yes_pat|no_pat)，如果idx或命名匹配存在，则这里应该匹配一个yes_pat，不存在则应该匹配no_pat，其中no_pat可以省略。例：'(<)?\w+(?(1)>)'，表示匹配'abc'或者匹配'<abc>'，不会匹配'<abc'</li></ul></li></ul><div>14. python部分标准库</div></div><div><ul><li>inspect.getsource(class or method)：提取源码。在ipython中，有对应的magic叫psource，即打印对象的源码</li></ul><div>14. Python project: 实现SimpleHTTPServer的默认行为-浏览当前文件夹</div></div><div><br>
</div><div>14. Python project: ComicWebServer, 用web.py编写的阅读漫画服务器，比如以海贼王的根目录作为参数运行服务器，浏览器访问的时候能分册浏览。对于图片文件，利用了http状态码304进行cache。</div><div><ul><li>http的文件cache方法</li><li style="list-style: none; display: inline"><ul><li>Expire头：服务器返回文件的时候，同时返回Expire头，这样，浏览器发现本地Expire没超时，直接就不再请求文件。适合周期性改变，而非事件触发改变的文件。优点是连304都不需要</li><li>Last-Modified头：服务器返回文件的时候，同时返回Last-Modified; 客户端请求文件时，同时带上它(在If-Modified-Since中)，服务器检测这个If-Modified-Since没有过期，则返回304，表示NotModified，否则返回新文件以及新的Last-Modified</li><li>ETag: 即文件内容的hash，用来标记文件版本，每次服务器都返，客户端也带，如果服务器发现ETag有变，则返回新文件，如果没变，则返回304。比Last-Modified的优点：时间戳变了，内容不一定变；1秒内连续变化，Last-Modified检测不出来；动态生成的文件没有时间戳，但可能根本没变</li></ul></li></ul><div>16. 注意淘宝、腾讯、新浪、网易等在网上提供了各种热门应用的api，http形式的，javascript形式的，不过一般需要注册开发者账号</div></div><div><br>
</div><div>17. c++11</div><div><ul><li>type deduction：类型推导，具体来说，是指c++14中的return type deduction，大概是比type inference简单吧</li><li>POD->在c++11中，被细分为两个属性，trivial class(无用类型，即构造、拷贝构造、赋值、析构都不存在), standard-layout。c++03中，union中不能包含non-trivial的成员。standard-layout即与c兼容了</li><li>perfect forwarding: 完美转发。</li><li style="list-style: none; display: inline"><ul><li>以T&&声明的模板，实参为X&&，则T->X；实参为X&，则T->X&</li><li>当T&&被推断为X&&时，如果直接以形参调用子函数，则形参会退化成X&& &，失去右值语义，所以需要改为forward<T>(v)，因为forward<T>的实现中最后一行是return (T&&)，而调用forward的T只会是X或者X&，故右值不会退化，类型被转发了</li><li>用具体类型声明的形参(非模板)X&&，一样需要以forward<X>来转发，否则一样退化成左值</li></ul></li><li>extern template class std::vector<MyClass>：which tells the compiler not to instantiate the template in this translation unit. 优化编译效率</li><li>initializer_list：可以以{x, x,x x,x x, x,x , }来构造对象，方便</li><li>成员字段在类体内的直接初始化</li><li>override, final</li><li>template aliasing: using</li><li>new string literal:</li><li style="list-style: none; display: inline"><ul><li>u8"abc", u"abc", U"abc":分别是utf-8, utf-16, utf-32，对应的类型分别是const char[], const char16_t[], const char32_t[]</li><li>R"(afsdjhkfsdf)": raw string,当然，内部不能包含)</li><li>R"delimiter(afdsfds)delminter": 比如R"#(fasdfsdfsd)#"中间不能包含#; R"@(xxxxx)@"中间不能包含@</li></ul></li><li>user-defined literal</li><li style="list-style: none; display: inline"><ul><li>后缀名必须是_xxx</li><li>实参为字符串的时候，形参为(const char *s, size_t len)</li><li>实参为整数的时候，形参为(const char*)或(unsigned long long)</li><li>例:</li></ul></li><li style="list-style: none; display: inline"><ul><li style="list-style: none; display: inline"><ul><li>声明1: RetType operator "" _suffix(const char *, size_t)</li><li>使用1: "afdsfs"_suffix</li><li>声明2: RetType operator "" _suffix(unsigned long long)</li><li>使用2: 1233_suffix</li></ul></li></ul></li></ul><div>17. c++14</div></div><div><ul><li>auto和decltype</li><li style="list-style: none; display: inline"><ul><li>decltype的类型依据表达式，可以是引用、非引用类型</li><li>auto总是非引用类型，auto&&总是引用类型，decltype(auto)则具体类型根据表达式来</li></ul></li></ul><div>17. c99</div></div><div><ul><li>关键字restrict，表示承诺该指针是访问对象的唯一方式，用来避免pointer aliasing引起的性能问题。msvc和gcc有相关扩展供c++使用</li></ul><div>18. c++的struct布局，两种方案</div></div><div><ul><li>#pragma pack: 如果文档/协议限定死了字段的顺序和布局，那么只能用pack，代价是访问字段的时候可能因为不对齐造成硬件异常，速度很慢</li><li>重排顺序，保证字段按类型对齐的同时，尽量节省空间: 重排了顺序，但是访问快、内存占用少</li></ul><div>18. linux下的系统调用profile工具</div></div><div><ul><li>strace: syscall trace, 度量所有系统调用。-c选项统计调用次数和耗时。最好编译程序的时候-static，免得一堆加载动态库的系统调用干扰分析</li><li>ltrace: library trace, 度量动态库的调用。-c统计次数和耗时。不能有-static，否则无法追踪</li></ul><div>19. sbrk/brk函数：</div><div><ul><li>unix下内核中进程堆地址的起点是变量brk（位于bss段后），sbrk增加一个增量，brk函数直接设置新的brk值。一般不要直接访问这组函数，使用malloc才是可移植的（malloc有可能是用sbrk或者mmap实现的）</li></ul><div>20. linux下pmap可以查看某进程的vm映射情况，因此，也就能知道栈、堆、各elf文件的page用量</div><div><br>
</div><div>20. linux下getrusage函数(查看resource usage)，可以查看当前进程、当前线程或者所有子进程的resident set用量、中断数、上线文切换数等信息</div><div><br>
</div><div>20. 深入理解计算机系统，第10章，第0节</div></div></div><div><ul><li>没有VM(virtual memory)的问题：</li><li style="list-style: none; display: inline"><ul><li>物理内存有限，可能不够用</li><li>其他进程占用内存太多可能导致你的进程申请不到内存</li><li>其他进程的非法内存访问(如内存越界)可能导致你的进程内存被破坏</li></ul></li><li>VM是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它提供了以下优点：</li><li style="list-style: none; display: inline"><ul><li>大。将主存看成是磁盘上的VM的cache，主存中只保存活跃的区域，在主存和磁盘间来回传递数据</li><li>一致。每个进程一致的内存空间，简化了管理</li><li>私有。保护每个进程的地址空间不被其他进程破坏</li></ul></li><li>程序员理解VM的好处</li><li style="list-style: none; display: inline"><ul><li>VM贯穿计算机系统的所有层面，包括硬件异常、汇编器、链接器、加载器、共享对象、文件和进程</li><li>VM提供了强大的能力，包括创建、销毁存储器块，将存储器块映射到文件，以及与其他进程共享</li><li>VM也容易被误用，了解VM，了解malloc包，可以在一定程度上避免这些错误</li></ul></li><li>本章主题主要包括：了解VM的作用；了解VM怎样工作；了解VM怎样被管理</li></ul><div>20. 深入理解计算机系统，第10章，第1节，物理和虚拟寻址</div></div><div><ul><li>早期PC，以及现在的部分DSP、微控制器、超级计算机，还在使用物理寻址: CPU->PA(physic address)->地址总线->主存/cache->数据->数据总线->register</li><li>现在PC一般使用虚拟寻址: CPU->VA(virtual address)->MMU(memory management unit，进行address translate)->PA->地址总线->cache/内存->数据->数据总线->register</li></ul><div>20. 深入理解计算机系统，第10章，第2节，地址空间</div></div><div><ul><li>linear address space: 地址空间中值是连续的</li><li>PAS(physic address space): 物理地址空间，由存储器容量决定</li><li>VAS(virtual address space): 虚拟地址空间，由CPU的地址总线位宽决定，常见有32位和64位</li></ul><div>20. 深入理解计算机系统，第10章，第3节，虚拟存储器作为缓存工具</div></div><div><ul><li>概念上，VM是磁盘上的一个数组，主存是VM的cache，它们之间的传输单元是page(启动前可以修改cpu配置来调整)，VM被组织为virtual page，主存被组织成physical page</li><li>一个VP可以有3种状态：未分配；缓存在主存中(有对应的PP)；没缓存，在磁盘上</li><li>DRAM比SRAM慢10+倍，disk比DRAM慢10w+倍；因为DRAM的miss代价很大，所以：</li><li style="list-style: none; display: inline"><ul><li>virtual page很大，4~8KB</li><li>DRAM是fully assocative cache，这样，任意virtual page可以和任意physical page关联</li><li>DRAM的replacing算法很复杂(发生在page fault时)</li><li>DRAM采用write-back替换算法</li></ul></li><li>page table。页表是一个page table entry的数组，其中索引是虚拟地址中除去低位的VPO(virtual page offset)后剩下的高位VPN(virtual page no)。每个PTE包括以下内容：valid位；PPN位向量(该虚拟页所映射到的物理页号)；读/写/执行标识、超级模式(内核地址段还是用户地址段)、是否已修改、是否在内存中等标记。原则上，如果PTE中标记该VP在主存中，则可以访问，否则应该触发page fault，让OS去判断是否是无效的地址访问还是应该从磁盘上换页</li><li>page fault时，如果OS判断地址合法，则根据算法选择要换掉的页，写回，换入，修改PTE，最后让触发page fault的指令重新执行</li><li>因为VM发明得很早(60年代)，所以使用了一套有别于SRAM的术语</li><li>DRAM和disk之间的页传输，叫交换(swapping)或者页调度(paging)</li><li>分配页面：在磁盘上分配VP，更新PTE和内核状态，直到第一次访问该page时触发page fault才进行swapping，将页面调入主存</li><li>由于locality的存在，程序在任意时刻访问的内存趋向于在一个小的active page集合中，即working set，或者叫resident set。如果程序的locality不够好，working set超过了主存，则会进行大量的swapping，这叫做颠簸(thrashing)</li></ul><div>21. 深入理解计算机系统，第10章，第4节，虚拟存储器作为存储器管理的工具</div></div><div><ul><li>早期的OS，比如DEC的PDP-11/70，它的VM甚至比主存小，它主要是提供本节所提到的管理上的便利</li><li>VM在管理方面的优点:</li><li style="list-style: none; display: inline"><ul><li>简化链接: 由于每个进程都有相同的VAS而不关心PA，所以每个linux进程内的数据段布局都是一样的，因此链接elf时很方便</li><li>简化加载: 加载elf时，系统并不真正的拷贝elf的段进主存，它只是设置相应的PTE，标记为未缓存的，直到第一次引用elf的段才由page fault handler加载文件内容</li><li>简化分配: 当进程需要大小为k的连续内存时，OS更容易提供连续的大小为k的VM，其对应的PM可能不连续。共享的PAS比私有的VAS更难分配大的连续空间</li><li>简化共享: VM可以通过将多个进程的各自的VP映射到相同的PP和磁盘文件，从而跨进程共享数据。内核代码、数据以及用户态的动态链接库，往往都是需要共享的</li></ul></li></ul><div>21. 深入理解计算机系统，第10章，第5节，虚拟存储器作为存储器保护的工具</div></div><div><ul><li>现代计算机系统应该为OS提供存储器保护手段来控制访问，比如:</li><li style="list-style: none; display: inline"><ul><li>不能写只读、文本段</li><li>不能读写内核代码和数据</li><li>不能访问其他进程私有存储器</li><li>未经其他共享者许可，不能修改共享数据(比如copy-on-write)</li></ul></li><li>PTE上有相关的许可位来控制访问，如读写许可、内核存储器访问许可等，如果访问非法，触发segmentation fault</li></ul><div>21. 深入理解计算机系统，第10章，第6节，地址翻译</div></div><div><ul><li>address translation: 将VA翻译成PA或者空</li><li>VA可以被分为: VPN和VPO，其中VPO和PPO相同，VPN会被MMU借助TLB、page table翻译成PPN</li><li>TLB是一种cache，一般实现为k-way set associative cache，它的输入是VPN，输出是PTE；VPN被划分为tlb tag, tlb idx，其中tlb idx用于set selection, tlb tag用于进行line match。一般TLB较小，比如i7的TLB是4-way的，总共只有16个set，因此只能缓存64个PTE。TLB之所以不需要太大，是因为，address translation实际需要翻译的只是page no，因此，需要cache的只是几个访问频繁的页，加上iTLB和dTLB一般还是分开的，hit rate就更高了，比如，一段数组访问算法，当访问的数组元素位于同样的4k内时，TLB全部会命中的，因为VPN相同。</li><li>CPU将page table的基址(PA)放在page table base register中，当需要进行页表查询时，MMU将PTBR+VPN得到的PTE物理地址发给cache/主存，请求PTE内容，进行进一步翻译</li><li>多级页表: 考虑32位系统，page size为4k，则VPO是12位，于是VPN是20位，又因为PTE是4字节，所以page table将达到4*1M=4M字节，单进程的页表达到4M字节，对OS压力太大，所以用分级页表。考虑2级页表，VPN被划分为VPN1, VPN2，各10位，1级页表是4*1K=4K字节，可以常驻主存，2级页表有1024个，每个也是4K；地址翻译的时候，MMU->PTBR+VPN1->cache/DRAM->PTE1->PTBR2+VPN2->cache/DRAM->PTE->PPN；如果所有的VM都被分配完，2级页表的页表总空间需要4K+1024*4K=4M+4K，比1级页表稍大，但因为4G的VAS一般使用有限，大量的2级page table都不需要分配(即大量的PTE1指向为空), 所以实际的页表消耗是4K+n*4K，其中n=分配的VM总大小/4M。2级页表比1级页表省了大量的页表内存占用，翻译速度会稍慢，但由于address translation本来就会被TLB大量的缓存下来，所以速度问题不是问题。64位系统可能需要更多级的页表</li><li>32位系统中page size是4k, VPO是12位，为了让address translation和访存同时进行，L1 cache会在VA->PA映射的同时直接拿着VPO(==PPO)进行set selection。比如P4的L1是128个set+32字节的cache line, 因此set selection刚好需要12位；同样，当i7的L1 cache是64个set+64字节的cahe line，也是12位。故address translation和L1 cache的set selection可以同时进行</li><li>address translation过程: </li><li style="list-style: none; display: inline"><ul><li>第1步，拿到PTE:(其中涉及的PTBR都是physical address)</li><li style="list-style: none; display: inline"><ul><li>CPU->VA->MMU->VPN->TLB->hit->PTE (绝大部分合法访存都会走这个分支)</li><li>CPU->VA->MMU->VPN->TLB->miss->PTBR+VPN1->cache/DRAM(可能cache miss等)->PTE1->PTBR2+VPN2->cache/DRAM(可能cache miss)->PTE</li><li>CPU->VA->MMU->VPN->TLB->PTE1 hit->PTBR2+VPN2->cache/DRAM(可能cache miss)->PTE</li><li>CPU->VA->MMU->VPN->TLB->miss->PTBR+VPN1->cache/DRAM(可能cache miss等)->PTE1->2级页表没有分配，非法VA，segmentation fault (这条分支是猜想)</li></ul></li><li>第2步，访问PTE</li><li style="list-style: none; display: inline"><ul><li>PTE->没有访问权限->segmentation fault</li><li>PTE->物理内存中->PPN+PPO->cache/DRAM(可能cache miss)->data->register</li><li>PTE->没在物理内存中，page fault->page fault handler->VA没有在任何段中，segmentation fault</li><li>PTE->没在物理内存中，page fault->page fault handler->VA在某段中，并且访问权限合法，则开始paging: 选择换出页、写回、换页、更新PTE、重新执行访存指令</li></ul></li></ul></li></ul><div>21. 深入理解计算机系统，第10章，第7节，案例研究: Pentium/Linux存储器系统</div></div><div><ul><li>pentium的processor package包括CPU、unified L2 cache + cache bus、iTLB、dTLB、L1 i-cache、L1 d-cache。所有TLB和cache都是4-way set associative的。page size可以在启动时配置成4K或者4M。iTLB有32行，dTLB有64行。</li><li>pentium使用两级页表，其中第1级页表叫page directory，因此PTE1叫做PDE，PTBR叫做PDBR</li><li>pentium的PTE中除了PPN外，还包含这些信息: 是否在物理存储器中；只读或者读写；是否要求内核访问许可；write-back还是write-through策略；缓存禁止/启用；页被读过吗；页被写过吗；页大小4k or 4M；常驻TLB吗。其中写标识用于区分dirty page，在swapping的时候改页需要write-back。pentium的PTE没有执行权限位，所以无法避免缓冲区溢出攻击，i7已经有了</li><li>pentium的TLB可以缓存PTE或者PDE</li><li>位于linux进程的0xc0000000之上的内核空间，包括所有进程共享的内核数据和代码，也包括进程私有的内核栈、页表、文件句柄等结构</li></ul><div>21. 深入理解计算机系统，第10章，第8节，存储器映射(memory mapping)</div></div><div><ul><li>注意存储器映射的一个特征: 只在PTE中记录映射关系，第一次访存的时候才加载文件内容</li><li>memory mapping一般用在两种文件上:</li><li style="list-style: none; display: inline"><ul><li>命名文件: </li><li style="list-style: none; display: inline"><ul><li>高效的读写任意文件</li><li>只读(copy-on-write)的方式加载elf的各个段</li></ul></li><li>匿名文件：用于分配进程私有的VM，如栈、堆、.bss段等</li></ul></li><li>私有段可能被共享，如fork或用execv加载同一个elf，如果在这样的私有共享段上进行写操作，会发生copy-on-write。考虑一个copy-on-write的实现:</li><li style="list-style: none; display: inline"><ul><li>一旦fork或者execv同一个文件，则其中readonly段不动，readwrite需要特殊处理: 将readwrite段的PTE标记改为readonly，并且在内核中标记该物理页被多少个进程共享，每发生一次写操作，写进程当场copy物理页，修改自己的PTE的指向和readwrite标记，内核减小源物理页的计数，如果计数>1，无特殊处理，如计数==1，则将唯一引用进程的PTE标识改为readwrite，至此该物理页不再被共享</li></ul></li><li>fork过程: 在内核中创建共享结构，记录该进程的pid、段结构等；拷贝文件句柄；拷贝页表，readonly页无特殊处理，copy-on-write的readonly页需要增加内核计数(这是在维护copy-on-write机制)，readwrite页改为readonly并将父进程页表项也改为readonly同时维护内核引用计数(这是在创建copy-on-write机制); </li><li>execv过程: </li><li style="list-style: none; display: inline"><ul><li>删除已有的段和页表; 文件句柄保持</li><li>对执行文件建立存储器映射: 以私有共享方式映射.init、.text、.rodata段到执行文件相应段；以私有共享方式(copy-on-write)映射.data段到执行文件.data段；以私有方式映射.bss段、栈、堆到匿名文件</li><li>对动态库如libc.so、libstdc++.so建立映射</li><li>设置eip到.init中的入口函数main</li></ul></li><li>mmap, mumap的使用</li></ul><div>21. 深入理解计算机系统，第10章，第9节，动态存储器分配</div></div><div><ul><li>unix内核维护了一个堆尾指针，叫brk，紧跟.bss段，用sbrk()和brk()操作，出于portable考虑，不要直接使用它</li><li>分配器有两种风格:</li><li style="list-style: none; display: inline"><ul><li>显示分配器，explicit allocator，比如c中的malloc包，比如c++中的new/delete</li><li>隐式分配器，implicit allocator，又叫garbage collector，自动释放未使用的已分配快的过程叫garbage collection</li></ul></li><li>malloc/free可以用mmap/munmap或者sbrk来实现</li><li>各系统的malloc函数，可能会出于内存对齐考虑，返回对齐指针。比如linux下，malloc返回8字节对齐指针。因为c语言的所有访问最终会落实到对基本类型的访问，所以struct的对齐要求最终也只是基本类型对齐，而基本类型，long long是最大的，8字节对齐足矣。由于近来SIMD指令集的兴起，它对内存有特殊对齐要求，如SSE的16字节，如AVX的32字节，在windows下，malloc似乎是16字节对齐的。</li><li>explicit allocator应该满足:</li><li style="list-style: none; display: inline"><ul><li>处理任意顺序、任意大小的分配/释放请求。顺序、大小都任意，这是造成allocator难以实现的主要原因。如果顺序有规律，比如集中分配后集中释放，则可以用最简单的单指针memory loop(类似auto release pool)；如果大小有规律，比如fixed size，则可以用单向链表的free-list实现</li><li>立即返回。不能缓存请求</li><li>对齐。可能要求双字对齐等(这里的双字是广义双字，而非x86中的双字，x86下的dword是受8086的16位影响，所以只有4字节)</li><li>不能修改已分配块。比如不能进行compact</li></ul></li><li>explicit allocator的目标:</li><li style="list-style: none; display: inline"><ul><li>最大化吞吐率</li><li>最大化存储器利用率。payload / (overhead + internal fragmentation + external fragmentation)要最大</li></ul></li><li>往往，牺牲VM利用率可以提高吞吐率。考虑最简单的实现: 保存一个指针, malloc时，p += size， free时，什么都不干</li><li>内存碎片</li><li style="list-style: none; display: inline"><ul><li>internal fragmentation: 内部碎片。指已分配快中除去overhead(header + footer)和payload(有效负载)之外的部分。可能是因为对齐要求而存在</li><li>external fragmentation: 外部碎片。这是相对概念，当空闲链表中的空闲块，不足以满足之后的分配请求size时，这叫外部碎片</li></ul></li><li>explicit allocator的实现问题:</li><li style="list-style: none; display: inline"><ul><li>怎样遍历空闲链表(free list)</li><li>怎样选择空闲块来分配。</li><li style="list-style: none; display: inline"><ul><li>first fit，首次适配</li><li>next fit, 每次适配后，保存位置，下次分配时从该位置继续。速度较快，但利用率稍低</li><li>best fit, 找最合适的块</li></ul></li><li>是否分割</li><li>释放后是否合并块</li></ul></li><li>隐式空闲链表(implicit free list)</li><li style="list-style: none; display: inline"><ul><li>按8字节对齐，每个块是n个双字，header是4字节，高29位保存size，低3位保存是否是已分配快</li><li style="list-style: none; display: inline"><ul><li>malloc: 根据header中的size，遍历所有的分配/空闲块，找到空闲块后修改分配标识。可以分割。如果空闲块不够，可能需要向OS额外申请堆</li><li>free: 将块的标识改为未分配。</li><li>合并: free的时候可以合并下一个空闲块；mallo的时候遍历free list时顺便合并</li></ul></li><li>改进1: 引入boundary tag(边界标记，knuth提出)。增加一个和header一模一样的footer，这样free的时候直接就可以合并前后块</li><li>改进2: 在header的低3位中，拿一位来存储前一块的分配标记，这样，可以省掉已分配快的footer</li></ul></li><li>显示空闲链表(explicit free list)</li><li style="list-style: none; display: inline"><ul><li>隐式列表的缺点是，分配时间和总块数成正比，如果我们能将free块链接起来，那么malloc就只跟free list长度成正比了</li><li>在free block的header后增加一个next指针。则malloc没问题，free也可以把新的free block加到list头上，但是无法合并</li><li>在free block的header后追加prev、next两个指针。malloc没问题，free的时候，如果需要合并，将前后free block从free list中断开，和新free块合并，再链到list开头</li></ul></li><li>简单分离空闲链表: 多个fixed-size memory loop，每个应对不同size的请求</li><li>适配分离空闲链表: 是explicit free list的改良，GNU malloc包既是这种实现</li><li style="list-style: none; display: inline"><ul><li>有多个free list，每个应对不同size请求 </li><li>malloc: 从小到大的遍历每个free list，如果找不到满足要求的，扩展堆，将新的大block放入最后的free list，重新malloc；如果找到匹配的block，分割，将剩余块放入对应的较小free list</li><li>free: 检测前后block，将前后block从原链中断开，合并，将新的block加入到大小合适的free list中</li></ul></li><li>buddy system: 优点是free时，容易计算buddy block从而合并。由于block都是2^n的size，内部碎片比较严重，适合特殊场合下的分配需求</li></ul><div>21. 深入理解计算机系统，第10章，第10节，垃圾收集</div></div><div><ul><li>mark and sweep是John McCarthy在20世纪60年代在MIT开发早期Lisp时提出的，由于它不需要移动指针，因此可以用作C/C++的保守垃圾回收。这里的保守，是指，有些正常数值被当做指针，从而一些已分配block被认为被引用，不能释放</li><li>garbage collector将存储器视为一张reachability graph，会自动将不可达的节点回收掉。ML、Java中，创建和使用指针有严格控制，故可以推算出精准的可达图，从而正确回收所有垃圾；而c/c++由于支持指针的算术运算和类型转换，故只能进行conservative garbage collection</li><li>mark and sweep的实现:</li><li style="list-style: none; display: inline"><ul><li>在已分配的block的header低3位中，保存marked位，表示已经标记</li><li>函数isPtr: 输入一个数，判断它是否是堆中的一个已分配块的payload部分地址，如果是，则返回已分配块的基址，否则返回NULL。注意，要实现这个isPtr可能比较困难，一种方法，在已分配block的header后追加left、right指针，将所有已分配节点组织成二叉树，然后从根节点开始查找isPtr的参数，找到比该数小的已分配节点后，看该值是否在节点的size范围内</li><li>函数mark: 输入一个数，如果isPtr为NULL，return；如果isPtr返回的block是marked，return; 标记该block为marked，遍历该block的payload中每个字，递归调用mark</li><li>函数sweep: 遍历allocator里的每个已分配block，如果marked，则标记为unmarked；如果是unmarked，则置为free block</li><li>最后，标记和清扫:</li><li style="list-style: none; display: inline"><ul><li>对所有的全局变量和栈(包括寄存器)调用mark</li><li>调用sweep</li></ul></li></ul></li></ul><div>21. 深入理解计算机系统，第10章，第11节，c程序中常见的存储器相关错误</div></div><div><ul><li>间接使用坏指针。比如scanf("%d", i)，结果scanf将i的值当指针，如果i恰好装了一个合法地址，则内存被破坏，可能很久后才crash</li><li>读未初始化内存</li><li>缓冲区溢出。 如gets，应该用fgets</li><li>指针元素类型错误。比如，分配二维数组中的第一维应该是malloc(sizeof(int*) * 10)，而不是malloc(sizeof(int) * 10)</li><li>off-by-one错误</li><li>错误指针运算。比如遍历整形数组，应该是pi++而不是pi += sizeof(int)</li><li>引用无效变量。比如返回局部变量地址</li><li>引用已释放内存。比如free(p); *p = 5;</li><li>memory leaks</li></ul><div>21. C++ project: Simple timing wheel</div></div><div><br>
</div><div>21. CSAPP: malloc lab, implicit free list</div><div><br>
</div><div>22. gproftools: tcmalloc。使用:</div><div><ul><li>法1: link TCMalloc into your application via the "-ltcmalloc" linker flag<br>
</li><li>法2: You can use TCMalloc in applications you didn't compile yourself, by using LD_PRELOAD: $ LD_PRELOAD="/usr/lib/libtcmalloc.so" . LD_PRELOAD is tricky, and we don't necessarily recommend this mode of usage.<br>
</li></ul><div>22. CSAPP: malloc lab, explicit free list, best fit</div></div><div><br>
</div><div>23. CSAPP: malloc lab, my tcmalloc</div><div><br>
</div><div>24. 深入理解计算机系统，第11章，第0节</div><div><ul><li>IO是主存和外部设备(磁盘、终端和网络)间进行数据传输的过程。输入是从IO设备拷贝到主存，输出是从主存拷贝IO设备</li><li>有了ANSI C的IO还要学习Unix IO的原因:</li><li style="list-style: none; display: inline"><ul><li>了解Unix IO有助于理解其他系统概念。例如在存储器结构、链接、加载、进程、虚拟存储器、文件共享中，都设计系统IO</li><li>有的时候ANSI C的IO不合适。比如磁盘、终端的IO可以用ANSI C，但socket更应该用UNIX IO</li></ul></li></ul><div>24. 深入理解计算机系统，第11章，第1节，UNIX IO</div></div><div><ul><li>打开文件。open函数返回一个文件描述符(descriptor)，<unistd.h>里定义了常量STDIN_FILENO、STDOUT_FILENO、STDERR_FILENO</li><li>改变当前位置。lseek</li><li>读写文件。read, write</li><li>关闭文件。close。结束进程时，系统会自动关闭没有关闭的文件</li><li>设置文件长度。ftruncate</li></ul><div>24. 深入理解计算机系统，第11章，第2节，打开和关闭文件</div></div><div><ul><li>open。flags参数包含O_RDONLY, O_WRONLY, O_RDWR以及O_CREAT, O_TRUNC, O_APPEND。mode参数可以指定S_IRUSER, S_IRGRP, S_IROTH等用户权限(对应的写和执行权限是S_IWUSR, S_IXUSR)</li><li>umask。设置一组全局的mode掩码(仍然是S_IRUSE、S_IWGRP等)，实际open时的mode会& ~umask。</li><li>close。关闭已经关闭的描述符会出错</li></ul><div>24. 深入理解计算机系统，第11章，第3节，读写文件</div></div><div><ul><li>有些时候read、write不能成功传输我们要求的长度: </li><li style="list-style: none; display: inline"><ul><li>磁盘: read只被EOF打断；write总是完全拷贝</li><li>终端: read时可能被行尾、EOF打断</li><li>网络: 除了read被EOF打断外，read、write都可能因内部缓冲区长度、超时打断</li></ul></li><li>总结，UNIX IO下，只有磁盘能够保证传输长度；网络可能被各种打断</li><li>read/write函数失败时返回-1，一个特殊的失败情况errno == EINTR是系统调用被interrupt打断，属于正常情况，应该容错。当然，系统调用不能自动重启这种事情，只在部分unix上会有，linux不会发生</li></ul><div>24. 深入理解计算机系统，第11章，第4节，用Rio包进行健壮读写</div></div><div><ul><li>rio提供两组函数:</li><li style="list-style: none; display: inline"><ul><li>无缓冲函数: 主要处理特殊设备(如网络)被意外打断的问题；经过rio_readn/rio_writen包装过后的read/write，能够传输n字节不被打断，除非遇上EOF</li><li>带缓冲函数: 因为主存<->设备间一般需要按一定的对齐(比如磁盘IO的页对齐，socket可能是max(内部缓冲对齐，页))来传输才能达到减少IO操作次数最优性能的目的，所以带缓冲IO能有效的减少系统调用次数，尤其当应用请求是大量小buffer的读写或者需要在输入中查找特殊字符(如readline)时尤为有效。rio包用rio_read包装了read函数提供了带缓冲但易打断的包装，再在rio_read的基础上提供了rio_readnb、rio_readlineb这两个分别读写文本和二进制的io函数，前者的语义是带缓冲不被打断(除了EOF)，后者是带缓冲读一行。</li></ul></li></ul><div>24. 深入理解计算机系统，第11章，第5节，读取文件元数据</div></div><div><ul><li>stat, fstat。其中st_mode字段，包括了权限(S_IRUSR等)和文件类型，其中文件类型用S_ISREG、S_ISDIR、S_ISSOCK判断</li></ul><div>24. 深入理解计算机系统，第11章，第6节，共享文件</div></div><div><ul><li>unix文件有三个级别的概念：</li><li style="list-style: none; display: inline"><ul><li>v-node table。内核中，所有进程共享。每个元素唯一标识一个打开的磁盘文件, stat相关信息都存储在这里</li><li>file table。内核中，所有进程共享。每个元素包括了引用计数(被进程的descriptor table引用)和当前读写位置。每open一次会创建一项(因为open返回的对象有独立的读写位置)，如果open的是同一个文件，则会是file table->v-node table上的2对1关系</li><li>descriptor table。进程独占的内核空间中。stdin、stdout、stderr分别是0, 1, 2。open总是返回最小的descriptor，因此close后再open，返回的是同样的descriptor值，只是指向不同的文件。fork、dup2，会形成descriptor table->file table上的多对一</li></ul></li><li>例子:</li><li style="list-style: none; display: inline"><ul><li>open("1.txt"), open("1.txt"): descriptor table、file table都有两项，但v-node table只有一项</li><li>open('1.txt'), dup2(newFd, 1): descriptor table有两项，file table只有一项(ref count为2)，v-node table只有一项</li><li>open('1.txt'), fork(): 两个进程的descriptor table各有一项，其值相同，file table只有一项(ref count为2)，v-node table只有一项</li></ul></li></ul><div>24. 深入理解计算机系统，第11章，第7节，IO重定向</div></div><div><ul><li>dup2(oldfd, newfd): 将oldfd上的file table指针覆盖到newfd位置上，如果newfd已经打开则会先关闭(因此如果关闭的时候newfd上的旧文件ref count为1，则会导致file table、v-node table的元素被内核回收)。如dup2(file1fd, 1)，会导致stdout被重定向到file1上</li><li>freopen(const char *fname, const char *mode, FILE *f): 语义同dup2一样, f会被重定向到fname对应的文件上，即，dup2(fnamefd, fileno(f))</li></ul><div>24. 深入理解计算机系统，第11章，第8节，标准IO</div></div><div><ul><li>ANSI C的IO函数都是带缓冲的，可以用setbuf来设置自定义缓冲(否则，在FILE上的首次IO会导致malloc一个BUFSIZ大小的缓冲(实现相关，可能是8k))或者关闭缓冲</li><li>既然ANSI C的函数都有缓冲:</li><li style="list-style: none; display: inline"><ul><li>fgetc来读文件并拷贝，性能差并不是因为IO次数多而是函数调用次数多(如果fgetc被实现为宏，则是微操作太多)</li><li>fread的buf大小不太重要，只要不小到像fgetc那样调用次数过多就行</li></ul></li></ul><div>24. 深入理解计算机系统，第11章，第9节，综合: 该用哪些IO函数</div></div><div><ul><li>文件、终端IO: 用ANSI C，后者提供了较完整、健壮的带缓冲IO</li><li>网络(socket): 像rio那样，自己封装带缓冲、不被打断的IO</li></ul><div>24. C++ project: buffered file</div></div><div><br>
</div><div>24. CSAPP: malloc lab, c++ implemention of my tcmalloc</div><div><br>
</div><div>25. URI vs URL</div><div><ul><li>一般来说:</li><li style="list-style: none; display: inline"><ul><li>URI: Uniform Resource Identifier (URI) is a string of characters used to identify a name or a resource on the Internet An URI identifies a resource either by location, or a name, or both. A URI has two specializations known as URL and URN.<br>
</li><li>URL: An Uniform Resource Locator (URL) is a subset of the Uniform Resource Identifier (URI) that specifies where an identified resource is available and the mechanism for retrieving it.URL defines how the resource can be obtained. It does not have to be HTTP URL (http://), a URL can also be (ftp://) or (smb://)<br>
</li><li>URN: An Uniform Resource Name (URN) is a Uniform Resource Identifier (URI) that uses the URN scheme, and does not imply availability of the identified resource. Both URNs (names) and URLs (locators) are URIs, and a particular URI may be both a name and a locator at the same time.<br>
</li></ul></li><li>http请求头中的request line中的URI:</li><li style="list-style: none; display: inline"><ul><li>Request-URI = "*" | absoluteURI | abs_path | authority<br>
</li><li>因此，当用户在浏览器中输入URL过后，浏览器根据主机定位到http服务器，然后发出http请求，在请求的request line中，可能只使用了形如"/index.html"这样的相对路径，但在这个语境下，它也是相对目标主机的一个URI，虽然就内容而言，它只是客户端的URL的一个字串</li></ul></li></ul><div>25. 通信中的单工、半双工、全双工</div></div><div><ul><li>单工(simplex): 数据只能单向传输，如电视、广播、传呼机</li><li>半双工(half duplex): 具备双向传输的能力，但任意时刻只能单向，如对讲机</li><li>全双工(full duplex): 可以同时双向传输，如电话、网络</li></ul><div>25. gethostbyname, gethostbyaddr在windows/linux下用了试试，有一定区别，尤其是windows下只有inet_addr没有inet_aton</div><div><br>
</div><div>25. telnet可以很方便访问各种基于tcp的文本服务器，比如基于http的web服务器。但是telnet主要还是用于交互式，脚本化的话，会比较丑陋，需要sleep: "(echo "GET / HTTP/1.0\n"; sleep 1) | telnet <a href="http://www.baidu.com/" target="_blank">www.baidu.com</a> 80"。更好的脚本化的http调试工具还是curl</div></div><div><br>
</div><div>26. 深入理解计算机系统，第12章，第1节，客户端-服务器编程模型</div><div><ul><li>大多数网络应用都是基于客户端-服务器模型，即一个服务器进程管理某种资源，并通过操纵这种起源来提供服务，而多个客户端进程并发的访问服务。所谓一个客户端-服务器事务(这里的事务不是数据库上的transaction概念，没有ACID的约束)包括:</li><li style="list-style: none; display: inline"><ul><li>客户端发送request</li><li>服务器接收request，并处理请求</li><li>服务器返回response</li><li>客户端接收响应并处理</li></ul></li><li>FTP服务器主要是管理文件；SMTP服务器读邮件；而Web服务器(WWW，万维网服务器)除了处理一般的文件，更重要的支持一种特殊的带超链接的格式HTML，而这种特殊文件可能静态、动态生成，使用的协议是一种文本协议HTTP</li></ul><div>26. 深入理解计算机系统，第12章，第2节，网络</div></div><div><ul><li>对一个主机而言，网络是又一种IO设备，对它的读写，实际上是网络适配器和存储器间通过DMA进行的数据传输</li><li>物理上，网络按照地理远近组成一个层次系统，最低的层次是LAN(local area network)，更高层的是WAN(wide area network)。LAN的一个流行技术是诞生自70年代施乐的以太网(Ehternet)，而WAN的主流技术是TCP/IP的Internet(Internet是一种WAN的实现，而internet是广义的互联网概念)，后者由美国军方推动，实际使用更早。</li><li>最简单的Ehternet设备是hub，它将一个网段(Ehternet segment)的主机连接起来，无条件的将一台主机发出的数据拷贝给其他主机，接收主机自己根据MAC地址判断是否处理。主机上的以太网适配器都有一个全球唯一地址MAC</li><li>网桥(bridge)可以用来将多个以太网段连接成一个更大的局域网，叫做Bridged Ethernet，网桥会通过一种聪明的分配算法，来有选择的将源数据拷贝到目标主机，非目标主机直接不传输数据</li><li>将hub、bridge不加区别的看做LAN，那么，路由器(router)可以将多个LAN连接成WAN</li><li>WAN允许每个LAN使用不同的LAN协议，因此，需要router通过协议软件封包公共的WAN协议。设计WAN要考虑的问题: 兼容不同的LAN；router怎么查找下个节点；路由规则变化过后怎么通知router；包丢了怎么办...</li><li>例子:</li><li style="list-style: none; display: inline"><ul><li>局域网A主机发数据给B主机: 将数据封包成IP包->IP层判断是内网IP，则查询目标IP对应的MAC，封包链路包->hub群发包->B主机判断目标MAC等于本机，所以拆包->IP层拆包给应用层</li><li>局域网W1的主机A经过WAN发数据给局域网W2的主机B: 封IP包->IP层判断非内网IP，则查询网关的MAC，封链路包->hub群发->网关拆包，查询bridge层的网关MAC，封链路包->bridge定向传输数据到WAN网关(router)->router拆链路包，查询目标IP应该到的下一个router节点的MAC，封链路包->...->目标router拆包，进行NAT映射，将目标的WAN IP:PORT1转换成LAN IP:PORT2->bridge定向从网关到hub->hub群发->B主机拆包</li></ul></li><li>考虑NAT的意义:</li><li style="list-style: none; display: inline"><ul><li>无NAT时: 把局域网IP简单的考虑成xx.xx.xx.IP，那么ipv4其实是支持了3个字节那么多个局域网，即32位的高24位是LAN No，低8位是LAN offset，总接入设备只有4字节那么多</li><li>有NAT时: 如果LAN IP总是0.0.0.IP，而非0.0.0.IP的情况都是WAN IP，那么，WAN IP其实是2^32-256个，而实际的主机IP是xx.xx.xx.xx:0.0.0.IP，这样，总共接入的主机是5字节那么多。但是TCP/IP协议中，地址只包括IP+PORT总共6字节，怎么办到的呢？其实等价于占用了端口号的2字节中的1字节，可利用端口变少了。极端情况下，256台LAN主机都存在，那么，支持NAT后，虽然只使用了一个WAN IP，但是每台主机平均只能用256个端口了。当然因为NAT的端口映射是动态的，而且256个主机一般也占不满，所以可用端口还是比较多的。</li><li>各种技术实质上支持接入的主机数：ipv4->ipv4+NAT->ipv6 => 2^(4*8)->2^(5*8)->2^(6*8) (这里基于LAN offset总是只占1字节的假设模型，现实中有不同)；当然用了NAT后，平均可用端口数从2^(2*8)减少到2^(1*8)了</li></ul></li><li>A/B/C这样的分类IP地址划分已经过时，现在是无类别域间路由(CIDR, classless inter-domain routing)也叫变长子网掩码(VLSM, variable length subnet mask)</li></ul><div>26. 深入理解计算机系统，第12章，第3节，全球IP因特网</div></div><div><ul><li>TCP/IP的特点:</li><li style="list-style: none; display: inline"><ul><li>IP(Internet protocal)是不可靠的(可能重复、丢包)，负责将数据从一台主机传输到另一台主机</li><li>UDP在IP基础上扩展，使数据在两台主机的两个进程间传输，仍然不可靠</li><li>TCP(transmission control prototcal)在IP基础上扩展，提供可靠、全双工的进程间数据传输</li></ul></li><li>socket interface典型的是作为系统调用来实现的，调用时会trap到内核</li><li>一般因特网传输数据是大端法，hton, ntoh是在本地顺序和因特网顺序间转换</li><li>hostname -i可以看到自己的IP: "127.0.0.1"</li><li>inet_aton、inet_ntoa，可以在整数IP和"xx.xx.xx.xx"格式IP间转换。这里的a、n分别是application、network</li><li>域名(domain)是按树来组织的，从根节点到叶节点，典型的层次是"国别(cn,en)->机构类型(com,edu,org,gov)->机构(mit,berkeley,amazon)->部门->人"，在URL中以反向遍历的形式出现。直到1988年，domain->IP的映射都是通过一个HOSTS.TXT手工维护的，后来才替换成DNS系统的数据库。DNS中的每个主机，是这样的一个结构"主机名+alias列表+ip列表"，用gethostbyname、gethostbyaddr可以分别通过域名和IP获得。在unix下，gethostbyname/gethostbyaddr返回的ip列表顺序、内容都可能变，起到负载均衡的作用。localhost是一个特殊域名，总是映射到本地回送地址(loopback address)127.0.0.1。</li><li>TCP通过连接(connection)在两个进程间通信，connection是点对点(point to point)的、双工的、可靠的，socket是conneciton一端的端点(end-point)，由IP+PORT的地址标记</li></ul><div>26. 深入理解计算机系统，第12章，第4节，套接字接口</div></div><div><ul><li>socket interface是伯克利在80年代提出的，通过Unix 4.2BSD内核分发给学校和实验室，影响广泛</li><li>最初设计socket api时，为了兼容各种WAN实现，所以socket地址使用的是通用结构sockaddr(当时的c语言没有void*)，WAN类型甚至都可配置；但今天，其他WAN都出局，只剩下IP，所以实际用到的是sockaddr_in(这里的in是internet network的意思)和AF_INET</li><li>shutdown可以单独控制关闭read/write/readwrite</li><li>可以用setsockopt配置SO_REUSEADDR来允许立即终止和重启，方便调试</li><li>socket()创建描述符后，默认是主动模式，通过listen将主动套接字转化为监听套接字</li><li>服务端socket api在设计上区分listen套接字和connected套接字，是为了支持并发</li><li>阻塞的进行accept->serve->close的服务器叫iterative server，相对的，同时服务多个客户端的叫concurrent server</li><li>EOF只是内核检测到的一种状态，并不是真正的字符</li><li style="list-style: none; display: inline"><ul><li>对于磁盘，读到文件尾内核触发EOF</li><li>对于网络，对方close会收到EOF</li></ul></li></ul><div>26. 深入理解计算机系统，第12章，第5节，web服务器</div></div><div><ul><li>web服务器和ftp服务器的主要区别是，web服务器使用http协议，可以静态、动态生成html内容。html的最大特色是支持超链接</li><li>www的兴起: 1989~1991年，瑞典的CERN(欧洲离子物理研究所)的工程师设计出了万维网(重要特色是分布式的超链接系统)，用于帮助科学家管理和共享资料；1993年，网景(netscape)创始人发布了能在windows/unix/macintosh下运行的图形化浏览器，于是web爆发了</li><li>web的内容是mime(multipurpose internet mail extensions)类型相关的字节序列，常见的mime包括: text/pain, text/html, image/jpge, image/gif, application/postscript等。web服务器提供这些内容的方式包括读静态文件和执行网关程序动态生成</li><li>典型的的客户端URL包括:</li><li style="list-style: none; display: inline"><ul><li>静态文件: <a href="http://www.abc.com/index.html" target="_blank">http://www.abc.com/index.html</a> 。显然web服务器需要有该文件的读权限</li><li>动态文件: <a href="http://www.abc.com/cgi-bin/user_list%E3%80%82%E8%BF%99%E6%98%AF%E4%B8%80%E4%B8%AAcgi%E7%A8%8B%E5%BA%8F%EF%BC%8C%u670D%E5%8A%A1%E5%99%A8%E4%BC%9A%E6%89%A7%E8%A1%8C%E5%AE%83%E4%BA%A7%E7%94%9F%E5%8A%A8%E6%80%81html" target="_blank">http://www.abc.com/cgi-bin/user_list</a>。 这是一个cgi程序user_list，服务器会执行它产生动态html。显然web服务器需要有对该文件的执行权限<br>
</li><li>带参数的动态文件: <a href="http://www.abc.com/cgi-bin/user_list?page=123&amp;limit=20" target="_blank">http://www.abc.com/cgi-bin/user_list?page=123&limit=20</a> 。这是以page=123, limit=20的参数来执行cgi程序user_list。因为浏览器URL只能用GET方法，所以参数使用?携带，如果是form的话，还能将参数放在post的http body中</li></ul></li><li>关于url的理解:</li><li style="list-style: none; display: inline"><ul><li>一个URL是动态还是静态，是web服务器怎么解释。常见用法是在cgi-bin目录下放一堆cgi程序，传入参数，动态生成内容</li><li>URL中主机后面接的URI，/表示资源根目录，但不是服务器OS的根目录</li><li>如果URL后面没有/，浏览器会自动补上，而很多服务器都会将/扩展成/index.html</li></ul></li><li>HTTP请求的组成:</li><li style="list-style: none; display: inline"><ul><li>request line。格式是"method uri http_version"，比如"GET / HTTP/1.0"，其实是请求/(可能就是/index.html)</li><li>request headers。每个header格式是"header: data"</li><li>空行</li><li>request body: POST方法会使用</li></ul></li><li>HTTP 响应:</li><li style="list-style: none; display: inline"><ul><li>response line: 格式"http_version status_code status_message"，如"HTTP/1.0 200 Succ"。常见的错误码包括, "200, 成功"、"301，永久移动"、"400，请求错误"、"404，未发现"、"501，未实现"、"505，http版本不支持"</li><li>response headers: 重要的头包括content-type, content-length</li><li>空行</li><li>response body: </li></ul></li><li>CGI接口是web服务器和动态内容生成程序间的约定:<br>
</li><li style="list-style: none; display: inline"><ul><li>关于程序参数: GET方法，URL中?后面的是参数，&分割每个参数；CGI程序通过QUERY_STRING环境变量访问；POST方法的参数放在request body中，CGI程序通过stdin访问</li><li>还有其他的常见环境变量: SERVER_PORT, REQUEST_METHOD, REMOTE_ADDR, REMOTE_HOST, CONTENT_TYPE, CONTENT_LENGTH</li><li>response的部分header和body都由CGI程序在stdout中输出</li></ul></li><li>最简单的web服务器上CGI程序调用流程: accept->fork->dup2(conn_sock, 1), dup2(conn_sock, 2)->setenv("QUERY_STRING"); setenv(...); ->execv -> wait</li></ul><div>27. 字符编码</div></div><div><ul><li>最初，数字到字符的映射各自为战，就出现了两个问题(1)有的字符集字符多有的少(2)同一个字符在不同的编码中有不同的映射。于是出现了美国的ASCII(American Standard Code for Information Interchange<br>
)，规定了128个字符，西欧国家各自在自己的语言中扩展到256个(但同一个字符可能在[128,256)中取不同值)，亚洲国家更是采用多字节编码。中文这样的多字节字符集叫MBCS(muti-byte character set)，其中的特例(包括GBK)是2字节编码叫DBCS(double-byte character set)。在windows上，程序员看见的概念叫MBCS和CP，而用户看到的概念叫ANSI，其实就是MBCS</li><li>IBM收录了各种编码，引入Code Page的概念，比如GBK就在936页，因此GBK==CP936。</li><li>由于不同的MBCS中，同一个字符的码值可能不同，出现了Unicode的概念。最初Unicode只收录了不到2^16个，这个字符集叫UCS-2(2字节的universal character set)，后来不够用了，扩展到UCS-4。但UCS只规定了字符集，没规定存储方式。</li><li>UTF(universal transformation format)是对UCS的存储方式的具体规定。UTF-16，用两个字节存储，当然，只能覆盖到UCS-2。UTF-32，用4字节存储，完整覆盖UCS-4。但这两种都太占空间，UTF-8，用字节存储，能表达所有的UCS-4。</li><li>UTF-8实现:</li><li style="list-style: none; display: inline"><ul><li>第1个字节的前缀位是, 1110，其中1的个数表示该字符总字节长度，剩余位是payload。这里的payload是UCS的最高位</li><li>第2个字节以后，前缀位总是10，其余6位是payload</li></ul></li><li>中文的MBCS的演进过程: gb2312->gbk->gb18030</li><li>python3的编码</li><li style="list-style: none; display: inline"><ul><li>string literal默认就是unicode。因此，习惯上内存尽量是unicode，只在边界上进行encode/decode</li></ul></li><li>python2的编码</li><li style="list-style: none; display: inline"><ul><li>源码中的string literal，编码是文件编码(coding:xxx)；unicode literal，等价于decode文件编码。</li><li>普通文件读写，直接是str/unicode对象进出</li><li>用codecs.open创建的文件对象，和open的encoding参数绑定。read的话，会自动被decode成unicode；write的话，如果是unicode，会被自动encode，如果是str，则不动</li><li>终端的读写，read返回的是sys.getdefaultencoding的str对象；write的话，unicode会被自动encode成default encoding的str对象并输出</li><li>文件系统的api都支持unicode和sys.getfilesystemencoding的str对象作为参数，返回的字符串，类型(str/unicode)和参数相同</li><li>web读写的出入口，建议用utf-8</li><li>web.py的内部字符串对象是unicode，因此注意和它的api交互时的串类型</li><li>建议:</li><li style="list-style: none; display: inline"><ul><li>当几乎不和中文打交道，不涉及编码问题时，可以用sys.getdefaultencoding(linux是utf-8，windows是mbcs(又叫ANSI，实际是gb2312))，但不推荐</li><li>其他时候统一用unicode(包括使用unicode literal)，让内存中总是unicode对象，只在io/库边界上，进行编码转换。边界上的编码转换，包括用codecs.open操作文件，用utf-8处理http request和response，用unicode和web.py交互</li><li>可以"from __future__ import unicode_literals"，然后"中国", b"中国"分别是unicode、str对象；之前u"中国", "中国"才是unicode、str对象</li></ul></li></ul></li></ul><div>27. http的connection头</div></div><div><ul><li>默认情况下，每次请求都需要重新建立TCP连接，而"Connection: Keep-Alive"开启连接复用模式，服务器会保持连接响应同一个客户端的下个请求。HTTP 1.0默认是关闭连接复用的，因此必须显示的指定"Connection: Keep-Alive"，而HTTP 1.1默认是开启复用的，除非显示的指定"Connection: Close"来让服务器处理完请求后断开连接(即无连接模式)</li><li>显然，连接复用模式，客户端(浏览器)必须通过其他方法判断reponse body已经接受完(无连接模式可以直接判断EOF)。对于固定内容的reponse，可以用Content-Length来判断；而动态内容，则通过"Transfer-Encoding：chunk"来指定，表示会边生成数据边发送给客户端，客户端收到长度为0的chunk表示完毕。</li></ul><div>27. 进程上下文切换vs线程上线文切换</div></div><div><ul><li>进程切换会多exception handler register和page table base register，其他GPR、浮点寄存器、状态寄存器、SIMD寄存器，切换情况一样</li><li>由于进程切换内存使用变化很大，TLB几乎完全失效；而线程切换，TLB中的堆页、全局变量页不一定失效。当然，由于TLB miss的摊还开销很小，所以几乎不计</li><li>进程切换由于内存使用情况变化导致的cache pollution更严重</li></ul><div>27. python project: FileSystemWebServer。提供help,listdir,hash,download等几个远程文件管理相关接口</div></div><div><br>
</div><div>28. c++ project: thread pool。典型的producer-consumer模型。注意，由于consumer结束wait的条件是两个，"有task可以执行"或者"超时，判断是否该退出线程"，所以用sem_timedwait</div><div><br>
</div><div>28. 深入理解计算机系统，第13章，第0节</div><div><ul><li>如果逻辑控制流在时间上重叠，就是并发(concurrent)的。如果有多个cpu同时执行，则是并行的(parallel)</li><li>concurrent在系统中的用处: 硬件中断、软件中断(signal)、进程</li><li>concurrent在应用中的用处:</li><li style="list-style: none; display: inline"><ul><li>多cpu上做计算</li><li>慢速IO设备时挂起</li><li>人机交互的并发需求</li><li>服务器需要服务多个客户端</li></ul></li><li>现代OS提供了至少三种并发方案:</li><li style="list-style: none; display: inline"><ul><li>进程</li><li>线程</li><li>IO多路复用</li></ul></li></ul><div>28. 深入理解计算机系统，第13章，第1节，基于进程的并发编程</div></div><div><ul><li>fork->exec->waitpid</li><li>注意:</li><li style="list-style: none; display: inline"><ul><li>需要处理SIGCHLD用waitpid回收zombie进程</li><li>子进程有父进程的descriptor table的拷贝，父句柄应该在子进程中关掉，对应的，子进程句柄也应该在父进程中关掉。这是使用fork后需要注意的地方。比如，父进程应该在fork后关闭connedsock</li></ul></li><li>多进程并发的优缺点:</li><li style="list-style: none; display: inline"><ul><li>独立的进程空间，没有内存破坏的担心，安全</li><li>创建进程需要拷贝页表等，加上进程调度压力更大，所以总开销更大</li><li>进程间通信需要IPC，编码不方便</li></ul></li></ul><div>28. 深入理解计算机系统，第13章，第2节，基于IO多路复用的并发编程</div></div><div><ul><li>即select、poll、epoll等模型</li><li>注意select允许的最大fd值FD_SETSIZE，在linux下是数组长度，默认是1024，修改需要重新编译内核；windows下有一些hack，允许在include winsock.h之前，重新define一个新值即可，select的内核实现使用的是一个运行时变量</li><li>使用select时，如果三个fd_set都为NULL，只有timeval非空，则相当于sleep</li><li>用select监听read的fd_set，返回的依据是，"此时read(fd)不会阻塞"，因为EOF也不会阻塞read，所以EOF也能使select返回</li><li>IO多路复用的优缺点:</li><li style="list-style: none; display: inline"><ul><li>不像多进程并发，采用的是内存共享，故安全性更低，一个客户处理出问题，可能破坏掉整个服务器</li><li>没有多进程的内核调度开销</li><li>任务间通信更容易，直接共享内存</li><li>调试更方便，是单线程模型</li><li>编码复杂，而且并发的粒度越小(即每次调度执行的指令数更少)编码越复杂</li><li>三种并发模型中最高的效率，能支持最多的并发数，平均每并发任务消耗的资源最少。注意select在linux下只能处理最大1024的fd(哪怕你只是打开了2000个文件，此时一用select，就因为fd太大而出问题)</li></ul></li></ul><div>28. 深入理解计算机系统，第13章，第3节，基于线程的并发编程</div></div><div><ul><li>同一个进程空间，多个调度单元，因此是多进程和IO多路复用的结合</li><li>pthread_create, pthread_self, pthread_exit, pthread_cancel, pthread_join, pthread_detach, pthread_once</li><li>本节是每任务一新线程的简单模型</li></ul><div>28. 深入理解计算机系统，第13章，第4节，多线程程序中的共享变量</div></div><div><ul><li>全局变量和静态变量都存储在数据段中，自动变量在栈上，故前者需要同步，后者线程安全</li></ul><div>28. 深入理解计算机系统，第13章，第5节，用信号量同步线程</div></div><div><ul><li>progress graph的概念</li><li>dijkstra提出了同步不同执行线程的方法，即基于信号量(semaphore)的PV操作，其中P是-1并可能挂起，V是+1。PV分别来自荷兰单词的Probern(测试)和Verhogen(增加)</li><li>semaphore绝不可能进入负值，这是semaphore invariant</li><li>具有0,1取值的二值信号量(binary semaphore)被用作保护临界区(critical section)，一般叫做mutex</li><li>sem_init, sem_destroy, sem_wait, sem_trywait, sem_timedwait, sem_post</li><li>不考虑sleep的存在的话(本来效果也不同)，信号量不止可以用作mutex，也可以用于线程调度。使用slots、items两个信号量的producer-consumer模型，就是双端调度，两个角色都可以挂起；如果只想挂起一方，比如像webserver、pthreadpool那样，producer不挂起，那么，只用items一个信号量即可。用法可以灵活处理</li></ul><div>28. 深入理解计算机系统，第13章，第6节，基于预线程化的并发服务器</div></div><div><ul><li>这里的prethreading就是threadpool的概念</li><li>threadpool是经典的producer-consumer模型，其中task即是产品</li></ul><div>28. 深入理解计算机系统，第13章，第7节，各种并发性问题</div></div><div><ul><li>线程安全(thread-safe)，对应的有thread-unsafe概念。常见的thread-unsafe有四种:</li><li style="list-style: none; display: inline"><ul><li>访问共享变量。thread-safe化: 用mutex保护起来</li><li>保持跨越多个调用的全局状态。典型的，rand、strtok。thread-safe化: 只能重写，编写reentrant版本</li><li>返回静态地址。典型的，asctime, ctime, localtime, gethostbyaddr, gethostbyname, inet_ntoa。 thread-safe化: lock-and-copy，即"p = (struct_type*)malloc(); lock(); *p = *call(); unlock(); return p;"。有内存泄露，且低效，但函数签名不变，无需改调用代码</li><li>调用thread-unsafe函数。必须将被调函数thread-safe化(1、3情况，lock+xxx即可；情况2，必须重写)，否则本函数也是thread-unsafe的</li></ul></li><li>上面2、3两种情况的ANSI C函数在unix下都有可重入版本，加上后缀_r，比如rand_r、strtok_r，但因为各unix实现文档很差，可能移植性不好</li><li>可重入性。可重入函数(reentrant function)是thread-safe的真子集，其特点是，它不会引用任何共享数据，因此天然thread-safe。</li><li style="list-style: none; display: inline"><ul><li>显式可重入(explicit reentrant): 参数是传值(没有指针传递)，只访问局部变量和参数。显示可重入函数无论被怎样调用，都是安全的。也叫纯函数</li><li>隐式可重入(implicit reentrant): 参数可以是指针。相比显示可重入函数，隐士可重入函数的可重入性还跟参数指针指向的位置有关，它可能不是thread-safe的</li></ul></li><li>死锁(deadlock)。死锁往往是程序员对PV使用不当。死锁是相当困难的问题，依赖具体的时序，因此不可预测、难以重现。</li><li>要避免一般死锁很困难，但只就避免使用mutex时的死锁来说，一个简单规则，对于"P(s);P(t);V(t);V(s)"这样PV嵌套的序列，每个线程都确保以相同的顺序进行P即可(比如P(s);P(t))，因为这样就不会再出现两个线程互相占有一种资源却申请另一种资源的情况。</li></ul></div></div>