软考笔记（更新至PV操作）

软考的备考笔记（更新至索引文件结构）

习题公众号：软考专题库

教材：软件设计师教程（第5版） 小蓝本

视频参考教程：软件设计师考试教程_哔哩哔哩_bilibili

学习资料：链接:https://pan.baidu.com/s/1rDCqvV53XOJgN3W3umjdzw
提取码:v2qc

计算机组成与体系结构

数据的表示

进制略过

浮点数表示

* N = M*R^e
* M为位数 e是指数 R为基数

CPU结构

Flynn分类法

体系结构类型	结构	关键特性	代表
单指令流单数据流SISD	一个控制部分 一个处理器 一个主存模块		单处理器系统
单指令流多数据流SIMD	一个控制部分 多个处理器 多个主存模块	各处理器以异步的形式执行同一条指令	并行处理机 陈列处理机 超级向量处理机
多指令流单数据流MISD	多个控制部分 一个处理器 多个主存模块	被证明不可能 至少是不实际	目前没有 有文献称流水线计算机为此类
多指令流多数据流MIMD	多个控制部分 多个处理器 多个主存模块	能够实现作业、任务、指令等各级全面并行	多处理机系统 多计算机

CISC和RISC

RISC就是CISC的抽取

指令系统类型	指令	寻址方式	实现方向	其他
CISC（复杂）	数量多，使用频率差别大 可变长格式	支持多种	微程序控制技术（微码）	研制周期长
RISC（精简）	数量少 使用频率接近 定长格式 大部分为单调期指令 操作寄存器 只有Load/Sotore操作内存	支持方式少	增加了通用寄存器；硬布线逻辑控制为主；适合采用流水线	优化编译 有效支持高级语言

流水线

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

流水线计算

流水线周期为执行时间最长的一段（取值，分析，执行的时间中最长的一段）

流水线计算公式：

• 1条执行执行时间+（指令条数-1）* 流水线周期
  • 理论公式：（t1+t2+..+tk）+(n-1) * 流水线周期
  • 实践公式：（k+n-1）* 流水线周期 k代表分了几个段（取值 分析 执行为三个段）

100条指令全部执行完毕的时间就是（实践公式）：（3+100-1）*2 = 204

考试中一般先选择理论公式的结果

流水线吞吐率计算

吞吐率是指单位时间内流水线所完成的任务数量或输出的结果数量

计算公式：TP = 指令条数/流水线执行时间

流水线最大吞吐率 TP = lim n趋向于无穷 n/(k+n-1)*流水线周期 = 1/一个流水线周期

流水线加速比计算

完成同样一批任务 不适用流水线所用的时间和使用流水线所用的时间之比称为流水线加速比

S = 不使用流水线执行时间/使用流水线执行时间

例如上一题中不使用流水线的执行时间为：（2+2+1）*100 = 500

所以之比为500/203

流水线的效率

流水线的效率是指流水线的设备利用率 在时空图上 流水线的效率定义为N个任务占用的时空区和k个流水段总的时空区之比

计算机层次化存储结构

Cache

• 功能：提高CPU数据输入输出的速率
• 在计算机的存储系统体系中 Cache是访问速度最快的层次
• 使用Cache改善系统性能的依据是程序的局部性原理

局部性原理

• 时间局部性：被引用过一次的位置在未来会被多次引用
• 空间局部性：如果一个位置被引用 未来它附近的位置也会被引用
• 工作集理论：工作集是进程运行时被频繁访问的页面集合

随机存储器和只读存储器

1. 随机存取存储器RAM
   • DRAM（Dynamic RAM 动态RAM） -SDRAM
   • SRAM（Static RAM 静态RAM）
2. 只读存储器ROM
   • MROM（Mask ROM 掩模式ROM）
   • PROM（Programmable ROM 一次可编程ROM）
   • EPROM(Erasable PROM 可擦书的PROM)
   • 闪速存储器（Flash memory,闪存）
3. 主存 - 编址的相关计算

计算多少K个地址单元 就用C7FFFH-AC000H

计算存储多少位 就用地址单元乘以16bit/28乘16K乘x = 1 计算得出x的值

磁盘工作原理

存取时间= 寻道时间+等待时间（平均定位时间+转动延迟）

寻道时间是指磁头移动到磁道所需的时间 等待时间位等待读写的扇区转到磁头下方所用的时间

计算机总线

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

系统可靠性分析

串联系统和并联系统

串联系统的特点：每个子系统必须都可靠 才能保证整个系统可靠

并联系统的特点：只有当所有子系统都失效 整个系统才失效

模冗余系统和混合系统

模冗余系统的特点：多个模块都做同样的计算 结果都汇总到表决器 通过少数服从多数进行表决 会对错误进行屏蔽 若某个子系统出错 不会影响到整个系统（计算几乎不考）

混合系统的特点：串并联混合 把串联在一起的看成一个并联进行计算

混合系统的公式考的更多

校验码

码距：整个编码系统中任务两个码字的最小距离 例如3位长度的二进制编码 A=111 B=000 AB之间的最小码距为3（码距即A码最少可以改变几位变成B码）

差错控制 - 循环校验码CRC

模2除法：在做除法运算的过程中不计其进位的除法

