WRY

Where Are You?
You are on the brave land,
To experience, to remember...

0%

《操作系统-精髓于设计原理》读书笔记

Posted on Edited on In
从操作系统汇总中拆分出来，阅读《操作系统-精髓于设计原理》的读书笔记，主要仍是思路思想，着重注意了书中对Linux的思路介绍。

操作系统知识点汇总，参考 ; 本文是针对该参考的继续补充。

《操作系统 精髓与设计原理》

阅读书中感兴趣的重点，对上述知识体系进行补充。

第1章 计算机系统概述

1.8 多处理器和多核计算机组织结构

三种提供复制处理器来提供并行的手段，分别是对称多处理器、多核计算机和集群

对称多处理器（SMP）

SMP具有如下几个重要的特点

  • 具有两个或以上的可比性能的处理器
  • 处理器之间共享内存和I/O设备，通过总线和其他内部连接
  • 处理器共享对I/O设备的访问，要么是相同的通道，要么是连接相同设备的不同通道
  • 所有处理器执行相同的功能（因此称为是对称的）
  • 整个系统由统一一个操作系统控制。

其优势主要体现在：性能，可用性（一个CPU挂掉，系统仍会正常运行），增量成长（以后还可以增加CPU数量），可伸缩性（数量可配置）

每个处理器有两级专用缓存，L1缓存和L2缓存

高速缓存带来了一个和其他兄弟高速缓存之间的一致性问题，通常会通过硬件的方式进行解决。

多核计算机

指将两个或多个处理器（核）组装在同一个芯片上，又称为chip multiprocessor，包含L1指令和数据高速缓存、L2高速缓存、L3高速缓存。

CPU寄存器

简称 名字
PC 程序计数器
IR 指令寄存器
MAR 内存地址寄存器
MBR 内存缓存寄存器

CPU三级缓存

CPU Cache分成了三个级别：L1，L2，L3，级别越小，容量越小，速度越快。

  • 每个核上都有两个L1，一个存放指令，一个存放数据，例如32K大小
  • 每个核上有一个L2的Cache，例如256K大小
  • 同一个CPU的所有核心共享L3 Cache，例如12M大小

CPU访问数据会从L1-> L2 -> L3 -> 内存的方式逐个查找，直至命中。缓存是按照行的方式进行缓存，通常一行是64字节的大小。

个人理解：此处的三级缓存数据的时候的数据位置是和内存中的位置相对应的，不存在区分进程地址的问题。

单核的执行和线程执行之间是对等的关系，通常情况下会将L1 Cache中的内容对应都线程使用的资源

三级缓存采用行缓存（64bytes）策略，会引入缓存一致性的问题，会导致就近数据，多线程写入的时候发生冲突，造成效率低下。

第2章 操作系统概述

2.8 传统UNIX系统

分为三个层次：硬件、内核和用户，操作系统通常称为系统内核。用户可以直接调用操作系统的服务，也可以通过库进行调用；系统调用接口是内核和用户的边界。系统被划分为两个主要的部分：

  • 进程控制，负责内存管理，进程调度和分发，进程同步及进程间通讯
  • 文件管理与I/O，按照字符流或者块的形式在内存和外部设备间交换数据，包含了各种驱动设备；块数据通过内存中增加系统缓冲区的方式，实现磁盘的高速缓存

缺点是：内核功能庞大，集成度高（非模块化），代码不可复用。

2.9 现代UNIX系统

现代UNIX系统通过模块化的方式编写小核心的软件，这些软件可以提供进程需要的功能和服务，每个外部的圆圈代表相应的功能和多种方式实现的接口。

2.10 Linux 操作系统

在Linux操作系统中，采用了模块化的结构，内核在运行时可以链接或者断开链接某些模块（对象文件）。每个模块通常是实现了某些特定的功能。Linux加载模块具有如下两个特点：

  • 动态链接，内核模块可被链接，加载到内存；也可以被断开，移出内存
  • 可堆叠模块，既可高层模块以库的形式调用低层模块；也可以低层模块以用户的形式调用高层模块。

会有如下的有点：

  • 相同代码可以移入单个模块中，降低重复性
  • 内核会确保所需要的模块存在。在加载模块时也会加载他需要的那些模块

