康瑞部落

操作系统

推荐教程：http://c.biancheng.net/cpp/u/xitong/

1. 进程的有哪几种状态，状态转换图，及导致转换的事件。

如上图所示，进程包括三种状态：就绪态、运行态和阻塞态。详细说明如下：
注意：创建和退出不是进程的状态。阻塞和就绪的区别：阻塞是等待除CPU以外的资源，而就绪等待的是CPU资源。
1）就绪——执行：对就绪状态的进程，当进程调度程序按一种选定的策略从中选中一个就绪进程，为之分配了处理机后，该进程便由就绪状态变为执行状态；
2）执行——阻塞：正在执行的进程因发生某等待事件而无法执行，则进程由执行状态变为阻塞状态，如进程提出输入/输出请求而变成等待外部设备传输信息的状态，进程申请资源（主存空间或外部设备）得不到满足时变成等待资源状态，进程运行中出现了故障（程序出错或主存储器读写错等）变成等待干预状态等等； 
3）阻塞——就绪：处于阻塞状态的进程，在其等待的事件已经发生，如输入/输出完成，资源得到满足或错误处理完毕时，处于等待状态的进程并不马上转入执行状态，而是先转入就绪状态，然后再由系统进程调度程序在适当的时候将该进程转为执行状态；
4）执行——就绪：正在执行的进程，因时间片用完而被暂停执行，或在采用抢先式优先级调度算法的系统中,当有更高优先级的进程要运行而被迫让出处理机时，该进程便由执行状态转变为就绪状态。

2. 进程与线程的区别。

一、定义
进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位。

线程是进程的一个实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈)，但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。

二、关系
一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行。

相对进程而言，线程是一个更加接近于执行体的概念，它可以与同进程中的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。

三、区别
进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

1) 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.

2) 线程的划分尺度小于进程，使得多线程程序的并发性高。

3) 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

4) 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。

5) 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

四、优缺点
线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源的管理和保护；而进程正相反。同时，线程适合于在SMP机器上运行，而进程则可以跨机器迁移。

3. 进程通信的几种方式。

1）普通管道(pipe)：管道是一种单工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系或者兄弟进程之间。

2）流管道(s_pipe)：一种半双工的通信方式，可以双向传输。

3）有名管道(named pipe)：有名管道也是半双工的通信方式，但是它允许无亲缘关系的进程间的通信。

4）信号量(semophore)：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

5）消息队列(message queue)：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓存区大小受限等缺点。

6）信号(signal)：信号是一种比较复杂的通信方式，用于通知接受进程某个事件已经发生。

7）共享内存(shared memory)：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量配合使用，来实现进程间的同步和通信。

8）套接字(socket)：套接字也是一种进程间通信的机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

4. 线程同步几种方式。(一定要会写生产者、消费者问题，完全消化理解)

线程间的同步方法大体可分为两类：用户模式和内核模式。顾名思义，内核模式就是指利用系统内核对象的单一性来进行同步，使用时需要切换内核态与用户态，而用户模式就是不需要切换到内核态，只在用户态完成操作。

用户模式下的方法有：原子操作（例如一个单一的全局变量），临界区。

内核模式下的方法有：事件，信号量，互斥量。

http://www.cppblog.com/suiaiguo/archive/2009/07/24/91045.html

5. 线程的实现方式. (也就是用户线程与内核线程的区别)

java中的线程实现方式：http://www.imyukin.com/?p=263

1）内核级线程:切换由内核控制，当线程进行切换的时候，由用户态转化为内核态。切换完毕要从内核态返回用户态；可以很好的利用smp，即利用多核cpu。windows线程就是这样的。

2）用户级线程内核的切换由用户态程序自己控制内核切换,不需要内核干涉，少了进出内核态的消耗，但不能很好的利用多核Cpu,目前Linux pthread大体是这么做的。

线程的实现可以分为两类：用户级线程(User-Level Thread)和内核线线程(Kernel-Level Thread)，后者又称为内核支持的线程或轻量级进程。在多线程操作系统中，各个系统的实现方式并不相同，在有的系统中实现了用户级线程，有的系统中实现了内核级线程。

