派大星 · 1月13日

理解程序运行时的内存布局1:知识铺垫之进程/线程切换、纤程

上次我们讲了《多任务、协同式与抢占式、时间片以及任务优先级》的概念,最后讲到了时间片以及任务优先级的概念,任务优先级就牵扯到调度算法——排序。但当时并没有讲到排序的对象,也就是线程或进程。本文将从进程切换开始,主要涉及线程、进程的相关概念等。讲这些的概念也是因为和运行时内存布局有关。

注:本文大量内容参考自陈海波老师的《现代操作系统:原理与实现》,不注明原创。这篇文章一个月前就写好了,但迟迟懒得发。

1 进程切换工作

注:小标题的编号是因为将原本的文章拆开了。之前内容见《多任务、协同式与抢占式、时间片以及任务优先级》

首先,也需要科普几个概念,前文提到了 Ready Queue,其实 Ready 是一个状态,对进程来说,其有以下状态:

  1. 新生:进程刚创建时的状态;
  2. 就绪:可执行,等待被调度器允许执行的状态,Ready Queue;
  3. 运行:进程正在执行的状态;
  4. 阻塞:等待如 I/O 请求等事件而无法执行的状态;
  5. 终止:进程执行结束的状态。
    image.png
    进程调度机制负责以上状态的切换,同时根据职责不同分为长、中、短期的调度:
  • 长期调度(long-term scheduling/job scheduling):粗粒度决定一个新进程是否纳入调度管理。进程总数量的限流阀门——限制被短期调度的进程数量。根据 CPU、 I/O 利用率合适的进程交给短期调度;
  • 短期调度(short-term scheduling/CPU scheduling):触发最频繁,细粒度。别名是 CPU Scheduling,主要负责进程在上述 5 个状态中的 3 个状态,即就绪、运行、阻塞状态的切换。一般触发短期调度的事件包括:进程的创建、执行结束、硬件终端(尤其是时钟中断)、系统调用等;
  • 中期调度(medium-term scheduling):相对频繁,辅助换页机制,也可以说是换页机制的一部分(换页机制我们后面会讲)。没啥别名,不过和内存关系密切。举个例子,如若现有系统中的进程已占大量内存,中期调度会挂起短期调度的部分进程,从而降低内存占用。这个过程会做如下几个事情:
  • 工作1:选择要被挂起的短期调度进程,如频繁发生缺页、长时间无响应的进程。标志着不再被调度执行,如上图进程从阻塞状态到挂起阻塞状态
  • 工作2:换页机制,会倾向于(那就不是100%一定,应该说大概率会)选择被挂起的进程所使用的内存替换入磁盘;
  • 工作3:其实到工作2完毕就结束了,同时也会为该进程激活做准备,即中期调度也会监控当前的内存使用,并在适当的时机(我猜是内存紧张状态得到缓解,且CPU和I/O等指标达到调度要求)将此前挂起的进程,被激活进入挂起就绪状态。

在内核中,每个进程都有一个名为进程控制块(Process Control Block,PCB)的数据结构保存其相关状态,状态有:进程标识符(PID)、进程状态、虚拟内存状态、打开文件等。
image.png
而进程 A 由于中断(外设触发,设备通知CPU)或者信号(也称为软件中断),切换到进程 B时,操作系统需要通过进程的上下文切换机制,来完成切换。进程的上下文,是指进程运行时的寄存器信息,用于保存和恢复一个进程在处理器上的状态。进程的上下文切换,则会将前一个进程的寄存器状态(上下文)保存到进程控制块(PCB)中,然后将下一个进程先前保存的状态(PCB)写入寄存器,从而切换到下一个进程执行。
image.png
早期操作系统中,进程是系统调度的基本单位,但更轻量的运行时抽象——线程的提出,调度和上下文切换的基本单位也从进程变为线程。引入原因主要两点:

  1. 进程创建的开销大:有大量拷贝,创建独立的地址空间、载入数据和代码段、初始化堆等步骤;
  2. 进程在数据共享和同步成本高:一般只能通过共享虚拟内存页(粗粒度)、进程间通信的两种方式。一个进程有独立的虚拟内存空间。同一个进程下的不同线程共享。相比进程间的共享和同步数据开销低。

