软件设计师教程思维导图模板_ProcessOn思维导图、流程图

计算机系统知识

计算机系统基础知识

计算机系统硬件基本组成

硬件

运算器

控制器

存储器

内部存储器

速度高

容量小

外部存储器

容量大

速度慢

输入设备

输入原始数据

输入各种命令

输出设备

输出计算机运行结果

软件

中央处理单元

核心部件

获取程序指令

对指令

进行译码

执行

CPU的功能

程序控制

操作控制

时间控制

数据处理

对系统内部和外部

中断（异常）做出响应

进行相应的处理

CPU的组成

运算器

主要功能

执行所有的算术运算

执行所有的逻辑运算并进行逻辑测试

各个部件及其功能

算术逻辑运算(ALU)

累加寄存器（AC)

数据缓存寄存器(DR)

状态条件寄存器(PSW)

控制器

步骤

取指令

指令译码

指令操作码执行

组成

指令寄存器（IR)

程序计数器（PC)

地址寄存器（AR)

指令译码器（ID)

寄存器组

多核CPU

数据表示

原码,反码,补码和移码

原码表示法

反码表示法

补码表示法

移码表示法

浮点数

工业标准IEEE 754

浮点数的运算

效验码

奇偶效验码

海明码

循环冗余效验码

计算机体系结构

计算机体系机构发展

计算机体系结构概述

三者关系

计算机体系结构（Computer Architecture)

计算机组织(Computer Organization)

计算机实现(Computer Implementation)

计算机体系结构分类

从宏观按处理机数量分类

单处理系统

并行处理与多处理系统

分布式处理系统

从微观按并行程度分类

Flynn分类法

冯泽云分类法

Handler分类法

Kuck分类法

指令系统

指令集体系结构分类

操作数在CPU中的存储方式

显式操作数的数量

操作数的位置

指令的操作

操作数的类型与大小

按暂存机制分类

堆栈（Stack）

累加器（Accumulator）

寄存器组（ a set of Registers)

CISC和RISC
指令集发展的两种途径

CISC

主要弊端

指令集过分庞杂

每条复杂的指令要执行一段解释性微程序

需要多个周期

降低机器的处理速度

指令系统过分庞大

选择目标指令范围大

编译程序本身

冗余

复杂

难以优化编译使之生成真正的高效的目标代码

CISC强调完善的中断控制

动作繁多

设计复杂

研制周期长

芯片设计带来很多困难

芯片种类增多

出错几率增大

成本提高而成品率降低

RISC

关键技术

重叠寄存器窗口技术

优化编译技术

超流水及超标量技术

硬布线逻辑与微程序相结合

优化

指令的流水处理

指令控制方式

顺序方式

重叠方式

流水方式

流水线的种类

级别

部件级

处理机级

系统级

功能

单功能流水线

多功能流水线

连接

静态流水线

动态流水线

反馈回路

线性流水线

非线性流水线

流动顺序

同步流水线

异步流水线

数据表示

标量流水线

向量流水线

流水的相关处理

RISC中采用的流水技术

超流水线

超标量

超长指令字

吞吐率和流水建立时间

陈列处理机，并行处理机和多处理机

并行处理分类
（从计算机信息处理步骤和阶段）

存储器操作并行

处理器操作步骤并行（流水线处理机）

处理器操作并行（陈列处理机）

指令，任务，作业并行

多处理机

分布处理机

计算机网络

陈列处理机

并行处理机

多处理机

其他计算机

存储系统

存储器的层次结构

存储器的分类

所处位置分类

内存

外存

构成材料分类

磁存储器

半导体存储器

静态

动态

光存储器

工作方式分类

读/写存储器

只读存储器

固定只读存储器

可编程的只读存储器

可擦除可编程的只读存储器

电擦除可编程的只读存储器

闪速存储器

访问方式

按地址访问存储器

按内容访问存储器

寻址地址方式

随机存储器

顺序存储器

直接存储器

相联存储器

高速缓存

高速缓存的组成

高速缓存中的地址映像方法

直接映像

全相联映像

组相联映像

替换算法

随机替换算法

先进先出算法

近期最少算法

优化替换算法

Cache的性能分析

多级Cache

虚拟存储器

外存储器

磁表面存储器

光盘存储器

固态硬盘

磁盘陈列技术

存储域网络

输入\输出技术

微型计算机中最常用的内存与接口的编址方法

内存与接口地址单独编址方式

内存与接口方式统一编址方式

直接程序控制

无条件传送

程序查询方式

缺点

降低了CPU的效率

对外部的突发事件无法做出实时响应

中断方式

中断处理方法

多中断信号线法

中断软件查询法

菊花链法

总线仲裁法

中断向量法

中断优先级控制

CPU先相应优先级最高的中断源

中断嵌套

直接存储器存取方式

输入/输出处理机(IOP)

总线结构

总线的分类

数据总线

地址总线

控制总线

常见总线

ISA总线

EISA总线

PCI总线

PCI Express 总线

前端总线

RS-233C

SCSI总线

SATA

USB

IEEE-1394

安全性，可靠性与系统性能测评
基础知识

计算机安全概述

计算机的安全等级

安全威胁

影响数据安全的因素

加密技术和认证技术

加密技术

对称加密技术

数据加密标准

三重DES（3DES/TDEA)

