计算机考研408总结:detailsofOS,CN...

文件管理&磁盘

1.文件系统的层次结构: 对象及其属性，操纵管理的软件集合，文件系统接口。

2.文件的结构分为有结构(记录型)和无结构(字节流型)；有结构文件分为顺序文件，索引文件，索引顺序文件,直接文件和哈希文件。顺序文件有串结构，顺序结构。有结构文件也可分为定长/不定长记录文件。

3.目录管理的要求: 1.实现按名存取2.提高目录检索速度3.文件共享4.允许文件重名。

4.目录的形式有: 单级文件目录，多级，树型，DAG；

5.影响文件安全性的因素: 人为因素，系统因素，自然因素；

6.分别采用存取控制机制.系统容错技术，后备系统来分别解决上述不安全因素。

7.访问矩阵中增加拷贝权，所有权，控制权来实现有控制的更改访问矩阵。

8.访问矩阵可以用访问控制表(按对象(文件)划分)与访问权限表来实现(按域(user/process)划分)。

9.文件保护的方法: 口令，密码，访问权限表。

10.文件共享的方法 : 利用索引节点(硬链接)，符号链接(软连接) (文件被删除时，链接失效)。

11.目录查询的方法有: 线性检索法， 哈希法。

11.1 在顺序检索的查找过程中，只要有一个文件分量名未能找到，便应停止查找。

12.磁盘的分配组织方法：顺序，链接(隐式，显式(FAT))，索引(链接，多级，混合索引(Unix))

13.磁盘空闲区的管理方式: 空闲表，空闲链表(块，区)，位图法，成组链接(Unix)；

14.位图法: 从0开始编号: i = k/n ; j = k%n ;  从1开始: i = (k-1)/n + 1 ; j = (k-1)%n + 1

15.提高磁盘IO速度的方式: 磁盘缓存，提前读，延迟写，优化物理块布局，虚拟盘，RAID

16.文件在使用前必须先执行OPEN操作，其主要功能是把文件的FCB从外存拷贝到内存，并在用户和指定文件之间建立一条通路，再返回给用户一个文件描述符。

16.1 Open,Close操作提高了文件访问的速度，无需再检索，通过文件描述符直接找到内存中的文件FCB，可以取消显式的open,close操作，但增加系统开销。

17.在树型目录结构中，用户对文件的首次访问通常都采用文件路径名，文件被打开后，对文件的访问通常采用文件描述符，打开文件操作完成的主要工作是把指定文件的目录项(FCB)复制到内存指定的区域。

18.利用Hash法查找文件时，如果目录中对应的目录项是空，则表示系统中无指定文件名，如果目录项中的文件名与指定的文件名匹配，则表示找到了指定文件，如果目录项中的文件名与指定的文件名不匹配，则表示发生了冲突。

19.在目录文件中每个目录项通常就是FCB，在Unix系统中目录项则是文件名及其索引结点指针。 (文件名与文件描述信息相分离，减少目录所占磁盘块数，加快检索目录的速度)

20.引入索引节点后，一个文件在磁盘中占有的资源包括 目录项，索引节点，数据块三部分。

21.在树形目录结构的文件系统中，根节点表示根目录，枝节点表示子目录文件，叶子节点表示数据文件。

22.在执行close过程中，若系统打开文件表项引用计数f.count ≠0(多少进程打开了该文件)，则应置用户文件描述符表项为空；若f.count = 0但内存索引节引用计数i.count ≠ 0，则应使用户文件描述符表项和文件表项皆为空。若i.count =0则应关闭文件。

23.在create过程中，若未检索到指定文件的索引节点，此时属于新建文件，；检索到指定文件的索引节点，此时若允许写，则此时为重写文件，否则是出错。

24.FAT表项通常取半个字节的整数倍。

25.在隐式链接分配中，每个盘块要留出几个字节来放下一个盘块号，FAT表项里面存储的内容即是下一盘块号。

26.对于一个文件的访问常由用户访问权限和文件属性共同确定。

27.Unix操作系统中，输入输出设备被看做是特殊文件。

28.加密保护机制更安全，访问控制表更灵活，必须由系统实现。

29. 目录项 = FCB (Unix 文件名+索引接点指针)

30.硬链接不可以直接删除文件(count --,除非为0)，软链接可以直接删除(链接无效)

31.可顺序存取的文件不一定能随机存取(链式)，可随机存取的文件不一定能顺序存取(索引结构文件)

输入输出系统，设备管理

