武汉大学-操作系统期末考试复习笔记.doc

Chapter 1:导论计算机系统可以大致分为4个部分：硬件，操作系统，系统程序与应用程序，用户操作系统是配置在计算机硬件上的第一层软件，是对硬件的首次扩充，它位于硬件与其他 软件之间，是所有其他软件运行的基础。对操作系统的公认的定义：操作系统是一直在计算机上运行的程序（通常称为内核）操作系统是计算机系统中的一个 系统软件 ，它管理和控制计算机系统中的 硬件和软件资源 。裸机：没有配置软件的计算机，即计算机硬件虚拟机：覆盖了软件的机器最基本的操作系统类型有三种：批处理操作系统，分时操作系统，实时操作系统批处理系统：单道批处理系统，多道批处理系统在单处理机系统中，多道程序运行的特点是多道、 宏观上并行 和 微观上串行 。分时系统：时间片轮转，设置多路卡，（用户能在很短时间内获得响应）人机交互，共享主机，方便用户上机实时系统：系统能及时响应外部事件的请求，在规定的时间范围内完成对该事件的处理，并控制实时任务协调一致地运行。（响应时间由控制对象决定，可靠性高）在主机控制下进行的输入/输出操作称为_联机输入输出_操作。（联机批处理，脱机批处理，联机I/O，脱机I/O）作业是用户在一次解题或一个事务处理过程中要求计算机系统所做的工作集合，包括用户程序、所需的数据及命令等操作系统的4个基本特征：并发，共享，虚拟，不确定（并发和共享互为存在条件）计算机系统的两种运行状态：核心态（kernel mode），0，用户态（user mode）,1Chapter2：操作系统结构用户接口：命令行接口（联机命令接口，脱机命令接口）、批处理接口以及图形用户接口（GUI）系统调用（system calls）:系统调用在运行程序和操作系统之间提供接口运行程序和操作系统之间的参数传递有3种常用方法：寄存器中的参数传递，参数存在内存的一张表中表地址作为寄存器的参数传递，程序把参数压入栈由操作系统弹出系统调用的类型：大致可分为5类：进程控制，文件管理，设备管理，信息维护，通信系统调用与过程调用的区别：系统调用在核心态下运行，子程序在用户态下运行；系统调用通过中断机构进入以实现运行状态的改变，子程序直接调用不涉及运行状态改变系统结构：MS-DOS：以最小的空间提供最多的功能。不划分模块，其接口和功能层次没有划分清楚早起的UNIX：受硬件功能限制，由两个独立的部分组成，系统程序和内核内核包括了在物理硬件之上，系统调用之下的一切。内核通过系统调用提供文件系统、CPU调度、存储管理和其他操作系统功能操作系统分层：0层为硬件层，N层（最高层）为用户接口，每层都利用较低层的功能和服务，为较高层隐藏一定的数据结构、操作和硬件的存在层次结构：给模块赋予了层次顺序使调用关系变得有序，在上下两层不变的基础上可以换掉某层便于移植和扩充，但牺牲一定的灵活性为代价微内核：微内核通常包括最小的进程和内存管理以及通信功能微内核特点：降低了开发难度，具有较好的扩展性及可移植性，特别适合大规模开放式的分布系统。但是效率较低模块结构，将操作系统内核按照功能划分为一个个独立的模块，模块之间相对独立，只能通过事先规定好的接口方式来调用。每个模块实现一个完整独立的功能，所有模块之间相互调用，共同构成一个完整的系统内核。模块结构特点：效率高，但全局函数使用多造成访问控制困难，结构不清晰可理解性可维护性可移植性差宏内核：在运行过程中，它是一个独立的进程。模块结构、层次结构的系统内核基本都是宏内核微内核：大部分内核模块都作为独立的进程，它们之间通过信息通信使模块之间互相提供服务。Chapter3 进程进程的顺序执行：程序通常由若干个程序段所组成，它们必须按照某种先后次序来执行，仅当前一个操作执行完后才能执行后继操作顺序执行的特征：顺序性，封闭性（一旦开始运行结果不受外界影响），可再现性（执行情况相同重复执行获得相同结果）程序的并发执行：若干程序或程序段同时在系统中运行并发执行的特性：间断性，失去封闭性（进程共享资源），不可再现性Bernstein条件：能保证两个程序段并发执行而不会产生与时间有关的错误（全局变量的改变什么的）R（Si） W（Sj）= 这两条保证R（Sj） W（Si）= 两次读之间数据不变W（Si） W（Sj）= 本条保证写操作结果不丢考虑下面是条语句：S1：a=x+y S2：b=z+1S3：c=a-b S4：d=c+1R(S1)=x,y R(S2)=z R(S3)=a,bW(S1)=a W(S2)=b W(S3)=c因R(S1) W(S2)R(S2) W(S1)W(S1)W(S2)= ，故S1和S2可以并发执行 。 因R(S2) W(S3)R(S3) W(S2)W(S3)W(S2)=b，故S2和S3不能并发执行 。并发语句描述：cobegin .coend进程：进程是执行中的程序。一个进程包括，代码段，程序计时器和处理机寄存器内容，栈，数据部分进程的特征：动态性（进程是动态存在和消失的而程序是静态实体），并发性（多个进程实体同时在内存并能在一段时间内同时发生），独立性（进程是独立运行的基本单位），异步性（进程各自以独立的不可预知的速度向前推进），结构性（由很多段组成(程序段，数据段，控制块)）进程状态：新建，运行，等待，就绪，终止通常一个进程至少应有以下三种基本状态：就绪状态，执行状态（运行），阻塞状态（等待状态通常是I/O请求）进程由PCB，程序段，数据段 三部分组成进程控制块（PCB,process-control-block）：每个进程在操作系统内用进程控制块表示。PCB是描述和管理进程的数据结构。它是进程实体的一部分，操作系统通过PCB感知进程的存在，PCB是进程存在的唯一标志。进程的挂起状态：（由于系统故障，检查，资源内存不足等原因）人为将进程挂起使之处于静止状态。/*进程调度*/作业队列：系统中所有进程的集合就绪队列：内存中就绪并等待执行的所有进程的集合（常用链表实现）设备队列：等待某I/O设备的进程队列长程调度（作业调度）：选择可以进入就绪队列的进程短程调度（CPU调度）：选择下一个执行并分配CPU长程调度（作业调度）的频率相对低，长程调度控制了多道进程可以分为：I/O型进程，和CPU型进程上下文切换：将CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态，这个任务称为上下文切换原语：原语是由若干条机器指令构成的，用以完成特定功能的一段程序，实现对进程的管理和控制。这段程序在执行期间不可分割（原语不允许被中断。不同层次之间的对话的语言称为原语）种类：创建原语，撤销原语，阻塞原语，唤醒原语，挂起原语，激活原语.进程创建：通过创建进程系统调用可以创建多个新进程，创建进程称为父进程，被创建进程称为子进程。每个新进程可以再创建新进程，从而形成了进程树。进程树又称为进程图或进程家族树有的系统中，若父进程终止不允许子进程继续，这种现象称为：级联终止进程的组织：线性方式，链接方式（链表方式），索引方式进程通信：进程之间的信息交换低级进程通信方式：进程互斥与同步交换的信息量较少且效率较低。P、V操作是一种低级进程通信原语高级进程通信方式：进程之间以较高的效率传送大量数据高级进程通信方式分为三大类：共享存储器系统，消息传递系统，管道通信系统或共享文件系统共享存储器系统：相互通信的进程共享某些数据结构或共享存储区消息传递系统：进程间的数据交换以消息为单位，程序员直接利用系统提供的一组通信命令（原语）来实现通信。消息传递系统因其实现方式不同可分为：直接通信方式（讲消息直接发在接受进程的消息队列上），间接通信方式（将消息发送到信箱）管道（共享文件）通信：通过连接读进程和写进程的共享文件来实现读写进程之间通信缓冲(Buffering) ：通信进程交换的信息都驻留在临时队列中，队列实现有三种形式，零容量（发送者必须等待接受者），有限容量（线路满则发送者必须等待），无限容量（发送者无需等待）管道：使用管道通信时，基本上采用文件系统的原有机制实现。包括创建、打开、关闭、读写等。管道机制应提供以下三方面的 协调能力：互斥（互斥读写管道），同步（管道空满情况处理），存在（确定对方是否存在）在单处理机计算机系统中，如果有N个进程（只考虑等待，就绪，运行）那么运行状态最多1个，最少0个；等待状态最多N个，最少0个；就绪状态最多N-1个，最少0个。Chapter 4 线程在操作系统中引入进程的目的是：使用多道程序能并发执行，以改善资源利用率及提高系统吞吐量在操作系统中引入线程的目的是：减少程序并发执行的时空开销，使操作系统有更好的并发性线程是CPU使用的一个基本单元，包括线程标识（thread ID），程序计数器（PC），寄存器集（register set），栈（stack）线程自己基本上不拥有资源，只拥有一点在运行时必不可少的资源（如程序计数器、寄存器集和栈）。但它可以与同属一个进程的其他线程共享进程拥有的全部资源线程与属于同一进程的线程共享：代码段，数据段，其他操作系统资源线程的状态，同步与通信与进程类似进程的挂起及终止将影响到其中所有进程线程的优点：响应能力强（即使进程的一块被阻塞了，其他部分也能运行），资源共享，经济性，多处理器体系结构的利用，创建撤销切换时间短，共享内存和资源线程间通信方便多线程模型操作系统中有多种方式实现对进程的支持：内核线程（kernel Threads），用户线程（User Threads）的组合实现内核线程：也称内核级线程，是指依赖于内核，由操作系统内核完成创建和撤销工作的线程。一个内核线程的阻塞不会影响其他线程的运行。处理机分配的对象是线程，所以有多个线程的进程将获得更多的处理机时间用户线程：也称用户级线程，是指不依赖于操作系统核心，由应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制的线程用户线程的维护由应用进程完成，可以用于不支持线程的操作系统当一个线程阻塞时，整个进程都必须等待。处理机时间是分配给进程的，进程内有多个线程时，每个线程的执行时间相对少一点用户线程与内核线程的关系多对一模型：将多个用户线程映射到一个内核线程。线程管理由线程库在用户空间进行。用于不支持内核线程的系统中（只有一个内核线程，相当于没有）一对一模型：将每个用户线程映射到一个内核线程。这种模型的绝大多数实现限制了系统支持的线程数量多对多模型：多个用户线程到同样数量或更少的内核线程上多线程问题：线程取消可以再一下两种情况下发生：异步取消（一个线程立即终止目标进程），延迟取消（目标线程不断检查它是否应该终止）线程与进程的比较：从调度的基本单位，拥有资源的基本单位，并发性，和系统开销四个方面说。Chapter5 CPU调度处理机的三级调度：作业调度，进程调度，交换调度作业调度：又称长程调度，宏观调度和高级调度，从外存上处于后备状态的作业中选择一个或多个作业，给他们分配内存、I/O设备等必要资源，并建立相应的进程，使该作业具有获得竞争处理机的权利作业调度的运行频率低，通常几分钟一次进程调度：又称短程调度，微观调度和低级调度，从就绪队列中选取一个进程，将处理机分配给它。进程调度的运行频率很高，一般十几毫秒就要运行一次交换调度：又称中程调度，中级调度，将内存总暂时不用的信息移到外存，以腾出空间给内存中的其他进程使用，或将需要的信息从外存读入内存。交换调度的目的是，提高内存利用率和系统吞吐量交换调度的运行频率介于上面两者之间作业：是用户在一次解题或一个事务处理过程中要求计算机系统所做的工作的集合，包括用户程序、所需的数据及命令等作业从提交到完成要经历四种状态：提交状态，后备状态（将作业插入后备作业队列中等待调度运行），运行状态（作业在内存中执行），完成状态作业控制块（JCB，job control block）：系统通过JCB感知作业的存在，JCB是作业存在的唯一标志一个作业可以分成若干顺序处理的加工步骤，每个步骤称为一个 作业步多道程序的设计目标在于任何时候都有某些进程运行，使CPU利用率最大化。CPU调度可能发生如下4种情况从运行状态转到等待状态从运行状态转到就绪状态从等待状态转到就绪状态进程终止1,4两种情况的调度称为非抢占调度，2，3两种情况的调度称为抢占式调度进程调度的两种方式：抢占方式，非抢占方式抢占方式：又称波多方式。抢占原则有，优先权，时间片分派程序：用来将对CPU的控制交给由短程调度程序选择的进程分派延迟：分派程序终止一个进程的运行并启动另一个进程运行所花的时间，也成为调度时间调度准则：CPU利用率吞吐量（单位时间内运行完的程序数）周转时间（进程从提交到运行结束的全部时间等待时间（进程在就绪队列中等待调度的时间总和）响应时间（从提交请求到系统首次产生响应所用的时间）带全周转时间（作业周转时间与作业实际运行时间的比）调度算法:（画图用到gantt图）FCFS 先来先服务调度，适用于作业调度，进程调度算法简单易于实现，不适用与短作业和I/O繁忙的作业SJB 最短作业优先（抢占/非抢占）适合短作业，对长作业不利，运行时间为估计抢占SJB调度有时称为最短剩余时间优先调度，若到达新进程的CPU区间短于当前运行进程的剩余时间，则它将抢占CPU。可能有饥饿优先级调度（抢占/非抢占）优先级的类型：静态优先级，动态优先级（确定原则：占用CPU时间，等待时间）存在的问题：饥饿，低优先级的进程可能永远得不到运行解决方法：老化，视进程等待时间的延长提高其优先级数时间片轮转调度（RR）每个进程得到小单位的CPU时间，称为时间片，通常为10-100毫 秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。时间片大小：太大：退化为FCFS 太小：调度频繁系统开销大。现代操作系统的时间片一般为10-100ms，上下文切换时间一般少于10us。确定时间片大小应考虑的因素：系统对响应时间的要求：响应时间=时间片*进程数就绪队列中的进程数目：时间片应与就绪进程数成反比系统的处理能力：考虑响应时间在可承受范围内，系统速度快则时间片可以增长时间片轮转算法的特点及改进：虚拟时间片轮转法（针对偏重I/O的进程）：新进程基于FCFS进入就绪队列，进程用完时间片后也进入就绪队列，进程因I/O阻塞进入I/O队列，I/O完成时进程进入附加队列，附加队列的优先级高于就绪队列，当进程从附加队列被调度时，其运行时间不超过上次发生中断时剩余的时间。高响应比优先调度算法 响应比1作业等待时间/估计运行时间多级队列调度将就绪队列分为多个独立队列，每个队列有自己的调度算法，根据进程属性，一个进程被永久分配到一个队列例如分为前台（交互式）RR算法，和后台（批处理）FCFS。前台的优先级高多级反馈队列调度进程能在不同的队列间移动。如果进程使用过多的CPU时间，那么它会被移动到更低优先级队列。此外，在较低优先级队列中等待时间过长的进程会被移到更高优先级队列每个队列有不同优先级，第一队列最高，其余递减，每个队列的时间片大小也各不相同，优先级高的队列时间片短。当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列中使用时间片轮转调度算法。仅当第1个队列为空时，调度程序才调度第2队列中的进程运行；仅当第1个至第（i1）个队列均为空时，才会调度第i个队列中的进程运行。当处理机正在为第i个队列中的某进程服务时，若又有新进程进入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行进程放回第i个队列末尾，重新将处理机分配给新进程。多级反馈队列调度算法能较好满足各类用户的需求公平分享调度算法：基于进程组来分配CPU时间，其实现思想是对系统中的每个用户赋予某种权值，根据用户权值大小，按比例分配处理机时间。进程切换：在操作系统中凡是要进行中断处理和进程调度时，都将涉及到进程上下文的保存的恢复。中断时：系统保存和恢复的是同一个进程的上下文进程调度时恢复的是调度程序所选中进程的上下文既考虑作业等待时间，又考虑作业执行时间的调度算法是 响应比高优先调度Chapter 6 进程同步进程同步：系统中各进程之间逻辑上的相互制约关系叫做进程同步在多道程序系统中，进程之间存在着的不同制约关系可以划分为两类：同步和互斥同步指进程间具有的一定逻辑关系；互斥是指进程间在使用共享资源方面的约束关系。临界区问题：每个进程有一个访问共享数据的代码段，称为临界区（critical section）。需保证一个进程在其临界区执行时，不允许其他进程在其临界区执行。临界资源：一段时间内仅允许一个进程使用的资源称为临界资源。如打印机，共享变量同类临界区：所有与同一临界资源相关联的临界区临界区问题的解决应满足：互斥，前进（如果没有进程在其临界区内执行，且有进程需要进入临界区，那么只有不在剩余区执行的进程可以参加选择，以确定下一个进入临界区的进程，且选择不能无限期延长），有限等待（在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区的次数必须是有限的）访问临界资源应遵循的原则：空闲让进，忙则等待，有限等待，让权等待（当进程不能进入自己的临界区时，应释放处理机）Peterson算法 enum boolean false，true；boolean flag2 false，false； int turn；P0： do flag0true； turn1； while （flag1 & turn = = 1）；/实现互斥，前进 进程P0的临界区代码CS0 ； flag0false ； 进程P0的其他代码； while (true) P1： do flag1true； turn0； while （flag0 & turn = = 0）； 进程P1的临界区代码CS1 ； flag1false ； 进程P1的其他代码； while (true) 硬件同步：用硬件方法实现互斥的主要思想是保证检查操作与修改操作不被打断禁止中断方法：当进程执行临界区代码时，禁止中断(很多缺点)硬件指令方法用TS实现互斥： boolean TS(boolean *1ock) boolean old； old=*lock； *lock=true； return old； while TS(&lock)；/lock=1的话，陷入while；lock=0的话，将lock置1，进入临界区 临界区代码 Critical Section ； lock=false ； 其他代码 remainder section； 用swap指令实现进程互斥：/swap(a,b)交换两值 key=true； while(key！=false)Swap(&lock，&key)；/如果lock=true，不停的swap，直到lock=false，进入临界区 临界区代码 Critical Section ； lock=false ； 其他代码 remainder section； 用锁机制实现互斥（自旋锁）lock（w） while（w=1）； w = 1； unlock（w） w = 0； 进程P1 进程P2 lock(w)； lock(w)； 临界区； 临界区； unlock(w)； unlock(w)； 这一页的方法都不能实现让权等待，即存在忙等待信号量：信号量S是个整型变量，除了初始化外，它只能通过两个标准原子操作wait()和signal()来访问。wait (S) signal (S): while S 0 do no-op; S+; S-; Wait是原来的P操作Signal是原来的V操作当进程需要使用资源时则对信号量执行wait，当释放资源时执行signal互斥信号量的实现信号量由两个成员（s，q）组成，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。又称信号灯。除信号量的初值外，信号量的值仅能由P操作（又称为wait操作）和V操作（又称为signal操作）改变。wait (semaphore *s)s-value-;if (s-value list;/如果所有资源都被占用，加入等待队列，if里的value是被减过的。如果等于0，那么value被减过之前是1，有资源，就不用等待了 block(); signal (semaphre *s) s-value+;if (s-value list; wakeup(P); 信号量中的整型变量S表示系统中某类资源的数目。当其值大于0时，表示系统中当前可用资源的数目；当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。P，V操作类似P，V操作是原语利用信号量实现互斥设S为两个进程P1、P2实现互斥的信号量，S的初值应为1（即可用资源数目为1）。只需把临界区置于P（S）和V（S）之间，即可实现两进程的互斥。死锁：两个或多个进程无限等待一个事件的发生，而该事件正是由其中一个的等待进程引起的。饥饿：无限期的阻塞。进程可能永远都无法从它等待的信号量队列中移去经典同步问题：有限缓冲问题 生产者消费者问题它描述了一组生产者进程向一组消费者进程提供产品，它们共享一个有界缓冲池。缓冲池中的每个缓冲区可以存放一个产品，生产者进程不断生产产品并将产品放入缓冲池中，消费者进程不断从缓冲池内取出产品并消费。设置两个同步信号量empty、full，其初值分别为n、0。/empty代表缓冲区空的区域个数，full代表缓冲区被填充的区域个数 mutex是确保对缓冲区的访问互斥的信号量，初值为1无论在生产者进程还是在消费者进程中，P操作的次序都不能颠倒，否则将可能造成死锁。读者-写者问题第一读者-写者问题：要求没有读者需要保持等待除非有一个写者已经获得允许使用共享数据第二读者-写者问题：一旦写者就绪，不会有新读者开始读操作用信号量解决读者-写者问题：目标：允许多个读进程同时读此数据对象，但是一个写进程不能与其他进程（不管是写进程还是读进程）同时访问此数据对象互斥信号量mutex,初值1, 共享变量readcount 记录当前读进程数，初值0，写互斥信号量writer，用于实现写进程与写进程和读进程的互斥，初值为1读者： p(mutex)； if (readcount=0) p(writer)；/如果没有读者访问，则等待写者的完成。如果有读者，则直接访问临界区 readcount=readcount+1； v(mutex)； 读数据集； p(mutex) ； readcount=readcount-1 ； if (readcount=0) v(writer)；/所有人读完才能写 v(mutex)；Mutex用于保护readcount的互斥访问哲学家进餐问题：第i个哲学家活动算法描述： p(sticki)； p(stick(i+1) % 5)； 进餐； v(sticki)； v(stick(i+1) % 5)； 思考；可能会死锁解决方法：至多允许四个哲学家同时进餐。仅当左、右两支筷子均可用时，才允许拿起筷子进餐。奇数号哲学家先拿左筷子再拿右筷子，偶数号哲学家相反。睡眠的理发师问题理发店里有一位理发师，一把理发椅和N把供等候理发顾客坐的椅子。如果没有顾客，理发师睡眠，当一个顾客到来时叫醒理发师；若理发师正在理发时又有顾客来，那么有空椅子就坐下，否则离开理发店。为解决睡眠的理发师问题，应使用三个信号量：customers记录等候理发的顾客数（不包括正在理发的顾客）；初值为0barbers记录正在等候顾客的理发师数；初值为0mutex用于互斥。初值为1变量count记录等候的顾客数，它是customers的一份拷贝。之所以使用count是因为无法读取信号量的当前值。理发师：p(customers)；/*是否有等候的顾客*/ p(mutex)； count=count1；/*顾客数减1*/v(barbers)； /*理发师开始理发*/ v(mutex)； 理发；顾客： p(mutex)； if(count N） count=count+1 v(customers)； v(mutex)； p(barbers)； 理发； else v(mutex)； /*无空椅子则离开*/Chapter 7 死锁死锁：是指多个进程因竞争系统资源或相互通信而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进可剥夺资源：某进程获得这类资源后，该资源可以被其他进程或系统剥夺，如CPU，存储器非剥夺资源：系统将这类资源分配给进程后，再不能强行收回，只能在进程使用完后主动释放。如打印机、读卡器注：竞争可剥夺资源不会产生死锁。永久性资源：可顺序重复使用的资源，如打印机消耗性资源：由一个进程产生，被另一个进程使用短暂时间后便无用的资源，又称为临时性资源。如消息注:竞争永久性资源和临时性资源都可能产生死锁死锁产生的原因：竞争资源，进程推进顺序不当死锁发生的条件：互斥，占有并等待，非抢占，循环等待（等待资源的进程间存在环）通过资源分配图来观察进程是否发生死锁如果资源分配图没有环，系统就没有进程死锁。如果分配图有环，那可能产生死锁有死锁的资源分配图： 有环但没有死锁的资源分配图图中P1占有R2的一个实例 可知P4释放资源后就不会死锁P1申请并等待R1的一个实例处理死锁的基本办法：忽略思索，预防死锁，避免死锁，检测死锁及解除避免死锁：1. 打破占有并等待，要求进程在执行前一次申请全部的资源，或只有没有占有资源时才可以分配资源。导致资源利用率低，可能出现饥饿2. 破坏非抢占条件，如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占。缺点：实现复杂，释放已获得资源可能造成前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。该协议通常应用于状态可以保存和恢复的资源，如CPU寄存器、内存3. 破坏循环等待：有序资源分配法;将所有资源按类型排队，并赋予不同序号，要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。能保证没有死锁安全状态：系统能按某种顺序如来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利完成为安全序列银行家算法：（举例）T0时刻存在着一个安全序列，故系统是安全的。资源分配图简化判断是否死锁：找出一个既不阻塞又非孤立的进程结点pi，进程pi获得了它所需要的全部资源，能运行完成然后释放所有资源。如果能消去所有边，则不死锁资源抢占来处理死锁：逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止。选择一个牺牲：最小代价回退：返回到安全状态，然后重新启动进程饥饿：同一进程可能总是被选中处理死锁的综合方法：将系统中的资源按层次分为若干类，对每一类资源使用最适合它的办法解决死锁问题。即使发生死锁，一个死锁环也只包含某一层次的资源，因此整个系统不会受控于死锁。把资源分为：内部资源（有序资源分配法），主存资源（资源剥夺法），作业资源（可分配的设备和文件采用避免方法），交换空间（静态分配法）对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于 避免 ，破坏环路等待条件是属于 预防 ，而剥夺资源是 解除 的基本方法Chapter 8 内存管理内存：即存储器、主存，分为两大部分：系统区，用户区内存由很大一组字或字节组成，每个字或字节都有它们自己的地址存储器管理的功能存储空间的分配和回收地址变换：将逻辑地址变换成物理地址存储保护：防止因用户程序错误破坏系统或其他用户，防止程序之间的相互干扰存储扩充：在逻辑上为用户提供一个比实际内存更大的存储空间CPU能直接访问的存储器有：主存，高速缓存和寄存器将程序装入内存有三种方式:绝对装入方式（编译时产生绝对地址的代码无需地址变换），可重定位装入方式（编译时产生相对地址的目标代码），动态运行时装入方式（执行时进行地址变换）逻辑地址：由CPU产生的地址。用户编程时所用的地址，又称相对地址、虚地址物理地址：内存单元所看到的地址。又称绝对地址，实地址逻辑地址空间：逻辑地址的集合物理地址空间：物理地址的集合为了确保每个进程都有独立的内存空间。基地址寄存器，界限地址寄存器 300040 120900那么程序可以访问300040-420900的所有地址内存管理单元（MMU， memory-management-unit）:运行时把虚拟地址映射到物理地址的设备。在MMU中，用户进程所产生的地址在送交内存前都将加上重定位寄存器的值地址变换：将逻辑地址转换为物理地址。又称地址映射、重定位地址变换分两类：静态地址变换（程序装入时一次完成不改变，需要连续存储空间，难共享），动态地址变换（在程序执行过程中，每次访问内存之前将要访问的地址转为内存地址，不需连续空间，可以实现虚拟存储）动态加载：子程序只有调用时才被加载。优点：不用的子程序不会被加载动态链接：链接被推迟到执行时期存根：小段代码用来定位合适的内存驻留库程序程序的链接：链接程序的功能是将经过编译或汇编后得到的目标模块以及所需的库函数装配成一个完整的装入模块实现链接的三种方式：静态链接，装入时动态链接，运行时动态链接静态链接：在程序运行之前，将各目标模块及其所需的库函数装配成一个完整的装入模块装入时动态链接：源程序编译后所得到的目标模块在装入内存时边装入边链接。运行时动态链接：将某些目标模块的链接推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存并链接到调用者模块上。覆盖技术：把一个大程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位。把程序执行时不要求同时装入内存的覆盖组成一组叫覆盖段。将一个覆盖段分配到同一个存储区中，这个存储区称为覆盖区。覆盖区的大小由覆盖段中最大的覆盖确定。覆盖技术主要在早期系统使用，要求专业的程序员给出覆盖结构。交换：进程可以暂时从内存中交换到备份存储上，当需要再次执行时再换回内存。（例如低优先级内存被换出，这样高优先级进程可以装入执行。这种交换又被称为滚出，滚入）交换空间管理：交换空间设置在外存交换区，交换空间管理的主要目标是提高交换速度交换空间采用连续分配方式，使用与动态分区分配类似的数据结构和分配算法交换技术由操作系统自己完成连续内存分配内存通常分为两个区域：一个驻留操作系统，通常位于内存低端；一个驻留用户进程，通常位于内存高端内存保护：防止一个进程有意无意的破坏系统或其他进程（内存访问不能越界）常用的存储保护方法：界限寄存器法，存储保护键，环保护机制，访问权限界限寄存器法：通过对每个进程设置一对界限寄存器（上下界寄存器或基址限长寄存器）来防止越界访问（如果越界则产生越界中断），达到存储保护的目的。存储保护键：为每个存储块分配一个保护键，相当于一把锁；进入系统的每个作业赋予一个保护键，相当于一把钥匙。当作业运行时，检查钥匙和锁是否匹配，若二者匹配，则允许访问。否则发出保护性中断信号环保护机制：处理器状态分为多个环，分别具有不同的存储访问特权级，通常环的编号越小，特权级越高。存取权限：除上述保护方案外，还有四种存取权限：禁止做任何操作，只能执行，只能读，读/写内存分配:分区储存管理分为：固定分区，动态分区分区分配算法：首次适应算法，循环首次适应算法（从上次找到的空闲分区的下一个开始，使存储空间利用均衡），最佳适应算法（分区按容量递增的次序排列），最坏适应算法（分区按容量大小递减）模拟实验显示，首次适应和最佳适应难分伯仲，但是首次适应快内部碎片：分配给作业的存储空间中未被使用的部分外部碎片：系统中无法利用的小存储块（ 因为它们太小了）解决碎片的方法：拼接/紧缩，要浪费很多的处理机时间分页：将物理内存分为固定大小的块，称为帧。将逻辑内存也分为同样大小的块，称为页。在为进程分配存储空间时，总是以块为单位来分配，可以将进程中的某一页存放到主存的某一空闲块中。分页没有外部碎片，有内部碎片页的逻辑地址由页号和页内位移（page offset）组成页的大小一般为512B-8KB页表：记录页面在内存中对应物理块的数据结构分页机制中，每一次的数据/指令存取需要两次内存访问（一次页表一次数据）TLB（translation look-aside buffer）转换后备缓冲区，即快表，存放当前访问的那些页表项TLB失效：页号不在TLB内，则访问页表如果TLB中的条目已满，则需要替换，替换策略有LRU（最近最少使用），随即替换等。有的TLB允许有些条目固定下来TLB命中率：一般80%-90%有效内存访问时间：如果内存一次存取时间是m，TLB访问一次时间是n，命中率为p。那么有效内存访问时间=p*(n+m)+(1-p)(2m+n)存储保护有效-无效位(valid-invalid bit):附在页表的每个表项中。当该位有效时，表示相关的页在进程的逻辑地址空间内，是合法的。反之不合法共享页：如果代码是可重入代码（reentrant code纯代码）则可以共享（每个进程可以有自己的数据页，但可用同一段代码，访问内存的同一块）可重入代码是不能自我修改的代码，它在执行期间不会改变分段（segmentation）：（考虑程序的逻辑完整性）一个程序是一些段的集合，一个段是一个逻辑单位。如一个程序可分段为：代码，全局变量，堆，每个线程的栈等每个分段有自己的名字，由0开始编址并采用一段连续的地址空间。每段分配一个连续的内存区，但各段之间不要求连续段表，类比页表分段不会产生内部碎片三种不连续内存管理方式是： 分页存储管理 、 分段存储管理 和 段页式存储管理 （访问两次内存）。Chapter9 虚拟内存虚拟内存技术：允许执行进程不必完全在内存中。是一种以时间换空间的技术虚拟存储器的特征：离散型（不连续内存分配），多次性（一个作业多次装入内存），对换性（允许运行中换进换出），虚拟性（逻辑上扩充内存）按需调页：只有在需要的时候才调入一个页（懒惰交换）页错误:当访问无效页时，会产生页错误陷阱.分页硬件在通过页表转换地址时，将发现已设置了无效位，会陷入操作系统。缺页中断:缺页中断处理程序根据该页在外存的地址把它调入内存。若内存有空闲空间，则缺页中断处理程序只需把缺页装入并修改页表中的相应项；若内存中无空闲物理块，则需要先淘汰内存中的某些页，若淘汰页曾被修改过，则还要将其写回外存。有效访问时间：内存的读写周期为t，缺页中断服务时间为tl（包含读入缺页、页表更新、快表更新时间）， 快表的命中率为，缺页中断率为f，快表访问时间为，则有效存取时间可表示为：EAT= *( +t )+(1- )* (1-f) *2 ( +t ) +f*(tl+ 2 (+t ) )（里面包括了查快表时间）页面置换（页面淘汰）：为进程分配的帧越多，页错误越少内存的引用序列称为引用串（reference string）采用如下引用串讨论页置换算法：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1（分配3个可用帧）先进先出置换算法（FIFO）(会有15次页面错误)（注：计算页面错误时，注意前三个必产生3个页面错误）Belady异常：页错误率可能随分配的帧数的增加而增加最优置换（OPT算法/MIN算法）（不会有belady异常）产生的页错误率最低置换最长时间不会用到的页（看未来）难实现LRU页置换 最近最少使用算法。可以画栈看会有多少页面错误近似LRU算法：附加引用位算法（被使用过就标记1并添置高位（前八位）舍弃最后一位），二次机会算法，增强型二次机会算法基于计数的页面置换：最不经常使用算法（LFU），最常使用页置换算法（MFU）页面缓冲算法：页面缓冲算法是FIFO算法的发展。它在系统中保存一个空闲帧缓冲池。页面缓冲置换算法采用FIFO选择被置换页面，选择出的页面不是立即换出，而是放入空闲帧池。帧分配帧的最小数量：分配的帧要大于最少数量（不然产生太多的页面错误）分配算法：平均分配，比例分配（根据进程大小，将可用的帧分给每个进程），按优先级分配全局分配与局部分配固定分配和可变分配将分配策略和置换范围组合可得如下三种策略：固定分配局部置换可变分配全局置换可变分配局部置换颠簸/抖动：频繁的页调度行为而几乎不能完成任何有效的工作。如果一个进程在换页上用的时间多于执行的时间，那么这个进程就在颠簸。Chapter 10 文件系统接口文件系统：操作系统中与管理文件有关的软件和数据的集合。文件系统负责管理外存上的文件，并为用户提供对文件进行存取、共享及保护的手段。文件是具有文件名的一组相关信息的集合，文件存放在外存上的。文件由若干记录组成。记录是一些相关数据项的集合。数据项是数据组织中可以命名的最小逻辑单位。文件属性包含：名称，标识符，类型，位置，大小，保护，时间日期和用户标识所有的文件的属性信息都保存在目录结构中通常目录项包含文件名及标识号，而标识号定位文件其他属性信息。文件操作：建立，删除，读，写，打开，关闭（文件的操作除了正常的访问之外，还要包括对目录项的操作）在文件内重定位：搜索相应的目录表项，设置当前文件指针给定值文件类型：实现文件类型的常用技术是在文件名称内包含类型：如名称.扩展名文件分类方法按用途分类：系统文件（系统软件构成的文件），库文件（系统提供给用户使用的各种标准过程、函数和应用程序），用户文件（用户委托文件系统保存的文件）按保护级别分类：只读文件，读写文件，执行文件（允许核准用户调用执行，但不允许读写），不保护文件（不加任何访问限制）按信息流向分类：输入文件（来自输入设备的文件），输出文件，输入输出文件（如磁盘上的文件，可以读也可以写）按数据形式分类：源文件（由源程序和数