RC-5

国标数据加密算法

高级加密标准

非对称加密技术

密钥管理

密钥产生

密钥备份和恢复

密钥更新

多密钥的管理

认证技术

Hash函数与信息摘要

MD5算法的特点

压缩性

容易计算

抗修改性

强抗碰撞

数字签名

数字签名过程

数字加密过程

SSL协议

服务

用户和服务器的合法性认证

加密数据以隐藏被传送的数据

保护数据的完整性

SSL(安全套接层）过程阶段

接通阶段

密码交换阶段

会谈密码阶段

检验阶段

客户认证阶段

结束阶段

数字时间戳技术

时间戳部分

需加时间戳的文件摘要

DTS收到文件的日期和时间

DTS的数字签名

计算机可靠性

计算机可靠性概述

计算机可靠性模型

串联系统

并联系统

N模冗余系统

计算机系统的性能评价

性能测评的常用方法

时钟频率

指令执行速度

等效指令速度法

数据处理速率

核心程序法

基准测试程序

整数测试程序

浮点测试程序

理论峰值浮点速度

Linpack基准测试程序

Whetstone基准测试程序

SPEC基准程序

TPC基准程序

程序设计语言基础知识

程序设计语言概述

程序设计语言的基本概念

低级语言和高级语言

低级语言

机器指令程序

汇编语言

高级语言

编译程序和解释程序

翻译形式

汇编

解释

编译

源程序

用某种高级语言

汇编语言

解释程序也称解释器

直接解释执行源程序

将源程序翻译成某种中间代码后再执行

编译程序（编译器）

将源程序翻译成目标语言程序

再计算机上运行目标程序

编译方式和解释方式
根本区别

编译方式

机器上运行的与源程序等价的目标程序

不参与目标程序的执行过程

源程序

编译程序

解释方式

要参与到程序的运行过程中

解释程序

源程序

运行程序的控制权在解释程序

程序设计语言的定义

程序设计语言的分类

程序设计语言发展概述

程序设计语言分类

命令式和结构化程序设计语言

面向对象的程序设计语言

函数式程序设计语言

逻辑型程序设计语言

程序设计语言的基本成分

基本成分

数据

运算

控制

传输

程序设计语言的数据成分

常量和变量

全局量和布局量

数据类型

基本类型

特殊类型

用户定义类型

构造类型

指针类型

抽象数据类型

程序设计语言的运算成分

程序设计语言的控制成分

顺序结构

选择结构

循环结构

C(C++)语言提高的控制语句

复合语句

if语句和switch语句

循环语句

while语句

do-while语句

for语句

程序设计语言的传输成分

函数

函数定义

函数声明

函数调用

值调用

引用调用

语言处理程序基础

汇编程序基本原理

汇编语言

指令语句

伪指令语句

宏指令语句

汇编程序

编译程序基本原理

编译过程概述

词法分析

语法分析

语义分析

中间代码生成

代码优化

目标代码生成

符号表管理

出错处理

文法和语言的形式描述

字母表，字符串，字符串集合及运算

文法和语言的形式描述

文法的定义

文法的分类

句子和语言

文法的等价

词法分析

正规表达式和正规集

有限自动机

确定的有限自动机

不确定的有限自动机

NFA到DFA的转换

DFA的最小化

正规式与有限自动机之间的转换

词法分析器的构造

语法分析

上下文无关文法

规范推导（最右推导）

短语，直接短语和句柄

自顶向下语法分析方法

消除文法的左递归

消除直接左递归

消除文法中的一切左递归

提前公共左因子

LL(I)文法

递归下降分析法

预测分析法

自底向上语法分析方法

LR分析器组成

驱动器

分析表

分析栈

LR分析过程，
改变格局的动作

移进

归约

接受

报错

语法制导翻译和中间代码生成

中间代码

后缀式（逆波兰式)

树形表示

三元式表示

四元式表示

常见语法结构的翻译

赋值语句及简单算术表示式的翻译

布尔表达式的翻译

常见语句的翻译

动态存储分配和过程调用的翻译

中间代码优化和目标代码生成

中间代码形式

目标代码形式

寄存器的分配

计算次序的选择

解释程序基本原理

解释程序的基本结构

高级语言编译与解释方式的比较

效率

灵活性

可移植性

数据结构

线性结构

线性表

线性表的定义

非空线性表的特点

存在唯一的一个称作“第一个”的元素

存在唯一的一个称作“最后一个”的元素

除第一个元素外，序列中的每个元素均只有一个直接前驱

除最后一个元素外，序列的每个元素均只有一个直接后继

线性表的存储方式

线性表的顺序存储

用一组地址连续存储单元依次存储线性表中的数据元素

从而使得逻辑上相邻的两个元素在物理位置上也相邻

元素间的逻辑关系上无须占用额外空间

优缺点

可以随机存取表中的元素

插入和删除操作需要移动元素

线性表的链式存储

通过指针链接起来的结点来存储数据元素

基本节点结构

数据域用来存储数据元素的值

指针域存储当前元素

直接前驱

直接后驱

指针域中的信息成为指针（或链）

优缺点

不能对数据元素进行随机访问

具有插入和删除操作不需要移动元素

其他的几种链表结构

双向链表

每个节点包含两个指针

直接前驱

直接后驱

特点

