操作系统全面剖析.ppt

1、操作系统综述,操作系统综述,如何装入可执行程序及其所需的数据,装入方式： 绝对装入 重定位装入 运行时动态装入,何时将程序的逻辑地址转换为物理地址,绝对装入,程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定的地方。 实现简单，无须进行逻辑地址到物理地址的变换。,绝对装入方式的缺点,1,4,程序每次必须装入同一内存区 程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址 程序的修改（增加或删除指令）将引起整个程序中指令地址的变动,重定位装入,允许将程序装入与逻辑地址不同的物理内存空间。即程序可以装入到内存的任何位置，其逻辑地址与装入内存后的物理地址无直接关系 必须进行地址映

2、射，将逻辑地址转换为物理地址,静态重定位,地址映射在程序装入时进行，以后不再更改程序地址 静态重定位不允许程序在内存中移动。这不便于进程交换和紧凑拼接操作，也很难实现多道程序环境下，多个程序同时装入内存的要求 静态重定位只适合于单道程序环境下,运行时动态装入,程序的地址转换不是在装入时进行，而是在程序运行时动态进行 运行时动态装入需要硬件支持，即重定位寄存器，用于保存程序在内存中的起始地址 程序被执行时，通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地址 运行时动态装入有利于多道程序环境下，进程的换进/换出及实现紧凑技术,程序在内存中是如何组织的？,程序在内存中的组织,连续存

3、储： 需要内存中一块连续的、足够大的分区 如果内存中没有足够大的连续空闲分区，但存在总量足够的独立小分区，系统要么拒绝分区，要么采用紧凑技术将独立小分区拼接起来供程序使用。,非连续存储：允许进程的程序和数据分别装在内存的不同分区中，必须把一个进程分到的所有分区的位置、大小、使用情况（如是否共享等）等信息记录下来。 常用的非连续存储技术：分页存储技术、分段存储技术及段页式存储技术。 动态地址转换和非连续存储是虚拟内存技术的关键。,连续存储与非连续存储,内存的连续存储与非连续存储,非连续存储-分页存储管理,分页存储管理技术是一种特殊的固定分区方法。 系统事先将物理内存划分成许多尺寸相等的页帧 (P

4、age Frame)，并将进程分割成许多大小相同的页面 (Page)，页面与页框大小相同。,分区 分页,分区：进程的逻辑地址空间是连续的、一维的、线性地址，进程的每一条指令和数据的地址相对于第一条语句的地址而定。 分页：进程被分割成许多页面。每个页面内的指令和数据是连续的，它们的地址相对于其所属页的第一条语句的地址，称为页内偏移量。 逻辑地址被分为两部分：页号和页内偏移量 。 当进程被装入内存时，系统将为进程的每个页面分配一个页框 同一个进程的多个页面不必存放在连续的多个页框中,分页,，实现了虚拟机的高可用性。,进程装入到离中散的页帧,页表与页表寄存器,页表：系统为每个进程建立一张页面映射表，

5、用于记载进程中各个页面到到物理内存中页帧的映射信息。 进程的每个页面依次对应页表中的一个表项，其中包含相应页在内存中对应的物理页帧号和页面存取控制权限等字段。,页表寄存器：存储执行进程的页表起始地址，执行快速地址映射。 进程的每个页面依次对应页表中的一个表项，其中包含相应页在内存中对应的物理页帧号和页面存取控制权限等字段。,分页地址直接映射,分页地址直接映射缺点,系统把被转换的逻辑地址和页表的基址放在处理器的高速寄存器中以保证在一个指令执行器内快速完成这些值的运算。 系统把直接映射的页表保存在主存中，对页表的一次饮用就需要一个完整的主存周期，而一个指令执行周期的最大部分都停留在主存访问上，再加

6、上页到页帧之间的映射也需要一个主存访问，这就可能导致系统运行程序的速度下降一半。 有人提出把直接映射页表放在高速缓冲存储器以加快转换速度，但如果逻辑地址空间可能会很大，鉴于高速缓冲存储器的高成本，此方案很快被认为不可行。,快表,又称后备式转换缓冲器(TLB)，只存储当前进程完整页表的一小部分内容，也即最近访问过的页表项。 快表基于局部性原理，即被访问过的页可能在不久的将来被再次访问。,快表地址转换,多级页表,直接地址映射中，一个页表中的所有页表项都必须在映射表中，按页号连续存储。这会消耗大量的内存空间。 假设一个页大小为4KB(212)的32位地址空间，将会有220(232-12)个页编号，这

