一 操作系统基础

1、什么是操作系统

操作系统（Operating System，简称 OS）是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。其主要作用是管理好这些设备，提高它们的利用率和系统的吞吐量，并为用户和应用程序提供一个简单的接口，便于用户使用。OS是现代计算机系统中最基本和最重要的系统软件，而其它的诸如编译程序、数据库系统管理系统等系统软件，以及大量的应用软件，都直接依赖于操作系统的支持，取得它所提供的服务。

2、操作系统的作用

• OS作为用户与计算机硬件系统之间的接口
• OS作为计算机系统资源的管理者
• OS实现了对计算机资源的抽象

3、操作系统的内核

操作系统的内核（Kernel）是操作系统的核⼼部分，它负责系统的内存管理，硬件设备的管理，⽂件系统的管理以及应⽤程序的管理。 内核是连接应⽤程序和硬件的桥梁，决定着系统的性能和稳定性。

4、内核态和系统态

为了防止OS本身及关键数据（如PCB等）遭受到应用程序有意或无意的破坏，通常将处理机的执行状态分成系统态和用户态两种：

• 系统态（内核态）：它具有较高的特权，能执行一切指令，访问所有寄存器的存储区，传统的OS都在系统态运行。
• 用户态：它是具有较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区。

一般情况下，应用程序只能在用户态运行，不能执行OS指令及访问OS区域，这样可以防止应用程序对OS的破坏。

5、什么是系统调用

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

6、系统调用的类型

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

二 进程和线程

1、进程和线程的概念

• 进程：程序执行时的一个实例，每个进程都有独立的内存地址空间，是系统进行资源分配和调度的基本单位。
• 线程：进程中的一个实体，比进程更加轻量，是CPU 调度和分派的基本单位。

2、进程和线程的区别

• 本质：进程是操作系统资源分配的基本单位；线程是任务调度和执行的基本单位。
• 内存分配：系统在运行的时候会为每个进程分配不同的内存空间，建立数据表来维护代码段、堆栈段和数据段；除了 CPU 外，系统不会为线程分配内存，线程所使用的资源来自其所属进程的资源。
• 资源拥有：进程之间的资源是独立的，无法共享；同一进程的所有线程共享本进程的资源，如内存，CPU，IO 等
• 开销：每个进程都有独立的代码和数据空间，程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行程序计数器和栈，线程之间切换的开销小。
• 通信：进程间 以IPC（管道，信号量，共享内存，消息队列，文件，套接字等）方式通信 ；同一个进程下，线程间可以共享全局变量、静态变量等数据进行通信，做到同步和互斥，以保证数据的一致性。
• 调度和切换：线程上下文切换比进程上下文切换快，代价小。
• 执行过程：每个进程都有一个程序执行的入口，顺序执行序列；线程不能够独立执行，必须依存在应用程序中，由程序的多线程控制机制控制。
• 健壮性：每个进程之间的资源是独立的，当一个进程崩溃时，不会影响其他进程；同一进程的线程共享此线程的资源，当一个线程发生崩溃时，此进程也会发生崩溃，稳定性差，容易出现共享与资源竞争产生的各种问题，如死锁等
• 可维护性：线程的可维护性，代码也较难调试，bug 难排查。

3、进程有哪几种状态

1. 创建状态(new) ：进程正在被创建，尚未到就绪状态。
2. 就绪状态(ready) ：进程已处于准备运⾏状态，即进程获得了除了处理器之外的⼀切所需资源，⼀旦得到处理器资源(处理器分配的时间⽚)即可运⾏。
3. 运⾏状态(running) ：进程正在处理器上上运⾏(单核 CPU 下任意时刻只有⼀个进程处于运⾏状态)。
4. 阻塞状态(waiting) ：⼜称为等待状态，进程正在等待某⼀事件⽽暂停运⾏如等待某资源为可⽤或等待 IO 操作完成。即使处理器空闲，该进程也不能运⾏。
5. 结束状态(terminated) ：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运⾏。

4、进程间的通信方式

1. 管道/匿名管道(Pipes) ：⽤于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
2. 有名管道(Names Pipes) : 匿名管道由于没有名字，只能⽤于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循先进先出(first in first out)。有名管道以磁盘⽂件的⽅式存在，可以实现本机任意两个进程通信。
3. 信号(Signal) ：信号是⼀种复杂的通信⽅式，⽤于通知接收进程某个事件已经发⽣；
4. 消息队列(Message Queuing) ：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（⽆名管道：只存在于内存中的⽂件；命名管道：存在于实际的磁盘介质或者⽂件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除⼀个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不⼀定要以先进先出的次序读取,也可以按消息的类型读取.⽐ FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载⽆格式字节流以及缓冲区⼤⼩受限等缺。
5. 信号量(Semaphores) ：信号量是⼀个计数器，⽤于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信⽅式主要⽤于解决与同步相关的问题并避免竞争条件。
6. 共享内存(Shared memory) ：使得多个进程可以访问同⼀块内存空间，不同进程可以及时看到对⽅进程中对共享内存中数据的更新。这种⽅式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有⽤的进程间通信⽅式。
7. 套接字(Sockets) : 此⽅法主要⽤于在客户端和服务器之间通过⽹络进⾏通信。套接字是⽀持 TCP/IP 的⽹络通信的基本操作单元，可以看做是不同主机之间的进程进⾏双向通信的端点，简单的说就是通信的两⽅的⼀种约定，⽤套接字中的相关函数来完成通信过程。

5、线程间的同步方式

线程同步是两个或多个共享关键资源的线程的并发执⾏，同步线程是为了避免关键资源的使⽤冲突。
操作系统⼀般有下⾯三种线程同步的⽅式：

1. 互斥量(Mutex)：采⽤互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有⼀个，所以可以保证公共资源不会被多个线程同时访问。⽐如 Java 中的synchronized 关键词和各种 Lock 都是这种机制。
2. 信号量(Semphares) ：它允许同⼀时刻多个线程访问同⼀资源，但是需要控制同⼀时刻访问此资源的最⼤线程数量。
3. 事件(Event) :Wait/Notify：通过通知操作的⽅式来保持多线程同步，还可以⽅便的实现多线程优先级的比较操作。

6、进程调度方式

1. 非抢占方式
   在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。
2. 抢占方式
   这种调度方式允许调度程序根据某种规则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。“抢占”不是一种任意性行为，必须遵循一定的原则，主要原则有：
   • 优先权原则：允许优先级高的新到进程抢占当前进程的处理机。
   • 短进程优先原则：允许新到的短进程抢占当前进程的处理机。
   • 时间片原则：各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。

7、进程的调度算法

进度调度的任务主要有三：保存处理机的现场信息；按某种算法选取进程；把处理器分配给进程。
这里的“某种算法”就是进程的调度算法。

• 先到先服务(FCFS)调度算法 : 从就绪队列中选择⼀个最先进⼊该队列的进程为之分配资源，使它⽴即执⾏并⼀直执⾏到完成或发⽣某事件⽽被阻塞放弃占⽤ CPU 时再重新调度。
• 短作业优先(SJF)的调度算法 : 从就绪队列中选出⼀个估计运⾏时间最短的进程为之分配资源，使它⽴即执⾏并⼀直执⾏到完成或发⽣某事件⽽被阻塞放弃占⽤ CPU 时再重新调度。
• 时间⽚轮转调度算法 : 时间⽚轮转调度是⼀种最古⽼，最简单，最公平且使⽤最⼴的算法，⼜称 RR(Round robin)调度。每个进程被分配⼀个时间段，称作它的时间⽚，即该进程允许运⾏的时间。
• 多级反馈队列调度算法 ：前⾯介绍的⼏种进程调度的算法都有⼀定的局限性。如短进程优先的调度算法，仅照顾了短进程⽽忽略了⻓进程 。多级反馈队列调度算法既能使⾼优先级的作业得到响应⼜能使短作业（进程）迅速完成。，因⽽它是⽬前被公认的⼀种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。算法详细：1）设置多个就绪队列，并为每个队列赋予不同的优先级；2）每个队列都采用FCFS算法；3）按队列优先级调度。
• 优先级调度 ： 为每个流程分配优先级，⾸先执⾏具有最⾼优先级的进程，依此类推。具有相同优先级的进程以 FCFS ⽅式执⾏。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

8、死锁的定义、起因、必要条件和处理方法

• 定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。
• 起因：死锁的起因，通常是源于多个进程对资源的争夺。
• 必要条件：产生死锁必须同时具备下面四个必要条件
  1. 互斥条件：一段时间内，某资源只能被一个进程占用，如果此时还有其它进程请求该资源，则请求进程只能等待，直至占用该资源的进程用毕释放。
  2. 请求和保持条件：进程已经保持了一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
  3. 不可抢占条件：进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。
  4. 循环等待条件：在发生死锁时，必然存在一个 进程-资源 的循环链，即进程集合中的正在等待一个占用的资源，正在等待占用的资源，......，正在等待已被占用的资源。
