操作系统复习

五月 21, 2021 11779

计算机操作系统

本文参考JavaGuide

一、操作系统基础

1.1 什么是操作系统？

  • 操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
  • 操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬件和软件资源。 举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。
  • 操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。
  • 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。 内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

1.2 系统调用

根据进程访问资源的特点，我们可以把进程在系统上的运行分为两个级别：

  • 用户态(user mode) : 用户态运行的进程可以直接读取用户程序的数据。
  • 内核态(kernel mode)：系统态，管态。可以简单的理解内核态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。特权指令比如I/O指令、清内存、设置时钟指令等只能在内核态由操作系统内核执行。用户态可以通过系统调用、异常、外围设备中断3种方式切换到内核态。

用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。也就是说，用户程序如果需要调用操作系统提供的内核态级别的子功能，就需要系统调用。

系统调用按功能大致可分为如下几类：

  • 设备管理。完成设备的请求或释放，以及设备启动等功能。
  • 文件管理。完成文件的读、写、创建及删除等功能。
  • 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
  • 进程通信。完成进程之间的消息传递或信号传递等功能。
  • 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

二、进程与线程

2.1 进程和线程的区别

进程

进程是一段程序的执行过程，是计算机资源分配的基本单位，进程是程序的基本执行实体。同时进程拥有自己的进程控制块，系统可以利用这个进程的控制块(PCB)来控制对应的进程。

线程

线程是操作系统进行调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

线程和进程的比较

  • 调度：线程是独立调度的基本单位，进程是资源分配的基本单位。
  • 拥有资源：进程是拥有资源的基本单位，而线程则不拥有系统的资源，但是线程可以访问其所属进程的资源。
  • 系统开销：系统创建和回收进程是需要对进程进行资源回收的。因此创建和回收进程的损耗要大于创建和回收线程的损耗。
  • 地址空间和其他资源：进程间各自的地址空间是独立的，线程间的地址空间是共享的。
  • 通信方面：进程间通信主要通过进程同步和互斥手段，而线程间可以直接读写进程数据段（如全局变量）进行通信。

程序：程序是一组指令的集合，是静态的代码。

JVM中，多个线程共享进程的堆和方法区，每个线程有自己的程序计数器、虚拟机栈、本地方法栈。参考Java中程序、进程、线程的区别

2.2 协程和管程

协程

协程（Coroutine）是用户级别的轻量级线程。一个线程可以包含多个协程，可以对比一个进程包含多个线程。协程运行在线程之上，当一个协程执行完成后，可以选择主动让出，让另一个协程运行在当前线程之上。协程并没有增加线程数量，只是在线程的基础之上通过分时复用的方式运行多个协程。协程相对独立，有自己的上下文，协程的切换由程序员控制，在用户态执行，切换的代价比线程从用户态到内核态的代价小很多。

纤程(Fiber)与协程类似，是Windows操作系统实现的一种轻量化线程上的一个执行结构，是Windows上的协程，通常多个fiber共享一个固定的线程, 然后他们通过互相主动切换到其他fiber来交出线程的执行权， 各个子任务之间的关系非常强。

管程

管程（Monitor）在功能上和信号量及PV操作类似，属于一种进程同步互斥工具，但是具有与信号量及PV操作不同的属性。

一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构。

管程很像一个类，将共享资源封装起来，并且，如果想要访问资源的话，只能通过类里面的方法来进行访问。同时，每次只允许一个进程进入管程，从而实现互斥，

管程的提出是为了更好的解决同步和互斥的问题。进程对共享资源的申请，释放等操作，都通过管程定义的过程来实现。这个过程还可以根据资源的情况，或接受或者阻塞进程访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，从而实现进程互斥。

2.3 进程的生命周期

进程大致分为 5 种状态，和线程类似：

  • 创建状态(new) ：进程正在被创建，尚未到就绪状态。
  • 就绪状态(ready) ：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。
  • 运行状态(running) ：进程正在处理器上上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。
  • 阻塞状态(waiting) ：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
  • 结束状态(terminated) ：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

进程的3种基本状态

2.4 进程通信/同步方式：

每个进程都有各自的用户地址空间，进程之间交换数据必须通过内核中的缓冲区，这种机制称为进程间通信IPC（InterProcess Communication），IPC有以下几种方式，参考进程间通信：

  • 共享内存(Shared memory) ：使得多个进程共享一块内存，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。是速度最快的IPC方式。

  • 管道/匿名管道(Pipes) ：先进先出，只能具有亲缘关系的父子进程间或者兄弟进程之间的通信。

    管道只存在于内存中的文件，实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据。管道只支持单向数据流，只能用于具有亲缘关系的进程之间，没有名字，且缓冲区是有限的，传送的是无格式字节流，必须事先约定数据格式。

  • 命名管道(Names Pipes) : 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了命名管道。命名管道严格遵循先进先出(first in first out)。命名管道名字存放在文件系统中，内容存放在内存中，可以实现本机任意两个进程通信。

    命名管道提供了一个路径名与之关联，以命名管道的文件形式存在于文件系统中，这样，即使与命名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过命名管道相互通信，因此，不相关的进程通过命名管道也能交换数据。

  • 消息队列(Message Queuing) ：消息队列是消息的链表，具有特定的格式，存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道不同的是消息队列存放在内核中，只有在内核重启(即操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取,也可以按消息的类型读取，比 FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺陷。

  • 套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。

  • 信号量(Semaphores) ：信号量是一个计数器，用于多进程对共享数据的访问，取值为非负整数，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。

    信号量用于同步，互斥量用于互斥。多数情况下，同步已经实现了互斥。

    进程为了获取共享资源，需要执行三个操作，都是原子操作，在内核中实现：

    ①创建信号量

    ②等待信号量，即P操作

    ③释放信号量，即V操作

  • 信号(Signal) ：信号用于通知接收进程某个事件已经发生，是Linux系统用于进程间通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。比如程序终止信号SIGING、程序退出信号SIGQUIT等。

2.5 线程通信/同步方式：

操作系统中，有三种线程同步的方式：

  • 互斥量（Mutex）：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
  • 信号量（Semphares）：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
  • 事件（Event）：使用通知操作的方式来保持多线程同步，比如Java中的wait()、notify()、notifyAll()方法。

互斥量的加锁和解锁必须由同一个线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。

2.6 进程的调度算法

进程调度算法是为了确定首先执行哪个进程以及最后执行哪个进程来实现最大CPU利用率，包括以下几种：

  • 先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。

  • 短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。

  • 时间片轮转调度算法 : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。

  • 多级反馈队列调度算法 ：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。

  • 优先级调度 ： 为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

  • 基于公平原则的调度算法

2.7 死锁

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象。

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的(Deadlock)。

产生死锁的四大必要条件：

  • 互斥访问：资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止。
  • 不可抢占：资源不能被抢占。只能在持有资源的进程完成任务后，该资源才会被释放。
  • 请求和保持：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
  • 循环等待：有一组等待进程 {P0, P1,..., Pn}， P0 等待的资源被 P1 占有，P1 等待的资源被 P2 占有，……，Pn-1 等待的资源被 Pn 占有，Pn 等待的资源被 P0 占有。

以上条件必须同时满足才会造成死锁。

进程死锁和线程死锁满足的条件是一致的，只是死锁的资源分别是进程和线程。

2.8 死锁处理

死锁的处理包括死锁预防、死锁避免、死锁检测、死锁解除四种方法。

死锁预防：

只有四个条件同时满足才会产生死锁，预防死锁的方法对应就是破坏四大必要条件，由于互斥条件是非共享设备所必须的，不仅不能改变，还应该加以保持，因此主要是破坏另外三个条件：

  • 破坏“不可抢占性”条件：当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源

  • 破坏“请求和保持”条件：一次性分配进程在整个运行过程中所需的全部资源，破坏了“请求”的条件。分配资源时，只要有一个资源得不到分配，就不给这个进程分配其他的资源，让其等待，破坏了“保持”的条件。

  • 破坏“循环等待”条件：给每类资源赋予一个编号，并规定每一个进程必须按编号递增的顺序请求资源，释放则相反。

    这种方式与前两种相比，资源利用率和系统吞吐量都有较明显的改善。但也存在下述问题:

    首先，为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加。

    其次，尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。

    第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少，然而这种按规定次序申请资源的方法必然会限制用户简单、自主地编程。

死锁避免：

死锁避免方法中，把系统状态分为安全状态和不安全状态。系统处于安全状态时可避免发生死锁，反之，系统处于不安全状态时，可能进入死锁状态。

安全状态指系统能按某种进程推进顺序 (P_1,P_2,...,P_n) 为每个进程 P_i 分配其所需资源，直至满足每个进程对资源的最大需求，是每个进程都可以顺利完成。如果系统无法找到这样的安全序列，则处于不安全状态，有可能发生死锁。

避免死锁应该在资源分配时，使系统不进入不安全状态。

具体方法有：

  • 银行家算法。每个新进程进入系统时，必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。

死锁检测：Java中可以使用JConsole、JStack工具检测死锁

死锁解除：常采用解除死锁的两种方法为抢占资源和终止进程法。

  • 抢占资源：从一个或多个进程中抢占足够数量的资源，分配个死锁进程，以解除死锁状态。
  • 终止(或撤销)进程法：终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。

三、内存管理

计算机存储系统

3.1 内存管理介绍

内存管理的工作主要是内存的空间分配和回收（malloc和free）、地址转换（将逻辑地址转换成相应的物理地址）、内存空间的扩充、存储保护。

3.2 内存管理机制

内存管理主要有连续分配管理方式和非连续分配管理方式两种

  • 连续分配主要指为一个用户程序分配一个连续的内存空间，连续分配的方式包括单一连续分配、固定分区分配、动态分区分配。

    • 单一连续分配，只用于单用户单进程的操作系统，
    • 固定分区分配，其将内存划分为多个固定大小的分区，当有空闲分区的时候，再从后续的作业队列中选择合适大小的作业装入。
    • 动态分区分配，OS根据程序需要，分给每个程序所需要的内存大小，但会出现内存碎片的问题。通常需要采用紧凑技术进行解决。可变分区的分配策略有以下几种：
      • 首次适应算法，空闲分区以地址递增次序连接，找到大小能满足要求的第一个分区。
      • 循环首次适应算法，与首次适应类似，只不过每次都从上一次的位置开始查找。
      • 最佳适应算法，空闲分区按容量递增次序连接，找到第一个能满足要求的空闲分区。
      • 最坏适应算法，空闲分区以容量递减次序连接，挑选第一个最大的分区。

    连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销 ，因此产生了非连续分配方式。

  • 非连续分配允许一个程序使用的内存分布在离散或者说不相邻的内存中，主要包括分页式存储管理、分段式存储管理、段页式存储管理三种方式：

    • 分页式存储管理：主要将内存划分成大小固定的页面，在程序申请内存的时候，分配适合大小的页面。这种方式可以有效减少内存的碎片，同时不需要数据连续存放。同时内存中会维护一张页表，用于对内存地址进行转换。作业的逻辑地址：页号+页内偏移。
    • 分段式存储管理：页式管理其中的页实际并无任何实际意义，而将内存分段中的每一段是有实际意义的。段式管理主要是从用户的角度出发，按照程序的自然段划分为逻辑空间。同样内存中会维护一张段表，每个段表项对应内存中的一段。内存地址借助于段表寄存器进行转换，作业的逻辑地址为：段号+段内偏移
    • 段页式存储管理：结合了上述两种方法的优点，首先会对作业进行分段，分段之后再保存到对应的每个页中。内存管理仍然和分页式存储一致。作业的逻辑地址分为三部分：段号+页号+逻辑地址。

3.3 快表和多级页表

在分页内存管理中，有两个问题需要解决：

  • 保证虚拟地址到物理地址的转换速度要快。
  • 解决虚拟地址空间大，页表也会很大的问题。

为了提高内存的空间性能，提出了多级页表的概念；但是提高空间性能是以浪费时间性能为基础的，因此为了补充损失的时间性能，提出了快表（即 TLB）的概念。 不论是快表还是多级页表实际上都利用到了程序的局部性原理。

快表

快表为了提高虚拟地址到物理地址转换速度。操作系统在页表方案基础之上，引入了快表加速虚拟地址到物理地址的转换。

可以把快表理解为一种特殊的高速缓存，其中的内容是页表的一部分或者全部内容。作为页表的Cache，它的作用与页表相似，但是提高了访问速率。由于使用页表做地址转换，读写内存数据时CPU要访问两次主存（第一次访问存放在主存（属于内存）的页表，第二次访问主存中指定的地址）。有了快表，有时只需要访问一次缓存，一次主存，这样可以加速查找并提高指令执行速度。

使用快表的地址转换流程：

  1. 根据虚拟地址中的页号查快表；
  2. 如果该页在快表中，直接从快表中读取相应的物理地址；
  3. 如果该页不在快表中，就访问内存中的页表，从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
  4. 当快表填满后，又要登记新页时，按照一定的淘汰策略淘汰掉快表中的一个页。

多级页表

引入多级页表的目的是为了避免把全部表页一直放在内存中占用过多空间，特别是那些根本不需要的页表，不需要保留在内存中。多级页表属于时间换空间的典型场景。参考多级页表如何节约内存

3.4 分页机制和分段机制对比

共同点：

  • 分页机制和分段机制都是为了提高内存利用率，减少内存碎片。
  • 页和段都是离散存储的，所以两者都是离散分配内存的方式，但是每个页和段中的内存是连续的。

区别：

  • 页的大小是固定的，由操作系统决定；段的大小不固定，取决于当前运行的程序。
  • 页是信息的物理单位，分页仅仅是为了满足操作系统内存管理的需求；段是逻辑信息的单位，在程序中可以体现为代码段、数据段，能够更好地满足用户的需要。

3.5 逻辑(虚拟)地址和物理地址

逻辑地址由操作系统决定，是访问指令给出的地址，比如C语言里的指针，可以理解为内存里的一个地址。逻辑地址需要经过寻址方式的计算或变换才得到物理地址。

物理地址指的是真实物理内存中的地址，即内存地址寄存器中的地址，物理地址是内存单元真正的地址。

3.6 CPU寻址？为什么需要虚拟地址空间？

CPU寻址

现代处理器使用的是一种称为虚拟寻址(Virtual Addressing)的寻址方式。使用虚拟寻址，CPU需要将虚拟地址转换为物理地址，这样才能访问到真实物理内存。CPU中称为内存管理单元(Memory Management Unit,MMU)的硬件用于将虚拟地址转换物理地址。如下图所示：

为什么要有虚拟地址空间？

如果没有虚拟地址空间，直接访问和操作物理内存，这样直接把物理地址暴露出来会带来严重问题，可能对操作系统造成伤害以及给同时运行多个程序造成困难：

  • 用户程序可以访问任意内存，寻址内存的每个字节，容易破坏操作系统，造成操作系统崩溃。
  • 如果同时运行多个程序，两个程序都可以对同一个地址上的数据进行修改，造成应用程序崩溃。

使用虚拟地址访问内存的优势：

  • 程序可以使用相邻的虚拟地址访问物理内存中不相邻的大内存缓冲区。
  • 程序可以使用虚拟地址访问大于可用物理内存的内存缓冲区（使用硬盘空间扩展内存），实际物理内存不变，让程序认为其独占内存。当物理内存供应量变小时，内存管理器将物理内存页保存到磁盘。程序运行时，数据和代码页会根据情况在物理内存和磁盘移动（比如从磁盘读取到内存中，长时间不用又会被保存到磁盘），按需缓存，只在主存中缓存活动区域。
  • 不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

四、虚拟内存

4.1 什么是虚拟内存(Virtual Memory)？

虚拟内存使得应用程序认为它拥有连续的可用内存(一个连续完整的地址空间)，而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。使用虚拟内存技术的系统使得大型程序的编写变得更容易，对真正的物理内存的使用也更有效率。

虚拟内存不仅仅是“使用硬盘空间扩展内存”这么简单，其重要意义在于虚拟内存定义了一个连续的虚拟地址空间，使程序的编写难度降。并且，把内存扩展到硬盘空间只是使用虚拟内存的必然结果，虚拟内存空间会存在硬盘中，并且会根据需要被内存缓存，有的操作系统还会在内存不够的情况下，将某一进程的内存全部放入硬盘空间中，并在切换到该进程时再从硬盘读取（这也是为什么Windows会经常假死的原因）。

虚拟内存的意义：

  • 它把主存看作为一个存储在硬盘上的虚拟地址空间的高速缓存，并且只在主存中缓存活动区域（按需缓存）。
  • 它为每个进程提供了一个一致的地址空间，从而降低了程序员对内存管理的复杂性
  • 它还保护了每个进程的地址空间不会被其他进程破坏。

4.2 局部性原理

局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。

局部性原理体现在两个方面：

  • 时间局部性：如果程序中的某条指令一旦执行，不久后该指令可能再次执行；如果某数据被访问过，不久后该数据可能再次被访问。产生时间局部性的原因，是因为程序中存在大量的循环操作。
  • 空间局部性：一旦程序访问了某个存储单元，不久后其附近的存储单元也将被访问，即程序在一段时间内访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表的形式存储的。

时间局部性通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。

空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。

虚拟内存技术实际上就是建立了“内存-外存”的两级存储器的结构，利用局部性原理实现高速缓存。

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其他部分留在外存，就可以启动程序执行。由于外存往往比内存大很多，所以我们运行的软件的内存大小实际上可以比系统实际内存大小大的。

程序执行过程中，当所访问的信息不在内存中时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。这样计算机好像为用户提供了一个比实际内存大得多的存储器，即虚拟存储器（虚拟内存）

4.3 虚拟内存的技术实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。实现方式有三种：

  • 请求分页存储管理。建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
  • 请求分段存储管理。建立在分段存储管理之上，增加了请求调段、分段置换功能。请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
  • 请求段页式存储管理

请求分页存储管理和分页存储管理的不同：请求分页是建立在分页管理之上的，根本区别是是否将作业的全部地址空间同时装入主存，请求分页存储管理不要求将作业全部地址空间同时装入主存，因此请求分页存储管理可以提供虚拟内存，而分页存储管理则不能。

请求分页和分页的实现都需要具备以下条件：

①一定容量的内存和外存，载入程序时，只需要将程序的一部分装入内存，将其他部分留在外存，然后程序就可以执行了。

②缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序。

③虚拟地址空间：逻辑地址到物理地址的变换。

4.4 页面置换算法

当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统必须在内存中选择一个页面将其移出内存，以便为即将调入的页面让出空间。页面置换算法就是用来选择淘汰哪一页，主要有以下几种算法：

  • OPT算法（最佳页面置换算法，Optimal,OPT)：选择被淘汰的页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，可以保证获得最低的缺页率。但是由于人们无法预知一个页面多长时间不再被访问，因此该算法无法实现，一般作为衡量其他置换算法的方法。

  • FIFO算法（先进先出页面置换算法，First In First Out）：淘汰最先进入的页面，即选择内存中驻留时间最久的页面淘汰。该算法实现简单，但会将那些经常被访问的页面也被换出，从而使缺页率升高。

    FIFO算法还会产生当分配的物理块数增大而缺页率不减反增的异常现象，称为Belady异常。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会。

  • LRU算法（最近最久未使用页面置换算法，Least Currently Used）：LRU 淘汰最近最久未使用的页面，其思想是过去一段时间内未使用的页面，在最近的将来也不会被访问。有两种实现方式：

    • 方式一：在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
    • 方式二：为每个页面设置一个访问字段，记录页面自上次被访问以来所经历的时间T，淘汰页面时将现有页面中T值最大的页面淘汰。

    LRU性能较好，但需要寄存器和栈的硬件支持，LRU是堆栈类的算法，理论上可以证明，堆栈类算法不可能出现Belady异常，FIFO算法基于队列实现，不是堆栈类算法。

    LRU算法题

  • LFU（最少使用页面置换算法，Least Frequently Used）：选择最近时期使用最少的页面进行淘汰。

    LFU算法题

  • Clock算法（时钟置换算法，或最近未用算法NRU）：LRU的一种近似算法。简单Clock 算法，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出;若为1，则重新将它置0，暂不换出，给予该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为 1，则再返回到队首去检查第一个页面。进阶的Clock算法需要考虑置换代价。

    由于该算法是循环地检查各页面的使用情况，故称为Clock算法。但因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法或NRU(Not Recently Used)算法。

查看评论