《操作系统概念》+《王道》笔记（二）

内存管理策略

基础概念

每个进程的合法内存地址可以通过基地址寄存器和界限地址寄存器来确定

基地址寄存器确定最小的合法物理内存地址，界限地址寄存器指定了范围的大小

只有操作系统可以通过在内核模式下执行特殊的特权指令，才能加修改这两个寄存器的值，而不允许用户程序修改它们

指令和数据绑定到存储器地址可以在程序从源代码到执行的沿途任何一步进行

CPU生成的地址通常称为逻辑地址（虚拟地址）

加载到内存地址寄存器的地址称为物理地址

从虚拟地址到物理地址的运行时映射是由内存管理单元(MMU)的硬件设备来完成

动态加载：一个程序只有在调用时才会加载，所有程序都以可重定位加载格式保存在磁盘上

动态链接库：常用于系统库，每个库程序的引用都有一个存根。存根是一小段代码，用来指出如何定位适当的内存驻留库程序，或者在程序不在内存内时应如何加载库。当执行存根时，它首先检查所需程序是否已在内存中，如果不在，就将程序加到内存。存根会有程序地址来替换自己，并开始执行程序

交换

系统维护一个可运行的所有进程的就绪队列，它们的映像在备份存储或内存中

如果分配器发现队列的下一个要执行的进程不在内存中，就会换出当前内存的一个进程，并换入所需内存

上述方法称为标准交换

现代操作系统事实上使用的是该交换的变种

变种一：正常情况下，禁止交换；当空闲内存抵御某个阈值时，启用交换。当空闲的内存数量增加，停止交换

变种二：只交换进程的一部分，以降低交换时间，这种变种通常与虚拟内存一起工作

连续内存分配

在采用连续内存分配时，每个进程位于一个连续的内存区域，与包含下一个进程的内存相连

多分区方法

将内存分为多个固定大小的分区，每个分区可以只包含一个进程

可变分区方案

该方案中操作系统有一个表，用于记录哪些内存可用和哪些内存已用

开始，所有内存都可以用于用户进程，因此可以作为一大块的可用内存，称为孔

可用的内存块为分散在内存里的不同大小的孔的集合，当新进程需要内存时，系统为该进程查找足够大的孔。如果孔太大，那么就分成两块：一块分配给新进程，另一块还回到孔集合

当进程终止时，它将释放内存，该内存将还给孔的集合。如果新的孔与其他孔相邻，那么将这些孔合并成大孔

从一组可用孔中选择一个空闲孔有如下方法

首次适应：分配首个足够大的孔，通常将空闲区按地址从小到大次序登记在空闲表。
最优适应：分配最小的足够大的孔，这种方法可用产生最小剩余孔，通常将空闲区按长度递增顺序次序登记在空闲表。

空闲区按长度递增的次序登记在空闲表中
最差适应：分配最大的孔，这种方法可以产生最大剩余孔，通常将空闲区按长度递减顺序次序登记在空闲表

模拟结果显示，首次适应和最优适应在执行时间和利用空间方面都好于最差适应

碎片

外部碎片：空闲内存空间被分为小的片段，总的可用内存之和可以满足请求但不连续，进程之间有被浪费的块

采用首次适应方法的统计说明，不管怎么优化，假定有N个可分配块，那么可能有0.5N个块为外部碎片，这一特性称为50%规则

内部碎片：进程所分配的内存比所需的要大，但剩下的孔需要很大开销来维护，此时按固定大小的块来分配内存。而剩余的内存部分在分区内部，但不能用

解决外部碎片的方法是紧缩

而另一种方法则是运行逻辑地址空间不连续，利用分段和分页技术

分段

分段是支持用户视图的内存管理方案，每个段都有名称和长度。地址制定了段名称和段内偏移，所有用户通过段名称和段偏移来指定地址

逻辑地址由有序对组成：$<段号，偏移>$

实际物理内存是一维的字节序列，需要通过段表来讲用户定义的二位地址映射到一维地址

段表的每个条目都有段基地址和段界限

逻辑地址由段号s和段偏移d组成，段号s用作段表的索引，段偏移d应位于0和段界限之间

分段管理不会产生内部碎片

分页

分页是另一种允许进程物理地址空间非连续的方案，但是其避免了外部碎片和紧缩

