操作系统复习笔记

操作系统介绍

操作系统的历史

第一个操作系统是在 1950 年代和 1960 年代开发的。这些早期的操作系统非常简单，专为大型计算机设计。

在 20 世纪 70 年代，操作系统开始变得更加复杂。这些新操作系统专为个人计算机设计，能够同时支持多个用户和多个程序。

在 20 世纪 80 年代，操作系统变得更加强大和用户友好。这些新操作系统能够支持图形用户界面 (GUI)，并且能够在各种硬件平台上运行。

如今，操作系统对于计算机的运行至关重要。它们为用户提供了运行应用程序、管理文件和访问硬件设备的平台。

操作系统的功能

处理机管理
存储管理
设备管理
信息资源管理

操作系统的组成部分

内核
用户界面
文件系统
设备驱动程序
服务
安全性

操作系统的特征

并发

并非是多赛道的程序运行，而是在一个时间段上，宏观的感觉多个程序在同时运行，但实际上是通过快速切换实现了同时执行的表象。OS可以通过时间片轮转、多进程、多线程等技术来实现他们。

并行：这并不是操作系统的基本特征，他主要作用在现代多处理器的设备上。他就是多赛道的程序运行，真正的同时执行。

共享

多个用户或者多个进程可以共享系统资源。例如处理器、内存、磁盘等等。OS管理这些资源的访问。

虚拟

OS将具体的物理资源抽象为高一级的逻辑实体，虚拟技术提供了一种虚拟环境。

异步

异步其实是一种编程模型。

对于任务，有一些是需要等待的，例如网络请求，需要等待响应，在等待的过程中，实际上进程并没有做任何的事情，因此在请求发出之时，这个任务对于自己就没有必须维持下去的必要了，因此引入了异步的概念。

当请求发出之后，开始异步操作，当数据返回后，再回调或者使用事件的方式处理。

因此对于异步性而言，我并不认为这是操作系统的一种特征。但是操作系统的发展历史中，异步这个概念确实和OS捆绑的很深，直到今天，无论是手机还是电脑，我们依然还在使用。

在2004年人民邮电出版的计算机操作系统/郁红英，冯庚豹的关于OS特征的描述中提到了不确定性的概念。

以下是引用

操作系统是在一个不确定的环境中运行，也就是说，人们不能对目前所运行的程序的行为作出判断。因为在多道程序环境下，进程的执行是“走走停停”的，在内存中的多个程序，何时运行？何时暂停？以怎样的速度向前推进？每个程序需要多少时间才能完成？都是不可预知的。我们无法知道运行着的程序会在什么时候做什么事情，因而一般来说无法确切地知道操作系统正处于什么样的状态。但是，这并不能说不能很好地控制操作系统，这种不确定性是允许的。不管怎样，只要在相同的环境下，一个程序无论执行多少次，其运行结果是相同的。但是它执行的时间可能不同，因为它每次执行时操作系统要处理的状况可能不同。

进程管理

程序的顺序执行

单道程序的环境中，程序可以理解为严格按照先后次序运行的序列。

这样的顺序执行的程序，具有顺序性、封闭性、可再现性的特征。

程序的并发执行

对于并发的处理技术来说，进程的执行不再是顺序的，有的进程有一个执行顺序的问题，例如对于关于IO的进程来说，必要的需要先接受到输入才能继续下一步的操作。但是对于某些进程来说却没有。

因此这样的进程具有间断性、失去封闭性、失去可再现性的特征。

进程的并发是有条件的，Bernsterin条件规定了这一点，他将程序在执行期间要参考的变量取名为“读集”，另外的在执行期间要改变的变量集合取名为“写集”。

两个进程P1与P2并发执行的条件是，当且仅当
$$
R（P1）∩W（P2）∪R（P2）∩W（P1）∪W（P1）∩W（P2）= {∅}
$$

简单的说，进程P1的读集要和P2的写集没有关系，写集要和P2的读集和写集都没有关系。才能形成无互斥的访问，两个进程才能并发执行。

进程

进程是当前正在运行的程序。

它是操作系统的基本工作单元。进程是在用户启动程序时由操作系统创建的。它们在程序终止时被销毁。

