多级反馈队列算法，如何兼顾短作业和长作业的？

多级反馈队列调度算法能较好地满足各种类型用户的需要。对终端型作业用户而言，由于 它们提交的作业大多属于交互型作业，作业通常比较短小，系统只要能使这些作业在第 1 级队列所规定的时间片内完成，便可使终端型作业用户感到满意；对于短批处理作业用户而言，它们的作业开始时像终端型作业一样，若仅在第 1 级队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间，对于稍长的作业，通常也只需要在第 2 级队列和第 3 级队列中各执行一个时间片即可完成，其周转时间仍然较短；对于长批处理作业用户而言，它们的长作业将依次在第 1，2，…… 级队列中运行，然后按时间片轮转方式运行，用户不必担心其作业长期得不到处理。

什么是虚拟存储器？如何实现页式虚拟存储器？

虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

页式虚拟存储器在基本分页系统基础之上，增加请求调页功能和页面置换功能。为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存，还需要有页表机制、缺页中断机构和地址变换机构。进行页面置换时，还需选取适合的页面置换算法，置换算法的好坏将直接影响到系统的性能。

程序局部性原理是什么？有什么具体表现（时间局部性/空间局部性）？

局部性原理，即程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。

局部性原理表现在以下两个方面：

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

时间局部性通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现。空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。

文件物理结构指的是一个文件在外存上的存储组织形式，主要有连续结构、链接结构和索引三类，请分别简述其优缺点。

• 连续结构
  • 优点：顺序访问容易，顺序存储速度快；支持随机访问。
  • 缺点：必须要有连续的存储空间；容易产生碎片，且磁盘利用率低；不利于文件的扩充。
• 链接结构
  • 优点：不要求连续的存储空间；没有碎片问题，磁盘利用率高；利于文件的增长扩充。
  • 缺点：文件的数据块之间通过指针进行链接，适合顺序访问，不适合随机访问。
• 索引结构
  • 优点：既支持顺序访问，也支持随机访问，并且查找效率高；便于文件的扩充和删除。
  • 缺点：索引表占用了一定的空间。

什么是文件的混合索引结构？直接地址、—次间接地址和多次间接地址所允许的最大文件规模。

混合索引结构是将多种索引分配方式相结合的分配方式。系统既采用直接地址，又采用单级索引分配方式或两级索引分配方式。

为了能够较全面地照顾到小型、中型、大型和特大型文件，可采用混合索引分配方式。对于小文件，为了提高对众多小文件的访问速度，最好能将它们的每个盘块地址直接放入 FCB，这样就可以直接从 FCB 中获得该文件的盘块地址，即为直接寻址。对于中型文件，可以采用单级索引方式，需要先从 FCB 中找到该文件的索引表，从中获得该文件的盘块地址，即为一次间址。对于大型或特大型文件，可以采用两级和三级索引分配方式。UNIX 系统采用的就是这种分配方式，在其索引结点中，共设有 13 个地址项，即 i.addr(0)〜i.addr(12)，如图所示。

1. 直接地址：为了提高对文件的检索速度，在索引结点中可设置 10 个直接地址项，即用 i.addr(0) ~ i.addr(9) 来存放直接地址，即文件数据盘块的盘块号。假如每个盘块的大小为 4KB，当文件不大于 40KB 时，便可直接从索引结点中读出该文件的全部盘块号。
2. —次间接地址：对于中、大型文件，只采用直接地址并不现实的。为此，可再利用索引结点中的地址项 i.addr(10) 来提供一次间接地址。这种方式的实质就是一级索引分配方式。 图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间 址块中可存放 1024 个盘块号，因而允许文件长达 4MB。
3. 多次间接地址：当文件长度大于 4MB + 40KB（一次间接地址与 10 个直接地址项）时， 系统还需采用二次间接地址分配方式。这时，用地址项 i.addr(11) 提供二次间接地址。该方式的实质是两级索引分配方式。系统此时在二次间址块中记入所有一次间址块的盘号。 地址项 i.addr(11) 作为二次间址块，允许文件最大长度可达4GB。同理，地址项 iaddr(12) 作为三次间址块，其允许的文件最大长度可达 4TB。

什么是设备的独立性，应如何实现？

设备独立性也称设备无关性，即应用程序独立于具体使用的物理设备。对用户而言，是指在编写程序时使用的设备与实际设备无关，在程序中只指明 I/O 使用的设备类型即可。

为了实现设备的独立性，应引入逻辑设备和物理设备两个概念。在应用程序中，使用逻辑设备名称来请求使用某类设备；而系统执行时，是使用物理设备名称。鉴于驱动程序是一个与硬件（或设备）紧密相关的软件，必须在驱动程序之上设置一层软件，称为设备独立性软件，以执行所有设备的公有操作、完成逻辑设备名到物理设备名的转换（为此应设置一张逻辑设备表 Logical Unit Table, LUT）并向用户层（或文件层）软件提供统一接口，从而实现设备的独立性。

什么是抖动？减少抖动的措施有哪些？

抖动指页面置换过程中，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存这种频繁的页面置换现象。

减少抖动的方法有：撤销部分进程；为某些进程添加适当的页帧；选择更适合的页面置换算法。

