什么是操作系统？请简要概述一下

操作系统是管理计算机硬件和软件资源的计算机程序，提供一个计算机用户与计算机硬件系统之间的接口。

向上对用户程序提供接口，向下接管硬件资源。

操作系统本质上也是一个软件，作为最接近硬件的系统软件，负责处理器管理、存储器管理、设备管理、文件管理和提供用户接口。

操作系统有哪些分类？

操作系统常规可分为批处理操作系统、分时操作系统、实时操作系统。

若一个操作系统兼顾批操作和分时的功能，则称该系统为通用操作系统。

常见的通用操作系统有：Windows、Linux、MacOS等。

用户态与核心态？哪些操作会导致用户态切换到核心态？

操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间，也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核，保证内核的安全，操作系统直接将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。

通常，系统调用、异常 和 外设中断会导致用户态到内核态的切换：

系统调用：是用户态进程主动要求切换到内核态的一种方式。用户态进程通过系统调用来使用操作系统内核提供的服务以完成自己的工作。例如Linux系统中常见的fork、open、read、write、close等系统调用。

异常：当CPU在执行运行在用户态下的程序时，突然发生了某些事先不可知的异常，这会导致CPU切换执行处理此异常的内核程序。

外设中断：当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会转切换至内核态并启用中断处理程序。

并发和并行的区别

并发（concurrency）：指宏观上看起来两个程序在同时运行，比如说在单核cpu上的多任务。但是从微观上看两个程序的指令是交织着运行的，指令之间交错执行，在单个周期内只运行了一个指令。这种并发并不能提高计算机的性能，只能提高效率（如降低某个进程的相应时间）。

并行（parallelism）：指严格物理意义上的同时运行，比如多核cpu，两个程序分别运行在两个核上，两者之间互不影响，单个周期内每个程序都运行了自己的指令，也就是运行了两条指令。这样说来并行的确提高了计算机的效率。所以现在的cpu都是往多核方面发展。

什么是进程？

进程是操作系统中最重要的抽象概念之一，是资源分配的基本单位，是独立运行的基本单位。

进程的经典定义就是一个执行中程序的实例。系统中的每个程序都运行在某个进程的上下文（context）中。

上下文是由程序正确运行所需的状态组成的。这个状态包括存放在内存中的程序的代码和数据，它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。

进程一般由以下的部分组成：

进程控制块PCB，是进程存在的唯一标志，包含进程标识符PID，进程当前状态，程序和数据地址，进程优先级、CPU现场保护区（用于进程切换），占有的资源清单等。

程序段

数据段

进程的基本状态？

进程有五种基本状态：创建状态、就绪状态、执行状态、阻塞状态、终止状态。状态的转换关系如下：

创建状态：为进程创建PCB（Process Control Block，进程控制块。它是操作系统为了管理进程专门设置的的数据结构）并分配除CPU时间片以外的必要资源的过程；

就绪状态：进程已分配到除CPU以外的所有必要资源后，便进入就绪状态;

执行状态：进程处于就绪状态被调度分配CPU资源后，进程进入执行状态；

阻塞状态：正在执行的进程由于某些事件（如：I/O请求）而暂时交出CPU资源，而无法继续运行便进入阻塞状态；

终止状态：进程自然结束，或出现错误而被系统终释放资源后进入终止状态，无法再执行。

简述进程间通信方法

进程间的通信方式

命名管道

进程调度的时机

当前运行的进程运行结束。

当前运行的进程由于某种原因阻塞。

执行完系统调用等系统程序后返回用户进程。

在使用抢占调度的系统中，具有更高优先级的进程就绪时。

分时系统中，分给当前进程的时间片用完。

不能进行进程调度的情况

在中断处理程序执行时。

在操作系统的内核程序临界区内。

其它需要完全屏蔽中断的原子操作过程中。

进程调度算法有哪些？

先到先服务 (FCFS) 调度算法 : 从就绪队列中选择⼀个最先进⼊队列的进程为其分配 CPU资源并使之运行。有利于长作业，但不利于短作业，短作业会因为前面的长作业长时间执行而迟迟得不到调度。

短作业优先 (SJF) 调度算法: 从就绪队列中选出⼀个估计运⾏时间最短的进程为其分配 CPU资源并使之运行。不利于长作业，如果新的短作业不断到达就绪队列，长作业会一直不能被调度。

