阿里云做网站送服务器,赣州英文网站建设,应用宝aso优化,做网页的工具操作系统总复习 文章目录 操作系统总复习一、考试题型1. 论述分析题2. 计算题3. 应用题 二、操作系统引论#xff08;第1章#xff09;2.1 操作系统的发展过程2.2 操作系统定义2.3 操作系统的基本特性2.3.1 并发2.3.2 共享2.3.3 虚拟2.3.4 异步 2.4 OS的功能2.5 OS结构2.5 习…操作系统总复习 文章目录 操作系统总复习一、考试题型1. 论述分析题2. 计算题3. 应用题 二、操作系统引论第1章2.1 操作系统的发展过程2.2 操作系统定义2.3 操作系统的基本特性2.3.1 并发2.3.2 共享2.3.3 虚拟2.3.4 异步 2.4 OS的功能2.5 OS结构2.5 习题1一、简答题1.在计算机系统上配置OS ( operating system,操作系统)的目标是什么?作用主要表现在哪几个方面?2. 试说明推动OS发展的主要动力是什么。3. OS具有哪几大特征?它们之间有何关系?4. 何谓原语?何谓原子操作?5. 简述中断处理过程。6. 什么是系统调用?系统调用与一般用户程序和库函数有何区别? 二、计算题1.设有3道程序A、B、C,它们按照优先次序(A→B →C)顺序执行,它们的计算时间和VO操作时间如表1-1-1所示,假设3道程序以串行方式使用相同的设备进行IO操作,试画出单道程序运行和多道程序运行的时间关系图,并计算完成这3道程序所须花费的时间。2.(考研真题)一个多道批处理系统中仅有P1和P2两个作业,P2比P11晚5ms 到达,它们的计算和I/O操作顺序如下。 三、综合应用题1.OS的概念、特征和功能是什么?2.(考研真题若某计算问题的执行情况如图1-1-6所示。 三、处理机管理第2、3、4章3.1 进程概念3.1.1 进程的定义3.1.2 进程的引入目的3.1.3 进程与程序的区别与联系 3.2 进程同步与临界资源管理3.2.1 进程同步的任务3.2.2 进程间两种制约关系3.2.3 临界资源、临界区概念、临界区的使用原则3.2.4 信号量机制3.2.5 信号量的应用3.2.5.1 实现进程互斥3.2.5.2 实现前驱关系简单的同步关系 3.3 调度管理3.3.1 调度的概念3.3.2 调度的原则3.3.3 调度方式3.3.4 调度类型 3.4 调度算法3.4.1 FCFS与SJ(P )F算法的应用3.4.2 高响应比优先算法(用于作业调度) 3.5 死锁管理3.5.1 死锁的概念3.5.2 产生死锁的原因3.5.3 死锁产生的必要条件3.5.4 处理死锁的基本方法3.5.5 银行家算法 3.5 习题2一、简答题1.什么是前趋图?请画出下列4条语句的前趋图。2.什么是进程?OS中为什么要引入进程?它会产生什么样的影响?3.进程最基本的状态有哪些?哪些事件可能会引起不同状态间的转换?4.为什么要引入进程的挂起状态? 二、综合应用题22.考研真题]现代OS 一般都提供多进程或称多任务运行环境回答以下问题。 3.6 习题3一. 填空题共1题4分1. (填空题, 4分) 二. 计算题共7题74分2. (计算题, 10分)课本P106页第19题3. (计算题, 10分)4. (计算题, 15分)设系统中有3种类型的资源ABC和5个进程资源的数量为17520。在T0时刻系统状态见表。系统采用银行家算法实施死锁避免策略。5. (计算题, 10分)某系统中共有11台磁带机X个进程共享此磁带机设备每个进程最多请求使用3台则系统必然不会死锁的最大X值是多少6. (计算题, 8分)某单CPU系统中有输入和输出设备各1台现有3个并发执行的作业每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms且都按输入、计算和输出的顺序执行则执行完3个作业需要的时间最少是 。7. (计算题, 11分)课本107页第22题8. (计算题, 10分) 三. 简答题共4题22分9. (简答题, 6分)死锁产生的原因和必要条件是什么如何预防死锁10. (简答题, 5分)在作业调度中应如何确定接纳多少个作业和接纳哪些作业11. (简答题, 5分)12. (简答题, 6分)试列举出三种作业调度算法并比较其优缺点。 3.7 习题4一. 简答题1.什么是临界资源?什么是临界区?2,同步机制应遵循的准则有哪些?3.为什么各进程对临界资源的访问必须互斥?4如何保证各进程互斥地访问临界资源? 二、计算题13若信号量的初值为2当前值为-1则表示有多少个等待进程?请分析。14.有m个进程共享同一临界资源,若使用信号量机制实现对某个临界资源的互斥访问,请求出信号量的变化范围。15若有4个进程共享同一程序段而且每次最多允许3个进程进入该程序段则信号量值的变化范围是什么? 三、综合应用题16.(考研真题)3个进程P1、P2、P3,互斥地使用一个包含N(N0)个单元的缓冲区。P,每次用produce()生成一个正整数并用put()将其送入缓冲区的某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数的个数;P。每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数的个数。请用信号量机制实现这3个进程的同步与互斥活动并说明所定义的信号量的含义。要求用伪代码描述。17.(考研真题某银行提供了1个服务窗口和10个供顾客等待时使用的座位。顾客到达银行时若有空座位则到取号机上领取一个号,等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时通过叫号选取一位顾客并为其服务。顾客和营业员的活动过程描述如下。20桌上有一个能盛得下5个水果的空盘子。爸爸不停地向盘中放苹果或橘子儿子不停地从盘中取出橘子享用,女儿不停地从盘中取出苹果享用。规定3人不能同时向(从)盘子中放(取水果。试用信号量来实现爸爸、儿子和女儿这3个“循环进程”之间的同步。 四、存储器管理第5、6章4. 存储器管理方式4.1 连续分配方式4.1.1 连续分配方式简介4.1.2 固定分区分配分区表4.1.3 动态分区分配空闲分区表4.1.4 基于顺序搜索的动态分区分配算法4.1.5 分区分配算法的具体实现4.1.6 分区分配算法的缺点 4.2 离散分配方式基本分页存储管理方式4.2.1 离散分配方式简介4.2.2 分页地址的地址结构4.2.3 页表4.2.4 地址变换4.2.5 具有块表的地址变换4.3 虚拟存储器管理4.3.1 理论依据和基本概念4.3.1.1 局部性原理4.3.1.2 虚拟存储器 4.3.2 关键技术4.3.2.1 请求调入4.3.2.2 置换 4.3.3 虚拟存储器的特征4.3.3.1 标准定义4.3.3.2 通俗解释 4.4 请求分页存储管理方式4.4.1 请求分页存储管理的硬件支持4.4.1.1 页表机制4.4.1.2 缺页中断机构4.4.1.3 地址变换机构 4.4.2 缺页中断和一般中断的联系与区别4.4.2.1 联系4.4.2.2 区别 4.5 页面置换算法4.5.1 OPT最佳置换算法4.5.1.1 标准定义 4.5.2 FIFO先进先出算法4.5.2.1 标准定义 4.5.3 LRU最近最少使用算法4.5.3.1 标准定义 4.6 习题54.7 习题6 五. 输入输出系统第7章5.1 I/O设备的类型5.2 I/O通道、I/O通道类型、通道与一般处理器的区别5.3 I/O控制方式5.4 I/O缓冲技术5.5 磁盘性能的影响因素5.6 磁盘调度算法5.6.1 FIFO先进先出5.6.2 SSTF最短寻道时间优先5.6.3 SCAN扫描5.6.4 CSCAN循环扫描 5.7 习题 六、文件管理 第8,9章6.1 文件系统的功能6.1.1 文件存储空间的管理6.1.2 目录管理6.1.3 文件的读写管理和保护 6.2 文件的逻辑结构、物理结构概念6.2.1 文件的逻辑结构6.2.2 文件的物理结构 6.3 外存的分配方式6.3.1 顺序式结构6.3.2 链接式结构6.3.3 索引式结构 6.4 Unix的混合索引方式6.5 存储空间管理6.5 习题一.简答题共6题,65.0分1、有哪几种I/O控制方式各适用于何种场合2、引入缓冲的主要原因是什么缓冲区都有哪些组织形式3、目前的磁盘调度算法有哪几种每种算法优先考虑的问题是什么4、按文件的组织方式可将文件分为哪几种类型5、目前广泛采用的目录结构有哪些它有什么优点6、目前常用的外存组织方式有哪些试比较其优缺点。 二.计算题共3题,35.0分1、设有如下磁道访问请求序列2、一个磁盘的转速是3000rpm盘面划分成10个扇区则读取一个扇区的时间是多少3、设文件索引结点中有7个地址项其中4个地址为直接地址2个地址为一级间接索引1个地址二级间接索引每个地址项大小为4B若磁盘索引块和磁盘数据块的大小均为256B则可表示的单个文件最大长度是多少 一、考试题型
1. 论述分析题
3题每题8分
2. 计算题
4题每题8分
3. 应用题
3题总计44分 二、操作系统引论第1章
2.1 操作系统的发展过程 单道批处理 标准定义 单道批处理是指一台计算机一次只能执行一个作业直到该作业执行完毕才能执行下一个作业。通俗解释 就像一台咖啡机一次只能冲一杯咖啡等当前咖啡冲好了才能开始下一杯。 多道批处理 标准定义 多道批处理是指计算机同时处理多个作业将它们组织成一个作业队列依次执行。通俗解释 想象一下计算机是一位高效的服务员而你是一位在餐厅就餐的顾客。你提前点好了多道菜然后将菜单交给服务员。不同的是这位服务员聪明地把所有顾客的菜单都组织成一个列表然后告诉厨师同时开始烹饪。而不是等待一道菜做好再点下一道。 分时 标准定义 分时是指计算机在短时间内轮流为多个用户服务每个用户感觉到自己在独占地使用计算机。通俗解释 就像一台共享单车不同用户可以在不同的时间共享使用每个用户感觉到独享整车。 实时 标准定义 实时是指计算机能够在规定的时间内对输入作出及时的响应通常用于控制系统等领域。通俗解释 就像电梯的按键按下后电梯会立即响应而不是等待一段时间再运行。 2.2 操作系统定义
标准定义 操作系统是控制和管理计算机硬件与软件资源为用户和应用程序提供服务的系统软件。通俗解释 操作系统就像计算机的总管家负责协调各种任务让计算机资源更好地为用户和应用服务。 2.3 操作系统的基本特性
2.3.1 并发
标准定义 并发是指两个或多个事件在同一时间间隔内发生。通俗解释 就像是一台电视机同时播放多个频道观众可以选择不同的节目观看。
2.3.2 共享
标准定义 共享是指多个进程之间共享系统资源的方式。通俗解释 互斥共享方式就像一辆共享自行车一次只能被一个人使用其他人需要等待。在计算机中这意味着某些资源一次只能由一个任务占用其他任务必须等待。同时访问方式就像一片公共草坪多个人可以同时在上面散步、读书彼此不会干扰。在计算机中这表示多个任务可以同时访问某些资源而不会产生冲突使得系统更加高效地共享资源。
2.3.3 虚拟
标准定义 虚拟是指通过一定的技术手段将物理实体划分为逻辑上的多个实体。通俗解释 虚拟存储器就像你有一个超级大的书桌但不是所有书都放在桌子上一部分放在书柜里需要时再取出。计算机的虚拟存储器也是这个道理能够像有很大内存一样使用实际上部分数据可能存在硬盘上。虚拟设备就像你有一台多合一打印机可以为多台电脑提供服务但实际上只有一台物理设备。
2.3.4 异步
标准定义 异步是指事件的发生和处理不是同步发生的。通俗解释 想象一下你发了一封电子邮件不需要等待对方立即回复你可以继续做其他事情然后在方便的时候查看是否收到回复就像是你自己掌握何时处理信息一样。 2.4 OS的功能
标准定义 操作系统具有多种功能包括进程管理、存储器管理、文件系统管理、设备管理和用户接口等。通俗解释 就像一位高效的项目经理负责协调团队中的各项工作确保项目顺利进行同时提供良好的沟通渠道。 进程管理 标准定义 操作系统负责创建、调度和终止进程以及管理进程间的通信与同步。通俗解释 像是一场舞会的主持人安排舞池中的舞者确保他们按照规定的步调舞动。 存储器管理 标准定义 操作系统控制计算机内存的分配和释放以及虚拟内存的管理。通俗解释 好比一个图书管理员负责将书籍合理地摆放在书架上确保读者能够方便地找到需要的信息。 文件系统管理 标准定义 操作系统负责组织和管理存储在计算机硬盘上的文件提供文件的创建、读取、写入和删除等操作。通俗解释 就像一名档案管理员整理文件柜确保每个文件都有清晰的标签和正确的存放位置。 设备管理 标准定义 操作系统协调和控制计算机的各类硬件设备包括输入设备、输出设备和存储设备。通俗解释 好比一位调度员负责安排机房中各种设备的工作确保它们协同运作。 用户接口 标准定义 操作系统提供与用户交互的界面可以是命令行界面、图形界面或其他形式的用户界面。通俗解释 就像手机的操作系统界面用户通过触摸屏或按键与手机进行交互完成各种操作。
2.5 OS结构
标准定义 操作系统的结构通常包括内核kernel和系统调用接口内核负责直接与硬件交互而系统调用接口为应用程序提供服务。通俗解释 类似一座建筑物内核是建筑的基础和支撑结构系统调用接口则是连接用户与内核的桥梁使用户能够利用操作系统的功能。 2.5 习题1
一、简答题
1.在计算机系统上配置OS ( operating system,操作系统)的目标是什么?作用主要表现在哪几个方面?
【参考答案】在计算机系统上配置OS,主要目标是实现:方便性、有效性、可扩充性和开放性。 OS的作用主要表现在以下3个方面:
OS作为用户与计算机硬件系统之间的接口;OS作为计算机系统资源的管理者;OS实现对计算机资源的抽象。
2. 试说明推动OS发展的主要动力是什么。
【参考答案】推动OS发展的主要动力表现在:
计算机系统资源的利用率不断提高:方便用户器件不断更新换代计算机体系结构不断发展新的应用需求不断被提出。
3. OS具有哪几大特征?它们之间有何关系?
答OS具有并发、共享、虚拟和异步这4个基本特征。
它们之间的关系包含以下几个方面。 1.并发和共享是OS最基本的特征。为了提高计算机资源的利用率OS必然要采用多道程序设计技术使多个程序共享系统的资源、并发地执行。 2.并发性和共享性互为存在的条件。一方面资源的共享是以程序进程的并发执行为条件的若系统不允许程序并发执行就不会存在资源共享问题;另一方面若系统不能对资源共享实策有效管理协调好各进程对共享资源的访问则必将影响程序的并发执行甚至会使程序无法并发执行。 3.虚拟性以并发性和共享性为前提。为了使并发进程能更方便、更有效地共享资源OS常采用多种虚拟技术在逻辑上增加CPU和设备的数量以及存储器的容量从而解决并发进程对有限系统资源的共享问题。 4.异步性是并发性和共享性的必然结果。OS允许多个并发进程共享资源、相互合作使得每个进程的运行过程受到了其他进程的制约不再“一气呵成”这必然会导致异步这一特征的产生。
4. 何谓原语?何谓原子操作?
答原语是由多条指令组成的用于完成特定功能的过程而原子操作是不可分割的基本单位要么全部执行要么全部不执行。因此原语在执行过程中是不允许被中断的。原子操作在内核态下执行常驻内存。
5. 简述中断处理过程。
答一旦CPU响应中断系统就会开始进行中断处理。中断处理过程主要包括以下3步。 (1) 保护被中断进程的现场。为了在中断处理结束后能使进程正确地返回中断点系统必须保存当前处理机状态字和程序计数器的值。 (2) 分析中断原因转去执行相应的中断处理程序。在多个中断请求同时发生时处理优先级最高的中断源所发出的中断请求。 (3) 恢复被中断进程的现场,CPU继续执行被中断的原进程。
6. 什么是系统调用?系统调用与一般用户程序和库函数有何区别?
答系统调用是OS提供给程序员的唯一接口。程序员利用系统调用在源程序层面动态请求和释放系统资源并调用系统中已有的系统功能来完成那些与机器硬件部分相关的工作以及控制程序的执行速度等。因此系统调用像一个“黑箱子”对用户屏蔽了OS的具体动作只提供有关的功能。
系统调用与一般用户程序、库函数的区别在于: ①系统调用程序在内核态执行调用它们时需要一个类似于硬件中断处理机制的中断处理机制来提供系统服务。 ②普通的用户程序是直接为用户完成某特定功能而设计的它们一般在用户态执行。 ③库函数是把函数放到库里供别人使用的一种方式是面向应用开发、方便人们编程的。
二、计算题
1.设有3道程序A、B、C,它们按照优先次序(A→B →C)顺序执行,它们的计算时间和VO操作时间如表1-1-1所示,假设3道程序以串行方式使用相同的设备进行IO操作,试画出单道程序运行和多道程序运行的时间关系图,并计算完成这3道程序所须花费的时间。 答计算时间时CPU处理时间IO操作时间是输入与输出时间。3个程序共享IO设备即串行使用IO设备。 (1)单道程序运行时,3道程序串行执行即先执行A、再执行B、最后执行C时间关系图如图所示。
单道程序运行时3道程序使用的时间为:( 304010 )(603010)(204020)260ms。 (2)多道程序运行时3道程序的计算与IO操作可部分并行分为非立即抢占式和立即抢占式两种时间关系图如图1和图2所示。 多道程序运行时3道程序非立即抢占式的总时间为180ms立即抢占式的总时间为190ms。
2.(考研真题)一个多道批处理系统中仅有P1和P2两个作业,P2比P11晚5ms 到达,它们的计算和I/O操作顺序如下。
P1:计算60ms, l/O操作 80ms,计算20ms. P2:计算120ms,I/O操作40ms,计算40ms. 不考虑调度和切换时间,请计算完成两个作业需要的最少时间。
答作业执行时间关系图如图所示。由于在多道批处理系统中P1与P2可以部分并行因此P1先到达系统其会先占用CPU进行计算到60ms ) 然后执行IO操作的时间是60ms ~ 140ms;而在P1执行IO操作的过程中P2可获得CPU运行120ms到180ms结束;当P1执行完它的I/O操作后执行计算此时CPU正被P2占用因此P1须等P2执行完后才能获得CPU执行剩余的20ms执行完成后退出系统;此时P会执行I/O操作40ms到220ms;最后P2获得CPU运行剩余的40ms(计算)到260ms结束。由图1-1-5可知完成两个作业需要的最少时间为260ms。
三、综合应用题
1.OS的概念、特征和功能是什么?
答该问题分步解答如下。 ( 1 ) OS是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以方便用户使用计算机的程序集合。OS是配置在计算机硬件上的第一层系统软件是对硬件系统的首次扩充;是硬件系统和应用软件间的桥梁;是用户与计算机硬件进行交互的接口;是计算机系统资源的管理者。 ( 2 )OS的4个特征:并发、共享、虚拟、异步。 ①并发:一段时间间隔内多个进程线程)并发执行是宏观上的并行微观上的串行。②共享:系统中的资源可供内存中多个并发执行的进程或线程共同使用。 ③虚拟:通过某种技术将物理实体变为若干个逻辑上的对应物。 ④异步:进程以人们不可预知的速度向前推进每次运行只要环境相同则结果必定一致。 ( 3 )OS的5大功能:处理机管理、存储器管理、设备管理、文件管理、接口管理。 ①处理机管理:进程线程是处理机调度的单位因此对外理器的管理实际上是对进程线程)的管理。 ②存储器管理:内存的分配与回收、地址转换、虚拟内存的实现等。 ③设备管理:设备的分配与回收、缓冲区管理、磁盘调度、设备虚拟等。 ④文件管理:文件存储空间的管理、文件目录管理、文件共享与保护等。 ⑤接口管理:用户接口、程序接口、命令接口和网络接口。
2.(考研真题若某计算问题的执行情况如图1-1-6所示。 则请回答下列问题。 (1)叙述该计算问题中处理机、输入机和打印机是如何协同工作的。 (2)计算在图1-1-6所示执行情况下处理机的利用率。 (3)简述处理机利用率不高的原因。 (4)请画出能提高处理机利用率的执行方案。
答(1)处理机、输人机和打印机是按照输人→处理→打印的顺序依次执行的输人机为处理机提供数据处理机得到数据后进行处理处理结果通过打印机打印输入。输人机读取一批数据花费时间为100;处理机对这批数据进行计算花费时间为20;打印机打印计算结果花费时间为40。 (2)处理机的利用率[ 20 (1002040) ] x100%12.5%。 (3)当一道程序在运行中发出IO请求后处理机只能处于等待状态即必须等LO完成后才能继续运行因此处理机会长时间处于空闲状态这会导致其利用率不高。 (4采用多道程序设计技术使处理机、输入机和打印机并行工作可以提高处理机的利用率如图所示。 三、处理机管理第2、3、4章
3.1 进程概念
3.1.1 进程的定义
标准定义 进程是程序执行的实体是操作系统进行资源分配和调度的基本单位。通俗解释 进程就像火车是程序的一次执行过程而程序则是火车的设计图。 进程就像是计算机中程序的具体执行是操作系统为程序提供运行环境并分配资源的基本单元。可以把进程看作是计算机中正在进行的任务每个任务都有自己的空间和资源。
3.1.2 进程的引入目的
标准定义 进程的引入旨在实现多道程序设计提高CPU的利用率使多个进程可以并发执行。通俗解释 进程的引入就像是在一个大厨房里同时烹饪多道菜提高了整体效率让每个菜都能在合适的时候完成。 引入进程的目的就是为了让计算机可以同时处理多个任务就像一台多功能机器能够在同一时间执行多个不同的任务从而更高效地利用计算机的处理能力。这让我们的电脑可以同时运行浏览器、音乐播放器和文档编辑器而不是只能一个任务一个任务地执行。
3.1.3 进程与程序的区别与联系
标准定义 进程 是程序在执行过程中的实体有独立的内存空间和系统资源。程序 是静态的存储在磁盘上的可执行文件是进程的设计图。 通俗解释 进程就像是在跑步的运动员有自己的身体和能量。程序就像是运动员的跑步计划是一份静态的文件需要通过运动员的执行才能变成实际的运动。
3.2 进程同步与临界资源管理
3.2.1 进程同步的任务
标准定义 对多个相关进程的执行次序进行协调以使并发的诸进程有效地共享资源和相互合作从而使程序的执行具有可再现性。通俗解释 进程同步的任务就像是一个大型协作舞蹈各个进程就是舞者它们需要协调动作共享舞台资源以确保整个表演有条不紊地进行。就像是一个编排精良的舞蹈表演每个舞者都需要在正确的时机做出正确的动作这样整个表演才能具有可再现性给观众留下深刻的印象。
3.2.2 进程间两种制约关系 直接制约关系同步 标准定义 源于进程间的合作要求某个进程等待另一个进程的信号或消息以保持进程的顺序执行。通俗解释 就像接力比赛中每个跑步者必须等待前一个跑手的交接棒信号确保顺序传递。 间接制约关系互斥 标准定义 源于资源共享要求对共享资源的访问是排他的即一次只允许一个进程访问共享资源。通俗解释 就像共享一台打印机一次只能有一个人使用其他人需要等待。
3.2.3 临界资源、临界区概念、临界区的使用原则 临界资源 标准定义 是一次只允许一个进程使用的资源如共享变量、共享文件等。通俗解释 临界资源就像是一把只有一个人能用的工具比如一把特殊的锤子。每次只有一个工人可以拿到这把锤子完成自己的工作。其他工人需要等待直到当前工人使用完毕并释放了这把锤子下一个工人才能拿到它。这样确保了在任何时刻临界资源只被一个进程占用避免了多个进程同时访问可能引起混乱和错误的情况。 临界区概念 标准定义 是涉及临界资源的代码段一次只能有一个进程进入执行。在临界区内对临界资源的访问是排他的其他进程需要等待。通俗解释 想象一下大家在写字台上使用同一支笔临界区就像是只有一个人能坐的椅子。当有人想写字时他需要先坐到椅子上进入临界区然后进行写字操作。其他人则需要等待当前写字的人完成才能轮到自己坐到椅子上。这样做的目的是为了防止多人同时使用同一支笔避免混乱和错误。 临界区的使用原则 标准定义 进程进入临界区前需要先申请访问权临界区内的执行尽量短离开临界区后释放访问权。通俗解释 就像使用共享单车每次骑行前需要先扫码解锁骑行结束后再锁定确保下一个人可以使用。 互斥使用临界资源 进入区:判断临界资源是否可用如果可以进入则设置临界区使用标志阻止后面的进程进入后面的进程通过查看临界区使用标志进入阻塞队列等待 退出区:l临界区使用完毕退出区修改临界区使用标志唤醒等待该资源的进行让其进入临界区。 由于同一临界资源在多个共享它的进程中对应多个临界区怎样才能保证进程间互斥的执行临界区? 必须保证临界区标志是可被系统中所有进程修改的全局变量而且诸进程对该标志的修改操作须互斥地进行。 3.2.4 信号量机制 整型信号量 标准定义 是一个整数用于表示资源的可用数量进程可以对其进行加减操作。通俗解释 整型信号量就像是一个计数器记录着可用资源的数量进程可以通过增减操作来请求或释放资源。 记录型信号量 标准定义 包含一个整数值和一个等待队列支持wait()和signal()原语用于实现进程同步。通俗解释 就像是一本书的借阅记录有人借阅时需要登记归还时也要登记确保借阅有序进行。 信号量的物理意义 标准定义 可以看作是一种保护机制防止多个进程同时访问临界资源。通俗解释 信号量就像是一把锁确保一次只有一个进程能够进入临界区避免资源的冲突和混乱。
3.2.5 信号量的应用
3.2.5.1 实现进程互斥
标准定义 使用信号量保护临界资源每个进程在访问临界资源前先对信号量进行P操作离开后进行V操作。通俗解释 进程互斥就像是共享厨房的规矩大家都想用同一把刀但不希望在同一时刻有多个人使用。所以每个人在使用刀前先检查有没有可用的标志。如果有就把标志设为不可用表示刀在使用中使用完后再将标志设回可用这样其他人就知道可以使用了。这个标志就像是信号量通过检查和设置标志大家有序地使用共享资源。
3.2.5.2 实现前驱关系简单的同步关系
标准定义 使用信号量实现进程的前驱关系确保某个进程在前驱进程完成后才能执行。通俗解释 前驱关系就像是工程中的任务链B任务必须等待A任务完成后才能开始。使用信号量就像是在A任务完成时扔一个小纸条通知B任务可以开始了。B任务在开始前检查这个小纸条如果有就执行没有的话就等待。这样通过信号量的通知机制保证了进程之间的前后顺序执行。
3.3 调度管理
3.3.1 调度的概念
标准定义 调度是操作系统根据一定的策略和算法决定进程或作业在系统中执行的顺序。通俗解释 调度就像是电梯的按钮你按下去后电梯就会按照一定的规则决定哪个楼层的人先上电梯实现有序的运送。操作系统的调度就是按照一定的规则决定哪个进程先执行确保系统资源的合理利用。
3.3.2 调度的原则
标准定义 先来先服务FCFS 按照进程到达的先后顺序进行调度先到达的进程先执行。短作业进程优先SJ§F 优先执行执行时间短的进程以减少平均等待时间。高响应比优先算法 通过考虑等待时间和执行时间的比值来选择下一个执行的进程以提高系统的响应速度。 通俗解释 先来先服务就像是排队购物先来的顾客先被服务。短作业优先就像是做事情时优先处理耗时短的任务。高响应比优先算法就像是服务行业中优先响应对服务质量有帮助的请求。 调度的原则就像是队伍中的排队规则有三种方式。先来先服务就像是谁先到谁先进入服务台。短作业进程优先就像是优先让那些任务最短的人先进入服务。高响应比优先算法就像是为了提高服务效率考虑每个人等待的时间和执行的时间比例选择合适的人先进行服务。这样可以更好地管理进程提高系统的整体性能。
3.3.3 调度方式
标准定义 非抢占式调度 进程获得CPU后直到主动放弃CPU或执行完毕才会释放。抢占式调度 操作系统具有中断能力可以强制中断当前进程的执行转而执行其他进程。 通俗解释 非抢占式调度就像是每个人洗澡前需要先预约一旦热水器分配给某人他就可以一直用直到洗完澡或者自愿放弃其他人不能抢走热水器。抢占式调度就像是有了中断按钮如果有人等急了或者有更重要的事情可以按下按钮迫使当前正在使用热水器的人放弃然后由等待的人使用。这样可以更灵活地管理资源。
3.3.4 调度类型
标准定义 作业调度 决定哪个作业进入内存执行以及作业的执行顺序。进程调度 决定哪个进程获得CPU的使用权以及进程的执行顺序。 通俗解释 作业调度就像是一场戏剧的编排决定哪个戏登场以及登场的次序确保整个戏剧有条不紊地上演。进程调度就像是舞台上演员的出场顺序决定哪个演员可以站在前台得到观众的关注确保整个表演流畅有序。
3.4 调度算法
3.4.1 FCFS与SJ(P )F算法的应用 FCFS先来先服务算法 标准定义 进程按照到达的先后顺序执行。通俗解释 就像是在排队等待服务先到达的进程先被执行类似于先到先得的原则。 SJ(P )F短作业进程优先算法 标准定义 优先执行执行时间短的进程可以减少平均等待时间。通俗解释 像在自助餐厅你会先选择那些烹饪时间短的食物以更快品尝到美味。
3.4.2 高响应比优先算法(用于作业调度)
高响应比优先算法 标准定义 通过考虑等待时间和执行时间的比值来选择下一个执行的进程以提高系统的响应速度。计算公式为响应比 (等待时间 服务时间) / 服务时间。通俗解释 想象你是一位聪明的服务员有很多桌子需要照顾。你会优先选择那些等待时间长且需要服务时间短的桌子因为这样可以更迅速地满足顾客需求提高整体餐厅效率。在计算机世界中高响应比优先算法就是让计算机系统像个聪明的服务员一样更聪明地选择下一个要处理的任务确保系统更迅速地响应用户需求提高整体运行效率。
3.5 死锁管理
3.5.1 死锁的概念
标准定义 死锁是指两个或多个进程无法继续执行因为每个进程都在等待其他进程释放资源。通俗解释 想象一群小朋友围成一个圈每个小朋友手里拿着糖果并想要换取其他小朋友手里的糖果。然而由于每个小朋友都固执地等着对方先给自己糖果最终导致所有小朋友都拿不到新的糖果大家陷入了僵局无法继续玩耍。这就好比计算机中的死锁每个进程都在等待其他进程释放资源最终导致所有进程都无法前进。
3.5.2 产生死锁的原因
标准定义 竞争资源 多个进程竞争有限的资源导致资源分配不当。进程间推进顺序不当 进程之间相互等待对方释放资源形成循环等待。 通俗解释 想象一家只有一个投影仪的会议室多个团队需要使用。每个团队都想要在会议室里展示自己的项目但因为只有一个投影仪团队之间开始争夺使用权导致资源投影仪的分配不当。最终可能导致某些团队无法正常进行演示整个会议室陷入混乱。假设有一群小朋友在玩过家家每个小朋友都需要等待其他小朋友完成某个动作后才能进行下一步。如果他们陷入相互等待的循环比如小朋友 A 等待 BB 等待 C而 C 又在等待 A那么整个过家家游戏可能无法进行下去就像死锁一样。这种相互等待的情况可能阻碍所有小朋友完成游戏。
3.5.3 死锁产生的必要条件
标准定义 互斥条件请求和保持条件不剥夺条件循环等待条件 通俗解释 让我们以家庭洗碗为例来理解导致死锁的四个必要条件。 互斥条件 就像家庭里只有一个洗碗槽一样同一时间只能有一个人使用。这就是互斥条件如果多个人试图同时使用洗碗槽就会发生互斥。 请求和保持条件 每个家庭成员在洗碗前都会请求并保持对洗碗槽的使用权以确保能够流畅地进行洗碗。这就是请求和保持条件。 不剥夺条件 当某人正在使用洗碗槽时其他人不能剥夺他的使用权类似于在洗碗过程中保持资源不可被剥夺的条件。 循环等待条件 想象家庭成员需要按照一定的顺序进行洗碗如果形成了一个循环等待比如A等待BB等待C而C又在等待A整个洗碗可能就会陷入循环等待就像死锁的循环等待条件。这种情况可能导致整个洗碗过程陷入僵局无法完成。
3.5.4 处理死锁的基本方法
标准定义 预防死锁 通过破坏死锁产生的四个必要条件之一来预防死锁的发生。避免死锁 在资源分配过程中动态地检查系统状态以确保不会进入死锁状态。检测死锁 允许死锁发生但通过检测和恢复来解决死锁。解除死锁 当检测到死锁时通过抢占资源或终止进程来解除死锁。 通俗解释 这就像在家庭洗碗时采取一些策略以应对可能发生的洗碗僵局。 预防死锁 就像在家庭洗碗时家庭成员事先协商好谁先使用哪个洗碗槽以破坏家庭洗碗可能导致死锁的条件之一即请求和保持条件。 避免死锁 在资源分配过程中就像在洗碗时动态地观察家庭成员使用洗碗槽的情况以确保不会进入洗碗的死锁状态。这可能涉及更灵活的资源分配策略以防止死锁的发生。 检测死锁 有时候允许死锁发生就像在洗碗时不阻止家庭成员同时请求多个洗碗槽。但系统会定期检测是否发生了死锁以便及时采取措施来解决问题。 解除死锁 当检测到死锁时就像在洗碗时发现了僵局可能需要采取措施比如抢占某个洗碗槽或者终止某个家庭成员的洗碗任务以解除死锁。
3.5.5 银行家算法
标准定义 一种预防死锁的算法通过判断系统分配资源后是否处于安全状态来决定是否分配资源。通俗解释 就像是银行根据账户余额判断是否能够提供贷款确保整个系统处于安全状态。
3.5 习题2
一、简答题
1.什么是前趋图?请画出下列4条语句的前趋图。
S1:axy; S2:bz1; S3:ca-b; S4: wc1: 【参考答案】本题分儿解答如下。 (1)趋图(procedence graph)是一个有向无环图,记为DAG( directed acyclic graph).用于描述进程间执行的前后关系。 (2题中4条语句对应的前图如图所示。
2.什么是进程?OS中为什么要引入进程?它会产生什么样的影响?
【参考答案】 ①进程是一段可并发执行的具有独立功能的程序,是关于某个数据集的一次执行过程也是OS进行资源分配和保护的基本单位。 ②在OS中引入进程,是为了实现多个程序的并发执行。传统的程序与其他程序并发执行时执行结果不可再现因此传统的程序不能与其他程序并发执行只有在为之创建进程后,其才能与其他程序(进程并发执行。这是因为并发执行的程序“停停走走”地执行只有在为它创建进程后在它停下时,方能将其CPU现场信息保存在它的PCB ( processing control block进程控制块中待下次被调度执行时再从PCB中恢复CPU现场而继续执行但传统的程序却无法满足上述要求。 ③建立进程所带来的好处是多个程序能并发执行这极大地提高了资源利用率和系统吞吐量。但管理进程也须付出一定的代价包括PCB及协调各运行机构所占用的内存空间开销以及为进行进程间的切换、同步与通信等所付出的时间开销。
3.进程最基本的状态有哪些?哪些事件可能会引起不同状态间的转换?
【参考答案】进程最基本的状态有3种。 ①运行态:进程占有处理机,正在运行。 ②就绪态:进程具备运行条件,等待系统分配处理机以便运行。 ③等待态(又称为阻塞态或睡眠态):进程不具备运行条件,正在等待某个事件的完成。 进程不同状态间的转换及引发原因介绍如下。 ①运行态→等待态:等待使用资源或某事件发生; ②等待态→就绪态:资源得到满足或某事件已经发生; ③运行态→就绪态:运行时间片到达或出现有更高优先级的进程; ④就绪态一运行态:CPU空闲时调度选中一个就绪进程需要其运行。
4.为什么要引入进程的挂起状态?
【参考答案】所谓挂起状态实际上就是一种静止的状态。一个进程被挂起后不管它是否处于就绪状态系统都不会分配给它处理机。因此引入挂起状态是基于系统和用户的如下需要。 ①终端用户的需要:当终端用户在自己的程序运行期间发现问题时希望暂停进程的运行。 ②父进程请求:父进程挂起自己的某个子进程,检查并修改该子进程或者协调各子进程之间的活动。 ③负荷调节的需要:当实时系统中的工作负荷较重、实时任务受到影响时挂起些不重要的进程。 ④OS的需要:OS挂起某些进程检查或统计运行中的资源使用情况。
二、综合应用题
22.考研真题]现代OS 一般都提供多进程或称多任务运行环境回答以下问题。
(1)为支持多进程的并发执行系统必须建立哪些关于进程的数据结构? (2)为支持进程状态的变迁,系统至少应提供哪些进程控制原语? (3)在执行每一个进程控制原语时进程状态会发生什么变化?相应的数据结构会发生什么变化? 【参考答案】 (1为支持多进程的并发执行系统必须建立关于进程的相关数据结构,包括PCB和队列结构如就绪队列、等待队列、运行指针等)。 (2)为支持进程状态的变迁,系统应提供的进程控制原语包括:创建原语、阻塞原语、唤醒原语、撤销原语。 (3在执行每一个进程控制原语时进程状态及相应的数据结构有4种变化情况。 ①创建原语:系统为进程创建PCB,并对它进行初始化。进程状态由无变为就绪状态,新创建的进程加入就绪队列中。 ②阻塞原语:进程状态从运行状态变为阻塞状态并将阻塞进程的PCB插入相应的阻塞队列中。 ③唤醒原语:进程状态从阻塞状态变为就绪状态从阻塞队列中删除该进程,并将其插入就绪队列中。 ④撤销原语:进程状态从运行状态变为消亡状态系统撤销该进程的PCB.。
3.6 习题3
一. 填空题共1题4分
1. (填空题, 4分)
若每个作业只能建立一个进程为了照顾短作业用户应采用 为了照顾紧急作业用户应采用 为了能实现人机交互应采用 而能使短作业、长作业和交互作业用户都满意应采用 。
A、先来先服务调度算法
B、短作业优先调度算法
C、时间片轮转调度算法
D、多级反馈队列调度算法
E、剥夺式优先级调度算法
正确答案 (1) B (2) E (3) C (4) D 当你想象计算机操作系统是一种类似于任务管理大师的存在时这几种进程调度算法就好比是不同的工作安排方式
A、先来先服务调度算法 就像是一个等着打饭的队伍谁先来的谁就先吃饭。
B、短作业优先调度算法 想象一下在自助餐厅里你会优先选择吃那些看起来短时间就能吃完的食物以便更快地满足你的饥饿感。
C、时间片轮转调度算法 就好比你和一群朋友轮流玩电脑游戏每个人都有一定的时间时间片来玩然后轮到下一个人。
D、多级反馈队列调度算法 想象一家图书馆有几个阅览室每个阅览室的环境和规则不同你根据你的学习需要和规定的时间在这些阅览室之间切换。
E、剥夺式优先级调度算法 就像是你正在看电视但如果有紧急的新闻播报电视节目可能会被打断以保证更重要的信息先被传达。
这些算法就是操作系统为了合理安排各种任务让计算机运行更高效更好地响应用户需求而设计的各种策略。
二. 计算题共7题74分
2. (计算题, 10分)课本P106页第19题 正确答案
3. (计算题, 10分)
设有4道作业它们的提交时间及执行时间如下 作业号 提交时间 执行时间 1 10.0 2.02 10.2 1.03 10.4 0.54 10.5 0.3试计算在单道程序环境下系统10.0开始调度采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间并指出它们的调度顺序。时间单位小时以十进制进行计算。
正确答案 先来先服务2.8 5.25
短作业优先2.45 3.85
答案解析
4. (计算题, 15分)设系统中有3种类型的资源ABC和5个进程资源的数量为17520。在T0时刻系统状态见表。系统采用银行家算法实施死锁避免策略。
① T0时刻是否为安全状态若是请给出安全序列。
② 在T0时刻若进程P2请求资源034是否能实施资源分配为什么
③ 在②的基础上若进程P4请求资源201是否能实施资源分配为什么
④ 在③的基础上若进程P1请求资源020是否能实施资源分配为什么
T0时刻系统状态 正确答案 1T0时刻是安全的存在安全序列P4,P2,P3,P5,P1
2P2请求0,3,4),系统可用资源向量(2,3,3)不满足P2请求P2阻塞等待。
3P4请求(2,0,1)(2,3,3)尝试将2,0,1分配给P4系统资源分配如下
经分析存在安全序列P4,P2,P3,P5,P1
(4)在③的基础上若进程P1请求资源020,系统可用资源向量0,3,2尝试分配给P1此时剩余资源向量0,1,2此时资源分配情况如下
可用资源向量0,1,2不能满足任何进程的请求故不予以分配。
5. (计算题, 10分)某系统中共有11台磁带机X个进程共享此磁带机设备每个进程最多请求使用3台则系统必然不会死锁的最大X值是多少
正确答案 X*3-1111
X5
答案解析X*3-1111X5
6. (计算题, 8分)某单CPU系统中有输入和输出设备各1台现有3个并发执行的作业每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms且都按输入、计算和输出的顺序执行则执行完3个作业需要的时间最少是 。
正确答案 17ms。
7. (计算题, 11分)课本107页第22题 8. (计算题, 10分)
假设有四个作业它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法系统8.0开始调度试问平均周转时间和平均带权周转时间为多少? 时间单位小时以十进制进行计算。
作业号 到达时间 运行时间
1 8.0 2.0
2 8.3 0.5
3 8.5 0.1
4 9.0 0.4
正确答案 在800时因为只有作业1到达系统将作业1投入运行。作业1运行2小时(即
1000时)完成。由于该算法采用响应比高者优先调度算法这样在作业1执行完后要计算剩下三个作业的响应比然后选响应比高者去运行。剩下三个作业的响应比为
r2l(10.0-8.3)0.54.4
r3l(10.0-8.5)0.116
r4l(10.0-9.0)0.43.5
从计算结果看作业3的响应比高所以让作业3先运行。
作业3运行0.1小时完成(即1010时)此时作业2和作业4的响应比为
r2l(10.1-8.3)0.54.6
r4l(10.1-9.0)0.43.75
从上述计算结果看作业2的响应比高所以让作业2先运行。因此四个作业的执行次序为作业1、作业3、作业2、作业4.
解四个作业的调度次序为作业1、作业3、作业2、作业4。
作业 到达 运行 开始 完成 周转 带权周转
1 8.0 2.0 8.0 10.0 2.0 1.0
2 8.3 0.5 10.1 10.6 2.3 4.6
3 8.5 0.1 10.0 10.1 1.6 16.0
4 9.0 0.4 10.6 11.0 2.0 5.0
平均周转时间 T(2.02.31.62.0)41.975
平均带权周转时间 W(14.6165)46.65
答案解析在800时因为只有作业1到达系统将作业1投入运行。作业1运行2小时(即1000时)完成。由于该算法采用响应比高者优先调度算法这样在作业1执行完后要计算剩下三个作业的响应比然后选响应比高者去运行。剩下三个作业的响应比为 r2l(10.0-8.3)0.54.4 r3l(10.0-8.5)0.116 r4l(10.0-9.0)0.43.5 从计算结果看作业3的响应比高所以让作业3先运行。作业3运行0.1小时完成(即1010时)此时作业2和作业4的响应比为 r2l(10.1-8.3)0.54.6 r4l(10.1-9.0)0.43.75 从上述计算结果看作业2的响应比高所以让作业2先运行。因此四个作业的执行次序为作业1、作业3、作业2、作业4.解四个作业的调度次序为作业1、作业3、作业2、作业4。作业 到达 运行 开始 完成 周转 带权周转 1 8.0 2.0 8.0 10.0 2.0 1.0 2 8.3 0.5 10.1 10.6 2.3 4.6 3 8.5 0.1 10.0 10.1 1.6 16.0 4 9.0 0.4 10.6 11.0 2.0 5.0 平均周转时间 T(2.02.31.62.0)41.975 平均带权周转时间 W(14.6165)46.65
三. 简答题共4题22分
9. (简答题, 6分)死锁产生的原因和必要条件是什么如何预防死锁
正确答案 死锁产生的原因竞争资源和推进顺序非法。
必要条件互斥、请求和保持、不剥夺、环路等待。
预防死锁是通过破坏死锁必要条件的一个或几个。包括破坏请求和保持、破坏不剥夺和破坏环路等待。
10. (简答题, 5分)在作业调度中应如何确定接纳多少个作业和接纳哪些作业
正确答案 接纳多少个作业取决于多道程序的度接纳哪些作业取决于调度算法。
11. (简答题, 5分)
假设系统中有下述3种解决死锁的方法
1银行家算法
2检测死锁终止处于死锁状态的进程释放进程所占有的资源
3资源预分配。
在上述解决死锁的几个方法中哪个方法允许最大的并发性 请按“并发性”从大到小对3种方法进行排序。
正确答案 第2种方法的并发性最大第1种次之第3种方法的并发性最弱。
12. (简答题, 6分)试列举出三种作业调度算法并比较其优缺点。
正确答案 FCFS按照作业到达系统的先后顺序依次调度适合于长作业不利于短作业未考虑作业的紧迫程度很少单独使用。
SJF选取运行时间最短的作业优先调度可以缩短平均周转时间不利于长作业未考虑作业的紧迫程度。
HRN既考虑作业运行时间也考虑作业等待时间但调度之前需要计算响应比增加了系统开销。
3.7 习题4
一. 简答题
1.什么是临界资源?什么是临界区?
【参考答案】 ①在计算机中有许多资源一次仅允许一个进程使用我们把一次仅允许一个进程使用的资源称为临界资源如打印机和一些共享变量等。 ②进程中访问临界资源的那段代码称为临界区。
2,同步机制应遵循的准则有哪些?
【参考答案】同步机制应遵循的准则主要有4个。 (1)空闲让进。当无进程处于临界区时表明临界资源处于空闲状态应允许一个请求进人临界区的进程立即进人临界区,以有效地利用临界资源。 (2)忙则等待。当已有进程在临界区时表明临界资源正在被访问因面其他试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。 (3)有限等待。对要求访问临界资源的进程应保证其能在有限时间内进入临界区以免陷人“死等”状态。 (4)让权等待。当进程不能进入临界区时,其应立即释放处理机以免进程陷入“忙等”。
3.为什么各进程对临界资源的访问必须互斥?
【参考答案】临界资源本身的特性决定了它们只能被各个进程互斥地访问如果并发执行的多个进程同时访问临界资源则会造成系统混乱或程序执行结果不确定。这样进程运行结果就可能不正确或者不确定。比如,两个进程并发执行如下程序段:
mov ax, (counter);
ine ax;
mov (eounter), ax;其中共享变量counter初值为0对counter执行加1操作。如果允许一个进程访问counter另一个进程也可以对其进行操作则counter的值最终可能是正确结果2也可能是错误结果1即计算结果出现了不确定性。因此各进程对临界资源的访问必须互斥地进行。
4如何保证各进程互斥地访问临界资源?
【参考答案】为了互斥地访问临界资源系统必须保证进程互斥地进入临界区。为此必须在临界区前增加一段进人区代码以检查是否有其他进程已进入临界区而在使用临界资源。若有则进程必须等待;否则允许进程进入临界区同时设置标志以表示有进程正在临界区内。同样在临界区后必须增加一-段退出区代码用于将已有进程进人临界区访问临界资源的标志改为无进程进人临界区使用临界资源。进入区和退出区可用多种同步机制实现,如锁、信号量机制等。
二、计算题
13若信号量的初值为2当前值为-1则表示有多少个等待进程?请分析。
【参考答案】信号量的初值表示系统中资源的数目每次的P操作表示进程请求一个单位的资源信号量进行减l操作,当信号量小于0时表示资源已分配完毕、进程自我阻塞。如果信号量小于0那么信号量的绝对值表示当前阻塞队列中进程的个数。因此当前值为-1表示有1个等待进程。
14.有m个进程共享同一临界资源,若使用信号量机制实现对某个临界资源的互斥访问,请求出信号量的变化范围。
【参考答案】某个临界资源的信号量初值为1,其是信号量的最大值。m个进程分别对临界资源发出1次请求信号量均要执行减1操作因此最多可允许m个进程同时申请、此时信号量的值是1-m为最小值。因此,信号量值的范围是1-m至1。
15若有4个进程共享同一程序段而且每次最多允许3个进程进入该程序段则信号量值的变化范围是什么?
【参考答案】程序段作为共享资源最多允许3个进程进入其中因此设置信号量初值为3。当4个进程共享该程序段时在每个进程中请进入时信号量都会执行减1操作。当第1个进程申请进入时信号量值变为2:第2个进程申请进入时信号量值变为l;第3个进程申请进入时信号量值变为0、第4个进程申请进入时信号量值变为-1。因此信号量的变化范围是3,210-1。
三、综合应用题
16.(考研真题)3个进程P1、P2、P3,互斥地使用一个包含N(N0)个单元的缓冲区。P,每次用produce()生成一个正整数并用put()将其送入缓冲区的某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数的个数;P。每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数的个数。请用信号量机制实现这3个进程的同步与互斥活动并说明所定义的信号量的含义。要求用伪代码描述。 【参考答案】定义资源信号量empty,odd、even用于控制生产者与消费者之间的同步其中empty表示空缓冲区的数目odd表示缓冲区中奇数的个数even表示缓冲区中偶数的个数;定义互斥信号量mutex用于实现进程对缓冲区的互斥访问。伪代码描述如下:
17.(考研真题某银行提供了1个服务窗口和10个供顾客等待时使用的座位。顾客到达银行时若有空座位则到取号机上领取一个号,等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时通过叫号选取一位顾客并为其服务。顾客和营业员的活动过程描述如下。 cobegin {
process顾客{从取号机上获得一个号码;等待叫号;获得服务;process营业员{while (TRUE){叫号;为顾客服务;}} } coend请添加必要的信号量和P、V操作或wait()、signal(操作实现上述过程中的互斥与同步。要求写出完整的过程,说明信号量的含义并赋初值。
semaphore numget1, seats10,eustom0, //numget是关于取号机互斥的信号量;信号量seats是座位的个数:信号量cuslom是顾客的个数process顾客{P(seats);//看有没有空座位P(numget);//取号取号;V(numget);//取完号后释放取号机V(custom);等待叫号;V(seats);接受服务;}process 营业员{P(custom);叫号:为顾客服务;}20桌上有一个能盛得下5个水果的空盘子。爸爸不停地向盘中放苹果或橘子儿子不停地从盘中取出橘子享用,女儿不停地从盘中取出苹果享用。规定3人不能同时向(从)盘子中放(取水果。试用信号量来实现爸爸、儿子和女儿这3个“循环进程”之间的同步。
【参考答案】分析:本题是生产者-消费者问题的变形相当于一个能生产两种产品的生产者(爸爸向两个消费者儿子和女儿提供产品的同步问题因此,须设置两个不同的full信号量apple和orange它们的初值均为0。为了描述上述同步问题可定义如下信号量:
semaphore empty5, orange0, apple0, mutex1;四、存储器管理第5、6章
4. 存储器管理方式
4.1 连续分配方式
4.1.1 连续分配方式简介
标准定义 连续分配方式是指将进程所需的全部空间一次性分配在内存中的某一块连续区域。通俗解释 就好比你在房间里找一片连续的空地把你所有的行李都放在这片地方这就是连续分配。
4.1.2 固定分区分配分区表
标准定义 固定分区分配是指将内存分成若干个固定大小的分区每个分区可以分配给一个进程。通俗解释 就像把一个大的书架划分成几个固定大小的格子每个格子可以放一本书每个进程就像是一本书被放在一个固定的位置。
4.1.3 动态分区分配空闲分区表
标准定义 动态分区分配是指根据进程的实际大小分配内存形成不连续的空间。通俗解释 就像你在书房里找到一些空闲的地方每本书需要的地方不一样你就根据每本书的大小找到适合的空地这就是动态分区分配。
4.1.4 基于顺序搜索的动态分区分配算法
标准定义 基于顺序搜索的动态分区分配算法是指按照内存地址顺序搜索找到第一个满足大小要求的空闲分区进行分配。通俗解释 就像你在书房里从头到尾找一个适合放书的地方找到第一个足够大的地方就把书放进去这就是基于顺序搜索的动态分区分配算法。
4.1.5 分区分配算法的具体实现
首次适应算法 将空闲分区链按照地址递增的次序排列选择第一个满足大小要求的空闲分区进行分配。通俗解释 就像你在找一个地方安置你的家具从房间的一头开始找找到第一个合适大小的位置就摆放家具。 下次适应算法 类似首次适应算法但从上次分配结束的位置开始搜索以减少搜索范围。通俗解释 类似首次适应算法但是这次你从上次摆放的地方继续找以减少搜索的范围就像在书房里找书上次找到书的地方之后再找不用每次都从头找起。 最佳适应算法 将空闲分区链按照容量从小到大顺序排列选择第一个满足大小要求的空闲分区进行分配。通俗解释 就好比你在书房里挑最小的地方放书以确保每个小空间都被充分利用。 最坏适应算法 将空闲分区链按照容量从大到小顺序排列选择第一个满足大小要求的空闲分区进行分配。通俗解释 就好比你在书房里找到一个最大的空地把书放进去以确保每次分配都有足够大的空间就像是给每本书都留有大的空间。
4.1.6 分区分配算法的缺点
标准定义 连续分配方式的缺点是容易产生碎片包括外部碎片和内部碎片。通俗解释 就好比你在书房里不断地往书架上放书和取书最后可能会出现一些空隙有的是书架之间的有的是每个格子里没有完全放满的这些空隙就是碎片。
4.2 离散分配方式基本分页存储管理方式
4.2.1 离散分配方式简介
标准定义 离散分配方式是指将进程的空间分为若干个固定大小的块这些块不需要连续通过页表进行地址映射。通俗解释 想象一下你的电脑内存就像一片大草地离散分配方式就好比在这片草地上划分了很多小块每块都有自己的地址。通过一个地图页表你可以找到需要的块就像在地图上找到特定位置的小块一样。
4.2.2 分页地址的地址结构
标准定义 分页地址的地址结构包括页号和页内地址位移量通过这两个信息可以唯一确定一个地址。通俗解释 想象一本大书被分成很多页每页都有一个页号和具体的内容。这里的页号就是告诉你在哪一页而页内地址就是告诉你在这一页的哪个位置两者结合起来就能找到你需要的具体信息。
4.2.3 页表
标准定义 页表是为了实现从页号到物理块号的地址映射系统为每一个进程建立了一张页面映像表简称页表其中每一页表项记录了相应页对应的物理块。通俗解释 想象一张巨大的表格每行是一页表格中的每个小格记录了该页对应的实际存储位置。通过这个表格系统就知道如何将你书写的页号翻译成实际存储位置。
4.2.4 地址变换
标准定义 地址变换是将逻辑地址由页号和页内地址组成转换为物理地址的过程。通俗解释 想象你在图书馆查找一本书你拿到一张卡片逻辑地址上面写着书的名字和页码。地址变换就像你把这张卡片交给图书管理员他会告诉你具体在哪个位置找到这本书。在计算机中系统通过地址变换告诉硬件在哪里找到需要的数据。
4.2.5 具有块表的地址变换 标准定义 具有块表的地址变换是一种更加灵活的映射方式通过块表来实现逻辑地址到物理地址的转换。 通俗解释 这就像是有了一份更加详细的目录不仅可以找到具体的页号还可以通过块表找到更加具体的物理地址从而更快速地找到内容。
4.3 虚拟存储器管理
4.3.1 理论依据和基本概念
4.3.1.1 局部性原理
标准定义 局部性原理是指程序在执行过程中对存储器的访问呈现出一定的局部性即一段时间内访问的地址更有可能在某个较小的范围内。通俗解释 想象一下你在图书馆学习你不会一直在整个图书馆里乱翻书而是更有可能在某个时间段内只关注某一类书籍或者某个专业领域。这种学习的方式就体现了局部性原理即你在一段时间内对知识的访问集中在某个范围内。
4.3.1.2 虚拟存储器
标准定义 虚拟存储器是一种将磁盘空间扩展到物理内存之外的存储技术通过在磁盘和内存之间进行数据交换实现了程序执行所需的存储空间。通俗解释 想象一下你的电脑内存就像书桌上的工作空间而虚拟存储器就好比一个巨大的书柜。当你的书桌放不下更多的书时你可以把一些书暂时放到书柜里需要时再拿回来。虚拟存储器就是让计算机能够像这样灵活地利用磁盘空间将不常用的数据放到磁盘上保证内存始终留给当前需要的任务。
4.3.2 关键技术
4.3.2.1 请求调入
标准定义 请求调入是指在程序执行过程中发现所需数据不在内存中时系统将其从磁盘加载到内存的过程。通俗解释 就像是你在阅读一本书时需要翻到某一页但这一页不在当前打开的书上于是你通过翻开其他部分或者查找目录将需要的页调到当前位置。
4.3.2.2 置换
标准定义 置换是指当内存空间不足时系统决定将当前不活跃的数据移出内存腾出空间给即将调入的数据。通俗解释 就像是你在读一本书书桌上只能放下一些书当新的书需要放在桌上时你可能会将一些不常用的书放回书架给新书腾出空间。
4.3.3 虚拟存储器的特征
4.3.3.1 标准定义
虚拟存储器的特征包括能够让程序认为它拥有比实际物理内存更大的地址空间、允许程序在执行过程中动态加载和卸载数据、提高了系统的多道程序设计能力等。
4.3.3.2 通俗解释
更大的地址空间 就好像是你的电脑有了一个更大的书桌可以放更多的书。动态加载和卸载数据 就像是你可以根据需要随时取出或放回书而不是一次性将所有书都摆在桌子上。多道程序设计 就像是你可以同时阅读多本书而不必等待一本书读完再读下一本。
4.4 请求分页存储管理方式
4.4.1 请求分页存储管理的硬件支持
4.4.1.1 页表机制
标准定义 页表机制是指通过页表来实现从页号到物理块号的地址映射用于确定程序中各页在内存中的位置。通俗解释 就像是书的目录通过查找目录中的页号可以快速找到对应的物理块号从而知道该页在内存的位置。
4.4.1.2 缺页中断机构
标准定义 缺页中断是指当程序访问的页不在内存中时触发的中断系统需要将该页从磁盘加载到内存。通俗解释 就像是你在读一本书要翻到某一页但发现这一页不在打开的书上于是你需要通过查找或请求将需要的页从书架上拿到桌上。
4.4.1.3 地址变换机构
标准定义 地址变换机构是指通过页表和地址变换的方式将逻辑地址转换为物理地址的硬件机制。通俗解释 想象一下你在使用地图找到一个城市的具体位置。这个过程中地图就好比页表而你手中的坐标就是逻辑地址。地址变换机构就像是你根据地图上的信息将逻辑地址坐标转换成实际的物理位置帮助你准确找到目标。在计算机中这个机构通过硬件的方式实现确保程序能够在内存中正确访问数据。
4.4.2 缺页中断和一般中断的联系与区别
4.4.2.1 联系
联系 缺页中断是一种中断机制和一般中断一样都是由硬件或软件触发导致程序的正常流程被中断。
4.4.2.2 区别
区别 缺页中断是特定于分页存储管理方式的一种中断它表示程序访问的页不在内存中需要从磁盘加载。而一般中断是指系统发生了某种事件需要引起处理程序的注意。
通过缺页中断系统可以在需要时动态地将数据从磁盘加载到内存保证程序的正常执行。这种机制使得程序的地址空间可以大于实际物理内存提高了系统的灵活性和效率。
4.5 页面置换算法
4.5.1 OPT最佳置换算法
4.5.1.1 标准定义
标准定义 OPTOptimal Replacement是一种理想情况下的页面置换算法它会选择未来最长时间内不会被访问的页面进行置换。通俗解释 OPT 就好比你在一家图书馆能够预测哪本书将来最久都不会再有人借阅。一旦找到这本书就把它从书架上拿下来腾出空间给新的书。这个过程就是 OPT 算法的思想总是选择最佳的替换方式。
4.5.2 FIFO先进先出算法
4.5.2.1 标准定义
标准定义 FIFOFirst-In-First-Out是一种简单的页面置换算法它选择最早进入内存的页面进行置换。通俗解释 FIFO 就好比你在超市排队结账谁先到的就先结账离开。在计算机中谁先进入内存的页面就先被踢出去给后来的页面腾位置。
4.5.3 LRU最近最少使用算法
4.5.3.1 标准定义
标准定义 LRULeast Recently Used是一种基于页面使用历史的算法它选择最近最久未被使用的页面进行置换。通俗解释 想象你有一个装满零食的篮子每袋零食代表内存中的一个页面。每当你想吃零食时你都会选择吃掉篮子里最久没吃过的那袋这样你总是能够享用到相对新鲜的零食。LRU 算法就像是你总是选择吃掉最久没被吃过的零食一样系统总是选择最近最少使用的页面保留在内存中而把最久没被使用的页面替换出去以确保内存中的数据相对较新。
这三种页面置换算法各有优劣选择哪种算法取决于具体的应用场景和系统特点。OPT具有理论上的最优性但实现较为困难FIFO简单实用但可能导致“老化”页面长时间停留在内存中LRU在实际中表现较好但需要维护访问时间的信息增加了系统的开销。在不同情况下选择适合的算法可以有效提高存储器管理的效率。
4.6 习题5 4.7 习题6 五. 输入输出系统第7章
5.1 I/O设备的类型
标准定义 I/O设备可分为独占设备、共享设备和虚拟设备。
解释 独占设备 定义 某一时刻只能被一个程序独占使用的设备。其他程序需要等待设备空闲才能使用。比喻 就像一部独立的打印机一次只能服务一个人其他人需要等待。 共享设备 定义 多个程序可以同时访问和使用的设备系统通过管理和调度来确保并发操作。比喻 就像一个共用的公共汽车多个人可以同时搭乘系统会安排好谁先上车。 虚拟设备 定义 设备的逻辑功能由操作系统虚拟出来实际物理设备可能不止一个通过虚拟化技术提供给应用程序使用。比喻 想象你在玩模拟城市游戏你创建了一个虚拟的市政建筑虽然在现实中并不存在但在游戏中其他虚拟角色和系统都与它进行交互。这个虚拟市政建筑就像是虚拟设备通过软件虚拟化技术创建为应用程序提供一种虚拟的逻辑功能。
5.2 I/O通道、I/O通道类型、通道与一般处理器的区别 I/O通道的标准定义 I/O通道Input/Output Channel是计算机中负责连接主存储器和外部设备的通信路径。它起到了数据传输的桥梁作用允许外部设备和主存之间进行高速、独立的数据交换。 通俗解释 想象I/O通道是计算机的交通管制中心它负责管理和协调数据在主存储器和外部设备之间的流动。就像是一个交通警察确保信息能够在系统内部畅通无阻地传递。 I/O通道就像是计算机的高速传送带它连接着计算机的大脑主存储器和外部设备负责快速而独立地将数据传递过去。你可以把它想象成一个快递员负责把主存储器的数据快速、可靠地送达给外部设备或者将外部设备的数据迅速送达给主存储器。这样计算机内外的信息就可以高效地来回传送。 I/O通道类型的标准定义
定义 字节多路通道 工作方式 按字节交叉方式工作的通道主要连接低速设备。子通道 通道分为子通道每个子通道连接一个设备。子通道之间相互独立可以同时操作多个设备。应用 适用于连接低速设备通过按字节的方式进行数据传输。 数组选择通道 工作方式 可以连接多台高速设备但在一段时间内只允许一台设备传输数据传输率高。当某台设备占用了通道后其他设备需要等待。应用 适用于连接高速设备但通道利用率较低因为一旦通道被某设备占用其他设备不能同时使用。 数组多路通道 特点 结合了前两者的优点含有多个非分配型子通道。子通道 各子通道设备分时并行操作允许多个设备同时传输数据。优势 既具有较高的数据传输速率又能获得令人满意的通道利用率。
通俗解释 字节多路通道 比喻 想象一条道路分成几个车道每个车道都通向不同的目的地。解释 这就像一条路上有几个车道每个车道都可以独立地让车辆设备通过。车辆可以按照字节的方式逐个字节交叉通过这适用于速度较慢的设备。 数组选择通道 比喻 想象一个高速收费站只允许一辆车通过其他车辆需要等待。解释 这就像一个高速收费站一次只能通过一辆车设备虽然速度很快但其他车辆需要等待不能同时通过。适用于速度较快但需要独占通道的设备。 数组多路通道 比喻 想象一条多车道高速每个车道都可以独立通行允许多辆车同时行驶。解释 这就像一条多车道高速每个车道都可以独立运行允许多辆车设备同时行驶。它结合了速度和并发性的优势。
通道与一般处理器的区别 I/O通道是专门设计用于数据传输的与主处理器CPU有所区别。主处理器负责执行计算任务而I/O通道专注于有效地管理外部设备和内存之间的数据传递以提高整体系统性能。
标准定义 通道是一种专门负责I/O设备数据传输的处理器它独立于主处理器通过并行、高效地处理大量数据提高了I/O操作的速度。与一般处理器相比通道更专注于数据传输而非通用计算。通俗解释 想象计算机是一座工厂一般处理器就像工厂的总经理负责全局的工作安排和决策。而通道就是专门的搬运工他们负责将原材料数据从外部设备运送到工厂主存储器或将成品处理好的数据从工厂送到外部设备。通道搬运工非常擅长这个任务可以同时搬运很多数据而不会占用总经理一般处理器太多时间和精力。因此通道和一般处理器在工作的专注程度和任务领域上有所区别。 5.3 I/O控制方式 I/O控制方式的标准定义 I/O控制方式指的是计算机系统中管理和协调输入/输出操作的方式。常见的方式包括程序I/O、中断I/O、DMA方式和通道方式。 通俗解释 程序I/O 就像是你亲自去超市购物需要逐个挑选商品主动控制整个购物过程。中断I/O 类似于你在超市购物时有了购物清单当你需要的商品出现时收银员通知你可以结账不需要你一直等在货架前。DMA方式 像是雇佣了一名速递员他负责将你购物清单上的商品直接送到你手上你不需要亲自前往。通道方式 就像是你委托了一位购物助手他负责帮你挑选商品、结账等你只需等待结果。 想象你在玩一场电子游戏而这场游戏就是计算机系统。I/O控制方式就像是你选择游戏角色与游戏互动的方式。有四种方式可以选择 程序I/O 就像你亲自控制游戏角色的每一步每次操作都由你来决定但可能会花费更多时间和精力。 中断I/O 类似于你在游戏中碰到了特殊任务需要你停下手头的操作去处理这个任务然后再回到原来的操作。 DMA方式 好比你请了一位助手专门负责搬运游戏中的物品你不必亲自去搬运可以把更多精力放在其他操作上。 通道方式 就像你雇佣了一个专业的团队他们负责协调和管理游戏中所有复杂的操作你只需告诉他们你的需求剩下的交给他们处理。这种方式效率高可以同时处理多个任务。不同的I/O控制方式就是在选择如何与游戏进行互动以及如何协调和处理各种任务。 程序控制型 像是手动操作需要中央处理器CPU不断发出指令告诉I/O通道何时开始或结束数据传输。 中断控制型 当外部设备准备好或者出现特定事件时中断通知I/O通道启动数据传输减轻了CPU的负担。 DMA型 直接存储器访问允许外部设备和内存之间直接交换数据不需要CPU介入效率更高。 想象你在操控一辆汽车而这辆汽车就是计算机的I/O通道。有三种不同的方式来驾驶这辆车分别对应三种I/O通道类型。第一种是“程序控制型”就像你手动操作每个车速和方向的控制器一样每一步都由你决定。第二种是“中断控制型”有点像你遇到交通信号时暂时停车等到有新指示时再继续前行。第三种是“直接存储器访问DMA型”就像你设置了一个目的地汽车可以自动沿着预定的路径行驶而你则可以专注于其他任务这提高了效率。不同的I/O通道类型就是决定这辆车如何驾驶以及数据如何在计算机内部和外部之间流动的方式。 5.4 I/O缓冲技术 I/O缓冲技术的标准定义 I/O缓冲技术是一种通过在计算机系统中引入缓冲区将输入/输出数据暂时存储起来以提高数据传输效率的方法。 通俗解释 想象你在使用手机浏览网页当你打开一个网页时页面上的图片和文字可能不是一次性全部加载完毕的而是逐步显示。这就好比浏览器采用了一种类似于I/O缓冲技术的方法提前加载一部分内容让用户感觉到更快的响应速度。
想象你在一家快餐店点餐而I/O缓冲技术就好比是你的点餐篮。当你点好餐后服务员不会立刻把食物逐一送到你手里而是先把你的订单放进点餐篮然后厨房根据这个篮子里的订单一次性准备好所有的食物最后一起交给你。这样就避免了每点一个菜都等待厨房准备的时间提高了整体服务效率。在计算机中I/O缓冲技术也是类似的通过引入缓冲区可以将输入/输出数据先存储起来等到一定量的数据积累后再进行高效的批量传输提高了数据传输的效率。 5.5 磁盘性能的影响因素 磁盘性能的标准定义 磁盘性能的影响因素主要包括寻道时间、旋转延迟和传输时间这些因素共同影响着磁盘读写操作的速度。 通俗解释 想象一下你在书架上查找一本书首先需要找到这本书所在的书架寻道时间然后等待这本书刚好处于你手边旋转延迟最后才能够翻阅书本内容传输时间。整个过程中每个步骤都会影响你获取书本信息的速度。 5.6 磁盘调度算法
5.6.1 FIFO先进先出 FIFO算法的标准定义 FIFO是一种磁盘调度算法按照磁盘请求的先后顺序进行调度先发出的请求先被满足。 通俗解释 就像是你在餐厅排队先到的人先被安排进餐按照先来先服务的原则。
5.6.2 SSTF最短寻道时间优先 SSTF算法的标准定义 SSTF是一种磁盘调度算法选择当前磁头位置最接近请求的磁道进行调度以减少寻道时间。 通俗解释 像是你在书架上找书每次都选择最接近手的那本书以最短的距离找到需要的书本。
5.6.3 SCAN扫描 SCAN算法的标准定义 SCAN是一种磁盘调度算法磁头按照一个方向移动直到碰到最边缘然后改变方向继续移动以此往复。 通俗解释 想象一下你在图书馆找书SCAN算法就像你从书架的一端开始按照一个方向扫描书架找到目标书籍后再改变方向直到扫描完整个书架。这样可以比较高效地找到你需要的书籍就像磁头在磁盘上按照一个方向移动找到需要的数据。
5.6.4 CSCAN循环扫描 CSCAN算法的标准定义 CSCAN是SCAN算法的一种改进版本磁头在到达磁盘末端时立即返回到磁盘起始位置形成一个循环。 通俗解释 类似于SCAN算法但是当到达磁盘末端时直接返回到磁盘起始位置再次开始扫描。 如果把SCAN算法比喻为你在图书馆来回扫描书架那么CSCAN就是你扫描完一遍后立即回到书架的开始重新扫描。这样做的好处是可以更加连贯地管理书架不会漏掉任何可能需要的书籍就像磁头在磁盘上形成一个循环提高了数据的读取效率。
5.7 习题
见6.5 六、文件管理 第8,9章
6.1 文件系统的功能
6.1.1 文件存储空间的管理
标准定义 文件系统负责有效管理存储设备上的文件存储空间确保文件能够被合理地存储、检索和组织。 通俗解释 文件系统就像是你的个人图书馆管理员负责管理书架上的图书。它要确保每本书都有合适的位置可以轻松找到还需要保证新添的书籍能够有序地放入。同样文件系统管理文件的存储空间让文件可以被方便地存储、找到和整理确保计算机上的数据有序可控。
6.1.2 目录管理
标准定义 文件系统通过目录管理组织和维护文件的层次结构以方便用户查找、访问和组织文件。
通俗解释 目录管理就像是你整理书架上的书籍一样。每本书有一个特定的位置而目录就是一个书籍清单告诉你每本书在哪里。文件系统的目录管理类似它创建了一个文件清单让你可以方便地查找和访问文件就像在图书馆的目录中找到书籍一样。这样你可以更轻松地组织和管理计算机上的文件。
6.1.3 文件的读写管理和保护
标准定义 文件系统负责管理文件的读写操作同时确保文件只能被授权的用户或进程访问以保护文件的完整性和安全性。
通俗解释 文件的读写管理就像是图书馆的规定只有借书证的人才能借书而文件系统就是为文件颁发了一种“文件借书证”只有持有这个证件的人或程序才能对文件进行读写操作。这样就能够有效地保护文件防止未经授权的人或程序进行随意操作确保文件的安全性和完整性。
6.2 文件的逻辑结构、物理结构概念
6.2.1 文件的逻辑结构
标准定义 文件的逻辑结构是指文件中数据元素之间的关系和组织方式包括文件的组织形式、数据的表示方法等。
通俗解释 文件的逻辑结构就像一本书的目录和章节安排它定义了文件中数据元素之间的关系和组织方式。想象一下一本小说它有序的章节和段落就构成了逻辑结构让读者可以按照一定的组织方式理解故事。文件的逻辑结构也是为了让计算机更好地理解和处理文件中的数据就像读者通过目录找到感兴趣的章节一样。
6.2.2 文件的物理结构
标准定义 文件的物理结构是指文件在存储设备上的实际存储方式包括文件的存储布局、磁盘块的组织等。
通俗解释 文件的物理结构就像一本书在书架上的具体存放方式它定义了文件在存储设备上的实际存储布局。想象一下你的书架每本书都占据一定的空间文件的物理结构也是为了将数据有序地存储在计算机的存储设备上就像书籍有特定的位置一样。这种存储方式能够帮助计算机更高效地读取和写入文件中的数据。
6.3 外存的分配方式
6.3.1 顺序式结构
标准定义 外存的顺序式结构是指文件在存储设备上按照逻辑顺序依次存储形成一个连续的数据块。
通俗解释 顺序式结构就像你在一张纸上按照顺序写下的文字每行都连接着上一行文件在外存中也是按照逻辑顺序一个接一个地存储就像连续的文字一样。这种结构使得文件的读取和写入相对简单就像你可以顺着纸上的文字一行一行读取一样。
6.3.2 链接式结构
标准定义 外存的链接式结构是指文件在存储设备上通过链接方式相互连接形成一个链表结构。
解释 想象一本书的每一页都贴着指向下一页的标签你可以根据标签跳转到其他页面。链接式结构就是通过这种方式连接文件的不同部分你可以通过链接找到文件的特定位置。 通俗解释 链接式结构就像你在纸上画的一组相互连接的箭头每个箭头指向下一个位置。文件在外存中也可以通过链接方式相互连接形成一个链表每个部分都知道下一个部分在哪里。这种结构使得在文件中插入或删除数据变得更加灵活就像你可以在图上添加或删除箭头一样。
6.3.3 索引式结构
标准定义 外存的索引式结构是指使用索引表来记录文件的存储位置通过索引查找实际数据块。
解释 比如一本书有一张目录列出了关键词和对应的页码。你可以通过查阅目录找到关键词对应的页码然后直接翻到该页。索引式结构就是通过索引表来快速定位文件的存储位置加速检索过程。 通俗解释 索引式结构就像一本书的目录记录着每个章节的页码文件在外存中也有一个索引表记录着每个数据块的位置。当需要查找特定数据时系统可以先查找索引表找到对应的位置然后直接跳到这个位置获取数据就像你通过书的目录找到特定章节一样这种结构有助于快速定位和获取文件中的数据。
6.4 Unix的混合索引方式
标准定义 Unix的混合索引方式是一种文件索引结构其中的索引结点i-node包含13个地址项iaddr(0)~iaddr(12)用于管理文件的存储位置。
解释 想象一个文件像一本书而索引结点就像书的目录。Unix的混合索引方式相当于在目录上设置了多个指针以便更有效地定位书中的不同章节。
iaddr(0)~iaddr(9)用来存放直接地址就像目录中列出直接可以查找的章节一样直接指向数据块。iaddr(10)用来存放一次间接地址类似于目录中有一个链接通过这个链接你可以找到另一个目录进而找到特定章节。iaddr(11)用来存放二次间接地址扩展了查找的范围就像有了两级目录结构。iaddr(12)用来存放三次间接地址进一步增加了查找的深度使得文件可以更加灵活地存储和组织。
通俗解释 Unix的混合索引方式就像你在一张地图上看到的一个标志上面有13个箭头每个箭头指向一个地点。这个标志就像Unix系统中的索引结点它包含13个地址项每个项指向文件在存储设备上的一个位置。当需要找到文件时系统可以根据这些地址项直接跳转到相应的位置就像你通过地图上的标志找到具体的地点一样。这种结构的设计有助于高效地管理文件的存储位置。
6.5 存储空间管理
标准定义 存储空间管理是文件系统用于有效组织和分配存储设备上的空间的一系列策略和方法包括空闲表法、位示图法和成组链接法等。
解释 存储空间管理就像图书馆管理员对书架上的书籍进行整理和分配一样确保每本书都有自己的位置。空闲表法记录可用的空间位示图法标记已使用的空间而成组链接法则是将空间按组织单元进行管理以提高效率。 空闲表法 定义 空闲表法通过维护一张表格来记录哪些存储块是空闲的哪些被占用。比喻 就像图书馆管理员维护一张书架上哪些位置有书、哪些位置是空的记录表一样方便查找可用的存储块。 位示图法 定义 位示图法使用位图来表示存储块的占用情况每个位对应一个存储块0表示空闲1表示占用。比喻 类似于城市停车场入口的指示牌每个车位都有一个小灯绿灯表示空闲红灯表示占用司机通过观察指示牌就能知道哪里有空车位。 成组链接法 定义 成组链接法将空闲存储块以链表的形式组织每个存储块中包含指向下一个空闲块的指针。比喻 就像一串串的火车车厢每个车厢上都有一个指示下一辆车的标志当需要添加或释放车厢时只需调整指针即可。
这些管理方法都旨在高效地组织存储空间确保系统可以有效地存储和检索数据。
通俗解释 存储空间管理就像你在书架上安排图书的方式确保每本书都有一个适当的位置。文件系统通过一系列策略和方法来有效地组织和分配计算机存储设备上的空间就像你在书架上安排图书一样。有些文件系统使用空闲表法记录可用的空间有些使用位示图法通过位图表示每个存储块的占用情况还有一些使用成组链接法将存储空间组织成一组一组的块。这些方法有助于系统高效地利用存储资源。
6.5 习题
一.简答题共6题,65.0分
1、有哪几种I/O控制方式各适用于何种场合
正确答案 I/O控制方式包括程序I/O方式、中断I/O控制方式、DMA控制方式、通道控制方式。程序I/O方式适用于早期的计算机系中并且是无中断的计算机系统中断I/O控制方式是普遍用于现代的计算机系统DMA方式适用于I/O设备为块设备时在和主机进行数据交换的一种I/O控制方式当I/O设备和主机进行数据交换是一组数据块时通常采用通道I/O控制方式但此时要求系统必须配置相应的通道及通道控制器。
2、引入缓冲的主要原因是什么缓冲区都有哪些组织形式
正确答案 引入缓冲区的目的是缓和CPU与I/O设备之间速度不匹配的矛盾减少对CPU的中断频率放宽CPU对中断响应时间的限制解决数据力度不匹配的问题提高CPU和I/O设备之间的并行性。 缓冲区的组织形式包括单缓冲、双缓冲、循环缓冲和缓冲池。 答案解析
3、目前的磁盘调度算法有哪几种每种算法优先考虑的问题是什么
正确答案 日前常用的磁盘调度算法有先来先服务、最短寻道时间优先及扫描等算法。 1先来先服务算法优先考虑进程请求访问磁盘的先后次序 2最短寻道时问优先算法优先考虑要求访问的磁道与当而磁头所在磁道距离是否最近 3扫描算法考虑欲访间的磁道与当前磁道间的距离更优先考虑磁头当前移动方向。
4、按文件的组织方式可将文件分为哪几种类型
正确答案 顺序文件、索引文件和索引顺序文件
5、目前广泛采用的目录结构有哪些它有什么优点
正确答案 日前广泛采用的日录结构是树型目录结构。它具有以下优点 1能有效提高对目的检索速度 2允许文件重名由于在树型结构的文件系统中是利用文件路径名来检索文件的故允许每个用户在自己的分目录中使用与其他用户文件相同的名字 3使于实现文件共享:在树型目录中用户可通过路径名来共享其他用户的文件也可将一个共享文件链接到自己的目录下。
6、目前常用的外存组织方式有哪些试比较其优缺点。
正确答案 顺序文件、链接文件和索引文件。 1顺序文件简单容易实现顺序访问速度快。但必须事先知道文件的长度文件长度不能动态增长。要求连续存储空间删除文件的某部分后产生外部碎片。严重降低外存空间的利用率。 2链接文件不要求连续分配消除了外部碎片文件可动态增长、插入、删除。但只适宜顺序存取磁头移动距离多指针链接可靠性降低指针占用空间。 3索引文件便于动态增长便于随机存取无外部碎片。 但增加索引表的空间开销存取文件需两次访问外存。
二.计算题共3题,35.0分
1、设有如下磁道访问请求序列
23598 1466257834667456871239714958 当前磁头在50道上次访问的磁道是18道。 试计算SSTF算法、SCAN和CSCAN三种调度算法下的平均寻道长度并比较结果。 正确答案
2、一个磁盘的转速是3000rpm盘面划分成10个扇区则读取一个扇区的时间是多少
正确答案 磁盘旋转一周需要的时间1/3000rpm1/50rps20ms 每个盘面10个扇区则读取一个扇区的时间20/102ms
3、设文件索引结点中有7个地址项其中4个地址为直接地址2个地址为一级间接索引1个地址二级间接索引每个地址项大小为4B若磁盘索引块和磁盘数据块的大小均为256B则可表示的单个文件最大长度是多少
正确答案 磁盘每个数据块的大小是256B则一个数据块中能存储256/464个地址项4个直接地址指向的数据块大小为4*265B1024B1KB2个一级间接地址所指向的数据块大小为2 * 64 * 256B32KB1个二级间接地址所指向的数据块大小为64 * 64 * 256B1024KB则7个地址所指向的数据块的总大小为1KB32KB1024KB1057KB。
