概述

什么是操作系统？

操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
操作系统本质上是一个运行在计算机上的软件程序，提供一个计算机用户与计算机硬件系统之间的接口。用于管理计算机硬件和软件资源。举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。
操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。
操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

分类：
操作系统常规可分为批处理操作系统、分时操作系统、实时操作系统。
若一个操作系统兼顾批操作和分时的功能，则称该系统为通用操作系统。
常见的通用操作系统有：Windows、Linux、MacOS等。

基本特征

并发与并行

并发（concurrency）：指宏观上看起来两个程序在同时运行，比如说在单核cpu上的多任务。但是从微观上看两个程序的指令是交织着运行的，指令之间交错执行，在单个周期内只运行了一个指令。这种并发并不能提高计算机的性能，只能提高效率（如降低某个进程的响应时间）。
并行（parallelism）：指严格物理意义上的同时运行，比如多核cpu，两个程序分别运行在两个核上，两者之间互不影响，单个周期内每个程序都运行了自己的指令，也就是运行了两条指令。这样说来并行的确提高了计算机的效率。所以现在的cpu都是往多核方面发展。

共享

共享是指系统中的资源可以被多个并发进程共同使用。
有两种共享方式：互斥共享和同时共享。
互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。

虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。
主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。
多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。
虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

基本功能

进程管理
进程控制、进程同步、进程通信、死锁处理、处理机调度等。
内存管理
内存分配、地址映射、内存保护与共享、虚拟内存等。
文件管理
文件存储空间的管理、目录管理、文件读写管理和保护等。
设备管理
完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。
主要包括缓冲管理、设备分配、设备处理、虛拟设备等。

系统调用

1. 用户态和系统态

为了避免操作系统和关键数据被用户程序破坏，将处理器的执行状态分为内核态和用户态。

用户态(user mode) ：用户态是用户程序执行时处理器所处的状态，不能执行特权指令，只能访问用户地址空间。
内核态(kernel mode)：内核态是操作系统管理程序执行时所处的状态，能够执行包含特权指令在内的一切指令，能够访问系统内所有的存储空间。

用户程序运行在用户态，操作系统内核运行在内核态。

2. 如何实现内核态和用户态的切换？

处理器从用户态切换到内核态的方法有三种：系统调用、异常和外部中断。

系统调用是操作系统的最小功能单位，是操作系统提供的用户接口，系统调用本身是一种软中断。
异常，也叫做内中断，是由错误引起的，如文件损坏、缺页故障等。
外部中断，是通过两根信号线来通知处理器外设的状态变化，是硬中断。

3. 什么是系统调用呢？

我们运行的程序基本都是运行在用户态，如果我们调用操作系统提供的系统态级别的子功能咋办呢？那就需要系统调用了！
也就是说在我们运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

操作系统面试题 - 图3

这些系统调用按功能大致可分为如下几类：

设备管理。完成设备的请求或释放，以及设备启动等功能。
文件管理。完成文件的读、写、创建及删除等功能。
进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
进程通信。完成进程之间的消息传递或信号传递等功能。
内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

Linux 的系统调用主要有以下这些：

Task	Commands
进程控制	fork(); exit(); wait();
进程通信	pipe(); shmget(); mmap();
文件操作	open(); read(); write();
设备操作	ioctl(); read(); write();
信息维护	getpid(); alarm(); sleep();
安全	chmod(); umask(); chown();

宏内核和微内核

宏内核
宏内核是将操作系统功能作为一个紧密结合的整体放到内核。
由于各模块共享信息，因此有很高的性能。

微内核
由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。
在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。
因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

操作系统面试题 - 图4

中断分类

外中断
由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
异常（内中断）
由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。
陷入
在用户程序中使用系统调用。

中断的处理过程

保护现场：将当前执行程序的相关数据保存在寄存器中，然后入栈。
开中断：以便执行中断时能响应较高级别的中断请求。
中断处理
关中断：保证恢复现场时不被新中断打扰
恢复现场：从堆栈中按序取出程序数据，恢复中断前的执行状态。

一、进程管理

进程和线程基础知识全家桶，30 张图一套带走

1. 进程与线程

1.1 进程

进程是程序的一次执行过程，是一个程序及其数据在处理机上顺序执行时所发生的活动
进程是系统进行资源分配的基本单位。
进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态（程序段、数据段的位置），所谓的创建进程和撤销进程，都是指对 PCB 的操作。

下图显示了 4 个程序创建了 4 个进程，这 4 个进程可以并发地执行。

1.2 线程

在引入线程之前，只有进程之间可以并发（一边听音乐，一边聊qq），为了进一步提高系统的并发度，引入了线程，使得一个进程内也可以并发处理多种任务（文字聊天的同时可以传送文件）
线程是独立调度的基本单位。
一个进程中可以有多个线程，它们共享进程资源。
QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。
同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程都有独立一套的寄存器和栈，这样可以确保线程的控制流是相对独立的。

1.3 进程和线程的区别

拥有资源
进程是资源分配的基本单位，进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈，线程可以访问隶属进程的资源。
调度
线程是CPU调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
系统开销
- 线程的创建比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
- 线程的终止比进程快，因为线程释放的资源相比进程少很多；
- 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
- 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；
通信方面
线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

1.4 进程切换为什么比线程更消耗资源？

