操作系统学习笔记

一、系统内核

1.基础

• 功能
  管理进程、线程
  管理内存
  管理硬件设备

• 内核空间，这个内存空间只有内核程序（内核态）可以访问；
• ⽤户空间，这个内存空间专门给应用程序使用（用户态）；

2.Linux设计

一切皆文件

（1）MutiTask 多任务

Linux 是⼀个多任务的操作系统，并发或并行。

（2）SMP 对称多处理

着每个 CPU 的地位是相等的，对资源的使⽤权限也是相同的，多个 CPU 共享同⼀个内存，每个 CPU 都可以访问完整的内存和硬件资源。

（3）ELF 可执行文件链接格式

是 Linux 操作系统中可执⾏⽂件的存储格式

（4）Monolithic Kernel 宏内核

宏内核：系统内核的所有模块，⽐如进程调度、内存管理、⽂件系统、设备驱动等，都运⾏在内核态。
微内核：只保留最基本的能⼒，⽐如进程调度、虚拟机内存、中断等，把⼀些应⽤放到了⽤户空间，⽐如驱动程序、⽂件系统等。
混合型内核：它的架构类似微内核，内核中包含最小核心，其他模块在此基础上构建，实现时类似宏内核，即内核作为一个完整程序，大部分服务都在内核中，像宏内核包裹着微内核。

3.Windows设计

（1）MutiTask 多任务

（2）SMP 对称多处理

（3）PE 可移植执行文件

扩展名为.exe，.dll，.sys等

（4）混合型内核

二、内存管理

1.虚拟内存

虚拟内存地址：程序所使用的内存地址
物理内存地址：实际存在硬件⾥⾯的空间地址
进程持有的虚拟地址会通过 CPU 芯⽚中的内存管理单元（MMU）的映射关系，来转换变成物理地址

2.内存分段

• 定义：程序是由若⼲个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就⽤分段（Segmentation）的形式把这些段分离出来。
  

• 组成：
  段选择子（含段号；而段表保存段的基地址、段的界限、特权等级）。
  段内偏移量，位于0和段界限之间，与段的基地址相加既物理地址。

• 存在问题：
  内存碎片：外部内存碎片（多个不连续的小物理内存），内部内存碎片（装载的程序的部分内存可能并不常被使用）
  内存交换效率低：内存交换可以解决内存碎片问题，就是把内存上的内容暂存到硬盘中。但如果某个程序占内存空间很大，交换会很低效。

3.内存分页

（1）基础概念

• 分页：把整个虚拟和物理内存空间切成一段段固定尺⼨的大小

• 页：在 Linux 下，每一页的大小为 4K

• 页表：虚拟地址与物理地址之间通过页表来映射

• 缺页异常：当进程访问的虚拟地址在⻚表中查不到时，系统会产生一个缺页异常。

• 问题解决
  内存碎片：采⽤了分⻚，那么释放的内存都是以⻚为单位释放的，也就不会产⽣⽆法给进程使⽤的⼩内存。
  内存交换：一次性写入磁盘的只有少数的几个页
  程序加载：无需一次性把程序全部加载到物理内存，运行用到时在加载。

• 组成：
  页号作为页表的索引，包含每页所在的物理内存基地址。
  页内偏移与基地址相加既物理地址。
  

• 存在问题：
  单级页表：很占用空间

（2）多级页表

• 问题解决
  多级页表：利用局部性原理，按需（被用到时）创建对应等级的页表项。

64位系统采用的是四级目录。

（3）TLB 页表缓存

用于缓存常用页表项，会被MMU优先查询，提升地址转换效率。

4.段页式内存管理

内存分段+内存分页

• 组成：
  段号（含段号；而段表保存段的基地址、段的界限、特权等级）。
  段内页号，位于0和段界限之间，与段的基地址相加既物理地址。
  页内位移，位于0和段界限之间，与段的基地址相加既物理地址。

段表→（页表起始地址）→页表→（物理页号）→+页内位移→物理地址

5.Linux内存管理

每个段都是从0地址开始，到整个4GB虚拟空间（32位）。屏蔽了处理器的逻辑地址，系统和应用程序直面虚拟地址。

虚拟地址被分为内核空间和用户空间。

每个程序用户空间独立，内核空间共享。

• 用户空间构成
  
  • 程序文件段：二进制可执行代码
  • 已初始化数据段：静态常量
  • 未初始化数据段：未初始化的静态常量
  • 堆段：动态分配的内存（malloc()）
  • 文件映射段：动态库、共享内存（mmap()）
  • 栈段：局部变量、函数调用的上下文，大小一般固定，但也可以调。

三、进程与线程

略写，代码详情见C++高性能服务器的第二章、第三章。

1.进程状态转移

2.PCB 进程控制块

• 组成
  进程描述信息：进程标识符（唯一的标识进程），用户标识符（进程归属的用户）
  进程控制和管理信息：进程的状态、优先级
  资源分配清单：内存地址空间、虚拟地址空间、打开文件的列表、使用的I/O设备信息
  CPU 相关信息：CPU寄存器的值

• 形式：链表
  就绪队列：处于就绪状态的进程链在⼀起
  阻塞队列：等待某事件⽽处于等待状态的进程链在⼀起

3.进程上下文切换

1. 基于时间片的公平调度算法；
2. 进程在系统资源不⾜（⽐如内存不⾜）时，要等到资源满⾜后才可以运⾏，这个时候进程也会被挂起，并由系统调度其他进程运⾏；
3. 当进程通过睡眠函数 sleep 这样的⽅法将⾃⼰主动挂起时，⾃然也会重新调度；
4. 为了保证⾼优先级进程的运⾏，当前进程会被挂起；
5. 发⽣硬件中断时，CPU 上的进程会被中断挂起，转⽽执⾏内核中的中断服务程序；

4.线程

（1）优缺点

• 优点
  ⼀个进程中可以同时存在多个线程；
  可以并发执行；
  共享地址空间和文件等资源；

• 缺点
  当进程中的⼀个线程崩溃时，会导致其所属进程的所有线程崩溃。

（2）与进程比较

• 对比
  单位：进程是资源分配的单位，线程是 CPU 调度的单位；
  资源：进程拥有⼀个完整的资源平台，⽽线程只独享必不可少的资源，如寄存器和栈；
  开销：线程能减少并发执⾏的时间和空间开销；
  状态：线程同样具有就绪、阻塞、执⾏三种基本状态，同样具有状态之间的转换关系；

• 开销减少
  创建时间短：共享很多资源
  通知时间短：需要释放的资源少
  上下文切换快：共享一个页表（在同一个进程中）
  数据传递快：共享内存和文件资源，因此无需经过内核

（3）线程实现

• 用户线程
  在用户空间实现，由用户态的线程库完成线程管理。含线程控制块TCB。多个用户线程对应一个内核线程。

  • 优点：
    • TCB 由⽤户级线程库函数来维护，可⽤于不⽀持线程技术的操作系统。
    • 无需用户态与内核态的切换，所以速度特别快。
  • 缺点：
    • 由于操作系统不参与，一个线程发起系统调用而阻塞，则会阻塞所有线程。
    • 一个线程开始运行后，其他线程没有权力打断，无法运行。
    • 由于时间片分配给进程，因此每个线程得到的时间片会很少。

• 内核线程
  在内核中实现的线程，是由内核管理的线程。一个用户线程对应一个内核线程。

  • 优点：
    • 一个线程阻塞，不影响其他线程。
    • 时间片分配给线程
  • 缺点：
    • 由操作系统维护PCB和TCB。
    • 线程创建、终止、切换都需要系统调用，系统开销大。

• LWP 轻量级进程
  在内核中来⽀持⽤户线程。⼀个进程可有⼀个或
  多个 LWP，每个 LWP 跟内核线程⼀对⼀映射。

  • 1 : 1 ，即⼀个 LWP 对应 ⼀个⽤户线程；实现并行，一个LWP阻塞不影响其他的；但系统开销大。
  • N : 1 ，即⼀个 LWP 对应多个⽤户线程；切换上下文效率高；但一个用户线程阻塞，也会影响其他的。
  • M : N ，即多个 LMP 对应多个⽤户线程；综合前两个的优缺点。

（4）线程安全

在C++中确保线程安全，可以采用以下几种方式：

1. 使用互斥量（Mutex）：互斥量可以用来防止多个线程同时访问共享资源，从而避免数据竞争的问题。例如，使用std::mutex来保护共享资源。

2. 使用读写锁（Reader-Writer Lock）：读写锁允许多个读线程同时访问共享资源，但是写线程必须独占资源。这样可以在保证线程安全的同时，也尽可能地提高系统的并发性。

3. 使用原子操作：在C++中，可以使用std::atomic类型来定义原子变量，并使用原子操作来对共享资源进行操作。

4. 使用条件变量（Condition Variable）：条件变量可以用来在线程之间传递信号，从而控制线程的执行流程。

5. 使用线程本地存储（Thread-Local Storage）：线程本地存储可以用来给每个线程分配独立的存储空间，从而避免数据冲突的问题。例如：

   #include <thread>
   #include <iostream>
   __thread int thread_specific_data; // 使用 __thread 关键字声明线程局部变量
   void thread_function() {
       thread_specific_data = 10; // 线程独立地设置变量
       std::cout << "Value in thread: " << thread_specific_data << std::endl;
   }
   int main() {
       std::thread t1(thread_function);
       std::thread t2(thread_function);
       t1.join();
       t2.join();
       return 0;
   }
   

   使用线程局部存储避免共享数据的竞争条件。

5.进程间通信

（1）匿名管道

pipe() //创建

管道：内核中的一串缓存，只能单向传输，通信效率低。数据先进先出，不支持lseek等函数。
匿名管道：只能是有亲缘关系（父子进程）的进程间通信。生命周期受到进程限制。

（2）有名管道

mkfifo() //创建

有名管道：以文件形式存在，有一个路径名，可以不同进程间通信。但通信时仍使用内核中的缓存。

（3）消息队列

消息队列：是保存在内核中的消息链表，在发送数据时，会分成⼀个⼀个独⽴的数据单元，也就是消息体（数据块）。

• 相比管道：

  • 比管道通信效率高。
  • 管道是无格式的字节流，消息队列需要约定好数据结构。
  • 生命周期跟随内核。
  • 是异步的，无需阻塞。

• 缺点

  • 通信不及时。
  • 不适合大数据的传输（每个消息体都有长度限制）。
  • 存在用户态和内核态的拷贝开销。

（4）共享内存

shmget() //创建
shmdt() //解除进程关联
shmctl() //销毁

共享内存：不同进程各拿出⼀块虚拟地址空间来，映射到相同的物理内存中。

• 相比管道和队列：
  • 无需经过内核态，效率高。

（5）内存映射

mmap() //创建
munmap() //销毁