进程没有一个统一的定义，以上的说法并不准确，参考时请注意场景。

并发执行的程序在一个数据集合上的执行过程。

这段引用是郁红英老师的对于进程的定义。

对于进程，一方面要深刻的理解到这是并发执行的程序中出现的概念，对于单道系统来说，进程这样的概念只是画蛇添足。

进程是动态的，因此他的活动性值得关注。同时进程是并发的，因为在多道系统中几乎见不到单一执行的程序，通常都是与其他执行过程并发执行的。

进程与程序

这并不是一个值得讨论的概念，因为前者是在并发下的一个动态概念，后者是静态的人为的定义。

因为，两者之间的区别：

进程是动态的，程序是静态的。
进程是并发的，程序是顺序的。（在程序中，无法真实的描述并发执行的概念。因为程序并不能作为独立调度执行的单位，他只代表一组语句的集合，并且通常在程序中语句是顺序执行的。）
进程是暂时的，程序是永久的。
进程是由程序、所用到的数据源、PCB（进程控制块）组成的

但是进程与程序又密切相关，一个进程可以涉及多个程序的执行，一个程序又可以对应多个进程。

每个进程都有自己的内存空间，与其他进程的内存空间隔离。这种隔离可以防止进程相互干扰。进程也有自己的一组资源，例如 CPU 时间、内存和文件。操作系统管理这些资源并确保它们被所有进程公平使用。

操作系统使用调度程序来决定接下来应该运行哪个进程。调度程序会考虑进程的优先级、已使用的 CPU 时间量以及正在使用的内存量等因素。

当进程运行时，它可以请求资源，例如 CPU 时间、内存和文件。如果这些请求可用，操作系统将授予这些请求。如果资源不可用，进程将处于等待状态，直到资源可用。

进程的状态及转换

进程的三种基本状态。

进程一定是动态的，并且因为在并发的环境下，因此进程具备着运行、就绪和阻塞着三种基本的状态。

运行，是进程在CPU上运行的状态，在单处理机的系统中，只有一个进程，但是多处理机的系统中可能存在多个进程。、

就绪，就绪的含义指的是进程已经获取了除了处理机之外的资源，正准备进入处理机运行的状态。

阻塞，进程进入等待操作或者因为某些进程或事件暂停时，就处于阻塞状态。

就绪与阻塞不同的时，就绪只需要分配处理机，但是阻塞需要满足等待条件，才能运行，如果不满足等待条件，即使将处理机分配给阻塞状态的进程，也无法运行。

进程的状态转化

对于进程的状态，实际上如果说计算机的资源无限，能满足所有进程的需要，那么进程就不会出于阻塞或者就绪状态，而是处于运行状态。（阻塞状态除外，因为存在一个进程等待另一个进程执行完毕或者一个进程在等待另一个进程占用某种资源而导致的阻塞状态的情景。）

但是明显的，资源是有限的，因此进程会根据外部环境的变化而改变状态。

就绪——运行状态。处于就绪状态的进程，具备了运行的条件，但是未能获得处理机，因此没有运行。所以对于这种的状态转换，是由进程调度程序负责的，它使得进程获得处理机，投入运行。

运行——就绪状态。正在运行的进程拥有一个属性叫做时间片，当时间片用完进程就会被暂停执行，此时的进程就会从运行状态转变为就绪状态。

运行——阻塞状态。处于运行状态的进程，除了因为时间片用完而暂停之外，还可能因为某些因素影响无法继续下去，此时的进程就会开始等待条件之中，进入阻塞状态。

阻塞——就绪状态。当满足等待条件之后，并不能立即运行，而是先转化为就绪状态等待处理机。

五种状态

对于进程，因为操作系统本身的复杂性，他的创建和退出并不是容易得事情，因此许多的系统增加了这两种状态。

创建状态，进程正在创建之中，还不能运行，此时的进程会被OS分配PCB（进程控制块）包括填写相关的内容、为进程分配组、连接进程可能存在的父子关系，为进程分配资源、建立地址空间等。当就绪队列接纳新建的进程时，进程就进入就绪状态。
退出状态，进程正常或异常技术，OS要将进程从运行状态中移除，使之成为一个不可能再运行的进程，使得进程成为退出状态，并回收资源，但是此时的OS并没有立即的撤销，而是暂时的留在系统里。

