Computer Systems

第1章

计算机系统	位	字节	字符	ASCII	文本文件	二进制文件	编译系统	gcc -o hello hello.c	可执行文件	指令集结构

存储器层次结构	文件	虚拟存储器	进程	线程	多线程	进程虚拟地址空间层次	并发	线程级并发	超线程	指令级并发

超标量	SLMD并行	单执行多数据	虚拟机

第2章

二进制	十六进制	十进制	转换	字长	字节顺序	大端法	小端法	sizeof(T)	二进制不兼容	布尔运算	逻辑运算	命题逻辑

逻辑运算	命题逻辑	位运算	掩码运算	逻辑运算短路	移位运算	左移	无符号逻辑右移	有符号算术右移	Umaxw	TMinw

TMaxw	2^w -1	-2^(w-1)	2^(w-1) -1	T2Uw(x)

移位代替乘以常数	无符号逻辑右移	有符号算术右移	代替除以2的幂	模运算	浮点数近似计算	二进制小数点	三个字段 三种情况

4舍入	浮点运算无结合率和分配律	int float double 转换	溢出	舍入情况

第3章

抽象	ISA	虚拟存储地址	unix> gcc -01 -o p p1.c p2.c	unix> gcc -01 -s code.c	unix>gcc -01 -c code.c	gcc -01 -o prog code.o main.c

unix> objdump -d prog	gdb 用法	x/17xb sum 检查16进制字节	字	双字	四字	%eax %acx &edx %ebx %esi %edi %esp栈 %ebp

$立即数	Ea寄存器	存储器引用	寻址	Imm	(Ea)间接寻址	Imm(Eb)基址+偏移量	(Eb,Ei)变址寻址	Imm(Eb,Ei)变址寻址

Imm(,Ei,S) (Eb, Ei, S) Imm(Eb,Ei,S) 比例变址寻址	movb movw movl movsbw movsbl movwl movzbw movzbl movzwl	S,D	push S

R[%esp] <– R[%esp]-4 M[R[%esp]] <– S	leal S,D	INC DEC NEG NOT D	ADD SUB IMUL XOR OR AND S,D	SAL SHL SAR SHR k, D

有无符号64位乘除	imull S	mull S	R[%eax]:R[%edx] <– S xR[%eax]	cltd转四字

idivl S	R[%edx] <– R[%edx]:R[%eax] mod S	R{%eax] <– R[%edx]:R[eax] / S	divl / S

