专业课简答题

操作系统

第一章 操作系统引论

1. 操作系统的作用?
   1. 操作系统是用户与计算机硬件系统之间的接口.
   2. 操作系统是计算机资源的管理者
   3. 操作系统是计算机工作流程的组织者
   4. 操作系统实现了对计算机资源的抽象
      {1. 覆盖了一层I/O设备管理软件,隐藏I/O细节;
      2.在隐藏I/O细节的基础上覆盖了一层用于文件管理的软件}
2. 操作系统具有那几大特征,他们之间的关系?
   操作系统有:并发、共享、虚拟、异步 四大特征
   1. 并发和共享是操作系统最基本的特征，为了提高计算机资源利用率，OS必然要采用多道技术，使多个程序共享系统的资源，并发的执行
   2. 并发和共享互为存在的条件。1. 资源的共享是以程序的并发执行为条件的。2.若系统不能对资源共享实施有效的管理，也必将影响到程序的并发
   3. 虚拟性以并发和共享为前提
   4. 异步性是并发和共享的必然结果，多个并发进行共享资源会使得每个进程的运行过程受到其他进程制约
3. 什么是多道技术，OS引入多道的目的
   多道程序技术是指在内存中同时存放若干个作业，并使它们共享系统资源且并发运行的技术。
   OS引入多道技术：1.提高CPU利用率；2.提高内存和I/O设备利用率；3.增加系统吞吐量
4. 推动批处理系统和分时系统形成和发展的主要动力是什么？
   批处理系统：不断提高系统资源利用率和提高系统吞吐量
   分时系统：为了更好地满足用户地需要
5. 实现分时系统地关键问题是使用户能与自己的作业进行交互，为此需要引入：1. 缓冲区暂存用户键入的命令和输出的结果；2. 规定每个程序每次只能运行一个时间片
6. 比较分时系统与实时系统
   分时系统：多路性、独立性、及时性、交互性
   实时系统：多路性、独立性、及时性、交互性、可靠性
   1. 从交互性方面：交互性是分时系统的关键问题，用户可以进行广泛的人机交互；实时系统的交互性具有很大的局限性。
   2. 从及时性方面：分时系统的及时性是指用户能在很短时间内获得系统的响应，2-3秒；及时性是实时系统的关键问题，由被控制对象所要求的开始截止时间和完成截止始键决定，毫秒级
   3. 从可靠性方面：可靠性是实时系统另一个关键问题。分时系统的可靠性要求较低
7. 批处理系统、分时系统、实时系统各有什么特点？
   1. 批处理系统：用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行
   2. 分时系统：可让多个用户同时使用计算机，人机交互性强，具有每个用户独立使用计算机的独占性，系统响应及时
   3. 实时操作系统能对控制对象做出及时反应，可靠性高，响应及时，但资源利用率低

第二章 进程控制与描述

1. 进程控制块PCB（进程存在的唯一标志）：
   作用：1. 进程控制块时操作系统用来描述和管理进程的数据结构；2.使一个在多道环境下不能独立运行的程序成为一个能独立运行的基本单位； 3.记录系统所需的用于描述进程当前情况机控制进程运行的全部信息。
   在进程整个生命周期中，系统总是通过PCB来对进程进行控制和管理，系统依靠PCB感知进程的存在。

   进程标识符
   处理机状态：主要是寄存器的内容组成，用于CPU切换时保存线程信息和恢复现场信息。
   进程调度信息：进程状态、优先级、等待和使用CPU的时间等，用于进程调度和对换。
   进程控制信息：地址，进程同步和通信信息，资源清单，队列指针等

2. 进程创建的过程：

   1. 申请空PCB：先从PCB集合中申请一个空闲的PCB
   2. 分配资源：在为新进程分配内存等资源
   3. 初始化PCB：根据父进程提供的参数和分配到的资源的情况来对PCB进行初始化
   4. 插入就绪队列

3. 进程同步机制原则：

   1. 空闲让进，临界区空闲，允许一个请求进程立即进入临界区
   2. 忙则等待，已有进程进入临界区，其他请求进入的进程必须等待
   3. 有限等待，应保证请求进程在有限时间内进入临界区
   4. 让权等待 ，当进程不能进入临界区，应立即释放处理机，防止忙等