1. IO软件的层次结构:(硬件，IO控制器),中断处理程序(ISR)，设备驱动程序，设备独立性软件，用户层IO软件。
2. 为什么引入缓冲区: 缓和CPU和IO设备速度不匹配的矛盾；减少CPU的终端频率；提高CPU与IO设备之间的并行性。
3. 为实现设备分配，应为每一个设备设置一张设备控制表DCT,为控制器设置一张COCT,为通道设置一张CHCT，在系统中设置一张系统设备表SDT。为实现设备无关性，系统中应设置一张逻辑设备表LUT。
4. SPOOLing是对脱机IO的模拟，SPOOLing系统中的输入井是对脱机输入中的磁盘进行模拟，输出井是对脱机输出中的磁盘进行模拟，输入进程是对脱机输入中的外围控制机进行模拟，输出进程是对脱机输出中的外围控制机进行模拟。
5. 虚拟设备是指把一个物理设备变换为多个对应的逻辑设备。
6. SPOOLing技术是指在多道程序环境下，利用多道程序中的一道或者两道程序来模拟脱机输入输出中的外围机的功能来达到脱机输入输出的目的。即在联机的状态下，将数据从输入设备输入传送到磁盘或从磁盘传送到输出设备。
7. SPOOLing技术是对脱机输入输出的模拟，必须建立在多道程序系统之上，而且还需要得到高速随机外存(通常为磁盘的支持)，SPOOLing技术主要有1.输入/输出井(Disk)2.输入/输出缓冲(Memory)3.输入进程输出进程4.井管理程序四部分构成。
8. SPOOLing系统中，用户程序可以随时将输出数据放在输出井中，待输出设备空闲时再执行数据输出操作。 输出先放在磁盘输出井，而不是内存。
9. 在实现后台打印时，SPOOLing系统中的输出进程，只为请求IO的进程做两件事情：第一为之在输出井中申请空闲空闲缓冲区，并把要打印的数据送入其中，第二为用户申请一张用户打印申请表，并把用户的打印要求填入其中，再把该表填在假脱机文件队列中。
10. 设备独立性是指用户程序独立于物理设备。
11. 为了实现设备独立性，应设置逻辑设备表LUT，通常包括逻辑设备名，物理设备名，设备驱动程序入口地址。
12. 设备驱动程序是进程和设备控制器之间的通信程序，它将上层发来的抽象IO请求转换为对IO设备的具体命令与参数，并把它装入到设备控制器中的命令和参数寄存器中，或相反。
13. 设备控制器是CPU和IO设备之间的接口，它接受CPU的IO指令，并用于控制IO设备的工作。(设备控制器，或适配器Adapter，也称作控制卡，接口卡，网卡就是设备控制器)
14. 通道是一种特殊的处理机，具有执行IO指令集的能力，主机的CPU和通道可以并行工作，并通过IO指令和IO中断来实现通信与同步。
15. 通道类型有字节多路通道，数组选择通道，数组多路通道。
16. 四级: CPU -> IO通道->IO控制器->IO设备。
17. 一次磁盘访问由寻道时间,旋转时间.数据传输时间组成。其中寻道时间所占比重比较大。
18. SSTF平均寻到时间较短，但容易产生饥饿。SSTF/SCAN/CSCAN算法可能出现磁壁粘着.使用N-step-SCAN可以避免(FCFS+SCAN)，FSCAN是其简化版。课本的SCAN,CSCAN指的就是LOOK,CLOOK吧。
19. 磁盘使用DMA,打印机使用IO中断。
20. 用户层软件: 产生IO请求，格式化IO,SPOOLing;设备独立性软件: 映射/保护/缓冲/分配
21. 设备驱动程序:设置控制器寄存器，检查状态;中断处理程序;IO控制器&设备:执行IO操作
22. 设备分配应考虑的问题: ①设备的固有属性(独占，共享，虚拟)②设备分配算法(FCFS,优先级)③安全性(安全分配，不安全分配。)
23. 设备驱动程序
24. 设备控制器
25. 磁盘的第一个扇区为MBR(主引导记录)(512Bytes) ，包含bootloader(MBR Code启动操作系统的必要代码，typically : GRUB) ,分区表。(有一分区被标志为引导块)
26. 每个分区是一个逻辑磁盘。每个分区的起始扇区以及大小都被记录在磁盘0扇区的主引导记录分区所包含的分区表中。
27. 磁盘传输时间 = 传输字节数/(磁道总字节数) × T  (即这些字节需要转多少度 × 每圈T)
28. 扇区是磁盘的可编址的最小单位，磁盘地址用柱面号，盘面号，扇区号表示。磁盘的存储能力受最内道的最大记录密度所限制。 位密度 ： 字节数/磁道长度。
29. 磁盘格式化 ：低级(物理)格式化:分成扇区。-> 分区 -> 高级(逻辑)格式化:创建文件系统，
30. 磁盘是共享设备，在一段时间内可以有多个用户同时访问。但是在某一时刻，只能有一个作业可以访问。
31. 磁臂移动调度，减少寻到时间。旋转调度: 减少等待时间，旋转时间。总是让首先到达读写磁头位置下的扇区先开始进行传输操作。
32. 优化磁盘物理块的分布式为了减少等待时间。(同一磁道连续编号)
33. 并行交叉存取是为了减少传输时间。(同一柱面，不同盘面。连续编号)
34. 坏块两种解决方式：1.手工处理，2.维护坏块链表。对坏块的处理实质上就是采用某种机制，是系统不去使用坏块，坏块属于硬件故障，操作系统是不能修复坏块的。
35. 设备分配之动态分配(执行过程中根据需要进行分配)(可能发生死锁)，静态分配(一次性分配所有需要的全部设备)(不会发生死锁)。独占设备一般采用静态分配，共享:动态。
36. 单缓冲MAX(C,T) + M；双缓冲MAX(C+M,T),为什么？C,M,T含义？传输过程？
37. 安全分配: 破坏请求保持，；不安全分配 ：可能死锁。请求保持。
38. 逻辑设备表 LUT ①单用户 一张LUT, 【逻辑设备名-物理设备名-驱动程序入口】②多用户，一张系统设备表SDT，每个用户一个LUT 【逻辑设备名-系统设备表指针】
39. SDT(设备类型，设备标识符，DCT,驱动程序入口),DCT(类型，id,状态，相连控制器表指针，队首指针),COCT(id,状态，相连通道表指针，队列首/尾指针),CHCT(id,状态,连接的控制器表首地址，队列首/尾指针)的表项。SDT中每一个表项有一个DCT指针，DCT里面有一个COCT指针，COCT里面有一个CHCT指针，CHCT里面有COCT表首地址。
40. 先分配设备，再分配控制器，最后分配通道。只有在设备，控制器，通道三者都分配成功，这次的设备分配才算成功。设备分配过程 SDT-> DCTs -> COCTs -> CHCTs       PCB插入DCT，COCT,CHCT等待队列，
41. 内存映射IO 即 统一编址。
42. 存储型设备，以块为单位传输。独占设备:一段时间内只允许一个用户进程使用。共享设备:一段时机内允许多个进程使用，但是每一时刻只允许一个。虚拟技术是指将一个独占设备变换为若干台逻辑设备。
43.  
44. 块设备可寻址到字节，分配共享设备不会死锁。共享设备必须是可寻址的和可随机访问的设备。
45. 用户层软件，设备无关层软件，驱动程序，中断处理程序，每一层都做什么事情？
46. 缓冲池:三个队列,四种缓冲区;空/装满输入数据/装满输出数据队列.收容/提取输入/输出。
47.  