而线程共享进程的虚拟地址空间(见上图),同一进程内的多个线程又有各自的运行时状态(即上下文,或者说是寄存器信息,也有对应的 TCB,即线程控制块)。

需要线程切换(上下文)切换是因为,单个 CPU 核心只有一个程序计数器(Program Counter,用于存放下一条指令所在单元的地址的地方,可以理解为程序是指令数组,而 PC 是遍历该数组的索引变量)。而同一个时间单个 CPU 核心仅能执行一个线程,为了确保所有线程都能看似被同步地执行,就需要切换线程。

而切换线程主要是切换两个线程内各自的状态信息,状态信息指的是当前处理器中大部分寄存器的值,以 AArch64 为例,包括三类:

  1. 程序计数器(PC),存储 CPU 当前所执行指令地地址。也有说 PC 是特殊寄存器的;
  2. 通用寄存器,存储 CPU 当前正在处理地数据。X0 ~ X30 共 31 个通用寄存器,其中 X29 用作栈指针(Frame Pointer,FP,用于保护)寄存器;
  3. 特殊寄存器,存储 CPU 当前地一些硬件状态和配置,如TTBR0EL1和TTBR1EL1都是页表地址、SPEL0线程运行时的栈指针等、SPSREL1线程执行时的CPU状态包括条件码/中断状态/是否处于调试状态等。

我们这里对线程上下文的切换以 ChCore 系统(该系统是《现代操作系统:原理与实验》中的实验操作系统)举例,ChCore采用的是一对一模型的多线程模型,即一个用户态线程映射给单一的内核态线程,来实现用户态线程与内核态线程的协作。线程有保存自己信息的结构即线程控制块(Thread Control Block,TCB),内核态和用户态线程保存有各自的 TCB。

  • 内核态 TCB 的结构:包括了线程运行状态、内存映射、标识符信息等;
  • 用户态 TCB 的结构:由线程库决定,如 Linux 平台上的 pthread ,pthread结构体就是用户态的 TCB,可以认为是对内核态 TCB 的扩展。
    image.png
    总之,TCB 中都预留了存储线程上下文(即上图保存的各种寄存器的值)的空间。书中写道:“线程的内核栈在 TCB 下面,线程进入内核后使用”,那么这里的 TCB 是内核态线程的,当线程进入内核态后,会自动将栈指针从 SPEL0 切换为 SPEL1 (EL是Exception Level,即异常级别,也是操作系统中的特权级,EL1是位于操作系统即内核态,当然也有EL0即内核态,还有EL2和EL3等,具体见特权级)。