CF ZF SF OF	(XOR CF OF 0)	(SAL « CF 移除位 OF 0）	INC DEC OF ZF	CMP S2, S1 相等 ZF=1	TEST S2, S1

set+条件后缀指令	D	将D设位0或1	-e、ne、s、ns、g、ge、setl、le、a、ae、b、be	mozbl %al %edx	最高24位清零为了32位

.L1直接跳转	*间接跳转	jmp、je、jne、je、jns、jg、jge、jl、jle、ja、jae、jb、jbe	循环实现	条件控制转移	分支预测

条件数据传送	条件数据传送的局限	破坏短路	浪费	跳转表实现多重分支	过程调用	参数或返回值形式将数据和控制转移，

需分配、释放空间

栈帧结构	%esp减小 分配空间	%esp增加释放空间	栈局部变量	参数偏移量对%ebp 4 + 4i	call过程调用	返回地址入栈

ret弹出地质并跳转到地址	leave为返回准备栈	调用者保存寄存器%eax %edx %ecx	被调用者保存寄存器%ebx %esi %edi

必须保存%ebp和%esp	程序计数器%eip	①push %ebp movl %esp %ebp sub $24, %esp	②pushl %ebp movl %esp %ebp pushl %ebx

③popl %ebx popl %ebp ret	④ leave ret	%ebp 变动了，返回地址压入后%ebp 压入	指针的值 Xp + L * i	T D[R][C] D[i][j] Xd + L(c*i+j)

寄存器溢出	struct指向内部指针既结构地址	加上字段的偏移量	联合union向内部的指针即联合的指针	最大字段大小即联合大小

用于减小分配空间量	数据对齐2、4、8	结构内每个元素都得对其	指针是抽象，值，&，*，数组，指针类型转换指不变

函数指针形式	unix> gdb prog P175	缓冲区溢出破坏	栈随机化	栈破坏检测金丝雀	限制可执行代码区域	字长限制了虚拟地址空间

unix>gcc -01 -s -m32/-m64 code.c	x86-64位没有生成栈帧，参数通过寄存器%rdi %rsi 传递，不是栈，不从存储器引用	%rax %eax %ax

%ah %al	返回值	%rbx %ebx %bx 被调用者保存	%rcx %rdx %rsu %rdi 参数	%rbp被调用者保存	PC程序计数器%rip	movabsq I，R

mov S,D	movsbq	movswq	movzbq	movzwq	pushq S	popq D	cltq	orq S1，S2设置S1或S2为返回值	imulq S	mulq S

R[%rdx]:R[%rax] <– S x R[%rax]	cqto	R[%rdx]:R[%rax] <– Sign Extend(R[%rax])	idivq S	R[%rdx] <– R[%rax]:R[%rax] mod S;

R[%rax] <– R[%rdx]:R[rax] / S	divq S	R[%rdx] <– R[%rdx]:R[%rax] mod S	R[%rdx] <– R[%rdx]:R[%rax] / S	X86-64汇编 rep 再接ret

不能全部变量放寄存器的函数才在栈上空间（太多、是数组或结构、&计算地址、参数传递到另一函数

第4章

ISA	HCL	程序员可见状态	虚拟地址	指令集	源、目的地址、操作、类型	指令的构成	指令编码	4位指令码，4位功能码

合起来为指令指示符	可能有单个字节寄存器指示符	可能有四字节常数	halt	nop	rrmovl	irmovl	rmmovl	mrmovl

opl	jxx	cmovxx	call将返回地址入栈并跳转到目的地址	ret	pushl	popl	只需要一个寄存器操作数的指令将另一

寄存器设为0xF	CISC有条件码、指令长度可变、栈密集的过程连接	RISC采用load/store体系结构和规则编码	AOK HLT ADR INS

状态码	异常处理程序	.汇编器命令指明生成代码的位置	pushl指令的歧义：①压入%esp的原始值②压入减去4的%esp的值

popl有同样的歧义	HCL HDL Verilog VHDL	多路复用器	组合逻辑没有短路操作规则	时钟寄存器	PC 条件寄存器	寄存器文件

指令存储	数据存储	随机访问寄存器	①取值：程序计算器PC的值位地址icode、ifun、rA、rB、valC 下条指令地址valP

valP = PC值 + 已取指令的长度	②译码：读入rA，rB得valA、valB	③执行：ALU 有效地址 ValE 栈指针 条件码	④访存 valM（读或写）

⑤写回（再次保存到寄存器）	⑥更新PC	降低硬件复杂度	INOP将PC加1	FNONE默认函数代码	RESP %esp寄存器ID

RNONE没有寄存器文件访问	吞吐量	延迟	流水线寄存器	信号->流水线寄存器->时钟上升才改变状态	吞吐量受最慢阶段限制

时序优化	流水线过深收益反而下降	控制相关反馈路径	流水线P 保存上一周期控制信号	预测选择或没选择分支PC为valC或valP

合并信号减少寄存器状态线路数量	数据相关	控制相关	冒险	一条指令操作数被前面三条指令任意一条改变时出现数据冒险

①暂停：将指令阻塞在译码阶段，执行阶段插入bubble，如nop	②数据转发：译码阶段发现有其他指令未进行的写，如上一条指令

的w_ValE直接用在下一条指令的valB上	加载/使用 冒险使用暂停 + 转发 即加载互锁 + 转发	异常指令后的指令禁止更新条件吗

PIPE各阶段实现P291	PIPE的硬件结构	控制逻辑	处理ret F暂停 Ｄ气泡	加载／使用 冒险 FD暂停 E气泡	预测错误DE气泡

特殊单元处理	乘除、浮点	用暂停处理短时间高速缓存不命中和用异常处理长时间的缺页

第5章

①选择合适的算法和数据结构	②理解优化编译器的能力和局限性，编写编译器能有效优化的代码，（消除不必要的函数调用、

条件测试和存储器引用，优化不依赖于目标极其的任何局限性。）性能最大化才是目标机器模型	理解处理器工作方式，调整程序

最大速度。	③利用指令级并行，降低数据相关，提高并行度。	研究汇编码，研究内循环代码，确认低性能原因，预测会不会并行

处理器资源、确认关键路径	妨碍优化的因素：①指针的存储器别名使用 ②函数调用若修改全局状态的函数

CPE	消除循环的低效率	循环条件调用移出	减少过程调用	消除不必要的存储器引用	表示性能改进的方式 T(old) / T(new)

之后进一步提高性能得考虑利用处理器微体系结构的优化，因机器而异	指令级并行	延迟界限、吞吐界限制–> 最大性能

超标量	乱序	指令控制单元ICU指令执行单元EU	现代处理器的框图	延迟	发射	完全流水线化	发射时间的倒数为最大吞

吐量	数据流	关键路径	CPE=延迟界限L	除法和浮点运算极缓慢	关键路径只提供下限，有可能更慢	循环展开

向量长度不一定位2的倍数则可选地增加一次迭代	循环展开不会改进浮点情况性能	提高并行性	K次循环展开，并且使用k路并行

即创建多个积累变量和重新结合	重新结合变换，并且k次循环展开	浮点数不能变换	其他因素：寄存器移除到栈。

写适合用条件传送的代码：功能式 ？ ：	分支预测只有加载操作受存储操作结果影响	对于寄存器，指令译码成操作即可确定相关

对于存储器操作，只有存储地质计算出才确定是否相关	所以尽可能将其保存在局部变量里	剖析程序GRPROF

unix>gcc -o -pg prog.c -o prog	unix>./prog file.txt	unix> gprof prog	剖析程序注意 最耗时部分	较短时间的剖析不准确

基本块是内部没有控制转移的指令序列，整个被执行	Amdahl定律	要大幅度提高整个系统速度，必须提高整个系统很大一部分速度

第6章

理解系统如何将数据在存储层次结构中移动，编写出具有局部性的程序，每次访问相同或邻近的数据。	RAM	SRAM高速缓存

DRAM主存、图形帧、缓冲区	SRAM对光、声、干扰不敏感	DRAMd 超单元	存储器控制器CAS RAS	引脚	存储器模块	DDR3

SDRAM	DRAM、SRAM易失	ROM非易失只读存储器、放置固件	闪存 SSD	磁盘	表面	主轴	旋转速率	磁道	扇区

间隙	柱面	读写头	传动臂	寻道、旋转、传送总时间	寻道时间x2 估计磁盘访问时间	逻辑块	磁盘控制器	总线结构

I/O端口	①CPU发起磁盘读，②DMA传送，③中断信号	逻辑块提供接口与抽象	SSD闪存芯片闪存翻译层	DRAM和磁盘性能滞后

重复引用同一变量有良好的时间局部性，步长为k的引用模式，k越小，空间局部性越好。	循环体越小，迭代次数越多，性能越好

存储器层次结构	块	相邻层次之间块大小固定的	低层补偿长时间访问用大的块	缓存命中	缓存不命中	替换驱逐

冷缓存 即空的缓存区，强制不命中	放置策略	i mod 4	冲突不命中 （两个低层的一直替换高层同一位置的块）	容量不命中

时间局部性期望后面对目标一系列访问命中	空间局部性期望后面对该块中其他对象命中	高速缓存行 1有效位 t标记位 B=2^b字节块

地址：t位标记 s位组索引 b位块偏移	①组选择 ②行中标记匹配有效位 ③字抽取 m=log2(M)物理地址	抖动即告诉缓存反复地加载和

驱逐相同的高速缓存的组，修正抖动，在每个数组结尾放B字节填充组相联告诉缓存(key,value) key标记为有效位value块内容

,必须搜索组中的每一行	替换策略：随机选择行、最不常用、最近少使用	全相联告诉缓存无组索引，只适合做小的告诉缓存

写命中	直写	写回（推迟）	写不命中 非写分配	写分配	尽量使用写回写分配	i-cache d-cache	i7 高速缓存层次

高速缓存性能衡量	不命中率、命中率、命中时间、不命中时间	高速缓存 块大小 折中

编写代码：①注意力集中在核心函数循环上 ②让循环内部缓存不命中数最小，局部变量都在寄存器中，除额外放不下的。

对局部变量的反复引用是好的，步长为1的引用模式是好的。读吞吐量、读宽带、存储器山	重新排列循环以提高空间局部性

第7章

链接	分离式链接	连接器任务 符号解析和重定位	编译驱动程序	静态链接	可重定位目标文件	可执行目标文件	共享目标文件

目标模块	ELF的组成	全局符号	外部全局符号	本地符号	本地符号本地变量不同	C static隐藏变量	static本地变量	共享库

符号表条目格式	符号解析（引用<->定义）	强符号至多一个	弱符号	静态库 拷出 目标模块	创建库 unix>ar rcs libvertor.a addvec.o

创建加载时不需要再次链接的可执行文件unix>gcc -static -o P2 mian2.o ./libvector.a	如何使用静态库解析引用

库放命令行尾，独立无序，非独立则定义在引用之后，可重复	重定义节和符号定义	重定位节中的符号引用	重定位条目

重定位PC相对引用 R_386_PC32	重定位绝对引用 R_386_32	使得每个全局变量运行地址确定	ELF可执行目标文件组成	加载

linux运行时存储器映像	共享库	动态链接	DLL	unix>gcc -shared -fPIC -o libvector.so addvec.c multvec.c

unix>gcc -o P2 main2.c ./libvector.so	如何重定位	运行时链接#include <dlfcn.h> void *dlopen(cosnt char *filename, int flag);

flag 为 TRLD_NOW	void *dlsym(void *handle, char *symbol);	int dlclose (void *handle);	const char *dlerror(void);	errmsg	-rdynamic

PIC	GOT	PLT	延迟绑定

第8章 异常控制流

控制转移	控制流	硬件层：异常事件处理程序	OS层：进程上下文切换	应用层：信号|信号处理程序	ECF	什么事异常

异常跳转表	异常处理程序	Icurr	Inext	中断	异常号	异常表基址寄存器	异常的类别、原因、同异步、返回行为

陷阱用途：系统调用	为何	用户模式	用户栈	内核模式	内核栈	异常号	描述	类别	系统调用示例	系统调用陷进指令

系统调用参数寄存器传递	栈%esp会被内核覆盖不能使用	进程上下文包括	独立的逻辑控制流	独立的地址空间	并发流	并发

时间分片	并行流	私有空间不被其他进程读写	模式位	内核模式	用户模式	用户程序通过系统调用接口访问内核代码和数据

用户模式切换内核模式唯一方式是通过中断故障陷阱系统调用异常	上下文切换 –> 多任务	调度	调度器	错误报告函数

错误处理包装函数

错误报告函数

void unix_error(char *msg)

{

fprintf(stderr, “%: %s\n”, msg, strerror(errno));

exit(0);

}

fork的错误包裹函数

pid_t Fork(void)

{

pid_t pid;

if ((pid = fork()) < 0)

unix_error(“Fork error”);

return pid;

}

#include <sys/types.h>

#include <unistd.h>

pid_t getpid(void);

pid_t getppid(void);

#include <stdlib.h>

void exit(int status);

#include <sys/types.h>

#include <unistd.h>

pid_t fork(void); // 调用一次返回两次，子进程返回0，父进程返回子进程的PID，出错为-1

// 父子进程：并发执行；相同的但是独立的地址空间，改变都是独立的；共享文件。

画进程图

#include <sys/types.h>

#inlcude <sys/wait.h>

pid_t waitpid(pid_t, int *status, int options); // pid>0 则等待单独的子进程。pid=1,则等待所有子进程

//options 设置为常量WNOHANG，若子进程都没终止，立即返回。默认是父进程挂起等待。

//options 设置为常量WUNTRACED 被停止的子进程也包含在内

// WIFEXITED(status)，WEXITSTATUS(status),WIFSIGNALED(status), WTERMSIG(status)，WIFSTOPPED(status), WSTOPSIG(status)

#include <sys/types.h>

#include <sys/wait.h>

pid_t wait(int *status); == pid_t waitpid(-1, &status, 0);

errno ECHILD

#include <unistd.h>

unsigned int sleep (unsigned int secs); // return time need to sleep yet

#include <unistd.h>

int pause(void); // always return -1

#include <unistd.h>

int execve(const char *filename, const char *argv[], const char *envp[]); // 成功则不返回，错误则返回-1

// 新程序的栈帧结构

#include <stdlib.h>

char *getenv (const char *name); // 返回指向value的指针，否则为NULL

#include <stdlib.h>

int setenv(const char *name, const char *newvalue, int overwrite); //override非0时才替换， 成功返回0， 错误返回-1。

void unsetenv(const char *name);

fork 在新的子进程中运行相同的程序，execve在当前进程上下文中加载并运行一个新程序，会覆盖当前进程的地质空间，但并没有创建新进程，新程序仍然有相同的PID，并继承了execve函数是已打开的所有文件描述符。

进程组

#include <unistd.h>

pit_t getpgrp(void);

#include <unistd.h>

int setpgid(pit_t pid, pit_t pgid); //成功则返回0，错误返回-1 若pid或gpid参数为0， 则将进程的PID设置为进程组PID

一个类型最多只会有一个待处理信号， 丢弃。 阻塞后，不接收信号。

unix> /bin/kill -9 15213 发送信号9(SIGKILL)给15213进程。

unix> /bin/kill -9 -15213 发送信号9(SIGKILL)给15213进程组的每个进程。

unix> ls | sort //键盘发送信号，两个进程组成的前台作业，是通过Unix管道连接起来的。每个作业创建独立的进程组。

#include <sys/types.h>

#include <signal.h>

int kill(pid_t pid, int sig); // 用kill发送信号，包括自身。若pid>0，则发送给pid进程，否则发送给abs(pid)进程组每个进程

#include <unistd.h>

unsigned int alarm(unsigned int secs); //安排内核在secs秒内给自身发送SIGALRM信号

#include <signal.h>

typedef void (*sighandler_t)(int);

sighandler_t signal(int signum, sighandler_t handler); // 成功位前次处理程序的指针，出错则为SIG_ERR，不设errno

//handler为SIG_IGN，则忽略signum的信号，为SIG_DFL，则恢复默认行为，否则，handler就是重定义的信号处理程序

不可以用信号类对其他进程中发生的事件计数。待处理信号被阻塞，待处理信号不会排队等待，系统调用可以被中断。

①修改SIGCHLD的处理程序，使得每次SIGCHLD处理程序被调用时，回收尽可能多的子进程。②编写可移植的信号处理代码。必须考虑系统调用过早返回的可能性，然后当它发生时手动重启它们。

#include <signal.h>

int sigaction(int signum, struct sigaction *act, struct sigaction *oldact); // 指明信号处理语义，被中断是重启还是永久放弃。

sigaction的包装函数

handler_t *Signal(int signum, handler_t *handler)

{

struct sigaction action, old_action;

action.sa_handler = handler;

sigemptyset(&action.sa_mask);

action.sa_flags = SA_RESTART;

if (sigaction(signum, &action, &old_action) < 0)

unix_error(“Signal, error”);

return (old_action.sa_handler);

}

显式地阻塞和取消阻塞信号，同步流以避免并发中的竞争错误

#include <signal.h>

int sigprocmask(int how, const sigset_t *set, sigset_t *oldset); //改变当前阻塞的集合blocked

// how为SIG_BLOCK时添加set中信号到blocked，SIG_UNBLOCK从blocked中删除set中信号，SIG_SETMASK则blocked=set

int sigemptyset(sigset_t *set);

int sigfillset(sigset_t *set);

int sigaddset(sigset_t *set, int signum);

int sigdelset(sigset_t *set, int signum);

int sigismember(const sigset_t *set, int signum); // 若是成员则返回1，否则返回0，出错返回-1

第9章

VM	作用③	物理寻址	虚拟寻址	虚拟地址	MMU	虚拟地址空间2^n	物理地址空间	VM放在磁盘上	虚拟页 映射 物理地址

未分配	缓存	未缓存	页表:DRAM:作用	页表条目	PTE组成	缺页	页面调度 简化链接和加载、代码和数据共享、存储器分配

PTE许可位	翻译后备缓冲器TLB	多级页表	VPO VPN TLBI TLBT PPO PPN CO CI CT	地址翻译步骤	进程的虚拟存储器	内核虚拟存储器

内核数据结构	内核数据结构组织VM	存储器映射 —> 共享对象 —> 私有对象 —> 写时拷贝	nmap	munmap	动态分配器

显式new delete	隐式垃圾收集器	吞吐率与存储器使用率权衡	内部碎片 外部碎片	隐式空闲链表	系统对齐 8字节 双子对齐

放置策略	头部 脚步	合并	分离存储	大小类	空闲链表数组	每个链表包含大小不同块	分割	剩余插入另一链表

不能返回局部变量的引用或指针	static -> 私有的	–和*优先级相同

#include <unistd.h>

#include <sys/nman.h>

void *mmap(void *start, size_t length, int port, int flags, int fd, off_t offset); //创建新的虚拟存储器区域，并将对象映射到这些区域。

// start为NULL，port的参数，PROT_EXEC可以被CPU指令执行, PROT_READ, PROT_WRITE, PROT_NONE不能被反问

#include <unistd.h>

#include <sys/mman.h>

int munmap(void *start, size_t length); //删除虚拟存储器的区域

动态存储分配器：显示分配器（malloc, free, new, delete），隐式分配器（垃圾收集器，Lisp，ML，Java）

#include <stdlib.h>

void *malloc(size_t size); //成功则返回指向存储块的指针，否则返回NULL，并设置errno

#include <unistd.h>

void *sbrk(intptr_t incr); // 成功则返回旧的brk指针，出错则为-1，并设置errno为ENOMEN

#include <stdlib.h>

void free(void *ptr);

第10章 系统级I/O

所有IO设备都被模型化为文件，所有的输入和输出都被当作是对相应文件的读和写。

Unix Shell创建的每个进程开始时都有三个打开的文件，描述符分别为<unistd.h>：STDIN_FILENO，STDOUT_FILENO和STDERR_FILENO

seek改变当前的文件位置k

读文件 将k到k+n字节拷贝到存储器，n超过文件字节大小m会触发EOF。写文件，从存储器拷贝n字节到文件，从k开始，然后更新k。

关闭文件时会释放文件打开时创建的数据结构，并释放他们的存储器资源。

#include <sys/types.h>

#include <sys/stat.h>

#include <fcntl.h>

int open(char *filename, int flags, mode_t mode); //flags为O_RDONLY, O_WRONLY, O_RDWR,可加上O_CREAT, O_TRUNC, O_AAEND的或

//mode为S_IRUSR, S_IWUSR, s_IXUSR, S_IRGRP… , S_IROTH // 访问权限为mode & ~umask //返回描述符或-1

#include <unistd.h>

int clonse(int fd); // 返回0或-1

#include <unistd.h>

ssize_t read(int fd, void *buf, size_t n); // 返回读的字节数，EOF返回0，出错-1，buf作为中间变量

ssize_t write(int fd, const void *buf, size_t n); // 返回写的字节数或-1

不足值：read和write传送的字节比应用程序要求的要少。

RIO无缓冲的输入输出函数（直接在存储器和文件之间传送，没有应用级缓冲，二进制数据读写到网络和从网络读写二进制尤其有用）

ssize_t rio_readn(int fd, void *usrbuf, size_t n)

{

size_t nleft = n;

ssize_t nread;

char *bufp = usrbuf;

while (nleft > 0) {

if ((nread = read(fd, bufp, nleft)) < 0) {

if (errno == EINTR) /* Interrupted by sig handler return */

nread = 0; /* and call read() again */

else

return -1; /* errno set by read() */

}

else if (nread == 0)

break; /* EOF */

nleft -= nread;

bufp += nread;

}

return (n - nleft); /* return >= 0 */

}

ssize_t rio_writen(int fd, void *usrbuf, size_t n)

{

size_t nleft = n;

ssize_t nwritten;

char *bufp = usrbuf;

while (nleft > 0) {

if ((nwritten = write(fd, bufp, nleft)) <= 0) {

if (errno == EINTR) /* Interrupted by sig handler return */

nwritten = 0; /* and call write() again */

else

return -1; /* errno set by write() */

}

nleft -= nwritten;

bufp += nwritten;

}

return n;

}

RIO的带缓冲的输入函数，从文本中读取文本杭和二进制数据，文件的内容缓冲在应用级缓冲区内，是线程安全的，可交错调用。

#define RIO_BUFSIZE 8192

typedef struct {

int rio_fd; /* Descriptor for this internal buf */

int rio_cnt; /* Unread bytes in internal buf */

char rio_bufptr; / Next unread byte in internal buf */

char rio_buf[RIO_BUFSIZE]; /* Internal buffer */

} rio_t;

void rio_readinitb(rio_t *rp, int fd) //Associate a descriptor with a read buffer and reset buffer

{

rp->rio_fd = fd;

rp->rio_cnt = 0;

rp->rio_bufptr = rp->rio_buf;

}

static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)