内存映射：将磁盘文件的数据映射到内存，用户通过修改内存就能修改磁盘文件。是非阻塞的。必须要有读权限，且文件的访问权限应该是内存访问权限的子集。

• 父子进程间：
  先创建父进程→创建映射区→创建子进程

• 其他进程间：
  创建一个大小不是0的文件→各个进程分别创建映射区

• 相比共享内存：

  • 内存映射有文件关联，是持久化的。共享内存虽然也不会随着进程退出而销毁，但系统重启数据便会丢失。
  • 内存映射适合频繁读写大文件，将文件的一部分映射到内存中；共享内存可以很高效地进行进程间通信。
  • 内存映射可以fork继承给子进程；共享内存不可以继承。

（6）匿名映射

匿名映射：无需创建具体文件的内存映射技术。相比内存映射，无需与文件系统交互。它和“共享内存”十分像，但实际上并不是一个事物。

（7）信号量

sem_init() //信号量初始化
sem_destroy() //信号量销毁
sem_wait() //信号量加锁，-1
sem_post() //信号量解锁，+1

信号量：是⼀个整型的计数器，主要⽤于实现进程间的互斥与同步，⽽不是⽤于缓存进程间通信的数据。

（8）信号

一些定义好的信号（比如Ctrl+C 就是信号 2 ，SIGINT）。可以默认执行、忽略（SIGKILL和SIGSEGV 除外）、或者捕获来做一些事情。

signal() //捕获信号，在捕获后可以执行一些自定义函数

（9）Socket

int socket(int domain, int type, int protocal)

可以用于跨网络通信。

• domain 参数⽤来指定协议族，⽐如 AF_INET ⽤于 IPV4、AF_INET6 ⽤于 IPV6、AF_LOCAL/AF_UNIX ⽤于本机；
• type 参数⽤来指定通信特性，⽐如 SOCK_STREAM 表示的是字节流，对应 TCP、SOCK_DGRAM 表示的是数据报，对应 UDP、SOCK_RAW 表示的是原始套接字；
• protocal 参数原本是⽤来指定通信协议的，但现在基本废弃。⼀般写成 0 即可；

TCP

• 服务端和客户端初始化 socket ，得到⽂件描述符；
• 服务端调⽤ bind ，将绑定在 IP 地址和端⼝;
• 服务端调⽤ listen ，进⾏监听；
• 服务端调⽤ accept ，等待客户端连接；
• 客户端调⽤ connect ，向服务器端的地址和端⼝发起连接请求；
• 服务端 accept 返回⽤于传输的 socket 的⽂件描述符；
• 客户端调⽤ write 写⼊数据；服务端调⽤ read 读取数据；
• 客户端断开连接时，会调⽤ close ，那么服务端 read 读取数据的时候，就会读取到了EOF ，待处理完数据后，服务端调⽤ close ，表示连接关闭。

注意：监听socket和已完成连接socket不是一个事物。

UDP

每次通信时，调⽤ sendto 和 recvfrom，都要传⼊⽬标主机的 IP 地址和端⼝。

本地通信

本地字节流 socket 和 本地数据报 socket 在 bind 的时候，不像 TCP 和 UDP 要绑定 IP 地址和端⼝，⽽是绑定⼀个本地⽂件。

6.线程间通信

（1）信号量

略，参考进程的信号量。

（2）条件变量

// 类似信号量的作用
pthread_cond_init() //初始化
pthread_cond_destroy() //销毁
pthread_cond_wait() //等待/阻塞
pthread_cond_signal() //唤醒

（3）生产者-消费者问题

• 概述：

  • 生产者在⽣成数据后，放在⼀个缓冲区中。
  • 消费者从缓冲区取出数据处理。
  • 任何时刻，只能有⼀个⽣产者或消费者可以访问缓冲区。

• 分析：
  任何时候只能有一个线程操作缓冲区，需要互斥。
  缓冲区空/满时，必须等待生产/消费，需要同步。

这里建议自己代码实现一下~

（4）哲学家就餐问题

• 概述：

  • 5 个哲学家围着一个桌子吃饭。
  • 只有 5 ⽀叉⼦，每两个哲学家之间放一支叉子。
  • 哲学家围在⼀起先思考，思考中途饿了就会想进餐。
  • 哲学家要两⽀叉⼦才愿意吃，左右手各拿一个叉子。
  • 吃完后会把叉子放回原处，继续思考。

• 方案一：死锁

  • 每个哲学家先拿左边叉子，再拿右边叉子，然后吃饭，吃完放下左边叉子，再放下右边叉子。
  • 会发生死锁！每个哲学家都是左手有叉子，而右手没有，谁都吃不成！
    

• 方案二：互斥信号量

  • 只要有一个哲学家开始拿叉子，其他哲学家就不能动。
  • 可以吃饭，但效率略低。

• 方案三：分支
  • 偶数编号哲学家先左后右，奇数编号哲学家先右后左。
  • 可以吃饭，效率最佳。
    
• 方案四：信号量互斥
  • 维护一个状态数组，只有哲学家的两个邻居都没有进餐时，才可以进入进餐状态。邻居再想进餐，则会被阻塞。
  • 可以吃饭，效率最佳。

这里建议自己代码实现一下~

（5）读者-写者问题

• 概述
  「读-读」允许：同⼀时刻，允许多个读者同时读
  「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
  「写-写」互斥：没有其他写者时，写者才能写

分为读者优先、写者优先、公平策略。（详情见图解系统P256）

四、锁

1.互斥锁和自旋锁

（1）互斥锁

