操作系统-面试篇

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

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

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

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

操作系统有哪些分类？

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

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

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

什么是内核态和用户态？

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

内核态是操作系统管理程序执行时所处的状态，能够执行包含特权指令在内的一切指令，能够访问系统内所有的存储空间。

用户态是用户程序执行时处理器所处的状态，不能执行特权指令，只能访问用户地址空间。

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

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

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

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

并发和并行的区别

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

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

什么是进程？

进程是资源分配的基本单位，是独立运行的单位。

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

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

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

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

进程的基本操作

在unix中，进程的相关操作如下。

1. 进程的创建：fork(),新创建的子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的(但是独立的)一份副本，包括代码和数据段、堆、共享库以及用户栈。
2. 回收子进程：当一个进程由于某种原因终止时，内核并不是立即把它从系统中清除。相反，进程被保持在一种已终止的状态中，直到被它的父进程回收（reaped）。当父进程回收已终止的子进程时，内核将子进程的退出状态传递给父进程，然后抛弃已终止的进程。
3. 加载并运行程序: execve 函数在当前进程的上下文中加载并运行一个新程序.
4. 进程终止: void exit(int status);

简述进程间通信方法

每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到.

所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程A把数据从用户空间拷到内核缓冲区,进程B再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信。

不同进程间的通信本质：进程之间可以看到一份公共资源；而提供这份资源的形式或者提供者不同，造成了通信方式不同。

进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。

进程如何通过管道进行通信

管道是一种最基本的IPC机制，作用于有血缘关系的进程之间，完成数据传递。调用pipe系统函数即可创建一个管道。有如下特质：

1. 其本质是一个伪文件(实为内核缓冲区)
2. 由两个文件描述符引用，一个表示读端，一个表示写端。
3. 规定数据从管道的写端流入管道，从读端流出。

管道的原理: 管道实为内核使用环形队列机制，借助内核缓冲区实现。

管道的局限性：

数据自己读不能自己写。

1. 数据一旦被读走，便不在管道中存在，不可反复读取。
2. 由于管道采用半双工通信方式。因此，数据只能在一个方向上流动。
3. 只能在有公共祖先的进程间使用管道。

进程如何通过共享内存通信？

它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。

进程如何通过共享内存通信？

它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。

特点：

1. 共享内存是最快的一种IPC，因为进程是直接对内存进行操作来实现通信，避免了数据在用户空间和内核空间来回拷贝。
2. 因为多个进程可以同时操作，所以需要进行同步处理。
3. 信号量和共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

什么是信号

一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件。 Linux 系统上支持的30 种不同类型的信号。 每种信号类型都对应于某种系统事件。低层的硬件异常是由内核异常处理程序处理的，正常情况下，对用户进程而言是不可见的。信号提供了一种机制，通知用户进程发生了这些异常。

1. 发送信号：内核通过更新目的进程上下文中的某个状态，发送（递送）一个信号给目的进程。发送信号可以有如下两种原因：
   • 内核检测到一个系统事件，比如除零错误或者子进程终止。
   • —个进程调用了kill 函数， 显式地要求内核发送一个信号给目的进程。一个进程可以发送信号给它自己。
2. 接收信号：当目的进程被内核强迫以某种方式对信号的发送做出反应时，它就接收了信号。进程可以忽略这个信号，终止或者通过执行一个称为信号处理程序(signal handler)的用户层函数捕获这个信号。

如何编写正确且安全的信号处理函数

1. 处理程序要尽可能简单。
2. 在处理程序中只调用异步信号安全的函数。
3. 保存和恢复errno。
4. 阻塞所有的信号，保护对共享全局数据结构的访问。
5. 用volatile 声明全局变量。 考虑一个处理程序和一个main 函数，它们共享一个全局变量g 。
6. 用sigatomict声明标志。在常见的处理程序设计中，处理程序会写全局标志来记录收到了信号。
7. 信号的一个与直觉不符的方面是未处理的信号是不排队的。

进程调度的时机