{

int cnt;

while (rp->rio_cnt <= 0) { /* Refill if buf is empty */

rp->rio_cnt = read(rp->rio_fd, rp->rio_buf,

sizeof(rp->rio_buf));

if (rp->rio_cnt < 0) {

if (errno != EINTR) /* Interrupted by sig handler return */

return -1;

}

else if (rp->rio_cnt == 0) /* EOF */

return 0;

else

rp->rio_bufptr = rp->rio_buf; /* Reset buffer ptr */

}

/* Copy min(n, rp->rio_cnt) bytes from internal buf to user buf */

cnt = n;

if (rp->rio_cnt < n)

cnt = rp->rio_cnt;

memcpy(usrbuf, rp->rio_bufptr, cnt);

rp->rio_bufptr += cnt;

rp->rio_cnt -= cnt;

return cnt;

}

ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n)

{

size_t nleft = n;

ssize_t nread;

char *bufp = usrbuf;

while (nleft > 0) {

if ((nread = rio_read(rp, bufp, nleft)) < 0)

​ return -1; /* errno set by read() */

else if (nread == 0)

break; /* EOF */

nleft -= nread;

bufp += nread;

}

return (n - nleft); /* return >= 0 */

}

ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen)

{

int n, rc;

char c, *bufp = usrbuf;

for (n = 1; n < maxlen; n++) {

​ if ((rc = rio_read(rp, &c, 1)) == 1) {

*bufp++ = c;

if (c == ‘\n’) {

​ n++;

​ break;

​ }

} else if (rc == 0) {

if (n == 1) {

return 0; /* EOF, no data read */

​ }

else {

break; /* EOF, some data was read */

​ }

} else

return -1; /* Error */

}

*bufp = ‘\0’;

return n-1;

}

