操作系统梳理漫谈：虚拟化

主要参考书目：《操作系统导论》(Operating System Three Easy Pieces)

英文原版教材作者主页免费阅读：

https://pages.cs.wisc.edu/~remzi/OSTEP/

1.操作系统框架概述

一个程序运行的过程：

处理器从内存中获取一条指令 ➡️ 对其进行解码（弄清楚这是哪条指令） ➡️ 然后执行它（做它该做的事情）。➡️再获取下一条指令，以此类推知道程序最终完成。

为了让程序运行变得更容易（甚至是同时运行多个程序），允许程序共享内存，让程序能够与设备交互等等，我们便采用了一类称之为操作系统的软件（Operating System，OS）。

要做到这些事情，操作系统主要利用一种通用的技术，我们称之为虚拟化，即OS将物力资源(如处理器、内存、磁盘等)转换为更通用、更强大、更易于使用的虚拟形式，故我们也将OS称作虚拟机(virtual machine)。

为了让用户告诉OS做什么，从而利用虚拟机的功能，OS还会提供一系列借口（API）供你调用。典型的OS会提供几百个系统调用(system call)，让应用程序调用，以实现访问内存和设备、进行其它相关操作的等目的。由此，我们也常说OS为应用程序提供了一个标准库(standard library)。

最后，因为OS让应用程序运行(从而共享CPU)，让许多程序可以同时访问自己的指令和数据(从而共享内存)，让许多程序访问设备(从而共享磁盘等)，所以操作系统有时也被称为资源管理器(resource manager)。每个CPU、内存和磁盘都是系统的资源(resource)，因此操作系统扮演的主要角色就是管理(manage)这些资源。

1.1 虚拟化CPU

通俗易懂地理解：即使我们希望在一个单CPU上同时运行多个程序也可以做到，事实上这是操作系统在一些硬件帮助下提供的假象，即OS拥有非常多个CPU的假象，将单个CPU(或其中一小部分)转换为看似无限数量的CPU，从而让许多程序看似同时运行，这就是所谓的虚拟化CPU。至于是如何做到的，以及类似于两个程序在某个特定的时间都要运行该运行哪个这类问题，都属于操作系统的策略，是操作室同实现的基本机制问题，这些都会在后面详谈。

1.2 虚拟化内存 (virtualizing memory)

通俗化理解就是：好像每个正在运行的程序都有自己的私有内存，而不是与其他正在运行的程序共享相同的物理内存。（如我们或许可以实验发现两个同时运行的程序的操作对象打印出来的地址指向的是同一个地址，不过这一点在日常用的电脑上试不出来，要先禁用一下地址空间随机化。）

这就是操作系统虚拟化内存时发生的情况。每个进程访问自己的私有虚拟地址空间(virtual address space)，（有时候简称为地址空间），操作系统以某种方式再将其映射到机器的物理内存上。如此一来正在运行的内存饮用不会影响其他进程(或是OS本身)的地址空间。对于正在运行的程序，它似乎完全拥有自己的物理内存，但实际上物理内存是操作系统管理的共享资源。

1.3 并发

并发这个术语用来指代一些列的问题，这些问题在同时(并发地)处理很多事情时出现且必须解决。

不管是操作系统本身同时处理很多事情，还是现代多线程程序(multi- threaded)都存在这些问题。

1.4 操作系统的设计目标

提供高性能，我们的目标是最小化操作系统的开销。
隔离。我们希望应用程序之间，OS和应用程序之间都能提供保护，使一个应用程序的恶意或意外行为不至于损害其他程序，当然更不希望损害到OS本身。保护是操作系统基本原理之一的核心，也就是所谓的隔离。让进程彼此隔离是保护的关键，这也决定的OS必须执行的大部分任务。
可靠性。OS要能够不间断运行，否则它一失效，系统上运行的程序也就失效了。

进程与线程的联系与区别

进程

进程是程序的一次执行过程，是一个动态概念，

它是程序在执行过程中分配和管理资源的基本单位，每个进程都有一个自己的地址空间。

线程

线程是CPU调度和分配，执行的基本单位，它可以和同属于一个进程的其他线程共享这个进程所拥有的全部资源。

进程和线程的联系

线程是进程的一部分，且一个线程只属于一个进程；

而一个进程可以有多个线程，但至少有一个线程。

当我们未提及线程时的程序可以看作是单线程的，如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线(线程)共同完成的，线程是进程的一部分，所以线程也被称轻量级进程。

进程和线程的区别

1.根本区别

进程是OS资源分配的基本单位，

线程是任务调度和执行的基本单位。

2.在开销方面

每个进程有独立的代码和数据空间(上下文，context)，进程之间切换会有较大的开销；

而线程可以看作是轻量级的进程，同一个进程下的线程共享代码和数据空间，

不过**每个线程都有自己独立的运行栈和程序计数器(PC)**，线程之间切换的开销更小。

3.所处的环境

在一个OS中能同时运行多个进程，

而在同一个进程中有多个线程同时执行（通过CPU调度，在每个时间片只有一个线程执行）。

4.内存分配

当系统运行时，会为每个进程分配不同的内存空间，

而对线程而言，除了CPU外，系统不会为线程分配内存等资源，线程所使用的资源来来自其所属进程的资源，进程组之间只能共享资源。

为什么要设计线程

传统进程模型中，进程的内涵可以分为两方面：

调度执行的基本单位，每个进程有自己的运行状态，优先级，寄存器等等，是OS调度的基本单位；
资源所有权：包括程序、数据和文件等资源，一个进程拥有对这些资源的所有权，OS则提供保护功能，避免不同进程之间的资源冲突

既然是两个独立的功能，那自然可以将它们分离，这就出现了线程的概念，由此：

执行与调度的基本单位：线程
资源的所有权：进程

这样做的好处：

操作系统中有两个重要概念：并发和隔离

并发：是为了尽量让硬件利用率高，线程就是为了在系统层面做到并发，因为线程的上下文切换效率比进程上下文的切换高很多，这样可以提高并发率。

隔离：也是并发之后要解决的问题，计算机资源一般是共享的，隔离要能保障崩溃了的资源能够被回收，不影响其他代码的使用，所以OS只有线程而没有进程其实也是可以的，只是OS会经常崩溃罢了，OS刚发展时和这种情形很像，而进程则有自己独立的数据空间，进程之间互不影响，保证了对各进程的有效隔离。

故说，线程和并发有关，进程和隔离有关，线程基本是为了并发执行而引入的概念，进程相当于一堆线程加上执行过程申请的资源，一旦挂了这些资源都要能回收，不影响其他程序。

堆（Heap）和栈（Stack）的区别

1.申请方式

栈（Stack）：由系统分配

堆（Heap）：可以程序员手动申请任意大小的内存并释放

2.申请后系统的响应

栈：只要栈的剩余空间大于所申请空间系统就会为程序提供内存，否则会报异常提示栈溢出。

堆：OS内有记录空闲内存地址的空闲链表，当OS收到申请后会遍历该链表，寻找第一个空间大于所申请的空间的堆结点，然后将该结点从空闲节点链表中删除，并将该结点的空间分配给程序。对于大多数系统而言，会在这块内存空间的首地址处记录本次分配的大小，这样代码中的delete语句才能正确地释放本内存空间。

找到的堆结点的大小不一定正好等于申请的大小，系统会自动将多余的那部分重新放入空闲链表中。

3.申请大小的限制

栈：栈由高地址向低地址扩展，是一块连续的内存区域，也就是说栈底的地址和栈的最大容量是系统预先规定好的，如果申请的空间超过栈的剩余空间时，将会提示overflow，因此能从栈中获得的空间较小。

堆：堆是向高地址扩展的数据结构，且是不连续的内存区域，这是由于系统是用链表来存储空闲的内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址扩展的，堆的大小受限于计算机系统有效的虚拟内存，由此可见，堆获得的空间比较灵活，也比较大。

4.申请效率

栈：由系统自动分配，速度较快，但是程序员无法控制，

堆：一般速度比较慢，而且容易产生内存碎块，不过用起来灵活方便。

5.堆和栈中存储的内容

栈：函数调用信息，参数，返回值，分配局部变量，

堆：动态内存分配。

虚拟化CPU（主要与进程调度策略相关）

底层机制：受限的直接执行 limit direct execution

直接执行，即直接在硬件CPU上运行，以保证执行速度可以很快。

但我们有两个想法：

希望保证程序不会做我们所要求的任务以外的“坏事”，即我们要保证操作系统的控制权。🍎
希望需要时可以将它停下来切换到另一个进程，从而实现虚拟化CPU所需的时分共享。🍎🍎

因此我们希望程序的一些操作是受到一些限制的，如向磁盘发出I/O请求或获得更多系统资源。

由此我们引入了用户模式和内核模式。

🍎：先看系统控制权怎么保证。

用户模式 User mode

在用户模式下运行的代码会受到限制。

如，用户模式下，进程不能发出I/O请求，如果这样做了会导致处理器发生异常，操作系统可能会终止进程。

内核模式 kernel mode

操作系统（或内核）就以这种模式运行，在此模式下运行的代码可以做它喜欢的事情，包括特权操作，如发出I/O请求和执行所有类型的受限指令。

用户模式下的系统调用

因为用户有时候也希望执行某种特权操作，如从磁盘读取。因此，几乎所有的现代硬件都提供了用户程序执行系统调用的能力。

系统调用允许内核小心地向用户程序暴露某些功能，例如访问文件系统、创建和销毁进程、与其他进程通信，以及分配更多内存。

大多数操作系统提供几百个调用。

