操作系统总复习及相关习题

操作系统总复习及相关习题

第一章 引论

名词解释

1操作系统

操作系统是管理和控制计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

2管态

当执行操作系统程序时，处理机所处的状态

3目态

当执行普通用户程序时，处理机所处的状态。

4多道程序设计

在这种设计技术下，内存中能同时存放多道程序，在管理程序的控制下交替的执行。这些作业共享CPU和系统中的其他资源。

5并发

是指两个或多个活动在同一给定的时间间隔中进行。它是宏观上的概念。 6并行

是指两个或多个活动在同一时刻同时执行的情况。

7吞吐量

在一段给定的时间内，计算机所能完成的总工作量。 8分时

就是对时间的共享。在分时系统中，分时主要是指若干并发程序对CPU时间的共享。 9实时

表示“及时”或“既时”。

10系统调用

是用户在程序中能以“函数调用”形式调用的、由操作系统提供的子功能的集合。每一个子功能称作一条系统调用命令。它是操作系统对外的接口，是用户级程序取得操作系统服务的唯一途径。 11特权指令

指指令系统中这样一些指令，如启动设备指令、设置时钟指令、中断屏蔽指令和清内存指令，这些指令只能由操作系统使用。 12命令解释程序

其主要功能是接收用户输入的命令，然后予以解释并且执行。

13脱机I/O

是指输入/输出工作不受主机直接控制，而由卫星机专门负责完成I/O，主机专门完成快速计算任务，从而二者可以并行操作。

14联机I/O

是指作业的输入、调入内存及结果输出都在cpu直接控制下进行。

15资源共享

是指计算机系统中的资源被多个进程所功用。例如，多个进程同时占用内存，从而对内存共享；它们并发执行时对cpu进行共享；各个进程在执行过程中提出对文件的读写请求，从而对磁盘进行共享等等。

简答题

1什么是操作系统？它的主要功能是什么？

答：操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。操作系统的主要功能有5个方面，即存储管理、处理机管理、设备管理、文件管理和用户接口。

2推动操作系统形成和发展的主要动力是什么？

答：推动操作系统发展的因素很多，主要可归结为两大方面：硬件技术更新和应用需求扩大伴随计算机器件的更

新换代和计算机体系结构的发展，促使操作系统的性能和结构有了显著发展。 应用需求促进了计算机技术的发展，也促进了操作系统的不断更新升级。

3操作系统的基本特征是什么？

答：操作系统的基本特征是并发、共享和不确定。并发性是指两个或多个活动在同一给定的时间间隔中进行；共享是指计算机系统中的资源被多个进程所共用；不确定性是指系统中各种事件发生顺序的不可预测性。

4多道程序和多重处理有何区别？

答：多道程序是作业之间自动调度执行、共享系统资源，并不是真正的同时执行多个作业；而多重处理系统配置多个cpu，能真正同时执行多道程序。要有效使用多重处理，必须采用多道程序设计技术，而多道程序设计原则上不一定要求多重处理系统的支持。

5试说明多道程序设计和多任务系统之间的关系

答：多道程序设计是利用外设与cpu能够并行处理的特性，在主存同时存放多个程序，使之在系统中交叉地使用cpu，从而提高系统资源的利用率。而多任务系统主要指多进程交叉使用cpu。多道程序隐含了多任务处理，但多任务系统中不一定有多道程序。因为一个程序也可以采用多任务处理机制。

6不同类型的操作系统提供不同的功能。假定有如下的应用环境，请你为它们选择适合的操作系统。

（1）飞机的导航，（2）办公自动化系统，（3）航空订票系统，（4）复杂的科学计算，（5）图书检索系统 答：（1）飞机的导航系统，应采用硬实时操作系统 （2）办公自动化系统，应采用分时操作系统 （3）航空订票系统，应采用软实时操作系统 （4）复杂的科学计算，应采用批处理系统 （5）图书检索系统，应采用软实时操作系统

7什么是批处理系统，它有什么特征？

答：批处理系统：操作员把用户提交的作业分类，把一批作业编成一个作业执行序列，由专门编制的监督程序自动依次处理。其主要特征是：用户脱机使用计算机、成批处理、多道程序运行。

8什么是分时系统，它有什么特征？

答：分时系统：把处理机的运行时间分成很短的时间片，按时间片轮转的方式，把处理机分配给各进程使用。其主要特征是：交互性、多用户同时性、独立性。

9什么是实时系统？它有什么特征？

答：实时系统：在被控对象允许时间范围内做出响应 。其主要特征是：对实时信息分析处理速度要比进入系统快、要求安全可靠、资源利用率低。

10什么是处理机的核心态和用户态？为什么要设置这两种不同的状态？

答：当执行操作系统程序时，处理机处于核心态。它有较高的特权，可以执行所有的指令，包括一般用户程序中不能使用的特权指令，从而能对所有寄存器和内存进行访问，启动i/o操作等。 用户程序是在用户态下执行，它的权限较低，只能执行指令集中非特权指令。（2分） 设置这两种不同状态的目的是为了保护操作系统程序（特别是其内核部分），防止受到用户程序的损害。

11系统调用与过程调用在功能及实现上有什么相同点和不同点？

答：相同点：两者都由程序代码构成，可直接用高级程序设计语言（如C,C++和Perl语言）来编制；使用方式相同——以函数调用的形式出现，调用时传送参数。

不同点：①代码层次不同，过程调用不属于操作系统的一部分，而系统调用是操作系统的一部分。②运行状态不同。过程调用只能在用户态下运行，不能进入核心态，而系统调用是在核心态下运行的。③进入方式不同。过程调用在用户程序中调用，并直接在用户空间内执行；而系统调用可以在用户程序中调用，但是在用户程序中执行到系统调用时，会产生异常事件。实现处理机状态从用户态到核心态的转变，从而进入操作系统核心空间去执行系统调用的代码。

12试说明特权指令和系统调用之间的区别与联系。

答：特权指令是一类只能在核心态下执行的机器指令。而系统调用不是机器指令，它往往以函数调用的形式出现，实现操作系统提供的子功能，它是操作系统与用户的编程接口 。在用户程序中可以使用系统调用来获得操作系

统服务，在系统调用代码中可以使用特权指令

第二章 进程和线程

名词解释

1顺序性

是指顺序程序所规定的每个动作都在上个动作结束后才开始的特性。

2封闭性

是指只有程序本身的动作才能改变程序的运行环境。

3可再现性

是指程序的执行结果与程序运行的速度无关。

4进程

程序在并发环境中的执行过程。

5互斥

在逻辑上本来完全独立的进程，由于竞争同一个资源而产生的相互制约的关系。

6同步

是指进程间共同完成一项任务时直接发生相互作用的关系。也就是说，这些具有伙伴关系的进程在执行次序上必须遵循确定的规律。

7临界资源

一次仅允许一个进程使用的资源。

8临界区

在每个进程中访问临界资源的那段程序。

9线程

线程是进程中实施调度和分派的基本单位。

10管程

管程是一种高级同步机制，一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。

11进程控制块

进程控制块是进程存在的唯一标识，它保存了系统管理和控制进程所必须的信息，是进程动态特性的集中表现。

12原语

指操作系统中实现一些具有特定功能的程序段，这些程序段的执行过程是不可分割的，即其执行过程不允许被中断。

13就绪态

进程已经获得了除cpu之外的全部资源，等待系统分配cpu，一旦获得cpu，进程就可以变为运行态。

14运行态

正在cpu上执行的进程所处的状态。在单cpu系统中，任何时候最多只能有一个进程处于运行状态。

15阻塞态

又称等待态，指正在运行的进程因等待某个条件发生而不能运行时所处的状态。处于阻塞态的进程在逻辑上是不能运行的，即使cpu空闲，它也不能占用cpu。

16进程通信

是指进程间的信息交换。

17同步机制

同步机构是负责处理进程之间制约关系的机制，即操作系统中负责解决进程之间协调工作的同步关系（直接制约关系），以及共享临界资源的互斥关系（间接制约关系）的执行机构。

简答题

1在操作系统中为什么要引入进程概念？

答: 由于多道程序并发执行时共享系统资源，共同决定这些资源的状态，因此系统中各程序在执行过程中就出现了相互制约的新关系，程序的执行出现“走走停停”的新状态。用程序这个静态的概念已不能如实反映程序并发执行过程中的这些特征。为此，人们引入了“进程（Process）”这一概念来描述程序动态执行过程的性质。

进程和程序是两个完全不同的概念。然而，进程与程序之间存在密切关系，进程的功能是通过程序的运行得以实现的，进程活动的主体是程序。进程不能脱离开具体程序而独立存在。

2有人说，一个进程是由伪处理机执行的一个程序，这话对吗？为什么？

答：对。

因为伪处理机的概念只有在执行时才存在，它表示多个进程在单处理机上并发执行的一个调度单位。因此，尽管进程是动态概念，是程序的执行过程，但是，在多个进程并行执行时，仍然只有一个进程占据处理机执行，而其他并发进程则处于就绪或等待状态。这些并发进程就相当于由伪处理机执行的程序。

3试比较进程和程序的区别

答：（1）进程是一个动态的概念，而程序是一个静态的概念，程序是指令的有序集合，无执行含义，进程则强调执行的过程。

（2）进程具有并行特征（独立性、异步性），程序则没有。

（3）不同的进程可以包含同一个程序，同一程序在执行中也可以产生多个进程。

4进程的基本状态有哪些？试描绘进程状态转换图。

答：进程至少有三种基本状态：运行状态、就绪状态和阻塞状态（或等待状态） 。进程状态转换如下图：

运行态

进程调度 所需要的资源未被满足

时间片到 （如等待 I/O）

所需资源得到满足

（如I/O完成） 运行态 运行态

5并发进程间的制约有哪两种？引起制约的原因是什么？

答：并发进程所受的制约有两种：直接制约和间接制约。

直接制约是由并发进程相互共享对方的私有资源所引起的；间接制约是由竞争共有资源而引起的。

6什么是进程间的互斥？什么是进程间同步？

答：进程间的互斥是指：一组并发进程中的一个或多个程序段，因共享某一共有资源而导致它们必须以一个不许交叉执行的单位执行，即不允许两个以上的共享该资源的并发进程同时进入临界区。

进程间的同步是指：异步环境下的一组并发进程因直接制约相互发送消息而进行相互合作、相互等待，是各进程按一定的速度执行的过程。

7什么是临界区和临界资源？进程进入临界区的调度原则是什么？

答：临界资源——一次仅允许一个进程使用的资源 临界区——在每个进程中访问临界资源的那段程序 一个进程进入临界区的调度原则是：

① 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入

② 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其他所有试图进入临界区的进程必须等待

③ 进入临界区的进程要在有限的时间内退出，以便让其他进程能及时进入自己的临界区 ④ 如果进程不能进入自己的临界区，则应让出cpu，避免进程出现“忙等”现象.