读取文件元数据

#include <unistd.h>

#include <sys/stat.h>

int stat(const char *filename, struct stat *buf); // 接收第一个参数用其设置第二个参数的各个成员信息，如st_mode, st_size

int fstat(int fd, struct stat *buf); // 接收第一个参数用其设置第二个参数的各个成员信息，如st_mode, st_size

S_ISREG(stat.st_mode)，S_ISDIR(stat.st_mode)，S_ISSOCK(stat.st_mode)

共享文件

描述符表：每个进程打开的描述符，文件表是打开文件的集合（文件位置，引用计数），v-node表含stat结构信息（st_mode, st_size)

I/O重定向 unix> ls > foo.txt

当一个Web服务器代表客户端运行CGI程序时，它就执行一种相似类型的重定向。

#include <unistd.h>

int dup2(int oldfd，int newfd); //重定向的实现

标准I/O库

fopen、fclose、fread、fwrite、fgets、fputs

#include <stdio.h>

extern FILE *stdin; //三个打开的流，流就是指向FILE类型的结构的指针

extern FILE *stdout;

extern FILE *stderr;

标准I/O函数是磁盘和终端设备I/O的选择。在网络套接字上不要使用标准I/O函数来进行输入和输出，要用RIO函数。

需要格式化的输出，使用sprintf函数在存储器中格式化一个字符串，然后用rio_writen发送到套接口。