分页将物理内存分为固定大小的块，称为帧或页帧，而逻辑内存也分为同样大小的块，称为页和页面

虚拟地址分为两部分：页码和页偏移，页码作为页表的索引

从页表中查询到页的物理内存的基地址，再与页偏移组合便形成了物理内存地址

如果逻辑地址空间为$2^m$，且页大小为$2^n$字节，那么逻辑地址的高m-n位表示页码。低n位表示页偏移

分页本身是一种动态的重定位

虽然分页不会产生外部碎片，但是分页有内部碎片

另外，操作系统负责管理物理内存，所以它会维护一个称为帧表的数据结构，其中每个条目对应着一个帧，以表示该帧是空闲还是占用，以及被哪个进程的哪个页占用

现代计算机系统将页表存在内存中，并将页表基地址寄存器指向页表

TLB

TLB为转换表缓冲区的简称，当关联内存根据给定值查找时，它会同时与所有的键进行比较，如果找到条目，就能得到相应值的字段，搜索速度很快。

TLB中只包含少数的页表条目

如果页码不在TLB（TLB未命中），那么就需要访问页表，将页码和帧码添加到TLB，方便下次再用时很快地查到

在TLB中查找到感兴趣页码的次数的百分比称为命中率

保护

与每个帧关联的保护位用于定义一个页时可读可写或只可读

另一个信息位为有效-无效位，其表示相关的页是否在进程的逻辑地址空间中

共享页

如果代码是可重入代码或纯代码，我们就可以共享其分页

可重入代码时不能自我修改的代码：它在执行期间不会改变

如果共享了代码的分页，那么在物理内存中只需保存一个该代码的副本，每个用户的页表映射到到该代码的同一副本，而不同用户间其他不同的数据则映射到不同的帧

页表结构

大多数现代计算机系统的页表本身可以非常大，此时我们需要将页表划分为更小的块

分层分页

一种方法是使用分层页表

例如下面的两层分页算法

这种方案也称为向前映射页表

p1是用来访问外部页表的索引，p2是内部页表的页偏移

但是对于64位的架构，过多的分层会导致过多的内存访问，使用分层页表并不适当

哈希页表

大于32位地址空间的常用方法是哈希页表

哈希页表的每一条目都包括一个链表，同一链表的元素的虚拟页码的哈希值相同，每一格链表元素包含三个字段：虚拟页码、映射的帧码、指向链表内下一个元素的指针

哈希页表的索引为哈希值

逻辑地址中的虚拟页码计算哈希值后用来与哈希表的索引对比，找到对应链表后使用虚拟页码与链表第一个元素的第一个字段比较，如果匹配，则第二个字段的帧码被用来形成物理地址；如果不匹配，则与链表的下一个节点进行比较

该方案的一个变体采用聚簇页表，不同之处在于其哈希表中每个条目引用多个页，对于稀疏地址空间特别有用

倒置页表

通常每个进程都有一个关联页表

但倒置页表的方案中，整个系统只有一个页表，该页表中仅为每个真正的内存页或帧保存一个条目。每个条目包含在真正内存位置上页的虚拟地址，以及拥有该页的进程的信息

每个倒置页表的条目为二元组：$<进程id，页码>$

而虚拟地址为三元组：$<进程id，页码，偏移>$

当匹配到页表中的条目$i$，$i$则被用于生成物理地址

这种方案增加了由于引用页面查找页表所需的时间

虚拟内存管理

操作系统的一个基本要求是执行的指令应处于物理内存

作业在运行前，不必全部装入内存，且在运行过程中也不必一直驻留内存

虚拟内存使得程序员不再需要担心有限的物理内存空间，只需要关注所要解决的问题

进程的虚拟地址空间就是进程如何在内存中存放的逻辑

包括空白的虚拟地址空间称为稀疏地址空间

虚拟内存除了将逻辑内存与物理内存分开，还允许文件和内存通过共享页面为多个进程所共享

逻辑内存（Logical Memory）

定义：逻辑内存通常指的是程序视角下的内存布局，它是程序员在编写程序时看到的内存结构。
作用：逻辑内存为程序员提供了一个简化的、连续的内存视图，使得程序开发更为简单。

请求调页

基本概念