8简述信号量的定义和作用。P，V操作原语是如何定义的？

答：信号量一般是由两个成员组成的数据结构，其中一个成员是整型变量，表示该信号量的值，它与相应资源的使用情况有关；另一个是指向PCB的指针。当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针项指出该队列的队首。（2分）

信号量通常可以简单反映出相应资源的使用情况，它与P、V操作原语一起使用可实现进程的同步和互斥。（1分）

P,V操作原语有如下定义。

P(S)顺序执行下述两个动作（1分）： ⑴信号量的值减1，即S=S-1; ⑵如果S>=0,则该进程继续执行。

如果S<0,则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直到其他进程在S上执行V操作，把它释放出来为止）。

V(S)顺序执行下述两个动作（1分）： ⑴S值加1，即S=S+1;

⑵如果S>0,则该进程继续运行；

如果S<=0,则释放信号量队列上的第一个PCB所对应的进程（把阻塞态改为就绪态）,执行V操作的进程继续运行。

9什么是线程？它与进程有什么关系？

答：线程是进程中实施调度和分派的基本单位。 线程和进程之间有如下关系：

① 一个进程可以有多个线程，但至少有一个线程；而一个线程只能在一个进程的地址空间内活动。 ② 资源分配给进程，同一进程的所有线程共享该进程的所有资源。 ③ 处理机分给线程，即真正在处理机上运行的是线程。

④ 线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。

10什么是管程？它由哪几部分组成？有什么基本特性?

答：一个管程定义了一个数据结构和能为并发进程在其上执行的一组操作，这组操作能同步进程和改变管程中的数据。

一个管程由四个部分组成，它们是管程名称、局部与管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句。 管程具有以下特性：

① 管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问 ② 进程要想进入管程，必须调用管程内的某个过程

③ 一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。就是说，管程自身能有效地实现互斥。

综合题

1如下图所示的工作模型中，有三个进程p0,p1,p2和三个缓冲区B0,B1,B2. 进程之间借助于相邻缓冲区进行消息

传递：每个进程每次从缓冲区中取一条消息，经加工处理后送入另一个缓冲区中，三个缓冲区分别可存放3,2,2个消息。初始时，仅缓冲区0有一个消息。试用P、V操作写出三个进程之间的同步及互斥流程。 答：这是一个生产者/消费者问题，而且每个进程既是生产者，也是消费者。(2’)

为此，应设置6个信号量：B0S1,B0S2,B1S1,B1S2,B2S1,B2S2,分别代表B0,B1,B2中是否有空缓冲和有数据。 B0S1,B0S2,B1S1,B1S2,B2S2:semaphore; B0S1=2;B0S2=1;B1S1=2;B1S2=0;B2S1=2;B2S2=0; (2’) Cobegin (`6’=2’*3) P0 P1 P2 begin begin begin P(B0S2) P(B1S2) P(B2S2) 从B0取一个数据 从B1取一个数据 从B2取一个数据 V(B0S2) V(B1S1) V(B2S1) 加工 加工 加工 P(B1S1) P(B2S1) P(B0S1) 将加工结果送B1 将加工结果送B2 将加工结果送B0 V(B1S2) V(B2S2) V(B0S2) end end end coend

这道题也可以增加互斥信号量，以便P0与P1之间互斥使用B0缓冲区，P1与P2之间互斥使用B1缓冲区，P2与P0之间互斥使用B0缓冲区。这里主要描述它们之间的同步关系。若考虑互斥共享缓冲区，请自己加上。

2设用三个队列管理缓冲区池的使用情况，分别为空白缓冲队列em，输入缓冲队列in，以及输出缓冲队列out。过程add_buf(type,numb)和take_buf(type,numb)分别用来把缓冲区numb插入type队列和从type队列中取出缓冲区numb。试描述进程从任一缓冲队列中得到一个缓冲区的过程get_buf(type,numb)和释放一个缓冲区numb进入缓冲队列的过程put_buf(type,numb)。

答：假定用信号量s代表任一队列的可用缓冲区个数。假定三个队列的初值分别为n1,n2,n3。对任一队列的操作必须互斥。因此再引入一个互斥使用任一队列的信号量mutex，其初值为1。这里type代表队列的类型，它的取值为输入、输出和空白。(4’)

当有进程希望从任一队列取一个缓冲区时，过程get_buf(type,numb)的动作如下： get_buf(type,numb) (`3’) begin p(s) p(mutex) numb=take_buf(type,numb) v(mutex) end

当有进程希望向任一队列送一个缓冲区时，过程put_buf(type,numb)的动作如下： put_buf(type,numb) (`3’) begin p(mutex) add_buf(type,numb) v(mutex) v(s)

end.

3设有一个售票厅，可容纳100人购票。如果厅内不足100人则允许进入，进入后购票，购票后退出。如果厅内已有100人，则在厅外等候。试问：

1） 购票者之间是同步还是互斥？

用P、V操作表达购票者的工作过程。 解：1）购票者之间是互斥关系。(2’)

2） 一个售票厅可容纳100人购票，说明最多允许100个购票者共享售票厅；可引入一个信号量empty，其初值

为100。由于购票者必须互斥地进行购票，故应再设一个mutex，其初值为1。(4’) 用P、V操作表达购票者的工作过程如下：(`4’)

empty,mutex:semaphore; empty:=100; mutex:=1; begin p(empty) p(mutex) 进入厅内购票,购票后退出 v(empty) v(mutex) end.

4某招待所有100个床位，住宿者入住要先登记（在登记表上填写姓名和床位号）．离去时要注销登记（在登记表上删去姓名和床位号）．请给出住宿登记及注销过程的算法描述．

答：某招待所有100个床位，为了正确管理，引入一个信号量empty代表空床位数，初值为100；住宿者入住要先登记（在登记表上填写姓名和床位号），显然，登记表是一个临界资源，必须互斥访问，引入一个mutex，其初值为1。(4’)

住宿登记及注销过程的算法描述如下： 住宿登记：(`3’) begin p(empty) //检查有无床位 p(mutex) //申请登记 找出一个空床位将名字登入表中 v(mutex) end 注销过程：(`3’) begin p(mutex) //申请退房 找出自己的登记项，并删除该项的登记 v(mutex) v(empty)

end.

5有一个阅览室，共有100个座位。为了很好地利用它，读者进入时必须先在登记表上进行登记。该表表目设有座位号和读者姓名；离开时再将其登记项擦除。

试问：为描述读者的动作，应编写几个程序，应设几个进程、它们之间的关系怎样？并请用P、V操作描述进程之间的同步算法。

解：为了描述阅览室，用一个登记表来记录其使用情况。表中共有100项。每当有读者进入阅览室时，为了正确地登记，各读者应互斥使用(1’)。为此设两个信号量：mutex为互斥信号量，用来制约各读者互斥地进行登记，其初值为1；empty为同步信号量，用来制约各读者能同时进入阅览室的数量，其初值为100 (2’)。 下面用两个过程描述对表格应执行的动作： 登记过程：(`2’) 擦除过程：(`2’) begin begin P(empty) P(mutex) P(mutex) 找到自己的登记项擦除 找到一个登记项登记 V(mutex)

V(mutex) V(empty) end end 为了正确地描述读者的动作，可以将读者看成进程。若干读者希望进入阅览室时，调用登记过程，退出阅览室时，调用擦除过程(1’)。

可见，一个程序可对应多个读者。可设的进程数由读者数决定，其动作如下：(`2’) begin 调用登记过程 进入阅览室阅读 准备退出 调用擦除过程 end.

6一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过；但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。

解：假设一座桥由N个桥墩，也即最多允许有N个人同向过河，用一个计数器R记录同时过河的人数(2’)。用S1信号量保护计数器，其初值为1，R的初值为0；互斥使用桥的信号量用S表示，其初值为1。(2’) 同步算法描述如下： procedure goriver() begin L:P(S1); //为同时过河,申请对计数器计数 If R>N begin V(S1); goto L; end //同方向过河的人站满桥墩时,重新申请计数 R=R+1; If R==1 P(S); //申请过河 V(S1); //释放计数器的使用权 (3’) 占有一个桥墩,并顺序过河到对岸; P(S1); R=R-1; If R==0 V(S); //如果已经无同向的人过河,释放占用权 V(S1); (3’)

end.

7在一个飞机订票系统中，多个用户共享一个数据库。各用户可以同时查询信息，若有一个用户要订票，须更新数据库时，其余所有用户都不可以访问数据库。请用P,V操作设计一个同步算法，实现用户查询与订票功能。要求：当一个用户订票而需要更新数据库时，不能因不断有查询者到来而使其长时间等待。利用信号量机制保证其正常执行。

解：这是典型的读者——写者问题，查询信息的用户是读者，订票用户是写者，并且要求写者优先。(2’) 变量说明：(`2’)

计数变量

rc——正在运行的查询者进程数目，初值为0. 信号量

Sw——控制订票者进程的活动，初值为1. Src——互斥使用rc变量，初值为1.

S——当订票者到达时封锁后续的读进程，初值为1. 读者进程 P(S) P(Src) rc=rc+1

if (rc==1) P(Sw) V(Src)

V(S) (2’) 查询库当中的信息 P(Src) rc=rc-1;

if (rc==0) V(Sw) V(Src) (2’)

写者进程 (`2’) P(S) P(Sw)

更新数据库内容 V(Sw) V(S)

8某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。 (2)根据所定义的信号量，把应执行的PV操作填入下述空格中，以保证进程能够正确地并发执行。 COBEGIN PROCESS PI(I=1，2，??) begin

进入售票厅； 购票；

退出； end COEND

(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。

答：(1)定义一信号量S，初始值为20。 (1’) 意义：(`3’=1’*3)

S>0 S的值表示可继续进入售票厅的人数 S=0 表示售票厅中已有20名顾客(购票者) S<0 |S|的值为等待进入售票厅的人数 (2)上空格为P(S) (2’) ；下空格为V(S) (2’)

(3)S的最大值为20 (1’ )；S的最小值为20－n (1’ )

9在公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开门关门，当售票员关好车门后，驾驶员才能开车行使。试用P/V操作实现司机与售票员间的同步。 解答：semaphore mutex1=0,mutex2=0; (2’) main(){

cobegin driver() busman()

coend

} (2’) driver(){

while(true){

p(mutex1) 启动公共汽车

正常开车 到站停车 v(mutex2) }

} (3’) busman(){

while(true){

关车门 v(mutex1) 售票

p(mutex2) 开车门 上下乘客 }

} (3’)

10并发问题：设有两个优先级相同的进程p1, p2如下。令信号s1, s2的初值为0，已知z=2，试问p1, p2并发运行结束后x=? y=? z=?

进程p1 进程p2 y := 1 x := 1 y := y+2 x := x+1 v(s1) p(s1) z := y+1 x := x+y p(s2) v(s2) y := z+y z := x+z 解答：（分析过程略 2’）从结果来看，两个进程无论谁先谁后，结果都是一样的。(2’) x = 5; y = 12; z = 9 (6’)