内存管理&VM

1. 链接[多模块-> exe]【静态，装入时动态链接(都链接,但可变)，运行时动态链接(不用不链接)】
2. 装载【绝对装入(单道)，静态重定位(多道系统)，动态重定位(支持可移动,对换/紧凑/VM)】
3. 静态重定位即可重定位装入，地址变换装入时一次完成。装入时分配要求的全部内存，在运行期间不能在内存中移动，也不能再申请空间。
4. 动态重定位:装入内存时并不立即把相对地址转换为物理地址，而是推迟到执行时才进行。装入内存的均为逻辑地址，需要重定位寄存器。可以分配不连续，装入部分，动态申请。
5. 目标文件，可执行文件
6. 紧凑，覆盖，对换
7. 在连续分配方式中，可以使用紧凑来减少内存零头，但是需要动态重定位的支持。
8. 存储保护: 防止地址越界，防止操作越权。
9. 内存分配 : 连续分配【单一，固定，动态】,离散分配【页，段，段页】
10. 分配算法：First Fit , Best Fit , Worst Fit , Next Fit.
11. 首次适应:空闲分区按照地址排序；最佳适应:按照容量大小递增排序。最差: 大小 减。
12. 循环首次: 使得空闲分区分布的较为均匀。
13. 伙伴系统: 静+动 分配。 分配/回收算法: 递归。
14.  buddy(x) = x + 2^k (x Mod x^k+1 == 0) ; x - 2^k (x Mod x^k+1 != 0)，
15.  buddy(x) = x + 2^k - [ (x/2^k) % 2 ]* 2^k+1 通用
16. 多级N级页表：最多访存N+1次；ɑ: TLB hit rate ε：TLB hit time t：Memory
17. 带TLB 访问: EAT =ɑ(t+ε)+(1 -ɑ)*(（N+1）*t +ε) ?过程？ 若TLB,页表并行计算？不同!  
18. 页表: 逻辑块号[可略]:物理块号 段表: 段号[可略]:段基址:短长
19. 分段有利于共享，动态链接，动态增长
20. 反置页表:整个系统一张 物理页号:进程:逻辑页号，利用进程ID/页号检索->很慢 -> HASH
21. Load R1,1000;采用静态重定位，该指令的第二个操作数修改为1000+起始地址。采用动态重定位则仍然为1000.
22. 静态链接实在 装入程序前 进行的。动态链接是在装入时，或者运行时进行的。适合于动态链接的存储方式是 分段 。
23. 产生内部碎片 ：分页，段页式，静态多分区，单一连续。产生外部碎片: 动态分区，分段
24. 常规存储器: 一次性，驻留性。虚拟存储：多次性，对换性，虚拟性。
25. 虚拟存储必须建立在离散分配的基础之上，有请求分页，分段，段页式等方式。
26. 分配置换策略，可变分配，固定分配；局部置换，局部置换。
27. Clock是一种常用的近似LRU算法，又称为NRU最近未用算法。
28. Clock 查0()
29. 整体对换从逻辑上也扩充了内存，因此也实现了虚拟存储器的功能。  False错误。
30. 驻留集，工作集
31. 驻留集 =m 

概论

进程管理&死锁

PV操作

特征

操作系统的特征

进程的特征

顺序执行，并发的特征

死锁的四个条件

进程映像 = 程序段 数据段PCB

循环等待 按递增顺序申请资源

死锁定理

单一连续分配，固定，动态多分区分配

分段，分页，段页式

局部性原理

一连续分配，固定，动态多分区分配

通道

RAID

成组链接

1. 运行->> 就绪   时间片完，抢占
2. 原语，系统调用
3. 进程的线程共享同一个地址空间
4. 处理机中可能没有处于运行状态的进程，因为此时系统处于死锁状态，所有进程阻塞。
5. 若不处于死锁状态，只要就绪队列非空，那么就可以择一而运行。
6. 进程是资源分配/拥有以及调度的基本单位。在引入线程的系统中，线程是调度的基本单位。
7. 用户级线程，内核级线程，映射关系多对一，一对一，多对多？优缺点
8. 高级调度，中级调度，低级调度?
9. 响应时间，等待时间，周转时间，加权周转时间= 周转时间/实际执行时间->平均加权周转时间
10. FCFS,SJF,优先级，高响应比优先，RR，多级反馈队列(优先级?时间片?FCFS&RR? 插队尾)
11. 抢占式，非抢占式短作业优先都可能会产生饥饿现象。
12. 短作业优先 平均周转时间最短
13. 优先级 IO密集型 > 计算密集型
14. 高响应比优先调度,主要用于作业调度。响应比 = (等待时间+执行时间)/执行时间
15. 多道批处理系统 作业调度(辅寸->主存Ready)  + 进程调度(Ready->Running)

应用层

1. 不一定要有域名，但是一定要有IP地址
2. 一个主机可以有多个域名(虚拟主机)，也可以有多个IP(多个网卡)
3. 一个域名可以解析为多个IP (负载均衡)

网络层

1. IP地址 ：4B 32位；IPV6 128位，16B ;MAC地址 48位，6B
2. A类(0... , 8位网络1 - 126)B类(10.... , 16位网络号，128.1 - 191.255)，C类(110，24位网络号,192.0 - 223.255)，D类(多播地址，1110，)，E类（1111，保留）

1. IP地址不仅指明一台主机，而且指明了主机所连接的网络，而MAC地址仅仅指明一台主机。与该主机所连接的网络毫无关系。
2. 主机号全0表示本网络本身，主机号全1表示本网络的广播地址。
3. 32位全0表示本主机0.0.0.0；32位全1表示整个TCP/IP网络的广播地址，由于路由器对广播域的隔离，255.255.255.255等效为本网络的广播地址。
4. (A类)127.0.0.0即网络号为127保留作为本地软件环回测试，本主机内部进程之间通信用。
5. 目的地址为环回地址的IP数据报永远不会出现在任何网络上。 127.x.x.x

回环地址范围 127.0.0.1 ~ 127.255.255.255

NAT地址范围

10.0.0.0 ~ 10.255.255.255,   172.16.0.0 ~ 172.31.255.255 ,     192.168.0.0 ~ 192.168.255.255

组播地址范围

1. 根据网络号来转发分组，不考虑目的主机号。
2. A-E类(网络号,主机号)-> 子网划分(从主机号借)(网络号,子网号,主机号),子网掩码 ->CIDR(网络前缀，主机号)/前缀长度 最长前缀匹配，路由聚合(超网)
3. 路由器具有两个或以上的IP地址，即路由器每一个接口都有一个不同网络号的IP地址。
4. 当两个路由器直接相连时，在连线两端的接口处，可以分配也可以不分配IP地址，如果分配，则这一段连线就构成了一种只包含一条线路的特殊网络，为了节省IP地址资源，常常不分配IP地址。
5. ARP工作流程; 本局域网内部之间; ARP请求广播，响应单播; 不在一局域网如何？
6.  RIP : Distance Vector, OSPF : Link State ,BGP : Path Vector (路径向量)
7. RIP : 16条，每个30S交换路由表，180s不可达，UDP:520应用层协议，适合小网络。环!
8. OSPF：链路状态变化洪泛链路状态，Dijkstra,AS划分区域，适合大网络，IP封装，网络层协议。收敛速度快!
9. BGP ：选择较好的路由，交换可达性信息，TCP连接传输BGP报文，应用层协议. BGP首次发送整个路由表，之后之更新有变化的部分。
10. RIP,OSPF,BGP都支持CIDR。
11. RIP仅和相邻路由器交换信息，OSPF向本AS内所有路由器发送信息。
12. ICMP报文两种，差错报告报文(终点不可达，源点抑制，超时，参数问题，改变路由(重定向))，询问报文(回送请求和回答(PING使用)，时间戳请求和回答)
13. PING(测试两主机间的连通性)工作在应用层，直接使用ICMP，没有使用传输层协议。
14. Traceroute(跟踪分组经过的路由器)，工作在网络层。
15. PING使用ICMP回送请求和回答报文，Traceroute使用ICMP超时报文和终点不可达。
16. 不应发送ICMP差错报文的情况:①对ICMP差错报告报文不再发送ICMP差错报告报文②对第一个分片的数据报片的所有后续分片都不发送ICMP差错报告报文③对具有组播地址的数据报都不发送ICMP差错报告报文④对特殊地址(127.0.0.0,0.0.0.0)的数据报不发送ICMP差错报告报文。
17. NAT 整个专用网使用少量的全球IP地址，NAT路由器，NAT转换表({全球IP地址:port}:{私有IP地址:port})，普通路由器转发IP数据报时不改变源/目IP，而NAT路由器在转发IP数据报时，要更改IP地址，普通路由器工作在网络层，NAT路由器需要查看传输层的端口号。

NAT表项由管理员添加。

1. IP多播(组播),仅应用于UDP(TCP不能用,why?),为什么组播？组播分为硬件组播(局域网内)以及因特网范围内组播，对组播数据报不产生ICMP差错报文。硬件组播MAC地址范围为

01-00-5E-00-00-00~01-00-5E-7F-FF-FF(后23位是组播IP地址后23位)，组播IP地址与以太网IP地址不是一一映射的(32:1)，因此收到组播数据报的主机，还要在IP层利用软件进行过滤。

IP组播地址，D类地址，并非所有D类地址都可以..

以太网广播FF-FF-FF-FF-FF-FF，组播01-00-5E-....。

IGMP协议是让连接在本地局域网上的组播路由器知道本局域网上是否有主机加入或退出了某个组播组。

组播路由选择协议找出以源主机为根节点的组播转发树。三种(LinkState,DV,协议无关)。

对不同的多播组有不同的多播转发树，同一个，不同的源点也会有不同的转发树。

1. 移动IP，移动节点，归属代理(本地代理【主地址，辅地址】)，外埠代理(外部代理)。通信过程。注册/注销转交地址,隧道。
2. 路由器 vs. 网桥/交换机 vs. 集线器/中继器
3. 在同一个网络中转递数据无需路由器的参数，而跨网络通信必须通过路由器进行转发。
4. 路由表(软件实现)[目的IP:子网掩码:下一跳:接口] -> 转发表(可软可硬)[目的IP：下一跳]
5. IPv6双协议栈，隧道
6. IP地址靠软件来维持而硬件地址。虚拟地址。
7. 主机收到广播/多播帧: NIC网卡筛选多播，接受每一个广播。CPU筛选广播。
8. IP协议规定，所有主机和路由器必须能够处理的IP数据报不得小于576字节，也就是说，只要IP数据报不超过576字节，这样的数据报就肯定不需要分片。(链路层MTU也大于之)
9. IP数据报3个长度，首部长度4位，单位4B，IP数据报长度16位，单位字节B，分片偏移，单位8B。故首部最长为15*4B = 60B,IP数据报最长为2^16-1 = 65535B(首+数据)
10. 路由器利用IP首部校验和检测出差错时，简单丢弃。不发送ICMP报文！因为srcIP！
11. MTU 不包含MAC帧的首部和尾部字段。因此MTU 即IP数据报的最大长度。
12. 网络层向上传输层提供的服务有两种，面向连接(虚电路)和无连接(数据报服务)。
13. 直接交付，间接交付
14. 路由器连接的多个局域网中，物理层，链路层，网络层协议可以不同；
15. 静态路由(非自适应路由)，动态路由(自适应路由)
16. 慢收敛是导致发生路由回路的根本原因。
17. 若IP数据报长度大于MTU而且，DF = 1即不允许分片，则向源主机发送ICMP差错报告。
18. IP数据报经过一个路由器，源IP和目的IP不改变，源MAC目的MAC改变。
19. 默认路由  0.0.0.0/0
20. OSPF 通过Hello分组来维持与其邻居的连接。当链路状态改变的时候，广播LSU分组。
21. OSPF将一个AS划分为若干区域，用户规模更大的网络。划分区域的好处就是把洪泛法交换链路状态信息的范围局限在每一个区域而不是整个AS。每一个区域内部的路由器只知道本区域的完整拓扑。主干区域。区域内部路由器，区域边界路由器，主干路由器，自治系统边界路由器。
22. 路由器路由选择部分:路由选择处理机，路由选择协议，路由表
23. 路由器转发部分: 交换结构，输入端口，输出端口。
24. 路由器转发速度最慢。
25. 广域网不需要分片，因为广域网能够通过的最大分组长度是该广域网内中所有节点都事先知道的。
26. 使用几次ARP解析？
27. 如果一个路由器要同时连接再一个以太网和一个ATM网络上，需要添加两个硬件，一个是以太网适配器，一个是ATM适配器。
28. IPv6 变化，零压缩，双协议栈，隧道

