1. 进程的有哪几种状态，状态转换图，及导致转换的事件。
（1）分别说明引起状态转换1、2、3、4的原因，并各举一个事件。
（2）为什么在转换图中没有就绪到阻塞和阻塞到运行的转换方向？
答： （1）
1：就绪->执行， 当前运行进程阻塞，调度程序选一个优先权最高的进程占有处理机；
2：执行->就绪， 当前运行进程时间片用完；
3：执行->阻塞，当前运行进程等待键盘输入，进入了睡眠状态。
4：阻塞->就绪，I/O操作完成，被中断处理程序唤醒。
（2）就绪进程没有占有处理机，也即没有经过运行，其状态就不会改变。
阻塞状态进程唤醒后先要进入就绪队列，才会被调度程序选中，进入了执行状态。
2. 进程与线程的区别。
进程是操作系统资源分配的单位，线程是操作系统执行的单位。
线程是为了提高操作系统的并发性而引入的，而且线程的创建，销毁及调度的开销一般都远小于进程。
一个进程可以包含多个共享该进程的资源的线程，同一进程内的线程间的通信是很容易实现的。
3. 进程通信（IPC）的几种方式。
- 管道（Pipe）及有名管道（named pipe）：管道可用于具有亲缘关系进程间的通信，有名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信；
- 信号（Signal）：信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；linux除了支持Unix早期信号语义函数sigal外，还支持语义符合Posix.1标准的信号函数sigaction（实际上，该函数是基于BSD的，BSD为了实现可靠信号机制，又能够统一对外接口，用sigaction函数重新实现了signal函数）；
- 报文（Message）队列（消息队列）：消息队列是消息的链接表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。
- 共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。
- 信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。
- 套接口（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的，但现在一般可以移植到其它类Unix系统上：Linux和System V的变种都支持套接字。
通信/同步/并发可以等价来看。
管道(pipe, FIFO)、消息(message queue)、共享存储区和套接字(socket)提供了进程间传递数据的方法，
而信号量（semaphore）和信号(signal)则用于其他进程的触发行为。
4. 线程同步几种方式。(一定要会写生产者、消费者问题，完全消化理解)
1.互斥量（mutex）:确保同一时刻只有一个线程访问数据。
本质是一把锁，在访问共享资源前对互斥量进行加锁，在访问完后释放互斥量上的锁。
对互斥量进行加锁以后，任何其他试图再次对互斥量加锁的线程将会被阻塞直到当前线程释放该互斥锁。
两种状态：锁住状态，不加锁。一次只有一个线程对其加锁。
2.读写锁：又叫共享-独占锁，读时共享，写时独占。
三种状态：读模式下加锁，写模式下加锁，不加锁。
1）.当读写锁以写模式锁住时，在这个锁被解锁之前，所有试图对这个锁加锁的线程都会被阻塞。
2）.当读写锁以读模式锁住时，它是以共享模式锁住的，此时所有试图以读模式对它进行加锁的线程都可以得到访问权，但若线程希望以写模式对此锁加锁，它必须阻塞直到所有的线程释放读锁。
3.条件变量（condition）：
与互斥锁不同，条件变量是用来等待而不是用来上锁的。
条件变量用来自动阻塞一个线程，直到某特殊情况发生为止。通常条件变量和互斥锁同时使用。条件变量分为两部分: 条件和变量。条件本身是由互斥量保护的。线程在改变条件状态前先要锁住互斥量。条件变量使我们可以睡眠等待某种条件出现。条件变量是利用线程间共享的全局变量进行同步的一种机制，主要包括两个动作：一个线程等待"条件变量的条件成立"而挂起；另一个线程使"条件成立"（给出条件成立信号）。
4.信号量（Semaphore）:
信号灯与互斥锁和条件变量的主要不同在于"灯"的概念，灯亮则意味着资源可用，灯灭则意味着不可用。如果说后两中同步方式侧重于"等待"操作，即资源不可用的话，信号灯机制则侧重于点灯，即告知资源可用；没有等待线程的解锁或激发条件都是没有意义的，而没有等待灯亮的线程的点灯操作则有效，且能保持灯亮状态。当然，这样的操作原语也意味着更多的开销。
信号灯的应用除了灯亮/灯灭这种二元灯以外，也可以采用大于1的灯数，以表示资源数大于1，这时可以称之为多元灯。
条件变量与互斥锁、信号量的区别
1）.互斥锁必须总是由给它上锁的线程解锁，信号量的挂出即不必由执行过它的等待操作的同一进程执行。一个线程可以等待某个给定信号灯，而另一个线程可以挂出该信号灯。
2）.互斥锁要么锁住，要么被解开（二值状态，类型二值信号量）
3）.由于信号量有一个与之关联的状态（它的计数值），信号量挂出操作总是被记住。然而当向一个条件变量发送信号时，如果没有线程等待在该条件变量上，那么该信号将丢失。
4）.互斥锁是为了上锁而设计的，条件变量是为了等待而设计的，信号灯即可用于上锁，也可用于等待，因而可能导致更多的开销和更高的复杂性。
生产者-消费者问题，线程同步（数据一致性）问题
#include <stdio.h>
#include <pthread.h>
#define MAX 10 //需要生产的数量
pthread_mutex_t the_mutex;
pthread_cond_t condc, condp;
int buffer = 0;//生产者、消费者使用的缓冲区
void *producer(void *ptr)
{
int i;
for(i=1; i<=MAX; i++)
{
pthread_mutex_lock(&the_mutex); //互斥使用缓冲区
while(buffer !=0) pthread_cond_wait(&condp, &the_mutex);
printf("procucer produce item %d\n",i);
buffer = i; //将数据插入缓冲区
pthread_cond_signal(&condc);//唤醒消费者
pthread_mutex_unlock(&the_mutex);//释放缓冲区
}
pthread_exit(0);
}
void *consumer(void *ptr)
{
int i;
for(i=1; i<=MAX; i++)
{
pthread_mutex_lock(&the_mutex);//互斥使用缓冲区
while(buffer ==0) pthread_cond_wait(&condc, &the_mutex);
printf("consumer consume item %d\n",i);
buffer = 0;//从缓冲区中取出数据
pthread_cond_signal(&condp);//唤醒生产者
pthread_mutex_unlock(&the_mutex);//释放缓冲区
}
pthread_exit(0);
}
int main(int argc, char *argv[])
{
pthread_t pro, con;
pthread_mutex_init(&the_mutex, 0);
pthread_cond_init(&condc,0);
pthread_cond_init(&condp,0);
pthread_create(&con, 0, consumer, 0);
pthread_create(&pro, 0, producer, 0);
pthread_join(pro,0);
pthread_join(con,0);
pthread_cond_destroy(&condc);
pthread_cond_destroy(&condp);
pthread_mutex_destroy(&the_mutex);
return 0;
}
5. 线程的实现方式. (也就是用户线程与内核线程的区别)两种。
用户级线程：
内核级线程：
1、在用户空间中实现线程
（1）特点：内核对线程包一无所知。从内核角度考虑，就是按正常的方式管理，即单线程进程（存在运行时系统）
（2）优点：
1.用户级线程包可以在不支持线程的操作系统上实现
2.保存线程状态的过程和调用程序都只是本地过程，故启动它们比进程内核调用效率更高，
3.不需要陷阱，不需要上下文切换，也不需要对内存高速缓存进行刷新，使得线程调用非常快捷
（3）缺点：
线程发生I/O或页面故障引起的阻塞时，如果调用阻塞系统调用则内核由于不知道有多线程的存在，而会阻塞整个进程从而阻塞所有线程
一个单独的进程内部，没有时钟中断，所以不可能用轮转调度的方式调度线程
2、在内核中实现线程
（1）特点：
当某个线程希望创建一个新线程或撤销一个已有线程时，它进行一个系统调用
（2）优点：
所有能够阻塞线程的调用都以系统调用的形式实现，代价可观
当一个线程阻塞时，内核根据选择可以运行另一个进程的线程，而用户空间实现的线程中，运行时系统始终运行自己进程中的线程
说明：由于内核创建线程代价大，故有线程回收
6. 用户态和核心态的区别。
当一个任务（进程）执行系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态（或简称为内核态）。此时处理器处于特权级最高的（0级）内核代码中执行。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。
当进程在执行用户自己的代码时，则称其处于用户运行态（用户态）。即此时处理器在特权级最低的（3级）用户代码中运行。当正在执行用户程序而突然被中断程序中断时，此时用户程序也可以象征性地称为处于进程的内核态。因为中断处理程序将使用当前进程的内核栈。这与处于内核态的进程的状态有些类似。
用户态切换到内核态的3种方式
a. 系统调用
这是用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如前例中fork()实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现，例如Linux的int 80h中断。
b. 异常
当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。
c. 外围设备的中断
当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。
这3种方式是系统在运行时由用户态转到内核态的最主要方式，其中系统调用可以认为是用户进程主动发起的，异常和外围设备中断则是被动的。
7. 用户栈和内核栈的区别。
内核创建进程，创建进程的同时创建进程控制块，创建进程自己的堆栈
一个进程有两个堆栈，用户栈和系统栈
用户堆栈的空间指向用户地址空间，内核堆栈的空间指向内核地址空间。
有个CPU堆栈指针寄存器，进程运行的状态有用户态和内核态，当进程运行在用户态时。CPU堆栈指针寄存器指向的是用户堆栈地址，使用的是用户堆栈；当进程运行在内核态时，CPU堆栈指针寄存器指向的是内核堆栈地址，使用的是内核堆栈。
堆栈切换
当系统因为系统调用（软中断）或硬件中断，CPU切换到特权工作模式，进程陷入内核态，进程使用的栈也要从用户栈转向系统栈。
从用户态到内核态要两步骤，首先是将用户堆栈地址保存到内核堆栈中，然后将CPU堆栈指针寄存器指向内核堆栈。
当由内核态转向用户态，步骤是将内核堆栈中得用户堆栈地址恢复到CPU堆栈指针寄存器中。
内核栈和用户栈区别
1.当进程由于中断进入内核态时，系统会把一些用户态的数据信息保存到内核栈中，当返回到用户态时，取出内核栈中得信息恢复出来，返回到程序原来执行的地方。
用户栈就是进程在用户空间时创建的栈，比如一般的函数调用，将会用到用户栈。
2.内核栈是属于操作系统空间的一块固定区域，可以用于保存中断现场、保存操作系统子程序间相互调用的参数、返回值等。
用户栈是属于用户进程空间的一块区域，用户保存用户进程子程序间的相互调用的参数、返回值等。
8. 内存池、进程池、线程池。(c++程序员必须掌握)
池的方式实质上就是一个二级缓存概念，
池化技术 一言以蔽之就是：提前保存大量的资源，以备不时之需以及重复使用
不管内存池、线程池、还是连接池。。应该都具备这些特点吧：
预先分配，先预分配好一定数量的对象，可以防止突然性的大并发请求，可以提升系统响应速度和负载能力。
缓存复用，使用完毕的对象可以暂时存储在池当中，以备被再利用。
方便管理，池中的对象本身做为一个对象是被总控线程监控和管理着的，想提升谁就提升谁，想灭谁就灭谁。。
9. 死锁的概念，导致死锁的原因.
所谓死锁是指多个进 程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。
产生死锁的原因主要是：
（1） 因为系统资源不足。
（2） 进程运行推进的顺序不合适。
（3） 资源分配不当等。
10. 导致死锁的四个必要条件。
产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。 (该条件不可能禁止)
（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
11. 处理死锁的四个方式。？三个
1) 预防死锁。 通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。 2) 避免死锁。（银行家算法） 在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 死锁避免（deadlock avoidence）是在系统运行过程中注意避免死锁的发生。这就要求每当申请一个资源时，系统都应根据一定的算法判断是否认可这次申请，使得在今后一段时间内系统不会出现死锁。 3)检测和解除死锁。 先检测：通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。检测方法包括定时检测、效率低时检测、进程等待时检测等。 再解除：常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。
12. 预防死锁（防止四个条件之一发生）的方法、避免死锁（银行家算法）的方法。
13. 进程调度算法。
(周转时间 = 程序结束时间 -- 开始服务时间 = 等待时间 + 服务时间 、 带权周转时间= 周转时间 / 要求服务时间)
决策模式：非抢占式；抢占式。
w:花费的等待时间
e：到现在为止，花费 的执行时间
s：进程所需要的总服务时间
选择函数决策模式
1.先来先服务（FCFS）：max（w） 非抢占
2.轮转（RR）：常数抢占
3.最短进程优先（SPN）：min（s）非抢占
4.最短剩余时间（SRT）：min（s - e）抢占
5.最高相应比（HRRN）：max（（w+s）/s）非抢占
6.反馈：抢占
14. Windows内存管理的方式(块式、页式、段式、段页式).
windows 内存管理方式主要分为：页式管理，段式管理，段页式管理。
页式管理的基本原理是将各进程的虚拟空间划分为若干个长度相等的页；页式管理把内存空间按照页的大小划分成片或者页面，然后把页式虚拟地址与内存地址建立一一对应的页表；并用相应的硬件地址变换机构来解决离散地址变换问题。页式管理采用请求调页或预调页技术来实现内外存存储器的统一管理。其优点是没有外碎片，每个内碎片不超过页的大小。缺点是,程序全部装入内存，要求有相应的硬件支持。例如地址变换机构缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了机器成本，增加了系统开销。
段式管理的基本思想是把程序按照内容或过程函数关系分段，每段都有自己的名字。一个用户作业或进程所包括的段对应一个二维线形虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换为实际内存物理地址。其优点是可以分别编写和编译，可以针对不同类型的段采用不同的保护，可以按段为单位来进行共享，包括通过动态链接进行代码共享。缺点是会产生外部碎片。
段页式管理：为了实现段页式管理，系统必须为每个作业或进程建立一张段表以管理内存分配与释放、缺段处理等。另外由于一个段又被划分成了若干个页。每个段必须建立一张页表以把段中的虚页变换成内存中的实际页面。显然与页式管理时相同，页表中也要有相应的实现缺页中断处理和页面保护等功能的表项。段页式管理的段式管理与页式管理方案结合而成的所以具有他们两者的优点。但反过来说，由于管理软件的增加，复杂性和开销也就随之增加了。另外需要的硬件以及占用的内存也有所增加。使得速度降下来。
分页和分段的区别：
1 页是信息的物理单位，分页是为了实现离散分配方式，以消减内存的外零头，提高内存的利用率。分页仅仅是由于系统管理的需要而不是用户的需要
段是信息的逻辑单位，分段的目的是为了能更好地满足用户的需要
2 页的大小固定，由系统把逻辑地址划分为页号和页内地址两部分，
段的长度却不固定，决定于用户所编写的程序
3 分页的作业地址空间是一维的，即单一的线性地址空间。
分段的作业地址空间是二维的 在标识一个地址时，即需给出段名，又需给出段内地址
1.分页管理：
用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
2.分段管理：
将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。
3.段页式存储管理：
分页系统能有效地提高内存的利用率，而分段系统能反映程序的逻辑结构，便于段的共享与保护，将分页与分段两种存储方式结合起来，就形成了段页式存储管理方式。
在段页式存储管理系统中，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于主存空间也分成大小相等的页，主存的分配以页为单位。
段页式系统中，作业的地址结构包含三部分的内容：段号 页号 页内位移量
程序员按照分段系统的地址结构将地址分为段号与段内位移量，地址变换机构将段内位移量分解为页号和页内位移量。
为实现段页式存储管理，系统应为每个进程设置一个段表，包括每段的段号，该段的页表始址和页表长度。每个段有自己的页表，记录段中的每一页的页号和存放在主存中的物理块号。
15. 内存连续分配方式采用的几种算法及各自优劣。
连续分配方式，是指为一个用户程序分配一个连续的内存空间。
它主要包括单一连续分配、固定分区分配和动态分区分配
单一连续分配：
内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。
这种方式的优点是简单、无外部碎片，可以釆用覆盖技术，不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。
固定分区分配：
固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区，如此循环。
固定分区分配在划分分区时，有两种不同的方法，如图3-4所示。
- 分区大小相等：用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性。
- 分区大小不等：划分为含有多个较小的分区、适量的中等分区及少量的大分区。
这种分区方式存在两个问题：一是程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术来使用内存空间；
二是主存利用率低，当程序小于固定分区大小时，也占用了一个完整的内存分区空间，这样分区内部有空间浪费，这种现象称为内部碎片。
固定分区是可用于多道程序设计最简单的存储分配，无外部碎片，但不能实现多进程共享一个主存区，所以存储空间利用率低。
图3-4 固定分区分配的两种方法
动态分区分配：
动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分区方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。
几种算法：
- 首次适应(First Fit)算法：从开始扫描内存，找到大小足够的第一个空闲分区。
- 最佳适应(Best Fit)算法：空闲分区按容量递增形成分区链，选择与要求最接近的空闲分区。
- 最坏适应(Worst Fit)算法：又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。
- 邻近适应(Next Fit)算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。
16. 动态链接及静态链接.
静态链接方法：静态链接的时候，载入代码就会把程序会用到的动态代码或动态代码的地址确定下来
静态库的链接可以使用静态链接，动态链接库也可以使用这种方法链接导入库动态链接方法：使用这种方式的程序并不在一开始就完成动态链接，而是直到真正调用动态库代码时，载入程序才计算(被调用的那部分)动态代码的逻辑地址，然后等到某个时候，程序又需要调用另外某块动态代码时，载入程序又去计算这部分代码的逻辑地址，所以，这种方式使程序初始化时间较短，但运行期间的性能比不上静态链接的程序。
简单的说，静态库和应用程序编译在一起，在任何情况下都能运行，而动态库是动态链接，顾名思义就是在应用程序启动的时候才会链接，所以，当用户的系统上没有该动态库时，应用程序就会运行失败。再看它们的特点：
动态库：
1.共享：多个应用程序可以使用同一个动态库，启动多个应用程序的时候，只需要将动态库加载到内存一次即可；
2.开发模块好：要求设计者对功能划分的比较好。
静态库：代码的装载速度快，执行速度也比较快，因为编译时它只会把你需要的那部分链接进去，应用程序相对比较大。但是如果多个应用程序使用的话，会被装载多次，浪费内存。
17. 基本分页、请求分页储存管理方式。
基本分页：
不具备页面对换功能 不支持虚拟存储器功能 在调度作业运行时 必须将它的所有页面一次调入内存 若内存没有足够的块 则作业等待 的这种分页管理方式被称为纯分页或基本分页存储管理方式
请求分页管理方式：是支持虚拟存储的 具备了页面的对换功能调度作业时 是将它的 一部分（而不是全部） 放入内存
当发现页面缺少时 会发出一个缺页请求 从外存调用页面文件进入内存
18. 基本分段、请求分段储存管理方式。
请求分段存储管理系统也与请求分页存储管理系统一样，为用户提供了一个比内存空间大得多的虚拟存储器。
在请求分段存储管理系统中，作业运行之前，只要求将当前需要的若干个分段装入内存，便可启动作业运行。
在作业运行过程中，如果要访问的分段不在内存中，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存，以便腾出内存空间
19. 分段分页方式的比较各自优缺点。
分页消除外碎片，分段消除内碎片
20. 几种页面置换算法，会算所需换页数。(LRU用程序如何实现？)
1．最佳置换算法（OPT）（理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。2．先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。3．最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。4．Clock置换算法（LRU算法的近似实现）：给每一帧关联一个附加位，称为使用位。当需要替换一页时，操作系统扫描缓冲区，以查找使用位为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位置为0；如果在这个过程开始时，缓冲区中所有的使用位均为0,则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有的使用位都置为0,并停留在最初的位置上，替换该帧中的页5．最少使用（LFU）置换算法
21. 虚拟内存的定义及实现方式。
基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。
虚拟存储器有以下三个主要特征：
- 多次性，是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。
- 对换性，是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。
- 虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量，远大于实际的内存容量。
虚拟内存的实现有以下三种方式：
- 请求分页存储管理。
- 请求分段存储管理。
- 请求段页式存储管理。
不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：
详见《操作系统精髓与设计原理（第五版）》 第8章 虚拟内存
- 一定容量的内存和外存。
- 页表机制（或段表机制），作为主要的数据结构。
- 中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。
- 地址变换机构，逻辑地址到物理地址的变换。
22. 操作系统的四个特性。
并发
共享
虚拟
异步
23. DMA。
DMA（Direct Memory Access），即直接存储器存取，是一种快速传送数据的机制。数据传递可以从适配卡到内存，从内存到适配卡或从一段内存到另一段内存。
24. Spooling。
1、SPOOLing的含义是什么？试述SPOOLing系统的特点、功能以及控制过程。答：SPOOLing是Simultaneous Peripheral Operation On-Line （即外部设备联机并行操作）的缩写它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为"假脱机技术"。 SPOOLing技术是在通道技术和多道程序设计基础上产生的，它由主机和相应的通道共同承担作业的输入输出工作，利用磁盘作为后援存储器，实现外围设备同时联机操作。 SPOOLing系统由专门负责I/O的常驻内存的进程以及输入井、输出井组成；它将独占设备改造为共享设备，实现了虚拟设备功能。
2、SPOOLing技术如何使一台打印机虚拟成多台打印机？ 答：将一*享打印机改造为可供多个用户共享的打印机，是应用SPOOLing技术的典型实例。具体做法是：系统对于用户的打印输出，但并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送入其中；然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。若打印机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。