需要格式化输入，使用rio_readlineb来读一个完整的文本行，然后用sscanf从文本行提取不同字段。

第11章

网络应用：一个服务器进程和多个客户端进程组成	对于主机，网络只是I/O设备	LAN局域网 以太网	帧：头部、有效负荷	网桥

桥接以太网	路由器	WAN广域网	协议消除不同网络的差异	LAN1帧有效负荷是互联网包头，互联网包头有效符合是用户数据

客户端和服务器混合使用套接字接口函数和Unix I/O函数进行通信	套接字函数作为陷入内核的系统调用实现
IP协议提供基本的命名方和和递送机制，数据报	TCP进程间可靠的双向的连接	DNS域名系统

struct in_addr // Internet address structure

{

unsigned int s_addr; // Network byte order (big-endian)

}

#include <netinet/in.h>

unsigned long int htonl (unsigned long int hostlong); // host byte order to network byte order 32位

unsigned short int htons(unsigned short int hostshort); // 16位

unsigned long int ntohl(unsigned long int netlong); // network byte order to host byte order 32位

unsigned short int ntohs(unsigned short int netshort); //16位

#include <arpa/inet.h> //IP地址和点分十进制字符串之间的转换

int inet_aton(const char *cp, struct in_addr *inp); // 成功返回1，出错返回0

char *inet_ntoa(struct in_addr in); // 返回指向点分十进制字符串的指针

struct hostent // DNS host entry structure

{

char *h_name;

char **h_aliases;

int h_addrtype; // host address type (AF_INET)

int h_length; // length of an address in bytes

char **h_addr_list;

}

#include <netdb.h>

struct hostent *gethostbyname(const char *name); //返回指向主机条目指针,出错位NULL指针，同时设置h_errno

struct hostent *gethostbyaddr(const char *addr, int len, 0); //同上， len为IP地址长度，总为四个字节

本地域名 localhost，本地回送地址：127.0.0.1，hostname命令可确定本地主机的实际域名

套接字是连接的一个端点，每个套接字有套接字地址，由因特网地址和16位端口组成。客户端是临时端口，服务器是知名端口。

一个连接有两端的套接字地址唯一确定的，套接字对。(cliaddr:cliport, servaddr:servport)

套接字接口