4. 进程通信的类型：
   共享存储器系统，管道通信，消息传递系统，客户机-服务器系统

5. 消息缓冲队列机制发送原语和接收原语：

原理：消息缓冲队列通信机制通过内存中公用的消息缓冲区进行进程通信，属于直接通信方式。发送进程发送消息时，需申请一个消息缓冲区，并把自己的进程标示符和有关消息的内容填入消息缓冲区，然后将其插入到接收进程的消息缓冲队列中，接收进程接收消息时需从自己的消息缓冲队列中摘下一个消息缓冲区，取出其中的消息，然后消息缓冲区归还给系统。

PCB需要添加：mq（消息缓冲队列队首指针）；mutex（消息缓冲队列互斥信号量）；sm（消息缓冲队列资源信号量）。

struct message_buffer{ //消息缓冲区数据结构
    int sender; //发送者进程标识符
    int size; //消息长度
    char *text；//消息正文
    struct message_buffer *next; //指向下一个消息缓冲区
}

void send(receiver a){ //发送原语
     getbuf(a.size, i); //根据a.size申请缓冲区
     i.sender = a.sender; //将发送区a中的信息复制到缓冲区i
     i.size = a.size;
     copy(i.text, a.text);
     i,next = 0;
     getid(PCBset, receiver, j)//获得接收程序j的PCB
     wait(j.mutex)
     insert(&j.mq, i) //将消息缓冲区i插入消息队列
     signal(j.mutex)
     signal(j.sm)
}

void receive(b) { //接收原语
    j = internal_name; //获取当前进行的PCB
    wait(j.sm);
    wait(j.mutex);
    remove(j.mq, i); //移出消息队列第一个消息
    signal(j.mutex); 
    b.sender = i.sender; //将缓冲区i中信息复制到接收区b
    b.size = i.size;
    copy(b.text, i.text);
    releasebuf(i); //释放消息缓冲区i
}

6. 为什么要引入进程？
   为了实现多个程序的并发执行，提高资源利用率和系统吞吐量。
   传统的程序在并发执行时结果不可再现。
   不利影响：管理进程需要付出一定的代价，包括进程控制块，进程间切换，同步，通信等。

7. 进程和程序的异同：
   进程与程序紧密相关又完全不同。

   1. 进程实体中除了程序段和数据段之外还包含一个数据结构PCB
   2. 进程是动态的，是程序的一次执行过程。
      程序是静态的，是一组指令的有序集合
   3. 多个进程实体可同时放在内存中并发执行，这是引入进程的目的
      程序的并发具有不可再现性，不能正确的并发。
   4. 进程是一个能够独立运行、独立分配资源和独立接收调度的基本单位。程序在多道程序环境下不能独立运行（没有PCB）
   5. 进程与程序不一一对应；同一程序多次运行产生多个进程；同一程序一次执行也可产生多个进程（fork调用产生子进程）；一个进程在生命周期不同时候可以执行不同的程序。

8. 进程和线程的异同

   1. 调度性：引入线程后，线程成为调度和分派的基本单位，进程只是拥有资源的基本单位
   2. 并发性：都可并发
   3. 拥有资源：拥有资源的基本单位是进程。线程只有一点必不可少的资源，但可共享其隶属进程的资源。
   4. 独立性：进程可独立的申请资源和运行，而同一进程下的线程共享进程的地址空间和其他资源，独立性较低。
   5. 开销：创建撤销进程时，OS都要为之分配和回收资源。开销远大于线程。
   6. 传统的进程只能运行在一个处理机上，多线程的进程则可以运行在多个处理机上，并发效果更好。

9. 进程状态转换

   状态转换	引起转换的事件
   就绪-执行	CPU调度
   执行-就绪	时间片完，更高优先级进程抢占
   执行-阻塞	等待I/O或临界资源
   阻塞-就绪	等待的事件完成

10. 内核支持线程和用户级线程：
    内核支持线程是在内核支持下实现的，即每个线程的线程控制块设置在内核中。用户级线程仅存在于用户空间中，每个线程控制块设置在用户空间中，所有对线程的操作也在用户空间中完成，无需内核帮助。