用户线程指不需要内核支持而在用户程序中实现的线程，其不依赖于操作系统核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。不需要用户态/核心态切换，速度快，操作系统内核不知道多线程的存在，因此一个线程阻塞将使得整个进程（包括它的所有线程）阻塞。由于这里的处理器时间片分配是以进程为基本单位，所以每个线程执行的时间相对减少。

内核线程：由操作系统内核创建和撤销。内核维护进程及线程的上下文信息以及线程切换。一个内核线程由于I/O操作而阻塞，不会影响其它线程的运行。Windows NT和2000/XP支持内核线程。

用户线程运行在一个中间系统上面。目前中间系统实现的方式有两种，即运行时系统（Runtime System）和内核控制线程。“运行时系统”实质上是用于管理和控制线程的函数集合，包括创建、撤销、线程的同步和通信的函数以及调度的函数。这些函数都驻留在用户空间作为用户线程和内核之间的接口。用户线程不能使用系统调用，而是当线程需要系统资源时，将请求传送给运行时，由后者通过相应的系统调用来获取系统资源。内核控制线程：系统在分给进程几个轻型进程（LWP），LWP可以通过系统调用来获得内核提供的服务，而进程中的用户线程可通过复用来关联到LWP，从而得到内核的服务。

以下是用户级线程和内核级线程的区别：

（1）内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的。

（2）用户级线程的创建、撤消和调度不需要OS内核的支持，是在语言（如Java）这一级处理的；而内核支持线程的创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。

（3）用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断。

（4）在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。

（5）用户级线程的程序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序。

内核线程的优点：

（1）当有多个处理机时，一个进程的多个线程可以同时执行。

缺点：

（1）由内核进行调度。

用户进程的优点：

（1） 线程的调度不需要内核直接参与，控制简单。

（2） 可以在不支持线程的操作系统中实现。

（3） 创建和销毁线程、线程切换代价等线程管理的代价比内核线程少得多。

（4） 允许每个进程定制自己的调度算法，线程管理比较灵活。

（5） 线程能够利用的表空间和堆栈空间比内核级线程多。

（6） 同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起。另外，页面失效也会产生同样的问题。

缺点：

（1）资源调度按照进程进行，多个处理机下，同一个进程中的线程只能在同一个处理机下分时复用

6. 用户态和核心态的区别。

  内核态与用户态是操作系统的两种运行级别，intel cpu提供Ring0-Ring3三种级别的运行模式。Ring0级别最高，Ring3最低。其中特权级0（Ring0）是留给操作系统代码，设备驱动程序代码使用的，它们工作于系统核心态；而特权极3（Ring3）则给普通的用户程序使用，它们工作在用户态。运行于处理器核心态的代码不受任何的限制，可以自由地访问任何有效地址，进行直接端口访问。而运行于用户态的代码则要受到处理器的诸多检查，它们只能访问映射其地址空间的页表项中规定的在用户态下可访问页面的虚拟地址，且只能对任务状态段（TSS）中I/O许可位图（I/O Permission Bitmap）中规定的可访问端口进行直接访问（此时处理器状态和控制标志寄存器EFLAGS中的IOPL通常为0，指明当前可以进行直接I/O的最低特权级别是Ring0）。以上的讨论只限于保护模式操作系统，象DOS这种模式操作系统则没有这些概念，其中的所有代码都可被看作运行在核心态。