什么是快表？说明利用快表进行地址转换的具体过程。

快表是一个具有并行查找能力的高速缓冲存储器，又称相联存储器（TLB），用来存放当前访问的若干页表（或段表）项，可以加速地址变换的过程。

在具有快表的分页机制中，地址的变换过程如下：

• ① CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
• ② 若找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样，存取数据仅一次访存便可实现。
• ③ 若未找到匹配的页号，则需要访问主存中的页表，读出页表项后，应同时将其存入快表，以便后面可能的再次访问。若快表已满，则须按特定的算法淘汰一个旧页表项。

快表的有效性基于局部性原理，一般命中率可达 90% 以上，可以有效提高地址变换过程。

Spooling 系统的组成部分有哪些，工作原理是什么？

• Spooling 系统的组成

  • 输入井和输出井：这是在磁盘上开辟的两个大存储空间。
    • 输入井是模拟脱机输入时的磁盘，用于暂存 I/0 设备输入的数据；
    • 输出井是模拟脱机输出时的磁盘，用来暂存用户程序的输出数据。
  • 输入缓冲区和输出缓冲区：这是在内存中开辟的两个缓冲区。
    • 输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。
    • 输出缓冲区用来暂存从输出井送来的数据，以后再传送给输出设备。
  • 输入进程和输出进程：输入/输出进程用于模拟脱机输入/输出时的外围控制机。
    • 输入进程，也称为预输入进程，将用户要求的数据从输入设备传送到输入缓冲区，再存放到输入井。当 CPU 需要输入设备时，直接从输入井读入内存。
    • 输出进程，也称为缓输出进程，把用户要求输出的数据，先从内存送到输出井，待输出设备空闲时， 再将输出井中的数据经过输出缓冲区送到输出设备上。
  • 井管理程序：用于控制作业与磁盘井之间信息的交换。当作业执行过程中向某台设备发出启动输入或输出操作请求时，由操作系统调用井管理程序，由其控制从输入井读取信息或将信息输出至输出井。

• 工作原理

  输入/输出进程用于模拟脱机输入/输出时的外围控制机。用户要求的数据从输入设备经过输入缓冲区送到输入井，当 CPU 需要输入数据时，直接从输入井读入内存。用户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备。

SPOOLing 系统的组成

如何实现文件共享？

文件共享使多个用户共享同一个文件，系统中只需保留该文件的一个副本。可以基于索引结点实现文件共享（硬链接），或者利用符号链方式实现文件共享（软链接）。

软链接硬链接是什么？主要区别是什么？

硬链接是指基于索引结点实现文件共享。在这种共享方式中，用户要共享某文件时，需在目录中增加一个目录项，并设置一个指针指向该文件的索引结点，通过该索引结点可找到共享文件。此外，共享文件对应索引结点上的需要增加链接计数 count，用于表示链接到本索引结点（即文件）上的用户目录项的数目。

软链接是指利用符号链方式实现文件共享。以这种方式建立链接时，系统会创建一个 LINK 类型的新文件，其内容为被链接文件的路径名。当用户要访问被链接的文件时，操作系统查看到要读的文件是 LINK 类型，则根据该文件中的路径名去找到文件，从而实现对文件的共享。

两者的区别：

利用软链接方式实现文件共享时，只有文件主才拥有指向其索引结点的指针。而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针，即无论多少个符号链接指向源文件，源文件索引节点的计数值都不会变。

硬链接中，索引节点中的链接计数 count 为 0 时，共享文件才能被删除。

软链接就是把到达共享文件的路径记录下来，当要访问文件时，根据路径寻找文件。可见，硬链接的查找速度要比软链接的快。

死锁避免和死锁预防的区别？

死锁预防：设置某些限制条件，破坏产生死锁的 4 个必要条件中的一个或几个。其属于事先预防策略，限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低。

死锁避免：在资源的动态分配过程中，用某种方法防止系统进入不安全状态。属于事先预防策略，限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

死锁产的必要条件是？如何预防和解除死锁？

1. 产生死锁的必要条件

   • 互斥条件：进程要求对所分配的资源（如打印机）进行排他性使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
   • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
   • 不可抢占（剥夺）条件：进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。
   • 循环等待条件：在发生死锁时，必然存在一个进程——资源的循环链，即进程集合 ${\small \{P_0 ,P_1, P_2, \dots ,P_n\}}$ 中的 ${\small P_0}$ 正在等待一个 ${\small P_1}$ 占用的资源，${\small P_1}$ 正在等待 ${\small P_2}$ 占用的资源…… ${\small P_n}$ 正在等待被 ${\small P_0}$ 占用的资源。

2. 处理死锁的方法

   防止死锁的发生只需破坏死锁产生的 4 个必要条件之一即可。

   1. 破坏“互斥”条件
   2. 破坏“请求和保持”条件
   3. 破坏“不可抢占（剥夺）”条件
   4. 破坏“循环等待”条件

3. 死锁解除

缓冲区的类型和引入缓冲区的目的。

PCB 中主要存储的内容是什么？为什么说 PCB 是进程存在的唯一标志？

在存储管理中，什么是重定位，为什么要引入重定位技术？