操作系统重点难点解析

1、12从操作系统在计算机系统中从操作系统在计算机系统中的位置来分析的位置来分析 3裸机裸机作作系系统统应应程程序序用用序序程程用用户户操操操作系统定义操作系统定义操作系统的功能操作系统的功能操作系统的实现技术操作系统的实现技术内容庞杂、涉及面广内容庞杂、涉及面广管理、控制所有硬件管理、控制所有硬件管理所有软件，控制程序的执行管理所有软件，控制程序的执行为用户提供良好的接口为用户提供良好的接口实践性强实践性强操作系统原理与实际运行的操作系统的关系操作系统原理与实际运行的操作系统的关系 技术发展快技术发展快基础性和先进性的关系基础性和先进性的关系 4裸机裸机作作系系统统应应程程序序用用序序程程用用户

2、户操操并行处理技术并行处理技术并行性并行性: 处理多个同时性活动的能力处理多个同时性活动的能力并行处理并行处理: 利用多个处理部件，为完成一个整体任务而同利用多个处理部件，为完成一个整体任务而同时执行。时执行。5虚拟技术虚拟技术用户的逻辑视图与操作系统所管理的物理视图分离用户的逻辑视图与操作系统所管理的物理视图分离逻辑视图与的物理视图映射逻辑视图与的物理视图映射 (1) 多用户、多任务同时执行多用户、多任务同时执行(并发执行并发执行)如何描述任务如何描述任务 如何控制任务状态的变化如何控制任务状态的变化 多任务关系如何协调多任务关系如何协调 多任务如何调度多任务如何调度 6同步与互斥同步与互斥

3、进程的引入与进程概念进程的引入与进程概念进程状态及控制进程状态及控制进程调度进程调度(2) 系统资源共享系统资源共享处理机如何共享处理机如何共享 存储器如何共享存储器如何共享 设备如何共享设备如何共享 信息如何共享信息如何共享 7存储分配、地址映射、虚存、存储保护存储分配、地址映射、虚存、存储保护策略、调度、处理机分派策略、调度、处理机分派文件结构、存取方法、磁盘空间分配文件结构、存取方法、磁盘空间分配文件共享、文件保护、文件完整性文件共享、文件保护、文件完整性设备分配、虚拟设备、设备驱动设备分配、虚拟设备、设备驱动 用户的逻辑视图与操作系统所管理的物理视图分离用户的逻辑视图与操作系统所管理的

4、物理视图分离 8应用程序应用程序1，应用程序，应用程序2， 应用程序应用程序nCPU1CPU2虚拟主存虚拟主存1打印机打印机1打印机打印机2虚拟主存虚拟主存2CPU主存主存打印机打印机分时分时主存管理主存管理假脱机打印假脱机打印软软件件硬硬件件9 10操作系统的用户界面操作系统的用户界面进程概念进程概念进程控制进程控制进程同步进程同步进程调度进程调度进程及进程管理进程及进程管理系统资源管理系统资源管理处理机管理处理机管理存储管理存储管理设备管理设备管理文件系统文件系统操作系统与硬件的接口操作系统与硬件的接口 存储程序式计算机存储程序式计算机 11裸机裸机作作系系统统应应程程序序用用序序程程用用

5、户户操操控制控制CPU的工作的工作 访问存储器访问存储器设备驱动、中断处理设备驱动、中断处理控制、管理控制、管理提供方便的用户界面提供方便的用户界面提供优质的服务提供优质的服务 12裸机裸机作作系系统统应应程程序序用用序序程程用用户户操操提供提供OS运行基础运行基础限制了限制了OS的功能实现的功能实现用户需求用户需求提供优质的服务提供优质的服务方便的用户界面方便的用户界面 13多道程序设计技术、分时技术、资源分配与调度等多道程序设计技术、分时技术、资源分配与调度等 单单CPU计算机计算机 计算机网络计算机网络 (多计算机系统多计算机系统)一对矛盾一对矛盾消息传递型多计算机消息传递型多计算机计算

6、机系统结构计算机系统结构操作系统操作系统 进程控制块：进程控制块：PCB进程队列进程队列就绪队列就绪队列各种等待队列各种等待队列运行指针运行指针14 就绪队列头指针就绪队列就绪队列 打印机等待队列头指针打印机等待队列队列打印机等待队列队列运行指针 进程进程控制块控制块 PCB程 序 与 数 据 进程控制进程控制进程调度进程调度功能功能策略策略 15wait_lpt_q_startPCB3PCB7 next打印机等待队列结构打印机等待队列结构runningPCB4 next运行指针运行指针ready_q_start ready_q_startPCB1PCB2PCB9就绪队列结构就绪队列结构nex

7、t创建撤消无无有有消亡消亡等待运行运行等待等待唤醒就绪就绪等待等待 多任务之间的相互制约关系多任务之间的相互制约关系间接的相互制约关系间接的相互制约关系 直接的相互制约关系直接的相互制约关系 16进程的直接相互制约关系进程的直接相互制约关系 互斥互斥同步同步 操作系统提供的同步机构操作系统提供的同步机构 锁、上锁操作、开锁操作锁、上锁操作、开锁操作信号灯、信号灯、P操作、操作、V操作操作 操作系统提供同步机构操作系统提供同步机构 操作系统的资源分配功能操作系统的资源分配功能 两类同步问题：合作进程的执行次序两类同步问题：合作进程的执行次序 共享缓冲区的合作进程的同步共享缓冲区的合作进程的同步

8、17资源描述器定义资源描述器定义 描述描述各类资源的最小分配单位的数据结构称为资源描述器 rd。资源描述器内容资源描述器内容 资源名、资源类型、最小分配单位的大小、地址、分配标志、 描述器链接信息、存取权限、密级、存取时间 资源信息块定义资源信息块定义 描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。资源信息块内容资源信息块内容 请求者队列可利用资源队列资源分配程序等待队列头指针可利用资源队列头指针资源分配程序入口地址18PCB1PCB2PCBn资源分配程序等待队列头指针可利用资源队列头指针资源分配程序入口地址RD1RD2RDm 19资源信息块例资源信息块例中央处理机资源

9、信息块内容中央处理机资源信息块内容 PCB1PCB2PCBk进程调度程序ready-q-start可用处理机信息scheduler-addrCPU描述器 20每一个新产生的请求均排在队尾，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要。排序原则排序原则：按请求的先后次序排序 表头按请求的先后次序先后按自然顺序排列的就绪队列 21 表头按优先级的高低排序高低按优先级高低排列的就绪队列在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。每一个新产生的请求按优先级的高低插入到队列适当的位置上，而当资源可用时，资源分配程序则从队列中选取第一个请求，

10、并满足其需要。排序原则排序原则：按优先级的高低排序 22调度的目标调度的目标 当有大量当有大量I/O请求时，降低完成这些请求时，降低完成这些I/O服务的总时间服务的总时间移臂调度移臂调度 总是选取与当前移动臂前进方向上最近的那个总是选取与当前移动臂前进方向上最近的那个I/O请求，请求，使移臂距离最短。使移臂距离最短。旋转调度旋转调度 总是选取与当前读写头最近的那个总是选取与当前读写头最近的那个I/O请求，使旋转圈请求，使旋转圈数最少。数最少。 2324 运运 行行服务请求(请求I/O等)服务完成/事件来到进程调度 等等 待待 就就 绪绪25 运运 行行服务请求(请求I/O等)服务完成/事件来到

11、进程调度时间片到 等等 待待 就就 绪绪?26 运运 行行服务请求(请求I/O等)服务完成/事件来到进程调度 等等 待待 就就 绪绪27 运运 行行1243 等等 待待 就就 绪绪变迁变迁1 变迁变迁4变迁变迁3 变迁变迁4变迁变迁1 变迁变迁328 若一个程序的执行可以改变另一个程序的变量，那么，后者的输出就可能有赖于各程序执行的相对速度，即失去了程序的封闭性特点。29 设：程序A对做n加1的操作， 程序B打印n值，并将它重新置为零。程序程序A n := n+1; 程序程序B print(n); n := 0; 程序A的n :=n+1与程序B的两个语句的关系 n的初值 打印的结果 n的最终赋

12、值 之前 10 11 0 之后 10 10 1 之间 10 10 0 设n初值为1030锁、上锁原语、开锁原语锁、上锁原语、开锁原语 能实现互斥信号灯、信号灯、P操作原语、操作原语、V操作原语操作原语 能实现同步与互斥互斥的实现相对简单，这里不作讨论31 所谓同步，就是并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。 病员就诊病员就诊 看病活动：看病活动： 要病人去要病人去化验；化验； 等等化验结果；化验结果； 继续诊病；继续诊病；化验活动：化验活动： 需要进行化验需要进行化验 ? 进行进行化验；化验； 开出化验结果；开出化验结果； 32共享缓冲区的

13、计算进程与打印进程的同步共享缓冲区的计算进程与打印进程的同步 计算进程 cp和打印进程 iop公用一个单缓冲 iop cpABCDABCDEE33设：程序A对做n加1的操作，程序B打印n值，并将它重新置为零。PA n := n+1; PB print(n); n := 0; 信号灯设置信号灯设置 s：表示进程A是否执行了加1操作，s = 0 同步描述同步描述 PA n := n+1; v(s ); PB p(s ); print(n); n := 0; 34进程流图进程流图 P3 s fP5P1P2P4P6P9P10P8 f sP5P6P7 s f35 P9P10P8 f s分析任务的同步关系

14、分析任务的同步关系 任务启动后 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操作实现这两个进程的同步。 iop cp

15、分析任务的同步关系分析任务的同步关系 当cp进程把计算结果送入buf时，iop进程才能从buf中取出结果去打印，即当buf内有信息时，iop进程才能动作，否则必须等待。 当iop进程把buf中的数据取出打印后，cp进程才能把下一个计算结果数据送入buf中，即只有当buf为空时，cp进程才能动作，否则必须等待。37 缓冲区bufi op cp同步描述同步描述 cp: iop: p(sa)； 产生一个数据；产生一个数据； 从从buf中取数据；中取数据； p(sb)； v(sb)； 将数据放入将数据放入buf 打印；打印； v(sa)；信号灯设置信号灯设置信号灯sa用来表示缓冲区中是否有可供打印的计

16、算结果，其初值为0。sa = 0信号灯sb用以表示缓冲区有无空位置存放新的信息，其初值为1。 sb = 138 当CPU给出的虚地址长度为16位，页面大小为1KB时，在分页系统中地址结构的格式如下15 10 9 0页号页号 P页内位移页内位移 W虚存的大小：虚存的大小：210 26 p w31 12 11 0页号页号P页内位移页内位移W虚存的大小：虚存的大小：220 212mov r1 ,205012301KB2KB3KB1作业2地址空间20020500 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 CPU给出的虚地址长度为32位，页面大小为4KB时39页式存储管理功能页式存储管

17、理功能页表页表 页页 号号 主存块号主存块号 中断位中断位 辅存地址辅存地址 引用位引用位 改变位改变位页式地址变换页式地址变换请调页面请调页面淘汰页面淘汰页面40先进先出淘汰算法先进先出淘汰算法(FIFO算法算法) 什么是先进先出淘汰算法什么是先进先出淘汰算法 总是选择在主存中居留时间最长总是选择在主存中居留时间最长(即最早进入主存即最早进入主存)的一的一页淘汰。页淘汰。先进先出淘汰算法的实现先进先出淘汰算法的实现建立一个页面进入主存的先后次序表；建立一个页面进入主存的先后次序表；建立一个替换指针，指向最早进入主存的页面；建立一个替换指针，指向最早进入主存的页面；当需要置换一页时，选择当需要

18、置换一页时，选择替换指向的那一页，然后替换指向的那一页，然后调整替换指针的内容。调整替换指针的内容。41最久未使用淘汰算法最久未使用淘汰算法(LRU算法算法) 什么是最久未使用淘汰算法什么是最久未使用淘汰算法 总是选择最长时间未被使用的一页淘汰。总是选择最长时间未被使用的一页淘汰。最久未使用淘汰算法的实现最久未使用淘汰算法的实现用引用位考察页面的使用情况用引用位考察页面的使用情况；当访问页面时，将引用位置当访问页面时，将引用位置1，并记时，并记时；当要淘汰一页时，选择时间最长的一页淘汰当要淘汰一页时，选择时间最长的一页淘汰。42在一请求分页系统中，某程序在一个时间段内有如下的存储器引用：12、

19、351、190、90、430、30、550（以上数字为虚存的逻辑地址）。假定主存中每块的大小为100B，系统分配给该作业的主存块数为3块。回答如下问题：(题中数字为十进制数) 1对于以上的存储器引用序列，给出其页面走向。 2设程序开始运行时，已装入第0页。在先进先出页面置换算法和最久未使用页面置换算法(LRU算法)下，分别画出每次访问时该程序的主存页面情况；并给出缺页中断次数。431. 页面走向页面走向0，3，1，0，4，0，52. (1) 先进先出页面置换算法先进先出页面置换算法0，3，1，0，4，0，5003031031314140405请求0310405中断1次次1次次1次次1次次1次次

20、共共 5 次次442. (2) 最久未使用页面置换算法最久未使用页面置换算法(LRU)0，3，1，0，4，0，5003031310104140405请求0310405中断1次次1次次1次次1次次共共 4 次次45 文件目录文件A索引表指针文件A目录项 r0 r1 0 23 1 19 2 26 3 29 r2 r3磁盘块号 23磁盘块号 19磁盘块号 26磁盘块号 29文件索引表逻辑块号物理块号什么是索引文件什么是索引文件 系统为每个文件建立逻辑块号与物理块号的对照表。这张表称为该文系统为每个文件建立逻辑块号与物理块号的对照表。这张表称为该文件的索引表。文件由数据文件和索引表构成。这种文件称为索

21、引文件。件的索引表。文件由数据文件和索引表构成。这种文件称为索引文件。46索引文件的操作索引文件的操作查文件索引，由逻辑块号查得物理块号查文件索引，由逻辑块号查得物理块号由此磁盘物理块号而获得所要求的信息由此磁盘物理块号而获得所要求的信息索引文件的特点索引文件的特点充分利用磁盘空间充分利用磁盘空间易于文件的增删易于文件的增删直接读写任意记录直接读写任意记录47文件A目录项 r0 r1文件目录 r2 r3磁盘块号 23磁盘块号 89磁盘块号 126磁盘块号 229 23 89 126 229 文件目录项中有一组表项用于索引。每一个表项登记的是文件目录项中有一组表项用于索引。每一个表项登记的是逻辑记录所在的磁盘块号。逻辑记录所在的磁盘块号。 索引表索引表: 用4个表项作为直接索引。 所支持的文件大小：所支持的文件大小： 4512B 文件目录项中有一组表项，其内容登记的是第一级索引表文件目录项中有一组表项，其内容登记的是第一级索引