理解程序运行时的内存布局0：知识铺垫之多任务、协同式与抢占式、时间片、任务优先级

计算机内存[1]（Computer Memory），是指计算机的临时存储区，其保存着中央处理单元（CPU）所要用的数据和指令，其中的指令，指令通常指处理器单独的某种操作[2]，由处理器指令集定义（Instruction set architecture，通常指令集包括四类指令：算术、逻辑、数据移动、控制流）。
在程序运行前，程序会从硬盘上加载并贮存到内存中，这样 CPU 即可直接访问程序。其中，内存是不可或缺的模块。操作系统，以及各式各样的软件中都以不同的形式存在在内存中，即独立的段区域（segment of memory），而且这些区段也被划分为数据段与程序段两种（未来，如果有机会，我们会详细讲的，这次没有）。

不过，在讲内存前，先来看一下什么是 多任务操作系统（Multitasking OS），因为这个概念与后文的内存有关，且涉及多任务时，不同进程的虚拟内存地址空间等概念，好了，我们开始吧。

1. 知识铺垫：多任务操作系统

多任务操作系统，是指这个操作系统或者其扩展功能，支持自动地在多个任务之间共享（share）可用的处理器时间[3]。

这篇文章[6]对单任务与多任务例子写得很生动，单核 CPU 在一个时刻只能被一个进程占用，这里进程可以看作一个单任务。多任务操作系统中的“多任务”，实际为一个宏观概念，如唱歌、吃饭，可以吃一口饭的同时唱一句歌。在某个时间段内，进行了吃饭和唱歌的任务了，相对于 CPU ，一段时间内既处理任务 A 又做任务 B，由于 CPU 工作速度快，用户感觉是同一时间在做多个任务，即多任务操作系统。

1.1 多任务的两种实现：协同式、抢占式

多任务操作系统又分为多种实现方式，根据多任务共享 CPU 时间的方式，被分为两种：

协同式多任务处理（Cooperative Multitasking，或者是另一种类别 Non-Preemptive）：任务使用 CPU 直到它主动放弃 CPU 权限，主动放弃如通过使用系统调用 yields （ yield 实现了当前进程所占用内核空间的短暂让步，即当前进程短暂地释放其占用的 CPU 资源，给其它进程执行的机会，短暂让步之后，当前进程会继续执行[5]）或 exits，即获取（这里没说是主动获取还是被动获取，不过我猜测既然有其他进程主动放弃，交给谁在这种 Cooperative 的模式下就定了，联想到的一个例子是生产者-消费者这种需要多模块协作的场景，就是被动获取）或主动放弃 CPU 使用权。协作式多任务系统例如 pre-X MacOS 或 Windows 3.x，都是很早期的系统。 在一些单语言的协同多任务处理系统中（注：这里说的“单语言”怎么理解，不清楚，根据与小浣熊交流，这里 Oberon 和 Ruby 各运行一个任务，那就是 Single language 了），如 Oberon 或 Ruby （Oberon 是一种通用目的的编程语言，其由 Modula-2 改进而来。其改进的主要特点在对于类型扩展的概念——允许基于已经存在类型或基础类型，来扩展新数据类型[4])，这里似乎说了和没说一样），编译器或解释器会自动周期性地确认代码持有控制权（periodically yield control），它保证程序在类似 DoS 的操作系统下跑运行多线程，这段优点啰嗦，你需要知道的重点是编译器或解释器也会确认代码持有的控制权；
抢占式多任务处理（Preemptive Multitasking）：在抢占多任务处理系统中，有些任务启动和结束，并非主动地获取或放弃 CPU ，而是操作系统由于一个或多个原因造成，如任务消耗了被给予的 CPU 时间，或存在一个更高优先级的任务需要 CPU ，这种切换是强制的（根据后文你会知道，调度和操作系统对不同调度单位如线程、进程的优先级和时间片有关，“强制”和中断有关）。

对于二者实现方式的对比，这里举一个例子[6]：Win95 前的多任务系统，采用的是协同式，现在更多是抢占式，后者当新进程开始时，在其时间片（time slice）内，CPU 使用权是在该进程手中，当时间片结束，系统要收回 CPU 的使用权做下一轮分配，即抢占式会根据任务优先级来分配了（1.3 会提到这个任务调度）。