陷阱指令与从陷阱返回指令

想要执行系统调用，程序必须执行特殊的陷阱指令。

👉该指令将跳入内核，并将特权级别提升到内核模式。一旦进入内核，系统就可以执行任何需要的特权操作(如果允许)，从而为调用进程执行所需的工作。

👉完成后，OS调用从陷阱返回指令，该指令返回发起调用的用户程序中，同时将特权级别降低，回到用户模式。

🧠：执行陷阱的时候，硬件必须确保储存足够多的调用者寄存器，以便在OS发出从陷阱返回指令时能够正确返回。如x86上，处理器会将程序计数器、标志和其他一些寄存器推送到每个进程的内核栈上；从陷阱返回时将从栈弹出这些值，并恢复用户模式程序。

陷阱表：配置特殊情况发生时该做什么(跳到哪段代码)

🧠思考一个问题：发起调用时，陷阱如何知道该在OS内运行哪些代码呢？（即我们发起某个调用或者是发生中断时，陷阱指令需要知道该去让系统做那些事情。）

我们显然不能让调用程序去指定要跳转到的位置，这样让程序可以跳转到内核中的任意位置肯定不安全。

为此我们设置了陷阱表，它在内核启动的时候就进行设置。

机器启动时是在特权(内核)模式下执行的，因此可以根据需要自由配置机器硬件。OS第一件要做的就是告诉硬件，在发生某些异常事件(如系统调用，硬盘中断，键盘中断)时需要运行哪些代码来处理。

OS通常用某种特殊指令通知硬件陷阱处理程序的位置，硬件一旦被告知就会记住这些处理程序的位置，(直到下一次重新启动机器)，并知道了在发生系统调用和其他异常事件的时候需要做什么(即跳到哪段代码)。

🍎🍎：现在来看进程切换的问题。

进程之间的切换

🧠问题的关键：当一个进程在CPU上运行，这意味着OS此时没有运行，那么它该如何重新获得对CPU的控制权以切换其他进程呢。

有两种方式：

协作方式：等待系统调用

这种方法即当一个进程进行系统调用时，将CPU控制权转移给操作系统；

如果应用进程执行了某些非法操作，也会将控制权转移给OS，如以0为除数或者尝试访问无法访问的内存，就会陷入操作系统，那OS便将再次控制CPU(并可能终止违规进程)。

👹：但是我们可以看到这样的话操作系统只能等进程进行系统调用或者程序出错或非法才能重新“夺得”(被施舍)控制权，这岂不是太被动了吗？👇

非协作方式：操作系统进行控制

协作方式让OS太被动，想主动也可以——关机大法。。。

非协作方法用了一个很简单的办法：时钟中断(timer inerrupt)

时钟设备可以编程为每隔几毫秒产生一次中断，产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序就会运行。此时操作系统重新获得CPU的控制权，便可以做它想做的事，如我所需要的：停止当前进程，并启动另一个进程。

这不光是关于进程切换，也对帮助OS维持机器的控制权至关重要。

🧠我们同样是在启动时OS通知硬件哪些代码在发生时钟中断时运行；当然在启动过程中我们自然也必须启动时钟，这也是一项特权操作。（需要时时钟也可以被关闭，当然这也是一项特权操作。）

和程序进行系统调用时类似，当发生中断时，硬件要为本来真在运行的程序保存足够的状态，以便随后从陷阱返回指令能够正确恢复真在运行的程序。整个过程也是：各种寄存器被保存进入内核栈，结束后从陷阱返回指令可以容易地恢复。

保存和恢复上下文

🧠无论是协作方式还是非协作，系统拿到控制权后都要决定：继续当前程序，还是切换到别的程序。

——这个决定由调度程序做出，它是OS的一部分。（进程调度将在后面详谈）

这里主要说切换的底层机制。

如果决定切换，OS就会执行一些底层的代码，即**上下文切换(context switch)**。

上下文切换：系统要做的就是为当前正在执行的进程保存一些寄存器的值(比如保存到内核栈)，为将要执行的进程恢复一些寄存器的值（从内核栈），如此一来系统可以确保最后执行从陷阱返回指令时，不是返回到之前运行的进程，而是继续执行另一段进程。

OS会执行一些底层汇编代码，以

保存当前正在运行进程的上下文，来保存通用寄存器、程序计数器以及当前进程的内核栈指针；

恢复寄存器、程序计数器，并切换内核栈，供即将运行的进程使用。

通过切换栈，

内核在进入切换代码调用时，是一个进程(被中断的进程)的上下文；

而在返回时，则是另一个进程(即将执行的进程)的上下文。

如此，当OS最终执行从陷阱返回指令的时候，即完成了上下文与进程的切换。

🧠要是一个中断时或是进行陷阱处理过程中，又发生了另一个中断怎么办呢？那就是后面并发要讲的东西了。

父进程与子进程

fork()

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

int main(int argc, char *argv[]){
        printf("hello my pid:%d\n",(int)getpid());
        int rc = fork();
        if(rc<0){
                fprintf(stderr,"fork failed.\n");
                exit(1);
        }
        else if(rc == 0){
                printf("hello , i am a child. pid:%D\n",(int)getpid());
        }
        else{
                printf("hello ,i am parent of %d ,my pid:%d\n",rc,(int)getpid());
        }
        return 0;
}

        
➜ gcc -o fork fork.c
➜ ./fork            
hello my pid:5489
hello ,i am parent of 5490 ,my pid:5489//rc>0
hello , i am a child. pid:5490//rc=0

关于fork():

我们用fork函数创建新进程（子进程）

原来从main开始的原始进程为父进程，

而子进程则不会从main开始执行(可以看到hello my pid:5489这句话只执行了一次。)，而是直接从fork()系统调用返回，就好像是它自己调用了fork()一样。

因此也可以看出来，子进程并不是完全拷贝父进程，虽然他有自己的地址空间（即拥有自己的私有内存）、寄存器、程序计数器等等，但是他从fork返回的值是不同的。

父进程获得的返回值（即rc被赋予的值）是新创建的子进程的PID，而子进程获得的返回值是0，若是小于0，则说明创建子进程失败了。

这里是parent即父进程先打印出来，但实际上不一定，要取决于CPU的调度，它决定了哪个时刻哪个进程被执行。CPU调度程序非常复杂，我们不能假设哪个进程会先运行。

wait()

从上面可以知道，父子进程的执行先后不一定，但如果我想让某一个先执行呢？比如碰巧是父进程先执行，但是我非要让子进程先执行，那么我们可以让父进程先等一等，等子进程先去执行，执行完了再来执行父进程，这个任务便由wait()函数（或者更完整的兄弟接口waitpid()）来完成。

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

int main(int argc, char *argv[]){
    printf("hello my pid:%d\n",(int)getpid());
    int rc = fork();
    if(rc<0){
        fprintf(stderr,"fork failed.\n");
        exit(1);
    }
    else if(rc == 0){
        printf("hello , i am a child. pid:%D\n",(int)getpid());
    }
    else{
        int wc = wait(NULL);//与之前的区别
        printf("hello ,i am parent of %d , wc:%d,my pid:%d\n",rc,wc,(int)getpid());
    }
    return 0;
}

➜ gcc -o wait wait.c
➜ ./wait
hello my pid:5623
hello , i am a child. pid:5624
hello ,i am parent of 5624 , wc:5624,my pid:5623

可以看到现在是孩子先出来了，当然你也可以说是碰巧先执行了孩子，这也是有可能的，但是如果先轮到了parent，最后还是会先让给孩子。另外wait()的返回值就是被等待的那个进程的PID（这里即子进程）。

因此我们通过wait()让输出结果变得确定了。

exec()系统调用

之前通过fork()得到的子进程与父进程执行的都是一样的程序，如果我们希望他们执行不同的程序，则exec()可以做这样的事。

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<sys/wait.h>
#include<string.h>
int main(int argc, char *argv[]){
    printf("hello my pid:%d\n",(int)getpid());
    int rc = fork();
    if(rc<0){
        fprintf(stderr,"fork failed.\n");
        exit(1);
    }
    else if(rc == 0){
        printf("hello , i am a child. pid:%D\n",(int)getpid());
        char* myargs[3];
        myargs[0] = strdup("wc");
        myargs[1] = strdup("exec.c");
        myargs[2] = NULL;//字符数组结尾
        execvp(myargs[0],myargs);
        printf("look at me.\n");//执行了execvp成功后，当前的程序就被替换成wc程序了，execvp()的成功调用永远不会返回，故不会执行这句话了。
    }
    else{
        int wc = wait(NULL);
        printf("hello ,i am parent of %d , wc:%d,my pid:%d\n",rc,wc,(int)getpid());
    }
    return 0;
}


➜  gcc -o exec exec.c
➜  ./exec            
hello my pid:5871
hello , i am a child. pid:5872
      27      67     667 exec.c
hello ,i am parent of 5872 , wc:5872,my pid:5871

进程的调度

上下文切换这类算是进程的底层机制(mechanism)的话，那下面要说的进程调度算是OS调度程序采用的上层策略(sheduling policy)了。

定义周转时间：

T周转时间 = T完成时间 - T到达时间

1.先来先服务(First Come First Served, FCFS),或称
先进先出(First In First Out, FIFO)

我们假设所有任务A，B，C几乎同时在0时到达，（假设）A比B早一点点点，B比C早一点点点，每个工作时间都需要10秒钟

那么A先做，B再做，C再做，则A，B，C的周转时间大约是10，20，30

则平均周转时间：（10+20+30）/3=20