1. 当前运行的进程运行结束。
2. 当前运行的进程由于某种原因阻塞。
3. 分时系统中，分给当前进程的时间片用完。
4. 执行完系统调用等系统程序后返回用户进程。
5. 在使用抢占调度的系统中，具有更高优先级的进程就绪时。

不能进行进程调度的情况

1. 在中断处理程序执行时。
2. 在操作系统的内核程序临界区内。
3. 其它需要完全屏蔽中断的原子操作过程中。

进程的调度策略

先到先服务调度算法

短作业优先调度算法

优先级调度算法

时间片轮转调度算法

高响应比优先调度算法

多级队列调度算法

多级反馈队列调度算法

进程调度策略的基本设计指标

CPU利用率。

系统吞吐率，即单位时间内CPU完成的作业的数量。

响应时间。

周转时间：等待时间+运行时间

是指作业从提交到完成的时间间隔。从每个作业的角度看，完成每个作业的时间也是很关键

平均周转时间

带权周转时间：作业运行时间/(周转时间)

平均带权周转时间

进程的状态与状态转换

进程在运行时有三种基本状态：就绪态、运行态和阻塞态。

1. 就绪态：进程具备运行条件，等待系统分配处理器以便运行的状态。
2. 运行态：进程占有处理器正在运行的状态。
3. 阻塞（wait）态：又称等待态或睡眠态，指进程不具备运行条件，正在等待某个时间完成的状态。

各状态之间的转换：

• 就绪→执行 处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
• 执行→就绪 处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。
• 执行→阻塞 正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
• 阻塞→就绪 处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。

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

孤儿进程： 父进程退出，子进程还在运行的这些子进程都是孤儿进程，孤儿进程将被init进程（1号进程）所收养，并由init进程对他们完成状态收集工作。

僵尸进程： 进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait 获waitpid 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中的这些进程是僵尸进程。

什么是线程？

1. 线程是cpu调度的基本单位，是进程中的一个任务。用于保证程序的实时性，实现进程内部的并发。
2. 线程是操作系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。
3. 每个线程完成不同的任务，但是属于同一个进程的不同线程之间共享同一地址空间（也就是同样的动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。

为什么需要线程？

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

1. 进程在同一时刻只能做一个任务，很多时候不能充分利用CPU资源。
2. 进程在执行的过程中如果发生阻塞，整个进程就会挂起，即使进程中其它任务不依赖于等待的资源，进程仍会被阻塞。 引入线程之后
3. 从资源上来讲，开辟一个线程所需要的资源要远小于一个进程。
4. 从切换效率上来讲，运行于一个进程中的多个线程，它们之间使用相同的地址空间，而且线程间彼此切换所需时间也远远小于进程间切换所需要的时间
5. 从通信机制上来讲，线程间方便的通信机制，而进程之间要进行数据和信息传递还需要进程间的通信。

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

1. 一个线程只属于一个进程，而一个进程可以有多个线程，但至少有一个线程，线程依赖于进程而存在。
2. 进程在执行过程中拥有独立的地址空间，而多个线程共享进程的地址空间。资源分配给进程，同一进程的所有线程共享该进程的所有资源，同一进程的所有线程共享 代码段， 数据区，堆，但是每个线程有自己的程序计数器和栈。
3. 进程是资源分配的最小单位，线程是CPU调度的最小单位。
4. 通信，因为统一进程的多个线程具有相同的地址空间，线程间的通信可以直接通过读写共享的数据区 即可，而进程通信IPC。
5. 进程变成调试简单可靠，创建销毁大。线程正相反，开销小切换快，单挑时复杂。
6. 进程间不会相互影响；一个进程内某个线程挂掉将导致整个进程挂掉。
7. 进程适应于多核、多机分布；线程适用于多核。

进程和线程的基本API

多线程模型

1. 多对一模型。将多个用户级线程映射到一个内核级线程上。
2. 一对一模型。将内核线程与用户线程一一对应。
3. 多对多模型。将多个用户级线程映射到多个内核级线程上。

进程同步的方法

操作系统中，进程是具有不同的地址空间的，两个进程是不能感知到对方的存在的。有时候需要多个进程共同协作完成一些任务，会存在一些进程执行的先后的顺序问题，所以进程需要操作系统进行同步控制。进程同步的方法：