内核组件

主要的内核组件有如下：

  • 信号，内核使用信号想进程提供信息，例如告知除零的错误

    其他信号的例子：终端挂起、键盘退出、终端写...

  • 系统调用，进程通过系统调用请求系统服务，有文件系统、进程、调度、进程间通信、套接字和其他。

    调度相关的系统调用：
    • 根据进程pid，设置调度策略（例如FIFO），以及调度策略的相关参数，或者获取最大优先级值
    • 根据进程pid，把轮转时间写入结构体中
    • yield，自动释放处理器，并因为静态优先级，移动到队列的队尾
    进程间通信（IPC）相关的系统调用：
    • 为接收消息分配消息缓冲结构体
    • 。。。看不懂

  • 进程和调度器，创建、管理、调度进程

  • 虚存，为进程分配和管理内存

  • 文件系统，为文件、目录和其他文件相关对象提供一个全局的分层次名命名空间并提供文件系统函数

  • 网络协议，为TCP/IP协议套件提供套接字接口

  • 字符设备驱动，管理向内核一次发送/接收1字节数据的设备。例如终端、打印机

  • 块设备驱动，管理以块为单位向内核发送/接收数据的设备，例如磁盘，CD等

  • 网络设备驱动，管理网卡和通信端口，即管理链接到网桥或路由的网络设备

  • 陷阱和错误，处理CPU产生的陷阱和错误，例如内存错误

  • 物理内存，管理实际内存中的内存页池，并为虚存分配业内存

  • 中断，处理来自外设的中断

整体框架图如下

第3章 进程描述和控制

3.2 进程的状态

参考3.6 节中的UNIX进程状态

进程终止可能的原因

  • 正常完成
  • 超出时限，可在总运行时间、执行时间等等维度上进行限制
  • 内存原因，无可用内存、超出范围
  • 权限问题，写一个只读文件、使用为操作系统保留的指令
  • 数据误用，类型或者未初始化的数据
  • 父进程终止，作为孤儿进程被init进程释放
  • 父进程请求，父进程具有终止其任何子进程的权力

3.3 进程描述

操作系统的控制结构，即其需要掌握的每个进程和资源的当前状态。主要包含如下四大类：

类别 简介
内存表 用于跟踪内存和外存，包含如下的信息，
分配给进程的内存
分配给进程的外存
内存块或者虚存块的任何保护属性，如那些进程可访问共享内存区域
管理虚存需要的各种信息
I/O表 管理计算机系统中的I/O设备和通道。记录他们的状态
文件表 文件信息
进程表 进程会以某种方式链接其他的表。（其他的表之间也会有交叉引用）

进程的控制结构，主要包含进程位置和进程属性两部分。进程的物理表示是至少包含一个或者一组被执行的程序，这些程序、数据、栈、和属性的集合被称为进程映像（process image）。程序要执行需要将程序从外存中载入内存或虚存。如果使用的是虚存，那么OS维护的进程表，需要给出进程映像中每页的位置。

进程属性被称为进程控制块（PCB）如下：

类别 主要信息
进程标识信息
标识符 包括
进程的标识符、
父进程标识符、
用户标识符
处理器状态信息
用户可见寄存器 在用户模式下，执行机器语言时可以访问的寄存器
控制和状态寄存器 用于控制处理器操作的歌中寄存器，包括：
程序计数器（PC）、
条件码（最近算术或逻辑运算的结果，符号、零、进位、等于、溢出等）、
状态信息（中断允许/禁用标识、执行模式）
栈指针 一个进程有一个或者多个相关联的系统栈，用于保存参数、过程调用或系统调用
进程控制信息
调度和状态信息 OS执行调度需要的信息，包括
进程状态（运行、就绪、阻塞、停止等）、
优先级（可能包含，默认、当前、最高许可）、
调度相关信息（具体取决于调度算法）、
事件（继续执行前等待的事件标志）
数据结构 进程会使用队列、环等数据结构链接到其他的进程，用于表示如下的关系：
具有某一优先级且处于等待状态的所有进程
进程之间的父子关系
进程间通信 各种标记、信号和信息可与两个无关进程间的通信关联。
进程特权 进程根据其可以访问的内存和可执行的指令类型来赋予特权。
存储管理 分配给该进程的虚存的段表/或页表的指针
资源所有权和使用权 进程控制的资源，如打开的文件或者其他资源的使用历史，等信息