第三章 处理机调度与死锁

1. 处理机调度算法的目标

   1. 资源利用率：为提高资源利用率，应使系统中的处理机和其他所有资源都尽可能保持忙碌
   2. 公平性：应使进程获得合理的CPU时间，不会发生饥饿现象。
   3. 平衡性：尽可能保持系统资源使用的平衡性
   4. 策略强制执行

2. 处理机调度的层次

   1. 高级调度：作业调度，把作业从后备队列拿出，分派资源后建立进程中，使之可以获得处理机
   2. 中级调度：内存调度，把外存中的就绪进程调入内存，插入就绪队列
   3. 低级调度：进程调度，最基本的调度。决定就绪队列的进程获得处理机

3. 调度的方式

   1. 非剥夺（非抢占）方式：一旦分配就占有资源直到阻塞或结束。优点是简单，系统开销小
   2. 剥夺（抢占）方式：当前进程所占有的资源可被其他进程夺走。
      1. 优点：更高的系统吞吐率和响应效率
      2. 原则：优先权、短进程、时间片原则

4. 引起进程调度的因素：

   1. 正在执行的进程正常终止或异常终止
   2. 正在执行的进程因某种原因而阻塞
   3. 引入时间片的系统中，时间片完
   4. 抢占调度方式中，有更高优先权的进程

5. 调度的算法的类型及比较：

   有先来先服务、短作业优先、优先级调度、高响应比优先、时间片轮转、多级反馈队列等

   1. 先来先服务、短作业优先无法保证及时接收和处理问题，无法保证在规定时间间隔内响应每个用户需求，也不能达到实时系统的及时性需求。
   2. 优先级调度算法，按优先级进行调度，对于更紧急的任务予以更高优先级，适合实时操作系统
   3. 高响应比优先，时间片轮转，多级反馈队列能保证每个任务在一定时间内分配到时间片，适合分时系统

6. 低级调度主要功能

   低级调度用于决定就绪队列中哪个进程获得处理机，并由分派程序把处理机分配给该进程

   1. 保存当前进程的处理机现场信息到PCB
   2. 按调度算法选择投入执行新进程
   3. 恢复新进程的现场，将处理机分配给新进程

7. 高响应比优先调度算法优点是什么？

   响应比 = 响应时间/要求服务时间 = （等待时间+要求服务时间）/要求服务时间 ； 优点是：

   1. 如果进程等待时间相同，则要求服务时间最短的进程优先权最高，有利于短作业。【SJF短作业优先只考虑了作业运行时间而忽略了作业等待时间】
   2. 如果作业要求服务时间相同，则优先权将取决于进程到达先后次序，体现了公平原则。【FCFS先来先服务只考虑作业等待时间而忽视了作业运行时间】
   3. 如果进程较长，它的优先权将随着等待时间的曾长而提高，不会长时间得不到服务。
      8. 为什么说多级反馈队列调度算法能较好地满足各方面用户的需要？
   4. 对于终端型作业用户而言，其提交的作业大多为交互型作业，作业通常较小，系统只要能使这些作业在第一个队列所规定的时间片内完成，便可使其满意
   5. 对于短批处理作业用户而言，较短的作业可在第一个队列完成，稍长的也可以在第二三队列执行一个时间片完成，周转时间仍然很短。
   6. 对于长批处理作业用户而言，用户不必担心作业长期得不到处理，且每下降一个队列，长作业等待时间都进一步缩短。

8. 死锁定理

   在资源分配图中找到一个既不阻塞又非独立的进程，分配给该进程资源后，该进程执行完毕释放所占资源，即消去请求边与分配边，使其成为孤立点，重复该过程，若能使所有进程都能成为孤立点，则该图是可完全简化的。
   当前状态为死锁的充分条件是，当且仅当该状态的资源分配图是不可完全简化的。

9. 产生死锁的原因和必要条件

   原因：系统资源的竞争和进程推进顺序非法。
   必要条件：互斥条件、请求与保持条件、不剥夺条件、循环等待条件
   预防死锁：破坏四个条件
   避免死锁：银行家算法，防止进入不安全状态
   检测死锁：死锁定理，资源分配图
   解除死锁：资源剥夺，撤销进程，解除死锁

