操作系统

同步、异步、阻塞、非阻塞的概念

  • 同步：当一个同步调用发出后，调用者要一直等待返回结果。通知后，才能进行后续的执行。

  • 异步：当一个异步过程调用发出后，调用者不能立刻得到返回结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。

  • 阻塞：是指调用结果返回前，当前线程会被挂起，即阻塞。

  • 非阻塞：是指即使调用结果没返回，也不会阻塞当前线程。

什么是IO多路复用？怎么实现？

IO多路复用（IO Multiplexing）是指单个进程/线程就可以同时处理多个IO请求。

实现原理：用户将想要监视的文件描述符（File Descriptor）添加到select/poll/epoll函数中，由内核监视，函数阻塞。一旦有文件描述符就绪（读就绪或写就绪），或者超时（设置timeout），函数就会返回，然后该进程可以进行相应的读/写操作。

IO多路复用

进程控制块（process control block，PCB）？

内容

进程描述信息：

  • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；

  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

  • 进程当前状态，如 new、ready、running、waiting 或 blocked 等；

  • 进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

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

CPU 相关信息：

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

结构

通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

  • 将所有处于就绪状态的进程链在一起，称为就绪队列；

  • 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；

  • 另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

进程和线程的区别？

  • 进程（Process）是系统进行资源分配和调度的基本单位，线程（Thread）是CPU调度和分派的基本单位；

  • 线程依赖于进程而存在，一个进程至少有一个线程；

  • 进程有自己的独立地址空间，线程共享所属进程的地址空间；

  • 进程是拥有系统资源的一个独立单位，而线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈)，和其他线程共享本进程的相关资源如内存、I/O、cpu等；

  • 在进程切换时，涉及到整个当前进程CPU环境的保存环境的设置以及新被调度运行的CPU环境的设置，而线程切换只需保存和设置少量的寄存器的内容，并不涉及存储器管理方面的操作，可见，进程切换的开销远大于线程切换的开销；

  • 线程之间的通信更方便，同一进程下的线程共享全局变量等数据，而进程之间的通信需要以进程间通信(IPC)的方式进行；

  • 多线程程序只要有一个线程崩溃，整个程序就崩溃了，但多进程程序中一个进程崩溃并不会对其它进程造成影响，因为进程有自己的独立地址空间，因此多进程更加健壮

进程的状态转换

三种状态：就绪态、运行态和阻塞态。

  • 就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源

  • 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数

  • 阻塞状态： 进程等待某种条件，在条件满足之前无法执行

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

  • 时间片到：为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；

  • 等待资源：进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；

  • 主动挂起：当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；

  • 优先级抢占：当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；

  • 中断：发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

进程间的通信方式有哪些？

管道

  1. 半双工，具有固定的读端和写端；

  2. 只能父子进程或者兄弟进程之间的进程的通信；

  3. 可以看成是一种特殊的文件，对于它的读写也可以使用普通的 read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。

命名管道

  1. FIFO 可以在无关的进程之间交换数据，与无名管道不同；

  2. FIFO 有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。

消息队列

  1. 消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符 ID 来标识；

  2. 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级；

  3. 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除；

  4. 消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取。

共享内存

  1. 共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区；

  2. 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。

信号量

  1. 信号量（semaphore）是一个计数器。用于实现进程间的互斥与同步，而不是用于存储进程间通信数据；

  2. 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存；

  3. 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作；

  4. 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数；

  5. 支持信号量组。

信号（signal/kill）

  1. 进程间通信机制中唯一的异步通信机制

  2. 处理方式：执行默认操作、捕捉信号、忽略信号

  3. 用于异常情况通信

套接字（Socket）

  1. 可以不同主机间进程通信，也可同一主机中进程通信

  2. 系统调用 

     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 即可；

  3. 通信方式

    • 实现 TCP 字节流通信： socket 类型是 AF_INET 和 SOCK_STREAM；

    • 实现 UDP 数据报通信：socket 类型是 AF_INET 和 SOCK_DGRAM；

    • 实现本地进程间通信： 「本地字节流 socket 」类型是 AF_LOCAL 和 SOCK_STREAM，「本地数据报 socket 」类型是 AF_LOCAL 和 SOCK_DGRAM。