TODO 回顾本科的Nachos操作系统的调度策略

3.5 操作系统的执行

操作系统的执行，可以分为如下三大类

  • 无进程内核，如图a所示。其具有最显著的特点，OS是在特权模式下运行的单独实体，进程的概念只存在于用户程序。（废弃
  • 在用户进程内运行，如图b所示。OS 函数在特权模式下运行，进入OS函数仅需切换模式，而不需要切换进程
  • 基于进程的操作系统，如图c所示。会将OS作为一组系统进程来执行。

在b模型下，进程结构如下；进入OS 函数之后，会调用共享空间中的OS函数，使用内核栈作为栈，继续执行可能的过程掉用。

3.6 UNIX SVR4 进程管理

UNIX采用了上图b的模型，OS的大部分都在用户进程环境内执行。但UNIX将进程分为了系统进程和用户进程两大类，系统进程在内核模式下运行，执行操作系统的代码，来实现管理功能，例如内存空间的分配和进程交换。

UNIX的进程状态有9大类

状态 说明
用户运行
内核运行
就绪，并驻留在内存中 内核调度，可立即执行
休眠，并驻留在内存中 阻塞状态，等待某个事件的发生，仍在内存中
就绪，被交换 进程已就绪，但交换程序要把他换入内存后才可执行
休眠，被交换 阻塞状态，等待某个事件发生，并被交换到外存
被抢占（Preempted） 进程从内核模式返回用户模式，但内核抢占了它，并做了进程切换，以调度另一个进程
创建 刚被创建，还未做好运行的准备
僵死（Zombie） 进程不再存在，但留下了一条父进程可以收集的记录

被抢占，抢到了内核抢占进程执行的一种方式。被抢占的状态和内存中的就绪状态本质上是同一类，他们共用一个队列进行管理。因为只有在内核模式切换到用户模式

第4章 线程

4.6 Linux的进程和线程管理

4.6.2 Linux 线程

老版本的Linux内核不支持多线程，多线程应用程序需要一组用户级程序库（如pthread）来编写，以便将所有的线程映射到一个单独地内核级进程中。现代UNIX提供一种不区分进程和线程的解决方案，将用户级线程映射到内核级进程，组成一个用户级进程的多个用户级线程映射到共享同一组ID的多个Linux内核级进程上，因此这些进程可以共享文件和内存资源，使得同一个组中进程调度切换不需要切换上下文。

Linux 将复制当前进程的属性创建一个新的进程，进程创建之后，可以共享资源。如文件，信号处理程序和虚存。共享虚存的进程可以视为同一个进程中的线程。但是没有给线程单独定义数据结构，因此Linux不区分进程和线程。使用clone函数替换了原来的fork函数。

4.6.3 Linux 命名空间

在《Docker 容器与容器云》 要点记录 中有更详细的介绍。

Linux中和每个进程相关联的是一组命名空间，它可以使一个共享同一个命名空间下的多个进程拥有和其他进程不同的系统视图（可以让他们产生一种系统中只有他们的错觉）。这和cgroups是轻量级虚拟化的基础。目前Linux有6种命名空间，即mnt、pid、net、ipc、utc和user。命名空间由clone通过6个空间克隆标记创建。

Mount：提供文件系统层次结构的特定视图。一个进程使用的所有文件操作，仅适用于该进程可见的文件系统。（通过共享/从属挂载，新的namespace可以看到部分原namespace下的挂载点。1

UST：UNIX timesharing，和Linux调用uname有关，uname返回当前内核的名字和信息，包括节点名（存在于用于定义实现网络的系统名）和域名（NIS域名）。允许某个NIS域下的一组机器共享一个通用配置文件集。（不懂，在《Docker容器和容器云》中的理解是主机名和域名。

IPC：隔离进程间通信资源，如信号量、POSIX消息队列和共享内存等

PID：隔离进程ID空间，不同的PID NS下可有相同的pid

网络命名空间：隔离与网络相关的系统资源，每个命名空间都有自己的网络设备，IP地址，IP路由表，端口号等。一个网络设备只属于一个网络命名空间，一个套接字也只能属于一个命名空间。

