408选择题笔记|自用|随笔记录

在内存中进行：
二叉搜索树、AVL树、红黑树

B树：

平衡：所有叶节点在同一层
有序：节点内有序
多路：最多m个分支，m-1个元素

• 删除操作一定会导致叶结点的变化
• 插入操作可能增加树的高度

访问节点

访问结点是在硬盘上进行的，结点内的查找是在内存中进行的。
在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或者折半查找查询等于k的关键字。

在B树查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。

# define m 3
typedef struct BTNode{int keynum;//B-树的阶 struct BTNode * parent;//指向双亲结点KeyType key[m+1];//关键字向量，0号单元未用struct BTNode *ptr[m+1];//子树指针向量Record *recptr[m+1];//记录指针向量，0号单元未用
}BTNode,*BTree;

typedef struct{
BTNode * pt;
int i;//
int tag;
}Result;

没有下溢的删除

父下来，兄上去（左兄或者右兄）

父亲节点下移到左，然后右并过来

链接

所有分支节点中仅包含它的各个子结点中关键字最大值及指向其子节点的指针。

在B+树中，非叶结点不含有该关键字对应记录的存储地址【使用更少的层数存储，1块数据中保存的关键字更多】。可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，读磁盘次数更少，查找更快。

每查找一层节点都要读磁盘

影响散列方法平均查找长度：

1. 装填因子
2. 散列函数
3. 冲突解决策略

堆可以看作完全二叉树，不能看作二叉排序树，因为左右未必有序

直接插入和简单排序辅助空间都是O（1）
直接插入在有序数组上的比较次数为n-1
简单排序为n(n-1)/2

建堆！=将结点插入空堆

建堆（整个写成二叉树之后调整）!=插入空堆（每插入一个数就进行调整）
快速排序空间复杂度$O(lo{g}_{2}n)$，不稳定，基本无序
快速排序不稳定

直接插入排序稳定

无向连通图G中各边的权值均为1，G可以视为无权图，可以使用广度优先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比Dijkstra算法更高效。

Prim适合求边稠密的算法
Dijkstra适合求点多的算法

现有长度5，初始为空的散列表HT，散列表函数H(k)=(k+4)mod5用线性探查再散列解决冲突。若将关键字序列2022，12，25依次插入HT中，然后删除25.HT中查找失败的平均长度（1.8）

采用开放定址法时，不能随便物理删除表中的已有元素，因为删除元素，可能会截断其他具有相同散列地址的元素的查找地址，因此要删除一个元素时，可给它做一个删除标记。依次将2022，12，23插入散列表，然后删除25

不稳定排序：选择排序，希尔排序，快速排序，堆排序
稳定排序：插入排序，冒泡排序，归并排序，基数排序

数据结构的逻辑结构独立于存储结构（现有逻辑结构再由存储结构）
链式结构结点内存储空间连续，结点之间存储空间可以不连续

时间复杂度O($n^2$)表明算法执行时间与$n^2$成正比

线性表的顺序存储结构：随机存取
线性表的链式存储结构：顺序存取

静态重定位：装入时。
动态重定位：动态运行时装入，执行时进行。

页式管理中，页表的起始地址放在寄存器中。
程序装入时放在pcb中，上cpu时存放在页表基址寄存器ptr中

设备映射表：建立逻辑设备与物理设备的对应关系

进程关闭文件，内存索引节点计数-1，当链接计数变为0，文件系统会释放内存索引节点。
命令接口：联机用户接口和脱机用户接口。

操作系统与用户通信接口：

1. shell
2. 命令解释器
3. 缓存管理指令

分时系统追求的目标：比较快速响应用户

操作系统必须提供的功能：中断处理

广义指令

广义指令只能在核心态下进行
分层操作系统清晰，容易调试，依赖关系单一，调用接口设计困难
模块操作系统清晰，不容易调试

SMTP支持在邮件服务器之间发送邮件，也支持从用户代理向邮件服务器发送信息，只支持传输7比特的ASCII码内容。
接入网络的时候可能使用到PPP（广域网协议）协议
单纯访问网页不可能用到SMTP协议

默认情况下FTP使用TCP20端口进行数据连接
是否使用20端口与传输方式有关

• 主动方式：TCP20
• 被动方式 : 服务端与客户端协商

TCP连接方式：
Close：非持续连接，告诉服务器发送完请求的文档后即可释放连接
Keep-alive：持续连接

IP分组只有首部校验和：不可靠
TCP/IP网络层提供的是无连接不可靠数据服务

100BaseT（T双绞线twist）

求每个子网可容纳的主机数量

主机位32-18=14
$2^{主机位-1}-2=2^{14-1}-2=2^{13}-2=8192-2=8190$
所以，每个子网可容纳的主机数量为8190

快重传：3次乱序冗余就重传

程序如何分段是在用户编程时决定的
分段式存储管理有利于动态链接，都是按照逻辑块进行划分的。
可重入程序是通过减少对换数量改善系统性能的
操作系统实现分区存储管理方式代价最小