pthread_mutex_init() //初始化
pthread_mutex_destroy() //销毁
pthread_mutex_lock() //加锁
pthread_mutex_unlock() //解锁

任何时候，至多只有一个线程可以锁定该互斥量。试图对已经锁定的某一互斥量再次加锁，将可能阻塞线程或者报错失败。一旦线程锁定互斥量，随即成为该互斥量的所有者，只有所有者才能给互斥量解锁。可以用于线程同步。

（2）自旋锁

• 相比互斥锁
  • 自旋锁加锁失败后，线程会忙等待，直到它拿到锁。互斥锁加锁失败后，线程会释放 CPU ，给其他线程。
  • 自旋锁没有线程上下文切换开销。若被锁住的代码执行时间很短，应该采用自旋锁而非互斥锁。
  • 在单核CPU上，需要抢占式调度器，否则会一直自旋。

2.死锁

（1）基础概念

两个线程为了保护两个不同的共享资源⽽使⽤了两个互斥锁，那么这两个互斥锁应⽤不当的时候，可能会造成两个线程都在等待对⽅释放锁，在没有外⼒的作⽤下，这些线程会⼀直相互等待，就没办法继续运⾏，这种情况就是发⽣了死锁。

• 条件
  • 互斥条件：多个线程不能同时使⽤同⼀个资源。
  • 持有并等待条件：线程在等待资源 2 的同时并不会释放⾃⼰已经持有的资源 1。
  • 不可剥夺条件：当线程已经持有了资源 ，在⾃⼰使⽤完之前不能被其他线程获取。
  • 环路等待条件：两个线程获取资源的顺序构成了环形链。

（2）调试

参考图解系统P270。

3.读写锁

//对应该函数
pthread_rwlock_init() //初始化
pthread_rwlock_destroy() //销毁
pthread_rwlock_rdlock() //读锁
pthread_rwlock_wrlock() //写锁
pthread_rwlock_unlock() //解锁

默认写优先锁：写锁为独占锁（写的优先级高，写时不能有其他的读写），读锁为共享锁（读的时候可以很多线程一起读）。

可以选择读优先、写优先、公平策略。

公平读写锁⽐较简单的⼀种⽅式是：⽤队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁即可，这样读线程仍然可以并发，也不会出现「饥饿」的现象。

4.乐观锁和悲观锁

（1）悲观锁

访问资源前先上锁。互斥锁、自旋锁、读写锁都是此类。

（2）乐观锁

又名无锁编程，先修改共享资源，再验证是否有冲突，若没有则操作完成。若有，则放弃本次操作。

五、调度算法

1.进程调度算法

（1）基础

• 触发系统调度：
  创建
  就绪→运行
  运行→就绪
  运行→阻塞
  结束

• 分类
  非抢占式、抢占式

（2）先到先服务调度算法

顾名思义。对长作业有利，但不适用于短作业、I/O繁忙型作业。

（3）最短作业优先调度算法

顾名思义。对长作业不利。

（4）高响应比优先调度算法

$$优先权=\frac{等待时间+要求服务时间}{要求服务时间}$$
权衡了短作业和长作业。

（5）时间片轮转调度算法

每个作业都按相同时间片运行。但时间片太短会导致过多的进程上下文切换，太长引起对短作业进程的响应时间变长。

（6）最高优先级调度算法

静态优先级：创建进程时确定。
动态优先级：根据进程的动态变化调整优先级（类似高响应比）。
此外还分为抢占式和非抢占式。可能导致低优先级的进程永远不会运行。

（7）多级反馈队列

1. 设置了多个不同优先级的队列。
2. 优先级越高，被分配的时间片越短。
3. 相应优先级的时间片使用完，进程会被分配到下一级的队尾。

兼顾了长短作业，有较好的响应时间。

2.页面置换算法

（1）基础

• 缺页异常：当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调⼊到物理内存。

  • 缺页中断在指令执行「期间」产⽣和处理中断信号，而一般中断在⼀条指令执行「完成」后检查和处理中断信号。
  • 缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行。

• 页表项
  

  • 状态位：表示该页是否有效。
  • 访问字段：记录一段时间内访问次数。
  • 修改位：是否被修改过。被修改过，置换页时要写入磁盘，否则不用。
  • 硬盘地址：物理块号。

（2）最佳页面置换算法 OPT

置换未来最长时间不访问的页面。很理想，但实际无法预测未来。

（3）先进先出置换算法 FIFO

顾名思义。效率略差。

（4）最近最久未使用的置换算法 LRU

选择最长时间没有被访问的页面置换，需要维护一个所有页的链表，最多使用的在链表头部，最少使用的在链表尾部。因此开销比较大。

（5）时钟页面置换算法 Lock

（6）最不常用置换算法 LFU

选择访问次数最少的页面淘汰。

• 但一方面，要增加一个计数器实现，有硬件成本。
• 同时要查找哪个页面访问次数最小，如果链表长度很大，也很耗时。
• 同时，LFU只考虑频率，而没有考虑时间。有些页面过去访问多，但现在已经不用了，也会因此次数多而无法剔除。结局方法：可以定期减少访问次数。

3.磁盘调度算法

（1）先来先服务算法 FCFS

顾名思义。如果访问的磁道很分散，效率很差。

（2）最短寻道时间优先算法 SSF

选择到当前磁头位置最短的请求访问。但如果一直有新请求加入，可能会导致磁头一直在一小块区域访问，离得远的请求一直无法访问到（饥饿）。