用户命名空间：为其自身的UID提供一个容器（隔离开其他环境），并完全与父进程分离。克隆的使用新的命名空间的进程对父进程的所有资源和特权的子集有使用权和特权。（在容器中，通过--userns-remap，可以实现容器中的root映射到宿主机的普通用户，从而实现权限控制。

Linux cgroup

子系统提供四大功能：

  • 资源限制，对任务使用的资源总额进行限制，如设定可以使用的内存上限，超过这个上限就会出现OOM的提示
  • 优先级分配，通过分配的CPU时间片数量和磁盘IO带宽大小，实际上相当于控制了任务运行的优先级
  • 资源统计，统计系统的资源使用量，可用于计费
  • 任务控制，可对任务执行挂起和恢复等操作

cgroups术语表

  • task（任务）：任务对应一个进程（或线程）
  • cgroup（控制组）：资源控制在cgroup维度实现。cgroup表示按照某种资源控制标准划分而成的任务组，包含一个或者多个子系统，任务可以在cgroup之间移动。
  • subsystem（子系统）：一个资源调度控制器，例如CPU子系统可以控制CPU时间分配，内存子系统可以限制内存的使用量
  • hierarchy（层级）：层级由一系列cgroup以一个树状结构排列而成，每个层级通过绑定对应的子系统进行资源限制。

第6章 并发：死锁和饥饿

6.7 UNIX 并发机制

管道、消息、共享内存、信号量、信号

6.8 Linux 内核并发机制

Linux在UNIX的并发机制的基础之上，还支持一种特殊类型的信号，实时信号。实时信号和标准UNIX信号相比有三个主要的不同点：

  • 支持按优先级顺序排列的信号进行传递
  • 多个信号能进行排队
  • 在标准的信号中，数值和消息只能视为通知，不能发送给目标进程。但实时信号可以将一个指针随信号一起发送过去

Linux还为内核提供了一套丰富的并发机制，专门为内核模式线程准备的。

原子操作

针对整数变量的整数操作以及针对位图中的某一位的操作。在单核处理器上，通过线程不能被中断实现原子，在多核处理器上通过锁住变量实现原子。

自旋锁

通过不断检查内存中的某个变量的值，若为0，置为1，进入，否则忙等。（不需要上下文的切换）。基本自旋锁具体有如下几种类型

  • 普通自旋锁：不被中断处理程序执行或者禁用中断的时候执行（不会被中断干扰）

  • _irq：中断一直被启用的时候，使用这种自旋锁。其会关闭本地处理上的中断

  • _irqsave：不知道执行时间内中断是否启用。获得锁后，本地处理器的中断状态会被保存。等到锁释放的时候会恢复这一状态

  • _bh：关闭下半部的执行。发生中断时，相应的中断处理器只处理最少量的必要工作。下半部是指一段代码执行中断相关工作的其他部分。因此允许尽快的启用当前的中断，但禁用下半部的执行。

自旋锁在单处理器下的工作原理：若关闭了内核抢占，在内核模式下不会被打断，锁在编译期就被删除了；若没有关闭内核抢占，则会被简单的实现为禁用中断。在多核处理器下，会由内核代码（swap and test）来实现。

除基本自旋锁之外，还有读写自旋锁，通过计数和标记实现更高的并发，属于读优先类型

计数 标记 解释
0 1 自旋锁释放并可用
0 0 自旋锁被写线程获得
\(n(n>0)\)​ 0 自旋锁被n个读线程获得
\(n(n>0)\)​ 1 无效

信号量

内核的信号量对用户是不可见的。Linux提供的内核信号量有三种：二元（互斥）信号量、计数信号量和读写信号量。

针对计数信号量，Linux提供三个版本的down（semWait）的操作

  • 对应传统的semWait操作。线程测试信号量，信号量不可用时阻塞，在up操作发生时被唤醒。同样适用于二元信号量

  • down_interruptible：允许因down操作而被阻塞的线程在此期间接收并响应内核信号。若线程被唤醒，则函数down_interruptible会在增加信号量值（相当于取消了该线程的down操作）的同时返回错误代码，这将告知线程对信号量的掉用已经被取消（线程强行释放了信号量）。这个特性在设备驱动程序和其他服务中很有用，可以更加方便的回滚操作down操作。

  • down_trylock：正如字面意思