　　当一个任务(进程)执行系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态(或简称为内核态)。此时处理器处于特权级最高的(0级) 内核代码中执行。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。当进程在执行用户自己的代码时，则称其处于用户运行态(用户态)。即此时处理器在特权级最低的(3级)用户代码中运行。
　　在内核态下CPU可执行任何指令，在用户态下CPU只能执行非特权指令。当CPU处于内核态，可以随意进入用户态；而当CPU处于用户态时，用户从用户态切换到内核态只有在系统调用和中断两种情况下发生，一般程序一开始都是运行于用户态，当程序需要使用系统资源时，就必须通过调用软中断进入内核态。
　　Linux使用了Ring3级别运行用户态，Ring0作为内核态，没有使用Ring1和Ring2。Ring3状态不能访问Ring0的地址空间，包括代码和数据。Linux进程的4GB地址空间，3G-4G部分大家是共享的，是内核态的地址空间，这里存放在整个内核的代码和所有的内核模块，以及内核所维护的数据。用户运行一个程序，该程序所创建的进程开始是运行在用户态的，如果要执行文件操作，网络数据发送等操作，必须通过 write，send等系统调用，这些系统调用会调用内核中的代码来完成操作，这时，必须切换到Ring0，然后进入3GB-4GB中的内核地址空间去执行这些代码完成操作，完成后，切换回Ring3，回到用户态。这样，用户态的程序就不能随意操作内核地址空间，具有一定的安全保护作用。
处理器模式从Ring3向Ring0的切换发生在控制权转移时，有以下两种情况：访问调用门的长转移指令CALL，访问中断门或陷阱门的INT指令。具体的转移细节由于涉及复杂的保护检查和堆栈切换，不再赘述，请参阅相关资料。现代的操作系统通常使用中断门来提供系统服务，通过执行一条陷入指令来完成模式切换，在INTEL X86上这条指令是INT，如在WIN9X下是INT30（保护模式回调），在LINUX下是INT80，在WINNT/2000下是INT2E。用户模式的服务程序（如系统DLL）通过执行一个INTXX来请求系统服务，然后处理器模式将切换到核心态，工作于核心态的相应的系统代码将服务于此次请求并将结果传给用户程序。
 
一，中断处理过程

硬件中断：来自时钟，外设

可编程中断：programmed interrupt，执行引起软件中断的指令。

例外中断：如页面错。

都由系统负责处理。当发生一个中断时，如果CPU正在比该中断级低的处理机运行级上运行，它就在解码下条指令之前，接受该中断，并提高处理机运行级。内核处理中断的操作顺序如下：

1，对于正在进行的进程，保存其当前寄存器上下文，并创建压入一个新的上下文层。

2，确定中断源，识别中断类型。如是时钟或磁盘的。

3，查找中断向量。当系统接受一个中断时，它从机器中得到一个数，系统把这个作为查表的偏移量。这个表通常成为中断向量（interrupt vector）。中断向量的内容包括各种中断源的中断处理程序的地址，以及中断处理程序取得参数的方式。

4，内核调用中断处理程序。

5，中断处理程序执行那个返回，恢复（弹出）前一上下文层。

二，软中断

软中断通知进程发生了异步事件。

系统有个进程表，每个进程在进程表中有有个进程表项，每个进程表项有个软中断信号字段，纪录发向一个进程的所有未处理的软中断信号。

当一个进程即将从核心态返回到用户态时，或它要进入或离开一个适当的低调度优先级时，内核要检查它是否收到了一个软中断信号。

内核仅当一个进程从核心态返回到用户态时才处理软中断信号。

三，系统调用

我们在C程序中调用系统调用好像是个一般的函数调用，当实际上调用系统调用会引起用户态到核心态的状态变化，这是怎么做到的呢？

原来，C编译程序采用一个预定义的函数库（C之程序库），其中的函数具有系统调用的名字，从而解决了在用户程序中请求系统调用的问题。这些库函数一般都执行一条指令，该指令将进程的运行方式变为核心态，然后，使内核开始为系统调用执行代码。我们称这个指令为操作系统陷入（operating system trap）。

系统调用的接口是一个中断处理程序的特例。

在处理操作系统陷入时，

1，内核根据系统调用号查系统调用入口表，找到相应的内核子程序的地址。

2，内核还要确定该系统调用所要求的参数个数。

3，从用户地址空间拷贝参数到U区（Unix V）。

4，保存当前上下文，执行系统调用代码。

核心态：当CPU正在运行内核代码时（内核代码是共享的）。

用户态：当CPU正在运行用户代码时。

用户模式：不可以访问内核空间（>=0x80000000)

