Skip to content
This repository has been archived by the owner on Jan 13, 2023. It is now read-only.

Latest commit

 

History

History
383 lines (260 loc) · 16.7 KB

os_interview.md

File metadata and controls

383 lines (260 loc) · 16.7 KB

操作系统

基础问题

进程和线程

  • 进程是系统进行资源分配和调度的一个独立单位
  • 线程是进程的一个实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位
    • 用户态线程和内核态线程
      • 用户态线程
        • 内核资源的分配仍然是按照进程进行分配的
        • 各个用户线程只能在进程内进行资源竞争
      • 内核态线程
        • 这些线程可以在全系统内进行资源的竞争
        • 线程控制块（TCB）

PCB

  1. 进程标识符

作用： 用于唯一地标识一个进程

• 进程本身：外标识、内部标识 • 家族信息：父进程、子进程信息

  1. 处理机状态

处理机状态信息也称为处理机的上下文（Context），主要是由处理机的各种寄存器中的内容组成的。 也就是中断现场的保留区，当进程被切换时，处理机状态信息必须都保存在相应的PCB中，以便该进程在重新执行时能再从断点继续执行。

  1. 进程调度信息

在OS进行调度时，必须了解进程的状态以及有关进程调度的信息。这些信息包括：

① 进程状态 就绪、执行、阻塞等，是进程调度和对换的依据

② 进程优先级 是分配CPU的重要依据

③ 其它信息 比如进程已等待CPU的时间总和、已执行的时间总和等

④ 事件 指的是阻塞原因（即程序由执行状态变为阻塞状态的原因）

  1. 进程控制信息

① 程序和数据的首地址 调度到该进程的时候，可以找到其程序和数据

② 进程同步和通信机制 如消息队列指针、信号量等，以后的进程同步中会学到

③ 资源清单 列出了该进程在运行期间所需的全部资源（CPU除外），另外还有一张该进程已分配的资源清单

④ 链接指针 给出了该进程（PCB）所在队列中下一个进程的PCB首地址，跟链表一样

img


TCB

进程调度算法

  • 先来先服务 - FIFO
  • 最短作业优先 - 提升短作业的处理效率
  • 高响应比优先 - 计算响应比，兼顾长短作业
  • 时间片轮转 - 抢占式，最公平，但可能造成频繁的上下文切换
  • 最高优先级 - 引入优先级的概念
  • 多级反馈队列
    • 多级表示优先级，优先级越高时间片越短
    • 反馈表示高优先级抢占

img


进程状态

上下文切换

进程通信

  • 管道
  • 消息队列
  • 共享内存
  • 信号量
  • 信号
  • socket - 不同PC机上

死锁产生条件

  • 互斥条件 - 一个资源每次只能被一个进程使用
  • 请求与保持条件 - 一个进程因请求资源而阻塞时，对已获得的资源保持不放
  • 不可剥夺条件 - 进程已获得资源，在使用完之前，不可被剥夺
  • 循环等待条件 - 若干进程之间形成一种头尾相连的循环等待资源关系

避免死锁

  • 把资源一次性分配，破坏请求与保持条件
  • 当进程的资源未被满足时，释放已经占用的资源，破坏不可剥夺条件
  • 系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反【哲学家就餐】，破坏循环等待条件

CPUCache

Cache Line

  • CPU读取内存时，是按照Cache Line读取的
  • L1 Cache Line大小是64字节

伪共享

  • 因为多个线程同时读写同⼀个 Cache Line 的不同变量时，⽽导致 CPU Cache 失效的现象称为伪共享

避免伪共享

  • 内核层面
    • Linux 内核 __cacheline_aligned_in_smp
    • 采⽤上⾯的宏定义使得变量在 Cache Line ⾥是对⻬的
  • 应用层面
    • Java 并发框架 Disruptor 使⽤「字节填充 + 继承」
    • long进行前置和后置填充

IO

缓冲与非缓冲IO

