2017考研计算机冲刺课程操作系统

操作系统1孙卫真optsys2001@冲刺班辅导材料第一章 操作系统概述2操作系统的概念、特征、功能和提供的服务操作系统的发展与分类操作系统的运行环境内核态与用户态中断、异常系统调用操作系统体系结构大纲要求操作系统的概念3OS作为用户与计算机硬件系统之间的接口OS作为计算机系统资源的管理者OS用作扩展机、虚拟机人机接口主要形式：系统调用（System

Call）命令输入（命令行、GUI、NUI）选择2015-23处理外部中断时，应该由操作系统保存的是A.

程序计数器(PC)的内容B.通用寄存器的内容C.快表(TLB)中的内容D.

Cache中的内容4操作系统的基本特性5并发(Concurrence)—最基本的特征！并行性和并发性是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生共享(Sharing)在操作系统环境下，所谓共享是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用操作系统的基本特性6虚拟(Virtual)操作系统中的所谓“虚拟”，是指通过某种技术把一个物理实体变为若干个逻辑上的对应物异步性(Asynchronism)在多道程序环境下，多个进程是以“停停走走”的方式运行失去封闭性选择2016-24．某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2

ms、3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是A．15msB．17msC．22

msD．27

ms7操作系统的发展过程无操作系统的计算机系统人工操作方式脱机输入/输出(Off-Line

I/O)方式单道批处理系统多道批处理系统分时系统实时系统8选择2016-23．下列关于批处理系统的叙述中，正确的是Ⅰ．批处理系统允许多个用户与计算机直接交互Ⅱ．批处理系统分为单道批处理系统和多道批处理系统Ⅲ．中断技术使得多道批处理系统的I/O设备可与CPU并行工作A．仅Ⅱ、ⅢC．仅Ⅰ、ⅡB．仅Ⅱ

D．仅Ⅰ、Ⅲ9操作系统的运行环境内核态与用户态中断、异常系统调用10内核态与用户态11内核态与用户态是指进程（线程）在执行代码过程中为了安全保护而设置的二个不同的阶段。内核态可以执行所有的系统代码，包括特权指令；而用户态只能执行用户的代码。若用户需要执行特权代码时，必须发起一次系统调用。内核态与用户态操作系统代码，系统调用，共享库用户进程1计算机资源用户进程2用户进程5用户进程3用户进程4内核态用户态系统调用 访管指令12特权指令内核态与用户态一般示例：用户代码不能互访内核代码也不能访问用户代码中断、异常13所谓中断（interrupt）是指处理机对系统中或系统外发生的异步事件的响应。异常（有时也称为陷阱trap）是指由系统发起的一次确定的服务过程（也称为软中断）中断、异常14访管指令不是特权指令用户从用户态进入内核态必定通过访管指令从内核态返回用户态可以修改状态字实现系统调用15系统调用是指当用户需要使用某些计算机资源时，因为这些资源是被操作系统所控制的，用户不能直接使用该资源，而是必须向操作系统提出“请求”，由操作系统安排合理、高效、安全地使用这些资源这种“请求”便称为系统调用这种“请求”的格式通常是指令名加上请求的服务识别号（有时是中断号）选择2012-23．下列选项中，不可能在用户态发生的事件是A．系统调用B．外部中断C．进程切换D．缺页16选择2013-28．下列选项中，会导致用户进程从用户态切换到内核态的操作是I．整数除以零II．sin()函数调用III．read系统调用A．仅I、IIB．仅I、IIIC．仅II、IIID．I、II和III17选择2014-25．下列指令中，不能在用户态执行的是A．trap指令B．跳转指令C．压栈指令D．关中断指令18操作系统的体系结构19单一结构分层结构客户/服务器结构（微内核）虚拟机结构本章重要习题分析20以概念题为主其中：OS的目标、作用，人机接口，OS特性以及OS的主要功能是考查重点形式以选择题（包括多项组合题）为主，鲜有综合题占2-6分，趋势是减少。第二章 进程管理进程与线程处理机调度同步与互斥死锁进程与线程进程概念、进程的状态与转换、进程控制、进程组织、进程通信（共享存储系统；消息传递系统；管道通信）、线程概念与多线程模型处理机调度调度的基本概念、调度时机、切换与过程、调度的基本准则、调度方式、典型调度算法（先来先服务调度算法；短作业（短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法）同步与互斥进程同步的基本概念、实现临界区互斥的基本方法（软件实现方法；硬件实现方法）、信号量、管程、经典同步问题（生产者-消费者问题；读者-写者问题；哲学家进餐问题）死锁死锁的概念、死锁处理策略、死锁预防、死锁避免（系统安全状态；银行家算法）、死锁检测和解除大纲要求进程与线程进程的基本概念进程的状态与转换进程控制进程组织进程通信线程概念与多线程模型进程的基本概念一个具有一定独立功能的程序对某个数据集合上的一次动态执行过程和资源分配过程进程的元素：代码、数据、进程表（进程控制块）Code、Data、PT（PCB）进程和程序的区别与联系进程是动态的，程序是静态的进程是暂时的，程序是永久的进程和程序的组成不同程序主要包含代码和数据进程除了包含代码和数据以外，还有进程表进程和程序间有非常紧密的联系程序经过多次创建，可以对应不同的进程一个进程通过系统调用，可以被多个程序所使用示例进程包含（）、（）和（）数据；记录项；目录；代码；进程表；文件，共享库示例（）是进程存在的唯一标志数据；记录项；目录；代码；进程表；文件，共享库进程的三种基本状态及其转换就绪(Ready)状态执行(Running)状态阻塞(Blocking)状态进程控制进程的创建（创建原语）进程的创建过程申请空白进程表为新进程分配资源初始化进程表将新进程插入就绪队列示例进程创建后，所有创建完成后的进程PCB被链接成一个序列，这个序列称为什么？阻塞序列挂起序列就绪序列运行序列选择2011-25下列选项中，导致创建新进程的操作是I．用户登录成功II．设备分配III．启动程序执行A．仅I和IIB．仅II和IIIC．仅I和IIID．I、II和III进程控制进程的终止正常结束（自愿的）异常结束出现错误控制退出（自愿的）致命错误被迫退出（非自愿的）外界干预（非自愿的）进程控制进程的终止过程从进程控制块中读出该进程的状态若被终止进程正处于执行状态，立即终止该进程的执行若该进程还有子孙进程，还应将其所有子孙进程予以终止将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统将被终止进程的进程控制块移出进程控制进程的阻塞与唤醒请求系统服务启动某种操作新数据尚未到达无新工作可做选择2014-26一个进程的读磁盘操作完成后，操作系统针对该进程必做的是A．修改进程状态为就绪态B．降低进程优先级C．为进程分配用户内存空间D．增加进程的时间片大小进程控制进程的挂起与激活进程组织进程表中的信息进程组织链接方式就绪队列链表（一般为一个）阻塞队列链表（可能依据不同阻塞原因有多个队列链表）索引方式就绪队列索引阻塞队列索引进程通信Shared