从Unix内核的角度来看，一个套接字就是通信的一个端点，从Unix程序的角度来看，套接字就是一个有相应描述符的打开文件。

typedef struct sockaddr SA;

connect、bind、accept要求一个指向协议相关的套接字地址结构的指针，使之能接受各种类型的套接字地址结构。

#include <sys/types.h>

#include <sys/scoket.h>

int socket(int domain, int types, int protocol);

clientfd = Socket(AF_INET, SOCK_STREAM, 0); // AF_INET表明使用因特网，SOCK_STREAM表明这个套接字是因特网连接的一个端点。

// socket返回的clientfd是不能用于读写的，如何打开需要取决于是客户端还是服务器。

#include <sys/socket.h>

int connect(int sockfd, struct sockaddr *serv_addr, int addrlen) // addrlen = sizeof(sockaddr_in), 此时sockfd就可以读写了

int open_clientfd(char *hostname, int port)

{

int client;

struct hostent *hp;

struct sockaddr_in serveraddr;

if ((clientfd = socket(AF_INET, SOCK_STREAM, 0)) < 0)

return -1;

if ((hp = gethostbyname(hostname)) == NULL)

return -2;

bzero((char *) &serveraddr, sizeof(serveraddr));

serveraddr.sin_family = AF_INET;

bcopy((char *)hp->h_addr_list[0],

(char *)&serveraddr.sin_addr.s_addr, hp->h_length);

serveraddr.sin_port = htons(port);

if (connect(clientfd, (SA *) &serveraddr, sizeof(serveraddr)) < 0)

return -1;

return client;

}

#include <sys/socket.h>

int bind(int sockfd, struct sockaddr *my_addr, int addrlen);

#include <sys/socket.h>

int listen(int sockfd, int backlog); //socke函数创建的描述符默认是主动套接字，linsten函数将其转化为监听套接字

//backlog 确切含义要看TCP/IP协议， 通常设为较大的值1024

int open_listrenfd(int port)

{

int listenfd, opval = 1;

struct sockaddr_in serveraddr;

if (listenfd = socket(AF_INET, SOCK_STREAM, 0)) < 0)

return -1;

/* Eliminates “Address already in use” error form bind , and let server can be stop and start immediatly */

if (setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, (const void *)&opval, sizeof(int)) < 0)

return -1;

bzero((char *) &serveraddr, sizeof(serveraddr));

serveraddr.sin_family = AF_INET;

serveraddr.sin_addr.s_addr = htonl(INADDR_ANY); //通配符地址使得服务器接收任何IP地址

serveraddr.sin_port = htons((unsigned short)port);

if (bind(listenfd, (SA *)&serveraddr, sizeof(serveraddr)) < 0)

return -1;

if (listen(listen, LISTEJQ) < 0)

return -1;

return listenfd;

}

#include <sys/socket.h>

int accept(int listenfd, struct sockaddr *addr, int *addrlen); // 等待来自客户端的请求到达监听描述符，在addr中填写客户端套接字地址

//返回已连接描述符，这个描述符用于Unix I/O函数与客户端通信

监听描述符是作为客户端连接请求的端点的，被创建一次，存在于整个声明周期。已连接描述符是客户端于服务器已经建立连接 的一个端点，服务器每次接收请求都会创建一个，只存在于为一个客户端服务的过程中。

Web服务器

Web客户端和服务器之间交互用的是基于文本的应用级协议，HTTP（超文本传输协议）

和文件检索服务FTP不同，Web服务主要是HTML内容，内容是与MIME（多用途的网际邮件扩充协议）类型相关的字节序列

①取一个磁盘文件、叫做静态内容、服务静态内容。②运行一个可执行文件并返回输出、动态内容、服务动态内容。

http://www/google.com:80/index.html web服务器返回的内容和它管理的某个文件想关联，URL（通用资源定位符）

http://blufish.ics.cs.cmu.edu:8080/cig-bin/adder?15000&213 /cig-bin/adder为可执行文件，?分割文件名和参数,每个参数用&分隔

每个服务器有对其管理的文件的规则，确定是静态内容还是动态内容，常见的是确定一个目录，如cgi-bin，存放所有的可执行文件。

TELNET用于调试在连接上通过文本行与客户端对话的服务器，HTTP标准要求每个文本行都通过一对回车和换行符来结束

HTTP请求：一个请求行（ ，后面跟随零个或多个请求报头，之后再跟随一个空的文本行来终止报头列表

HTTP支持的方法：GET、POST、OPTIONS、HEAD、PUT、DELETE、TRACE

URI（统一资源标识符），URI是相应URL的后缀，包括文件名和可选的参数。浏览器请求内容是可用，代理服务器请求URI需是完整URL

请求报头：

:

， Host报头，客户端和原始服务器之间可以有多个代理（代理链，Host报头指明原始服务器

HTTP响应：一个相应行，后面零个或多个相应报头，之后一个终止报头的空行，再跟随一个响应主体。

一个相应行（ ），状态码200、301、400错误请求、403禁止、404未发现、501方法、505

Content-Type报头告知客户端相应主体内容的MIME类型，Content-Length指示相应主体的字节大小。

服务动态内容

如何做到传送的？（客户端参数->服务器，服务器参数与其他信息->子进程，子进程输出->客户端）

GET请求的参数在URI中传递，？分隔文件名和参数，&分割每个参数，参数中不允许有空格，%20来表示。

对于POST请求，子进城重定向标准输入到已连接描述符中，然后CGI程序重标准输入中读取请求主体中的参数。

服务器收到一个带可执行文件的请求后，调用fork创建子进程，将CGI环境变量QUERY_STRING设为参数列表，并调用execve在子进程的上下文中执行可执行文件，运行后用Unix getenv函数来引用。这个可执行文件常称为CGI（通用网关接口）程序。

在子进程加载并运行CGI程序之前，使用Unix dup2函数将标准输出重定向到和客户端相关联的已连接描述符。子进程负责生成Content-Type和Content-Length响应报头以及终止报头的空行。

第12章 并发编程

并发在不同层面上：硬件异常处理程序、进程、Unix信号处理程序

构造并发程序的三种基本方法: ①进程、②I/O多路复用、③线程

==============================基于进程的并发 begin===================================================

