中级软考知识点-JZTXT

fc6be87b7868ad59bd3115c6b767c51

461fb34b1b9249f1799027f255c5f26

1. 计算机组成与体系结构

2d55b806b80c3c56995a59caac8e6b7

1.1 数据表示

进制转换

N转10：按权展开法
10转N：短除法
2进制转8进制、16进制：位数关系

原码反码补码移码

	1	-1	1-1（应该为0
原码	0000 0001	1000 0001	1000 0010
反码	0000 0001	1111 1110	1111 1111
补码	0000 0001	1111 1111	0000 0000
移码	1000 0001	0111 1111	1000 0000

最高位用作符号位

原码：{范围：-（2^(n-1) - 1）~ 2^(n-1)-1}
反码：正数不变，负数符号位不变其他取反。{范围：-（2^(n-1) - 1）~ 2^(n-1)-1}
补码：正数不变，负数为反码+1。{范围：-（2^(n-1) ）~ 2^(n-1)-1，如-128到128}

{-128}补 = {-127-1}补=1000 0000；其中{-127}补=1000 0001

模计算：{-128}补=模-|X|=1 0000 0000-1000 0000 = 1000 0000

移码：在进行浮点数计算中用作解码。在补码的基础上符号位取反

浮点数运算

浮点数表示：N=M*R^e

其中M称为尾数、e是指数、R是基数

运算步骤：对阶（把基数指数化成一样，一般把尾数化小）——>尾数计算——>结果格式化（小数点前留一位）

1.2 计算机结构

95f494fedbf77fe4c31372eb8bb7030

主机：CPU（运算器+控制器）+主储存器（内存）

运算器：算术逻辑单元ALU、累加寄存器AC、数据缓冲寄存器DR、状态条件寄存器PSW（常考，计算过程的标志位，如进位、溢出、中断状态信息等）
控制器：程序计数器PC、指令寄存器IR、指令译码器、时序部件

计算机体系结构分类——Flynn

68b18cbe02eb0b6dc35067be7020dac

依据指令流和数据流进行分类，根据单或多分为四种不同结构。

能够根据典型描述判断所属类型

CISC和RISC

9731d22e1ba9cd36fcffd096b9f2356

复杂指令集计算机，Complex Instruction Set Computer。简称CISC：CISC是在计算机还没大规模使用时提出，指令是定制的，根据不同用户需求设计。
精简指令集计算机(RISC:Reduced Instruction Set Computer RISC)：RISC泛用性更强。

流水线

概念

程序执行多条指令重叠进行操作的一种准并行处理实现技术。
各部件同时处理是针对不同指令而言，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度。

9ed567893949ab8f3e459ae8cebc192

周期及执行时间计算

周期：流水线周期为执行时间最长的一段
计算公式：流水线执行时间计算公式为：
- 1条指令执行时间+（指令条数-1）*流水线周期
- 理论公式：（t1+t2+…tk）+（n-1）*△t
- 实践公式：（k+n-1）*△t （更接近工业，更工整）

eg：取值2ns，分析2ns，执行1ns，周期是多少，100条指令执行需要的时间。

周期：△t = Max{2ns，2ns，1ns} = 2ns

时间：（2ns+2ns+1ns）+99*2ns = 203ns

（3+100-1） *2ns = 204ns

吞吐率计算

吞吐率（Though Put rate，TP）是指在单位时间内流水线所完成的任务数量或输出的结果数量。基本公式如下：

TP= 指令条数/流水线执行时间{上题中为100/203}

最大吞吐量（理想状态，不考虑运行前后）=Lim（n—>max）n/（k+n-1）△t = 1/△t

加速比计算

流水线加速比：完成同一批任务，不适用流水线所用时间与使用流水线所用时间之比。越高越好

S = 不使用流水线用时/使用流水线用时{上题中为 500ns/203ns}

流水线效率：流水线设备的利用率。时空图上，流水线的效率定义为n个任务占用的时空区域k个流水段总的时空区之比

32f2912e2928f1774d1a88bfecf04d6

eg：假设一个任务分为四步，占用时间分别为△t、△t、△t、3△t。

效率为：4 * 6 △t /4*15△t = 2/5

计算机层次化存储结构

dbed7d1fbd17c2272e619d3f780df52

重点：整体结构、cache、内存

CPU中有运算器、控制器，二者当中存在寄存器使用（容量小速度快）。

cache高速缓存存储器，用来实现高效调用（减少CPU与内存的直接交互）。

不是所有存储结构都用寄存器是考虑到成本问题。

cache基本概念

