Linux内核设计精髓

置顶 读书记录
Created At :
Views 👀 :
  1. 进程线程概念与管理
    1. 相关概念
    2. 进程的创建
      1. fork创建进程
      2. 创建线程
      3. 进程终结
    3. 进程调度
      1. Linux调度器
      2. 睡眠和唤醒
      3. 抢占和上下文切换
      4. 实时调度策略
      5. 绑定处理器内核和主动让出
    4. 进程调度算法
    5. 同步
      1. 死锁
      2. 哲学家就餐问题
      3. Linux提供的锁
      4. 生产者消费者
      5. 读者写者问题
  2. 分布式
  3. 内存管理和虚拟内存
    1. 页面置换算法

如果你去直接搜索书名的话，应该是搜不到的。这里是两本书《Linux内核设计与实现》和《操作系统-精髓与设计原理》的总结内容😅

进程线程概念与管理

相关概念

进程：是正在执行的程序代码的事实结果。是程序和相关资源的总称（不只有text代码段，还有诸如打开的文件、内存映射的内存地址空间和全局变量的数据段等等）

线程：线程是进程中活动的对象，每个线程都有独立的计数器、进程栈和一组进程寄存器。而在Linux中线程是一种特殊的进程。

进程描述符： 进程的列表被存放在任务队列中（一个双向循环链表，节点是struct task_struct其中包含一个进程的所有信息）。其中包含着诸如打开的文件、进程的地址空间、挂起的信号、进程的状态和其他信息。

上面的进程描述符结构被包裹在struct thread_info结构体中，这个结构体位于进程内核栈的栈底

  • pid（进程标识值）：存放在上面的进程描述符中。由pid最大值限制的进程最大数量是可以调整的，但是这个值越大就代表上面的双向循环链表越长，遍历一圈的时间也就越长 。

  • 进程状态

    • TASK_RUNNING（运行）
    • TASK_INTERRUPTIBLE（可中断）睡眠状态
    • TASK_UNINTERRUPTIBLE（不可中断）即使接收到信号也不会被唤醒和准备投入运行
    • __TASK_TRACED（被其他进程跟踪，如ptrace gdb）
    • __TASK_STOPPED（停止）

  • 进程上下文：当程序调用了系统调用或者触发异常就陷入了内核空间

  • 进程家族树：所有的进程都是PID为1的init进程后代。每个进程都有parent指针指向父进程的task_struct和一个叫做children的子进程链表所以Linux中可以通过一个进程遍历到所有其他进程

用户级线程的优点

  • 线程切换不需要内核态的权限，避免了两次状态转换。
  • 可以自己定制线程调度算法
  • 用户级线程可以运行在任何操作系统上

用户级线程的缺点

  • 用户级线程一旦阻塞其他同进程的用户级线程也会阻塞
  • 无法利用系统多处理器的优点

进程的创建

通过fork系统调用可以拷贝当前进程创建一个子进程，此时父子进程的区别仅仅是PID和PPID和某些资源和统计量。

写时拷贝：Linux通过写时拷贝减少或者免除拷贝，fork之后并不是复制所有的进程地址空间，而是使用原来进程的地址空间。只有当需要写入的时候，才会进行拷贝，在此之前是通过只读方式共享。

  • 当fork之后立即exec的时候就完全没有必要复制父进程的地址空间。
  • fork的实际开销就是复制父进程的页表以及创建唯一的进程描述符

fork创建进程

pid_t fork()
{
    clone();
}
int clone(参数)
{
    do_fork();
}
UNKNOW do_fork()
{
    copy_process();

    // 唤醒新创建的子进程开始运行
}
UNKNOW copy_process()
{
    dup_task_struct(); // 为新进程创建内核栈，thread_info和task_struct结构体。此时父子进程的进程描述符完全相同。

    检查是否有空闲的pid来分配

    将自已与父进程区别开，进程描述符中的小部分信息被清除，主要是统计信息

    子进程被设置为不可中断状态，防止被投入运行

    copy_flags(); // 更新flag成员
    alloc_pid(); // 为新进程分配pid

    根据传递给clone的参数 这里会拷贝或者共享打开的文件，文件系统信息，信号处理函数，进程地址空间等等 
        一般同一进程的线程会共享这些内容，而不同的进程之前则是不同的需要拷贝

    return 指向子进程的指针
}

