第一章、计算机基础知识

+0、-0 原码反码补码移码

+0 原码,正数原码反码补码移码一样
0000 0000
反码: 
0000 0000
补码：
0000 0000
移码： 
0000 0000

-0原码
1000 0000
反码：原码 绝对值 取反
1111 1111
补码：反码+1,符号位一样进一
0000 0000
移码：补码符号位取反
0000 0000

浮点数 1.5 x 10^3

浮点数的精度由尾数决定,数的表示范围由阶码的位数决定。浮点数相加时，需要先对阶，将小阶向大阶对齐，对阶时通过较小数的尾数右移实现。

CPU

运算器：

  • 算数逻辑单元ALU
  • 累加寄存器 （暂存运算结果）
  • 数据缓冲寄存器
  • 状态条件寄存器

控制器： （保证指令正确执行，处理异常事件）

  • 指令寄存器IR (操作码和地址码，完全透明)
  • 程序计数器PC (程序员可以访问，跟踪指令地址的寄存器)
  • 指令译码器 (指令译码)
  • 时序部件

寻址方式：

目的：扩大寻址空间并提高编程灵活性

立即寻址：给出的指令就是操作数本身 #45

直接寻址：在指令地址段中直接指出操作数在内存的地址

寄存器寻址：指令给出通用寄存器的编号（操作数不在内存，在寄存器中） MOV R1

按寻址方式的存储器： 随机存储器、顺序存储器、直接存储器

按内容方式访问的存储器： 相联存储器

第二章：计算机组成和体系结构

字节

字长 需要地址算大小需要乘8bit 变为字节

​ 16^5

400 FFFFFH - 400 00000H + 1 = 100000 4*5=20 2^20 =1024*1024 = 1024K = 1024k * 8bit

1024k * 8bit / 256K*8bit =4片,

DCFFFH - A5000H = 38000H 每位算差值就可以了。

3*16^4 + 8*16^3

DABFF - B3000 = 27c00 = 2*16^4 +7*16^3 + 12*16^2

内存按字节编码 DFFFF - A0000 = 50000 = 4*16^4 = 4 *2^16 = 4 *2^6 kb * 8bit / 32k * 8bit =

第三章 数据结构

3.2 非线性结构

数组、三对角矩阵

3.3.3 树

  • 二叉树

    每个节点最多有两个子树

  • 满二叉树

image-20210616125334106.png

  • 完全二叉树

image-20210616125529271.png

除了最后一层不是满的，其他层都是满的

  • 非完全二叉树

性质:

  1. 第 i 层上最多有 $2^(i - 1)$ 个节点
  2. 深度 k 最多有 $2^k-1$ 个节点
  3. 具有 n 个节点的完全二叉树的深度为 $log_2 n +1$ ，2^3=10 3层加1层=4层

二叉树的存储结构：

  • 顺序存储 完全二叉树节约空间，一般二叉树会浪费空间，有虚节点，最坏情况下（一条边链，需要用存储单元 $2^k-1$ 个）
  • 链式存储 使用链表进行存储，每个节点包含左右子树的根信息和自己节点 data

遍历方式：

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中
  • 层序遍历：从上到下，从左到右

最优二叉树(哈夫曼树)：带权路径长度最小（每个节点权值*到根路径深度）

图的遍历:深度优先、广度优先

通信加密：S 将所发送的信息适用 S 的私钥进行数字签名，T 收到后使用 S 的公钥进行验证消息的真实性。

数字签名：用户 B 收到用户 A 的数字签名信息 M，为了验证 M 的真实性，从 CA 获取 A 的数字证书，利用 CA 的公钥验证证书的真伪，利用 A 的公钥验证消息 M 的真伪。

第四章 操作系统知识

操作系统 OS 有两个重要的作用:

  • 第一 通过资源管理提高计算机系统的效率;
  • 第二 改善人 机界面向用户提供友好的工作环境。

操作系统特征与功能

  1. 进程管理
  2. 文件管理
  3. 存储管理
  4. 设备管理
  5. 作业管理

