这是为了用来区分队空与队满的情况。如果不空一个位置，则判断队空和队满的条件是一样的。
二叉排序树又称二叉查找树，它或者是一颗空树，或者满足一下性质的二叉树：
①若左子树不空，则左子树上所有结点的值均小于根节点的值；
②若右子树不空，则右子树上所有结点的值均大于根节点的值；
③左右子树也分别是二叉排序树。
原理步骤：
若子树为空，查找不成功。
定义：
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。
构造方法：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：
(1)将w1、w2、…，wn看成是有n棵树的森林(每棵树仅有一个结点)；
(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
特点：
①权值越大的结点，距离根节点越近；
②树中没有度为一的结点。
应用：
哈夫曼编码，减少编码的长度。哈夫曼编码就是长度最短的前缀编码。
散列（哈希）表：
冲突：指的是多个关键字映射同一个地址的情况。
解决办法：
（1）开放定址法
①线性探查法（产生堆积问题）；
②平方探查法（不能探查到哈希表上所有的地址，但至少能探查到一半的地址）
（2）链地址法
把所有的同义词用单链表连接起来。
补充（常见的哈希函数构造方法）
直接定址法，数字分析法，平方取中法，除留余数法。
深度优先搜索遍历
基本思想：首先访问出发点V，并将其标记为已访问；然后选取与V邻接的未被访问的邻接顶点W，访问W；再选取与W邻接的未被访问的顶点访问，以此类推。当一个顶点所有的邻接顶点都被访问过时，则依次退回最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些顶点中去一个顶点进行上述的过程，直至图中所有顶点都被访问过为止。
广度优先搜索遍历
基本思想：首先访问起始顶点V，然后选取与V邻接的全部顶点w1，w2，….，wn进行访问，再一次访问与w1，w2，…
，wn邻接的全部顶点（不包括已访问过的顶点），以此类推，直至所有顶点都被访问过为止。
该算法可以求得某一顶点到其余各顶点的最短路径。
算法思想：设有两个顶点集合S和T，其中集合S中存放的是图中已找到最短路径的顶点，集合T中存放的是图中的剩余顶点。
初始状态时，集合S中只包含源点V0，然后不断从集合T中选取到顶点V0路径最短的顶点Vu并加入集合S中。集合S每加入一个新的顶点Vu，都要修改V0到集合T中各个顶点的最短路径的长度值。不断重复这个过程，直至集合T中的顶点全部并入到S中为止。
O(n)链表是顺序存储，故（1+n）/2。
①邻接矩阵：是图的顺序存储结构，用两个数组分别存储数据元素（顶点）信息和数据元素之间的关系（边/弧）的信息。图的邻接矩阵表示是唯一的，无向图的邻接矩阵是对称的。
②邻接表：是图的链式存储结构，由单链表的表头形成的顶点表和单链表其余结点所形成的边表两部分组成。
③十字链表：有向图的另一种链式存储结构。
④邻接多重表：无向图的链式存储结构。
不一定是不唯一。我们可以取图中任一顶点进行深度遍历。
图：由结点的有穷集合V和边的集合E组成。
类别：有向图和无向图。
顶点的度：出度和入度。
有向完全图和无向完全图：若有向图有n个顶点，则最多有n(n-1)条边，则称为有向完全图；
若无向图有n个顶点，则最多有n(n-1)/2条边，则称为无向完全图。
路径：相邻顶点序偶所构成的序列。
简单路径：序列中的顶点和路径不重复出现的路径。
回路：路径中第一个顶点和最后一个顶点相同的路径。
连通：无向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中任意两个顶点之间都连通，则称改图为连通图。
有向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中每一对顶点Vi和Vj，从Vi到Vj和Vj到Vi都有路径，则称改图为强连通图。
一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图联通的最少的边。如果在最小生成树中添加一条边，必定成一个环。
①普里姆算法
②克鲁斯卡尔算法
N个结点的最小生成树有几个结点，几条边：n个结点，n-1条边。
平衡二叉树又称AVL树，是一种特殊的二叉排序树，其左右子树都是平衡二叉树，且左右子树的高度差的绝对值不超过1.
平衡因子：左子树高度减去右子树高度的差。
平衡调整：先找到失去平衡的最小子树，即以距离插入结点最近，且平衡因子绝对值大于1的结点最为根节点的子树，分为LL,LR,RL,RR四中调节方式。
①顺序存储结构：用一个数组来存储一颗二叉树，二叉树中的结点值按照编号依次存入一个一维数组中。适用于完全二叉树，若用于一般的二叉树则会浪费大量存储空间。
②链式存储结构：二叉树中的每一个结点用一个链结点来存放。
①B+树所有有效数据全在叶子节点，而B-树所有节点分散在树中，B-树中的关键字不重复。
②B+树种有几个关键字就有几个子树，B-树中具有n个关键字的节点含有(n+1)棵子树。
③B+树有两个指针，根指针和只想最小节点的指针，叶子节点连接成一个不定长的线性链表
④B+树中，每个节点（除根节点外）中的关键字个数n的取值范围是m/2<=n<=m，根节点n的取值
⑤范围是2<=n<=m。B-树中，每个节点（除根节点外的所有最底层非叶子节点）中的关键字取值范围是
⑥m/2-1<=n<=m-1，根节点n的取值范围是1<=n<[m-1]。
⑦B+树中的所有非叶子节点仅仅起到索引的作用，节点中的每个索引项只包含对应子树的最大关键字和
指向该子树的指针，不含有该关键字对应记录的存储地址。而在B-树中，每个关键字对应记录的存储
地址。
又称二分查找，基本思路：
在当前的查找区间[low…high]中，首先确定mid=(low+high)/2，然后拿关键字与mid比较，若相等则查找成功，返回该位置，否则确定新的查找区间，mid>K，[low…mid-1]
mid 直至查找自区间长度小于1时查找结束。 适用范围：顺序结构存储并按照关键字大小有序排列。 若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。 完全二叉树特点： 堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足： 任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。若父亲大孩子小，则为大顶堆，若父亲肖孩子大，则为小顶堆。 作用：应用于堆排序。 如何实现：把数组弄成一个环，让rear和front指针沿着环走，这样就可以产生循环队列。 好处：循环队列是顺序队列的改进，在顺序队列中，在元素进队的时候，rear要向后移动，元素出队的时候，front也要向后移动，这样经过一系列的出队和入队操作之后，两个指针最后会达到数组的末端，此时虽然队中已经没有元素了，但是还是不能让元素入队，即出现了“假溢出”的现象。循环队列就能避免出现这个现象。 （森林，不能说树）（不唯一，因为邻接表可能不唯一） 2的n次方减一（2n-1） 递增有序序列 有向无环图 队列是一种操作受限的线性表，只允许队尾入队，在队头进行出队。最大的特点是先进先出。 节点循环，DFS或者BFS。 各类排序的算法详见书本。（需要说出每个算法的基本思想） ①进程是动态的，程序是静止的。进程是程序的执行，程序是有序代码的集合。 ②进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可以长久保存。 ③进程和程序的组成不同：进程包括程序，数据和进程控制块。 ⑤进程可以创建其他进程，但是程序不能形成新的程序。 ①调度：线程是独立调度的基本单位，进程是资源拥有的基本单位。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行线程切换，将会引起进程切换。 ②拥有资源：进程是拥有资源的基本单位，而线程不拥有系统资源（除了少量资源，比如栈，程序计数器，寄存器），不过线程可以访问其隶属进程的系统资源。 ③并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且同一个进程内的多个线程之间也可以并发执行，能提高系统的吞吐量，系统的并发性也更好。 ④系统开销：在创建进程和撤销进程时，系统都要为之分配或回收资源，所以操作系统为进程付出的系统开销远大于创建线程或撤销线程的开销。 ⑤同步和通信：多线程之间的同步和通信容易实现。 微内核操作系统能有效地支持多处理机运行，非常适用于分布式系统环境。 什么是微内核操作系统到现在没有一致公认的定义，但是可以从四个方面对微内核操作系统进行描述： ①足够小的内核：在微内核操作系统中，内核是指精心设计的，能实现现代OS最基本核心功能的部分，并非是一个完整的OS，而只是OS中最基本的部分。 ②基于C/S模式：将操作系统中最基本的部分放入内核中，而把操作系统的绝大部分功能都放于微内核外面的一组服务器中实现。 ③应用“极致与策略分离”原理：在传统OS中，讲极致放在OS的内核的较低层，把策略放在内核的较高层中。而在微内核OS中，通常把机制放在OS的微内核中，这样才有可能将内核做得很小。 ④采用面向对象技术。 ①进程（线程）管理 ②低级存储器管理 ③中断和陷入处理 优点： ①提高了系统的可扩展性 ②增强系统的可靠性 ③可移植性 ④提供了对分布式系统的支持 ⑤融入了面向对象技术 ①中断方式是在数据缓冲寄存器满之后发出中断，要求CPU进行，而DMA方式则是在所要求传送的数据块全部传送结束时要求CPU进行中断处理。这就大大减少了CPU进行中断处理的次数。 ②中断方式的数据传送是在中断处理时由CPU控制完成的，而DMA方式则是在DMA控制器的控制下，不经过CPU控制完成的。这就排除了CPU因并行设备过多而来不及处理以及因速度不匹配而造成数据丢失等现象。 软中断： 1、编程异常通常叫做软中断 2、软中断是通讯进程之间用来模拟硬中断的一种信号通讯方式。 3、中断源发中断请求或软中断信号后,CPU或接收进程在适当的时机自动进行中断处理或完成软中断信号 对应的功能 4、软中断是软件实现的中断,也就是程序运行时其他程序对它的中断;而硬中断是硬件实现的中断,是程序运 行时设备对它的中断。 硬中断： 1、硬中断是由外部事件引起的因此具有随机性和突发性；软中断是执行中断指令产生的，无外部施加中断 请求信号，因此中断的发生不是随机的而是由程序安排好的。 2、硬中断的中断响应周期，CPU需要发中断回合信号（NMI不需要），软中断的中断响应周期，CPU不 需发中断回合信号。 3、硬中断的中断号是由中断控制器提供的（NMI硬中断中断号系统指定为02H）；软中断的中断号由指 令直接给出，无需使用中断控制器。 4、硬中断是可屏蔽的（NMI硬中断不可屏蔽），软中断不可屏蔽。 区别： 2、软中断是由程序调用发生的,而硬中断是由外设引发的 ①最佳置换算法（OPT）：在预知一个进程的页面号引用串的情况下，每次都淘汰以后不再使用的货以后最迟再被使用的页面。该算法不能实现，只能作为一个标准来衡量其他置换算法的优劣。 ③最近最少使用算法（LRU）：选择最近最少未被使用的页面淘汰，其思想是用以前的页面引用情况来预测将来会出现的页面引用情况。利用了局部性原理。 ④时钟置换算法（CLOCK）：是LRU和FIFO的折中，具体方法略。 ⑤工作集算法 ⑥工作集时钟算法 ⑦第二次机会算法 ⑧最近未使用（NRU） 信号量是一个确定的二元组（s，q），其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目；当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。 信号量分类： ①整型信号量：所谓整型信号量就是一个用于表示资源个数的整型量 ②记录型信号量（资源信号量）：就是用一个结构体实现，里面包含了表示资源个数的整型量和一个等待队列。 信号量的应用： ①实现进程同步 ②实现进程互斥 信号量的值除了初值外，仅能由这PV原语加以改变。P、V操作以原语形式实现，保证了对信号量进行操作过程中不会被打断或阻塞。P操作相当于申请资源，V操作相当于释放资源。P操作和V操作必定成对出现，但未必在同一个进程中。 操作系统理论研究者有时把操作系统分成四大部分： 栈：运算器出栈压栈 队列：进程管理 树：目录管理 表格：优先级的设置 系统调用提供了用户程序和操作系统之间的接口，应用程序通过系统调用实现其余OS的通信，并取得它的服务。系统调用不仅可供所有的应用程序使用，而且也可供OS本身的其它部分，如命令处理程序。 系统调用的处理步骤（三步）： 首先，将处理机状态由用户态转为系统态；然后由硬件和内核程序进行系统调用的一般性处理，即首先保护被中断进程的CPU环境，将处理机状态字PSW、程序计数器PC、系统调用号、用户栈指针以及通用寄存器内容等压入堆栈；再然后将用户定义的参数传送到指定的地址保存起来。 其次，分析系统调用类型，转入相应的系统调用处理子程序。（通过查找系统调用入口表，找到相应处理子程序的入口地址转而去执行它。） 最后，在系统调用处理子程序执行完后，应恢复被中断的货设置新进程的CPU现场，然后返回被中断进程或新进程，继续往下执行。 基于局部性原理，应用程序在运行之前，仅将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂时留在盘上。程序运行时，如果它要访问的页已调入内存，便可继续执行下去；但如果程序要访问的页或段尚未调入内存（即缺页），此时程序应利用请求调入功能将它们调入内存，以使程序能继续执行下去。如果此时内存已满，无法装入新的页或段，则需要利用页面置换功能，将内存中暂不使用的页面或段调至盘上，腾出空间用于页面调入内存，是程序继续执行下去。这样，就实现了大的用户程序能在较小的内存空间里运行，也可以在内存中同时装入更多的进程使它们并发运行。从用户角度出发，该系统的内存容量比实际内存容量大很多，故成这样的存储器为虚拟存储器。 页面置换算法 存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器，故应具有以下功能： ①内存的分配和回收：实施内存的分配，回收系统或用户释放的内存空间。 ②地址变换：提供地址变换功能，将逻辑地址转换成物理地址。 ③扩充内存：借助于虚拟存储技术活其他自动覆盖技术，为用户提供比内存空间大的地址空间，从逻辑上扩充内存。 ④存储保护：保证进入内存的各道作业都在自己的存储空间内运行，互不干扰。 TLB的作用是在处理器访问内存数据的时候做地址转换。TLB的全称是TranslationLookasideBuffer，可以翻译做旁路缓冲，是一个具有并行查询能力的特殊高速缓冲寄存器。TLB中存放了一些页表文件，文件中记录了虚拟地址和物理地址的映射关系。当应用程序访问一个虚拟地址的时候，会从TLB中查询出对应的物理地址，然后访问物理地址。TLB通常是一个分层结构，使用与Cache类似的原理。处理器使用一定的算法把最常用的页表放在最先访问的层次。 补充：应用程序从用户编写的源文件到内内存中执行的进程大致分为三个阶段，经过编译程序将源代码便以为若干个目标模块，在通过链接程序将编译好的目标模块以及所需的库函数链接到一起，形成完整的装入模块，最后通过装入程序将这些装入模块装入内存并执行。（编译，链接，装入） 装入方式： ①绝对装入：在编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计。 ②可重定位装入：根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称静态重定位。当操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址。 ③动态运行装入：允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现要依靠硬件地址变换机构。 ①静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开。 ②装入时动态链接：将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式。 ③运行时动态链接：知道程序运行过程中需要一些模块时，才对这些模块进行链接。 覆盖技术：把一个大的程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位，把程序执行时并不要求同时装入内存的覆盖组成一组，成为覆盖段，这个覆盖段分配到同一个存储区域，这个存储区域成为覆盖区，它与覆盖段一一对应。覆盖段的大小由覆盖段中最大的覆盖来确定。（为了解决内存容量太小的问题，打破了必须将一个程序全部信息装入内存后才能运行的限制） 交换技术：把暂时不用的某个程序及数据部分从内存移到外存中去，以便腾出必要的内存空间；或者把指定的程序或数据从外存读到相应的内存中，并将控制权交给他，让其在系统上运行的一种内存扩充技术。处理器的中级调度就是采用交换技术。 ①与覆盖技术相比，交换技术不要求程序员给出的程序段之间的覆盖结构； ②交换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行； ③覆盖技术只能覆盖于覆盖程序段无关的程序段，交换进程由换出和换入两个过程组成。 ①单一连续分配（静态分配） ②固定分区分配（分区大小可以不等，但事先必须确定，运行时不能改变） ③动态分区分配 P131详细 ①首次适应算法FirstFit ②循环首次适应算法NextFit ③最佳适应算法BestFit ④最差适应算法WorstFit 即将存储器中所有已分配分区移动到主存的一端，使本来分散的多个小空闲区连成一个大的空闲区，这种通过移动把多个分散的小分区拼接成一个大分区的方法即为拼接技术。 所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何contextswitch（切换到另一个线程）。 内部碎片：分配给作业的存储空间中未被利用的部分。 外部碎片：系统中无法利用的小存储块，比如通过动态内存分配技术从空闲内存区上分配内存后剩下的那 部分内存块。 （1）界限寄存器 上下界寄存器方法 基址、限长寄存器方法 （2）存储保护键：给每个存储块分配一个单独的存储键，它相当于一把锁。 为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页面映射表。 页表由页表项组成，页表项有页号和块号组成，根据页表项就可以找到每个页号对于物理内存中物理块的块号。 段寄存器是因为对内存的分段管理而设置的。计算机需要对内存分段，以分配给不同的程序使用（类似于硬盘[分页。在描述内存分段时，需要有如下段的信息：1.段的大小；2.段的起始地址；3.段的管理属性（禁止写入/禁止/执行/系统专用等）。需要用8个字节（64位）存储这些信息，但段寄存器只有16位，因此段寄存器中只能存储段号（segmentselector，也译作“段选择符”），再由段号映射到存在内存中的GDT（global(segment)descriptortable，全局段号记录表），读取段的信息。 进程树是一个形象化的比喻，比如一个进程启动了一个程序，而启动的这个进程就是原来那个进程的子进程，依此形成的一种树形的结构，我们可以在进程管理器选择结束进程树，就可以结束其子进程和派生的子进程。 一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成的某 项任务，是要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完 成4个阶段。而进程是对已提交完毕的程序所执行过程的描述，是资源分配的基本单位。 其主要区别如下。 (1)作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后，系统将它放入外存中的作业等 待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程， 只要它被创建，总有相应的部分存在于内存中。 (2)一个作业可由多个进程组成，且必须至少由一个进程组成，反过来则不成立。 (3)作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。而进程的概念则 用在几乎所有的多道程序系统中进程是操作系统进行资源分配的单位。在Windows下,进程又被细化为线 程,也就是一个进程下有多个能独立运行的更小的单位。 ①先来先服务调度FCFS ②短作业优先调度SJF ③优先级调度Priority ⑤高响应比优先调度 ⑥多级队列调度 ⑦多级反馈队列调度 死锁：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。 ①系统资源不足 ②进程推进顺序不当 ②请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。 ③不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。 ④环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。 ①预防死锁：这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。 ②避免死锁：该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 ③检测死锁：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。 ④解除死锁：这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。 饥饿并不代表系统一点死锁，但至少有一个程序的执行被无限期地推迟。 差别： ①进入饥饿的进程可以只有一个，但是死锁必须大于等于两个； ②出于饥饿状态的进程可以是一个就绪进程，但是死锁状态的进程必定是阻塞进程。 1、段是信息的逻辑单位，分段的目的是为了更好地实现共享,根据用户的需要划分，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要，其对用户是透明的。 2、段的大小不固定，由它所完成的功能决定；页的大小固定（一般为4K），由系统决定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。 3、段向用户提供二维地址（段号+段内地址）；页向用户提供的是一维地址（页号） 4、段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。 主要思想是避免系统进入不安全状态，在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有，则先试行分配，并对分配后的新状态进行安全性检查。如果新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样就保证系统始终处于安全状态，从而避免死锁现象的发生。 文件控制块 集线器（多端口）中继器（两个端口）物理层 TCP是面向连接的协议，而UDP是无连接的协议。这意味着当一个客户端和一个服务器端通过TCP发送数据前，必须先建立连接，建立连接的过程也被称为TCP三次握手。 TCP提供交付保证，这意味着一个使用TCP协议发送的消息是保证交付给客户端的，如果消息在传输过程中丢失，那么它将重发。UDP是不可靠的，它不提供任何交付的保证，一个数据报包在运输过程中可能会丢失。 消息到达网络的另一端时可能是无序的，TCP协议将会为你排好序。UDP不提供任何有序性的保证。 TCP速度比较慢，而UDP速度比较快，因为TCP必须创建连接，以保证消息的可靠交付和有序性，他需要做比UDP多的事。这就是为什么UDP更适用于对速度比较敏感的应用。TCP适合传输大量数据，UDP适合传输少量数据。 TCP是重量级的协议，UDP协议则是轻量级的协议。一个TCP数据报的报头大小最少是20个字节，UDP数据报的报头固定是8个字节。TCP报头中包含序列号，ACK号，数据偏移量，保留，控制位，窗口，紧急指针，可选项，填充项，校验位，源端口和目的端口。而UDP报头只包含长度，源端口号，目的端口号，校验和。 TCP有流量控制和拥塞控制。UDP没有流量控制和拥塞控制。 TCP是字节流的协议，无边界记录。 UDP发送的每个数据报是记录型的数据报，所谓的记录型数据报就是接收进程可以识别接收到的数据报的记录边界。 传统交换机从网桥发展而来，属于OSI第二层即数据链路层设备。它根据MAC地址寻址，通过站表选择路由，站表的建立和维护由交换机自动进行。路由器属于OSI第三层即网络层设备，它根据IP地址进行寻址，通过路由表路由协议产生。交换机最大的好处是快速，由于交换机只须识别帧中MAC地址，直接根据MAC地址产生选择转发端口算法简单，便于ASIC实现，因此转发速度极高。但交换机的工作机制也带来一些问题。 1.回路：根据交换机地址学习和站表建立算法，交换机之间不允许存在回路。一旦存在回路，必须启动生成树算法，阻塞掉产生回路的端口。而路由器的路由协议没有这个问题，路由器之间可以有多条通路来平衡负载，提高可靠性。 3.广播控制：交换机只能缩小冲突域，而不能缩小广播域。整个交换式网络就是一个大的广播域，广播报文散到整个交换式网络。而路由器可以隔离广播域，广播报文不能通过路由器继续进行广播。 4.子网划分：交换机只能识别MAC地址。MAC地址是物理地址，而且采用平坦的地址结构，因此不能根据MAC地址来划分子网。而路由器识别IP地址，IP地址由网络管理员分配，是逻辑地址且IP地址具有层次结构，被划分成网络号和主机号，可以非常方便地用于划分子网，路由器的主要功能就是用于连接不同的网络。 5.保密问题：虽说交换机也可以根据帧的源MAC地址、目的MAC地址和其他帧中内容对帧实施过滤，但路由器根据报文的源IP地址、目的IP地址、TCP端口地址等内容对报文实施过滤，更加直观方便。 近几年，交换机为提高性能做了许多改进，其中最突出的改进是虚拟网络和三层交换。 交换机和路由器是性能和功能的矛盾体，交换机交换速度快，但控制功能弱，路由器控制性能强，但报文转发速度慢。解决这个矛盾的技术是三层交换，既有交换机线速转发报文能力，又有路由器良好的控制功能。 在第三层交换技术出现之前，几乎没有必要将路由功能器件和路由器区别开来，他们完全是相同的：提供路由功能正在路由器的工作，然而，现在第三层交换机完全能够执行传统路由器的大多数功能。作为网络互连的设备，第三层交换机具有以下特征： 1.转发基于第三层地址的业务流； 2.完全交换功能； 3.可以完成特殊服务，如报文过滤或认证； 4.执行或不执行路由处理。 第三层交换机与传统路由器相比有如下优点： 1.子网间传输带宽可任意分配：传统路由器每个接口连接一个子网，子网通过路由器进行传输的速率被接口的带宽所限制。而三层交换机则不同，它可以把多个端口定义成一个虚拟网，把多个端口组成的虚拟网作为虚拟网接口，该虚拟网内信息可通过组成虚拟网的端口送给三层交换机，由于端口数可任意指定，子网间传输带宽没有限制。 2.合理配置信息资源：由于访问子网内资源速率和访问全局网中资源速率没有区别，子网设置单独服务器的意义不大，通过在全局网中设置服务器群不仅节省费用，更可以合理配置信息资源。 3.降低成本：通常的网络设计用交换机构成子网，用路由器进行子网间互连。目前采用三层交换机进行网络设计，既可以进行任意虚拟子网划分，又可以通过交换机三层路由功能完成子网间通信，为此节省了价格昂贵的路由器。 4.交换机之间连接灵活：作为交换机，它们之间不允许存在回路，作为路由器，又可有多条通路来提高可靠性、平衡负载。三层交换机用生成树算法阻塞造成回路的端口，但进行路由选择时，依然把阻塞掉的通路作为可选路径参与路由选择。 物理层 数据链路层（PPP、HDLC、CSMA/CD） 网络层(IP、ARP（IP→MAC）/RARP(MAC→IP)、ICMP) 传输层（TCP、UDP） 会话层 表示层 应用层（telnet23、FTP20<数据>+21<控制>、SMTP161、DNS、SNMP、DHCP、HTTP80） TCP/IP是四层（网络接口层、网际层、运输层、应用层） 均等 IPV4是32位；IPV6是128位 单工：又称为单向通信，即只能有一个方向的通信而没有反方向的交互。例：无线电广播，电视广播 半双工：又称为双向交替通信，即通信的双方都可以发送信息，但不能双方同时发送（当然也就不能同时接受）。 全双工：又称为双向同时通信，即通信的双方可以同时发送和接受信息。 备注：单工只要一条信道，而半双工和全双工需都需要两条信道（每个方向各一条）。 假如当我们访问一个网站时，在知道网站IP的情况下，猫访问的是实际网卡地址，所以需要通过APD广播，通过工作站将此信息转达给互联网所有的猫(路由器) 当互联网的猫收到这个广播时会检查广播包里的IP是否与自己的IP一致，如果一致则返回给指定猫自己的网卡地址 那么此时双方会在自己内部形成一个链表将其记录下来，让IP与网卡地址形成映射，保存起来，便于下次通讯！ 那么下次在通讯时,当我们要访问一个IP时，猫会在自己的链表里检查这个IP是否已经拥有对应的MAC地址，如果有则在包头里将IP更改为MAC地址，这样在对方路由器无需获取IP地址，可以直接根据猫网卡中的MAC地址进行校验，当下次对方IP地址变更时，猫也会重复上面的步骤，通过APD广播重新获取IP地址对应的MAC地址！ 比如对方原本是193.2，后来更换成了193.1，这样发送时，猫在自己链表里找不到对应的MAC地址了，所以直接在发送一个APD广播，此时对方返回自己的MAC地址，猫发现原本链表里的193.2对应着这个MAC地址，所以就会直接将链表里193.2换成193.1！ 为什么猫使用MAC地址？ 答：这是以太网的一种协议，猫必须遵守，因为IP地址是随机变化的，有可能在你们通讯的过程中IP地址就发生了变化，所以为了确定正确性必须使用MAC地址！ 假如使用IP地址，你的IP地址是193.2，通讯过程中突然换成了193.1，而193.2分配给另外一个人了，那么另外一个人就会收到这个信息，但是MAC地址是唯一的，所以当地址变更时猫能在链表里查出来，并重新通过APD广播获取新的IP地址！ 上面说过猫会接受所有的包，但不是自己的不处理，其实我们可以在猫的设置页面将其猫的网卡设置成混杂模式即可接受所有包，但是接受了也不会被处理，因为包里的大多使用的是TCP/IP/UDP协议，这些协议需要socket套接字，不能保证机器下socket套接字是一致的，所以即便收到了，也不知道给哪个进程，所以直接就废弃了，但是我们可以编写一些抓包工具来抓到所有包，并分析！ 注意当我们如果想要访问国外网站时，是没有办法将包转发到国外线路上的，原因很简单： 运营商会修改边界转发工作站的工作模式，在解析你发送的包，如果包里包含敏感IP则使工作站不转发此包！ 因为访问国外服务器是有特定的路线的，这也是为什么部分国外网站可以访问，但是部分不让访问的原因！ 如果想访问国外的网站需要特定的服务器转接，注意，大陆是可以访问香港服务器，而香港服务器可以访问国外网站，所以我们可以在香港设立服务器，并且在访问香港的服务器进行转接！ 由于IP层是不可靠的，因此TCP需要采取措施使得传输层之间的通信变得可靠。停止等待协议就是保证可靠传输，以流量控制为目的的一个协议。其工作原理简单的说就是每发送一个分组就停止发送，等待对方的确认，在收到确认后再发送下一个分组，如果接受方不返回应答，则发送方必须一直等待。 ②如果接收方的确认分组丢失或者因其他原因，收到了重传分组，则：丢弃这个重传分组，并且向发送方发送确认。 DNS(域名系统)，将网址解析成IP地址。 DHCP（动态主机设置协议），是一个局域网的网络协议，使用UDP协议工作，主要有两个用途：给内部网络或网络服务供应商自动分配IP地址，给用户或者内部网络管理员作为对所有计算机作中央管理的手段。 FTP(文件传输协议)，FTP客户机可以给服务器发出命令来下载文件，上载文件，创建或改变服务器上的目录。 TELNET(远程终端协议)，能将用户的击键传到远程主机，同时也能将远程主机的输出通过TCP连接返回到用户屏幕。 数据链路层在物理层提供的服务的基础上向网络层提供服务，将原始的、有差错的物理线路改进成逻辑上无差错的数据链路，从而向网络层提供高质量的服务。功能主要有：①链路管理；②封装成帧；③透明传输；④差错检测 域内： ②OSPF（开放最短路由协议）。链路状态协议；基于IP；向自治域中所有路由器发送信息（防洪法），且发送的是链路状态表（LSA），触发更新；更新过程收敛快；根据代价选择最佳路由；支持多路径负载均衡。 域间： BGP（外部网关协议）是不同AS之间的路由器之间交换路由信息的协议。 载频之间保留了一定的保护间隔，使得相邻的频带不会相互重叠，这样传输过程中不同频率的各路信号便不会相互干扰，而且在接收端可以很容易的利用带通滤波器把各路信号再分割开来，恢复到多路复用前的分路情况。 局域网： 广域网： ①PPP（点对点协议），面向字节；不需要的功能：纠错（PPP协议只负责检错）、流量控制（由TCP负责）、序号（PPP协议是不可靠传输协议，故不需要对帧进行编号）、多点线路（PPP协议是点对点的通信方式）、半双工或单工（PPP只支持全双工链路）。 ②HDLC(高级数据链路控制协议)，面向比特；标记字段（01111110），地址字段（全1是广播，全0为无效）；控制字段（根据前两位取值可以将HDLC帧划分为三类（无奸细）：信息帧，监督帧，无编号帧），信息字段，帧检验序列FCS（CRC循环冗余码） 物理层：集线器，中继器（均不能隔离冲突域和广播域） 数据链路层：交换机（转发/学习机制、存储转发、隔离冲突域不能隔离广播域），网桥 网络层：路由器（隔离冲突域和广播域） 滑动窗口协议，是TCP使用的一种流量控制方法。该协议允许发送方在停止并等待确认前可以连续发送多个分组。由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输。 （3）PPP具有错误检测能力，但不具备纠错能力，所以ppp是不可靠传输协议； （4）无重传的机制，网络开销小，速度快。 个域网、局域网、城域网、广域网 见前题 网络安全由于不同的环境和应用而产生了不同的类型。主要有以下几种： 1、系统安全 运行系统安全即保证信息处理和传输系统的安全。它侧重于保证系统正常运行。避免因为系统的损坏而对系统存储、处理和传输的消息造成破坏和损失。避免由于电磁泄露，产生信息泄露，干扰他人或受他人干扰。 2、网络的安全 网络上系统信息的安全。包括用户口令鉴别，用户存取权限控制，数据存取权限、方式控制，安全审计，计算机病毒防治，数据加密等。 3、信息传播安全 网络上信息传播安全，即信息传播后果的安全，包括信息过滤等。它侧重于防止和控制由非法、有害的信息进行传播所产生的后果，避免公用网络上大云自由传输的信息失控。 4、信息内容安全 网络上信息内容的安全。它侧重于保护信息的保密性、真实性和完整性。避免攻击者利用系统的安全漏洞进行窃听、冒充、诈骗等有损于合法用户的行为。其本质是保护用户的利益和隐私 DHCP动态主机配置协议 传输层（TCP）、数据链路层(ARQ) 频分复用：给每个信号分配唯一的载波频率并通过单一媒体来传输多个独立信号的方法。 波分复用：就是光的频分复用。用一根光纤同时传输多个频率很接近的光载波信号。 见高分笔记P27 实际上CSMA/CD的工作流程与人际间通话非常相似，可以用以下7步来说明。 第一步：载波监听，想发送信息包的节点要确保没有其他节点在使用共享介质，所以该节点首先要监听信道上的动静（即先听后说）。 第二步：如果信道在一定时段内寂静无声（称为帧间缝隙IFG），则该节点就开始传输（无声则讲）。 第三步：如果信道一直很忙碌，就一直监视信道，直到出现最小的IFG时段时，该节点才开始发送它的数据（有空就说）。 第四步：冲突检测，如果两个节点或更多的节点都在监听和等待发送，然后在信道空时同时决定立即（几乎同时）开始发送数据，此时就发生碰撞。这一事件会导致冲突，并使双方信息包都受到损坏。以太网在传输过程中不断地监听信道，以检测碰撞冲突（边听边说）。 第五步：如果一个节点在传输期间检测出碰撞冲突，则立即停止该次传输，并向信道发出一个“拥挤”信号，以确保其他所有节点也发现该冲突，从而摒弃可能一直在接收的受损的信息包（冲突停止，即一次只能一人讲）。 第七步：返回到第一步。 实际上，冲突是以太网电缆传输距离限制的一个因素。例如，如果两个连接到同一总线的节点间距离超过2500米，数据传播将发生延迟，这种延迟将阻止CSMA/CD的冲突检测例程正确进行[2]。 传统地，路由器工作于OSI七层协议中的第三层，其主要任务是接收来自一个网络接口的数据包，根据其中所含的目的地址，决定转发到下一个目的地址。因此，路由器首先去掉数据包的二层头，取出目的IP地址，在转发路由表中查找它对应的下一跳地址，若找到，就在数据包的帧格前添加下一个MAC地址，同时IP数据包头的TTL（TimeToLive）域也减一，并重新计算校验和。当数据包被送到输出端口时，它需要按顺序等待，以便被传送到输出链路上。 网络中存在太多的数据包导致数据包被延迟或丢失，从而降低了整个网络的传输性能，这种情况叫做拥塞。如果产生网络拥塞，则网络的性能明显下降，整个网络的吞吐量将随着输入负荷的增大而下降。 拥塞控制：可分为闭环控制和开环控制。开环控制是在设计网络时事先将有关拥塞的因素考虑到，力求网络在工作时不产生拥塞。闭环拥塞是基于反馈环路的概念。 拥塞控制的4种算法： ①慢开始算法 ②拥塞避免算法 ③快重传算法 ④快恢复算法 电信网，广播电视网，互联网。 ①语义：对构成协议元素的含义的解释； ②语法：数据域控制信息的结构和格式； ③同步：规定事件的执行顺序。 与报文交换相比较，分组交换的优点和缺点如下。 ②简化了存储管理：分组的长度固定，相应的缓冲区大小也固定。 ③减少出错几率和重发数据量：因为分组较短，其出错几率必然减少，所以每次重发的数据量也就大大减少，这样不仅提高了可靠性，也减少了传输时延。 ①存在传输时延：尽管与报文交换相比的传输时延较短，但是与电路交换相比仍然存在存储转发时延，而且对其结点交换机的处理能力有更高的要求。 ②当分组交换采用数据报服务时，可能出现失序、丢失或重复分组，分组到达的目的地的结点时，要对分组按编号进行排序工作，工作量较大。 流量控制就是要控制发送方数据传输的速率，使接收方来得及接收。 数据链路层：相邻结点的流量控制， 传输层：端到端的流量控制，利用滑动窗口机制在TCP连接上实现流量控制。 原理： 二层交换技术是发展比较成熟，二层交换机属数据链路层设备，可以识别数据包中的MAC 地址信息，根据MAC地址进行转发，并将这些MAC地址与对应的端口记录在自己内部的 一个地址表中。 三层交换机就是具有部分路由器功能的交换机 三层交换技术就是二层交换技术＋三层转发技术。传统交换技术是在OSI网络标准模型第 二层——数据链路层进行操作的，而三层交换技术是在网络模型中的第三层实现了数据包的 高速转发，既可实现网络路由功能，又可根据不同网络状况做到最优网络性能。 频带之间会有足够长的隔离频带 ACK NAT（私网地址的部署） IPv6的地址长度为128位，是IPv4地址长度的4倍。于是IPv4点分十进制格式不再适用，采用十六进制表示。IPv6有3种表示方法。 一、冒分十六进制表示法格式为X:X:X:X:X:X:X:X，其中每个X表示地址中的16b，以十六进制表示，例如：ABCD:EF01:2345:6789:ABCD:EF01:2345:6789这种表示法中，每个X的前导0是可以省略的，例如：2001:0DB8:0000:0023:0008:0800:200C:417A→2001:DB8:0:23:8:800:200C:417A 二、0位压缩表示法在某些情况下，一个IPv6地址中间可能包含很长的一段0，可以把连续的一段0压缩为“::”。但为保证地址解析的唯一性，地址中”::”只能出现一次，例如：FF01:0:0:0:0:0:0:1101→FF01::11010:0:0:0:0:0:0:1→::10:0:0:0:0:0:0:0→:: 三、内嵌IPv4地址表示法为了实现IPv4-IPv6互通，IPv4地址会嵌入IPv6地址中，此时地址常表示为：X:X:X:X:X:X:d.d.d.d，前96b采用冒分十六进制表示，而最后32b地址则使用IPv4的点分十进制表示，例如::192.168.0.1与::FFFF:192.168.0.1就是两个典型的例子，注意在前96b中，压缩0位的方法依旧适用[11]。 IPv6的报文头部结构如图： IPv6报文中不再有“选项”字段，而是通过“下一报头”字段配合IPv6扩展报头来实现选项的功能。使用扩展头时，将在IPv6报文下一报头字段表明首个扩展报头的类型，再根据该类型对扩展报头进行读取与处理。每个扩展报头同样包含下一报头字段，若接下来有其他扩展报头，即在该字段中继续标明接下来的扩展报头的类型，从而达到添加连续多个扩展报头的目的。在最后一个扩展报头的下一报头字段中，则标明该报文上层协议的类型，用以读取上层协议数据[12]。 搜索引擎的原理，可以分为四步：从互联网上抓取网页、建立索引数据库、在索引数据库中搜索排序、对搜索结果进行处理和排序。 利用能够从互联网上自动收集网页的蜘蛛系统程序，自动访问互联网，并沿着任何网页中所有URL爬到其他网页，重复这个过程，并把爬过的所有网页收集回来。 加密技术一般分为对称式加密以及非对称式加密两类。采用的比较广泛的是对称式加密，主要特点是加密和解密使用同一个密钥。而非对称式加密在进行加密时则使用了两个密钥，加密和解密过程中分别使用不同的密钥，这两个密钥分别为“公钥”以及“私钥”，想要能正常完成加密解密过程，就必需配对使用，而在使用过程中，“公钥”是公开的，“私钥”则必须由发送人保密，同时只能由持有人所有。对称式的加密方法如果用于通过网络传输加密文件，那么不管使用任何方法将密钥告诉对方，都有可能被窃听，而非对称式的加密方法则具有一定的优越性，因为它包含有两个密钥，且仅有其中的“公钥”是可以被公开的，接收方只需要使用自己已持有的私钥进行解密，这样就可以很好的避免密钥在传输过程中产生的安全问题。 数据可用性是一种以使用者为中心的设计概念，易用性设计的重点在于让产品的设计能够符合使用者的习惯与需求。以互联网网站的设计为例，希望让使用者在浏览的过程中不会产生压力或感到挫折，并能让使用者在使用网站功能时，能用最少的努力发挥最大的效能。基于这个原因，任何有违信息的“可用性”都算是违反信息安全的规定。因此，世上不少国家，不论是美国还是中国都有要求保持信息可以不受规限地流通的运动举行。 网络安全主要有系统安全、网络的安全、信息传播安全、信息内容安全。具体如下： 运行系统安全即保证信息处理和传输系统的安全，侧重于保证系统正常运行。避免因为系统的崩演和损坏而对系统存储、处理和传输的消息造成破坏和损失。避免由于电磁泄翻，产生信息泄露，干扰他人或受他人干扰。 网络上系统信息的安全，包括用户口令鉴别，用户存取权限控制，数据存取权限、方式控制，安全审计。安全问题跟踩。计算机病毒防治，数据加密等。 网络上信息传播安全，即信息传播后果的安全，包括信息过滤等。它侧重于防止和控制由非法、有害的信息进行传播所产生的后果，避免公用网络上大云自由传翰的信息失控。 网络上信息内容的安全侧重于保护信息的保密性、真实性和完整性。避免攻击者利用系统的安全漏洞进行窃听、冒充、诈骗等有损于合法用户的行为。其本质是保护用户的利益和隐私。 它能增强机构内部网络的安全性。Internet防火墙负责管理Internet和机构内部网络之间的访问。在没有防火墙时，内部网络上的每个节点都暴露给Internet上的其它主机，极易受到攻击。这就意味着内部网络的安全性要由每一个主机的坚固程度来决定，并且安全性等同于其中最弱的系统。 在这个网络生态系统内，每个网络用户都可以相互信任彼此的身份，网络用户也可以自主选择是否拥有电子标识。除了能够增加网络安全，电子标识还可以让网络用户通过创建和应用更多可信的虚拟身份，让网络用户少记甚至完全不用去记那些烦人的密码。 CA中心采用的是以数字加密技术为核心的数字证书认证技术，通过数字证书，CA中心可以对互联网上所传输的各种信息进行加密、解密、数字签名与签名认证等各种处理，同时也能保障在数字传输的过程中不被不法分子所侵入，或者即使受到侵入也无法查看其中的内容。 多路复用：当传输介质的带宽超过了传输单个信号所需的带宽时，通过在一条介质上同时携带多个传输信号的方法来提高传输系统的利用率。 多路复用技术能把多个信号组合在一条物理信道上进行传输，使多个计算机或终端设备共享信道资源，提高信道利用率。 信道共享技术又称为多点接入（multipleaccess）技术，包括随机接入和受控。 ②受控接入，特点是各个用户不能随意接入信道而必须服从一定的控制。又可分为集中式控制和分散式控制。 我们日常使用最多的ping，就是响应请求（Type=8）和应答（Type=0），一台主机向一个节点发送一个Type=8的ICMP报文，如果途中没有异常（例如被路由器丢弃、目标不回应ICMP或传输失败），则目标返回Type=0的ICMP报文，说明这台主机存在，更详细的tracert通过计算ICMP报文通过的节点来确定主机与目标之间的网络距离。[5] 基于字符传输 DHCP（DynamicHostConfigurationProtocol，动态主机配置协议）通常被应用在大型的局域网络环境中，主要作用是集中的管理、分配IP地址，使网络环境中的主机动态的获得IP地址、Gateway地址、DNS服务器地址等信息，并能够提升地址的使用率。 DHCP有三种机制分配IP地址： 三种地址分配方式中，只有动态分配可以重复使用客户端不再需要的地址。 DHCP消息的格式是基于BOOTP（BootstrapProtocol）消息格式的，这就要求设备具有BOOTP中继代理的功能，并能够与BOOTP客户端和DHCP服务器实现交互。BOOTP中继代理的功能，使得没有必要在每个物理网络都部署一个DHCP服务器。RFC951和RFC1542对BOOTP协议进行了详细描述。 随机通道存储器（randomaccessmemory）。一般用来存放各种现场的输入输出数据、中间计算结果、与外存交换的信息以及作为堆栈。一般分为双极型RAM和MOSRAM（又分为静态SRAM、动态DRAM）。 双极型RAM以晶体管的触发器作为基本存储电路，所以管子多，速度快、功耗大、集成度较低、成本高，一般用于高速计算机或者cache。 MOSRAM一般分为静态SRAM和动态DRAM。静态RAM用由六管构成的触发器作为基本电路，集成度适中，功耗适中，速度较快，不需要刷新电路（为了维持数据，动态RAM中需要一个刷新电路，在短周期内对所有基本存储单元进行充电，维持电平状态，来达到数据的保存）。 动态DRAM基本存储电路用单管线路组成（电平靠电容存储，如一般计算机中的内存），集成度高，功耗低，成本比SRAM低，由于靠电容的电荷保持电平，所以需要刷新电路（典型要求每隔1ms刷新一次）。 总的说RAM使用晶体管打开或关闭通往位于交点处的电容器来访问电路。它有如下特性：A、易挥发B、速度快C、成本高，即不易制作大容量的RAM。所以这类存储器一般用在计算机设备的内存部分，而且往往容量不会很大。 可擦写可编程rom：有紫外线擦除（EPROM，70年代初）、电擦除（EEPROM）以及FLASH（闪存）。他们都是可以多次重复擦写的ROM。 EPROM原理是通过击穿绝缘层向浮空栅注入电子进行写操作；利用紫外线使浮空栅电子泄露进行擦操作。 EEPROM：原理与EPROM相似，在绝缘层间加入隧道二极管，于是可以通过电场作用，使浮空栅带上电子或消去。 上图是一位全加器示意图：Ai、Bi是两个二进制加数，Ci-1是上一级加法器的进位，Si是本级一位加法输出，Ci是加法进位。真值表如下： Si=Ai⊙Bi⊙Ci-1 Ci=（Ai⊙Bi）Ci-1+AiBi（⊙表示异或逻辑） 芯片组（Chipset）是构成主板电路的核心。一定意义上讲，它决定了主板的级别和档次。它就是"南桥"和"北桥"的统称，就是把以前复杂的电路和元件最大限度地集成在几颗芯片内的芯片组。芯片组是整个身体的神经，芯片组几乎决定了这块主板的功能，进而影响到整个电脑系统性能的发挥，芯片组是主板的灵魂。芯片组性能的优劣，决定了主板性能的好坏与级别的高低。这是因为目前CPU的型号与种类繁多、功能特点不一，如果芯片组不能与CPU良好地协同工作，将严重地影响计算机的整体性能甚至不能正常工作。 北桥芯片****：提供对CPU类型和主频的支持、系统高速缓存的支持、主板的系统总线频率、内存管理（内存类型、容量和性能）、显卡插槽规格，ISA/PCI/AGP插槽、ECC纠错等支持； 南桥芯片****：提供了对I/O的支持，提供对KBC（键盘控制器）、RTC（实时时钟控制器）、USB（通用串行总线）、UltraDMA/33(66)EIDE数据传输方式和ACPI（高级能源管理）等的支持，以及决定扩展槽的种类与数量、扩展接口的类型和数量（如USB2.0/1.1，IEEE1394，串口，并口，笔记本的VGA输出接口）等； 三类：电位触发、主从触发、边沿触发 中断源产生中断请求，CPU一般要先屏蔽该中断源的中断，防止错误的中断嵌套->CPU对现场进行保存，存储断点程序地址并将当前数据压入栈中->PC指向对应的中断入口，转入执行中断向量指向的中断服务程序->完成中断响应后，恢复现场，程序回到断点处，将栈中的数据重新读出->重新开中断。 中断传输：中断式传送是指处理器进行的各种处理。执行主程序时，输入设备准备好数据，或者输出设备已把数据输出，向处理器发出中断申请，使处理器中止当前程序的执行，转向中断服务程序，读取输入设备的数据，或者把数据送往输出设备。 中断是难以或者无法预测的，查询的操作是用户在程序中制定的，所以一般是可以控制的。 USB好像是同步的。 PC机的串口是异步的，即UART，采用RS-232标准。 异步通信：它用一个起始位表示字符的开始，用停止位表示字符的结束来构成一帧。它的传输帧是由起始位、内容和停止位构成的。每个字符可能还包含有奇偶校验位。波特率一般在50-9600baud。数据信号传输速率单位是字符/秒或bps。 同步通信：为了提高速度，去掉异步通信中使用的起始位和停止位，而在数据块开始前使用一段同步字符指示通信开始，同步通信对整块数据进行传输，速度较快，通常为几十到几百Kbaud。 电路的输出仅由该时刻电路的输入决定的电路，称为组合逻辑电路。 上面那句是概念性的东西，具体在数字电路组合逻辑部分。 郎艳峰上的EDA技术用的FPGA就是组合逻辑控制的一种，不过那个太低端了。。 程序的特点是：为了达到一定目的，程序按照一定的逻辑关系一条一条地执行，程序执行的快慢取决于机器周期的快慢、CPU的性能以及软件算法的优劣等。 1、速度上：组合逻辑电路由用户制定好逻辑关系后，输入信号经过电路的响应，直接得出结果，很大程度上是纯硬件的响应，因此在时刻间隙内可以完成可能需要通过多条程序才能完成的算法，不难看出，组合逻辑电路设计的控制单元比程序控制的单元具有更快的处理速度，而且系统越复杂，组合逻辑在速度上的优势越明显。 2、复杂度上：组合逻辑电路是由设计者按照自己的设想将众多逻辑器件组合而成的，对于较为复杂的系统，设计一个逻辑电路往往需要庞大的工作量，检验和仿真等都是费时费力的工程。在这一点上，程控的方法显得方便的多，程序结构的有条不紊是它在设计复杂度上占优势的主要因素。一个无比复杂的逻辑结构可能只需要设计者为CPU设计一些精炼的算法就可以实现，在对处理速度没有十分苛刻的要求情况下，通过程序设计会大大地减轻设计者的工作量。 3、成本：一般来说，大型可编程逻辑器件的成本要比一些较为高端的处理器或单片机高得多，而且工作量一般比较大，花费的工比较多。 总的来说，工程设计上，要综合实际应用的要求和成本，设计者要尽量选择全方位的设计方案。 接口：接口是位于主机和外设之间的一种缓冲电路，包括了硬件电路和软件控制，现在接口通常为可编程的大规模集成电路芯片。 端口：接口电路通常有三种寄存器：数据输入输出缓冲寄存器、控制寄存器、状态寄存器。这些寄存器称为（数据、控制、状态）端口。对I/O设备的访问，就是通过对端口访问实现的，每个端口赋予一个唯一的地址码，称为端口地址。 端口的编址：独立编址和统一编址。统一编址是将端口当做存储器单元，与内存统一编址，内存和端口的操作指令是统一的，所以指令功能强，但是端口占用了存储器的地址空间，使存储器容量减少。 独立编址也称为I/O映射编址，即端口和内存分开各自独立地拥有自己的地址空间，端口不占用存储器空间。 80x86采用独立编址。 I/O端口地址译码：1、用逻辑门电路进行译码2、用译码器进行译码3、比较器译码4、PROM（可编程rom）和GAL（通用逻辑阵列）。 指当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。 在响应中断时，CPU执行两个连续的中断响应周期，每个周期都输出中断响应信号/INTA，第一个周期CPU使0~15位的地址总线(8086有20根地址总线)浮空，第二个周期被响应的外设向数据总线输送一个字节的中断向量号，而后CPU读取中断向量号，转向中断服务程序，响应中断。 有些不可屏蔽中断是可以打断其它中断的。如掉电、复位等。 我们把要求计算机执行的各种操作用命令的形式写下来，就是指令。 通常一条指令对应着一种基本操作，其具体的功能是由设计人员赋予它的指令系统决定的。一台计算机能执行什么样的操作，能做多少种操作，是由设计计算机时所规定的指令系统决定的。一条指令，对应着一种基本操作。计算机所能执行的全部指令，就是计算机的指令系统，这是计算机所固有的。 指令通常分为操作码和操作数两部分。操作码表示计算机执行什么操作；操作数指明参加操作的数的本身或操作数所在的位置。 什么是总线周期，以及三者的关系如下： 采用冯·诺依曼体系构架，即数据和程序统一放在同一块存储器里。80X86CPU是由几个独立的不同功能部件构成的：执行部件、指令部件、总线部件和地址部件。其中，8086只有执行部件和总线部件。 8086是16位处理器，采用40引脚封装，分别有16位数据线，以及20位地址线（其中16根与数据线公用），可寻址1MB空间的内存。 中断信号线：INTR（输入）、NMI（输入）、/INTA（输出、三态）； 系统复位：RESET，输入；准备好：READY，输入；测试：/TEST，输入； 时钟：CLK，输入； 电源：Vcc； 底线：GND； 读选通：/RD，输出； 写选通：/WD，输出； 模式选择信号：MN/~MX，最小/最大工作模式控制信号，输入。高电平工作于最小模式，组成单处理器系统；低电平工作于最大模式，组成多处理器系统。 IA-32结构的CPU通常有四种主要的寻址方式：立即数寻址，寄存器操作数寻址，（前面两类比较简单，跟单片机差不多），IO端口寻址（在第10题里说过）和存储器操作数寻址。以下是存储器操作数寻址方式详解： 8086采用段寻址方式，有4个16位段寄存器：CS：代码段寄存器；DS：数据段寄存器；SS：堆栈段寄存器；ES：附加段寄存器（第二个数据段）。 8086把1MB的存储空间分为若干段，每段用一个段寄存器标识。每个段的起始值（段基值）按如下方法得出： 段基值=（段寄存器内容）16=（段寄存器内容）10H(即左移四位)。 8086的物理地址形成方法：段地址：偏移；即在段基址的基础上加上偏移地址量。偏移地址量存放在IP（代码指针），SP（堆栈指针），SI（源变址寄存器），DI(目的变址寄存器)四个寄存器中，或使用一个有效地址EA，该EA地址的内容就是偏移量。 80286开始有了实地址、保护方式两种不同的存储器管理模式，往后的CPU物理存储空间逐渐加大，也都拥有这两种管理模式。实地址方式类似于8086类似的物理地址生成。保护方式下，CPU可提供一定大小的虚拟存储空间，这个大小一般比物理地址空间大得多。执行程序时，若相应的程序段未调入内存，则向操作系统发出中断，把所需要的程序段和数据从外存调入内存，所以用户可以不受实际物理空间大小的限制，有利于开发大规模的程序。 程序控制传送分为无条件传送（同步传送）和程序查询传送（条件传送、异步传送）。条件查询的条件是在执行输入或输出指令前，要先查询接口中状态寄存器的状态。输入时，由它只是要输入的数据是否已准备就绪；而输出时，由它只是输出设备是否空闲，由此条件决定执行输入或输出。 CALL（LCALL）指令执行时，进行两步操作： （1）将程序当前执行的位置IP，加1压入堆栈中； （2）转移到调用的子程序。 RET指令：从堆栈的栈顶取得在执行call指令时压入的代码地址值，继续执行之前的程序。 中断虽然是对设备实时地进行了响应，但是还是需要通过CPU对数据进行读写操作，导致数据的传输速率受到影响，而且执行中断响应要执行多条指令，这样还是降低了CPU的效率。DMA是直接存储器访问技术，它可以避开CPU，让CPU暂停对总线的控制，独自占用总线达到对外设和内存之间的数据传输，传输结束时，释放总线并通知CPU重新控制总线。如此一来，数据的传输速率基本只受限于存储器的性能。 PC机中一般都设有DMA控制器来提高数据的吞吐率，减轻CPU负担，提高操作系统运行速度。 DMA的一般过程如下： 1、向CPU发出hold信号； 2、当CPU返回HLDA信号后，接管和控制总线，进入DMA方式； 3、发出地址信息，能对存储器寻址以及能修改地址指针； 4、发出读、写等控制信号； 5、决定传送的字节数，判断DMA传送是否结束； 6、发出DMA结束信号，使CPU恢复正常工作状态。 高速缓冲存储器：比主存储器体积小但速度快，用于保有从主存储器得到指令的副本。很可能在下一步为处理器所需的专用缓冲器。一般采用SRAM技术。 主要由三大部分组成： Cache存储体：存放由主存调入的指令与数据块。 地址转换部件：建立目录表以实现主存地址到缓存地址的转换。 替换部件：在缓存已满时按一定策略进行数据块替换，并修改地址转换部件。 电子线路设计：审题并制定方案->借助CAD或者EDA技术进行模拟仿真->电子线路要进行器件选型->电子线路要制板->加工->测试->总结 集成电路设计：审题并制定方案->设计验证和基础器件设计->生产->测试->总结 PC机的CPU是单纯的处理器，它提供的是丰富的I/O口资源和高速的处理速度，它本身没有太多资源，这让它无法单独运行，但是具有极高的可扩展性，结合大量外设（如存储器、DMA、各种控制器等）同它构成完整的系统能够发挥出它的巨大作用，一般用在高端的场合。如今的CPU主频可高达3G赫兹以上，功耗大，组成的设备体积大，功能强，资源多。它在系统中起数据处理和任务调度的作用。 单片机在一块芯片上集成了包括CPU、存储器、AD/DA在内的许多外设，CPU同外设的接口都由厂家统一规划，集成度高，性能稳定，使用者只需要操作CPU对各外设的寄存器进行操作即可。单片机的引脚多被外设占用，因此IO口的资源很有限，可扩展性不高，而且它片内的CPU性能一般不会太高，如今高端的单片机虽然运用32位处理器，但工作频率最高只有百兆赫兹，处理速度不快，适用于一些小体积、低功耗、低要求、低成本的场合。单片机在系统中一般作为核心的控制器，外围电路一般不需要添加很多其它设备。 PC的CPU一般采用冯·诺依曼结构，单片机中一般采用哈佛构架（程序和数据存放在不同的存储器中）。 N****型半导体：在本征半导体中掺入少量五价元素（如磷P），成为N型半导体。由于掺入杂质后，电离能力大大加强，电离产生自由电子，所以掺入的杂质称为施主杂质，留下的带正电的离子称为施主离子。这种掺有施主杂质的、以电子导电为主的半导体，称为N型半导体。N型半导体中，多子是自由电子，少子是空穴。 P****型半导体：在本征半导体中掺入少量三价元素（如硼B），成为P型半导体。如硼一类的三价元素，起着接受电子的作用，称为受主杂质，电离后不可移动的负离子称为受主离子。掺有受主杂质的半导体中，空穴的浓度远远大于自由电子的浓度，所以空穴成为多子，自由电子成为少子，这种掺有受主杂质的半导体称为P型半导体。 两种载流子的运动：扩散运动、漂移运动。扩散运动是载流子由高浓度向低浓度扩散引起的，这样形成的电流称为扩散电流。漂移运动是在电场的作用下，载流子沿着电场方向（自由电子逆电场方向）运动造成的，这样形成的电流称为漂移电流。 PN****结原理：P、N型半导体结合后，由于两边载流子相互吸引。在交界处附近，载流子都被束缚在晶体的晶格上无法参与导电，于是形成了一个电荷数目相等、极性相反的空间电荷区（耗尽层）。空间电荷区存在内建电场，电场的方向由N指向P（因为N中电离出电子，余下的是正离子，带正电）。由于这个内建电场的作用，两边多子的扩散受到抑制，而同时也出现了少子的漂移。当扩散电流和漂移电流达到平衡时，空间电荷区达到平衡状态，从而形成PN结。 PN****结单向导电原理：PN结是处于一个平衡的状态，这个状态的原因是由于内建电场的作用。所以很明显，如果在PN结的两端加上电压，将会打破这个平衡。1、正向电压（P->N，表示P接正极，N接负极）：正向电压与内建电场的方向相反，于是抑制了PN结两方少子的漂移运动，扩散电流大于漂移电流，产生正向电流。当正向电压加大时，势垒电场（内建电场）会进一步减小，正向电流进一步扩大。2、反向电压（N->P）：反之，当加上反向电压后，内建电场受到增强，势垒电压增大，漂移电流增大，但是由于漂移电流的产生源于PN结两边的少子，数量很少，所以该漂移电流也很小，PN结处于反向截止状态，这时电路中的电流称为反向电流。当反向电压不是很高时，几乎所有的少子均参与了漂移运动，所以当反向电压再变大时，反向电流几乎不增大，故反向电流又称为反向饱和电流。但PN结对温度比较敏感，如果温度上升，PN结中少子数量急剧增加，反向电流也会迅速变大。 传递函数（系统函数）有并联型，串联型和反馈型。并联型的n个系统函数等效于将这n个系统函数相加成一个系统函数，串联型等效于相乘。 研究系统的输入控制系统状态的能力。 研究系统的输出观测系统状态的能力。 DAC主要由数字寄存器、模拟电子开关、位权网络、求和运算放大器和基准电压源组成。数据存入数字寄存器中，控制模拟电子开关通断，在位权网络中形成于输入电压（电流）成比例关系的比例结构，通过运放进行运算输出。（具体内容数电上有） 渐进稳定嘛，就是一个反馈系统，它的输入响应一开始是呈减幅震荡的，但最终渐渐地趋向于一个稳定值，或者在这个值左右小幅震荡。比如说一个PID算法控制电机转速的系统，电机的转速就是渐进稳定，趋向于预定转速的。 波长λ是波在传播时，同一波线上两个相邻的、相位差为2π的质点之间的距离。λ=波速u*周期T 波在波源移向观察者时接收频率变高，而在波源远离观察者时接收频率变低。或者说，当观察者向波源移动时，频率变高，反之亦然。 1、点对点、广播（点对多点）、多点对多点（路由）。（我觉得是==`） 2、频分复用（FDM）、时分多址（TDMA）、码分多址（CDMA）。如果问到正交频分复用（OFDM），自求多福吧，呵呵。 如果一个信号含有的最高的频率分量是Fh，在用频率为Fs的抽样信号对该信号进行采样时，采样后信号的频谱会作Fs周期的周期延拓，如果Fs<2*Fh的话，就会导致信号在频谱上出现混叠，这样就无法准确恢复出原信号。 奈奎斯特定律即：对连续信号采样时，抽样信号的频率要不小于被采样信号主瓣频率的两倍。即：