memory(共享内存)Message(消息机制)Pipe(管道)Signal(信号)Socket(套接字)线程线程的基本概念线程线程的属性轻型实体（容易创建和撤销）独立调度和分派的基本单位可并发执行共享进程资源适应硬件的发展线程

在具有线程OS中，进程是作为拥有系统资源的基本单位，进程不再作为一个执行的实体。具有线程的OS中的进程有以下属性：作为系统资源分配的单位可包括多个线程进程不是一个可执行的实体线程线程间的同步和通信互斥锁(mutex):互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制条件变量线程共享同一进程的全局变量2016-30．进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示。下列选项中，需要互斥执行的操作是A．a=1与a=2B．a=x与b=xC．x+=1与x+=2D．x+=1与x+=3//进程P1int

x=0：Thread1(

){ int

a：a=1；x+=1；}Thread2(

){ int

a：a=2；x+=2；}//进程P2int

x=0：Thread3(

){ int

a；a=x；x+=3；}Thread4(

){ int

b；b=x；x+=4；}选择线程内核支持线程内核支持线程是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠内核实现的。在内核空间还为每一个内核支持线程设置了一个线程控制块，内核是根据该控制块而感知某线程的存在的，并对其加以控制线程内核支持线程线程用户级线程用户级线程仅存在于用户空间中。这种线程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。对于用户级线程的切换，通常是发生在一个应用进程的诸多线程之间，无须内核的支持。由于切换的规则比进程切换的规则简单，因而使线程的切换速度特别快。线程用户级线程线程混合线程处理机调度处理机调度的基本概念调度算法处理机调度处理机调度的基本概念处理机调度处理机调度高级、中级和低级调度FCFSSJFHRFSRFFCFSSPFRRPS处理机调度高级调度(High

Scheduling)，宏观调度，作业调度在每次执行作业调度时（由外存创建到内存成为进程），都须做出以下两个决定接纳多少个作业?接纳哪些作业?处理机调度中级调度(Intermediate-Level

Scheduling)