然而若A的工作时间为100，B为10，C为10，

则平均周转时间：（100+110+120）/3=110，显然若是B或C可以先做的话平均周转时间会小很多

⬇️

2.最短任务优先（Shortest Job First，SJF）

我们仍然假设他们同时到达，A工作时间需要100，B为10，C为10

因为先让B或C工作，

由此，平均周转时间：（10+20+120）/3=50显然快多了

在假设所有任务同时到达的情况下，最短任务优先时最优的。

然而，如果到达时间不同呢？

A先到，运行100，B和C在10的时候到也要等到100之后才能工作，

则平均周转时间：（100+110+120）/3 = 110

如果A能在中间停下来先让B和C先来拿B和C的周转时间会小很多，平均周转时间自然会小很多。

⬇️

3.最短完成时间优先（Shortest Time-to-Complete First, STCF）

基于能让A停下来的猜想，我们可以采用抢占式调度程序，即当B和C到达时我们可以抢占工作A，并运行B或C，等B和C完成后，再继续做A。

最短完成时间优先就是这样的调度程序，因此也被称作抢占式最短作业优先（Preemptive Shortest Job First，PSJF）。它可以看作是抢占式的最短任务优先。

每当新工作进入系统时候，调度程序就会判断当前剩余工作和新工作中，谁的剩余时间最少，然后调度改工作。

A：0时到达，需要时间100

B：10时到达，需要10

C：10时到达，需要10

自然A先运行，运行到10时候，B，C来了

此时A还需要90，而B、C需要10即可，故先做B（C也可以）

B做完时是20，B的周转时间为20-10=10

这时候A还需要90，C需要10，故先做C

C从20的时候开始做，做完时为30，C的周转时间：30-10=20

现在只剩下A，需要90，继续做A，做完后时间来到了120，A的周转时间：120 - 0 = 120

故平均周转时间只有（10+20+120）/3 = 50

4.轮转调度（Round-Robin,RR）

引入一个新的指标：响应时间（Response Time），意思是任务A从到达到能被执行需要等待多长时间

从上面那个例子来看，

A到了就可以执行，RT = 0

B到了就可以执行，RT = 0

C到了却要等十秒钟等B做完了才能执行，RT=10

轮转调度正是为了解决这个问题而被引入的。

基本思想：RR是在一个时间片内运行一个工作，这个时间片结束就切换到下一个任务，而不是一直运行同一个任务。如此反复直到所有任务完成。因此轮转调度有时候被称为时间切片（time-slicing）。

⚠️：时间片长度必须是时钟中断周期的倍数。

即若时钟中断是10ms中断一次，则时间片可以是10ms，20ms，30ms等等。

A：0时到达，需要工作时间5s

B：0时到达，需要工作时间5s

C：0时到达，需要工作时间5s

由于他们的耗时都一样，所以SJF和STCF是一样的效果，因此我们就把RR和SJF做比较。

SJF：

A：0～5

B：5～10

C：10～15

平均响应时间：（0+5+10）/3=5

1s时间片的RR：

A：0-1，3-4，6-7，9-10，12-13

B：1-2，4-5，7-8，10-11，13-14

C：2-3，5-6，8-9，11-12，14-15

平均响应时间：（0+1+2）/3=1

时间片的长度对RR来说至关重要，越短，RR的表现越好。

然而，时间片太短也有问题：频繁切换上下文的成本将影响整体性能。

因此，系统设计者需要权衡时间片的长短，在尽量短的同时，使其足够长，以便摊销上下文切换成本，而又不会使系统不及时响应。

举个例子，若切换上下文需要1ms，而时间片设置为10ms，那么也就是说10ms之后就要让下一个任务上来运行，所以在这之前就得切换，那么就要浪费1ms/10ms = 10%的时间用于切换上下文。（或者是10ms之后切换，那就是浪费下一个任务的时间，都一样）。但如果我们把时间片设置为100ms，那么只需要差不多1/100=1%的时间去切换上下文。

**上下文切换的成本**不仅来自保存和恢复寄存器的操作系统操作。程序运行时，他们在CPU高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态，切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。

假如我们只考虑以响应时间是我们的唯一的指标，那么带有合理时间片的RR肯定是非常好的调度程序；
但是倘若以周转时间为指标，由于RR会让每个任务差不多都要到最后才能完成，毫无疑问RR是相当差劲的。事实上若以周转时间为指标，RR几乎是最差的，在很多情况下它甚至比FIFO还要更差。

总结

我们称RR这样在较小时间内将CPU均匀分配到活动进程之间的策略成为公平的策略。

事实上，公平（响应时间）与周转时间是一对矛盾的存在。采用公平的策略，那周转时间就会被拉高；想让周转时间少，那响应时间则势必要上去了。

由于有这两种方面的需要，因此我们开发了两类调度程序，即前面说到的。

第一类，SJF，STCF优化周转时间，但对响应时间不利。

第二类，即RR，优化响应时间，但对周转时间不利。

5.结合I/O

假设任务A有I/O操作，则我们可以在A进行I/O操作而进入阻塞态时，让任务B执行，等I/O操作结束后再让A进入就绪态，甚至是你也可以选择直接把B停下让A开始工作。

我们还有一个问题没考虑，那就是我们常常在运行之前根本无法预料一个任务总共需要运行多长时间！

6.多级反馈队列（Muti- level Feedback Queue，MLFQ）

MLFQ希望解决两个问题：

优化周转时间。
降低响应时间

没错，他全都要！

我们知道像轮转这样的算法虽然降低了响应时间，但是周转时间很差；

而像SJF，STCF可以降低周转时间，但是响应时间很高。而且！我们通常不知道工作需要做多久，可这是SJF和STCF等算法所必需的。

🧠：问题来了，我们如何能在对进程一无所知的情况下去实现我们的调度目标呢？

多级反馈队列的思路是：利用历史经验来预测未来。通过在运行中学习进程的特征，从而做出更好的调度决策。

MLFQ中有许多独立的队列，每个队列有不同的优先级。任何时刻，一个工作只能存在于一个队列中，MLFQ总是执行优先级较高的工作，即在较高优先级的队列中的工作。

当然，每个队列中可能有多个工作，他们具有同样的优先级。我们对这些工作采用轮转制度。

**MLFQ策略的关键**载入如何设置优先级。MLFQ策略并不是让每个任务的优先级固定不变的，而是根据观察到的行为调整他的优先级。

例如，若一个工作不断地放弃CPU去等待键盘输入，这是交互型进程的可能行为，MLFQ会让它保持高优先级；因为他一会儿就放弃一下CPU，别的进程就有机会来执行了，所以把它保持在较高优先级，它有需要让它先执行，反正他一会儿就让出来了。

而若一个工作长时间占用CPU，MLFQ则会降低其优先级。

即我们有两类工作：

既有运行时间很短，频繁放弃CPU的交互型工作，
也有需要很多CPU时间，但响应时间却不重要的计算密集型工作。

MLFQ的基本规则：

如果A的优先级 > B的优先级，则运行A而不运行B
如果A的优先级 = B的优先级，则轮转运行A和B
一个工作刚进入系统时，总是先放在最高优先级队列中（最上层队列中）
如果一个工作用完了它在某一层中的时间配额（无论它中间主动放弃了多少次CPU），就降低其优先级（即移入低一级队列）。
- 没有规则4，系统便有漏洞可钻，如果是当一个时间片用完便降级，那我完全可以在一个时间片用完之前主动放弃CPU，下次轮到我我又可以得到一个新的时间片，这样我就能一直身居高位了，这显然不行，因为这样其他工作岂不是得不到运行的机会了。
经过一段时间S，我们就让所有工作重新进入最高优先级队列。

这个想法解决了两个问题：
- 计算密集型工作饿死的问题。如果没有这条规则，那当系统中有太多交互型工作时就会不断占用CPU，导致长工作永远不会得到CPU，即称长工作饿死了。
- 一个进程在不同时间的表现可能不同，一个计算密集型进程可能在某个时候表现为交互型进程，若没有规则5，那么便没有机制让下层的任务得到去上层的机会，一个任务只有下降的份儿，而没有上升的份儿。

比例份额的想法是：调用程序的最终目标，是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间。

份额调度的经典例子即是彩票调度（lottery scheduling）。

彩票调度：每隔一段时间，都会举行一次彩票抽奖，以此来决定接下来应该运行那个进程。当然，我们希望越是应该频繁运行的程序，越是应该拥有更多的赢得彩票的机会。

最简单公平的方法就是随机抽彩票了，另一个方法就是步长调度。

虚拟化内存（关于虚拟地址向物理地址映射的问题）

前面提到过虚拟化内存的目的——隔离。

在时分共享系统中，进程切换时，我们将进程信息仍放在内存中，这样OS可以更有效率地实现时分共享。

我们的担忧是，当多个程序同时驻留在内存中，我们不希望一个进程能读取另一个进程的内存，更别说直接把另一个进程的信息给改掉了。

因此我们希望对每个进程进行保护，即隔离，以保证各个进程不受别的进程影响。

由于物理内存是一个共享空间，因此我们需要想办法提供一个物理内存的抽象——（虚拟）地址空间，让它成为运行的程序所看到的系统中的内存。

地址空间

一个进程的地址空间包含运行的程序的所有内存状态，如：

