计算机软件技术基础总复习.ppt

1、总复习,各部分内容比例,数据结构 50%左右 操作系统 30 %左右 数据库系统 15 %左右 软件工程 5 %左右,考试时间： 12周四6-7 考试地点： 231：M206/M306 251：D209/B209 集中答疑时间：12周二6-7，周三下午 答疑地点：实验楼304,数据结构,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为 Group=（D，R）,(亦称物理结构),数组,逻辑结构 存储结构（定义，特点） 顺序存储结构

2、链式存储结构 相关运算及应用 插入、删除等,线性表,定义，特点 存储结构 相关运算及应用,栈和队列,多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。 稀疏矩阵的三元组表示,数组,树的概念，包括与树有关的各个名词的意义 二叉树的定义 二叉树的性质 两种特殊情形的二叉树(完全二叉树和满二叉树的定义) 二叉树的遍历: 能够熟练排出二叉树的三种遍历次序。 三种遍历算法的实现，运用这些算法解决简单的问题。 二叉排序树 二叉排序树的插入和生成，给定一个序列，画出二叉排序树的生成过程。 二叉排序树中结点的删除。 哈夫曼树: 用图示法画出哈夫曼树 根据哈夫曼树给出最优前缀码

3、。,树形结构,图形结构,图的概念包括与图有关的各个名词的意义 图的邻接矩阵表示法和邻接表表示法 根据表示法画出图或者根据图写出邻接矩阵表示或画出邻接表。 图的遍历 深度优先遍历 广度优先遍历 单源最短路径 拓扑排序,查找,查找的基本概念，平均查找长度的定义及计算 线性表的查找有三种方法 顺序查找、二分查找、分块查找 二叉排序树查找 哈希查找，什么是哈希表?哈希函数、哈希值、哈希的含义。冲突(碰撞)、同义词的含义。 处理哈希表中冲突的方法： 开放定址法 拉链法 画出哈希表，并计算哈希表中查找的平均查找长度,排序方法,插入排序,选择排序,交换排序,归并排序,线性插入排序,对半插入排序,简单选择排序

4、,堆排序,冒泡排序,快速排序,排序,操作系统概念,操作系统基本概念 定义、目的、特征 操作系统的分类 批处理系统、分时系统、实时系统。 操作系统的功能 处理机管理、存储管理、设备管理、文件管理、作业管理,处理机管理,作业的概念 作业的定义、组成、 JCB、状态 进程的概念 进程的定义、PCB、进程与程序 进程状态及进程控制 进程状态及转换、进程队列、进程控制 处理机调度 高级调度、低级调度、调度算法 进程的同步与互斥 概念、解决同步互斥的软件工具（ P-V操作）、生产者消费者问题 死锁 产生死锁的原因、必要条件、解决死锁方法,解决死锁方法,预防：在系统运行之前就采取措施，严格防止死锁的产生。方

5、法为：破坏死锁产生的四个必要条件之一。 一次性分配资源。 申请不到资源，则释放全部资源。 资源编号，从低到高申请。 避免：允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，小心地避免。 银行家算法。 检测和恢复：允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。 化简资源分配图。 撤销进程。按某种次序强行从系统中撤销一个或多个卷入死锁的进程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。 挂起进程。使用挂起/激活机构挂起一些进程，暂时剥夺它们占有的资源，以解除死锁，待以后条件满足后再激活被挂起的进程。,存储管理,存储管理任务 主存空间分配、地址映射、内存保护、内存“扩充

6、” 实存储管理 固定分区、动态分区（空闲分区分配算法、动态重定位） 虚拟存储管理 请求分页（概念、特点、地址转换、页面置换算法） 请求分段,设备管理,有关概念 设备管理的功能、任务 I/O请求的检测与控制 循环测试、中断、DMA、通道 缓冲技术 概念、目的 设备管理程序 逻辑设备与物理设备 虚拟设备技术 虚拟设备、SPOOLing技术,文件管理,基本概念与术语 文件、文件系统文件分类 文件的结构 逻辑结构（记录式文件、流式文件） 、物理结构（连续分配、链接分配、索引分配） 文件目录 FCB、文件目录、目录项、目录文件、目录结构（单级、目录、目录）、路径 文件存储空间的管理,数据库系统概述,数据

7、库基本概念 DB、 DBMS、 DBS、DBA 数据模型 数据模型（E-R图） 、结构模型（层次、网状、关系）、 E-R图转换为关系模型 数据库系统结构（三级模式结构） 外模式、模式、内模式、外模式/模式映象、模式/内模式映象 、逻辑独立性、物理独立性 关系数据库的基本概念 关系、元组、属性、候选码、主码 关系模式、关系模型、关系特点,关系数据操作语言,关系代数 传统的集合运算（并、交、差、广义笛卡尔积） 专门的关系运算（选择、投影、连接（条件连接、自然连接） 结构化查询语言SQL SQL：DDL、DML、DCL SELECT语句的使用,数据库设计与应用,关系模式规范化 范式、规范化、 1NF

