操作系统

发表于 分类于
总结

操作系统

参考

参考

参考

用户态和内核态

最简单的运行程序的方式是“直接执行”，即直接在 CPU 上执行任意程序。直接执行的问题是：

  1. 无法限制
  2. 无法进程调度

因此引入用户态和内核态和两种模式。用户态无法执行受限操作，如 I/O 请求，执行这些操作会引发异常。内核态只能由操作系统运行，可以执行特权操作。用户程序通过系统调用执行这些特权操作。OS 执行前会判断进程是否有权限执行相应的指令

陷入内核态

系统调用（trap）、中断（interrupt）和异常（exception）

  • C 访问空指针会陷入内核态，访问指针相当于访问一个虚拟地址，直接映射到物理内存

进程与线程的区别

  • 进程是一个拥有资源和执行任务的单元体。进程拥有的资源包括：内存空间中的代码、数据等；I/O 资源；文件；处理机等。
  • 线程是一个执行任务的单元体。线程只拥有处理机，线程之间共享进程的资源，如内存、I/O 等。

为什么需要线程

  • 只切换必需的、与处理机相关的信息，减少开销
  • 当上下文切换的时候，正在运行的线程会将寄存器的状态保存到 TCB（Thread Control Block）里（进程是 PCB，Process Control Block），然后恢复另一个线程的上下文
  • 问题就是并发，共享空间，一个线程出错，整个进程都会结束（使用多进程解决）

同一进程中的线程共享与独占的资源

  • 共享
    • 内存空间
      • 代码
      • 公共数据（全局变量、静态变量）
      • 堆
    • 文件描述符
    • 信号处理器
    • 进程 ID / 进程组 ID
    • 。。。
  • 独占
    • 线程 ID
    • 栈（函数调用）
    • 错误返回码
    • 信号屏蔽码

作业、管程

  • 作业：用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合。它包括用户程序、所需要的数据及控制命令等。作业时由一系列有序的步骤组成的
  • 管程：是定义了一个数据结构和在该数据结构上能为并发进程所执行的一组操作。这些操作能同步进程和改变管程中的数据。它是一种进程同步机制。在结构上类似于面向对象中的类。在功能上和信号量和p，v操作类似。可以更方便的管理系统的临界资源

进程的三种基本状态

  • 就绪：进程已获得除处理机以外的所需资源，等待分配处理机资源
  • 执行：进程正在占用处理机资源执行
  • 阻塞：进程等待某种条件，在条件满足之前无法执行。如发起了 I/O 系统调用，会被阻塞，等待 I/O 中断发生
  • 注意挂起和阻塞的区别
    • “挂起”是指将暂不执行的进程换出到外存，节省内存空间
      • 挂起就绪状态：进程在外存中，但是只要被载入内存就可以执行
      • 挂起阻塞状态：进程在外存中并等待一个事件，即使被载入内存（激活）也无法运行
  • Linux 下的阻塞状态可分为 3 种：暂停、浅睡眠、深睡眠
    • 若不需要等待资源，则切换为“暂停”；若需要等待资源，切换为“睡眠”；如果睡眠状态能被信号唤醒，则是“浅睡眠”，否则是“深睡眠”

Linux 进程的 5 种状态

进程调度算法

  • 注意饥饿问题、僵尸进程（僵尸进程、孤儿进程、守护进程）
  • 批处理系统
    • 先来先服务 FCFS、最短作业优先 SJF、最短剩余时间优先 SRTN、最高响应比优先 HRRN
  • 交互系统（分时系统）
    • 时间片轮转 RR、优先级调度 Priority、多级反馈队列 MFQ、彩票法、公平分享法
  • 实时系统
    • 最早截止时间优先算法
  • 僵尸进程、孤儿进程、守护进程
    • 参考
    • 僵尸进程：停止运行
    • 孤儿进程：正在运行
    • 守护进程：正在运行

