操作系统设计原理 课件 第6-10章 文件管理-操作系统设计问题

第六章文件管理1第六章文件管理26.1文件6.2目录6.3文件系统的空间管理

6.4文件系统的可靠性6.5

虚拟文件系统6.6文件系统的类型6.7文件系统实例

文件系统负责文件的存储、检索、共享与保护，以及文件存储空间的组织与管理、分配与回收。本章将从文件、文件目录管理、文件的共享与保护、文件存储空间管理、文件分配，以及UNIX、Linux和Windows操作系统的文件系统实例等方面进行讲述。6.1文件6.1.1

文件命名6.1.2文件类型6.1.3文件属性6.1.4

文件的存取方法6.1.5文件操作

6.1.6文件的逻辑结构36.1.1文件命名1、文件是一组逻辑上相互关联的信息的集合，是计算机系统中信息的一种组织结构

如：一个Ｃ语言源程序、I/O设备上传输的信息2、文件命名规则：一般由文件名和扩展名组成46.1.2文件类型普通文件和目录文件普通文件存储文件内容信息，可分为ASCII文件和二进制文件对普通文件类型进一步细化，可通过文件扩展名来区分文件类型56.1.3文件属性文件属性用于标识和描述文件，如文件名、文件创建时间、文件长度、文件的物理地址、存取权限等信息用户对文件的存取权限：保护、口令、创建者和所有者4个属性与文件保护有关查找关键字所需信息：记录长度、关键字位置和关键字长度时间域：文件的创建时间、最近存取时间以及最近修改时间长度域：文件当前的大小66.1.4文件的存取方法文件存取方法是研究存储空间上物理文件的访问方法顺序存取方法严格按照数据记录的排列顺序依次存取可用于顺序存取设备(如磁带)，又可用于直接存储设备(如磁盘)直接存取方法用户随意读写文件的任意一条记录适用于直接存取设备索引存取方法索引存取方法建立在直接存取方法之上，需要创建文件索引76.1.5文件操作8

文件系统为用户提供了一系列文件操作接口，典型的文件操作如下：创建删除打开关闭读写6.1.6文件的逻辑结构逻辑文件从结构上分成二种形式：一种是无结构的流式文件，是指对文件内信息不再划分单位，它是依次地一串字符流构成的文件；另一种是有结构的记录式文件,是用户把文件内的信息按逻辑上独立的含义划分信息单位，每个单位称为一个逻辑记录(简称记录)选取文件的逻辑结构应遵循下述原则

修改时，尽量减少对已存储好信息的变动。操作时，尽可能快地查找到需要的记录或信息应使文件信息占据最小的存储空间便于用户进行操作96.1.6文件的逻辑结构记录式文件常用的组织方式有：堆文件、顺序文件、索引顺序文件、索引文件和哈希文件(直接文件)

。堆文件对于多条记录大小和结果不同，可采用堆(pile)文件来组织

按照记录到达的时间顺序组织的记录之间用界定符区分访问只能顺序进行顺序文件

顺序(sequential)文件是最常用的文件组织形式

每条有一个关键域，记录格式相同、长度相同优点是顺序存取速度快，适用于顺序存取和成批处理多条记录的场合对查询或更新较多情况，顺序文件将表现出较差的性能解决办法：日志文件或链接文件106.1.6文件的逻辑结构索引顺序文件

按照记录的关键域的顺序组织的关键特性文件索引溢出文件溢出文件用于添加新纪录，类似于顺序文件中的日志文件主文件中的每条记录包含一个附加指针域，该指针用来指向溢出文件的某一位置116.1.6文件的逻辑结构索引文件

按关键字建立的索引表为主索引表(或称完全索引)按其他属性建立的索引表为辅助索引表(或称部分索引)索引文件支持随机直接访问，多用于对信息处理及时性要求较高的场合直接文件

直接文件也称为哈希文件或散列文件，是用散列技术组织成的文件直接文件使用基于关键字的散列直接文件中的记录通常是成组存放的若干条记录组成一个存储单位，称之为桶溢出桶、基桶接文件具有随机存取、记录不需排序、插入删除方便、存取速度快、不需要索引区和节省存储空间等优点直接文件不能顺序存取126.2目录13目录是由文件说明索引组成的用于文件检索的特殊文件。文件目录的内容主要是文件访问的控制信息（不包括文件内容）。对文件目录管理的要求：实现“按名存取”。提高对文件目录的检索速度共享文件允许文件重名

6.2.1文件目录内容

6.2.2文件目录结构

6.2.1文件目录内容

14从用户的角度来说，文件目录在文件名与文件自身之间提供一种映射。文件控制块(FileControllingBlock，FCB)：用于描述文件和控制文件信息的数据结构每一文件有一个与之对应的文件控制块

1)文件控制块基本信息：文件名、文件类型、文件组织文件的地址信息：卷、起始地址、文件使用大小、文件分配大小访问控制信息：文件的所有者、访问信息、许可的行为标记使用信息：建立日期、上一次读日期、上一次读用户名上一次修改用户名上一次备份日期当前文件活动状态6.2.1文件目录内容

152)索引结点FCB可以进一步被划分为文件名和除文件名之外的其他信息部分在文件目录表中仅放文件名和与之对应的索引结点位置信息将除文件名之外的其他信息放在索引结点中每一文件对应一个索引结点应用：UNIX和Linux6.2.2文件目录结构

16目录结构讨论目录的组织结构，设计目标是提高检索效率。单级目录：整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系统。它具有如下的特点：结构简单，使用方便，易于实现；局限重名问题搜索效率低难于实现文件共享6.2.2文件目录结构

17两级目录：在根目录下，每个用户对应一个目录（第二级目录）；在用户目录下是该用户的文件，而不再有下级目录。适用于多用户系统，各用户可有自己的专用目录。两级目录结构与单级目录结构相比具有以下优点解决了不同用户之间的重名问题提高了检索速度允许不同用户之间的文件共享6.2.2文件目录结构

18多级目录：或称为树型目录结构(TreeStructuredDirectory,TSD)。在文件数目较多时，便于系统和用户将文件分散管理。适用于较大的文件系统管理。目录级别太多时，会增加路径检索时间。树型多级目录的优点：较好地反映现实世界中具有层次关系的数据集合和较确切地反映系统内部文件的分支结构；不同文件可以重名，只要它们不是在同一末端的子目录中；易于规定不同层次或子树中文件的不同存取权限便于文件的保护、保密和共享等。196.2.2文件目录结构

