第一章 操作系统概述

什么是操作系统/span>

 

1. 软件中最基础的部分是操作系统，它运行在内核态（也称为管态、核心态）。在这个模式中，操作系统具有对所有硬件的完全访问权，可以执行机器能够运行的任何指令。软件的其余部分运行在用户态下。在用户态下，只使用了机器指令中的一个子集。特别是那些会影响机器的控制或可进行I/O的操作指令，在用户态中的程序是禁止的。
2. 作为资源管理者的操作系统：负责对系统的硬软件资源实施有效的控制和管理，提高系统资源的利用率。

     资源管理包括用一下两种不同方式实现多路复用（共享）资源：

在时间上复用：当一种资源在时间上复用时，不同的程序或用户轮流使用它。

在空间上复用：每个客户都得到资源的一部分，从而取代了客户排队。

      3. 作为扩展机器的操作系统：是计算机硬件的首次扩充，掩盖了硬件操作的细节，使用户或程序员与硬件细节隔离，从而方便了用户的使用。

操作系统的作用

1. 从一般用户的观点来看，操作系统是用户与计算机硬件系统之间的接口。用户并不直接与计算机硬件打交道，而是通过操作系统提供的命令，系统功能调用以及图形化接口来使用计算机。
2. 从资源管理的观点来看，操作系统使计算机资源的管理者。处理机的分配和控制，内存的分配和回收，I/O设备的分配和处理，文件的存取，共享和保护工作都是由操作系统完成的。
3. 从虚拟机的观点来看，操作系统是扩充裸机(没有配置软件的计算机)功能的软件。在裸机上覆盖操作系统后，裸机将变成一台功能更强大使用更方便的虚拟机。
4. 从任务组织的观点来看，操作系统是计算机工作流程的组织者。它负责在众多作业间切换处理机，并协调它们的推进速度，从而进一步提高系统的性能。

操作系统的设计目标

1. 方便性：操作系统使计算机系统更易于使用
2. 有效性：操作系统使计算机资源的使用更有效，即使资源的利用率更高
3. 可扩充性：操作系统必须能方便地开发，测试和引进新的系统功能，以适应计算机硬件和体系结构的迅速发展以及应用不断扩大的要求
4. 开放性：操作系统必须能提供统一开放的环境，以使其应用在不同的系统中具有可移植性，并使不同的系统能够通过网络进行集成，从而能正确，有效地协同工作

操作系统的5大功能

1. 进程管理功能
2. 存储管理功能
3. 设备管理功能
4. 文件管理功能
5. 作业管理功能

计算机硬件介绍

1. 处理器CPU

计算机的大脑是CPU，它从内存中取出指令并执行。在每个CPU基本周期中，首先从内存中取出指令，解码以确定其类型和操作熟，接着执行之，然后取指、解码并执行下一条指令。

寄存器：在CPU内部用来保存关键变量和临时数据。种类：程序计数器、堆栈指针、程序状态字

2. 存储器

寄存器：它们用与CPU相同的材料制成，所以和CPU一样快，访问没有延时

高速缓存：其作用是为了更好的利用局部性原理，减少CPU访问主存的次数。简单地说，CPU正在访问的指令和数据，其可能会被以后多次访问到，或者是该指令和数据附近的内存区域，也可能会被多次访问。因此，第一次访问这一块区域时，将其复制到cache中，以后访问该区域的指令或者数据时，就不用再从主存中取出。现代CPU中设计了两个缓存：L1缓存和L2缓存，两者的差别在于时序，对于L1缓存的访问，不存在任何延时；而对于L2缓存的访问，则会延时1或2个时钟周期。

主存：也称为随机访问存储器（RAM），所有不能在高速缓存中得到满足的访问请求都会转往主存。

磁盘：磁盘唯一的问题是随机访问数据时大约慢了三个数量级。其低速的原因是因为磁盘是一种机械装置。

3. 输入/输出设备

I/O设备一般包括两个部分：设备控制器和设备本身。

控制器：它是插在电路板上的一块芯片或一组芯片，这块电路板物理的控制设备。它从操作系统接收命令。例如，从设备读取数据，并且完成数据的处理。每类设备控制器都是不同的，所以，需要不同的软件进行控制。专门与控制器对话，发出命令并接受响应的软件，称为设备驱动程序

