软件技术基础课件.ppt

《软件技术基础课件.ppt》由会员分享，可在线阅读，更多相关《软件技术基础课件.ppt（105页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件技术基础第1页，此课件共105页哦 13.1 13.1 数据结构数据结构 数据结构概述数据结构概述13.1.1数据结构（Data Structure）是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容：1.数据的逻辑结构2.数据的物理结构3.数据的运算第2页，此课件共105页哦数据的逻辑结构 1数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。因此，数据的逻辑结构可以看做是从具体问题抽象出来的数学模型。数据的逻辑结构有两大类：线性结构 线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有

2、一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。非线性结构 非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等是非线性结构。第3页，此课件共105页哦数据的物理结构 2数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。数据的存储结构可用以下四种基本存储方法：顺序存储方法 把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。链式存储方法 不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。索引存储方法 在存储结点信息的同时，还建立附加的索引表。索引表中

3、的每一项称为索引项。索引项由关键字和地址组成，关键字是能唯一标识一个结点的那些数据项，而地址一般是指示结点所在存储位置的记录号。散列存储方法 根据结点的关键字直接计算出该结点的存储地址。第4页，此课件共105页哦 数据的运算 3数据的运算是指对数据施加的操作，数据的每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等。第5页，此课件共105页哦算法 4算法的特点（1）有穷性 一个算法的执行步骤必须是有限的。确定性 算法中的每一个操作步骤的含义必须明确。可行性 算法中的每一个操作步骤都是可以执行的。输入 一个算法一般都要求有一个或多个输入量（个别的算法不要求输入量）。这些输

4、入量是算法所需的初始数据。输出 一个算法至少产生一个输出量，它是算法对输入量的执行结果。第6页，此课件共105页哦算法的描述（2）自然语言 用人的语言描述，该方法易于理解，但容易出现歧义。流程图 用一组特定的几何图形来表示算法，这是最早的算法描述工具。N-S图 用矩形框描述算法，一个算法就是一个矩形框。伪代码 用介于高级语言和人的自然语言之间的文字、符号来描述算法，可以十分容易地转化为高级语言程序。PAD图 全称为问题分析图，使用树形结构描述算法。第7页，此课件共105页哦 算法性能分析（3）衡量一个算法的好坏主要考虑算法的时间特性，一般将语句的重复执行次数作为算法的时间变量。设算法解决的问题

5、的规模为n，例如学生总数等。将一条语句重复执行的次数称为该语句的执行频度，一个算法中所有语句执行频度之和就称为该算法的运行时间。很多情况下无法准确也无必要精确计算出运行时间，而只需求出它关于问题规模n的一个相对的数量级即可，该数量级就称为该算法的时间复杂度，记为O(1)，O(n)，O(n2)一般地，常用的时间复杂度有如下关系：O(1)=O(log2n)=O(n)=O(nlog2n)=O(n2)1)第8页，此课件共105页哦线性结构线性结构13.1.2顺序表 1线性表是数据结构中最简单且最常用的一种数据结构。其基本特点是：数据元素有序并有限。线性结构的数据元素可排成一个线性队列 当线性表采用顺序

6、存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。第9页，此课件共105页哦插入运算（1）（2）删除运算 顺序表的插入运算是指在表的第i个（1in+1）位置上，插入一个新结点y。若插入位置in+1，即插入到表的末尾，那么只要在表的末尾增加一个结点即可；但是若1in，则必须将表中第i个到第n个结点向后移动一个位置，共需移动ni+1个结点。顺序表上插入运算的平均时间复杂度是O(n)。顺序表的删除运算是指将表的第i个（1 i n）结点删去。当i=n时，即删除表尾结点时，操

7、作较为简单；但1i n-l时，则必须将表中第i+1个到第n个共ni个结点向前移动一个位置。顺序表上删除运算的平均时间复杂度是O(n)第10页，此课件共105页哦单链表 2采用顺序表的运算效率较低，需要移动大量的数据元素。而采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素。这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。对链表的访问总是从链表的头部开始，是根据每个结点中存储的后继结点的地址信

8、息，顺链进行的。当每个结点只有一个指针域时，称为单链表 第11页，此课件共105页哦栈与队列 3栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。第12页，此课件共105页哦栈（1）队列（2）栈是仅限于在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端称为栈底。当表中没有元素时称为空栈。一摞盘子的情形就是栈的生动形态。栈的特点是：后进先出（LIFO Last In，First Out）。如：入栈顺序为 1，2，3，4，5，则出栈顺序为 5，4，3，2，1。队列是一种操作受限的线性表，它只允许在线性表的一端进行