首先给商一个1 用10111的前三位101和110进行异或运算 再给商一个1 得到的结果再进行异或 最后剩下11没办法异或了就给商一个0

首先将多项式化为二进制11011 将原始报文的后面补上多项式最高次数幂个0 然后用其对11011进行模2运算

最后得到的CRC编码就是原始报文后面补上四位商的结果 即110010101010011

海明校验码（难点 常考）

2的幂次方位放校验位（1，2，4，8，16等）

可以看到7，6，5中都含有2^2 也就是r2 所以r2的值就等于I4异或I3异或I2

进行纠错的方法：加入校验位中有错误位 信息位在进行异或操作后可以得到每个校验位的值 所以可以对错误的校验位进行纠错

操作系统

操作系统概述

功能

• 管理系统的硬件、软件、数据资源
• 控制程序运行
• 人机之间的接口
• 应用软件与硬件之间的接口

管理职能

• 进程管理：进程状态 前趋图 PV操作 死锁问题
• 存储管理：段页式存储 页面置换算法
• 文件管理：索引文件 位示图
• 作业管理
• 设备管理
• 微内核操作系统

进程管理

进程的状态：就绪、运行、等待

前趋图

表达有哪些活动可以先进行 可以同时进行 而不是一步一步进行

进程的同步与互斥

• 互斥：在同一时刻只允许一个进程使用资源 其他进程不能同时使用
• 同步：可以同时进行 速度有差异 在一定情况下等待

PV操作

• 临界资源：诸进程间需要互斥方式对其进行共享的资源 如打印机 千军万马过独木桥中的独木桥
• 临界区：每个进程中访问临界资源的那段代码
• 信号量：特殊的变量 如P(S) V(S)中的S

P操作：判断S 若小于0则进入到进程 若大于0则继续循环 V操作则与之相反

P就是加锁挂起 V就是解锁激活进程

生产者与消费者互为前后驱

死锁问题

进程管理是操作系统的核心 设计不当就会出现死锁问题

如果一个进程在等待一件不可能发生的事 则进程就死锁了 而一个或多个进程产生死锁 则会造成系统死锁

在计算最少分配多少资源不会发生死锁问题时 可以先给每个进程都分配需要的资源-1个 最后剩下一个不管分给哪个进程都可以满足

银行家算法

死锁的预防：打破四大条件

• 互斥
• 环路等待
• 保持和等待
• 不剥夺

死锁的避免：有序资源分配法 银行家算法

银行家算法：相当于银行贷款

• 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
• 进程可以分期请求资源 但请求的总数不能超过最大需求量
• 当系统现有的资源不能满足进程尚需资源数时 对进程的请求可以推迟分配 但总能使进程在有限的时间里得到资源

存储管理

分区存储组织

给作业4分配空间使得分配空间尽可能减少移动 减少碎块

页式存储

把用户程序等分为页 内存也用同样的方式分页

高级程序语言使用逻辑地址；运行状态 内存中使用物理地址

• 优点：利用率高 碎片小 分配及管理简单
• 缺点：增加了系统开销 可能产生抖动现象

段式存储

包括段号和段内地址 段长不是固定的

• 优点：多道查询共享内存 各段程序修改互不影响
• 缺点：内存利用率低 内存碎片浪费大

段页式存储

• 优点：空间浪费下 存储共享容易 存储保护容易 能动态连接
• 由于管理软件的增加 复杂性和开销也随之增加 需要的硬件以及占用的内容也有所增加 使得执行速度大大下降

快表

是一块小容量的相联存储器 由高速缓存器组成 速度快 并且可以从硬件上保证按内容并行查找 一般用来存放当前访问最频繁的少数活动页面的页号

页面置换算法

• 最优算法OPT 往往用于用来对比其他算法与最优算法的理论差距 没办法实现
• 随机算法RAND
• 先进先出FIFO 有可能产生抖动 即分配资源越多可能还会使缺页越多
• 最近最少使用算法LRU 不会抖动 即分配资源越多性能越好

没有使用快表的情况下 每个页面访问内存需要2次 所以需要访问12次内存

如果一个指令横跨两个页 指令只会缺页一次 而操作数会缺页两次

文件管理

索引文件结构

（计算题需补充）

文件与树型目录结构

文件属性

• R只读文件属性
• A存档属性
• S系统文件
• H隐藏文件

文件名的组成

• 驱动器号
• 路径
• 主文件名
• 扩展名

绝对路径：从盘符开始的路径

相对路径：从当前路径开始的路径

空闲存储空间的管理

• 空闲区表法（空闲文件目录）
• 空闲链表法
• 位示图法：将空间用01来表示是否空闲
• 成组链接法

设备管理

数据传输控制方式

指内存和外设间的控制传输方式

• 程序控制方式 需要CPU介入 发出相应的查询指令查询是否传输完
• 程序中断方式 外设完成相应的传输后会自动发出中断信号
• DMA方式 直接程序控制方式有专门的控制器 全程由DMA控制器来完成
• 通道 包括字节多通道和选择通道的传送方式
• 输入输出处理机

虚设备和SPOOLING技术

SPOOLING技术相当于一个队列 加入缓冲区来防止出现一台打印机一直被占用的情况

微内核操作系统

把一些文件系统 存储系统等放在内核之外 把微内核缩之最小 这样存储系统等出现故障时就不会影响到核心