优先级调度调度算法： 为每个进程设置优先级，⾸先执⾏⾼优先级的进程，相同优先级的进程按照先来先服务的策略调度。

时间⽚轮转调度算法 : 按照先来先服务的策略依次调度进程，每个进程执行固定时间片后被重新放入队尾。

多级反馈队列调度算法 ：前⾯介绍的⼏种进程调度算法都有⼀定的局限性，⽽该算法可以兼顾高优先级以及长、短作业。

该算法由高到低设置多个优先级不同的队列，该算法按照时间片轮转算法先调度高优先级队列里的进程，通常优先级越高的队列设置的时间片越小。

若高优先级队列中已没有需要调度的进程，则依次调度次优先级队列中的进程。

高优先级队列中的进程如果被调度执行一个时间片的大小后仍没有完成，则依次放入次优先级队列中。

如果低优先级队列中的进程被调度执行时高优先级队列中又有新的进程到达，那么执行完当前时间片后，CPU会马上分配给新到达高优先队列中的进程。

什么是孤儿进程？僵尸进程?

Linux系统中，子进程由父进程创建，子进程退出后虽然会释放部分资源，但进程描述等资源并没有被释放，需要父进程调用wait(会阻塞父进程)或waitpid（可以为非阻塞）来释放，可以方便父进程拿到子进程的终止状态。

僵尸进程：当进程退出之后，他的父进程没有通过调用wait或waitpid回收他的资源，该进程会继续停留在系统的进程表中，占用内核资源，这样的进程就是僵尸进程。通过ps命令显示的僵尸进程状态为Z(zombie)。大量僵尸进程没被回收会导致资源浪费，更致命的是他们会占用大量进程号，导致系统无法给新进程分配进程号。

孤儿进程：进程结束后，它的一个或多个子进程还在运行，那么这些子进程就是孤儿进程。孤儿进程如果没有被自己所在的进程组收养，就会作为init(PID = 1)进程的子进程，他的的资源会由init进程回收。

僵尸进程在其父进程退出后转为孤儿进程。
如何解决僵尸进程：

通过kill -9 杀掉其父进程，僵死进程就可以转为孤儿进程，进而被init进程回收；
由于进程退出时会向父进程发送SIGCHLD信号，因此，可以在父进程捕获该信号并通过wait或waitpid释放子进程资源。

什么是线程？

是进程划分的任务，是一个进程内可调度的实体，是CPU调度的基本单位，用于保证程序的实时性，实现进程内部的并发。

线程是操作系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。

每个线程完成不同的任务，但是属于同一个进程的不同线程之间共享同一地址空间（也就是同样的动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。

为什么需要线程？

线程产生的原因：进程可以使多个程序能并发执行，以提高资源的利用率和系统的吞吐量；但是其具有一些缺点：

进程在同一时刻只能做一个任务，很多时候不能充分利用CPU资源。

进程在执行的过程中如果发生阻塞，整个进程就会挂起，即使进程中其它任务不依赖于等待的资源，进程仍会被阻塞。

引入线程就是为了解决以上进程的不足，线程具有以下的优点：

从资源上来讲，开辟一个线程所需要的资源要远小于一个进程。

从切换效率上来讲，运行于一个进程中的多个线程，它们之间使用相同的地址空间，而且线程间彼此切换所需时间也远远小于进程间切换所需要的时间（这种时间的差异主要由于缓存的大量未命中导致）。

从通信机制上来讲，线程间方便的通信机制。对不同进程来说，它们具有独立的地址空间，要进行数据的传递只能通过进程间通信的方式进行。线程则不然，属于同一个进程的不同线程之间共享同一地址空间，所以一个线程的数据可以被其它线程感知，线程间可以直接读写进程数据段（如全局变量）来进行通信（需要一些同步措施）。

简述线程和进程的区别和联系

一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。

进程在执行过程中拥有独立的地址空间，而多个线程共享进程的地址空间。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）

进程是资源分配的最小单位，线程是CPU调度的最小单位。

通信：由于同一进程中的多个线程具有相同的地址空间，使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信（需要一些同步方法，以保证数据的一致性）。

就系统开销来说： 进程创建和销毁时，系统都要单独为它分配和回收资源，开销远大于线程的创建和销毁；进程的上下文切换需要保存更多的信息，线程（同一进程中）的上下文切换只需要保存线程的私有数据：栈、程序计数器（PC）等，系统开销更小。

