PDF文件自取

时间复杂性是指执行算法所需的计算工作量。由于整个算法的执行时间与基本操作的重复执行次数成正比，因此以算法中的基本操作次数作为算法时间复杂度的测量。一般来说，时间复杂度是根据基本操作次数最多的输入来计算的，在大多数情况下，我们在最深循环中描述的操作是基本操作。

这是用来区分空队和满队的情况的。如果一个位置不空，判断空队和满队的条件是一样的。

二叉排序树又称二叉搜索树，它或空树，或满足二叉树的性质：

① 若左树不空，则左树上所有结点的值均小于根节点的值；

② 如果右子树不空，右子树上所有结点的值都大于根节点的值；

③ 左右子树也是二叉排序树。

原理步骤：

若根结点的关键字值等于搜索的关键字，成功。

否则，如果关键字值小于根结点，递归检查左子树。

若大于根结点的关键字值，递归右子树。

若子树为空，发现不成功。

定义：

给定n个权值作为n个叶结点，构建二叉树。如果带权路径长度最小，则称这种二叉树为最佳二叉树，也称为哈夫曼树(Huffman tree)。

构造方法：

假设有n个权值，哈夫曼树就有n个叶结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的结构规则如下：

(1) 将w1、w2、…，wn看成是有n 森林(每棵树只有一个结点)；

(2) 选择森林中两个根结点权值最小的树合并，作为新树的左右树，新树的根结点权值为其左右根结点权值之和；

(3)从森林中删除选定的两棵树，并将新树添加到森林中；

(4)重复(2)、(3)步，直到森林里只剩下一棵树，这棵树就是哈夫曼树。

特点：

① 结点越大，离根节点越近；

② 树中没有度为一的结点。

应用：

哈夫曼编码，减少编码长度。哈夫曼编码是长度最短的前缀编码。

散列(哈希)表：

根据关键码值(Key value)直接访问的数据结构。根据给定的关键字计算表中关键字的地址，以加快搜索速度。

冲突：指多个关键字映射同一地址的情况。

解决办法：

