软件技术基础复习.ppt

软件技术基础复习 2020 1 25 1 页式存储中 知道逻辑地址求对应物理地址 地址结构及页面大小设置 页面的划分完全是一种系统硬件的行为 地址结构如下 在这个完整的32位地址结构中 页号占10位 页内偏移量 也叫页内地址 占12位 页面大小为4KB 若给定某一个逻辑地址 或相对地址 通过下面式子可以得出页号和页内偏移量 页号 逻辑地址DIV页面大小页内偏移量 逻辑地址MOD页面大小 例如页面大小为4KB的系统中 若逻辑地址为28024 由上式求得28024div4096 6 页号 28024mod4096 3448 页内偏移量 页表与地址映射 在分页系统中 允许将作业 进程 的任一页装入到内存中的任一可用的物理块中 但进程的地址空间本来是连续的 若将其分页后装入到不相邻的物理块中 为保证作业仍能正确运行 即将进程的逻辑地址变换为内存的物理地址 系统就要记录用户程序的逻辑页与内存物理块之间的对应关系 这通过为每个应用程序建立一张页面映射表来实现 简称页表 通过页表实现地址映射 设页长为P 若逻辑地址为A 则有 A所对应的物理地址 块号M 页长P 页内地址D 实例 在采用页式存储管理的系统中 某作业J的的逻辑地址空间为4页 每页2048字节 且已知该作业的页面映象表如下 试借助地址变换图 画出地址变换图 求出有效逻辑地址4865所对应的物理地址 2 P V操作 信号量机制 荷兰著名科学家 后来的计算机图灵奖获得者 E W Dijkstra于1965年提出了用作进程同步工具的信号量 semaphore 机制 这是一种卓有成效的进程互斥同步工具 已被广泛应用于现代计算机系统中 信号量的思想 两个或多个进程可以利用彼此间收发的简单的信号来实现 正确的 并发执行 一个进程在收到一个指定信号前 会被迫在一个确定的或者需要的地方停下来 从而保持同步或互斥 经典的整型信号量 经记录型信号量 信号量集机制 CPU忙等 造成死锁 不易死锁 可能导致资源利用率低 1 整型信号量 最初由Dijkstra将信号量定义为一个整型量SS是个具有非负初值的整型变量 表示该信号量的值 且S的值只能由定义在信号量上的P操作原语和V操作原语来改变 2 记录型信号量 P Passeren proberen V Vrijgeren verhogen 是荷兰语 分别代表 通过 测试或等待 及 释放 增加或发信号 信号量S值的物理含义 当S 0时 表示某类可用资源的数目 或者说表示可以执行P操作而不会被阻塞的进程的数目 当S 0时 其绝对值表示信号量S的阻塞队列中的进程数 即系统中因请求该类资源而被阻塞的进程的数目 亦即被信号灯挡住的进程数目 这些进程需要别的进程发出相应的信号灯来唤醒 另外 S的值只能由P V操作来改变 P S 操作和V S 操作的物理含义 P S 操作表示 等信号 即测试一个要等的信号是否到达 V S 操作表示 发信号 这个信号在实现同步时就是 合作者的伙伴进程已完成前趋任务 在实现互斥时就是 临界资源可用 另外 在互斥问题中 每执行一次P S 操作的含义 也可理解为进程请求一个单位的S类资源 每执行一次V S 操作的含义 也可理解为进程释放一个单位的S类资源 上述P V操作一次只能对一个信号量做加一或减一操作 即只能使进程获得或释放一个单位的某种临界资源 假如进程一次需要共享多种临界资源 且每种资源个数不限于一个时 则P V操作就显得效率不高 这种情况下我们可以用信号量集来解决 在信号量集机制中 进程一次可以申请多个不同种类的临界资源 当可用资源个数低于系统规定的某一下限值时 不予分配 3 信号量集 信号量应用 1 利用P V操作原语实现进程的互斥即保证进程互斥地进入各自的临界区 这里所用信号量的初值一般为1 表示临界资源未被占用 且其可用数目为1 用P V操作原语实现进程互斥的效率更高一些 因为P操作中引入了阻塞机制 所以消除了CPU忙等现象 三个进程互斥进入临界区 然后P1 P2同时竞争P操作 设P1先执行 设P3先进入此时s 1 s于是s 0 设P3退出后此时s 1 s于是s 1 P1执行后此时s 1 s于是s 0 P2执行此时s 1 s于是s 1 阻塞 P1退出 此时s 1 s于是s 0 0 释放P2 P2退出后此时s 1 s于是s 1 P V操作也都是配对出现 但对同一个信号量的P V操作却不是同时出现在每一个进程的程序里 而是分别出现在一个进程和它的合作伙伴的代码中 解答这类进程同步问题的主要步骤也是有三步 1 分析清楚题目涉及的进程间的制约关系 2 设置信号量 包括信号量的个数和初值及其物理含义 合作进程间需要收发几条消息相应就设置几个信号量 同步信号量的初值一般为0 表示得到合作进程的消息后才能向前推进 3 给出进程相应程序的算法描述或流程控制 并把P V操作加到程序的适当处 2 用P V操作实现进程的同步 例1 生产者 消费者问题 公用缓冲池 有n个缓冲区 问题分析 生产者 消费者之间的同步关系表现为 一旦缓冲池中所有缓冲区均装满产品时 生产者必须等待消费者提供空缓冲区 一旦缓冲池中所有缓冲区全为空时 消费者必须等待生产者提供满缓冲区 生产者 消费者之间还有互斥关系 由于缓冲池是临界资源 所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行 生产者 消费者问题是相互合作进程关系的一种抽象 问题解答 所用信号量设置如下 同步信号量empty 初值为n 表示消费者已把缓冲池中全部产品取走 有n个空缓冲区可用 同步信号量full 初值为0 表示生产者尚未把产品放入缓冲池 有0个满缓冲区可用 互斥信号量mutex 初值为1 以保证同时只有一个进程能够进入临界区 访问缓冲池 用信号量机制解决生产者 消费者问题的算法描述如下 生产者i消费者j生产出一产品 P full P empty P mutex P mutex 从缓冲区取出一产品 将该产品放入缓冲区 V mutex V mutex V empty V full 消费该产品 实例总结 可以得出这样的结论 实现进程的同步互斥实际就是给进程的并发执行增加一定的限制 以保证被访问的共享数据的完整性和进程执行结果的可再现性 用信号量机制解这类题的三个步骤 1 分析进程间的制约关系 2 设置信号量 3 实施P V操作 第一步是基础 关键 第三步是核心 掌握实现进程互斥与进程同步的第三步在形式上差异 即P V操作总是配对出现的 但P V在互斥问题中总是出现在同一个进程的代码中 且紧紧夹着临界区 而在同步问题中 却是分别出现在两个合作进程的代码中 需要等消息的一方用P操作 相应的对同一信号量的V操作则在发出此消息的另一方中 3 Hash函数 根据关键字直接计算出元素所在位置的函数 例如 设哈希函数为 int K 3 1则构造01 02 05 09 11 13 16 19 21 26 27 31 的散列表 哈希表 为 哈希函数 冲突 两个不同的关键字具有相同的存储位置 2 构造哈希函数的方法 1 直接定址法 取关键字或关键字的某个线性函数值为散列地址 即H K K或H K A K B 其中A B为常数 直接定址哈希函数示例 某公司一险种投保费交纳表 20年 将年份作关键字 哈希函数取关键字本身 若查找第3年应交纳的保费 只要查找表的第3项即可 2 平方取中法 取关键字平方后的中间几位为哈希函数 如 K 308 K2 94864 H K 486 3 除后余数法 取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数 即H K KMODp p m 3 处理冲突的方法 1 开放定址法 设散列函数H K KMODm m为表长 若发生冲突 则沿着一个探查序列逐个探查 那么 第i次计算冲突的散列地址为 Hi H K di MODm di 1 2 m 1 i 1 2 F F m 1 012345678910 设散列函数H k kMOD11求 60 17 29 38在散列表中的位置 H 60 60mod11 5H 17 17mod11 6H 29 29mod11 7H 38 38mod11 5 H 38 1 mod11 6H 38 2 mod11 7H 38 3 mod11 8 4 二叉树的遍历及树 森林与二叉树的转换 先序遍历定义 若二叉树为空 遍历结束 否则 1 访问根结点 2 按先序方式遍历根结点的左子树 3 按先序方式遍历根结点的右子树 中序遍历定义 若二叉树为空 遍历结束 否则 1 按中序方式遍历根结点的左子树 2 访问根结点 3 按中序方式遍历根结点的右子树 后序遍历定义 若二叉树为空 遍历结束 否则 1 按后序方式遍历根结点的左子树 2 按后序方式遍历根结点的右子树 3 访问根结点 根据遍历序列构造二叉树 若给定一棵二叉树的中序遍历序列和另一种序列便可得到该二叉树 不失一般性 这里以一棵二叉树的中序遍历序列和先序遍历序列来构造该二叉树 构造二叉树的步骤 1 从先序遍历序列中取第一个结点 为该二叉树的根结点 再从中序遍历序列中找到根结点 根结点之前的结点序列为根结点左子树的中序遍历序列 之后的结点序列为根结点右子树的中序遍历序列 2 再用递归的方法 分别重构根结点的左右子树 重复用第一步的方法 直到得到所有的结点序列为止 例 已知二叉树先序遍历序列为ABCDEFGHIJ 中序遍历序列为CBDEAFHIGJ 试构造此二叉树 树转换成二叉树 操作算法 保留一个结点的最左子结点 抹掉其余兄弟结点与上级结点的连线 将兄弟结点连在一起 以根为轴 顺时针旋转一个角度 举例 5 排序的思想及其过程 插入排序选择排序交换排序快速排序归并排序 插入排序 基本思想 将n个元素的数列分为已有序和无序两个部分 a1 a2 a3 a4 an a1 1 a2 1 a3 1 a4 1 an 1 a1 n 1 a2 n 1 an n 1 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较 找出插入位置 将该元素插入到有序数列的合适位置中 有序无序 选择排序 基本思想 每次从待排序的记录中选出关键字最小 或最大 的记录 顺序放在已有序的记录序列的最后 或最前 面 直到全部数列有序 a1 a2 a3 a4 an a1 1 a2 1 a3 1 a4 1 an 1 a1 n 1 a2 n 1 an n 1 有序无序 3 交换排序 冒泡排序 指导思想 两两比较待排序记录的关键字 并交换不满足顺序要求的那些偶对元素 直到全部数列满足有序为止 冒泡排序 Bubblesort 是基于交换排序的一种算法 它是依次两两比较待排序元素 若为逆序 递增或递减 则进行交换 将待排序元素从左至右比较一遍称为一趟 冒泡 每趟冒泡都将待排序列中的最大关键字交换到最后 或最前 位置 直到全部元素有序为止 a1a2a3 an 1an 最大值 冒泡排序算法举例 设有数列 65 97 76 13 27 49 58 比较次数第1趟 65 76 13 27 49 58 97 6第2趟 65 13 27 49 58 76 97 5第3趟 13 27 49 58 65 76 97 4第4趟 13 27 49 58 65 76 97 3第5趟 13 27 49 58 65 76 97 2第6趟 13 27 49 58 65 76 97 1总计 21次 4 快速排序基本思想 在待排序序列中按某种方法选取一个元素K 以它为分界点 用交换的方法将序列分为两个部分 比该值小的放在左边 否则在右边 形成 左子序列 K 右子序列 再分别对左 右两部分实施上述分解过程 直到各子序列长度为1 即有序为止 分界点元素值K的选取方法不同 将构成不同的排序法 也将影响排序的效率 取左边第1个元素为分界点 取中点A left right 2 为分界点 选取最大和最小值的平均值为分界点等 设有序列 a1 a2 An 选取中点元素K为分界点 分别从序列两头分别与K进行比较 小于K的元素交换到左边 否则交换到右边 一趟处理后 左边子序列的元素均小于分界点值K 右边子序列元素均大于等于K值 Step1分别从两端开始 指针i指向第一个元素A left 指针j指向最后一个元素A right 分界点取K Step2循环 i j 从右边开始进行比较 若K A j 则将A j 交换到左边 若K A j 则j j 1 再进行比较 从左边开始进行比较 若K A i 则i i 1 再进行比较 若K A i 则将A i 交换到右边 当i j时 一次分解操作完成 Step3在对分解出的左 右两个子序列按上述步骤继续进行分解 直到子序列长度为1 不可再分 为止 也即序列全部有序 快速排序算法举例 对于数列 49 38 60 90 70 15 30 49 采用中点分界法 初始状态 4938609070153049比较次数第1趟493860907015304949386090701530495 i4 j1 49386049701530905 i5 j2 49386049701530 90小计 10 i k 90 j i j j i 5 归并排序 归并是将两个或两个以上的有序表合成一个新的有序表 用这种思想实现的排序称作归并排序 MergingSort 假设初始序列有n个记录 可以看成是有n个有序的字序列 然后两两归并 得到n 2个有序的子序列 再两两归并 直到得到一个长度为n的有序序列为止 这种排序方法称为2 路归并排序 2 路归并排序是我们最经常使用的归并排序 其核心操作是将一维数组中前后相邻的2个有序序列归并成为一个有序序列 Step1把待排序的n个记录看作是长度为1的有序序列 将相邻子序列两两归并为长度为2的有序序列 Step2把得到的n 2个长度为2的有序子序列再归并为长度为2 2的有序序列 Step3按Step2的方式 重复对相邻有序子序列进行归并操作 直到成为一个有序序列为止 49 49 38 27 13 76 65 97 第一趟排序 将每一个元素看成一个有序表两两归并 38 49 49 27 76 13 65 97 第二趟排序 38 49 65 97 13 27 49 76 第三趟排序 13 97 27 76 65 49 38 49 13 97 27 76 65 49 38 49 6 通过邻接矩阵 邻接表写出其图的遍历 56 一 深度优先搜索二 广度优先搜索 图的遍历 遍历定义 从已给的连通图中某一顶点出发 沿着一些边 访遍图中所有的顶点 且使每个顶点仅被访问一次 就叫做图的遍历 它是图的基本运算 遍历实质 找每个顶点的邻接点的过程 图的特点 图中可能存在回路 且图的任一顶点都可能与其它顶点相通 在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点 解决思路 可设置一个辅助数组visited n 用来标记每个被访问过的顶点 它的初始状态为0 在图的遍历过程中 一旦某一个顶点i被访问 就立即改visited i 为1 防止它被多次访问 图常用的遍历 怎样避免重复访问 57 一 深度优先搜索 DFS 基本思想 仿树的先序遍历过程 Depth FirstSearch v1 DFS结果 例1 v2 v4 v8 v5 v3 v6 v7 例2 v2 v1 v3 v5 DFS结果 v4 v6 起点 起点 遍历步骤 应退回到V8 因为V2已有标记 58 深度优先搜索 遍历 步骤 详细归纳 在访问图中某一起始顶点v后 由v出发 访问它的任一邻接顶点w1 再从w1出发 访问与w1邻接但还未被访问过的顶点w2 然后再从w2出发 进行类似的访问 如此进行下去 直至到达所有的邻接顶点都被访问过的顶点u为止 接着 退回一步 退到前一次刚访问过的顶点 看是否还有其它未被访问的邻接顶点 如果有 则访问此顶点 之后再从此顶点出发 进行与前述类似的访问 如果没有 就再退回一步进行搜索 重复上述过程 直到连通图中所有顶点都被访问过为止 简单归纳 访问起始点v 若v的第1个邻接点没访问过 深度遍历此邻接点 若当前邻接点已访问过 再找v的第2个邻接点重新遍历 59 讨论1 计算机如何实现DFS DFS结果 邻接矩阵A 辅助数组visited n 起点 开辅助数组visited n 例 v2 v1 v3 v5 v4 v6 请注意逐级回退是递归概念 61 讨论2 在图的邻接表中如何进行DFS DFS结果 辅助数组visited n 例 照样借用visited n 起点 0123 注意 在邻接表中 并非每个链表元素 表结点 都被扫描到 因此遍历速度很快 v0 v1 v2 v3 63 二 广度优先搜索 BFS 基本思想 仿树的层次遍历过程 Breadth FirstSearch v1 BFS结果 例1 例2 v3 BFS结果 v4 v5 起点 遍历步骤 起点 v2 v1 v6 v9 v8 v7 64 广度优先搜索 遍历 步骤 简单归纳 在访问了起始点v之后 依次访问v的邻接点 然后再依次 顺序 访问这些点 下一层 中未被访问过的邻接点 直到所有顶点都被访问过为止 广度优先搜索是一种分层的搜索过程 每向前走一步可能访问一批顶点 不像深度优先搜索那样有回退的情况 因此 广度优先搜索不是一个递归的过程 其算法也不是递归的 65 讨论1 计算机如何实现BFS 邻接表 宽度优先搜索要借助队列 例 起点 辅助队列 v2已访问过了 V2入队 visited n 仍需要 BF