第四章 存储器管理

1. 程序的装入

   1. 绝对装入方式：产生使用绝对地址的目标模块。只适用于单道程序环境
   2. 可重定位装入方式：程序中的其他地址都是相对于始址的
      1. 静态重定位：在装入时，由重定位程序一次性完成的。不允许程序在运行时在内存中移动位置。
   3. 动态运行时装入方式：需要重定位寄存器的支持。可以将程序分配在不连续的存储区中，程序运行之前可以只装入部分代码即刻运行，运行期间动态申请分配内存，便于程序段共享。

2. 程序的链接

   1. 静态链接方式：在程序运行之前将各目标模块及所需的库函数链接为一个完整的装入模块。
   2. 装入时动态链接：链接在装入时进行，便于对程序模块进行修改和更新，可对外存中的目标模块实现共享。
   3. 运行时动态链接：链接在运行时进行。便于实现目标模块的修改、更新和共享，加快程序的装入过程，提高内存利用率。

3. 为什么引入对换？

   1. 在多道程序环境下，一方面内存中某些进程由于某事件尚未发生而阻塞，却占用大量内存空间，可能出现内存中所有进程被阻塞。另一方面：又有很多作业意志驻留外存，不能进入内存运行
   2. 提高内存利用率，系统吞吐量

4. 什么情况下需要进行重定位？为什么要引入重定位？

   重定位概念：将作业空间中的逻辑地址转换为主存空间中的物理地址，从而保证作业能够正常进行。

   1. 程序在装入时，指令和数据的实际物理地址与装入模块中的相对地址是不一致的，此时需要重定位。
   2. 引入动态重定位是因为进程在运行过程中进场要在内存中移动位置。重定位的过程是由硬件地址变换机构在程序执行每条指令时自动完成。

5. 连续分配方式中动态分区分配方式：

   1. 首次适应算法：按地址从小到大为序，分配第一个符合条件的分区。
   2. 最佳适应算法：按空间从小到大为序，分配第一个符合条件的分区。
   3. 最坏适应算法：按空间从大到小为序，分配第一个符合条件分区。
   4. 循环首次适应：与首次适应算法相似，从上次分配的下一个位置继续。

6. 分页系统地址变换机构

   硬件支持：页表寄存器，地址变换机构

   1. 页号与页表长度比较，页号大于页表长度，则产生越界中断
   2. 以页号为索引去检索页表。页表始址+页号x页表项长度
   3. 从页表中获取物理块号。
   4. 物理地址=物理块号+页内地址。

   一次数据操作，访问两次内存：访问页表获取块号，访问数据。
   引入快表的地址变换机构

   1. 页表在与页表寄存器中的页表长度比较时并行地与快表中的所有页号比较。
   2. 若在快表中则直接读出物理块号。
   3. 否则从页表中读，并将得到的页表项和页号装入到快表中。

   多级页表机制下页内地址长度等于页面大小。

7. 分段系统地址变换机构

   硬件支持：段表寄存器，地址变换机构

   1. 段号S与段表度长比较，若大于则产生越界中断。
   2. 使用段号进行索引段表得到该段的基址和长度。段表始址+段号x段表项长度。
   3. 检查段内地址是否超过段长，超过则产生越界中断。
   4. 物理地址=起始地址（基址）+段内地址。

   一次数据操作访问两次内存。

8. 分页与分段比较：

   1. 页是信息的物理单位，分页是为了提高内存利用率。段是信息的逻辑单位，含有一组其意义相对完整的信息。分段是为了能更好的满足用户的需要。

   2. 页的大小固定且由系统决定。段的长度不固定且由用户所编写的程序决定。

   3. 分页的地址空间是一维的，分段的地址空间是二维的。

   4. 分页有内部碎片，无外部碎片。分段无内部碎片，有外部碎片。

   5. 分段更容易实现共享和动态链接。

第五章 虚拟存储器

