【OS】操作系统总复习笔记

操作系统总复习

一、考试题型

1. 论述分析题

• 3题，每题8分

2. 计算题

• 4题，每题8分

3. 应用题

• 3题，总计44分

---

二、操作系统引论（第1章）

2.1 操作系统的发展过程

1. 单道批处理：

   • 标准定义： 单道批处理是指一台计算机一次只能执行一个作业，直到该作业执行完毕，才能执行下一个作业。
   • 通俗解释： 就像一台咖啡机一次只能冲一杯咖啡，等当前咖啡冲好了才能开始下一杯。

2. 多道批处理：

   • 标准定义： 多道批处理是指计算机同时处理多个作业，将它们组织成一个作业队列，依次执行。
   • 通俗解释： 想象一下计算机是一位高效的服务员，而你是一位在餐厅就餐的顾客。你提前点好了多道菜，然后将菜单交给服务员。不同的是，这位服务员聪明地把所有顾客的菜单都组织成一个列表，然后告诉厨师同时开始烹饪。而不是等待一道菜做好再点下一道。

3. 分时：

   • 标准定义： 分时是指计算机在短时间内轮流为多个用户服务，每个用户感觉到自己在独占地使用计算机。
   • 通俗解释： 就像一台共享单车，不同用户可以在不同的时间共享使用，每个用户感觉到独享整车。

4. 实时：

   • 标准定义： 实时是指计算机能够在规定的时间内对输入作出及时的响应，通常用于控制系统等领域。
   • 通俗解释： 就像电梯的按键，按下后电梯会立即响应，而不是等待一段时间再运行。

---

2.2 操作系统定义

• 标准定义： 操作系统是控制和管理计算机硬件与软件资源，为用户和应用程序提供服务的系统软件。
• 通俗解释： 操作系统就像计算机的总管家，负责协调各种任务，让计算机资源更好地为用户和应用服务。

---

2.3 操作系统的基本特性

2.3.1 并发

• 标准定义： 并发是指两个或多个事件在同一时间间隔内发生。
• 通俗解释： 就像是一台电视机同时播放多个频道，观众可以选择不同的节目观看。

2.3.2 共享

• 标准定义： 共享是指多个进程之间共享系统资源的方式。
• 通俗解释：
  • 互斥共享方式：就像一辆共享自行车，一次只能被一个人使用，其他人需要等待。在计算机中，这意味着某些资源一次只能由一个任务占用，其他任务必须等待。
  • 同时访问方式：就像一片公共草坪，多个人可以同时在上面散步、读书，彼此不会干扰。在计算机中，这表示多个任务可以同时访问某些资源，而不会产生冲突，使得系统更加高效地共享资源。

2.3.3 虚拟

• 标准定义： 虚拟是指通过一定的技术手段，将物理实体划分为逻辑上的多个实体。
• 通俗解释：
  • 虚拟存储器：就像你有一个超级大的书桌，但不是所有书都放在桌子上，一部分放在书柜里，需要时再取出。计算机的虚拟存储器也是这个道理，能够像有很大内存一样使用，实际上部分数据可能存在硬盘上。
  • 虚拟设备：就像你有一台多合一打印机，可以为多台电脑提供服务，但实际上只有一台物理设备。

2.3.4 异步

• 标准定义： 异步是指事件的发生和处理不是同步发生的。
• 通俗解释： 想象一下你发了一封电子邮件，不需要等待对方立即回复，你可以继续做其他事情，然后在方便的时候查看是否收到回复，就像是你自己掌握何时处理信息一样。

---

2.4 OS的功能

• 标准定义： 操作系统具有多种功能，包括进程管理、存储器管理、文件系统管理、设备管理和用户接口等。
• 通俗解释： 就像一位高效的项目经理，负责协调团队中的各项工作，确保项目顺利进行，同时提供良好的沟通渠道。

1. 进程管理：

   • 标准定义： 操作系统负责创建、调度和终止进程，以及管理进程间的通信与同步。
   • 通俗解释： 像是一场舞会的主持人，安排舞池中的舞者，确保他们按照规定的步调舞动。

2. 存储器管理：

   • 标准定义： 操作系统控制计算机内存的分配和释放，以及虚拟内存的管理。
   • 通俗解释： 好比一个图书管理员，负责将书籍合理地摆放在书架上，确保读者能够方便地找到需要的信息。

3. 文件系统管理：

   • 标准定义： 操作系统负责组织和管理存储在计算机硬盘上的文件，提供文件的创建、读取、写入和删除等操作。
   • 通俗解释： 就像一名档案管理员，整理文件柜，确保每个文件都有清晰的标签和正确的存放位置。

4. 设备管理：

   • 标准定义： 操作系统协调和控制计算机的各类硬件设备，包括输入设备、输出设备和存储设备。
   • 通俗解释： 好比一位调度员，负责安排机房中各种设备的工作，确保它们协同运作。

5. 用户接口：

   • 标准定义： 操作系统提供与用户交互的界面，可以是命令行界面、图形界面或其他形式的用户界面。
   • 通俗解释： 就像手机的操作系统界面，用户通过触摸屏或按键与手机进行交互，完成各种操作。

2.5 OS结构

• 标准定义： 操作系统的结构通常包括内核（kernel）和系统调用接口，内核负责直接与硬件交互，而系统调用接口为应用程序提供服务。
• 通俗解释： 类似一座建筑物，内核是建筑的基础和支撑结构，系统调用接口则是连接用户与内核的桥梁，使用户能够利用操作系统的功能。

---

2.5 习题1

一、简答题

1.在计算机系统上配置OS ( operating system,操作系统)的目标是什么?作用主要表现在哪几个方面?

【参考答案】在计算机系统上配置OS,主要目标是实现:方便性、有效性、可扩充性和开放性。
OS的作用主要表现在以下3个方面:

1. OS作为用户与计算机硬件系统之间的接口;
2. OS作为计算机系统资源的管理者;
3. OS实现对计算机资源的抽象。

2. 试说明推动OS发展的主要动力是什么。

【参考答案】推动OS发展的主要动力表现在:

1. 计算机系统资源的利用率不断提高:
2. 方便用户
3. 器件不断更新换代
4. 计算机体系结构不断发展
5. 新的应用需求不断被提出。

3. OS具有哪几大特征?它们之间有何关系?

答：OS具有并发、共享、虚拟和异步这4个基本特征。

它们之间的关系包含以下几个方面。
1.并发和共享是OS最基本的特征。为了提高计算机资源的利用率，OS必然要采用多道程序设计技术，使多个程序共享系统的资源、并发地执行。
2.并发性和共享性互为存在的条件。一方面，资源的共享是以程序（进程）的并发执行为条件的，若系统不允许程序并发执行，就不会存在资源共享问题;另一方面，若系统不能对资源共享实策有效管理，协调好各进程对共享资源的访问，则必将影响程序的并发执行，甚至会使程序无法并发执行。
3.虚拟性以并发性和共享性为前提。为了使并发进程能更方便、更有效地共享资源，OS常采用多种虚拟技术在逻辑上增加CPU和设备的数量以及存储器的容量，从而解决并发进程对有限系统资源的共享问题。
4.异步性是并发性和共享性的必然结果。OS允许多个并发进程共享资源、相互合作，使得每个进程的运行过程受到了其他进程的制约，不再“一气呵成”，这必然会导致异步这一特征的产生。

4. 何谓原语?何谓原子操作?

答：原语是由多条指令组成的用于完成特定功能的过程，而原子操作是不可分割的基本单位，要么全部执行，要么全部不执行。因此，原语在执行过程中是不允许被中断的。原子操作在内核态下执行，常驻内存。

5. 简述中断处理过程。

答：一旦CPU响应中断，系统就会开始进行中断处理。中断处理过程主要包括以下3步。
(1) 保护被中断进程的现场。为了在中断处理结束后能使进程正确地返回中断点，系统必须保存当前处理机状态字和程序计数器的值。
(2) 分析中断原因，转去执行相应的中断处理程序。在多个中断请求同时发生时，处理优先级最高的中断源所发出的中断请求。
(3) 恢复被中断进程的现场,CPU继续执行被中断的原进程。

6. 什么是系统调用?系统调用与一般用户程序和库函数有何区别?

答：系统调用是OS提供给程序员的唯一接口。程序员利用系统调用，在源程序层面动态请求和释放系统资源，并调用系统中已有的系统功能来完成那些与机器硬件部分相关的工作以及控制程序的执行速度等。因此，系统调用像一个“黑箱子”，对用户屏蔽了OS的具体动作，只提供有关的功能。

系统调用与一般用户程序、库函数的区别在于:
①系统调用（程序）在内核态执行，调用它们时需要一个类似于硬件中断处理机制的中断处理机制来提供系统服务。
②普通的用户程序是直接为用户完成某特定功能而设计的，它们一般在用户态执行。
③库函数是把函数放到库里供别人使用的一种方式，是面向应用开发、方便人们编程的。

二、计算题

1.设有3道程序A、B、C,它们按照优先次序(A→B →C)顺序执行,它们的计算时间和VO操作时间如表1-1-1所示,假设3道程序以串行方式使用相同的设备进行IO操作,试画出单道程序运行和多道程序运行的时间关系图,并计算完成这3道程序所须花费的时间。

1. 答：计算时间时，CPU处理时间，IO操作时间是输入与输出时间。3个程序共享IO设备，即串行使用IO设备。
   (1)单道程序运行时,3道程序串行执行，即先执行A、再执行B、最后执行C，时间关系图如图所示。
   

单道程序运行时，3道程序使用的时间为:( 30+40+10 )+(60+30+10)+(20+40+20)=260ms。
(2)多道程序运行时，3道程序的计算与IO操作可部分并行，分为非立即抢占式和立即抢占式两种，时间关系图如图1和图2所示。
多道程序运行时，3道程序非立即抢占式的总时间为180ms，立即抢占式的总时间为190ms。