运输层

1. UDP 数据报（User Datagram Protocol） TCP : 报文段 (Transmission Control Protocol)
2. 16位端口号 65536个端口 (熟知端口号0-1023,登记端口号，短暂端口号)
3. 两台计算机中的进程要通信，不仅要知道对方的IP地址，还要知道对方的端口号。
4. IP层只检验首部，对数据部分不检验。传输层UDP/TCP对整个报文检验。
5. UDP首部 : 16位源port ,  16位目的port,，                          长度>=8
6.           16位长度 ，  16位checksum   数据部分(如果有)          首部长8字节
7.  UDP首部 8B,TCP 首部 20B , IP 首部 20B , 以太网首部14B,4B(尾部FCS) TCP ：20+4N
8. UDP是面向报文的，TCP是面向字节流的 (UDP对应用层报文直接加上头部交付IP层，不合并，不拆分。而是保留这些报文的边界。IP层可能会对其分片，影响效率)
9. UDP 支持一对一，一对多，多对一和多对多的交互通信，无拥塞控制。UDP可多播
10. TCP会根据网络的拥塞程度以及接收方接受窗口决定发送多长字节。
11. 接受方收到有差错的UDP用户数据报应如何处理，简单的丢弃!  同IP
12. 如果应用程序愿意使用UDP完成可靠传输，这可能吗? 可能，由应用层来实现可靠传输。
13. TCP必须先建立连接再传送数据，TCP只能是点对点的(一对一)，全双工(同时收发)
14. TCP建立的连接是虚连接，不是一条真正的物理链路。
15. 两个进程之间建立了TCP连接，实际上套接字之间的TCP连接，TCP连接的端点是套接字(IP : port)
16.  IP , UDP 尽最大努力交付。
17. TCP连接建立 ①.SYN =1 ,ACK = 0,SEQ = x;②.SYN = 1,ACK = 1,SEQ = y,ack = x+1;③.SYN = 0,SEQ = x+1,ack = y+1;   （ACK (有效),ack(序号)，连接过程中ACK = 1）
18. TCP 连接释放 ①FIN = 1,SEQ = u ②SEQ = v,ack = u+1 ③FIN = 1,SEQ = w，ack = u+1④SEQ = u+1,ack = w +1
19. SYN,FIN都消耗1个序号。 整个过程发两个SYN,两个FIN报文，连接确认一次SYN,释放确认两次FIN。ACK不消耗一个序号，计整个过程中多消耗4个序号。(2SYN,2FIN)
20. URG,ACK,PSH,RST,SYN,FIN,窗口，紧急指针，选项（MSS最大数据部分长度）
21. 发送窗口，接受窗口，拥塞窗口， ssthresh(慢开始阈值)
22. 慢开始与拥塞避免，快重传与快恢复
23. 以太网规定重传16次认为传输失败，但是TCP没有规定最大重传次数。
24. 链路层的HDLC协议，网络层的X.25协议都要确认机制与窗口机制。广泛使用的PPP，IP无。HDLC按帧确认，TCP按字节确认。
25. TCP有重传计时器，持续计时器，保活计时器，时间等待计时器(2MSL连接释放最后)(why?)
26. TCP需要计算RTT,而UDP不需要计算RTT。
27. 假定在一互联网中，所有链路的传输都不会差错，此时TCP的可靠交付是多余的？错误!
28.  TCP报文段总长度 ≤ Min[(对方给的MSS+TCP首部) ， 65515B]  (假定IP使用20B首部)
29. IP数据报总长度小于65535B，若IP使用20B首部，则TCP报文段不能超过65515字节。
30.  RTTs = (1 - α ) *旧RTTs +  α*新RTT样本 α常取1/8
31. 网络层使用数据报(不可靠)或虚电路(可靠 主机与主机之间)，传输层仍然可能出错，为了保证可靠通信不论网络层提供多么可靠的服务，运输层仍然必须由可靠交付的协议。
32. 分伪首部既不向下传送也不向下递交，而仅仅是为了计算运输层校验和。
33. 停等协议中，不使用编号不行，需使用0，1两个编号，收到重复的报文段不予理睬也不可行(一直超时重传)。收到重复ACK可以不予理睬，传输层不能使用停等协议(只用0-1编号)
34. n位用于分组编号，GBN :  1 ≤ Wt≤ 2^n -1  SR：Wt + Wr ≤ 2^n ;Wtmax = Wrmax = 2^n-1
35.  在TCP如果有一个ACK丢失了，那么一定会使对应的报文段重传。错误! (收到更大ACK)
36. 如果接收方UDP发现收到的报文中目的端口号不正确(即不存在对应端口号的进程)，就丢弃该报文，并由ICMP发送端口不可达差错报文给发送方。
37. TCP校验和是必须的，UDP校验和是可选的(全为0)。UDP校验和计算结果为1，说明无误。按照二进制反码运算求和再取反。
38. 端到端，port-port传输层
39. 服务器端的资源是在第二次握手完成时分配的，而客户端是在第三次握手时分配的，使得服务器容易受到SYN洪泛攻击。
40. 一个套接字只能与远程的一个套接字相连。
41. 同一个端口号既可以TCP,也TCP。

