第一章
1、1TB=1024GB;常见的I/O总线:PCI、USB通行串行总线、1394总线。
2、冯·诺依曼提出了“存储程序”的思想,此思想可简化为三点:
(1)计算机应用包括运算器、控制器、存储器、输入/输出设备;
(2)计算机内部应采用二进制来表示指令和数据;
(3)将编好的程序和数据送进内存储器,然后计算机自动的逐条取出指令和数据进行分析、处理和执行。
3、计算机系统的基于存储程序式结构,程序与数据均存放在存储器内,存储器分为内存储器和外存储器两大类。中央处理器(CPU)只有直接对内存储器中的数据进行处理,输入设备中得到的控制指令必须先转换成二进制代码送入计算机的内存中存储起来,才能被CPU访问。运算器的功能是对二进制代码进行算术运算和逻辑运算。
4、高速缓存(如Cache)是最贵最快的存储介质,接下来依次为主存、第二存储器(联机存储)、第三存储器(脱机存储)。
5、RAM成为随机存储器,上面的信息既可读出也可写入,但一断电RAM上存放的信息就丢失。如计算机内存
6、数字信号处理器(DSP)主要用于快速处理大量复杂数字信息的领域,如通信设备、雷达、数字图像处理设备、数字音频设备中。彩色电视机应用电信号
7、广域网包括——X.25、帧中继、SMDS、B-ISDN和ATM;
局域网包括——FDDI(光纤分布式数据接口);
8、局域网的特点:(1)覆盖地理范围有限;(2)传输速率高,误码率低;(3)一般为一个单位所有,便于建立、维护与扩展。
9、局域网常用的拓扑结构有星形、环形、总线型和树形等几种。
10、调制:将数字信号转换成电话线上传输的模拟信号;解调就是反过来。
11、网络操作系统就是在计算机网络中管理一台或多台主机的软硬件资源、支持网络通信、提供网络服务的程序集合。其主要任务是对全网资源进行管理,实现资源共享和计算机间的通信和同步。
12、WWW是以超文本标注语言(HTML)和超文本传输协议(HTTP)为基础,能够提供面向Internet服务的、风格一致的用户界面的信息浏览系统。
13、WWW的描述语言为HTML(超文本标记语言);
14、WWW服务采用客户机/服务器(C/S)工作模式;
15、统一资源定位符(URL--Uniform Resource Locator)或称为网页地址,是因特网上标准的资源地址,由三部分组成:协议类型、主机名和路径/文件名。
16、搜索引擎是因特网的一个WWW服务器,它的主要任务是在因特网中主动搜索其他WWW服务器的信息并对其自动索引,将索引内容存储在可供查询的大型数据
库中。用户可以利用搜索引擎所提供的分类目录和查询功能查找所需信息。
17、Internet是一个通过网络互连设备——路由器将分布在世界各地的数以万计的广域网、域域网和局域网互联起来,而形成的全球性的大型互联网络。
18、用户计算机接入Internet两种方式:1)通过电话网2)通过局域网;
19、用户的局域网使用路由器,通过数据通信网与ISP(互联网供应商)相连接,再通过ISP的连接通道接入Internet。
20、异步传输模式ATM:
(1)是B-ISDN选择的数据传输模式;
(2)数据传输方式,兼备了线路交换方式的实时性好,及分组交换方式的灵活性高;
(3)能很好地满足网络应用及实时通信所要求的网络传输的高速率和低延迟。
21、网络接入方式——ADSL(Asymmetrical Digital Subscriber Loop)非对称数字用户线路:用一对电话铜线提供上、下行非对称传输速率的一种高速宽带技术。
22、TCP/IP参考模型的层次——应用层、传输层、网络层、物理链路层。
(1)应用层协议:FTP(文件传输协议)、SMTP(电子邮件协议)、HTTP(超文 本传输协议)、DNS(域名服务)、Telnet(网络终端服务)、 RIP(路由信息协议)、NFS(网络文件协议)
(2)传输层协议:TCP、UDP(用户数据报协议)
(3)网络层协议:IP、ICMP、ARP、RARP
23、以太网协议属于网络底层协议,通常在OSI模型的物理层和数据连接路层操作,它是总线型协议中最常见的,数据速率为10Mbps/s(兆比特/秒),是当今现有的局域网采用的最通用的通信协议标准。
24、在IPv4中,一个IP地址的长度是32位的二进制数。
信息安全
25、信息认证的方法:数字签名、身份认证和消息认证;密钥管理属于加密处理;
26、密钥管理最关键和最难解决的问题是解决密钥分配和存储问题。
27、网络安全技术的研究主要涉及安全攻击、安全机制和安全服务三方面内容。
28、Internet中,对网络攻击主要可以分为两种基本类型:服务攻击和非服务攻击。服务攻击是指对网络提供某种服务的服务器发起攻击。
29、作为一个安全的网络系统提供的基本安全服务功能,认证服务可用于解决网络中信息的源节点用户与目的节点用户身份的真实性。
30、隔离 操作系统安全
(1)物理隔离--使不同安全要求的进程使用不同的物理实体;
(2)逻辑隔离--限制程序的存取,使不同操作系统不能存取允许范围以外的实
体;
(3)时间隔离--使不同的进程在不同的时间运行;
(4)密码隔离--进程以其他进程不了解的方式隔离数据和计算。
一、存储结构
1、存储结构是指计算机语言如何表示结点之间的关系。常用映射方法:顺序表、链表、索引和散列表。在链式存储结构中,用指针来体现数据元素之间逻辑上的联系。
2、链式存储结构中有单链表和双向链表。单链表中每个节点只设置一个指针域,用于指向其后续结点,而双链表在每个节点中设置两个指针域,分别指向其前驱结点和后续结点。线性表为空时,头结点的指针域为空。
3、线性表顺序存储方式:可随机存储表中任一结点,查找第i个节点的存储地址,可用一个简单、直观的公式直接计算出来,执行时间与i的值无关。
链式存储方式:要查找某个位置的结点,必须从头开始逐个访问每个结点,直到找到该位置。
不论是哪种存储方式,要查找某个人特定关键码值的结点则必须采用遍历整个线性表的方法直到找到该节点。
顺序存储结构满足随机访问的条件。
4、散列表:(1)基本思想是--有节点的关键码值决定结点的存储地址;(2)好的散列函数的标准是能将关键码值均匀地分布在整个地址空间中;(3)除余法是散列函数的构造方法;(4)散列表的平均检索长度随负载因子的增大而增大。
5、散列函数h(K)=k mod 13意义:一个数K除以13的余数就是结果。
6、散列法解决碰撞的方法:拉链法、开地址法。
二、排序
1、基础
(1)直接选择排序,一遍又一遍的查,一个个换,不论原数组初始状态,每一次都要遍历一遍剩余的数来选取最大(最小)值;
(2)起泡排序和快速排序(空间复杂度较高)都是交换排序;
(3)归并排序要求待排序文件已经部分排序。
(4)在待排序文件已基本有序的前提下,起泡排序效率最高。
2、快速排序算法主要应用了递归算法。对n个记录的文件进行快速排序,平均执行时间为O(nlog2n),在最坏的情况下,其效率降低为O(n2)。
3、快速排序法是对冒泡排序的改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两个部分,其中一部分的所有数据都要比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以
递归进行,从而使整个数据变成有序序列。
4、归并排序是一种稳定、高效的排序方法。归并排序算法一般是顺序存储结构实现的。使用顺序存储结构实现归并排序需要空间复杂度为O(n)的辅助存储空间。
5、Shell排序法:将数据分成n(n为初始增量)个组,所有距离为n的倍数的元素分在一组中,各组中用插入法排序。
杂乱知识点
1、索引的建立中,列名后可设置顺序(ASC为升序、DESC为降序,默认为升序)。而在Index前的修饰Unique指此索引的每一个索引值只对应唯一的数据,Cluster表示要建立的索引为聚簇索引。
2、笛卡儿积是指包含两个集合中任意取出两个元素构成的组合的集合,对两集合无特殊要求。
3、半连接运作是指两个关系R、S的自然连接在关系R或S的属性集上的投影。R和S的半连接(R?<S)不等于S和R的半连接。不符合交换律。
4、外连接是在R和S进行自然连接时,把原该舍弃的元组也保留在新关系中,同时在这些元组的新增属性上填NULL。
5、连接条件中的运算符为算数比较运算符,当取“=”时,为等值连接。若等值连接中连接属性为相同属性(或属性组),且在结果关系中去掉重复组,则此等值连接为自然连接。
6、基于半连接操作的分布式查询的基本思想是:将关系从一个站点传输到另一个站点之前减少该关系中连接操作的数量。
7、服务器程序是一类辅助性的程序,它提供各种运行所需要的服务。如程序的嵌入、连接、编辑及调试用的装入程序、连接程序、编辑程序及调试程序以及故障诊断程序、纠错程序。
8、数据元素是数据的基本单位。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项组成。
9、一个算法的评价主要从时间复杂度和空间复杂度来考虑。
10、记录
(1)记录的成组:把若干个逻辑记录并成一组存入一块的记录;
(2)从一组中把一个逻辑记录分离出来的工作成为记录的分解;
(3)信息交换以块为单位,用户处理信息要以逻辑记录为单位,所以当逻辑记录成组后,要处理记录时必须执行分解操作,记录的分解也要使用主存储器的缓冲区。
(4)成组与分解操作提高存储空间的使用率,减少存储设备的启动次数。
11、数据冗余会导致:(1)数据不一致(2)增大表所占的空间,造成不必要的磁盘浪费(3)查询效率低。
12、实际安全产品的安全等级分为四级:D、C(C1、C2)、B(B1、B2、B3)、A。D是最低的安全级别,系统的访问控制没有限制,无需登记系统就可以访问数据;C2级是实际安全产品的最低档次;B1级别的产品才被认为是真正意义上的安全产品。A级别称为验证设计级,是目前最高的安全级别。
13、Armstrong公理系统:
自反率(Y?X,X→Y)、
增广率(X?Y,且Z?U则XZ?YZ)、
传递率(X?Y且Y?Z,则X?Z);
推理:合并规则(若X→Y,X→Z则X→YZ在R上成立)、
分解规则(若X→Y且Z?Y,则X→Z在R上成立);
伪传递规则(若X→Y,Y→Z,则WX→Z在R上成立)。
14、多值依赖的性质
(1)对称性:若X→→Y,则X→→Z(Z=U-X-Y);
(2)若X→Y则X→→Y;(函数依赖是多值依赖的特殊情况)
(3)有效性和属性集范围有关:XY?W?U,当X→→Y在R(U)上成立时,则在R(W)上成立,反之不成立。
(4)函数依赖X→Y在R(U)上成立,则对于任何Y’属于Y,X→Y’成立;
(5)若X→→Y在R(U)上成立,且Y'?Y,不能断言X→→Y’;
(6)若X→→Y且Z=U-X-Y=?,则X→→Y为平凡的多值依赖。
15、包含在任何一个候选码的属性叫做主属性;
不包含在任何候选码中的属性叫做非主属性。
16、广义表(又称列表)是线性表的推广,由0个或多个单元素或子表所组成的有限序列。
17、广义表的特征:
(1)广义表元素可以是子表,而子表的元素还可以为子表;
(2)广义表可被其他广义表所共享(引用);
(3)可以为递归的表,即广义表也可是为本身的一个子表。
第二篇:计算机三级数据库知识点总结——操作系统
第三章——操作系统
一、操作系统
1、操作系统具有并发性、共享性、随机性三个特征。前两个为基本特性。
2、操作系统管理的资源有:程序、CPU、内存。不包括中断。
3、系统中的资源按照使用性质分为两类:永久性资源、临时性资源
(1)永久性资源:系统中可供进程重复使用、长期存在的资源。如硬件资源、软件资源、数据文件;
(2)临时性资源:有某个进程产生、只为另一个进程使用一次或经过短暂时间后就不再使用的资源。如I/O和时钟中断、同步信号、消息等。
4、操作系统向用户提供两类接口:
(1)程序级接口:由一组系统调用命令组成。用户程序借助于系统调用命令来向操作系统提出各种资源要求和服务请求。
(2)作业级接口(操作级接口):由一组操作命令组成,是用户以交互方式请求操作系统服务的手段。
5、分时操作系统追求的目标是高速响应。采用时间片轮转方式处理用户服务请求。
6、在批处理系统兼分时系统的系统中,往往由分时系统控制的作业称为前台作业,而由批处理系统控制的作业成为后台作业。
7、实时操作系统(RTOS)是指计算机能够及时响应外部事件的请求,在规定的时间内严格完成对该事件的处理,并控制所有实时设备和实时任务协调一致的工作的操作系统。其主要特点是资源的分配和调度首先考虑实时性然后才是效率。实时操作系统有较强的容错能力。
二、OS的硬件环境——CPU、中断、存储、I/O、时钟
(一)CPU的指令
1.指令系统——数据传输类指令、算术逻辑类指令、判定控制类指令;
2.精简指令系统计算机RISC(Reduced Instruction System Computer);
3.特权指令是指只允许操作系统使用,而不允许一般用户使用的指令。用户只能使用非特权指令。若用户要使用特权指令时需将CPU状态切换到管态,一般情况下用户都处于目态(较低特权级别)。要从目态到管态转换的唯一途径就是通过中断。
4.常见的特权指令:启动I/O设备指令(测试I/O工作状态、控制I/O动作指令、修改程序状态字、中断屏蔽、设置时钟。
5.Intel公司的x86系列处理器提供四个特权级别(R0,R1,R2,R3)。较大的数字表示较低的特权。R0运行那些最关键的代码,比如操作系统的内核代码。
6.访管指令属于非特权指令,是一条可以在目态下执行的指令,用户程序中凡
是要调用操作系统功能时就安排一条访管指令。当处理器执行到访管指令是就产生一个中断事件(自愿中断),暂停用户程序的执行,而让操作系统来为用户服务。
(二)中断
1、强迫性中断:输入输出中断、硬件故障中断、时钟中断、控制台中断、程序性中断(缺页、缺段、溢出等)。
2、发生中断时被打断程序的暂停点称为断点,引起中断的事件成为中断源。
3、自愿性中断:访管中断、编程中设备的中断。
4、缺页中断就是要访问的页不在主存,需要操作系统将其调入主存后再进行访问。
5、影响缺页中断的原因有:(1)分配给作业的主存块数,每个作业只要能得到一块贮存空间就可以开始执行,可增加同时执行的作业数,设作业有n页,当能分到n/2块主存空间时才把它装入主存,则可使系统获得最高效率;(2)页面的大小,页面大则缺页中断率低,反之缺页率高;(3)程序编制方法(4)页面调度方法。
6、中断响应:CPU每执行完一条指令,便去扫描中断寄存器,查询有无中断请求,若有,则通过交换中断向量,进入中断处理程序。
(三)I/O控制方式体系
1、DMA指Direct Memory Access(存储器直接访问)。是一种高速的数据传输操作,允许在外部设备和存储器之间直接读写数据,既不通过CPU,也不需要CPU的干涉。整个数据传输操作在一个称为“DMA控制器”的控制下进行。CPU除了在数据传输开始和结束时做一点处理,在传输过程中CPU可以进行其他的工作。
三、进程管理
1、进程的转换:
(1)进程等待某个资源会导致该进程被挂起,从运行态转换为等待状态;
(2)进程等待的资源变为可用,进程会从等待状态转换为就绪状态;
(3)进程时间片用完,进程会从运行态转换为就绪状态。
2、每个进程都有自己的工作集,工作集大小可以调整。工作集模型解决了系统颠簸的问题。工作集最主要的属性是其大小,太小会使进程经常缺页,缺页率上升,工作集大些,可降低缺页率。
3、从静态的观点看,操作系统的进程是由程序段、数据和进程控制块(PCB)3部分组成。
4、系统中有N个进程,则某个进程等待队列中最多可有N个进程。
5、进程的阻塞原语BLOCK主要完成进程从执行状态到阻塞的转换。
6、进程间通信机制
(1)高级通信机制分为三类:共享内存、消息机制和管道通信。(用于解决进程之间的大量信息的传送问题)
(2)低级通信机制:P操作和V操作,解决少量信息的交换。
(3)消息机制包括:消息缓冲和选择通道。
7、线程是进程中的一个实体,是被系统独立调度和分派的基本单位,线程自己不拥有系统资源,只拥有一点在运行中必不可少的资源,但它可与同属一个进程的其他线程分享进程所拥有的全部资源。一个进程可以创建和撤销另一个进程,同一进程中多个线程之间可以并发执行。
8、一个标准的线程由线程ID,当前指针(PC),寄存器集合和堆栈组成。
9、在时间片轮转算法中,每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。如果时间片结束时进程还在运行,则CPU将被剥夺并被分配给另一个进程,时间片设的太短会导致过多的进程切换,降低了CPU效率。
10、形成死锁的四个必要条件:互斥使用资源、占用并等待资源、不可抢夺资源和循环等待资源。
11、一组进程处于死锁状态是指:该组中每一个进程都在等待被另一个进程所占有的、且不能抢占的资源,而不可继续运行。但是系统中不属于该组的进程仍然可以运行。
12、银行家算法是最著名的避免死锁的算法。
13、在单CPU系统中,最多只有一个进程处于运行态。若同时存在24个并发进程,有可能都具备运行条件,因此处于就绪队列中的进程最多有23个。 14、
四、存储管理
1、存储管理解决的问题:内存的分配和回收、内存空间的共享、存储保护、地址映射、内存扩充。
2、存储管理地址映射中,内存地址是按照物理地址进行编址的。用户程序中使用的是逻辑地址,且从0开始编址;动态地址映射是在程序执行过程中完成的,而且需要硬件支持。
3、数据存储组织:
(1)一个数据库被映射为多个不同的文件,它们由操作系统来维护;
(2)数据库映射的文件存储于磁盘上的磁盘块中;
(3)分槽的页结构删除一条记录会引起记录的移动以保持上面的特性,由于块大小限制,代价不会很高。
4、分槽的页结构组织变长记录,块头记录中包括:块头中记录条目的个数、块中空闲空间的末尾地址、一个包含每条记录位置和大小的条目组成的数组。
5、UNIX系统中,把输入/输出设备看成特殊文件。
6、在页式存储管理中,为进行地址转换工作,系统提供一对硬件寄存器——页表始址寄存器和页表长度寄存器。
7、在存储管理中,为实现地址映射,硬件提供两个寄存器,一个是基址寄存器,另一个是限长寄存器。
8、利用高速缓存存储器存放页表的一部分,把存放在高速存储器中的部分页表称为“快表”。快表中登记了一部分页号与主存块号的对应关系。根据程序执行局部性的特点,在一段时间内总是经常访问某些页,若登记入快表中,则可快速查找并提高执行速度。
9、虚拟页式存储管理系统中,选择页面淘汰算法时应尽量减少或避免颠簸现象的发生。
10、在虚拟页式存储管理中,页表包含逻辑页面号、物理页面号、驻留位、保护位、修改位和访问位。其中驻留位指示该页在内存还是外存。
11、虚拟存储的容量受到计算机地址位数因素的限制。
12、虚拟存储技术的引入前提是程序局部性原理。
程序的局部性:在一段时间内,程序的执行仅限于某个部分,相应的,它所访问的存储空间也局限在某个区域。存储管理系统将进程中不经常被访问的程序段和数据放入外存中,待需要访问时再将他们调入内存。
五、文件管理
1、纪录式文件的记录可以是定长的,也可以是变长的。记录可以只有记录键,也可以有记录键和其他属性。
2、文件可分为流式文件(即无结构文件)和有结构文件,源程序和目标代码等文件属于流式文件。
3、为了提高文件的检索速度,文件系统向用户提供了一个当前正在使用的目录,成为当前目录。
4、可提高语言文件系统的性能的技术:当前目录、文件目录的改进、块高速缓存、磁盘空间的合理分配、磁盘的驱动调度、信息的优化分布。
5、文件控制块(FCB)是操作系统为管理文件而设置的数据结构,存放了为管理文件所需的所有有关信息。包括文件号、文件建立日期、口令等。
6、通道分类:
(1)字节多路通道:适用于低速或中速的I/O设备;
(2)选择通道:适用于连接磁盘、磁带等高速设备,在一段时间内只能为一台设备服务;
(3)成组多路设备:实质是对通道程序采用了多道程序设计技术,适用于通道
连接的设备并可以并行工作,支持通道程序并发操行。
7、文件共享是指一个文件可允许多个用户共同使用。
8、文件的物理结构之一:
索引结构——在文件系统中,将逻辑上连续的文件分散存放在若干不相连的物理块中,系统为每个文件建立一张表,记录文件信息所在的逻辑块号和与之对应的物理块号,这种文件的物理结构就称为索引结构。
HASH结构与之区别在于:没有建立一张索引表。
六、设备管理
(一)虚拟设备技术(SPOOLing技术)
1、SPOOLing技术提高了共享设备利用率,是一类典型的虚拟设备技术。
2、SPOOLing,即外围设备联机并行操作,将独占设备变成逻辑上的共享设备,解决了独占设备效率低的问题,需要磁盘空间作为缓冲。可用于打印机的管理。??
8、在虚拟系统中,不能实现但可以作为衡量其他页面淘汰算法标准的页面淘汰算法是——最佳淘汰算法(OPT)。
9、最佳淘汰算法:淘汰以后不再需要的,或者在最长的时间以后才会用到的页面。
10、页面淘汰--LRU算法:淘汰最后一次访问时据当前时间间隔时间最长的页面。
11、需要N个物理块进行存放,则平均访盘为(1+N)/2 +1。
12、从资源分配的角度可将设备分类为独占设备、共享设备和虚拟设备。
13、引入多道程序设计的目的是充分利用cpu,提高cpu利用率。
(二)磁盘调度
1、磁盘驱动调度中移臂调度只能减少磁头寻道时间。
2、扫描算法可以提高寻道优化的时间。
3、最短寻道时间优先(SSTF)算法选择这样的进程:要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。此法可能会使I/O请求无限等待。