说完了线程切换的主要对象,那么再说说线程的切换地过程,还是书上的内容,虽然仍旧是 ChCore 操作系统,即使不同操作系统、不同体系结构下虽然方法多种多样,但在基本思想和方式上是相近的。我简单提炼一下,上下文间切换的核心操作是在内核态完成,其切换过程包含三个阶段

  1. 进入内核态与上下文保存:通常由时钟中断除触发,只要系统调度器设定好时间,时间到了就会触发硬件中断(注:这里再回顾一下“轮询”与“中断”,二者方向不同,“中断”是由设备发出通知CPU,而“轮询”是CPU发通知给设备。操作系统可以为不同设备配置不同的中断处理函数),CPU硬件会自动执行一些列操作,保存好线程的上下文,操作系统为发生时钟中断所对应的处理函数配置相应代码,即在内核态用内核栈对用户态线程的上下文进行保存,其中没有对页表相关寄存器进行保存(在下一步);
  2. 页表与内核栈的切换:进入内核态有了高特权级(EL0,即操作系统所在的特权级,即内核态),才能有切换页表的能力。切换过程涉及内核线程之间的内核栈切换:
  3. switch context:切换页表和找到目标线程的内核栈。由于进程虚拟地址空间分为内核部分和应用部分,分别对应 aarch64 在地址翻译过程会使用的两个页表基地址寄存器 TTBR1EL1 和 TTBR0EL1,由于每个线程映射的内核部分是相同的,所以只需要更新应用部分的页表基地址寄存器 TTBR0EL1 为目标线程的应用空间页表基地址,此外该函数还会找到目标线程的 TCB 的起始地址(我猜测应该还是内核态线程的 TCB 因为还没切换出来),并将该地址作为目标线程的内核栈顶;
  4. eret_to_thread:通过 mov 指令,切换到目标线程的内核栈(再次看上图),由于所有用户态线程在进入内核态前都将线程的上下文都已保存在各自线程的 TCB 中了,因此切换到另一个线程的内核栈后,处理器当前的内核栈顶即为目标线程的上下文。因此,可以将 mov 视为两个线程执行的分界点
  5. 上下文恢复与返回用户态:刚刚在上一步,erettothread 已经切换到目标线程的内核栈,且栈顶就是目标线程的上下文。现在,内核使用 exceptionenter 的反向操作 exceptionexit (看函数名就是退出特权级,应该就就是从 Exception Level 1 的内核态回到 Exception Level 0 的用户态),操作完毕就将目标线程的上下文从内核栈的栈顶依次弹出,恢复到了寄存器中,并最终返回到用户态。后续继续目标线程的执行即可。
    image.png
    其实从粗粒度到细粒度,提到了进程、线程,他们都有其上下文和切换。现在主流操作系统也有纤程(Fiber)这个概念出现的背景是由于应用程序的复杂,用户态线几乎完全程受到操作系统调度器的管理,但应用对网络通信、计算、读写的要求只有自身更了解,换句话说,只有自己才能做出更适合自己的线程语义和执行状态,即调度决策。此外,用户态线程比内核态线程更加轻量、切换和创建开销相比内核态线程要低

以上两个原因,操作系统开始提供对用户态线程,即纤程(Fiber)的支持,在该支持下,用户态进程和内核态线程的映射服务关系也从一对一向多对一发展。

下面从一个例子讲讲纤程的优点。生产者消费者模型,包含两部分,即生产者,负责“生产”数据,消费者,负责“消费”数据,即消费者依赖生产者“生产”的数据进行“消费”

现假设一个进程有两个线程,分别为生产者线程和消费者线程,两个线程在同一个虚拟地址空间,生产者将生产的数据写入空间,消费者使用。假设该计算机只有一个处理器,那么从生产者生产到消费者处理数据需要至少经历一次线程的上下文切换。但实际中,计算机不知道二者这样的关系,操作系统本身又有自己的调度策略:即生产者生产完紧接着按理说可以让消费者来消费,但是由于:

  1. 操作系统有自己的调度策略的选择;
  2. 线程切换有上下文相关寄存器的读写开销,会导致消费者经历不少延迟才会拿到数据。

为了消除这两点带来的开销,可以使用纤程。利用纤程,可以对类似生产消费者这种有依赖关系的多模块协作场景予以高效率支持。生产者完成生产直接交由消费者,我这里没给出代码,不过代码中的实现是完成消费的函数内的最后一句——会切换上下文到生产者纤程,反之也是如此。即纤程切换都在用户态,不需要操作系统调度。

对于纤程的上下文切换触发机制是软件触发,与线程、进程切换的通过中断方式抢占 CPU 并进行切换有本质不同,后者切换是强制的,内核态线程的触发机制是硬件时钟中断(当达到由 OS 调度器设置好的时间,就会发出一个硬件中断,在中断触发后,CPU 硬件根据设置的中断触发函数自动进行操作,略),即前文说的抢占式多任务处理(Preemptive Multitasking)模式

