谢旭升《操作系统教程》课后习题解答

word文件下载地址在文末

谢旭升《操作系统教程》课后习题解答

习题一

1.设计操作系统的主要目的是什么?

设计操作系统的目的是:

(1)从系统管理人员的观点来看,设计操作系统是为了合理地去组织计算机工作流程,管理和分配计算机系统硬件及软件资源,使之能为多个用户所共享。因此,操作系统是计算机资源的管理者。

(2)从用户的观点来看,设计操作系统是为了给用户使用计算机提供一个良好的界面,以使用户无需了解许多有关硬件和系统软件的细节,就能方便灵活地使用计算机。

 

2.操作系统的作用可表现在哪几个方面?

(1) 方便用户使用:操作系统通过提供用户与计算机之间的友好界面来方便用户使用。

(2) 扩展机器功能:操作系统通过扩充硬件功能和提供新的服务来扩展机器功能。

(3) 管理系统资源:操作系统有效地管理系统中的所有硬件和软件资源,使之得到充分利用。

(4) 提高系统效率:操作系统合理组织计算机的工作流程,以改进系统性能和提高系统效率。

(5)构筑开放环境:操作系统遵循国际标准来设计和构造一个开放环境。其含义主要是指:遵循有关国际工业标准和开放系统标准,支持体系结构的可伸缩性和可扩展性;支持应用程序在不同平台上的可移植性和互操作性。

 

3.试叙述脱机批处理和联机批处理工作过程

(1)联机批处理工作过程

用户上机前,需向机房的操作员提交程序、数据和一个作业说明书,后者提供了用户标识、用户想使用的编译程序以及所需的系统资源等基本信息。这些资料必须变成穿孔信息,(例如穿成卡片的形式),操作员把各用户提交的一批作业装到输入设备上(若输入设备是读卡机,则该批作业是一叠卡片),然后由监督程序控制送到磁带上。之后,监督程序自动输入第一个作业的说明记录,若系统资源能满足其要求,则将该作业的程序、数据调入主存,并从磁带上调入所需要的编译程序。编译程序将用户源程序翻译成目标代码,然后由连接装配程序把编译后的目标代码及所需的子程序装配成一个可执行的程序,接着启动执行。计算完成后输出该作业的计算结果。一个作业处理完毕后,监督程序又可以自动地调下一个作业处理。重复上述过程,直到该批作业全部处理完毕。

(2)脱机批处理系统

脱机批处理系统由主机和卫星机组成,如下图所示。卫星机又称外围计算机,它不与主机直接连接,只与外部设备打交道。卫星机负责把输入机上的作业逐个转输到输入磁带上,当主机需要输入作业时,就把输入带与主机连上。主机从输入带上调入作业并运行,计算完成后,输出结果到输出磁带上,再由卫星机负责把输出带上的信息进行输出。在这样的系统中,主机和卫星机可以并行操作,二者分工明确,可以充分发挥主机的高速计算能力。

 

 

 

 

 

4.分时系统的特征是什么?

(1)同时性。允许在一台主机上同时联接多台联机终端,系统按分时原则为每个用户服务。宏观上,是多个用户同时工作,共享系统资源;而微观上,则是每个用户作业轮流运行一个时间片。它提高了资源利用率,从而促进了计算机更广泛的应用。

(2)独立性。每个用户各占一个终端,彼此独立操作,互不干扰。因此,用户会感觉到就像他一人独占主机。

(3)及时性。用户的请求能在很短时间内获得响应,此时间隔是以人们所能接受的等待时间来确定的,通常为2--3秒钟。

(4)交互性。用户可通过终端与系统进行广泛的人机对话。其广泛性表现在:用户可以请求系统提供多方面的服务,如文件编辑、数据处理和资源共享等。

 

5.何谓多道程序设计?叙述它的主要特征和优点。

多道程序设计是一种软件技术,该技术使同时进入计算机主存的几个相互独立的程序在管理程序控制之下相互交替地运行。当某道程序因某种原因不能继续运行下去时(如等待外部设备传输数据),管理程序便将另一道程序投入运行。这样可以使中央处理器及各外部设备尽量处于忙碌状态,从而大大提高计算机的使用效率。

在单处理器系统中,多道程序运行的特征是:

(1)多道:即计算机主存中同时存放几道相互独立的程序。

(2)宏观上并行:同时进入系统的几道程序都处于运行过程中,即它们先后开始了各自的运行,但都未运行完毕。

(3)微观上串行:从微观上看,主存中的多道程序轮流地或分时地占用处理器,即多道程序交替执行。

引入多道程序设计的优点是:

(1)可提高CPU的利用率;

(2)可提高主存和I/O设备利用率;

(3)可增加系统吞吐量;

 

6.实现多道程序应解决哪些问题?

为使系统中的多道程序能协调地运行,必须解决以下一些问题:

(1)并行运行的程序要共享计算机系统的硬件和软件资源,既有对资源的竞争,但又必须相互同步。因此同步与互斥机制成为系统设计中的重要问题。

(2)多道程序的增加,出现了主存不够用的问题,提高主存的使用效率也成为关键。因此出现了诸如覆盖技术、对换技术和虚拟存储技术等主存管理技术。

(3)多道程序存在于主存,为了保证系统程序存储区和各用户程序存储区的安全可靠,提出了主存保护的要求。

 

7.试比较单道与多道批处理系统的特点及优缺点。

单道批处理系统的特征是:

(1)自动性。在顺利的情况下,在磁带上的一批作业能自动地逐个作业依次运行,而无须人工干预。

(2)顺序性。磁带上的各道作业是顺序地进入主存,各道作业完成的顺序与它们进入主存的顺序之间,在正常情况下应当完全相同,亦即先调入主存的作业先完成。

(3)单道性。主存中仅有一道程序并使之运行,即监督程序每次从磁带上只调入一道程序进入主存运行,仅当该程序完成或发生异常情况时,才调入其后继程序进入主存运行。

其优点是:作业运行期间占有所有资源,运算速度较快。

其缺点是:CPU、主存和I/O设备资源利用率低;系统吞吐量低;

 

多道程批处理系统的特征是:

(1)多道:即计算机主存中同时存放几道相互独立的程序。

(2)宏观上并行:同时进入系统的几道程序都处于运行过程中,即它们先后开始了各自的运行,但都未运行完毕。

(3)微观上串行:从微观上看,主存中的多道程序轮流地或分时地占用处理器,即多道程序交替执行。

其优点是:可提高CPU、主存和I/O设备利用率;可增加系统吞吐量;

其缺点是:每个作业占用内存相对减少;作业交替运行需要时间切换;竞争资源会导致死锁和安全问题,等。

 

8.为什么要引入实时操作系统?

60年代中期计算机进入第三代,计算机的性能和可靠性有了很大提高,造价亦大幅度下降,导致计算机越来越广泛应用于工业过程控制、军事实时控制、信息实时处理等领域,需要保证及时响应、快速处理、高可靠性和安全性,而不强求系统资源的利用率。一般操作系统不能达到这些要求。而针对实时处理的实时操作系统是以在允许的时间范围之内做出响应为特征的并具有高可靠性和安全性。它要求计算机对于外来信息能以足够快的速度进行处理,并在被控对象允许时间范围内作出快速响应,其响应时间要求在秒级、毫秒级甚至微秒级或更小。实时系统是较少有人为干预的监督和控制系统,仅当计算机系统识别到了违反系统规定的限制或本身发生故障时,才需要人为干预。

 

9.操作系统具有哪几大特征?

虽然不同的操作系统各有自己的特征,但它们也都具有以下四个基本特征:

(1)并发

并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下,并发性是指宏观上在一段时间内多道程序在同时运行。但在单处理器系统中,每一时刻仅能执行一道程序,故微观上这些程序是在交替执行的。

(2)共享

所谓共享是指系统中的资源可供主存中多个并发执行的进程共同使用。由于资源的属性不同,故多个进程对资源的共享方式也不同。

并发和共享是操作系统的两个最基本的特征,它们又是互为存在条件。一方面,资源共享是以程序(进程)的并发执行为条件;若系统不允许程序并发执行,自然不存在资源共享问题。另一方面,若系统不能对资源共享实施有效管理,则也必将影响到程序的并发执行,甚至根本无法并发执行。

(3)虚拟

操作系统中的所谓“虚拟”是指通过某种技术把一个物理实体变成若干个逻辑上的对应物。物理实体(前者)是实的,即实际存在的,而后者是虚的,是用户感觉上的东西。

(4)异步性

在多道程序环境下,允许多个进程并发执行,但由于资源等因素的限制,通常进程的执行并非“一气呵成”,而是以“走走停停”的方式运行,即进程是以异步方式运行的。尽管如此,但只要运行环境相同,作业经多次运行,都会获得完全相同的结果,因此,异步运行方式是允许的。

 

10.主存管理的主要任务是什么?有哪些主要功能?

存储管理的主要任务是为多道程序的运行提供良好的环境,方便用户使用存储器,提高存储器的利用率,以及能从逻辑上来扩充主存。为此,存储管理应具有以下功能:

(1)主存分配与回收;

(2)地址转换和存储保护;

(2)主存的共享与保护;

(3)主存扩充。

 

11.处理器管理的主要任务是什么?有哪些主要功能?

处理器管理的主要任务是对处理器进行分配,并对其运行进行有效的控制和管理。对处理器的管理和调度可归结为对进程和线程的管理和调度。它包括以下几方面功能:

(1)进程控制和管理;

(2)进程同步和互斥;

(3)进程通信;

(4)进程死锁;

(5)线程控制和管理;

(6)处理器调度。

 

12.设备管理的主要任务是什么?有哪些主要功能?

设备管理的主要任务是管理各种外部设备,完成用户提出的I/O请求,为用户分配I/O设备;提高CPU和I/O设备的利用率;提高I/O速度;方便用户使用I/O设备。为实现上述任务,设备管理应具有以下主要功能:

(1)提供设备控制处理;

(2)提供缓冲区管理;

(3)提供设备独立性;

(4)实现设备的分配与回收;

(5)实现共享设备的驱动调度;

(6)实现虚拟设备。

 

13.文件管理的主要任务是什么?有哪些主要功能?

文件管理的主要任务是对用户文件和系统文件进行有效管理,以方便用户使用,并保证文件的安全性。为此,文件管理应具有以下主要功能:

(1)提供文件的逻辑组织方法;

(2)提供文件的物理组织方法;

(3)提供文件的存取和使用方法;

(4)提供文件的目录管理;

(5)实现文件的共享和保护;

(6)实现文件的存储空间管理。

 

14.试在交互性、及时性和可靠性方面,将分时系统与实时系统进行比较。

在交互性方面,分时系统的交互性强,实时系统的交互性弱,因为交互性强很能满足实时系统响应速度快和高可靠性的要求。

在及时性方面,实时系统要求快速响应而及时性强,分时系统相比较及时性较差。

在可靠性方面,实时系统要求高可靠性而可靠性强,分时系统相比较可靠性较差。

 

15.是什么原因使操作系统具有异步性特征?

在多道程序环境下,允许多个进程并发执行,但由于资源数量有限而每个进程在运行中需要竞争资源,导致进程的执行并非“一气呵成”,而是以“走走停停”的方式运行,即进程是以异步方式运行的。主存中的每个进程在何时执行,何时暂停,以怎样的速度向前推进,每道程序总共需多少时间才能完成,都是不可预知的。很可能是先进入主存的作业后完成,而后进入主存的作业先完成。

 

16.试说明网络操作系统的主要功能。

网络环境下的操作系统既要为本机用户提供简便、有效地使用网络资源的手段,又要为网络用户使用本机资源提供服务。为此,网络操作系统除了具备一般操作系统应具有的处理器管理、存储区管理、设备管理,文件管理等功能模块之外,还要增加网络功能模块,主要应具有下述五方面的功能:

(1)网络通信

这是网络最基本的功能,其任务是在源主机和目标主机之间实现无差错的数据传输。

(2)网络资源管理

对网络中的共享资源(硬件与软件)实施有效的管理,协调各用户对共享资源的使用,保证数据的安全性和一致性。

(3)网络服务

这是在前两个功能的基础上,为了方便用户而直接向用户提供的多种有效服务。例如:电子邮件服务、共享打印服务、共享硬盘服务等。

(4)网络管理

网络管理最基本的任务是安全管理。比如,通过“存取控制”来确保存取数据的安全性;通过“容错技术”来保证系统故障时数据的安全性。此外,还应能对网络性能进行监视,对使用情况进行统计,以便为提高网络性能、进行网络维护和记帐等提供必要的信息。

(5)互操作能力

在90年代后推出的网络操作系统,提供了一定范围的互操作能力。所谓互操作,在客户/服务器模式的局域网环境下,是指连接在服务器上的多种客户机和主机,不仅能与服务器通信,而且还能以透明的方式访问服务器上的文件系统;而在互连网络环境下的互操作,是指不同网络间的客户机不仅能通信,而且也能以透明的方式,访问其它网络中的文件服务器。

 

17.试比较网络操作系统与分布式操作系统。

计算机网络是通过通信设施将物理上分散的、具有自治功能的多个计算机系统互连起来的,实现信息交换、资源共享、可互操作和协作处理的系统。

在计算机网络中,每个主机都有操作系统,它为用户程序运行提供服务。当某一主机联网使用时,该系统就要同网络中更多的系统和用户交往,这个操作系统的功能就要扩充,以适应网络环境的需要。网络操作系统既要为本机用户提供简便、有效地使用网络资源的手段,又要为网络用户使用本机资源提供服务。为此,网络操作系统除了具备一般操作系统应具有的功能模块之外,还要增加网络功能模块,主要应具有网络通信、网络资源管理、网络服务、.网络管理、互操作能力等。

一个分布式系统就是通过网络连接的若干计算机的集合。这些计算机都有自己的局部存贮器和外部设备。它们既可以独立工作(自治性),亦可合作工作。在这个系统中各计算机可以并行操作且有多个控制中心,即具有并行处理和分布控制的功能。分布式系统是一个一体化的系统,在整个系统中有一个全局的操作系统称为分布式操作系统,它负责全系统的资源分配和调度、任务划分、信息传输、控制协调等工作,并为用户提供一个统一的界面、标准的接口。用户通过这一界面实现所需的操作和使用系统资源。至于操作定在哪一台计算机上执行或使用哪台计算机的资源则是系统的事,用户是不用知道的,也就是说系统对用户是透明的。

习题二

  • 解释程序的顺序执行和并发执行。

程序是指令的有序集合,是一个在时间上按严格次序前后相继的操作序列,仅当前一操作执行完后,才能执行后继操作。程序体现了编程人员要求计算机完成的功能所应该采取的顺序步骤。程序的顺序执行具有顺序性、封闭性、可再现性特点,其执行结果与它的执行速度无关(即与时间无关),而只与初始条件有关。只要给定相同的输入条件,程序重复执行一定会得到相同的结果。

并发执行是为了增强计算机系统的处理能力和提高资源利用率所采取的一种同时操作技术。程序的并发执行是一组在逻辑上互相独立的程序或程序段在执行过程中其执行时间在客观上互相重叠,即一个程序段的执行尚未结束,另一个程序段的执行已经开始的执行方式。

 

2.程序并发执行为什么会产生间断性?程序并发执行为何会失去封闭性和可再现性?

程序在并发执行时,由于它们共享资源或为完成同一项任务而相互合作,致使在并发程序之间形成了相互制约的关系。一旦使某程序暂停的因素消失,则程序便可恢复执行。简言之,相互制约将导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。

程序在并发执行时,多个程序共享系统中的各种资源,因此这些资源的状态将由多个程序来改变,致使程序的运行已失去了封闭性。这样,某程序在执行时,必然会受到其它程序的影响。例如,当处理器资源被其它程序占有时,某程序必须等待。

程序在并发执行时,由于失去了封闭性,其执行结果已与并发程序的执行速度有关,从而使程序失去了可再现性,亦即,程序经过多次执行后,虽然其执行时的环境和初始条件都相同,但得到的结果却可能各不相同。

 

3.何谓进程?它有哪些基本状态?列举使进程状态发生变化的事件。

进程是可并发执行的程序在一个数据集上的一次执行过程,它是系统进行资源分配的基本单位。进程有就绪、执行、等待三个基本状态。

例如,处于就绪状态的进程,当进程调度程序为之分配了处理器后,该进程便由就绪状态转换为执行状态。正在执行的进程因访问I/O设备而无法继续执行时,就释放处理器转换为等待状态。因访问I/O设备正在等待的进程在访问I/O设备结束后,就由等待状态转换为就绪状态。正在执行的进程,如因时间片用完而被暂停执行,该进程便由执行状态转变为就绪状态。

 

4.试比较进程和程序的区别。

程序是指令的有序集合,是一个在时间上按严格次序前后相继的操作序列,仅当前一操作执行完后,才能执行后继操作,它是一个静态的概念

进程是可并发执行的程序在一个数据集上的一次执行过程,它是系统进行资源分配的基本单位。进程和程序是两个截然不同的概念。进程具有以下五个基本特征:

(1)动态性

进程既然是进程实体的执行过程,因此,动态性是进程最基本的特性。其表现为:“它由创建而产生,由调度而执行,因得不到资源而暂停执行,以及由撤销而消亡”。可见,进程有一定的生命期。而程序只是一组有序指令的集合,并存放在某种介质上,本身并无运动的含义,因此,程序是个静态实体。

(2)并发性

并发性是指多个进程实体,同存于主存中,能在一段时间内同时运行。并发性是进程的重要特征,同时也成为操作系统的重要特征。引入进程的目的也正是为了使其程序能和其它进程的程序并发执行,而程序是不能并发执行的。

(3)独立性

独立性是指进程实体是一个能独立运行的基本单位,同时也是系统中独立获得资源和独立调度的基本单位。凡未建立进程的程序,都不能作为一个独立的单位参加运行。进程与程序并非是一一对应的,一个程序运行在不同的数据集上就构成不同的进程。

(4)异步性

这是指进程按各自独立的、不可预知的速度向前推进;或者说,进程按异步方式运行。正是这一特征,将导致程序执行的不可再现性。因此,在操作系统中必须采取某种措施来保证各程序之间能协调运行。

(5)结构特征

从结构上看,进程实体是由程序段、数据段及进程控制块三部分组成,有人把这三部分统称为“进程映像”。

 

5.试说明PCB的作用?为什么说PCB是进程存在的唯一标志?

每一个进程都有一个也只有一个进程控制块(Process Control Block,简称 PCB),进程控制块是操作系统用于记录和刻画进程状态及有关信息的数据结构,也是操作系统控制和管理进程的主要依据,它包括了进程执行时的情况,以及进程让出处理器后所处的状态、断点等信息。进程控制块的作用,是使一个在多道程序环境下不能独立运行的程序(含数据),成为一个能独立运行的基本单位,一个能与其它进程并发执行的进程。

在进程的整个生命周期中,系统总是通过其PCB对进程进行控制和管理的,亦即,系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的,所以说,PCB是进程存在的唯一标志。

 

6.在进行进程切换时,所要保存的处理器状态信息主要有哪些?

当进程由于某种原因让出处理器时,把与处理器有关的各种现场信息保留下来,以便该进程在重新获得处理器后能把保留的现场信息重新置入处理器的相关寄存器中继续执行。通常被保留的现场信息有通用寄存器内容、控制寄存器内容以及程序状态字寄存器内容等。

 

7.试说明引起进程创建的主要事件。

进程控制的基本功能之一是能创建各种新的进程,这些新进程是一个与现有进程不同的实体。例如,在系统生成时,要创建一些必需的、承担系统资源分配和管理工作的系统进程;对于用户作业,每当调入系统时,由操作系统的作业调度程序为它创建相应的进程;在层次结构的系统中,允许一个进程创建一些新进程,以完成一些可以并行的工作。

 

8.试说明引起进程撤销的主要事件。

进程控制的基本功能之一是能撤销进程。一个进程可能因为它完成了所指派的工作而正常终止需撤销,或由于一个错误而非正常终止需撤销;一个进程也可能由于其祖先进程的要求被终止需撤销。当一个进程要撤销其它进程时可采用不同的方式,既可撤销具有指定标识符的进程,又可撤销一个优先级中的所有进程。当一个进程被撤销时,它必须从系统队列中移出,释放并归还所有系统资源,同时还要审查该进程是否有子孙进程,若有的话一起予以撤销。

 

9.试说明引起进程阻塞或唤醒的主要事件是什么?

有了创建原语和撤销原语,虽然进程可以从无到有、从存在到消亡而变化,但还不能完成进程各种状态之间的转换。例如,由“执行”转换为“等待”,由“等待”转换为“就绪”,需要通过使用“阻塞原语”和“唤醒原语”来实现。

(1)进程阻塞

当一个进程在执行过程中出现等待事件时,该进程调用阻塞原语将自己阻塞。即由于进程正处于执行状态,故应中断处理器,把CPU现场送至该进程的现场保护区,置该进程的状态为“等待”,并插入到相应的等待队列中,然后转进程调度程序,另选一个进程投入运行。

(2)进程唤醒

进程由执行转换为等待状态是由于进程发生了等待事件,所以处于等待状态的进程是绝对不可能唤醒自己。比如,某进程正在等待输入输出操作完成或等待别的进程发消息给它,只有当该进程所期待的事件出现时,才由“发现者”进程用唤醒原语叫醒它。一般说来,发现者进程和被唤醒进程是合作的并发进程。

 

10.在创建一个进程时,需完成的主要工作是什么?

在创建一个进程时,需完成的主要工作是给定一个指定进程标识符,形成该进程的PCB并放入系统队列中。所以,调用者必须提供形成PCB的有关参数,以便在创建时填入。对于较复杂的PCB结构,还需提供资源清单等。

 

11.在撤销一个进程时,需完成的主要工作是什么?

在撤销一个进程时,需完成的主要工作是必须把该进程的PCB从系统队列中移出,释放并归还所有系统资源,同时还要审查该进程是否有子孙进程,若有的话一起予以撤销。

 

12.在单处理器的计算机系统中,采用多道程序设计技术后,处于执行状态的进程可以有几个?为什么?

在单处理器的计算机系统中,采用多道程序设计技术后,处于执行状态的进程只能有一个?因为在单处理器的计算机系统中,CPU只有一个,每时刻占有CPU的进程只有一个,故处于执行状态的进程只能有一个。

 

13.进程调度的功能有哪些?

(1)记录系统中所有进程的执行情况

作为进程调度的准备,进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的进程控制块中。并且,根据各进程的状态特征和资源需求等,进程管理模块还将各进程的进程控制块排成相应的队列并进行动态队列转换。进程调度模块通过进程控制块的变化来掌握系统中存在的所有进程的执行情况和状态特征,并在适当的时机从就绪队列中选择出一个进程占有处理器。

(2)选择占有处理器的进程

进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程,使其获得处理器执行。根据不同的系统设计目的,有各种各样的选择策略,这些选择策略决定了调度算法的性能。

(3)把处理器分配给进程,即进行进程上下文切换

把选中进程的进程控制块内有关现场的信息如程序状态字、通用寄存器等内容送入处理器相应的寄存器,从而让它占用处理器运行。当进行上下文切换时,系统要首先检查是否允许做上下文切换(在有些情况下,上下文切换是不允许的,例如系统正在执行某个不允许中断的原语时)。然后,系统要保留有关被切换进程的足够信息,便于以后切换回该进程时,顺利恢复该进程的执行。在系统保留了CPU现场之后,调度程序选择一个新的处于就绪状态的进程,并装配该进程的信息,使CPU的控制权掌握在被选中进程手中。

(4)收回处理器

将处理器有关寄存器内容送入该进程的进程控制块内的相应单元,从而使进程让出处理器。

 

14.进程调度的时机有哪几种?

(1)正在执行的进程执行完毕。这时,如果不选择新的就绪进程执行,将浪费处理器资源。

(2)执行中的进程自己调用阻塞原语将自己阻塞起来进入等待状态。

(3)执行中的进程调用了P原语操作,从而因资源不足而被阻塞;或调用了V原语操作激活了等待资源的进程队列。

(4)执行中的进程提出I/O请求后被阻塞。

(5)在分时系统中时间片已经用完。

(6)在执行完系统调用等系统程序后返回用户进程时,这时可看作系统进程执行完毕,从而可调度选择一新的用户进程执行。

(7)在可剥夺CPU执行方式时,当就绪队列中某进程的优先级变得高于当前执行进程的优先级时,也将引发进程调度。

 

15.有5个进程P1,P2,P3,P4,P5,它们同时依次进入就绪队列,它们的优先数和需要的处理器时间如下表所示。

进程 处理器时间 优先数
P1

P2

P3

P4

P5

10

1

2

1

5

3

1

3

4

2

忽略进程调度等所花费的时间,请回答下列问题:

(1)写出分别采用“先来先服务”和“非抢占式的优先数”调度算法时选中进程执行的次序。

(2)分别计算出在两种算法下各进程在就绪队列中的等待时间以及平均等待时间。

 

解:(1)采用“先来先服务”调度算法时,其调度顺序是P1,P2,P3,P4,P5; 进程P1的等待时间是0; 进程P2的等待时间是10; 进程P3的等待时间是11; 进程P4的等待时间是13; 进程P5的等待时间是14; 平均等待时间为(0+10+11+13+14)/5=9.6

(2) 采用“非抢占式的优先数”调度算法时,其调度顺序是P4,P1,P3,P5,P2; 进程P4的等待时间是0; 进程P1的等待时间是1; 进程P3的等待时间是11; 进程P5的等待时间是13; 进程P2的等待时间是18; 平均等待时间为(0+1+11+13+18)/5=8.6

 

 

16.假定一个处理器正执行两道作业,一道以计算为主,另一道以输入输出为主,你将怎样赋予它们占有处理器的优先级?为什么?

假定一个处理器正执行两道作业,一道以计算为主,另一道以输入输出为主,将赋予它们以输入输出为主的作业更高的优先级。因为根据优先数调度算法,可先调度以输入输出为主的作业先运行,而以输入输出为主的作业只占用很少的CPU时间,主要是占用I/O设备工作,故CPU就有空闲时间,随后即可调度以计算为主的作业运行。这样,以计算为主的作业和以输入输出为主的作业就可并发执行,可以提高系统资源利用率。

 

17.设计一个实现按优先数进行处理器调度的方案,画出它的工作流程。

 

18.何谓线程?为什么要引入线程的的概念?

线程(Thread)是进程中的一个实体,是可独立参与调度的基本单位。一个进程可以有一个或多个线程,它们共享所属进程所拥有的资源。

进程是实现系统并发运行的一种实体。创建进程时需要申请必要的系统资源,在运行过程中,根据需要还将申请更多资源。当然,其间也会释放已经使用完毕的资源。当进程获得处理器资源时,称为进程调度。可见,进程既是资源申请及拥有的实体,同时也是调度的实体。另一方面,系统因为创建进程、调度进程、管理进程等将付出很大的额外开销。为了保持系统的并发性,同时降低系统为此付出的额外开销,现代操作系统将传统意义的进程进行分离,即将资源申请与调度执行分开,进程作为资源的申请与拥有单位,线程作为调度的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器、一组寄存器和栈),但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和另一个线程;同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约,致使线程在运行中也呈现出间断性。相应地,线程也同样有就绪、等待和执行三种基本状态,有的系统中线程还有终止状态等。

 