链路层

物理层

1. 奈氏准则 理想无噪声信道 极限数据传输速率2Wlog2(V) bit/s W,V含义？
2. 信噪比 S/N 10log10(S/N)
3. 香浓定理: Wlog2(1 + S/N)
4. 什么是编码，调制？
5. 曼彻斯特编码(按起始)，差分曼彻斯特编码(起始跳变为0，不跳变为1)
6. 数字数据-> 数字信号 (非归零，曼彻斯特，差分..)
7. 数字数据-> 模拟数据 (ASK,FSK,PSK,QAM[A+P],Wlog2(m*n))
8. 模拟数据-> 数字信号  PCM(抽样，量化，编码)
9. 模拟数据-> 模拟信号
10. 分组交换，报文交换，电路交换。
11. 电路交换时延较小，在出错率很高的信道上，选择数据报方式更合适。
12. 将基带信号直接传送到数字信道上的传输方式是基带传输。将基带信号经过调制之后传送到模拟信道上的方式是频带传输。宽带传输？
13. 多模光纤:近距离传输，发光二极管；单模光纤:远距离传输。激光二极管。
14. 微波直线传输。
15. PDU,SDU,PCI; n-PCI + n-SDU = n-PDU = n-1-SDU
16. 会话层5，表示层6

组成原理

概论

1. 基准测试程序执行的越快，不能说明机器的性能越好。
2. 高级语言程序，汇编程序都不能再机器上直接执行，只有机器语言可以。
3. 冯诺依曼机: 存储程序(stored program) (ENIAC不是)
4. 高级语言虚拟机级->汇编语言虚拟机级->OS虚拟机级->机器语言机器级
5. 同一个功能既可以用硬件实现也可以用软件实现。
6. 总响应时间(感觉到的时间) =  CPU 时间 + 其他时间；
7. CPU时间 = 用户CPU时间 + 操作系统CPU时间；其他时间：IO/执行其他操作时间 ；
8. 性能 = 1/执行时间    性能/速度 ，时间
9. 相联存储器既可以按地址又可以按内容寻址。
10. 对用户透明的寄存器IR,MAR,MDR不透明可见的PC，FLAGS，通用寄存器

数据的机器级表示

1.C语言强制类型转换 ： 有符号数->无符号数

2.浮点数除数为0，结果是无穷大+-∞，不是溢出异常

ASCII 0-9(30-39H)，A ( 65D) , a( 97D )

3.字，字长;字长(数据通路的宽度) 字(处理信息的单位，用来度量数据类型宽度，x86 字16bit)

4.码距(Hamming Distance海明距离) 奇偶校验码码距 = 2，8421码码距 = 1

5.海明码①确定位数 2^r ≥ m + r + 1，②.放在1，2，4，8....(从1开始编号)(组成原理从右开始，计网从左开始)③确定校验位0/1 异或为0④检错，翻转之。

6. L - 1 = D + C (L: 码距 D : 检错位数 C :纠错位数)

7.检错d位，需要d+1位码距；纠错d位,需要2d+1位码距；纠错d1位，同时检错d2位，则码距d1 + d2 + 1（d2≥d1）分

8.若码距d为奇数，则可以发现d-1位错，或者能纠错(d - 1)/2位

若码距d为偶数，则可以发现d-1为错，或者能发现d/2位并纠d/2-1位

1. 求补码 正:0 + ...负数各位取反末尾加1，；[x]补 = [-x]补取反 + 1
2. 求移码，加bias,一般2^n-1,或者先求补码，符号位取反；求移码真值，减去bias。移码补码只是符号位相反，因为差2^n-1（补码加2^n）
3. MSB（最高有效位，最高有效字节）,LSB（最低有效位，最低有效字节）
4. 数据元素起始地址都是低地址
5. 确定一个数值元素的值需要①进制②定点/浮点③编码方式
6. 三种补码判断溢出的方式(进位次进位，结果符号，变形补码)
7. 浮点数的指数只用移码，可以简化对阶，即比较阶大小的过程。
8. IEEE754 零的表示，正0 ：00000000H负0 ：80000000H 当
9. 10^3,6,9 时钟频率：GHz,MHz ,带宽Gb/s,Mb/s,数据传输率，
10. 2^10,20,30 内存容量:GB,MB,KB
11. 补码/移码0的表示唯一，原码/反码表示不唯一，浮点数有+0，-0
12. n位2进制数补码，其模式2^n ,[x]补 = x0 . x1x2x..n的模是2。
13. 相同位数的补码，移码具有相同的表数范围。
14. CRC加零个数为G(x)次数。CRC码 = 数据 + 校验码（G(x)次数）
15. IEEE 754 float 32bit = 1+8+23 bias127;double64bit = 1+11+52 bias 1023;
16. 浮点数表示与转换
17. 规格化尾数。原码：尾数最高位是1；补码：符号位，和尾数最高位异号。
18. 浮点数精度取决于尾数位数，表示范围取决于阶码位数。

运算

1. 浮点数没有移位，拓展。
2. MIPS运算指令区分有符号，无符号。无符号不检测是否溢出。
3. X86不区分，解释不一样。
4. & | ~ ^
5. 浮点数加减法 ①对阶(小向大)②尾数加减(原码)③规格化(左归右归)④舍入(就近偶数，舍入位)⑤溢出判断（上溢：阶码全1，下溢：阶码全0）【尾数为0则结果为0】
6. 移位溢出判断：①逻辑移位：针对于无符号数，右移不考虑溢出，左移时移出位为1则移出。②算术移位：针对有符号数，右移不考虑，左移时移位前后符号改变则溢出。
7. 补码加减法溢出判断：①进位次进位，②结果符号③，变形补码
8. 原码加减法：符号位，数值位 分开运算。
9. 浮点数：大数吃小数
10.  
11. 移码加减法：移码的和，差等于和，差的补码。通过移码计算和差的补码，最后将符号位取反。

①②③④⑤

①②③④⑤

存储器

1. (存储元件，记忆单元,Bit) 0/1 --> 存储单元(8位，16位，32位..) --> 存储体

DRAM 地址复用(容量太大)；分时传送地址，靠行列地址RAS,CAS选通信号来区分地址引脚线上传送的是行地址还是列地址。N -> 2√N

1. 主存Memory 包括RAM,ROM.并不是只用DRAM
2. 半导体存储器都采用随机存取方式进行读写。错误! 如相联存储器
3. 多模块存储器之所以能快速访问，是因为各模块有独立的读写电路。
4. 虚拟内存大小由地址空间决定。逻辑地址的位数。与磁盘/内存容量没有直接的关系。
5. Cache不能增加存储容量。因为存放的是放在主存里面的信息副本。
6. TLB miss【页表中找，找到修改TLB，访存；不在页表转Page Fault】,Page Fault【调页，修改TLB,页表，重新执行当前指令】,Cache miss【读miss : 调进来 写miss :分配/不分配】分别做哪些动作？
7. 分段比分页更利于存储保护。
8. 每次执行存储器访问，都要进行逻辑地址到物理地址之间的转换吗？
9. 逻辑地址到物理地址之间的转换是由硬件还是由软件实现的？
10.            

1. 虚拟存储对应用程序员透明，对系统程序员不透明。
2. 计算Cache容量 Tag valid modified,cache block
3. 4路组相连LRU为2位，2路组相连LRU为1位。
4. 全相连依次装入，Cache地址？

指令系统

1. 累加型指令的一个源操作数和目的操作数总是在累加器中。
2. 堆栈型:操作数和结果都在栈顶，都是零地址一地址指令，对指令序列的顺序要求严格。对于双目运算，采用软堆栈(主存)需访存4次(取指,取两操作数,写结果)，硬堆栈(寄存器)访存1次。(取指)
3. 相对寻址用于公共子程序的浮动，转移
4. 操作数可能位于寄存器，主存，堆栈，IO端口，立即数。
5. 偏移寻址有3种 ： 基址寻址，变址寻址，相对寻址。
6. 寄存器直接寻址:操作数在寄存器中，OP = R[r1]，使用寄存器编号EA = r1；寄存机间接寻址：操作数在内存中，OP = M[R[r1]]地址为寄存器内容EA = R[r1]。
7.  基址寻址：形式地址(给出的地址值)为偏移 + 基址寄存器内容。EA = (B)+ A；变址寻址: 形式地址为数组的首地址(给出的地址为首地址)。+变址寄存器内容。EA = A + (Reigister) 如  mov al , [SI + 1000H]
8. 定长操作码，拓展操作码【不允许短码是长码的前缀】
9. 隐含寻址，立即寻址，直接寻址，寄存机直接寻址，寄存器间接寻址，偏移寻址(基,变,相)
10. 一次间接寻址，2次间接寻址..   各个寻址方式的访存次数
11. 变址间址结合使用;先变址再间址: EA = ( (I)+A ) [先变];先间址再变址 EA = (I) + (A) [后变址]
12.  

总线

IO

中断

CPU

流水线

线性数据结构

树

图

查找

1.二叉排序树：查找，插入，删除(叶子，非叶子)

2.AVL树：插入(LL,RR,LR,RL，根节点选择?第一个不平衡的点)，删除(自底向上改变bf,调整，可能调整多次)

3.B树插入与删除，B+ vs. B

4.BST 最坏O(n) ,AVL最坏 O(log2N)

5.除留余数法，p一般选择≤表长的最大素数。

6.线性探测法容易产生堆积问题，平方探测法可以减少发生堆积问题，缺点是不能探查到Hash表上的所有单元，但是至少能探查到一半的单元。

排序