目录文件：一个目录的目录项组成的文件。目录名：可以修改。目录树：中间结点是目录，叶子结点是目录或文件。目录的上下级关系：当前目录(currentdirectory,workingdirectory)、父目录(parentdirectory)、子目录(subdirectory)、根目录(rootdirectory)等；查找一个文件是根据该文件的路径完成的。文件的路径分为绝对路径和相对路径。绝对路径(absolutepath)。从根目录到任何数据文件或目录文件之间，只存在一条通路相对路径(relativepath)。从当前目录开始直到数据文件为止所构成的路径称为相对路径

6.2.2文件目录结构

20216.2.2文件目录结构

无环图目录结构：树型目录结构限制了文件和目录的共享，通过将树型目录结构改进为无环图(acyclicgraph)可克服这一局限。无环目录结构比树型目录结构更加灵活，但也更加复杂。现在一个文件可能有多个绝对路径名会出现不同文件名表示同一文件的现象在文件查找、文件数量的统计、备份和删除等方面与树型目录结构相比有其特殊性。在文件或目录的删除上需要注意以下两方面：(1)当共享文件或目录被删除后出现悬空或指向其他文件(被释放的磁盘空间被分配给其他文件)问题时。采用与访问其他非法文件名或目录名一样处理的方法来解决。(2)删除共享文件或目录的另一种处理办法是：保留被删除的共享文件或目录直到删除所有共享指针为止。需要为每个共享文件或目录保留一个引用列表，当删除共享文件或目录时，仅删除引用表中对应的目录项，直到引用列表空时才删除文件或目录本身226.2.2文件目录结构

236.2.2文件目录结构

通用图目录结构：在无环图目录结构中，进一步允许子目录对上层目录的引用，就产生了通用图目录结构。通用图目录结构的主要优点：可用简单的算法来遍历图并确定是否存在文件引用。在使用时面临的难点有：(1)由于图中存在环，在搜索某个子目录时要避免无穷地循环搜索。这个问题可以通过限制访问目录的次数来确定。(2)在判断一个文件是否可删除时，由于存在文件的自我引用，所以不能简单地通过引用计数是否为0来判断是否可被删除。246.2.2文件目录结构

6.2.3文件共享与保护

25

文件共享

－文件共享是指一个文件被若干用户或进程共同使用。避免了系统复制文件的开销，并节省文件占用的存储空间。

文件保护

－文件系统必须提供安全可靠的保护与保密措施，以防止文件信息被有意或无意的破坏或偷窃。

文件共享

26

1.利用符号链接实现共享

2.基于索引结点的共享方式

3.利用基本文件目录实现文件共享实现文件共享的常用方法

文件共享

27符号链接(symboliclinking)：采用无环图目录结构。在要共享的子目录中创建一个LINK类型的新文件。在新文件中写入被链接文件路径名，以实现目录与文件的链接只有文件主才拥有指向其索引结点的指针共享该文件的其他用户，只有该文件的路径名，而没有指向索引结点的指针不会发生在文件主删除共享文件后留下悬空指针的问题类似于Windows系统中的快捷方式优点：能够用于链接计算机网络上的任何地点中的文件缺点：时间、空间开销较大1.利用符号链接实现共享

文件共享

281.利用符号链接实现共享

文件共享

292.基于索引节点的共享方式思想：将文件中诸如文件的物理地址及其文件属性等信息，不放在文件目录表目中，而是放在索引节点中。在文件目录中只设置文件名及其指向相应索引节点的指针。在索引结点中有一个链接计数器，表示链接到索引结点的用户数量30

文件共享

2.基于索引节点的共享方式删除共享文件时可能会出现指针悬空的问题：只有文件主才可删除共享文件，但保留索引结点，并使链接计数器减1当链接计数器为0时，删除索引结点基于索引结点的共享方式也称为硬链接共享方式，与符号链接方式本质区别不能实现跨文件系统和跨设备的共享，特别是不能基于网络的共享。因为不同设备上有各自的文件系统，每一文件系统下有自己的文件目录和索引结点表，而文件的目录仅与自身的索引结点表关联，因此，基于索引结点的共享方式不能实现跨文件系统的共享。

文件共享

31利用基本文件目录实现文件共享：利用把目录表目进行分解的办法来加快检索速度，同时也便于实施文件的共享目录分解：就是把一个目录表目分解为两部分：基本文件目录（BFD）部分与符号文件目录（SFD）部分。

3.利用基本文件目录实现文件共享

文件共享

323.利用基本文件目录实现文件共享6.3文件系统的空间管理33

文件存储空间管理的数据结构通常称为磁盘分配表(diskallocationtable)，分配的基本单位是簇。文件系统可靠性包括检错和差错恢复。空闲空间的管理方法有：1.空闲表法2.空闲链表法

3.位示图(bitmap)4.链接索引表法

6.3文件系统的空间管理341.空闲表法空闲区：存储介质中一个连续的未分配区域。

系统为存储介质上的所有空闲区建立一张空闲表，每一个空闲区对应表中的一个表目。表目的内容包括：空闲区第一个盘块号、该空闲区的盘块总数等信息。将所有空闲区按第一盘块号的大小排列。

分配算法与内存分配类似。6.3文件系统的空间管理351.空闲表法空闲区分配：扫描各表目的空闲块总数满足要求？NY实际＝请求？设为空表目Y多余的块号留在原表目中

N删除文件：－扫描空闲表，寻找一个空表目，将文件所释放的第一个盘块号及其占用的盘块数填入该表目中。6.3文件系统的空间管理361.空闲表法总结：适用于连续分配文件，管理方法简单，但当空闲区过多时，将大大影响使用效率。6.3文件系统的空间管理372.空闲链表法空闲链表法是将所有的空闲区拉成一条空闲链。根据构成链的基本元素的不同，可分为：空闲盘块链－空闲盘块链是指将磁盘上所有空闲区，以盘块为基本元素拉成一条链。

空闲区链－空闲区链是指将磁盘上所有的空闲区（每个空闲区可能包含若干个盘块）拉成一条链。

优点：分配与回收一个盘块的过程非常简单；缺点：空闲盘块链可能很长，影响效率。

