操作系统概念(共14页)

1、操作系统：操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度以及方便用户的程序集合，并充当计算机硬件和计算机用户的中介，控制和协调(xitio)各用户的应用程序对硬件的使用。DMA（直接(zhji)内存存取）存储设备层次金字塔：寄存器、高速缓存、主存、电子(dinz)磁盘、磁盘、光盘、磁带。（都是双向）OS（操作系统）三种基本类型：批处理系统、分时系统、实时系统操作系统的主要设计目标：从用户方面，是为了方便用户使用；从系统方面，是为了保证计算机系统高效执行操作系统是控制程序，控制程序管理用户，程序的执行和防止错误和计算机的使用不当大型计算机系统：是最早的计算机系统，用于处理

2、许多商业和科学应用。包括，批处理系统，多道程序设计系统，分时系统各种系统的思想特点批处理系统：脱机输入系统，批量送入执行，自动运行作业表 优点：节省作业装入时间 缺点：CPU经常空闲，人机交互性差多道程序设计系统：同时在内存中驻留多个程序，当一个进程等待时，系统会自己切换到另一个进程执行。 优点：通过组织作业使CPU中总有一个作业可执行，充分利用CPU 缺点：引起作业调度，CPU调度和内存磁盘管理的问题分时系统：解决了批处理系统的交互问题，作为多道程序设计系统的扩展，使CPU可在多个任务之间快速切换，用户可以得到在线交互实时系统：用于对处理器操作和数据流动有严格时间控制，分硬实时系统和软实时系

3、统。硬实时系统保证关键任务按时完成。软实时系统保证关键任务的优先级要高于其他任务的优先级且在完成之前保持其高优先级多道程序设计和分时是现代操作系统的主题双重模式操作分为用户模式和内核模式。解决问题：保护资源不被非法使用，保护计算机的安全特权指令：将能引起机器损害的指令成为特权指令，硬件仅允许在监督程序模式下执行系统调用：用户与操作系统交互，从而请求系统执行一些只有操作系统才能做的指令，每个这样的请求都是由用户调用来执行特权指令的，这种请求称为系统调用硬件保护：I/O保护：为防止用户执行非法I/O，可定义所有I/O指令为特权指令内存保护：通过基址寄存器和界限寄存器来确定程序所能访问的合法地址空间

4、并保护其他内存空间CPU空间：使用定时器来防止用户程序运行的时间过长。作用：防止用户程序无限占用CPU传递参数的三种方法：通过寄存器来传递参数寄存器传递参数块首地址参数通过程序存放或压入堆栈中，并通过操作系统弹出堆栈shell：命令解释程序，含于内核中，主要作用是获取并执行用户指定的下一条指令。操作系统(co zu x tn)中最重要的服务是程序执行，即系统必须能将程序装入内存并运行程序。程序必须能结束执行，包括正常或不正常结束。友好且有用的用户设计界面不再是操作系统统管(tn un)的功能API：一系列适用(shyng)于应用程序管理员的函数系统调用提供了操作系统的有效服务界面I/O系统：一

5、个包括缓冲、高速缓存和假脱机的内存管理部分。包括通用设备驱动器接口和特定硬件设备的驱动程序系统结构的思想及特点简单结构：较小，简单且功能有限分层方法：将操作系统模块化，分成若干层，每层建立在较低层上。最底层为硬件，最高层使用用户接口。（操作系统分为八个模块：进程管理、内存管理、文件管理、输入/输出系统管理、二级存储管理、联网、保护系统、命令解释系统）特点：系统分层采用模块化，简化了系统的设计和实现，每层都是利用较低层所提供的功能来实现的，但是对层的仔细认证的定义比较困难，与其他方法相比效率略差。微内核：将所有非基本部分从内核中移走，并将它们实现为系统程序或用户程序，剩余部分即为微内核。优点：便