读写信号量：对读者使用一个计数信号量，对写者使用一个二元信号量。因为读写信号量使用不可中断睡眠，因此每个down只有一个版本。

屏障

RCU（Read-Copy-Update）类似版本控制的机制。通过指针的方式管理资源，每个指针上的内容只可被写者赋值一次，写者写数据，会写到一个副本中，同时将指向副本的指针更新（原子操作）到RCU管理的指针上。读者会读到指针更新前，或者更新后的数据，但是不会读到更新中的错误数据。当对一个指针的所有读者都释放了读锁，该资源会被真的释放掉。

针对读写场景

关于读写场景，自旋锁、信号量和屏障都给出了解决方案。

自旋锁提供的解决方案，是读优先，会造成更新延迟等问题；

信号量通过不同的实现方式，可以实现不同类型（读优先、写优先、公平读写）的读写锁，自由度高

屏障中提到的RCU，会创建副本，耗费更多的空间，但错开了读写之间的冲突，实现了更高的效率（配置中心的策略可能就是如此）。

第7章 内存管理

7.1 内存管理需求

重定位。由于多个进程共享主存，进程在生命周期中可能因为换出外存再换回主存，而出现在主存的不同位置。简单的讲会有如下的寻址需求。

附录 7A 加载和链接

Fig 7.14

加载

加载器把加载的模块放置在内存x开始的位置（满足7.1 中提到的寻址需求）。可以采用三种方式：

  • 绝对加载

    绝对加载器要求给定加载模块总被加载到内存中的同一个位置。但这个耦合度太高，通常会将绝对的内存地址用符号来代替，上层程序通过符号引用来进行替代。如图(b) Absolute load module。

  • 可重定位加载

    可分配到内存中任何地方的加载模块。汇编器和编译器不使用绝对地址，而是使用相对某些已知点(加载时确定)的地址。如下图的(c) Relative load module.

  • 动态运行加载

    在上述两种方案中，使用的地址都在程序被加载时确认且不能修改，这就不能满足程序被换出后换回到不同内存地址的问题。动态运行加载，在真正被执行时才计算它的绝对地址（通过硬件设备保证执行的效率）

  1. Object module 是用户程序指明使用的符号地址

链接

链接器的功能是把一组目标模块作为输入，产生一个包含完整程序和数据模块的加载模块，并传递给加载器。

链接编辑程序（静态），如下图(b)所示，产生可重定位加载模块的链接器。将外部引用替换成了外部模块所在的符号地址。

动态链接器，把某些外部模块的链接推迟到创建加载模块之后，因此加载模块包含到其他程序的未解析的引用，这些引用可以在运行时或加载时解析。

  • 加载时的动态链接，如图Fig 7.14中的Loader下的Dynamic Library，优点如下：
    • 更容易的并入已改变或已升级的目标模块
    • 多应用程序自动代码共享，节省内存空间
    • 更容易的扩展功能
  • 运行时的动态链接，某些链接工作被推迟到了执行时。当调用的模块不存在时，OS定位给模块，加载他。并把他链接到调用模块中。

第8章 虚拟内存

8.1 硬件和控制结构

基础术语：

  • 常驻集：进程执行的任何时候都在内存的部分
  • 实存储器：内存，又称为实存
  • 虚拟内存：通常分配在磁盘上，又称为虚存
  • 页框：内存被划分成的固定大小块

典型的内存管理格式：分页，分段和段页结合类型。如下图所示，其中的P页是否在内存中；M页是否被修改过；其他控制位为了实现页一级的控制保护和共享。

8.1.2 分页

页表结构

分页，需要页表项存储所有虚拟内存的地址映射，这会占用大量的空间，因此提出了两级或者三级的地址映射管理方式，最高一级被限制成了一页的大小，下面的层级同样使用虚存管理的方法。就节省了大量的空间。两级地址映射如下图所示

倒排页表

上述页表的设计的依旧会存在页表项和虚拟地址空间大小成正比的缺陷。因此有倒排页表的提出。逻辑如下图所示，通过散列拉链的方式找到页号对应的物理内存的地址。