根据「是否利⽤标准库缓冲」，可以把⽂件I/O分为缓冲I/O和⾮缓冲

  • 缓冲 I/O：利⽤的是标准库的缓存实现⽂件的加速访问，⽽标准库再通过系统调⽤访问⽂件
  • ⾮缓冲 I/O：直接通过系统调⽤访问⽂件，不经过标准库缓存

直接与非直接IO

根据是「否利⽤操作系统的缓存」，可以把⽂件 I/O 分为直接 I/O 与⾮直接 I/O

  • 直接 I/O：不会发⽣内核缓存和⽤户程序之间数据复制，⽽是直接经过⽂件系统访问磁盘
  • ⾮直接 I/O：读操作时，数据从内核缓存中拷⻉给⽤户程序；写操作时，数据从⽤户程序拷⻉给内核缓存，再由内核决定什么时候写⼊数据到磁盘

阻塞与非阻塞IO

阻塞等待的是「内核数据准备好」和「数据从内核态拷⻉到⽤户态」这两个过程

  • 阻塞 I/O：当⽤户程序执⾏ read ，线程会被阻塞，⼀直等到内核数据准备好，并把数据从内核缓冲区拷⻉到应⽤程序的缓冲区中，当拷⻉过程完成， read 才会返回
  • ⾮阻塞 I/O，⾮阻塞的 read 请求在数据未准备好的情况下⽴即返回，可以继续往下执⾏，此时应⽤程序不断轮询内核，直到数据准备好，内核将数据拷⻉到应⽤程序缓冲区， read 调⽤才可以获取到结果

同步与异步IO

⽆论是阻塞 I/O、⾮阻塞 I/O，还是基于⾮阻塞 I/O 的多路复⽤都是同步调⽤。因为它们在 read 调⽤时，内核将数据从内核空间拷⻉到应⽤程序空间，过程都是需要等待的，也就是说这个过程是同步的

真正的异步 I/O 是「内核数据准备好」和「数据从内核态拷⻉到⽤户态」这两个过程都不⽤等待


IO多路复用

⼀个进程虽然任⼀时刻只能处理⼀个请求，但是处理每个请求的事件时，耗时控制在 1 毫秒以内，这样 1 秒内就可以处理上千个请求，把时间拉⻓来看，多个请求复⽤了⼀个进程，这就是多路复⽤

select

  • 将已连接的 Socket 都放到⼀个⽂件描述符集合，然后调⽤select 函数将⽂件描述符集合拷⻉到内核⾥，让内核来检查是否有⽹络事件产⽣，检查的⽅式很粗暴，就是通过遍历⽂件描述符集合的⽅式，当检查到有事件产⽣后，将此 Socket 标记为可读或可写， 接着再把整个⽂件描述符集合拷⻉回⽤户态⾥，然后⽤户态还需要再通过遍 历的⽅法找到可读或可写的 Socket，然后再对其处理
  • 对于 select 这种⽅式，需要进⾏ 2 次「遍历」⽂件描述符集合，⼀次是在内核态⾥，⼀个次是在⽤户态⾥ ，⽽且还会发⽣ 2 次「拷⻉」⽂件描述符集合，先从⽤户空间传⼊内核空间，由内核修改后，再传出到⽤户空间中
  • select 使⽤固定⻓度的 BitsMap，表示⽂件描述符集合，⽽且所⽀持的⽂件描述符的个数是有限制的，在 Linux 系统中，由内核中的 FD_SETSIZE 限制， 默认最⼤值为 1024 ，只能监听 0~1023 的⽂件描述符

poll

  • poll 不再⽤ BitsMap 来存储所关注的⽂件描述符，取⽽代之⽤动态数组，以链表形式来组织，突破了 select 的⽂件描述符个数限制，当然还会受到系统⽂件描述符限制
  • 都是使⽤「线性结构」存储进程关注的 Socket集合，因此都需要遍历⽂件描述符集合来找到可读或可写的 Socket，时间复杂度为 O(n)，⽽且也需要在⽤户态与内核态之间拷⻉⽂件描述符集合