19.试比较进程和线程的区别。

进程是可并发执行的程序在一个数据集上的一次执行过程,它是系统进行资源分配的基本单位。而线程是进程中的一个实体,是可独立参与调度的基本单位。一个进程可以有一个或多个线程,它们共享所属进程所拥有的资源。我们从以下几个方面来比较线程与进程:

  • 拥有资源方面

不管是在以进程为基本单位的操作系统,还是在引入线程的操作系统中,进程都是独立拥有资源的一个基本单位。它可以申请并拥有自己的资源,也可以访问其所属进程的资源。而线程只拥有一点在运行中必要的资源,如程序计数器、寄存器和栈。当然,它可以访问其所属进程的资源(注意:资源仍然是分给进程的)。

(2)调度方面

在引入线程的操作系统中,进程作为独立拥有资源的基本单位,而线程是独立参与调度的基本单位。这样,引入线程的操作系统中存在着两级调度:同一进程内线程之间的调度、不同进程之间的调度(由分属于不同进程的线程之间的调度引起)。同一个进程内的线程切换不会引起进程切换;而在由一个进程内的线程切换到另一进程内的线程时,将引起进程切换。

(3)并发性方面

在引入线程的操作系统中,不仅不同进程的线程之间可以并发执行,而且在同一个进程的多个线程间亦可并发执行,因而使系统具有更好的并发性。

(4)系统开销方面

相比于没有引入线程的操作系统,引入线程的系统其系统开销将显著降低。例如,在创建或撤销线程时,系统只需分配与回收很少的资源,而无须像进程创建或撤销那样,花费开销来分配或回收如内存空间、I/O设备等资源;又如,在线程切换时,只需保存和设置少量的寄存器的内容,而无须像进程切换那样,花费开销来保存和设置很多的现场信息。另外,同一个进程内线程之间的通信由于共享所属进程的存储空间,因此也比进程通信更加容易。

 

20.线程有哪些属性?

线程具有如下属性:

(1)多个线程可以并发执行。

(2)一个线程可以创建另一个线程。

(3)线程具有动态性。一个线程被创建后便开始了它的生命周期,可能处于不同的状态,直至衰亡。

(4)每个线程同样有自己的数据结构即线程控制块(Thread Controlling Block, TCB),其中记录了该线程的标识符、线程执行时的寄存器和栈等现场状态信息。

(5)在同一进程内,各线程共享同一地址空间(即所属进程的存储空间)。

(6)一进程中的线程在另一进程中是不可见的。

(7)同一进程内的线程间的通信主要是基于全局变量进行的。

 

21.试说明线程的分类。

多线程的实现分为三类:用户级线程ULT);内核级线程(KLT);混合式线程方式。

(1)内核级线程

内核级线程是指线程的管理工作由内核完成,由内核所提供的线程API来使用线程,

当任务提交给操作系统执行时,内核为其创建进程和一个基线程,线程在执行过程中可通过内核的创建线程原语来创建其他线程,应用程序的所有线程均在一个进程中获得支持。内核需要为进程及进程中的单个线程维护现场信息,所以,应在内核空间中建立和维护进程控制块PCB及线程控制块TCB,内核的调度在线程的基本上进行。

(2)用户级线程

用户级线程是指线程的管理由应用程序完成,在用户空间中实现,内核无须感知线程的存在。用户级多线程由用户空间中的线程库来完成,应用程序通过线程库进行设计,再与线程库连接、运行以实现多线程。线程库是由用户级线程管理的例行程序包,在这种情况下,线程库是线程运行的支撑环境。

(3)混合式线程

某些操作系统既支持用户级线程,又支持内核级线程,Solaris便是一个例子。线程的实现分为两个层次:用户层和内核层。用户层线程在用户线程库中实现;内核层线程在操作系统内核中实现,处于两个层次的线程分别称为用户级线程和内核级线程。在混合式线程系统中,内核必须支持内核级多线程的建立、调度和管理,同时也允许应用程序建立、调度和管理用户级线程。

 

22.什么叫与时间有关的错误?与时间有关的错误表现在哪些方面?请举例说明之。

进程按异步方式执行,对于有交往的并发进程来说,可能有若干并发进程同时使用共享资源,即一个进程一次使用未结束,另一进程已开始使用,形成交替使用共享资源的现象。如果对这种情况不加控制的话,就可能出现与时间有关的错误,在共享资源(变量)时就会出错,就会得到不正确的结果。与时间有关的错误主要表现在进程的互斥和进程的同步。

 

23.什么是临界区?试举一临界区的例子。

有交往的并发进程执行时出现与时间有关的错误,其根本原因是对共享资源(变量)的使用不加限制,当进程交叉使用了共享资源(变量)就可能造成了错误。为了使并发进程能正确地执行,必须对共享变量的使用加以限制。我们把并发进程中与共享资源(变量)有关的程序段称为“临界区”。共享资源在(变量)所代表的资源称为“临界资源”。多个并发进程中涉及相同共享资源(变量)的那些程序段称为“相关临界区”

 

24.什么是进程的互斥?什么是进程的同步?

进程的互斥是指当有若干进程都要使用某一共享资源时,任何时刻最多只允许一个进程去使用,其他要使用该资源的进程必须等待,直到占用资源者释放该资源。

进程的同步是指并发进程之间存在一种制约关系,一个进程的执行依赖另一个进程的消息,当一个进程没有得到另一个进程的消息时应等待,直到消息到达时才被唤醒。

 

25.若信号量s表示一种资源,则对s作PV操作的直观含义是什么?

若信号量s表示一种资源,则对s作PV操作的直观含义是,P(s)表示申请一个s资源,V(s)表示释放一个s资源。

26.在信号量s上作PV操作时,s的值发生变化,当s>0,s=0,s<0时,它们的物理意义是什么?

在信号量s上作PV操作时,s的值发生变化,当s>0时表示还有|s|个可用资源;当s=0时表示已无可用资源;当s<0时表示不但无可用资源,且还有|s|个进程在等待使用资源。

 

27.有三个并发进程,R负责从输入设备读入信息并传送给M,M将信息加工后并传送给P,P把加工后的信息打印输出。现有:

(1)一个缓冲区;

(2)两个缓冲区;

用PV操作写出这三个进程能正确工作的程序。

解:(1)一个缓冲区

设信号量S1表示缓冲区的容量;

信号量S2表示R读入的信息数;

信号量S3表示M信息加工后的信息数;

Var S1,S2,s3: Semaphore;

S1=缓冲区容量;

S2=0;

S3=0;

Cobegin

{

R();

M();

P();

}

R( )

{  WHILE(1)

{

从输入设备读入信息X;

P(S1);

把读入信息X放入缓冲区中;

V(S2);

}

}

M( )

{  WHILE(1)

{

P(S2);

从缓冲区中取R的读入信息X;

V(S1);

信息加工得到新数据Y;

P(S1);

把新数据Y放入缓冲区中;

V(S3);

}

}

P( )

{  WHILE(1)

{

P(S3);

从缓冲区中取新数据Y;

V(S1);

把新数据Y打印输出;

}

}

 

28.用PV操作解决生产者和消费者问题。假设有一个可以存放1件产品的缓冲器;有m个生产者,每个生产者每次生产一件产品放入缓冲器中,有n个消费者,每个消费者每次从缓冲器中取出一件产品。

解:  设信号量Sp表示是否可以把产品放入缓冲器中;

信号量Sg表示缓冲器中是否存放了产品;

buffer: integer;

Sp,Sg: integer;

Sp:=1;

Sg:=0;

Cobegin

Procedure  produceri(i=1,2,3,…,m)

Begin

L1: [ produce a product ];

P(Sp);

Buffer:=product ;

V(Sg);

Goto L1 ;

End;

Procedure consumerj(j=1,2,3,…,n)

L2: P(Sg);

[take a product from buffer ];

V(Sp);

[consume];

Goto L2;

End;

 

29.系统有输入机和行式打印机各一台,有两个进程都要使用它们,采用PV操作实现请求使用和归还释放后,还会产生死锁吗?若否,说明理由;若会产生死锁则给出一种防止死锁的方法。

系统有输入机和行式打印机各一台,有两个进程都要使用它们,采用PV操作实现请求使用和归还释放后,不会产生死锁。因为系统的输入机和行式打印机作为临界资源分别用两个信号量表示,初值为1,在需要使用它们时用P操作申请,在需要归还它们时用V操作释放,这样就保证了两个进程对输入机和行式打印机的互斥使用,可防止死锁的产生。

 

30.若系统有同类资源m个,被n个进程共享,问:当m>n和m≤n时每个进程最多可以请求多少个这类资源,使系统一定不会发生死锁?

若系统有同类资源m个,被n个进程共享,当m>n时,每个进程最多可以请求(m/n向上取整)个这类资源,使系统一定不会发生死锁。当m≤n时每个进程最多可以请求1个这类资源,使系统一定不会发生死锁

 

31.在公共汽车上,司机和售票员的工作流程如下图所示。为保证乘客的安全,司机和售票员应密切配合协调工作。请用PV操作来实现司机与售票员之间的同步。

 

解:设 S1是否可以启动汽车;

S2是否可以开车门;

Var S1,S2: Semaphore;

S1=0;

S2=1;

Cobegin

{

Driver();

Busman();

}

Driver()

{  while(1)

{

P(S1);

启动车辆;

正常行车;

到站停车;

V(S2);

}

};

busman()

{  while(1)

{

售票;

P(S2);

开车门;;

关车门;

V(S1)

}

};

 

 

32.如下图所示的进程流程图中,有六个进程合作完成某一任务,试说明这六个进程之间的同步关系,并用PV操作实现之。

 

 

 

 

 

 

 

 

 

解:设信号量S2,S3,S4,S5,S6分别表示进程P2,P3,P4,P5,P6是否能执行。

S2,S3,S4,S5,S6:integer;

S2:=0;

S3:=0;

S4:=0;

S5:=0;

S6:=0;

Cobegin

Procedure  P1;

Begin

……

V(S2);

V(S3);

V(S4);

End;

Procedure  P2;

Begin

P(S2);

……

V(S6);

End;

Procedure  P3;

Begin

P(S3);

……

V(S5);

End;

Procedure  P4;

Begin

P(S4);

……

V(S6);

End;

Procedure  P5;

Begin

P(S5);

……

V(S6);

End;

Procedure  P6;

Begin

P(S6);

P(S6);

P(S6;

……

End;

Coend

 

33.何谓管程?管程的的特性有哪些?

管程是关于共享资源的数据及在其上的操作的一组过程或共享数据结构及其规定的所有操作。管程的引入可以让我们按资源管理的观点,将共享资源和一般资源的管理区分开来,使进程同步机制的操作相对集中。采用这种方法,对共享资源的管理可借助数据结构及其上所实施操作的若干进程来进行;对共享资源的申请和释放通过进程在数据结构上的操作来实现。

管程具有如下几个主要的特性:

(1)模块化:一个管程是一个基本程序单位,可以单独编译。

(2)抽象数据类型:管程是一种特殊的数据类型,其中不仅有数据,而且有对数据进行操作的代码(即过程)。

(3)安全性:管程内的数据和过程都局限于管程本身。管程内的数据只能被管程内的过程所访问,管程内的过程也只能访问管程内的数据,管程内部的实现在其外部是不可见的。

(4)互斥性:在任一时刻,共享资源的进程可以访问管程中的管理此资源的过程,但最多只有一个调用者能够真正地进入管程,其他调用者必须等待直至管程可用。管程的互斥操作通常由编译程序支持。

 

34.试说明管程与PV操作的区别。

信号量机制为实现进程的同步与互斥提供了一种原始、功能强大且灵活的工具,然而在使用信号量和PV操作实现进程同步时,对共享资源的管理分散于各个进程中,进程能够直接对共享变量进行处理,不利于系统对临界资源的管理,难以防止进程有意或无意的违法同步操作,容易造成程序设计错误。

管程是关于共享资源的数据及在其上的操作的一组过程或共享数据结构及其规定的所有操作。管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块,它提供一种互斥机制,进程可互斥地调用这些过程。管程把分散在各个进程中互斥地访问公共变量的那些临界区集中在一起,提供对它们的保护。由于共享变量每次只能被一个进程所访问,把代表共享资源状态的共享变量放置在管程中,那么,管程就可以控制共享资源的使用。管程可作为程序设计语言的一个成分,采用管程作为同步机制便于用高级语言来编写程序,也便于程序正确性验证。

 

35.桌子上有一只盘子,每次只能放一只水果,爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,一个儿子专等吃盘子里的橘子,一个女儿专等吃盘子里的苹果。写出能使爸爸、妈妈、儿子、女儿正确同步工作的管程。

解:Type FMSD=monitor     //管程定义

var plate:(apple,orange,null);

Count:interge;

Sp,ss,sd:condition;

Procedure put( var fruit:(apple,orange))   //放水果

{  if (count=1) then sp.wait

else

{plate=fruit;

Count=count+1;

};

If (fruit=apple) then ss.signal

Else sd.signal;

};

Procedure get( var fruit:(apple,orange), x:plate)  //取水果

{  if (count=0) or plate<>fruit then

{if (fruit=apple) then ss.wait else sd.wait}

else

{ Count=count-1;

X=plate;

};

Sp.signal;

};

{ count=0;    //赋初值

Plate=null;

}

 

 

Procedure father()  //父亲

While(1)

{ 准备苹果;

FMSD.put(apple);

}

};

Procedure mother()  //母亲

While(1)