进程调度

批处理系统

  • 先来先服务

  • 最短作业优先

  • 最短剩余时间优先

  • 最高响应比优先

交互式系统

  • 时间片轮转

  • 优先级调度算法

  • 多级反馈队列调度

什么是死锁？

一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁的。资源死锁是竞争性同步问题，通信死锁是协同同步问题。

资源死锁产生的必要条件？

  • 互斥：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。

  • 占用并等待：当进程因请求资源而阻塞时，对已获得的资源保持不放。

  • 不可抢占：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。

  • 环路等待：在发生死锁时，必然存在一个进程–资源的环形链。

如何解决死锁？

预防

  1. 破坏请求条件：一次性分配所有资源，这样就不会再有请求了；

  2. 破坏请保持条件：只要有一个资源得不到分配，也不给这个进程分配其他的资源：

  3. 破坏不可剥夺条件：当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源；

  4. 破坏环路等待条件：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反。

避免

银行家算法

解除

  1. 资源剥夺：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程（但应该防止被挂起的进程长时间得不到资源）；

  2. 撤销进程：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源（撤销的原则可以按进程优先级和撤销进程代价的高低进行）；

  3. 进程回退：让一个或多个进程回退到足以避免死锁的地步。进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

多线程竞争与协作

生产者-消费者问题

生产者-消费者问题描述：

  • 生产者在生成数据后，放在一个缓冲区中；

  • 消费者从缓冲区取出数据处理；

  • 任何时刻，只能有一个生产者或消费者可以访问缓冲区；

三个信号量，分别是：

  • 互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1；

  • 资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；

  • 资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）； 

 #define N 100  semaphore mutex=1;   //互斥信号量，用于临界区的互斥访问  semaphore emptyBuffers=N; //表示缓冲区[空槽l的个数  semaphore fullBuffers=0; //表示缓冲区[满槽]的个数  //生产者线程函数  void producer()  {      while(TRUE)      {          P(emptyBuffers); //将空槽的个数-1          P(mutex);   //进入临界区    put();    //将生成的数据放到缓冲区中          V(mutex);   //离开临界区    V(fullBuffers);  //将满槽的个数+1      }  }    //消费者线程函数  void consumer()  {      while(TRUE)      {          P(ful1Buffers);  //将满槽的个数-1    P(mutex);   //进入临界区    get();    //从缓冲区里读取数据    V(mutex);   //离开临界区    V(emptyBuffers); //将空槽的个数+1      }  }

哲学家就餐问题

  • 一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。

  • 一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。

哲学家就餐问题

读者-写者问题

公平策略：

  • 优先级相同；

  • 写者、读者互斥访问；

  • 只能一个写者访问临界区；

  • 可以有多个读者同时访问临界资源；

读者-写者问题

分页与分段的区别？

  • 页式存储：用户空间划分为大小相等的部分称为页（page），内存空间划分为同样大小的区域称为页框，分配时以页为单位，按进程需要的页数分配，逻辑上相邻的页物理上不一定相邻；

  • 段式存储：用户进程地址空间按照自身逻辑关系划分为若干个段（segment）（如代码段，数据段，堆栈段），内存空间被动态划分为长度不同的区域，分配时以段为单位，每段在内存中占据连续空间，各段可以不相邻；

  • 段页式存储：用户进程先按段划分，段内再按页划分，内存划分和分配按页。

区别：

  • 目的不同：分页的目的是管理内存，用于虚拟内存以获得更大的地址空间；分段的目的是满足用户的需要，使程序和数据可以被划分为逻辑上独立的地址空间；

  • 大小不同：段的大小不固定，由其所完成的功能决定；页的大小固定，由系统决定；

  • 地址空间维度不同：分段是二维地址空间（段号+段内偏移），分页是一维地址空间（每个进程一个页表/多级页表，通过一个逻辑地址就能找到对应的物理地址）；

  • 分段便于信息的保护和共享；分页的共享收到限制；

  • 碎片：分段没有内碎片，但会产生外碎片（不属于当前进程的闲置空间）；分页没有外碎片，但会产生内碎片（一个页填不满）