，中程调度引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量中级调度的算法主要由内存管理来实现，与高级调度和低级调度的算法不同，故一般在存储管理中分析，虚拟存储的中级调度即页面调入、置换等实现处理机调度低级调度(LowLevelScheduling)，微观调度，进程调度，线程调度非抢占方式(Non-preemptive

Mode)抢占方式(Preemptive

Mode)调度算法先来先服务算法比较有利于长作业，而不利于短作业有利于CPU繁忙的作业，而不利于I/O繁忙的作业调度算法短作业(进程)优先调度算法优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间提高系统的吞吐量缺点：对长作业非常不利，可能长时间得不到执行，饥饿未能依据作业的紧迫程度来划分执行的优先级难以准确估计作业（进程）的执行时间，从而影响调度性能调度算法“最短剩余时间优先”SRT(Shortest

RemainingTime)允许比当前进程剩余时间更短的进程来抢占“最高响应比优先”HRRN(Highest

Response

RatioNext)响应比R=(等待时间+要求执行时间)/要求执行时间是FCFS和SJF的折衷调度算法高优先权优先调度算法非抢占式优先权算法抢占式优先权调度算法优先权的类型静态优先级动态优先级调度算法基于时间片的轮转调度算法(RR:

Round

Robin)调度算法多级反馈队列调度算法(Round

Robin

with

Multiple

Feedback)多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展调度算法多级反馈队列调度算法PS选择2009-24下列进程调度算法中，综合考虑进程等待时间和执行时间的是A．时间片轮转调度算法B．短进程优先调度算法C．先来先服务调度算法D．高响应比优先调度算法选择2010-26下列选项中，降低进程优先级的合理时机是A．进程的时间片用完B．进程刚完成I/O，进入就绪队列C．进程长期处于就绪队列D．进程从就绪状态转为运行态调度算法实时调度算法给定m个周期事件事件i的周期为Pi需要处理器时间Ci可能调度的条件是同步与互斥进程同步的基本概念两种形式的制约关系间接相互制约关系直接相互制约关系临界资源(Critical

Resource)临界区(Critical

Section)一个飞机订票系统（软件相同），两个终端，运行T1、T2进程T1：……read(x);if

x>=1

thenx:=x-1;write(x);……T2：……read(x);if

x>=1

thenx:=x-1;write(x);……互斥关系Coming

data

blocks初始状态结果正确错误错误错误错误错误同步关系同步与互斥同步机制应遵循的规则空闲让进忙则等待有限等待让权等待同步与互斥(Peterson’s

Algorithm)：先修改、后检查；后修改者等待正确的算法turn=j;描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后：检查对方flag，如果不在临界区则自己进入－－空闲则入否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入－－先到先入，后到等待选择2010-27进程P0和P1的共享变量定义及初值为boolean

flag[2];int

turn

=

0;flag[0]

=

FALSE;

flag[1]

=FALSE;若进程P0和P1访问临界资源的类C伪代码实现如下：void

P0（）

//进程P0{while（TRUE）{flag[0]

=

TRUE;

turn

=

1;while（flag[1]&&（turn

==

1））;临界区;flag[0]

=

FALSE;}}void

P1（）

//进程P1{while（TRUE）{flag[1]=TRUE;turn=0;while（flag[0]&&（turn==0））;临界区;flag[1]

=

FALSE;}}则并发执行进程P0和P1时产生的情况是A．不能保证进程互斥进入临界区，会出现“饥饿”现象B．不能保证进程互斥进入临界区，不会出现“饥饿”现象C．能保证进程互斥进入临界区，会出现“饥饿”现象D．能保证进程互斥进入临界区，不会出现“饥饿”现象同步与互斥硬件TSL指令2016-27．使用TSL(Testand

SetLock)指令实现进程互斥的伪代码如下所示。下列与该实现机制相关的叙述中，正确的是A．退出临界区的进程负责唤醒阻塞态进程

B．等待进入临界区的进程不会主动放弃CPU

C．上述伪代码满足“让权等待”的同步准则

D．while(TSL(&lock))语句应在关中断状态下执行do

{……while(TSL(&lock))；critical

section；lock=FALSE；……}while(TRUE)；选择同步与互斥信号量机制整型信号量：最初由Dijkstra把整型信号量定义为一个整型量，仅能通过初始化和两个标准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。两个操作被分别称为P、V操作(primitive)同步与互斥78P

原语wait(s);