2.(考研真题)一个多道批处理系统中仅有P1和P2两个作业,P2比P11晚5ms 到达,它们的计算和I/O操作顺序如下。

P1:计算60ms, l/O操作 80ms,计算20ms.
P2:计算120ms,I/O操作40ms,计算40ms.
不考虑调度和切换时间,请计算完成两个作业需要的最少时间。

2. 答：作业执行时间关系图如图所示。由于在多道批处理系统中，P1与P2可以部分并行，因此，P1先到达系统，其会先占用CPU进行计算（到60ms ) ，然后执行IO操作的时间是60ms ~ 140ms;而在P1执行IO操作的过程中，P2可获得CPU运行120ms，到180ms结束;当P1执行完它的I/O操作后，执行计算，此时CPU正被P2占用，因此P1须等P2执行完后才能获得CPU执行剩余的20ms，执行完成后退出系统;此时，P会执行I/O操作40ms，到220ms;最后P2获得CPU运行剩余的40ms(计算)，到260ms结束。由图1-1-5可知，完成两个作业需要的最少时间为260ms。
   

三、综合应用题

1.OS的概念、特征和功能是什么?

答：该问题分步解答如下。
( 1 ) OS是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以方便用户使用计算机的程序集合。OS是配置在计算机硬件上的第一层系统软件，是对硬件系统的首次扩充;是硬件系统和应用软件间的桥梁;是用户与计算机硬件进行交互的接口;是计算机系统资源的管理者。
( 2 )OS的4个特征:并发、共享、虚拟、异步。
①并发:一段时间间隔内多个进程（线程)并发执行，是宏观上的并行，微观上的串行。②共享:系统中的资源可供内存中多个并发执行的进程或线程共同使用。
③虚拟:通过某种技术将物理实体变为若干个逻辑上的对应物。
④异步:进程以人们不可预知的速度向前推进，每次运行只要环境相同，则结果必定一致。
( 3 )OS的5大功能:处理机管理、存储器管理、设备管理、文件管理、接口管理。
①处理机管理:进程（线程）是处理机调度的单位，因此对外理器的管理实际上是对进程（线程)的管理。
②存储器管理:内存的分配与回收、地址转换、虚拟内存的实现等。
③设备管理:设备的分配与回收、缓冲区管理、磁盘调度、设备虚拟等。
④文件管理:文件存储空间的管理、文件目录管理、文件共享与保护等。
⑤接口管理:用户接口、程序接口、命令接口和网络接口。