创建线程

在Linux中可以说没有线程这个独立的概念。有的是创建进程时根据传入clone的参数决定哪些资源共享、哪些资源拷贝。

pid_t fork()
{
    clone(SIGCHLD, 0);
}
int pthread_create()
{
    clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0);
}
  • CLONE_VM 父子进程共享地址空间
  • CLONE_FS 父子进程共享文件系统信息
  • CLONE_FILES 父子进程共享打开的文件.如果不指定会进行拷贝使得引用计数+1，而共享的话则不会+1
  • CLONE_SIGHAND 父子进程共享信号处理函数和被阻断的信号

进程终结

虽然让人伤感😥，但进程终归要终结的。当一个进程终结的时候，内核必须释放其占有的资源，并将这一不幸通知父进程。

不管是显示或者隐式调用exit，或者收到不能处理也不能忽视的信号时可能被动终结。最终都会调用do_exit函数

UNKNOW do_exit()
{
    将task_struct中的标志成员设置为PF_EXITING();

    del_timer_sync(); // 删除定时器

    if (开启记账)
    {
        进行记账();
    }

    exit_mm(); // 释放进程占用的mm_struct 如果这个地址空间没有被共享 则彻底释放

    sem_exit(); // 取消IPC信号的排队等待

    exit_files(); // 递减文件描述符和引用计数
    exit_fs(); // 递减文件系统的引用计数

    设置task_struct的exit_code成员中的任务退出代码(代码是exit传入的值);

    exit_notify(); // 向父进程发送信息，为本进程的子进程寻找养父 然后将自己设置成EXIT_ZOMBIE

    schedule(); // 本进程已经终结，调用此函数切换到新的线程。因为EXIT_ZOMBIE的进程永远不会再次被调用，do_exit永远不会返回了😇
}

至此此进程没有了地址空间，仅存的是内核栈、thread_info和task_struct结构。为的是向父进程提供信息，可以通过wait系列函数收回仅存的这些内容

进程调度

从处理器的角度来看，它只是从程序计数器指向的地址中取得指令然后执行，并忠实的执行这些指令。而程序计数器在系统运行过程中，可能时不时地从指向一个进程的代码指向另一个进程的代码，从而实现进程的切换。

进程必须能够被操作系统跟踪，也就是说，一个进程必须包含一些必要的信息（进程控制块、进程的状态和在内存中的地址），使得操作系统能够感知到进程的存在，从而控制它的执行。

系统必须设计某种队列暂时执行和暂时无法执行的进程。进程要么因为时间片用完而被中断，然后加入等待队列。要么执行完毕离开系统。或者阻塞等这时候操作系统从队列中找到新的进程来运行。

PSW（程序状态字）中存在当前执行模式的标记（用户级 内核级）。当出现中断的时候，需要从用户级向内核级切换这时候这个标记就从用户级切换为内核级这样就能够执行内核空间的代码。当从内核返回的时候标记从内核级切换为用户级这样返回用户空间。

何时进行进程切换？

当操作系统从当前运行的进程处得到了控制权的时候。

  • 中断（时间片用尽会发生时间中断）
  • 异常
  • 系统调用（Linux中系统调用就是中断的方式）

模式切换？

从用户态临时转向内核态，仅仅是保存和恢复进程上下文。并不会导致当前进程被切换

进程切换步骤

  1. 保存当前进程上下文（程序计数器和其他寄存器）
  2. 改变当前进程的进程控制块内容（进程状态变更）
  3. 将当前进程控制块移动到其他队列（就绪队列，某个事件的阻塞队列等）
  4. 选择一个合适的进程
  5. 更新被选择进程的进程控制块（设置为运行态）

Linux提供了抢占式的任务调度和实时的任务调度策略

主动让出 VER1.0 EX协程

  • 抢占式调度器

    • 时间片耗尽或者执行完毕让出VER2.0
    • O（1）对于交互式进程很不友好 VER3.0
    • 完全平衡调度算法，简称CFS VER4.0

  • 实时任务调度器

进程可以分为I/O消耗型和处理器消耗型。GUI程序的交互一般属于前者。这里就存在了两种矛盾

  1. 处理器消耗型 希望使用更大的时间片，减少进程切换多做计算
  2. GUI等交互程序 希望快速响应，这就意味着需要更小的时间片，保证快速响应

调度策略在这两个矛盾间寻找平衡点。

我们希望能够快速的响应交互程序。所以最终将分配时间片改成了分配CPU使用比。加假如系统中仅存两个优先级相同的进程（交互进程和计算进程），那么调度器会给这两个进程各自分配50%的使用占比。然而对于交互进程这些时间远远足够，每次分配后都无法用尽，对于计算进程却能每次用尽分配的占比。这样CFS将会在交互进程需要运行时，毫不犹豫立刻抢占CPU给交互进程（这是因为 CPU承若给他50%的使用，然而他却没有用完。）这样就能使得交互进程快速响应以及计算进程占用更多的CPU。

Linux调度器

Linux调度器

Linux调度器是以模块的方式提供，不同的继承可以选择不同的调度器。这种模块化的结构称为调度器类。每个调度器都有自己的优先级，基础的调度器会按照优先级遍历这些调度器。而每个调度器都会提供经过他自己的算法决定下一个应该运行的进程。

Linux 调度器入口

每个调度器有自己的入口函数

之后schedule函数调用优先级最高的一个调度器，问这个调度器谁是下一个该运行的进程。

睡眠和唤醒

为了防止调度器选出一个本不想运行的进程，调度器会从可执行红黑树中寻找下一个该运行的进程

睡眠

进程在将自己标记为休眠时，可以从可执行红黑树中将自己移除，放入等待队列。然后通过schedule选出下一个可执行的进程

void 睡眠()
{
    DEFINE_WAIT(); // 在等待队列创建一个位置

    add_wait_queue(); // 将自己加入等待队列中

    while(条件不满足)
    {
        prepare_to_wait(); // 将自己变更为TASK_INTERRUPTIBLE或者TASK_UNINTERRUPTIBLE

        if (信号到来); // TASK_INTERRUPTIBLE下会被信号唤醒，而不是条件满足
        {
            处理信号();
        }
        if (条件满足)
        {
            break; // 条件满足时退出循环
        }
        else
        {
            schedule(); // 让出CPU 睡眠
        }
    }

    将自己变更为TASK_RUNNING;

    finish_wait(); // 将自己移出等待队列
}

唤醒

将自己标记为可执行状态，然后从等待队列移动回可执行红黑树

void wake_up()
{
    唤醒等待队列上所有进程;

    将进程设置为TASK_RUNNING;

    将自己放入红黑树;
}

抢占和上下文切换

上下文切换

从一个可执行进程切换到另一个可执行进程。通过context_switch负责处理。当进程A被选定要投入运行的时候通过schedule函数就能调用前面的函数，实现上下文切换。

void schedule()
{
    context_switch();
}
void context_switch()
{
    switch_mm(); // 将虚拟内存从上一个进程切换到新的进程

    switch_to(); // 负责处理器状态的切换。包括保存、恢复进程和栈的信息。
}

内核必须知道什么时候调用schedule。

当每个进程应该被抢占时，会被设置need_resched标志。这个标志告诉内核有其他进程应该被运行了，要尽快调动调度程序

用户抢占

从内核返回用户空间的时候，如果need_resched被设置，将会导致schedule被调用 内核会选取一个更加合适的进程投入运行

用户抢占的发生时机

  • 从系统调用返回用户空间
  • 从中断处理程序返回用户空间