进程通信（同步）方式（IPC）

  • 信号

  • 管道

    • 匿名管道和命名管道
      • 匿名管道（pipe）
        • 只能用在亲缘进程中，管道文件信息保存在内存里
        • 本质是一个伪文件(实为内核缓冲区)，由两个文件描述符引用，一个表示读端，一个表示写端
        • 下游进程或者上游进程需要等另一方释放锁后才能操作管道。管道就相当于一个文件，同一时刻只能有一个进程访问
        • 数据自己读不能自己写
        • 管道不再被任何进程使用时，自动消失，生命周期随进程的结束结束
      • 命名管道（FIFO）
        • 以FIFO的文件形式存储于文件系统中，因此，可用于没有亲缘的进程间
        • 也是通过内核缓冲区来实现数据传输
        • 建立命名管道时，会在磁盘中创建一个索引节点，命名管道的名字就相当于索引节点的文件名
        • 当不再被任何进程使用时，命名管道在内存中释放，但磁盘节点仍然存在
    • 管道是由内核管理的一个缓冲区，缓冲区被设计成为环形的数据结构，以便管道可以被循环利用（循环队列）

  • 信号量 Semaphore

    • S 表示可用资源的数量
    • P(S) 即 down
      • 请求分配一个单位资源，减少信号量 S 的数值，如果 S 为 0，则挂起进程
    • V(S) 即 up
      • 释放资源，若S>0，唤醒等待队列中的一个进程，增加信号量 S 的数值，
    • 如果信号量只有二进制的 0 或 1，称为二进制信号量（binary semaphore）。二进制信号量可以用来实现一个互斥锁（Mutex）

  • 共享内存

    • 管道和消息队列，需要在内核和用户空间进行四次的数据拷贝（读输入文件、写到管道；读管道、写到输出文件），而共享内存则只拷贝两次（一次从输入文件到共享内存区，另一次从共享内存到输出文件）
    • 缺点是存在并发问题

  • 消息队列

    • 接收者必须轮询消息队列，才能收到最近的消息
    • 与管道相比，消息队列提供了有格式的数据，但消息队列仍然有大小限制

  • 套接字

    • 不同的计算机的进程之间通过 socket 通信，也可用于同一台计算机的不同进程
    • 主机地址与端口号
    • 网络层

  • 锁

    • 互斥锁、读写锁、自旋锁、条件锁
    • 互斥锁的开销主要体现在线程的重新调度和上下文切换上，获取锁的开销是比较大的。因此 mutex 适用于线程持有锁时间比较长的场景

临界资源和临界区、互斥与同步

  • 临界资源：一次仅允许一个进程使用的共享资源，也就是互斥资源
  • 临界区：程序中访问临界资源的那段代码，也称危险区、敏感区
  • 互斥：多个程序片段，同一时刻仅有一个能进入临界区
  • 同步：若干程序片断运行必须严格按照规定的某种先后次序来运行。同步是一种更复杂的互斥：互斥不会限制程序对资源的访问顺序，即访问是无序的；而同步必须要按照某种次序来运行
  • 常见的同步问题
    • 生产者与消费者问题
      • 生产者和消费者共享固定大小的缓冲区，生产者向缓冲区写入数据，消费者从缓冲区读出数据，生产者不能在缓冲区满时加入数据，消费者也不能在缓冲区空时消耗数据
      • 这里如果直接使用操作系统提供的 sleep() 和 wakeup()，可能发生死锁，原因在于：「判断是否要休眠（缓冲区空/满）」和「执行 sleep()」不是一个原子操作，有可能在执行 sleep() 之前被切换到另一个程序，导致 wakeup() 信号丢失，最后两者都进入休眠
      • 使用信号量可以解决上述问题
      • 在多个生产者和消费者的情况下，有可能出现两个或以上的进程同时读或写同一个缓冲区槽的情况，因此再用一个二值信号量 mutex 实现一个锁
    • 读者写者问题
      • 允许多个进程同时读数据库
      • 有进程在读数据库的时候，不允许写数据库
      • 如果有一个进程正在写数据库，则不允许其他任何进程访问数据库
    • 浴室洗澡问题
      • 一个浴室，当有一个女生在浴室里，其他女生可以进入，但是男生不行，反之亦然
    • 哲学家就餐问题
      • 假设有五位哲学家围坐在一张圆形餐桌旁，吃饭或者思考。每位哲学家之间各有一根筷子，哲学家必须用两根筷子吃东西。他们只能使用自己左右手边的那两根筷子
      • 可能有死锁的写法：每个哲学家都拿着左边的筷子，永远都在等右边的筷子