epoll

  • epoll 在内核⾥使⽤红⿊树来跟踪进程所有待检测的⽂件描述符
  • epoll 使⽤事件驱动的机制，内核⾥维护了⼀个链表来记录就绪事件
  • 事件触发方式
    • 边缘触发
      • 服务器端只会从epoll_wait 中苏醒⼀次
      • 边缘触发模式⼀般和⾮阻塞 I/O 搭配使⽤
    • 水平触发
      • 服务器端不断地从epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束 img

内存管理

虚拟内存

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

直接使用物理内存会产生如下的问题

  • 内存空间利用率问题，内存碎片
  • 读写内存的安全性问题，没有访问控制
  • 进程间的安全问题
  • 内存读写效率问题

虚拟内存的工作原理

当一个进程试图访问虚拟地址空间中的某个数据时，会经历下面两种情况的过程：

  • CPU想访问某个虚拟内存地址，找到进程对应的页表中的条目，判断有效位， 如果有效位为1，说明在页表条目中的物理内存地址不为空，根据物理内存地址，访问物理内存中的内容，返回
  • CPU想访问某个虚拟内存地址，找到进程对应的页表中的条目，判断有效位，如果有效位为0，但页表条目中还有地址，这个地址是磁盘空间的地址，这时触发缺页异常，系统把物理内存中的一些数据拷贝到磁盘上，腾出所需的空间，并且更新页表。此时重新执行访问之前虚拟内存的指令，就会发现变成了情况1.

img


页面置换算法

缺页中断

在请求分页系统中，可以通过查询页表中的状态位来确定要访问的页面是否存在于内存中。每当所要访问的页面不在内存时，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到缺页，将其调入内存。

缺页本身是一种中断，与一般的中断一样，需要经过四个处理步骤：

  • 保护CPU现场
  • 分析中断原因
  • 转入缺页中断处理程序进行处理
  • 恢复CPU现场，继续执行

但是缺页中断时由于所要访问的页面不存在内存，由硬件所产生的一种特殊的中断，因此，与一般的中断存在区别：

  • 在指令执行期间产生和处理缺页中断信号
  • 一条指令在执行期间，可能产生多次缺页中断
  • 缺页中断返回时，执行产生中断的那一条指令，而一般的中断返回时，执行下一条指令

页面置换算法

  • 最佳页面置换算法 - 置换在[未来]最长时间不访问的页面，理想算法难以实现
  • 先入先出 - 选择在内存驻留时间最长的页面进行置换
  • LRU - 选择最长时间没有被访问的页面进行置换

img

  • 时钟页面置换算法

    • 所有页面都保存在一个类似于时钟的[环形链表]中
    • 指针开始指向那个最老的页面
    • 当发生缺页中断时，指针开始遍历环形链表
      • 把沿途遇到的访问位为1的修改为0
      • 直到遇到访问位为0的，将其淘汰，IO进需要的页面

  • LFU - 选择访问最少的页面将其淘汰

img


虚拟文件系统

MMU

Memory management Unit是内存管理单元。它是一种负责处理CPU的内存访问请求的计算机硬件。功能主要包括：

  • 虚拟地址到物理地址的转换（虚拟内存管理）
  • 内存保护
  • 中央处理器高速缓存

img

img

MMU将虚拟地址映射到物理地址是以page为单位的，32位处理器的页尺寸通常是4KB。

物理内存中的页成为物理页面或者页帧。虚拟内存的哪个页面映射到物理内存的哪个页帧是通过页表来描述的，页表保存在物理内存中，MMU会查找页表来确定一个虚拟地址应该映射到什么物理地址。