8、、 2NF、 3NF 数据库设计,软件工程,软件工程基本概念 软件、软件危机 软件生命周期 软件开发过程 过程模型 软件开发方法 结构化、面向对象 软件开发工具,结构化软件开发方法,可行性研究 市场、经济 、技术 、法律、可行性研究报告 需求分析 任务、步骤、数据流图、数据字典、需求规格说明书 概要设计 体系结构设计、模块设计、用户界面设计、数据库设计、概要设计说明书 模块独立性、耦合、内聚 详细设计（图形工具） 编码 测试 目的、任务、白盒测试、黑盒测试、测试用例、测试计划、测试报告 软件维护 改正性维护、适应性维护、 扩充与完善性维护、预防性维护,线性链表的基本操作,指针赋值 指针移动 后

9、插 前插,p,s,s = p,p = p - next,p,p,s,p, s-next= p-next p-next=s,s,p,q,head,q=head While (q-next!=p) q=q-next q-next=s s-next=p,栈的定义,限定只能在表的一端进行插入和删除的特殊的线性表 栈顶（top)：允许插入和删除的一端； 栈底（bottom):不允许插入和删除的一端。 空栈:表中无元素时。 栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out).,栈底,进栈,出栈,栈顶,栈底,练习,设一数列的顺序为1,2,3,4,5 通过栈操作,不

10、可能得到的序列是( ) A. 23451 B. 54123 C. 23145 D. 15432,1,2,2,3,3,4,4,5,5,1,练习,设一数列的顺序为1,2,3,4,5 通过栈操作,不可能得到的序列是( ) A. 23451 B. 54123 C. 23145 D. 15432,1,2,3,4,4,5,5,答案 B,队的定义,一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear):允许插入的一端 队头 (Front):允许删除的一端 队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out),a1,a2,a3,a

11、4,a5,an,front队头,rear队尾,出队,入队,数组的顺序存储结构,计算机的内存结构是一维的，因此将数组元素排成线性序列，然后将这个线性序列存放在存储器中 行优先顺序：把数组按一行一行的顺序依次排列。 列优先顺序：就是把数组按一列列的顺序依次排列。,地址的计算方法 二维按行优先顺序存放,存放在计算机内：,m,j-1,aij,i-1,n,Loc（aij）=Loc(a11)+(i-1) * n +(j-1) (1=i=m,1=j=n) 第一个元素是从a11开始，注意从a00开始的情况 Loc（aij）=Loc(a00)+ i* n +j,aij前的元素个数,地址的计算方法 二维按列优先顺

12、序存放,存放在计算机内：,m,j-1,aij,i-1,n,Loc（aij）=Loc(a11)+(j-1) * m +(i-1) (1=i=m,1=j=n) 第一个元素是从a11开始，注意从a00开始的情况 Loc（aij）=Loc(a00)+(j* m +i)*d,稀疏矩阵的压缩存储方式三元组表示,把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。 但是这种压缩存储方式将失去随机存储功能。,一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。,稀疏矩阵的压缩存储方式三元组表示,把非零元素的值和它所在的行号列号做

13、为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。 但是这种压缩存储方式将失去随机存储功能。,7,1,1,列,行,值,介绍几个术语： 结点（Node）：树中的元素。 结点的度（Degree）：结点拥有的子树数。 叶子（Leaf）：度为零的结点，也称端结点。 结点的层次：从根结点开始算起，根为第一层。 深度（Depth)： 树中结点的最大层次数。 孩子（Child）：除根结点外,每个结点都是其前趋结点的孩子 双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲 兄弟（Sibling）：同一双亲的孩子。 森林（Forest）：M棵互不相交的树的集合。 有序树:

14、每个结点的各子树从左到右的次序不能互换的树称为有序树 二叉树,非完全二叉树,完全二叉树,特点：除最后一层外，每一层都取最大结点数， 最后一层结点都集中在该层最左边的若干位置。,二、几种特殊形式的二叉树,二叉树的性质,二叉树上第i层上的结点数目最多为2i-1(i1) 深度为h的二叉树至多有2h-1个结点(h1) 在任意一棵二叉树中，若叶子结点的个数为n0,度为2的结点数为n2，则n0=n2+1。 具有n个结点的完全二叉树高度为|_ log2n_| +1 设完全二叉树中阶段数n，按层编号，对树中第i个结点有： 若i=1，i的双亲节点编号为|_ i/2_| i的左子位于第2*i号节点 i的右子位于第

15、2*i+1号节点,二叉树的遍历,先序ABCDEFG 中序CBDAEGF 后序CDBGFEA,A,B,G,C,E,D,F,若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。,例:已知一棵二叉树的前序序列和中序序列分别为前序遍历:ABCDEFG 中序遍历:CBDAFEG ，请画出此二叉树。,二叉排序树,二叉排序树或是空树,或具有下列性质 其左子树上所有结点的数据值均小于根结点的数据值; 其右子树上所有结点的数据值均大于或等于根结点的数据值; 左子树和右子树又各是一棵二叉排序树,10,