6、于扩充操作系统，具有更好的安全性和可靠性，操作系统很容易从一种硬件平台设计移植到另一种硬件平台设计。缺点：要忍受系统功能总开销的增加而导致系统性能下降虚拟机：单个计算机的硬件抽象为几个不同的执行部件。有的系统程序可以很容易的被应用程序调用，虽然系统程序比其他子程序的层次要高，但是应用程序还是可以将他们的一切下层当成硬件的一部分看做一个整体，这种分成方法自然而然的逻辑延伸为虚拟机的概念功能：提供与基本硬件的相同的接口原因：在并行运行几个不同的执行环境（即不同的操作系统）时能共享相同的硬件优点：在虚拟机环境中，不同的系统资源具有完全的保护；不存在安全问题；系统容易被调试，为运作体系提供了一个很好地

7、平台，用于开发和研究的平台进程：可并发执行程序在一个数据集合上运行过程。进程是程序的一次执行，是可开发的程序在一个数据集合上的运行过程。通常包括堆栈段和数据段。PCB：进程控制块，能感知进程的存在，是进程存在的唯一标识。包括许多与一个特定进程相关的相关信息。如进程状态，程序计数器，CPU寄存器，CPU调度信息，内存管理信息。进程状态：新的：进程正在被创建 运行：指令正在被执行等待：进程等待一定时间的出现 就绪：进程等待分配给某个处理器终止：进程已经完成执行调度程序：进程在其生命周期中会在各种调度队列之间进行迁移，进程选择是由相应的调度程序来完成的。长期调度程序：从大容量存储设备的缓冲池中选择进

8、程并将他们装入内存以执行。长期调度程序控制多道程序设计的程度，即内存的进程数量。创建进程的平均速度等于进城离开系统的平均速度。因此，长期调度程序需要在进程离开系统时才被唤起。由于每次执行之间的较长的时间间隔，长期调度程序能使更多的时间来选择执行进程。中期调度程序：也称为交换，将进程移出内存，因此降低了多道程序设计的程度，之后，进程能被重新调用并从中断处继续执行。分时系统，引入中期调度程序。短期调度程序：从准备(zhnbi)可执行的进程中选择进程，并为其分配CPU。区别(qbi):选择进程的位置(wi zhi)不一样。执行频率上看，短期调度程序执行频率最高，中期次之，长期最低。上下文切换：将CP

9、U切换到另一个进程需要保护当前进程的状态并回复另一进程的状态。通过fork系统调用，创建一个新进程；对于新（子）进程，系统调用fork返回值为0，而对于父进程，返回值为子进程的进程标识符。当进程完成执行最后的语句并使用系统调动exit（）请求操作系统删除自身时，进程终止。这时，进程可以返回状态值（通常为整数）到父进程（通过系统调用wait（）所有进程资源被操作系统释放。进程间通信IPC共享内存 消息传递在操作系统试验中，TPG用共享内存；IPC用消息队列和信号量消息传递对于交换较少数量的数据很有用，他通常用系统调用来实现，且比共享内存更易于实现。而共享内存允许以最快的速度进行方便通信。比消息传

10、递快。线程的概念线程是一个实体；被系统调用和分配的基本单位；自己基本不用有资源，只拥有一些在执行中必不可少的资源，可与同属于一个进程的其他线程共享所拥有的全部资源；可以创建和撤销另一个线程；同一进程的多个线程可以并发执行。多线程优点：响应度高；资源共享；经济；多处理器体系结构利用。线程和进程的比较调度：传统OS中，调度和分派的基本单位是进程，用于资源的基本单位也是进程。引入线程的OS中，调度和分派的基本单位是线程，拥有资源的基本单位是进程。并发性：在引入线程的系统中，进程之间可以并发执行，同一进程的多个线程之间也可以并发执行，使系统具有更好的并发性，进一步提高了资源利用率以及系统吞吐量。拥有资

11、源：进程是拥有资源的基本单位。线程本身不用有资源，只拥有一定的必不可少的资源，可以访问其隶属进程的资源，可供同一进程的线程共享。系统开销：系统创建及撤销进程时的开销远大于创建和撤销线程时的开销。进程间切换的开销也远大于创建和撤销线程的开销。为什么要引入线程和进程OS中进程的引入：使多个程序可以并发执行，改善资源利用率，提高系统的吞吐量。OS中线程的引入：减少程序并发执行时所付出的时空开销，使OS具有更好的并发性。多线程模型含义及优缺点优点：响应度高，资源共享，经济，多处理器体系结构的应用。多对一模型：将多个用户级线程映射到一个内核级线程，线程管理在用户空间内完成。效率较高，但如果一个线程执行了