程序的代码（或说指令）必须在内存中，因此它们在地址空间里；代码和字面常量放在代码区
程序运行时，利用栈来保存当前的函数调用信息，分配空间给局部变量，传递参数和函数返回值
堆则用于管理动态分配的、用户管理的内存，如用malloc和new申请空间
其他还有用来分配全局变量和静态变量的静态存储区等等。静态存储区分为 DATA 段和 BSS 段。DATA 段（全局初始化区）存放初始化的全局变量和静态变量；BSS 段（全局未初始化区）存放未初始化的全局变量和静态变量。

如何虚拟化内存

后面在描述地址空间时，都是指OS提供给运行程序的抽象，即虚拟地址空间。

如我们说当前程序的地址空间为0～16KB，并非指在物理内存中的0～16KB，他可能被载入到的是物理内存中的任意位置。如此，我们便说操作系统在虚拟化内存，因为运行的程序以为它被加载到特定地址的内存中，并且拥有非常大的地址空间，但事实并不是这样。

具体来说，OS在专门硬件的帮助下，通过每一个虚拟内存的索引，将其转换为物理地址，物理内存根据所获取的物理地址去获取所需的信息。OS会同时对许多进程执行此操作，并且确保程序之间互相不会受到影响，当然也不会让它们影响到操作系统本身。

这就说明了我们的虚拟内存系统的一个主要目标——透明。这里的透明不是说啥都一览无余，而恰恰相反，我们是希望一个进程好像看不见其他的进程一样。程序不应该感知到内存被虚拟化的事实，相反，程序的行为就好像他自己拥有自己的私有物理内存。在幕后，OS和硬件完成了所有的工作，让不同的工作能够复用内存。

下面具体来说其中的机制和策略。

机制：地址转换

利用地址转换，硬件每次对内存访问进行处理（即指令获取、数据读取或写入），将指令中的虚拟地址转换为数据实际存储的物理地址。每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中的实际位置。当然除了硬件，还需要OS在关键的位置介入，设置好硬件才行，因此OS必须管理好内存，记录被占用和空闲的内存位置。

如此营造一种假象：每个程序都拥有私有的内存，里面存放着它自己的代码和数据。

现实是：许多程序其实是在同一时间共享着内存。

具体方法：基址加界限机制（动态重定位）、分段、分页

基址加界限机制（动态重定位）

每个CPU需要两个硬件寄存器：基址(base)寄存器和界限(bound)寄存器/限制(limit)寄存器。

其中基址为物理地址，而界限则是指我们在虚拟地址空间中的地址(或者说是偏移量吧这样好理解一点)；

那么便有：

实际物理地址 = 基地址 + 虚拟地址；

physical address = base + virtual address；

基址加界限机制会把每个虚拟地址给转换为物理地址，但其实如栈和堆之间就有大量空隙，那么把整片地址空间都给都给映射到物理地址上就会占用了很多物理地址，这显然是一种浪费。

分段：泛化的基址/界限

分段思想将在MMU(内存管理单元，Memory Mangement Unit)中引入不止一对基址、界限寄存器；而是为地址空间中的每个逻辑段都引入一对。

一个段只是地址空间中的一个连续定长的区域（如下面代码段为2KB，堆段3KB，栈段2KB），

在典型的地址空间中有三个逻辑不同的段：代码、栈和堆。

分段思想让我们我们只将这些实际用到的空间投射到物理内存中去，以避免地址空间中未使用部分占用物理内存。

正是在支持分段的机器上，我们才看到了那个令C/C++程序员闻风丧胆的segmentation fault——段错误，以及段异常(segmentation violation)。这通常是由于访问非法的地址引起的。

举个例子：

有个地址空间中，

0～1KB：程序代码

2～4KB：空闲

4～6KB：堆

6～14KB：空闲

16～14KB：栈

那么利用分段机制，我们只将0～1KB，4～6KB，16～14KB给映射到物理内存中了。

☄️那么，当我们访问地址：7KB时，由于其无法映射到物理内存中，即它是一个非法地址，当你做出诸如此类的事情的时候机器便可能会告诉你：segmentation fault或是segmentation violation。

段寄存器

当我们采用分段机制，硬件在地址转换时会使用到段寄存器，它保存了段标识和偏移量。

关于段标识：

我们在地址转换为实际物理地址的时候，由于采用了分段机制因此我们当然要知道当前地址在哪个段内以及偏移量是多少，这样才能去找物理地址中对应的这个段存储位置和实际物理地址。

段寄存器便采用了段标识来标记属于哪个段。

比如我们采用14位的虚拟地址，假如只有我们上面提到的代码、栈和堆这三个段，那么对于每一个虚拟地址我们可以用14位中的前两位来标识(00,01,10,11)当前的地址属于哪个段，即告诉硬件我们引用了哪个段，然后用后12位来标识段内偏移量。如下所示：

(当然这里有一个问题，由于我们只有三个段，但是有四个标识00,01,10,11，加入我们用的是前三个，那么显然11开头的地址就都被浪费了，因为不会有地址往哪里映射，因此有些系统中会把堆栈当作同一个段，这样我们只需要两种标识(0，1)，那用1位就可以了。)

别忘了，分段机制还是基于基址界限方法，于是我们当然还是需要一个基址寄存器来记录当前段的基址。

于是我们来说两句题外话：

(这个不展开来说了，挖个[坑]，可以先参考

GDT详解：https://blog.csdn.net/zdwzzu2006/article/details/4030882

GDT与LDT：https://blog.csdn.net/billpig/article/details/5833980

GDT、GDTR、LDT、LDTR的学习：https://blog.csdn.net/yeruby/article/details/39718119（这篇参考了前两篇）

)

LDT表

基址用LDT(局部描述符表，Local Description Table)来记录，对于每一个进程有一个LDT表，它记录了当前进程中每个段所在的物理位置。因为每个进程都有一张，这就是为啥叫做“局部进程表”。

那么我们该如何找到哪个进程该用哪张表呢？

GDT表

既然有局部的，那么自然就有全局的，我们称为GDT(全局描述符表，Global Description Table)，这意味着所有进程都可以看到这张表并访问它，以此得到我们需要的LDT表。

GDT表中，有着不同LDT表的地址(通过LDTR和selector得到)，如下图所示。

LDTR寄存器显示的就是当前LDT表的入口/起始地址。

GDTR寄存器则是保存了GDTR表的入口/起始地址。

下图表示了，我们可以通过GDTR找到GTD，再找到LDT的过程。

话锋一转，再回到分段上来。

当我们在当前进程的LDT表的帮助下得到了某个段的基地址，于是便可以由某个段的基地址和段寄存器中标识的偏移量得到实际的物理地址：（基址界限法）

物理地址 = 基地址 + 偏移量

在我们的例子中，在段寄存器中，除了对段标识占用的两位，剩下的14位显然也标识出了我们最大的偏移量。

偏移量简化了对段边界的判断，我们只要检查偏移量是否不超过界限即可，大于界限则为非法地址。

分段的优点:

当我们原始的基址界限法的时候，我们将整块地址空间映射到了物理空间中，这样的糟糕之处在于地址空间中很多地方都没有用到，但他们映射后依然占着物理空间，这样别的进程就没法映射到这块物理地址上来，造成了极大的浪费。

这样地址空间内存在未用空间的现象中，我们称这些未用空间为内部碎片。

而分段方法则很好的解决了这个问题，因为它只将我们的各个段给映射了物理空间内，而那些我们还没想好该拿他们来干啥的空间(可以理解为还没开发的荒地)则不会被映射过去。

但是请注意，由于段是定长的，所以每个段内部其实还是有尚未使用的空间的。每个段就像是一栋楼，这栋楼虽然是已经开发之地，明确了是用来住人的(就像是栈明确了是用来放局部变量、函数参数等信息的一样)，但里面当然也有还没人住的空房间。所以“分段机制是我们用了多少就映射了多少”这种说法是不准确的。

关于栈的偏移量

由于栈是反向增长的，因此我们没法直接用基址加上正向偏移量来算物理地址。

于是我们在段寄存器中增加一位判断反向的标记(0：自大而小增长,1自小而大增长)。

由此对栈偏移做出特殊处理；

举个例子，我们仍用段标识+偏移量我们仍用14位。

（书上表16.2可能会给你误导，让你以为段大小最多为2KB，但事实上英文版的书上表中“大小”两个字的旁边还写 (max 4K)，翻译没写上。。。当初看的时候很疑惑2KB的大小怎么下面算的时候还能有3KB的偏移呢？）

说一下关于4K的问题，4K是指我们最多能为每个段分配4K的空间，而如2K则是我们现在实际为栈段分配的空间。所以我们是可以为段再分配空间的，因此可以有3KB的偏移。

而中文版的书上是这样的：(没错他还把堆的大小写错了，不知道是版本更新把错改过来了，还是就是中文版自己弄错了。原作者网站上一直保持最新版。看到3KB也不会想着段大小只有2KB了。。)

如我们访问的虚拟地址为15KB；

其二进制表示为：11 110000000000(共14位)

那么前两位为11，则我们知道它位于栈段

后面十二位为偏移量：110000000000即3KB。

那么由于标识了反向增长，则偏移量为3-4=-1KB或者你说反向偏移为-3KB那么-3+4=-1KB即正向看为正向偏移-1KB。

那么由于栈段基址为28KB，故我们的15KB的物理地址即为：

物理地址=基址+偏移量=28+（-1）=27KB。

算栈的时候由于偏移是负的，所以我们用偏移量的绝对值<=段大小来判断未过界。

共享

为了节省内存，有些东西没必要每个进程都存一次，如代码在程序运行期间不会改变，因此代码在各个地址空间之间共享是很常见的。

不难想到，地址空间之间共享可能会破坏隔离，于是我们给段寄存器再加上一个保护位，来标识某一个段的读写执行权限。