功能：提高CPU数据输入输出效率，突破CPU与存储系统间数据传送宽带限制。

存储系统体系中，cache是访问速度最快的层次，使用cache改善性能的依据是程序的局部性原理。选最快，有寄存器寄存器否则cache。

将当下的高频访问指令和数据放入cache来避免不断访问内存。

49c046ab72ea90ec23debefe4559fce

局部性原理（时间局部性与空间局部性）

cda08225bcbaf86293944cbdabd3570

时间局部性：处理相关数据和程序时，有某个时段集中访问某些指令，或者说某一时段集中读取某些数据。

空间局部性：例如处理数组时，短时间内访问的路径地址是连续的。

工作集理论：进程运行时被频繁访问的页面集合。

随机存储器与只读存储器

随机存取存储器RAM：（如内存，断电后信息丢失）
- DRAM（动态RAM）
- SRAM（静态RAM）
只读存储器ROM：（如bios，掉电后信息不丢失）
- MROM（掩码ROM）
- PROM（Programmable ROM，一次可编程ROM）
- EPROM（可擦出PROM）
- 闪速存储器（Flash Memory，闪存）

编址：

容量小的芯片构成大的存储器，如两片8*4（8个地址空间，每个空间存4位）可以构成8 * 8或16 *4

计算地址单元数= 内存地址相减后+1

0a0e879f4ebaef3bd61141fd1804dd9

1k=2的十次方

磁盘工作原理

4baa4c8cfa8a841e5c7cd7eb7702603

考点：磁盘运作原理、

磁盘：环形盘片。盘面用于保存数据，由专业的设备磁头进行读取。

平均等待时间为磁盘转一圈时间。注意：读取过程中磁盘一直匀速旋转。完整读完区域才能进行处理。

如图中，由于读取需要用时3ms，所以当R0存入存储器中时，磁盘继续转，等到读取完毕后磁头位于R2开头。

最长用时计算（前一位运行结束位置转一周再来到下一位位置）：（周期33ms+处理3ms）*10（除了最后一个）+6（最后一个读和处理）=366ms

最短用时计算（修改各部分的布局）：一周旋转33*2=66

计算机总线

根据所处位置的不同，分为三类：

内部总线
- 微机内部各个外围芯片与处理器之间的总线（芯片级）
系统总线
- 各个插件板和系统板之间的总线（如PCI接口、VGA的一些接口）
- 数据总线、地址总线、控制总线
  - 数据总线：传输数据（32位指的是总线宽度是32bit位，一个周期传输数据是32个bit位）
  - 地址总线：地址总线若是32位，它代表的地址空间是2的32次方。
    - 例如32位电脑能处理的内存上限为4G。
  - 控制总线：
    *
外部总线
- 微机和外部设备的总线

串并联系统的可靠性计算

计算可靠性

串联系统
- 可靠率：各串联子模块可靠性相乘
- 失效率：各子系统失效率相加（不准确，仅在各系统每个失效率极低的情况下可用）
并联系统
- 并联某个子系统不失效系统就可以用
- 可靠率：1-所有子系统都失效的概率。
- 失效率：1-可靠度
模冗余系统与混合系统
- 通过冗余部署，多个系统完成同一个任务，任务结果采用少数服从多数选择最终用作输出的结果，提高系统可靠性

串并联组合：

校验码的概念

差错控制

码距：整个编码系统中任意（所有）两个码字的最小距离。

码距和检错纠错的关系：

一个码组内为了检测e个误码，要求最小码距d应该满足：d>=e+1
一个码组内为了纠错t个误码，要求最小码距d应该满足：d>=2t+1

比如要检测一个误码，必须码距至少为2，纠错一个误码，码距至少为3

码距为1时，无法分辨传输的数据是被错误传输与否。大部分有误均假设仅改变了一个位的数据。

循环校验码（CRC）【可检错不能纠错】

模2除法是指在做除法运算过程中不计其进位的除法，不是用减法是做异或操作。

被除数为1则商为1，被除数为0则商为0；
余数去掉首位为新的被除数；
新的被除数以0开头，则除数变为全0，以1开头则除数不变；

编码后的数据能够与循环校验码的生成多项式相除余数为零。接收后相除余数非零说明传输出错。

生成多项式的长度N减一，在原始报文后加上（N-1）个零。余数尾数也为(N-1)，把余数替换掉报文后面加的（N-1）个零。

上题中的CRC编码是110010101010011（原始后接余数）

与生成多样式做除法，余数为0

海明校验码（高频难点）

编码基本规则、信息位数目、校验位数目