down(s);P(s)--s.count; //表示申请一个资源;if

(s.count

<0)//表示没有空闲资源;{调用进程进入等待队列s.queue;阻塞调用进程;}同步与互斥79V

原语signal(s);up(s);V(s)//表示释放一个资源；//表示有进程处于阻塞状态；++s.count;if

(s.count

<=

0){从等待队列s.queue中取出一个进程P;进程P进入就绪队列;}选择2010-25设与某资源相关联的信号量初值为3，当前为1，若M表示该资源的可用个数，N表示等待该资源的进程数，则M，N分别是A．0、1B．1、0C．1、2D．2、0经典进程的同步与互斥问题生产者—消费者问题利用信号量解决生产者—消费者问题2009-45三个进程P1、P2，P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用Put（）送入缓冲区某一空单元中；P2每次用

getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述82综合题//并发进程//生产者进程//等待调度解答：semaphoremutex=1，odd=

0，even

=

0，empty

=

N；//缓冲区可用，没有放置奇数和偶数，全空，odd+even+empty=Nmain（）cobegin{Process

P1while（true）{number=produce（）；

//生产者生产数P（empty）；P（mutex）；//有无空间//能否进入缓冲区83//放置数字//释放缓冲区//是否偶数//偶数信号量加1put（）；V（mutex）；If number

%

2

=

=

0V（even）；elseV（odd）；}//否则奇数信号84

量加1process

P2//消费者进程1//有无奇数//能否进入缓冲区//取奇数//释放缓冲区//空间加1while（true）{

P（odd）；P（mutex）；getodd（）；V（mutex）；V（empty）；countodd（）；}//计算奇数个数85//有无偶数//能否进入缓冲区//取偶数//释放缓冲区//空间加1Process

P3while（true）{

P（even）；P（mutex）；geteven（）；V（mutex）；V（empty）；counteven（）；}}coend//计算偶数个数//并发结束86【分析】：本题是生产者和消费者问题的延伸。从生产者-消费者的原题出发，正确设置信号量，保证进程同步和互斥的实现。考虑缓冲区是一互斥资源，因此设互斥信号量mutex。对于同步问题：P1、P2因为奇数的放置与取用而同步，设同步信号量odd；

P1、P3因为偶数的放置于取用而同步，设同步信号量even；P1、P2，P3因为共享缓冲区，设同步信号量empty872015-45．（9分）有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放入对方的信箱中。假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件(0<x<M)，B的信箱中有y个邮件

(0<y<N)。辩论者每取出一个邮件，邮件数减1。A和B两人的操作过程描述如下：综合题CoBeginA

{while(TRUE){从A的信箱中取出一个邮件；回答问题并提出一个新问题；将新邮件放人B的信箱；}}B

{while(TRUE){从B的信箱中取出一个邮件；回答问题并提出一个新问题；将新邮件放人A的信箱；}}CoEnd当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V(或wait、signal)操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。解答：本题在PV操作中是比较简单的题，从题意可以看出，AB的信箱双方分别可以读写，因此需要设置互斥信号量。又由于信箱的大小受限，因此要设置资源信号量。资源信号量要设空和满的二种。semaphore

EA=M-x；//A信箱空缓冲区数

semaphore

EB=N-y；//B信箱空缓冲区数

semaphore

FA=x；//A信箱满缓冲区数

semaphore

FB=y；//B信箱满缓冲区数semaphore

mutexA=1；//用于实现读写A信箱的互斥量

semaphore

mutexB=1；//用于实现读写B信箱的互斥量(1分)CoBeginA

{B

{while(TRUE){while(TRUE){P(FA)；P(FB)；P(mutexA)；P(mutexB)；从A的信箱中取出一个邮件；从B的信箱中取出一个邮件；V(EA)；V(EB)；V(mutexA)；V(mutexB)；回答问题并提出一个新问题；回答问题并提出一个新问题；P(FB)；P(FA)；P(mutexB)；P(mutexA)；将新邮件放入B的信箱；将新邮件放入A的信箱；V(EB)；V(EA)；V(mutexB)；V(mutexA)；}}}}CoEnd【分析】：在书写P操作时，一定将资源信号量在先，互斥量在后。而在V操作时没有这个要求。一定需要对空位和满位均设置信号量，否则可能造成读空信箱或写满信箱。经典进程的同步与互斥问题哲学家进餐问题Philosophers

eat/thinkEating

needs

2

forksPick

one

fork

at

a

timeHow

to

prevent