{ 准备桔子;

FMSD.put(orange);

}

};

Procedure son()  //儿子

While(1)

{ FMSD.get(orange, y);

吃桔子;

}

};

Procedure daughe()  //女儿

While(1)

{ FMSD.get(apple, y);

吃苹果;

}

};

 

36.何谓进程通信?通信机制中应设置哪些基本通信原语?

在计算机系统中,进程之间要交换大量的信息,这种大量信息的传递要有专门的通信机制来实现。我们把通过专门的通信机制实现进程间交换大量信息的通信方式称为“进程通信”。

进程通信分为直接通信和间接通信。可用send原语和receive原语来实现进程之间的通信。

 

37.简述两种通信方式。

进程通信分为直接通信和间接通信。直接通信是指发送进程利用操作系统所提供的发送命令直接把消息发送给接收进程,而接收进程则利用接收命令直接从发送进程接收消息。

采用间接通信方式时,进程间发送或接收消息通过一个共享的数据结构——信箱来进行,消息可以被理解成信件,每个信箱有一个唯一的标识符。当两个以上的进程有一个共享的信箱时,它们就能进行间接通信。

 

38.何谓死锁?产生死锁的原因和必要条件是什么?

若系统中存在一组进程(两个或多个进程),它们中的每一个进程都占用了某种资源而又都在等待其中另一进程所占用的资源,这种等待永远不能结束,则说系统出现了“死锁”,或说这组进程处于“死锁”状态。

产生死锁的原因可归结为两点:

(1)竞争资源。当系统中供多个进程所共享的资源,不足以同时满足它们的需要时,引起它们对资源的竞争而产生死锁。

(2)进程推进顺序非法。进程在运行过程中,请求和释放资源的顺序不当,导致了进程死锁。

系统产生死锁必定同时保持以下四个必要条件:

(1)互斥条件:进程应互斥使用资源,任一时刻一个资源仅为一个进程独占,若另一个进程请求一个已被占用的资源时,它被置成等待状态,直到占用者释放资源。

(2)占有且等待条件:一个进程请求资源得不到满足而等待时,不释放已占有的资源。

(3)不剥夺条件:任一进程不能从另一进程那里抢夺资源,即已被占用的资源,只能由占用进程自己来释放。

(4)循环等待条件:存在一个循环等待链,其中,每一个进程分别等待另一个进程所持有的资源,造成永远等待。

 

39.简述银行家算法的工作过程。

我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。这样做,能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行到结束,执行结束后归还的资源加入到系统的剩余资源中,这些资源又至少可以满足一个进程的最大需求。于是,保证了所有进程都能在有限的时间内得到需要的全部资源。可见银行家算法是通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的,在能确保系统处于安全状态时才能把资源分配给申请者,从而避免系统发生死锁。

 

40.请叙述预防死锁的方法。

很显然,只要破坏四个必要条件中的其中一个就可预防死锁的发生。破坏第一个条件(互斥条件)和破坏第三个条件(不剥夺条件)不能对所有资源可行,因此可破坏第二个条件(占有且等待条件)和第四个条件(循环等待条件)。

(1)静态分配策略

所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源,并且直到它所要的资源都得到满足后才开始执行。无疑所有并发执行的进程要求的资源总数不超过系统拥有的资源数。采用静态分配后,进程在执行中不再申请资源,因而不会出现占有了某些资源再等待另一些资源的情况,即破坏了第二个条件(占有且等待条件)。

(2)层次分配策略

层次分配策略将阻止第四个条件(循环等待条件)的出现。在层次分配策略下,资源被分成多个层次,一个进程得到某一层的一个资源后,它只能再申请较高一层的资源;当一个进程要释放某层的一个资源时,必须先释放所占用的较高层的资源;当一个进程获得了某一层的一个资源后,它想再申请该层中的另一个资源,必须先释放该层中的已占用资源。

 

 

习题三

  1. 解释作业和作业步。

答:把用户在一次解题过程中要求计算机所做工作的集合称为一个作业。

 

任何一个作业都要经过若干加工步骤才能得到结果,我们把作业的每一个加工步骤称为一个“作业步”。

 

  1. 计算机上运行一个用户作业通常要经过哪几个作业步?

答:在计算机上运行用户作业时,通常要经历以下4步:

(1)编辑,即采用某种高级语言按一定算法编写源程序,将源程序通过某种手段(如键盘输入)送入计算机内;

(2)编译,即调用上述高级语言的编译程序,对源程序进行编译,产生目标代码程序;

(3)连接装配,即将目标代码及调用的各种库代码连接装配成一个可执行程序;

(4)运行,即将可执行程序装入内存并提供程序运行时所需数据,然后运行程序并产生运行结果。

 

  1. 操作系统提供哪些手段控制和管理作业?

答:作业控制方式有两种,即批处理控制方式和交互式控制方式。其中:

采用批处理控制方式控制作业执行时,用户使用操作系统提供的“作业控制语言”对作业执行的控制意图编写成一份“作业控制说明书”,连同该作业的源程序和初始数据一同提交给计算机系统,操作系统将按照用户说明的控制意图来控制作业的执行。

采用交互式控制方式控制作业执行时,用户使用操作系统提供的“操作控制命令”来表达对作业执行的控制意图。

 

  1. 用户交付计算机运行的作业有哪几种?

答:用户交付计算机运行的作业有两种,即:

采用批处理控制方式的作业称为“批处理作业”,又称“脱机作业”。

采用交互式控制方式的作业称为“交互式作业”,又称“联机作业”,对于来自终端的作业也称为“终端作业”。

 

  1. 作业管理功能包括哪几个部分?

答:根据作业进入系统的过程,可将作业管理功能分成三部分:

(1) 作业输入:把作业装入辅存输入井中,并按照进入输入井的先后顺序形成后备作业队列的过程。

(2) 作业调度:按某种调度策略选择后备作业队列中的若干作业装入主存运行的过程。

(3) 作业控制:在操作系统控制下,用户如何组织他的作业并控制作业进入处理器运行的过程。

 

  1. 什么是JCL和JCB,分别列举它们的主要内容和作用。

答:JCL全称Job Control Language,即作业控制语言,是由若干作业控制语句组成的集合,每个控制语句除包含了表示特征的关键字外,还有指示控制要求的若干参数,大都提供以下主要功能:

(1)作业的提交。

(2)控制作业和作业步的执行。

(3)各种软硬件资源的使用。

JCB全称Job Control Block,即作业控制块,是批处理作业在系统中存在的标志,其中存有系统对于作业进行管理所需要的全部信息,它们被保存于辅存存储区域中。作业控制块中所包含的信息数量及内容因系统而异,但一般应包含:

作业名、作业状态、作业类别、作业优先数、作业控制方式、资源需求量、进入系统时间、开始运行时间、运行时间、作业完成时间和所需主存地址及外设种类及台数等。

 

  1. 什么是作业调度程序?简述作业调度程序的主要功能。

答:完成作业调度功能的控制程序称作业调度程序。作业调度程序的主要功能包括:

(1)按照某种调度算法从后备作业队列中选取作业。

(2)为被选中的作业分配必要的主存和外设资源。因此作业调度程序在挑选作业过程中要调用存储管理程序和设备管理程序中的某些功能。

(3)为选中的作业开始运行做好一切准备工作。这种准备工作包括:修改作业状态为运行态,为运行作业创建进程,构造和填写作业运行时所需要的有关表格,如作业表等。

(4)在作业运行完成或由于某种原因需要撤离系统时,作业调度程序还要完成作业的善后处理工作。包括回收分给它的全部资源,为输出必要信息编制输出文件,撤销该作业的全部进程和作业控制块等,最终将其从现有作业队列中删除。

 

  1. 作业的状态分成哪几种?简述各种状态之间是如何转换的。

答:通常作业的状态分成四种,即提交状态、后备状态、运行状态和完成状态;具体转换过程如下:

(1)提交状态:一个作业在其处于用户手中并经过输入设备进入到外存输入井 ,系统为其建立作业控制块。这时的作业处于提交状态。

(2)后备状态:对于已经进入输入井的作业,系统将它插入到输入井后备队列中,等待作业调度程序的调度运行。这时的作业从提交状态进入后备状态。

(3)运行状态:一个处于后备状态的作业,一旦被作业调度程序选中装入主存,系统就为它分配必要的软硬件资源,然后建立相应的进程并插入到进程就绪队列中。这时的作业从后备状态进入运行状态。

(4)完成状态:作业完成其全部运行过程并释放其所占全部资源而正常结束或异常终止时,作业从运行状态进入完成状态。

 

  1. 什么是作业调度?影响作业调度的主要因素有哪些?

答:从“输入井”中选择若干作业装入主存并进入处理器运行的过程称作业调度。影响作业调度的主要因素有:公平性、均衡使用资源、提高系统吞吐量和平衡系统和用户需求四个方面。

 

  1. 试叙述作业,进程和程序三者的关系。

答:执行作业调度之前的作业是静态的,基本上是以文件形式存储在外部存储介质中的,当该作业经过作业调度的高级阶段调度后,其状态即从静态转变为动态执行状态,并为此创建了相应的作业进程,进程在经过若干次状态变更后即可完成作业功能并结束运行撤消。程序作为作业的主体部分,也是以文件静止存在于外部存储介质中,当该程序被执行时,即转变为执行状态。

 

  1. 简述作业调度包括的主要性能指标。

答:对于批处理系统而言,作业调度的性能优劣受多项指标影响,主要的性能指标体现在:CPU利用率高低、吞吐能力强弱、周转时间长短、平均周转时间长短和平均带权周转时间大小。

 

  1. 批处理作业调度要经历哪几个阶段?

答:在多道程序系统中,一个作业被提交后,必须经过处理器调度才能获得处理器并运行。对于批处理作业而言,通常至少要经历作业调度和进程调度两个阶段后,才能获得处理器运行。

 

  1. 简述作业调度与进程调度的关系。

答:作业调度是批处理作业运行的前提,称高级调度;进程调度是作业调度的后续,称低级调度。由于作业调度往往发生在一个批处理作业执行完毕,另一个需要调入主存时,因此作业调度周期较长且速度慢、花费时间长;而进程调度频率快、速度快且花费时间短。

 

  1. 简述批处理作业三级调度层次关系。

答:当高级调度发生在作业装入时,作业的状态由后备状态变更为执行状态,该调度过程决定一个进程能否被创建,或者是创建后能否被置成就绪状态,以参与竞争处理器资源获得运行,或者当高级调度发生在进程终止运行时,作业的状态由执行状态变更为完成状态,并对该作业进行一系列善后处理,然后退出系统;正常中级调度反映到进程状态上就是挂起和解除挂起,它根据系统的当前负荷情况决定停留在主存中的进程数;低级调度则是决定哪一个就绪进程占有CPU运行

 

  1. 批处理作业调度有哪几种调度算法?

答:批处理作业调度有以下五种调度算法:先来先服务FCFS、短作业优先SJF、响应比最高者优先算法HRRF、优先数调度算法和分类调度算法等。

 

  1. 试比较先来先服务、短作业优先和响应比最高者优先三种算法的各自特点。

答:先来先服务FCFS算法是一种非剥夺式调度算法,容易实现,体现了公平,但效率不高,只顾及到作业等候时间,而没考虑作业要求服务时间的长短,不利于短作业而优待了长作业。

短作业优先SJF调度算法强调了资源的充分利用,有效地降低了作业的平均等待时间,使得单位时间内处理作业的个数最大,保证了作业吞吐量最大,但对作业运行时间预先作出估算难,且完全未考虑作业的紧迫程度和等待时间,因此对于长作业极为不利。

响应比最高者优先算法HRRF是介乎这两种算法之间的一种折衷的策略,既考虑作业等待时间,又考虑作业的运行时间。这样既照顾了短作业又不使长作业的等待时间过长,改进了调度性能,缺点是每次计算各道作业的响应比会有一定的时间开销,需要估计期待的服务时间,性能要比SJF略差。

 

  1. 在单道批处理系统中,有四个作业到达输入井和需要的计算时间如表所示,现分别采用先来先服务调度算法、最短作业优先算法和响应比最高者优先算法,忽略作业调度所花的时间。当第一个作业进入系统后就可开始调度。
作业 入井时间 计算时间 开始时间 完成时间 周转时间 带权周转时间
JOB1 8︰00 2小时 8︰00 10:00 120分 1
JOB2 8︰30 30分钟 10:00 10:30 120分 4
JOB3 9︰00 6分钟 10:30 10:36 96分 16
JOB4 9︰30 12分钟 10:36 10:48 78分 6.5

(1)填充表中空白处

(2)四个作业的执行次序为__________________。

(3)四个作业的平均周转时间和带权平均周转时间为__________________。

对于先来先服务调度算法,填充表如上,从表中可以看出作业的执行次序为:1,2,3,4;平均周转时间为103.5,带权平均周转时间为6.875

对于最短作业优先算法,填充表略,作业的执行次序为:1, 3,4,2;平均周转时间为93,带权平均周转时间为5.15

对于响应比最高者优先算法,填充表略,作业的执行次序为:1, 3,2,4;平均周转时间为97.5,带权平均周转时间为5.675

 

  1. 单道批处理系统中,下列三个作业采用先来先服务调度算法、最短作业优先算法和最高响应比优先算法进行调度,哪一种算法性能较好?请完成下表:
作业 提交时间 计算时间 开始

时间

完成

时间

周转

时间

带权周

转时间

JOB1

JOB2

JOB3

10∶00

10∶10

10∶25

2∶00

1∶00

0∶25

10:00

12:00

13:00

12:00

13:00

13:25

120分

170分

180分

 1

2.83

7.2

平均作业周转时间T=156.7