11 试用信号量机制来描述下述前趋图

M1 M5 M2 M4 M3 M7

M8 解答：首先定义信号量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都为0，分别表示相对应的进程是否完成：(2’) COBEGIN (`8’=1’*8) Process M1: begin

V(S12) V(S13) V(S14) end

Process M2:

M6

4设系统中有150个可用的同类资源。在某时刻系统中的进程已获得的资源和最大请求资源如下所示，请用银行家算法分别判断完成下列请求时，系统是否安全？若安全，请给出进程的完成序列。如不安全，请说明原因。 进程 最大需求量 当前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0 (1) 进程p4当前请求25个资源； (2) 之后p4又提出35个资源的请求。

解答：系统当前剩余资源量为：150 – 25 – 40 – 45 = 40 (2’)

(1) 可以满足(2’)，假定先分配p4的25个资源，系统还剩15个。将这15个资源可先分配给p3，p3达到最大请

求，释放60个；之后可以分配给其他任何进程，系统中的进程都能顺利完成。由此可见，p2请求的25个资源可以满足，且能找到完成序列：p3，p1，p2，p4，…(4’)

(2) 当p4再提出35个资源请求时，系统还剩15，显然不能满足它的请求，让其阻塞等待。(2’)

5系统中有五个进程，分别为p1\\p2\\p3\\p4\\p5，四类资源分别为r1\\r2\\r3\\r4。某一时刻，系统剩余资源向量A=(1，2，3，0)。

（1） 用银行家算法试判断系统当前状态是否安全？

（2） 当进程p3提出对资源r3的剩余请求时，能否满足她？ （3） 系统初始配置的各类资源分别为多少？

?1?1? MAX??2??0??0?1?0???1 NEED??0??0212?750??356? ，

?852?636???0?1??1??0??0012?000??144? .

?632?014??解答：系统剩余资源向量 A=(1, 2, 3, 0) 。现在需求出各进程的剩余资源请求矩阵:

200?750??212? (2’)

?220?622??(1) 详细步骤省略。由于系统存在一个进程完成的安全序列P1\\P3\\P4\\P2\\P5(2’)，故系统状态是安全的(2’)。

(2) 进程P3提出对资源R3的剩余请求为1，由于系统剩余资源向量A=(1,2, 3, 0)，故可以假定分配给它。如果

能找到一个安全序列，就可以真正进行分配。当分配给P3一个资源时，系统剩余资源向量A=(1 ,2 ,2 , 0)。由此可见，仍然可以找到一个与(1)相同的安全序列。故可以满足P3的请求。(3’) (3) 系统初始配置的各类资源分别为(3 ,9 , 12 , 12 )。(1’)

第四章 调度 名词解释

1作业

用户在一次上机过程中要求计算机系统所做工作的集合。

2周转时间

是指从作业进入系统开始，到作业退出系统所经历的时间。

3响应时间

是分时系统的一个技术指标，指从用户输入命令到系统对命令开始执行和显示所需要的时间。

4作业调度

作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。

5进程调度

也称低级调度程序，它完成进程从就绪状态到运行状态的转化。实际上，进程调度完成一台物理的cpu转变成多台虚拟（或逻辑）的cpu的工作。

6交换调度

是基于系统确定的某个策略，将主存中处于等待状态或就绪状态的某个或某些进程交换到外存交换区中，以便将外存交换区上具备运行条件的进程换入主存，准备执行。引入交换调度的目的是为了解决主存紧张和提高主存的利用效率。

7剥夺式调度

当一个进程正在执行时，系统基于某种策略强行将处理机从占有者进程剥夺而分配给另一个进程的调度。这种调度方式系统开销大，但系统能及时响应请求。

8非剥夺式调度

系统一旦把处理机分配给某个进程之后，该进程一直运行下去，直到该进程完成或因等待某个事件发生时，才将处理机分配给其他进程。这种调度方式实现简单，系统开销小，但系统性能不够好。

简答题

1作业由哪几部分组成？各有什么功能？

答：作业由三部分组成：程序、数据和作业说明书。

程序和数据完成用户所要求的业务处理工作，作业说明书则体现用户的控制意图。

2试比较作业和进程的区别

答：一个进程是一个程序对某个数据集的执行过程，是分配资源的单位。作业是用户需要计算机完成某项任务，而要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成4个阶段。而进程是已提交完毕的程序所执行过程的描述，是资源分配的基本单位。 其主要区别关系如下：

（1）作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在内存中。

（2）一个作业可由多个进程组成。且必须至少由一个进城组成，但反过来不成立。

（3）作业的概念主要用在批处理系统中。像UNIX这样的分时系统中，则没有作业概念。则进程的概念则用在几乎所有的多道程序系统中。

3高级调度与低级调度的主要功能是什么？为什么要引入中级调度？

答:高级调度的主要功能是根据一定的算法,从输入的一批作业中选出若干作业,分配必要的资源,如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输入/输出进程），最后把它们的程序和数据调入内存，等待进程调度程序对其执行调度，并在作业完成后做善后处理工作。

低级调度的主要功能是根据一定的算法将cpu分派给就绪队列中的一个进程。 为了使内存中同时存放的进程数目不至于太多，有时需要把某些进程从内存移到外存上，以减少多道程序的数目，为此设立了中级调度.

4处理机调度一般分为哪三级？其中哪一级调度必不可少？为什么？

答：处理机调度一般可分为高级调度（作业调度）、中级调度和低级调度（进程调度） 。其中进程调度必不可少 。 进程只有在得到CPU之后才能真正活动起来，所有就绪进程经由进程调度才能获得CPU的控制权。实际上，进程调度完成一台物理的CPU转变成多台虚拟机（或逻辑）的CPU的工作，进程调度的实现策略往往决定了操作系统的类型，其算法优劣直接影响整个系统的性能。

5作业调度与进程调度之间有什么差别？二者间如何协调工作？

答：作业调度与进程调度之间的差别主要是：作业调度是宏观调度，它所选择的作业只是具有获得处理机的资格，但尚未占有处理机，不能立即在其上实际运行；而进程调度是微观调度，动态地把处理机实际地分配给所选择的进程，使之真正活动起来。另外，进程调度相当频繁，而作业调度执行的次数一般很少。

作业调度从外存的后背队列中选择一批作业调入内存，为它们创建进程，这些进程被送入就绪队列。进程调度从就绪队列中选出一个进程来，并把它的状态改为运行态，把cpu分配给它。当运行进程要等待某一事件时，就让出cpu，进入相应的阻塞队列，并进行进程调度。运行进程完成后，由作业调度进行善后处理工作。

综合题

1假定在单CPU条件下要执行的作业如下表所示。

表 作业列表

作 业 运 行 时 间 优 先 级 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2

作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。 ①用一个执行时间图描述使用非抢占式优先级算法时各自执行这些作业的情况： ②对于该算法，各个作业的周转时间是多少?平均周转时间是多少？

③对于该算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？ 解：⑴ 非抢占式优先级

J1 J4 J3 J5 J2 0 10 11 13 18 19 (3’) ⑵和⑶ 非抢占式优先级 (`7’=1’*7) JOB ts tr te T W J1 0 10 10 10 1 J2 1 1 19 18 18 J3 2 2 13 11 5.5 J4 3 1 11 8 8.0 J5 4 5 18 14 2.8

T

12.2 2.06

W

2在一个有两道作业的批处理系统中，作业调度采用短作业优先级调度算法，进程调度采用抢占式优先级调度算法。设作业序列如表4-9所示。 表4-9 作业列表

作业名 到达时间 预估计时间（分钟） 优先数 A 8:00 40 10 B 8:20 30 5 C 8:30 50 8 D 8:50 20 12

其中给出的作业优先数即为相应进程的优先数。其数值越小，优先级越高。要求： ①列出所有作业进入内存的时间及结束时间。 ②计算平均周转时间和平均带权周转时间。 解：①

8:00 8:20 8:30 8:50 9:10 10:00 10:20

(4’)

② (`6’=1’*6) JOB ts tsr te T A 8:00 8:00 9:10 70 B 8:20 8:20 8:50 30 C 8:30 9:10 10:00 90 D 8:50 8:50 10:20 90

D C B A T

70 2.2625

W

3有A、B、C、D、E，共5个待运行作业，各自估计的运行时间为9，6，3，5，x。试问采用哪种运行次序使得平均响应时间为最短？（答案依赖于x） 解答：

由于短作业优先调度算法可以使作业的平均周转时间最短，同样使作业的平均响应时间为最短。 (5’) 下面对x的取值进行讨论：(`5’=1’*5)

当09，作业的运行顺序应为C(3),D(5),B(6),A(9),E(x)

4有一个具有如下作业流的批处理处理系统，作业调度采用短作业优先，进程调度采用基于优先数的抢先式调度算法。下表给出的是作业序列和相应进程的优先数，优先数越小优先级越高。 作业名 到达时间 估计运行时间/min 优先数 1 8:00 40 4 2 8:20 30 2 3 8:30 50 3 4 8:50 20 5 (1) 列出所有作业进入内存时间及完成时间

(2) 计算作业的平均周转时间和平均带权周转时间

解答：

(1)作业进入内存时间与结束时间如下所示：(`4’=1’*4) 作业名 进入内存时间 结束时间 1 8:00 9:10 2 8:20 8:50 3 9:10 10:00

4 8:50 10:20 (2)各作业的周转时间为： (`4’=1’*4) 作业A：9:10 – 8:00 = 70 min 作业B：8:50 – 8:20 = 30 min 作业C：10:00 – 8:30 = 90 min

作业D：10:20 – 8:50 = 90 min

作业的平均周转时间为：(70+30+90+90)/4=70 min (1’)

作业的平均带权周转时间为：(70/40+30/30+90/50+90/20)/4=2.26 min (1’)

第五章 存储管理 名词解释

1物理地址

内存中各存储单元的地址由统一的基地址顺序编址，这种地址称为物理地址。

2逻辑地址

用户程序经编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为逻辑地址。

3逻辑地址空间

由程序中逻辑地址组成的地址范围叫做逻辑地址空间。

4物理地址空间

由内存中的一系列存储单元所限定的地址范围称作内存空间。

5重定位

把逻辑地址转变为内存物理地址的过程叫做重定位。

6静态重定位

在目标程序装入内存时所进行的重定位。

7动态重定位

在程序执行期间，每次访问内存之前进行的重定位。

8内部碎片

在一个分区内部出现的碎片（即被浪费的空间）称作内部碎片。如固定分区法会产生内部碎片。

9外部碎片

在所有分区之外新产生的碎片称作外部碎片，如在动态分区法实施过程中出现的越来越多的小空闲块，由于它们太小，无法装入一个小进程，因而被浪费掉。

10碎片

在分区法中，内存出现许多容量太小、无法被利用的小分区称作“碎片”。

