面试题汇总

操作系统篇

1. 进程和线程的区别

  1. 进程是资源分配的基本单位，属于同一进程的线程共享进程资源
  2. 线程是CPU调度的基本单位，同一进程之间的线程切换，不会引起进程切换，开销很小。不同进程之间的线程切换，会引起进程切换，开销大。
  3. 线程之间的通信更加方便，因为同一进程下的线程共享全局变量、静态变量等数据。

2. 进程的状态和状态之间的转换

状态：

  1. 就绪态
  2. 运行态
  3. 阻塞态

就绪态：进程拥有除cpu以外的所有资源，等待带被调度，被调度了就转成运行态

运行态：

  • 进程正在被cpu处理。如果时间片到了，或者cpu被抢占（可能有更高级别的进程到来，优先被调度），转为就绪态。
  • 如果运行态进程进行系统调用请求某种资源（或等待某一事件发生），则变为阻塞态

阻塞态：还要等待操作系统分配其他资源，当除了CPU以外，其他所需资源全部分配到了，则变为就绪态

  • 阻塞态可以到就绪态

  • 就绪态可以到运行态

  • 运行态可以到阻塞态或者就绪态

3. 进程通信方式

  1. 管道通信（一股脑的写，一股脑的读，不适合频繁通信）

    管道以文件的形式存在，各进程之间要互斥的访问管道。管道是半双工通信，如果要实现双向同时通信，则需要两个管道。

    • 对于匿名管道，只能在父子进程之间通信。匿名管道是特殊文件只存在于内存，没有存在于文件系统中。

    • 对于命名管道，可以在不相关的进程之间进行通信。命名管道是一个真实存在的管道文件。

    缺点：

    管道通信必须写完了才能读，读完了才能写，效率低。假设现在有AB两个进程，A进程将数据写入管道，B进程需要等待A进程将信息写完以后才能读出来，所以这种方案不适合频繁的通信。

  2. 消息队列 （分开写，分开读，不适合大数据传输）

    每个进程都有自己的消息队列，保存在内核中。

    • 进程将要发送的数据分成一个个的消息体，将消息体从用户态拷贝到内核态，将其写入目标进程的消息队列。

    缺点：

    要将数据从用户态拷贝到内核态，不适合大数据传输。

  3. 共享内存

    共享内存就是两个进程使用一块共享内存空间。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度

    缺点：

    多个进程同时修改同一个共享内存，很有可能就冲突了。例如两个进程都同时写一个地址，那先写的那个进程会发现内容被别人覆盖了。（要解决这个问题，可以使用信号量）

  4. 信号量

    信号量其实是一个整型的计数器，代表当前可使用资源的数量。主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据

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

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

  5. 信号

    对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程。

  6. Socket

    跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

4.进程调度算法

  • 先来先服务（FCFS）：先到达的进程先服务，非抢占式。对长作业友好，短作业不友好，不会导致饥饿。

  • 短作业优先（SJF）：运行时间短的作业优先,有抢占式和非抢占式两种。对短作业友好，长作业不友好，可能会导致长作业饥饿。进程的运行时间由用户提供，并不一定真实，不一定是真正的短作业优先

    牛客上看到一位老哥面百度的面试题：

    Q: 操作系统怎么知道哪个是短作业？

    A: 作业运行时间由用户提供。可能一个进程本身是长作业，但是用户告诉操作系统这个进程运行时间很短，这个进程会被优先调度，所以不是真正意义上的短作业优先。

  • 高响应比优先算法（HRRN）: 操作系统计算进程的响应比,响应比高的先调度，非抢占式。响应比 = （等待时间 + 要求服务时间）/ 要求服务时间。

  • 时间片轮转算法（RR)：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，抢占式算法。如果进程没有在一个时间片内执行完，则将进程放入就绪队列队尾重新排队。如果时间片太大，则退化为先来先服务算法。时间片太小，则进程切换过于频繁，增大系统开销。

  • 优先级调度算法：每个进程有各自的优先级，调度时选择优先级高的进程。低优先级的进程可能永远不会被调度，可以随着进程等待时间的增加，提高进程的优先级。

  • 多级反馈队列算法：设置多级就绪队列，各级队列优先级从高到低，时间片从小到大，抢占式调度算法。新进程到达时，先进入第一级队列，如果时间片到了，还没有运行完，则进入第二级队列，以此类推。如果不断的有短进程到达，可能会导致饥饿。

5.进程同步与进程互斥

  • 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
  • 互斥：多个进程在同一时刻只有一个进程能进入临界区。

6.生产者消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

Java实现单生产者单消费者模型

Java实现多生产者多消费者模型

Java解决抽烟者问题

7.什么是死锁

在多个进程环境下，各个进程因资源竞争互相等待对方所持有的资源，导致各个进程都阻塞，这就是死锁。

比如说，

面试官：你先给我解释一下死锁我就给你发offer。

我：你先给我发offer我就解释。

面试官：好，那你回去等通知吧。

8.死锁产生的必要条件

  1. 互斥条件。一个资源每次只能被一个进程使用。
  2. 不可剥夺条件。进程已获得的资源，在未使用完之前，不能强行剥夺，但可以主动释放。
  3. 占有和等待条件。一个进程因请求资源而阻塞时，对已获得的资源保持不放。
  4. 循环等待条件。有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

9.死锁的处理方法

  1. 鸵鸟策略

    • 把头埋在沙子里，假装根本没发生问题。

    • 因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

    • 当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

    • 大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

  2. 预防死锁

    • 破坏互斥条件。让一个资源可以被共享使用。
    • 破坏不可剥夺条件。可以剥夺低优先级进程所持有的资源给高优先级使用。
    • 破坏占有和等待条件。一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
    • 破坏循环等待条件。可以给资源编号，按顺序申请资源。

  3. 避免死锁

    • 安全序列

    • 银行家算法

      1. 检查此时系统剩余的可用资源是否能满足这次请求。
      2. 尝试分配，并检查当前剩余的可用资源是否能满足某个进程的最大需求，如果可以，则进行分配。

  4. 死锁检测和解除

    • 死锁检测算法

      资源分配图

      • 进程节点 --> 资源节点（请求边）

      • 资源节点 --> 进程节点（分配边）

      依次消除与不阻塞进程相连的边。如果最终不能消除所有的边，则发生了死锁。

    • 死锁解除

      • 资源剥夺法，剥夺某些进程所持有的资源。
      • 终止进程法，终止部分进程。
      • 进程回退法，让一个或多个死锁进程回退。

10. 什么是内存？

内存是一种告诉的存储设备。因为cpu的处理速度和从外存读取程序的速度存在很大的差异，所以程序执行前要先将程序放入内存才能被CPU处理，缓和CPU和外存的速度矛盾，提高CPU利用率。

11. 分页与分段

  • 分页

    分页是指将内存空间分为一个个大小相等的分区，每个分区叫做“页框”，典型的页框大小为1KB。

    将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”。

    进程的每一个页面被分别放入到页框里。

    程序使用的仍然是逻辑地址，通过页表加页内偏移计算得到物理地址

  • 分段

    分段是指按照程序自身的逻辑关系划分为若干个段，每个段有一个段名，比如代码段、数据段、堆栈段。

    分段管理很方便按照逻辑模块实现信息的共享和保护。

  • 区别

    • 分页是操作系统为了充分利用内存空间，将程序按页装入内存，是一个系统行为。对程序员透明，无实际逻辑意义，相当于一个碎纸机。分段是按照程序的逻辑意义将程序划分，要程序员显示划分每个段。
    • 页的大小是固定的，由操作系统决定。段的大小不固定，取决于用户编写的程序。
    • 分页是一维的地址空间，分段是二维的

    为什么说分页是一维的，分段是二维的？

    https://blog.csdn.net/yangkuiwu/article/details/53493458

    如果采用分页机制，对于逻辑地址来说，第0页的最后一个地址和第1页的第一个地址在数值上是连续的，因此说分页的地址空间是一维的。

    image-20200805173937511

    如果采用分段机制，这段程序会被编程成多个段，比如数据段、代码段、堆栈段等，每个段的长度不定。因此，虽然数据段、代码段的段号是连续的，但是数据段的最后一个地址和代码段的第一个地址是不连续的。因此说分段是二维的。

    image-20200805173806064

12.段页式存储

将进程按逻辑模块分段，再将各段分页。将内存空间分为大小相同的“页框”，将程序按页装入页框。

13.缺页中断

当前执行的指令想要访问目标页面未调入内存，从而产生缺页中断。

14.页面置换算法

  1. 最佳置换算法（OPT）
    • 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
    • 操作系统无法提前预判页面的访问序列，因此，最佳置换算法是无法实现的。
  2. 先进先出算法（FIFO）
    • 每次淘汰的页面是最早进入内存的页面。
    • 先进入的页面也有可能最经常被访问，算法性能差。
  3. 最近最久未使用置换算法（LRU）
    • 每次淘汰的页面是最近最久未使用的页面。
    • 在页表中，用一个字段记录该页面上次被访问以来所经历的时间t，淘汰页面时，选择t值最大的。
    • 性能最接近最佳置换算法，但是实现困难，开销大。
  4. 时钟置换算法（CLOCK）
    • 为每个页面设置一个访问位。访问位为1代表这个页面最近被访问过，访问位为0代表最近未访问过。
    • 每个页面被链接成为一个循环队列。扫描这个循环队列，检查页的访问位。如果为0，则将该页换出。如果为1，则将它置位0，暂不换出。选择淘汰一个页面最多会经过两轮扫描。
  5. 改进型时钟置换算法
    • 除了考虑一个页面最近有没有被访问过之外，还要考虑页面有没有被修改过。应该优先淘汰没有被修改过的页面，避免将其写回外存，减少IO操作。
    • 用（访问位，修改位）的形式表示各页面状态。如（1,1）表示一个页面最近被使用过且被修改过。
    • 过程：
      • 第一轮扫描：找到一个状态为（0,0）的页面并淘汰（即找到最近没有被访问，且未修改过的页面），本轮不修改任何标志位。
      • 第二轮扫描：若第一轮扫描失败，则重新扫描。查找第一个状态为（0,1）的页面并淘汰。本轮将所有页面的访问位都置位0。
      • 第三轮扫描：若第二轮扫描失败，则又找状态位为（0,0）的页面。（因为第二轮将访问位都置0了，所以其实找的是之前的(1,0) ）。
      • 第四轮扫描：若第三轮扫描失败，则又找状态为（0，1）的页面。（因为第二轮将访问位都置0了，所以其实找的是之前的(1,1) ）。

15.磁盘寻址

  1. 根据“柱面号”移动磁壁，让磁头指向指定柱面
  2. 激活指定盘面对应的磁头
  3. 磁盘旋转过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读写

16.磁盘调度算法

  • 先来先服务算法
    • 按照磁盘请求的顺序进行调度。
    • 优点是公平和简单。
    • 缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。
  • 最短寻找时间优先算法
    • 优先处理与当前磁头最近的磁道。
    • 虽然平均寻道时间比较低，但是不够公平。
    • 如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象，因为磁头总在一个小区域内移动。
  • 电梯算法
    • 只有磁头移动到最外侧磁道的时候才可以往内移动，只有磁头移动到最内侧磁道的时候才可以往外移动。
    • 不会产生饥饿现象。

计算机网络篇

17.