1. 什么是虚拟存储器？

   虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。
   虚拟存储器具有如下特征：

   1. 多次性，最本质最重要的特征。虚拟存储器将一个作业分成多次调入内存。部分装入。
   2. 对换性，虚拟存储器允许将将暂时用不到的程序从内存调到对换区，提高内存利用率。
   3. 虚拟性，虚拟存储器对内存的扩充是逻辑上的。
   4. 离散性，虚拟存储器必须建立在离散分配的基础上。

2. 如何实现页式虚拟存储器？

   首先请求分页的页表机制。扩充页表，增加状态位确认是否在内存；增加外存始址便于调入；增加引用位供置换算法。增加修改位减少换出时写磁盘次数。
   请求调页技术，需要硬件上缺页中断机制和软件配合实现。
   置换页技术，关键是采取什么置换算法。
   还有地址变换机构。

3. 局部性原理

   1. 时间局部性，某条指令（数据）一旦执行（访问），不久后可能被再次执行（访问）。原因是程序中的大量循环操作。
   2. 空间局部性，程序在一段时间内所访问的地址可能集中在一定范围内。原因是程序的顺序执行。

4. 缺页中断中断机构与一般中断之间的区别

   1. 在指令执行期间产生和处理中断信号。
   2. 一条指令在执行期间可能产生多次中断。

5. 请求分页系统中地址变换过程（考试中不需要写这个详细的，要写按地址字段进行转换的）

6. 页面置换算法

   1. 最佳算法（OPT）：选择往后最长时间内不再被访问的页面置换。

   2. 先进先出页面置换算法（FIFO）

   3. 最近最久未使用算法（LRU）：为每个页面设置一个访问字段，记录自上次被访问以来所经历的时间。选择最大的置换。需要寄存器和栈的硬件支持。

第六章 输入输出系统（I/O）

1. I/O系统基本功能

   方便用户使用I/O设备。

   1. 隐藏物理设备的细节
   2. 与设备的无关性

   提高设备的资源利用率。

   1. 提高处理机和I/O设备的利用率。

   2. 对I/O设备进行控制。

   方便用户共享。

   1. 确保对设备的正确共享

   2. 错误处理

2. I/O系统的层次结构

   1. 用户层I/O软件
   2. 设备独立性软件
   3. 设备驱动程序
   4. 中断处理程序

3. I/O控制方式

   1. 轮询方式：程序直接对设备循环测试

      优点：简单，易于实现
      缺点：CPU和I/O只能串行工作，CPU利用率很低

   2. 中断方式：引入中断机制，当设备准备完成时发生中断

      优点：CPU和I/O可以并行工作，相较于轮询方式大大提高了CPU利用率
      缺点：仍以字节为单位，降低了效率。

   3. DMA（直接存储器存取）方式：在I/O设备与内存之间直接开辟数据通路

      特点：

      1. 基本单位是数据块
      2. 数据是直接从设备送入送出内存的
      3. 仅在传送一个或多个数据块的开始和结束时才需要CPU干预，整块数据的传送是在DMA控制器的控制下完成的。

   4. 通道控制方式：引入专门的I/O处理机进行管理

      进一步减少CPU干预，基本单位变为一组数据块

4. 试说明I/O控制发展的主要推动因素是什么？

   1. 力图减少CPU对I/O设备的干预，充分发挥CPU的数据处理能力
   2. 缓和CPU的高速性和I/O设备的低速性之间速度不匹配的矛盾。提高CPU利用率和系统的吞吐量。
   3. 提高CPU和I/O设备操作的并行程度。提高整个系统的资源利用率和吞吐量。

5. 中断的重要性：

   1. 中断是多道程序实现的基础，进程的切换通过中断完成。
   2. 中断是设备管理的基础，为提高CPU利用率和实现CPU与I/O设备并行执行。

6. 中断驱动I/O方式和DMA方式有什么不同？

   1. 中断方式是程序的切换，要保护和恢复现场； DMA方式除了预处理和后处理其余时间不占用CPU
   2. 对中断请求的响应只能发生在每条指令结束时（指令执行周期后）；对DMA的请求响应可以发生在每个机器周期结束时（取指、间址、执行），只要CPU不占用总线就可以响应。
   3. 中断传送过程需要CPU的干预；DMA传送过程不需要CPU的干预，故DMA传输效率高，适合高速外设成组数据传输。
   4. DMA请求优先于中断请求
   5. 中断方式具有对异常事件的处理能力。 DMA方式仅局限传送数据块的I/O操作。
   6. 从数据传送来看，中断靠程序传送，DMA靠硬件传送。