11紧缩

移动某些已分区的内容，使所有作业的分区紧挨在一起，而把空闲区留在另一端，这种技术称为紧缩。

12可重定位地址

当含有它的程序被重定位时，将随之被调整的一种地址。

13固定分区法

内存中分区的个数固定不变，各个分区的大小也固定不变，但不同分区的大小可以不同，每个分区只可装入一道作业。

14动态分区法

各个分区是在相应作业要求进入内存时才建立的，使其大小恰好适应作业的大小。

15可再入代码

也称纯代码，是指那些在其执行过程本身不做任何修改的代码，通常由指令和常数组成。

16虚拟存储器

虚拟存储器是用户能作为可编程内存对待的虚拟存储空间，在这种计算机系统中实现了用户逻辑存储器与物理存储器的分离，它是操作系统给用户提供的一个比真实内存空间大得多的地址空间。

17抖动

页面抖动是系统中频繁进行页面置换的现象。即如果一个进程没有一定数量的内存块，它很快就发生缺页。此时，它必须淘汰某页。由于所有这些页面都正在使用，所以刚被淘汰出去的页很快又被访问，因而要把它重新调入。可是调入不久又再被淘汰出去，这样再访问，再调入，如此反复，使得整个系统的页面替换非常频繁，以致大部分机器时间都用在来回进行的页面调度上，只有一小部分时间用于进程的实际运算方面。

18工作集

工作集是一个进程在某一小段时间内访问页面的集合。利用工作集模型可防止抖动，也可以进行页面置换。

19程序局部性原理

在相对短的一段时间内，进程集中在一组子程序或循环中之行，导致所有的存储器访问局限于进程地址空间的一个固定子集。这种现象就叫做程序局部性原理。

20快表

又叫“联想存储器”。在分页系统中，由于页表是存放在主存中的，因此cpu存取一个数据时要访问两次主存。这样使计算机的处理速度降低约一倍。为了提高地址变换速度，在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器，用以存放当前访问的页表项。这样的高速缓冲存储器就是快表。

21交换

交换系统指系统根据需要把主存中暂时不运行的某个（或某些）作业部分或全部移到外存。而把外存中的某个（或某些）作业移到相应的主存区，并使其投入运行。

22换页

指系统根据某种策略选择某页出主存，将某页调入主存的过程。

23实存

实存是指计算机配置的物理存储器，它直接向cpu提供程序和数据。

24虚存

虚存是指系统向用户程序提供的编程空间，其大小由cpu的地址长度决定。

简答题

1解释固定分区法和动态分区法的基本原理。

答：固定分区法——内存中分区的个数固定不变，各个分区的大小也固定不变，但不同分区的大小可以不同。每个分区只可装入一道作业。

动态分区法——各个分区是在相应作业要进入内存时才建立的，使其大小恰好适应作业的大小。

2说明内部碎片和外部碎片的不同之处

答：内存中出现的其容量太小、无法被利用的小分区称作碎片 。内部碎片和外部碎片出现的位置不同 。内部碎片出现在一个分区的内部（即被浪费的空间），如固定分区法会产生内部碎片 。外部碎片出现在所有分区之外，是新增的小分区，如在动态分区法实施过程中会出现外部碎片 。

3动态重定位分区管理方式中如何实现虚-实地址映射？

答：作业装入内存时，是将该用户的程序和数据原封不动地装入到内存中 。当调度该进程在cpu上执行时，操作系统就自动将该进程在内存的起始地址装入基址寄存器，将进程的大小装入限长寄存器 。当执行指令时，如果地址合法，则将相对地址与基址寄存器中的地址相加，所得结果就是真正要访问的内存地址；如果地址越界，则发出相应中断，进行处理 。

4什么是虚拟存储器？它有哪些基本特征？

答:虚拟存储器是用户能作为可编址内存对待的虚拟存储空间,在这种计算机系统中实现了用户逻辑存储器与物理存储器的分离,它是操作系统给用户提供的一个比真实内存空间大得多的地址空间。

虚拟存储器的基本特征是:虚拟扩充——不是物理上,而是逻辑上扩充了内存容量;部分装入——每个作业不是全部一次性地装入内存,而是只装入一部分;离散分配——不必占用连续的内存空间,而是”见缝插针”;多次对换——所需的全部程序和数据要分成多次调入内存。

5引入虚拟存储器后，除了获得主存“扩充”的好处，还有什么好处？

答：引入虚存后，程序的地址空间都是虚地址的集合，只有在程序运行中通过硬件地址转换机构和操作系统的相应软件，才能将虚地址变换成主存的实地址，这将为主存的分配带来更大的灵活性。另外，虚、实地址分开，用户程序不能干扰实地址的生成，从而实现了存储器的保护 。

6什么是分页？什么是分段？二者有何主要区别？

答：分页是由系统将一个进程的逻辑地址空间划分成若干大小相等的部分，每一部分称做一个页面。 分段是用户根据作业的逻辑关系进行自然划分，每个分段是作业中相对独立的一部分。

分段和分页都是非连续的存储管理方法， 分页和分段的主要区别有：

①页是信息的物理单位，段是信息的逻辑单位。

②页面的大小由系统确定，并且各页大小都相同；各段长度因段而已，由用户决定。 ③分页的作业地址空间是一维的，分段的作业的地址空间是二维的。 ④分页的活动对用户是不可见的，而分段是用户可见的活动。

7在分页系统中页面大小由谁决定？页表的作用是什么？如何将逻辑地址转换成物理地址？

答:在分页系统中页面大小由硬件决定。

页表的作用是:实现从页号到物理块号的地址映射。

逻辑地址转换成物理地址的过程是:用页号P去检索页表，从页表中得到该页的物理块号，把它装入物理地址寄存器中。同时，将页内地址d直接送入物理地址寄存器的块内地址字段中。这样，物理地址寄存器中的内容就是由二者拼接成的实际访问内存地址，从而完成了从逻辑地址到物理地址的转换。

8什么是belady现象？

答：belady现象是指在使用FIFO算法进行内存页面置换时 ，在未给进程或作业分配足它所要求的全部页面的情况下，有时出现的分配的页面数增多，缺页次数发而增加的奇怪现象。

9请求分页技术的基本思想是什么？它与简单分页技术之间有何根本区别？

答：请求分页技术的基本思想是：当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入内存。这样，就减少了对换时间和所需内存数量，允许增加程序的道数。

请求分页技术是在简单分页技术基础上发展起来的，两者根本区别是：请求分页提供虚拟存储器，而简单分页系统并未提供虚拟存储器。

10为什么分段技术比分页技术更容易实现程序或数据的共享和保护？

答： 每一段在逻辑上是相对完整的一组信息，分段技术中的共享是在段一级出现的。这样，任何共享的信息就可以单独成为一段。同样，段中所有内容可以用相同的方式进行使用，从而规定相同的保护权限。 然而，页是信息的物理单位，在一页中可能存在逻辑上互相独立的两组或多组信息，各有不同的使用方式和存取权限，因而，对分页难以进行共享和保护。

11何谓工作集？它有什么作用？

答：工作集是一个进程在某一小段时间内访问页面的集合。 利用工作集模型可防止抖动，也可以进行页面置换。

12什么是页面抖动？系统怎样检测是否出现抖动？一旦检测到抖动？系统如何消除它？

答：页面抖动是系统频繁进行页面置换的现象。整个系统的页面替换非常频繁，以致大部分机器时间都用在来回进行的页面调度上，只有一小部分时间用于进程的实际运算方面。

操作系统监督每个进程的工作集，并给它分配工作集所需的内存块。若有足够多的额外块，就可以装入并启动另外的进程。如果工作集增大了，超出可用块的总数，即系统中全部进程对内存块的总请求量大于可用内存块的总量，将出现抖动，因为某些进程得不到足够的内存块。

一旦检测到抖动，操作系统要选择一个进程让它挂起，把它的页面写出去，把它占用的内存块分给别的进程。被挂起的进程将在以后适当时机重新开始执行。

综合题

1考虑下面页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 当内存块数量分别为3时，试问LRU,FIFO,OPT三种置换算法的缺页次数各是多少？（注意，所有内存最初都是空的，凡第1次用到的页面都产生一次缺页） 答： LRU

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 1 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6 3 3 3 3 3 6 6 6 6 3 3 3 3 3 3 3 3 3 × × × × × × × × × × × × × × × (2’) FIFO

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 1 1 1 4 4 4 4 6 6 6 6 3 3 3 3 2 2 2 2 6 2 2 2 2 1 1 1 2 2 2 2 7 7 7 7 1 1 1 1 3 3 3 3 5 5 5 1 1 1 1 6 6 6 6 6 3 3 × × × × × × × × × × × × × × × × (2’)

OPT

1 2 3 1 1 1 2 2 3 × × ×

内存块数 3

4 1 2 4 × 2 1 2 4 1 1 2 4 5 1 2 5 × 6 1 2 6 × 2 1 2 6 1 1 2 6 2 1 2 6 3 3 2 6 × 7 3 7 6 × 6 3 7 6 3 3 7 6 2 3 2 6 × 1 3 2 1 × 2 3 2 1 3 3 2 1 6 3 2 6

× (2’)

置换算法 FIFO 16

LRU 15 OPT

11 (3’)

2考虑下面存储访问序列，该程序大小为460字：10，11，104，170，73，309，185，245，246，434，458，364

设页面大小是100字，请给出该访问序列的页面走向。又设该程序基本可用内存是200字，采用FIFO置换算法，求出缺页率。如果采用LRU算法，缺页率是多少？如果采用最优淘汰算法，其缺页率又是多少？ 解:

该序列的页面走向为：0、1、0、3、1、2、4、3。 (1’) FIFO 0 1 0 3 1 2 4 3 0 0 0 3 3 3 4 2 1 1 1 1 2 2 3 × × × × × × (2’)

LRU 0 1 0 3 1 2 4 3 0 0 0 0 1 1 4 4 1 1 3 3 2 2 3 × × × × × × × (2’)

OPT 0 1 0 3 1 2 4 3 0 0 0 3 3 3 3 3 1 1 1 1 2 4 4 × × × × × (2’)

算法 FIFO LRU OPT 缺页次数 6 7 5 缺页率 6/12=0.5 7/12=0.583 5/12=0.417 (3’)

3设某页系统中，页帧大小为100字。一个程序大小为1200字，可能的访问序列如下： 10，205，110，735，603，50，815，314，432，320，225，80，130，270

系统采用LRU算法。当为其分配4个主存块时，给出该作业驻留的各个页的变化情况及页故障数。 答：

首先将逻辑地址变换成页号。这样10，205，110，735，603，50，815，314，432，320，225，80，130，720，通过除以页的大小100，页号分别为0，2，1，7，6，0，8，3，4，2，0，1，2。(3’) 系统为运行进程分配4个主存块，采用LRU算法，因此可以列表给出进程的缺页情况： 0 2 1 7 6 0 8 3 4 3 2 0 1 2