挂起状态

为不同的OS中，进程的状态是不同的。

在某些时候，我们需要将进程移出内存，或者是让程序暂停以便于我们调试。此时就需要新增另一种新的状态，挂起。

这似乎和就绪或者是阻塞概念重合了，但实际上挂起正式对两者的细分。

对于挂起，有阻塞挂起与就绪挂起。对于新状态引入的状态转换有挂起和激活两种。

所谓的挂起就是将进程从内存移出到外出，相反激活就是将外存的进程再移回内存。

进程控制块

进程是由程序段、数据段和进程控制块组成的。

程序段是用户定义的，描述了进程本身索要完成的功能，数据段是程序操作的一组存储单元，是程序操作的对象，而进程控制块是在进程创建时建立的，在进程存在时，实际上进程控制块就代表了这个进程。

一般的进程控制块中的信息是包括描述与控制进程运行的。

进程描述信息（进程名、标识符、所属用户名和进程组）
处理机状态信息（寄存器、PC指令计数器、程序状态字，栈指针）
进程调度信息（进程状态、优先级、运行统计、阻塞原因）
进程控制和资源占用信息（程序入口地址、程序外存地址、进程同步与通信、资源占用信息、链接指针）

一般的，对于PCB可以使用链接方式，将相同状态的PCB链接成一个队里，就会形成一个运行、就绪、阻塞、空队列。在队列中就可以进行调度，调节进程运行顺序。还可以使用索引的方式，建立索引表。

进程控制

进程控制的作用就是对进程进行有效的管理。

为了防止OS和关键的数据结构收到用户程序的破坏，因此处理机的执行状态一般的分为系统态和用户态。

系统态，核心态。特权高，能执行一切指令，访问一切的寄存器和内存。一般的OS内核就运行在系统态。

用户态，低特权，只能执行规定指令，访问指定的寄存器和内存的指定区域。

操作系统导论中对于这一技术的描述是，LDE（受限的直接执行）

有一个很关键的前提，无论如何，一个CPU在同一时间都只能运行一个程序。

因此如果说此时有一个程序运行需要读取或者写入磁盘，那么此时实际上任何的权限系统都是无效的，因为此时的CPU中，它并没有运行。

因此一种新的处理器模式被引入，即用户态。这种模式执行的程序是受到限制的。

内核与原语

所谓内核并不是一个具体的物理设备，操作系统内核的本质就是原语的实现。内核中的是一些与硬件紧密相关的模块。

所谓的原语就是原子操作。（不可分割，也就是要么全执行要么全部执行）

内核为系统对进程的控制和对内存的管理提供了有效的机制。

线程

进程是一个虚拟化的对象，为了解决并发的问题而出现。

而线程是为了减少程序并发执行所需要的时空开销。

因为进程是资源的拥有者，因此频繁的转换进程状态十分浪费资源。

线程是进程的一个实体，是独立调度的单位，表示进程的一个控制点，执行一系列指令。

进程的互斥与同步

进程具有异步性，为系统造成了混乱，特别是临界资源。虽然在执行上能够正常执行，但是在输出结构时，多个进程的结果可能交织在一起。

并发：本质是不断切换进程达到的多个进程同时运行的假象。

问题：

变量共享具备了危险，如果两个进程同时对一个数进行累加n次，最后的结果不会是2n，因此这并不是原子操作，对数加和保存有可能会冲突，导致结果不如意。（代码在操作系统导论）
资源分配很难最佳
定位错误变难

因此，为了解决以上的问题，OS必须记录进程情况，为这些进程分配和释放资源，保护进程数据和资源，保证结果正确。

进程的并发，使得进程之间不可能离开交互，也就是说进程之间应该存在通信。

进程之间的交互包括互斥、同步与通信。

互斥

这是由共享资源决定的，当一个进程占用或者使用这个资源时，其他进程必须等待。

同步

同步指的是进程之间必须存在某种时序关系，也就是说必须是A执行完再执行B。

通信

通信指的是进程之间要传递的信息。

临界资源

有的资源在一个时间段内只允许一个进程使用，这就是临界资源。

如果多进程使用，就必须使用互斥的方式。