可以从表中任意的结点出发

从两个方向上遍历链表

循环链表

在单向链表（或双向链表）基础上令表尾结点的
指针指向链表的第一个结点，构成循环链表

特点

可以从表中任意结点开始遍历整个链表

静态链表

借助数组来描述线性表的链式存储结构

用数组元素的下标表示元素所在结点的指针

栈和队列

栈按“后进先出”的规则进行操作

队列按“先进先出”的规则进行操作

栈

栈的定义及基本运算

栈的定义

一种线性数据结构

数据存储

检索

又称后进先出的线性表

栈的基本运算

初始化栈InitStack(S)

创建一个空栈

判栈空isEmpty(S)

当栈S为空时返回“真”
否则返回“假”

入栈Push(S,x)

将元素x加入栈顶

并更新栈顶指针

出栈Pop(S)

将栈顶元素从栈中删除

并更新栈顶指针

读栈顶元素Top（S)

返回栈顶元素的值

但不修改栈顶指针

栈的存储结构

顺序存储

采用顺序存储的栈也称顺序栈

栈的链式存储

用链表作为存储结构的栈也称链栈

链表的头指针就是栈顶指针

栈的应用

队列

队列的定义及基本运算

队列的定义

先进先出的线性表

允许插入元素的一端称为队尾

允许删除元素的一端称为对头

队列的基本运算

初始化队列InitQueue(Q)

创建一个空的队列Q

判队空isEmpty(Q)

当队列为空时返回“真”
否则返回“假”

入队EnQueue(Q,x)

将元素x加入到队列Q的队尾

并更新队尾指针

出队DelQueue(Q)

将对头元素从队列Q中删除

并更新对头指针

读对头元素FrontQue(Q)

返回对头元素的值

但不更新对头指针

队列的存储结构

队列的顺序存储

又称顺序队列

元素入队时只修改队尾指针

元素出队时只修改队头指针

队列的链式存储

也称链队列

给链队列添加一个头结点
并令头指针指向头结点

队列的应用

串

串的定义及基本运算

串的定义

串是仅由字符构成的有限序列，是一种线性表

S是串名

单引号括起来的字符序列是串值

串的几个基本概念

空串

长度为零的串称为空串

空串不包含任何字串

空格串

由一个或多个空格组成的串

空格虽然是一个空白字符，
但它也是一个字符

子串

由串中任意长度的连续字符构成的序列称为子串

含有子串的串为主串

子串在主串中的位置

子串首次出现时

该子串的第一个子串在主串中的位置

空串是任意串的子串

串相等

两个串长度

对应序号的字符

串比较

两个串比较大小时以字符的ASCII码值(或其他字符编码集合)作为依据

比较操作从两个串的第一个字符开始进行

字符的码值大者所在的串为大

若其中一个串先结束，则以串长较大者为大

串的基本操作

赋值操作StrAssign(s,t)

将串s的值赋给串t

连接操作Concat(s,t)

将串t接续在串s的尾部

形成一个新串

求串长StrLength(s,t)

返回串s的长度

串比较StrCompare(s,t)

比较两个串的大小

返回值

-1表示s<t

0表示s=t

1表示s>t

求子串

返回串s中start开始

长度为len的字符序列

串的存储结构

串的顺序存储结构

指用一组地址连续的存储单元来存储串值的字符序列

由于串中的元素为字符

可通过程序语言提供的字符数组定义串的存储空间

也可以根据串长的需要动态申请字符串的存储空间

串的链式存储

当用链表存储串的字符时

每个节点中可以存储一个字符

也可以存储多个字符

在链式存储结构中，结点大小的选择会直接影响对串的处理效率

串的模式分配

子串的定位操作通常称为串的模式匹配

是各种串处理系统中的最重要的运算模式之一

子串也称模式串

朴素的模式匹配算法

也称布鲁特-福斯算法

改进的模式匹配算法

也称KMP算法

数组，矩阵和广义表

数组与广义表可以看作是线性表的推广
其特点是数据元素仍然是一个表

数组

数组的定义及基本运算

数组的定义

数组是定长线性表在维数上的扩展

线性表中的元素又是一个线性表

n维数组

一种"同构"的数据结构

每个数据元素类型相同，结构一致

数组结构的特点

数据元素数目固定

一旦定义了一个数组结构

就不再有元素个数的增减变化

数据元素具有相同的类型

数据元素的下标关系具有上下界的的约束且下标有序

数组的两个基本运算

给定一组下标，存取相应的数据元素

给定一组下标，修改相应的数据元素中某给数据项的值

程序语言中把数组看作具有相同某种的同一类型的多个变量的集合

数组的顺序存储

数组一般不做插入和删除运算

一旦定义了数组

结构中的数据元素个数

元素之间的关系

数组适合采用顺序存储结构

二维数组的存储结构

以行为主序

以列为主序

矩阵

为了节省存储空间

多个值相同元素只分配一个存储单元

对0不分配存储单元

假如值相同的元素或0元素在矩阵中的分布有一定规律

则称为特殊矩阵

否则称为稀疏矩阵

特殊矩阵

若矩阵中的元素(或非0元素)的分布有一定的规律，
则成为特殊矩阵

常见的特殊矩阵

对称矩阵

三角矩阵

对角矩阵

稀疏矩阵

广义表