作业平均带权周转时间W=3.68

答:先来先服务调度算法执行表如上所示,最短作业优先算法作业执行次序为1,3,2,其平均作业周转时间为145分钟,平均带权周转时间为3.02;最高响应比优先算法作业执行次序为1,3,2,其平均作业周转时间为145分钟,平均带权周转时间为3.02;

由此可知:最短作业优先算法性能较好。

 

  1. 有一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法,如下表所示的作业序列,作业优先数即为进程优先数,优先数越小优先级越小。

 

 

 

 

 

 

 

 

(1)列出所有作业进入系统时间及结束时间。

(2)计算平均周转时间和带权平均周转时间。

答:所有作业执行情况表如下所示:

作业次序 进入时间 运行时间 作业调度 进程调度 结束时间 周转时间 带权周转时间
A 10:00 40分钟 10:00 10:00 10:40 40分钟 1
B 10:20 30分钟 10:20 11:50 12:20 120分钟 4
C 10:30 50分钟 11:00 11:00 11:50 80分钟 1.6
D 10:40 20分钟 10:40 10:40 11:00 20分钟 1
作业平均周转时间 T =65分钟

作业带权平均周转时间 W =1.9

280分钟 7.6

 

  1. 若某系统采用可变分区方式管理主存中的用户空间,供用户使用的最大主存空间为100K,主存分配算法为最先适应分配法,系统配有4台磁带机,一批作业如下表所示:
作业名 进入时间 运行时间 主存需求量 磁带机需求量
JOB1 10:00 40分钟 35K 3台
JOB2 10:10 30分钟 70K 1台
JOB3 10:15 20分钟 50K 3台
JOB4 10:35 10分钟 25K 2台
JOB5 10:40 5分钟 20K 2台

该系统采用多道程序设计技术,对磁带机采用静态分配,忽略设备工作时间和系统进行调度所花的时间,进程调度采用先来先服务算法。请分别给出采用“先来先服务调度算法”、“最短作业优先算法”和“响应比最高者优先算法”选中作业执行的次序以及作业的平均周转时间和带权平均周转时间。假设不允许移动已在主存中的任何作业。

答:先来先服务调度算法运行结果

作业次序 进入时间 运行时间 作业调度 进程调度 结束时间 周转时间 带权周转时间
JOB1 10:00 40分钟 10:00 10:00 10:40 40分钟 1
JOB2 10:10 30分钟 10:40 10:40 11:10 60分钟 2
JOB4 10:35 10分钟 10:40 11:10 11:20 45分钟 4.5
JOB5 10:40 5分钟 11:10 11:20 11:25 45分钟 9
JOB3 10:15 20分钟 11:25 11:25 11:45 90分钟 4.5
作业平均周转时间 T =56分钟

作业带权平均周转时间 W =4.2

280分钟 21

最短作业优先调度算法运行结果

作业次序 进入时间 运行时间 作业调度 进程调度 结束时间 周转时间 带权周转时间
JOB1 10:00 40分钟 10:00 10:00 10:40 40分钟 1
JOB5 10:40 5分钟 10:40 10:40 10:45 5分钟 1
JOB4 10:35 10分钟 10:40 10:45 10:55 20分钟 2
JOB3 10:15 20分钟 10:55 10:55 11:15 60分钟 3
JOB2 10:10 30分钟 11:15 11:15 11:45 95分钟 3.2
作业平均周转时间 T =44分钟

作业带权平均周转时间 W =2.04

220分钟 10.2

响应比最高者优先调度算法运行结果

作业次序 进入时间 运行时间 作业调度 进程调度 结束时间 周转时间 带权周转时间
JOB1 10:00 40分钟 10:00 10:00 10:40 40分钟 1
JOB3 10:15 20分钟 10:40 10:40 11:00 45分钟 2.25
JOB5 10:40 5分钟 11:00 11:00 11:05 25分钟 5
JOB4 10:35 10分钟 11:00 11:05 11:15 40分钟 4
JOB2 10:10 30分钟 11:05 11:15 11:45 95分钟 3.17
作业平均周转时间 T =49分钟

作业带权平均周转时间 W =3.08

245分钟 15.42

 

  1. 有一个多道程序设计系统,仍采用可变分区方式管理主存中的用户空间,但允许移动已在主存中的任何作业。假设用户可使用的最大主存空间为100K,主存分配算法为最先适应分配法,作业序列如下表所示:
作业名 进入时间 运行时间 主存需求量
JOB1 10:06 42分钟 55K
JOB2 10:20 30分钟 40K
JOB3 10:30 24分钟 35K
JOB4 10:36 15分钟 25K
JOB5 10:42 12分钟 20K

 

该系统采用多道程序设计技术,忽略设备工作时间和系统进行调度所花的时间,进程调度也仍采用先来先服务算法。请分别给出采用“先来先服务调度算法”、“最短作业优先算法”和“响应比最高者优先算法”选中作业执行的次序以及作业的平均周转时间和带权平均周转时间。

答:先来先服务调度算法运行结果

作业次序 进入时间 运行时间 作业调度 进程调度 结束时间 周转时间 带权周转时间
JOB1 10:06 42分钟 10:06 10:06 10:48 42分钟 1
JOB2 10:20 30分钟 10:20 10:48 11:18 58分钟 1.93
JOB3 10:30 24分钟 10:48 11:18 11:42 72分钟 3
JOB4 10:36 15分钟 10:48 11:42 11:57 81分钟 5.4
JOB5 10:42 12分钟 11:57 11:57 12:09 87分钟 7.25
作业平均周转时间 T =68分钟

作业带权平均周转时间 W =3.72

340分钟 18.58

最短作业优先调度算法运行结果

作业次序 进入时间 运行时间 作业调度 进程调度 结束时间 周转时间 带权周转时间
JOB1 10:06 42分钟 10:06 10:06 10:48 42分钟 1
JOB2 10:20 30分钟 10:20 10:48 11:18 58分钟 1.93
JOB5 10:42 12分钟 10:48 11:18 11:30 48分钟 4
JOB4 10:36 15分钟 10:48 11:30 11:45 69分钟 4.6
JOB3 10:30 24分钟 11:18 11:45 12:09 99分钟 4.13
作业平均周转时间 T =63.2分钟

作业带权平均周转时间 W =3.13

316分钟 15.66

响应比最高者优先调度算法运行结果

作业次序 进入时间 运行时间 作业调度 进程调度 结束时间 周转时间 带权周转时间
JOB1 10:06 42分钟 10:06 10:06 10:48 42分钟 1
JOB2 10:20 30分钟 10:20 10:48 11:18 58分钟 1.93
JOB4 10:36 15分钟 10:48 11:18 11:33 57分钟 3.8
JOB3 10:30 24分钟 10:48 11:33 11:57 87分钟 3.63
JOB5 10:42 12分钟 11:18 11:57 12:09 87分钟 7.25
作业平均周转时间 T =66.2分钟

作业带权平均周转时间 W =3.52

331分钟 17.61

 

  1. 操作系统向用户提供了哪几种接口?

答:操作系统向用户提供了三种接口,分别是:操作命令或作业控制语言(JCL),系统功能调用接口和图形用户接口。

 

  1. 根据作业控制方式的不同,可将命令接口又分成哪几种?

答:根据作业控制方式的不同,可将命令接口又分成联机命令接口和脱机命令接口两种。

 

  1. 简述操作系统提供的系统调用功能类型。

答:不同的操作系统提供的系统调用不完全相同,但大致都包括以下几类:文件操作类、资源申请类、控制类和信息维护类等。

 

  1. 简述系统调用执行过程包括的主要阶段。

答:系统调用执行过程可大致分成三个阶段:设置系统调用参数、系统调用命令的一般性处理和统调用命令的处理程序完成具体过程。

 

  1. 批处理作业是如何控制执行的。

答:根据作业控制说明书中的作业步控制语句中参数指定的程序,把相应的程序装到主存,然后创建一个相应的作业步进程,把它的状态设置为“就绪”。当被进程调度程序选中运行时,该进程就执行相应的程序,完成该作业步功能。当一个作业步的进程执行结束,需要向操作系统报告执行结束的信息,然后撤销该进程,再继续取下一个作业步的控制语句,控制作业继续执行。

 

  1. 终端用户的注册和退出过程各起什么作用?

答:只有注册成功的终端用户方可从终端上输入作业的程序和数据,也可使用系统提供的终端控制命令控制作业执行;用户只有通过请求退出系统,系统接收命令后就收回该用户所占的资源让其正常退出。

 

  1. 简述系统调用的主要执行过程。

答:用户编制程序使用系统调用请求操作系统服务时,编译程序将其转换成目标程序中的“访管指令”及一些参数。目标程序执行时,当CPU执行到“访管指令”,产生自愿性中断,操作系统接过控制权(在管态下),并分析“访管指令”中相关参数,让对应的“系统调用”子程序为用户服务;完成系统调用后,操作系统将CPU状态改变为目态,返回到用户程序继续执行。

 

习题四

1.什么是静态链接、装入时动态链接和运行时的动态链接?

答:静态链接是指在程序运行之前,首先将各个目标模块以及所需要的库函数链接成一个完整的装入模块,又称为可执行文件,运行时可直接将它装入主存。

装入时动态链接是指用户源程序经编译后得到的一组目标模块,在装入主存时,采用边装入边链接的方式,即在装入一个目标模块时,若需要调用另一个模块,则找出该模块,将它装入主存,并修改目标模块中的逻辑地址。

运行时动态链接是指运行时动态链接是指在程序执行过程中当需要该目标模块时,才把该模块装入主存,并进行链接。这样不仅可以加快程序装入的速度,而且可以节省大量的主存空间。

 

2.什么是重定位?为什么要引入动态重定位? 

答:在装入作业时,装入程序直接把作业装入到所分配的主存区域中,在作业执行过程中,随着每条指令或数据的访问,由硬件地址转换机制自动地将指令中的逻辑地址转换成对应的物理地址。这种地址转换的方式是在作业执行过程中动态完成的,故称为动态重定位。

采用动态重定位的系统支持程序浮动。

 

3.试设计和描述最先适应算法的主存分配和回收过程。

答:最先适应分配算法是将空闲分区的起始地址从小到大的顺序登记在空闲分区表中。最先适应分配算法在主存空间分配时,总是顺序查找空闲分区表,选择第一个满足作业地址空间要求的空闲分区进行分割,一部分分配给作业,而剩余部分仍为空闲分区,重新登记在空闲分区标的合适位置。

装入的作业执行结束后,它所占据的分区将被回收。回收空间时应检查是否存在与回收区相邻的空闲分区,如果有,则将其合并成为一个新的空闲分区进行登记管理。回收后的空闲区按起始地址的顺序插入到空闲分区表的适当位置登记在空闲区表中,用于装入新的作业。

4.在可变分区存储管理方式下,采用移动技术有什么优点?移动一道作业时操作系统需要做哪些工作?

答:当主存中各个空闲区的长度都不能满足作业的要求,而空闲区总的大小又大于作业需要的空间时,可以移动已在主存中的作业,使分散的空闲区连成一片,形成一个较大的空闲区,使主存空间得到充分利用,作业在执行过程中扩充主存空间提供方便。

移动作业时,需要进行作业信息的传送,作业移动后,作业占用的分区和空闲区的位置和长度都发生了变化,需要修改主存分配表和保存在进程控制块中的分区始址和长度,这些都增加了操作系统的工作量,也增加了操作系统占用CPU的时间。

 

5.设某系统中作业J1,J2,J3占用主存的情况如下图。今有一个长度为20k的作业J4要装入主存,当采用可变分区分配方式时,请回答:

  • J4装入前的主存已分配表和未分配表的内容。
  • 写出装入J4时的工作流程,并说明你采用什么分配算法。

 

0k OS
10k  J1
18k   
30k  J2
40k   
54k  J3
70k 

100k

 

答:( 1 )主存已分配表共有三项,由作业j1 、j2 、j3 占用,长度依次为:10k 、30k 和54k 未分配表共有三项:空闲区1 、空闲区2 和空闲区3 ,长度依次为18k 、40k 和70k 。

( 2 )作业J4 装入时,采用直接分配,搜索未分配表,空闲区1 不能满足。所以,要继续搜索未分配表,空闲区2 可以满足J4 的装入要求。

 

 

6.给定主存空闲分区,按地址从小到大为:100KB、500KB、200KB、300KB和600KB。现有用户进程依次分别为212KB、417KB、112KB和426KB:

(1)分别采用最先适应、最优适应和最坏适应算法将它们装入到主存的那个分区?

(2)哪个算法能最有效利用主存?

答:

( 1 )1)最先适应 212KB 选中分区2 ,这时分区2 还剩288KB 。417KB 选中分区5 ,这时分区5 还剩183KB 。112KB 选中分区2 ,这时分区2 还剩176KB 。426KB 无分区能满足,应该等待。

2 )最优适应 212KB 选中分区4 ,这时分区4 还剩88KB 。417KB 选中分区2 ,这时分区2 还剩83KB 。112KB 选中分区3 ,这时分区3 还剩88KB 。426KB 选中分区5 ,这时分区5 还剩174KB 。

3 ) 最坏适应 212KB 选中分区5 ,这时分区5 还剩388KB 。417KB 选中分区2 , 这时分区2 还剩83KB 。112KB 选中分区5 ,这时分区5 还剩176KB 。426KB 无分区能满足,应该等待。

( 2 )对于该作业序列,最优适应 算法能最有效利用内存

 

 

7.为什么要引入页式存储管理方法?在这种管理中硬件提供了哪些支持?