线性表元素序号从1开始
数组下标序号从0开始
链式存储结构比顺序存储结构更能方便地表示各种逻辑结构，链式结构更好地体现直接前驱和后继
LRU算法实现起来耗费高的原因是：需要对所有页进行排序，结果是需要硬件的特殊支持

页故障：使用合法位判断是否产生页故障（是否处在内存中/是否缺页异常）
所有的页面置换策略都可能产生抖动异常
虚拟存储管理系统的基础是程序的局部性原理
使用覆盖、交换可以实现虚拟存储

虚拟内存的实现方式

虚拟内存的实现：
方式：
一、 离散分配

1. 请求分页存储管理
2. 请求分配存储管理
3. 请求段页式存储管理
   二、 需要的东西

• 一定的硬件支持，一定容量的内存和外存
• 页表/段表机制作为主要的数据结构
• 中断机制，当程序要访问的部分还未调入内存时产生中断
• 地址变换机构

请求分页和分页共有的特点：消除了页内碎片
请求分页本质上使用了虚拟内存的方式，可以实现内存扩充
分段存储方式：便于动态链接

UNIX操作系统中将输入输出设备视为特殊文件

文件打开的操作：把指定文件的目录复制到内存指定的区域
调用open，根据文件名搜索目录，将指明文件的属性（包括该文件在外存上的物理地址）
从外存复制到内存打开文件表的一个【表目录】中，并将该表目的编号返回给用户

文件目录项FCB和文件安全性管理级别

文件目录项包括：文件名，文件访问权限，文件所在的物理位置
FCB：记录文件的名字，索引节点指针以及其他目录项的层级关联关系
目录/目录文件：FCB的集合
按名存取：在文件系统中为每个文件设置用户描述和控制文件的数据结构（FCB文件控制块）
目录项：数据结构，缓存在内存
目录项文件：存储在磁盘

访问控制系统由系统实现。

一般从 4 个级别上对文件进行安全性管理：系统级、用户级、目录级、文件级。

• 系统级：主要任务是不允许未经授权的用户进入系统，从而也防止了他人非法使用系统中的各类资源（包括文件）。系统级管理的主要措施有注册与登录
• 用户级安全管理是通过对所有用户分类和对指定用户分配访问权，不同的用户对不同文件设置不同的存取权限来实现。例如，在 UNIX 系统中将用户分为文件主、组用户和其他用户。有的系统将用户分为超级用户、系统操作员和一般用户。
• 目录级安全管理是为了保护系统中各种目录而设计的，它与用户权限无关。为了保证目录的安全，规定只有系统核心才具有写目录的权利。
• 文件级安全管理是通过系统管理员或文件属性的设置来控制用户对文件的访问。通常可设置以下几种属性：只执行、隐含、只读、读/写、共享、系统。用户对文件的访问，将由用户访问权、目录访问权及文件属性三者的权限所确定，或者说是有效权限和文件属性的交集。例如对于只读文件，尽管用户的有效权限是读/写，但都不能对只读文件进行修改、更名和删除。对于非共享文件，将禁止在同一时间内由多个用户对它们进行访问。

逻辑文件：

• 流式文件
• 非流式文件

文件的【逻辑结构】是为了方便【用户】而设计的

索引文件

索引：记录关键字值与记录的存储位置之间的对应关系；
索引文件：由基本数据与索引表两部分组成的数据文件称为索引文件；
索引文件组成：

• 逻辑文件
• 索引表
  

索引表的特点：
1、索引表是由系统自动产生的；
2、索引表中表项按关键字值有序排列；

稠密索引文件
文件的基本数据中的每一个记录在索引表中都占有一项，这样的索引文件叫稠密索引文件
非稠密索引分块文件
将文件的基本数据中记录分成若干块(块与块之间记录按关键字值有序, 块内记录是否按关键字值有序无所谓)，索引表中为每一块建立一项，这样的索引文件叫非稠密索引分块文件，如下图：
多级索引文件
当索引文件的索引本身非常庞大时，可以把索引分块，建立索引的索引，形成树形结构的多级索引。

引用

三种存取方式及适用器件

按地址访问（顺序存储、直接存储和随机存储）：我知道这个数据存在哪个地址中，现在我把这个地址给你，麻烦你帮我找出我要的数据来
按内容访问（相联存储）：我要找一个数据，数据里其中一段是“XXXXXXX”，麻烦你帮我匹配下有哪些数据包含了这一段的，给我找出来

顺序存储（磁带）
磁带只能顺序存储，只能组织成顺序文件
使用一个共享的读写装置进行存取，写入的数据以记录的形式进行组织：
如果要读取地址N+N的数据，那么也是需要从地址N开始一直累加地址寻找，直到找到地址N+N在哪里。所以存取的时间是线性的。

直接存储（磁盘存储器）
直接存储也是使用一个共享的读写装置进行数据存取，但每个数据块都拥有一个唯一的地址标识：

如果我要读取地址N+7的数据，那么直接在第三数据块的首地址N+6开始往右找地址N+7在哪里，待最后找到N+7之后再把该地址的数据读取出来交给你，如果要找地址N+5的数据，那么直接在第二数据块的首地址N+3开始往右找地址N+5。所以存取的时间是可变的，根据数据块的数量、大小实时改变的。