仅在需要时才加载页面，这种技术被称为请求调页

在请求调页系统中，当进程需要执行时它被交换到内存中，不过只会交换需要的页面，即采用惰性交换器，这里的惰性交换器特指调页程序

当换入进程时，调页程序会猜测在该进程被再次换出前会用到哪些页，从而避免读入那些不使用的页

为了区别内存的页面和磁盘的页面，我们可以在页表添加一个有效-无效位

当试图访问标记位位无效的页面时，会发生缺页错误

纯请求调页：一开始不进行预测，而是通过缺页错误将所有需要的页面调入内存

外存（或辅助存储）用于保存不在内存中的那些页面。外存通常为高速硬盘，称为交换设备，用于交换的这部分磁盘称为交换空间

性能

有效访问时间很大程度上决定了请求调页的性能

$有效访问时间=(1-p)\times ma+p\times 缺页错误时间$

其中$p$为缺页错误的概率，$ma$为内存访问时间

缺页错误的处理时间有三个主要组成部分：

处理缺页错误中断
读入页面
重新启动程序

写时复制

写时复制允许父进程和子进程最初共享相同的页面来工作，这些共享页面标记为写时复制

当任何进程写入共享页面时，就创建共享页面的副本

写时复制这种技术提供了快速的进程创建，并最小化了必须分配给新创建进程的新页面的数量

页面置换

基本页面置换

当我们使用请求调页时，增加了多道程度，即能允许更多进程

但也可能会过度分配内存，例如某个进程突然试图使用其所有页面

最常见的解决方案即页面置换

采用修改位（脏位）可以减少缺页错误处理时间。每当页面内的任何字节被写入时，它的修改位就会被设置，此时如果该页面要被换出，应将页面写入磁盘；如果修改位未被设置，那么说明页面从磁盘读入后还未被修改，我们不需要将该页面写到磁盘因为它已经存在

请求调页中需要解决两个问题

帧分配算法：如果有多个进程在内存中，如何决定为每个进程分配多少帧

页面置换算法：当需要页面置换时，如何选择要置换的帧

FIFO页面置换

FIFO页面置换算法为每个页面记录了调到内存的时间（使用FIFO队列）

当必须置换页面的时候，将选择最旧的页面，即置换FIFO队列的首个页面

Belady异常：随着分配帧数量的增加，缺页错误率可能会增加

最优页面置换（OPT）

最优页面置换具有所有算法中最低的缺页错误率，且不会遭受Belady异常

主要思想是置换长时间不会使用的页面

然而，最优置换算法难以实现，因为它需要来自未来的信息

LRU页面置换（最近最少使用算法）

核心思想是将最近的过去作为不远的将来的近似，置换最长时间没有使用的页

一种方法时采用时钟计数器，存储每个页面最后引用的时间，每次置换具有最小时间的页面

另一种方法则是使用堆栈，每次有页面被应用时，他就从堆栈中被移到顶部，每次置换堆栈底部的页面。最好是使用具有首尾指针的双向链表来实现

近似LRU页面置换

通过引用位，许多不支持LRU的计算机系统也能达到近似的效果

每当我们引用一个页面时，它的引用位就被硬件置位

额外引用位算法

如果我们为页表中的每个页面保留一个n位，用于记录该页面最近n个时间周期内的使用情况

每个周期将引用位移到最高位，其他位右移，这样我们就能通过比对每个页面的移位寄存器来选择置换页面

此时具有最小寄存器的页面可以被替换

第二次机会算法（时钟算法CLOCK）

第二次机会置换更像是一种FIFO置换算法，可以采用循环队列

当需要一个帧时，指针向前移动直到找到一个引用位为0的页面，并会沿途清除引用位

增强型第二次机会算法

我们可以将引用位和修改位结合成有序对

每次我们根据有序对替换级别最低的页面

由于为被修改过的页面赋予了更高的级别，I/O的数量能够有效降低

基于计数的页面置换

为每个页面的引用次数保存一个计数器

最不经常使用（LFU）：置换具有最小计数的页面

最经常使用（MFU）：置换具有最大计数的页面

页面缓冲算法

通过维护一个空闲帧缓冲池，我们能在换出牺牲帧的同时将所需页面读到来自缓冲池的空闲帧