广义表的定义及其概念

广义表是线性表的推广，
是由0个或多个单元素或子表组成的有限序列

区别

线性表的元素都是结构上不可分的单元素

广义表的元素

既可以是单元素

也可以是有结构的表

广义表一般记为：
LS=()

既可以是单元素

又可以是广义表

分别称为

原子

子表

广义表

长度:广义表中元素的个数

深度:广义表展开后所含的括号最大层数

广义表的基本操作

广义表也有查找，删除和插入等操作

但广义表结构复杂

不如线性表实现简单

两个重要运算

取表头head(LS)

非空广义表LS的第一个元素称为表头

它可以是单元素

也可以是一个子表

去表尾tail(LS)

在非空广义表中，除表头元素外

由其余元素所构成的表称为表尾

非空广义表的表尾必定是一个表

广义表的特点

广义表可以是多层次的结构

广义表的元素可以是子表

子表的元素还可以是子表

广义表中的元素

可以是已经定义的广义表的名字

一个广义表可被其他广义表所共享

广义表

可以是一个递归的表

广义表的元素可以是本广义表的名字

广义表的存储结构

由于广义表中的元素本身可以是具有结构

它是一种带有层次的非线性结构

通常采用链式存储结构

若广义表不空可分解为

表头

表尾

树

树与二叉树的定义

树结构是一种非常重要的非线性结构

该结构的一个数据元素可以

两个

两个以上

树可以描述客观世界中广泛存在的层次结构关系

树的定义

树是n(n>0)个结点的有限集合

当n=0时，树为空树

在任一非空树(n>0)时，
有且仅有一个称为根的结点

树的定义是递归的

表明了树本身的固有特性

一颗树由若干棵子树构成

子树由更小的子树构成

树的基本概念

双亲

结点的子树的根称为该节点的孩子

该结点称为其子结点的双亲

具有相同双亲的结点互为兄弟

结点的度

一个结点的子树的个数记为该节点的度

叶子结点

叶子节点也称终端结点

指度为0的结点

内部结点

度不为0的结点

分支节点

非终端结点

除根节点以外，分支节点也称内部结点

结点的层次

根为第一层

根的孩子为第二层

树的高度

一颗树的最大层数记为树的高度(或深度)

有序(无序)树

若将树中结点的各子树看成从左到右具有次序的，
既不能交换

则称该树为有序树

否则称无序树

二叉树的定义

它或者是空树(n=0)

一个根结点但及两棵不相交的且

二叉树同样具有递归性质

区别

二叉树中结点的子树要区分左子树右子树

既是在结点只有一颗子树的情况下，
也要明确指出该子树是左子树还是右子树

二叉树结点最大度为2

树中不限结点的度数

二叉树的性质与存储结构

二叉树的性质

性质

二叉树第i层上最多有

高度为k的二叉树最多有的结点

对于任何一颗二叉树，若其终端结点数为，则称

具有n个结点的完全二叉树的深度为

分类

完全二叉树

深度为k，有n个结点的二叉树

当且仅当其每一个结点都与深度为k的满二叉树
中编号从1至n的结点一一对应时

非完全二叉树

在一个高度为h的完全二叉树中

除了第h层(即最后一层),其余各层都是满的

在第h层上的结点必须从左到右依次放置，不能留空

二叉树的存储结构

二叉树的顺序存储结构

顺序存储是用一组地址连续的存储单元二叉树中的结点

必须把结点排成一个适当的线性序列

结点在这个序列中的相互位置能反映除结点之间的逻辑关系

假如有编号为i的结点，则有

若i=1，则该节点为根节点，无双亲；
若i>1,则该结点的双亲结点为[i/2]

若

若，则该节点的有孩子编号为2i+1，否则无右孩子

在最坏情况下，一个深度为k且只有k个结点的二叉树(单支树)需要个存储单元

二叉树的链式存储结构

由于二叉树的结点包含

数据元素

左子树的根

右子树的根

双亲

链表的头指针指向二叉树的根节点

二叉树的遍历

先序

先访问根

再依次访问左子树(从左到右)

后序

先访问左子树

再访问右子树

最后访问根

层次

先访问根

再按层次从左往右依次访问

中序

先访问左子树

再访问根

最后访问右子树

线索二叉树

线索二叉树的定义

二叉树遍历的本质

对一个非线性结构进行线性化的过程

使得每个结点
(除第一个和最后一个)
在这些线性序列中有且仅有一个

直接前驱

直接后继

在二叉链表存储结构中

只能找到一个结点的

左孩子

右孩子

不能直接得到结点在任一遍历序列中

前驱

后继

这些信息是只有在遍历的动态过程中才能得到

引入线索二叉树来保存这些动态过程的信息

建立线索二叉树

若二叉树的二次链表采用上述结点

则对于的链表称为线索链表

其指向结点前驱，后继的指针称为线索

加上线索的二叉树称为线索二叉树

对二叉树以某种次序遍历
使其称为线索二叉树的过程
称为线索化

按某种次序将二叉树线索化

实质上是在遍历过程中用线索取代空指针

访问线索二叉树

最优二叉树

最优二叉树又称哈夫曼树

一类带权路径长度最短的树

路径是从树中一个结点到另一个结点的通路

路径上的分支数目称为路径长度

树的路径长度是从树根到每一个叶子之间的路径长度之和