答:连续分配方式要求作业一次性、连续装入在主存空间,对空间的要求较高,而且经过若干个作业的装入与撤销后,有可能形成很多“碎片”,虽然可能通过移动技术将零散的空闲区汇集成可用的大块空间,但需要增加系统的额外开销。采用分页式存储管理方式把逻辑地址连续的作业分散存放到几个不连续的主存区域中,并能保证作业的正确执行,既可充分利用主存空间、减少主存的碎片,又可避免移动所带来的额外开销。在页式存储管理中,硬件提供页表机制、缺页中断机构以及地址变换机构等支持。

 

8.在页式存储管理中为什么要设置页表和快表?

答:在分页式存储管理系统中,允许将作业的每一页离散地存储在主存的物理块中,为了保证作业的正确运行,即能在主存中找到每个页面所对应的物理块。为此,系统为每个作业建立了一张页面映像表,简称页表。页表实现了从页号到主存块号的地址映像。

页表存放在主存中,取一个数据或指令至少需要访问主存两次以上。为了提高存取速度,通常在地址变换机构中增设一个具有并行查找能力的小容量高速缓冲寄存器,利用高速缓冲寄存器存放页表的一部分,这部分页表称为快表。快表的查找速度极快。

 

9.在页式存储管理中如何实现多个作业共享一个程序或数据?

答:页式存储管理中的共享须区分数据共享和程序共享。实现数据共享时,可允许不同的作业对共享的数据页采用不同页号,只需要将各自的有关表目指向共享的数据信息块即可。而实现程序共享时,由于页式存储结构要求逻辑地址空间是连续的,所以在程序运行前它们的页号是确定的。假设有一个共享程序EDIT,其中含有转移指令,转移指令中的转移地址必须指明页号和页内地址,如果是转向本页,则转移地址中的页号应与本页的页号相同。设有两个作业共享该程序EDIT,一个作业定义它的页号为3,另一个作业定义它的页号为5。既然一个EDIT程序要为两个作业以同样的方式服务,那么这个程序一定是可再入程序,转移地址中的页号不能按作业的要求随机地改成3或5,因此对共享程序必须规定一个统一的页号。当共享程序的作业数较多时,规定一个统一的页号就比较困难。

 

10.在段式存储管理中如何实现共享?与页式存储管理的共享有何不同?

答:由于段是按逻辑意义来划分的,可以按段名进行访问。分段式存储管理系统允许若干个进程共享一个或多个段。为实现某段代码的共享,在分段式存储管理中,各个进程对共享段使用相同的段名,在各自的段表中填入共享段的起始地址,并置以适当的读/写控制权,即可做到共享一个逻辑上完整的主存段信息。

段式存储管理中段是信息的逻辑单位,在实现对程序和数据的共享时,以信息逻辑单位为基础。分页系统中的页是存放信息的物理单位,无完整意义,不便于共享;。

 

 

11.分页式存储管理和分段式存储管理有何区别?

答:分页和分段系统都采用离散分配主存方式,需要通过地址映射机构来实现地址变换,有许多相似之处。但两者又是完全不同的。具体表现:

①页是信息的物理单位,是系统管理的需要而不是用户的需要;而段则是信息的逻辑单位,它含有一组意义相对完整的信息,分段是为了更好地满足用户的需要。

②页的大小固定且由系统决定,因而一个系统只能有一种大小的页面;而段的长度却不固定,由用户所编写的程序决定,通常由编译程序对源程序进行编译时根据信息的性质来划分。

③分页式作业的地址空间是一维的,页间的逻辑地址是连续的;而分段式作业的地址空间则是二维的,段间的逻辑地址是不连续的。

 

12.在具有快表的段页式存储管理系统中如何实现地址变换? 

答:段页式存储管理为每一个装入主存的作业建立一张段表,且对每一段建立一张页表。段表中的每一个表目指出本段页表的始址和长度。页表中的每一个表目指出本段的逻辑页号与主存物理块号之间的对应关系。

执行指令时,地址机构根据逻辑地址的段号查找快表中的段表,得到该段的页表始址,然后根据逻辑地址中的页号查找该页表,得到对应的主存块号,由主存块号与逻辑地址中的页内地址形成可访问的物理地址。如果在快表中没有对应的段表项,则再访问主存中的段表,找到该页表始址,再进行地址变换,同时将该段表项写入快表中,以保证下次的访问。如果逻辑地址中的段号超出了段表中的最大段号或者页号超出了该段页表中的最大页号,都将形成“地址越界”程序性中断事件。

 

13.在一个分页式存储管理系统中,某作业的页表如下表所示。已知页面大小为1024B,试将逻辑地址10112148300040005012转化为相应的物理地址。

 

页号 块号
0

1

2

3

2

3

1

6

 

答:

1011 3059
2148 1124
3000 1976
4000 7012
5012 越界

 

14.给定段表如下:

段号 段首址 段长
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96

给定地址为段号和位数,试求出对应的主存物理地址。

(1)[0,430]   (2)[3,400]   (3)[1,1]   (4)[2,500]   (5)[4,42]

答:(1)649    (2)1727    (3)2301    (4)越界    (5)1994

15.一个页式存储管理系统使用FIFO、OPT和LRU页面置换算法,如果一个作业的页面走向为:

(1)2、3、2、1、5、2、4、5、3、2、5、2。

(2)4、3、2、1、4、3、5、4、3、2、1、5。

(3)1、2、3、4、1、2、5、1、2、3、4、5。

当分配给该作业的物理块数分别为3和4时,试计算访问过程中发生的缺页中断次数和缺页中断率。

答:(1)2、3、2、1、5、2、4、5、3、2、5、2

FIFO,M=3,F=9,f=75%

2 3 2 1 5 2 4 5 3 2 5 2
2 3 3 1 5 2 4 4 3 3 5 2
  2 2 3 1 5 2 2 4 4 3 5
      2 3 1 5 5 2 2 4 3

FIFO,M=4,F=6,f=50%

2 3 2 1 5 2 4 5 3 2 5 2
2 3 3 1 5 5 4 4 4 2 2 2
  2 2 3 1 1 5 5 5 4 4 4
      2 3 3 1 1 1 5 5 5
        2 2 3 3 3 1 1 1

OPT,M=3,F=6,f=50%

2 3 2 1 5 2 4 5 3 2 5 2
2 3 3 1 5 5 5 5 5 5 5 5
  2 2 3 3 3 3 3 3 2 2 2
      2 2 2 4 4 4 4 4 4

OPT,M=4,F=5,f=41.7%

2 3 2 1 5 2 4 5 3 2 5 2
2 3 3 1 5 5 5 5 5 5 5 5
  2 2 3 1 1 4 4 4 4 4 4
      2 3 3 3 3 3 3 3 3
        2 2 2 2 2 2 2 2

LRU,M=3,F=7,f=58.3%

2 3 2 1 5 2 4 5 3 2 5 2
2 3 2 1 5 2 4 5 3 2 5 2
  2 3 2 1 5 2 4 5 3 2 5
      3 2 1 5 2 4 5 3 3

LRU,M=4,F=6,f=50%

2 3 2 1 5 2 4 5 3 2 5 2
2 3 2 1 5 2 4 5 3 2 5 2
  2 3 2 1 5 2 4 5 3 2 5
      3 2 1 5 2 4 5 3 3
        3 3 1 1 2 4 4 4

(2)作业的物理块数为3 块,

使用FIFO:F=9 次,f=9 / 12 = 75 %。

使用LRU :F=10 次,f=10 / 12 = 83 %

使用OPT :F=7 次,f=7/12 = 58 %。

作业的物理块数为4 块,

使用FIFO :F=10 次,f=10 / 12 = 83 %

使用LRU :F=8 次,f=8/12=66.7%

使用OPT :F=6次,f=6/12=50%

其中,出现了Belady 现象,增加分给作业的内存块数,反使缺页中断率上升。

(3)作业的物理块数为3 块,

使用FIFO :F=9 次,f=9 / 12 = 75 %

使用LRU :F=10 次,f=10 / 12 = 83 %

使用OPT :F=7 次,f=7/12 = 58 %

作业的物理块数为4 块,

使用FIFO :F=10 次,f=10 / 12 = 83 %

使用LRU :F=8 次,f=8/12=66.7%

使用OPT :F=6次,f=6/12=50%

 

 

16.在一个请求分页式系统中,假如一个作业共有5个页面,其页面调度次序为:1,4,31,2,51,4,21,4,5。若分配给改作业的主存块数为3,分别采用FIFO、LRU、Clock页面置换算法,试计算访问过程中所发生的缺页中断次数和缺页中断率。

答:

FIFO:F=9,f=75%

LRU: F=8,f=66.7%

Clock: F=8,f=66.7%

 

 

17.在一个分页虚存系统中,用户编程空间32个页,页长1KB,主存为16KB。如果用户程序有10页长,若己知虚页0、1、2、3,已分配到主存8、7、4、10物理块中,试把虚地址0AC5H和1AC5H转换成对应的物理地址。

答:0AC5H对应的物理地址为12C5

1AC5会发生缺页中断,由系统另行分配主存空间。

 

 

18.“FIFO算法有时比LRU算法的效果好。这句话对吗?为什么?“LRU算法有时比OPT算法 的效果好。这句话对吗?为什么?

答:“FIFO算法有时比LRU算法的效果好。”这句话是对的。由于虚拟存储是基于局部性原理,有的作业的执行有可能采用FIFO算法有时比LRU算法的效果好。

“LRU算法有时比OPT算法 的效果好。”这句话是错误的。其他算法的缺页中断率不可能比OPT算法少。因为该算法选择的被淘汰页面是将来不再使用,或者是在将来最长时间内不再被访问的页面,这样产生的缺页中断次数最少。采用OPT算法可获得最低的缺页中断率,但是这是一种理想化的算法,无法实现,可以作为衡量其他算法的标准。

 

19.什么是抖动?产生抖动的原因是什么?

答:刚被调出的页面又立即要用,因而又要把它调入,而调入不久又被选中调出,调出不久又被调入,如此反复,使调度非常频繁,以至于大部分时间都花费在来回调度上。这种现象称为“抖动”或称“颠簸”。一个好的置换算法应该尽可能地减少和避免抖动现象的发生。

产生抖动的原因是系统分配给该作业的主存空间不足,需要通过页面置换满足作业占有主存的要求。

20.试设计和描述一个请求分页式存储管理的主存页面分配和回收算法。

答:

21.什么是Belady现象?试找出一个产生Belady现象的例子。

答:FIFO算法存在一种异常现象。一般来说,对于任一个作业,系统分配给它的主存物理块数越接近于它所要求的页面数,发生缺页中断的次数会越少。如果一个作业能获得它所要求的全部物理块数,则不会发生缺页中断现象。但是,采用FIFO算法时,在未给作业分配足够它所要求的页面数时,有时会出现这样的奇怪现象:分配的物理块数增多,而缺页中断次数反而增加,这种现象称为Belady现象。如:4,3,2,1,4,3,5,4,3,2,1,5。M=3,F=9;M=4,F=10。

22.试全面比较主存空间的连续分配和离散分配方式。

答:

(1)连续分配是指为一个用户程序分配一个连续的地址空间,包括单一和分区两种分配方

式。单一方式将内存分为系统区和用户区,最简单,只用于单用户单任务操作系统;分区方

式分固定和动态分区。

(2)离散分配方式分为分页、分段和段页式存储管理。分页式存储管理旨在提高内存利用

率,分段式存储管理旨在满足用户(程序员)的需要,段页式存储管理则将两者结合起来,具

有分段系统便于实现、可共享、易于保护和动态链接等优点,又能像分页系统很好解决外部

碎片及为各段可离散分配内存等问题,是比较有效的存储管理方式。

 

23.试述缺页中断与一般中断的主要区别。

答:缺页中断与一般的中断有着明显的区别,主要表现为:

①在指令执行期间产生和处理中断信号。通常,CPU在一条指令结束后接收中断请求并响应,而缺页中断则是在指令执行期间所要访问的指令或数据不在主存时所产生和处理的。

②一条指令在执行期间可能产生多次缺页中断。

 

24.在虚拟存储器管理中,淘汰页面时为什么要进行回写?通常采用什么方式来减少回写次 数和回写量?

答:请求分页式存储管理的主要依据就是页表。页表格式如下所示:

 

页号 物理块号 状态位 访问字段 修改位 辅存地址

 

其中, “修改位”则表示该页在调入主存后是否被修改,由于作业在磁盘上保留一份备份,若此次调入主存后未被修改,则在置换该页时不需要再将该页写回磁盘,以减少系统的开销;如果已被修改,则必须将该页回写到磁盘上,以保证信息的更新与完整。

 

25.在请求式页式存储管理中,可采用工作集模型以决定分给进程的物理块数,有如下页面访问序列:

……251633789162343434443443……

|-------| |-------|

⊿   t1     ⊿  t2

窗口尺寸⊿=9,试求t1,t2时刻的工作集。

答:⊿=9, t1时刻的工作集为{1,6,3,7,8,9}

⊿=9,t2时刻的工作集{3,4}

 

26.一个程序要将100×100数组置初值0。现假设分配给该程序的主存块数有两块,页面的大 小为每页100个字,数组中每一行元素存放在一页中。开始时,第一页已经调入主存。若采用LRU算法,则下列两种对数组的初始化程序段引起缺页中断次数各是多少?

(1)  for (j=0;j<100;j++)

for (i=0;i<100;i++)

A[i][j]=0;

(2)  for (i=0;i<100;i++)

for (j=0;j<100;j++)

A[i][j]=0;

 

答:(1) 100*100-1

(2)100-1

 

27.试叙述虚拟存储器的基本原理,如何确定虚拟存储器的容量?

