计算机中的相关知识点(较杂)
注：为了面试将计算机底层知识进行相关复习
计算机的由来
(听的是马老师的公开，讲的计算机的底层，但是课程较短)
cpu制作过程：沙子+铜+胶水+特定的工艺+特殊金属
沙子脱氧-》石英-》二氧化硅-》提纯-》硅锭-》切割-》晶圆-》涂抹光刻胶-》光刻-》蚀刻-》清除光刻胶-》电镀-》抛光-》铜层-》测试-》切片-》封装
计算机的发展：
硅-》加入特殊元素-》P、N半导体-》PN结-》二极管-》场效应管-》逻辑开关
逻辑开关实现：与门、或门、非门（异或门）进而实现加法器，借助内存存储指令控制硬件
(图片来自马士兵课堂的ppt)
ALU计算单元，PC存储指令当前的地址
计算机中各种存储器存取速度：
| 需要cpu周期 | 大约需要时间 | |
|---|---|---|
| 主存 | 约60-80纳秒 | |
| QPI总线传输 | 约20ns | |
| L3 Cache | 约40-45 cycles | 约15ns |
| L2 Cache | 约10cycles | 约3ns |
| L1 Cache | 约3-4 cycles | 约1ns |
| 寄存器 | 1 cycle | 仅次于cpu |
一个cpu多核，每个核有自己的L1、L2缓存，共享L3缓存。
计算机的底层的缓存：
缓存一致性协议：一个cpu中的缓存经过修改(modified)那么就需要通过总线通知另一个cpu或者是另一个核与之相关的缓存设置为无效(invalid)，底层通过缓存锁来实现缓存的数据的一致性。
相关的名词解释：
MIPS(Million instructions per second):每秒处理的百万级的机器语言指令数
CPI(cycle per instruction)：每条指令执行时所花费的平均时钟数
IPC(Instruction per clock)每个时钟周期平均可执行的指令数量
MFLOPS(Million Floating - Point Operations per Second)每秒百万个浮点操作
GBN：后退N帧协议传输数据
FCFS：先来先服务
HRN：最高响应比优先
SPF：短作业优先
HPF：基于优先调度算法
ARP协议的功能：根据IP地址查询MAC地址
CSMA/CD：带冲突检测的载波侦听多路存取
SMTP：邮件传输协议
PPP：点到点协议
IP：网络间相互连协议
FTP：文件传输协议
FDDI：双环令牌传递拓扑结构
SDU(服务数据单元)：层与层之间
PDU(协议数据单元) ：同层之间
Seek time：寻道时间
Rotational delay 旋转延迟
Actual data transfer time 实际数据传输时间
Mutex：互斥锁
rdlock：读写锁
cond：条件变量
Semophone：信号量
数据库的相关笔记简单梳理
mysql中实现的四种通信协议：
TCP/IP协议、Unix Socket协议 、share Memory协议、Name Pipes协议
数据库的模式：是数据库全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图
1.内模式：
又称存储模式，一个数据只有一个内模式，它是数据物理结构和存储方式的描述，是数据在数据库内部的组织方式
2.外模式：
又称子模式或用户模式，它是数据库用户能够看到和使用的局部数据的逻辑结构和特征描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。
逻辑数据模型一般有：
1.层次模型：有且仅有一个节点没有父节点，其余节点仅有一个父节点
2.网状模型：允许一个以上无双亲节点，一个节点可以有多个双亲节点
3.关系模型：单一的数据模型
4.面向对象数据模型：把实体表示为类，一个类表示实体属性和实体行为
5.对象关系数据模型
6.半结构化模型
mysql中的键：
1.主键：当有多个候选码时，可以选择一个作为主码，选定的候选码称为主键
2.外键：关系R中的一个属性组，它不是R的一个候选码，但它与另一个关系S的候选码相对应
3.侯选建：关系中的一个属性组，其值能唯一标识一个元祖，若属性组中去掉任何一个属性，其不具备有这一性质
索引：
聚集索引：该索引中键值的逻辑顺序决定了表中相应的行的物理顺序
非聚集索引:数据存储在一个地方，索引存储另一个地方，索引带有指针指向数据的存储位置
Hash索引：利用哈希函数，计算存储地址，检索时不像BTree
Hash数据结构与BTree数据结构的差异
1.Hash索引只能用于等值的比较，不能满足范围查找
2.优化器不能使用Hash索引来加速orderby操作
3.使用Hash索引时，Mysql不能确定在两个值之间大约有多少行，如果将一个MyIsam表改为Hash索引的Memory表，会降低查询效率
4.Hash索引只能使用整个关键字来搜索一行
进程线程通信
| Windows | Linux | |
|---|---|---|
| 线程 | 互斥量、信号量、临界区、事件 | 互斥量、信号量、条件变量 |
| 进程 | 管道、消息队列、共享内存、信号量、套接字 | 管道、信号、消息队列、共享内存、信号量、套接字 |
死锁的原因
1.系统资源不足
2.进程运行推进的顺序不合适
3.资源分配不当
死锁的必要条件
1.互斥条件
2.请求与保持
3.不可剥夺条件
4.循环等待条件
两段锁协议:
1.在对任何数据进行读、写操作之前，首先申请并获得对该数据的封锁
2.在释放一个封锁之后，事务不再申请和获得其他任何封锁
数制的转换
R进制转换成呢过十进制：按权展开法
二进制到十进制
10100.01 = 1*2^4+1*2^2+1*2^-2
八进制到十进制
604.01 = 6*8^2+4*8^0+1*8^-1
十进制转R进制:短除法
94(十进制)—-> 1011110(二进制)
二进制转八进制
10001110(二进制)将其三位一划分，利用8421码进行计算
10(2) 001(1) 110(6) = 216(八进制)
二进制转换十六进制
10001110 将二进制以四位进行划分，利用8421码进行计算
1000(8) 1110(E) = 8E(十六进制)
指令系统
指令：程序是一系列按照一定顺序排列的指令。
一条指令一般包含：操作码、操作数地址、操作结果存储地址、下一条指令的地址。
一条指令总体包括两种信息，操作码和地址码，地址码用来描述该指令的操作对象，指令长度取决于操作码长度和操作数的地址数以及操作数的地址的个数
零地址指令：开机指令、关机指令、重启指令。只有操作码的指令
一地址指令：只有一个地址码，数据的单目运算(数据取反、取负)；数据出栈入栈操作（数据在栈顶位置或次栈顶位置）
二地址指令、三地址指令
定长操作码指令格式：操作码的长度决定了指令系统中完全不同操作的指令条数，操作码长度为k位，最多有2^k条不同的指令。
扩展操作码指令格式：操作码的长度可变，操作码逐渐侵占地址码扩展操作码使得指令满足条件。对于4位的地址码，高一级地址在扩展时，每留出一条，下一级可以扩展2^4条指令。
例题：假设机器字长16位，操作数的地址码为6位，指令有零指令地址、一地址和二地址三种格式。
问题1：
1.设操作码固定，若零地址指令有P种，一地址指令有Q种，则二地址指令最多有多少种？
指令条数有2^4
二地址指令最多有：2^4 - P -Q
问题2：
2.采用扩展操作码技术，若二地址指令有X种，令地址指令有Y种，则一地址指令最多有多少种？
一地址指令最多有：(2^4-X)*2^6-Y/(2^6)
指令寻址和数据寻址
寻址：确定本条指令的操作数以及下一条执行指令的指令地址
指令寻址：顺序寻址，PC寄存器存放的是下一条执行的指令地址。PC = PC+1，1表示的是一条指令。指令字长指的是一条指令的二进制比特位数，32位。
数据寻址：寻找指令中的操作数。指令字长=存储字长=机器字长
立即寻址：形式地址A 就是操作数本身 OP # A
直接寻址：有效地址由形式地址直接给出
隐含寻址：操作数地址隐含在操作码中，另一个操作数隐含在ACC中
间接寻址：有效地址由形式地址间接提供EA = (A)
寄存器寻址EA = Ri，有效地址即为寄存器编号
寄存器间接寻址：EA = (Ri) 有效地址在寄存器中
基址寻址：EA = (BR)+A，其中BR 为基址寄存器
变址寻址：EA=(IX)+A有效地址EA等于指令字中的形式地址A与变址寄存器IX的内容相加之和
相对寻址：EA = (PC)+A，A是相对于当前指令的位移量(可正可负，补码)
堆栈寻址：先进后出(一个入出口) 栈顶地址 由SP指出，软堆栈是使用内存设计的栈
CISC和RISC
复杂指令系统计算机CISC（complex instruction set computer）：在指令系统中增加更多的指令，来提高操作系统的效率，为了做到程序兼容。同一系列计算机的新机器和高档机的指令系统只能扩充而不能减去一条，因此使得指令系统越来越复杂，称这些计算机为复杂指令系统计算机。
精简指令系统计算机RISC(reduced instruction set computer):精简指令系统计算机对指令数目和寻址方式都做了精简，使其实现更容易，指令并行执行程度更好，编译器效率更高。通过简化指令系统，是计算机的结构更加合理，从而提高运算速度。
RISC特点：
1.优先选取使用频率最高的简单指令、以及一些常用但不复杂的指令
2.指令长度固定，指令格式种类少，寻址方式种类少
3.指令之间各字段的划分比较一致，各字段的功能比较规整
4.只有取数/存数指令访问存储器，其余指令操作都在寄存器之间进行
5.CPU中通用的寄存器数量相当多。算数逻辑运算指令的操作数都在寄存器中
6.大部分指令在一个或小于一个机器周期内完成
7.以硬布线控制逻辑为主，不用或少用微码控制
8.一般用高级语言编程，重视编程优化工作，减少程序执行时间
区别：
文件系统
初识文件
文件的定义：一组有意义的信息的集合
文件的属性：文件名、标识符、类型、位置、大小、保护信息..
文件内部应如何被组织：文件的逻辑结构
文件之间应该如何被组织：目录结构
操作系统提供的函数功能：create、delete、open、close、read、write系统调用
文件存放在外存：文件的物理结构
操作系统如何关系外存的空闲块：存储空间的管理
文件的分类
有结构的文件和无结构文件
有结构的文件，如数据库中的相关文件，又分为顺序文件、索引文件、索引顺序文件。
顺序文件：
串结构：记录顺序与关键字无关；顺序结构：记录按关键字顺序排列。可变长记录的顺序文件无法实现随机存取，定长记录可以，定长记录、顺序结构的顺序文件可以快速检索。
缺点：不方便增加/删除 记录
索引文件：
建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录
索引表本身就是定长记录的顺序文件，一个索引表项就是一个定长的记录，因此索引文件可支持随机存取；若索引表按关键字顺序排列，则支持快速索引
缺点：解决了顺序文件不方便增删的问题，增加索引表带来了额外的空间开销
索引顺序文件：
将记录分组，每组对应一个索引表项；索引记录时顺序查索引表，找到分组，再顺序查找分组，当记录过多时，可建立多级索引表。
文件目录
一个文件对应一个FCB(文件控制块)，一个FCB就是一个目录项，多个FCB组成文件目录。文件目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
目录结构有：单级目录结构、两级目录结构(用户目录、系统目录)、多级目录形式(树形)、无环图目录结构
操作系统对磁盘的管理
对非空闲磁盘块的管理(存放了文件数据的磁盘块)
对空闲磁盘块的管理
文件物理结构
连续分配：每个文件在磁盘上占有一组连续的块
物理块号 = 起始块+逻辑块号，连续分配支持顺序访问和直接访问(随机访问)。
连接分配(隐式连接、显示连接)
索引分配
文件的组织方式
多级索引组织方式
在为一个大文件分配磁盘空间时，如果分配出去的盘块号已经装满一个索引块，OS必须再为该文件分配一个索引块，用于将以后继续为之分配的盘块号记录于其中。一次类推，再通过链指针将各索引快按序链接起来，多级索引加大访问范围。
例如，盘块大小为4KB，每一个盘块号为4字节(4B)表示，则一个索引盘块可以存放1K个盘块号，文件长度4MB。如果为二级索引，盘块号最多为1K1K = 1M个，文件长度为4KB1M=4GB。
增量式索引组织方式
为了能够全面照顾大、中、小以及特大型作业，可以再用多种组织方式构建文件的物理结构。
小文件：如果盘块大小为1KB或者4KB(文件大小对应1KB
10KB或4KB40KB)，最多只会占用10个盘块，将他们的每一个盘块地址都直接放入文件控制块FCB(索引结点)中，这样就可以直接从FCB中获取文件的盘块地址。中文件：文件大小11KB
256KB或5KB4MB，采用单级索引，也称为一次间址大文件或特大文件：两级或三级索引，称为二级间址或三次间址。
unix混合索引方式
上图最长的文件长度，设机器字长为W，块大小为256W，基本的数据为10*256W，一级索引数据为256*256W,二级索引数据为256*256*256W,三级索引数据为256*256*256*256W。
最长文件长度为所有数据的总和。
例题：
1)512*10+170*512+170*170*512+170*170*170*512
2)逻辑块号为292(15000/512),偏移量为496(15000%512)
292-180(10+170) = 112，物理地址在第二索引的第0格中
3）最少一次(直接地址) 最多四次(读三重索引、读二重索引、读一重索引、读数据内容)
文件存储空间管理
空闲表法和空闲链表法
1.空闲表
空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中表项序号、空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有的空闲区按其起始盘块号递增的次序排列，形成空闲盘块表。
例如：
| 序号 | 第一空闲盘块号 | 空闲盘快数 |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 9 | 3 |
| 3 | 15 | 5 |
| 4 | — | — |
表示，空闲盘号从2开始有4块盘块空闲，依次类推。
存储空间的分配与回收
空闲盘区的分配与内存的分区(动态)分配类似，同样采用首次适应算法和最佳适应算法，它们对于存储空间的利用率大体相当，都优于最坏适应算法。在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各个表项，直至找到第一个其大小能满足要求的空闲区，再将该盘块分配给用户(进程)，同时修改空闲表。
2.位示图法：
位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为”0”时，表示对应的盘块空闲；当为”1”时，表示已分配。磁盘上的所有盘块构成的二进制位与之对应，这样的盘块构成的集合，称为位示图。
盘块的分配，根据位示图进行盘块分配时，分为三步：
1.顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位
2.将所找到的一个或一组二进制位转换成与之对应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则将其对应的盘块号按b = n(i-1)+j，n表示每一行的位数。
3.修改位示图，令map[i,j] = 1
盘块的回收：
1.将回收的盘块按照盘块号转换成位示图的行号和列号，转换公式为i = (b-1) DIV n+1;j = (b-1) MOD n+1
2.修改位示图。令map[i,j] = 0
3.UNIX中采用的是成组链接法(B站某个老师的课程，本人并还了解)
空闲盘块的组织
1）空闲盘块号栈：用来存放当前可用的一组空闲盘块的盘块号(最多含100 个号)，以及栈中尚有的空闲盘块号数N。顺便指出，N 还兼作栈顶指针用。例如，当N=100 时，它指向S.free(99)。由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一把锁。（只有这个是放在内存中的，其它是在磁盘上。）
(2) 文件区中的所有空闲盘块被分成若干个组，比如，将每100 个盘块作为一组。假定盘上共有10 000 个盘块，每块大小为1 KB，其中第201～7999 号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为7901～7999；次末组为7801～7900……；第二组的盘块号为301～400；第一组为201～300，如上图右部所示。
(3) 将每一组含有的盘块总数N 和该组所有的盘块号记入其前一组的第一个盘块的
S.free(0)～S.free(99)中。这样，由各组的第一个盘块可链成一条链。
(4) 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。
(5) 最末一组只有99 个盘块，其盘块号分别记入其前一组的S.free(1) ～S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为99，不应是100，因为这是指可供使用的空闲盘块，其编号应为(1～99)，0号中放空闲盘块链的结尾标志。)
空闲磁盘块的分配与回收
当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1 并返回。
在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1 操作。当栈中空闲盘块号数目已达100 时，表示栈已满，便将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为新栈底
提高磁盘I/O速度的途径
1.改进文件的目录结构以及检索目录的方法来减少对目录的查找时间
2.选取好的文件存储结构，以提高对文件的访问速度
3.提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反。
