操作系统常见面试题总结

╰+攻爆jí腚メ 2022-04-10 12:46 356阅读 0赞

## 一、操作系统简介： ##

### 1、什么是操作系统： ###

操作系统本质上是一个运行在计算机上的软件程序 ，管理着计算机硬件和软件资源，为计算机硬件和软件提供了一种中间层，使应用软件和硬件进行分离，屏蔽了硬件层的复杂性，让我们把关注点更多放在软件应用上。操作系统的主要功能有：

>  *  （1）进程管理：进程管理的主要作用就是任务调度，以及进程的创建销毁、阻塞唤醒、进程同步、进程通信、死锁处理等功能。
>  *  （2）内存管理：内存分配与回收、地址映射、虚拟内存以及页面的置换
>  *  （3）文件管理：有效地管理文件的存储空间，合理地组织和管理文件系统，为文件访问和文件保护提供更有效的方法及手段。
>  *  （4）设备管理：根据确定的设备分配原则对设备进行分配，使设备与主机能够并行工作，为用户提供良好的设备使用界面。

### 2、什么是用户态和内核态： ###

用户态和系统态是操作系统的两种运行状态：

>  *  内核态：内核态运行的程序可以访问计算机的任何数据和资源，不受限制，包括外围设备，比如网卡、硬盘等。处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况。
>  *  用户态：用户态运行的程序只能受限地访问内存，只能直接读取用户程序的数据，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。

将操作系统的运行状态分为用户态和内核态，主要是为了对访问能力进行限制，防止随意进行一些比较危险的操作导致系统的崩溃，比如设置时钟、内存清理，这些都需要在内核态下完成

## 二、进程与线程： ##

### 1、进程与线程的区别： ###

（1）一个程序至少有一个进程，一个进程至少有一个线程，线程是依赖于进程存在的，线程是一个进程中代码的不同的执行路线；

（2）进程是对运行时程序的封装，是操作系统进行资源调度和分配的最小单位，实现了操作系统的并发；线程是程序执行的最小单位，是CPU调度和分派的基本的单位，实现进程内部的并发。

（3）资源与内存空间：进程是资源分配的基本单位，线程不拥有资源；进程之间拥有相互独立的内存单位，但是同一个进程下的各个线程之间共享程序的内存空间，（包括代码段、数据集、堆等)及一些进程级的资源(如打开文件和信号)，某进程内的线程在其它进程不可见；

（4）系统开销：创建或销毁进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等；而线程只需要堆栈指针以及程序计数器就可以了，开销远小于创建或撤销进程时的开销。在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

（5）通信：线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助IPC。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E3NDUyMzM3MDA_size_16_color_FFFFFF_t_70][]

### **2、进程的五种状态：** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E3NDUyMzM3MDA_size_16_color_FFFFFF_t_70 1][]

（1）创建状态：进程刚被创建，尚未进入就绪队列。创建进程需要两个步骤：即为新进程分配所需要的资源和空间，设置进程为就绪态，并等待调度执行。

（2）就绪状态：进程已获得除CPU以外的所需的一切资源，一旦得到CPU资源即可运行；

（3）运行状态：进程正在处理器上面运行

（4）阻塞状态：进程正在等待某一事件而暂停运行，如等待某资源或者等待 IO 操作完成，即使CPU 空闲，该进程也不能运行；

（5）终止状态：进程达到正常结束点或因其他原因被终止，下一步将被撤销。 终止一个进程需要两个步骤：先等待操作系统或相关的进程进行善后处理；然后回收占用的资源并被系统删除。

>  *  只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
>  *  阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

### 3、进程的调度算法： ###

（1）先来先服务：按照请求的顺序进行调度，使用队列实现。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

（2）最短作业优先：按照估计运行时间最短的顺序进行调度。有利于短作业，但长作业有可能饿死，处于一直等待短作业执行完毕的状态，因为可能一直有短作业到来，那么长作业永远得不到调度。

（3）最短剩余时间优先：按估计剩余时间最短的顺序进行调度。

（4）时间片轮转：将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

> 时间片轮转算法的效率和时间片的大小有很大关系：因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。而如果时间片过长，那么实时性就不能得到保证。

（5）优先级调度：为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

