OS基本内容总结.doc

l OS（Operating System）地位、作用和定义定义：操作系统是控制应用程序执行的程序，并充当应用程序和硬件间的接口。操作系统是最基本的系统软件。它控制计算机的所有资源，并提供应用程序开发的基础。作用：研究操作系统的几种观点：系统观点：作为资源管理器的操作系统操作系统的主要任务：满足资源使用请求；记录资源使用情况；协调各个程序和用户对资源使用请求的冲突。用户观点：作为扩展机的操作系统为用户提供一台等价的扩展机，或称为虚拟机，它比底层编程更容易编程。l OS分类和发展历史n 批处理、分时、实时、通用、多处理、网络（了解各自的特征和适用场合）无操作系统时代/第一代计算机：使用真空管和插件板；无任何软件和操作系统单道批处理系统/第二代计算机目标：减少机时的浪费单道批处理系统的问题：内存利用率低；CPU利用率低多道批处理系统/第三代计算机基地址寄存器和界限寄存器；多道程序设计多道批处理系统的问题：响应时间不确定；不同调度算法，不同结果分时系统每个用户拥有一个终端；n个用户同时申请任务，给每个用户1/n有效的处理器速度实时系统对处理器操作或者数据流动有严格的时间要求时使用。硬实时系统：保证关键实时任务按时开始或者按时完成软实时系统：关键实时任务的优先级高于其他任务的优先级，并在完成之前保证它的最高优先级l OS特征并发并行：两个事件在同一个时刻发生并发：两个事件在同一个时间间隔发生共享：互斥的共享方式；同时访问方式虚拟异步性：内存中程序何时执行、何时暂停、需要多少时间完成都是不可知的l OS功能处理器管理的功能；存储管理的功能；设备管理的功能；文件管理的功能；用户接口l 一些概念n 监控程序（monitor) 、多道程序系统、多处理系统n 引入多道程序设计的目的l 什么是双重操作模式为什么要引进双重操作模式n 系统态、用户态以及转换的条件n 特权指令和非特权指令l 用户与OS的两种接口：定义和功能命令接口：由一组键盘操作命令和命令解释程序组成；DOS程序接口：为了用户程序访问系统资源而设；用户程序获取操作系统服务的唯一途径；系统调用；Windows API图形用户接口(GUI)l 系统调用（System Call）：定义、功能用户对操作系统提出的服务是由系统调用来实现的，它提供了进程与操作系统之间的接口。l 操作系统的结构有几种各自的特点整体式结构操作系统是一系列过程的集合，只要需要就可以相互调用。层次式结构层次式系统的各种功能可以划分为几个层次，每个层次建立在下面的层次之上。优点：模块化缺点：对层的定义并且相对效率差C/S结构把原本属于操作系统内核的功能放到内核的外部，使内核成为一个微内核。操作系统的微内核之外的进程是服务器进程，用户进程是客户进程；微内核实现消息的传递优点：易于维护；易于扩充；适用于分布式系统虚拟机结构虚拟机监控器运行在硬件系统上，提供多道程序的功能，并为上一层提供虚拟机。虚拟机是硬件的完全拷贝，包括真实机器中的内核模式、用户模式、I/O、中断等。优点：提供了安全层；允许进行系统开发而不必中断正常的系统操作n 陷阱（trap）与中断（interrupt）的区别中断：由硬件引起的中断，例如时钟中断陷阱：是因为错误/用户程序的特定请求而引起的软件生成中断，又称软中断，例如系统调用l 进程(Process)n 定义、特征、作用定义：进程指一个正在执行的程序，包括程序计数器、寄存器和变量的当前值。n 程序顺序执行、并发执行的特点n 进程与程序的区别与联系进程不只是程序代码，还包括当前的活动以及堆栈段和数据段程序是被动的实体，进程是活动的实体n 进程状态（三状态和五状态）及其转换三状态：就绪状态；运行状态；等待状态五状态：新状态：进程正在被创建。就绪状态：只要有机会获得CPU就能够开始执行。 运行状态：进程正在执行。等待状态：等待某个事件发生。终止状态：进程已经完成或者被迫终止。n 进程控制块PCB（Process Control Block）：作用及其内容为了实现进程模型，操作系统维持着一张表格，从数据结构上看就是一个结构数组，也就是进程表。每个进程占用一个表项，就是每个进程的进程控制块。l 进程控制n 主要功能；创建、撤销、挂起、唤醒、阻塞、激活等原语所需完成的功能；了解fork ()和exec()的工作原理创建进程在执行过程中通过系统调用创建进程。如果一个进程创立了另一个进程，则前者称为父进程，后者称为子进程。一个进程只有一个父进程，但是可以有零个或多个子进程。因此，进程和进程之间会形成一个进程树。终止/撤销进程终止自己（自愿的）：使用exit系统调用；父进程使用wait系统调用得知终止进程的进程号父进程终止子进程（非自愿的）：使用abort系统调用，传入子进程ID号操作系统终止进程（非自愿的）：引用不存在的内存，除以零；级联终止：父进程终止，子进程只好终止，此操作由操作系统进行阻塞原因：请求系统服务；启动某种操作；新数据尚未到达；无新工作可做操作：进程通过调用阻塞原语block将自己阻塞，进入等待队列，进程的状态变成等待唤醒原因：被阻塞的进程等待的事件到来操作：相关进程调用唤醒原语wakeup将对方唤醒，被唤醒的进程进入就绪状态fork父子进程从fork之后分别执行。父进程执行fork后返回子进程ID。子进程执行fork后返回0。exec用新的程序代码代替父进程给定的代码。l 进程通信的几种方法n 消息队列、共享内存为了能让消息成功地发送，消息总是驻留在临时的队列中，称为消息队列零容量：发送必须阻塞直到接收者收到消息有限容量：如果队列不满，发送可以把消息放在队列中，不必等待；如果队列满，发送必须阻塞等待队列可用无限容量：发送从不阻塞l 进程同步与互斥n 概念：临界资源、临界区、信号量、同步、互斥、进程间的制约关系（直接、间接）Send和receive可以是阻塞的（称为同步），也可以是非阻塞的（称为异步）。阻塞 send, 阻塞 receive：发送者和接收者被阻塞直到完成消息交付；也称作会合/集合点无阻塞 send, 阻塞 receive：发送者连续处理，例如尽快地发送消息；接收者被阻塞直到所需的消息到达无阻塞send, 无阻塞receive：不要求任何一方等待l 互斥（mutual exclusion）问题如果有进程在临界区中执行，那么其他进程都不能在临界区中执行。这样就可以避免竞争条件的产生。有空让进；有限等待；不对进程的相对执行速度进行任何假设n 准则n 实现方法：硬件、信号量（软件方法不要求）硬件：屏蔽中断进入临界区之前关中断，离开之后开中断：现代操作系统是中断驱动的，没有了中断操作系统就失去了控制系统的能力；只有一个CPU的时候有效系统提供了特殊硬件指令允许原子地检查和修改字的内容或者交换两个字。原子操作：TestAndSet（TS指令）；Swap（XCHG指令）互斥锁：实现互斥的软件工具，也称自旋锁。底层用TestAndSet或Swap指令实现：acquire()release()l 信号量（Semaphore）n 定义、含义、操作（初始化，P,V）定义：信号量S就是一个整数变量；在S上可以执行两个原子操作：wait(S)signal(S)分类：计数信号量 Counting Semaphore：整数值可以是任何整数值；二元信号量 Binary Semaphore：取值只能是0或者1；与互斥锁类似l 进程同步与互斥问题n 生产者与消费者一或多个生产者产生数据并放在缓冲区中，每次一个；一或多个消费者从缓冲区取数据项并消费，每次一个条件：在任意时间只能一个生产者或消费者访问缓冲区互斥；保证生产者不能向满缓冲区中放产品；保证消费者不能从空缓冲区中取产品semaphore n=0;semaphore s=1;semaphore e=N;void producer()while(true)a=produce();wait(e);wait(s);put(a);signal(s);signal(n);void consumer()while(true)wait(n);wait(s);a=take();signal(s);signal(e);consume(a);用管程实现:l 死锁n 掌握解决死锁的方法：预防、避免、检测n 掌握银行家算法：如何判别安全性定义：两个或多个进程无限地等待一个事件，而这个事件只能由这些等待进程之一来产生/如果一个进程集合中每一个进程都在等待只能由本集合中的另一个进程才能引发的事件，则称这种状态为死锁。 产生原因：使用排他的资源资源分成两种类，可剥夺式资源：可以从拥有资源的进程中剥夺资源而不会产生副作用；非剥夺式资源：若从拥有这类资源的进程处剥夺资源会导致失败使用一个资源的顺序是：申请资源->使用资源->释放资源进程在申请资源时，如果失败，则进程阻塞。必要条件：互斥：一个资源同时只让一个进程使用拥有并等待：进程在拥有一个资源时又申请另一个资源，并等待分配给它。资源不可抢占：分配给一个进程的资源是不可抢占的，只能由占有它的进程释放环路等待：进程和资源之间存在一个拥有和需求的闭环忽略该问题；死锁检测并恢复；仔细检查动态资源分配来避免死锁；破除四个条件之一，用来预防死锁的产生预防：预先在系统实现时就把死锁排除直接预防：预防第四个产生死锁条件的方法间接预防：预防前三个产生死锁的条件的方法预防拥有并等待：让进程一次将所有的资源需求提出；操作系统要么一次性将所有的资源分配给进程，要么阻塞进程执行缺点：进程可能正等待所有需求被满足，而实际上只需要一部分资源就能执行下去；进程在执行时拥有所有资源，导致一些资源长期占用不使用，而其他进程也不能使用这些资源；在多模块或多线程应用中，一次提出所有资源的需求会有困难。预防不可剥夺资源：只在资源的状态很容易恢复时才可以使用，对于像打印机这样的资源则不好使用预防环路等待：定义一个资源类型的线性顺序来解决这个问题。如果一个进程已经分配了R类型的资源，则只能再申请R类型以后的类型的资源。问题在于这种线性顺序很难确定。 避免：中心思想：允许前三个条件的发生，但不允许最后一种机制来防止到达死锁的状态。死锁的避免要求欲知将来进程的需求。银行家算法：这种算法与早期的银行贷款的方法相似。银行中只有固定数目的资金可以借贷给顾客。银行如果认为不能有足够的资金贷给顾客以满足顾客的所有要求，而使顾客可以全部偿还的话，就拒绝给这个顾客贷款。状态：系统中分配给进程的资源的状况，由Resource、Available向量和Max、Allocation、Need矩阵组成。安全状态指至少有一个进程执行顺序会让所有进程安全地执行完而不会导致死锁的状态，非安全状态与安全状态相反。死锁避免策略：保证进程和资源总是处于安全状态。如果一个进程要求的资源在分配给它以后，系统仍处于安全状态，则分配给它。否则阻塞这个进程直到可以达到安全为止。银行家算法分析：要求事先提出进程对资源的所有需求（无法提出）；进程的个数是确定的（进程个数会变化）；资源的个数也是确定的（资源可能会失败）检测：中心思想：死锁的检测方法并不限制对资源的访问；进程可以在可能的情况下获得它所需要的资源，只是检测死锁是否存在；如果存在，则想办法恢复对于死锁的检测可以在以下两种情况下执行：在每次进行资源分配后进行；定期检测死锁死锁检测算法：使用Allocation矩阵和Available向量；需求矩阵request，定义qij代表进程 i 对资源 j 的请求数目；这个算法通过标记没有死锁的进程来执行；初始时，所有进程都没有标记。算法步骤：（1）只要在Allocation矩阵中一行的值都是0，标记此进程。（2）初始化一个临时向量w，另Available->w。（3）找一个索引i，保证进程Pi没有被标记，且对于1<=k<=m，有Requestik<wk。如果没有这样的Pi，算法结束。（4）如果找到Pi，则标记i，并执行w=w+Ai，转去执行（3）l 调度的几种类型n 长程调度、中程调度、进程调度调度程序用于选择进程。长期调度/作业调度：负责从进程池中选择进程进入内存/从存储设备的缓冲池中选进程进入内存执行；执行频率低（几分钟一次）；可控制多道程序设计的程度，对I/O为主的进程和CPU为主的进程组合以保证CPU和外设的有效使用中期调度：从换出到外存挂起的进程中选择进程进入内存/将进程换入换出（交换）以降低多道程序设计的程度短期调度/CPU调度：从就绪队列中选择进程进入CPU执行；执行频率高（100ms至少一次）l 调度队列就绪队列；设备队列：等待I/O设备的进程队列；排队的信息在PCB中保存l 可剥夺调度和不可剥夺调度/抢占式调度和非抢占式调度：定义和特点抢占式调度：可以将进程暂时终止执行的策略。非抢占式调度：一旦一个进程进入运行状态，它会一直执行，直到它阻塞、进行系统调用或执行完。抢占式调度的系统开销要大于非抢占式调度。但是抢占式调度对于整个系统的进程服务要好，因为它可以防止独占处理器。l 调度算法的性能评价准则批处理系统：周转时间（进程的结束执行的时间与进程到达系统的时间的差值）很重要，越接近进程实际执行的时间，调度的效率就越高。分时系统：响应时间短很重要l 调度程序（Scheduler）的功能、时机；在系统中，当有多个进程处于就绪状态时，操作系统必须决定先运行哪一个进程。在操作系统中，决定选择哪个就绪进程去CPU运行的部分称为调度程序；它所使用的算法称为调度算法。发生时机：进程从running到waiting；进程从running到ready；进程终止；进程从waiting到readyl 调度算法：n FCFS 、SJF、RR、优先级、多级队列、多级反馈队列、HRRN优点和缺点、适用场合n 要求会计算：调度顺序、周转时间、平均周转时间FCFS调度算法：非抢占式调度；选择就绪队列中等待最长时间的进程评价：FCFS算法对长进程有优势；FCFS算法更利于多处理器处理的进程，而不利于多I/O处理的进程。SJF（最短作业优先）算法：可以是非抢占式调度，也可以是抢占式调度；选择下一个期望最短处理时间的进程执行。缺点：需要知道或者估计出进程会执行多长时间；可能使长进程产生饥饿；因为没有剥夺，所以不适合在实时系统中实现。HRRN（高响应比优先）算法：响应比=(A+B)/BA：等待处理器的时间B：期望服务的时间非抢占式算法；调度响应比高的进程；优点在于考虑到等待处理器的时间；需估计进程的执行时间RR（时间片轮转）算法：抢占式调度算法；时钟每隔一段时间产生一个中断；运行状态的进程进入就绪状态；用FCFS方法从就绪队列中选择一个进程去执行时间片长短的讨论：太短，开销大；太长，变成FCFS优先权算法：非抢占式调度算法；调度优先级最高的进程；防止高优先级的进程总占用处理器：动态优先级多级队列调度：将优先级调度和时间片轮转算法相结合：将进程按优先级分为若干类；各个类之间用优先级调度；同一优先级之间用时间片轮转调度多级反馈队列调度：可抢占式算法方法：有多个队列优先级从高到低；进程刚进入系统，进入RQ0；执行完一个时间片，进入RQ1；.；只有最低优先级的队列是按RR方法调度缺点：长进程可能会产生饥饿优化：为防止长进程饥饿，根据队列的优先级的高低来分配时间片的长度，RQi队列的进程的时间片长度是2i。仍然可能导致长进程产生饥饿，补救方法：当一个进程在当前队列中等待服务的时间达到一定的长度后，就进入高一级的队列中去。l 什么是线程为什么要引进线程线程又称为轻量级进程（LWP），是进程内的一条运行线；是使用CPU的基本单元；由线程ID、程序计数器、寄存器集合和堆栈组成；属于同一进程的线程共享进程的代码段、数据段和其他操作系统资源。响应度高：一个进程中一个线程的阻塞不会导致整个进程的阻塞资源共享：同属一个进程的多个线程共享这个进程的所有资源通信简单经济：创建进程所需内存和资源分配比较昂贵，但创建线程相对好些；线程切换比进程切换所需资源少多处理器体系结构的利用：可以利用多个CPU执行多个线程实现并行处理l 线程和进程的区别进程的特点：进程是资源的拥有者；进程是调度的单位线程的特点：线程是调度的单位；进程是资源的拥有者l 线程的实现方式n 用户级线程和内核级线程l 存储器管理程序的功能l 逻辑地址、物理地址、地址重定位、地址映射的概念CPU生成的地址是逻辑地址，程序生成的逻辑地址的集合是逻辑地址空间内存单元的地址是物理地址，所有物理地址的集合是物理地址空间逻辑地址向物理地址的转换过程就是重定位l 连续内存分配（固定分区、可变分区）：n 原理、数据结构、地址变换、特点n First-Fit,Best-Fit,Worst-Fit固定分区：把存储器分为大小相等的区。所需空间小于等于分区大小的进程可以调入可用分区。进程换入换出：所有的分区都是满的；没有进程处于就绪状态或运行状态特点优点：简单缺点：程序可能太大而不能放入一个分区：程序员要设计一种覆盖的方法；主存的应用效率低：小程序也要占用整个分区；限制了系统中可以激活的进程数目因调入的数据小于分区而产生分区空间的浪费，称为内部碎片。用不等长的分区来缓解，但不能根本解决。放置算法等长分区：主存中只要有可用的分区，进程就可以调入到那个分区中；如果所有的分区都被不能执行的进程占用，则其中的一个进程会被换出以放入新进程不等长分区：将进程放置在它最适合的最小的分区中；将所有进程排在一个队列中，当该调入一个进程进入主存中时，就选择可用的且可以保存这个进程的分区可变分区：系统中分区的长度和数目是可变的。当有进程进入系统时，从主存按一定策略划出一块与进程所需空间相等的区分配给进程。特点缺点：一开始运行得很好，但是在执行一段时间后，会出现一些小的洞，这种在分区外的洞称为外部碎片。需要用内存紧缩（紧凑）方法解决。分配多大的内存给进程简单方法：按照需求的大小进行分配。这样如果程序有可以动态增长的段，就有问题。解决方法是为进程分配一些额外的内存。内存管理方法：位图将内存按一定大小划分成分配单位，每个分配单位对应位图中的一位；用0表示空闲，1表示使用（或者反过来）；在内存大小确定的情况下，分配单位的大小决定了位图的大小。内存管理方法：链表维护一个已分配和空闲内存段的链表。每一个表项都有：P或H表示是进程还是空闲区域、起始地址、段长度和指向下一个表项的指针。l 页式管理n 原理、数据结构、地址、地址映射过程、特点n 碎片（内碎片，外碎片），怎么产生，如何解决n 紧缩把主存分为定长的块，称为页框（帧）；把用户进程也分为与主存的块大小相等的块，称为页；内部碎片只在进程的最后一页中发生，没有外部碎片；为页和页框分别编号，从0开始。优点：碎片小，节省存储器空间；分页对程序员是透明的缺点：共享和保护不容易实现；程序员不能按照自己的方式组织程序地址映射过程：分页地址变换机构自动将逻辑地址分为页号和页内地址位移以页号为索引去查询页表，得到页框号页框号与页内地址位移相结合，获得物理地址l 段（segment）式内存管理n 原理、数据结构、地址组成、地址变换、特点原理：让存储器提供多个相互独立的空间，称为段；每个段由0到最大的线性地址构成；不同的段的长度不同，段的长度可以在运行期间改变。优点：共享和保护容易实现；程序员可以按照自己的方式组织程序缺点：有碎片，浪费存储器空间l 段页式内存管理n 原理、数据结构、地址组成、地址变换、特点段页式管理是将用户的地址空间分段，段内按内存页框的大小分页。逻辑地址由段号、段内页号和页内位移三部分组成。操作系统在进行管理时，为每个进程维护一个段表和多个页表。页表的结构与页式管理中的页表一样，段表中包含的是页表的起始地址和页表的长度及其它控制位。l 覆盖与交换：原理、特点、比较覆盖：在任何时候只能在内存中保留所需要的指令和数据，新的指令和数据可覆盖不用的指令和数据；不需要操作系统提供特别支持例子：two-pass汇编程序交换：在内存不足的情况下，需要把一个进程整个换入和换出，称为交换交换空间的分配：进程在被换出时分配交换空间，每次换到不同的位置；进程分配固定的交换空间l 虚拟存储器n 概念、原理、实现方法、理论基础（局部性原理）n 虚拟存储器的特征概念：虚拟存储器就是指仅把作业的一部分装入内存就可以运行作业的存储系统。它具有请求调入功能和置换功能，是从逻辑上对内存容量进行扩充的一种存储系统。CPU生成的地址是虚拟地址；内存单元的地址是物理地址；程序生成的虚拟地址的集合是虚拟地址空间；所有物理地址的集合是物理地址空间局部性原理：程序在执行时，除了少部分的转移和过程调用外，大多数情况下仍是顺序执行的。过程调用会使程序的执行轨迹从一部分内存区域转至另一部分，但调用深度不会超过5。即程序会在一段时间内局限在这些过程的范围之内运行。程序中存在循环，由少数指令构成，但多次执行。对数据结构的处理都局限于很小的范围内。l 请求页式管理一个进程调入内存时只调入部分页；当需要的页面不在内存时，请求调入所需的页面；如果内存不足，可以把内存中的某个页面换出到外部辅存中n 基本原理n 什么是缺页中断、发生时机及处理过程n 置换策略（OPT、FIFO、LRU）：计算缺页次数、缺页中断率、判别是否有Belady异常n 逻辑地址到物理地址转换l 存储的共享与保护方法l 什么是TLB其作用描述带有TLB的地址转换过程相联存储器页表保存在内存中，每次要存取数据要两次访问内存：访问内存中的页表，找页框号，形成物理地址；从第一次访问得到的物理地址中得到所需的数据为了增加地址变换速度，可以在地址变换机构中，增加一个具有并行查询功能的特殊高速缓冲存储器，称之为相联存储器。在IBM中又被命名为TLB（Translation Lookaside Buffer翻译后备缓冲），用来存放当前被访问的那些页表的表项。l 什么是Belady异常哪一种算法会产生为什么缺页率随页框分配数量的增加而增加先进先出置换算法替代的页可能会很快使用l 请求段式管理的原理一个进程调入内存时只调入部分段：当需要的段不在内存时，请求调入所需的段；如果内存不足，可以把内存中的某个或者某几个段换出到外部辅存中l 虚拟段页式n 原理n 地址转换l 什么是颠簸（抖动）为什么会出现当系统多道程度达到一定高度时再增加进程的数目，反而会使缺页率增加，系统的性能下降CPU的时间都在进行页面的调入/调出，几乎不能完成任何有效操作，称系统颠簸或抖动。l 文件、目录、目录项、记录、域、文件管理系统、路径、当前路径文件：记录在外存上的具有名字的相关信息/记录的集合域：是数据的基本单位。有自己的长度和数据类型。在不同的文件系统中，域可以是定长的，也可以是变长的。记录：是相关域的集合。记录也可以是定长的，也可以是变长的。文件是一个单独的实体，也可以创建和删除。对于访问的控制和限制通常是文件级的。l 文件系统的功能和目的系统要求对数据进行长期的存储：可以存储大量信息；在使用信息时，信息要存在；必须能使多个进程并发存取有关信息解决的方法是采用文件的形式来管理信息。主要包括对文件的操作，如何分配存储空间，及相应的保护机制。l 文件的组织（逻辑）结构：类型、特点逻辑结构：有结构文件（记录式文件）：顺序文件；索引文件；索引顺序文件无结构文件（流式文件）：流式文件，利用读写指针来指出下一个将要访问的位置顺序文件：每个记录有固定的格式记录是等长的；所有记录的域都相同（顺序和长度）；域名和长度都是文件的属性；有一个域是关键域：用于唯一确定一个记录；记录按照关键字的顺序存储；新记录被放在一个日志文件或者事务文件中；使用批修改来将日志文件和主文件合并索引顺序文件：在顺序文件中引入索引索引提供了一种快速接近目标记录的查找能力；包含一个关键字域和一个指向主文件的指针；查找等于或者小于期望关键字值的最大的索引索引文件：为不同的关键字域使用多重索引；可以包含一个穷举索引为主文件的每一个记录建立一个项目；可以包含一个局部索引l 文件的存取方法文件存取类型有顺序存取、随机存取。顺序存取：指用户只能从开始的地方顺序读文件的所有记录，不能跳过一些内容。主要用于磁带设备。随机存取/直接访问/相对访问：指可以按任何次序读取记录。如按照关键字。主要用于磁盘设备。l 文件存取控制矩阵与文件存取控制表l 文件系统的层次结构l 文件分配方法即文件在物理存储器上的结构连续分配；链表分配；带索引的链表分配：索引节点（i节点）n 三种方法：原理、优缺点n 多级索引分配连续分配：文件作为连续数据块存储在磁盘上：记录文件的开始盘块和文件的长度缺点：有外部碎片；文件大小必须在文件创立时提出链表分配：分配以块为基础：每块有指向链中下一块的指针；记录开始块和结束块；是一种动态分配策略；没有外部碎片，适合于顺序文件的顺序处理缺点：数据分散，读文件时不能保证一次读的都是有用的块带索引的链表分配：每个文件建立索引；保存文件各磁盘块的顺序n Unix的索引节点（index node）/i节点的定义一些系统采用索引节点的方法，把文件的描述信息单独形成一个称为索引节点的数据结构，简称为i节点。文件目录中的每个目录项中只有文件名和指向该文件i节点的指针。节省了平均启动磁盘的次数，提高了效率。l 磁盘存储空间管理方法n 位图、空闲块链接、空闲目录、成组块链接法n 难点：多级索引分配、成组块链接法位图/位向量使用一个位表示磁盘块的分配状态。0表示没有分配，1表示已经分配。优点是位示图很小，可以放在主存中。这样不用每次分配时都从磁盘中读数据。链表：可以把空闲块用指针链接，系统只需掌握首指针和链表长度空闲区链：把多个连续的空闲块组成空闲区；可以把空闲区用指针链接；系统只需掌握首指针和链表长度l 什么是缓冲为什么要引入缓冲原因：缓和CPU和I/O设备之间速度不匹配的矛盾；减少对CPU的中断频率，放宽对中断响应时间的限制；提高CPU和I/O设备之间的并行性特点：预输入缓输出分类：面向块的缓冲和面向流的缓冲；单缓冲、双缓冲和循环缓冲面向块的缓冲：信息被存储在固定大小的块中；一次传送一块；用于磁盘和磁带面向流的缓冲：以字节流的方式传送信息；用于终端、打印机、通信端口、鼠标和大多数其它非二级存储器的设备单缓冲：操作系统在内存中为一个I/O请求分配一个缓冲区双缓冲：使用两个系统缓冲区而不是一个；进程可以在操作系统清空或者填满一个缓冲区时与另一个缓冲区传送数据循环缓冲：使用两个以上的缓冲区；在循环缓冲中每个单独的缓冲区都是一个单元；当I/O操作能够跟得上进程执行时使用l 区分独占设备、共享设备、虚拟设备n 理解对共享设备可同时使用的含义；n 简述实现虚拟设备的基本条件，虚拟设备的实现原理n 解释假脱机操作Spooling(Simutaneous Peripheral Operations On-Line)系统及其组成；输入井和输出井的位置及作用SPOOLing技术：将一台独占设备变为多用户共享的技术：在多道系统中；用一道程序来模拟脱机输入；把低速的I/O设备上的数据传送到高速磁盘上；用一道程序模拟脱机输出；把数据从高速磁盘传送到低速I/O上。这样在主机的控制下实现了脱机的输入/输出操作。脱机操作是模拟的，所以称之为假脱机操作。SPOOLing系统的组成：输入井和输出井：磁盘上开辟的两个大区；输入缓冲和输出缓冲：是内存中开辟的两个大区；输入进程SPi和输出进程SPO：用于模拟输入外围机和输出外围机l 设备独立性的含义应用程序独立于具体使用的物理设备。l 设备分配方法l 磁盘组织结构n 磁道、扇区、柱面n 一次磁盘存取操作的时间组成软盘：磁道；扇区硬盘：柱面；磁道；扇区磁盘访问时间：寻道时间Ts：用于把磁头放到指定磁道的时间；Ts=m×n+S（m是一个与磁盘驱动器的速度有关的常数）旋转延迟Tr：磁头到达扇区开始位置的时间；根据磁盘转速(r/min)计算每转用时得到平均转动延迟传送时间Tt：实际传送数据的时间；Tt=B/(RN)（B:每次读/写的字节数;R:旋转速度;N:每条磁道上的字节数）l 磁盘调度算法n 访问顺序，移动距离FCFS调度：进程顺序提出请求，对所有进程都是公平的；如果进程过多在性能上与随机调度区别不大SSTF（短服务时间优先）调度：选择磁臂从当前位置移动距离最短的I/O请求来满足；选择最短的寻道时间，如果两个方向上距离相等，采取随机的策略选择一个满足SCAN调度：磁臂向一个方向移动；在途中满足所有没有满足的请求，直到到达这个方向的最后一个磁道为止；倒转服务方向；又称电梯算法C-SCAN调度：严格限制扫描只能向一个方向；当已经到达一个方向的最后一个磁道，磁臂直接回到开始位置重新开始扫描LOOK/C-LOOK调度：磁头只移动到一个方向上最远的请求为止SCAN->LOOK；C-SCAN->C-LOOK