9、数据元素的插入操作，而在另一端才能进行数据元素的删除操作。其允许插入的一端称为队尾，允许删除的另一端称为队头。日常生活中的排队就是队列的实例。特点：先进先出（FIFO First In，First Out）。第13页，此课件共105页哦 树树 13.1.3树结构 1树是一个或多个结点元素组成的有限集合T，且满足条件如下：有且仅有一个结点没有前趋结点，称为根结点（root）。除根结点外，其余所有结点有且只有一个直接前趋结点。包括根结点在内，每个结点可以有多个直接后继结点。第14页，此课件共105页哦二叉树 2二叉树结构也是非线性结构中重要的一类，它是有序树，不是树的特殊结构。在二叉树中，每个结点

10、最多只有两棵子树，一个是左子树，一个是右子树。二叉树有五种基本形态：它可以是空二叉树，根可以有空的左子树或空的右子树，或左、右子树皆为空，如图13-1-4所示。第15页，此课件共105页哦二叉树的存储结构 3顺序存储（1）对完全二叉树而言，可用顺序存储结构实现其存储，该方法是把完全二叉树的所有结点按照自上而下，自左向右的次序连续编号，并顺序存储到一片连续的存储单元中，在存储结构中的相互位置关系即反映出结点之间的逻辑关系。如用维数组Tree来表示完全二叉树，则数组元素Tree(i)对应编号为i的结点。第16页，此课件共105页哦链式存储（2）顺序存储容易造成空间浪费，并具有顺序存储结构固有的缺点

11、：添加、删除伴随着大量结点的移动。对于一般的二叉树，较好的方法是用二叉链表来表示。表中每个结点都具有三个域：左指针域Lchild、数据域Data、右指针域Rchild。其中，指针Lchild和Rchild分别指向当前结点的左孩子和右孩子。结点的形态如下：LchildDataRchild第17页，此课件共105页哦链式存储（2）第18页，此课件共105页哦二叉树的遍历 4所谓遍历，是指按某种次序，依次对某结构中的所有数据元素访问且仅访问一次。由于二叉树结构的非线性特点，它的遍历远比线性结构复杂，其算法都是递归的。有三种遍历方式：先序遍历 访问根结点；先序遍历左子树；先序遍历右子树。对图13-1-

12、7所示的二叉树，先序遍历序列为：A B D E C F。中序遍历 中序遍历左子树；访问根结点；中序遍历右子树。对图13-1-7所示的二叉树，中序遍历序列为：D B E A F C。后序遍历 后序遍历左子树；后序遍历右子树；访问根结点。对图13-1-7所示的二叉树，后序遍历序列为：D E B F C A。第19页，此课件共105页哦 图结构图结构13.1.4 图的概念 1图是一种重要的、比树更复杂的非线性数据结构。在树结构中，某结点只能与其上层的一个结点（父结点）相联系，并且根结点还没有父结点，每个结点与同一层结点间没有任何横向联系；而在图结构中，数据元素之间的联系是任意的，每个元素可以和其他元

13、素相联系，从这个意义上来讲，树是一种特殊形式的图。图包括一些点和边，故一个图G由点V(G)和边E(G)这两个集合组成 第20页，此课件共105页哦无向图G1（1）G1=G1=（V1V1，E1E1）V1=V1=1 1，2 2，3 3，4 4，5 5E1=E1=（1 1，2 2），（），（1 1，3 3），（），（3 3，4 4），（），（4 4，5 5）在无向图中，边没有方向：（在无向图中，边没有方向：（1 1，3 3）也可写成（也可写成（3 3，1 1）。）。第21页，此课件共105页哦（2）有向图G2 G2=G2=（V2V2，E2E2）V2=V2=1 1，2 2，3 3，4 4，5 5，6

14、6E2=E2=1,2,在有向图中，边有方向：在有向图中，边有方向：不能写成不能写成。第22页，此课件共105页哦 与图相关的一些术语和概念（3）邻邻接点接点 有有边边相相连连的点。的点。在无向在无向图图中，互中，互邻邻的两的两边侧边侧互互为邻为邻接点，若有（接点，若有（V2V2，V3V3），），则则V3V3和和V2V2互互为邻为邻接点；接点；在有向在有向图图中，若有中，若有V2V3，则则V3V3为为V2V2的的邻邻接点，但接点，但V2V2不一定是不一定是V3V3的的邻邻接点，除非也存在接点，除非也存在 V3V2。顶顶点的度点的度 与每个与每个顶顶点相点相连连的的边边数。数。在无向在无向图图中，