结点的带权路径长度

为该结点到树根之间的路径长度

与该节点权值

树的带权路径长度

树中所有叶子结点的带权路径长度之和

记为：WPL=

n为带权叶子结点数目

为叶子节点的权值

为叶子节点到根的路径长度

哈曼夫算法

若对每个字符编制相同长度的二进制码，则称为等长编码

任一字符的编码都不是另一个字符的编码的前缀，
这种编码称为前缀码

树和森林

树的存储结构

树的双亲表示法

用一组地址连续的单元存储树的结点

并在每个结点中附设一个指示器

指出其双亲结点在该存储结构中的位置
(即结点所在数组元素的下标)

树的孩子表示法

用指针指示出

结点的每个孩子

为树中每个结点的孩子建立一个链表

令每个结点的所有孩子结点

构成一个用单链表表示的线性表

n个结点的树具有n个单链表

孩子兄弟表示法

又称二次链表表示法

树和森林的遍历

树的遍历

树的先根遍历

树的后根遍历

森林的遍历

先序遍历森林

中序遍历森林

树,森林和二叉树之间的相互转化

树,森林转换为二叉树

二叉树转换为树和森林

图

图的定义与存储

图是比树结构更复杂的一种数据结构

在线性结构中

除首结点没有前驱

末尾结点没有后继

一个结点只有

唯一的一个直接前驱

唯一的一个直接后继

在图中

任意两个结点之间都有可能有直接关系

图中的结点的

前驱结点

后继结点

图的定义与存储

图的定义

有向图

无向图

完全图

度,出度和入度

路径

子图

连接图与连通分量

强连通图与强连通分量

网

有向树

图的存储结构

邻接矩阵表示法

邻接链表表示法

图的遍历

深度优先搜索(DFS)

类似树的先根遍历

在第一次经过一个顶点式就进行访问操作

从图G中任一结点v出发按深度优先搜索进行遍历的步骤

设置搜索指针p,使p指向顶点v

访问p所指顶点，并使p指向与其相邻接的且尚未访问过的顶点

若p所指顶点存在,则重复步骤(2)，否则执行步骤(4)

沿着刚才访问的次序和方向

回溯到一个尚有邻接顶点且未访问过的顶点

并使p指向这个未被访问的顶点

然后重复步骤(2)

直到所有的顶点均被访问为止

这个算法特点

尽可能先纵深方向搜索

可以得到其递归遍历算法

广度优先搜索(BFS)

方法

从图中的某个顶点v出发

在访问了v之后依次访问v的各个未被访问的邻接点

分别从这些邻接点出发依次访问它们的邻接点

并使"先被访问的顶点的邻接点"先于"后被访问的顶点的邻接点"被访问

直到图中所有已被访问的顶点的邻接点被访问到

在广度优先遍历算法中，每个顶点最多进一次队列

生成树及最小生成树

生成树的概念

极小连通子图

对于有n个顶点的连通图

至少有n-1条边

而生成树中恰好有n-1条边

连通图的生成树是该图极小连通子图

图的生成树不是唯一的

从不同的顶点出发

选择不同的存储方式

用不同的求解方法

最小生成树

概念

对于连通图来说

边是带权值

生成树的各边也带权值

生成树各边的权值总和称为生成树的权

把权值最小的生成树称为最小生成树

求解算法

普里姆(Prim)算法

克鲁斯卡尔(Kruskal)算法

拓扑排序和关键路径

AOV网

拓扑排序及其算法

对AOV网进行拓扑排序的方法

在AOV网中选择一个入度未0(没有前驱)的顶点且输出它

从网中删除该顶点及与该顶点有关的所有弧

重复上述两步，直到网中不存在入度为0的顶点为止

AOE网

关键路径和关键活动

顶点事件的最早发生时间ve(j)

顶点事件的最晚发生时间vl(i)

活动的最早开始时间e(k)

活动的最晚开始时间l(k)

最短路径

单源点最短路径

每对顶点间的最短路径

查找

查找的基本概念

基本概念

查找是一种常用的基本运算

查找表是指由同一类型的数据元素(或记录)构成的集合

查找表是一种非常灵活的数据结构

查找表经常要进行的两种操作

查询某个特定的数据元素是否在查找表中

检索某个特定的数据元素的各种属性

对查找表经常要进行的另外两种操作

在查找表中插入一个数据元素

从查找表中删除一个数据元素

动态查找表

在查找表中插入不存在的数据元素

从查找表中删除已存在的某个数据元素

关键字

数据元素(或记录)的某个数据项的值

用它来识别(标识)这个数据元素

主关键字是能唯一标识一个数据元素的关键字

次关键字是能标识多个数据元素的关键字

平均查找长度

静态查找表的查找方法

顺序查找

基本思路

查找成功

从表的一端开始，逐个将记录的关键字和给定值比较

若找到一个记录的关键字与给定值相等

查找失败

若整个表中的记录均比较过

仍未找到关键字等于给定值的记录

对于顺序存储方式和链式存储方式的查找表都适用

优缺点

顺序查找方法在n值较大时

其平均查找长度较大

查找效率较低

算法简单且适用广

对查找表的结构没有要求

无论记录是否按关键字有序排序均可应用

折半查找

分块查找

动态查找表

二叉排序树

平衡二叉树

B_树

哈希表

哈希表的定义

哈希函数的构造方法

处理冲突的方法

哈希表的查找

排序

排序的基本概念

简单排序

直接插入排序

冒泡排序

简单选择排序

希尔排序

快速排序

堆排序

归并排序

基数排序

内部排序方法小结

外部排序

操作系统知识

操作系统概述

操作系统的基本概念

操作系统定义及作用

操作系统定义

能有效地组织和管理系统中的各种软/硬件资源

合理地组织计算机系统工作流程

控制程序的执行

向用户提供一个良好的工作环境和友好的接口

操作系统作用

通过资源管理提高计算机系统的效率

改善人机界面向用户提供友好的工作环境

操作系统是计算机系统的资源管理者

操作系统的特征与功能

特征

并发性

共享性

虚拟性

不确定性

功能

进程管理

文件管理

存储管理

设备管理

作业管理

操作系统分类及特点

批处理操作系统

单道批处理

多道批处理

多道

宏观上并行处理

微观上串行处理

分时操作系统

多路性

独立性

交互性

及时性

实时操作系统

分类

实时控制系统

实时信息处理系统

区别

系统的设计目标不同

交互性的强弱不同

响应时间的敏感程度不同

网络操作系统

功能

高效

可靠的网络通信

对网络中共享资源的有效管理

服务

提供电子邮件

文件传输

共享

硬盘

打印机

网络安全管理

提供互操作能力

特征

硬件独立性

多用户支持

支持网络实用程序及其管理程序

多种客户端支持

提供目录服务

支持多种增值服务

分类

集中模式

客户端/服务器模式

对等模式(Peer-to-Peer)模式

分布式操作系统

微型计算机操作系统

嵌入式操作系统

主要特点

微型化

可定制

实时性

可靠性

易移植性

操作系统的发展

进程管理

进程管理又称处理机管理

基本概念

程序与进程

程序顺序执行的特征

顺序性

封闭性

可再现性

程序并发执行的特征

没有封闭性:失去了程序的封闭性

不可再现性:程序和机器的执行程序的活动不再一一对应

间断性:并发程序间的相互制约性

进程的组成

进程是程序的一次执行，该程序可以和其他程序并发执行

组成

PCB（进程控制块）

PCB是进程存在的唯一标识

主要内容

进程描述信息

进程控制与调度信息

资源信息

现场信息

PCB的内容

进程标识符

状态

位置信息

控制信息

队列指针

优先级

现场保护区

其他

程序

程序部分描述了进程需要完成的功能

数据

数据部分包括程序执行时所需的数据及工作区

进程的状态及其状态间的切换

三态模型

运行

就绪

阻塞

五态模型

具有挂起状态的进程状态及其转换

活跃就绪

静止就绪

活跃阻塞

静止阻塞

进程的控制

对系统中所有进程从创建道消亡的全过程实施有效的控制

进程控制是操作系统内核(Kernel)中的原语实现的

原语

指由若干条机器指令组成的，用于完成特定功能的程序段

特点

执行时不可被分割

原子操作要么做

原子操作要么不做

内核中原语主要包括

进程控制原语

进程创建原语

进程撤销原语

进程挂起原语

进程激活原语

进程阻塞原语

进程唤醒原语

进程通信原语

资源管理原语

其他方面的原语

进程间的通信

同步与互斥

同步是合作进程间的直接制约问题

互斥是申请临界资源进程间的间接制约问题

进程间的同步

进程间的互斥

临界区管理的原则

临界区(CS)是进程中对临界资源实施操作的那段程序

互斥临界区原则

有空即进

无空则等

有限等待

让权等待

信号量机制

主要

整型信号量

记录型信号量

信号量集机制

整型信号量与PV操作

公用信号量

私用信号量

利用PV操作实现进程的互斥

高级通信原语

PV操作属于低级通信方式

若用PV操作实现进程间通信，则存在以下问题

编程难度大，通信对用户不透明

效率低

高级通信主要分为

共享存储模式

消息传递模式

管道通信

管程

管程的引入

管程的结构

利用管程解决生产者-消费者问题

进程调度

调度

可剥夺

当有更高优先级的进程来到时

强行将正在运行的进程的CPU分配给高优先级的进程

不可剥夺

指当有更高优先级的进程来到时

必须等待正在运行进程自动释放占用的CPU

然后将CPI分配给高优先级的进程

三级调度

高级调度

又称

长调度

作业调度

接纳调度

决定处于

输入池中哪个后备作业可以调入主系统做好运行的准备

成为一个或一组就绪进程

在系统中一个作业只需经过一次高级调度

中级调度

又称

中程调度

对换调度

决定处于

交换区的哪个就绪程序可以调入内存

以便直接参与对CPU的竞争

低级调度

又称

短程调度

进程调度

决定处于

内存中的哪个就绪程序可以占用CUP

操作系统

最活跃

最重要

对系统的影响最大

调度算法

先来先服务(FCFS)

按照

作业提交

进程就绪状态

进程调度总是将就绪队列首的进程投入运行

特点

比较有利于长作业，而不利于短作业

有利于CPU繁忙的作业，而不利于I/O繁忙的作业

FCFS算法主要用于宏观调度

时间片轮转

时间片轮转算法主要用于微观调度

设计目标是提高资源利用率

通过时间片轮转提高

进程并发性

响应时间特性

选择方法

固定时间片

可变时间片

优先级调度

优先级调度算法

每个进程的有一个优先数

数值大的表示优先级高

系统调度时总选择优先数大的占用CPU

分为

静态优先级

进程的优先级在创建时确定，直到进程终止都不会改变

以下因素确定优先级

进程类型

对资源的需求

用户要求

动态优先级

在创建进程时赋予一个优先级

在进程运行过程中还可以改变

以便获取更好的调度性能

多级反馈调度

算法是时间片轮转算法和优先级算法的综合与发展

优点

照顾了短进程以提高系统吞吐量，缩短了平均周转时间

照顾了I/O型进程以获得较好的I/0设备利用率和缩短响应时间

不必估计进程的执行时间，动态调度优先级

算法实现思路

设置多个就绪队列

新进程进入内存后

先投入队列1的末尾

按FCFS算法调度

仅当较高优先级的队列为空才调度较低优先级队列中的进程执行

进程优先级确定

优先级确定需要考虑如下情况

对于I/O型进程

让其进入最高优先级队列

以及时响应需要I/O交互的进程

对于计算型进程

每次都执行时间片后进入更低级队列

最终采用最大时间片来执行

以减少调度次数

对于I/O次数不多，主要是CPU的处理

在I/O完成后，返回优先I/O请求时离开的队列

以免每次都返回到最高优先级队列后再逐次下降

为适应一个进程在不同时间段的运行特点

I/O完成时，提高优先级

时间片用完时，降低优先级

死锁

两个以上的进程互相都要对方已经占有的资源导无法继续运行下去的现象

死锁举例

死锁产生的原因及4个必要条件

死锁产生的原因

竞争资源

进程推进顺序

必要条件

互斥条件

请求保持条件

不可剥夺条件

环路条件

死锁的处理

死锁的处理策略

鸵鸟策略(即不理睬策略)

预防策略

避免策略

检测与解锁死锁

死锁预防

采用某种策略限制并发进程对资源的请求

破坏死锁产生的4个必要条件之一

使系统在任何时刻都不满足死锁的必要条件

预防死锁的两种策略

预先静态分配法

预先分配所需资源，保证不等待资源

方法问题

降低了对资源的利用率

降低进程的并发的程度

有时可能无法预先知道所需资源

资源有序分配法

破坏了“环路条件”

方法问题

限制进程对资源的请求

由于资源的排序占用系统开销

死锁避免

死锁预防是设法破坏死锁产生的四个必要条件

死锁避免是严格地限制死锁的必要条件

银行家算法

死锁检测

死锁解除

线程

传统的进程基本属性

可拥有资源的独立单元

可独立调度和分配的基本单位

线程具有三种基本状态

就绪

运行

阻塞

存储管理

存储器的管理的对象是主存存储器简称主存或内存

基本概念

存储器的结构

常用的存储器结构

寄存器-主存-外存

寄存器-缓存-主存-存储组织的功能外存

地址/空间

虚拟地址

数据的存放地址是由符号决定的

符号名地址

名地址

源程序的地址空间称为

符号名地址空间

名空间

相对地址

地址空间

相对地址编址的模块

源程序经过汇编或编译后

经过链接编辑程序加工形成的程序模块

相对地址也称为

逻辑地址

虚地址

把程序中由相对地址组成的空间成为逻辑地址空间

相对地址空间通过再定位机构转换到绝对地址空间

绝对地址空间也成为物理地址空间

存储空间

逻辑地址空间(简称地址空间)是逻辑地址的集合

物理地址空间(简称存储空间)是物理地址的集合

地址重定位

将逻辑地址变成主存物理地址的过程

分类

静态地址重定位

动态地址重定位

存储管理方案

主要目的是解决多个用户使用主存的问题

存储管理方案

分区存储管理

分页存储管理

分段存储管理

段页式存储管理

虚拟存储管理

分区存储管理

固定分区

静态分区方式

可变分区

动态分区方式

请求和释放分区

最佳适应算法

最差适应算法

首次适应算法

循环首次适应算法

可重定位分区

分区保护

采用上界/下界寄存器保护

采用基址/限长寄存器保护

分页存储管理

纯分页存储

分页原理

地址结构

页表

快表

页式存储管理至少需要两次访问主存

第一次访问页表，得到数据的物理地址

第二次是存取数据

为了提高访问主存的速度

在地址映射机构中增加一组高速寄存器，用来保存页表

在地址映射机构中增加一个小容量的联想存储器

联想存储器是由一组高速存储器组成，
称为快表

两级页表机制

分段存储管理

在系统中为每个进程建立一个段映射表(段表)

每个段在表中占有一个表项记录

主存的起始地址(基址)

段的长度

段页式存储管理

访问了3次内存

为获取数据或指令

分页过程是由操作系统做出的

优点:对用户是透明的，用户不用担心分页的过程

缺点:不易实现共享

段是信息的逻辑单位

易于实现段的共享

允许若干进程共享一个或多个段

对段的保护也十分简单

段页式系统

地址结构组成

段号

段内页号

页内地址

实现变换

从逻辑地址到物理地址

系统中必须同时配置

段表

页表

虚拟存储管理

程序局部性原理

时间局限性

内容

执行