• 处理方法：目前处理死锁的方法可归结为四种
  1. 预防死锁：（待补充）
  2. 避免死锁：（待补充）
  3. 检测死锁：（待补充）
  4. 接触死锁：（待补充）
     上述四种方法，从1到4对死锁的防范程度逐渐减弱，对对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度下降（即并发程度提高）。

三 内存管理

1、操作系统的内存管理主要是做什么？

内存管理的主要任务，是为多道程序的运行提供良好的环境，提高内存的利用率，方便用户使用，并能从逻辑上扩充内存。因此，内存管理应具有内存分配和回收、内存保护、地址映射和内存扩充等功能。

2、内存管理机制

简单分为连续分配管理⽅式和非连续分配管理⽅式这两种。连续分配管理方式是指为⼀个⽤户程序分配⼀个连续的内存空间，常见的如 分区管理。连续分配方式会形成许多碎片，虽然可以通过“紧凑”方法将许多碎片拼接成可用的大空间，但须为之付出很大开销，如果允许将一个进程直接分散装入许多不相邻接的分区中，便可充分地利用内存空间，而无须再进行“紧凑” 。基于这一思想而产生了非连续的分配管理方式，非连续分配管理⽅式允许⼀个程序使⽤的内存分布在离散或者说不相邻的内存中，常见的如页式管理、段式管理及“段页式管理”。

1. 分区管理 ： 远古时代的计算机操系统的内存管理⽅式。将内存的用户空间分若干个分区（大小固定或动态），每
   个分区中只包含⼀个进程。如果程序运⾏需要内存的话，操作系统就分配给它一个分区，如果程序运⾏只需要很小的空间的话，分配的这块内存很⼤⼀部分⼏乎被浪费了。这些在每个块中未被利⽤的空间，我们称之为碎片。
2. 页式管理 ：在该方式中，将用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”。相应地，也将内存空间分为若干个物理块或页框（frame），页和块的大小相同。这样可将用户程序的任一页放入任一物理块中，实现了离线分配。系统为每个进程建立了一张页面映射表，简称页表，页表的作用是实现从页号到物理块号的地址映射。
3. 段式管理 ： 这是为了满足用户要求而形成的一种内存管理方式。它把用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。例如，有主程序段MAIN、子程序段X、数据段D及栈段S等。在内存分配时，以段为单位，这些段在内存中可以不相邻接，所以也同样实现了离散分配。系统为每个进程建立一张段映射表，简称段表，段表项记录了该段在内存中的起始地址（又称“基址”）和段的长度，段表的作用是实现从逻辑段到物理内存区的映射的。
4. 段页式管理：
   段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是先将用户程序分成若干段，再把每个段分成若干页，并为每一个段赋予一个段名。

3、块表和多级页表

快表
由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要访问两次内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据（或向此地址中写入数据）。
为了提高地址变换速度，操作系统在页表方案基础之上引入了快表来加速虚拟地址到物理地址的转换。
快表可以看作页表的一种缓存，用以存放当前访问的那些页表项。
使用快表之后的地址转换流程是这样的：

1. 根据虚拟地址中的页号查找快表；
2. 如果该页在快表中，直接从快表中读取相应的物理地址；
3. 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该表项添加到快表中；
4. 当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

多级页表
引⼊多级页表的主要⽬的是为了避免把全部页表⼀直放在内存中占⽤过多空间，特别是那些根本就不需要的页表就不需要保留在内存中。

4、段页式管理机制的地址变换过程

在段页式系统中，为了获得一条指令或数据，须三次访问内存。
第一次访问是访问内存中的段表，从中取得页表始址；
第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；
第三次访问才是珍重从第二次访问所得的地址中取出指令或数据。

5、分页机制和分段机制的共同点和区别

1. 共同点
   • 分页机制和分段机制都是为了提⾼内存利⽤率，减少内存碎⽚。
   • 页和段都是离散存储的，所以两者都是离散分配内存的⽅式。但是，每个页和段中的内存是连续的。
2. 区别
   • ⻚的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序。
   • 分页仅仅是为了满⾜操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段，数据段，能够更好满⾜用户的需要。

6、逻辑（虚拟）地址与物理地址

1. 为什么要有虚拟地址？

   • 如果直接把物理地址暴露出来的话会带来严重问题，比如可能对操作系统造成伤害以及给同时运⾏多个程序造成困难。
   • 如果没有虚拟地址，在编写程序时，必须要知道程序所在的物理地址空间，这在实际中是难以确定的。而通过虚拟地址可以屏蔽掉物理地址的细节，使程序员只关注程序本身的地址空间。
   • 直接暴露物理地址无法对各个进程能访问的地址空间进行隔离。