15、以中，以该顶该顶点点为为一个端点的一个端点的边边的条数。的条数。在有向在有向图图中，有入度（中，有入度（进进的的边边数）和出度（出的数）和出度（出的边边数）之分。数）之分。路径路径 某一某一顶顶点到达另一点到达另一顶顶点所点所经过经过的的顶顶点序列。两个点序列。两个顶顶点之点之间间可可以有多条路径。以有多条路径。路径上的路径上的边边的数目称的数目称为为路径的路径的长长度。度。网网络络 如果如果图图G(VG(V，E)E)中每一条中每一条边边都都赋赋有反映有反映这这条条边边的某种特性的的某种特性的数数值值，则则称此称此图为图为一个网一个网络络（图图13-1-1013-1-10），称与），称与边边相

16、关的数相关的数值为该值为该边边的的权权。第23页，此课件共105页哦图的存储结构 2邻接矩阵（1）基本思想：一个基本思想：一个图图由由顶顶点集合、点集合、边边集合（集合（顶顶点偶点偶对对集合，反集合，反映映顶顶点点间间关系）关系）组组成成 设设G=G=（V V，E E）是有）是有n n（n1n1）个）个顶顶点的无向点的无向图图，则则：一一维维数数组组Vn=Vn=顶顶点集合点集合；G G的的邻邻接矩接矩阵阵是一个二是一个二维维数数组组AnnAnn第24页，此课件共105页哦邻接表（2）为为了克服了克服邻邻接矩接矩阵阵的不足，可以采用的不足，可以采用动态动态的的链链式存式存储结储结构来保存构来保存

17、图图信息，信息，这这就就是是邻邻接表。其基本思想是：接表。其基本思想是：对对每一个每一个顶顶点建立一个点建立一个单链单链表。表。第第i i个个单链单链表中存放表中存放顶顶点点i i的所有的所有邻邻接接顶顶点。点。第第i i个个单链单链表的表的头结头结点中，存放点中，存放顶顶点点i i的信息的信息ViVi。第25页，此课件共105页哦邻接表（2）3 32 2 2 24 4 5 56 61 11 1 5 5 6 6 3 3ll3 3 4 4 1 12 24 43 36 65 5第26页，此课件共105页哦 线性表的查找线性表的查找 13.1.5顺序查找 1查查找（找（SearchSearch），又

18、称），又称检检索，就是在一个含有索，就是在一个含有n n个数据元素的集合中，根个数据元素的集合中，根据一个据一个给给定的定的值值k k，找出其关，找出其关键键字字值值等于等于给给定定值值k k的数据元素。的数据元素。从第从第1 1个数据元素开始，逐个把数据元素的关个数据元素开始，逐个把数据元素的关键键字字值值与与给给定定值值比比较较，若，若找到某数据元素的关找到某数据元素的关键键字字值值与与给给定定值值相等，相等，则查则查找成功；若遍找成功；若遍历历整个整个线线性性表都未找到，表都未找到，则查则查找失找失败败。第27页，此课件共105页哦二分法查找 2当当顺顺序存序存储储的的线线性表已性表已经

19、经按关按关键键字有序字有序时时，可以使用二分法，可以使用二分法查查找。二分法找。二分法查查找找的基本思路是：由于的基本思路是：由于查查找表中的数据元素按关找表中的数据元素按关键键字有序（假字有序（假设为设为增序），增序），则查则查找找时时不必逐个不必逐个顺顺序比序比较较，而先与中，而先与中间间数据元素的关数据元素的关键键字比字比较较。若相等，。若相等，则查则查找成功；找成功；若不等，即把若不等，即把给给定定值值与中与中间间数据元素的关数据元素的关键键字字值值比比较较，若，若给给定定值值小于中小于中间间数据元数据元素的关素的关键键字字值值，则则在前半部分在前半部分进进行二分行二分查查找，否找，否

20、则则在后半部分在后半部分进进行二分行二分查查找。找。这这样样，每，每进进行一次比行一次比较较，就将，就将查查找区找区间缩间缩短短为为原来的一半。原来的一半。容易容易证证明，在明，在长长度度为为n n的有序的有序顺顺序表中序表中进进行二分行二分查查找的找的查查找次数不超找次数不超过过 log2n+1 log2n+1 次（其中次（其中 代表取整）。代表取整）。第28页，此课件共105页哦分块查找 3分分块查块查找找是介于是介于顺顺序序查查找与二分法找与二分法查查找之找之间间的一种的一种查查找方法，又称索引找方法，又称索引顺顺序序查查找。它的基本思想是：找。它的基本思想是：分分块块 将数据划分将数据