16、3,21,2,18,4,13,15,9,9,8,中序遍历: 2,3,4,8,9,9,10,13,15,18,21 得到由小到大的有序序列,哈夫曼树,树的带权路径长度最小的二叉树就称为最优二叉树（即哈夫曼树）。,d,b,a,c,7,5,2,4,WPL=7*1+5*2+2*3+4*3=35,哈夫曼首先提出了构造最优二叉树的算法，哈夫曼算法,练习:给定一组权值w=2，3，8，4，45，7，9构造关于w的哈夫曼树,练习:给定一组权值w=2，3，8，4，45，7，9构造关于w的哈夫曼树,各字符编码是 T ； A C S 00 01 10 110 111,方法： （1）用 2，4， 2，3， 3 作为叶子

17、结点的权值生成一棵哈夫曼树，并将对应权值wi的叶子结点注明对应的字符； （2）约定左分支表示字符“0”，右分支表示字符1 （3）从根结点到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。,哈夫曼编码的构造-利用哈夫曼树构造通讯中电文编码（前缀码） 例2：要传输的电文是CAS；CAT；SAT；AT 要传输的字符集是 D=C，A，S，T， ； 每个字符出现的频率是W= 2，4， 2，3， 3 ,图的概念,图是一种复杂的非线性结构, 由两个集合V和E组成，V是顶点的有穷非空集，E是V中顶点偶对(边)的有穷集 图的逻辑结构特征：就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之

18、间之间都可能相关。 无向图:图中顶点关系为无序对。(边) 有向图:图中顶点关系为有序对。(弧) 网：图中每一条边附有一个对应的数（权） 有向网：弧上带权的有向图 子图:简单地说，子图就是原图的一部分 度:无向图中顶点的度就是关联于该顶点的边的数目 入度:顶点v的入度即是以该顶点为终点的边的数目 出度:顶点v的出度即是以该顶点为始点的边的数目,图的存储结构邻接矩阵表示法,1,2,3,5,4,0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0,1,2,3,4,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,有向图,无向图，矩阵对称,图

19、的存储结构邻接表,1,2,3,5,4,1,2,3,4,1,2,3,4,2,1,3,3,2,1,5,4,1,5,3,1,2,3,2,3,4,4,1,邻接矩阵与邻接表,从存储空间角度看，邻接表更适合于表示稀疏图而邻接矩阵适合于表示稠密图。 从求解相应问题来看，求顶点的度，采用邻接矩阵比邻接表表示更方便。,图的遍历,从某一个顶点出发，沿着某条路经对途中其余顶点进行访问，且每个顶点仅被访问一次 深度优先遍历（DFS depth-first search） 广度优先遍历（BFS breadth-first search）,深度优先遍历算法(dfs),0 1 1 0 0 0 0 0 1 0 0 1 1 0

20、 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,Dfs(1),Dfs(2),Dfs(4),Dfs(8),Dfs(5),Dfs(6),Dfs(3),Dfs(7),Visited1:8,1,1 2 3 4 5 6 7 8,1,1,1,1,1,1,深度优先遍历算法邻接表存储,1,2,4,5,2,1,3,3,1,6,7,4,8,5,8,2,2,6,8,8,5,3,4,6,7,Dfs(7)

21、,Dfs(3),Dfs(1),Dfs(2),Dfs(4),Dfs(8),Dfs(5),Dfs(6),7,8,3,Visited1:8,1 2 3 4 5 6 7 8,1,1,1,1,1,1,1,广度优先遍历算法(邻接表存储),1,2,4,5,2,1,3,3,1,6,7,4,8,5,8,2,2,6,8,8,5,3,4,6,7,Visited1:8,0 1 2 3 4 5 6 7,1 2 3 4 5 6 7 8,2,队列,1,1,2,1,3,1,3,1,4,1,4,5,1,5,6,1,6,7,1,7,8,1,8,7,8,3,图的应用单源最短路径,求单源最短路径的(dijkstra)思想 设置并逐步

22、扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个将V-S中的顶点加S中，直到S中包含全部顶点，而V-S为空。,图的应用拓扑排序,AOV网作业活动网 将G中所有顶点排成一个线性序列，使得对图中任一对顶点u和v，若E(G)(该有向边在该图的边集中可以找到)，则u在线性序列中出现在v之前。这种线性序列称为拓扑序列。 拓扑排序是对于有向无环图才可以排序成功的，若图中存在有向环，则该拓扑序列不存在。,拓扑排序方法,每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。,1,2,3,4,5,6,三种查

23、找方法的比较,哈希表（散列表）概念,1 2 3 4 . . . 26,通过对给定值做某种运算，直接求得某关键字在记录文件中的位置,哈希(hash)函数： 根据关键字直接计算出元素所在位置的函数 H(key),哈希表：存放记录元素的一维数组 哈希地址：一维数组的下标,处理冲突的方法,开放定址法：将所有结点均存放在哈希表T0.m-1中 线性探查法 平方探查法 随机探查法 拉链法：将互为同义词的结点链成一个单链表，而将此链表的头指针放在哈希表中。,线性探查法,关键字序列: 19、14、23、1、68、20、84、28、55、11、10、79 设哈希函数为： H(k)=k mod 13(除留余数法),

