操作系统复习

第1章操作系统特性 并发性:多个程序在宏观上同时向前推进 共享性:1.多个程序共用系统中的各种软硬件资源2.在操作系统的协调和控制下异步行（随机性）:多个程序以不可预知的速度向前推进 虚拟性（通过分时实现）;通过某种技术把一个物理实体变为若干个逻辑上的对应物 操作系统的分类多道批处理系统：内存中同时存放多个相互独立的程序 分时操作系统;一台主机连接了多个终端（输入输出设备），同时允许多个用户通过自己的终 端，以交互的方式使用计算机，共享主机资源。实时操作系统:及时响应外部事件请求（响应时间远远小于分时系统）第2章进程：进程是进程实体的运行过程，是系统进行资源分配和调度的基本单位。它强调两个方面：动态（执行中的程序）; 并发（可与其他进程同）进程的状态：（1）运行态（RUN）:占有CPU正在向前推进（2）就绪态（READY）:可以运行，但未得到CPU；已分配到了处理机以外的所有必要资源，多个进程组成就绪队列。（3）等待态（WAIT）:正在执行的进程由于发生某事件而暂时无法继续执行，放弃处理机（自己阻塞自己，比如请求I/O,申请缓存）进程状态状态改变的原因：就绪一运行：进程调度，获得处理机运行一就绪：剥夺处理机（如时间片用完）运行一等待：申请资源未得到等待一就绪：得到资源PCB中的信息组织方式：（1）链接方式：同一状态下的PCB，用其中的链接字链接成一个队列，如就绪队列、等 待队列。（2）索引方式： 建立就绪索引表、阻塞索引表等。把索引表在内存中的首地址放在内 存的专用单元中。（地址集合时执行 引起创建进程的事件：1. 用户登录 2. 作业调度 3.提供服务 （系统内核创建） 4.应用请求 （ 自己创建子进程） 引起进程终止的事件:（1）正常结束（2）异常结束（越界，算术，非法指令，超时，保护错，I/O故障）（ 3）外界干预（操作员干预，父进程终止）作业：用户要求计算机系统为其完成的计算任务的集合。（作业中一个相对独立的处理步骤 称为一个作业步）作业的状态：（ 1）提交状态（ 2）后备状态（ 3）运行状态（ 4）完成状态第3章：处理器调度1. 一个批处理型作业，从进入系统并进入在外存的后备队列上开始，直至作业运行完毕，可 能要经历三级调度：高级调度、 中级调度、低级调度。高级调度，又称为作业调度、长程调度、接纳调度 作用：把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配资源、排在就绪 队列上、准备执行。适用于批处理系统 中级调度，又称为中程调度。目的：提高内存利用率和系统吞吐量 作用：使暂时不能运行的进程从内存调至外存，进入就绪驻外存状态或挂起状态。把外存上 又具备运行条件的进程，重新调入内存，并修改为就绪状态，挂在就绪队列上。称为对换。 低级调度，也称为进程调度、短程调度，作业决定就绪队列中的哪个进程应获得处理机，然 后由分派程序执行把处理机分配给该进程的具体操作，所有OS中都必须配置的2. 进程调度的两种方式：（1）非抢占方式，一旦处理机分配给某进程后，便让其一直执行，直至完成或等待时，才把 处理机另外分配（2）抢占方式，允许暂停某个正在执行的进程，将已分配给该进程的处理机重新分配3. 抢占原则：（1）优先权选（2）短作业优先（3）时间片原则（分时系统）4. 几个参数的计算 周转时间：从作业提交给系统开始，到作业完成为止的时间间隔。周转时间：完成时间-进入时间 平均周转时间：周转时间的平均值 带权周转时间：周转时间/运行时间（占有处理机的时间） 平均带权周转时间：带权周转时间的平均值 响应时间：从用户通过键盘提交一个请求开始直至系统首次产生响应为止的时间间隔 截止时间：指某任务必须开始执行的最迟时间，或必须完成的最迟时间。 吞吐量：单位时间内系统所完成的作业数。评价批处理系统的重要指标。6几种算法：（P 61）先到先服务算法（FCFS）按照进程申请CPU的次序，即进入就绪状态的次序来调度。优点：“公平”；既适用于作业调度也可用于进程调度；有利于CPU繁忙型（科学计算） 缺点:短作业等待时间长；不利于I/O繁忙型最短作业优先（SJF）：按照CPU阵发时间递增的次序调度，易于证明平均周转（等待）时间最短。最大程度降低了平均等待时间，但是也带来了不公平性：一个较长的就绪任务可能由 于短作业的不断到达而长期得不到运行机会，发生饥饿，甚至被饿死。高响应比优先算法（HRN）是先到先服务算法和最短作业优先算法的折中。优先权=（等待时 间+服务时间）/服务时间RR表示响应比BT为阵发时间WT为等待时间，响应比，响应比越 高，优先权更高。最高优先数/权优先（HPF）：优先权调度算法的类型：（1）非抢占式（用于批处理系统和某些对实时性要求不严的系统） （2）抢占式（更好的完成紧迫作业要求，用于要求比较严格的实时系统）优先权的类型：（1）静态（创建进程时确定，运行期间不变；确定依据：系统进程高于用户，要求资源较 少的，用户要求） 简单，开销小，但是不够精确。（2）动态（随进程推进或等待时间增加 而改变）7.周期性实时事务：每隔固定时间发生一次，假设系统中有M个周期性硬实时任务，令Ci 为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,Pm可调度的 必要条件为（N 为处理机个数）：gC N第4章与时间有关的错误：不一定会发生，与推进速度有关。两个进程同时对一个变量进行操作， 失去了变量数据的完整性。临界区：访问共享变量的程序段 临界资源：一次只允许一个进程使用的资源 进程互斥：两个或两个以上的进程不能同时进入关于同一组共享变量的临界区，否则可能发生与时间有关的错误，可以发生在任意两个进程之间进程互斥的实现：doentry section临界区Exit section其余代码 while (1)临界区的管理（实现进程互斥）：1.互斥性，任意时刻至多只能有一个进程处于关于同一组 共享变量的临界区之中2进展性，临界区空闲时，只有执行entry或者exit的进程参与下 一个进入临界区进程的决策，该决策不能被无限期推迟3.有限等待性，一个请求进入临界区的进程应当在有限的等待时间获得进入该临界区的机会。忙式等待：不进入等待状态的等待 同步（进程同步）：一组进程，为了协调其推进速度，在某些点处需要相互等待或者唤醒， 进程之间这种相互制约的关系，仅发生在相互有逻辑关系的进程之间PV 操作：P101 P35 第 21、22、35 题信号变量的使用要求： 1必须置一次初值，也只能置一次初值，初值必须非负整数2只执行P、V操作生产者一消费者问题P103 进程通信：进程之间的互斥、同步、信息交换 进程通信的模式：1 共享内存模式 2 消息传递模式第5章1. 死锁和饥饿都是由于进程竞争资源而引起的.2. 死锁：一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而 永远无法得到的资源，这种现象称为进程死锁。3. 死锁的条件：资源独占、不可抢占、保持申请、循环等待 （破坏上述任意一个条件可以消除死锁）4. 死锁的处理：死锁预防-静态、死锁避免-动态、死锁检测、死锁恢复 4.1死锁的预防：设置某些限制条件，破坏四个必要条件中的一个或几个。资源独占（不可以）、不可剥夺（可以）、保持申请（可以）、环路等待条件（可以） 预防方法：预先分配法；有序分配法4.2死锁避免：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态 可获得较高的资源利用率和系统吞吐量（减少了限制条件，提高了并发性）4.3死锁检测：（1）死锁检测算法（PPT）（ 2 ）死锁检测时刻： 考虑因素：死锁发生频度；死锁影响的进程数。（ 1 ）等待时检测：发现早，恢复代价小，开销大（ overhead）。（2）定时检测：资源（eg. CPU）利用率下降时检测。4.4 死锁恢复：（1）重新启动 简单，代价大，涉及未参与死锁的进程。（2）终止进程（process t ermina tion）环路上占有资源的进程。一次性全部终止；逐步终止（优先级，代价函数）（3）剥夺资源（resource preemp tion）+进程回退（rollback） select a victim； rollback.问题：a.保存snapshot代价大；b.消除影响困难；c.starvation.5. 饥饿：当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿.饥饿到一定程度 的进程所赋予的使命即使完成也不再具有实际意义时称该进程被饿死（s tarved to dea th）. 忙式等待条件下发生的饥饿，称为活锁（live lock）.6. 饥饿 vs 死锁： 死锁进程处于等待状态，忙式等待的进程并非处于等待状态， 但却可能被饿死;死锁进程等待永远不会释放的资源， 饿死进程等待可能被释放，但却不会分给自己的资源， 其等待时间没有上界;死锁一定发生了循环等待， 饿死则不然;死锁至少涉及两个进程， 饿死进程可能只有一个.7. 本章算法：1. 资源分配图的约简： 资源分配图的约简方法：（1）寻找一个非孤立且没有请求边的进程结点Pi,若没有则算法结束。（2）去除所有Pi的分配边，使Pi成为孤立结点。（3）寻找所有请求边均可满足的进程Pj,将Pj的请求边全部改为分配边。（4）转步骤（1）算法结束时，若所有结点均为孤立结点，则称资源分配图是可以完全约简的，否则 称为不可完全约简的。死锁定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。2. 死锁检测算法3. 银行家算法第 6章 存储管理1. 存储管理需要完成以下功能：存储分配、存储共享、存储保护、存储扩充、地址映射。2. 存储共享是指两个或多个进程共用内存中的相同区域，即它们的物理空间有相交的部分。3. 存储共享的目的： 1.节省内存空间 2.实现进程通信共享内容：程序段（纯代码）、数据4. 将逻辑地址转换为物理地址的过程称为地址映射。5. 动态分区的几个算法：最先适应（P177）、最佳适应（P178）、最坏适应（P178）6. 覆盖技术: 将较大程序装入较小进程空间的技术。程序内部的若干程序段共享主存的技 术。7. 页式存储管理： 基本原理：（1）内存空间划分：内存空间被静态的划分为若干个等长的区域，每个区域称为一个物理页框，每个页框通常有个2个单元（i为整）（2）进程空间划分：静态等长，2 i,称为一个页面。8. （虚拟页式存储管理）虚拟淘汰算法： 1.最佳淘汰算法2.先进先出算法 3.最近最少使用 算法（P198P203）第7章文件:具有符号名而且在逻辑上具有完整意义的信息项的序列 文件系统:文件与管理文件的程序集合。是管理文件的机构，而不是文件集合 文件系统的作用:文件系统是操作系统中负责操纵和管理文件的一整套机制，它实现文件的 共享和保护，方便用户“按名存取”。文件系统为用户提供了存取简便、格式统一、安全可 靠的管理各种文件信息的方法。顺序结构：一个文件占有若干连续的磁盘块。 优点：速度快，节省空间，无其他的空间开销 缺点：长度变化困难 链接结构（串结构）：一文件可存于不连续块中，块间以指针相连。优点：节省空间，长度变化容易。 缺点：随机访问速度慢。 索引结构（间接寻址）：一文件可存于不连续块中，块号记在索引块中。优点：速度快，长度变化容易。 缺点：索引块占空间。Hash结构：计算地址：hash（key）二addr （在磁盘或文件中的存放位置）逻辑组织: 用户看到的文件组织形式 记录式文件：记录的序列（基本单位是记录） 等长记录（优点：处理方便，速度快；缺点：空间浪费） 不等长记录（优点：省空间；缺点：处理不便，速度慢） 流式文件：字节的序列（基本单位是字节）物理组织:逻辑组织到磁盘块的映射（文件在存储设备上的存放方法）目录项:目录文件中的一项，内容为 FCB文件控制块（FCB）:文件存在的标志，其中保存系统管理文件需要的全部信息文件目录的查找: 1.查找路径:由根目录开始查找; 由当前目录开始查找2查找算法:顺序查找（UNIX）; hash查找;对分查找（要求文件名排序）共享目的: 1 . 节省存储空间 2. 进程相互通讯 保护:防止用户对文件进行非授权的访问 保密: 防止文件内容泄露 安全: 防止文件被破坏第8章1. 设备管理的目标是方便用户使用设备；实现设备的独立性；提高设备的使用效率；对各种 外设进行统一的管理。2. 设备管理的功能就是：设备控制；设备分配（算法和策略）；I/O操作；缓冲管理。3.I/O 传输方式: 程序控制查询方式: 缺点:处理机与设备串行工作; 一段时间内只能和一台外围设备交 换数据信息，不能执行并行操作。消耗大量处理机时间，只适用与低速CPU和外围设备较少 的情况。 中断驱动方式：特点：CPU与设备并行工作。设备多时对CPU打扰多（每次输入输出 都会出现中断），消耗大量的CPU时间。 DMA方式（直接内存存取方式）：内部有若干寄存器，通过总线与设备，内存相连。 操作系统可采用DMA方式进行输入输出操作。 通道方式：负责10操作的处理机（控制设备和内存直接进行数据交换），涉及内容包 括指令系统，运控部件，存储区域。一个通道程序可以控制若干设备进行多次I0传输。4. 设备分配的数据结构：设备控制表（DCT）控制器控制表（C0CT）通道控制表（CHCT）系统设备表（ SDT）5. 磁盘引臂调度（disk head scheduling）：详见p269 先到先服务（FCFS）：按照输入输出请求的次序为各个进程服务， 最短寻找时间优先（SSTF）：优先为距离磁头当前所在位置最近的请求服务。 （SCAN）扫描（LOOK）电梯算法：往复扫描各个柱面并为路经柱面的请求服务，从 外向内。 C-SCAN （C-LOOK）：只在单方向移动过程中才为路经的请求服务。6. 引入缓冲技术的主要目的是：缓和CPU与I/O设备间速度不匹配的矛盾；提高它 们之间的并行性； 减少对CPU的中断次数，放宽CPU对中断响应时间的要求。7.SPOOLing技术就是最成功的虚拟设备技术，其结构为：（1）输入井和输出井（2）输入缓 冲区和输出缓冲区（3）输入进程SP1和输出进程SP28. 磁带的物理结构：盘面，扇区，柱面（磁道），详见 p259