详细解析：为什么要有虚拟内存

物理地址、逻辑地址、虚拟内存的概念

  1. 物理地址：它是地址转换的最终地址，进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取，是内存单元真正的地址。

  2. 逻辑地址：是指计算机用户看到的地址。例如：当创建一个长度为 100 的整型数组时，操作系统返回一个逻辑上的连续空间：指针指向数组第一个元素的内存地址。由于整型元素的大小为 4 个字节，故第二个元素的地址时起始地址加 4，以此类推。事实上，逻辑地址并不一定是元素存储的真实地址，即数组元素的物理地址（在内存条中所处的位置），并非是连续的，只是操作系统通过地址映射，将逻辑地址映射成连续的，这样更符合人们的直观思维。

  3. 虚拟内存：是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

如何进行地址空间到物理内存的映射？

内存管理单元（MMU）管理着逻辑地址和物理地址的转换，其中的页表（Page table）存储着页（逻辑地址）和页框（物理内存空间）的映射表，页表中还包含包含有效位（是在内存还是磁盘）、访问位（是否被访问过）、修改位（内存中是否被修改过）、保护位（只读还是可读写）。逻辑地址：页号+页内地址（偏移）；每个进程一个页表，放在内存，页表起始地址在PCB/寄存器中。

页面置换算法有哪些？

先进先出置换算法（FIFO）

先进先出，即淘汰最早调入的页面。

最佳置换算法（OPT）

选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。

最近最久未使用（LRU）算法

即选择最近最久未使用的页面予以淘汰

时钟（Clock）置换算法

时钟置换算法也叫最近未用算法 NRU（Not RecentlyUsed）。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。

最不经常使用算法NFU

置换出访问次数最少的页面

动态链接库和静态链接库的理解？

  • 静态链接：编译链接时直接将需要的执行代码拷贝到调用处，优点就是在程序发布的时候就不需要的依赖库，也就是不再需要带着库一块发布，程序可以独立执行，但是体积可能会相对大一些。

  • 动态链接：编译的时候不直接拷贝可执行代码，而是通过记录一系列符号和参数，在程序运行或加载时将这些信息传递给操作系统，操作系统负责将需要的动态库加载到内存中，然后程序在运行到指定的代码时，去共享执行内存中已经加载的动态库可执行代码，最终达到运行时连接的目的。优点是多个程序可以共享同一段代码，而不需要在磁盘上存储多个拷贝，缺点是由于是运行时加载，可能会影响程序的前期执行性能

进程的异常控制流：陷阱、中断、异常和信号？

  • 陷阱是有意造成的“异常”，是执行一条指令的结果。陷阱是同步的。陷阱的主要作用是实现系统调用。比如，进程可以执行 syscall n 指令向内核请求服务。当进程执行这条指令后，会中断当前的控制流，陷入到内核态，执行相应的系统调用。内核的处理程序在执行结束后，会将结果返回给进程，同时退回到用户态。进程此时继续执行下一条指令。

  • 中断由处理器外部的硬件产生，不是执行某条指令的结果，也无法预测发生时机。由于中断独立于当前执行的程序，因此中断是异步事件。中断包括 I/O 设备发出的 I/O 中断、各种定时器引起的时钟中断、调试程序中设置的断点等引起的调试中断等。

  • 异常是一种错误情况，是执行当前指令的结果，可能被错误处理程序修正，也可能直接终止应用程序。异常是同步的。这里特指因为执行当前指令而产生的错误情况，比如除法异常、缺页异常等。有些书上为了区分，也将这类“异常”称为“故障”。

  • 信号是一种更高层的软件形式的异常，同样会中断进程的控制流，可以由进程进行处理。一个信号代表了一个消息。信号的作用是用来通知进程发生了某种系统事件。

什么是用户态和内核态？