这样能允许进程尽快重新启动，当牺牲帧被写出后，会被添加到空闲帧池

帧分配

帧的最小数

随着分配给每个进程的帧数量的减少，缺页错误率会增加

必须有足够的帧来容纳任何单个指令可用引用的所有不同的页面，否则若在执行指令完成之前发生缺页错误，那么指令会被重新启动

每个进程的最小帧数由体系结构决定，但最大帧数是由可用物理内存的数量决定

分配算法

平均分配：n个进程分配m个帧，则每个进程分配$floor(m/n)$个帧，剩下的当作空闲帧缓冲池

比例分配：根据每个进程的大小加权分配可用内存

全局置换与局部置换

全局置换允许一个进程从所有帧的集合中选择一个置换帧

局部置换只允许每个进程从它自己的帧中进行选择

相对而言，全局置换会有更好的系统吞吐量

系统抖动

一个进程的调页时间多于它的执行时间，那么这个进程就在抖动

如果低优先级进程所分配的帧数低于计算机体系结构所需的最小数量，那么必须暂停该进程执行并释放它的所有分配的帧

通过局部置换和优先权置换算法可以限制系统抖动，局部置换能够防止一个进程开始抖动时，从另一个进程获取帧而使其也抖动

局部性模型工作集策略研究了一个进程实际使用多少帧

我们只需分配大于工作集的帧数即可

文件系统

文件概念

操作系统对存储设备的物理属性加以抽象，从而定义逻辑存储单位，即文件

从用户角度来看，文件是逻辑外存的最小分配单元

文件可以粗略分为以下几种类型：

同时，每个文件也拥有自己的属性

系统有一个打开文件表，用于维护所有打开文件的信息。当请求文件操作时，可以通过该表的索引指定文件

操作系统采用两级的内部表：进程表和系统表，每个进程的进程表跟踪他打开的所有文件，进程表的条目指向系统的打开文件表

系统表的文件条目具有以下关联信息：

访问方法

顺序访问

文件信息按顺序加以处理，编辑器和编译器通常以这种方式访问文件

直接访问

在直接访问中，文件由固定长度的逻辑记录组成

直接访问基于文件的磁盘模型，因为磁盘允许对任何文件块的随机访问

对于大量信息的立即访问，直接访问文件极为有用，所以数据库通常是这种类型的

直接访问的文件操作需要包括块号作为参数，如read(n)和write(n)，其中n为块号

当然，用户提供的通常为相对块号

索引访问

索引访问通过搜索索引，根据索引项中包含的块的指针直接访问文件

对于大文件，索引文件本身可能也会变得很大，一种解决方案时为索引文件创建索引

目录与磁盘的结构

包含文件系统的磁盘分区通常称为卷，卷中包含有关系统内的文件信息，这些信息保存在设备目录或卷目录表

存储结构

使用链接存在两个问题：一个是当查找文件或者统计文件时，共享结构可能不止一次被遍历到；第二个问题是删除共享文件时，分配的控件何时可以被释放和重用，当直接删除时，可能会留下悬挂指针，另一种方法是保留文件直到文件的索引引用都被删除

文件系统实现

文件系统结构

文件系统主要有两个设计方向，一个是用户接口，另外一个就是如何创建算法，以便映射逻辑文件系统到物理外存设备

I/O控制层包括设备驱动程序和中断处理程序，以在主内存和磁盘系统之间传输信息。其中设备驱动程序将高级指令翻译成底层的硬件指令

基本文件系统向设备驱动程序发送通用命令，以读取和写入磁盘的物理块

文件组织模块知道文件及其逻辑块以及物理块，可以将逻辑块地址转成物理块地址，以供文件系统传输

逻辑文件系统管理元数据信息，元数据包括文件系统的所有结构，但不包括实际数据。逻辑文件系统通过文件控制块来维护文件结构，文件控制块(FCB)包含有关文件的信息

文件系统布局

文件系统实现

引导控制块：包含从该卷引导操作系统的所需信息

卷控制块：包含卷或分区的详细信息

打开文件表的条目有多种名称，UNIX称之为文件描述符，Windows称之为文件句柄

open()和read()操作的流程如下图所示

目录实现

线性列表

目录实现的最简单方法是，采用文件名称和数据块指针的线性列表

线性列表的缺点是，查找文件需要线性搜索

