admin 管理员组

文章数量: 887007

学习方法：重复复习！！知识点配上问题自己提问！不要跳一点点过！不断精简自己写的过程！！！不要重复抄写书上的知识点，要带有自己的理解记忆。学习最忌讳重复抄书本上的知识，没用！浪费时间低效率！！！但是对于过程知识点，每次其实都是重新来，效率低。应该画一幅图，过程都写在图上！每次精简，这样就有一个标准，不至于每次都是从头开始回顾也不知道到底缺了哪里！题目要反复看

这个重复复习要的不是看的次数，而是合上书在脑子里复习的次数！也叫输出，很难很累但是效果效率最高！一开始都很难但是次数多了就能形成条件反射！低效率的复习都不如一次次时间长的高效率！

小知识碎碎 

计组

熟读并背诵流程

从主存取指令，读指令进行译码，计算下一条指令的地址，取操作数并执行，将结果送回存储器。

存储系统：TLB-cache-页表

指令系统：栈，指令数据寻址，定长指令扩展操作码，精简和复杂指令集

CPU：中断周期流程

数据表示与运算

重点：无符号整数加减乘及溢出判断；带符号整数补码加减乘及溢出判断；IEE754标准-浮点数加减步骤

回忆：进制之间的转换，原反补移转换？无符号加减法（溢出），乘法除法咋算？浮点数的精度丢失问题？

原反补移

补码加减运算器功能咋实现的比较重要

原反补码移位：
逻辑移位（无符号）
算术移位（有符号：原码只补0，反码只补符号位，补码左移补0右移补符号位：原0反符，左0补右符）
循环移位（CF）

进制之间的转换，2Binary 8Octal 10Decimal 16Hexadecimal。2到816 是因为有位数刚好能表示，但是到10就是因为没有一个完整的位能表示就只能一点点加。 10 ->2 8 16之间都靠除基取余法，乘基取整法来转换！理解一下除基取余，32d->100000b  0.25D-> 0.01b（0.3d得不到二进制）

有（无）符号数加法：保持位数相同，按无符号数的方式直接相加。有符号数高位需补充符号位
无符号8(1000)和 －3(1101)相加，结果为(1)0101，高位溢出，但有效位表示的值为5
无符号F0000000H + 有符号FF12H，FF12H补全后为FFFFFF12H，相加得到EFFFFF12H

补码最小值1000 0000=-128可以这么理解别的都可以按照特殊方法化成原码就-128不行所以为最小值

IEEE754

IEEE754 浮点数：简读+案例=秒懂-CSDN博客

首先要明白移码是：移码=真值+偏移值！这里的偏移值跟之前规定的原反补移码的移码不一样！这里的对于float偏移值就是127。double就是1023。规定阶码用移码表示！尾数用原码表示

同样的位数，浮点数的个数并不比定点数多，只是范围变大了，在数轴上不等距分布；

IEEE754的规格化是：1.XXXXX这里的1是数值位！这个尾数第一个1是不存储的！真值写成浮点数形式要把第一个1舍去！还原的时候再加上！单独搞了一位最开始表示数符。

对于浮点数的规格化，要知道正数浮点数范围是[1/2  1-2^(-n)]。负数的是[-（1-2^(-n)）-1/2  ]，因为有阶码不允许出现正数小于0.5的，负数大于0.5的，如果出现都可以化成标准值的     +1/4d=0.01b；补码规格化的负数是1.0是因为也要满足小于-1/2

规格化的原码尾数，最⾼数值位⼀定是1
规格化的补码尾数，符号位与最⾼数值位⼀定相反

这个负数补码的范围是负数原码的范围往下降了2^(-n)，其实跟八位整数运算规则很像！
负数补码最大值1.01xxxx1换成原码负数就是1.1000xxxx1=-（1/2+2^（-n））


尾数必须是1.xxx这种形式的。

浮点数加减法：对阶，尾数和，规格化，舍入，溢出判断。
这个小阶像大阶看齐，不可能会有1xxx.xxx+1.xxx这种情况对阶。必须只能1.xxx+1.xxx这种形式后。然后小阶向大阶看齐。
为什么右规只需要一次，左规要多次，因为能右规也只能是两个数相加，而相加按照二进制来算再怎么加也只能1.xxx加或减1.xxx。这样结果为两种1x.xxx  0.00001xxx前者需要右规，后者需要左规。

舍入，是尾数的长度超过可以表示的23 52 64 （8 11 15）的范围了，要舍入。零舍1入，入1可能会导致1.1111 1111 1变成10.0000 0000 这样要右规，阶码变大会可能上溢。左规可能阶码下溢，右规有可能阶码上溢

浮点数的加减法运算过程详解（面向小白的）_浮点数加减法-CSDN博客

127=7FH 1023=3FFH。因为阶码的规定范围1-254且规定偏移值127
规定，阶码最低-126，-1022，最高127或1023。对应。最低1，254，2046
正数上溢（超出127，1023）负数下溢（超出-126，-1022）
上限最大值1111 1110=254-127=127。上溢出1111 1111 =255-127=128
下限最小值0000 0001 =1-127=-126。下溢出0000 0000=0-127=-127下溢出

注意双符号位的要求可能阶码跟尾数要补码表示，见到
10.xx要右规→11.0xx
01.xxx要右规→00.1xxx
而
00.01xx要左规，00.1xxx
11.10xxx要左规，11.0xxx
核心也就是科学记数法。
IEEE754用的舍入方法是零舍一入方法

溢出

单符号位
两同号相加（正+正=负 负+负=正） 表明有溢出
两异号相减，如果结果的符号与被减数的符号相反，则表明有溢出（正-负=负 负-正=正）

双符号位
用“00”表示正数，“11”表示负数，符号位第一位叫第一符号位，第二位称为第二符号位，两个符号位同时参加运算。
如果运算结果两符号位相同，则没有溢出发生。
如果运算结果两符号位不同，则表明产生了溢出。
10 负溢出说明运算结果为负数

01 正溢出说明运算结果为正数

进位值
两补码数进行加减运算时

若最高数值位产生向符号的进位而符号位不产生进位时，发生正溢出

若最高数值位无进位而符号位有进位时，发生负溢出

双符号位负溢出双符号位正溢出进位值负溢出进位值正溢出
  11 000 0001=-127   00 111 1111=127  1 000 0001=-127   0 111 1111=127
+11 111 1100=-4+ 00 000 0100=4+1 111 1100=-4+ 0 000 0100=4
1 10 111 1101 0 01 000 0011 10 111 1101  01 000 0011

⽆符号数减法关注 CF、ZF（只需注意A-B够不够减。够减，cf=0）有符号数减法关注 OF、SF、ZF

OF溢出位
SF最高位，计算的结果的最高位负为1
ZF是否为零，都有意义
CF借位进位，只对有符号位   加法时CF表示进位；减法时CF表示借位 

求A+B时， 进位输出为1则CF为1，进位输出为0则CF为0；求A-B时， 进位输出为1则CF为0，进位输出为0则CF为1。

1111 +00011100 +00011111-0001=1111+11110001-1000=0001+1000
1 0000   0 1101  1 1110  0 1001 
加法，
有进位
CF=1		加法，
无进位
CF=0		减法，
无借位
CF=0		减法，
有借位
CF=1

存储系统:TLB-cache([不]命中策略/替换策略)-页表；三种刷新；低位交叉(流水线)；字位扩展

TLB-页表（一二级）-cache：TLB（缺页 映射方式）；页表（表项、内容大小、脏位、有效位、缺页、一二级、未命中要写入）；cache（映射方式、大小、一行几bit、置换方法、未命中、脏位、有效位、）


平均每条指令访存n次；Cache命中率为H;
假设使用页式虚拟存储器，在Cache缺失的情况下访问主存时缺页率为m。（注意，要是没说cache的事情的话就直接×缺页率）
平均每条指令访问Cache次数为n×H;
平均每条指令访问主存次数为n×(1-H);
平均每条指令访存缺页次数为n×(1-H)×m。

连续编址时 CPU 地址线的高位作为片选信号，低位表示模块内/体内地址，地址在模块内连续， CPU串行访问存储模块，但 DMA 可同时访问其它的模块；交叉编址则以低位作为片选信号，高位表示模块内地址，多采用轮流启动方式， 存取速度提高 n 倍，提高了带宽；

cache分块太小不能充分利用空间局部性； 若分块太大，Cache行数减小，导致缺失率增加（一个找不到这个大的cache块就要换出去），都会降低性能；

TLB不分多级，页表分；页表未命中（缺页），外存调入内存的时候，该页表的页表项会被修改（有效位为1），同时TLB的表项内容也会被修改。这也引入了缺页异常是内中断，当调页后不缺页了，需要重新执行该条指令！这个时候TLB命中就不需要查慢表了！（回顾：遇到陷阱是执行下一条指令！故障是重新执行当前指令？终止是当前或者下一条？）同时注意，页面调入os会给某个进程限制用几个页框！所以会涉及页框置换算法（FIFO LRU）这就要页表项有一个置换位！同时置换要看当前页是否被修改（修改就要写回外存不修改就直接覆盖）。cache也如此，物理地址没命中就会把这个内存块的内容调入cache，替换里面有效位为0的cache块！或者都有效的话，按照替换策略替换掉。cache不是这样的，是有回写全写写分配非写分配的策略的，跟TLB页表不一样！！！

程序启动，数据指令从外存【磁盘】调到主存，os会给这个进程建立完整的虚拟空间，由内核区该进程的页表管理这个虚拟地址到物理地址的映射关系！两个过程需要这个转换（1.取指令） IR PC把指令送到MMU MMU查TLB 命中直接把物理块号+块内地址给MAR，同时注意cpu如何知道页表在内存地址？是因MMU内部有页表始址寄存器（存放有页表始址）未命中TLB MMU就把页表始址以及VA送到内存，找到页表拿到物理地址，通过MDA送到IR出，同时把内容复制到MMU里的TLB。这时PA得到了，IR把PA送到MMU里的MAR给内存取到真正要的数据或者指令！ 页表始址寄存器的内容以及IR PC的内容，都是os在调度进程（都有PCB）的时候把PCB里的页表始址以及一些必要寄存器内容（PC PSW、、、）调入到CPU的寄存器里！在进程调度的时候会保存上下文！！！ MMU里有TLB 页表始址寄存器（都是硬件所以很快）

比较器 给的VA跟TLB的页号比较，用比较器 比如24位页号比较，比较器的设置可以设置为24个异或门，只有当每位都相等所有的结果就都是0，再让所有的结果取反，然后相与，得到的结果1就代表对比上了，然后让这个1与有效位相与，结果为1说明页号对，在TLB，这个时候一个三态门直接连到MAR的底12位，就把TLB物理地址送到MAR了！

TLB命中不可能缺页，如果OS要置换页，且该页的物理地址在TLB里，OS会把该页表项也从TLB删除！而页表项可能缺页！ 内存块根cache块一样的大小！直接映射本质一路组相连

静态分析：1.分析cache地址结构 2.分析cache行完整（有效位 脏位 Tag标记 数据块 替换块）

动态分析：直接给出PA地址 、给的是数组、给的是机器代码形式。然后问cache命中率 cache的替换

见到cache想   PA（物理）多少位？cache多少行？行有哪些必要的信息？cache大小多少？采用什么方式映射？搭配的什么写策略？马上写还是待会写？cache行的替换算法是什么？

32bit物理地址，字节编址，物理块64B，cache块也是，块内地址8bit cache总大小？ 假如8cache行，每行包含 （行号/组号）Tag标记 脏位 有效位 替换信息位 块内数据。直接映射无替换信息位，全相连log2行数 bit 组相连log2组数 bit 同时数据调入cache要更新什么信息？

见到TLB想 VA多少位？页内地址多少位？什么映射方式？替换的算法是什么？每行包含的信息是什么？

cache总容量不等于cache数据副本的容量。cache一读就是把一整个内存块读进来！！！！占满64Bcache数据副本

TLB抖动 cache为什么没有抖动？ 替换控制位知道的是组相连，能够分清替换哪一个！那要是直接映射如何替换呢（跟组相连一样？）？

cache回写有脏位。

cache行的位数＝cache行标记项位数（有效位（1bit） 标记位【tag】 脏位（1bit） 替换控制位）＋cache块位数

cache总容量=cache行数×cache行的位数


全相联，就是只有标记+页内偏移36=24 12
组相联，就是标记（小标记+组号）+页内偏移，64个tlb行，分4路组相联。36= 20 4 12
直接映射，假如64个tlb行，36=18 6 12

可以想虚拟36，物理32。片内偏移12位，一个cache块64B，字节编址。
cache跟的是物理地址32位，cache块内偏移6位
全相联映射只需要前26位
直接映射：要看有多少cache块（行）16行的话22+4+6。低六位是一个块里可以放的内容，中间4位是直接映射嘛哪一块映射到对应cache这是定死的，比如某一块的中间四位就是这个高22位来回换，只要你中间四位是这个0001这种，你就只能站这个cache行别的行都不能用。先找cache行，看配不配再找cache标记22看对不对，也就是说只能是对应cache行后标记也对的才能占连续的64B的内容，下一个64B的内容一定中间4位就变化了。也就是说但凡中间跟高22都匹配且有效位1，那个数据必在cache
组相联：中间的换成组号，组内随机，（标记+组号+字块内地址）组号的位数跟有多少组有关。

（2021）若计算机主存地址为32位，按字节编址，cache数据区大小为32KB，主存块大小为32B，采用直接映射方式和回写（Write back）策略，则cache行的位数至少是：1脏+17tag+1有效+32*8=275bit

DRAM刷新+地址复用

现在DRAM行列地址线是复用的！

刷新的实质：先将原信息读出，再由刷新放大器形成原信息重新写入的再生成的过程。因此刷新一行的时间是等于存取周期的。因为刷新的过程与一次存取相同，只是没有在总线上输入输出。

分散刷新无死区，根本在于把刷新时间加到存储周期里去了。异步刷新的死时间缩短为0.5μs，是刷新一行！而同步刷新是一整段死时间0.5μs*128（理解：死时间，这段时间不能读取，异步就0.5μs 尽管还有127个0.5μs。但是这是间断的不构成一整段死时间。还可以理解成对于每行的死时间，同步对于每行死时间64μs，异步是0.5μs 分散没有）

数据-指令流水线

指令流水线：加速比，吞吐率，装入时间排空时间，效率

数据流水线-低位多体m>T/t

为何有多体并行存储器，因内存是DRAM取完数据后要刷新，要时间但不能让CPU等。
T存取一个字的存取周期，t总线传送周期（每经过t启动一个模块）
连续存取m个字时间=T+（m-1）t

低位：【r(cpu发读写信号)+T（存储体把数据读出来之后发给cpu的时间）】当存储体M0在进行准备数据的过程中，过了时间r后便会读取M1存储体，以此类推。但是M0读完在总线传输时间T-r，这段时间在T-2r的时刻第二个模块读完也要占用总线，但此时第一个总线还没用完。低位多体是多条路径，但cpu发读命令的r是不可能并行的！【遗留：速速想出m>T/t m<T/t的样子】

咋样写

要CPU写数据！回写法与写分配条件下是：命中cache等到要换cache再写内存，不命中就把数据调入cache后再写cache。搭配的原因是，局部性原理，一个数据块被调入cache后很可能下一次还会访问这个内存。这样不管如何修改都不会重复回写到主存！！全写法和非写分配，就是如果命中就把cache和主存都写上！不命中cache，就直接修改内存，省了还要把数据写回cache这一步！因为写回去没意义，执行的是全写法，下一次命中cache后内存的也要改，何必调进去！

指令：地址码 扩展操作码 CISC RISC 10+2（指令）

流水线核心就是五个阶段（取数，译码，执行，访存，回写）在执行完取数之后，后续的操作交给CPU做，之后再执行取数，一直不停！（按照低位交叉编制，第一个内存块使用过后隔着m个r次后再次使用第一个内存块，依旧可以使用而不是第一个内存块的指令周期还没执行完毕）

寻址方式

