软件设计师

数据的表示

R进制转十进制：按权展开法

二进制1001010.01=
整数部分：1001010从左向右看
第一位：0×2¹，第二位：1×2¹，第二位：0×2²……
小数部分：01
第一位：0×2^-1，第二位：1×2^-2
以此类推，将求得的值加上就是十进制的值（Tip：0乘任何数都为0，因此在求解的时候可以不用写出来），以上解的值为74.25。
其余进制也是相同的求法，不同的地方在于要将2改成对应的进制，例如是8进制即是8的多少次方。

十进制整数转R进制

全为整数：短除法

例如：98转二进制
98÷2=49余0
49÷2=24余1
24÷2=12余0
12÷2=6余0
6÷2=3余0
3÷2=1余1
1（逆序排上去）
结果为：1100010

有小数转R进制

整数部分使用短除法，小数部分乘上对应的进制数，取其整数部分的数值，小数部分继续相乘（Tip：有些数值并不总能转换成对应的R进制的小数，就需要采用取近似值的方法）
例如：0.25转二进制
第一次：0.25×2=0.5取0
第二次：0.5×2=1取1
0.25的二进制表示就为：0.01
若要转为其它进制只需要将2改成对应的进制即可。

二进进制，八进制，十六进制相互转换

二进进制转八进制

每三个二进制位对应一个八进制
例如：10001110
从右至左分段，每三个分一段：10 001 110（Tip：最左边的也许会不足三个，只需要补上0即可）
然后分别使用按权展开相加即可
110=1×2¹+1×2²=6
001=1×2⁰=1
10=1×2¹=2
10001110对应的八进制即：216

二进进制转十六进制

每四个二进制位对应一个十六进制
例如：10001110
从右至左分段，每四个分一段：1000 1110（Tip：最左边的也许会不足三个，只需要补上0即可）
然后分别使用按权展开相加即可
1110：1×2¹+1×2²+1×2³=14
14对应十六进制的的E（Tip：不清楚的可以去看看16进制表）
1000：1×2³=8
10001110对应的十六进制即：8E
如果是需要八进制转十六进制的，我还不知道咋整，我是把八进制转回二进制再转成十六进制的。

原码计算

将十进制转为二进制，如果不足八位，在前面补0，直至满八位。

	数值1	数值-1
原码	0000 0001	1000 0001

最高位为符号位（表格中加粗的），0表示整数，1表示负数

反码计算

	数值1	数值-1	1-1
反码	0000 0001	1111 1110	1111 1111

正数的反码、补码、原码相同，负数的符号位保持不变，其余各位分别取反。
由此可得，
反码进行1-1的计算后得：1111 1111
由于是反码，求解时需要将其转为源码
符号位不变得：1000 0000
转为十进制得：-0，与我们需要得到的结果接近
我们平时肯定直接说0而不会说-0

补码计算

	数值1	数值-1	1-1
补码	0000 0001	1111 1111	0000 0000

负数的补码在反码的基础上+1
1-1得到值为0，求解完毕。

移码计算

	数值1	数值-1	1-1
移码	1000 0001	0111 1111	1000 0000

在补码的基础上将首位进行取反操作

原反补的取值范围

	整数
原码	-（2n-1-1）~2n-1-1 （设n=8，-127~127）
反码	-（2n-1-1）~2n-1-1
补码	-2n-1~2n-1-1

补码之所以表示的范围比原码与反码多一位，是由于0与-0在原码与反码中表示的形式是不一样的，而在补码中的表示形式是一样的。

浮点数运算

浮点数表示：N = M×R^e
M：尾数，e：指数，R：基数
运算步骤：对阶→尾数计算→结果格式化
例题：1×10³+1.19×10²
①1.19×10²转为0.119×10³
②1×10³+0.119×10³ = 1.119×10³
结果格式化是指：结果必须是科学计数法的形式，第一位不能为0或小数点前只能有一位。

计算机结构

主机组成：CPU和主存储器（内存）

CISC与RISC

CISC：在计算机还没全面推广时提出的。

执行部分时间最长的一段表示为流水线周期
依照例题，三个部分中执行时间最长的为2ns，因此流水线周期为2

理论公式

t1，t2+…+tk表示的是分为几个部分
依照例题：分为了三个部分：取值，分析，执行
花费的时间分别是：2，2，1
相加结果为5
n表示的是共有几条指令
n-1是因为(t1+t2+…+tk)已经将第一条计算完毕了
Δt表示流水线周期
理论公式求解例题：(2+2+1)×(100-1)×2=203

实践公式