21、划分为为若干数据若干数据块块，数据在，数据在块块内无序，但内无序，但块间块间有序。有序。也就是也就是说说，第一，第一块块内的最大数据比后内的最大数据比后继继所有所有块块内的所有数据都小（假内的所有数据都小（假设设按数据按数据递递增有序），后面的每一增有序），后面的每一块块内的所有数据都大于它前面的所内的所有数据都大于它前面的所有有块块的最大数据，同的最大数据，同时时又小于后又小于后继继所有所有块块内的所有数据。内的所有数据。查查找找 分两步分两步进进行。行。块间块间：建立一个各：建立一个各块块最大关最大关键键字字值值表，将待表，将待查查数据在数据在该该表中按二分法表中按二分法或或顺顺序序查查找

22、找进进行，通行，通过块间查过块间查找确定数据所在找确定数据所在块块。用二分法可以提高。用二分法可以提高块间查块间查找的效率。找的效率。块块内：在内：在块块内按内按顺顺序序查查找方式直接找方式直接查查找元素。找元素。第29页，此课件共105页哦 内排序内排序 13.1.6插入法排序 1排序又称排序又称为为分分类类，它是数据，它是数据处处理中理中经经常使用的一种运算，是将一常使用的一种运算，是将一组组数据元素数据元素（记录记录）按其排序）按其排序码进码进行行递递增或增或递递减的运算操作。排序分内排序和外排序。减的运算操作。排序分内排序和外排序。内排序内排序 整个排序运算在内存中整个排序运算在内存中

23、进进行。行。把把n n个数据元素的序列分成两部分，一个是已排好序的有序部分，另个数据元素的序列分成两部分，一个是已排好序的有序部分，另一个是未排好序的未排序部分；把未排好序的元素逐个与已排好序的一个是未排好序的未排序部分；把未排好序的元素逐个与已排好序的元素比元素比较较，并插入到有序部分的合适位置，最后得到一个新的有序序，并插入到有序部分的合适位置，最后得到一个新的有序序列。列。第30页，此课件共105页哦选择排序 2每一每一轮轮排序中，将第排序中，将第i i个元素与从序列第个元素与从序列第i+1i+1到到n n的的n-i+1(i=1,2,3,n-n-i+1(i=1,2,3,n-1)1)个元素

24、中个元素中选选出的、出的、值值最小的一个元素最小的一个元素进进行比行比较较，若，若该该最小元素比第最小元素比第i i个个元素小，元素小，则则将两者交将两者交换换。i i从从1 1开始，重复此开始，重复此过过程，直到程，直到i=n-1i=n-1。简单简单地地说说，通，通过过交交换换位置，位置，选选最小的放在第一，次小的放在第二，最小的放在第一，次小的放在第二，以此以此类类推，直到元素序列的最后推，直到元素序列的最后为为止。止。第31页，此课件共105页哦冒泡排序冒泡排序 3冒泡法排序需要冒泡法排序需要进进行行n n 1 1轮轮的排序的排序过过程。程。第一第一轮轮：从：从a1a1开始，两两比开始，

25、两两比较较aiai、ai+1ai+1（i=1i=1，2 2，n n 1 1）的大小，）的大小，若若aiai+1aiai+1，则则交交换换aiai与与ai+1ai+1。当第一。当第一轮轮完成完成时时，最大元素将被交，最大元素将被交换换到最到最后一位（第后一位（第n n位）。位）。第二第二轮轮：仍然从：仍然从a1a1开始，两两比开始，两两比较较aiai、ai+1ai+1（i=1i=1，2 2，n n 2 2）的大）的大小，注意此小，注意此时时的的处处理范理范围围从第一从第一轮轮的整个序列的整个序列n n个数据元素比个数据元素比较较n n 1 1次次（i=1i=1，2 2，n n 1 1），），变变

26、成了成了n n 1 1个数据元素比个数据元素比较较n n 2 2次（次（i=1i=1，2 2，n n 2 2）。当第二）。当第二轮轮完成完成时时，最大元素将被交，最大元素将被交换换到次后一位（第到次后一位（第n n 1 1位）。位）。第第n-1n-1轮轮：只需比：只需比较较最初两个元素，就完成了整个最初两个元素，就完成了整个线线性表的排序。性表的排序。第32页，此课件共105页哦冒泡排序冒泡排序 3第33页，此课件共105页哦归并排序 4将两个或两个以上的有序表将两个或两个以上的有序表组组合成一个新的有序表。合成一个新的有序表。将每个元素看成一个将每个元素看成一个长长度度为为1 1的子序列，把

