计算机操作系统(第四版)汤晓丹,梁紅兵,哲凤屏,汤子瀛编著,西安电子科技大学出版社
1.2操作系统的发展过程:是一组能有效组织和管理计算机硬件和软件资源，合理对各类作业進行调度以及方便用户使用的程序的集合。1.2.1未配置操作系统的计算机系统1、人工操作方式[缺点:用户独占全机CPU等待人工IO操作]，严重降低叻计算机资源的利用率2、脱机输入/输出(Off-LineI/O)方式，程序和数据的输入实在外围机(脱离主机)的控制下完成[优点:减少了CPU的空闲时间(IO操作不占用主机时间)，提高了IO速度(数据直接从高速磁带上输入到内存中)]1.2.2单道批处理系统先把一批作业以脱机方式输入到磁带上在系统监督程序的控淛下，使作业能够一个接着一个的连续处
[缺点:资源得不到充分的利用(当理批处理系统旨在提高系统资源的利用率和系统吞吐量。
程序发絀IO请求后CPU必须等待)]1.2.3多道批处理系统利用作业调度算法，当一程序因IO操作而使CPU空闲时调用执行另个程序。[优点:资源利用率高系统吞吐量大。和平均周转时间都尽可能短2.系统吞吐量高，指单位时间内系统所完成的作业数与处理的作业从平均长度有关。3.处理机使用率高分时系统的目标:1.响应时间快，从用户提交一个请求开始到显示出处理结果为止2.均衡性好，指系统响应时间的快慢与用户请求服务的复雜性相适应实时系统的目标:1.截止时间短，2.可预测性
3.2.3先来先服务FCFS和短作业优先SJF调度算法FCFS:系统按照作业到达的先后次序进行调度。主要用於与其他调度算法结合形成一种更为有效的调度算法，如可以把进程按优先级设置多个队列每个队列采用FCFS。SJF:作业时间短优先级高。[缺点：]1.必须预知作业的运行时间2.对长作业非常不利。3.无法时间人机交互4.不能保证紧迫作业及时执行。
4.2进程的装入和链接用户程序要在系统中运行必须先装入内存，然后将其转变为一个可以执行的程序1.编译，编译程序对源程序进行编译形成若干个目标模块。2.链接(静態链接和动态链接)链接程序将一组目标模块和他们所需的库函数链接在一起，形成一个完成的装入模块3.装入，将装入模块装入内存4.2.1程序装入：1.绝对装入方式，事先知道程序将驻留在内存的位置装入模块装入内存后，程序中的逻辑地址与内存物理地址相同2.可重定位裝入方式，编译形成的目标模块起始地址都是从0开始，程序中的其他地址都是相对于其实地址计算的装入时对目标程序中指令和数据哋址的修改成为重定向。地址变换实在程序装入时一次性完成故称为静态重定向。3.动态运行时装入方式指把模块装入内存后，不立即紦装入模块中的逻辑地址转换为物理地址而使把地址转换关键词来检索记录，需要为顺序文件建立多个索引表[优点：极大的提高了对攵件的查找速度，插入和删除记录也很方便缺憾：每个记录都有一个索引项，增加了存储开销]7.2.5索引顺序文件1.一个是引入了文件索引表，通过索引表可以时间对索引顺序文件的随机访问；另一个是增加了溢出文件用来记录新增加的，删除和修改的记录能有效克服变长記录文件的缺点，又不需要付出过多代价2.一级索引顺序文件：只使用了一级索引，索引项中含有首记录的关键字和指向记录的指针在對索引顺序文件检索时，首先利用用户提供的关键字以及某种查找算法检索索引表找到该记录所在记录组中的第一个记录的表项，从中嘚到该记录组的第一个记录在为主文件中的位置然后利用顺序查找方式查找主文件。3.两级索引顺序文件:顺序文件建立了多级索引,即为索引文件建立一张索引表,形成两级索引表
缺点:平均周转时间长，无交互能力]多道批处理系统需要解决的问题有：1处理机争用问程度设置的優先级进行调度HRRN：是既考虑了作业的等待时间，又考虑了运行时间的题2内存分配和保护问题，3IO设备分配问题4文件的组织和管理问题，5作业管理问
调度算法[优点:]既照顾了短作业又不使长作业的等待时间过长，改善了处理机调度的性题
6用户与系统的借口问题。1.2.4分时系統指在一台主机上连接了多个配有显示器和键能优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间。1.如果作盘的终端并甴此所组成的系统该系统允许多个用户通过自己的终端，以交互方式使用和业等待时间相同则要求服务时间越短，优先权越高有利於短作业。2.当要求服务时间计算机共享主机中的资源。及时接受及时处理。[特性:多路性独立性，及时性交相同，优先权取决于响應时间3.对于长作业，优先级随着等待时间的增加而提高[缺点:]互性]1.2.5实时系统指系统能够及时响应外部事件的请求，在规定时间内完成对該事件的调度前需要做响应比计算增加系统开销。
处理并控制所有实时人物协调一致地运行。[实时系统的类型]：工业控制系统信息查3.3.1.1进程调度的任务1.保存处理微机的硬件系统现场信息。2.按某种算法选取进程3.把处理器分询系统，多媒体系统嵌入式系统。1.2.6微机操作系統的发展1、单用户单任务操作系统:配给进程3.3.1.2进程调度机制1.排队器，事先将系统中的所有就绪进程按照一定的策略只允许一个用户上机苴只允许用户程序作为一个任务运行。2、单用户多任务操作系统:排成一个或多个队列2.分派器，将处理机分配个新选出的进程3.上下文切換器，分派处只允许一个用户上机但允许用户把程序分为若干个任务，并发执行有效的改善系统的理器时，新选进程的CPU现场信息装入箌处理器的各个寄存器中；阻塞进程时将处理器性能。3、多用户多任务操作系统:允许多个用户通过各自的终端使用同一台机器，共享寄存器中的现场信息保存到进程PCB中3.3.1.3进程调度方式1.非抢占方式：把处理机主机系统中的各种资源。每个用户程序又可以进一步分为几个任務并发执行，进一步提分配给进程后只有当进程运行结束或者阻塞时，才将处理机分配给其他进程[优点:]实高资源利用率和系统吞吐量。
现简单系统开销小。适用于大多数批处理系统2.抢占方式，允许调度程序根据某种原1.3操作系统的基本特征1.3.1并行指两个或多个事件在哃一时刻发生并发则，去暂停某个正在执行的进程将处理机分配个另一个进程。抢占原则1.优先权原则性指两个或多个事件在同一时間间隔内发生。1.3.2进程指在系统中能够独立运行并作为2.短进程优先原则3.时间片原则。
资源分配的基本单位由一组机器指令，数据和堆栈等组成是一个活动实体。多个进程3.3.2转轮调度算法之间可以并发执行和交换信息能够极大的提高系统资源的利用率和增加系统吞吐量。運行一个时间片保证就绪队列中的所有进程在确定的时间内，都能获得一个时间片的处2.1.3程序并发执行2.理机时间进程切换时机：1.时间片未用完，进程已经结束2.时间片已用完。时间片大小的特征:间断性失去封闭性，不可再现性程序并发执行时由于共享系统资源和为完荿同的确定：一个较为可取的时间片是略大于一个典型交互所需要的时间，使大多数交互进程一项任务而相互合作致使并发的程序之间形成了相互制约的关系。程序并发执行时系能在一个时间片内完成，从而获得很小的响应时间统中共享的资源状态有并发程序来改变，使任一程序在运行时其环境都会受到其他程序3.3.3优先级调度算法1.非抢占式优先级调度算法。2.的影响而失去封闭性程序失去了封闭性，吔将导致失去可再现性
1.静态优先级，在创建进程时确定整个运行期间不会改变。2.动态优先级进程创建初期2.2.1进程的定义与特征定义：為了使程序能够并发运行并保持独立性，对并发的程序加赋予一个优先级随着进程的推进或等待时间的增加而改变，以便获得更好的调喥性能以描述和控制，引入进程操作系统为保证并发程序的独立性，设置了一个专门的数据结3.3.4多队列调度算法将不同类型或性质的进程固定分配在不同的就绪队列中不同的就构：进程控制块PCB。利用PCB来描述进程的基本情况和活动过程进而控制和管理进程。绪队列采用鈈同的调度算法
创建撤销进程，就是创建撤销进程实体中的PCB进程是进程实体的运行过程，是系统3.3.5多级反馈队列调度算法事先不需要知噵各种进程所需的执行时间还可以较好的满进行资源分配和调度的独立单位。进程的特征动态性并发性，独立性异步性。进程同足各类进程的需求调度机制：1.设置多个队列，为每个队列赋予不同的优先级优先级步机制，当进程在并发运行具有异步性时保证进程並发执行的结果是可再现的。进程的越高时间片越小。2.每个队列都采用FCFS算法3.按队列优先级调度。调度程序首先调三种基本状态:就绪状態执行状态，阻塞状态另外有创建状态和终止状态。引入创建度最高优先级队列中的进程运行第一队列空闲时才调度第二队列。调喥算法的性能：如状态是为了保证进程的调度必须在创建工作完成后进行确保对PCB操作的完整性，也增果规定第一个队列的时间片略大于哆数人机交互的处理时间便能较好满足各类用户的需加了管理的灵活性。挂起操作和进程状态的转换:引入挂起操作的原因：终端用户的需要求。终端用户作业在第一队列时间片中完成短批处理用户的周转时间较短，长批处理用父进程请求对换需要，负荷调节的需要操作系统的需要。处于挂起状态的进程不能接户不用担心长期得不到处理
收处理机调度。状态的转换：1.活动就绪->静止就绪2.活动阻塞->靜止阻塞，3.静止就绪3.3.6基于公平原则的调度算法不是保证优先运行而是明确的性能保证，->活动就绪4.静止阻塞->活动阻塞。
每个相同类型的進城获得相同相同的运行时间公平分享调度算法调度的公平性针对用2.2.4进程控制块PCB的作用PCB是操作系统中最重要的记录型数据结构。1.作为独竝运户使所有用户能获得相同的处理机时间，或所要求的时间比例调度是以进程为基本单行基本单位的标志，PCB已成为进程存在于系统Φ的唯一标志2.实现间断性运行方式。3.
位的必须考虑到每个用户的进程数。
提供进程管理所需要的信息
4.提供进程调度所需要的信息。5.實现与其他进程的同步与通3.5.2计算机系统中的死锁死锁是源于多个进程对资源的争夺对不可抢占资源争夺，对信进程控制块中的信息：主要包括1.进程标志符，2.处理机状态3.进程调度信息，4.可消耗资源的争夺和进程推进顺序不当时会引起死锁。
进程控制信息处理机状态信息主要由处理微机的硬件系统各种寄存器中的内容组成，包括1.通用寄3.5.3死锁的定义必要条件和处理方法存器，2.指令计数器3.程序状态字，4用户栈指正当进程被切换时，处理机状态信息必待仅由该组进程中的其他进程才能引发的事件那么该组进程时死锁的。死锁的必要條件：须保存在相应的PCB中以便在进程重新执行时能够从断点继续。进程控制块的组织方式:1.互斥条件在一段时间内，某资源只能被一个進程占用2.请求和保持条件，进程已经保1.线性方式将系统中所有的PCB都组织在一张线性表中。2.链接方式把具有相同状态持了一些资源，叒请求新的资源却被其他进程占用，此时进程被阻塞3.不可占用条件，的PCB分别通过PCB中的链接字链接成一个队列如就绪队列，阻塞队列囷空白队列3.进程已获得的资源在未使用完之前不能被抢占。4.循环等待条件,发生死锁时必然存在一个索引方式根据进程状态的不同，建竝几张索引表如就绪索引表和阻塞索引表。
进程-资源的循环链即每个进程都在等待另一个进程的资源释放。处理死锁的方法：1.预2.4.1进程哃步的基本概念进程同步机制的主要任务是对多个相关进程在执行次序上进行防死锁通过设置限定条件，破坏产生死锁四个必要条件中嘚一个或几个易实现。2.避协调使并发执行的诸进程之间能够按照一定的规则共享系统资源，并能很好的相互合作免死锁，在资源的動态分配中用某种方法防止系统进入不安全状态，从而避免死锁的发从而使程序的执行具有可再现性1。两种形式的制约关系：1).间接相互制约关系进程生，例如使用银行家算法3.检测死锁，事先不采取任何措施通过检测机构及时的检测之间因为临界资源的使用而相互淛约。因此系统的资源必须有系统实施统一分配用户先
出死锁的发生，然后采取措施解脱死锁4.解除死锁，当检测到系统已发生死锁撤销一申请才能使用资源。2).直接相互制约进程之间有严格的执行次序的制约。
2.临界资源：不些进程回收资源，并将资源分配各阻塞状態中的进程解除死锁。
同进程之间所共享的数据变量，资源涉及使用和修改时，都需要作为临界资源互斥访3.6死锁的预防1.一次性地申請进程在整个运行过程中所需要的全问3.临界区：访问临界资源的代码称为临界区。4.进程同步应遵循的规则：1).空闲让部资源进程在整个運行期间，不会再提出资源请求[缺点:1.资源被严重浪费，严重恶化出临界资源空闲时需要立即让请求的进程使用该资源。2).忙则等待临堺资源被使用时，了资源的利用率2.使进程经常发生饥饿现象。]2.允许一个进程获得运行初期所需资源其他进程需要等待资源使用完毕再使用。3).有限等待保证进程能在有限的时间内进入临化后开始运行。在运行过程中初步释放自己使用完毕的资源申请新的资源。能使进程更界区以免进入忙等。4).让权等待进程不能进入临界区时，让出处理机以免进入忙等快的完成任务，提高设备的利用率减少进程發生饥饿的几率。破坏不可抢占条件：当一状态
个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能满足时必须释放洎2.4.2硬件同步机制1.2.Test-and-Set3.Swap硬件指令能够己所有的资源，以后需要时再申请[缺点:可能使进程无限推迟执行，延长了进程的周转有效的实现进程互斥但是容易让进城进入忙等状态，也很难解决复杂的进程同步问题时间，增加系统开销降低吞吐量。]破坏循环条件：对系统所有资源進行线性编号规2.4.3信号量机制1.一个用于表示资源数目的整型量S，仅能通过两个标准定每个进程都按照资源编号顺序请求资源进程必须释放所有具有相同或者更高序号的资的院子操作wait(S)和signal(S)来访问。整型信号量未遵循让权等待原则2.记录型信号量：源后才能申请较低序号的资源[缺点:各类资源的序号必须相对稳定，限制了新设备的增是一种不存在忙等的进程同步机制在信号量机制中，还增加了一个进程链表指针list用加。作业使用的资源顺序和资源编号不一致限制用户自主，简单的编程]
于链接所有等待进程。3.AND型信号量：将进程在整个运行过程Φ需要的资源一次性分3.7避免死锁指系统能按照某种进程推进顺序为每个进程分配所需资源配，结束后一次性释放4.信号量集：对AND信号量進行扩充，对进程所申请的所有资直至满足每个进程对资源的最大需求使每个进程都可顺利的完成，此时为一个安全资源源以及每类资源不同的资源需求量再一次PV原语操作中完成申请和释放。信号量集的分配序列有安全序列则为安全状态。避免死锁的实质在于在进行資源分配时是系统不特殊情况：1).Swait(S,d,d),信号量集中只有一个信号量S，允许每次申请d个资源当现有进入不安全状态。
资源少于d时不予分配。2).Swait(1,1),蛻变为记录型信号量或互斥量3).Swait(s,1,0)，当3.8死锁的检测与解除死锁检测：1.S》=1时允许多个进程进入临界区，当S变为0时阻止任何进程进入临界区。
资源请求边是从进程指向资源，分配边是从资源指向进程2.死锁定理：当且仅当某一2.4.5管程机制管程是对进程共享资源的申请，释放和其他操作的封装代表共享资源的状态时的资源分配图是不可简化的。简化的方法：1).在资源分配图中找到不阻塞也不独立数据结构及有对該共享数据结构操作的一组过程组成的资源管理程序构成了一个操作系统的进程结点P1正常情况下该结点是可以获得资源顺利执行完并释放所有资源的。去除该的资源管理模块管程。管程的主要特性：1).模块化2).抽象数据类型，3).信息掩蔽2.结点的请求边和分配边使其孤立。2).P1釋放资源后P2才可以继续运行，消除P2的请条件变量：当一个进程调用了管程在管程中时被阻塞或挂起，直到解除为止的期间内求边和汾配边，使其孤立3).若能够消除所有进程结点的请求边和分配边，则该资源分配如果不释放管程其他进程便无法进入管程，被迫长时间等待因此引入条件变量，指引图是可简化的反之不能简化，就会产生死锁
起进程阻塞和挂起的条件的变量。x.wait是将因某个条件阻塞或掛起的进程送入等待队列3.类似于银行家算法的数据结构。
并释放管程x.signal是将因某个条件送入等待队列的进程激活。死锁解除：解除死锁嘚方法有两种1是抢占资源，从一个或多个进程中抢占足够数量的3.1.1处理机调度的层次1.调度对象是作业根据某种算法将外村上处于后备队資源，分配给死锁进程以解除死锁状态。2是终止进程终止一个或多个死锁的进程，列中的哪几个作业调入内存创建进程，分配必要嘚资源放入就绪队列。多用于多道批知道打破死锁环路终止的方法有：1).终止所有死锁进程,2).逐个终止死锁进程。
处理系统中2.低级调度：调度对象是进程，根据某种算法保存处理微机的硬件系统现场信息，并
终止进程时要考虑的因素：1).进程的优先级大小2).进程执行的时間，还要执行的时间决定就绪队列中的哪个进程获得处理机。进程调度是一种最基本的调度
3.中级调度:又为3).进程使用的资源，还需要的哆少资源4).进程是交互式还是批处理式
内存调度，对象是进程主要目的是提高内存利用率和系统吞吐量，把暂时不能运行的进代价最小嘚死锁解除算法：从死锁状态S中先终止一个死锁进程P1使系统状态由S演程调至外存等待，进程状态变为挂起状态当运行条件具备和内存涳余时，再把进程调度变成U1将P1记入被终止进程的集合d(T)中，并把所付出的代价C1加入到Rc(T)中；对到内存中的就绪队列变为就绪状态。
死锁进程P2P3等重复上述过程。得到状态U1U2...Un后，在按终止进程时话费的代缴3.1.2处理机调度算法的目标:1.提高资源利用率使处理机和其他所有资源尽可夶小，把它插入到由S状态所演变的新状态队列L中队列L的第一个状态U1时有S状能的保持忙碌状态。2.公平性每个进程都获得合理的CPU时间，不發生进程饥饿现象态花最小代价终止一个进程所演变成的状态。在终止一个进程后若系统还是处于死锁状3.平衡性，尽可能保持系统资源使用的平衡性4.:1.平态，则再从U1状态按照上述处理方式在依次的终止一个进程得到U1’,U2’...Uk'状态，再均周转时间短作业被提交给系统开始箌作业完成为止的时间间隔短。应使作业周转时间从U’状态中选出一个代价最小的Uj’,如此下去直到死锁解除把系统从死锁中解除出来所嶊迟到程序真正要执行时进行。装入内存后的所有地址都是逻辑地址三种装入方式都适7.3文件目录文件目录也是一种数据结构，用于标识系统中的文件及其物理地址供检索用于多道程序环境中。4.2.2程序链接：1.静态链接方式程序在运行之前，先将各个目标时使用对目录管悝的要求：1.实现”按名存取”，2.提高对目录的检索速度3.文件共享，模块及他们所需的库函数链接成一个完整的装配模块以后不可拆开。[需要解决的问题：4.允许文件重名
1.修改模块间的相对地址。2.变换外部调用符号将其变换为相对地址。]2.7.3.1文件控制块和索引结点文件控制塊FCB是为了能对一个文件进行正确的存取而必须接方式指目标模块装入内存时，边装入边链接。[优点：1.便于修改和更新目标模块2.为文件设置用于描述和控制文件的数据结构。文件与文件控制块一一对应文件控制块的便于实现目标模块的共享。]3.运行时动态链接方式将模块的链接推迟到程序执行时才有序集合称为文件目录，也是一个文件1.文件控制卡FCB：FCB中含有基本信息，存取进行程序执行过程中发现被调用模块未装入内存，OS立即寻找该模块并装入内存，连控制信息和使用信息三类信息2.索引结点：把文件名与文件描述信息分开，时攵件描接到调用者模块上[优点:加快程序的装入过程，节省大量的内存空间]
述信息单独形成一个称为索引结点的数据结构。在文件目录Φ的每个目录项仅由文件名和4.5分页存储管理方式指向该文件所对应的索引结点的指针所构成磁盘索引结点：存放在磁盘上的索引结点，夶小的区域成为页或页面。将内存空间分为若干个物理块页和块的大小相同，可以将每个文件有唯一的一个磁盘索引结点内存索引結点：存放在内存中的索引结点，文件被程序的若干页面放入内存的多个多个可以不相邻的物理块中最后一页经常装不满，形成打开时要将磁盘索引结点号拷贝到内存的索引结点中。
不可利用的碎片称为页内碎片。页面过小可以减少内存碎片的总空间，提高内存的利7.3.2简单的文件目录1.整个文件系统中只建立一张目录表每个文件占用效率，但会使一个程序占用较多的页面导致页表过长，占用大量内存降低页面换进一个目录项。为表明每个目录项是否空闲有设置了一个状态位。优点是简单能够实现换出的效率。页面过大减少叻页表的长度，但会增大页内碎片页表：实现从页号到物目录管理中最基本的功能：按名存取。不满足其他三方面要求即：查找速度慢，不允许理块号的地址映射允许将进程的各个页面离散的存储在内存的任一物理块中。
重名不便于实现文件共享。2.两级文件目录：為每个用户再建立一个单独的用户文件目4.5.2地址变换机构任务是将逻辑地址中的页号转换为内存中的物理块号是借助页表来
录UFD，由用户所囿文件的文件控制块组成建立一个主文件目录MFD，MFD中每个用完成的1.基本的地址变换机构：页表大多驻留在内存中，在系统中设置一个页表寄存器
户目录都占有一个目录项，包括用户名和指向该用户目录文件的指针两级文件目录提高存放页表在内存的起始地址和页表的長度。进程未执行时页表的起始地址和长度存放在了检索目录的速度，在不同的用户目录中可以使用相同的用户名不同用户可以使用鈈同进程的PCB中。当调度到该进程时才将这两个数据装入到页表寄存器中当进程要访问某的文件名访问系统中的同一共享文件。
个逻辑地址中的数据时分页地址变换机构会自动地将有效地址(相对地址)分为页号和页7.3.3树形结构目录1.可以明显提高对目录的检索速度和文件系统的性能。从内地址以页号为索引检索页表。检索前先将页号和页表长度比较若页号大于页表长度，当前目录开始直到数据文件位置所构荿的路径名称为相对路径把从树根开始的路径名称则报错。否则将页表起始地址和页号与页表项长度的乘积相加得到该表项在页表中嘚位为绝对路径名。[优点：查询速度更快层次结构更加清晰，能够有效的进行文件的管理和置于是可以得到该页的物理块号，将之装叺物理地址寄存器中再将有效地址寄存器中保护。]
的页内地址送入物理地址寄存器的块内地址字段中完成逻辑地址到物理地址的转换。2.7.3.4目录查询技术1.在单级目录中利用用户提供的文件名，用顺序查找具有快表的地址变换机构：提高地址变换速度在地址变换机构中增設一个具有并行查询法直接从文件目录中找到指定名称的目录项。在树形目录中用户提供的文件名是由多个能力的高速缓冲寄存器，快表在CPU给出有效地址后，有地址变换机构自动将页号P送文件分量名组成的路径名需要对多级目录进行查找。2.Hash方法：系统利用用户提供的叺快表中并将此页号与快表中所有页号进行比较，若有匹配的页号便可直接从快表中文件名，变换为文件目录的索引值利用索引值箌目录中查找。这样显著提高了检索速度读出该页所对应的物理块号，并送到物理寄存器中如果在快表中没有找到，则需要访问8.2文件存储空间管理为文件分配磁盘时除了需要文件分配表外，系统还应为可分配存内存中的页表把从页表项中读出的物理块号送到地址寄存器，同时将此页表项存入快表储空间设置相应的数据结构即磁盘分配表，用于基础可供分配的存储空间情况提供对中。若满了就替换认为不再使用的页表项。
盘块进行分配和回收的手段
4.5.4.1两级页表当页表过大很难找到连续的内存空间来存放页表的时候，可将页表进荇8.2.1空间表法和空闲链表法1.为每个文件分配一块连续的存储空间系统为分页，是每个页面的大小与内存物理块的大小相同编号，并离散嘚存在不同的物理块中外存上的所有空间区建立一张空闲表，每个空闲区对应于一个空闲表项包括表项序号、同时创建一张外层页表，在页表项中记录了页表页面的物理块号利用外层页表和页表的
该空闲区的第一个盘块号、该区的空闲盘块数等。将所有空闲区按其其實盘块号递增的次两级页表结构时间从逻辑地址到物理地址的变换
[两级页表并没有解决长页表占用内存大序排列，形成空闲盘块表2.空閑链表法：是将所有空闲盘区拉成一条空闲链。根据构成的现象]在采用两级页表结构的情况下，对于正在运行的进程必须将外层页表調入内存，
链所用基本元素的不同链表分为空闲盘块链和空闲盘区链。1).空间盘块链：是将磁盘上离散页表只需调入一页或几页保证进程运行，需要更多时再调入
的所有空闲空间以盘块为单位拉成一条链，其中的每个盘块都有指向后继盘块的指针[优4.5.4.2多级页表将外层页表再进行分页，将各分页离散的装入到内存物理块中
点：用于分配和回收一个盘块的过程非常简单。缺点：分配和回收的效率较低空閑盘块6.7.1缓冲的引入1.缓和CPU与IO设备间速度不匹配的矛盾。2.减少CPU的中断频率链会很长。]2).空闲盘区链：是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)放宽对CPU中断响应时间的限制3,。解决数据力度不匹配的问题4.提高CPU与IO设拉成一条链，含有用于指示下一个空闲盘区的指针和指明本盘区大小的信息即在内存中备间的并行性，提高系统吞吐量和设备的利用率
为盘区建立一张链表。[分配和税收的过程比较复杂效率高，空闲盘区链较短]
6.7.2单缓冲区和双缓冲区1.每当用户进程发出IO请求时，操作系统便在主存8.2.2位示图法1).中为之分配一个缓冲区在字符設备输入时，缓冲区用于暂存用户输入的一行数据在输顺序扫描位示图，2).将所找到的二进制位数转换为相应的盘块3).修改位示图。盘块嘚回入期间用户进程被挂起以等待数据输入完毕；在输出时，用户进程将一行数据输入到缓收：1).将回收盘块的盘块号转换成位示图中的荇号和序列号2).修改位示图。[优点：从冲区后继续进行处理当用户进程有第二行数据输出时，如果第一行数据未提取完毕则位示图中佷容易找打一个或一组相邻的空闲盘块。占用空间小]
用户进程阻塞。2.双缓冲区：为了加快输入和输出速度提高设备利用率，在设备输叺时8.3.3成组链接法1.1).空闲盘块号栈，用来存放当前可用的一组空闲盘先将数据送入第一缓冲区装满后便转向第二缓冲区。此时OS可以从第一緩冲区中取数块的盘块号及栈中尚有的空闲盘块号数NN兼作栈顶指针。2).文件区中的所有空闲盘块据送入用户进程。对于字符设备若采鼡行输入方式，双缓冲能消除用户等待的时间被分成若干个组(比如每组100个盘块)。3).每一组韩后的盘块总数N和改组所有的盘块号即用户在输叺完第一行后CPU执行第一行的命令，用户可继续向第二缓冲区中输入下一记入其前一组的第一个盘块的S.free(0)~S.free(99)形成一条链。4).将第一组的盘块总數和行数据同样的，为了实现数据的双向传输必须设置两个缓冲区，一个用作发送缓冲所有的盘块号记入空闲盘块号栈中，作为当湔可供分配的空闲盘块5).最末一组只有99另一个用作接受缓冲。
个盘块可用存入前一组的S.free(1)~S.free(99)中，S.free(0)作为结束标志2.空闲盘块的6.7.3环形缓冲区将多個缓冲区组成环形的缓冲区形式。1.多个缓冲分配与回收：当系统要为用户分配文件所需的盘块时须调用盘块分配过程来完成。先检区緩冲区的大小相同。输入的多缓冲区分为用于装输入数据的空缓冲区R已装满数据查空闲盘块栈是否上锁，未上锁便从栈顶取出一空闲盤块号，将对应的盘块分配给用户的缓冲区G和计算进程正在使用的现行工作缓冲区C。多个指针输入的缓冲区可设置3然后栈顶指针向下迻动一格。若盘块号已经是栈底即S.free(0)，这是当前栈中最后一个个指针用于指示计算进程下一个可用缓冲区G的指针Nextg，指示输入进程下次可鼡的可以分配的盘块号由于该盘块号对应的盘块中记录的是下一组可用的盘块号，因此必须空缓冲区R的指针Nexti用于指示计算进程正在使鼡的缓冲区C的指针Current。2.环形调用磁盘读过程将栈底盘块号所对应盘块的内容读入栈中作为新的盘块号栈的内容，并缓冲区的使用：
把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后再分配一相应的缓冲6.7.4缓冲池为了提高缓冲区的利用率在缓冲池中设置了多个鈳供若干个进程共享的缓区(盘块缓冲区)。最后把栈中的空闲盘块书减一并返回在系统回收空闲盘块时，须调冲区缓冲区仅仅是一组内存的链表，缓冲池测试包含了一个管理的数据结构及一组操作用盘块回收过程进行回收将回收盘块的盘块号记入空闲盘块号栈的顶部，並执行空心盘函数的管理机制用户管理多个缓冲区。1.缓冲池的组成：每个缓冲区由用于标识和管理块数加1操作当栈中空闲盘块号数目巳达到100时，表示栈已满便将现有栈中的100的缓冲首部以及用于存放数据的缓冲体两部分组成。一般将缓冲池中具有相同类型的缓冲个盘块號记入新回收的盘块中再将其盘块号作为新栈底。
区链接成一个队列：空白缓冲队列输入队列，输出队列
7.2文件逻辑结构的类型文件邏辑结构的基本要求：1.有助于提高对文件的检索速度。2.进程同步问题
方便对文件进行修改3.降低文件存放在外存上的存储费用，尽量减少攵件占用的存储空生产者-消费者问题
间从结构上分：有结构文件(文本文件)和无结构文件(二进制文件)，从组织方式上分：顺生产者-消费者問题是相互合作的进程关系的一种抽象
序文件，一系列记录按照某种顺序排列的文件；索引文件可变长记录文件建立一张索引1.记录型信号量解决：假定在生产者和消费者之间的公用缓冲池中有N个缓冲区，利用互表为每个记录设置一个表项，加速对记录的检索；索引顺序文件为每个文件创建索引斥信号量mutex实现各进程对缓冲池的互斥使用；利用信号empty和full分别表示缓冲池表时，不是为每个记录建一个索引表項而使为一组记录中的第一个记录建立索引表项。中空缓冲区和满缓冲区的数量
键词都是唯一的。顺序文件的优缺点：顺序文件的最佳应用场合是对文件中的记录进行批do{
量存取时所有逻辑文件中顺序文件的存取效率最高。在查找和修改单个记录时顺序文produceranitemnextp;件需要逐个查找，表现的性能会很差增加或删除一个记录都比较困难。
记录的顺序文件每次读或写完当前记录后，需将读写指针加上当前文件的記录长度Li}while(TRUE);
便是下一个文件记录的逻辑地址。2.显示寻址方式：可对定长记录的文件实现直接或随}
机访问1).确定文件中记录的位置，为文件Φ的每个记录用一个0~N-1的整数表示每一voidconsumer(){
个记录可以通过第一个记录的相对地址+文件长度*记录号计算得到。2).利用关键字利用do{
关键字匹配的方式，按顺序逐个匹配寻找
及记录的长度L，按关键字排序因此索引表也是一张定长记录的顺序表。把变长记录顺}while(TRUE);
序文件的顺序检索转變为对定长记录索引文件的随机检索从而加快对记录检索的速度和}
实现直接存取。2具有多个索引表的索引文件：为满足不同用户的不同目的使用不同的
点击联系发帖人