进程间不会相互影响；一个进程内某个线程挂掉将导致整个进程挂掉。

进程同步的方法

操作系统中，进程是具有不同的地址空间的，两个进程是不能感知到对方的存在的。有时候，需要多个进程来协同完成一些任务。当多个进程需要对同一个内核资源进行操作时，这些进程便是竞争的关系，操作系统必须协调各个进程对资源的占用，进程的互斥是解决进程间竞争关系的方法。进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。当多个进程协同完成一些任务时，不同进程的执行进度不一致，这便产生了进程的同步问题。需要操作系统干预，在特定的同步点对所有进程进行同步，这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。进程互斥本质上也是一种进程同步。进程的同步方法：

互斥锁（互斥量是信号量的一种特例，互斥量的本质是一把锁。）

读写锁

条件变量

记录锁

信号量

屏障（barrier）

线程同步的方法

操作系统中，属于同一进程的线程之间具有相同的地址空间，线程之间共享数据变得简单高效。遇到竞争的线程同时修改同一数据或是协作的线程设置同步点的问题时，需要使用一些线程同步的方法来解决这些问题。

线程同步的方法：

互斥锁

读写锁

条件变量

/*
    条件变量的类型 pthread_cond_t
    int pthread_cond_init(pthread_cond_t *restrict cond, const pthread_condattr_t *restrict attr);
    int pthread_cond_destroy(pthread_cond_t *cond);
    int pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex);
        - 等待，调用了该函数，线程会阻塞。
    int pthread_cond_timedwait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex, const struct timespec *restrict abstime);
        - 等待多长时间，调用了这个函数，线程会阻塞，直到指定的时间结束。
    int pthread_cond_signal(pthread_cond_t *cond);
        - 唤醒一个或者多个等待的线程
    int pthread_cond_broadcast(pthread_cond_t *cond);
        - 唤醒所有的等待的线程
*/
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>

// 创建一个互斥量
pthread_mutex_t mutex;
// 创建条件变量
pthread_cond_t cond;

struct Node{
    int num;
    struct Node *next;
};

// 头结点
struct Node * head = NULL;

void * producer(void * arg) {

    // 不断的创建新的节点，添加到链表中
    while(1) {
        pthread_mutex_lock(&mutex);
        struct Node * newNode = (struct Node *)malloc(sizeof(struct Node));
        newNode->next = head;
        head = newNode;
        newNode->num = rand() % 1000;
        printf("add node, num : %d, tid : %ld\n", newNode->num, pthread_self());
        
        // 只要生产了一个，就通知消费者消费
        pthread_cond_signal(&cond);

        pthread_mutex_unlock(&mutex);
        usleep(100);
    }

    return NULL;
}

void * customer(void * arg) {

    while(1) {
        pthread_mutex_lock(&mutex);
        // 保存头结点的指针
        struct Node * tmp = head;
        // 判断是否有数据
        if(head != NULL) {
            // 有数据
            head = head->next;
            printf("del node, num : %d, tid : %ld\n", tmp->num, pthread_self());
            free(tmp);
            pthread_mutex_unlock(&mutex);
            usleep(100);
        } else {
            // 没有数据，需要等待
            // 当这个函数调用阻塞的时候，会对互斥锁进行解锁，当不阻塞的，继续向下执行，会重新加锁。
            pthread_cond_wait(&cond, &mutex);
            pthread_mutex_unlock(&mutex);
        }
    }
    return  NULL;
}

int main() {

    pthread_mutex_init(&mutex, NULL);
    pthread_cond_init(&cond, NULL);

    // 创建5个生产者线程，和5个消费者线程
    pthread_t ptids[5], ctids[5];

    for(int i = 0; i < 5; i++) {
        pthread_create(&ptids[i], NULL, producer, NULL);
        pthread_create(&ctids[i], NULL, customer, NULL);
    }

    for(int i = 0; i < 5; i++) {
        pthread_detach(ptids[i]);
        pthread_detach(ctids[i]);
    }

    while(1) {
        sleep(10);
    }

    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&cond);

    pthread_exit(NULL);

    return 0;
}

信号量

自旋锁

屏障

线程间同步的三种方式

条件变量和信号量的区别

进程同步与线程同步有什么区别

进程之间地址空间不同，不能感知对方的存在，同步时需要将锁放在多进程共享的空间。而线程之间共享同一地址空间，同步时把锁放在所属的同一进程空间即可。