12、阻塞系统调用，就会阻塞整个进程。多个线程不可以运行在多个处理器上。一对一模型：将每个用户线程映射到一个内核线程，比多对一模型提供了更好的并发性，允许多个线程在多个处理器上并发运行。如果创建一个用户线程，同时就需要创建一个相应的内核线程。多对多模型：将多个用户级线程映射到少于或等于其数目的内核级线程，一对一模型由于用户线程和内核级线程是相对应的，因而一个应用程序不允许创建多于系统支持的最大线程数的线程，在多对多的模型中不存在这个问题。优点：开发人员可以创建任意多的用户(yngh)线程，并且相应的内核线程能在多处理器上并发执行，而且当一个线程执行阻塞系统(xtng)调用时，内核能调度另一个线程来执

13、行。调度(diod)准则：CPU使用率：是CPU尽可能忙吞吐量：指一个时间单位内完成进程的数量周转时间：从进程提交到进城完成的数量等待时间：是在就绪队列中等待所花时间之和响应时间：从提交请求到产生第一响应的时间需要使CPU使用率和吞吐量最大化而使周转时间、等待时间、响应时间最小化可抢占式调度（CPU决策发生环境）a.当一个进程从运行状态切换到等到状态b.当一个进程从运行状态切换到就绪状态c.当一个进程从等待状态切换到就绪状态d.当一个进程终止时a.d没有选择只有调度，此时称调度方案是非抢占的（或协作的），否则，称为抢占的。分派程序的功能：切换上下文，切换到用户模式，跳转到用户程序的合适位置以重

14、新启动这个程序各种调度思想及其优点FCFS（先到先服务调度）先请求CPU的进程，被首先分配到CPU优点：每个进程都能按到达的先后顺序执行保证绝对公平，实现简单自然，属于非占先式调度缺点：平均等待时间最长；产生护航效果，使CPU和设备利用率变低（护航效果：所有其他进程都等待一个大进程释放CPU）SJF（最短作业有限调度）将每个进程与其下一个CPU区间段关联，当CPU可用时，它会赋给具有最短后续CPU区间的进程优点：系统吞吐量大，平均等待时间短，有利于短作业缺点：不利于长作业，容易出现饿死现象；由于下一个CPU区间长度无法精确获得，因而只能采用预测的方法，这不适合于CPU短期调度优先权调度分为占先

15、（如果新加入就绪队列的优先级高于正在执行的进程的优先级，则抢占当前执行的程序）的和非占先的。每个进程都有一个优先权与其相连，具有最高优先权的进程会被分配到CPU，具有相同优先权的进程按FCFS顺序调度。优点：用户通过进程设置优先级，可以在一定程度上干预CPU调度。缺点：存在饥饿现象解决：逐渐增加在系统中等待时间很长进程的优先权。轮转法调度（可抢占的专门为分时系统设计的）定义时间片，循环执行进程。如果比时间片短，则执行完毕，如果不比它短，则执行时间片然后停止，加到队列尾部，等待再一次执行。优点：有利于分时系统地实现，提高并发行，缩短等待时间缺点(qudin)：对时间片长度需要(xyo)仔细(zx

16、)确定，时间片过长，RR调度就类似于FCFS调度，不能很好地缩短时间，时间片过短，需要有大量的上下文切换，导致CPU产生大量空闲时间多级队列调度将就绪队列分成多个独立队列，根绝进程的某些属性，如内存大小，进程优先级或进程类型，进程会被永久分配到一个队列，每个队列都有自己的调度算法优点：低调度开销缺点：不够灵活多级反馈队列调度根据不同的CPU区间特点以区分进程，如果进程食用过多的CPU时间，那么它就会被移到更低优先权队列，类似，在较低优先权中等待过长的进程会被转移到较高优先权队列。各种调度算法的甘特图临界资源：在一段时间内只允许一个进程访问的资源被称为临界资源，临界资源要求互斥的共享或互斥的访问

