数据库系统工程师操作系统

第一章操作系统概述操作系统是计算机系统中非常重要的系统软件，它是紧挨着硬件的第一层 软件，提供其它软件的运行环境，可以将其看成是用户与硬件的接口， 是整个计 算机系统的控制和指挥中心。1.1操作系统功能一、操作系统的定义操作系统是计算机系统中一个系统软件，它是一组用以控制、管理计算机系 统中软、硬件资源，提高资源管理效率、方便用户使用计算机的程序集合。二、操作系统的特征并行性、共享性是操作系统的特征。三、系统的层次结构没有任何软件的计算机称之为裸机，用户所使用的计算机系统通常是经过若 干次软件的扩充而得到的。但第一层扩充的软件必须是操作系统， 图3.1表示了 系统的层次结构。应用程序调试工具编辑工具连接装配程序编译程序解释程序汇编程序操作系统计算机硬件（裸机）图3.1系统的层次四、操作系统的功能操作系统负责管理计算机系统的所有资源，并调度这些资源的使用。具体来 说，其主要功能有：处理机管理、存储管理、设备管理、文件管理、作业管理五方面。1.2操作系统的类型对于计算机不同的应用领域，人们对计算机的要求也是不尽相同的，对于 计算机操作系统的性能要求、使用方式也不相同。因此，形成了多种操作方式的 操作系统，其基本类型有：批处理系统、分时系统、实时系统、个人计算机操作 系统、网络操作系统和分布式操作系统。1.3操作系统的硬件环境一、处理机状态与程序状态字计算机系统都有自己的指令系统，在多道程序设计系统中，指令系统分为 “特权指令”与“非特权指令”。特权指令仅能由操作系统使用，如设置时钟、 清内存等为特权指令；其它指令为非特权指令，用户只能使用非特权指令。在系统中,处理机（CPU会在系统程序和用户程序间切换，当CPU执行系统程序时，称处理机处于“管态”，当CPU执行用户程序时，称其处于“目态”程序状态字（PSW是用来控制指令执行顺序并且保留和指示与程序有关的 系统状态。一般包括三部分内容：程序基本状态（指令地址、条件码、管目态位 等）；中断码；中断屏蔽位。每个程序都有一个程序状态字，但整个系统设置一 个程序状态字寄存器，存放当前正在运行程序的程序状态字。二、中断机构所谓中断，即是CPU对系统所发生的异步事件的反应。当发生中断时，保 护现场后，CPU暂停当前的处理而转去执行相应的处理，处理完成再转回执行被 中断的程序。其过程是由软、硬件共同完成的。对于某些程序，不希望在其执行过程中被中断所打断，这可通过在该程序 的程序状态字（PSW中设置中断位来实现，即中断屏蔽。此时即使发生中断， CPU也暂不响应。三、定时装置由于系统的需要，硬件必须提供定时装置（即时钟） ，以处理与时间有关的 操作，时钟分为绝对时钟和相对时钟两种。四、通道在中型以上的系统中设有通道，通道也称为 I/O 处理机，专门用来处理系 统的I/O操作。CPU只负责执行机器指令，当出现I/O时将其交给通道，这样可 极大地提高系统的并行性。五、地址映射与存储保护 在多道程序设计系统中，用户编写程序时是不知道程序运行时所在内存地 址，因此用户只能使用相对地址（逻辑地址） ，这样系统必须提供地址映射机构 负责将程序中的相对地址转换为实际的内存地址。另外，在系统还必须防止内存中的多个程序之间的相互干扰、破坏，系统 的存储保护应包括地址越界保护和存取控制保护。系统一旦发生相关的非法操 作，将产生中断交由操作系统处理。1.4 操作系统与用户的接口 用户使用计算机系统时，与系统的接口有两种：系统调用和作业控制。一、系统调用 操作系统往往编制了许多不同功能的子程序（例如，读文件子程序、写文件于程序、分配主存子程序、启动I/O子程序等），供用户程序执行中调用，这些 由操作系统提供的子程序称“系统功能调用”程序，简称“系统调用” 。二、作业控制一个用户作业进入计算机系统后， 除作业程序执行时要调用系统功能外， 用 户往往还要告诉系统控制作业执行的步骤。例如，依次做编译、装配、运行等。 系统提供了让用户给出作业执行步骤的手段：作业控制语言和操作控制命令。用户可以用作业控制语言写出控制作业执行步骤的“作业说明书” ，这是一 种非交互的控制方式； 也可以从键盘输入操作控制命令或从 “菜单”中选择命令 来指出作业的执行步骤，这是一种交互的控制方式。第二章 处理器管理2.1 多道程序设计系统内存中存放多个用户算题它们并行执行， 这种程序设计方法称为多道程 序设计系统。引入多道程序设计系统的目的是提高系统效率，提高处理机与 I/O 设备工作的并行性，因为当 CPU 正在执行内存中的某一程序时， I/O 设 备可以同时为其它程序进行输入 /输出。2.2 进程的概念 进程是操作系统中的一个最基本、最重要的概念，所谓进程是具有一定独立 功能的程序关于某个数据集合上的一次运行活动。它实际上是对“程序”在 系统中运行活动的描述。进程在它存在过程中，其状态处于不断地变化中， 通常一个进程至少有三种不同的状态：运行状态、就绪状态、等待状态，并 且在这三种状态下不断地变化。一个进程通常在其刚创建时处于就绪状态， 而在运行状态下结束其生命期而 退出系统。一个进程由三部分组成：程序、数据及进程控制块（PCB）。进程控制块是记录进程有关信息的一块主存，是进程存在的唯一标识。进程具有以下特征：动态性、并发性和异步性。操作系统中往往设计一些完成特定功能的、 不可中断的过程， 这些不可中断 的过程称为原语。用于控制进程的原语有：（ l ）“创建”原语。分配一个工作区和建立进程控制块，置该进程为就绪状 态。（ 2）“撤消”原语。一个进程完成工作后，收回它的工作区和进程控制块。 （ 3）“阻塞”原语。进程运行过程中发生等待事件时把进程状态改为等待态。（ 4）“唤醒”原语。当进程等待的事件结束时，把进程的状态改为就绪态。2.3 进程队列为了便于控制和管理， 将系统中不同状态的进程用不同的队列组织起来， 各 进程队列可以通过进程控制块的链接来形成， 同一队列中的进程， 通过进程控制 块中的队列指针联系起来， 前一个进程的进程控制块中的指针指向它的下个进程 的进程控制块的位置， 队首指针指向队列中第一个进程的进程控制块的位置， 最 后一个进程的进程控制块中的指针值为“ 0”。除了就绪队列外，系统也可把等待不同资源的进程组织成不同的等待队列， 形成多个等待队列。一个进程被创建后， 它被置于就绪队列中， 当它能得到处理器时， 就从就绪 队列中退出进入“运行态” 。在运行过程中可能要求读磁盘上的信息而处于等待 传输信息的状态， 进入等待传输的队列。 当它要求的磁盘传输操作结束后， 又要 退出等待队列而进入就绪队列。 所以，一个进程在执行过程中， 由于进程的状态 不断变化而要从一个队列退出且进入另一个队列， 直至进程结束。 一个进程从所 在的队列中退出称为“出队” ，相反，一个进程排入到一个指定队列中称为“入 队”。系统中负责进程入队和出队的工作称“队列管理” 。2.4 进程调度在多道程序设计的系统中， 有多个进程处于就绪状态， 而一个处理器在每一 时刻只能让一个进程占用。 系统中的“进程调度” 程序按照某种调度算法从就绪 队列中选择一个进程，让它占用处理器。所以，有时也把进程调度程序称为“处 理器调度”程序。常用的进程调度算法有先来先服务、 优先数、时间片轮转及多级调度等算法。 、先来先服务调度算法这种调度算法是按照进程进入就绪队列的先后次序选择可以占用处理器的 进程。当有进程就绪时， 把该进程排入就绪队列的末尾， 而进程调度总是把处理 器分配给就绪队列中的第一个进程。 一旦一个进程占有了处理器， 它就一直运行 下去，直到因等待某事件或进程完成了工作才让出处理器。二、优先数调度算法对每个进程确定一个优先数， 进程调度总是让具有最高优先数的进程先使用 处理器。如果进程具有相同的优先数， 则对这些有相同优先数的进程再按先来先 服务的次序分配处理器。 就绪队列中进程可按优先数从大到小排列， 这样，进程 调度也总是把处理器分配给就绪队列中的第一个进程。进程被创建时系统为其确定一个优先数， 进程的优先数可以是固定的， 也可 随进程的执行过程而动态变化。优先数调度算法分为“非抢占式”的与“可抢占式”的两种。三、时间片轮转调度算法系统规定一个 “时间片”的值。调度算法让就绪进程按就绪的先后次序排成 队列，每次总是选择就绪队列中的第一个进程占用处理器， 但规定只能使用一个 “时间片”。如果一个时间片用完，进程工作尚未结束，则它也必须让出处理器 而被重新排到就绪队列的末尾， 等待再次运行， 当再次轮到运行时， 重新开始使 用一个新的时间片。这样，就绪队列中的进程就依次轮流地占用处理器运行。 2.5 中断由于某些事件的出现， 中止现行进程的运行， 而转去处理出现的事件， 待适 当的时候让被中止的进程继续运行，这个过程称为“中断” 。引起中断的事件称 为“中断源”。对出现的事件进行处理的程序称为“中断处理程序” 。在第一章中 我们简单地介绍了中断的概念，这里将对中断的问题做进一步的讨论。 251 中断的类型不同硬件结构的计算机，它们的中断源不尽相同。 但从中断事件的性质来说， 一般可以分成下述几类：硬件故障中断、程序中断、外部中断、输入输出中断、 访管中断。前面四类中断是由于外界的原因迫使正在运行的进程被打断， 因此可称为强 迫性中断事件。 而第五类中断是正在运行的进程所期待的， 可称为自愿性中断事 件。252 中断的响应通常在处理器执行完一条指令后， 硬件的中断装置立即检查有无中断事件发 生，若有中断事件发生， 则暂停现行进程的运行， 而让操作系统中的中断处理程 序占用处理器，这一过程称为“中断响应” 。253 中断处理中断处理程序对中断事件的处理可分两步进行。 第一步是保护好被中断进程 的现场信息，即把被中断进程的通用寄存器和控制寄存器内容以及被中断进程的 PSW 保存起来，这些信息可以保存在被中断进程的进程控制块中。第二步是对 所发生的中断事件进行具体处理。 对各类中断事件必须进行不同的处理， 中断处 理程序分析引起中断的原因后，转交给适当的例行程序来处理该中断。第三章 存储管理 存储管理是操作系统的重要组成部分，它负责计算机系统内存空间的管理。 其目的是充分利用内存空间， 为多道程序并发执行提供存储基础， 并尽可能地方 便用户使用。3.1 存储管理的目的采用多道程序设计技术， 就要在内存中同时存放多道程序， 这就要求存储管 理解决以下四个重要问题， 以达到尽可能方便用户使用和充分利用内存以提高内 存利用率的目的。一、内存空间的分配和回收二、内存空间的共享与存储保护 三、地址映射（地址重定位）四、内存扩充3.2 单用户连续存储管理这是一种最简单的存储管理方式， 系统是将整个内存除了给操作系统划分出 一块空间外， 其余部分的空间都分配给一个作业使用。 个人机可采用此种管理方 法，它不适宜多道程序设计系统。可以采用静态重定位方式完成地址映射； 处理器在执行指令时， 要检查其绝 对地址是否属于规定范围内的地址， 如果属于，则按此地址访问， 否则将产生“地 址越界”中断。某些系统还采用对换技术（Swapping）让多个进程轮流进入内存，这种技术 多用于分时系统， 随着进程调度， 将内存中的进程暂时移到外存， 而把外存中某 一进程换进内存。3.3 固定分区存储管理其基本思想是将内存划分成若干固定大小的分区， 每个分区中最多只能装入 一个作业。当作业申请内存时， 系统按一定的算法为其选择一个适当的分区， 并 装入内存运行。由于分区大小是事先固定的，因而可容纳作业的大小受到限制， 而且当用户作业的地址空间小于分区的存储空间时，造成存储空间浪费。一、空间的分配与回收 系统设置一张“分区分配表”来描述各分区的使用情况， 登记的内容应包括： 分区号、起始地址、长度和占用标志。其中占用标志为“ 0”时，表示目前该分 区空闲；否则登记占用作业名（或作业号） 。有了“分区分配表”，空间分配与回 收工作是比较简单的。二、地址转换和存储保护 固定分区管理可以采用静态重定位方式进行地址映射。为了实现存储保护，处理器设置了一对“下限寄存器”和“上限寄存器” 。当一 个已经被装入主存储器的作业能够得到处理器运行时， 进程调度应记录当前运行 作业所在的分区号， 且把该分区的下限地址和上限地址分别送入下限寄存器和上 限寄存器中。处理器执行该作业的指令时必须核对其要访问的绝对地址是否越 界。三、多作业队列的固定分区管理 为避免小作业被分配到大的分区中造成空间的浪费， 可采用多作业队列的方法。即系统按分区数设置多个作业队列， 将作业按其大小排到不同的队列中， 一 个队列对应某一个分区，以提高内存利用率。3.4 可变分区可变分区存储管理不是预先将内存划分分区， 而是在作业装入内存时建立分 区，使分区的大小正好与作业要求的存储空间相等。 这种处理方式使内存分配有 较大的灵活性， 也提高了内存利用率。 但是随着对内存不断地分配、 释放操作会 引起存储碎片的产生。一、空间的分配与回收 采用可变分区存储管理，系统中的分区个数与分区的大小都在不断地变化， 系统利用“空闲区表”来管理内存中的空闲分区，其中登记空闲区的起始地址、 长度和状态。当有作业要进入内存时，在“空闲区表”中查找状态为“未分配” 且长度大于或等于作业的空闲分区分配给作业， 并做适当调整； 当一个作业运行完成时，应将该作业占用的空间作为空闲区归还给系统。可以采用首先适应算法、最佳（优）适应算法和最坏适应算法三种分配策略 之一进行内存分配。二、地址转换和存储保护可变分区存储管理一般采用动态重定位的方式，为实现地址重定位和存储保 护，系统设置相应的硬件：基址/限长寄存器（或上界/下界寄存器）、加法器、比 较线路等。基址寄存器用来存放程序在内存的起始地址， 限长寄存器用来存放程序的长 度。处理机在执行时，用程序中的相对地址加上基址寄存器中的基地址，形成一个绝对地址，并将相对地址与限长寄存器进行计算比较，检查是否发生地址越界。三、存储碎片与程序的移动所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。解决碎片的方法 是移动所有的占用区域，使所有的空闲区合并成一片连续区域， 这一技术称为移 动技术（紧凑技术）。移动技术除了可解决碎片问题还使内存中的作业进行扩充。 显然，移动带来系统开销加大，并且当一个作业如果正与外设进行I/O时，该作业是无法移动的。3.5页式存储管理基本原理1 .等分内存页式存储管理将内存空间划分成等长的若干区域，每个区域的大小一般取2 的整数幕，称为一个物理页面有时称为块。内存的所有物理页面从0开始编号，称作物理页号。2. 逻辑地址系统将程序的逻辑空间按照同样大小也划分成若干页面，称为逻辑页面也称 为页。程序的各个逻辑页面从0开始依次编号，称作逻辑页号或相对页号。每个 页面内从0开始编址，称为页内地址。程序中的逻辑地址由两部分组成：页号p页内地址d逻辑地址3. 内存分配系统可用一张“位示图”来登记内存中各块的分配情况，存储分配时以页面 （块）为单位，并按程序的页数多少进行分配。相邻的页面在内存中不一定相邻， 即分配给程序的内存块之间不一定连续。对程序地址空间的分页是系统自动进行的，即对用户是透明的。由于页面尺寸为2的整数次幕，故相对地址中的高位部分即为页号，低位部分为页内地址。实现原理1 .页表系统为每个进程建立一张页表，用于记录进程逻辑页面与内存物理页面之间 的对应关系。地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排 列，形如：逻辑页号主存块号0B01B12B23B32. 地址映射过程页式存储管理采用动态重定位，即在程序的执行过程中完成地址转换。处理 器每执行一条指令，就将指令中的逻辑地址（p,d）取来从中得到逻辑页号（p）, 硬件机构按此页号查页表，得到内存的块号 B，便形成绝对地址（B ,d，处理 器即按此地址访问主存。3. 页面的共享与保护当多个不同进程中需要有相同页面信息时，可以在主存中只保留一个副本， 只要让这些进程各自的有关项中指向内存同一块号即可。同时在页表中设置相应的“存取权限”，对不同进程的访问权限进行各种必要的限制。3.6段式存储管理3. 6. 1基本原理1 .逻辑地址空间程序按逻辑上有完整意义的段来划分，称为逻辑段。例如主程序、子程序、 数据等都可各成一段。将一个程序的所有逻辑段从0开始编号，称为段号。每一 个逻辑段都是从0开始编址，称为段内地址。2 .逻辑地址程序中的逻辑地址由段号和段内地址（s,d ）两部分组成。3 .内存分配系统不进行预先划分，而是以段为单位进行内存分配，为每一个逻辑段分配 一个连续的内存区（物理段）。逻辑上连续的段在内存不一定连续存放。3. 6. 2实现方法1 .段表系统为每个进程建立一张段表，用于记录进程的逻辑段与内存物理段之间的 对应关系，至少应包括逻辑段号、物理段首地址和该段长度三项内容。2 .建立空闲区表系统中设立一张内存空闲区表，记录内存中空闲区域情况，用于段的分配和 回收内存。3 .地址映射过程段式存储管理采用动态重定位，处理器每执行一条指令，就将指令中的逻辑 地址（s,d）取来从中得到逻辑段号（s），硬件机构按此段号查段表，得到该段在 内存的首地址 S,该段在内存的首地址 S加上段内地址d,便形成绝对地址（S +d，处理器即按此地址访问主存。3. 6. 3段页式存储管理页式存储管理的特征是等分内存，解决了碎片问题；段式存储管理的特征是 逻辑分段，便于实现共享。为了保持页式和段式上的优点，结合两种存储管理方 案，形成了段页式存储管理。段页式存储管理的基本思想是：把内存划分为大小相等的页面；将程序按其 逻辑关系划分为若干段；再按照页面的大小，把每一段划分成若干页面。程序的 逻辑地址由三部分组成，形式如下：逻辑地 址段号s页号p页内地址d内存是以页为基本单位分配给每个程序的， 在逻辑上相邻的页面内存不一定 相邻。系统为每个进程建立一张段表，为进程的每一段各建立一张页表。地址转换 过程，要经过查段表、页表后才能得到最终的物理地址。3.7虚拟存储管理前面介绍的各种存储管理方案有一点是共同的，即当一个参与并发执行的进 程运行时，其整个程序都在内存，存在的缺点是：若一个进程的尺寸比内存可用 空间大，则该进程无法运行；而实际上由于局部特性，一个进程在运行的任一阶 段只使用所占存储空间的一部分，因此未用到的内存区域就被浪费。虚拟存储管理是当进程要求运行时， 不是将它的全部信息装入内存，而是将 其一部分先装入内存，另一部分暂时留在外存（通常是磁盘） 。进程在运行过程 中，如果要访问的信息不在内存时，发中断由操作系统将它们调入内存， 以保证 进程的正常运行。虚拟存储管理分为页式虚拟存储管理、段式虚拟存储管理和段页式虚拟存储 管理。页式虚拟存储管理一、基本原理基本思想是，在进程开始执行之前，不是装入全部页面，而是只装入一个或 几个页面，然后根据进程执行的需要，动态地装入其他页面。页表中将增加若干项：标志位（又称驻留位），指示该页是否装入内存；外 存地址给出该页在外存（磁盘）的地址。地址映射时当从页表标志位得知此页不在内存时，发缺页中断。此时暂停进程执行，CPU转去执行缺页中断处理程序，负责把所需的页从外存调入到内存某 空闲块中，并把物理页号填入页表、更改标志位，然后再返回继续执行被中断的 进程。二、页面淘汰当内存已无空闲块而又发生缺页中断时，必须在内存中选择一页面将其淘汰 并写回到外存，然后再换进新的页面，这一过程称为页面调度，选择被淘汰页面 的算法称作页面调度算法。如果页面淘汰算法不合理，可能产生刚被淘汰出去的 一页，又要访问它，因而又要把它调入，如此反复，使系统的页面调入调出工作 非常频繁从而降低系统效率，这种现象称为“颠簸”或“抖动”。常用的页面调度算法有：先进先出调度算法（FIFO）、最近最少使用调度算 法（LRU和最近最不经常使用调度算法（LFU）。注意，对于单用户连续、固定分区、可变分区存储管理是不能实现虚拟存储 管理的，因为它们的共同点是，在对作业进行内存分配时是将整个作业全部、 连 续地放入内存。第四章文件管理4.1概述计算机系统中存放着各种各样的信息，系统经常把这些信息保存在磁盘、 磁带等外存上，为了方便用户、保证系统的安全，系统中的文件管理（或文件系 统）部分负责对外存上的信息进行管理。一、文件和文件系统 我们把具有符号名的一组相关信息项的集合称为一个文件。例如，一 个程序、一个文档等都可做为一个文件，文件系统来管理文件的存储、检索、共 享与保护等。二、文件系统功能 从用户角度看，文件系统主要是实现“按名存取” 。实际上文件系统应具有 如下功能：（1）实现从逻辑文件到物理文件间的转换，即“按名存取”外存上的文件。（2）分配文件的存储空间。（3）建立文件目录。文件目录是实现按名存取的有效手段，也是保证文件 安全的机构。（4）提供合适的存取方法以适应各种不同的应用。（5）实现文件的共享、保护和保密。不同用户能在系统的控制下共享其他 用户的文件。（6）提供一组文件操作。完成对文件的诸如建立、删除、更名、复制和移 动等操作。4.2 文件的存储介质可用来记录信息的磁带、 磁盘等称为存储介质。 要把信息记录到存储介质上 或从存储介质上读出信息必须启动相应的磁带机、 磁盘驱动器等设备。 把存储介 质的物理单位定义为卷，例如，一盘磁带、一张软盘片、一个磁盘组都可称为一 个卷。把存储介质上连续信息所组成的一个区域称为块（物理记录） 。块是主存 储器与这些设备进行信息交换的单位。目前常用的存储设备是磁带机和磁盘机。磁带机是一种顺序存取的存储设备，总是从磁头的当前位置开始读 /写。 磁盘机是一种直接存取存储设备，它把信息记录在盘片上，若干张盘片组成 一个盘组。每个盘面有一个读写磁头， 所有的读写磁头按次序编号， 称为磁头号； 每个盘面有许多磁道， 各盘面上相同磁道组成一个柱面， 盘面上的磁道按由外向 里的顺序编号， 作为柱面号； 盘面被划分成相等的扇区， 各扇区的编号称为扇区 号。磁盘上任何一块的位置可由三个参数确定：柱面号、磁头号、扇区号。4.3 文件的组织 文件的组织是指文件的构造方式，用户眼中看到的文件结构，称为文件的 逻辑结构 （逻辑文件 ）。存储介质上文件实际的存储方式称为文件的存储结构。4.3.1 文件的逻辑结构 逻辑文件可以有两种形式，一种是流式文件，另一种是记录式文件。流式 文件是指对文件内的信息不再划分单位， 是依次的一串信息组成。 记录式文件是 指用户还可把信息按逻辑上独立的涵义划分信息单位， 每个单位称为一个逻辑记 录（简称记录），如数据库文件就是一种记录式文件。4.3.2 文件的存储结构 由于存储设备的类型不同、特性各异，因而文件在相应存储介质上的组织方 式也有差异。通常文件的存储结构有三种：顺序结构、链接结构和索引结构。1顺序结构 一个文件被存放到连续相邻的块上，其逻辑记录顺序和物理块的顺序相一 致，这类文件称顺序文件或连续文件。 文件占用的第一块的物理地址及文件长 （末 地址）登记在该文件目录项中。2链接结构链接结构文件的逻辑记录是顺序的，但在存储空间中不必选择连续的物理 块，每个物理块的最后一个单元中用来存放物理块之间的链接指针。 要将文件占 用的第一块的物理地址登记在文件目录中。链接结构与顺序结构都只适合于顺序存取，不适宜随机访问，而下面介绍的 索引结构文件适于随机访问。3索引结构 索引结构是实现非连续存储的另一种方法， 索引结构为每个文件建立一张索 引表，其中包含两项内容： 记录的关键字和存放地址。 索引结构文件既可随机存 取也可顺序存取，索引表的位置应登记到该文件的目录项中。磁带上文件只能组织成顺序结构，磁盘上文件可以组织成任何一种形式。 433 记录的成组和分解逻辑记录的大小与存储介质上块的大小不一定相同。 把若干个逻辑记录合并 成一组存入一块的工作称“记录的成组” ；当用户需要某一记录时必须把含有该 记录的一块信息读出， 从一组记录中把所要的逻辑记录分离出来， 这一工作称“记 录的分解”。有时一个逻辑记录很大需存放在多个块中， 这些块可以是连续的， 也可以是 不连续的， 这样的记录称为跨块记录。 用户需要一个记录时， 必须把若干块的信 息读出。成组与分解操作不仅提高存储空间的利用率，而且减少存储设备的启动次 数，缺点是记录的成组和分解操作必须使用主存储器中的缓冲器， 会增加系统的 开销。4.4 存储空间的分配 当要建立一个文件时文件系统必须能够为文件分配存储空间， 而当某个文件 不再需要时能够收回它们所占的存储空间， 这依赖于对空闲块的管理方法。 通常 采用位示图法、空闲块链接法实现对空闲块的管理。4 4 1 位示图法用一张位示图来指示磁盘存储空间的使用情况， 磁盘分块后， 根据可分配的 总块数决定位示图由多少位组成， 它的每一位与一块对应，“ 1”状态表示相应块 已占用，“0”状态表示该块空闲。442 空闲块链接法 1单块链接 把所有的空闲块用指针连接起来， 每个空闲块中都设置一个指向另一空闲块的指针，形成了空闲块链。系统设置一个链首指针，指向链中的第一个空闲块， 最后一个空闲块中的指针为“ 0”。2成组链接 把磁盘存储空间的空闲块成组链接。 每 100个空闲块为一组， 每一组的第一 个空闲块中登记下一组空闲块的磁盘物理块号和空闲块总数， 最后不足 100 块的 那部分磁盘物理块号及块数记入专用块中。4.5 文件目录 存储介质上的文件目录其作用类似于一本书的目录， 实现对存储介质上的文 件按名存取。文件目录由若干目录项组成，每个目录项中应包含：文件名、存放 地址、类型、组织方式、记录的长度、存取权限，以及文件的建立日期和保存期 限等，这些信息构成文件控制块。451 一级目录一级目录结构是把所有的文件都登记在一张目录表中， 按文件名查找目录就 能知道文件存放的地址。每当建立一个新文件时就在文件目录中增加一个目录项；每当删去一个文件时就在文件目录中删去该文件的目录项。但这种结构无法解决文件重名问题。4. 5. 2二级目录二级目录结构是为每个用户设置一张用户文件目录，再用主文件目录来登记图4.1二级文件目录采用二级目录结构后，不同用户的文件名可以相同，例如，图中用户A和用户C 都文件xy。此结构也可实现不同的用户共享某个文件，图中用户 A的文件E1 和用户B的sb文件实际共享的同一物理文件。4. 5. 3树形目录大多数文件系统允许在文件目录中再建立其子目录，即形成多级目录结构。 如：Windows、UNIX、MS-DOS系统都采用多级目录结构。这种结构也称为树 形目录结构，该树从根向下，每一个节点是一个目录，最末的叶结点是文件。访问文件时，必须指出文件所在的路径，路径名是从根目录开始到该文件的 通路上所有各级目录名及该文件名拼起来得到。通常引入当前目录的概念，将某级目录中设置为当前工作目录，要访问文件时，就可从当前目录开始设置路径， 称相对路径。4.6文件的保护和保密文件系统在实现文件共享时，应考虑文件的安全性，安全性体现在文件的保 护和保密两个方面。4. 6. 1文件的保护文件的保护是指防止文件被破坏。造成文件可能被破坏的原因有时是硬件故 障、软件失误引起的，有时是由于共享文件时引起错误， 应根据不同的情况采用 不同的保护措施。1. 防止系统故障造成的破坏为了防止各种意外破坏文件，可以采用建立副本和定时转储的方法来保护文 件。2. 防止用户共享文件时造成的破坏为了防止不同用户使用文件时破坏文件，可规定各用户对文件的使用权限。 例如：只读、读/写、执行、不能删除等。对多用户可共享的文件采用树形目录 结构，能得到某级目录权限就可得到该级目录所属的全部目录和文件，按规定的存取权限去使用目录或文件。4. 6. 2文件的保密文件的保密是指防止他人窃取文件。 “口令”和“密码”是两种常见的方法。 一旦为文件在目录中设置口令后， 文件使用者必须提供口令， 只有提供的口令与 设置的口令一致时才可使用该文件，否则无法使用。 “密码”是把文件信息翻译 成密码形式保存， 使用时再解密。 密码的编码方式只限文件主及允许使用该文件 的用户知道，但这种方法增加了文件编码和译码的开销。4.7 文件的使用 471 存取方法对文件的存取方法可以分成两类： 顺序存取和随机存取。 顺序存取是指按文 件的记录顺序依次进行读 /写记录；随机存取是指按任意的次序、随机地读 /写文 件中的记录。对顺序存取的文件， 系统可把它组织成顺序文件、 链接文件或索引文件； 对 随机存取的文件，只能把它组织成索引文件。472 文件操作文件系统至少应提供如下文件操作：1建立文件用户要求把一个新文件存放到存储介质上时， 首先要向系统提出“建立文件” 要求。2打开文件 用户要使用一个存放在存储介质上的文件时，应先提出“打开文件”要求， 系统将找出该文件的目录把它读到主存中， 如果是索引文件还应将文件索引表读 入内存。3读写文件 系统对已经打开或建立的文件进行读写，完成数据传输。4关闭文件 读/写完毕后，需要执行“关闭”操作，将该文件的目录(或索引表)从内 存中撤消。5删除文件系统执行该操作时把指定文件的目录项和索引表撤消， 并收回它占用的存储 区域。第五章 设备管理 设备管理是指对计算机系统中所有输入、输出设备的管理。设备管理与文件 管理是密切相关的， 文件系统实现逻辑文件与物理文件间的转换， 设备管理实现 对外围设备的启动与控制。5.1 设备管理功能 一、设备管理的目标：(l )方便用户使用外部设备，控制设备工作完成用户的输入输出请求。( 2 )提高系统的并行工作能力，提高设备的使用效率。(3)提高外围设备和系统的可靠性和安全性，以使系统能正常地工作。 二、设备管理功能设备管理应具有如下功能： 设备的分配和回收、 外围设备的启动、 对磁盘的 驱动调度、外部设备中断处理、虚拟设备的实现。5.2 外围设备的分配一、设备的分类现代计算机系统总是配有各种类型的外部设备， 种类繁多， 可以从不同的角 度对它们进行分类。从设备的使用角度可将设备分为两类： 独占设备和共享设备。 有的系统还有另一类较为特殊的设备，称为虚拟设备，它是用共享设备来模 拟独占设备， 就好象把一台设备变成了多台虚拟设备， 我们称被模拟的设备为虚 拟设备。二、设备的绝对号与相对号 给系统中的每一台设备确定一个编号以便系统识别，这种编号称为“设备绝 对号”。但绝对号是用户不允许使用的，用户在申请设备时只能用设备类型来申 请，但用户为了识别同类设备中的某台设备，可使用“设备相对号” 。三、设备的分配用户申请设备时通过设备类别申请， 系统根据请求及当前设备分配情况在相 应类的设备中选择一个空闲设备， 并将其分配给申请者， 申请与实际设备的无关 性称为设备独立性。系统设立“设备类表”和“设备表”记录系统设备的分配情 况。5.3 磁盘的驱动调度 对于磁盘设备同一时刻可能会有许多访问请求， 按照什么次序为这些访问请 求服务是磁盘驱动调度所解决的问题。磁盘上任何一块的位置可由三个参数确定：柱面号、磁头号、扇区号，对移 动臂磁盘的存取访问一般要经过三部分时间：首先要将磁头移动至相应的柱面 上，这个时间叫做寻找时间； 一旦磁头到达指定柱面， 等待所访问的扇区旋转到 读写头下，叫延迟时间； 实际传送所需时间叫传送时间。 一次磁盘访问的时间 就是以上三者之和，其中“寻找时间”所花费的时间最长。5.3.1 移臂调度 可采用以下几种移臂调度算法。 1先来先服务算法 即按照访问请求的次序服务， 这是最公平而又最简单的算法， 但是效率不高。 2最短寻找时间优先算法 优先为距离当前磁头所在位置最近柱面的请求服务。 该算法与上面的算法都 可能造成磁臂经常改变方向而影响效率。3扫描（电梯）算法 总是从磁臂当前位置沿磁臂的移动方向选择距当前位置最近的请求， 当前进 方向无请求时才改变移动方向。这种算法比较公平，而且效率较高。5.3.2 旋转延迟调度 当磁头到达某柱面时， 该柱面上可能有多个请求， 对它们的调度通常是按这 些请求旋转通过磁头的顺序进行调度。5.4 设备的启动和 I/O 中断处理5.4.1 通道通道相当于一个功能单一的处理机， 代替CPU对1/O操作进行控制，专门 负责数据输入输出工作，从而使 I/O 操作可以与 CPU 并行工作。通道是实现计 算和传输并行的基础。在一个配备了通道的系统中， 主机上可连接多个通道， 一个通道连接多个控 制器，一个控制器连接多台同类型的设备； 而对某些设备 （象磁盘那样的快速设 备）往往需连接到多个控制器上，将控制器连接到多个通道上进行交叉连接。 5.4.2 外围设备的启动通道具有自己的指令系统，包括读、写、控制、转移、结束、以及空操作等指令，一旦CPU发出“启动I/O”的指令，通道就可以独立于 CPU工作，执行 由通道指令（CCW）形成的通道程序完成I/O。启动、控制外围设备完成 I/O 的过程如下：（1）根据 I/O 请求，构造通道程序。（2）中央处理机发出“启动I/O”指令，通道逐条执行通道程序中的指令实 现 I/O 。（3）I/O 完成后，通道利用中断机构向中央处理机报告执行情况。5.4.3 I/O 中断处理 中断处理程序负责对通道发出的中断进行处理， 对输入输出是否正常结束或 出现错误等进行相应的处理。通道状态字（CSW）中记录通道、控制器、设备的状态，当中央处理机接 到通道发出的中断后，利用通道状态字判断本次输入输出是否正常。5.5 虚拟设备独占型设备是不利于提高系统效率的， 可采用的措施有两种： 脱机外围设备操作 和联机同时外围设备操作。脱机外围设备操作 脱机外围设备操作是使用两台外围计算机， 分别负责把慢速、 独占设备上的 信息写入磁盘以及将磁盘上的信息传送到独占设备， 作业执行时只与可共享的磁 盘进行信息交换。 外围计算机是独立于主计算机的， 不是在主计算机控制下进行 的，所以称作“脱机外围设备操作” 。脱机外围设备操作虽然提高了系统效率， 但也存在一些新问题： 外围计算机 的使用，提高了成本；增加了操作员的手工操作；增加了作业的周转时间。 联机同时外围设备操作联机同时外围设备操作也称为一种虚拟设备技术， 其核心思想是在一台共享 设备（通常是指磁盘） 上模拟独占设备的操作， 把低速的独占设备改造成为若干 台可并行操作的虚拟设备。操作系统设计两个程序：“预输入程序”和“缓输出程序” ；在磁盘上开辟一 块称为“井”的区域。 “预输入程序”和“缓输出程序”的执行是在计算机控制 下进行的，所以这种技术称为“联机的同时外围设备操作” （缩写为 SPOOL 或 SPOOLING），还有的系统称之为“假脱机操作”。当用户作业要进入系统时， 由 SPOOLing 系统的预输入程序将作业信息从独 占的输入设备上送到磁盘上指定区域（称为输入井） ；当作业运行时，可以直接 从输入井读入数据； 当执行过程中需要输出数据时， 可以先将输出数据送往磁盘 上另一指定区域（称为输出井） ；最后，当作业完成后由缓输出程序依次将输出 井上的数据送到独占的输出设备上。实现“输入井读” 和“输出井写” 的程序可统称为“井管理”程序。 SPOOLing 系统实际上是以中断机构和通道作为其硬件基础的，它由三部分程序组成： “预 输入”程序、“井管理”程序和“缓输出”程序。第六章 作业管理6.1作业作业和作业步 把用户要求计算机系统处理的一个计算问题称为一个“作业” 。把一个作业 所经历的每一个加工步骤（如编译、连接装配、运行等）称为一个“作业步” 。作业控制方式实际上每个作业所经历的加工步骤可能是不同的， 操作系统为用户提供了说 明作业加工步骤的手段， 系统提供两种手段： 作业控制语言和操作控制命令， 让 用户来说明他的作业需进行加工的步骤。 相应地， 作业控制方式也有两种： 批处 理方式和交互方式。1批处理方式 采用批处理控制方式的作业， 用户把对作业执行的控制意图用作业控制语言 写成一份说明书， 连同该作业的源程序和初始数据一起输入到计算机系统， 系统 就可按用户说明书来控制作业的执行。 作业执行过程中用户不能干预， 一切由系 统自动地控制作业的执行， 因此，批处理控制方式也可称 “脱机控制方式” 或“自 动控制方式”。2交互方式 在作业执行过程中，用户把对作业执行的控制意图通过逐条输入的命令表 达，操作系统每接到一条命令，就根据命令的要求执行，一条命令执行完，系统 反馈命令执行情况且允许用户输入下一条命令， 以控制作业继续执行。 作业执行 过程中系统与用户之间需不断地交互信息， 这种方式也称为“联机控制方式”。终 端用户一般使用交互控制方式，经常把这种作业称为终端作业或交互式作业。6.2 批处理作业的管理 一个批处理作业应包括：源程序、初始数据以及作业说明书，其中作业说明 书是用作业控制语言来描述的，规定如何控制作业的执行。作业控制语言 不同的系统中其作业控制语言可能是不同的，但它们的基本特性是类似的。作业控制语言由若干控制语句组成， 一个作业中的每一个作业步都可以用一个控 制语句来描述。因此，用户可以用作业控制语言编写“作业说明书” ，指出自己 的作业需经历哪些作业步以及作业步的执行顺序。批处理作业的输入 用户可把自己作业的信息 （源程序、 初始数据以及作业说明书） 存储在存储 介质上（如磁带、软盘等）交给操作员，在采用 SPOOL 技术的计算机系统中， 操作员只要输人一条“预输入”命令启动“预输入程序”工作，就可把作业流中 的作业信息存放到磁盘输入井中等待处理。批处理作业的调度 输入井中等待处理的作业 （后备作业） 可能会有很多， 应怎样从中选择作业 让它们先执行？系统根据允许的道数和一定的算法从后备作业中选取若干作业 让它们进入主存储器以便获得处理器运行，这项工作称为“作业调度” 。作业调度选中了一个作业且把它装人主存储器时， 就为该作业创建进程。 这 些进程的初始状态为就绪，由进程调度来选择当前可占用处理器的进程，所以， 作业调度与进程调度相互配合能实现多道作业的并行执行。设计作业调度算法时应尽可能地遵循以下原则： 公平性、平衡资源使用和极 大的流量。人们经常用“周转时间”来衡量一个调度算法的优劣，所谓周转时间 是一个作业从进入输入井到得到运行完成的时间。 对于每个用户来说总希望自己 作业的周转时间（ Ti ）尽可能地小，从系统的角度，希望进入输入井的作业的平 均周转时间尽可能地小。对n个作业来说，它们的平均周转时间为：T=（工Ti）/n。常用的作业调度算法：1先来先服务算法 该算法是一种较简单的调度算法， 它是按照作业进入输入井的先后次序来挑 选作业，先进入的作业优先被挑选。但要注意，不是先进入的一定先被选中，只 有满足必要条件的作业才可能被选中。先来先服务算法具有一定的公平性， 容易实现。 但可能使计算时间短的作业 长时间地等待， 使作业周转时间变长造成这些用户不满意， 也增加了平均周转时 间，降低系统的吞吐能力。2短作业优先算法这种算法要求用户预先估计自己作业所需要计算的时间， 并在作业说明书中 说明。调度时优先选择计算时间短且资源能得到满足的作业。 这种算法能降低作 业的平均周转时间，从而提高系统的吞吐能力。采用短作业优先算法要注意两个问题：（1）这种算法是以用户估计的计算时间为标准，为了避免用户故意把计算 时间估计过低现象，可采用对超过所估计的时间部分加价收费的办法。（2）可能会由于计算时间短的作业不断进入，造成进入输入井早但要求计 算时间长的作业无限制地被推迟。3最高响应比优先算法 最高响应比优先算法综合考虑等待时间和计算时间，把响应比定义为：响应比 =等待时间 /计算时间 可以看出计算时间短的作业响应比较高， 所以能被优先选中； 但等待时间长 的作业响应比也会较高， 这样就不会因不断地有小作业进入输入井而使大作业无 限制地被推迟。4优先数调度算法系统为每一作业确定一个优先级， 优先级高的作业优先被选取。 优先级的确 定可根据作业的缓急程度、估计计算时间、作业等待时间、资源申请情况、付费 情况等因素综合考虑，既照顾用户要求，也考虑系统效率。5均衡调度算法根据各作业对不同资源的申请进行调度， 其目标是使系统中的各类资源能均 衡利用，避免资源忙闲不均的情况。作业的状态 一个作业从进入系统到运行结束，一般要经历进入、后备、运行和完成四个 阶段，相应地，作业亦有进入、后备、运行和完成四种状态。但作业的运行状态是指作业被调入内存运行，不意味着占用处理机。6.3 交互式作业的管理6.3.1 交互式作业采用交互方式控制的作业， 用户根据作业执行情况决定应该输入的下一条命 令，以控制作业的继续执行 ,交互式作业的特点主要表现在交互性上。6.3.2 交互式作业的控制利用计算机提供的显示屏幕、 键盘、鼠标等设备可实现人机对话。 操作系统 为用户提供操作使用接口， 目前常用的操作使用接口有操作控制命令、 菜单技术、 窗口技术等。1. 操作控制命令 不同系统提供给用户使用的操作控制命令不相同， 操作控制命令可分下面几 类：“注册”和“注销”命令、编辑命令、文件类命令、调试类命令等。用户根 据规定的命令格式从键盘上输入命令， 请求系统完成指定的功能， 要求用户记住 各个命令的功能和使用格式。2. 菜单技术提供菜单技术后， 用户可不必事先记住程序提供的功能及其使用方法， 而根 据屏幕上显示的莱单来进行选择。 因此，菜单技术为用户提供了一种 “友好的使 用接口”。3. 窗口技术一个屏幕上可设置多个窗口， 当多个应用程序同时执行时， 每个应用程序可 在自己的窗口中执行。 每次只允许用户对其中的一个窗口进行直接操作， 并允许 用鼠标或键盘来对窗口进行操作。如 Windows、Windows NT 等都是窗口软件， 向用户提供了更友好的“图形用户接口” 。交互控制方式的系统都会提供命令解释程序， 负责接受并解释执行用户的命 令。可把命令分为两大类： 由系统中的模块直接解释执行， 通过创建用户进程解 释执行。6.3.3 终端作业的管理在分时系统中， 当用户想利用某个终端使用系统控制作业运行时， 一般经过 四个阶段：终端的连接、用户注册、控制作业运行、用户注销（退出） 。第七章 并发进程7.1 进程的并发性711 进程的顺序性 进程的顺序性是指进程在处理器上的执行是按照程序规定的顺序， 只有在前 一个操作结束后才能开始下一个操作。当一个进程独占处理器顺序执行时，具有两个特性： （1）封闭性进程执行的结果与其执行速度无关，只取决于进程本身。 （2）可再现性只要初始条件相同，无论进程在什么时间执行都产生相 同的结果。712 进程的并发性 在多道程序设计系统中同时存在着许多进程， 在单处理器的情况下， 一个进 程的工作没有全部完成之前，另一个进程就可开始工作，这些可同时（交替）执 行的进程具有并发性，把可同时执行的进程称为“并发进程” 。并发进程相互之间可能是无关的、 各自独立的， 而有些并发进程相互之间是 有交往的，这些进程并发执行时，执行结果与其执行的相对速度有关，因而，进 程的并发执行会破坏“封闭性”和“可再现性” 。7.2 与时间有关的错误 系统中通常存在着多个进程，进程执行的相对速度不能由进程自己来控制， 这些进程分别以不可预知的速度，靠系统的处理机（进程）调度向前推进，然而 有时某些进程在运行时需要相互协调，如需要同步、互斥。考察下面的例子：P1进程1 ) R1 ： =COUNT2)R1：=R1+13)COUNT：=R1P2进程(1 ) R：2 =COUNT (2) R：2 =R2+1 (3) COUN：T =R2P1, P2两个进程实际上是分别执行 C0UNT:=C0UNT+1操作，如果两个进 程顺序执行， 结果是正确的， 使 COUNT 的值加 2；但在多道程序设计系统中 P1，P2两个进程是可以并发执行的，如果两个进程执行顺序为： 、(1 )(2 ) (3 )3)，则最终结果只使COUNT的值加1,造成错误(顺序为：1、2、1)2)3)3同样造成错误)。其错误的原因是由于Pi进程被打断的时间造成的，这种 错误被称为“与时间有关的错误”。7.3临界区问题与PV操作临界区问题我们把并发进程中与共享变量有关的程序段称为“临界区”。P1)P2进程中就涉及到临界区，其错误的原因也是由于临界区问题，系统应避免当一个进程在 临界区中执行时，其它的进程进入相关的临界区执行。7.3.2 PV 操作Dijkstra发明的PV操作能够实现对上述问题的解决，PV操作是两个原语：P 原语和V原语，这两个操作是两个不可中断的，是对信号量的操作。它们的功 能可分别按下述粗略地描述，其中 S是信号量。P( S):将S信号量值减1,若结果小于0,则调用P (S)的进程被置成等 待状态；否则该进程继续执行。V (S):将信号量S值加1，若结果不大干0,则释放一个等待信号量 S的 进程，使其变为就绪状态。7.4进程的互斥与同步进程的互斥进程的互斥是指当有若干进程都要使用某一共享资源时，任何时刻最多只允 许一个进程使用，其它要使用该共享资源的进程必须等待，直到占用者释放了该资源。前面提到的临界区问题就属于互斥问题。互斥问题用PV操作可方便地得到解决。设信号量S的初值为1P1进程：P2进程：P(S)P(S)R1： =COUNTR2: =COUNTR1： =R1+1R2: =R2+1COUNT: =R1COUNT: =R2V(S)V(S)这种解决模式同样适用与多个进程的互斥问题。进程的同步进程的同步是指：并发进程之间存在的一种制约关系， 一个进程的执行依赖 另一进程的消息，当一个进程没有得到另一个进程的消息时应等待， 直到消息到 达才被唤醒。设有两个进程A和B,它们共享一个缓冲器，进程 A不断地读入记录并送到缓 冲器，进程B不断地从缓冲器中取出记录并加工，如图7.1所示。AB图7.1进程同步1假定缓冲器的容量为每次只能存放一个记录，系统为了能正常同步必须是： 进程A把一个记录送入缓冲器后，应等到进程 B已将缓冲器的记录取走，才