什么是协程

 协程，是一种比线程更加轻量级的存在，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。

子程序，或者称为函数，在所有语言中都是层级调用，比如A调用B，B在执行过程中又调用了C，C执行完毕返回，B执行完毕返回，最后是A执行完毕。所以子程序调用是通过栈实现的，一个线程就是执行一个子程序。子程序调用总是一个入口，一次返回，调用顺序是明确的。而协程的调用和子程序不同。

协程在子程序内部是可中断的，然后转而执行别的子程序，在适当的时候再返回来接着执行。

协程的特点在于是一个线程执行，那和多线程比，协程有何优势？

• 极高的执行效率：因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显；

• 不需要多线程的锁机制：因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

死锁是怎样产生的？

死锁是指两个或两个以上进程在执行过程中，因争夺资源而造成的下相互等待的现象。产生死锁需要满足下面四个条件：

互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源。

占有并等待条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源。

非抢占条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放。

循环等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链。

如何解决死锁问题？

解决死锁的方法即破坏产生死锁的四个必要条件之一，主要方法如下:

资源一次性分配，这样就不会再有请求了（破坏请求条件）。

只要有一个资源得不到分配，也不给这个进程分配其他的资源（破坏占有并等待条件）。

可抢占资源：即当进程新的资源未得到满足时，释放已占有的资源，从而破坏不可抢占的条件。

资源有序分配法：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反，从而破坏环路等待的条件

死锁避免–银行家算法

死锁的检测与解除

请说一下什么是写时复制？

如果有多个进程要读取它们自己的那部门资源的副本，那么复制是不必要的。每个进程只要保存一个指向这个资源的指针就可以了。只要没有进程要去修改自己的“副本”，就存在着这样的幻觉：每个进程好像独占那个资源。从而就避免了复制带来的负担。如果一个进程要修改自己的那份资源“副本”，那么就会复制那份资源，并把复制的那份提供给进程。不过其中的复制对进程来说是透明的。这个进程就可以修改复制后的资源了，同时其他的进程仍然共享那份没有修改过的资源。所以这就是名称的由来：在写入时进行复制。

写时复制的主要好处在于：如果进程从来就不需要修改资源，则不需要进行复制。惰性算法的好处就在于它们尽量推迟代价高昂的操作，直到必要的时刻才会去执行。

在使用虚拟内存的情况下，写时复制（Copy-On-Write）是以页为基础进行的。所以，只要进程不修改它全部的地址空间，那么就不必复制整个地址空间。在fork()调用结束后，父进程和子进程都相信它们有一个自己的地址空间，但实际上它们共享父进程的原始页，接下来这些页又可以被其他的父进程或子进程共享。

实时操作系统的概念

实时操作系统（Real-time operating system, RTOS），又称即时操作系统，它会按照排序运行、管理系统资源，并为开发应用程序提供一致的基础。实时操作系统与一般的操作系统相比，最大的特色就是“实时性”，如果有一个任务需要执行，实时操作系统会马上（在较短时间内）执行该任务，不会有较长的延时。这种特性保证了各个任务的及时执行。

优先级反转是什么？如何解决

由于多进程共享资源，具有最高优先权的进程被低优先级进程阻塞，反而使具有中优先级的进程先于高优先级的进程执行，导致系统的崩溃。这就是所谓的优先级反转(Priority Inversion)。其实,优先级反转是在高优级(假设为A)的任务要访问一个被低优先级任务(假设为C)占有的资源时,被阻塞.而此时又有优先级高于占有资源的任务©而低于被阻塞的任务(A)的优先级的任务(假设为B)时,于是,占有资源的任务就被挂起(占有的资源仍为它占有),因为占有资源的任务优先级很低,所以,它可能一直被另外的任务挂起.而它占有的资源也就一直不能释放,这样,引起任务A一直没办法执行.而比它优先低的任务却可以执行。

目前解决优先级反转有许多种方法。其中普遍使用的有2种方法：一种被称作优先级继承(priority inheritance)；另一种被称作优先级极限(priority ceilings)。

优先级继承(priority inheritance) 优先级继承是指将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级.当高优先级任务由于等待资源而被阻塞时,此时资源的拥有者的优先级将会自动被提升。

优先级天花板(priority ceilings)优先级天花板是指将申请某资源的任务的优先级提升到可能访问该资源的所有任务中最高优先级任务的优先级.(这个优先级称为该资源的优先级天花板)。