进程切换时需要刷新TLB（页表）并获取新的地址空间，然后切换硬件上下文和内核栈；线程切换时只需要切换硬件上下文和内核栈。
进程是程序的动态表现。 一个程序运行起来后，会使用很多资源，比如使用寄存器，内存，文件等。每当切换进程时，必须要考虑保存当前进程的状态。状态包括存放在内存中的程序的代码和数据，它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开的文件描述符的集合，这个状态叫做上下文（Context）。可见，想要切换进程，保存的状态还不少。不仅如此，由于虚拟内存机制，进程切换时需要刷新TLB并获取新的地址空间。
线程存在于进程中，一个进程可以有一个或多个线程。线程是运行在进程上下文中的逻辑流，这个线程可以独立完成一项任务。同样线程有自己的上下文，包括唯一的整数线程ID，栈、栈指针、程序计数器、通用目的寄存器和条件码。可以理解为线程上下文是进程上下文的子集。
由于保存线程的上下文明显比进程的上下文小，因此系统切换线程时，必然开销更小。

1.5 协程

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

线程与协程的区别：
（1）协程执行效率极高。协程直接操作栈基本没有内核切换的开销，所以上下文的切换非常快，切换开销比线程更小。
（2）协程不需要多线程的锁机制，因为多个协程从属于一个线程，不存在同时写变量冲突，效率比线程高。
（3）一个线程可以有多个协程。
协程的优势：
（1）协程调用跟切换比线程效率高：协程执行效率极高。协程不需要多线程的锁机制，可以不加锁的访问全局变量，所以上下文的切换非常快。
（2）协程占用内存少：执行协程只需要极少的栈内存（大概是4～5KB），而默认情况下，线程栈的大小为1MB。
（3）切换开销更少：协程直接操作栈基本没有内核切换的开销，所以切换开销比线程少。

为什么协程比线程切换的开销小？
（1）协程执行效率极高。协程直接操作栈基本没有内核切换的开销，所以上下文的切换非常快，切换开销比线程更小。
（2）协程不需要多线程的锁机制，因为多个协程从属于一个线程，不存在同时写变量冲突，效率比线程高。避免了加锁解锁的开销。

1.6 说说僵尸进程和孤儿进程

我们知道在unix/linux中，正常情况下，子进程是通过父进程创建的，子进程再创建新的进程。子进程的结束和父进程的运行是一个异步过程，即父进程永远无法预测子进程到底什么时候结束。当一个进程完成它的工作终止之后，它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。
孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。

1.7 Java中的线程和Linux中线程的对应关系

Java里的线程是由JVM来管理的，它如何对应到操作系统的线程是由JVM的实现来确定的。Linux 2.6上的HotSpot使用了NPTL机制，JVM线程跟内核轻量级进程有一一对应的关系。线程的调度完全交给了操作系统内核，当然jvm还保留一些策略足以影响到其内部的线程调度，举个例子，在linux下，只要一个Thread.run就会调用一个fork产生一个线程。
Java线程在Windows及Linux平台上的实现方式，现在看来，是内核线程的实现方式。这种方式实现的线程，是直接由操作系统内核支持的——由内核完成线程切换，内核通过操纵调度器（Thread Scheduler）实现线程调度，并将线程任务反映到各个处理器上。内核线程是内核的一个分身。程序一般不直接使用该内核线程，而是使用其高级接口，即轻量级进程（LWP），也即线程。这看起来可能很拗口。看图：
操作系统面试题 - 图7
（说明：KLT即内核线程Kernel Thread，是“内核分身”。每一个KLT对应到进程P中的某一个轻量级进程LWP（也即线程），期间要经过用户态、内核态的切换，并在Thread Scheduler 下反应到处理器CPU上。）

2. 进程状态的切换

我们一般把进程大致分为 5 种状态，这一点和线程很像！

创建状态(new) ：进程正在被创建，尚未到就绪状态。（操作系统为该进程分配所需内存空间等系统资源，创建、初始化PCB）
就绪状态(ready) ：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。
运行状态(running) ：进程正在处理器上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。
阻塞状态(waiting) ：又称为等待状态，进程正在等待某一事件而暂停运行，如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
结束状态(terminated) ：进程正在从系统中消失（是一个过程，回收分配给进程的资源，撤销进程PCB等）。可能是进程正常结束或其他原因中断退出运行。

应该注意以下内容：

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

挂起状态：
它表示进程没有占有物理内存空间。这跟阻塞状态是不一样，阻塞状态是等待某个事件的返回。
由于虚拟内存管理原因，进程的所使用的空间可能并没有映射到物理内存，而是在硬盘上，这时进程就会出现挂起状态，另外调用 sleep 也会被挂起。
挂起状态可以分为两种：

阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

这两种挂起状态加上前面的五种状态，就变成了七种状态变迁（留给我的颜色不多了），见如下图：

3. 进程的控制结构

在操作系统中，是用进程控制块（process control block，PCB）数据结构来描述进程的。PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

3.1 PCB 具体包含什么信息？

进程描述信息：

进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

进程当前状态，如 new、ready、running、waiting 或 blocked 等；
进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

CPU 相关信息：

CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

3.2 每个 PCB 是如何组织的呢？
通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：
将所有处于就绪状态的进程链在一起，称为就绪队列；
把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

那么，就绪队列和阻塞队列链表的组织形式如下图：

4. 进程的控制

我们熟知了进程的状态变迁和进程的数据结构 PCB 后，再来看看进程的创建、终止、阻塞、唤醒的过程，这些过程也就是进程的控制。
01 创建进程
操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源，当子进程被终止时，其在父进程处继承的资源应当还给父进程。同时，终止父进程时同时也会终止其所有的子进程。
创建进程的过程如下：

为新进程分配一个唯一的进程标识号，并申请一个空白的 PCB，PCB 是有限的，若申请失败则创建失败；
为进程分配资源，此处如果资源不足，进程就会进入等待状态，以等待资源；
初始化 PCB；
如果进程的调度队列能够接纳新进程，那就将进程插入到就绪队列，等待被调度运行；