注意，这里堆段的权限为读和写，并不意味着其他地址空间的进程可以对这个地址空间的堆可以改写了。事实上，每个进程还是只能看见自己的地址空间，而共享的事情是操作系统在背后做的。一般操作系统只会让代码段在各个地址空间进行共享。这些保护位权限还是对当前进程来说的，他们能看到还是只有自己地址空间的东西，即这个进程看到“我只能对代码段读和执行啊”，那个进程看到的也是“我只能对代码段读和执行啊”，以此保证代码段内容不会被改掉。而堆栈这些操作系统根本不会让它在各个地址空间之间共享，因此每个进程读和改写的是这个进程的堆栈数据，而不会去改掉别的进程的数据

有了保护位，我们除了要检查界限，自然也要检查一下操作权限了。

外部碎片

从前面所述，可以知道，我们为每个段分配的大小是不同的。于是当曾经被占用的内存被释放的时候，就会产生很多大小不一的空间片段。物理内存中很快就会有很多这样的小片段，加起来有大很的空间，但是由于我们希望段是连续的空间，于是即使有这么大的空间也满足不了我们的分配要求。这种问题便是外部碎片问题了。

举个例子：

(图16.6:非紧凑和紧凑的内存)

左图中可以看到，我们还有8+8+8=24KB的空间空着(not in use)，但是如果我们现在想去为一个进程分配一个20KB的段却做不到，因为没有这样连续的20KB空间。这也是对空间的极大浪费。

一种方法是紧凑物理内存，即在分配之前先终止现有进程，然后把他们的数据都复制到连续的一块内存区域去，但是拷贝段是内存密集型的人物，可想而知每次都这么弄，会占用大量的处理器时间，成本极高。

另一种简单的做法就是空闲列表管理算法。

空闲列表管理算法

外部碎片的问题，不只是操作系统用分段的方式实现虚拟内存的时候有，使用用户级的内存分配库(如malloc和free函数)也会有。

说在前面，空闲列表管理相关的算法可能有成百上千种，当时无论多么精妙都无法完全消除外部碎片，所以可以把期待值降低一下，它没有你想的这么神奇。只要大小不一，就会有碎片，除非我们把分配的都是大小相同的。

下面主要从用户及内存分配库（malloc和free）出发来了解相关点，即在堆上管理空间。

(叫堆是历史原因，和数据结构中的堆不同)

在堆上管理空闲空间的数据结构通常称为空闲列表(free list)，该结构包含了所管理的内存区域中所有空闲块的引用。（空闲列表的具体数据结构不固定，只要能追踪空闲空间就行，如链表。）

空闲列表的机制：分割与合并

对于这样一个堆(字节0～29)，空闲列表会记录如下：

即两块10个字节空闲空间：字节0～9和字节20～29.

那么现在我们可以知道，申请任何大于10字节的分配请求都会失败，因为没有大于10的连续可用空间。

如果我们要分配一个小于10的空间，则分配程序会执行一个分割操作，如我们找到的是第二块空闲空间，要分配1个字节，那把字节20分配给他之后，空闲列表变成下面这样：

另一个操作就是合并。

还是看第一幅图，如现在三块空间全都放掉了，那么按理来说我们又拥有了30字节，但事实上我们得到的却是三块10个字节的空间，我们想要分配一块15字节的空间还是会失败。因此分配程序在释放一块内存的时候会合并可用空间，即在归还的时候检查一下与他相临的块是不是空闲状态，是那就把空闲列表变成这样(即合并为一个较大的块)：

可以记得，在我们用free(p)的时候并没有块大小的参数，即我们不需要说我们释放了多大的空间，由此可知分配程序本身是可以很快知道要释放空间的大小的。

这是通过“头块”实现的，它一般在我们拿到的内存块之前，如图所示：

ptr指向的即是我们所申请内存的起始位置，在这块空间之前的那块便是头块(header)，这里面保存了一些东西，至少应该保存有我们所申请空间的大小。图中的magic叫幻数，它的作用是提供完整性检查(我也不知道具体怎么用)。

由此，当用户申请N字节的内存时，库不是寻找N字节的空闲块，而是寻找N加上头块大小的空闲块；自然实际释放的也是分配的空间大小加上头块的大小。

嵌入空闲列表

上面大概说了空闲列表的样子，知道表中节点可以带我们找到空闲空间，那么这个表是存在哪儿的呢？事实上，空闲列表往往本身就在我们所管理的空间内部。

假设我们要管理一块(下面的16KB是虚拟空间中这一块空间的起始地址)大小为4096字节的空间，那么我们先设置一个头块(8字节)，它记录了空闲空间的大小(size)和下一块空闲空间的位置（next），由于现在只有一块空闲空间，故next为NULL(这里写作0)：

(有一个空闲块的堆)

由此我们得到一块4088字节的空闲块。

下面我们要分配一块100字节的空间，则共需要准备108字节的空间(8字节作头块)，

由此现在我们的空间构成为(8+100)+(8+3980):

可以看到空闲列表的头块(head)(即空闲空前最前面那8个字节)里记录的size变为了3980，当然由于我们现在还是只有一块空闲空间，故next仍为0；

以此类推，我们再分配两块空间得到下图：

我们一共分配了三块100自己的空间，假如现在我们要释放掉其中第二块(即sptr指向的那块100字节的空间)已分配空间，

那么我们的库要做的便是将它释放掉，然后把这歌空闲块加回到空闲列表，这里我们可以采用头插法插到空闲列表的最前面，如下图：

可以看到这块新的空闲块处在了空闲列表的头位置，而他指向了另一块空闲块。

也就是说，我们现在一共有了两块空闲块，一块100字节，一块3764字节。

最后提醒一点，假设我们把另外两块也给释放了，而没做其他任何操作，那么我们又回到了之前说的问题，我们没有得到一块整空闲块，而是得到了四个空闲块。如下图所示：

故我们要遍历列表，合并相邻块，完成后，堆便又成了一个整体(整体是指我们查找的时候可以作为整体查找这片空闲空间，他自身作为地址空间一直都是整体)。

(事实上前面说过，合理的做法应该是是，每次释放时，我们就应该检查相邻空闲块，并合并他们，因为空闲列表管理算法的目的就是试图尽量保留大的内存块用于分配。)

分配策略

上面说了大致该怎么分配怎么释放，那么当我们的空间中有几块空闲块(即空闲列表不止一个节点)，我们该从哪块上面分配空间个申请者呢。

理想化的分配程序当然是希望速度又快，碎片又能最小化。但是由于分配和释放的请求的序列是任意的(谁知道用户什么时候想申请多大的空间，又会在什么时候把它释放掉呢？)，所以任何特定的策略都会有表现非常差的时候。故下面说的这些策略，我们不会去说有什么最好的策略，只是看看他们的优缺点罢了。

最优匹配

遍历整个空闲列表，找到不小于申请大小的空闲块，然后选择其中最小的一个把用户需要的分配给他，剩下的留在空闲列表中。即找到一个最接近需求大小的块，尽量避免空间的浪费。

由于要遍历查找，所以要付出较高的性能代价。

最差匹配

同样遍历，不过然后是找最大的块，分割满足用户的需求，然后将剩余的块留在空闲列表中。

最差匹配想的是，由于我找的是现有的最大的块，因此我分割完了之后还能将较大的块留在空闲列表中，而不是像最优匹配那样剩下很多难以利用的小块。

然后事实表明，最差匹配算法如其名，表现非常差，与他的理想背道而驰，会导致过量的碎片，同时还有很高的开销。

首次匹配

找到第一个第一个够大的块，将请求的空间返回给用户，剩余的留在空闲列表，留给以后的请求。

这种方法不用每次遍历完整个列表，因而速度快一些，但是有时候会让列表开始的部分有很多小块。

怎么解决这些小块呢？当然是合并啦。

但是如果按照释放的顺序形成空闲列表，在堆中相邻的两块区域在列表中节点可能并不相邻。因此一个解决办法就是我们让空闲列表节点的顺序，一直和对应空闲块的地址顺序一致，这样找相邻块合并就会容易很多，从而减少了内存碎片。所以记住，我们说让相邻块合并，肯定是指实际相邻的空闲块，列表的相邻节点对应的空闲块并不一定相邻。当然也可以想到，这样的按地址排序肯定也是耗时的。

下次匹配

与首次匹配每次都从列表开头开始查找，而是多维护了一个指针，指向上一次查找结束的位置。这样做的好处是，我们会一直往下查找，将对空闲空间的查找操作扩散到了整个列表去，避免了对列表开头的地方频繁分割，堆积很多碎片。

这种策略的性能与首次匹配很接近，同样避免了遍历查找。

分段暂时告一段落，分离空闲列表、后块程序以及伙伴系统啥的以后再说。 [坑]

总结

一下分段机制的优缺点：

优点

除了和普通基址界限法一样的实现了动态重定位，还避免了地址空间的逻辑段之间大量潜在的内存浪费，分段能更好地支持稀疏地址空间。

分段要求的算法很容易，很适合硬件完成，因此很快，地址转换的开销极小。

动态重定位是通过基址➕界限实现的，意思是有了基址我们可以根据不同的虚拟地址，将地址映射到不同的物理地址上。

稀疏地址空间简单理解就是存在很多空位/未用空间的地址空间，如果只用普通的基址界限法那就会产生很多内部碎片。

缺点

由于我们给不同的段分配了不同大小的空间，于是物理内存中将会出现很多外部碎片，因此可能会让后面的申请变得困难。