在线性列表上进一步延申的是排序列表，优点是允许二分搜索，而且不需要单独排序步骤就可以生成排序的目录信息

哈希表

哈希表根据文件名称获得一个值，并返回线性列表内的一个元素指针

需要注意的是，需要做出一些规定来避免哈希碰撞（两个文件名称哈希到相同的位置）

一个拓展的方法是使用溢出链接的哈希表，此时哈希表的每个条目可以是链表而不是单个值

分配方法

连续分配

连续分配的方案中，每个文件在磁盘上占有一组连续的块

访问连续分配文件所需的寻道数量最小，需要寻道时所需的寻道时间最小

连续分配存在一些问题

首先是如何为新文件找到，这属于一个动态存储分配问题，已知的算法都会随时间产生外部碎片

为了防止外部碎片引起的大量磁盘空间的浪费，可以将整个文件系统复制到另一个磁盘再复制回来，将空闲空间合并，不过合并的代价是时间长

另一个问题是，确定一个文件需要多少空间。由于文件内容大小可能发生改变，如果为文件分配的空间太小，则可能会发现文件无法扩展

链接分配

链接分配解决了连续分配的所有问题

在链接分配中，每个文件是磁盘块的链表，磁盘块可能会散布在磁盘的任何地方

目录包括文件第一块和最后一块的指针，且每块都存有下一块的指针

只要有可用的空闲块，文件就可以继续增长大小

一个缺点是，链接分配只能顺序访问文件：要找到文件的第i个块，必须从文件的开始起

另一个缺点是存储指针需要很多空间，如果指针需要使用512字节块的4字节，则0.78%的磁盘空间会用于指针。解决这个问题可以将多个块组成簇，在磁盘中仅以簇为单位来操作，这样可以降低指针所占磁盘空间的百分比

链接分配的变种是文件分配表(FAT)：每个卷的开头部分的磁盘用于存储该表，表中每个磁盘块都有一个条目，可以按块号来索引。

索引分配

如果不使用FAT，链接分配的块指针与块会一起分散在整个磁盘上，不能高效的直接访问

索引分配通过将所有指针放在一起，即索引块，解决了这个问题

每个文件都有自己的索引块，文件的目录包含索引块的地址，索引块的第i个条目指向文件的第i个块

索引分配直接直接访问，并且没有外部碎片问题

决定索引块的大小时，目前有几种机制：

链接方案：由于索引块本身是一个磁盘块，所以可以直接读写。为了支持大的文件，可以将多个索引块链接起来
多级索引：通过第一级索引块指向第二级的索引块，然后第二级索引块再指向文件块
组合方案：

空闲空间管理

为了跟踪空闲磁盘空间，系统需要维护一个空闲空间列表。空闲空间列表有几种实现方法

位向量

空闲空间列表按位图或位向量来实现：每块用一个位表示，如果块是空闲的，位为1；如果块是分配的，位为0

链表

将所有空闲磁盘块用链表连接起来，将指向第一空闲块的指针保存在磁盘的特殊位置上，同时也将其缓存在内存中

组

在第一个空闲块中存储n个空闲块的地址，这些块的前n-1块为空，最后一块包含另外n个空闲块的地址

计数

记录第一块的地址和紧跟第一块的连续空闲块的数量n

大容量存储结构

磁盘调度

对于磁盘，访问时间主要包括两个部分：寻道时间（移动磁臂到所要柱面的所需时间）和旋转延迟（旋转磁臂到所要扇区的所需时间）

当我们完成一个磁盘访问相关的请求时，应该由磁盘调度算法来决定选择下一个待处理的请求服务是谁

我们选择的主要是哪个柱面，即寻道时间

FCFS调度

最简单的形式即先来先到服务(FCFS)

假如请求块的柱面的顺序如下：98,183,37,122,14,124,65,67

如果磁头开始位于柱面53，那么它首先从53移动到98，接着再到183、37、122等等

磁头移动柱面的总数位640

SSTF调度

最短寻道时间优先(SSTF)选择处理距离当前磁头位置的最短寻道时间的请求

虽然相比于先来先到服务，SSTF的寻道时间大大减少，但是可能会出现一些请求的饥饿

某些请求可能长时间或者永远得不到服务

SCAN调度