TLB

工作原理如下图所示。

8.1.3 分段

分段允许程序员把内存视为由多个地址空间或段组成。有如下的优点：

  • 对于未知大小的数据结构可以申请放入段式虚存，操作系统会根据需要把段换成更大或者更小的段
  • 允许程序独立的改变或者重新编译，而不要求整个程序集重新连接和重新加载。可以通过多个段来实现
  • 有助于进程间共享
  • 有助于保护。程序员或者系统管理员可以更方便的指定段的访问权限

分段系统的地址转换如下图所示。。

8.2 操作系统软件

操作系统内存管理设计取决于三个基本的选择：

  • 是否使用虚存技术
  • 分页分段还是同时使用
  • 为各种存储管理特征采用的算法

虚拟内存的操作系统策略如下图所示：

类别 策略
读取策略 请求分页、
预先分页
放置策略 （决定一个进程块驻留在实存中的什么位置
置换策略 基本算法： 最优、
最近最少使用（LRU )、
先进先出（FIFO）、
时钟、
页缓存
驻留集管理 驻留集大小：固定、可变
置换范围：全局、局部
清除策略 请求式清除、预约式清除
加载控制 系统并发度

  • 读取策略

    • 预先分页

      针对程序刚启动的时候频繁页缺失的问题和从磁盘中一次顺序读取多个页更快的特性，会预先分页

  • 置换策略

    • Clock算法利用使用位和修改位来筛选置换的页。

      1. 找未访问、未修改。不对标志位进行修改。
      2. 若1.没有找到，重新扫描，找未访问，已修改的页；对每个跳过的访问位置为0；
      3. 若2.没有找到，重复第一步

    • 页缓存算法

      使用的是FIFO策略，但不是立马将要置换出去的页踢出内存，而是放入两个链表中管理，一个未修改链表，一个修改链表。当真的需要新的页时，会从未修改和已修改的链表的头部开始取。这么做的好处是，但读到被置换的页，其仍有可能在内存中，恢复成正常状态的代价小；其次修改的页可以批量写会，减少I/O的开销。

  • 驻留集管理

    • 驻留集大小
      • 驻留集大小的影响
        • 若进程给一个进程的内存越少，任何时候驻留在内存中的进程数量就越多，增加了OS找到至少一个就绪进程的可能性就越大。
        • 过小缺页率高，过大，缺页率没有明显的变化
      • 策略
        • 固定大小策略，在进程创建的时候设置好
        • 可变分配策略，根据进程缺页率的情况，动态设置
    • 置换范围
      • 局部置换策略，只在该进程的中的页选择置换
      • 全局置换策略，在全部进程的页中选择置换

8.4 Linux内存管理

Linux内存的基本单位是物理页。页面积大小通常为4KB，也可以支持大页例如2MB。

级别 大小
Page 4KB（1024个Int）,或者2MB

8.4.1 进程的虚拟内存分配

Linux使用三级页表结构，如下图所示。其中Global directory只有一页，每个活动进程对应一个Global Directory，必须存在于内存中。Middle directory和page table都可能是多页。

页面分配，内核维护一系列大小固定的连续页框组，一组可以包含1、2、3、8、16或32个页框，当一页在内存中被分配或者解除分配时，使用伙伴算法来分裂或者合并。伙伴算法示意图如下：

页面置换算法，每个页关联一个8位的age和一个修改位。当页被访问时，age++，当周期性扫描全局页池，age--，属于最少使用频率的策略，缺点是周期性扫描页缓存池，增大了CPU的时间。

在2.6.28之后，引入了新的页面置换算法，分割LRU。页面关联两个状态PG_avtive和PG_referenced。并被分为两大类，激活和非激活，使用链表对他们进行管理。非激活链表中的一页，第一次访问PG_referenced设置为有效，再被访问一次，会从非激活链表中移动到激活链表；若两次访问时间间隔太长，PG_referenced会被重置为无效；同样的激活链表在超时之后会被放到非激活链表中去（状态转移如下图所示）。判断超时进行修改的工作由内核驻留进程kswapd在后台周期性执行。在非激活状态的链表中会被LRU的页面置换算法进行置换。

8.4.2 内核内存分配