操作系统分类：

  • 批处理操作系统：

    单道：一次一个，自动下个作业

    多道：宏观上并行，微观上串行

  • 分时操作系统

    在分时操作系统中，一个计算机系统与多个终端设备连接。例如，一个带 20 个终端的分时系统，若每个用户每次分配一个 50ms 的时间片,则每隔 1s 即可为所有的用户服务一遍。 因此，响应时间为 1s。

  • 实时操作系统

    限制访问有限的专用程序。实时系统对交互能力要求不高。因此，实时系统对响应时间的敏感程度更强。

  • 网络操作系统

  • 分布式操作系统

    分布式操作系统是网络操作系统的更高级形式，它保持网络系统所拥有的全部功能，同时 又有透明性、可靠性和高性能等特性。

  • 微型计算机操作系统：win、macOS、linux

  • 嵌入式操作系统

    微型化、可定制、实时性较高、可靠性、易移植性

进程管理

程序和进程

其中输入是计算的前驱(计算是输入的后继)，输入结束才能进行计算；计算是输出的前驱，计算结束才能进行输出。并发图里面：竖着看，$C_1$、$I_2$ 并发执行，$P_1$$C_2$$I_3$ 并发执行，$P_2$$C_3$ 并发执行。斜着看制约，$I_1$ 间接制约 $I_2$$I_3$，$C_1$ 间接制约 $C_2$$C_3$，$P_1$间接制约 $P_2$$P_3$

并发特征:

  • 失去了程序的封闭性
  • 程序和机器的执行程序不在一一对应
  • 并发程序间相互制约性

进程由程序、数据、进程控制块 PCB 组成的。

基本状态：

进程间通信

同步和互斥：同步A要等B执行完才可以执行完，互斥AB请求打印机只能一个访问。

信号量机制：使用同步和互斥的工具 P V 操作，P 申请资源 V 释放资源

进程调度：

  • 高级调度 长调度，系统中的一个作业只需经过一次高级调度，调入主系统做好运行准备
  • 中级调度 决定交换区中那个就绪进程调入内存
  • 低级调度 决定内存中那个就绪进程可以占用CPU

调度算法：

  1. 先来先服务 FCFS ，有利于长作业、CPU繁忙作业；不利于短作业、IO繁忙作业

  2. 时间片轮转

    固定时间片、可变时间片。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;

  3. 优先级调度

    静态优先级、动态优先级

  4. 多级反馈调度

进程优先级确定：IO型进程执行小时间片，对于计算型采用最大时间片来执行。IO次数不多CPU多使用，返回IO的优先级队列

​

死锁：

产生的4个必要条件：互斥条件、请求保持条件、不可剥夺条件、环路条件

死锁处理：鸵鸟策略、预防策略（预先静态分配、资源有序分配）、避免策略、检测和解除死锁（资源剥夺、撤销进程）

线程：可拥有资源独立单位；可独立调度和分配的基本单位。

存储服务：

  1. 虚拟地址：数据存放地址是有符号决定的，符号名为地址

  2. 地址空间：把程序中由符号组成的空间成为空间

  3. 存储空间：地址空间的物理合集

地址重定位：

地址重定位是指将逻辑地址变换成主存物理地址的过程。

  • 静态重定位：程序装入主存时已经完成了地址变换
  • 动态重定位：程序运行是变化，实现机制依赖硬件地址变换机构如基地地址寄存器 BR

存储管理方案

1.分区存储管理 固定分区、可变分区、可重定位分区（会靠拢已分配分区，解决碎片）

可变分区请求释放算法

  1. 最佳适应算法：选个最接近的大小分区，大点的还是会产生碎片
  2. 最差适应算法：总是将用户作业装入最大的空白分区，不易产生碎片
  3. 首次适应算法：从低地址开始选择一个能装入作业的空白分区，释放空间时易合并
  4. 循环首次适应算法：每次分配都是从刚分配的空白开始寻找一个能满足用户要求的空白区

分页存储管理

1.分页原理：将一个进程的地址空间划分为若干个相等的区域，称为页。

地址结构

页表：

映射进程和所要访问的物理块。

2.分段式存储管理

主程序段、子程序段、数据段、堆栈段

段表

段寄存器：用于存放段表起始地址和段表长度

3.段页式存储管理

段页式将用户程序按逻辑关系分为若干段，为每个段赋予一个段名，将每个段分为若干页，以页框为单位离散分配。

段表寄存器，用于存放段表其实地址和段表长度

同时配置段表和页表

段表存放页表的起始地址和页表长度

4.虚拟存储管理

  • 时间局部性：循环再次请求该存储单元
  • 空间局部性： 程序按顺序执行，存储单元附近的也可能访问到

虚拟存储器：页式虚拟存储管理、段氏虚拟存储管理、段页式虚拟存储管理

页式虚拟存储管理：在分页系统的基础上增加了请求调页和页面置换功能

5.页面置换算法

  • 最佳置换算法，性能最好难于实现
  • 先进先出置换算法，性能最差
  • 最近最少未使用
  • 最近未使用

设备管理

第五章 软件工程

软件生存周期：

  1. 可行性分析与项目开发计划。产生文档：可行性分析报告、项目开发计划
  2. 需求分析。产生文档：软件需求说明书
  3. 概要设计。设计软件的结构，产生文档：概要设计说明书
  4. 详细设计。产生文档：详细设计文档
  5. 编码
  6. 测试。产生文档：软件测试计划、测试用例、测试报告
  7. 维护。

软件基本特性：

功能性、可靠性（成熟性、容错性、易恢复性）、易使用性、效率、可维护性、可移植性

统一过程 （UP）： 为复杂软件项目开发提供成熟的、统一的、系统的、广泛适用的方法。

SEI 能力成熟模型（SEUCMM）

  • 初始级别：无秩序
  • 可重复级别：又类似项目经验（有章可循）
  • 已定义级别：文档化、标准化
  • 已管理级别：有软件过程和产品质量度量标准
  • 优化级别：能对新概念、新技术进行吸收改进

软件模型

瀑布模型：

需求分析、设计、编码、测试、运行与维护

优点：容易理解、成本低、强调开发阶段性

缺点：1.很难评估项目状态 2.项目快要结束时出现大量集成和测试的工作 3.项目结束前不能演示系统 4.错误往往要到项目后期才能被发现，对项目控制能力较弱，导致项目通常延期，经费超支。

V模型

需求 >> 验收测试

概要设计 >> 系统测试

详细设计 >> 集成测试

编码 >> 单元测试

增量模型：

可以快速交付第一版本

缺点：一些增量可能需要重新开发，对进度、成本、配置管理会更复杂

演化模型：原型模型、螺旋模型

原型模型：

沟通需求开发再迭代

螺旋模型：

结合瀑布模型和演化模型，加入了风险分析。适用于庞大、复杂、高风险的系统。

喷泉模型：

以客户需求为动力，以对象为驱动。

统一过程模型：由UML方法和工具支持

  • 起始阶段：初始用例模型

  • 精华阶段：用例模型、初步设计模型，修订风险列表、项目计划、初始用户手册

  • 构建阶段：设计模型

  • 移交阶段：测试报告、综合用户反馈。

需求分析

原则：

  1. 必须能表示和理解问题的信息域
  2. 必须能定义软件将要完成的任务
  3. 必须能表示软件的行为
  4. 必须划分描述数据、功能和行为的模型
  5. 分析过程应该要从要素信息移向细节信息

系统设计常用方法：面向数据流SD，面向对象OOD。基本步骤：概要设计、详细设计

测试

系统测试包括：软件测试、硬件测试、网络测试

测试策略：单元测试、集成测试、确认测试（确认测试始于集成测试的结束，配置评审）、系统测试（恢复测试、安全性测试、压力测试、性能测试、部署测试）

测试方法：黑盒测试（功能测试）、白盒测试（结构测试）

项目管理

人员person、产品product、过程、process、项目project

项目估算

进度管理：甘特图（表示任务的开始时间、当前进度、计划完成时间）、项目计划评审图PERT（可以表达任务的先后次序及其时间要素）

软件质量：

软件评审：设计质量评审、程序质量评审、与运行环境的接口 实现容错的主要手段是冗余

软件配置管理：基线、软件配置项、版本控制、变更控制（开发库、受控库、产品库）

软件风险管理：风险控制最好的办法就是主动的避免风险。

耦合方式：

数据耦合：两个模块通过数据交换信息。

标记耦合：两个模块同数据结构交换信息。

控制耦合：一个模块间通过开关、标记控制另一个模块。

内容耦合：直接访问另一模块内部数据、代码重叠、模块多入口

辅助软件维护过程中的活动的软件称为“软件维护工具”，它辅助维护人员对软件代码及其文档进行各种维护活动。软件维护工具主要有：1、版本控制工具；2、文档分析工具；3、开发信息库工具；4、逆向工程工具；5、再工程工具；6、配置管理支持工具。

上次更新时间: 2024/5/7 05:59:02

← JMM→