02 终止进程
进程可以有 3 种终止方式：正常结束、异常结束以及外界干预（信号kill掉）。
终止进程的过程如下：

查找需要终止的进程的 PCB；
如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程；
如果其还有子进程，则应将其所有子进程终止；
将该进程所拥有的全部资源都归还给父进程或操作系统；
将其从 PCB 所在队列中删除；

03 阻塞进程
当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。
阻塞进程的过程如下：

找到将要被阻塞进程标识号对应的 PCB；
如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
将该 PCB 插入的阻塞队列中去；

04 唤醒进程
进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的。
如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。
唤醒进程的过程如下：

在该事件的阻塞队列中找到相应进程的 PCB；
将其从阻塞队列中移出，并置其状态为就绪状态；
把该 PCB 插入到就绪队列中，等待调度程序调度；

进程的阻塞和唤醒是一对功能相反的语句，如果某个进程调用了阻塞语句，则必有一个与之对应的唤醒语句。

5. 进程的上下文切换

各个进程之间是共享 CPU 资源的，进程之间需要切换，让不同的进程可以在 CPU 执行，那么这个一个进程切换到另一个进程运行，称为进程的上下文切换。

在详细说进程上下文切换前，我们先来看看 CPU 上下文切换
大多数操作系统都是多任务，通常支持大于 CPU 数量的任务同时运行。实际上，这些任务并不是同时运行的，只是因为系统在很短的时间内，让各个任务分别在 CPU 运行，于是就造成同时运行的错觉。
任务是交给 CPU 运行的，那么在每个任务运行前，CPU 需要知道任务从哪里加载，又从哪里开始运行。
所以，操作系统需要事先帮 CPU 设置好CPU 寄存器和程序计数器。
CPU 寄存器是 CPU 内部一个容量小，但是速度极快的内存（缓存）。我举个例子，寄存器像是你的口袋，内存像你的书包，硬盘则是你家里的柜子，如果你的东西存放到口袋，那肯定是比你从书包或家里柜子取出来要快的多。
再来，程序计数器则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。
所以说，CPU 寄存器和程序计数器是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做CPU 上下文。
既然知道了什么是 CPU 上下文，那理解 CPU 上下文切换就不难了。
CPU 上下文切换就是先把前一个任务的 CPU 上下文（CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。
系统内核会存储保持下来的上下文信息，当此任务再次被分配给 CPU 运行时，CPU 会重新加载这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。
上面说到所谓的「任务」，主要包含进程、线程和中断。所以，可以根据任务的不同，把 CPU 上下文切换分成：进程上下文切换、线程上下文切换和中断上下文切换。

进程的上下文切换到底是切换什么呢？
进程是由内核管理和调度的，所以进程的切换只能发生在内核态。
所以，进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。
通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行，如下图所示：

大家需要注意，进程的上下文开销是很关键的，我们希望它的开销越小越好，这样可以使得进程可以把更多时间花费在执行程序上，而不是耗费在上下文切换。

发生进程上下文切换有哪些场景？

正常情况：为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，就会被系统挂起，切换到其它正在等待 CPU 的进程运行；
主动：进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；
主动：当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
被动：当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
被动：发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；
6. 进程调度算法
调度：当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。
进程调度的主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。这是实现进程并发执行的基础。
不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

非抢占式：只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。（实现简单，系统开销小，但是无法及时处理紧急任务，适合早期的批处理系统） 抢占式：当一个进程正在处理机上执行时，如果有一个更重要或者更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程。（适合分时操作系统、实时操作系统）

1. 先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。
有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

2. 短进程优先 shortest process first（SPF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。
长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

3. 最短剩余时间优先 shortest remaining time next（SRTN）

短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

4. 高响应比优先 highest response ratio next（HRRN）

非抢占式算法，综合考虑进程的等待时间和要求服务的时间
在每次调度时先计算各个进程的响应比(等待时间+要求服务时间)/要求服务时间，选择响应比最高的进程为其服务

5. 时间片轮转

抢占式算法，将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
时间片轮转算法的效率和时间片的大小有很大关系：因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。而如果时间片过长，那么实时性就不能得到保证。

5. 优先级调度

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

6. 多级反馈队列
对以上调度算法的折中权衡。

设计多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
只有第k级队列为空时，才会为k+1级队头的进程分配时间片。如果k+1级队列执行过程中，有新的进程加入到k级队列中，则会先去执行高优先级的队列中的进程。（优先级调度的体现）

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。

7. 进程通信

凉了！张三同学没答好「进程间通信」，被面试官挂了….
👨‍💻面试官 ：进程间的通信常见的的有哪几种方式呢?

进程通信就是指进程之间的信息交换。
进程是分配系统资源的基本单位，因此各进程拥有的内存地址空间相互独立。
为了保证安全，一个进程不能直接访问另一个进程的地址空间。但是有些时候，进程间的信息交换又是必须实现的。内核空间是每个进程都共享的，所以进程之间要通信必须通过内核。

大概有 7 种常见的进程间的通信方式。

下面这部分总结参考了:《进程间通信 IPC (InterProcess Communication)》这篇文章，推荐阅读，总结的非常不错。

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；
进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

管道：

匿名管道
匿名管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
如果你学过 Linux 命令，那你肯定很熟悉「|」这个竖线。

$ ps auxf | grep mysql