deadlock让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。else{P(c[i+1

mod

5]);P(c[i]);eat;V

(c[i]);V(c[i+1mod5]);}send(i)beginif

i

mod

2

==0

then{P(c[i]);P(c[i+1

mod

5]);eat;V(c[i+1

mod

5]);V

(c[i]);}end数据区读者计数互斥经典进程的同步与互斥问题读者-写者问题互斥利用信号量解决读者-写者问题2014-46．(8分)系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区(初始为

空)。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取走10件产品后，其他消费者进程才可以取产品。请使用信号量的P、V(wait( )、signal( ))操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。综合题解答：本题考查信号量的使用及P、V操作伪代码如下：初始化semaphore

empty=1000；semaphore

full=0；semaphore

mutex1=1；semaphore

mutex2=1；int

in=0；int

out=0；//空缓冲区数//非空缓冲区数(1分)//用于实现生产者和消费者之间的互斥//用于实现消费者之间的互斥(1分)//初始化//初始化//调度//生产产品//P空闲位置同步量//P与消费者和其他生产者互斥量//放置产品//循环指针加1//释放互斥量//释放同步量while(TRUE){

produce；P(empty)；P(mutexl)；put

an

item

into

buf[in]；in=(in+1)mod

n；Ⅴ(mutex1)；Ⅴ(full)；}生产者进程(2分)//调度//P消费者互斥量2//连续消费10//P产品的同步量//P生产者互斥量1//取货//设置消防循环指针//释放互斥量1//释放同步量//释放互斥量2//消费while(TRUE){

P(mutex2)；for(int

i=0；i<10；i++){

P(full)；P(mutex1)；get

anitem

from

buf[out]；out=(out+1)mod

n；Ⅴ(mutex1)；Ⅴ(empty)；}Ⅴ(mutex2)；consume；}消费者进程(4分)2016-46．(6分)某进程调度程序采用基于优先数(priority)的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，

cpuTime置0，waitTime定时加1。请回答下列问题。若调度程序只将nice的值作为进程的优先数，即priority=nice，则可能会出现饥饿现象，为什么?使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。综合题解答：nice固定时为“固定优先级”调度算法，此时。若发生nice较低的进程源源不断进入就绪队列，较高nice的进程就会得不到调度，引起饥饿。简单的解决方法是改为“动态优先级”调度算法，利用waitTime的值，将

priority=nice–waitTime，当进程在就绪队列中等待时间waitTime增加时，适当提高优先级，即减少优先数priority，直到为0（即最高优先级），这样就解决了饥饿的问题。

waitTime起到提升优先级的作用。更复杂的算法可以将cpuTime也考虑进去。死锁产生死锁的原因和必要条件解决死锁的方法死锁产生死锁的原因互斥资源分配不当（造成剩余资源不足，非资源不足）进程间推进顺序不当死锁死锁死锁死锁定义:同一进程集中的二个以上的不同进程都在互相等待对方为自己释放资源因而造成的进程无法推进的现象死锁产生死锁的四个必要条件互斥条件请求和保持条件不剥夺条件环路等待条件2016-25．系统中有3个不同的临界资源R1、R2和R3，被4个进程p1、p2、p3及p4共享。各进程对资源的需求为：

p1申请R1和R2，p2申请R2和R3，p3申请R1和R3，p4申请

R2。若系统出现死锁，则处于死锁状态的进程数至少是A．1B．2C．3D．4死锁处理死锁的基本方法忽略死锁(鸵鸟算法)检测和解除死锁(有向图，矩阵:剥夺资源)避免死锁(银行家算法)预防死锁(打破死锁的四个必要条件)死锁死锁的检测死锁资源矩阵死锁死锁的恢复剥夺资源回溯到还原点撤消进程重起系统死锁安全和不安全状态利用银行家算法避免死锁一个银行家把他的固定资金（capital）贷给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回死锁预防死锁摒弃互斥条件摒弃“请求和保持”条件摒弃“不剥夺”条件摒弃“环路等待”2009-25某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K最小值是A．2

B．3

C．4

D．5选择2015-26．若系统S1采用死锁避免方法，S2采用死锁检测方法。下列叙述中，正确的是Ⅰ．S1会限制用户申请资源的顺序，而S2不会

Ⅱ．S1需要进程运行所需资源总量信息，而S2不需要

Ⅲ．S1不会给可能导致死锁的进程分配资源，而S2会A．仅Ⅰ、Ⅱ