每个控制流都是一个进程，由内核调度和维护，进程有独立的虚拟地址空间，进程间通信（IPC）。

服务器会运行很久，所以必须要有SIGCHLD处理程序回收僵死进程，因为信号会阻塞，所以SIGCHLD必须能一次回收多个僵死子进程。

客户端服务器模型，服务器接收连接请求后，派生一个子进程，子进程获得服务器描述符表的完整拷贝。子进程要关闭监听描述符，父进程要关闭已连接描述符的拷贝，否则会引起存储器泄露。

父子进程共享文件表，但不共享用户地址空间。为了共享信息，必须用显式的IPC（进程间通信）机制，进程控制和IPC的开销很高。

IPC：waitpid、Unix信号是基本的IPC机制。不同主机：套接字接口是IPC的重要形式。同主机: 管道、先进先出、系统V共享存储器、系统V信号量。

============================基于I/O多路复用并发 begin ===============================================

如交互命令等，服务器必须响应两个互相独立的I/O时间：网络客户端发起连接请求；用户键盘键入。

等待哪个事件呢？等待连接请求时就不能响应输入命令了，等待输入命令，就不能响应连接请求了。浪费大量时间。

使用select函数，要求内核挂起进程，会一直阻塞，只有在一个或多个I/O事件发生后，才将控制返回个应用程序。

#include <unistd.h>

#include <sys/types.h>

int select(int n, fd_set *fdset, NULL, NULL, NULL); //返回以准备好的描述符的非零的个数，出错为-1

FD_ZERO(fd_set *fdset); //清除所有

FD_CLR(int fd, fd_set *fd_set); // 去除fd_set中的fd

FD_SET(int fd, fd_set *fd_set); // 添加fd到fd_set

FD_ISSET(int fd, fd_set *fdset);

调用select后fd_set指向乐准备好的子集，所以必须每次调用select时都更新读集合。

基于I/O多路复用的并发事件驱动服务器

将逻辑流模型转化为状态机，一个状态机就是一组状态、输入事件和转移。每个转移将一个（输入状态和输入事件）对映射到一个输出状态。

基于I/O多路复用的并发事件驱动服务器的模型是怎么样的？

池结构、初始化池、select来检测不同类型的输入事件：①新客户端的连接请求到达②一个已存在客户端的连接描述符准备好读。

当请求客户端达到，服务器打开连接，并将客户端添加进池内（创建新的状态机）。最后服务器把每个准备好连接描述符的文本行送回（转移），完成文本行发送，删除状态机。

I/O多路复用：比进程的并发服务器有了更多的行为的控制。运行在单一进程中，每个逻辑流共享进程全部地址空间。不需要切换上下文，更高效。编码复杂，不能充分利用多核处理器。

================================基于 I/O 多路复用 并发end ===============================================

============================================基于线程并发 begin ======================================================

进程是运行在进程上下文中的逻辑流。线程由内核自动调度，每个线程都有自己的线程上下文，包括唯一的整数线程ID，栈、栈指针、程序计数器、通用目的寄存器和条件码。运行在一个进程中的线程共享整个虚拟地址空间。

主线程、对等线程

线程的上下文比进程的上下文小很多，切换快得多。线程不像进程那样严格的父子层次来阻止。和一个进程相关的线程组成的一个对等线程池，独立于其他线程创建的线程。

线程例程：通用指针输入，返回通用指针。若要传递多个参数或返回多个值，都应当封装在struct里，用指向struct的指针传递。

#include <pthread.h>

typedef void *(func)(void *);

int pthread_create(pthread_t *tid, pthread_att_t *attr, func *f, void *arg); //在新线程上下文运行线程例程f。attr改变属性。

// attr oftern set NULL. Returns: 0 if OK, nonzero on error

#include <pthread.h>

pthread_t pthread_self(void);

#include <pthread.h>

void pthread_exit(void *thread_return); //Returns: 0 if OK, nonzero on error

If the main thread calls pthread_exit, it waits for all other peer threads to terminate, and then terminates the main thread and the entire process with a return value of thread_return.

Some peer thread calls the Unix exit function, which terminates the process and all threads associated with the process.

#include <pthread.h>

int pthread_cancel(pthread_t tid); //Another peer thread terminates the current thread.

#include <pthread.h>

int pthread_join(pthread_t tid, void **thread_return); //The pthread_join function blocks until thread tid terminates

//assigns the generic(void *)pointer returned by thet hread routine to the location //pointed to by thread_return, and then reaps any memory resources held by the //terminated thread.

#include <pthread.h>

int pthread_detach(pthread tid); //detaches the joinable thread tid. Thread detach themselves with an argument of pthred_self()

By default, threads are created joinable. In order to avoild memory leads, each joinable thread should either be explicitly reaply by another thread, or detached by a call to the pthread_detach function. Each peer thread should detach itself before it begins processing the request so that its memory resources can be reclaimed after it terminates.

#include <pthread.h>

pthread_once_t once_control = PTHREAD_ONCE_INIT;

int pthread_once(pthread_once_t *once_control, void (*init_routine)(void));

//The pthread_once is useful whenever you need to dynamically initialize global variables that shared by multiples.

要注意对等线程的赋值语句与主线程之间的accept语句是否存在竞争race。先后完成是否结果不同。避免竞争，在accept返回的已连接描述符分配到它自己的动态分配的存储器块。在线程例程中分离线程，接引描述符，释放主线程分配的存储器块。

Thread Memory Model And Shared Variables

Registers are nerver shared, whereas vitural memory is always shared. Each thread has its own separate thread context, which includes a thread ID, stack, stack pointer, program counter, condition codes, and general-purposes register values. Each thread shared virtual address space, include read-only txt(code), read/write data, the heap, and any shared library code and data areas. The threads also share the same set of open files.

Global variables: At run time, the read/write area of virtual momory contains exactly one instance of each gloabl variable that can be reference by any thread.

Local automatic variables: Each thread’s stack contains it’s own instances of any local automatics variables.

Local static varibales: The read/write area of virtual memory contains exactly one instance of each local static variables declared in a program.

使用信号量来对共享变量实现互斥

In general, there is no way for you to predict whether the operating system will choose a correct ordering for you thread.

Load, Update, Store 三个指令在不同线程之间顺序不当更新共享变量的值导致错误。