上面命令行里的「|」竖线就是一个管道，它的功能是将前一个命令（ps auxf）的输出，作为后一个命令（grep mysql）的输入，从这功能描述，可以看出管道传输数据是单向的，如果想相互通信，我们需要创建两个管道才行。
同时，我们得知上面这种管道是没有名字，所以「|」表示的管道称为匿名管道，用完了就销毁。注意，这个匿名管道是特殊的文件，只存在于内核的内存中，不存于文件系统中。
有名管道
匿名管道，由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道(FIFO)。
有名管道不同于匿名管道之处在于它提供了一个路径名与之关联，以有名管道的文件形式存在于文件系统中，这样，即使与有名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信，因此，通过有名管道不相关的进程也能交换数据。值得注意的是，有名管道严格遵循先进先出(first in first out) ，对匿名管道及有名管道的读总是从开始处返回数据，对它们的写则把数据添加到末尾。它们不支持诸如lseek()等文件定位操作。有名管道的名字存在于文件系统中，内容存放在内存中。也是一个读一个写的单向数据流动。

消息队列

消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示。
与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。
另外与管道不同的是，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达。

消息队列特点总结： （1）消息队列是消息的链表，具有特定的格式，存放在内存中并由消息队列标识符标识. （2）消息队列允许一个或多个进程向它写入与读取消息. （3）管道和消息队列的通信数据都是先进先出的原则。（4）消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取。比FIFO更有优势。（5）消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。（6）目前主要有两种类型的消息队列：POSIX消息队列以及System V消息队列，系统V消息队列目前被大量使用。系统V消息队列是随内核持续的，只有在内核重起或者人工删除时，该消息队列才会被删除。

缺点：

消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。在 Linux 内核中，会有两个宏定义MSGMAX和MSGMNB，它们以字节为单位，分别定义了一条消息的最大长度和一个队列的最大长度。
消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

共享内存

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。
进程间本身的内存是相互隔离的，而共享内存机制相当于给两个进程开辟了一块二者均可访问的内存空间，这时，两个进程便可以共享一些数据了。但是，多进程同时占用资源会带来一些意料之外的情况，这时，我们往往会采用上述的信号量来控制多个进程对共享内存空间的访问。

采用共享内存通信的一个显而易见的好处是效率高，因为进程可以直接读写内存，而不需要任何数据的拷贝。对于像管道和消息队列等通信方式，则需要在内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次数据：一次从输入文件到共享内存区，另一次从共享内存区到输出文件。实际上，进程之间在共享内存时，并不总是读写少量数据后就解除映射，有新的通信时，再重新建立共享内存区域。而是保持共享区域，直到通信完毕为止，这样，数据内容一直保存在共享内存中，并没有写回文件。共享内存中的内容往往是在解除映射时才写回文件的。因此，采用共享内存的通信方式效率是非常高的。

4. 信号量
用了共享内存通信方式，带来新的问题，那就是如果多个进程同时修改同一个共享内存，很有可能就冲突了。例如两个进程都同时写一个地址，那先写的那个进程会发现内容被别人覆盖了。
为了防止多进程竞争共享资源，而造成的数据错乱，所以需要保护机制，使得共享的资源，在任意时刻只能被一个进程访问。正好，信号量就实现了这一保护机制。
信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步。
信号量表示资源的数量，控制信号量的方式有两种原子操作：

一个是P 操作，这个操作会把信号量减去 -1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。
另一个是V 操作，这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程；

P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。

接下来，举个例子，如果要使得两个进程互斥访问共享内存，我们可以初始化信号量为1。

具体的过程如下：

进程 A 在访问共享内存前，先执行了 P 操作，由于信号量的初始值为 1，故在进程 A 执行 P 操作后信号量变为 0，表示共享资源可用，于是进程 A 就可以访问共享内存。
若此时，进程 B 也想访问共享内存，执行了 P 操作，结果信号量变为了 -1，这就意味着临界资源已被占用，因此进程 B 被阻塞。
直到进程 A 访问完共享内存，才会执行 V 操作，使得信号量恢复为 0，接着就会唤醒阻塞中的线程 B，使得进程 B 可以访问共享内存，最后完成共享内存的访问后，执行 V 操作，使信号量恢复到初始值 1。

可以发现，信号初始化为1，就代表着是互斥信号量，它可以保证共享内存在任何时刻只有一个进程在访问，这就很好的保护了共享内存。

另外，在多进程里，每个进程并不一定是顺序执行的，它们基本是以各自独立的、不可预知的速度向前推进，但有时候我们又希望多个进程能密切合作，以实现一个共同的任务。
例如，进程 A 是负责生产数据，而进程 B 是负责读取数据，这两个进程是相互合作、相互依赖的，进程 A 必须先生产了数据，进程 B 才能读取到数据，所以执行是有前后顺序的。
那么这时候，就可以用信号量来实现多进程同步的方式，我们可以初始化信号量为0。

具体过程：

如果进程 B 比进程 A 先执行了，那么执行到 P 操作时，由于信号量初始值为 0，故信号量会变为 -1，表示进程 A 还没生产数据，于是进程 B 就阻塞等待；
接着，当进程 A 生产完数据后，执行了 V 操作，就会使得信号量变为 0，于是就会唤醒阻塞在 P 操作的进程 B；
最后，进程 B 被唤醒后，意味着进程 A 已经生产了数据，于是进程 B 就可以正常读取数据了。

可以发现，信号初始化为0，就代表着是同步信号量，它可以保证进程 A 应在进程 B 之前执行。

5. 信号
上面说的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。信号是一种比较复杂的通信方式，信号可以在任何时候发给某一进程，而无需知道该进程的状态。
信号跟信号量虽然名字相似度 66.66%，但两者用途完全不一样，就好像 Java 和 JavaScript 的区别。
在 Linux 操作系统中，为了响应各种各样的事件，提供了几十种信号，分别代表不同的意义。