（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(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时查找结束。

适用范围：顺序结构存储并按照关键字大小有序排列。

时间复杂度：O(log2N)

若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

完全二叉树特点：

叶子结点只可能在最大的两层上出现， 对任意结点， 若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；

堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足：

任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。若父亲大孩子小，则为大顶堆，若父亲肖孩子大，则为小顶堆。

作用：应用于堆排序。

如何实现：把数组弄成一个环，让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 硬中断不可屏蔽），软中断不可屏蔽。

区别：

1、软中断发生的时间是由程序控制的,而硬中断发生的时间是随机的

2、软中断是由程序调用发生的,而硬中断是由外设引发的

3、硬件中断处理程序要确保它能快速地完成它的任务,这样程序执行时才不会等待较长时间。

① 最佳置换算法（OPT）：在预知一个进程的页面号引用串的情况下，每次都淘汰以后不再使用的货以后最迟再被使用的页面。该算法不能实现，只能作为一个标准来衡量其他置换算法的优劣。

② 先进先出算法（FIFO）：每次总是淘汰最先进入内存的页面，也就是将在内存中驻留时间最长的页面淘汰。（可能会产生Belady异常，缺页次数随着分配的物理块的增加而增加）。

③ 最近最少使用算法（LRU）：选择最近最少未被使用的页面淘汰，其思想是用以前的页面引用情况来预测将来会出现的页面引用情况。利用了局部性原理。

④ 时钟置换算法（CLOCK）：是LRU和FIFO的折中，具体方法略。

⑤ 工作集算法

⑥ 工作集时钟算法

⑦ 第二次机会算法

⑧ 最近未使用（NRU）

磁盘调度算法目的：使磁盘的平均寻道时间最少。

信号量是一个确定的二元组（s，q），其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目；当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。

信号量分类：

① 整型信号量：所谓整型信号量就是一个用于表示资源个数的整型量

② 记录型信号量（资源信号量）：就是用一个结构体实现，里面包含了表示资源个数的整型量和一个等待队列。

信号量的应用：

① 实现进程同步

② 实现进程互斥

信号量的值除了初值外，仅能由这PV原语加以改变。P、V 操作以原语形式实现，保证了对信号量进行操作过程中不会被打断或阻塞。P 操作相当于申请资源，V 操作相当于释放资源。P操作和V操作必定成对出现，但未必在同一个进程中。

Struct semaphore{

       Int count;

       queueType queue;

       };

Wait (semaphore s)    // P

{

       s.count --;

       if(s.count<0)

           {   阻塞该进程；

               将该进程插入等待序列s.queue;

           }

}

signal (semaphore s)    // V

{

       s.count ++;

       if(s.count<=0)

           {   从等待队列s.queue取出第一个进程p；

               将p插入就绪队列;

           }

}

操作系统（Operating System，简称OS）是管理和控制计算机硬件与软件资源的计算机程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行。操作系统是用户和计算机的接口，同时也是计算机硬件和其他软件的接口。操作系统的功能包括管理计算机系统的硬件、软件及数据资源，控制程序运行，改善人机界面，为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，提供了各种形式的用户界面，使用户有一个好的工作环境，为其它软件的开发提供必要的服务和相应的接口。

操作系统理论研究者有时把操作系统分成四大部分：

1. 驱动程序是最底层的、直接控制和监视各类硬件的部分，它们的职责是隐藏硬件的具体细节，并向其他部分提供一个抽象的、通用的接口。

2. 内核是操作系统之最内核部分，通常运行在最高特权级，负责提供基础性、结构性的功能。

3. 支承库是一系列特殊的程序库，它们职责在于把系统所提供的基本服务包装成应用程序所能够使用的编程接口（API），是最靠近应用程序的部分。例如，GNU C运行期库就属于此类，它把各种操作系统的内部编程接口包装成ANSI C和POSIX编程接口的形式。

4. 外围是指操作系统中除以上三类以外的所有其他部分，通常是用于提供特定高级服务的部件。例如，在微内核结构中，大部分系统服务，以及UNIX/Linux中各种守护进程都通常被划归此列。

栈：运算器出栈压栈

队列：进程管理

树：目录管理

表格：优先级的设置

系统调用提供了用户程序和操作系统之间的接口，应用程序通过系统调用实现其余OS的通信，并取得它的服务。系统调用不仅可供所有的应用程序使用，而且也可供OS本身的其它部分，如命令处理程序。

系统调用的处理步骤（三步）：

首先，将处理机状态由用户态转为系统态；然后由硬件和内核程序进行系统调用的一般性处理，即首先保护被中断进程的CPU环境，将处理机状态字PSW、程序计数器PC、系统调用号、用户栈指针以及通用寄存器内容等压入堆栈；再然后将用户定义的参数传送到指定的地址保存起来。

其次，分析系统调用类型，转入相应的系统调用处理子程序。（通过查找系统调用入口表，找到相应处理子程序的入口地址转而去执行它。）

最后，在系统调用处理子程序执行完后，应恢复被中断的货设置新进程的CPU现场，然后返回被中断进程或新进程，继续往下执行。

基于局部性原理，应用程序在运行之前，仅将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂时留在盘上。程序运行时，如果它要访问的页已调入内存，便可继续执行下去；但如果程序要访问的页或段尚未调入内存（即缺页），此时程序应利用请求调入功能将它们调入内存，以使程序能继续执行下去。如果此时内存已满，无法装入新的页或段，则需要利用页面置换功能，将内存中暂不使用的页面或段调至盘上，腾出空间用于页面调入内存，是程序继续执行下去。这样，就实现了大的用户程序能在较小的内存空间里运行，也可以在内存中同时装入更多的进程使它们并发运行。从用户角度出发，该系统的内存容量比实际内存容量大很多，故成这样的存储器为虚拟存储器。

相关算法：

页面置换算法

① 最佳置换算法（OPT）：在预知一个进程的页面号引用串的情况下，每次都淘汰以后不再使用的货以后最迟再被使用的页面。该算法不能实现，只能作为一个标准来衡量其他置换算法的优劣。

② 先进先出算法（FIFO）：每次总是淘汰最先进入内存的页面，也就是将在内存中驻留时间最长的页面淘汰。（可能会产生Belady异常，缺页次数随着分配的物理块的增加而增加）。

③ 最近最少使用算法（LRU）：选择最近最少未被使用的页面淘汰，其思想是用以前的页面引用情况来预测将来会出现的页面引用情况。利用了局部性原理。

④ 时钟置换算法（CLOCK）：是LRU和FIFO的折中，具体方法略。

⑤ 工作集算法

⑥ 工作集时钟算法

⑦ 第二次机会算法

⑧ 最近未使用（NRU）

存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器，故应具有以下功能：

① 内存的分配和回收：实施内存的分配，回收系统或用户释放的内存空间。

② 地址变换：提供地址变换功能，将逻辑地址转换成物理地址。

③ 扩充内存：借助于虚拟存储技术活其他自动覆盖技术，为用户提供比内存空间大的地址空间，从逻辑上扩充内存。

④ 存储保护：保证进入内存的各道作业都在自己的存储空间内运行，互不干扰。

TLB 的作用是在处理器访问内存数据的时候做地址转换。TLB 的全称是Translation Lookaside Buffer，可以翻译做旁路缓冲，是一个具有并行查询能力的特殊高速缓冲寄存器。TLB中存放了一些页表文件，文件中记录了虚拟地址和物理地址的映射关系。当应用程序访问一个虚拟地址的时候，会从TLB 中查询出对应的物理地址，然后访问物理地址。TLB 通常是一个分层结构，使用与Cache 类似的原理。处理器使用一定的算法把最常用的页表放在最先访问的层次。

补充：应用程序从用户编写的源文件到内内存中执行的进程大致分为三个阶段，经过编译程序将源代码便以为若干个目标模块，在通过链接程序将编译好的目标模块以及所需的库函数链接到一起，形成完整的装入模块，最后通过装入程序将这些装入模块装入内存并执行。（编译，链接，装入）

装入方式：

① 绝对装入：在编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计。

② 可重定位装入：根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称静态重定位。当操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址。

③ 动态运行装入：允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现要依靠硬件地址变换机构。

① 静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开。

② 装入时动态链接：将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式。

③ 运行时动态链接：知道程序运行过程中需要一些模块时，才对这些模块进行链接。

覆盖技术：把一个大的程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位，把程序执行时并不要求同时装入内存的覆盖组成一组，成为覆盖段，这个覆盖段分配到同一个存储区域，这个存储区域成为覆盖区，它与覆盖段一一对应。覆盖段的大小由覆盖段中最大的覆盖来确定。（为了解决内存容量太小的问题，打破了必须将一个程序全部信息装入内存后才能运行的限制）

交换技术：把暂时不用的某个程序及数据部分从内存移到外存中去，以便腾出必要的内存空间；或者把指定的程序或数据从外存读到相应的内存中，并将控制权交给他，让其在系统上运行的一种内存扩充技术。处理器的中级调度就是采用交换技术。

区别：

① 与覆盖技术相比，交换技术不要求程序员给出的程序段之间的覆盖结构；

② 交换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行；

③ 覆盖技术只能覆盖于覆盖程序段无关的程序段，交换进程由换出和换入两个过程组成。

① 单一连续分配（静态分配）

② 固定分区分配（分区大小可以不等，但事先必须确定，运行时不能改变）

③ 动态分区分配

P131详细

① 首次适应算法First Fit

② 循环首次适应算法Next Fit

③ 最佳适应算法Best Fit

④ 最差适应算法Worst Fit

在分区管理方式下，系统运行一段时间后，内存中会出现相当一部分的碎片，拼接技术是解决碎片问题的方法。

即将存储器中所有已分配分区移动到主存的一端，使本来分散的多个小空闲区连成一个大的空闲区，这种通过移动把多个分散的小分区拼接成一个大分区的方法即为拼接技术。

所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）。

内部碎片：分配给作业的存储空间中未被利用的部分。

外部碎片：系统中无法利用的小存储块，比如通过动态内存分配技术从空闲内存区上分配内存后剩下的那

部分内存块。

（1）界限寄存器

上下界寄存器方法

基址、限长寄存器方法

为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页面映射表。

页表由页表项组成，页表项有页号和块号组成，根据页表项就可以找到每个页号对于物理内存中物理块的块号。

段寄存器是因为对内存的分段管理而设置的。计算机需要对内存分段，以分配给不同的程序使用（类似于硬盘[分页。在描述内存分段时，需要有如下段的信息：1.段的大小；2.段的起始地址；3.段的管理属性（禁止写入/禁止/执行/系统专用等）。需要用8个字节（64位）存储这些信息，但段寄存器只有16位，因此段寄存器中只能存储段号（segment selector，也译作“段选择符”），再由段号映射到存在内存中的GDT（global (segment) descriptor table，全局段号记录表），读取段的信息。

进程树是一个形象化的比喻，比如一个进程启动了一个程序，而启动的这个进程就是原来那个进程的子进程，依此形成的一种树形的结构，我们可以在进程管理器选择结束进程树，就可以结束其子进程和派生的子进程。

一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成的某

项任务，是要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完

成4 个阶段。而进程是对已提交完毕的程序所执行过程的描述，是资源分配的基本单位。

其主要区别如下。

(1)作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后，系统将它放入外存中的作业等

待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，

只要它被创建，总有相应的部分存在于内存中。

(2) 一个作业可由多个进程组成，且必须至少由一个进程组成，反过来则不成立。

(3) 作业的概念主要用在批处理系统中，像UNIX 这样的分时系统中就没有作业的概念。而进程的概念则

用在几乎所有的多道程序系统中进程是操作系统进行资源分配的单位。在Windows 下,进程又被细化为线

程,也就是一个进程下有多个能独立运行的更小的单位。

① 先来先服务调度FCFS

② 短作业优先调度SJF

③ 优先级调度Priority

④ 时间片轮转调度RR

⑤ 高响应比优先调度

⑥ 多级队列调度

⑦ 多级反馈队列调度

死锁： 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

① 系统资源不足

② 进程推进顺序不当

① 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。

② 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

③ 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

④ 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0 正在等待一个P1 占用的资源；P1 正在等待P2 占用的资源，……，Pn 正在等待已被P0占用的资源。

① 预防死锁：这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。

② 避免死锁：该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

③ 检测死锁：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。

④ 解除死锁：这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。

等待时间给进程推进和响应带来明显影响时成为进程饥饿。

饥饿并不代表系统一点死锁，但至少有一个程序的执行被无限期地推迟。

差别：

① 进入饥饿的进程可以只有一个，但是死锁必须大于等于两个；

② 出于饥饿状态的进程可以是一个就绪进程，但是死锁状态的进程必定是阻塞进程。

1、段是信息的逻辑单位，分段的目的是为了更好地实现共享,根据用户的需要划分，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要，其对用户是透明的。

2、段的大小不固定，由它所完成的功能决定；页的大小固定（一般为4K），由系统决定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。

3、段向用户提供二维地址（段号+段内地址）；页向用户提供的是一维地址（页号）

4、段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

主要思想是避免系统进入不安全状态，在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有，则先试行分配，并对分配后的新状态进行安全性检查。如果新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样就保证系统始终处于安全状态，从而避免死锁现象的发生。

独立磁盘冗余阵列（RAID，redundant array of independent disks，redundant array of inexpensive disks）是把相同的数据存储在多个硬盘的不同的地方（因此，冗余地）的方法。通过把数据放在多个硬盘上，输入输出操作能以平衡的方式交叠，改良性能。因为多个硬盘增加了平均故障间隔时间（MTBF），储存冗余数据也增加了容错。

文件控制块

集线器（多端口） 中继器（两个端口） 物理层

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发送的每个数据报是记录型的数据报，所谓的记录型数据报就是接收进程可以识别接收到的数据报的记录边界。

TCP应用场景：效率要求相对低，但对准确性要求相对高的场景。因为传输中需要对数据确认，重发，排序等操作，相比之下效率没有UDP高。举几个例子：文件传输、邮件传输、远程登录。

**UDP应用场景：**效率要求相对高，对准确性要求相对低的场景。举几个例子：QQ聊天、QQ视频，网络语音电话（即时通讯，要求速度高，但是出现偶尔断续不是太大问题，并且此处完全不可以使用重传机制）、广播通信（广播、多播）

传统交换机从网桥发展而来，属于OSI第二层即数据链路层设备。它根据MAC地址寻址，通过站表选择路由，站表的建立和维护由交换机自动进行。路由器属于OSI第三层即网络层设备，它根据IP地址进行寻址，通过路由表路由协议产生。交换机最大的好处是快速，由于交换机只须识别帧中MAC地址，直接根据MAC地址产生选择转发端口算法简单，便于ASIC实现，因此转发速度极高。但交换机的工作机制也带来一些问题。

1.回路：根据交换机地址学习和站表建立算法，交换机之间不允许存在回路。一旦存在回路，必须启动生成树算法，阻塞掉产生回路的端口。而路由器的路由协议没有这个问题，路由器之间可以有多条通路来平衡负载，提高可靠性。

2.负载集中：交换机之间只能有一条通路，使得信息集中在一条通信链路上，不能进行动态分配，以平衡负载。而路由器的路由协议算法可以避免这一点，OSPF路由协议算法不但能产生多条路由，而且能为不同的网络应用选择各自不同的最佳路由。

3.广播控制：交换机只能缩小冲突域，而不能缩小广播域。整个交换式网络就是一个大的广播域，广播报文散到整个交换式网络。而路由器可以隔离广播域，广播报文不能通过路由器继续进行广播。

4.子网划分：交换机只能识别MAC地址。MAC地址是物理地址，而且采用平坦的地址结构，因此不能根据MAC地址来划分子网。而路由器识别IP地址，IP地址由网络管理员分配，是逻辑地址且IP地址具有层次结构，被划分成网络号和主机号，可以非常方便地用于划分子网，路由器的主要功能就是用于连接不同的网络。

5.保密问题：虽说交换机也可以根据帧的源MAC地址、目的MAC地址和其他帧中内容对帧实施过滤，但路由器根据报文的源IP地址、目的IP地址、TCP端口地址等内容对报文实施过滤，更加直观方便。

6.介质相关：交换机作为桥接设备也能完成不同链路层和物理层之间的转换，但这种转换过程比较复杂，不适合ASIC实现，势必降低交换机的转发速度。因此目前交换机主要完成相同或相似物理介质和链路协议的网络互连，而不会用来在物理介质和链路层协议相差甚元的网络之间进行互连。而路由器则不同，它主要用于不同网络之间互连，因此能连接不同物理介质、链路层协议和网络层协议的网络。路由器在功能上虽然占据了优势，但价格昂贵，报文转发速度低。

近几年，交换机为提高性能做了许多改进，其中最突出的改进是虚拟网络和三层交换。

划分子网可以缩小广播域，减少广播风暴对网络的影响。路由器每一接口连接一个子网，广播报文不能经过路由器广播出去，连接在路由器不同接口的子网属于不同子网，子网范围由路由器物理划分。对交换机而言，每一个端口对应一个网段，由于子网由若干网段构成，通过对交换机端口的组合，可以逻辑划分子网。广播报文只能在子网内广播，不能扩散到别的子网内，通过合理划分逻辑子网，达到控制广播的目的。由于逻辑子网由交换机端口任意组合，没有物理上的相关性，因此称为虚拟子网，或叫虚拟网。虚拟网技术不用路由器就解决了广播报文的隔离问题，且虚拟网内网段与其物理位置无关，即相邻网段可以属于不同虚拟网，而相隔甚远的两个网段可能属于不同虚拟网，而相隔甚远的两个网段可能属于同一个虚拟网。不同虚拟网内的终端之间不能相互通信，增强了对网络内数据的访问控制。

交换机和路由器是性能和功能的矛盾体，交换机交换速度快，但控制功能弱，路由器控制性能强，但报文转发速度慢。解决这个矛盾的技术是三层交换，既有交换机线速转发报文能力，又有路由器良好的控制功能。

在第三层交换技术出现之前，几乎没有必要将路由功能器件和路由器区别开来，他们完全是相同的：提供路由功能正在路由器的工作，然而，现在第三层交换机完全能够执行传统路由器的大多数功能。作为网络互连的设备，第三层交换机具有以下特征：

1.转发基于第三层地址的业务流；

2.完全交换功能；

3.可以完成特殊服务，如报文过滤或认证；

4.执行或不执行路由处理。

第三层交换机与传统路由器相比有如下优点：

1.子网间传输带宽可任意分配：传统路由器每个接口连接一个子网，子网通过路由器进行传输的速率被接口的带宽所限制。而三层交换机则不同，它可以把多个端口定义成一个虚拟网，把多个端口组成的虚拟网作为虚拟网接口，该虚拟网内信息可通过组成虚拟网的端口送给三层交换机，由于端口数可任意指定，子网间传输带宽没有限制。

2.合理配置信息资源：由于访问子网内资源速率和访问全局网中资源速率没有区别，子网设置单独服务器的意义不大，通过在全局网中设置服务器群不仅节省费用，更可以合理配置信息资源。

3.降低成本：通常的网络设计用交换机构成子网，用路由器进行子网间互连。目前采用三层交换机进行网络设计，既可以进行任意虚拟子网划分，又可以通过交换机三层路由功能完成子网间通信，为此节省了价格昂贵的路由器。

4.交换机之间连接灵活：作为交换机，它们之间不允许存在回路，作为路由器，又可有多条通路来提高可靠性、平衡负载。三层交换机用生成树算法阻塞造成回路的端口，但进行路由选择时，依然把阻塞掉的通路作为可选路径参与路由选择。

物理层

数据链路层（PPP、HDLC、CSMA/CD）

网络层(IP、ARP（IP→MAC）/RARP(MAC→IP)、ICMP)

传输层（TCP、UDP）

会话层

表示层

应用层（telnet 23、FTP 20<数据>+21<控制>、SMTP 161、DNS、SNMP、DHCP、HTTP 80）

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地