7、就相当于需要100万个页表项，而一个使用4MB的64位地址空间大约需要4万亿个页表项，这就会严重占用程序实际可使用的内存。 多级页表使得系统把一个进程经常使用的那部分页表保存在内存的不连续地址中。而进程页表的其它部分可以在第一次使用时创建，并在不再被经常使用时移出内存。 多级页表的层次结构每级一个表，存储指向下一级表的指针，最低级由包含页到页帧的映射的表组成。,二级页表寻址,分段存储管理,分段：在模块化程序设计中，每个程序的指令和数据被划分成大小不同的子程序，称为分段。物理内存被动态划分成大小不等的分区，当进程被装入内存时，系统为进程的每一段分配一个分区，同一进程的不同段不必存放在连续的分区中

8、。 段表同样被保存在物理内存中，并用段表寄存器来存放当前执行进程的段表在物理内存中的的起始地址。,分段直接地址映射,分段与分页技术比较,都采用非连续存储，由地址映射实现地址变换。 页是信息的物理单位，大小固定。段是信息的逻辑单位，各段的长度不固定。每一段都具有一定逻辑含义。 分页的地址空间是一维的，逻辑地址的划分由机器硬件实现，对用户透明。分段的地址空间是二维或多维的，程序员知道段名和段内偏移量。 分页活动源于系统管理物理内存的需要，在系统内部进行，由系统实施，用户看不见。分段活动源于用户进行模块化程序设计的需要，在系统外部进行，由用户实施，用户是知道的。,段页式存储,基本思想：采用分段方法组

9、织用户程序，采用分页方法分配和管理内存。即用户程序可以用模块化思想进行设计，一个用户序由若干段构成。系统将内存划分成固定大小的页帧，并将程序的每一段分割成若干页以后装入内存执行时。 逻辑地址由3部分组成：段号、段内页号、页内偏移量。,段页式存储,段页式存储直接地址映射,段页式存储,在整个地址转换过程中，搜索段表时可能会发现要找的分段不在段表中，从而产生分段缺失错误，操作系统将获得控制权并在辅助存储上找到对应分段，创建对应分段的页表，再把相应的页装入内存。如果分段在内存中，对页表的查找可能会发现要找的页不在内存中，发出一个缺页错误，操作系统又将获得控制权，将辅助存储上的对应的页装入内存。 进程还

10、可能要引用一个不在分段范围内的逻辑地址，从而产生一个分段溢出异常。 为了保护每个进程不受其它进程破坏，操作系统为每个进程分配对一些分段的访问权，如果不具有对被引用地址的访问权限，还会产生一个分段保护异常。,处理器调度,现代操作系统里，多为多道程序设计，即内存驻留的进程不止一个 在某一特定时刻，一个CPU只能运行一个进程 多道程序设计环境下，CPU如何协调处理多个进程之间的运行？,处理器调度,操作系统处理器调度分三个级别：高级调度、中级调度和处级调度。 高级调度：也称作业调度，它负责决定哪些作业准许进入系统。一旦作业进入系统，作业就会初始化，并成为进程或进程组。 中级调度：作业被高级调度准许进入

11、系统后，将由中级调度决定允许哪些进程竞争处理器。它临时挂起并恢复进程，确保系统流畅工作。 低级调度：负责决定在处理器可用时，将哪个就绪状态的进程分配给处理器。,处理器调度,具三级调度的调度队列模型,处理机资源管理,处理机资源管理要解决三个问题： 依什么原则分配处理机，即确定处理机调度算法 什么时候分配处理机，即确定处理机调度实际 如何分配处理机，即给出处理机调度过程,调度算法,调度算法要考虑一下几个指标： CPU利用率：尽量让CPU处于运行状态，在一定的I/O等待时间的百分比，运行的进程越多，则CPU的闲置时间越低。 吞吐率：单位时间内所处理的进程数。 周转时间：从进程等待进入内存开始直到进程

12、完成为止的时间总和。 响应时间：就是从进程就绪到处理开始。 系统开销：处理机调度过程中所付出的时空开销。,处理机调度算法类型,先来先服务调度算法 短进程优先调度算法 高优先权优先调度算法 高响应比优先调度算法 基于时间片的轮转调度算法 多级反馈队列调度算法,处理器调度时机,创建进程：创建进程时 进程终止时：一个进程终止时必须进行调度。如果没有就绪进程，系统通常会启动一个空转进程(休闲进程)等待(硬/软)中断的发生。 等待事件：进程由于等待I/O、信号量或其它原因而放弃CPU，这样就必须选择另外一个进程。 中断发生：当发生I/O中断，原先等待I/O的进程就从阻塞态转变成就绪态，是否可强占。 运行