k表示分为几个部分，例题中分为3个部分
n表示共有几条指令
Δt表示流水线周期
实际公式求解例题：(3+100-1)××2=204
考试中一般采用理论公式，如果理论公式找不到答案再采用时间公式的答案

吞吐率（Though Put rate TP）计算

概念

单位时间内处理的任务的数量

公式

吞吐率最基本的公式：

1/Δt是最理想化的状态，忽略的流水线的准备时间，认为一个流水线周期就能够完成一条指令。

加速比

概念

完成同一批任务，不适用流水线所用的时间与使用流水线所用的时间的比值。

公式

例题：

被有效利用的时间片：(Δt+Δt+Δt+3Δt)×4=24Δt
乘以4：共有4个任务执行
全部的时间片：15Δt*4=60Δt
乘以4：共有4个控件执行
从图中可以看出
E=24Δt/60Δt
综上：在每个部分所需要的时间都均等的清空下，效率较高。

层次化存储结构

假设h为95%，t₁=1ns，t₂=1ms=1×10⁶
t₃=95%×1ns+(1-95%)×1×10⁶ns=50000.95ns
有命中率因素是因为cpu在访问时会先范文Cache中的内容，若Cache中没有所需要的数据，cpu会再去访问内存中的内容
直接在Cache中就获取到的几率就是命中率，没有在Cache中获取到在内存中获取到的就称为失效率

局部性原理

时间局部性

刚刚被方位的指令立刻又需要被访问

空间局部性

当程序访问了一个空间后又立即访问了它相邻的控件。

主存

分类

随机存储器（RAM）：内存（断点数据就丢失）
只读存储器（ROM）：BIOS

共有（）K个地址单元
算总共有多少个地址单元时，先用（末地址位-首地址位）+1，一般先加1再做减法


上图是数据存储优化后的结果，当R₀被读取结束后，刚好能够直接读取R₁（因为在缓冲区处理数据是需要耗时3ms，而磁头读取数据不会停止，因此处理完R₀时，此时磁头在R₁开始的这个位置上)

总线

内部总线
系统总线：数据总线，地址总线，控制总线
外部总线

系统可靠性分析

串联系统

可靠率：1-(1-R₁)×(1-R₁)……×(1-R_n)
(1-R₁)：每个系统的失效率
相乘是求出所有系统的失效率
用1去减是求出整个并联系统的失效率

模冗余系统

从整体上看，整个系统使串联的
因此可靠性只要讲三个系统的可靠性都分别求出来后相乘就能得到结果

差错控制

概念

前提条件：
采用1位长度的二进制编码。若A=1，B=0
采用2位长度的二进制编码。若A=11，B=00。
采用3位长度的二进制编码。若A=111，B=000。
检错：能够从接收到的编码中发现错误
假设传输的是1位长度的二进制编码A，在传输过程中发生错误1变为0，当接收方接收到位0时便会以为对方传输的时B，因为0与1都是合法的，因此时无法检错的。
假设传输的是2位长度的二进制编码A，在传输过程中发生错误11变为10，当接收方接收到位10时便会发现错误，因为10是非法的，但无法纠错。
纠错：能够从接收到的编码中发现错误并纠错
假设传输的是3位长度的二进制编码A，在传输过程中发生错误111变为110，当接收方接收到位110时便会发现错误，因为10是非法的，通常认为通信电路时比较靠谱的，不会出现多位的错误，因此会讲110与正确的编码进行对比，发现110与111更为接近，因此会讲110修正为111
码距：一个编码系统的码距使整个编码系统中任意（所有）两个码字的最小距离
例如采用1位长度的二进制编码。若A=1，B=0。
A与B之间至多只需要修改1位就能够表示对方，码距：1
A与B之间至多只需要修改2位就能够表示对方，码距：2

信息位：4位
要存放下4位的信息位，数据位数就要有3位校验码
校验码的位置分别在2⁰+2¹+2²（1，2，4）

在将其进行异或操作，以r₂为例：
因为7，6，5这个三个都含有2²因此他们的数据对于第2个校验码都会产生影响
因此r₂会等于三个位置的数据进行异或得到的结果
按顺序两两进行异或求解
r₂=1⊕0⊕1=0
求解步骤：
1⊕0=1
再用1⊕1=0
最后结果为0
其它位计算方式一样

运行态：需要的所有资源都已经准备就绪，且分配到cpu资源
就绪态：需要的所有资源都已经准备就绪
等待态：除cpu资源外还需要其它资源，例：与外设交互等

进程的同步与互斥

互斥（对应共享）