那么每一个进程中访问临界资源的那段代码就是临界区。

对于同步

空闲让进，当临界区没有进程，也就是此时临界资源处于空闲状态时，它应当与其他资源保持一致，允许任何进程进入。
忙则等待，当有进程访问临界资源时，其他想访问的进程必须等待。
有限等待，对于访问临界资源的进程，要保证在有限的时间内进入。
让权等待，当进程不能进入临界区时，应该释放处理机。

进程互斥的方法

一般的实现进程互斥，有两种方法。

1、希望进程自己完成

2、使用专门的机器指令

3、操作系统来控制

最初的方式是在进程进入时，设置一些标志。

单标志算法

设置一个公共整形变量，当进程进入临界区时检查变量，确定是否可进，在进程退出临界区时，又修改。

这能满足任何时刻只有一个进程进入临界区，但是缺点是无法满足空闲让进的问题。
双标志算法（先检查）
先检查后修改
先修改后检查后修改者等待

在硬件上有一些方式也可以实现进程互斥，但是不能适应进程数量很多的情况。

基本思路是，用一条指令完成读和写两个操作，保证读写不被打断。

信号量与PV

信号量是一个用于解决进程同步问题的设计，通俗的说他就是一个可以在C中表示的结构体。

PV操作，P与V都是原语，P代表进程请求一个资源，而V表示进程释放一个资源。

最初的信号量值包含一个整形值和一个等待队列。

struct semaphore{  
	int value;  
	struct QUEUETYPE *queue;  
}

P操作（一般使用wait函数来表示）

void wait(semaphore s)  { 		s.value = s.value - 1;  
	if (s.value < 0)  				block(s.queue); /* 将进程阻塞，并将其投入等待队列 s.queue */
}

V操作（一般使用函数signal表示）

void signal(semaphore s)  { 	s.value = s.value + 1;  
	if (s.value <= 0)  				wackup(s.queue);  /* 唤醒被阻塞进程，将其从等待队列 s.queue 取出，投入就绪队列*/ 
}

在信号量机制中，信号量的初值 s.value 表示系统中某种资源的数目，因而又称为资源信号量。

AND信号量

当一个进程需要先获得多个临界资源的资源事后，之前的单个资源的互斥访问就无法起到作用了。很容易出现僵持的状态。

其基本思想是，将进程在整个运行期间所需要的所有临界资源，一次性地全部分配给进程，待该进程使用完后再一起释放。

因为一个AND条件，所以称作是AND信号量。

Swait(s1,s2,…,sn)
{
	if (s1 >= 1 && s2 >= 1 && … && sn.>= 1) { 
		/* 满足资源要求时*/ 
 		for (i = 1; i <= n; i = i + 1) 
 			si = si -1; 
 	} 
 	else 
 	{ /* 某些资源不能满足要求时*/ 
		将进程投入第一个小于 1 的信号量的等待队列 si.queue ; 
		阻塞进程;
 	}
}

以上是wait的函数的伪代码，signal函数同理。

但是可以看出此时临界值一直是1，这明显不符合实际。

一般“信号量集”

如果进程同时需要多种资源，且对每种资源需要的数目不同，并且系统在分配资源时存在一个临界值 t，只有系统中的资源数大于 t 时，才予以分配且一次分配 d 个（通常 t >= d）资源；否则不予分配。

这样就对AND信号量进行扩充。

Swait(s1,t1,d1,…,sn,tn,dn)
{
	if (s1 >= t1 && s2 >= t2 && … && sn.>= tn) { 
		/* 满足资源要求时*/ 
 		for (i = 1; i <= n; i = i + 1) 
 			si = si -di; 
 	} 
 	else 
 	{ /* 某些资源不能满足要求时*/ 
		将进程投入第一个小于 1 的信号量的等待队列 si.queue ; 
		阻塞进程;
 	}
}

一般“信号量集”可以用于各种情况的资源的分配和释放。下面我们讨论几种特殊情况：

Swait(s,d,d)。此时在信号量集中只有一个信号量，但它允许每次申请 d 个资源，当现有资源数小于 d 时，不予以分配。
Swait(s,1,1)。此时在信号量集已经退化为互斥信号量。
Swait(s,1,0)。可作为一个可控开关，当 s≥1 时，允许进程进入某临界区；当 s = 0 时，禁止进程进入某临界区。