24、0 1 2 3 4 5 6 7 8 9 10 11 12,6、 1、 10、1、 3、 7、 6、 2、 3、 11、10、1,19,14,23,1,68,20,84,28,55,11,10,79,1,84,84,28,28,55,10,79,处理冲突的方法,线性探查法,关键字序列: 19,14,23,1,68,20,84,27,55,11,10,79 H(k)=k mod 13 (除留余数法),0 1 2 3 4 5 6 7 8 9 10 11 12,1,84,10,28,55,79,ASL=（6*1+1*2+4*3+1*9）/ 12=2.42,处理冲突的方法,拉链法,将所有关键字为同义词的

25、结点链接在同一个单链表中。,0 1 2 3 4 5 6 7 8 9 10 11 12,关键字序列: 19,14,23,1,68,20,84,28,55,11,10,79 6, 1, 10, 1, 3, 7, 6, 2, 3, 11, 10, 1 H(k)=k mod 13 (除留余数法),ASL=7*1+4*2+1*3=1.5,处理冲突的方法,排序,1.插入排序： 基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 线性插入排序 从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上 对半

26、插入排序 在有序区中进行对分查找，以确定插入的位置,排序,2.交换排序 基本思想：两两比较反即换。 冒泡排序 第一趟：第1个与第2个比较，大则交换；第2个与第3个比较， 大则交换，关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上； 依次类推，则完成排序。 快速排序 通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。,排序,3.选择排序 基本思想：每趟选一排在（前）后。 简单选择排序： 每一趟从待排序的记录中选出关键字最小的记录，顺序存放已排好的子文件的最后(最

27、前)，直到全部记录排序完毕。 堆排序：堆的定义、堆的构造、堆排序基本思想 由给定的无序序列构造堆 将堆顶元素与堆中最后一个元素交换， 将最后一个元素从堆中删除 将余下的元素构成完全二叉树重新调整成堆 反复进行，直到堆空。,堆排序过程,第一趟结果:,第二趟结果:,第三趟结果:,第四趟结果:,第五趟结果:,第六趟结果:,第七趟结果:,46 55 13 42 94 05 17 70,快速排序例,初始值 46 55 13 42 94 5 17 70,第一趟 17 5 13 42 46 94 55 70,第二趟 5 13 17 42 46 70 55 94,第三趟 5 13 17 42 46 55 70

28、 94,第四趟 5 13 17 42 46 55 70 94,例如对序列16，31，9，15，87，76，13，24，43进行二路归并排序过程为：,归并排序,一趟归并过程中的三种情况,n,1,length,i,i,i+2*length=n,n,1,length,i,i,i+lengthn,剩下两个子文件，其中一个长度小于length,归并后退出,n,1,length,i,i,只剩下一个子文件，将最后一个子文件复制到r1中，完成后退出,待归并记录至少有两个长度为length的子文件，归并完成后 i+*length,操作系统复习,操作系统的定义,操作系统是计算机系统中的一个系统软件， 是一些程序模

29、块的集合,它们能以尽量有效、合理的方式组织和管理计算机的软硬件资源，合理的组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使得用户能够灵活、方便、有效的使用计算机，使整个计算机系统能高效地运行。,操作系统的分类由于用户对OS的要求不同,1、批处理操作系统 2、分时系统 3、实时系统 4、网络操作系统 5、分布式操作系统,单道批处理系统,多道批处理系统,批处理操作系统特点,多道： 多道指某个作业占用CPU，若由于某种原因暂时不用CPU 则系统让第二个作业占用CPU,成批处理： 用户自己不能干预自己作业的运行，一旦发现作业错误不能及时改正，并延长开发软件时间，所以适用于成熟的程序。,

30、在多道批处理系统，用户无法干预自己程序的运行，缺乏参与感，于是分时系统应运而生。,分时操作系统特点,多路性 交互性 “独占”性 及时性,同时有多个用户使用一台计算机 宏观上：是多个人同时使用一个CPU 微观上：多个人在不同时刻轮流使用CPU,用户根据系统响应结果进一步 提出新请求(用户直接干预每一步),用户感觉不到计算机为其他人服务 （OS提供虚机器，各个用户的虚 机器互不干扰）,系统对用户提出的请求及时响应,实时操作系统,主要追求目标： 对外部请求在严格时间范围内作出反应 高可靠性 安全性 完整性 实时系统必须和先进的技术装备相结合,操作系统的功能,1、处理机管理 2、存储管理 3、设备管理