17、临界区问题四项基本原则互斥：如果进程P在其临界区内执行，那么其他进程都不能在其临界区内执行有空让进：如果没有进程在其临界区内执行且有希望进入临界区，那么只有那些不在剩余去内执行的进程可能参加决策，以选择谁能下一个进入临界区，且这种选择不能无限推迟有限等待：在一个进程作出进入其临界区的请求到该请求被允许期间，其他进程被允许进入其临界区的次数存在一个上限让权等待两进程解法进程共享两个变量Boolean flag2,int turn,Do flagi=true; true=j; while(flagj&turn=j) 临界区flagi=flase;剩余区 while(i)为证明这一算法正确，需要证明

18、互斥成立，前进要求满足，有限等待要求满足信号量：是一个整数变量，除了初始化外，只能通过wait（）和signal（）来访问信号量数据结构 Typedef struct Int value; Struct process *list;semaphoreWait操作定义Void wait(semaphore s)s.value-;if(s.value0)add this process to s,L;block();Signal操作(cozu)定义Void signal(semaphore s) S.value+; If(s.value=0)Remove a process P from L;wa

19、ke up (P);此问题解题(ji t)思路死锁，即组内的每个进程都等待一个事件(shjin)，而该事件只能由组内的另一个进程产生。无限期阻塞或饥饿：进程在信号量内无限期等待忙等待：当一个进程位于临界区内时，其他试图进入其临界区的进程都必须在其进入代码中连续循环。经典的同步问题有限缓冲问题读者-写者问题哲学家进餐问题管程（确保一次只有一个进程能在管程内活动）一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。思想：管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程（相当于通过管程的门）才能进入，而

20、管程每次只允许一个进程进入管程，从而实现进程间的互斥。管程实现进程间的互斥，进程同步由自定义的condition变量来实现，condition变量仅有的操作是wait和signal。41 .死锁与饥饿的含义 死锁：一个进程申请资源，如果资源不可用那么进入等待进程，如果所申请的资源被其他等待进程占有，那么该等待的进程有可能无法改变状态，这种情况称为死锁。 饥饿：进程在信号量内无限期等待。正常模式下，进程按如下顺序使用资源申请：如果申请不能立即被允许，那么申请进程必须等待知道它获得资源为止使用：进程对资源进行操作释放：进程释放资源死锁产生的四个必要条件（四个条件同时满足，引起死锁）互斥：必须有一个

21、资源处于非共享模式，即一次只有一个进程使用，如果另一个进程申请该资源，那么申请进程必须延迟直到释放该资源为止。占有并等待：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有不剥夺：非抢占资源不能被抢占，即只能在进城完成其任务之后，才会释放其资源环路等待(dngdi)：有一组进程（p1,p2pn），p0等待(dngdi)的资源为p1所占有(zhnyu)，p1等待的为p2所占有，pn-1所等待的为pn所占有，pn等待的为p1所占有资源分配图如果图中没有环，那么系统没有进程死锁。如果有环，那么可能存在死锁。如果每个资源类型刚好有一个实例，那么有环就意味着会出现死锁。资源分配图死锁

22、处理方式使用协议以预防或避免死锁，确保系统不会进入死锁状态允许系统进入死锁状态，然后检测它并加以恢复（检测与解决）可忽视这个问题，认为死锁不可能在系统内发生（鸵鸟策略）死锁预防互斥：通常不能通过否定互斥条件来预防死锁，有的资源本身就是非共享的。占有并等待：一种可以使用的协议是进程在执行申请前，申请并获得资源不剥夺：为确保这一条件不成立，可使用如下协议，如果一个进程占有并申请另一个不能立即分配的资源，那么其现在已分配的资源都会被抢占环路等待：一个确保此条件不成立的方法是对所有资源类型进行完全排序且要求每个进程按照递增顺序申请资源死锁避免：根据每个进程可能申请的每种资源实例的最大需求的实现信息可以

23、构造一个算法以确保系统不会进入死锁状态。安全队列：进程顺序（p1，p2，.，pn）如果对于每个pi，pi申请的资源小于当前可用资源加上pj（ji）占有的资源，那么这一顺序为安全队列。有了安全状态的概念，可定义避免算法以确保系统不会出现死锁，其思想是简单的确保系统始终处于安全状态。开始系统处于安全状态，当进程申请一个可用的资源时，系统必须确定这一申请时可以立即分配还是要等待，只有分配后系统仍处于安全状态，才允许申请。银行家算法思想：当新进程进入系统时，它必须说明其可能需要的每种只有最大类型的实例最大数量，这一数量不可能超过系统资源的总量，当用户申请一组资源时，系统必须确保这些资源的分配是否仍使系