数据来自三个地方（立即数 寄存器 内存）把十种寻址方式也分为三类！而指令只可能在主存里（不可能在寄存器也不可能立即数存的是指令）

跳跃寻址，本条指令的下一条指令的地址不由PC自动给出，而是通过本条指令（跳跃寻址）计算后的结果给PC，然后再由PC给出（不是PC无脑+“1”）

隐式寻址，形式地址给的不是地址而是一个“参数”。这个参数的位置是根据上下文来看的，直接寻址给的就是真内存地址。比如return指令，没有操作数。地址由硬件规定去内存堆栈区栈顶找到返回的地址

相对寻址：是该条指令已经取到后，PC已经+1了。之后知道本次运行指令是相对寻址，然后再在PC+1基础上加上偏移量！重写到PC（两次改写）

x86梳理

x86-mov mips=r【0】

PC也可能是负数（补码形式给出FE=-2往回走两个字节） ；看x86 四看有没有条件判断（cmp jxxx jmp）有没有循环（loop）有没有函数调用（ret cal）有没有 EBP-8找的是局部变量（上层定义int a 这层直接传递a） EBP+4找的是全局变量

一个函数内定义的int a 叫局部变量，函数内定义的函数要找这个局部变量是ebp-4，而参数是函数头call（int a）自带的，也就是别的函数调用这个call的时候 传过来的！这个a是ebp+4找到的（因为要想这个call有上层传的参数 必须压到本栈的栈低，故ebp+4）

int add(int a ,int y){
    return x+y;
}


int caller{ 
//这个n是参数 ebp+4 理解成要想使用n需要把n的数值压到call函数调用这个栈的栈底
int a =1;//里面定义了a
int b=2;//里面定义了b

int temp= add(a,b);//这里面用到了a，这个时候a叫局部变量需要上上层去找！ebp-4 ebp-8
}

栈帧如何跳转？

mips risc-v考流水线是否堵塞！

CPU

问题：

取指周期结束后，这个指令存到IR了，之后CPU是如何分析指令的？

可见不可见对用户，对程序员，对汇编程序员？？？

流程：IR指令执行完后，PC存放下一条指令地址，是通过地址总线？送到IR的？然后循环？；中断产生时中断信号存放在哪？中断处理程序存放在哪？中断控制器在哪？可屏蔽中断线在哪？psw和那几个标志位关系

大题：CPU中数据流动过程？从哪来经过什么到哪去？指令流程，PC加加减减的跳转，运算过程，运算结果存哪？异常中断检测与处理？流水线的冒险处理？

机器指令的操作码字段形成其对应微程序的入口地址

可见（程序员可改——中通APP）：中断、通用寄存器组、ACC、PSW、PC、变址寄存器IX

不可见：MAR MDR IR 微指令 移位器 暂存器 指令缓冲寄存器 乘法器（mux） 基址寄存器BR
 

cache不管用户还是程序员都不可见！

PC可见是为了使程序可以跳转执行，若不能修改的话程序只能顺序执行；MAR MDR IR 不能被修改的原因就是这些存在的目的辅助硬件工作不需要人为干预。

运算器（ALU PSW ACC 通用寄存器 暂存器）
控制器（PC IR ID（指令译码器）控制器CU）

通用寄存器组里面就是存放运算后的结果，可以减少访存次数，
PSW ，ALU运算的结果生成一些标志位，控制信息，有的供跳转使用有的供设置可不可以中断的

通用寄存器清零则不需要切换到内核态执行

取数周期，主存到MDR后，数据先存到通用寄存器组，对于ALU这个纯计算的东西，考就是两个输入一个输出。对于输入端口有一个是直通的一个是带有MUX多路选择器的，或者再来一个暂存器（缓存器），ALU输出也要一个缓存器，防止数据直接打到总线上。ALU本身没有寄存器只能运算，大部分也都是两个数的加减，ALU再配一个标志寄存器，把输出的结果打到（OFZFSFCF）传递给CU控制器做下一步操作。

五段流水，指令和数据cache分离。
译码阶段，译码跟取寄存器的操作数，对于流水线（RICS），规定访存指令只能使用load和store。其他不允许访存。
执行阶段，使用ALU计算，可能把运算结果写回内存也可能写回寄存器。
访存阶段，(这个地方就有问题了，在ALU运算完后，如果是写回内存，下一条指令还用这个内存的数据就必须等访存段结束。如果计算的结果需要存到寄存器堆这就需要第五段)
回写：把EX段运算完的结果回写到寄存器堆当中。

16位cpu通用寄存器共有8个：.八个寄存器都可以作为普通的数据寄存器使用。
AX（累加器(Accumulator Register)）
BX（基地址寄存器(Base Register)）
CX（计数寄存器(Count Register)）
DX（数据寄存器(Data Register)）
BP（基址指针寄存器（Base Pointer））
SP（堆栈指针寄存器（Stack Pointer））
SI（源变址寄存器 （Source Index））
DI（目的变址寄存器（Destination Index））

时间局部性，用了还用这个（temp用了一次又用），空间我用这个下一次用的就在这个旁边（数组就是）。

一条指令执行过程

操作元件（组合逻辑元件，运算器）：ALU、加法器、乘法器、除法器、三态门、多路选择器（MUX）、译码器（Decoder）
存储元件（时序逻辑元件，控制器）：普通寄存器（无特殊功能只管存储 MAR MDR IR PC PSW）、暂存寄存器 、通用寄存器组（PTRS）、移位功能寄存器、自增自减寄存器、符号扩展寄存器、零扩展寄存器、取反寄存器

取指都一样，注意PC+1。可以由ALU或者加法器或者带有自增自减的寄存器实现！

执行阶段：
        数据传输指令，立即数---寄存器---主存之间数据流动
        运算指令，加、减、乘、除、与、或、非、移位、短数与长数之间的转变
        转移指令

RAW WAW WAR

RAW写后读注意在WB之后才可读不然读的是旧的！WAR安排读空几个周期让写先写好再读！

运算类指令，load指令，store指令，条件转移指令，无条件转移指令
对于运算类指令，访存这步骤通常没有操作（操作结果直接送往 WB）。运算结果不需要访问内存，因为它不涉及对数据存取。它只是计算并等待下一步写回寄存器。对于纯运算类指令，结果通常直接送往 WB（写回）阶段，因为它们只是寄存器之间的数据操作，不涉及内存访问。没有数据需要从内存中读取或者写入到内存中。
无条件转移指令，WB 阶段有时候的确是为了特定操作，例如更新 PC 值，尽管称为写回阶段，但它并不是典型的寄存器数据写回，而是控制流的更新。

分析是否存在数据冒险？
核心特点：两条指令，前“写”后"读"同一个寄存器
分析方法：从第一条指令开始，观察该指令“写”了某个寄存器，并观察后续相邻的3条指令是否“读”了同一个寄存器。若发现此类情况，则存在数据冒险。

控制冒险，但凡有转移指令就有可能发生控制冒险，只需要让后一条指令往后延迟三个时钟周期，这样当上一条指令在访存M阶段（会修改PC），下一条指令在上条指令修改完PC后再去取指，取到的就是正确的指令了！

I1 IF ID EX M WB

I2      IF ID EX M WB

I1    IF ID EX M WB

I2         █  █   █   IF ID EX M WB

这时候取指取得是旧PC这时候取指取得是修改后的PC，真PC

各种冒险设计流水线主要还是ID如何取（ID是译码同时从寄存器取数，这些冲突就发生在寄存器当中） 取数ID是有变化的，IF取指令是无所谓的！但是在跳转指令的时候IF必须安排在修改完真PC后才能IF也就是上图I6-I1这段！跳转指令在M阶段更新PC。指令执行过程在取完址IF之后就更新PC，但是对于跳转指令这时候PC是假的！要等到EX之后重新计算真的PC，在M阶段给PC赋值！

在一个时钟周期内，流水线的每个阶段都可能发生异常或中断，一般的做法是只将异常原因和断点记录到特定寄存器，指令继续在流水线中执行， 直到最后阶段（中断周期），检测该指令是否发生了异常或出现外部中断，若有则刷新（重新开始一段流水线）流水线并转入中断处理过程；

总线

 IO

 

 

中断

当外设准备好时，便向CPU发中断请求，CPU响应后，中止现行程序的执行，转入一个“中断服务程序”进行输入/出操作，实现主机和外设接口之间的数据传送，并启动外设工作。“中断服务程序”执行完后， 返回原被中止的程序断点处继续执行。此时，外设和CPU并行工作。
中断响应的条件（缺一不可）：CPU处于开中断状态；在一条指令执行完；至少要有一个未被屏蔽的中断请求
中断响应过程：执行一条隐指令，可能需完成一次总线操作，从总线上取中断类型号

保护现场及旧屏蔽字（压栈）；开中断（新中断的屏蔽字设置好可以执行新中断程序了，开中断说明该中断允许嵌套）；关中断（恢复阶段，弹旧屏蔽字是原子操作不能被打断）

CPU响应一个中断是在中断周期才响应！取指间址执行结束后进入中断周期检查中断信号INTR！而异常是立刻响应的

中断过程：响应（硬件）+处理（软件） ；单级中断系统不允许中断嵌套。①~③由硬件完成， ④~⑧由中断服务程序完成

1.关中断：0=>中断允许触发器

2.保存断点；保存PC和PSW（跟保存现场不一样！CPU执行任何程序根据的是PC值！要想执行中断服务程序，必须根据PC地址）

3.识别中断源；（送中断服务程序地址到CPU的PC 执行程序）

4.保存现场和屏蔽字；（软件来做 把IR PTRs寄存器数据压栈；多留意到底PSW是软件保存的还是硬件？只能是硬件来保存这些PC PSW。现场信息是指用户可见的工作寄存器的内容，它存放程序执行到断点处的现行值。如果没有嵌套，那么也就无所谓保存屏蔽字了）

5.中断事件处理；

6.恢复现场:（弹栈，单级不可能嵌套中断！但多级时恢复现场操作是原子操作不允许打扰。嵌套中断只多了在执行程序前后的开中断，关中断）

7.开中断：

8.中断返回。

中断响应优先级是针对同时到达的中断请求先处理谁。比如A、B同时向CPU发出中断请求，而中断响应优先级是A>B，那么CPU就会先处理A，再处理B。中断处理优先级是解决中断嵌套情况下优先处理谁。比如A、B两个中断的中断处理优先级是B>A，如果当CPU正在处理中断请求A时，B向CPU发送了中断请求，那么CPU会先暂停处理A，转而处理B，B结束后再继续处理A。在同一个系统中，中断响应优先级A>B和中断处理优先级B>A是不冲突的。A、B同时到达由中断响应优先级决定先执行谁（先执行A 然后在A隐指令执行完，开中断时中断A去执行B中断！然后返回A），A、B不同时到达在发生中断嵌套时由中断处理优先级决定先执行谁。

每个中断源自己设置屏蔽寄存器的屏蔽字（目的是设置中断处理优先级）！CPU在中断周期查询到INTR有效！发出中断查询信号（CPU只知道有中断，不知有几个）需要去判优电路查询哪个中断源响应优先级更高。这里B更高！会形成B中断源的向量地址（中断号）送到CPU。会先执行B中断，这时B设置自己的屏蔽寄存器的屏蔽字，并开中断。C的中断处理优先级更高！B的屏蔽字屏蔽不了C的中断请求信号，这是CPU到中断周期可以检测到INTR=1，去判优电路查询哪个中断源响应优先级更高（这里只有C，这时候尽管C的响应优先级低但是处理优先级高，依旧执行C）

判优电路决定中断源响应优先级，屏蔽寄存器决定中断处理优先级。中断处理优先级决定CPU能不能响应中断（一旦屏蔽字没屏蔽掉这个中断，那么必是比当前中断处理优先级高）

多重中断才有中断响应优先级，中断处理优先级。

指令周期执行差不多了，去执行中断周期，执行完再返回执行该指令！是的，该条指令以及执行完，但是一个功能的完成并不是只有一条指令！比如开机这个功能需要10条，在执行完第五条去执行中断！然后再返回当前PC值继续执行下面5条！

理解，E处看的不是响应优先级而是处理优先级。为什么C处看的是响应？记住一点同时到来就看响应，其余情况比如E这里，看的是处理优先级。为什么1执行完回到2？此时不应该5的优先级更大吗？是因为，2的屏蔽字等信息压栈了，1执行完，2的信息弹出来。当2程序开中断时，5的处理优先级高，先执行5，2的信息再压栈。2处理完，因为3的中断被屏蔽需要先回到主程序，然后在指令周期结束后。查询INTR发现有中断再回去执行3中断

有说保存断点（PC）只能硬件保存，软件（中断处理程序）只能保存PSW PTRs等寄存器的值！

应用程序通过系统调用（System Call）向os请求服务时触发的中断。系统调用是应用程序与操作系统之间的接口，允许应用程序访问操作系统的功能和服务。当应用程序执行系统调用时，CPU 会转移到操作系统的内核态，并跳转到相应的系统调用处理程序。这个过程中发生了从用户态到内核态的转换，并触发了中断，即系统调用引起的中断。假设有一个应用程序需要从文件中读取数据。应用程序会调用操作系统提供的读取文件的系统调用，如read()。在调用read()时，CPU会触发中断并转到操作系统内核态的处理程序，将读取文件的请求传递给操作系统。处理完成后，操作系统将结果返回给应用程序，并将 CPU 切换回用户态，应用程序继续执行。

执行系统调用过程：传递系统调用参数->执行陷入trap指令->执行服务程序->返回用户态
保存断点和程序状态字（隐指令做的）；CPU把用户态到内核态（也是隐指令做的）；保存通用寄存器内容（软件做的，指保存现场）；执行系统调用服务例程（软件做的）

向量地址内容是中断向量的地址，中断向量是中断程序的入口地址

一.从中断控制器的角度来理解整个中断处理的过程
二.printf -从系统调用到i/o控制方式的具体实现
三. scanf-中断方式下输入一个字符串的具体过程

cpu 设备控制器 IO设备

计组里面着重讲三种/O控制方式，操作系统里面着重讲/O软件的处理过程，软硬件究竟是怎么协同工作的呢？？？
不同的VO控制方式对应不同的设备驱动程序工作流程上到底有什么样的区别呢？

设备驱动程序和中断处理程序到底是什么呢？有什么区别呢？是什么关系呢？
什么是设备控制器？ 用户缓冲区？ 内核缓冲区？数据究竟是怎么一步一步一步的输入输出的呢？ 每一个过程是由什么程序来控制的呢？

系统调用在i/O里面起了什么作用呢？ 中断软件机制和中断硬件是怎么协同工作的呢？

一个具体的IO过程 硬件（IO控制方式），软件（用户层软件，设备独立性软件，设备驱动程序，中断处理程序，硬件）

设备驱动程序一定有一部分是在发起系统调用的进程A当中执行的，而中断处理程序则一定不是在进程A中执行，取决于CPU响应中断时正在执行哪个进程？

1.开机CPU如何一条条的读取命令

时钟信号就是计算机的心脏，从通电开始一直到关机，电脑的时钟信号始终是高低电平不停的跳动，每个硬件都有自己感知时钟信号的触发器（这个触发器能够做到极致的精确），触发器是构成时序逻辑电路的基本单元，它具有记忆功能，能够根据时钟信号的跳变来改变自己的输出状态。这样CPU就知道自己在计算机内的“时间”。

电脑硬件会自动将ROM当中的bios程序加载到内存当中去（系统进程加载到内存内核区），然后在CPU的PC计数器存着（进程有PCB，存放各个寄存器的初始值）初始化后，存放这个bios程序的初始内存地址。接下来会执行bios开机程序，这个CPU是如何执行这个开机程序的呢？关键就是总线（cpu与内存有地址，数据，控制总线）

首先是CPU根据PC（根据IR 知道本条指令多长计算结果 +1就是PC寄存器的内容），把地址通过地址总线送到内存的地址译码器中！（接着通过控制总线向内存发读信号），这个过程信息是如何传递的呢？CPU根据PC的传输的地址信息（二进制数据），当获取地址总线使用权限后，通过总线，按照时钟信号的跳动节奏有规律的发送地址信息。

