操作系统面试重点

发表于 更新于 分类于

进程和线程的区别 16

  1. 进程的状态、协程、和虚拟内存的关系
  2. 开多个java进程和多个线程的区别
  3. 一个进程能否访问到另一个进程的内存
  4. Java线程和系统线程的区别

区别

  • 进程是系统进行资源分配和调度的基本单位；线程是 CPU 资源分配和调度的基本单位
  • 线程依赖于进程，一个进程至少有一个线程
  • 进程有自己独立的地址空间，线程共享进程所属的地址空间
  • 上下文切换时，进程涉及到当前 CPU 环境的保存和新进程 CPU 环境的设置；线程只涉及少量寄存器内容的保存和设置 前者开销更大

协程

  • 协程是用户态轻量级线程，完全由程序控制而不被内核管理，内核不知道协程的存在
  • 一个线程可以有多个协程，一个进程也可以有多个协程
  • 进程和线程都是同步机制，协程是异步

Java线程和系统线程的区别

  • 底层数据结构不同， Java 是 JVM 中的实现，系统中的线程根据需求会有不同的实现
  • 状态不同， Java 线程有 New Terminated 等状态，操作系统只有ready running 和waiting 三种状态
  • Java 线程都是在用户态的，但是系统内核线程都是在内核态下，用户是通过系统调用来调用的

内存模型 7

虚拟内存的理解和作用（段页式、缺页中断、页面置换、内存颠簸）

逻辑地址和物理地址转化

虚拟内存

地址空间被按页划分，每页地址被映射到对应的物理内存。但不是所有页都在内存中，一些不常用的页存在磁盘上，当程序引用到不存在于物理内存中的页时，操作系统将缺失的部分装入物理内存。逻辑上内存大于物理上的内存，但其中一部分其实存储在磁盘上（磁盘上会有一个 swap 分区用来实现置换，当内存不足时会将暂时不用的一部分取出放到 swap 分区中来为当前的程序腾出足够的内存空间），所以叫虚拟内存。优点是让程序获得更多的可用内存

它让程序认为它拥有一块连续的可用内存，但其实这些内存往往离散的分布在不同的物理空间

虚拟内存和常规存储

常规存储有两个问题

  • 问题一：作业运行前要一次性装入内存，如果作业大小超出内存，就无法执行
  • 问题二：作业装入内存后就一直在内存中，直到作业运行结束。期间其他作业只能等待

针对这两个问题，虚拟内存的解决办法是

针对问题一

  • 根据局部性原理

    时间上：最近被访问的页在不久的将来还会被访问

    空间上：内存中被访问的页周围的页也很可能被访问

  • 程序在运行时只将当前需要的页装入内存

  • 如果所需要的页都在内存中就正常运行，如果发生缺页，就申请将需要的页从磁盘调入内存

针对问题二

  • 如果内存已满，就根据页面置换算法将需要的页与当前内存中的页进行置换

页式存储

  • 将内存抽象成地址空间
  • 地址空间被分成很多大小相等的块，每一块称为页
  • 内存空间也按照同样的大小被划分，每一块称为页框
  • 页表存储着页和页框的映射表
  • 逻辑上相邻的页，对应的物理地址不一定相邻
  • 虚拟地址分为两部分，一部分为页面号，一部分为偏移量

页太小会导致页表过大，降低对换效率，但是可以减少内碎片

页太大可以提高对换速度，但是内碎片过大，降低内存利用率

段式存储

  • 将进程自己的地址空间按照逻辑划分成若干段，如代码段，数据段等。内存空间页被动态地划分成长度不同的区域（段可以应付动态增长的情况），每段从 0 开始编址
  • 段式管理通过段表对应逻辑地址和物理地址

分页主要是用于实现虚拟内存，获得更大的地址空间；分段是为了使程序和数据可以被划分为逻辑上独立的地址空间，有助于共享和保护

要实现动态链接也需要段式存储。动态链接是在程序运行之前，先不把几个目标程序段连起来，而是只把主程序对应的程序段装入内存中，运行期间如果需要调用其他程序段，再把程序段装入内存并进行连接

段页式管理

  • 用户进程先分段，每个段内部再分页，实现了对内存的划分以及段内存的按页分配
  • 寻址：先通过段号找到该段对应的页表；再在页表中根据页号在物理地址中找到对应的物理块号，并根据页内偏移找到数据的物理地址；第三次再根据物理地址访问数据。一共三次访问主存。