常见内存管理方式有哪些？

内存管理机制分为连续分配管理方式和非连续分配管理方式。前者为进程分配一个连续的内存空间，是古老的内存管理方式，常见的有单一连续分配、固定分区分配等。后者是充分利用离散的内存，将进程分散的装入内存分区中；根据分区大小是否固定可以分为页式管理（固定分区大小）和段式管理（不固定分区大小）；还可以二者混用成段页式管理。

什么是分页存储管理？什么是分段存储管理？区别是什么？

分页存储管理：

分页存储管理极大的提高了内存利用率，他将实际的物理内存分为大小相等的块，通常被称为页帧。页式管理将用户程序所需内存以离散的页帧形式分配给他们。每个用户程序都有自己的逻辑地址空间，逻辑空间也被划分为与页帧大小相同的页面，逻辑页面和物理页帧是一一对应的关系。

那么CPU寻址时，是如何完成逻辑地址到实际物内存地址的转换呢？首先要知道，逻辑地址被划分为高位和低位，高位代表当前逻辑地址所在页面对应的页号，低位代表的是页内偏移，以32位操作系统来说，他的逻辑地址共有32位，如果页面（由页帧大小决定）大小为4KB（4 * 1024 = 212，注：地址单位为B，字节。）则需要占用低12位来表示页内偏移。显然，CPU仅仅借助逻辑地址是无法完成寻址的，还需要借助进程页表才能完成逻辑地址到物理地址的转换，页表中记录的是页面和页帧的对应关系。开始寻址时，CPU根据逻辑地址得到页号和页内偏移，查询页表可得到页号对应页帧在物理内存中的起始地址，页帧起始地址加上页内偏移即可得到实际的物理地址。如下图：

分段存储管理：

分页存储是从计算机的角度进行设计的，目的是为了提高内存的利用率，每一页面并没有实际意义。段式存储管理从程序员和用户角度出发，把程序分割成具有逻辑意义的段，例如：主程序段、子程序段、数据段等等，每一段的大小不定。段式管理将用户程序所需内存以离散的内存段的形式分配给她们。借助段式管理容易实现数据的共享与保护。

那么分段存储管理中，CPU又是如何完成寻址的呢？分段存储管理中，逻辑地址同样被划分为高位和低位，高位表示段号，低位表示段内偏移。仅仅根据段号和段内偏移尚无法完成寻址，还需要借助进程段表，段表记录了逻辑段的大小（段长）以及逻辑段在内存中的起始地址（基址）。开始寻址时，CPU先拿到指明的段号和段内偏移（由于段长不定，段号和段内偏移无法像分页管理那样根据逻辑地址和页面大小直接计算出来页号和页内偏移，需要指明逻辑地址中哪部分表示段号，哪部分表示段内偏移，这也是段式管理中逻辑地址是二维的原因），继续查询段表可以得到逻辑段的基址（段表中的段长是用来检查当前段的段内偏移是否超过段长而发生越界），基址加上段内偏移即可得到实际的物理地址。如下图：

分页管理和分段管理区别：

分页管理是站在计算机角度进行设计，每一页并无逻辑意义，目的是减少外部碎片，提高内存的利用率，对用户不可见；段式管理站在程序员和用户角度，是一种逻辑上的划分，是为了满足用户的需要，对用户是可见的，编程时需要指明段名和段内地址（汇编语言中指明了段名和段内地址就指明了逻辑地址的段号和段内偏移）。
分页管理中，页面大小是固定的；而分段管理中段的大小取决于具体程序代码段，是变化的。
分页管理中，逻辑地址是一维的；而分段管理中逻辑地址是二维的。
在实现对程序和数据的共享与保护时，分段管理中，程序和数据本就按逻辑段存储在内存段中，容易实现对程序段、数据段的共享控制以及保护控制；而分页管理中，逻辑上的代码段或数据段是被分散的存储在各个离散的内存页帧当中，很难实现对逻辑程序段或逻辑数据段的共享与保护。

注：进程页表和进程段表都存放于物理内存中，且一个页表或段表是占用的连续空间。以上图中为了方便表达没有将页表或段表画在物理内存中。

虚拟内存

段页式存储管理了解吗？