这个信息跟时钟信号不一样，时钟信号是永远一高一低不变化的，但是这个数据信息就是有高有低（为啥要时钟信号？感觉就是计算机的沟通语言！多么长的低电平代表一个基本字符，假如发的信息是100个单位的低电平，因为地址译码器知道多长代表一个低电平，所以知道这数据是100个低电平。或者这样理解，发过来的100个电平是不知道多少，是根据时钟信号高低电平变化多少次记录的！就像是两条传送带，数据的那个传送带按照多长切一刀是根据时钟信号的传送带的高低变化的长度）跟计网一样，数据传递有数据头数据尾中间是要传递的数据！地址译码器当读取20个低电平就知道这下一个电信号就是数据的内容了，当读到连续的20个高电平就知道数据读取完毕了（至于纠错，这些都是一样的）

内存的地址译码器翻译出地址后，把数据通过数据总线传递到MDR，送到IR指令寄存器，然后翻译出来指令的地址信息！根据指令信息调度各个硬件资源！

这里的翻译指令的操作码字段使用的是什么部件？翻译出来的指令应该是在CU控制单元里对照是哪一种指令，然后CU开始下达各种控制信号！

2.数据流在CPU当中IR和MAR以及CPU是如何交互

看图，应该是IR的所有信息交给控制器CU（按照网上搜的这句话理解的不对），然后CU负责拆分翻译IR当中的指令，对比CU当中的快存储器分析出这条操作码是做什么的？分析出地址码送给MAR（这里只有一条路先到PC后道MAR，有点不对，因为当读取到本条指令后PC就自增了，那么这里的要取数的信息再去PC不就覆盖了！应该CU到MAR有一条通路）。控制器CU可以给ALU下达操作指令也可以直接去控制总线向外下达控制指令，CU也可以

CPU中翻译指令的操作码字段使用的部件是指令译码器。操作码经过译码后，控制器会根据译码结果生成相应的控制信号来执行特定操作。指令中的地址字段传递到存储器地址寄存器（MAR）的方法通常是这样的：当CPU需要访问内存以读取或写入数据时，如果该地址信息包含在指令中，这个地址会首先被放置到指令寄存器（IR）中。之后，CPU控制逻辑会从IR中取出地址字段，并通过内部总线将其传递到MAR。这个过程不是直接从控制器（CU）到MAR，而是通过IR作为中介。简而言之，地址信息的流动路径大致为IR → MAR，而非CU直接到MAR。控制器在此过程中起着协调和控制的作用，确保数据在正确的时间被正确地路由到MAR中。

这里有一步需要注意，当第一次是指令信息动刀IR后，然后拆分成操作码op以及地址码ad之后，MAR根据ad去内存取数，这时候取出来的经过数据总线送到CPU应该不再放在IR了，应该直接进入到ALU或者寄存器组GPRs了。

3.要执行的是一段加法程序，两个数据都在内存，CPU要执行加法操作并把结果写回内存当中

PC指向当前指令在内存当中的位置，然后取指令。取指令，PC通过控制总线向内存发送读信号（必定是内存同意后CPU才发指令）然后通过地址总线（从CPU过去的数据都是地址总线，从内存过来的都是数据总线）到内存的地址译码器，译码结束发信号给CPU，通过数据总线传给CPU。

译码阶段，IR得到指令然后进行译码（不是IR译码而是指令译码器），这个时候PC自动指向下一条指令（这个1是当前IR中（也就是正在执行的指令的长度））译码结束后是加法操作，这个时候把送过来的32位数据（取址阶段是指令）按照规则进行截取，通过MAR从地址总线到内存得到对应的操作数，循环两次后。第一次取数放到暂存器，第二次取到直接运算。

执行阶段，ALU从CPU当中的寄存器取数，一个数据在暂存器，之所以要这样设计一方面ALU不能存数，所以必须两个数同时到ALU才能运算，一方面是因为总线传数据是互斥使用的！所以有了ALU+暂存器的配置！

回写阶段，这个阶段CPU会根据指令当中的需要回写的地址，把数据要么写回内存要么存到寄存器

如果没有影响控制流的指令（如跳转、返回等），CPU将继续按照PC指向的地址取下一条指令执行。如果有特殊控制指令，CPU将根据指令要求更新PC的值，改变执行流程。

4.cpu在执行指令的时候PC+1，在硬件上具体是如何执行的？流程是什么？

当前指令完成执行后，控制单元（Control Unit）通过内部的时钟信号触发一个自增操作。PC存储的当前指令的地址会被送入一个加法器（ALU，算术逻辑单元，15年考的是乘法器！直接乘2）。加法器将PC的值和当前指令长度进行相加操作。相加的结果会被送回PC寄存器，覆盖原来的值。PC寄存器更新后，会将新的指令地址发送给指令缓存器（Instruction Cache）。指令缓存器根据新的指令地址从内存中读取下一条指令。控制单元将读取到的指令送入解码器（Decoder），对指令进行解析并执行相应的操作。执行完当前指令后，控制单元会再次触发一个自增操作，重复上述流程继续执行下一条指令。

ALU和加法器在功能上的区别在于，加法器是一种用于执行加法运算的数位电路部件，而ALU是一种可对二进制整数执行算术运算或位运算的组合逻辑数字电路。加法器的输入是加数和被加数，输出是和数；而ALU的输入是要进行操作的数据以及来自控制单元的指令代码，输出是运算结果。

6.dma方式也运行中断程序，为什么不需要保护现场？

保护现场指的是寄存器等需要被中断后的程序使用，所以原来的值需要换地方存储，DMA中断以后，不需要操纵寄存器，信息传送不经过CPU，只需要cpu处理一下，所以被解释成“只用借用一点时间“，无需保护现场。

程序查询程序中断DMA
数据传输方式依赖软件依赖软件依赖硬件
数据传输的基本单位字或字节字或字节数据块
CPU与I/O设备的工作方式串行工作

CPU与I/O设备并行工作，

现行程序与I/O传送串行进行

CPU与I/O设备并行工作，

现行程序与I/O传送并行进行

CPU的工作方式CPU主动查询I/O设备状态CPU被动接受I/O中断请求CPU被动接受DMA请求
传输速度不同软件额外开销时间基本没有，因此传输速度比中断快软件额外开销时间比较大，因此传输速度最慢由硬件实现传送，因此速度最快
中断跟DMA对比

1.目标是CPU，
2.可以处理异常，
3.靠程序传送的，
4.中断的优先级小于DMA

5.中断处理在指令结束后响应

6.多控制低速设备（鼠标键盘，这些中断次数少慢，要多的话，CPU光搞中断了没办法工作了）

1.目标是总线，
2.仅用来传送数据，
3.靠硬件传送的

4.每个机器周期（取址，间址，这些机器周期（也叫总线周期）结束就可以检测）

DMA 导致的虚存跨页和 Cache 一致性问题？

机器字长：CPU一次性能够处理的二进制位数
指令字长：一个指令字包含的二进制位数
存储字长：一个存储单元包含的二进制长度

若指令字长是存储字长的二倍，那取一条指令要访问主存两次，也就是说取指阶段要访问主存两次，
机器字长一般等于内部寄存器组的位数（也有可能多或少）
单字长指令就是：指令长度=机器字长
双字长指令，半字长指令

指令执行过程，只要各个步骤能同时发生（不能同时发生就是在传输数据可能有冲突），就可以安排在一个时钟周期。比如内存到MDR，PC+1可以同时进行！09年大题，CPU内部的一系列的操作，PC、ALU、ACC、通用寄存器组、IR这些用的通路跟CPU外的三条线不一样！所以这两个部分的操作可以放在一起！比如，累加器acc结果存到寄存器组这个操作可以跟主存数据通过数据总线传到MDR！

计算机采用16位定长指令字格式！说明IR是16bit！

题目

20 1 0 ；

OS

os完成的就是在执行程序的时候被打断（优先级高）去执行别的程序而要进行上下文切换。关于在切换这一瞬间需要做的什么事情，理解中断，异常，调用，上下文。

  1. 进程三个组成部分？PCB包含哪些信息？进程的四个特点？五种状态？进程三种通信？进程线程六比较？线程的两种实现？
  2. 每个进程配一个页表，TLB只有一个（所有进程共享）在进程切换的时候整个TLB失效（只考虑单核，那么一个时间内只可能有一个进程在CPU，页表是每个进程配一个，在进程切换的时候直接清空TLB，页表信息则存回PCB。如果多核？）
  3. 每个进程的虚拟地址空间都是4GB，一页大小4KB 那就是每个进程给1M个虚拟页框。高地址是共享的内核区！低地址有的物理页框也可以共享。而查询页表或者TLB的时候！只根据虚拟地址的高字段，咋分辨到底是谁的物理地址？不同页都共享这4GB的虚拟地址！（是每个进程在上处理机的时候TLB是清空的，当访问页的时候未命中，这时候才上TLB，单核多核都一样，因为没有别的进程跟你抢！哪个进程在最开始用TLB的时候都是干干净净的。页表是虚拟地址与物理地址的映射关系，存放到TLB也是这个映射关系，是先有这个关系才有的TLB上的表项，所以不可能有冲突。A B进程就算都是一样的虚拟地址，但是页表项对应的物理地址不一样。虚拟地址不重要）
  4. 各个进程的物理地址有各自独有的也有共享的（内核区，有问题，内核区有不同进程各自的信息，共享了那不乱套了？都随便修改内容了）。不止内核，也有普通的这个共享方便了通信！A在01H页放数据，下处理机后B上从01H取数据！
  5. 中断向量表，中断向量：有中断信号,CPU根据中断信号去查表（向量表存的每一项都是中断向量），得到中断向量（存放的是中断程序入口地址）
  6. 一级页表在物理上连续存放完整一个页框，因为当查页表需要借助初始地址跟页表项大小找到每一个页框大小，若一级页表在一个页框存不下。
  7. 中断处理和设备驱动，文件，虚拟，各种PCB寄存器，内存映射文件。把中断各个步骤，保存啥回来，过去理解透彻，文件，调用，驱动，磁盘，
  8. os在查页表时发生缺页为什么不可能检查是否越界！越界检查在VA-PA已经查过了！
  9. os内核是由中断驱动的，即只有在中断或异常发生后才会引出内核工作，处理完成后内核就会退出
  10. 猝发传输第1个周期传输地址，后续周期传输数据

 

内存-磁盘

缺页处理程序与系统调用命令，这是指的真真正正处理了是在内核，而缺页发生了去找缺页处理程序的这个缺页指令，以及调用系统调用的指令是在用户态，必定要通过用户才能到核心态。以及访管指令，也是。缺页处理程序与系统调用命令（内核态）；缺页指令，调用系统调用的指令，访管指令都是用户态的程序。
修改PSW程序状态字是特权指令。

基本分页存储管理方式 ，不具备页面对换功能，不支持虚拟存储器功能，在调度作业时 ,必须将它所有页面一次调入内存 ,若内存没有足够的块, 则作业等待。
请求分页管理方式是支持虚拟存储的,具备了页面的对换功能，调度作业时，是将它的一部分放入内存。虚拟也就是交换，引出调度交换算法，局部置换就是那些FIFO LRU CLOCK OPT（最优算法不现实谁都看不到未来）全局置换，也就是工作集。虚拟也就是基于局部性不然没有局部性那就有可能出现抖动或者一直缺页。


工作集：分配四个！时间4-1232工作集123，而工作集窗口是允许重复的，此时工作集窗口1232

轮询，CPU放弃当前执行环境去管io，这个有上下文切换的时钟周期消耗。之前考18年，咋才不丢数据就关键是你上下切换耗费的时钟周期必须要比我充入数据缓冲寄存器的时间短才不丢。至于这个保存完上下文后CPU是到底咋取数据呢？不能把CPU当个人走到数据缓冲区看到的吧？有数据我再扛回CPU这个家再存到内存中。

绝对装入：编译时就知道程序将放入内存中的位置，编译程序将产生绝对地址的目标代码，只适用于单道程序环境。
静态重定向：装入模块中的地址还是逻辑地址，直到真正装入内存时将逻辑地址变换位物理地址，程序运行期间无法移动
动态重定向：装入程序把装入模块装入内存后，并不会立即把VA->PA，而是把地址转换推迟到程序真正执行时才发生。需要一个重定位寄存器
链接前应该是编译结束（也就是形成了机器代码）

分扇区（物理格式化）→分区→装文件系统（逻辑格式化）→装os

分配内存：首次适应（先找低块，碎片大）；下次适应（上次查找结束开始往后找）

进程

 等待时间注意只是等待CPU的时间，等待IO不算！

进程之间交互信息：通道和中断引入就是为了保持进程之间能正常工作。单道作业变成多道系统（从原来的一次只能执行一个任务可以变成同时并发执行多个任务）。通道就是小CPU，IO处理机。

驻留集，一个进程能得到的页框。
工作集，某段时间的页面集合

如果系统只有用户态线程，则线程对操作系统是不可见的，操作系统只能调度进程；
如果系统中有内核态线程，则操作系统可以按线程进行调度

进程调度内容

7个算法
先来先服务 （FCFS)——不抢占，不利于IO繁忙型作业有利于cpu繁忙型作业，IO繁忙会大量跟IO交互如何先到CPU会长时间占据CPU资源（资源浪费），CPU繁忙来了就处理，很少跟IO，处理很快充分利用CPU资源
短作业优先（SJF）——不抢占
最短时间剩余优先（SRT）——抢占，抢不抢的时机是刚来到，

高响应比优先 （ HRN ）——不抢占，尽管算的是（等待+处理）÷处理。但是也只是每一次一个任务结束后才算的而不是时时刻刻计算。

优先级调度 （HPF）——实时，有可能饥饿
时间片轮转（ RR）——抢占，适合分时
多级反馈队列

 调度的时机

什么时候能进行进程调度？当上一个进程离开CPU的时候，可以调度下一个进程上CPU。
①某进程结束②进程时间片用完③进程被抢占④进程被阻塞⑤外部I/O中断，转到中断服务程序⑥父进程执行fork()，产生子进程，选择调度父进程还是子进程

什么时候不能进行进程调度？①关中断之后的中断处理过程②在OS内核临界区不能调度③执行原语

当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，就不会影响处理机的调度。比如，通常访问的临界资源可能是慢速的外设（如打印机），若在进程访问打印机时，不能进行处理机调度，则系统的性能将非常差

进程调度的代价：cache TLB清空！调度好上处理机初期缺页率高，重新保存/恢复PTRs

父子进程--进程--线程

关于进程：关于线程：
进程是什么？它由哪些组成部分构成？
进程的状态有哪些？解释每个状态的含义。
进程之间如何通信的？列举几种进程间通信的方式。
什么是进程调度？操作系统如何决定将CPU时间分配给哪个进程？
进程的创建和终止过程中有哪些关键步骤？
进程间的资源共享和竞争是如何解决的？
进程的地址空间是什么？它是如何分配和管理的？
进程控制块（PCB）的作用是什么？它包含哪些信息？		线程是什么？与进程有何区别？
线程的执行方式是怎样的？它与进程的执行有什么不同之处？
什么是用户线程和内核线程？它们之间的关系是什么？
线程的同步是什么？为什么需要线程同步？
什么是线程死锁？它是如何发生的，又如何解决？
线程的调度是如何进行的？有哪些调度算法可以选择？
线程之间是如何共享数据的？有哪些线程间通信的机制？
线程的优点和缺点分别是什么？在什么情况下适合使用线程？