24、统处于安全状态，如果会，就可以分配资源；否则，进程必须等待直到某个其他进程释放足够资源为止。基地址寄存器含有最小的合法物理内存地址，而界限地址寄存器决定了范围的大小，只有操作系统可以通过特殊的特权指令来加载基地址寄存器和界限地址寄存器。地址绑定通常，将指令与数据绑定到内存地址有以下几种情况：编译时，如果在编译时就知道进程将在内存中的驻留地，那么就可以生成绝对代码。加载时，如果编译时不知道进程将驻留在何处，那么编译器就生成可重定位代码。执行时，如果进程在执行时从一个内存段移到另一个内存段，那么捆绑必须延迟到执行时才进行。CPU所生成的地址通常称为逻辑地址，而内存单元所看到的地址（即加载到内存地址

25、寄存器中的地址）通常称为物理地址。编译时和加载时地址捆绑生成相同的逻辑地址和物理地址。执行时的地址捆绑方案导致不同的逻辑地址和物理地址。交换（联系中期调度） 内存交换空间（磁盘）进程需要在内存中以便执行。进程可以暂时从内存中交换到备份存储上，当需要再次执行时间再调回到内存中。图示P241图8.5使用磁盘作为备份存储的两个进程的交换。通常，一个交换(jiohun)出的进程需要交换(jiohun)回它原来所占有的内存空间。这一限制是由地址绑定方式决定的。如果绑定是在汇编时或加载时所决定的，那么就不可以移动到不同的位置。如果绑定在运行时才确定，由于物理地址是在运行时才确定的，那么进程(jnchng)

26、可以移到不同的地址空间。内存必须容纳操作系统和用户进程。内存分配方法：连续内存分配内部碎片 外部碎片分页帧 页 页大小=帧大小 逻辑内存、物理内存页表包含每页所在物理内存的基地址。采用分页技术不产生外部碎片，产生内部碎片。课本P248帧表：每个条目对应一个帧，以表示该帧是空闲还是已占用。每个进程都有一个页表，页表的指针存在于进程PCB中。页表使用方式：将页表放在内存中，并将页表基地址寄存器指向页表（PTBR）TLB转换表缓冲区，TLB包括页表中一小部分条目。当CPU产生逻辑地址时，其页号提交给TLB，TLB先在自身中查找，若有，则继续；若不在TLB中，则需访问页表。查找帧号，并将页号、帧号增加

27、到TLB中。成功：访问TLB 不成功：访问TLB+两次访存计算有效内存访问时间（页表长度寄存器PTLR：表示页表大小，该寄存器的值用于检查每个逻辑地址以验证其是否位于进程的有效范围内）分页的优点：共享公共代码 消除外部碎片分页下的内存保护：在页表中，有效-无效位、读写位与每一条目关联。有效-无效位表示相关页是否在进程的逻辑地址空间中。读写位定义一个页是可读写的还是只读的。页表结构：多级分页反向分页：对于每一个真正的内存页或帧只有一个条目，每个条目包含保存在真正内存位置的页的虚拟地址及拥有该页的进程信息，使整个系统只有一个页表，对每个物理内存的页只有一条相应条目。虚拟内存的作用：1.将逻辑内存和

28、物理内存分开；2.允许文件和内存通过共享页而为两个或多个进程所共享。虚拟内存的实现：按需调页（在需要的时间才调入相应的页）调页：对进程的单个页进行操作交换：对整个进程进行操作在换入进程时，按需调页程序据推测将所需页调入内存。当进程试图访问在页表中标记无效的位时，引发页错误陷阱。这种陷阱是由于操作系统未能将所需的页调入内存所引起的。当发生页错误陷阱时，处理页错误步骤如下：检查进程的内部页表（通常与PCB一起保存），以确定该引用是合法还是非法的地址访问；如果引用非法，那么终止(zhngzh)进程。如果引用有效但是尚未调入页面，那么现在应调入；找到一个空闲(kngxin)帧（例如，从空闲帧链表中选取