答:虚拟存储器基于局部性原理,即可以把作业信息保存在磁盘上,当作业请求装入时,只需将当前运行所需要的一部分信息先装入主存,作业执行过程时,如果所要访问的信息已调入主存,则可继续执行;如果信息尚未装入主存,再将这些信息调入主存,使程序继续执行;如果此时主存已满,无法再装入新的信息,则系统将主存中暂时不用的信息置换到磁盘上,腾出主存空间后,再将所需要的信息调入主存,使程序继续执行。这样,可使一个大的用户程序得以在比较小的主存空间中运行,也可以在主存中同时装入更多的作业使它们并发执行。这不仅使主存空间能充分地被利用,而且用户编制程序时可以不必考虑主存的实际容量,允许用户的逻辑地址空间大于主存的实际容量。从用户的角度来看,好像计算机系统提供了一个容量很大的主存,它为虚拟存储器。

虚拟存储器的容量由计算机的地址结构和辅助存储器的容量所决定,与实际主存的容量无关,其逻辑容量由主存和辅助存储器容量之和决定。

 

28.设某计算机的逻辑地址空间和物理地址空间均为64KB按字节编址若某进程最多需要6页数据存储空间,页的大小为1KB操作系统采用固定分配局部置换策略为此进程分配4个物理块。

页号 块号 装入时刻 访问位
0 7 130 1
1 4 230 1
2 2 200 1
3 9 160 1

当该进程执行到时刻260时,要访问逻辑地址为17CAH的数据,请问答下列问题:

(1)该逻辑地址对应的页号是多少?

(2)若采用先进先出(FIFO)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。

(3)若采用时钟(CLOCK)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。(设搜索下一页的指针沿顺时针方向移动,且当前指向2号物理块,示意图如下。)

 

 

 

 

 

 

 

 

 

答:

(1)该逻辑地址对应的页号是5

(2)FIFO算法,该逻辑地址对应的物理地址是1FCAH

(3)CLOCK算法,该逻辑地址对应的物理地址是0BCAH

习题五

1.试说明各种I/O控制方式及其主要优缺点。

答: I/O设备的控制方式分为四类:直接程序控制方式、中断驱动控制方式、直接存储器访问(DMA)控制方式和通道控制方式。

(1)直接程序控制方式

直接程序控制方式由用户进程直接控制主存或CPU和外围设备之间的信息传送。通过I/O指令或询问指令测试I/O设备的忙/闲标志位,决定主存与外围设备之间是否交换一个字符或一个字。

直接程序控制方式简单,不需要多少硬件的支持,但由于高速的CPU和低速的I/O设备之间在速度上不匹配,因此,CPU与外围设备只能串行工作,使CPU的绝大部分时间都处于等待是否完成I/O操作的循环测试中,造成CPU的极大浪费,外围设备也不能得到合理的使用,整个系统的效率很低。直接程序控制方式只适合于CPU执行速度较慢,且外围设备较少的系统。

(2)中断驱动控制方式

中断机制,外围设备仅当操作正常结束或异常结束时才向CPU发出中断请求。在I/O设备输入每个数据的过程中,由于无需CPU干预,一定程度上实现了CPU与I/O设备的并行工作。仅当输入或输出完一个数据时,才需CPU花费极短的时间做中断处理。这样可使CPU和I/O设备都处于忙碌状态,从而提高了整个系统的资源利用率及吞吐量。中断驱动控制方式可以成百倍地提高CPU的利用率,并且能支持多道程序和设备的并行操作。但是由于I/O操作直接由CPU控制,每传送一个字符或一个字,都要发生一次中断,仍然占用了大量的CPU处理时间。

(3)直接存储器访问控制方式

直接存储器访问控制方式又称DMA(Direct Memory Access)方式。在DMA控制器的控制下,采用窃取或挪用总线控制权,占用CPU的一个工作周期把数据缓冲器中的数据直接送到主存地址寄存器所指向的主存区域中,在设备和主存之间开辟直接数据交换通道,成批地交换数据,而不必受CPU的干预。DMA方式与中断驱动控制方式相比,减少了CPU对I/O操作的干预,进一步提高了CPU与I/O设备的并行操作程度。

DMA的操作全部由硬件实现,不影响CPU寄存器的状态。DMA方式的线路简单,价格低廉,适合高速设备与主存之间的成批数据传输,小型、微型机中的快速设备均采用这种方式,但其功能较差,不能满足复杂的I/O要求。

  1. 通道控制方式

通道控制方式将对一个数据块的读(或写)为单位的干预,减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预,可以进一步减少CPU的干预程度。同时可实现CPU、通道和I/O设备三者的并行操作,从而更加有效地提高整个系统的资源利用率。

 

 

2.试说明DMA的工作流程。

答:在DMA控制器的控制下,采用窃取或挪用总线控制权,占用CPU的一个工作周期把数据缓冲器中的数据直接送到主存地址寄存器所指向的主存区域中,在设备和主存之间开辟直接数据交换通道,成批地交换数据,而不必受CPU的干预。DMA方式的工作流程如下图所示。

3.简述采用通道技术时,I/O操作的全过程。

答:采用通道技术当进程提出I/O请求后,操作系统首先分配通道和外设,然后按照I/O请求编制通道程序并存入主存,将其起始地址送入通道地址寄存器(CAW),接着CPU发出“启动I/O”指令启动通道工作,启动成功后,通道逐条执行通道程序中的通道指令,控制设备实现I/O操作。

CPU启动通道后,通道的工作过程如下。

①从主存固定单元取出通道地址寄存器(CAW),根据该地址从主存中取出通道指令,通道执行通道控制字寄存器(CCW)中的通道命令,将I/O地址送入CCW,发出读、写或控制命令,并修改CAW使其指向下一条通道指令地址。

②控制器接收通道发来的命令之后,检查设备状态,若设备不忙,则告知通道释放CPU,开始I/O操作。执行完毕后,如果还有下一条通道指令,则返回①,否则转③。

③通道完成I/O操作后,向CPU发出中断请求,CPU根据通道状态字了解通道和设备的工作情况,处理来自通道的中断。

 

 

4.试叙述引入缓冲的主要原因。其实现的基本思想是什么?

答:引入缓冲的主要原因(1)缓和CPU与I/O设备间速度不匹配的矛盾;(2)减少对CPU的中断频率,放宽对CPU中断响应时间的限制;(3)提高CPU和I/O设备之间的并行性

缓冲的实现方法有两种:一种方法是采用专用硬件缓冲器;另外一种方法是在主存中划出一个具有n个单元的专用区域,以便存放I/O数据,主存缓冲区又称软件缓冲。

 

 

5.何谓设备的独立性?如何实现设备的独立性?

答:用户在编制程序时使用的设备与实际使用哪台设备无关,这种特性称为设备的独立性。用户编制程序时,不必指明特定的设备,而是在程序中使用用“设备类、逻辑号”定义的逻辑设备,程序执行时系统根据用户指定的逻辑设备转换成与其对应的具体物理设备,并启动该物理设备工作。

 

 

6.假定磁带记录密度为每英寸800字符,每一逻辑记录为160个字符,块间隙为0.6英寸。今有1500个逻辑记录需要存储,试计算磁带利用率?若要使磁带空间利用率不少于50%,至少应以多少个逻辑记录为一组?

答:

(1)160/800=0.2(英寸)

0.2/(0.2+0.6)=25%

(2)假设块因子为x

0.2x/(0.2x+0.6)>50%

求出块因子为3

7.目前常用的磁盘调度算法有哪几种?每种算法优先考虑的问题是什么?

答:目前常用的磁盘调度算法有先来先服务、最短寻道时间优先及电梯调度等算法等。

(1) 先来先服务算法优先考虑进程提出请求访问磁盘的先后次序;

(2) 最短寻道时间优先算法优先考虑要求访问的磁道与当前磁头所在磁道距离是否最短;

(3) 电梯调度算法考虑不仅考虑访问的磁道与当前磁道间的距离,更优先考虑磁头当前的移动方向。

 

 

8.假设某磁盘共200个柱面,编号为0~199,如果在访问143号柱面的请求服务后,当前正在访问125号柱面,同时有若干请求者在等待服务。它们依次请求的柱面号为:

861479117794150102175130。

请回答:分别采用先来先服务算法、最短寻找时间优先算法、电梯调度算法和单向扫描算法确定实际的服务次序以及移动臂分别移动的距离。

答:采用先来先服务算法服务次序:125,86,147,91,177,94,150,102,175,130;移动的距离为547;

最短寻找时间优先算法服务次序:125,130,147,150,175,177,102,94,91,86;移动的距离为143;

电梯调度算法服务次序:125,102,94,91,86,130,147,150,175,177;移动的距离为130;

单向扫描算法服务次序:125,130,147,150,175,177,86,91.94,102;移动的距离为375。

 

 

9.假定在某移动臂磁盘上,刚刚处理了访问75号柱面的请求,目前正在80号柱面读信息,并且有下述请求序列等待访问磁盘:

请求次序 1 2 3 4 5 6 7 8
欲访问的柱面号 160 40 190 188 90 58 32 102

试用:(1) 电梯调度算法

(2) 最短寻找时间优先算法

分别列出实际处理上述请求的次序。

答:(1) 电梯调度算法服务次序为:80,90,102,160,188,190,58,40,32

(2) 最短寻找时间优先算法服务次序为:80,90,102,160,188,190,58,40,32

 

 

10.除FCFS外,所有磁盘调度算法都不公平,如造成有些请求饥饿。试分析:(1)为什么不公平?(2)提出一种公平性调度算法。(3)为什么公平性在分时系统中是一个很重要的指标?

答:( l )对位于当前柱面的新请求,只要一到达就可得到服务,但对其他柱面的服务则不然。如SST 下算法,一个离当前柱面远的请求,可能其后不断有离当前柱面近的请求到达而得不到服务(饥饿)。 ( 2 )可划定一个时间界限,把这段时间内尚未得到服务的请求强制移到队列首部,并标记任何新请求不能插到这些请求前。对于SSTF 算法来说,可以重新排列这些老请求,以优先处理。 ( 3 )公平性可避免分时进程等待时间过长而拉长响应时间。

 

 

11.假定磁盘的移动臂现在处于第8号柱面,有如下6个请求者等待访问磁盘,请列出最省时间的响应次序。

序号 柱面号 磁头号 扇区号
1

2

3

4

5

6

9

7

15

9

20

7

6

5

20

4

9

15

3

6

6

4

5

2

 

答:2,6,1,4,3,2 或2,6,4,1,3,2 或 6,2,1,4,3,2或 6,2,4,1,3,2

 

 

12.一个软盘有40个柱面,查找移过每个柱面花6ms。若文件信息块零乱存放,则相邻逻辑块平均间隔13个柱面。但优化存放,相邻逻辑块平均间隔2个柱面。如果搜索延迟为100ms,传输速度为每块25ms,问在这两种情况下传输100块的文件各需要多长的时间。

答:非优化存放,读一块数据需要时间为:13 *6 100 25 = = 203ms 因而,传输100 块文件需:2O300ms

优化存放,读一块数据需要时间为:2*6 十100 + 25 = = 137ms 因而,传输100 块文件需:13700ms 。

 

 

13.假定某磁盘的旋转速度是每圈20ms,格式化时每个盘面分成10个扇区,现有10个逻辑记录顺序存放在同一个磁道上,处理程序要处理这些记录,每读出一条记录后处理要花4毫秒的时间进行处理,然后再顺序读下一条记录进行处理,直到处理完这些记录,请回答:

(1)顺序处理完这10条记录总共花费多少时间?

(2)请给出一个优化方案,使处理能在最短时间内完成,并计算出优化分布时需要花费的时间。

答:(1)20/2+2+4+(16+2+4)*9=214

(2)20/2+(2+4)*10=70

 

 

14.试说明设备驱动程序应具备哪些功能?

答:为了实现I/O进程与设备控制器之间的通信,设备驱动程序应具有以下功能。

①接收由I/O进程发来的命令和参数,并将命令中的抽象要求转换为具体要求。例如,将磁盘块号转换为磁盘的柱面号、磁道号及扇区号。

②检查用户I/O请求的合法性,了解I/O设备的状态,传递有关参数,设置设备的工作方式。

③发出I/O命令。如果设备空闲,便立即启动I/O设备去完成指定的I/O操作。如果设备处于忙碌状态,则将请求者的请求挂在设备队列上等待。

④及时响应由控制器或通道发来的中断请求,并根据其中断类型调用相应的中断处理程序进行处理。

⑤对于设置有通道的计算机系统,驱动程序还应能够根据用户的I/O请求自动地构成通道程序。

 

 

15.何谓虚拟设备?简述虚拟设备的设计思想。

答:虚拟设备是指采用相应的技术和方法将独占型设备变换为若干台对应的逻辑设备,即实现了虚拟设备功能。其设计思想是将独占型设备改造为共享型设备。宏观上,虽然十多个进程在同时使用一台独占型设备,而对每一个进程而言,它们都认为自己独占了一个设备。

 

 

16.SPOOLing系统由哪些部分组成?简述它们的功能。

答:SPOOLing系统主要由三部分程序组成,即“预输入”程序、实现输入井读和输出井写的“井管理”程序和“缓输出”程序。

(1)预输入程序

预输入程序把一批作业组织在一起形成作业流,由预输入程序把作业流中每个作业的初始信息由输入设备输入到输入井保存,并填写好输入表以便在作业执行中要求输入信息时,可以随时找到它们的存放位置,以备作业调度。

(2)井管理程序

井管理程序包括井管理读程序和井管理写程序两部分。

当作业请求从输入机上读文件信息时,就把任务转交给井管理读程序,从输入井中读出信息供用户使用。

当作业请求从打印机上输出结果时,就把任务转交给井管理写程序,把产生的结果保存到“输出井”中。