实现输入和输出的方式有三种：忙等待、中断、直接存储器访问

4. 总线：系统中有很多总线，每条总线的传输速度和功能都不同

                                           第二章 进程管理

什么是进程/span>

狭义定义：进程本质上是正在执行的一个程序，程序一旦运行就是进程

广义定义：进程是具有独立功能的程序关于某个数据集合的一次运行过程。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。进程由程序、数据和进程控制块（PCB）三部分组成。

1. 进程的特征：

在某一个瞬间，CPU只能运行一个进程。但在1秒钟内，它可以运行多个进程，这样就产生并行的错觉。真正的CPU在各个进程之间来回切换，称为多道程序设计。

动态性：进程的实质是程序在多道程序系统中的一次执行过程，进程是动态产生，动态消亡的。

并发性：任何进程都可以同其他进程一起并发执行

独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；

异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进

2. 进程的三种基本状态

 

就绪状态：进程已获得除处理器外的所需资源，等待分配处理器资源，只要分配了处理器进程就可执行（可运行，但因为其他进程正在运行而暂时停止）

运行状态：进程占用处理器资源，处于此状态的进程的数目小于等于处理器的数目（该时刻进程实际占用CPU）

阻塞状态：由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行（除非某种外部事件发生，否则进程不能运行）

3. 进程的创建和终止

导致进程创建的事件：系统初始化；正在运行的程序执行了创建进程的系统调用；用户请求创建一个新进程；一个批处理作业的初始化

在UNIX系统中，只有一个系统调用可以用来创建新的进程：folk

导致进程终止的事件：正常退出（自愿的）；出错退出（自愿的）；严重错误（非自愿）；被其他进程杀死（非自愿）

什么是线程/span>

1. 定义：线程是进程的一个实体，是进程的一条执行路径

2. 线程同步的方式

互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。

信号量：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

事件（信号）：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

3. 多线程：指从软件或者硬件上实现多个线程的并发技术

优点：使用多线程可以把程序中占据时间长的任务放到后台去处理，如图片、视屏的下载；发挥多核处理器的优势，并发执行让系统运行的更快、更流畅，用户体验更好

缺点：大量的线程降低代码的可读性；更多的线程需要更多的内存空间；当多个线程对同一个资源出现争夺时候要注意线程安全的问题

4. 线程的状态：运行、阻塞、就绪、终止

什么是程序/span>

程序是为了实现一个特定的目标而设计的一组可操作的工作步骤，对于计算机而言，程序就是系统可以识别的一组有序的指令，能指挥计算机执行我们想要它做的动作。程序储存在磁盘上，在执行时从磁盘到内存再到寄存器，最后被CPU执行。

进程与线程的区别

进程本质上是正在执行的一个程序；线程是进程的一个实体，是进程的一条执行路径

1. 一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行；一个进程可包含多个线程，线程属于进程
2. 基本单位：进程是资源分配的基本单位，线程是CPU调度和分派的基本单位
3. 地址空间：进程拥有独立的地址空间，同一进程中的线程共享相同的地址空间
4. 健壮性：多进程比多线程程序要健壮。一个线程死掉整个进程就死掉了，但是在保护模式下，一个进程死掉对另一个进程没有直接影响

有了进程为什么还要线程

1. 使用线程可以减少程序的响应时间
2. 与进程相比，线程的创建和切换开销更小
3. 使用多线程能简化程序的结构，使程序便于理解和维护
4. 一个非常复杂的进程可以分成多个线程来执行

同步和互斥

进程（线程）之间的两种关系：同步与互斥

1. 区别：

所谓互斥，是指在不同进程之间的若干程序片断，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。

所谓同步，是指在不同进程之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。

2. 联系

同步是一种更为复杂的互斥，而互斥是一种特殊的同步。也就是说互斥是两个线程之间不可以同时运行，他们会相互排斥，必须等待一个线程运行完毕，另一个才能运行，而同步也是不能同时运行，但他是必须要安照某种次序来运行相应的线程（也是一种互斥）。

进程和程序的区别

1. 程序是永存的，是静态的，本身只是一组有序指令的集合，保存在硬盘上，除非手动删除掉，否则永远存在；进程是暂时的，是动态的，进程是程序在数据集上的一次执行，有创建有撤销，具备生命周期，存在是暂时的
2. 进程能并发执行，而程序不能并发执行
3. 进程和程序不是一一对应的：一个程序可对应多个进程；一个进程可以执行一个或几个程序