1.2 协同式与抢占式的比较

再回到对于抢占式与协同式调度策略，二者可以进一步比较，这份 Slide Process and Thread Scheduling[7] 也有描述：

图1 Preemptive vs. Non-preemptive Scheduling[7]

现在主流操作系统，都是抢占式如 Linux 、 Windows 等。抢占式多任务处理系统，还可以进一步细分：抢占任务型如 Linux 、抢占内核型如 AmigaOS 。

抢占式和协同式的最大差异，根据上面 Slides 这两个比较的第二点：Canlead to imporve response time、 Unimportantprocesses can block important ones indefinitley，即分别是二者的优劣，即协同式会导致某个不重要但耗时的进程 block。这里有个例子[6]，据说很久以前，协同式多任务系统的用户常会因开启多个程序，某程序出现“无法响应”而导致系统崩溃的——这就是因为该程序在某个部位长时间占用了 CPU 的结果。为了使各程序能够通畅的执行，“抢占式多任务”应运而生。

这里有一篇文章[31])对二者做了对比，表格罗列的更细致一些：

表1 Preemptive Vs Non-Preemptive Scheduling[31])

其实，判断是 Preemptive 还是 Non-preemptive 只需要记住一点，非抢占式（Non-preemptive Scheduling）会导调度会让某个执行的进程持有 CPU 资源到其终止或者，这是判断依据[31])：

Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state. No process is interrupted until it is completed, and after that processor switches to another process.

看上面写的，不只是 gets terminated 还有 pushed to the waiting state：