13、到时：在分时系统中，当前进程用完给定的时间片，时钟中断使该进程让出CPU进入调度。,处理器调度,某一特定时间片里，一个处理器只能被一个进程占用。 宏观上并行，微观上串行。,死锁,死锁的四个充分必要条件： 互斥条件：一个资源每次只能由一个进程独占式地获得 保持和等待条件：获取了一个独占资源的一个进程可以在获取其它资源时持有那个资源。 一旦进程获取了一个资源，系统就不能把它从进程的控制中移出，除非进程结束资源。 循环等待条件：两个或多个进程在一个循环链中锁定。其中，每个进程都等待由链中的下一个进程所持有的一个或多个资源。,无限延期,假定系统采用优先级来调度资源，当一个进程因为资源分配及进程调度策略

14、而等待的过程中，大量具有高优先级的进程持续到来，这个进程就进入了无尽的等待资源的境况。 无限延期不同于死锁，但同样也会给系统造成严重的后果。,预防死锁,杜绝“等待”条件：一个进程完成任务所需的全部资源必须同时请求，系统要么全部批准，要么全部拒绝，进程等待时，将不能持有任何资源。 杜绝“不可抢占”条件：假如持有资源的一个进程在请求附加资源时被拒，它必须释放以前持有的资源。 杜绝“循环等待”条件：为系统的每个资源分配一个不重复的编号，创建资源的一个线性顺序，进程必须严格按升序来请求它的资源。,死锁解决办法,死锁预防：杜绝发生死锁的四个必要条件之一 死锁避免：允许进程动态地申请资源，但系统在进行资源

15、分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。,文件管理,进程需要把内存中的数据往外存上写，如何找到数据要写入的位置 数据在外存是如何组织的,数据层次结构,最底层按位组合在一起来标识有意义的数据项 次层就是固定长度的位模式，如字节、字符和字。字是处理器一次能操作的位数。 一组字符就组成了字段 一组字段组成了记录 一组记录则组成了文件 一个卷则可以包含多个文件，分逻辑卷和物理卷。,文件系统,文件系统负责对文件进行组织并管理对数据的访问。 文件管理：提供存储、引用、共享文件和保护文件安全的机制。 辅助存储器管理：在辅助存储设备

16、或第三季存储设备上位文件分配空间。 文件完整性机制：确保文件中存储的信息未被破坏。 访问方法：如何访问存储的数据。,文件系统管理,同虚拟内存管理一样，文件系统管理也要： 分配存储器 向应用程序隐藏存储器的物理视图 控制对存储器的访问,文件分配方式,连续文件分配 链表式文件分配 表格式文件分配 索引式文件分配,连续文件分配,连续文件分配：把文件数据存放在存储设备的连续地址上。,连续文件分配,连续文件分配：把文件数据存放在存储设备的连续地址上。 连续分配方式下文件数据的定位非常直接，只要找到第一个数据块以后就不需要执行繁琐的寻道操作，加快了访问速度。 但容易产生碎片。 随着文件的增大，导致没有相邻

17、的空闲块可供使用，就必须把文件传输到一个新的有足够大小的区域，这就会引起额外的I/O操作。 适合一次性写入CD和DVD，它们不允许文件随着时间的过去而增大或缩小。,链表式非连续文件分配,在可重写的辅助存储介质上实现的大多数文件系统都使用非连续分配。,链表式非连续文件分配采用块(由连续扇区组成)分配策略，系统给文件分配新块时，选择与已有文件数据块尽量接近的空闲块，最好是在同一个柱面上。每次访问文件时，都需要确定相应的数据块和相应数据块内的扇区。 块分配策略下，每个块都由一个数据块和一个指向下一个数据块的指针组成，块链上的所有块就是文件的组成。 块散列在整个磁盘中，增加了寻道时间。,链表式非连续文

18、件分配,链表式非连续文件分配,只适合于顺序访问，对随机访问效率低。,块散列在整个磁盘中，增加了寻道时间。,表格式非连续文件分配,该策略将各物理块的指针显示地放在内存的一张链接表中。该表整个磁盘中设一张，表的序号为盘块号，在文件的FCB的物理地址中填写其链首指针所对应的盘块号。,FAT（File Allocation Table）：文件分配表，整个磁盘设置一张，放在内存中。 缺点：不能直接存取；FAT占较大内存空间。,表格式非连续文件分配,表格式非连续文件分配,FAT（File Allocation Table）：文件分配表，整个磁盘设置一张，放在内存中。 缺点：不能直接存取；FAT占较大内存空