死锁产生的四个必要条件

  • 互斥条件
  • 占有且等待条件：线程占有已经分配给它们的资源（如锁）并且等待其他的资源（也就是说不会主动释放）
  • 不可抢占条件（也就是说不会被动释放）
  • 环路等待条件：每个进程都在等待下一个进程占有的资源

死锁的避免

破坏上面四个条件任意一个，但很难，所以

  • 银行家算法：允许系统中同时存在四个必要条件，但是每当进程提出资源申请时，系统要分析满足该资源请求后，系统是否会发生死锁，若不会发生则实施分配，否则拒绝分配，即
    • 通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待

线程通信（同步）方式

  • 信号，使用方法和进程几乎一样，但是是另一套相似的API，不可以互换
  • 信号量，和进程类似，功能和互斥锁基本一样
  • 互斥锁，保护临界资源
  • 控制变量，常和互斥锁配合使用，控制线程执行的先后。暂时挂起线程还锁，解决线程为获得数据等待其他线程，导致长时间占用锁

内存抖动

指内存频繁地分配和回收，占用了大量CPU时间

物理内存管理

  • 内部碎片和外部碎片
    • 内部碎片是固定分区法产生的，指被占用分区上未被利用的空间，由于该分区被占用，因此无法被分配使用
    • 外部碎片是动态分区法产生的，指被占用分区之间的小空间，虽然可以被使用，但是由于太小而无法被分配
    • 解决：
      • 页面管理算法（Linux）
        • Buddy（伙伴）分配算法
          • 把相同大小的页框块用链表串起来
          • 所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存
          • 因为任何正整数都可以由 2^n 的和组成，所以总能找到合适大小的内存块分配出去，减少了外部碎片产生
        • slab 分配器
          • 通过将内存按使用对象不同再划分成不同大小的空间，应用于内核对象的缓存
          • 内核中有大量的小对象，对于每个内核中的相同类型的对象，如：task_struct、file_struct 等需要重复使用的小型内核数据对象，都会有个 slab 缓存池，缓存住大量常用的「已经初始化」的对象，每当要申请这种类型的对象时，就从缓存池的slab 列表中分配一个出去；而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免内部碎片，同时也大大提高了内存分配性能
          • slab 内存分配器是对伙伴分配算法的补充
          • slab 高速缓存分为两大类，通用高速缓存和专用高速缓存
  • 固定分区法（等长、不等长）
  • 动态分区法
  • 页式内存管理
    • 把固定分区面积缩小，一个进程可使用多个分区；进程被分割成若干块，装入内存中的几个分区中，物理上无需相连，逻辑上通过页表关联
  • 段式内存管理
    • 按照逻辑意义将程序分成若干个段，每个段独立载入到内存的不同区间中
    • 缺点：每个段必须连续、全部加载到内存中
  • 段页式内存管理
    • 先把程序按照逻辑意义分成段，然后每个段再分成固定大小的页
  • 页面、页框、页表
    • 页表：每个进程有一个页表，描述该进程每个页面对应的页框号，以及该页面是否已经被载入内存（“在/不在”位）
    • 对大内存页表
      • 多级页表
        • 时间换空间，节省空间，时间可以用 TLB 来缓解
      • 倒排页表
      • 散列表