扫描算法(SCAN)从磁盘的一端开始，向另一端移动

到达另一端时，磁头移动方向翻转

所以扫描算法也叫电梯算法

C-SCAN调度

循环扫描(C-SCAN)是扫描算法的一个变种，当磁头达到磁盘另一端时，它立即返回到磁盘的开头，并不处理回程上的请求

LOOK调度(C-LOOK)

LOOK调度和C-LOOK调度是扫描算法及循环扫描的改进

这两种算法只会移动到一个方向上的最远请求

磁盘管理

将磁盘分为扇区的过程称为低级格式化（物理格式化）。每个扇区使用特殊的数据结构填充磁盘

操作系统需要先将磁盘由柱面分为多个分区，然后进行逻辑格式化，这一步将初始的文件系统数据结构存储在磁盘上

I/O系统

I/O硬件

设备域计算机的通信通过一个连接点或端口

总线是一组线路和通过线路传输信息的严格定义的一个协议

如果设备A通过线路连接到设备B，B又通过线路连接到设备C，C通过端口连到计算机，则这种方式称为菊花链

控制器是可以操作端口、总线或设备的一组电子器件

I/O端口通常由四个寄存器组成

性能

I/O是系统性能的一个主要因素

如果忙等所需的计算机周期并不多，则程序控制I/O比中断驱动I/O更为有效

网络流量也能导致高的上下文切换速率

为了改善I/O效率，可以采用多种方法：

减少上下文切换的次数
减少设备和应用程序之间传递数据时的内存数据的复制次数
通过大传输、智能控制器、轮询，减少中断频率
增加并发
将处理原语移到硬件，允许控制器操作与CPU和总线操作并发

系统保护

保护目标

确保系统的活动程序组件按照规定策略来使用系统资源

保护原则

最低特权原则：程序、用户甚至系统只能拥有足够特权以便执行任务

遵循最低特权原则的操作系统实现它的特征、程序、系统调用和数据结构，以便组建的故障或妥协做到最小伤害并且允许最小伤害

保护域

每个计算机系统是进程和对象的一组集合，对象包括硬件对象和软件对象

进程只应允许访问获得了授权的资源，同时还有需要知道原则：当进程p调用过程A()时，该过程只应允许访问它自己的变量和传递给它的形式参数；它应当不能访问进程p的所有变量

进程需要在保护域内执行，每个域为访问权限的一组集合，每个权限为一个有序对<对象，操作集>

如果进程可用的资源集合在进程的生命周期中时固定的，则进程和域的关联可以是静态的，否则是动态的

域的实现可以是每个用户是一个域，每个进程可以是一个域，每个过程可以是一个域

访问矩阵

访问矩阵的行表示域，列表示对象，访问条目access(i,j)定义了执行在域$D_i$中的进程可以针对对象$O_j$调用的操作集合

当用户创建新对象$O_j$时，增加列$O_j$到访问矩阵，且具有创建者指定的适当初始化条目

当切换一个进程从一个域到另一个域时，我们为域内对象执行switch操作

从域$D_i$到$D_j$的切换是允许的，当且仅当$switch \in access(i,j)$

控制权限只能作用于域对象，即如果access(i,j)包含控制权限，那么域$D_i$中的进程可以删除行j内的任何访问权限

保证对象最初持有信息不能移到执行环境之外的问题称为禁闭问题

访问矩阵的实现

全局表

全局表包括一组有序三元组<域，对象，权限集>

这种实现的缺点是表通常很大，不能保存在内存中，且不能利用对象和域特殊分组的优点

对象的访问列表

每个对象的访问列表包括一组有序对<域，权限集>

这种方法可以轻松扩展，以便定义一个列表加上一个访问权限的默认集合

域的能力列表

域的能力列表又一组对象以及对象允许的操作组成

能力列表本身是受保护的对象，由操作系统维护，用户只能按简介方式来访问

锁-钥匙机制

每个对象都有一个唯一的位模式列表，称为锁。每个域也有一个唯一的位模式列表，称为钥匙。执行在域中的经常可以访问一个对象，仅当该域具有匹配这个对象锁的一个钥匙时

钥匙和锁列表必须通过操作系统来管理

作业内容小记

内存分配