什么叫同一进程当中的线程拥有相同的地址空间？指在一个进程内所有线程共享相同的虚拟内存空间。所有的线程都能访问到这个进程所拥有的全部内存区域，包括代码段、数据段、堆和栈等。如果线程共享进程的空间，那么线程的数据存放在哪？进程的空间都存放了进程的数据了！当说线程共享进程的地址空间时，意味着它们共享进程的代码段、全局数据、静态数据和堆内存。但是，每个线程也拥有自己私有的部分，主要是栈空间和一些线程局部存储（TLS, Thread Local Storage）。

  1. 栈空间：每个线程都有自己的栈空间，用于存储函数调用的局部变量、函数参数和返回地址。这意味着即使两个线程调用了相同的函数，它们各自栈上的局部变量也是完全独立的，不会相互干扰。

  2. 线程局部存储（TLS）：TLS是专门为线程设计的存储区域，每个线程都可以在TLS中保存私有数据，这些数据不会被其他线程访问。TLS通常用于存储线程ID、线程特定的配置或状态信息等。

  3. 共享数据：除了栈和TLS之外的内存区域，如全局变量、静态变量和堆上分配的内存，都是所有线程共享的。这意味着如果一个线程修改了全局变量，这种改变对其他线程也是可见的。因此，需要使用同步机制来控制对共享数据的访问，防止数据竞争和不一致性。

一个进程包含的信息代码段，数据段，堆，栈还有TLS。就相当于给线程留一些空间！这里所有的线程有相同的地址空间就代表，所有的进程空间线程都可使用（除了一些TLS）

进程通信是如何通信的以及线程通信如何通信的？
进程通信通常需要通过内核提供的机制来实现，涉及更多的系统调用和资源管理（进程间的通信机制低级通信方式：信号量；高级通信方式：共享存储（数据结构存储区）、消息传递（消息缓冲通信、信箱通信）、管道通信）
线程通信则更直接，主要要关注原子操作以及互斥，防止多个线程同时访问临界资源或者说共享的变量。

 进程的状态
1.就绪挂起只能和就绪态互换！
2.阻塞挂起可以转换为就绪挂起，反之不行[这个跟就绪和阻塞的关系一样都不能反过来]

同步互斥

临界区互斥方法
硬件：①中断屏蔽方法②硬件指令方法：TestAndSet指令；Swap指令【所有硬件方法都不能实现让权等待？？？】
软件：单标志（只检测不上锁执行完再turn=0让别人用），双标先检查后上锁，双标先上锁后检查，Peterson

用户态到内核态通过系统调用或者中断或者异常。

为了把分散在各进程中的临界区集中起来进行管理引入管程，管程就像JAVA里的“类”，一次只能一个进程调用（wait signal信号），保持互斥。
管程一种进程同步机制，但并不是通信机制

访管指令，用户态可以执行，目的产生访管中断进入核心态。

PV---消费者，哲学家，读者

所谓同步就是资源（十个饭碗N=10），所谓互斥就是不能同时操作（拿饭碗这个动作mutex=1）
生产者消费者读写着问题叫号问题哲学家
对于缓冲区的互斥mutex
产品及空间的同步full、empty		读写互斥read、write
读操作计数int count		对取号机的互斥mutex
客户、服务员同步costumer、server
号码int number		一下子拿完才给吃
筷子互斥数组chopsticks[n]
需要对哲学家进行限制

生产消费，服务被服务，读写者（同类不互斥，异类互斥）历年从未考过，哲学家（只有一类进程，每个进程需要同时多个资源）

生产消费问题-进程之间是生产和消费资源的关系！具体操作必须写注释

  1. 几类进程？一个进程一个函数！
  2. 函数内部中文描述动作！动作重复与否？重复加while（1）
  3. 做动作之前是否要先申请资源？（也就是P一下）P的时候是否要互斥的访问缓冲区，有P必有V写完P就快写V。
    1. 写semaphore的时候要给注释！rice=0 ；//注释！
    2. 先P同步，后P互斥！一百个坑位拿走一个就少一个（同步）；我把产品放在这个坑位的动作是互斥访问的！我放坑位的时候你不能放，这叫互斥。
    3. 互斥访问缓冲区。P（mutex）这个mutex放在最里面最好，最不容易产生死锁。
  4. 先写pv之后再定义信号量！定义后思考初值
  5. 多个P连续出现是否可能出现死锁！要是PV之间没有其他P就不可能产生信号量死锁！破坏了请求和保持这个条件！（我既然可以申请A，那么在释放A之前没有申请其他资源，不可能有请求保持！即破坏死锁必要条件）
  6. 多梳理一下看看合理与否！

某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入缸取水仅为1桶水，且不可同时进行。给出有关从缸取水、入水的算法描述。

第一次写，没考虑清楚老和尚喝水也要桶，以及小和尚取水是需要互斥访问井的！以及把水倒进缸里也是需要互斥的（有老的喝就不能倒水！有人倒水别的人就不能喝以及不能倒水）问题就是，老和尚喝水之前不能先拿桶，要先判断一下是否有水，没有水就不拿桶，不然三个老和尚都拿桶了，卡死了也没水！进行不下去了！同时小和尚也一样！也不能都打水！那样要是满了老和尚就喝不了水！也卡死！（也就是看有没有死锁就看，当多个P连续出现会不会出现死锁！最里面用缸PV成对出现不会产生死锁！只有P(桶)P(缸有水)P(互斥使用缸)这三者之间会出现死锁！)

对待这种容量有增有减的，必须配两个自变量，为什么水缸需要两个？因为是同步信号量，而水桶也是有增有减的只需要一个自变量就可以表示的？因为是互斥信号量。

哲学家进餐问题就可以无脑用一下子取得所有的资源来做！比如干饭人，要碗要座位要筷子要菜，这种类型就一下子全拿所有的资源就行！互斥拿！互斥p（mutex）mutex初值为1，一个个申请！申请完释放！

前驱后继的问题，先V后P

中断

要程序并发就要引入中断，中断就是引出os工作。中断是os唯一夺回CPU使用权的方式。
用户态→核心态是通过中断实现的。并且中断是唯一途径
核心态→用户态的切换是通过执行一个特权指令，将程序状态字（PSW）的标志位设置为用户态
但凡有对资源的请求都要用的系统调用对os发出对某种资源的请求。

当CPU在执行用户进程时获得一个中断信号后，会保存寄存器状态、切换到内核态、查找中断向量表、执行中断处理程序，最后恢复用户进程的执行
中断向量表跟中断处理程序都在os内核区，不一定都在内核。因为保存断点pc跟程序状态psw是硬件自动完成不是os。

可以把中断理解成，os从用户手里夺取CPU使用权。用户态到内核态（内核态是os进程在运行）而且因为有了中断才使得并发可能。

外部中断是用户态到核心态的”门”，发生在用户态，在核心态完成中断过程。
进程切换只能发生在核心态，而缺页中断由用户态发出，在核心态执行缺页中断服务程序。
进程通过read系统读取磁盈文件中的数据，需要通过陷入将CPU从用户态切换到核心态

一般中断是去执行别的服务，但时钟中断目的只是为了进程调度！当前进程你的时间片到了换下一个进程

中断硬件保存PC PSW 子程序调用软件只保存PC

异常（内中断），外中断

当异常和中断来的时候，到底是立刻执行还是要等到中断周期再执行？异常不能被屏蔽，有异常就立刻执行。但是中断是可以到中断周期执行！相当于当前指令执行完毕后（这种外部中断都不紧急），响应完中断回来后，就自然下一条指令了。保存断点，CPU状态都是为了回来到这条指令的下一条继续。

系统调用的概念是用户态要进入核心态的一个程序，用户要使用系统调用要使用trap指令（陷入异常[内中断]，trap指令），trap指令运行在用户态

哪几种异常会使CPU重新执行命令，哪几种中断会使CPU继续执行命令？这个不好说，就算是保存了寄存器数值到内核栈，也不一定就返回的时候继续执行。但是做题对于中断应该是继续，系统调用也是继续，而异常要重新执行。

异常出现后执行完处理程序后返回的时候是重新执行指令还是到下一条指令执行，看题目吧，但是中断是必定下一条指令！异常包含陷入指令。这个跟系统调用没关系，是用户要系统调用才会trap异常，这个时候直接执行trap指令！至于反不反回到trap，我想的是一般一条指令要trap的话，也应该到了最后阶段了！

管道

死锁的四个必要条件

互斥，不可剥夺，请求和保持，循环等待

临界区使用准则： 空闲让进，忙则等待，有限等待，让权等待

两个资源：平板和厕所！我在上厕所想要用平板看电影，但是平板在我室友那！我室友有平板，但是他想上厕所看电影！这个就构成死锁了！我占有的资源我不放手而且这个资源就一个，我用你不能用，你不能抢，同时我有一个资源我还想要另外一个资源。对方也是，这个时候就有一个圈。所以就行成了死锁，除非打破这个死锁。

打破互斥：俩人用一个马桶上厕所！【这个不可行，这有点无赖】

打破不可剥夺：室友把我从马桶上拽出来他上厕所，或者我抢他的平板。

打破请求和保持：我自己主动让出马桶，或者对方主动让出平板

打破循环等待：我不要平板看电影了，我干拉；我室友不要厕所了拉裤子里也要看电影。

有循环等待不是产生思索的充要原因，是因为每一个资源都只有一个，才是充要原因。

文件系统

打开文件的过程：假设该文件还没被打开过。进程打开文件，由给出的路径找到目录项，目录项包括文件名和文件元数据（索引结点=FCB），以索引节点为例，目录项里保存了文件名以及对应索引节点号。由索引节点号去索引节点表找到索引节点在外存的位置，再将它写入内存缓冲，系统级打开文件表增加一个表项，索引节点号和对应内存指针。进程级打开文件表增加一个表项，内容是系统级打开文件表对应表项的指针，系统级打开文件表表项引用计数置1，给用户返回文件描述符fd。打开文件就是将FCB读入内存

对于文件系统来说，用户查找数据，首先会通过文件名跟路径找到目录文件中的对应FCB调入内存，再通过FCB里的文件信息找到该文件在磁盘中的数据，必须必须分两步。记死

可以理解为用户在使用文件系统的功能时，实际上是通过内存中的操作系统内核来访问文件系统的，而不是直接由文件系统的进程在工作。文件系统的进程是由操作系统内核来管理和调度的，它们负责实际的文件系统操作，但是这些操作是由内核代表用户进程来完成的。
用户进程想要打开文件，首先是向os内核申请访问文件系统，os内核检查一系列安全信息后才代替用户进程对文件系统进行操作并返回信息的。
文件系统的大部分内容还在磁盘，只有少数跟随os开机存到内存。比如驱动程序以及一些元数据（根目录）

打开文件表，os有一个打开文件表，每个用户进程也有一个打开文件表。整个os的打开文件表包含所有的FCB副本（Inode节点）及文件的一些信息。
用户调用open系统调用打开文件只不过简简单单查os的打开文件表，返回给用户指向os打开文件表的索引
用户open调用→通过进程的打开文件表→os的打开文件表（有全部文件FCB的副本inode）
有差异反正就理解系统打开文件表要么就是有指向inode表，要么就是系统打开文件表就存着inode指针指向外存的文件。

文件描述符（file describtor） 用于指代被打开的文件所有执行IO操作的系统调用都用过fd实现。可以理解fd就是一个数字（指代本进程的打开文件表）我这个进程要打开的文件有一个fd这个数值指针？可以返回给用户使用。指向的系统打开文件表，系统打开文件表指向的是每一个在外存的文件都配备的inode节点。因为不需要把整个FCB调进来。

os提供的接口
命令接口，脱机（流程化），联机（做一说一）
程序接口，必须通过程序调用间接使用。

SPOOLing假脱机技术
脱机就是脱离主机进行输入输出操作
输入输出进程像纸袋机，必须与用户进程并发，所以必须是多道程序技术
输入井，人把信息输入到磁带。存下来
输出井，磁带数据输出给外设。出去

过程：开机过程+查文件（open一直到把文件的磁盘块调入内存为止+read读文件的信息，比如一个磁盘块4kB，我要读这个文件的第11kB-12kB的信息）+十个一级索引不够了，读二级索引过程（就是二级索引那个磁盘块都是用来存放索引的，假如一个索引4B，那么这个磁盘块就够存1024个索引）+UINX FAT

开机
1.CPU执行主存ROM里的引导程序（自举程序会把MBR调入内存）
2.将磁盘第一块主引导记录（MBR）调入内存（主引导记录里面有磁盘引导程序和分区表），执行磁盘引导程序来检查分区表（这样才知道这个磁盘分为几个盘块！os安装在那个分区！）。从主分区（安装了os）读取分区（比如C盘）的引导块到内存，CPU执行该引导块的程序（C盘分区里引导块的程序就是为了初始化os）分区表记录了每个卷（盘）起始终止地址
3.从该主分区的某部分空间里存的是根目录信息（调入内存）找到完成的os初始化程序并执行，完成开机一系列操作。

Unix文件系统：

分清楚目录文件和Inode，C盘的引导程序应该是先找到根的inode调入内存，根据根目录的inode中的索引信息找到的根目录文件，调入内存。根目录调入内存后，通过根目录文件下的各个（文件名，inode号）一一对应，找到A文件的inode在哪！然后根据inode里的索引找到A文件夹的目录文件存放在磁盘的哪个位置！

索引表是Inode的一部分，Inode有一些FCB的基本信息（有一个共享计数的部分是用来识别有多少个硬链接的）；inode格式化的时候已经初始化好有多少个inode了，不能动态增加。而且inode会固定存放在外村的某几个簇里！用数组结构存储（大小固定，方便快速找到某个文件的inode）

FAT文件系统：

FAT文件系统就没有INODE，根目录文件（固定存放）包含了一个文件的所有信息（除了数据文件，数据文件需要查FAT表后才知道在磁盘的哪几个块），FAT表也是固定存放！开机时会把根目录文件+FAT表同时读入内存（常驻内存）。

查文件，只需要去根目录文件找到这个文件的起始磁盘块是哪！然后去FAT找到这个文件的完整的信息！
查文件夹，这个时候根目录文件的目录项存放的就是这个文件夹的目录文件在磁盘的位置，然后查FAT表，看这个目录文件到底有多长？可能只用一个磁盘块或者多个！通通调入内存！再看这个文件夹里的文件！以此类推！

FAT表示存储结构，-1表示某个文件（文件夹）结束，可以用-2表示空闲块！而unix表示空闲用的是位示图或者其他方法！

I/O管理

IO接口

控制线传的读写控制信号和数据线传的控制状态信息

硬件与软件管理

硬件管理：数据如何从设备到内存，内存到设备。因此需要各种对设备的管理方式，比如轮询，中断，DMA，通道（这是I/O控制的种类），不同设备IO方式不同所以需要不同的I/O控制方式。

软件管理：有了输入输出了但是计算机与设备有速度不匹配的问题（看直播也是通过网络传到网卡里再下载到内存中浏览器所占据的那一部分空间里的数据区，然后浏览器显示出来的。）解决不匹配就有缓冲，缓存，假脱机这些技术。以及要解决基本数据单元大小不匹配（必须下下来全部才能播放）；网卡这些设备很少，但是进程很多就需要考虑如何分配这些临界资源

硬件管理主要是I/O控制方式：取数据到内存，CPU利用率变高，成本变高，复杂度变高

程序直接控制（轮询）：数据到内存但不知何时到内存，需要CPU一直去IO接口的数据缓冲区检查是否已经充满一组数据。让CPU定时检查buffer是否填满。CPU利用率很低，提出中断驱动方式

CPU查IO接口的数据缓冲区是否充满，是CPU运行在内存的输入进程这个程序，让这个进程去检查数据到底满不满，去看GPIO管脚，有输入存放到输入进程的数据区然后转到相应需要该数据的进程

中断驱动：一旦IO接口的buffer满了就通知CPU来取数据，CPU效率高，但还不够。因每一次满就要中断当前进程来处理这个取数据的操作（操作很无脑）为了减少打扰CPU正常工作的次数，提出DMA方式。中断处理程序来获取buffer中的数据，这个程序不是进程。

DMA：雇佣一个小cpu，一旦一组文件（一组可能会充满buffer多次），主CPU下达任务要取多少以及存放在内存哪个位置，命令到DMA后，在这一组文件的提取与存放就不需要主CPU干预了，只需要在一组结束后提醒一下主CPU，我这一组结束了（重点理解书上说这个提醒不算中断）还不够，因为每组文件从外部搞到内存固定区域后，还需要主CPU下达下一组的命令，还是需要主CPU干预，引入了通道

