原文和下载地址:https://liuyanzhao.com/2916.html
原文文末有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)层次分配策略
层次分配策略将阻止第四个条件(循环等待条件)的出现。在层次分配策略下,资源被分成多个层次,一个进程得到某一层的一个资源后,它只能再申请较高一层的资源;当一个进程要释放某层的一个资源时,必须先释放所占用的较高层的资源;当一个进程获得了某一层的一个资源后,它想再申请该层中的另一个资源,必须先释放该层中的已占用资源。

习题三

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

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

计算机上运行一个用户作业通常要经过哪几个作业步?
答:在计算机上运行用户作业时,通常要经历以下4步:
(1)编辑,即采用某种高级语言按一定算法编写源程序,将源程序通过某种手段(如键盘输入)送入计算机内;
(2)编译,即调用上述高级语言的编译程序,对源程序进行编译,产生目标代码程序;
(3)连接装配,即将目标代码及调用的各种库代码连接装配成一个可执行程序;
(4)运行,即将可执行程序装入内存并提供程序运行时所需数据,然后运行程序并产生运行结果。

操作系统提供哪些手段控制和管理作业?
答:作业控制方式有两种,即批处理控制方式和交互式控制方式。其中:
采用批处理控制方式控制作业执行时,用户使用操作系统提供的“作业控制语言”对作业执行的控制意图编写成一份“作业控制说明书”,连同该作业的源程序和初始数据一同提交给计算机系统,操作系统将按照用户说明的控制意图来控制作业的执行。
采用交互式控制方式控制作业执行时,用户使用操作系统提供的“操作控制命令”来表达对作业执行的控制意图。

用户交付计算机运行的作业有哪几种?
答:用户交付计算机运行的作业有两种,即:
采用批处理控制方式的作业称为“批处理作业”,又称“脱机作业”。
采用交互式控制方式的作业称为“交互式作业”,又称“联机作业”,对于来自终端的作业也称为“终端作业”。

作业管理功能包括哪几个部分?
答:根据作业进入系统的过程,可将作业管理功能分成三部分:
(1) 作业输入:把作业装入辅存输入井中,并按照进入输入井的先后顺序形成后备作业队列的过程。
(2) 作业调度:按某种调度策略选择后备作业队列中的若干作业装入主存运行的过程。
(3) 作业控制:在操作系统控制下,用户如何组织他的作业并控制作业进入处理器运行的过程。

什么是JCL和JCB,分别列举它们的主要内容和作用。
答:JCL全称Job Control Language,即作业控制语言,是由若干作业控制语句组成的集合,每个控制语句除包含了表示特征的关键字外,还有指示控制要求的若干参数,大都提供以下主要功能:
(1)作业的提交。
(2)控制作业和作业步的执行。
(3)各种软硬件资源的使用。
JCB全称Job Control Block,即作业控制块,是批处理作业在系统中存在的标志,其中存有系统对于作业进行管理所需要的全部信息,它们被保存于辅存存储区域中。作业控制块中所包含的信息数量及内容因系统而异,但一般应包含:
作业名、作业状态、作业类别、作业优先数、作业控制方式、资源需求量、进入系统时间、开始运行时间、运行时间、作业完成时间和所需主存地址及外设种类及台数等。

什么是作业调度程序?简述作业调度程序的主要功能。
答:完成作业调度功能的控制程序称作业调度程序。作业调度程序的主要功能包括:
(1)按照某种调度算法从后备作业队列中选取作业。
(2)为被选中的作业分配必要的主存和外设资源。因此作业调度程序在挑选作业过程中要调用存储管理程序和设备管理程序中的某些功能。
(3)为选中的作业开始运行做好一切准备工作。这种准备工作包括:修改作业状态为运行态,为运行作业创建进程,构造和填写作业运行时所需要的有关表格,如作业表等。
(4)在作业运行完成或由于某种原因需要撤离系统时,作业调度程序还要完成作业的善后处理工作。包括回收分给它的全部资源,为输出必要信息编制输出文件,撤销该作业的全部进程和作业控制块等,最终将其从现有作业队列中删除。

作业的状态分成哪几种?简述各种状态之间是如何转换的。
答:通常作业的状态分成四种,即提交状态、后备状态、运行状态和完成状态;具体转换过程如下:
(1)提交状态:一个作业在其处于用户手中并经过输入设备进入到外存输入井 ,系统为其建立作业控制块。这时的作业处于提交状态。
(2)后备状态:对于已经进入输入井的作业,系统将它插入到输入井后备队列中,等待作业调度程序的调度运行。这时的作业从提交状态进入后备状态。
(3)运行状态:一个处于后备状态的作业,一旦被作业调度程序选中装入主存,系统就为它分配必要的软硬件资源,然后建立相应的进程并插入到进程就绪队列中。这时的作业从后备状态进入运行状态。
(4)完成状态:作业完成其全部运行过程并释放其所占全部资源而正常结束或异常终止时,作业从运行状态进入完成状态。

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

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

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

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

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

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

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

试比较先来先服务、短作业优先和响应比最高者优先三种算法的各自特点。
答:先来先服务FCFS算法是一种非剥夺式调度算法,容易实现,体现了公平,但效率不高,只顾及到作业等候时间,而没考虑作业要求服务时间的长短,不利于短作业而优待了长作业。
短作业优先SJF调度算法强调了资源的充分利用,有效地降低了作业的平均等待时间,使得单位时间内处理作业的个数最大,保证了作业吞吐量最大,但对作业运行时间预先作出估算难,且完全未考虑作业的紧迫程度和等待时间,因此对于长作业极为不利。
响应比最高者优先算法HRRF是介乎这两种算法之间的一种折衷的策略,既考虑作业等待时间,又考虑作业的运行时间。这样既照顾了短作业又不使长作业的等待时间过长,改进了调度性能,缺点是每次计算各道作业的响应比会有一定的时间开销,需要估计期待的服务时间,性能要比SJF略差。

在单道批处理系统中,有四个作业到达输入井和需要的计算时间如表所示,现分别采用先来先服务调度算法、最短作业优先算法和响应比最高者优先算法,忽略作业调度所花的时间。当第一个作业进入系统后就可开始调度。
作业 入井时间 计算时间 开始时间 完成时间 周转时间 带权周转时间
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