资源同一个时间只能有一个人使用

同步（对应异步）

速度快的要等速度慢的，相当于是两者必须同时完成工作

生产者消费者

信号量：主要用于PV操作的变量
P操作：信号量–
V操作：信号量++


因此：a1与b1应为一对PV操作，先由a1进行V操作唤醒b1，再由b1进行P操作，由此可知a1与b1中的信号量应该是相同的

由收营员进程首先进行V操作去唤醒消费者进程，进而消费者进行P操作
因此答案为：A，C

将前驱图转为PV操作

将前驱图的每一个活动都转成相应的进程，然后在并发执行时，依然按照前驱图的约束关系先后执行
前驱图主要表达进行的这些活动的依赖关系

每一个箭头都表示一个PV操作所以都对应一个信号量，对应的规则是：从左到右，从上到下

答案：C，A，A

死锁问题

至少多少资源不会造成死锁

至少有多少系统资源不会发生死锁的题目：

互斥：同一时刻只能有一个进程使用
保持和等待：所有进程都保持自己所拥有的资源并等待别人释放更多的资源
不可剥夺：系统不会剥夺已分配给进程的资源
环路等待：进程之间相互等待对方释放资源，形成一个闭环

首次适应算法（FF）

实现：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，从链首开始查找，将满足需求的第一个空闲分区分配给作业。
特点：该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。
不足：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销。

最佳适应算法(BF):

实现：将所有空闲分区按照从小到大的顺序形成空闲分区链，在申请内存分配时，总是把满足需求的、最小的空闲分区分配给作业。
特点：综合性能最好，算法开销小，回收分区后一般不需要对空闲分区队列重新排序，会有更多的大分区被保留下来，更能满足大进程需求。
不足：算法开销大，回收分区后可能需要对空闲分区队列重新排序。会产生很多太小的，难以利用的碎片。

最差适应算法(WF)

实现：将所有的空闲分区按照从大到小的顺序形成空闲分区链，在申请内存分配时，总是把满足需求的、最大的空闲分区分配给作业。
特点：减少难以利用的小碎片。
不足：大分区容易被用完，不利于大进程，算法开销大，原因同上。

循环首次适应算法（NF）

实现：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，总是从上次找到的空闲分区的下一个空闲分区开始查找，将满足需求的第一个空闲分区分配给作业。
特点：不用每次都从低地址开始检索，算法开销小，原因同首次适应算法。
不足：高地址的大分区也被用完。

段页式存储

页式存储

（1）物理地址应为十六进制：
已知可得：
页面大小为4k=2¹²→业内地址12位
逻辑地址：5A29H→低位的12位为页内地址A29为业内地址，5为页号
页号5对应的页帧号为6，将求得的页帧号与页内地址连接起来即为物理地址：6A29H，因此选D
（2）应该淘汰的页号（）页面
状态位值为1的页面在内粗一年中
由图中的可看出0，1，2，5页在内存中
由访问位值为1可以看出，0，2，5刚被访问过
因此应该首先淘汰没有被访问过的页面，所以要淘汰的页号：1，因此选B

段式存储

快表

先进先出置换算法（FIFO）

索引节点一般为13个，编号由0~12
若索引节点中都是直接索引，假设每个索引节点可以存储4k的字节，那么13个所有节点最多只能存放4k×13=52k的数据
一级间接索引：该索引节点存放的是下一级索引的地址，假设每个地址占4个字节
4k÷4=1024，该索引节点对应的物理盘块存储1024个物理盘块的地址，对应的那些物理盘块才存索引内容
一级间接索引存储的容量空间：4k×1024

绝对路径最前面有一个’/’符号

空闲存储空间的管理

(1)
由于物理号是从0开始计算的，因此：(4195+1)÷32=131.125
4195+1：这是因为它是从0开始编号的，因此编号为4195的物理块，实际上是第4196个物理块。
由于字是从1开始计算的，取整为：132
因此答案为132，选择D
(2)
位置是从第0个位置开始计算
程序控制方式（程序查询方式）：最低级也是CPU介入最多的一种方式。
程序中断方式：当外设完成相应数据的处理，它会发一个中断指令，系统收到后就会进行下一步的处理。
DMA（直接存储控制方式）：有专门的控制器，只要是外设与内存的数据交换过程中这个控制器会进行管控，CPU只需要在开始的时候进行介入，整个过程由DMA控制器进行监管，完成后再由CPU进行接管。

虚拟设备与SPOOLING技术

数据库系统

数据库模式（三级模式-两级映射）

来源：零乘一