2.(考研真题）若某计算问题的执行情况如图1-1-6所示。

则请回答下列问题。
(1)叙述该计算问题中处理机、输入机和打印机是如何协同工作的。
(2)计算在图1-1-6所示执行情况下处理机的利用率。
(3)简述处理机利用率不高的原因。
(4)请画出能提高处理机利用率的执行方案。

答：(1)处理机、输人机和打印机是按照输人→处理→打印的顺序依次执行的，输人机为处理机提供数据，处理机得到数据后进行处理，处理结果通过打印机打印输入。输人机读取一批数据，花费时间为100;处理机对这批数据进行计算，花费时间为20;打印机打印计算结果，花费时间为40。
(2)处理机的利用率=[ 20 (100+20+40) ] x100%=12.5%。
(3)当一道程序在运行中发出IO请求后，处理机只能处于等待状态，即必须等LO完成后才能继续运行．因此处理机会长时间处于空闲状态，这会导致其利用率不高。
(4）采用多道程序设计技术使处理机、输入机和打印机并行工作，可以提高处理机的利用率，如图所示。

---

三、处理机管理（第2、3、4章）

3.1 进程概念

3.1.1 进程的定义

1. 标准定义： 进程是程序执行的实体，是操作系统进行资源分配和调度的基本单位。
2. 通俗解释： 进程就像火车，是程序的一次执行过程，而程序则是火车的设计图。
   进程就像是计算机中程序的具体执行，是操作系统为程序提供运行环境并分配资源的基本单元。可以把进程看作是计算机中正在进行的任务，每个任务都有自己的空间和资源。

3.1.2 进程的引入目的

1. 标准定义： 进程的引入旨在实现多道程序设计，提高CPU的利用率，使多个进程可以并发执行。
2. 通俗解释： 进程的引入就像是在一个大厨房里同时烹饪多道菜，提高了整体效率，让每个菜都能在合适的时候完成。
   引入进程的目的就是为了让计算机可以同时处理多个任务，就像一台多功能机器，能够在同一时间执行多个不同的任务，从而更高效地利用计算机的处理能力。这让我们的电脑可以同时运行浏览器、音乐播放器和文档编辑器，而不是只能一个任务一个任务地执行。

3.1.3 进程与程序的区别与联系

1. 标准定义：
   • 进程： 是程序在执行过程中的实体，有独立的内存空间和系统资源。
   • 程序： 是静态的，存储在磁盘上的可执行文件，是进程的设计图。
2. 通俗解释：
   • 进程就像是在跑步的运动员，有自己的身体和能量。
   • 程序就像是运动员的跑步计划，是一份静态的文件，需要通过运动员的执行才能变成实际的运动。

3.2 进程同步与临界资源管理

3.2.1 进程同步的任务

1. 标准定义： 对多个相关进程的执行次序进行协调，以使并发的诸进程有效地共享资源和相互合作，从而使程序的执行具有可再现性。
2. 通俗解释： 进程同步的任务就像是一个大型协作舞蹈，各个进程就是舞者，它们需要协调动作，共享舞台资源，以确保整个表演有条不紊地进行。就像是一个编排精良的舞蹈表演，每个舞者都需要在正确的时机做出正确的动作，这样整个表演才能具有可再现性，给观众留下深刻的印象。

3.2.2 进程间两种制约关系

1. 直接制约关系（同步）：

   • 标准定义： 源于进程间的合作，要求某个进程等待另一个进程的信号或消息，以保持进程的顺序执行。
   • 通俗解释： 就像接力比赛中，每个跑步者必须等待前一个跑手的交接棒信号，确保顺序传递。

2. 间接制约关系（互斥）：

   • 标准定义： 源于资源共享，要求对共享资源的访问是排他的，即一次只允许一个进程访问共享资源。
   • 通俗解释： 就像共享一台打印机，一次只能有一个人使用，其他人需要等待。

3.2.3 临界资源、临界区概念、临界区的使用原则

1. 临界资源：

   • 标准定义： 是一次只允许一个进程使用的资源，如共享变量、共享文件等。
   • 通俗解释： 临界资源就像是一把只有一个人能用的工具，比如一把特殊的锤子。每次只有一个工人可以拿到这把锤子，完成自己的工作。其他工人需要等待，直到当前工人使用完毕并释放了这把锤子，下一个工人才能拿到它。这样确保了在任何时刻，临界资源只被一个进程占用，避免了多个进程同时访问可能引起混乱和错误的情况。

2. 临界区概念：

   • 标准定义： 是一段代码，一次只能有一个进程进入执行。在临界区内，对临界资源的访问是排他的，其他进程需要等待。
   • 通俗解释： 想象一下大家在写字台上使用同一支笔，临界区就像是只有一个人能坐的椅子。当有人想写字时，他需要先坐到椅子上（进入临界区），然后进行写字操作。其他人则需要等待当前写字的人完成，才能轮到自己坐到椅子上。这样做的目的是为了防止多人同时使用同一支笔，避免混乱和错误。

3. 临界区的使用原则：

   • 标准定义： 进程进入临界区前需要先申请访问权，临界区内的执行尽量短，离开临界区后释放访问权。
   • 通俗解释： 就像使用共享单车，每次骑行前需要先扫码解锁，骑行结束后再锁定，确保下一个人可以使用。

3.2.4 信号量机制

1. 整型信号量：

   • 标准定义： 是一个整数，用于表示资源的可用数量，进程可以对其进行加减操作。
   • 通俗解释： 整型信号量就像是一个计数器，记录着可用资源的数量，进程可以通过增减操作来请求或释放资源。

2. 记录型信号量：

   • 标准定义： 包含一个整数值和一个等待队列，支持wait()和signal()原语，用于实现进程同步。
   • 通俗解释： 就像是一本书的借阅记录，有人借阅时需要登记，归还时也要登记，确保借阅有序进行。

3. 信号量的物理意义：

   • 标准定义： 可以看作是一种保护机制，防止多个进程同时访问临界资源。
   • 通俗解释： 信号量就像是一把锁，确保一次只有一个进程能够进入临界区，避免资源的冲突和混乱。

3.2.5 信号量的应用

3.2.5.1 实现进程互斥

• 标准定义： 使用信号量保护临界资源，每个进程在访问临界资源前先对信号量进行P操作，离开后进行V操作。
• 通俗解释： 进程互斥就像是共享厨房的规矩，大家都想用同一把刀，但不希望在同一时刻有多个人使用。所以，每个人在使用刀前，先检查有没有"可用"的标志。如果有，就把标志设为"不可用"，表示刀在使用中；使用完后再将标志设回"可用"，这样其他人就知道可以使用了。这个标志就像是信号量，通过检查和设置标志，大家有序地使用共享资源。

3.2.5.2 实现前驱关系（简单的同步关系）

• 标准定义： 使用信号量实现进程的前驱关系，确保某个进程在前驱进程完成后才能执行。
• 通俗解释： 前驱关系就像是工程中的任务链，B任务必须等待A任务完成后才能开始。使用信号量就像是在A任务完成时扔一个小纸条，通知B任务可以开始了。B任务在开始前检查这个小纸条，如果有，就执行，没有的话就等待。这样通过信号量的通知机制，保证了进程之间的前后顺序执行。

3.3 调度管理

3.3.1 调度的概念

• 标准定义： 调度是操作系统根据一定的策略和算法，决定进程或作业在系统中执行的顺序。
• 通俗解释： 调度就像是电梯的按钮，你按下去后，电梯就会按照一定的规则，决定哪个楼层的人先上电梯，实现有序的运送。操作系统的调度就是按照一定的规则，决定哪个进程先执行，确保系统资源的合理利用。

3.3.2 调度的原则

• 标准定义：
  1. 先来先服务（FCFS）：
     按照进程到达的先后顺序进行调度，先到达的进程先执行。
  2. 短作业（进程）优先（SJ§F）：
     优先执行执行时间短的进程，以减少平均等待时间。
  3. 高响应比优先算法：
     通过考虑等待时间和执行时间的比值来选择下一个执行的进程，以提高系统的响应速度。
• 通俗解释：
  • 先来先服务就像是排队购物，先来的顾客先被服务。
  • 短作业优先就像是做事情时优先处理耗时短的任务。
  • 高响应比优先算法就像是服务行业中，优先响应对服务质量有帮助的请求。
    调度的原则就像是队伍中的排队规则，有三种方式。先来先服务就像是谁先到谁先进入服务台。短作业（进程）优先就像是优先让那些任务最短的人先进入服务。高响应比优先算法就像是为了提高服务效率，考虑每个人等待的时间和执行的时间比例，选择合适的人先进行服务。这样可以更好地管理进程，提高系统的整体性能。

3.3.3 调度方式

• 标准定义：
  1. 非抢占式调度：
     进程获得CPU后，直到主动放弃CPU或执行完毕才会释放。
  2. 抢占式调度：
     操作系统具有中断能力，可以强制中断当前进程的执行，转而执行其他进程。
• 通俗解释：
  • 非抢占式调度就像是每个人洗澡前需要先预约，一旦热水器分配给某人，他就可以一直用，直到洗完澡或者自愿放弃，其他人不能抢走热水器。
  • 抢占式调度就像是有了中断按钮，如果有人等急了或者有更重要的事情，可以按下按钮，迫使当前正在使用热水器的人放弃，然后由等待的人使用。这样可以更灵活地管理资源。

3.3.4 调度类型

• 标准定义：
  1. 作业调度：
     决定哪个作业进入内存执行，以及作业的执行顺序。
  2. 进程调度：
     决定哪个进程获得CPU的使用权，以及进程的执行顺序。
• 通俗解释：
  • 作业调度就像是一场戏剧的编排，决定哪个戏登场，以及登场的次序，确保整个戏剧有条不紊地上演。
  • 进程调度就像是舞台上演员的出场顺序，决定哪个演员可以站在前台，得到观众的关注，确保整个表演流畅有序。

3.4 调度算法

3.4.1 FCFS与SJ(P )F算法的应用

1. FCFS（先来先服务）算法：

   • 标准定义： 进程按照到达的先后顺序执行。
   • 通俗解释： 就像是在排队等待服务，先到达的进程先被执行，类似于先到先得的原则。

2. SJ(P )F（短作业（进程）优先）算法：

   • 标准定义： 优先执行执行时间短的进程，可以减少平均等待时间。
   • 通俗解释： 像在自助餐厅，你会先选择那些烹饪时间短的食物，以更快品尝到美味。

3.4.2 高响应比优先算法(用于作业调度)

• 高响应比优先算法：
  • 标准定义： 通过考虑等待时间和执行时间的比值来选择下一个执行的进程，以提高系统的响应速度。计算公式为响应比 = (等待时间 + 服务时间) / 服务时间。
  • 通俗解释： 想象你是一位聪明的服务员，有很多桌子需要照顾。你会优先选择那些等待时间长且需要服务时间短的桌子，因为这样可以更迅速地满足顾客需求，提高整体餐厅效率。在计算机世界中，高响应比优先算法就是让计算机系统像个聪明的服务员一样，更聪明地选择下一个要处理的任务，确保系统更迅速地响应用户需求，提高整体运行效率。

3.5 死锁管理

3.5.1 死锁的概念

• 标准定义： 死锁是指两个或多个进程无法继续执行，因为每个进程都在等待其他进程释放资源。
• 通俗解释： 想象一群小朋友围成一个圈，每个小朋友手里拿着糖果，并想要换取其他小朋友手里的糖果。然而，由于每个小朋友都固执地等着对方先给自己糖果，最终导致所有小朋友都拿不到新的糖果，大家陷入了僵局，无法继续玩耍。这就好比计算机中的死锁，每个进程都在等待其他进程释放资源，最终导致所有进程都无法前进。

3.5.2 产生死锁的原因

• 标准定义：
  1. 竞争资源：
     多个进程竞争有限的资源，导致资源分配不当。
  2. 进程间推进顺序不当：
     进程之间相互等待对方释放资源，形成循环等待。
• 通俗解释：
  • 想象一家只有一个投影仪的会议室，多个团队需要使用。每个团队都想要在会议室里展示自己的项目，但因为只有一个投影仪，团队之间开始争夺使用权，导致资源（投影仪）的分配不当。最终可能导致某些团队无法正常进行演示，整个会议室陷入混乱。
  • 假设有一群小朋友在玩过家家，每个小朋友都需要等待其他小朋友完成某个动作后才能进行下一步。如果他们陷入相互等待的循环，比如小朋友 A 等待 B，B 等待 C，而 C 又在等待 A，那么整个过家家游戏可能无法进行下去，就像死锁一样。这种相互等待的情况可能阻碍所有小朋友完成游戏。

3.5.3 死锁产生的必要条件

• 标准定义：
  1. 互斥条件
  2. 请求和保持条件
  3. 不剥夺条件
  4. 循环等待条件
• 通俗解释：
  让我们以家庭洗碗为例，来理解导致死锁的四个必要条件。

1. 互斥条件
   就像家庭里只有一个洗碗槽一样，同一时间只能有一个人使用。这就是互斥条件，如果多个人试图同时使用洗碗槽，就会发生互斥。

2. 请求和保持条件
   每个家庭成员在洗碗前都会请求并保持对洗碗槽的使用权，以确保能够流畅地进行洗碗。这就是请求和保持条件。

3. 不剥夺条件
   当某人正在使用洗碗槽时，其他人不能剥夺他的使用权，类似于在洗碗过程中保持资源不可被剥夺的条件。

4. 循环等待条件
   想象家庭成员需要按照一定的顺序进行洗碗，如果形成了一个循环等待，比如A等待B，B等待C，而C又在等待A，整个洗碗可能就会陷入循环等待，就像死锁的循环等待条件。这种情况可能导致整个洗碗过程陷入僵局，无法完成。

3.5.4 处理死锁的基本方法

• 标准定义：
  1. 预防死锁：
     通过破坏死锁产生的四个必要条件之一，来预防死锁的发生。
  2. 避免死锁：
     在资源分配过程中，动态地检查系统状态，以确保不会进入死锁状态。
  3. 检测死锁：
     允许死锁发生，但通过检测和恢复来解决死锁。
  4. 解除死锁：
     当检测到死锁时，通过抢占资源或终止进程来解除死锁。
• 通俗解释：
  这就像在家庭洗碗时采取一些策略，以应对可能发生的洗碗僵局。

1. 预防死锁
   就像在家庭洗碗时，家庭成员事先协商好谁先使用哪个洗碗槽，以破坏家庭洗碗可能导致死锁的条件之一，即请求和保持条件。

2. 避免死锁
   在资源分配过程中，就像在洗碗时动态地观察家庭成员使用洗碗槽的情况，以确保不会进入洗碗的死锁状态。这可能涉及更灵活的资源分配策略，以防止死锁的发生。

3. 检测死锁
   有时候允许死锁发生，就像在洗碗时不阻止家庭成员同时请求多个洗碗槽。但系统会定期检测是否发生了死锁，以便及时采取措施来解决问题。

4. 解除死锁
   当检测到死锁时，就像在洗碗时发现了僵局，可能需要采取措施，比如抢占某个洗碗槽，或者终止某个家庭成员的洗碗任务，以解除死锁。

3.5.5 银行家算法

• 标准定义： 一种预防死锁的算法，通过判断系统分配资源后是否处于安全状态来决定是否分配资源。
• 通俗解释： 就像是银行根据账户余额判断是否能够提供贷款，确保整个系统处于安全状态。

3.5 习题2

一、简答题

1.什么是前趋图?请画出下列4条语句的前趋图。

S1:a=x+y;
S2:b=z+1;
S3:c=a-b;
S4: w=c+1:
【参考答案】本题分儿解答如下。
(1)趋图(procedence graph)是一个有向无环图,记为DAG( directed acyclic graph).用于描述进程间执行的前后关系。
(2）题中4条语句对应的前图如图所示。

2.什么是进程?OS中为什么要引入进程?它会产生什么样的影响?

【参考答案】
①进程是一段可并发执行的具有独立功能的程序,是关于某个数据集的一次执行过程，也是OS进行资源分配和保护的基本单位。
②在OS中引入进程,是为了实现多个程序的并发执行。传统的程序与其他程序并发执行时，执行结果不可再现，因此，传统的程序不能与其他程序并发执行，只有在为之创建进程后,其才能与其他程序(进程）并发执行。这是因为并发执行的程序“停停走走”地执行，只有在为它创建进程后，在它停下时,方能将其CPU现场信息保存在它的PCB ( processing control block，进程控制块）中，待下次被调度执行时再从PCB中恢复CPU现场而继续执行，但传统的程序却无法满足上述要求。
③建立进程所带来的好处是多个程序能并发执行，这极大地提高了资源利用率和系统吞吐量。但管理进程也须付出一定的代价，包括PCB及协调各运行机构所占用的内存空间开销，以及为进行进程间的切换、同步与通信等所付出的时间开销。

3.进程最基本的状态有哪些?哪些事件可能会引起不同状态间的转换?

【参考答案】进程最基本的状态有3种。
①运行态:进程占有处理机,正在运行。
②就绪态:进程具备运行条件,等待系统分配处理机以便运行。
③等待态(又称为阻塞态或睡眠态):进程不具备运行条件,正在等待某个事件的完成。
进程不同状态间的转换及引发原因介绍如下。
①运行态→等待态:等待使用资源或某事件发生;
②等待态→就绪态:资源得到满足或某事件已经发生;
③运行态→就绪态:运行时间片到达或出现有更高优先级的进程;
④就绪态一运行态:CPU空闲时调度选中一个就绪进程需要其运行。

4.为什么要引入进程的挂起状态?

【参考答案】所谓挂起状态，实际上就是一种静止的状态。一个进程被挂起后，不管它是否处于就绪状态，系统都不会分配给它处理机。因此，引入挂起状态是基于系统和用户的如下需要。
①终端用户的需要:当终端用户在自己的程序运行期间发现问题时，希望暂停进程的运行。
②父进程请求:父进程挂起自己的某个子进程,检查并修改该子进程，或者协调各子进程之间的活动。
③负荷调节的需要:当实时系统中的工作负荷较重、实时任务受到影响时，挂起些不重要的进程。
④OS的需要:OS挂起某些进程，检查或统计运行中的资源使用情况。

二、综合应用题

22.（考研真题]现代OS 一般都提供多进程（或称多任务）运行环境，回答以下问题。

(1)为支持多进程的并发执行，系统必须建立哪些关于进程的数据结构?
(2)为支持进程状态的变迁,系统至少应提供哪些进程控制原语?
(3)在执行每一个进程控制原语时，进程状态会发生什么变化?相应的数据结构会发生什么变化?
【参考答案】
(1为支持多进程的并发执行，系统必须建立关于进程的相关数据结构,包括PCB和队列结构（如就绪队列、等待队列、运行指针等)。
(2)为支持进程状态的变迁,系统应提供的进程控制原语包括:创建原语、阻塞原语、唤醒原语、撤销原语。
(3）在执行每一个进程控制原语时，进程状态及相应的数据结构有4种变化情况。
①创建原语:系统为进程创建PCB,并对它进行初始化。进程状态由无变为就绪状态,新创建的进程加入就绪队列中。
②阻塞原语:进程状态从运行状态变为阻塞状态，并将阻塞进程的PCB插入相应的阻塞队列中。
③唤醒原语:进程状态从阻塞状态变为就绪状态，从阻塞队列中删除该进程,并将其插入就绪队列中。
④撤销原语:进程状态从运行状态变为消亡状态，系统撤销该进程的PCB.。

3.6 习题3

一. 填空题（共1题，4分）

1. (填空题, 4分)

若每个作业只能建立一个进程，为了照顾短作业用户，应采用（ ）；为了照顾紧急作业用户，应采用（ ）；为了能实现人机交互，应采用（ ）；而能使短作业、长作业和交互作业用户都满意，应采用（ ）。

A、先来先服务调度算法

B、短作业优先调度算法

C、时间片轮转调度算法

D、多级反馈队列调度算法

E、剥夺式优先级调度算法

正确答案：
(1) B
(2) E
(3) C
(4) D
当你想象计算机操作系统是一种类似于"任务管理大师"的存在时，这几种进程调度算法就好比是不同的工作安排方式：

A、先来先服务调度算法： 就像是一个等着打饭的队伍，谁先来的，谁就先吃饭。

B、短作业优先调度算法： 想象一下在自助餐厅里，你会优先选择吃那些看起来短时间就能吃完的食物，以便更快地满足你的饥饿感。

C、时间片轮转调度算法： 就好比你和一群朋友轮流玩电脑游戏，每个人都有一定的时间（时间片）来玩，然后轮到下一个人。

D、多级反馈队列调度算法： 想象一家图书馆有几个阅览室，每个阅览室的环境和规则不同，你根据你的学习需要和规定的时间在这些阅览室之间切换。

E、剥夺式优先级调度算法： 就像是你正在看电视，但如果有紧急的新闻播报，电视节目可能会被打断，以保证更重要的信息先被传达。

这些算法就是操作系统为了合理安排各种任务，让计算机运行更高效，更好地响应用户需求而设计的各种策略。

二. 计算题（共7题，74分）

2. (计算题, 10分)课本P106页第19题

正确答案：

3. (计算题, 10分)

设有4道作业，它们的提交时间及执行时间如下：

作业号 提交时间 执行时间

 1        10.0      2.02        10.2      1.03        10.4      0.54        10.5      0.3

试计算在单道程序环境下，系统10.0开始调度，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算。）

正确答案：
先来先服务：2.8 5.25

短作业优先：2.45 3.85

答案解析：

4. (计算题, 15分)设系统中有3种类型的资源（A，B，C）和5个进程，资源的数量为（17，5，20）。在T0时刻系统状态见表。系统采用银行家算法实施死锁避免策略。

① T0时刻是否为安全状态？若是，请给出安全序列。

② 在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？

③ 在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？

④ 在③的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？

T0时刻系统状态

正确答案：
（1）T0时刻是安全的，存在安全序列<P4,P2,P3,P5,P1>

（2）P2请求（0,3,4),系统可用资源向量(2,3,3)，不满足P2请求，P2阻塞等待。

（3）P4请求(2,0,1)<(2,3,3)，尝试将（2,0,1）分配给P4，系统资源分配如下：

经分析存在安全序列<P4,P2,P3,P5,P1>

(4)在③的基础上，若进程P1请求资源（0，2，0）,系统可用资源向量（0,3,2），尝试分配给P1，此时剩余资源向量（0,1,2），此时资源分配情况如下 ：

可用资源向量（0,1,2）不能满足任何进程的请求，故不予以分配。

5. (计算题, 10分)某系统中共有11台磁带机，X个进程共享此磁带机设备，每个进程最多请求使用3台，则系统必然不会死锁的最大X值是多少？

正确答案：
X*（3-1）+1=11

X=5

答案解析：X*（3-1）+1=11X=5

6. (计算题, 8分)某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是（ ）。

正确答案：
17ms。

7. (计算题, 11分)课本107页第22题

8. (计算题, 10分)

假设有四个作业，它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法，系统8.0开始调度，试问平均周转时间和平均带权周转时间为多少? （时间单位：小时，以十进制进行计算。）

作业号 到达时间 运行时间

1 8.0 2.0

2 8.3 0.5

3 8.5 0.1

4 9.0 0.4

正确答案：
在8：00时，因为只有作业1到达，系统将作业1投入运行。作业1运行2小时(即

10：00时)完成。由于该算法采用响应比高者优先调度算法，这样在作业1执行完后，要计算剩下三个作业的响应比，然后选响应比高者去运行。剩下三个作业的响应比为：

r2=l+(10.0-8.3)／0.5=4.4

r3=l+(10.0-8.5)／0.1=16

r4=l+(10.0-9.0)／0.4=3.5

从计算结果看，作业3的响应比高，所以让作业3先运行。

作业3运行0.1小时完成(即10：10时)，此时，作业2和作业4的响应比为：

r2=l+(10.1-8.3)／0.5=4.6

r4=l+(10.1-9.0)／0.4=3.75

从上述计算结果看，作业2的响应比高，所以让作业2先运行。因此四个作业的执行次序为：作业1、作业3、作业2、作业4.

解：四个作业的调度次序为：作业1、作业3、作业2、作业4。

作业 到达 运行 开始 完成 周转 带权周转

1 8.0 2.0 8.0 10.0 2.0 1.0

2 8.3 0.5 10.1 10.6 2.3 4.6

3 8.5 0.1 10.0 10.1 1.6 16.0

4 9.0 0.4 10.6 11.0 2.0 5.0

平均周转时间 T=(2.0+2.3+1.6+2.0)／4=1.975

平均带权周转时间 W=(1+4.6+16+5)／4=6.65

答案解析：在8：00时，因为只有作业1到达，系统将作业1投入运行。作业1运行2小时(即10：00时)完成。由于该算法采用响应比高者优先调度算法，这样在作业1执行完后，要计算剩下三个作业的响应比，然后选响应比高者去运行。剩下三个作业的响应比为： r2=l+(10.0-8.3)／0.5=4.4 r3=l+(10.0-8.5)／0.1=16 r4=l+(10.0-9.0)／0.4=3.5 从计算结果看，作业3的响应比高，所以让作业3先运行。作业3运行0.1小时完成(即10：10时)，此时，作业2和作业4的响应比为： r2=l+(10.1-8.3)／0.5=4.6 r4=l+(10.1-9.0)／0.4=3.75 从上述计算结果看，作业2的响应比高，所以让作业2先运行。因此四个作业的执行次序为：作业1、作业3、作业2、作业4.解：四个作业的调度次序为：作业1、作业3、作业2、作业4。作业 到达 运行 开始 完成 周转 带权周转 1 8.0 2.0 8.0 10.0 2.0 1.0 2 8.3 0.5 10.1 10.6 2.3 4.6 3 8.5 0.1 10.0 10.1 1.6 16.0 4 9.0 0.4 10.6 11.0 2.0 5.0 平均周转时间 T=(2.0+2.3+1.6+2.0)／4=1.975 平均带权周转时间 W=(1+4.6+16+5)／4=6.65

三. 简答题（共4题，22分）

9. (简答题, 6分)死锁产生的原因和必要条件是什么？如何预防死锁？

正确答案：
死锁产生的原因：竞争资源和推进顺序非法。

必要条件：互斥、请求和保持、不剥夺、环路等待。

预防死锁是通过破坏死锁必要条件的一个或几个。包括：破坏请求和保持、破坏不剥夺和破坏环路等待。

10. (简答题, 5分)在作业调度中应如何确定接纳多少个作业和接纳哪些作业？

正确答案：
接纳多少个作业取决于多道程序的度，接纳哪些作业取决于调度算法。

11. (简答题, 5分)

假设系统中有下述3种解决死锁的方法：

（1）银行家算法；

（2）检测死锁，终止处于死锁状态的进程，释放进程所占有的资源；

（3）资源预分配。

在上述解决死锁的几个方法中，哪个方法允许最大的并发性？ 请按“并发性”从大到小对3种方法进行排序。

正确答案：
第（2）种方法的并发性最大，第（1）种次之，第（3）种方法的并发性最弱。

12. (简答题, 6分)试列举出三种作业调度算法，并比较其优缺点。

正确答案：
FCFS：按照作业到达系统的先后顺序依次调度，适合于长作业，不利于短作业，未考虑作业的紧迫程度，很少单独使用。

SJF：选取运行时间最短的作业优先调度，可以缩短平均周转时间，不利于长作业，未考虑作业的紧迫程度。

HRN：既考虑作业运行时间，也考虑作业等待时间，但调度之前需要计算响应比，增加了系统开销。

3.7 习题4

一. 简答题

1.什么是临界资源?什么是临界区?

【参考答案】
①在计算机中有许多资源一次仅允许一个进程使用，我们把一次仅允许一个进程使用的资源称为临界资源，如打印机和一些共享变量等。
②进程中访问临界资源的那段代码称为临界区。

2,同步机制应遵循的准则有哪些?

【参考答案】同步机制应遵循的准则主要有4个。
(1)空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进人临界区的进程立即进人临界区,以有效地利用临界资源。
(2)忙则等待。当已有进程在临界区时，表明临界资源正在被访问，因面其他试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。
(3)有限等待。对要求访问临界资源的进程，应保证其能在有限时间内进入临界区，以免陷人“死等”状态。
(4)让权等待。当进程不能进入临界区时,其应立即释放处理机，以免进程陷入“忙等”。

3.为什么各进程对临界资源的访问必须互斥?

【参考答案】临界资源本身的特性决定了它们只能被各个进程互斥地访问，如果并发执行的多个进程同时访问临界资源，则会造成系统混乱或程序执行结果不确定。这样，进程运行结果就可能不正确或者不确定。比如,两个进程并发执行如下程序段:

mov ax, (counter);
ine ax;
mov (eounter), ax;

其中，共享变量counter初值为0，对counter执行加1操作。如果允许一个进程访问counter，另一个进程也可以对其进行操作，则counter的值最终可能是正确结果2，也可能是错误结果1，即计算结果出现了不确定性。因此，各进程对临界资源的访问必须互斥地进行。

4．如何保证各进程互斥地访问临界资源?

【参考答案】为了互斥地访问临界资源，系统必须保证进程互斥地进入临界区。为此，必须在临界区前增加一段进人区代码，以检查是否有其他进程已进入临界区而在使用临界资源。若有，则进程必须等待;否则，允许进程进入临界区，同时设置标志以表示有进程正在临界区内。同样，在临界区后必须增加一-段退出区代码，用于将已有进程进人临界区访问临界资源的标志改为无进程进人临界区使用临界资源。进入区和退出区可用多种同步机制实现,如锁、信号量机制等。

二、计算题

13．若信号量的初值为2，当前值为-1，则表示有多少个等待进程?请分析。

【参考答案】信号量的初值表示系统中资源的数目，每次的P操作表示进程请求一个单位的资源，信号量进行减l操作,当信号量小于0时，表示资源已分配完毕、进程自我阻塞。如果信号量小于0．那么信号量的绝对值表示当前阻塞队列中进程的个数。因此，当前值为-1，表示有1个等待进程。

14.有m个进程共享同一临界资源,若使用信号量机制实现对某个临界资源的互斥访问,请求出信号量的变化范围。

【参考答案】某个临界资源的信号量初值为1,其是信号量的最大值。m个进程分别对临界资源发出1次请求，信号量均要执行减1操作，因此，最多可允许m个进程同时申请、此时信号量的值是1-m，为最小值。因此,信号量值的范围是1-m至1。

15．若有4个进程共享同一程序段，而且每次最多允许3个进程进入该程序段，则信号量值的变化范围是什么?

【参考答案】程序段作为共享资源，最多允许3个进程进入其中，因此设置信号量初值为3。当4个进程共享该程序段时，在每个进程中请进入时，信号量都会执行减1操作。当第1个进程申请进入时，信号量值变为2:第2个进程申请进入时，信号量值变为l;第3个进程申请进入时，信号量值变为0、第4个进程申请进入时，信号量值变为-1。因此，信号量的变化范围是3,2，1，0，-1。

三、综合应用题

16.(考研真题)3个进程P1、P2、P3,互斥地使用一个包含N(N>0)个单元的缓冲区。P,每次用produce()生成一个正整数，并用put()将其送入缓冲区的某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数，并用countodd()统计奇数的个数;P。每次用geteven()从该缓冲区中取出一个偶数，并用counteven()统计偶数的个数。请用信号量机制实现这3个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

【参考答案】定义资源信号量empty,odd、even，用于控制生产者与消费者之间的同步，其中，empty表示空缓冲区的数目，odd表示缓冲区中奇数的个数，even表示缓冲区中偶数的个数;定义互斥信号量mutex，用于实现进程对缓冲区的互斥访问。伪代码描述如下:

17.(考研真题）某银行提供了1个服务窗口和10个供顾客等待时使用的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号,等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下。

cobegin {
process顾客{从取号机上获得一个号码;等待叫号;获得服务;process营业员{while (TRUE){叫号;为顾客服务;}}	} coend

请添加必要的信号量和P、V操作或wait()、signal(操作，实现上述过程中的互斥与同步。要求写出完整的过程,说明信号量的含义并赋初值。

semaphore numget=1, seats=10,eustom=0, //numget是关于取号机互斥的信号量;信号量seats是座位的个数:信号量cuslom是顾客的个数

process顾客{P(seats);//看有没有空座位P(numget);//取号取号;V(numget);//取完号后释放取号机V(custom);等待叫号;V(seats);接受服务;}

process 营业员{P(custom);叫号:为顾客服务;}

20．桌上有一个能盛得下5个水果的空盘子。爸爸不停地向盘中放苹果或橘子，儿子不停地从盘中取出橘子享用,女儿不停地从盘中取出苹果享用。规定3人不能同时向(从)盘子中放(取）水果。试用信号量来实现爸爸、儿子和女儿这3个“循环进程”之间的同步。

【参考答案】分析:本题是生产者-消费者问题的变形，相当于一个能生产两种产品的生产者(爸爸）向两个消费者（儿子和女儿）提供产品的同步问题，因此,须设置两个不同的full信号量apple和orange，它们的初值均为0。为了描述上述同步问题，可定义如下信号量:

semaphore empty=5, orange=0, apple=0, mutex=1;

四、存储器管理（第5、6章）

4. 存储器管理方式

4.1 连续分配方式

4.1.1 连续分配方式简介

• 标准定义： 连续分配方式是指将进程所需的全部空间一次性分配在内存中的某一块连续区域。
• 通俗解释： 就好比你在房间里找一片连续的空地，把你所有的行李都放在这片地方，这就是连续分配。

4.1.2 固定分区分配（分区表）

• 标准定义： 固定分区分配是指将内存分成若干个固定大小的分区，每个分区可以分配给一个进程。
• 通俗解释： 就像把一个大的书架划分成几个固定大小的格子，每个格子可以放一本书，每个进程就像是一本书，被放在一个固定的位置。

4.1.3 动态分区分配（空闲分区表）

• 标准定义： 动态分区分配是指根据进程的实际大小分配内存，形成不连续的空间。
• 通俗解释： 就像你在书房里找到一些空闲的地方，每本书需要的地方不一样，你就根据每本书的大小找到适合的空地，这就是动态分区分配。

4.1.4 基于顺序搜索的动态分区分配算法

• 标准定义： 基于顺序搜索的动态分区分配算法是指按照内存地址顺序搜索，找到第一个满足大小要求的空闲分区进行分配。
• 通俗解释： 就像你在书房里从头到尾找一个适合放书的地方，找到第一个足够大的地方就把书放进去，这就是基于顺序搜索的动态分区分配算法。

4.1.5 分区分配算法的具体实现

1. 首次适应算法：
   • 将空闲分区链按照地址递增的次序排列，选择第一个满足大小要求的空闲分区进行分配。
   • 通俗解释： 就像你在找一个地方安置你的家具，从房间的一头开始找，找到第一个合适大小的位置就摆放家具。
2. 下次适应算法：
   • 类似首次适应算法，但从上次分配结束的位置开始搜索，以减少搜索范围。
   • 通俗解释： 类似首次适应算法，但是这次你从上次摆放的地方继续找，以减少搜索的范围，就像在书房里找书，上次找到书的地方之后再找，不用每次都从头找起。
3. 最佳适应算法：
   • 将空闲分区链按照容量从小到大顺序排列，选择第一个满足大小要求的空闲分区进行分配。
   • 通俗解释： 就好比你在书房里挑最小的地方放书，以确保每个小空间都被充分利用。
4. 最坏适应算法：
   • 将空闲分区链按照容量从大到小顺序排列，选择第一个满足大小要求的空闲分区进行分配。
   • 通俗解释： 就好比你在书房里找到一个最大的空地，把书放进去，以确保每次分配都有足够大的空间，就像是给每本书都留有大的空间。

4.1.6 分区分配算法的缺点

• 标准定义： 连续分配方式的缺点是容易产生碎片，包括外部碎片和内部碎片。
• 通俗解释： 就好比你在书房里不断地往书架上放书和取书，最后可能会出现一些空隙，有的是书架之间的，有的是每个格子里没有完全放满的，这些空隙就是碎片。

4.2 离散分配方式：基本分页存储管理方式

4.2.1 离散分配方式简介

• 标准定义： 离散分配方式是指将进程的空间分为若干个固定大小的块，这些块不需要连续，通过页表进行地址映射。
• 通俗解释： 想象一下你的电脑内存就像一片大草地，离散分配方式就好比在这片草地上划分了很多小块，每块都有自己的地址。通过一个地图（页表），你可以找到需要的块，就像在地图上找到特定位置的小块一样。

4.2.2 分页地址的地址结构

• 标准定义： 分页地址的地址结构包括页号和页内地址（位移量），通过这两个信息可以唯一确定一个地址。
• 通俗解释： 想象一本大书被分成很多页，每页都有一个页号和具体的内容。这里的页号就是告诉你在哪一页，而页内地址就是告诉你在这一页的哪个位置，两者结合起来就能找到你需要的具体信息。

4.2.3 页表

• 标准定义： 页表是为了实现从页号到物理块号的地址映射，系统为每一个进程建立了一张页面映像表，简称页表，其中每一页表项记录了相应页对应的物理块。
• 通俗解释： 想象一张巨大的表格，每行是一页，表格中的每个小格记录了该页对应的实际存储位置。通过这个表格，系统就知道如何将你书写的页号翻译成实际存储位置。

4.2.4 地址变换

• 标准定义： 地址变换是将逻辑地址（由页号和页内地址组成）转换为物理地址的过程。
• 通俗解释： 想象你在图书馆查找一本书，你拿到一张卡片（逻辑地址），上面写着书的名字和页码。地址变换就像你把这张卡片交给图书管理员，他会告诉你具体在哪个位置找到这本书。在计算机中，系统通过地址变换告诉硬件在哪里找到需要的数据。

4.2.5 具有块表的地址变换

• 标准定义
  具有块表的地址变换是一种更加灵活的映射方式，通过块表来实现逻辑地址到物理地址的转换。

• 通俗解释
  这就像是有了一份更加详细的目录，不仅可以找到具体的页号，还可以通过块表找到更加具体的物理地址，从而更快速地找到内容。

4.3 虚拟存储器管理

4.3.1 理论依据和基本概念

4.3.1.1 局部性原理

• 标准定义： 局部性原理是指程序在执行过程中，对存储器的访问呈现出一定的局部性，即一段时间内访问的地址更有可能在某个较小的范围内。
• 通俗解释： 想象一下你在图书馆学习，你不会一直在整个图书馆里乱翻书，而是更有可能在某个时间段内只关注某一类书籍或者某个专业领域。这种学习的方式就体现了局部性原理，即你在一段时间内对知识的访问集中在某个范围内。

4.3.1.2 虚拟存储器

• 标准定义： 虚拟存储器是一种将磁盘空间扩展到物理内存之外的存储技术，通过在磁盘和内存之间进行数据交换，实现了程序执行所需的存储空间。
• 通俗解释： 想象一下你的电脑内存就像书桌上的工作空间，而虚拟存储器就好比一个巨大的书柜。当你的书桌放不下更多的书时，你可以把一些书暂时放到书柜里，需要时再拿回来。虚拟存储器就是让计算机能够像这样灵活地利用磁盘空间，将不常用的数据放到磁盘上，保证内存始终留给当前需要的任务。

4.3.2 关键技术

4.3.2.1 请求调入

• 标准定义： 请求调入是指在程序执行过程中，发现所需数据不在内存中时，系统将其从磁盘加载到内存的过程。
• 通俗解释： 就像是你在阅读一本书时，需要翻到某一页，但这一页不在当前打开的书上，于是你通过翻开其他部分或者查找目录，将需要的页调到当前位置。

4.3.2.2 置换

• 标准定义： 置换是指当内存空间不足时，系统决定将当前不活跃的数据移出内存，腾出空间给即将调入的数据。
• 通俗解释： 就像是你在读一本书，书桌上只能放下一些书，当新的书需要放在桌上时，你可能会将一些不常用的书放回书架，给新书腾出空间。

4.3.3 虚拟存储器的特征

4.3.3.1 标准定义

虚拟存储器的特征包括能够让程序认为它拥有比实际物理内存更大的地址空间、允许程序在执行过程中动态加载和卸载数据、提高了系统的多道程序设计能力等。

4.3.3.2 通俗解释

• 更大的地址空间： 就好像是你的电脑有了一个更大的书桌，可以放更多的书。
• 动态加载和卸载数据： 就像是你可以根据需要随时取出或放回书，而不是一次性将所有书都摆在桌子上。
• 多道程序设计： 就像是你可以同时阅读多本书，而不必等待一本书读完再读下一本。

4.4 请求分页存储管理方式

4.4.1 请求分页存储管理的硬件支持

4.4.1.1 页表机制

• 标准定义： 页表机制是指通过页表来实现从页号到物理块号的地址映射，用于确定程序中各页在内存中的位置。
• 通俗解释： 就像是书的目录，通过查找目录中的页号，可以快速找到对应的物理块号，从而知道该页在内存的位置。

4.4.1.2 缺页中断机构

• 标准定义： 缺页中断是指当程序访问的页不在内存中时，触发的中断，系统需要将该页从磁盘加载到内存。
• 通俗解释： 就像是你在读一本书，要翻到某一页，但发现这一页不在打开的书上，于是你需要通过查找或请求，将需要的页从书架上拿到桌上。

4.4.1.3 地址变换机构

• 标准定义： 地址变换机构是指通过页表和地址变换的方式，将逻辑地址转换为物理地址的硬件机制。
• 通俗解释： 想象一下你在使用地图找到一个城市的具体位置。这个过程中，地图就好比页表，而你手中的坐标就是逻辑地址。地址变换机构就像是你根据地图上的信息，将逻辑地址（坐标）转换成实际的物理位置，帮助你准确找到目标。在计算机中，这个机构通过硬件的方式实现，确保程序能够在内存中正确访问数据。

4.4.2 缺页中断和一般中断的联系与区别

4.4.2.1 联系

• 联系： 缺页中断是一种中断机制，和一般中断一样，都是由硬件或软件触发，导致程序的正常流程被中断。

4.4.2.2 区别

• 区别： 缺页中断是特定于分页存储管理方式的一种中断，它表示程序访问的页不在内存中，需要从磁盘加载。而一般中断是指系统发生了某种事件，需要引起处理程序的注意。

通过缺页中断，系统可以在需要时动态地将数据从磁盘加载到内存，保证程序的正常执行。这种机制使得程序的地址空间可以大于实际物理内存，提高了系统的灵活性和效率。

4.5 页面置换算法

4.5.1 OPT（最佳置换算法）

4.5.1.1 标准定义

• 标准定义： OPT（Optimal Replacement）是一种理想情况下的页面置换算法，它会选择未来最长时间内不会被访问的页面进行置换。
• 通俗解释： OPT 就好比你在一家图书馆，能够预测哪本书将来最久都不会再有人借阅。一旦找到这本书，就把它从书架上拿下来，腾出空间给新的书。这个过程就是 OPT 算法的思想，总是选择最佳的替换方式。

4.5.2 FIFO（先进先出算法）

4.5.2.1 标准定义

• 标准定义： FIFO（First-In-First-Out）是一种简单的页面置换算法，它选择最早进入内存的页面进行置换。
• 通俗解释： FIFO 就好比你在超市排队结账，谁先到的就先结账离开。在计算机中，谁先进入内存的页面就先被踢出去，给后来的页面腾位置。

4.5.3 LRU（最近最少使用算法）

4.5.3.1 标准定义

• 标准定义： LRU（Least Recently Used）是一种基于页面使用历史的算法，它选择最近最久未被使用的页面进行置换。
• 通俗解释： 想象你有一个装满零食的篮子，每袋零食代表内存中的一个页面。每当你想吃零食时，你都会选择吃掉篮子里最久没吃过的那袋，这样你总是能够享用到相对新鲜的零食。LRU 算法就像是你总是选择吃掉最久没被吃过的零食一样，系统总是选择最近最少使用的页面保留在内存中，而把最久没被使用的页面替换出去，以确保内存中的数据相对较新。

这三种页面置换算法各有优劣，选择哪种算法取决于具体的应用场景和系统特点。OPT具有理论上的最优性，但实现较为困难；FIFO简单实用，但可能导致“老化”页面长时间停留在内存中；LRU在实际中表现较好，但需要维护访问时间的信息，增加了系统的开销。在不同情况下，选择适合的算法可以有效提高存储器管理的效率。

4.6 习题5

4.7 习题6

五. 输入输出系统（第7章）

5.1 I/O设备的类型

标准定义：
I/O设备可分为独占设备、共享设备和虚拟设备。

解释：

1. 独占设备：

   • 定义： 某一时刻只能被一个程序独占使用的设备。其他程序需要等待设备空闲才能使用。
   • 比喻： 就像一部独立的打印机，一次只能服务一个人，其他人需要等待。

2. 共享设备：

   • 定义： 多个程序可以同时访问和使用的设备，系统通过管理和调度来确保并发操作。
   • 比喻： 就像一个共用的公共汽车，多个人可以同时搭乘，系统会安排好谁先上车。

3. 虚拟设备：

   • 定义： 设备的逻辑功能由操作系统虚拟出来，实际物理设备可能不止一个，通过虚拟化技术提供给应用程序使用。
   • 比喻： 想象你在玩模拟城市游戏，你创建了一个虚拟的市政建筑，虽然在现实中并不存在，但在游戏中，其他虚拟角色和系统都与它进行交互。这个虚拟市政建筑就像是虚拟设备，通过软件虚拟化技术创建，为应用程序提供一种虚拟的逻辑功能。

5.2 I/O通道、I/O通道类型、通道与一般处理器的区别

1. I/O通道的标准定义：
   I/O通道（Input/Output Channel）是计算机中负责连接主存储器和外部设备的通信路径。它起到了数据传输的桥梁作用，允许外部设备和主存之间进行高速、独立的数据交换。

2. 通俗解释：
   想象I/O通道是计算机的交通管制中心，它负责管理和协调数据在主存储器和外部设备之间的流动。就像是一个交通警察，确保信息能够在系统内部畅通无阻地传递。
   I/O通道就像是计算机的高速传送带，它连接着计算机的大脑（主存储器）和外部设备，负责快速而独立地将数据传递过去。你可以把它想象成一个快递员，负责把主存储器的数据快速、可靠地送达给外部设备，或者将外部设备的数据迅速送达给主存储器。这样，计算机内外的信息就可以高效地来回传送。

3. I/O通道类型的标准定义：
   I/O通道分为三种类型：程序控制型、中断控制型和直接存储器访问（DMA）型。这些类型决定了数据传输的控制方式和效率。

4. 通俗解释：

   • 程序控制型： 像是手动操作，需要中央处理器（CPU）不断发出指令，告诉I/O通道何时开始或结束数据传输。
   • 中断控制型： 当外部设备准备好或者出现特定事件时，中断通知I/O通道启动数据传输，减轻了CPU的负担。
   • DMA型： 直接存储器访问允许外部设备和内存之间直接交换数据，不需要CPU介入，效率更高。
     想象你在操控一辆汽车，而这辆汽车就是计算机的I/O通道。有三种不同的方式来驾驶这辆车，分别对应三种I/O通道类型。第一种是“程序控制型”，就像你手动操作每个车速和方向的控制器一样，每一步都由你决定。第二种是“中断控制型”，有点像你遇到交通信号时暂时停车，等到有新指示时再继续前行。第三种是“直接存储器访问（DMA）型”，就像你设置了一个目的地，汽车可以自动沿着预定的路径行驶，而你则可以专注于其他任务，这提高了效率。不同的I/O通道类型就是决定这辆车如何驾驶，以及数据如何在计算机内部和外部之间流动的方式。

5. 通道与一般处理器的区别：
   I/O通道是专门设计用于数据传输的，与主处理器（CPU）有所区别。主处理器负责执行计算任务，而I/O通道专注于有效地管理外部设备和内存之间的数据传递，以提高整体系统性能。

• 标准定义： 通道是一种专门负责I/O设备数据传输的处理器，它独立于主处理器，通过并行、高效地处理大量数据，提高了I/O操作的速度。与一般处理器相比，通道更专注于数据传输而非通用计算。
• 通俗解释： 想象计算机是一座工厂，一般处理器就像工厂的总经理，负责全局的工作安排和决策。而通道就是专门的搬运工，他们负责将原材料（数据）从外部设备运送到工厂（主存储器），或将成品（处理好的数据）从工厂送到外部设备。通道搬运工非常擅长这个任务，可以同时搬运很多数据，而不会占用总经理（一般处理器）太多时间和精力。因此，通道和一般处理器在工作的专注程度和任务领域上有所区别。

---

5.3 I/O控制方式

1. I/O控制方式的标准定义：
   I/O控制方式指的是计算机系统中管理和协调输入/输出操作的方式。常见的方式包括程序I/O、中断I/O、DMA方式和通道方式。

2. 通俗解释：

   • 程序I/O： 就像是你亲自去超市购物，需要逐个挑选商品，主动控制整个购物过程。
   • 中断I/O： 类似于你在超市购物时，有了购物清单，当你需要的商品出现时，收银员通知你可以结账，不需要你一直等在货架前。
   • DMA方式： 像是雇佣了一名速递员，他负责将你购物清单上的商品直接送到你手上，你不需要亲自前往。
   • 通道方式： 就像是你委托了一位购物助手，他负责帮你挑选商品、结账等，你只需等待结果。

   想象你在玩一场电子游戏，而这场游戏就是计算机系统。I/O控制方式就像是你选择游戏角色与游戏互动的方式。有四种方式可以选择：

   • 程序I/O： 就像你亲自控制游戏角色的每一步，每次操作都由你来决定，但可能会花费更多时间和精力。
   • 中断I/O： 类似于你在游戏中碰到了特殊任务，需要你停下手头的操作，去处理这个任务，然后再回到原来的操作。
   • DMA方式： 好比你请了一位助手，专门负责搬运游戏中的物品，你不必亲自去搬运，可以把更多精力放在其他操作上。
   • 通道方式： 就像你雇佣了一个专业的团队，他们负责协调和管理游戏中所有复杂的操作，你只需告诉他们你的需求，剩下的交给他们处理。这种方式效率高，可以同时处理多个任务。不同的I/O控制方式就是在选择如何与游戏进行互动，以及如何协调和处理各种任务。

---

5.4 I/O缓冲技术

1. I/O缓冲技术的标准定义：
   I/O缓冲技术是一种通过在计算机系统中引入缓冲区，将输入/输出数据暂时存储起来，以提高数据传输效率的方法。

2. 通俗解释：
   想象你在使用手机浏览网页，当你打开一个网页时，页面上的图片和文字可能不是一次性全部加载完毕的，而是逐步显示。这就好比浏览器采用了一种类似于I/O缓冲技术的方法，提前加载一部分内容，让用户感觉到更快的响应速度。

想象你在一家快餐店点餐，而I/O缓冲技术就好比是你的点餐篮。当你点好餐后，服务员不会立刻把食物逐一送到你手里，而是先把你的订单放进点餐篮，然后厨房根据这个篮子里的订单一次性准备好所有的食物，最后一起交给你。这样，就避免了每点一个菜都等待厨房准备的时间，提高了整体服务效率。在计算机中，I/O缓冲技术也是类似的，通过引入缓冲区，可以将输入/输出数据先存储起来，等到一定量的数据积累后再进行高效的批量传输，提高了数据传输的效率。

---

5.5 磁盘性能的影响因素

1. 磁盘性能的标准定义：
   磁盘性能的影响因素主要包括寻道时间、旋转延迟和传输时间，这些因素共同影响着磁盘读写操作的速度。

2. 通俗解释：
   想象一下你在书架上查找一本书，首先需要找到这本书所在的书架（寻道时间），然后等待这本书刚好处于你手边（旋转延迟），最后才能够翻阅书本内容（传输时间）。整个过程中，每个步骤都会影响你获取书本信息的速度。

---

5.6 磁盘调度算法

5.6.1 FIFO（先进先出）

1. FIFO算法的标准定义：
   FIFO是一种磁盘调度算法，按照磁盘请求的先后顺序进行调度，先发出的请求先被满足。

2. 通俗解释：
   就像是你在餐厅排队，先到的人先被安排进餐，按照先来先服务的原则。

5.6.2 SSTF（最短寻道时间优先）

1. SSTF算法的标准定义：
   SSTF是一种磁盘调度算法，选择当前磁头位置最接近请求的磁道进行调度，以减少寻道时间。

2. 通俗解释：
   像是你在书架上找书，每次都选择最接近手的那本书，以最短的距离找到需要的书本。

5.6.3 SCAN（扫描）

1. SCAN算法的标准定义：
   SCAN是一种磁盘调度算法，磁头按照一个方向移动，直到碰到最边缘，然后改变方向继续移动，以此往复。

2. 通俗解释：
   想象一下你在图书馆找书，SCAN算法就像你从书架的一端开始，按照一个方向扫描书架，找到目标书籍后再改变方向，直到扫描完整个书架。这样可以比较高效地找到你需要的书籍，就像磁头在磁盘上按照一个方向移动，找到需要的数据。

5.6.4 CSCAN（循环扫描）

1. CSCAN算法的标准定义：
   CSCAN是SCAN算法的一种改进版本，磁头在到达磁盘末端时立即返回到磁盘起始位置，形成一个循环。

2. 通俗解释：
   类似于SCAN算法，但是当到达磁盘末端时，直接返回到磁盘起始位置，再次开始扫描。
   如果把SCAN算法比喻为你在图书馆来回扫描书架，那么CSCAN就是你扫描完一遍后，立即回到书架的开始重新扫描。这样做的好处是可以更加连贯地管理书架，不会漏掉任何可能需要的书籍，就像磁头在磁盘上形成一个循环，提高了数据的读取效率。

5.7 习题

见6.5

---

六、文件管理 （第8,9章）

6.1 文件系统的功能

6.1.1 文件存储空间的管理

标准定义：
文件系统负责有效管理存储设备上的文件存储空间，确保文件能够被合理地存储、检索和组织。
通俗解释：
文件系统就像是你的个人图书馆管理员，负责管理书架上的图书。它要确保每本书都有合适的位置，可以轻松找到，还需要保证新添的书籍能够有序地放入。同样，文件系统管理文件的存储空间，让文件可以被方便地存储、找到和整理，确保计算机上的数据有序可控。

6.1.2 目录管理

标准定义：
文件系统通过目录管理，组织和维护文件的层次结构，以方便用户查找、访问和组织文件。

通俗解释：
目录管理就像是你整理书架上的书籍一样。每本书有一个特定的位置，而目录就是一个书籍清单，告诉你每本书在哪里。文件系统的目录管理类似，它创建了一个文件清单，让你可以方便地查找和访问文件，就像在图书馆的目录中找到书籍一样。这样，你可以更轻松地组织和管理计算机上的文件。

6.1.3 文件的读写管理和保护

标准定义：
文件系统负责管理文件的读写操作，同时确保文件只能被授权的用户或进程访问，以保护文件的完整性和安全性。

通俗解释：
文件的读写管理就像是图书馆的规定，只有借书证的人才能借书，而文件系统就是为文件颁发了一种“文件借书证”，只有持有这个证件的人或程序才能对文件进行读写操作。这样，就能够有效地保护文件，防止未经授权的人或程序进行随意操作，确保文件的安全性和完整性。

6.2 文件的逻辑结构、物理结构概念

6.2.1 文件的逻辑结构

标准定义：
文件的逻辑结构是指文件中数据元素之间的关系和组织方式，包括文件的组织形式、数据的表示方法等。

通俗解释：
文件的逻辑结构就像一本书的目录和章节安排，它定义了文件中数据元素之间的关系和组织方式。想象一下一本小说，它有序的章节和段落就构成了逻辑结构，让读者可以按照一定的组织方式理解故事。文件的逻辑结构也是为了让计算机更好地理解和处理文件中的数据，就像读者通过目录找到感兴趣的章节一样。

6.2.2 文件的物理结构

标准定义：
文件的物理结构是指文件在存储设备上的实际存储方式，包括文件的存储布局、磁盘块的组织等。

通俗解释：
文件的物理结构就像一本书在书架上的具体存放方式，它定义了文件在存储设备上的实际存储布局。想象一下你的书架，每本书都占据一定的空间，文件的物理结构也是为了将数据有序地存储在计算机的存储设备上，就像书籍有特定的位置一样。这种存储方式能够帮助计算机更高效地读取和写入文件中的数据。

6.3 外存的分配方式

6.3.1 顺序式结构

标准定义：
外存的顺序式结构是指文件在存储设备上按照逻辑顺序依次存储，形成一个连续的数据块。

通俗解释：
顺序式结构就像你在一张纸上按照顺序写下的文字，每行都连接着上一行，文件在外存中也是按照逻辑顺序一个接一个地存储，就像连续的文字一样。这种结构使得文件的读取和写入相对简单，就像你可以顺着纸上的文字一行一行读取一样。

6.3.2 链接式结构

标准定义：
外存的链接式结构是指文件在存储设备上通过链接方式相互连接，形成一个链表结构。

解释：
想象一本书的每一页都贴着指向下一页的标签，你可以根据标签跳转到其他页面。链接式结构就是通过这种方式连接文件的不同部分，你可以通过链接找到文件的特定位置。
通俗解释：
链接式结构就像你在纸上画的一组相互连接的箭头，每个箭头指向下一个位置。文件在外存中也可以通过链接方式相互连接，形成一个链表，每个部分都知道下一个部分在哪里。这种结构使得在文件中插入或删除数据变得更加灵活，就像你可以在图上添加或删除箭头一样。

6.3.3 索引式结构

标准定义：
外存的索引式结构是指使用索引表来记录文件的存储位置，通过索引查找实际数据块。

解释：
比如一本书有一张目录，列出了关键词和对应的页码。你可以通过查阅目录找到关键词对应的页码，然后直接翻到该页。索引式结构就是通过索引表来快速定位文件的存储位置，加速检索过程。
通俗解释：
索引式结构就像一本书的目录，记录着每个章节的页码，文件在外存中也有一个索引表，记录着每个数据块的位置。当需要查找特定数据时，系统可以先查找索引表，找到对应的位置，然后直接跳到这个位置获取数据，就像你通过书的目录找到特定章节一样，这种结构有助于快速定位和获取文件中的数据。

6.4 Unix的混合索引方式

标准定义：
Unix的混合索引方式是一种文件索引结构，其中的索引结点（i-node）包含13个地址项（iaddr(0)~iaddr(12)），用于管理文件的存储位置。

解释：
想象一个文件像一本书，而索引结点就像书的目录。Unix的混合索引方式相当于在目录上设置了多个指针，以便更有效地定位书中的不同章节。

1. iaddr(0)~iaddr(9)用来存放直接地址，就像目录中列出直接可以查找的章节一样，直接指向数据块。
2. iaddr(10)用来存放一次间接地址，类似于目录中有一个链接，通过这个链接你可以找到另一个目录，进而找到特定章节。
3. iaddr(11)用来存放二次间接地址，扩展了查找的范围，就像有了两级目录结构。
4. iaddr(12)用来存放三次间接地址，进一步增加了查找的深度，使得文件可以更加灵活地存储和组织。

通俗解释：
Unix的混合索引方式就像你在一张地图上看到的一个标志，上面有13个箭头，每个箭头指向一个地点。这个标志就像Unix系统中的索引结点，它包含13个地址项，每个项指向文件在存储设备上的一个位置。当需要找到文件时，系统可以根据这些地址项直接跳转到相应的位置，就像你通过地图上的标志找到具体的地点一样。这种结构的设计有助于高效地管理文件的存储位置。

6.5 存储空间管理

标准定义：
存储空间管理是文件系统用于有效组织和分配存储设备上的空间的一系列策略和方法，包括空闲表法、位示图法和成组链接法等。

解释：
存储空间管理就像图书馆管理员对书架上的书籍进行整理和分配一样，确保每本书都有自己的位置。空闲表法记录可用的空间，位示图法标记已使用的空间，而成组链接法则是将空间按组织单元进行管理，以提高效率。

1. 空闲表法：

   • 定义： 空闲表法通过维护一张表格来记录哪些存储块是空闲的，哪些被占用。
   • 比喻： 就像图书馆管理员维护一张书架上哪些位置有书、哪些位置是空的记录表一样，方便查找可用的存储块。

2. 位示图法：

   • 定义： 位示图法使用位图来表示存储块的占用情况，每个位对应一个存储块，0表示空闲，1表示占用。
   • 比喻： 类似于城市停车场入口的指示牌，每个车位都有一个小灯，绿灯表示空闲，红灯表示占用，司机通过观察指示牌就能知道哪里有空车位。

3. 成组链接法：

   • 定义： 成组链接法将空闲存储块以链表的形式组织，每个存储块中包含指向下一个空闲块的指针。
   • 比喻： 就像一串串的火车车厢，每个车厢上都有一个指示下一辆车的标志，当需要添加或释放车厢时，只需调整指针即可。

这些管理方法都旨在高效地组织存储空间，确保系统可以有效地存储和检索数据。

通俗解释：
存储空间管理就像你在书架上安排图书的方式，确保每本书都有一个适当的位置。文件系统通过一系列策略和方法来有效地组织和分配计算机存储设备上的空间，就像你在书架上安排图书一样。有些文件系统使用空闲表法，记录可用的空间；有些使用位示图法，通过位图表示每个存储块的占用情况；还有一些使用成组链接法，将存储空间组织成一组一组的块。这些方法有助于系统高效地利用存储资源。

6.5 习题

一.简答题（共6题,65.0分）

1、有哪几种I/O控制方式？各适用于何种场合？

正确答案：
I/O控制方式包括：程序I/O方式、中断I/O控制方式、DMA控制方式、通道控制方式。程序I/O方式适用于早期的计算机系中，并且是无中断的计算机系统；中断I/O控制方式是普遍用于现代的计算机系统；DMA方式适用于I/O设备为块设备时在和主机进行数据交换的一种I/O控制方式，当I/O设备和主机进行数据交换是一组数据块时通常采用通道I/O控制方式，但此时要求系统必须配置相应的通道及通道控制器。

2、引入缓冲的主要原因是什么？缓冲区都有哪些组织形式？

正确答案：
引入缓冲区的目的是：缓和CPU与I/O设备之间速度不匹配的矛盾：减少对CPU的中断频率：放宽CPU对中断响应时间的限制；解决数据力度不匹配的问题；提高CPU和I/O设备之间的并行性。
缓冲区的组织形式包括：单缓冲、双缓冲、循环缓冲和缓冲池。
答案解析：

3、目前的磁盘调度算法有哪几种？每种算法优先考虑的问题是什么？

正确答案：
日前常用的磁盘调度算法有：先来先服务、最短寻道时间优先及扫描等算法。
（1）先来先服务算法优先考虑进程请求访问磁盘的先后次序：
（2）最短寻道时问优先算法优先考虑要求访问的磁道与当而磁头所在磁道距离是否最近；
（3）扫描算法考虑欲访间的磁道与当前磁道间的距离，更优先考虑磁头当前移动方向。

4、按文件的组织方式可将文件分为哪几种类型？

正确答案：
顺序文件、索引文件和索引顺序文件

5、目前广泛采用的目录结构有哪些？它有什么优点？

正确答案：
日前广泛采用的日录结构是树型目录结构。它具有以下优点：
（1）能有效提高对目的检索速度；
（2）允许文件重名：由于在树型结构的文件系统中，是利用文件路径名来检索文件的，故允许每个用户在自己的分目录中使用与其他用户文件相同的名字；
（3）使于实现文件共享:在树型目录中，用户可通过路径名来共享其他用户的文件，也可将一个共享文件链接到自己的目录下。

6、目前常用的外存组织方式有哪些？试比较其优缺点。

正确答案：
顺序文件、链接文件和索引文件。
（1）顺序文件：简单，容易实现；顺序访问速度快。但必须事先知道文件的长度，文件长度不能动态增长。要求连续存储空间，删除文件的某部分后产生外部碎片。严重降低外存空间的利用率。
（2）链接文件：不要求连续分配，消除了外部碎片；文件可动态增长、插入、删除。但只适宜顺序存取；磁头移动距离多；指针链接可靠性降低；指针占用空间。
（3）索引文件：便于动态增长，便于随机存取，无外部碎片。 但增加索引表的空间开销，存取文件需两次访问外存。

二.计算题（共3题,35.0分）

1、设有如下磁道访问请求序列：

23，5，98， 14，66，25，78，34，66，74，56，87，12，39，71，49，58
当前磁头在50道，上次访问的磁道是18道。
试计算SSTF算法、SCAN和CSCAN三种调度算法下的平均寻道长度，并比较结果。
正确答案：

2、一个磁盘的转速是3000rpm，盘面划分成10个扇区，则读取一个扇区的时间是多少？

正确答案：
磁盘旋转一周需要的时间=1/3000rpm=1/50rps=20ms
每个盘面10个扇区，则读取一个扇区的时间=20/10=2ms

3、设文件索引结点中有7个地址项，其中4个地址为直接地址，2个地址为一级间接索引，1个地址二级间接索引，每个地址项大小为4B，若磁盘索引块和磁盘数据块的大小均为256B，则可表示的单个文件最大长度是多少？

正确答案：
磁盘每个数据块的大小是256B，则一个数据块中能存储256/4=64个地址项，4个直接地址指向的数据块大小为：4*265B=1024B=1KB；2个一级间接地址所指向的数据块大小为：2 * 64 * 256B=32KB；1个二级间接地址所指向的数据块大小为：64 * 64 * 256B=1024KB，则7个地址所指向的数据块的总大小为：1KB+32KB+1024KB=1057KB。