《操作系统复习提纲v4.ppt》由会员分享,可在线阅读,更多相关《操作系统复习提纲v4.ppt(55页珍藏版)》请在三一文库上搜索。
1、操作系统内容要点,操作 系统,基本概念,处理机管理,设备管理,用户接口,存储管理,文件管理,操作系统定义 OS的目标 OS的作用 OS的特征 OS的主要功能 OS的基本类型,程序的执行 进程的特征和定义 进程的状态 进程的管理 进程的同步和通信 进程和线程 进程调度 死锁,I/O系统 I/O控制方式 缓冲技术 I/O软件组成 设备独立性 设备分配 驱动程序 虚设备技术 通道技术 磁盘调度,文件基本概念 文件的逻辑结构 文件的物理结构 文件目录 外存空间管理 文件共享与保护 数据一致性,用户接口 作业基本概念 批处理系统作业管理 分时系统作业管理,程序的装入与链接 存储管理任务 动态分区分配 交
2、换技术 页式存储管理 段式存储管理 段页式 虚拟存储技术,第二、三章 进程管理,1、进程和线程的概念 2、进程的基本状态及状态转换的原因 3、PCB的作用 4、进程控制的原语操作 5、进程互斥、临界区、进程同步的基本概念、同步准则 6、记录型信号量 7、信号量的应用 8、经典进程同步问题;生产者与消费者问题 9、进程间通信的原理和实现方法 信箱,进程 进程状态及转换 进程控制块 进程控制 进程特征,共享内存 消息缓冲队列 Send/Receive原语 信箱,调度的层次 调度算法的准则 算法: 先来先服务 短作业(进程)优先 时间片轮转 基于优先权 高响应比优先 实时调度算法(EDF),进程同步
3、 进程互斥 临界资源 进程同步机制 信号量 P、V操作 生产者与消费者问题 读者写者问题 哲学家进餐问题,死锁的原因 产生死锁的必要条件 死锁预防 死锁避免 死锁检测和解除 安全状态 银行家算法(避免),多道程序设计,进程基本概念,进程同步互斥,进程间通信,进程调度,死锁,顺序执行 并发执行 前趋图,进程 管理,第二、三章 进程管理的典型问题,进程的三种基本状态及其转变原因。 进程互斥、临界资源 三种经典同步问题及其变型 同步约束条件的分析,信号量的初值的设定 单缓冲区的一个生产者一个消费者同步问题 单缓冲区的一个生产者多个消费者同步问题 多个生产者多个消费者多个缓冲区的同步问题,页式存储管理
4、 段式存储管理 段页式存储管理,虚拟存储器 虚拟存储技术 程序局部性原理 请求分页管理 请求分段管理 页面置换算法 抖动(颠簸),用户程序划分 逻辑地址 内存空间划分 内存分配 管理考虑 硬件支持 地址映射过程,程序装入与链接 对换技术 覆盖技术,寄存器 高速缓存 内存 磁盘缓存 磁盘,单一连续分配 分区分配(固定、动态) 动态重定位分区分配,存储器的层次结构,连续分配方式,离散分配方式,虚拟存储管理,其他,存储 管理,第四、五章 存储管理的重点、难点,重定位的基本概念:为什么要引入 如何提高内存利用率:离散分配、对换机制、动态链接、虚拟存储器、存储器共享 动态分区分配方式:分配、回收算法 基
5、本分页存储管理方式:为什么引入;地址变换机构和过程(含具有快表的情况) 基本分段存储管理方式:为什么引入;地址变换机构和过程(含具有快表的情况);信息的共享和保护 虚拟存储器的基本概念:为什么要引入;特征;实现虚拟存储的关键技术 请求分页系统的基本原理:页表机制;地址变换过程;页面置换算法,第四、五章的典型问题,存储器管理的基本任务 动态重定位的概念、实现方式,什么情况下需要重定位 比较连续分配与离散分配 基于空闲分区链的内存分配与回收算法的应用实例:首次适应法,循环首次适应法,最佳适应法 在某分页系统中,给定内存容量和物理块大小,计算物理块的数量;对给定的进程页表,将给定的逻辑地址,计算出其
6、对应的物理地址并画出地址变换流程图。 在某分段系统中对给定的进程段表,将给定的逻辑地址,计算出其对应的物理地址并画出地址变换流程图。 请求分页系统过程的各种问题,并用流程图的方式表示地址变换过程 对给定的问题,按各种页面置换算法,写页面调入过程,计算和分析缺页率,并对多种算法的性能作比较分析,设备管理重要性 设备独立性 设备分类 设备管理任务 设备管理功能,用户进程 与设备无关软件 设备驱动程序 中断处理程序 设备控制器,SPOOLing技术 共享打印机,设备管理 设备分配回收 独占设备分配 共享设备分配,基本概念,I/O软件组成,缓冲技术,设备处理,虚设备技术,设备驱动程序,设备 管理,磁盘
7、访问时间 磁盘调度 先来先服务 最短寻道时间优先 扫描(电梯算法) CSCAN,磁盘存储管理,第六章设备管理的重点、难点,I/O 控制方式:四种I/O 方式的基本原理;四种I/O 方式由低效到高效的演变 缓冲管理 缓冲的概念,为什么引入缓冲 单缓冲如何提高I/O 速度,它存在哪些不足,双缓冲、循环缓冲又如何提高CPU 与I/O 设备的并行性 缓冲池是为了解决什么问题而引入,引入缓冲池后系统将如何处理I/O 设备和CPU 间的数据输送 缓冲池的工作方式及Getbuf和Putbuf过程 设备独立性 什么是设备独立性 如何实现设备独立性 设备驱动程序,第六章设备管理的重点、难点,虚拟设备和SPOOL
8、ing 技术 什么是虚拟设备 什么是假脱机(SPOOLing)技术,SPOOLing系统的组成 如何利用SPOOLing技术实现共享打印机 磁盘调度 磁盘调度的目标 磁盘访问时间的计算 FCFS、SSTF、SCAN、CSCAN 等算法的应用及这些调度算法的演变过程,分别解决了哪些问题;各算法的性能比较,第五章设备管理的典型问题,各种I/O 控制方式的比较 为什么引入缓冲区 缓冲如何提高I/O 速度 为什么引入设备独立性,如何实现 什么是虚拟设备,实现虚拟设备的关键技术 SPOOLing技术的组成,如何利用SPOOLing 技术实现共享打印机 设备处理程序的功能和处理过程 对各种磁盘调度算法,计
9、算访问次序和平均寻道时间,性能 磁盘访问时间的组成和计算,文件控制块 文件目录 目录文件 目录项 树型目录结构 目录查询技术,文件 文件系统 文件分类 文件操作 文件逻辑结构 外存分配方式,空闲表 空闲链表 位示图,文件目录,文件基本概念,文件存储空间的管理,文件共享与保护,文件 管理,第七、八章文件管理的重点、难点,文件的逻辑结构:顺序文件、索引文件和索引顺序文件 原理和特征 组织方式、访问方法及各种文件形式的比较 外存分配方式:连续分配、链接分配和索引分配原理、优缺点 显示链接FAT、增量式索引分配 目录管理:目录管理的要求 文件控制块(FCB) 索引结点 目录结构:单级、两级和多级 文件
10、磁盘空间管理 空闲表法和空闲链法 位示图法:分配和回收的具体计算,第七、八章 文件管理的典型问题,画出链接分配方式的链接情况和FAT 的链接情况、FAT长度计算等。 增量式索引分配的的寻址方式、地址转换的计算和索引结点的地址映射图(书P259) 对给定的位示图和文件的分配和回收需求,具体写出分配过程和回收过程。 目录管理的要求;目前广泛采用的目录结构及其优点 说明在树形目录结构中线性检索的过程,并画出相应的流程图 文件的共享,第九章 操作系统接口,联机命令接口 联机命令 终端处理程序 命令解释程序 程序接口 系统调用与一般过程调用的区别 中断与陷入 图形用户接口,一个生产者一个消费者n个缓冲区
11、,由于只有一个生产者和一个消费者,不会发生几个生产者和消费者同时存取同一缓冲单元的情况,故无须设置互斥信号量。,假定系统有3个并发进程get 、copy 和put共享缓冲器B1和B2。进程get负责从输入设备上读信息,每读出一条记录后放到B1中。进程copy从缓冲器B1中取出一条记录拷贝后存入B2。进程put取出B2中的记录打印输出。B1和B2每次只能存放一条记录。要求3个进程协调完成任务,使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。,解:,设置4个信号量,其中empty1对应空闲的缓冲区1,其初值为1;full1对应缓冲区1中的记录,其初值为0; empty2对
12、应空闲的缓冲区2,其初值为1;full2对应缓冲区2中的记录,其初值为0。相应进程描述为: get( ) while(ture) 从输入设备读入一条记录; P(empty1); 将记录存入缓冲区1; V(full1); ,copy( ) while(true) P(full1); 从缓冲区1中取出一条记录; V(empty1); P(empty2); 将取出的记录存入缓冲区2 ; V(full2); ,put( ) while(1) P(full2); 从缓冲区2中取出一条记录; V(empty2); 将取出的记录打印出来; Main( ) parbegin(get,copy,put); ,例
13、,一台计算机有10台磁带机被n个进程竞争,每个进程最多需要3台磁带机,那么n最多为_时,系统没有死锁的危险? 解:n最大为4。,补充:关于死锁的公式: 当一个系统有N个并发进程,每个进程都需要M个同类资源,那么最少需要多少资源才能避免死锁的出现? (M-1)*N+1 注:每个进程分配M-1个资源,然后再加上一个资源,该资源无论给哪个进程都可以保证当前系统不会出现死锁。,例,在银行家算法中,若出现下述的资源分配情况: Process Max Allocation Available P0 0 0 4 4 0 0 3 2 1 6 2 2 P1 2 7 5 0 1 0 0 0 P2 3 6 10 1
14、0 1 3 5 4 P3 0 9 8 4 0 3 3 2 P4 0 6 6 10 0 0 1 4 试问: 1)该状态是否安全? 2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它? 3)如果系统立即满足P2的上述请求,系统是否立即进入死锁状态?,解: 1)利用安全性算法对上面的状态进行分析(如下表所示),找到了一个安全序列P0,P3,P4,P1,P2或P0,P3,P1,P4, P2,故系统是安全的。,2) P2发出请求向量Request(1,2,2,2)后,系统按照银行家算法进行检查: Request2(1,2,2,2)Need2(2,3,5,6); Reques
15、t2(1,2,2,2)Available(1,6,2,2); 系统先假定可为P2分配资源,并修改Available,Allocation2和Need2向量: Availabe=(0,4,0,0)Allocation2=(2,5,7,6) Need2=(1,1,3,4) 进行安全性检查:此时对所有进程,条件Needi Available(0,4,0,0)都不成立,即Available不能满足任何进程的请求,故系统进入不安全状态。因此,当进程P2提出请求Request(1,2,2,2)后,系统不能将资源分配给它。 3)系统立即满足进程P2的请求(1,2,2,2)后,并没有马上进入死锁状态。因为,此
16、时上述进程并没有申请新的资源,并未因得不到资源而进入阻塞状态。只有当上述进程提出新的请求,并导致所有没执行完的多个进程因得不到资源而阻塞时,系统才进入死锁状态。,例2:已知某分页系统,主存容量为64K,页面大小为1K,对一个4页大的作业,其0、1、2、3页分别被分配到主存的2、4、6、7块中。 (1)将十进制的逻辑地址1023、2500、3500、4500转换成物理地址? (2)以十进制的逻辑地址1023为例画出地址变换过程图?,答: 逻辑地址1023:1023/1K,得页号为0,页内地址为1023,查页表找到对应的物理块号为2,故物理地址为21K+1023=3071 逻辑地址2500:250
17、0/1K,得页号为2,页内地址为452,查页表找到对应的物理块号为6,故物理地址为61K+452=6596 逻辑地址3500:3500/1K,得页号为3,页内地址为428,查页表找到对应的物理块号为7,故物理地址为71K+428=7596 逻辑地址4500:4500/1K,得页号为4,页内地址为404,因页号大于页表长度,故产生越界中断。,(2)地址变换过程图,例题,对访问串1,2,3,4,1,2,5,1,2,3,4,5,指出在驻留集大小分别为3、4时,使用FIFO替换算法的缺页次数和缺页率。结果说明了什么?,Reference string: 1, 2, 3, 4, 1, 2, 5, 1,
18、2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process) 4 frames FIFO Replacement more frames less page faults ?,先进先出(FIFO)页面置换算法(续),9 page faults,10 page faults,例,一台计算机有四个页框,装入时间、上次引用时间、它们的R(读)与M(修改)位如下表所示(时间单位:嘀嗒),请问NRU、FIFO、LRU算法将替换哪一页?,解答,FIFO算法在需要淘汰某一页时,淘汰最先进入内存的页。在题述条件下,第2页是最先进入内存
19、的页。故FIFO算法将淘汰第2页。 LRU算法在需要淘汰某一页时,淘汰最近最久未使用的页面。在题述条件下,第1页是最近最久未使用的页面。故LRU算法将淘汰第1页。 NRU算法在需要淘汰某一页时,从那些最近一个时期内未被访问的页中任选一页淘汰。在题述条件下,只有第0页是最近一个时期内未被访问的页。故NRU算法将淘汰第0页。,一个磁盘系统,平均寻道时间为12ms,转速为10000转/分,每个磁道有18个扇区,每个扇区512个字节。请问要读取一个扇区所花的时间是多少? 解: TS = 12ms TR = 1/2r = 60100000.5 = 3ms TA=b/rN = 512(10000/60)
20、(18512)= 0.33ms TT = TS + TR + TA =12 + 3 + 0.33 = 15.33ms 答:读取一个扇区所花的时间是15.33ms。,例,磁盘调度,目标:减少寻道时间 1、FCFS(Fisrt Come First Served)先来先服务 特点:公平、简单,寻道时间长,相当于随机访问模式。 仅适用于请求磁盘I/O的进程数目较少的场合。 2、SSTF(Shortest Seek Time First)最短寻道时间优先 SSTF比FCFS有更好的寻道性能 饥饿现象 不能保证平均寻道时间最短 ?,图 5-25 FCFS调度算法,图 5-26 SSTF调度算法,3、SC
21、AN 扫描算法(也称为电梯算法)。 SSTF存在进程“饥饿现象” SCAN算法: 在移动方向固定的情况下采用了SSTF,以避免饥饿现象 存在请求进程等待延迟现象 4、循环扫描CSCAN 磁头单向移动 一个方向读完,不是象SCAN那样回头,而是循环扫描。 请求延迟时间:2TT+Smax,图 5-27 SCAN调度算法示例,图 5-28 CSCAN调度算法示例,例,假定盘块的大小为1KB,硬盘的大小为500MB,采用显示链接分配方式时,其FAT需占用多少存储空间(FAT表项占2.5个字节)?如果文件A占用硬盘的11, 12 , 16, 14四个盘块,试画出文件A中各盘块在FAT表中的链接情况.,解
22、:此时硬盘共有500M/1K=500K个盘块, FAT表项共有500K* 2.5B=1250KB,FAT,FCB,图 混合索引方式,例,存放在某个磁盘上的文件系统,对于采用混合索引分配方式,其FCB中共有13项地址项,第09个地址项为直接地址,第10个地址项为一次间接地址,第11个地址项为二次间接地址,第12个地址项为三次间接地址。如果每个盘块的大小为512字节,盘块号需要3个字节来描述,则每个盘块最多存放170个盘块地址: (1) 该文件系统允许的最大长度是多少? (2) 将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。 (3) 假设某文件的索引结点已在内存中
23、,但其他信息均在外存,为了访问该文件中某个位置的内容,最多需要几次访问磁盘?,文件的最大长度为: 10+170+1702+1703=4942080块=2471040KB 5000/512得商9,余数为392。即逻辑块号为9,块内偏移为392。故可直接从该文件的FCB的第9个地址处得到物理盘块号,块内偏移为392。 15000/512得商为29,余数为152。即逻辑块号为29,块内偏移为152。由于102910+170,而29-10=19,故可从FCB的第10个地址项,即一次间址项中得到一次间址块;并从一次间址块的19项中获得对应的物理盘块号,块内偏移为152。 150000/512得商为292
24、,余数为496。即逻辑块号为292,块内偏移为496。由于10+170292,故可从FCB的第11个地址项,即二次间址项中获得第1个一次间址块;并从该一次间址块的112项中获得对应的物理盘块号,块内偏移为496。,(3) 由于文件的索引结点已在内存,为了访问文件中的某个位置的内容,最少需要1次访问磁盘(即通过直接地址直接读文件盘块),最多需要4次访问磁盘(第一次是读三次间址块,第二次读二次间址块,第三次读一次间址块,第四次是读文件盘块),例,有一个计算机系统利用下图所示的位示图(行号、列号都从0 开始编号)来管理空闲盘块。如果盘块从1开始编号,每个盘块的大小为1KB。 (1)现要从文件分配两盘
25、块,试具体说明分配过程。 (2)若要释放磁盘的第300块,应如何处理?,解,(1)分配过程 线形检索得:i1=2,j1=2; i2=3,j2=6。 计算空闲盘块号: b1=i116+j1+1=216+2+1=35 b2=i216+j2+1=316+6+1=55 修改位示图: 令map2,2=map3,6=1,并将对应块35,55分配出去。,解,(2)释放过程 计算出第300块所对应的二进制行号i和j i=(300-1)/16=18 j= (300-1)% 16=11 修改位示图: 令map18,11=0。,例,用户与OS之间的接口有哪些方式?它们在什么情况下使用的?,解答:用户与操作系统之间的接口有以下方式:命令接口、程序接口、图形用户接口。 命令接口是用户在终端输入命令与系统交互或者是用户通过提交作业控制说明书来控制系统运行。这种方式要求用户记忆所以的命令,有较强的英语应用能力。 程序接口是通过系统调用来实现的,这种接口主要提供给程序员使用,在OS的外层软件或用户程序中,凡是与资源有关的操作都必须通过该接口向操作系统提出服务请求,并由OS代为完成。 图形化用户接口直观、方便、易学,更适合于普通用户使用。,
链接地址:https://www.31doc.com/p-2249099.html