南大软院 操作系统.pptVIP

* * 走独木桥问题 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 先来先服务算法（First Come First Service） 基本思想是按照进程到达的先后顺序进行调度 最短作业优先算法（Shortest Job First） 要求作业在开始执行时预计执行时间，给预计执行时间短的作业优先分派处理机。后来的短作业不抢现正在执行的作业。 优先级算法（Priority Scheduling） 是多级队列的改进，协调各进程队列中进程的响应时间要求。分为抢占式和非抢占式。 计算各种调度算法下作业队列的 平均周转时间 进程的调度 并发－》串行 协作关系 同步 竞争关系 互斥 临界资源是指计算机系统中需要互斥使用的硬件或软件资源，如外设、共享代码段、共享数据结构等。 临界区是指进程中访问临界资源的一段代码。 信号量：由操作系统提供的管理公有资源的有效手段。信号量代表可用资源实体的数量，0表示还有可用的资源，新来的进程可以直接执行，0表示已经没有可用的资源，有进程因此而阻塞，＝0表示已经没有可用的资源，也没有进程在等待该资源。 P原语 P(s)：把信号量s 减去1，如果计算后的信号量s小于0 ，则阻塞该进程 V原语 V(s)：把信号量s 加1，如果计算后的信号量s小于或等于0，则从阻塞队列中激活一个等待的进程 解决若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。 One Producer, One Consumer, N Buffers One Producer，N Consumer, N Buffers N Producer, One Consumer, N Buffers N Producer, N Consumer, N Buffers 有五个哲学家围坐在一圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后，欲吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。 死锁（deadlock）是指系统中多个进程无限制的等待永远不会发生的条件。 产生条件 互斥：任意时刻只允许一个进程使用资源 请求和保持：进程在请求其他资源的时候，不主动释放已经占用的资源 非剥夺：进程已经占用的资源，不会被强制剥夺 环路等待：环路中的每一进程在请求另一进程已经占有的资源。 死锁的预防 预防死锁是指通过某种策略来限制并发进程对资源的请求，使系统在任何时候都不满足死锁的必要条件。 预先静态分配法和有序资源使用法。 死锁的检测 基本思路是在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。 资源分配图 死锁的避免 最合理做法应该是在分配资源时判断是否出现死锁，只有确信不会导致死锁时才分配资源。 银行家算法 内存管理的基本原理 内存管理主要包括内存分配和回收、地址变换、内存扩充、内存共享和保护等功能。 内存的管理 分区 分页 分段 段页式 最先适配法 按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端，但是随着低端分区不断划分，会产生较多小分区，每次分配时，查找时间开销便会增大。 下次适配法 按分区在内存的先后次序，从上次分配的分区起查找（到最后分区时，再从头开始），找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。 最佳适配法 按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。这种方法的优点是较大的空闲分区可以被保留下来。 最坏适配法 按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，因此当有对内存需求较大的进程需要运行时，其要求不易被满足。 将程序的逻辑地址空间划分为固定大小的页（page），而将物理内存划分为同样大小的页框（page frame）。加载程序时，可以将任意一页放入内存中任意一个页框，这些页框不必连续，从而实现了离散分配。该方法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中，地址结构由两个部分组成，前一部分是页号，后一部分为页内地址。 将程序的地址空间划分为若干段（segment），这样每个进程都有一个二维的地址空间。系统为每个段分配一个连续的分区，而进程中的各个段可以不连续的存放在内存的不同分区中。程序加