一种处理办法是定期紧凑内存，另一种办法是空闲列表管理法，但无论什么空闲列表管理办法都没办法彻底解决外部碎片问题。

另一个问题是分段还是不足以支持更一般化的稀疏地址空间，如一个堆内也有可能是很稀疏的，但由于这些空间都在堆段内，因此整个堆仍然要完整地加载到内存中。

分页

简要说一下背景。

分页和分段相比主要是，将虚拟地址空间都按照固定大小的单元划分，每个单元称为一页；

同时物理内存也按照同样大小的单元划分，这样物理内存就像一个插槽阵列一样，将会带来极大的便利，每个“插槽”称为一个页帧(page frame)。每个这样的页帧包含一个虚拟内存页。我们不用担心大小不一的碎片，只需要向使用插槽一样去使用空间即可。通过完善的分页方法，OS可以高效地提供地址空间的抽象，不管进程如何使用地址空间。例如我们不会假定堆和栈的增长方向以及他们如何使用。

为了完成地址转换，记录每个虚拟页在物理内存中的位置(即对应物理页帧的位置)，OS通常会为每个进程保存一个页表(page table)，我们通过虚拟页号查页表，页表项(PTE,page table element)记录了对应的物理帧号。

我们通过虚拟页号(virtual page number,VPN)和页内偏移量(offset)来实现地址转换。

由于页表中保存了虚拟页号对应的物理帧号(PFN,physical frame number)，因此在得到虚拟页号之后通过查找页表便得到了物理帧号，而偏移量大小是保持不变的，于是我们便得到最后的物理地址。

页表往往很大，且存在物理内存中，在做地址转换的时候，我们先要根据虚拟页号找到页表项，这便需要访问一次内存，然后再根据页表项去找到物理帧号，而这才是我们真正需要访问的内存。因此直接采用分页机制暴露了很多缺点——大，消耗的内存多；多余的内存访问，也就导致很慢。

关于慢的问题，OS希望的到一些帮助来获得提速，帮助来硬件。

针对页表处理慢的解决方案：TLB

我们增加了用来处理频繁发生的虚拟到物理地址转换的硬件缓存——地址转换旁路缓冲存储器(translation-lookside buffer，也称地址转换缓存)。

对于每次转换，硬件先查看TLB，看看其中是否有期望的转换映射，如果有便完成转换(很快)，而不用访问页表(页表中有全部的转换映射)。

其实有了TLB之后，我们还是需要访问页表，这是因为TLB算法涉及到了TLB命中和未命中的问题。

算法：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2 (Success, TlbEntry) = TLB_Lookup(VPN)
3 if (Success == True) // TLB Hit
4 if (CanAccess(TlbEntry.ProtectBits) == True)
5 Offset = VirtualAddress & OFFSET_MASK
6 PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
7 Register = AccessMemory(PhysAddr)
8 else
9 RaiseException(PROTECTION_FAULT)
10 else // TLB Miss
11 PTEAddr = PTBR + (VPN * sizeof(PTE))
12 PTE = AccessMemory(PTEAddr)
13 if (PTE.Valid == False)
14 RaiseException(SEGMENTATION_FAULT)
15 else if (CanAccess(PTE.ProtectBits) == False)
16 RaiseException(PROTECTION_FAULT)
17 else
18 TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
19 RetryInstruction()

其大致流程为：

首先从虚拟地址中提取页号
检查TLB中是否有该VPN的转换映射
如果有，则称TLB命中，这意味着TLB有该页的转换映射，于是我们从TLB中相关的项提取出页帧号(PFN)，与原来的虚拟地址中的偏移量组合便得到了期望的物理地址，然后去访问那里即可。
如果没有，那么便要去访问页表来找转换映射了，并用该转换映射更新TLB，即将它加入TLB。(这里因为要访问页表需要额外的内存引用，所以会产生比命中🎯时更大的开销。)当TLB更新成功后，OS会再次尝试检查TLB寻找转换映射，而这个时候TLB中有了这个转换映射，因此内存引用可以得到很快处理。

你或许要问，为什么第四步访问页表之后不直接转换，而要先放到TLB中，然后再去查TLB呢，不是多此一举吗？

事实上用TLB和直接的页表相比，主要作用在，对于曾经进行过转换的地址来说，下次再去做地址转换的时候由于其在TLB中有记录，因此可以很快得到处理，而不用费力去查页表了。因此这里先更新TLB也是这个目的，对于当前这个地址转换我们确实看似多做了一步，但是前人种树，造福后世嘛。要知道在我们访问页表时，会导致一次额外的内存引用，如果页表很复杂可能会导致更多，所以分页开销是很大的，如果这经常发生，那程序的运行程序就会显著变慢。而TLB处于核心处理器附近，设计的访问速度则很快。

始终要记得页表和TLB做的都是对页的转换得到页帧，最后再和偏移量组合得到物理地址，而不是直接对虚拟地址转换，因此只要某一页中的第一项访问过了即VPN转换过了，那么这一页中的其他地址想要转换的时候便不会再出现不命中了(当然了，除非出啥错了，那没办法)。这也是使用TLB的一大好处。

看个例子吧。

有一个8位的地址空间，即地址用8位来表示，那么整个空间大小为2^8=256B，规定页大小为16B，则可以共有16页(即VPN：0-15)；

由于2^4=16，于是我们需要4位来标识VPN(0-15)，剩下4位来标识偏移量(图中横向的0到16offset，由于我们的例子都是四字节的数据，故写作00～04～08～12～16)。

现在我们有一个有10个4字节整数组成的数组，起始地址为100(图中可以看出6*16+4=100)。

现在我们要从a[0]到a[9]依次访问这十个元素，来看一下TLB命中情况。

一开始TLB是空的。

故访问a[0]时，TLB未命中

而接下来由于a[1]，a[2]都在06页，故TLB都命中。这就叫做空间局部性，即仍在同一页中访问。

a[3]，未命中，a[4]，a[5]，a[6]都命中；

a[7]，未命中，a[8]，a[9]命中。

至此访问结束。

10次访问，3次未命中，故TLB命中率70%，

而加入我们在这次数组访问之后不久再次访问这个数组，由于TLB中都有，于是这次的将全部命中，命中率达100%。这就是时间局部性，即短时间内对内存项再次引用。

类似于其他缓存，TLB的成功依赖于空间和时间局部性，如果某个程序表现出这样的局部性(许多程序都是这样)，那么TLB的命中率就可能很高。

关于未命中处理

以前TLB未命中使用硬件来处理，而更加现代的体系结构则有所谓的软件管理TLB，未命中的时候，硬件系统会抛出一个异常，这会暂停当前的指令流，将特权级别提升到内核模式，跳转到陷阱处理指令程序，这个陷阱处理程序自然是操作系统的一段代码，用来处理TLB未命中。这段代码运行时，会查找页表中的转换映射，然后用特别的特权指令更新TLB，并从陷阱返回。然后硬件会重试TLB查找指令，则导致TLB命中。

这里的从陷阱返回指令与之前系统调用那里不太一样，

系统调用，从这条语句陷入，返回时执行下一条语句，类似于从函数返回后执行函数调用语句的下一条语句一样；而TLB这里返回之后硬件必须从导致陷阱的指令继续执行，即上面说的重试指令(然后会导致TLB命中)。

软件管理办法灵活简单，OS可以使用任意数据结构来实现页表，不需要改变硬件；另外硬件不需要对未命中做太多工作，它抛出异常，然后OS的未命中处理程序会负责剩下的工作。

关于TLB中内容的具体形式与表项，挖个[坑]，以后再说。

针对页表太大耗费内存太多的解决办法

方法1：更大的页

由于页表只是针对页信息进行存储，而不是存下每一个地址，因此页表大小和页的数量有关，因此可以考虑增大页的大小，这样页数少了，页表中的项也就少了，即页表的大小就小了。

这种办法倒是简单，但是大页会导致每一页内的浪费，即还是内部碎片问题(因为浪费发生在分配单元内部)。因为可能当分配了一页之后，结果只用了这页中的一小部分，而内存中很快就会充满这些过大的页。

因此其实绝大多数系统在常见情况下还是会使用相对较小的页大小，如4KB(x86)。

方法2：分页和分段混合

看看上图，假设在左边虚拟地址空间中，只有代码区，堆区，栈区，他们总共只需要用4页。

而我们知道，页表肯定要保存所有的页与物理页帧的对应关系，即页表有16个表项，而我们始终只能用到4个，因此页表中的大部分都没有用到，充满了无效项(即无用的表项)，这是对页表极大的浪费，自然也造成了对内存的极大浪费。

而在讨论段的时候，我们说过，段机制只需要将用到的这些段给映射出去，而无需管其他空白的空间，因此不难想到我们可以将段和页结合使用。

这样的杂合方法不再是未整个地址空间提供单个页表，而是为每个逻辑段提供一个页表。

那么在这里便是提供三个页表，即地址空间的代码、堆和栈各有一个。

这里我们在MMU中仍用到分段中的基址寄存器和界限寄存器，区别在于

	分段机制中	段页杂合方法中
基址寄存器	告诉我们每个段在物理内存中的位置	保存的是这个段的页表的物理地址
界限寄存器	告诉我们每个段的大小	指示这个段有多少有效页如在这个例子中代码：1 栈：1 栈：2

当然我们仍要记得，每个进程都应该有自己的页表，因此上下文切换的时候需要换到新进程的寄存器，以反映新运行进程的页表的位置。