Linux系统中常用信号：（1）SIGHUP：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。（2）SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。（3）SIGQUIT：程序退出信号。程序运行过程中，按Ctrl+\键将产生该信号。（4）SIGBUS和SIGSEGV：进程访问非法地址。（5）SIGFPE：运算中出现致命错误，如除零操作、数据溢出等。（6）SIGKILL：用户终止进程执行信号。shell下执行kill -9发送该信号。（7）SIGTERM：结束进程信号。shell下执行kill 进程pid发送该信号。（8）SIGALRM：定时器信号。（9）SIGCLD：子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。

运行在 shell 终端的进程，我们可以通过键盘输入某些组合键的时候，给进程发送信号。例如

Ctrl+C 产生SIGINT信号，表示终止该进程；
Ctrl+Z 产生SIGTSTP信号，表示停止该进程，但还未结束；

如果进程在后台运行，可以通过kill命令的方式给进程发送信号，但前提需要知道运行中的进程 PID 号，例如：

kill -9 1050 ，表示给 PID 为 1050 的进程发送SIGKILL信号，用来立即结束该进程；

所以，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令）。

信号是Linux系统中用于进程间互相通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。
如果该进程当前并未处于执行状态，则该信号就有内核保存起来，直到该进程恢复执行并传递给它为止。
如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消是才被传递给进程。

Socket

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。
实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。
我们来看看创建 socket 的系统调用：

int socket(int domain, int type, int protocal)

三个参数分别代表：

domain 参数用来指定协议族，比如 AF_INET 用于 IPV4、AF_INET6 用于 IPV6、AF_LOCAL/AF_UNIX 用于本机；
type 参数用来指定通信特性，比如 SOCK_STREAM 表示的是字节流，对应 TCP、SOCK_DGRAM 表示的是数据报，对应 UDP、SOCK_RAW 表示的是原始套接字；
protocal 参数原本是用来指定通信协议的，但现在基本废弃。因为协议已经通过前面两个参数指定完成，protocol 目前一般写成 0 即可；

根据创建 socket 类型的不同，通信的方式也就不同：

实现 TCP 字节流通信：socket 类型是 AF_INET 和 SOCK_STREAM；
实现 UDP 数据报通信：socket 类型是 AF_INET 和 SOCK_DGRAM；
实现本地进程间通信：「本地字节流 socket 」类型是 AF_LOCAL 和 SOCK_STREAM，「本地数据报 socket 」类型是 AF_LOCAL 和 SOCK_DGRAM。另外，AF_UNIX 和 AF_LOCAL 是等价的，所以 AF_UNIX 也属于本地 socket；

1) 针对 TCP 协议通信的 socket 编程模型

服务端和客户端初始化socket，得到文件描述符；
服务端调用bind，将绑定在 IP 地址和端口;
服务端调用listen，进行监听；
服务端调用accept，等待客户端连接；
客户端调用connect，向服务器端的地址和端口发起连接请求；
服务端accept返回用于传输的socket的文件描述符；
客户端调用write写入数据；服务端调用read读取数据；
客户端断开连接时，会调用close，那么服务端read读取数据的时候，就会读取到了EOF，待处理完数据后，服务端调用close，表示连接关闭。

这里需要注意的是，服务端调用accept时，连接成功了会返回一个已完成连接的 socket，后续用来传输数据。
所以，监听的 socket 和真正用来传送数据的 socket，是「两个」 socket，一个叫作监听 socket，一个叫作已完成连接 socket。
成功连接建立之后，双方开始通过 read 和 write 函数来读写数据，就像往一个文件流里面写东西一样。

2) 针对 UDP 协议通信的 socket 编程模型

UDP 是没有连接的，所以不需要三次握手，也就不需要像 TCP 调用 listen 和 connect，但是 UDP 的交互仍然需要 IP 地址和端口号，因此也需要 bind。
对于 UDP 来说，不需要要维护连接，那么也就没有所谓的发送方和接收方，甚至都不存在客户端和服务端的概念，只要有一个 socket 多台机器就可以任意通信，因此每一个 UDP 的 socket 都需要 bind。
另外，每次通信时，调用 sendto 和 recvfrom，都要传入目标主机的 IP 地址和端口。

3) 针对本地进程间通信的 socket 编程模型
本地 socket 被用于在同一台主机上进程间通信的场景：

本地 socket 的编程接口和 IPv4 、IPv6 套接字编程接口是一致的，可以支持「字节流」和「数据报」两种协议；
本地 socket 的实现效率大大高于 IPv4 和 IPv6 的字节流、数据报 socket 实现；

对于本地字节流 socket，其 socket 类型是 AF_LOCAL 和 SOCK_STREAM。
对于本地数据报 socket，其 socket 类型是 AF_LOCAL 和 SOCK_DGRAM。
本地字节流 socket 和本地数据报 socket 在 bind 的时候，不像 TCP 和 UDP 要绑定 IP 地址和端口，而是绑定一个本地文件，这也就是它们之间的最大区别。

总结
由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

Linux 内核提供了不少进程间通信的方式，其中最简单的方式就是管道，管道分为「匿名管道」和「命名管道」。
- 匿名管道顾名思义，它没有名字标识，匿名管道是特殊文件只存在于内核中的内存中，没有存在于文件系统中，shell 命令中的「|」竖线就是匿名管道，通信的数据是无格式的流并且大小受限，通信的方式是单向的，数据只能在一个方向上流动，如果要双向通信，需要创建两个管道，再来匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。
- 命名管道突破了匿名管道只能在亲缘关系进程间的通信限制，因为使用命名管道的前提，需要在文件系统创建一个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信。
- 另外，不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则，不支持 lseek 之类的文件定位操作。
消息队列克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。
共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。
那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是P 操作和 V 操作。
与信号量名字很相似的叫信号，它俩名字虽然相似，但功能一点儿都不一样。信号是进程间通信机制中唯一的异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即SIGKILL和SEGSTOP，这是为了方便我们能在任何时候结束或停止某个进程。
前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。
8. 进程同步