进程间通信（IPC Inter Process Communication）

1. 定义：是指在不同进程之间传播或交换信息
2. 进程间的通信方式：管道、消息队列、信号量、共享内存以及套接字

管道：管道可用于具有亲缘关系进程间的通信，有名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信；

消息队列：消息队列是消息的链接表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

信号量：主要作为进程间以及同一进程不同线程之间的同步手段。

共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。

套接口：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的，但现在一般可以移植到其它类Unix系统上：Linux和System V的变种都支持套接字。

管道

1. 管道，通常指无名管道，是UNIX系统IPC最古老的形式。

特点：它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。

它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。

它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。

2. 命名管道FIFO

特点：FIFO可以在无关的进程之间交换数据，与无名管道不同。

FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。

消息队列

消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。

特点：消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。

消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。

消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。

信号量

信号量是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

特点：信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。

信号量基于操作系统的PV操作，程序对信号量的操作都是原子操作。

每次对信号量的PV操作不仅限于对信号量值加1或减1，而且可以加减任意正整数。

支持信号量组。

共享内存

共享内存，指两个或多个进程共享一个给定的存储区。

特点：共享内存是最快的一种IPC，因为进程是直接对内存进行存取。

因为多个进程可以同时操作，所以需要进行同步。

信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

套接字

socket，即套接字是一种通信机制，凭借这种机制，客户/服务器（即要进行通信的进程）系统的开发工作既可以在本地单机上进行，也可以跨网络进行。也就是说它可以让不在同一台计算机但通过网络连接计算机上的进程进行通信。也因为这样，套接字明确地将客户端和服务器区分开来。

几种常见的操作系统调度策略

批处理系统中的调度

1. 先来先服务FCFS

先来先服务调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

2. 短作业(进程)优先

短作业(进程)优先调度算法，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

3. 最短剩余时间优先

使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。再次提醒，有关的运行时间必须提前掌握。当一个新的作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。

交互式系统中的调度

1. 时间片轮转法

一种最古老、最简单、最公平且使用最广的算法是轮转调度。每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。

2. 优先级调度

轮转调度做了一个隐含的假设，即所有的进程同等重要，而拥有和操作多用户计算机系统的人对此常有不同的看法。优先级调度的基本思想很清楚：每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。

实时系统中的调度

实时系统是一种时间起着主导作用的系统。典型地，一种或多种外部物理设备发给计算机一个服务请求，而计算机必须在一个确定的时间范围内恰当地做出反应。

实时系统通常可以分为硬实时（hard real time）和软实时（soft real time），前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。

实时系统的调度算法可以是静态或动态的。前者在系统开始运行之前作出调度决策；后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作，而动态调度算法不需要这些限制。

                                           第三章 内存管理

概述

内存（RAM）是计算机中一种需要认真管理的重要资源。

经过多年探索，人们提出了分层存储器体系（memory hierarchy）的概念，即在这个体系中，计算机有若干兆（MB）快速、昂贵且易失性的高速缓存（cache），数千兆（GB）速度与价格适中且同样易失性的内存，以及几兆兆（TB）低速、廉价、非易失性的磁盘存储，另外还有诸如DVD和USB等可移动存储装置。操作系统的工作是将这个存储体系抽象为一个有用的模型并管理这个抽象模型。

操作系统中管理分层存储器体系的部分称为存储管理器。它的任务是有效地管理内存，即记录哪些内存是正在使用的，哪些内存是空闲的；在进程需要时为其分配内存，在进程使用完后释放内存。

地址空间和交换技术

1. 地址空间

在最初系统中没有对内存的抽象，直接使用物理地址进行存储，这种方法会带来严重的问题：如果用户程序可以寻址内存的每个字节，它们就可以容易地破坏操作系统，从而使操作系统停止运行。想要同时运行多个程序很困难，因为使用物理地址很容易将数据覆盖。

要保证多个应用程序同时存在于内存并且不互相影响，要解决两个问题：保护和重定位。一个很好的解决方法是创造一个内存抽象：地址空间。地址空间为程序创造了一种抽象的内存，地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间(在特殊情况下想要共享除外)。