虚拟内存管理

  • 原先的覆盖、交换技术太垃圾
  • 虚存管理和覆盖技术一样，不是把程序所有内容全部放入内存，但这个操作是由操作系统完成，而不是程序员
  • 和交换技术一样，实现进程在内存和外存的交换，但虚存管理做的更好，是只对进程的部分内容在内存和外存之间交换
  • 需要有程序局部性（要有时间、空间局部性）
    • P23
    • 指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域
  • 物理内存分配不连续，虚拟地址空间使用不连续
  • 简略实现
    • 在系统中为每个程序定义一个虚拟地址空间，虚拟地址空间中的地址都是连续的
    • 虚拟地址空间被分割成多个块，每块称为一个页或者页面
    • 物理内存被分成和页面大小相同的多个区域，称作页框
    • 程序加载时，可将任意一个页面放入内存中的任意一个页框
    • CPU 的硬件负责将虚拟地址映射到物理内存中的地址（页面 -> 页框）
    • 程序的整个地址空间无需全部载入物理内存，还有部分暂时存储在外存上，需要时再换入内存
    • 如果程序引用到一部分不在物理内存中的虚拟地址时，会发生缺页中断，由操作系统负责将缺失的页面加载入页框中，并重新执行失败的指令
  • 交换分区
  • 转换检测缓冲区（TLB）
    • 缓冲页表
  • 缺页中断/异常
    • 请求调页和页面置换
    • 页面置换/淘汰
    • 目的是减少页面换入换出的次数
    • 局部页面置换算法
      • 最优页面置换算法
        • 判断未来，是理想情况，实际中不可能实现
        • 这是评价标准
      • FIFO
      • LRU 最近最久未使用
        • （算法题：链表 + 哈希表）
      • 第二次机会算法
        • FIFO 的改进
      • 时钟页面置换算法（Clock 算法）
        • LRU 近似 + 第二次机会置换法的改进
        • 将页面保存在环形链表中，只需要后移队头指针，就相当于是把原来的队头放到队尾了，避免了移动链表节点的开销
      • LFU 最不常用
      • Belady 现象：FIFO时，可能会出现分配的物理页面增多，缺页率反而提高
      • LRU 性能好，但开销大，FIFO 开销小，但会 Belady；还是 Clock 算法折中
    • 全局页面置换算法
      • 工作集页置换算法
      • 缺页率置换算法

Linux虚存

用户空间内存分配

  • malloc
    • 当申请小于 128KB 小内存的时， malloc 使用 sbrk 或 brk 分配内存；当申请大于 128KB 的内存时，使用 mmap 函数申请内存
    • 由于 brk/sbrk/mmap 属于系统调用，cpu 在用户态和内核态之间频繁切换
      • 解决：malloc 使用的是内存池
        • 先申请一块大内存，然后将内存分成不同大小的内存块，然后用户申请内存时，直接从内存池中选择一块相近的内存块分配出去

内核空间内存分配

  • kmalloc

    • 分配的虚拟地址范围在内核空间的直接内存映射区
    • 基于 slab 分配器
    • 按字节为单位虚拟内存，一般用于分配小块内存，释放内存对应于 kfree ，可以分配连续的物理内存

  • vmalloc

    • 分配的虚拟地址区间，位于 vmalloc_start 与 vmalloc_end 之间的动态内存映射区
    • （内核页表）
    • 一般用分配大块内存，释放内存对应于 vfree，分配的虚拟内存地址连续，物理地址上不一定连续

  • 两个再通过 Buddy 分配内存

文件系统

  • 文件块
    • 卷控制模块、控制块、目录节点会部分加载进内存以提高访问效率
  • 文件表
  • 层次目录结构
  • 路径遍历
  • 种类
    • 磁盘文件系统：FAT、NTFS、ext2/3/4…
    • 数据库文件系统
    • 日志文件系统
    • 。。。
  • 虚拟文件系统
    • 可以说整合了各种文件系统的复杂操作，成为一个虚拟文件系统层，提供了文件系统 API
  • RAID
    • RAID-0：把数据均匀的分布在不同的磁盘上，然后并行访问
    • RAID-1：写数据时往几个同样的硬盘写同样的数据（可靠性）
    • RAID-4：0和1结合，用额外的一个盘（Parity Disk）来容错，这个盘会频繁写
    • RAID-5：把Parity Disk均匀分布在不同的硬盘上
    • 。。。

I/O

  • 5 种 I/O 模型：阻塞 I/O、非阻塞 I/O、信号驱动式 I/O、I/O 多路复用、异步 I/O（AIO）