31、 4、文件管理 5、用户接口,第四节 操作系统的特征,并发性 共享性 不确定性 虚拟性,第五节 操作系统的性能评价,可靠性 方便性 效率 可维护性 可移植性,第八章 处理器管理,基本内容 作业的概念 进程的概念 进程状态及进程控制 处理机调度 进程的同步和互斥 死锁问题 要求 掌握进程的概念及作用 掌握进程的控制与调度方法 掌握进程的同步与互斥、P、V操作 掌握死锁的概念和死锁的解决方法,一、作业的定义,作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做的工作的集合。,作业控制块JCB,作业被收容到外存后，系统为每个作业建立一个JCB，它详细记录作业的有关信息,作业队列,(Job C

32、ontrol Block),提交,作业,收容,执行,完成,辅存,内存,设备管理,作业管理,区分配,作业的生命期,作业从进入计算机系统到运行结束、退出系统的整个过程分成四个阶段,进程是一个可并发执行的程序在一个数据集上的一次执行过程。它是系统分配资源的基本单位。,进程是由程序、数据集和进程控制块三部分组成。,进程定义,进程的三种基本状态,运行,就绪,阻塞,选中,等待事件发生 (如I/O请求),等待结束 如等到I/O资源,落选 (时间到）,作业调度,进程调度,就绪：获得了除CPU之外的全部资源。 运行：被调度程序选中，使用CPU。（获得全部资源） 阻塞：等待某个事件的发生或发生错误。,进程控制块

33、PCB (Process Control Block),是进程的档案，记录各进程执行情况。 是进程存在的标志 进程与PCB是一一对应的,第四节 处理器调度,一、高级调度（作业调度、宏观调度） 二、中级调度（交互调度） 三、低级调度（进程调度、微观调度）,进程状态,第五节 进程的同步和互斥,一、相关概念 二、信号量和P、V原语 三、用P，V原语实现进程互斥 四、用P，V原语操作实现简单同步 五、P，V原语在进程同步/互斥问题中的应用,进程的同步,进程的同步：synchronism 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一

34、伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态,进程的互斥 mutual exclusion 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥,临界区：critical section 在每个进程中，访问临界资源的那段程序称为临界区。,临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源,同步互斥问题的解决方法P-V操作原语荷兰计算机科学家迪克斯特拉(Dijkstra)发明,对每一个临界资源设置一个信号量，初始化后，只能通过P操作和V操

35、作来访问信号量 信号量S是一个整型变量 S0时，表示该类临界资源的可用个数。 S0时，表示等待使用该类临界资源的进程个数。,P(Passeren)荷兰语通过 V(Vrijgeven)荷兰语释放,二、信号量和P，V原语,1.信号量S：是一个整型变量 S0时，表示该类临界资源的可用个数。 S0时，表示等待使用该类临界资源的进程个数。 信号量只能通过P操作和V操作来访问。,P操作记为 P(S)，其中S为一信号量，其执行顺序完成以下两个动作： （1） S=S1，表示申请使用一个资源； （2）若S0，表示系统中有资源可用，现进程可继续执行。 （3）若S0，表示系统中没有可用资源，则置该进程阻塞状 态，到

36、S信号量 的队列中去等待，直到其他进程在S上执 行V操作释放它为止。,2. P原语,S0时，表示该类临界资源的可用个数。 S0时，表示等待使用该类临界资源的进程个数。,V操作记为 V(S)，其中S为一信号量，其执行顺序完成以下两个动作： （1） S=S+1，表示释放一个资源； （2）若S0，表示系统中没有等待该资源的进程，现进程可继续执行。 (3) 若S0，表示系统中有等待该资源的进程，则唤醒S信号量队列中的第一个进程，使其插入到就绪队列，继续执行现进程。,3 .V原语,S0时，表示该类临界资源的可用个数。 S0时，表示等待使用该类临界资源的进程个数。,第六节 死锁问题,一、死锁的概念 二、死

37、锁产生的原因 三、死锁产生的必要条件 四、死锁的排除方法,死锁产生的原因,系统资源不足 进程推进的顺序不当,产生死锁的必要条件,所涉及的资源是非共享的（互斥条件） 进程在等待新资源时,继续占用已分配的资源（请求和保持条件） 一个进程占有的资源不能被别的进程强行攻占（不剥夺条件） 前一个进程获得的资源正是后一个进程所请求的,从而形成一个进程的循环链（环路等待条件）,进程1 进程2 申请R1 申请R2 申请R2 申请R1 释放R1 释放R2,解决死锁方法,预防：在系统运行之前就采取措施，严格防止死锁的产生。方法为：破坏死锁产生的四个必要条件之一。 静态分配资源。 申请不到资源，则释放全部资源。 资

38、源编号，从低到高申请。 避免：允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，小心地避免。 银行家算法。 检测和恢复：允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。 化简资源分配图。 撤销进程。按某种次序强行从系统中撤销一个或多个卷入死锁的进程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。 挂起进程。使用挂起/激活机构挂起一些进程，暂时剥夺它们占有的资源，以解除死锁，待以后条件满足后再激活被挂起的进程。,第九章 存储管理,基本内容 存储器层次结构 存储管理任务 实存储管理 虚拟存储管理 要求 掌握存储管理任务 掌握存储管理、 实存储管理、虚拟存储管理 了解存储器

39、层次结构,第二节 存储管理任务,主存空间分配: 动态地为不断进进出出的作业分配内存空间。 地址映射:保证作业运行中能够正确的定位。 内存保护:保证作业的进程之间既能互相通信而又不互相干扰。 内存“扩充”:使空间需求量大于用户区容量的作业也能够正常运行。,2.地址映射,程序的起始地址都是从“0”开始的，程序中的其它地址都是相对于起始地址计算的，该地址被称为逻辑地址（或相对地址） 。 由这些地址所形成的地址范围称为（作业）地址空间。 主存单元的编号称为物理地址（或绝对地址） 由主存中的一系列单元所限定的地址范围称为存储空间。 相对地址到绝对地址的转换，同时程序中与地址有关的指令的修改，这一过程叫做

40、地址重定位。 静态重定位在程序装入时进行, 由装配程序进行地址转换 动态重定位是在程序的执行过程中, 当CPU访问指令或数据前，由地址变换机构进行地址变换。,第三节 实存储管理,单一连续分区(单道环境) 固定分区 动态分区,为调入内存的程序提供一个不小于作业地址空间的存储空间，当存储空间不够时，采用覆盖或交换技术扩充内存,固定分区的优缺点,优点 实现多个作业共享 分区的分配和回收算法简单 缺点 内存利用不充分，因为每个分区中都会有一部分空间被浪费了。,作业2,作业3,0 16k 24k 40k 72k 128k,内存,碎片,3.动态分区,分区分配 空闲分区分配算法 分区的回收 可重定位的动态分

41、区,3.动态分区,2. 空闲分区分配算法 1）首次适应算法（First Fit） 2）下次适应算法（Next Fit） 3）最坏适应算法（Worst Fit） 4）最佳适应算法（Best Fit）,3.动态分区,4.可重定位的动态分区 使用紧凑技术，为了消除外部碎片，进一步提高主存的利用率，定时地（或者在主存空间紧张时）把主存中的作业“搬家”集中在主存的一端，使另一端产生一个大的空闲区，这种技术称为存储器的“紧凑”。 紧凑仅仅在动态重定位时才可以用，并且在运行时执行。,P1,P2,P3,P4,P5,P6,占用块,空闲块,P1,P2,P3,P5,第四节 虚拟存储管理,1. 虚拟存储器的原理 2.

42、 请求分页存储管理 3. 请求分段存储管理,虚拟存储管理,工作原理：首先把作业信息保留在磁盘上，当作业请求装入时，只将其中一部分先装入主存，作业执行中若要访问的信息不在主存中，则再设法将这些信息装入主存。,用软件方法扩充内存。 逻辑上扩充了内存空间。 虚拟地址空间的大小受指令中地址长度的限制和外存储容量的限制； 需解决什么时候把哪部分程序装入内存、放在内存什么地方、淘汰策略问题。,内存分页,分页存储管理,页:将作业的地址空间划分成一系列大小相等的块，称为页，所有页按顺序编号为0、1、2、。 页内地址:每个页内的内容也都从0开始顺序编号，这个编号称为页内地址。 块: 内存空间也划分成与页一样大的

43、块，所有的块从低地址到高地址顺序编号为0、1、2、。 页表:系统为作业建立一个页号与块号的对照表。,分页系统中的逻辑地址,逻辑地址可用一个数对表示,p=INT,A L,逻辑地址,页面大小,d = A MOD L,例:设某系统页面大小位1024字节，若逻辑地址为:2500, 则p=INT(2500/1024)=2 d=2500 MOD 1024=452 即2500处于第2页,第452位置上,分页管理中的地址转换,地址空间,内存 块号,0 1 8 10,1000 2500 3000,页号 块号 状态,+,页表长 页表起始地址,页表地址寄存器,23285,PMT表,p d,p d,地址变换机构,8*

44、1024+452=8644,绝对地址=块号*页面大小+页内地址,P175 16,某请求分页系统中用户编程空间共64个页面，每页1K，主存32K ，假如某时刻某进程对应的页表如下，请求出16进制逻辑地址128D的物理地址，并写出计算过程,128D H 0001 0010 1000 1101,328DH,3). 页面置换算法,当主页中无空闲块时，为了装入一个页面，就必须按某种算法将主存中某个页调出，调入所需装入的页面。这就是页面调度。算法有： 先进先出调度算法(FIFO)、 最近最少使用调度算法(LRU) 最近未使用页面置换算法（NRU） 最佳页面置换算法(OPT),先进先出算法(FIFO),设一

