2014年考研计算机基础班讲义：操作系统
操作系统
【考查目标】
1． 了解操作系统在计算机系统中的作用、地位、发展和特点。
2． 理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。
3． 能够运用所学的操作系统原理、方法与技术分析问题和解决问题。
一 操作系统概述
大纲要求：
1．操作系统的概念、特征、功能和提供的服务。
重点在于操作系统的基本概念（什么是操作系统）、基本类型（主要三类）、基本特征（四点）和基本的服务功能（五大功能）。
2．操作系统的发展与分类。
操作系统的历史，从简单到复杂、从个人机到大型机。从不同角度对操作系统的分类。
3． 操作系统的运行环境。
目前操作系统的应用情况，使用对象以及三大主要运行环境。
知识点：
本章复习要点：操作系统概述基本上不会出现大型考题，一般是以基本原理和概念的形式为主，属于识记形式的题目。其中重点是“什么是操作系统?”、“操作系统有什么作用”、“操作系统的特征”及“操作系统的主要功能”等题目。在这里面的重中之重，就是操作系统的四大特征和五大功能，特别地需要对操作系统的四大特征及其之间的关系；操作系统的五大功能及各个功能的基本内涵等有较为深入的理解。
二 进程管理
大纲要求：
1．进程与线程
进程概念：程序的动态运行过程，包含了更多的内涵（数据、代码、PCB以及堆、栈等）。
进程的状态与转换：三种基本状态和四种主要转换。
进程控制：进程的创建、撤销、激活、挂起等操作。
进程组织：PCB的数据结构，就绪队列的排列，多个阻塞队列的组织。
进程通信：共享存储系统；消息传递系统；管道通信。
线程概念与多线程模型：线程的概念，线程的运用，线程的分类，线程的数据结构等。
2．处理机调度
调度的基本概念：为什么要调度，调度的实质，算法以及分派程序等。
调度时机、切换与过程：调度何时激活，如何调度，上下文切换的概念和执行过程等。
调度的基本准则：公平性，各部件使用的均衡性，优先策略运用是其基本点；对不同类型的调度有不同的调度准则。大型机的批处理系统以周转时间、吞吐量和处理机利用率为指标；交互式系统以响应时间和符合用户的习惯为准则；实时系统就以截止时间和保证周期性任务为准则。
调度方式：分为作业调度（宏观调度），内外存交换调度（中级调度），进程线程调度（微观调度）。
典型调度算法：先来先服务调度算法；短进程、短线程优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。
3． 进程同步
进程同步的基本概念：竞争与合作形成了同步与互斥的基本关系。
实现临界区互斥的基本方法：同步的四个基本准则。
软件实现方法：标志法，彼德森算法。
硬件实现方法：TS，SWAP方法。
信号量：PV原语的含义，自我阻塞，阻塞队列，唤醒操作；互斥信号量，资源信号量等。
管程：管程的概念，封装；管程的实现方法和管程的使用。
经典同步问题：生产者－消费者问题；读者－写者问题；哲学家进餐问题。
4． 死锁
死锁的概念：死锁的定义，以及与饥饿的区别。死锁产生的原因，死锁产生的四个必要条件。
死锁处理策略：死锁处理的四种办法。
死锁预防：死锁预防，打破死锁的四个必要条件。
死锁避免：系统安全状态；银行家算法。
死锁检测和解除：死锁的检测方法有资源有向图法、资源矩阵法；死锁的解除有剥夺资源法、进程回退法、撤销进程法和重启系统法四种方法。
知识点：
进程和线程的控制和调度（由于进程是资源分配的基本单位，所以一般都以进程作为讨论对象，只有在处理机调度时，需要以线程作为讨论对象；在没有线程的操作系统中，调度的对象就以进程为主），以及有关并发进程以及进程通信和死锁的问题是本章重点。
进程定义为一个具有独立功能的程序对某个数据集的一次动态处理过程和对资源的动态使用过程。进程是操作系统进行资源分配和调度的基本单位（关于这一点，我们必须指出，对于早期的操作系统，由于没有引入线程概念，这样的说法是正确的；但是，现代的、通用的操作系统均已经引入了线程概念，此时，进程仅仅作为资源分配的基本单位，而调度的基本单位就让位于线程。我们将在本章中仔细讨论有关进程和线程的相关问题，请同学予以重视）。进程和程序的区别在于：进程是动态的，程序是静态的；进程是暂时的，程序是永久的；进程由指令代码，数据和进程控制块组成，程序只有指令代码和数据，甚至最小的程序只有代码；一个内核进程通过系统调用可以被多个不同的程序所使用，而同一个程序通过多次创建可以对于不同的进程。
如上所述，进程在大多数系统中是进行资源分配和调度的基本单位，这样的系统由一组进程的集合所组成。操作系统进程运行系统代码，用户进程运行用户代码，所有进程可以并发运行。为了减少进程并发运行时进程切换所付出的时空开销，使操作系统具有更好的并发性能，在操作系统中，再引入线程。
线程是进程中的一个实体，是被处理机独立调度和分派的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源，如线程状态、寄存器上下文和线程栈等，主要存放在线程控制块里。每一个进程至少有一个主线程（例如对应main（void），它可与同属一个进程的其他线程共享进程所拥有的全部资源。
操作系统除了进行进程和线程管理外，还处理以下活动：用户进程与系统进程的创建与删除，处理机调度，提供并发进程之间的同步机制，进行进程间的通信以及进程死锁问题的处理。现代操作系统随着多道程序设计技术的出现，继续使用程序的概念来描述多道程序并发运行的动态特点是不合适的，为了认识操作系统动态活动的内在本质，从而引入了进程和线程的概念。
进程管理是考试的热门。也是操作系统知识的重要内容。本章出题的灵活性比较大，重点是要掌握进程的基本特征和状态转换及转换的原因和事件，线程与进程的比较和线程两种实现方式的比较，进程通信的基本类型；要掌握各种算法及其适用环境，并要会用算法来进行计算。死锁一节相对比较确定，重点掌握死锁的定义、产生死锁的原因、形成死锁的四个充分必要条件；熟练掌握死锁的预防、死锁的避免和死锁的检测算法，注意死锁与饥饿的区别与联系，了解处理死锁问题时避免饥饿的方法。
1．进程与线程。
进程的基本状态及其状态转换的原因和事件是需要重点认知的知识点，进程可以有多种状态，例如Windows有七种状态，UNIX系统有九大状态。但是，进程的基本状态主要是三种，包括运行状态（也叫运行状态）、阻塞状态（或称等待状态、睡眠状态）和就绪状态（或称准备状态）。
进程在运行期间，可以多次处于就绪状态和运行状态，也可多次处于阻塞状态。当就绪队列允许接纳新进程时，系统（批处理系统中是作业调度）便把程序创建为进程并移入就绪队列。而进程调度程序按照规定的算法选择某个处于就绪状态的进程分配处理机后，该进程进入运行状态。正在运行的进程因需要等待某事件（使用设备或获取数据等）而无法运行，就会出让处理机。当进程所等待的事件发生了（设备空闲或数据到达了），进程就从阻塞状态进入就绪状态。在采用时间片轮转算法的交互式系统中，当正在运行的进程因分配给它的时间片用完而被暂停运行；或者在采用可抢先式调度算法的系统中，一个高优先级的进程到来后，正在运行的低优先级的进程被强制剥夺了处理机，则该进程转换为就绪状态。当一个进程己完成或发生某种特殊事件时，进程将终止退出。
线程的引入，线程的特征，线程与进程的比较和线程两种实现方式的比较。引入线程是为了减少程序并发运行时所付出的时空开销，使操作系统具有更好的并发性能，当然还有其它硬件发展的一些原因。
在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中（现代操作系统均会引入线程），则把线程作为调度和分派的基本单位，而把进程作为资源分配的基本单位。由此，不仅进程之间可以并发运行，而且在一个进程中的多个线程之间，也可并发运行。线程自己不直接拥有系统资源，但它可以访问其所在进程的资源，一个进程所拥有的资源可供它的所有线程共享。
在进程切换时，涉及整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置、裸机地址空间的切换，I/O设备的切换，文件的切换等；而线程切换，只需保存和设置少量CPU相关寄存器的内容，它并不涉及存储器、I/O、文件管理等方面的操作。此外，由于同一进程中的多个线程具有相同的地址空间，这使它们之间的同步和通信变得比较容易（例如全局变量）。线程的切换、同步和通信可以无须操作系统内核的干预（涉及内核切换的除外）。但是进程间通信需要进程同步和互斥手段的辅助，以保证数据一致性，而线程间，可以直接读写进程数据段来进行通信。
2．处理机调度。
关于调度算法问题，需要对各种算法的引入原因以及各自的优缺点重点认知。各个适应什么情形。先来先服务（FCFS）根据就绪队列进程进入的先后次序来分配处理机，这是一种无条件不可抢占、非抢先的调度方式。一旦一个进程占有处理机，就一直运行下去，直到该进程完成其工作，这种算法非常公平，但是会使很多晚到的、运行时间短的作业等待时间过长，会加大作业周转时间，影响短作业用户的使用。
短作业优先（SJF）或短进程优先（SPF）算法是指选择作业队列或就绪队列中预计运行时间最短的作业或进程创建进入内存或调度进入处理机运行，它能有效地缩短作业的周转时间和平均周转时间，当短作业或短进程较多时会显著提高系统的吞吐量，但不利于长作业（长进程）和紧迫作业的运行。当短作业或短进程源源不断时，长作业或长进程会产生饥饿。由于在采用时间片轮转的调度算法中，进程运行的时间片是断断续续的，考虑到阻塞等因素，进程的长短难以预计，因此，在交互式系统中不可能存在短进程优先的调度算法。
高响应比优先调度（HRRN）算法主要应用于作业调度，它能为每个作业引入前面所述的动态优先级，并使作业的优先级随着等待时间的增加而以速率V提高，则长作业在等待一定的时间后，也必然有机会分配到处理机。它是先来先服务算法与短作业（短进程）优先算法的折中。公平而高效。
最高优先级优先调度算法是一种最常用的进程调度算法，它把处理机分配给优先级最高的进程。而优先级可以通过不同的优先级设置机制而赋予。
时间片轮转调度算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列。进程调度程序总是选择队列中第一个进程运行，并分配其运行一个时间片（也叫时间配额）。在使用完一个时间片后，即使进程并未完成其运行，也必须将处理机交给下一个进程。因此，它是绝对可抢先的调度算法。
多级反馈队列调度算法中，则采用更为灵活的调度算法。设置多个就绪队列，并为每个队列赋予不同的优先级。赋予各个队列中进程运行时间片的大小也各不相同。当一个新进程进入内存后，若为了能获得较高的响应时间，则会首先将它放入最高优先级队列的末尾，按先来先服务的原则排队等待该队列的调度。当轮到该进程运行时，如能在一个时间片内完成，则运行完了可以撤离系统。如果它在一个时间片结束时尚未完成，调度程序会使将该进程优先级降低，转入次高优先级队列的末尾，再同样地按先来先服务原则等待调度运行。
3．进程同步。
进程间的信息交换称为进程间的通信。进程之间的互斥与同步就是最常见的两种进程间的通信方式。由于进程互斥与同步交换的信息量较少，通信传递的方式直接，通信量固定，通信的效率较低，因此一般称这两种通信方式为低级通信方式。与之相应的P/V原语操作称为低级通信原语。而高级通信方式是指进程之间以较高的效率传送较大量数据的通信方式。高级通信方式可分为三大类，分为共享内存、消息传递以及管道通信。
如何用信号量机制和相应的管程机制解决进程同步问题，用信号量来实现互斥和实现同步关系。作为平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决共有资源的使用问题。那么操作系统可从进程管理者的角度来处理互斥与同步的问题，信号量就是操作系统提供的管理公有资源的有效手段。
4．死锁。
死锁问题中需要对死锁的基本概念，死锁的原因，产生死锁的必要条件和死锁的处理方式有基本的认识，需要熟练掌握如何使用银行家算法避免死锁以及死锁的检测与解除方法，特别地对死锁预防的四种方法要求了解清楚。
银行家算法借鉴于银行信贷操作法则，我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的法则为进程分配资源，当进程首次申请资源时，要求该进程提出对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量，则按当前的申请量分配资源，否则就推迟分配。
而当进程在运行中继续申请资源时，应该先检测该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过，则拒绝分配资源，若没有超过，则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足，则按当前的申请量分配资源，否则，也要推迟分配。银行家算法虽然可以避免死锁，但是要求进程提出对资源的最大需求量往往难以实现，因此，在现实系统中，银行家算法很少被实际使用，但是作为一种算法是值得探讨和研究的。
对于死锁，操作系统可定时运行一个“死锁检测”程序，该程序按一定的算法去检测系统中是否存在死锁。检测死锁的实质是判断是否存在“循环等待”条件，检测算法确定死锁的存在并识别出与死锁有关的进程和资源，提供给操作系统采取适当措施以恢复死锁。死锁的恢复实质上就是如何解除“循环等待”的条件，并且能让死锁环路中的进程能够继续运行。
系统一旦出现死锁后，必须采用一些方法来解除死锁和进行系统恢复。恢复死锁的方法有剥夺资源法，进程回退法，撤销进程法和重启系统法。除了重启系统法，采用其它方法时需要考虑以下问题：
（1）哪些资源可以剥夺?对系统的影响最小。
（2）重新运行或回退到还原点继续运行，若从一个进程那里剥夺了资源，要为该进程做些什么事情?若这个进程不能继续正常运行了，必须将该进程回退到还原点或某个状态，进程回退的状态由什么组成?有没有可能?如何记录?如何确定回退点的状态?
（3）若要撤销进程，如何选择一个代价最低的进程，它有哪些资源?
（4）如何保证不会发生“饿死”现象，也即如何保证并不总是剥夺同一进程的资源，导致该进程处于“饥饿”状态。
（5）怎样使得进程回退带来的开销最小?
三 内存管理
大纲要求：
1．内存管理基础
内存管理概念：
程序装入与链接、重定位技术；逻辑地址与物理地址空间；相对地址与绝对地址；内存保护方法（读写控制或键控制）。
交换与覆盖：内外存交换原理和方法。
连续分配管理方式：动态分区分配；动态分区分配的四种算法；内存分区的管理数据结构；链表法和位示图法。
非连续分配管理方式：简单分页管理方式；分段管理方式；段页式管理方式。
2．虚拟内存管理
虚拟内存基本概念：虚拟内存的基础；局部性原理；部分装入运行，
请求分页管理方式：虚拟页式的方法，数据结构，操作机制。
页面置换算法：最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK）。
页面分配策略：平均分配；比例分配；局部置换；全局置换。
抖动：抖动现象；抖动的原因；解决抖动的方法；工作集策略，工作集的实现。
请求分段管理方式：虚拟段式的方法，优缺点。
请求段页式管理方式：虚拟段页式的实现，适应用途。
知识点：
存储管理是操作系统的重要组成部分，它负责计算机系统内存空间的管理。其目的是充分利用内存空间，为多道程序并发运行提供存储基础，并尽可能地方便用户使用。近几年来，随着软、硬件技术和操作系统的发展，大容量存储技术使得充分利用内存空间的目的已经显得不再重要，但是由于处理机运算速度的提高，对内存管理的主要目的已经从原来的提高内存空间的利用率到提升内存的性能，也即内存的读写速度上，并且对存储的安全性越来越重视，对存储管理的主要目的的变迁可以看到计算机发展变化的快速。
存储管理主要是指对内存的管理，它是操作系统的重要功能之一。内存储器是计算机系统中的一种宝贵资源，对内存的管理和有效使用是操作系统中十分重要的内容。为了便于对内存进行有效的管理，一般将内存分成若干个区域，以便同时存放多个用户程序和系统软件。因此，存储管理应具有如下功能：内存的分配和回收、提高内存的利用率、加快内存的交换速度、“扩充”内存容量和存储保护。
存储分配主要解决多道作业之间划分内存空间的问题，存储分配有三种主要方式：直接分配方式、静态分配方式和动态分配方式。绝大多数计算机系统都采用静态分配方式或动态分配方式，对于嵌入式系统有部分采用直接分配方式。
为了实现静态和动态两种存储分配策略，需要采用将逻辑地址与物理地址分开，并实施地址重定位技术。所谓重定位是由于一个作业装入到与其地址空间不一致的存储空间时所引起的有关地址调整过程。实质上，这是一个地址变换过程，地址变换也称为地址映射。
根据地址变换进行的时间及采用的技术手段，可以把重定位分为两类：静态重定位和动态重定位。所谓静态重定位是在程序运行之前，由链接装配程序进行的重定位。静态重定位的特点是无须增加硬件地址变换机构，但要求为每个程序分配一个连续的存储区，且在程序运行期间不能移动，故难以做到程序和数据的共享；动态重定位是在程序的运行过程中，每当访问到指令或数据时，将要访问的程序或数据的逻辑地址转换成物理地址。
动态重定位的实现需要依靠硬件地址变换机构。最简单的实现方法是利用一个重定位寄存器。动态重定位的特点是需要附加硬件的支持，复杂的动态重定位技术是可以将程序分配到不连续的存储区中，在程序运行之前可以只装入部分代码即可运行，然后在程序运行期间，根据需要动态地申请分配内存。
利用程序运行的局部性原理，只要逻辑地址以及地址变换机构的字长足够多，系统可向用户提供一个比内存的存储空间大得多的地址空间，该地址空间称为虚拟存储器。程序运行时再通过动态重定位技术将虚拟地址转换到实际地址。虚拟内存管理方式包括有页式管理、段式管理以及段页式管理等多种内存管理技术，可以有效地对内存空间进行管理使用。
1．内存管理基础
（1）内存管理概念：包括程序的装入与链接，逻辑地址与物理地址空间关系，内存保护等。
内存管理实质上是对内存空间的部分系统区和所有用户区进行管理，其目的是尽可能地方便用户使用和提高内存空间的利用率。存储管理要为运行进程的程序和数据分配内存空间，并在不需要时回收它们占据的空间。内存管理必须配合硬件进行地址转换工作。把用户使用的逻辑地址转换成处理机能访问的绝对地址。
交换与覆盖：使用交换与覆盖实现内存扩充。覆盖是指一个作业的若干程序段，或几个作业的某些部分轮流使用某一段存储空间。主要目的是解决内存不足的问题以及保护自己的软件，防止软件被别人分析。交换实际上使用外存做缓冲，让用户程序在较小的存储空间中通过不断地换出、换入而进行较大的作业。可以提高内存利用率，增加并发进程数目，提高系统效率，当然也会付出代价。当交换频繁影响到系统时，这种换出换入就称为抖动。
内存空间的共享是指若干个进程能够同时访问公共程序所占的内存区。
内存保护是为了防止多程序在运行中互相干扰并保护区域内的信息不被破坏。
（2）连续分配管理方式和非连续分配管理方式：这两种管理方式的基本原理和工作过程，了解它们之间的关系和区别，以及各种方式的优点和缺点。连续分配管理方式包括单一连续管理、固定分区管理以及可变分区管理。单一连续管理的主要特点是管理简单，不需要太多的软硬件支持。但由于内存中只允许存放一个作业，因此系统的资源利用率不高。固定分区的优点是实现技术简单，适用于作业的大小和多少事先都比较清楚的系统中。但由于每个分区只能存放一道作业，所以内存的利用率不高，内碎片较多。可变分区又称为动态分区，这种内存管理技术是固定分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。但是存在外碎片，需要通过内存紧缩来合并。而非连续分配管理方式包括分页管理、分段管理以及段页式管理。现代操作系统主要使用非连续分配管理方式，应予以重视。
分页存储管理采用链表或位示图来管理可用物理页框，管理方法简单，但硬件开销大，进行内存分配时，每道作业平均内碎片长度为半个页面。分段存储管理消除了内碎片，可动态增加段长，便于动态装入和链接，可共享一个程序，便于实现存储保护。但地址变换和内存紧缩需占用CPU时间，管理表格需占存储空间，段的最大长度受实存限制，会出现系统抖动现象。段页式存储管理综合了上述两者的优点。
2．虚拟内存管理
虚拟内存基本概念要有所认识。
（1）虚拟内存是利用操作系统产生一个其容量比内存大得多的存储器，实际上是一个地址空间，其地址空间的大小受编译系统和处理机地址线及其变换机构的位宽所决定。虚拟内存与常规存储管理的一次性相反，虚拟内存将一个作业分成多次调入内存，在作业运行期间，虚拟内存允许将那些暂不使用的程序或数据从内存调至对换区，待以后需要时再调入内存，从而能有效地提高内存利用率。对用户来说所看到的大容量只是一种感觉，并不实际存在，因此是虚的。
对于虚拟页式存储系统，每当所要访问的页面不在内存时，便要产生缺页中断，请求操作系统将所缺页面调入内存，它是一种特殊的中断，和一般的中断有所不同。一般中断是由CPU在指令的最后一个周期的倒数第二个时钟周期检测到中断信号后产生的，而缺页中断是由访问的页面不在内存中产生的。缺页中断可以产生在指令中间。页面置换算法是在内存没有空闲页面，而又有程序和数据需要从外存中装入内存运行，这时需要从内存中选出一个或多个页面淘汰出去，以便新的程序和数据装入运行。
FIFO算法总是选择最早进入内存的一页将其淘汰。但FIFO算法忽略了一种现象的存在，就是最早进入内存的页面往往也是经常被访问的页。将这些页面淘汰，很可能刚置换出去，又请求调用该页，致使缺页中断太频繁，严重降低内存的使用性能和计算机系统整体的效率。同时对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。但是使用FIFO算法时，在未给进程或作业分配它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的现象。这称为belady异常。
最近最久未使用页面置换算法（LRU）是当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页面先淘汰。最佳置换算法即选择那些将来不再使用的，或者在很长时间内不再被访问的页面置换出去。是一种理想化的算法，性能最好，但在实际上难以实现。因为你无法预知将来的页面走向。
时钟页面替换算法（Clock）使用页表中的“引用位”，把作业已调入内存的页面链成循环队列，用一个指针指向循环队列中的下一个将被替换的页面。
（2）请求分页管理方式
段页式虚拟存储管理提供了大量的虚存空间，能有效地利用内存，为组织多道程序运行提供了方便。但同时增加了硬件成本、系统的复杂性和管理上的开销，页面使用不充分，各种表格占用内存空间，有系统抖动的危险。在请求分页存储管理中，可能会出现这种情况，即对于刚被替换出去的页，立即又要被访问，需要将它调入，因无空闲内存又要替换另一页，而后者又是即将被访问的页，于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重时导致系统瘫痪，这种现象称为抖动现象。这种现象的出现主要是由于程序在运行时呈现出局部性规律，即在一较短的时间内，程序的运行仅局限于某个部分。相应地，它所访问的存储空间也仅局限于某个区域。
局部性通常有时间局部性：程序中的某条指令一旦运行，不久以后该指令可能再次运行。如果某个数据被访问，则不久以后该数据可能被再次访问。原因是程序中存在大量循环操作。
空间局部性：一旦程序访问了某个存储单元，不久以后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围内。原因起于冯诺依曼体系计算机上顺序计算机，指令是顺序逐条执行。
为了解决抖动问题，通常采用工作集技术。所谓工作集是指在某段时间间隔内，进程实际要访问的页面的集合。引入虚拟内存后，程序只需有少量的内存就可运行，但为了使程序有效地运行，较少产生缺页，必须使程序的工作集尽量在内存中。
四 文件管理
大纲要求：
1．文件系统基础。
文件概念：什么是文件、文件系统，两者之间的区别。
文件结构：顺序文件；索引文件；索引顺序文件。
目录结构：目录的概念；文件控制块的概念；什么是索引节点；单级目录结构和两级目录结构；树形目录结构；图形目录结构。
文件共享：软链接和硬链接的方法。
文件保护：通过访问类型保护；通过访问控制保护。
2．文件系统实现。
文件系统层次结构：文件系统的概念；文件系统的多层模型。
目录实现：简单目录和复杂目录，目录项。
文件实现：管理方法和结构。
3． 磁盘组织与管理。
磁盘的结构：磁头、柱面、扇区；逻辑块号。对UNIX系统中的成组链，将盘块进行分组并将各个盘块组链成一个成组链来进行盘块的分配和回收
磁盘调度算法：先来先服务；最短寻道时间优先；扫描算法；查看算法等。上述算法分别是如何进行磁盘调度的，以及在这些调度算法的演变过程中，分别解决了哪些问题。会应用这些算法解题。
磁盘的管理：磁盘访问；坏区处理；可靠性等。
知识点：
计算机对于存储的需求是：高速；海量；非易失。内存速度快，容量小，易失，不能长期保存计算机信息，因此，计算机内的大量信息是存放在低速，大容量，非易失的硬盘或磁带、光盘上。为便于存放和查找，信息总是以文件的形式出现，平时保存在外存（主要是硬盘）上，当需要的时候将它们调入内存。操作系统中负责管理和存取文件信息的软件机构称为文件管理系统。用户通过文件管理系统就可实现“按名存取”，方便地使用文件，而无须了解存储设备的硬件特征和存取过程。文件系统是操作系统中负责存取和管理信息的模块，它用统一的方式管理系统本身和用户的信息，为它们的存储、检索、更新、共享和保护提供一整套方便有效的文件使用和操作方法。
“文件”这一术语不但反映了用户概念中的逻辑结构，而且和存放它的辅助存储器（也称文件存储器）的存储结构紧密相关。所以，同一个文件必须从逻辑文件和物理文件两个侧面来观察它。对于用户来说，可按自己的愿望并遵循文件系统的规则来定义文件信息的逻辑结构，由文件系统提供“按名存取”来实现对用户文件信息的存储和检索。
用户在处理他的信息时，只需关心所运行的文件操作及文件的逻辑结构，而不必涉及存储结构。但对文件系统本身来说，必须采用特定的数据结构和有效算法，实现文件的逻辑结构到存储结构的映射，实现对文件存储空间和用户信息的管理，并提供多种存取控制和保护的方法。
操作系统的功能之一是资源管理，其中对计算机系统的软件资源管理就会用到文件管理。在计算机系统中，软件资源非常重要，对软件资源的使用也相当频繁，因此文件系统在操作系统中也占有非常重要的地位。为了实现这些功能，操作系统必须考虑文件目录的建立和维护、文件存储空间的分配和回收、数据的保密和安全、用户存取和修改文件的权限、信息的存储次序、以及怎样检索用户信息等许多问题。
文件管理在实际的系统中有不同的模型，相互之间差异很大，所呈现的特性也各不相同，同学们应该兼收并蓄，融会贯通，把握文件系统的实质，从而做到熟悉并运用文件管理的各种方式，会处理各种局面。
文件管理不是考试的重点，这一章出题的量不会很大，文件管理的重点是文件的几种逻辑物理结构，目录的管理和磁盘管理，可能容易出题的是磁盘管理各种调度算法的基本原理以及应用（随着时间的变迁和软硬件的发展，实际操作系统中对磁盘的调度已经归口到专门的存储系统，操作系统倾向于不再关心它了）。
现行的数据信息已经积累到了相当的数量，人们对数据信息的依赖也越来越强，所以信息安全存放和使用是一个非常重要的问题。在一些重要的场合，例如政府、银行、石油、电信等部门，信息数据无论数量或重要性均已经上升到了一个新的高度。基于操作系统的文件系统管理已经显得力不从心了，所以目前普遍发展的容错和灾难备份系统扩展了操作系统对文件进一步进行管理，其理论和模型也演变成了一门独立的研究方向。它是对文件系统的一个有力的补充和支持，也是大存储概念的一部分。
1．文件系统基础
文件的定义为：文件是被命名的相关联的数据集合体。
文件的物理结构：是指文件在外部存储介质上的存放形式，也叫文件的存储结构。它对文件的存取方法有较大的影响。文件在逻辑上看都是连续的，但在物理介质上存放时却不一定连续。
通常有以下一些物理存储组织形式。
连续文件也称为顺序文件，是基于磁带设备的最简单的物理文件结构，它是把一个逻辑上连续的文件信息存放在连续编号的物理块中。连续文件的优点是在顺序存取时速度较快，常用于存放系统文件，如操作系统文件、编译程序文件和其他由系统提供的实用程序文件。但连续文件可能出现外部碎片，就是在存储介质上存在很多空闲块，但它们都不连续，无法被连续文件使用，造成浪费。
索引文件系统为每个文件建立一个索引表，其中的表项指出存放该文件的各个物理块号，而整个索引表由文件说明项指出，它可以方便地进行随机存取。但是这种组织形式需要增加索引表，增加了空间开销。其中如果索引文件的数据区的记录按关键字排列有序，称为索引顺序文件。
2．文件系统实现
每个文件的文件目录项（也称文件头）又称文件控制块FCB（File Control Block），FCB一般应该包括以下内容：有关文件存取控制的信息，有关文件结构的信息（文件的逻辑结构和文件的物理结构以及文件物理结构类型，记录存放在外存的相对位置或文件第一块的物理块号，也可指出文件索引的所在位置等），有关文件使用的信息，已打开的文件，文件被修改的情况，文件最大和当前大小等。有关文件管理的信息：如文件建立日期，文件最近修改日期，文件访问日期等。
文件系统在磁盘上一般存放在分区中，以卷的形式出现。文件系统出了包含文件，目录以外，还包含启动信息（存放在启动块里），文件分配信息，空闲块管理信息等。不同文件系统在磁盘上还需要主引导记录来指示系统启动的路径。
3．磁盘组织与管理
要使磁盘服务尽可能快，就需要操作系统提供合适的磁盘调度算法，以改善磁盘服务的平均时间。设计磁盘调度算法应当考虑两个基本因素是公平性（一个磁盘访问请求应当在有限时间内得到满足）和高效性（减少设备机械运动所带来的时间开销）。
先来先服务磁盘调度算法（FCFS）即按照访问请求的次序为各个进程服务，这是最公平而又最简单的算法，但是效率不高。固为磁臂的移动速度很慢，如果按照访问请求发出的次序依次读写各个磁盘块，则磁臂将可能频繁大幅度移动，容易产生机械振动，亦造成较大的时间开销，影响效率。
最短寻道时间优先磁盘调度算法（SSTF）以寻道优化为出发点，优先为距离碰头当前所在位置最近磁道（柱面）的访问请求服务。这种算法改善了平均服务时间，但也存在缺点，假设某一段时间外磁道请求不断，则可能有内磁道请求长时间得不到服务，缺乏公平性。
扫描算法（SCAN）因其基本思想与电梯的工作原理相似，故又称电梯算法。SCAN算法也是一种寻道优化的算法，它克服了SSTF算法只考虑访问磁道与磁头当前位置的距离，而未考虑磁臂的移动方向，而SCAN算法则既考虑距离，也考虑方向，且以方向优先。即：当无访问请求时，磁头臂停止不动，当有访问请求时，磁头臂按照方向扫描。这种算法比较公平，而且效率较高。
五 输入输出（I/O）管理
大纲要求：
1．输入/输出管理概述。
输入/输出设备：输入/输出设备的概念，分类，高速低速，字符以及块设备等。
输入/输出管理目标：外设资源的控制，外设资源的共享，提高外设资源的利用率。
输入/输出管理功能：提供设备使用的用户命令接口和编程接口，设备分配和释放，设备的访问和控制，输入/输出缓冲和调度，提高输入/输出访问效率。
输入/输出应用接口：针对用户接口，提供抽象的命令，如：Open， Close， Read， Write；针对通信设备，则是通信体系结构如网络协议栈；针对文件存储设备，是文件系统的逻辑结构控制；
输入/输出控制方式。程序访问，中断，DMA和通道技术四种控制方式。
2．输入/输出核心子系统。
输入/输出调度概念：物理设备控制实体；设备驱动程序；并发输入/输出访问调度；设备控制和状态维护；中断处理等。
高速缓存与缓冲区：单缓冲，双缓冲，环形缓冲技术。
设备分配与回收：设备分配的原则以及设备分配的数据结构。
假脱机技术（SPOOLing）：高速虚拟输入/输出操作；实现对独享设备的共享。
出错处理：对错误的反应以及处理。
知识点：
输入输出（I/O）设备是计算机系统的重要资源，用户无权直接使用。设备管理是对硬件资源中除CPU、存储器之外的所有设备进行管理，而外设占整个系统投资的比重比较大，管理好整个系统的设备，使其高效地发挥功是操作系统的重要任务。
设备管理的一个重要任务便是按照一定的算法在各进程间调度和分配设备，同时设备管理还要按照用户要求启动具体设备，完成数据传输操作，并且处理设备的中断，以及如何利用虚拟技术使独享设备变为共享设备，使一台物理设备变为多台逻辑设备。
本章在操作系统中题量较少。由于设备管理在不同操作系统中差异较大，设备的发展又日新月异，因此，主要要掌握几个关键要素和基本准则。
1．I/0管理概述
输入输出管理的重点是四种I/O控制方式各自的特点及其相互比较，而中断处理和SPOOLing技术，提高性能的缓冲策略也很重要。
设备管理的主要任务之一是控制设备和内存或CPU之间的数据传送，外围设备和内存之间的I/O控制方式有四种：
（1）程序访问：由用户进程直接控制内存或CPU和外围设备之间的信息传送。这种方式使CPU和外围设备只能串行工作。CPU在一段时间内只能和一台外围设备交换数据信息，不能实现设备之间的并行工作，无法发现和处理由于设备或其他硬件所产生的错误。
（2）中断是指计算机在运行期间，系统内发生其它非预期的急须处理事件，使得CPU暂时中断当前正在运行的程序而转去运行相应的事件处理程序，待处理完毕后又返回原来被中断处继续运行的过程。中断控制方式比程序访问方式提高了CPU的利用率。CPU可以不用花费大量时间去照应I/O设备，直到有具体操作时再响应。
（3）DMA方式又称直接存取方式。其基本思想是在外围设备和内存之间开辟直接的数据交换通路。中断方式的数据传送是在CPU控制下完成的，而DMA方式则是在DMA控制器的控制下完成的。并发性更好。
（4）通道是一个独立于CPU的专管输入/输出控制的处理机，它控制设备与内存直接进行数据交换。它有自己的通道指令，这些通道指令受CPU启动，并在操作结束时向CPU发送中断信号。在DMA方式中，数据的传送方向、存放数据的内存起始地址及传送数据块长度等都由CPU控制，而在通道方式中，这些都是由专管输入/输出的通道来进行控制。通道控制方式可以做到一个通道控制多台同类设备与内存进行数据交换，这与用DMA方式时每台设备至少有一个DMA控制器不同。
2．I/0核心子系统
为了提高系统的可适应性和可扩展性，所编制的用户程序应与实际使用的物理设备无关，这就是设备独立性或设备无关性。为了实现设备独立性而引入了逻辑设备和物理设备的概念。所谓逻辑设备是实际物理设备属性的抽象，它并不局限于某个具体设备。为了实现设备的独立性，引入逻辑设备和物理设备两个概念。在应用程序中，使用逻辑设备名称来请求使用某类设备；而系统运行时，是使用物理设备名称。鉴于驱动程序是一个与硬件（或设备）紧密相关的软件，必须在驱动程序之上设置一层软件，称为设备独立性软件，以运行所有设备的公有操作，完成逻辑设备名到物理设备名的转换（为此应设置一张逻辑设备表）并向用户层（或文件层）软件提供统一接口，从而实现设备的独立性。
SPOOLing系统是用户层I/O软件的另一重要类别。它是在多道程序设计中将一台独占设备改造为共享设备的一种行之有效的技术。
在实现后台打印时，SPOOling系统应为请求I/O的进程提供以下服务：
（1）由输出进程在输出井中为之申请一空闲盘块区，并将要打印的数据输入其中。
（2）输出进程再为用户进程申请一张空闲的用户打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。
（3）一旦打印机空闲，输出进程便从请求打印队列的队首取出一张请求打印表，根据表中的要求将要打印的数据从输出井传送到内存缓冲区，再由打印机进行打印。
最新评论（共0条）评论一句
Copyright©2007–2021 www.100xuexi.com All rights reserved 圣才学习网 版权所有
全国热线：400-900-8858（09:00-22:00），18001260133（09:00-22:00）
增值电信业务经营许可证 出版物经营许可证 网络文化经营许可证 广播电视节目制作经营许可证