0

2 0

1 2 0

7 1 2 0

6 7 1 2

0 6 7 1

8 0 6 7

3 8 0 6

4 3 8 0

3 4 8 0

2 3 4 8

0 2 3 4

1 0 2 3

2 1 0 3

F F F F F F F F F S F F F S (5’)

由上表可见，被淘汰的页依次为0，2，1，7，6，0，8，4。缺页次数为12次 (2’)

4某请求页式管理系统，用户编程空间有40个页面，每个页面为200H字节。假定某时刻用户页表中虚页号和物理块号对照表如下： 虚页号 0 2 5 17 20 物理块号 5 20 8 14 36

求虚地址0A3CH、223CH分别对应的物理地址。 答：

虚地址0A3CH转换成十进制数为2620，每个页为200H，即512B，由2620/512可得，页号为5，页内地址为60。查页表可知，其主存块号为8。(3’)

因此地址为2620的物理地址为：8*512+60=4156。(2’)

虚地址223CH转换成十进制数为8762，由8762/512可得，其页号为17，页内地址为58。查页表可知，其主存块号为14。(3’)

因此地址为8762的物理地址为14*512+58=7226。(2’)

5某系统采用页式存储管理策略，拥有逻辑空间32页，每页2KB；拥有物理空间1MB。 1） 写出逻辑地址的格式

2） 若不考虑访问权限位，进程的页表有多少项？每项至少多少位？ 3） 如果物理空间减少一半，页表结构应作怎样的改？ 答：

1）逻辑空间32页，占5个二进制位。每页2KB，占11位。故描述逻辑空间需要16位(2’)。 15 … 11 10 … 0

逻辑地址的格式：[ | ] (1’)

2)进程的页表有32项，每项的位数由主存的分块数决定(2’)。1MB的空间可划分为512个2KB的块，每个块用9个二进制位表示(2’)。

3）如果物理空间减少一半时，主存地址需要19位表示，仍大于逻辑空间的大小，故页表结构可以不变。(3’)

6有一虚拟存储系统，采用先进先出（FIFO）的页面淘汰算法。在主存忠为每一个作业进程开辟3页。某作业运行中使用的操作数所在的页号依次为：4，3，2，1，4，3，5，4，3，2，1，5。 1） 该作业运行中总共出现多少次缺页？

2） 若每个作业进程在主存拥有4页，又将产生多少次缺页？ 3） 如何解释所出现的现象？ 解：

先进先出算法的实质是：总是选择作业中在主存驻留时间最长的一页进行淘汰。

若在主存中为每一作业进程开辟3页，对于题中的页面访问过程，其页面调度过程如下所示

4 3 2 1 4 3 5 4 3 2 1 5 页面1 4 4 4 1 1 1 5 5 5 5 5 5 页面2 3 3 3 4 4 4 4 4 2 2 2 页面3 2 2 2 3 3 3 3 3 1 1 缺页中断 F F F F F F F F F (3’) 1） 该作业运行中总共出现9次缺页(1’)

2） 在主存拥有4页，又将产生10次缺页(1’)。其页面调度过程见下图：

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

页面1 4 4 4 4 4 4 5 5 5 5 1 1 页面2 3 3 3 3 3 3 4 4 4 4 5 页面3 2 2 2 2 2 2 3 3 3 3 页面4 1 1 1 1 1 1 2 2 2 缺页中断 F F F F F F F F F F (3’)

3)从这个例子可以看出，当主存中为每一作业进程开辟4页时，出现了缺页次数反而增加的现象。这种现象称为

Belady现象。(2’)

7关于存储管理，试问：

（1） 在分页、分段和段页式存储管理中，当访问一条指令或数据时，需要访问内存几次？各做什么处理？ （2） 假设一个分页存储系统具有快表，多数活动页表都可以存在其中，页表放在内存中，内存访问时间是1us。

若快表的命中率是85%，快表的访问时间为0.1us，则有效存取时间为多少？若快表命中率为50%，那么有效存取时间为多少？

解答：（1）分页需要访问2次，第一次访问页表，第二次执行访内操作(2’)；分段需要访问2次，第一次访问段表，第二次执行访内操作；段页式需要访问3次，第一次访问段表，第二次访问页表，第三次执行访内操作(2’)。 （2）当快表的命中率为85%时，执行一次访内操作需要的时间： T=1*0.85+2*(1-0.85)=1.15(us) (3’)

当快表的命中率为50%时，执行一次访内操作需要的时间： T=1*0.5+2*(1-0.5)=1.5(us) (3’)

8在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：

（1）按FIFO调度算法将产生多少次缺页中断，依次淘汰的页号为多少，缺页中断率为多少。 （2）按LRU调度算法将产生多少次缺页中断，依次淘汰的页号为多少，缺页中断率为多少。 答：

页面走向为：1，2，1，0，4，1，3，4，2，1

（1）按FIFO调度算法将产生5次缺页中断；依次淘汰的页号为：0，1，2； 缺页中断率为：5/10=50% (3’) 1 2 1 0 4 1 3 4 2 1 0 0 0 0 0 4 4 4 4 4 4 1 1 1 1 1 1 3 3 3 3 2 2 2 2 2 2 2 2 1 × × × × × (2’)

（2）按LRU调度算法将产生6次缺页中断；依次淘汰的页号为：2，0，1，3； 缺页中断率为：6/10=60% (3’) 1 2 1 0 4 1 3 4 2 1 0 0 0 0 0 0 0 3 3 3 3 1 1 1 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 1 × × × × × × (2’)

9一台计算机含有65536字节的存储空间，这一空间被分成许多长度为4096字节的页。有一个程序，其代码段为32768字节，数据段为16386字节，栈段为15870字节。试问该机器的主存空间适合这个进程吗？如果将每页改成512字节，合适吗？ 答：

当存储空间每块为4096B时，共可分成16块。其中： 程序代码段占：32768/4096=8块； (1’) 数据段占：16386/4096=5块； (1’) 栈段占：15870/4096=4块； (1’) 合计为：8+5+4=17块； (1’)

故该机器的主存空间不适合这个作业。 (1’)

当存储空间每块为512B时，共可分成128块。其中： 程序代码段占：32768/512=64块； (1’) 数据段占：16386/512=32块； (1’) 栈段占：15870/512=31块； (1’) 故合计为：64+32+31=127块。 (1’)

故该机器的主存空间是适合这个作业的。 (1’)

10一个请求分页系统中，内存的读/写周期为8纳秒，当配置有快表时，查快表需要1纳秒，内外存之间传送一个页面的平均时间为5000纳秒。假定快表的命中率为75%，页面失效率为10%，求内存的有效存取时间。 答：

访问主存的时间可用下面公式表示：

访问主存时间=主存的命中率*（快表的命中率*访问快表的时间+执行实际操作访问主存的时间）+页面失效率*页面失效时的访问时间 (6’)

因此 TA=(1-0.1)*[0.75*1+(1-0.75)*(8+1)+8]+0.1*5000 (4’)

11在一个虚拟存储器系统中，一次访问主存的时间用TA1表示，一个访问外存的时间用TA2表示。假定TA1=10^-7秒，TA2=10^-2秒。试问，为了使访问效率达到80%以上，命中率H至少应该达到多少？ 答：

访问效率：e=TA1/TA=0.8 (2’) TA=TA1/0.8=1.25*10^-7 s ( 2’) TA=H*TA1+(1-H)*TA2=H(TA1-TA2)+TA2 H=(TA-TA2)/(TA1-TA2) (2’)

解得 H=(1.25*10^-7-10^-2)/(10^-7 – 10^-2)=0.999975 (2’)

因此，为了使访问效率达到80%以上，命中率H至少应该达到0.999975。(2’)

第六章 文件系统 名词解释

1逻辑记录

用户构造文件时使用的一个信息单位。通常以逻辑记录为单位存取文件。

2物理记录

文件存储器上组织信息的一个单位。它是文件存储器识别信息的单位。

3文件

是命名的相关信息的集合体，它通常存放在外存（如磁盘、磁带）上，可以作为一个独立单位存放并实施相应的操作（如打开、关闭、读、写等）。

4文件系统

操作系统中负责操纵和管理文件的一整套设施，它实现文件的共享和保护，方便用户“按名存取”。

5目录项

为了加快对文件的检索，把文件控制块集中在一起进行管理。这种文件控制块的有序集合称为文件目录。当然，文件控制块也是其中的目录项。

6目录文件

全由目录项构成的文件成为目录文件。

7路径

在树形目录结构中，从根目录出发经由所需子目录到达指定文件的通路。

8当前目录

为节省文件检索的时间，每个用户可以指定一个目录作为当前工作目录，以后访问文件时，就从这个目录开始向下顺序检索。这个目录就称作当前目录。

9文件的逻辑组织

用户对文件的观察和使用是从自身处理文件数据时所采用的组织方式来看待文件组织形式。这种从用户观点出发所见到的文件组织形式称为文件的逻辑组织。

10文件的物理组织

文件在存储设备上的存储组织形式称为文件的物理组织。

11文件控制块

用于描述和控制文件的数据结构，其中包括文件名、文件类型、位置、大小等信息。文件控制块与文件一一对应，即在文件系统内部，给每个文件唯一地设置一个文件控制块，核心利用这种结构对文件实施各种管理。

12存取权限

用户或系统为文件规定的谁能访问，以及如何访问的方式

简答题

1什么是文件、文件系统？文件系统有哪些功能？

答：在计算机系统中，文件被解释为一组赋名的相关字符流的集合，或者是相关记录的集合。 文件系统是操作系统中与管理文件有关的软件和数据。

文件系统的功能是为用户建立文件，撤销、读写修改和复制文件，以及完成对文件的按名存取和进行存取控制。

2文件系统一般按什么分类？可以分为那几类？

答：文件系统一般按性质，用途，组织形式，文件中的信息流向或文件的保护级别等分类：按文件的性质与用途可以分为系统文件，库文件和用户文件。按文件的组织形式可以分为普通文件，目录文件和特殊文件。按文件中的信息流向可以分为输入文件，输出文件和输入/输出文件。按文件的保护级别可以分为只读文件，读写文件，可执行文件和不保护文件。

3什么是文件的逻辑结构，什么是记录？

答：文件的逻辑结构就是用户可见的结构，可分为字符流式的无结构文件和记录式的有结构文件两大类。

记录是一个具有特定意义的信息单位，它由该记录在文件中的逻辑地址（相对位置）与记录名所对应的一组关键字，属性及其属性值所组成。

4什么是文件目录？文件目录中包含那些信息？

答：一个文件的文件名和对该文件实施控制管理的说明信息称为该文件的说明信息，又称为该文件的目录。

文件目录中包含文件名、与文件名相对应的文件内部标识以及文件信息在文件存储设备上第一个物理块的地址等信息。另外还可能包含关于文件逻辑结构、物理结构、存取控制和管理等信息。