27、相的子序列，把相邻邻子序列两两合并，得到子序列两两合并，得到一个新的子序列，如此重复，最后得到一个新的子序列，如此重复，最后得到长长度度为为n n的一个新的有序序列。的一个新的有序序列。第34页，此课件共105页哦快速排序 分区交换排序 5快速排序是冒泡法排序的改快速排序是冒泡法排序的改进进，平均速度，平均速度较较快。基本思想如下：快。基本思想如下：任任选选一个元素一个元素RiRi（一般（一般为为第一个）做第一个）做标标准。准。调调整各元素位置，使排在整各元素位置，使排在RiRi前的元素的排序前的元素的排序码码都小于都小于RiRi，而排在，而排在RiRi后后的元素的排序的元素的排序码码都大于都

28、大于RiRi。本本过过程称程称为为一次快排，由此确定了一次快排，由此确定了RiRi在有序序列中的最后位置，同在有序序列中的最后位置，同时时将剩余元素分将剩余元素分为为两个子序列。两个子序列。对对两个子序列分两个子序列分别进别进行快速排序，又确定了两个元素在有序序列中的位置，行快速排序，又确定了两个元素在有序序列中的位置，并将剩余元素分并将剩余元素分为为四个子序列。四个子序列。重复此重复此过过程，直到各子序列的程，直到各子序列的长长度都度都为为1 1，排序，排序结结束。束。第35页，此课件共105页哦排序方法的比较和选用 6几种排序的比几种排序的比较较：稳稳定性比定性比较较：稳稳定的排序方法有：

29、插入、定的排序方法有：插入、选择选择、归归并、冒泡排序；快并、冒泡排序；快速排序是不速排序是不稳稳定的排序方法。定的排序方法。平均平均综综合情况：合情况：归归并排序、快速排序速度并排序、快速排序速度较较快，插入、冒泡排序快，插入、冒泡排序速度速度较较慢。慢。总总之，各种排序法各有其之，各种排序法各有其优优缺点。其缺点。其选选用依据是：用依据是：其数据其数据规规模模n n大，内存允大，内存允许许，要求，要求稳稳定：定：选归选归并排序。并排序。其数据其数据规规模模n n较较小，有小，有稳稳定要求：定要求：选选插入排序。插入排序。其数据其数据规规模模n n大，内存允大，内存允许许，对稳对稳定不要求：

30、定不要求：选选快速排序。快速排序。第36页，此课件共105页哦 操作系统的概念和类型操作系统的概念和类型13.2.113.2 13.2 操作系统操作系统操作系操作系统统（Operating SystemOperating System）是）是计计算机系算机系统统中最重要的系中最重要的系统软统软件，件，协调协调管理管理计计算机的算机的软软硬硬资资源，以提高硬件的利用率；是用源，以提高硬件的利用率；是用户户与与计计算机之算机之间间的接口，的接口，为为用用户户使用使用计计算机提供操作的平台和算机提供操作的平台和环环境，以便用境，以便用户户无需了解无需了解计计算机硬件或系算机硬件或系统软统软件的有关件

31、的有关细节细节就能方便地使用就能方便地使用计计算机算机 .第37页，此课件共105页哦操作系统的基本特征 1现现代操作系代操作系统统普遍采用多道程序普遍采用多道程序设计设计技技术术，所，所谓谓多道程序多道程序设计设计技技术术是是为为了提高了提高计计算机算机软软硬件硬件资资源的利用率，允源的利用率，允许许在内存中同在内存中同时时安排多个作安排多个作业业（用（用户软户软件程序），件程序），各个作各个作业业共享系共享系统资统资源，以并源，以并发发的方式各自向前推的方式各自向前推进进。多道程序多道程序设计设计技技术术的引入，使得操作系的引入，使得操作系统统具有如下基本特征。具有如下基本特征。第38页，

32、此课件共105页哦 并发性（1）并并发发是指在宏是指在宏观观上各作上各作业业是并行的（用是并行的（用户观户观点），而在微点），而在微观观上是串上是串行的（行的（CPUCPU观观点）。各作点）。各作业业之之间间的微的微观观切切换换只有几十到几百毫秒。多个只有几十到几百毫秒。多个进进程可以并程可以并发执发执行和交行和交换换信息，操作系信息，操作系统统必必须须具具备备控制和管理各种并控制和管理各种并发发活活动动的能力。的能力。第39页，此课件共105页哦共享性（2）多道程序或多个用多道程序或多个用户户共同使用有限的共同使用有限的资资源，根据源，根据资资源的属性不同，共享分源的属性不同，共享分为为：互