Linux内核内存管理物理内存页框，主要功能是为特定用途分配和回收页框。页框的可能所有者包括用户空间进程（即页框是某个进程的虚拟内存当前驻留在实存中的一部分）、动态分配的内核数据、静态内核代码以及业缓冲区。

该部分的内容，个人感觉和STL里面的allocator比较像。

辅助讲解

参考链接 《Linux内核设计与实现》中的内容

物理页的数据结构

描述了物理页是否被分配，谁拥有这个页（Eg：用户空间进程、动态分配的内核数据、静态内核代码、页高速缓存等）

系统中的每个物理页都要分配一个这样的结构体，内核仅仅用这个数据结构来描述当前时刻在相关的物理页中存放的东西，这种数据结构的目的在于描述物理内存本身，而不是描述包含在其中的数据。

页分配

以伙伴算法为基础

内核提供了请求内存的底层机制，并提供了对它进行访问的几个接口，所有这些接口都是以页为单位管理内存(函数定义于<linux/gfp.h>)中。

标识 描述
分配页 分配页
alloc_page(gfp_mask) 只分配一页，返回指向页结构的指针
alloc_page(gfp_mask, order) 分配\(2^{order}\)个连续页，返回指向第一页页结构的指针
__get_free_page(gfp_mask) 只分配一页，返回指向其逻辑地址的指针
__get_free_pages(gfp_mask, order) 分配\(2^{order}\)个连续页，返回指向第一页逻辑地址的指针
get_zerod_page(gfp_mask) 只分配一页，内容填0，返回指向其逻辑地址的指针
地址转换 地址转换
page_address(struct page *page) 把给定的页转换成它的逻辑地址
释放页 释放页
__free_pages(struct page *page, unsigned int order) 释放页，该函数先检查page指向的页描述符，如果该页框未被保留，就把描述符的count字段减1，如果count值变为0，就假定从与page对应的页框开始的\(2^{order}\)个连续页框(物理页)不再使用。
free_pages(unsigned long addr, unsigned int order) 和__free_pages功能一样，不过接收的是第一个页框的逻辑地址
free_page(unsigned long addr) 等价于free_pages(unsigned long addr, 0)

在内核态申请内存：内核认为一旦有内核函数申请内存，那么就必须立刻满足该申请；而在用户态申请时，内核总是尽量延后分配物理内存，用户进程总是先获得一个虚拟内存的使用权，最终通过缺页异常获得一块真正的物理内存。

字节分配

内核以slab为基础

对于常见的以字节为单位进行内存分配来说，内核在<linux/slab.h>中提供了如下的函数，能处理最小的大小为32/64字节，最大为8k。

标识 描述
kmalloc(size_t size, gfp_t flags) 返回一个指向内存块的指针，其内存块至少要有size大小，所分配的内存区在物理上是连续的，出错时，返回NULL
kfree(const *ptr) 释放由kmalloc()分配出来的内存块。(PS：kfree(NULL)是安全的)

个人理解类似STL中alloc

第10章 多处理器、多核和实时调度

在《深入理解Linux内核》一书中提到了优先级相关的内容（粗略阅读，没有深入理解细节）

在普通进程中

  • 静态优先级：静态优先级决定了程序的时间片大小。（时间片用完之后，会变成过期进程；过期进程在活跃进程全部运行完之后才会被重新设置时间片变成活跃进程）

  • 动态优先级：动态优先级决定了调度程序选择哪个新进程来运行。动态优先级根据静态优先级和进程最近运行的情况（最近睡眠时间）决定的。

进程是交互式进程还是批处理进程由平均睡眠时间和静态优先级决定。睡眠时间超过某个阈值的被认为是交互式程序，静态优先级越高的阈值越低，越容易被认为是交互式进程。

在实时进程中（实时进程一直都属于在普通进程中所言的活跃进程队列中）

  • FIFO会根据优先级判断进程是否需要被抢占
  • 时间片调度算法的时间片长度会根据静态优先级进行计算

调度程序会使用如下几个函数完成调度工作：

scheduler_tick()：随着时钟节拍到来以中断的形式被触发，会

  • 检查当前进程是否还属于活跃进程，不属于的话，进程将被重新调度；
  • 根据进程使用的调度策略的不同，修改进程的时间片计数器：针对FIFO，什么也不做；针对RR，会递减时间片，判断是否被用完
  • 调用rebalance_tick(),保证不同CPU的运行队列包含数量基本相同的可运行队列