5文件系统中目录结构主要有哪几种？分别说明各自的实现思想？

答：文件系统中的目录结构主要有：单级目录结构，二级目录结构，树形目录结构和非循环图目录结构。 单级目录结构——在这种组织方式下，全部文件都登记在同一目录中。

二级目录结构——在主文件目录中登载了各个用户的名称，每个用户有自己的用户文件目录。

树形目录结构——在这种结构中，只有一个根目录，每一级目录可以是下级目录的说明，也可以是包含文件的说明。从根开始一层一层地扩展下去，就形成一个树形层次结构。

非循环图目录结构——树形目录结构的自然推广就是非循环图目录结构，它允许一个文件或目录可在多个父目录中占有项目，但并不构成环路。

6什么是文件控制块?它与文件有何关系？

答：文件控制块——用于描述和控制文件的数据结构，其中包括文件名、文件类型、位置、大小等信息。

文件控制块与文件一一对应，即在文件系统内部，给每个文件唯一地设置一个文件控制块，核心利用这种结

构对文件实施各种管理。

7文件系统中的目录结构有哪几种基本形式？各有何优缺点？

答：文件系统中的目录结构有：单级目录结构、二级目录结构、树形目录结构和非循环图目录结构，UNIX采用非循环图目录结构，即带链接的树形目录结构。

文件系统目录结构 优点 缺点

单级目录结构

简单、能实现按名存取

查找速度慢；不允许重名；不便于共享

二级目录结构 允许重名；提高了检索目录的速度 仍不利于文件共享

树形目录结构 文件的层次和隶属关系清晰，便于 只能在用户级对文件进行临时共享

实现不同级别的存取保护和文件系统 的动态装卸

非循环图目录结构

具有树形结构的优点，而且实现对 管理较复杂 文件的永久共享

8常用的磁盘空闲区管理技术有哪几种？试简要说明各自的实现思想。

答：常用的磁盘空闲区管理技术有：空闲空间表达法、空闲块链接法、位示图法和空闲块成组链接法。

空闲空间表法——所有连续的空闲盘块在表中占据一项，其中标出第一个空闲块号和该项中所包含的空闲块个数，以及相应的物理块号。利用该表可进行盘块的分配和文件的删除时盘块的回收

空闲块链接法——所有的空闲盘块链在一个队列中，用一个指针（空闲区头）指向第一个空闲块，而各个空闲块中都含有下一个空闲块的块号，最后一块的指针项计为NULL，表示链尾。分配和释放盘块都在链首进行

位示图法——利用一串二进制的值来反映磁盘空间的分配情况，每个盘块都对应一位。如果盘块是空闲的，对应位是0；如盘块已分出去，则对应位是1。

空闲块成组链法——把所有空闲盘块按固定数量分组，组与组之间形成链接关系，最后一组的块号（可能不满一组）通常放在内存的一个专用栈结构中。这样，对盘块的分配和释放是在栈中进行（或构成新的一组）.

9什么是文件共享？文件链接如何实现文件共享？

答：文件的共享是指系统允许多个用户（进程）共同使用某个或某些文件。

文件链接是给文件起别名，即将该文件的目录项登记在链接目录中。这样，访问该文件的路径就不只一条。不同的用户（进程）就可以利用各自的路径来共享同一文件。

10什么是文件后备？数据转储方法有哪两种？按时间划分，后备分哪几种？ 答：文件的后备就是把硬盘上的文件转储到其他外部介质上。

将磁盘上的数据转储到磁带上有两种方式：物理转储和逻辑转储。物理转储是从磁盘上第0块开始，把所有的盘块按照顺序写到磁带上，当复制完最后一块时，转储结束。逻辑转储方式是从一个或多个指定的目录开始，递归地转储自某个日期以来被修改过的所有文件和目录。

通常有以下三种备份策略：完全备份、增量备份和更新备份。

完全备份也称简单备份，即每隔一定时间就对系统作一次全面的备份；增量备份使每隔一段较短的时间进行一次备份，但仅仅备份在这段时间间隔内修改过的数据；更新备份是备份从上次进行完全备份后至今更改的全部数据文件。

11文件系统的一般格式是怎样的？其中引导块和超级块的作用各是什么？

答：文件系统的一般由引导块、超级块、空闲空间管理、I节点、根目录、文件数据区

引导块的作用是引导操作系统。它包括一个小程序，用于读入该分区上相应操作系统的引导部分，从而把该分区中的操作系统装入内存。

超级块的作用是对整个文件系统进行控制和管理。它包含有关文件系统的全部关键参数。当计算机加电进行引导或第一次遇到该文件系统时，就把超级块中的信息读入内存。超级块中包含标识文件系统类型的幻数、文件系统中的盘块数量、修改标记及其他关键管理方面的信息。

第七章 设备管理

名词解释

1输入井

是指为使设备与cpu速度相匹配，系统在磁盘上设置的多个缓冲区，以实现设备与cpu之间的数据交换。输入井主要用来存放由输入设备输入的信息。

2缓冲池

又叫公共缓冲区，也是系统在磁盘上设置的多个缓冲区。它既可以用于输入，也可以用于输出，较好地克服了专用缓冲区的缺点。一方面提高了缓冲区的利用率，另一方面也提高了设备与cpu的并行操作程度。

3虚拟设备

它是利用共享设备上的一部分空间来模拟独占设备的一种I/O技术。

4存储设备

它们是指计算机用来存储信息的设备，如此盘（硬盘和软盘）、磁带等。

5输入输出设备

是计算机用来接收来自外部世界信息的设备，或者将计算机加工处理好的信息送向外部世界的设备。例如键盘、打印机、卡片输入机。

6设备的无关性

也称设备独立性，就是说，用户程序应与实际使用的物理设备无关，由操作系统来考虑因实际设备不同而需要使用不同的设备驱动程序等问题。

7通道

为使CPU摆脱繁忙的I/O事务，现代大、中型计算机都设置了专门处理I/O操作的机构，这就是通道。

8 RAID

称作廉价磁盘冗余阵列，即利用一台磁盘阵列控制器来统一管理和控制一组磁盘驱动器（几台到几十台），组成一个高可靠性、快速大容量的磁盘系统。采用该技术可以获取更高的可靠性和更快的数据传输速率，而不是价格上更便宜。

简答题

1为什么要引入缓冲技术？设置缓冲区的原则是什么？

答：引入缓冲区的主要目的是：⑴缓和CPU与I/O设备间速度不匹配的矛盾。⑵提高它们之间的并行性。⑶减少对CPU的中断次数，放宽CPU对中断响应时间的要求。

设置缓冲区的原则是：如果数据到达率与离去率相差很大，则可采用单缓冲方式；如果信息的输入与输出速率相同（或者相差不大）时，则可用双缓冲区；对于阵发性的输入/输出，可以设立多个缓冲区。

2操作系统中设备管理的功能是什么？

答：对各种外部设备进行管理是操作系统的一个重要任务，也是其基本组成部分。 操作系统中设备管理的功能是： ① 监视设备状态； ② 进行设备分配； ③ 完成I/O操作；

④ 缓冲管理与地址转换。

3什么是缓冲？为什么要引入缓冲？

答：缓冲即是使用专用硬件缓冲器或在内存中划出一个区域用来暂时存放输入输出数据的器件。

引入缓冲是为了匹配外设和cpu之间的处理速度，减少中断次数和cpu的中断处理时间，同时解决dma或通道方式时的数据传输瓶颈问题。

4 I/O设备通常可分为哪两大类？各自传输的信息单位有什么特点？

答：I/O设备通常可分为字符设备和块设备。

字符设备通常以独占方式分配，信息的传输单位是字符或字节。块设备通常采用共享方式分配，信息的传输是以块为单位进行传输的。

5什么是I/O控制？,I/O操作的四种控制方式是什么？

答：I/O控制是指从用户进程的输入/输出请求开始，给用户进程分配设备和启动有关设备进行I/O操作，并在I/O操作完成之后响应中断,直至善后处理为止的整个系统控制过程 。

I/O操作的四种控制方式分别是：程序直接控制方式、中断I/O控制方式、DMA控制方式、I/O通道控制方式 。

6 I/O控制可用那几种方式实现，各有什么优缺点？

答：I/O控制过程可用三种方式实现：作为请求I/O操作的进程实现；作为当前进程的一部分实现；由专门的系统进程——I/O进程完成。

第一种方式请求对应I/O操作的进程能很快占据处理机，但要求系统和I/O操作的进程具有良好的实时性。第二种方式不要求系统具有高的实时性，但I/O控制过程要由当前进程负责。第三种方式增加了一个额外的进程开销，但用户不用关心I/O控制过程。

7设备分配技术主要有哪些？常用的设备分配算法是什么？

答：设备分配技术主要有：独占分配、共享分配和虚拟分配。

常用的设备分配算法是：先来先服务算法和优先级高的优先服务算法。

8实现SPOOLing系统的硬件前提是什么？SPOOLing系统的主要功能是什么？

答：实现SPOOLING系统的首先要有硬件支持：要提供大容量的磁盘，要有中断和通道装置，以便使外围设备与中央处理器能够并行工作。 它是为了满足多道程序或多进程队独占设备的共享使用而引入的，其主要功能即是：将独占设备改造为共享设备，实现虚拟设备 。

9简述处理I/O请求的主要步骤。

答：处理I/O请求是一个系统获取用户I/O请求转发给相应外设完成的过程 ，其具体的处理步骤如下： ①用户进程发出I/O操作；

②系统接受这个I/O请求，转去执行操作系统的核心程序； ③设备驱动程序具体完成I/O操作；

④I/O完成后,系统进行I/O中断处理，然后用户进程重新开始执行

10设备驱动程序主要执行什么功能？

答：设备驱动进程严格执行设备驱动程序中规定的各种功能 ，即接受用户的I/O请求 ；取出请求队列中队首的请求，将相应的设备分配给它 ；启动该设备工作，完成指定的I/O操作 ；处理来自设备的中断 。

11 I/O软件的设计目标？它是如何划分层次的？各层的功能是什么？

答：I/O软件的设计目标：

①与设备无关

②对文件和设备应统一命名 ③层次结构 ④效率高

I/O软件可分为如下4个层次：中断处理程序、设备驱动程序、与设备无关的操作系统软件和用户级软件 。各层功能为：

①中断处理程序——分析中断原因，并依据中断原因调用相应的处理程序 ②设备驱动程序——它接受来自上层、与设备无关软件的抽象读写请求，并将该I/O请求排在请求队列的队尾，还要检查I/O请求的合法性；取出请求队列中对首请求，将相应设备分配给它；向该设备控制器发送命令，启动该设备工作，完成指定的I/O操作；处理来自设备的中断

③与设备无关的操作系统软件——其基本功能是执行所有驱动器共同的I/O功能和对用户级软件提供统一软件