而纤程提供 yield 接口,让当前纤程会暂时放弃 CPU 允许其他纤程调度,这种调度方式称为合作式多任务处理(Cooperative Multitasking,前文一开始的时候也提到了),需要多个纤程协作完成调度。除操作系统外,编程语言如 Go 、Ruby、C++ 也支持纤程,一般称为“协程”,该特性常被用于上下文频繁切换的应用场景如 Web 服务等。在 C++ 中有 3 种方法常见的方法让当前线程主动让出 CPU

  1. std::this_thread::yield :C++11提供的方法,其实现基于 Linux 系统调用方法 sched_yield,作用是让当前线程放弃执行即主动放弃 CPU,从而让其他线程有机会运行,当前线程在后续调度周期里再参与 CPU 调度。有一个应用场景[34]是你的线程需要等待某个操作完成,如果用一个循环不断判断这个操作是否完成,就会使得这个线程占满 CPU 时间,这会造成资源浪费。但是如果你判断一次操作是否完成,如果没有完成就调用 yield 交出时间片,过一会儿再来判断是否完成,这样这个线程占用CPU时间会大大减少。但这个方法有个缺点,再次执行原始线程的中间时间不固定,依赖操作系统 CPU 调度策略[35]weixin34029680的博客-CSDN博客 https://blog.csdn.net/weixin_34029680/article/details/91871163,以 CPU 调度时间片为单位,在不同操作系统/调度策略下,表现可能不同;
  2. std::sleep_for():线程调用该方法同样会让出 CPU 并休眠设定的时间。优点相比 yield是时间可控;
  3. Coroutines:C++20 提供的协程,协程是一个可以挂起(suspend)和恢复(resume)的函数[36])。你可以暂停协程的执行,去做其他事情,然后在适当的时候恢复到暂停的位置继续执行。但是其中的实现很奇怪,写起来比较繁琐,这里略。

本小节主要关注了线程、进程、纤程的概念以及进程的切换,其实对于线程与进程的关系而言。线程的创建接口pthread_create,就是调用进程创建的接口clone实现的。clone是精确控制创建进程的接口。

换句话说,线程只不过是特殊(资源受限)的进程,clone可以精密地控制资源来创建,新的“进程”在代码库,堆,数据,代码等内存部分与父进程共享,这个“新进程”。

2 多任务的进程、进程地址空间

下面,我们紧接着再来看看进程地址空间。这篇文章[6]对任务与线程和进程、进程地址空间的概念举例也很清楚,我把其中一些概念摘出来:

  • 前面提到了多任务,对于任务的定义其实在单任务操作系统时期,写好的程序(program),既可表示静态的软件代码——由一组指令组合的实体,也可表示其动态的执行过程。一个程序即一个任务,多任务操作系统出现后,特定任务是被时间片(time slice)间断执行,此时任务被细分,出现进程(process)的概念——系统执行程序时,加载到内存地数据单元;
  • 进程可以被再次细分为称为线程(thread)地更小任务,可把线程视作轻量级地进程。进程可以看成是 N 个线程构成地集合,若 N=1 ,为单线程进程;当 N>1 ,为多线程进程;这里根据《现代操作系统:原理与实现》再补充一点,关于线程与进程的不同:
  • 进程是资源隔离单位,一个进程可以有多个线程,这些线程可以在不同 CPU 上并行执行;
  • 线程是执行单位,是调度器的调度对象,在 Linux 等操作系统中通常用任务(Task)来描述线程。
  • 虽线程可看作轻量级进程,但二者最主要区别——是在内存中,进程与进程之间是分开的,拥有各自地址空间;而线程间是共享地址空间:下面描述从高级语言地角度,进程 A 与进程 B 都有变量 x ,但二者空间是各自地,毫不相干,因为保存在各自进程地地址空间。但若在一个进程里,某个线程 C 和 D 同时对程序地变量 y 做写操作,就会错误,因为两个线程共享同一块内存地址空间;
  • 虽然进程间地址空间是分开的,保证安全性,但资源利用率却低。想象一个场景,在进程 A 中有一占用较大空间的变量 z ,现在需要创建新进程 B ,按照不同的进程分配不同的地址空间,那么进程 B 也将会有在其进程上独立的变量 z 。这样,就导致会存在多份 z 变量的拷贝,分布在不同进程的各自地址空间中,而且还有个问题,拷贝 z 变量比较慢时间开销大。鉴于此,Linux 系统采用了一种叫做“Copy-on-Write”(CoW)技术,该技术的做法顾名思义,资源的复制只有在需要写入的时候才进行。比方新的进程 F 在创建时,在新分配到的内存地址空间中并没有实实在在的将变量 z 写入,而只是写入了指向进程 B 所属得到内存地址空间中的变量 z 的指针。当新进程要读取变量 z 时,直接到进程 A 所属的内存地址空间读就是了;若进程 B 要对变量 z 进行写操作,此时方才将进程 A 所属内存地址空间的变量 z 实实在在的复制到进程 B 所属的地址空间。这就是“Copy on Write”技术,不仅 Linux 进程有用到,默写 C++ IDE 也支持对 string 类型的 COW 技术[9]。