7. DMA方式和I/O通道方式的区别。

   1. DMA需要CPU控制数据传送位置，数据块大小等参数，而通道中这些参数的设置是由通道控制的。
   2. 一个DMA控制器对应一台设备。 一个I/O通道可以控制多台设备。

8. 为什么I/O通道常采用交叉连接的方式

   I/O通道是一种特殊的处理机，它具有执行I/O指令的功能，能控制I/O操作。由于通道价格昂贵，所以通道数量少，这往往成为I/O的瓶颈，造成整个系统吞吐量的下降。为解决此问题，增加设备到主机之间的通路而不增加通道，提高了系统可靠性。

9. 为什么要引入缓冲区？（重要）

   1. 缓和CPU和I/O设备速度不匹配的矛盾。
   2. 减少对CPU的中断频率，放宽CPU响应中断时间。
   3. 提高CPU和I/O设备之间的并行性
   4. 解决数据粒度不匹配的问题。

10. 为什么要引入设备独立性？如何实现设备独立性？（重要）

    引入设备独立性，可使应用程序独立于具体的物理设备。用逻辑设备名来申请使用某类物理设备，可显著地改善资源的利用率及可适应性。独立性还可以使用户程序独立于设备的类型，可以很方便地进行输入输出重定向。
    为了实现设备独立性，必须在设备驱动程序之上设置一层设备独立性软件，用来执行所有I/O设备的公用操作，并向用户层软件提供统一接口。关键是系统中必须设置一张逻辑设备表LUT来进行逻辑设备到物理设备的映射。（逻辑设备名、物理设备名、设备驱动程序入口地址）

11. 什么是虚拟设备？实现虚拟设备的关键技术是什么？

    虚拟设备是指通过某种虚拟技术，将一台物理设备变为若干台逻辑设备，从而实现多个用户对该物理设备的同时共享。
    虚拟设备技术常通过在可共享的、高速的磁盘上开辟两个大的存储空间（输入井、输出井）以及预输入、缓输出技术来实现。预输入和缓输出可通过脱机和假脱机技术实现。

12. SPOOLing系统（假脱机技术）由哪几部分组成？以打印机为例说明如何利用SPOOLing技术实现多个进程对打印机共享。

    SPOOLing系统由磁盘上的输入井和输出井、内存中的输入缓冲区和输出缓冲区，输入进程和输出进程以及井管理程序构成。
    使用SPOOLing技术共享打印机：

    1. 在输出井中为进程申请一空闲缓冲区，放入要打印的数据。

    2. 为用户进程申请一张空白的打印申请表，在把该表挂到假脱机文件队列上。

第七章 文件管理

1. 文件系统为什么通常是显式进行文件”打开””关闭”操作？

   1. 打开文件操作的基本功能是将指定文件的属性信息FCB复制到内存中，并返回指向内存中该文件属性信息的地址（文件描述符）。关闭文件操作是从内存中删除文件的属性信息，并写回外存。
   2. 显式进行打开操作，当用户需要对一个文件实施多次读写操作时，只需要使用文件描述符而非路径名。系统则无需对目录进行检索便可通过文件描述符直接找到内存中的文件FCB。避免了重复检索目录，提高了文件的访问速度。

2. 文件的逻辑结构和物理结构的概念

   1. 文件的物理结构是文件的存储结构，指系统过将文件存储在外存上的存储形式

   2. 文件的逻辑结构指从用户角度出发所观察到的文件组织形式，文件的内部数据在逻辑上是怎么组织的。

      1. 有结构文件

         1. 顺序文件：与关键字有关的串结构，无关的顺序结构
         2. 索引文件：为变长文件建立索引表
         3. 索引顺序文件：顺序文件和索引文件的结合
         4. 直接文件：通过哈希函数直接决定记录地址

      2. 无结构文件：将数据按顺序组织成记录并积累保存。