（6）多级反馈队列调度算法：可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。它设置了多个队列，每个队列时间片大小都不同，进程在第一个队列没执行完，就会被移到下一个队列。

> 实施过程：
> 
>  *  ① 设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中，为每个进程所规定的执行时间片就越小。
>  *  ② 当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。 如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度…… 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。
>  *  ③ 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1到第（i-1）队列空时， 才会调度第i队列中的进程运行，并执行相应的时间片轮转。
>  *  ④ 如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列， 则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。

### 4、进程的通信方式： ###

（1）匿名管道 pipe：用于具有亲缘关系的进程间的通信；

（2）有名管道 named pipe：可以用于无亲缘关系的进程间的通信，可以实现本机任意两个进程间的通信

（3）信号 signal：用于通知和接收进程某个事件已经发生。

（4）消息队列 Message Queuing ：消息队列是消息的链表，具有特定的格式，存放在内存中并由消息队列标识符标识。消息队列克服了信号传递信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。管道和消息队列的通信数据都是先进先出的原则，但消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取，比 FIFO 更有优势。

>  *  无名管道：只存在于内存中的文件；
>  *  命名管道：存在于实际的磁盘介质或者文件系统
>  *  消息队列：存放在内核中，只有在内核重启，即操作系统重启或者显示地删除一个消息队列时，该消息队列才会被真正的删除。

（5）信号量 semophore：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。

（6）共享内存 Shared memory：多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。它是针对其他进程间通信方式运行效率低而专门设计的。

（7）套接字 socket：与其他通信机制不同的是，socket 可用于不同机器间的进程通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点。

### 5、线程的七种状态： ###

在 JVM 中，可以将线程划分为以下几种状态：创建(new)、就绪(runnable/start)、运行(running)、阻塞(blocked)、等待(waiting)、时间等待(time waiting) 和 消亡(dead/terminated)。在某一时刻，一个线程只能处于一种状态。

![线程的状态.jpg-59.9kB][.jpg-59.9kB]

### 6、线程间同步的方式： ###

（1）临界区 CriticalSection：在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。

（2）互斥量 Mutex：采用互斥对象机制。只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。当前拥有互斥对象的线程处理完任务后必须将线程交出，以便其他线程访问该资源。互斥对象和临界区对象非常相似，但是互斥量允许在进程间使用，而临界区只限制于同一进程的各个线程之间使用，但是更节省资源，更有效率。

（3）信号量 semophore：信号量其实就是一个计数器，限制了同一时刻访问同一资源的最大线程数。如果这个计数达到了零，则所有对这个Semaphore类对象所控制的资源的访问尝试都被放入到一个队列中等待，直到超时或计数值不为零为止。

（4）事件 Event，wait/notify：事件机制，允许一个线程在处理完一个任务后，主动唤醒另一个线程执行任务，通过通知操作的方式来保持线程的同步。

## 三、死锁： ##

在两个或以上并发进程中，如果每个进程持有某种资源并且都等待别的进程释放它们保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁，也就是多个进程无限期的阻塞、相互等待的一种状态。

### 1、死锁的四个必要条件： ###

（1）互斥条件：一个资源每次只能被一个进程使用。此时若有其他进程请求该资源，则请求进程只能等待。

（2）请求与保持条件：进程已经获得了至少一个资源，但是又提出新的资源请求，而该资源已经被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。即当一个进程等待其他进程是，继续占有已经分配的资源。

（3）不可剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，只能由获得该资源的进程释放。

（4）循环等待条件：若干进程间形成首尾相接的循环等待资源的关系。

### 2、处理死锁的基本策略： ###

常用的处理死锁的方法有：死锁预防、死锁避免、死锁检测、死锁解除、鸵鸟策略。

**（1）死锁的预防：**基本思想就是确保死锁发生的四个必要条件中至少有一个不成立：

>  *  ① 破除资源互斥条件
>  *  ② 破除“请求与保持”条件：实行资源预分配策略，进程在运行之前，必须一次性获取所有的资源。缺点：在很多情况下，无法预知进程执行前所需的全部资源，因为进程是动态执行的，同时也会降低资源利用率，导致降低了进程的并发性。
>  *  ③ 破除“不可剥夺”条件：允许进程强行从占有者那里夺取某些资源。当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已经占有的资源会被暂时被释放，或者说被抢占了。
>  *  ④ 破除“循环等待”条件：实行资源有序分配策略，对所有资源排序编号，按照顺序获取资源，将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行，一个进程只有获得较小编号的进程才能申请较大编号的进程。

