操作系统常见面试题

说一下什么事进程、线程、协程

进程

  • 程序的一次执行过程
  • 一个程序及其数据在处理和顺序执行时所发生的活动
  • 独立的功能的程序在一个数据集合上所运行的过程，他是系统进行资源分配和调度的一个独立单位

线程

  • 操作系统调度的最小单位
  • 一个进程可以包含多个线程、是进程中的实际运行单位
  • 一个线程指的事进程中一个单一顺序的控制流

协程

  • 用户态内执行，并不是在操作系统内执行的
  • 一个线程可以包括多个协程
  • 在java中没有实习协程、但是在python、lua等一些语言中使用协程

线程中哪些资源是共享，哪些资源不共享

线程共享资源

  • 堆
    • 由于堆是在进程空间中开辟出来的，所以它是被该进程中的线程所共享的；
    • 堆中主要存放对象实例，栈中主要存放各种基本数据类型、对象的引用指针
  • 全局变量
    • 它是与某一函数无关的，与特定线程无关的，因此也是共享的
  • 静态变量
    • 虽然对局部变量来说，他在代码中是在函数中的，但是其存放位置和全部变量一样，存于堆中开辟的位置
  • 文件等公用资源
    • 这个是共享的，使用这些公共资源的线程必须同步。win32提供了几种同步资源的方式，包括信号、临界区、事件和互斥体

线程非共享

  • 栈
  • 寄存器
  • 程序计数器

进程状态

进程的三种基本状态

  1. 就绪（Ready）
    1. 这里指已处于准备好的状态，即进程已分配到除了cpu以外的所有必要资源后，只要再获得cpu，就立即可以执行
  2. 执行（Running）
    1. 这时指进程已获得cpu，其程序正在执行的状态。对于任何一个时刻而言，在单处理机系统中，只有一个进程处于执行状态，在多处理机系统中，则可有多个进程处于执行状态
  3. 阻塞（Block）
    1. 正在执行的进程由于发生某事件（如I/O请求，申请缓冲区失败等）暂时无法继续执行的状态，也就是进程的执行收到阻塞

三种基本状态的转换

image.png

  • 执行–>就绪 正在执行的进程（当前进程）如果因分配给他的时间片已经被用完而被剥夺处理机暂停执行时，其状态便由执行转为就绪；

  • 执行–>阻塞 如果因发生某事件，致使当前进程的执行受阻（例如进程访问某临界资源，而改组元正被其他进程访问时），试纸无法继续执行，则该进程状态将由执行转变为阻塞。

  • 阻塞–>就绪 进程所等待的事件已经发生，就进入就绪队列

  • 就绪–>执行 CPU空闲时被调度选中一个就绪进程执行。

进程通信

进程通信的方式有哪些

管道通讯

  • 管道是针对于本地计算机的两个进程之间的通信而设计的通信方法，建立管道后，实际获得两个文件描述符：一个用于读取而另一个用于写入
  • 最常见的 IPC 机制，通过 pipe 系统调用
  • 管道是单工的，数据只能向一个方向流动，需要双向通信时，需要建立起两个管道
  • 数据的读出和写入：
    • 一个进程向管道中写的内容被管道另一端的进程读出。
    • 写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据
    • 当管道中没有信息的话，从管道中读取的进程会等待，直到另一端的进程放入信息。
    • 当管道被放满信息的时候，尝试放入信息的进程会等待，直到另一端的进程取出信息。
    • 当两个进程都终结的时候，管道也自动消失
  • 管道实际上就是建立在内核区域的一块缓存(buffer)
匿名管道（PIPE）
  • 在关系进程中进行（父进程和子进程、兄弟进程之间）
  • 由 pipe 系统调用，管道由父进程建立
  • 管道位于内核空间，其实是一块缓存
命名管道（FIFO）
  • 两个没有任何关系的进程之间通信可通过命名管道进行数据传输，本质是内核中的一块缓存，另在文件系统中以一个特殊的设备文件（管道文件）存在
  • 通过系统调用 mkfifo 创建

消息队列

分为两种方式：

直接通讯方式：消息直接挂到接收方的消息队列里

间接（信箱）通信方式：消息发送到中间体（信箱）

共享内存

映射一段能被其他进程所访问的内存

这段共享空间要互斥的访问

分为两种方式：

基于数据结构的空间（低级）

基于存储区的共享空间（高级）

信号量

信号量的本质是计数器，用于多进程对共享数据对象的访问

在进程访问临界资源之前，需要测试信号量，如果为正数，则信号量-1并且进程可以进入临界区，若为非正数，则进程挂起放入等待队列，直至有进程退出临界区，释放资源并+1信号量，此时唤醒等待队列的进程。

信号量本身就是临界资源，所以必须是原子操作。

套接字通信

套接字：套接口也是一种进程间的通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

无名管道和有名管道的联系和区别

联系：

  • 通信数据只存在于内存缓冲页面中
  • 都是办双工通讯

区别：

  • 无名管道是无名的，有名管道是有名的
  • 无名管道只能用于父子进程或兄弟进程之间的通信，而有名管道可用于任意两进程之间通信
  • 无名管道是无形的，即无名管道的inode结构不是在磁盘上存储的，而是临时生成的，而有名管道的inode节点在磁盘上

线程同步

什么事线程同步，为什么有线程同步

线程同步：即当有一个线程在对内存进行操作时，其他线程都不可以对这个内存进行操作，直到该线程完成操作，其他线程才能对该内存地址进行操作，而其他线程又处于等待状态。

线程有可能和其他县城共享一些资源，比如，内存，文件，数据库等。

当多个线程同时读写同一份共享资源的时候，可能会引起冲突。这时候，我们需要引入线程”同步“机制，即各个线程之间要有个先来后到，不能一窝蜂挤上去抢作一团。

线程同步就是指“排队”：几个线程之间要排队，一个一个对共享资源进行操作，而不是同时进行操作。

线程同步的实现方式

  • 互斥量：采用互斥对象机制，只有拥有互斥资源的线程才能有访问公共资源的权限。因为互斥对象只有一个，所有可以保证公共资源不会被多个线程同时访问。
  • 信号量：允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。PV操作
  • 事件（信号）：通过通知操作的方式来保持多线程同步，事件Event内部它包含一个使用计数，两个布尔值，一个表示手动置位事件还是自动置位事件，另一个布尔值用来表示事件有无触发，还可以方便的实现多线程优先级的比较顺序。

调度算法有哪些

页面置换算法

先进先出置换算法（FIFO）：

​ 每次选择淘汰的页面是最早进入内存的页面。
  实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头，页面队列的最大长度取决于系统为进程分配了多少个内存块。
  FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。

最近最久未使用置换算法（LRU）：

每次淘汰的页面是最近最久未使用的页面。
  当需要置换一页时，选择在最近一段时间里没有使用过的页面予以置换。

磁盘调度算法

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

旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）；

寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）；

实际的数据传输时间。

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

先来先服务算法

按照磁盘请求的顺序进行调度。

优点是公平和简单。

缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

最短寻道时间优先算法

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

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

电梯扫描算法

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

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

进程调度算法有哪些

所谓进程调度，就是从进程的就绪队列中按照一定的算法选择一个进程并将CPU分配给他运行，以实现进程的并发执行。这是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

非抢占式进程调度算法

非抢占式调度的意思就是，当进程正在运行时，他就会一直运行，直到该进程完成或发生某个事件而被阻塞，才会把CPU让给其他进程。

对应的，抢占式的意思就是，当进程正在运行的时候，可以被打断，把CPU让给其他进程。

先来先服务 FCFS

先来先服务调度算法（First Come First Serve,FCFS）：按照进程到达的先后顺序进行调度，先到的进程就先被调度，也就是说，等待时间越久的越优先得到服务。

优点：公平、算法实现简单

缺点：对短进程不利。排在长进程后面的短进程需要等待很长时间，短进程的响应时间太长利，用户交互体验会变差。

短任务优先SJF

短任务优先（Shortest Job First, SJF）：每次调度时选择当前已到达的、且运行时间最短的进程。

缺点：短任务优先算法和先来先服务算法恰好相反，先来先服务算法对短进程不利，而短任务优先算法对长进程不利。因为如果一直有短进程到来，那么长进程永远得不到调度，长进程有可能会被饿死，处于一直等待短作业执行完毕的状态

高响应比优先 HRRN

高响应比优先算法（Highest Response Ratio Next，HRRN）：高响应比优先调度算法既考虑了作业的等待时间，有考虑了作业运行时间的调度算法。因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。响应比=（进程的等待时间 + 进程需要的运行时间）/ 进程需要的运行时间。响应比越大，越先得到服务，且响应比会随着进程等待时间逐渐增大，避免进程被饿死的情况发生。

抢占式进程调度算法

抢占式就是指当进程正在运行的时候，可以被打断，把CPU让给其他进程。抢占的原则一般有三种，分别是时间片原则、优先权原则、短作业优先原则。

  • 优先权原则，指允许优先级高的新到进程抢占当前进程的处理机。

  • 短进程优先原则，指与徐新到的短进程可以抢占当前长进程的处理机。

  • 时间便原则，指各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。

最短时间优先 SRTN

最短剩余时间优先（Shortest Remaining Time Next，SRTN）算法是短任务优先的抢占式版本。

当一个新的进程到达时，把他所需要的整个运行时间与当前进程的剩余运行时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程，否则新的进程等待。

时间片轮转算法 RR

轮转调度算法（Round Robin，RR）也称时间片调度算法：调度程序每次把 CPU 分配给就绪队列首进程使用规定的时间间隔，称为时间片，通常为 10ms ~ 200ms，就绪队列中的每个进程轮流地运行一个时间片，当时间片耗尽时就强迫当前运行进程让出 CPU 资源，转而排到就绪队列尾部，等待下一轮调度。所以，一个进程一般都需要多次轮转才能完成。

轮转调度算法对每个进程都一视同仁，就好比大家都排好队，一个一个来，每个人都运行一会儿再接着重新排队等待运行。

需要注意的是：时间片的长度是一个很关键的因素：

  • 如果时间片设置得太短，就会导致频繁的进程上下文切换，降低了 CPU 效率；
  • 如果时间片设置得太长，那么随着就绪队列中进程数目的增加，轮转一次消耗的总时间加长，即每隔进程的相应速度放慢。甚至时间片大到让进程足以完成其所有任务，RR 调度算法便退化成 FCFS 算法。

最高优先级 HPF

RR 调度算法对所有的进程都是相同的策略，如果用户进程太多，可能会导致内核的服务进程响应跟不上。而在操作系统中，内核进程是比用户进程重要的多的，毕竟它关乎整个系统的稳定性。

最高优先级调度算法（Highest Priority First，HPF）就是从就绪队列中选择最高优先级的进程进行运行。进程的优先级是怎么规定的呢？分为静态优先级或动态优先级：

  • 静态优先级：创建进程时候，就预先规定优先级，并且整个运行过程中该进程的优先级都不会发生变化。一般来说，内核进程的优先级都是高于用户进程的。
  • 动态优先级：根据进程的动态变化调整优先级。比如随着进程的运行时间增加，适当的降低其优先级；随着就绪队列中进程的等待时间增加，适当的升高其优先级。

另外，需要注意的是，最高优先级算法并非是固定的抢占式策略或非抢占式，系统可预先规定使用哪种策略：

  • 非抢占式：当就绪队列中出现优先级高的进程，则运行完当前进程后，再选择该优先级高的进程。
  • 抢占式：当就绪队列中出现优先级高的进程，则立即强制剥夺当前运行进程的 CPU 资源，分配给优先级更高的进程运行。

死锁

什么是死锁

死锁是指两个或两个以上的进程中，由于竞争资源而造成的一种阻塞的现象，若无外力作用，他们都将无法推进下去。此时称系统处于死锁状态或者系统产生了死锁，这些永远在相互等待的进程成为死锁进城。

如果一组进程中的每一个进程都在等待仅由改组进程中的其他进程才能引发的事件，那么该组进城是死锁的。

产生死锁的原因

死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。

  • 竞争不可抢占资源引起死锁
  • 竞争可消耗资源引起死锁
  • 进城推进顺序不当引起死锁

死锁产生的四个必要条件

  • 互斥条件

    • 进程对所分配的资源进行排他性使用，即在一段时间内，某资源只能被一个进程占用。如果此时还有其他进程请求该资源，则请求进程只能等待，直至占有该资源的进程用完释放

  • 请求和保持条件。

    • 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进城占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

  • 不可抢占条件。

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

  • 循环等待条件。

    • 在发生死锁时，必然存在一个进程——资源的循环链，即进程集合（P0，P1，P2….，Pn）中的P0正在等待一个P1占用的资源，P1正在等待P2占用的资源，….，Pn正在等待已被P0占用的资源

处理死锁的方法

  1. 预防死锁

    设置某些限制条件，去破坏产生死锁的几个必要条件中的一个或者几个来预防产生死锁。

  2. 避免死锁

    并不是事先采取各种限制措施，去破坏死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免死锁。

  3. 检测死锁

    这种方法无需事先采取任何限制性措施，允许进程在运行过程中发生死锁。但是可以通过检测机构及时的检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。

  4. 解除死锁

    当检测到系统中已发生死锁时，就采取响应措施，将进程从死锁状态中解除出来。常用的方法是撤销一些进程，回收他们的资源，将他们分配给已处于阻塞状态的进程，使其能继续运行（抢占资源、终止进城）。