2. 通过虚拟地址访问内存有哪些优势

   • 程序可以使⽤⼀系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
   • 程序可以使⽤⼀系列虚拟地址来访问⼤于可⽤物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将物理内存页（通常大小为 4 KB）保存到磁盘⽂件。数据或代码页会根据需要在物理内存与磁盘之间移动。
   • 不同进程使⽤的虚拟地址彼此隔离。⼀个进程中的代码无法更改正在由另⼀进程或操作系统使⽤的物理内存。

7、对换（Swapping）技术

“对换”，是指把内存中暂时不能运行的进程或暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据换入内存。对换是改善内存利用率的有效措施，它可以解决内存紧张问题，直接提高处理机的利用率和系统的吞吐量。

四 虚拟内存

1、什么是虚拟内存

• 广义 ：虚拟内存使得应⽤程序认为它拥有连续的可⽤的内存（⼀个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使⽤虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如 RAM）的使⽤也更有效率。
• 狭义：虚拟内存是现代操作系统中内存管理的一项重要技术，实现内存扩充功能。但该功能并非是从物理上实际地扩大内存地容量，而是从逻辑上实现对内存容量地扩充，让用户感觉到的内存容量比实际内存容量大得多。于是便可以让比内存空间更大的程序运行，或者让更多的用户程序并发运行。这样既满足了用户的需要，又改善了系统的性能。

2、局部性原理

要想更好地理解虚拟内存技术，必须要知道计算机中著名的局部性原理，该原理又表现在以下两个方面：

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

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

3、虚拟存储器的基本工作

基于局部性原理，在程序装入时，可以仅将程序当前要运行的⼀部分装⼊内存，⽽将其他部分留在外存，就可以启动程序执行。由于外存往往比内存⼤很多，所以我们运⾏的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调⼊内存，然后继续执⾏程序。另⼀⽅⾯，操作系统将内存中暂时不使⽤的内容换到外存上，从而腾出空间存放将要调⼊内存的信息。这样，计算机好像为⽤户提供了⼀个比实际内存⼤得多的存储器——虚拟存储器。

4、虚拟内存的技术实现

• 基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。
• 程序在运行时，如果它所要访问的页或段已调入内存，便可继续执行下去；但如果程序所要访问的页或段尚未调入内存（称为缺页或缺段），便发出缺页或缺段的中断请求，此时OS将利用请求调页（段）功能将它们调入内存，以使进程能继续执行下去。
• 如果此时内存已满，无法再装入新的页或段，OS还需要再利用页或段的置换功能，将内存中暂时不用的页或段调至盘上，腾出足够的内存空间后，再将需要访问的页或段调入内存，使程序继续执行下去。
• 这样，便可使一个大的用户程序再较小的内存空间中运行，也可在内存中同时装入更多的进程，使它们并发执行。

5、页面置换算法的作用

当发⽣缺页中断时，如果当前内存中并没有空闲的页⾯，操作系统就必须在内存选择⼀个页面将其移出内存，以便为即将调⼊的页面让出空间。⽤来选择淘汰哪⼀⻚的规则叫做页面置换算法，我们可以把页面置换算法看成是淘汰页面的规则。
置换算法的好坏将直接影响到系统的性能。
不适当的算法可能会导致进程发生“抖动”，即刚被换出的页很快又要被访问，需要将它重新调入，此时又需再选一页调出；而此刚被调出的页很快又被访问，又需将它调入，如此频繁的更换页面，以致一个进程在运行中把大部分时间都花费在页面置换工作上，我们称该进程发生了“抖动”。

产生抖动的原因：

1. 进程分配的物理块数太少
2. 置换算法选择不当
3. 全局置换使抖动传播 ？

7、常见的页面置换算法

• OPT（Optimal）页面置换算法（最佳页面置换算法） ：最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使⽤的，或者是在最⻓时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前⽆法预知进程在内存下的若千页面中哪个是未来最⻓时间内不再被访问的，因而该算法无法实现。⼀般作为衡量其他置换算法的方法。
• FIFO（First In First Out） 页面置换算法（先进先出页面置换算法） ：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进⾏淘汰。
• LRU （Least Currently Used）页面置换算法（最近最久未使⽤⻚⾯置换算法） ：LRU算法赋予每个页面⼀个访问字段，⽤来记录⼀个页面自上次被访问以来所经历的时间 T，当须淘汰⼀个页面时，选择现有页面中其 T 值最大的，即最近最久未使⽤的页面予以淘汰。
• LFU （Least Frequently Used）页面置换算法（最少使⽤页面置换算法） : 该置换算法选择在之前时期使⽤最少的页面作为淘汰页。