④用户级软件——多数I/O软件都在操作系统中，用户空间中也有一小部分。通常，它们以库函数形式出现，在用户程序中可以调用它们

12什么叫寻道？访问磁盘时间由哪几部分组成?其中哪一个是磁盘调度的主要目标？为什么？

答: 把磁头从当前位置移到相应的磁道上或柱面上，这个操作过程叫做寻道。

访问磁盘一般要有三部分时间：寻道时间、旋转延迟时间和传输时间。 寻道时间是磁盘调度的主要目标。 传输时间是硬件设计时就固定的，寻道时间和旋转延迟时间与信息在磁盘上的位置有关。因为磁头臂是机械移动，所以对大多数磁盘来说，寻道时间远大于旋转延迟时间与传输时间之和，它是影响磁盘调度的主要因素。

13什么是RAID？采用RAID技术的优点是什么？

答：RAID称作廉价磁盘冗余阵列，即利用一台磁盘阵列控制起来统一管理和控制一组磁盘驱动器（几台到几十台），组成一个高可靠性、快速大容量的磁盘系统。

采用RAID技术可以获取更高的可靠性和更快的数据传输速率，而不是价格上更便宜。

综合题

1假定一个硬盘有100个柱面，每个柱面有10个磁道，每个磁道有15个扇区。当进程要访问磁盘的12345扇区

时，计算磁盘的三维物理扇区号。 解：

每个柱面的扇区数为：10*15=150 (3’)

12345/150=82余45,故12345扇区所在的柱面为82 (3’) 再将45/15，其商为3，余数为0，(3’)

故求得12345扇区所在的磁盘地址为：82柱面，3磁道，0扇区。(1’)

2假设移动头磁盘有200个磁道（0-199号）。目前正在处理143号磁道上的请求，而刚刚处理结束的请求是125号，如果下面给出的顺序是按FIFO排成的等待服务队列顺序：86，147，91，177，94，150，102，75，130 那么，下列各种磁盘调度算法来满足这些请求所需的总磁头移动量是多少？ 1）FCFS, 2)SSTF 解：

1） FCFS:125?143—86—147—91—177—94—150—102—75—130 (2’) 满足这些请求所需要的总磁头移动量为

(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(102-75)+(130-75) =57+61+65+86+83+56+48+27+55=529 (3’)

2) SSTF:125?143—147—150—130—102—94—91—86—75—177 (2’)

满足这些请求所需的总磁头移动量为

(150-143)+(150-75)+(177-75)=7+75+102=182 (3’)

3假设移动头磁盘有200个磁道（0-199号）。目前正在处理143号磁道上的请求，而刚刚处理结束的请求是125号，如果下面给出的顺序是按FIFO排成的等待服务队列顺序：86，147，91，177，94，150，102，75，130 那么，下列各种磁盘调度算法来满足这些请求所需的总磁头移动量是多少？

1)SCAN, 2)C-LOOK

解：

1)SCAN:125?143—147—150—177—199—130—102—94—91—86—75 (2’) (199-143)+(199-75)=56+124=180 (3’)

2)C-LOOK:125?143—147—150—177 —75—86—91—94—102—130 (2’) 满足这些请求所需要的总磁头移动量为

177-143+177-75+130-75=33+102+55=190 (3’)

4假设一个磁盘由200个磁道，编号从0~199。当前磁头正在143道上服务，并且刚刚完成了125道的请求。如果寻道请求队列的顺序是：86，147，91，177，94，150，102，175，130 问：为完成上述请求，下列算法各自磁头移动的总量是多少？ ①FCFS ②SSTF 解：

⑴FCFS磁头移动顺序:

143 ? 86 ? 147 ? 91 ? 177 ? 94 ? 150 ? 102 ? 175 ? 130 (2’) 57 61 56 86 83 56 48 73 45 磁头移动总量: 57+61+56+86+83+56+48+73+45=565 (3’) ⑵SSTF磁头移动顺序

143 ? 147 ? 150 ? 130 ? 102 ? 94 ? 91 ? 86 ? 175 ? 177 (2’) 4 3 20 28 8 3 5 89 2 磁头移动总量: 4+3+20+28+8+3+5+89+2=162 ( 3’)

5假设一个磁盘由200个磁道，编号从0~199。当前磁头正在143道上服务，并且刚刚完成了125道的请求。如果寻道请求队列的顺序是：86，147，91，177，94，150，102，175，130 问：为完成上述请求，下列算法各自磁头移动的总量是多少？

① SCAN ② C-SCAN 解：

（1）SCAN磁头移动顺序

143 ? 147 ? 150 ? 175 ? 177 ? 199 ?130 ? 102 ? 94 ? 91 ? 86 (2’) 4 3 25 2 22 69 28 8 3 5 磁头移动总量: 4+3+25+2+22+69+28+8+3+5=169 (3’)

（2）C-SCAN磁头移动顺序

143 ? 147 ? 150 ? 175 ? 177 ? 199 ? 0 ? 86 ? 91 ? 94 ? 102 ? 130 (2’) 4 3 25 2 22 199 86 5 3 8 28 磁头移动总量: 4+3+25+2+22+199+86+5+3+8+28=385 (3’)

6磁盘请求以10，22，20，2，40，6，38柱面的次序到达磁盘驱动器。寻道时每个柱面移动需要6ms，计算以下寻道次序和寻道时间：

①先到先服务 ②电梯调度算法（起始移动向上）

所有情况下磁臂的起始位置都是柱面20。 解: 寻道时间=柱面（磁道）移动总量×6ms 1） 先到先服务算法的调度顺序： 20 ? 10 ? 22 ? 20 ? 2 ? 40 ? 6 ? 38 (2’) 10 12 2 18 38 34 32 柱面移动总量=10+12+2+18+38+34+32=146 (2’) 寻道时间=146×6ms=876ms (1’)

2） 电梯算法的调度顺序： 20 ? 22 ? 38 ? 40 ? 10 ? 6 ? 2 (2’)

2 16 2 30 4 4

柱面移动总量=2+16+2+30+4+4=58 (2’) 寻道时间=58×6ms=348ms (1’)

7某系统文件存储空间共有80个柱面，20磁道/柱面，6块/磁道，每块有1K字节。用位示图表示。每张位示图为64个字，其中有4个包含的是控制信息。位示图中的位若为1，表示占用；为0表示空闲。试给出分配和回收一个盘块的计算公式。

解：每个柱面的块数为：20*6=120（块）(1’)

计算该文件系统的磁盘块：80*120=9600（块）(1’)

每张位示图为64个字，其中有4个字包含的是控制信息。假定每个字为16位。每张可以记录的块数为：(64-4)*16=960（块）(1’) 总共有9600块，用位示图表示，需要占用9600位，每张位示图可记录960块，需要的位示图数位：9600/960=10（张），用0~9进行编号。(1’) 1） 分配一个盘块的计算公式 (3’)

相对块号=位图的张号*960+字号*16+位号

柱面号=（相对块号/每个柱面的块数）的商=（相对块号/120）的商 磁盘号=（相对块号/每个柱面的块数）的余数的商 扇区号=（（相对块号/每个柱面的块数）的余数）的余数 2） 回收一个盘块的计算公式 (3’)

先将三维地址转换为相对块号，再将相对块号转换为位图的字号和位号。 相对块号=柱面号*120+磁盘号*6+扇区号 字号=（相对块号/16）的商 位号=（相对块号/16）的余数

第八章 中断和信号机制 名词解释

1 中断

是指CPU对系统发生的某个事件做出的一种反应，CPU暂停正在执行的程序，保留现场后自动地转去执行相应的处理程序，处理完该事件后，如被中断进程的优先级最高，则返回断点继续执行被“打断”的程序。

2中断源

引起中断的事件或发出中断请求的来源称为中断。

3中断请求

中断源向CPU提出进行处理的请求。

4中断向量

通常包括相应中断处理程序入口地址和中断处理时处理机状态字。

5异常

它是指来自cpu内部的事件或程序执行中的事件引起的中断

6程序性中断

是指因错误地使用指令或数据而引起的中断，用于反映程序执行过程中发现的例外情况，例如，非法操作码，无效地址、运算溢出，等等。

7断点

发生中断时，被打断程序的暂停点称为断点。

8中断响应

发生中断时，cpu暂停执行当前的程序，转去处理中断。这个由硬件对中断请求做出反应的过程，称为中断响应。

9中断屏蔽

是指在提出中断请求之后，cpu不予响应的状态。它常常用来在处理某个中断时防止同级中断的干扰，或在处理一段不可分割的、必须连续执行的程序时防止意外事件把它打断。

10中断禁止

是指在可引起中断的事件发生时系统不接收该中断的信号，因而就不可能提出中断请求而导致中断。简言之，就是不让某些事件产生中断。

11软中断

又称信号机制，它是在软件层次上对中断机制的一种模拟，其中，信号的发送者相当于中断源，而接收者（必定是一个进程）相当于cpu。

简答题

1什么是中断？什么叫中断处理？什么叫中断响应？

答：中断是指计算机在执行期间，系统内发生任何非寻常的或非预期的急需处理事件，使得cpu暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行的过程。

Cpu转去执行相应的事件处理程序的过程称为中断处理。 Cpu收到中断请求后转到相应的事件处理程序称为中断响应。

2什么叫关中断？什么叫开中断？什么叫中断屏蔽？

答：把cpu内部的处理机状态字psw的中断允许位清除从而不允许cpu响应中断叫做关中断。

设置cpu内部的处理机状态字psw的中断允许位从而允许cpu响应中断叫做开中断。 中断屏蔽是指中断请求产生之后，系统用软件方式有选择地封锁部分中断而允许其余部分的中断仍能得到响应。

3什么是陷阱？什么是软中断？

答：陷阱指处理机和内存内部产生的中断，它包括程序运算引起的各种错误，如地址非法、检验错、页面失效。存取访问控制错、从用户态到核心态的切换等都是陷阱的例子。

软中断是通信进程之间用来模拟硬中断的一种信号通信方式。

4中断响应主要做哪些工作？由谁来完成？

答：中断响应主要做的工作是： ①中止当前程序的执行；

②保存原程序的断点信息（主要是程序计数器PC和程序状态寄存器PS的内容）； ③转到相应的处理程序

中断响应由硬件实施。

5叙述缺页中断和一般中断的区别？

答：缺页中断也是中断的一种，既然是中断都应保护当前运行程序的现场信息，中断完成后恢复被中断的现场。但缺页中断是当前运行进程自己产生的中断，且当前指令还未执行完，故中断处理将所需的页调入主存后，应该恢复该进程重新执行被中断的这条指令。

对一般中断，中断源与当前正在执行的进程无关，故正在执行的进程执行完当前这条指令后才响应中断。中断处理完成后，可能恢复被中断的进程，也可能调度其他进程的运行。即使恢复被中断进程的运行，恢复后执行的指令也是中断发生时的下一条指令。