(3)缓输出程序

缓输出程序负责查看输出井中是否有等待输出的结果信息,若有,则启动打印机把作业的结果文件打印输出。当一个作业的文件信息输出完毕后,将它占用的井区回收以供其他作业使用。

 

 

17.实现虚拟设备的主要条件是什么?

答:虚拟设备必须建立在具有多道程序功能的操作系统上,需要有高速的、大容量的随机存储器支持。

 

 

 

习题六

  1. 什么是文件?

答:文件是一组在逻辑上有完整意义的相关信息的集合,每个文件都要用一个名字标识,称为文件名。

 

  1. 文件系统应具有哪些功能?

答:文件系统应具有以下功能:目录管理、文件的组织、文件存储空间的管理、文件操作和文件的共享、保护和保密等 。

 

  1. 文件系统提供的主要文件操作有哪些?

答:文件系统提供的基本文件操作有建立文件、打开文件、读文件、写文件、关闭文件和删除文件等。

 

  1. 文件系统可分成几个层次?简述每层的主要功能。

答:文件系统分成三个层次,即最底层的描述层、中间的管理层和最上面的接口层。其中:描述层负责说明系统中所有文件和文件存储介质的使用状况;管理层包括了对文件进行管理的启动控制I/O设备、数据交换、文件存储组织及文件的检索、文件保护等绝大多数手段,因而成为文件系统的最关键部分;接口层负责为用户使用文件系统提供相应的接口。

 

  1. 什么是文件的逻辑结构?它有哪几种组织方式?

答:文件的逻辑结构是用户所观察到的文件组织形式,是用户可以直接处理的数据及结构,它独立于物理特性构造而成。由用户构造的文件称文件的逻辑结构,又称逻辑文件。文件的逻辑结构可分成两大类:一类是无结构的流式文件,另一类是有结构的记录式文件。

 

  1. 什么是文件的物理结构?它有哪几种组织方式?

答:文件的物理结构又称文件的存储结构,它是指文件在辅存上的存储组织形式,与存储介质的存储性能有关。常见的文件物理结构有三种,即顺序结构、链接结构、索引结构,不太使用直接文件结构。

 

  1. 解释下列术语并说明它们之间的关系:存储介质、卷、块、文件。

答:存储介质是可用来记录信息的媒体。常用的存储介质有磁带、硬磁盘组、软磁盘片、光盘及U盘等。存储介质的物理单位是“卷”。块又称物理记录,是存储介质上连续信息所组成的一个存储区域。文件是一组在逻辑上有完整意义的相关信息的集合。

一个卷上可以只保存一个文件,也可以保存多个文件,一个文件也可保存在多个卷上;块也成为内存、存储介质间进行数据交换的基本单位。

 

  1. 选择存取方式时主要考虑的因素有哪些?

答:选择存取方式时主要取决于下面两个方面的因素:文件的性质和存储设备的特性。

 

  1. 总结文件的存取方法、文件的存储结构和存储设备类型之间的关系。

答:磁带机是一种从磁头的当前位置开始顺序读写的设备,文件适合顺序存取成顺序结构或链接结构;磁盘机是一种可按指定的块地址进行信息存取的设备,文件适合随机存取成链接结构或索引结构。

 

  1. 试比较顺序文件和链接文件各自的优点和缺点。

答:顺序文件:优点是按照文件内容的先后顺序依次访问,不必每次都对内容进行定位,因此文件的存取速度快;缺点是存储空间的利用率不高、动态更新文件困难、要求确定文件长度、不适于随机存取。

链接文件:采用链接结构建立文件时也不必事先考虑文件的长度,只要存储空间足够大,可在文件的任何位置插入一个记录或删除一个记录,效率明显高于顺序文件;缺点是链接指针占用了一定的空间、不适于随机存取、可靠性无法得到保证。

 

  1. 什么是索引文件?为什么要引入多级索引文件?

答:所谓索引结构是指系统为每个文件建立一个专用数据结构——索引表,用于指出每个逻辑记录的物理存储位置。为了克服检索索引表速度慢和开销大的缺点,还可以采取建二级直至多级索引表的办法,其中主索引表指出次索引表的位置,次索引表指出该文件按关键字顺序排列的包含若干记录的子集。

 

12.什么是记录的成组?采用这种技术有什么优点?

答:把若干个逻辑记录合并成一组存入一个物理块的过程称记录的成组。记录的成组操作不仅提高了存储空间的利用率,而且还减少了启动外设的次数,大大提高了系统的工作效率。

 

13.什么是记录的分解?采用这种技术有什么优点?

答:从一组逻辑记录中把一个个逻辑记录分离出来的操作过程称为记录的分解。当把一个物理块读入系统缓冲区中时,利用记录的分解操作可将一个个逻辑记录从物理块中读出来并处理,有利于提高存储介质的利用率和减少启动存储设备的次数。

 

14.已知某用户文件共10个逻辑记录,每个逻辑记录长度为480个字符,现把该文件存放到磁带上,若磁带记录密度为800字符/英寸,块与块之间的间隙为0.6英寸,请

(1)求解不采用记录成组操作时磁带空间的利用率。

(2)求解采用记录成组操作且块因子为5时,磁带空间的利用率。

(3)当按上述方式把文件存放到磁带上后,用户要求每次读一个逻辑记录存放到他的工作区。当对该记录处理后,又要求把下一个逻辑记录读入他的工作区,直至10个逻辑记录处理结束。系统应如何为用户服务?

答:(1)不采用记录成组操作时磁带空间的利用率=480/(480+800*0.6)=50%

(2)采用记录成组操作且块因子为5时,利用率=480*5//(480*5 +800*0.6)=83.3%

(3)把文件10个逻辑记录读入用户区单元开始区域,则主要过程如下:

首先向系统申请一个系统缓冲区,其起始地址假设为内存的L单元,很明显先读第1

个记录组到L单元,然后逐个将该组的记录一个个分离出来并放入用户缓冲区单元中处

理记录,等处理完毕再分离下一个记录到用户缓冲区,直至第一组全部处理结束;

然后基本重复第一组记录的读入及分离过程,直至10个记录全部结束。

 

15.什么叫‘按名存取’?文件系统如何实现文件的按名存取?

答:按名存取即用户只须向系统提供所需访问文件的名字,便能快速准确找到文件在辅存上的存储位置。文件系统通过文件目录机制实现文件的按名存取功能。

 

16.为了实现按名存取,文件目录应包括哪些内容?

答:文件目录主要是由若干文件目录项组成,每个目录项包括:文件基本信息、文件结构信息、文件管理信息和文件存取控制信息。

 

17.文件目录在何时建立?它在文件管理中起什么作用?

答:每新建一个文件都要新建一个文件控制块并将其添加到文件目录中,文件目录是文件实现按名存取、快速检索、文件共享和文件重名的关键手段。

 

18.比较一级目录和二级目录各自的优点和缺点

答:一级目录结构比较简单,易实现,管理非常方便,但是查找速度慢、不允许文件重名和共享;二级目录由一张主文件目录表和它所管辖的若干张用户文件目录表构成,可以方便实现文件访问克服了一级目录结构的缺点,但也存在一些问题。该结构虽然能有效地隔离管理多个用户,但只有当用户之间完全无关时,这种隔离才是一个优点;若用户之间需要相互合作共同去完成一个大任务,且一用户又随时需要去访问其他用户的文件时,这种隔离便成了缺点,因为这样便使得用户不便于共享文件。

 

19.何为绝对路径?何为相对路径?

答:绝对路径名是从根目录出发到某个文件的通路上所有各级子目录名的顺序组合称为该文件的路径名;相对路径指从当前目录出发到指定文件的路径名。

 

20.简述文件控制块的主要功能,它应包含哪些内容?

答:文件控制块可以惟一标识出一个文件,并与文件一一对应。一般地说,文件控制块应包含如下内容: 文件基本信息、文件结构信息、文件管理信息和文件存取控制信息。

 

21.辅存空间的管理方法有哪几种?

答:常用的辅存空间的管理方法有:空闲块表法、空闲块链法、位示图法和成组链接法

 

22.试比较空闲块表法和空闲块链表各自特点。

答:空闲块表法特点:可减少访问辅存的I/O操作次数,因此具有较高的分配速度。但该方法在反复分配时会产生较多的存储碎片,这也会影响辅存空间的利用率。

空闲块链法特点:与空闲块链表法相比,空闲区链表法的优缺点刚好与前者相反,即分配和回收过程较复杂,但链表长度较短,且访问辅存的次数大大减少,效率更高。

 

23.试简述成组链接法中专用块组的作用。

答:专用块组的作用是存放不足N块的那部分空闲块的块号及块数,分配块时,直接在主存专用块堆栈中可找到哪些块是空闲的;回收块时,只要把归还块的块号登记到当前专用块堆栈的栈顶即可。

 

24.文件系统提供的主要文件操作有哪几个?

答:文件系统提供的主要文件操作有六种:建立文件、打开文件、读文件、写文件、关闭文件和删除文件。

 

25.使用文件系统时,通常要显式地进行打开和关闭操作,为什么?

答:通过“打开文件”,验证了用户对文件的使用权,并为用户做好读文件前的准备工作。当用户访问结束后,再通过“关闭文件”,向系统归还该文件的使用权,至此文件访问过程结束。

 

26.删除文件时为什么不要执行打开操作?

答:若执行了打开操作时,系统会将文件的有关信息从辅存读入主存,此时的文件是无法删除并释放辅存空间的。

 

27.何为文件共享?文件共享有哪些主要方法?

答:所谓文件共享,是指允许两个或更多个用户同时使用同一个文件。当前常用的文件共享方法有:绕道法和链接法,其中后者更常用。

 

28.链接法共享文件主要采取哪几种实现技术?试比较每种实现技术的特点。

答:根据链接对象的不同,链接法共享文件主要采取三种具体实现技术。其中:

目录链接技术的特点为:将共享文件的存储地址、长度等文件信息记录在文件目录项中,但链接后的目录结构变成了网状结构图,使得管理就变得复杂了,同时会导致删除异常和更新异常。

基于索引结点的链接技术特点为:将共享文件的存储地址、长度等文件信息记录在索引结点中,大大减少了删除异常和更新异常,但也会导致指针悬空及共享文件所有者为等待其他用户完成而付出高昂的代价。

符号链接术的特点为:通过调用系统过程“link”来创建一个LINK型新文件登记被链接的文件的路径名,优点突出,主要体现在下列避免了指针悬空和实现网络环境下任意文件的共享两方面。

 

29.影响文件系统安全的主要因素有哪些?

答:影响文件系统安全的主要因素有人为因素、系统因素和自然因素等三方面。

 

30.试比较文件保护和文件保密两种技术的区别。

答:文件保护是指防止用户由于错误操作导致的数据丢失或破坏;而文件保密是指文件本身不得被未经授权的用户访问。

 

31.常见的文件存取权限一般有哪几种?

答:常见的文件存取权限一般有可执行权E、可读权R、可写权W及不能执行任何操作权-。

 

32.磁盘容错技术可以分成哪几个等级?

答:磁盘容错技术可以分成三个等级:一级磁盘容错技术主要用于防止磁盘表面发生缺陷所引起的数据丢失;二级磁盘容错技术则用于防止磁盘驱动器故障和磁盘控制器故障所引起的系统不能正常工作;三级容错技术则主要用于高可靠的网络系统。

 

33.与一级磁盘容错技术相比,二级容错技术有什么优点?

答:一级容错技术一般只能防止磁盘表面损坏造成的数据丢失。若磁盘驱动器发生故障时,则数据无法写入磁盘中,仍可能造成数据丢失。为避免在这种情况下产生数据丢失,可采取磁盘镜像和磁盘双工等二级容错技术。

 

34.数据转储技术通常采用的措施有哪几种?

答:数据转储技术通常采用的措施有建立副本、定期转储等两种。

 

35.若一个硬盘上共有5000个磁盘块可用于存储信息,若由字长为32位的字构造位示图,求:

  • 位示图共需多少个字?
  • 若某文件被删除,它所占据的盘块块号分别为12、16、23和37,文件删除后,位示图如何修改?

答:(1) 位示图共需5000/32=157个字,另加一个登记空闲块字,共158个

  • 根据要回收的磁盘物理块号计算得到字号和位号分别为:

12对应的字号和位号分别为0字12位;16对应0字16位;23对应0字23位;37对应1字5位,则当文件被删除时只需将0字12位、16位、23位及1字5位共四个位置清0,同时再将空闲块总数加4即可。

 

  1. 若一个硬盘共有100个柱面,每个柱面上有15个磁头,每个磁道划分成8个扇区。现有一个含有6000个逻辑记录的文件,逻辑记录的大小与扇区大小一致,该文件以顺序结构的形式被存放到磁盘上。磁盘柱面、磁头、扇区的编号均从“0”开始,逻辑记录的编号从“1”开始。文件信息从0柱面、0磁头、0扇区开始存放,求:

(1)该文件的第5000个逻辑记录应放在哪个柱面的第几磁头的第几扇区?

(2)36柱面12磁头5扇区中存放了该文件的第几个逻辑记录?

答:(1)5000记录号对应4999块号,转换成物理地址为:柱面号=4999 div 120=41

磁头号=4999 mod 120 div 8=79 div 8=9;扇区号=79 mod 8=7

即该文件的第5000个逻辑记录应放在41柱面的9磁头的7扇区上。

(2)块号=36*120+12*8+5=4421,逻辑记录=4421+1=4422

即36柱面12磁头5扇区中存放了该文件的第4422个逻辑记录。

 

 

 

本文地址:http://liuyanzhao.com/2916.html

转载请注明

 

word文件下载地址:

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
言曌

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: