从操作系统层次架构的角度讲述操作系统各个模块的基础知识

概述

操作系统定义与结构

操作系统是沟通底层硬件与用户的桥梁，通过操作系统，用户得以调度系统资源、管理系统。操作系统总体架构大致可分为用户——应用程序——操作系统——硬件几个层次。其中，操作系统主要实现的功能包括内核管理、进程管理、CPU调度、进程同步与死锁、存储系统与虚拟内存、系统接口等部分

操作系统服务

依据其要实现的目标，操作系统提供如下服务：

  • UI：提供一系列用户交互接口，包括命令行cli，图形界面GUI
  • Program execution：系统需要调度内存中的程序并执行它
  • I/O operation：对外接设备以及文件的I/O读写
  • 文件系统模拟：操作系统需要读写文件系统，管理文件权限
  • 进程调度：操作系统需要创建调度进程在系统文件中进行信息交换
  • 错误检测：操作系统需要能够检测出错误并修改错误
  • resource allocation：资源配置，对多用户的资源配置
  • Accounting：资源调度统计
  • Protecting and security：权限管理

以上服务可分为两个层面，分别为用户层的UI接口和操作系统层的具体调用逻辑，用户处理信息时分为System call用做在UI界面和系统内部交流的接口，以及程序运行Program execution，即实际上程序内部如何运行调度

System call：获取系统相关信息的调用，例如创建文件，读写文件等，都需要调用system call接口，如open()，write()，chmod()等接口都属于system call的范畴

操作系统的特征

操作系统基于其功能与服务，体现了如下4个特征：

  1. 并发：两个或多个事件在同一时间间隔内发生，用以在单核CPU中同时运行多个程序
  2. 共享：系统中的资源可供内存中多个并发执行的进程同时使用(共享访问硬盘资源)
  3. 虚拟化：把物理实体变为逻辑上的对应物（主要体现在内存管理层面的虚拟内存部分），通过动态分配程序运行空间，从而使得同时打开的内存大于实际内存
  4. 异步：异步使用系统资源，解决同步等待导致进程调度缓慢的问题

MS-DOS分层架构

MS-DOS分层架构是如今操作系统中最流行的架构方式
依据功能结构不同，将操作系统分为多层，从内到外包括：

  1. BIOS层：最底层的硬件控制层
  2. DOS内核：MS-DOS核心文件，包含操作系统基本功能，如内核管理，文件管理等
  3. 命令解释器层：提供用户和系统内部交流的渠道
  4. 系统应用层：可以通过命令调用的外部应用
  5. 外部设备层：外接设备
    通过分层模块化设计，使得操作系统各层之间不互相干扰，增强系统的灵活性，可维护性，可拓展性，同时，核心小巧，资源占用少，运行高效

操作系统内核

什么是内核？

内核是操作系统中执行指令的部分，而内核程序则是操作系统中执行机器指令的系统。现代操作系统一般会有两种状态，分别为用户态和内核态，用户态为常态，用来存储用户信息以及权限等，内核态拥有管理员权限，用来执行一些底层指令

内核状态切换

  • 内核态(kernel(0))：运行内核程序，此时可以执行特权指令
  • 用户态(user(1))：运行用户程序，只能执行非内核程序
  • 程序状态字寄存器(PSW)：用来管理内核态和用户态的切换

切换方式：

  • 内核态->用户态：执行一条修改PSW标志位的特权指令
  • 用户态->内核态：由“中断“引发，硬件自动完成变态过程

当用户执行完需要的操作后应从内核态切换为用户态

切换为内核态之后就拥有了一系列高级权限，可以执行更多操作，例如：

  • 设置计时器
  • 清空内存
  • 关闭中断
  • 修改设备状态表
  • 访问I/O设备

微内核（Microkernel）

微内核是指将操作系统的核心功能缩减到最小，只在内核中保留最基本的资源管理功能，如进程调度，内存管理等，将其余功能移动到用户态中
这种设计具有如下好处：

  • 易于拓展：由于核心功能小，故易于拓展
  • 容易移植：容易将微内核移动到其他架构中
  • 更可靠：模块化设计使每个模块各司其职，故更加可靠，减小出错概率
  • 安全性高：由于大部分功能运行在用户态，故减小了系统被攻击的概率
    但缺点是需要频繁在不同状态间进行切换，故内核状态切换过于缓慢

微内核同属一种操作系统结构，除了MS-DOS和微内核结构外，操作系统还提供了一些可以实现的结构，如单核结构，即将所有主要功能都集中在一块大的内核中

进程

要讨论进程的概念就要理解进程与程序之间的关系：

  • Program程序：程序是存储在系统磁盘中的一系列可执行文件（passive entity）
  • Process进程：进程是活动实体（active entity），具体指定要执行的下一条指令的程序计数器和与其相关联的资源

进程的组成部分

  • 进程编码：PID
  • 当前活动：包括程序计数器，进程寄存器
  • 进程栈：包括函数参数、返回地址、局部变量
  • 数据段：全局变量
  • 进程堆：为进程动态分配的堆

PCB:进程控制块，记录进程相关信息，包括进程状态，程序计数器，进程调度策略，块内存限制，打开的文件，日志等信息

进程状态

进程执行具有一个执行周期，周期执行对应状态转换，进程有如下状态：

  • new：进程创建时
  • running：指令运行
  • waiting：进程等待某些事件的发生，如I/O操作或某些完成信号
  • ready：进程准备完成，等待被分配给处理器执行
  • terminate：进程执行完毕
    waiting状态只能到ready状态才可以进行下一步操作
    running状态可以到waiting、ready、terminate任意状态

进程调度

进程调度要实现的目的：

  1. 最大化CPU利用率，快速进行进程间的切换
  2. 在众多进程中选择可靠的进程作为下一个CPU执行进程
  3. 维持进程的调度队列
    • 调度队列如下：
    • 长程队列（job queue）：系统中所有进程的集合
    • 就绪队列（ready queue）：系统中准备好执行的进程队列，包含两个指针，分别指向队列的头和尾（的PCB）
    • 等待队列（waiting queue）：等待执行的进程队列
    • 设备队列（device queue）：等待I/O设备的进程队列
  • 进程切换的本质是上下文切换（context switch），通过PCB中记录的信息完成

  • 进程切换的方法是就绪队列中指针的切换

  • 进程切换步骤

    1. 保存（save）当前进程状态
    2. 选择下一个要运行的进程
    3. 恢复（restore）新进程状态
    4. 切换内存空间
    5. 更新调度队列

Scheduler调度程序

进程调度类型

  • 长程调度（long-term scheduler）：选择将哪些进程丢进ready queue中
  • 短程调度（short-term scheduler）：选择下一个使用CPU资源执行的进程
  • 中程调度（middle-term schduler）：负责内存和磁盘的交换，负责将内存中的资源移到磁盘中以让新的资源进入

CPU scheduler调度器

理想状态下，CPU调度器在ready queue中选择进程并调用CPU执行这项进程
调度的目标：

  1. 提高CPU利用率：尽量减少CPU空闲时间
  2. 提高系统吞吐量：在单位时间内完成更多工作
  3. 降低响应时间：确保交互式系统快速响应用户需求
  4. 保证公平性：确保所有进程公平分配CPU资源

调度类型：

  • 抢占式调度：在任意节点启用中断机制，优先级高的进程抢占优先级低的进程
  • 非抢占式调度：无中断机制，实现简单

调度算法：

  1. 先来先服务（FCFS调度）：顾名思义，按照进程先后顺序先进先出
  2. 最短优先（SJF调度）：活动时间最短的进程优先进入
  3. 优先级调度（Priority调度）：按照优先级排列，数字越小，优先级越高，可以动态决定资源调用
  4. 时间片轮转（RR调度）：设定一个时间片大小，按照这个时间片进行进程轮转调度
  5. 多级反馈队列（Multiple Feedback Queue）：使用多个队列，每个队列有其适合的调度算法，按需定制

平均周转时间：完成时间-到达时间
平均等待时间：完成时间-到达时间-执行时间

进程同步和死锁