典型的例子是磁盘存储器。

随机存储（主存）
随机存取的每一个可寻址单元都具有自己唯一的地址和读写装置（不是共享），系统可以在相同的时间内对任意一个存储单元的数据进行访问，而与先前的访问序列无关：
如果我要读取地址N+7的数据，那么直接用地址N+7的读写装置把数据拿出来给你，如果要找地址N+5的数据，那么直接用地址N+5的读写装置把数据拿出来给你，速度真的没话说，但是速度快的同时价格也很高，所以一般容量都不会很大。
典型的例子是电脑的主存（8G/16G/32G内存条）

引用

成组分解访问磁盘次数

成组分解技术，访问x块磁盘进行修改，修改磁盘后需要写回磁盘还需要访问一次。需要访问磁盘x+1次

C语言标识符

c语言标识符：

1. 不能以数字开头
2. 严格区分大小写
3. 标识符可以为任意长度
4. 26英文字符大小写，数字，下划线，美元符号

采用共享栈的好处：节省存储空间，降低发生上溢的可能
对音频信号进行编码的脉冲调制：PCM，能够达到高保真水平，三步：抽样，量化，编码

1. 抽样：

• 对模拟信号进行周期性扫描，把时间上连续的信号变成时间上离散的信号。
• f采样频率>=2fi信号最高频率

2. 量化

• 把抽样得到的电平幅值按照一定的分级标度转换为对应的数字值，并取整数，就把连续的电平幅值转换为离散的数字量

3. 编码

• 把量化的结果转换为与之对应的二进制编码

最小帧长

链接
下面来详细讲下最小帧长的计算
首先要注意单位换算 bit （位） B（字节） word （ 字） 1 字 =2字节=16位
在冲突发生时，为了使两个站点都能及时正确接受到冲突发生的信号，要满足传输一帧的时间大于2倍的信道传输时延
所以：CSMA/CD总线网中最短帧长的计算公式为：
　　最短数据帧长(bit)/数据传输速率(Mbps)=2*(两站点间的最大距离(m)/传播速度)
信号传播时延(μs)= 两站点间的距离(m)÷信号传播速度(200m/μs)，并且：数据传输时延 (s)=数据帧长度(bit)÷数据传输速率(bps)
以一个以太网的最小帧长作为例子
冲突周期是 51.2us 传播速率是10mbp/s
min frame size=51.2 *10=512 bits=64B

以太网速度上限：最小帧长64byte，使用曼彻斯特编码，需要两个电平表示一个波特，波特率是数据率的两倍，传输效率只有一半
包括标准以太网（10Mbps），快速以太网（100Mbps）和千兆以太网（100Mbps）、10G以太网，他们都符合IEEE802.3系列标准规范。
①逻辑拓扑为总线型，物理拓扑为星型；
②使用CSMA/CD，且使用CSMA/CD就可以被称为以太网；
③采用曼彻斯特编码；
③实现无差错接收，差错帧直接丢弃，差错纠正由高层负责；
④提供无连接不可靠传输：发送方和接收方之间无“握手过程”，不对发送方的数据帧编号，接收方不向发送方进行确认；
命名规则：按速度-调制方式-传输媒介-编码体系-lane的顺序命名：

物理传输层介质

TCP/IP模型中——

数据链路层提供：无连接不可靠的服务；
网络层提供：无连接不可靠（IP）的服务；
传输层提供：无连接不可靠（UDP）和有连接可靠（TCP）的服务。

局域网&广域网考点总结

虚拟局域网（VLAN）
定义：一种将局域网内的设备划分成与物理位置无关的逻辑组技术，以软件的方式（VLAN表）实现逻辑工作组的划分与管理，这些逻辑组有某些共同的需求，每个VLAN是一个单独的广播域/不同的子网；
虚拟局域网
出现原因：传统局域网的局限，（1）缺乏流量隔离；（2）用户管理不便；（3）路由器成本较高；
实现技术：（1）基于接口的VLAN技术（常用）；（2）基于MAC地址的VLAN技术；

4.令牌环网
特点：物理拓扑为星型，逻辑拓扑为环形；
5.FDDI网
特点：物理拓扑为双环拓扑，逻辑上是环形拓扑；
6.ATM网
特点：使用比较新型的单元交换技术；

将局域网的数据链路层划分为两个子层：MAC和LLC，它们的作用如下：

广域网的通信子网主要使用分组交换技术。因特网(Internet)是世界范围内最大的广域网。
广域网:

• ppp协议：全双工链路，面向【字节】
• HDLC协议：是一个在同步网上传输数据、面向比特的数据链路层协议，数据报文可透明传输，用于实现透明传输的 “0”比特插入法 易于硬件实现。采用 全双工通信，CRX检验，对帧进行编号，传输可靠性高。
  

ppp协议的要求

引用

流水线