45、用户程序共分5页, 分配给它的内存块数为3 页面走向P为 4 3 2 1 4 3 5 4 3 2 1 5 其页面淘汰过程:,缺页中断9次,分段存储管理,分段存储管理中,作业的地址空间被划分为若干个段,每段定义一组逻辑信息,如:主程序段,子程序段,数据段等,规定一个段号,每段地址空间都从0开始.,逻辑地址可用两部分表示,内存分配: 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放,分段管理中的地址转换,逻辑地址 段号s 段内地址w,内存,+,段表长 段表起始地址,段表地址寄存器,8292,12345,SMT表,b,+,8kB,段号 长度

46、 起址 状态,段号2,段表地址,绝对地址=根据段号找到段表中的起始地址+段内地址,第十章 设备管理,基本内容 设备管理的有关概念 I/O请求的检测与控制 缓冲技术 设备管理程序 虚拟设备技术 要求 掌握设备管理的有关概念 掌握I/O请求的检测与控制 掌握缓冲技术、设备管理程序、虚拟设备技术,第一节 设备管理的有关概念,1.设备分类 2.设备管理的任务,1.设备分类,1从数据组织的角度分类 块设备 以块为单位组织和传送数据，每块的大小一般是512的倍数，如磁盘是一种典型的块设备。 字符设备 以字符为单位组织和传送数据，如键盘、打印机等。,2从资源分配的角度分类 独占设备 在系统运行期间，在某一段