3. 对文件目录管理的要求？

   1. 能够实现”按名存取”。
   2. 能够提供快速的目录查询手段以提高对文件的检索速度。
   3. 为文件的共享和重名提供方便
   4. 允许文件同名

4. 文件系统：文件控制块和索引节点的内容

   

   1. 文件控制块：

      1. 基本信息：包括文件名，文件物理地址，文件逻辑结构，文件物理结构
      2. 存取控制信息：文件的存取权限
      3. 使用信息：文件的建立时间，修改时间，当前使用信息。

   2. 索引结点：至少要有索引结点编号、存取权限、文件物理地址、文件大小的信息。

      1. 优点是：可以减少文件查找时平均启动磁盘的次数，有效提升文件检索速度。

   3. 磁盘索引结点

      1. 文件主标识符
      2. 文件类型
      3. 文件存取权限
      4. 文件物理地址
      5. 文件长度
      6. 文件连接计数
      7. 文件存取时间

   4. 内存索引结点

      1. 索引结点编号
      2. 状态：是否修改
      3. 访问计数
      4. 文件所属文件系统的逻辑设备号
      5. 链接指针，指向空闲链表和散列队列。

5. 文件系统必要的系统调用

   创建文件、删除文件、读文件、写文件。
   以读文件为例：

   1. 系统调用给出文件名和读入的内存目标地址
      1. 系统通过查找目录表，找到该文件所对应的索引结点编号，或直接通过指向索引节点的指针找到索引结点。
      2. 根据索引结点中的物理地址，找到文件在外存中存放的位置。
      3. 将该文件读入内存。

6. 树形目录结构中线性检索法的检索过程

   1. 系统在检索一个文件时，先读入给定文件路径名中的第一个分量名，用它与根目录文件（当前目录文件）中的各目录项中的文件名顺序地进行比较。
      1. 若找到相匹配的目录项，则可获得它的FCB或索引节点编号，从而找到该分量名对应的文件。
      2. 然后系统再读入第二个文件分量名，与刚检索到的目录文件中的各目录项的文件名顺序比较，若找到，则重复该过程，逐级检索指定文件分量名，最后会得到指定文件的FCB或索引结点。

7. 文件共享方式

   目的是提高文件存储空间利用率，方便用户对文件的使用。

   1. 基于索引结点的共享方式（硬链接）：将多个目录项指向同一个磁盘索引结点

   2. 利用符号链实现文件共享（软链接）：建立一个类型为LINK，内容为被共享文件路径名的新文件来实现共享。

第八章 磁盘存储器的管理

1. 文件外存分配中，即文件的物理结构，连续分配、链接分配、和索引分配各自的优缺点。

   1. 连续分配方式：为每个文件分配一组相邻的物理块，将文件信息按逻辑顺序存放。

      1. 适合不经常更新，经常随机访问
      2. 优点：管理简单；顺序访问存取速度很快；支持对文件随机存取
      3. 缺点：要求连续的存储空间，容易产生碎片，降低存储空间利用率；要求事先知道文件长度；不利于文件的增长扩充。

   2. 链接分配方式：隐式链接方式类似于单链表；显式链接方式是将链接各物理块的指针显式地登记在系统的一张文件分配表FAT中。

      1. 适合经常更新，经常顺序访问

      2. 隐式链接：

         1. 优点：解决了外部碎片；不需事先知道文件长度；插入删除修改容易；
         2. 缺点：只支持顺序访问；可靠性较差

      3. 显式链接：

         1. 优点：可显著提高检索的速度；增加了文件系统的可靠性。
         2. 缺点：不支持高效的随机存取；文件存储介质较大，则FAT也要占用较大存储空间。

   3. 索引组织方式：为每个文件建立一个索引表，登记分配给该文件所有的物理块号，文件FCB的物理地址字段为该索引表的指针。

      1. 适合经常更新，经常随机访问
      2. 优点：既支持顺序访问又支持随机访问；查找效率高；便于文件删除
      3. 缺点：索引表会占用一定存储空间，对单独的中小文件也需要分配完整的索引表，对外存空间造成严重浪费。