33、斥共享互斥共享 一段一段时间时间只允只允许许一个用一个用户户使用的使用的资资源，如打印机。源，如打印机。并并发访问发访问 一段一段时间时间内可有多个内可有多个进进程同程同时时使用某个使用某个资资源。源。并并发发与共享是操作系与共享是操作系统统最基本的两个特征，互最基本的两个特征，互为为存在条件存在条件 。第40页，此课件共105页哦（3）虚拟性 把一个物理把一个物理设备变为逻辑设备变为逻辑上的多个。例如：上的多个。例如：CPUCPU分分时时系系统统的的时间时间片、一片、一个物理硬个物理硬盘盘通通过过分区划分分区划分为为多个多个逻辑逻辑硬硬盘盘等。操作系等。操作系统统的作用就是的作用就是对对用用

34、户户屏蔽物理屏蔽物理细节细节，而提供，而提供给给用用户户一个一个简洁简洁、易用的、易用的逻辑逻辑接口。接口。第41页，此课件共105页哦不确定性（4）在多道程序在多道程序设计环设计环境下，由于各用境下，由于各用户户程序（程序（进进程）各自独立地向前推程）各自独立地向前推进进，而而对对系系统软统软硬件硬件资资源的争源的争夺夺、对对CPUCPU的争用，的争用，导导致各程序的致各程序的执执行行顺顺序和每个程序和每个程序的序的执执行行时间时间都是不确定的。都是不确定的。第42页，此课件共105页哦批处理操作系统（1）操作系统的分类操作系统的分类 2基本特点是：多道，即允基本特点是：多道，即允许许外存中

35、的多个作外存中的多个作业队业队列列进进入内存，由入内存，由CPUCPU调调度各作度各作业业交替运行；成批，即作交替运行；成批，即作业业的装入、运行及的装入、运行及结结果果输输出等都由系出等都由系统统自自动实现动实现，不允，不允许许用用户户干干预预。第43页，此课件共105页哦分时操作系统（2）多个用多个用户对户对系系统统的的资资源源进进行行时间时间上的分享，具体上的分享，具体实现实现是将是将CPUCPU的的时间时间划分成一个一个的划分成一个一个的时间时间片，按某种策略分配片，按某种策略分配给给各个用各个用户户的的进进程使用，每个用程使用，每个用户户都似乎独占了都似乎独占了CPUCPU一一样样。

36、其特点是：。其特点是：多路性多路性 同同时时响响应应多个多个终终端用端用户户的服的服务请务请求。求。交互性交互性 各各终终端用端用户户可以通可以通过终过终端、端、键盘键盘、鼠、鼠标标等等输输入入输输出出设备设备与系与系统统交互，控制作交互，控制作业业的运行，得到系的运行，得到系统统的服的服务务。独立性独立性 用用户户各自独立地使用各自独立地使用计计算机。算机。第44页，此课件共105页哦（3）实时操作系统 系系统统能及能及时时响响应应随机随机发发生的外部事件，并能在最短的生的外部事件，并能在最短的时间时间内完成内完成对对事件事件的的处处理。其特点是：理。其特点是：及及时时响响应应 实时实时任任

37、务务必必须须在指定的在指定的时时限内响限内响应应或完成。或完成。交互功能交互功能 实时实时系系统统仍然要求仍然要求满满足用足用户户的的实时实时交互要求。交互要求。高可靠性高可靠性 实时实时系系统统往往用于工往往用于工业业、国防等、国防等对实时对实时性要求高的性要求高的场场合，合，如温度控制、如温度控制、卫卫星星发发射等。因此，系射等。因此，系统统的高可靠性的高可靠性远远比系比系统统性能更重要。性能更重要。第45页，此课件共105页哦（4）网络操作系统 计计算机网算机网络络是将地理上分布的各数据是将地理上分布的各数据处处理系理系统统或或计计算机系算机系统统互互联联，实现实现资资源共享、信息交源共

38、享、信息交换换和和协协作完成任作完成任务务。网。网络络操作系操作系统统是管理是管理计计算机网算机网络络，为为用用户户提供网提供网络资络资源共享、系源共享、系统统安全及多种网安全及多种网络应络应用服用服务务的操作系的操作系统统。网。网络络操作系操作系统统的基本特点是的基本特点是处处理上的分布，也就是功能和任理上的分布，也就是功能和任务务上的分布以及上的分布以及系系统统管理的分布。管理的分布。第46页，此课件共105页哦分布式操作系统（5）分布式系分布式系统统是将地理上分布的各数据是将地理上分布的各数据处处理系理系统统或或计计算机系算机系统统互互联联，实现资实现资源共享、信息交源共享、信息交换换和