在杂合机制下，当TLB未命中时，(假设用硬件来处理TLB未命中)，硬件使用分段位来确定要用哪个基址界限对。然后硬件将其中的物理地址(指的是这个段的页表的物理地址)与VPN结合起来形成页表项PTE的地址。

杂合方法的问题所在

还是要分段，只是将段内容放在一页或几页。这样的话，比如有一个很大很稀疏的堆，占了8页但只有2页有内容，那还是对页表有很大的浪费。只是从整个空间的页表浪费变成了某一块区域的页表浪费。而且在分配段内部的浪费，这也算是出现了内部碎片吧。
由于要分段，每个段大小不一样，这就造成了每个页表大小不一样(PTE整数倍)，于是在页表存储问题上出现了外部碎片，在内存中为页表分配空间变得更为复杂。

方法3：多级页表

多级页表不依赖于分段，当然他想要解决的问题仍然是：如何去掉页表中的无效区域，而不是将他们都保留在内存中。

所谓的多级页表，就是将页表再分页，分成页大小的单元，如上图所示，我们将页表分成了四页，即：PFN201，PFN202，PFN203，PFN204(其实左图中是线性页表，其实是没有这样分的，只是为了和右图对照所以也给标出来了。)

从前学说过的可以知道，左图这样的线性页表中，即使PFN202和PFN203中都是无效的，但是我们还是要为这些区域分配页表空间；

而右图就不一样了。在这个两级页表中有一个页目录，他有多个页目录项(PDE,page directory entries)。PDE至少得有一个有效位和一个页帧号(这里的页帧号是指页表分出来的页的页帧号PFN201这些，而PFN201页中每一行才是一个PTE，第三栏的PFN是我们以前说的虚拟页的物理页帧)。

PDE的有效位数为1，是说这个页中至少有一个PTE(虚拟页)有效；否则为零，即这一页中中的PTE都无效。

上右图中可以可以看出只将201和204标为1，故只将这两页页表存在内存中。

至此，我们可以看到多级页表的一些明显优势：

最明显的就是多级页表分配的页表空间真的做到了分配的页表空间与你正在使用的内存量基本成正比；也由此它通常很紧凑，并且支持稀疏的地址空间。
另一个优势就是存放页表变得灵活方便了。原来的页表是个按照VPN来索引的PTE数组，用这样的结构，那页表(或者说这个数组)就必须驻留在物理内存中的一块连续空间中。当我们的表很大时，去找这样一块很大的连续空闲物理内存显然是挺不容易的。而用多级页表，由于我们建了目录，目录项存了页表分割成的页的地址，这就是说我们可以把页表分成好多页，把每页存在物理内存的不同地方！这样对连续空间的要求大大降低！真的是非常的amazing啊。

可以看到多级页表的一些明显优势基本是来自对内存即空间的节省。那么你不难想到，鱼与熊掌二者不可得兼，既然把控了空间的优势，那时间上就必然会出现一些不尽如人意的地方。多级页表时时间与空间这种的一个典型例子。

因此TLB很快，所以这里时间上的问题，多是来自未命中的时候要查找页表的时候出现的。

TLB未命中🎯时，需要先加载页目录，然后才能加载到具体的PTE，即需要从内存加载两次，才能从页表中得到正确的地址转换信息，而用线性表只要加载一次(即找到页表即可索引)。得也小页表，失也小页表。小页表让我们节省了空间，却消耗了时间。
结构变复杂了。我们需要经过两级结构才能找到我们需要的PTE，这使查找过程变得复杂了，当然了我们这么做也是为了节省内存。我们愿意增加复杂通常都是为了提高性能或是降低管理费用。

现在一个页表被拆成了好几页，还多加了一个目录，我们显然没法再用一个VPN号直接索引到PTE了。

那么该如何找到我们需要的PTE呢？

拿个具体例子来看吧。

现在我们有一个16KB的地址空间，因此我们需要14位地址来表示这个地址空间。

我们将其分页，每页64个字节，因此共有16KB/64B=256页，

故用8位来标识VPN，用6位来标识偏移量。

我们假设每个PTE的大小为4字节。

那么如果采用线性页表，则无论我们实际用了多少，我们都要维护一个256个PTE的页表，大小为256*4=1KB。

现在我们尝试构造一个二级页表。

我们整个页表为1KB，而我们的页为64字节，因此我们可以将整个页表分成1KB/64字节=16页，而每页64字节可以容纳64/4=16个PTE。

将整个页表划分为16页，这也就是说我们需要构建一个有16个页目录项(PDE)的目录。

不难想到，我们第一步应该先由虚拟地址找到PDE索引，PDE便会带我们到小页表去，然后第二步我们再在页表页中索引PTE，然后PTE便带我们找到了我们真正需要的物理帧号，再利用偏移量，我们便得到了最终的物理地址。

由于上面说了，我们的目录有16项，故我们应该用4位来提取页目录索引，即找到需要的PDE；

我们共有8位来标识VPN，故除了上面的4位，剩下的4位则用来做页表索引，即在页表页中找PTE。

故地址结构如下：

（虚拟页号，偏移量，页目录索引，页表索引）

我们需要的页目录项PDE的地址就为：
PDEAddr = PageDirBase + ( PDIndex * sizeof( PDE ) ) ；

如果这条PDE的有效位标记为无效，那说明我们要访问的地址无效，我们不用再往下走了。

如果标记为有效，那我们继续，往下走：

我们现在已经确定了PDE，于是用页表索引，即可得到PTE，那么PTE的地址为：

PTEAddr = ( ( PDE.PFN )<<SHIFT ) + ( PTIndex * sizeof( PTE ) ) ；

其中SHIFT即为偏移量的位数。

前面我们说过共有256页，即有256个VPN（0-255），现在假设我们要找的是第254个VPN的第0个字节，

地址即：11111110000000（即254*64=16256），VPN：11111110，offset=000000

前四位：1111=15，故找第十五个PDE：PFN=101

于是我们去查第三张表@PFN：101

然后看下面四位：1110=14；故找第十四个PTE：PFN=55，即物理帧号为55=110111

于是我们想要的物理地址为：

PhysAddr = (PTE.PFN << SHIFT) + offset

= 110111<<6 + 000000

=110111000000=00110111000000（前面加两位是因为地址为14位）

SHIFT为偏移量位数=6

多级页表>2

刚才我们说的都是二级页表；

其实如果页目录本身很大，不足以在一页放得下，那我们也要对页目录进行分页，于是往上再加一层页目录。这就是所谓的多级页表

总结

从多级页表可以看出构建页表不一定是使用线性数组，而是使用更复杂的数据结构。这样的页表体现了时间和空间上的折中。多级页表节省了空间，但是消耗了时间。而想线性页表那样的很大的表格，表个越大，TLB未命中可以处理得更快，不要因为大就想着他慢，它是通过索引拿到PTE的所以没多大关系。
说了真么多页表的事情，别忘了TLB，只有在未命中的时候我们才去查页表呢。
对于内存紧张的系统，多级页表这种拆解成小结构的做法是有意义的。而如果我们的内存比较充足，那我们使用更大的页表来加速TLB位命中的处理速度，可能才是正确的选择。说白了解决资源速度问题的的永恒终极办法都是——加钱💰。

交换空间与页面替换

比物理内存还大的地址空间

我们之前一直说把整个地址空间映射到物理内存里怎么怎么不好，基址界限那里说有内部碎片啥的。

但是现实是，我们常常没法把整个地址空间放入物理内存中，因为它比物理内存还要大。

我们为啥要把地址空间搞这么大？

当然是为了方便和易用。地址空间够大，我们不用担心数据结构是否有足够的空间存储，只管写程序，按自己的需要分配内存即可。有了足够大的空间，我们也不用去担心系统无法跑多个程序。

这是系统提供的一个巨大的假象。

那么，提供比物理内存还大的地址空间是怎么做到的呢，我们甚至常常为好几个并发运行的都进程提供如此巨大的地址空间。要知道，进程可是随时都可能用到某部分资源啊。

交换空间

答案就是交换空间了。具体来说，既然我们不能真的把所有地址空间都放到物理内存里，那就根据需要在适合的时候将一些物理页给换出去，然后让另一些页进来。

首先，我们要在硬盘上开辟一部分空间，用于物理页的移入和移出。这样的空间就是所谓的交换空间(swap space)，即我们将内存中的页换到这里，又会在需要的时候又交换回去。

因此我们假设OS能够以页大小为单元读取或者写入交换空间，为达到这个目的，OS需要记住给定页的硬盘地址(disk address)。

交换空间的大小非常重要，他决定了系统在某一时刻能够使用的最大内存页数。当然这里是说，最多有多少页可以被换进换出，物理内存中能用多少页当然还是物理内存决定的。

由此，我们便大概知道了，使用交换空间是如何让OS假装内存比实际物理内存还要大的。在某一时刻运行的进程，它可能部分数据在物理内存中，而部分数据待在交换空间中。如下图所示：

进程0，1，2在共享着物理内存，并且只有部分有效页在物理内存中，其他剩下的都在交换空间中。

而进程3的所有页都在交换空间中，因此可以知道他目前没有运行。

有一块交换空间现在是空闲的。

如何交换

通常内存引用的步骤是，进程生成虚拟内存引用，然后硬件将其转换为物理地址，去物理内存中找到并获取数据。

具体来说，硬件先根据虚拟地址获取VPN，检查TLB是否命中，命中获得正确的物理地址并从内存中取回。

如果未命中，则硬件在内存中找页表(用页表基址寄存器)，找到之后根据VPN查找页表找到PTE，然后去到物理内存中找到并取回所需数据。