Progress Graph. 对于线程i，操作共享变量cnt内容的指令(Li, Ui, Si)构成了一个关于某个共享变量的临界区。

两个临界区的交集形成的状态空间区域称为不安全区。绕开不安全区的轨迹线叫做安全轨迹线，接触不安全区的是不安全轨迹线。

Any safe trajectory will correctly update the shared counter.

A semaphore, s, is a global variable with a nonnegative integer value that can only manipultated by two special operations

P(s):If s is non zero, then P decrements s and returns immediately. If s is zero, then suspend the thread until s becomes nonzero and the process is restarted by a V operation. After restarting, the P operation decrements s and returns control to the caller.

V (s): The V operation increments s by 1. If there are any threads blocked at a P operation waiting for s to become nonzero, then the V operation restarts exactly one of these threads, which then completes its P operation by decrementing s.

#include <semaphore.h>

int sem_init(sem_t *sem, 0, unsigned int value);

int sem_wait(sem_t s); / P(s) */

int sem_post(sem_t s; / V(s) */

// Return: 0 if OK, -1 on error

void P(sem_t *s);

void V(sem_t *s);

The basic idea is to associate a smaphore s, initially 1, with each shared variable (or releated set of shared variables) and then surround the corresponding critical section with P(s) and V(s) operations.

以互斥为目的的二元信号量称为互斥锁，对互斥锁执行P为加锁，执行V为解锁。

P和V操作创建了一个禁止区，禁止区包括了不安全区，信号量不变性，没有轨迹线能接触到禁止区。

全局共享变量volatile int cnt = 0;

全局 sem_t mutext;

在主例程中 Sem_init(&mutex, 0, 1);

线程例程中 P(&mutex);

cnt++;

V(&mutex);

无论单核多核，都要同步共享变量。

使用信号量来调度对共享资源的访问

①生产者——消费者问题，buf，三个信号量，mutex实现互斥，slots和items记录空槽和可用数目。

typedef struct {

int *buf;

int n;

int front;

int rear;

sem_t mutex;

sem_t slots;

sem_t items;

} sbuf_t;

void sbuf_init(subf *sp, int n)

{

sp->buf = Calloc(n, sizeof(int));

sp->n = n;

sp->front = sp->rear = 0;

Sem_init(&sp->mutex, 0, 1);

Sem_init(%sp->slots, 0, n);

Sem_init(&sp->items, 0, 0);

}

void sbuf_deinit(sbuf_t *sp)

{

Free(sp->buf);

}

void sub_insert(subf_t *sp, int item)

{

P(&sp->slots);

P(sp->mutex);

sp->buf[(++sp->rear)%(sp->n)] = item;

V(&sp->mutex);

V(&sp->items);

}

int subf_remove(subf_t *sp)

{

int item;

P(&sp->items);

P(&sp->mutex);

item = sp->buf[(++sp->front)%(sp->n)];

V(&sp->mutex);

V(&sp->slots);

return item;

}

②读者——写者问题。第一类是读者优先，第二类是写者优先。一下是读者优先。

int readcnt;

sem_t mutex w;

void reader(void)

{

while(1) {

P(&mutex);

readcnt++

if (readcnt == 1)

P(&w);

V(&mutex);

/* Reading Happen */

P(&mutex);

readcnt–;

if (readcnt == 0)

V(&w);

V(&mutex);

}

}

void writer(void)

{

while(1) {

P(&w);

/* Writing Happen */

V(&w);

}

}

通过生产者——消费者模型编写预线程化的并发服务器。

…

sbuf_init(&sbuf, SBUFSIZE);

listenfd = Open_listenfd(port);

for (i = 0; i < NTHERADS; i++)

Pthread_create(&tid, NULL, thread, NULL);

while (1) {

connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);

sbuf_insert(&buf, connfd);

}

…

void *thread(void *vargp)

{

Pthread_detach(pthread_self());

while (1) {

int connfd = subf_remove(&sbuf);

echo_cnt(connfd); //在线程例程里用pthread_once调用初始化全局变量的函数

Close(connfd);

}

}

基于线程的事件驱动程序

顺序程序、并发程序、并行程序的关系。并行程序是一个运行在多个处理器上的并发程序。并行程序常写为每个核上只运行一个程序

加速比 S(p) = T(1) / T(p)，有时称为强扩展，p为处理器核数，T(k)是在k个核的运行时间

当T(1)是程序在顺序执行版本的执行时间时，S(p)为绝对加速比，当T(1)为程序并行版本在一个核上的运行时间时，S(p)为相对加速比。

效率 E(p) = S(p) / p = T(1) / (p * Tp) ，具有高效的程序在有用的工作时间上花费更多时间，在同步和通信花费更少的时间。

被多个并发线程反复调用时，会产生正确的结果就是线程安全。线程不安全有几类：

①不保护共享变量的函数。②保持跨越多个调用状态的函数。如rand函数就是不安全的，当前调用结果依赖于前次调用的中间结果。③返回指向静态变量的指针的函数。

④调用线性不安全函数的函数。如果是第二类，这种情况唯一的方式就是重写它。如果是第一类和第三类，线性不安全的函数是无法修改的时候采用加锁-拷贝技术。定义包装函数，对互斥锁加锁，调用线性不安全函数，将函数结果拷贝到私有的存储器区域，对互斥锁解锁。

可重入函数：当他们被多个线程调用时，不会引用任何共享数据。将第②类线程不安全函数转化为线程安全的方式就是改写为可重入

Races

A race occurs when the correctness of a program depends on one thread reaching point x in its control flow before another thread reaches point y, forgetting the golden rule that threaded programming must work correctly for any feasible trajectory.

To eliminate the race, we can dynamically allocate a separate block for each integer ID, and pass the thread routine a pointer to this block. And the routine must free the block in order to avoid a memory leak.

Deadlokc

信号量引入了死锁错误，一般是由于P和V操作顺序不当，where a collection of threads are blocked, waiting for a condition that never be true.

互斥锁加锁顺序规则：如果对于程序中每对互斥锁(s, t)，给所有的锁分配一个全序，每个线程按照这个顺序来请求锁，并且按照逆序来释放，那么这个程序就是无死锁的。