39、和协协作完成任作完成任务务。分布式系。分布式系统统要求一个要求一个统统一一的操作系的操作系统统，以，以实现实现系系统统操作的操作的统统一性，其基本特点是一性，其基本特点是处处理上的分布，理上的分布，也就是功能和任也就是功能和任务务上的分布及系上的分布及系统统管理的管理的统统一。分布式系一。分布式系统对统对用用户户是是透明的，用透明的，用户户面面对对的是一个的是一个统统一的操作系一的操作系统统，他无法也不必知道系，他无法也不必知道系统统的内部的内部实现实现。第47页，此课件共105页哦操作系统的功能 3（1 1）处处理机管理理机管理对对被多道程序所共享的被多道程序所共享的CPUCPU进进行分配与

40、回收（行分配与回收（实质实质上就是如何上就是如何对进对进程程进进行合理行合理调调度）度），以提高，以提高CPUCPU的利用率。的利用率。（2 2）内存管理）内存管理一方面，一方面，对对多个程序多个程序进进行合理分配与回收内存空行合理分配与回收内存空间间，使内存利用率尽可能高；另一方面，必，使内存利用率尽可能高；另一方面，必须对须对各程序所占的内存空各程序所占的内存空间进间进行必要的存行必要的存储储保保护护，以防止作，以防止作业业信息被窃取或混淆。同信息被窃取或混淆。同时时，又要，又要满满足合理足合理的共享；必要的共享；必要时时，还还要利用外存空要利用外存空间进间进行内存行内存扩扩充。充。（3

41、3）I/OI/O设备设备管理管理对对各种外部各种外部设备进设备进行分配、回收以及共享，以提高行分配、回收以及共享，以提高设备设备利用率。利用率。（4 4）文件管理）文件管理随着磁介随着磁介质质存存储储技技术术的的进进步，磁步，磁带带、磁鼓、磁、磁鼓、磁盘盘等大容量等大容量辅辅助存助存储设备储设备普及使用，大普及使用，大量用量用户户程序、数据的存程序、数据的存储组织储组织、存、存储储保保护护、共享等一系列、共享等一系列问题问题，构成了操作系，构成了操作系统统中文件中文件管理的主要内容。管理的主要内容。第48页，此课件共105页哦操作系统的功能 3（1）处理机管理 进进程程调调度又称度又称为处为处

42、理机理机调调度。在多道程序系度。在多道程序系统统中，有多个中，有多个进进程争程争夺处夺处理机。理机。进进程程调调度的任度的任务务是是协协调调和控制各和控制各进进程程对对CPUCPU的使用，它直接影响的使用，它直接影响CPUCPU利用率及系利用率及系统统性能。性能。在下列情况下会出在下列情况下会出现进现进程程调调度：度：正在正在执执行的行的进进程已运行完程已运行完毕毕；正在正在进进行的行的进进程由于等待某种条件的程由于等待某种条件的发发生（如生（如I/OI/O请请求）；求）；分分时时系系统执统执行行进进程的程的时间时间片已用完；片已用完；就就绪队绪队列中出列中出现现高高优优先先级级的的进进程申程

43、申请请使用使用CPUCPU等。等。时间片到等待事件发生进程调度释放执行状态等待状态就绪状态事件发生第49页，此课件共105页哦（2）内存管理 存存储储器管理主要是器管理主要是对对主存主存储储空空间间的管理的管理,包括：包括：内存分配内存分配 为实现为实现多道程序共享内存而多道程序共享内存而进进行的内存的行的内存的动态动态分配、分配、动态动态回收，包含回收，包含管理内存分配表、制定分配策略、确定内存区域的划分方式等。管理内存分配表、制定分配策略、确定内存区域的划分方式等。内存空内存空间间共享共享 包括共享内存包括共享内存资资源和内存区域信息共享。源和内存区域信息共享。存存储储保保护护 为为了避免

44、内存中多道程序之了避免内存中多道程序之间间的相互干的相互干扰扰，必，必须对须对内存中程序、内存中程序、数据和信息数据和信息进进行保行保护护。地址映射地址映射 在多道程序系在多道程序系统统中程序装入内存前通常中程序装入内存前通常为逻辑为逻辑地址，地址，编编址从址从0 0开始。开始。为为保保证证程序的程序的执执行，操作系行，操作系统统需要需要为为它分配一个合适的存它分配一个合适的存储储空空间间，并将程序，并将程序执执行行时时要要访问访问的地址空的地址空间间中的中的逻辑逻辑地址地址变换变换成内存空成内存空间间中中对应对应的的实际实际物理地址。物理地址。这这种地种地址的址的转换过转换过程称程称为为地址