（3）扫描算法（电梯算法） SCAN

磁头一直在一个方向移动，访问所有未完成的请求，直到到达改方向上的最后磁道，才调换方向。不会有饥饿现象，但是中间位置的磁道很占便宜（被扫描次数多）。

（4）循环扫描算法 C-SCAN

只有磁头朝某个特定⽅向移动时，才处理磁道访问请求，⽽返回时直接快速移动⾄最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求。

（5）LOOK与C-LOOK算法

• LOOK算法：
  磁头在每个方向上仅仅移动到最远的请求位置（而不是到边缘），然后立即反向移动，反向移动过程会响应请求。
• C-LOOK算法：
  磁头在每个方向上仅仅移动到最远的请求位置（而不是到边缘），然后立即反向移动，反向移动过程不会响应请求。

五、文件系统

⽂件系统是操作系统中负责管理持久数据的⼦系统。

1.文件系统组成

• 目录项：dentry，缓存在内存，包含文件名字、索引节点指针。每个文件都会有。
• 索引节点区：文件被访问时进入内存。
  • 索引节点：inode，持久化在磁盘，包含inode编号、文件大小、访问权限、创建时间、修改时间、磁盘位置。每个文件都会有。
• 超级块：文件系统详细信息，块数、块大小、空闲块。文件系统挂在时进入内存。
• 数据块区
  • 数据块：储存文件或目录数据。

更详细的结构：

• 块组描述符：包含⽂件系统中各个块组的状态，⽐如块组中空闲块和 inode 的数目等，每个块组都包含了⽂件系统中「所有块组的组描述符信息」。
• 数据位图和 inode 位图， ⽤于表示对应的数据块或 inode 是空闲的，还是被使⽤中。

有很多重复信息，用于冗余备份和恢复。

2.虚拟文件系统

文件系统和用户层的中间层，定义了一组所有文件系统都支持的数据结构和标准接口。

• 磁盘的⽂件系统，直接把数据存储在磁盘中。
• 内存的⽂件系统，⽂件系统的数据存储在内存空间， /proc 和 /sys ⽂件系统都属于这⼀类，读写这类⽂件，实际上是读写内核中相关的数据。
• ⽹络的⽂件系统，⽤来访问其他计算机主机数据的⽂件系统，⽐如 NFS、SMB 等等。

⽂件系统⾸先要先挂载到某个⽬录才可以正常使⽤，⽐如 Linux 系统在启动时，会把⽂件系统挂载到根⽬录。

3.文件的使用

操作系统为每个进程维护⼀个打开⽂件表，⽂件表⾥的每⼀项代表「⽂件描述符」。包含以下信息：

• ⽂件指针：系统跟踪上次读写位置作为当前⽂件位置指针，这种指针对打开⽂件的某个进程来说是唯⼀的；
• ⽂件打开计数器：系统在删除打开⽂件条⽬之前，必须等待最后⼀个进程关闭⽂件；
• ⽂件磁盘位置：绝⼤多数⽂件操作都要求系统修改⽂件数据，该信息保存在内存中，以免每个操作都从磁盘中读取；
• 访问权限：每个进程打开⽂件都需要有⼀个访问模式（创建、只读、读写、添加等）；

4.文件的存储

4.空闲空间管理

（1）空闲表法

空闲表法：为所有空闲空间建⽴⼀张表，表内容包括空闲区的第⼀个块号和该空闲区的块个数。是连续分配的。

仅当有少量的空闲区时才有较好的效果。当有大量小空闲区是，空闲表会变得很大，顺序查询效率很低。不适用于大型文件系统。

（2）空闲链表法

空闲链表法：每⼀个空闲块⾥有⼀个指针指向下⼀个空闲块。

简单，但不能随机访问，⼯作效率低，在链上增加或移动空闲块时需要做很多 I/O 操作，同时数据块的指针消耗了⼀定的存储空间。不适用于大型文件系统。

（3）位图法

位图法：是利⽤⼆进制的⼀位来表示磁盘中⼀个盘块的使⽤情况。

Linux就用了这个方法管理空闲数据块和空闲incode块。

5.目录的存储

普通⽂件的块⾥⾯保存的是⽂件数据，⽽⽬录⽂件的块⾥⾯保存的是⽬录⾥⾯⼀项⼀项的⽂件信息。以列表的形式，记录⽬录下的⽂件信息（如⽂件名、⽂件 inode、⽂件类型等）。

⽬录查询优化1：对文件名进行哈希计算，保存为哈希值，大幅提升检索效率。

⽬录查询优化2：把当前使⽤的⽂件⽬录缓存在内存，从⽽降低磁盘操作次数，提⾼⽂件系统的访问速度。

6.软链接和硬链接

链接（Links）是一种文件，它指向另一个文件或目录。（个人看法：可以联想一下网址链接的作用）

（1）软链接

软链接：软链接类似于Windows中的快捷方式，它包含了一个指向另一个文件或目录的路径。软链接是一个独立的文件，有自己的inode。

• 可以跨文件系统：软链接可以指向不同文件系统中的文件或目录。
• 删除影响：删除原始文件会使软链接变为“死链接”（dangling link）。
• 路径变化影响：如果原始文件或目录的路径发生变化，软链接将不再有效。

（2）硬链接

硬链接：指向文件的直接指针，它与原始文件共享相同的inode（索引节点）。这意味着硬链接和原始文件实际上是同一个文件，它们共享相同的数据块。