C．仅Ⅰ、ⅢB．仅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ选择本章重要习题分析重点！重点！重点！大量考题，选择、综合复杂综合题总体占10-15分第三章 内存管理内存管理基础虚拟内存管理内存管理基础内存管理概念（程序装入与链接；逻辑地址与物理地址空间；内存保护）、交换与覆盖、连续分配管理方式、非连续分配管理方式（分页管理方式；分段管理方式；段页式管理方式）虚拟内存管理虚拟内存基本概念、请求式分页管理方式、页面置换算法（最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK））、页面分配策略、工作集、抖动大纲要求简单存储管理定位和重定位程序的装入绝对装入方式(Absolute

Loading

Mode)程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予例如：ORG

1000H可重定位装入方式(Relocation

Loading

Mode)静态动态简单存储管理动态运行时装入方式(Dynamic

Run-time

Loading)动态运行时装入程序，在把装入模块(Loader)装入内存后，并不把其它模块装入内存，而是把装入过程推迟到程序真正要执行时才进行简单存储管理程序的链接静态链接方式(Static

Linking)装入时动态链接(Load

time

Dynamic

Linking)运行时动态链接(Run-time

Dynamic

Linking)简单存储管理简单连续分配方式单一连续分配固定分区分配(等额和差额)动态分区分配简单存储管理分区分配中的数据结构位示图空闲分区链表简单存储管理分区分配算法首次适应算法First

Fit循环首次适应算法Next

Fit最佳适应算法Best

Fit最坏适应算法Worst

Fit快速适应算法Quick

Fit129PointerComing

a

New

process

is

16KWorst

fit选择2010-28某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空闲），采用最佳适配（Best

Fit）算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是A．7MBB．9MBC．10MBD．15MB简单存储管理交换(Swapping)覆盖(Overlay)简单存储管理基本分页存储管理方式页号P位移量W0简单存储管理分页地址中的地址结构如下31

12

11简单存储管理多级页表(Multi-Level

Page

Table)Windows

的多级页表结构选择2014-32下列选项中，属于多级页表优点的是A．加快地址变换速度B．减少缺页中断次数C．减少页表项所占字节数D．减少页表所占的连续内存空间段号段长/段内地址简单存储管理基本分段存储管理方式31

16

15

02016-28．某进程的段表内容如下所示。当访问段号为2、段内地址为400的逻辑地址时，进行地址转换的结果是

A．段缺失异常

B．得到内存地址4400

C．越权异常

D．越界异常段号段长内存起始地址权限状态01006000只读在内存1200—读写不在内存23004000读写在内存选择选择2009-27一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是A．28字节B．216字节C．224字节D．232字节选择2010-29某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节，页表项大小为2字节，逻辑地址结构为下图所示，逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是A．64B．128C．256D．512页目录号页号页内偏移量XXXXXX简单存储管理分页和分段的主要区别页是信息的物理单位，分页是为实现离散分配方式，提高内存的利用率。是由于系统管理的需要而不是用户的需要段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要页的大小固定且由系统决定，而段的长度却不固定分页的作业地址空间是一维的，而分段的作业地址空间则是二维的虚拟存储管理虚拟存储器的基本概念多次性对换性虚拟性虚拟存储管理局部性原理时间局部性，程序执行时，大多数情况下是顺序执行的空间局部性，程序中存在许多循环结构，它们将多次执行。程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内虚拟存储管理虚拟存储器定义所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由CPU及其存储器的地址线宽度，实际容量由内存容量和外存容量之和决定，其运行速度接近于内存速度，而每位的成本却又接近于外存虚拟存储管理虚拟存储器的实现方法分页请求系统：页表机制硬件支持：缺页中断机构；地址变换机构实现请求分页的软件虚拟存储管理页表表项Virtual

time

and

so

onOnly

for

memory

mapped

I/OBeyond

fault虚拟存储管理选择2014-28．下列措施中，能加快虚实地址转换的是Ⅱ．让页表常驻内存

Ⅲ．增Ⅰ．增大快表(TLB)容量大交换区(swap)A．仅IB．仅IIC．仅I、IID．仅II、III虚拟存储管理页面置换算法最佳置换算法其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率虚拟存储管理FIFO432143543215页1432143555211页243214333522页34321444355页面置换算法先进先出置换算法(FIFO)x

x

x

x

x

x

x

x

x

共缺页中断9次虚拟存储管理时钟算法虚拟存储管理页面置换算法最近最久未使用置换算法(LRU)LRU432143543215页1432143543215页243214354321页34321435432xxxxxxxxxx共缺页中断10次虚拟存储管理工作集算法w(k,t)