OS和MMU是这样配合的：

  • 操作系统在初始化或者分配、释放内存时会执行一些指令在物理内存中填写页表，然后用指令设置MMU，告诉MMU页表在物理内存中的什么位置
  • 设置好后，CPU每次执行访问内存的指令都会自动触发MMU做查表和地址转换操作，地址转换操作由硬件自动完成，不需要用指令控制MMU去做

内存保护

MMU除了做地址转换之外，还提供内存保护机制。

各种体系结构都有用户模式（User Mode）和特权模式（Privileged Mode）之分，操作系统可以在页表中设置每个内存页面的访问权限，有些页面不允许访问，有些页面只有在CPU处于特权模式时才允许访问，有些页面在用户模式和特权模式都可以访问，访问权限又分为可读、可写和可执行三种。

用户程序加载到用户空间，在用户模式下执行，不能访问内核中的数据，也不能跳转到内核代码中执行。这样可以保护内核，如果一个进程访问了非法地址，顶多这一个进程崩溃，而不会影响到内核和整个系统的稳定性。

img


文件IO

文件IO

  • 直接访问文件，每一次都会执行系统调用
  • open() read() write() close()

标准IO

  • 先读写缓冲区，必要时再访问文件
  • fopen() fread() fwrite() fclose()

用户态和内核态

  • 内核态
    • 运行操作系统程序，操作硬件
    • 能访问所有的内存空间和对象，且所占有的处理器是不允许被抢占的
  • 用户态
    • 运行用户程序
    • 进程所能访问的内存空间和对象受到限制，其所处于占有的处理器是可被抢占的
  • 用户态-->内核态
    • syscall
    • 异常，比如缺页异常
    • 外围设备的中断，比如磁盘读写

中断和异常

Linux同步机制

磁盘调度算法

  • 先来先服务
  • 最短寻道时间优先
  • 扫描算法
  • 循环扫描算法
  • LOOK与C-LOOK算法

细节问题

程序执行流程

屏幕输出HelloWorld

  • OS创建一个进程，将hello映射到该进程结构
  • 为hello配置CPU上下文环境
  • 执行helloworld程序的第一条指令，发生缺页异常
  • 缺页置换
  • syscal，输出到屏幕

读文件

  • 进程调用库函数发起读文件请求
  • 内核检查进程的文件描述符，定位到虚拟文件系统
  • 系统调用read()
  • 访问页缓存，命中则直接read()；未命中产生缺页中断，执行页面置换

写文件

  • 前三步和read一样
  • 页缓存命中，直接write()，未命中缺页置换
  • 将页缓存标记为脏页，进程定时写回磁盘
  • 脏页写回磁盘时，需要上锁

进程隔离

进程隔离的主要的工作是操作系统和MMU合作完成的。

MMU可以控制哪些内存能被用户态访问，哪些内存能在内核态被访问，以及一个虚拟地址对应的物理地址是哪里。一般来说，内核态可以访问用户态的内存，但反过来不行。

主流的操作系统都会划分出固定的内存区域，来区分内核态和用户态，同时，通过MMU页表来禁止用户态代码直接访问内核区域的内存。

比如在32位Windows里，000000007FFFFFFF是用户内存区，80000000FFFFFFFF是内核内存区，用户态代码不能访问内核态代码，但是内核态代码可以访问用户态代码。Linux一般是3G永用户，1G内核。

通过设置MMU页表属性，把相关的地址范围隔离开，这样用户态代码就无法访问内核内存区了。

不同的进程可以拥有不同的页表，并且页表在内核态（或者通过权限控制，只允许内核访问），这样就可以防止用户态恶意修改页表。

通过上面的操作，因为用户态进程每次访问内存都要经过页表，操作系统只要控制页表，把不同进程的虚拟地址映射到不同的物理地址上，就可以实现进程之间的内存隔离了。同时，用户代码不能访问页表，所以用户进程也就不能修改内存映射了。

换页的过程是在内核完成的，内核是知道哪些内存被换出，哪些内存被换入的，这个操作不是在用户态完成的，所以用户态进程是看不到换入换出的内容的。