但是如果采用了交换空间，那PTE可能就找不到物理地址。于是我们在页表中添加一条新信息，存在位(present bit)，存在位为1，则表示该页在物理内存中；为0，则表示该页不在内存中，而在硬盘中，这个时候便会产生“页错误”(page fault)，即访问不在物理内存中的页。

这个时候就需要OS用PTE中某些位来存放各个页的硬盘地址了，这些位通常用来存储像页的PFN这样的数据。当OS接收到页错误时，它会在PTE中查找地址，并将请求发送到硬盘，将页读取到内存中。

当硬盘I/O完成，OS会更新页表，将此页标记为存在，并更新页表项(PTE)的PFN字段以记录新获取页的内存位置，并重试指令。

然后下一次重新访问TLB还是未命中，但这次因为页在内存中，故查找页表可以将地址更新到TLB中(也可以在处理页错误的时候就更新TLB以避免此步骤)。最后再重试操作会在TLB中找到地址转换映射，我们便可以得到我们想要的物理地址，从而获取所需的数据或指令。

另外需要注意，当I/O在运行时，当前程序处于阻塞状态。因此页错误处理时，OS可以自由地运行其他可执行的进程。因为I/O操作是非常昂贵的，一个进程进行I/O时会执行另一个进程，这种交叠是多道程序系统充分利用硬件的一种方式。

页面替换

当内存充足时，我们可以根据需要去换入换出页面，可挡内存紧张了，我们就该做出抉择，内存压力迫使OS必须换出一些页，为常用的页腾出空间。显然这时候我们需要决定，该把那些页给踢出去，这就是所谓的页面替换策略。

要知道怎么换，首先应该知道我们想把它换成什么样，即我们的目标是什么？

所有的替换都是为了进程运行服务，进程运行进行内存访问当然是希望成功访问，也就是我们希望能在内存找到想找的页，能成功找到的次数越多越好，比例越高越好。

换个说法：由于内存只包含系统所有页的子集，因此可以将其看作是系统虚拟内存页的缓存，由上所述，我们的目的便是让缓存命中最多(cache hit)。

说策略之前提醒一点，一般认为缓存中一开始没有任何东西，所以所以每个页的第一次访问都是未命中的，这称为冷启动未命中。(cold-start miss)

最优替换策略

最优替换策略的想法是，换出内存中在最远的将来才会被访问到的页，这样可以达到命中率最高。其实想想很简单，一个页面要是在最远的将来才会被用到，那显然其他的页面都会比他先用到，在引用他之前肯定要先引用别的页，那把它替换出去显然是明智的。

有以下访问序列：0，1，2，0，1，3，0，3，1，2，1

命中率：6/11=54.5%

去掉强制未命中的命中率：6/7=85.7%

(根据英文版书的最新版本，这是正确的去掉强制未命中计算方法。

即命中次数/(总数-强制未命中) )

但是你想想也知道，这想法很难实现，你怎么知道谁是最远的将来才会被访问到的页呢？除非我们知道我们提前知道访问顺序。

好啦，看点儿实际点儿的策略吧。

十分简单的策略：FIFO

FIFO，即先进先出替换策略。

页进入系统时，我们将它放入一个队列，当要发生替换时候，便是最先进来的最先出去。

共11次，4次命中，7次未命中。

命中率：4/11=36.4%；

若去掉强制性未命中(即冷启动未命中)

则命中率为：4/(11-4)=4/7 = 57.1%，根据英文版书的最新版本，这是正确的去掉强制未命中计算方法。

即命中次数/(总数-强制未命中)

FIFO性能还是挺差的，另外FIFO无法确定页面的重要性，即使第0页已经被多次访问，FIFO还是会把他踢出去，只因为他是第一个进入内存的。

Belady 异常

试一下用FIFO做下面两个实验，看一下命中率

序列为A：

1，2，3，4，1，2，5，1，2，3，4，5

当缓存大小为3，命中率：1/3

当缓存大小为4，命中率1/6

可以看到，缓存变大了，命中率反而下降了。

但像LRU则不会遇到这个问题，因为LRU有所谓的栈特性。对于有这个特性的算法，大小为N+1的缓存自然包含大小为N的缓存的内容。因此当增加缓存大小时，缓存命中率至少保证不变，有可能会提高。

而像FIFO和随机等算法则显然没有栈特性。

更简单的策略：随机

顾名思义，每次随机替换一个页面，纯粹靠人品。

用上述数据做10000次实验，大概只有40%能命中6次。换其他数据还不知道啥样呢。

想上面这两种👆不考虑页面状态信息的都叫做无状态策略。

利用历史数据：LFU和LRU

FIFO也不管重要性，也不管访问频率，只管让先进来的先出去。这性能明显上不去。

于是我们希望以历史为参考设计出一些算法来。

LFU：Least- Frequently- Used ，即最不经常使用，它会把最不经常使用的页给替换出去。

LRU：Least- Recently- Used ，即最近最少使用，它会把最近使用得最少的页面给替换出去，即看谁是缓存中最常时间没被使用的。

当然也有与之完全相反的算法，MFU，最经常使用策略；MRU，最近最多使用策略。但像这些个把用的多的页面给踢掉的算法绝大多数都表现很差。

我们还是来看一下LRU吧，

命中率：6/11=54.5%

去掉强制未命中的命中率：6/7=85.7%

这已经和这组数据的最优策略一样了。

当然了也有数据巧合的因素，但可以看出来确实是比随机和FIFO要优秀不少。

一般我们该如何设计策略呢

对多数程序来说，其实都具有空间和时间局部性，之前也提过。

空间局部性就是，当页P被访问了，那页p+1和页p-1可能也会被访问；

时间局部性就是，如果p近期刚被访问过，那可能在将来不久还会被访问。

我们以此设计策略，常常有相对较好的效果。

我们用更多的数据来看一下效果

下面的实验中，我们将缓存大小从1变到100，对每个大小的缓存我们都访问一百个页来观察效果。(整个实验做完，我们一共访问了10000页)；

第一个实验假设页面访问没有局部性：

最优的表现当然是最好的，然后可以发现当没有了局部性，LRU的优势就体现不出来了，因为相当于每个页面访问操作都是随机的，与历史信息没有关系。

第二个实验访问有局部性

80-20是指，他表现出局部性：80%的引用访问的都是20%的页(即这些页是“热门页”)。

剩下的20%的访问是在对另外80%的页访问(冷门页)。

可以看到这时候LRU的优势就体现出来了，当然了跟最优策略肯定是没法比了。

第三个实验是个确定的序列

共五十页页面，我们依次访问0-49页，然后循环访问。

对于每个大小的缓存，我们都像这样做。

可以看到直到缓存到49，FIFO和LRU的命中率仍然是0。

那缓存为49距离，以FIFO来看，访问前49个页由于缓存中都没有，故都没命中；当访问第五十个页面，还是没命中，把0踢出去，50放进来；下面访问0，0刚被踢出去，还是未命中。。。。永远都是未命中。

而当缓存达到50，命中率则到了100%(应该是没算强制未命中)。

这个例子表现了LRU和FIFO的最差表现，还不如随机。

操作系统梳理漫谈：虚拟化

1.操作系统框架概述

1.1 虚拟化CPU

1.2 虚拟化内存 (virtualizing memory)

1.3 并发

1.4 操作系统的设计目标

进程与线程的联系与区别

进程

线程

进程和线程的联系

进程和线程的区别

1.根本区别

2.在开销方面

3.所处的环境

4.内存分配

为什么要设计线程

堆（Heap）和栈（Stack）的区别

1.申请方式

2.申请后系统的响应

3.申请大小的限制

4.申请效率

5.堆和栈中存储的内容

虚拟化CPU（主要与进程调度策略相关）

底层机制：受限的直接执行 limit direct execution

用户模式 User mode

内核模式 kernel mode

用户模式下的系统调用

陷阱指令 与 从陷阱返回指令

陷阱表：配置特殊情况发生时该做什么(跳到哪段代码)

进程之间的切换

协作方式：等待系统调用

非协作方式：操作系统进行控制

保存和恢复上下文

父进程与子进程

fork()

wait()

exec()系统调用

进程的调度

1.先来先服务(First Come First Served, FCFS),或称先进先出(First In First Out, FIFO)

2.最短任务优先（Shortest Job First，SJF）

3.最短完成时间优先（Shortest Time-to-Complete First, STCF）

4.轮转调度（Round-Robin,RR）

总结

5.结合I/O

我们还有一个问题没考虑，那就是我们常常在运行之前根本无法预料一个任务总共需要运行多长时间！

6.多级反馈队列（Muti- level Feedback Queue，MLFQ）

7.比例份额（proportional- share）调度 / 公平份额（fair- share）调度

虚拟化内存（关于虚拟地址向物理地址映射的问题）

地址空间

如何虚拟化内存

机制：地址转换

基址加界限机制（动态重定位）

分段：泛化的基址/界限

段寄存器

LDT表

GDT表

分段的优点:

关于栈的偏移量

共享

外部碎片

空闲列表管理算法

空闲列表的机制：分割与合并

嵌入空闲列表

分配策略

总结

分页

针对页表处理慢的解决方案：TLB

关于未命中处理

针对页表太大耗费内存太多的解决办法

方法1：更大的页

方法2：分页和分段混合

方法3：多级页表

多级页表>2

总结

交换空间与页面替换

比物理内存还大的地址空间

交换空间

如何交换

页面替换

最优替换策略

陷阱指令与从陷阱返回指令

1.先来先服务(First Come First Served, FCFS),或称
先进先出(First In First Out, FIFO)