这些特殊情况下的一般信号量，使用时非常灵活，有时并不成对使用。为了避免死锁，常常一次申请所需要的资源，但不一起释放。

生产者和消费者问题

一组进程被称为生产者，另一组进程被称为消费者。缓冲池是由若干个大小相等几个的缓冲区组成的，每个缓冲区可以容纳一个产品。生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。指针 i 和 j 分别指向当前的第一个空闲缓冲区和第一个存满产品的缓冲区。

在生产者和消费者问题中，既存在着进程同步问题，也存在着临界区的互斥问题。当缓冲区满时，表示供大于求，生产者必须停止生产，而进入等待状态，同时唤醒消费者；当所有的缓冲区都空时，表示供不应求，消费者必须停止消费，唤醒生产者。这就是生产者进程和消费者进程的同步关系。对于缓冲池，它显然是一个临界资源，所有的生产者和消费者都要使用它，而且都要改变它的状态，故对于缓冲池的操作必须是互斥的。

读者、写者问题

一个数据对象若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求写操作，对此，我们把只想读的进程称为“读者”，而把要求写的进程称为“写者”。在读者、写者问题中，任何时刻要求“写者”最多只允许有一个执行，而“读者” 则允许有多个同时执行。因为多个“读者”的行为互不干扰，他们只是读数据，而不会改变数据对象的内容，而“写者”则不同，他们要改变数据对象的内容，如果他们同时操作，则数据对象的内容将会变得不可知。所以对共享资源的读写操作的限制条件是：允许任意多的读进程同时读；一次只允许一个写进程进行写操作；如果有一个写进程正在进行写操作，禁止任何读进程进行读操作。

哲学家进餐问题

有五个哲学家，他们的生活方式是交替地思考和进餐。哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时拿起其左、右的两支筷子进餐，进餐完毕又进行思考。这里的问题是哲学家只有拿到靠近他的两支筷子才能进餐，而拿到两支筷子的条件是他的左、右邻居此时都没有进餐。

管程

管程的基本思想是把信号量及其操作原语封装在一个对象内部。即将共享资源以及针对共享资源的所有操作集中在一个模块中。

可把管程（monitor）定义为关于共享资源的数据结构以及一组针对该资源的操作过程，这组操作能同步进程和改变管程中的数据。管程可以用函数库的形式实现，一个管程就是一个基本程序单位，可以单独编译。管程的主要特征是：

（1）封装于管程的共享变量（数据结构），且该变量只能被管程的过程访问，任何外部过程都不能访问。

（2）一个进程通过调用管程的一个过程进入管程。

（3）任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变为可用。

进程通信（IPC）

操作系统提供了多种允许进程相互通信的IPC机制。这些机制包括共享内存、管道和套接字。

共享内存

共享内存是一种技术，其中两个或多个进程共享一个公共内存块。这允许进程轻松地彼此共享数据。

管道

管道是一种单向通信通道，允许两个进程相互通信。管道通常用于进程之间的短期通信。

套接字

套接字是一种双向通信通道，允许两个进程相互通信。套接字通常用于进程之间的长期通信。

消息传递

此方法允许进程相互发送消息。消息可以包含数据、控制信息或两者。

IPC 方法的选择取决于应用程序的具体需求。例如，共享内存对于需要频繁共享数据的进程是一个不错的选择，而消息传递对于需要不频繁通信的进程是一个不错的选择。

死锁

死锁可以被定义为一组竞争系统资源或相互通信的进程相互的“永久”阻塞。

其实关于死锁这个概念，前文已经大段的叙述了很多，包括针对于临界资源的处理，使用的标志算法与信号量都是为了预防死锁。

下面简短的描述一下。

死锁的必要条件：

互斥条件
请求和保持
不可剥夺

以上三者很容易导致环路，那么死锁就不可避免的产生了。

对于死锁的预防和避免，同样根据他的必要条件来实施。

检测死锁

如何判断是否出现死锁，是根据进程是否有循环等待的。

将进程与申请资源情况描述为有向图，那么当有环时就代表出现了死锁。

死锁的解除