这题应该选C，首先释放的空线分区域另外两个空闲分区合并，同时由于是采用最佳适应算法，空闲分区按大小递增的顺序排在链上

页面置换

下列关于虚拟存储器的叙述中，正确的是（ B）。

A. 虚拟存储只能基于连续分配技术

B. 虚拟存储只能基于非连续分配技术

C. 虚拟存储容量只受外存容量的限制

D. 虚拟存储容量只受内存容量的限制

装入程序时，只将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。
采用连续分配方式，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，也无法从逻辑上扩大内存容量，因此虚拟内容的实现只能建立在离散分配的内存管理的基础上。
虚拟存储器容量既不受外存容量限制，又不受内存容量限制，而是由CPU的寻址范围决定的。

当系统发生抖动时，可以采取的有效措施是（A ）。

I.撤销部分进程

II.增加磁盘交换区的容量

III.提高用户进程的优先级

A. 仅 I

B. 仅 II

C. 仅 III

D. 仅 I、II

系统抖动是由于内存不够

页面大小为4KB，低12位是页内偏移。虚拟地址为02A01H，页号为02H, 02H页对应的页表项中存在位为0,进程P分配的页框固定为2，且内存中已有两个页面存在。根据CLOCK算法，选择将3号页换出，将2号页放入60H页框，经过地址变换后得到的物理地址是60A01H

文件系统

假设某文件为链接文件，它由 5 个逻辑记录组成，每个逻辑记录的大小与磁盘块的大小相等，均为 512B，并依次存放在 50,121,75,80,63 号磁盘块上。若要存取文件的第 1569 逻辑字节处的信息，则应该访问 ( B) 号磁盘块。

A. 3

B. 80

C. 75

D. 63

第 1 个逻辑记录（0-511 字节）在 50 号磁盘块

第 2 个逻辑记录（512-1023 字节）在 121 号磁盘块

第 3 个逻辑记录（1024-1535 字节）在 75 号磁盘块

第 4 个逻辑记录（1536-2047 字节）在 80 号磁盘块

第 5 个逻辑记录（2048-2559 字节）在 63 号磁盘块

在一个文件被用户进程首次打开的过程中，操作系统需要做的是（B ）。

A. 将文件内容读到内存中

B. 将文件控制块读到内存中

C. 修改文件控制块中的读写权限

D. 将文件的数据缓冲区首指针返回给用户进程

若目录 dir 下有文件 file1，则在删除该文件时，内核不必完成的工作是（A ）。

A. 删除 file1 的快捷方式

B. 释放 file1 的文件控制块

C. 释放 file1 占用的磁盘空间

D. 删除目录 dir 中与 file1 对应的目录项

下列选项中，可用于文件系统管理空闲磁盘块的数据结构是
I．位图
II．索引结点
III．空闲磁盘块链
IV．文件分配表（FAT）
A．仅 I、II
B．仅 I、III、IV
C．仅 I、III
D．仅 II、III、IV

答案：B
解析：传统的文件系统管理空闲磁盘的方法包括空闲表法、空闲链表法、位示图法和成组链接法，即 I 、III正确；
索引结点是操作系统为了实现文件名与文件信息分开而设计的数据结构，存储了文件的描述信息，索引结点属于文件目录管理部分的内容，即 II 不对；
文件分配表（FAT）的表项与物理磁盘块一一对应，并且可以用一个特殊数字 -1表示文件的最后一块，用 -2 表示这个磁盘块是空闲的，因此文件分配表（FAT）不仅记录了文件中各个块的先后链接关系，同时还标记了空闲的磁盘块，操作系统可以通过FAT对文件存储空间进行管理，即 IV 正确。

引入高速缓冲的主要目的是（ C）。

A. 提高 CPU 的利用率

B. 提高 I/O 设备的利用率

C. 改善 CPU 与 I/O 设备速度不匹配的问题

D. 节省内存

I/O系统

系统将数据从磁盘读到内存的过程包括以下操作：

① DMA 控制器发出中断请求

② 初始化 DMA 控制器并启动磁盘

③ 从磁盘传输一块数据到内存缓冲区

④ 执行“DMA 结束”中断服务程序

正确的执行顺序是（ B）。

A. ③→①→②→④

B. ②→③→①→④

C. ②→①→③→④

D. ①→②→④→③