在分页存储管理中，内存利用率高，不会产生外部碎片，但不方便实现数据的共享与保护；而分段存储管理则刚好相反。段页式存储管理就是为了结合两者的优点。简单来说，段页式存储管理将逻辑空间划分为逻辑段，逻辑段再划分为逻辑页面；而物理内存划分为大小相同的页帧，逻辑页面和物理页帧一一对应，并装入物理页帧当中。

在段页式存储管理中，逻辑地址被划分为三段，由高到低依次代表段号、页号、页内偏移。CPU寻址时需要借助段表和页表，段表记录了各个逻辑段对应页表的物理内存起始地址，以及页表长度；页表则记录了各个逻辑页面对应物理页帧的起始地址。 寻址开始时，CPU首先拿到指明的段号并根据页面（页帧）大小计算出页号和页内偏移，CPU根据段号和段表可以找到该逻辑段对应页表的起始物理内存地址，再根据页号和页表找到对应页帧首地址，该首地址加上页内偏移即可得到实际的物理地址。（段表中的页表长度用来检查页号是否越界）。如下图：

虚拟内存

虚拟内存允许执行进程不必完全在内存中。

基本思想：

每个进程拥有独立的地址空间，这个空间被分为大小相等的多个块，称为页(Page)，每个页都是一段连续的地址。

这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。

当程序引用到一部分在物理内存中的地址空间时，由硬件立刻进行必要的映射。

当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。

这样，对于进程而言，逻辑上似乎有很大的内存空间，实际上其中一部分对应物理内存上的一块(称为帧，通常页和帧大小相等)，还有一些没加载在内存中的对应在硬盘上

注意

1、请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的，通过请求实现内存与外存的信息置换。

2、如果虚拟内存的页并不存在于物理内存中（如图5的3,4），会产生缺页中断，从磁盘中取得缺的页放入内存，如果内存已满，还会根据某种算法将磁盘中的页换出。

常见的页面置换算法

进程运行时，若其访问的页面不存在内存中却需将其调入，而且内存已经没有空闲空间时，就需要从内存中调出一页程序或者数据，送入磁盘的对换区，替换一个页，选择调出页面的算法称为页面置换算法。好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后长时间内不会再访问的页面先调出。

当前操作系统中最常见的缺页置换算法有：

先进先出（FIFO）算法，最近最少使用（LRU）算法、最不常用（LFU）算法、最佳置换(OPT)算法

先进先出FIFO:

原理：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面

实现：按照进入内存的先后次序排列成队列，从队尾进入，从队首删除

优点：实现简单直观

缺点：没有考虑到实际的页面使用频率，性能差、调出的页面可能是经常访问的，实际应用较少

改进：给每个页面增加一个R位，每次先从链表头开始查找，如果R置位，清除R位并且把该页面的节点放到链表结尾；如果R是0，那么就是又老又没用到，替换掉。

最近最少使用LRU:

原理：置换最近一段时间一类最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间没有被访问的页面，最近可能不会被访问。

实现：缺页时，计算内存中每个逻辑页面的上一次访问时间，选择上一次使用到当前时间最长的页面。

特点：可能达到最优的效果，但维护这样的访问链表开销比较大，当前最常采用的就是LRU算法。

手写LRU缓存机制:https://leetcode-cn.com/problems/lru-cache/submissions/

和redis的一样！！！

最不常用LFU:

原理：缺页时，置换访问次数最少的页面

实现：每个页面设置一个访问计数，访问页面时，访问计数加一，缺页时，置换计数最小的页面

特点：算法开销大，开始时频繁使用，但以后不使用的页面很难置换

最佳置换OPT:

原理：每次选择当前物理块中的页面在未来长时间不被访问的 或 未来不再使用的页面进行淘汰

优点：具有较好的性能，可以保证获取最低的缺页率

缺点：过于理想化，但是实际上无法实现（没有办法预支未来的页面）

颠簸

本质：频繁的页调度行为

具体来讲：进程发生缺页中断，这时，必须置换某一页。然而，其他所有的页都在使用，它置换一个页，但又立刻再次需要这个页。因此，会不断产生缺页中断，导致整个系统的效率急剧下降，这种现象称为颠簸（抖动）。
解决策略：

如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；
如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；
否则，还剩下两个办法：终止该进程或增加物理内存容量。

局部性原理

(1). 时间上的局部性：最近被访问的页在不久的将来还会被访问；
(2). 空间上的局部性：内存中被访问的页周围的页也很可能被访问。