**（2）死锁避免：**

死锁预防通过约束资源请求，防止4个必要条件中至少一个的发生，可以通过直接或间接预防方法，但是都会导致低效的资源使用和低效的进程执行。而死锁避免则允许前三个必要条件，但是通过动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。银行家算法是经典的死锁避免的算法。

**（3）死锁检测：**

死锁预防策略是非常保守的，他们通过限制访问资源和在进程上强加约束来解决死锁的问题。死锁检测则是完全相反，它不限制资源访问或约束进程行为，只要有可能，被请求的资源就被授权给进程。但是操作系统会周期性地执行一个算法检测前面的循环等待的条件。死锁检测算法是通过资源分配图来检测是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有存在环，也就是检测到死锁的发生。

>  *  （1）如果进程-资源分配图中无环路，此时系统没有死锁。 
>  *  （2）如果进程-资源分配图中有环路，且每个资源类中只有一个资源，则系统发生死锁。 
>  *  （3）如果进程-资源分配图中有环路，且所涉及的资源类有多个资源，则不一定会发生死锁。

**（4）死锁解除：**

死锁解除的常用方法就是终止进程和资源抢占，回滚。所谓进程终止就是简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；所谓资源抢占就是从一个或者多个死锁进程那里抢占一个或多个资源。

**（5）鸵鸟策略：**

把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任何措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

### 3、活锁： ###

某些情况下，当进程意识到它不能获取所需要的下一个锁时，就会尝试礼貌的释放已经获得的锁，然后等待非常短的时间再次尝试获取。可以想像一下这个场景：当两个人在狭路相逢的时候，都想给对方让路，相同的步调会导致双方都无法前进。

现在假想有一对并行的进程用到了两个资源。它们分别尝试获取另一个锁失败后，两个进程都会释放自己持有的锁，再次进行尝试，这个过程会一直进行重复。很明显，这个过程中没有进程阻塞，但是进程仍然不会向下执行，这种状况我们称之为活锁。

## 四、内存管理： ##

### 1、内存连续分配算法： ###

为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配算法是最早出现的分配方式，该分配方式为用户程序在内存中分配一个连续的内存空间。连续分配方式可以分为四类：单一连续分配、固定分区分配、动态分区分配 和 动态可重定位分区分配。

**（1）单一连续分配：**

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

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

**（2）固定分区分配：**

将用户内存空间划分为若干个固定大小的区域（分区大小可以相等也可以不等），每个分区只装入一道作业。 当有空闲分区时，便可以再从外存的后备作业队列中，选择适当大小的作业装入该分区，如此循环。

> 这种分区方式存在两个问题：一是程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术来使用内存空间；二是主存利用率低，当程序小于固定分区大小时，也占用了一个完整的内存分区空间，存在称为内部碎片。

**（3）动态分区分配：**

该分区方法不预先划分内存划，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要，因此分区的大小和数目是可变的。在进程装入主存时，如果内存中有多个足够大的空闲块，操作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略，常见的分配策略有：

① 首次适应算法：从空闲分区链首开始查找，直至找到一个能满足其大小需求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者。

> 该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区非常少被利用，从而保留了高地址部分的大空闲区。为以后到达的大作业分配大的内存空间创造了条件。缺点在于低址部分不断被划分，留下许多内存碎片，并且每次查找都从低址部分开始，会增加查找的开销。

② 循环首次适应算法：在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区开始查找，直至找到一个能满足需求的空闲分区，并从中划出一块来分给作业。

> 该算法能使空闲中的内存分区分布得更加均匀，缺点是将会缺乏大的空闲分区。

（3）最佳适应算法：把既能满足需求，又是最小的空闲分区分配给作业。

> 为了加速查找，需要将所有的空闲区按照大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足需求的空闲区，必然是最优的，因为每次分配后剩余的空间一定是最小的，缺点是在于内存中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。

（4）最差适应算法：按分区大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中分配，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。在大空闲区中放入程式后，剩下的空闲区常常也非常大，于是还能装下一个较大的新程式。

