《复习指导》PPT课件.ppt

操作系统复习指导,操作系统基本概念,操作系统是控制和管理计算机系统的硬件和软件资源，合理地组织计算机工作流程及方便用户使用的程序和数据的集合。,操作系统的功能和主要特征,主要功能: 处理机管理 存储管理 设备管理 文件管理 用户接口,主要特征 并发性 共享性 虚拟性 不确定性 （随机性）,操作系统的结构,两部分：内核、核外部分。 内核有两种组织形式： 强内核 微内核,单用户操作系统 批处理操作系统 分时操作系统 实时操作系统 网络操作系统 分布式操作系统 多处理操作系统,操作系统的分类,五大类型(批处理、实时、分时、网络、分布),用户与操作系统的接口,用户与操作系统的三级接口 作业（命令）控制级接口 程序级接口 图形级接口,四个概念: 系统态、用户态、特权指令、访管制令,作业的概念、组成以及作业控制块的内容,作业：由不同的顺序相连的作业步组成。 作业步：在一个作业的处理过程中，计算机所做的相对独立的工作。 作业流：一次有一批作业进入系统，并在操作系统控制下，一个接一个地顺序进行处理。,作业由程序、数据和作业说明书三部分组成。,系统调用的概念 实现过程 与普通过程调用的区别,系统调用,定义：指系统为用户程序调用操作系统核心中实现系统功能的过程（子程序）。,系统调用的实现过程,实际上系统调用语句本身是硬件提供的（机器指令），但其所调用的功能是操作系统提供的。每种机器的机器指令集中都有一条系统调用指令。,作业调度,作业调度性能衡量指标,(1)作业平均周转时间T (Ti为每个作业的周转时间；tc作业完成时刻；ts作业进入系统时刻),(2)平均带权周转时间W （Ti为每个作业的周转时间；tr为作业实际运行时间）,作业调度算法,先来先服务（FCFS）：按照作业进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业。 短作业优先（SJF）：以要求运行时间长短进行调度，即启动要求运行时间最短的作业。,高响应比优先（HRF: Highest Response Ratio Next ）：响应比最高的作业优先启动。 响应比= 周转时间 / 估计运行时间 =（等待时间+估计运行时间）/ 估计运行时间 = 1 + 等待时间 / 估计运行时间 高优先级优先（HPF：Highest Priority First）：由用户指定作业优先级，优先级高的作业启动。,假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间，应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间。,最短作业优先算法结果,最高响应比优先算法结果,先来先服务调度算法计算结果,顺序程序特征： 程序执行的顺序性 程序执行的封闭性 程序执行结果的确定性（可再现性）,多道程序设计的特征 并发性 独立性 动态随机性 相互制约性,进程定义：Process 进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程，是系统进行资源分配和调度的独立单位,进程,进程的组成要素： 用户程序 用户数据 进程控制块PCB,进程的特征 动态性 独立性 并发性、异步性 结构化,进程与程序的区别 进程是动态的，程序是静态的; 进程是暂时的，程序的永久的; 进程与程序的组成不同; 进程可以创建其它进程，而程序不能； 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。,系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。,进程控制块 (PCB, process control block),进程状态转换图,中断、 内核、 原语,基本概念,处理机调度的层次,引进进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于阻塞状态（等待I/O） 当有一个优先级更高的进程就绪（可抢占式） 例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语） 分时系统中时间片到,常用进程调度算法,先进先出(FIFO)算法 最短CPU运行期优先调度算法 最高优先权优先调度算法 时间片轮转法 多级反馈队列,线程的特点： 是进程的一个实体，可作为系统独立调度和分派的基本单位。 不拥有系统资源（只拥有从属进程的全部资源，资源是分配给进程） 一个进程中的多个线程可并发执行。（进程可创建线程执行同一程序的不同部分）,线程（Thread）,定义：是进程的一个实体，是CPU调度的基本单位。线程自己基本上不拥有系统资源，只留有几个寄存器，但它可以与同属同一个进程的其他线程共享进程所拥有的全部资源。,进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问。 进程同步：指多个相关进程在执行次序上的协调。 临界资源:一次仅供一个进程使用的资源。 在进程中涉及到临界资源的程序段叫临界区。 多个进程的临界区称为相关临界区。,进程互斥与同步机制,信号量及P.V操作,信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则| S |表示S等待队列中的进程个数 P(S)：表示申请一个资源。 V(S)：表示释放一个资源，信号量的初值应该大于等于0。,P(S)： S=S-1; 若S0，则调用P(S)的进程继续运行； 若S0，则调用P(S)的进程被阻塞，并把它插入到等待信号量S的阻塞队列中。 ,P操作的原语,V(S)： S=S+1; 若S0，则调用V(S)的进程继续运行； 若S0，从等待信号量S的阻塞队列中唤醒头一个进程， 然后调用V(S)的进程继续运行。,V操作的原语,利用P.V操作 实现进程的同步与互斥,司机与售票员问题 生产者与消费者问题,管程：把分散的各同类临界区集中起来。并为每个可共享资源设立一个专门的机构来统一管理各进程对该资源的访问。,消息缓冲通讯技术的基本思想是：根据“生产者-消费者”原理，利用内存中公用消息缓冲区实现进程的信息交换。,死锁,概念：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称这一组进程或系统此时发生了死锁。,四个必要条件： 互斥控制（资源独占） 非剥夺控制（不可剥夺） 逐次请求（部分分配，占有申请） 环路条件（循环等待）,原因：系统资源不足； 进程推进顺序不合适；,对死锁的采取的对策,(1) 鸵鸟策略。 (2) 预防策略。 (3) 避免策略。 (4) 检测和解除。,预防死锁,破坏死锁四个必要条件中的一个或多个，来防止死锁。,解决方法： 静态资源分配 资源有序分配法,系统中对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。,避免死锁,最具有代表性算法：银行家算法。,例如，设系统中有 10 台磁带机，由三个进程A、B、C共享。假定A、B、C已分别占用了 2 台、3 台、3 台，它们的最大需求量分别为4 台、 6 台、 8 台。（假定只有当满足了最大需求量后才能释放所占用的全部资源。）,单项资源的银行家算法,P2: 5 3 2 P4: 7 4 3 P1: 7 5 3 P3: 10 5 5 P5: 10 5 7,P2 P4 P1 P3 P5,多项资源的银行家算法,地址变换(地址再定位,地址映射),直接指定方式:程序员在编序时或编译程序对源程序进行编译时，所用的是实际存储地址。 名空间程序 逻辑空间逻辑地址（相对地址，虚地址） 存储空间物理地址（绝对地址，实地址）,逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。 物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。 地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。,分区存储管理,原理：把内存分为一些大小相等或不等的分区，每个应用进程占用一个或几个分区。每个进程占据一个分区。 特点：适用于多道程序系统和分时系统 支持多个程序并发执行 难以进行内存分区的共享 问题：可能存在内碎片和外碎片。 内碎片：占用分区之内未被利用的空间 外碎片：占用分区之间难以利用的空闲分区。,固定分区,预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，但分区大小固定不变，每个分区装一个且只能装一个作业。,相关技术： 覆盖 交换,可变分区,按空闲块链接方式不同，有四种分配算法： 首次适应法 下次适应法（循环首次适应法） 最佳适应法 最坏适应法,可再定位式分区和多重分区 概念和原理,分页存储管理,页：把用户程序按逻辑页划分成大小相等的部分。用户程序分页的划分是由系统自动完成的，对用户是透明的。一页的大小为2的整数次幂。 内存块：按页的大小划分为大小相等的区域，称为内存块（又叫物理页面，页框）。 内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻，通过页表把作业的各个页面与内存块对应起来。,页面变换表,列出了作业的逻辑地址与主存中的物理地址间的对应关系。 页面大小: 页面的大小应适中，且页面大小应是2的幂 一个页表中包含若干个表目，自然序号对应于用户程序中的页号，块号是该页对应的物理块号。 页面变换表的每一个表目除了包含指向页框的指针外，还包括一个存取控制字段。,请求式分页存储管理,与纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。,缺页中断 当要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺的页面调入内存。,页面置换算法 ,先进先出置换算法 最近最久未用置换算法(LRU) 近似的LRU算法（NRU算法）,先进先出(FIFO)页面置换算法,基本思想：置换时 首先淘汰在内存中驻留时间最长的页面，即最早进入主存的页面。,FIFO M=3 缺页中断次数：F=9 缺页率：f=9/12=75%,最近最久未用(LRU)置换算法,基本思想：当需要置换一页时， 选择在最近一段时间最久未用的页予以淘汰。,LRU M=3 缺页中断次数：F=10 缺页率：f=10/12=83%,分段存储管理,原理：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。,内存划分 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。 内存分配 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。,段表,记录了段号，段的首（地）址和长度之间的关系。每一个程序设置一个段表，放在内存， 属于进程的现场信息。,分页与分段的主要区别,段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。 页的大小固定不变，由系统决定。段的大小是不固定的，它由其完成的功能决定。 段式向用户提供的是二维地址空间，页式向用户提供的是一维地址空间，其页号和页内偏移是机器硬件的功能。 由于段是信息的逻辑单位，因此便于存贮保护和信息的共享，页的保护和共享受到限制。,段页式存储管理,段页式管理吸收了分段的地址空间按逻辑意义分段的优点和分页在存储空间管理上的优点，不把段看成一个单一的连续整体来实现，而是将每个段分成若干页面来管理。 进程的逻辑地址由三个部分组成：即段号s，页号p，和页内相对地址w。,段表长度,段表控制寄存器,段表,内存,起始地址,第0段页表,第2段页表,5,6,12,19,20,段页式地址映像,段表长度指某个作业进程所含段的数量； 页表长度指一个段所占用的页的数量。,设备管理,设备的分类:按照功能、数据组织、资源分配和数据传输速率 设备的独立性 设备的统一性,设备控制器的组成,程序直接控制方式。 (2) 程序中断I/O方式。 (3) DMA方式。 (4) 通道方式。,I/O控制方式,DMA方式下的数据传输,通道分类: 字节多路通道 选择通道 数组多路通道,通道,通道工作原理：CPU、通道,IO软件的层次,中断处理程序 设备驱动程序 与设备无关的I/O软件 用户层的输入/输出软件,设备管理中的四种控制块,I/O系统的设备分配 按如下步骤实施设备分配： 分配设备。 (2) 分配控制器。 (3) 分配通道。,I/O控制,单缓冲 双缓冲 多缓冲 缓冲池,缓冲区管理,文件：是指具有符号名的数据信息的集合。 逻辑记录：构成文件内容和对文件进行存取控制的基本单位。 文件系统：操作系统中负责管理和存取文件信息的软件机构，是对文件存储器的存储空间进行组织和分配，负责文件的存储并对存入的文件进行保护和检索的系统。,文件与文件系统,文件的分类与逻辑结构,1）连续文件（顺序结构） 文件的信息存放在若干连续的物理块中 2）串联文件（链接结构） 一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块 3）随机文件（索引结构） 一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中,文件的物理结构,文件控制块（FCB）：文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息，是文件存在的标志。 文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合 目录项：构成文件目录的项目（目录项就是FCB） 目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件,概念,文件系统的层次结构,END!,