内核抢占

当从中断返回的时候如果当前没有持有锁（通过thread_info中的preempt_count计数器，加锁时+1，解锁时-1 为0时说明没有锁），而且need_resched被设置说明存在更加需要执行的进程可以被安全抢占

如果内核中的进程被阻塞了，或者显示调用了schedule内核抢占就会显示的发生（根本不需要额外的逻辑保证可以安全的抢占，因为如果代码显示的调用了schedule说明他清楚自己是可以安全的被抢占的）

实时调度策略

SCHED_FIFO

不使用时间片，处于此状态的进程会比任何SCHED_NORMAL级的进程都先得到调度。他会一直执行下去直到自己受到阻塞或者主动让出，如果存在多个此策略的进程则会轮流执行。

SCHED_RR

带时间片的SCHED_FIFO

绑定处理器内核和主动让出

进程调度算法

先来先服务（FCFS）

最短进程优先（SPN）

最短剩余时间优先（SRT）

时间片轮换法(以此为基础的升级版 动态时间片)

CFS（公平调度）

sched_setaffinity

sched_getaffinity

sched_yield 主动让出

同步

在单一处理器的时候，只有在中断发生的时候，或者内核明确地提出重新调度、执行另外一个任务的时候，才会出现数据的并发访问。

竞争条件和同步

如果两个执行线程在同一个临界区中执行，而且会因为执行顺序的不同影响最终结果，这就是程序存在的BUG。将这种情况称为竞争条件。这种条件出现的可能很低，所以非常难于排查。避免并发和防止竞争条件称为同步。

需要辨认出真正需要共享的资源和相应的临界区，才是难的地方

进程交互的三种类型

  • 无交互 存在对系统资源的竞争
    • 竞争可能导致饥饿
    • 竞争可能导致死锁
  • 间接交互 知道其他进程的存在，但是不和其直接交互。存在共享协作要求
  • 直接交互 知道其他进程的存在，通过PID直接进行交互。同样存在通信协作要求

造成并发执行的原因

  • 中断 （几乎能在任意时刻发生，然后就会打断当前执行的代码）
  • 软中断和tasklet
  • 内核抢占
  • 睡眠以及用户空间的同步

锁

锁的使用是程序员自愿的，并不是系统强制的，是程序员可以选择的手段。

锁是采用原子操作实现的

锁之间的区别

当锁已经其他线程获取后导致的不可用时的行为表现。

  • 有的锁在争用时简单的忙等待。（自旋锁）
  • 有的锁则会睡眠直到锁可用。（读写锁 信号量 互斥体 条件变量 这四个的具体行为各不相同）

死锁

  • 自死锁 当一个线程尝试去获取已经持有的锁的时候
  • ABBA死锁 线程1拿着A锁获取B锁 线程2拿着B锁获取A锁
  • 除了资源争用还有互相等待消息也会导致死锁（B等待A的消息，但是A的消息丢失或者没有发送）

死锁解决办法

  • 按顺序加锁
  • 防止发生饥饿
  • 不要重复请求一个锁
  • 设计应该力求简单

死锁的解决

  • 使用相同的顺序锁定两个互斥元，可以使用std::lock同时锁定所有需要的互斥元

  • 持有锁的时候尽量不要调用其他部分的函数，防止其他函数中也存在锁相关内容

  • 使用层次锁

  • 死锁预防
    • 一次性申请所有资源（解决占有且等待）
      • 未得到资源的可能需要长时间等待，已得到资源的则会长时间不使用
      • 可能不能明确知道需要分配多少资源
    • 抢占 （解决不可剥夺）内存可以采用此方案， 因为可以将内存数据保存到硬盘中
      • 进程占有资源后，在后续执行中申请所有需要的资源，资源得不到满足的情况下释放已经占有的资源
      • 通过进程优先级决定高优先级进程可以抢占低优先级进程资源
    • 资源有序分配 （解决循环等待）
      • 有序资源分配，对资源进行编码申请编码R资源后，后续申请只能申请编码大于R的资源
  • 死锁避免
    • 拒绝创建进程，所有进程需要的资源总量小于可使用的资源总量
    • 拒绝分配资源（银行家算法）使得系统一直在稳定状态
  • 死锁检测
    • 周期性检查（将现有的剩余资源进行分配，如果某个进程拿到了所有需要的资源则结束并返回所有占有的资源，当能够结束的进程都结束后依然存在进程无法得到足够的资源说明剩余进程之间存在死锁）