程序中的某条指令一旦执行

则不久将来指令可能再次被执行

访问

某个存储单元被访问

则不久将来可能再次被访问

典型原因

程序中存在着大量的循环操作

空间局限性

一旦程序访问了某个存储单元

附件的存储单元也最有可能被访问

程序在一段时间内所访问的地址可能集中在一定的范围内

典型原因

程序是顺序执行的

虚拟存储器的实现

具有

请求调入功能

置换功能

逻辑容量

主存和外存容量之和

CPU可寻址的范围

运行速度接近于主存

实现方式

请求分页系统

请求分段系统

请求段页式系统

请求分页管理的实现

请求分页

在纯分页系统的基础上增加

请求调页功能

页面置换功能所形成的
页式虚拟存储系统

目前最常用的一种虚拟存储的方式

缺页中断与一般中断的主要区别

缺页中断在指令执行期间产生和处理中断信号

一般中断

在一条指令执行完

下一条指令开始执行前检查和处理中断信号

发生缺页中断时，返回到被中断指令的开始重新执行指令

一般中断返回到下一条指令执行

一条指令在执行期间可能会产生多次缺页中断

页面置换算法

置换过程

在进程运行过程中

如果发生缺页

此时主存又无空闲块

必须从主存中调出

一页程序

数据送磁盘的对换区

哪个页面调出，却决于置换算法确定

置换算法的好坏将直接影响系统的性能

常用的页面置换算法

最佳(Optimal)置换算法

最理想化的算法

选择哪些是永不使用的

在最长时间内不再被访问的

性能最好

但实际上难于实现

要确定哪个页面是未来最长时间内不再被访问的是很难的

该算法通常用来评价其他算法

先进先出(FIFO)置换算法

算法

总是淘汰最先进入主存的页面

选择在主存中驻留时间最久的页面予以淘汰

实现简单

缺点

最直观,性能最差的算法

有Belady异常现象

如果对一个进程未分配它所要求的全部页面

有时会出现

分配的页面增多

但缺页率反而提高

最近最少未使用(LRU)置换算法

最近未用(NUR)置换算法

工作集

设备管理

各种设备分配

缓冲区管理

实际物理I/O设备操作

设备管理概论

计算机系统中负责管理设备和输入/输出的机构称为I/O系统

设备的分类

按数据组织分类

块设备

字符设备

按设备的功能分类

输入设备

输出设备

存储设备

网络联网设备

供电设备

按资源分配角度分类

独占设备

共享设备

虚拟设备

按数据传输率分类

低速设备

中速设备

高速设备

设备管理的目标与任务

目标

如何提高设备的利用率

为用户提供方便

统一的界面

任务

保证在多道程序环境下
当多个进程竞争使用设备时

按一定的策略

分配各种设备

管理各种设备

控制设备的各种操作

完成I/O设备与主存之间的数据交换

功能

动态地掌握并记录设备的状态

设备分配和释放

缓冲区管理

实现物理I/O设备的操作

提高设备使用的用户接口及设备的访问和控制

I/O软件

从事I/O设备管理软件的结构

基本思想是分层构造

设备管理组织成为一系列的层次

设计I/O软件的主要目标

设备独立性

统一命名

I/O管理软件

中断处理程序

设备驱动程序

与设备无关的系统软件

用户级软件

设备管理采用的相关技术

通道技术

引入管道技术

使数据的传输独立于CPU

使CPU从烦琐的I/O工作中解脱出来

信息交换不同

字节多路通道

数组选择通道

数组多路通道

DMA技术

数据在主存与I/O设备间直接成块传送

在主存与I/O设备间传送一个数据块不需要CPU的任何干涉

只需要CPU在过程中

开始启动

过程结束

缓冲技术

可提高外设使用率

尽可能使外设处于忙状态

采用

硬件缓冲

软件缓冲

引用缓冲的主要原因

缓和CPU与I/O设备间速度不匹配的矛盾

减少对CPU的中断频率，放宽对中断响应时间的限制

提高CPU和I/O设备之间的并行性

分类

单缓冲

双缓冲

多缓冲

环形缓冲

Spooling技术

外围设备联机操作的简称

实际上

一类物理设备模拟另一类物流设备的技术

是使独占使用的设备变成多台虚拟设备的技术

一种速度匹配技术

组成

预输入系统

缓输出程序

井管理程序

输入和输出井

输出井的三种状态

提交状态

后备状态

执行状态

完成状态

磁盘调度

磁盘是可被多个进程共享的设备

磁盘调度

移臂调度

旋转调度

先进行移臂调度，后进行旋转调度

磁盘驱动调度

先来先服务(FCFS)

最短寻道时间优先(SSTF)

扫描算法(SCAN)

单向扫描算法(CSCAN)

旋转调度算法

文件管理

文件与文件系统

文件

定义

具有符号名

在逻辑上具有完整意义的一组相关信息项的集合

信息项是构成文件内容的基本单位

可以是一个字符

也可以是一个记录

等长记录

不等长记录

一个文件包括

文件体:文件真实的内容

文件说明

操作系统为管理文件所用到的信息

包括

文件名

文件内部标识

文件的类型

文件存储地址

文件的长度

访问权限

建立时间

访问时间

文件系统

文件管理系统(文件系统)

操作系统中实现文件管理

一组软件