五段式流水线为取指IF、译码ID、执行EX、访存MEM、写回WB；
取指（IF）:取指通常能在指令cache中取指，而不在主存中取指，取出指令放在指令寄存器IR中，PC+“1”。
译码&取数（ID）:控制器中的ID对OP（IR）进行译码，然后从通用寄存器组中读出操作数放到ID段锁存器。
执行/计算地址（EX）：执行运算操作或者计算有效地址。
访存（MEM）：根据有效地址从主存中取数或运算的结果可能需要写回主存，故对主存进行读写操作（只有load/store指令访问主存），但理想中该阶段是对数据cache操作。
写回（WB）:将运算的结果写回寄存器堆。

①结构相关，又称资源相关；②数据相关；③控制相关，主要由转移指令引起。
数据旁路技术的主要思想是，不必等某条指令的执行结果送回到寄存器，再从寄存器中取出该结果，而是直接将执行结果送到其他指令所需的地方，这样可以使流水线不发生停顿。

• 结构冒险（资源冲突）可以nop、stall或资源分离，
• 数据冒险（数据冲突）可以nop、stall或旁路转发，
• 控制冒险可以nop、stall或分支预测。

进程和线程

循环队列

在入队时执行rear=(rear+1)%maxsize，且只改变rear指针；
在出队时执行 front=(front+1)%maxsize，且只改变front指针。
rear指向队尾结点的下一个空间

队头结点指向队头，队尾结点指向队尾

进程5状态

中断

异常(Exception)也称内中断，是指来自CPU执行指令内部的事件，如程序的非法操作码、地址越界、运算溢出、虚存系统的缺页及专门的陷入指令等引起的事件。异常不能被屏蔽，一旦出现，就应立即处理。

• 故障，通常是由指令执行引起的异常，如非法操作码、缺页故障、除数为0、运算溢出等
• 自陷，是一种事先安排的“异常”事件，用于在用户态下调用操作系统内核程序，如条件陷阱指令、系统调用指令
• 终止，(Abort)是指出现了使得CPU无法继续执行的硬件故障，如控制器出错、存储器校验错等。缺页中断完成后返回当前指令执行，trap、DMA传送完成后返回下一条指令执行。

中断(Interruption)也称外中断，是指来自 CPU 执行指令外部的事件，通常用于信息输入/输出,如设备发出的I/O结束中断，表示设备输入/输出处理已经完成。时钟中断，表示一个固定的时间片已到，让处理机处理计时、启动定时运行的任务等。
外中断可分为可屏蔽中断和不可屏蔽中断。可屏蔽中断是指通过INTR线发出的中断请求，通过改变屏蔽字可以实现多重中断，从而使得中断处理更加灵活。不可屏蔽中断是指通过 NMI线发出的中断请求，通常是紧急的硬件故障，如电源掉电等。此外，异常也是不能被屏蔽的。在每种中断的中断处理程序中可以设置它的中断屏蔽字，比它中断处理优先级高的中断设为0，表示不可屏蔽，比它中断处理优先级低的（包括它自身）中断设为1，表示可屏蔽。

中断优先级

中断优先级分为响应优先级和处理优先级，响应优先级由硬件排队器（或中断查询程序）决定，处理优先级由屏蔽字决定，而非请求的先后次序决定

响应优先级是对于多个中断同时到达时讨论的，中断屏蔽字影响的情况是已经在执行一个中断了，这时候又一个中断来了。也就是嵌套中断
响应优先级，硬件得出的不用管怎么来的，用于在中断同时到达时确定该响应谁
处理优先级，当两个中断处理时间冲突时，用屏蔽字来确定谁优先
总结：按照常理来说谁先来就是谁响应，但是当中断同时来的时候不知道该响应谁了，所以就需要硬件电路的排队顺序（响应优先级）来决定响应顺序。处理就按屏蔽字就行了。

王道模拟卷里面的一道题，我说一下最后，他是把ABD按照一定顺序完成之后不能马上执行b，因为即使是最后执行的d的屏蔽字也屏蔽了b，因此不可以直接转b，但他们都没有提到同时到达的响应问题，这个也值得注意一下从高服务优先级执行结束跳转低服务优先级时，需要考虑高服务优先级是否抢占了其他低优先级的，抢占谁，回到谁，如果没有抢占任何低服务优先级且后面还有一个低服务优先级等着上处理机的，要先回到普通程序再切换

不同响应优先级的中断同时请求，会优先处理高响应优先级的中断，在中断服务程序开中断之后，如果有新的中断请求，才会进行中断响应，挑选处理优先级最高的中断进行响应，如果在开中断后没有新中断请求到来，即使在开始时刻同时到达的中断中有处理优先级更高的中断也不会响应
中断响应的三个条件 1，开中断 2，至少一个未被屏蔽的中断请求 3，指令执行完

【在中断同时到达的情况下】
1.响应次序=中断判优电路得出的一个新的响应优先级次序
2.屏蔽字技术影响中断服务（子）程序执行完的顺序
【在中断先后到达并且下一个中断到达时上一个中断已经结束了的情况下】
响应次序=到达次序

1234同时请求，处理优先级是3142，响应优先级是1234，那么此时先响应1，然后1响应完要进入处理阶段的时候屏蔽字起作用，发现已经到达的中断3比目前1的优先级要高，所以会直接截断1，转而执行3。后面以此类推。