一旦检测到死锁，就需要解除死锁。下面是解除死锁的方法：

（1）撤消所有的死锁进程。这是操作系统中最常用的方法，也是最容易实现的方法。（2）把每个死锁的进程恢复到前面定义的某个检查点，并重新运行这些进程。要实现这个方法需要系统有构造重新运行和重新启动机制。该方法的风险是有可能再次发生原来发生过的死锁，但是操作系统的不确定性（随机性），使得不会总是发生同样的事情。

（3）有选择地撤消死锁进程，直到不存在死锁。选择撤消进程的顺序基于最小代价原则。在每次撤消一个进程后，要调用死锁检测算法，以检测是否仍然存在死锁。

（4）剥夺资源，直到不存在死锁。和（3）一样也需要基于最小代价原则选择要剥夺的资源。同样也需要在每次剥夺一个资源后，调用死锁检测算法，检测系统是否仍然存在死锁。

最小代价原则

（1）到目前为止消耗的处理机时间最少。（2）到目前为止产生的输出最少。

（3）预计剩下的执行时间最长。

（4）到目前为止分配的资源总量最少。（5）进程的优先级最低。

（6）撤消某进程对其他进程的影响最小。

处理机调度

调度源自管理领域。

在调度时，需要考虑一些指标。

指标是我们用来衡量某些东西的东西，在进程调度中，有一些不同的指标是有意义的。现在，让我们简化一下生活，只用一个指标：周转时间（turnaround time）。任务的周转时间定义为任务完成时间减去任务到达系统的时间。更正式的周转时间定义

T 周转时间是： T 周转时间= T 完成时间−T 到达时间

因为我们假设所有的任务在同一时间到达，那么 T 到达时间= 0，因此 T 周转时间= T 完成时间。随着我们放宽上述假设，这个情况将改变。

你应该注意到，周转时间是一个性能（performance）指标，这将是本章的首要关注点。另一个有趣的指标是公平（fairness），比如 Jian’s Fairness Index[J91]。性能和公平在调度系统中往往是矛盾的。例如，调度程序可以优化性能，但代价是以阻止一些任务运行，这就降低了公平。这个难题也告诉我们，生活并不总是完美的。

周转时间是指一个用户作业被提交到完成的时间间隔。

为了进一步衡量作业在处理机上的实际执行时间和等待时间，我们还定义带权周转时间 Wi 为作业的周转时间 Ti 与它在处理机上实际执行时间 Tsi之比。

调度算法

先来先服务（First Come First Serivice，FCFS）是一种最简单的调度算法，可以用在进程调度和作业调度中。它的基本思想是按进程或作业到达的前后顺序进行调度。

短作业（进程）优先（Shortest Job First，SJF 或 Shortest Process Next，SPN）。是指对短作业或短进程优先调度的算法。该算法可分别用于作业调度和进程调度。

时间片轮转法主要用于进程调度。通常，系统将所有的就绪进程按 FCFS 原则，排成一个队列，每次系统调度时，把处理机分配给队首的进程，并令其执行一个时间片，时间片的大小一般是几个毫秒到几百个毫秒。当一个进程被分配的时间片用完时，由系统时钟发出一个中断，调度程度暂停当前进程的执行，并将其送到就绪队列的末尾。同时从就绪队列队首选择另一个进程运行。

为了照顾到进程的紧急程度，使得紧急的进程能够及时得到处理，很多的操作系统使用了优先权调度算法。优先权调度算法适用于作业调度和进程调度。当该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业调入内存。当用于进程调度时，把处理机分配给就绪队列中优先权最高的进程。进程调度中使用优先权调度算法时又可把算法分成两种方式：可剥夺方式和不可剥夺方式。

多级反馈队列调度算法是一种较好的进程调度算法，在 UNIX 及 OS/2 中都采用了类似的算法。在这种算法中，设置多个就绪队列，每个队列的优先权不同，第一个队列的优先权最高，第二个队列次之，依此类推，队列的优先权逐个降低，