• 不可跨文件系统：硬链接不能跨越不同的文件系统。
• 删除限制：删除原始文件不会影响硬链接。还要把所有硬链接都删了，才能真正的删除对应文件。

7.文件I/O

（1）缓冲与非缓冲I/O

• 缓冲 I/O，利⽤的是标准库的缓存实现⽂件的加速访问（减少系统调用次数），⽽标准库再通过系统调⽤访问⽂件。
• ⾮缓冲 I/O，直接通过系统调⽤访问⽂件，不经过标准库缓存。

（2）直接与非直接I/O

• 直接 I/O，不会发⽣内核缓存和⽤户程序之间数据复制，⽽是直接经过⽂件系统访问磁盘。

• ⾮直接 I/O（默认），读操作时，数据从内核缓存中拷⻉给⽤户程序，写操作时，数据从⽤户程序拷⻉给内核缓存，再由内核决定什么时候写⼊数据到磁盘。

• 如果使用了非直接I/O，什么时候内核才会把缓存数据写入磁盘？

  • 调用write后，且内核缓存数据太多时
  • 用户主动调用sync
  • 内存十分紧张，无法再分配页面时
  • 内核缓存的数据的缓存时间超过阈值时

（3）阻塞与非阻塞I/O

• 阻塞I/O：等待内核数据准备好、等待数据从内核态拷贝到用户态
  

• 非阻塞I/O：等待数据从内核态拷贝到用户态。需要持续轮询。
  

• I/O多路复用（非阻塞）：等待数据从内核态拷贝到用户态。被通知前可以做其他事情。
  

（4）同步与异步I/O

• 同步I/O：所有阻塞、非阻塞I/O。在read调用时需要等待，内核实现的效率不高时，会等待很久。

• 异步I/O：无需等待。
  

六、设备管理

1.设备控制器

为了屏蔽设备之间的差异，每个设备都有⼀个叫设备控制器（Device Control） 的组件。属于硬件部分。

控制器组成：

• 数据寄存器，CPU 向 I/O 设备写⼊需要传输的数据。
• 命令寄存器，CPU 发送⼀个命令，告诉 I/O 设备，任务完成后，会把状态寄存器⾥⾯的状态标记为完成。
• 状态寄存器，⽬的是告诉 CPU ，现在已经在⼯作或⼯作已经完成。直到状态寄存标记成已完成，CPU 才能发送下⼀个字符和命令。

输入输出设备：

• 块设备：把数据存储在固定⼤⼩的块中，每个块有⾃⼰的地址（硬盘，USB等）。控制器为其设立了一个可读写的数据缓冲区，减少频繁操作。
• 字符设备：以字符为单位发送或接收⼀个字符流，字符设备是不可寻址的，也没有任何寻道操作（鼠标、键盘等）。

CPU与控制寄存器和数据缓冲区通信：

• 端口I/O：每个控制寄存器被分配一个I/O端口。
• 内存映射I/O：将所有控制寄存器映射到内存空间中。

2.I/O控制方法

• 轮询等待：让 CPU ⼀直查状态寄存器，很糟糕的方法。
• 中断：设备完成任务时，由中断控制器通知CPU，CPU就停下手头的任务来处理中断事件。但对于频繁读写数据的磁盘并不友好，CPU经常被打断，会占⽤CPU ⼤量的时间。
  • 软中断：如代码调⽤ INT 指令触发
  • 硬中断：硬件通过中断控制器触发
• DMA：（Direct Memory Access）

3.设备驱动程序

以为了屏蔽「设备控制器」的差异，引⼊了设备驱动程序。属于操作系统部分。

设备驱动程序初始化的时候，要先注册⼀个该设备的中断处理函数。

4.通用块层

对于块设备，为了减少不同块设备的差异带来的影响，Linux 通过⼀个统⼀的通⽤块层，来管理不同的块设备。

• 作用：

  • 向上为⽂件系统和应⽤程序，提供访问块设备的标准接⼝，向下把各种不同的磁盘设备抽象为统⼀的块设备，并在内核层⾯提供⼀个框架来管理这些设备的驱动程序；
  • 给⽂件系统和应⽤程序发来的 I/O 请求，进行 I/O 调度。

• Linux I/O调度算法：

  • 没有调度算法：虚拟机常用。
  • 先入先出调度算法：顾名思义。
  • 完全公平调度算法：按照时间片均匀分配（大多数系统用）。
  • 优先级调度算法：优先级高的I/O请求先发生（桌面环境、多媒体应用）。
  • 最终期限调度算法：分别为读、写请求创建了不同的 I/O 队列，并确保达到最终期限的请求被优先处理。

5.储存系统I/O软件分层

• 储存系统I/O：
  • ⽂件系统层：包括虚拟⽂件系统和其他⽂件系统的具体实现，它向上为应⽤程序统⼀提供了标准的⽂件访问接⼝，向下会通过通⽤块层来存储和管理磁盘数据。
  • 通用块层：包括块设备的 I/O 队列和 I/O 调度器。
  • 设备层：包括硬件设备、设备控制器和驱动程序。

6.键盘敲入字母时，期间发生了什么？

