文档介绍：一、数据结构与算法
1、数据结构是指:数据元素的集合(或数据对象)及元素间的相互关系和构造方法
数据结构按逻辑关系分:线形结构和非线性结构,非线性结构分:树结构和图结构
算法换数据结构密切相关,数据结构是算法的基础,算法总是建立在一定的数据结构上,合理的数据结构会使算法简单高效
2、常用数据结构
线性表
栈和队列
串
数组、矩阵、广义表
二、操作系统知识
1、计算机系统中的软件通常分:系统软件和应用软件
应用软件是指用户利用计算机软硬件资源为某一专门目的而开发的软件
系统软件是计算机系统的一部分,用于支持应用软件的运行,为用户开发应用提供一个平台
2、操作系统的作用:
通过资源管理提高计算机系统效率
改善人机界面向用户提供友好的工作环境
操作系统的特征:并发行(concurrency)、共享性(sharing)、虚拟性(virtual)、不确定性(non-determinacy)
操作系统的五大管理功能:
进程管理:实质是对处理器执行时间的管理,采用多道程序等技术将CPU真正合理的分配给每个任务
包括进程控制、进程同步、进程通信、进程调度
文件管理:又称信息管理
包括文件存储空间管理、目录管理、文件读写管理和存取控制、软件管理
存储管理:主要是对主存储器“空间”进行管理
包括存储分配和回收、存储保护、地址映射或变换、主存扩充
设备管理:实质是对硬件设备的管理
包括输入输出设备的分配、启动、完成和回收
作业管理:
包括任务、界面管理、人机交互、图形界面、语音控制、虚拟现实等
3、操作系统分类(7类):批处理操作系统、分时系统、实时系统、网络操作系统、分布式操作系统、微机操作系统、嵌入式操作系统
批处理操作系统:分为单道批处理和多道批处理
批处理操作系统中,作业由用户程序、数据和作业说明(作业控制语言)3部分构成
优点:通一批作业内各作业自动依次执行,改善了CPU和I/O设备的使用效率,提高了吞吐量
缺点: 磁带或磁盘需人工装卸,作业需人工分类,监督程序易遭到用户程序破坏,批作业中的错误只能等到作业结束才能修改
分时系统:分时系统将CPU工作的时间划分为许多很短的时间片轮流给各终端用户服务
分时系统特点:多路性、独立性、交互性、及时性
响应时间是分时系统的重要指标,是用户发出终端命令到系统作出响应的时间间隔
实时系统:对交互能力要求不高,对可靠性要求高;以“事件驱动”方式来设计
实时是指:计算机对外来信息能够以足够快的速度处理,并在被控对象允许的时间范围内作出快速反应
实时系统可分为:实时控制系统、实时信息处理系统
实时系统的特点:快速的响应时间,有限的交互能力、高可靠性
与分时系统的区分:
系统的设计目标不同、交互性的强弱、响应时间敏感程度不同
网络操作系统:功能包括高效可靠的网络通信、对网络中共享资源有效管理、提供电子邮件、文件传输、共享硬盘、及打印机服务,网络安全管理,提供互操作能力
分布式操作系统(是更高级的网络操作系统,保持网络操作系统所有功能的同时,又具有透明性、可靠性和高性能),与网络操作系统最大的区别在于网络操作系统工作时必须确认网址
微机操作系统
MS-DOS操作系统是事实上的16位单用户单任务操作系统标准
嵌入式操作系统
运行在嵌入式智能芯片环境中,对整个智能芯片几个控制部件及装置等资源进行统一协调、处理、指挥和控制的系统软件
4、研究操作系统的观点:
资源管理的观点
从资源管理的观点来看,操作系统管理的对象是计算机系统的资源
通常将操作系统分为处理机管理、存储管理、设备管理、文件管理、用户与操作系统接口
主要研究的问题:记住资源的使用情况、确定资源的分配策略、分配/回收资源
虚拟机(virtual machine)的观点:虚拟机加裸机(bare machine)等于虚拟计算机,操作系统的全部功能成为操作系统虚拟机
虚拟机的观点是从功能分解的角度出发,考虑操作系统的结构,将操作系统分为若干层,每层完成特定功能,并向上提供支持,构成它的运行环境
5、进程是资源分配和独立运行的基本单位
程序由程序段组成,各程序段先后执行的次序关系可以用前趋图表示
前趋图是一个有向无循环图,图由节点和节点间的有向边组成
节点代表程序段的操作,有向边代表两程序段的操作间存在前趋关系(->)
Pi->Pj Pi是Pj的前趋,Pj是Pi的后继
程序顺序执行的特征:顺序性、封闭性、可再现性
程序并发执行的特征:失去了程序的封闭性、程序和机器执行程序的活动不再一一对应、并发程序间的相互制约性
引入进程的原因:由于程