优点：空闲区链较短；缺点：分配与回收的过程较复杂。386.3文件系统的空间管理3.位示图(bitmap)每一位表示一个盘块，取值0和1分别表示空闲和占用。在文件使用期间存放在内存中，使用方便、速度较快。分配步骤：1.位示图中找到一个其值为“0”的二进制位。2.计算盘块号为b=n*(I-1)+J，（I为行，J为列）。注：B为相对块号，实际中盘块号为:(柱面号，磁头号，块号）3.令map[I,J]=1.回收步骤：1.将盘块号b变换成相应的行号I和列号J

：

I=(b-1)divn+1；

J=(b-1)modn+1。2.令map[I,J]=0

396.3文件系统的空间管理3.位示图(bitmap)6.3文件系统的空间管理404.链接索引表法基本思想：使用若干个空闲盘块作为索引表块，来指出存储空间中所有空闲盘块。

分配：－系统从链表头的索引表块（如图6-17中的A索引块）的尾部开始分配。回收：－系统将释放的空闲块添加到索引链表头指出的索引表块的空闲表目中（链表中只有头指针指出的索引表块是不满的，其他索引表块全是满的）。6.3文件分配41文件分配：也叫文件的物理组织，即文件在文件存储空间上的存储结构。

文件分配的优劣主要取决于：采用静态分配（预分配）还是动态分配。分区大小应该是多少。文件空间的管理。

文件分配方法。

静态分配是指创建一个文件时就给文件一次性分配所需的最大文件存储空间；

动态分配是指随文件动态增长动态分配所需的文件存储空间。6.3文件分配42如何才能有效地利用文件存储空间、如何提高对文件的访问速度是文件存储空间分配时要考虑的主要问题。

主要的文件分配方法：连续分配链接分配索引链接分配课堂练习6.3文件分配43连续分配是指在创建文件时，给文件分配一组连续的物理盘块，使用静态分配策略。所形成的物理文件为顺序文件。

连续分配优点:

－比较简单，容易实现；－顺序访问速度快，性能好(支持直接存取，即检索一个块也是非常容易。)缺点：－必须在文件创建时就知道文件的最大长度。－造成磁盘碎片

6.3文件分配44链接分配是指为每个文件构造磁盘块的链接表，每个块的第一个字用于指向下一块的指针，块的其它部分存放数据，由此形成的物理文件称为链接文件。链接分配分类：隐式链接显式链接6.3文件分配45在文件目录的每个目录表目中，都须含有指向链接文件的第一盘块和文件长度（或最后一个盘块的指针）

链接分配－隐式链接缺点：只适应顺序访问，对随机访问效率很差。此外，其可靠性也较差。－为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇。6.3文件分配46显式链接是指把用于链接文件的各物理地址指针，显式地放在内存的一张链接表中。该表在整个磁盘中仅设置一张。链接分配－显式链接优点：不会形成磁盘碎片。缺点:

随机存取却相当缓慢；另外，每个磁盘块存储数据的字节数不再是2的幂，降低了系统的运行效率。6.3文件分配47索引分配是为了解决连续分配和链接分配的问题而产生的。索引链接分配是文件逻辑组织中索引组织的物理实现。索引链接分配分类：

1.一级索引链接分配

2.多级索引链接分配

－适合于大的文件

6.3文件分配48思想：为每个文件分配一个索引块（表），把分配给该文件的所有盘块号，都记录到该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，必须在该文件的目录表目中，填上指向该索引块的指针。

索引链接分配－一级缺点：当文件较小时，索引块大部分空间未被使用上，造成索引块的利用率低。6.3文件分配思想：对大文件来说，分配给文件的索引块数量较多，各索引块之间也必须用链接指针链接起来，当检索第I块时，需将该文件的所有索引块读入内存，然后进行检索。UNIX系统在此基础上采用索引结点，即用i-结点的方法来解决文件的存储，具体细节见6.6.4节49索引链接分配－多级506.3文件分配文件F由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F中，作为其第30条记录。请回答下列问题，并说明理由。1）若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F的存储区域前后均有足够的空闲磁盘空间，则要完成上述操作最少要访问多少次磁盘块？F的文件控制块内容会有哪些改变？2）若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则要完成上述操作最少要访问多少次磁盘块？若每个磁盘块大小为1KB，其中4个字节存放链接指针，则该文件系统支持的文件最大长度是多少？课堂练习516.3文件分配【解】1）向前移动文件的前29条记录，每条记录读写各1次，腾出一个磁盘块空间，将该记录插入到此磁盘块作为第30条记录，故最少要访问磁盘块的次数=29*2+1=59。F的文件控制块内容中文件的起始地址和文件长度需要修改2）采用链接分配方式需要读取前29条记录链接指针，修改第29条记录的链接指针并写盘，第30条记录与链接指针一起写入一个磁盘块，这样完成上述操作最少要访问磁盘块的次数=29+1+1=31该文件系统支持的文件最大长度是：(1024-4)*232B=4080GB课堂练习6.4文件系统的可靠性52主要目标：实现文件的保密性、完整性和可用性。

具体的实现技术：用户认证：使用加密的口令、物理身份鉴别等技术。文件保护机制：使用保护域、存取矩阵（如存取控制表、权能表等）等技术。数据备份：包括全量备份和增量备份等。在第八章里面讲6.4文件系统的可靠性53

在文件的保护技术中，另外还有一个重要的内容是有关文件系统的一致性问题。解决不一致问题的方法是进行一致性检查。包括：1.块的一致性检查：

－建立两张表。每张表中，每块对应一个计数器，初始值设为0。第一张表的计数器记录了每块在文件中出现的次数；第二张表的计数器记录了每块在空闲块链表(或空闲块位图)中出现的次数。文件系统的一致性维护磁盘块读入内存，修改后再写盘，当写盘过程中系统崩溃，会出现不一致问题546.4文件系统的可靠性文件系统的一致性维护6.4文件系统的可靠性552。文件的一致性检查：一张计数器表，每个计数器对应于一个文件的i-节点。检验程序从根目录开始，沿着目录树递归下降，检查文件系统中的每个目录。对每个目录中的文件，其i-节点对应的计数器加1。若i-节点对应的计数器与i-节点内的共享文件链接数相同，则一致，否则不一致。文件系统的一致性维护6.5虚拟文件系统56Linux重要的特征之一就是支持多种文件系统，从而使多种文件管理系统和文件结构共存。为了支持多种文件系统和文件结构，Linux采用了虚拟文件系统(VirtualFileSystem,VFS)。

6.5虚拟文件系统57

VFS在Linux内核中扮演的角色如图6-28所示。当进程发起一个面向文件的系统调用时，内核调用VFS中的一个函数。586.5虚拟文件系统VFS提供以下功能：•记录可用的文件系统类型；•将文件系统与对应的存储设备联系起来；•处理面向文件的通用操作；•涉及具体文件系统的操作时，把它们映射到相关的具体文件系统。VFS由下列四个对象类型组成：超级块(superblock)对象：代表一个文件系统。存放已安装的文件系统的信息索引节点(inode)对象：代表一个文件。存放一个具体文件的所有信息目录项(dentry)对象：代表路径中的一个组成部分。存放目录项与对应文件进行链接的信息。文件(file)对象：代表由进程已打开的一个文件。存放已打开的文件与进程的交互信息，这些信息仅当进程访问文件期间才存于内存中

596.5虚拟文件系统1超级块(superblock)对象超级块描述了特定文件系统的信息，并存储在磁盘上的一个特定的扇区中每个特定文件系统，都有各自的超级块，如Ext2超级块当内核对一个特定文件系统进行初始化和注册时，系统在内存为其分配一个超级块，并从磁盘读取特定文件系统超级块中的信息填充进来，这是VFS超级块超级对象由许多数据项组成：Device：文件系统所在的块设备标识信息；Inodepointers：索引结点指针指向文件系统中已安装索引结点的第一个索引结点。而coveredinode指针指向此文件系统安装目录的inode。根文件系统的VFS超级块不包含covered指针；Blocksize：文件系统基本块的大小(以字节为单位)；Superblockoperations：指向此文件系统一组超级块操作例程的指针。这些例程被VFS用来读写inode和超级块；FileSystemtype：指向已安装文件系统的file_system_type结构的指针；FileSystemspecific：指向文件系统所需信息的指针606.5虚拟文件系统2索引结点对象一个索引结点(inode)与一个文件相关联。包含关联文件的除了文件的文件名和文件数据内容之外的所有信息文件名可以更改，但索引节点对文件是唯一的，且随文件的存在而存在。索引结点信息可以从磁盘索引节点中直接读入VFS的inode对象中在磁盘上的inode称为静态节点，读入内存VFS的inode称为动态节点。每个VFSinode包含下列域：

device：索引结点所在的块设备标识信息；

inodenumber：文件系统中唯一的inode号。

mode：表示此VFSinode的存取权限；

userids：所有者的标识符；

times：VFSinode创建、修改和写入时间；

blocksize：文件块的大小(以字节为单位)；

inodeoperations：指向一组例程地址的指针。

count：使用此VFSinode的系统部件数。

lock：用来对某个VFSinode加锁，如用于读取文件系统时；

dirty：VFSinode是否已经被修改过，如果是则底层文件系统需要更新。616.5虚拟文件系统3目录项对象目录项(directoryentry,dentry)对象是路径上的一个特定成分，该成分或为目录名或为文件名，为文件和目录的访问提供方便。例如，在路径/bin/vi中，VFS为根目录/、bin和vi分别创建了3个目录项对象，前两个是目录文件，后一个是普通文件。引入dentry的主要目的是对目录进行缓冲，加快对文件的快速定位，改进文件系统效率。dentry结构代表逻辑意义上的文件，描述文件的逻辑属性，它在磁盘上并没有对应的映像；而inode结构代表物理意义上的文件，记录文件的物理属性，它在磁盘上有对应的映像。一个有效的dentry结构必定对应一个inode结构一个inode可能对应多个dentry结构，也就是说，一个文件可以有多个文件名或路径名，626.5虚拟文件系统4文件对象文件对象代表一个进程所打开的一个文件文件对象包含如下一些数据项： 与该文件相关联的目录对象； 包含该文件的文件系统； 文件对象使用计数器； 用户ID； 用户组ID； 文件指针，即文件中下一次操作发生的当前位置。636.5虚拟文件系统5主要的数据结构之间的关系646.5虚拟文件系统6Linux文件系统的安装和管理同其他操作系统一样，Linux支持多个物理硬盘，每个物理磁盘可以划分为一个或多个磁盘分区，在每个磁盘分区上就可以建立一个文件系统。一个文件系统在物理数据组织上一般划分成引导块、超级块、inode区以及数据区。引导块位于文件系统开头，通常为一个扇区，存放引导程序、用于读入并启动操作系统。超级块记录文件系统的管理信息，因此不同的文件系统对应的超级块中存储的信息也不相同。inode区用于登记每个文件的目录项，第一个inode是该文件系统的根节点。数据区则存放文件数据或一些管理数据。一个安装好的Linux操作系统究竟支持几种不同类型的文件系统，是通过文件系统类型注册链表来描述的，VFS以链表形式管理已注册的文件系统。向系统注册文件系统类型有两种途径，一是在编译操作系统内核时确定，并在系统初始化时通过函数调用向注册表登记；另一种是把文件系统当作一个模块，通过kerneld或insmod命令在装入该文件系统模块时向注册表登记它的类型。6.6文件系统的类型65文件系统按类型可分成以下四种:磁盘文件系统

:是一种设计用来利用数据存储设备来保存计算机文件的文件系统，如：FAT、exFAT、NTFS、ext3、ext4等。闪存文件系统

:是一种设计用来在闪存上储存文件的文件系统。伪文件系统

:启动时动态生成的文件系统，包含有关当前正在运行的内核的许多信息、配置和日志。网络文件系统:NFS，（NetworkFileSystem）是一种将远程主机上的分区（目录）经网络挂载到本地系统的一种机制，是一种分布式文件系统。6.7文件管理实例：UNIX文件管理66UNIX操作系统可由多个可以动态安装及拆卸的文件系统组成。UNIX文件系统主要分为两大类：根文件系统和附加文件系统。

（1）UNIX文件类型（2）UNIX文件系统存储结构（3）目录与索引结点（4）文件分配（5）文件系统的打开与读写(1)UNIX文件类型67在UNIX中文件共分为六种：普通文件(ordinaryfile)：文本文件和二进制文件目录文件(directory)特殊文件(specialfile)：设备文件，在/dev目录下有名管道文件链接文件：硬链接，基于索引结点的共享符号链接文件(symboliclinks)：包含被链接文件的路径名(2)UNIX文件系统存储结构UNIX文件系统结构的组成元素是引导块

(Bootblock,0#块)：存储了引导或初启操作系统的引导代码。超级块(Superblock,1#块)：用来描述文件系统的状态。如指出文件系统的大小、有关空闲块分配和回收用的堆栈等。索引结点表(Inodetable,2#~K#块)：用来存放文件说明信息。UNIX系统把一个文件的说明信息称为i结点或索引结点。索引结点表的大小由系统管理人员在进行系统配置时指定。数据块(Datablock,K+1#块之后)用来存放文件数据，包括目录文件数据68(3)

目录与索引结点69

UNIX文件系统具有如图6-23所示的树型层次结构(3)

目录与索引结点70为了减少检索文件访问的物理块数，UNIX把目录中的文件名和其它文件说明信息分开，把除文件名之外的其它文件属性信息组成文件控制块，称为索引结点(i-node)。一个目录是一个包含文件名列表和指向相关索引结点指针的文件

索引结点存放在物理存储器的索引结点表中，从1开始顺序编号，记为i-no(4)

文件分配71文件分配是以块为单位，采用动态分配方式进行分配。UNIX采用多级索引分配方法，即基于索引结点的分配方法。文件数据块的直接索引指针和间接索引的部分指针保存在索引结点表中72(4)

文件分配73(4)

文件分配文件系统的存储分配和回收包括索引结点和磁盘块的分配和回收。系统将有关空闲索引结点和空闲磁盘块的信息保存在超级块(如图6-22)中。超级块包括以下等方面内容：文件系统的大小；文件系统中的空闲块数目；可用的空闲块表；空闲块表中的下一个空闲块的下标；索引结点表的大小；空闲索引结点数目；空闲索引结点表；空闲索引结点表中下一个空闲索引结点的下标；空闲块表的锁字段和空闲索引结点表的锁字段；用来指示超级块已被修改的标志。74(4)

文件分配当安装一个文件系统时，核心要将超级块读入内存中当创建一个新文件时，核心要为该文件分配一个索引结点当进程写文件信息时，核心要从文件系统中分配空闲磁盘块，把它作为直接或间接数据块UNIX系统按成组链接法来组织空闲磁盘块，如图6-17所示分配一个空闲磁盘块时，就把超级块中的空闲块号表中的下一个空闲块分配出去。回收一磁盘块时，分未满和已满两者情况处理。这种方案有以下几点好处：(1)索引结点大小固定，并且相对比较小，因而可以在主存中保留比较长的时间。(2)小文件可以通过很少的间接访问，或不通过间接访问，从而减少了处理时间和磁盘访问时间。(3)理论上，文件大小对所有的应用程序来说都是足够的。(5)文件系统的打开与读写75进程对文件的操作都是通过系统调用完成的。有关文件操作的系统调用所涉及到的主要数据结构有：用户打开文件表、系统打开文件表和内存索引结点表766.7文件管理实例：Windows文件管理(NTFS)NTFS(NewTechnologyFileSystem)是WindowsNT操作环境和WindowsNT高级服务器网络操作系统环境的文件系统

。

NTFS取代了文件分配表(FAT)文件系统。（1）NTFS的主要特性（2）NTFS卷和文件结构（3）NTFS的可恢复性

776.7文件管理实例：Windows文件管理(NTFS)(1)NTFS的主要特性可恢复性安全性大磁盘和大文件多数据流日志压缩和加密硬链接和符号链接通用索引功能

786.7文件管理实例：Windows文件管理(NTFS)(2)NTFS卷和文件结构扇区(sector)：磁盘上最小的物理单位簇(cluster)：一个或多个连续的扇区(磁盘上彼此紧挨着)

卷(volume)：磁盘上的逻辑分区。一个卷包含文件系统信息、一组文件及卷中剩余的可以分配给文件的未分配空间796.7文件管理实例：Windows文件管理(NTFS)(2)NTFS卷和文件结构NTFS卷布局分区引导扇区：包含卷的布局信息、文件系统的结构以及引导启动信息和代码主文件表：包含关于在这个NTFS卷中所有文件和文件目录的信息以及关于可用的未分配空间的信息。每一行描述了该卷中的一个文件或文件夹。系统文件：MFT2、日志文件、簇的位映像、属性定义表。806.7文件管理实例：Windows文件管理(NTFS)(3)NTFS的可恢复性支持可恢复性的重要组成I/O管理日志文件服务高速缓存管理器：通过延迟写和延迟提交技术优化磁盘I/O虚存管理器为确定可恢复性，需要以下四个步骤(1)调用日志文件系统，在高速缓存内的日志文件中记录任何修改卷结构的事务(2)NTFS修改这个卷(在高速缓存中)；(3)高速缓存管理器调用日志文件系统，提示它刷新磁盘中的日志文件；(4)如果日志文件在磁盘上的更新是安全的，则高速缓存管理器把该卷的变化刷新到磁盘中。第7章输入/输出管理本章目标掌握I/O管理的基本原理、算法及处理机制能够识别I/O管理功能实现的关键环节和影响因素能够认识到I/O管理功能实现有多种方案可选择，能够通过文献研究，在多种方案中，寻求一种更合适的解决方案能够遵循系统化的基本要求，确定解决I/O管理的设计目标和技术方案能够运用所学知识解决I/O管理设计与实现问题，能在设计实现中体现创新意识能够对实验结果进行输入条件关联分析和解释，并能综合应用场景和技术需求，得出结论的有效性第7章输入/输出管理

7.1I/O管理概述

7.2

I/O控制方式

7.3

I/O缓冲

7.4

设备驱动程序

7.5

设备分配

7.6

磁盘存储器的管理

7.7

时钟管理和电源管理

7.8

输入/输出管理实例通常将处理器和主存以外的设备称为外部设备（或I/O设备）。I/O设备种类繁多，操作系统必须提供相应的设备管理程序，简单、方便、高效、统一使用各类设备。7.1I/O

管理概述7.1.1I/O管理目标与功能

7.1.2I/O系统组成7.1.1

I/O管理目标与功能I/O子系统概述I/O子系统指对设备进行管理的那部分操作系统。I/O管理目标为用户提供方便、统一的界面。提高资源的利用率。I/O管理功能设备控制设备分配与回收。其它功能建立统一的独立于I/O设备的应用接口；完成设备驱动程序，实现真正的I/O操作；处理I/O设备的中断处理；管理I/O缓冲区；实现设备的虚拟性和独立性

7.1.2

I/O系统组成5.1.2I/O子系统设计目标I/O设备

设备控制器

通道

I/O统一接口7.1.2

I/O系统组成5.1.2I/O子系统设计目标系统组成I/O设备：用于完成数据的输入与输出；控制器：用于控制对应的I/O设备；通路：用于数据传输(总线型或通道型)

；应用接口：为不同设备的使用提供统一的接口。7.1.2

I/O系统组成5.1.2I/O子系统设计目标系统总线主机(CPU、存储器)磁盘控制器磁盘显示器控制器显示器其它控制器其它设备存储器通道A控制器A设备1设备2设备3设备4通道B控制器B总线型系统通道型系统7.1.2

I/O系统组成5.1.2I/O子系统设计目标关键技术I/O调度技术：缓冲区管理技术。设备分配与回收技术。虚拟设备技术。

I/O设备

按设备的从属关系分类：系统设备：如键盘，显示器等，OS安装时就进行管理。用户设备：如网卡，扫描仪，打印机等，用户安装驱动程序。按设备的共享属性分类：共享设备：同一时间段允许多个进程使用。如硬盘，光盘等。独占设备：同一时间段只许一个进程使用。如键盘，打印机等。虚拟设备：将独占设备转化为共享设备。按传输速率分类：低速设备：传输率：几个B-几百B/S。如键盘，鼠标。中速设备：传输率：几个KB-几十KB/S。如打印机。高速设备：传输率：几十KB-几个MB/S。如磁盘、光盘机。按信息交换单位分类：字符设备：以字符为单位组织处理信息。如打印机。块设备：以数据块为单位组织处理信息。如磁盘，光盘。I/O设备的分类

设备控制器1.设备控制器的功能接收和识别命令数据交换获取设备的状态地址识别2.设备控制器的组成设备控制器与处理机的接口I/O控制逻辑设备控制器与设备的接口

通道1.什么是通道通道指专门用来处理输入/输出工作的处理器(简称I/O处理器)。2.通道的种类字节多路通道数据选择通道数组多路通道3.通道程序操作码内存地址传送字节数特征位

I/O统一接口设备硬件级设备驱动程序……设备驱动程序设备驱动程序接口逻辑I/O系统调用接口内核内核级用户级用户进程库函数用户进程7.2I/O控制方式7.2.1程序直接控制方式7.2.2中断控制方式7.2.3DMA控制方式7.2.4通道控制方式程序直接控制方式：用询问指令测试设备状态，决定主存与设备交换一个字。早期计算机采用之。

优点：工作过程简单

缺点：CPU的利用率很低

7.2.1

程序直接控制方式中断控制方式：I/O正常/异常结束中断CPU要求处理。I/O操作直接由CPU控制。优点：提高了CPU的利用率，并且支持CPU与设备的并行工作。

缺点：数据传输中，中断发生次数较多，耗费大量CPU时间。7.2.2

中断控制方式直接存储器存取（DMA）控制方式

在外围设备和内存之间开辟直接的数据交换通路。该方法一般用于块设备的数据传输。

优点：不用CPU干预，减轻了CPU的负担；

I/O数据传送速度大大提高；

特点：1）数据传输的基本单位是数据块2）传输数据直接从设备送入内存或相反3）数据传输在DMA控制器控制下完成4）硬件线路比较复杂7.2.3DMA控制方式DMA控制器的组成主机与DMA控制器的接口

DMA控制器与块设备的接口

I/O控制逻辑主机与控制器的接口由四类寄存器实现。命令/状态寄存器内存地址寄存器数据寄存器数据计数器DirectMemoryAccess(DMA)OperationofaDMAtransferDMA工作过程参数准备阶段DMA工作阶段中断处理阶段交换数据的字节数，主存地址，辅存地址，交换类型等DMA发传输请求，CPU应答，DMA控制器接管对总线的控制，主存寻址，启动数据传输利用中断向CPU报告DMA操作结束7.2.4

通道方式和输入输出处理器DMA输入输出控制方法只解决了外存与主存的快速数据传输，CPU的效率不高，为提高CPU与I/O设备的并行性，引入了通道结构。通道

独立于CPU的专门用来处理输入输出控制的处理器（简称I/O处理器），它控制设备与内存直接进行数据交换。有自己的通道指令，指令受CPU启动，操作结束向CPU发中断信号。举例：通道方式下的数据输入过程：1）CPU发启动指令，指明I/O操作，设备号和对应通道。2）通道接收CPU指令，读出内存中的通道指令，执行通道程序，控制设备将数据传输到指定内存区域。3）数据传输结束后，向CPU发中断请求，CPU转中断处理程序。通道控制方式与DMA方式的比较相似处：都以内存为中心，实现设备和内存直接交换数据。不同处：

1）DMA方式中，数据传输方向，内存始址，数据块长度都由CPU控制；通道方式中，这些由通道控制。2）通道控制方式可以做到一个通道控制多台设备与内存进行数据交换，DMA方式时每台设备至少有一个DMA控制器。2.通道的类型字节多路通道选择通道数组多路通道以字节为单位分时传送以成组方式传送分时传输一个数据块主要用于低速或中速设备主要用于高速设备用于中速设备分时并行操作通道利用率低传输速率高，通道利用率高3.通道程序

1)通道程序：由通道命令按照一定的控制要求组织起来的，它规定I/O设备所应执行的操作及顺序。2）通道命令（CCW）：规定了对设备操作的指令。包含信息：l

操作码：规定了指令所执行的操作，有数据传输类、通道转移类、设备控制类三类。l

内存地址：标明了数据送入内存或从内存取出时的内存首址。l

传送字节数：表明本指令所要读或写的字节数。l

特征位：程序结束位、记录结束标志位。3）通道程序的组织形成通道程序放在主存；将通道程序的首地址送入通道地址字（CAW）。即通知通道；通道程序在执行过程中也把信息汇集在主存的另一个固定单元中，该单元称为通道状态字CSW；CSW指出包括下一条通道命令的主存地址、通道及与之相连的控制器和设备的状态，以及数据传输的情况。4）一次的I/O执行过程（1）根据要求组织好通道程序，且把通道程序的首地址放在通道地址字中。（2）CPU执行“启动I/O”指令启动通道工作，通道逐条执行通道命令，控制设备实现输入输出操作。（3）通道完成输入输出操作后，向CPU报告执行情况，CPU处理来自通道的信息。7.3I/O缓冲7.3.1单缓冲

7.3.2双缓冲

7.3.3循环缓冲

7.3.4缓冲池

7.3.5缓冲的作用

缓冲技术是为了缓解快速的主机和慢速的I/O设备速度不相匹配的矛盾。引入缓冲的主要原因：缓解CPU与I/O设备间速度不匹配的矛盾，提高CPU与I/O设备之间的并行性减少对CPU的中断频率，放宽对中断响应时间的限制7.3.1

单缓冲在内存开辟一个缓冲区预输入或缓输出减少对磁盘的操作优点：缓解设备与处理机的处理速度矛盾缺点：设备和设备之间不能通过单缓冲达到并行操作传输传输操作系统用户进程I/O设备7.3.2

双缓冲两个系统缓冲区一个用于缓冲输入、一个用于缓冲输出或者两个都用于输入或输出优点：提高了CPU与设备，设备与设备之间的并行性缺点：难以满足多进程和多设备之间并行操作的需要传输传输操作系统用户进程I/O设备7.3.3

循环缓冲多个缓冲区形成循环缓冲链一部分用于缓冲输入、一部分用于缓冲输出优点：提高了CPU与设备及设备与设备之间的并行能力缺点：消耗大量的内存空间，并且利用率也不高传输传输操作系统用户进程I/O设备缓冲区1……缓冲区n7.3.4

缓冲池缓冲池：把多个缓冲区连接起来统一管理，既可用于输入又可用于输出的缓冲结构。1.缓冲池结构每个缓冲区由两部分组成：缓冲区首部和缓冲体。三种队列：空白缓冲队列em：队首指针为F(em)和队尾指针为L(em)输入缓冲队列in：队首指针为F(in)和队尾指针为L(in)输出缓冲队列out：队首指针为F(out

)和队尾指针为L(out

)7.3.4

缓冲池工作缓冲状态：收容输入缓冲区(hin)、提取输入缓冲区(sin)、收容输出缓冲区(hout)、提取输出缓冲区(sout)。收容输入提取输入缓冲池用户进程输入设备hinsoutsinhout收容输出提取输出输出设备输入缓冲队列in输出缓冲队列out空白缓冲队列em7.3.4

缓冲池2.管理(1)take_buf(type)：取出一个缓冲区(2)add_buf(type,number)：插入缓冲区(3)get_buf(type,number)：申请缓冲区(4)put_buf(type,work_buf)：放入相应缓冲区3.工作过程(1)收容输入。(2)收容输出。(3)提取输入。(4)提取输出。7.3.5

缓冲的作用缓冲是用来平滑I/O需求峰值的一种技术。提高操作系统效率和单个进程性能的一种方法7.4设备驱动程序1设备驱动程序的模式2设备驱动程序的功能3设备驱动程序的特点4设备驱动程序的处理过程1设备驱动程序的模式设备驱动程序（DeviceDriver）：控制设备直接进行各种操作的内核模块。特点：与设备类型一一对应，设备不同，驱动程序也不相同；一个设备驱动程序也可控制一种给定类型的多种设备。好处：方便用户操作使用物理设备，降低操作系统设计复杂性。驱动程序的两种实现模式：（1）驱动程序作为内核过程操作系统中使用的主要模式。

优点：便于实现I/O子系统的层次模型，将其作为特殊文件处理，提供统一的界面，管理和使用。（2）驱动程序作为独立的进程（I/O进程）

缺点：不便于I/O子系统的层次实现；系统开销大；不能将其与文件统一地处理2设备驱动程序的功能将接收到的上层软件的抽象要求转换为具体要求。检查用户I/O请求的合法性，了解I/O设备状态，传递参数，设置设备工作方式。发出I/O命令，启动设备，完成指定I/O操作。

及时响应处理控制器或通道发出的中断请求。对有通道的系统，根据用户I/O请求，自动构成通道程序。3设备驱动程序的特点设备驱动程序是请求I/O的进程与设备控制器之间的一个通信程序。设备驱动程序与I/O设备的特性紧密相关。设备驱动程序与I/O控制方式紧密相关。设备驱动程序与硬件紧密相关。4设备驱动程序的处理过程设备驱动程序所做的工作：l

执行进程提出的I/O请求。l完成I/O后要用中断向CPU报告完成情况，并准备好执行下一个请求。l

按某种优化策略维护I/O请求队列，以优化系统性能。4设备驱动程序的处理过程执行I/O请求的驱动程序一般处理过程：1）将用户及上层软件对设备控制器的抽象要求转为具体要求；（相对地址物理地址）2）检查I/O请求的合法性；3）读出和检查设备的状态；4）传送必要的参数（如传送字节数、主存始址送入相应的控制寄存器）；5）设置工作方式；6）启动I/O设备；（向命令寄存器发控制命令）7.5设备分配7.5.1设备分配原则与分配方式

7.5.2设备分配时应该考虑的因素

7.5.3设备分配中的数据结构7.5.4I/O设备分配的基本流程7.5.5SPOOLing技术7.5.1

设备分配原则与分配方式

1．设备分配原则提高设备利用率并避免死锁方便用户使用设备2．设备分配方式静态分配动态分配7.5.2

设备分配时应考虑的因素1．I/O设备的固有属性独占设备的分配共享设备分配虚拟设备分配

2．I/O设备的分配算法(1)先来先服务(2)优先级高者优先

3．设备分配的安全性⑴安全分配方式⑵不安全分配方式

4．设备无关性将用户程序和具体物理设备隔离开来，即实现设备无关性(独立性)

逻辑设备与物理设备好处：设备分配时的灵活性易于实现I/O重定向独占设备分配中的数据结构：

设备控制表（DCT）

系统为每一个设备都设置一张设备控制表，用于记录本设备的情况。包括：设备标识符，设备类型，设备状态，重执行次数或时间，控制器控制表指针，设备队列指针。

控制器控制表（COCT）和通道控制表（CHCT）

每个控制器设置一张控制器控制表，每个通道配有一张通道控制表。COCT包括控制器标识符，控制器状态，与控制器连接的通道表指针，控制器队列队首，队尾指针。

CHCT包括通道标识符，通道状态，与通道连接的控制器表指针，

通道队列队首，队尾指针。

系统设备表（SDT）

记录系统中所有设备信息，每个设备占一个表目。包括设备类型，标识符，DCT和设备驱动程序的地址。7.5.3

设备分配中的数据结构SDT、DCT、COCT和CHCT的关系SDT表目1…表目i设备类型设备标识获得设备的进程DCT指针…DCT设备类型设备标识设备忙/闲标识COCT指针设备等待队首设备等待队尾…COCT控制器标识控制忙/闲标识CHCT指针控制器等待队首控制器等待队尾…CHCT通道标识通道忙/闲标识通道等待队首通道等待队尾…分配步骤：1）分配设备。查找系统设备表，若找到好的空设备，并满足安全性要求，则将该空设备分配给请求进程，然后转分配控制器，若不能分配，将进程PCB插入设备的等待队列。2）分配控制器。在DCT中查找与该设备连接的COCT，检查控制器是否空闲，若空闲，则将控制器分配给请求进程，然后转分配通道，否则请求进程PCB进入该控制器的等待队列。

3）分配通道。在COCT中查找与该控制器连接的CHCT，检查通道是否空闲，若是空闲，则将通道分配给该请求进程，然后启动I/O设备进行数据传送，否则该进程PCB进入该通道的等待队列上。

7.5.4

设备分配的基本流程7.5.5

Spooling技术问题的提出：系统中独占设备数目有限，不能满足多进程的需要设备的静态分配可导致等待进程被阻塞独占设备的利用率不高为此现代操作系统提供虚拟设备来解决这些问题。1．什么是SPOOLing脱机工作模式7.5.5

Spooling技术1．什么是SPOOLing假脱机操作SPOOLing(SimultancausPeriphernalOperationOn-Line)技术在一台共享设备（如高速、大容量的磁盘设备）上模拟若干台独占设备的操作，使每一台独占设备成为若干台可并行操作的虚拟设备，即把独占设备变成逻辑上的共享设备，从而提高了设备利用率和系统的效率，这种技术被称为虚拟设备技术。实现这种技术的硬件和软件系统被称为Spooling(simultaneousperipheraloperationonline)系统，或称为假脱机系统。使用Spooling技术所提供的设备就称为虚拟设备。7.5.5

Spooling技术2.SPOOLing的组成(1)输入井和输出井(2)输入缓冲区和输出缓冲区(3)输入进程和输出进程3．SPOOLing系统的工作原理磁盘输入设备输入缓冲区输出缓冲区输出设备输入井输出井输入进程输出进程7.5.5

Spooling技术4．SPOOLing系统的特点(1)提高了I/O速度(2)将独占设备改造为共享设备(3)实现了虚拟设备的功能7.6

磁盘调度7.6.0

概述7.6.1

磁盘性能参数7.6.2

磁盘调度7.6.3

磁盘阵列概述磁盘数据的组织磁盘每面上一系列记录信息的同心圆称为磁道，磁道间有空隙,把它们从0开始由外向内顺序编号。不同盘面上具有相同编号的磁道形成一个个柱面。每个磁道一般都划分若干个相等的扇形弧段，每个弧段称为一个扇区或物理纪录，各扇区实际物理长度不同。每个扇区对应的磁道弧长虽然不一，但存储的信息量是相同的。每个扇区一般包括两个字段：标识符字段和数据字段。每个物理记录参数：柱面号，磁头号和扇区号。概述2．磁盘的类型固定头磁盘

活动头磁盘柱面号

磁头号扇区号

7.6.1磁盘性能参数

寻道时间：活动磁头将读、写磁头移动到相应的磁道所花费的时间。

旋转时间：读、写定位于某一磁道的扇区所需要的时间。

传送时间：数据写入磁盘，或从此磁盘读出的时间。磁盘I/O请求服务的时间为以上三部分之和，其中寻道时间所花费的时间最长。7.6.2磁盘调度

先来先服务算法

最短寻道时间优先算法

扫描算法

循环扫描法

对队列多步扫描法

磁盘调度包括“移动调度”和“旋转调度”，分别针对减少寻道时间和旋转时间。我们主要介绍“移动调度”，即根据用户作业发出的磁盘I/O请求的柱面位置，来决定请求执行顺序的调度。其目的是尽可能的减少移动臂的移动距离。常用的算法有以下几种：先来先服务算法

（First-Come-First-Served,FCFS）

根据进程请求访问磁盘的先后顺序进行调度，而不管进程的优先级。

举例

优点：公平，处理简单，每个进程的请求都会得到处理。

缺点：未对寻道进行优化，致使平均寻道时间可能较长。举例：一个磁盘请求序列的磁道号为55，58，39，18，90，160，150，38，184。假定开始时，磁头位于100号磁道。184160150905855393818磁头移动方向磁头总移动量=(100-55)+(58-55)+(58-39)+(39-18)+(90-18)+(160-90)+(160-150)+(150-38)+(184-38)=498平均寻道时间=498/9=55.3最短寻道时间优先算法

（Shortest-Seek-Time-First,SSTF）

以申请者要求磁头移动距离大小作为优先的因素，磁道距离磁头当前位置愈近者优先。

举例

优点：平均等待时间得到改善，可以获得较好的寻道性能。

缺点：对用户进程请求的响应机会不是均等的，可能导致某些进程发生“饿死”现象。举例：一个磁盘请求序列的磁道号为55，58，39，18，90，160，150，38，184。假定开始时，磁头位于100号磁道。184160150905855393818磁头总移动量=(100-90)+(90-58)+(58-55)+(55-39)+(39-38)+(38-18)+(150-18)+(160-150)+(184-160)=248平均寻道时间=248/9=27.5磁头移动方向扫描算法

（SCAN，又称电梯调度）

不仅考虑申请者要求磁头移动方向，又考虑要求磁头移动距离，而且首先是方向一致，其次才是距离最短。

举例

优点：避免了饥饿现象。

缺点：优待了中间磁道的请求（因为被服务者无方向需求），有“磁臂粘着”现象。举例：一个磁盘请求序列的磁道号为55，58，39，18，90，160，150，38，184。假定开始时，磁头位于100号磁道。184160150905855393818磁头移动方向磁头总移动量=(150-100)+(160-150)+(184-160)+(184-90)+(90-58)+(58-55)+(55-39)+(39-38)+(38-18)=260平均寻道时间=260/9=28.9循环扫描法

（C-SCAN）规定磁头单向移动。将各磁道视作一个环形缓冲区结构，最大磁道号和最小磁道号构成循环。

举例

优点：等待时间较均衡。

缺点：有“磁臂粘着”现象。举例：一个磁盘请求序列的磁道号为55，58，39，18，90，160，150，38，184。假定开始时，磁头位于100号磁道。184160150905855393818磁头移动方向磁头总移动量=(150-100)+(160-150)+(184-160)+(184-18)+(38-18)+(39-38)+(55-39)+(58-55)+(90-58)=322平均寻道时间=322/9=35.8思想：把磁盘请求队列分成长度为N的子队列；按FCFS策略依次处理这些子队列，而每处理一个队列，又是用SCAN策略；在处理某一个队列时，新请求必须添加到其他某个队列中。

好处：可避免出现“磁臂粘着”现象。

多队列多步扫描（N-STEP-SCAN）策略

旋转调度当同一柱面有多个记录块的I/O请求时，对该柱面的服务应考虑旋转优化调度。如设每个磁道有9个记录块，当前I/O请求：(10,1,8),(10,0,5),(10,0,2),(10,1,1)旋转优化调度：按次序：(10,1,1),(10,0,2),(10,0,5),(10,1,8)来响应这些I/O请求，在磁盘旋转一周，即可完成这些I/O。若按I/O请求次序响应：(10,1,8),(10,0,5),(10,0,2),(10,1,1)，磁盘应旋转2.5周才可完成这些I/O。7.7时钟管理和电源管理7.7.1时钟管理1）时钟硬件简单的时钟被连接到110V或220V的电源线上，每个电压周期产生一个中断，来计时。另一种类型的时钟由三个部件构成：晶体振荡器、计数器和存储寄存器。大多数计算机具有一个由电池供电的备份时钟。对于一个连入网络的系统可以从远程主机获取当前时间。7.7时钟管理和电源管理时钟软件涉及时间的其他所有工作都必须由软件—时钟驱动程序完成。通常用于：1)维护日常时间；2)防止进程超时运行；3)CPU的使用情况记账；4)处理用户进程提出的报警系统调用；5)为系统本身的各个部分提供监视定时器；6)完成概要剖析、监视和统计信息收集。软定时器：是可编程时钟，可以设置它以程序需要的任何速率引发定时器中断。7.7时钟管理和电源管理7.7.2电源管理目的是实现更好的节能与环保。1）硬件问题大多数计算机厂商对于电源节约采取的一般措施是将CPU、内存以及I/O设备设计成具有多种状态：工作、睡眠、休眠和关闭。某些计算机具有两个甚至三个电源按钮来实现不同状态下的节能。

7.7时钟管理和电源管理2）操作系统问题

操作系统必须考虑若干问题来有效管理电源。必须决定关闭什么设备、何时关闭以及以什么状态关闭。采用智能算法或启发式方法做决定更好。