这两道题都是王道的题目，P1是不同优先级中断不同时到达的情况，P2是不同优先级中断同时到达的情况，他们响应的顺序在中断同时到达的情况下由硬件判优电路决定（与处理优先级无关），如果先后到达那么响应顺序就按先后次序排序，响应后进行服务程序的处理时两种情况都会根据屏蔽字判断处理优先级。

上述题目和解答参考
beokkayy_

讨论中断时，该不该考虑不可屏蔽中断

CPU收到有效的NMI必须进行响应，它在被响应时无中断响应周期

参考bok视频

多级中断过程如下：关中断→保存断点→形成中断服务程序入口地址（以上由硬件/中断隐指令完成）→（以下由中断服务程序完成）保护现场与屏蔽字→开中断→执行中断服务程序→关中断→恢复现场和屏蔽字→中断返回

中断隐指令包括：关中断，保存断点，形成中断向量地址。
中断隐指令是由CPU中的硬件完成。
中断隐指令叫中断隐指令的原因是，由系统自动完成，在这个过程中，不需要操作系统的参与。
1. 关中断：CPU响应中断后，输出中断响应信号，自动将状态标志寄存器FR或EFR的内容压入堆栈保护起来，然后将FR或EFR中的中断标志位IF与陷阱标志位TF清零，从而自动关闭外部硬件中断。因为CPU刚进入中断时要保护现场，主要涉及堆栈操作，此时不能再响应中断，否则将造成系统混乱
2. 保存断点：保护断点就是将CS和IP/EIP的当前内容压入堆栈保存，以便中断处理完毕后能返回被中断的原程序继续执行，这一过程也是由CPU自动完成。
3. 中断源识别当系统中有多个中断源时，一旦有中断请求，CPU必须确定是哪一个中断源提出的中断请求，并由中断控制器给出中断服务子程序的入口地址，装入【CS与IP/EIP】两个寄存器。CPU转入相应的中断服务子程序开始执行。
参考

注意（存疑）：需要保存的数据是会被更改且不可恢复的，TLB、Cache等虽然会被修改但是可以恢复，不会被修改的寄存器虽然不可恢复但是不会被修改，故无需保存。
表格中的12条可进行合并

I/O接口的基本结构

如图所示是一个I/O接口的通用结构，I/O 接口在主机侧通过IO总线与内存、CPU 相连。

I/O【接口】可以分为：

1. 数据缓冲寄存器【端口，编址方式有两种】：用来暂存与CPU或内存之间传送的数据信息；
2. 状态寄存器：用来记录接口和设备的状态信息；
3. 控制寄存器：用来保存 CPU 对外设的控制信息；
4. 数据线：传送的是读/写数据、状态信息、控制信息和中断类型号；
5. 地址线：传送的是要访问I/O接口中的寄存器的地址；
6. 控制线：传送的是读/写控制信号，以确认是读寄存器还是写寄存器，还会传送中断请求和响应信号、仲裁信号和握手信号；
7. I/O 控制逻辑：能对控制寄存器中的命令字进行译码，并将译码得到的控制信号通过外设界面控制逻辑送到外设，同时将数据缓冲寄存器的数据发送到外设或从外设接收数据到数据缓冲寄存器，还要具有收集外设状态到状态寄存器的功能；

需要注意的

1. 状态寄存器和控制寄存器在传送方向上是相反的，在访问时间上也是错开的；
2. 对数据缓冲寄存器、状态/控制寄存器的访问操作是通过相应的指令来完成的，通常称这类指令为I/O指令，I/O 指令只能在操作系统内核的底层I/O 软件中使用，它们是一种特权指令；
3. 端口和接口是两个不同的概念，【端口】是指接口电路中可以进行读/写的【寄存器】。I/O 端口是指I/O接口电路中可被 CPU直接访问的寄存器，主要有数据端口、状态端口和控制端口。通常，CPU 能够对数据端口中的数据进行读/写操作；但对状态端口中的外设状态只能进行读操作，对控制端口中的各种控制命令只能进行写操作。
4. I/O端口要想能够被 CPU访问，就必须要对各个端口进行编址，每个端口对应一个端口地址。而对I/O端口的编址方式有与存储器独立编址和统一编址两种。

死锁

死锁：是指多个进程因竞争资源而造成的一种僵局(互相等待对方手里的资源),使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。

饥饿：由于分配策略的不合理导致进程长时间等待，并给进程的推进带来了很大影响；

主要差别：
①发生饥饿的进程可以只有一个；而死锁是因循环等待对方手里的资源而导致的，因此，如果有死锁现象，那么发生死锁的进程必然大于或等于两个。
②发生饥饿的进程可能处于【就绪态】(长期得不到 CPU,如 SJF 算法的问题)，也可能处于【阻塞态】(如长期得不到所需的I/O 设备，如上述举例)；而发生死锁的进程必定处于阻塞态。

死锁产生的必要条件
1)互斥条件。进程要求对所分配的资源(如打印机)进行排他性使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。