临界区

通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
优点：保证在某一时刻只有一个线程能访问数据的简便办法。
缺点：虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。相当于排它锁
临界区：对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

互斥量

为协调共同对一个共享资源的单独访问而设计的。互斥量跟临界区很相似，比临界区复杂，互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限。
优点：

使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

缺点：

互斥量是可以命名的，也就是说它可以跨越进程使用，所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。
通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号量对象可以说是一种资源计数器。

信号量

为控制一个具有有限数量的用户资源而设计。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。互斥量是信号量的一种特殊情况，当信号量的最大资源数=1就是互斥量了。

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}
void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。

monitor ProducerConsumer
    integer i;
    condition c;
    procedure insert();
    begin
        // ...
    end;
    procedure remove();
    begin
        // ...
    end;
end monitor;

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

人们到一家叫做计算机的银行取钱，这个银行里面就一个空窗口。最早之前，每个人需要从这个窗口爬进去取钱。这里，银行里面每一个需要取钱的人看作进程，而银行里面的钱可以看做计算机的共享资源，一般是硬件设备或一群共享变量。每个人都向窗口拥挤，场面混乱不堪。后面计算机银行不断改进，发明了一种叫ATM的机器（管程），ATM（管程）封装了钱和对外开放了一些存取钱的操作。这样一来，ATM（管程）在计算机银行的钱和客户之间担任了中介服务的角色。在一个相对封闭的屋子里面，一次只能服务一个人（让进程互斥使用）。ATM屋子里面有人的时候，其他需要依次排队使用。一个人（进程）在ATM使用的时间太长也不行，所以需要一个条件变量（condition）来约束他。条件变量可以让一个线程等待时让另一线程进入管程，这样可以有效防止死锁。

9. 线程同步

👨‍💻面试官 ：那线程间的同步的方式有哪些呢?
🙋 我：线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。操作系统一般有下面三种线程同步的方式：