过程：疑问（尽管是DMA程序，但是程序的执行还是只能依靠CPU，这里咋感觉CPU与DMA程序并行执行？）

外设告诉CPU要传输数据（发送DMA请求，在通道程序发送的是通道请求）；

CPU响应请求，去配置在内存中的DMA配置程序，配置四个部分（要存在内存哪？主存地址计数器AR，要存多少WC，每次存的数据在IO接口有多少？DR，以及控制信号）

开始读取，进程DMA程序从磁盘忘自己的DR读数据，然后再把DR数据根据AR地址存到目的地址。一直读到WC计数为零，说明读完了！

然后程序向CPU发送中断请求，中断处理程序就去打开记事本说我已经传完一组了，够不够？如果要读的数据不止这一组，还有好多组数据要读！这时候要继续重新执行磁盘发送请求，再重新配置来一遍，直到所有的数据存完即可

通道方式：关于一整个大的文件，一次性把所有的信息都告诉在内存的通道程序，之后这一个大的文件（肯定会分成很多小的组，每组在哪个位置）就不需要CPU管，只需要把这一个整个大的文件搞完再给CPU一个信息。

过程：不一样就在于，初始时设备向CPU发送通道请求，CPU相应之后配置通道程序（告诉通道要在哪存？存多少？）然后通道程序去启动DMA程序，跟CPU配置DMA程序一样，通道程序也配置DMA，每读完一组到内存后，通道程序便重新再配置一下DMA程序，直到所有的组都发完后，通道程序请求中断，CPU响应中断去执行中断程序

四者区别：

一个大的文件假如分为100个组，一组里假如有能充满IO接口的buffer100次。每充满一次buffer如果CPU不及时提走，下一次又来了就会覆盖，会丢失数据。因此

轮询就是定时来检查

中断就是充满一次提走一次，要有100*100次

DMA就是用这个小cpuDMA，主CPU告诉你取完一组放到内存某位置，取完一组提醒一次只需要中断100次

通道就是，告诉通道程序，我有一个文件要存到内存，你来管，最后告诉我位置我能知道去内存的那个地方找到即可，只需要一次中断

有个题目就是轮询和中断处理的方式，有一个比率下数据充满不会丢。因为数据一直从io忘buffer充。

缓存和缓冲

缓存在内存，井在硬盘

快表TLB是主存内页表的缓存；高速缓存cache是主存内页面的缓存；而磁盘的高速缓存逻辑上是属于磁盘但是物理上是内存中的盘块，缓冲时间换流畅度！从bilibili服务器观看视频，需要从服务器下载数据通过网卡下载到本地内存里，然后CPU再显示在显示屏中，但是有时候网卡速度有限，就会产生不流畅的感觉！比如说：30帧/s 人才会觉得不卡，每一帧都是一张图片假如100kb/帧 的话，一分钟就需要下载180Mb，但是网卡假如才1.5Mb/s的话，就相当于1分钟下载90Mb，卡一半。人的视觉就会觉得卡。因此缓冲技术就是先等两分钟，等我下完你在看！这样就不卡了

作用：

1.缓和CPU与IO的速度不匹配（是因为用时间换的！并没有彻底解决速度不匹配的问题）
2.解决基本数据单元大小不匹配的问题，就是说传一张图片在网络上是分好几部分接受的，先接受图片的上半部分再中间再下半部分（假如是这样！）如果播放器就接受多少就播放多少，图片就不完整！所以播放器会运用韩冲技术等接收完完整的一张图片的信息后才会去播放一张图片，因此说解决了基本数据单元大小不匹配的问题。
3.减少IO对CPU中断的频率，比如说网速太慢传一张照片要3秒，这时候如果没有缓冲区，传1秒是照片最上面的部分，就中断CPU现行程序去执行显示图片，但是等好久不到下一秒数据到，CPU就回去了执行原来程序，等一小会又被中断来执行显示图片的程序。有了缓冲区后就会等接收完一张图片的所有数据后才去中断现行程序大大降低对CPU的中断频率
4.因此引出第四个优点就是提高了CPU与IO的并行性！

也就是低速才有缓冲的概念，高速会有那个进度条后面白点就是那种不一样的缓冲

传送进程（M），消费进程（C）都是CPU在忙，生产进程（T）是IO在忙
单缓冲：空时才能输入，直到充满为止，满时才能取出，直到取完为止（缓冲区要么空要么满）
双缓冲：

DCT<COCT<CHCT<SDT：每一个系统只有一个SDT（系统设备表），初始没插鼠标键盘的时候SDT里面就只存一个DCT（设备控制表）就是磁盘，之后插鼠标键盘后每一个设备都有对应的DCT，之后查对应DCT对应的COCT（控制器控制表）并为其分配对应的通道控制表（CHCT），以便于CPU通过通道控制控制器以及DCT设备

磁盘

柱面号（从外到内）盘面号（从上到下一片一片）扇区号（编号），计算磁块号到柱面盘面扇区的映射：

B（磁块号）=XM（每一个柱面M个磁道）N + Y（盘面号）N（每一个磁道有多少个扇区） + Z（扇区号）

Ts（寻道 ）：m×n（从最外面到目标磁道要跨n个磁道，每个磁道延迟m） + s（启动延迟）

Tr（寻扇区号）= 1 / 2r ，r是转速，1/r是一圈时间，平均找到具体扇区是1/2r

Tt（传输延迟） 1/r=T总消耗时间，N（这个扇区比特数），传b个bit要花费时间   b / Nr=bT / N

用来解决如何减少延迟（Ts Tr 都可以使用软件解决但是Tt一旦磁盘固化变不了了）

扇面或扇区交错编号可以减少延迟时间。

1.CPU调度各个进程的过程，相应的pcb以及一些状态信息

PCB的功能：

  • 程序计数器PC：指示进程下一次要执行的指令地址。
  • 进程状态：新建、就绪、运行、阻塞、终止等
  • CPU寄存器集合：通用寄存器、索引寄存器、堆栈指针等，存储进程执行时必要的数据和指令指针。
  • CPU调度信息：如进程优先级、调度队列指针、时间片剩余等，帮助os进行调度决策。
  • 内存管理信息：如基址、界限寄存器、页表地址等，用于虚拟地址到物理地址的转换。
  • I/O状态信息：记录进程相关的I/O请求和完成状态。
  • 记账信息：如CPU使用时间、等待时间等，用于系统监控和性能分析。

OS如何感知到有进程的？根据PCB常驻内存，有一个PCB就知道内存空间有一个进程！

进程是程序的执行，是一个动态的概念时时刻刻都发生着变化；
进程映像是某时刻进程的内容与状态的集合，包括：进程控制块（PCB），程序，数据（私有栈等），核心栈；

操作系统使用进程映像来创建和管理进程实体。当启动一个程序时，操作系统会根据进程映像加载程序的代码和数据到内存中，并分配资源给进程实体。进程实体执行程序，修改自己的状态，并与其他进程进行交互。进程实体是正在执行的程序实例，而进程映像是程序的静态快照（很像是一个进程在某时刻的所有寄存器pcb等信息的整合）

线程切换仍需保存和恢复寄存器状态，但不涉及地址空间切换，开销比进程切换小。用户级线程切换成本较低，因为它们通常在用户空间进行，不需要系统调用。

进程上下文是处理器的一个执行环境，包括：用户级上下文（程序 ，数据，私有栈等）、系统级上下文（PCB，页表，核心栈等）、寄存器上下文（PSW，PC，SP，控制寄存器，通用寄存器等）

创建进程，程序员写好的程序会存在外存，现在就当这个程序是一个进程。在创建进程，首先会创建PCB，初始化进程的信息，PCB会保存进程的地址信息（外存地址）。创建的PCB块会放到PCB组当中（在内存里），之后os把程序从外存调内存（这里也有涉及调度的问题，内存空间不足的时候的调度算法）内存管理单元（MMU）负责将虚拟地址转换为物理地址，确保进程间的地址空间隔离。这个时候更新PCB块在内存的位置信息，大小信息，数据段，代码段等的位置，还有一些上下文信息，比如PC值，psw的数值等。还有一点就是要把pcb当中进程的状态改为就绪状态加到就绪队列当中去。

执行进程，CPU首先会读取该进程的pcb的信息到CPU中，有了这些状态，CPU就知道要执行的进程在内存的位置（根据pc的信息）

切换进程，首先要保存当前执行进程的上下文信息，就是CPU各个组件（控制器，运算器部件）的数值到PCB中，把旧进程设置为阻塞或者就绪。这样再读取新的就绪队列上进程的PCB（涉及到进程状态的转换）到CPU上，并把状态改为运行态。

销毁进程，销毁的是PCB，一般不会把内存当中的信息回写到外存，新来的进程直接覆盖。除非内容发生改变！要把信息回写到外存！

2.如何理解内核级线程和用户级线程的区别？

内核创建内核级线程，而进程里面可以有很多的内核级线程，这里的内核级线程是内核空间创建的，只不过内核级线程的空间是被存在进程的线程空间当中去了！进程管不了线程，而进程里的资源被内核级线程使用！

内核不知晓用户级线程的存在，只看到进程本身。所以用户级线程再多，一旦卡住所有都卡住（在单处理器），内核（可以理解内核为OS）只分配给进程资源，具体操作是进程分配给下面线程的，单核中，一旦一个线程卡柱了！那么整个进程的运行都卡住了。

这里内核级线程对应一个进程？这句话不对。首先是OS知道进程的存在，然后会创建内核级线程，比如给了3个内核级线程那么这个进程就可以同时运行三个用户级线程，一个卡了换其他的，进程能正常运行！如果OS不创建内核级线程给进程，那么进程创建再多的线程，卡一个所有的都不能正常运行（并发性很差）

引入线程后进程就不是CPU分配的基本单位了（线程才是处理机分配的基本单位），进程能够执行是依赖于内核级线程的！而每一个用户级线程之所以能够运行根本是也是对应有内核级线程在，OS才会分配给这些用户级线程CPU的使用权！

这个内核级线程和用户级线程还有进程还有OS。可以做个比喻理解一下。

进程比作不复当年风范的爹

内核级线程比作最吊的后代

用户级线程比作最屌的后代的儿子

OS比作有资源的人（这里资源指的是CPU）

当初OS没见到进程的内核级线程的时候，看进程还有点用，就把资源给他了。后来这个内核级线程出现了，觉得利用价值更高把资源都给这个内核级线程了。后来这个内核级线程有了后代，很飞扬跋扈，但是这个OS看在他爹的面子上也给这些用户级线程一些面子！但其实背后里靠的还是他爹内核级线程。一旦他爹g了，那好了，你这个儿子要啥也不可能给你了！你爷爷更不管用，外面的资源就不可能再给你家！

这样这个进程就阻塞了！只有当OS再为这个进程分配内核级线程的时候，这个进程才会继续执行！

OS能感受到进程，能感受到内核级线程，但是感受不到用户级线程就在此。内核级线程共享进程的资源，但调度和管理由内核负责。进程通过用户空间的线程库来管理用户级线程的创建、销毁、调度和同步。

为什么用户级线程一个被阻塞整个进程都被阻塞？归根结底还是内核级线程被阻塞了！

怎么感觉不太对呢？早期的计算机不支持线程，所谓的线程是通过线程库实现的！那这里的一个线程被阻塞整个进程都被阻塞是因为什么？（OS只能感知到进程，但这里的进程把一些操作让线程库分给一些所谓的线程了，这些线程每个人得到一些CPU资源但是不足够）

用户级线程库：提供线程创建、销毁、切换、同步等功能，但这些功能在进程用户空间内实现，不涉及内核。线程切换比进程切换更快，因为没有上下文切换开销（如陷入内核态）

是说，这些线程的切换啥的都没啥问题也可以并发的使用，但是一旦涉及到内核的指令的时候一旦阻塞，整个所有的线程都将阻塞（好好理解，没完）

3.页面置换

时钟置换算法
最佳置换算法性能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好（LRU），是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。
时钟置换算法是一种性能和开销较均衡的算法，称CLOCK算法，或最近未用算法（NRU,NotRecently Used)
CLOCK算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）
改进型的时钟置换算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。如果被淘汰的页面没有被修改过，就不需要执行IO 操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。因此，除了考虑一个页面最近有没有被访问过之外，os还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免l/O操作。
修改位＝0，表示页面没有被修改过；
修改位＝1，表示页面被修改过。
用（访问位，修改位）的形式表示各页面状态。如（1,1）表示一个页面近期被访问过，且被修改过。
算法规则：将所有可能被置换的页面排成一个循环队列
第一轮：从当前位置开始扫描到第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位
第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描
 

 

 

计网AL-TL-NL-DL-PL

Application layer-Transport layer-Network layer-Data Link Layer-Physical layer 

遗忘

 集线器半双工！集中-交往（集线器-中继器；交换机-网桥）

OSI七层，上三资源子网，下三通信子网，中间传输承上启下。   TCP/IP四层
物理层： 规定通信端点之间的机械特性、 电气特性、 功能特性以及规程特性。 
数据链路层： 在不可靠的物理介质上提供可靠的传输。 
网络层： 负责对子网之间的数据包进行路由选择。 
传输层： 负责将上层数据分段并提供端到端的可靠的或不可靠的传输。 还要处理端到端的差错控制和流量控制
会话层： 管理主机之间的会话进程
表示层： 加密解密
应用层： 为应用程序提供访问网络的服务。

TCP/IP 的核心思想是“网络互联”， 将使用不同低层次协议的异构网络， 在传输层、 网络层建立一个统一的虚拟逻辑网络。

2^16=65536

各路由器使用RIP且已收敛啥意思？

OSPF网络层协议不使用UDP或TCP而是直接IP数据报传送，而RIP应用层协议在传输层使用UDP（why）


万维网www服务器第一步是域名解析

功能
应用层

处理特定的网络应用，如Web浏览器、电子邮件客户端等

HTTP 80服务器监听客户请求的端口  HTTPS443 FTP 20/21 POP 110 DNS 53 DHCP 67   RIP BGP SMTP 25

传输层在源主机和目标主机之间建立可靠的数据传输连接，使用TCP或UDP协议来提供可靠的数据传输服务；TCP/UDP
网络层

将数据包从源主机传输到目标主机。使用IP协议进行寻址和路由，以确保数据的正确传输；

ipv4 arp icmp ospf。ABCDE地址，

数据链路层

将数据分割为帧，并在物理介质上进行传输。在直接相连的节点之间提供可靠的数据传输。负责将网络层传递的数据分割成帧，并添加物理地址、错误检测和纠错等功能。可以实现节点之间的直接通信和数据传输。

CSMA/CD（有线） CSMA/CA（无线）IEEE802.3 IEEE802.11

广域网的(PPP HDLC)

传输介质 滑动窗口 11 n1 nn

物理层将比特流转化为电信号，并通过传输介质进行传输。

网络层只需要管理好点对点能传到就行，别的不用管。大部分能传到位即可。传输层管好数据到主机的时候是按照udp还是TCP接受，TCP就是网络层传过来的数据必须有序不错，TCP保证了的可靠连接。UDP是传过来就行

每一个数据报从一台主机发送到另一台主机的过程，如何封装！如何获取目的IP？如何获取目的MAC？如何找到下一跳的IP地址以及IP对应的MAC地址？在同一网段呢？不在同一网段呢？每一步骤使用的协议是什么？交换机是怎么去寻址的？交换机的路由表是怎么构建的？（动态静态！），主机怎么去解封装？主机怎么去判断交付给哪个进程！

数据的每一个阶段的封装，应用层数据到传输层，加TCP首部，到网络层加IP首部，到数据链路层再加一个MAC帧首部和尾部（6624），到物理层转换为01比特流或者幅值在传输介质上传输！ 这些首部的作用都只是为了能够在链路上正确的传播与接受！而真正有用的数据只有应用层一开始要传的数据！传输层加的TCP首部是为了能够正确的传到对应服务器或主机的某个端口（进程），而IP首部是为了可以找到要传的哪一个网络！MAC帧首部是为了实实在在的能找到往哪传！