死锁预防

  • 优点
    • 排除了出现死锁的可能
  • 缺点
    • 资源使用率低

死锁避免

  • 优点
    • 相对于死锁检测，不需要抢占资源或者回滚进程
    • 相对于死锁预防更加灵活
    • 虽然可能出现死锁，但是尽力不让死锁出现
  • 缺点
    • 需要知道进程的最大资源使用
    • 进程之间是独立的
    • 可分配资源数是固定的
    • 进程结束必须释放所有资源

死锁检测

原子性和顺序性

前者通过原子操作实现，后者通过屏障实现。

哲学家就餐问题

Linux提供的锁

自旋锁

  • 短时间锁定的锁

信号量

  • 用于长时间被锁定的锁
  • 锁的时间较短的话，可能会导致因为睡眠锁导致的用户态到内核态的切换和内核态到用户态的切换，以及相关队列的维护是得不偿失的

生产者消费者

生产者

在生产的时候不仅需要写缓冲区，还要读缓冲区确认缓冲区状态和将要写的位置。

消费者

不仅需要读缓冲区，还需要将已读的从缓冲区移出

PV操作 通过计数值作为资源的数量

条件变量 生产后signal消费者

读者写者问题

读者优先

写者优先

读写锁

分布式

中间件： 在上层应用程序和下层的通信软件及操作系统之间使用标准的编程接口和协议。这种标准化的接口和协议称为中间件

中间件的基本目的：使得位于客户端的应用程序或用户能够访问服务器上的各种服务，而无需考虑服务器之间的差距。

现在存在两种不同的数据库，有一个程序想要从两个数据库中读取数据。如果通过中间件，程序不需要考虑两个数据库之间的差异，而是直接根据标准读取即可

可以通过添加一个中间层解决大多数问题。

分布式消息传递

  • 使用消息
  • 以消息为基础，称为远程过程调用

内存管理和虚拟内存

内存保护需要通过硬件方式实现，因为操作系统无法预测程序所有的内存访问。

分页使用拼接的方式 得到真实物理地址 因为每个页面大小相同

分段则使用相加的方式 因为每个段的大小不同

换出一块将要被使用的内存块，内存块马上又要被使用将会导致频繁的换出和换入造成抖动

页表（分页式和段页式）段表（段式）的表中 每条项目存在P（存在标记）M（修改标记）

减少页的大小

  • 页内碎片减少
  • 进程使用的页的数量增加，页表增大
  • 页的数量多，每个页面都是最近访问的页面，这样缺页率较低

增加页的大小

  • 页的数量小且单个页大，每个页包含的内容将与任何一个最近访问的内容越来越远，局部性原理将会削弱，缺页率会增加

读取策略

请求分页：开始执行时会发生大量的缺页中断

预分页：预先加载一些页

页面置换算法

最佳页面置换算法（Opt）

换出未来不会使用的页面

最近最少使用（LRU）

置换出最长时间没有被访问的页面

先进先出（FIFO）

时钟策略

第一次被加载到内存时的使用为是1，当需要置换的时候指针扫描一圈，如果遇到使用位是1的将其变为0，遇到是0的则选中这个页面进行置换

增加了修改位后的时钟策略

首先选取未被使用未被修改的作为置换页（扫描过程不修改使用位）

其次选取未被使用但修改过的作为置换页（扫描过程会将使用位从1改为0）

©2016-2023 lsmg

Built with Hexo and 3-hexo theme