第十章 操作系统
10.1 操作系统的角色
- 应用软件(application software): 帮助我们解决现实世界问题的程序。
- 系统软件(system soffware):管理计算机系统并与硬件进行交互的程序。
- 操作系统(operatingsystem):管理计算机资源并为系统交互提供界面的系统软件。
一台计算机通常只有一个活动的操作系统， 在系统运行中负责控制工作。计算机硬件是靠电线连接的，初始时载人永久性存储器(ROM)中存储的一-小组系统指令。这些指令将从二级存储器(通常是硬盘)中载人大部分系统软件。最终将载人操作系统软件的所有关键元素，执行启动程序，提供用户界面，系统就准备就绪了。这个过程叫作引导 计算机 。术语“引导”来自于“靠自己的努力振作起来”这一思想，这也正是计算机开机后它所做的事情。
计算机可以具备两个或者更多个操作系统，用户在计算机开机时可以选择使用哪个操作系统。这种配置称为双引导 或多引导 系统。不过，任何时候都只有一个操作系统在控制计算机。
10.1.1 内存、进程与CPU管理
- 多道程序设计(multiprogramming): 同时在主存中驻留多个程序，由它们竞争CPU的技术。
- 内存管理(memory management):了解主存中载有多少个程序以及它们的位置的动作。帕讯进程(process): 程序执行过程中的动态表示法。
- 进程管理( process management):了 解活动进程的信息的动作 。
- CPU调度(CPU scheduling):确定主存中的哪个进程可以访问CPU以便执行的动作。
记住，操作系统自身也是必须执行的程序，所以在内存中也要和其他系统软件及应用程序一起管理和维护OS进程。执行OS的CPU就是执行其他程序的CPU,因此也要把OS进程排人竞争CPU的队列中。
在深人探讨资源(如主存和CPU)管理前，还需要介绍一些般的概念，
10.1.2 批处理
现在术语“批”表示的是一个系统，在这个系统中，程序和系统资源的协作与执行不需用户和程序之间的交互。现代操作系统中的批处理概念允许用户把一组OS命令定义为一个批文件，以控制一个大型程序或一组交互程序的处理。
10.1.3 分时
- 分时(timesharing):多个交互用户同时共享CPU时间的系统。
- 虚拟机(virtual machine):分时系统创建的每个用户都有专有机器的假象。
- 主机(mainframe):一个大型的多用户计算机，通常与早期的分时系统相关。
- 哑终端(dumb terminal):在早期的分时系统中用户用于访问主机的一.套显示器和键盘。
10.1.4 其他OS要素
- 操作系统也已经发展成支持计算机用法的这些变化了。
- 操作系统还必须把计算机通常要连接到网络这个因素考虑在内。
- 操作系统要负责与各种各样的设备通信。
- 操作系统的最后一个要素是需要支持实时系统的。
- 实时系统(real-time system):应用程序的特性决定了响应时间至关重要的系统。
- 响应时间(response time):收到信号和生成响应之间的延迟时间。
10.2 内存管理
本章前面介绍过多道程序设计环境，也就是在主存中同时驻留多个程序(和它们的数据)。因此，操作系统必须采用下列技术:
- 跟踪一个程序驻留在内存的什么位置以及是如何
驻留的 - 把逻辑程序地址转换成实际的内存地址
程序中到处都是对变量的引用和对程序其他部分的引用。在编译程序时，这些引用将被转换成数据或代码驻留的内存地址。
- 逻辑地址(logical address):对一个存储值的引用，是相对于引用它的程序的。
- 物理地址(physical address):主存储设备中的真实地址。
在编译程序时，对标识符(如变量名)的引用将被转化为逻辑地址。当程序最终载入内存时，每个逻辑地址将被转换成对应的物理地址。逻辑地址和物理地址间的映射叫作地址联编。 把逻辑地址联编到物理地址的时间越迟，得到的灵活度越大 。逻辑地址使得程序可以在内存中移动，或者每次载入不同的位置。只要知道程序存储的位置，就可以确定任何逻辑地址对应的物理地址。
- 地址联编(address binding):逻辑地址和物理地址间的映射。
10.2.1 单块内存管理
- 单块内存管理( single contiguous memory mangement):把应用程序载人一段连续的内存区域的内存管理方法。
单块内存管理法的优点在于实现和管理都很简单，但却大大浪费了内存空间和CPU时间。应用程序一般不可能需要操作系统剩余的所有空间，而且在程序等待某些资源的时候，还会浪费CPU时间。
10.2.2 分区内存管理
- 固定分区法(fixed-partition technique ):把内存分成特定数目的分区以载人程序的内存管理方法。
- 动态分区法( dynamic-partition technique):根据容纳程序的需要对内存分区的内存管理方法。
- 基址寄存器(baseregister):存放当前分区的起始地址的寄存器。
- 界限寄存器(bounds register):存放当前分区的长度的寄存器。
那么，对于一个新程序， 应该分配给它哪个分区呢?下面有三种常用的分区选择法:
- 最先匹配，即把第一个足够容纳程序的分区分配给它。
- 最佳匹配，即把最小的能够容纳程序的分区分配给它。
- 最差匹配，即把最大的能够容纳程序的分区分配给它。
在固定分区法中，最差匹配没有意义，因为它将浪费较大的分区。最先匹配和最佳匹配适用于固定分区。但在动态分区中，最差匹配常常是最有用的，因为它留下了最大可能的空白分区，可以容纳之后的其他程序。
分区内存管理同时把几个程序载人内存，从而可以有效地利用主存。但要记住，一个分区必须要能够容纳整个程序。虽然固定分区比动态分区容易管理，但却限制了进来的程序的机会。系统本身可能有足够的空间容纳这些程序。在动态分区中，作业可以在内存中移动，以创建较大的空白分区。这个过程叫作压缩 。
10.2.3 页式内存管理
- 页式内存管理法( paged memory technique):把进程划分为大小固定的页，载人内存时存储在帧中的内存管理方法。
- 帧(frame):大小固定的一部分主存， 用于存放进程页。
- 页(page):大小固定的一部分进程 ，存储在内存帧中。
- 页映射表(Page Map Table, PMT): 操作系统用于记录页和帧之间的关系的表。
分页的优点在于不必再把进程存储在连续的内存空间中。这种分割进程的能力把为进程寻找一大块可用空间的问题转化成了寻找足够多的小块内存。
页式内存管理系统中的逻辑地址与分区系统中的一样，都是从一个相对于程序起始点的整数值开始。但这个地址被转换成两个值————页编号和偏移量。用页面大小除逻辑地址得到的商是页编号，余数是偏移量。因此，如果页面大小是1024，那么逻辑地址2566对应的就是进程的第2页的第518个字节。逻辑地址通常被表示为<页编号，偏移量>，如<2，518>。
要生成物理地址，首先需要查看PMT,找到页所在的帧的编号，然后用帧编号乘以帧大小，加上偏移量即可。例如图10-8 中的例子，如果进程1是活动的，逻辑地址<1, 222>将被进行如下处理:进程1的页面1存储在帧12中，因此这个逻辑地址对应的物理地址是12 x 1024+222=12510。
注意，有两种逻辑地址是无效的，一种是越过了进程的界限，一种是偏移量大于帧大小 。
- 请求分页( demand paging):页式内存管理法的扩展，只有当页面被引用(请求)时才会被载人内存。
- 页面交换(page swap):把一个页面从二级存储设备载人内存，通常会使另一个页面从内存中删除。
- 虚拟内存(virtualmemory):由于整个程序不必同时处于内存而造成的程序大小没有限制的假象。
- 系统颠簸(thrashing): 频繁的页面交换造成的低效处理。
10.3 进程管理
10.3.1 进程状态
在计算机系统的管理下，进程会历经几种状态。即进入状态、准备执行、执行、等待资源以及执行结束。
- 进程状态：在操作系统的管理下，进程历经的概念性阶段
下面来分析在进程的每个状态会发生哪些事情。
- 在创建状态 ，将创建一个新进程。
- 在准备就绪状态 中，进程没有任何执行障碍。
- 运行状态 下 的进程是当前CPU执行的进程。
- 等待状态 下的进程是当前在等待资源(除了CPU以外的资源)的进程。
- 终止状态 下的进程已经完成了它的执行，不再是活动进程。此时，操作系统不再需要维护有关这个进程的信息。
注意，可能同时有多个进程处于准备就绪或等待状态，但只有一个进程处于运行状态。
10.3.2 进程控制块
- 进程控制块(PCB)：操作系统管理进程信息使用的数据结构
- 上下文切换：当上一个进程移出CPU，另一个进程取代它时发生的寄存器信息。
通常，每个状态由一个PCB列表表示，处于该状态的每个进程对应一个PCB。当进程从一个状态转移到另一个状态时，它对应的PCB也会从一个状态列表中转移到另一个状态列表。新的PCB是在最初创建进程(新状态)的时候创建的，将一直保持到进程终止。
PCB存储了有关进程的各种信息，包括程序计数器的当前值(说明了进程中下一条要执行的指令)。 如图10-8的生命周期所示，进程在执行过程中可能会被中断多次。每次中断时，它的程序计数器的值将被保存起来，以便当它再次进人运行状态时可以从中断处开始执行。
PCB还存储了进程在其他所有CPU寄存器中的值。记住，只有一个CPU,因此只有一套CPU寄存器。 这些寄存器存放的是当前执行的进程的值(处于运行状态的进程)。每当--个进程进人了运行状态，当前正在运行的进程的寄存器值将被存人它的PCB,新运行的进程的寄存器值将被载人CPU。这种信息交换叫作上下文切换。
PCB还要维护关于CPU调度的信息，如操作系统给予进程的优先级。 它还包括内存管理的信息，如(分区系统的)基址寄存器和界限寄存器的值或(页式系统的)页表。最后，PCB还具有核算信息，如账户、时间限制以及迄今为止使用的CPU时间。
10.4 CPU调度
- 非抢先调度(nonpreemptive scheduling):当当前执行的进程自愿放弃了CPU时发生的CPU调度。
- 抢先调度( preemptive scheduling):当操作系统决定照顾另一个进程而抢占当前执行进程的CPU资源时发生的CPU调度。
通常用特殊的标准(如进程的周转周期)来评估调度算法。所谓周转周期，是从进程进人准备就绪状态到它退出运行状态的时间间隔。进程的平均周转周期越短越好 。
- 周转周期(turnaround time):从进程进人准备就绪状态到它最终完成之间的时间间隔，是评估CPU调度算法的标准。
10.4.1 先到先服务
在先到先服务(FCFS)调度方法中，进程按照它们到达运行状态的顺序转移到CPU。FCFS调度是非抢先的。一旦进程获得了CPU的访问权，那么除非它强制请求转入等待状态(如请求其他进程正在使用的设备)，否则将一直占用CPU。
FCFS算法很容易实现，但却因不注意某些重要因素(如服务时间的需求)而变得复杂。虽然我们在计算周转周期的时候使用了服务时间，但是FCFS算法却没有用这些信息来帮助确定最佳的进程调度顺序。
10.4.2 最短作业优先
最短作业优先( SJN) CPU调度算法将查看所有处于准备就绪状态的进程，并分派一个具有最短服务时间的。和FCFS一样，它通常被实现为非抢先算法。
注意，SJN算法是基于未来信息的。也就是说，它将把CPU给予执行时需要最短时间的作业。这个时间基本上是不可能确定的。因此要运行这个算法，每个进程的服务时间是操作系统根据各种概率因素和作业类型估算的。但如果估算错误，算法的前提就崩溃了，它的性能将恶化。
SJN算法是可证明最佳的，意思是如果知道每个作业的服务时间，那么相对于其他算法来说，SJN算法能使所有作业生成最短的周转周期 。
但是，由于我们不可能绝对地明了未来，所以只能猜测并且希望这种猜测是正确的 。
10.4.3 轮询法
CPU的轮询法将把处理时间平均分配给所有准备就绪的进程。该算法建立单独的时间片(或时间量子)，即在每个进程被抢占并返回准备就绪状态之前收到的时间量。被抢占的进程最终会得到其他的CPU时间片。这个过程将持续到进程得到了完成所需的全部时间从而终止了为止。
- 时间片(time slice);在CPU轮询算法中分配给每个进程的时间量。
注意，轮询算法是抢先的。时间片到期，进程就会被强制移出CPU,即从运行状态转移到准备就绪状态。
只能说，对于某套特定的进程，， 种算法比另一 种算法有效。算法有效性的一般分析要复杂得多。
CPU的轮询算法可能是应用最广泛的。它一般支持所有的作业，被认为是最公平的算法。
第十一章 文件系统和目录
11.1 文件系统
磁盘上的数据都存储在文件中，这是在电子媒介上组织数据的一种机制。所谓文件，就是相关数据的有名集合。从用户的角度来看，文件是可以写人二级存储设备的最小数据量。用文件组织所有信息呈现出一个统的数据 存储视图。文件系统是操作系统提供的一个逻辑视图，使用户能够按照文件集合的方式管理数据。文件系统通常用目录组织文件。
- 文件(file): 数据的有名集合，用于组织二级存储设备。
- 文件系统(file system):操作系统为它管理的文件提供的逻辑视图。目录(directory):文件的有名分组。
11.1.1 文本文件和二进制文件
- 文本文件(text file):包含字符的文件。
- 二进制文件(binary file):包含特定格式的数据的文件，要求给位串一一个特定的解释。
有些信息有字符表示法，通常使人更容易理解和修改。虽然文本文件只包括字符，但是这些字符可以表示各种各样的信息。例如，操作系统会将很多数据存储为文本文件，如用户账号的信息。用高级语言编写的程序也会被存储为文本文件，有时这种文件叫作源文件 。用文本编辑器可以创建、查看和修改文本文件的内容，无论这个文本文件存储的是什么类型的信息。
而有些信息类型则是通过定义特定的二进制格式或解释来表示数据，以使其更有效且更符合逻辑。只有用专门解释这种类型的数据的程序才能够阅读或修改它。例如，存储图像信息的文件类型有很多，包括位图、GIF、JPEG和TIFF等。第3章中介绍过，即使它们存储的是同一个图像，它们存储信息的方式也不同。它们的内部格式是专有的，要查看或修改一种特定类型的二进制文件，必须编写专用的程序。这就是处理GIF图像的程序不能处理TIFF图像的原因。
有些文件你认为是文本文件，其实它并不是。例如，在字处理程序中输人并存储在硬盘中的报表。这个文档实际上被存储为一个二进制文件，因为除了文档中存储的字符外，它还包括有关格式、样式、边界线、字体、颜色和附件(如图形或剪贴画)的信息。有些数据(字符自身)被存储为文本，而其他信息为了存人文件则需要每个文字处理程序都有自己的格式。
11.1.2 文件类型
- 文件类型(file type):文件(如Java程序或Microsoft文档)中存放的关于类型的信息。
- 文件扩展名(fileextensionn):文件名中说明文件类型的部分。
11.1.3 文件操作
在操作系统协助下，可以对文件进行下列操作：
- 创建文件
- 删除文件
- 打开文件
- 关闭文件
- 从文件中读取数据
- 把数据写入文件
- 重定义文件中的当前文件指针
- 把数据附加到文件的结尾
- 删减文件(删除它的内容)
- 重命名文件
- 复制文件
无论何时，一个打开的文件都有一个当前文件指针(一个地址)，说明下一次读写 操作要发生在什么位置。有些系统还为文件分别设置了读指针和写指针。所谓读文件 ，是指操作系统提交文件中从当前文件指针开始的数据的副本。发生读操作后，文件指针将被更新。写信息 是把数据存储到由当前文件指针所指向的位置，然后更新文件指针。通常，操作系统允许用户打开文件以便进行写操作或读操作，但不允许同时进行这两项操作 。
11.1.4 文件访问
- 顺序文件访问(sequential file access):以线性方式访问文件中的数据的方法。
- 直接文件访问(direct file access):通过指定逻辑记录编号直接访问文件中的数据的方法。
11.1.5 文件保护
在多用户系统中，文件保护的重要性居于首要地位。也就是说，除非是特许的，否则我们不想让一个用户访问另一个用户的文件。确保合法的文件访问是操作系统的责任。不同操作系统管理文件保护的方式不同。无论哪种情况，文件保护机制都决定了谁可以使用文件，以及为什么目的而使用文件。
例如，UNIX操作系统中的文件保护设置有三类，即Owner、Group和World。在每种类别下，你可以决定一个文件是可读的、可写的还是可执行的。采用这种机制，如果可以对一个文件进行写操作，就可以对它进行删除操作。
每个文件都由一个特定用户所拥有，通常是文件的创建者。Owner 通常具有文件的最高访问许可。一个文件可能具有一一个相关的组名，分组只是一个用户列表。一个关联组中的用户都具有Group许可。例如，对于从事一个项目的所有用户可以这样分组。最后，访问系统的用户需要具有World许可。由于这些许可把访问权给予了最大数量的用户，所以它们通常是最受限制的。
注意，没有用户具有该文件的执行特权，因为它是一个数据文件，不是一个可执行的程序。
虽然其他操作系统实现保护机制的方式不同，但目的是相同的，即控制文件的访问，以防止蓄意获取不正当访问的企图，以及最小化那些由出于好意的用户不经意引起的问题。
11.2 目录
11.2.1 目录树
- 目录树(directory tree):展示文件系统的嵌套目录组织的结构。
- 根目录(root directory):包含其他所有目录的最高层目录。
无论何时，你都可以认为自己在文件系统中的某个特定位置(即特定的子目录)工作。这个子目录叫作当前工作目录。只要在文件系统中“移动”，当前工作目录就会改变。
- 工作目录(working directory):当前活动的子目录。
注意，UNIX环境的根目录是用/表示的。
11.2.2 路径名
- 路径(path):文件或子目录在文件系统中的位置的文本名称。
- 绝对路径( absolute path):从根目录开始，包括所有后继子目录的路径。
- 相对路径(relative path):从当前工作目录开始的路径。
11.3 磁盘调度
- 磁盘调度：决定先满足哪个磁盘I/O请求的操作
对我们的讨论来说，最重要的一点是在任意时刻都有一组读写头在所有盘片的特定柱面上盘旋。记住，寻道时间是读写头到达指定柱面所花费的时间。等待时间是盘片旋转到正确的位置以便能读写数据所花费的时间。
在这两个时间中， 寻道时间的要求更高，因此它是磁盘调度算法处理的重点 。
11.3.1 先到先服务磁盘调度法
第10章介绍过一种叫作先到先服 务(FCFS)的CPU调度算法。类似的算法同样适用于磁盘调度。虽然它不是最有效的磁盘调度算法，但却是最容易实现的。
11.3.2最短寻道时间优先磁盘调度法
最短寻道时间优先(SSTF)磁盘调度算法将通过尽可能少的读写头移动满足所有未解决的请求。这种方法可能会在满足-个请求后改变读写头的移动方向。
虽然这种方法不能保证读写头的整体移动最少，但通常比FCFS算法有所改进。不过这种方法会带来一个重要问题。假设已有的请求还未解决，而新的请求仍然源源不断地到来，并且新的请求总是比早期的请求所需要的柱面离当前位置更近。
那么从理论上来说，早期的请求将永远得不到满足，因为不断到来的请求总有优先权。这种情况叫作饿死
先到先服务磁盘调度算法不会出现饿死的情况。
11.3.3 SCAN磁盘调度法
在计算领域中，算法分析的经典例子是为使电梯到达有人等候的楼层而设计的方案。一般说来，电梯都是从一端移到另外一端( 即从建筑的顶层到底层)，为搭乘请求服务，然后再从底层上到顶层，为另外的请求服务。
SCAN磁盘调度算法的工作方式与之类似，只是在磁盘调度算法中没有上下移动，而是读写头向轴心移动，然后再向盘片边缘移动，就这样在轴心和盘片边缘之间来回移动。
让我们对前面的请求序列执行这个算法。与其他算法不同的是，我们要决定读写头最初移动的方向。
不可能出现饿死现象，因为每个柱面都会被依次处理到。
这种算法的一些变体能用各种方法提高它的性能。例如，对盘片边缘柱面的请求可能需要等读写头从边缘移到轴心再从轴心移回到边缘。为了减少平均等待时间，环形SCAN算法把磁盘看作环而不是磁盘。也就是说，当读写头达到一端后直接返回另一端，之间不再处理请求。
另一种变体则是最小化到轴心和到盘片边缘的移动极限。读写头只移动到请求的最外面或最里面的柱面，不再移动到盘片边缘或轴心。在移动到下一个请求的柱面之前，有种算法会检查未处理的请求的列表，判断当前移到的方向是否正确。这种变体叫作LOOK磁盘调度算法，因为它会预先判断读写头是否应该继续按照当前的方向移动。