29、(xunq)一个）调度一个磁盘操作，以便将所需要的页调入刚分配的帧；当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中；重新开始因陷阱而中断的指令，进程现在能访问所需要的页，就好像它似乎总在内存中；硬件支持：1.页表，利用其有效-无效位或保护位；2.次级存储器：有效访问时间：EAT=（1-p）*ma+p*页错误时间（ma内存访问时间）写时复制写时复制页：如果任何一个进程需要对页进行写操作，就创建一个共享页副本。写时复制允许父进程和子进程开始时共享一个页面。（只有可能被修改的页才需标记为写时复制，不能修改的页为子进程和父进程所共享）虚拟内存允许在用系统调用fork（）创建进程期间共

30、享页，从而加快进城创建。页面置换：页面换算法FIFO页置换：为每个页调入记录着该页调入内存的时间，当必须置换这一页时将选择最旧的页。 优点：容易理解和实现缺点：其性能不总是很好Belady异常：页错误率可能会随所分配的帧数的增加而增加最优页置换算法（置换那些在最长时间中不会被使用的页）优点：是所有算法中产生错误率最低的且不存在Belady异常；缺点：难以实现LRU页置换（置换最长时间没有使用的帧）优点：相对于最优页置换算法置换容易实现且效果不错，优于FIFO置换缺点：可能需要大量硬件支持近似LRU页置换第二次机会页置换算法二次机会算法增强型二次机会算法基于计数的页置换最不经常使用页置换算法：L

31、FV最常使用页置换算法：MFV 帧分配 平均分配比例分配 页置换时：全局置换：允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程；局部置换：每个进程仅从自己的分配中进行选择；颠簸：定义：若从一个进程在换页上的时间要多于执行时间，那么(n me)这个进程就在颠覆。原因(yunyn)：图示p294图9.18系统(xtng)颠覆系统颠覆的原因防止系统颠覆的方法：页错误频率：当页错误太高时，进程需要更多帧。若页错误率太低，进程可能有太多帧，可以为所期望的页错误率设置上限和下限。如果错误率超过上限，那么为进程分配更多的帧；如果错误率低于下限，那么可以从该进程中移走帧。工作集合模型（

32、最近*个引用的页集合称为工作集合，工作集合是程序员局部的近似）文件是记录在外存上的相关信息具有名称的集合，文件是逻辑外存的最小分配单元。通常文件表示程序和数据。文件系统由两部分组成：一组文件（文件用于存储相关数据）和目录结构（目录用于组织系统内的文件并提供有关文件的信息）文件系统位于设备上。文件属性通常有：名称、标识符、类型、位置、大小等。所有文件的信息都保存在目录结构中，通常目录条目包括文件名及其唯一标识符。Open（） close（）在文件的基本操作中，每次都涉及为给定文件搜索相关目录条目。为了避免这种不断的搜索，许多系统要求在首次使用文件时，使用系统调用open（），操作系统维护一个包含

33、所有打开文件的信息表（打开文件表）。当需要一个文件操作时，可通过该表的一个索引指定文件，而不需要搜索。（课本P323）Open（）操作调用open（）会首先搜索系统范围内的打开文件表以确定该文件是否被其他进程使用，若不存在，则操作open（）会根据文件名搜索目录，并将目录条目复制到打开文件表。调用open（）也可接受访问参数：创建、只读、只写、添加等。该模式可以根据文件许可位进行检查，如果请求模式可获得允许进程就可以打开文件。系统调用open（）通常返回一个指向打开文件表中一个条目的指针。在多进程可能同时打开同一文件的环境中，进程执行调用open（），其结果只不过简单的在其进程打开表中增加一个

34、条目，并指向整个系统表的相关条目。同时，系统表内相关文件的文件打开计数器open count加1。Close（）操作操作close（）会使文件条目从进程打开表中删除。同时使系统表内相应文件的文件打开计数器open count减1，当打开计数器为0时，表示该文件不再被使用，该文件条目可从系统打开表中删除。文件访问方法：顺序访问直接访问其他访问（通过创建文件索引）目录结构单层目录结构优点：所有文件都包含在同一目录下，便于理解和支持。缺点：在文件类型增加或系统有多个(du )用户时，单层目录结构受到限制。双层目录(ml)结构分两层，主文件目录（MFD）和用户(yngh)文件目录（UFD）。当一个用户