算法\|特点	FCFS	SPN	SRT	HRRN	时间片轮转	优先权	多级反馈队列
决策模式	不可剥夺	不可剥夺	不可剥夺	不可剥夺	剥夺（时间片用完时）	剥夺	剥夺（时间片用完时）
吞吐量	不强调	高	高	高	若时间片太短，吞吐量会很低	不强调	不强调
响应时间	有时可能高	短进程的响应时间比较高	较高	较高	高	高	高
系统开销	最小	较高	较高	较高	较小	较高	较高
对进程影响	对短进程不利	对长进程不利	对长进程不利	较好的平衡各种进程	对 I/O 频繁的进程不利	较好的平衡各种进程	可能对 I/O 频繁的进程有利
饿死	无	可能	可能	无	无	可能	可能

存储管理（内存）

操作系统提供一个易用（easy to use）的物理内存抽象。这个抽象叫作地址空间（address space），是运行的程序看到的系统中的内存。

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

包括代码段、栈、堆。当然做为一个复杂的程序，肯定还有其他比如静态初始化的变量这些东西，但是假设只有这三个部分。

代码段：程序的代码与指令，这很容易理解，他们要想运行就必须在内存中。

栈：一种先进后出的数据结构，用来保存当前的函数调用信息，分配空间给局部变量，传递参数与返回值。

堆：完全二叉树，同样是一种数据结构。他并不是用来保存什么的，他的主动功能是管理动态分配、用户管理的内存。例如c语言中的malloc。

在地址空间中，代码段一般来说无关轻重，因为他们从执行的那一刻开始就是不变的了，因此值得关注的是栈和堆。

在地址空间的逻辑抽象中，他们一个在顶部，一个在底部，中间是未分配的可以给他们扩展的空间。

栈一般在底部，堆在顶部。当然这只是一种约定，并没有什么含义。

地址转换

如果你打印过指针，那么你会得到一串地址，但是很遗憾那是虚拟的，实际上对于用户级的程序员来说，都是虚拟的。

只有操作系统，通过精妙的虚拟化内存技术，知道这些指令和数据所在的物理内存的位置。虚拟地址只是提供地址如何在内存中分布的假象，只有操作系统（和硬件）才知道物理地址。

有一个问题？在c语言里，没有自动回收机制的存在，但是我执行完程序之后，不需要手动执行free，这难道不会造成内存泄漏嘛？

不会，因此实际上有两层的内存管理，一层是进程，一层是OS的管理。即使进程没有free，地址空间中堆的状态如何，OS会在进程结束后释放这一切。

将虚拟地址转换为物理地址，这正是所谓的地址转换（address translation）技术。

重定位

地址重定位完成的是相对地址转换（逻辑地址）成内存的绝对地址（物理地址）的工作。地址重定位又称为地址映射。按照重定位的时机，可分为静态重定位和动态重定位。

静态重定位有许多问题，首先也是最重要的是不提供访问保护，进程中的错误地址可能导致对其他进程或操作系统内存的非法访问。因此现在的重定位更多的需要依赖硬件。

动态重定位是指程序在执行过程中进行地址重定位。更确切地说，是在每次访问每个地址单元前再进行地址变换。动态重定位需要硬件——重定位寄存器的支持。

具体来说，每个 CPU 需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存器，有时称为限制（limit）寄存器。这组基址和界限寄存器，让我们能够将地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的地址空间。

进程中使用的内存引用都是虚拟地址（virtual address），硬件接下来将虚拟地址加上基址寄存器中的内容，得到物理地址（physical address），再发给内存系统。

硬件取得进程认为它要访问的地址，将它转换成数据实际位于的物理地址。由于这种重定位是在运行时发生的，而且我们甚至可以在进程开始运行后改变其地址空间。

链接

链接程序的功能是将经过编译后得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。

实现链接的方法有三种：静态链接、装入时动态链接和运行时动态链接。

其中静态链接是编译后得到的，后两者如名。

分段

为什么要分段？

实际上，在单核的情况下，一个时间点只有一个进程在执行，那么这个进程完全即使完全占用全部的内存空间也没有关系，为什么还要对内存空间进行划分？？？是因为并行的执行情况吗？

上文中提到，在堆和栈中间存在中很大的一部分空间。