2)不可剥夺条件。进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放(只能是主动释放)。

3)请求并保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

4)循环等待条件。存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

死锁计算

根据死锁公式，当资源数量大于各个进程所需资源数-1的总和时，不会发生死锁，因此对于计算发生死锁最小进程数类题目，设总资源数为N，每个进程需要资源数为n，则最小进程数k等于：

预防死锁和避免死锁都属于事先预防策略，
预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；
避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

（一）死锁预防
只需破坏死锁产生的4个必要条件之一即可，其中之一的“破坏循环等待条件”，一般采用顺序资源分配法，即限制了用户申请资源的顺序。

1. 破坏互斥条件：使资源可以【共享】；
2. 破坏不可剥夺条件：当一个已经保持了某些不可剥夺资源的进程，请求新的资源而【得不到满足】时，它必须【释放已经保持的所有资源】，待以后需要时再重新申请。
3. 破坏请求保持条件：采用【预先静态分配方法】，即进程在运行前【一次申请完】它所需要的全部资源；或者允许进程只获得运行初期所需的资源后，便可开始运行。进程在运行过程中再逐步释放已分配给自己且已使用完毕的全部资源后，才能请求新的资源。
4. 破坏循环等待条件：采用【顺序资源分配法】。首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源(编号相同的资源)一次申请完。也就是说，一个进程只在已经占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能再逆向申请小编号的资源，因此不会产生循环等待的现象。
   （二）死锁避免
   银行家算法用于避免死锁，其思路为：当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。
   

（三）死锁检测与解除
可用资源分配图来检测系统所处的状态是否为死锁状态。用圆圈表示一个进程，用框表示一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆表示一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。

总的来说，死锁检测的思想是：能分配尽分配，检查是否有环。

解除方法有三：（1）资源剥夺；（2）撤销进程；（3）进程回退

指令字长和性能指标

一、字长类
指令字长：即一条指令的长度，常常是一到多倍的存储字长；例如半字长指令、单字长指令、双字长指令等；在做题中常用来计算PC+“1”的实际意义、指令中部分的位数等。
存储字长：即主存中存储单元的长度，常常是一到多倍的字节长度；例如按字节编址、按字编址等；在做题中常用来计算页内地址位数等。
机器字长：即CPU一次操作的位数；例如32位、64位。
地址位数：由逻辑地址空间决定；在做题中常考地址位数的计算。
二、性能指标类
CPI：每条指令需要的时钟周期数，用于计算CPU执行时间；
主频：CPU每秒包含的时钟周期数，用于计算CPU执行时间；
指令条数：完成某项作业时程序中包含的指令条数，用于计算CPU执行时间；
指令访存次数：每条指令需要的访存次数，用于计算总访存次数；

TCP协议差错检测、可靠传输和流量控制

一、差错检测

伪首部校验：

TCP校验和UDP校验和和IP校验和

TCP校验和

TCP首部校验和计算三部分：TCP首部+TCP数据+TCP伪首部。

发送端：

1. 首先，把伪首部、TCP报头、TCP数据分为16位的字，如果总长度为奇数个字节，则在最后增添一个位都为0的字节。
2. 把TCP报头中的校验和字段置为0。（否则就陷入鸡生蛋还是蛋生鸡的问题）。
3. 其次，用反码相加法（对每16bit进行二进制反码求和）累加所有的16位字（进位也要累加，进位则将高位叠加到低位）。
4. 最后，将上述结果作为TCP的校验和，存在检验和字段中。

接收端：
同样利用反码求和，高位叠加到低位， 如计算结果的16位中每一位都为1，则正确，否则说明发生错误。

验证示例：
EXP1:
校验和 反码求和过程
以4bit 为例
发送端计算：

    数据：   1000  0100   校验和  0000则反码：0111  1011               1111叠加：   0111+1011+1111 = 0010 0001   高于4bit的， 叠加到低4位      0001 + 0010 = 0011 即为校验和接收端计算：数据：  1000   0100   检验和  0011反码：  0111   1011                1100叠加：  0111 + 1011 +1100 = 0001 1110  叠加为4bit为1111.   全为1，则正确

EXP2:

1、首先将检验和置零；
2、然后将TCP伪首部部分，TCP首部部分，数据部分都划分成16位的一个个16进制数
3、将这些数逐个相加，记得溢出的部分加到最低位上，这是循环加法：
0xc0a8+ 0x0166+……+0x0402=0x9b49
4、最后将得到的结果取反，则可以得到检验和位0x64b6
发送方：原码相加 ，并将高位叠加到低位，取反 ，得到反码求和结果，放入校验和
接收方：将所有原码 相加，高位叠加， 如全为1，则正确

UDP检验和

    基本过程和TCP检验和相同，不同的是UDP的伪首部中8位传输层协议号是17而TCP是6。

IP检验和

    IP首部中的检验和只覆盖IP的首部，不覆盖IP数据报中的任何数据

三者检验和的异同

    TCP和UDP检验和是一个端到端的检验和，由发送端计算，然后由接收端验证。TCP和UDP检验和覆盖首部和数据，而IP首部中的检验和只覆盖IP的首部，不覆盖IP数据报中的任何数据。TCP的检验和是[必需的]，而UDP的检验和是[可选的]。TCP和UDP计算检验和时，都要加上一个12字节的伪首部。

伪首部共有12字节（前96Bits），包含如下信息：源IP地址、目的IP地址、保留字节(置0)、传输层协议号(TCP是6)、TCP报文长度(报头+数据)。
伪首部是为了增加TCP校验和的检错能力：如检查TCP报文是否收错了(目的IP地址)、传输层协议是否选对了(传输层协议号)等。

TCP可靠传输

保证接收方进程从缓存区读出的字节流与发送方发出的字节流是完全一致的。
实现机制：
①校验：伪首部；
②序号：seq；
③确认：ACK，采用累计确认；
④重传：分为超时重传和快速重传，
（1）超时重传：RTT，TCP采用自适应算法确定重传时间RTT；
（2）快速重传：冗余ACK，指明下一个期待字节的序号，若发送方收到三个对于某个报文段的冗余ACK，则重传该报文段；

三、流量控制

滑动窗口机制：在通信过程中，接收方根据自己接收缓存的大小，动态地调整接收窗口rwnd (接收方设置确认报文段的窗口字段来将rwnd通知给发送方)，发送方的发送窗口取接收窗口rwnd和拥塞窗口cwnd的最小值。

三种交换方式

参考

一、电路交换
概念：面向连接，在通信双方之间建立一条物理连接，通过这条连接进行数据传输。在建立电路之前，通信双方需要进行握手协商，以确定通信参数和建立连接。一旦建立了电路，通信双方就可以通过这条连接进行数据传输，直到通信结束，然后释放电路。

使用方法：

• 握手协商：通信双方需要进行【握手协商】，以确定通信参数和建立连接。
• 建立电路：一旦握手协商成功，通信双方就可以建立电路，通过这条连接进行数据传输。
• 释放电路：通信结束后，通信双方需要释放电路，以便其他通信双方可以使用这条连接。

特点：电路交换技术可以保证通信的可靠性和实时性，但需要占用一定的带宽和资源。

适用范围：适用于需要实时传输大量数据的场景，如电话通信、视频会议等。

优缺点：

二、报文交换
概念：无需连接，将整个数据报文作为一个整体进行传输，数据报文在传输过程中不会被分割成小的单位。在报文交换中，发送方将整个数据报文发送到接收方，接收方在接收到完整的数据报文后才能进行处理。

使用方法：

• 封装报文：发送方将整个数据报文封装成一个整体。
• 传输报文：发送方将封装好的数据报文发送到接收方。
• 接收报文：接收方接收到完整的数据报文后，进行处理。

特点：传输效率高，但是对网络资源的利用不够灵活，容易出现网络拥塞和资源浪费的问题。

适用范围：适用于【数据量较小】、传输速度不是很关键的场景，如电子邮件、文件传输等。

三、分组交换

概念：无需连接，将数据分割成固定大小的数据包进行传输，每个数据包包含有关该数据块的信息，如源地址、目的地址、序列号、校验和等。在分组交换中，数据包通过网络传输到目的地，每个数据包独立地进行存储-转发，因此可以通过不同的路径到达目的地。在到达目的地后，数据包会被重新组装成原始数据。

使用方法：

• 分割数据：发送方将数据分割成固定大小的数据包。
• 封装数据包：每个数据包包含有关该数据块的信息，如源地址、目的地址、序列号、校验和等。
• 传输数据包：发送方将封装好的数据包发送到接收方。
• 路由选择和转发：每个数据包独立地进行路由选择和转发，可以通过不同的路径到达目的地。
  重新组装数据：在到达目的地后，数据包会被重新组装成原始数据。

特点：灵活性和高效性，可以更好地利用网络资源，但也可能会出现数据包丢失、延迟等问题。

适用范围：适用于数据量较大、传输速度较快、【对实时性要求不是很高】的场景，如互联网、局域网等。

优缺点：
总时延=传输时延（发送时延）+传播时延+排队时延+处理时延，通常只需要计算传输时延+传播时延。

（一）数据报：半双工，无连接
① 无连接 : 发送前不确定传输路径 , 每个分组传输路径都是独立的 , 不同的分组的传输路径可能不同 ;
② 携带地址 : 每个分组都有目的地址和源地址 ;
③ 转发分组 : 路由器根据目的地址 , 转发分组；
④独立选路：每个分组选择传输路径都是独立的

（二）虚电路：全双工，逻辑连接
① 建立虚电路 : 在源主机和目的主机之间 , 建立一条逻辑连接 , 路径上的节点 ( 路由器 ) 都需要维护一张虚电路表 , 其中记录了虚电路信息；每个分组都有虚电路号信息 , 不携带目的地址；源主机向目的主机发出呼叫请求分组 , 目的主机回送呼叫应答分组 ，虚电路 ( 逻辑连接 ) 建立成功 ;
② 数据传输 : 该通信是全双工通信 ;
③ 释放虚电路 : 分组发送完毕后 , 源主机发送释放请求分组 , 释放虚电路 ;

注意一下在Cache中：

块： Cache和主存之间交换数据的最小单位是一个物理块（=页框=页帧=内存块=物理页面）；

行： 行是Cache的存储单位，存储块（拿到的数据）以及标记项，见下：

组： 组是一个或多个行的集合。在直接映射中一组由一行组成，组相联映射中一组由多行组成；

因为一行总是存储一块，因此 “行” 和 “块” 通常互换使用，但二者概念是不同的。

命中率与访问时间
CPU欲访问的信息已在 Cache 中的比率称为 Cache 的命中率。设一个程序执行期间，Cache的总命中次数为$N_c$,访问主存的总次数为$N_m$,则命中率H为：$H=N_c/(N_c+N_m)$，缺失率则为1-H。

可见为提高访问效率，命中率H越接近1越好。设$t_c$为命中时的Cache 访问时间，$t_m$为未命中时的访问时间，1-H表示未命中率，则Cache-主存系统的 平均访问时间$T_a$为：$T_a=H{t}_c+(1-H)t_m$

时空局部性
时间局部性是指在最近的未来要用到的信息，很可能是现在正在使用的信息。比如程序中的循环；空间局部性是指在最近的未来要用到的信息，很可能与现在正在使用的信息在存储空间上是连续的，因为指令通常是顺序存放，顺序执行的，数据通常也是以向量、数组等形式簇聚在一起。

高速缓冲技术便是利用的程序局部性原理，将程序正在使用的数据放到一个高速的、容量较小的Cache中，从而使CPU的访存操作大多对Cache进行，因而提高了程序的执行速度。因此在计算Cache的命中率时，常常涉及到时间局部性与空间局部性。此类题目要观察程序中对数据的访问方法（往往是对数组），看一个Cache块在不置换的情况下被访问多少次，倘若每次被置换进来只能被访问一次，则缺失率为100%。

⭐ 计算行优先/列优先存储的二维数组进行行优先/列优先访问时的命中率：

（1）倘若是行优先存储，则同行数组元素连续存储在一个Cache块(主存块)中，因此行优先访问可以利用空间局部性访问，减少Cache置换次数，提高Cache命中率，此时只有调入Cache块的第一个数组元素缺失，其他均命中，命中率 H=1/n，其中一个Cache块中存储n个数组元素。

（2）而如果是列优先访问，则需要不断置换Cache块，Cache命中率降低，此时的命中率计算要注意一个Cache块被调入后可以访问几次后再置换出去，命中率 H=1/t，其中t指Cache块每次被置换进来可以访问t次。

（3）注意读取、赋值各算一次访问，例如语句“a[k]=a[k]+32”，首先读取a[k]需要访问一次a[k]，之后将结果赋值给a[k]需要访问一次，共访问两次。

上述资料参考
@啊哈哈哈哈哈韩

OS文件管理

文件的物理结构

• 连续分配
• 链接分配
  • 隐式链接 只能一个一个访问，不能随机访问
  • 显示链接 显示存在于分配表中，FAT（文件分配表），整个磁盘仅仅只有一个，FAT可以实现随机访问，表的序号是物理盘块号，可以进行空闲区间的管理，每个表项存放链接指针（下一个盘块号）
• 索引分配

一个扇区称为一个盘块（或数据块）
⭐从考试角度看是一样大小的

索引分配

文件物理结构优缺点对比

open目录项复制到打开文件表中
第一次调用open才会创建打开文件表表项



inode访问计数

目录和FCB的关系

看到inode反应到文件使用的是索引分配

根据inode地址项类型和个数计算最大文件大小

索引结点总数决定了文件

参考beokayy_

外存管理

1. 空闲表法 连续分配方式
2. 空闲链表法 将空闲盘区拉成一条空闲链
   • 根据链条元素
     • 空闲盘块链
     • 空闲盘区链
3. 位示图法 利用二进制的0表示盘块空闲，1表示盘块已分配，这样所有盘块对应的比特构成一个集合，叫做位示图
4. 成组链接法
   • 空闲盘块号栈中存放了本栈中空闲盘块的数量
   • 栈底记录的是下一个这样的一组数据所在的盘块号
   • 栈底如果是0，就是空闲盘块链的结束标志
   • 栈中除了栈底记录的是空闲盘块号栈，其他记录的都是空闲的盘块
   • 栈是临界资源，需要互斥访问
   • 分配盘块时，从栈顶取出空闲盘块号分给用户，然后栈顶指针向下移动一位，记录空闲盘块的数量减一，若已经到了栈底，就把记录的下一个空闲盘块号栈所在的块调入内存，并把原栈底对应的盘块分配出去。
5. FAT也可以进行空闲块的管理
   
   
   这里的栈涉及到PV信号量的问题

复制300盘块到内存

成组链接法是将连续分配和离散分配相结合的方法，也能方便找到连续的空闲块

目录

• FCB和文件一一对应
• 索引节点inode
  • 磁盘索引节点
  • 内存索引节点
    

FCB优化查找，FCB表项分为文件名和inode指针（放在磁盘）

索引分配，混合索引

文件共享