操作系统重点难点解析

,计算机操作系统内容提炼与重难点解析,提纲,认识操作系统操作系统采用的技术 操作系统内容提炼操作系统课程重点与难点解析,计算机操作系统内容提炼与重难点解析,1,一. 认识操作系统,2,什么是操作系统 操作系统的特点,认识操作系统,1. 认识操作系统 从操作系统在计算机系统中的位置来分析操作系统是什么 ？ 操作系统能做什么 ？ 操作系统如何去做 ？,3,操作系统定义,操作系统的功能,操作系统的实现技术,认识操作系统,认识操作系统,2. 操作系统的特点内容庞杂、涉及面广管理、控制所有硬件管理所有软件，控制程序的执行为用户提供良好的接口实践性强 操作系统原理与实际运行的操作系统的关系 技术发展快 基础性和先进性的关系,4,并行处理技术并行性: 处理多个同时性活动的能力并行处理: 利用多个处理部件，为完成一个整体任务而同时执行。,5,操作系统采用的技术,虚拟技术用户的逻辑视图与操作系统所管理的物理视图分离逻辑视图与的物理视图映射,二. 操作系统采用的技术,1. 并行处理技术 (1) 多用户、多任务同时执行(并发执行)如何描述任务 如何控制任务状态的变化 多任务关系如何协调 多任务如何调度 ,6,同步与互斥,进程的引入与进程概念,进程状态及控制,进程调度,操作系统采用的技术,(2) 系统资源共享处理机如何共享 存储器如何共享 设备如何共享 信息如何共享 ,7,存储分配、地址映射、虚存、存储保护,策略、调度、处理机分派,文件结构、存取方法、磁盘空间分配文件共享、文件保护、文件完整性,设备分配、虚拟设备、设备驱动,操作系统采用的技术,2. 虚拟技术 用户的逻辑视图与操作系统所管理的物理视图分离,8,操作系统采用的技术,三. 操作系统内容提炼,9,操作系统内容提炼,现代操作系统内容框架 操作系统与各层的关系 计算机系统结构与操作系统的关系 多任务并发执行的机制和策略 系统资源管理的策略和方法,1现代操作系统内容框架,10,操作系统内容提炼,11,2. 操作系统与各层的关系,(1) OS对各层的管理与控制与硬件的关系控制CPU的工作 访问存储器设备驱动、中断处理与用户及其他软件的关系控制、管理提供方便的用户界面提供优质的服务,操作系统内容提炼,12,(2) 各层对OS的制约和影响,下层硬件环境的制约提供OS运行基础限制了OS的功能实现用户和上层软件的要求用户需求提供优质的服务方便的用户界面,操作系统内容提炼,13,3. 计算机系统结构与操作系统的关系,OS采用了一系列软件技术多道程序设计技术、分时技术、资源分配与调度等计算机体系结构与硬件技术的变化 单CPU计算机 计算机网络 (多计算机系统),顺序计算模型,如何解决矛盾 ?,消息传递型多计算机,计算机系统结构,操作系统内容提炼,4多任务并发执行的机制和策略,(1) 所需的数据结构进程控制块：PCB进程队列就绪队列各种等待队列运行指针,14,操作系统内容提炼,4多任务并发执行的机制和策略,(2) 进程控制、进程调度、进程队列结构之间的关联进程控制,进程调度功能策略,15,创建,撤消,等待,唤醒,操作系统内容提炼,4多任务并发执行的机制和策略,(3) 多任务协调多任务之间的相互制约关系间接的相互制约关系 直接的相互制约关系 ,16,进程的直接相互制约关系 互斥同步,操作系统提供的同步机构 锁、上锁操作、开锁操作信号灯、P操作、V操作,操作系统提供同步机构,操作系统的资源分配功能, 两类同步问题：合作进程的执行次序 共享缓冲区的合作进程的同步,操作系统内容提炼,17,资源描述器资源描述器定义 描述描述各类资源的最小分配单位的数据结构称为资源描述器 rd。资源描述器内容 资源名、资源类型、最小分配单位的大小、地址、分配标志、 描述器链接信息、存取权限、密级、存取时间,(1) 资源分配机构,操作系统内容提炼,资源信息块资源信息块定义 描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。,5系统资源管理,资源信息块内容,18,操作系统内容提炼,19,资源信息块例中央处理机资源信息块内容,操作系统内容提炼,20,先请求先服务每一个新产生的请求均排在队尾，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要。排序原则：按请求的先后次序排序,(2) 资源分配策略,操作系统内容提炼,21,优先调度在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。每一个新产生的请求按优先级的高低插入到队列适当的位置上，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要。排序原则：按优先级的高低排序,操作系统内容提炼,22,针对设备特性的调度策略调度的目标 当有大量I/O请求时，降低完成这些I/O服务的总时间移臂调度 总是选取与当前移动臂前进方向上最近的那个I/O请求，使移臂距离最短。旋转调度 总是选取与当前读写头最近的那个I/O请求，使旋转圈数最少。UNIX、Linux系统的磁盘调度采用的是电梯调度策略,操作系统内容提炼,四. 操作系统课程重点、难点解析,23,操作系统课程重点、难点解析,进程状态及变迁 进程的同步与互斥 页式存储管理技术 文件索引结构,24,(1) 进程的三个基本状态及变迁 运行、就绪、等待,操作系统课程重点、难点解析,1. 进程状态及变迁,25,运 行,服务请求(请求I/O等),服务完成/事件来到,进程调度,时间片到,等 待,就 绪,操作系统课程重点、难点解析,?,26,(2) 具有进程基本状态的变迁图,操作系统课程重点、难点解析,27,(3) 进程状态变迁的讨论,变迁1 变迁4,变迁3 变迁4,变迁1 变迁3,操作系统课程重点、难点解析,28,2. 进程的同步与互斥,(1) 为什么需要同步,并发程序的特点失去程序的封闭性和可再现性 若一个程序的执行可以改变另一个程序的变量，那么，后者的输出就可能有赖于各程序执行的相对速度，即失去了程序的封闭性特点。,操作系统课程重点、难点解析,29,例：讨论共享公共变量的两个程序，执行时可能产生的不同结果。 设：程序A对做n加1的操作， 程序B打印n值，并将它重新置为零。,程序A的n :=n+1与程序B的两个语句的关系 n的初值 打印的结果 n的最终赋值,之前 10 11 0,之后 10 10 1,之间 10 10 0,设n初值为10,操作系统课程重点、难点解析,30,(2) 如何实现正确的同步,操作系统提供同步工具锁、上锁原语、开锁原语 能实现互斥信号灯、P操作原语、V操作原语 能实现同步与互斥,用户编程时，正确描述有直接相互制约关系的各进程的同步关系 (互斥的实现相对简单，这里不作讨论),操作系统课程重点、难点解析,31,什么是进程同步 所谓同步，就是并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。,进程同步的例,病员就诊,(3) 进程同步的概念,操作系统课程重点、难点解析,32,共享缓冲区的计算进程与打印进程的同步 计算进程 cp和打印进程 iop公用一个单缓冲,A,B,C,D,A,B,C,D,E,E,操作系统课程重点、难点解析,33,(4) 进程同步的实现 设：程序A对做n加1的操作，程序B打印n值，并将它重新置为零。,信号灯设置 s：表示进程A是否执行了加1操作，s = 0,同步描述,操作系统课程重点、难点解析,34,合作进程的执行次序,进程流图,(5) 两类同步问题的解法,操作系统课程重点、难点解析,35,分析任务的同步关系 任务启动后 P8先执行，当它结束后， P9 、 P10可以开始执行， P9 、 P10都执行完毕后，任务终止。,信号灯设置 设两个同步信号灯s9、 s10分别表示进程P9和P10能否开始执行，其初值均为0。,同步描述 P8 P9 P10 P(s9 )； P(s10 )； V(s9 )； V(s10 )； ,例: P8、 P9 、 P10为一组合作进程，其进程流图如图所示，试用信号灯的p、v操作实现这三个进程的同步。,操作系统课程重点、难点解析,36,计算进程 cp和打印进程 iop公用一个单缓冲， 为了完成正确的计算与打印，试用信号灯的 p、v操作实现这两个进程的同步。,共享缓冲区的合作进程的同步的解法,分析任务的同步关系 当cp进程把计算结果送入buf时，iop进程才能从buf中取出结果去打印，即当buf内有信息时，iop进程才能动作，否则必须等待。 当iop进程把buf中的数据取出打印后，cp进程才能把下一个计算结果数据送入buf中，即只有当buf为空时，cp进程才能动作，否则必须等待。,操作系统课程重点、难点解析,37,同步描述 cp: iop: p(sa)； 产生一个数据； 从buf中取数据； p(sb)； v(sb)； 将数据放入buf 打印； v(sa)；,信号灯设置信号灯sa用来表示缓冲区中是否有可供打印的计算结果，其初值为0。sa = 0信号灯sb用以表示缓冲区有无空位置存放新的信息，其初值为1。 sb = 1,操作系统课程重点、难点解析,38,3. 页式存储管理技术,(1) 虚地址结构 当CPU给出的虚地址长度为16位，页面大小为1KB时，在分页系统中地址结构的格式如下,虚存的大小：210 26,虚存的大小：220 212,0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0,操作系统课程重点、难点解析,CPU给出的虚地址长度为32位，页面大小为4KB时,39,(2) 页表与页式存储管理功能之间的关系,页式存储管理功能页式地址变换请调页面淘汰页面,页表,操作系统课程重点、难点解析,40,(3) 页面淘汰算法,先进先出淘汰算法(FIFO算法) 什么是先进先出淘汰算法 总是选择在主存中居留时间最长(即最早进入主存)的一页淘汰。先进先出淘汰算法的实现建立一个页面进入主存的先后次序表；建立一个替换指针，指向最早进入主存的页面；当需要置换一页时，选择替换指向的那一页，然后调整替换指针的内容。,操作系统课程重点、难点解析,41,最久未使用淘汰算法(LRU算法) 什么是最久未使用淘汰算法 总是选择最长时间未被使用的一页淘汰。最久未使用淘汰算法的实现用引用位考察页面的使用情况；当访问页面时，将引用位置1，并记时；当要淘汰一页时，选择时间最长的一页淘汰。,操作系统课程重点、难点解析,42,(4) 页面淘汰算法的例,在一请求分页系统中，某程序在一个时间段内有如下的存储器引用：12、351、190、90、430、30、550（以上数字为虚存的逻辑地址）。假定主存中每块的大小为100B，系统分配给该作业的主存块数为3块。回答如下问题：(题中数字为十进制数) 1对于以上的存储器引用序列，给出其页面走向。 2设程序开始运行时，已装入第0页。在先进先出页面置换算法和最久未使用页面置换算法(LRU算法)下，分别画出每次访问时该程序的主存页面情况；并给出缺页中断次数。,操作系统课程重点、难点解析,43,1. 页面走向0，3，1，0，4，0，5,2. (1) 先进先出页面置换算法0，3，1，0，4，0，5,请求,0,3,1,0,4,0,5,中断,1次,1次,1次,1次,1次,共 5 次,操作系统课程重点、难点解析,44,2. (2) 最久未使用页面置换算法(LRU)0，3，1，0，4，0，5,请求,0,3,1,0,4,0,5,中断,1次,1次,1次,1次,共 4 次,操作系统课程重点、难点解析,45,4. 文件索引结构,(1) 索引文件概念,什么是索引文件 系统为每个文件建立逻辑块号与物理块号的对照表。这张表称为该文件的索引表。文件由数据文件和索引表构成。这种文件称为索引文件。,操作系统课程重点、难点解析,46,索引文件的操作 访问索引文件需要两步操作查文件索引，由逻辑块号查得物理块号由此磁盘物理块号而获得所要求的信息索引文件的特点充分利用磁盘空间易于文件的增删直接读写任意记录,操作系统课程重点、难点解析,47,(2) 索引表的组织多级索引直接索引,文件目录项中有一组表项用于索引。每一个表项登记的是逻辑记录所在的磁盘块号。,操作系统课程重点、难点解析,索引表: 用4个表项作为直接索引。 所支持的文件大小： 4512B,一级间接索引,文件目录项中有一组表项，其内容登记的是第一级索引表块的块号。第一级索引表块中的索引表项登记的是文件逻辑记录所在的磁盘块号。,48,操作系统课程重点、难点解析,索引表: 用4个表项作为一级间接