47、时间内，为某一进程所独占的设备。大多数低速设备属于独占设备，如纸带输入机、打印机等。 共享设备 允许若干用户或进程同时共同使用的设备，如磁盘等。 虚拟设备 通过软件技术（如假脱机技术），把原来的独占设备改造成共享设备。,2.设备管理的任务,1）确定分配策略 按照进程的请求把进程需要的输入输出设备分配给进程。 2）启动设备完成实际的输入输出操作 输入输出设备都有一个控制器，它直接控制设备完成具体的输入输出，而CPU只是与设备控制器交换信息。 3）提供统一、友好的使用界面 使用户能方便地利用外部设备资源。 4）优化设备的调度、提高设备的利用率 使各种外部设备与主机以及各外部设备之间能协调地工作，以

48、充分合理地利用系统资源，尽量提高并行程度。,设备管理的主要内容,1) I/O请求的检测与控制 2) 解决设备的低速性与CPU高速性之间的矛盾，提高CPU的利用率 3) 设备分配策略,第二节 I/O请求的检测与控制,循环测试I/O方式 中断驱动方式 直接内存存取（DMA）方式 I/O通道方式,第三节 缓冲技术,在内存中划出一块由n个单元组成的区域，称为缓冲区，作为外部设备传输数据的临时存储区。 目的：解决处理数据过程中CPU的高速性与设备传输的低速性之间的矛盾 单缓冲区和双缓冲区 多缓冲区 缓冲池,第四节 设备管理程序,逻辑设备与物理设备 设备分配程序 设备驱动程序,逻辑设备与物理设备,绝对设备

49、号：就是将每一台设备确定一个编号（相当于一个绝对地址）。 （物理设备号） 相对设备号：设备类型号（逻辑设备号）系统为每一类设备规定一个类型号 符号名（逻辑设备名）：在OS的命令语言中，通常用符号名代替设备类型号，如：COM为串行打印机，LPT为并行打印机。,第五节 虚拟设备技术,虚拟设备:是一个软件子系统，使用这个软件子系统，可以将独占设备变成共享设备, 构成： 外存储空间 相应的数据结构 控制代码 SPOOLing（Simultaneous Peripheral Operation On-Line）技术，习惯上称其为假脱机技术。 当在外围设备和计算机处理器之间传送数据时，为了减少处理的延时,

50、把辅助存储器作为缓冲存储器来使用的一种方法或技术。,卡片机,打印机,卫星机,主机,输入磁带,输出磁带,早期脱机批处理,1.虚拟设备技术的引入,假脱机技术将一台低速的输入输出设备改变成一台高速的虚拟设备，把一台独占设备改变成具有共享能力的虚拟设备。这增加了系统调度和分配的灵活性，提高了设备的利用率。,2. SPOOLing系统的组成,1）输入井和输出井 2）输入缓冲区（输入队列）和输出缓冲区（输出队列） 3）输入进程SPI和输出进程SPO,3. SPOOLing技术的特点,1）提高了I/O速度 从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作，如同脱机操作一样，提高了I/O速度，缓和

51、了CPU与低速I/O设备速度不匹配的矛盾。 2）设备并没有分配给任何进程 在输入井或输出井中，分配给进程的是一个存储区和建立的一张I/O请求表。 3）实现了虚拟设备功能 多个进程同时使用同一独享设备，而对每一进程而言，都认为自己独占这一设备，不过，该设备是逻辑上的设备。,第十一章 文件管理,第十一章 文件管理,基本内容 基本概念与术语 文件的结构 文件目录 文件存储空间的管理 文件的共享 文件的存取控制 要求 掌握基本概念与术语 掌握文件的结构、文件目录、文件存储空间的管理 了解文件的共享、文件的存取控制,第一节 基本概念与术语,1.文件与文件系统的概念 文件:是具有标识符（文件名）的一组相关