内核模式：可以访问任何有效虚拟地址，包括内核空间。一个线程可以访问其他任何线程地址空间。

7. 用户栈和内核栈的区别。

1）进程的堆栈

    内核在创建进程的时候，在创建task_struct的同时，会为进程创建相应的堆栈。每个进程会有两个栈，一个用户栈，存在于用户空间，一个内核栈，存在于内核空间。当进程在用户空间运行时，cpu堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；当进程在内核空间时，cpu堆栈指针寄存器里面的内容是内核栈空间地址，使用内核栈。

2）进程用户栈和内核栈的切换

    当进程因为中断或者系统调用而陷入内核态之行时，进程所使用的堆栈也要从用户栈转到内核栈。

    进程陷入内核态后，先把用户态堆栈的地址保存在内核栈之中，然后设置堆栈指针寄存器的内容为内核栈的地址，这样就完成了用户栈向内核栈的转换；当进程从内核态恢复到用户态之行时，在内核态之行的最后将保存在内核栈里面的用户栈的地址恢复到堆栈指针寄存器即可。这样就实现了内核栈和用户栈的互转。

    那么，我们知道从内核转到用户态时用户栈的地址是在陷入内核的时候保存在内核栈里面的，但是在陷入内核的时候，我们是如何知道内核栈的地址的呢？

    关键在进程从用户态转到内核态的时候，进程的内核栈总是空的。这是因为，当进程在用户态运行时，使用的是用户栈，当进程陷入到内核态时，内核栈保存进程在内核态运行的相关信心，但是一旦进程返回到用户态后，内核栈中保存的信息无效，会全部恢复，因此每次进程从用户态陷入内核的时候得到的内核栈都是空的。所以在进程陷入内核的时候，直接把内核栈的栈顶地址给堆栈指针寄存器就可以了。

8. 内存池、进程池、线程池。(c++程序员必须掌握)

内存池

平常我们使用new、malloc在堆区申请一块内存，但由于每次申请的内存大小不一样就会产生很多内存碎片，造成不好管理与浪费的情况

内存池则是在真正使用内存之前，先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。这样做的一个显著优点是尽量避免了内存碎片，使得内存分配效率得到提升。

进程池&&线程池

这两个问题有一定的相似度，在面向对象程序编程中，对象的创建与析构都是一个较为复杂的过程，较费时间，所以为了提高程序的运行效率尽可能减少创建和销毁对象的次数，特别是一些很耗资源的对象创建和销毁。

所以我们可以创建一个进程池（线程池）,预先放一些进程（线程）进去,要用的时候就直接调用,用完之后再把进程归还给进程池,省下创建删除进程的时间,不过当然就需要额外的开销了利用线程池与进程池可以是管理进程与线程的工作交给系统管理，不需要程序员对立面的线程、进程进行管理

线程池主要用于：

1、需要大量的线程来完成任务，且完成任务的时间比较短。 WEB服务器完成网页请求这样的任务，使用线程池技术是非常合适的。因为单个任务小，而任务数量巨大，你可以想象一个热门网站的点击次数。但对于长时间的任务，比如一个Telnet连接请求，线程池的优点就不明显了。因为Telnet会话时间比线程的创建时间大多了。

2、对性能要求苛刻的应用，比如要求服务器迅速响应客户请求。

3、接受突发性的大量请求，但不至于使服务器因此产生大量线程的应用。突发性大量客户请求，在没有线程池情况下，将产生大量线程，虽然理论上大部分操作系统线程数目最大值不是问题，短时间内产生大量线程可能使内存到达极限，并出现"OutOfMemory"的错误。

9. 死锁的概念，导致死锁的原因.

死锁概念：操作系统中的死锁被定义为系统中两个或者多个进程无限期地等待永远不会发生的条件，系统处于停滞状态，这就是死锁。

产生死锁的原因主要是：
（1）因为系统资源不足。
（2）进程运行推进的顺序不合适。
（3）资源分配不当等。

如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。

10. 导致死锁的四个必要条件。

产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

11. 处理死锁的四个方式。