2. 内存超载

当所有要执行的进程所需要的内存大于计算机的物理内存时，就不能把所有进程一直保存在内存中。这种情况叫做内存超载。要想解决这种问题，有两种方法。

交换技术：即把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，就不会占用内存。

虚拟内存：可以使程序在只有一部分被调入内存的情况下运行。

虚拟内存

1. 一个进程是和其他进程共享CPU和主存的，但是主存的空间是有限的，当同时运行多个进程时，就会使内存不够用。这个时候，我们就引入了虚拟内存的概念，它是一种对主存的抽象的计算机内存管理技术。
2. 虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每个块称作一页或页面，每一页又连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存才能运行程序。当程序引用到一部分在物理内存的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
3. 虚拟内存机制的优缺点：

优点：可以弥补物理内存大小的不足；一定程度的提高反映速度；减少对物理内存的读取从而保护内存延长内存使用寿命；可在较小的可用内存中执行较大的用户程序；可在内存中容纳更多程序并发执行；不必影响编程时的程序结构（与覆盖技术比较）

缺点：占用一定的物理硬盘空间；加大了对硬盘的读写；设置不得当会影响整机稳定性与速度

虚拟内存和物理内存

1. 用户编制程序时使用的地址称为虚地址或逻辑地址，其对应的存储空间称为虚存空间或逻辑地址空间

    计算机物理内存的访问地址则称为实地址或物理地址，其对应的存储空间称为物理存储空间或主存空间

2. 物理内存：在应用中，真实存在的，插在主板内存槽上的内存条的容量的大小。从本质上来说，物理内存是代码和数据在其中运行的窗口。

    虚拟内存：使程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

   若计算机运行程序或操作所需的随机存储器(RAM)不足时，则Windows会用虚拟存储器进行补偿，即拿出一部分硬盘空间来充当内存使用，这部分空间即称为虚拟内存，虚拟内存在硬盘上的存在形式就是PAGEFILE.SYS这个页面文件。它将计算机的RAM和硬盘上的临时空间组合。将数据移入分页文件可释放RAM，以便完成工作。

   若计算机的速率由于RAM可用空间匮乏而减缓，则可尝试通过增加虚拟内存来进行补偿。但是，计算机从RAM读取数据的速率要比从硬盘读取数据的速率快，因而扩增RAM容量（可加内存条）是最佳选择。

内存的分页机制

实际上存储在物理内存上（磁盘上），运行时一页一页读取

1. 基本思想：用户程序的地址空间（虚拟地址空间）被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
2. 逻辑地址：系统将程序的逻辑空间按照同样大小也划分成若干页面，称为逻辑页面也称为页。程序的各个逻辑页面从0开始依次编号，称作逻辑页号或相对页号。每个页面内从0开始编址，称为页内地址。程序中的逻辑地址由两部分组成：页号P和页内位移量W。

        若给定一个逻辑地址为A，页面大小为L，则页号P=INT[A/L]，页内地址W=A MOD L

1. 页表：分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，为了能在内存中找到每个页面对应的物理块，系统为每个进程建立一张页表，用于记录进程逻辑页面与内存物理页面之间的对应关系。页表的作用是实现从页号到物理块号的地址映射，地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排列
2. 缺页中断：进程线性地址空间里的页面不必常驻内存，在执行一条指令时，如果发现他要访问的页没有在内存中（即存在位为0），那么停止该指令的执行，并产生一个页不存在的异常，对应的故障处理程序可通过从外存加载该页的方法来排除故障，之后，原先引起的异常的指令就可以继续执行，而不再产生异常。

分页和分段的区别

1. 段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。
2. 段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定
3. 段向用户提供二维地址空间；页向用户提供的是一维地址空间
4. 段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

页面置换算法

程序运行过程中，有时要访问的页面不在内存中，而需要将其调入内存。但是内存已经无空闲空间存储页面，为保证程序正常运行，系统必须从内存中调出一页程序或数据送到磁盘对换区，此时需要一定的算法来决定到底需要调出那个页面。通常将这种算法称为“页面置换算法”。

1. 最佳置换算法（OPT）（理想置换算法）

实现原理：每次选择未来长时间不被访问的或者以后永不使用的页面进行淘汰。从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。即被淘汰页面是以后永不使用或最长时间内不再访问的页面。