52、信息的集合。 文件体:即文件本身的信息 文件属性:即文件存储和管理信息，如文件名、文件内部标识、文件存储地址、访问权限和访问时间等。 文件系统:负责管理外存上的文件，并把对文件的存取、共享和保护手段提供给OS和用户,组成: 管理文件所需的数据结构（如文件控制块，存储分配表等） 相应的管理软件 访问文件的一组操作,文件逻辑结构,文件逻辑结构:从用户角度看到的文件面貌 。 有两种形式： 无结构文件（流式文件）组成流式文件的基本信息单位是字节或字，其长度是文件中所含字节的数目，如源程序，库函数，word文件，图片文件等。 有结构文件（记录式文件）：由若干个相关的记录构成的文件，每个单位为一个逻辑记录

53、。每个记录可以独立存取。 等长记录 变长记录,文件管理,文件物理结构（存储结构）：逻辑文件在外存储器上的存放形式，是从系统的角度来看文件 连续分配 链接分配 索引分配,文件物理结构,1.文件控制块(FCB),1.文件控制块（FCB）：文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。是文件存在的标志。其内容有： 有关文件存取控制信息：例如用户名、文件名、文件类型、文件属性（可读写、只读、只执行等） 有关文件结构的信息：例如文件的逻辑结构、物理结构、记录个数和在存储介质上的位置等。 有关文件管理的信息：例如文件建立的日期、修改日期、口令、保留期限等。 2. 文件

54、目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合 3. 目录项：构成文件目录的项目（目录项就是FCB） 4. 目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件,2.文件的目录结构,文件的目录结构关系到文件系统的存取速度、文件的共享性、文件的安全性。文件目录可分为 单级目录 二级目录 多级目录。,3. 多级目录结构 允许用户在自己的文件中再建立子目录。从根目录到文件之间所有各级子目录名和该文件名的顺序组合称为文件的“路径名” 优点： 层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的

55、控制。 缺点：增加了系统空间开销,多级目录,2.文件的目录结构,2.文件的目录结构,3多级目录（树型目录） 路径名：从树的根(即主目录)开始， 把全部目录文件名与数据文件名，依次地用“”连接起来， 即构成该数据文件的路径名(path name)。 相对路径：把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name) 绝对路径：把从树根开始的路径名称为绝对路径名(absolute path name)。,第四节文件存储空间管理,空闲表法 空闲链表法 成组链接法,第十二章数据库系统概述,基本内容 数据库基本概念 数据模型 数据库系统结构 关系数据库的基本

56、概念 要求 熟练掌握数据库的基本概念和关系数据模型 熟悉数据库系统结构特别是三级模式结构,第一节数据库基本概念,一、数据库（DataBase，简称DB） 数据库是长期存放在计算机内、有组织、可共享的数据集合， 数据库中的数据按一定的数据模型组织、描述和储存，具有尽可能小的冗余度和较高的数据独立性和易扩展性， 并可为各种用户共享。,数据1,数据2,数据n,第一节数据库基本概念,二、数据库管理系统（DBMS） 数据库系统的核心组成部分，对数据进行管理的软件。 主要功能： 数据定义 :对数据库中的数据对象（包括表、视图、索引等）进行定义 。 数据操纵 ：对数据库操作 查询 插入 删除 修改等 数据库

57、的运行管理：对数据库的建立、运用和维护进行统一管理和控制 安全性控制、完整性控制、并发控制、备份与恢复 数据库的建立和维护功能 数据库初始数据的输入和转换功能、数据库的转储和恢复功能以及数据库重组织功能和性能监视、分析功能等。,数据1,DBMS 统一存取,数据2,数据n,第一节数据库基本概念,三、数据库系统（DBS） 在计算机系统中引入数据库后的系统构成 组成： 数据库（及相关硬件） 数据库管理系统（DBMS） 开发工具 应用系统 数据库管理员 用户 数据库管理员(DataBase Administrator,简称DBA),数据库在计算机系统中的地位示意图,一、数据模型的基本概念,数据模型 表

58、示实体和实体之间联系的模型,应用,概念数据模型（E-R表示）,结构数据模型 （DBMS支持）,二、概念模型与E-R图,独立于计算机系统的数据模型 信息世界模型 信息世界基本概念 实体(Entity) 属性(Attribute) 域(Domain) 实体型(Entity Type) 实体集(Entity set) 码(Key) 联系(Relationship),三、结构模型,三要素： 数据结构 数据操作 数据完整性约束 常用的结构模型 层次模型 网状模型 关系模型,直接面向数据库中数据的结构,数据模型,关系模型,关系(Relation)一个关系对应一张二维表。 元组(Tuple)二维表中的一行称为一个元组。 属性(Attribute)二维表中的一列称为一个属性，对应每一个属性的名字称为属性名。 超码(Super Key)二维表中的某个属性或是属性组可以唯一确定一个元组，则称为超码。 候选码(Candidate Key) 最小的超码 主码(Primary Key) 任选一个候选码 域(Domain)属性的取值范围称为域。 分量元组中的一个属性值。,第三节数据库系统结构,一、数据库的三级模式结构