校验位位于信息编码的2的N次方位置，如下图。当只放一个信息位，就至少需要3位长度。当信息位5位，则编码需要9位（1、2、4、8都是校验位）

校验位r和信息位x一定会满足：2^r >= x + r +1

编码：1）填入信息位。2）校验位：按照规则填入

将信息位数拆解成由2的N次方公式组合，如：7=2²⁺²1+2^0，6=22+2^1，5=22+2^0,3=21+2^0

则计算对应位置的校验位时，将用到该位做组合的信息位的数值做异或。

2 操作系统基本原理

管理整个软硬件资源

2.1 进程管理

进程状态

运行态、等待态、就绪态。
- 就绪：资源都配好了，差CPU
- 等待：除了没有CPU资源还差其他资源，如外设、数据之类
  - 等待不能到运行，就绪不能回等待
时间片轮法：避免有长时间的进程长期挤占cpu资源
- 固定周期的进程暂停挂起

前趋图（和pv操作组合考察）

同步和互斥

互斥：同时只允许一个进程调用资源

同步：速度有差异，在一定情况下停下等待，有速度匹配要求

同步和互斥不是反义词！！

单缓冲区：生产者和消费者不能同时对一个内容做处理，当消费者未使用掉时生产者不能放入（互斥）

PV操作

利用到同步互斥的一些理念解决实际问题，用到的工具就是PV操作。

临界资源：进程间需要互斥进行占用的资源，如打印机
临界区：每个进程中访问临界资源的代码成为临界区
信号量：一种特殊变量，如P(S)、V(S)，中的s即为信号量

P操作：把信号量-1
- 当信号量小于零，阻塞当前P的执行位置，将进程放入到进程队列中。在进程列表中进入等待状态。
- 当信号量大于等于零，继续执行。
V操作：信号量+1
- 当信号量小于等于零，则从进程队列中唤醒一个进程继续执行。
- 否则继续执行下去。

转自b站热评：用公共厕所蹲坑轻松理解PV操作:
进程就是急着蹲坑的每个人
- 信号量S代表剩余的闲置坑位，为负数时代表坑位不够即有人在排队

当一个人来到厕所里面，Pronounce(正式宣布)要蹲坑，就相当于执行了P操作，在此之前:
- 当S>0，代表有空闲坑位，肯定没人排队，于是P操作后S减1，立刻开始蹲坑放大
- 当S=0，代表没有空闲坑位，坑位都被占了而且大概率还有人在排队(S<0时)，于是P操作后S减1，再急也得乖乖站在旁边排队-

当一个人从坑位出来，蹲坑放大成功获得胜利Victory，就相当于执行了V操作，在此之前:
- 当S>0，代表有空闲坑位，肯定没人排队，于是V操作后S加1，挥挥衣袖潇洒离开
- 当S<0，代表没有空闲坑位，坑位都被占了而且大概率还有人在排队(S<0时)，于是V操作后S加1，出于人道主义精神，喊一个正在排队的人过来接坑，然后拂衣而去深藏功与名

PV操作例题：

前趋图转PV：

技巧：从左到右，从上到下标注信号量，然后箭头起点进程标V，箭头末尾进程标P，如上图所示。

死锁

题型：给定一定数量进程，每个进程资源，计算至少多少资源系统不会死锁
死锁预防和避免问题（银行家算法）

死锁：所有可用资源均已分配，但所有进程都无法完成当前进程（需要进一步申请资源），导致无法释放占有的资源。

至少资源：假设各进程所需资源为Ni，则求和（Ni - 1），所得结果+1即为至少所需资源

答案为13

死锁的四个条件：互斥；保持等待；不剥夺；环路等待（即等待资源成环）

死锁预防：打破四大条件

死锁避免：有序资源分配法（资源利用率低），银行家算法（重点）

先算剩下的资源数。

2.2 存储管理

分区存储（四种）

最佳适应法会导致多次分区后系统中很多小块内存

页式存储

页号（等大）和页内地址

逻辑地址与物理地址的转换

分成等分的区域

页表记录页号和块号关系，需要通过表进行转换

逻辑和物理地址转换：二者的页号不一定一样，页内地址一样。保留页内地址，求取页号。

首先区分出页号和页内地址。

页面大小4K，即2^12次方，业内地址是12位。12位也就是16进制的后三位。页内地址保留，其前面的就是页号。页号通过查表得知。

应该淘汰的页号需要满足：1. 状态位为1（在内存上）2.
段式存储

段号（按逻辑层次划分段）和段内地址
段页式存储

先分段、分段后再分页。

需要查两次表