如果不对内存空间做任何操作，那么这一部分空闲的空间就会陷入一种尴尬的境地，那就是不被使用却占用了实际的内存，以上的那种由基址寄存器和界限寄存器实现的虚拟内存就会十分的浪费。另外，如果剩余物理内存无法提供连续区域来放置完整的地址空间，进程便无法运行。这种基址加界限的方式看来并不像我们期望的那样灵活。

因此我们需要新的更加灵活的方式来处理。

引入不止一个基址和界限寄存器对，给地址空间内的每个逻辑段（segment）一对。一个段只是地址空间里的一个连续定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈和堆。分段的机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了虚拟地址空间中的未使用部分占用物理内存。

段错误指的是在支持分段的机器上发生了非法的内存访问。有趣的是，即使在不支持分段的机器上这个术语依然保留。

空闲空间管理

事实上，要管理的空闲空间由大小不同的单元构成，他们不是连续的，管理就变得困难（而且有趣）。

在用户级的内存分配库（如 malloc()和 free()），或者操作系统用分段（segmentation）的方式实现虚拟内存。

在这两种情况下，出现了外部碎片（external fragmentation）的问题：空闲空间被分割成不同大小的小块，成为碎片，后续的请求可能失败，因为没有一块足够大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。

此时我们需要引入一些来自底层的机制。

分割和合并

当我们申请一个较小的空间时，刚好此刻的空闲空间足够，那么分配程序执行分割动作，找到一块满足的空间分割，将满足用户需求的一块返回，剩下的留在空闲空间中。

追踪已分配空间的大小

要想完成free函数，就必须完成这一点，毕竟你可以发现，在这个函数使用时，并没有携带参数。

大多数分配程序会在头部保存一点额外信息，他在返回的内存块之前。

嵌入空闲空间

让堆增长

当空闲空间的内存耗尽？此时如果还需要分配，那么就可以请求系统再次分配。

匹配策略（空闲空间分配算法）

最优匹配（best fit）策略非常简单：首先遍历整个空闲列表，找到和请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块。这就是所谓的最优匹配（也可以称为最小匹配）。只需要遍历一次空闲列表，就足以找到正确的块并返回。

最差匹配（worst fit）方法与最优匹配相反，它尝试找最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表。最差匹配尝试在空闲列表中保留较大的块，而不是向最优匹配那样可能剩下很多难以利用的小块。但是，最差匹配同样需要遍历整个空闲列表。更糟糕的是，大多数研究表明它的表现非常差，导致过量的碎片，同时还有很高的开销。

首次匹配（first fit）策略就是找到第一个足够大的块，将请求的空间返回给用户。同样，剩余的空闲空间留给后续请求。

下次匹配（next fit）算法多维护一个指针，指向上一次查找结束的位置。其想法是将对空闲空间的查找操作扩散到整个列表中去，避免对列表开头频繁的分割。这种策略的性能与首次匹配很接它，同样避免了遍历查找。

分页

先回顾吧，OS如何管理空间呢？

基址加界限寄存器的方式让OS能在单进程运行时，管理程序、堆栈，并且实现对堆栈的扩展。

但是这样不灵活的方式十分的浪费空间，于是引入多对基址加界限寄存器构成了分段。

本质上说，空间被分割成了不同长度的片。

但是这样来管理空间出现了问题，相信如果你实现了对于空闲空间的管理之后，就会发现。

使得，空间本身变得碎片化，并且分配内存会变得十分困难，因为涉及到大量的合并操作。

因此，OS考虑了新的解决方案，同样是分割，但是长度变为定长的，这就是分页。

也就是说分页不是像分段那样将一个进程的地址空间划分为不同长度的逻辑段，而是分割成固定大小的单元，每个单元成为一页。那么相对应的，物理内存被成为定长槽块的阵列，叫做页帧。每个这样的页帧包含一个虚拟内存页。

为了记录地址空间的每个虚拟页放在物理内存中的位置，OS通常为每个进程保存一个数据结构叫做页表。页表的主要作用就是为了每个虚拟页面保存地址转换，从而让我们知道每个页具体的物理位置。

重要的是，页表是每一个进程的数据结构。

页表大吗？页表可以很大。

因此面对如此庞大，而作用仅仅是来处理地址转换的数据结构，明显的不会用到任何物理硬件来存放它。一般的，它都在内存中。

小小世界

你看到的不止如此