is

the

size

of

the

working

set

at

time,

tLocality

of

reference若工作集的窗口大小为6，则在t时刻的工作集为A．{6，0，3，2}B．{2，3，0，4}C．{0，4，3，2，9}D．{4，5，6，0，3，2}选择2016-29．某进程访问页面的序列如下所示。虚拟存储管理Belady’s

异常Thrashing

抖动选择2014-30在页式虚拟存储管理系统中，采用某些页面置换算法，会出现

Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是Ⅰ．LRU算法

Ⅱ．FIFO算法

Ⅲ．OPT算法A．仅IIB．仅I、IIC．仅I、IID．仅II、III虚拟存储管理局部置换全局置换7

frames2015-30．在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是A．可变分配，全局置换

B．可变分配，局部置换

C．固定分配，全局置换

D．固定分配，局部置换选择选择2009-26分区分配内存管理方式的主要保护措施是A．界地址保护B．程序代码保护C．数据保护D．栈保护综合题2009-45请求分页管理系统中，假设某进程的页表内容如左表所示，页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（己含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：依次访问上述三个虚地址，各需多少时间？给出计算过程。基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。页号页框号有效位0101H11-02254H1161解答：1565H指令P=1，访问快表10ns，不在TLB，访问页表

100ns，不在内存，发生缺页中断花费108ns，取得新页框号（含TLB更新），合成物理地址后去主存取指令需要花费100ns。总时间10ns+100ns+108ns+100ns≈108ns。25A5H指令，P=2，访问快表，因第一次访问己将该页号放入快表，因此花费10ns便可合成物理地址，访问主存取指100ns，共计10ns+100ns=110ns。地址页号页内位移2362H2362H1565H1565H25A5H25A5H162当访问虚地址1565H时，因不在内存而产生缺页中断，因驻留集为2个页，现在已有0页和2页在内存，必须从中淘汰一个页面，从而将新1页调入内存。根据LRU置换算法，0页和2页除有效位以外的其它信息未知，但是，2页刚刚访问过，其引用位应刚置为1且时间间隔不长，根据最近最少使用置换算法，相比之下应首先淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。（1）

210ns；108ns；110ns。（2）

101565H。163【分析】：根据页式管理的工作原理，应先将页号和页内位移地址分解出来。页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高4位。可得三个虚地址的页号P如上表，2362H指令，P=2，访问快表

10ns，因初始为空，需要再到内存访问页表，花费100ns得到页框号，合成物理地址后去主存取指令需要花费

100ns。总时间10ns+100ns+100ns=210ns。164本章重要习题分析重点！特别是虚拟存储技术！各种变换！选择题（包括多项组合题）、综合题均有总体占10-12分，保持稳定。165第四章文件管理文件系统基础文件系统实现磁盘组织与管理文件系统基础文件概念、文件的逻辑结构（顺序文件；索引文件；索引顺序文件）、目录结构（文件控制块和索引节点；单级目录结构和两级目录结构；树形目录结构；图形目录结构）、文件共享、文件保护（访问类型；访问控制）文件系统实现文件系统层次结构、目录实现、文件实现磁盘组织与管理磁盘的结构、磁盘调度算法、磁盘的管理大纲要求文件文件、记录和数据项文件属性可以包括文件类型文件长度文件的物理位置文件的建立时间示例在一个学生的文件记录中，哪个可以作为主键用于检索姓名年龄学号性别示例从用户角度看，我们建立文件系统是为了实现（），为达到此目的，我们必需建立（）文件管理；文件访问；按名存储；文件保存；文件安全文件名；目录；字典；文件识别号；文件属性文件文件类型按文件中数据的形式分类系统文件/用户文件/库文件/源文件按用途分类目标文件/可执行文件按存取控制属性分类只执行文件只读文件/读写文件文件文件的逻辑结构累积文件索引结构文件文件文件的物理结构磁盘磁带光盘非易失存储器件磁盘磁盘的结构磁盘磁盘管理磁盘存储块分配表（FAT）位示图（Bitmap）选择2014-27．现有一个容量为10GB的磁盘分区，磁盘空间以簇(Cluster)为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位(bit)标识一个簇是否被分配，则存放该位图所需簇的个数为A．80B．320C．80KD．320KFCB文件外存分配方式(物理结构)连续分配顺序访问容易，速度快要求有连续的存储空间必须事先知道文件的长度示例视频流数据最好存储在什么结构的文件系统中？顺序随机索引索引节点2014-46、(7分)文件F由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入到文件F中，作为其第30条记录。请回答下列问题，并说明理由。若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块?F的文件控制块内容会发生哪些改变?若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块?若每个磁盘块大小为1KB，其中4个字节存放链接指针，则该文件系统支持的文件最大长度是多少?17综合题解答：本题考查文件系统的物理结构(1)向前移动文件的1-29共29条记录，每条记录读写各1次，腾出原第29个磁盘块空间，以将该记录插入到此磁盘块作为文件的第30条记录。(1分)故需要磁盘访问的次数为：