35、作业开始执行或一个用户注册时，就搜索系统的主文件目录，通过用户名或账号可索引MFD，每个条目都指向用户的UFD。优点：解决了名称冲突问题。缺点：这种结构有效地对用户进行了隔离，这种隔离在用户需要完全独立时是优点，但是用户需要在某个任务上进行合作和访问其他文件时却是个缺点。树状目录结构是双层目录结构的推广，其层数为任意高度。它允许用户创建自己的子目录，相应的组织文件。优点：允许用户定义自己的子目录结构，可以使其能按一定结构组织文件；用户除了可以访问自己的文件还能访问其他用户的文件。缺点：禁止共享文件和目录。（绝对路径名：从根开始并给出路径上的目录名直到所指定的文件。相对路径名：从当前目录开始定义

36、路径。）无环图目录结构无环图目录允许目录含着子目录和文件。同一文件或子目录可出现在两个不同目录中。无环图是树形结构目录方案的自然扩展。优点：可共享文件，比树形图灵活，允许重名，允许共享。缺点：可能出现可变的并可能很大的文件引用表。通用图目录结构访问控制列表ACL（保护）每个文件盒目录都有一个ACL，以给定每个用户名及其所允许的访问类型。当一个用户请求访问一个特定文件时，操作系统检查ACL，判断能否访问。文件系统结构：设备I/O控制基本文件系统文件组织系统逻辑文件系统应用程序（从低到高排列）文件控制块FCB（类似于PCB）目录实现线性列表：编程简单，运行费时哈希表：搜索时间短，大小固定为文件分配

37、磁盘空间的方法连续分配（每个文件在磁盘上占有一组连续的块）文件目录中存放起始盘块号和块数优点：访问容易，速度快，不需要额外空间，能随机存放缺点：分配算法复杂，产生外部碎片，必须事先知道文件长度（连续分配支持顺序访问和直接访问）链接分配每个文件由磁盘块链表组成，每一个盘块含有下一个盘块的指针，文件目录中包含指向第一盘块和最后一个盘块的指针。优点：实现离散分配，无外部碎片，文件大小可变缺点：只能顺序访问，指针占空间，链断致命，会产生内部碎片。改进措施：1.按簇分配（多个块组成簇）容易产生内部碎片，使指针占用的空间变小 2.链接信息专门存放，文件分配表FAT.每个卷的开始部分用于存储该FAT，每块都

38、在该表下有一项，该表可以通过块号码来索引。目录条目包含首块号码，根据块号码索引的FAT条目包含文件下一块的块号码。优点：改善随机(su j)访问时间缺点：有大量磁头(ctu)寻道时间索引(suyn)分配每个文件都有其索引块，索引块包含文件所有块的指标，索引块的第i个条目指向文件的第i块，文件目录条目包含其索引块地址。优点：支持直接访问，无外部碎片缺点：浪费空间，索引块大小问题，索引块指针开销通常比链接分配指针开销大管理大文件的改进措施：链接。2.多层索引。3.组合方案。空闲空间管理操作系统维护空闲空间链表来记录空闲磁盘空间位向量：将空闲空间实现为位图或位向量，每块用一位来表示。如果一块为空闲，

39、那么其位为1，如果已分配，那么其位为0.优点：容易找到连续块，查找磁盘上第一个空闲块和n个连续的空闲块时相对简单和高效。缺点：需要额外空间。链表：将所有空闲磁盘块用链表连接起来，链表的头部放在超级块中。缺点：此法的效率不高，要遍历整个表时，需要读入每一块，这需要大量的IO时间。组：将n个空闲块的地址存在第一个空闲块中，这些块前n-1个确实为空，最后一块包含另外n个空闲块地址。计数：为磁盘的每块连续存储空间建一个表。磁盘为现代计算机系统提供了大容量的外存。磁头和磁臂相连，磁臂能将所有磁头作为一个整体而一起移动。磁盘片的表面被逻辑地划分为圆形磁道。磁道再进一步划分为扇区。位于同一磁臂位置的磁道集合