> 该算法克服了最佳适应算法留下的许多小碎片的不足，但缺点是保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法相同复杂。

### 2、虚拟内存： ###

连续分配方式会形成许多“碎片”，虽然可以通过“紧凑”方法将碎片拼接成可用的大块空间，但开销很大，如果允许将一个进程分散地装入到许多不相邻的分区中，便可以充分利用内存，而无须再进行“紧凑”。基于这一思想而产生了离散分配方式：分页存储管理、分段存储管理、段页式存储管理。而实现这种离散式分配的基础就是虚拟内存。

虚拟内存是为了让物理内存扩充成更大的逻辑内存，让程序获得更多的可用内存。实现的前提是应用程序在运行之前没有必要将页面或段全部装入内存，仅需将那些当前运行所需的少数页面或段先装入内存，其余部分暂留在磁盘上。

虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分为大小相等的多个块，称为页，每个页都是一段连续的地址。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻进行必要的映射；当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E3NDUyMzM3MDA_size_16_color_FFFFFF_t_70 2][]

> 虚拟内存的好处在于：
> 
>  *  （1）在内存中更多的进程，提高系统并发度。由于对任何特定的进程都仅仅装入它的某些块，因此就有足够的空间来放置更多的进程。
>  *  （2）进程可以比物理内存的全部空间还大。

### 3、页面置换算法： ###

在进程运行的过程中，如果所要访问的页面不在内存，则需把他们调入内存，但是如果内存已无空闲空间时，系统必须从内存中调出一页程序或者数据送到磁盘的对换区中。这时，把选择换出页面的算法称为页面置换算法。

（1）最佳页面替换算法（OPT）：被换出的页面将是最长时间内不再被访问的，通常可以保证获得最低的缺页率。是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

（2）最近最少使用（LRU）：淘汰最近一段时间内最久未被使用的页面。

（3）最近未使用（NRU）：

> 每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：
> 
>  *  R=0，M=0
>  *  R=0，M=1
>  *  R=1，M=0
>  *  R=1，M=1
> 
> 当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
> 
> NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

（4）先进先出（FIFO）：淘汰在内存中驻留时间最长的页。

（5）第二机会算法（SCR）：

> FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

（6）时钟页面替换算法（Clock）：

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法与SCR算法思路一致。只是用循环队列来构造页面队列，队列指针指向可能被淘汰的页面。如果队列指针指向的页的“引用位”为1，则将其置为0，同时队列指针指向下一个页。

### 4、颠簸/抖动： ###

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

内存颠簸的解决策略包括：

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

## 五、文件系统： ##

### 1、磁盘的物理结构： ###

![OS\_DISK][OS_DISK]

>  *  磁盘面（Platter）：一个磁盘有多个盘面；
>  *  磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
>  *  扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
>  *  磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
>  *  机械臂杆（Actuator arm）：用于在磁道之间移动磁头；
>  *  转轴（Spindle）：使整个盘面转动。

在磁盘上定位某个物理记录需要知道其柱面号、磁头号以及扇区号。定位物理记录时，磁头到达指定扇区的时间称为查找时间， 选择磁头号并旋转至指定扇区的时间称为 搜索延迟。

### 2、磁盘调度算法： ###

> 读写一个磁盘块的时间的影响因素有：
> 
>  *  寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
>  *  旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
>  *  实际的数据传输时间
> 
> 其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

（1）先来先服务（FCFS）：按照磁盘请求的顺序进行调度。优点是公平和简单，缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

（2）最短寻道时间优先（SSTF）：优先调度与当前磁头所在磁道距离最近的磁道。虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

（3）电梯算法（SCAN）：电梯算法和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

## 六、IO篇： ##

### 1、Unix 常见的IO模型： ###

对于一次IO访问（以read举例），数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。所以说，当一个read操作发生时，它会经历两个阶段：

>  *  等待数据准备就绪 (Waiting for the data to be ready)
>  *  将数据从内核拷贝到进程中 (Copying the data from the kernel to the process)

正式因为这两个阶段，linux系统产生了下面五种网络模式的方案：

>  *  阻塞式IO模型(blocking IO model)
>  *  非阻塞式IO模型(noblocking IO model)
>  *  IO复用式IO模型(IO multiplexing model)
>  *  信号驱动式IO模型(signal-driven IO model)
>  *  异步IO式IO模型(asynchronous IO model)