1. 键盘控制器就会产⽣扫描码数据，并将其缓冲在键盘控制器的寄存器中，紧接着键盘控制器通过总线给 CPU 发送中断请求。
2. CPU 收到中断请求后，操作系统会保存被中断进程的 CPU 上下⽂，然后调⽤键盘的中断处理程序。
3. 键盘的中断处理程序是在键盘驱动程序初始化时注册的，键盘中断处理函数的功能就是从键盘控制器的寄存器的缓冲区读取扫描码，再根据扫描码找到⽤户在键盘输⼊的字符。然后把扫描码翻译为对应字符。
4. 得到了显示字符的 ASCII 码后，就会把 ASCII 码放到「读缓冲区队列」。
5. 显示设备的驱动程序会定时从「读缓冲区队列」读取数据放到「写缓冲区队列」，最后把「写缓冲区队列」的数据逐个写⼊到显示设备的控制器的寄存器中的数据缓冲区，最后将这些数据显示在屏幕⾥。
6. 显示出结果后，恢复被中断进程的上下文。

七、网络系统与I/O多路复用

计网部分略。

1.Linux接收/发送网络包的流程

文字表述详情见 图解系统P364。
– TODO –

2.I/O工作方式

（1）DMA技术

若没有DMA（Direct Memory Access），整个输出传输的过程都需要CPU亲自参与。如下图所示：

DMA相当于一个中介，在进⾏ I/O 设备和内存的数据传输的时候，数据搬运的⼯作全部交给 DMA 控制器。

1. 用户进程调用read方法，向操作系统发出I/O请求，请求读取数据到自己的内存缓冲区，进程进入阻塞状态。
2. 操作系统收到请求后，进⼀步将 I/O 请求发送 DMA，然后让 CPU 执⾏其他任务；
3. DMA 进⼀步将 I/O 请求发送给磁盘；
4. 磁盘收到 DMA 的 I/O 请求，把数据从磁盘读取到磁盘控制器的缓冲区中，当磁盘控制器的缓冲区被读满后，向 DMA 发起中断信号，告知⾃⼰缓冲区已满；
5. DMA 收到磁盘的信号，将磁盘控制器缓冲区中的数据拷⻉到内核缓冲区中；
6. 当 DMA 读取了⾜够多的数据，就会发送中断信号给 CPU；
7. CPU 收到 DMA 的信号，将数据从内核拷⻉到⽤户空间，系统调⽤返回；

（2）传统文件传输

传统 I/O 的工作方式是，数据读取和写⼊是从⽤户空间到内核空间来回复制。

发⽣了 4 次⽤户态与内核态的上下⽂切换、4次数据拷贝。

（3）优化文件传输

• 内存映射
  read() 系统调⽤的过程中会把内核缓冲区的数据拷⻉到⽤户的缓冲区⾥，于是为了减少这⼀步开销，我们可以⽤ mmap() 替换 read() 系统调⽤函数。
  
  发⽣了 4 次⽤户态与内核态的上下⽂切换、3次数据拷贝。

• sendfile
  个专⻔发送⽂件的系统调⽤函数，可以直接把内核缓冲区⾥的数据拷⻉到 socket 缓冲区⾥，不再拷⻉到⽤户态。
  
  发⽣了 2 次⽤户态与内核态的上下⽂切换、3次数据拷贝。

（4）零拷贝实现

• 支持SG-DMA的网卡sendfile
  进⼀步减少通过 CPU 把内核缓冲区⾥的数据拷⻉到 socket 缓冲区的过程。
  
  发⽣了 2 次⽤户态与内核态的上下⽂切换、23次数据拷贝。

这就是所谓的**零拷⻉（Zero-copy）**技术，因为我们没有在内存层⾯去拷⻉数据，也就是说全程没有通过 CPU 来搬运数据，所有的数据都是通过 DMA 来进⾏传输的。

（5）PageCache 磁盘⾼速缓存作用

PageCache： 来缓存最近被访问的数据，当空间不⾜时淘汰最久未被访问的缓存。此外，PageCache 使⽤了「预读功能」，会额外读取一些指令要求之外的信息。

• 不适用大文件
  • 在传输⼤⽂件（GB 级别的⽂件）的时候，PageCache 会不起作⽤，那就⽩⽩浪费DMA 多做的⼀次数据拷⻉，造成性能的降低，即使使⽤了 PageCache 的零拷⻉也会损失性能。
  • PageCache 中的⼤⽂件数据，由于没有享受到缓存带来的好处，但却耗费 DMA 多拷⻉到 PageCache ⼀次；

（6）大文件传输

不采用PageCache和零拷贝技术，而是使用异步I/O（也是直接I/O，适用于高并发）。

• 过程

  • 前半部分，内核向磁盘发起读请求，但是可以不等待数据就位就可以返回，于是进程此时可以处理其他任务；
  • 后半部分，当内核将磁盘中的数据拷⻉到进程缓冲区后，进程将接收到内核的通知，再去处理数据；

• 异步I/O+直接I/O适用场景

  • 大文件传输
  • 应用程序已经实现了磁盘数据缓存

• 异步I/O+直接I/O失去的内核优化

  • 内核对I/O请求在PageCache中的合并
  • 内核对I/O请求的预读

3.I/O多路复用

（1）Socket模型

略，参考上文关于Socket的介绍和 图解网络P386。

Socket结构里有：发送队列和接收队列，都是一个个sk_buff结构体。可以表示应用层、运输层、网络层、网络接口层的包，如下图所示。

（2）C10K问题

那如果服务器的内存只有 2 GB，⽹卡是千兆的，能⽀持并发 1 万请求吗？

• 多进程模型：应对少量客户端，太多顶不住。
  

• 多线程模型：频繁创建销毁线程，开销很大。可以采用线程池的方法解决。但一万个线程也很难顶。
  
  线程池：就是提前创建若⼲个线程，这样当由新连接建⽴时，将这个已连接的 Socket 放⼊到⼀个队列⾥，然后线程池⾥的线程负责从队列中取出已连接 Socket 进程处理。