进程同步中的相关概念

  • 临界区（critical section）：临界区是指访问共享资源的代码段，同时只有一个进程可以进入该区域
  • 互斥（mutual exclusion）：如果临界区已经被某个进程占用了，互斥保证没有其他资源可以进入这段临界区
  • 锁（lock）：通过acquire和release创建和释放临界区
  • 信号量（semaphore）：一个计数器，用于控制对临界区的访问

计数信号量

  • 通过两个原子操作P和V控制信号量S从而实现进程互斥，P表示S--，V表示S++，当S<=0时，进程阻塞，S>0时进程启用，于是有如下结论
  • 当S=0，表示刚好无资源可用
  • S>0时S的值表示可用进程数
  • S<0,S的绝对值表示阻塞的进程数

死锁Dead Lock

死锁是指在多任务或多线程操作系统中多个进程因为相互等待而导致无法继续执行的状态。死锁会导致系统资源的浪费和性能下降

死锁的条件：

  • 互斥（mutual exclusion）：至少有一个资源是非共享的
  • 保持和等待（hold and wait）：一个进程至少已经持有一个资源并在等待其他进程的运行
  • 非抢占（no preemption）：已经执行的资源不会被抢占
  • 环路等待（circle wait）：存在一个进程链，使得每个进程都在等待别的进程的资源释放

死锁预防：

  • 破坏互斥条件：使资源共享
  • 破坏hold and wait：要求进程请求资源时不持有其他资源
  • 破坏“非抢占”：允许资源抢占
  • 破坏“环路”：要求所有资源按序分配，避免环路形成

死锁避免：
使用银行家算法（banker algorithm）进行死锁避免
计算每个进程的所需资源，比较可用空间，给出进程执行的一个有效序列

内存

每一个进程都需要一块专属的物理地址空间，这就是内存，而为保证进程能够正确运行就需要内存间互不干扰，这就是内存保护机制。（address proptection），包括地址空间和内存隔离

程序运行三种绑定时间

  • 编译时绑定（compile time binding）：编译时绑定内存，生成绝对内存代码
  • 加载时绑定（load time binding）：在编译时不知道内存位置，需要生成可重定位的代码
  • 执行时绑定（execute time binding）：程序执行时动态分配内存段

内存地址类型

  • 逻辑地址（logical address）：由CPU生成，逻辑地址，也被称为虚拟地址
  • 物理地址（physical address）：内存单元中的地址

内存保护机制的实现

分页（paging）

定义：分页是一种内存管理技术，将物理内存分为固定大小的块，称为页框（page frame），将逻辑内存分为大小相同的块，称为页（paging），用页表（page table）将逻辑地址映射到物理地址

  • 页面大小（page size）：一张页面的大小，可用来求页面数量
  • 页号（page number）：地址所在的逻辑页号，在页表中根据页号映射物理地址
  • 偏移量（offset）：由页面大小决定，决定在一张页中的位置

分段（segmentation）

分段是另一种内存管理技术，将程序和数据分为若干段，每个段包括起始地址和段长，更符合程序的自然结构，区别于分页技术，分段中各个段的段长是可控的，因此可以按照需要分配

分页vs分段

  • 分页大小是固定的，分段不是固定的
  • 分页有助于内存管理，分段有助于从程序员的视角看待问题
  • 一个使用页表管理，一个使用段表管理
  • 分页不易出现碎片化，分段容易出现内存碎片（fragmentation）

几种页表结构

  • single-level page table（单级页表）：简单的线性数组，每个条目对应一个页面
  • multi-level page table（多级页表）：采用分级结构，第一级页表指向第二级页表，依次类推
  • inverted page table（倒置页表）：只有一个表，每个条目对应一个物理帧
  • hash page table（哈希页表）：通过哈希页表进行虚拟地址到物理地址的映射

TLB页面访问加速

TLB是一种高速缓存，用来存储最近使用过的页面条目，当CPU重新调度某个页面时，其会先在TLB上寻找，从而加快页表查找效率和命中率

虚拟内存管理

概述