对于这几种 IO 模型的详细说明，可以参考这篇文章：[掘金][Link 1]

其中，IO多路复用模型指的是：使用单个进程同时处理多个网络连接IO，他的原理就是select、poll、epoll 不断轮询所负责的所有 socket，当某个socket有数据到达了，就通知用户进程。该模型的优势并不是对于单个连接能处理得更快，而是在于能处理更多的连接。

### 2、select、poll 和 epoll 之间的区别： ###

（1）select：时间复杂度 O(n)

select 仅仅知道有 I/O 事件发生，但并不知道是哪几个流，所以只能无差别轮询所有流，找出能读出数据或者写入数据的流，并对其进行操作。所以 select 具有 O(n) 的无差别轮询复杂度，同时处理的流越多，无差别轮询时间就越长。

（2）poll：时间复杂度 O(n)

poll 本质上和 select 没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个 fd 对应的设备状态， 但是它没有最大连接数的限制，原因是它是基于链表来存储的。

（3）epoll：时间复杂度 O(1)

epoll 可以理解为 event poll，不同于忙轮询和无差别轮询，epoll 会把哪个流发生了怎样的 I/O 事件通知我们。 所以说 epoll 实际上是事件驱动（每个事件关联上 fd）的。

> select，poll，epoll 都是 IO 多路复用的机制。I/O 多路复用就是通过一种机制监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），就通知程序进行相应的读写操作。但 select，poll，epoll 本质上都是同步 I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步 I/O 则无需自己负责进行读写，异步 I/O 的实现会负责把数据从内核拷贝到用户空间。

--------------------

> 相关阅读：
> 
> [Spring常见面试题总结][Spring]
> 
> [SpringMVC常见面试题总结][SpringMVC]
> 
> [Mybatis常见面试题总结][Mybatis]
> 
> [MySQL常见面试题总结][MySQL]
> 
> [Redis常见面试题总结][Redis]
> 
> [RabbitMQ消息队列常见面试题总结][RabbitMQ]
> 
> [ElasticSearch搜索引擎常见面试题总结][ElasticSearch]
> 
> [计算机网络常见面试题总结][Link 2]
> 
> [操作系统常见面试题总结][Link 3]
> 
> [Java基础、集合、多线程常见面试题总结][Java]
> 
> [Java虚拟机常见面试题总结][Java 1]
> 
> [Java常见设计模式总结][Java 2]
> 
> [海量数据处理的方法总结][Link 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E3NDUyMzM3MDA_size_16_color_FFFFFF_t_70]: /images/20220330/c9d200d06a88492c843998726bb910e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E3NDUyMzM3MDA_size_16_color_FFFFFF_t_70 1]: /images/20220330/301314b17c0741f0a1e6e146ed8a21a6.png
[.jpg-59.9kB]: /images/20220330/d0dc2418ea274ceba2525e72b89db261.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E3NDUyMzM3MDA_size_16_color_FFFFFF_t_70 2]: /images/20220330/cecc33248dfa4c37ad7dd789843150cc.png
[OS_DISK]: /images/20220330/34c679578afa473cacacdbd1b715ea4e.png
[Link 1]: https://juejin.cn/post/6942686874301857800#heading-13
[Spring]: https://blog.csdn.net/a745233700/article/details/80959716
[SpringMVC]: https://blog.csdn.net/a745233700/article/details/80963758
[Mybatis]: https://blog.csdn.net/a745233700/article/details/80977133
[MySQL]: https://blog.csdn.net/a745233700/article/details/114242960
[Redis]: https://blog.csdn.net/a745233700/category_10727715.html
[RabbitMQ]: https://blog.csdn.net/a745233700/article/details/115060109
[ElasticSearch]: https://blog.csdn.net/a745233700/article/details/115585342
[Link 2]: https://blog.csdn.net/a745233700/article/details/114824602
[Link 3]: https://blog.csdn.net/a745233700/article/details/85995095
[Java]: https://blog.csdn.net/a745233700/category_9280527.html
[Java 1]: https://blog.csdn.net/a745233700/category_7655827.html
[Java 2]: https://blog.csdn.net/a745233700/article/details/120371090
[Link 4]: https://blog.csdn.net/a745233700/article/details/114006686