北大面试题目：
一、内存交换
内存交换（对换）的基本思想是，把处于等待状态（或在CPU调度原则下被剥夺运行权利） 的程序从内存移到辅存，把内存空间腾出来，这一过程又叫换出；把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称为换入。
有关交换需要注意以下几个问题：
1、交换需要备份存储，通常是快速磁盘。它必须足够大，并且提供对这些内存映像的直接访问。
2、为了有效使用CPU，需要每个进程的执行时间比交换时间长，而影响交换时间的主要是转移时间。转移时间与所交换的内存空间成正比。
3、如果换出进程，必须确保该进程是完全处于空闲状态。
4、交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用就可能很快。
5、交换通常在有许多进程运行且内存空间吃紧时开始启动，而系统负荷降低就暂停。
6、普通的交换使用不多，但交换策略的某些变种在许多系统中（如UNIX系统）仍发挥作用。
二、进程通信
1、种进程间的通信方式
# 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
# 有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
# 信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
# 消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
# 信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
# 共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
# 套接字( socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。
进程间通信有4种方式，以下从简单到复杂的方式出场:
1.管道(pipe)
管道是一种具有两个端点的通信通道，一个管道实际上就是只存在在内存中的文件，对这个文件操作需要两个已经打开文件进行，他们代表管道的两端，也叫两个句槟，管道是一种特殊的文件，不属于一种文件系统，而是一种独立的文件系统，有自己的数据结构，根据管道的使用范围划分为无名管道和命名管道。
无名管道用于父进程和子进程之间，通常父进程创建管道，然后由通信的子进程继承父进程的读端点句柄和写端点句柄，或者父进程有读写句柄的子进程，这些子进程可以使用管道直接通信，不需要通过父进程。
命名管道，命名管道是为了解决无名管道只能在父子进程间通信而设计的，命名管道是建立在实际的磁盘介质或文件系统(而不是只存在内存中)，任何进程可以通过文件名或路径建立与该文件的联系，命名换到需要一种FIFO文件(有先进先出的原则)，虽然FIFO文件的inode节点在磁盘上，但仅是一个节点而已，文件的数据还是存在于内存缓冲页面中，和普通管道相同。
2.信号
信号，用于接受某种事件发生，除了用于进程间通信之外，进程还可以发送信号给进程本身。除了系统内核和root之外，只有具备相同id的进程才可以信号进行通信。
3.消息队列
消息队列是消息的链表，包括Posix消息队列和system v消息队列(Posix常用于线程，system常用于进程)，有权限的进程可以向消息队列中添加消息，有读权限的进程可以读走消息队列的消息。
消息队列克服了信号承载信息量少，管道只能承载无格式字节流及缓冲区大小受限等缺陷。
4.共享内存
共享内存使多个进程可以访问同一块内存空间，是最快的IPC形式，是针对其他通信方式运行效率低而设计的，往往与其他进程结合使用，如与信号量结合，来达到进程间的同步与互斥。传递文件最好用共享内存的方式。
三、应用层协议
网际层协议：包括：IP协议、ICMP协议、ARP协议、RARP协议。
传输层协议：TCP协议、UDP协议。
应用层协议：FTP、Telnet、SMTP、HTTP、RIP、NFS、DNS。
1.DNS:域名系统
DNS：域名系统。DNS是因特网使用的命名系统，用来把便于人们使用的机器名字转换为IP地址。
现在*域名TLD分为三大类：国家*域名nTLD；通用*域名gTLD;基础结构域名
域名服务器分为四种类型：根域名服务器；*域名服务器；本地域名服务器；权限域名服务器。
2.FTP:文件传输协议
FTP：文件传输协议。FTP是因特网上使用得最广泛的文件传送协议。FTP提供交互式的访问，允许客户指明文件类型与格式，并允许文件具有存取权限。FTP其于TCP。
3. Telnet:远程终端协议
Telnet:远程终端协议。telnet是一个简单的远程终端协议，它也是因特网的正式标准。又称为终端仿真协议。
4. HTTP:超文本传送协议
HTTP：超文本传送协议。是面向事务的应用层协议，它是万维网上能够可靠地交换文件的重要基础。http使用面向连接的TCP作为运输层协议，保证了数据的可靠传输。
5. SMTP:电子邮件协议
SMTP:电子邮件协议。即简单邮件传送协议。SMTP规定了在两个相互通信的SMTP进程之间应如何交换信息。SMTP通信的三个阶段：建立连接、邮件传送、连接释放。
6. POP3：邮件读取协议
POP3：邮件读取协议。POP3(Post Office Protocol 3)协议通常被用来接收电子邮件。
7. SNMP：简单网络管理协议
SNMP：简单网络管理协议。由三部分组成：SNMP本身、管理信息结构SMI和管理信息MIB。SNMP定义了管理站和代理之间所交换的分组格式。SMI定义了命名对象类型的通用规则，以及把对象和对象的值进行编码。MIB在被管理的实体中创建了命名对象，并规定类型。
四、饥饿与死锁
饥饿
饥饿是指系统不能保证某个进程的等待时间上界，从而使该进程长时间等待，当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死。
死锁
产生死锁的原因主要有两个，一是竞争资源，系统提供的资源数量有限，不能满足每个进程的需求；二是多道程序运行时，进程推进顺序不合理。由此可见，发生死锁时死锁进程的个数至少是两个。我们可以举一个最简单的例子来了解一下死锁：
假如双方都拥有部分资源（P1拥有A，P2拥有B，且A，B均只有一个），但这时P1还需要B，P2还需要A，于是P1与P2都会处在无限等待状态，发生了死锁。
由这个例子，我们可以归纳分析出产生死锁的必要条件：
(1) 互斥条件
资源是独占的且排他使用。即任意时刻一个资源只能给一个进程使用，其他申请者只有等待，直到资源被占有者释放。如例子中的Ａ，Ｂ资源。
(2) 不可剥夺条件
进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由拥有该资源的进程自愿释放。如例子中P2 不能强占P1拥有的A资源，而P1也不能强占P2拥有的B资源。
(3) 请求和保持条件
进程每次申请他所需要的一部分资源，在申请新的资源的同时，继续占用已分配到的资源。如例子中P1申请B资源时继续占有A资源，P2申请A资源时继续占有B资源。
(4) 循环等待条件
在发生死锁时，必然存在一个进程等待环路，环路中的每一个进程已占有的资源同时被另一个进程所申请。如例子中的P1和P2就是一个简单的等待环路。
系统发生死锁不仅浪费了大量的系统资源，甚至会导致整个系统的崩溃，因此如何解决死锁问题是操作系统设计中的一个重点。目前主要有两类方法，一类是不让死锁发生；另一类是让死锁发生，再加以解决。
死锁预防就是力图不让死锁发生，它采用破坏“不可剥夺”条件，或破坏“请求保持”条件，或破坏“循环等待”条件来达到目的，但这种方法给系统加上了较强的限制条件，严重的影响了系统性能。死锁避免则是不破坏死锁的必要条件，而是系统对进程发出的每一个系统能够满足的资源申请进行动态检验，并根据检验结果决定是否分配资源，如果分配后系统可能发生死锁，则不分配，否则分配。这种方法算法复杂，会消耗很多的系统时间。
死锁的检测与解除则属于让死锁发生，再加以解决的方法。操作系统不断的监督进程的进展路径，一旦检测到死锁的发生，则采用专门的措施解除死锁，并以最小的代价使整个系统恢复正常。
死锁和饥饿的异同
相同点：二者都是由于竞争资源而引起的。
不同点：
- 从进程状态考虑，死锁进程都处于等待状态，忙等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死；
- 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待)；
- 死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死；
- 死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。
- 在饥饿的情形下，系统中有至少一个进程能正常运行，只是饥饿进程得不到执行机会。而死锁则可能会最终使整个系统陷入死锁并崩溃。
七、冒泡与插入
其实冒泡排序和插入排序的区别是很大的，我倒是现在弄不明白之前自己为什么会混淆了。插入排序的思想就是，对于给定的待排序的数列，第一次分成两部分，一部分是有序部分，只有给定的数列的第一个元素，另外一部分是待排序的部分，有给定数列的剩余的元素。然后接着从给定数列的第二个元素开始，将元素依次放入有序部分的正确位置。
而对于冒泡排序而言，其思想是，对于给定的待排序数列，其处理是，假如是需要将数列排序成从小到大的顺序，那么循环第一趟，将最小的数值放在数列第一位，第二趟是将次小的数值放在数列第二位，以此类推，但是其将数值依次冒泡上来的路径上并不是第一次就能找到最小值，所以一开始可能会将局部最小值挪动，但最终的目的还是不变的，是要将小数值冒上去。
八、多态性
九、pv操作
对于信号量，可以认为是一个仓库，有两个概念，容量和当前的货物个数。
P操作从仓库拿货，如果仓库中没有货，线程一直等待，直到V操作，往仓库里添加了货物，为了避免P操作一直等待下去，会有一个超时时间。
V操作往仓库送货，如果仓库满了，线程等待，直到有P操作，从仓库中拿走货物，有空的位置。
创建信号量，设置容量，先有V操作，才能P操作。
P操作：货物个数减1，减过之后，货物个数大于等于0，说明已经拿到货物，线程继续。否者线程阻塞。
V操作：货物个数加1，加过之后，货物个数小于等于容量，说明添加成功，线程继续。否者线程阻塞。
信号量：0≤ 信号量≤容量 ，取值 表示当前可以使用的货物；
信号量<0 ， 取值 表示当前等待使用货物的线程；
信号量>容量 ， 信号量-容量 表示当前等待添加货物的线程。
通常，信号量的容量设置很大，可以一直V操作，不会阻塞，但是P操作的时候，很可能阻塞。
当容量为1，也就是互斥，执行流程必定是V操作，P操作，V操作，P操作...
信号量如何做到线程同步？
可以认为信号量关联一组线程，保存一个指针，指向线程数组的首地址。比如当前信号量为-1，进行P操作，信号量为-2，说明没有拿到货物，线程等待，取值为-2，说明有两个线程等待那货物。这个时候，其他线程进行V操作，信号量加1，为-1，信号量通知等待的线程中，第一个线程继续执行，第二个线程继续等待。
也就是说，P操作等待的情况是减1后，信号量小于0。 P操作继续执行的情况有两种：a、减1后，信号量大于等于0，不需等待，直接执行；b、信号量小于0，等待中，其他人进行了V操作，通知这个线程，继续执行。
项目中的使用场景：
客户端使用提供的SDk与服务交互，为了提高效率，客户端发送一个请求后，SDK异步回调给客户端。但是，有些请求，客户端希望同步，等待回复。这个时候，建立一个map，以req的sequence为key，value为信号量的指针，信号量的容量设置为1，可用的货物为0，对信号量进行TimeoutP操作，货物个数为-1，阻塞在这里。异步回调，收到回复的sequence，根据map找到信号量指针，进行V操作，货物个数为0，通知前面TimeoutP的线程继续执行下去，这个时候，TimeoutP的线程，把回复消息取出来，返回给客户端。
十、路由器，交换器
十一、进程模块pcb
十二、堆，栈区别。
一、预备知识—程序的内存分配
一个由C/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap）
— 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后由系统释放。
4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。
二、例子程序
这是一个前辈写的，非常详细
//main.cpp
int a =
0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[]
= "abc"; 栈
char *p2; 栈
char *p3
= "123456"; 123456/0在常量区，p3在栈上。
static int
c =0； 全局（静态）初始化区
p1 =
(char *)malloc(10);
p2 =
(char *)malloc(20);
分配得来得10和20字节的区域就在堆区。
strcpy(p1,
"123456"); 123456/0放在常量区，编译器可能会将它与p3所指向的"123456"
优化成一个地方。
}
二、堆和栈的理论知识
2.1申请方式
stack:
由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间heap:
需要程序员自己申请，并指明大小，在c中malloc函数
如p1 = (char
*)malloc(10);
在C++中用new运算符
如p2 = new
char[10];
但是注意p1、p2本身是在栈中的。
2.2
申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时， 会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。
2.3申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
2.4申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一块内存，虽然用起来最不方便。但是速度快，也最灵活。
2.5堆和栈中的存储内容
栈：在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可
执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。
2.6存取效率的比较
char s1[]
= "aaaaaaaaaaaaaaa";
char *s2
= "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的；
而bbbbbbbbbbb是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
比如：
#include
void main()
{
char a
= 1;
char c[]
= "1234567890";
char *p
="1234567890";
a =
c[1];
a =
p[1];
return;
}
2.7小结：
堆和栈的区别可以用如下的比喻来看出：
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就
走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是*度小。
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且*度大。 (经典！)