虚拟内存是一种内存管理技术，它使得每个进程都拥有一个虚拟的地址空间。这些虚拟地址空间可以独立于物理内存进行分配和管理。

虚拟内存通过硬件和软件的结合，使得程序员可以编写在有限内存资源上运行的大程序，而不必担心物理内存的限制。

虚拟地址空间限度取决于CPU逻辑地址容量

工作原理

虚拟内存通过地址转换机制，将虚拟地址映射到物理地址。地址转换通常由内存管理单元（MMU）在硬件层面完成。MMU使用页表将虚拟地址翻译为物理地址。
简而言之，动态使用物理地址，通过展示页面的切换完成

  • 页：虚拟内存和物理内存都划分为固定大小的块，称为页。默认情况下，每页的大小是4KB。
  • 页表：页表是存储虚拟地址到物理地址映射关系的数据结构。每个进程都有一个页表，用于管理其虚拟地址空间。

页表机制

通过虚拟地址到物理地址的映射，当CPU访问虚拟地址时，自动将其转化为物理地址

  • 虚拟地址：包含页号和偏移量
  • 页表结构：存储从虚拟地址到物理地址映射关系的数据结构
  • 地址转换：由内存管理单元（MMU）完成，MMU查找页表并将其翻译为物理地址

转化规则

  • 提取页号和偏移量：从虚拟地址中提取出页号和页内偏移量
  • 查找页表：查找页号对应页表项，找到物理内存页框号
  • 计算物理地址：物理页框号+偏移量 = 最终物理地址

验证规则：当虚拟页号小于页表中的limit限制，则转化无法完成

页面调度策略

决定物理内存和磁盘间的资源调度

下列样例中，页面访问序列表示虚拟内存序列，数字表示页面编号，将其替换到物理内存中，下面例子默认页面窗格大小为3


加载页面的过程称为页面错误（缺页fault）

OPT算法：活跃替换（Optimal Page Replacement）

  • 理想最优算法，选择那些在未来最长时间内不会被访问的页面（需要预先知道页面访问频率，故只存在于理想情况）替换
  • 示例：
    • 页面访问序列为：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
    • 替换过程：2->7(7页面出现次数最少)

FIFO算法：先进先出（First In, First Out）

  • 先进先出算法，不考虑页面是否被访问过
  • 会造成belady异常现象
  • 重复出现时不会刷新时间戳
  • 示例：
    • 页面访问序列为：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
    • 替换过程：2->7（7最先进入，最先替换）

LRU算法：频率替换（Least Recently Used）

  • 选择最近使用最少的页面
  • 选择方式是从当前节点往前数最晚到达的节点
  • 示例：
    • 页面访问序列为：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
    • 替换过程：2->7（目前频率都为0，依序选择7）
  • 实现LRU算法的两种方式
    • Counter计时器法：为每个页面添加一个计时器，每当调用该页面时启用计时器，根据页面计时器大小决定替换的页面
    • Stack堆栈法：维护一个栈数据结构，每当有新页面调用时，将其移动到栈顶，从而刷新页面最后访问时间，以此寻找最后调用页面

clock算法：时钟算法（second choice algorithm）

  • 添加一个对页面的指针，指针依序遍历物理内存，遍历则-1，每次访问页面时指针引用值＋1，找到引用值为0时便替换，并将指针后移
  • 示例：
    • 页面访问序列为：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
    • 替换过程：2->7（开始全为1，遍历一轮全为0）
    • 0->0(替换后0引用值为1，其他都为0)
    • 3->1（依此类推）

文件系统

用以存储文件和目录信息，对磁盘中的文件资源进行定位与查找

文件系统地址分配方法：

  • 连续分配法（contiguous allocation）：每个文件在磁盘上占用连续的块，需要起始块号和长度，容易产生外部碎片，扩展困难
  • 链表分配法（linked allocation）：使用链表进行块之间的分配，不易产生外部碎片，容易扩展，顺序访问速度慢
  • 索引分配法（index allocation）：为每个文件分配一个索引块，之后只需要在索引块中寻找文件即可，访问速度快且避免外部碎片但需要格外占用空间
    • 多级索引：采用多块索引块依次指向目标文件