1、计 算 机 软 件 技 术 基 础( 第 二 版 )李 芳芸 沈 被娜 王 选民 编 著清 华 大 学 出 版 社内 容 简 介本书是计算机基础教育用书之一, 适用于非计算机专业的本科生、研究生及 广大从事计算机应用工作的科技人员。本书 用较短 的篇幅、通俗 的语言, 系统 地介绍 了计算 机软 件技 术的基 础知 识, 其中包括软件和软件工程概论、数据结构、操作系统和数据库系统四章。每章 既有基本原理的叙述又有常用实例的介绍, 各章后均附有习题。( 京) 新登字 158 号计算机软件技术基础( 第二版)李芳芸 沈被娜 王选民 编著 清华大学出版社出版 北 京 清 华 园 通县宏飞印刷厂印刷新
2、华书店总店科技发行所发行开 本 : 7 8 7 1 09 2 1 / 1 6 印 张 : 1 5. 7 5 字 数 : 3 7 2 千 字1 99 3 年 6 月 第 2 版 1 99 3 年 6 月 第 1 次 印 刷印数: 0000110000ISBN 7-302-01200-8/ T P 450定价: 7. 30 元计算 机基 础教 育丛 书出 版说 明近年来, 我国的计算机应 用事业迅 速发展, 大批 科技人员、大 中学生、管理人 员, 以 及 各行各业的在职人员都迫切要求学习计算机知识, 他们已经认识到, 计算机知识是当代知 识分子的知识结构中不可缺少的重要部分。计算机应用人 才的队
3、伍由两部 分人组成: 一部 分是从计 算机专 业毕业的 计算机专 门 人才, 他们是计算机应用人才队伍中的骨干力量; 另一部分是各行各业中从事计算机应用 的人才, 他们既熟悉本专业的业务, 又掌握计算机应用的技术, 人数众多, 是计算机应用人 才队伍的基本力量。他们掌握计算机知识的情况和应用计算机的能力在相当大程度上决 定了我国计算机应用的水平。因此, 在搞好计算机专业教育的同时, 在广大非计算机专业 中开展计算机基础教育是十分必要的。非计算机专业 中的计算机教 学, 无 论就目 的、内 容、教 学体系、教材、教学 方法等各 方 面都与计算机专业有很大的不同, 它以应用为目的, 以应用为出发点
4、。如果不注意这个特 点, 将会事倍功半。广大非计算机专业的师生、在职干部迫切希望有一套适合他们的教材, 以便循序渐进地迈入计算机应用领域, 并且不断地提高自己的水平。我们在前几年陆续编 写了一些适合初学者使用的教材, 受到广大群众的欢迎。许多读者勉励我们在此基础上进 一步摸索和总结规律, 为我国的广大非计算机专业人员编写一整套合适的教材。近年来, 全国许多专家、学者在这 个领域 作了有益 的探索, 写出 了一批受 到群众欢 迎 的计算机基础教育的教材。特别是全国高等学校计算机基础教育研究会作了大量的工作, 在集思广益的 基础上, 提 出了在高等学校 的非计算 机专业中 进行计 算机教育 的四个
5、层 次 的设想, 受到广泛的注意和支持。我们认为: 计算机的应用是分层次的, 同样, 计算机人才 的培养也是分 层次的; 非 计算机专业中各 个领域 的情况不 同, 也 不能一 律要求, 在进行 计 算机教育时也应当有不同的层次。对于每一个学习计算机知识的人, 还有一个由浅入深、 逐步提高的过程。我们认为, 编辑出版一套全面而有层次的计算机基础教育的教材, 目前不仅是十分必 要的, 而且是完全有条件的。在全国高等学校计算机基础教育研究会和许多同志的积极推 动和清华大学出版社的大力支持下, 我们决定编辑计算机基础教育丛书。它的对象是: 高等学校非计算机专业的学生、计算机继续教育或培训班的学员、广
6、大在职自学人员。本丛书包括计算机科学技术的一些最基本的内容, 例如计算机各种常用的高级语言、 计算机软件技术基础、计算机硬件技术基础、微型计算机的原理与应用、算法与数据结构、 数据库基础、计算机辅助设计基础、微机网络与应用、系统分析与设计等, 形成多层次的结 构, 读者可以根据需要与可能选学。本丛书的宗旨是针对广大非计算机专业的需要和特点来组织教材。敢于破除框框, 从 实际出发, 用读者容易理 解的体系和叙述 方法, 深入浅 出、循 序渐进 地帮助读 者更好地 掌 握课程的基本内容。希望我们的丛书能在这方面闯出自己的风格, 在实践中接受检验。本丛书的作者大多数是高等学校中有较丰富教学经验的教师
7、。但是, 由于计算机科学 技术的飞速发展以及我们的水平有限, 丛书肯定会存在许多不足, 丛书的书目和内容也应 当不断发展和更新。我们热情地希望得到社会各界和广大读者的批评指正。主编 谭 浩强 林定 基 刘瑞 挺1988. 10 前 言计算机软件技术基础于 1987 年 10 月由清华大学出版社出版第一版。通过几年的 教学实践, 广泛听取了广大读者提出的宝贵意见, 特别是得到了清华大学教务处及相关各 系同行们的支持, 与我们共同讨论确定了第二版的内容大纲。为使书的内容精练, 第二版中删除了原书中部分章节, 保留了概论、数据结构、操作系 统、数据库系统这四部分软件技术的基本内容。并在内容上进行了修
8、改与补充, 加强了系 统性和应用性。为便于教学和自学, 每章后面都附有习题。本书作为计算机基础教育丛书之一, 适用对象为非计算机专业的本科生、研究生及 广大从事计算机应用工作的科技人员。在计算机应用日益广泛, 特别是计算机软件飞速发 展的今天, 广大计算机应用软件的开发者和使用者迫切需要掌握计算机软件的有关知识。 本书包括了计算机软件的基础知识 数据结构, 计算机系统的核心软件 操作系统, 以及广为使用的数据处理软件 数据库系统。通过这些内容的学习能使读者在掌握这 些知识的基础上, 进一步提高使用计算机的能力和研制应用软件的水平。本书第一、第四章由李芳 芸编写, 第二 章由王选 民、沈 被娜、
9、李芳芸 编写, 第三章由 沈 被娜编写。我们对在第二版的修订出版过程中所得到的各方面的帮助和支持表示感谢。限于我 们的水平, 书中缺点和问题难免, 敬请计算机软件教学工作者和广大读者提出宝贵意见。编 者 目 录1. 1 计算机软件的发展1 2.5.2 二叉树及其性质53 1.1.1 汇编语言的出现1 2.5.3 二叉树的遍历55 1.1.2 高级语言的出现3 2.5.4 二叉树的应用57 1.1.3 操作系统的形成52.6 图65 1.1.4 计算机网络软件、数据库 2.6.1 图的定义和基本概念65软件的出现7 2.6.2 图的存储结构681. 2 计算机软件8 2.6.3 图的遍历71 1
10、.2.1 计算机系统资源8 2.6.4 最短路径73 1.2.2 计算机软件定义9 2.6.5 关键路径法781. 3 软件的研制102.7 检索81 1.3.1 软件工程学的基本概念10 2.7.1 线性检索法81 1.3.2 系统分析与设计方法介绍12 2.7.2 对半检索法82 1.3.3 结构化系统分析与设计15 2.7.3 分块检索法85第一章 概论 1 2.5.1 树的定义及其存储结构 52习题一17参考文献172.1 概述18 2.8.2 冒泡排序90 2.1.1 引言18 2.8.3 线性插入排序91 2.1.2 什么是数据结构19 2.8.4 对半插入排序92 2.1.3 与
11、数据结构相关联的运算22 2.8.5 快速排序932.2 线性表23 2.8.6 归并排序94 2.2.1 线性表的逻辑结构23习题二95 2.2.2 线性表的存储结构23参考文献99 2.2.3 线性表的基本运算25第三章 操作系统 101 2.2.4 线性表的应用28 3. 1 引论1012.3 数组31 3.1.1 什么是操作系统101 2.3.1 数组的定义31 3.1.2 操作系统的分类102 2.3.2 数组的顺序存储结构31 3.1.3 操作系统的功能和特性105 2.3.3 稀疏矩阵34 3. 2 存储管理1082.4 栈与队40 3.2.1 存储管理的功能及有关 2.4.1
12、栈的结构与运算40的概念108 2.4.2 栈的应用41 3.2.2 实存储管理110 2.4.3 队的结构与运算45 3.2.3 虚拟存储管理116第二章 常用数据结构及其运算 18 2.7.4 散列检索法85 2. 8 排序89 2.8.1 选择排序90 2.4.4 队的应用46 2. 5 树51 3. 3 处理机管理124 3.3.1 概述124 3.3.2 作业调度和进程调度126 4.1.2 数据描述187 3.3.3 并行程序设计中的 4.1.3 三类数据模型189几个问题130 4.1.4 数据库管理系统9 3.4.1 概述140 4.1.5 用户访问数据的过程195 3.4.2
13、 设备分配程序1434.2 关系数据库理论基础196 3.4.3 设备处理程序144 4.2.1 关系代数196 3.4.4 虚拟设备 假脱机 4.2.2 数据依赖概念203系统145 4.2.3 规范化理论205 3.4 设备管理140( DBMS )194 3.5 文件管理146 3.5.1 引言146 3.5.2 文件结构及存取方式148 3.5.3 文件目录管理150 3.5.4 文件存储空间管理153 3.5.5 文件的共享与文件系统的安全性155 3.5.6 文件的使用及文件系统的一般模型156 3. 6 用户接口160 4.2.4 结构化查询语言 SQ L209 4.3 数据库设
14、计213 4.3.1 数据库设计的目的及设计阶段213 4.3.2 概念结构设计工具 E -R 方法216 4.3.3 逻辑结构设计220 4.3.4 物理结构设计224 4.3.5 数据字典230 4.4 数据完整性及安全性230 3.6.1 概述160 4.4.1 数据完整性230 3.6.2 系统调用命令160 4.4.2 数据安全性232 3.6.3 脱机作业控制方式162 4.4.3 数据库恢复233 3.6.4 联机作业控制方式162 4. 5 分布式数据库系统234 3. 7 网络环境下的操作系统167 4.5.1 概述234 3.7.1 计算机网络167 4.5.2 分布式数据
15、库的系统类型及 3.7.2 网络操作系统172数据分布方式235习题三182 4.5.3 分布式数据库系统设计中参考文献183的问题237第四章 数据库系统 184习题四241 4.1 绪论184参考文献243 4.1.1 什么是数据库系统184第一 章 概 论 1.1 计算机软件的发展 自 1946 年世界上出现 第一台电子数 字计算 机以来, 仅仅几 十年时 间, 计 算机系统 得 到了飞速发展。人们习惯按组成计算机的元件的演变来划分计算机的发展阶段。计算机 元件的演变分为四个阶段, 计算机的发展也相应分为四个时代。第一代为电子管时代( 19451959) 。在这个阶段计算机的主要逻辑元件
16、是电子管, 存 储器为水银延迟线或静电屏。第二代为晶体管时代( 19591965) 。在这个阶段计算机的主要逻辑元件是晶体管, 存 储器由磁芯构造。第三代为集成电路时代( 19651971) 。在这个阶段计算机主要逻辑元件是集成电路,存储器除磁芯外还增加了镀线。第四代为大规模集成电路时代( 自 1971 年开始) 。大规模集成电路的集成度超过 100个门电路, 每平方英寸包含 50000 个元件以上, 存储器用 M OS 和双极型元件。现在 正在研制 第五代 计算机系 统, 简 称 FGCS( Five Gener ation Comput er Syst em ) , 其关键技术是超大规模集
17、成电路( VL SI) 结构、并行处理、基于关系数据库 的知识库, 以及 人工智能和 模式处理的应用。其 主要目标是 具有问题 求解和推 理能力, 能进 行知识库 管 理, 具有智能接口。因此 F GCS 是具有人工智能知识信息处理能力和非数值运算能力的高 性能计算机。F GCS 硬件 与软件设 计和制 造的目标 是为用 途广泛的 知识工 程服 务, 因此应 该包 括 专家系统、知识库, 能迅速进行相联检索, 能进行逻辑推理操作。在程序结构和软件中利用 并行方式达到高速运行, 而且机器和使用者之间可以使用自然语言和图像进行通信。F GCS 为实现以上目标和功能按照三个子 系统组织工作, 第一是
18、管理 知识库子系统,第二是问题求解和推理子系统, 第三是人与机器之间的交互子系统。图 1.1 示出第五代计算机系统的硬件、软件及与人的关系。硬件与软件的关联随计算 机的发展越来越紧密, 在 FGCS 中就充分显示出硬件、软件及人的统一。在整个计算机的发展过程, 随着计算机硬件技术的不断发展及广泛使用, 软件也逐步 丰富与完善, 而软件的发展又大大地促进了硬件的发展, 最终成为一个完整统一的整体。计算机软件也有标志其发展的四个阶段, 下面作一个详细的介绍。1.1.1 汇编语 言的出现一台没有装入任何软件的计算机, 我们称它为裸机。裸机只认识“0”、“1”两种代码, 程 序人员只能用机器指令或称机
19、器语言来编写程序。这样就要求程序设计人员熟记计算机 的全部指令, 工作量很大且容易出错又不易于修改。由于各种计算机的机器指令不一定相图 1.1同, 所编制的程序只适用于某一特定的机器, 局限性很大。在早期的计算机中, 采用了建立 标准子程序或标准程序库的办法, 这虽然在一定程度上缓和了工作量大的矛盾, 但不能从 根本上解决 问题。为了摆脱用机 器指令编码 的困难, 出现了 用指令 符号来编 制程序的 办 法。用指令符号编制的程序称为符号程序, 在编制程序时, 只要记住用英文名称缩写的指 令的助记符就可以了。例如取数用 L DA 、加法用 ADD 等。在符号语言的基础上进一步发 展就是汇编语言。
20、用汇编语言编制程序要比用机器的指令代码方便得多, 便于检查和修改错误, 而且指 令、原始数据和结果数据的存放单元可由机器自动分配。然而, 计算机的内部结构是根据指令代码设计的, 也就是说它只能识别和理解用二进 制代码表示的机器指令, 不能识别和理解指令助记符。因此, 人们用汇编语言编出程序后, 必 须将 此程序 翻译 为机器 语言 程序, 称为 目的 程序 ( 目 标程序 ) , 机器 才能 执行并 算出 结 果。这个翻译工作是由预先装入计算机中的“汇编程序”完成的。汇编程序是一种“编译” 程序, 计算机有了它, 才能允许用 户在该计算 机上使用 汇编语言 编制程 序, 这 个程序称 为 汇编
21、语言程序或称为汇编源程序。汇编程序是计算机必不可少的软件。用汇编语言写的程序和用机器语言写的程序有相同之处, 又有不同之处。相同之处在 于程序主体部分几乎是一一对应的, 不同的是 0、1 数码换成了符号, 地址换成了可读的名 字, 另外还增加了关于 工作单元和常数 单元的成 分。这些不 同之处 也正是汇 编语言的 优 点, 使得用汇编语言编写的程序好写、好读、好改。由于汇编语言也是依赖于机器的, 因此称它为面向机器的语言。使用时必须了解机器 的某些细节, 如累加器的个数、每条指令的执行速度、内存容量等等。但也正由于它依赖于19机器, 就可以与机器语言程序一样可结合机器特点编出短小、高质量、执行
22、速度快的程序。 所以, 时至今日, 汇编语言仍起着重要作用。在一些计算机公司中仍用汇编语言编写系统 软件, 以保证高质量软件的功效。汇编程序的主 要功能是把用汇 编语言编 写的源程 序加工成 机器语 言写的目 标程序。 这由三个过程来完成, 如图 1.2 所示。图 1.2第一个过程, 用汇编语言编制出源程序;第二个过程, 将源程序输入到计算机内, 由汇编程序把它加工成计算机能够执行的目 标程序;第三个过程, 执行目标程序, 得到计算结果。源程序 由一串符 号化 的指令 组成, 一 般采用 标准 的 ASCI I 码, 当 汇编 程序加 工源 程 序时, 总是从头到尾, 一个符号接着一个符号地阅
23、读, 称为扫描源程序。从头到尾扫描一次 源程序为扫描一遍。一般汇编程序均扫描两遍, 第一遍把源程序中所有出现的名字进行造 表, 确定每个名字将占用的内存位置。第二遍扫描时, 按所造出的表, 把每条符号化指令代 换成数码形式的机器指令。此外汇编程序还具有一些附加的功能:查错功能: 当用户写的汇编语言不符合汇编语言所要求的书写格式、不符合语法要 求时, 汇编程序指出源程序的位置和出了什么性质的错误。修改功能: 汇编程序提供修改源程序的简便办法, 用户把修改的要求提供给汇编程 序, 由汇编程序实现对源程序的自动修改。打印功能: 在汇编过程中, 当发现错误时, 将错误信息印出来, 必要时可印出名字表
24、及目标程序, 还可印出修改后源程序的文本等。1.1.2 高级语 言的出现采用汇编语言编制程序, 仍要记住机器指令的助记符, 且所编的程序只能针对某一类 机器。为了解决这些问题, 出现了高级语言程序。它使得程序编制工作可以从专职程序设 计员手中解 放出来。高级语言的 出现大大方 便了程序 的设计工 作, 也促进了 计算机的 应 用, 使得计算机的使用由计算机专业人员扩大到各行各业。高级语言是按照一定的“语法规则”, 由表达各种意义的“词”和“数学公式”组成的。通 常把用程序设 计语言编制的程 序称为源程序, 而计 算机进行 运算仍 要根据目 的程序来 进 行。这中间也如同汇编程序一样, 要有一个
25、“编译器”, 把源程序“翻译”成目标程序。这种 程序设计的方法比较接近人们的习惯, 编出的源程序与具体机器的指令系统无关, 可适用 于任何机器, 因此人们把程序设计语言称为高级语言。目前, 世界上有几百种程序设计语言, 较通用的也有几十种, 各有其特点。我们以常用的几种语言为例, 介绍其特点。FOR TR AN 语言: 最常用的科学与工程计算的语言。其程序结构是分块结构, 一个 F OR T R A N 程序包含一个主程序块和 若干个子程序块。 程序的执行由主 程序块开始, 主 程序块可以调用子程序块, 子程序块间也可以调用, 但子程序块不可以调用主程序块。另 外, 程 序 中 的 变 量 地
26、 址 是 静 态 分 配 的, 不 能 包 含 递 归 子 程 序 和 动 态 数 组。总 的 来 讲, F OR T R A N 程序的结构比较简单, 而且可以分块书写、分块编译, 故使用起来灵活、方便。AL GOL 60 语 言: 主要 用于科 学与 工程计 算的 语 言, 其程 序结 构是 分 程序 嵌套 结 构。整个 A LGO L 60 是一个大分程序, 分程序中又可以嵌套进一层的分程序, 其嵌套的深 度可以任意, 内层分程序可以使用外层分程序定义的量, 反之则不可以。其变量地址是动 态分配的, 在进入分程序时分配, 在退出分程序时释放, 因此节省内存。而且允许递归子程 序和动态数组
27、。其程序结构比较严谨、清晰。COBOL 语言: FOR T R AN 和 AL GOL 60 语言 都是 适于数 据处 理的 计 算机 语言, COBOL 语言中 引入了按 层次 结构来 描述 的数 据部分, 这 种数 据描述 形式 完全适 合于 现 实生活中各种管理信息。另外, 其程序设计采用了自然语言的程序设计风格, 程序的书写 采用接近英语的形式。由于这些原因, 在商业、工业和行政管理部门被广泛地使用。PASCAL 语 言: 这 是一种 典型的 系统 结构化 程序 设计 的语言, PA SCAL 语 言的 出 现和结构程序设计技术的发展推动了编译程序工程技术的发展。PASCA L 语言强
28、调概念 清晰, 实现简化, 方便用户; 强调程序的可靠性, 易于验证; 有较好的结构, 减少了错误的发 生并易于阅读。因此虽然问世较晚, 但却得到人们的极大重视。C 语 言: C 语 言是 1972 年设 计出 并首 先 在 U NI X 操作 系 统、P DP -11 机器 上实 现 的。U N IX 操作系统是用 C 语言书写的, C 语言也与 U NI X 操作系统紧密地联系在一起。 但目前, C 语言却独立于 U N IX 系统, 独立于 PDP-11 系列而蓬勃发展了起来。用 C 误言 编写的程序很容易移植, 所以具有“可移植的汇编语言”的称号。此外, 由于它具有丰富的 运算符和表达
29、式, 以及先进的控制结构、数据结构, 因此还具有表达能力强、编译出的目标 程序质量高、语言简单灵活、易于实现等特点。C 语言不仅可用来 写操作系统、编译程序、 数据库管理系统等系统软件, 也可以用来写各种应用软件, 例如企事业管理、办公自动化、 工业自动控制、图形处理等。C 语言已成为当今最流行的程序设计语言。PL / 1 语 言: 这 是一 种 大型 通 用 语言, 它 综 合了 FOR T RA N 、AL GOL 60、COBOL 等 语 言 的 特 点。 其 表 达式 和 语 法 来 自 FOR T RA N 语 言, 分 程 序 结 构 和 类 型 说 明 来 自 A L GOL 6
30、0 语 言, 数据描 述取 自 COBOL 语言, 控 制结 构和总 体结 构则兼 有 FOR T RA N 和 A LGO L 60 语言的特点。它包含了各种功能的语言成 分, 既能进 行数值计算又能 进行 数据处理; 可以作表处理, 又可以作符号串处理; 还具有格式丰富的输入/ 输出设施和中断 并行等能力。用户可以根据需要选用它的一部分或全部。LI SP 语 言: 在 计算机的 应用中 有一个非 常有意义 的领域 叫做非数 值处理, 例如 公 式的推导、用机器证明定 理、下棋、印刷 排版、编辑修 改、版 面设计、机器 翻译、语言研究 等 人工智能问题。这些非数值 处理问题是 FOR T R
31、A N 、A LGOL 60、COBOL 等语言不 能解 决的, 例如( X+ Y ) 2 的计算, 在 FOR T RA N 语言中只 能先给 出变量 X 和 Y 的数 值, 然 后 才能 计算, 绝不能推 导出( X+ Y ) 2 等于 X2 + 2XY + Y2 来, 然 而 LI SP 语言 可以解 决这 类问题。L I SP 语言有两个基本的数据类型, 叫做原子和表。一般原子定义为以大写字 母打 头, 由大写字母和数字串组成, 其长度不超过 30 个字符的串。表是递归定义的, 也就是在 表的定义中 又可以用到表, 每个表可以 构成一个 复合表。还 定义了 一组简单 而有效的 操 作,
32、 例如由两个表构造一个复合表的运算, 从一个表中选出其第一个分量的运算和从一个 表中去掉其 第一个分量而取 余下部分的运算。通 过原子、表、表的运算 和定义的 L ISP 函 数, 就可以进行符号演算、公式推导、博奕等种种非数值处理的工作。L ISP 语言的理 论基 础是数理逻辑, 它简单但又有很强的表达能力。在运行过程中动态分配大量的存储单元, 可以随时把无用的存储单元收集回来再用, 这也是非数值处理语言的一个共同特点。除以 上通用 的程 序设计 语言 外, 还有专 用于 某种 特定用 途的 语言, 这 种 语言 种类 很 多, 例 如飞机制造工业中 的机翼设计语言、造 船设计中 的船体放
33、样语言、专用 于计算机 线 路设计的语言、专用于系统仿真的语言以及用于编辑、排版的语言等。近年来为了适应大型软件开发的需要, 并由于软件工程学概念的广泛普及, 还出现了超高级语言、蓝图语言等。超高级语言功 能强且简洁, 但运行时 需要大 型支撑系 统的支 持, 这 增加了存 储容量, 也降低了用这种语言写的程序的执行速度, 因此它不适于用来开发实际的大系统, 而是用 来开发模型系统。模型系统是对系统分析阶段的检验, 是进一步确定系统需求的工具。模 型系统通常具有实际系统的主要功能而不是全部性能, 而且可以降低对接口、可靠性和程 序质量的要求; 此外还可以省掉许多文档资料方面的工作, 所以可以大
34、大降低模型系统的 开发成本。在 U N IX 操作系统上的命令解释语言 Shell 就是超高级语言的代表。蓝图语言是为 设计软件和描 述软件 的一种方 法论 软件 蓝图方 法论使用 的语言。 软件蓝图方法论是由美国马里兰大学朱耀汉教授提出来的。它指导软件工程师采用自顶 向下、模块化和结构化的 设计原理; 它只规定 了必须实 现的设计 结构, 并没有 硬性规定 必 须采用的具体设计方法。它把软件设计和软件实现作为相对独立的两个不同阶段, 把软件 设计分为三级。A 级用概念性的设计提供软件的整体概貌; B 级用一个结构化设计描述控 制流( 数据操作序列) 和数据流( 数据元素的序列) ; C 级用
35、详细的设计来描 述软件的实现。 所用蓝图语言是自然语言和形式化的软件设计语言的混杂语言, 它有统一的语法, 严格规 定了三级设 计中什么地方用 自然语言、什么地方 用软件 设计语言。 使用自然 语言描述 简 明、易读易理解; 使用软件设计语言描述精确, 可保证设计的完整性。蓝图语言吸收了两者 的优点。超高级语言和 蓝图语言都是将 软件分析 和设计两 个阶段结 合起来, 为实 现软件工 程 提供工具, 是具有发展前景的语言。1.1.3 操作系 统的形成为了充分发挥计算机的高工作效率, 需要解决以下问题。首先要处理好人对机器过多 的干预或手动操作过多的问题。这就要求用户组织好交给计算机来完成的每个
36、作业。这 就需要有一个管理软件, 这个管理软件具有能接受和处理用户提交作业的功能。其次, 要处理好中央处理机与外围设备在速度上快慢不匹配的问题。要求管理软件具 有处理中断的 功能, 应提 供一种简便的、统一 的调用外 围设备的 手段, 统一管 理外围设 备的输入和输出。第三, 给多个用户提供使用计算机的方便, 给中央处理机设置多个终端。因此要求管 理软件具有处理来自不同终端的多道作业的功能。总之, 要使计算机所 有资源( 包括中央处 理机、存储器、各种 外部设备 和各种 软件) 协 调一致、有条不紊地工作, 就要有一个功能强大的管理软件进行统一调度与管理。这个软 件称为操作系统, 具有操作系统
37、的计算机系统常称为虚拟计算机。计算机操作经 过了手工阶段、早期的 批处理 阶段、执行系统 阶段、多道程 序系统和 分 时系统阶段。多道程序系统和分时系统的出现才标志着操作系统的正式形成。1. 手工操作阶段( 50 年代初至 50 年代中期)用户使用计算 机是将机器语言 或高级语 言编制的 程序凿在 纸带或 卡片上, 用户扳 动 扳键、启动按钮、光电输入机或卡片读入机读入程序, 程序运行的结果由打印机印出。出现 故障时, 用计算机上的扳键进行修改。手工操作的特点是计算机软、硬件资源只能由一个用户的一个程序独占, 而且操作过 程必须人工干预。2. 早期批处理阶段( 50 年代中期至 50 年代末期
38、)手工操作占用的时间与计算机运行时间的不匹配, 随着计算机运行速度的提高, 问题 越来越大, 因此出现了早期的批处理方式。计算机的系统操作员将各个用户提出的作业组 合成一批作业, 利用常驻 在内存中的监督 程序, 将各个 用户的作 业逐个 输入到磁 带中, 由 磁带再逐个将作业调入内存运行, 运行结果也先输入至另一磁带上, 再逐个打印出来。这种 批处理 方式 为联机 批处 理, 外部设 备如 输入 机、打 印机 和主 机的 工 作仍 串联 运 行。为解决这个问题采用脱机批处理方式。脱机批处理方式是增加一台卫星机( 小型计算 机) , 通过卫星 机将卡片输入到 磁带上, 同 样在磁带 上的输出
39、结果也 通过卫星 机后再打 印 出来。这样可以达到主机和输入、输出设备并行工作, 从而解决了外部设备与主机运行速 度不匹配的矛盾, 提高了主机使用效率。3. 执行系统阶段( 50 年代末至 60 年代初)由于早期批处 理方式中的监督 程序常常 被用户程 序破坏, 需要 解决对监 督程序的 保 护问题, 因此产生了执行系统。在执行系统中使用了通道设备并提出了中断处理的概念。通道设备解决 了多台外设与主 机并行工 作的问题; 中断 处理是 指外围设 备或通道 发 出信号要求暂时停止主机当前的工作, 而转去处理外设提出的要求 中断处理程序。中断处理程序以及负责控制输入、输出的服务程序称为执行系统,
40、它对其它的系统程 序和应用程序起控制指挥作用。而原来的监督程序只起相互调用的作用。执行系统常驻 内存, 其它程序在其指挥下工作, 从而增加了对系统的保护能力。执行系统的出现还促进了软件技术的发展, 使系统程序设计实现模块化结构, 使系统 结构简单, 易于设计、修改和扩充。4. 多道程序系统( 60 年代初至 60 年代中期)为 提高 计算机 中央 处理器 ( CPU ) 的运行 效率, 在 内存中 应保 持有多 道程 序, 而且 程 序可以交替占用 CPU 和外部设备。因此在多道程序系统中解决了以下几个主要问题:对 CPU 来说, 要 解决在何时、以何种策略把 CPU 分配给 哪一道 程序使用
41、 的问题。通常把解决这一问题的过程称为调度算法。对 存储器 来说, 要 解决多 道程 序在内 存中 定位、分配 及避 免互 相冲 突 和破 坏的 问 题。把解决这一问题称为存储管理问题。对外部设备 来说, 在多 道程序下提 高设备 利用率, 避免发 生矛盾, 负责 外部设备 的 分配、释放、控制及信息交换的程序称为设备管理程序。在辅助存储器的管理方面, 出现了文件系统, 使用户可以把程序和数据以文件形式 存放于辅助存储器中。管理及使用文件的程序称为文件管理程序或文件系统。5. 分时系统( 60 年代中期以后)多道程序系统保持并发展了执行系统的特点, 使操作更加自动化, 但对一般的使用者 来说,
42、 更希望能直接与机器接触, 以便随时发挥人的主观能动作用, 这样出现了分时系统。 分时系统的特征是在一台计算机上挂有若干个终端, 每一个终端提供给一个用户使用, 因 此用户可以通过自己的终端, 用对答方式( 交互式) 直接控制自己的程序, 随时对程序作必 要的修改和 补充。在分时系统中, 系统将 CPU 的时间 轮流分给 每个联 机终端, 这样使 用 户感到好像只有他在使用机器。因此称这种分时系统为一种高级联机操作方式。多道程序和分 时系统是操作系 统形成的 标志, 随着计算 机应用 的扩大和 计算机硬 件 的不断发展, 操作系统更加完善, 功能更为扩大, 出现了实时操作系统、网络操作系统等。 操作系统的出现是软件发展的一个重大转折, 也是计算机系统的一个重大转折。操作 系统本身是 一个庞大的程序, 在它的控 制下, 计 算机系统 的每个 部件( 既包括 硬件也包 括软件) 最大限度地发挥着作用, 因此操作系统是软件系统的核心。目前, 操作系
