操作系统 --- 期末复习
本文主要是介绍武汉理工大学操作系统这门课程的期末考试重点。重点章节:进程调度、处理机调度、存储管理、文件管理第一章 绪论操作系统的地位:紧贴硬件(裸机)之上,在所有软件之下。提供其他软件的支持环境,是计算机资源的管理者。操作系统也是软件(系统软件)虚拟机(扩展机):经过操作系统提供的资源管理功能和方便用户的各种服务功能能把裸机改造为功能更强、使用更方便的机器。虚拟化技术的实例:内存技术的虚拟化、V
目录
前言
本文主要是介绍武汉理工大学操作系统这门课程的期末考试重点。
重点章节:进程调度、处理机调度、存储管理、文件管理
第一章 绪论
操作系统的地位:紧贴硬件(裸机)之上,在所有软件之下。提供其他软件的支持环境,是计算机资源的管理者。
操作系统也是软件(系统软件)
虚拟机(扩展机):经过操作系统提供的资源管理功能和方便用户的各种服务功能能把裸机改造为功能更强、使用更方便的机器。
虚拟化技术的实例:内存技术的虚拟化、VPN;
操作系统的定义:1)操作系统是系统软件,由一整套程序组成;2)OS的基本职能;3)OS为用户提供友好、可靠、安全的服务。
OS的基本职能:管理和控制计算机系统中的硬件及软件资源;合理地组织计算机工作流程
操作系统的作用:OS作为计算机系统的资源管理者;OS作为用户与计算机硬件之间的接口;OS作为虚拟机、扩展机。
操作系统的功能:1)存储管理;2)处理机管理;3)设备管理;4)文件管理;5)用户接口
操作系统的特征:并发性、共享性、虚拟性、异步性。
并发性
并发:指两个或两个以上的事件或活动在同一时间间隔内发生
并行:指在同一时刻发生。
并发、并行与多线程的关系:并行需要两个或两个以上的线程跑在不同的处理器上,并发可以跑在一个处理器上通过时间片进行切换。
操作系统是一个并发系统。各进程间的并发,系统与应用间的并发,都是由操作系统来管理的。
在多道处理器中,宏观上并发,微观上交替执行(单处理器)。
程序的静态实体是可执行文件,而动态实体是进程(任务),并发是指进程。
共享性
共享:操作系统中的资源可被多个并发执行的进程所使用。操作系统要对系统资源进行合理分配和使用。
资源共享的方式:互斥共享 、 同时访问
互斥共享:资源分配后到释放前,不能被其他进程所使用。例如:音频设备
同时共享:一些资源允许同一时间内多个进程对它进行共享。例如:磁盘
虚拟性
虚拟是操作系统中的一种管理技术。把物理上一个实体变成逻辑上多个对应物(一变多)或把物理上多个实体变成逻辑上一个对应物(多变少)。
虚拟性的实现:
异步性
异步性:进程执行顺序和执行时间的不确定性。
异步性的体现:
进程的运行速度不可预知:分时系统中,多个进程并发执行,“时走时停”,不可预知每个进程的运行推进快慢。
程序运行发生错误或异常的时刻是随机的;难以重现系统在某个时刻的状态(包括重现运行中的错误)
各种各样硬件和软件中断事件发生的时刻是随机的。
练习题
1)操作系统的职能是什么?
2)什么是操作系统的基本功能?
3)多道程序设计和多重处理的区别是什么?
第二章 用户界面
作业的定义:是要求计算机系统按指定步骤对应用程序进行处理并得到计算结果的加工作。
在一次应用业务处理过程中,从输入开始到输出结束,用户要求计算机所做的有关该次业务处理的全部工作。
批处理系统中,作业是抢占内存的基本单位。
作业步:对应用程序进行处理的步骤。
作业与作业步的关系
1)作业由不同的顺序相连的作业步组成。
2)作业步是在一个作业的处理过程中,计算机所做的相对独立的工作。
作业的组成:作业由程序、数据和作业说明书三部分组成。
程序和数据:完成用户所要求的业务处理工作。
每个作业至少包含一个程序
作业说明书:体现用户的控制意图。系统通过作业说明书控制文件形式的程序和数据,使之执行和操作。
作业的控制方式
脱机作业控制:用户输入作业说明书,整个作业的运行由系统控制。执行过程中,用户无法干涉
联机作业控制:通过人-机会话方式控制作业运行。
练习题
1)什么是作业和作业步
2)作业由哪几部分组成,这几部分各有什么功能?
3)什么是系统调用?系统调用与一般用户程序有什么区别?
第三章 进程调度
进程的基本概念
进程的定义:进程是指一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。
进程分类:系统进程和用户进程。
系统进程:起着资源管理和控制的作用,或者执行操 作系统核心代码的进程。
用户进程:执行用户程序的进程。
进程与程序的关系:进程是程序的一次执行过程,有一定的生命期;通过多次执行,一个程序可对应多个进程;通过调用关系,一个进程可包括多个程序。
进程和作业的区别
进程 : 已提交完毕程序的执行过程的描述,是资源分配的基本单位。
作业 : 是用户需要计算机完成某项任务时要求计算机所做工作的集合。
作业是用户向计算机提交任务的任务实体,进程则是完成用户任务的执行实体。一个作业可由多个进程组成,且至少必须由一个进程组成,但反过来不成立。
进程的特征:并发性;动态性;调度性;交互性;异步性;结构性。
进程的组成:进程通常由程序、数据集合和进程控制块PCB三部分组成。
进程上下文:是对进程执行活动全过程的静态描述, 包括PCB结构、与执行该进程有关的各种寄存器的值、正文集(程序段在经过编译之后形成的机器指令代码集)、数据集及各种堆栈值。
进程的状态(重点)
进程在系统中的活动规律:执行 --> 暂停 --> 执行
进程的三种基本状态:就绪状态、运行状态、等待状态(阻塞、挂起、睡眠)
三态模型
就绪状态
处于就绪状态的进程已经得到除CPU之外的其他资源,只要由调度得到处理机,便可立即投入执行。
可以有多个进程处于就绪态。
运行状态
进程调度程序从就绪队列中选择一个进程分配给它CPU 控制权,该进程所处的状态为运行状态。
在单CPU系统中,总只有一个进程处于运行状态
等待状态
进程因等待某个事件的发生(如等待I/O的完成),而暂停执行,则称该进程处于等待状态(即使给它 CPU时间,它也无法执行)
可以有多个进程处于等待状态
就绪态、等待态、运行态是最基本的进程状态,如果不成立:
没有运行态:就不知道哪个进程在使用处理机。
没有就绪态:就无法有效地挑选出合适运行的进程,或者挑选出的进程根本就不能运行。
没有等待态:就无法区分各个进程除了缺少CPU资源外是否还缺少其他资源。
三个基本态的作用:准备运行的进程和不具备运行条件的进程就不会混杂在一起。
进程状态的转换模型
原语
定义:是在系统态下执行的完成系统特定功能的程序段
特点:原语是一个不可分割的基本单位,原语操作具有原子性,既在执行过程中不允许被中断,且不能并发执行
作用:原语是一种特殊的系统调用,为了实现进程的控制和通信。
原子性:要么一起成功,要么一起失败。
进程互斥
临界资源:一次仅允许一个进程使用的资源称为临界资源。例如:电话、打印机等
临界区:每个进程中访问临界资源的那段程序段称为临界区(临界段),简称CS区。
进程互斥:进程 A 和进程 B 不能在同一时刻执行。
信号量:是一个确定的二元组(s,q),s是一个具有非负初值的整型变量,q 是一个初始状态为空的队列。
- 信号量只能通过初始化和两个标准的原语(P&V)来访问: 作为OS核心代码执行,不受进程调度的打断。
- 初始化指定一个非负整数值,表示空闲资源总数。
信号量的物理含义:
P原语操作
V原语操作
PV原语形成进程同步
私用信号量:是一种同步机制,用于在多个进程或线程之间控制对共享资源的访问。私用信号量只能由创建它的进程或线程使用,并且不能被其他进程或线程访问。
私用信号量与公用信号量不同,后者可以由多个进程或线程共享。私用信号量通常用于限制单个进程或线程对资源的访问,以确保数据的完整性和一致性
PV语句例题:黑白棋分拣;生产者-消费者问题;哲学家就餐问题;公交车服务问题;理发师问题
死锁
定义:指两个或多个并发进程彼此相互等待对方所拥有的资源,且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源,而无法继续向前推进的状态。
死锁产生的原因
竞争资源:系统中配备的非剥夺性资源的数量不能满足每个进程运行的需要时,会使进程因争夺资源而陷入僵局。
进程推进顺序不合理:进程在运行过程中,请求和释放资源的顺序不当。例如:两个并发进程按照顺序p_0, p_1, q_0, q_1, p_2, q_2 运行就会出现死锁情况,D、T为不可剥夺性资源,而且通常这是一个编程导致的错误。
产生死锁的必要条件(缺一不可)
- 互斥条件:进程要求对所分配的资源进行排它性控制,即在一段时间内某个资源仅为一个进程所占有。(涉及的资源是临界资源)
- 部分分配(请求和保持条件):进程每次申请它所需要的一部分资源,在等待新资源的同时,继续占有已经分配到的资源。
- 不剥夺条件:进程已获得的资源,在没有使用完之前,不能被剥夺,只能在使用完时由自己释放。
- 环路条件:在发生死锁时,必然存在一种进程-资源的循环链,链中每一个进程已获得的资源同时被下一个进程所请求。
显然,只要使上述4个必要条件中的某一个不满足,则死锁就可以排除。
排除死锁的方法
- 预防死锁:破坏死锁的必要条件中的一个或多个。
- 避免死锁:防止系统进入不安全状态(银行家算法)
- 检测与解除死锁:系统设有专门的机构,当发生死锁时,该机构能够检测到死锁发生的位置和原因,并能通过外力破坏死锁发生的必要条件,从而使得并发进程从死锁中恢复出来。(检测:程序员的经验;解除:撤销进程、资源剥夺、进程回退)
线程
进程:程序的一次执行过程和资源分配的基本单位。
线程:比进程更小的独立运行的基本单位;一个进程中可以有多个线程,它们共享这个进程的资源。
引入线程的目的是简化线程间的通信,以小的开销来提高进程内的并发程度。
线程的分类:用户级线程与核心级线程
进程与线程的区别
1)地址空间和其他资源:进程间相互独立,同一进程的各线程间共享。
2)通信:进程间通信IPC,线程间可以直接读写进程数据段(如全局变量)来进行通信--需要线程同步和互斥手段的辅助,以保证数据的一致性。
3)调度:线程上下文切换比进程上下文切换要快得多。进程调度和切换都是由操作系统内核来完成,而线程既可由操作系统内核来完成也可由用户程序来完成。
4)状态:线程和进程一样,都有自己的状态,也有相应的同步机制。不过,由于线程没有单独的数据和程序空间。因此,线程不能像进程的数据与程序那样交换到外存存储空间。
练习题
1)进程获取处理器运行时通过调度得到的。( )
2)优先级是进程调度的重要依据,一旦确定不能改动。 ( )
3)在单处理系统中。任何时刻都只有一个进程处于运行态。 ( )
4)进程申请处理器而得不到满足时,其状态会变为等待态。 ( )
5)在正常单处理系统中,若同时存在10个进程,则处于就绪队列中的进程最多有( )个。处于等待队列最多有( )个。
6)系统进程所请求的一次I/O操作完成后,将使进程状态从( )(A)运行态变为就绪态 (B) 运行态变为阻塞态 (C)就绪态变为运行态 (D)阻塞态变为就绪态
7)两家旅行社去航空公司订机票,形成互斥资源的是( )(A)旅行社 (B) 航空公司 (C) 飞机票 (D)旅行社或航空公司
8)死锁的避免是根据( ) 采取措施实现。A. 配置足够的系统资源 B. 使进程的推进顺序合理 C. 破坏死锁的四个必要条件之一 D. 防止系统进入不安全状态
9)某计算机系统中有8台打印机,由K个进程竞争使用,每个进 程最多需要3台打印机。该系统可能会发生死锁的K的最小值 是( ) A. 2 B. 3 C. 4 D.5
第四章 处理机调度
处理机:计算机系统中存储程序和数据,并按照程序规定的步骤执行指令的部件。
作业与进程的关系:
作业是用户向计算机提交任务的任务实体。
进程是计算机为了完成用户任务实体而设置的执行实体。
计算机要完成一个任务实体,必须要有一个以上的执行实体,即一个作业是由一个以上的进程组成。
系统必须为一个作业创建一个根进程,然后再根据任务要求创建相应的子进程。
调度算法性能的衡量(重点)
CPU利用率 = CPU工作时间 / 占用CPU总时间
系统吞吐量 = 单位时间内完成的作业数量
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = : 第i个作业的周转时间;N:作业的总数
带权周转时间 = 周转时间 / 作业执行时间
平均带权周转时间 = : 第i个作业的带权周转时间;N:作业的总数
等待时间 = (作业周转时间 - 作业执行时间)
平均等待时间 = 等待时间 / 作业总数
响应时间 = 作业首次开始执行的时间 - 作业提交的时间
进程调度
进程切换的步骤:1)检查状态是否可以切换(原语执行时不可切换)。2)保存被切换的进程的现场,并转移到合适的队列(阻塞、就绪)。3)选取一个新的进程。4)恢复被选中进程的现场。
进程调度的原因:1)正在执行的进程运行完毕,或由于某种错误而终止运行。2)执行中的进程自己调用阻塞原语,将自己阻塞起来进入等待状态。3)执行中的进程执行了P原语操作,因资源不足而被阻塞,或执行了V原语操作激活了等待资源的进程队列。4)执行中的进程提出I/O请求后被阻塞。5)执行完系统调用,在系统程序返回用户进程时,可调度选择一新的用户进程执行。6)分时系统中时间片到。7)当有一个优先级更高的进程就绪(可抢占式)
进程调度的方式:非抢占式(进程自己让出CPU)与抢占式(强行剥夺正在执行的进程的CPU)
进程调度的调度算法(大题重点)
1)先来先服务算法(FCFS)
2)短作业优先法(SJF)
3)最高响应比优先法(HRN) 响应比 = 1 + 作业等待时间 / 运行时间
4)时间片轮转法(RR)
5)多级队列算法
6)优先级法 1)静态优先级;2)动态优先级;3)线性优先级调度算法
7)多级反馈轮转法(RRMF)
算法评价
练习题
1)设有4个作业同时到达,每个作业的执行时间均为2h,他们在一台处理机上按单道式运行,这平均周转时间为( ) A. 1h B. 5h C. 2.5h D. 8h
2)作业是用户提交的,进程是由系统自动生成的,除此之外,两者的区别是() A. 两者执行不同的程序段 B. 前者以用户任务为单位,后者以操作系统控制为单位 C. 前者是批处理的,后者是分时的 D. 后者是可并发执行,前者则不同
第五章 存储管理
基本概念
外存储器:外存和辅存
CPU不能直接访问的存储器;用来存放用户的各种信息,存取速度相对于内存要慢得多,但可用来长期保存。
内存储器:内存和主存
CPU能直接访问的存储器;用来存放系统和用户的程序和数据,其特点是存取速度快,存储方式是以旧换新,断电信息丢失。
内存地址:把内存分成若干个大小相等的存储单元,每个单元占8位,即1字节。每个存储单元给一个编号,称为内存地址。
内存地址空间:内存地址的集合称为内存地址空间,它是一个一维的线性空间。
逻辑地址:用户编程时所用的地址;物理地址:内存单元的绝对地址
地址映射:将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。
分区管理:固定分区法与动态分区法
固定分区法:系统初始化时将内存固定地划分区域;适用于内存大小固定且不需要频繁地增加或减少的情况。
动态分区法:在作业的处理过程中划分区域(根据需要确定大小);适用于内存大小不确定且需要频繁增加或减少的情况。
常见的动态分区算法(重点):
最先适应法(first-fit):按分区起始地址的递增次序,从头查找,找到符合要求的第一个分区。
最佳适应法(best-fit):按分区大小的递增次序,从头查找,找到符合要求的第一个分区。
最坏适应法(worst-fit):按分区大小的递减次序,从头查找,找到符合要求的第一个分区。
三种算法的比较:
最先适应法:1)尽可能的利用了低地址空间;2)分配和释放的时间性能好。
最佳适应法:1)利用最接近于所要求的内存大小。2)容易形成“碎片”。3)寻找较大的空闲区所需要的时间长。
最坏适应法:1)避免了空闲区越分越小、留下碎片的问题。
查找速度 | 释放速度 | 空闲区利用 | 碎片利用 | |
最先适应法 | 好 | 好 | 次 | 次 |
最佳适应法 | 差 | 次 | 好 | 差 |
最坏适应法 | 差 | 次 | 差 | 好 |
固态分区与动态分区的比较
固态分区:1)适用于内存大小固定且不需要频繁地增加或减少的情况。在固定分区中,内存会被预先划分为几个静态的、大小相等的区域,每个区域可以用于存储不同类型的数据或程序。2)固定分区的优点是简单、易于管理和保证系统性能稳定;缺点是可能会导致浪费和碎片化,并且难以适应内存需求的变化。
动态分区:1)适用于内存大小不确定且需要频繁增加或减少的情况。在动态分区中,内存会根据当前的内存需求动态地分配给进程使用。2)动态分区的优点是可以更好地利用内存,减少浪费和碎片化,并且可以适应内存需求的变化;缺点是需要更复杂的管理和调度算法,可能会影响系统性能。
页式管理
分页的概念
逻辑空间分页 :程序地址空间分成大小相等的页(页面的大小为 ,通常1KB,2KB,nKB 等)。每页都有一个页号,从0开始编排。
内存空间分块 :把内存也按页的大小分成内存块或页面,同样从0开始编排。
内存分配原则:当一个用户程序装入内存时,以页为单位进行分配,并且一个进程的若干页可分别装入物理上不相邻的内存块中。
页式管理中的逻辑地址表示:在分页存储管理中,用户程序中的逻辑地址包括页号和页内地址(页内位移)。
如果给定页面大小为L,逻辑地址是A,则页号和页内位移可按下式计算:
例如:假设设某系统的页面大小为1KB(2^10=1024),A=3456,则P=3,d=384。
页表结构
页号 | 块号 | 存取结构 |
页式地址映射(逻辑地址到物理地址)
页式管理中的常见置换算法
- 随机淘汰算法:随机地选择某个用户的页并将其换出
- 轮转法(RR):循环换出内存可用区内一个可以被换出的页。
- 先进先出(FIFO):选择在内存驻留时间最长的页将其淘汰。
- 最近最久未使用页面置换算法(LRU):当需要淘汰一页时,选择最长时间未使用的页。
- 理想型淘汰算法(OPT):当需要淘汰一旧页时,选址以后不再使用的页,或者是以后相当长的时间内不会使用的页。
置换算法评价指标:缺页次数和缺页率(缺页次数和缺页率)
Belady现象
正常情况:对于任一作业或进程,如果给它分配的内存块数越接近于它所要求的页面数,则发生缺页的次数会越少。
Belady现象:使用FIFO算法时,在未给进程或作业分配足够它所需要的块数时,有时会出现分配的块数增多,缺页次数反而增加的现象
分段管理
含义:一个用户程序往往由几个程序段(主程序、子程序和函数)所组成,把程序按内容或过程关系分段,每段有自己的名字(段号)。每个段都从0开始编址,采用一段连续的地址空间。各段的长度可以不等。
段式管理中的逻辑地址结构表示:段式管理把二维虚拟地址空间设计成段号S与段内相对地址W。
段号S | 段内相对地址W |
段表结构:
段号 | 始址 | 长度 | 存取方式 | 内外 | 访问位 |
分页和分段的异同:
相同点:在内存中都不是整体连续,且均通过地址映射机构将逻辑地址映射到物理内存。
不同点:1)页是信息的物理单位。用户不需要把程序分页,完全是系统管理的要求;段是信息的逻辑单位。每一段在逻辑上是相对完整的一组信息。分段更好地满足了用户的需求。2)页的大小是固定的,且在同一系统中大小相等;段的大小因段而异,取决于用户编写的程序。3)分页的作业地址空间是一维的;分段的作业地址空间是二维的。
段式地址映射(逻辑地址到物理地址)
段页式管理
基本思想:用分段方法来管理和分配虚拟存储器,而用分页方法来管理和分配内存(主存储器) 1)可以保持分段地址空间所带来的优点,如允许段的动态扩展,可实现段的动态链接,段的共享,实施 段保护措施等等。 2)利用页式管理解决主存分区的拼接,辅存的管理以及对分段大小限制等问题。
分段+分页
将地址空间按照程序自身的逻辑关系划分为若干个段,再将各段分为大小相等的页面
将内存空间分为与页面大小相等的一个个内存块,系统以块为单位为进程分配内存
段页式管理中的逻辑地址结构表示:
段号S | 段内页号P | 页内位移d |
段表与页表
每个段对应一个段表项。各段表项长度相同,由段号、页表长度、页表存放地址 组成。
段号 | 页表长度 | 页表始址 |
每个页对应一个页表项。各页表项长度相同,由页号、页面存放的内存块号 组成。
页号 | 块号 |
段页式地址映射(逻辑地址到物理地址)
总结
页式管理一共需要访问2次内存:第一次访问页表,第二次访问目标
段式管理一共需要访问2次内存:第一次访问段表,第二次访问目标
段页式管理一共需要访问3次内存:第一次访问段表,第二次由段表访问页表,第三次访问目标
练习题
1)动态重定位是在作业的( )中进行的。A.编译过程 B.装入过程 C.修改过程 D.执行过程
2)可变分区管理方式按作业需求量分配主存分区,所以( )。A. 分区的长度是固定 B.分区的个数是确定的 C.分区长度和个数都是确定的 D.分区的长度和个数是不确定的
第八章 文件管理
文件系统出现的原因:大容量磁盘、磁带等的出现,为程序和数据等软件资源的透明存取提供了物质基础。这导致了对软件资源管理质的飞跃。
文件系统功能
系统角度
- 文件空间管理:为合理地存放文件,必须对文件空间进行统一管理。
- 逻辑结构:为了实现按名存取,需要有一个用户可见的文件逻辑结构,用户按照文件逻辑结构所给定的方式进行信息存取和加工。
- 物理结构:为了便于存放和加工信息,文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。
- 信息查找:完成对存放在存储设备上的文件信息的查找。
- 信息共享与保护
用户角度:按名存取
文件类型
目的:对不同文件进行管理, 提高系统效率。
按文件性质和用途分类
系统文件:OS及各种系统程序的信息所组成的文件。
用户文件:用户委托保存的文件,如源程序文件、用户数据库文件等。
库文件:标准子程序及常用应用程序组成的文件。
按文件的保护方式分类
只读文件、读写文件、执行文件、不保护文件
按文件组织和处理方式分类
普通文件:组织形式为一般格式的文件,如ASCII或二进制文件。
目录文件:由文件的目录信息构成的文件,用于检索普通文件。
特殊文件:所有输入输出设备都被看作特殊文件(UNIX系统)。
文件物理结构
常见的文件物理结构:顺序结构(连续文件分配方式)、链接结构(串联文件分配方式)、索引结构(索引文件分配方式)
顺序结构(连续文件分配)
优点:结构简单;存取速度快
缺点:不能动态增加;部分删除后会有“碎片”
局限性:不适于存放用户文件、数据库文件等经常被修改的文件。
链接结构(串联文件分配)
特点:文件长度可动态地增长;搜索效率较低;只适用于逻辑上连续的文件,且存取方法应该是顺序存取的;不适宜随机存取。
索引结构(索引文件分配)
特点:既可以满足文件动态增长的要求,又可以较为方便和迅速地实现随机存取;索引表需要占用一定的存储空间:增加了存储空间的开销;至少二次访问存储器,多级索引访问次数更多。
存在的问题:一个文件过大,一个磁盘块装不下文件的整张索引表。
解决方案:多级索引与混合索引
多级索引:索引表所指的物理块中存放的不是文件信息,而是装有这些信息的物理块的地址。
混合索引:将索引表的头几项设计成直接寻址方式,也就是这几项所指的物理块号中存放的是文 件信息,而索引表的后几项设计成多重索引,也就是间接寻址方式。
文件存储设备:顺序存取设备与直接存取设备
顺序存取设备:磁带
特点:只有在前面的物理块被存取之后,才能存取后续的物理块的内容。
直接存取设备:磁盘
磁盘设备允许文件系统直接存取磁盘上的任意物理块。为了存取一个特定的物理块,磁头将直接移动到所要求的位置上,而不需要像顺序存取那样事先存取其他的物理块。
一次访盘的请求由三个动作组成:寻道、旋转延迟、数据传输。
磁盘调度(寻道)算法(重点)
先来先服务算法(FCFS):按访问请求到达的先后次序服务
最短寻道时间优先算法(SSTF):优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先。
扫描算法(SCAN,电梯算法):磁头只有移动到最外侧,才可以向内移动。
优点:克服了最短寻道优先的缺点,既考虑了距离,同时又考虑了方向。(先方向后距离)。
文件存储空间的管理
常见方法:空闲文件目录法;空闲块链法;成组链接法;位示图法
空闲块表(空闲文件目录):将所有空闲块记录在一个表中,即空闲块表。
空闲块链表:把所有空闲块链成一个链。
成组链接法(空闲块链的扩展):把文件存储设备中的所有空闲块按50块分为一组。
位图法:用一串二进制位反映磁盘空间的分配使用情况, 每个物理块对应一位, 分配物理块为1,否则为0。
文件目录管理
分类:单级目录;二级目录;多级目录
单级目录:系统为所有存入系统的文件建立一张表,每一文件有一个表目
在单级目录表中,各文件说明项处于平等地位。文件名与文件 一一对应。实现“按名存取”
优点:简单且能实现按名存取。
缺点:不允许重名;当目录项过多时,查找速度慢;不便于共享。
二级目录:各个文件的说明信息被组织成目录文件, 且以用户为单位把各自的文件说明划分为不同的组。
目录分为两级:主文件目录(MFD)与用户文件目录(UFD)。
优点:解决了文件的重名问题和文件共享问题,提高搜索速度,查找时间降低
缺点:不太适合大量用户和大量文件的大系统,增加了系统开销。
多级(树形)目录:除了最低一级的物理块中装有文件信息外,其它每一级目录中存放的都是下一级目录或文件的说明信息。
优点:层次结构清晰,便于管理和保护;解决重名问题;查找速度加快。
便于共享的文件目录的方法:绕道法;链接法;基本文件目录法BFD
绕道法:用户对所有文件的访问都是相对于当前目录进行的。
链接法:将一个目录中的链接指针直接指向被共享文件所在的目录。(链接法仍然需要用户指定被共享的文件和被链接的目录)
练习题
文件系统的主要目的是( )A. 实现虚拟存储 B. 提高外存的读写速度 C. 用于存储系统文件 D. 实现对文件的按名存储
面向用户的文件组织属于( )A. 虚拟结构 B. 实际结构 C. 逻辑结构 D. 物理结构
磁盘与主机之间传递数据的单位是( )A. 柱面 B. 磁道 C. 数据块 D. 记录
文件系统采用多级目录结构的目的是( ) A.减少系统开销 B.节省存储空间 C.解决命名冲突 D.缩短传送时间
第九章 设备管理
数据传送的方式
数据传送的方式:程序直接控制方式、中断控制方式、 DMA方式及通道控制方式
程序直接控制方式:由用户进程来直接控制内存/CPU和外围设备之间的信息传送。这种方式的控制者是用户进程。
优点:控制简单,不需要多少硬件支持。
缺点:1)CPU的利用率大大降低;2)不能实现设备之间的并行工作;3)无法发现和处理由于设备或其他硬件所产生的错误。
中断控制方式:求CPU与设备(或控制器)之间有相应的中断请求线,在设备控制器的控制状态寄存器中有相应的中断允许位。减少程序直接控制方式中CPU等待时间以及提高系统的并行工作程度。
优点:CPU的利用率大大提高;能支持多道程序和设备的并行操作。
缺点:一次数据传送过程中,可能发生较多次的中断;可能造成CPU无法响应中断和出现数据丢失现象。
DMA方式:在外围设备和内存之间开辟直接的数据交换通路。DMA方式挪用CPU的一个工作周期把数据缓冲寄存器中的数据直接送到内存地址寄存器所指向的内存区域。从而,DMA控制器可用来代替CPU控制内存和设备之间进行成批的数据交换。
DMA方式与中断方式的区别:CPU进行中断处理的次数大大减少;排除了因并行操作设备过多时CPU来不及处理或因速度不匹配而造成数据丢失等现象
DMA方式的局限性:DMA方式对外围设备的管理和某些操作仍由CPU控制;多个DMA控制器的同时使用是不经济的,且会引起内存地址的冲突并使得控制过程进一步复杂化。
通道控制方式:通道是一个独立于CPU的专门负责I/O控制的处理机。它有自己的指令系统,通道指令受CPU启动,并在操作结束时向CPU发中断信号。
通道的类型:字节多路通道、数组多路通道、选择通道
通道控制方式与DMA方式的比较
相同点:以内存为中心,实现设备和内存的直接数据交换
不同点:1)DMA方式中,数据的传送由CPU控制;通道方式中,由专管输入输出的硬件“通道”来进行控制。2)DMA方式中,每台设备至少一个DMA控制器;通道控制方式中,一个通道可控制多台设备与内存的数据交换
中断技术
中断:指计算机在执行期间,系统内发生非寻常的或非预期的急需处理事件,使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序。待处理完毕后又返回原来中断处继续执行或调度新的程序执行的过程。
按照中断产生的条件,中断可以分为:外中断与内中断
中断和陷阱的主要区别:(1) 陷阱通常由处理机正在执行的现行指令引起,而中断则是由与现行指令无关的中断源引起的。 (2) 陷阱处理程序提供的服务为当前进程所用,而中断处理程序提供的服务则不是为了当前进程的。 (3) CPU在执行完一条指令之后,下一条指令开始之前响应中断,而在一条指令执行中也可以响应陷阱。 (4) 有的系统中,陷进处理程序被规定在各自的进程上下文中执行,而中断处理程序则在系统上下文中执行。
硬中断:中断和陷阱要通过硬件产生相应的中断请求。
软中断:通信进程之间用来模拟硬中断的一种信号通信方式。
接收软中断信号的进程不一定正好在接收时占有处理机,相应的处理必须等到该接收进程得到处理机之后才能进行。
中断处理的过程:
缓冲技术
引入缓冲的目的:1)缓和CPU和I/O设备间速度不匹配的矛盾;2)减少对CPU的中断次数; 3)解决DMA或通道方式时的瓶颈问题
缓冲技术的分类:单缓冲、双缓冲、多缓冲、缓冲池。
设备分配
设备分配常见的数据结构:1)系统设备表SDT;2)设备控制表DCT;3)控制器控制表COCT;4)通道控制表CHCT。
根据用户请求的I/O设备的逻辑名,查找逻辑设备和物理设备的映射表;以物理设备为索引,查找SDT,找到该设备所连接的DCT;继续查找与该设备连接的COCT和CHCT。一个进程只有获得了通道、控制器和所需设备三者之后,才具备了进行I/O操作的物理条件。
设备分配的策略的方法:先请求先分配与优先级高者先分配
假脱机技术:SPOOLING系统
思想:利用一台高速共享设备(磁盘或磁鼓)将一台独占设备模拟成多台可并行操作的虚拟设备。这样一来,使每个用户都感到得到了系统中的一台独享设备。
一个完整的SPOOLING 系统中有硬件部分和软件部分,它们之间协调配合,共同实现了假脱机技术。
硬件部分: 这部分包含了在外存上设立的两区域:输入井和输出井,以及在内存中开辟出的两个缓冲区:输入缓冲区和输出缓冲区。
假脱机技术的特点:1)提高了I/O速度;2)设备并没有分配给任何进程;3)实现了虚拟设备功能。
总结
实验与作业大家也一定要重点关注。
更多推荐
所有评论(0)