1. 互斥锁
2. 读写锁
3. 条件变量
4. 记录锁(record locking)
5. 信号量
6. 屏障（barrier）

线程同步的方法

遇到竞争的线程同时修改同一数据或是协作的线程设置同步点的问题时，需要使用一些线程同步的方法来解决这些问题。

线程同步的方法：

1. 互斥锁
2. 读写锁
3. 条件变量
4. 自旋锁
5. 信号量
6. 屏障（barrier）

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

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

死锁是怎样产生的？

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

互斥条件：进程对所分配到的资源不允许其他进程访问，一次只能分配到该资源的进程访问。

不可剥夺：进程获得的资源在未使用完之前不可被其他的进程剥夺。

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

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

如何解决死锁问题？

解决死锁的方法即破坏产生死锁的四个必要条件之一：

1. 资源一次性分配，这样就不会再有请求了（破坏请求条件）。
2. 只要有一个资源得不到分配，也不给这个进程分配其他的资源（破坏占有并等待条件）
3. 可抢占资源：即当进程新的资源未得到满足时，释放已占有的资源，从而破坏不可抢占的条件。
4. 资源有序分配法：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反，从而破坏环路等待的条件

什么是虚拟地址，什么是物理地址？

地址空间是一个非负整数地址的有序集合。

在一个带虚拟内存的系统中，CPU 从一个有N=pow(2,n)个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间（virtual address space）。

一个系统还有一个物理地址空间（physical address space），对应于系统中物理内存的M 个字节。

地址空间的概念是很重要的，因为它清楚地区分了数据对象（字节）和它们的属性（地址）。

主存中的每字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

什么是虚拟内存？

虚拟内存提供了三个重要的能力：

1. 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。看上去的相似增大了内存的空间，实际是主存与磁盘交互的结果。
2. 它为每个进程提供了一致的地址空间，从而简化了内存管理。
3. 它保护了每个进程的地址空间不被其他进程破坏。

为什么要引入虚拟内存？

1. 虚拟内存作为缓存的工具
   • 虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组
   • 虚拟内存利用DRAM缓存来自通常更大的虚拟地址空间的页面。
2. 虚拟内存作为内存管理的工具。
3. 简化链接
4. 简化加载： 虚拟内存还使得容易向内存中加载可执行文件和共享对象文件
5. 加载器从不在磁盘到内存实际复制任何数据，在每个页初次被引用时，虚拟内存系统会按照需要自动的调入数据页。
6. 简化共享： 独立地址空间为OS提供了一个管理用户进程和操作系统自身之间共享的一致机制。

常见的页面置换算法

当访问一个内存中不存在的页，并且内存已满，则需要从内存中调出一个页或将数据送至磁盘对换区，替换一个页，这种现象叫做缺页置换。

1. 先进先出(FIFO)算法：
   • 置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。
2. 最近最少使用（LRU）算法:
   • 置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。
3. 最不常用算法（Least Frequently Used, LFU）
   • 缺页时，置换访问次数最少的页面

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

如果有多个进程要读取它们自己的那部门资源的副本，那么复制是不必要的。每个进程只要保存一个指向这个资源的指针就可以了，因为需要修改的时候，会把复制的拿分提供给进程。不过其中的复制的副本给到要修改的进程。同时其他的进程仍然共享那份没有修改过的资源。所以这就是名称的由来：在写入时进行复制。

写时复制的主要好处：如果进程从来就不需要修改资源，则不需要进行复制。

在使用虚拟内存的情况下，写时复制（Copy-On-Write）是以页为基础进行的。

实时操作系统的概念

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

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

具有最高优先权的进程被低优先级进程阻塞，反而使具有中优先级的进程先于高优先级的进程执行，导致系统的崩溃。这就是所谓的优先级反转。

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

1. 优先级继承(priority inheritance) 优先级继承是指将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级.当高优先级任务由于等待资源而被阻塞时,此时资源的拥有者的优先级将会自动被提升。
2. 优先级天花板(priority ceilings)优先级天花板是指将申请某资源的任务的优先级提升到可能访问该资源的所有任务中最高优先级任务的优先级.(这个优先级称为该资源的优先级天花板)。