互斥量(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
事件(Event) ：用来通知线程有一些事件已发生，从而启动后继任务的开始。比如Java中的Wait/Notify通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

10. 死锁

什么是死锁

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

必要条件

互斥条件：即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器，打印机等等，必须在占有该资源的进程主动释放它之后，其它进程才能占有该资源。这是由资源本身的属性所决定的。如独木桥就是一种独占资源，两方的人不能同时过桥。
不剥夺条件：进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。如过独木桥的人不能强迫对方后退，也不能非法地将对方推下桥，必须是桥上的人自己过桥后空出桥面（即主动释放占有资源），对方的人才能过桥。
请求和保持条件：进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。还以过独木桥为例，甲乙两人在桥上相遇。甲走过一段桥面（即占有了一些资源），还需要走其余的桥面（申请新的资源），但那部分桥面被乙占有（乙走过一段桥面）。甲过不去，前进不能，又不后退；乙也处于同样的状况。
循环等待条件：存在一个进程等待序列{P1，P2，…，Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一源，……，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。就像前面的过独木桥问题，甲等待乙占有的桥面，而乙又等待甲占有的桥面，从而彼此循环等待。

处理方法

1. 死锁预防
在程序运行之前预防发生死锁。

破坏互斥条件
例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
破坏占有和等待条件
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
破坏不可抢占条件
破坏环路等待
给资源统一编号，进程只能按编号顺序来请求资源。

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

安全状态 图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

单个资源的银行家算法 一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

多个资源的银行家算法 上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

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

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

死锁恢复

利用抢占恢复
利用回滚恢复
通过杀死进程恢复

鸵鸟策略

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

二、内存管理

真棒！ 20 张图揭开内存管理的迷雾，瞬间豁然开朗

1. 内存管理介绍

👨‍💻 面试官: 操作系统的内存管理主要是做什么？

操作系统负责内存空间的分配与回收。（进程的数据块、地址块）
操作系统需要提供某种技术从逻辑上对内存空间进行扩充。（虚拟技术）
操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换。（程序员写程序不需要关注物理内存的实际情况）操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。
操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰。

2. 常见的几种内存管理机制
👨‍💻 面试官: 操作系统的内存管理机制了解吗？内存管理有哪几种方式?
简单分为连续分配管理方式和非连续分配管理方式这两种。连续分配管理方式是指为一个用户程序分配一个连续的内存空间，常见的如 块式管理 。同样地，非连续分配管理方式允许一个程序使用的内存分布在离散或者说不相邻的内存中，常见的如页式管理 和 段式管理。
块式管理 ：远古时代的计算机操作系统的内存管理方式。将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间，我们称之为碎片。
页式管理 ：把主存分为大小相等且固定的一页一页的形式，页较小，相对相比于块式管理的划分力度更大，提高了内存利用率，减少了碎片。页式管理通过页表对应逻辑地址和物理地址。
段式管理 ：页式管理虽然提高了内存利用率，但是页式管理其中的页实际并无任何实际意义。段式管理把主存分为一段段的。但是，最重要的是段是有实际意义的，每个段定义了一组逻辑信息，例如，有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。段式管理通过段表对应逻辑地址和物理地址。

👨‍💻面试官 ：回答的还不错！不过漏掉了一个很重要的 段页式管理机制 。段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的。

3. 虚拟内存

3.1 什么是虚拟内存(Virtual Memory)?

传统存储管理方式存在的问题：

一次性：作业必须一次性全部装入内存后才能开始运行，这样会造成两个问题：
- 作业很大时，不能全部装入内存，导致大作业无法运行
- 大量作业要求运行时，由于内存无法容纳所有作业，因此只能有少量作业能运行，导致多道程序并发度下降
驻留性：一旦作业被装入内存，就会一直驻留在内存中，直到作业运行结束。这会导致内存中驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

为了解决以上问题，出现了虚拟内存：

基于局部性原理，在程序装入时，可以将程序中很快就会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
在操作系统的管理下，在用户看起来似乎有一个比实际内存大得多的内存，这就是虚拟内存。（实际的物理内存没有变，只是在逻辑上进行了扩充）

除了以上考虑，还有：

如果你是电子相关专业的，肯定在大学里捣鼓过单片机。单片机是没有操作系统的，所以每次写完代码，都需要借助工具把程序烧录进去，这样程序才能跑起来。另外，单片机的 CPU 是直接操作内存的「物理地址」。在这种情况下，要想在内存中同时运行两个程序是不可能的。如果第一个程序在 2000 的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容，所以同时运行两个程序是根本行不通的，这两个程序会立刻崩溃。操作系统是如何解决这个问题呢？这里关键的问题是这两个程序都引用了绝对物理地址，而这正是我们最需要避免的。我们可以把进程所使用的地址「隔离」开来，即让操作系统为每个进程分配独立的一套「虚拟地址」，人人都有，大家自己玩自己的地址就行，互不干涉。但是有个前提每个进程都不能访问物理地址，至于虚拟地址最终怎么落到物理内存里，对进程来说是透明的，操作系统已经把这些都安排的明明白白了。 操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。 如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。于是，这里就引出了两种地址的概念：

我们程序所使用的内存地址叫做虚拟内存地址（Virtual Memory Address）
实际存在硬件里面的空间地址叫物理内存地址（Physical Memory Address）。

操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存，如下图所示：操作系统是如何管理虚拟地址与物理地址之间的关系？主要有两种方式，分别是内存分段和内存分页。

3.2 局部性原理

👨‍💻面试官 ：要想更好地理解虚拟内存技术，必须要知道计算机中著名的局部性原理。另外，局部性原理既适用于程序结构，也适用于数据结构，是非常重要的一个概念。
🙋 我：局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。

以下内容摘自《计算机操作系统教程》第 4 章存储器管理。

早在 1968 年的时候，就有人指出我们的程序在执行的时候往往呈现局部性规律，也就是说在某个较短的时间段内，程序执行局限于某一小部分，程序访问的存储空间也局限于某个区域。

局部性原理表现在以下两个方面：

时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。

3.3 虚拟内存的技术实现

👨‍💻面试官 ：虚拟内存技术的实现呢？
🙋 我：虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。（在其基础上加入请求调页（或请求调段）功能、页面置换（或段置换）功能。虚拟内存的实现有以下三种方式：

请求分页存储管理 ：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分页即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
请求分段存储管理 ：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。请求分段存储管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
请求段页式存储管理

这里多说一下？很多人容易搞混请求分页与分页存储管理，两者有何不同呢？
请求分页存储管理建立在分页管理之上。他们的根本区别是是否将程序全部所需的全部地址空间都装入主存，这也是请求分页存储管理可以提供虚拟内存的原因，我们在上面已经分析过了。

它们之间的根本区别在于是否将一作业的全部地址空间同时装入主存。请求分页存储管理不要求将作业全部地址空间同时装入主存。基于这一点，请求分页存储管理可以提供虚存，而分页存储管理却不能提供虚存。

不管是上面那种实现方式，我们一般都需要：

一定容量的内存和外存：在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了；
缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；
虚拟地址空间 ：逻辑地址到物理地址的变换。

3.4 页面置换算法

👨‍💻面试官 ：虚拟内存管理很重要的一个概念就是页面置换算法。那你说一下 页面置换算法的作用？常见的页面置换算法有哪些?
🙋 我：
地址映射过程中，若在页面中发现所要访问的页面不在内存中，则发生缺页中断。

缺页中断 就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。在这个时候，被内存映射的文件实际上成了一个分页交换文件。

当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。用来选择淘汰哪一页的规则叫做页面置换算法，我们可以把页面置换算法看成是淘汰页面的规则。页面的换入换出需要磁盘IO，会有较大开销，因此好的页面置换算法应该追求更少的缺页率。

OPT 页面置换算法（最佳置换算法） ：最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。一般作为衡量其他置换算法的方法。
FIFO（First In First Out）页面置换算法（先进先出页面置换算法） : 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。
LRU （Least Currently Used）页面置换算法（最近最久未使用页面置换算法） ：LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。
为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
```
4，7，0，7，1，0，1，2，1，2，6
```
LFU （Least Frequently Used）页面置换算法（最少使用页面置换算法） : 该置换算法选择在之前时期使用最少的页面作为淘汰页。

4. 分页管理

4.1 基本概念

4.2 基本地址映射
在分页系统中，由逻辑地址转换为物理地址需要
- ① 计算逻辑地址对应的页号；-> 逻辑地址/页面长度
- ② 知道该页号在内存中的起始地址；->页表
- ③ 算出逻辑地址在页面内的偏移量。 ->逻辑地址%页面长度
- 这样的话 物理地址=页面始址+页内偏移量
内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页号（程序地址空间）和页框号（物理内存空间）的映射表。
- 一个进程对应一张页表，
- 进程的每一页对应一个页表项，每个页表项由“页号”和“块号”组成；
- 页表记录进程页面和实际存放的内存块之间的对应关系；
- 每个页表的长度是相同的，页号是隐含的
一个虚拟地址分成两个部分，一部分存储页号，一部分存储偏移量。

4.3 具有快表的地址变换

在基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。因此可以利用这个特性减少访问页表的次数。

为了解决虚拟地址到物理地址的转换速度，操作系统在 页表方案 基础之上引入了快表来加速虚拟地址到物理地址的转换。我们可以把快表理解为一种特殊的高速缓冲存储器（Cache），其中的内容是页表的一部分或者全部内容。作为页表的 Cache，它的作用与页表相似，但是提高了访问速率。由于采用页表做地址转换，读写内存数据时 CPU 要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

快表： 又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放，以加速地址变换的过程。与此对应，内存中的页表常被称为慢表。

对比：

4.4 多级页表

单级页表存在的问题：

页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。-> 拆分多级页表
没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。-> 使用虚拟存储技术，在需要访问页面时才把页面调入内存

引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中。多级页表属于时间换空间的典型场景，具体可以查看下面这篇文章
多级页表如何节约内存：https://www.polarxiong.com/archives/多级页表如何节约内存.html

5. 分段管理

分页是为了提高内存利用率，而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享，数据保护，动态链接等)。

分段内存管理当中，地址是二维的，一维是段号，二维是段内地址；其中每个段的长度是不一样的，而且每个段内部都是从0开始编址的。由于分段管理中，每个段内部是连续内存分配，但是段和段之间是离散分配的，因此也存在一个逻辑地址到物理地址的映射关系，相应的就是段表机制。

6. 分页与分段的比较

共同点
- 分页机制和分段机制都是为了提高内存利用率，减少内存碎片。
- 页和段都是离散存储的，所以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的。
- 单级页表下分页管理和分段管理访问一个逻辑地址都需要两次访存。
区别
- 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
- 地址空间的维度：分页是一维地址空间，分段是二维的（段名，段内地址）。
- 大小是否固定：页的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序。
- 出现的原因：分页主要目的是为了实现离散分配，提高内存利用率；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间，并且有助于信息的共享和保护（为了实现共享，只需让各进程的段表项指向同一个段即可）。
  7. 段页式
  程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分段、分页优缺点分析：

段页式：

地址转换：

段页式地址变换中要得到物理地址须经过三次内存访问：

第一次访问段表，得到页表起始地址；
第二次访问页表，得到物理页号；
第三次将物理页号与页内位移组合，得到物理地址。
8. 交换空间
操作系统把物理内存(physical RAM)分成一块一块的小内存，每一块内存被称为页(page)。当内存资源不足时，Linux把某些页的内容转移至硬盘上的一块空间上，以释放内存空间。硬盘上的那块空间叫做交换空间(swap space)，而这一过程被称为交换(swapping)。物理内存和交换空间的总容量就是虚拟内存的可用容量。

用途：

物理内存不足时一些不常用的页可以被交换出去，腾给系统。
程序启动时很多内存页被用来初始化，之后便不再需要，可以交换出去。

9. 操作系统的几种地址

https://www.bilibili.com/video/BV1rK411p7gv?spm_id_from=333.337.search-card.all.click
操作系统有物理地址、逻辑地址（也叫虚拟地址）、线性地址三种地址

物理地址
在存储器里以字节为单位存储信息，为正确地存放或取得信息，每一个字节单元给以一个唯一的存储器地址，称为物理地址（Physical Address），又叫实际地址或绝对地址。
地址从0开始编号，顺序地每次加1，因此存储器的物理地址空间是呈线性增长的。它是用二进制数来表示的，是无符号整数，书写格式为十六进制数。它是出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果。用于内存芯片级的单元寻址，与处理器和CPU连接的地址总线相对应。
逻辑地址（目前与虚拟地址不做区分）
逻辑地址在计算机体系结构中是指应用程序角度看到的内存单元（memory cell）、存储单元（storage element）、网络主机（network host）的地址。逻辑地址往往不同于物理地址（physical address），通过地址翻译器（address translator）或映射函数可以把逻辑地址转化为物理地址。
在有地址变换功能的计算机中，访问指令给出的地址 (操作数) 叫逻辑地址，也叫相对地址。要经过寻址方式的计算或变换才得到内存储器中的物理地址。把用户程序中使用的地址称为相对地址即逻辑地址。逻辑地址由两个16位的地址分量构成，一个为段基值，另一个为偏移量。两个分量均为无符号数编码。
线性地址（现代操作系统只有一个段，所以有些说法逻辑地址=线性地址）
线性地址（Linear Address）是逻辑地址到物理地址变换之间的中间层。在分段部件中逻辑地址是段中的偏移地址，然后加上基地址就是线性地址。
线性地址是一个32位无符号整数，可以用来表示高达4GB的地址，也就是，高达4294967296个内存单元。线性地址通常用十六进制数字表示，值的范围从0x00000000到0xffffffff）。程序代码会产生逻辑地址，通过逻辑地址变换就可以生成一个线性地址。如果启用了分页机制，那么虚拟地址可以再经过变换以产生一个物理地址。当采用4KB分页大小的时候，虚拟地址的高10位为页目录项在页目录表中的编号，中间10位为页表中的页号，其低12位则为偏移地址。如果是使用4MB分页机制，则高10位页号，低22位为偏移地址。如果没有启用分页机制，那么虚拟地址直接就是物理地址。

三、设备管理

磁盘结构

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

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. 先来先服务

FCFS, First Come First Served

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

2. 最短寻道时间优先

SSTF, Shortest Seek Time First

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

3. 电梯算法

SCAN

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

操作系统面试题

概述