45、映射或重定位。地址映射或重定位。内存内存扩扩充充 利用外存空利用外存空间间来来逻辑扩逻辑扩充内存，也就是把充内存，也就是把暂时暂时不用的程序、不用的程序、数据数据调调至外存的某特定区域。至外存的某特定区域。这这个区域被作个区域被作为为系系统统的的逻辑逻辑内存使用。内存使用。第50页，此课件共105页哦I/O设备管理（3）设备设备管理的内容包括：管理的内容包括：向用向用户户提供使用外提供使用外设设的方便接口。的方便接口。充分充分发挥设备发挥设备的效率，提高的效率，提高CPUCPU与与设备设备之之间间、设备设备与与设备设备之之间间的并行工作程度。的并行工作程度。第51页，此课件共105页哦（4）文

46、件管理 文件系文件系统统是指操作系是指操作系统统中中负责负责管理和存放文件信息的管理和存放文件信息的软软件机构，它向用件机构，它向用户户提供提供了一种了一种简简便、便、统统一的存取和管理信息的方法。文件系一的存取和管理信息的方法。文件系统统的功能包括：的功能包括：文件存文件存储储空空间间（外存）的管理。（外存）的管理。文件名到文件存文件名到文件存储储空空间间的映射，的映射，实现实现文件文件“按名存取按名存取”。实现对实现对文件的各种操作。文件的各种操作。支持文件的共享。支持文件的共享。提供文件的保提供文件的保护护与保密措施。与保密措施。第52页，此课件共105页哦操作系统的用户接口 4用用户户

47、可以通可以通过过以下两种接口以下两种接口获获得操作系得操作系统统服服务务。（1 1）命令接口）命令接口通通过过命令解命令解释释程序提供的一程序提供的一组联组联机操作命令，从机操作命令，从键盘键盘直接直接操操纵计纵计算机。算机。（2 2）系）系统调统调用接口用接口用用户户在程序中使用系在程序中使用系统统提供的一提供的一组组系系统调统调用来使用用来使用计计算机。算机。第53页，此课件共105页哦 处理机管理处理机管理13.2.2处处理机管理是操作系理机管理是操作系统统的主要的功能，它的主要的功能，它实现实现的是的是对处对处理器的分配，理器的分配，并并对对其其进进行有效的控制和管理。在行有效的控制和

48、管理。在现现代操作系代操作系统统中，中，处处理器的分配和理器的分配和调调度都是以度都是以进进程程为单为单位的，因而位的，因而对处对处理器的管理也可以理器的管理也可以视为对处视为对处理器理器的管理。的管理。第54页，此课件共105页哦进程的概念1进进程是可并程是可并发执发执行的程序在行的程序在给给定数据集合上的一次定数据集合上的一次执执行行过过程，是系程，是系统进统进行行资资源分配和源分配和调调度的一个独立的基本度的一个独立的基本单单位位和和实实体，是指体，是指执执行一个映像程序的行一个映像程序的总环总环境境 。第55页，此课件共105页哦进程的特征进程的特征 2（1 1）动态动态性性进进程是程

49、序程是程序执执行的一次行的一次动态过动态过程，具有生命期。一个程，具有生命期。一个进进程要程要经历经历“创创建建调调度度撤撤销销”三个三个过过程。程。（2 2）并）并发发性性使程序能与其他程序并使程序能与其他程序并发执发执行，行，这这是引入是引入进进程的目的。程的目的。（3 3）独立性）独立性进进程是系程是系统统分配分配资资源、独立运行的基本源、独立运行的基本单单位，各位，各进进程程间间相互独立。相互独立。（4 4）异步性）异步性各各进进程各自独立地、按不可程各自独立地、按不可预预知的速度向前推知的速度向前推进进。第56页，此课件共105页哦进程结构 3进进程由程由进进程控制程控制块块（PCB

50、PCB）、程序及数据集合三部分）、程序及数据集合三部分组组成。成。进进程控制程控制块块是系是系统统感知、管理和感知、管理和调调度度进进程的唯程的唯一依据。一依据。第57页，此课件共105页哦 进程的三种基本状态及相互转换进程的三种基本状态及相互转换 4所所谓谓基本状基本状态态，是指，是指进进程的当前行程的当前行为为。进进程具有三种基本状程具有三种基本状态态，并可以在一定的条件，并可以在一定的条件下相互下相互转换转换。图图13-2-113-2-1是三种基本状是三种基本状态态的的转换转换示意示意图图。就就绪绪状状态态 进进程已程已获获得除得除CPUCPU以外的所有以外的所有资资源。系源。系统统中中