用户态和内核态是操作系统的两种运行状态。

  • 内核态：处于内核态的 CPU 可以访问任意的数据，包括外围设备，比如网卡、硬盘等，处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况，一般处于特权级 0 的状态我们称之为内核态。

  • 用户态：处于用户态的 CPU 只能受限的访问内存，并且不允许访问外围设备，用户态下的 CPU 不允许独占，CPU 能够被其他程序获取。

用户程序都运行在用户态，但有时需要进行一些内核态的操作，比如从硬盘或者键盘读数据，这时就需要进行系统调用，使用陷阱指令，CPU切换到内核态，执行相应的服务，再切换为用户态并返回系统调用的结果。

守护进程、僵尸进程和孤儿进程

守护进程

指在后台运行的，没有控制终端与之相连的进程。它独立于控制终端，周期性地执行某种任务。Linux的大多数服务器就是用守护进程的方式实现的，如web服务器进程http等

僵尸进程

一个子进程结束后，它的父进程并没有等待它（调用wait或者waitpid），那么这个子进程将成为一个僵尸进程。僵尸进程是一个已经死亡的进程，但是并没有真正被销毁。它已经放弃了几乎所有内存空间，没有任何可执行代码，也不能被调度，仅仅在进程表中保留一个位置，记载该进程的进程ID、终止状态以及资源利用信息(CPU时间，内存使用量等等)供父进程收集，除此之外，僵尸进程不再占有任何内存空间。这个僵尸进程可能会一直留在系统中直到系统重启。

危害：占用进程号，而系统所能使用的进程号是有限的；占用内存。

解决：

  • 该进程的父进程先结束了。每个进程结束的时候，系统都会扫描是否存在子进程，如果有则用Init进程接管，成为该进程的父进程，并且会调用wait等待其结束。

  • 父进程调用wait或者waitpid等待子进程结束（需要每隔一段时间查询子进程是否结束）。wait系统调用会使父进程暂停执行，直到它的一个子进程结束为止。waitpid则可以加入WNOHANG(wait-no-hang)选项，如果没有发现结束的子进程，就会立即返回，不会将调用waitpid的进程阻塞。同时，waitpid还可以选择是等待任一子进程（同wait），还是等待指定pid的子进程，还是等待同一进程组下的任一子进程，还是等待组ID等于pid的任一子进程；

  • 子进程结束时，系统会产生SIGCHLD(signal-child)信号，可以注册一个信号处理函数，在该函数中调用waitpid，等待所有结束的子进程（注意：一般都需要循环调用waitpid，因为在信号处理函数开始执行之前，可能已经有多个子进程结束了，而信号处理函数只执行一次，所以要循环调用将所有结束的子进程回收）；

  • 可以用signal(SIGCLD, SIG_IGN)(signal-ignore)通知内核，表示父进程忽略SIGCHLD信号，那么子进程结束后，内核会进行回收。

孤儿进程

一个父进程已经结束了，但是它的子进程还在运行，那么这些子进程将成为孤儿进程。孤儿进程会被Init（进程ID为1）接管，当这些孤儿进程结束时由Init完成状态收集工作。

介绍一下几种典型的锁？

读写锁

  • 多个读者可以同时进行读

  • 写者必须互斥（只允许一个写者写，也不能读者写者同时进行）

  • 写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）

互斥锁

一次只能一个线程拥有互斥锁，其他线程只有等待

互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒，而操作系统负责线程调度，为了实现锁的状态发生改变时唤醒阻塞的线程或者进程，需要把锁交给操作系统管理，所以互斥锁在加锁操作时涉及上下文的切换。

条件变量（信号量）

互斥锁一个明显的缺点是他只有两种状态：锁定和非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足，他常和互斥锁一起使用，以免出现竞态条件。当条件不满足时，线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量，他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说互斥锁是线程间互斥的机制，条件变量则是同步机制。

自旋锁

如果进线程无法取得锁，进线程不会立刻放弃CPU时间片，而是一直循环尝试获取锁，直到获取为止。如果别的线程长时期占有锁，那么自旋就是在浪费CPU做无用功，但是自旋锁一般应用于加锁时间很短的场景，这个时候效率比较高。

参考资料

计算机基础知识

操作系统面试题

图解系统介绍 | 小林coding

《现代操作系统》