发布时间 : 星期四 文章名校操作系统历年考研试题（含解答）更新完毕开始阅读9a50b72651e79b89680226e0
1.覆盖技术与虚拟存储技术有何本质不同?交换技术与虚存中使用的调入/调出技术有何相同与不同之处?
2.文件顺序存取与随机存取的主要区别是什么?它们对有结构文件与无结构文件的操作有何不同?
3.死锁和竞争有何关系?
4.何请虚拟设备? 请说明SPOOLing系统是如何实现虚拟设备的。
(三)(10分)有5个任务A,B,C,D,E,它们几乎同时到达,预计它们的运行时间为10,6,2,4,8mn。其优先级分别为3,5,2,1和4,这里5为最高优先级。对于下列每一种调度算法,计算其平均进程周转时间(进程切换开销可不考虑)。 (1)先来先服务(按A,B,c,D,E)算法。 (2)优先级调度算法。 (3)时间片轮转算法。
(四)(10分)在虚拟页式存储系统中引入了缺页中断。 1.试说明为什么引入缺页中断。
2.缺页中断的实现由哪几部分组成?并分别给出其实现方法。
(五)(13分)消息缓冲通信技术是一种高级通信机制,由HANSEN首先提出。 1.试叙述高级通信机制与低级通信机制P、V原语操作的区别。 2.请给出消息缓冲通信机制(有界缓冲)的基本工作原理。
3.试设计相应的数据结构,并用P、V原语操作实现Send和Receive原语。
西安交通大学2000年考研操作系统试题解答
(一)名词解释(15分)
1.所谓线程(thread),从操作系统管理角度看线程是指\进程的一个可调度实体\是处理机调度的基本单位: 从编程逻辑看线程是指\程序内部的一个单一的顺序控制流\。线程是进程的一个组成部分。
2.所谓分时系统,就是指在一台计算机上,连接多个终端,用户通过各自的终端和终端命令把作业送入计算机,计算机又通过终端向各用户报告其作业的运行情况。这种计算机能分时轮流地为各终端用户服务并能及时对用户服务请求予以响应,这就构成了分时系统。分时系统设计的主要目标是使用户能与系统交互作用,对用户的请求及时响应,并在可能的条件下尽量提高系统资源的利用率。分时系统的主要特征是:
①同时性:若干个终端用户按照系统提供的各种服务,在各自终端进行操作,同时使用一台计算机资源。宏观上看是各用户在并行工作,微观上看是各用户轮流使用计算机。
②独立性:用户间可以相互独立地操作,互不干涉,系统保证各用户程序运行的完整性,不会发生相互混淆或破坏现象。
③及时性:系统可对用户的输入及时作出响应。分时系统性能的主要指标之一是响应时间,它是指从终端发出命令到系统予以应答所需的时间。
④交互性:用户可根据系统对请求的响应结果,进一步向系统提出新的请求,即能使用户和系统进行人一机对话的工作方式,所以分时系统也被称之为交互式系统。
3.系统调用是指用户在程序中能用\访管指令\调用的由操作系统提供的子功能的集合。每一个子功能称为一条系统调用命令(或广义指令)。系统调用是操作系统在程序级给用户提供的接口。
4.所谓地址再定位,就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程,即将地址空间给出的逻辑地址映射到内存的物理地址。地址重定位有静态重定位和动态重定位两种方式。
5.多道程序设计是指在主存中同时存放多道用户作业,它们都处于执行的开始点和结束点之间。多道程序设计的特点如下:
(1)多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。 (2)宏观上并行。从宏观上看,它们在同时执行。
(3)微观上串行。从微观上看,它们在交替、穿插地执行。
采用多道程序设计后,减少了CPU时间的浪费。尤其对计算题的作业,由于I/O操作较少,CPU浪费的时间很少。 (二)简答题(32分)
1.覆盖技术与虚拟存储技术最本质的不同在于覆盖的程序段的最大长度要受到物理内存容量的限制,而虚拟存储器的最大长度不受物理内存容量的限制,只受计算机地址结构的限制。另外,使用覆盖技术要求程序员必须精心地设计程序及其数据结构,使得要覆盖的段具有相对独立性,不存在直接联系或相互交叉访问。而虚拟存储技术对用户的程序段之间没有此要求。
交换技术与虚存中使用的调入/调出技术的主要相同点是都要在内存与外存之间交换信息。交换技术与虚存中使用的调入/调出技术的主要区别在于:交换技术换进换出整个进程(proc结构和共享正文段除外〉,因此一个进程的大小受物理存储器的限制:而虚存中使用的调入/调出技术在内存和外存之间来回传递的是存储页或存储段,而不是整个进程,从而使得进程的地址映射具有了更大的灵活性,且允许进程的大小比可用的物理存储空间大得多。
2.顺序存取法就是严格按物理记录排列的顺序依次存取:随机存取法允许随意存取文件中的任何一个物理记录,而不管上次存取了哪一个记录。
顺序存取法对有结构文件的操作是设置一个访问指针ptr,令它总是指向\下一次\要访问的记录首址。每访问完一个记录后,对ptr住进行相应的修改。对于定长记录:ptr=ptr+L(L为文件的物理记录长度):对于变长记录:Ptr=ptr+Li+1(其中1是存放记录长度Li的字节数)。顺序存取法对无结构文件的操作是按读写位移(offset)从当前位置开始读写,即每读写完一段信息后,读写位移自动力日上这段的长度,然后再根据该位移读写下面的信息。
随机存取法对有结构文件的操作也是设置一个访问指针pt,对于定长记录文件,欲访问第I个记录。(I=0,1,2,?)的首址为: ptr=offset+I*L(其中,offest是该文件的首址,L为记录长度):对于变长记录,随机存取法是十分低效的。随机存取法对无结构文件的操作必须事先用有关的命令把读写位移移到欲读写的信息开始处,然后再进行读写。
3.死锁是指多个进程因竞争资源而造成的一种僵局,若无外力的作用,这些进程都将永远不能再向前推进。所以,死锁是由于系统中多个进程所共享的资源不足以同时满足需要时,引起对资源的竞争而产生的。但竞争资源不→定都会产生死锁,因为只要进程推进顺序合法,就不会产生死锁。
4.所谓虚拟设备,是指利用SPOOLing系统把低速的独占设备改造成为共享的设备,或利用软件方法把共享的设备分割为若干台虚拟设备。
SPOOLing系统的核心思想是利用一台可共享的、高速大容量的块设备(磁盘)来模拟独占设各的操作,使一台独占设备变成多台可并行使用的虚拟设备。SPOOLing系统主要由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。它的特点是提高了I/O操作的速度:将独占设备改造为共享设备;实现了虚拟设备功能。 (三)(10分)
(1)采用FCFS的调度算法时,各任务在系统中的执行情况如下表所示:
执行次序 A 运行时间 10 优先数 3 等待时间 周转时间 0 10 B C D E 6 2 4 8 5 2 1 4 10 16 18 22 16 18 22 30 所以,进程的平均周转时间为:
T=(10+16+18+22+3O)/5=19.2 min
(2)采用优先级调度算法时,各任务在系统中的执行情况如下表所示:
执行次序 B E A C D 运行时间 6 8 10 2 1 优先数 5 4 3 2 1 等待时间 周转时间 0 6 14 24 26 6 14 24 26 27 所以,进程的平均周转时间为:
T=(6+14+24+26+27)/5=19.4 min
(3)采用时间片轮转算法时,假定时间片为2min,各任务的执行情况是:(A,B,C,D,E),(A,B,D,E),(A,B,E),(A,E),(A)。设A～E五个进程的周转时间依次为T1～T5,显然,
T1=3Omin, T2=22min, T3=6min,T4=16min,T5=28min 所以,进程的平均周转时间为:
T=(30+22+6+16+28)/5=20.4min (四)(10分)
1.因为虚拟页式存储系统中允许作业的一部分页面在内存,只有引入缺页中断,才能将不在内存的信息页从外存调入内存,中断恢复后可以继续执行。
2.缺页中断的实现由硬件和软件两部分组成。其实现方法如下:
每当CPU要执行一条指令时,首先形成操作数的有效地址,在计算页号和页内地址,检查页表看该页在实存吗。如在,则进行地址变换,按变换后的地址取出操作数,完成该指令的功能,然后继续进行下一条指令; 如不在,则引起缺页中断,进入缺页中断处理程序。
在中断处理程序中,首先利用存储器分块表(MBT)检查实存是否有空闲页面,如无,则选择某页淘汰。若该页被修改过还需写入辅存,并修改PMT和MBT,此时便出现了空闲实页。如有空闲实页,则根据辅助页表提供的磁盘地址调入所需的页面,修改PMT和MBT。最后再重新执行被中断的指令。 (五)(13分)
1.高级通信机制与低级通信机制P、V原语操作的主要区别是:
(1)交换信息量方面:利用p、v原语操作作为进程间的同步互斥工具是理想的,但进程间只能交换一些信息,基本上只能是控制信息,缺乏传输消息的能力。而高级通信不仅能较好地解决进程间的同步互斥问题,且能很好交换大量消息,是理想的进程通信工具。 (2)通信对用户透明方面:用户要用P、V原语进行进程间的通信必须在程序中增加p、V编程,这样做不但增加了编程的复杂性,不便对程序有直观的理解,同时由于编程不当,有可能出现死锁,难以查找其原因。而高级通信机制不但能高效传输大量信息,且操作系统隐藏了进程通信的实现细节,即通信过程对用户是透明的。这样就大大地简化了通信程序编制上的复杂性。 2.所谓消息(Message),是指一组信息,消息缓冲区是含有如下信息的缓冲区:
指向发送进程的指针:Sptr
指向下一信息缓冲区的指针:Nptr;
消息长度: Size; 消息正文: Text;
消息缓冲通信机制的基本工作原理是:把消息缓冲区作为进程通讯的一个基本单位,为了实现进程之间的通讯,系统提供了发送原语Send(A)和接收原语Receive(B)。每当发送进程欲发送消息时,发送进程用Send(A)原语把欲发送的消息从发送区复制到消息缓冲区,并将它挂在接收进程的消息队列末尾。如果该接收进程因等待消息而处于阻塞状态,则将其换醒。而每当接收进程欲读取消息时,就用接收原语Receive(B)从消息队列头取走一个消息放到自己的接收区。
3.消息缓冲通信机制中,消息队列属于临界资源,故在PCB中设置了一个用于互斥的信号量mutex,而每当有进程要进入消息队列时,应对信号量mutex施行P操作,退出消息队列后,应对信号量mutex施行V操作。由于接受进程可能会收到几个进程发来的消息,故应将所有的消息缓冲区链成一个队列,其队头由接收进程PCB中的队列头指针Hptr指出。
为了表示队列中的消息的数目,在PCB中设置了信号量旬,每当发送进程发来一个消息,并将它挂在接收进程的消息队列上时,便在Sn上执行V操作:而每当接收进程从消息队列上读取一个消息时,先对Sn执行P操作,再从队列上移出要读取的消息。
用P、V原语操作实现Send原语和Receive原语的处理流程如下: Procedure Send(receiver,Ma) {发送原语}
begin
getbuf(Ma, size,i); {申请消息缓冲区}
i.sender:=Ma.Sender; {将发送区的信息发送到消息缓冲区} i.size:=Ma.Size; i.text:=Ms.text; i.next:=0;
getid(PCB set,receive,j); {获得接收进程的内部标识符} P(j.mutex);
insert(j.Hptr,i); {消息缓冲区插入到消息队列首} V(j.Sn); V(j.mutex); end
Procedure Receive(Mb) {接收原语} begin
j:internal name; {接收进程内部标识符} P(j.Sn); P(j.mutex);
remove(j.Hptr,i); {从消息队列中移出第一个消息} V(j.mutex);
Mb.Sender:=i.Sender; {将消息缓冲区中的信息复制到接收区} Mb.Size:=i.Size: Mb.text:=i.text: End
10.4 西安电子科技大学2000年考研操作系统试题
(一)单项选择题(10分)
1.分页式虚拟存储管理系统中,一般来说页面的大小与可能产生缺页中断的次数_____。 A.成正比 B.成反比 C.无关 D.成固定比值