40、形成了柱面。每个磁盘驱动器有数千个同心柱面，每个磁道可能包括数百个扇区。图示P388 图12.1移动磁头的磁盘装置定位时间（传输效率）=寻道时间+旋转等待时间传输速率：驱动器和计算机之间的数据传输速率磁盘调度寻道时间：磁臂将磁头移动到包含目标扇区的柱面的时间旋转延迟：磁盘需要将目标扇区转动到次磁头下的时间磁盘带宽：所传递的总的字节数除以从服务请求开始到最后传递结束时的总时间FCFS：先到先服务调度特点：算法本身较公平，但不提供最快的服务。例如：有一个磁盘队列，其I/O对各个柱面上块的请求顺序如下：98,183,37,122,14,65,67调度如下：图示P393图12.4FCFS磁盘调度SST

41、F（寻短寻道时间优先算法）在将磁头移到远处以处理其他请求之前，先处理靠近当前磁头位置的请求。特点：平均寻道时间最短，可能导致进程发生饥饿现象。例如：有一个磁盘(c pn)队列，其I/O对各个柱面上块的请求顺序(shnx)如下：98，183，37，122,14,124,65,67SCAN（电梯(dint)算法）磁臂从磁盘的一端向另一端移动，同时当磁头移过每个柱面时处理位于该柱面的服务请求。特点：如果一个请求刚好在磁头之前加入到队列，那么它几乎马上得到处理。如果一个请求刚好在磁头之后加入到队列，那么它必须等待磁头到达磁盘的另一端调转方向并返回，不会发生饥饿现象。C-SCAN 是SCAN的变种，主要

42、提供一个更为均匀的等待时间。与SCAN一样，C-SCAN将磁头从磁盘的一端移动到另一端，随着移动不断处理请求。不过，当磁头移动到另一端时，他会马上返回磁盘开始，返回时，并不处理请求。LOOK调度通常，磁头只移动到一个方向上最远的请求为止，接着，他马上回头，而不是继续走到磁盘的尽头，这种形式的SCAN和C-scan称为LOOK和C-LOOK。RAID结构磁盘冗余阵列（RAID）技术：指多种磁盘组织技术高可靠性高数据传输率（引入冗余的方法是复制每个磁盘，这种技术称为镜像）P405.图12.11RAID的级别RAID级别0：指按块级别分散的磁盘阵列,没有冗余RAID级别1:指磁盘镜像RAID级别2设

43、备驱动程序：为I/O子系统提供了统一设备访问接口控制器：用于操作端口，总线或设备的一组电子器件轮询：主机不断读取状态寄存器直到忙位被消除。中断：使外设通知CPU的硬件机制。DMA控制器（DMA直接内存访问）【无需CPU】I/O调度：当有多个应用程序请求I/O时，I/O调度重新安排队列顺序从而改善系统总体效率和应用程序的平均响应时间。I/O子系统改善计算机效率的方法：1.进行I/O操作调度；2.使用主存或磁盘上的存储空间的技术（如缓冲、高速缓存、假脱机）；缓冲区用来保存两个设备之间或在设备和应用程序之间所传输数据的内存区域。假脱机是用来保存设备输出的缓冲区，这些设备（如打印机）不能接受交叉的数据

44、流。I/O请求的生命周期一个进程对已打开文件的文件描述符阻塞read（）系统调用。2.内核系统调用代码检查参数是否正确。对于输入，如果数据已经在高速缓存中，那么就将该数据返回给进程并完成i/o请求。3.否则，就需要执行物理I/O请求。这时，该进程会从运行队列移到设备的等待队列上，并调度I/O请求。最后I/O子系统对设备驱动程序发出请求。根据操作系统的不同，该请求可能通过子程序调用或内核信息传递。4.设备驱动程序分配内核缓冲空间以接收数据，并调度I/O。最后，设备驱动程序通过写入设备控制器寄存器来对设备控制器发送命令。5.设备控制器控制设备硬件以执行数据传输。6.设备程序可以轮询检测状态和数据，或通过设置DMA将数据传入到内核内存。