19、间。,索引分配,该策略使用索引块指向一个文件中的数据。每个文件都有一个或多个索引块，索引块包含一系列指向文件数据块的指针。,索引分配,设备管理,I/O设备： 独占设备 在一段时间内只允许一个进程访问的设备，也即临界资源。 共享设备 在一段时间内允许多个进程访问的设备。可寻址的、可随机访问的。如磁盘。 虚拟设备 通过虚拟技术将一台独占设备变为若干台逻辑设备，供若干进程使用。,I/O控制方式,程序I/O方式：早期CPU没有中断机构，须循环测试I/O设备状态以判断设备的忙闲状态。由于CPU与I/O设备速度的不一致性，导致CPU绝大部分时间都处于循环测试中。 中断驱动I/O方式：当进程要启动某个I/O

20、设备工作时，由CPU向相应的设备控制器发出一条I/O指令，然后立即返回继续执行原来的任务。设备完成相应的操作后便向CPU发送一个中断，CPU随机处理。实现了CPU与I/O设备的并行。,I/O控制方式,直接存储器访问DMA I/O方式：中断驱动I/O方式时的CPU是以字(节)为单位进行干预的。用于块设备的I/O时，效率将极其低下。DMA以数据块为基本传输单位，数据块是直接在内存与设备之间传送的，且仅在传输的开始和结束时需要CPU的干预。 I/O通道控制方式：把对一个数据块的读写干预，改为对一组数据块读写的干预。实现CPU、通道和I/O设备三者的并行操作。,尽量减少CPU对I/O控制的干预，提高系

21、统效率。,缓冲区,缓和CPU与I/O设备间速度不匹配的矛盾。 减少对CPU的中断频率。 提高CPU与I/O设备之间的并行性。,SPOOLing,SPOOLing 技术实际上是一种外围设备同时联机操作技术,又称为排队转储技术。它在输入和输出之间增加了“输入井”和“输出井”的排队转储环节。 提高了I/O速度。从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作，如同脱机操作一样，提高了I/O速度，缓和了CPU与低速I/O设备速度不匹配的矛盾。 设备并没有分配给任何进程。在输入井或输出井中，分配给进程的是一存储区和建立一张I/O请求表。 实现了虚拟设备功能。多个进程同时使用一独享设备，而对每

22、一进程而言，都认为自己独占这一设备，不过，该设备是逻辑上的设备。,设备驱动程序,接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求。,检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。,发出I/O命令，设备闲则启动以完成指令，忙则将请求放到等待队列。,及时响应控制器或通道发来的终端请求，并调用相应的中断处理程序来处理。,进程迁移,进程迁移就是将一个进程的状态，从一台机器转移到另一台上，从而使该进程能在目标机上执行。,为什么要进程迁移,负载平衡：通过将进程从负载较重的系统迁移到负载较轻的系统，系统负载就可以平衡，从而提高整体执行效率。 获得特定

23、资源：一个进程可以迁移，以利用一特定节点上独有的资源。如一个进程可能要访问一个只能通过另外一个节点才能方位的阵列。 提高通信性能：相互间紧密作用的进程可以移到同一节点，以减少他们作用期间的通信耗费。,谁来激发迁移,由谁来激发迁移取决于进程迁移的目的： 负载平衡：由操作系统中掌管负载平衡的组件来决定什么时候激发迁移。组件需要掌握其它系统的负载情况，以决定进程迁移到哪里。 问题1：如何获取系统负载情况？ 问题2：以什么方式来选中要被迁移的进程？ 获得特定资源：进程需要自己迁移。此时进程须了解系统的负载情况。,迁移过程,第1步：两个节点同意迁移进程。,第2步：发送节点将被迁移进程挂起，并创建一个消息

24、队列，以保存发往该进程的所有消息，发送节点还会提取该进程的状态，包括复制进程的存储器内容(在该进程的虚拟内存中标记为有效的页)、寄存器内容、打开文件的状态和其它与进程有关的信息。接收节点创建一个新进程。,第3步：在两个节点中传送进程状态。,第4步：两个节点将迁移进程的新地址通知给所有其它进程。,第5步：发送节点转发被迁移进程消息队列中的消息，并撤销该进程的本地实例。,进程迁移的剩余依赖性,剩余依赖性：进程对原节点的依赖性。,进程原节点可能包含该进程的部分工作集，或者可能正在执行与被迁移进程进行通信的其它进程。导致执行该进程时，接收节点必须与发送节点通信，增加了IPC，降低了性能。,被迁移进程的执行需要依赖于两个节点的正常工作，降低了容错性。,进程迁移策略,进程迁移策略必须平衡传输大量进程数据的性能代价与最小化一个进程的剩余依赖性的好处。