参考

  1. Computer memory - Simple English Wikipedia, the free encyclopedia https://simple.wikipedia.org/wiki/Computer_memory
  2. Instruction set - Simple English Wikipedia, the free encyclopedia https://simple.wikipedia.org/wiki/Instruction_set
  3. Understanding Memory Layout. The memory refers to the computer… | by Shohei Yokoyama | Medium https://medium.com/@shoheiyokoyama/understanding-memory-layout-4ef452c2e709
  4. Microsoft Word - Oberon07.Report.doc (ethz.ch) http://people.inf.ethz.ch/wirth/Oberon/Oberon07.Report.pdf
  5. Linux内核 yield()|酷客网 https://www.coolcou.com/linux-kernel/linux-process-scheduling-kernel-api/the-linux-kernel-yield.html
  6. 多任务 - nianjun - 博客园 (cnblogs.com) https://www.cnblogs.com/sengnj/p/3559835.html
  7. Microsoft PowerPoint - scheduling.ppt [Compatibility Mode] (ucdavis.edu) https://web.cs.ucdavis.edu/~pandey/Teaching/ECS150/Lects/05scheduling.pdf
  8. Getting the CPU time and status of threads in a process with PowerShell - TheShellNut (mathieubuisson.github.io) https://mathieubuisson.github.io/cpu-time-threads-status-powershell/
  9. Linux写时拷贝技术(copy-on-write) - as_ - 博客园 (cnblogs.com) https://www.cnblogs.com/biyeymyhjob/archive/2012/07/20/2601655.html
  10. Virtual address spaces - Windows drivers | Microsoft Docs https://docs.microsoft.com/en-us/windows-hardware/drivers/gettingstarted/virtual-address-spaces
  11. Memory Management : Paging. Paging is a method of writing and… | by Esmery Corniel | Medium https://medium.com/@esmerycornielle/memory-management-paging-43b85abe6d2f#:~:text=The physical part of the memory containing a,facilitates more efficient and faster use of storage.
  12. CS 4410 Operating System, Memory: Paging | cornell.edu http://www.cs.cornell.edu/courses/cs4410/2016su/slides/lecture11.pdf
  13. Introduction to the page file - Windows Client Management | Microsoft Docs https://docs.microsoft.com/en-us/windows/client-management/introduction-page-file
  14. memory - Does Linux have a page file? - Stack Overflow https://stackoverflow.com/questions/35054783/does-linux-have-a-page-file
  15. What Is the Windows Page File, and Should You Disable It? (howtogeek.com) https://www.howtogeek.com/126430/htg-explains-what-is-the-windows-page-file-and-should-you-disable-it/
  16. Converting Virtual Addresses to Physical Addresses - Windows drivers | Microsoft Docs https://docs.microsoft.com/en-us/windows-hardware/drivers/debugger/converting-virtual-addresses-to-physical-addresses
  17. Disable Windows Pagefile and Hibernation To Free Up Space - TechCult https://techcult.com/disable-windows-pagefile-and-hibernation-to-free-up-space/
  18. How to disable and re-enable hibernation - Windows Client | Microsoft Docs https://docs.microsoft.com/en-us/troubleshoot/windows-client/deployment/disable-and-re-enable-hibernation
  19. intro-to-memory-management (elinux.org) https://elinux.org/images/b/b0/IntroductiontoMemoryManagementin_Linux.pdf
  20. [教學] 關機、待命、睡眠、休眠和交互式睡眠的分別 « FoolEgg.com https://www.foolegg.com/what-are-the-differences-between-shut-down-standby-sleep-hibernate-and-hybrid-sleep/
  21. Understanding-linux-virtual-memory.pdf (cmu.edu) http://linuxclass.heinz.cmu.edu/doc/Open-Source-books/Understanding-linux-virtual-memory.pdf
  22. What are types of kernel objects? (fyicenter.com) http://dev.fyicenter.com/Interview-Questions/Windows/Whataretypesofkernelobjects.html
  23. A Process s Kernel Object Handle Table | Programming Applications for Microsoft Windows (Microsoft Programming Series) (flylib.com) https://flylib.com/books/en/4.419.1.29/1/
  24. Memory Limits for Windows and Windows Server Releases - Win32 apps | Microsoft Docs https://docs.microsoft.com/en-us/windows/win32/memory/memory-limits-for-windows-releases#memory-and-address-space-limits
  25. How PAE X86 Works: System Reliability | Microsoft Docs https://docs.microsoft.com/en-us/previous-versions/windows/it-pro/windows-server-2003/cc736309(v=ws.10)
  26. High Non-Paged Pool Memory Usage (Leak) in Windows | Windows OS Hub (woshub.com) http://woshub.com/huge-memory-usage-non-paged-pool-windows
  27. Memory Management — The Linux Kernel documentation (linux-kernel-labs.github.io) https://linux-kernel-labs.github.io/refs/heads/master/lectures/memory-management.html#physical-memory-management
  28. What is a Hardware Abstraction Layer (HAL)? - Definition from Techopedia https://www.techopedia.com/definition/4288/hardware-abstraction-layer-hal
  29. Unit OS4: Windows OS Thread Scheduling https://www.cs.sjtu.edu.cn/~kzhu/cs490/8/8_Scheduling.pdf
  30. unit2 Process Scheduling and Synchronization.pdf http://www.notesengine.com/main/notes/eee/7sem/os/notes/unit2.pdf
  31. Preemptive and Non-Preemptive Scheduling (tutorialspoint.com) https://www.tutorialspoint.com/preemptive-and-non-preemptive-scheduling
  32. Chapter 5: CPU Scheduling | 2.01 (cmu.edu) https://www.andrew.cmu.edu/course/14-712-s20/applications/ln/14712-l6.pdf
  33. Operating Systems: CPU Scheduling https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6CPUScheduling.html
  34. c++11 yield函数的使用 - 小怪兽&奥特曼 - 博客园 https://www.cnblogs.com/jinxiang1224/p/8468164.html
  35. C++ yield()与sleepfor()weixin34029680的博客-CSDN博客 https://blog.csdn.net/weixin34029680/article/details/91871163
  36. 如何编写 C++ 20 协程(Coroutines)【图文】程序喵大人51CTO博客 https://blog.51cto.com/u_12444109/3031169
  37. C/C++ Sleep()函数和wait()函数的区别苞米地里捉小鸡的博客-CSDN博客c++ wait https://blog.csdn.net/weixin_42709632/article/details/105175396
来源:NeuralTalk
作者:开心的派大星

往期回顾

本作品采用知识共享署名-相同方式共享 4.0 通用许可协议进行许可。
欢迎关注公众号,关注模型压缩、低比特量化、移动端推理加速优化、部署。
嵌入式AI.jpg
更多嵌入式AI相关技术干货请关注嵌入式AI专栏。
1 阅读 532
推荐阅读
0 条评论
关注数
14352
内容数
611
嵌入式端AI,包括AI算法在推理框架Tengine,MNN,NCNN,PaddlePaddle及相关芯片上的实现。欢迎加入微信交流群,微信号:aijishu20(备注:嵌入式)
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
Arm中国学堂公众号
关注Arm中国学堂
实时获取免费 Arm 教学资源信息
Arm中国招聘公众号
关注Arm中国招聘
实时获取 Arm 中国职位信息