物理层

问题：模拟信号数字信号区别？会话式通信？时延带宽积（传播时延*信道带宽（最大传输速率b/s）），

补充HUB为100Base集线器线路传输速率100Mb/s以太网交换机（转发速度比网桥快，因为可以采取直通交换方式进行转发决策使用的PDU地址是自的物理地址

电路交换，一次性干完（也就没有中间节点的发送时延了，只有最开始的），要先建立连接
报文交换，拖家带口，一个个目的地找
分组交换，流水线，不像报文对每个网络节点要求缓存大小。
分组分为虚电路（事先建立好连接）跟数据报（乱发，无所吊谓）叫虚电路，是因为逻辑相连的不是真真正正的电路。电路交换这个是实电路，因为双方完全独占其他人谁都不允许用。而虚电路就不同，尽管我俩用这个节点，别人也可以用。虚电路致命问题，一旦前面的分组丢了没按时到达后面全完蛋都不能用了。

假设某信道中的信号功率为0.6W，噪声功率为0.0193W，信道的频带宽度为160MHz，信道的长度为1km，信号在该信道的传播速率为200,000km/s，则该信道的时延带宽积是：香农----最高传输速率=Wlog2（1+S/N）（b/s）=160M×log2(1+0.6/0.0193)=800Mb/s；带宽积=1km/200,200km/s  ×800Mb/s=4000b

主机甲通过1个路由器与主机乙相连，两段链路的数据传输率均为10Mb/s ，主机甲分别采用报文交换和分组大小为10kb的分组交换向主机乙发送一个 大小为 8Mb(1M=10^6)的报文。若忽略传播时延、分组头开销和分组拆装时间， 则两种交换方式所需总时间分别是？
(8Mb/10kb/s)*2=1.6s   ;    (10kb/10Mb)[2+799]=0.801s

1km长的CSMA/CD网络的数据率1Gbit/s 信号在线路上传输的速率是200,000km/s，此协议最短帧长：争用期×数据传输速率=2*（1km/200,000km/s） *1*10^9。最短帧长，一个bit一来一回最迟发生碰撞的时间，超过这个时间就不可能碰撞。这里争用期就是跟传播有关，一来一回的时间，这个时间乘以传输就得这个争用期最短发送多少帧长，一旦低于这个就表明有可能碰撞。

不归零要有一根线传同步信号效率低，所以引入归零。但是归零的自同步效率也低，引入曼彻斯特。 

传输媒体并不是物理层。传输媒体在物理层的下面，因为物理层是体系结构的第一层，因此有时称传输媒体为0层。在传输媒体中传输的是信号，但传输媒体并不知道所传输的信号代表什么意思。物理层规定了电气特性，因此能够识别所传送的比特流。
物理地址称硬件地址或MAC地址，属于数据链路层范畴

数据链路层

滑动窗口与信道利用率；（以太网分组交换技术使用曼彻斯特编码，每位数据（一个比特）对应两个电平（脉冲信号）敌波特率是数据率的两倍）

互联网可以连接不同类型的网络，使用路由器连接（从互联网的角度，广域网和局域网是平等关系）
广域网是类型单一的网络，使用节点交换机连接；以太网是局域网的一种实现形式，逻辑拓扑是总线型结构，物理拓扑是星型

DL的流量控制是点对点，接收端收不下后不发送确认（会有计时器，超时重传）；IEEE
TL流量控制是端到端，接收端需要给发送端一个窗口公告。DL数据丢了无所谓，重传就是了。但是TL的数据丢了需要费很大力气，所以一般需要传一次就最好能接受，所以需要先发一个窗口大小（告诉发送方别发多了）

可靠传输：发送端发送什么，接收端就接收什么
流量控制：控制发送速率，使接收方有足够的缓冲空间来接收每一个帧

滑动窗口机制
1.解决可靠传输：发送方自动重传
2.解决流量控制：在没有收到窗口确认的情况下不发送下一个

通常有线链路距离短，效果好，可以无连接；而无线距离长，质量差，尽量有确认或有连接。
为网络层提供服务为什么没有有连接无确认服务？

以太网使用CSMA/CD(IEEE802.3 有线，提供无连接不可靠服务)；WLAN使用CSMA/CA(IEEE802.11，无线)

DL组帧（NL递交的分组封装成帧）目的是防止数据错误要全部重发，组帧主要解决帧定界、帧同步、透明传输等问题。
组帧时要加首部，尾部，原因是，在网络中信息是以帧为最小单位进行传输的，接收端要正确地接收帧，必须要清楚该帧在比特流中从哪里开始到哪里结束，而分组（即IP数据报）仅是包含在帧中的数据部分，所以不需要加尾部来界定。

DL负责在直接相连的节点之间传输数据：1.帧（DL传输的基本单位）2. 物理地址（MAC地址）因网络设备都有唯一的MAC地址，DL使用MAC地址来标识和寻址网络设备。3. 媒体访问控制（MAC）协议：CSMA/CD（以太网）和CSMA/CA（无线局域网）4. 错误检测和纠错，添加校验位来进行错误检测。5. 流量控制，避免接收方无法处理过多的数据。6. 差错控制：确保数据准确。7. 透明传输，无论数据的内容是什么都不会对传输造成影响。8. PL设备：链路层设备包括网卡（网络适配器）和交换机。网卡负责将数据从计算机传输到物理介质上，而交换机用于在局域网中转发数据帧。

10Mb/s以太网把争用期定为512比特发送时间，即51.2us，因此其总线长度不能超过5120m，但考虑到其他一些因素，如信号衰减等，以太网规定总线长度不能超过2500m

传统局域网的缺陷，缺乏流量隔离：广播流量会跨越整个机构网络（ARP、RIP、DHCP协议）一个单位的不同部门共享一个局域网，对安全不利。引入VLAN（用三层交换机或路由器划分逻辑局域网（子网），缩小广播域）

比特率：波特率是n:1。因为这个n代表着比特的位数（一个码元4比特，那就有16种码元）比特率(bit/s)=4*波特率(Baud)。波特表示每秒传多少码元！比特表示每秒传多少bit（信号传输的速率就是波特率，因为一个完整的码元才能代表一个信号！仔细辨别信号速率，比特率，波特率区别）

 

以太网的信道利用率

假设r是以太网单程端的传播时延。则争用期长度为2r，设帧长为L（bit），数据发送速率为C（bit/s）,则帧的发送时间To=L/C(s)；成功发送一个帧需要占用信道的时间为To+r。
参数a利用率  a=r/To：a越小，以太网的信道利用率就越高。a趋向0时，表示一发生碰撞就可以立即检测出来，并立即停止发送；
参数a的要求：数据率一定时（T0固定），以太网的连线长度受到限制，否则r的数值会变大；以太网的帧长不能太短，否则To的值会太小，使a的值太大；
信道利用率的最大值Smax = To/(To+2r)=1/（1+2a）;To为帧本身的发送时间，To+r是发送一帧占用线路的时间（发送T0+确认r）当参数a远小于1才能得到尽可能高的极限信道利用率；当以太网的信道利用率达到30%（a=7/3）时就已经处于重载的情况了，很多的网络容量被网上的碰撞消耗掉了

有效数据传输率=数据长度/（发送时间+RTT）（b/s）;
数据长度：后退N帧GBN=单个帧（单个分组）×窗口大小；以太网帧是去掉头部信息的18B

最短帧长，最远距离
最小帧长 =  2г（RTT）× 数据传输速率（2r的时间是因为，帧长最迟在刚到接收方就碰撞）
最远距离 (总线电缆最大长度) = 发送时延×传播速率
最大平均数据传输率 = min  {有效数据率 ， 带宽}

为什么字节数最小？

若一个网络采用一个具有24个10Mb/s 端口的半双工交换机作为连接设备，则每连接点平均获得的带宽为多少？该交换机总容量为？
① 对于交换机每个端口带宽相同10 Mb/s
② 对于集线器每个端口平分带宽 
24x10Mb/s全双工；24x10Mb/s×1/2半双工

CSMA-CD确定重传时机一一截断二进制指数规避法
1.确定基本退避时间，一般为2T
2.定义重传次数k，k不超过10
3. 从在[0,2^k - 1]的范围内任取一个整数r， 重传所需要推迟的时间即为： r ＊ 基本退避时间 = r ＊ 2 T
4.当重传16次仍然不成功时说明网络拥挤，抛弃此帧并向上层报告出错 

 CD是冲突检测，一旦有冲突就随机重发，但是不具备确认机制？CA是避免但不能完全避免，CA使用停等实现可靠传输！

PC0和PC1之间传递数据（IP通信）不需要配置网关，PC1与PC2之间传递数据需要配置网关！不在同一个网络下的主机之间通信需要先把数据送到路由器上的网关！两个主机能否进行通信，看要是在同一个网络下，不需要配置网关也可以通信！在不同网络下要配置好网关才可以通信！

注意，有可能两个主机被同一个交换机相连！但是他俩不是在一个网络下（怎么判断是不是在一个网络下？就是让IP与子网掩码相与看网络号是不是一样！）那么也需要配置网关这俩主机才可以通信！

硬件地址固化在电脑上或者手机上，但是ip地址是连的wifi或流量这个局域网分给你的，你连校园网是校园网分的，连WIFI是WIFI分的。Mac地址与硬件绑定，而ip地址是逻辑地址。考试说Mac不能改但实际上是可以改的。

最初只有几台电脑时，两两互联可以够交换数据。但是当电脑多了就不行了，所以引入交换机，所有电脑练这个交换机上。当A给B转发数据是要通过各自的MAC地址来区分的。A先发到交换机，交换机从所有端口转发出去，交换机会自学习。知道1端口是A，只有B回应其他电脑丢弃这个数据。但是每个交换机的端口不够用，所以引入了交换机与交换机相连的结构，但是还不够，不能学习几十万亿个表项，会去学哪个主机对应哪个端口。就引入了路由器（隔绝广播域）

hub无脑所有端口广播。交换机是如果交换表上有目的mac就单播要是没有找到目的mac不管别的端口的目的Mac对不对都发送帧。

路由器每个端口都是一个网络，因此引入了IP地址，通过IP地址就可以在网络内去寻址。这样很灵活！

每一个主机加入一个网络要么静态的配置IP，要么使用DHCP动态的获得IP，不会受到生产厂家，序列号的这些限制。为什么要用IP分成不同的网络而不是MAC地址，就是因为MAC地址受生产厂家以及序列号的限制！最初的构建思路就是先分区进行管理！把数据先分到这个区里，再在这个区里进行转发找到对应的主机！因此要使用MAC进行划分网络的话！那么分区就是通过生产厂家进行分区，再在这个区里找主机！不科学！因为每一个厂家的每个MAC生产厂家一样！一个在北京一个在纽约，如果这俩分成一个区！那这就不能玩了！而IP就很灵活！每一台主机都可以加入任意一个网络只需要分配给我这台主机一个IP即可！（可以解决分拨划分区域的问题了！）

交换机有交换表！路由器也有路由表！默认路由一般会与拓扑图中的互联网同步出现！如果在本台路由器没找到对应目的网络目的主机，就直接通过某一默认路由发往下一跳！后续任务本路由器不会管！但是每一跳对应的生存时间TTL都会减一（16）。路由器与路由器之间的转发是一跳，路由器的直接交付给目的主机这也算一跳（14年TTL设置为64只是经过一次路由器算一跳，也就是直接交付不算一跳！！）

目的地址掩码下一跳端口
A：目的网络 （网络号）通过目的地址和掩码就可以确定对应的网络号下一个路由器的端口的IP地址本路由器往哪口出去！
B：目的主机（具体主机号）
C：默认路由（0.0.0.0）

每台主机都会有一个默认网关（这个默认网关存的是路由器在该网络下的端口对应的IP地址）！如果本主机要转发的目的地址不跟自己在一个网络下！那么就会通过默认网关把数据转发到对应的路由器上的网关？（是叫网关吧！）让路由器去转发分组！如果自己要转发的目的网络跟自己在同一个网络那么就要通过ARP广播找到对应IP对应的Mac地址！（广播请求，单播相应）具体如何判断目的地址是不是跟自己在一个网络就只需要用目的地址的IP与本机的子网掩码相与，结果是不是本主机的网络号！是就代表在本网络，不是就是在别的网络！如果目的地址不跟自己在同一个网络下，就会解析默认网关的IP对应的MAC地址是什么！

ARP广播请求（全一的数据报）单播回应默认网关IP对应的MAC地址，这样就可以封装成帧了，源MAC是本机的MAC目的MAC是默认网关的IP的MAC地址！

访问百度域名！通过DNS找到对应IP地址！应用层数据一层层到网络层！网络层封装源IP和目的IP，再交给链路层！因为不知道目的MAC无法封装成帧！所以需要检测是不是在本网络！不是的话要ARP广播到默认网关转发出去！直到收到回应！封装成帧之后到物理层，物理层不会对帧进行封装只会进行一个转换（转换成模拟信号或者数字信号（01bit流）发送到传输介质上去！）

建立TCP连接的时候头两次是建立连接不带数据！第三次就可以带数据了！同时若一个HTML页面有十张图片！那么需要请求报文有十一次（第一次请求HTML页面，后十次请求外链图片）

默认网关可以理解是主机要连到外面路由器哪个端口的IP地址！默认路由更多是在路由器上！

ARP广播会被路由器隔离！如果目的地址不在同一网络那么就会通过默认网关转发到路由器中！再通过路由器的路由表和ARP表配合找到MAC（第一次的目的MAC就是该网络下主机存的默认网关ip对应路由器的端口的MAC）每个路由器的每个端口都有一个IP一个MAC地址！

MAC变而IP不变

在IP数据报转发的过程中，源IP和目的IP地址不会发生改变，因为IP地址是源主机和目的主机的唯一标识，用于确定数据报的源和目的地。这些地址对于IP路由是固定的

而源MAC和目的MAC地址会在每一跳（路由器之间的跳转）中发生改变，是因为MAC地址是链路层地址，是物理地址，用于在局域网络中唯一标识网络设备。每个网络设备（如路由器、交换机）都会根据源MAC和目的MAC地址来决定下一跳的路径，并在转发过程中更新数据包中的MAC地址，以确保数据包在局域网络中正确传输。

在数据包从源主机到目的主机的过程中，每个路由器都会检查目的IP地址，并根据自己的路由表将数据包转发到下一个跳的目标IP地址。在每个路由器上，源MAC和目的MAC地址都会根据链路层的协议（如以太网）进行更新，以便将数据包正确地发送到下一跳。

虽然源和目的IP都不变，但是IP地址不能唯一区分下一跳的地址是谁！还是要知道IP后以及对应IP的MAC后，才能知道下一跳是要转发给哪个IP，最底层还是这个MAC地址。因为每个设备的IP都是可以变的！但是MAC不会变化！可能上一次通过路由器B的时候这个IP是192.168.2.211下一次再通过是192.168.2.222。尽管IP不一样，但是知道B的MAC不变，还是通过MAC转发！物理层设备不知道什么IP地址，只知道MAC地址。

交换机和路由器找下一跳的区别就在于！路由器是找下一个IP和端口！（根本还是找MAC），而交换机找的是下一个MAC地址！路由器是将数据包转发到不同网络之间的设备，而交换机是在局域网内部进行数据包转发的设备。路由器使用目的IP地址来决定下一跳，而交换机使用目的MAC地址来决定转发路径。

分析一下从A到F的数据转发的具体细节过程！

转发表（二层设备：交换机） MAC地址+接口
ARP表（三层设备：主机，路由器）IP地址+MAC地址+接口
路由表（路由器） 目的地址+子网掩码+下一跳+接口

路由器既有路由表又有ARP表，当进行数据转发的时候，路由器参考哪个表?