2. UNIX系统的混合索引方式：索引地址分为13个地址项。假设每个物理块4KB

   优点：既能节省存储地址所占的存储空间，又有较高的查找速度。

   1. 直接地址：0-9共10个地址项，分配相应文件的前十个物理块地址。可存储4KB X 10 = 40KB的文件

   2. 一次间址：地址项10为一次间址。登记分配给文件的第10个物理块及后序物理块地址。如果地址长度为4B，则一次间址块可存储4KB / 4B = 1K个物理块号。最大存储文件为40KB+ 1K x 4KB

   3. 多次间址：地址项11为二次间址，存储的是1次间址的块号。故可存储40KB+4MB+4GB的文件；地址项12是三次间址，存储的是二次间址的块号。故可存储40KB + 4MB + 4GB + 4TB的文件。

3. 文件存储空间的管理

1. 位示图法：用1表示分配，0表示清除

2. 成组链接法：适合大型文件。将一个文件卷的所有空闲盘块按固定大小分成若干组，并将每一组的盘块数和该组所有盘块号计入前一组的最后一个盘块中。（最后一组的0标记也算一个）

   1. 分配过程（操作题）：

      1. 将s_nfree（该组空闲盘块数）减1；
      2. 若s_nfee仍大于0，即第一组不只一个空闲盘块，则将s_free[s_nfree]空闲盘块号栈栈顶的空闲盘块分配出去。
      3. 若s_nfree为0，即当前空闲盘块号栈中只剩下最后一个空闲盘块，则用唯一所剩的盘块替换掉超级块，再将该盘块分配出去。
      4. 若s_nfree为0，且栈底登记盘块号为0；则表示系统已无空闲盘块可分配。

3. 磁盘调度算法（计算）

   一次磁盘读写操作时间：
   

   ​ 寻道时间（m x 磁道数 + 启动时间） + 延迟时间（1/2r） + 传输时间（b/(r x 一个磁道上字节数)）

   1. 先来先服务（FCFS）：根据进程请求访问磁盘的先后顺序进行调度
   2. 最短寻找时间优先（SSTF）：选择当前磁头所在磁道距离最近的磁道
   3. 电梯算法（SCAN）：在当前移动方向上最近的磁道。
   4. 循环扫描算法（CSCAN）：只能一个方向，到达当前方向上最后一个需要访问的磁道后，从头开始。

4. 提高磁盘I/O速度的途径。

   1. 磁盘高速缓存

   2. 提前读

3. 延迟写

4. 优化物理块布局

5. 虚拟盘

6. 提高文件访问速度的途径。

   1. 改进文件的目录结构及检索目录的方法来减少对目录的查询时间

   2. 选取好的文件存储结构，以提高对文件访问速度

   3. 提高磁盘I/O速度。

组成原理

1. 冯·诺伊曼计算机结构的主要特点：

   1. 计算机由运算器、控制器、存储器、输入设备和输出设备5大部分组成
   2. 指令和数据用二进制表示，两者形式上没有差别。
   3. 指令和数据存放在存储器中，按地址访问
   4. 指令由操作码和地址码组成，操作码指定操作性质，地址码指定操作数地址
   5. 采用”存储程序”方式进行工作

2. 计算机系统层次结构

3. 指令和数据均以二进制形式存放在存储器中，计算机如何区分？

   时间上说，在取指周期取的是指令，在执行周期取的是数据；
   空间上说，指令存放在指令寄存器，数据存放在通用寄存器；
   并且，指令地址在PC中存放，数据地址在指令的地址字段。

4. 控制器设计的两种方式及其各自特点

   1. 微程序控制器：微操作控制信号以微程序的形式存放在控制存储器中，执行指令时读出，执行速度慢，较规整，应用于CISC，易扩充和修改。指令添加容易，可维护性好。
   2. 硬布线控制器：微操作控制信号由组合逻辑电路根据当前指令码、状态和时序即时产生，执行速度快，繁琐不规整，应用于RISC，难易扩充，可维护性差。

5. 计算机调用中断服务程序与调用子程序有何区别

   1. 中断程序：随机的，和主程序有关，从隐指令中取得中断服务地址
   2. 子程序：预先设计好的，为主程序服务，由调用服务给出地址。