目前处理死锁的方法可归结为以下四种：　　

1)预防死锁。

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

   I   资源一次性分配：（破坏请求和保持条件）
   II  可剥夺资源：即当某进程新的资源未满足时，释放已占有的资源（破坏不可剥夺条件）
   III 资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）

2)避免死锁。

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

3)检测死锁。

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

4)解除死锁。

这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

   I  剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；
   II 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止；
所谓代价是指优先级、运行代价、进程的重要性和价值等。

12. 预防死锁的方法、避免死锁的方法。

13. 进程调度算法。(周转时间 =  程序结束时间 -- 开始服务时间、带权周转时间=  周转时间 /  要求服务时间)

（1）先来先服务

（2）短进程优先

（3）高优先权调度算法（抢占式，非抢占式）

（4）高响应比优先

（5）时间片轮转

（6）多级反馈队列调度

http://www.iteblog.com/archives/251

14. Windows内存管理的方式(块式、页式、段式、段页式).

页式：

用户程序的逻辑地址空间被划分成若干固定大小的区域，称为“页”或者“页面”，相应地，内存物理空间也分成相对应的若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。

段式：

将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

段页式：

分页系统能有效地提高内存的利用率，而分段系统能反映程序的逻辑结构，便于段的共享与保护，将分页与分段两种存储方式结合起来，就形成了段页式存储管理方式。

在段页式存储管理系统中，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于主存空间也分成大小相等的页，主存的分配以页为单位。

15. 内存连续分配方式采用的几种算法及各自优劣。

连续分配方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。

单一连续分配

内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。

这种方式的优点是简单、无外部碎片，可以釆用覆盖技术，不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。

固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区，如此循环。

动态分区分配

动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分区方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。

http://c.biancheng.net/cpp/html/2610.html

16. 动态链接及静态链接.

静态链接就是在生成可执行文件的时候，把所有需要的函数的二进制代码都包含到可执行文件中去。

动态链接就是在运行的时候再去链接

http://blog.csdn.net/jewes/article/details/8765745

17. 基本分页、请求分页储存管理方式。

基本分页储存管理方式具有如下特征：

1) 一次性。要求将作业全部装入内存后方能运行。许多作业在每次运行时，并非其全部程序和数据都要用到。如果一次性地装入其全部程序，造成内存空间的浪费。

2) 驻留性。作业装入内存后，便一直驻留在内存中，直至作业运行结束。尽管运行中的进程会因I/O而长期等待，或有的程序模块在运行过一次后就不再需要(运行)了，但它们都仍将继续占用宝贵的内存资源。

请求分页储存管理是实现虚拟存储器的一种常用方式，它是在基本分页储存管理的基础上实现的。其基本思想是：在进程开始运行之前，仅装入当前要执行的部分页面即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的页面；当内存空间已满，而又需要装入新的页面时，者根据置换功能适当调出某个页面，以便腾出空间而装入新的页面。为实现请求分页，需要一定的硬件支持，包括：页表机制、缺页中断机构、地址变换机构。

18. 基本分段、请求分段储存管理方式。

19. 分段分页方式的比较各自优缺点。

1、页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。

段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要。

2、页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。

段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。

3、分页的作业地址空间是维一的，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。

分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

20. 几种页面置换算法，会算所需换页数。(LRU用程序如何实现？)

http://c.biancheng.net/cpp/html/2614.html

1.最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

2.先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

3.最近最久未使用(LRU)置换算法

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

4.时钟(CLOCK)置换算法

LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。
简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。
CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一：

最近未被访问，也未被修改(u=0, m=0)。

最近被访问，但未被修改(u=1, m=0)。

最近未被访问，但被修改(u=0, m=1)。

最近被访问，被修改(u=1, m=1)。

算法执行如下操作步骤：

1)从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。

2)如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。

3)如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。

改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。

21. 虚拟内存的定义及实现方式。

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（对用户完全透明），给用户的感觉是好像存在一个比实际物理内存大得多的存储器。虚拟存储器的大小由计算机的地址结构决定，并非是内存和外存的简单相加。虚拟存储器有以下三个主要特征：