try_to_wake_up()：把阻塞进程重新插入本地的CPU运行队列。此处会根据进程阻塞时间和其他CPU运行队列的负载情况，可能调整其所属的CPU运行队列

reclac_task_prio()：更新进程的动态优先级

schedule()：选择要被执行的新进程

load_balance：维持多处理器系统中运行队列的平衡

10.3 Linux调度

实时调度

负责Linux实时调度的三个类

  • SCHED_FIFO：先进先出实时线程

    实时类的优先级（0-99）高于Normal类（100-139）。调度有如下的规则

    • 除非有更高优先级的FIFO线程就绪、因等待事件阻塞、自愿放弃，否则不会系统中断
    • 被中断后，放入与其优先级相关联的队列中
    • 更高优先级，等待时间最长的线程优先执行

  • SCHED_RR：轮转实时线程

    • 和FIFO类似，但是每个线程会和一个时间片关联，时间片用完，将会换更高优先级或者同级的其他线程执行

  • SCHED_NORMAL：其他非实时线程

    • 仅当实时队列中无线程时，才会被调度

非实时调度

Linux 2.4的SCHED_NORMAL策略的调度随着中央处理器和程序数量的增加，表现并不好，有如下的缺点

  • 多处理器仅使用一个运行队列，线程可能被调度到任何一个处理器上，造成缓存命中率低
  • 运行队列锁，限制了调度的效率
  • 不可抢占

在Linux 2.6中进行了改进，提出了完全公平的调度策略。会根据线程的占用CPU的时间排序，每次选择占用时间最短的线程执行。

同时引入了组的概念，将一组任务当成一个任务进行调度。

个人理解：多级优先调度队列模型的调度策略，只是针对分时任务（优先级最低）的。在Unix SVR4调度策略中有体现。

第11章 I/O管理和磁盘调度

11.6 RAID

11.9 Linux I/O

磁盘调度算法

Linux页面缓存

Linux维护一个页面缓存，以缓存从普通文件系统中的读写或缓存虚拟内存的页面，他涉及所有的磁盘和内存间的数据交换。好处：

  • 脏页面可以经过多次修改，只通过I/O写会一个最终的版本。
  • 脏页面可以被适当的排序，从而高效的写回。

脏页面在两种情况下会被写回

  • 空闲内存低于某个阈值时

第12章 文件管理

12.8 UNIX 文件管理

12.8.1 索引节点

一个索引节点，记录了这个文件的所有元信息，包含了文件的基本属性、文件地址等。

12.8.2 文件分配

文件分配是以块为基础完成的，根据需要进行动态分配。在UNIX中索引节点包含直接指针和三个（1，2，3级）间接指针（见上图）。他们依次可以索引\(12\)，\(512\)，\(512*512\)， \(512*512*512\)​个块。

12.9 Linux 虚拟文件系统

Linux提供了统一的简单的文件系统接口，通过系统调用操作某个文件的请求，会被映射到该文件所属实际文件系统的具体操作上。这称之为虚拟文件系统（Virtual File System）。结构如下图所示

VFS主要包含如下四个对象：

  • 超级块对象（superblock object），描述了特定文件系统的信息，对应于磁盘上特定扇区的文件系统超级块或文件系统控制块，包含如下的信息：
    • 挂接的设备
    • 基本块大小
    • 超级块是否被修改
    • 文件系统标志
    • 指向文件系统根目录的指针
    • 控制访问文件系统的信号量
    • 操作超级块的函数指针数组的指针，例如alloc_inode、write_inode（写回磁盘）、remount_fs（重新挂载）
    • 。。。
  • 索引节点对象（innode object)，与一个文件相关联，包含除了文件名和实际数据内容外的所有信息。
  • 目录项对象（dentry object），是路径上的一个特定的组成，包括一个指向索引节点的指针，还包括一个指向父目录的指针和指向子目录的指针
  • 文件对象（file object），在进程打开一个文件的时候创建，在调用close之后销毁。

第14章 虚拟机

14.3 容器虚拟化

。。。