6什么是软中断？

答：软中断是对硬中断的一种模拟，发送软中断就是向接收进程的proc结构中的相应项发送一个特定意义的信号 。软中断必须等到接收进程执行时才能生效 。

7进程在什么时候处理它接收到的软中断信号？进程接收到软中断信号后放在什么地方？

答：进程在再次被调度执行时先检查是否收到软中断，若进程接收到了软中断信号则优先处理软中断 。进程把接收到软中断信号存放在proc结构的相应项中 。

8中断处理的主要步骤是什么？ 答：中断处理的一般步骤是:

保存被中断程序的现场， 分析中断原因，

转入相应处理程序进行处理， 恢复被中断程序现场（即中断返回）。

9什么叫系统调用？执行用户程序中的系统调用时，相应进程的状态会发生什么变化？

答：系统调用是用户在程序中能以“函数调用”形式调用的、由操作系统提供的子功能的集合。每一个子功能称作一条系统调用命令。它是操作系统对外的接口，是用户级程序取得操作系统服务的唯一途径。

执行到用户程序中的系统调用时，相应进程的状态从用户态变为核心态。

10在用户程序执行过程中，CPU接到盘I/O中断。对此，系统（硬件和软件）要进行相应处理，试列出其主要

处理过程。

答：硬件主要处理过程是：cpu中止当前程序的正常执行；保存原程序的程序计算器pc和程序状态寄存器ps的内容：取出盘I/O中断向量，转到相应的处理程序。

软件主要处理过程是：保存被中断程序的现场（如通用寄存器的内容）：分析中断原因，由中断向量得到盘I/O中断的处理程序地址；运行盘I/O中断处理程序，判断I/O工作是否完成，如正常完成，则作I/O结束处理；执行完中断处理程序，核心恢复前面保存的现场，进程回到用户态。

------------------------------------------------------------------------------------------------------------------------------------------------ 设置操作系统的目的：

1、方便性:操作系统使计算机更易于使用

2、有效性:操作系统允许以更有效的方式使用计算机系统资源。

3、可扩展性:在操作系统中,允许有效地开发，测试和引进新的系统功能。 4、开放性:实现应用程序的可移植性和互操作性,要求具有统一的开放的环境。 OS的作用

OS作为用户与计算机硬件系统之间的接口 OS作为用户与计算机系统资源的管理者 OS作为扩充机器

操作系统作为计算机系统资源管理者。 1、处理机管理：分配和控制CPU。 2、存储器管理：内存分配与回收。

3、I/O设备管理：I/O设备的分配与操纵。 4、文件管理：文件的存取、共享和保护。

●操作系统用作扩充机器功能，使其便于使用，这种只安装了OS的机器又称为虚拟机。

单道批处理系统

1、在内存中仅存一道作业运行，运行结束或出错，才自动调另一道作业运行。 2、单道批处理系统主要特征：自动性、顺序性、单道性。

3、单道批处理系统主要优点：减少人工操作，解决了作业的自动接续。

4、单道批处理系统主要缺点：平均周转时间长，没有交互能力。 多道批处理系统

一、多道程序的概念：

在内存中存放多道作业运行，运行结束或出错，自动调度内存中的另一道作业运行。 ●多道程序带来的好处： 1、提高CPU的利用率。

2、提高内存和I/O设备利用率。 3、增加系统吞吐率。

二、多道批处理系统主要特征：

多道性、无序性、调度性（进程调度和作业调度）。

三、多道批处理的主要优点：提高了资源利用率和吞吐能力。 多道批处理的主要缺点：平均周转时间长，没有交互能力。

例1．设在内存中有三道程序A、B和C，按A、B、C的优先次序运行，其内部计算和I／O操作时间由下图给出。

若处理机调度程序每次进行状态转换需要的时间为1ms，试画出按多道程序运行的时间关系图。并计算完成这三道程序共使用了多少时间？并计算比单道运行节省多少时间？

由图可计算出在多道程序运行下执行了196ms的时间，而在单道运行的时间为： 30＋1+40＋1＋10＋1+60＋1＋30＋1＋16＋1+20＋1＋40＋1＋20 ＝274ms

多道运行的时间为：

30+1+40+1+10+1+20+1+30+1+40+1+20=196 则多道程序比单道程序节省的时间为： 274一196＝ 78ms 分时系统的特征：

多路性：同时有多个用户使用一台计算机，宏观上看是多个人同时使用一个CPU，微观上是多个人在不同时刻轮流使用CPU。

独立性：用户感觉不到计算机为其他人服务，就像整个系统为他所独占。 及时性：系统对用户提出的请求及时响应。

交互性：用户根据系统响应结果进一步提出新请求(用户直接干预每一步)。“

所谓实时系统：是计算机及时响应外部 事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行。 一、实时系统分为两类 1、实时控制系统

2、实时信息处理系统 二、实时任务的类型

1、按任务执行是否为周期性来划分 2、按截止时间来划分 三、实时系统的特征

1、多路性：能对多个对象进行控制。 2、独立性：独立运行，不混淆，不破坏。

3、交互性：仅限于访问系统中某些特定的专用服务程序。 4、可靠性：高可靠性，应具有过载防护能力。

5、及时性：不同的系统要求不一样，控制对象必须在截止时间内完成。

?

是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以及方便用户的程序的集合。

现代OS的四个基本特征：

1、并发 2、共享 3、虚拟 4、异步

? 并发是最重要的特征，其它特征都以并发为前提。 ? 并发——并行性和并发性，并发执行的 过程。 - 并行性是指两个或多个事件在同一时刻发生。

- 并发性是指两个或多个事件在同一时间间隔内发生。

? 任务共行

- 从宏观上看，任务共行是指系统中有多个任务同时运行

- 从微观上看，任务共行是指单处理机系统中的任务并发（Task Concurrency：即多个任务在单个处理机上交替运行）或多处理机系统中的任务并行（Task Parallelism：即多个任务在多个处理机上同时运行）。

? 所谓共享是指系统中的资源可供内存中多个并发执行的进程共同使用。 1、互斥共享方式：

- 把在一段时间内只允许一个进程访问的资源，称为临界资源。

- 系统中的临界资源可以提供给多个进程使用，但一次仅允许一个进程使用，称为互斥共享方式。例如打印机。

2、同时访问方式：

- 从宏观上看，资源共享是指多个任务可以同时使用系统中的软硬件资源

- 从微观上看，资源共享是指多个任务可以交替互斥地使用系统中的某个资源。例如磁盘。

所谓虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。 虚拟处理机：分时实现

虚拟设备：SPOOLING技术 虚拟存储器：虚拟存储管理实现

异步性—— 是指进程以异步的方式执行，进程是以人们不可预知的速度向前推进。内存中的每个进程何时执行,何时暂停,以怎样的速度向前推进,每道程序总共需要多少时间才能完成等,都是不可预知的

? 操作系统是一个大型系统软件，其结构已经历了四代的变革：

? ? ? ?

整体式结构、核心结构和层次结构。

【例2】桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

分析 在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：

? ? ? ? ? ? ? ? ?

int S＝1; int Sa＝0; int So＝0;

main() {

cobegin

father(); /*父亲进程*/ son(); /*儿子进程*/ daughter(); /*女儿进程*/

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?

coend }

father() {

while(1) {

P(S);

将水果放入盘中;

if（放入的是桔子）V(So); else V(Sa); } } son() {

while(1) {

P(So);

从盘中取出桔子; V(S); 吃桔子;

} }

daughter() {

while(1) {

P(Sa);

从盘中取出苹果; V(S); 吃苹果; } }

四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：

（1）应定义的信号量及初值： 。

（2）在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作：

A() B() C() D() { { { {

[1]; [3]; [5]; [7];

read F; read F; read F; read F; [2]; [4]; [6]; [8]; } } } }

（1）定义二个信号量S1、S2，初值均为1，即：S1=1，S2=1。其中进程A和C使用信号量S1，进程B和D使用信号量S2。

? ? ? ? ? ? ? ? ?

? （2）从[1]到[8]分别为：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2) 第四章 存储器管理 一、程序的装入

1、绝对装入方式

直接用物理地址编制程序。 2、可重定位装入方式（静态重定位）

重定位——把在装入时对目标程序中的指令和数据地址的修改过程称为重定位。 3、动态运行时装入方式（动态重定位）

作业在存储空间的位置，也是装入时确定的，但在作业运行过程中，每次存访内存之前，将程序的地址（逻辑地址）变为内存的物理地址。这种变换是依靠硬件地址变换机构、自动连续实施，这样程序在内存的地址是可变的，可申请临时空间。 二、程序的链接

1、 静态链接——事先进行链接，以后不再拆开的链接方式，称为静态链接。

2、 装入时动态链接——编译后的目标模块，是在装入内存时，边装入，边链接的。

3、运行时动态链接——将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，再由操作系统去找到该模块，将它装入内存，并把它链接到调用者模块上。 4、静态链接需要共享目标模块的拷贝，而动态链接不需要共享目标模块的拷贝。 三、连续分配存储管理方式 1、 固定式分区

2、 动态分区分配——根据用户实际需要，动态的分配连续空间。 l 拼接技术

3、 动态重定位分区分配——采用动态重定位技术的分区分配。 l 紧凑技术

四、分区管理的算法

1、 首次适应算法：每个空白区按地址顺序链接在一起，表头指向第一个空白区。

2、 循环首次适应算法：将空白区构成循环链表。表头指向当前开始查找的第一个空白区。 3、 最佳适应算法：空白区按尺寸大小递增顺序构成队列。表头指向第一个空白区。 五、对换技术 （交换技术）

就是将主存中的信息以文件的形式写入到辅存，接着将指定的信息从辅存读入主存，并将控制转给它，让其在系统上运行。

六、分页存储器管理

1、在分页存储管理方式中，一个进程的逻辑地址空间分成若干个大小相等的片，称为页面。内存空间也分成与页相同大小的存储块，并将进程的每一个页面离散地存储在内存的任一物理块中，建立相应的页表，由系统实现进程的正确运行。

2、快表——为了提高地址变换速度，可在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲存储器，称为快表。

例：有一页式系统，其页表存放在主存中：

? ①如果对主存的一次存取需要1.5 μs,试问实现一次页面访问的存取时间是多少?

? ②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0, 试问此时的存取时

间是多少?

答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。

? ■页表在主存的存取访问时间 ? =1.5*2=3(μs)

? ■增加快表后的存取访问时间

? =0.85*1.5+(1-0.85)*2*1.5=1.725(μs) 七、分段存储管理

① 在分段存储管理方式中，一个作业的地址空间分成若干个段，每一段定义了一组逻辑信息，则为每个段分配连续的分区，而进程中的各段可以离散地存储在内存中不同的分区中，建立相应的段表，由系统实现进程的正确运行。

② 分页与分段存储管理的区别？ 答：P160或P121

本文来源：https://www.bwwdw.com/article/di17.html