会参考路由表（Routing Table），而不是ARP表。 路由器是根据目的IP地址来决定下一跳的路径，并将数据包从源网络转发到目的网络。它使用路由表来存储网络的路由信息和路由决策。路由表包含目的网络的网络地址及其相关的下一跳地址、出接口等信息。 当路由器接收到一个数据包时，会检查数据包的目的IP地址，并根据路由表中的路由信息来确定下一跳的路径。一旦找到下一跳（这个找到，有可能在本网络也可能不在，不在就返回默认路由MAC，送走），路由器会利用ARP协议来获取下一跳的MAC地址。在此过程中，路由器会发送一个ARP请求广播，以获取下一跳的MAC地址，并将其添加到数据包的帧头中，然后再将数据包转发到下一跳。 因此，路由器在进行数据转发时，先根据路由表进行路由决策，确定下一跳的路径，然后根据ARP协议在数据包转发过程中动态获取下一跳的MAC地址。ARP表等在数据转发过程外部用于缓存（关机或者定时清理）主机的IP地址与MAC地址映射关系。

路由表决定从哪个端口出发，而ARP表决定我到下一跳的MAC地址是什么！归根到底还是只能通过MAC地址才能完成数据的转发！因此主机也必须有ARP表，我要知道我的下一跳的目的MAC

RIP和路由表相互配合的过程，就是定期本路由器会收到相邻路由器发来的RIP数据包！通过我自己的RIP算法（三个！没有的填上，下一跳一样的不管变长变短都更新，下一跳不一样的比较一下谁短用谁的！）就会有很多个RIP表项【目的网络+接口+跳数】，等到本路由器要转发数据的时候，会看我的RIP表看我从哪个口出去经过的跳数最少！从这个接口发出！这时候要看自己的ARP表了，我要发的这个下一跳的IP地址对应的MAC是多少！有的话就直接转发！没有的话，会在这个A~~~B路由器之间的网络发一下ARP广播，都不回应，这个时候只有B的默认网关回应MAC地址（默认网关）这个时候就把数据从A路由器通过MAC帧转发到B路由器！

很像MAC地址是物理结构而IP地址是逻辑结构！用户能看到的是IP地址，而实际上传输的时候是根据物理地址来的！

MAC 地址6个字节组成。前3个字节表示厂商识别码，每个网卡厂商都有特定唯一的识别数字。后3个字节由厂商给每个网卡进行分配。

路由表是一个三层交换设备，就是路由器可以把接受的数据报01比特流组成对应链路层的帧再拆开找到对应的网络层的IP数据报，基于这个目的IP地址往哪条路走！

IP和MAC变化
1.每一跳，包括从主机到路由器、路由器到主机、路由器到路由器都是一跳！每一跳都会有源MAC和目的MAC的转换（因为MAC地址要去找我的下一跳应该给谁？）
2.所有链路源目的IP均不变。遇到NAT路由，修改源IP为NAT出接口的IP
3.广播时，目的MAC：FF - FF - FF - FF - FF -FF。DHCP时，由于无目的IP，置IP全1：255.255.255.255

HTTP报文分为请求报文&响应报文
请求报文：1.请求行：请求方法 （常用get/post）、请求URL、 HTTP协议版本 2.首部行 3.请求体/实体主体
响应报文：1.状态行 2.响应头部3.响应体

UDP数据报：首部8B，由4个字段组成 （都是2B）；长度字段包括首部+数据部分；检验和检验首部+数据部分 （可选）

TCP报文段
1.首部固定部分为20B，最大值为60B （和IP分组一样)；源端口和目的端口各占2B
3.序号 （本报文段第一个字节的序号）和确认号（期望收到下一个的序号）各占4B
4.数据偏移=首部长度（4B整数倍）
5.确认位ACK、同步位SYN、终止位FIN什么时候为0/1
6.窗口字段表示允许对方发送的数据量 （流量控制用）

与传统共享式局域网相比， 使用局域网交换机的交换式局域网为什么能改善网络的性能和服务质量？

传统共享式局域网的核心设备是集线器， 而交换式局域网的核心是以太网交换机。使用共享式集线器的传统局域网中， 在任何一个时刻只能有一个结点通过共享通信信道发送数据。而在使用交换机的交换式局域网中， 交换机可以在它的多个端口之间建立多个并发连接，从而实现了结点之间数据的并发传输

以太网适配器（网卡）工作在数据链路层，实现介质访问控制(MAC)和物理层的功能。

在 MAC 层可以：

发送时将数据组装成带有地址和差错检测段的帧；接收时拆卸帧，执行地址识别和差错检测；管理链路上的通信，执行 CSMA/CD

在物理层可以：

信号的编码/译码；前导码（前缀）的生成/除去（用于同步)；比特的发送/接收。

网关： 工作在网络层以上， 作用是实现协议转换


网络层

总结：归根到底还是IP，数据的传输过程！有交换机，路由器，Internet，默认网关，默认路由（不熟悉），RIP和OSPF区别，ARP，路由表，下一跳，接口，广播单播，特殊IP，私有IP，分片，MTU，聚合，子网，变长划分（哈夫曼树）
过程：RIP距离向量算法过程！最长匹配前缀，子网，超网，CIDR（无分类编址）

不希望传输层TL处理太多的事情，只需要服务好应用即可，实现应用到应用的通信，而实际的传输功能就交给网络层NL

ARP因为“看到了”IP地址，所以它工作在网络层，而NAT路由器因为“看到了”端口，所以它工作在传输层。

若NAT路由器拥有n个全球IP地址则内部专用网内最多可以同时有n台主机通过该路由器访问因特网

网络控制应用程序的接口（北向API）---北控；通信层（南向API）--男同
SDN控制器与网络控制应用程序的交互都要通过北向API接口

路由选择协议，

内部网关IGP：RIP OSPF

外部网关EGP：BGP（应用层的协议，不传数据，只是规定自治系统之间如何传输数据）

IPv4 IPv6

IP协议主要包含三方面内容：IP编址方案、分组封装格式及分组转发规则 ①虽说借助子网化、无类寻址和NAT技术可以提高1P地址使用效率，因特网中P地址的耗尽仍然是一个没有彻底解决的问题；②IPv4设有提供对实时音频和视频传输这种要求传输最小时延的第略和预留资源支持；③IPv4不能对某些有数据加密和鉴别要求的应用提供支持。为了克服这些缺点，IPv6被提了出来。

其他协议

ARP地址解析协议

DHCP动态主机设置协议

ICMP互联网那个控制消息协议 ICMP报错报文和ICMP报告报文

IGMP组播协议

路由器直接交付这一步跳数不是0是1

最初是有分类的ABCDE类的IP地址，后来因为一个A类地址太多主机了，引入了子网划分，使用子网掩码来对原网络中主机号的借位，为了让编址更加的灵活，不写什么ABCDE类地址，就引入了CIDR无分类编址！

定长/变长子网划分（对主机号划分不改变网络号）

IP数据报分片：标识标志片偏移，对于片偏移只计算数据部分不带头20，DF（Don‘t Fragment）0可分，MF1还有片。 片偏移（始终是8的倍数！）最初MF=1 DF=0 最后一片MF=0 DF=0
某IPv4数据报的首部中， 包含有3字节长的可选字段则填充字段的长度和首部长度字段的二进制值分别是多少？
固定首部是20字节！可选字段3字节， 填充字段要1字节（这样才满足首部长度是4的整数倍），所以首部长度是20+4=24B=0110（长一首四偏八，6*4=24）
注意首部长度最长可以20+40=60（1111=15*4）

子网掩码（使用子网掩码来表达对原网络中主机号的借位，与后得网络号）

路由聚合成超网需要匹配最小公共前缀！这样可以减少路由表项。

网络拓扑图一旦出现互联网，就是路由表项会有默认路由

通常情况下一个路由器的一个端口下是一个网段！在这个网络下的所有的主机都可以相互通信！但是也有子网划分的可能！这样的话不同子网之间通信必须通过路由器进行转发！要先把数据传到路由器再由路由器传到另一个子网。P158（2016真题）

对子网号的叫法，比如最初/24 /16 /8这些都是标准固定的网络号，突然进行划分了，比如/25,/28这种的！192.168.2.0/.25这个网络的子网号是0，192.168.2.172/26这个网络的子网号是11，也就是说，子网号111，110，1110101，不管是啥样式的！定了就不能变！

MTU是最大数据传输单元！以太网传输的数据部分最大是1500B，因此以太网传输的最大IP数据报就是64~1518B，最小的数据就是46B 因为首部为18B（6+6+2+尾4）这是对MAC帧的限制！而IP数据报的首部加数据就是MAC帧的数据部分

考研过程中是不需要考虑交换机的MAC地址的！只有经过路由器后的mac会发生变化而经过交换机的MAC是不发生变化的（也好理解，交换机肯定是有MAC地址的，不然咋把数据传递过去的！）

路由

        静态路由 手动写（下一跳，出去的端口，目的网络）

        动态路由 RIP（相邻交换，三原则）

转发

        目的网络：匹配就直接交付 不匹配就间接交付送到下一跳，不匹配就由默认路由处理，没有默认路由那就丢弃（路由不可达）

        路由表项的匹配原则就是最长前缀匹配。

私有IP地址
A类1个网段--10.0.0.0~10.255.255.255
B类16个网段--172.16.0.0~ 172.31.255.255
C类256个网段 --192.168.0.0 ~ 192.168.255.255
目的地址是全1路由器也不转发；路由器对目的地址是私有IP地址的数据报一律不进行转发。

路由表这些目的地址下一条的这些信息的维护就是通过路由协议来维护的：RIP OSPF BGP

组播（多播）不产生ICMP差错报文；组播地址只能作为目的地址；源地址只能为单播地址；UDP连接，不可靠！

主机名与 IP 地址的映射， 需要使用域名解析系统 DNS。

当用户程序需要将域名（主机名） 解析为 IP 地址时， 就通过本地主机的地址解析器， 先向本地域名服务器发出询问， 是否是本地域名； 若是， 便进行本地解析； 否则查高速缓存， 看最近是否解析过； 若是， 则将查到的 IP 地址报告本地主机的地址解析器； 否则，访问远程域名服务器， 使用递归查询或者迭代查询的方式， 向根域名服务器、 顶级域名服务器和权限域名服务器发出请求。

DNS 是应用层协议， 用来请求域名服务器将连接在因特网上的某个主机的域名解析为 IP 地址， 用于广域网。
ARP 是网络层协议， 它采用广播方式请求将连接在本以太网上的某个主机或路由器的 IP 地址解析为以太网硬件地址， 用于局域网。

 

 

 

 这是因为集线器和中继器没有识别帧的能力只能无脑转发！

 

 

 

 

 

 

传输层

点到点通信为端到端通信提供服务，传输层为第一个端到端通信

网络层是为主机提供逻辑通信，而传输层为主机上的进程提供端到端的逻辑通信
复用：AB两个不同应用进程可以使用同一个传输层协议传输数据；
分用：传输层从网络层收到数据后交付指明的应用进程
传输层对收到的报文进行差错检测（同样需要注意：网络层，只校验首部是否差错，而传输层需要对报文进行差错检测

DNS传输层协议 使用 UDP 而不是 TCP（没必要可靠，丢了重新发）

主机如何访问www.baidu，那些顶级的，，，，

TCP报文段在发送的时候是有缓存的！但如果有些字段的URG是1就是紧急发送的话！那就要优先发送这个URG为1的报文

从发送HTTP请求报文开始到收到全部内容为止，所耗费的时间是。这个是不包含建立的，如果说从建立的第一个请求报文开始那就包含建立的rtt

为什么叫TCP段，是因为上层交付的数据，在传输层分成一个个段发送出去！

序号是自己开头发的，比如我第一个段连续发送100B的数据，那么我这个TCP段的序号就是0，而第二个段的序号就是100。

而ack确认序号是对对方的确认，比如对方发给我200B数据从100B开始，所以我发过去的确认号ack是（100B+199B=299B这个是我收到的那么多，但我要发过去ack=300，意思是我收到了300以前的（0-299B我都收到了！），请你发300及以后的数据！）

TCP全双工的，我发送过去对方也在发回来！

seq序号是自己的，ack确认号是对对方的确认，可以相同但是表达的含义不一样！

滑动窗口控制发送方发送的数据的大小！链路层的滑动窗口以帧为单位，而传输层是以B为单位！

这个滑动窗口需要使用到操作系统里面讲的单缓冲，双缓冲，循环缓冲的概念！

客户机最短释放时间 1RTT + 2MSL，服务器最短释放时间 1.5 RTT（即断开连接时，接收方无数据传送，即少了0.5个RTT）

流量控制是指A和B之间的！而拥塞控制是指整个网络的！路由器就像是一个交通枢纽！每个主机发送数据就像是车，车太多了，路由器就把车都丢了！

一个过程叫传输轮次！这个·每一轮都会指数增长，就是每得到一次ack回应，cwnd就加一。因此第一次cwnd=1，得到一次回应cwnd=2，再发俩，cwnd=4，，，，，就俩算法，慢开始和拥塞避免算法！

TCP与UDP区别联系。

TCP面向连接，发送方发数据要先建立连接！然后发一个数据要等收到接收方的确认信号才能发下一个！确保信息的准确送达！发送完后还要关闭连接！适合在发送文件的时候！

UDP，不需要建立连接，无连接尽最大努力交付！可以一下子发完！不需要建立连接。适合在视频通话过程！不需要太高的画质凡是要求延迟低！


TCP无网，Osi面传

之所以OSI与TCP模型不同！就在于OSI在网络层就设计出面向连接的虚电路服务以及面向无连接的数据报服务！（虚电路面向连接的，IP数据报面向无连接！）但是这给网络层的路由器压力很大，所以TCP/IP模型下，网络层只需要无连接，简单灵活，尽最大努力交付的数据报服务即可！因为计算机本身的强大算力，以及纠错能力！当数据报来了时候，我在端（计算机）这边再去实现面向连接与无连接的服务会大大节约成本！就是说，你网络层数据丢就丢了！我计算机能知道哪些丢了！你只需要尽最大努力给我就行了！至于丢的我再去要求重传！

TCP面向连接可靠，UDP面向无连接不可靠！那为什么还有网络层的无连接的服务？到底听谁的？根据谁的服务来传输数据?

TCP提供面向连接的服务意味着在通信前，发送方和接收方要先建立一个连接，之后才进行数据的传输。在传输数据时，TCP使用序号、确认和重传机制来保证数据的可靠性。每个数据包都有一个唯一的序号，接收方通过确认序号告知发送方已正确接收数据，并且发送方会对未收到确认的数据进行重传。

网络层提供的是无连接的服务，也就是说在通信前不需要建立连接。这使得网络层的数据传输更加高效，但不保证数据的可靠性。当一个数据包从源主机发送到目标主机时，网络层使用IP协议将数据包传递给下一跳路由器，而这个传递过程是无连接的，没有确认和重传的机制。

数据在链路上传递时是不可靠的，因为网络层没有提供可靠性保证。但是，当数据被传递到传输层的TCP协议时，TCP会提供可靠的传输服务，确保数据的完整性和有序性。在涉及数据的可靠传输时，应该听取TCP协议的可靠传输机制。而网络层提供的无连接服务则更注重传输的效率。

网络层传输不需要可靠，但是到了传输层要求按顺序到来！要求可靠！

应用层

HEAD读取调试，但不返回请求对象
IP分组经路由器转发：需要修改那些头部信息（1）分片影响总长度，标志，片偏移（2）路由器转发生存时间TTL-1，头部校验和（因TTL变化而变化）（3）私网地址影响源IP地址一定变化若为公网地址，则不变化；目的IP地址根据到达网络是否为公网还是私网判断，判断原则如上

DHCP

要是没有DHCP服务器，电脑要手动配置ip地址，子网掩码，默认网关，DNS服务器IP地址。会有可能出错。所以建一个DHCP服务器，每次电脑开机都会自动启动DHCP进程，动态从DHCP服务器获取这些信息。性能高。DHCP是TCP/IP中的应用层协议使用传输层的UDP服务，DHCP服务器使用的UDP端口67，DHCP客户使用的UDP端口68