• I/O多路复用
  它允许单个进程/线程同时处理多个I/O流，进程/线程可以通过⼀个系统调⽤函数从内核中获取多个事件。

  • select：
    • 将已连接的Socket都放到一个文件描述符集合（位图），然后调用select函数将文件描述符集合拷贝到内核中。
    • 遍历检查是否有事件发生，检测到后再拷贝回用户态。
    • 再次遍历检查。
    • 仅支持水平触发
  • poll
    • 采用动态数组结构，其他与select一致。
    • 比select可承载的文件描述符数量大。
  • epoll
    • 在内核使用红黑树跟踪进程所有待检测的文件描述符。
    • 把需要监控的Socket加入到内核红黑树。
    • 维护一个链表来记录就绪事件，进复制有事件的文件描述符到用户态。
    • 没有文件描述符数量限制（相比select/poll）。
    • 支持边缘触发

• 触发方式

  • 水平触发：当被监控的 Socket 上有可读事件发⽣时，服务器端不断地从epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束。
  • 边缘触发：当被监控的 Socket 描述符上有可读事件发⽣时，服务器端从epoll_wait 中苏醒⼀次（不会再次苏醒，除非有新数据到来），不论数据有没有被read读取。

边缘触发一般和非阻塞I/O搭配使用，如果使用阻塞I/O，当数据到达并且程序被唤醒去读取数据时，如果没有一次性读完所有数据，内核不会再次发送通知，这可能导致数据丢失。而非阻塞I/O允许程序在读取操作返回EAGAIN或EWOULDBLOCK错误后继续尝试读取，直到所有数据都被读取完毕。

select等I/O多路复用时，最好也搭配非阻塞I/O一起使用，防止出错（多路复用API不一定可读可写，使用阻塞I/O调用read/write时可能发生程序阻塞）。

4.高性能网络模式

（1）Reactor

Reactor模式是⾮阻塞同步⽹络模式，感知的是就绪可读写事件。在每次感知到有事件发⽣后，就需要应⽤进程主动进行系统调用。

单Reactor 单进程/线程

Reactor 对象的作⽤是监听和分发事件；
Acceptor 对象的作⽤是获取连接；
Handler 对象的作⽤是处理业务；

• 方案：

  • Reactor 对象通过 select 监听事件；
  • Reactor 对象收到事件后通过dispatch分发；
  • 如果是建立链接事件，交由Acceptor对象，它会通过accept方法获取链接，并创建一个Handler对象处理后续响应。
  • 如果不是建立链接时间，交由Handler对象处理响应。
  • Handler对象通过read->业务处理->send完成业务流程。

• 优点

  • 无需考虑进程间通信
  • 不用担心多进程竞争
  • 适用于业务处理非常快速的场景

• 缺点

  • 只有一个进程，无法利用多喝CPU的性能，
  • Handler对象在业务处理时，无法处理其他事件，如果业务处理耗时长，会造成响应延迟。
  • 不适用于计算密集型的场景。

单Reactor 多进程/线程

• 方案：

  • Reactor 对象通过 select 监听事件；
  • Reactor 对象收到事件后通过dispatch分发；
  • 如果是建立链接事件，交由Acceptor对象，它会通过accept方法获取链接，并创建一个Handler对象处理后续响应。
  • 如果不是建立链接时间，交由Handler对象处理响应。
  • Handler对象不再负责业务处理，只负责数据收发。
  • Handler对象将数据交由子线程进行业务处理。

• 优点

  • 充分利用多核CPU的能力

• 缺点

  • 存在多线程竞争问题
  • 多进程要比多线程复杂更多

多Reactor 单进程/线程

与单Reactor 单进程/线程相比没有任何优势，因此没有应用。

多Reactor 多进程/线程

• 方案：

  • MainReactor 对象通过 select 监听连接建立事件；
  • 收到事件交由Acceptor对象，通过accept方法获取链接，将新的连接分配给子进程；
  • 子线程的SubReactor 对象将被分配的连接加入 select 监听，并创建一个Handler对象；
  • 如果有新的事件发生，SubReactor 对象交由对应Handler对象处理响应。
  • Handler对象通过read->业务处理->send完成业务流程。

• 优点

  • 主线程和子线程分工明确。
  • 主线程和子线程交互简单。
  • 实现要比单Reactor多线程要简单得多。

（2）Proactor

Proactor模式是异步网络模式， 感知的是已完成的读写事件。在发起异步读写请求时，需要传⼊数据缓冲区的地址（⽤来存放结果数据）等信息，⼯作全程由操作系统来做。

• 方案：
  • Proactor Initiator 负责创建 Proactor 和 Handler 对象，并将 Proactor 和 Handler 都通过Asynchronous Operation Processor 注册到内核；
  • Asynchronous Operation Processor 负责处理注册请求，并处理 I/O 操作；
  • Asynchronous Operation Processor 完成 I/O 操作后通知 Proactor；
  • Proactor 根据不同的事件类型回调不同的 Handler 进⾏业务处理；
  • Handler 完成业务处理；

八、Linux指令

1.网络性能指标

–TODO–
等我学完项目第四章再补充

（1）性能指标

带宽、时延、吞吐率、PPS（包/秒）
网络可用性、并发连接数、丢包率、重传率

（2）网络配置

（3）Socket信息

（4）网络吞吐率和PPS

（5）连通性和延迟

2.日志分析