第一种我理解是完成或者是异常终止掉了；
而第二种的 waiting state ，根据这篇博客讲到的 sleep 与 wait [37]函数的区别苞米地里捉小鸡的博客-CSDN博客c++ wait https://blog.csdn.net/weixin\_42709632/article/details/105175396[)：
sleep 方法（后文关于线程部分也会见到），即让当前正在执行的线程在指定的时间内暂停执行，进入阻塞状态， sleep 过程既可以让其他同优先级或者高优先级的线程得到执行的机会，也可以让低优先级的线程得到执行机会。此外，该方法使用过程中必须 try-catch-finally捕获异常，因为有可能被其他对象调用 `sleep 对象的 interupt() 产生 Interrupted Exception 异常进入 TERMINATED 状态；
wait() 方法，当线程调用该方法后，则会进入等待池，即等待阻塞，并让出 CPU 资源。

1.3 概念：时间片、任务优先级

因为1.1 提到了时间片（time slice，可能也不是这么写，但都是时间片）和任务优先级，先说这个时间片。

1.3.1 概念：时间片

时间片来自多线程执行（这里任务对应一个线程），当多任务在 CPU 上运行时，看起来是多个任务同时运行，实际是 CPU 在不同程序上给予固定的时间，这个时间称为 time slice 。其实，根据前文也能理解。

从 Round Robin 优先级调度方法来看，每个 process 会得到一个小的 CPU 时间单位即 time quantum ，通常是 10~100 ms ，当这个小的时间单位流逝，当前进程会被抢占，并被添加到一个 ready queue 的队尾（这个后续我感觉可以写一下，什么是 Ready Queue，在调度策略中 Ready Queue 是哪个步骤，这个问题我会在后续进程切换工作这里稍微提到）。总之，这里的 time quantum 也可以理解是时间片。

1.3.2 概念：任务优先级

这里以 Windows 的优先级名词 ProcessPriorityClass 与 ThreadPriorityLevel 讲起，因为在查阅这个概念的过程中，翻到有一篇讲在 Win 上通过 Get-Process 命令在 PowerShell 中获取 Threads 信息的文章，可以看到如 TotolProcessorTime 、 ThreadState 、 WaitReason 等性能相关字段[8]，其中便有一个优先级字段 PriorityLevel ，这个字段的单位是 Threads 即线程的：

C:\> (Get-Process -Id 10080).Threads | Get-Member

TypeName: System.Diagnostics.ProcessThread
Name                       MemberType Definition
---- ---------- ----------
PriorityLevel Property System.Diagnostics.ThreadPriorityLevel PriorityLevel {get;set;}
PrivilegedProcessorTime Property timespan PrivilegedProcessorTime {get;}
ProcessorAffinity Property System.IntPtr ProcessorAffinity {set;}
ThreadState Property System.Diagnostics.ThreadState ThreadState {get;}
TotalProcessorTime Property timespan TotalProcessorTime {get;}
UserProcessorTime Property timespan UserProcessorTime {get;}
WaitReason Property System.Diagnostics.ThreadWaitReason WaitReason {get;}

其实说到这里，我就比较好奇 Windows 这个 PriorityLevel 优先级是怎么排序的，Microsoft Docs 在 System.Diagnostices 的 ThreadPriorityLevel 页面有提到这个 ThreadPriorityLevel 是一个枚举类，其表示指定线程的优先级。Windows 在优先级方面的文档我看了一圈，其相关字段很多给我的感觉是混乱。不过我这里总结三点：

每个线程都有一个基本优先级：由线程的优先级值（我这里），与其进程的优先级类确定。操作系统对所有可执行线程的基本优先级别排序，来确定哪个线程获取处理器下一个时间；
当线程调度优先级，值更大表示优先级越高。其值介于 1~15 表示 dynamic priority ， 16~31 表示 real-time priority ，而 0 则表示 zero-page thread 的优先级，其被保留用于将内存页面归零防止出现需要0 page fault的问题[29]（这里对 0 page fault没看懂【TODO】），且低于所有其他所有优先级。
线程的优先级值，每个线程都有一个 base priority 和 current priority ：
base priority：继承来自 thread's process。举例来说，Kernel-mode 下的 driver 代码运行在用户线程的 context 里，其 base priority 就是当前 thread's user process 的 priority ，priority 源于 I/O 操作的请求；而另外一个同样的 Kernel-mode 下的 driver 代码，运行在 system worker thread 如 work item 其 base priority 则是为其队列提供服务的 system worker threads ；
current priority：在某个时间上的当前的 thread priority，是一个动态的。

系统为了去调整完成任务的吞吐量，会去不断调整线程优先级，即调度策略。

图 Basic Concept && Scheduling Criteria | Process and Thread Scheduling[7]

虽然 Windows 的文档没有讲清楚其调度策略，但是通常调度设计中，都包含如下几个概念（根据上图提到的）：

最大化 multiprogramming 时的 CPU 的利用率。multiprogramming ，是指内存中同时存放几个互相独立的程序，在管理程序控制下可以穿插运行，表现为这些程序同时处于开始和结束之间的状态。burst 无论是 I/O、还是 CPU，我认为1个或者多个burst对应给一个进程的 quantum；
CPU - I/O Burst Cycle ：进程执行过程中包含的 CPU 执行 cycle 数和 I/O wait cycle 数。对于 Burst 的概念，根据上下文的内容推断，可理解成单纯的操作；
CPU burst distribution：根据上面概念理解就是 CPU 执行任务的时间分布。跟上面图2，我想对 IO 的假设应该是两点：单个IO操作时间很多，但是单个操作时间很短，就像图1右边表示的那样，很多CPU burst之间有 I/O burst，可能也表示 CPU 执行会因为数据还没有被读进 cache，需要等待一段时间，所以无法做连续的 CPU burst。
I/O bound 表示：存在很多既多又短的 CPU Burst 。综合 I/O 与 CPU 的时间比例，从 I/O 角度来说，就是 I/O 速度太慢但 CPU 算的快，即我们常说的 I/O 两小时计算5分钟；
CPU bound表示：存在很少且执行时间很长的 CPU Bursts。

虽然 PPT 这里显示的调度粒度不是线程还是进程，但调度粒度也可以是线程，操作系统的 Context switch 是以进程为单位，也有线程粒度的上下文切换。

调度也是有 Scheduling Criteria 的，通常包含如下参数，还是上面 PPT 的第 3 张，我补充些其他内容[30]：

CPU utilization：范围通常是 0~100%，现实中通常介于 40~90% ；
Throughput：单位时间内完成的 Processes 数量；
Turnaround time：从进程提交到完成的完整时间，包括了等待从内存中取数、 waiting in the ready queue、executing on the CPU, and dong I/O；
Waiting time：waiting in the ready queue；
Response time：从请求提交到第一次响应产生的时间。

进程（线程）调度算法也是基于这些参数作为优化目标来设计的，比方最小化 Response time / Turnaround time、最大化 CPU utilization / Throughput 等。比方 First-Come First-Served 策略，来了就服务，采用 FIFO 数据结构且是串行方式，虽然策略简单，但并不能做到多进程在时间片上的共享，我认为应该属于典型的非抢占式策略。

也有考虑 waiting time 的 Shortest-Job First 策略，SJF 是 Priority Scheduling 的一种特殊情况，Priority Scheduling 可以是 Preemptive 或 no-Preemptive

怎么看是抢占式或者非抢占式？所有 Scheduling algorithm 都可以是这两种形式吗？对于这个疑问，我在前文提到了：非抢占式（Non-preemptive Scheduling）会导调度会让某个执行的进程持有 CPU 资源到其终止或者）。

但是 Priority Scheduling 也存在 blocking 、starvation。对于二者的理解：

blocking：我觉得这个是对于提交的进程任务队列来说的，阻塞了，导致的原因可能不一定是对正在运行的进程来说，当前 CPU 计算慢或计算任务多，也有可能是 I/O 资源，如目前处于 I/O burst 执行过程有 load/store ；
starvation：有个人说是阻塞的加强版，指后到的进程，虽然来得晚但优先级高，所以先到的低优先级进程还要等着。对排在后面的 low priority process 来说，就是“饿了”。

为此要解决低优先级无限等待的问题就是 aging， aging 处于等待状态的 process 每隔一段时间就会将自己的 priority 提升，以此有机会执行。

扯远了，再次回到 SJF 和 Priority Scheduling 。Shortest-Job First 即 Priority 就是考虑每个进程的需要的时间 CPU burst，将执行进程的顺序调整为按照他们所需时间升序排列，这样 average waiting time 是最小的。SJF 既可以用于 Preemptive Scheduling 也可以用于 Non-Preemptive Scheduling。

如果是后者就是考虑 Short-Job 对 CPU burst 排序串行执行就完事了，但如果是 Preemptive Scheduling，需要考虑每个进程的 arrive time，请看下面这个例子：

图 SJF Preemptive Scheduling[30]

这时，对于 Average waiting time 的计算就要考虑 arrival time（注：指任务到达时间，跟调度算法无关），P1虽然 burst time 是8 比较长，但是它先到，其他P2/P3/P4还没到：

也就是P1先执行到第二个即P2到的时候，即甘特图到1的时候，P1和P2再比较，发现虽然P1执行了1，但此时P1 的 Burst Time更新为7，比P2大，所以P1暂停，由P2执行；
再到 ArrivalTime=2时，P3到了，此时P1/P2/P3的Burst Time 更新，此时：P1: 7，P2: 3，P3: 9，那依旧是P2执行；
ArrivalTime=3时，P4到了，此时P3:2，P1: 7，P3: 9，P4: 5，因为后面没有别的进程，且，P3是burst最短的，那么P3就会执行完；
甘特图 Time=5 时，P3执行完，还剩下P4: 5，P1: 7，P3: 9，此时最短的是P4，那么P4执行到 Time=10 结束；
甘特图 Time=10 时，P4结束，还剩下：P1: 7，P3: 9，类似前面的操作，P1执行完然后是P3，全部任务完成时 Time=26。

其中，有 2 个关键的地方在于：

还没执行，怎么知道每个 Burst time 的长短从而排序呢，这个估计 Burst time 的过程是否耗时。这里是 SJF 地缺点，在执行前 Burst Time 的长短很难到，即使做到了也是估计的，不过下面给出了估计 Next CPU Burst 的思考；
在 ArrivalTime=2 时，P1 切换到 P2 ，需要做哪些工作，设计线程上下文切换，主要是寄存器值地读写（后面我们会详细说）。

1.3.2.1 估计Next CPU Burst

这个估计的基本思想：根据前面已完成的 CPU bursts 时间长度，使用指数平均（exponential averaging，看到这里不禁想到凸优化里的 Exponential Moving Average）来估计，并估计出最小的那个作为下一个要执行的进程。

图 determining Length of Next CPU Burst[31])

根据上图在第3页即 Prediction of the Length of the Next CPU Burst 页，可以看到当不同时刻对应的 CPU Burst，如 t0 时 CPU Burst 为6, t1时为4, t2时为6，结合第4页 Example of Exponential Averaging 得到估计用的公式。在下面，我会展开并推导：基于预测的下一个时间的CPU Burst，依赖上一个真实与历史估计值的这一想法，有如下表示：

有时间 t_{n}时的 CPU Burst ，是实际值；
要预测下一个时间的CPU Burst，注意是预测值，即 tp_{n+1} 为 n+1 时刻预测的 CPU Burst；
其中 alpha为系数，范围： 0<=alpha<=1，这个系数通常设置为 0.5；
那么有： tp_{n+1}=alpha*t_{n}+(1-alpha)*tp_{n}

抢占式版本（Preemptive）的这个 SJF 也称为：shortest-remaining-time-first。进一步分析公式，对系数 alpha 来说：

alpha = 0
tp_{n+1} = tp__{n}，即历史估计 Burst time 不参与估计
alpha = 1
即 tp_{n+1} = t_{n}，估计的完全基于历史真实的
但若将这个公式扩展，可以得到：
tp_{n+1} = alpha*t_{n} + (1-alpha) * tp\_{n}，展开tp_{n}
tp_{n+1} = alpha * t_{n} + (1-alpha) * [alpha * t_{n-1} + (1-alpha) * tp\_{n-1}]，展开tp\_{n-1}
tp_{n+1} = alpha * t_{n} + (1-alpha) * {alpha * t_{n-1} + (1-alpha) * [alpha * t_{n-2} + (1-alpha) * tp\_{n-2}]}，后续继续展开tp_{n-2}
最终得到：
tp_{n+1} = alpha * t_{n} + (1-alpha) * alpha * t_{n-1} + (1-alpha)^2 * alpha * t_{n-2} + (1-alpha)^3 * alpha * t_{n-3} + ... + (1-alpha)^(n) * alpha * t_{n-n} + (1-alpha)^(n+1) * tp_{n-n}
可以抽象为：
tp_{n+1} = alpha * t_{n} + ... + (1-alpha)^{j} * alpha * t_{n-j} + ... + (1-alpha)^(n+1) * tp_{0}
由于 0<alpha<1，且 0<1-alpha<1，则公式中越靠后，系数越小。
推到这里，感觉推导的一圈没啥用，还是得看这个原始的公式： tp_{n+1}=alpha*t_{n}+(1-alpha)*tp_{n}，实际应该也是根据这个公式来算。

但是根据公式，我有两个疑问：

怎么guess tp_0的时间？无法预测，没有历史数据，有冷启动问题？首次时间：有两个解决方案，一是根据观察过去的所有任务统计的实际 CPU Burst 时间，给出中位数或者众数作为首次时间，解决冷启动问题；二是更准确地，或许也可以根据过去执行过的任务的静态属性建立与实际执行时间的关系，比方假设有线性相关性建立模型，然后根据当前 Job 的静态属性和刚建立的模型，来估计 Job 的 CPU Burst time；
Prediction of the Length of the Next CPU Burst 这一页的 guess 时间通过公式 tp_{n+1}=alpha*t_{n}+(1-alpha)*tp_{n}推出来不符合？我认为是图上写的错了。这个 PPT 也是有 UIC 配文字的电子版的，这其中对 Guess 和 CPU Burst 没解释。

参考

Computer memory - Simple English Wikipedia, the free encyclopedia https://simple.wikipedia.org/wiki/Computer_memory
Instruction set - Simple English Wikipedia, the free encyclopedia https://simple.wikipedia.org/wiki/Instruction_set
Understanding Memory Layout. The memory refers to the computer… | by Shohei Yokoyama | Medium https://medium.com/@shoheiyok...
Microsoft Word - Oberon07.Report.doc (ethz.ch) http://people.inf.ethz.ch/wir...
Linux内核 yield()|酷客网 https://www.coolcou.com/linux...
多任务 - nianjun - 博客园 (cnblogs.com) https://www.cnblogs.com/sengn...
Microsoft PowerPoint - scheduling.ppt [Compatibility Mode] (ucdavis.edu) https://web.cs.ucdavis.edu/~p...
Getting the CPU time and status of threads in a process with PowerShell - TheShellNut (mathieubuisson.github.io) https://mathieubuisson.github...
Linux写时拷贝技术(copy-on-write) - as_ - 博客园 (cnblogs.com) https://www.cnblogs.com/biyey...
Virtual address spaces - Windows drivers | Microsoft Docs https://docs.microsoft.com/en...
Memory Management : Paging. Paging is a method of writing and… | by Esmery Corniel | Medium https://medium.com/@esmerycor... physical part of the memory containing a,facilitates more efficient and faster use of storage.
CS 4410 Operating System, Memory: Paging | cornell.edu http://www.cs.cornell.edu/cou...
Introduction to the page file - Windows Client Management | Microsoft Docs https://docs.microsoft.com/en...
memory - Does Linux have a page file? - Stack Overflow https://stackoverflow.com/que...
What Is the Windows Page File, and Should You Disable It? (howtogeek.com) https://www.howtogeek.com/126...
Converting Virtual Addresses to Physical Addresses - Windows drivers | Microsoft Docs https://docs.microsoft.com/en...
Disable Windows Pagefile and Hibernation To Free Up Space - TechCult https://techcult.com/disable-...
How to disable and re-enable hibernation - Windows Client | Microsoft Docs https://docs.microsoft.com/en...
intro-to-memory-management (elinux.org) https://elinux.org/images/b/b...\_Linux.pdf
[教學] 關機、待命、睡眠、休眠和交互式睡眠的分別 « FoolEgg.com https://www.foolegg.com/what-...
Understanding-linux-virtual-memory.pdf (cmu.edu) http://linuxclass.heinz.cmu.e...
What are types of kernel objects? (fyicenter.com) http://dev.fyicenter.com/Inte...
A Process s Kernel Object Handle Table | Programming Applications for Microsoft Windows (Microsoft Programming Series) (flylib.com) https://flylib.com/books/en/4...
Memory Limits for Windows and Windows Server Releases - Win32 apps | Microsoft Docs https://docs.microsoft.com/en...
How PAE X86 Works: System Reliability | Microsoft Docs https://docs.microsoft.com/en...(v=ws.10)
High Non-Paged Pool Memory Usage (Leak) in Windows | Windows OS Hub (woshub.com) http://woshub.com/huge-memory...
Memory Management — The Linux Kernel documentation (linux-kernel-labs.github.io) https://linux-kernel-labs.git...
What is a Hardware Abstraction Layer (HAL)? - Definition from Techopedia https://www.techopedia.com/de...
Unit OS4: Windows OS Thread Scheduling https://www.cs.sjtu.edu.cn/~kzhu/cs490/8/8_Scheduling.pdf
unit2 Process Scheduling and Synchronization.pdf http://www.notesengine.com/main/notes/eee/7sem/os/notes/unit2.pdf
Preemptive and Non-Preemptive Scheduling (tutorialspoint.com) https://www.tutorialspoint.com/preemptive-and-non-preemptive-scheduling
Chapter 5: CPU Scheduling | 2.01 (cmu.edu) https://www.andrew.cmu.edu/course/14-712-s20/applications/ln/14712-l6.pdf
Operating Systems: CPU Scheduling https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6CPUScheduling.html
c++11 yield函数的使用 - 小怪兽&奥特曼 - 博客园 https://www.cnblogs.com/jinxiang1224/p/8468164.html
C++ yield()与sleepfor()weixin34029680的博客-CSDN博客 https://blog.csdn.net/weixin34029680/article/details/91871163
如何编写 C++ 20 协程(Coroutines)【图文】程序喵大人51CTO博客 https://blog.51cto.com/u_12444109/3031169
C/C++ Sleep()函数和wait()函数的区别苞米地里捉小鸡的博客-CSDN博客c++ wait https://blog.csdn.net/weixin_42709632/article/details/105175396