优点：最佳置换算法可以保证获得最低的缺页率

缺点：最佳置换算法是一种理想化算法，具有较好的性能，但是实际上无法实现（无法预知一个进程中的若干页面哪一个最长时间不被访问）

2. 最近未使用算法（NRU）

实现原理：为使操作系统能够收集有用的统计信息，在大部分具有虚拟内存的计算机中，系统为每一页面设置了两个状态位。当页面被访问（读或写）时设置访问位R位；当页面（即修改页面）被写入时设置修改位M位。用R位和M位来构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都由操作系统设置成0，R位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：

第0类：没有被访问，没有被修改 00

第1类：没有被访问，已被修改   01

第2类：已被访问，没有被修改   10

第3类：已被访问，已被修改     11

NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰之。这个算法隐含的意思是，在最近一个时钟滴答中（典型的时间是大约20ms）淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面好。

优点：易于理解和能够有效地被实现，虽然它的性能不是最好的，但是已经够用了

3. 先进先出置换算法（FIFO）

实现原理：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。 即优先淘汰最早进入内存的页面。

优点：先进先出算法实现简单，是最直观的一个算法

缺点：先进先出的性能最差，因为与通常页面的使用规则不符合，所以实际应用少

4. 第二次页面置换算法

实现原理：FIFO算法可能会把经常使用的页面置换出去，为避免该问题，对该算法做一个简单的修改：检查最老页面的R位。如果R位是0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续搜索。

5. 时钟页面置换算法

实现原理：尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。

6. 最近最少未使用置换算法（LRU）

实现原理：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。即淘汰最近最长时间未访问过的页面。

内存的分段机制

段式管理的基本思想是：把程序按内容或过程（函数）关系分成段，每个段有自己的名字（编号）。

在程序员眼中的程序是分为很多段的，每一段都有不同的特点。适用于不同的领域。每一段都是从该段的地址0开始的。就是说主程序存放的地方地址应该是从零开始的，变量存放的地方地址也应该是从零开始的，其他区域也是如此。用户程序里面每个区域都有其自己的特点，比如主程序这部分应该是只读的，变量所在的区域是可写的，函数库应该是可以可以链接也可以不链接的，栈应该只能单向增加。如果是将整个程序都放在一块的话这些要求肯定不能保证。因此程序应该是要分段保存的，并且这些段都有自己的特点。

既然是分段的，那么是怎么定义地址的呢是基址+偏移。只不过这里的基址不再是这个程序的起始位置了，而是这一段程序的起始地址。这个基址放在段表里面

 

CPU每执行一条牵涉到地址的指令都会查一下PCB里面这个进程段表，从而确定物理地址。这个表其实就是LDT表，有一个专门存放该表地址的寄存器LDTR寄存器。到目前为止内存已经可以使用起来了。因为地址已经设定好了。

内存分区

1. 固定分区

操作系统初始化的时候将内存等分为n个分区，大小一样。但是程序运行的时候内存的需求有大有小，如果采用这种方式势必会造成很大的浪费。

2. 可变分区

可变分区的基本思想是建立已分配分区表和空闲分区表，已分配分区表中记录了已经使用了的内存有哪些，注明了这一段内存是哪个程序使用了，起始地址和长度是多少。空闲分区表记录了内存中的空闲区域，包括起始地址和长度。这时候如果有段内存请求，根据请求的内存大小以及空闲分区表上面空闲分区的大小来给这个请求分配内存，同时更新这两张表；如果有进程运行完了也同样更新这两张表。这样做的好处是：可以给需要大内存的程序分配大块内存，给需要小内存的程序分配小内存，提高内存利用率。

3. 可变分区的三种适配方式

比如有一个请求需要40K内存，空闲分区表里面有很多个大于40K的内存区域，应该选择哪一个分配呢/p>

首次适配：顾名思义，就是将第一个符合该请求的内存分配出去。这样的好处是：快

下次适配：分配时，从上次扫描结束处继续查找，从第一个满足要求的空闲去中分配

最佳适配：把所有的空闲内存块都看一遍，将最接近40K并且大于40K的内存分配给它。这样的好处是可以可以提高内存的使用率

最差适配来源：殊彦Hiroyuki