多次性，是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。

对换性，是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。

虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量，远大于实际的内存容量。

实现方式：

请求分页存储管理。

请求分段存储管理。

请求段页式存储管理。

22. 操作系统的四个特性。

操作系统的4个特征是并发性、共享性、虚拟性和不确定性。
并发性（concurrency）：指在计算机系统中存在着许多并发执行的活动。对计算机系统而言，并发是指宏观上看系统内有多道程序同时运行，微观上看是串行运行。因为在大多数计算机系统中一般只有一个CPU，在任意时刻只能有一道程序占用CPU。
共享性（sharing）：系统中各个并发活动要共享计算机系统中的各种软、硬件资源，因此操作系统必须解决在多道程序间合理地分配和使用资源问题。
虚拟性（virtual）：虚拟是操作系统中的重要特征，所谓虚拟是指把物理上的一台设备变成逻辑上的多台设备。例如，在操作系统中采用了spooling技术，可以利用快速、大容量可共享的磁盘作为中介，模拟多个非共享的低速的输入输出设备，这样的设备称为虚拟设备。
不确定性（non-determinacy）：通常一个程序的初始条件相同时，无论何时运行结果必然相同。但由于程序的并发执行系统内的各种进程错综复杂，与这些进程有关的事件，如：从外部设备来的中断、输入输出请求、各种运行故障等，发生的时间都不可预测，如果处理不当将导致系统出错，这种不确定性所带来错误是很难查找的。

操作系统的五大管理功能是进程管理、文件管理、存储管理、设备管理和作业管理。

23. DMA。

Direct Memory Access（存储器直接访问）。这是指一种高速的数据传输操作，允许在外部设备和存储器之间直接读写数据，既不通过CPU，也不需要CPU干预。整个数据传输操作在一个称为"DMA控制器"的控制下进行的。CPU除了在数据传输开始和结束时做一点处理外，在传输过程中CPU可以进行其他的工作。这样，在大部分时间里，CPU和输入输出都处于并行操作。因此，使整个计算机系统的效率大大提高

24. Spooling。

为了缓和CPU的高速性与I/O设备低速性之间的矛盾而引入了脱机输入/输出技术。该 技术是利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上；或者相反。 SPOOLing的意思是外部设备同时联机操作，又称为假脱机输入/输出操作，是操作系统中釆 用的一项将独占设备改造成共享设备的技术。

SPOOLing系统组成如图5-11所示。

输入井和输出井

在磁盘上开辟出的两个存储区域。输入井模拟脱机输入时的磁盘，用于收容I/O设备输 入的数据。输出井模拟脱机输出时的磁盘，用于收容用户程序的输出数据。

图5-11  SPOOLing系统的组成

输入缓冲区和输出缓冲区

在内存中开辟的两个缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再传送 到输入井。输出缓冲区用于暂存从输出井送来的数据，以后再传送到输出设备。

输入进程和输出进程

输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再 送到输入井。当CPU需要输入数据时，直接将数据从输入井读入内存。输出进程模拟脱机 输出时的外围控制机，把用户要求输出的数据先从内存送到输出并，待输出设备空闲时，再 将输出井中的数据经过输出缓冲区送到输出设备。

共享打印机是使用SPOOLing技术的一个实例，这项技术已被广泛地用于多用户系统和 局域网络中。当用户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正 立即把打印机分配给该用户进程，而只为它做两件事：

• 由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中。

• 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入 其中，再将该表挂到请求打印队列上。

SPOOLing系统的主要特点有：提高了 I/O的速度；将独占设备改造为共享设备；实现 了虚拟设备功能。

25. 外存分配的几种方式，及各种优劣。

外存分配方式主要有这几种：连续分配，链式分配，索引分配。

一. 连续分配

原理：创建文件时，分配一组连续的块；FAT（文档分配表）中每个文件只要一项，说明起始块和文件长度。对于顺序文件有利。

