《操作系统(第六版)复习整理》由会员分享，可在线阅读，更多相关《操作系统(第六版)复习整理（6页珍藏版）》请在金锄头文库上搜索。
1、五： Concurrency：Mutual Exclusion and Synchronization 并发性：互斥与同步1. 并发出现在以下三种不同的上下文中:A. 多个应用程序:多道程序设计技术允许在多个活动的应用程序间动态共事处理时间。B. 结构化应用程序:作为模块化设计和结构化程序设计的扩展，一些应用程序可以有效地 设计成一组并发进程。C. 操作系统结构：同样的结构化程序设计优点可用于系统程序员，且我们已经知道操作系 统自身常常作为一组进程或线程来实现。2. Principles of Concurrency: (并发的原理)(1) . 多道程序设计系统的一个基本特性:进程的相对执行速
2、度不可预测，它取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。这就带来了下列困难:1. 全局资源的共享充满了危险。2. 操作系统很难对分配资源进行最优化的管理。3. 定位程序设计错误是非常困难的。(2) . 和并发相关的关键术语如下：临界区：是一段代码，在这段代码中进程将访问共享资源，当另外一个进程已经在这段 代码中运行时，这个进程就不能在这段代码中执行死锁： 两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而 不能继续执行，这样的情形叫死锁活锁： 两个或两个以上的进程为了响应其他进程中的变化而继续改变自己的状态但 不做有用的工作，这样的情形叫活锁互斥： 当
3、一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共 事资源，这种情形叫互斥竞争条件：多个线程或者进程在读写一个共享数据时结果依赖于它们执行的相对时间， 这种情形叫竞争饥饿：是指一个可运行的进程尽管能继续执行，但被调度器无限期地忽视，而不能被 调度执行的情况(3) . 为了提供对互斥的支持，必须满足以下要求:1必须强制实随互斥:在具有关于相同资源或共享对象的临界区的所有进程中,一次只 允许一个进程进入临界区。2. 个在非临界区停止的进程必须不干涉其他进程。3. 决不允许出现一个需要访问临界区的进程被无限延迟的情况，即不会死锁或饥饿。4. 当没有进程在临界区中时,任何需要进入临界区
4、的进程必须能够立即进入。5. 对相关进程的速度和处理器的数目没有任何要求和限制。6. 一个进程驻留在临界区中的时间必须是有限的。3. 互斥的硬件支持：(1) . 中断禁用 在一个单处理器机器中,并发进程不能重叠,只能交替。此外,一个进程将一直运行,直到它调用了一个操作系统服务或被中断。因此为保证互斥,只需要保证一个进程不被中 断就可以了,这种能力可通过系统内核为启用中断和禁用中断定义的原语来提供。(2) . 使用专门的机器指令实施互斥有以下优点:适用于在单处理器或共事内存的多处理器上的任何数目的进程。非常简单且易于证明。可用于支持多个临界区，每个临界区可以用它自己的变量定义。 但是，同样也有一
5、些严重的缺点:使用了忙等待。因此，当一个进程正在等待进入一个临界区时，它会继续消耗处理 器时间。可能饥饿。当一个进程离开一个临界区并且有多个进程正在等待时，选择哪一个等 待进程是任意的。因此，某些进程可能无限期地被拒绝进入。 可能死锁。4. Semaphores (信号量):被阻塞时间最久的进程最先从队列释放。采用这个策略定义的信号量称为强信号量(strong semaphore)。没 有策略规定进程从队列中移出的顺序的信号量称为弱信号量(weak semaphore)。5.生产者和消费者问题解决方法：严 progmik producerconsumer semaphore ti -0; se
6、maphore s = I;vaid producerf)while (true)produce; semWait(s); append();sefnSignat(n);void JTisumcr()whffe (true)scmWait(n)； wmWait(s); take();semSienal(s)； consume (;*rid matn()purbe血(producer, consumer);严 progruiTk bounded buffer */ tonst int sizcofhuffer = /* buffer size */; semaphore s 1； semopho
7、re n= 0;semaphore c- sizeofbuffer： void produter()wMte (true)produce。； srniWajt(u; semWait(s)； nppend();scmSinaJK)；mSignal(n)void consumer()while (true)sen)Waitn); semWatifs)； iake();scmSignal(s)：cnnsume()：T Ivoid raatnO!parben (producer, consumerK使用信号量解决元限缓冲区生产者/消费者问题的方法使用信号量解决有限缓冲区生产者/消费者问题的方法6.Mo
8、nitors 管程是由一个或多个过程、一个初始化序列和局部数据组成的软件 模块，其主要特点如下:1. 局部数据变量只能被管程的过程访问，任何外部过程都不能访问。2. 一个进程通过调用管程的一个过程进入管程。3. 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都 被挂起，以等待管程变为可用。*:管程通过使用条件变量提供对同步的支持，这些条件变量包含在管程中，并且只有在管程 中才能被访问。有两个函数可以操作条件变量: cwait( c): 调用进程的执行在条件 c 上挂起，管程现在可被另一个进程使用。 csi 但 al ( c ): 恢复在 cwait 之后为某些条件而挂起的进程的
9、执行。如果有多种这样的 进程，选择其中一个;如果没有这样的进程，什么也不做。注意，管程的eU和signal操作与信号量不同。如果在管程中的一个进程发信号，但没 有在这个条件变量上等待的任务，则这个信号丢失。7: Message Passing (消息传递): 当进程互相交互时，必须满足两个基本要求:同步和通信。为实施互斥，进程间需要同步; 为了合作，进程间需要交换信息。提供这些功能的一种方法是消息传递*:消息传递的实际功能以一对原语的形式提供:send ( destination, messages)receive ( source , message) *:两个进程间的消息通信隐含着某种程序
10、的同步:只有当一个进程发送出消息之后，接收者才能接收消息。此外，当一个进程产生了 se.nd 或 recei 四原语后，需要确定会发生什么。图5.19 -般消息格式六： Deadlock and Starvation1. 死锁原理：(1) . 资源通常可分为两类:可重用的和可消费的。可重用资源是指一次只能供一个进程安 全地使用，并且不会由于使用而耗尽的资糠。可消费资掠是指可以创建(生产)并且可以销毁 (消费)的资源(2) . 若可能发生死锁，则必定要出现三个条件:1. 互斥。一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的 资源。2. 占有且等待。当一个进程在等待分配得到其
11、他资源时，其继续占有已分配得到的资 源。3. 非抢占。不能强行抢占进程中已占有的资源。4. 循环等待。存在一个封闭的进程链，使得每个资源至少占有此链中下一个进程所需 要的一个资源.前三个条件是死锁存在的必要条件，但不是充分条件。第四个条件实际上是前三个条件的 潜在结果，即假设前三个条件存在，可能发生的一系列事件会导致不可解的循环等待。在死锁预防中，通过约束资源请求，防止 4 个死锁条件中至少一个的发生。这可以通过 防止发生三个必要策略条件中的一个(互斥、占有且等待、非抢占)间接完成，也可以通过防 止循环等待直接完成，但这都会导致低效的资源使用和低效的进程执行。死锁避免则相反， 它允许三个必要条
12、件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免比死锁 预防允许更多的并发。两种死锁避免方法:A :如果一个进程的请求会导致死锁，则不启动此进程。即进程启动拒绝；B: 如果一个进程增加资源的请求会导致死锁，则不允许此分配。即资源分配拒绝，又 叫银行家算法。死锁探测：实验一；哲学家就餐问题；七：Memory Management1. 内存重定位(Memory relocation)：由于某种原因，处理器硬件和操作系统软件必须能够 把程序代码中的存储器访问转换成实际的物理存储器地址，以反映程序在主存中的当前 位置。2. Memory Partitioning (内存分区):固定分区: 在
13、系统生成阶段，主存被划分成许多静态实现简单，只稽要极少的操 分区。进程可以装入到大子或等于自身作系统开销大小的分区中动态分区: 分区是动态创建的，因而使得每个进程可没有内部碎片;可以更充分 以装入到与自身大小正好相等的分区中地使用主存伙伴系统是一个合理的折中方案，它克服了固定分区和可变分区方案的缺陷。弱点：A :由于有内部碎片，对内存的使用不充分;活动进程的最大数目是固定的B：由于需要压缩外部碎片，对内存的使用不充分伙伴系统：逐次平分，直到产生大于或等于s的最小块，并分配给该请求。八虚拟内存1. 分段优点：1. 简化不断增长的数据结构的处理。2. 允许程序独立地改变或重新编译，而不要求整个程序
14、集合重新链接和重新加载。3. 有助于进程间的共享。4. 有助于保护。2读取策略：读取策略确定一页何时取入主存，常用的两种方法是请求式分页(demand paging) 和预约式分页(preparing)(一次读取许多连续的页)。对于请求式分页，只有当访问到某页中 的一个单元时才将该页取人主存。3. 帧锁定： :主存中的某些帧可能是被锁定的。如果一个帧被锁定时，当前保存在该帧中的页 就不能被替换。4. 基本替换算法：最佳( Optimal , OPT)最近最少使用(Least Recently Used ,LRU)先进先出(First In First Out, FIFO )时钟(Clock)驻
15、留集管理（Resident Set Management）：分固定分配、可变分配策略。 替换范围：局部替换、全局替换。可变分配、局部范围：工作集策略（Working Set Strategy） 0 九：单处理器调度1. 调度的类型长程调度 决定加入到待执行的进程池中中程调度 决定加入到部分或全部在主存中的进程集合中短程调度 决定哪一个可用进程将被处理器执行I/0 调度 决定哪一个进程挂起的 110 请求将被可用的 1/0 设备处理2. 选择调度策略FCFS 轮转 SPN SRT HRRN 反馈 非抢非抢非抢SPN：最短进程优先，不中断；SRT:最短剩余时间，中断；HRRN:最高响应比优先，不 中断。（响应比=（等待处理器时间+期待服务时间） /期待服务时间）A：各算法的性能比较：rr I, _ 一一 一一一 7； 1 -P十.多处理器和实时调度1. 实时操作系统可以被描述成具备以下五方面的要求MORG92:可确定性可响应性用户控制可靠性故障弱化操作2. 当前的实时操作系统包括以下典型特征STAN89:快速的进程或线程切换 体积小（只具备