29×2+1=59次。(1分)向后移动文件的30-200共171条记录，每条记录读写各1次，腾出原第30个磁盘块空间，以将该记录插入到此磁盘块作为文件的第30条记录。故需要磁

盘访问的次数为：171×2+1=343次。其中较少的是59次。且文件控制块中文件的起始地址和文件大小发生了变化。(1分)18(2)采用链接分配方式存储文件F，需要读文件的前29块的链接指针(共读29次)，在第29块内找到指向原第30块的链接指针。再为该记录分配一个空闲磁盘块，将该记录及第29块内保存的链接指针写入其中，将该块写到磁盘(写1次)。最后修改第29块的链接指针，指向新的插入块，并将第29块写回磁盘(写1次)。(1分)故需要磁盘访问的次数：29+2=31次。(1分)该文件系统支持的文件最大长度是：(1024-4)×232B=4080

GB。(2分)18FCB文件链接分配(链式)隐式链接文件链接分配(链式)显式链接2016-47．(9分)某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。若FAT的每个表项仅存放簇号，占2个字节，则FAT的最大长度为多少字节?该文件系统支持的文件长度最大是多少?综合题系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。假设仅FAT和dir目录文件已读入内存，若需将文件

dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇?文件名簇号dir1dir148file1100、106、108file2200、201、202解答：(1)目录文件dir为根目录，其内容为目录文件dir1为。。。。。。dir148。。。。。。。。。。。。file1100file2200。。。。。。(2)FAT表占2个字节即16位，共可以形成簇指针216=65536个，每个指针大小为2B，则FAT需要占用65536*2B=128KB，即

FAT的最大长度为128KB，共需要128KB/4KB=32个簇才能容纳下。其支持的最大文件为65536*4KB=256MB。(3)链接结构将下一个簇号放在前一个簇号的表项中，第一个簇号放在目录中。而簇号本身是隐含的。106放在簇号100中，108放在106中，108中放文件结束符-1（0xFFFF）。(4)访问文件dir/dir1/file1的第5000个字节，则计算：访问dir：免读簇，得到dir1簇48。访问dir1：读簇48；查FAT，免读簇，得到dir1内容file1和file2。计算5000个字节：5000/4096=1.x=>2，第5000个字节位于第2个簇内；查FAT，免读簇，查得file1第二个簇位于簇106。访问file1：读簇106，得到4KB数据，移动指针，找到第5000个字节。访问结束。共访问了簇48和簇106。文件索引分配单级索引分配多级索引分配FCBcount示例下列文件物理结构中，适合随机访问且易于文件扩展的是A．连续结构B．索引结构C．链式结构且磁盘块定长D．链式结构且磁盘块变长文件

A

UNIX

i-node10256+10=266K256*256+10=64M256*256*256+10=16T2015-31．文件系统用位图法表示磁盘空间的分配情况，

位图存于磁盘的32～127号块中，每个盘块占1024个字节，盘块和块内字节均从0开始编号。假设要释放的盘块号为

409612，则位图中要修改的位所在的盘块号和块内字节序号分别是A．81、1C．82、1B．81、2D．82、2选择选择2010-30设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是A．33KBB．519KBC．1057KBD．16513KB目录目录管理实现“按名存取”提高对文件的检索速度文件共享允许文件重名示例设置当前工作目录的主要目的是A．节省外存空间B．节省内存空间C．加快文件的检索速度D．加快文件的读/写速度示例在文件系统中是利用（

）来管理文件的，为了允许不同用户的文件使用相同的文件名，通常文件系统中采用（

）；在目录文件中的每个目录项通常就是（

）；在Unix文件系统中的目录项则是（）文件控制块；索引结点；目录；索引表；多级目录；文件表指针；文件名和文件物理地址；文件名和索引结点指针；符号名表示例文件系统中，文件访问控制信息存储的合理位置是A．文件控制块B．文件分配表C．用户口令表D．系统注册表磁盘磁盘访问时间寻道时间(Seek

time)