单道批处理系统中,下列三个作业采用先来先服务调度算法、最短作业优先算法和最高响应比优先算法进行调度,哪一种算法性能较好?请完成下表:
作业 提交时间 计算时间 开始
时间
完成
时间
周转
时间
带权周
转时间
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)列出所有作业进入系统时间及结束时间。
(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

若某系统采用可变分区方式管理主存中的用户空间,供用户使用的最大主存空间为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

有一个多道程序设计系统,仍采用可变分区方式管理主存中的用户空间,但允许移动已在主存中的任何作业。假设用户可使用的最大主存空间为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

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

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

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

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

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

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

简述系统调用的主要执行过程。
答:用户编制程序使用系统调用请求操作系统服务时,编译程序将其转换成目标程序中的“访管指令”及一些参数。目标程序执行时,当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,试将逻辑地址1011,2148,3000,4000,5012转化为相应的物理地址。

页号 块号
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,3,1,2,5,1,4,2,1,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要求。
通道控制方式
通道控制方式将对一个数据块的读(或写)为单位的干预,减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预,可以进一步减少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号柱面,同时有若干请求者在等待服务。它们依次请求的柱面号为:
86,147,91,177,94,150,102,175,130。
请回答:分别采用先来先服务算法、最短寻找时间优先算法、电梯调度算法和单向扫描算法确定实际的服务次序以及移动臂分别移动的距离。
答:采用先来先服务算法服务次序: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.实现虚拟设备的主要条件是什么?
答:虚拟设备必须建立在具有多道程序功能的操作系统上,需要有高速的、大容量的随机存储器支持。

习题六

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

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

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

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

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

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

解释下列术语并说明它们之间的关系:存储介质、卷、块、文件。
答:存储介质是可用来记录信息的媒体。常用的存储介质有磁带、硬磁盘组、软磁盘片、光盘及U盘等。存储介质的物理单位是“卷”。块又称物理记录,是存储介质上连续信息所组成的一个存储区域。文件是一组在逻辑上有完整意义的相关信息的集合。
一个卷上可以只保存一个文件,也可以保存多个文件,一个文件也可保存在多个卷上;块也成为内存、存储介质间进行数据交换的基本单位。

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

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

试比较顺序文件和链接文件各自的优点和缺点。
答:顺序文件:优点是按照文件内容的先后顺序依次访问,不必每次都对内容进行定位,因此文件的存取速度快;缺点是存储空间的利用率不高、动态更新文件困难、要求确定文件长度、不适于随机存取。
链接文件:采用链接结构建立文件时也不必事先考虑文件的长度,只要存储空间足够大,可在文件的任何位置插入一个记录或删除一个记录,效率明显高于顺序文件;缺点是链接指针占用了一定的空间、不适于随机存取、可靠性无法得到保证。

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

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即可。

若一个硬盘共有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 9=7
即该文件的第5000个逻辑记录应放在41柱面的9磁头的7扇区上。
(2)块号=36*120+12*8+5+1=4422
即36柱面12磁头5扇区中存放了该文件的第4422个逻辑记录。

习题七

Windows 2000中线程的状态分为几种?
答: Windows 2000的线程是内核线程,系统的处理机调度对象为线程。Windows 2000把线程状态分成下面七种状态:①、创建和初始化线程对象;②、等待运行的就绪状态;③、优先级最高的就绪线程转为备用状态,即下一个要运行的线程,要说明的是在多处理器系统中,每个处理器上只能有一个线程处于备用状态;④、运行态,是指线程处于处理器上运行,直至出现被更高优先级线程抢占、终止、时间时间片用光、调用用于I/O等阻塞式系统调用为止的状态;⑤、等待信号的等待态;⑥、为等待执行时所需资源所处的转换态;⑦、执行完成后所处的终止态。图7-11显示了 Windows 2000的线程状态及这些状态之间的转换情况。

Windows 2000的主要设计目标是哪些?
答:操作系统的设计目标有:可靠性(正确性和健壮性)、高效性、简明性、易维护性、易移植性、安全性、可适应性等。微软公司为达到这些目标对市场作了大量的调研,并尽可能地提高其技术来实现这些目标。在Windows 2000的设计中,微软公司把握的总原则是用市场需求驱动设计目标,实现这些需求作为设计目标。

Windows 2000的系统体系结构是怎样的?
答:Windows 2000的系统结构如图7-1所示。根据下图,可以发现系统的体系结构是分层的模块系统,主要的层次有硬件抽象层(HAL)、内核和大量的子系统集合等,除了各个子系统都在用户模式下运行外其他三个都运行在保护模式下。
图7-1 Windows 2000的系统结构

Windows 2000提供了哪些常用的系统机制?
答:Windows 2000的系统的工作由四种系统机制来完成,它们是陷阱调度、执行体对象管理器、同步、本地过程调用。

Windows 2000中的系统核心构成如何?
答:Windows 2000的内核是由用户态组件和核心态组件构成的。
用户态组件中,系统支持进程(system support process),它不是Windows 2000的服务,不由服务控制器启动;服务进程(service process),它是Windows 2000的服务,由服务控制器启动;环境子系统(environment subsystems),它们向应用程序提供操作系统功能调用接口,包括Win32、POSIX和OS/2接口;应用程序(user applications),支持五种类型Win32、Windows 3.1、MS-DOS、POSIX 或OS/2的应用程序在系统中运行;子系统动态链接库用于调用层转换和映射。
核心态组件中,内核(kernel,或核心)包含了最低级的操作系统功能,例如线程调度、中断和异常调度、多处理器同步等。同时它也提供了执行体(Executive)用来实现高级结构的一组例程和基本对象;执行体包含基本的操作系统服务,例如主存管理器、进程和线程管理、安全控制、I/O以及进程间的通信等。硬件抽象层(HAL, Hardware Abstraction Layer)将内核、设备驱动程序以及执行体同硬件分隔开来,实现硬件映射的功能。设备驱动程序(Device Drivers)包括文件系统和硬件设备驱动程序等,其中硬件设备驱动程序将用户的I/O函数调用转换为对特定硬件设备的I/O请求。窗口和图形系统包含了实现图形用户界面(GUI,Graphical User Interface)的基本函数。

什么是硬件抽象层(HAL)?
答:硬件抽象层(HAL)
这是Windows 2000的重要部分,是实际硬件与Windows 2000抽象计算机描述的接口层和功能映射层,它隐藏各种与硬件有关的细节,例如I/O接口、中断控制器以及多处理器通信机制等,实现多种硬件平台上的可移植性。硬件抽象层给出虚拟机接口,可供内核、执行体和设备驱动程序使用。这样设计的优点是只需提供每个设备驱动程序的一个版本就可运行在所有的硬件平台上,不必移植驱动程序代码。硬件抽象层也支持对称多处理,并为了提升性能允许图形驱动程序和I/O驱动程序直接访问操纵硬件。

什么是执行体?
答:执行体
在内核和设备驱动程序之上的部分是操作系统的上层部分,称为执行体。执行体由C语言编写的,与硬件体系结构无关,从而只需少量改动就可移植到新机器上。执行体由对象管理程序、I/O管理程序、进程管理程序、虚拟内存管理程序、安全管理程序、即插即用管理程序和本地过程调用管理程序多个部件组成。

Windows 2000中的中断处理过程是怎样的?
答:中断分为两类:硬件中断和软件中断。如图7-6所示。
在Windows 2000下的硬件中断处理过程是:首先,保存计算机的状态并禁用中断;然后,调用中断调度程序;提高处理器的IRQL到中断源的级别;再重新启用中断;在中断分配表中查找处理特定中断的例程;服务例程执行;降低处理器的IRQL到该中断发生前的级别;加载保存的机器状态;最后,中断返回。
在Windows 2000下对应的软件中断处理过程是:首先,由定时器产生一个中断信号延迟过程调用(DPC,Deferred Procedure Call),将等待定时器的线程释放;当中断优先级低于DPC / dispatch的优先级时,延迟过程调用(DPC,Deferred Procedure Call)中断产生;此时在延迟过程调用(DPC,Deferred Procedure Call)中断之后,系统控制权交给调度程序;调度程序执行延迟过程调用(DPC,Deferred Procedure Call)队列中的每一个例程。这一过程请参考图7-7所示的软件中断的处理情况。

图7-6 中断调度的优先级
图7-7 软件中断的处理——延迟过程调用

Windows 2000中的异常调度是的内容是什么?
答:异常调度是指在Windows 2000中用于处理由硬件或软件产生的异常事件,异常直接由运行程序的执行所产生。除了那些可由陷阱处理程序解决的简单异常外,所有异常都是由异常调度程序接管。其处理的过程是:先进行结构化异常处理,调用基于框架的异常处理程序,运行异常调度过程。图7-8给出了异常调度程序处理软件或硬件产生的异常事件。
图7-8 异常调度程序处理软件或硬件产生的异常事件

Windows 2000的同步机制如何工作的?
答:同步(Synchronization)
在Windows 2000中同步包括自旋锁(Spin lock)、内核调度程序对象(Kernel Dispatcher Objects)。这里所说的同步机制,是由内核同步和执行体同步构成。
内核同步的操作对象是内核的临界区,该区是修改共用数据结构的代码段,该临界区工作中最大的问题是中断,解决的方法一般采用自旋锁,使用临界区的管理避免产生不必要的影响。为说明这一问题请参考图7-10所描述的内容。
图7-10 内核同步

线程作为重要的运行单位在Windows 2000中的组成是怎样的?其在系统中的状态是哪些?
答:xx
Windows 2000的线程是内核线程,系统的处理机调度对象为线程。Windows 2000把线程状态分成下面七种状态:①、创建和初始化线程对象;②、等待运行的就绪状态;③、优先级最高的就绪线程转为备用状态,即下一个要运行的线程,要说明的是在多处理器系统中,每个处理器上只能有一个线程处于备用状态;④、运行态,是指线程处于处理器上运行,直至出现被更高优先级线程抢占、终止、时间时间片用光、调用用于I/O等阻塞式系统调用为止的状态;⑤、等待信号的等待态;⑥、为等待执行时所需资源所处的转换态;⑦、执行完成后所处的终止态。

Windows 2000的存储管理的组成部分有哪些?
答:Windows 2000系统中存储器管理由一组执行体系统服务程序,一个转换无效和访问错误陷阱处理程序和六个关键的组件组成。
转换无效和访问错误陷阱处理程序用于解决硬件监测到的主存管理异常,并代表进程将虚拟页面装入主存。六个关键组件有:工作集管理器、进程/堆栈交换程序、已修改页面写入器、映射页面写入器、废弃段线程、零页线程。

Windows 2000的存储管理的分配方式是什么?
答:Windows 2000的主存分配是使用三组函数实现:以页为单位的虚拟主存函数(Virtualxxx);主存映射文件函数( CreateFileMapping , MapViewOfFile);堆函数(Heapxxx )。
Windows 2000对系统主存的分配主要采用两种方式:
非分页缓冲池方式由系统虚拟地址组成,它们长期驻留在物理主存中,在任何时候都可以被访问到(从任何IRQL级和任何进程上下文),而不会发生页错误。
分页缓冲池方式是指系统中可以被分配的页与系统空间中虚拟主存组成的一个区域。执行体系统服务程序不必从延迟过程调用(DPC,Deferred Procedure Call)或更高一级去访问主存的设备驱动程序,可以使用分页缓冲池。

在Windows 2000的存储管理中的存储保护机制是怎样工作的?
答:在Windows 2000中,所有系统范围内的核心态组件使用的数据结构和主存缓冲池只能在核心态下被访问。每个进程有一个独立、私有的地址空间,禁止其它进程的线程访问。主存保护的支持提供了主存保护措施(如读/写,只读等)。 共享主存区域对象具有标准的Windows 2000存取控制表(ACLs)。系统主存的地址变换机制如图7-12所示。
图7-12 地址变换机制

Windows 2000的存储管理的虚拟存储管理技术的实现是怎样的?
答:虚拟存储管理程序使用32位地址,每个进程有4GB的虚拟地址空间。如图7-13虚拟地址空间所示。
图7-13 虚拟地址空间

高地址部分保留给系统使用,低地址部分是用户存储区,它们各占2GB。用户存储区可被用户态和核心态线程存取,并对每个进程都是惟一的;系统存储区只能供核心态线程存取,且对所有进程都相同。
在Windows 2000中,采用请求分页的虚拟存储管理技术,页帧和页面的大小均为4KB。Windows 2000的地址机构不同于传统的页面地址转换机构,它采用二级页表结构。第1级称页目录,每个进程有一个页目录。每个页目录均包含1024个表目,每个表目指向第二级页表的起始地址(即每个页表的地址)。第2级页表中也包含1024个表目,每个表目指向实际的页帧,每个表目的大小是4B,每个第2级页表均为4KB大小,恰好占一个页帧。当给定虚拟地址后,这个地址被自动分为三部分:页内位移(第0—11位,共12位),页表位移(第12—21位,共10位),目录位移(第22—31位,共10位)。地址转换机构将页目录地址与目录位移拼接成页目录中表目所在地址,该表目中包含相应页表地址,即页表所在页帧号;然后将此页表地址与页表位移拼接成页表中目标表目地址,其中包含该页所在的页帧号;最后将此页帧号与页内位移拼接成内存的物理地址,从而得到访问内存的物理地址。请参见下图7-14。
图7-14 二级页表地址转换机构

应用程序在访问Windows系统中的动态链接库(DLL)时的基本工作过程是怎样的?
答:Windows在连接生成应用程序时,如果使用动态链接库函数,连接器并不拷贝DLL中的任何代码,它只是将引入库中指定所需函数在DLL中位置的信息拷贝在应用程序模块中,当应用程序运行时,这些定位信息在可执行应用程序和动态链接库之间建立动态连接。
应用程序要访问动态链接库函数,它应该做下面三件事:建立库函数原型,调用库函数,引入库函数。建立库函数原型一般通过在C语言源文件中包含动态链接库的头文件解决。应用程序调用DLL中的引出函数还要在应用程序中对其进行引入,一般有三种方法:(1)、连接时隐式引入,(2)、连接时显式引入,(3)、 运行时动态引入。

为什么要在Windows 2000中引入页面文件?
答:对于庞大的Windows操作系统以及功能越来越强大、占用系统内存资源也越来越多的各种软件来说,内存资源远远不能满足其要求。Windows使用的页面文件来解决这一问题,其功能相当于虚拟内存。其实现的原理是将一部分硬盘空间设置为虚拟内存,从而扩大了计算机的可用“内存”空间来满足程序的运行要求。

Windows 2000的“磁盘管理器”具有哪些功能?
答:Windows 2000在磁盘管理方面提供了强大的功能。Windows 2000的磁盘管理任务是以一组磁盘管理实用程序的形式提供给用户的,它们位于“计算机管理”控制台中,包括查错程序、磁盘碎片整理程序、磁盘整理程序等。Windows 2000的磁盘管理支持基本磁盘和动态磁盘。基本磁盘是包括主分区、扩展分区或逻辑驱动器的物理磁盘。基本磁盘也包括使用Windows NT 4.0或以前版创建的跨卷(卷设置)、镜像卷(镜像设置)、带卷(带设置)和RAID—5卷(带奇偶检测的带设置)。可以使用MS—DOS访问基本磁盘。动态磁盘是含有使用磁盘管理创建动态卷的物理磁盘。动态磁盘不能含有分区和逻辑驱动器,也不能使用MS—DOS访问。

解释分区、卷的概念,并说明它们之间的关系?
答:Windows 2000磁盘管理功能经常涉及到的概念和术语:
分区:是物理磁盘的一部分,其作用如同一个物理分隔单元。分区通常指主分区或扩展分区。
卷:是格式化后由文件系统使用的分区或分区集合。可以为Windows 2000的卷指定驱动器名,并使用它组织目录和文件。
在动态磁盘上,存储被分为卷,而不是分区。用户可以在任何时候将基本存储更新为动态存储。当更新为动态存储时,需要将现有的分区转换为卷。表7-5 显示了用户应如何将分区转换为卷。
表7-5 分区转换为对应的卷
基本磁盘组织 动态磁盘组织
分区 卷
系统和启动分区 系统和启动卷
活动分区 活动卷
扩展分区 卷和未分配空间
逻辑驱动器 简单卷
卷标设置 跨卷
带设置 带卷
镜像设置 镜像卷
在用户了解了分区和卷的区别,以及将分区转换为卷时两个不同磁盘组织的对应关系后,便可以在需要时将基本磁盘更新到动态磁盘。

Windows 2000设备驱动程序的基本组成是哪些?
答:Windows 2000设备驱动程序由用户模式驱动程序和核心模式驱动程序组成。
用户模式驱动程序包括:Win32多媒体驱动、虚拟设备驱动程序VDD、其他保护子系统的驱动程序。
核心模式驱动程序包括:PnP驱动程序、Windows驱动程序模型(WDM,Windows Drivers Model)驱动程序、小端口驱动程序、文件系统驱动程序、遗留设备驱动程序。

Windows 2000支持哪些文件系统?
答:在Windows 2000中,常见的文件系统有如下的几个:
(1) FAT(File Allocation Table,文件分配表)文件系统
(2) FAT32文件系统
(3) NTFS (New Technology File System,NT文件系统)
(4) UDF(Universal Disk Format,通用磁盘格式)
(5) CDFS(CDROM File system,只读光盘文件系统)

在WINDOWS 2000 中NTFS、FAT和CDFS 3种文件系统可以同时存在吗?
答:不同的分区上可以使不同的文件系统。

在WINDOWS 2000中推荐采用NTFS文件系统的理由是什么?
答:Windows 2000中使用NTFS有许多优点,比FAT和FAT32具有更多扩展的功能。NTFS具有众多优点,这主要是因为它在磁盘上独特的实现方法可以更好地划分磁盘,组织文件与目录,存储文件属性与数据,压缩文件数据等。

NTFS磁盘结构的组成内容是怎样的?
答:NTFS磁盘结构的组成内容有:卷,簇,主控文件表,文件引用号,文件记录,文件名称,常驻属性与非常驻属性,索引,数据压缩。

习题八

试说说Linux系统的历史和特点?
答:1987年,由Andrew S. Tanenbaum开发了MINIX操作系统。MINIX虽然很好,但只是一个用于教学目的简单操作系统,而不是一个强有力的实用操作系统。1991年,芬兰赫尔辛基大学计算机科学系二年级学生Linus Benedict Torvalds,开始酝酿并着手编制自己的操作系统。Linux操作系统是UNIX操作系统的一种克隆系统。它诞生于1991年的10月5日。
Linux功能强大而全面,目前从2.4以后的内核源代码就有上百万行之多。如果我们能通读所有的代码,也许可以发现如下相关特点。
与UNIX兼容。
自由软件和源码公开。
性能高且安全性强。
便于定制和再开发。
强大的互操作性。
全面的多任务和真正的32位及64位的操作系统。

Linux内核有哪两种版本?Linux内核版本号的组成是如何的?
答:Linux有两种版本,一个是内核(Kernel)版本,另一个是发行(Distribution)版本。
内核版本主要是Linux内核,由Linus等人在不断地开发和推出新的内核。Linux内核的官方版本由Linus Torvalds本人维护。第一个版本的内核是0.01。内核版本的序号由三部分数字构成,其形式为:“主版本号.次版本号.对当前版本的修订次数”。前两者构成当前内核版本号。另外约定,次版本号为奇数时,表示该版本中加入新内容,但不一定很稳定,相当于测试版本;次版本号为偶数时,表示为一个可以使用的稳定版本。到本书编写时为止最新稳定内核版本号为3.0.4。一些组织或厂家,将Linux系统的内核与外围实用程序(Utilities)软件和文档包装起来,并提供一些系统安装界面和系统配置、设定与管理工具,就构成了一种发行版本(distribution)。第一个正式的发行版本名字是Slackware。相对于Linux操作系统内核版本,发行版本的版本号随着发布者的不同而不同,与Linux系统内核的版本号是相对独立的。目前最流行的几个正式版本有:SUSELinux、RedHat、Fedora、Ubuntu、TurboLinux、Slackware、OpenLinux、Debian。其中Ubuntu表现最为稳定。国内的Linux产品有中科红旗Linux等。

Linux具有的特点是哪些?
答:Linux功能强大而全面,目前从2.4以后的内核源代码就有上百万行之多。如果我们能通读所有的代码,也许可以发现如下相关特点。
与UNIX兼容。
自由软件和源码公开。
性能高且安全性强。
便于定制和再开发。
强大的互操作性。
全面的多任务和真正的32位及64位的操作系统。

Linux操作系统内核的内核模式是怎样的?
答:从结构上看,早期的Linux操作系统内核是采用单内核模式。由于不断的开发和更新内核,在设计Linux的内核模块系统时将微内核的许多优点引入到Linux的单内核设计中,所以Linux内核是微内核和单一内核的混合产物。

试说说Linux内核构成的5个主要模块的作用及功能为何?
答:Linux内核主要由5个模块构成,它们分别是:进程调度模块、内存管理模块、文件系统模块、进程间通信模块和网络接口模块。如图8-1 Linux内核五个模块之间的依赖关系,图中实线表示数据流,虚线表示控制或信号流。

图8-1 Linux内核五个模块之间的依赖关系
Linux系统进程控制系统由进程调度模块和进程间通信模块构成,用于进程管理、进程同步、进程通信、进程调度等。
Linux系统内存管理模块控制内存分配与回收。系统采用交换和请求式分页两种策略管理内存。
Linux系统的文件系统模块管理文件、分配文件空间、管理空闲空间、控制对文件的访问,且为用户检索数据。进程通过一组特定的系统调用(如open,close,read,write,chmod等)与文件系统交互作用。Linux系统使用了虚拟文件系统(VFS)来支持多种不同的文件系统,只要每个文件系统都要提供给VFS一个相同的接口。这使得所有的文件系统对系统内核和系统中的程序来说都相同,因为看到的都是VFS的接口。从而通过VFS层,允许用户同时在系统中透明地安装多个不同的文件系统。
Linux系统支持字符设备、块设备和网络设备三种类型的硬件设备。其中,字符设备和块设备通常组织为特殊的设备文件,这样管理、控制和访问起来就同访问普通文件一样。网络设备通过网络接口模块实现控制和访问。Linux系统和设备驱动程序之间使用标准的交互接口。从而使内核使用同样的方法使用完全不同的各种设备。

试说说早期Linux系统的启动过程?
答:Linux的启动过程是,当PC机的电源打开后,80x86结构的CPU将自动进入实模式,并从地址0xFFFF0开始自动执行程序代码。PC机的BIOS将执行某些系统的检测,并在物理地址0处开始初始化中断向量。此后,它将可启动设备(启动设备通常是软驱或是硬盘)的第一个扇区(磁盘引导扇区,512字节)读入内存绝对地址0x7C00处,并跳转到这个地方让CPU执行代码。Linux的最前面部分(boot/bootsect.s)是用8086汇编语言编写的程序,它将由BIOS读入到内存绝对地址0x7C00(31KB)处,当它被执行时就会把自己移到绝对地址0x90000(576KB)处,并把启动设备中后2KB字节代码(boot/setup.s)读入到内存0x90200处,而内核的其它部分(system模块)则被读入到从地址0x10000开始处,因为当时(早期的linux版本)system模块的长度不会超过0x80000字节大小(即512KB),所以它不会覆盖在0x90000处开始的bootsect和setup模块。随后将system模块移动到内存起始处,这样system模块中代码的地址也即等于实际的物理地址。便于对内核代码和数据的操作。在系统加载期间将显示信息”Loading … “。然后控制权将传递给boot/setup.s中的代码,这是另一个实模式汇编语言程序。启动部分识别主机的某些特性以及VGA卡的类型等。如果需要,它会要求用户为控制台选择显示模式。然后执行源代码boot/head.S,进入保护模式并跳转至系统的余下部分。此时所有32位运行方式的设置启动被完成:IDT(中断描述符表)、GDT(全局描述符表)以及LDT(本地描述符表)被加载,处理器和协处理器也已确认,分页工作也设置好了;注意如果在上述的任何一步中出了错,计算机就会死锁。最终调用init/main.c中的main()程序。实现操作系统完全运转。

Linux中断是指什么?中断的分类如何?Linux系统是如何处理中断的?
答:所谓中断是指CPU对系统发生的某个事件做出的一种反应,CPU暂停正在执行的程序,保留现场后自动地转去执行相应的处理程序,处理完该事件后再返回断点继续执行被“打断”的程序。
Linux中断可分为三类,第一类是由CPU外部引起的,称作中断,如I/O中断、时钟中断、控制台中断等。第二类是来自CPU的内部事件或程序执行中的事件引起的过程,称作异常,如由于CPU本身故障(电源电压低于105V或频率在47~63Hz之外)、程序故障(非法操作码、地址越界、浮点溢出等)等引起的过程。第三类由于在程序中使用了请求系统服务的系统调用而引发的过程,称作“陷入”(trap,或者陷阱)。前两类通常都称作中断,它们的产生往往是无意、被动的,而陷入是有意和主动的。
中断处理一般分为中断响应和中断处理两个步骤。中断响应由硬件实施,中断处理主要由软件实施。
1.中断响应
对中断请求的整个处理过程是由硬件和软件结合起来而形成的一套中断机构实施的。发生中断时,CPU暂停执行当前的程序,而转去处理中断。这个由硬件对中断请求作出反应的过程,称为中断响应。一般说来,中断响应顺序执行下述三步动作:
◆中止当前程序的执行;
◆保存原程序的断点信息(主要是程序计数器PC和程序状态寄存器PS的内容);
◆从中断控制器取出中断向量,转到相应的处理程序。
通常CPU在执行完一条指令后,立即检查有无中断请求,如果有,则立即做出响应。
如果当前CPU的执行优先级低于中断的优先级,那么它就中止对当前程序下条指令的执行,接受该中断,并提升处理器的执行级别(一般与中断优先级相同),以便在CPU处理当前中断时,能屏蔽其它同级的或低级的中断,然后保存断点现场信息,通过取得的中断向量转到相应的中断处理程序的入口。
2.中断处理
CPU从中断控制器取得中断向量,然后根据具体的中断向量从中断向量表IDT中找到相应的表项,该表项应是一个中断门。于是,CPU就根据中断门的设置而到达了该通道的总服务程序的入口。
内核对中断处理的顺序主要由以下动作完成:
◆保存正在运行进程的各寄存器的内容,把它们放入内核栈的新帧页中。
◆确定“中断源”或核查中断发生,识别中断的类型(如时钟中断或盘中断)和中断的设备号(如哪个磁盘引起的中断)。系统接到中断后,就从机器那里得到一个中断号,它是检索中断向量表的位移。中断向量因机器而异,但通常都包括相应中断处理程序入口地址和中断处理时处理器的状态字。
◆内核调用中断处理程序,对中断进行处理。
◆中断处理完成并返回。中断处理程序执行完以后,内核便执行与机器相关的特定指令序列,恢复中断时寄存器内容和执行内核栈退栈,进程回到用户态。如果设置了重调度标志,则在本进程返回到用户态时做进程调度。

什么是系统调用?其作用是什么?
答:所谓系统调用,就是内核提供的、功能十分强大的一系列的函数。这些系统调用是在内核中实现的,再通过一定的方式把系统调用给用户,一般都通过门(gate)陷入(trap)实现。系统调用是用户程序和内核交互的接口。在Linux kernel 2.6.5的内核里,有280多个系统调用。
系统调用在Linux系统中发挥着巨大的作用,如果没有系统调用,那么应用程序就失去了内核的支持。系统调用是用户接口在内核中的实现,如果没有系统调用,用户就不能利用内核。

试说说系统调用的实现及调用过程?
答:系统调用对于内核来说就相当于函数。我们的关键问题是从用户模式到内核模式的转换、堆栈的切换以及参数的传递是如何实现的呢?
结合arch/i386/kernel/entry.S的内核源代码进行分析。(限于篇幅请读者自行找到对应的文件。下文中情况相同。)。这段代码里定义了两个非常重要的宏,即SAVE_ALL和RESTORE_ALL。SAVE_ALL先保存用户模式的寄存器和堆栈信息,然后切换到内核模式。宏__SWITCH_KERNELSPACE实现地址空间的转换,RESTORE_ALL的过程与SAVE_ALL的过程正好相反。
在内核源代码里有一个系统调用表(在entry.S的文件里面),系统调用使用sys_call_table函数来指向。在Linux kernel 2.6.5的内核里,有280多个系统调用,这些系统调用的名称全部在这个系统调用表里。从glibc的函数到系统调用还有一个很重要的环节就是系统调用号。系统调用号的定义在include/asm-i386/unistd.h里。 system_call函数根据用户传来的系统调用号,在系统调用表里找到对应的系统调用再执行。每一个系统调用号都对应有一个系统调用。接下来就是系统调用宏的展开。
当发生调用时,函数中的name会被系统调用名所代替。然后调用system_call。这个过程里包含了系统调用的初始化,系统调用的初始化源代码在:arch/i386/kernel/traps.c中。每当用户执行int 0x80时,系统进行中断处理,把控制权交给内核的system_call。

整个系统调用的过程可以总结如下:
(1).执行用户程序(如:fork)
(2).根据glibc中的函数实现,取得系统调用号并执行int $0x80产生中断。
(3).进行地址空间的转换和堆栈的切换,执行SAVE_ALL。(进行内核模式)
(4).进行中断处理,根据系统调用表调用内核函数。
(5).执行内核函数。
(6).执行RESTORE_ALL并返回用户模式。

进程管理是Linux操作系统内核的主要内容之一,它对整个操作系统的执行效率至关重要。
试说说你对操作系统的进程管理机制的理解和掌握的情况,并谈谈学习现代操作系统的体会。
答:操作系统的重要任务之一是管理计算机的软、硬件资源。现代操作系统的主要特点在于程序的并发执行,由此引出系统的资源被共享和用户随机使用系统。因而操作系统最为核心的概念就是进程:即正在运行的程序。操作系统借助于进程来管理计算机的软、硬件资源,支持多任务的并发。操作系统的其它内容都是围绕进程展开的。所以进程管理是Linux操作系统内核的主要内容之一,它对整个操作系统的执行效率至关重要。

Linux的进程和线程有什么不同,有什么相同,它们如何区别?
答:进程是一个动态的实体,是一个可并发执行的程序在一个数据集合上的运行过程,它是一个正在执行的程序,是操作系统分配资源的基本单位。进程不仅包含指令和数据也包含程序计数器和所有CPU寄存器的值,同时它的堆栈中存储着如子程序参数,返回地址以及变量之类的临时数据。
从概念上来说,线程是同一个进程中独立的执行上下文,它们为单一进程提供了一种同时处理多件事情的方法。同一线程组中的线程共享它们的全局变量并有相同的堆(heap),因此使用malloc给线程组中的一个线程分配的内存可以被该线程组中的其它线程读写。但是它们拥有不同的堆栈(它们的局部变量是不共享的),并可以同时在进程代码不同的地方运行。
线程只是偶然的共享相同的全局内存空间的进程(Linux内核使用的观点)。
在引入了线程以后,为了与传统的进程相区分,把具有线程的进程实体称之为任务(task)。
线程是比进程粒度更细的调度单位,在多CPU系统中,同一个任务中的若干个线程是可以并行执行的;而在单CPU系统中,线程仍是并发执行的,一个线程也是处在走走停停的不断变化的状态中。
线程是和进程紧密相关的概念。一般来说,Linux系统中的进程应具有一段可执行的程序,专用的系统栈空间,私有的“进程控制块”(即task_struct数据结构)和独立的存储空间。然而,Linux系统中的线程只具备前三个组成部分,缺省自己的存储空间。
线程可以看作进程中指令的不同执行路线。Linux系统支持内核空间的多线程,但它与大多数操作系统不同。因为大多数操作系统单独定义线程,而Linux则把线程定义为进程的“执行上下文”。

什么是Linux系统的任务?
答:在引入了线程以后,为了与传统的进程相区分,把具有线程的进程实体称之为任务(task)。

Linux用task_struct数据结构来表示每个进程,谈谈你对设计这个数据结构的是如何理解的?
答:Linux用task_struct数据结构来表示每个进程,在Linux中任务与进程表示的意义是一样的。系统维护一个名为task的数组,task包含指向系统中所有进程的task_struct结构的指针。创建新进程时,Linux将从系统内存中分配一个task_struct结构并将其加入task数组。当前运行进程的结构用current指针来指示。
Xxx

task_struct数据结构由几类信息组成,它们的主要功能和作用是什么?
答:通过对上述源代码的分析,我们可以发现尽管task_struct数据结构庞大而复杂,但可以归为如下几类:
1.进程的状态信息(State),是指进程在执行过程中会根据环境来改变进程的状态,Linux进程有以下状态:
Running 进程处于运行(它是系统的当前进程)或者准备运行状态(它在等待系统将CPU分配给它)。
Waiting 进程在等待一个事件或者资源。Linux将等待进程分成两类;可中断与不可中断。可中断等待进程可以被信号中断;不可中断等待进程是由于硬件原因而等待,例如进程打开某个设备文件,在得到设备的回应前处于等待状态,因此在任何情况下都不可中断。
Stopped 进程被停止,通常是通过接收一个信号。正在被调试的进程可以处于停止状态。
Zombie 这是因为某些原因而被终止的进程,但是在task数据中仍然保留task_struct结构。它像一个已经死亡的进程。
2.调度信息(Scheduling Information)是指Linux调度进程所需要的信息,包括进程的类型(普通或实时)和优先级,计数器中记录允许进程执行的时间量。
3.进程标识信息(Identifiers)是因为系统中每个进程都有进程标志。进程标志并不是task数组的索引,它仅仅是个数字。每个进程还有一个用户与组标志,它们用来控制进程对系统中文件和设备的存取权限。
4.进程的通信信息(Inter-Process Communication)在Linux中主要有:Linux支持经典的Unix IPC机制,如信号,管道和命名管道以及System V中IPC机制,包括共享内存,信号量和消息队列。
5.链接信息(Links)用于描述Linux系统中所有进程的相互联系性质。除了初始化进程外,所有进程都有一个父进程。新进程不是被创建,而是被复制,都是从以前的进程克隆而来。每个进程对应的task_struct结构中包含有指向其父进程和兄弟进程(具有相同父进程的进程)以及子进程的指针。
系统中所有进程都用一个双向链表连接起来,而它们的根是init进程的task_struct数据结构。这个链表被Linux核心用来寻找系统中所有进程,它为ps或者kill命令提供了支持。
6.时间和定时器信息(Times and Timers)。核心需要记录进程的创建时间以及在其生命期中消耗的CPU时间。时钟每跳动一次,核心就要更新保存在jiffies变量中,记录进程在系统和用户模式下消耗的时间量。Linux支持与进程相关的interval定时器,进程可以通过系统调用来设定定时器以便在定时器到时后向它发送信号。这些定时器可以是一次性的或者周期性的。
7.有关文件系统的信息(File system)。进程可以自由地打开或关闭文件,进程的task_struct结构中包含一个指向每个打开文件描述符的指针以及指向两个VFS inode的指针。每个VFS inode唯一地标记文件中的一个目录或者文件,同时还对底层文件系统提供统一的接口。这两个指针,一个指向进程的根目录,另一个指向其当前或者pwd目录。这两个VFS inode包含一个count域,当多个进程引用它们时,它的值将增加。这就是为什么你不能删除进程当前目录或者其子目录的原因。
8.虚拟内存信息(Virtual memory)。多数进程都有一些虚拟内存(核心线程和后台进程没有),Linux核心必须跟踪虚拟内存与系统物理内存的映射关系。
9.进程上下文信息(Processor Specific Context)。进程可以认为是系统当前状态的总和。进程运行时,它将使用处理器的寄存器以及堆栈等等。进程被挂起时,进程的上下文中所有与CPU相关的状态必须保存在它的task_struct结构内。当调度器重新调度该进程时,所有上下文被重新设定。
10.其它信息。Linux支持SMP多CPU结构,在task_struct中有相应的描述信息。此外还包括资源使用,进程终止信号,描述可执行的文件格式的信息等等。
另外,在Linux系统中,每个进程都有一个系统栈,用来保存中断现场信息和进程进入内核模式后执行子程序(函数)嵌套调用的返回现场信息。每一个进程系统栈的数据结构与task_struct数据结构之间存在紧密联系也因而二者在物理存储空间中也连在一起。

在系统中,通过fork创建了子进程后,系统是如何让子进程来运行的?
答:子进程被创建后,通常处于“就绪态”,以后被调度选中才可运行。由于创建子进程过程中,是把父进程的映像复制给子进程,所以子进程开始执行的入口地址就是父进程调用fork( )系统调用建立子进程映像时的返回地址,此时二者的映像基本相同。
如果子进程不改变其映像,就必然重复父进程的过程。为此,要改变子进程的映像,使其执行另外的特定程序(如命令所对应的程序)。
改换进程映像的工作很复杂,是由系统调用execve( )实现的,它用一个可执行文件的副本来覆盖该进程的内存空间。

信号是什么?其发展历程是怎样的?有哪些常见的种类?
答:信号(Signal)是一种软件机制,它报告与程序相关的软件和硬件事件。主要有同步事件(或称信号异常)和异步事件(即异步I/O的完成或从另一个进程来的kill())。
信号是由UNIX System V(一个重要的UNIX版本)首先引入的,但不够可靠。BSD (Berkely Software Distribution)4.2解决了其中的许多问题。BSD4.3进一步强化和改善了信号机制,但System V和BSD的信号借口不完全兼容。目前所有的Linux内核的信号机制都和Posix兼容。
在Linux上可以实现任意多的信号,其中包括实时信号和普通信号。有关的Linux系统进程信号说明请参考表8-4。
表8-4 Linux系统进程常见进程信号
标号 名称 说明 默认操作
1 SIGHUP (Hangup)当你不再控制终端时内核会产生该信号,或者当你关闭Xterm或断开modem。由于后台程序没有控制的终端,因而它们常用SIGUP来发出需要重新读取其配置文件的信号。 (Abort)挂断控制中断或进程。
2 SIGINT (Interrupt)来自键盘的终端。通常终端驱动程序会将其与^C绑定。 (Abort)终止程序。
3 SIGQUIT (Quit)来自键盘的终端。通常终端驱动程序会将其与^\绑定。 (Dump)程序被终止并产生dump core文件。
4 SIGILL (Illegal Instruction)程序出错或者执行了一个非法的操作指令。 (Dump)程序被终止并产生dump core文件。
5 SIGTRAP (Breakpoint/Trace Trap)调试用,跟踪断点。
6 SIGABRT (Abort)放弃执行,异常结束。 (Dump)程序被终止并产生dump core文件。
6 SIGIOT (IO Trap)同SIGABRT (Dump)程序被终止并产生dump core文件。
7 SIGUNUSED (Unused)没有使用。
8 SIGFPE (Floating Point Exception)浮点异常。 (Dump)程序被终止并产生dump core文件。
9 SIGKILL (Kill)程序被终止。该信号不能被捕获或者被忽略。想立刻终止一个进程,就发送信号9。注意程序将没有任何机会做清理工作。 (Abort)程序被终止。
10 SIGUSR1 (User defined Signal 1)用户定义的信号。 (Abort)进程被终止。
11 SIGSEGV (Segmentation Violation)当程序引用无效的内存时会产生此信号。比如:寻址没有映射的内存;寻址未许可的内存。 (Dump)程序被终止并产生dump core文件。
12 SIGUSR2 (User defined Signal 2)保留给用户程序用于IPC或其它目的。 (Abort)进程被终止。
13 SIGPIPE (Pipe)当程序向一个套接字或管道写时由于没有读者而产生该信号。 (Abort)进程被终止。
14 SIGALRM (Alarm)该信号会在用户调用alarm系统调用所设置的延迟秒数到后产生。该信号常用判别于系统调用超时。 (Abort)进程被终止。
15 SIGTERM (Terminate)用于和善地要求一个程序终止。它是kill的默认信号。与SIGKILL不同,该信号能被捕获,这样就能在退出运行前做清理工作。 (Abort)进程被终止。
16 SIGSTKFLT (Stack fault on coprocessor)协处理器堆栈错误。 (Abort)进程被终止。
17 SIGCHLD (Child)父进程发出。停止或终止子进程。可改变其含义挪作它用。 (Ignore)子进程停止或结束。
18 SIGCONT (Continue)该信号致使被SIGSTOP停止的进程恢复运行。可以被捕获。 (Continue)恢复进程的执行。
19 SIGSTOP (Stop)停止进程的运行。该信号不可被捕获或忽略。 (Stop)停止进程运行。
20 SIGTSTP (Terminal Stop)向终端发送停止键序列。该信号可以被捕获或忽略。 (Stop)停止进程运行。
21 SIGTTIN (Terminal Input on Background)后台进程试图从一个不再被控制的终端上读取数据,此时该进程将被停止,直到收到SIGCONT信号。该信号可以被捕获或忽略。 (Stop)停止进程运行。
22 SIGTTOU (TTY Output on Background)后台进程试图向一个不再被控制的终端上输出数据,此时该进程将被停止,直到收到SIGCONT信号。该信号可被捕获或忽略。 (Stop)停止进程运行。
其中,除了SIGSTOP(进程终止执行)和SIGKILL(进程退出)两个信号外,进程可以忽略其余的信号。

信号相关的系统调用有哪些?它们的作用各是什么?
答:信号事件的发生有两个来源:硬件来源(比如我们按下了键盘或者其它硬件故障);软件来源,最常用发送信号的系统函数是kill,raise,alarm和setitimer以及sigqueue函数,软件来源还包括一些非法运算等操作。发送信号的主要函数有:kill(),raise(),sigqueue(),alarm(),setitimer()以及abort()。
有关的Linux系统进程信号说明请参考表8-4。(习题17答案)

信号有哪些特点?
答:在Linux系统中,信号的主要用途是:①、事件警报。②、进程同步。③、进程间通信。④、作业控制。但是信号的主要缺点也很明显:①、信号的捕获开销大。②信号并不能提供完全的通信机制(原因是多样的:无返回值,不建立连接,BASE POSIX语法很弱,系统未要求报告有多个相同的信号的到达,系统可能按实现有关的顺序提交了多个挂起的信号等)。

Linux系统中的管道是什么?
答:管道是一个先进先出,大小固定的缓冲区,容量为1页(4Kbyte),用于两个进程之间的单向数据传递。当管道有空间时,写者进程把数据送入管道,否则将被阻塞;如果管道中没有数据或读者进程需要的数据多于其中的数据,读者进程会被阻塞,否则执行读者进程的请求。整个过程由操作系统监控完成,互斥地访问管道。当传送的数据量大于管道的容量时,可以通过同步机制分次传送数据。

Linux系统中的消息队列是什么?
答:Linux系统也支持System V的进程间通信(IPC)达到机制,包括消息队列,信号量和共享存储。所有的IPC对象在Linux中有一个公共的ipc_perm结构,它含有进程拥有者,创建者和组标志符,以及对此对象(拥有者,组及其它)的存取模式以及IPC对象键。
ipc_perm,此结构描述对一个System V IPC对象的存取权限。
struct ipc_perm {
key_t key;
ushort uid; /* owner euid and egid */
ushort gid;
ushort cuid; /* creator euid and egid */
ushort cgid;
ushort mode; /* access modes see mode flags below */
ushort seq; /* sequence number */
};
消息是按一定格式封装起来的信息。每个进程都有一个与之关联的消息队列,接收进程按时间顺序或消息类型从消息队列取走消息。如果进程向一个满队列发送消息或从一个空队列取走消息都会被阻塞。
Linux系统维护着一个msgque消息队列链表,其中每个元素指向一个描述消息队列的msqid_ds结构,该结构完整地描述一个消息队列。每个msqid_ds结构包含一个ipc_perm结构和指向已经进入此队列消息的指针。另外,Linux保留有关队列修改时间信息,如上次系统向队列中写入的时间等。msqid_ds包含两个等待队列:一个为队列写入进程使用而另一个由队列读取进程使用。

Linux系统中的信号量的实现过程?
答:在执行信号量操作时,Linux首先将检查是否所有操作已经成功。如果操作值与信号量当前数值相加大于0,或者操作值与信号量当前值都是0,操作将会成功。如果所有信号量操作失败,Linux仅仅会把那些操作标志没有要求系统调用为非阻塞类型的进程挂起。进程挂起后,Linux必须保存信号量操作的执行状态并将当前进程放入等待队列。系统还在堆栈上建立sem_queue结构并填充各个域。这个sem_queue结构将被放到此信号量对象等待队列的尾部。系统把当前进程置入sem_queue结构中的等待队列中,然后执行调度程序。
如果所有这些信号量操作都成功则无需挂起当前进程,Linux将对信号量数组中的其他成员进行相同操作,然后检查那些处于等待或者挂起状态的进程。首先,Linux将依次检查挂起队列(sem_pending)中的每个成员,看信号量操作能否继续。如果可以则将其sem_queue结构从挂起链表中删除并对信号量数组发出信号灯操作。Linux还将唤醒处于睡眠状态的进程并使之成为下一个运行的进程。如果在对挂起队列的遍历过程中有的信号量操作不能完成则Linux将一直重复此过程,直到所有信号量操作完成且没有进程需要继续睡眠。

Linux系统中的System V IPC是什么?
答:System V IPC中的信号量机制是对传统信号量机制的推广,实际是“用户空间信号量”。它由内核支持,在系统空间实现,但可由用户进程直接使用。

Linux系统的支持哪些不同的文件系统?
答:Linux系统的一个重要特征就是支持多种不同的文件系统,如EXT、FAT、EXT2、EXT3、MINIX、MSDOS、SYSV等。目前,Linux主要使用的文件系统是EXT2和EXT3。

虚拟文件系统VFS的结构如何?作用和功能是什么?
答:Linux系统的最大的特点之一就是能支持多种不同的文件系统,每一种文件系统都有自己的组织结构和文件操作函数,相互之间差别很大,为此,必须使用一种统一的接口,这就是虚拟文件系统(VFS)。
图8-12示出VFS和实际文件系统之间的关系,从图中可以看出,用户程序(进程)通过有关文件系统操作的系统调用进入系统空间,然后经由VFS才可使用Linux系统中具体的文件系统。
这个抽象的界面主要由一组标准的、抽象的有关文件操作构成,以系统调用的形式提供给用户程序,如read( )、write( )和lseek( )等。所以,VFS必须管理所有同时安装的文件系统。它通过使用描述整个VFS的数据结构和描述实际安装的文件系统的数据结构,来管理这些不同的文件系统。
图8-12 VFS和实际文件系统之间的关系
不同的文件系统通过不同的程序来实现其各种功能。VFS定义了一个名为file_operations的数据结构,这个数据结构成为VFS与各个文件系统的界面。
VFS的功能主要有:记录可用的文件系统的类型;将设备同对应的文件系统联系起来;处理一些面向文件的通用操作;涉及到针对文件系统的操作时,VFS把他们映射到与控制文件、目录、以及inode相关的物理文件系统。

Linux文件系统中的EXT3是什么?
答:EXT3是保有EXT2的格式之下再加上日志功能。EXT3是一种日志式文件系统(Journal File System),最大的特点是:它会将整个磁盘的写入动作完整的记录在磁盘的某个区域上,以便有需要时回溯追踪。当在某个过程中断时,系统可以根据这些记录直接回溯并重整被中断的部分,重整速度相当快。该分区格式被广泛应用在Linux系统中。

何谓VFS超级块?
答:VFS和EXT2文件系统一样也使用超级块和索引节点来描述和管理系统中的文件。每个安装的文件系统都有一个VFS超级块,其中包含以下主要信息:
(1) Device,设备标识符:表示文件系统所在块设备的设备标志符。这是存储文件系统的物理块设备的设备标识符,如系统中第一个IDE磁盘/dev/hda1的标识符是0x301。
(2) Inode pointers,索引节点指针:这个mounted inode指针指向文件系统中第一个inode。而covered inode指针指向此文件系统安装目录的inode。根文件系统的VFS超级块不包含covered指针。安装索引节点指针指向被安装的子文件系统的第一个索引节点;覆盖索引节点指针指向安装文件系统目录(安装点)的索引节点。根文件系统的VFS超级块中没有覆盖索引节点指针。
(3) Blocksize,数据块大小:文件系统中数据块的字节数。以字节记数的文件系统块大小,如1024字节。
(4) Superblock operations,超级块操作集:指向一组超级块操作例程的指针,VFS利用它们可以读写索引节点和超级块。这些例程被VFS用来读写inode和超块。
(5) File System type,件系统类型:这是一个指向已安装文件系统的file_system_type结构的指针。
(6) File System specific,件系统的特殊信息:指向文件系统所需要信息的指针。
可以看出,VFS超级块的结构比EXT2文件系统的超级块简单,主要增加的是超级块操作集,它用于对不同文件系统进行操作,对于超级块本身并无作用。

Linux文件系统的安装与拆卸过程是怎样的?
答:Linux文件系统可以根据需要随时装卸,从而实现文件存储空间的动态扩充。在系统初启时,往往只安装有一个文件系统,即根文件系统,其上的文件主要是保证系统正常运行的操作系统代码文件,以及若干语言编译程序、命令解释程序和相应的命令处理程序等构成的文件。此外,还有大量的用户文件空间。根文件系统一旦被安装上,则在整个系统运行过程中是不能卸下的,它是系统的基本部分。
其它的文件系统(例如由软盘构成的文件系统)可以根据需要(如从硬盘向软盘复制文件),作为子系统动态地安装到主系统中。经过安装之后,主文件系统与子文件系统就构成一个有完整目录层次结构的、容量更大的文件系统。
若干子文件系统可以并列安装到主文件系统上,也可以一个接一个地串连安装到主文件系统上。已安装的子文件系统也可从整个文件系统上卸下来,恢复安装前的独立状态。

Linux支持虚拟内存,什么是虚拟内存?
答:Linux系统采用了虚拟内存管理机制,就是交换和请求分页存储管理技术。这样,当进程运行时,不必把整个进程的映像都放在内存中,只需在内存保留当前用到的那一部分页面。当进程访问到某些尚未在内存的页面时,就由核心把这些页面装入内存。
这种策略就使进程的虚拟地址空间映射到机器物理空间时,具有更大的灵活性,通常允许进程的大小可大于可用内存的总量,并允许更多进程同时在内存中执行。
为了实现离散存储,虚拟内存与物理内存都以大小相同的页面来组织,一般将页面大小设为2的次幂。页面模式下的虚拟地址由两部分构成:页面框号和页面内偏移值。在页表的帮助下,它将虚拟页面框号转换成物理页面框号,然后访问物理页面中相应偏移处。

简述请求分页的基本思想。
答:请求分页存储管理技术是在简单分页技术基础上发展起来的,二者根本区别在于请求分页提供虚拟存储器。
它的基本思想是,当要执行一个程序时才把它换入内存;但并不把全部程序都换入内存,而是用到哪一页时才换入它。这样,就减少了对换时间和所需内存数量,允许增加程序的道数。
为了表示一个页面是否已装入内存块,在每一个页表项中增加一个状态位,Y表示该页对应的内存块可以访问;N表示该页不对应内存块,即该页尚未装入内存,不能立即进行访问。
如果地址转换机构遇到一个具有N状态的页表项时,便产生一个缺页中断,告诉CPU当前要访问的这个页面还未装入内存。操作系统必须处理这个中断:它装入所要求的页面,并相应调整页表的记录,然后再重新启动该指令。
由于这种页面是根据请求而被装入的,所以这种存储管理方法叫做请求分页存储管理。通常在作业最初投入运行时,仅把它的少量几页装入内存,其它各页是按照请求顺序动态装入的,这样就保证用不到的页面不会被装入内存。

Linux进行地址映射的过程是怎样的?
答:执行进程时,可执行的命令文件被打开,同时其内容被映射到进程的虚拟内存。这时可执行文件实际上并没有调入物理内存,而是仅仅连接到进程的虚拟内存。当程序的其他部分运行时引用到这部分的时候才把它们从磁盘上调入内存。将虚拟地址转换成物理地址的过程称为地址映射。
每个进程的虚拟内存用一个mm_struct来表示。它包含当前执行的映象以及指向vm_area_struct的大量指针。每个vm_area_struct数据结构描述了虚拟内存的起始与结束的位置;进程对此内存区域的存取权限以及一组内存操作函数。这组内存操作函数都是Linux在操纵虚拟内存区域时必须用到的子程序。其中一个负责处理进程试图访问不在当前物理内存中的虚拟内存(通过缺页中断)的情况。此函数叫nopage。它用于Linux试图将可执行映象的页面调入内存时。
可执行程序映射到进程虚拟地址时将产生一组相应的vm_area_struct数据结构。每个vm_area_struct数据结构表示可执行程序的一部分:可执行代码、初始化数据(变量)、未初始化数据等等。

Linux采用三级页表结构的内容是什么?
答:Linux采用三级页表结构,如图8-21所示。每个页表通过所包含的下级页表的页框号PFN来访问。Linux的三级页表的说明如下:
页目录(第一级):每个活动进程有一个一页大小的页目录,其中的每一项指向页间目录中的一页。
页间目录(第二级):页间目录可以由多个页面组成,其中的每一项指向页表中的一页。
页表(第三级):页表也可以由多个页面组成,每个页表项指向进程的一个虚页。
Linux的虚地址由四个域组成,页目录是第一级索引,由它找到页间目录的起始位置。第二级索引是根据页间目录的值确定页表的起始位置,它通过页表的值找到物理页面的页框号,再加上最后一个域的页内偏移量,得到了页面中数据的地址。
图8-21中PGD表示页面目录,PMD表示中间目录,PT表示页表。一个线性的虚拟地址在逻辑上从高位到低位划分成4个位段,分别用作页面目录PGD中的下标、中间目录PMD中的下标、页表PT中的下标和物理页面(即内存块)内的位移。
图8-21 三级页表地址映射示意图

这样,把一个线性地址映射成物理地址分为以下四步:
(1) 以线性地址中最高位段作下标,在PGD中找到相应的表项,该表项指向相应的PMD。
(2) 以线性地址中第二个位段作下标,在PMD中找到相应的表项,该表项指向相应的PT。
(3) 以线性地址中第三个位段作下标,在PT中找到相应的表项,该表项指向相应的物理页面(即该物理页面的起始地址)。
(4) 线性地址中的最低位段是物理页面内的相对位移量,此位移量与该物理页面的起始地址相加就得到相应的物理地址。

Linux系统中页面的数据结构是怎样的?
答:在Linux当中,每个进程的虚拟内存用一个mm_struct来表示。它包含当前执行的映象以及指向vm_area_struct的大量指针。每个vm_area_struct数据结构描述了虚拟内存的起始与结束的位置;进程对此内存区域的存取权限以及一组内存操作函数。这组内存操作函数都是Linux在操纵虚拟内存区域时必须用到的子程序。其中一个负责处理进程试图访问不在当前物理内存中的虚拟内存(通过缺页中断)的情况。此函数叫nopage。它用于Linux试图将可执行映象的页面调入内存时。
可执行程序映射到进程虚拟地址时将产生一组相应的vm_area_struct数据结构。每个vm_area_struct数据结构表示可执行程序的一部分:可执行代码、初始化数据(变量)、未初始化数据等等。
虚拟内存子系统中负责页面分配与回收的数据结构用mem_map_t结构的链表mem_map来描述,这些结构在系统启动时初始化。每个mem_map_t描述了一个物理页面。其中几个重要的域如下:
count :记录使用此页面的用户个数。当这个页面在多个进程之间共享时,其值大于1。
age :此域用于描述页面的年龄,用于选择将适当的页面抛弃或者置换出内存时。
map_nr:记录本mem_map_t描述的物理页面框号。
系统使用free_area数组管理整个缓冲,实现分配和释放页面。
代表物理页面的page数据结构是在文件include/linux/mm.h中定义的。系统维持的物理页面供应量由两个全局量确定,那就是freepages.high(初始化语句位于mm/swap.c)和inactive_target(初始化语句位于include/linux/mm_inline.h),分别为空闲页面的数量以及不活跃页面的数量,二者之和为正常情况下潜在的供应量。

Linux系统中页面淘汰策略是如何的?
答:为了防止“抖动”的发生,linux将页面的换出和内存页面的释放分成两步来做。当系统挑选出若干内存页面准备换出时,将这些页面的内容写入到相应的磁盘中,并且将相应的页面表项的内容设置为指向磁盘页面。
页面表项的数据结构pte_t的定义位于include/asm-i386/page.h中,它是一个32位的整形变量,其中它的第一位P用于表示该页面是否在内存中:P位为1表示在内存中;为0,则表示不在内存中。这里需要将换出页面的P位置0,但是所占据的内存页面却并不立即释放,而是将其page结构留在一个cache队列当中,并使其从“活跃状态”转入“不活跃状态”,至于最后释放内存页面的操作就推迟到以后有条件时来进行。这样,如果在一个页面被换出以后立即又被访问而发生缺页异常时,就可以从物理页面的cache队列中找到相应的页面,并为之建立映射。由于该页面尚未释放,内存中还保留着原来的内容,就不需要再从磁盘上读入了。反之,如果经过一段时间以后,一个不活跃的内存页面还是没有被访问,那就到了最后释放的时候了。如果位于cache队列中的页面又受到了访问,那么只需要恢复这个页面在内存中的映射并使其脱离cache队列就可以了。
在Linux当中通过一个全局的address_space数据结构swapper_space,把所有可交换的内存页面管理起来,每个可交换内存页面的page数据结构都通过其队列头结构list链入其中的一个队列。函数add_to_swap_cache()完成将page结构链入相应队列的工作,它的代码位于mm/swap_state.c中。将内存页面的“换出”与“释放”分两步走的策略显然可以减少抖动发生的可能,并减少系统在页面交换上的开销。

Linux系统采用设备文件统一管理硬件设备,从而将硬件设备的特性及管理细节对用户隐藏起来,实现用户程序与设备无关性。试说明Linux系统是如何实现的。
答:用户是通过文件系统与设备接口的,所有设备都作为特别文件,从而在管理上就具有一些共性。
(1)每个设备都对应文件系统中的一个索引节点,都有一个文件名。设备的文件名一般由两部分构成,第一部分是主设备号,第二部分是次设备号。
主设备号代表设备的类型,可以惟一地确定设备的驱动程序和界面,如hd表示IDE硬盘,sd表示SCSI硬盘,tty表示终端设备等;次设备号代表同类设备中的序号,如hda表示IDE主硬盘,hdb表示IDE从硬盘等。
(2)应用程序通常可以通过系统调用open()打开设备文件,建立起与目标设备的连接。
(3)对设备的使用类似于对文件的存取。打开设备文件以后,就可以通过read()、write()、ioctl()等文件操作对目标设备进行操作。
(4)设备驱动程序都是系统内核的一部分,它们必须为系统内核或它们的子系统提供一个标准的接口。例如,一个终端驱动程序必须为Linux内核提供一个文件I/O接口;一个SCSI设备驱动程序应该为SCSI子系统提供一个SCSI设备接口,同时SCSI子系统也应为内核提供文件I/O和缓冲区。
(5)设备驱动程序利用一些标准的内核服务,如内存分配等。另外,大多数Linux设备驱动程序都可以在需要时装入内核,不需要时可以卸载下来。
对于一般文件(即磁盘文件),要进行空间的映射—从普通文件的逻辑空间映射到设备的逻辑空间,然后在设备驱动层做进一步映射—从设备的逻辑空间映射到物理空间(即设备的物理地址空间),进而驱动底层物理设备工作。
对于设备文件,则文件的逻辑空间通常就等价于设备的逻辑空间,然后从设备的逻辑空间映射到设备的物理空间,再驱动底层的物理设备工作。

谈谈Linux设备管理的结构是怎样的。
答:Linux设备管理主要由系统调用和设备驱动程序组成。系统调用是上层的、与设备无关的软件,它为用户和内核之间提供了一个统一而简单的接口。设备驱动程序是下层的、与设备有直接关系的软件,它直接与相应设备打交道,而且向上层内核提供一组访问接口。Linux设备管理层次图见图8-24。
图8-24 Linux 设备管理层次图

Linux系统中的设备及分类是怎样的,它们的操作有哪些特点?
答:在Linux系统中,硬件设备分为两种,即块设备和字符设备。
在Linux系统中,打印机、终端等字符设备都作为字符特别文件出现在用户面前。用户对字符设备的使用就和存取普通文件一样。在应用程序中,使用标准的系统调用来打开、关闭、读写字符设备。当字符设备初始化时,其设备驱动程序被添加到由device_struct结构组成的chrdevs结构数组中。
对块设备的存取和对文件的存取方式一样,其实现机制也和字符设备使用的机制相同。Linux系统中有一个名为blkdevs的结构数组,它描述了一系列在系统中登记的块设备。
数组blkdevs也使用设备的主设备号作为索引,其元素类型是device_struct结构。该结构中包括指向已登记的设备驱动程序名的指针和指向block_device_operations结构的指针。
在block_device_operations结构中包含指向有关操作的函数指针。所以,该结构就是连接抽象的块设备操作与具体块设备类型的操作之间的枢纽。
与字符设备不一样,块设备有几种类型,例如SCSI设备和IDE设备。每类块设备都在Linux系统内核中登记,并向内核提供自己的文件操作。

Linux设备管理主要的I/O控制方式有哪些,它们的内容是什么?
答:1.轮询方式
轮询方式即程序直接控制方式,是指在I/O过程中经常读取设备的状态,直到设备状态表明请求已经完成为止。如果设备驱动被连接进入核心,这时使用轮询方式将会带来灾难性后果:核心将在此过程中无所事事,直到设备完成此请求。但是轮询设备驱动可以通过使用系统定时器,让核心周期性调用设备驱动中的某个例程来检查设备状态。定时器过程可以检查命令状态及Linux软盘驱动的工作情况。使用定时器是轮询方式中最好的一种,但更有效的方法是使用中断。
2.中断方式
基于中断的设备驱动会在它所控制的硬件设备需要服务时引发一个硬件中断。Linux核心需要把来自硬件设备的中断传递到相应的设备驱动。这个过程是由设备驱动向核心注册其使用的中断来协助完成。此中断处理例程的地址和中断号都将被记录下来。对中断资源的请求在驱动初始化时就已经完成。作为IBM PC体系结构的遗产,系统中有些中断已经固定。例如软盘控制器总是使用中断6。其它中断,如PCI设备中断,在启动时进行动态分配。设备驱动必须在取得对此中断的所有权之前找到它所控制设备的中断号(IRQ)。Linux通过支持标准的PCI BIOS回调函数来确定系统中PCI设备的中断信息,包括其IRQ号。
如何将中断发送给CPU本身取决于体系结构,但是在多数体系结构中,中断以一种特殊模式发送,同时还将阻止系统中其它中断的产生。设备驱动在其中断处理过程中做得越少越好,这样Linux核心将能很快的处理完中断并返回中断前的状态中。为了在接收中断时完成大量工作,设备驱动必须能够使用核心的底层处理例程或者任务队列来对以后需要调用的那些例程进行排队。
3.直接内存访问(DMA)
数据量比较少、数据传传输率较低时,使用中断驱动设备驱动程序能顺利地在硬件设备和内存之间交换数据,否则会降低CPU的利用率。而DMA控制器可以在不受处理器干预的情况下在设备和系统内存之间高速传输数据。PC机的ISA DMA控制器有8个DMA通道,其中七个可以由设备驱动使用。每个DMA通道具有一个16位的地址寄存器和一个16位的记数寄存器。为了初始化数据传输,设备驱动将设置DMA通道地址和记数寄存器以描述数据传输方向以及读写类型,然后通知设备可以在任何时候启动DMA操作。传输结束时设备将中断PC。在传输过程中CPU可以转去执行其他任务。
DMA控制器没有任何虚拟内存的概念,它只存取系统中的物理内存。同时用作DMA传输缓冲的内存空间必须是连续物理内存块。这意味着不能在进程虚拟地址空间内直接使用DMA。但是你可以将进程的物理页面加锁以防止在DMA操作过程中被交换到交换设备上去。另外DMA控制器所存取物理内存有限。由于DMA通道地址寄存器代表DMA地址的高16位,而页面寄存器记录的是其余8位,因此DMA请求被限制到内存最低16M字节中。
Linux通过dma_chan(每个DMA通道一个)数组来跟踪DMA通道的使用情况。dma_chan结构中包含有两个域,一个是指向此DMA通道拥有者的指针,另一个指示DMA通道是否已经被分配出去。

Linux设备驱动程序是用来干什么的?其基本组成是哪些?
答:Linux设备驱动程序是处理或操作硬件控制器的软件,被集成在内核中,是常驻内存的低级硬件处理程序的共享库,设备驱动程序就是对设备的抽象处理。
(1).对设备进行初始化
(2).使设备投入运行和退出服务
(3).从设备接收数据并将它们送回内核
(4).将数据从内核送到设备
(5).检测和处理设备出现的错误
根据功能进行划分,可以把设备驱动程序的代码分为如下几个部分:
1.驱动程序的注册与注销
系统引导时或系统引导后在需要装载模块时,对字符设备或块设备进行初始化过程中要
通过register_chrdev()或register_blkdev()向内核注册。在不需要字符设备或块设备时,要通过unregister_chrdev()或unregister_blkdev()从内核中注销该设备。
2.设备的打开与释放
要使用设备就要打开该设备,打开设备需要通过open()来完成;在用完设备后需要释放该设备,一般用release()来完成。
3.设备的读写操作
字符设备的读写是通过read()和write()来实现的。而块设备的读写操作是通过调用内核函数block_read()和block_write()来完成对缓冲区的数据操作。对于块设备真正的读写是通过request_fn()来完成的。
4.设备的控制操作
除了读写操作外,还可以对设备进行控制操作。设备的控制操作可以通过驱动程序中的ioctl()来完成,与读写操作不同,ioctl()的用法与具体设备密切相关。除了ioctl(),设备驱动程序还可以有其它控制函数,如lseek()、mmap()、lock()、fsync()和fasync()等。
5.设备的中断和轮询处理
如果每个设备都有一个唯一的中断向量号,则当接收到中断时,根据向量号可唯一指向相应的中断处理函数。如果中断向量号被许多设备共享,则必须确定是哪个设备产生的中断。
Linux操作系统内核是采取把相同中断向量号的中断处理函数用一张链表连接起来的办法来解决的。接收到中断后,轮询链表上的所有驱动程序。驱动程序检查收到的中断请求是否由它所管的设备所产生。如果是,则它就会处理中断,否则继续轮询下一个设备。

Linux使用了多个高速缓冲机制,它们的内容各是什么?
答:Linux使用了多个高速缓冲,说明如下:
1.缓冲区高速缓冲(Buffer Cache)
这是块设备驱动使用的数据缓冲。这些缓冲的单元的大小一般固定(例如说512字节)并且包含从块设备读出或者写入的信息块。利用设备标志符和所需块号作索引可以在buffercache中迅速地找到数据。块设备只能够通过buffer cache来存取。如果数据在buffer cache中可以找到则无需从物理块设备(如硬盘)中读取,这样可以加速访问。
2.页面高速缓冲(Page Cache)
这是页面进行输入/输出操作时,访问程序和数据所用的磁盘高速缓存,它以页为单位存储数据,页面从磁盘上读入内存后缓存在page cache中。
3.交换高速缓冲(Swap Cache)
交换文件中保存的是修改过的页面。只要这些页面在写入到交换文件后没有被修改,则下次此页面被交换出内存时,就不必再进行更新写操作,这些页面都可以简单的丢弃。
4.转换后援存储器(TLB)
这是一个具有并行查寻能力的高速缓冲,也叫联想存储器。基于局部性原理,程序在一段时间的执行总是在几个页面中进行。而Linux采用的是三级页表机制,要多次访问内存,降低了程序执行的效率。设置该缓冲器后,它包含页表入口的缓冲拷贝。当需要进行地址转换时,CPU去与TLB中的内容匹配,若命中则直接将逻辑地址转换成物理地址。如果没有命中,即按正常次序访问页表,然后从TLB中淘汰一项,替换成刚找到的页表项。


本文地址:http://liuyanzhao.com/2916.html
转载请注明

Logo

更多推荐