分页和分段的区别

  • 目的不同：分页的目的是管理内存，用于虚拟内存以获得更大的地址空间；分段的目的是满足用户的需要，使程序和数据可以被划分为逻辑上独立的地址空间；
  • 大小不同：段的大小不固定，由其所完成的功能决定；页的大小固定，由系统决定；
  • 地址空间维度不同：
    • 分段是二维地址空间（段号+段内偏移），因为段和段之间没有关系，段号连续的两个段，地址并不一定连续；需要给出段号和段内偏移才能确定物理地址
    • 分页是一维地址空间，页和页之间逻辑上连续，第一个页的最后一个地址和第二个页的第一个地址数值上是连续的；只需要给出一个逻辑地址就能计算出页号和页内偏移，从而确定物理地址，因为页号大小是确定的。
  • 分段便于信息的保护和共享，对于可重入代码，可以专门划分一个段，其他进程的段表加入该段就可以实现代码共享；分页的共享受到限制，一个页中可能只需要共享一部分代码，但是共享的时候只能整个页一起共享；
  • 碎片：分段没有内碎片，但会产生外碎片；分页没有外碎片，但会产生内碎片（一个页填不满）
    • 内碎片是占用分区内未被利用的空间
    • 外碎片是占用分区之间难以利用的空闲分区

缺页中断

如果需要的页不在物理内存中，就发生缺页中断，需要将该页从磁盘掉入内存中。如果此时内存已满，就需要从内存中挑出一个与之进行置换

页面置换算法

页面置换算法是为了让缺页率最低

最佳页面置换算法：把未来很长一段时间内不会被用到的页面置换掉-理论算法

最近最久未使用LRU：将最近最久未使用的页面置换出去。实现方式是链表，每次一个页面被访问，把它移动到链表头，置换时候置换掉链表尾部的页面

先进先出FIFO：置换掉在内存中停留时间最长的页面-会把常用的页面置换出去

第二次机会算法：相当于优化FIFO，解决了常用页面被置换的问题。为每一个页面设置一个R位，被读和写时置为1，需要置换链表头部的页时，检查R位，如果是0就置换，如果是1，就将R置0，放入链表尾部。

时钟：省去第二次机会算法在链表中移动的开销，将页面首尾相连，指针指向最老的那个页面。需要置换时，判断R位是否为1，如果为1，重置为0，指针移向下一页；如果为0，把页面置换出

内存颠簸

本质就是频繁的页面调度。进程发生缺页中断，必须置换某一页。但是所有页都在使用，置换页面之后马上又发生缺页中断，导致系统效率急剧下降。解决策略包括：

  • 增加物理内存
  • 修改页面置换算法
  • 减少运行的程序数量

死锁 5

死锁的条件，说一个死锁情况，如何避免，尽量破坏哪一个来避免死锁

死锁的起因是互相等待对方释放占有的资源而处于永远暂停的状态

死锁产生的必要条件

  • 资源互斥：资源每次只能被一个线程占有
  • 请求与保持：线程因请求资源而被阻塞时，对已获得的资源保持不放
  • 不可抢占：线程已获得的资源，在未使用完之前不能强行剥夺
  • 循环等待：若干线程形成一种头尾相接循环等待资源的关系

死锁预防

思想是破坏产生死锁的四个条件

  • 破坏互斥：某些资源不具备这个条件
  • 破坏请求与保持：一次性申请所需要的所有资源；请求资源前先释放自己拥有的资源
  • 破坏不可抢占：允许进程抢占资源
  • 破坏循环等待：锁排序法，通过指定锁的获取顺序。一个线程只有获得A锁和B锁才能对某资源进行操作，在多线程下，可以指定只有获得A锁的线程才能获得B锁，按顺序获取锁就能避免两个线程同时持有A锁和B锁出现循环等待

死锁避免

  • 银行家算法 - 动态监测资源分配，确保处于安全状态下才进行资源分配。安全状态是指当前所有进程突然请求所有需要的资源时，有一种分配顺序能够满足所有进程

死锁解除

  • 回滚到之前的状态
  • 杀死进程 - 按照优先级杀死进程直到死锁解除

IO方法 4

操作系统底层原理
操作系统之上的应用程序都运行在用户空间，操作系统运行在内核空间，涉及到对磁盘、内存这些系统资源的访问，都需要在内核态进行。所以当应用程序要进行 IO 操作时，都需要进行系统调用。IO 操作分为准备数据和拷贝两个部分，准备数据是指将数据放置到对应的缓冲区（进程缓冲区/内核缓冲区），拷贝是指将数据从一个缓冲区拷贝到另一个缓冲区

阻塞式 IO

调用 IO 操作时，应用进程被阻塞，直到数据从内核缓冲区被复制到进程缓冲区才恢复，进行拷贝时继续阻塞。所以等待和拷贝两个阶段都处于阻塞状态

非阻塞式 IO

进程调用 IO 操作，如果数据还没准备好，系统会返回一个错误码，期间应用进程可以继续执行，期间会定期询问内核有没有准备好数据，如果准备好就进行拷贝。拷贝的过程依然是阻塞的

IO多路复用

select / poll / epoll 都是多路复用，多路复用就是通过一种机制，可以监听多个描述符，一旦某个描述符就绪，就可以通知程序进行响应的读写操作

区别：

  • 支持的最大连接数
  • 文件描述符是否从内核空间到用户空间来回复制
  • 触发方式
  • 查询描述符的效率，是否轮询

select

  • 将文件描述符放入集合中
  • 每次调用时将集合从用户空间拷贝到内核空间（每次都要复制，开销大）内核根据就绪状态修改集合内容
  • 集合大小有限制（32位机默认只有1024），采用水平触发
  • select函数返回后，需要通过遍历集合找到就绪的文件描述符（轮询效率低），文件描述符越多，效率越低

poll

  • 用链表存储文件描述符，所以大小没有限制
  • 其他和select一样

epoll

  • 用红黑树来存储被监听的描述符
  • 用户空间和内核空间共享内存，避免了来回复制的开销
  • 支持的最大连接数很大，1G 可以支持 10W 左右的连接数
  • 文件描述符就绪时会调用回调函数，将描述符添加到一个链表，之后返回这个链表
  • 支持水平触发和边缘触发
  • 采用边缘触发时只有活跃的描述符才会触发回调函数。所谓活跃，就是指缓冲区的状态发生变化：从不可读到可读；从不可写到可写；缓冲区的内容增多或减少
  • 采用水平触发时如果一次没有将缓冲区中的内容全部读完，下次即使缓冲区内容没有变化，还会再通知

连接数多并且很多不活跃时使用 epoll；连接数少且多数活跃时使用前两者，因为 epoll 需要回调，性能会稍差

水平触发

只要一个文件描述符就绪，就会发送通知，如果用户程序没有一次性把数据读写完，再次还会通知

边缘触发

描述符从为就绪变为就绪时通知一次，如果没读完之后也不会再通知

区别：边缘触发效率更高，减少了被重复触发的次数。水平触发可能会导致用户程序收到大量不需要的文件描述符

异步 IO

执行 IO 调用后可以立即返回，继续执行原来的操作。内核会在操作完成后通知进程。比如读操作，会在把数据放到用户指定的缓冲区后通知进程。等待和拷贝过程都不是阻塞的。

进程调度算法 3

批处理系统

目的是保证吞吐量和周转时间

  • 先来先服务
    • 非抢占，按照请求顺序调度，有利于长作业，不利于短作业，短作业可能需要等待很久来让长作业执行完
  • 短作业优先
    • 非抢占，长作业可能被饿死
  • 最短剩余时间优先
    • 短作业优先的抢占式版本，长作业还是可能会饥饿
  • 最高响应比优先
    • 计算响应比 = 1 + 等待时间 / 处理时间，平衡了长短进程，非抢占，但是开销大

交互式系统

保证快速响应

  • 时间片轮转
    • 所有进程按 FCFS 拍成队列，每个进程分配一个 CPU 时间片，用完后排到队尾部
    • 效率取决于时间片长短，太短会导致切换过频繁，太长实时性不能保证
  • 优先级调度
    • 为每个进程分配一个优先级，按优先级调度
    • 为保证低优先级等不到调度，随着等待时间的增加提高优先级
  • 多级反馈队列调度
    • 前两种方法的结合
    • 设置多个队列，从前到后时间片大小增加，优先级减小
    • 如果在前一个没有执行完就移到下一个队列，只有上一个队列没有进程，才执行下一个队列

进程间通信 3

机制，什么时候用什么，哪个最优（共享内存？）

管道：传输信息量大，只适用于亲缘进程 - 半双工，数据只能单向流动。如果要双向流动需要建立两个管道。只能用于亲缘进程是因为管道没有实体，只能通过 fork 来复制父进程的文件描述符来达到通信的目的。

命名管道：传输信息量大，适用任何场景。可以用于不相关的进程间，因为命名管道创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件就能进行通信。

管道其实就是内核中的一串缓存，管道一端写入的数据放到缓存中，另一端从缓存中取出数据。一端把数据放入管道后，只有等到另一端把数据取出，这一端才能正常返回。在这里理解为同步阻塞的，通信效率低

共享内存：传输信息量大，可适用于多个进程间通信 - 允许多个进程共享一段物理内存，不同进程可以将这个内存映射到自己的地址空间，然后像访问正常内存一样访问它。进程可以通过向共享内存区域读写数据来交换信息。优点：速度快，就像使用自己的内存区域一样，不需要系统调用，不存在用户态和内核态之间的数据拷贝 缺点：存在并发问题，一般和信号量一起使用解决并发问题

套接字：传输信息量大，适用于不同主机间进程的通信。服务端有一个专门用于监听的 socket，当收到客户端的连接请求时，会返回一个专门用于传输数据的 socket。

消息队列：消息队列是保存在内核中的消息链表，每一个消息都是一个数据块，具有固定的数据类型和大小。（管道是无格式的字节流数据）局限是因为数据块大小限制，不能上传过大文件

信号：传输少量信息，适用任何场景

信号量：主要用于互斥同步，是进程通信中唯一的异步通信机制

线程间通信机制 3

线程间通信的目的主要是用于线程同步，没有像进程通信中用于数据交换的通信机制

  • 锁机制：互斥锁、读写锁
  • 可以读写同一进程中的数据进行通信，全局变量 - 因为多个线程可能更改全局变量，所以把它声明为 volatile
  • 信号量机制 semaphore
  • 信号机制 signal

TLB 2

是什么，有什么作用

又被称为快表，相当于页表的cache，存储了当前最可能被访问到的页表项。提高了虚拟地址到物理地址的转换速度。在没有快表时，读写内存数据时要访问两次主存，有了快表之后就可能只要访问一次高速缓存和一次主存，提高查找速度。

线程同步机制 2

  • 互斥量，是内核对象，只有拥有互斥对象才能访问互斥资源。互斥对象只有一个，所以同一时刻互斥资源只能被同一对象访问。当前线程处理完后要将互斥对象交出
  • 信号量，是内核对象，允许同一时刻多个线程访问同一资源，每增加一个线程访问资源，信号量就减1
  • 事件，允许线程在处理完一个任务后主动唤醒另外一个线程执行任务
  • 临界区，任意时刻只允许一个线程访问临界区

互斥量和临界区的区别

互斥量是可以命名的，可以用于不同进程间同步；临界区只能用于同一进程中线程的同步。创建互斥量需要的资源更多，所以临界区优势是速度快，节省资源。

进程状态

进程有三种状态：就绪态，运行态，阻塞态

运行态和就绪态可相互转换，就绪态获得CPU资源进入运行态，运行态用完CPU资源进入就绪态

运行态可以转为阻塞态，当运行中的进程缺失某个资源无法进行下去时会进入阻塞态

阻塞态可以转化为就绪态，当阻塞态的进程获取到想要的资源时，转变为就绪态

综上：就绪态和阻塞态不能相互转化

进程间socket通信和网络间socket通信的区别

网络间socket

  • 建立 socket 需要一对套接字，一个运行于客户端，一个运行于服务端
  • 连接过程分为三个步骤：服务器监听，客户端请求，连接确认
  • 服务器监听：服务器端套接字处于等待连接状态，等待客户端的连接请求
  • 客户端请求：客户端提出连接请求，指出服务端套接字的地址和端口号，然后向服务端套接字提出连接请求
  • 连接确认：服务端套接字接收到客户端的连接请求后，就响应客户端的连接请求，建立一个新的线程，把服务端套接字的描述发送给客户端，一旦客户端确认，双方就正式建立连接。

用户态和内核态

是系统的两个权限等级，代表不同的访问能力

  • 内核态可以访问内存的所有数据以及外围设备，例如硬盘网卡
  • 用户态只能受限访问内存，不能访问外围设备，不能占用 CPU

所有应用程序都运行在用户态，需要进行一些内核操作，例如读取硬盘数据时就要进行系统调用，切换到内核态，执行完服务之后再返回用户态，并返回调用结果

从用户态切换到内核态的方法

  • 系统调用
  • 异常：一些异常需要在内核态进行处理

磁盘寻道

过程

  • 磁头先找到对应的盘面
  • 磁头移动到对应的磁道（寻道时间）
  • 磁盘旋转到对应的扇区（旋转时间）

调度算法

先来先服务：公平简单，但是平均寻道时间长

最短寻道优先：平均时间较短，但是会饥饿

电梯算法：按照一个方向进行磁盘调度，等到该方向没有未完成请求后，改变方向

fork()

创建一个与原来进程几乎完全相同的进程