简述 select

select是一种多路复用技术。其收到所有输入的文件描述符，返回哪些文件有新数据。

其可以设置为阻塞或者非阻塞状态，底层采用1024位bitmap做实现，因此有文件描述符上限数。

poll

poll是一种多路复用技术。其收到所有输入的文件描述符，返回哪些文件有新数据。

其通过链表代替了之前select的数据结构，使得其没有上限限制。

简述epoll

epoll是一种多路复用技术。其采用一个文件描述符管理多个输入的文件描述符，采用事件回调的方式，提高了程序运行效率。

简述虚拟地址到物理地址转化过程

虚拟地址由虚拟页号和页偏移两部分组成。 通过虚拟地址的页面号，首先在快表中查询是否有该映射，查询不成功，在页表中找到该页对应的物理地址。 然后通过页物理地址+页偏移，得到真实的物理地址,页偏移又叫做页内地址。

简述页表

页表用于存储虚拟地址中的虚拟页面号和物理页面号的映射关系。 除此之外，有些页的读写有限制，页表也通过其他存储位，标记该页访问位，是否在内存中（可能被页面置换出去了）等等。

简述多级页表

多级页表用于减少内存的占用。以二级页表为例，虚拟地址被分为DIR,PAGE和offset三部分，通过顶级页表和DIR，寻找到该二级页表的起始位置，再通过二级页表的起始位置和PAGE，找到页物理地址，最后加上页偏移，即可得到最终的物理地址。

简述块表

快表也称为页表高速缓存。其会存储一定数量的页表项，以此加快虚拟地址到物理地址的映射速度。

简述MMU

MMU即内存管理单元，该硬件负责处理虚拟地址到物理地址的转化工作。快表也存储在MMU上。

进程调度算法

1. 先来先服务调度算法：创建一个任务队列，一旦有新任务就加入这个队列，CPU完成一个任务后就从队列取任务。
2. 短作业(进程)优先调度算法：针对较短的作业，优先调给CPU工作。
3. 时间片轮转算法：每个时间片依次执行一个任务，时间片结束后将该任务放回任务队列。
4. 多级反馈队列：也按时间片轮转算法执行任务，设置n个队列，当第一个队列任务为空，才执行第二个队列，依次类推。 如果在i队列的任务在该时间片执行后没有完成，即插入i+1号队列。

简述进程组

进程组即多个进程的集合,进程组有一个组长,组长进程的PID等于进程组的PGID。

简述协程

协程，即用户态线程。我们知道，在Linux下，线程有PCB，然后可以占用时间片去调度，但是在用户态线程中，该线程的执行不由内核做调度，由用户自己实现。

可以这么理解，在用户进程A中，再实现了个调度器，调度用户线程，这些线程不像之前的线程，内核是感知不到的，它们只能感知到A的存在，用户态线程之间时间片只能争取内核分给进程A的时间片。

IO模型有哪几种

在同步方式上，可以分为同步IO和异步IO。

在阻塞方式上，可以分为阻塞IO和非阻塞IO。

简述阻塞IO

阻塞和非阻塞描述的是调用方在获取消息过程中的状态，阻塞等待还是立刻返回。阻塞io指的是调用方在获取消息的过程中会挂起阻塞，知道获取到消息。

简述非阻塞IO

非阻塞io指的是调用方在获取io的过程中会立刻返回而不进行挂起。

简述同步IO

同步和异步描述的是一种消息通知的机制，主动等待消息返回还是被动接受消息，同步io指的是调用方通过主动等待获取调用返回的结果来获取消息通知。

异步IO

异步io指的是被调用方通过某种方式（如，回调函数）来通知调用方获取消息。

简述信号驱动IO

信号驱动IO即，在内核中注册一个回调函数，当某个事件发生时，内核使用信号，使程序运行回调函数。

简述IO多路复用

IO多路复用，即单线程可以监控多个文件描述符是否能进行IO操作的能力。