C 16 18 214 3 所以,进程的平均周转时间为 T=(10+16+18+22+30)/5=19.2min (2)采用优先级调度算法时,各任务在系统中的执行情况如下表所示 执行次序运行时间优先数|等待时间周转时间 BEACD 680 14 14 2224 26 所以,进程的平均周转时间为 T=(6+14+24+26+27)/5=19.4min (3)采用时间片轮转算法时,假定时间片为2min,各任务的执行情况 是:(A,B,C,D,E),(A,B,D,E),(A,B,E),(A,E),(A)。设A~E五个进程的周转时间依次为T1~ T5,显然, T1=30min, T2=22min, T3=6min, T4=16min. T5=28min 所以,进程的平均周转时间为 1.因为虚拟页式存储系统中允许作业的一部分页面在内存,只有引入缺页中断,才能将不 在内存的信息页从外存调入内存,中断恢复后可以继续执行 2.缺页中断的实现由硬件和软件两部分组成。其实现方法如下 每当CPU要执行一条指令时,首先形成操作数的有效地址,在计算页号和页内地址,检查 页表看该页在实存吗。如在,则进行地址变换,按变换后的地址取出操作数,完成该指令的功能, 然后继续进行下一条指令;如不在,则引起缺页中断,进入缺页中断处理程序 在中断处理程序中,首先利用存储器分块表(MBT)检查实存是否有空闲页面,如无,则选择 某页淘汰。若该页被修改过还需写入辅存,并修改PMT和MBT,此时便出现了空闲实页。如有 空闲实页,则根据辅助页表提供的磁盘地址调入所需的页面,修改PMT和MBT。最后再重新执 行被中断的指令 (五)(13分) 1.高级通信机制与低级通信机制P、V原语操作的主要区别是: (1)交换信息量方面:利用p、ⅴ原语操作作为进程间的同步互斥工具是理想的,但进程间只能 交换一些信息,基本上只能是控制信息,缺乏传输消息的能力。而高级通信不仅能较好地解决 进程间的同步互斥问题,且能很好交换大量消息,是理想的进程通信工具。 (2)通信对用户透明方面∷用户要用P、Ⅴ原语进行进程间的通信必须在程序中增加p、V编程, 这样做不但增加了编程的复杂性,不便对程序有直观的理解,同时由于编程不当,有可能出现 死锁,难以査找其原因。而高级通信杋制不但能髙效传输大量信息,且操作系统隐藏了进程通 信的实现细节,即通信过程对用户是透明的。这样就大大地简化了通信程序编制上的复杂性 2.所谓消息( Message),是指一组信息,消息缓冲区是含有如下信息的缓冲区 指向发送进程的指针:Sptr 指向下一信息缓冲区的指针:Nptr 消息长度:Size;
C 2 2 16 18 D 4 1 18 22 E 8 4 22 30 所以,进程的平均周转时间为: T=(10+16+18+22+3O)/5=19.2 min (2)采用优先级调度算法时,各任务在系统中的执行情况如下表所示: 执行次序 运行时间 优先数 等待时间 周转时间 B 6 5 0 6 E 8 4 6 14 A 10 3 14 24 C 2 2 24 26 D 1 1 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施行Ⅴ操作。由于接受进程可能会收到几个进程发来的消息,故应将所有的消息 缓冲区链成一个队列,其队头由接收进程PCB中的队列头指针Htr指出。 为了表示队列中的消息的数目,在PCB中设置了信号量旬,每当发送进程发来一个消息,并将 它挂在接收进程的消息队列上时,便在Sn上执行Ⅴ操作:而每当接收进程从消息队列上读取 个消息时,先对Sn执行P操作,再从队列上移出要读取的消息 用P、V原语操作实现Send原语和 Receive原语的处理流程如下 Procedure Send (receiver, Ma) 发送原语 begil getbuf (Ma 申请消息缓冲区} i sender: =Ma Sender 将发送区的信息发送到消息缓冲区 i. text: =Ms. text i next: =0: getid(PCB set, receive, j) 获得接收进程的内部标识符} (j insert(j Hptr, i 消息缓冲区插入到消息队列首} v(. Sn) v(jmutex) Procedure Receive (Mb) 接收原语} egin j: internal name 接收进程内部标识符} P(j. Sn) P(i mutex) remove(j Hptr, i) 从消息队列中移出第一个消息} v( Mb Sender:=i Sender 将消息缓冲区中的信息复制到接收区} Mb. Size:=i Size Mb. text: =i. text 0.4西安电子科技大学200年考研操作系统试题 (一)单项选择题(10分) 1.分页式虚拟存储管理系统中,一般来说页面的大小与可能产生缺页中断的次数。 A.成正比B.成反比 C.无关 D.成固定比值 2.实时操作系统必须在 内完成来自外部的事件
消息正文: 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.成固定比值 2.实时操作系统必须在_______内完成来自外部的事件
A.响应时间B.周转时间C.规定时间D.调度时间 3.早期UNIX操作系统的存储管理采用 方案 A.段式管理 请求分页 C.可变式分区管理D.固定式分区管理 4.在下列语言中属于脱机作业控制语言的是 A.作业控制语言 B.汇编语言 C.会话式程序设计语言D.解释 BASIC语言 5.MS-D0S中的文件物理结构采用 A.连续结构B.链接结构C.索引结构D.哈希表 6.在请求分页存储管理方案中,如果所需的页面不在内存中,则产生缺页中断,它属于 中断 A.硬件故障B.I/0 D.程序中断 7.设有四个作业同时到达,每个作业的执行时间均为2小时,它们在仪态处理机上按单道方式 运行,则平均周转时间为 A.1小时B.5小时C.25小时D.8小时 8.在关于 SPOOLING的叙述中 描述是不正确的。 A. SPOOLING系统中不需要独占设备 B. SPOOLING系统加快了作业执行的速度 C.SP0 OLING系统使独占设备变成共享设备 D. SPOOLBNG系统利用了处理器与通道并行工作的能力 9.页式虚拟存储管理的主要特点是 A.不要求将作业装入到主存的连续区域 B.不要求将作业同时全部装入到主存的连续区域 C.不要求进行缺页中断处理 D.不要求进行页面置换 0.下列文件中属于逻辑结构的文件是 A.连续文件B.系统文件C.散列文件D.流式文件 (二)改错题(对错误的命题,请说明原因)(10分) 1.采用多道程序设计的系统中,系统的程序道数越多,系统的效率就越高。 2.特权指令只能在管态下执行,而不能在算态下执行 3.采用资源的静态分配算法可以预防死锁的发生 4.一个虚拟的存储器,其地址空间的大小等于辅存的容量加上主存的容量 5.一个作业由若干个作业步组成,在多道程序设计的系统中这些作业步可以并发执行。 6.作业调度是处理机的高级调度,进程调度是处理机的低级调度 7.I/0交通管理程序的主要功能是管理主存、控制器和通道 8.移臂调度的目标是使磁盘旋转周数最小 进程是一个独立的运行单位,也是系统进行资源分配和调度的基本单位 10.作业的联机控制方式适用于终端作业 (三)、填空题(9分) 1.UNIX操作系统在结构上分为两个部分: 2.把作业装入内存中随即进行地址变换的方式称为 ,而在作业执行期间,当访问到指 令或数据时才进行地址变换的方式称为 3.死锁产生的四个必要条件是:互斥控制、 4.多道程序设计的引入给存储管理提出了新的课题,应考虑的三个问题是
A.响应时间 B.周转时间 C.规定时间 D.调度时间 3.早期 UNIX 操作系统的存储管理采用_______方案。 A.段式管理 B.请求分页 C.可变式分区管理 D.固定式分区管理 4.在下列语言中属于脱机作业控制语言的是_______。 A.作业控制语言 B.汇编语言 C.会话式程序设计语言 D.解释 BASIC 语言 5.MS-DOS 中的文件物理结构采用_________。 A.连续结构 B.链接结构 C.索引结构 D.哈希表 6.在请求分页存储管理方案中,如果所需的页面不在内存中,则产生缺页中断,它属于______ 中断。 A.硬件故障 B.I/O C.外 D.程序中断 7.设有四个作业同时到达,每个作业的执行时间均为 2 小时,它们在仪态处理机上按单道方式 运行,则平均周转时间为________。 A.1 小时 B.5 小时 C.25 小时 D.8 小时 8.在关于 SPOOLING 的叙述中,_______描述是不正确的。 A.SPOOLING 系统中不需要独占设备 B.SPOOLING 系统加快了作业执行的速度 C.SPOOLING 系统使独占设备变成共享设备 D.SPOOLBNG 系统利用了处理器与通道并行工作的能力。 9.页式虚拟存储管理的主要特点是_____。 A.不要求将作业装入到主存的连续区域 B.不要求将作业同时全部装入到主存的连续区域 C.不要求进行缺页中断处理 D.不要求进行页面置换 10.下列文件中属于逻辑结构的文件是 A.连续文件 B.系统文件 C.散列文件 D.流式文件 (二)改错题(对错误的命题,请说明原因)(10 分) 1.采用多道程序设计的系统中,系统的程序道数越多,系统的效率就越高。 2.特权指令只能在管态下执行,而不能在算态下执行。 3.采用资源的静态分配算法可以预防死锁的发生。 4.一个虚拟的存储器,其地址空间的大小等于辅存的容量加上主存的容量。 5.一个作业由若干个作业步组成,在多道程序设计的系统中这些作业步可以并发执行。 6.作业调度是处理机的高级调度,进程调度是处理机的低级调度。 7.I/O 交通管理程序的主要功能是管理主存、控制器和通道。 8.移臂调度的目标是使磁盘旋转周数最小。 9.进程是一个独立的运行单位,也是系统进行资源分配和调度的基本单位。 10.作业的联机控制方式适用于终端作业。 (三)、填空题(9 分) 1.UNIX 操作系统在结构上分为两个部分:_______和_______。 2.把作业装入内存中随即进行地址变换的方式称为_______,而在作业执行期间,当访问到指 令或数据时才进行地址变换的方式称为________。 3.死锁产生的四个必要条件是:互斥控制、________、________、________。 4.多道程序设计的引入给存储管理提出了新的课题,应考虑的三个问题是________
5.在存储管理方案中,可用上下限地址寄存器存储保护的是 6.在UNIX文件管理系统中,为了对磁盘空间的空闲块进行有效的管理,采用的方法 7.为了记录设备的分配情况,操作系统应设置一张和三个控制块:设备控制块、 8.I/0设备处理进程平时处于状态,当和出现时被唤醒。 (四)综合题(21分) 1.什么叫”可再入”程序?它有什么特征? 2.简述UNIX的进程调度的公式和算法 3.给出UNDE进程的调度状态,当子进程终止时,处于什么状态? 4.假设有4个记录A、B、C、D存放在磁盘的某个磁道上,该磁道划分为4块,每块存放一个记 录,安排如下表所示 块号 记录号 D 现在要顺序处理这些记录,如果磁盘旋转速度为2ms转一周,处理程序每读出一个记录 后花5ms的时间进行处理。试问处理完这4个记录的总时间是多少?为了缩短处理时间应进行 优化分布,试问应如何安排这些记录?并计算处理的总时间。 5.有一个理发师,一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便 在理发椅子上睡觉:当一个顾客到来时,必须唤醒理发师,进行理发:如果理发师正在理发时, 又有顾客来到,则如果有空椅子可坐,他就坐下来等,如果没有空椅子,他就离开。为理发师和 顾客各编一段程序描述他们的行为,要求不能带有竞争条件。 西安电子科技大学2000考研操作系统试题答案 (一)单项选择题(10分) B2.C3.C4.A5.B6.D7.B8.C9.B10.D (二)改错题(对错误的命题,请说明原因)(10分) 1.错,系统的程序道数越多,并不能说明效率就越高 3.对 4.错,虚存大小与地址总线的位数有关。 5.错,作业之间并发执行 6.对 7.错,I/O交通管理程序管理设备、控制器、通道的全部状态信息等,但它不管理主存。 8.错,移臂调度以减少移臂时间为目的。 9.对 (三)填空题(9分) 1.外壳内核 2.静态地址再定位动态地址再定位 3.非剥夺控制零散请求环路条件 4.存储器分配虚存管理存储保护 5.分区分配 6.成组连接法
________、________。 5.在存储管理方案中,可用上下限地址寄存器存储保护的是______。 6.在 UNIX 文件管理系统中,为了对磁盘空间的空闲块进行有效的管理,采用的方法____。 7.为了记录设备的分配情况,操作系统应设置一张______和三个控制块: 设备控制块、 _______、_______。 8.I/O 设备处理进程平时处于_______状态,当______和______出现时被唤醒。 (四)综合题(21 分) 1.什么叫"可再入"程序? 它有什么特征? 2.简述 UNIX 的进程调度的公式和算法。 3.给出 UNDE 进程的调度状态,当子进程终止时,处于什么状态? 4.假设有 4 个记录 A、B、C、D 存放在磁盘的某个磁道上,该磁道划分为 4 块,每块存放一个记 录,安排如下表所示: 块号 1 2 3 4 记录号 A B C D 现在要顺序处理这些记录,如果磁盘旋转速度为 2Oms 转一周,处理程序每读出一个记录 后花 5ms 的时间进行处理。试问处理完这 4 个记录的总时间是多少?为了缩短处理时间应进行 优化分布,试问应如何安排这些记录?并计算处理的总时间。 5.有一个理发师,一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便 在理发椅子上睡觉:当一个顾客到来时,必须唤醒理发师,进行理发；如果理发师正在理发时, 又有顾客来到,则如果有空椅子可坐,他就坐下来等,如果没有空椅子,他就离开。为理发师和 顾客各编一段程序描述他们的行为,要求不能带有竞争条件。 西安电子科技大学 2000 考研操作系统试题答案 (一)单项选择题(10 分) 1.B 2.C 3.C 4.A 5.B 6.D 7.B 8.C 9.B 10.D (二)改错题(对错误的命题,请说明原因)(10 分) 1.错,系统的程序道数越多,并不能说明效率就越高。 2.对 3.对 4.错,虚存大小与地址总线的位数有关。 5.错,作业之间并发执行。 6.对 7.错,I/0 交通管理程序管理设备、控制器、通道的全部状态信息等,但它不管理主存。 8.错,移臂调度以减少移臂时间为目的。 9.对 10.对 (三)填空题（9 分) 1.外壳 内核 2.静态地址再定位 动态地址再定位 3.非剥夺控制 零散请求 环路条件 4.存储器分配 虚存管理 存储保护 5.分区分配 6.成组连接法
7.系统设备表控制器控制块通道控制块。 8.睡眠II0中断I/0请求 (四)综合题(21分) 可再入程序是能够被多个进程共享的程序段,代码不因程序的执行而改变,又称为可再入 码。纯代码的主要作用就是可被多个程序共享。其特点如下: (1)可再入程序必须是纯代码的,在执行中不变化。 (2)一个可再入程序要求调用者提供工作区,以保证程序以同样的方式为用户服务 (3)编译程序和操作系统程序通常是可再入程序,能同时被不同用户调用而形成不同进程 2.UNIX采用动态优先数调度算法,优先数的计算公式为 p pri=min 127, (p cpu/16+PUSER+p ice)) UNIX A4 6 H p pri=(p cpu/2+PUSER+NZERO UNIX System 优先数越大,优先级越低 3.在UNIX系统中,进程状态有:运行状态、就绪状态、睡眠状态、创建状态、僵尸状态 进程终止时处于僵尸状态 4优化前处理总时间=(5+5)+(5*3+5+5)+(5*3+5+5)+(5*3+5+5)=85ms 优化后记录顺序为:A,C,B,D 优化后处理总时间=(20/4+5)*4+5=45ms 5. #define CHAIRS 6/ *为等候的顾客准备的椅子数*/ emphore customers=o semphore barbers=0 semaphore /*用于互斥* int waiting=0 void barber I while (T) customer P(S) waiting =waiting -1 V(S) 理发 P(S); if (wait<CHAIRS) waiting=waiting+I V (customers) V(S) P(barbers) 坐下等待
7.系统设备表控 制器控制块 通道控制块。 8.睡眠 IIO 中断 I/O 请求 (四)综合题(21 分) 1.可再入程序是能够被多个进程共享的程序段,代码不因程序的执行而改变,又称为可再入 码。纯代码的主要作用就是可被多个程序共享。其特点如下: (1)可再入程序必须是纯代码的,在执行中不变化。 (2)一个可再入程序要求调用者提供工作区,以保证程序以同样的方式为用户服务。 (3)编译程序和操作系统程序通常是可再入程序,能同时被不同用户调用而形成不同进程。 2.UNIX 采用动态优先数调度算法,优先数的计算公式为: p_pri=min{127,(p_cpu/16+PUSER+p_ice)} UNIX 第 6 版 p_pri=(p_cpu/2+PUSER+NZERO) UNIX System 优先数越大,优先级越低。 3.在 UNIX 系统中,进程状态有: 运行状态、就绪状态、睡眠状态、创建状态、僵尸状态。当 进程终止时处于僵尸状态。 4.优化前处理总时间=(5+5)+(5*3+5+5)+(5*3+5+5)+(5*3+5+5)=85ms 优化后记录顺序为: A,C,B,D 优化后处理总时间=(20/4+5)*4+5=45ms 5. #define CHAIRS 6/ *为等候的顾客准备的椅子数*/ semphore customers=0; semphore barbers=O; semaphore S=1; /*用于互斥*/ int waiting=0; void barber() { while (T) { P(customers); P(S); waiting =waiting -1; V(bMbers); V(S); 理发... } } void customerO { P(S); if (wait<CHAIRS) { waiting=waiting+I; V(customers); V(S); P(barbers); 坐下等待: