操作系统

进程线程调度

略

内存管理

CPU查找一个数据，先进行逻辑地址翻译成物理地址（先查缓存中的快表TLB有无记录，若无，去主存中的页/段表查）

TLB or 主存中最终查得到目标页面的物理地址和该页面是否被调入内存（虚拟内存机制），如果没有调入内存，则产生缺页中断（中断处理将该页面调入内存）

这里获取到物理地址，并确定目标页在内存中之后，就应该通过物理地址去获取数据了。（先查缓存cache中是否存有该物理地址对应的页面，如果没有，再去指定地址的主存查找）

最多要访问两次主存

总体来说就是：逻辑地址->物理地址，（考虑虚拟内存机制），物理地址->访问数据

文件系统

FCB文件控制块

目录结构

硬链接接指针指向目标文件

软链接记录目标文件的路径

访问控制表

文件物理地址分配：

连续分配

链接分配（隐式链接：一个串一个；显式链接：一个FAT文件分配表记录所有链接，FAT在磁盘中只有一张，可以加载进内存，每个表项存放对应块的下一块连接指针）

P.S. FAT32中表示文件大小的那个变量是4个字节，也就是32位表示，所以最大支持4G

索引分配（每个文件都有索引块储存在外存，所以需要IO两次或多次（若为多级索引））

文件储存空间管理（物理块是否空闲分配）：

空闲表法、空闲链表法、位视图法

磁盘：

一个盘面很多磁道，一个磁道划分成固定大小的几百个扇区（通常512B），一个扇区叫一个盘块

扇区是最小可寻址单元

簇是根据不同的文件系统决定的，可以1KB 2KB 4KB等，是每次读写数据时的最小单位

而文件物理地址分配的时候，分配的是簇（因为是读写最小单位），比如FAT里一个表项是一个簇

磁盘调度算法：FCFS、SSTF（最短寻找时间）、SCAN（电梯）、CSCAN（循环）

IO

程序直接控制方式：CPU阻塞等待IO数据

中断驱动方式：IO使用中断通知CPU数据好了

DMA：IO与内存直接交换数据，CPU只在开始和结束做点微小的工作

SPOOLing假脱机：提高IO速度，将独占设备改造为共享设备，实现虚拟设备等（实际上就是把需要打印机要打印的东西先拷到磁盘中，然后挂载到打印机等待队列上，等资源有了就打印）

计算机网络

从高层向下逐层封装，然后到最底层实际通过物理层发送

物理层

①物理层（原生bit流）：

工作设备：中继器，集线器

数据链路层

②数据链路层（帧）：差错控制（确认、超时重传）。流量控制、传输管理；提供点到点通信（点：一个硬件或IP地址）分为MAC（介质访问控制子层）和逻辑链路控制子层

PPP HDLC；工作设备： 网桥、交换机（帧转发），网卡

网卡存在一个唯一的代码：MAC（介质访问控制）地址，也叫物理地址

重传：回退N帧重传（只收顺序帧）；回退N帧缓存窗口只重传丢弃；窗口外丢弃；收一个ACK一个

控制介质访问：ALOHA；间隙ALOHA；CSMA/CD；CSMA/CA(无线)

当数据经过网络层分组转发到达LAN之后，LAN中是在数据链路层MAC地址寻址（具体见网络层的ARP）

网络层

③网络层（数据报）：流量控制、拥塞控制、差错控制、网际互联、路由选择<-路由器（路由选择、分组转发）

IP ICMP ARP RARP OSPF

路由算法：1距离向量（RIP，每个结点仅与它的直接邻居交谈；30秒固定更新；有最高跳数，超出即不可达，以防止环路）

2链路状态（OSPF，每个结点都具有完全的网络拓扑信息，每个结点向所有结点广播，但仅广播与它直接相连的链路的费用，然后问题变成了最短路径问题，使用Dijkstra算法；链路每变化一次就更新，重新计算最小路径）

层次路由：通过层次路由，将互联网划分为很多自治系统，每个自治系统AS（AS内部有很多个路由器，可以由多个局域网组成）自己决定域内的路由选择协议（如RIP、OSPF），对于域外交流，需要用到BGP协议（应用层协议，基于TCP）（一种外部网关协议，用在互联网的网关之间，每个AS选出一个BGP发言人，与其它AS的BGP发言人TCP交换路由信息）

由于链路层数据报有最大传送单元MTU限制，所以IP数据报过大会被分装在多个小的IP数据报中（称为片），然后再在目的地的网络层被重新组装

路由表中的每一行：<目的IP地址，子网掩码，下一跳地址>

分组转发过程：①从数据报首部获取目标主机IP，得到目标网络地址 ②对与路由器直接相连的网络逐个排查，用子网掩码与IP按位与，看结果是否和相应的网络地址相匹配，若匹配则直接交付③若路由表中有目的地址的主机路由，则将数据报传送给该路由④对路由表中每一行的子网掩码和目的IP按位与得到目标网络地址，若与该行的目的IP地址相同，则传送给下一跳路由器⑤若有默认路由，则传给默认路由器⑥出错

注意：得到下一跳路由器的IP地址并不是直接将该地址填入待发送的数据报，而是将IP地址转换成MAC地址（荣国ARP），将其放在MAC帧首部中，然后根据这个MAC地址找到下一跳路由器（链路层）。在不同网络中传送时，MAC帧中的源地址和目的地址要发生变化，但是最终目的IP地址是不会变的。

网络地址转换NAT：通过将专用网络地址（如本地局域网）转换为公用网络地址，从而对外部隐藏内部管理的IP地址

局域网内不需要路由器，因为只有广域网才需要路由转发功能。局域网使用的协议主要工作在数据链路层，广域网使用的协议主要工作在网络层。一个局域网连接进广域网就需要路由器。

IP地址：

分为<网络号，主机号>

网络号首部为标志位（ABCDE类网络）

主机号全为0表示本网络本身，如202.98.174.0

127.0.0.1为回环地址，永远不会出现在网络上（不会被转发出去）

0.0.0.0表示本网络上的本主机

255.255.255.255表示本网络的广播地址

路由器对广播域有隔离作用

子网划分：

不划分子网，即一台机器一个物理地址会使得路由表太大

所以变成：<网络号，子网号，主机号> + 子网掩码

路由交换的时候必须告知子网掩码

网络变成三级结构了

软件实现，将子网掩码与IP地址按位与就可以得到子网地址

CIDR（无分类域间路由选择）：灵活划分子网，可以实现路由聚合，构成超网

表示法：<网络前缀，主机号>/前缀所占比特数，如206.1.0.0/17

仍然有掩码一词，网络前缀-网络号即为人为划分子网数

ARP：每台主机都有一个ARP缓存。主机A欲向本局域网的某主机B发送IP数据报，就先在ARP缓存中查看是否有误主机B的IP地址，若有，则直接查出B的MAC地址。若没有，就通过使用目的MAC地址为FFFFFFFFFFFF的帧来封装并广播ARP请求分组，同一个局域网内的主机B收到ARP请求后，向主机A发送响应ARP分组，包含MAC地址。

主机A收到后写缓存，并向目的MAC地址的硬件发送MAC帧。

ICMP：ICMP是网络层协议！它可以让主机或路由器报告差错和异常情况。分为ICMP差错报告报文、ICMP询问报文；

PING工作在应用层，直接使用网络层的ICMP，不使用TCPUDP

Traceroute/Tracert（跟踪分组路过的路由）工作在网络层，使用ICMP

组播：只发一份，分叉（路由）复制

局域网内不需要网络层的分组转发，直接用交换机即可（数据链路层）；公网就需要网络层分组转发、路由选择，需要路由器（网络层）

传输层

④传输层：屏蔽下层通信子网；为端到端提供可靠的传输服务、流量控制、差错控制、服务质量、数据传输管理等

TCP UDP；提供端到端的逻辑通信（端：运行在主机上的进程，一个进程由一个端口标识，所以叫端）

套接字是一个通信端点：

TCP：面向连接，可靠

UDP：无连接，非可靠（UDP也要校验，有差错就丢弃）

TCP如何做到可靠传输：校验、序号（保证有序）、确认号（标明希望下一个报文段的序号，累计确认至第一个断序处）、重传（超时重传、冗余ACK确认可以快速重传）

TCP流量控制：滑动窗口，每次可以动态要求窗口大小

TCP拥塞控制（防止过多数据注入，以免网络中的路由器或链路过载，一般表现为超时）：[慢开始算法、拥塞避免算法]（慢开始窗口从1开始，倍数增大，到一个门限改用拥塞避免算法，窗口加法增大，第一次超时，窗口变为1，门限减半）、[快重传、快恢复]（快重传指收到3个ACK就认为超时，这时候以门限/2为窗口大小开始发包，直接进入拥塞避免状态）（慢开始和快重传都指的是拥塞/超时从什么时候开始，从1窗口开始是慢开始，从门限开始是快重传，门限都会减半）

一旦发现拥塞，缩小窗口/减少主机发送分组数

关于三次握手四次挥手（非常重要，但这里不解释）

三次挥手的原因：

如客户端发出连接请求，但因连接请求报文丢失而未收到确认，于是客户端再重传一次连接请求。后来收到了确认，建立了连接。数据传输完毕后，就释放了连接，客户端共发出了两个连接请求报文段，其中第一个丢失，第二个到达了服务端，但是第一个丢失的报文段只是在某些网络结点长时间滞留了，延误到连接释放以后的某个时间才到达服务端，此时服务端误认为客户端又发出一次新的连接请求，于是就向客户端发出确认报文段，同意建立连接，不采用三次握手，只要服务端发出确认，就建立新的连接了，此时客户端忽略服务端发来的确认，也不发送数据，则服务端一致等待客户端发送数据，浪费资源。

应用层

⑤应用层（会话层、表示层、应用层）

会话层：不同主机的各个进程之间进行有序的会话，也叫建立同步

表示层：提供数据表示的变换功能

应用层：用户与网络的解谜，如FTP，DNS，SMTP，HTTP，DHCP，BGP

DHCP：基于UDP；往返共四次，都是广播，前面先确认，后面再发送。某计算机启动，①向本地网络广播DHCP发现报文，②只有DHCP服务器才能回复该报文，DHCP先在数据库查找该计算机配置信息，找不到就在IP池中取一个地址，然后将信息广播，DHCP回复称为提供报文（也是广播）③计算机如果接受该配置信息，就通过广播发送DHCP请求报文确认④DHCP广播DHCP确认报文，将该IP地址分配给计算机