主机要ip的过程有四部分，客户找DHCP，服务器提供IP，客户接受IP，服务器确认你接受IP。

提供IP的时候服务器要ARP确保提供的IP没被占用。客户使用IP的时候（第四个步骤结束后）也会ARP看有没有被占用。

因为不愿意在每个网络下都设置DHCP服务器所以会给路由器配置DHCP服务器的IP地址。这样不同网络的主机想要获得IP就直接四个步骤就可以了。有点不同的是，当本网络主机发送DHCP广播报文的时候路由器接受这个报文后单播发送给DHCP服务器。这时候这个路由器被称为DHCP的中继代理。

FTP基于的传输协议是 TCP

控制21数据20，这是FTP服务器中主动连接FTP客户的时候的端口号

但当FTP服务器被动的连接FTP客户的时候就是FTP客户主动连接FTP服务器，服务器端控制端口还是21但是数据端口对于客户和服务器都是随机的临时端口。

总之不管主动被动连接，客户端的端口号都是随机的，而变化的只是服务器端的端口号，当服务器端主动连接时控制21数据20，当服务器端被动连接控制端口21数据端口协商随机的。

控制一直开，数据通道传输时开不传输时就关。

电子邮件

客户SMTP通过TCP连接发送数据到发送方邮件服务器的SMTP服务器（进程），发送方的邮件服务器使用SMTP客户（进程）把数据通过TCP连接使用SMTP发送到接收方邮件服务器的SMTP服务器（进程）。接收方邮件服务器使用POP3服务器（进程）把数据通过TCP连接使用POP3读取邮件读取到接收方的用户代理的POP3（进程）

四个东西：发送方用户代理 发送方邮件服务器 接收方邮件服务器 接收方用户代理

基于万维网的电子邮件，就不需要下载邮件服务器到本地，可以直接使用基于万维网的电子邮件也就是登录QQ邮箱，客户通过http协议连接到服务器。就不需要之前的SMTP和POP3协议。这是对于俩人都是QQ邮箱

如果是A使用qq，B使用网易。那就是A通过HTTP与QQ邮箱服务器建立连接，B使用HTTP与网易邮箱建立连接，而QQ与网易之间使用的还是SMTP连接

如果电子邮件包含非ASCII码数据需要MIME转换成ASCII才可以发送。

万维网

http/1.0传一个文件后就断开，请求一个万维网文档2RTT+文档传输时延（第一个RTT是建立连接，第三次发送http请求报文也就是带了数据。）

虽然 HTTP 使用了 TCP， 但 HTTP 协议本身是无连接的， 也是无状态的， 这样可使读取网页信息完成得较迅速。
 

http/1.1，持续连接不断，流水线可以多个HTTP请求报文，依次响应，使得TCP连接空闲时间少。

15年考的一题尽管是http/1.1也可以使用非持续连接，但大都使用keep-alive。如果connection：close尽管是http/1.1只是说明这个使用的是非持续连接而已。

Internet 上提供客户访问的主机一定要有lP地址
递归查询：（主机所询问本地域名服务器不知道被查询的域名的IP地址，那么本地域名服务器自己变为DNS客户）此时主机和本地域名服务器发送的域名请求均为1
注意形式为www.abc.xyz的网站，根域名服务器1；顶级域名服务器（）1；权限域名服务器（xyz;abc.xyz)2.所以此时最多1+1+24次DNS查询
授权域名服务器一定能够可以把主机名转化为主机的IP地址 

 

题目

1、网络P地址空间为192.168.5.0/24，采用定长子网划分，子网掩码为255.255.255.248。则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是

192.168.5.0/24讲明了网络号24位，以及子网号跟主机号是后八位。 255.255.255.248讲明了248=11111000，说明子网号为24+5=29，因此主机号3。 所以可分配子网个数：2^5=32，主机数2^3-2=6（全一表示网络，全零表示广播）

再补充一点，这个网络能够分配的地址个数 32×6=192

子网掩码

1 对应网络前缀（网络+子网位） 0 对应主机位

可以看到这个C类地址，经过子网划分后可分配的是192个。但是要是不子网划分的话，可分配的是2^8-2=254个，少了64个用在了各个子网的网络地址和广播地址。因此可以说子网划分有利有弊！方便对网络管理，但是少了可分配地址！

2、在子网192.168.4.0/30中，能接收目的地址192.168.4.3的IP分组的最大主机数为多少？2

在这个子网中，能作为主机地址只有两个，192.168.4.1。 192.168.4.2 因为192.168.4.0是表示本网络号，192.168.4.3是广播地址！所以说目的地址是广播地址的话就表明在这个网络下的所有的主机都可接受！所以为2 但要是192.168.4.0/24的话，目的地址为192.168.4.3，能够接受这个IP分组就只能是一个，因为这个不是广播地址！

3、某主机的IP地址为180.80.77.55，子网掩码为255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是

DS

一个算法（“穷人”）：很穷（有穷性），且确定（确定性）自己正确（可行性），没有输入全是输出；
标准的好的穷人（算法）：多了几本书的（可读性），身体还好（健壮性），就确定自己是对的（正确性），还想要的很多（高效率的得到低存储的消耗）

逻辑线性：推广的线性表：数组；受限制线性表：栈，队列，串；一般线性表：顺序表，链表
逻辑非线性：集合，树，图

物理：顺序存储；链接存储（指针，引用）； 索引存储（附加索引表建立 key 与地址的映射）； 散列存储（ 由 key 可直接计算地址）（后三者非顺序存储）
散列存储不需要存储索引表，但是索引存储（比散列更快！）需要，例子：中文有那么多汉字，但是一次会议只需要一小部分汉字，如果使用索引存储会浪费很多空间，但是散列就只需要构建使用的这些汉字的关系就行！

int m=0,i,j;
for(i=1;i<n;i++)   // i执行n次
    for(j=1;j<=2*i;j++)
        m++;
// 执行次数：2,4,6,8,2n（求和：n(2+2n)/2  O(n^2)）

int i=0,j=0,sum=o;
while(sum<n)  sum+=++j;

// sum=  0+1, 1+2,1+2+3,1+2+3+4,,,,    
k(k+1)/2=n 所以O(√n)

int x=0;
while(n>(x+1)*(x+1))  x=x+1

1 2^2 3^3 4^4 k^k
k^k=n    O(√n)

int i=n*n;
while(i!=1)  i=i/2

t=0     1      2       3        i
i=n^2 n^2/2 n^2/2^2 n^2/2^3    n^2/2^i 

n^2/2^i=1  i=2logn   O(logn)

线性表-串-数组

  1. 顺序存储的线性表，设长度为n ，在任何位置上插入或刪除操作都是等概率的。 刪除一个元素时平均需要移动表中的几个元素。（0+1+,,,n-1）/n。插入（0+，，，，+n+1）/n
  2. 静态链表，不支持随机存取必须从头往下找；
    插入：①找到一个空的结点，存入数据元素②从头结点出发找到位序为i-1的结点③修改新结点的 next④修改i-1号结点的 next
    删除：①从头结点出发找到前驱结点②修改前驱结点的游③ 被删除结点 next 设为 -2
  3. 单链表的头插法，尾插法，判空（看有头无头，有头是L->next=null，无头）
  4. 循环双链表：在哪插在哪删都一样
    p结点之后插入s结点  s->next=p->next ;  p->next->prior=s;s->prior=p; p->next=s
    删除p 的后继结点q：p-> next=q->next;q->next->prior=p; free(q)
    判空：L->next==L

 

next 的改进版nextval


模式串   a b a a b c a c
next值   0 1 1 2 2 3 1 2
nextval  0 1 0 2 1 3 0 2

nextval 的计算方式
1.第1位写0
2.第2位 若与第1位 相同为0，不同为1
3.从第三位开始根据next值往前找下标所指位置
相同则= 别人nextval值
不同则 =当前next值

n个不同元素进栈，出栈顺序卡特兰数Cn/2n   *(1/(n+1))

树

已知一棵完全二叉树的第6层 （设根为第一层）有8个叶结点，则该完全二叉树的结点个数最多是 (111第六层满，然后留8个叶子). 最少是 ( 39)。如果说只有6层的完全二叉树那么只可能39

哈夫曼树不唯一（所有叶子都不一样时候唯一），不存在度为1的节点（严格K叉树），节点总数2n-1（n是初始节点也是叶子节点）WPL唯一，利用哈夫曼编码（变长编码），有利用字符频率编码（左0右1根本还是哈夫曼树的构造）

二叉排序树

左根右，中序遍历得到递增序列！删除过程Z节点是叶子直接删除，结点Z只有一棵左（右）子树，让Z节点子树成为Z父结点子树 。结点Z有左右两棵子树 ，令Z的直接后继（前驱）代替Z，再删除该直接后继（前驱）。删除一个节点再插入这个节点得到的二叉排序树可能不一样！

基于邻接表的深度优先搜索生成树不唯一只有基于邻接矩阵才唯一

线索二叉树

  1. 线索二叉树： n 个结点的二叉链表中有 n+1 个空指针

  2.  

平衡二叉树

AVL什么都可能，删除再插入相同元素，位置可能一样也可能不一样。

时间复杂度BSTAVL红黑树
查O(n)O(logn)O(logn)
插O(n)O(logn)O(logn)
删O(n)O(logn)O(logn)

 

 并查集

 想·

图

  1. 无向非连通图最多有 （）条边，
  2. 图是需要辅助空间的，空间复杂度O(N)
  3. 图的广度优先，深度优先：无向图的DFS/BFS调用次数=连通分量数；有向图的强连通图，只用1次DFS/BFS调用
  4. AOV(Action on Vertex)网（顶点表示活动，AOE是边表示活动顶点表示事件）一定是DAG（(Directed Acyclic Graph)有向无环图）
    拓扑排序：从AOV网中选择一个没有前驱（入度为0）的顶点并输出，从网中删除该顶点和所有以它为起点的有向边。3.重复，直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（也就是有可能，有多个入度为0的节点，但是拓扑排序扫不到这些只能找一个）逆拓扑反着来
  5. 拓扑排序其实就是对一个有向图构造拓扑序列的过程，拓扑排序只存在于有向图中。
  6. 最小（代价）生成树 MST (Minimum-cost spanning tree )，一个连通图的生成树必有 n-1 条边，且这些边不能构成环路；带权图的 MST 不是唯一的；Prim（有i先找点），kruskal找边，都属于贪心( Grady )算法

BFSDijkstraFloyd
无权√√√
带权×√√
带负权××√
带负权回路×××
时间复杂度O(n^2)O(n^2)O(n^3)

AOE(Action on Edge)网，先画出关键路径（13456=12）要找哪个余量最大或能够最晚多久开始就跟关键路径上的对比就行，这里关键（1346）
找1→2最晚以及余量，123中，13是5，1最晚要完成1-2的2个时间以及2-3的一个时间故（5-2-1=2）1→2最晚2就要出发了不然就耽误时间了。
2->3 (5-2-1=2s，歇2s到4s出发)；
2->4(关键路径上的8-3（d）-2（a）=3。说明2传4的时候可以歇3s，到5s出发)；
3->6（12-g-b=12-1-5=6，也就是歇6s到 5+6=11s出发）
3->5（12-j-f-b=12-1-4-5=2s，歇2s到7s出发）
5->6(12-j-f-b=12-1-4-5=2s,歇2s到11s出发)，留意一下这个5出发是要等到4送来，4最早9s到，但这题没影响

查找 ASL（average search length）

B,B+,RBT,排序树，AVL，散列，折半，分块，顺序

  1. 二叉排序树BST的中根是递增序列（查找效率最好logn，最坏n全是右子树）
  2. 分块：用“索引表”保存每个分块的最大关键字和分块的存储区间，先查索引表 （顺序或折半）再对分块内进行顺序查。块内无序，块间有序。对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在low>high，要在low所指分块中查找。若low超出索引表，查找失败
  3. 折半查找（要有序）元素n个树高log2（n+1），时间复杂度log2小n

  4. 折半，二叉排序树，平衡二叉树，B树的查找时间复杂度都是log2小n；m阶B+是log小m大n
  5. 二叉排序树插入不需要翻转，故不是平衡树；删除时是叶子直接删，不是叶子
  6. 平均查找长度与填装因子（即表中记录数与表长之比）有关在开放定址的情况下，不能随便删除表中的某个元素（只能标记为删除状态），否则可能会导致搜索路径被中断

  1. m阶B树：不管是根还是其他，子树最大最小都比关键字的最大最小多1
  2. m阶B+树：根节点非页节点关键字【2，m】  其他节点非页节点关键字【┏m/2┓，m】，叶子结点的关键字就是1
m阶B树根节点其他节点
关键字min1┏m/2┓-1，省的不平衡
关键字maxm-1
子树min2┏m/2┓
子树maxm

B树

红黑树 是二叉排序树

目前最详细的红黑树原理分析（大量图片+过程推导！！！） - 西*风 - 博客园 (cnblogs)

1.叶结点 （外部结点、NULL结点、失败结点））均是黑色的（根页黑）
2.不红红
3.黑路同（故只含有黑节点的RBT为满二叉树）

红黑树，红叔染色即可，黑叔出现就要旋转了（一种可能是不平衡或者就是普通要旋转！）

排序

插入排序（希插插）：直插，折半插，希尔插；
交换排序（快冒泡）：快排，冒泡；
选择排序（选择堆）：选择，堆排序
基数+归并（这俩都稳）

大小根堆的插入差不多。都是从层序遍历的最后一位插入。然后依次往上进行调整。直到符合要求，删除是输出堆顶元素，之后层序的最后一位顶替上堆顶，然后再调整。调整是俩孩子比较（加入小根堆），谁小谁再跟父节点比较。而不是父节点分别与这俩子节点比较


插帽龟，统计鸡（插入，冒泡，归并，桶排序，计数，基数，都很稳故别的都不稳）
插帽龟喜欢插堆起来的帽子，统计鸡喜欢加加乘（n+k，n+k，n*k）
有一天插冒龟在选择帽子插（选择冒泡插入）的时候，n性长老脸方（时间复杂度n^2）了。恩老（这仨都是nlog2n）大叫快点归还给堆（快排归并堆排序）
插入就可以理解在一点点摸牌，新牌插入有序的里面；快排是已经拿完所有牌了在理牌；
特殊记，快排时间是nlogn空间logn，归并时间nlogn空间n（因为要分而治之，原来多少元素就要开多少空间），统计鸡是时间加加乘，空间加加加。希尔n^1.3。其余空间都是1，

考试桶排序计数排序没了。统计鸡只剩鸡了

堆排序自底向上逐步扩大，将各子树局部均调整为堆；针对每一个元素单独的删除或者插入的时间复杂度是O(log2 n)，自然对于所有的元素的时间复杂度均为 O(n*log2 n)

交换类排序和选择类排序在每轮排序后，已处理过的元素所在的位置即是最终有序状态下的位置；而插入排序和归并排序没有这个特点
n 较小 —— 直接插入或简单选择
关键字基本有序 一一 直接插入或冒泡
n较大 一一 快排，堆排，归并排序
n很大，记录关键字位数较少且分解一一 基数排序
记录信息量大 一 链表存储

快速排序在序列已经有序（正序或逆序） 时为最坏情况，而其它方法一般是正序为最好情况，逆序为最坏情况

堆排序：大小根堆是完全二叉树（这样节省空间，且数组存储），输出根节点后是最后一个节点顶上去后面依次调整。

希尔：增量分组，每个分组插入排序。就是关键在于理解每个间隔怎么算：A B C D E F G H I J K L M N（如果说间隔为4，A E I M）

基数排序，关键字（个十百千）从左到右每个桶按照队列进出（在比较个位数时候先找到329后找到839等出来的时候是329先出）

归并排序(外部排序一般用归并，大文件的时候)，分治，每个分治也是插入排序

外部排序比较好的：408数据结构学习笔记——外部排序_考研外部排序笔记-CSDN博客

本文标签： kaoYan

版权声明：本文标题：kaoYan-408 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732463305h1538676.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。