优点：1.简便。适用于一次性写入操作。2.支持顺序存取和随机存取，顺序存取速度快。3.所需的磁盘寻道次数和寻道时间最少。（因为空间的连续性，当访问下一个磁盘块时，一般无需移动磁头，当需要移动磁头时，只需要移动一个磁道。）

缺点：1.文件不能动态增长。（可能文件末尾处的空块已经分配给了别的文件。）2.不利于文件的插入和删除。3.外部碎片问题。（反复增删文件后，很难找到空间大小足够的连续块，需要进行紧缩。）4.在创建文件时需生命文件大小。

如图： 

二. 链式分配

原理：一个文件的信息存放在若干个不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。fat中每个文件同样只需要一项，包括文件名、起始块号和最后块号。任何一个自由块都可以加入到链中。

优点：1.提高磁盘的空间利用率，不存在外部碎片问题。2.有利于文件的插入和删除。3.有利于文件的动态扩充。

缺点：1.存取速度慢，一般只适用于信息的顺序存取，不适于随机存取。2.查找某一块必须从头到尾沿着指针进行。3.可靠性问题，如指针出错。4.更多的寻道次数和寻道时间。5.链接指针占一定的空间，将多个块组成簇，按簇进行分配而不是按块进行分配。（增加了磁盘碎片）

如图：

使用FAT文件分配表法，链接分配的变种，如MS-DOS 和 OS/2.

三. 索引分配

原理：每个文件在FAT中有一个一级索引，索引包含分配给文件的每个分区的入口。文件的索引保存在单独的一个块中，FAT中该文件的入口指向这一块。

优点：1.保持了链接结构的优点，又解决了其缺点：按快分配可以消除外部碎片。按大小可改变的分区分配可以提高局部性。索引分配支持顺序访问文件和直接访问文件，是普遍采用的一种方式。2.满足了文件动态增长，插入删除的要求。（只要有空闲块）3.能充分利用外存空间。

缺点：1.较多的寻道次数和寻道空间。2.索引表本身带来了系统开销，如：内外存空间、存取时间。

计算机网络

1. 电路交换与分组交换的区别？优劣对比。

2. OSI有哪几层，会画出来，知道主要几层的各自作用。

3. TCP/IP有哪几层，会画出来，知道所有层数的作用，会列举各层主要的协议名称。

4. 硬件(MAC)地址的概念及作用。

5. ARP协议的用途 及算法、在哪一层上会使用arp ？

6. CRC冗余校验算法，反码和检验算法。

7. 如何实现透明传输。

8. 知道各个层使用的是哪个数据交换设备。（交换机、路由器、网关）

9. 路由表的内容。

10. 分组转发算法。

11. IP报文的格式，格式的各个字段的含义要理解。

12.MTU的概念，啥叫路径MTU？ MTU发现机制，TraceRoute(了解)。

13.RIP协议的概念及算法。

14.ICMP协议的主要功能。

15.组播和广播的概念，IGMP的用途。(环回地址、广播地址)

16.Ping协议的实现原理，ping 命令格式。

17. 子网划分的概念，子网掩码。

18. IP地址的分类，如何划分的，及会计算各类地址支持的主机数。

19.DNS的概念，用途，DNS查询的实现算法。

20. TCP与UDP的概念，相互的区别及优劣。

21.UDP报文的格式，字段的意义。

22. TCP 报文的格式，字段的意义。

23.TCP通过哪些措施，保证传输可靠？

24. 三次握手，四次断开过程。

25. TIME_WAIT状态的概念及意义。

26.滑动窗口协议 与停止等待协议的区别。

27. TCP的流量控制和拥塞控制实现原理(会画拥塞控制的典型图)。

28.TCP的快速重传与快速恢复算法。

29.TFTP 与 FTP的区别。

30.阻塞方式和非阻塞方式，阻塞connect与非阻塞connect。(比较难，有兴趣可以了解)

31. HTTP基本格式。（java程序员必须掌握）

设计模式

1. 各种常用模式的用途，使用方法(类图)。

2. 单例模式的双重检查实现。

3. MVC模式

转自：http://blog.csdn.net/troy__/article/details/39609143